andersch.dev

dandersch contact [at} andersch {dot) dev
<2024-01-08 Mon>
[ datastructure ]

Linked List

A linked list is a data structure where each node contains the relevant data and a pointer to the next node.

Generic Linked Lists in C

Two approaches:

  • Macro-based with hardcoded member names (next, prev)
  • Intrusive linked list node type as struct member (Linux kernel approach)

Macro-based Linked List API

For doubly-linked lists, hardcode the structure member names (i.e the nodes to link) to "prev" and "next". 

typedef struct item_t item_t;
struct item_t {
    int foo;
    float bar;
    /* ... */
    item_t* prev;
    item_t* next;
};

The macro-based API then can look like this: 

#define DL_FOREACH(head,el) \
    for ((el) = (head); el; (el) = (el)->next)

#define DL_APPEND(head,add)          \
do {                                 \
  if (head) {                        \
      (add)->prev = (head)->prev;    \
      (head)->prev->next = (add);    \
      (head)->prev = (add);          \
      (add)->next = NULL;            \
  } else {                           \
      (head)=(add);                  \
      (head)->prev = (head);         \
      (head)->next = NULL;           \
  }                                  \
} while (0)

#define DL_DELETE(head,del)                \
do {                                       \
  assert((head) != NULL);                  \
  assert((del)->prev != NULL);             \
  if ((del)->prev == (del)) {              \
      (head)=NULL;                         \
  } else if ((del) == (head)) {            \
      assert((del)->next != NULL);         \
      (del)->next->prev = (del)->prev;     \
      (head) = (del)->next;                \
  } else {                                 \
      (del)->prev->next = (del)->next;     \
      if ((del)->next) {                   \
          (del)->next->prev = (del)->prev; \
      } else {                             \
          (head)->prev = (del)->prev;      \
      }                                    \
  }                                        \
} while (0)

Intrusive linked list - list_head

The Linux kernel approach to having linked lists is a type of intrusive linked list where the links are embedded in the struct that is being linked: 

struct list_head {
    struct list_head *next, *prev;
};

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name)      struct list_head name = LIST_HEAD_INIT(name)
void INIT_LIST_HEAD(struct list_head *list) { list->next = list; list->prev = list; }

/* api */
void list_add(struct list_head *new, struct list_head *head);
void list_add_tail(struct list_head *new, struct list_head *head);
void list_del(struct list_head *entry);
int  list_is_head(const struct list_head *list, const struct list_head *head);
int  list_empty(const struct list_head *head);

#define list_entry(ptr, type, member)          container_of(ptr, type, member)                        // get struct of the entry
#define list_first_entry(ptr, type, member)    list_entry((ptr)->next, type, member)                  // get first element from list
#define list_next_entry(pos, member)           list_entry((pos)->member.next, typeof(*(pos)), member) // get next element in list
#define list_entry_is_head(pos, head, member)  (&pos->member == (head))                               // test if entry is head of list
#define list_for_each_entry(pos, head, member)                    \   // iterate over list of given type
        for (pos = list_first_entry(head, typeof(*pos), member);  \
             !list_entry_is_head(pos, head, member);              \
             pos = list_next_entry(pos, member))
#define list_for_each_entry_safe(pos, n, head, member)           \
        for (pos = list_first_entry(head, typeof(*pos), member), \
             n = list_next_entry(pos, member);                   \
             !list_entry_is_head(pos, head, member);             \
             pos = n, n = list_next_entry(n, member))


/* usage code */
struct mdev_state {
    struct vfio_device vdev;
    /* ... */
    struct list_head dmabufs; /* intrusive linked list */
    u32 active_id;
    u32 next_id;
};

/* init list */
static int mbochs_init_dev(struct vfio_device *vdev)
{
    /* ... */
    INIT_LIST_HEAD(&mdev_state->dmabufs);
    /* ... */
}

/* add to list */
static struct mbochs_dmabuf *mbochs_dmabuf_alloc(struct mdev_state *mdev_state, struct mbochs_mode *mode)
{
    dmabuf = kzalloc(sizeof(struct mbochs_dmabuf), GFP_KERNEL);
    dmabuf->mode = *mode;
    dmabuf->id = mdev_state->next_id++;
    dmabuf->pagecount = DIV_ROUND_UP(mode->size, PAGE_SIZE);
    dmabuf->pages = kcalloc(dmabuf->pagecount, sizeof(struct page *), GFP_KERNEL);
    dmabuf->mdev_state = mdev_state;
    list_add(&dmabuf->next, &mdev_state->dmabufs);
    return dmabuf;
}

/* iterate through list */
static struct mbochs_dmabuf* mbochs_dmabuf_find_by_mode(struct mdev_state *mdev_state, struct mbochs_mode *mode)
{
    struct mbochs_dmabuf *dmabuf;

    list_for_each_entry(dmabuf, &mdev_state->dmabufs, next) {
      if (mbochs_modes_equal(&dmabuf->mode, mode)) { return dmabuf; }
    }

    return NULL;
}

/* use of container_of, safely iterate and delete */
static void mbochs_close_device(struct vfio_device *vdev)
{
    struct mdev_state *mdev_state = container_of(vdev, struct mdev_state, vdev);
    struct mbochs_dmabuf *dmabuf, *tmp;

    list_for_each_entry_safe(dmabuf, tmp, &mdev_state->dmabufs, next) {
        list_del(&dmabuf->next);
        if (dmabuf->buf) {
            /* free in mbochs_release_dmabuf() */
            dmabuf->unlinked = true;
        } else {
            kfree(dmabuf);
        }
    }
}

Resources