Kernel

Kernel Git Source Tree

Root/net/decnet/dn_table.c

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 <linux/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
42	struct 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
55	struct 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
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) \
73	for( ; ((f) = *(fp)) != NULL; (fp) = &(f)->fn_next)
74
75	#define DN_FIB_SCAN_KEY(f, fp, key) \
76	for( ; ((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
80	static struct hlist_head dn_fib_table_hash[DN_FIB_TABLE_HASHSZ];
81	static DEFINE_RWLOCK(dn_fib_tables_lock);
82
83	static struct kmem_cache *dn_hash_kmem __read_mostly;
84	static int dn_fib_hash_zombies;
85
86	static inline dn_fib_idx_t dn_hash(dn_fib_key_t key, struct dn_zone *dz)
87	{
88	u16 h = le16_to_cpu(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
95	static 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
102	static 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
107	static 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
112	static inline int dn_key_eq(dn_fib_key_t a, dn_fib_key_t b)
113	{
114	return a.datum == b.datum;
115	}
116
117	static inline int dn_key_leq(dn_fib_key_t a, dn_fib_key_t b)
118	{
119	return a.datum <= b.datum;
120	}
121
122	static inline void dn_rebuild_zone(struct dn_zone *dz,
123	struct dn_fib_node **old_ht,
124	int old_divisor)
125	{
126	struct dn_fib_node f, fp, next;
127	int i;
128
129	for(i = 0; i < old_divisor; i++) {
130	for(f = old_ht[i]; f; f = 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
142	static 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",
157	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
178	static 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
185	static 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
227	static 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
268	static 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
294	static 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
352	nlmsg_failure:
353	rtattr_failure:
354	nlmsg_trim(skb, b);
355	return -EMSGSIZE;
356	}
357
358
359	static 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;
381	errout:
382	if (err < 0)
383	rtnl_set_sk_err(&init_net, RTNLGRP_DECnet_ROUTE, err);
384	}
385
386	static __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
415	static __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
439	static 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
466	int 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;
496	next:
497	e++;
498	}
499	}
500	out:
501	cb->args[1] = e;
502	cb->args[0] = h;
503
504	return skb->len;
505	}
506
507	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)
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
597	create:
598	err = -ENOENT;
599	if (!(n->nlmsg_flags & NLM_F_CREATE))
600	goto out;
601
602	replace:
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;
638	out:
639	dn_fib_release_info(fi);
640	return err;
641	}
642
643
644	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)
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
726	static 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
749	static 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
768	static int dn_fib_table_lookup(struct dn_fib_table tb, const struct flowidn 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->daddr, 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->flowidn_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;
808	out:
809	read_unlock(&dn_fib_tables_lock);
810	return err;
811	}
812
813
814	struct 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
860	struct 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
870	void 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
886	void __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
894	void __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

Download this file

Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master

Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9

Kernel

Kernel Git Source Tree

Root/net/decnet/dn_table.c

interactive