Reader-Writer lock starvation issues

The current version of rte_rwlock doesn't do what it says in the documentation.
" The lock is used to protect data that allows multiple readers in parallel, but only one writer. All readers are blocked until the writer is finished writing."

The problem is that the current implementation does not stop a a new reader from acquiring the lock while a writer is waiting.

Writer:

      repeat until x = __atomic_load(&counter) == 0;
      __atomic_compare_exchange(&counter, &x, -1);

Reader:

      x = __atomic_load(&counter);
      __atomic_compare_exchange(&counter, &x, x + 1);

Fixing it likely would require an ABI change to add additional state.

For more background on reader-writer locks see:

https://www.cs.rochester.edu/research/synchronization/pseudocode/rw.htm
l

The code in DPDK is actually effectively the same as the first example "Simple, non-scalable reader-preference lock"

It looks like doing the right thing will require increasing the size of the rte_rwlock structure and cause an ABI breakage.

I am running with an alternative which uses ticket locks to do:
"Simple, non-scalable writer-preference lock"

My recommendation would be:

1. Fix documentation in rte_rwlock.h (and add release note) and put this in
20.02 and LTS.

2. Add new rte_ticket_rwlock.h which provides the correct semantics.

Comments?

<snip>

Quoted 8 lines

The current version of rte_rwlock doesn't do what it says in the documentation.
" The lock is used to protect data that allows multiple readers in parallel, but only one writer. All readers are blocked until the writer is finished writing."

The problem is that the current implementation does not stop a a new reader from acquiring the lock while a writer is waiting.

Agree, essentially the arbitration is left to the hardware.

Quoted 12 lines

Writer:

       repeat until x = __atomic_load(&counter) == 0;
       __atomic_compare_exchange(&counter, &x, -1);

Reader:

       x = __atomic_load(&counter);
       __atomic_compare_exchange(&counter, &x, x + 1);

Fixing it likely would require an ABI change to add additional state.

Quoted 7 lines

For more background on reader-writer locks see:

https://www.cs.rochester.edu/research/synchronization/pseudocode/rw.htm
l

The code in DPDK is actually effectively the same as the first example "Simple, non-scalable reader-preference lock"

I do not think the DPDK implementation has reader-preference. There is no code to control the arbitration between writers and readers. It is possible that if there are multiple writers the readers might be starved depending on how the hardware does the arbitration.

Quoted 6 lines

It looks like doing the right thing will require increasing the size of the rte_rwlock structure and cause an ABI breakage.

I am running with an alternative which uses ticket locks to do:
"Simple, non-scalable writer-preference lock"

Does it provide good scalability?

Quoted 5 lines

My recommendation would be:

1. Fix documentation in rte_rwlock.h (and add release note) and put this in
20.02 and LTS.

Agree, the document is not clear on the arbitration.

Quoted 1 line

2. Add new rte_ticket_rwlock.h which provides the correct semantics.

Agree.

Quoted 2 lines

Comments?

Quoted 6 lines

Quoted 6 lines

The current version of rte_rwlock doesn't do what it says in the documentation.
" The lock is used to protect data that allows multiple readers in parallel, but only one writer. All readers are blocked until the writer is

finished writing."

Quoted 19 lines

Quoted 3 lines

The problem is that the current implementation does not stop a a new reader from acquiring the lock while a writer is waiting.

Agree, essentially the arbitration is left to the hardware.

Quoted 14 lines

Writer:

       repeat until x = __atomic_load(&counter) == 0;
       __atomic_compare_exchange(&counter, &x, -1);

Reader:

       x = __atomic_load(&counter);
       __atomic_compare_exchange(&counter, &x, x + 1);

Fixing it likely would require an ABI change to add additional state.

For more background on reader-writer locks see:

Quoted 7 lines

Quoted 6 lines

https://www.cs.rochester.edu/research/synchronization/pseudocode/rw.h
tm
l

The code in DPDK is actually effectively the same as the first example "Simple, non-scalable reader-preference lock"

I do not think the DPDK implementation has reader-preference. There is no

code to control the arbitration between writers and readers. It is possible that if there are multiple writers the readers might be starved depending on how the hardware does the arbitration.

Quoted 1 line

As far as I can see, in current implementation:

When writer has the lock, both writers and readers needs to wait, and when writer releases reader or writer has chance to acquire the lock.

When reader has the lock, other readers can acquire the lock and writers has to wait, and if readers keep coming it can cause writer starvation. Overall this doesn't look fair reader-writer lock ...

Quoted 22 lines

Quoted 7 lines

It looks like doing the right thing will require increasing the size of the rte_rwlock structure and cause an ABI breakage.

I am running with an alternative which uses ticket locks to do:
"Simple, non-scalable writer-preference lock"

Does it provide good scalability?

Quoted 6 lines

My recommendation would be:

1. Fix documentation in rte_rwlock.h (and add release note) and put
this in
20.02 and LTS.

Agree, the document is not clear on the arbitration.

Quoted 1 line

2. Add new rte_ticket_rwlock.h which provides the correct semantics.

Agree.

Quoted 2 lines

Comments?

The implementation of reader/writer locks in DPDK (from first release) is simple and fast. But it can lead to writer starvation issues.

It is not easy to fix this without changing ABI and potentially breaking customer applications that are expect the unfair behavior.

The wikipedia page on reader-writer problem has a similar example which summarizes the problem pretty well.

14/01/2021 17:55, Stephen Hemminger:

Quoted 5 lines

The implementation of reader/writer locks in DPDK (from first release) is simple and fast. But it can lead to writer starvation issues.

It is not easy to fix this without changing ABI and potentially breaking customer applications that are expect the unfair behavior.

typo: "are expect"

Quoted 2 lines

The wikipedia page on reader-writer problem has a similar example which summarizes the problem pretty well.

Maybe add the URL in the commit message?

lib/librte_eal/include/generic/rte_rwlock.h line 18

Quoted 6 lines

Signed-off-by Stephen Hemminger <[email protected]>

---

lib/librte_eal/include/generic/rte_rwlock.h +1 -0

+ * Note: This version of reader/writer locks is not fair because

Quoted 6 lines

+ * readers do not block for pending writers. A stream of readers can
+ * subsequently lock out all potential writers and starve them.
+ * This is because after the first reader locks the resource,
+ * no writer can lock it. The writer will only be able to get the
+ lock
+ * when it will only be released by the last reader.

You did not get review, probably because nobody was Cc'ed. +Cc Honnappa, Joyce and Konstantin

<snip>

Quoted 13 lines

14/01/2021 17:55, Stephen Hemminger:

Quoted 5 lines

The implementation of reader/writer locks in DPDK (from first release) is simple and fast. But it can lead to writer starvation issues.

It is not easy to fix this without changing ABI and potentially breaking customer applications that are expect the unfair behavior.

typo: "are expect"

Quoted 2 lines

The wikipedia page on reader-writer problem has a similar example which summarizes the problem pretty well.

Quoted 8 lines

Maybe add the URL in the commit message?

lib/librte_eal/include/generic/rte_rwlock.h line 18

Quoted 6 lines

Signed-off-by Stephen Hemminger <[email protected]>

---

lib/librte_eal/include/generic/rte_rwlock.h +1 -0

+ * Note: This version of reader/writer locks is not fair because

^^^^^^ may be "implementation" would be better?

Quoted 6 lines

Quoted 6 lines

+ * readers do not block for pending writers. A stream of readers can
+ * subsequently lock out all potential writers and starve them.
+ * This is because after the first reader locks the resource,
+ * no writer can lock it. The writer will only be able to get the
+ lock
+ * when it will only be released by the last reader.

This looks good. Though the writer starvation is prominent, the reader starvation is possible if there is a stream of writers when a writer holds the lock. Should we call this out too?

Quoted 3 lines

You did not get review, probably because nobody was Cc'ed. +Cc Honnappa, Joyce and Konstantin

Ping for v3

12/02/2021 01:21, Honnappa Nagarahalli:

Quoted 36 lines

<snip>

Quoted 13 lines

14/01/2021 17:55, Stephen Hemminger:

Quoted 5 lines

The implementation of reader/writer locks in DPDK (from first release) is simple and fast. But it can lead to writer starvation issues.

It is not easy to fix this without changing ABI and potentially breaking customer applications that are expect the unfair behavior.

typo: "are expect"

Quoted 2 lines

The wikipedia page on reader-writer problem has a similar example which summarizes the problem pretty well.

Quoted 8 lines

Maybe add the URL in the commit message?

lib/librte_eal/include/generic/rte_rwlock.h line 18

Quoted 6 lines

Signed-off-by Stephen Hemminger <[email protected]>

---

lib/librte_eal/include/generic/rte_rwlock.h +1 -0

+ * Note: This version of reader/writer locks is not fair because

^^^^^^ may be "implementation" would be better?

Quoted 6 lines

Quoted 6 lines

+ * readers do not block for pending writers. A stream of readers can
+ * subsequently lock out all potential writers and starve them.
+ * This is because after the first reader locks the resource,
+ * no writer can lock it. The writer will only be able to get the
+ lock
+ * when it will only be released by the last reader.

This looks good. Though the writer starvation is prominent, the reader starvation is possible if there is a stream of writers when a writer holds the lock. Should we call this out too?

Quoted 3 lines

You did not get review, probably because nobody was Cc'ed. +Cc Honnappa, Joyce and Konstantin