Virtual memory as a dictionary

mmapDictionary.c

// An experiment of using the virtual memory as a huge directly addressed map/dictionary.

#include <stdio.h>
#include <stdint.h>
#include <sys/mman.h>

uint64_t setupMemory(uint64_t virtualSize);

int main()
{
    uint64_t keyBits    = 32;               // 4 Gi possible keys
    uint64_t keySpace   = (1UL << keyBits);
    uint32_t recordSize = sizeof(int);      // using int as the record type

    // As long as the arch & cpu supports it
    // (check virtual address space - in 64bit linux == 128 TiB)
    // the following can greatly exceed the physical memory size.
    uint64_t memSize = recordSize * keySpace;
    uint64_t start = setupMemory(memSize);
    printf("Reserved memory will start at: 0x%016lX (%lu)\n", start, start);

    {
        // Given a key
        uint64_t key = 0x01234567; // Note: key < keySpace
        // we can get its address
        void *keyAddr = (void *)(start + key * recordSize);
        // and now cast it to the type we want
        int *val_p = (int *)keyAddr;
        // and set it to anything we want
        *val_p = 555;
    }

    // We can also use array indexing syntax:

    int *dict = (int *)start;

    // same as before, but much cleaner
    {
        uint64_t key = 0x01234567;
        dict[key] = 555;
    }


    // The first time we set the value, the kernel will allocate a physical page,
    // which will contain the value, as well as the values of adjacent keys.

    // Later, we can retrieve the value
    {
        uint64_t key = 0x01234567;
        int val = dict[key];

        printf("%d\n", val); // should print 555
    }

    // This time, the mem page had already been allocated,
    // its virtual address was (probably) already in the TLB,
    // and the contained record in cache,
    // so we got a fast lookup.

    // Certainly, this only works well for very frequent accesses to a small set of keys,
    // or in cases where the record size is comparable to the page's size (or larger),
    // as translating and fetching a new page from memory is quite expensive.

    // If a key doesn't exist when we try to read its address,
    // the kernel will (?) allocate its corresponding page,
    // and fill it with zeros, so the value read will be 0.
    {
        uint64_t key = 0x00112233;
        int val = dict[key];

        printf("%d\n", val); // should print 0
    }
}


// Reserves the requested virtual memory and returns its starting address.
// On error, it returns 0 (== NULL).
// 'virtualSize' must be a multiple of the page size (sysconf(_SC_PAGESIZE))
uint64_t setupMemory(uint64_t virtualSize)
{
    // We can't start at 0, and have to start at a multiple of page size.
    // So let's pick 1 * 'virtualSize' for this example.
    uint64_t startingAddress = virtualSize;

    void *ret = mmap(
        (void *)startingAddress, virtualSize,
        PROT_READ | PROT_WRITE,
        MAP_PRIVATE | MAP_FIXED | MAP_ANONYMOUS | MAP_NORESERVE,
        -1,
        0
    );
    if (ret == MAP_FAILED) {
        perror("mmap");
        return 0ULL;
    }
    return startingAddress;
}

// Just an experiment, have fun !