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