vsync / map / listset_opt.h

This implementation is an optimized verison of listset_fine.

Groups: Linearizable, SMR-required

It uses fine grained locking (one lock per node) to serialize all operations. This implementation allows for list traversal without acquiring locks. Locks are only acquired to validate the traversal results and performing the operations.

Example:

#include <vsync/map/listset_opt.h>
#include <vsync/smr/gdump.h>
#include <pthread.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define N 11

typedef struct data_s {
    vlistset_node_t lst_node; /* embed list set node */
    vlistset_key_t key;
    smr_node_t smr_node; /* embed smr node */
} data_t;

#define MIN_KEY 0
#define MAX_KEY 10

gdump_t g_gdump;

vlistset_t g_lst;

pthread_rwlock_t g_lock;

static inline void
thread_rw_read_acq(void *arg)
{
    pthread_rwlock_t *lock = (pthread_rwlock_t *)arg;
    int ret                = pthread_rwlock_rdlock(lock);
    assert(ret == 0);
}

static inline void
thread_rw_read_rel(void *arg)
{
    pthread_rwlock_t *lock = (pthread_rwlock_t *)arg;
    int ret                = pthread_rwlock_unlock(lock);
    assert(ret == 0);
}
static inline void
thread_rw_write_acq(void *arg)
{
    pthread_rwlock_t *lock = (pthread_rwlock_t *)arg;
    int ret                = pthread_rwlock_wrlock(lock);
    assert(ret == 0);
}
static inline void
thread_rw_write_rel(void *arg)
{
    pthread_rwlock_t *lock = (pthread_rwlock_t *)arg;
    int ret                = pthread_rwlock_unlock(lock);
    assert(ret == 0);
}

smr_rwlock_lib_t g_rwlock_lib = {thread_rw_read_acq, thread_rw_read_rel,
                                 thread_rw_write_acq, thread_rw_write_rel,
                                 &g_lock};

void
free_cb(smr_node_t *snode, void *args)
{
    data_t *data = V_CONTAINER_OF(snode, data_t, smr_node);
    free(data);
    (void)args;
}

int
cmp_cb(vlistset_node_t *node, vlistset_key_t key)
{
    data_t *data = (data_t *)node;
    if (data->key == key) {
        return 0;
    } else if (data->key < key) {
        return -1;
    } else {
        return 1;
    }
}

void
retire_cb(vlistset_node_t *node, void *args)
{
    data_t *data = (data_t *)node;
    gdump_retire(&g_gdump, &data->smr_node, free_cb, NULL);
    (void)args;
}

int
yield_cb(void *args)
{
    (void)args;
    return sched_yield();
}

vatomic8_t g_stop = VATOMIC_INIT(0);

void
reclaim(void)
{
    while (vatomic8_read(&g_stop) == 0) {
        vsize_t count = gdump_recycle(&g_gdump, yield_cb, NULL, 1);
        if (count > 0) {
            printf("%zu node(s) were reclaimed\n", count);
        }
    }
}

void
reader(gdump_thread_t *thread)
{
    data_t *data = NULL;
    gdump_register(&g_gdump, thread);
    for (vlistset_key_t key = MIN_KEY; key <= MAX_KEY; key++) {
        gdump_enter(&g_gdump, thread);
        data = (data_t *)vlistset_get(&g_lst, key);
        if (data) {
            assert(key == data->key);
            printf("Reader found key %lu\n", data->key);
        }
        gdump_exit(&g_gdump, thread);
    }
    gdump_deregister(&g_gdump, thread);
}

void
writer(gdump_thread_t *thread)
{
    data_t *data    = NULL;
    vbool_t success = false;

    gdump_register(&g_gdump, thread);
    for (vlistset_key_t key = MIN_KEY; key <= MAX_KEY; key++) {
        gdump_enter(&g_gdump, thread);
        success = vlistset_remove(&g_lst, key);
        gdump_exit(&g_gdump, thread);
        if (success) {
            printf("Removed node with key %lu\n", key);
        } else {
            data      = malloc(sizeof(data_t));
            data->key = key;
            gdump_enter(&g_gdump, thread);
            success = vlistset_add(&g_lst, key, &data->lst_node);
            gdump_exit(&g_gdump, thread);
            if (success) {
                printf("Added node with key %lu\n", key);
            } else {
                free(data);
            }
        }
    }
    gdump_deregister(&g_gdump, thread);

    // writer is done, it can trigger recycle if it wishes
    vsize_t count = gdump_recycle(&g_gdump, yield_cb, NULL, 1);
    printf("writer reclaimed %zu nodes\n", count);
}

void *
run(void *args)
{
    gdump_thread_t thread;
    vsize_t tid = (vsize_t)args;

    if (tid == 0) {
        reclaim();
    } else if (tid % 2 == 0) {
        writer(&thread);
    } else {
        reader(&thread);
    }

    return NULL;
}

int
main(void)
{
    pthread_t threads[N];

    int ret = pthread_rwlock_init(&g_lock, NULL);
    assert(ret == 0);

    gdump_init(&g_gdump, g_rwlock_lib);
    vlistset_init(&g_lst, retire_cb, NULL, cmp_cb);

    for (vsize_t i = 0; i < N; i++) {
        pthread_create(&threads[i], NULL, run, (void *)i);
    }

    for (vsize_t i = 1; i < N; i++) {
        pthread_join(threads[i], NULL);
    }
    vatomic8_write(&g_stop, 1);
    pthread_join(threads[0], NULL);

    vlistset_destroy(&g_lst);
    gdump_destroy(&g_gdump);

    ret = pthread_rwlock_destroy(&g_lock);
    assert(ret == 0);
    return 0;
}

References:

Maurice Herlihy, Nir Shavit - The Art of Multiprocessor Programming 9.6

---

Functions

Function	Description
vlistset_init	Initializes the given vlistset_t object lst.
vlistset_destroy	Destroys all the remaining nodes in the listset.
vlistset_add	Inserts the given node into the listset.
vlistset_remove	Removes the node associated with the given key from the listset.
vlistset_get	Looks for the listset node associated with the given key.

Function vlistset_init

static void vlistset_init(vlistset_t *lst, vlistset_handle_node_t retire_fun, void *retire_fun_arg, vlistset_cmp_key_t cmp_fun)

Initializes the given vlistset_t object lst.

Note: must be called before threads access the listset.

Parameters:

• lst: address of vlistset_t object.
• retire_fun: address of the function used to retire removed nodes.
• retire_fun_arg: optional second parameter to pass to retire_fun.
• cmp_fun: address of the function used for comparing a key in vlistset_node_t object with a given key.

Function vlistset_destroy

static void vlistset_destroy(vlistset_t *lst)

Destroys all the remaining nodes in the listset.

Note: call only after thread join, or after all threads finished accessing the given vlistset_t object.

Parameters:

• lst: address of vlistset_t object.

Function vlistset_add

static vbool_t vlistset_add(vlistset_t *lst, vlistset_key_t key, vlistset_node_t *node)

Inserts the given node into the listset.

The node is only inserted if there is no other node associated with the given key exists in the listset.

Note: if the operation fails, users can safely free or reuse the given node. Precondition: the key must be set in the given node before calling add.

Parameters:

• lst: address of vlistset_t object.
• key: the key value that is used to identify the node.
• node: address of vlistset_node_t object.

Returns: true operation succeeded, the given node has been added.

Returns: false operation failed, the given node has not been added, because there exists another node associated with the given key.

Note: must be called inside SMR critical section.

Function vlistset_remove

static vbool_t vlistset_remove(vlistset_t *lst, vlistset_key_t key)

Removes the node associated with the given key from the listset.

Note: the registered retire callback will be called on the removed node.

Parameters:

• lst: address of vlistset_t object.
• key: the key identifying the node to remove.

Returns: true the node associated with the given key was removed successfully.

Returns: false could not find a node holding the given key to remove.

Note: must be called inside SMR critical section.

Function vlistset_get

static vlistset_node_t* vlistset_get(vlistset_t *lst, vlistset_key_t key)

Looks for the listset node associated with the given key.

Parameters:

• lst: address of vlistset_t object.
• key: key value.

Returns: vlistset_node_t* address of the listset node associated with the given key.

Returns: NULL if no node associated with the given key was found.

Note: must be called inside SMR critical section.

---