Memory Tagging and the Granule Trade-Off

The software approaches to this problem pay for safety in cycles. Every access carries a check, every allocation carries redzones, and every free carries a quarantine. Memory tagging moves the check into the load and store units themselves, which makes the per-access cost close to nothing but changes what the check can see: the hardware compares a few bits against a few bits, at a fixed granule, and everything about the scheme follows from that granularity.

The idea is old enough to have been implemented more than once under different names. Oracle’s SPARC M7 shipped it as Application Data Integrity, with a version number in the unused high bits of the pointer and a matching version stored per 64-byte line. Arm’s Memory Tagging Extension, part of Armv8.5, uses a four-bit allocation tag in the top byte of the address and a matching tag per 16-byte granule. Both spend four bits on the tag; they differ in where those bits sit in the pointer and in the granule size. The mechanism is the same.

A tag in the pointer, a tag in memory

On a 64-bit architecture the top byte of a pointer is ignored by the address translation hardware, a facility the architecture provides for exactly this kind of metadata. Tagging schemes consume it. Arm’s MTE puts a four-bit allocation tag in that byte, alongside four bits the architecture already treats as ignored. The address the hardware uses for the access is the pointer with the tag bits cleared, and the tag is carried alongside the access as an extra qualifier.

Every 16-byte granule of memory has a four-bit tag associated with it, stored in a parallel tag region rather than inline with the data. Inline tags would change the layout of every structure and break the assumption that consecutive bytes are contiguous; the separate region keeps data layout intact and makes tag storage an address-space cost rather than a memory-layout cost. The tag region is one thirty-second of the address space, since one byte of tag covers two granules of 16 bytes when the tag is packed four bits to a byte.

An access is permitted when the pointer’s tag equals the granule’s tag. The comparison is on the four-bit tag only; the 56 address bits below the tag byte are unrestricted within the mapped region, so a tagged pointer can point anywhere its tag matches.

/* Conceptually, the split and comparison a tagged load performs. */
#define ADDR_MASK 0x00ffffffffffffffULL   /* low 56 bits carry the address */

unsigned char load_tagged(const unsigned char *p)
{
    unsigned tag  = (uintptr_t)p >> 56 & 0xf;                  /* allocation tag  */
    const unsigned char *addr = (const unsigned char *)((uintptr_t)p & ADDR_MASK);
    if (tag != granule_tag(addr >> 4))                          /* memory tag      */
        raise_fault(addr);                                      /* mismatch        */
    return *addr;
}

That is the crucial difference from a capability scheme, and the reason tagging is a probabilistic defence rather than a bounds mechanism.

Allocation tags and the reuse cycle

The allocator’s job is to give each allocation a tag, store that tag on every granule the allocation covers, and return pointers carrying it. On free, the tag is changed to a different random value, so that pointers from the previous allocation no longer match. On reallocation, a fresh tag is chosen.

The result is a heap in which a stale pointer carries a tag that the recycled block no longer has. The next access through the stale pointer fails the comparison and faults, and the fault is attributed to the access rather than to the free, which is the diagnostic property the software sanitizers achieve with quarantine. No quarantine is needed here, because the block can be reused immediately: the tag, not the mapping, encodes the generation.

Out-of-bounds accesses within an allocation’s last granule are invisible. An allocation of 20 bytes occupies two granules, one of 16 and one of 4, and the second granule’s tag matches the pointer’s tag for all 16 of its bytes. Bytes 20 through 31 are past the end of the object and still carry the object’s tag, so a write to byte 21 passes. This is the granule trade: a 16-byte granule means the last up-to-15 bytes of slack in each allocation are unchecked, and an overflow of fewer than 16 bytes that stays within the object’s final granule produces no fault.

Reducing the granule reduces the slack. A 4-bit tag per 4-byte granule would quadruple the tag region and require a tag lookup per word rather than per cache line, which is why the implementations chose 16 and 64 bytes rather than something smaller. The choice is a direct exchange between tag storage, check granularity, and the size of the blind spot at the end of every object.

Synchronous, asynchronous, and the cost of reporting

Tag mismatches can be reported synchronously or asynchronously, with a hybrid of the two as a third option, and the choice determines whether the feature is usable in a deployed service.

In synchronous mode the access that fails the check faults immediately, with the faulting address and the instruction available to the handler. The signal carries enough information to identify the access, and the runtime can print a report with the pointer’s tag, the memory’s tag, and the allocation history if the allocator kept it. The cost is that every access must be checked before it completes, which the hardware does by comparing tags in the load-store path: no extra instruction, but a comparison in the pipeline and a tag load that may miss in the tag cache.

In asynchronous mode the check is deferred. The hardware allows the access, records the mismatch in a register, and the runtime reads the register at some later point, typically on a context switch or another entry into the kernel. The fault then arrives at an unrelated instruction, with no reliable way to identify the access that caused it, and the register may have been overwritten by several later mismatches. What asynchronous mode loses in diagnosis it gains in scheduling freedom: the tag load does not have to complete before the access retires, so the pipeline is not stalled on it.

The third mode is asymmetric: loads are checked synchronously, so a faulty read faults at the instruction that issued it, while stores are checked asynchronously, so a faulty write is recorded and reported later without stalling the store. The rationale is that loads feed instructions that depend on their result, so a faulting load is caught where the value is used, whereas a store has no such dependent consumer. Implementations expose all three because the right choice depends on the deployment: synchronous for development and for high-value processes, asynchronous for a fleet-wide deployment where the cost of a stall on every access is unacceptable.

The tag cache is the hardware’s answer to the tag-region access cost. Tags for recently accessed granules are held in a small structure indexed by address, so a sequential walk over an allocation hits the cache after the first granule. A random access pattern over a large working set misses, and each miss is a memory access to the tag region, the same cost as a data access that misses in L1. This is the honest reason the feature is described as low overhead rather than free.

Probabilistic guarantees and the number of tags

Four bits give sixteen possible tags. If the allocator chooses uniformly at random, the probability that a stale pointer’s tag matches the tag of the block that replaced it is one in sixteen. An attacker who can retry the operation, such as a service that accepts requests or a fuzzer that feeds inputs, succeeds after a small number of attempts, and the number is small enough to be practical.

That is not a flaw in the implementation; it is the design point. Memory tagging is not claimed to prevent a determined attacker with unlimited attempts. It is claimed to raise the cost of exploiting a memory-safety bug by a constant factor and to convert a class of silent corruption into a detected event. For a bug that is reached once per input, a one-in-sixteen chance of detection is a strong deterrent; for a bug in a loop that retries until success, it is not.

The tag space can be used more carefully. An allocator can avoid reusing a tag that is still live in the address space, which reduces the collision probability for the allocations that matter; it can derive tags from the address so that neighbouring allocations differ; and it can use the reserved tag values to mark special states. None of these change the fundamental bound, which is that the tag has four bits and the attacker can observe the result of an attempt.

The other half of the probabilistic argument is the pointer’s tag being secret. If the attacker knows the tag of the target block, the one-in-sixteen becomes one-in-one. Tag values are observable through any read primitive that can read a pointer, and pointers carrying tags are stored in structures the program can read. The tag is therefore a defence against a bug that corrupts an address without giving the attacker a read of the surrounding memory, and much weaker against an attacker who already has a read primitive.

Where the scheme sits among the others

Compared with shadow-memory instrumentation, tagging has a much lower per-access cost and a coarser check. The sanitizer’s shadow byte encodes a partial granule count, so it catches a five-byte overflow exactly; the tag’s four bits cannot express “four bytes valid” for a 16-byte granule, so the same overflow is caught only if it crosses into the next granule. The sanitizer also distinguishes freed memory from redzone memory and can report which kind of violation occurred; the tag knows only that the values differ.

Compared with capabilities, tagging is a much smaller change to the architecture. A capability replaces the pointer with a 128-bit object carrying bounds and permissions, which requires recompiling everything and changing the ABI; a tag occupies spare bits of an existing 64-bit pointer and is ignored by code that does not use it, so tagged and untagged code can coexist in one process. That compatibility is why tagging has shipped in general-purpose processors while capabilities remain confined to research and specialised silicon.

The deployment friction is in the allocator and the runtime, not the instruction set. The allocator must tag on allocation and retag on free, which means the heap implementation is aware of the feature; the kernel must map the tag region and handle the faults; the runtime must know how to interpret a tag fault and produce a useful report. Where the allocator is unaware, as with a program using a custom allocator or memory from a source the runtime does not control, the granules carry whatever tag they happened to have, and the checks are meaningless. The feature is only as good as the discipline of every component that hands out memory.