ip6_fib.c 62 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715
  1. // SPDX-License-Identifier: GPL-2.0-or-later
  2. /*
  3. * Linux INET6 implementation
  4. * Forwarding Information Database
  5. *
  6. * Authors:
  7. * Pedro Roque <roque@di.fc.ul.pt>
  8. *
  9. * Changes:
  10. * Yuji SEKIYA @USAGI: Support default route on router node;
  11. * remove ip6_null_entry from the top of
  12. * routing table.
  13. * Ville Nuorvala: Fixed routing subtrees.
  14. */
  15. #define pr_fmt(fmt) "IPv6: " fmt
  16. #include <linux/errno.h>
  17. #include <linux/types.h>
  18. #include <linux/net.h>
  19. #include <linux/route.h>
  20. #include <linux/netdevice.h>
  21. #include <linux/in6.h>
  22. #include <linux/init.h>
  23. #include <linux/list.h>
  24. #include <linux/slab.h>
  25. #include <net/ip.h>
  26. #include <net/ipv6.h>
  27. #include <net/ndisc.h>
  28. #include <net/addrconf.h>
  29. #include <net/lwtunnel.h>
  30. #include <net/fib_notifier.h>
  31. #include <net/ip6_fib.h>
  32. #include <net/ip6_route.h>
  33. static struct kmem_cache *fib6_node_kmem __read_mostly;
  34. struct fib6_cleaner {
  35. struct fib6_walker w;
  36. struct net *net;
  37. int (*func)(struct fib6_info *, void *arg);
  38. int sernum;
  39. void *arg;
  40. bool skip_notify;
  41. };
  42. #ifdef CONFIG_IPV6_SUBTREES
  43. #define FWS_INIT FWS_S
  44. #else
  45. #define FWS_INIT FWS_L
  46. #endif
  47. static struct fib6_info *fib6_find_prefix(struct net *net,
  48. struct fib6_table *table,
  49. struct fib6_node *fn);
  50. static struct fib6_node *fib6_repair_tree(struct net *net,
  51. struct fib6_table *table,
  52. struct fib6_node *fn);
  53. static int fib6_walk(struct net *net, struct fib6_walker *w);
  54. static int fib6_walk_continue(struct fib6_walker *w);
  55. /*
  56. * A routing update causes an increase of the serial number on the
  57. * affected subtree. This allows for cached routes to be asynchronously
  58. * tested when modifications are made to the destination cache as a
  59. * result of redirects, path MTU changes, etc.
  60. */
  61. static void fib6_gc_timer_cb(struct timer_list *t);
  62. #define FOR_WALKERS(net, w) \
  63. list_for_each_entry(w, &(net)->ipv6.fib6_walkers, lh)
  64. static void fib6_walker_link(struct net *net, struct fib6_walker *w)
  65. {
  66. write_lock_bh(&net->ipv6.fib6_walker_lock);
  67. list_add(&w->lh, &net->ipv6.fib6_walkers);
  68. write_unlock_bh(&net->ipv6.fib6_walker_lock);
  69. }
  70. static void fib6_walker_unlink(struct net *net, struct fib6_walker *w)
  71. {
  72. write_lock_bh(&net->ipv6.fib6_walker_lock);
  73. list_del(&w->lh);
  74. write_unlock_bh(&net->ipv6.fib6_walker_lock);
  75. }
  76. static int fib6_new_sernum(struct net *net)
  77. {
  78. int new, old;
  79. do {
  80. old = atomic_read(&net->ipv6.fib6_sernum);
  81. new = old < INT_MAX ? old + 1 : 1;
  82. } while (atomic_cmpxchg(&net->ipv6.fib6_sernum,
  83. old, new) != old);
  84. return new;
  85. }
  86. enum {
  87. FIB6_NO_SERNUM_CHANGE = 0,
  88. };
  89. void fib6_update_sernum(struct net *net, struct fib6_info *f6i)
  90. {
  91. struct fib6_node *fn;
  92. fn = rcu_dereference_protected(f6i->fib6_node,
  93. lockdep_is_held(&f6i->fib6_table->tb6_lock));
  94. if (fn)
  95. WRITE_ONCE(fn->fn_sernum, fib6_new_sernum(net));
  96. }
  97. /*
  98. * Auxiliary address test functions for the radix tree.
  99. *
  100. * These assume a 32bit processor (although it will work on
  101. * 64bit processors)
  102. */
  103. /*
  104. * test bit
  105. */
  106. #if defined(__LITTLE_ENDIAN)
  107. # define BITOP_BE32_SWIZZLE (0x1F & ~7)
  108. #else
  109. # define BITOP_BE32_SWIZZLE 0
  110. #endif
  111. static __be32 addr_bit_set(const void *token, int fn_bit)
  112. {
  113. const __be32 *addr = token;
  114. /*
  115. * Here,
  116. * 1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)
  117. * is optimized version of
  118. * htonl(1 << ((~fn_bit)&0x1F))
  119. * See include/asm-generic/bitops/le.h.
  120. */
  121. return (__force __be32)(1 << ((~fn_bit ^ BITOP_BE32_SWIZZLE) & 0x1f)) &
  122. addr[fn_bit >> 5];
  123. }
  124. struct fib6_info *fib6_info_alloc(gfp_t gfp_flags, bool with_fib6_nh)
  125. {
  126. struct fib6_info *f6i;
  127. size_t sz = sizeof(*f6i);
  128. if (with_fib6_nh)
  129. sz += sizeof(struct fib6_nh);
  130. f6i = kzalloc(sz, gfp_flags);
  131. if (!f6i)
  132. return NULL;
  133. /* fib6_siblings is a union with nh_list, so this initializes both */
  134. INIT_LIST_HEAD(&f6i->fib6_siblings);
  135. refcount_set(&f6i->fib6_ref, 1);
  136. return f6i;
  137. }
  138. void fib6_info_destroy_rcu(struct rcu_head *head)
  139. {
  140. struct fib6_info *f6i = container_of(head, struct fib6_info, rcu);
  141. WARN_ON(f6i->fib6_node);
  142. if (f6i->nh)
  143. nexthop_put(f6i->nh);
  144. else
  145. fib6_nh_release(f6i->fib6_nh);
  146. ip_fib_metrics_put(f6i->fib6_metrics);
  147. kfree(f6i);
  148. }
  149. EXPORT_SYMBOL_GPL(fib6_info_destroy_rcu);
  150. static struct fib6_node *node_alloc(struct net *net)
  151. {
  152. struct fib6_node *fn;
  153. fn = kmem_cache_zalloc(fib6_node_kmem, GFP_ATOMIC);
  154. if (fn)
  155. net->ipv6.rt6_stats->fib_nodes++;
  156. return fn;
  157. }
  158. static void node_free_immediate(struct net *net, struct fib6_node *fn)
  159. {
  160. kmem_cache_free(fib6_node_kmem, fn);
  161. net->ipv6.rt6_stats->fib_nodes--;
  162. }
  163. static void node_free_rcu(struct rcu_head *head)
  164. {
  165. struct fib6_node *fn = container_of(head, struct fib6_node, rcu);
  166. kmem_cache_free(fib6_node_kmem, fn);
  167. }
  168. static void node_free(struct net *net, struct fib6_node *fn)
  169. {
  170. call_rcu(&fn->rcu, node_free_rcu);
  171. net->ipv6.rt6_stats->fib_nodes--;
  172. }
  173. static void fib6_free_table(struct fib6_table *table)
  174. {
  175. inetpeer_invalidate_tree(&table->tb6_peers);
  176. kfree(table);
  177. }
  178. static void fib6_link_table(struct net *net, struct fib6_table *tb)
  179. {
  180. unsigned int h;
  181. /*
  182. * Initialize table lock at a single place to give lockdep a key,
  183. * tables aren't visible prior to being linked to the list.
  184. */
  185. spin_lock_init(&tb->tb6_lock);
  186. h = tb->tb6_id & (FIB6_TABLE_HASHSZ - 1);
  187. /*
  188. * No protection necessary, this is the only list mutatation
  189. * operation, tables never disappear once they exist.
  190. */
  191. hlist_add_head_rcu(&tb->tb6_hlist, &net->ipv6.fib_table_hash[h]);
  192. }
  193. #ifdef CONFIG_IPV6_MULTIPLE_TABLES
  194. static struct fib6_table *fib6_alloc_table(struct net *net, u32 id)
  195. {
  196. struct fib6_table *table;
  197. table = kzalloc(sizeof(*table), GFP_ATOMIC);
  198. if (table) {
  199. table->tb6_id = id;
  200. rcu_assign_pointer(table->tb6_root.leaf,
  201. net->ipv6.fib6_null_entry);
  202. table->tb6_root.fn_flags = RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
  203. inet_peer_base_init(&table->tb6_peers);
  204. }
  205. return table;
  206. }
  207. struct fib6_table *fib6_new_table(struct net *net, u32 id)
  208. {
  209. struct fib6_table *tb;
  210. if (id == 0)
  211. id = RT6_TABLE_MAIN;
  212. tb = fib6_get_table(net, id);
  213. if (tb)
  214. return tb;
  215. tb = fib6_alloc_table(net, id);
  216. if (tb)
  217. fib6_link_table(net, tb);
  218. return tb;
  219. }
  220. EXPORT_SYMBOL_GPL(fib6_new_table);
  221. struct fib6_table *fib6_get_table(struct net *net, u32 id)
  222. {
  223. struct fib6_table *tb;
  224. struct hlist_head *head;
  225. unsigned int h;
  226. if (id == 0)
  227. id = RT6_TABLE_MAIN;
  228. h = id & (FIB6_TABLE_HASHSZ - 1);
  229. rcu_read_lock();
  230. head = &net->ipv6.fib_table_hash[h];
  231. hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
  232. if (tb->tb6_id == id) {
  233. rcu_read_unlock();
  234. return tb;
  235. }
  236. }
  237. rcu_read_unlock();
  238. return NULL;
  239. }
  240. EXPORT_SYMBOL_GPL(fib6_get_table);
  241. static void __net_init fib6_tables_init(struct net *net)
  242. {
  243. fib6_link_table(net, net->ipv6.fib6_main_tbl);
  244. fib6_link_table(net, net->ipv6.fib6_local_tbl);
  245. }
  246. #else
  247. struct fib6_table *fib6_new_table(struct net *net, u32 id)
  248. {
  249. return fib6_get_table(net, id);
  250. }
  251. struct fib6_table *fib6_get_table(struct net *net, u32 id)
  252. {
  253. return net->ipv6.fib6_main_tbl;
  254. }
  255. struct dst_entry *fib6_rule_lookup(struct net *net, struct flowi6 *fl6,
  256. const struct sk_buff *skb,
  257. int flags, pol_lookup_t lookup)
  258. {
  259. struct rt6_info *rt;
  260. rt = pol_lookup_func(lookup,
  261. net, net->ipv6.fib6_main_tbl, fl6, skb, flags);
  262. if (rt->dst.error == -EAGAIN) {
  263. ip6_rt_put_flags(rt, flags);
  264. rt = net->ipv6.ip6_null_entry;
  265. if (!(flags & RT6_LOOKUP_F_DST_NOREF))
  266. dst_hold(&rt->dst);
  267. }
  268. return &rt->dst;
  269. }
  270. /* called with rcu lock held; no reference taken on fib6_info */
  271. int fib6_lookup(struct net *net, int oif, struct flowi6 *fl6,
  272. struct fib6_result *res, int flags)
  273. {
  274. return fib6_table_lookup(net, net->ipv6.fib6_main_tbl, oif, fl6,
  275. res, flags);
  276. }
  277. static void __net_init fib6_tables_init(struct net *net)
  278. {
  279. fib6_link_table(net, net->ipv6.fib6_main_tbl);
  280. }
  281. #endif
  282. unsigned int fib6_tables_seq_read(struct net *net)
  283. {
  284. unsigned int h, fib_seq = 0;
  285. rcu_read_lock();
  286. for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
  287. struct hlist_head *head = &net->ipv6.fib_table_hash[h];
  288. struct fib6_table *tb;
  289. hlist_for_each_entry_rcu(tb, head, tb6_hlist)
  290. fib_seq += tb->fib_seq;
  291. }
  292. rcu_read_unlock();
  293. return fib_seq;
  294. }
  295. static int call_fib6_entry_notifier(struct notifier_block *nb,
  296. enum fib_event_type event_type,
  297. struct fib6_info *rt,
  298. struct netlink_ext_ack *extack)
  299. {
  300. struct fib6_entry_notifier_info info = {
  301. .info.extack = extack,
  302. .rt = rt,
  303. };
  304. return call_fib6_notifier(nb, event_type, &info.info);
  305. }
  306. static int call_fib6_multipath_entry_notifier(struct notifier_block *nb,
  307. enum fib_event_type event_type,
  308. struct fib6_info *rt,
  309. unsigned int nsiblings,
  310. struct netlink_ext_ack *extack)
  311. {
  312. struct fib6_entry_notifier_info info = {
  313. .info.extack = extack,
  314. .rt = rt,
  315. .nsiblings = nsiblings,
  316. };
  317. return call_fib6_notifier(nb, event_type, &info.info);
  318. }
  319. int call_fib6_entry_notifiers(struct net *net,
  320. enum fib_event_type event_type,
  321. struct fib6_info *rt,
  322. struct netlink_ext_ack *extack)
  323. {
  324. struct fib6_entry_notifier_info info = {
  325. .info.extack = extack,
  326. .rt = rt,
  327. };
  328. rt->fib6_table->fib_seq++;
  329. return call_fib6_notifiers(net, event_type, &info.info);
  330. }
  331. int call_fib6_multipath_entry_notifiers(struct net *net,
  332. enum fib_event_type event_type,
  333. struct fib6_info *rt,
  334. unsigned int nsiblings,
  335. struct netlink_ext_ack *extack)
  336. {
  337. struct fib6_entry_notifier_info info = {
  338. .info.extack = extack,
  339. .rt = rt,
  340. .nsiblings = nsiblings,
  341. };
  342. rt->fib6_table->fib_seq++;
  343. return call_fib6_notifiers(net, event_type, &info.info);
  344. }
  345. int call_fib6_entry_notifiers_replace(struct net *net, struct fib6_info *rt)
  346. {
  347. struct fib6_entry_notifier_info info = {
  348. .rt = rt,
  349. .nsiblings = rt->fib6_nsiblings,
  350. };
  351. rt->fib6_table->fib_seq++;
  352. return call_fib6_notifiers(net, FIB_EVENT_ENTRY_REPLACE, &info.info);
  353. }
  354. struct fib6_dump_arg {
  355. struct net *net;
  356. struct notifier_block *nb;
  357. struct netlink_ext_ack *extack;
  358. };
  359. static int fib6_rt_dump(struct fib6_info *rt, struct fib6_dump_arg *arg)
  360. {
  361. enum fib_event_type fib_event = FIB_EVENT_ENTRY_REPLACE;
  362. int err;
  363. if (!rt || rt == arg->net->ipv6.fib6_null_entry)
  364. return 0;
  365. if (rt->fib6_nsiblings)
  366. err = call_fib6_multipath_entry_notifier(arg->nb, fib_event,
  367. rt,
  368. rt->fib6_nsiblings,
  369. arg->extack);
  370. else
  371. err = call_fib6_entry_notifier(arg->nb, fib_event, rt,
  372. arg->extack);
  373. return err;
  374. }
  375. static int fib6_node_dump(struct fib6_walker *w)
  376. {
  377. int err;
  378. err = fib6_rt_dump(w->leaf, w->args);
  379. w->leaf = NULL;
  380. return err;
  381. }
  382. static int fib6_table_dump(struct net *net, struct fib6_table *tb,
  383. struct fib6_walker *w)
  384. {
  385. int err;
  386. w->root = &tb->tb6_root;
  387. spin_lock_bh(&tb->tb6_lock);
  388. err = fib6_walk(net, w);
  389. spin_unlock_bh(&tb->tb6_lock);
  390. return err;
  391. }
  392. /* Called with rcu_read_lock() */
  393. int fib6_tables_dump(struct net *net, struct notifier_block *nb,
  394. struct netlink_ext_ack *extack)
  395. {
  396. struct fib6_dump_arg arg;
  397. struct fib6_walker *w;
  398. unsigned int h;
  399. int err = 0;
  400. w = kzalloc(sizeof(*w), GFP_ATOMIC);
  401. if (!w)
  402. return -ENOMEM;
  403. w->func = fib6_node_dump;
  404. arg.net = net;
  405. arg.nb = nb;
  406. arg.extack = extack;
  407. w->args = &arg;
  408. for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
  409. struct hlist_head *head = &net->ipv6.fib_table_hash[h];
  410. struct fib6_table *tb;
  411. hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
  412. err = fib6_table_dump(net, tb, w);
  413. if (err < 0)
  414. goto out;
  415. }
  416. }
  417. out:
  418. kfree(w);
  419. return err;
  420. }
  421. static int fib6_dump_node(struct fib6_walker *w)
  422. {
  423. int res;
  424. struct fib6_info *rt;
  425. for_each_fib6_walker_rt(w) {
  426. res = rt6_dump_route(rt, w->args, w->skip_in_node);
  427. if (res >= 0) {
  428. /* Frame is full, suspend walking */
  429. w->leaf = rt;
  430. /* We'll restart from this node, so if some routes were
  431. * already dumped, skip them next time.
  432. */
  433. w->skip_in_node += res;
  434. return 1;
  435. }
  436. w->skip_in_node = 0;
  437. /* Multipath routes are dumped in one route with the
  438. * RTA_MULTIPATH attribute. Jump 'rt' to point to the
  439. * last sibling of this route (no need to dump the
  440. * sibling routes again)
  441. */
  442. if (rt->fib6_nsiblings)
  443. rt = list_last_entry(&rt->fib6_siblings,
  444. struct fib6_info,
  445. fib6_siblings);
  446. }
  447. w->leaf = NULL;
  448. return 0;
  449. }
  450. static void fib6_dump_end(struct netlink_callback *cb)
  451. {
  452. struct net *net = sock_net(cb->skb->sk);
  453. struct fib6_walker *w = (void *)cb->args[2];
  454. if (w) {
  455. if (cb->args[4]) {
  456. cb->args[4] = 0;
  457. fib6_walker_unlink(net, w);
  458. }
  459. cb->args[2] = 0;
  460. kfree(w);
  461. }
  462. cb->done = (void *)cb->args[3];
  463. cb->args[1] = 3;
  464. }
  465. static int fib6_dump_done(struct netlink_callback *cb)
  466. {
  467. fib6_dump_end(cb);
  468. return cb->done ? cb->done(cb) : 0;
  469. }
  470. static int fib6_dump_table(struct fib6_table *table, struct sk_buff *skb,
  471. struct netlink_callback *cb)
  472. {
  473. struct net *net = sock_net(skb->sk);
  474. struct fib6_walker *w;
  475. int res;
  476. w = (void *)cb->args[2];
  477. w->root = &table->tb6_root;
  478. if (cb->args[4] == 0) {
  479. w->count = 0;
  480. w->skip = 0;
  481. w->skip_in_node = 0;
  482. spin_lock_bh(&table->tb6_lock);
  483. res = fib6_walk(net, w);
  484. spin_unlock_bh(&table->tb6_lock);
  485. if (res > 0) {
  486. cb->args[4] = 1;
  487. cb->args[5] = READ_ONCE(w->root->fn_sernum);
  488. }
  489. } else {
  490. int sernum = READ_ONCE(w->root->fn_sernum);
  491. if (cb->args[5] != sernum) {
  492. /* Begin at the root if the tree changed */
  493. cb->args[5] = sernum;
  494. w->state = FWS_INIT;
  495. w->node = w->root;
  496. w->skip = w->count;
  497. w->skip_in_node = 0;
  498. } else
  499. w->skip = 0;
  500. spin_lock_bh(&table->tb6_lock);
  501. res = fib6_walk_continue(w);
  502. spin_unlock_bh(&table->tb6_lock);
  503. if (res <= 0) {
  504. fib6_walker_unlink(net, w);
  505. cb->args[4] = 0;
  506. }
  507. }
  508. return res;
  509. }
  510. static int inet6_dump_fib(struct sk_buff *skb, struct netlink_callback *cb)
  511. {
  512. struct rt6_rtnl_dump_arg arg = { .filter.dump_exceptions = true,
  513. .filter.dump_routes = true };
  514. const struct nlmsghdr *nlh = cb->nlh;
  515. struct net *net = sock_net(skb->sk);
  516. unsigned int h, s_h;
  517. unsigned int e = 0, s_e;
  518. struct fib6_walker *w;
  519. struct fib6_table *tb;
  520. struct hlist_head *head;
  521. int res = 0;
  522. if (cb->strict_check) {
  523. int err;
  524. err = ip_valid_fib_dump_req(net, nlh, &arg.filter, cb);
  525. if (err < 0)
  526. return err;
  527. } else if (nlmsg_len(nlh) >= sizeof(struct rtmsg)) {
  528. struct rtmsg *rtm = nlmsg_data(nlh);
  529. if (rtm->rtm_flags & RTM_F_PREFIX)
  530. arg.filter.flags = RTM_F_PREFIX;
  531. }
  532. w = (void *)cb->args[2];
  533. if (!w) {
  534. /* New dump:
  535. *
  536. * 1. hook callback destructor.
  537. */
  538. cb->args[3] = (long)cb->done;
  539. cb->done = fib6_dump_done;
  540. /*
  541. * 2. allocate and initialize walker.
  542. */
  543. w = kzalloc(sizeof(*w), GFP_ATOMIC);
  544. if (!w)
  545. return -ENOMEM;
  546. w->func = fib6_dump_node;
  547. cb->args[2] = (long)w;
  548. }
  549. arg.skb = skb;
  550. arg.cb = cb;
  551. arg.net = net;
  552. w->args = &arg;
  553. if (arg.filter.table_id) {
  554. tb = fib6_get_table(net, arg.filter.table_id);
  555. if (!tb) {
  556. if (rtnl_msg_family(cb->nlh) != PF_INET6)
  557. goto out;
  558. NL_SET_ERR_MSG_MOD(cb->extack, "FIB table does not exist");
  559. return -ENOENT;
  560. }
  561. if (!cb->args[0]) {
  562. res = fib6_dump_table(tb, skb, cb);
  563. if (!res)
  564. cb->args[0] = 1;
  565. }
  566. goto out;
  567. }
  568. s_h = cb->args[0];
  569. s_e = cb->args[1];
  570. rcu_read_lock();
  571. for (h = s_h; h < FIB6_TABLE_HASHSZ; h++, s_e = 0) {
  572. e = 0;
  573. head = &net->ipv6.fib_table_hash[h];
  574. hlist_for_each_entry_rcu(tb, head, tb6_hlist) {
  575. if (e < s_e)
  576. goto next;
  577. res = fib6_dump_table(tb, skb, cb);
  578. if (res != 0)
  579. goto out_unlock;
  580. next:
  581. e++;
  582. }
  583. }
  584. out_unlock:
  585. rcu_read_unlock();
  586. cb->args[1] = e;
  587. cb->args[0] = h;
  588. out:
  589. res = res < 0 ? res : skb->len;
  590. if (res <= 0)
  591. fib6_dump_end(cb);
  592. return res;
  593. }
  594. void fib6_metric_set(struct fib6_info *f6i, int metric, u32 val)
  595. {
  596. if (!f6i)
  597. return;
  598. if (f6i->fib6_metrics == &dst_default_metrics) {
  599. struct dst_metrics *p = kzalloc(sizeof(*p), GFP_ATOMIC);
  600. if (!p)
  601. return;
  602. refcount_set(&p->refcnt, 1);
  603. f6i->fib6_metrics = p;
  604. }
  605. f6i->fib6_metrics->metrics[metric - 1] = val;
  606. }
  607. /*
  608. * Routing Table
  609. *
  610. * return the appropriate node for a routing tree "add" operation
  611. * by either creating and inserting or by returning an existing
  612. * node.
  613. */
  614. static struct fib6_node *fib6_add_1(struct net *net,
  615. struct fib6_table *table,
  616. struct fib6_node *root,
  617. struct in6_addr *addr, int plen,
  618. int offset, int allow_create,
  619. int replace_required,
  620. struct netlink_ext_ack *extack)
  621. {
  622. struct fib6_node *fn, *in, *ln;
  623. struct fib6_node *pn = NULL;
  624. struct rt6key *key;
  625. int bit;
  626. __be32 dir = 0;
  627. RT6_TRACE("fib6_add_1\n");
  628. /* insert node in tree */
  629. fn = root;
  630. do {
  631. struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,
  632. lockdep_is_held(&table->tb6_lock));
  633. key = (struct rt6key *)((u8 *)leaf + offset);
  634. /*
  635. * Prefix match
  636. */
  637. if (plen < fn->fn_bit ||
  638. !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit)) {
  639. if (!allow_create) {
  640. if (replace_required) {
  641. NL_SET_ERR_MSG(extack,
  642. "Can not replace route - no match found");
  643. pr_warn("Can't replace route, no match found\n");
  644. return ERR_PTR(-ENOENT);
  645. }
  646. pr_warn("NLM_F_CREATE should be set when creating new route\n");
  647. }
  648. goto insert_above;
  649. }
  650. /*
  651. * Exact match ?
  652. */
  653. if (plen == fn->fn_bit) {
  654. /* clean up an intermediate node */
  655. if (!(fn->fn_flags & RTN_RTINFO)) {
  656. RCU_INIT_POINTER(fn->leaf, NULL);
  657. fib6_info_release(leaf);
  658. /* remove null_entry in the root node */
  659. } else if (fn->fn_flags & RTN_TL_ROOT &&
  660. rcu_access_pointer(fn->leaf) ==
  661. net->ipv6.fib6_null_entry) {
  662. RCU_INIT_POINTER(fn->leaf, NULL);
  663. }
  664. return fn;
  665. }
  666. /*
  667. * We have more bits to go
  668. */
  669. /* Try to walk down on tree. */
  670. dir = addr_bit_set(addr, fn->fn_bit);
  671. pn = fn;
  672. fn = dir ?
  673. rcu_dereference_protected(fn->right,
  674. lockdep_is_held(&table->tb6_lock)) :
  675. rcu_dereference_protected(fn->left,
  676. lockdep_is_held(&table->tb6_lock));
  677. } while (fn);
  678. if (!allow_create) {
  679. /* We should not create new node because
  680. * NLM_F_REPLACE was specified without NLM_F_CREATE
  681. * I assume it is safe to require NLM_F_CREATE when
  682. * REPLACE flag is used! Later we may want to remove the
  683. * check for replace_required, because according
  684. * to netlink specification, NLM_F_CREATE
  685. * MUST be specified if new route is created.
  686. * That would keep IPv6 consistent with IPv4
  687. */
  688. if (replace_required) {
  689. NL_SET_ERR_MSG(extack,
  690. "Can not replace route - no match found");
  691. pr_warn("Can't replace route, no match found\n");
  692. return ERR_PTR(-ENOENT);
  693. }
  694. pr_warn("NLM_F_CREATE should be set when creating new route\n");
  695. }
  696. /*
  697. * We walked to the bottom of tree.
  698. * Create new leaf node without children.
  699. */
  700. ln = node_alloc(net);
  701. if (!ln)
  702. return ERR_PTR(-ENOMEM);
  703. ln->fn_bit = plen;
  704. RCU_INIT_POINTER(ln->parent, pn);
  705. if (dir)
  706. rcu_assign_pointer(pn->right, ln);
  707. else
  708. rcu_assign_pointer(pn->left, ln);
  709. return ln;
  710. insert_above:
  711. /*
  712. * split since we don't have a common prefix anymore or
  713. * we have a less significant route.
  714. * we've to insert an intermediate node on the list
  715. * this new node will point to the one we need to create
  716. * and the current
  717. */
  718. pn = rcu_dereference_protected(fn->parent,
  719. lockdep_is_held(&table->tb6_lock));
  720. /* find 1st bit in difference between the 2 addrs.
  721. See comment in __ipv6_addr_diff: bit may be an invalid value,
  722. but if it is >= plen, the value is ignored in any case.
  723. */
  724. bit = __ipv6_addr_diff(addr, &key->addr, sizeof(*addr));
  725. /*
  726. * (intermediate)[in]
  727. * / \
  728. * (new leaf node)[ln] (old node)[fn]
  729. */
  730. if (plen > bit) {
  731. in = node_alloc(net);
  732. ln = node_alloc(net);
  733. if (!in || !ln) {
  734. if (in)
  735. node_free_immediate(net, in);
  736. if (ln)
  737. node_free_immediate(net, ln);
  738. return ERR_PTR(-ENOMEM);
  739. }
  740. /*
  741. * new intermediate node.
  742. * RTN_RTINFO will
  743. * be off since that an address that chooses one of
  744. * the branches would not match less specific routes
  745. * in the other branch
  746. */
  747. in->fn_bit = bit;
  748. RCU_INIT_POINTER(in->parent, pn);
  749. in->leaf = fn->leaf;
  750. fib6_info_hold(rcu_dereference_protected(in->leaf,
  751. lockdep_is_held(&table->tb6_lock)));
  752. /* update parent pointer */
  753. if (dir)
  754. rcu_assign_pointer(pn->right, in);
  755. else
  756. rcu_assign_pointer(pn->left, in);
  757. ln->fn_bit = plen;
  758. RCU_INIT_POINTER(ln->parent, in);
  759. rcu_assign_pointer(fn->parent, in);
  760. if (addr_bit_set(addr, bit)) {
  761. rcu_assign_pointer(in->right, ln);
  762. rcu_assign_pointer(in->left, fn);
  763. } else {
  764. rcu_assign_pointer(in->left, ln);
  765. rcu_assign_pointer(in->right, fn);
  766. }
  767. } else { /* plen <= bit */
  768. /*
  769. * (new leaf node)[ln]
  770. * / \
  771. * (old node)[fn] NULL
  772. */
  773. ln = node_alloc(net);
  774. if (!ln)
  775. return ERR_PTR(-ENOMEM);
  776. ln->fn_bit = plen;
  777. RCU_INIT_POINTER(ln->parent, pn);
  778. if (addr_bit_set(&key->addr, plen))
  779. RCU_INIT_POINTER(ln->right, fn);
  780. else
  781. RCU_INIT_POINTER(ln->left, fn);
  782. rcu_assign_pointer(fn->parent, ln);
  783. if (dir)
  784. rcu_assign_pointer(pn->right, ln);
  785. else
  786. rcu_assign_pointer(pn->left, ln);
  787. }
  788. return ln;
  789. }
  790. static void __fib6_drop_pcpu_from(struct fib6_nh *fib6_nh,
  791. const struct fib6_info *match,
  792. const struct fib6_table *table)
  793. {
  794. int cpu;
  795. if (!fib6_nh->rt6i_pcpu)
  796. return;
  797. /* release the reference to this fib entry from
  798. * all of its cached pcpu routes
  799. */
  800. for_each_possible_cpu(cpu) {
  801. struct rt6_info **ppcpu_rt;
  802. struct rt6_info *pcpu_rt;
  803. ppcpu_rt = per_cpu_ptr(fib6_nh->rt6i_pcpu, cpu);
  804. pcpu_rt = *ppcpu_rt;
  805. /* only dropping the 'from' reference if the cached route
  806. * is using 'match'. The cached pcpu_rt->from only changes
  807. * from a fib6_info to NULL (ip6_dst_destroy); it can never
  808. * change from one fib6_info reference to another
  809. */
  810. if (pcpu_rt && rcu_access_pointer(pcpu_rt->from) == match) {
  811. struct fib6_info *from;
  812. from = xchg((__force struct fib6_info **)&pcpu_rt->from, NULL);
  813. fib6_info_release(from);
  814. }
  815. }
  816. }
  817. struct fib6_nh_pcpu_arg {
  818. struct fib6_info *from;
  819. const struct fib6_table *table;
  820. };
  821. static int fib6_nh_drop_pcpu_from(struct fib6_nh *nh, void *_arg)
  822. {
  823. struct fib6_nh_pcpu_arg *arg = _arg;
  824. __fib6_drop_pcpu_from(nh, arg->from, arg->table);
  825. return 0;
  826. }
  827. static void fib6_drop_pcpu_from(struct fib6_info *f6i,
  828. const struct fib6_table *table)
  829. {
  830. /* Make sure rt6_make_pcpu_route() wont add other percpu routes
  831. * while we are cleaning them here.
  832. */
  833. f6i->fib6_destroying = 1;
  834. mb(); /* paired with the cmpxchg() in rt6_make_pcpu_route() */
  835. if (f6i->nh) {
  836. struct fib6_nh_pcpu_arg arg = {
  837. .from = f6i,
  838. .table = table
  839. };
  840. nexthop_for_each_fib6_nh(f6i->nh, fib6_nh_drop_pcpu_from,
  841. &arg);
  842. } else {
  843. struct fib6_nh *fib6_nh;
  844. fib6_nh = f6i->fib6_nh;
  845. __fib6_drop_pcpu_from(fib6_nh, f6i, table);
  846. }
  847. }
  848. static void fib6_purge_rt(struct fib6_info *rt, struct fib6_node *fn,
  849. struct net *net)
  850. {
  851. struct fib6_table *table = rt->fib6_table;
  852. /* Flush all cached dst in exception table */
  853. rt6_flush_exceptions(rt);
  854. fib6_drop_pcpu_from(rt, table);
  855. if (rt->nh && !list_empty(&rt->nh_list))
  856. list_del_init(&rt->nh_list);
  857. if (refcount_read(&rt->fib6_ref) != 1) {
  858. /* This route is used as dummy address holder in some split
  859. * nodes. It is not leaked, but it still holds other resources,
  860. * which must be released in time. So, scan ascendant nodes
  861. * and replace dummy references to this route with references
  862. * to still alive ones.
  863. */
  864. while (fn) {
  865. struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,
  866. lockdep_is_held(&table->tb6_lock));
  867. struct fib6_info *new_leaf;
  868. if (!(fn->fn_flags & RTN_RTINFO) && leaf == rt) {
  869. new_leaf = fib6_find_prefix(net, table, fn);
  870. fib6_info_hold(new_leaf);
  871. rcu_assign_pointer(fn->leaf, new_leaf);
  872. fib6_info_release(rt);
  873. }
  874. fn = rcu_dereference_protected(fn->parent,
  875. lockdep_is_held(&table->tb6_lock));
  876. }
  877. }
  878. }
  879. /*
  880. * Insert routing information in a node.
  881. */
  882. static int fib6_add_rt2node(struct fib6_node *fn, struct fib6_info *rt,
  883. struct nl_info *info,
  884. struct netlink_ext_ack *extack)
  885. {
  886. struct fib6_info *leaf = rcu_dereference_protected(fn->leaf,
  887. lockdep_is_held(&rt->fib6_table->tb6_lock));
  888. struct fib6_info *iter = NULL;
  889. struct fib6_info __rcu **ins;
  890. struct fib6_info __rcu **fallback_ins = NULL;
  891. int replace = (info->nlh &&
  892. (info->nlh->nlmsg_flags & NLM_F_REPLACE));
  893. int add = (!info->nlh ||
  894. (info->nlh->nlmsg_flags & NLM_F_CREATE));
  895. int found = 0;
  896. bool rt_can_ecmp = rt6_qualify_for_ecmp(rt);
  897. bool notify_sibling_rt = false;
  898. u16 nlflags = NLM_F_EXCL;
  899. int err;
  900. if (info->nlh && (info->nlh->nlmsg_flags & NLM_F_APPEND))
  901. nlflags |= NLM_F_APPEND;
  902. ins = &fn->leaf;
  903. for (iter = leaf; iter;
  904. iter = rcu_dereference_protected(iter->fib6_next,
  905. lockdep_is_held(&rt->fib6_table->tb6_lock))) {
  906. /*
  907. * Search for duplicates
  908. */
  909. if (iter->fib6_metric == rt->fib6_metric) {
  910. /*
  911. * Same priority level
  912. */
  913. if (info->nlh &&
  914. (info->nlh->nlmsg_flags & NLM_F_EXCL))
  915. return -EEXIST;
  916. nlflags &= ~NLM_F_EXCL;
  917. if (replace) {
  918. if (rt_can_ecmp == rt6_qualify_for_ecmp(iter)) {
  919. found++;
  920. break;
  921. }
  922. fallback_ins = fallback_ins ?: ins;
  923. goto next_iter;
  924. }
  925. if (rt6_duplicate_nexthop(iter, rt)) {
  926. if (rt->fib6_nsiblings)
  927. rt->fib6_nsiblings = 0;
  928. if (!(iter->fib6_flags & RTF_EXPIRES))
  929. return -EEXIST;
  930. if (!(rt->fib6_flags & RTF_EXPIRES))
  931. fib6_clean_expires(iter);
  932. else
  933. fib6_set_expires(iter, rt->expires);
  934. if (rt->fib6_pmtu)
  935. fib6_metric_set(iter, RTAX_MTU,
  936. rt->fib6_pmtu);
  937. return -EEXIST;
  938. }
  939. /* If we have the same destination and the same metric,
  940. * but not the same gateway, then the route we try to
  941. * add is sibling to this route, increment our counter
  942. * of siblings, and later we will add our route to the
  943. * list.
  944. * Only static routes (which don't have flag
  945. * RTF_EXPIRES) are used for ECMPv6.
  946. *
  947. * To avoid long list, we only had siblings if the
  948. * route have a gateway.
  949. */
  950. if (rt_can_ecmp &&
  951. rt6_qualify_for_ecmp(iter))
  952. rt->fib6_nsiblings++;
  953. }
  954. if (iter->fib6_metric > rt->fib6_metric)
  955. break;
  956. next_iter:
  957. ins = &iter->fib6_next;
  958. }
  959. if (fallback_ins && !found) {
  960. /* No matching route with same ecmp-able-ness found, replace
  961. * first matching route
  962. */
  963. ins = fallback_ins;
  964. iter = rcu_dereference_protected(*ins,
  965. lockdep_is_held(&rt->fib6_table->tb6_lock));
  966. found++;
  967. }
  968. /* Reset round-robin state, if necessary */
  969. if (ins == &fn->leaf)
  970. fn->rr_ptr = NULL;
  971. /* Link this route to others same route. */
  972. if (rt->fib6_nsiblings) {
  973. unsigned int fib6_nsiblings;
  974. struct fib6_info *sibling, *temp_sibling;
  975. /* Find the first route that have the same metric */
  976. sibling = leaf;
  977. notify_sibling_rt = true;
  978. while (sibling) {
  979. if (sibling->fib6_metric == rt->fib6_metric &&
  980. rt6_qualify_for_ecmp(sibling)) {
  981. list_add_tail(&rt->fib6_siblings,
  982. &sibling->fib6_siblings);
  983. break;
  984. }
  985. sibling = rcu_dereference_protected(sibling->fib6_next,
  986. lockdep_is_held(&rt->fib6_table->tb6_lock));
  987. notify_sibling_rt = false;
  988. }
  989. /* For each sibling in the list, increment the counter of
  990. * siblings. BUG() if counters does not match, list of siblings
  991. * is broken!
  992. */
  993. fib6_nsiblings = 0;
  994. list_for_each_entry_safe(sibling, temp_sibling,
  995. &rt->fib6_siblings, fib6_siblings) {
  996. sibling->fib6_nsiblings++;
  997. BUG_ON(sibling->fib6_nsiblings != rt->fib6_nsiblings);
  998. fib6_nsiblings++;
  999. }
  1000. BUG_ON(fib6_nsiblings != rt->fib6_nsiblings);
  1001. rt6_multipath_rebalance(temp_sibling);
  1002. }
  1003. /*
  1004. * insert node
  1005. */
  1006. if (!replace) {
  1007. if (!add)
  1008. pr_warn("NLM_F_CREATE should be set when creating new route\n");
  1009. add:
  1010. nlflags |= NLM_F_CREATE;
  1011. /* The route should only be notified if it is the first
  1012. * route in the node or if it is added as a sibling
  1013. * route to the first route in the node.
  1014. */
  1015. if (!info->skip_notify_kernel &&
  1016. (notify_sibling_rt || ins == &fn->leaf)) {
  1017. enum fib_event_type fib_event;
  1018. if (notify_sibling_rt)
  1019. fib_event = FIB_EVENT_ENTRY_APPEND;
  1020. else
  1021. fib_event = FIB_EVENT_ENTRY_REPLACE;
  1022. err = call_fib6_entry_notifiers(info->nl_net,
  1023. fib_event, rt,
  1024. extack);
  1025. if (err) {
  1026. struct fib6_info *sibling, *next_sibling;
  1027. /* If the route has siblings, then it first
  1028. * needs to be unlinked from them.
  1029. */
  1030. if (!rt->fib6_nsiblings)
  1031. return err;
  1032. list_for_each_entry_safe(sibling, next_sibling,
  1033. &rt->fib6_siblings,
  1034. fib6_siblings)
  1035. sibling->fib6_nsiblings--;
  1036. rt->fib6_nsiblings = 0;
  1037. list_del_init(&rt->fib6_siblings);
  1038. rt6_multipath_rebalance(next_sibling);
  1039. return err;
  1040. }
  1041. }
  1042. rcu_assign_pointer(rt->fib6_next, iter);
  1043. fib6_info_hold(rt);
  1044. rcu_assign_pointer(rt->fib6_node, fn);
  1045. rcu_assign_pointer(*ins, rt);
  1046. if (!info->skip_notify)
  1047. inet6_rt_notify(RTM_NEWROUTE, rt, info, nlflags);
  1048. info->nl_net->ipv6.rt6_stats->fib_rt_entries++;
  1049. if (!(fn->fn_flags & RTN_RTINFO)) {
  1050. info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
  1051. fn->fn_flags |= RTN_RTINFO;
  1052. }
  1053. } else {
  1054. int nsiblings;
  1055. if (!found) {
  1056. if (add)
  1057. goto add;
  1058. pr_warn("NLM_F_REPLACE set, but no existing node found!\n");
  1059. return -ENOENT;
  1060. }
  1061. if (!info->skip_notify_kernel && ins == &fn->leaf) {
  1062. err = call_fib6_entry_notifiers(info->nl_net,
  1063. FIB_EVENT_ENTRY_REPLACE,
  1064. rt, extack);
  1065. if (err)
  1066. return err;
  1067. }
  1068. fib6_info_hold(rt);
  1069. rcu_assign_pointer(rt->fib6_node, fn);
  1070. rt->fib6_next = iter->fib6_next;
  1071. rcu_assign_pointer(*ins, rt);
  1072. if (!info->skip_notify)
  1073. inet6_rt_notify(RTM_NEWROUTE, rt, info, NLM_F_REPLACE);
  1074. if (!(fn->fn_flags & RTN_RTINFO)) {
  1075. info->nl_net->ipv6.rt6_stats->fib_route_nodes++;
  1076. fn->fn_flags |= RTN_RTINFO;
  1077. }
  1078. nsiblings = iter->fib6_nsiblings;
  1079. iter->fib6_node = NULL;
  1080. fib6_purge_rt(iter, fn, info->nl_net);
  1081. if (rcu_access_pointer(fn->rr_ptr) == iter)
  1082. fn->rr_ptr = NULL;
  1083. fib6_info_release(iter);
  1084. if (nsiblings) {
  1085. /* Replacing an ECMP route, remove all siblings */
  1086. ins = &rt->fib6_next;
  1087. iter = rcu_dereference_protected(*ins,
  1088. lockdep_is_held(&rt->fib6_table->tb6_lock));
  1089. while (iter) {
  1090. if (iter->fib6_metric > rt->fib6_metric)
  1091. break;
  1092. if (rt6_qualify_for_ecmp(iter)) {
  1093. *ins = iter->fib6_next;
  1094. iter->fib6_node = NULL;
  1095. fib6_purge_rt(iter, fn, info->nl_net);
  1096. if (rcu_access_pointer(fn->rr_ptr) == iter)
  1097. fn->rr_ptr = NULL;
  1098. fib6_info_release(iter);
  1099. nsiblings--;
  1100. info->nl_net->ipv6.rt6_stats->fib_rt_entries--;
  1101. } else {
  1102. ins = &iter->fib6_next;
  1103. }
  1104. iter = rcu_dereference_protected(*ins,
  1105. lockdep_is_held(&rt->fib6_table->tb6_lock));
  1106. }
  1107. WARN_ON(nsiblings != 0);
  1108. }
  1109. }
  1110. return 0;
  1111. }
  1112. static void fib6_start_gc(struct net *net, struct fib6_info *rt)
  1113. {
  1114. if (!timer_pending(&net->ipv6.ip6_fib_timer) &&
  1115. (rt->fib6_flags & RTF_EXPIRES))
  1116. mod_timer(&net->ipv6.ip6_fib_timer,
  1117. jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
  1118. }
  1119. void fib6_force_start_gc(struct net *net)
  1120. {
  1121. if (!timer_pending(&net->ipv6.ip6_fib_timer))
  1122. mod_timer(&net->ipv6.ip6_fib_timer,
  1123. jiffies + net->ipv6.sysctl.ip6_rt_gc_interval);
  1124. }
  1125. static void __fib6_update_sernum_upto_root(struct fib6_info *rt,
  1126. int sernum)
  1127. {
  1128. struct fib6_node *fn = rcu_dereference_protected(rt->fib6_node,
  1129. lockdep_is_held(&rt->fib6_table->tb6_lock));
  1130. /* paired with smp_rmb() in rt6_get_cookie_safe() */
  1131. smp_wmb();
  1132. while (fn) {
  1133. WRITE_ONCE(fn->fn_sernum, sernum);
  1134. fn = rcu_dereference_protected(fn->parent,
  1135. lockdep_is_held(&rt->fib6_table->tb6_lock));
  1136. }
  1137. }
  1138. void fib6_update_sernum_upto_root(struct net *net, struct fib6_info *rt)
  1139. {
  1140. __fib6_update_sernum_upto_root(rt, fib6_new_sernum(net));
  1141. }
  1142. /* allow ipv4 to update sernum via ipv6_stub */
  1143. void fib6_update_sernum_stub(struct net *net, struct fib6_info *f6i)
  1144. {
  1145. spin_lock_bh(&f6i->fib6_table->tb6_lock);
  1146. fib6_update_sernum_upto_root(net, f6i);
  1147. spin_unlock_bh(&f6i->fib6_table->tb6_lock);
  1148. }
  1149. /*
  1150. * Add routing information to the routing tree.
  1151. * <destination addr>/<source addr>
  1152. * with source addr info in sub-trees
  1153. * Need to own table->tb6_lock
  1154. */
  1155. int fib6_add(struct fib6_node *root, struct fib6_info *rt,
  1156. struct nl_info *info, struct netlink_ext_ack *extack)
  1157. {
  1158. struct fib6_table *table = rt->fib6_table;
  1159. struct fib6_node *fn, *pn = NULL;
  1160. int err = -ENOMEM;
  1161. int allow_create = 1;
  1162. int replace_required = 0;
  1163. if (info->nlh) {
  1164. if (!(info->nlh->nlmsg_flags & NLM_F_CREATE))
  1165. allow_create = 0;
  1166. if (info->nlh->nlmsg_flags & NLM_F_REPLACE)
  1167. replace_required = 1;
  1168. }
  1169. if (!allow_create && !replace_required)
  1170. pr_warn("RTM_NEWROUTE with no NLM_F_CREATE or NLM_F_REPLACE\n");
  1171. fn = fib6_add_1(info->nl_net, table, root,
  1172. &rt->fib6_dst.addr, rt->fib6_dst.plen,
  1173. offsetof(struct fib6_info, fib6_dst), allow_create,
  1174. replace_required, extack);
  1175. if (IS_ERR(fn)) {
  1176. err = PTR_ERR(fn);
  1177. fn = NULL;
  1178. goto out;
  1179. }
  1180. pn = fn;
  1181. #ifdef CONFIG_IPV6_SUBTREES
  1182. if (rt->fib6_src.plen) {
  1183. struct fib6_node *sn;
  1184. if (!rcu_access_pointer(fn->subtree)) {
  1185. struct fib6_node *sfn;
  1186. /*
  1187. * Create subtree.
  1188. *
  1189. * fn[main tree]
  1190. * |
  1191. * sfn[subtree root]
  1192. * \
  1193. * sn[new leaf node]
  1194. */
  1195. /* Create subtree root node */
  1196. sfn = node_alloc(info->nl_net);
  1197. if (!sfn)
  1198. goto failure;
  1199. fib6_info_hold(info->nl_net->ipv6.fib6_null_entry);
  1200. rcu_assign_pointer(sfn->leaf,
  1201. info->nl_net->ipv6.fib6_null_entry);
  1202. sfn->fn_flags = RTN_ROOT;
  1203. /* Now add the first leaf node to new subtree */
  1204. sn = fib6_add_1(info->nl_net, table, sfn,
  1205. &rt->fib6_src.addr, rt->fib6_src.plen,
  1206. offsetof(struct fib6_info, fib6_src),
  1207. allow_create, replace_required, extack);
  1208. if (IS_ERR(sn)) {
  1209. /* If it is failed, discard just allocated
  1210. root, and then (in failure) stale node
  1211. in main tree.
  1212. */
  1213. node_free_immediate(info->nl_net, sfn);
  1214. err = PTR_ERR(sn);
  1215. goto failure;
  1216. }
  1217. /* Now link new subtree to main tree */
  1218. rcu_assign_pointer(sfn->parent, fn);
  1219. rcu_assign_pointer(fn->subtree, sfn);
  1220. } else {
  1221. sn = fib6_add_1(info->nl_net, table, FIB6_SUBTREE(fn),
  1222. &rt->fib6_src.addr, rt->fib6_src.plen,
  1223. offsetof(struct fib6_info, fib6_src),
  1224. allow_create, replace_required, extack);
  1225. if (IS_ERR(sn)) {
  1226. err = PTR_ERR(sn);
  1227. goto failure;
  1228. }
  1229. }
  1230. if (!rcu_access_pointer(fn->leaf)) {
  1231. if (fn->fn_flags & RTN_TL_ROOT) {
  1232. /* put back null_entry for root node */
  1233. rcu_assign_pointer(fn->leaf,
  1234. info->nl_net->ipv6.fib6_null_entry);
  1235. } else {
  1236. fib6_info_hold(rt);
  1237. rcu_assign_pointer(fn->leaf, rt);
  1238. }
  1239. }
  1240. fn = sn;
  1241. }
  1242. #endif
  1243. err = fib6_add_rt2node(fn, rt, info, extack);
  1244. if (!err) {
  1245. if (rt->nh)
  1246. list_add(&rt->nh_list, &rt->nh->f6i_list);
  1247. __fib6_update_sernum_upto_root(rt, fib6_new_sernum(info->nl_net));
  1248. fib6_start_gc(info->nl_net, rt);
  1249. }
  1250. out:
  1251. if (err) {
  1252. #ifdef CONFIG_IPV6_SUBTREES
  1253. /*
  1254. * If fib6_add_1 has cleared the old leaf pointer in the
  1255. * super-tree leaf node we have to find a new one for it.
  1256. */
  1257. if (pn != fn) {
  1258. struct fib6_info *pn_leaf =
  1259. rcu_dereference_protected(pn->leaf,
  1260. lockdep_is_held(&table->tb6_lock));
  1261. if (pn_leaf == rt) {
  1262. pn_leaf = NULL;
  1263. RCU_INIT_POINTER(pn->leaf, NULL);
  1264. fib6_info_release(rt);
  1265. }
  1266. if (!pn_leaf && !(pn->fn_flags & RTN_RTINFO)) {
  1267. pn_leaf = fib6_find_prefix(info->nl_net, table,
  1268. pn);
  1269. #if RT6_DEBUG >= 2
  1270. if (!pn_leaf) {
  1271. WARN_ON(!pn_leaf);
  1272. pn_leaf =
  1273. info->nl_net->ipv6.fib6_null_entry;
  1274. }
  1275. #endif
  1276. fib6_info_hold(pn_leaf);
  1277. rcu_assign_pointer(pn->leaf, pn_leaf);
  1278. }
  1279. }
  1280. #endif
  1281. goto failure;
  1282. } else if (fib6_requires_src(rt)) {
  1283. fib6_routes_require_src_inc(info->nl_net);
  1284. }
  1285. return err;
  1286. failure:
  1287. /* fn->leaf could be NULL and fib6_repair_tree() needs to be called if:
  1288. * 1. fn is an intermediate node and we failed to add the new
  1289. * route to it in both subtree creation failure and fib6_add_rt2node()
  1290. * failure case.
  1291. * 2. fn is the root node in the table and we fail to add the first
  1292. * default route to it.
  1293. */
  1294. if (fn &&
  1295. (!(fn->fn_flags & (RTN_RTINFO|RTN_ROOT)) ||
  1296. (fn->fn_flags & RTN_TL_ROOT &&
  1297. !rcu_access_pointer(fn->leaf))))
  1298. fib6_repair_tree(info->nl_net, table, fn);
  1299. return err;
  1300. }
  1301. /*
  1302. * Routing tree lookup
  1303. *
  1304. */
  1305. struct lookup_args {
  1306. int offset; /* key offset on fib6_info */
  1307. const struct in6_addr *addr; /* search key */
  1308. };
  1309. static struct fib6_node *fib6_node_lookup_1(struct fib6_node *root,
  1310. struct lookup_args *args)
  1311. {
  1312. struct fib6_node *fn;
  1313. __be32 dir;
  1314. if (unlikely(args->offset == 0))
  1315. return NULL;
  1316. /*
  1317. * Descend on a tree
  1318. */
  1319. fn = root;
  1320. for (;;) {
  1321. struct fib6_node *next;
  1322. dir = addr_bit_set(args->addr, fn->fn_bit);
  1323. next = dir ? rcu_dereference(fn->right) :
  1324. rcu_dereference(fn->left);
  1325. if (next) {
  1326. fn = next;
  1327. continue;
  1328. }
  1329. break;
  1330. }
  1331. while (fn) {
  1332. struct fib6_node *subtree = FIB6_SUBTREE(fn);
  1333. if (subtree || fn->fn_flags & RTN_RTINFO) {
  1334. struct fib6_info *leaf = rcu_dereference(fn->leaf);
  1335. struct rt6key *key;
  1336. if (!leaf)
  1337. goto backtrack;
  1338. key = (struct rt6key *) ((u8 *)leaf + args->offset);
  1339. if (ipv6_prefix_equal(&key->addr, args->addr, key->plen)) {
  1340. #ifdef CONFIG_IPV6_SUBTREES
  1341. if (subtree) {
  1342. struct fib6_node *sfn;
  1343. sfn = fib6_node_lookup_1(subtree,
  1344. args + 1);
  1345. if (!sfn)
  1346. goto backtrack;
  1347. fn = sfn;
  1348. }
  1349. #endif
  1350. if (fn->fn_flags & RTN_RTINFO)
  1351. return fn;
  1352. }
  1353. }
  1354. backtrack:
  1355. if (fn->fn_flags & RTN_ROOT)
  1356. break;
  1357. fn = rcu_dereference(fn->parent);
  1358. }
  1359. return NULL;
  1360. }
  1361. /* called with rcu_read_lock() held
  1362. */
  1363. struct fib6_node *fib6_node_lookup(struct fib6_node *root,
  1364. const struct in6_addr *daddr,
  1365. const struct in6_addr *saddr)
  1366. {
  1367. struct fib6_node *fn;
  1368. struct lookup_args args[] = {
  1369. {
  1370. .offset = offsetof(struct fib6_info, fib6_dst),
  1371. .addr = daddr,
  1372. },
  1373. #ifdef CONFIG_IPV6_SUBTREES
  1374. {
  1375. .offset = offsetof(struct fib6_info, fib6_src),
  1376. .addr = saddr,
  1377. },
  1378. #endif
  1379. {
  1380. .offset = 0, /* sentinel */
  1381. }
  1382. };
  1383. fn = fib6_node_lookup_1(root, daddr ? args : args + 1);
  1384. if (!fn || fn->fn_flags & RTN_TL_ROOT)
  1385. fn = root;
  1386. return fn;
  1387. }
  1388. /*
  1389. * Get node with specified destination prefix (and source prefix,
  1390. * if subtrees are used)
  1391. * exact_match == true means we try to find fn with exact match of
  1392. * the passed in prefix addr
  1393. * exact_match == false means we try to find fn with longest prefix
  1394. * match of the passed in prefix addr. This is useful for finding fn
  1395. * for cached route as it will be stored in the exception table under
  1396. * the node with longest prefix length.
  1397. */
  1398. static struct fib6_node *fib6_locate_1(struct fib6_node *root,
  1399. const struct in6_addr *addr,
  1400. int plen, int offset,
  1401. bool exact_match)
  1402. {
  1403. struct fib6_node *fn, *prev = NULL;
  1404. for (fn = root; fn ; ) {
  1405. struct fib6_info *leaf = rcu_dereference(fn->leaf);
  1406. struct rt6key *key;
  1407. /* This node is being deleted */
  1408. if (!leaf) {
  1409. if (plen <= fn->fn_bit)
  1410. goto out;
  1411. else
  1412. goto next;
  1413. }
  1414. key = (struct rt6key *)((u8 *)leaf + offset);
  1415. /*
  1416. * Prefix match
  1417. */
  1418. if (plen < fn->fn_bit ||
  1419. !ipv6_prefix_equal(&key->addr, addr, fn->fn_bit))
  1420. goto out;
  1421. if (plen == fn->fn_bit)
  1422. return fn;
  1423. if (fn->fn_flags & RTN_RTINFO)
  1424. prev = fn;
  1425. next:
  1426. /*
  1427. * We have more bits to go
  1428. */
  1429. if (addr_bit_set(addr, fn->fn_bit))
  1430. fn = rcu_dereference(fn->right);
  1431. else
  1432. fn = rcu_dereference(fn->left);
  1433. }
  1434. out:
  1435. if (exact_match)
  1436. return NULL;
  1437. else
  1438. return prev;
  1439. }
  1440. struct fib6_node *fib6_locate(struct fib6_node *root,
  1441. const struct in6_addr *daddr, int dst_len,
  1442. const struct in6_addr *saddr, int src_len,
  1443. bool exact_match)
  1444. {
  1445. struct fib6_node *fn;
  1446. fn = fib6_locate_1(root, daddr, dst_len,
  1447. offsetof(struct fib6_info, fib6_dst),
  1448. exact_match);
  1449. #ifdef CONFIG_IPV6_SUBTREES
  1450. if (src_len) {
  1451. WARN_ON(saddr == NULL);
  1452. if (fn) {
  1453. struct fib6_node *subtree = FIB6_SUBTREE(fn);
  1454. if (subtree) {
  1455. fn = fib6_locate_1(subtree, saddr, src_len,
  1456. offsetof(struct fib6_info, fib6_src),
  1457. exact_match);
  1458. }
  1459. }
  1460. }
  1461. #endif
  1462. if (fn && fn->fn_flags & RTN_RTINFO)
  1463. return fn;
  1464. return NULL;
  1465. }
  1466. /*
  1467. * Deletion
  1468. *
  1469. */
  1470. static struct fib6_info *fib6_find_prefix(struct net *net,
  1471. struct fib6_table *table,
  1472. struct fib6_node *fn)
  1473. {
  1474. struct fib6_node *child_left, *child_right;
  1475. if (fn->fn_flags & RTN_ROOT)
  1476. return net->ipv6.fib6_null_entry;
  1477. while (fn) {
  1478. child_left = rcu_dereference_protected(fn->left,
  1479. lockdep_is_held(&table->tb6_lock));
  1480. child_right = rcu_dereference_protected(fn->right,
  1481. lockdep_is_held(&table->tb6_lock));
  1482. if (child_left)
  1483. return rcu_dereference_protected(child_left->leaf,
  1484. lockdep_is_held(&table->tb6_lock));
  1485. if (child_right)
  1486. return rcu_dereference_protected(child_right->leaf,
  1487. lockdep_is_held(&table->tb6_lock));
  1488. fn = FIB6_SUBTREE(fn);
  1489. }
  1490. return NULL;
  1491. }
  1492. /*
  1493. * Called to trim the tree of intermediate nodes when possible. "fn"
  1494. * is the node we want to try and remove.
  1495. * Need to own table->tb6_lock
  1496. */
  1497. static struct fib6_node *fib6_repair_tree(struct net *net,
  1498. struct fib6_table *table,
  1499. struct fib6_node *fn)
  1500. {
  1501. int children;
  1502. int nstate;
  1503. struct fib6_node *child;
  1504. struct fib6_walker *w;
  1505. int iter = 0;
  1506. /* Set fn->leaf to null_entry for root node. */
  1507. if (fn->fn_flags & RTN_TL_ROOT) {
  1508. rcu_assign_pointer(fn->leaf, net->ipv6.fib6_null_entry);
  1509. return fn;
  1510. }
  1511. for (;;) {
  1512. struct fib6_node *fn_r = rcu_dereference_protected(fn->right,
  1513. lockdep_is_held(&table->tb6_lock));
  1514. struct fib6_node *fn_l = rcu_dereference_protected(fn->left,
  1515. lockdep_is_held(&table->tb6_lock));
  1516. struct fib6_node *pn = rcu_dereference_protected(fn->parent,
  1517. lockdep_is_held(&table->tb6_lock));
  1518. struct fib6_node *pn_r = rcu_dereference_protected(pn->right,
  1519. lockdep_is_held(&table->tb6_lock));
  1520. struct fib6_node *pn_l = rcu_dereference_protected(pn->left,
  1521. lockdep_is_held(&table->tb6_lock));
  1522. struct fib6_info *fn_leaf = rcu_dereference_protected(fn->leaf,
  1523. lockdep_is_held(&table->tb6_lock));
  1524. struct fib6_info *pn_leaf = rcu_dereference_protected(pn->leaf,
  1525. lockdep_is_held(&table->tb6_lock));
  1526. struct fib6_info *new_fn_leaf;
  1527. RT6_TRACE("fixing tree: plen=%d iter=%d\n", fn->fn_bit, iter);
  1528. iter++;
  1529. WARN_ON(fn->fn_flags & RTN_RTINFO);
  1530. WARN_ON(fn->fn_flags & RTN_TL_ROOT);
  1531. WARN_ON(fn_leaf);
  1532. children = 0;
  1533. child = NULL;
  1534. if (fn_r) {
  1535. child = fn_r;
  1536. children |= 1;
  1537. }
  1538. if (fn_l) {
  1539. child = fn_l;
  1540. children |= 2;
  1541. }
  1542. if (children == 3 || FIB6_SUBTREE(fn)
  1543. #ifdef CONFIG_IPV6_SUBTREES
  1544. /* Subtree root (i.e. fn) may have one child */
  1545. || (children && fn->fn_flags & RTN_ROOT)
  1546. #endif
  1547. ) {
  1548. new_fn_leaf = fib6_find_prefix(net, table, fn);
  1549. #if RT6_DEBUG >= 2
  1550. if (!new_fn_leaf) {
  1551. WARN_ON(!new_fn_leaf);
  1552. new_fn_leaf = net->ipv6.fib6_null_entry;
  1553. }
  1554. #endif
  1555. fib6_info_hold(new_fn_leaf);
  1556. rcu_assign_pointer(fn->leaf, new_fn_leaf);
  1557. return pn;
  1558. }
  1559. #ifdef CONFIG_IPV6_SUBTREES
  1560. if (FIB6_SUBTREE(pn) == fn) {
  1561. WARN_ON(!(fn->fn_flags & RTN_ROOT));
  1562. RCU_INIT_POINTER(pn->subtree, NULL);
  1563. nstate = FWS_L;
  1564. } else {
  1565. WARN_ON(fn->fn_flags & RTN_ROOT);
  1566. #endif
  1567. if (pn_r == fn)
  1568. rcu_assign_pointer(pn->right, child);
  1569. else if (pn_l == fn)
  1570. rcu_assign_pointer(pn->left, child);
  1571. #if RT6_DEBUG >= 2
  1572. else
  1573. WARN_ON(1);
  1574. #endif
  1575. if (child)
  1576. rcu_assign_pointer(child->parent, pn);
  1577. nstate = FWS_R;
  1578. #ifdef CONFIG_IPV6_SUBTREES
  1579. }
  1580. #endif
  1581. read_lock(&net->ipv6.fib6_walker_lock);
  1582. FOR_WALKERS(net, w) {
  1583. if (!child) {
  1584. if (w->node == fn) {
  1585. RT6_TRACE("W %p adjusted by delnode 1, s=%d/%d\n", w, w->state, nstate);
  1586. w->node = pn;
  1587. w->state = nstate;
  1588. }
  1589. } else {
  1590. if (w->node == fn) {
  1591. w->node = child;
  1592. if (children&2) {
  1593. RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
  1594. w->state = w->state >= FWS_R ? FWS_U : FWS_INIT;
  1595. } else {
  1596. RT6_TRACE("W %p adjusted by delnode 2, s=%d\n", w, w->state);
  1597. w->state = w->state >= FWS_C ? FWS_U : FWS_INIT;
  1598. }
  1599. }
  1600. }
  1601. }
  1602. read_unlock(&net->ipv6.fib6_walker_lock);
  1603. node_free(net, fn);
  1604. if (pn->fn_flags & RTN_RTINFO || FIB6_SUBTREE(pn))
  1605. return pn;
  1606. RCU_INIT_POINTER(pn->leaf, NULL);
  1607. fib6_info_release(pn_leaf);
  1608. fn = pn;
  1609. }
  1610. }
  1611. static void fib6_del_route(struct fib6_table *table, struct fib6_node *fn,
  1612. struct fib6_info __rcu **rtp, struct nl_info *info)
  1613. {
  1614. struct fib6_info *leaf, *replace_rt = NULL;
  1615. struct fib6_walker *w;
  1616. struct fib6_info *rt = rcu_dereference_protected(*rtp,
  1617. lockdep_is_held(&table->tb6_lock));
  1618. struct net *net = info->nl_net;
  1619. bool notify_del = false;
  1620. RT6_TRACE("fib6_del_route\n");
  1621. /* If the deleted route is the first in the node and it is not part of
  1622. * a multipath route, then we need to replace it with the next route
  1623. * in the node, if exists.
  1624. */
  1625. leaf = rcu_dereference_protected(fn->leaf,
  1626. lockdep_is_held(&table->tb6_lock));
  1627. if (leaf == rt && !rt->fib6_nsiblings) {
  1628. if (rcu_access_pointer(rt->fib6_next))
  1629. replace_rt = rcu_dereference_protected(rt->fib6_next,
  1630. lockdep_is_held(&table->tb6_lock));
  1631. else
  1632. notify_del = true;
  1633. }
  1634. /* Unlink it */
  1635. *rtp = rt->fib6_next;
  1636. rt->fib6_node = NULL;
  1637. net->ipv6.rt6_stats->fib_rt_entries--;
  1638. net->ipv6.rt6_stats->fib_discarded_routes++;
  1639. /* Reset round-robin state, if necessary */
  1640. if (rcu_access_pointer(fn->rr_ptr) == rt)
  1641. fn->rr_ptr = NULL;
  1642. /* Remove this entry from other siblings */
  1643. if (rt->fib6_nsiblings) {
  1644. struct fib6_info *sibling, *next_sibling;
  1645. /* The route is deleted from a multipath route. If this
  1646. * multipath route is the first route in the node, then we need
  1647. * to emit a delete notification. Otherwise, we need to skip
  1648. * the notification.
  1649. */
  1650. if (rt->fib6_metric == leaf->fib6_metric &&
  1651. rt6_qualify_for_ecmp(leaf))
  1652. notify_del = true;
  1653. list_for_each_entry_safe(sibling, next_sibling,
  1654. &rt->fib6_siblings, fib6_siblings)
  1655. sibling->fib6_nsiblings--;
  1656. rt->fib6_nsiblings = 0;
  1657. list_del_init(&rt->fib6_siblings);
  1658. rt6_multipath_rebalance(next_sibling);
  1659. }
  1660. /* Adjust walkers */
  1661. read_lock(&net->ipv6.fib6_walker_lock);
  1662. FOR_WALKERS(net, w) {
  1663. if (w->state == FWS_C && w->leaf == rt) {
  1664. RT6_TRACE("walker %p adjusted by delroute\n", w);
  1665. w->leaf = rcu_dereference_protected(rt->fib6_next,
  1666. lockdep_is_held(&table->tb6_lock));
  1667. if (!w->leaf)
  1668. w->state = FWS_U;
  1669. }
  1670. }
  1671. read_unlock(&net->ipv6.fib6_walker_lock);
  1672. /* If it was last route, call fib6_repair_tree() to:
  1673. * 1. For root node, put back null_entry as how the table was created.
  1674. * 2. For other nodes, expunge its radix tree node.
  1675. */
  1676. if (!rcu_access_pointer(fn->leaf)) {
  1677. if (!(fn->fn_flags & RTN_TL_ROOT)) {
  1678. fn->fn_flags &= ~RTN_RTINFO;
  1679. net->ipv6.rt6_stats->fib_route_nodes--;
  1680. }
  1681. fn = fib6_repair_tree(net, table, fn);
  1682. }
  1683. fib6_purge_rt(rt, fn, net);
  1684. if (!info->skip_notify_kernel) {
  1685. if (notify_del)
  1686. call_fib6_entry_notifiers(net, FIB_EVENT_ENTRY_DEL,
  1687. rt, NULL);
  1688. else if (replace_rt)
  1689. call_fib6_entry_notifiers_replace(net, replace_rt);
  1690. }
  1691. if (!info->skip_notify)
  1692. inet6_rt_notify(RTM_DELROUTE, rt, info, 0);
  1693. fib6_info_release(rt);
  1694. }
  1695. /* Need to own table->tb6_lock */
  1696. int fib6_del(struct fib6_info *rt, struct nl_info *info)
  1697. {
  1698. struct net *net = info->nl_net;
  1699. struct fib6_info __rcu **rtp;
  1700. struct fib6_info __rcu **rtp_next;
  1701. struct fib6_table *table;
  1702. struct fib6_node *fn;
  1703. if (rt == net->ipv6.fib6_null_entry)
  1704. return -ENOENT;
  1705. table = rt->fib6_table;
  1706. fn = rcu_dereference_protected(rt->fib6_node,
  1707. lockdep_is_held(&table->tb6_lock));
  1708. if (!fn)
  1709. return -ENOENT;
  1710. WARN_ON(!(fn->fn_flags & RTN_RTINFO));
  1711. /*
  1712. * Walk the leaf entries looking for ourself
  1713. */
  1714. for (rtp = &fn->leaf; *rtp; rtp = rtp_next) {
  1715. struct fib6_info *cur = rcu_dereference_protected(*rtp,
  1716. lockdep_is_held(&table->tb6_lock));
  1717. if (rt == cur) {
  1718. if (fib6_requires_src(cur))
  1719. fib6_routes_require_src_dec(info->nl_net);
  1720. fib6_del_route(table, fn, rtp, info);
  1721. return 0;
  1722. }
  1723. rtp_next = &cur->fib6_next;
  1724. }
  1725. return -ENOENT;
  1726. }
  1727. /*
  1728. * Tree traversal function.
  1729. *
  1730. * Certainly, it is not interrupt safe.
  1731. * However, it is internally reenterable wrt itself and fib6_add/fib6_del.
  1732. * It means, that we can modify tree during walking
  1733. * and use this function for garbage collection, clone pruning,
  1734. * cleaning tree when a device goes down etc. etc.
  1735. *
  1736. * It guarantees that every node will be traversed,
  1737. * and that it will be traversed only once.
  1738. *
  1739. * Callback function w->func may return:
  1740. * 0 -> continue walking.
  1741. * positive value -> walking is suspended (used by tree dumps,
  1742. * and probably by gc, if it will be split to several slices)
  1743. * negative value -> terminate walking.
  1744. *
  1745. * The function itself returns:
  1746. * 0 -> walk is complete.
  1747. * >0 -> walk is incomplete (i.e. suspended)
  1748. * <0 -> walk is terminated by an error.
  1749. *
  1750. * This function is called with tb6_lock held.
  1751. */
  1752. static int fib6_walk_continue(struct fib6_walker *w)
  1753. {
  1754. struct fib6_node *fn, *pn, *left, *right;
  1755. /* w->root should always be table->tb6_root */
  1756. WARN_ON_ONCE(!(w->root->fn_flags & RTN_TL_ROOT));
  1757. for (;;) {
  1758. fn = w->node;
  1759. if (!fn)
  1760. return 0;
  1761. switch (w->state) {
  1762. #ifdef CONFIG_IPV6_SUBTREES
  1763. case FWS_S:
  1764. if (FIB6_SUBTREE(fn)) {
  1765. w->node = FIB6_SUBTREE(fn);
  1766. continue;
  1767. }
  1768. w->state = FWS_L;
  1769. fallthrough;
  1770. #endif
  1771. case FWS_L:
  1772. left = rcu_dereference_protected(fn->left, 1);
  1773. if (left) {
  1774. w->node = left;
  1775. w->state = FWS_INIT;
  1776. continue;
  1777. }
  1778. w->state = FWS_R;
  1779. fallthrough;
  1780. case FWS_R:
  1781. right = rcu_dereference_protected(fn->right, 1);
  1782. if (right) {
  1783. w->node = right;
  1784. w->state = FWS_INIT;
  1785. continue;
  1786. }
  1787. w->state = FWS_C;
  1788. w->leaf = rcu_dereference_protected(fn->leaf, 1);
  1789. fallthrough;
  1790. case FWS_C:
  1791. if (w->leaf && fn->fn_flags & RTN_RTINFO) {
  1792. int err;
  1793. if (w->skip) {
  1794. w->skip--;
  1795. goto skip;
  1796. }
  1797. err = w->func(w);
  1798. if (err)
  1799. return err;
  1800. w->count++;
  1801. continue;
  1802. }
  1803. skip:
  1804. w->state = FWS_U;
  1805. fallthrough;
  1806. case FWS_U:
  1807. if (fn == w->root)
  1808. return 0;
  1809. pn = rcu_dereference_protected(fn->parent, 1);
  1810. left = rcu_dereference_protected(pn->left, 1);
  1811. right = rcu_dereference_protected(pn->right, 1);
  1812. w->node = pn;
  1813. #ifdef CONFIG_IPV6_SUBTREES
  1814. if (FIB6_SUBTREE(pn) == fn) {
  1815. WARN_ON(!(fn->fn_flags & RTN_ROOT));
  1816. w->state = FWS_L;
  1817. continue;
  1818. }
  1819. #endif
  1820. if (left == fn) {
  1821. w->state = FWS_R;
  1822. continue;
  1823. }
  1824. if (right == fn) {
  1825. w->state = FWS_C;
  1826. w->leaf = rcu_dereference_protected(w->node->leaf, 1);
  1827. continue;
  1828. }
  1829. #if RT6_DEBUG >= 2
  1830. WARN_ON(1);
  1831. #endif
  1832. }
  1833. }
  1834. }
  1835. static int fib6_walk(struct net *net, struct fib6_walker *w)
  1836. {
  1837. int res;
  1838. w->state = FWS_INIT;
  1839. w->node = w->root;
  1840. fib6_walker_link(net, w);
  1841. res = fib6_walk_continue(w);
  1842. if (res <= 0)
  1843. fib6_walker_unlink(net, w);
  1844. return res;
  1845. }
  1846. static int fib6_clean_node(struct fib6_walker *w)
  1847. {
  1848. int res;
  1849. struct fib6_info *rt;
  1850. struct fib6_cleaner *c = container_of(w, struct fib6_cleaner, w);
  1851. struct nl_info info = {
  1852. .nl_net = c->net,
  1853. .skip_notify = c->skip_notify,
  1854. };
  1855. if (c->sernum != FIB6_NO_SERNUM_CHANGE &&
  1856. READ_ONCE(w->node->fn_sernum) != c->sernum)
  1857. WRITE_ONCE(w->node->fn_sernum, c->sernum);
  1858. if (!c->func) {
  1859. WARN_ON_ONCE(c->sernum == FIB6_NO_SERNUM_CHANGE);
  1860. w->leaf = NULL;
  1861. return 0;
  1862. }
  1863. for_each_fib6_walker_rt(w) {
  1864. res = c->func(rt, c->arg);
  1865. if (res == -1) {
  1866. w->leaf = rt;
  1867. res = fib6_del(rt, &info);
  1868. if (res) {
  1869. #if RT6_DEBUG >= 2
  1870. pr_debug("%s: del failed: rt=%p@%p err=%d\n",
  1871. __func__, rt,
  1872. rcu_access_pointer(rt->fib6_node),
  1873. res);
  1874. #endif
  1875. continue;
  1876. }
  1877. return 0;
  1878. } else if (res == -2) {
  1879. if (WARN_ON(!rt->fib6_nsiblings))
  1880. continue;
  1881. rt = list_last_entry(&rt->fib6_siblings,
  1882. struct fib6_info, fib6_siblings);
  1883. continue;
  1884. }
  1885. WARN_ON(res != 0);
  1886. }
  1887. w->leaf = rt;
  1888. return 0;
  1889. }
  1890. /*
  1891. * Convenient frontend to tree walker.
  1892. *
  1893. * func is called on each route.
  1894. * It may return -2 -> skip multipath route.
  1895. * -1 -> delete this route.
  1896. * 0 -> continue walking
  1897. */
  1898. static void fib6_clean_tree(struct net *net, struct fib6_node *root,
  1899. int (*func)(struct fib6_info *, void *arg),
  1900. int sernum, void *arg, bool skip_notify)
  1901. {
  1902. struct fib6_cleaner c;
  1903. c.w.root = root;
  1904. c.w.func = fib6_clean_node;
  1905. c.w.count = 0;
  1906. c.w.skip = 0;
  1907. c.w.skip_in_node = 0;
  1908. c.func = func;
  1909. c.sernum = sernum;
  1910. c.arg = arg;
  1911. c.net = net;
  1912. c.skip_notify = skip_notify;
  1913. fib6_walk(net, &c.w);
  1914. }
  1915. static void __fib6_clean_all(struct net *net,
  1916. int (*func)(struct fib6_info *, void *),
  1917. int sernum, void *arg, bool skip_notify)
  1918. {
  1919. struct fib6_table *table;
  1920. struct hlist_head *head;
  1921. unsigned int h;
  1922. rcu_read_lock();
  1923. for (h = 0; h < FIB6_TABLE_HASHSZ; h++) {
  1924. head = &net->ipv6.fib_table_hash[h];
  1925. hlist_for_each_entry_rcu(table, head, tb6_hlist) {
  1926. spin_lock_bh(&table->tb6_lock);
  1927. fib6_clean_tree(net, &table->tb6_root,
  1928. func, sernum, arg, skip_notify);
  1929. spin_unlock_bh(&table->tb6_lock);
  1930. }
  1931. }
  1932. rcu_read_unlock();
  1933. }
  1934. void fib6_clean_all(struct net *net, int (*func)(struct fib6_info *, void *),
  1935. void *arg)
  1936. {
  1937. __fib6_clean_all(net, func, FIB6_NO_SERNUM_CHANGE, arg, false);
  1938. }
  1939. void fib6_clean_all_skip_notify(struct net *net,
  1940. int (*func)(struct fib6_info *, void *),
  1941. void *arg)
  1942. {
  1943. __fib6_clean_all(net, func, FIB6_NO_SERNUM_CHANGE, arg, true);
  1944. }
  1945. static void fib6_flush_trees(struct net *net)
  1946. {
  1947. int new_sernum = fib6_new_sernum(net);
  1948. __fib6_clean_all(net, NULL, new_sernum, NULL, false);
  1949. }
  1950. /*
  1951. * Garbage collection
  1952. */
  1953. static int fib6_age(struct fib6_info *rt, void *arg)
  1954. {
  1955. struct fib6_gc_args *gc_args = arg;
  1956. unsigned long now = jiffies;
  1957. /*
  1958. * check addrconf expiration here.
  1959. * Routes are expired even if they are in use.
  1960. */
  1961. if (rt->fib6_flags & RTF_EXPIRES && rt->expires) {
  1962. if (time_after(now, rt->expires)) {
  1963. RT6_TRACE("expiring %p\n", rt);
  1964. return -1;
  1965. }
  1966. gc_args->more++;
  1967. }
  1968. /* Also age clones in the exception table.
  1969. * Note, that clones are aged out
  1970. * only if they are not in use now.
  1971. */
  1972. rt6_age_exceptions(rt, gc_args, now);
  1973. return 0;
  1974. }
  1975. void fib6_run_gc(unsigned long expires, struct net *net, bool force)
  1976. {
  1977. struct fib6_gc_args gc_args;
  1978. unsigned long now;
  1979. if (force) {
  1980. spin_lock_bh(&net->ipv6.fib6_gc_lock);
  1981. } else if (!spin_trylock_bh(&net->ipv6.fib6_gc_lock)) {
  1982. mod_timer(&net->ipv6.ip6_fib_timer, jiffies + HZ);
  1983. return;
  1984. }
  1985. gc_args.timeout = expires ? (int)expires :
  1986. net->ipv6.sysctl.ip6_rt_gc_interval;
  1987. gc_args.more = 0;
  1988. fib6_clean_all(net, fib6_age, &gc_args);
  1989. now = jiffies;
  1990. net->ipv6.ip6_rt_last_gc = now;
  1991. if (gc_args.more)
  1992. mod_timer(&net->ipv6.ip6_fib_timer,
  1993. round_jiffies(now
  1994. + net->ipv6.sysctl.ip6_rt_gc_interval));
  1995. else
  1996. del_timer(&net->ipv6.ip6_fib_timer);
  1997. spin_unlock_bh(&net->ipv6.fib6_gc_lock);
  1998. }
  1999. static void fib6_gc_timer_cb(struct timer_list *t)
  2000. {
  2001. struct net *arg = from_timer(arg, t, ipv6.ip6_fib_timer);
  2002. fib6_run_gc(0, arg, true);
  2003. }
  2004. static int __net_init fib6_net_init(struct net *net)
  2005. {
  2006. size_t size = sizeof(struct hlist_head) * FIB6_TABLE_HASHSZ;
  2007. int err;
  2008. err = fib6_notifier_init(net);
  2009. if (err)
  2010. return err;
  2011. spin_lock_init(&net->ipv6.fib6_gc_lock);
  2012. rwlock_init(&net->ipv6.fib6_walker_lock);
  2013. INIT_LIST_HEAD(&net->ipv6.fib6_walkers);
  2014. timer_setup(&net->ipv6.ip6_fib_timer, fib6_gc_timer_cb, 0);
  2015. net->ipv6.rt6_stats = kzalloc(sizeof(*net->ipv6.rt6_stats), GFP_KERNEL);
  2016. if (!net->ipv6.rt6_stats)
  2017. goto out_timer;
  2018. /* Avoid false sharing : Use at least a full cache line */
  2019. size = max_t(size_t, size, L1_CACHE_BYTES);
  2020. net->ipv6.fib_table_hash = kzalloc(size, GFP_KERNEL);
  2021. if (!net->ipv6.fib_table_hash)
  2022. goto out_rt6_stats;
  2023. net->ipv6.fib6_main_tbl = kzalloc(sizeof(*net->ipv6.fib6_main_tbl),
  2024. GFP_KERNEL);
  2025. if (!net->ipv6.fib6_main_tbl)
  2026. goto out_fib_table_hash;
  2027. net->ipv6.fib6_main_tbl->tb6_id = RT6_TABLE_MAIN;
  2028. rcu_assign_pointer(net->ipv6.fib6_main_tbl->tb6_root.leaf,
  2029. net->ipv6.fib6_null_entry);
  2030. net->ipv6.fib6_main_tbl->tb6_root.fn_flags =
  2031. RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
  2032. inet_peer_base_init(&net->ipv6.fib6_main_tbl->tb6_peers);
  2033. #ifdef CONFIG_IPV6_MULTIPLE_TABLES
  2034. net->ipv6.fib6_local_tbl = kzalloc(sizeof(*net->ipv6.fib6_local_tbl),
  2035. GFP_KERNEL);
  2036. if (!net->ipv6.fib6_local_tbl)
  2037. goto out_fib6_main_tbl;
  2038. net->ipv6.fib6_local_tbl->tb6_id = RT6_TABLE_LOCAL;
  2039. rcu_assign_pointer(net->ipv6.fib6_local_tbl->tb6_root.leaf,
  2040. net->ipv6.fib6_null_entry);
  2041. net->ipv6.fib6_local_tbl->tb6_root.fn_flags =
  2042. RTN_ROOT | RTN_TL_ROOT | RTN_RTINFO;
  2043. inet_peer_base_init(&net->ipv6.fib6_local_tbl->tb6_peers);
  2044. #endif
  2045. fib6_tables_init(net);
  2046. return 0;
  2047. #ifdef CONFIG_IPV6_MULTIPLE_TABLES
  2048. out_fib6_main_tbl:
  2049. kfree(net->ipv6.fib6_main_tbl);
  2050. #endif
  2051. out_fib_table_hash:
  2052. kfree(net->ipv6.fib_table_hash);
  2053. out_rt6_stats:
  2054. kfree(net->ipv6.rt6_stats);
  2055. out_timer:
  2056. fib6_notifier_exit(net);
  2057. return -ENOMEM;
  2058. }
  2059. static void fib6_net_exit(struct net *net)
  2060. {
  2061. unsigned int i;
  2062. del_timer_sync(&net->ipv6.ip6_fib_timer);
  2063. for (i = 0; i < FIB6_TABLE_HASHSZ; i++) {
  2064. struct hlist_head *head = &net->ipv6.fib_table_hash[i];
  2065. struct hlist_node *tmp;
  2066. struct fib6_table *tb;
  2067. hlist_for_each_entry_safe(tb, tmp, head, tb6_hlist) {
  2068. hlist_del(&tb->tb6_hlist);
  2069. fib6_free_table(tb);
  2070. }
  2071. }
  2072. kfree(net->ipv6.fib_table_hash);
  2073. kfree(net->ipv6.rt6_stats);
  2074. fib6_notifier_exit(net);
  2075. }
  2076. static struct pernet_operations fib6_net_ops = {
  2077. .init = fib6_net_init,
  2078. .exit = fib6_net_exit,
  2079. };
  2080. int __init fib6_init(void)
  2081. {
  2082. int ret = -ENOMEM;
  2083. fib6_node_kmem = kmem_cache_create("fib6_nodes",
  2084. sizeof(struct fib6_node),
  2085. 0, SLAB_HWCACHE_ALIGN,
  2086. NULL);
  2087. if (!fib6_node_kmem)
  2088. goto out;
  2089. ret = register_pernet_subsys(&fib6_net_ops);
  2090. if (ret)
  2091. goto out_kmem_cache_create;
  2092. ret = rtnl_register_module(THIS_MODULE, PF_INET6, RTM_GETROUTE, NULL,
  2093. inet6_dump_fib, 0);
  2094. if (ret)
  2095. goto out_unregister_subsys;
  2096. __fib6_flush_trees = fib6_flush_trees;
  2097. out:
  2098. return ret;
  2099. out_unregister_subsys:
  2100. unregister_pernet_subsys(&fib6_net_ops);
  2101. out_kmem_cache_create:
  2102. kmem_cache_destroy(fib6_node_kmem);
  2103. goto out;
  2104. }
  2105. void fib6_gc_cleanup(void)
  2106. {
  2107. unregister_pernet_subsys(&fib6_net_ops);
  2108. kmem_cache_destroy(fib6_node_kmem);
  2109. }
  2110. #ifdef CONFIG_PROC_FS
  2111. static int ipv6_route_native_seq_show(struct seq_file *seq, void *v)
  2112. {
  2113. struct fib6_info *rt = v;
  2114. struct ipv6_route_iter *iter = seq->private;
  2115. struct fib6_nh *fib6_nh = rt->fib6_nh;
  2116. unsigned int flags = rt->fib6_flags;
  2117. const struct net_device *dev;
  2118. if (rt->nh)
  2119. fib6_nh = nexthop_fib6_nh_bh(rt->nh);
  2120. seq_printf(seq, "%pi6 %02x ", &rt->fib6_dst.addr, rt->fib6_dst.plen);
  2121. #ifdef CONFIG_IPV6_SUBTREES
  2122. seq_printf(seq, "%pi6 %02x ", &rt->fib6_src.addr, rt->fib6_src.plen);
  2123. #else
  2124. seq_puts(seq, "00000000000000000000000000000000 00 ");
  2125. #endif
  2126. if (fib6_nh->fib_nh_gw_family) {
  2127. flags |= RTF_GATEWAY;
  2128. seq_printf(seq, "%pi6", &fib6_nh->fib_nh_gw6);
  2129. } else {
  2130. seq_puts(seq, "00000000000000000000000000000000");
  2131. }
  2132. dev = fib6_nh->fib_nh_dev;
  2133. seq_printf(seq, " %08x %08x %08x %08x %8s\n",
  2134. rt->fib6_metric, refcount_read(&rt->fib6_ref), 0,
  2135. flags, dev ? dev->name : "");
  2136. iter->w.leaf = NULL;
  2137. return 0;
  2138. }
  2139. static int ipv6_route_yield(struct fib6_walker *w)
  2140. {
  2141. struct ipv6_route_iter *iter = w->args;
  2142. if (!iter->skip)
  2143. return 1;
  2144. do {
  2145. iter->w.leaf = rcu_dereference_protected(
  2146. iter->w.leaf->fib6_next,
  2147. lockdep_is_held(&iter->tbl->tb6_lock));
  2148. iter->skip--;
  2149. if (!iter->skip && iter->w.leaf)
  2150. return 1;
  2151. } while (iter->w.leaf);
  2152. return 0;
  2153. }
  2154. static void ipv6_route_seq_setup_walk(struct ipv6_route_iter *iter,
  2155. struct net *net)
  2156. {
  2157. memset(&iter->w, 0, sizeof(iter->w));
  2158. iter->w.func = ipv6_route_yield;
  2159. iter->w.root = &iter->tbl->tb6_root;
  2160. iter->w.state = FWS_INIT;
  2161. iter->w.node = iter->w.root;
  2162. iter->w.args = iter;
  2163. iter->sernum = READ_ONCE(iter->w.root->fn_sernum);
  2164. INIT_LIST_HEAD(&iter->w.lh);
  2165. fib6_walker_link(net, &iter->w);
  2166. }
  2167. static struct fib6_table *ipv6_route_seq_next_table(struct fib6_table *tbl,
  2168. struct net *net)
  2169. {
  2170. unsigned int h;
  2171. struct hlist_node *node;
  2172. if (tbl) {
  2173. h = (tbl->tb6_id & (FIB6_TABLE_HASHSZ - 1)) + 1;
  2174. node = rcu_dereference_bh(hlist_next_rcu(&tbl->tb6_hlist));
  2175. } else {
  2176. h = 0;
  2177. node = NULL;
  2178. }
  2179. while (!node && h < FIB6_TABLE_HASHSZ) {
  2180. node = rcu_dereference_bh(
  2181. hlist_first_rcu(&net->ipv6.fib_table_hash[h++]));
  2182. }
  2183. return hlist_entry_safe(node, struct fib6_table, tb6_hlist);
  2184. }
  2185. static void ipv6_route_check_sernum(struct ipv6_route_iter *iter)
  2186. {
  2187. int sernum = READ_ONCE(iter->w.root->fn_sernum);
  2188. if (iter->sernum != sernum) {
  2189. iter->sernum = sernum;
  2190. iter->w.state = FWS_INIT;
  2191. iter->w.node = iter->w.root;
  2192. WARN_ON(iter->w.skip);
  2193. iter->w.skip = iter->w.count;
  2194. }
  2195. }
  2196. static void *ipv6_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
  2197. {
  2198. int r;
  2199. struct fib6_info *n;
  2200. struct net *net = seq_file_net(seq);
  2201. struct ipv6_route_iter *iter = seq->private;
  2202. ++(*pos);
  2203. if (!v)
  2204. goto iter_table;
  2205. n = rcu_dereference_bh(((struct fib6_info *)v)->fib6_next);
  2206. if (n)
  2207. return n;
  2208. iter_table:
  2209. ipv6_route_check_sernum(iter);
  2210. spin_lock_bh(&iter->tbl->tb6_lock);
  2211. r = fib6_walk_continue(&iter->w);
  2212. spin_unlock_bh(&iter->tbl->tb6_lock);
  2213. if (r > 0) {
  2214. return iter->w.leaf;
  2215. } else if (r < 0) {
  2216. fib6_walker_unlink(net, &iter->w);
  2217. return NULL;
  2218. }
  2219. fib6_walker_unlink(net, &iter->w);
  2220. iter->tbl = ipv6_route_seq_next_table(iter->tbl, net);
  2221. if (!iter->tbl)
  2222. return NULL;
  2223. ipv6_route_seq_setup_walk(iter, net);
  2224. goto iter_table;
  2225. }
  2226. static void *ipv6_route_seq_start(struct seq_file *seq, loff_t *pos)
  2227. __acquires(RCU_BH)
  2228. {
  2229. struct net *net = seq_file_net(seq);
  2230. struct ipv6_route_iter *iter = seq->private;
  2231. rcu_read_lock_bh();
  2232. iter->tbl = ipv6_route_seq_next_table(NULL, net);
  2233. iter->skip = *pos;
  2234. if (iter->tbl) {
  2235. loff_t p = 0;
  2236. ipv6_route_seq_setup_walk(iter, net);
  2237. return ipv6_route_seq_next(seq, NULL, &p);
  2238. } else {
  2239. return NULL;
  2240. }
  2241. }
  2242. static bool ipv6_route_iter_active(struct ipv6_route_iter *iter)
  2243. {
  2244. struct fib6_walker *w = &iter->w;
  2245. return w->node && !(w->state == FWS_U && w->node == w->root);
  2246. }
  2247. static void ipv6_route_native_seq_stop(struct seq_file *seq, void *v)
  2248. __releases(RCU_BH)
  2249. {
  2250. struct net *net = seq_file_net(seq);
  2251. struct ipv6_route_iter *iter = seq->private;
  2252. if (ipv6_route_iter_active(iter))
  2253. fib6_walker_unlink(net, &iter->w);
  2254. rcu_read_unlock_bh();
  2255. }
  2256. #if IS_BUILTIN(CONFIG_IPV6) && defined(CONFIG_BPF_SYSCALL)
  2257. static int ipv6_route_prog_seq_show(struct bpf_prog *prog,
  2258. struct bpf_iter_meta *meta,
  2259. void *v)
  2260. {
  2261. struct bpf_iter__ipv6_route ctx;
  2262. ctx.meta = meta;
  2263. ctx.rt = v;
  2264. return bpf_iter_run_prog(prog, &ctx);
  2265. }
  2266. static int ipv6_route_seq_show(struct seq_file *seq, void *v)
  2267. {
  2268. struct ipv6_route_iter *iter = seq->private;
  2269. struct bpf_iter_meta meta;
  2270. struct bpf_prog *prog;
  2271. int ret;
  2272. meta.seq = seq;
  2273. prog = bpf_iter_get_info(&meta, false);
  2274. if (!prog)
  2275. return ipv6_route_native_seq_show(seq, v);
  2276. ret = ipv6_route_prog_seq_show(prog, &meta, v);
  2277. iter->w.leaf = NULL;
  2278. return ret;
  2279. }
  2280. static void ipv6_route_seq_stop(struct seq_file *seq, void *v)
  2281. {
  2282. struct bpf_iter_meta meta;
  2283. struct bpf_prog *prog;
  2284. if (!v) {
  2285. meta.seq = seq;
  2286. prog = bpf_iter_get_info(&meta, true);
  2287. if (prog)
  2288. (void)ipv6_route_prog_seq_show(prog, &meta, v);
  2289. }
  2290. ipv6_route_native_seq_stop(seq, v);
  2291. }
  2292. #else
  2293. static int ipv6_route_seq_show(struct seq_file *seq, void *v)
  2294. {
  2295. return ipv6_route_native_seq_show(seq, v);
  2296. }
  2297. static void ipv6_route_seq_stop(struct seq_file *seq, void *v)
  2298. {
  2299. ipv6_route_native_seq_stop(seq, v);
  2300. }
  2301. #endif
  2302. const struct seq_operations ipv6_route_seq_ops = {
  2303. .start = ipv6_route_seq_start,
  2304. .next = ipv6_route_seq_next,
  2305. .stop = ipv6_route_seq_stop,
  2306. .show = ipv6_route_seq_show
  2307. };
  2308. #endif /* CONFIG_PROC_FS */