A Linux Kernel Queue Container

Your are probably familiar with the linux kernel linked list that can be found in linux/list.h.  While this is a wonderful tool to use in your kernel programming, sometimes you need something a bit different.  One such instance is a queue – a first in, first out collection of objects.  Here I will present a generic Queue container based on the linux kernel linked list.

Before we start, please note that a Fedora Core 12 system was used for all code presented here.

Here is the header file, queue.h

#ifndef QUEUE_H_
#define QUEUE_H_

#include <linux/list.h>
#include <linux/spinlock.h>

typedef struct QueueItem
{
   struct list_head    list;      // Linked List
   void *              item;      // Item of Data
} QueueItem;

typedef struct Queue
{
   struct list_head    list;      // List Head
   spinlock_t          lock;      // Lock
} Queue;

// Prototypes

Queue *  qCreate(void);
void     qDelete(Queue *q);
void     qEnqueue(Queue *q, void *item);
void *   qDequeue(Queue *q);
int      qIsEmpty(Queue *q);
int      qLock(Queue *q);
void     qUnlock(Queue *q);

#endif   // QUEUE_H_

Here are the items of note from this header file:

  • The Queue uses the linux linked list to maintain the container.
  • An item on the Queue is represented as a void pointer.
  • The Queue has locking.

In this example a spinlock is used.  Please use whatever locking mechanism is right for you.  The qLock function has an int return value in case the chosen lock has an error return.

Now we move on to the code source, queue.c

#include <linux/slab.h>
#include "queue.h"

Queue *
qCreate(void)
{
   Queue *    q;

   q = (Queue *) kmalloc(sizeof(Queue), GFP_ATOMIC);
   if (! q)
   {
      printk(KERN_ALERT "qCreate:kmalloc failed\n");
      return q;
   }

   INIT_LIST_HEAD(&(q->list));

   spin_lock_init(&(q->lock));

   return q;
}

// Queue must be empty!
void
qDelete(Queue *q)
{

   kfree((void *) q);

   return;
}

void
qEnqueue(Queue *q, void *item)
{
   QueueItem *   qi;

   qi = (QueueItem *) kmalloc(sizeof(QueueItem), GFP_ATOMIC);
   if (! qi)
   {
      printk(KERN_ALERT "qEnqueue:kmalloc failed\n");
      return;
   }

   qi->item = item;

   qLock(q);
   list_add_tail(&(qi->list), &(q->list));
   qUnlock(q);

   return;
}

void *
qDequeue(Queue *q)
{
   QueueItem *   qi;
   void *        item;

   if (qIsEmpty(q))
   {
      return NULL;
   }

   qLock(q);

   qi = list_first_entry(&(q->list), QueueItem, list);

   item = qi->item;

   list_del(&(qi->list));

   kfree((void *) qi);

   qUnlock(q);

   return item;
}

int
qIsEmpty(Queue *q)
{
   int   ret;

   qLock(q);
   ret = list_empty(&(q->list));
   qUnlock(q);

   return ret;
}

int
qLock(Queue *q)
{

   spin_lock(&(q->lock));

   return 0;
}

void
qUnlock(Queue *q)
{

   spin_unlock(&(q->lock));

   return;
}

Here are the items of note from this source file:

  • qCreate and qDelete dynamically allocate and free memory for a Queue.  The Queue must be empty before calling qDelete or memory will be leaked.
  • qEnqueue dynamically allocates memory for each item in the Queue container.  qDequeue will free this memory when an item is dequeued.
  • All Queue locking is performed by the Queue functions.

Be careful what you queue.  For example, if you call a function and it queues an item on its stack and then returns, this will have catastrophic results.  The item to be queued must be persistent.

Now we present a bit of source code that shows usage of the Queue container.

void
queueTest()
{
   Queue *   q;
   void *    item;

   q = qCreate();

   item = kmalloc(20, GFP_ATOMIC);
   qEnqueue(q, item);

   item = kmalloc(20, GFP_ATOMIC);
   qEnqueue(q, item);

   item = kmalloc(20, GFP_ATOMIC);
   qEnqueue(q, item);

   while(1)
   {
      if (qIsEmpty(q))
         break;

      item = qDequeue(q);
      kfree(item);
   }

   qDelete(q);

   return;
}

So, there it is.  Hope you found this useful.

-OGB

One Response

  1. Strongly suggest adding a “google+” button for the blog!