Skip to content

Allocator: consider runtime-typed headers #656

@nwf

Description

@nwf

MChunkHeaders serve, largely, to dynamically carve up the heap into 8-byte aligned spans of space and to track whether these spans are allocated or free. There's some coalescing and indexing logic for free spans, but that's about all you need for an allocator's core, and that's basically what alloc.h gives you. Great.

And then came the rest of the owl^Wallocator. Headers where then pressed into service tracking additional state for "higher layers" (that is, main.cc):

  • Whether an allocated object is the result of the token object creation APIs (isSealedObject),
  • An ownership relationship between quotas and allocated objects (ownerID),
  • A notion of claims associated with allocated objects (claims).

(With the exception of claims, which is checked in one place in alloc.h, none of these fields are really meaningfully manipulated in alloc.h.) Moreover, the "rest of the allocator" uses the allocator core to create objects for its own purposes! Presently, there are Claim objects and soon there will be dynamic sub-quotas. Claim objects, despite being allocated chunks of the heap, are neither owned (after the fix of #651) nor claim-able, and yet their payloads hold both an owner identifier and a (further) claims field as the MChunkHeader! (But do see possible future work in #655.) Dynamic sub-quotas, similarly, will be allocated objects and might even be subject to user claims (!), but are not really "owned" in the sense currently meant (but sure are associated with parent quotas).

All of this suggests that maybe the boundary between alloc.h and main.cc is, at the very least, awkward and perhaps should be revisited.

In particular, maybe we want a runtime-type tag field in the header. Every header would continue to carry its isPrevInUse flag and successor and predecessor linkages (well, see the orthogonal violence of #332). But now the rest of the bits are a tag field and then interpreted dependently.

  • Free chunks do not have owners or claimants. Their payloads are known to be indexing metadata.
  • Ordinary allocated chunks have owners and/or claimants and arbitrary payloads.
  • Sealed allocated chunks share the same additional header fields as ordinary objects. Their payloads are known to contain runtime ocap headers (though exactly where is possibly a bit of fun arithmetic; that could be fixed. See Use @jrtc27's approach to enable large sealed objects. #244 for details.).
  • Claim objects need not have owner or claimant fields in the same sense as other allocated objects. We can reuse these bits to hold part of the claim metadata. This probably frees up enough room in the object payload that we can either include backwards references to the associated (claimed) object or make the claims chain a ring; this may be of interest to iterators like heap_free_all.
  • Dynamic subquota objects may be subject to claims but can repurpose the owner bits of an allocated object to track their parent.

This all seems doable, and like it would be useful, but my initial reaction is that we might want to hold off until we have explored a RiiR allocator implementation, given the resulting increased reliance on case analysis?

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    Status

    Todo

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions