20.500.12556/RUL-187783 Primerjava podatkovnih struktur za hranjenje pomnilniških oznak Comparison of data structures for storing memory tags V diplomskem delu so proučeni različni pristopi k programskemu označevanju pomnilnika ter njihove časovne in prostorske lastnosti. Za primerjavo so implementirane štiri podatkovne strukture: senčni pomnilnik, dvonivojska tabela, AVL drevo in kukavičja zgoščevalna tabela. Vse implementacije uporabljajo enoten vmesnik in skupno simulirano pomnilniško okolje, kar omogoča primerljivo izvajanje meritev. Pri posameznih pristopih so analizirane časovna zahtevnost operacij označevanja, preverjanja in sproščanja pomnilnika ter prostorska režija. Rezultati omogočajo primerjavo primernosti posameznih podatkovnih struktur glede na različne vzorce uporabe pomnilnika. Senčni pomnilnik omogoča najpreprostejše in najhitrejše preverjanje, vendar zahteva prostor za celoten pokriti naslovni prostor. Dvonivojska tabela zmanjša prostorsko porabo pri redko uporabljenem naslovnem prostoru, medtem ko AVL drevo in kukavičja zgoščevalna tabela shranjujeta informacije predvsem za dejansko uporabljene pomnilniške bloke. Delo tako pokaže kompromis med časovno zahtevnostjo, prostorsko režijo in načinom organizacije oznak pri programskih izvedbah označevanja pomnilnika. This thesis examines various approaches to software-based memory tagging, along with their time and space characteristics. Four data structures were implemented for comparison: shadow memory, a two-level table, an AVL tree, and a Cuckoo hash table. All implementations utilize a unified interface and a shared simulated memory environment, enabling comparable performance measurements. For each approach, the time complexity of tagging, checking, and untagging operations is analyzed, as is the memory overhead. The results allow for a comparison of the suitability of each data structure based on different memory usage patterns. Shadow memory offers the simplest and fastest checking mechanism but requires space to cover the entire address range. A two-level table reduces space consumption when the address space is sparsely used, whereas the AVL tree and Cuckoo hash table store information primarily for the memory blocks actually in use. Thus, the thesis demonstrates the trade-offs between time complexity, space overhead, and tag organization methods in software-based memory tagging implementations. Varnost pomnilnika označevanje pomnilnika ARM MTE senčni pomnilnik dvonivojska tabela AVL drevo Kukavičja zgoščevalna tabela podatkovne strukture Memory safety memory tagging ARM MTE shadow memory two-page table AVL tree Cuckoo hash table data structures true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2026-09-14 12:10:00 2026-09-14 12:10:04 2026-09-15 04:27:48 0000-00-00 00:00:00 2026 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 38892 Kristan_Matej_-_Primerjava_podatkovnih_struktur_za_hranjenje_pomnilniskih_oznak.pdf Kristan_Matej_-_Primerjava_podatkovnih_struktur_za_hranjenje_pomnilniskih_oznak.pdf 1 F8AF19B912CAA8D1C93AC31567629B2C 1ac5bfdfa1fb1da57e614c31ae2454e98c909c8c75629499e3ecbc388720618a 6c883617-b024-11f1-8bc5-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=247535 Fakulteta za računalništvo in informatiko 0 0 0