ip6_fib.c 29 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487
  1. /*
  2. * Linux INET6 implementation
  3. * Forwarding Information Database
  4. *
  5. * Authors:
  6. * Pedro Roque <roque@di.fc.ul.pt>
  7. *
  8. * $Id: ip6_fib.c,v 1.1.1.1 2007/06/12 07:27:14 eyryu Exp $
  9. *
  10. * This program is free software; you can redistribute it and/or
  11. * modify it under the terms of the GNU General Public License
  12. * as published by the Free Software Foundation; either version
  13. * 2 of the License, or (at your option) any later version.
  14. */
  15. /*
  16. * Changes:
  17. * Yuji SEKIYA @USAGI: Support default route on router node;
  18. * remove ip6_null_entry from the top of
  19. * routing table.
  20. * Ville Nuorvala: Fixed routing subtrees.
  21. */
  22. #include <linux/errno.h>
  23. #include <linux/types.h>
  24. #include <linux/net.h>
  25. #include <linux/route.h>
  26. #include <linux/netdevice.h>
  27. #include <linux/in6.h>
  28. #include <linux/init.h>
  29. #include <linux/list.h>
  30. #ifdef CONFIG_PROC_FS
  31. #include <linux/proc_fs.h>
  32. #endif
  33. #include <net/ipv6.h>
  34. #include <net/ndisc.h>
  35. #include <net/addrconf.h>
  36. #include <net/ip6_fib.h>
  37. #include <net/ip6_route.h>
  38. #define RT6_DEBUG 2
  39. #if RT6_DEBUG >= 3
  40. #define RT6_TRACE(x...) printk(KERN_DEBUG x)
  41. #else
  42. #define RT6_TRACE(x...) do { ; } while (0)
  43. #endif
  44. struct rt6_statistics rt6_stats;
  45. static struct kmem_cache * fib6_node_kmem __read_mostly;
  46. enum fib_walk_state_t
  47. {
  48. #ifdef CONFIG_IPV6_SUBTREES
  49. FWS_S,
  50. #endif
  51. FWS_L,
  52. FWS_R,
  53. FWS_C,
  54. FWS_U
  55. };
  56. struct fib6_cleaner_t
  57. {
  58. struct fib6_walker_t w;
  59. int (*func)(struct rt6_info *, void *arg);
  60. void *arg;
  61. };
  62. static DEFINE_RWLOCK(fib6_walker_lock);
  63. #ifdef CONFIG_IPV6_SUBTREES
  64. #define FWS_INIT FWS_S
  65. #else
  66. #define FWS_INIT FWS_L
  67. #endif
  68. static void fib6_prune_clones(struct fib6_node *fn, struct rt6_info *rt);
  69. static struct rt6_info * fib6_find_prefix(struct fib6_node *fn);
  70. static struct fib6_node * fib6_repair_tree(struct fib6_node *fn);
  71. static int fib6_walk(struct fib6_walker_t *w);
  72. static int fib6_walk_continue(struct fib6_walker_t *w);
  73. /*
  74. * A routing update causes an increase of the serial number on the
  75. * affected subtree. This allows for cached routes to be asynchronously
  76. * tested when modifications are made to the destination cache as a
  77. * result of redirects, path MTU changes, etc.
  78. */
  79. static __u32 rt_sernum;
  80. static DEFINE_TIMER(ip6_fib_timer, fib6_run_gc, 0, 0);
  81. static struct fib6_walker_t fib6_walker_list = {
  82. .prev = &fib6_walker_list,
  83. .next = &fib6_walker_list,
  84. };
  85. #define FOR_WALKERS(w) for ((w)=fib6_walker_list.next; (w) != &fib6_walker_list; (w)=(w)->next)
  86. static inline void fib6_walker_link(struct fib6_walker_t *w)
  87. {
  88. write_lock_bh(&fib6_walker_lock);
  89. w->next = fib6_walker_list.next;
  90. w->prev = &fib6_walker_list;
  91. w->next->prev = w;
  92. w->prev->next = w;
  93. write_unlock_bh(&fib6_walker_lock);
  94. }
  95. static inline void fib6_walker_unlink(struct fib6_walker_t *w)
  96. {
  97. write_lock_bh(&fib6_walker_lock);
  98. w->next->prev = w->prev;
  99. w->prev->next = w->next;
  100. w->prev = w->next = w;
  101. write_unlock_bh(&fib6_walker_lock);
  102. }
  103. static __inline__ u32 fib6_new_sernum(void)
  104. {
  105. u32 n = ++rt_sernum;
  106. if ((__s32)n <= 0)
  107. rt_sernum = n = 1;
  108. return n;
  109. }
  110. /*
  111. * Auxiliary address test functions for the radix tree.
  112. *
  113. * These assume a 32bit processor (although it will work on
  114. * 64bit processors)
  115. */
  116. /*
  117. * test bit
  118. */
  119. static __inline__ __be32 addr_bit_set(void *token, int fn_bit)
  120. {
  121. __be32 *addr = token;
  122. return htonl(1 << ((~fn_bit)&0x1F)) & addr[fn_bit>>5];
  123. }
  124. static __inline__ struct fib6_node * node_alloc(void)
  125. {
  126. struct fib6_node *fn;
  127. fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC);
  128. return fn;
  129. }
  130. static __inline__ void node_free(struct fib6_node * fn)
  131. {
  132. kmem_cache_free(fib6_node_kmem, fn);
  133. }
  134. static __inline__ void rt6_release(struct rt6_info *rt)
  135. {
  136. if (atomic_dec_and_test(&rt->rt6i_ref))
  137. dst_free(&rt->u.dst);
  138. }
  139. static struct fib6_table fib6_main_tbl = {
  140. .tb6_id = RT6_TABLE_MAIN,
  141. .tb6_root = {
  142. .leaf = &ip6_null_entry,
  143. .fn_flags = RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO,
  144. },
  145. };
  146. #ifdef CONFIG_IPV6_MULTIPLE_TABLES
  147. #define FIB_TABLE_HASHSZ 256
  148. #else
  149. #define FIB_TABLE_HASHSZ 1
  150. #endif
  151. static struct hlist_head fib_table_hash[FIB_TABLE_HASHSZ];
  152. static void fib6_link_table(struct fib6_table *tb)
  153. {
  154. unsigned int h;
  155. /*
  156. * Initialize table lock at a single place to give lockdep a key,
  157. * tables aren't visible prior to being linked to the list.
  158. */
  159. rwlock_init(&tb->tb6_lock);
  160. h = tb->tb6_id & (FIB_TABLE_HASHSZ - 1);
  161. /*
  162. * No protection necessary, this is the only list mutatation
  163. * operation, tables never disappear once they exist.
  164. */
  165. hlist_add_head_rcu(&tb->tb6_hlist, &fib_table_hash[h]);
  166. }
  167. #ifdef CONFIG_IPV6_MULTIPLE_TABLES
  168. static struct fib6_table fib6_local_tbl = {
  169. .tb6_id = RT6_TABLE_LOCAL,
  170. .tb6_root = {
  171. .leaf = &ip6_null_entry,
  172. .fn_flags = RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO,
  173. },
  174. };
  175. static struct fib6_table *fib6_alloc_table(u32 id)
  176. {
  177. struct fib6_table *table;
  178. table = kzalloc(sizeof(*table), GFP_ATOMIC);
  179. if (table != NULL) {
  180. table->tb6_id = id;
  181. table->tb6_root.leaf = &ip6_null_entry;
  182. table->tb6_root.fn_flags = RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
  183. }
  184. return table;
  185. }
  186. struct fib6_table *fib6_new_table(u32 id)
  187. {
  188. struct fib6_table *tb;
  189. if (id == 0)
  190. id = RT6_TABLE_MAIN;
  191. tb = fib6_get_table(id);
  192. if (tb)
  193. return tb;
  194. tb = fib6_alloc_table(id);
  195. if (tb != NULL)
  196. fib6_link_table(tb);
  197. return tb;
  198. }
  199. struct fib6_table *fib6_get_table(u32 id)
  200. {
  201. struct fib6_table *tb;
  202. struct hlist_node *node;
  203. unsigned int h;
  204. if (id == 0)
  205. id = RT6_TABLE_MAIN;
  206. h = id & (FIB_TABLE_HASHSZ - 1);
  207. rcu_read_lock();
  208. hlist_for_each_entry_rcu(tb, node, &fib_table_hash[h], tb6_hlist) {
  209. if (tb->tb6_id == id) {
  210. rcu_read_unlock();
  211. return tb;
  212. }
  213. }
  214. rcu_read_unlock();
  215. return NULL;
  216. }
  217. static void __init fib6_tables_init(void)
  218. {
  219. fib6_link_table(&fib6_main_tbl);
  220. fib6_link_table(&fib6_local_tbl);
  221. }
  222. #else
  223. struct fib6_table *fib6_new_table(u32 id)
  224. {
  225. return fib6_get_table(id);
  226. }
  227. struct fib6_table *fib6_get_table(u32 id)
  228. {
  229. return &fib6_main_tbl;
  230. }
  231. struct dst_entry *fib6_rule_lookup(struct flowi *fl, int flags,
  232. pol_lookup_t lookup)
  233. {
  234. return (struct dst_entry *) lookup(&fib6_main_tbl, fl, flags);
  235. }
  236. static void __init fib6_tables_init(void)
  237. {
  238. fib6_link_table(&fib6_main_tbl);
  239. }
  240. #endif
  241. static int fib6_dump_node(struct fib6_walker_t *w)
  242. {
  243. int res;
  244. struct rt6_info *rt;
  245. for (rt = w->leaf; rt; rt = rt->u.dst.rt6_next) {
  246. res = rt6_dump_route(rt, w->args);
  247. if (res < 0) {
  248. /* Frame is full, suspend walking */
  249. w->leaf = rt;
  250. return 1;
  251. }
  252. BUG_TRAP(res!=0);
  253. }
  254. w->leaf = NULL;
  255. return 0;
  256. }
  257. static void fib6_dump_end(struct netlink_callback *cb)
  258. {
  259. struct fib6_walker_t *w = (void*)cb->args[2];
  260. if (w) {
  261. cb->args[2] = 0;
  262. kfree(w);
  263. }
  264. cb->done = (void*)cb->args[3];
  265. cb->args[1] = 3;
  266. }
  267. static int fib6_dump_done(struct netlink_callback *cb)
  268. {
  269. fib6_dump_end(cb);
  270. return cb->done ? cb->done(cb) : 0;
  271. }
  272. static int fib6_dump_table(struct fib6_table *table, struct sk_buff *skb,
  273. struct netlink_callback *cb)
  274. {
  275. struct fib6_walker_t *w;
  276. int res;
  277. w = (void *)cb->args[2];
  278. w->root = &table->tb6_root;
  279. if (cb->args[4] == 0) {
  280. read_lock_bh(&table->tb6_lock);
  281. res = fib6_walk(w);
  282. read_unlock_bh(&table->tb6_lock);
  283. if (res > 0)
  284. cb->args[4] = 1;
  285. } else {
  286. read_lock_bh(&table->tb6_lock);
  287. res = fib6_walk_continue(w);
  288. read_unlock_bh(&table->tb6_lock);
  289. if (res != 0) {
  290. if (res < 0)
  291. fib6_walker_unlink(w);
  292. goto end;
  293. }
  294. fib6_walker_unlink(w);
  295. cb->args[4] = 0;
  296. }
  297. end:
  298. return res;
  299. }
  300. int inet6_dump_fib(struct sk_buff *skb, struct netlink_callback *cb)
  301. {
  302. unsigned int h, s_h;
  303. unsigned int e = 0, s_e;
  304. struct rt6_rtnl_dump_arg arg;
  305. struct fib6_walker_t *w;
  306. struct fib6_table *tb;
  307. struct hlist_node *node;
  308. int res = 0;
  309. s_h = cb->args[0];
  310. s_e = cb->args[1];
  311. w = (void *)cb->args[2];
  312. if (w == NULL) {
  313. /* New dump:
  314. *
  315. * 1. hook callback destructor.
  316. */
  317. cb->args[3] = (long)cb->done;
  318. cb->done = fib6_dump_done;
  319. /*
  320. * 2. allocate and initialize walker.
  321. */
  322. w = kzalloc(sizeof(*w), GFP_ATOMIC);
  323. if (w == NULL)
  324. return -ENOMEM;
  325. w->func = fib6_dump_node;
  326. cb->args[2] = (long)w;
  327. }
  328. arg.skb = skb;
  329. arg.cb = cb;
  330. w->args = &arg;
  331. for (h = s_h; h < FIB_TABLE_HASHSZ; h++, s_e = 0) {
  332. e = 0;
  333. hlist_for_each_entry(tb, node, &fib_table_hash[h], tb6_hlist) {
  334. if (e < s_e)
  335. goto next;
  336. res = fib6_dump_table(tb, skb, cb);
  337. if (res != 0)
  338. goto out;
  339. next:
  340. e++;
  341. }
  342. }
  343. out:
  344. cb->args[1] = e;
  345. cb->args[0] = h;
  346. res = res < 0 ? res : skb->len;
  347. if (res <= 0)
  348. fib6_dump_end(cb);
  349. return res;
  350. }
  351. /*
  352. * Routing Table
  353. *
  354. * return the appropriate node for a routing tree "add" operation
  355. * by either creating and inserting or by returning an existing
  356. * node.
  357. */
  358. static struct fib6_node * fib6_add_1(struct fib6_node *root, void *addr,
  359. int addrlen, int plen,
  360. int offset)
  361. {
  362. struct fib6_node *fn, *in, *ln;
  363. struct fib6_node *pn = NULL;
  364. struct rt6key *key;
  365. int bit;
  366. __be32 dir = 0;
  367. __u32 sernum = fib6_new_sernum();
  368. RT6_TRACE("fib6_add_1\n");
  369. /* insert node in tree */
  370. fn = root;
  371. do {
  372. key = (struct rt6key *)((u8 *)fn->leaf + offset);
  373. /*
  374. * Prefix match
  375. */
  376. if (plen < fn->fn_bit ||
  377. !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
  378. goto insert_above;
  379. /*
  380. * Exact match ?
  381. */
  382. if (plen == fn->fn_bit) {
  383. /* clean up an intermediate node */
  384. if ((fn->fn_flags & RTN_RTINFO) == 0) {
  385. rt6_release(fn->leaf);
  386. fn->leaf = NULL;
  387. }
  388. fn->fn_sernum = sernum;
  389. return fn;
  390. }
  391. /*
  392. * We have more bits to go
  393. */
  394. /* Try to walk down on tree. */
  395. fn->fn_sernum = sernum;
  396. dir = addr_bit_set(addr, fn->fn_bit);
  397. pn = fn;
  398. fn = dir ? fn->right: fn->left;
  399. } while (fn);
  400. /*
  401. * We walked to the bottom of tree.
  402. * Create new leaf node without children.
  403. */
  404. ln = node_alloc();
  405. if (ln == NULL)
  406. return NULL;
  407. ln->fn_bit = plen;
  408. ln->parent = pn;
  409. ln->fn_sernum = sernum;
  410. if (dir)
  411. pn->right = ln;
  412. else
  413. pn->left = ln;
  414. return ln;
  415. insert_above:
  416. /*
  417. * split since we don't have a common prefix anymore or
  418. * we have a less significant route.
  419. * we've to insert an intermediate node on the list
  420. * this new node will point to the one we need to create
  421. * and the current
  422. */
  423. pn = fn->parent;
  424. /* find 1st bit in difference between the 2 addrs.
  425. See comment in __ipv6_addr_diff: bit may be an invalid value,
  426. but if it is >= plen, the value is ignored in any case.
  427. */
  428. bit = __ipv6_addr_diff(addr, &key->addr, addrlen);
  429. /*
  430. * (intermediate)[in]
  431. * / \
  432. * (new leaf node)[ln] (old node)[fn]
  433. */
  434. if (plen > bit) {
  435. in = node_alloc();
  436. ln = node_alloc();
  437. if (in == NULL || ln == NULL) {
  438. if (in)
  439. node_free(in);
  440. if (ln)
  441. node_free(ln);
  442. return NULL;
  443. }
  444. /*
  445. * new intermediate node.
  446. * RTN_RTINFO will
  447. * be off since that an address that chooses one of
  448. * the branches would not match less specific routes
  449. * in the other branch
  450. */
  451. in->fn_bit = bit;
  452. in->parent = pn;
  453. in->leaf = fn->leaf;
  454. atomic_inc(&in->leaf->rt6i_ref);
  455. in->fn_sernum = sernum;
  456. /* update parent pointer */
  457. if (dir)
  458. pn->right = in;
  459. else
  460. pn->left = in;
  461. ln->fn_bit = plen;
  462. ln->parent = in;
  463. fn->parent = in;
  464. ln->fn_sernum = sernum;
  465. if (addr_bit_set(addr, bit)) {
  466. in->right = ln;
  467. in->left = fn;
  468. } else {
  469. in->left = ln;
  470. in->right = fn;
  471. }
  472. } else { /* plen <= bit */
  473. /*
  474. * (new leaf node)[ln]
  475. * / \
  476. * (old node)[fn] NULL
  477. */
  478. ln = node_alloc();
  479. if (ln == NULL)
  480. return NULL;
  481. ln->fn_bit = plen;
  482. ln->parent = pn;
  483. ln->fn_sernum = sernum;
  484. if (dir)
  485. pn->right = ln;
  486. else
  487. pn->left = ln;
  488. if (addr_bit_set(&key->addr, plen))
  489. ln->right = fn;
  490. else
  491. ln->left = fn;
  492. fn->parent = ln;
  493. }
  494. return ln;
  495. }
  496. /*
  497. * Insert routing information in a node.
  498. */
  499. static int fib6_add_rt2node(struct fib6_node *fn, struct rt6_info *rt,
  500. struct nl_info *info)
  501. {
  502. struct rt6_info *iter = NULL;
  503. struct rt6_info **ins;
  504. ins = &fn->leaf;
  505. for (iter = fn->leaf; iter; iter=iter->u.dst.rt6_next) {
  506. /*
  507. * Search for duplicates
  508. */
  509. if (iter->rt6i_metric == rt->rt6i_metric) {
  510. /*
  511. * Same priority level
  512. */
  513. if (iter->rt6i_dev == rt->rt6i_dev &&
  514. iter->rt6i_idev == rt->rt6i_idev &&
  515. ipv6_addr_equal(&iter->rt6i_gateway,
  516. &rt->rt6i_gateway)) {
  517. if (!(iter->rt6i_flags&RTF_EXPIRES))
  518. return -EEXIST;
  519. iter->rt6i_expires = rt->rt6i_expires;
  520. if (!(rt->rt6i_flags&RTF_EXPIRES)) {
  521. iter->rt6i_flags &= ~RTF_EXPIRES;
  522. iter->rt6i_expires = 0;
  523. }
  524. return -EEXIST;
  525. }
  526. }
  527. if (iter->rt6i_metric > rt->rt6i_metric)
  528. break;
  529. ins = &iter->u.dst.rt6_next;
  530. }
  531. /* Reset round-robin state, if necessary */
  532. if (ins == &fn->leaf)
  533. fn->rr_ptr = NULL;
  534. /*
  535. * insert node
  536. */
  537. out:
  538. rt->u.dst.rt6_next = iter;
  539. *ins = rt;
  540. rt->rt6i_node = fn;
  541. atomic_inc(&rt->rt6i_ref);
  542. inet6_rt_notify(RTM_NEWROUTE, rt, info);
  543. rt6_stats.fib_rt_entries++;
  544. if ((fn->fn_flags & RTN_RTINFO) == 0) {
  545. rt6_stats.fib_route_nodes++;
  546. fn->fn_flags |= RTN_RTINFO;
  547. }
  548. return 0;
  549. }
  550. static __inline__ void fib6_start_gc(struct rt6_info *rt)
  551. {
  552. if (ip6_fib_timer.expires == 0 &&
  553. (rt->rt6i_flags & (RTF_EXPIRES|RTF_CACHE)))
  554. mod_timer(&ip6_fib_timer, jiffies + ip6_rt_gc_interval);
  555. }
  556. void fib6_force_start_gc(void)
  557. {
  558. if (ip6_fib_timer.expires == 0)
  559. mod_timer(&ip6_fib_timer, jiffies + ip6_rt_gc_interval);
  560. }
  561. /*
  562. * Add routing information to the routing tree.
  563. * <destination addr>/<source addr>
  564. * with source addr info in sub-trees
  565. */
  566. int fib6_add(struct fib6_node *root, struct rt6_info *rt, struct nl_info *info)
  567. {
  568. struct fib6_node *fn, *pn = NULL;
  569. int err = -ENOMEM;
  570. fn = fib6_add_1(root, &rt->rt6i_dst.addr, sizeof(struct in6_addr),
  571. rt->rt6i_dst.plen, offsetof(struct rt6_info, rt6i_dst));
  572. if (fn == NULL)
  573. goto out;
  574. pn = fn;
  575. #ifdef CONFIG_IPV6_SUBTREES
  576. if (rt->rt6i_src.plen) {
  577. struct fib6_node *sn;
  578. if (fn->subtree == NULL) {
  579. struct fib6_node *sfn;
  580. /*
  581. * Create subtree.
  582. *
  583. * fn[main tree]
  584. * |
  585. * sfn[subtree root]
  586. * \
  587. * sn[new leaf node]
  588. */
  589. /* Create subtree root node */
  590. sfn = node_alloc();
  591. if (sfn == NULL)
  592. goto st_failure;
  593. sfn->leaf = &ip6_null_entry;
  594. atomic_inc(&ip6_null_entry.rt6i_ref);
  595. sfn->fn_flags = RTN_ROOT;
  596. sfn->fn_sernum = fib6_new_sernum();
  597. /* Now add the first leaf node to new subtree */
  598. sn = fib6_add_1(sfn, &rt->rt6i_src.addr,
  599. sizeof(struct in6_addr), rt->rt6i_src.plen,
  600. offsetof(struct rt6_info, rt6i_src));
  601. if (sn == NULL) {
  602. /* If it is failed, discard just allocated
  603. root, and then (in st_failure) stale node
  604. in main tree.
  605. */
  606. node_free(sfn);
  607. goto st_failure;
  608. }
  609. /* Now link new subtree to main tree */
  610. sfn->parent = fn;
  611. fn->subtree = sfn;
  612. } else {
  613. sn = fib6_add_1(fn->subtree, &rt->rt6i_src.addr,
  614. sizeof(struct in6_addr), rt->rt6i_src.plen,
  615. offsetof(struct rt6_info, rt6i_src));
  616. if (sn == NULL)
  617. goto st_failure;
  618. }
  619. if (fn->leaf == NULL) {
  620. fn->leaf = rt;
  621. atomic_inc(&rt->rt6i_ref);
  622. }
  623. fn = sn;
  624. }
  625. #endif
  626. err = fib6_add_rt2node(fn, rt, info);
  627. if (err == 0) {
  628. fib6_start_gc(rt);
  629. if (!(rt->rt6i_flags&RTF_CACHE))
  630. fib6_prune_clones(pn, rt);
  631. }
  632. out:
  633. if (err) {
  634. #ifdef CONFIG_IPV6_SUBTREES
  635. /*
  636. * If fib6_add_1 has cleared the old leaf pointer in the
  637. * super-tree leaf node we have to find a new one for it.
  638. */
  639. if (pn != fn && !pn->leaf && !(pn->fn_flags & RTN_RTINFO)) {
  640. pn->leaf = fib6_find_prefix(pn);
  641. #if RT6_DEBUG >= 2
  642. if (!pn->leaf) {
  643. BUG_TRAP(pn->leaf != NULL);
  644. pn->leaf = &ip6_null_entry;
  645. }
  646. #endif
  647. atomic_inc(&pn->leaf->rt6i_ref);
  648. }
  649. #endif
  650. dst_free(&rt->u.dst);
  651. }
  652. return err;
  653. #ifdef CONFIG_IPV6_SUBTREES
  654. /* Subtree creation failed, probably main tree node
  655. is orphan. If it is, shoot it.
  656. */
  657. st_failure:
  658. if (fn && !(fn->fn_flags & (RTN_RTINFO|RTN_ROOT)))
  659. fib6_repair_tree(fn);
  660. dst_free(&rt->u.dst);
  661. return err;
  662. #endif
  663. }
  664. /*
  665. * Routing tree lookup
  666. *
  667. */
  668. struct lookup_args {
  669. int offset; /* key offset on rt6_info */
  670. struct in6_addr *addr; /* search key */
  671. };
  672. static struct fib6_node * fib6_lookup_1(struct fib6_node *root,
  673. struct lookup_args *args)
  674. {
  675. struct fib6_node *fn;
  676. __be32 dir;
  677. if (unlikely(args->offset == 0))
  678. return NULL;
  679. /*
  680. * Descend on a tree
  681. */
  682. fn = root;
  683. for (;;) {
  684. struct fib6_node *next;
  685. dir = addr_bit_set(args->addr, fn->fn_bit);
  686. next = dir ? fn->right : fn->left;
  687. if (next) {
  688. fn = next;
  689. continue;
  690. }
  691. break;
  692. }
  693. while(fn) {
  694. if (FIB6_SUBTREE(fn) || fn->fn_flags & RTN_RTINFO) {
  695. struct rt6key *key;
  696. key = (struct rt6key *) ((u8 *) fn->leaf +
  697. args->offset);
  698. if (ipv6_prefix_equal(&key->addr, args->addr, key->plen)) {
  699. #ifdef CONFIG_IPV6_SUBTREES
  700. if (fn->subtree)
  701. fn = fib6_lookup_1(fn->subtree, args + 1);
  702. #endif
  703. if (!fn || fn->fn_flags & RTN_RTINFO)
  704. return fn;
  705. }
  706. }
  707. if (fn->fn_flags & RTN_ROOT)
  708. break;
  709. fn = fn->parent;
  710. }
  711. return NULL;
  712. }
  713. struct fib6_node * fib6_lookup(struct fib6_node *root, struct in6_addr *daddr,
  714. struct in6_addr *saddr)
  715. {
  716. struct fib6_node *fn;
  717. struct lookup_args args[] = {
  718. {
  719. .offset = offsetof(struct rt6_info, rt6i_dst),
  720. .addr = daddr,
  721. },
  722. #ifdef CONFIG_IPV6_SUBTREES
  723. {
  724. .offset = offsetof(struct rt6_info, rt6i_src),
  725. .addr = saddr,
  726. },
  727. #endif
  728. {
  729. .offset = 0, /* sentinel */
  730. }
  731. };
  732. fn = fib6_lookup_1(root, daddr ? args : args + 1);
  733. if (fn == NULL || fn->fn_flags & RTN_TL_ROOT)
  734. fn = root;
  735. return fn;
  736. }
  737. /*
  738. * Get node with specified destination prefix (and source prefix,
  739. * if subtrees are used)
  740. */
  741. static struct fib6_node * fib6_locate_1(struct fib6_node *root,
  742. struct in6_addr *addr,
  743. int plen, int offset)
  744. {
  745. struct fib6_node *fn;
  746. for (fn = root; fn ; ) {
  747. struct rt6key *key = (struct rt6key *)((u8 *)fn->leaf + offset);
  748. /*
  749. * Prefix match
  750. */
  751. if (plen < fn->fn_bit ||
  752. !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
  753. return NULL;
  754. if (plen == fn->fn_bit)
  755. return fn;
  756. /*
  757. * We have more bits to go
  758. */
  759. if (addr_bit_set(addr, fn->fn_bit))
  760. fn = fn->right;
  761. else
  762. fn = fn->left;
  763. }
  764. return NULL;
  765. }
  766. struct fib6_node * fib6_locate(struct fib6_node *root,
  767. struct in6_addr *daddr, int dst_len,
  768. struct in6_addr *saddr, int src_len)
  769. {
  770. struct fib6_node *fn;
  771. fn = fib6_locate_1(root, daddr, dst_len,
  772. offsetof(struct rt6_info, rt6i_dst));
  773. #ifdef CONFIG_IPV6_SUBTREES
  774. if (src_len) {
  775. BUG_TRAP(saddr!=NULL);
  776. if (fn && fn->subtree)
  777. fn = fib6_locate_1(fn->subtree, saddr, src_len,
  778. offsetof(struct rt6_info, rt6i_src));
  779. }
  780. #endif
  781. if (fn && fn->fn_flags&RTN_RTINFO)
  782. return fn;
  783. return NULL;
  784. }
  785. /*
  786. * Deletion
  787. *
  788. */
  789. static struct rt6_info * fib6_find_prefix(struct fib6_node *fn)
  790. {
  791. if (fn->fn_flags&RTN_ROOT)
  792. return &ip6_null_entry;
  793. while(fn) {
  794. if(fn->left)
  795. return fn->left->leaf;
  796. if(fn->right)
  797. return fn->right->leaf;
  798. fn = FIB6_SUBTREE(fn);
  799. }
  800. return NULL;
  801. }
  802. /*
  803. * Called to trim the tree of intermediate nodes when possible. "fn"
  804. * is the node we want to try and remove.
  805. */
  806. static struct fib6_node * fib6_repair_tree(struct fib6_node *fn)
  807. {
  808. int children;
  809. int nstate;
  810. struct fib6_node *child, *pn;
  811. struct fib6_walker_t *w;
  812. int iter = 0;
  813. for (;;) {
  814. RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);
  815. iter++;
  816. BUG_TRAP(!(fn->fn_flags&RTN_RTINFO));
  817. BUG_TRAP(!(fn->fn_flags&RTN_TL_ROOT));
  818. BUG_TRAP(fn->leaf==NULL);
  819. children = 0;
  820. child = NULL;
  821. if (fn->right) child = fn->right, children |= 1;
  822. if (fn->left) child = fn->left, children |= 2;
  823. if (children == 3 || FIB6_SUBTREE(fn)
  824. #ifdef CONFIG_IPV6_SUBTREES
  825. /* Subtree root (i.e. fn) may have one child */
  826. || (children && fn->fn_flags&RTN_ROOT)
  827. #endif
  828. ) {
  829. fn->leaf = fib6_find_prefix(fn);
  830. #if RT6_DEBUG >= 2
  831. if (fn->leaf==NULL) {
  832. BUG_TRAP(fn->leaf);
  833. fn->leaf = &ip6_null_entry;
  834. }
  835. #endif
  836. atomic_inc(&fn->leaf->rt6i_ref);
  837. return fn->parent;
  838. }
  839. pn = fn->parent;
  840. #ifdef CONFIG_IPV6_SUBTREES
  841. if (FIB6_SUBTREE(pn) == fn) {
  842. BUG_TRAP(fn->fn_flags&RTN_ROOT);
  843. FIB6_SUBTREE(pn) = NULL;
  844. nstate = FWS_L;
  845. } else {
  846. BUG_TRAP(!(fn->fn_flags&RTN_ROOT));
  847. #endif
  848. if (pn->right == fn) pn->right = child;
  849. else if (pn->left == fn) pn->left = child;
  850. #if RT6_DEBUG >= 2
  851. else BUG_TRAP(0);
  852. #endif
  853. if (child)
  854. child->parent = pn;
  855. nstate = FWS_R;
  856. #ifdef CONFIG_IPV6_SUBTREES
  857. }
  858. #endif
  859. read_lock(&fib6_walker_lock);
  860. FOR_WALKERS(w) {
  861. if (child == NULL) {
  862. if (w->root == fn) {
  863. w->root = w->node = NULL;
  864. RT6_TRACE("W %p adjusted by delroot 1\n", w);
  865. } else if (w->node == fn) {
  866. RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w, w->state, nstate);
  867. w->node = pn;
  868. w->state = nstate;
  869. }
  870. } else {
  871. if (w->root == fn) {
  872. w->root = child;
  873. RT6_TRACE("W %p adjusted by delroot 2\n", w);
  874. }
  875. if (w->node == fn) {
  876. w->node = child;
  877. if (children&2) {
  878. RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
  879. w->state = w->state>=FWS_R ? FWS_U : FWS_INIT;
  880. } else {
  881. RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
  882. w->state = w->state>=FWS_C ? FWS_U : FWS_INIT;
  883. }
  884. }
  885. }
  886. }
  887. read_unlock(&fib6_walker_lock);
  888. node_free(fn);
  889. if (pn->fn_flags&RTN_RTINFO || FIB6_SUBTREE(pn))
  890. return pn;
  891. rt6_release(pn->leaf);
  892. pn->leaf = NULL;
  893. fn = pn;
  894. }
  895. }
  896. static void fib6_del_route(struct fib6_node *fn, struct rt6_info **rtp,
  897. struct nl_info *info)
  898. {
  899. struct fib6_walker_t *w;
  900. struct rt6_info *rt = *rtp;
  901. RT6_TRACE("fib6_del_route\n");
  902. /* Unlink it */
  903. *rtp = rt->u.dst.rt6_next;
  904. rt->rt6i_node = NULL;
  905. rt6_stats.fib_rt_entries--;
  906. rt6_stats.fib_discarded_routes++;
  907. /* Reset round-robin state, if necessary */
  908. if (fn->rr_ptr == rt)
  909. fn->rr_ptr = NULL;
  910. /* Adjust walkers */
  911. read_lock(&fib6_walker_lock);
  912. FOR_WALKERS(w) {
  913. if (w->state == FWS_C && w->leaf == rt) {
  914. RT6_TRACE("walker %p adjusted by delroute\n", w);
  915. w->leaf = rt->u.dst.rt6_next;
  916. if (w->leaf == NULL)
  917. w->state = FWS_U;
  918. }
  919. }
  920. read_unlock(&fib6_walker_lock);
  921. rt->u.dst.rt6_next = NULL;
  922. if (fn->leaf == NULL && fn->fn_flags&RTN_TL_ROOT)
  923. fn->leaf = &ip6_null_entry;
  924. /* If it was last route, expunge its radix tree node */
  925. if (fn->leaf == NULL) {
  926. fn->fn_flags &= ~RTN_RTINFO;
  927. rt6_stats.fib_route_nodes--;
  928. fn = fib6_repair_tree(fn);
  929. }
  930. if (atomic_read(&rt->rt6i_ref) != 1) {
  931. /* This route is used as dummy address holder in some split
  932. * nodes. It is not leaked, but it still holds other resources,
  933. * which must be released in time. So, scan ascendant nodes
  934. * and replace dummy references to this route with references
  935. * to still alive ones.
  936. */
  937. while (fn) {
  938. if (!(fn->fn_flags&RTN_RTINFO) && fn->leaf == rt) {
  939. fn->leaf = fib6_find_prefix(fn);
  940. atomic_inc(&fn->leaf->rt6i_ref);
  941. rt6_release(rt);
  942. }
  943. fn = fn->parent;
  944. }
  945. /* No more references are possible at this point. */
  946. if (atomic_read(&rt->rt6i_ref) != 1) BUG();
  947. }
  948. inet6_rt_notify(RTM_DELROUTE, rt, info);
  949. rt6_release(rt);
  950. }
  951. int fib6_del(struct rt6_info *rt, struct nl_info *info)
  952. {
  953. struct fib6_node *fn = rt->rt6i_node;
  954. struct rt6_info **rtp;
  955. #if RT6_DEBUG >= 2
  956. if (rt->u.dst.obsolete>0) {
  957. BUG_TRAP(fn==NULL);
  958. return -ENOENT;
  959. }
  960. #endif
  961. if (fn == NULL || rt == &ip6_null_entry)
  962. return -ENOENT;
  963. BUG_TRAP(fn->fn_flags&RTN_RTINFO);
  964. if (!(rt->rt6i_flags&RTF_CACHE)) {
  965. struct fib6_node *pn = fn;
  966. #ifdef CONFIG_IPV6_SUBTREES
  967. /* clones of this route might be in another subtree */
  968. if (rt->rt6i_src.plen) {
  969. while (!(pn->fn_flags&RTN_ROOT))
  970. pn = pn->parent;
  971. pn = pn->parent;
  972. }
  973. #endif
  974. fib6_prune_clones(pn, rt);
  975. }
  976. /*
  977. * Walk the leaf entries looking for ourself
  978. */
  979. for (rtp = &fn->leaf; *rtp; rtp = &(*rtp)->u.dst.rt6_next) {
  980. if (*rtp == rt) {
  981. fib6_del_route(fn, rtp, info);
  982. return 0;
  983. }
  984. }
  985. return -ENOENT;
  986. }
  987. /*
  988. * Tree traversal function.
  989. *
  990. * Certainly, it is not interrupt safe.
  991. * However, it is internally reenterable wrt itself and fib6_add/fib6_del.
  992. * It means, that we can modify tree during walking
  993. * and use this function for garbage collection, clone pruning,
  994. * cleaning tree when a device goes down etc. etc.
  995. *
  996. * It guarantees that every node will be traversed,
  997. * and that it will be traversed only once.
  998. *
  999. * Callback function w->func may return:
  1000. * 0 -> continue walking.
  1001. * positive value -> walking is suspended (used by tree dumps,
  1002. * and probably by gc, if it will be split to several slices)
  1003. * negative value -> terminate walking.
  1004. *
  1005. * The function itself returns:
  1006. * 0 -> walk is complete.
  1007. * >0 -> walk is incomplete (i.e. suspended)
  1008. * <0 -> walk is terminated by an error.
  1009. */
  1010. static int fib6_walk_continue(struct fib6_walker_t *w)
  1011. {
  1012. struct fib6_node *fn, *pn;
  1013. for (;;) {
  1014. fn = w->node;
  1015. if (fn == NULL)
  1016. return 0;
  1017. if (w->prune && fn != w->root &&
  1018. fn->fn_flags&RTN_RTINFO && w->state < FWS_C) {
  1019. w->state = FWS_C;
  1020. w->leaf = fn->leaf;
  1021. }
  1022. switch (w->state) {
  1023. #ifdef CONFIG_IPV6_SUBTREES
  1024. case FWS_S:
  1025. if (FIB6_SUBTREE(fn)) {
  1026. w->node = FIB6_SUBTREE(fn);
  1027. continue;
  1028. }
  1029. w->state = FWS_L;
  1030. #endif
  1031. case FWS_L:
  1032. if (fn->left) {
  1033. w->node = fn->left;
  1034. w->state = FWS_INIT;
  1035. continue;
  1036. }
  1037. w->state = FWS_R;
  1038. case FWS_R:
  1039. if (fn->right) {
  1040. w->node = fn->right;
  1041. w->state = FWS_INIT;
  1042. continue;
  1043. }
  1044. w->state = FWS_C;
  1045. w->leaf = fn->leaf;
  1046. case FWS_C:
  1047. if (w->leaf && fn->fn_flags&RTN_RTINFO) {
  1048. int err = w->func(w);
  1049. if (err)
  1050. return err;
  1051. continue;
  1052. }
  1053. w->state = FWS_U;
  1054. case FWS_U:
  1055. if (fn == w->root)
  1056. return 0;
  1057. pn = fn->parent;
  1058. w->node = pn;
  1059. #ifdef CONFIG_IPV6_SUBTREES
  1060. if (FIB6_SUBTREE(pn) == fn) {
  1061. BUG_TRAP(fn->fn_flags&RTN_ROOT);
  1062. w->state = FWS_L;
  1063. continue;
  1064. }
  1065. #endif
  1066. if (pn->left == fn) {
  1067. w->state = FWS_R;
  1068. continue;
  1069. }
  1070. if (pn->right == fn) {
  1071. w->state = FWS_C;
  1072. w->leaf = w->node->leaf;
  1073. continue;
  1074. }
  1075. #if RT6_DEBUG >= 2
  1076. BUG_TRAP(0);
  1077. #endif
  1078. }
  1079. }
  1080. }
  1081. static int fib6_walk(struct fib6_walker_t *w)
  1082. {
  1083. int res;
  1084. w->state = FWS_INIT;
  1085. w->node = w->root;
  1086. fib6_walker_link(w);
  1087. res = fib6_walk_continue(w);
  1088. if (res <= 0)
  1089. fib6_walker_unlink(w);
  1090. return res;
  1091. }
  1092. static int fib6_clean_node(struct fib6_walker_t *w)
  1093. {
  1094. int res;
  1095. struct rt6_info *rt;
  1096. struct fib6_cleaner_t *c = (struct fib6_cleaner_t*)w;
  1097. for (rt = w->leaf; rt; rt = rt->u.dst.rt6_next) {
  1098. res = c->func(rt, c->arg);
  1099. if (res < 0) {
  1100. w->leaf = rt;
  1101. res = fib6_del(rt, NULL);
  1102. if (res) {
  1103. #if RT6_DEBUG >= 2
  1104. printk(KERN_DEBUG "fib6_clean_node: del failed: rt=%p@%p err=%d\n", rt, rt->rt6i_node, res);
  1105. #endif
  1106. continue;
  1107. }
  1108. return 0;
  1109. }
  1110. BUG_TRAP(res==0);
  1111. }
  1112. w->leaf = rt;
  1113. return 0;
  1114. }
  1115. /*
  1116. * Convenient frontend to tree walker.
  1117. *
  1118. * func is called on each route.
  1119. * It may return -1 -> delete this route.
  1120. * 0 -> continue walking
  1121. *
  1122. * prune==1 -> only immediate children of node (certainly,
  1123. * ignoring pure split nodes) will be scanned.
  1124. */
  1125. static void fib6_clean_tree(struct fib6_node *root,
  1126. int (*func)(struct rt6_info *, void *arg),
  1127. int prune, void *arg)
  1128. {
  1129. struct fib6_cleaner_t c;
  1130. c.w.root = root;
  1131. c.w.func = fib6_clean_node;
  1132. c.w.prune = prune;
  1133. c.func = func;
  1134. c.arg = arg;
  1135. fib6_walk(&c.w);
  1136. }
  1137. void fib6_clean_all(int (*func)(struct rt6_info *, void *arg),
  1138. int prune, void *arg)
  1139. {
  1140. struct fib6_table *table;
  1141. struct hlist_node *node;
  1142. unsigned int h;
  1143. rcu_read_lock();
  1144. for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
  1145. hlist_for_each_entry_rcu(table, node, &fib_table_hash[h],
  1146. tb6_hlist) {
  1147. write_lock_bh(&table->tb6_lock);
  1148. fib6_clean_tree(&table->tb6_root, func, prune, arg);
  1149. write_unlock_bh(&table->tb6_lock);
  1150. }
  1151. }
  1152. rcu_read_unlock();
  1153. }
  1154. static int fib6_prune_clone(struct rt6_info *rt, void *arg)
  1155. {
  1156. if (rt->rt6i_flags & RTF_CACHE) {
  1157. RT6_TRACE("pruning clone %p\n", rt);
  1158. return -1;
  1159. }
  1160. return 0;
  1161. }
  1162. static void fib6_prune_clones(struct fib6_node *fn, struct rt6_info *rt)
  1163. {
  1164. fib6_clean_tree(fn, fib6_prune_clone, 1, rt);
  1165. }
  1166. /*
  1167. * Garbage collection
  1168. */
  1169. static struct fib6_gc_args
  1170. {
  1171. int timeout;
  1172. int more;
  1173. } gc_args;
  1174. static int fib6_age(struct rt6_info *rt, void *arg)
  1175. {
  1176. unsigned long now = jiffies;
  1177. /*
  1178. * check addrconf expiration here.
  1179. * Routes are expired even if they are in use.
  1180. *
  1181. * Also age clones. Note, that clones are aged out
  1182. * only if they are not in use now.
  1183. */
  1184. if (rt->rt6i_flags&RTF_EXPIRES && rt->rt6i_expires) {
  1185. if (time_after(now, rt->rt6i_expires)) {
  1186. RT6_TRACE("expiring %p\n", rt);
  1187. return -1;
  1188. }
  1189. gc_args.more++;
  1190. } else if (rt->rt6i_flags & RTF_CACHE) {
  1191. if (atomic_read(&rt->u.dst.__refcnt) == 0 &&
  1192. time_after_eq(now, rt->u.dst.lastuse + gc_args.timeout)) {
  1193. RT6_TRACE("aging clone %p\n", rt);
  1194. return -1;
  1195. } else if ((rt->rt6i_flags & RTF_GATEWAY) &&
  1196. (!(rt->rt6i_nexthop->flags & NTF_ROUTER))) {
  1197. RT6_TRACE("purging route %p via non-router but gateway\n",
  1198. rt);
  1199. return -1;
  1200. }
  1201. gc_args.more++;
  1202. }
  1203. return 0;
  1204. }
  1205. static DEFINE_SPINLOCK(fib6_gc_lock);
  1206. void fib6_run_gc(unsigned long dummy)
  1207. {
  1208. if (dummy != ~0UL) {
  1209. spin_lock_bh(&fib6_gc_lock);
  1210. gc_args.timeout = dummy ? (int)dummy : ip6_rt_gc_interval;
  1211. } else {
  1212. local_bh_disable();
  1213. if (!spin_trylock(&fib6_gc_lock)) {
  1214. mod_timer(&ip6_fib_timer, jiffies + HZ);
  1215. local_bh_enable();
  1216. return;
  1217. }
  1218. gc_args.timeout = ip6_rt_gc_interval;
  1219. }
  1220. gc_args.more = 0;
  1221. ndisc_dst_gc(&gc_args.more);
  1222. fib6_clean_all(fib6_age, 0, NULL);
  1223. if (gc_args.more)
  1224. mod_timer(&ip6_fib_timer, jiffies + ip6_rt_gc_interval);
  1225. else {
  1226. del_timer(&ip6_fib_timer);
  1227. ip6_fib_timer.expires = 0;
  1228. }
  1229. spin_unlock_bh(&fib6_gc_lock);
  1230. }
  1231. void __init fib6_init(void)
  1232. {
  1233. fib6_node_kmem = kmem_cache_create("fib6_nodes",
  1234. sizeof(struct fib6_node),
  1235. 0, SLAB_HWCACHE_ALIGN|SLAB_PANIC,
  1236. NULL, NULL);
  1237. fib6_tables_init();
  1238. }
  1239. void fib6_gc_cleanup(void)
  1240. {
  1241. del_timer(&ip6_fib_timer);
  1242. kmem_cache_destroy(fib6_node_kmem);
  1243. }