[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øiland-Jørgensen <toke at toke.dk> wrote:
>> On Sun, Oct 2, 2016 at 1:31 PM, Toke Høiland-Jørgensen <toke at 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=a0ad61c1a0e25a376e145f07ca27c605d3852bc4
>
> 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 = 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=jd/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