• Stephen Hemminger's avatar
    [IPV4] fib_trie: avoid rescan on dump · d5ce8a0e
    Stephen Hemminger authored
    This converts dumping (and flushing) of large route tables form O(N^2)
    to O(N). If the route dump took multiple pages then the dump routine
    gets called again. The old code kept track of location by counter, the
    new code instead uses the last key.
    
    This is a really big win ( 0.3 sec vs 12 sec) for big route tables.
    
    One side effect is that if the table changes during the dump, then the
    last key will not be found, and we will return -EBUSY.
    Signed-off-by: default avatarStephen Hemminger <shemminger@vyatta.com>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    d5ce8a0e
fib_trie.c 59.3 KB