diff options
| -rw-r--r-- | include/net/ip6_fib.h | 1 | ||||
| -rw-r--r-- | net/ipv6/ip6_fib.c | 8 | ||||
| -rw-r--r-- | net/ipv6/route.c | 97 |
3 files changed, 68 insertions, 38 deletions
diff --git a/include/net/ip6_fib.h b/include/net/ip6_fib.h index 9eda572a2a6..cf355a3c2ad 100644 --- a/include/net/ip6_fib.h +++ b/include/net/ip6_fib.h @@ -58,6 +58,7 @@ struct fib6_node __u16 fn_bit; /* bit key */ __u16 fn_flags; __u32 fn_sernum; + struct rt6_info *rr_ptr; }; #ifndef CONFIG_IPV6_SUBTREES diff --git a/net/ipv6/ip6_fib.c b/net/ipv6/ip6_fib.c index f4d7be77eb0..268f476ef3d 100644 --- a/net/ipv6/ip6_fib.c +++ b/net/ipv6/ip6_fib.c @@ -658,6 +658,10 @@ static int fib6_add_rt2node(struct fib6_node *fn, struct rt6_info *rt, ins = &iter->u.dst.rt6_next; } + /* Reset round-robin state, if necessary */ + if (ins == &fn->leaf) + fn->rr_ptr = NULL; + /* * insert node */ @@ -1109,6 +1113,10 @@ static void fib6_del_route(struct fib6_node *fn, struct rt6_info **rtp, rt6_stats.fib_rt_entries--; rt6_stats.fib_discarded_routes++; + /* Reset round-robin state, if necessary */ + if (fn->rr_ptr == rt) + fn->rr_ptr = NULL; + /* Adjust walkers */ read_lock(&fib6_walker_lock); FOR_WALKERS(w) { diff --git a/net/ipv6/route.c b/net/ipv6/route.c index a6b3117df54..3931b33b25e 100644 --- a/net/ipv6/route.c +++ b/net/ipv6/route.c @@ -363,55 +363,76 @@ static int rt6_score_route(struct rt6_info *rt, int oif, return m; } -static struct rt6_info *rt6_select(struct rt6_info **head, int oif, - int strict) +static struct rt6_info *find_match(struct rt6_info *rt, int oif, int strict, + int *mpri, struct rt6_info *match) { - struct rt6_info *match = NULL, *last = NULL; - struct rt6_info *rt, *rt0 = *head; - u32 metric; + int m; + + if (rt6_check_expired(rt)) + goto out; + + m = rt6_score_route(rt, oif, strict); + if (m < 0) + goto out; + + if (m > *mpri) { + if (strict & RT6_LOOKUP_F_REACHABLE) + rt6_probe(match); + *mpri = m; + match = rt; + } else if (strict & RT6_LOOKUP_F_REACHABLE) { + rt6_probe(rt); + } + +out: + return match; +} + +static struct rt6_info *find_rr_leaf(struct fib6_node *fn, + struct rt6_info *rr_head, + u32 metric, int oif, int strict) +{ + struct rt6_info *rt, *match; int mpri = -1; - RT6_TRACE("%s(head=%p(*head=%p), oif=%d)\n", - __FUNCTION__, head, head ? *head : NULL, oif); + match = NULL; + for (rt = rr_head; rt && rt->rt6i_metric == metric; + rt = rt->u.dst.rt6_next) + match = find_match(rt, oif, strict, &mpri, match); + for (rt = fn->leaf; rt && rt != rr_head && rt->rt6i_metric == metric; + rt = rt->u.dst.rt6_next) + match = find_match(rt, oif, strict, &mpri, match); - for (rt = rt0, metric = rt0->rt6i_metric; - rt && rt->rt6i_metric == metric && (!last || rt != rt0); - rt = rt->u.dst.rt6_next) { - int m; + return match; +} - if (rt6_check_expired(rt)) - continue; +static struct rt6_info *rt6_select(struct fib6_node *fn, int oif, int strict) +{ + struct rt6_info *match, *rt0; - last = rt; + RT6_TRACE("%s(fn->leaf=%p, oif=%d)\n", + __FUNCTION__, fn->leaf, oif); - m = rt6_score_route(rt, oif, strict); - if (m < 0) - continue; + rt0 = fn->rr_ptr; + if (!rt0) + fn->rr_ptr = rt0 = fn->leaf; - if (m > mpri) { - if (strict & RT6_LOOKUP_F_REACHABLE) - rt6_probe(match); - match = rt; - mpri = m; - } else if (strict & RT6_LOOKUP_F_REACHABLE) { - rt6_probe(rt); - } - } + match = find_rr_leaf(fn, rt0, rt0->rt6i_metric, oif, strict); if (!match && - (strict & RT6_LOOKUP_F_REACHABLE) && - last && last != rt0) { + (strict & RT6_LOOKUP_F_REACHABLE)) { + struct rt6_info *next = rt0->u.dst.rt6_next; + /* no entries matched; do round-robin */ - static DEFINE_SPINLOCK(lock); - spin_lock(&lock); - *head = rt0->u.dst.rt6_next; - rt0->u.dst.rt6_next = last->u.dst.rt6_next; - last->u.dst.rt6_next = rt0; - spin_unlock(&lock); + if (!next || next->rt6i_metric != rt0->rt6i_metric) + next = fn->leaf; + + if (next != rt0) + fn->rr_ptr = next; } - RT6_TRACE("%s() => %p, score=%d\n", - __FUNCTION__, match, mpri); + RT6_TRACE("%s() => %p\n", + __FUNCTION__, match); return (match ? match : &ip6_null_entry); } @@ -657,7 +678,7 @@ restart_2: fn = fib6_lookup(&table->tb6_root, &fl->fl6_dst, &fl->fl6_src); restart: - rt = rt6_select(&fn->leaf, fl->iif, strict | reachable); + rt = rt6_select(fn, fl->iif, strict | reachable); BACKTRACK(&fl->fl6_src); if (rt == &ip6_null_entry || rt->rt6i_flags & RTF_CACHE) @@ -752,7 +773,7 @@ restart_2: fn = fib6_lookup(&table->tb6_root, &fl->fl6_dst, &fl->fl6_src); restart: - rt = rt6_select(&fn->leaf, fl->oif, strict | reachable); + rt = rt6_select(fn, fl->oif, strict | reachable); BACKTRACK(&fl->fl6_src); if (rt == &ip6_null_entry || rt->rt6i_flags & RTF_CACHE) |