[WireGuard] Requeuing Race Condition [Was: Re: [Cake] WireGuard Queuing, Bufferbloat, Performance, Latency, and related issues]

[WireGuard] Requeuing Race Condition [Was: Re: [Cake] WireGuard Queuing, Bufferbloat, Performance, Latency, and related issues]

[Jason A. Donenfeld]

Hey Toke,

On Wed, Oct 5, 2016 at 3:59 PM, Toke H=C3=B8iland-J=C3=B8rgensen <toke@toke=
.dk> wrote:
>> On Sun, Oct 2, 2016 at 1:31 PM, Toke H=C3=B8iland-J=C3=B8rgensen <toke@t=
oke.dk> wrote:
>>> You don't need a timer. You already have a signal for when more queue
>>> space is available in the encryption step: When a packet finishes
>>> encryption. All you need to do is try to enqueue another one at this
>>> point.
>>
>> Oh, silly me. Yes of course. Voila:
>> https://git.zx2c4.com/WireGuard/commit/?id=3Da0ad61c1a0e25a376e145f07ca2=
7c605d3852bc4
>
> Yup, that seems like the way to go about it :)

There's a small problem with this approach:

Thread 1                            |  Thread 2
----------------------------------  |  ------------------------------------
Queue it up? Nope, queue is full.   |
                                    |  I just finished encrypting my last
                                    |  packet. My queue is now empty. Has
                                    |  thread 1 set need_resend_queue? Nope=
,
                                    |  so I'll go to sleep.
Set need_resend_queue =3D true and    |
wait for thread 2 to requeue it.    |
                                    |
Nothing happens.                    |
                                    | Nothing happens.
Nothing happens.                    |
                                    | Nothing happens.
Nothing happens.                    |
                                    | Nothing happens.

One way of fixing this would be to add a spin lock that synchronizes the
submission of jobs in thread 1 and the completion of jobs in thread 2. That
looks like this:

https://git.zx2c4.com/WireGuard/commit/?h=3Djd/ugly-sync

I have no intention of actually merging this approach, as it's really too
awful. But perhaps you have a better race-free and lock-free approach.


Jason

Re: [WireGuard] Requeuing Race Condition [Was: Re: [Cake] WireGuard Queuing, Bufferbloat, Performance, Latency, and related issues]

[Toke Høiland-Jørgensen]

"Jason A. Donenfeld" <Jason@zx2c4.com> writes:

> Hey Toke,
>
> On Wed, Oct 5, 2016 at 3:59 PM, Toke H=C3=B8iland-J=C3=B8rgensen <toke@to=
ke.dk> wrote:
>>> On Sun, Oct 2, 2016 at 1:31 PM, Toke H=C3=B8iland-J=C3=B8rgensen <toke@=
toke.dk> wrote:
>>>> You don't need a timer. You already have a signal for when more queue
>>>> space is available in the encryption step: When a packet finishes
>>>> encryption. All you need to do is try to enqueue another one at this
>>>> point.
>>>
>>> Oh, silly me. Yes of course. Voila:
>>> https://git.zx2c4.com/WireGuard/commit/?id=3Da0ad61c1a0e25a376e145f07ca=
27c605d3852bc4
>>
>> Yup, that seems like the way to go about it :)
>
> There's a small problem with this approach:
>
> Thread 1                            |  Thread 2
> ----------------------------------  |  ----------------------------------=
--
> Queue it up? Nope, queue is full.   |
>                                     |  I just finished encrypting my last
>                                     |  packet. My queue is now empty. Has
>                                     |  thread 1 set need_resend_queue? No=
pe,
>                                     |  so I'll go to sleep.
> Set need_resend_queue =3D true and    |
> wait for thread 2 to requeue it.    |
>                                     |
> Nothing happens.                    |
>                                     | Nothing happens.
> Nothing happens.                    |
>                                     | Nothing happens.
> Nothing happens.                    |
>                                     | Nothing happens.
>
> One way of fixing this would be to add a spin lock that synchronizes the
> submission of jobs in thread 1 and the completion of jobs in thread 2. Th=
at
> looks like this:
>
> https://git.zx2c4.com/WireGuard/commit/?h=3Djd/ugly-sync
>
> I have no intention of actually merging this approach, as it's really too
> awful. But perhaps you have a better race-free and lock-free approach.

Ah yes, an unprotected flag will be problematic. Do you really need the
flag, though? Can't you just inspect the queue length? Presumably you're
already doing that in a way that is multithreading-safe?

-Toke