DPDK patches and discussions
 help / color / mirror / Atom feed
* [dpdk-dev] Reader-Writer lock starvation issues
@ 2021-01-08 19:13 Stephen Hemminger
  2021-01-08 21:27 ` Honnappa Nagarahalli
  2021-01-12  1:04 ` [dpdk-dev] [PATCH] eal/rwlock: add note about writer starvation Stephen Hemminger
  0 siblings, 2 replies; 10+ messages in thread
From: Stephen Hemminger @ 2021-01-08 19:13 UTC (permalink / raw)
  To: dev

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.html

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?

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [dpdk-dev] Reader-Writer lock starvation issues
  2021-01-08 19:13 [dpdk-dev] Reader-Writer lock starvation issues Stephen Hemminger
@ 2021-01-08 21:27 ` Honnappa Nagarahalli
  2021-01-11 11:52   ` Ferruh Yigit
  2021-01-12  1:04 ` [dpdk-dev] [PATCH] eal/rwlock: add note about writer starvation Stephen Hemminger
  1 sibling, 1 reply; 10+ messages in thread
From: Honnappa Nagarahalli @ 2021-01-08 21:27 UTC (permalink / raw)
  To: Stephen Hemminger, dev; +Cc: Honnappa Nagarahalli, nd, nd

<snip>

> 
> 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.

> 
> 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"
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.

> 
> 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?

> 
> 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.

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

> 
> Comments?

^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [dpdk-dev] Reader-Writer lock starvation issues
  2021-01-08 21:27 ` Honnappa Nagarahalli
@ 2021-01-11 11:52   ` Ferruh Yigit
  2021-01-11 13:05     ` Honnappa Nagarahalli
  0 siblings, 1 reply; 10+ messages in thread
From: Ferruh Yigit @ 2021-01-11 11:52 UTC (permalink / raw)
  To: Honnappa Nagarahalli, Stephen Hemminger, dev; +Cc: nd

On 1/8/2021 9:27 PM, Honnappa Nagarahalli wrote:
> <snip>
> 
>>
>> 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.
> 
>>
>> 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"
> 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.
> 

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 ...

>>
>> 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?
> 
>>
>> 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.
> 
>>   2. Add new rte_ticket_rwlock.h which provides the correct semantics.
> Agree.
> 
>>
>> Comments?


^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [dpdk-dev] Reader-Writer lock starvation issues
  2021-01-11 11:52   ` Ferruh Yigit
@ 2021-01-11 13:05     ` Honnappa Nagarahalli
  0 siblings, 0 replies; 10+ messages in thread
From: Honnappa Nagarahalli @ 2021-01-11 13:05 UTC (permalink / raw)
  To: Ferruh Yigit, Stephen Hemminger, dev; +Cc: nd, Honnappa Nagarahalli, nd

<snip>

> >
> >>
> >> 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.
> >
> >>
> >> 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.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.
> >
> 
> 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.
Yes, since reader or writer can acquire the lock (when writer releases), I do not think we can call the current implementation as 'reader-preference'.

> 
> 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 ...
Agree

> 
> >>
> >> 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?
> >
> >>
> >> 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.
> >
> >>   2. Add new rte_ticket_rwlock.h which provides the correct semantics.
> > Agree.
> >
> >>
> >> Comments?


^ permalink raw reply	[flat|nested] 10+ messages in thread

* [dpdk-dev] [PATCH] eal/rwlock: add note about writer starvation
  2021-01-08 19:13 [dpdk-dev] Reader-Writer lock starvation issues Stephen Hemminger
  2021-01-08 21:27 ` Honnappa Nagarahalli
@ 2021-01-12  1:04 ` Stephen Hemminger
  2021-01-14 16:55   ` [dpdk-dev] [PATCH v2] " Stephen Hemminger
  1 sibling, 1 reply; 10+ messages in thread
From: Stephen Hemminger @ 2021-01-12  1:04 UTC (permalink / raw)
  To: dev; +Cc: Stephen Hemminger, stable

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.
Therfore this patch just changes the documentation.

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

Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
Cc: stable@dpdk.org
---
 lib/librte_eal/include/generic/rte_rwlock.h | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/lib/librte_eal/include/generic/rte_rwlock.h b/lib/librte_eal/include/generic/rte_rwlock.h
index da9bc3e9c0e2..0b30c780fc34 100644
--- a/lib/librte_eal/include/generic/rte_rwlock.h
+++ b/lib/librte_eal/include/generic/rte_rwlock.h
@@ -15,6 +15,14 @@
  * one writer. All readers are blocked until the writer is finished
  * writing.
  *
+ * Note: This version of reader/writer locks is not fair because
+ * readers do not block for pending writers. A stream of readers can
+ * subsequently lock all potential writers out and starve them.
+ * This is because after the first reader locks the resource,
+ * no writer can lock it, before it gets released.
+ * And it will only be released by the last reader.
+ *
+ * See also: https://en.wikipedia.org/wiki/Readers%E2%80%93writers_problem
  */
 
 #ifdef __cplusplus
-- 
2.29.2


^ permalink raw reply	[flat|nested] 10+ messages in thread

* [dpdk-dev] [PATCH v2] eal/rwlock: add note about writer starvation
  2021-01-12  1:04 ` [dpdk-dev] [PATCH] eal/rwlock: add note about writer starvation Stephen Hemminger
@ 2021-01-14 16:55   ` Stephen Hemminger
  2021-02-11 22:51     ` Thomas Monjalon
  0 siblings, 1 reply; 10+ messages in thread
From: Stephen Hemminger @ 2021-01-14 16:55 UTC (permalink / raw)
  To: dev; +Cc: Stephen Hemminger

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.

Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
---
v2 - fix wording and spelling

 lib/librte_eal/include/generic/rte_rwlock.h | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/lib/librte_eal/include/generic/rte_rwlock.h b/lib/librte_eal/include/generic/rte_rwlock.h
index da9bc3e9c0e2..15980e2d93e5 100644
--- a/lib/librte_eal/include/generic/rte_rwlock.h
+++ b/lib/librte_eal/include/generic/rte_rwlock.h
@@ -15,6 +15,12 @@
  * one writer. All readers are blocked until the writer is finished
  * writing.
  *
+ * Note: This version of reader/writer locks is not fair because
+ * 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.
  */
 
 #ifdef __cplusplus
-- 
2.29.2


^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [dpdk-dev] [PATCH v2] eal/rwlock: add note about writer starvation
  2021-01-14 16:55   ` [dpdk-dev] [PATCH v2] " Stephen Hemminger
@ 2021-02-11 22:51     ` Thomas Monjalon
  2021-02-12  0:21       ` Honnappa Nagarahalli
  0 siblings, 1 reply; 10+ messages in thread
From: Thomas Monjalon @ 2021-02-11 22:51 UTC (permalink / raw)
  To: Stephen Hemminger
  Cc: dev, honnappa.nagarahalli, joyce.kong, konstantin.ananyev

14/01/2021 17:55, Stephen Hemminger:
> 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"

> 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?

> 
> Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
> ---
> --- a/lib/librte_eal/include/generic/rte_rwlock.h
> +++ b/lib/librte_eal/include/generic/rte_rwlock.h
> + * Note: This version of reader/writer locks is not fair because
> + * 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



^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [dpdk-dev] [PATCH v2] eal/rwlock: add note about writer starvation
  2021-02-11 22:51     ` Thomas Monjalon
@ 2021-02-12  0:21       ` Honnappa Nagarahalli
  2021-05-12 19:10         ` Thomas Monjalon
  0 siblings, 1 reply; 10+ messages in thread
From: Honnappa Nagarahalli @ 2021-02-12  0:21 UTC (permalink / raw)
  To: thomas, Stephen Hemminger
  Cc: dev, Joyce Kong, konstantin.ananyev, nd, Honnappa Nagarahalli, nd

<snip>

> 
> 14/01/2021 17:55, Stephen Hemminger:
> > 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"
> 
> > 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?
> 
> >
> > Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
> > ---
> > --- a/lib/librte_eal/include/generic/rte_rwlock.h
> > +++ b/lib/librte_eal/include/generic/rte_rwlock.h
> > + * Note: This version of reader/writer locks is not fair because
                                ^^^^^^ may be "implementation" would be better?

> > + * 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?

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


^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [dpdk-dev] [PATCH v2] eal/rwlock: add note about writer starvation
  2021-02-12  0:21       ` Honnappa Nagarahalli
@ 2021-05-12 19:10         ` Thomas Monjalon
  2021-11-08 10:18           ` Thomas Monjalon
  0 siblings, 1 reply; 10+ messages in thread
From: Thomas Monjalon @ 2021-05-12 19:10 UTC (permalink / raw)
  To: Stephen Hemminger
  Cc: dev, Joyce Kong, konstantin.ananyev, Honnappa Nagarahalli

Ping for v3

12/02/2021 01:21, Honnappa Nagarahalli:
> <snip>
> 
> > 
> > 14/01/2021 17:55, Stephen Hemminger:
> > > 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"
> > 
> > > 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?
> > 
> > >
> > > Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
> > > ---
> > > --- a/lib/librte_eal/include/generic/rte_rwlock.h
> > > +++ b/lib/librte_eal/include/generic/rte_rwlock.h
> > > + * Note: This version of reader/writer locks is not fair because
>                                 ^^^^^^ may be "implementation" would be better?
> 
> > > + * 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?
> 
> > 
> > You did not get review, probably because nobody was Cc'ed.
> > +Cc Honnappa, Joyce and Konstantin





^ permalink raw reply	[flat|nested] 10+ messages in thread

* Re: [dpdk-dev] [PATCH v2] eal/rwlock: add note about writer starvation
  2021-05-12 19:10         ` Thomas Monjalon
@ 2021-11-08 10:18           ` Thomas Monjalon
  0 siblings, 0 replies; 10+ messages in thread
From: Thomas Monjalon @ 2021-11-08 10:18 UTC (permalink / raw)
  To: Stephen Hemminger
  Cc: dev, Joyce Kong, konstantin.ananyev, Honnappa Nagarahalli

Ping again. Stephen?


12/05/2021 21:10, Thomas Monjalon:
> Ping for v3
> 
> 12/02/2021 01:21, Honnappa Nagarahalli:
> > <snip>
> > 
> > > 
> > > 14/01/2021 17:55, Stephen Hemminger:
> > > > 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"
> > > 
> > > > 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?
> > > 
> > > >
> > > > Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
> > > > ---
> > > > --- a/lib/librte_eal/include/generic/rte_rwlock.h
> > > > +++ b/lib/librte_eal/include/generic/rte_rwlock.h
> > > > + * Note: This version of reader/writer locks is not fair because
> >                                 ^^^^^^ may be "implementation" would be better?
> > 
> > > > + * 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?
> > 
> > > 
> > > You did not get review, probably because nobody was Cc'ed.
> > > +Cc Honnappa, Joyce and Konstantin





^ permalink raw reply	[flat|nested] 10+ messages in thread

end of thread, other threads:[~2021-11-08 10:18 UTC | newest]

Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-01-08 19:13 [dpdk-dev] Reader-Writer lock starvation issues Stephen Hemminger
2021-01-08 21:27 ` Honnappa Nagarahalli
2021-01-11 11:52   ` Ferruh Yigit
2021-01-11 13:05     ` Honnappa Nagarahalli
2021-01-12  1:04 ` [dpdk-dev] [PATCH] eal/rwlock: add note about writer starvation Stephen Hemminger
2021-01-14 16:55   ` [dpdk-dev] [PATCH v2] " Stephen Hemminger
2021-02-11 22:51     ` Thomas Monjalon
2021-02-12  0:21       ` Honnappa Nagarahalli
2021-05-12 19:10         ` Thomas Monjalon
2021-11-08 10:18           ` Thomas Monjalon

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).