search

cloudflare / quiche

🥧 Savoury implementation of the QUIC transport protocol and HTTP/3
https://docs.quic.tech/quiche/
BSD 2-Clause "Simplified" License
9.4k stars 709 forks source link

almost_full tends to true #983

Open Sparika opened 3 years ago

Sparika commented 3 years ago

The following is only theoretical as I've not checked if it happens or not. But looking at the code and running some simplified computations, I have the impression that the almost_full function may tends to true once the received offset is sufficiently large compared to the initial max_data.

Here, max_data_next is increased by the len of the emited packets. https://github.com/cloudflare/quiche/blob/f86de8f18e930f823e00b43b08eee47dc52aa635/src/stream.rs#L872

and almost_full is true if max_data_next/2 > max_data - len (here, len is the total length received). https://github.com/cloudflare/quiche/blob/f86de8f18e930f823e00b43b08eee47dc52aa635/src/stream.rs#L951

I believe max_data_next increases constantly but max_data - (total)_len is heuristically bounded by the regular increase of max_data. Supposing that this bound is the initial value of max_data, then once max_data_next > 2*initial_max_data the stream tends to be always declared almost full.

If this is indeed true, the practical implication would be that MAX_STREAM_DATA frames would be send at a high frequency once this threshold is passed. Is it the behavior intended?

Sparika commented 3 years ago

I can confirm I am observing the behavior I've described in practice. The setup is a server sending a large amount of data to a client.

The client is configured with the following

        config.set_initial_max_data(1_000_000);
        config.set_initial_max_stream_data_uni(1_000_000);
        config.set_initial_max_stream_data_bidi_local(1_000_000);
        config.set_initial_max_stream_data_bidi_remote(1_000_000);
        config.set_initial_max_streams_bidi(100);
        config.set_initial_max_streams_uni(100);

And here what I'm observing:

    pub fn almost_full(&self) -> bool {
        // Send MAX_STREAM_DATA when the new limit is at least double the
        // amount of data that can be received before blocking.
        if self.fin_off.is_none() &&
            self.max_data_next != self.max_data &&
            self.max_data_next / 2 > self.max_data - self.len {
                println!("{:?} ALMOST FULL", self);
                true
            } else {
                println!("{:?} OK", self);
                false
            }
    }
[... All traces before that point ar "OK", i.e. not "ALMOST FULL"]
RecvBuf { data: [], off: 332053, len: 332053, max_data: 1000000, max_data_next: 1332053, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 332100, len: 332100, max_data: 1000000, max_data_next: 1332100, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 333403, len: 333403, max_data: 1000000, max_data_next: 1333403, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 333450, len: 333450, max_data: 1333403, max_data_next: 1333450, fin_off: None, drain: false } OK
[... 326 OK traces]
RecvBuf { data: [], off: 554850, len: 554850, max_data: 1333403, max_data_next: 1554850, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 556153, len: 556153, max_data: 1333403, max_data_next: 1556153, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 556200, len: 556200, max_data: 1556153, max_data_next: 1556200, fin_off: None, drain: false } OK
[... 217 OK traces]
RecvBuf { data: [], off: 703350, len: 703350, max_data: 1556153, max_data_next: 1703350, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 704653, len: 704653, max_data: 1556153, max_data_next: 1704653, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 704700, len: 704700, max_data: 1704653, max_data_next: 1704700, fin_off: None, drain: false } OK
[... 144 OK traces]
RecvBuf { data: [], off: 801900, len: 801900, max_data: 1704653, max_data_next: 1801900, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 803203, len: 803203, max_data: 1704653, max_data_next: 1803203, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 803250, len: 803250, max_data: 1803203, max_data_next: 1803250, fin_off: None, drain: false } OK
[... 95 OK traces]
RecvBuf { data: [], off: 868050, len: 868050, max_data: 1803203, max_data_next: 1868050, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 869353, len: 869353, max_data: 1803203, max_data_next: 1869353, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 869400, len: 869400, max_data: 1869353, max_data_next: 1869400, fin_off: None, drain: false } OK
[... 64 OK traces]
RecvBuf { data: [], off: 912600, len: 912600, max_data: 1869353, max_data_next: 1912600, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 913903, len: 913903, max_data: 1869353, max_data_next: 1913903, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 913950, len: 913950, max_data: 1913903, max_data_next: 1913950, fin_off: None, drain: false } OK
[... 42 OK traces]
RecvBuf { data: [], off: 942300, len: 942300, max_data: 1913903, max_data_next: 1942300, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 943603, len: 943603, max_data: 1913903, max_data_next: 1943603, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 943650, len: 943650, max_data: 1943603, max_data_next: 1943650, fin_off: None, drain: false } OK
[... 25 OK traces]
RecvBuf { data: [], off: 961200, len: 961200, max_data: 1943603, max_data_next: 1961200, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 962503, len: 962503, max_data: 1943603, max_data_next: 1962503, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 962550, len: 962550, max_data: 1962503, max_data_next: 1962550, fin_off: None, drain: false } OK
[... 18 OK traces]
RecvBuf { data: [], off: 974700, len: 974700, max_data: 1962503, max_data_next: 1974700, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 976003, len: 976003, max_data: 1962503, max_data_next: 1976003, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 976050, len: 976050, max_data: 1976003, max_data_next: 1976050, fin_off: None, drain: false } OK
[... 10 OK traces]
RecvBuf { data: [], off: 982800, len: 982800, max_data: 1976003, max_data_next: 1982800, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 984103, len: 984103, max_data: 1976003, max_data_next: 1984103, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 984150, len: 984150, max_data: 1984103, max_data_next: 1984150, fin_off: None, drain: false } OK
[... 6 OK traces]
RecvBuf { data: [], off: 988200, len: 988200, max_data: 1984103, max_data_next: 1988200, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 989503, len: 989503, max_data: 1984103, max_data_next: 1989503, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 989550, len: 989550, max_data: 1989503, max_data_next: 1989550, fin_off: None, drain: false } OK
[... 3 OK traces]
RecvBuf { data: [], off: 992250, len: 992250, max_data: 1989503, max_data_next: 1992250, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 993553, len: 993553, max_data: 1989503, max_data_next: 1993553, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 993600, len: 993600, max_data: 1993553, max_data_next: 1993600, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 994897, len: 994897, max_data: 1993553, max_data_next: 1994897, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 994950, len: 994950, max_data: 1993553, max_data_next: 1994950, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 996253, len: 996253, max_data: 1993553, max_data_next: 1996253, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 996300, len: 996300, max_data: 1996253, max_data_next: 1996300, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 997597, len: 997597, max_data: 1996253, max_data_next: 1997597, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 997650, len: 997650, max_data: 1997597, max_data_next: 1997650, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 998947, len: 998947, max_data: 1997597, max_data_next: 1998947, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 999000, len: 999000, max_data: 1998947, max_data_next: 1999000, fin_off: None, drain: false } OK
RecvBuf { data: [], off: 1000297, len: 1000297, max_data: 1998947, max_data_next: 2000297, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 1000350, len: 1000350, max_data: 2000297, max_data_next: 2000350, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 1001647, len: 1001647, max_data: 2000350, max_data_next: 2001647, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 1001700, len: 1001700, max_data: 2001647, max_data_next: 2001700, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 1002997, len: 1002997, max_data: 2001700, max_data_next: 2002997, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 1003050, len: 1003050, max_data: 2002997, max_data_next: 2003050, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 1004347, len: 1004347, max_data: 2003050, max_data_next: 2004347, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 1004400, len: 1004400, max_data: 2004347, max_data_next: 2004400, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 1005697, len: 1005697, max_data: 2004400, max_data_next: 2005697, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 1005750, len: 1005750, max_data: 2005697, max_data_next: 2005750, fin_off: None, drain: false } ALMOST FULL
[ ... 2931 ALMOST FULL traces]
RecvBuf { data: [], off: 3000997, len: 3000997, max_data: 3999700, max_data_next: 4000997, fin_off: None, drain: false } ALMOST FULL
RecvBuf { data: [], off: 3001050, len: 3001050, max_data: 4000997, max_data_next: 4001050, fin_off: Some(3001050), drain: false } OK
RecvBuf { data: [], off: 132, len: 132, max_data: 1000000, max_data_next: 1000132, fin_off: Some(132), drain: false } OK

I've shortened the trace but it's easy to see the pattern where the stream is declared almost full more and more frequently until it is always declared almost full.

I believe a fix could be to store the amount of available control flow credit (i.e. max_data_next - self.len) when sending a MAX_STREAM_DATA frame and use that value divided by two to decide if the stream is almost full instead of max_data_next/2. i.e. declare a stream almost full once half of the control flow credits available since last MAX_STREAM_DATA frames has been consumed.

ghedo commented 3 years ago

Your analysis looks correct, in fact this is a known issue, just haven't gotten to fixing it yet.

Would you like to provide a PR with a possible fix? Otherwise might take us a bit longer to fix.

Sparika commented 3 years ago

Yes, I think that is something I can look into.

Any requirements regarding PR and contributions I should know about ?

wxzcyy commented 1 year ago

Is the problem finally solved? @Sparika @ghedo