• Contact: tech-kern, board, core

This project proposal is a subtask of smp networking.

The goal of this project is to implement lockless and atomic FIFO/LIFO queues in the kernel. The routines to be implemented allow for commonly typed items to be locklessly inserted at either the head or tail of a queue for either last-in, first-out (LIFO) or first-in, first-out (FIFO) behavior, respectively. However, a queue is not instrinsicly LIFO or FIFO. Its behavior is determined solely by which method each item was pushed onto the queue.

It is only possible for an item to removed from the head of queue. This removal is also performed in a lockless manner.

All items in the queue must share a atomic_queue_link_t member at the same offset from the beginning of item. This offset is passed to atomic_qinit.

The proposed interface looks like this:

• void atomic_qinit(atomic_queue_t *q, size_t offset);

  Initializes the atomic_queue_t queue at q. offset is the offset to the atomic_queue_link_t inside the data structure where the pointer to the next item in this queue will be placed. It should be obtained using offsetof.

• void *atomic_qpeek(atomic_queue_t *q);

  Returns a pointer to the item at the head of the supplied queue q. If there was no item because the queue was empty, NULL is returned. No item is removed from the queue. Given this is an unlocked operation, it should only be used as a hint as whether the queue is empty or not.

• void *atomic_qpop(atomic_queue_t *q);

  Removes the item (if present) at the head of the supplied queue q and returns a pointer to it. If there was no item to remove because the queue was empty, NULL is returned. Because this routine uses atomic Compare-And-Store operations, the returned item should stay accessible for some indeterminate time so that other interrupted or concurrent callers to this function with this q can continue to deference it without trapping.

• void atomic_qpush_fifo(atomic_queue_t *q, void *item);

  Places item at the tail of the atomic_queue_t queue at q.

• void atomic_qpush_lifo(atomic_queue_t *q, void *item);

  Places item at the head of the atomic_queue_t queue at q.