Checking list_empty without a lock

user_4457419 0
Viewed 280

I'm wondering about the thread safety of the linux kernel linked list. Suppose one thread adds items to a list while another thread reads the list. Of course while modifying the list I need to take a lock/mutex. But does checking if the list is empty using list_empty already require a lock?

Looking at the source of list_empty:

static inline int list_empty(const struct list_head *head)
{
    return READ_ONCE(head->next) == head;
}

we see that it uses READ_ONCE. AFAIK this prevents certain compiler optimizations and is also atomic for properly aligned/sized variables. Because there is no memory barrier I get no ordering with other memory accesses whatsoever, but the list will eventually become not empty after some other thread added an item. So I believe a lock is not strictly necessary for list_empty.

I'm asking because I want to use list_empty as a condition for wait_event_interruptible.

linux-kernel multithreading c
1 Answers

Let's use some pseudo assembler.

In order to read head->next it needs to read head.

mov ax, head                 (1)

Then it takes the offset of next and gets next:

mov cx, [ax+offset(next)]    (2)

Now it compares it to head:

cmp ax,cx                    (3)

If we assume that head does not change and is not null (e.g. a global variable), then step (2) is atomic and no lock is required. However, if head can change, then step 2 may fetch wrong data as ax may no longer be valid, for example because the scheduler suspended the task after step 1, and the three steps must be performed in a locked state.

user_31003120
Related