If we use fine grain locking, why do we still need the list wide lock (list->lock)?
adbenson
I believe I see a bug in the delete implementation.
Consider two delete calls, the first of which is trying to delete the second node, and it doesn't matter for the second.
The first grabs pointers to prev and cur, grabs the prev lock, then unlocks the list. By doing so, the second is then able to grab pointers to the same prev and cur, and waits for the prev lock.
The first then deletes cur. However, the second's cur pointer is now invalid, since it was already created.
I think a fix would be for delete to create the cur pointer after acquiring the prev lock.
kayvonf
@adbenson. Great catch! You are correct. NOTE TO ALL STUDENTS: The slide you see above has been updated to include @adbenson's fix.
At the top of insert() and delete(), the code now sets cur = prev->next AFTER taking the lock on prev.
If we use fine grain locking, why do we still need the list wide lock (list->lock)?
I believe I see a bug in the delete implementation.
Consider two delete calls, the first of which is trying to delete the second node, and it doesn't matter for the second.
The first grabs pointers to prev and cur, grabs the prev lock, then unlocks the list. By doing so, the second is then able to grab pointers to the same prev and cur, and waits for the prev lock. The first then deletes cur. However, the second's cur pointer is now invalid, since it was already created.
I think a fix would be for delete to create the cur pointer after acquiring the prev lock.
@adbenson. Great catch! You are correct. NOTE TO ALL STUDENTS: The slide you see above has been updated to include @adbenson's fix.
At the top of
insert()
anddelete()
, the code now setscur = prev->next
AFTER taking the lock onprev
.