• Yaogong Wang's avatar
    tcp: use an RB tree for ooo receive queue · 9f5afeae
    Yaogong Wang authored
    Over the years, TCP BDP has increased by several orders of magnitude,
    and some people are considering to reach the 2 Gbytes limit.
    
    Even with current window scale limit of 14, ~1 Gbytes maps to ~740,000
    MSS.
    
    In presence of packet losses (or reorders), TCP stores incoming packets
    into an out of order queue, and number of skbs sitting there waiting for
    the missing packets to be received can be in the 10^5 range.
    
    Most packets are appended to the tail of this queue, and when
    packets can finally be transferred to receive queue, we scan the queue
    from its head.
    
    However, in presence of heavy losses, we might have to find an arbitrary
    point in this queue, involving a linear scan for every incoming packet,
    throwing away cpu caches.
    
    This patch converts it to a RB tree, to get bounded latencies.
    
    Yaogong wrote a preliminary patch about 2 years ago.
    Eric did the rebase, added ofo_last_skb cache, polishing and tests.
    
    Tested with network dropping between 1 and 10 % packets, with good
    success (about 30 % increase of throughput in stress tests)
    
    Next step would be to also use an RB tree for the write queue at sender
    side ;)
    Signed-off-by: default avatarYaogong Wang <wygivan@google.com>
    Signed-off-by: default avatarEric Dumazet <edumazet@google.com>
    Cc: Yuchung Cheng <ycheng@google.com>
    Cc: Neal Cardwell <ncardwell@google.com>
    Cc: Ilpo Järvinen <ilpo.jarvinen@helsinki.fi>
    Acked-By: default avatarIlpo Järvinen <ilpo.jarvinen@helsinki.fi>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    9f5afeae
tcp.h 55.6 KB