Queues in the Linux Kernel

Question

I've been searching for information for a common kernel implementation of queues, that is, first-in-first-out data structures. I thought there may be one since it's likely something that's common to use, and there's a standard for linked lists (in the form of the list_head structure). Is there some standard queue implementation I can't find, or is it perhaps common practice to just use linked lists as queues and hope for the best?

Solution 1

You're right, the Linux kernel typically uses linked lists to implement queues. This makes sense, because linked lists offer the required behavior. See this example from kernel/workqueue.c:

  INIT_LIST_HEAD(&wq->list);
  // ...
   case CPU_UP_CANCELED:
            list_for_each_entry(wq, &workqueues, list) {
                    if (!per_cpu_ptr(wq->cpu_wq, hotcpu)->thread)

Solution 2

Are you looking for include/linux/kfifo.h? From the heading:

A simple kernel FIFO implementation.

It's rather new anyway, so it's not hard to find direct usages of linked lists. Also, they have a quite different implementation (FIFOs are implemented as circular buffers), so they have different applications.

Note also they are designed with multithreaded usage in mind (think to producer/consumer queues), but you can use them without locking with __kfifo_put/__kfifo_get.

Btw: I remember I learned about them on lwn.net - bookmark this: lwn.net/Kernel/Index, and read the entry about kfifo :-).

From your ex-kernel developer, Blaisorblade

Solution 3

You seem to confusing an abstraction (a fifo queue) with an implementation (a linked list). They are not mutually exclusive - in fact queues are most commonly implemented as linked lists - there is no "hoping for the best".