THMAP(9)

🎀 NAME 🎀

okay so this is thmap — concurrent trie-hash map — and this whole page is THMAP(9) from the Kernel Developer’s Manual 💖 bestie, it’s giving “serious kernel data structure but make it readable.”

🌸 SYNOPSIS 🌸

#include <thmap.h>

thmap_t *
thmap_create(uintptr_t baseptr, const thmap_ops_t *ops, unsigned flags);

void
thmap_destroy(thmap_t *thmap);

void *
thmap_get(thmap_t *thmap, const void *key, size_t len);

void *
thmap_put(thmap_t *thmap, const void *key, size_t len, void *val);

void *
thmap_del(thmap_t *thmap, const void *key, size_t len);

void *
thmap_stage_gc(thmap_t *thmap);

void
thmap_gc(thmap_t *thmap, void *ref);

void
thmap_setroot(thmap_t *thmap, uintptr_t root_offset);

uintptr_t
thmap_getroot(const thmap_t *thmap);

💅 DESCRIPTION 💅

So thmap is a concurrent trie-hash map — a general purpose associative array that combines the elements of hashing and radix trie. It’s lowkey iconic, and here are the highlights:

• Very competitive performance, with logarithmic time complexity on average.
• Lookups are lock-free and inserts/deletes are using fine-grained locking.
• Incremental growth of the data structure — so no large resizing/rehashing, periodt.
• Optional support for use with shared memory, e.g. a memory-mapped file.

🚨 Delete operations (the key/data destruction) must be synchronized with the readers using some reclamation mechanism. Like, do not just yeet the memory and hope for the best, bestie. This is a real concurrency caveat.

🦋 FUNCTIONS 🦋

💖 thmap_create(baseptr, ops, flags)

Construct a new trie-hash map. The optional ops parameter can be used to set the custom allocate/free operations (see the description of thmap_ops_t below). In such case, the baseptr is the base (start) address of the address space mapping — it must be word-aligned. If ops is set to NULL, then malloc(3) and free(3) will be used as the default operations and baseptr should be set to zero.

Currently, the supported flags are:

• THMAP_NOCOPY — the keys on insert will not be copied and the given pointers to them will be expected to be valid and the values constant until the key is deleted; by default, the put operation will make a copy of the key.
• THMAP_SETROOT — indicate that the root of the map will be manually set using the thmap_setroot() routine; by default, the map is initialized and the root node is set on thmap_create().

🧚 thmap_destroy(thmap)

Destroy the map, freeing the memory it uses. Cleanup era 💅

⭐ thmap_get(thmap, key, len)

Lookup the key (of a given length) and return the value associated with it. Return NULL if the key is not found — and yes, see the CAVEATS section, because NULL is doing double duty there.

🔥 thmap_put(thmap, key, len, val)

Insert the key with an arbitrary value. If the key is already present, return the already existing associated value without changing it. Otherwise, on a successful insert, return the given value. Just compare the result against val to test whether the insert was successful. That’s the vibe check right there.

🌈 thmap_del(thmap, key, len)

Remove the given key. If the key was present, return the associated value; otherwise return NULL.

The memory associated with the entry is not released immediately, because in the concurrent environment (e.g., multi-threaded application) the caller may need to ensure it is safe to do so. It is managed using the thmap_stage_gc() and thmap_gc() routines.

🎀 thmap_stage_gc(thmap)

Stage the currently pending entries — the memory not yet released after the deletion — for reclamation (G/C). This operation should be called before the synchronization barrier.

Returns a reference which must be passed to thmap_gc(). Not calling the G/C function for the returned reference would result in a memory leak. 🫶 so please actually call it.

🦋 thmap_gc(thmap, ref)

Reclaim (G/C) the staged entries, i.e. release any memory associated with the deleted keys. The ref must be the value returned by the call to thmap_stage_gc().

This function must be called after the synchronization barrier which guarantees that there are no active readers referencing the staged entries.

---

If the map is created using the THMAP_SETROOT flag, then the following functions are applicable:

👑 thmap_setroot(thmap, root_offset)

Set the root node. The address must be relative to the base address, as if allocated by the thmap_ops_t::alloc() routine. Return 0 on success and -1 on failure (if already set).

💜 thmap_getroot(thmap)

Get the root node address. The returned address will be relative to the base address.

🌸 Members of thmap_ops_t are

uintptr_t (*alloc)(size_t len);
void      (*free)(uintptr_t addr, size_t len);

🍓 EXAMPLES 🍓

Simple case backed by malloc(3), which could be used in a multi-threaded environment:

thmap_t *kvmap;
struct obj *obj;

kvmap = thmap_create(0, NULL);
assert(kvmap != NULL);
...
obj = obj_create();
thmap_put(kvmap, "test", sizeof("test") - 1, obj);
...
obj = thmap_get(kvmap, "test", sizeof("test") - 1);
...
thmap_destroy(kvmap);

👑 AUTHORS 👑

Mindaugas Rasiukevicius <rmind@noxt.eu>

💀 CAVEATS 💀

The implementation uses pointer tagging and atomic operations. This requires the base address and the allocations to provide at least word alignment.

While the NULL values may be inserted, thmap_get() and thmap_del() cannot indicate whether the key was not found or a key with a NULL value was found. If the caller needs to indicate an “empty” value, it can use a special pointer value, such as (void *)(uintptr_t)0x1. Not me warning you twice, but like… be aware 💀

---

okay that’s the whole page, bestie — source/version: Debian, date: December 11, 2018, manual: THMAP(9). slay and stay aligned 🫶✨💖