diff options
author | Alexander Duyck <alexander.h.duyck@redhat.com> | 2015-02-25 18:31:51 -0500 |
---|---|---|
committer | David S. Miller <davem@davemloft.net> | 2015-02-27 16:37:07 -0500 |
commit | 79e5ad2ceb00673e5f2d278a892adcbf596a6b5a (patch) | |
tree | ded89f2190deffac52d17be63a99a8920c25da18 /net/ipv4/fib_trie.c | |
parent | 9b6ebad5c3a152271c6af19cd44e20001ae72fe8 (diff) |
fib_trie: Remove leaf_info
At this point the leaf_info hash is redundant. By adding the suffix length
to the fib_alias hash list we no longer have need of leaf_info as we can
determine the prefix length from fa_slen. So we can compress things by
dropping the leaf_info structure from fib_trie and instead directly connect
the leaves to the fib_alias hash list.
Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net/ipv4/fib_trie.c')
-rw-r--r-- | net/ipv4/fib_trie.c | 463 |
1 files changed, 156 insertions, 307 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c index 79cd8c029cf4..f48534577f8d 100644 --- a/net/ipv4/fib_trie.c +++ b/net/ipv4/fib_trie.c | |||
@@ -108,17 +108,10 @@ struct tnode { | |||
108 | struct tnode __rcu *child[0]; | 108 | struct tnode __rcu *child[0]; |
109 | }; | 109 | }; |
110 | /* This list pointer if valid if bits == 0 (LEAF) */ | 110 | /* This list pointer if valid if bits == 0 (LEAF) */ |
111 | struct hlist_head list; | 111 | struct hlist_head leaf; |
112 | }; | 112 | }; |
113 | }; | 113 | }; |
114 | 114 | ||
115 | struct leaf_info { | ||
116 | struct hlist_node hlist; | ||
117 | unsigned char slen; | ||
118 | struct hlist_head falh; | ||
119 | struct rcu_head rcu; | ||
120 | }; | ||
121 | |||
122 | #ifdef CONFIG_IP_FIB_TRIE_STATS | 115 | #ifdef CONFIG_IP_FIB_TRIE_STATS |
123 | struct trie_use_stats { | 116 | struct trie_use_stats { |
124 | unsigned int gets; | 117 | unsigned int gets; |
@@ -289,11 +282,6 @@ static void __node_free_rcu(struct rcu_head *head) | |||
289 | 282 | ||
290 | #define node_free(n) call_rcu(&n->rcu, __node_free_rcu) | 283 | #define node_free(n) call_rcu(&n->rcu, __node_free_rcu) |
291 | 284 | ||
292 | static inline void free_leaf_info(struct leaf_info *leaf) | ||
293 | { | ||
294 | kfree_rcu(leaf, rcu); | ||
295 | } | ||
296 | |||
297 | static struct tnode *tnode_alloc(size_t size) | 285 | static struct tnode *tnode_alloc(size_t size) |
298 | { | 286 | { |
299 | if (size <= PAGE_SIZE) | 287 | if (size <= PAGE_SIZE) |
@@ -327,21 +315,11 @@ static struct tnode *leaf_new(t_key key) | |||
327 | /* set bits to 0 indicating we are not a tnode */ | 315 | /* set bits to 0 indicating we are not a tnode */ |
328 | l->bits = 0; | 316 | l->bits = 0; |
329 | 317 | ||
330 | INIT_HLIST_HEAD(&l->list); | 318 | INIT_HLIST_HEAD(&l->leaf); |
331 | } | 319 | } |
332 | return l; | 320 | return l; |
333 | } | 321 | } |
334 | 322 | ||
335 | static struct leaf_info *leaf_info_new(int plen) | ||
336 | { | ||
337 | struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL); | ||
338 | if (li) { | ||
339 | li->slen = KEYLENGTH - plen; | ||
340 | INIT_HLIST_HEAD(&li->falh); | ||
341 | } | ||
342 | return li; | ||
343 | } | ||
344 | |||
345 | static struct tnode *tnode_new(t_key key, int pos, int bits) | 323 | static struct tnode *tnode_new(t_key key, int pos, int bits) |
346 | { | 324 | { |
347 | size_t sz = offsetof(struct tnode, child[1ul << bits]); | 325 | size_t sz = offsetof(struct tnode, child[1ul << bits]); |
@@ -864,32 +842,6 @@ static void resize(struct trie *t, struct tnode *tn) | |||
864 | } | 842 | } |
865 | } | 843 | } |
866 | 844 | ||
867 | /* readside must use rcu_read_lock currently dump routines | ||
868 | via get_fa_head and dump */ | ||
869 | |||
870 | static struct leaf_info *find_leaf_info(struct tnode *l, int plen) | ||
871 | { | ||
872 | struct hlist_head *head = &l->list; | ||
873 | struct leaf_info *li; | ||
874 | int slen = KEYLENGTH - plen; | ||
875 | |||
876 | hlist_for_each_entry_rcu(li, head, hlist) | ||
877 | if (li->slen == slen) | ||
878 | return li; | ||
879 | |||
880 | return NULL; | ||
881 | } | ||
882 | |||
883 | static inline struct hlist_head *get_fa_head(struct tnode *l, int plen) | ||
884 | { | ||
885 | struct leaf_info *li = find_leaf_info(l, plen); | ||
886 | |||
887 | if (!li) | ||
888 | return NULL; | ||
889 | |||
890 | return &li->falh; | ||
891 | } | ||
892 | |||
893 | static void leaf_pull_suffix(struct tnode *l) | 845 | static void leaf_pull_suffix(struct tnode *l) |
894 | { | 846 | { |
895 | struct tnode *tp = node_parent(l); | 847 | struct tnode *tp = node_parent(l); |
@@ -914,43 +866,47 @@ static void leaf_push_suffix(struct tnode *l) | |||
914 | } | 866 | } |
915 | } | 867 | } |
916 | 868 | ||
917 | static void remove_leaf_info(struct tnode *l, struct leaf_info *old) | 869 | static void fib_remove_alias(struct tnode *l, struct fib_alias *old) |
918 | { | 870 | { |
919 | /* record the location of the previous list_info entry */ | 871 | /* record the location of the previous list_info entry */ |
920 | struct hlist_node **pprev = old->hlist.pprev; | 872 | struct hlist_node **pprev = old->fa_list.pprev; |
921 | struct leaf_info *li = hlist_entry(pprev, typeof(*li), hlist.next); | 873 | struct fib_alias *fa = hlist_entry(pprev, typeof(*fa), fa_list.next); |
922 | 874 | ||
923 | /* remove the leaf info from the list */ | 875 | /* remove the fib_alias from the list */ |
924 | hlist_del_rcu(&old->hlist); | 876 | hlist_del_rcu(&old->fa_list); |
925 | 877 | ||
926 | /* only access li if it is pointing at the last valid hlist_node */ | 878 | /* only access fa if it is pointing at the last valid hlist_node */ |
927 | if (hlist_empty(&l->list) || (*pprev)) | 879 | if (hlist_empty(&l->leaf) || (*pprev)) |
928 | return; | 880 | return; |
929 | 881 | ||
930 | /* update the trie with the latest suffix length */ | 882 | /* update the trie with the latest suffix length */ |
931 | l->slen = li->slen; | 883 | l->slen = fa->fa_slen; |
932 | leaf_pull_suffix(l); | 884 | leaf_pull_suffix(l); |
933 | } | 885 | } |
934 | 886 | ||
935 | static void insert_leaf_info(struct tnode *l, struct leaf_info *new) | 887 | static void fib_insert_alias(struct tnode *l, struct fib_alias *fa, |
888 | struct fib_alias *new) | ||
936 | { | 889 | { |
937 | struct hlist_head *head = &l->list; | 890 | if (fa) { |
938 | struct leaf_info *li, *last = NULL; | 891 | hlist_add_before_rcu(&new->fa_list, &fa->fa_list); |
892 | } else { | ||
893 | struct fib_alias *last; | ||
939 | 894 | ||
940 | hlist_for_each_entry(li, head, hlist) { | 895 | hlist_for_each_entry(last, &l->leaf, fa_list) { |
941 | if (new->slen < li->slen) | 896 | if (new->fa_slen < last->fa_slen) |
942 | break; | 897 | break; |
943 | last = li; | 898 | fa = last; |
944 | } | 899 | } |
945 | 900 | ||
946 | if (last) | 901 | if (fa) |
947 | hlist_add_behind_rcu(&new->hlist, &last->hlist); | 902 | hlist_add_behind_rcu(&new->fa_list, &fa->fa_list); |
948 | else | 903 | else |
949 | hlist_add_head_rcu(&new->hlist, head); | 904 | hlist_add_head_rcu(&new->fa_list, &l->leaf); |
905 | } | ||
950 | 906 | ||
951 | /* if we added to the tail node then we need to update slen */ | 907 | /* if we added to the tail node then we need to update slen */ |
952 | if (l->slen < new->slen) { | 908 | if (l->slen < new->fa_slen) { |
953 | l->slen = new->slen; | 909 | l->slen = new->fa_slen; |
954 | leaf_push_suffix(l); | 910 | leaf_push_suffix(l); |
955 | } | 911 | } |
956 | } | 912 | } |
@@ -989,8 +945,8 @@ static struct tnode *fib_find_node(struct trie *t, u32 key) | |||
989 | /* Return the first fib alias matching TOS with | 945 | /* Return the first fib alias matching TOS with |
990 | * priority less than or equal to PRIO. | 946 | * priority less than or equal to PRIO. |
991 | */ | 947 | */ |
992 | static struct fib_alias *fib_find_alias(struct hlist_head *fah, u8 tos, | 948 | static struct fib_alias *fib_find_alias(struct hlist_head *fah, u8 slen, |
993 | u32 prio) | 949 | u8 tos, u32 prio) |
994 | { | 950 | { |
995 | struct fib_alias *fa; | 951 | struct fib_alias *fa; |
996 | 952 | ||
@@ -998,6 +954,10 @@ static struct fib_alias *fib_find_alias(struct hlist_head *fah, u8 tos, | |||
998 | return NULL; | 954 | return NULL; |
999 | 955 | ||
1000 | hlist_for_each_entry(fa, fah, fa_list) { | 956 | hlist_for_each_entry(fa, fah, fa_list) { |
957 | if (fa->fa_slen < slen) | ||
958 | continue; | ||
959 | if (fa->fa_slen != slen) | ||
960 | break; | ||
1001 | if (fa->fa_tos > tos) | 961 | if (fa->fa_tos > tos) |
1002 | continue; | 962 | continue; |
1003 | if (fa->fa_info->fib_priority >= prio || fa->fa_tos < tos) | 963 | if (fa->fa_info->fib_priority >= prio || fa->fa_tos < tos) |
@@ -1023,16 +983,9 @@ static void trie_rebalance(struct trie *t, struct tnode *tn) | |||
1023 | 983 | ||
1024 | /* only used from updater-side */ | 984 | /* only used from updater-side */ |
1025 | 985 | ||
1026 | static struct hlist_head *fib_insert_node(struct trie *t, u32 key, int plen) | 986 | static struct tnode *fib_insert_node(struct trie *t, u32 key, int plen) |
1027 | { | 987 | { |
1028 | struct hlist_head *fa_head = NULL; | ||
1029 | struct tnode *l, *n, *tp = NULL; | 988 | struct tnode *l, *n, *tp = NULL; |
1030 | struct leaf_info *li; | ||
1031 | |||
1032 | li = leaf_info_new(plen); | ||
1033 | if (!li) | ||
1034 | return NULL; | ||
1035 | fa_head = &li->falh; | ||
1036 | 989 | ||
1037 | n = rtnl_dereference(t->trie); | 990 | n = rtnl_dereference(t->trie); |
1038 | 991 | ||
@@ -1063,8 +1016,7 @@ static struct hlist_head *fib_insert_node(struct trie *t, u32 key, int plen) | |||
1063 | /* we have found a leaf. Prefixes have already been compared */ | 1016 | /* we have found a leaf. Prefixes have already been compared */ |
1064 | if (IS_LEAF(n)) { | 1017 | if (IS_LEAF(n)) { |
1065 | /* Case 1: n is a leaf, and prefixes match*/ | 1018 | /* Case 1: n is a leaf, and prefixes match*/ |
1066 | insert_leaf_info(n, li); | 1019 | return n; |
1067 | return fa_head; | ||
1068 | } | 1020 | } |
1069 | 1021 | ||
1070 | tp = n; | 1022 | tp = n; |
@@ -1072,12 +1024,8 @@ static struct hlist_head *fib_insert_node(struct trie *t, u32 key, int plen) | |||
1072 | } | 1024 | } |
1073 | 1025 | ||
1074 | l = leaf_new(key); | 1026 | l = leaf_new(key); |
1075 | if (!l) { | 1027 | if (!l) |
1076 | free_leaf_info(li); | ||
1077 | return NULL; | 1028 | return NULL; |
1078 | } | ||
1079 | |||
1080 | insert_leaf_info(l, li); | ||
1081 | 1029 | ||
1082 | /* Case 2: n is a LEAF or a TNODE and the key doesn't match. | 1030 | /* Case 2: n is a LEAF or a TNODE and the key doesn't match. |
1083 | * | 1031 | * |
@@ -1090,7 +1038,6 @@ static struct hlist_head *fib_insert_node(struct trie *t, u32 key, int plen) | |||
1090 | 1038 | ||
1091 | tn = tnode_new(key, __fls(key ^ n->key), 1); | 1039 | tn = tnode_new(key, __fls(key ^ n->key), 1); |
1092 | if (!tn) { | 1040 | if (!tn) { |
1093 | free_leaf_info(li); | ||
1094 | node_free(l); | 1041 | node_free(l); |
1095 | return NULL; | 1042 | return NULL; |
1096 | } | 1043 | } |
@@ -1116,7 +1063,7 @@ static struct hlist_head *fib_insert_node(struct trie *t, u32 key, int plen) | |||
1116 | rcu_assign_pointer(t->trie, l); | 1063 | rcu_assign_pointer(t->trie, l); |
1117 | } | 1064 | } |
1118 | 1065 | ||
1119 | return fa_head; | 1066 | return l; |
1120 | } | 1067 | } |
1121 | 1068 | ||
1122 | /* | 1069 | /* |
@@ -1126,9 +1073,9 @@ int fib_table_insert(struct fib_table *tb, struct fib_config *cfg) | |||
1126 | { | 1073 | { |
1127 | struct trie *t = (struct trie *) tb->tb_data; | 1074 | struct trie *t = (struct trie *) tb->tb_data; |
1128 | struct fib_alias *fa, *new_fa; | 1075 | struct fib_alias *fa, *new_fa; |
1129 | struct hlist_head *fa_head = NULL; | ||
1130 | struct fib_info *fi; | 1076 | struct fib_info *fi; |
1131 | int plen = cfg->fc_dst_len; | 1077 | u8 plen = cfg->fc_dst_len; |
1078 | u8 slen = KEYLENGTH - plen; | ||
1132 | u8 tos = cfg->fc_tos; | 1079 | u8 tos = cfg->fc_tos; |
1133 | u32 key, mask; | 1080 | u32 key, mask; |
1134 | int err; | 1081 | int err; |
@@ -1146,8 +1093,6 @@ int fib_table_insert(struct fib_table *tb, struct fib_config *cfg) | |||
1146 | if (key & ~mask) | 1093 | if (key & ~mask) |
1147 | return -EINVAL; | 1094 | return -EINVAL; |
1148 | 1095 | ||
1149 | key = key & mask; | ||
1150 | |||
1151 | fi = fib_create_info(cfg); | 1096 | fi = fib_create_info(cfg); |
1152 | if (IS_ERR(fi)) { | 1097 | if (IS_ERR(fi)) { |
1153 | err = PTR_ERR(fi); | 1098 | err = PTR_ERR(fi); |
@@ -1155,12 +1100,7 @@ int fib_table_insert(struct fib_table *tb, struct fib_config *cfg) | |||
1155 | } | 1100 | } |
1156 | 1101 | ||
1157 | l = fib_find_node(t, key); | 1102 | l = fib_find_node(t, key); |
1158 | fa = NULL; | 1103 | fa = l ? fib_find_alias(&l->leaf, slen, tos, fi->fib_priority) : NULL; |
1159 | |||
1160 | if (l) { | ||
1161 | fa_head = get_fa_head(l, plen); | ||
1162 | fa = fib_find_alias(fa_head, tos, fi->fib_priority); | ||
1163 | } | ||
1164 | 1104 | ||
1165 | /* Now fa, if non-NULL, points to the first fib alias | 1105 | /* Now fa, if non-NULL, points to the first fib alias |
1166 | * with the same keys [prefix,tos,priority], if such key already | 1106 | * with the same keys [prefix,tos,priority], if such key already |
@@ -1187,7 +1127,7 @@ int fib_table_insert(struct fib_table *tb, struct fib_config *cfg) | |||
1187 | fa_match = NULL; | 1127 | fa_match = NULL; |
1188 | fa_first = fa; | 1128 | fa_first = fa; |
1189 | hlist_for_each_entry_from(fa, fa_list) { | 1129 | hlist_for_each_entry_from(fa, fa_list) { |
1190 | if (fa->fa_tos != tos) | 1130 | if ((fa->fa_slen != slen) || (fa->fa_tos != tos)) |
1191 | break; | 1131 | break; |
1192 | if (fa->fa_info->fib_priority != fi->fib_priority) | 1132 | if (fa->fa_info->fib_priority != fi->fib_priority) |
1193 | break; | 1133 | break; |
@@ -1255,12 +1195,12 @@ int fib_table_insert(struct fib_table *tb, struct fib_config *cfg) | |||
1255 | new_fa->fa_tos = tos; | 1195 | new_fa->fa_tos = tos; |
1256 | new_fa->fa_type = cfg->fc_type; | 1196 | new_fa->fa_type = cfg->fc_type; |
1257 | new_fa->fa_state = 0; | 1197 | new_fa->fa_state = 0; |
1258 | new_fa->fa_slen = KEYLENGTH - plen; | 1198 | new_fa->fa_slen = slen; |
1259 | 1199 | ||
1260 | /* Insert new entry to the list. */ | 1200 | /* Insert new entry to the list. */ |
1261 | if (!fa_head) { | 1201 | if (!l) { |
1262 | fa_head = fib_insert_node(t, key, plen); | 1202 | l = fib_insert_node(t, key, plen); |
1263 | if (unlikely(!fa_head)) { | 1203 | if (unlikely(!l)) { |
1264 | err = -ENOMEM; | 1204 | err = -ENOMEM; |
1265 | goto out_free_new_fa; | 1205 | goto out_free_new_fa; |
1266 | } | 1206 | } |
@@ -1269,19 +1209,7 @@ int fib_table_insert(struct fib_table *tb, struct fib_config *cfg) | |||
1269 | if (!plen) | 1209 | if (!plen) |
1270 | tb->tb_num_default++; | 1210 | tb->tb_num_default++; |
1271 | 1211 | ||
1272 | if (fa) { | 1212 | fib_insert_alias(l, fa, new_fa); |
1273 | hlist_add_before_rcu(&new_fa->fa_list, &fa->fa_list); | ||
1274 | } else { | ||
1275 | struct fib_alias *last; | ||
1276 | |||
1277 | hlist_for_each_entry(last, fa_head, fa_list) | ||
1278 | fa = last; | ||
1279 | |||
1280 | if (fa) | ||
1281 | hlist_add_behind_rcu(&new_fa->fa_list, &fa->fa_list); | ||
1282 | else | ||
1283 | hlist_add_head_rcu(&new_fa->fa_list, fa_head); | ||
1284 | } | ||
1285 | 1213 | ||
1286 | rt_cache_flush(cfg->fc_nlinfo.nl_net); | 1214 | rt_cache_flush(cfg->fc_nlinfo.nl_net); |
1287 | rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id, | 1215 | rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id, |
@@ -1314,7 +1242,7 @@ int fib_table_lookup(struct fib_table *tb, const struct flowi4 *flp, | |||
1314 | #endif | 1242 | #endif |
1315 | const t_key key = ntohl(flp->daddr); | 1243 | const t_key key = ntohl(flp->daddr); |
1316 | struct tnode *n, *pn; | 1244 | struct tnode *n, *pn; |
1317 | struct leaf_info *li; | 1245 | struct fib_alias *fa; |
1318 | t_key cindex; | 1246 | t_key cindex; |
1319 | 1247 | ||
1320 | n = rcu_dereference(t->trie); | 1248 | n = rcu_dereference(t->trie); |
@@ -1417,56 +1345,51 @@ backtrace: | |||
1417 | 1345 | ||
1418 | found: | 1346 | found: |
1419 | /* Step 3: Process the leaf, if that fails fall back to backtracing */ | 1347 | /* Step 3: Process the leaf, if that fails fall back to backtracing */ |
1420 | hlist_for_each_entry_rcu(li, &n->list, hlist) { | 1348 | hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) { |
1421 | struct fib_alias *fa; | 1349 | struct fib_info *fi = fa->fa_info; |
1422 | 1350 | int nhsel, err; | |
1423 | hlist_for_each_entry_rcu(fa, &li->falh, fa_list) { | ||
1424 | struct fib_info *fi = fa->fa_info; | ||
1425 | int nhsel, err; | ||
1426 | 1351 | ||
1427 | if (((key ^ n->key) >= (1ul << fa->fa_slen)) && | 1352 | if (((key ^ n->key) >= (1ul << fa->fa_slen)) && |
1428 | ((BITS_PER_LONG > KEYLENGTH) || | 1353 | ((BITS_PER_LONG > KEYLENGTH) || (fa->fa_slen != KEYLENGTH))) |
1429 | (fa->fa_slen != KEYLENGTH))) | ||
1430 | continue; | ||
1431 | if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos) | ||
1432 | continue; | ||
1433 | if (fi->fib_dead) | ||
1434 | continue; | 1354 | continue; |
1435 | if (fa->fa_info->fib_scope < flp->flowi4_scope) | 1355 | if (fa->fa_tos && fa->fa_tos != flp->flowi4_tos) |
1436 | continue; | 1356 | continue; |
1437 | fib_alias_accessed(fa); | 1357 | if (fi->fib_dead) |
1438 | err = fib_props[fa->fa_type].error; | 1358 | continue; |
1439 | if (unlikely(err < 0)) { | 1359 | if (fa->fa_info->fib_scope < flp->flowi4_scope) |
1360 | continue; | ||
1361 | fib_alias_accessed(fa); | ||
1362 | err = fib_props[fa->fa_type].error; | ||
1363 | if (unlikely(err < 0)) { | ||
1440 | #ifdef CONFIG_IP_FIB_TRIE_STATS | 1364 | #ifdef CONFIG_IP_FIB_TRIE_STATS |
1441 | this_cpu_inc(stats->semantic_match_passed); | 1365 | this_cpu_inc(stats->semantic_match_passed); |
1442 | #endif | 1366 | #endif |
1443 | return err; | 1367 | return err; |
1444 | } | 1368 | } |
1445 | if (fi->fib_flags & RTNH_F_DEAD) | 1369 | if (fi->fib_flags & RTNH_F_DEAD) |
1370 | continue; | ||
1371 | for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) { | ||
1372 | const struct fib_nh *nh = &fi->fib_nh[nhsel]; | ||
1373 | |||
1374 | if (nh->nh_flags & RTNH_F_DEAD) | ||
1375 | continue; | ||
1376 | if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif) | ||
1446 | continue; | 1377 | continue; |
1447 | for (nhsel = 0; nhsel < fi->fib_nhs; nhsel++) { | 1378 | |
1448 | const struct fib_nh *nh = &fi->fib_nh[nhsel]; | 1379 | if (!(fib_flags & FIB_LOOKUP_NOREF)) |
1449 | 1380 | atomic_inc(&fi->fib_clntref); | |
1450 | if (nh->nh_flags & RTNH_F_DEAD) | 1381 | |
1451 | continue; | 1382 | res->prefixlen = KEYLENGTH - fa->fa_slen; |
1452 | if (flp->flowi4_oif && flp->flowi4_oif != nh->nh_oif) | 1383 | res->nh_sel = nhsel; |
1453 | continue; | 1384 | res->type = fa->fa_type; |
1454 | 1385 | res->scope = fi->fib_scope; | |
1455 | if (!(fib_flags & FIB_LOOKUP_NOREF)) | 1386 | res->fi = fi; |
1456 | atomic_inc(&fi->fib_clntref); | 1387 | res->table = tb; |
1457 | 1388 | res->fa_head = &n->leaf; | |
1458 | res->prefixlen = KEYLENGTH - fa->fa_slen; | ||
1459 | res->nh_sel = nhsel; | ||
1460 | res->type = fa->fa_type; | ||
1461 | res->scope = fi->fib_scope; | ||
1462 | res->fi = fi; | ||
1463 | res->table = tb; | ||
1464 | res->fa_head = &li->falh; | ||
1465 | #ifdef CONFIG_IP_FIB_TRIE_STATS | 1389 | #ifdef CONFIG_IP_FIB_TRIE_STATS |
1466 | this_cpu_inc(stats->semantic_match_passed); | 1390 | this_cpu_inc(stats->semantic_match_passed); |
1467 | #endif | 1391 | #endif |
1468 | return err; | 1392 | return err; |
1469 | } | ||
1470 | } | 1393 | } |
1471 | } | 1394 | } |
1472 | #ifdef CONFIG_IP_FIB_TRIE_STATS | 1395 | #ifdef CONFIG_IP_FIB_TRIE_STATS |
@@ -1501,15 +1424,14 @@ static void trie_leaf_remove(struct trie *t, struct tnode *l) | |||
1501 | int fib_table_delete(struct fib_table *tb, struct fib_config *cfg) | 1424 | int fib_table_delete(struct fib_table *tb, struct fib_config *cfg) |
1502 | { | 1425 | { |
1503 | struct trie *t = (struct trie *) tb->tb_data; | 1426 | struct trie *t = (struct trie *) tb->tb_data; |
1504 | u32 key, mask; | ||
1505 | int plen = cfg->fc_dst_len; | ||
1506 | u8 tos = cfg->fc_tos; | ||
1507 | struct fib_alias *fa, *fa_to_delete; | 1427 | struct fib_alias *fa, *fa_to_delete; |
1508 | struct hlist_head *fa_head; | 1428 | u8 plen = cfg->fc_dst_len; |
1429 | u8 tos = cfg->fc_tos; | ||
1430 | u8 slen = KEYLENGTH - plen; | ||
1509 | struct tnode *l; | 1431 | struct tnode *l; |
1510 | struct leaf_info *li; | 1432 | u32 key, mask; |
1511 | 1433 | ||
1512 | if (plen > 32) | 1434 | if (plen > KEYLENGTH) |
1513 | return -EINVAL; | 1435 | return -EINVAL; |
1514 | 1436 | ||
1515 | key = ntohl(cfg->fc_dst); | 1437 | key = ntohl(cfg->fc_dst); |
@@ -1518,19 +1440,11 @@ int fib_table_delete(struct fib_table *tb, struct fib_config *cfg) | |||
1518 | if (key & ~mask) | 1440 | if (key & ~mask) |
1519 | return -EINVAL; | 1441 | return -EINVAL; |
1520 | 1442 | ||
1521 | key = key & mask; | ||
1522 | l = fib_find_node(t, key); | 1443 | l = fib_find_node(t, key); |
1523 | |||
1524 | if (!l) | 1444 | if (!l) |
1525 | return -ESRCH; | 1445 | return -ESRCH; |
1526 | 1446 | ||
1527 | li = find_leaf_info(l, plen); | 1447 | fa = fib_find_alias(&l->leaf, slen, tos, 0); |
1528 | |||
1529 | if (!li) | ||
1530 | return -ESRCH; | ||
1531 | |||
1532 | fa_head = &li->falh; | ||
1533 | fa = fib_find_alias(fa_head, tos, 0); | ||
1534 | 1448 | ||
1535 | if (!fa) | 1449 | if (!fa) |
1536 | return -ESRCH; | 1450 | return -ESRCH; |
@@ -1541,7 +1455,7 @@ int fib_table_delete(struct fib_table *tb, struct fib_config *cfg) | |||
1541 | hlist_for_each_entry_from(fa, fa_list) { | 1455 | hlist_for_each_entry_from(fa, fa_list) { |
1542 | struct fib_info *fi = fa->fa_info; | 1456 | struct fib_info *fi = fa->fa_info; |
1543 | 1457 | ||
1544 | if (fa->fa_tos != tos) | 1458 | if ((fa->fa_slen != slen) || (fa->fa_tos != tos)) |
1545 | break; | 1459 | break; |
1546 | 1460 | ||
1547 | if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) && | 1461 | if ((!cfg->fc_type || fa->fa_type == cfg->fc_type) && |
@@ -1564,17 +1478,12 @@ int fib_table_delete(struct fib_table *tb, struct fib_config *cfg) | |||
1564 | rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id, | 1478 | rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id, |
1565 | &cfg->fc_nlinfo, 0); | 1479 | &cfg->fc_nlinfo, 0); |
1566 | 1480 | ||
1567 | hlist_del_rcu(&fa->fa_list); | 1481 | fib_remove_alias(l, fa); |
1568 | 1482 | ||
1569 | if (!plen) | 1483 | if (!plen) |
1570 | tb->tb_num_default--; | 1484 | tb->tb_num_default--; |
1571 | 1485 | ||
1572 | if (hlist_empty(fa_head)) { | 1486 | if (hlist_empty(&l->leaf)) |
1573 | remove_leaf_info(l, li); | ||
1574 | free_leaf_info(li); | ||
1575 | } | ||
1576 | |||
1577 | if (hlist_empty(&l->list)) | ||
1578 | trie_leaf_remove(t, l); | 1487 | trie_leaf_remove(t, l); |
1579 | 1488 | ||
1580 | if (fa->fa_state & FA_S_ACCESSED) | 1489 | if (fa->fa_state & FA_S_ACCESSED) |
@@ -1585,13 +1494,14 @@ int fib_table_delete(struct fib_table *tb, struct fib_config *cfg) | |||
1585 | return 0; | 1494 | return 0; |
1586 | } | 1495 | } |
1587 | 1496 | ||
1588 | static int trie_flush_list(struct hlist_head *head) | 1497 | static int trie_flush_leaf(struct tnode *l) |
1589 | { | 1498 | { |
1590 | struct hlist_node *tmp; | 1499 | struct hlist_node *tmp; |
1500 | unsigned char slen = 0; | ||
1591 | struct fib_alias *fa; | 1501 | struct fib_alias *fa; |
1592 | int found = 0; | 1502 | int found = 0; |
1593 | 1503 | ||
1594 | hlist_for_each_entry_safe(fa, tmp, head, fa_list) { | 1504 | hlist_for_each_entry_safe(fa, tmp, &l->leaf, fa_list) { |
1595 | struct fib_info *fi = fa->fa_info; | 1505 | struct fib_info *fi = fa->fa_info; |
1596 | 1506 | ||
1597 | if (fi && (fi->fib_flags & RTNH_F_DEAD)) { | 1507 | if (fi && (fi->fib_flags & RTNH_F_DEAD)) { |
@@ -1599,28 +1509,11 @@ static int trie_flush_list(struct hlist_head *head) | |||
1599 | fib_release_info(fa->fa_info); | 1509 | fib_release_info(fa->fa_info); |
1600 | alias_free_mem_rcu(fa); | 1510 | alias_free_mem_rcu(fa); |
1601 | found++; | 1511 | found++; |
1602 | } | ||
1603 | } | ||
1604 | return found; | ||
1605 | } | ||
1606 | |||
1607 | static int trie_flush_leaf(struct tnode *l) | ||
1608 | { | ||
1609 | int found = 0; | ||
1610 | struct hlist_node *tmp; | ||
1611 | struct leaf_info *li; | ||
1612 | unsigned char slen = 0; | ||
1613 | |||
1614 | hlist_for_each_entry_safe(li, tmp, &l->list, hlist) { | ||
1615 | found += trie_flush_list(&li->falh); | ||
1616 | 1512 | ||
1617 | if (hlist_empty(&li->falh)) { | ||
1618 | hlist_del_rcu(&li->hlist); | ||
1619 | free_leaf_info(li); | ||
1620 | continue; | 1513 | continue; |
1621 | } | 1514 | } |
1622 | 1515 | ||
1623 | slen = li->slen; | 1516 | slen = fa->fa_slen; |
1624 | } | 1517 | } |
1625 | 1518 | ||
1626 | l->slen = slen; | 1519 | l->slen = slen; |
@@ -1628,8 +1521,7 @@ static int trie_flush_leaf(struct tnode *l) | |||
1628 | return found; | 1521 | return found; |
1629 | } | 1522 | } |
1630 | 1523 | ||
1631 | /* | 1524 | /* Scan for the next right leaf starting at node p->child[idx] |
1632 | * Scan for the next right leaf starting at node p->child[idx] | ||
1633 | * Since we have back pointer, no recursion necessary. | 1525 | * Since we have back pointer, no recursion necessary. |
1634 | */ | 1526 | */ |
1635 | static struct tnode *leaf_walk_rcu(struct tnode *p, struct tnode *c) | 1527 | static struct tnode *leaf_walk_rcu(struct tnode *p, struct tnode *c) |
@@ -1704,7 +1596,7 @@ int fib_table_flush(struct fib_table *tb) | |||
1704 | found += trie_flush_leaf(l); | 1596 | found += trie_flush_leaf(l); |
1705 | 1597 | ||
1706 | if (ll) { | 1598 | if (ll) { |
1707 | if (hlist_empty(&ll->list)) | 1599 | if (hlist_empty(&ll->leaf)) |
1708 | trie_leaf_remove(t, ll); | 1600 | trie_leaf_remove(t, ll); |
1709 | else | 1601 | else |
1710 | leaf_pull_suffix(ll); | 1602 | leaf_pull_suffix(ll); |
@@ -1714,7 +1606,7 @@ int fib_table_flush(struct fib_table *tb) | |||
1714 | } | 1606 | } |
1715 | 1607 | ||
1716 | if (ll) { | 1608 | if (ll) { |
1717 | if (hlist_empty(&ll->list)) | 1609 | if (hlist_empty(&ll->leaf)) |
1718 | trie_leaf_remove(t, ll); | 1610 | trie_leaf_remove(t, ll); |
1719 | else | 1611 | else |
1720 | leaf_pull_suffix(ll); | 1612 | leaf_pull_suffix(ll); |
@@ -1734,20 +1626,18 @@ void fib_free_table(struct fib_table *tb) | |||
1734 | kfree(tb); | 1626 | kfree(tb); |
1735 | } | 1627 | } |
1736 | 1628 | ||
1737 | static int fn_trie_dump_fa(t_key key, struct hlist_head *fah, | 1629 | static int fn_trie_dump_leaf(struct tnode *l, struct fib_table *tb, |
1738 | struct fib_table *tb, | 1630 | struct sk_buff *skb, struct netlink_callback *cb) |
1739 | struct sk_buff *skb, struct netlink_callback *cb) | ||
1740 | { | 1631 | { |
1741 | int i, s_i; | 1632 | __be32 xkey = htonl(l->key); |
1742 | struct fib_alias *fa; | 1633 | struct fib_alias *fa; |
1743 | __be32 xkey = htonl(key); | 1634 | int i, s_i; |
1744 | 1635 | ||
1745 | s_i = cb->args[5]; | 1636 | s_i = cb->args[4]; |
1746 | i = 0; | 1637 | i = 0; |
1747 | 1638 | ||
1748 | /* rcu_read_lock is hold by caller */ | 1639 | /* rcu_read_lock is hold by caller */ |
1749 | 1640 | hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) { | |
1750 | hlist_for_each_entry_rcu(fa, fah, fa_list) { | ||
1751 | if (i < s_i) { | 1641 | if (i < s_i) { |
1752 | i++; | 1642 | i++; |
1753 | continue; | 1643 | continue; |
@@ -1762,38 +1652,6 @@ static int fn_trie_dump_fa(t_key key, struct hlist_head *fah, | |||
1762 | KEYLENGTH - fa->fa_slen, | 1652 | KEYLENGTH - fa->fa_slen, |
1763 | fa->fa_tos, | 1653 | fa->fa_tos, |
1764 | fa->fa_info, NLM_F_MULTI) < 0) { | 1654 | fa->fa_info, NLM_F_MULTI) < 0) { |
1765 | cb->args[5] = i; | ||
1766 | return -1; | ||
1767 | } | ||
1768 | i++; | ||
1769 | } | ||
1770 | cb->args[5] = i; | ||
1771 | return skb->len; | ||
1772 | } | ||
1773 | |||
1774 | static int fn_trie_dump_leaf(struct tnode *l, struct fib_table *tb, | ||
1775 | struct sk_buff *skb, struct netlink_callback *cb) | ||
1776 | { | ||
1777 | struct leaf_info *li; | ||
1778 | int i, s_i; | ||
1779 | |||
1780 | s_i = cb->args[4]; | ||
1781 | i = 0; | ||
1782 | |||
1783 | /* rcu_read_lock is hold by caller */ | ||
1784 | hlist_for_each_entry_rcu(li, &l->list, hlist) { | ||
1785 | if (i < s_i) { | ||
1786 | i++; | ||
1787 | continue; | ||
1788 | } | ||
1789 | |||
1790 | if (i > s_i) | ||
1791 | cb->args[5] = 0; | ||
1792 | |||
1793 | if (hlist_empty(&li->falh)) | ||
1794 | continue; | ||
1795 | |||
1796 | if (fn_trie_dump_fa(l->key, &li->falh, tb, skb, cb) < 0) { | ||
1797 | cb->args[4] = i; | 1655 | cb->args[4] = i; |
1798 | return -1; | 1656 | return -1; |
1799 | } | 1657 | } |
@@ -1853,8 +1711,7 @@ void __init fib_trie_init(void) | |||
1853 | 0, SLAB_PANIC, NULL); | 1711 | 0, SLAB_PANIC, NULL); |
1854 | 1712 | ||
1855 | trie_leaf_kmem = kmem_cache_create("ip_fib_trie", | 1713 | trie_leaf_kmem = kmem_cache_create("ip_fib_trie", |
1856 | max(sizeof(struct tnode), | 1714 | sizeof(struct tnode), |
1857 | sizeof(struct leaf_info)), | ||
1858 | 0, SLAB_PANIC, NULL); | 1715 | 0, SLAB_PANIC, NULL); |
1859 | } | 1716 | } |
1860 | 1717 | ||
@@ -1976,14 +1833,14 @@ static void trie_collect_stats(struct trie *t, struct trie_stat *s) | |||
1976 | rcu_read_lock(); | 1833 | rcu_read_lock(); |
1977 | for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) { | 1834 | for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) { |
1978 | if (IS_LEAF(n)) { | 1835 | if (IS_LEAF(n)) { |
1979 | struct leaf_info *li; | 1836 | struct fib_alias *fa; |
1980 | 1837 | ||
1981 | s->leaves++; | 1838 | s->leaves++; |
1982 | s->totdepth += iter.depth; | 1839 | s->totdepth += iter.depth; |
1983 | if (iter.depth > s->maxdepth) | 1840 | if (iter.depth > s->maxdepth) |
1984 | s->maxdepth = iter.depth; | 1841 | s->maxdepth = iter.depth; |
1985 | 1842 | ||
1986 | hlist_for_each_entry_rcu(li, &n->list, hlist) | 1843 | hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) |
1987 | ++s->prefixes; | 1844 | ++s->prefixes; |
1988 | } else { | 1845 | } else { |
1989 | s->tnodes++; | 1846 | s->tnodes++; |
@@ -2015,7 +1872,7 @@ static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat) | |||
2015 | bytes = sizeof(struct tnode) * stat->leaves; | 1872 | bytes = sizeof(struct tnode) * stat->leaves; |
2016 | 1873 | ||
2017 | seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes); | 1874 | seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes); |
2018 | bytes += sizeof(struct leaf_info) * stat->prefixes; | 1875 | bytes += sizeof(struct fib_alias) * stat->prefixes; |
2019 | 1876 | ||
2020 | seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes); | 1877 | seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes); |
2021 | bytes += sizeof(struct tnode) * stat->tnodes; | 1878 | bytes += sizeof(struct tnode) * stat->tnodes; |
@@ -2266,29 +2123,25 @@ static int fib_trie_seq_show(struct seq_file *seq, void *v) | |||
2266 | &prf, KEYLENGTH - n->pos - n->bits, n->bits, | 2123 | &prf, KEYLENGTH - n->pos - n->bits, n->bits, |
2267 | n->full_children, n->empty_children); | 2124 | n->full_children, n->empty_children); |
2268 | } else { | 2125 | } else { |
2269 | struct leaf_info *li; | ||
2270 | __be32 val = htonl(n->key); | 2126 | __be32 val = htonl(n->key); |
2127 | struct fib_alias *fa; | ||
2271 | 2128 | ||
2272 | seq_indent(seq, iter->depth); | 2129 | seq_indent(seq, iter->depth); |
2273 | seq_printf(seq, " |-- %pI4\n", &val); | 2130 | seq_printf(seq, " |-- %pI4\n", &val); |
2274 | 2131 | ||
2275 | hlist_for_each_entry_rcu(li, &n->list, hlist) { | 2132 | hlist_for_each_entry_rcu(fa, &n->leaf, fa_list) { |
2276 | struct fib_alias *fa; | 2133 | char buf1[32], buf2[32]; |
2277 | 2134 | ||
2278 | hlist_for_each_entry_rcu(fa, &li->falh, fa_list) { | 2135 | seq_indent(seq, iter->depth + 1); |
2279 | char buf1[32], buf2[32]; | 2136 | seq_printf(seq, " /%zu %s %s", |
2280 | 2137 | KEYLENGTH - fa->fa_slen, | |
2281 | seq_indent(seq, iter->depth+1); | 2138 | rtn_scope(buf1, sizeof(buf1), |
2282 | seq_printf(seq, " /%zu %s %s", | 2139 | fa->fa_info->fib_scope), |
2283 | KEYLENGTH - fa->fa_slen, | 2140 | rtn_type(buf2, sizeof(buf2), |
2284 | rtn_scope(buf1, sizeof(buf1), | 2141 | fa->fa_type)); |
2285 | fa->fa_info->fib_scope), | 2142 | if (fa->fa_tos) |
2286 | rtn_type(buf2, sizeof(buf2), | 2143 | seq_printf(seq, " tos=%d", fa->fa_tos); |
2287 | fa->fa_type)); | 2144 | seq_putc(seq, '\n'); |
2288 | if (fa->fa_tos) | ||
2289 | seq_printf(seq, " tos=%d", fa->fa_tos); | ||
2290 | seq_putc(seq, '\n'); | ||
2291 | } | ||
2292 | } | 2145 | } |
2293 | } | 2146 | } |
2294 | 2147 | ||
@@ -2416,8 +2269,8 @@ static unsigned int fib_flag_trans(int type, __be32 mask, const struct fib_info | |||
2416 | */ | 2269 | */ |
2417 | static int fib_route_seq_show(struct seq_file *seq, void *v) | 2270 | static int fib_route_seq_show(struct seq_file *seq, void *v) |
2418 | { | 2271 | { |
2272 | struct fib_alias *fa; | ||
2419 | struct tnode *l = v; | 2273 | struct tnode *l = v; |
2420 | struct leaf_info *li; | ||
2421 | __be32 prefix; | 2274 | __be32 prefix; |
2422 | 2275 | ||
2423 | if (v == SEQ_START_TOKEN) { | 2276 | if (v == SEQ_START_TOKEN) { |
@@ -2429,42 +2282,38 @@ static int fib_route_seq_show(struct seq_file *seq, void *v) | |||
2429 | 2282 | ||
2430 | prefix = htonl(l->key); | 2283 | prefix = htonl(l->key); |
2431 | 2284 | ||
2432 | hlist_for_each_entry_rcu(li, &l->list, hlist) { | 2285 | hlist_for_each_entry_rcu(fa, &l->leaf, fa_list) { |
2433 | struct fib_alias *fa; | 2286 | const struct fib_info *fi = fa->fa_info; |
2287 | __be32 mask = inet_make_mask(KEYLENGTH - fa->fa_slen); | ||
2288 | unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi); | ||
2434 | 2289 | ||
2435 | hlist_for_each_entry_rcu(fa, &li->falh, fa_list) { | 2290 | if ((fa->fa_type == RTN_BROADCAST) || |
2436 | const struct fib_info *fi = fa->fa_info; | 2291 | (fa->fa_type == RTN_MULTICAST)) |
2437 | __be32 mask = inet_make_mask(KEYLENGTH - fa->fa_slen); | 2292 | continue; |
2438 | unsigned int flags = fib_flag_trans(fa->fa_type, mask, fi); | ||
2439 | |||
2440 | if (fa->fa_type == RTN_BROADCAST | ||
2441 | || fa->fa_type == RTN_MULTICAST) | ||
2442 | continue; | ||
2443 | 2293 | ||
2444 | seq_setwidth(seq, 127); | 2294 | seq_setwidth(seq, 127); |
2445 | 2295 | ||
2446 | if (fi) | 2296 | if (fi) |
2447 | seq_printf(seq, | 2297 | seq_printf(seq, |
2448 | "%s\t%08X\t%08X\t%04X\t%d\t%u\t" | 2298 | "%s\t%08X\t%08X\t%04X\t%d\t%u\t" |
2449 | "%d\t%08X\t%d\t%u\t%u", | 2299 | "%d\t%08X\t%d\t%u\t%u", |
2450 | fi->fib_dev ? fi->fib_dev->name : "*", | 2300 | fi->fib_dev ? fi->fib_dev->name : "*", |
2451 | prefix, | 2301 | prefix, |
2452 | fi->fib_nh->nh_gw, flags, 0, 0, | 2302 | fi->fib_nh->nh_gw, flags, 0, 0, |
2453 | fi->fib_priority, | 2303 | fi->fib_priority, |
2454 | mask, | 2304 | mask, |
2455 | (fi->fib_advmss ? | 2305 | (fi->fib_advmss ? |
2456 | fi->fib_advmss + 40 : 0), | 2306 | fi->fib_advmss + 40 : 0), |
2457 | fi->fib_window, | 2307 | fi->fib_window, |
2458 | fi->fib_rtt >> 3); | 2308 | fi->fib_rtt >> 3); |
2459 | else | 2309 | else |
2460 | seq_printf(seq, | 2310 | seq_printf(seq, |
2461 | "*\t%08X\t%08X\t%04X\t%d\t%u\t" | 2311 | "*\t%08X\t%08X\t%04X\t%d\t%u\t" |
2462 | "%d\t%08X\t%d\t%u\t%u", | 2312 | "%d\t%08X\t%d\t%u\t%u", |
2463 | prefix, 0, flags, 0, 0, 0, | 2313 | prefix, 0, flags, 0, 0, 0, |
2464 | mask, 0, 0, 0); | 2314 | mask, 0, 0, 0); |
2465 | 2315 | ||
2466 | seq_pad(seq, '\n'); | 2316 | seq_pad(seq, '\n'); |
2467 | } | ||
2468 | } | 2317 | } |
2469 | 2318 | ||
2470 | return 0; | 2319 | return 0; |