Add a memory-mappable binary serialization format (#7222)

The files `slang-fossil.{h,cpp}` define a new serialization format that is designed to support data being memory-mapped in and then traversed as-is.
The `docs/design/serialization.md` document was updated with details on this new format.

The `slang-serialize-fossil.{h,cpp}` files define implementations of the recently introduced `ISerializerImpl` interface for reading/writing this new binary format.
The overall structure of these implementations is heavily based on the existing RIFF implementation from `slang-serialize-riff.{h,cpp}`.

Switching the AST serialization over to use this format required almost no changes to `slang-serialize-ast.cpp`.
The new format is more space-efficient than the RIFF-based format in memory (by factor of over 2x), but is actually *worse* than the RIFF-based format in terms of how it affects the size of `slang.dll`, because the new format is seemingly less amenable to LZ4 compression.

A few pieces of utility code were added or moved as part of this work:

* The `core/slang-internally-linked-list.*` implementation is just a type that was used as part of `core/slang-riff.*`, but that wasn't really RIFF-specific.

* The `core/slang-blob-builder.*` files implement a low-level utility for building a binary format in memory out of "chunks". The overall structure of this type is based on the RIFF-specific builder implementation, but has been generalized so that it should apply to other kinds of binary serialization.

* The `core/slang-relative-ptr.h` file implements a simple relative pointer type, which is currently only used by the `slang-fossil.h` format.

If there are concerns about adopting the new format immediately for the AST, this change could be modified to introduce all the new code, but leave the AST serialization using the previous RIFF-based format.

8 files changed, 1064 insertions, 67 deletions

diff --git a/source/core/slang-blob-builder.cpp b/source/core/slang-blob-builder.cpp
new file mode 100644
index 000000000..10dd4003e
--- /dev/null
+++ b/source/core/slang-blob-builder.cpp
@@ -0,0 +1,473 @@
+// slang-blob-builder.cpp
+#include "slang-blob-builder.h"
+
+namespace Slang
+{
+
+//
+// BlobBuilder
+//
+
+BlobBuilder::BlobBuilder()
+    : _arena(4096)
+{
+}
+
+void BlobBuilder::writeTo(Stream* stream)
+{
+    // First we scan through all the chunks to set their
+    // absolute offsets, which enables us to compute the
+    // correct values for relative pointers when we write
+    // them out.
+    //
+    SLANG_MAYBE_UNUSED
+    Size sizeComputed = _calcSizeAndSetCachedChunkOffsets();
+
+    // Now we can scan through the chunks again and write
+    // the bytes of each of their shards.
+    //
+    SLANG_MAYBE_UNUSED
+    Size sizeWritten = _writeChunksTo(stream);
+
+    SLANG_ASSERT(sizeComputed == sizeWritten);
+}
+
+Size BlobBuilder::_calcSizeAndSetCachedChunkOffsets()
+{
+    Size totalSize = 0;
+    for (auto chunk : _chunks)
+    {
+        auto chunkPrefixSize = chunk->getPrefixSize();
+        auto chunkContentSize = chunk->getContentSize();
+        auto chunkAlignment = chunk->getAlignment();
+
+        // We add the size of the chunk prefix (if any) *before*
+        // aligning the current offset. Doing it this way
+        // means that sometimes the prefix can fit "for free"
+        // in space that would otherwise be padding.
+        //
+        // For example, if the current `totalSize` is 4, the
+        // `chunkAlignment` is 16, and the `chunkPrefixSize` is 8,
+        // then the sequence will be:
+        //
+        // * Add `totalSize += chunkPrefixSize`, resulting in a `totalSize`
+        //   of 12.
+        //
+        // * Round the `totalSize` up to the `chunkAlignment`, to compute
+        //   a `chunkOffset` of 16.
+        //
+        // The result is that the chunk's content starts at offset 16,
+        // and the prefix can occupy the 8 bytes before that (so the
+        // prefix is at offset 8).
+        //
+        // In the best case this approach can save a few bytes here or
+        // there when `chunkAlignment` is larger than the `chunkPrefixSize`,
+        // and in the worst case it does no harm.
+
+        totalSize += chunkPrefixSize;
+        auto chunkOffset = roundUpToAlignment(totalSize, chunkAlignment);
+
+        chunk->_setCachedOffset(chunkOffset);
+
+        totalSize = chunkOffset + chunkContentSize;
+    }
+    return totalSize;
+}
+
+Size BlobBuilder::_writeChunksTo(Stream* stream)
+{
+    Size totalSize = 0;
+    for (auto chunk : _chunks)
+    {
+        auto chunkPrefixSize = chunk->getPrefixSize();
+        auto chunkContentSize = chunk->getContentSize();
+        auto chunkOffset = chunk->_getCachedOffset();
+
+        SLANG_ASSERT(
+            chunkOffset == roundUpToAlignment(totalSize + chunkPrefixSize, chunk->getAlignment()));
+
+        auto paddingSize = chunkOffset - totalSize;
+
+        // The "padding" before the chunk's content also
+        // includes the space reserved for the chunk's prefix.
+        //
+        // We can thus subtract the prefix size from the number
+        // of pad bytes to write.
+
+        SLANG_ASSERT(paddingSize >= chunkPrefixSize);
+        paddingSize -= chunkPrefixSize;
+
+        while (paddingSize--)
+        {
+            Byte padding = 0;
+            stream->write(&padding, sizeof(padding));
+        }
+
+        // The `ChunkBuilder::_writeTo()` call will write the
+        // prefix *and* the chunk content, so it is appropriate
+        // to call it here even when the total number of bytes
+        // written to the stream is not equal to the `chunkOffset`
+        // (because in that case the total bytes written so far
+        // should be `chunkOffset - chunkPrefixSize`).
+        //
+        chunk->_writeTo(stream);
+
+        totalSize = chunkOffset + chunkContentSize;
+    }
+
+    return totalSize;
+}
+
+void BlobBuilder::writeToBlob(ISlangBlob** outBlob)
+{
+    OwnedMemoryStream stream(FileAccess::Write);
+    writeTo(&stream);
+
+    List<uint8_t> data;
+    stream.swapContents(data);
+
+    *outBlob = ListBlob::moveCreate(data).detach();
+}
+
+ChunkBuilder* BlobBuilder::createUnparentedChunk()
+{
+    auto chunk = new (_arena) ChunkBuilder(this);
+    return chunk;
+}
+
+void BlobBuilder::addChunk(ChunkBuilder* chunk)
+{
+    // TODO(tfoley): it would be good to have a way to assert
+    // that the chunk has not already been added.
+
+    _chunks.add(chunk);
+}
+
+ChunkBuilder* BlobBuilder::addChunk()
+{
+    auto chunk = new (_arena) ChunkBuilder(this);
+    _chunks.add(chunk);
+    return chunk;
+}
+
+ChunkBuilder* BlobBuilder::addChunkAfter(ChunkBuilder* existingChunk)
+{
+    auto newChunk = new (_arena) ChunkBuilder(this);
+    _chunks.insertAfter(existingChunk, newChunk);
+    return newChunk;
+}
+
+//
+// ChunkBuilder
+//
+
+void ChunkBuilder::setAlignmentToAtLeast(Size alignment)
+{
+    SLANG_ASSERT(alignment > 0);
+    SLANG_ASSERT(isPowerOfTwo(alignment));
+
+    _contentAlignment = std::max(_contentAlignment, alignment);
+}
+
+void ChunkBuilder::writePaddingToAlignTo(Size alignment)
+{
+    setAlignmentToAtLeast(alignment);
+
+    auto alignedSize = roundUpToAlignment(_contentSize, alignment);
+
+    auto requiredPaddingSize = alignedSize - _contentSize;
+
+    while (requiredPaddingSize)
+    {
+        Byte padByte = 0;
+        writeData(&padByte, sizeof(padByte));
+        requiredPaddingSize -= sizeof(padByte);
+    }
+}
+
+ChunkBuilder::ChunkBuilder(BlobBuilder* parentBlob)
+    : _parentBlob(parentBlob)
+{
+}
+
+Size ChunkBuilder::getContentSize() const
+{
+    return _contentSize;
+}
+
+Size ChunkBuilder::getPrefixSize() const
+{
+    if (!_prefixShard)
+        return 0;
+
+    return _prefixShard->getSize();
+}
+
+Size ChunkBuilder::getAlignment() const
+{
+    return _contentAlignment;
+}
+
+
+void ChunkBuilder::writeData(void const* data, Size size)
+{
+    // Adding no data should be a no-op.
+    //
+    if (size == 0)
+        return;
+
+
+    // The most interesting implementation detail here
+    // is that we will try to detect cases where we
+    // can re-use an existing `ShardBuilder` by adding the data
+    // to the end of that shard's allocation.
+    //
+    // This is only possible because of the way that
+    // we are using a single `MemoryArena` to allocate
+    // everything, which makes it possible that the
+    // next address the arena would return for an allocation
+    // of `size` bytes is the same as the ending address
+    // of the payload for the last shard of this chunk.
+    //
+    auto& arena = getParentBlob()->_getArena();
+
+    // We start by checking if this chunk already has
+    // a last shard that we could consider appending to.
+    //
+    auto lastShard = _childShards.getLast();
+    if (lastShard && lastShard->_kind == ShardBuilder::Kind::Data)
+    {
+        // If there is a last shard, then we can compute
+        // the end address of its payload, and see if
+        // it is the same as the cursor of the arena
+        // we are allocating from.
+        //
+        auto payload = lastShard->_data.ptr;
+        auto payloadSize = lastShard->_size;
+        auto payloadEnd = (Byte*)payload + payloadSize;
+        if (payloadEnd == arena.getCursor())
+        {
+            // Now that we've confirmed that the shard's
+            // payload ends at an address the arena could
+            // conceivably allocate from, we need to ask
+            // the arena to allocate `size` bytes from
+            // the current block it is using, and see if
+            // doing so succeeds.
+            //
+            if (arena.allocateCurrentUnaligned(size))
+            {
+                // At this point, we've confirmed that we
+                // are in our special case, and the relevant
+                // bytes have been allocated from the arena.
+                //
+                // Now we can simply write the new data at
+                // what used to be the end address for the
+                // shard's payload, and adjust its state
+                // to account for the new allocation.
+                //
+                ::memcpy(payloadEnd, data, size);
+
+                lastShard->_size = payloadSize + size;
+                _contentSize += size;
+                return;
+            }
+        }
+    }
+
+    // If the special case above doesn't apply, we simply
+    // allocate a new shard to hold the data that was
+    // passed in.
+    //
+    auto shard = _createDataShard(data, size);
+    _childShards.add(shard);
+    _contentSize += size;
+}
+
+void ChunkBuilder::addContentsOf(ChunkBuilder* otherChunk)
+{
+    auto otherPrefixShard = otherChunk->_prefixShard;
+    auto otherChunkSize = otherChunk->getContentSize();
+    auto otherChunkAlignment = otherChunk->getAlignment();
+    auto otherChunkShards = otherChunk->_childShards;
+
+    otherChunk->_prefixShard = nullptr;
+    otherChunk->_contentSize = 0;
+    otherChunk->_contentAlignment = 1;
+    otherChunk->_childShards = InternallyLinkedList<ShardBuilder>();
+
+    if (otherPrefixShard)
+    {
+        // If the other chunk included a prefix, then
+        // it only makes sense to append it in the case
+        // where *this* chunk is completely empty.
+
+        SLANG_ASSERT(!_prefixShard);
+        SLANG_ASSERT(!_childShards.getFirst());
+        _prefixShard = otherPrefixShard;
+    }
+
+    writePaddingToAlignTo(otherChunkAlignment);
+    _childShards.append(otherChunkShards);
+    _contentSize += otherChunkSize;
+}
+
+ChunkBuilder* ChunkBuilder::addChunkAfter()
+{
+    return getParentBlob()->addChunkAfter(this);
+}
+
+void ChunkBuilder::_writeRelativePtr(ChunkBuilder* targetChunk, Size ptrSize)
+{
+    SLANG_ASSERT(ptrSize != 0);
+    SLANG_ASSERT(ptrSize <= sizeof(UInt64));
+
+    writePaddingToAlignTo(ptrSize);
+
+    if (!targetChunk)
+    {
+        UInt64 value = 0;
+        writeData(&value, ptrSize);
+        return;
+    }
+
+    auto shard = _createRelativePtrShard(targetChunk, ptrSize);
+    _childShards.add(shard);
+    _contentSize += ptrSize;
+}
+
+void ChunkBuilder::_addPrefixRelativePtr(ChunkBuilder* targetChunk, Size ptrSize)
+{
+    SLANG_ASSERT(targetChunk != nullptr);
+    SLANG_ASSERT(ptrSize != 0);
+
+    SLANG_ASSERT(!_prefixShard);
+
+    setAlignmentToAtLeast(ptrSize);
+
+    auto shard = _createRelativePtrShard(targetChunk, ptrSize);
+    _prefixShard = shard;
+}
+
+void ChunkBuilder::addPrefixData(void const* data, Size size)
+{
+    SLANG_ASSERT(data != nullptr);
+    SLANG_ASSERT(size != 0);
+
+    SLANG_ASSERT(!_prefixShard);
+
+    setAlignmentToAtLeast(size);
+
+    auto shard = _createDataShard(data, size);
+    _prefixShard = shard;
+}
+
+ShardBuilder* ChunkBuilder::_createDataShard(void const* data, Size size)
+{
+    auto& arena = getParentBlob()->_getArena();
+    auto shard = new (arena) ShardBuilder(ShardBuilder::Kind::Data);
+
+    auto shardData = arena.allocateUnaligned(size);
+    ::memcpy(shardData, data, size);
+
+    shard->_data.ptr = shardData;
+    shard->_size = size;
+
+    return shard;
+}
+
+ShardBuilder* ChunkBuilder::_createRelativePtrShard(ChunkBuilder* targetChunk, Size ptrSize)
+{
+    auto& arena = getParentBlob()->_getArena();
+    auto shard = new (arena) ShardBuilder(ShardBuilder::Kind::RelativePtr);
+
+    shard->_relativePtr.targetChunk = targetChunk;
+    shard->_size = ptrSize;
+
+    return shard;
+}
+
+void ChunkBuilder::_writeTo(Stream* stream)
+{
+    auto chunkOffset = _getCachedOffset();
+
+    if (_prefixShard)
+    {
+        // Note that the prefix is written *before* the
+        // starting offset of the chunk's content, so we
+        // compute the appropriate offset to pass down.
+        //
+        auto prefixSize = _prefixShard->getSize();
+        auto prefixOffset = chunkOffset - prefixSize;
+
+        _prefixShard->_writeTo(stream, prefixOffset);
+    }
+
+    auto shardOffset = chunkOffset;
+    for (auto shard : _childShards)
+    {
+        shard->_writeTo(stream, shardOffset);
+        shardOffset += shard->getSize();
+    }
+    SLANG_ASSERT(shardOffset == chunkOffset + getContentSize());
+}
+
+
+//
+// ShardBuilder
+//
+
+ShardBuilder::ShardBuilder(Kind kind)
+    : _kind(kind)
+{
+}
+
+void ShardBuilder::_writeTo(Stream* stream, Size inSelfOffset)
+{
+    switch (_kind)
+    {
+    case Kind::Data:
+        {
+            stream->write(_data.ptr, _size);
+        }
+        break;
+
+    case Kind::RelativePtr:
+        {
+            auto targetChunk = _relativePtr.targetChunk;
+            SLANG_ASSERT(targetChunk);
+
+            auto selfOffset = intptr_t(inSelfOffset);
+            auto targetOffset = intptr_t(targetChunk->_getCachedOffset());
+
+            intptr_t relativeOffset = targetOffset - selfOffset;
+
+            switch (_size)
+            {
+            case sizeof(Int32):
+                {
+                    auto value = Int32(relativeOffset);
+                    stream->write(&value, sizeof(value));
+                }
+                break;
+
+            case sizeof(Int64):
+                {
+                    auto value = Int64(relativeOffset);
+                    stream->write(&value, sizeof(value));
+                }
+                break;
+
+            default:
+                SLANG_UNEXPECTED("unsupported relative pointer size");
+                break;
+            }
+        }
+        break;
+
+    default:
+        SLANG_UNEXPECTED("unknown Fossil::ShardBuilder::Kind");
+        break;
+    }
+}
+
+} // namespace Slang
diff --git a/source/core/slang-blob-builder.h b/source/core/slang-blob-builder.h
new file mode 100644
index 000000000..0b59ee7ab
--- /dev/null
+++ b/source/core/slang-blob-builder.h
@@ -0,0 +1,352 @@
+// slang-blob-builder.h
+#ifndef SLANG_BLOB_BUILDER_H
+#define SLANG_BLOB_BUILDER_H
+
+// This file provides utilities for building "blobs" of data
+// where, for purposes, a blob is a contiguous sequence of
+// bytes where the interpretation *of* those bytes depends
+// only on the bytes themselves, and not other factors like
+// the in-memory address of the blob, or the address/contents
+// of memory not in the blob.
+//
+// Superficially, the task seems simple: just maintain a
+// dynamically-sized array of bytes and append to it until
+// you're done. If that's what you need, you're probably
+// better off just using an `OwnedMemoryStream`.
+//
+// The utilities in this file deal with the case where you
+// want to build some kind of offset-based data structure,
+// so that parts of the blob will store byte offsets to
+// other parts, while also being able to build parts of
+// that structure "out of order", so that the final offset
+// of a particular piece of data in the blob may not be
+// known until everything *before* it has been fully built.
+
+#include "slang-basic.h"
+#include "slang-internally-linked-list.h"
+#include "slang-io.h"
+#include "slang-memory-arena.h"
+
+namespace Slang
+{
+
+inline constexpr bool isPowerOfTwo(Size value)
+{
+    return value > 0 && (value - 1 & value) == 0;
+}
+
+inline constexpr Size roundUpToAlignment(Size size, Size alignment)
+{
+    SLANG_ASSERT(isPowerOfTwo(alignment));
+
+    auto alignmentMask = Size(alignment) - 1;
+    return (size + alignmentMask) & ~alignmentMask;
+}
+
+class ShardBuilder;
+class ChunkBuilder;
+struct BlobBuilder;
+
+
+/// A utility type for composing a binary blob.
+///
+/// A blob builder allows a blob to be composed as a sequence of discrete
+/// chunks, allowing chunks to be added and written to in any order.
+///
+/// Chunks can contain (relative) pointers to one another, with the correct
+/// relative offsets being computed as part of writing the entire blob out.
+///
+struct BlobBuilder
+{
+public:
+    /// Construct an empty blob builder.
+    BlobBuilder();
+
+    /// Write the contents of the blob to the given `stream`.
+    void writeTo(Stream* stream);
+
+    /// Create a copy of the contents of the blob and assign to `outBlob`.
+    void writeToBlob(ISlangBlob** outBlob);
+
+    /// Add a new empty chunk to the end of the blob.
+    ChunkBuilder* addChunk();
+
+    /// Add a new empty chunk after the given `chunk`.
+    ChunkBuilder* addChunkAfter(ChunkBuilder* chunk);
+
+    /// Create a chunk that is not initially part of the blob.
+    ///
+    /// The contents of the returned chunk will only become
+    /// part of the full blob if `addChunk()` is called later,
+    /// *or* if the contents of the new chunk are moved into
+    /// another chunk that gets added.
+    ///
+    ChunkBuilder* createUnparentedChunk();
+
+    /// Add a chunk to the blob that was initially not part of the blob.
+    void addChunk(ChunkBuilder* chunk);
+
+private:
+    InternallyLinkedList<ChunkBuilder> _chunks;
+    MemoryArena _arena;
+
+    friend class ChunkBuilder;
+    friend class ShardBuilder;
+    MemoryArena& _getArena() { return _arena; }
+
+    Size _calcSizeAndSetCachedChunkOffsets();
+    Size _writeChunksTo(Stream* stream);
+};
+
+/// A chunk is a logically contiguous unit, such that data can
+/// only ever be appended to it. As a result, offsets that are
+/// relative to the start of a chunk are meaningful, and can be
+/// used to encode relative offsets for pointers.
+///
+/// Every `ChunkBuilder` is owned by its parent `BlobBuilder`.
+/// A pointer to a `ChunkBuilder` will only be valid during the
+/// lifetime of the parent `BlobBuilder`.
+///
+/// Conceptually, a `ChunkBuilder` has the following:
+///
+/// * A minimum *alignment* in bytes (initially 1)
+///
+/// * Zero or more bytes of *content* data (initially empty)
+///
+/// * An optional *prefix* consisting of zero or more bytes (initially absent)
+///
+/// The content may be a mix of raw data (e.g., added via `writeData()`),
+/// relative pointers to other chunks (`writeRelativePtr()`) and padding
+/// bytes (`writePaddingToAlignTo()`).
+///
+/// The prefix may only be either a single relative pointer, or a
+/// single range of raw data bytes.
+///
+/// When the parent blob written out as a flat buffer of bytes, the
+/// following are guaranteed:
+///
+/// * The content of the chunk will be a contiguous range of bytes
+///   starting at some offset, and will not overlap any other chunks.
+///
+/// * The byte offset where the chunk contents start will be a multiple
+///   of the chunk's minimum alignment.
+///
+/// * The bytes of the prefix (if any) will immediately precede the
+///   bytes of the content.
+///
+class ChunkBuilder : public InternallyLinkedList<ChunkBuilder>::Node
+{
+public:
+    /// Get the blob builder that this chunk belongs to.
+    BlobBuilder* getParentBlob() const { return _parentBlob; }
+
+    /// Get the required alignment of this chunk.
+    ///
+    /// The minimum alignment for a chunk starts at 1,
+    /// and may be increased by operations such as
+    /// `setAlignmentToAtLeast()` and `writePaddingToAlinTo()`.
+    ///
+    Size getAlignment() const;
+
+    /// Potentially increases the required alignment of this chunk.
+    ///
+    /// If the alignment of the chunk is less than `alignment`,
+    /// then it will be increased to `alignment`.
+    ///
+    /// The `alignment` passed in must be a power of two.
+    ///
+    void setAlignmentToAtLeast(Size alignment);
+
+    /// Get the size in bytes of the content of this chunk.
+    ///
+    /// Note that the size is not necessarily a multiple of the
+    /// alignment of the chunk.
+    ///
+    Size getContentSize() const;
+
+    /// Write data into the chunk.
+    ///
+    /// The chunk will retain a copy of the data passed in,
+    /// so the `data` pointer only needs to be valid for
+    /// the duration of the call.
+    ///
+    /// Note that this operation does *not* adjust the
+    /// alignment of the chunk in any way.
+    ///
+    /// The data must only contain types that can be copied
+    /// bit-for-bit, and that do not depend on addresses
+    /// in meory. In particular no pointers (absolute or
+    /// relative) should be written.
+    ///
+    void writeData(void const* data, Size size);
+
+    /// Append padding bytes to this chunk until its content size
+    /// is a multiple of `alignment`.
+    ///
+    /// May also increase the alignment of the chunk, as if
+    /// calling `setAlignmentToAtLeast(alignment)`.
+    ///
+    /// The padding bytes will all be zero.
+    ///
+    void writePaddingToAlignTo(Size alignment);
+
+    /// Write a relative pointer to the given `targetChunk`.
+    ///
+    /// The type parameter `T` is used to determine the size
+    /// of the relative pointer (should be either 4 or 8 bytes).
+    ///
+    /// The bytes that eventually get written will contain
+    /// the computed offset of `targetChunk` minus the computed
+    /// offset of the first byte of the relative pointer itself.
+    ///
+    /// Acts as is `writePaddingToAlignTo(sizeof(T))` were
+    /// called immediately before.
+    ///
+    template<typename T>
+    void writeRelativePtr(ChunkBuilder* targetChunk)
+    {
+        _writeRelativePtr(targetChunk, sizeof(T));
+    }
+
+    /// Append the contents of another chunk to this one.
+    ///
+    /// This *moves* all of the contents of `chunk` into `this`.
+    /// After the operation completes `chunk` will be an empty
+    /// chunk with one-byte alignment.
+    ///
+    /// This operation is useful when accumulating data that
+    /// needs to be appended to the chunk, but where the correct
+    /// alignment for that data is not yet known; a use can
+    /// effectively create a temporary "sub-chunk" and then append
+    /// it to the main chunk once its correct alignment is known.
+    ///
+    void addContentsOf(ChunkBuilder* chunk);
+
+    /// Get the size in bytes of the prefix of this chunk, if any.
+    ///
+    /// The prefix will be written so that the *end* offset of the
+    /// prefix data is the same as the starting offset of the
+    /// chunk's content.
+    ///
+    Size getPrefixSize() const;
+
+    /// Add a prefix to this chunk, consisting of raw data.
+    ///
+    /// This chunk must not already have a prefix.
+    ///
+    void addPrefixData(void const* data, Size size);
+
+    /// Add a prefix to this chunk, consisting of a relative pointer.
+    ///
+    /// This chunk must not already have a prefix.
+    ///
+    /// Updates the alignment of the chunk as if making a call to
+    /// `setAlignmentToAtLeast(sizeof(T))`.
+    ///
+    template<typename T>
+    void addPrefixRelativePtr(ChunkBuilder* targetChunk)
+    {
+        _addPrefixRelativePtr(targetChunk, sizeof(T));
+    }
+
+    /// Insert a new chunk into the blob, immediately after this chunk.
+    ///
+    ChunkBuilder* addChunkAfter();
+
+private:
+    ChunkBuilder() = delete;
+    ChunkBuilder(ChunkBuilder const&) = delete;
+    ChunkBuilder(ChunkBuilder&&) = delete;
+
+    friend struct BlobBuilder;
+    friend class ShardBuilder;
+
+    ChunkBuilder(BlobBuilder* parentBlob);
+
+    Size _contentSize = 0;
+    Size _contentAlignment = 1;
+
+    InternallyLinkedList<ShardBuilder> _childShards;
+    BlobBuilder* _parentBlob = nullptr;
+
+    Size _cachedOffset = ~Size(0);
+    Size _getCachedOffset() { return _cachedOffset; }
+    void _setCachedOffset(Size offset) { _cachedOffset = offset; }
+
+    void _writeRelativePtr(ChunkBuilder* targetChunk, Size ptrSize);
+
+    ShardBuilder* _createDataShard(void const* data, Size size);
+    ShardBuilder* _createRelativePtrShard(ChunkBuilder* targetChunk, Size ptrSize);
+
+    ShardBuilder* _prefixShard = nullptr;
+
+    void _writeTo(Stream* stream);
+
+    void _addPrefixRelativePtr(ChunkBuilder* targetChunk, Size ptrSize);
+};
+
+/// A shard is a unit of contiguously-allocated data that makes
+/// up part of a chunk.
+///
+/// Shards are *not* meant to be directly manipulated by users;
+/// they are an implementation detail of `ChunkBuilder`.
+///
+/// Every `ShardBuilder` is owned by its parent `ChunkBuilder`.
+/// A pointer to a `ShardBuilder` will only be valid during the
+/// lifetime of the parent `ChunkBuilder`.
+///
+class ShardBuilder : public InternallyLinkedList<ShardBuilder>::Node
+{
+public:
+    // There are two kinds of shards that may appear in a chunk:
+    //
+    // * Shards that hold plain data that will be part of the
+    //   serialized chunk.
+    //
+    // * Shards that represent a relative pointer to some chunk,
+    //   which cannot have their exact binary value determined
+    //   until the offsets of chunk/shards have been finalized.
+
+    enum class Kind
+    {
+        Data,
+        RelativePtr,
+    };
+
+    Size getSize() const { return _size; }
+
+private:
+    ShardBuilder() = delete;
+    ShardBuilder(ShardBuilder const&) = delete;
+    ShardBuilder(ShardBuilder&&) = delete;
+
+    friend class ChunkBuilder;
+    ShardBuilder(Kind kind);
+
+    void _writeTo(Stream* stream, Size selfOffset);
+
+    /// Kind of this shard (data or relative pointer)
+    Kind _kind = Kind::Data;
+
+    union
+    {
+        /// Used when `_kind == Kind::Data`
+        struct
+        {
+            void const* ptr;
+        } _data;
+
+        /// Used when `_kind == Kind::RelativePtr`
+        struct
+        {
+            ChunkBuilder* targetChunk;
+        } _relativePtr;
+    };
+
+    // Size of this shard in bytes.
+    Size _size = 0;
+};
+
+} // namespace Slang
+
+#endif
diff --git a/source/core/slang-internally-linked-list.cpp b/source/core/slang-internally-linked-list.cpp
new file mode 100644
index 000000000..27bbd77b0
--- /dev/null
+++ b/source/core/slang-internally-linked-list.cpp
@@ -0,0 +1,2 @@
+// slang-internally-linked-list.cpp
+#include "slang-internally-linked-list.h"
diff --git a/source/core/slang-internally-linked-list.h b/source/core/slang-internally-linked-list.h
new file mode 100644
index 000000000..168885531
--- /dev/null
+++ b/source/core/slang-internally-linked-list.h
@@ -0,0 +1,126 @@
+// slang-internally-linked-list.h
+#ifndef SLANG_INTERNALLY_LINKED_LIST_H
+#define SLANG_INTERNALLY_LINKED_LIST_H
+
+// This file provides support for the idiom of a linked
+// list of values where the "next" pointer is stored in
+// the values themselves (thus requiring no additional
+// allocation for list nodes, at the price of any given
+// value only being able to appear in a single list).
+
+#include "slang-basic.h"
+
+namespace Slang
+{
+
+/// A linked list where the elements are themselves the nodes.
+///
+/// The type parameter `T` should be a type that publicly
+/// inherits from `InternallyLinkedList<T>::Node`.
+///
+template<typename T>
+struct InternallyLinkedList
+{
+public:
+    struct Node
+    {
+    public:
+        Node() {}
+
+    private:
+        friend struct InternallyLinkedList<T>;
+        T* _next = nullptr;
+    };
+
+    struct Iterator
+    {
+    public:
+        Iterator() {}
+
+        Iterator(T* node)
+            : _node(node)
+        {
+        }
+
+        T* operator*() const { return _node; }
+
+        void operator++() { _node = static_cast<Node const*>(_node)->_next; }
+
+        bool operator!=(Iterator const& that) const { return _node != that._node; }
+
+    private:
+        T* _node = nullptr;
+    };
+
+    Iterator begin() { return Iterator(_first); }
+
+    Iterator end() { return Iterator(); }
+
+    T* getFirst() const { return _first; }
+
+    T* getLast() const { return _last; }
+
+    void add(T* element)
+    {
+        SLANG_ASSERT(element != nullptr);
+        if (!_last)
+        {
+            SLANG_ASSERT(_first == nullptr);
+
+            _first = element;
+            _last = element;
+        }
+        else
+        {
+            SLANG_ASSERT(_first != nullptr);
+
+            _last->_next = element;
+            _last = element;
+        }
+    }
+
+    void insertAfter(T* existingElement, T* newElement)
+    {
+        SLANG_ASSERT(existingElement != nullptr);
+        SLANG_ASSERT(newElement != nullptr);
+        if (existingElement == _last)
+        {
+            add(newElement);
+        }
+        else
+        {
+            newElement->_next = existingElement->_next;
+            existingElement->_next = newElement;
+        }
+    }
+
+    void append(InternallyLinkedList<T> const& other)
+    {
+        if (!other._first)
+        {
+        }
+        else if (!_last)
+        {
+            _first = other._first;
+            _last = other._last;
+        }
+        else
+        {
+            SLANG_ASSERT(_first != nullptr);
+
+            _last->_next = other._first;
+            _last = other._last;
+        }
+    }
+
+private:
+    T* _first = nullptr;
+    T* _last = nullptr;
+};
+
+template<typename T>
+using InternallyLinkedListNode = InternallyLinkedList<T>::Node;
+
+} // namespace Slang
+
+#endif
diff --git a/source/core/slang-memory-arena.h b/source/core/slang-memory-arena.h
index 03631befe..714918b9a 100644
--- a/source/core/slang-memory-arena.h
+++ b/source/core/slang-memory-arena.h
@@ -476,4 +476,15 @@ SLANG_FORCE_INLINE void operator delete(void* memory, Slang::MemoryArena& arena)
     SLANG_UNUSED(arena);
 }
 
+SLANG_FORCE_INLINE void* operator new[](size_t size, Slang::MemoryArena& arena)
+{
+    return arena.allocate(size);
+}
+
+SLANG_FORCE_INLINE void operator delete[](void* memory, Slang::MemoryArena& arena)
+{
+    SLANG_UNUSED(memory);
+    SLANG_UNUSED(arena);
+}
+
 #endif // SLANG_MEMORY_ARENA_H
diff --git a/source/core/slang-relative-ptr.cpp b/source/core/slang-relative-ptr.cpp
new file mode 100644
index 000000000..0c4da2c6e
--- /dev/null
+++ b/source/core/slang-relative-ptr.cpp
@@ -0,0 +1,2 @@
+// slang-relative-ptr.cpp
+#include "slang-relative-ptr.h"
diff --git a/source/core/slang-relative-ptr.h b/source/core/slang-relative-ptr.h
new file mode 100644
index 000000000..6c4bc942c
--- /dev/null
+++ b/source/core/slang-relative-ptr.h
@@ -0,0 +1,97 @@
+// slang-relative-ptr.h
+#ifndef SLANG_RELATIVE_PTR_H
+#define SLANG_RELATIVE_PTR_H
+
+// This file implements a smart pointer type `RelativePtr<T>`
+// that, rather than storing the actual *address* of a value
+// of type `T`, stores the relative offset (in bytes) between
+// the target `T*` and the address of the `RelativePtr<T>`
+// itself.
+//
+// This kind of pointer representation can be useful when
+// implementing "memory-mappable" data structures that can
+// still conveniently represent complicated object graphs.
+
+#include "slang-basic.h"
+
+namespace Slang
+{
+namespace detail
+{
+struct RelativePtr32Traits
+{
+    using Offset = Int32;
+    using UOffset = UInt32;
+};
+
+struct RelativePtr64Traits
+{
+    using Offset = Int64;
+    using UOffset = UInt64;
+};
+} // namespace detail
+
+template<typename T, typename Traits>
+struct RelativePtr
+{
+public:
+    using This = RelativePtr<T, Traits>;
+    using Value = T;
+    using RawPtr = T*;
+    using Offset = typename Traits::Offset;
+    using UOffset = typename Traits::UOffset;
+
+    RelativePtr() = default;
+    RelativePtr(RelativePtr const& ptr) { set(ptr); }
+    RelativePtr(RelativePtr&& ptr) { set(ptr); }
+    RelativePtr(T* ptr) { set(ptr); }
+
+    void operator=(RelativePtr const& ptr) { set(ptr); }
+    void operator=(RelativePtr&& ptr) { set(ptr); }
+    void operator=(T* ptr) { set(ptr); }
+
+    T* get() const
+    {
+        if (_offset == 0)
+        {
+            return nullptr;
+        }
+
+        intptr_t thisAddr = intptr_t(this);
+        intptr_t targetAddr = thisAddr + intptr_t(_offset);
+
+        return (T*)(targetAddr);
+    }
+
+    void set(T* ptr)
+    {
+        if (ptr == nullptr)
+        {
+            _offset = 0;
+            return;
+        }
+
+        intptr_t thisAddr = intptr_t(this);
+        intptr_t targetAddr = intptr_t(ptr);
+        intptr_t offsetVal = targetAddr - thisAddr;
+
+        _offset = Offset(offsetVal);
+        SLANG_ASSERT(intptr_t(_offset) == offsetVal);
+    }
+
+    operator T*() const { return get(); }
+    T* operator->() const { return get(); }
+
+private:
+    Offset _offset = 0;
+};
+
+template<typename T>
+using RelativePtr32 = RelativePtr<T, detail::RelativePtr32Traits>;
+
+template<typename T>
+using RelativePtr64 = RelativePtr<T, detail::RelativePtr64Traits>;
+
+} // namespace Slang
+
+#endif
diff --git a/source/core/slang-riff.h b/source/core/slang-riff.h
index 20b1d7c66..9459c8a55 100644
--- a/source/core/slang-riff.h
+++ b/source/core/slang-riff.h
@@ -16,6 +16,7 @@
 //
 
 #include "slang-basic.h"
+#include "slang-internally-linked-list.h"
 #include "slang-memory-arena.h"
 #include "slang-stream.h"
 #include "slang-writer.h"
@@ -564,73 +565,6 @@ T const* as(Chunk const* chunk)
     return static_cast<T const*>(chunk);
 }
 
-/// A linked list where the elements are themselves the nodes.
-///
-template<typename T>
-struct InternallyLinkedList
-{
-public:
-    struct Node
-    {
-    public:
-        Node() {}
-
-    private:
-        friend struct InternallyLinkedList<T>;
-        T* _next = nullptr;
-    };
-
-    struct Iterator
-    {
-    public:
-        Iterator() {}
-
-        Iterator(T* node)
-            : _node(node)
-        {
-        }
-
-        T* operator*() const { return _node; }
-
-        void operator++() { _node = static_cast<Node const*>(_node)->_next; }
-
-        bool operator!=(Iterator const& that) const { return _node != that._node; }
-
-    private:
-        T* _node = nullptr;
-    };
-
-    Iterator begin() { return Iterator(_first); }
-
-    Iterator end() { return Iterator(); }
-
-    T* getFirst() const { return _first; }
-
-    T* getLast() const { return _last; }
-
-    void add(T* element)
-    {
-        if (!_last)
-        {
-            SLANG_ASSERT(_first == nullptr);
-
-            _first = element;
-            _last = element;
-        }
-        else
-        {
-            SLANG_ASSERT(_first != nullptr);
-
-            _last->_next = element;
-            _last = element;
-        }
-    }
-
-private:
-    T* _first = nullptr;
-    T* _last = nullptr;
-};
-
 /// A builder for a chunk in a RIFF.
 class ChunkBuilder : public InternallyLinkedList<ChunkBuilder>::Node
 {