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.
|
