• Ilpo Järvinen's avatar
    [TCP]: Rewrite SACK block processing & sack_recv_cache use · 68f8353b
    Ilpo Järvinen authored
    Key points of this patch are:
    
      - In case new SACK information is advance only type, no skb
        processing below previously discovered highest point is done
      - Optimize cases below highest point too since there's no need
        to always go up to highest point (which is very likely still
        present in that SACK), this is not entirely true though
        because I'm dropping the fastpath_skb_hint which could
        previously optimize those cases even better. Whether that's
        significant, I'm not too sure.
    
    Currently it will provide skipping by walking. Combined with
    RB-tree, all skipping would become fast too regardless of window
    size (can be done incrementally later).
    
    Previously a number of cases in TCP SACK processing fails to
    take advantage of costly stored information in sack_recv_cache,
    most importantly, expected events such as cumulative ACK and new
    hole ACKs. Processing on such ACKs result in rather long walks
    building up latencies (which easily gets nasty when window is
    huge). Those latencies are often completely unnecessary
    compared with the amount of _new_ information received, usually
    for cumulative ACK there's no new information at all, yet TCP
    walks whole queue unnecessary potentially taking a number of
    costly cache misses on the way, etc.!
    
    Since the inclusion of highest_sack, there's a lot information
    that is very likely redundant (SACK fastpath hint stuff,
    fackets_out, highest_sack), though there's no ultimate guarantee
    that they'll remain the same whole the time (in all unearthly
    scenarios). Take advantage of this knowledge here and drop
    fastpath hint and use direct access to highest SACKed skb as
    a replacement.
    
    Effectively "special cased" fastpath is dropped. This change
    adds some complexity to introduce better coveraged "fastpath",
    though the added complexity should make TCP behave more cache
    friendly.
    
    The current ACK's SACK blocks are compared against each cached
    block individially and only ranges that are new are then scanned
    by the high constant walk. For other parts of write queue, even
    when in previously known part of the SACK blocks, a faster skip
    function is used (if necessary at all). In addition, whenever
    possible, TCP fast-forwards to highest_sack skb that was made
    available by an earlier patch. In typical case, no other things
    but this fast-forward and mandatory markings after that occur
    making the access pattern quite similar to the former fastpath
    "special case".
    
    DSACKs are special case that must always be walked.
    
    The local to recv_sack_cache copying could be more intelligent
    w.r.t DSACKs which are likely to be there only once but that
    is left to a separate patch.
    Signed-off-by: default avatarIlpo Järvinen <ilpo.jarvinen@helsinki.fi>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    68f8353b
tcp_input.c 153 KB