fib_semantics.c 31 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329
  1. /*
  2. * INET An implementation of the TCP/IP protocol suite for the LINUX
  3. * operating system. INET is implemented using the BSD Socket
  4. * interface as the means of communication with the user level.
  5. *
  6. * IPv4 Forwarding Information Base: semantics.
  7. *
  8. * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
  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. #include <asm/uaccess.h>
  16. #include <linux/bitops.h>
  17. #include <linux/types.h>
  18. #include <linux/kernel.h>
  19. #include <linux/jiffies.h>
  20. #include <linux/mm.h>
  21. #include <linux/string.h>
  22. #include <linux/socket.h>
  23. #include <linux/sockios.h>
  24. #include <linux/errno.h>
  25. #include <linux/in.h>
  26. #include <linux/inet.h>
  27. #include <linux/inetdevice.h>
  28. #include <linux/netdevice.h>
  29. #include <linux/if_arp.h>
  30. #include <linux/proc_fs.h>
  31. #include <linux/skbuff.h>
  32. #include <linux/init.h>
  33. #include <linux/slab.h>
  34. #include <net/arp.h>
  35. #include <net/ip.h>
  36. #include <net/protocol.h>
  37. #include <net/route.h>
  38. #include <net/tcp.h>
  39. #include <net/sock.h>
  40. #include <net/ip_fib.h>
  41. #include <net/netlink.h>
  42. #include <net/nexthop.h>
  43. #include "fib_lookup.h"
  44. static DEFINE_SPINLOCK(fib_info_lock);
  45. static struct hlist_head *fib_info_hash;
  46. static struct hlist_head *fib_info_laddrhash;
  47. static unsigned int fib_info_hash_size;
  48. static unsigned int fib_info_cnt;
  49. #define DEVINDEX_HASHBITS 8
  50. #define DEVINDEX_HASHSIZE (1U << DEVINDEX_HASHBITS)
  51. static struct hlist_head fib_info_devhash[DEVINDEX_HASHSIZE];
  52. #ifdef CONFIG_IP_ROUTE_MULTIPATH
  53. static DEFINE_SPINLOCK(fib_multipath_lock);
  54. #define for_nexthops(fi) { \
  55. int nhsel; const struct fib_nh *nh; \
  56. for (nhsel = 0, nh = (fi)->fib_nh; \
  57. nhsel < (fi)->fib_nhs; \
  58. nh++, nhsel++)
  59. #define change_nexthops(fi) { \
  60. int nhsel; struct fib_nh *nexthop_nh; \
  61. for (nhsel = 0, nexthop_nh = (struct fib_nh *)((fi)->fib_nh); \
  62. nhsel < (fi)->fib_nhs; \
  63. nexthop_nh++, nhsel++)
  64. #else /* CONFIG_IP_ROUTE_MULTIPATH */
  65. /* Hope, that gcc will optimize it to get rid of dummy loop */
  66. #define for_nexthops(fi) { \
  67. int nhsel; const struct fib_nh *nh = (fi)->fib_nh; \
  68. for (nhsel = 0; nhsel < 1; nhsel++)
  69. #define change_nexthops(fi) { \
  70. int nhsel; \
  71. struct fib_nh *nexthop_nh = (struct fib_nh *)((fi)->fib_nh); \
  72. for (nhsel = 0; nhsel < 1; nhsel++)
  73. #endif /* CONFIG_IP_ROUTE_MULTIPATH */
  74. #define endfor_nexthops(fi) }
  75. const struct fib_prop fib_props[RTN_MAX + 1] = {
  76. [RTN_UNSPEC] = {
  77. .error = 0,
  78. .scope = RT_SCOPE_NOWHERE,
  79. },
  80. [RTN_UNICAST] = {
  81. .error = 0,
  82. .scope = RT_SCOPE_UNIVERSE,
  83. },
  84. [RTN_LOCAL] = {
  85. .error = 0,
  86. .scope = RT_SCOPE_HOST,
  87. },
  88. [RTN_BROADCAST] = {
  89. .error = 0,
  90. .scope = RT_SCOPE_LINK,
  91. },
  92. [RTN_ANYCAST] = {
  93. .error = 0,
  94. .scope = RT_SCOPE_LINK,
  95. },
  96. [RTN_MULTICAST] = {
  97. .error = 0,
  98. .scope = RT_SCOPE_UNIVERSE,
  99. },
  100. [RTN_BLACKHOLE] = {
  101. .error = -EINVAL,
  102. .scope = RT_SCOPE_UNIVERSE,
  103. },
  104. [RTN_UNREACHABLE] = {
  105. .error = -EHOSTUNREACH,
  106. .scope = RT_SCOPE_UNIVERSE,
  107. },
  108. [RTN_PROHIBIT] = {
  109. .error = -EACCES,
  110. .scope = RT_SCOPE_UNIVERSE,
  111. },
  112. [RTN_THROW] = {
  113. .error = -EAGAIN,
  114. .scope = RT_SCOPE_UNIVERSE,
  115. },
  116. [RTN_NAT] = {
  117. .error = -EINVAL,
  118. .scope = RT_SCOPE_NOWHERE,
  119. },
  120. [RTN_XRESOLVE] = {
  121. .error = -EINVAL,
  122. .scope = RT_SCOPE_NOWHERE,
  123. },
  124. };
  125. static void free_nh_exceptions(struct fib_nh *nh)
  126. {
  127. struct fnhe_hash_bucket *hash = nh->nh_exceptions;
  128. int i;
  129. for (i = 0; i < FNHE_HASH_SIZE; i++) {
  130. struct fib_nh_exception *fnhe;
  131. fnhe = rcu_dereference_protected(hash[i].chain, 1);
  132. while (fnhe) {
  133. struct fib_nh_exception *next;
  134. next = rcu_dereference_protected(fnhe->fnhe_next, 1);
  135. kfree(fnhe);
  136. fnhe = next;
  137. }
  138. }
  139. kfree(hash);
  140. }
  141. static void rt_nexthop_free(struct rtable __rcu **rtp)
  142. {
  143. struct rtable *rt = rcu_dereference_protected(*rtp, 1);
  144. if (!rt)
  145. return;
  146. /* Not even needed : RCU_INIT_POINTER(*rtp, NULL);
  147. * because we waited an RCU grace period before calling
  148. * free_fib_info_rcu()
  149. */
  150. dst_free(&rt->dst);
  151. }
  152. static void rt_nexthop_free_cpus(struct rtable __rcu * __percpu *rtp)
  153. {
  154. int cpu;
  155. if (!rtp)
  156. return;
  157. for_each_possible_cpu(cpu) {
  158. struct rtable *rt;
  159. rt = rcu_dereference_protected(*per_cpu_ptr(rtp, cpu), 1);
  160. if (rt)
  161. dst_free(&rt->dst);
  162. }
  163. free_percpu(rtp);
  164. }
  165. /* Release a nexthop info record */
  166. static void free_fib_info_rcu(struct rcu_head *head)
  167. {
  168. struct fib_info *fi = container_of(head, struct fib_info, rcu);
  169. change_nexthops(fi) {
  170. if (nexthop_nh->nh_dev)
  171. dev_put(nexthop_nh->nh_dev);
  172. if (nexthop_nh->nh_exceptions)
  173. free_nh_exceptions(nexthop_nh);
  174. rt_nexthop_free_cpus(nexthop_nh->nh_pcpu_rth_output);
  175. rt_nexthop_free(&nexthop_nh->nh_rth_input);
  176. } endfor_nexthops(fi);
  177. release_net(fi->fib_net);
  178. if (fi->fib_metrics != (u32 *) dst_default_metrics)
  179. kfree(fi->fib_metrics);
  180. kfree(fi);
  181. }
  182. void free_fib_info(struct fib_info *fi)
  183. {
  184. if (fi->fib_dead == 0) {
  185. pr_warn("Freeing alive fib_info %p\n", fi);
  186. return;
  187. }
  188. fib_info_cnt--;
  189. #ifdef CONFIG_IP_ROUTE_CLASSID
  190. change_nexthops(fi) {
  191. if (nexthop_nh->nh_tclassid)
  192. fi->fib_net->ipv4.fib_num_tclassid_users--;
  193. } endfor_nexthops(fi);
  194. #endif
  195. call_rcu(&fi->rcu, free_fib_info_rcu);
  196. }
  197. void fib_release_info(struct fib_info *fi)
  198. {
  199. spin_lock_bh(&fib_info_lock);
  200. if (fi && --fi->fib_treeref == 0) {
  201. hlist_del(&fi->fib_hash);
  202. if (fi->fib_prefsrc)
  203. hlist_del(&fi->fib_lhash);
  204. change_nexthops(fi) {
  205. if (!nexthop_nh->nh_dev)
  206. continue;
  207. hlist_del(&nexthop_nh->nh_hash);
  208. } endfor_nexthops(fi)
  209. fi->fib_dead = 1;
  210. fib_info_put(fi);
  211. }
  212. spin_unlock_bh(&fib_info_lock);
  213. }
  214. static inline int nh_comp(const struct fib_info *fi, const struct fib_info *ofi)
  215. {
  216. const struct fib_nh *onh = ofi->fib_nh;
  217. for_nexthops(fi) {
  218. if (nh->nh_oif != onh->nh_oif ||
  219. nh->nh_gw != onh->nh_gw ||
  220. nh->nh_scope != onh->nh_scope ||
  221. #ifdef CONFIG_IP_ROUTE_MULTIPATH
  222. nh->nh_weight != onh->nh_weight ||
  223. #endif
  224. #ifdef CONFIG_IP_ROUTE_CLASSID
  225. nh->nh_tclassid != onh->nh_tclassid ||
  226. #endif
  227. ((nh->nh_flags ^ onh->nh_flags) & ~RTNH_F_DEAD))
  228. return -1;
  229. onh++;
  230. } endfor_nexthops(fi);
  231. return 0;
  232. }
  233. static inline unsigned int fib_devindex_hashfn(unsigned int val)
  234. {
  235. unsigned int mask = DEVINDEX_HASHSIZE - 1;
  236. return (val ^
  237. (val >> DEVINDEX_HASHBITS) ^
  238. (val >> (DEVINDEX_HASHBITS * 2))) & mask;
  239. }
  240. static inline unsigned int fib_info_hashfn(const struct fib_info *fi)
  241. {
  242. unsigned int mask = (fib_info_hash_size - 1);
  243. unsigned int val = fi->fib_nhs;
  244. val ^= (fi->fib_protocol << 8) | fi->fib_scope;
  245. val ^= (__force u32)fi->fib_prefsrc;
  246. val ^= fi->fib_priority;
  247. for_nexthops(fi) {
  248. val ^= fib_devindex_hashfn(nh->nh_oif);
  249. } endfor_nexthops(fi)
  250. return (val ^ (val >> 7) ^ (val >> 12)) & mask;
  251. }
  252. static struct fib_info *fib_find_info(const struct fib_info *nfi)
  253. {
  254. struct hlist_head *head;
  255. struct hlist_node *node;
  256. struct fib_info *fi;
  257. unsigned int hash;
  258. hash = fib_info_hashfn(nfi);
  259. head = &fib_info_hash[hash];
  260. hlist_for_each_entry(fi, node, head, fib_hash) {
  261. if (!net_eq(fi->fib_net, nfi->fib_net))
  262. continue;
  263. if (fi->fib_nhs != nfi->fib_nhs)
  264. continue;
  265. if (nfi->fib_protocol == fi->fib_protocol &&
  266. nfi->fib_scope == fi->fib_scope &&
  267. nfi->fib_prefsrc == fi->fib_prefsrc &&
  268. nfi->fib_priority == fi->fib_priority &&
  269. memcmp(nfi->fib_metrics, fi->fib_metrics,
  270. sizeof(u32) * RTAX_MAX) == 0 &&
  271. ((nfi->fib_flags ^ fi->fib_flags) & ~RTNH_F_DEAD) == 0 &&
  272. (nfi->fib_nhs == 0 || nh_comp(fi, nfi) == 0))
  273. return fi;
  274. }
  275. return NULL;
  276. }
  277. /* Check, that the gateway is already configured.
  278. * Used only by redirect accept routine.
  279. */
  280. int ip_fib_check_default(__be32 gw, struct net_device *dev)
  281. {
  282. struct hlist_head *head;
  283. struct hlist_node *node;
  284. struct fib_nh *nh;
  285. unsigned int hash;
  286. spin_lock(&fib_info_lock);
  287. hash = fib_devindex_hashfn(dev->ifindex);
  288. head = &fib_info_devhash[hash];
  289. hlist_for_each_entry(nh, node, head, nh_hash) {
  290. if (nh->nh_dev == dev &&
  291. nh->nh_gw == gw &&
  292. !(nh->nh_flags & RTNH_F_DEAD)) {
  293. spin_unlock(&fib_info_lock);
  294. return 0;
  295. }
  296. }
  297. spin_unlock(&fib_info_lock);
  298. return -1;
  299. }
  300. static inline size_t fib_nlmsg_size(struct fib_info *fi)
  301. {
  302. size_t payload = NLMSG_ALIGN(sizeof(struct rtmsg))
  303. + nla_total_size(4) /* RTA_TABLE */
  304. + nla_total_size(4) /* RTA_DST */
  305. + nla_total_size(4) /* RTA_PRIORITY */
  306. + nla_total_size(4); /* RTA_PREFSRC */
  307. /* space for nested metrics */
  308. payload += nla_total_size((RTAX_MAX * nla_total_size(4)));
  309. if (fi->fib_nhs) {
  310. /* Also handles the special case fib_nhs == 1 */
  311. /* each nexthop is packed in an attribute */
  312. size_t nhsize = nla_total_size(sizeof(struct rtnexthop));
  313. /* may contain flow and gateway attribute */
  314. nhsize += 2 * nla_total_size(4);
  315. /* all nexthops are packed in a nested attribute */
  316. payload += nla_total_size(fi->fib_nhs * nhsize);
  317. }
  318. return payload;
  319. }
  320. void rtmsg_fib(int event, __be32 key, struct fib_alias *fa,
  321. int dst_len, u32 tb_id, struct nl_info *info,
  322. unsigned int nlm_flags)
  323. {
  324. struct sk_buff *skb;
  325. u32 seq = info->nlh ? info->nlh->nlmsg_seq : 0;
  326. int err = -ENOBUFS;
  327. skb = nlmsg_new(fib_nlmsg_size(fa->fa_info), GFP_KERNEL);
  328. if (skb == NULL)
  329. goto errout;
  330. err = fib_dump_info(skb, info->pid, seq, event, tb_id,
  331. fa->fa_type, key, dst_len,
  332. fa->fa_tos, fa->fa_info, nlm_flags);
  333. if (err < 0) {
  334. /* -EMSGSIZE implies BUG in fib_nlmsg_size() */
  335. WARN_ON(err == -EMSGSIZE);
  336. kfree_skb(skb);
  337. goto errout;
  338. }
  339. rtnl_notify(skb, info->nl_net, info->pid, RTNLGRP_IPV4_ROUTE,
  340. info->nlh, GFP_KERNEL);
  341. return;
  342. errout:
  343. if (err < 0)
  344. rtnl_set_sk_err(info->nl_net, RTNLGRP_IPV4_ROUTE, err);
  345. }
  346. /* Return the first fib alias matching TOS with
  347. * priority less than or equal to PRIO.
  348. */
  349. struct fib_alias *fib_find_alias(struct list_head *fah, u8 tos, u32 prio)
  350. {
  351. if (fah) {
  352. struct fib_alias *fa;
  353. list_for_each_entry(fa, fah, fa_list) {
  354. if (fa->fa_tos > tos)
  355. continue;
  356. if (fa->fa_info->fib_priority >= prio ||
  357. fa->fa_tos < tos)
  358. return fa;
  359. }
  360. }
  361. return NULL;
  362. }
  363. int fib_detect_death(struct fib_info *fi, int order,
  364. struct fib_info **last_resort, int *last_idx, int dflt)
  365. {
  366. struct neighbour *n;
  367. int state = NUD_NONE;
  368. n = neigh_lookup(&arp_tbl, &fi->fib_nh[0].nh_gw, fi->fib_dev);
  369. if (n) {
  370. state = n->nud_state;
  371. neigh_release(n);
  372. }
  373. if (state == NUD_REACHABLE)
  374. return 0;
  375. if ((state & NUD_VALID) && order != dflt)
  376. return 0;
  377. if ((state & NUD_VALID) ||
  378. (*last_idx < 0 && order > dflt)) {
  379. *last_resort = fi;
  380. *last_idx = order;
  381. }
  382. return 1;
  383. }
  384. #ifdef CONFIG_IP_ROUTE_MULTIPATH
  385. static int fib_count_nexthops(struct rtnexthop *rtnh, int remaining)
  386. {
  387. int nhs = 0;
  388. while (rtnh_ok(rtnh, remaining)) {
  389. nhs++;
  390. rtnh = rtnh_next(rtnh, &remaining);
  391. }
  392. /* leftover implies invalid nexthop configuration, discard it */
  393. return remaining > 0 ? 0 : nhs;
  394. }
  395. static int fib_get_nhs(struct fib_info *fi, struct rtnexthop *rtnh,
  396. int remaining, struct fib_config *cfg)
  397. {
  398. change_nexthops(fi) {
  399. int attrlen;
  400. if (!rtnh_ok(rtnh, remaining))
  401. return -EINVAL;
  402. nexthop_nh->nh_flags =
  403. (cfg->fc_flags & ~0xFF) | rtnh->rtnh_flags;
  404. nexthop_nh->nh_oif = rtnh->rtnh_ifindex;
  405. nexthop_nh->nh_weight = rtnh->rtnh_hops + 1;
  406. attrlen = rtnh_attrlen(rtnh);
  407. if (attrlen > 0) {
  408. struct nlattr *nla, *attrs = rtnh_attrs(rtnh);
  409. nla = nla_find(attrs, attrlen, RTA_GATEWAY);
  410. nexthop_nh->nh_gw = nla ? nla_get_be32(nla) : 0;
  411. #ifdef CONFIG_IP_ROUTE_CLASSID
  412. nla = nla_find(attrs, attrlen, RTA_FLOW);
  413. nexthop_nh->nh_tclassid = nla ? nla_get_u32(nla) : 0;
  414. if (nexthop_nh->nh_tclassid)
  415. fi->fib_net->ipv4.fib_num_tclassid_users++;
  416. #endif
  417. }
  418. rtnh = rtnh_next(rtnh, &remaining);
  419. } endfor_nexthops(fi);
  420. return 0;
  421. }
  422. #endif
  423. int fib_nh_match(struct fib_config *cfg, struct fib_info *fi)
  424. {
  425. #ifdef CONFIG_IP_ROUTE_MULTIPATH
  426. struct rtnexthop *rtnh;
  427. int remaining;
  428. #endif
  429. if (cfg->fc_priority && cfg->fc_priority != fi->fib_priority)
  430. return 1;
  431. if (cfg->fc_oif || cfg->fc_gw) {
  432. if ((!cfg->fc_oif || cfg->fc_oif == fi->fib_nh->nh_oif) &&
  433. (!cfg->fc_gw || cfg->fc_gw == fi->fib_nh->nh_gw))
  434. return 0;
  435. return 1;
  436. }
  437. #ifdef CONFIG_IP_ROUTE_MULTIPATH
  438. if (cfg->fc_mp == NULL)
  439. return 0;
  440. rtnh = cfg->fc_mp;
  441. remaining = cfg->fc_mp_len;
  442. for_nexthops(fi) {
  443. int attrlen;
  444. if (!rtnh_ok(rtnh, remaining))
  445. return -EINVAL;
  446. if (rtnh->rtnh_ifindex && rtnh->rtnh_ifindex != nh->nh_oif)
  447. return 1;
  448. attrlen = rtnh_attrlen(rtnh);
  449. if (attrlen < 0) {
  450. struct nlattr *nla, *attrs = rtnh_attrs(rtnh);
  451. nla = nla_find(attrs, attrlen, RTA_GATEWAY);
  452. if (nla && nla_get_be32(nla) != nh->nh_gw)
  453. return 1;
  454. #ifdef CONFIG_IP_ROUTE_CLASSID
  455. nla = nla_find(attrs, attrlen, RTA_FLOW);
  456. if (nla && nla_get_u32(nla) != nh->nh_tclassid)
  457. return 1;
  458. #endif
  459. }
  460. rtnh = rtnh_next(rtnh, &remaining);
  461. } endfor_nexthops(fi);
  462. #endif
  463. return 0;
  464. }
  465. /*
  466. * Picture
  467. * -------
  468. *
  469. * Semantics of nexthop is very messy by historical reasons.
  470. * We have to take into account, that:
  471. * a) gateway can be actually local interface address,
  472. * so that gatewayed route is direct.
  473. * b) gateway must be on-link address, possibly
  474. * described not by an ifaddr, but also by a direct route.
  475. * c) If both gateway and interface are specified, they should not
  476. * contradict.
  477. * d) If we use tunnel routes, gateway could be not on-link.
  478. *
  479. * Attempt to reconcile all of these (alas, self-contradictory) conditions
  480. * results in pretty ugly and hairy code with obscure logic.
  481. *
  482. * I chose to generalized it instead, so that the size
  483. * of code does not increase practically, but it becomes
  484. * much more general.
  485. * Every prefix is assigned a "scope" value: "host" is local address,
  486. * "link" is direct route,
  487. * [ ... "site" ... "interior" ... ]
  488. * and "universe" is true gateway route with global meaning.
  489. *
  490. * Every prefix refers to a set of "nexthop"s (gw, oif),
  491. * where gw must have narrower scope. This recursion stops
  492. * when gw has LOCAL scope or if "nexthop" is declared ONLINK,
  493. * which means that gw is forced to be on link.
  494. *
  495. * Code is still hairy, but now it is apparently logically
  496. * consistent and very flexible. F.e. as by-product it allows
  497. * to co-exists in peace independent exterior and interior
  498. * routing processes.
  499. *
  500. * Normally it looks as following.
  501. *
  502. * {universe prefix} -> (gw, oif) [scope link]
  503. * |
  504. * |-> {link prefix} -> (gw, oif) [scope local]
  505. * |
  506. * |-> {local prefix} (terminal node)
  507. */
  508. static int fib_check_nh(struct fib_config *cfg, struct fib_info *fi,
  509. struct fib_nh *nh)
  510. {
  511. int err;
  512. struct net *net;
  513. struct net_device *dev;
  514. net = cfg->fc_nlinfo.nl_net;
  515. if (nh->nh_gw) {
  516. struct fib_result res;
  517. if (nh->nh_flags & RTNH_F_ONLINK) {
  518. if (cfg->fc_scope >= RT_SCOPE_LINK)
  519. return -EINVAL;
  520. if (inet_addr_type(net, nh->nh_gw) != RTN_UNICAST)
  521. return -EINVAL;
  522. dev = __dev_get_by_index(net, nh->nh_oif);
  523. if (!dev)
  524. return -ENODEV;
  525. if (!(dev->flags & IFF_UP))
  526. return -ENETDOWN;
  527. nh->nh_dev = dev;
  528. dev_hold(dev);
  529. nh->nh_scope = RT_SCOPE_LINK;
  530. return 0;
  531. }
  532. rcu_read_lock();
  533. {
  534. struct flowi4 fl4 = {
  535. .daddr = nh->nh_gw,
  536. .flowi4_scope = cfg->fc_scope + 1,
  537. .flowi4_oif = nh->nh_oif,
  538. };
  539. /* It is not necessary, but requires a bit of thinking */
  540. if (fl4.flowi4_scope < RT_SCOPE_LINK)
  541. fl4.flowi4_scope = RT_SCOPE_LINK;
  542. err = fib_lookup(net, &fl4, &res);
  543. if (err) {
  544. rcu_read_unlock();
  545. return err;
  546. }
  547. }
  548. err = -EINVAL;
  549. if (res.type != RTN_UNICAST && res.type != RTN_LOCAL)
  550. goto out;
  551. nh->nh_scope = res.scope;
  552. nh->nh_oif = FIB_RES_OIF(res);
  553. nh->nh_dev = dev = FIB_RES_DEV(res);
  554. if (!dev)
  555. goto out;
  556. dev_hold(dev);
  557. err = (dev->flags & IFF_UP) ? 0 : -ENETDOWN;
  558. } else {
  559. struct in_device *in_dev;
  560. if (nh->nh_flags & (RTNH_F_PERVASIVE | RTNH_F_ONLINK))
  561. return -EINVAL;
  562. rcu_read_lock();
  563. err = -ENODEV;
  564. in_dev = inetdev_by_index(net, nh->nh_oif);
  565. if (in_dev == NULL)
  566. goto out;
  567. err = -ENETDOWN;
  568. if (!(in_dev->dev->flags & IFF_UP))
  569. goto out;
  570. nh->nh_dev = in_dev->dev;
  571. dev_hold(nh->nh_dev);
  572. nh->nh_scope = RT_SCOPE_HOST;
  573. err = 0;
  574. }
  575. out:
  576. rcu_read_unlock();
  577. return err;
  578. }
  579. static inline unsigned int fib_laddr_hashfn(__be32 val)
  580. {
  581. unsigned int mask = (fib_info_hash_size - 1);
  582. return ((__force u32)val ^
  583. ((__force u32)val >> 7) ^
  584. ((__force u32)val >> 14)) & mask;
  585. }
  586. static struct hlist_head *fib_info_hash_alloc(int bytes)
  587. {
  588. if (bytes <= PAGE_SIZE)
  589. return kzalloc(bytes, GFP_KERNEL);
  590. else
  591. return (struct hlist_head *)
  592. __get_free_pages(GFP_KERNEL | __GFP_ZERO,
  593. get_order(bytes));
  594. }
  595. static void fib_info_hash_free(struct hlist_head *hash, int bytes)
  596. {
  597. if (!hash)
  598. return;
  599. if (bytes <= PAGE_SIZE)
  600. kfree(hash);
  601. else
  602. free_pages((unsigned long) hash, get_order(bytes));
  603. }
  604. static void fib_info_hash_move(struct hlist_head *new_info_hash,
  605. struct hlist_head *new_laddrhash,
  606. unsigned int new_size)
  607. {
  608. struct hlist_head *old_info_hash, *old_laddrhash;
  609. unsigned int old_size = fib_info_hash_size;
  610. unsigned int i, bytes;
  611. spin_lock_bh(&fib_info_lock);
  612. old_info_hash = fib_info_hash;
  613. old_laddrhash = fib_info_laddrhash;
  614. fib_info_hash_size = new_size;
  615. for (i = 0; i < old_size; i++) {
  616. struct hlist_head *head = &fib_info_hash[i];
  617. struct hlist_node *node, *n;
  618. struct fib_info *fi;
  619. hlist_for_each_entry_safe(fi, node, n, head, fib_hash) {
  620. struct hlist_head *dest;
  621. unsigned int new_hash;
  622. hlist_del(&fi->fib_hash);
  623. new_hash = fib_info_hashfn(fi);
  624. dest = &new_info_hash[new_hash];
  625. hlist_add_head(&fi->fib_hash, dest);
  626. }
  627. }
  628. fib_info_hash = new_info_hash;
  629. for (i = 0; i < old_size; i++) {
  630. struct hlist_head *lhead = &fib_info_laddrhash[i];
  631. struct hlist_node *node, *n;
  632. struct fib_info *fi;
  633. hlist_for_each_entry_safe(fi, node, n, lhead, fib_lhash) {
  634. struct hlist_head *ldest;
  635. unsigned int new_hash;
  636. hlist_del(&fi->fib_lhash);
  637. new_hash = fib_laddr_hashfn(fi->fib_prefsrc);
  638. ldest = &new_laddrhash[new_hash];
  639. hlist_add_head(&fi->fib_lhash, ldest);
  640. }
  641. }
  642. fib_info_laddrhash = new_laddrhash;
  643. spin_unlock_bh(&fib_info_lock);
  644. bytes = old_size * sizeof(struct hlist_head *);
  645. fib_info_hash_free(old_info_hash, bytes);
  646. fib_info_hash_free(old_laddrhash, bytes);
  647. }
  648. __be32 fib_info_update_nh_saddr(struct net *net, struct fib_nh *nh)
  649. {
  650. nh->nh_saddr = inet_select_addr(nh->nh_dev,
  651. nh->nh_gw,
  652. nh->nh_parent->fib_scope);
  653. nh->nh_saddr_genid = atomic_read(&net->ipv4.dev_addr_genid);
  654. return nh->nh_saddr;
  655. }
  656. struct fib_info *fib_create_info(struct fib_config *cfg)
  657. {
  658. int err;
  659. struct fib_info *fi = NULL;
  660. struct fib_info *ofi;
  661. int nhs = 1;
  662. struct net *net = cfg->fc_nlinfo.nl_net;
  663. if (cfg->fc_type > RTN_MAX)
  664. goto err_inval;
  665. /* Fast check to catch the most weird cases */
  666. if (fib_props[cfg->fc_type].scope > cfg->fc_scope)
  667. goto err_inval;
  668. #ifdef CONFIG_IP_ROUTE_MULTIPATH
  669. if (cfg->fc_mp) {
  670. nhs = fib_count_nexthops(cfg->fc_mp, cfg->fc_mp_len);
  671. if (nhs == 0)
  672. goto err_inval;
  673. }
  674. #endif
  675. err = -ENOBUFS;
  676. if (fib_info_cnt >= fib_info_hash_size) {
  677. unsigned int new_size = fib_info_hash_size << 1;
  678. struct hlist_head *new_info_hash;
  679. struct hlist_head *new_laddrhash;
  680. unsigned int bytes;
  681. if (!new_size)
  682. new_size = 1;
  683. bytes = new_size * sizeof(struct hlist_head *);
  684. new_info_hash = fib_info_hash_alloc(bytes);
  685. new_laddrhash = fib_info_hash_alloc(bytes);
  686. if (!new_info_hash || !new_laddrhash) {
  687. fib_info_hash_free(new_info_hash, bytes);
  688. fib_info_hash_free(new_laddrhash, bytes);
  689. } else
  690. fib_info_hash_move(new_info_hash, new_laddrhash, new_size);
  691. if (!fib_info_hash_size)
  692. goto failure;
  693. }
  694. fi = kzalloc(sizeof(*fi)+nhs*sizeof(struct fib_nh), GFP_KERNEL);
  695. if (fi == NULL)
  696. goto failure;
  697. if (cfg->fc_mx) {
  698. fi->fib_metrics = kzalloc(sizeof(u32) * RTAX_MAX, GFP_KERNEL);
  699. if (!fi->fib_metrics)
  700. goto failure;
  701. } else
  702. fi->fib_metrics = (u32 *) dst_default_metrics;
  703. fib_info_cnt++;
  704. fi->fib_net = hold_net(net);
  705. fi->fib_protocol = cfg->fc_protocol;
  706. fi->fib_scope = cfg->fc_scope;
  707. fi->fib_flags = cfg->fc_flags;
  708. fi->fib_priority = cfg->fc_priority;
  709. fi->fib_prefsrc = cfg->fc_prefsrc;
  710. fi->fib_nhs = nhs;
  711. change_nexthops(fi) {
  712. nexthop_nh->nh_parent = fi;
  713. nexthop_nh->nh_pcpu_rth_output = alloc_percpu(struct rtable __rcu *);
  714. } endfor_nexthops(fi)
  715. if (cfg->fc_mx) {
  716. struct nlattr *nla;
  717. int remaining;
  718. nla_for_each_attr(nla, cfg->fc_mx, cfg->fc_mx_len, remaining) {
  719. int type = nla_type(nla);
  720. if (type) {
  721. u32 val;
  722. if (type > RTAX_MAX)
  723. goto err_inval;
  724. val = nla_get_u32(nla);
  725. if (type == RTAX_ADVMSS && val > 65535 - 40)
  726. val = 65535 - 40;
  727. if (type == RTAX_MTU && val > 65535 - 15)
  728. val = 65535 - 15;
  729. fi->fib_metrics[type - 1] = val;
  730. }
  731. }
  732. }
  733. if (cfg->fc_mp) {
  734. #ifdef CONFIG_IP_ROUTE_MULTIPATH
  735. err = fib_get_nhs(fi, cfg->fc_mp, cfg->fc_mp_len, cfg);
  736. if (err != 0)
  737. goto failure;
  738. if (cfg->fc_oif && fi->fib_nh->nh_oif != cfg->fc_oif)
  739. goto err_inval;
  740. if (cfg->fc_gw && fi->fib_nh->nh_gw != cfg->fc_gw)
  741. goto err_inval;
  742. #ifdef CONFIG_IP_ROUTE_CLASSID
  743. if (cfg->fc_flow && fi->fib_nh->nh_tclassid != cfg->fc_flow)
  744. goto err_inval;
  745. #endif
  746. #else
  747. goto err_inval;
  748. #endif
  749. } else {
  750. struct fib_nh *nh = fi->fib_nh;
  751. nh->nh_oif = cfg->fc_oif;
  752. nh->nh_gw = cfg->fc_gw;
  753. nh->nh_flags = cfg->fc_flags;
  754. #ifdef CONFIG_IP_ROUTE_CLASSID
  755. nh->nh_tclassid = cfg->fc_flow;
  756. if (nh->nh_tclassid)
  757. fi->fib_net->ipv4.fib_num_tclassid_users++;
  758. #endif
  759. #ifdef CONFIG_IP_ROUTE_MULTIPATH
  760. nh->nh_weight = 1;
  761. #endif
  762. }
  763. if (fib_props[cfg->fc_type].error) {
  764. if (cfg->fc_gw || cfg->fc_oif || cfg->fc_mp)
  765. goto err_inval;
  766. goto link_it;
  767. } else {
  768. switch (cfg->fc_type) {
  769. case RTN_UNICAST:
  770. case RTN_LOCAL:
  771. case RTN_BROADCAST:
  772. case RTN_ANYCAST:
  773. case RTN_MULTICAST:
  774. break;
  775. default:
  776. goto err_inval;
  777. }
  778. }
  779. if (cfg->fc_scope > RT_SCOPE_HOST)
  780. goto err_inval;
  781. if (cfg->fc_scope == RT_SCOPE_HOST) {
  782. struct fib_nh *nh = fi->fib_nh;
  783. /* Local address is added. */
  784. if (nhs != 1 || nh->nh_gw)
  785. goto err_inval;
  786. nh->nh_scope = RT_SCOPE_NOWHERE;
  787. nh->nh_dev = dev_get_by_index(net, fi->fib_nh->nh_oif);
  788. err = -ENODEV;
  789. if (nh->nh_dev == NULL)
  790. goto failure;
  791. } else {
  792. change_nexthops(fi) {
  793. err = fib_check_nh(cfg, fi, nexthop_nh);
  794. if (err != 0)
  795. goto failure;
  796. } endfor_nexthops(fi)
  797. }
  798. if (fi->fib_prefsrc) {
  799. if (cfg->fc_type != RTN_LOCAL || !cfg->fc_dst ||
  800. fi->fib_prefsrc != cfg->fc_dst)
  801. if (inet_addr_type(net, fi->fib_prefsrc) != RTN_LOCAL)
  802. goto err_inval;
  803. }
  804. change_nexthops(fi) {
  805. fib_info_update_nh_saddr(net, nexthop_nh);
  806. } endfor_nexthops(fi)
  807. link_it:
  808. ofi = fib_find_info(fi);
  809. if (ofi) {
  810. fi->fib_dead = 1;
  811. free_fib_info(fi);
  812. ofi->fib_treeref++;
  813. return ofi;
  814. }
  815. fi->fib_treeref++;
  816. atomic_inc(&fi->fib_clntref);
  817. spin_lock_bh(&fib_info_lock);
  818. hlist_add_head(&fi->fib_hash,
  819. &fib_info_hash[fib_info_hashfn(fi)]);
  820. if (fi->fib_prefsrc) {
  821. struct hlist_head *head;
  822. head = &fib_info_laddrhash[fib_laddr_hashfn(fi->fib_prefsrc)];
  823. hlist_add_head(&fi->fib_lhash, head);
  824. }
  825. change_nexthops(fi) {
  826. struct hlist_head *head;
  827. unsigned int hash;
  828. if (!nexthop_nh->nh_dev)
  829. continue;
  830. hash = fib_devindex_hashfn(nexthop_nh->nh_dev->ifindex);
  831. head = &fib_info_devhash[hash];
  832. hlist_add_head(&nexthop_nh->nh_hash, head);
  833. } endfor_nexthops(fi)
  834. spin_unlock_bh(&fib_info_lock);
  835. return fi;
  836. err_inval:
  837. err = -EINVAL;
  838. failure:
  839. if (fi) {
  840. fi->fib_dead = 1;
  841. free_fib_info(fi);
  842. }
  843. return ERR_PTR(err);
  844. }
  845. int fib_dump_info(struct sk_buff *skb, u32 pid, u32 seq, int event,
  846. u32 tb_id, u8 type, __be32 dst, int dst_len, u8 tos,
  847. struct fib_info *fi, unsigned int flags)
  848. {
  849. struct nlmsghdr *nlh;
  850. struct rtmsg *rtm;
  851. nlh = nlmsg_put(skb, pid, seq, event, sizeof(*rtm), flags);
  852. if (nlh == NULL)
  853. return -EMSGSIZE;
  854. rtm = nlmsg_data(nlh);
  855. rtm->rtm_family = AF_INET;
  856. rtm->rtm_dst_len = dst_len;
  857. rtm->rtm_src_len = 0;
  858. rtm->rtm_tos = tos;
  859. if (tb_id < 256)
  860. rtm->rtm_table = tb_id;
  861. else
  862. rtm->rtm_table = RT_TABLE_COMPAT;
  863. if (nla_put_u32(skb, RTA_TABLE, tb_id))
  864. goto nla_put_failure;
  865. rtm->rtm_type = type;
  866. rtm->rtm_flags = fi->fib_flags;
  867. rtm->rtm_scope = fi->fib_scope;
  868. rtm->rtm_protocol = fi->fib_protocol;
  869. if (rtm->rtm_dst_len &&
  870. nla_put_be32(skb, RTA_DST, dst))
  871. goto nla_put_failure;
  872. if (fi->fib_priority &&
  873. nla_put_u32(skb, RTA_PRIORITY, fi->fib_priority))
  874. goto nla_put_failure;
  875. if (rtnetlink_put_metrics(skb, fi->fib_metrics) < 0)
  876. goto nla_put_failure;
  877. if (fi->fib_prefsrc &&
  878. nla_put_be32(skb, RTA_PREFSRC, fi->fib_prefsrc))
  879. goto nla_put_failure;
  880. if (fi->fib_nhs == 1) {
  881. if (fi->fib_nh->nh_gw &&
  882. nla_put_be32(skb, RTA_GATEWAY, fi->fib_nh->nh_gw))
  883. goto nla_put_failure;
  884. if (fi->fib_nh->nh_oif &&
  885. nla_put_u32(skb, RTA_OIF, fi->fib_nh->nh_oif))
  886. goto nla_put_failure;
  887. #ifdef CONFIG_IP_ROUTE_CLASSID
  888. if (fi->fib_nh[0].nh_tclassid &&
  889. nla_put_u32(skb, RTA_FLOW, fi->fib_nh[0].nh_tclassid))
  890. goto nla_put_failure;
  891. #endif
  892. }
  893. #ifdef CONFIG_IP_ROUTE_MULTIPATH
  894. if (fi->fib_nhs > 1) {
  895. struct rtnexthop *rtnh;
  896. struct nlattr *mp;
  897. mp = nla_nest_start(skb, RTA_MULTIPATH);
  898. if (mp == NULL)
  899. goto nla_put_failure;
  900. for_nexthops(fi) {
  901. rtnh = nla_reserve_nohdr(skb, sizeof(*rtnh));
  902. if (rtnh == NULL)
  903. goto nla_put_failure;
  904. rtnh->rtnh_flags = nh->nh_flags & 0xFF;
  905. rtnh->rtnh_hops = nh->nh_weight - 1;
  906. rtnh->rtnh_ifindex = nh->nh_oif;
  907. if (nh->nh_gw &&
  908. nla_put_be32(skb, RTA_GATEWAY, nh->nh_gw))
  909. goto nla_put_failure;
  910. #ifdef CONFIG_IP_ROUTE_CLASSID
  911. if (nh->nh_tclassid &&
  912. nla_put_u32(skb, RTA_FLOW, nh->nh_tclassid))
  913. goto nla_put_failure;
  914. #endif
  915. /* length of rtnetlink header + attributes */
  916. rtnh->rtnh_len = nlmsg_get_pos(skb) - (void *) rtnh;
  917. } endfor_nexthops(fi);
  918. nla_nest_end(skb, mp);
  919. }
  920. #endif
  921. return nlmsg_end(skb, nlh);
  922. nla_put_failure:
  923. nlmsg_cancel(skb, nlh);
  924. return -EMSGSIZE;
  925. }
  926. /*
  927. * Update FIB if:
  928. * - local address disappeared -> we must delete all the entries
  929. * referring to it.
  930. * - device went down -> we must shutdown all nexthops going via it.
  931. */
  932. int fib_sync_down_addr(struct net *net, __be32 local)
  933. {
  934. int ret = 0;
  935. unsigned int hash = fib_laddr_hashfn(local);
  936. struct hlist_head *head = &fib_info_laddrhash[hash];
  937. struct hlist_node *node;
  938. struct fib_info *fi;
  939. if (fib_info_laddrhash == NULL || local == 0)
  940. return 0;
  941. hlist_for_each_entry(fi, node, head, fib_lhash) {
  942. if (!net_eq(fi->fib_net, net))
  943. continue;
  944. if (fi->fib_prefsrc == local) {
  945. fi->fib_flags |= RTNH_F_DEAD;
  946. ret++;
  947. }
  948. }
  949. return ret;
  950. }
  951. int fib_sync_down_dev(struct net_device *dev, int force)
  952. {
  953. int ret = 0;
  954. int scope = RT_SCOPE_NOWHERE;
  955. struct fib_info *prev_fi = NULL;
  956. unsigned int hash = fib_devindex_hashfn(dev->ifindex);
  957. struct hlist_head *head = &fib_info_devhash[hash];
  958. struct hlist_node *node;
  959. struct fib_nh *nh;
  960. if (force)
  961. scope = -1;
  962. hlist_for_each_entry(nh, node, head, nh_hash) {
  963. struct fib_info *fi = nh->nh_parent;
  964. int dead;
  965. BUG_ON(!fi->fib_nhs);
  966. if (nh->nh_dev != dev || fi == prev_fi)
  967. continue;
  968. prev_fi = fi;
  969. dead = 0;
  970. change_nexthops(fi) {
  971. if (nexthop_nh->nh_flags & RTNH_F_DEAD)
  972. dead++;
  973. else if (nexthop_nh->nh_dev == dev &&
  974. nexthop_nh->nh_scope != scope) {
  975. nexthop_nh->nh_flags |= RTNH_F_DEAD;
  976. #ifdef CONFIG_IP_ROUTE_MULTIPATH
  977. spin_lock_bh(&fib_multipath_lock);
  978. fi->fib_power -= nexthop_nh->nh_power;
  979. nexthop_nh->nh_power = 0;
  980. spin_unlock_bh(&fib_multipath_lock);
  981. #endif
  982. dead++;
  983. }
  984. #ifdef CONFIG_IP_ROUTE_MULTIPATH
  985. if (force > 1 && nexthop_nh->nh_dev == dev) {
  986. dead = fi->fib_nhs;
  987. break;
  988. }
  989. #endif
  990. } endfor_nexthops(fi)
  991. if (dead == fi->fib_nhs) {
  992. fi->fib_flags |= RTNH_F_DEAD;
  993. ret++;
  994. }
  995. }
  996. return ret;
  997. }
  998. /* Must be invoked inside of an RCU protected region. */
  999. void fib_select_default(struct fib_result *res)
  1000. {
  1001. struct fib_info *fi = NULL, *last_resort = NULL;
  1002. struct list_head *fa_head = res->fa_head;
  1003. struct fib_table *tb = res->table;
  1004. int order = -1, last_idx = -1;
  1005. struct fib_alias *fa;
  1006. list_for_each_entry_rcu(fa, fa_head, fa_list) {
  1007. struct fib_info *next_fi = fa->fa_info;
  1008. if (next_fi->fib_scope != res->scope ||
  1009. fa->fa_type != RTN_UNICAST)
  1010. continue;
  1011. if (next_fi->fib_priority > res->fi->fib_priority)
  1012. break;
  1013. if (!next_fi->fib_nh[0].nh_gw ||
  1014. next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
  1015. continue;
  1016. fib_alias_accessed(fa);
  1017. if (fi == NULL) {
  1018. if (next_fi != res->fi)
  1019. break;
  1020. } else if (!fib_detect_death(fi, order, &last_resort,
  1021. &last_idx, tb->tb_default)) {
  1022. fib_result_assign(res, fi);
  1023. tb->tb_default = order;
  1024. goto out;
  1025. }
  1026. fi = next_fi;
  1027. order++;
  1028. }
  1029. if (order <= 0 || fi == NULL) {
  1030. tb->tb_default = -1;
  1031. goto out;
  1032. }
  1033. if (!fib_detect_death(fi, order, &last_resort, &last_idx,
  1034. tb->tb_default)) {
  1035. fib_result_assign(res, fi);
  1036. tb->tb_default = order;
  1037. goto out;
  1038. }
  1039. if (last_idx >= 0)
  1040. fib_result_assign(res, last_resort);
  1041. tb->tb_default = last_idx;
  1042. out:
  1043. return;
  1044. }
  1045. #ifdef CONFIG_IP_ROUTE_MULTIPATH
  1046. /*
  1047. * Dead device goes up. We wake up dead nexthops.
  1048. * It takes sense only on multipath routes.
  1049. */
  1050. int fib_sync_up(struct net_device *dev)
  1051. {
  1052. struct fib_info *prev_fi;
  1053. unsigned int hash;
  1054. struct hlist_head *head;
  1055. struct hlist_node *node;
  1056. struct fib_nh *nh;
  1057. int ret;
  1058. if (!(dev->flags & IFF_UP))
  1059. return 0;
  1060. prev_fi = NULL;
  1061. hash = fib_devindex_hashfn(dev->ifindex);
  1062. head = &fib_info_devhash[hash];
  1063. ret = 0;
  1064. hlist_for_each_entry(nh, node, head, nh_hash) {
  1065. struct fib_info *fi = nh->nh_parent;
  1066. int alive;
  1067. BUG_ON(!fi->fib_nhs);
  1068. if (nh->nh_dev != dev || fi == prev_fi)
  1069. continue;
  1070. prev_fi = fi;
  1071. alive = 0;
  1072. change_nexthops(fi) {
  1073. if (!(nexthop_nh->nh_flags & RTNH_F_DEAD)) {
  1074. alive++;
  1075. continue;
  1076. }
  1077. if (nexthop_nh->nh_dev == NULL ||
  1078. !(nexthop_nh->nh_dev->flags & IFF_UP))
  1079. continue;
  1080. if (nexthop_nh->nh_dev != dev ||
  1081. !__in_dev_get_rtnl(dev))
  1082. continue;
  1083. alive++;
  1084. spin_lock_bh(&fib_multipath_lock);
  1085. nexthop_nh->nh_power = 0;
  1086. nexthop_nh->nh_flags &= ~RTNH_F_DEAD;
  1087. spin_unlock_bh(&fib_multipath_lock);
  1088. } endfor_nexthops(fi)
  1089. if (alive > 0) {
  1090. fi->fib_flags &= ~RTNH_F_DEAD;
  1091. ret++;
  1092. }
  1093. }
  1094. return ret;
  1095. }
  1096. /*
  1097. * The algorithm is suboptimal, but it provides really
  1098. * fair weighted route distribution.
  1099. */
  1100. void fib_select_multipath(struct fib_result *res)
  1101. {
  1102. struct fib_info *fi = res->fi;
  1103. int w;
  1104. spin_lock_bh(&fib_multipath_lock);
  1105. if (fi->fib_power <= 0) {
  1106. int power = 0;
  1107. change_nexthops(fi) {
  1108. if (!(nexthop_nh->nh_flags & RTNH_F_DEAD)) {
  1109. power += nexthop_nh->nh_weight;
  1110. nexthop_nh->nh_power = nexthop_nh->nh_weight;
  1111. }
  1112. } endfor_nexthops(fi);
  1113. fi->fib_power = power;
  1114. if (power <= 0) {
  1115. spin_unlock_bh(&fib_multipath_lock);
  1116. /* Race condition: route has just become dead. */
  1117. res->nh_sel = 0;
  1118. return;
  1119. }
  1120. }
  1121. /* w should be random number [0..fi->fib_power-1],
  1122. * it is pretty bad approximation.
  1123. */
  1124. w = jiffies % fi->fib_power;
  1125. change_nexthops(fi) {
  1126. if (!(nexthop_nh->nh_flags & RTNH_F_DEAD) &&
  1127. nexthop_nh->nh_power) {
  1128. w -= nexthop_nh->nh_power;
  1129. if (w <= 0) {
  1130. nexthop_nh->nh_power--;
  1131. fi->fib_power--;
  1132. res->nh_sel = nhsel;
  1133. spin_unlock_bh(&fib_multipath_lock);
  1134. return;
  1135. }
  1136. }
  1137. } endfor_nexthops(fi);
  1138. /* Race condition: route has just become dead. */
  1139. res->nh_sel = 0;
  1140. spin_unlock_bh(&fib_multipath_lock);
  1141. }
  1142. #endif