[Bug Report] `skiplist_release()` leaks the header node and the list struct (frees only the data nodes)

[OPTIONPOOL]

Found while integrating omx-engine into an open matching-engine benchmark, the Matching Engine Performance Challenge — it cross-checks engines against the byte-identical consensus of other open-source engines. The leak doesn't affect matching output (the engine is clean on the workload), so it surfaces under AddressSanitizer rather than as a wrong result: it's a latent resource leak in the general-purpose skiplist utility the matcher builds on.

Pinned at current master (bfc0139092957d89191083f7dccab74850bdbfc2); reproduced with gcc 14.2 under -fsanitize=address.

skiplist_create() allocates two things up front — the skiplist_t control struct and a sentinel header node — and returns the struct to the caller. skiplist_release(), the matching destructor, walks the list and frees every data node, but it never frees the header node or the skiplist_t itself. Each call therefore leaks the header node plus the list struct — 184 bytes per release on this build (a 48-byte skiplist_t + a 136-byte header node) — even though the caller has handed ownership back to the destructor and holds no other reference.

Repro. The two leaked blocks only become unreachable once the caller drops its handle, so a short create/release loop makes the accumulation visible under AddressSanitizer:

/* gcc -g -fsanitize=address -I src/engine/utils repro.c \
 *     src/engine/utils/ut_skiplist.c -o repro && ./repro */
#include <stdlib.h>
#include <string.h>
#include "ut_skiplist.h"

static int cmp(const void *a, const void *b) {
    long x = (long)a, y = (long)b;
    return x == y ? 0 : (x > y ? 1 : -1);
}

static void cycle(void) {                  /* one create -> insert -> release */
    skiplist_type t;
    memset(&t, 0, sizeof t);
    t.compare = cmp;                       /* no .free: values not owned here */
    skiplist_t *sl = skiplist_create(&t);  /* mallocs sl + sl->header        */
    for (long i = 1; i <= 5; i++)
        skiplist_insert(sl, (void *)i);
    skiplist_release(sl);                  /* the destructor                 */
}

int main(void) {
    for (int n = 0; n < 100; n++) cycle();
    return 0;
}

Actual (AddressSanitizer) — 184 bytes leaked for every release:

Direct leak of 4752 byte(s) in 99 object(s) allocated from:
    #1 skiplist_create        ut_skiplist.c:35
Indirect leak of 13464 byte(s) in 99 object(s) allocated from:
    #1 skiplist_create_node   ut_skiplist.c:17
    #2 skiplist_create        ut_skiplist.c:42
SUMMARY: AddressSanitizer: 18216 byte(s) leaked in 198 allocation(s).

(48 bytes × 99 structs + 136 bytes × 99 header nodes = 18216; the final cycle's list is still reachable from a stale stack slot, so 99 of the 100 are flagged.) Expected: a create followed by a release leaves nothing unfreed — 0 leaks.

Mechanism / root cause. skiplist_create() allocates the struct and the header node (src/engine/utils/ut_skiplist.c:35, :42, with the node malloc at skiplist_create_node, :17):

skiplist_t *list = malloc(sizeof(skiplist_t));                       // :35  (leaks)
...
list->header = skiplist_create_node(list, SKIPLIST_MAX_LEVEL, NULL); // :42 -> :17 (leaks)

skiplist_release() frees the data nodes and stops there (src/engine/utils/ut_skiplist.c:136-149):

void skiplist_release(skiplist_t *list)
{
    unsigned long len = list->len;
    skiplist_node *curr = list->header->forward[0];
    skiplist_node *next;
    while (len--) {
        next = curr->forward[0];
        if (list->type.free) {
            list->type.free(curr->value);
        }
        free(curr);          // frees each data node ...
        curr = next;
    }
}                            // ... but never frees list->header or list

The loop visits exactly list->len data nodes (header->forward[0] onward) and frees each. The sentinel header (allocated at :42) is never on that chain, and list is the object being released — neither is freed, so both leak on every call. For contrast, skiplist_release_iterator() (:170) correctly frees its own allocation, so the pattern elsewhere in the file is to free what was created.

In the matcher this destructor is reached via dict_user_val_free() at src/engine/matchengine/me_market.c:53 (skiplist_release(key)), invoked when a per-user order-list skiplist is torn down with the users dict — so it's a teardown / dict-eviction leak rather than a per-order hot-path one, but any code that creates and releases skiplists repeatedly accumulates it.

Fix. Free the two allocations skiplist_create() made, after the data-node loop:

         free(curr);
         curr = next;
     }
+    free(list->header);
+    free(list);
 }

I applied exactly this to a local copy and re-ran the loop above under AddressSanitizer: 0 leaks, and the data-node loop is unchanged so existing behaviour is preserved.

This is just a time-stamped snapshot of one specific commit, offered back in case it's useful — thanks very much for putting the engine out there.

Respectfully submitted.