From: Dmitry Vyukov <dvyukov@google.com>
To: "Jason A. Donenfeld" <Jason@zx2c4.com>
Cc: WireGuard mailing list <wireguard@lists.zx2c4.com>
Subject: Re: [PATCH RFC v1] wireguard: queueing: get rid of per-peer ring buffers
Date: Tue, 9 Feb 2021 17:20:01 +0100 [thread overview]
Message-ID: <CACT4Y+YM9d6nN7Sjy=Z=Rw++r333RtFOXJgNU7WfrJk4V+nofw@mail.gmail.com> (raw)
In-Reply-To: <CAHmME9pc==7a3vw-bv7TTDPv6XXAba_uwOHhBJvvJHZpH7hqAg@mail.gmail.com>
On Tue, Feb 9, 2021 at 4:44 PM Jason A. Donenfeld <Jason@zx2c4.com> wrote:
>
> Hi Dmitry,
>
> Thanks for the review.
>
> On Tue, Feb 9, 2021 at 9:24 AM Dmitry Vyukov <dvyukov@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;
}
next prev parent reply other threads:[~2021-02-09 16:20 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-02-08 13:38 Jason A. Donenfeld
2021-02-09 8:24 ` Dmitry Vyukov
2021-02-09 15:44 ` Jason A. Donenfeld
2021-02-09 16:20 ` Dmitry Vyukov [this message]
2021-02-17 18:36 ` Toke Høiland-Jørgensen
2021-02-17 22:28 ` Jason A. Donenfeld
2021-02-17 23:41 ` Toke Høiland-Jørgensen
2021-02-18 13:49 ` Björn Töpel
2021-02-18 13:53 ` Jason A. Donenfeld
2021-02-18 14:04 ` Björn Töpel
2021-02-18 14:15 ` Jason A. Donenfeld
2021-02-18 15:12 ` Björn Töpel
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CACT4Y+YM9d6nN7Sjy=Z=Rw++r333RtFOXJgNU7WfrJk4V+nofw@mail.gmail.com' \
--to=dvyukov@google.com \
--cc=Jason@zx2c4.com \
--cc=wireguard@lists.zx2c4.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).