A useless data structure?

atomic_buffer_store.c

/**
 * atomic_array.c
 *
 * Not a general purpose container, this just serves as a circular buffer
 * for void poiners with O(1) lookup but with better constants
 * than a hash-table and thread safe for insertion and deletion.
 *
 * This can be used as a data structure to share between threads, as a kind
 * of shared pointer. Both threads keep a key into the table, they can retrieve,
 * insert and delete a void pointer atomically.
 *
 * Note that this is not free of very dangerous pitfalls. For example, there
 * can be no more than MAX_ENTRIES in the array (it is static).
 *
 * Secondly and more importantly, there is no guarantee that the object you
 * retrieve is the object you put in. This might sound scarier than it is.
 * For example: thread A and thread B share a key K. They are happily using
 * this data structure until thread A decides to delete the key. In the best
 * case, no thread tries to add a key to that position until thread B tries
 * to retrieve from that key and notices that the object is gone, at which
 * point it will hopefully get rid of the local state associated with the
 * object.
 *
 * However, it is possible that before thread B gets to the object, it is
 * replaced by another. in this case B will merrily use it being none the wiser.
 * Kind of like the well-known ABA problem except it can also be ABC here,
 * the code has no way if identifying if the object is the right one.
 *
 * So, the assumption is that this does not happen, because there are far more
 * entries than there are objects. Or the objects have pretty sequential lifetimes
 * or... yea I just noticed that this data structure has only a very narrow purpuse,
 * and that's in my specific case where sometimes epoll wakes up and gives a pointer
 * to an object that's already been removed from the epoll set by another thread AND
 * deleted.
 *
 * I can't just free the pointer in the epoll thread because 99% of the time, after
 * removing the fd from the set, the epoll doesn't wake up for that fd anymore. This
 * would leave unfreed memory. Secondly, I can't not remove the fd from the epoll
 * set in the main thread because... why?
 */

#define WM_INVALID_KEY (MAX_ENTRIES + 1)

#define MEMORY_MODEL __ATOMIC_SEQ_CST

/**
 * the atomic operations rely on this being a power of two, don't change that property
 *
 * http://stackoverflow.com/questions/4161494/atomic-counter-in-gcc
 */
#define MAX_ENTRIES 1024U

struct atomicArray {
	void *array[MAX_ENTRIES];

	unsigned int counter;
};

typedef struct atomicArray *atarray_t;
typedef unsigned int atkey_t;

atkey_t atomicInsert(atarray_t self, void *value) {
	unsigned int counter;
	void *expected;

	int tries = 0;


	/**
	 * find the next free spot
	 *
	 * __atomic_compare_exchange_n overwrites expected in case of failure, which
	 * is different from __sync_bool_compare_and_swap, the old and deprecated
	 * version
	 */
	do {
		if (++tries == MAX_ENTRIES) {
			TRACE("buffer is full, aborting\n");

			return WM_INVALID_KEY;
		}

		expected = NULL;

		/**
		 * atomic add with wraparound, if MAX_ENTRIES was 4
		 * the counter would go like: 0, 1, 2, 3, 0
		 */
		counter = __atomic_fetch_add(&self->count, 1, MEMORY_MODEL) & (MAX_ENTRIES - 1);
	} while (!__atomic_compare_exchange_n(&self->array[counter], &expected, value, false, MEMORY_MODEL, MEMORY_MODEL));

	/**
	 * store atomically into the new spot
	 */
	__atomic_store_n(&self->array[counter], value, MEMORY_MODEL);

	return counter;
}

/**
 * this is not refcounted, if you manage to extract a pointer from
 * this queue, that means it's valid. Though if you don't use a lock
 * you don't know if it's still valid when you assign it. Such is
 * life with multiple threads.
 */
void *atomicPointerGet(atarray_t self, atkey_t entry) {
	assert(entry >= 0 && entry < MAX_ENTRIES);

	return __atomic_load_n(&self->array[entry], MEMORY_MODEL);
}

/**
 * does not free the pointer, only removes it from the shared list
 */
void atomicPointerRemove(atarray_t self, atkey_t entry) {
	assert(entry >= 0 && entry < MAX_ENTRIES);

	/* delete first, ask questions later */
	__atomic_clear(&self->array[entry], MEMORY_MODEL);
}