Skip to content
  • Peter Oskolkov's avatar
    ip: add helpers to process in-order fragments faster. · 353c9cb3
    Peter Oskolkov authored
    
    
    This patch introduces several helper functions/macros that will be
    used in the follow-up patch. No runtime changes yet.
    
    The new logic (fully implemented in the second patch) is as follows:
    
    * Nodes in the rb-tree will now contain not single fragments, but lists
      of consecutive fragments ("runs").
    
    * At each point in time, the current "active" run at the tail is
      maintained/tracked. Fragments that arrive in-order, adjacent
      to the previous tail fragment, are added to this tail run without
      triggering the re-balancing of the rb-tree.
    
    * If a fragment arrives out of order with the offset _before_ the tail run,
      it is inserted into the rb-tree as a single fragment.
    
    * If a fragment arrives after the current tail fragment (with a gap),
      it starts a new "tail" run, as is inserted into the rb-tree
      at the end as the head of the new run.
    
    skb->cb is used to store additional information
    needed here (suggested by Eric Dumazet).
    
    Reported-by: default avatarWillem de Bruijn <willemb@google.com>
    Signed-off-by: default avatarPeter Oskolkov <posk@google.com>
    Cc: Eric Dumazet <edumazet@google.com>
    Cc: Florian Westphal <fw@strlen.de>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    353c9cb3