1/* 2 * DECnet An implementation of the DECnet protocol suite for the LINUX 3 * operating system. DECnet is implemented using the BSD Socket 4 * interface as the means of communication with the user level. 5 * 6 * DECnet Routing Forwarding Information Base (Routing Tables) 7 * 8 * Author: Steve Whitehouse <SteveW@ACM.org> 9 * Mostly copied from the IPv4 routing code 10 * 11 * 12 * Changes: 13 * 14 */ 15#include <linux/string.h> 16#include <linux/net.h> 17#include <linux/socket.h> 18#include <linux/slab.h> 19#include <linux/sockios.h> 20#include <linux/init.h> 21#include <linux/skbuff.h> 22#include <linux/rtnetlink.h> 23#include <linux/proc_fs.h> 24#include <linux/netdevice.h> 25#include <linux/timer.h> 26#include <linux/spinlock.h> 27#include <linux/atomic.h> 28#include <asm/uaccess.h> 29#include <linux/route.h> /* RTF_xxx */ 30#include <net/neighbour.h> 31#include <net/netlink.h> 32#include <net/dst.h> 33#include <net/flow.h> 34#include <net/fib_rules.h> 35#include <net/dn.h> 36#include <net/dn_route.h> 37#include <net/dn_fib.h> 38#include <net/dn_neigh.h> 39#include <net/dn_dev.h> 40 41struct dn_zone 42{ 43 struct dn_zone *dz_next; 44 struct dn_fib_node **dz_hash; 45 int dz_nent; 46 int dz_divisor; 47 u32 dz_hashmask; 48#define DZ_HASHMASK(dz) ((dz)->dz_hashmask) 49 int dz_order; 50 __le16 dz_mask; 51#define DZ_MASK(dz) ((dz)->dz_mask) 52}; 53 54struct dn_hash 55{ 56 struct dn_zone *dh_zones[17]; 57 struct dn_zone *dh_zone_list; 58}; 59 60#define dz_key_0(key) ((key).datum = 0) 61 62#define for_nexthops(fi) { int nhsel; const struct dn_fib_nh *nh;\ 63 for(nhsel = 0, nh = (fi)->fib_nh; nhsel < (fi)->fib_nhs; nh++, nhsel++) 64 65#define endfor_nexthops(fi) } 66 67#define DN_MAX_DIVISOR 1024 68#define DN_S_ZOMBIE 1 69#define DN_S_ACCESSED 2 70 71#define DN_FIB_SCAN(f, fp) \ 72for( ; ((f) = *(fp)) != NULL; (fp) = &(f)->fn_next) 73 74#define DN_FIB_SCAN_KEY(f, fp, key) \ 75for( ; ((f) = *(fp)) != NULL && dn_key_eq((f)->fn_key, (key)); (fp) = &(f)->fn_next) 76 77#define RT_TABLE_MIN 1 78#define DN_FIB_TABLE_HASHSZ 256 79static struct hlist_head dn_fib_table_hash[DN_FIB_TABLE_HASHSZ]; 80static DEFINE_RWLOCK(dn_fib_tables_lock); 81 82static struct kmem_cache *dn_hash_kmem __read_mostly; 83static int dn_fib_hash_zombies; 84 85static inline dn_fib_idx_t dn_hash(dn_fib_key_t key, struct dn_zone *dz) 86{ 87 u16 h = le16_to_cpu(key.datum)>>(16 - dz->dz_order); 88 h ^= (h >> 10); 89 h ^= (h >> 6); 90 h &= DZ_HASHMASK(dz); 91 return *(dn_fib_idx_t *)&h; 92} 93 94static inline dn_fib_key_t dz_key(__le16 dst, struct dn_zone *dz) 95{ 96 dn_fib_key_t k; 97 k.datum = dst & DZ_MASK(dz); 98 return k; 99} 100 101static inline struct dn_fib_node **dn_chain_p(dn_fib_key_t key, struct dn_zone *dz) 102{ 103 return &dz->dz_hash[dn_hash(key, dz).datum]; 104} 105 106static inline struct dn_fib_node *dz_chain(dn_fib_key_t key, struct dn_zone *dz) 107{ 108 return dz->dz_hash[dn_hash(key, dz).datum]; 109} 110 111static inline int dn_key_eq(dn_fib_key_t a, dn_fib_key_t b) 112{ 113 return a.datum == b.datum; 114} 115 116static inline int dn_key_leq(dn_fib_key_t a, dn_fib_key_t b) 117{ 118 return a.datum <= b.datum; 119} 120 121static inline void dn_rebuild_zone(struct dn_zone *dz, 122 struct dn_fib_node **old_ht, 123 int old_divisor) 124{ 125 struct dn_fib_node *f, **fp, *next; 126 int i; 127 128 for(i = 0; i < old_divisor; i++) { 129 for(f = old_ht[i]; f; f = next) { 130 next = f->fn_next; 131 for(fp = dn_chain_p(f->fn_key, dz); 132 *fp && dn_key_leq((*fp)->fn_key, f->fn_key); 133 fp = &(*fp)->fn_next) 134 /* NOTHING */; 135 f->fn_next = *fp; 136 *fp = f; 137 } 138 } 139} 140 141static void dn_rehash_zone(struct dn_zone *dz) 142{ 143 struct dn_fib_node **ht, **old_ht; 144 int old_divisor, new_divisor; 145 u32 new_hashmask; 146 147 old_divisor = dz->dz_divisor; 148 149 switch (old_divisor) { 150 case 16: 151 new_divisor = 256; 152 new_hashmask = 0xFF; 153 break; 154 default: 155 printk(KERN_DEBUG "DECnet: dn_rehash_zone: BUG! %d\n", 156 old_divisor); 157 case 256: 158 new_divisor = 1024; 159 new_hashmask = 0x3FF; 160 break; 161 } 162 163 ht = kcalloc(new_divisor, sizeof(struct dn_fib_node*), GFP_KERNEL); 164 if (ht == NULL) 165 return; 166 167 write_lock_bh(&dn_fib_tables_lock); 168 old_ht = dz->dz_hash; 169 dz->dz_hash = ht; 170 dz->dz_hashmask = new_hashmask; 171 dz->dz_divisor = new_divisor; 172 dn_rebuild_zone(dz, old_ht, old_divisor); 173 write_unlock_bh(&dn_fib_tables_lock); 174 kfree(old_ht); 175} 176 177static void dn_free_node(struct dn_fib_node *f) 178{ 179 dn_fib_release_info(DN_FIB_INFO(f)); 180 kmem_cache_free(dn_hash_kmem, f); 181} 182 183 184static struct dn_zone *dn_new_zone(struct dn_hash *table, int z) 185{ 186 int i; 187 struct dn_zone *dz = kzalloc(sizeof(struct dn_zone), GFP_KERNEL); 188 if (!dz) 189 return NULL; 190 191 if (z) { 192 dz->dz_divisor = 16; 193 dz->dz_hashmask = 0x0F; 194 } else { 195 dz->dz_divisor = 1; 196 dz->dz_hashmask = 0; 197 } 198 199 dz->dz_hash = kcalloc(dz->dz_divisor, sizeof(struct dn_fib_node *), GFP_KERNEL); 200 if (!dz->dz_hash) { 201 kfree(dz); 202 return NULL; 203 } 204 205 dz->dz_order = z; 206 dz->dz_mask = dnet_make_mask(z); 207 208 for(i = z + 1; i <= 16; i++) 209 if (table->dh_zones[i]) 210 break; 211 212 write_lock_bh(&dn_fib_tables_lock); 213 if (i>16) { 214 dz->dz_next = table->dh_zone_list; 215 table->dh_zone_list = dz; 216 } else { 217 dz->dz_next = table->dh_zones[i]->dz_next; 218 table->dh_zones[i]->dz_next = dz; 219 } 220 table->dh_zones[z] = dz; 221 write_unlock_bh(&dn_fib_tables_lock); 222 return dz; 223} 224 225 226static int dn_fib_nh_match(struct rtmsg *r, struct nlmsghdr *nlh, struct nlattr *attrs[], struct dn_fib_info *fi) 227{ 228 struct rtnexthop *nhp; 229 int nhlen; 230 231 if (attrs[RTA_PRIORITY] && 232 nla_get_u32(attrs[RTA_PRIORITY]) != fi->fib_priority) 233 return 1; 234 235 if (attrs[RTA_OIF] || attrs[RTA_GATEWAY]) { 236 if ((!attrs[RTA_OIF] || nla_get_u32(attrs[RTA_OIF]) == fi->fib_nh->nh_oif) && 237 (!attrs[RTA_GATEWAY] || nla_get_le16(attrs[RTA_GATEWAY]) != fi->fib_nh->nh_gw)) 238 return 0; 239 return 1; 240 } 241 242 if (!attrs[RTA_MULTIPATH]) 243 return 0; 244 245 nhp = nla_data(attrs[RTA_MULTIPATH]); 246 nhlen = nla_len(attrs[RTA_MULTIPATH]); 247 248 for_nexthops(fi) { 249 int attrlen = nhlen - sizeof(struct rtnexthop); 250 __le16 gw; 251 252 if (attrlen < 0 || (nhlen -= nhp->rtnh_len) < 0) 253 return -EINVAL; 254 if (nhp->rtnh_ifindex && nhp->rtnh_ifindex != nh->nh_oif) 255 return 1; 256 if (attrlen) { 257 struct nlattr *gw_attr; 258 259 gw_attr = nla_find((struct nlattr *) (nhp + 1), attrlen, RTA_GATEWAY); 260 gw = gw_attr ? nla_get_le16(gw_attr) : 0; 261 262 if (gw && gw != nh->nh_gw) 263 return 1; 264 } 265 nhp = RTNH_NEXT(nhp); 266 } endfor_nexthops(fi); 267 268 return 0; 269} 270 271static inline size_t dn_fib_nlmsg_size(struct dn_fib_info *fi) 272{ 273 size_t payload = NLMSG_ALIGN(sizeof(struct rtmsg)) 274 + nla_total_size(4) /* RTA_TABLE */ 275 + nla_total_size(2) /* RTA_DST */ 276 + nla_total_size(4); /* RTA_PRIORITY */ 277 278 /* space for nested metrics */ 279 payload += nla_total_size((RTAX_MAX * nla_total_size(4))); 280 281 if (fi->fib_nhs) { 282 /* Also handles the special case fib_nhs == 1 */ 283 284 /* each nexthop is packed in an attribute */ 285 size_t nhsize = nla_total_size(sizeof(struct rtnexthop)); 286 287 /* may contain a gateway attribute */ 288 nhsize += nla_total_size(4); 289 290 /* all nexthops are packed in a nested attribute */ 291 payload += nla_total_size(fi->fib_nhs * nhsize); 292 } 293 294 return payload; 295} 296 297static int dn_fib_dump_info(struct sk_buff *skb, u32 portid, u32 seq, int event, 298 u32 tb_id, u8 type, u8 scope, void *dst, int dst_len, 299 struct dn_fib_info *fi, unsigned int flags) 300{ 301 struct rtmsg *rtm; 302 struct nlmsghdr *nlh; 303 304 nlh = nlmsg_put(skb, portid, seq, event, sizeof(*rtm), flags); 305 if (!nlh) 306 return -EMSGSIZE; 307 308 rtm = nlmsg_data(nlh); 309 rtm->rtm_family = AF_DECnet; 310 rtm->rtm_dst_len = dst_len; 311 rtm->rtm_src_len = 0; 312 rtm->rtm_tos = 0; 313 rtm->rtm_table = tb_id; 314 rtm->rtm_flags = fi->fib_flags; 315 rtm->rtm_scope = scope; 316 rtm->rtm_type = type; 317 rtm->rtm_protocol = fi->fib_protocol; 318 319 if (nla_put_u32(skb, RTA_TABLE, tb_id) < 0) 320 goto errout; 321 322 if (rtm->rtm_dst_len && 323 nla_put(skb, RTA_DST, 2, dst) < 0) 324 goto errout; 325 326 if (fi->fib_priority && 327 nla_put_u32(skb, RTA_PRIORITY, fi->fib_priority) < 0) 328 goto errout; 329 330 if (rtnetlink_put_metrics(skb, fi->fib_metrics) < 0) 331 goto errout; 332 333 if (fi->fib_nhs == 1) { 334 if (fi->fib_nh->nh_gw && 335 nla_put_le16(skb, RTA_GATEWAY, fi->fib_nh->nh_gw) < 0) 336 goto errout; 337 338 if (fi->fib_nh->nh_oif && 339 nla_put_u32(skb, RTA_OIF, fi->fib_nh->nh_oif) < 0) 340 goto errout; 341 } 342 343 if (fi->fib_nhs > 1) { 344 struct rtnexthop *nhp; 345 struct nlattr *mp_head; 346 347 if (!(mp_head = nla_nest_start(skb, RTA_MULTIPATH))) 348 goto errout; 349 350 for_nexthops(fi) { 351 if (!(nhp = nla_reserve_nohdr(skb, sizeof(*nhp)))) 352 goto errout; 353 354 nhp->rtnh_flags = nh->nh_flags & 0xFF; 355 nhp->rtnh_hops = nh->nh_weight - 1; 356 nhp->rtnh_ifindex = nh->nh_oif; 357 358 if (nh->nh_gw && 359 nla_put_le16(skb, RTA_GATEWAY, nh->nh_gw) < 0) 360 goto errout; 361 362 nhp->rtnh_len = skb_tail_pointer(skb) - (unsigned char *)nhp; 363 } endfor_nexthops(fi); 364 365 nla_nest_end(skb, mp_head); 366 } 367 368 return nlmsg_end(skb, nlh); 369 370errout: 371 nlmsg_cancel(skb, nlh); 372 return -EMSGSIZE; 373} 374 375 376static void dn_rtmsg_fib(int event, struct dn_fib_node *f, int z, u32 tb_id, 377 struct nlmsghdr *nlh, struct netlink_skb_parms *req) 378{ 379 struct sk_buff *skb; 380 u32 portid = req ? req->portid : 0; 381 int err = -ENOBUFS; 382 383 skb = nlmsg_new(dn_fib_nlmsg_size(DN_FIB_INFO(f)), GFP_KERNEL); 384 if (skb == NULL) 385 goto errout; 386 387 err = dn_fib_dump_info(skb, portid, nlh->nlmsg_seq, event, tb_id, 388 f->fn_type, f->fn_scope, &f->fn_key, z, 389 DN_FIB_INFO(f), 0); 390 if (err < 0) { 391 /* -EMSGSIZE implies BUG in dn_fib_nlmsg_size() */ 392 WARN_ON(err == -EMSGSIZE); 393 kfree_skb(skb); 394 goto errout; 395 } 396 rtnl_notify(skb, &init_net, portid, RTNLGRP_DECnet_ROUTE, nlh, GFP_KERNEL); 397 return; 398errout: 399 if (err < 0) 400 rtnl_set_sk_err(&init_net, RTNLGRP_DECnet_ROUTE, err); 401} 402 403static __inline__ int dn_hash_dump_bucket(struct sk_buff *skb, 404 struct netlink_callback *cb, 405 struct dn_fib_table *tb, 406 struct dn_zone *dz, 407 struct dn_fib_node *f) 408{ 409 int i, s_i; 410 411 s_i = cb->args[4]; 412 for(i = 0; f; i++, f = f->fn_next) { 413 if (i < s_i) 414 continue; 415 if (f->fn_state & DN_S_ZOMBIE) 416 continue; 417 if (dn_fib_dump_info(skb, NETLINK_CB(cb->skb).portid, 418 cb->nlh->nlmsg_seq, 419 RTM_NEWROUTE, 420 tb->n, 421 (f->fn_state & DN_S_ZOMBIE) ? 0 : f->fn_type, 422 f->fn_scope, &f->fn_key, dz->dz_order, 423 f->fn_info, NLM_F_MULTI) < 0) { 424 cb->args[4] = i; 425 return -1; 426 } 427 } 428 cb->args[4] = i; 429 return skb->len; 430} 431 432static __inline__ int dn_hash_dump_zone(struct sk_buff *skb, 433 struct netlink_callback *cb, 434 struct dn_fib_table *tb, 435 struct dn_zone *dz) 436{ 437 int h, s_h; 438 439 s_h = cb->args[3]; 440 for(h = 0; h < dz->dz_divisor; h++) { 441 if (h < s_h) 442 continue; 443 if (h > s_h) 444 memset(&cb->args[4], 0, sizeof(cb->args) - 4*sizeof(cb->args[0])); 445 if (dz->dz_hash == NULL || dz->dz_hash[h] == NULL) 446 continue; 447 if (dn_hash_dump_bucket(skb, cb, tb, dz, dz->dz_hash[h]) < 0) { 448 cb->args[3] = h; 449 return -1; 450 } 451 } 452 cb->args[3] = h; 453 return skb->len; 454} 455 456static int dn_fib_table_dump(struct dn_fib_table *tb, struct sk_buff *skb, 457 struct netlink_callback *cb) 458{ 459 int m, s_m; 460 struct dn_zone *dz; 461 struct dn_hash *table = (struct dn_hash *)tb->data; 462 463 s_m = cb->args[2]; 464 read_lock(&dn_fib_tables_lock); 465 for(dz = table->dh_zone_list, m = 0; dz; dz = dz->dz_next, m++) { 466 if (m < s_m) 467 continue; 468 if (m > s_m) 469 memset(&cb->args[3], 0, sizeof(cb->args) - 3*sizeof(cb->args[0])); 470 471 if (dn_hash_dump_zone(skb, cb, tb, dz) < 0) { 472 cb->args[2] = m; 473 read_unlock(&dn_fib_tables_lock); 474 return -1; 475 } 476 } 477 read_unlock(&dn_fib_tables_lock); 478 cb->args[2] = m; 479 480 return skb->len; 481} 482 483int dn_fib_dump(struct sk_buff *skb, struct netlink_callback *cb) 484{ 485 struct net *net = sock_net(skb->sk); 486 unsigned int h, s_h; 487 unsigned int e = 0, s_e; 488 struct dn_fib_table *tb; 489 int dumped = 0; 490 491 if (!net_eq(net, &init_net)) 492 return 0; 493 494 if (nlmsg_len(cb->nlh) >= sizeof(struct rtmsg) && 495 ((struct rtmsg *)nlmsg_data(cb->nlh))->rtm_flags&RTM_F_CLONED) 496 return dn_cache_dump(skb, cb); 497 498 s_h = cb->args[0]; 499 s_e = cb->args[1]; 500 501 for (h = s_h; h < DN_FIB_TABLE_HASHSZ; h++, s_h = 0) { 502 e = 0; 503 hlist_for_each_entry(tb, &dn_fib_table_hash[h], hlist) { 504 if (e < s_e) 505 goto next; 506 if (dumped) 507 memset(&cb->args[2], 0, sizeof(cb->args) - 508 2 * sizeof(cb->args[0])); 509 if (tb->dump(tb, skb, cb) < 0) 510 goto out; 511 dumped = 1; 512next: 513 e++; 514 } 515 } 516out: 517 cb->args[1] = e; 518 cb->args[0] = h; 519 520 return skb->len; 521} 522 523static int dn_fib_table_insert(struct dn_fib_table *tb, struct rtmsg *r, struct nlattr *attrs[], 524 struct nlmsghdr *n, struct netlink_skb_parms *req) 525{ 526 struct dn_hash *table = (struct dn_hash *)tb->data; 527 struct dn_fib_node *new_f, *f, **fp, **del_fp; 528 struct dn_zone *dz; 529 struct dn_fib_info *fi; 530 int z = r->rtm_dst_len; 531 int type = r->rtm_type; 532 dn_fib_key_t key; 533 int err; 534 535 if (z > 16) 536 return -EINVAL; 537 538 dz = table->dh_zones[z]; 539 if (!dz && !(dz = dn_new_zone(table, z))) 540 return -ENOBUFS; 541 542 dz_key_0(key); 543 if (attrs[RTA_DST]) { 544 __le16 dst = nla_get_le16(attrs[RTA_DST]); 545 if (dst & ~DZ_MASK(dz)) 546 return -EINVAL; 547 key = dz_key(dst, dz); 548 } 549 550 if ((fi = dn_fib_create_info(r, attrs, n, &err)) == NULL) 551 return err; 552 553 if (dz->dz_nent > (dz->dz_divisor << 2) && 554 dz->dz_divisor > DN_MAX_DIVISOR && 555 (z==16 || (1<<z) > dz->dz_divisor)) 556 dn_rehash_zone(dz); 557 558 fp = dn_chain_p(key, dz); 559 560 DN_FIB_SCAN(f, fp) { 561 if (dn_key_leq(key, f->fn_key)) 562 break; 563 } 564 565 del_fp = NULL; 566 567 if (f && (f->fn_state & DN_S_ZOMBIE) && 568 dn_key_eq(f->fn_key, key)) { 569 del_fp = fp; 570 fp = &f->fn_next; 571 f = *fp; 572 goto create; 573 } 574 575 DN_FIB_SCAN_KEY(f, fp, key) { 576 if (fi->fib_priority <= DN_FIB_INFO(f)->fib_priority) 577 break; 578 } 579 580 if (f && dn_key_eq(f->fn_key, key) && 581 fi->fib_priority == DN_FIB_INFO(f)->fib_priority) { 582 struct dn_fib_node **ins_fp; 583 584 err = -EEXIST; 585 if (n->nlmsg_flags & NLM_F_EXCL) 586 goto out; 587 588 if (n->nlmsg_flags & NLM_F_REPLACE) { 589 del_fp = fp; 590 fp = &f->fn_next; 591 f = *fp; 592 goto replace; 593 } 594 595 ins_fp = fp; 596 err = -EEXIST; 597 598 DN_FIB_SCAN_KEY(f, fp, key) { 599 if (fi->fib_priority != DN_FIB_INFO(f)->fib_priority) 600 break; 601 if (f->fn_type == type && 602 f->fn_scope == r->rtm_scope && 603 DN_FIB_INFO(f) == fi) 604 goto out; 605 } 606 607 if (!(n->nlmsg_flags & NLM_F_APPEND)) { 608 fp = ins_fp; 609 f = *fp; 610 } 611 } 612 613create: 614 err = -ENOENT; 615 if (!(n->nlmsg_flags & NLM_F_CREATE)) 616 goto out; 617 618replace: 619 err = -ENOBUFS; 620 new_f = kmem_cache_zalloc(dn_hash_kmem, GFP_KERNEL); 621 if (new_f == NULL) 622 goto out; 623 624 new_f->fn_key = key; 625 new_f->fn_type = type; 626 new_f->fn_scope = r->rtm_scope; 627 DN_FIB_INFO(new_f) = fi; 628 629 new_f->fn_next = f; 630 write_lock_bh(&dn_fib_tables_lock); 631 *fp = new_f; 632 write_unlock_bh(&dn_fib_tables_lock); 633 dz->dz_nent++; 634 635 if (del_fp) { 636 f = *del_fp; 637 write_lock_bh(&dn_fib_tables_lock); 638 *del_fp = f->fn_next; 639 write_unlock_bh(&dn_fib_tables_lock); 640 641 if (!(f->fn_state & DN_S_ZOMBIE)) 642 dn_rtmsg_fib(RTM_DELROUTE, f, z, tb->n, n, req); 643 if (f->fn_state & DN_S_ACCESSED) 644 dn_rt_cache_flush(-1); 645 dn_free_node(f); 646 dz->dz_nent--; 647 } else { 648 dn_rt_cache_flush(-1); 649 } 650 651 dn_rtmsg_fib(RTM_NEWROUTE, new_f, z, tb->n, n, req); 652 653 return 0; 654out: 655 dn_fib_release_info(fi); 656 return err; 657} 658 659 660static int dn_fib_table_delete(struct dn_fib_table *tb, struct rtmsg *r, struct nlattr *attrs[], 661 struct nlmsghdr *n, struct netlink_skb_parms *req) 662{ 663 struct dn_hash *table = (struct dn_hash*)tb->data; 664 struct dn_fib_node **fp, **del_fp, *f; 665 int z = r->rtm_dst_len; 666 struct dn_zone *dz; 667 dn_fib_key_t key; 668 int matched; 669 670 671 if (z > 16) 672 return -EINVAL; 673 674 if ((dz = table->dh_zones[z]) == NULL) 675 return -ESRCH; 676 677 dz_key_0(key); 678 if (attrs[RTA_DST]) { 679 __le16 dst = nla_get_le16(attrs[RTA_DST]); 680 if (dst & ~DZ_MASK(dz)) 681 return -EINVAL; 682 key = dz_key(dst, dz); 683 } 684 685 fp = dn_chain_p(key, dz); 686 687 DN_FIB_SCAN(f, fp) { 688 if (dn_key_eq(f->fn_key, key)) 689 break; 690 if (dn_key_leq(key, f->fn_key)) 691 return -ESRCH; 692 } 693 694 matched = 0; 695 del_fp = NULL; 696 DN_FIB_SCAN_KEY(f, fp, key) { 697 struct dn_fib_info *fi = DN_FIB_INFO(f); 698 699 if (f->fn_state & DN_S_ZOMBIE) 700 return -ESRCH; 701 702 matched++; 703 704 if (del_fp == NULL && 705 (!r->rtm_type || f->fn_type == r->rtm_type) && 706 (r->rtm_scope == RT_SCOPE_NOWHERE || f->fn_scope == r->rtm_scope) && 707 (!r->rtm_protocol || 708 fi->fib_protocol == r->rtm_protocol) && 709 dn_fib_nh_match(r, n, attrs, fi) == 0) 710 del_fp = fp; 711 } 712 713 if (del_fp) { 714 f = *del_fp; 715 dn_rtmsg_fib(RTM_DELROUTE, f, z, tb->n, n, req); 716 717 if (matched != 1) { 718 write_lock_bh(&dn_fib_tables_lock); 719 *del_fp = f->fn_next; 720 write_unlock_bh(&dn_fib_tables_lock); 721 722 if (f->fn_state & DN_S_ACCESSED) 723 dn_rt_cache_flush(-1); 724 dn_free_node(f); 725 dz->dz_nent--; 726 } else { 727 f->fn_state |= DN_S_ZOMBIE; 728 if (f->fn_state & DN_S_ACCESSED) { 729 f->fn_state &= ~DN_S_ACCESSED; 730 dn_rt_cache_flush(-1); 731 } 732 if (++dn_fib_hash_zombies > 128) 733 dn_fib_flush(); 734 } 735 736 return 0; 737 } 738 739 return -ESRCH; 740} 741 742static inline int dn_flush_list(struct dn_fib_node **fp, int z, struct dn_hash *table) 743{ 744 int found = 0; 745 struct dn_fib_node *f; 746 747 while((f = *fp) != NULL) { 748 struct dn_fib_info *fi = DN_FIB_INFO(f); 749 750 if (fi && ((f->fn_state & DN_S_ZOMBIE) || (fi->fib_flags & RTNH_F_DEAD))) { 751 write_lock_bh(&dn_fib_tables_lock); 752 *fp = f->fn_next; 753 write_unlock_bh(&dn_fib_tables_lock); 754 755 dn_free_node(f); 756 found++; 757 continue; 758 } 759 fp = &f->fn_next; 760 } 761 762 return found; 763} 764 765static int dn_fib_table_flush(struct dn_fib_table *tb) 766{ 767 struct dn_hash *table = (struct dn_hash *)tb->data; 768 struct dn_zone *dz; 769 int found = 0; 770 771 dn_fib_hash_zombies = 0; 772 for(dz = table->dh_zone_list; dz; dz = dz->dz_next) { 773 int i; 774 int tmp = 0; 775 for(i = dz->dz_divisor-1; i >= 0; i--) 776 tmp += dn_flush_list(&dz->dz_hash[i], dz->dz_order, table); 777 dz->dz_nent -= tmp; 778 found += tmp; 779 } 780 781 return found; 782} 783 784static int dn_fib_table_lookup(struct dn_fib_table *tb, const struct flowidn *flp, struct dn_fib_res *res) 785{ 786 int err; 787 struct dn_zone *dz; 788 struct dn_hash *t = (struct dn_hash *)tb->data; 789 790 read_lock(&dn_fib_tables_lock); 791 for(dz = t->dh_zone_list; dz; dz = dz->dz_next) { 792 struct dn_fib_node *f; 793 dn_fib_key_t k = dz_key(flp->daddr, dz); 794 795 for(f = dz_chain(k, dz); f; f = f->fn_next) { 796 if (!dn_key_eq(k, f->fn_key)) { 797 if (dn_key_leq(k, f->fn_key)) 798 break; 799 else 800 continue; 801 } 802 803 f->fn_state |= DN_S_ACCESSED; 804 805 if (f->fn_state&DN_S_ZOMBIE) 806 continue; 807 808 if (f->fn_scope < flp->flowidn_scope) 809 continue; 810 811 err = dn_fib_semantic_match(f->fn_type, DN_FIB_INFO(f), flp, res); 812 813 if (err == 0) { 814 res->type = f->fn_type; 815 res->scope = f->fn_scope; 816 res->prefixlen = dz->dz_order; 817 goto out; 818 } 819 if (err < 0) 820 goto out; 821 } 822 } 823 err = 1; 824out: 825 read_unlock(&dn_fib_tables_lock); 826 return err; 827} 828 829 830struct dn_fib_table *dn_fib_get_table(u32 n, int create) 831{ 832 struct dn_fib_table *t; 833 unsigned int h; 834 835 if (n < RT_TABLE_MIN) 836 return NULL; 837 838 if (n > RT_TABLE_MAX) 839 return NULL; 840 841 h = n & (DN_FIB_TABLE_HASHSZ - 1); 842 rcu_read_lock(); 843 hlist_for_each_entry_rcu(t, &dn_fib_table_hash[h], hlist) { 844 if (t->n == n) { 845 rcu_read_unlock(); 846 return t; 847 } 848 } 849 rcu_read_unlock(); 850 851 if (!create) 852 return NULL; 853 854 if (in_interrupt()) { 855 net_dbg_ratelimited("DECnet: BUG! Attempt to create routing table from interrupt\n"); 856 return NULL; 857 } 858 859 t = kzalloc(sizeof(struct dn_fib_table) + sizeof(struct dn_hash), 860 GFP_KERNEL); 861 if (t == NULL) 862 return NULL; 863 864 t->n = n; 865 t->insert = dn_fib_table_insert; 866 t->delete = dn_fib_table_delete; 867 t->lookup = dn_fib_table_lookup; 868 t->flush = dn_fib_table_flush; 869 t->dump = dn_fib_table_dump; 870 hlist_add_head_rcu(&t->hlist, &dn_fib_table_hash[h]); 871 872 return t; 873} 874 875struct dn_fib_table *dn_fib_empty_table(void) 876{ 877 u32 id; 878 879 for(id = RT_TABLE_MIN; id <= RT_TABLE_MAX; id++) 880 if (dn_fib_get_table(id, 0) == NULL) 881 return dn_fib_get_table(id, 1); 882 return NULL; 883} 884 885void dn_fib_flush(void) 886{ 887 int flushed = 0; 888 struct dn_fib_table *tb; 889 unsigned int h; 890 891 for (h = 0; h < DN_FIB_TABLE_HASHSZ; h++) { 892 hlist_for_each_entry(tb, &dn_fib_table_hash[h], hlist) 893 flushed += tb->flush(tb); 894 } 895 896 if (flushed) 897 dn_rt_cache_flush(-1); 898} 899 900void __init dn_fib_table_init(void) 901{ 902 dn_hash_kmem = kmem_cache_create("dn_fib_info_cache", 903 sizeof(struct dn_fib_info), 904 0, SLAB_HWCACHE_ALIGN, 905 NULL); 906} 907 908void __exit dn_fib_table_cleanup(void) 909{ 910 struct dn_fib_table *t; 911 struct hlist_node *next; 912 unsigned int h; 913 914 write_lock(&dn_fib_tables_lock); 915 for (h = 0; h < DN_FIB_TABLE_HASHSZ; h++) { 916 hlist_for_each_entry_safe(t, next, &dn_fib_table_hash[h], 917 hlist) { 918 hlist_del(&t->hlist); 919 kfree(t); 920 } 921 } 922 write_unlock(&dn_fib_tables_lock); 923} 924