How can I use spinlocks on list entries inside the linux kernel?

Question

Hi, I'm developing a patch for the linux kernel. I have to use several lists and I have to protect'em against concurrent modification on a multicore machine. I'm trying to use spinlocks for this goal, but there's something I can't understand. I have to lock the entries of a list (I'm using linux default implementation of linked lists) and it can happen that a process invokes a syscall to remove one element of the list while the same element which is locked because some modification is actually being made on it. If I insert a spinlock inside the list entry, what happens if a process manage to remove it while someone is spinlocking on it?? Should I lock the entire list? I'm looking for a piece of code that can explain how to do handle this situation.

For example, this code shouldn't work (see comment on the last line of code):

   struct lista{
    int c;
    spinlock_t lock;
    struct list_head;
}

spinlock_t list_lock;
struct lista lista;


//INSERT
struct lista* cursor;
struct lista* new = (struct lista*) kmalloc(sizeof(struct lista),GFP_KERNEL);

/*do something*/
spin_lock(&list_lock);     //Lock on the whole list
list_for_each_entry(cursor,&lista.list,list){
    if (cursor->c == something ){
        ...
        spin_unlock(&list_lock)  //unlock
        spin_lock(&cursor->lock) // Lock on list entry
        list_add(&new->list, &lista.list);
        spin_unlock(&cursor->lock)  // unlock of the list entry
        ...
    }
}


//REMOVAL
struct lista* cursor;

spin_lock(&list_lock);  
list_for_each_entry(cursor,&lista.list,list){
    if (cursor->c == something ){
        ...
        spin_unlock(&list_lock)  //unlock
        spin_lock(&cursor->lock) // Lock on list entry
        list_del(&cursor.list,&lista.list);
        spin_unlock(&cursor->lock)  // unlock of the list entry
        kfree(cursor);  //WHEN THE ENTRY IS FREED SOMEONE COULD HAVE TAKEN THE LOCK SINCE IT IS UNLOCKED
        ...
    }
}

Can you help me??

Answer 1

Don't release list_lock until you're done removing the item.

You might end up with the slightly awkward procedure of:

1. Acquire list lock (this will block other incoming threads)
2. Acquire item lock, release item lock (this insures that all earlier threads are done)
3. Remove item
4. Release list lock.

Variation: use a reader-writer lock for the list lock.

Threads looking to modify list items take the reader lock; this allows multiple threads to operate on the list in parallel.

Threads looking to remove list items take the writer lock; this waits for all readers to exit and blocks them until you release it. In this case you still have to hold the list lock until you're done removing the item,

In this way you can avoid step 2 above. This might seem conceptually clearer, as you don't need to explain the pointless-looking lock/release.

Answer 2

You almost certainly shouldn't be using spinlocks at all, unless there's concurrent access from hard IRQ context. Use mutexes instead.

The easiest option for your list is just to lock the entire list while you operate on it. Don't worry about per-item locks unless and until you find that there's sufficient contention on the list lock that you need it (and in that case, you probably want to look at using RCU instead, anyway).

Answer 3

Your list head doesn't need to be a struct lista, it should just be a struct list_head. Notice that you keep using &lista.list, that should just be a list_head called "list" or something. See for example the code in drivers/pci/msi.c, notice that dev->msi_list is just a list_head, not a struct msi_desc.

You can't safely drop the list lock and then grab the cursor lock. It's possible that after you dropped the list lock but before you get the cursor lock someone else came in and free'd your cursor. You can juggle the locks, but that is very easy to get wrong.

You almost definitely just want one lock, for the whole list, and no per-item locks. And the list lock should be a mutex unless you need to manipulate the list from interrupt context.