Gitweb:     
http://git.kernel.org/git/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commit;h=d5ce8a0e97073169b5fe0b7c52bd020cdb017dfa
Commit:     d5ce8a0e97073169b5fe0b7c52bd020cdb017dfa
Parent:     9195bef7fb0ba0a91d5ffa566bcf8e007e3c7172
Author:     Stephen Hemminger <[EMAIL PROTECTED]>
AuthorDate: Tue Jan 22 21:57:22 2008 -0800
Committer:  David S. Miller <[EMAIL PROTECTED]>
CommitDate: Mon Jan 28 15:11:01 2008 -0800

    [IPV4] fib_trie: avoid rescan on dump
    
    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: Stephen Hemminger <[EMAIL PROTECTED]>
    Signed-off-by: David S. Miller <[EMAIL PROTECTED]>
---
 net/ipv4/fib_trie.c |   34 +++++++++++++++++++++-------------
 1 files changed, 21 insertions(+), 13 deletions(-)

diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 441c4ea..f1005fe 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -1917,35 +1917,43 @@ static int fn_trie_dump_leaf(struct leaf *l, struct 
fib_table *tb,
        return skb->len;
 }
 
-
-
 static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb,
                        struct netlink_callback *cb)
 {
        struct leaf *l;
        struct trie *t = (struct trie *) tb->tb_data;
-       int h = 0;
-       int s_h = cb->args[2];
+       t_key key = cb->args[2];
 
        rcu_read_lock();
-       for (h = 0, l = trie_firstleaf(t); l != NULL; h++, l = 
trie_nextleaf(l)) {
-               if (h < s_h)
-                       continue;
-
-               if (h > s_h) {
-                       cb->args[3] = 0;
-                       cb->args[4] = 0;
+       /* Dump starting at last key.
+        * Note: 0.0.0.0/0 (ie default) is first key.
+        */
+       if (!key)
+               l = trie_firstleaf(t);
+       else {
+               l = fib_find_node(t, key);
+               if (!l) {
+                       /* The table changed during the dump, rather than
+                        * giving partial data, just make application retry.
+                        */
+                       rcu_read_unlock();
+                       return -EBUSY;
                }
+       }
 
+       while (l) {
+               cb->args[2] = l->key;
                if (fn_trie_dump_leaf(l, tb, skb, cb) < 0) {
                        rcu_read_unlock();
-                       cb->args[2] = h;
                        return -1;
                }
+
+               l = trie_nextleaf(l);
+               memset(&cb->args[3], 0,
+                      sizeof(cb->args) - 3*sizeof(cb->args[0]));
        }
        rcu_read_unlock();
 
-       cb->args[2] = h;
        return skb->len;
 }
 
-
To unsubscribe from this list: send the line "unsubscribe git-commits-head" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to