Is this really lock free? It seems to have spin locks.

[battaglia01]

For instance:

static inline void _sl_read_lock_an(skiplist_node* node) {
    for(;;) {
        // Wait for active writer to release the lock
        uint32_t accessing_next = 0;
        ATM_LOAD(node->accessing_next, accessing_next);
        while (accessing_next & 0xfff00000) {
            YIELD();
            ATM_LOAD(node->accessing_next, accessing_next);
        }

        ATM_FETCH_ADD(node->accessing_next, 0x1);
        ATM_LOAD(node->accessing_next, accessing_next);
        if ((accessing_next & 0xfff00000) == 0) {
            return;
        }

        ATM_FETCH_SUB(node->accessing_next, 0x1);
    }
}

This seems to be the cause of the problem here in #1 (deadlock). Do you just mean std::mutex free?

[greensky00]

The critical section of that spinlock is tiny: accessing individual reference counter, not the entire operation. It was used for protecting reference counter against memory deallocation, the same reason why shared_ptr itself is not thread-safe while shared_ptr's reference counter is atomic.

There were a few options to address this problem at that time:

1. atomic_shared_ptr: it was not generally available, and also too expensive just for reference counter.
2. RCU style lazy deallocation: it was one of TO-DOs, didn't have a chance to implement it.

And the link you referred to is not a deadlock. It is a misusage not following the description here, and also can be avoided by using sl_set_gc.

[battaglia01]

Thanks for clarifying, hadn't seen sl_set_gc. This seems to be different from other lock free skip list implementations I've seen before. Is there any paper on it?