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.
6 * DECnet Routing Forwarding Information Base (Routing Tables)
8 * Author: Steve Whitehouse <SteveW@ACM.org>
9 * Mostly copied from the IPv4 routing code
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>
33 #include <net/fib_rules.h>
35 #include <net/dn_route.h>
36 #include <net/dn_fib.h>
37 #include <net/dn_neigh.h>
38 #include <net/dn_dev.h>
42 struct dn_zone
*dz_next
;
43 struct dn_fib_node
**dz_hash
;
47 #define DZ_HASHMASK(dz) ((dz)->dz_hashmask)
50 #define DZ_MASK(dz) ((dz)->dz_mask)
55 struct dn_zone
*dh_zones
[17];
56 struct dn_zone
*dh_zone_list
;
59 #define dz_key_0(key) ((key).datum = 0)
60 #define dz_prefix(key,dz) ((key).datum)
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++)
65 #define endfor_nexthops(fi) }
67 #define DN_MAX_DIVISOR 1024
69 #define DN_S_ACCESSED 2
71 #define DN_FIB_SCAN(f, fp) \
72 for( ; ((f) = *(fp)) != NULL; (fp) = &(f)->fn_next)
74 #define DN_FIB_SCAN_KEY(f, fp, key) \
75 for( ; ((f) = *(fp)) != NULL && dn_key_eq((f)->fn_key, (key)); (fp) = &(f)->fn_next)
77 #define RT_TABLE_MIN 1
79 static DEFINE_RWLOCK(dn_fib_tables_lock
);
80 struct dn_fib_table
*dn_fib_tables
[RT_TABLE_MAX
+ 1];
82 static kmem_cache_t
*dn_hash_kmem __read_mostly
;
83 static int dn_fib_hash_zombies
;
85 static inline dn_fib_idx_t
dn_hash(dn_fib_key_t key
, struct dn_zone
*dz
)
87 u16 h
= dn_ntohs(key
.datum
)>>(16 - dz
->dz_order
);
91 return *(dn_fib_idx_t
*)&h
;
94 static inline dn_fib_key_t
dz_key(__le16 dst
, struct dn_zone
*dz
)
97 k
.datum
= dst
& DZ_MASK(dz
);
101 static inline struct dn_fib_node
**dn_chain_p(dn_fib_key_t key
, struct dn_zone
*dz
)
103 return &dz
->dz_hash
[dn_hash(key
, dz
).datum
];
106 static inline struct dn_fib_node
*dz_chain(dn_fib_key_t key
, struct dn_zone
*dz
)
108 return dz
->dz_hash
[dn_hash(key
, dz
).datum
];
111 static inline int dn_key_eq(dn_fib_key_t a
, dn_fib_key_t b
)
113 return a
.datum
== b
.datum
;
116 static inline int dn_key_leq(dn_fib_key_t a
, dn_fib_key_t b
)
118 return a
.datum
<= b
.datum
;
121 static inline void dn_rebuild_zone(struct dn_zone
*dz
,
122 struct dn_fib_node
**old_ht
,
126 struct dn_fib_node
*f
, **fp
, *next
;
128 for(i
= 0; i
< old_divisor
; i
++) {
129 for(f
= old_ht
[i
]; f
; f
= 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
)
141 static void dn_rehash_zone(struct dn_zone
*dz
)
143 struct dn_fib_node
**ht
, **old_ht
;
144 int old_divisor
, new_divisor
;
147 old_divisor
= dz
->dz_divisor
;
149 switch(old_divisor
) {
155 printk(KERN_DEBUG
"DECnet: dn_rehash_zone: BUG! %d\n", old_divisor
);
158 new_hashmask
= 0x3FF;
162 ht
= kcalloc(new_divisor
, sizeof(struct dn_fib_node
*), GFP_KERNEL
);
166 write_lock_bh(&dn_fib_tables_lock
);
167 old_ht
= dz
->dz_hash
;
169 dz
->dz_hashmask
= new_hashmask
;
170 dz
->dz_divisor
= new_divisor
;
171 dn_rebuild_zone(dz
, old_ht
, old_divisor
);
172 write_unlock_bh(&dn_fib_tables_lock
);
176 static void dn_free_node(struct dn_fib_node
*f
)
178 dn_fib_release_info(DN_FIB_INFO(f
));
179 kmem_cache_free(dn_hash_kmem
, f
);
183 static struct dn_zone
*dn_new_zone(struct dn_hash
*table
, int z
)
186 struct dn_zone
*dz
= kzalloc(sizeof(struct dn_zone
), GFP_KERNEL
);
192 dz
->dz_hashmask
= 0x0F;
198 dz
->dz_hash
= kcalloc(dz
->dz_divisor
, sizeof(struct dn_fib_node
*), GFP_KERNEL
);
205 dz
->dz_mask
= dnet_make_mask(z
);
207 for(i
= z
+ 1; i
<= 16; i
++)
208 if (table
->dh_zones
[i
])
211 write_lock_bh(&dn_fib_tables_lock
);
213 dz
->dz_next
= table
->dh_zone_list
;
214 table
->dh_zone_list
= dz
;
216 dz
->dz_next
= table
->dh_zones
[i
]->dz_next
;
217 table
->dh_zones
[i
]->dz_next
= dz
;
219 table
->dh_zones
[z
] = dz
;
220 write_unlock_bh(&dn_fib_tables_lock
);
225 static int dn_fib_nh_match(struct rtmsg
*r
, struct nlmsghdr
*nlh
, struct dn_kern_rta
*rta
, struct dn_fib_info
*fi
)
227 struct rtnexthop
*nhp
;
230 if (rta
->rta_priority
&& *rta
->rta_priority
!= fi
->fib_priority
)
233 if (rta
->rta_oif
|| rta
->rta_gw
) {
234 if ((!rta
->rta_oif
|| *rta
->rta_oif
== fi
->fib_nh
->nh_oif
) &&
235 (!rta
->rta_gw
|| memcmp(rta
->rta_gw
, &fi
->fib_nh
->nh_gw
, 2) == 0))
240 if (rta
->rta_mp
== NULL
)
243 nhp
= RTA_DATA(rta
->rta_mp
);
244 nhlen
= RTA_PAYLOAD(rta
->rta_mp
);
247 int attrlen
= nhlen
- sizeof(struct rtnexthop
);
250 if (attrlen
< 0 || (nhlen
-= nhp
->rtnh_len
) < 0)
252 if (nhp
->rtnh_ifindex
&& nhp
->rtnh_ifindex
!= nh
->nh_oif
)
255 gw
= dn_fib_get_attr16(RTNH_DATA(nhp
), attrlen
, RTA_GATEWAY
);
257 if (gw
&& gw
!= nh
->nh_gw
)
260 nhp
= RTNH_NEXT(nhp
);
261 } endfor_nexthops(fi
);
266 static int dn_fib_dump_info(struct sk_buff
*skb
, u32 pid
, u32 seq
, int event
,
267 u8 tb_id
, u8 type
, u8 scope
, void *dst
, int dst_len
,
268 struct dn_fib_info
*fi
, unsigned int flags
)
271 struct nlmsghdr
*nlh
;
272 unsigned char *b
= skb
->tail
;
274 nlh
= NLMSG_NEW(skb
, pid
, seq
, event
, sizeof(*rtm
), flags
);
275 rtm
= NLMSG_DATA(nlh
);
276 rtm
->rtm_family
= AF_DECnet
;
277 rtm
->rtm_dst_len
= dst_len
;
278 rtm
->rtm_src_len
= 0;
280 rtm
->rtm_table
= tb_id
;
281 rtm
->rtm_flags
= fi
->fib_flags
;
282 rtm
->rtm_scope
= scope
;
283 rtm
->rtm_type
= type
;
284 if (rtm
->rtm_dst_len
)
285 RTA_PUT(skb
, RTA_DST
, 2, dst
);
286 rtm
->rtm_protocol
= fi
->fib_protocol
;
287 if (fi
->fib_priority
)
288 RTA_PUT(skb
, RTA_PRIORITY
, 4, &fi
->fib_priority
);
289 if (rtnetlink_put_metrics(skb
, fi
->fib_metrics
) < 0)
291 if (fi
->fib_nhs
== 1) {
292 if (fi
->fib_nh
->nh_gw
)
293 RTA_PUT(skb
, RTA_GATEWAY
, 2, &fi
->fib_nh
->nh_gw
);
294 if (fi
->fib_nh
->nh_oif
)
295 RTA_PUT(skb
, RTA_OIF
, sizeof(int), &fi
->fib_nh
->nh_oif
);
297 if (fi
->fib_nhs
> 1) {
298 struct rtnexthop
*nhp
;
299 struct rtattr
*mp_head
;
300 if (skb_tailroom(skb
) <= RTA_SPACE(0))
302 mp_head
= (struct rtattr
*)skb_put(skb
, RTA_SPACE(0));
305 if (skb_tailroom(skb
) < RTA_ALIGN(RTA_ALIGN(sizeof(*nhp
)) + 4))
307 nhp
= (struct rtnexthop
*)skb_put(skb
, RTA_ALIGN(sizeof(*nhp
)));
308 nhp
->rtnh_flags
= nh
->nh_flags
& 0xFF;
309 nhp
->rtnh_hops
= nh
->nh_weight
- 1;
310 nhp
->rtnh_ifindex
= nh
->nh_oif
;
312 RTA_PUT(skb
, RTA_GATEWAY
, 2, &nh
->nh_gw
);
313 nhp
->rtnh_len
= skb
->tail
- (unsigned char *)nhp
;
314 } endfor_nexthops(fi
);
315 mp_head
->rta_type
= RTA_MULTIPATH
;
316 mp_head
->rta_len
= skb
->tail
- (u8
*)mp_head
;
319 nlh
->nlmsg_len
= skb
->tail
- b
;
325 skb_trim(skb
, b
- skb
->data
);
330 static void dn_rtmsg_fib(int event
, struct dn_fib_node
*f
, int z
, int tb_id
,
331 struct nlmsghdr
*nlh
, struct netlink_skb_parms
*req
)
334 u32 pid
= req
? req
->pid
: 0;
335 int size
= NLMSG_SPACE(sizeof(struct rtmsg
) + 256);
337 skb
= alloc_skb(size
, GFP_KERNEL
);
341 if (dn_fib_dump_info(skb
, pid
, nlh
->nlmsg_seq
, event
, tb_id
,
342 f
->fn_type
, f
->fn_scope
, &f
->fn_key
, z
,
343 DN_FIB_INFO(f
), 0) < 0) {
347 NETLINK_CB(skb
).dst_group
= RTNLGRP_DECnet_ROUTE
;
348 if (nlh
->nlmsg_flags
& NLM_F_ECHO
)
349 atomic_inc(&skb
->users
);
350 netlink_broadcast(rtnl
, skb
, pid
, RTNLGRP_DECnet_ROUTE
, GFP_KERNEL
);
351 if (nlh
->nlmsg_flags
& NLM_F_ECHO
)
352 netlink_unicast(rtnl
, skb
, pid
, MSG_DONTWAIT
);
355 static __inline__
int dn_hash_dump_bucket(struct sk_buff
*skb
,
356 struct netlink_callback
*cb
,
357 struct dn_fib_table
*tb
,
359 struct dn_fib_node
*f
)
364 for(i
= 0; f
; i
++, f
= f
->fn_next
) {
367 if (f
->fn_state
& DN_S_ZOMBIE
)
369 if (dn_fib_dump_info(skb
, NETLINK_CB(cb
->skb
).pid
,
373 (f
->fn_state
& DN_S_ZOMBIE
) ? 0 : f
->fn_type
,
374 f
->fn_scope
, &f
->fn_key
, dz
->dz_order
,
375 f
->fn_info
, NLM_F_MULTI
) < 0) {
384 static __inline__
int dn_hash_dump_zone(struct sk_buff
*skb
,
385 struct netlink_callback
*cb
,
386 struct dn_fib_table
*tb
,
392 for(h
= 0; h
< dz
->dz_divisor
; h
++) {
396 memset(&cb
->args
[3], 0, sizeof(cb
->args
) - 3*sizeof(cb
->args
[0]));
397 if (dz
->dz_hash
== NULL
|| dz
->dz_hash
[h
] == NULL
)
399 if (dn_hash_dump_bucket(skb
, cb
, tb
, dz
, dz
->dz_hash
[h
]) < 0) {
408 static int dn_fib_table_dump(struct dn_fib_table
*tb
, struct sk_buff
*skb
,
409 struct netlink_callback
*cb
)
413 struct dn_hash
*table
= (struct dn_hash
*)tb
->data
;
416 read_lock(&dn_fib_tables_lock
);
417 for(dz
= table
->dh_zone_list
, m
= 0; dz
; dz
= dz
->dz_next
, m
++) {
421 memset(&cb
->args
[2], 0, sizeof(cb
->args
) - 2*sizeof(cb
->args
[0]));
423 if (dn_hash_dump_zone(skb
, cb
, tb
, dz
) < 0) {
425 read_unlock(&dn_fib_tables_lock
);
429 read_unlock(&dn_fib_tables_lock
);
435 static 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
)
437 struct dn_hash
*table
= (struct dn_hash
*)tb
->data
;
438 struct dn_fib_node
*new_f
, *f
, **fp
, **del_fp
;
440 struct dn_fib_info
*fi
;
441 int z
= r
->rtm_dst_len
;
442 int type
= r
->rtm_type
;
449 dz
= table
->dh_zones
[z
];
450 if (!dz
&& !(dz
= dn_new_zone(table
, z
)))
456 memcpy(&dst
, rta
->rta_dst
, 2);
457 if (dst
& ~DZ_MASK(dz
))
459 key
= dz_key(dst
, dz
);
462 if ((fi
= dn_fib_create_info(r
, rta
, n
, &err
)) == NULL
)
465 if (dz
->dz_nent
> (dz
->dz_divisor
<< 2) &&
466 dz
->dz_divisor
> DN_MAX_DIVISOR
&&
467 (z
==16 || (1<<z
) > dz
->dz_divisor
))
470 fp
= dn_chain_p(key
, dz
);
473 if (dn_key_leq(key
, f
->fn_key
))
479 if (f
&& (f
->fn_state
& DN_S_ZOMBIE
) &&
480 dn_key_eq(f
->fn_key
, key
)) {
487 DN_FIB_SCAN_KEY(f
, fp
, key
) {
488 if (fi
->fib_priority
<= DN_FIB_INFO(f
)->fib_priority
)
492 if (f
&& dn_key_eq(f
->fn_key
, key
) &&
493 fi
->fib_priority
== DN_FIB_INFO(f
)->fib_priority
) {
494 struct dn_fib_node
**ins_fp
;
497 if (n
->nlmsg_flags
& NLM_F_EXCL
)
500 if (n
->nlmsg_flags
& NLM_F_REPLACE
) {
510 DN_FIB_SCAN_KEY(f
, fp
, key
) {
511 if (fi
->fib_priority
!= DN_FIB_INFO(f
)->fib_priority
)
513 if (f
->fn_type
== type
&& f
->fn_scope
== r
->rtm_scope
514 && DN_FIB_INFO(f
) == fi
)
518 if (!(n
->nlmsg_flags
& NLM_F_APPEND
)) {
526 if (!(n
->nlmsg_flags
& NLM_F_CREATE
))
531 new_f
= kmem_cache_alloc(dn_hash_kmem
, SLAB_KERNEL
);
535 memset(new_f
, 0, sizeof(struct dn_fib_node
));
538 new_f
->fn_type
= type
;
539 new_f
->fn_scope
= r
->rtm_scope
;
540 DN_FIB_INFO(new_f
) = fi
;
543 write_lock_bh(&dn_fib_tables_lock
);
545 write_unlock_bh(&dn_fib_tables_lock
);
550 write_lock_bh(&dn_fib_tables_lock
);
551 *del_fp
= f
->fn_next
;
552 write_unlock_bh(&dn_fib_tables_lock
);
554 if (!(f
->fn_state
& DN_S_ZOMBIE
))
555 dn_rtmsg_fib(RTM_DELROUTE
, f
, z
, tb
->n
, n
, req
);
556 if (f
->fn_state
& DN_S_ACCESSED
)
557 dn_rt_cache_flush(-1);
561 dn_rt_cache_flush(-1);
564 dn_rtmsg_fib(RTM_NEWROUTE
, new_f
, z
, tb
->n
, n
, req
);
568 dn_fib_release_info(fi
);
573 static 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
)
575 struct dn_hash
*table
= (struct dn_hash
*)tb
->data
;
576 struct dn_fib_node
**fp
, **del_fp
, *f
;
577 int z
= r
->rtm_dst_len
;
586 if ((dz
= table
->dh_zones
[z
]) == NULL
)
592 memcpy(&dst
, rta
->rta_dst
, 2);
593 if (dst
& ~DZ_MASK(dz
))
595 key
= dz_key(dst
, dz
);
598 fp
= dn_chain_p(key
, dz
);
601 if (dn_key_eq(f
->fn_key
, key
))
603 if (dn_key_leq(key
, f
->fn_key
))
609 DN_FIB_SCAN_KEY(f
, fp
, key
) {
610 struct dn_fib_info
*fi
= DN_FIB_INFO(f
);
612 if (f
->fn_state
& DN_S_ZOMBIE
)
617 if (del_fp
== NULL
&&
618 (!r
->rtm_type
|| f
->fn_type
== r
->rtm_type
) &&
619 (r
->rtm_scope
== RT_SCOPE_NOWHERE
|| f
->fn_scope
== r
->rtm_scope
) &&
621 fi
->fib_protocol
== r
->rtm_protocol
) &&
622 dn_fib_nh_match(r
, n
, rta
, fi
) == 0)
628 dn_rtmsg_fib(RTM_DELROUTE
, f
, z
, tb
->n
, n
, req
);
631 write_lock_bh(&dn_fib_tables_lock
);
632 *del_fp
= f
->fn_next
;
633 write_unlock_bh(&dn_fib_tables_lock
);
635 if (f
->fn_state
& DN_S_ACCESSED
)
636 dn_rt_cache_flush(-1);
640 f
->fn_state
|= DN_S_ZOMBIE
;
641 if (f
->fn_state
& DN_S_ACCESSED
) {
642 f
->fn_state
&= ~DN_S_ACCESSED
;
643 dn_rt_cache_flush(-1);
645 if (++dn_fib_hash_zombies
> 128)
655 static inline int dn_flush_list(struct dn_fib_node
**fp
, int z
, struct dn_hash
*table
)
658 struct dn_fib_node
*f
;
660 while((f
= *fp
) != NULL
) {
661 struct dn_fib_info
*fi
= DN_FIB_INFO(f
);
663 if (fi
&& ((f
->fn_state
& DN_S_ZOMBIE
) || (fi
->fib_flags
& RTNH_F_DEAD
))) {
664 write_lock_bh(&dn_fib_tables_lock
);
666 write_unlock_bh(&dn_fib_tables_lock
);
678 static int dn_fib_table_flush(struct dn_fib_table
*tb
)
680 struct dn_hash
*table
= (struct dn_hash
*)tb
->data
;
684 dn_fib_hash_zombies
= 0;
685 for(dz
= table
->dh_zone_list
; dz
; dz
= dz
->dz_next
) {
688 for(i
= dz
->dz_divisor
-1; i
>= 0; i
--)
689 tmp
+= dn_flush_list(&dz
->dz_hash
[i
], dz
->dz_order
, table
);
697 static int dn_fib_table_lookup(struct dn_fib_table
*tb
, const struct flowi
*flp
, struct dn_fib_res
*res
)
701 struct dn_hash
*t
= (struct dn_hash
*)tb
->data
;
703 read_lock(&dn_fib_tables_lock
);
704 for(dz
= t
->dh_zone_list
; dz
; dz
= dz
->dz_next
) {
705 struct dn_fib_node
*f
;
706 dn_fib_key_t k
= dz_key(flp
->fld_dst
, dz
);
708 for(f
= dz_chain(k
, dz
); f
; f
= f
->fn_next
) {
709 if (!dn_key_eq(k
, f
->fn_key
)) {
710 if (dn_key_leq(k
, f
->fn_key
))
716 f
->fn_state
|= DN_S_ACCESSED
;
718 if (f
->fn_state
&DN_S_ZOMBIE
)
721 if (f
->fn_scope
< flp
->fld_scope
)
724 err
= dn_fib_semantic_match(f
->fn_type
, DN_FIB_INFO(f
), flp
, res
);
727 res
->type
= f
->fn_type
;
728 res
->scope
= f
->fn_scope
;
729 res
->prefixlen
= dz
->dz_order
;
738 read_unlock(&dn_fib_tables_lock
);
743 struct dn_fib_table
*dn_fib_get_table(int n
, int create
)
745 struct dn_fib_table
*t
;
747 if (n
< RT_TABLE_MIN
)
750 if (n
> RT_TABLE_MAX
)
753 if (dn_fib_tables
[n
])
754 return dn_fib_tables
[n
];
759 if (in_interrupt() && net_ratelimit()) {
760 printk(KERN_DEBUG
"DECnet: BUG! Attempt to create routing table from interrupt\n");
763 if ((t
= kmalloc(sizeof(struct dn_fib_table
) + sizeof(struct dn_hash
), GFP_KERNEL
)) == NULL
)
766 memset(t
, 0, sizeof(struct dn_fib_table
));
769 t
->insert
= dn_fib_table_insert
;
770 t
->delete = dn_fib_table_delete
;
771 t
->lookup
= dn_fib_table_lookup
;
772 t
->flush
= dn_fib_table_flush
;
773 t
->dump
= dn_fib_table_dump
;
774 memset(t
->data
, 0, sizeof(struct dn_hash
));
775 dn_fib_tables
[n
] = t
;
780 static void dn_fib_del_tree(int n
)
782 struct dn_fib_table
*t
;
784 write_lock(&dn_fib_tables_lock
);
785 t
= dn_fib_tables
[n
];
786 dn_fib_tables
[n
] = NULL
;
787 write_unlock(&dn_fib_tables_lock
);
792 struct dn_fib_table
*dn_fib_empty_table(void)
796 for(id
= RT_TABLE_MIN
; id
<= RT_TABLE_MAX
; id
++)
797 if (dn_fib_tables
[id
] == NULL
)
798 return dn_fib_get_table(id
, 1);
802 void __init
dn_fib_table_init(void)
804 dn_hash_kmem
= kmem_cache_create("dn_fib_info_cache",
805 sizeof(struct dn_fib_info
),
806 0, SLAB_HWCACHE_ALIGN
,
810 void __exit
dn_fib_table_cleanup(void)
814 for (i
= RT_TABLE_MIN
; i
<= RT_TABLE_MAX
; ++i
)