Skip to content
  • Timo Teras's avatar
    [XFRM]: Speed up xfrm_policy and xfrm_state walking · 4c563f76
    Timo Teras authored
    
    
    Change xfrm_policy and xfrm_state walking algorithm from O(n^2) to O(n).
    This is achieved adding the entries to one more list which is used
    solely for walking the entries.
    
    This also fixes some races where the dump can have duplicate or missing
    entries when the SPD/SADB is modified during an ongoing dump.
    
    Dumping SADB with 20000 entries using "time ip xfrm state" the sys
    time dropped from 1.012s to 0.080s.
    
    Signed-off-by: default avatarTimo Teras <timo.teras@iki.fi>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    4c563f76