Efficient Tagged Memory

Authors:
  • AJAlexandre Joannou
    Alexandre Joannou
  • JWJonathan Woodruff
    Jonathan Woodruff
  • RKRobert Kovacsics
    Robert Kovacsics
  • SMSimon W. Moore
    Simon W. Moore
  • ABAlex Bradbury
    Alex Bradbury
  • RWRobert N.M. Watson
    Robert N.M. Watson
  • DCDavid Chisnall
    David Chisnall
  • MRMichael Roe
    Michael Roe
  • BDBrooks Davis
    Brooks Davis
  • ENEdward Napierala
    Edward Napierala
  • JBJohn Baldwin
    John Baldwin

Abstract
We characterize the cache behavior of an in-memory tag table and demonstrate that an optimized implementation can typically achieve a near-zero memory traffic overhead. Both industry and academia have repeatedly demonstrated tagged memory as a key mechanism to enable enforcement of powerful security invariants, including capabilities, pointer integrity, watchpoints, and information-flow tracking. A single-bit tag shadowspace is the most commonly proposed requirement, as one bit is the minimum metadata needed to distinguish between an untyped data word and any number of new hardware-enforced types. We survey various tag shadowspace approaches and identify their common requirements and positive features of their implementations. To avoid non-standard memory widths, we identify the most practical implementation for tag storage to be an in-memory table managed next to the DRAM controller. We characterize the caching performance of such a tag table and demonstrate a DRAM traffic overhead below 5% for the vast majority of applications. We identify spatial locality on a page scale as the primary factor that enables surprisingly high table cache-ability. We then demonstrate tag-table compression for a set of common applications. A hierarchical structure with elegantly simple optimizations reduces DRAM traffic overhead to below 1% for most applications. These insights and optimizations pave the way for commercial applications making use of single-bit tags stored in commodity memory.

This publication has 21 references indexed in Scilit: