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