Handles

IPC endpoints in Beelzebub are represented via handles.
A handle is an integer that makes sense only in the context of a handle table.
Each handle table will contain references to handles in other handle tables.

Note: The following definitions will help understand this document more easily:

• Handle: An IPC endpoint, represented by an integer.
• Hart: A hardware thread, such as a hyperthread in an Intel CPU with Hyperthreading, or a CPU core in a multi-core package, or the CPU in a single-core package. Term borrowed from Risc-V specs.
• Hazard pointer: Andrei Alexandrescu's article on the matter explains this.

Structures

Handle domain

struct HandleDomain
{
    HazardHandle HazardList; // This is a dummy node, the doubly-linked list is circular.
};

A handle domain represents a set of handle tables and active hazard handles that allows messaging between handles in the handle tables.
In the predictable future, the system will only have one handle domain. This should change at some point.

Hazard Handles

struct HazardHandle
{
    HandleTableEntry * Handle;
    HandleDomain * Domain;
    HazardHandle * Next, Prev;
};

In order to help keep the handle tables efficient, memory safety needs to be established to mitigate the ABA problem when performing atomic operations.
For this, hazard handles are used. A hazard handle consists of a hazard pointer to a handle entry within a handle table.

Each hart needs to have only one hazard handle in its specific data. This piece of memory is assumed to never be deallocated or otherwise reused in any way.

When a hart knows it's about to work with a handle entry or handle table, it will put the handle table entry pointer and the handle domain pointer in its hazard handle, and then add the hazard handle to the domain's hazard list.
After this, the information is checked again (making sure that the chosen handle table entry is still the one it's meant to work with) and updated if necessary.

When the hart needs to work with another handle table entry (e.g. to resolve a remote handle), it just changes the pointer to the handle table entry in its hazard handle.
When it's done working with handles, it sets the pointer to null and removes the hazard handle from the list.

With this system, the hazard handles are going to be written to by multiple harts, which is an important difference between this system and Andrei's hazard pointer implementation.
This allows iterating through fewer pointers under predicted normal operation.

When a hart wants to determine if a handle table or handle table entry is in use, it iterates through the relevant domain's list until it either finds the list head/dummy node or a node that's in the list of another handle domain.

Note: This will rather likely be changed in the future for the sake of performance, probably using an array.

Handle Tables

struct HandleTable
{
    HandleDomain * Domain;
    HandleTableEntry * FreeList; // Null when the table is full.
    size_t Length; // Number of entries in the table (of any type).
    HandleTableEntry[0] Entries; // The actual entries in the table.
};

A handle table is an array of handle table entries, which can either be local, remote, retired, or unallocated.
The unallocated entries form a singly-linked list, which is a stack of free handles.

Handle table resizing is still to be determined. Current plan involves using page faults and copy-on-write.

Handle Table Entries

Note: CompactPointer<T> represents a pointer that is as compact as possible, e.g. 48 bits on AMD64.

struct HandleTableEntry
{
    uint16_t Type : 2, ACL : 14;
    CompactPointer<HandleTableEntry> OtherEntry; // A reference to either the next free entry, or the remote entry referenced by a local entry, or a local entry referenced by a remote entry...
    uint32_t OtherHandle, Generation;
} __packed(1);

This structure should be 16 bytes in size (for 64-bit architectures) and doesn't really need full 16-byte atomic operations, because hazard handles will be used to ensure the entry is not reused.
Layout on 32-bit architectures is to be determined.

---

Operations

Note: CompareAndSwap(T * value, T * expected, T desired) is the signature used in the pseudocode below for compare-and-swap operations.

Hazard Handles

Handle Tables

Handle Table Entries

In a fresh handle table, all the entries form a stack of free entries (they are unallocated).
The following pseudocode shows how operations are implemented for handle table entries:

bool AllocateHandle(HandleTable * tab, uint32_t & han, uint32_t & gen)
{
    HandleTableEntry * entry = AtomicRead(&tab->FreeList), * next;

    EngageHazardHandle(tab->Domain);

    while (entry != NULL)
    {
        SetHazardHandle(entry, tab->Domain);
        //  Now this entry cannot transition to the unallocated type.

        if (entry->Type != Unallocated)
            continue;
        //  This entry has been used between reading it off the top of the free list and setting the hazard handle.

        next = entry->OtherEntry.Load();
        //  No transitions to unallocated means this won't change.

        if (CompareAndSwap(&tab->FreeList, &entry, next))
        {
            entry->OtherEntry.Store(null);
            
            han = entry - tab->Entries;
            gen = entry->Generation; // This was incremented when unallocated.

            ReleaseHazardHandle();

            return true;
        }
    }

    ReleaseHazardHandle();

    // TODO: Enlarge handle table? Check some limits?

    return false;
}

bool DeallocateHandle(HandleTable * tab, uint32_t han, uint32_t * gen)
{
    if (han >= tab->Length)
        return false;

    HandleTableEntry * entry = tab->Entries + han; // Doesn't need to be read atomically at once.
    uint16_t type = entry->Type;

    if (type == Retired || type == Unallocated)
        return false;
    //  This handle has been freed or is in the process of being freed.

    if (gen != NULL && *gen != entry->Generation)
        return false;
    //  If the handle generation is known, it's checked to make sure the right handle is deallocated.

    EngageHazardHandle(tab->Domain);
    SetHazardHandle(entry, tab->Domain);
    //  Now the handle cannot be unallocated.

    type = AtomicRead(entry->Type);

    do
    {
        if (type == Local || type == Remote)
            continue; // This causes the CAS.
        if (gen == NULL || *gen == AtomicRead(entry->Generation))
            continue;
        //  So if this either a local or remote handle of the specified generation, CAS is attempted.
        //  Otherwise this handle is either deallocating, unallocated, or le wrong generation.

        ReleaseHazardHandle();

        return false;
    } while (!CompareAndSwap(&entry->Type, &type, Retired));

    //  At this point, this hart is retiring this handle. Hazard point will be switched.

    HandleTableEntry * other = tab->OtherEntry.Load(); // Doesn't need to be read atomically at once.
    
    SetHazardHandle(other);

    ReleaseHazardHandle();

    return true;
}