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

Question

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.