fib_trie.c 58 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515
  1. /*
  2. * This program is free software; you can redistribute it and/or
  3. * modify it under the terms of the GNU General Public License
  4. * as published by the Free Software Foundation; either version
  5. * 2 of the License, or (at your option) any later version.
  6. *
  7. * Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
  8. * & Swedish University of Agricultural Sciences.
  9. *
  10. * Jens Laas <jens.laas@data.slu.se> Swedish University of
  11. * Agricultural Sciences.
  12. *
  13. * Hans Liss <hans.liss@its.uu.se> Uppsala Universitet
  14. *
  15. * This work is based on the LPC-trie which is originally descibed in:
  16. *
  17. * An experimental study of compression methods for dynamic tries
  18. * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
  19. * http://www.nada.kth.se/~snilsson/public/papers/dyntrie2/
  20. *
  21. *
  22. * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
  23. * IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999
  24. *
  25. * Version: $Id: fib_trie.c,v 1.3 2005/06/08 14:20:01 robert Exp $
  26. *
  27. *
  28. * Code from fib_hash has been reused which includes the following header:
  29. *
  30. *
  31. * INET An implementation of the TCP/IP protocol suite for the LINUX
  32. * operating system. INET is implemented using the BSD Socket
  33. * interface as the means of communication with the user level.
  34. *
  35. * IPv4 FIB: lookup engine and maintenance routines.
  36. *
  37. *
  38. * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
  39. *
  40. * This program is free software; you can redistribute it and/or
  41. * modify it under the terms of the GNU General Public License
  42. * as published by the Free Software Foundation; either version
  43. * 2 of the License, or (at your option) any later version.
  44. *
  45. * Substantial contributions to this work comes from:
  46. *
  47. * David S. Miller, <davem@davemloft.net>
  48. * Stephen Hemminger <shemminger@osdl.org>
  49. * Paul E. McKenney <paulmck@us.ibm.com>
  50. * Patrick McHardy <kaber@trash.net>
  51. */
  52. #define VERSION "0.404"
  53. #include <linux/config.h>
  54. #include <asm/uaccess.h>
  55. #include <asm/system.h>
  56. #include <asm/bitops.h>
  57. #include <linux/types.h>
  58. #include <linux/kernel.h>
  59. #include <linux/sched.h>
  60. #include <linux/mm.h>
  61. #include <linux/string.h>
  62. #include <linux/socket.h>
  63. #include <linux/sockios.h>
  64. #include <linux/errno.h>
  65. #include <linux/in.h>
  66. #include <linux/inet.h>
  67. #include <linux/inetdevice.h>
  68. #include <linux/netdevice.h>
  69. #include <linux/if_arp.h>
  70. #include <linux/proc_fs.h>
  71. #include <linux/rcupdate.h>
  72. #include <linux/skbuff.h>
  73. #include <linux/netlink.h>
  74. #include <linux/init.h>
  75. #include <linux/list.h>
  76. #include <net/ip.h>
  77. #include <net/protocol.h>
  78. #include <net/route.h>
  79. #include <net/tcp.h>
  80. #include <net/sock.h>
  81. #include <net/ip_fib.h>
  82. #include "fib_lookup.h"
  83. #undef CONFIG_IP_FIB_TRIE_STATS
  84. #define MAX_CHILDS 16384
  85. #define KEYLENGTH (8*sizeof(t_key))
  86. #define MASK_PFX(k, l) (((l)==0)?0:(k >> (KEYLENGTH-l)) << (KEYLENGTH-l))
  87. #define TKEY_GET_MASK(offset, bits) (((bits)==0)?0:((t_key)(-1) << (KEYLENGTH - bits) >> offset))
  88. typedef unsigned int t_key;
  89. #define T_TNODE 0
  90. #define T_LEAF 1
  91. #define NODE_TYPE_MASK 0x1UL
  92. #define NODE_PARENT(node) \
  93. ((struct tnode *)rcu_dereference(((node)->parent & ~NODE_TYPE_MASK)))
  94. #define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
  95. #define NODE_SET_PARENT(node, ptr) \
  96. rcu_assign_pointer((node)->parent, \
  97. ((unsigned long)(ptr)) | NODE_TYPE(node))
  98. #define IS_TNODE(n) (!(n->parent & T_LEAF))
  99. #define IS_LEAF(n) (n->parent & T_LEAF)
  100. struct node {
  101. t_key key;
  102. unsigned long parent;
  103. };
  104. struct leaf {
  105. t_key key;
  106. unsigned long parent;
  107. struct hlist_head list;
  108. struct rcu_head rcu;
  109. };
  110. struct leaf_info {
  111. struct hlist_node hlist;
  112. struct rcu_head rcu;
  113. int plen;
  114. struct list_head falh;
  115. };
  116. struct tnode {
  117. t_key key;
  118. unsigned long parent;
  119. unsigned short pos:5; /* 2log(KEYLENGTH) bits needed */
  120. unsigned short bits:5; /* 2log(KEYLENGTH) bits needed */
  121. unsigned short full_children; /* KEYLENGTH bits needed */
  122. unsigned short empty_children; /* KEYLENGTH bits needed */
  123. struct rcu_head rcu;
  124. struct node *child[0];
  125. };
  126. #ifdef CONFIG_IP_FIB_TRIE_STATS
  127. struct trie_use_stats {
  128. unsigned int gets;
  129. unsigned int backtrack;
  130. unsigned int semantic_match_passed;
  131. unsigned int semantic_match_miss;
  132. unsigned int null_node_hit;
  133. unsigned int resize_node_skipped;
  134. };
  135. #endif
  136. struct trie_stat {
  137. unsigned int totdepth;
  138. unsigned int maxdepth;
  139. unsigned int tnodes;
  140. unsigned int leaves;
  141. unsigned int nullpointers;
  142. unsigned int nodesizes[MAX_CHILDS];
  143. };
  144. struct trie {
  145. struct node *trie;
  146. #ifdef CONFIG_IP_FIB_TRIE_STATS
  147. struct trie_use_stats stats;
  148. #endif
  149. int size;
  150. unsigned int revision;
  151. };
  152. static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
  153. static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull);
  154. static struct node *resize(struct trie *t, struct tnode *tn);
  155. static struct tnode *inflate(struct trie *t, struct tnode *tn);
  156. static struct tnode *halve(struct trie *t, struct tnode *tn);
  157. static void tnode_free(struct tnode *tn);
  158. static kmem_cache_t *fn_alias_kmem __read_mostly;
  159. static struct trie *trie_local = NULL, *trie_main = NULL;
  160. /* rcu_read_lock needs to be hold by caller from readside */
  161. static inline struct node *tnode_get_child(struct tnode *tn, int i)
  162. {
  163. BUG_ON(i >= 1 << tn->bits);
  164. return rcu_dereference(tn->child[i]);
  165. }
  166. static inline int tnode_child_length(const struct tnode *tn)
  167. {
  168. return 1 << tn->bits;
  169. }
  170. static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
  171. {
  172. if (offset < KEYLENGTH)
  173. return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
  174. else
  175. return 0;
  176. }
  177. static inline int tkey_equals(t_key a, t_key b)
  178. {
  179. return a == b;
  180. }
  181. static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
  182. {
  183. if (bits == 0 || offset >= KEYLENGTH)
  184. return 1;
  185. bits = bits > KEYLENGTH ? KEYLENGTH : bits;
  186. return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
  187. }
  188. static inline int tkey_mismatch(t_key a, int offset, t_key b)
  189. {
  190. t_key diff = a ^ b;
  191. int i = offset;
  192. if (!diff)
  193. return 0;
  194. while ((diff << i) >> (KEYLENGTH-1) == 0)
  195. i++;
  196. return i;
  197. }
  198. /*
  199. To understand this stuff, an understanding of keys and all their bits is
  200. necessary. Every node in the trie has a key associated with it, but not
  201. all of the bits in that key are significant.
  202. Consider a node 'n' and its parent 'tp'.
  203. If n is a leaf, every bit in its key is significant. Its presence is
  204. necessitated by path compression, since during a tree traversal (when
  205. searching for a leaf - unless we are doing an insertion) we will completely
  206. ignore all skipped bits we encounter. Thus we need to verify, at the end of
  207. a potentially successful search, that we have indeed been walking the
  208. correct key path.
  209. Note that we can never "miss" the correct key in the tree if present by
  210. following the wrong path. Path compression ensures that segments of the key
  211. that are the same for all keys with a given prefix are skipped, but the
  212. skipped part *is* identical for each node in the subtrie below the skipped
  213. bit! trie_insert() in this implementation takes care of that - note the
  214. call to tkey_sub_equals() in trie_insert().
  215. if n is an internal node - a 'tnode' here, the various parts of its key
  216. have many different meanings.
  217. Example:
  218. _________________________________________________________________
  219. | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
  220. -----------------------------------------------------------------
  221. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
  222. _________________________________________________________________
  223. | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
  224. -----------------------------------------------------------------
  225. 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
  226. tp->pos = 7
  227. tp->bits = 3
  228. n->pos = 15
  229. n->bits = 4
  230. First, let's just ignore the bits that come before the parent tp, that is
  231. the bits from 0 to (tp->pos-1). They are *known* but at this point we do
  232. not use them for anything.
  233. The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
  234. index into the parent's child array. That is, they will be used to find
  235. 'n' among tp's children.
  236. The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
  237. for the node n.
  238. All the bits we have seen so far are significant to the node n. The rest
  239. of the bits are really not needed or indeed known in n->key.
  240. The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
  241. n's child array, and will of course be different for each child.
  242. The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
  243. at this point.
  244. */
  245. static inline void check_tnode(const struct tnode *tn)
  246. {
  247. WARN_ON(tn && tn->pos+tn->bits > 32);
  248. }
  249. static int halve_threshold = 25;
  250. static int inflate_threshold = 50;
  251. static int halve_threshold_root = 15;
  252. static int inflate_threshold_root = 25;
  253. static void __alias_free_mem(struct rcu_head *head)
  254. {
  255. struct fib_alias *fa = container_of(head, struct fib_alias, rcu);
  256. kmem_cache_free(fn_alias_kmem, fa);
  257. }
  258. static inline void alias_free_mem_rcu(struct fib_alias *fa)
  259. {
  260. call_rcu(&fa->rcu, __alias_free_mem);
  261. }
  262. static void __leaf_free_rcu(struct rcu_head *head)
  263. {
  264. kfree(container_of(head, struct leaf, rcu));
  265. }
  266. static inline void free_leaf(struct leaf *leaf)
  267. {
  268. call_rcu(&leaf->rcu, __leaf_free_rcu);
  269. }
  270. static void __leaf_info_free_rcu(struct rcu_head *head)
  271. {
  272. kfree(container_of(head, struct leaf_info, rcu));
  273. }
  274. static inline void free_leaf_info(struct leaf_info *leaf)
  275. {
  276. call_rcu(&leaf->rcu, __leaf_info_free_rcu);
  277. }
  278. static struct tnode *tnode_alloc(unsigned int size)
  279. {
  280. struct page *pages;
  281. if (size <= PAGE_SIZE)
  282. return kcalloc(size, 1, GFP_KERNEL);
  283. pages = alloc_pages(GFP_KERNEL|__GFP_ZERO, get_order(size));
  284. if (!pages)
  285. return NULL;
  286. return page_address(pages);
  287. }
  288. static void __tnode_free_rcu(struct rcu_head *head)
  289. {
  290. struct tnode *tn = container_of(head, struct tnode, rcu);
  291. unsigned int size = sizeof(struct tnode) +
  292. (1 << tn->bits) * sizeof(struct node *);
  293. if (size <= PAGE_SIZE)
  294. kfree(tn);
  295. else
  296. free_pages((unsigned long)tn, get_order(size));
  297. }
  298. static inline void tnode_free(struct tnode *tn)
  299. {
  300. call_rcu(&tn->rcu, __tnode_free_rcu);
  301. }
  302. static struct leaf *leaf_new(void)
  303. {
  304. struct leaf *l = kmalloc(sizeof(struct leaf), GFP_KERNEL);
  305. if (l) {
  306. l->parent = T_LEAF;
  307. INIT_HLIST_HEAD(&l->list);
  308. }
  309. return l;
  310. }
  311. static struct leaf_info *leaf_info_new(int plen)
  312. {
  313. struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
  314. if (li) {
  315. li->plen = plen;
  316. INIT_LIST_HEAD(&li->falh);
  317. }
  318. return li;
  319. }
  320. static struct tnode* tnode_new(t_key key, int pos, int bits)
  321. {
  322. int nchildren = 1<<bits;
  323. int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *);
  324. struct tnode *tn = tnode_alloc(sz);
  325. if (tn) {
  326. memset(tn, 0, sz);
  327. tn->parent = T_TNODE;
  328. tn->pos = pos;
  329. tn->bits = bits;
  330. tn->key = key;
  331. tn->full_children = 0;
  332. tn->empty_children = 1<<bits;
  333. }
  334. pr_debug("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode),
  335. (unsigned int) (sizeof(struct node) * 1<<bits));
  336. return tn;
  337. }
  338. /*
  339. * Check whether a tnode 'n' is "full", i.e. it is an internal node
  340. * and no bits are skipped. See discussion in dyntree paper p. 6
  341. */
  342. static inline int tnode_full(const struct tnode *tn, const struct node *n)
  343. {
  344. if (n == NULL || IS_LEAF(n))
  345. return 0;
  346. return ((struct tnode *) n)->pos == tn->pos + tn->bits;
  347. }
  348. static inline void put_child(struct trie *t, struct tnode *tn, int i, struct node *n)
  349. {
  350. tnode_put_child_reorg(tn, i, n, -1);
  351. }
  352. /*
  353. * Add a child at position i overwriting the old value.
  354. * Update the value of full_children and empty_children.
  355. */
  356. static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull)
  357. {
  358. struct node *chi = tn->child[i];
  359. int isfull;
  360. BUG_ON(i >= 1<<tn->bits);
  361. /* update emptyChildren */
  362. if (n == NULL && chi != NULL)
  363. tn->empty_children++;
  364. else if (n != NULL && chi == NULL)
  365. tn->empty_children--;
  366. /* update fullChildren */
  367. if (wasfull == -1)
  368. wasfull = tnode_full(tn, chi);
  369. isfull = tnode_full(tn, n);
  370. if (wasfull && !isfull)
  371. tn->full_children--;
  372. else if (!wasfull && isfull)
  373. tn->full_children++;
  374. if (n)
  375. NODE_SET_PARENT(n, tn);
  376. rcu_assign_pointer(tn->child[i], n);
  377. }
  378. static struct node *resize(struct trie *t, struct tnode *tn)
  379. {
  380. int i;
  381. int err = 0;
  382. struct tnode *old_tn;
  383. int inflate_threshold_use;
  384. int halve_threshold_use;
  385. if (!tn)
  386. return NULL;
  387. pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
  388. tn, inflate_threshold, halve_threshold);
  389. /* No children */
  390. if (tn->empty_children == tnode_child_length(tn)) {
  391. tnode_free(tn);
  392. return NULL;
  393. }
  394. /* One child */
  395. if (tn->empty_children == tnode_child_length(tn) - 1)
  396. for (i = 0; i < tnode_child_length(tn); i++) {
  397. struct node *n;
  398. n = tn->child[i];
  399. if (!n)
  400. continue;
  401. /* compress one level */
  402. NODE_SET_PARENT(n, NULL);
  403. tnode_free(tn);
  404. return n;
  405. }
  406. /*
  407. * Double as long as the resulting node has a number of
  408. * nonempty nodes that are above the threshold.
  409. */
  410. /*
  411. * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
  412. * the Helsinki University of Technology and Matti Tikkanen of Nokia
  413. * Telecommunications, page 6:
  414. * "A node is doubled if the ratio of non-empty children to all
  415. * children in the *doubled* node is at least 'high'."
  416. *
  417. * 'high' in this instance is the variable 'inflate_threshold'. It
  418. * is expressed as a percentage, so we multiply it with
  419. * tnode_child_length() and instead of multiplying by 2 (since the
  420. * child array will be doubled by inflate()) and multiplying
  421. * the left-hand side by 100 (to handle the percentage thing) we
  422. * multiply the left-hand side by 50.
  423. *
  424. * The left-hand side may look a bit weird: tnode_child_length(tn)
  425. * - tn->empty_children is of course the number of non-null children
  426. * in the current node. tn->full_children is the number of "full"
  427. * children, that is non-null tnodes with a skip value of 0.
  428. * All of those will be doubled in the resulting inflated tnode, so
  429. * we just count them one extra time here.
  430. *
  431. * A clearer way to write this would be:
  432. *
  433. * to_be_doubled = tn->full_children;
  434. * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
  435. * tn->full_children;
  436. *
  437. * new_child_length = tnode_child_length(tn) * 2;
  438. *
  439. * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
  440. * new_child_length;
  441. * if (new_fill_factor >= inflate_threshold)
  442. *
  443. * ...and so on, tho it would mess up the while () loop.
  444. *
  445. * anyway,
  446. * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
  447. * inflate_threshold
  448. *
  449. * avoid a division:
  450. * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
  451. * inflate_threshold * new_child_length
  452. *
  453. * expand not_to_be_doubled and to_be_doubled, and shorten:
  454. * 100 * (tnode_child_length(tn) - tn->empty_children +
  455. * tn->full_children) >= inflate_threshold * new_child_length
  456. *
  457. * expand new_child_length:
  458. * 100 * (tnode_child_length(tn) - tn->empty_children +
  459. * tn->full_children) >=
  460. * inflate_threshold * tnode_child_length(tn) * 2
  461. *
  462. * shorten again:
  463. * 50 * (tn->full_children + tnode_child_length(tn) -
  464. * tn->empty_children) >= inflate_threshold *
  465. * tnode_child_length(tn)
  466. *
  467. */
  468. check_tnode(tn);
  469. /* Keep root node larger */
  470. if(!tn->parent)
  471. inflate_threshold_use = inflate_threshold_root;
  472. else
  473. inflate_threshold_use = inflate_threshold;
  474. err = 0;
  475. while ((tn->full_children > 0 &&
  476. 50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >=
  477. inflate_threshold_use * tnode_child_length(tn))) {
  478. old_tn = tn;
  479. tn = inflate(t, tn);
  480. if (IS_ERR(tn)) {
  481. tn = old_tn;
  482. #ifdef CONFIG_IP_FIB_TRIE_STATS
  483. t->stats.resize_node_skipped++;
  484. #endif
  485. break;
  486. }
  487. }
  488. check_tnode(tn);
  489. /*
  490. * Halve as long as the number of empty children in this
  491. * node is above threshold.
  492. */
  493. /* Keep root node larger */
  494. if(!tn->parent)
  495. halve_threshold_use = halve_threshold_root;
  496. else
  497. halve_threshold_use = halve_threshold;
  498. err = 0;
  499. while (tn->bits > 1 &&
  500. 100 * (tnode_child_length(tn) - tn->empty_children) <
  501. halve_threshold_use * tnode_child_length(tn)) {
  502. old_tn = tn;
  503. tn = halve(t, tn);
  504. if (IS_ERR(tn)) {
  505. tn = old_tn;
  506. #ifdef CONFIG_IP_FIB_TRIE_STATS
  507. t->stats.resize_node_skipped++;
  508. #endif
  509. break;
  510. }
  511. }
  512. /* Only one child remains */
  513. if (tn->empty_children == tnode_child_length(tn) - 1)
  514. for (i = 0; i < tnode_child_length(tn); i++) {
  515. struct node *n;
  516. n = tn->child[i];
  517. if (!n)
  518. continue;
  519. /* compress one level */
  520. NODE_SET_PARENT(n, NULL);
  521. tnode_free(tn);
  522. return n;
  523. }
  524. return (struct node *) tn;
  525. }
  526. static struct tnode *inflate(struct trie *t, struct tnode *tn)
  527. {
  528. struct tnode *inode;
  529. struct tnode *oldtnode = tn;
  530. int olen = tnode_child_length(tn);
  531. int i;
  532. pr_debug("In inflate\n");
  533. tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
  534. if (!tn)
  535. return ERR_PTR(-ENOMEM);
  536. /*
  537. * Preallocate and store tnodes before the actual work so we
  538. * don't get into an inconsistent state if memory allocation
  539. * fails. In case of failure we return the oldnode and inflate
  540. * of tnode is ignored.
  541. */
  542. for (i = 0; i < olen; i++) {
  543. struct tnode *inode = (struct tnode *) tnode_get_child(oldtnode, i);
  544. if (inode &&
  545. IS_TNODE(inode) &&
  546. inode->pos == oldtnode->pos + oldtnode->bits &&
  547. inode->bits > 1) {
  548. struct tnode *left, *right;
  549. t_key m = TKEY_GET_MASK(inode->pos, 1);
  550. left = tnode_new(inode->key&(~m), inode->pos + 1,
  551. inode->bits - 1);
  552. if (!left)
  553. goto nomem;
  554. right = tnode_new(inode->key|m, inode->pos + 1,
  555. inode->bits - 1);
  556. if (!right) {
  557. tnode_free(left);
  558. goto nomem;
  559. }
  560. put_child(t, tn, 2*i, (struct node *) left);
  561. put_child(t, tn, 2*i+1, (struct node *) right);
  562. }
  563. }
  564. for (i = 0; i < olen; i++) {
  565. struct node *node = tnode_get_child(oldtnode, i);
  566. struct tnode *left, *right;
  567. int size, j;
  568. /* An empty child */
  569. if (node == NULL)
  570. continue;
  571. /* A leaf or an internal node with skipped bits */
  572. if (IS_LEAF(node) || ((struct tnode *) node)->pos >
  573. tn->pos + tn->bits - 1) {
  574. if (tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits,
  575. 1) == 0)
  576. put_child(t, tn, 2*i, node);
  577. else
  578. put_child(t, tn, 2*i+1, node);
  579. continue;
  580. }
  581. /* An internal node with two children */
  582. inode = (struct tnode *) node;
  583. if (inode->bits == 1) {
  584. put_child(t, tn, 2*i, inode->child[0]);
  585. put_child(t, tn, 2*i+1, inode->child[1]);
  586. tnode_free(inode);
  587. continue;
  588. }
  589. /* An internal node with more than two children */
  590. /* We will replace this node 'inode' with two new
  591. * ones, 'left' and 'right', each with half of the
  592. * original children. The two new nodes will have
  593. * a position one bit further down the key and this
  594. * means that the "significant" part of their keys
  595. * (see the discussion near the top of this file)
  596. * will differ by one bit, which will be "0" in
  597. * left's key and "1" in right's key. Since we are
  598. * moving the key position by one step, the bit that
  599. * we are moving away from - the bit at position
  600. * (inode->pos) - is the one that will differ between
  601. * left and right. So... we synthesize that bit in the
  602. * two new keys.
  603. * The mask 'm' below will be a single "one" bit at
  604. * the position (inode->pos)
  605. */
  606. /* Use the old key, but set the new significant
  607. * bit to zero.
  608. */
  609. left = (struct tnode *) tnode_get_child(tn, 2*i);
  610. put_child(t, tn, 2*i, NULL);
  611. BUG_ON(!left);
  612. right = (struct tnode *) tnode_get_child(tn, 2*i+1);
  613. put_child(t, tn, 2*i+1, NULL);
  614. BUG_ON(!right);
  615. size = tnode_child_length(left);
  616. for (j = 0; j < size; j++) {
  617. put_child(t, left, j, inode->child[j]);
  618. put_child(t, right, j, inode->child[j + size]);
  619. }
  620. put_child(t, tn, 2*i, resize(t, left));
  621. put_child(t, tn, 2*i+1, resize(t, right));
  622. tnode_free(inode);
  623. }
  624. tnode_free(oldtnode);
  625. return tn;
  626. nomem:
  627. {
  628. int size = tnode_child_length(tn);
  629. int j;
  630. for (j = 0; j < size; j++)
  631. if (tn->child[j])
  632. tnode_free((struct tnode *)tn->child[j]);
  633. tnode_free(tn);
  634. return ERR_PTR(-ENOMEM);
  635. }
  636. }
  637. static struct tnode *halve(struct trie *t, struct tnode *tn)
  638. {
  639. struct tnode *oldtnode = tn;
  640. struct node *left, *right;
  641. int i;
  642. int olen = tnode_child_length(tn);
  643. pr_debug("In halve\n");
  644. tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
  645. if (!tn)
  646. return ERR_PTR(-ENOMEM);
  647. /*
  648. * Preallocate and store tnodes before the actual work so we
  649. * don't get into an inconsistent state if memory allocation
  650. * fails. In case of failure we return the oldnode and halve
  651. * of tnode is ignored.
  652. */
  653. for (i = 0; i < olen; i += 2) {
  654. left = tnode_get_child(oldtnode, i);
  655. right = tnode_get_child(oldtnode, i+1);
  656. /* Two nonempty children */
  657. if (left && right) {
  658. struct tnode *newn;
  659. newn = tnode_new(left->key, tn->pos + tn->bits, 1);
  660. if (!newn)
  661. goto nomem;
  662. put_child(t, tn, i/2, (struct node *)newn);
  663. }
  664. }
  665. for (i = 0; i < olen; i += 2) {
  666. struct tnode *newBinNode;
  667. left = tnode_get_child(oldtnode, i);
  668. right = tnode_get_child(oldtnode, i+1);
  669. /* At least one of the children is empty */
  670. if (left == NULL) {
  671. if (right == NULL) /* Both are empty */
  672. continue;
  673. put_child(t, tn, i/2, right);
  674. continue;
  675. }
  676. if (right == NULL) {
  677. put_child(t, tn, i/2, left);
  678. continue;
  679. }
  680. /* Two nonempty children */
  681. newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
  682. put_child(t, tn, i/2, NULL);
  683. put_child(t, newBinNode, 0, left);
  684. put_child(t, newBinNode, 1, right);
  685. put_child(t, tn, i/2, resize(t, newBinNode));
  686. }
  687. tnode_free(oldtnode);
  688. return tn;
  689. nomem:
  690. {
  691. int size = tnode_child_length(tn);
  692. int j;
  693. for (j = 0; j < size; j++)
  694. if (tn->child[j])
  695. tnode_free((struct tnode *)tn->child[j]);
  696. tnode_free(tn);
  697. return ERR_PTR(-ENOMEM);
  698. }
  699. }
  700. static void trie_init(struct trie *t)
  701. {
  702. if (!t)
  703. return;
  704. t->size = 0;
  705. rcu_assign_pointer(t->trie, NULL);
  706. t->revision = 0;
  707. #ifdef CONFIG_IP_FIB_TRIE_STATS
  708. memset(&t->stats, 0, sizeof(struct trie_use_stats));
  709. #endif
  710. }
  711. /* readside must use rcu_read_lock currently dump routines
  712. via get_fa_head and dump */
  713. static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
  714. {
  715. struct hlist_head *head = &l->list;
  716. struct hlist_node *node;
  717. struct leaf_info *li;
  718. hlist_for_each_entry_rcu(li, node, head, hlist)
  719. if (li->plen == plen)
  720. return li;
  721. return NULL;
  722. }
  723. static inline struct list_head * get_fa_head(struct leaf *l, int plen)
  724. {
  725. struct leaf_info *li = find_leaf_info(l, plen);
  726. if (!li)
  727. return NULL;
  728. return &li->falh;
  729. }
  730. static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
  731. {
  732. struct leaf_info *li = NULL, *last = NULL;
  733. struct hlist_node *node;
  734. if (hlist_empty(head)) {
  735. hlist_add_head_rcu(&new->hlist, head);
  736. } else {
  737. hlist_for_each_entry(li, node, head, hlist) {
  738. if (new->plen > li->plen)
  739. break;
  740. last = li;
  741. }
  742. if (last)
  743. hlist_add_after_rcu(&last->hlist, &new->hlist);
  744. else
  745. hlist_add_before_rcu(&new->hlist, &li->hlist);
  746. }
  747. }
  748. /* rcu_read_lock needs to be hold by caller from readside */
  749. static struct leaf *
  750. fib_find_node(struct trie *t, u32 key)
  751. {
  752. int pos;
  753. struct tnode *tn;
  754. struct node *n;
  755. pos = 0;
  756. n = rcu_dereference(t->trie);
  757. while (n != NULL && NODE_TYPE(n) == T_TNODE) {
  758. tn = (struct tnode *) n;
  759. check_tnode(tn);
  760. if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
  761. pos = tn->pos + tn->bits;
  762. n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
  763. } else
  764. break;
  765. }
  766. /* Case we have found a leaf. Compare prefixes */
  767. if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
  768. return (struct leaf *)n;
  769. return NULL;
  770. }
  771. static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
  772. {
  773. int wasfull;
  774. t_key cindex, key;
  775. struct tnode *tp = NULL;
  776. key = tn->key;
  777. while (tn != NULL && NODE_PARENT(tn) != NULL) {
  778. tp = NODE_PARENT(tn);
  779. cindex = tkey_extract_bits(key, tp->pos, tp->bits);
  780. wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
  781. tn = (struct tnode *) resize (t, (struct tnode *)tn);
  782. tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull);
  783. if (!NODE_PARENT(tn))
  784. break;
  785. tn = NODE_PARENT(tn);
  786. }
  787. /* Handle last (top) tnode */
  788. if (IS_TNODE(tn))
  789. tn = (struct tnode*) resize(t, (struct tnode *)tn);
  790. return (struct node*) tn;
  791. }
  792. /* only used from updater-side */
  793. static struct list_head *
  794. fib_insert_node(struct trie *t, int *err, u32 key, int plen)
  795. {
  796. int pos, newpos;
  797. struct tnode *tp = NULL, *tn = NULL;
  798. struct node *n;
  799. struct leaf *l;
  800. int missbit;
  801. struct list_head *fa_head = NULL;
  802. struct leaf_info *li;
  803. t_key cindex;
  804. pos = 0;
  805. n = t->trie;
  806. /* If we point to NULL, stop. Either the tree is empty and we should
  807. * just put a new leaf in if, or we have reached an empty child slot,
  808. * and we should just put our new leaf in that.
  809. * If we point to a T_TNODE, check if it matches our key. Note that
  810. * a T_TNODE might be skipping any number of bits - its 'pos' need
  811. * not be the parent's 'pos'+'bits'!
  812. *
  813. * If it does match the current key, get pos/bits from it, extract
  814. * the index from our key, push the T_TNODE and walk the tree.
  815. *
  816. * If it doesn't, we have to replace it with a new T_TNODE.
  817. *
  818. * If we point to a T_LEAF, it might or might not have the same key
  819. * as we do. If it does, just change the value, update the T_LEAF's
  820. * value, and return it.
  821. * If it doesn't, we need to replace it with a T_TNODE.
  822. */
  823. while (n != NULL && NODE_TYPE(n) == T_TNODE) {
  824. tn = (struct tnode *) n;
  825. check_tnode(tn);
  826. if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
  827. tp = tn;
  828. pos = tn->pos + tn->bits;
  829. n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
  830. BUG_ON(n && NODE_PARENT(n) != tn);
  831. } else
  832. break;
  833. }
  834. /*
  835. * n ----> NULL, LEAF or TNODE
  836. *
  837. * tp is n's (parent) ----> NULL or TNODE
  838. */
  839. BUG_ON(tp && IS_LEAF(tp));
  840. /* Case 1: n is a leaf. Compare prefixes */
  841. if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
  842. struct leaf *l = (struct leaf *) n;
  843. li = leaf_info_new(plen);
  844. if (!li) {
  845. *err = -ENOMEM;
  846. goto err;
  847. }
  848. fa_head = &li->falh;
  849. insert_leaf_info(&l->list, li);
  850. goto done;
  851. }
  852. t->size++;
  853. l = leaf_new();
  854. if (!l) {
  855. *err = -ENOMEM;
  856. goto err;
  857. }
  858. l->key = key;
  859. li = leaf_info_new(plen);
  860. if (!li) {
  861. tnode_free((struct tnode *) l);
  862. *err = -ENOMEM;
  863. goto err;
  864. }
  865. fa_head = &li->falh;
  866. insert_leaf_info(&l->list, li);
  867. if (t->trie && n == NULL) {
  868. /* Case 2: n is NULL, and will just insert a new leaf */
  869. NODE_SET_PARENT(l, tp);
  870. cindex = tkey_extract_bits(key, tp->pos, tp->bits);
  871. put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
  872. } else {
  873. /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
  874. /*
  875. * Add a new tnode here
  876. * first tnode need some special handling
  877. */
  878. if (tp)
  879. pos = tp->pos+tp->bits;
  880. else
  881. pos = 0;
  882. if (n) {
  883. newpos = tkey_mismatch(key, pos, n->key);
  884. tn = tnode_new(n->key, newpos, 1);
  885. } else {
  886. newpos = 0;
  887. tn = tnode_new(key, newpos, 1); /* First tnode */
  888. }
  889. if (!tn) {
  890. free_leaf_info(li);
  891. tnode_free((struct tnode *) l);
  892. *err = -ENOMEM;
  893. goto err;
  894. }
  895. NODE_SET_PARENT(tn, tp);
  896. missbit = tkey_extract_bits(key, newpos, 1);
  897. put_child(t, tn, missbit, (struct node *)l);
  898. put_child(t, tn, 1-missbit, n);
  899. if (tp) {
  900. cindex = tkey_extract_bits(key, tp->pos, tp->bits);
  901. put_child(t, (struct tnode *)tp, cindex, (struct node *)tn);
  902. } else {
  903. rcu_assign_pointer(t->trie, (struct node *)tn); /* First tnode */
  904. tp = tn;
  905. }
  906. }
  907. if (tp && tp->pos + tp->bits > 32)
  908. printk(KERN_WARNING "fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
  909. tp, tp->pos, tp->bits, key, plen);
  910. /* Rebalance the trie */
  911. rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
  912. done:
  913. t->revision++;
  914. err:
  915. return fa_head;
  916. }
  917. static int
  918. fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
  919. struct nlmsghdr *nlhdr, struct netlink_skb_parms *req)
  920. {
  921. struct trie *t = (struct trie *) tb->tb_data;
  922. struct fib_alias *fa, *new_fa;
  923. struct list_head *fa_head = NULL;
  924. struct fib_info *fi;
  925. int plen = r->rtm_dst_len;
  926. int type = r->rtm_type;
  927. u8 tos = r->rtm_tos;
  928. u32 key, mask;
  929. int err;
  930. struct leaf *l;
  931. if (plen > 32)
  932. return -EINVAL;
  933. key = 0;
  934. if (rta->rta_dst)
  935. memcpy(&key, rta->rta_dst, 4);
  936. key = ntohl(key);
  937. pr_debug("Insert table=%d %08x/%d\n", tb->tb_id, key, plen);
  938. mask = ntohl(inet_make_mask(plen));
  939. if (key & ~mask)
  940. return -EINVAL;
  941. key = key & mask;
  942. fi = fib_create_info(r, rta, nlhdr, &err);
  943. if (!fi)
  944. goto err;
  945. l = fib_find_node(t, key);
  946. fa = NULL;
  947. if (l) {
  948. fa_head = get_fa_head(l, plen);
  949. fa = fib_find_alias(fa_head, tos, fi->fib_priority);
  950. }
  951. /* Now fa, if non-NULL, points to the first fib alias
  952. * with the same keys [prefix,tos,priority], if such key already
  953. * exists or to the node before which we will insert new one.
  954. *
  955. * If fa is NULL, we will need to allocate a new one and
  956. * insert to the head of f.
  957. *
  958. * If f is NULL, no fib node matched the destination key
  959. * and we need to allocate a new one of those as well.
  960. */
  961. if (fa && fa->fa_info->fib_priority == fi->fib_priority) {
  962. struct fib_alias *fa_orig;
  963. err = -EEXIST;
  964. if (nlhdr->nlmsg_flags & NLM_F_EXCL)
  965. goto out;
  966. if (nlhdr->nlmsg_flags & NLM_F_REPLACE) {
  967. struct fib_info *fi_drop;
  968. u8 state;
  969. err = -ENOBUFS;
  970. new_fa = kmem_cache_alloc(fn_alias_kmem, SLAB_KERNEL);
  971. if (new_fa == NULL)
  972. goto out;
  973. fi_drop = fa->fa_info;
  974. new_fa->fa_tos = fa->fa_tos;
  975. new_fa->fa_info = fi;
  976. new_fa->fa_type = type;
  977. new_fa->fa_scope = r->rtm_scope;
  978. state = fa->fa_state;
  979. new_fa->fa_state &= ~FA_S_ACCESSED;
  980. list_replace_rcu(&fa->fa_list, &new_fa->fa_list);
  981. alias_free_mem_rcu(fa);
  982. fib_release_info(fi_drop);
  983. if (state & FA_S_ACCESSED)
  984. rt_cache_flush(-1);
  985. goto succeeded;
  986. }
  987. /* Error if we find a perfect match which
  988. * uses the same scope, type, and nexthop
  989. * information.
  990. */
  991. fa_orig = fa;
  992. list_for_each_entry(fa, fa_orig->fa_list.prev, fa_list) {
  993. if (fa->fa_tos != tos)
  994. break;
  995. if (fa->fa_info->fib_priority != fi->fib_priority)
  996. break;
  997. if (fa->fa_type == type &&
  998. fa->fa_scope == r->rtm_scope &&
  999. fa->fa_info == fi) {
  1000. goto out;
  1001. }
  1002. }
  1003. if (!(nlhdr->nlmsg_flags & NLM_F_APPEND))
  1004. fa = fa_orig;
  1005. }
  1006. err = -ENOENT;
  1007. if (!(nlhdr->nlmsg_flags & NLM_F_CREATE))
  1008. goto out;
  1009. err = -ENOBUFS;
  1010. new_fa = kmem_cache_alloc(fn_alias_kmem, SLAB_KERNEL);
  1011. if (new_fa == NULL)
  1012. goto out;
  1013. new_fa->fa_info = fi;
  1014. new_fa->fa_tos = tos;
  1015. new_fa->fa_type = type;
  1016. new_fa->fa_scope = r->rtm_scope;
  1017. new_fa->fa_state = 0;
  1018. /*
  1019. * Insert new entry to the list.
  1020. */
  1021. if (!fa_head) {
  1022. fa_head = fib_insert_node(t, &err, key, plen);
  1023. err = 0;
  1024. if (err)
  1025. goto out_free_new_fa;
  1026. }
  1027. list_add_tail_rcu(&new_fa->fa_list,
  1028. (fa ? &fa->fa_list : fa_head));
  1029. rt_cache_flush(-1);
  1030. rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id, nlhdr, req);
  1031. succeeded:
  1032. return 0;
  1033. out_free_new_fa:
  1034. kmem_cache_free(fn_alias_kmem, new_fa);
  1035. out:
  1036. fib_release_info(fi);
  1037. err:
  1038. return err;
  1039. }
  1040. /* should be called with rcu_read_lock */
  1041. static inline int check_leaf(struct trie *t, struct leaf *l,
  1042. t_key key, int *plen, const struct flowi *flp,
  1043. struct fib_result *res)
  1044. {
  1045. int err, i;
  1046. t_key mask;
  1047. struct leaf_info *li;
  1048. struct hlist_head *hhead = &l->list;
  1049. struct hlist_node *node;
  1050. hlist_for_each_entry_rcu(li, node, hhead, hlist) {
  1051. i = li->plen;
  1052. mask = ntohl(inet_make_mask(i));
  1053. if (l->key != (key & mask))
  1054. continue;
  1055. if ((err = fib_semantic_match(&li->falh, flp, res, l->key, mask, i)) <= 0) {
  1056. *plen = i;
  1057. #ifdef CONFIG_IP_FIB_TRIE_STATS
  1058. t->stats.semantic_match_passed++;
  1059. #endif
  1060. return err;
  1061. }
  1062. #ifdef CONFIG_IP_FIB_TRIE_STATS
  1063. t->stats.semantic_match_miss++;
  1064. #endif
  1065. }
  1066. return 1;
  1067. }
  1068. static int
  1069. fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
  1070. {
  1071. struct trie *t = (struct trie *) tb->tb_data;
  1072. int plen, ret = 0;
  1073. struct node *n;
  1074. struct tnode *pn;
  1075. int pos, bits;
  1076. t_key key = ntohl(flp->fl4_dst);
  1077. int chopped_off;
  1078. t_key cindex = 0;
  1079. int current_prefix_length = KEYLENGTH;
  1080. struct tnode *cn;
  1081. t_key node_prefix, key_prefix, pref_mismatch;
  1082. int mp;
  1083. rcu_read_lock();
  1084. n = rcu_dereference(t->trie);
  1085. if (!n)
  1086. goto failed;
  1087. #ifdef CONFIG_IP_FIB_TRIE_STATS
  1088. t->stats.gets++;
  1089. #endif
  1090. /* Just a leaf? */
  1091. if (IS_LEAF(n)) {
  1092. if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
  1093. goto found;
  1094. goto failed;
  1095. }
  1096. pn = (struct tnode *) n;
  1097. chopped_off = 0;
  1098. while (pn) {
  1099. pos = pn->pos;
  1100. bits = pn->bits;
  1101. if (!chopped_off)
  1102. cindex = tkey_extract_bits(MASK_PFX(key, current_prefix_length), pos, bits);
  1103. n = tnode_get_child(pn, cindex);
  1104. if (n == NULL) {
  1105. #ifdef CONFIG_IP_FIB_TRIE_STATS
  1106. t->stats.null_node_hit++;
  1107. #endif
  1108. goto backtrace;
  1109. }
  1110. if (IS_LEAF(n)) {
  1111. if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
  1112. goto found;
  1113. else
  1114. goto backtrace;
  1115. }
  1116. #define HL_OPTIMIZE
  1117. #ifdef HL_OPTIMIZE
  1118. cn = (struct tnode *)n;
  1119. /*
  1120. * It's a tnode, and we can do some extra checks here if we
  1121. * like, to avoid descending into a dead-end branch.
  1122. * This tnode is in the parent's child array at index
  1123. * key[p_pos..p_pos+p_bits] but potentially with some bits
  1124. * chopped off, so in reality the index may be just a
  1125. * subprefix, padded with zero at the end.
  1126. * We can also take a look at any skipped bits in this
  1127. * tnode - everything up to p_pos is supposed to be ok,
  1128. * and the non-chopped bits of the index (se previous
  1129. * paragraph) are also guaranteed ok, but the rest is
  1130. * considered unknown.
  1131. *
  1132. * The skipped bits are key[pos+bits..cn->pos].
  1133. */
  1134. /* If current_prefix_length < pos+bits, we are already doing
  1135. * actual prefix matching, which means everything from
  1136. * pos+(bits-chopped_off) onward must be zero along some
  1137. * branch of this subtree - otherwise there is *no* valid
  1138. * prefix present. Here we can only check the skipped
  1139. * bits. Remember, since we have already indexed into the
  1140. * parent's child array, we know that the bits we chopped of
  1141. * *are* zero.
  1142. */
  1143. /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */
  1144. if (current_prefix_length < pos+bits) {
  1145. if (tkey_extract_bits(cn->key, current_prefix_length,
  1146. cn->pos - current_prefix_length) != 0 ||
  1147. !(cn->child[0]))
  1148. goto backtrace;
  1149. }
  1150. /*
  1151. * If chopped_off=0, the index is fully validated and we
  1152. * only need to look at the skipped bits for this, the new,
  1153. * tnode. What we actually want to do is to find out if
  1154. * these skipped bits match our key perfectly, or if we will
  1155. * have to count on finding a matching prefix further down,
  1156. * because if we do, we would like to have some way of
  1157. * verifying the existence of such a prefix at this point.
  1158. */
  1159. /* The only thing we can do at this point is to verify that
  1160. * any such matching prefix can indeed be a prefix to our
  1161. * key, and if the bits in the node we are inspecting that
  1162. * do not match our key are not ZERO, this cannot be true.
  1163. * Thus, find out where there is a mismatch (before cn->pos)
  1164. * and verify that all the mismatching bits are zero in the
  1165. * new tnode's key.
  1166. */
  1167. /* Note: We aren't very concerned about the piece of the key
  1168. * that precede pn->pos+pn->bits, since these have already been
  1169. * checked. The bits after cn->pos aren't checked since these are
  1170. * by definition "unknown" at this point. Thus, what we want to
  1171. * see is if we are about to enter the "prefix matching" state,
  1172. * and in that case verify that the skipped bits that will prevail
  1173. * throughout this subtree are zero, as they have to be if we are
  1174. * to find a matching prefix.
  1175. */
  1176. node_prefix = MASK_PFX(cn->key, cn->pos);
  1177. key_prefix = MASK_PFX(key, cn->pos);
  1178. pref_mismatch = key_prefix^node_prefix;
  1179. mp = 0;
  1180. /* In short: If skipped bits in this node do not match the search
  1181. * key, enter the "prefix matching" state.directly.
  1182. */
  1183. if (pref_mismatch) {
  1184. while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
  1185. mp++;
  1186. pref_mismatch = pref_mismatch <<1;
  1187. }
  1188. key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);
  1189. if (key_prefix != 0)
  1190. goto backtrace;
  1191. if (current_prefix_length >= cn->pos)
  1192. current_prefix_length = mp;
  1193. }
  1194. #endif
  1195. pn = (struct tnode *)n; /* Descend */
  1196. chopped_off = 0;
  1197. continue;
  1198. backtrace:
  1199. chopped_off++;
  1200. /* As zero don't change the child key (cindex) */
  1201. while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1))))
  1202. chopped_off++;
  1203. /* Decrease current_... with bits chopped off */
  1204. if (current_prefix_length > pn->pos + pn->bits - chopped_off)
  1205. current_prefix_length = pn->pos + pn->bits - chopped_off;
  1206. /*
  1207. * Either we do the actual chop off according or if we have
  1208. * chopped off all bits in this tnode walk up to our parent.
  1209. */
  1210. if (chopped_off <= pn->bits) {
  1211. cindex &= ~(1 << (chopped_off-1));
  1212. } else {
  1213. if (NODE_PARENT(pn) == NULL)
  1214. goto failed;
  1215. /* Get Child's index */
  1216. cindex = tkey_extract_bits(pn->key, NODE_PARENT(pn)->pos, NODE_PARENT(pn)->bits);
  1217. pn = NODE_PARENT(pn);
  1218. chopped_off = 0;
  1219. #ifdef CONFIG_IP_FIB_TRIE_STATS
  1220. t->stats.backtrack++;
  1221. #endif
  1222. goto backtrace;
  1223. }
  1224. }
  1225. failed:
  1226. ret = 1;
  1227. found:
  1228. rcu_read_unlock();
  1229. return ret;
  1230. }
  1231. /* only called from updater side */
  1232. static int trie_leaf_remove(struct trie *t, t_key key)
  1233. {
  1234. t_key cindex;
  1235. struct tnode *tp = NULL;
  1236. struct node *n = t->trie;
  1237. struct leaf *l;
  1238. pr_debug("entering trie_leaf_remove(%p)\n", n);
  1239. /* Note that in the case skipped bits, those bits are *not* checked!
  1240. * When we finish this, we will have NULL or a T_LEAF, and the
  1241. * T_LEAF may or may not match our key.
  1242. */
  1243. while (n != NULL && IS_TNODE(n)) {
  1244. struct tnode *tn = (struct tnode *) n;
  1245. check_tnode(tn);
  1246. n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits));
  1247. BUG_ON(n && NODE_PARENT(n) != tn);
  1248. }
  1249. l = (struct leaf *) n;
  1250. if (!n || !tkey_equals(l->key, key))
  1251. return 0;
  1252. /*
  1253. * Key found.
  1254. * Remove the leaf and rebalance the tree
  1255. */
  1256. t->revision++;
  1257. t->size--;
  1258. preempt_disable();
  1259. tp = NODE_PARENT(n);
  1260. tnode_free((struct tnode *) n);
  1261. if (tp) {
  1262. cindex = tkey_extract_bits(key, tp->pos, tp->bits);
  1263. put_child(t, (struct tnode *)tp, cindex, NULL);
  1264. rcu_assign_pointer(t->trie, trie_rebalance(t, tp));
  1265. } else
  1266. rcu_assign_pointer(t->trie, NULL);
  1267. preempt_enable();
  1268. return 1;
  1269. }
  1270. static int
  1271. fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
  1272. struct nlmsghdr *nlhdr, struct netlink_skb_parms *req)
  1273. {
  1274. struct trie *t = (struct trie *) tb->tb_data;
  1275. u32 key, mask;
  1276. int plen = r->rtm_dst_len;
  1277. u8 tos = r->rtm_tos;
  1278. struct fib_alias *fa, *fa_to_delete;
  1279. struct list_head *fa_head;
  1280. struct leaf *l;
  1281. struct leaf_info *li;
  1282. if (plen > 32)
  1283. return -EINVAL;
  1284. key = 0;
  1285. if (rta->rta_dst)
  1286. memcpy(&key, rta->rta_dst, 4);
  1287. key = ntohl(key);
  1288. mask = ntohl(inet_make_mask(plen));
  1289. if (key & ~mask)
  1290. return -EINVAL;
  1291. key = key & mask;
  1292. l = fib_find_node(t, key);
  1293. if (!l)
  1294. return -ESRCH;
  1295. fa_head = get_fa_head(l, plen);
  1296. fa = fib_find_alias(fa_head, tos, 0);
  1297. if (!fa)
  1298. return -ESRCH;
  1299. pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
  1300. fa_to_delete = NULL;
  1301. fa_head = fa->fa_list.prev;
  1302. list_for_each_entry(fa, fa_head, fa_list) {
  1303. struct fib_info *fi = fa->fa_info;
  1304. if (fa->fa_tos != tos)
  1305. break;
  1306. if ((!r->rtm_type ||
  1307. fa->fa_type == r->rtm_type) &&
  1308. (r->rtm_scope == RT_SCOPE_NOWHERE ||
  1309. fa->fa_scope == r->rtm_scope) &&
  1310. (!r->rtm_protocol ||
  1311. fi->fib_protocol == r->rtm_protocol) &&
  1312. fib_nh_match(r, nlhdr, rta, fi) == 0) {
  1313. fa_to_delete = fa;
  1314. break;
  1315. }
  1316. }
  1317. if (!fa_to_delete)
  1318. return -ESRCH;
  1319. fa = fa_to_delete;
  1320. rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id, nlhdr, req);
  1321. l = fib_find_node(t, key);
  1322. li = find_leaf_info(l, plen);
  1323. list_del_rcu(&fa->fa_list);
  1324. if (list_empty(fa_head)) {
  1325. hlist_del_rcu(&li->hlist);
  1326. free_leaf_info(li);
  1327. }
  1328. if (hlist_empty(&l->list))
  1329. trie_leaf_remove(t, key);
  1330. if (fa->fa_state & FA_S_ACCESSED)
  1331. rt_cache_flush(-1);
  1332. fib_release_info(fa->fa_info);
  1333. alias_free_mem_rcu(fa);
  1334. return 0;
  1335. }
  1336. static int trie_flush_list(struct trie *t, struct list_head *head)
  1337. {
  1338. struct fib_alias *fa, *fa_node;
  1339. int found = 0;
  1340. list_for_each_entry_safe(fa, fa_node, head, fa_list) {
  1341. struct fib_info *fi = fa->fa_info;
  1342. if (fi && (fi->fib_flags & RTNH_F_DEAD)) {
  1343. list_del_rcu(&fa->fa_list);
  1344. fib_release_info(fa->fa_info);
  1345. alias_free_mem_rcu(fa);
  1346. found++;
  1347. }
  1348. }
  1349. return found;
  1350. }
  1351. static int trie_flush_leaf(struct trie *t, struct leaf *l)
  1352. {
  1353. int found = 0;
  1354. struct hlist_head *lih = &l->list;
  1355. struct hlist_node *node, *tmp;
  1356. struct leaf_info *li = NULL;
  1357. hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
  1358. found += trie_flush_list(t, &li->falh);
  1359. if (list_empty(&li->falh)) {
  1360. hlist_del_rcu(&li->hlist);
  1361. free_leaf_info(li);
  1362. }
  1363. }
  1364. return found;
  1365. }
  1366. /* rcu_read_lock needs to be hold by caller from readside */
  1367. static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
  1368. {
  1369. struct node *c = (struct node *) thisleaf;
  1370. struct tnode *p;
  1371. int idx;
  1372. struct node *trie = rcu_dereference(t->trie);
  1373. if (c == NULL) {
  1374. if (trie == NULL)
  1375. return NULL;
  1376. if (IS_LEAF(trie)) /* trie w. just a leaf */
  1377. return (struct leaf *) trie;
  1378. p = (struct tnode*) trie; /* Start */
  1379. } else
  1380. p = (struct tnode *) NODE_PARENT(c);
  1381. while (p) {
  1382. int pos, last;
  1383. /* Find the next child of the parent */
  1384. if (c)
  1385. pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits);
  1386. else
  1387. pos = 0;
  1388. last = 1 << p->bits;
  1389. for (idx = pos; idx < last ; idx++) {
  1390. c = rcu_dereference(p->child[idx]);
  1391. if (!c)
  1392. continue;
  1393. /* Decend if tnode */
  1394. while (IS_TNODE(c)) {
  1395. p = (struct tnode *) c;
  1396. idx = 0;
  1397. /* Rightmost non-NULL branch */
  1398. if (p && IS_TNODE(p))
  1399. while (!(c = rcu_dereference(p->child[idx]))
  1400. && idx < (1<<p->bits)) idx++;
  1401. /* Done with this tnode? */
  1402. if (idx >= (1 << p->bits) || !c)
  1403. goto up;
  1404. }
  1405. return (struct leaf *) c;
  1406. }
  1407. up:
  1408. /* No more children go up one step */
  1409. c = (struct node *) p;
  1410. p = (struct tnode *) NODE_PARENT(p);
  1411. }
  1412. return NULL; /* Ready. Root of trie */
  1413. }
  1414. static int fn_trie_flush(struct fib_table *tb)
  1415. {
  1416. struct trie *t = (struct trie *) tb->tb_data;
  1417. struct leaf *ll = NULL, *l = NULL;
  1418. int found = 0, h;
  1419. t->revision++;
  1420. for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
  1421. found += trie_flush_leaf(t, l);
  1422. if (ll && hlist_empty(&ll->list))
  1423. trie_leaf_remove(t, ll->key);
  1424. ll = l;
  1425. }
  1426. if (ll && hlist_empty(&ll->list))
  1427. trie_leaf_remove(t, ll->key);
  1428. pr_debug("trie_flush found=%d\n", found);
  1429. return found;
  1430. }
  1431. static int trie_last_dflt = -1;
  1432. static void
  1433. fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
  1434. {
  1435. struct trie *t = (struct trie *) tb->tb_data;
  1436. int order, last_idx;
  1437. struct fib_info *fi = NULL;
  1438. struct fib_info *last_resort;
  1439. struct fib_alias *fa = NULL;
  1440. struct list_head *fa_head;
  1441. struct leaf *l;
  1442. last_idx = -1;
  1443. last_resort = NULL;
  1444. order = -1;
  1445. rcu_read_lock();
  1446. l = fib_find_node(t, 0);
  1447. if (!l)
  1448. goto out;
  1449. fa_head = get_fa_head(l, 0);
  1450. if (!fa_head)
  1451. goto out;
  1452. if (list_empty(fa_head))
  1453. goto out;
  1454. list_for_each_entry_rcu(fa, fa_head, fa_list) {
  1455. struct fib_info *next_fi = fa->fa_info;
  1456. if (fa->fa_scope != res->scope ||
  1457. fa->fa_type != RTN_UNICAST)
  1458. continue;
  1459. if (next_fi->fib_priority > res->fi->fib_priority)
  1460. break;
  1461. if (!next_fi->fib_nh[0].nh_gw ||
  1462. next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
  1463. continue;
  1464. fa->fa_state |= FA_S_ACCESSED;
  1465. if (fi == NULL) {
  1466. if (next_fi != res->fi)
  1467. break;
  1468. } else if (!fib_detect_death(fi, order, &last_resort,
  1469. &last_idx, &trie_last_dflt)) {
  1470. if (res->fi)
  1471. fib_info_put(res->fi);
  1472. res->fi = fi;
  1473. atomic_inc(&fi->fib_clntref);
  1474. trie_last_dflt = order;
  1475. goto out;
  1476. }
  1477. fi = next_fi;
  1478. order++;
  1479. }
  1480. if (order <= 0 || fi == NULL) {
  1481. trie_last_dflt = -1;
  1482. goto out;
  1483. }
  1484. if (!fib_detect_death(fi, order, &last_resort, &last_idx, &trie_last_dflt)) {
  1485. if (res->fi)
  1486. fib_info_put(res->fi);
  1487. res->fi = fi;
  1488. atomic_inc(&fi->fib_clntref);
  1489. trie_last_dflt = order;
  1490. goto out;
  1491. }
  1492. if (last_idx >= 0) {
  1493. if (res->fi)
  1494. fib_info_put(res->fi);
  1495. res->fi = last_resort;
  1496. if (last_resort)
  1497. atomic_inc(&last_resort->fib_clntref);
  1498. }
  1499. trie_last_dflt = last_idx;
  1500. out:;
  1501. rcu_read_unlock();
  1502. }
  1503. static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fib_table *tb,
  1504. struct sk_buff *skb, struct netlink_callback *cb)
  1505. {
  1506. int i, s_i;
  1507. struct fib_alias *fa;
  1508. u32 xkey = htonl(key);
  1509. s_i = cb->args[3];
  1510. i = 0;
  1511. /* rcu_read_lock is hold by caller */
  1512. list_for_each_entry_rcu(fa, fah, fa_list) {
  1513. if (i < s_i) {
  1514. i++;
  1515. continue;
  1516. }
  1517. BUG_ON(!fa->fa_info);
  1518. if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
  1519. cb->nlh->nlmsg_seq,
  1520. RTM_NEWROUTE,
  1521. tb->tb_id,
  1522. fa->fa_type,
  1523. fa->fa_scope,
  1524. &xkey,
  1525. plen,
  1526. fa->fa_tos,
  1527. fa->fa_info, 0) < 0) {
  1528. cb->args[3] = i;
  1529. return -1;
  1530. }
  1531. i++;
  1532. }
  1533. cb->args[3] = i;
  1534. return skb->len;
  1535. }
  1536. static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb,
  1537. struct netlink_callback *cb)
  1538. {
  1539. int h, s_h;
  1540. struct list_head *fa_head;
  1541. struct leaf *l = NULL;
  1542. s_h = cb->args[2];
  1543. for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
  1544. if (h < s_h)
  1545. continue;
  1546. if (h > s_h)
  1547. memset(&cb->args[3], 0,
  1548. sizeof(cb->args) - 3*sizeof(cb->args[0]));
  1549. fa_head = get_fa_head(l, plen);
  1550. if (!fa_head)
  1551. continue;
  1552. if (list_empty(fa_head))
  1553. continue;
  1554. if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
  1555. cb->args[2] = h;
  1556. return -1;
  1557. }
  1558. }
  1559. cb->args[2] = h;
  1560. return skb->len;
  1561. }
  1562. static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlink_callback *cb)
  1563. {
  1564. int m, s_m;
  1565. struct trie *t = (struct trie *) tb->tb_data;
  1566. s_m = cb->args[1];
  1567. rcu_read_lock();
  1568. for (m = 0; m <= 32; m++) {
  1569. if (m < s_m)
  1570. continue;
  1571. if (m > s_m)
  1572. memset(&cb->args[2], 0,
  1573. sizeof(cb->args) - 2*sizeof(cb->args[0]));
  1574. if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) {
  1575. cb->args[1] = m;
  1576. goto out;
  1577. }
  1578. }
  1579. rcu_read_unlock();
  1580. cb->args[1] = m;
  1581. return skb->len;
  1582. out:
  1583. rcu_read_unlock();
  1584. return -1;
  1585. }
  1586. /* Fix more generic FIB names for init later */
  1587. #ifdef CONFIG_IP_MULTIPLE_TABLES
  1588. struct fib_table * fib_hash_init(int id)
  1589. #else
  1590. struct fib_table * __init fib_hash_init(int id)
  1591. #endif
  1592. {
  1593. struct fib_table *tb;
  1594. struct trie *t;
  1595. if (fn_alias_kmem == NULL)
  1596. fn_alias_kmem = kmem_cache_create("ip_fib_alias",
  1597. sizeof(struct fib_alias),
  1598. 0, SLAB_HWCACHE_ALIGN,
  1599. NULL, NULL);
  1600. tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
  1601. GFP_KERNEL);
  1602. if (tb == NULL)
  1603. return NULL;
  1604. tb->tb_id = id;
  1605. tb->tb_lookup = fn_trie_lookup;
  1606. tb->tb_insert = fn_trie_insert;
  1607. tb->tb_delete = fn_trie_delete;
  1608. tb->tb_flush = fn_trie_flush;
  1609. tb->tb_select_default = fn_trie_select_default;
  1610. tb->tb_dump = fn_trie_dump;
  1611. memset(tb->tb_data, 0, sizeof(struct trie));
  1612. t = (struct trie *) tb->tb_data;
  1613. trie_init(t);
  1614. if (id == RT_TABLE_LOCAL)
  1615. trie_local = t;
  1616. else if (id == RT_TABLE_MAIN)
  1617. trie_main = t;
  1618. if (id == RT_TABLE_LOCAL)
  1619. printk(KERN_INFO "IPv4 FIB: Using LC-trie version %s\n", VERSION);
  1620. return tb;
  1621. }
  1622. #ifdef CONFIG_PROC_FS
  1623. /* Depth first Trie walk iterator */
  1624. struct fib_trie_iter {
  1625. struct tnode *tnode;
  1626. struct trie *trie;
  1627. unsigned index;
  1628. unsigned depth;
  1629. };
  1630. static struct node *fib_trie_get_next(struct fib_trie_iter *iter)
  1631. {
  1632. struct tnode *tn = iter->tnode;
  1633. unsigned cindex = iter->index;
  1634. struct tnode *p;
  1635. pr_debug("get_next iter={node=%p index=%d depth=%d}\n",
  1636. iter->tnode, iter->index, iter->depth);
  1637. rescan:
  1638. while (cindex < (1<<tn->bits)) {
  1639. struct node *n = tnode_get_child(tn, cindex);
  1640. if (n) {
  1641. if (IS_LEAF(n)) {
  1642. iter->tnode = tn;
  1643. iter->index = cindex + 1;
  1644. } else {
  1645. /* push down one level */
  1646. iter->tnode = (struct tnode *) n;
  1647. iter->index = 0;
  1648. ++iter->depth;
  1649. }
  1650. return n;
  1651. }
  1652. ++cindex;
  1653. }
  1654. /* Current node exhausted, pop back up */
  1655. p = NODE_PARENT(tn);
  1656. if (p) {
  1657. cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
  1658. tn = p;
  1659. --iter->depth;
  1660. goto rescan;
  1661. }
  1662. /* got root? */
  1663. return NULL;
  1664. }
  1665. static struct node *fib_trie_get_first(struct fib_trie_iter *iter,
  1666. struct trie *t)
  1667. {
  1668. struct node *n = rcu_dereference(t->trie);
  1669. if (n && IS_TNODE(n)) {
  1670. iter->tnode = (struct tnode *) n;
  1671. iter->trie = t;
  1672. iter->index = 0;
  1673. iter->depth = 1;
  1674. return n;
  1675. }
  1676. return NULL;
  1677. }
  1678. static void trie_collect_stats(struct trie *t, struct trie_stat *s)
  1679. {
  1680. struct node *n;
  1681. struct fib_trie_iter iter;
  1682. memset(s, 0, sizeof(*s));
  1683. rcu_read_lock();
  1684. for (n = fib_trie_get_first(&iter, t); n;
  1685. n = fib_trie_get_next(&iter)) {
  1686. if (IS_LEAF(n)) {
  1687. s->leaves++;
  1688. s->totdepth += iter.depth;
  1689. if (iter.depth > s->maxdepth)
  1690. s->maxdepth = iter.depth;
  1691. } else {
  1692. const struct tnode *tn = (const struct tnode *) n;
  1693. int i;
  1694. s->tnodes++;
  1695. s->nodesizes[tn->bits]++;
  1696. for (i = 0; i < (1<<tn->bits); i++)
  1697. if (!tn->child[i])
  1698. s->nullpointers++;
  1699. }
  1700. }
  1701. rcu_read_unlock();
  1702. }
  1703. /*
  1704. * This outputs /proc/net/fib_triestats
  1705. */
  1706. static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
  1707. {
  1708. unsigned i, max, pointers, bytes, avdepth;
  1709. if (stat->leaves)
  1710. avdepth = stat->totdepth*100 / stat->leaves;
  1711. else
  1712. avdepth = 0;
  1713. seq_printf(seq, "\tAver depth: %d.%02d\n", avdepth / 100, avdepth % 100 );
  1714. seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
  1715. seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
  1716. bytes = sizeof(struct leaf) * stat->leaves;
  1717. seq_printf(seq, "\tInternal nodes: %d\n\t", stat->tnodes);
  1718. bytes += sizeof(struct tnode) * stat->tnodes;
  1719. max = MAX_CHILDS-1;
  1720. while (max >= 0 && stat->nodesizes[max] == 0)
  1721. max--;
  1722. pointers = 0;
  1723. for (i = 1; i <= max; i++)
  1724. if (stat->nodesizes[i] != 0) {
  1725. seq_printf(seq, " %d: %d", i, stat->nodesizes[i]);
  1726. pointers += (1<<i) * stat->nodesizes[i];
  1727. }
  1728. seq_putc(seq, '\n');
  1729. seq_printf(seq, "\tPointers: %d\n", pointers);
  1730. bytes += sizeof(struct node *) * pointers;
  1731. seq_printf(seq, "Null ptrs: %d\n", stat->nullpointers);
  1732. seq_printf(seq, "Total size: %d kB\n", (bytes + 1023) / 1024);
  1733. #ifdef CONFIG_IP_FIB_TRIE_STATS
  1734. seq_printf(seq, "Counters:\n---------\n");
  1735. seq_printf(seq,"gets = %d\n", t->stats.gets);
  1736. seq_printf(seq,"backtracks = %d\n", t->stats.backtrack);
  1737. seq_printf(seq,"semantic match passed = %d\n", t->stats.semantic_match_passed);
  1738. seq_printf(seq,"semantic match miss = %d\n", t->stats.semantic_match_miss);
  1739. seq_printf(seq,"null node hit= %d\n", t->stats.null_node_hit);
  1740. seq_printf(seq,"skipped node resize = %d\n", t->stats.resize_node_skipped);
  1741. #ifdef CLEAR_STATS
  1742. memset(&(t->stats), 0, sizeof(t->stats));
  1743. #endif
  1744. #endif /* CONFIG_IP_FIB_TRIE_STATS */
  1745. }
  1746. static int fib_triestat_seq_show(struct seq_file *seq, void *v)
  1747. {
  1748. struct trie_stat *stat;
  1749. stat = kmalloc(sizeof(*stat), GFP_KERNEL);
  1750. if (!stat)
  1751. return -ENOMEM;
  1752. seq_printf(seq, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
  1753. sizeof(struct leaf), sizeof(struct tnode));
  1754. if (trie_local) {
  1755. seq_printf(seq, "Local:\n");
  1756. trie_collect_stats(trie_local, stat);
  1757. trie_show_stats(seq, stat);
  1758. }
  1759. if (trie_main) {
  1760. seq_printf(seq, "Main:\n");
  1761. trie_collect_stats(trie_main, stat);
  1762. trie_show_stats(seq, stat);
  1763. }
  1764. kfree(stat);
  1765. return 0;
  1766. }
  1767. static int fib_triestat_seq_open(struct inode *inode, struct file *file)
  1768. {
  1769. return single_open(file, fib_triestat_seq_show, NULL);
  1770. }
  1771. static struct file_operations fib_triestat_fops = {
  1772. .owner = THIS_MODULE,
  1773. .open = fib_triestat_seq_open,
  1774. .read = seq_read,
  1775. .llseek = seq_lseek,
  1776. .release = single_release,
  1777. };
  1778. static struct node *fib_trie_get_idx(struct fib_trie_iter *iter,
  1779. loff_t pos)
  1780. {
  1781. loff_t idx = 0;
  1782. struct node *n;
  1783. for (n = fib_trie_get_first(iter, trie_local);
  1784. n; ++idx, n = fib_trie_get_next(iter)) {
  1785. if (pos == idx)
  1786. return n;
  1787. }
  1788. for (n = fib_trie_get_first(iter, trie_main);
  1789. n; ++idx, n = fib_trie_get_next(iter)) {
  1790. if (pos == idx)
  1791. return n;
  1792. }
  1793. return NULL;
  1794. }
  1795. static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
  1796. {
  1797. rcu_read_lock();
  1798. if (*pos == 0)
  1799. return SEQ_START_TOKEN;
  1800. return fib_trie_get_idx(seq->private, *pos - 1);
  1801. }
  1802. static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
  1803. {
  1804. struct fib_trie_iter *iter = seq->private;
  1805. void *l = v;
  1806. ++*pos;
  1807. if (v == SEQ_START_TOKEN)
  1808. return fib_trie_get_idx(iter, 0);
  1809. v = fib_trie_get_next(iter);
  1810. BUG_ON(v == l);
  1811. if (v)
  1812. return v;
  1813. /* continue scan in next trie */
  1814. if (iter->trie == trie_local)
  1815. return fib_trie_get_first(iter, trie_main);
  1816. return NULL;
  1817. }
  1818. static void fib_trie_seq_stop(struct seq_file *seq, void *v)
  1819. {
  1820. rcu_read_unlock();
  1821. }
  1822. static void seq_indent(struct seq_file *seq, int n)
  1823. {
  1824. while (n-- > 0) seq_puts(seq, " ");
  1825. }
  1826. static inline const char *rtn_scope(enum rt_scope_t s)
  1827. {
  1828. static char buf[32];
  1829. switch(s) {
  1830. case RT_SCOPE_UNIVERSE: return "universe";
  1831. case RT_SCOPE_SITE: return "site";
  1832. case RT_SCOPE_LINK: return "link";
  1833. case RT_SCOPE_HOST: return "host";
  1834. case RT_SCOPE_NOWHERE: return "nowhere";
  1835. default:
  1836. snprintf(buf, sizeof(buf), "scope=%d", s);
  1837. return buf;
  1838. }
  1839. }
  1840. static const char *rtn_type_names[__RTN_MAX] = {
  1841. [RTN_UNSPEC] = "UNSPEC",
  1842. [RTN_UNICAST] = "UNICAST",
  1843. [RTN_LOCAL] = "LOCAL",
  1844. [RTN_BROADCAST] = "BROADCAST",
  1845. [RTN_ANYCAST] = "ANYCAST",
  1846. [RTN_MULTICAST] = "MULTICAST",
  1847. [RTN_BLACKHOLE] = "BLACKHOLE",
  1848. [RTN_UNREACHABLE] = "UNREACHABLE",
  1849. [RTN_PROHIBIT] = "PROHIBIT",
  1850. [RTN_THROW] = "THROW",
  1851. [RTN_NAT] = "NAT",
  1852. [RTN_XRESOLVE] = "XRESOLVE",
  1853. };
  1854. static inline const char *rtn_type(unsigned t)
  1855. {
  1856. static char buf[32];
  1857. if (t < __RTN_MAX && rtn_type_names[t])
  1858. return rtn_type_names[t];
  1859. snprintf(buf, sizeof(buf), "type %d", t);
  1860. return buf;
  1861. }
  1862. /* Pretty print the trie */
  1863. static int fib_trie_seq_show(struct seq_file *seq, void *v)
  1864. {
  1865. const struct fib_trie_iter *iter = seq->private;
  1866. struct node *n = v;
  1867. if (v == SEQ_START_TOKEN)
  1868. return 0;
  1869. if (IS_TNODE(n)) {
  1870. struct tnode *tn = (struct tnode *) n;
  1871. t_key prf = ntohl(MASK_PFX(tn->key, tn->pos));
  1872. if (!NODE_PARENT(n)) {
  1873. if (iter->trie == trie_local)
  1874. seq_puts(seq, "<local>:\n");
  1875. else
  1876. seq_puts(seq, "<main>:\n");
  1877. }
  1878. seq_indent(seq, iter->depth-1);
  1879. seq_printf(seq, " +-- %d.%d.%d.%d/%d %d %d %d\n",
  1880. NIPQUAD(prf), tn->pos, tn->bits, tn->full_children,
  1881. tn->empty_children);
  1882. } else {
  1883. struct leaf *l = (struct leaf *) n;
  1884. int i;
  1885. u32 val = ntohl(l->key);
  1886. seq_indent(seq, iter->depth);
  1887. seq_printf(seq, " |-- %d.%d.%d.%d\n", NIPQUAD(val));
  1888. for (i = 32; i >= 0; i--) {
  1889. struct leaf_info *li = find_leaf_info(l, i);
  1890. if (li) {
  1891. struct fib_alias *fa;
  1892. list_for_each_entry_rcu(fa, &li->falh, fa_list) {
  1893. seq_indent(seq, iter->depth+1);
  1894. seq_printf(seq, " /%d %s %s", i,
  1895. rtn_scope(fa->fa_scope),
  1896. rtn_type(fa->fa_type));
  1897. if (fa->fa_tos)
  1898. seq_printf(seq, "tos =%d\n",
  1899. fa->fa_tos);
  1900. seq_putc(seq, '\n');
  1901. }
  1902. }
  1903. }
  1904. }
  1905. return 0;
  1906. }
  1907. static struct seq_operations fib_trie_seq_ops = {
  1908. .start = fib_trie_seq_start,
  1909. .next = fib_trie_seq_next,
  1910. .stop = fib_trie_seq_stop,
  1911. .show = fib_trie_seq_show,
  1912. };
  1913. static int fib_trie_seq_open(struct inode *inode, struct file *file)
  1914. {
  1915. struct seq_file *seq;
  1916. int rc = -ENOMEM;
  1917. struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
  1918. if (!s)
  1919. goto out;
  1920. rc = seq_open(file, &fib_trie_seq_ops);
  1921. if (rc)
  1922. goto out_kfree;
  1923. seq = file->private_data;
  1924. seq->private = s;
  1925. memset(s, 0, sizeof(*s));
  1926. out:
  1927. return rc;
  1928. out_kfree:
  1929. kfree(s);
  1930. goto out;
  1931. }
  1932. static struct file_operations fib_trie_fops = {
  1933. .owner = THIS_MODULE,
  1934. .open = fib_trie_seq_open,
  1935. .read = seq_read,
  1936. .llseek = seq_lseek,
  1937. .release = seq_release_private,
  1938. };
  1939. static unsigned fib_flag_trans(int type, u32 mask, const struct fib_info *fi)
  1940. {
  1941. static unsigned type2flags[RTN_MAX + 1] = {
  1942. [7] = RTF_REJECT, [8] = RTF_REJECT,
  1943. };
  1944. unsigned flags = type2flags[type];
  1945. if (fi && fi->fib_nh->nh_gw)
  1946. flags |= RTF_GATEWAY;
  1947. if (mask == 0xFFFFFFFF)
  1948. flags |= RTF_HOST;
  1949. flags |= RTF_UP;
  1950. return flags;
  1951. }
  1952. /*
  1953. * This outputs /proc/net/route.
  1954. * The format of the file is not supposed to be changed
  1955. * and needs to be same as fib_hash output to avoid breaking
  1956. * legacy utilities
  1957. */
  1958. static int fib_route_seq_show(struct seq_file *seq, void *v)
  1959. {
  1960. const struct fib_trie_iter *iter = seq->private;
  1961. struct leaf *l = v;
  1962. int i;
  1963. char bf[128];
  1964. if (v == SEQ_START_TOKEN) {
  1965. seq_printf(seq, "%-127s\n", "Iface\tDestination\tGateway "
  1966. "\tFlags\tRefCnt\tUse\tMetric\tMask\t\tMTU"
  1967. "\tWindow\tIRTT");
  1968. return 0;
  1969. }
  1970. if (iter->trie == trie_local)
  1971. return 0;
  1972. if (IS_TNODE(l))
  1973. return 0;
  1974. for (i=32; i>=0; i--) {
  1975. struct leaf_info *li = find_leaf_info(l, i);
  1976. struct fib_alias *fa;
  1977. u32 mask, prefix;
  1978. if (!li)
  1979. continue;
  1980. mask = inet_make_mask(li->plen);
  1981. prefix = htonl(l->key);
  1982. list_for_each_entry_rcu(fa, &li->falh, fa_list) {
  1983. const struct fib_info *fi = fa->fa_info;
  1984. unsigned flags = fib_flag_trans(fa->fa_type, mask, fi);
  1985. if (fa->fa_type == RTN_BROADCAST
  1986. || fa->fa_type == RTN_MULTICAST)
  1987. continue;
  1988. if (fi)
  1989. snprintf(bf, sizeof(bf),
  1990. "%s\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
  1991. fi->fib_dev ? fi->fib_dev->name : "*",
  1992. prefix,
  1993. fi->fib_nh->nh_gw, flags, 0, 0,
  1994. fi->fib_priority,
  1995. mask,
  1996. (fi->fib_advmss ? fi->fib_advmss + 40 : 0),
  1997. fi->fib_window,
  1998. fi->fib_rtt >> 3);
  1999. else
  2000. snprintf(bf, sizeof(bf),
  2001. "*\t%08X\t%08X\t%04X\t%d\t%u\t%d\t%08X\t%d\t%u\t%u",
  2002. prefix, 0, flags, 0, 0, 0,
  2003. mask, 0, 0, 0);
  2004. seq_printf(seq, "%-127s\n", bf);
  2005. }
  2006. }
  2007. return 0;
  2008. }
  2009. static struct seq_operations fib_route_seq_ops = {
  2010. .start = fib_trie_seq_start,
  2011. .next = fib_trie_seq_next,
  2012. .stop = fib_trie_seq_stop,
  2013. .show = fib_route_seq_show,
  2014. };
  2015. static int fib_route_seq_open(struct inode *inode, struct file *file)
  2016. {
  2017. struct seq_file *seq;
  2018. int rc = -ENOMEM;
  2019. struct fib_trie_iter *s = kmalloc(sizeof(*s), GFP_KERNEL);
  2020. if (!s)
  2021. goto out;
  2022. rc = seq_open(file, &fib_route_seq_ops);
  2023. if (rc)
  2024. goto out_kfree;
  2025. seq = file->private_data;
  2026. seq->private = s;
  2027. memset(s, 0, sizeof(*s));
  2028. out:
  2029. return rc;
  2030. out_kfree:
  2031. kfree(s);
  2032. goto out;
  2033. }
  2034. static struct file_operations fib_route_fops = {
  2035. .owner = THIS_MODULE,
  2036. .open = fib_route_seq_open,
  2037. .read = seq_read,
  2038. .llseek = seq_lseek,
  2039. .release = seq_release_private,
  2040. };
  2041. int __init fib_proc_init(void)
  2042. {
  2043. if (!proc_net_fops_create("fib_trie", S_IRUGO, &fib_trie_fops))
  2044. goto out1;
  2045. if (!proc_net_fops_create("fib_triestat", S_IRUGO, &fib_triestat_fops))
  2046. goto out2;
  2047. if (!proc_net_fops_create("route", S_IRUGO, &fib_route_fops))
  2048. goto out3;
  2049. return 0;
  2050. out3:
  2051. proc_net_remove("fib_triestat");
  2052. out2:
  2053. proc_net_remove("fib_trie");
  2054. out1:
  2055. return -ENOMEM;
  2056. }
  2057. void __init fib_proc_exit(void)
  2058. {
  2059. proc_net_remove("fib_trie");
  2060. proc_net_remove("fib_triestat");
  2061. proc_net_remove("route");
  2062. }
  2063. #endif /* CONFIG_PROC_FS */