By: Linus Torvalds (torvalds.delete@this.linux-foundation.org), August 26, 2022 11:01 am
Room: Moderated Discussions
Michael S (already5chosen.delete@this.yahoo.com) on August 26, 2022 3:46 am wrote:
>
> I would guess that if we enumerate cases that are
> A. Useful in parctice
> B. Can not be done with 1 cache line
> C. Can be done with unlimited number of distinct lines
> then about half of them can be done with 2 distinct lines.
No, I really do think that 3 distinct lines are pretty much required - since the most obvious case I can think of (doubly linked list) needs it.
And yes, yes, if you look up DCAS and doubly linked lists, you'll find that people talk about just two lines for that operation - but that's not for a doubly linked list that is coherent with a lock, that's for a purely unlocked doubly linked list.
In fact, I suspect that you actually really want four lines, because while three should be sufficient for a doubly linked list (modifying the two entries on both sides, and checking the lock), you probably do want to also hold/modify the cacheline of the entry itself that you are adding or removing.
Yes, you can probably make do without that fourth entry - When adding an entry to the linked list you can pre-fill the prev/next pointers of the new entry before actually doing the operation - and that's the kinds of tricks that you have to do when you only have one entry and you are using 'cmpxchg' or 'll/sc' to do simpler lock-free singly-linked lists.
But I do suspect that four cachelines is noticeably better than three, and two is just simply not sufficient for a lot of simple things.
That said, even just two is probably usable for some things. People who implement locking would use it internally, I bet, and it might be sufficient for a number of "test condition consistent with a lock" situations. I just think that "doubly linked list handling co-existing with a lock" is probably worth considering as a minimally useful thing.
I dunno.
I suspect in the end it's one of those things where it's just not useful enough: locking works, and usually works well enough.
Linus
>
> I would guess that if we enumerate cases that are
> A. Useful in parctice
> B. Can not be done with 1 cache line
> C. Can be done with unlimited number of distinct lines
> then about half of them can be done with 2 distinct lines.
No, I really do think that 3 distinct lines are pretty much required - since the most obvious case I can think of (doubly linked list) needs it.
And yes, yes, if you look up DCAS and doubly linked lists, you'll find that people talk about just two lines for that operation - but that's not for a doubly linked list that is coherent with a lock, that's for a purely unlocked doubly linked list.
In fact, I suspect that you actually really want four lines, because while three should be sufficient for a doubly linked list (modifying the two entries on both sides, and checking the lock), you probably do want to also hold/modify the cacheline of the entry itself that you are adding or removing.
Yes, you can probably make do without that fourth entry - When adding an entry to the linked list you can pre-fill the prev/next pointers of the new entry before actually doing the operation - and that's the kinds of tricks that you have to do when you only have one entry and you are using 'cmpxchg' or 'll/sc' to do simpler lock-free singly-linked lists.
But I do suspect that four cachelines is noticeably better than three, and two is just simply not sufficient for a lot of simple things.
That said, even just two is probably usable for some things. People who implement locking would use it internally, I bet, and it might be sufficient for a number of "test condition consistent with a lock" situations. I just think that "doubly linked list handling co-existing with a lock" is probably worth considering as a minimally useful thing.
I dunno.
I suspect in the end it's one of those things where it's just not useful enough: locking works, and usually works well enough.
Linus