[PATCH RFC v1] wireguard: queueing: get rid of per-peer ring buffers

[Dmitry Vyukov]

On Tue, Feb 9, 2021 at 4:44 PM Jason A. Donenfeld <Jason at zx2c4.com> wrote:
>
> Hi Dmitry,
>
> Thanks for the review.
>
> On Tue, Feb 9, 2021 at 9:24 AM Dmitry Vyukov <dvyukov at google.com> wrote:
> > Strictly saying, 0.15% is for delaying the newly added item only. This
> > is not a problem, we can just consider that push has not finished yet
> > in this case. You can get this with any queue. It's just that consumer
> > has peeked on producer that it started enqueue but has not finished
> > yet. In a mutex-protected queue consumers just don't have the
> > opportunity to peek, they just block until enqueue has completed.
> > The problem is only when a partially queued item blocks subsequent
> > completely queued items. That should be some small fraction of 0.15%.
>
> Ah right. I'll make that clear in the commit message.
>
> > We could try to cheat a bit here.
> > We could split the counter into:
> >
> > atomic_t enqueued;
> > unsigned dequeued;
> >
> > then, consumer will do just dequeued++.
> > Producers can do (depending on how precise you want them to be):
> >
> > if ((int)(atomic_read(&enqueued) - dequeued) >= MAX)
> >     return false;
> > atomic_add(&enqueued, 1);
> >
> > or, for more precise counting we could do a CAS loop on enqueued.
>
> I guess the CAS case would look like `if
> (!atomic_add_unless(&enqueued, 1, MAX + dequeued))` or similar, though
> >= might be safer than ==, so writing out the loop manually wouldn't
> be a bad idea.

What I had in mind is:

int e = READ_ONCE(q->enqueued);
for (;;) {
  int d = READ_ONCE(q->dequeued);
  if (e - d >= MAX)
    return false;
  int x = CAS(&q->enqueued, e, e+1);
  if (x == e)
    break;
  e = x;
}