1 char radij_c_version[] = "RCSID $Id: radij.c,v 1.40 2002/01/29 17:17:58 mcr Exp $";
4 * This file is defived from ${SRC}/sys/net/radix.c of BSD 4.4lite
6 * Variable and procedure names have been modified so that they don't
7 * conflict with the original BSD code, as a small number of modifications
8 * have been introduced and we may want to reuse this code in BSD.
10 * The `j' in `radij' is pronounced as a voiceless guttural (like a Greek
11 * chi or a German ch sound (as `doch', not as in `milch'), or even a
12 * spanish j as in Juan. It is not as far back in the throat like
13 * the corresponding Hebrew sound, nor is it a soft breath like the English h.
14 * It has nothing to do with the Dutch ij sound.
16 * Here is the appropriate copyright notice:
20 * Copyright (c) 1988, 1989, 1993
21 * The Regents of the University of California. All rights reserved.
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions
26 * 1. Redistributions of source code must retain the above copyright
27 * notice, this list of conditions and the following disclaimer.
28 * 2. Redistributions in binary form must reproduce the above copyright
29 * notice, this list of conditions and the following disclaimer in the
30 * documentation and/or other materials provided with the distribution.
31 * 3. All advertising materials mentioning features or use of this software
32 * must display the following acknowledgement:
33 * This product includes software developed by the University of
34 * California, Berkeley and its contributors.
35 * 4. Neither the name of the University nor the names of its contributors
36 * may be used to endorse or promote products derived from this software
37 * without specific prior written permission.
39 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
40 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
41 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
42 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
43 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
44 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
45 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
46 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
47 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
48 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51 * @(#)radix.c 8.2 (Berkeley) 1/4/94
55 * Routines to build and maintain radix trees for routing lookups.
58 #include <linux/config.h>
59 #include <linux/version.h>
60 #include <linux/kernel.h> /* printk() */
62 #include "ipsec_param.h"
65 # include <linux/slab.h> /* kmalloc() */
66 #else /* MALLOC_SLAB */
67 # include <linux/malloc.h> /* kmalloc() */
68 #endif /* MALLOC_SLAB */
69 #include <linux/errno.h> /* error codes */
70 #include <linux/types.h> /* size_t */
71 #include <linux/interrupt.h> /* mark_bh */
73 #include <linux/netdevice.h> /* struct device, and other headers */
74 #include <linux/etherdevice.h> /* eth_type_trans */
75 #include <linux/ip.h> /* struct iphdr */
76 #include <linux/skbuff.h>
78 # include <asm/uaccess.h>
79 # include <linux/in6.h>
81 #include <asm/checksum.h>
87 #include "ipsec_encap.h"
88 #include "ipsec_radij.h"
89 #include "ipsec_netlink.h"
92 struct radij_mask *rj_mkfreelist;
93 struct radij_node_head *mask_rjhead;
94 static int gotOddMasks;
95 static char *maskedKey;
96 static char *rj_zeroes, *rj_ones;
98 #define rj_masktop (mask_rjhead->rnh_treetop)
102 #define Bcmp(a, b, l) (l == 0 ? 0 : memcmp((caddr_t)(b), (caddr_t)(a), (size_t)l))
104 * The data structure for the keys is a radix tree with one way
105 * branching removed. The index rj_b at an internal node n represents a bit
106 * position to be tested. The tree is arranged so that all descendants
107 * of a node n have keys whose bits all agree up to position rj_b - 1.
108 * (We say the index of n is rj_b.)
110 * There is at least one descendant which has a one bit at position rj_b,
111 * and at least one with a zero there.
113 * A route is determined by a pair of key and mask. We require that the
114 * bit-wise logical and of the key and mask to be the key.
115 * We define the index of a route to associated with the mask to be
116 * the first bit number in the mask where 0 occurs (with bit number 0
117 * representing the highest order bit).
119 * We say a mask is normal if every bit is 0, past the index of the mask.
120 * If a node n has a descendant (k, m) with index(m) == index(n) == rj_b,
121 * and m is a normal mask, then the route applies to every descendant of n.
122 * If the index(m) < rj_b, this implies the trailing last few bits of k
123 * before bit b are all 0, (and hence consequently true of every descendant
124 * of n), so the route applies to all descendants of the node as well.
126 * The present version of the code makes no use of normal routes,
127 * but similar logic shows that a non-normal mask m such that
128 * index(m) <= index(n) could potentially apply to many children of n.
129 * Thus, for each non-host route, we attach its mask to a list at an internal
130 * node as high in the tree as we can go.
134 rj_search(v_arg, head)
136 struct radij_node *head;
138 register struct radij_node *x;
141 for (x = head, v = v_arg; x->rj_b >= 0;) {
142 if (x->rj_bmask & v[x->rj_off])
151 rj_search_m(v_arg, head, m_arg)
152 struct radij_node *head;
155 register struct radij_node *x;
156 register caddr_t v = v_arg, m = m_arg;
158 for (x = head; x->rj_b >= 0;) {
159 if ((x->rj_bmask & m[x->rj_off]) &&
160 (x->rj_bmask & v[x->rj_off]))
169 rj_refines(m_arg, n_arg)
172 register caddr_t m = m_arg, n = n_arg;
173 register caddr_t lim, lim2 = lim = n + *(u_char *)n;
174 int longer = (*(u_char *)n++) - (int)(*(u_char *)m++);
175 int masks_are_equal = 1;
189 if (masks_are_equal && (longer < 0))
190 for (lim2 = m - longer; m < lim2; )
193 return (!masks_are_equal);
198 rj_match(v_arg, head)
200 struct radij_node_head *head;
203 register struct radij_node *t = head->rnh_treetop, *x;
204 register caddr_t cp = v, cp2, cp3;
205 caddr_t cplim, mstart;
206 struct radij_node *saved_t, *top = t;
207 int off = t->rj_off, vlen = *(u_char *)cp, matched_off;
210 * Open code rj_search(v, top) to avoid overhead of extra
213 for (; t->rj_b >= 0; ) {
214 if (t->rj_bmask & cp[t->rj_off])
220 * See if we match exactly as a host destination
222 KLIPS_PRINT(debug_radij,
223 "klips_debug:rj_match: "
224 "* See if we match exactly as a host destination\n");
226 cp += off; cp2 = t->rj_key + off; cplim = v + vlen;
227 for (; cp < cplim; cp++, cp2++)
231 * This extra grot is in case we are explicitly asked
232 * to look up the default. Ugh!
234 if ((t->rj_flags & RJF_ROOT) && t->rj_dupedkey)
238 matched_off = cp - v;
240 KLIPS_PRINT(debug_radij,
241 "klips_debug:rj_match: "
242 "** try to match a leaf, t=0x%p\n", t);
246 * Even if we don't match exactly as a hosts;
247 * we may match if the leaf we wound up at is
250 cp3 = matched_off + t->rj_mask;
251 cp2 = matched_off + t->rj_key;
252 for (; cp < cplim; cp++)
253 if ((*cp2++ ^ *cp) & *cp3++)
257 cp = matched_off + v;
259 } while ((t = t->rj_dupedkey));
261 /* start searching up the tree */
262 KLIPS_PRINT(debug_radij,
263 "klips_debug:rj_match: "
264 "*** start searching up the tree, t=0x%p\n",
267 register struct radij_mask *m;
270 KLIPS_PRINT(debug_radij,
271 "klips_debug:rj_match: "
274 if ((m = t->rj_mklist)) {
276 * After doing measurements here, it may
277 * turn out to be faster to open code
278 * rj_search_m here instead of always
279 * copying and masking.
281 /* off = min(t->rj_off, matched_off); */
283 if (matched_off < off)
285 mstart = maskedKey + off;
288 cp3 = m->rm_mask + off;
289 KLIPS_PRINT(debug_radij,
290 "klips_debug:rj_match: "
291 "***** cp2=0x%p cp3=0x%p\n",
293 for (cp = v + off; cp < cplim;)
294 *cp2++ = *cp++ & *cp3++;
295 x = rj_search(maskedKey, t);
296 while (x && x->rj_mask != m->rm_mask)
299 (Bcmp(mstart, x->rj_key + off,
302 } while ((m = m->rm_mklist));
305 KLIPS_PRINT(debug_radij,
306 "klips_debug:rj_match: "
307 "***** not found.\n");
313 struct radij_node *rj_clist;
315 DEBUG_NO_STATIC void traverse(struct radij_node *);
320 #endif /* RJ_DEBUG2 */
321 #endif /* RJ_DEBUG */
324 rj_newpair(v, b, nodes)
327 struct radij_node nodes[2];
329 register struct radij_node *tt = nodes, *t = tt + 1;
330 t->rj_b = b; t->rj_bmask = 0x80 >> (b & 7);
331 t->rj_l = tt; t->rj_off = b >> 3;
332 tt->rj_b = -1; tt->rj_key = (caddr_t)v; tt->rj_p = t;
333 tt->rj_flags = t->rj_flags = RJF_ACTIVE;
335 tt->rj_info = rj_nodenum++; t->rj_info = rj_nodenum++;
336 tt->rj_twin = t; tt->rj_ybro = rj_clist; rj_clist = tt;
337 #endif /* RJ_DEBUG */
342 rj_insert(v_arg, head, dupentry, nodes)
344 struct radij_node_head *head;
346 struct radij_node nodes[2];
349 struct radij_node *top = head->rnh_treetop;
350 int head_off = top->rj_off, vlen = (int)*((u_char *)v);
351 register struct radij_node *t = rj_search(v_arg, top);
352 register caddr_t cp = v + head_off;
354 struct radij_node *tt;
356 *find first bit at which v and t->rj_key differ
359 register caddr_t cp2 = t->rj_key + head_off;
360 register int cmp_res;
361 caddr_t cplim = v + vlen;
370 cmp_res = (cp[-1] ^ cp2[-1]) & 0xff;
371 for (b = (cp - v) << 3; cmp_res; b--)
375 register struct radij_node *p, *x = top;
379 if (cp[x->rj_off] & x->rj_bmask)
382 } while (b > (unsigned) x->rj_b); /* x->rj_b < b && x->rj_b >= 0 */
385 printk("klips_debug:rj_insert: Going In:\n"), traverse(p);
386 #endif /* RJ_DEBUG */
387 t = rj_newpair(v_arg, b, nodes); tt = t->rj_l;
388 if ((cp[p->rj_off] & p->rj_bmask) == 0)
392 x->rj_p = t; t->rj_p = p; /* frees x, p as temp vars below */
393 if ((cp[t->rj_off] & t->rj_bmask) == 0) {
396 t->rj_r = tt; t->rj_l = x;
400 printk("klips_debug:rj_insert: Coming out:\n"), traverse(p);
401 #endif /* RJ_DEBUG */
407 rj_addmask(n_arg, search, skip)
411 caddr_t netmask = (caddr_t)n_arg;
412 register struct radij_node *x;
413 register caddr_t cp, cplim;
414 register int b, mlen, j;
417 mlen = *(u_char *)netmask;
419 x = rj_search(netmask, rj_masktop);
420 mlen = *(u_char *)netmask;
421 if (Bcmp(netmask, x->rj_key, mlen) == 0)
424 R_Malloc(x, struct radij_node *, maj_keylen + 2 * sizeof (*x));
427 Bzero(x, maj_keylen + 2 * sizeof (*x));
428 cp = (caddr_t)(x + 2);
429 Bcopy(netmask, cp, mlen);
431 x = rj_insert(netmask, mask_rjhead, &maskduplicated, x);
433 * Calculate index of mask.
435 cplim = netmask + mlen;
436 for (cp = netmask + skip; cp < cplim; cp++)
437 if (*(u_char *)cp != 0xff)
439 b = (cp - netmask) << 3;
443 for (j = 0x80; j; b++, j >>= 1)
456 rj_addroute(v_arg, n_arg, head, treenodes)
458 struct radij_node_head *head;
459 struct radij_node treenodes[2];
461 caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg;
462 register struct radij_node *t, *x=NULL, *tt;
463 struct radij_node *saved_tt, *top = head->rnh_treetop;
465 int mlen, keyduplicated;
467 struct radij_mask *m, **mp;
470 * In dealing with non-contiguous masks, there may be
471 * many different routes which have the same mask.
472 * We will find it useful to have a unique pointer to
473 * the mask to speed avoiding duplicate references at
474 * nodes and possibly save time in calculating indices.
477 x = rj_search(netmask, rj_masktop);
478 mlen = *(u_char *)netmask;
479 if (Bcmp(netmask, x->rj_key, mlen) != 0) {
480 x = rj_addmask(netmask, 0, top->rj_off);
482 return -ENOMEM; /* (0) rgb */
488 * Deal with duplicated keys: attach node to previous instance
490 saved_tt = tt = rj_insert(v, head, &keyduplicated, treenodes);
493 if (tt->rj_mask == netmask)
494 return -EEXIST; /* -ENXIO; (0) rgb */
497 (tt->rj_mask && rj_refines(netmask, tt->rj_mask)))
499 } while ((tt = tt->rj_dupedkey));
501 * If the mask is not duplicated, we wouldn't
502 * find it among possible duplicate key entries
503 * anyway, so the above test doesn't hurt.
505 * We sort the masks for a duplicated key the same way as
506 * in a masklist -- most specific to least specific.
507 * This may require the unfortunate nuisance of relocating
508 * the head of the list.
510 if (tt && t == saved_tt) {
511 struct radij_node *xx = x;
512 /* link in at head of list */
513 (tt = treenodes)->rj_dupedkey = t;
514 tt->rj_flags = t->rj_flags;
515 tt->rj_p = x = t->rj_p;
516 if (x->rj_l == t) x->rj_l = tt; else x->rj_r = tt;
517 saved_tt = tt; x = xx;
519 (tt = treenodes)->rj_dupedkey = t->rj_dupedkey;
523 t=tt+1; tt->rj_info = rj_nodenum++; t->rj_info = rj_nodenum++;
524 tt->rj_twin = t; tt->rj_ybro = rj_clist; rj_clist = tt;
525 #endif /* RJ_DEBUG */
527 tt->rj_key = (caddr_t) v;
529 tt->rj_flags = t->rj_flags & ~RJF_ROOT;
535 tt->rj_mask = netmask;
539 b_leaf = -1 - t->rj_b;
540 if (t->rj_r == saved_tt) x = t->rj_l; else x = t->rj_r;
541 /* Promote general routes from below */
543 if (x->rj_mask && (x->rj_b >= b_leaf) && x->rj_mklist == 0) {
548 m->rm_mask = x->rj_mask;
549 x->rj_mklist = t->rj_mklist = m;
552 } else if (x->rj_mklist) {
554 * Skip over masks whose index is > that of new node
556 for (mp = &x->rj_mklist; (m = *mp); mp = &m->rm_mklist)
557 if (m->rm_b >= b_leaf)
559 t->rj_mklist = m; *mp = 0;
561 /* Add new route to highest possible ancestor's list */
562 if ((netmask == 0) || (b > t->rj_b ))
563 return 0; /* tt rgb */ /* can't lift at all */
568 } while (b <= t->rj_b && x != top);
570 * Search through routes associated with node to
571 * insert new route according to index.
572 * For nodes of equal index, place more specific
575 cplim = netmask + mlen;
576 for (mp = &x->rj_mklist; (m = *mp); mp = &m->rm_mklist) {
577 if (m->rm_b < b_leaf)
579 if (m->rm_b > b_leaf)
581 if (m->rm_mask == netmask) {
584 return 0; /* tt rgb */
586 if (rj_refines(netmask, m->rm_mask))
591 printk("klips_debug:rj_addroute: "
592 "Mask for route not entered\n");
593 return 0; /* (tt) rgb */
597 m->rm_mask = netmask;
601 return 0; /* tt rgb */
605 rj_delete(v_arg, netmask_arg, head, node)
606 void *v_arg, *netmask_arg;
607 struct radij_node_head *head;
608 struct radij_node **node;
610 register struct radij_node *t, *p, *x, *tt;
611 struct radij_mask *m, *saved_m, **mp;
612 struct radij_node *dupedkey, *saved_tt, *top;
614 int b, head_off, vlen;
617 netmask = netmask_arg;
618 x = head->rnh_treetop;
619 tt = rj_search(v, x);
620 head_off = x->rj_off;
625 Bcmp(v + head_off, tt->rj_key + head_off, vlen - head_off))
626 return -EFAULT; /* (0) rgb */
628 * Delete our route from mask lists.
630 if ((dupedkey = tt->rj_dupedkey)) {
632 netmask = rj_search(netmask, rj_masktop)->rj_key;
633 while (tt->rj_mask != netmask)
634 if ((tt = tt->rj_dupedkey) == 0)
635 return -ENOENT; /* -ENXIO; (0) rgb */
637 if (tt->rj_mask == 0 || (saved_m = m = tt->rj_mklist) == 0)
639 if (m->rm_mask != tt->rj_mask) {
640 printk("klips_debug:rj_delete: "
641 "inconsistent annotation\n");
644 if (--m->rm_refs >= 0)
649 goto on1; /* Wasn't lifted at all */
653 } while (b <= t->rj_b && x != top);
654 for (mp = &x->rj_mklist; (m = *mp); mp = &m->rm_mklist)
661 printk("klips_debug:rj_delete: "
662 "couldn't find our annotation\n");
665 * Eliminate us from tree
667 if (tt->rj_flags & RJF_ROOT)
668 return -EFAULT; /* (0) rgb */
670 /* Get us out of the creation list */
671 for (t = rj_clist; t && t->rj_ybro != tt; t = t->rj_ybro) {}
672 if (t) t->rj_ybro = tt->rj_ybro;
673 #endif /* RJ_DEBUG */
676 if (tt == saved_tt) {
677 x = dupedkey; x->rj_p = t;
678 if (t->rj_l == tt) t->rj_l = x; else t->rj_r = x;
680 for (x = p = saved_tt; p && p->rj_dupedkey != tt;)
682 if (p) p->rj_dupedkey = tt->rj_dupedkey;
683 else printk("klips_debug:rj_delete: "
684 "couldn't find us\n");
687 if (t->rj_flags & RJF_ACTIVE) {
689 *++x = *t; p = t->rj_p;
691 b = t->rj_info; *++x = *t; t->rj_info = b; p = t->rj_p;
692 #endif /* RJ_DEBUG */
693 if (p->rj_l == t) p->rj_l = x; else p->rj_r = x;
694 x->rj_l->rj_p = x; x->rj_r->rj_p = x;
698 if (t->rj_l == tt) x = t->rj_r; else x = t->rj_l;
700 if (p->rj_r == t) p->rj_r = x; else p->rj_l = x;
703 * Demote routes attached to us.
707 for (mp = &x->rj_mklist; (m = *mp);)
711 for (m = t->rj_mklist; m;) {
712 struct radij_mask *mm = m->rm_mklist;
713 if (m == x->rj_mklist && (--(m->rm_refs) < 0)) {
717 printk("klips_debug:rj_delete: "
718 "Orphaned Mask %p at %p\n", m, x);
724 * We may be holding an active internal node in the tree.
731 b = t->rj_info; *t = *x; t->rj_info = b;
732 #endif /* RJ_DEBUG */
733 t->rj_l->rj_p = t; t->rj_r->rj_p = t;
735 if (p->rj_l == x) p->rj_l = t; else p->rj_r = t;
738 tt->rj_flags &= ~RJF_ACTIVE;
739 tt[1].rj_flags &= ~RJF_ACTIVE;
741 return 0; /* (tt) rgb */
746 struct radij_node_head *h;
747 register int (*f)(struct radij_node *,void *);
751 struct radij_node *base, *next;
752 register struct radij_node *rn;
754 if(!h || !f /* || !w */) {
760 * This gets complicated because we may delete the node
761 * while applying the function f to it, so we need to calculate
762 * the successor node in advance.
764 /* First time through node, go left */
765 while (rn->rj_b >= 0)
768 #ifdef CONFIG_IPSEC_DEBUG
770 printk("klips_debug:rj_walktree: "
771 "for: rn=%p rj_b=%d rj_flags=%x",
776 printk(" node off=%x\n",
778 printk(" leaf key = %08x->%08x\n",
779 (u_int)ntohl(((struct sockaddr_encap *)rn->rj_key)->sen_ip_src.s_addr),
780 (u_int)ntohl(((struct sockaddr_encap *)rn->rj_key)->sen_ip_dst.s_addr))
783 #endif /* CONFIG_IPSEC_DEBUG */
785 /* If at right child go back up, otherwise, go right */
786 while (rn->rj_p->rj_r == rn && (rn->rj_flags & RJF_ROOT) == 0)
788 /* Find the next *leaf* since next node might vanish, too */
789 for (rn = rn->rj_p->rj_r; rn->rj_b >= 0;)
792 #ifdef CONFIG_IPSEC_DEBUG
794 printk("klips_debug:rj_walktree: "
795 "processing leaves, rn=%p rj_b=%d rj_flags=%x",
800 printk(" node off=%x\n",
802 printk(" leaf key = %08x->%08x\n",
803 (u_int)ntohl(((struct sockaddr_encap *)rn->rj_key)->sen_ip_src.s_addr),
804 (u_int)ntohl(((struct sockaddr_encap *)rn->rj_key)->sen_ip_dst.s_addr))
807 #endif /* CONFIG_IPSEC_DEBUG */
809 while ((rn = base)) {
810 base = rn->rj_dupedkey;
811 #ifdef CONFIG_IPSEC_DEBUG
813 printk("klips_debug:rj_walktree: "
814 "while: base=%p rn=%p rj_b=%d rj_flags=%x",
820 printk(" node off=%x\n",
822 printk(" leaf key = %08x->%08x\n",
823 (u_int)ntohl(((struct sockaddr_encap *)rn->rj_key)->sen_ip_src.s_addr),
824 (u_int)ntohl(((struct sockaddr_encap *)rn->rj_key)->sen_ip_dst.s_addr))
827 #endif /* CONFIG_IPSEC_DEBUG */
828 if (!(rn->rj_flags & RJF_ROOT) && (error = (*f)(rn, w)))
832 if (rn->rj_flags & RJF_ROOT)
839 rj_inithead(head, off)
843 register struct radij_node_head *rnh;
844 register struct radij_node *t, *tt, *ttt;
847 R_Malloc(rnh, struct radij_node_head *, sizeof (*rnh));
850 Bzero(rnh, sizeof (*rnh));
852 t = rj_newpair(rj_zeroes, off, rnh->rnh_nodes);
853 ttt = rnh->rnh_nodes + 2;
857 tt->rj_flags = t->rj_flags = RJF_ROOT | RJF_ACTIVE;
860 ttt->rj_key = rj_ones;
861 rnh->rnh_addaddr = rj_addroute;
862 rnh->rnh_deladdr = rj_delete;
863 rnh->rnh_matchaddr = rj_match;
864 rnh->rnh_walktree = rj_walktree;
865 rnh->rnh_treetop = t;
874 if (maj_keylen == 0) {
875 printk("klips_debug:rj_init: "
876 "radij functions require maj_keylen be set\n");
879 R_Malloc(rj_zeroes, char *, 3 * maj_keylen);
880 if (rj_zeroes == NULL)
882 Bzero(rj_zeroes, 3 * maj_keylen);
883 rj_ones = cp = rj_zeroes + maj_keylen;
884 maskedKey = cplim = rj_ones + maj_keylen;
887 if (rj_inithead((void **)&mask_rjhead, 0) == 0)
892 rj_preorder(struct radij_node *rn, int l)
897 printk("klips_debug:rj_preorder: "
903 rj_preorder(rn->rj_l, l+1);
904 rj_preorder(rn->rj_r, l+1);
905 printk("klips_debug:");
908 printk(" off = %d\n",
911 printk("klips_debug:");
914 printk(" flags = %x",
915 (u_int)rn->rj_flags);
916 if (rn->rj_flags & RJF_ACTIVE) {
919 printk(" key = %08x->%08x",
920 (u_int)ntohl(((struct sockaddr_encap *)rn->rj_key)->sen_ip_src.s_addr),
921 (u_int)ntohl(((struct sockaddr_encap *)rn->rj_key)->sen_ip_dst.s_addr));
922 printk(" @mask = %p",
925 printk(" mask = %08x->%08x",
926 (u_int)ntohl(((struct sockaddr_encap *)rn->rj_mask)->sen_ip_src.s_addr),
927 (u_int)ntohl(((struct sockaddr_encap *)rn->rj_mask)->sen_ip_dst.s_addr));
929 printk(" dupedkey = %08x",
930 (u_int)rn->rj_dupedkey);
937 DEBUG_NO_STATIC void traverse(struct radij_node *p)
941 #endif /* RJ_DEBUG */
946 rj_preorder(rnh->rnh_treetop, 0);
950 rj_free_mkfreelist(void)
952 struct radij_mask *mknp, *mknp2;
954 mknp = rj_mkfreelist;
958 mknp = mknp->rm_mklist;
966 return rj_walktree(rnh, ipsec_rj_walker_delete, NULL);
974 error = radijcleartree();
976 rj_free_mkfreelist();
978 /* rj_walktree(mask_rjhead, ipsec_rj_walker_delete, NULL); */
996 * Revision 1.40 2002/01/29 17:17:58 mcr
997 * moved include of ipsec_param.h to after include of linux/kernel.h
998 * otherwise, it seems that some option that is set in ipsec_param.h
999 * screws up something subtle in the include path to kernel.h, and
1000 * it complains on the snprintf() prototype.
1002 * Revision 1.39 2002/01/29 04:00:55 mcr
1003 * more excise of kversions.h header.
1005 * Revision 1.38 2002/01/29 02:13:19 mcr
1006 * introduction of ipsec_kversion.h means that include of
1007 * ipsec_param.h must preceed any decisions about what files to
1008 * include to deal with differences in kernel source.
1010 * Revision 1.37 2001/10/18 04:45:23 rgb
1011 * 2.4.9 kernel deprecates linux/malloc.h in favour of linux/slab.h,
1012 * lib/freeswan.h version macros moved to lib/kversions.h.
1013 * Other compiler directive cleanups.
1015 * Revision 1.36 2001/08/22 13:43:51 henry
1016 * eliminate the single use of min() to avoid problems with Linus changing it
1018 * Revision 1.35 2001/06/15 04:57:29 rgb
1019 * Clarified error return codes.
1020 * Changed mask add already exists to EEXIST.
1021 * Changed mask delete did not exist to ENOENT.
1023 * Revision 1.34 2001/05/03 19:44:26 rgb
1024 * Fix sign of error return codes for rj_addroute().
1026 * Revision 1.33 2001/02/27 22:24:56 rgb
1027 * Re-formatting debug output (line-splitting, joining, 1arg/line).
1028 * Check for satoa() return codes.
1030 * Revision 1.32 2001/02/27 06:23:15 rgb
1031 * Debug line splitting.
1033 * Revision 1.31 2000/11/06 04:35:21 rgb
1034 * Clear table *before* releasing other items in radijcleanup.
1036 * Revision 1.30 2000/09/20 04:07:40 rgb
1037 * Changed static functions to DEBUG_NO_STATIC to reveal function names in
1040 * Revision 1.29 2000/09/12 03:25:02 rgb
1041 * Moved radij_c_version printing to ipsec_version_get_info().
1043 * Revision 1.28 2000/09/08 19:12:56 rgb
1044 * Change references from DEBUG_IPSEC to CONFIG_IPSEC_DEBUG.
1046 * Revision 1.27 2000/07/28 14:58:32 rgb
1047 * Changed kfree_s to kfree, eliminating extra arg to fix 2.4.0-test5.
1049 * Revision 1.26 2000/05/10 23:11:37 rgb
1050 * Comment out most of the startup version information.
1052 * Revision 1.25 2000/01/21 06:21:47 rgb
1053 * Change return codes to negative on error.
1055 * Revision 1.24 1999/11/18 04:09:20 rgb
1056 * Replaced all kernel version macros to shorter, readable form.
1058 * Revision 1.23 1999/11/17 15:53:41 rgb
1059 * Changed all occurrences of #include "../../../lib/freeswan.h"
1060 * to #include <freeswan.h> which works due to -Ilibfreeswan in the
1061 * klips/net/ipsec/Makefile.
1063 * Revision 1.22 1999/10/15 22:17:28 rgb
1064 * Modify radijcleanup() to call radijcleartree().
1066 * Revision 1.21 1999/10/08 18:37:34 rgb
1067 * Fix end-of-line spacing to sate whining PHMs.
1069 * Revision 1.20 1999/10/01 15:44:54 rgb
1070 * Move spinlock header include to 2.1> scope.
1072 * Revision 1.19 1999/10/01 08:35:52 rgb
1073 * Add spinlock include to shut up compiler for 2.0.38.
1075 * Revision 1.18 1999/09/23 18:02:52 rgb
1076 * De-alarm the search failure message so it doesn't sound so grave.
1078 * Revision 1.17 1999/05/25 21:26:01 rgb
1079 * Fix rj_walktree() sanity checking bug.
1081 * Revision 1.16 1999/05/09 03:25:38 rgb
1082 * Fix bug introduced by 2.2 quick-and-dirty patch.
1084 * Revision 1.15 1999/05/05 22:02:33 rgb
1085 * Add a quick and dirty port to 2.2 kernels by Marc Boucher <marc@mbsi.ca>.
1087 * Revision 1.14 1999/04/29 15:24:15 rgb
1088 * Add sanity checking for null pointer arguments.
1089 * Standardise an error return method.
1091 * Revision 1.13 1999/04/11 00:29:02 henry
1094 * Revision 1.12 1999/04/06 04:54:28 rgb
1095 * Fix/Add RCSID Id: and Log: bits to make PHMDs happy. This includes
1096 * patch shell fixes.
1098 * Revision 1.11 1999/02/17 16:52:53 rgb
1099 * Convert DEBUG_IPSEC to KLIPS_PRINT
1100 * Clean out unused cruft.
1102 * Revision 1.10 1999/01/22 06:30:05 rgb
1106 * Revision 1.9 1998/12/01 13:22:04 rgb
1107 * Added support for debug printing of version info.
1109 * Revision 1.8 1998/11/30 13:22:55 rgb
1110 * Rationalised all the klips kernel file headers. They are much shorter
1111 * now and won't conflict under RH5.2.
1113 * Revision 1.7 1998/10/25 02:43:26 rgb
1114 * Change return type on rj_addroute and rj_delete and add and argument
1115 * to the latter to be able to transmit more infomation about errors.
1117 * Revision 1.6 1998/10/19 14:30:06 rgb
1118 * Added inclusion of freeswan.h.
1120 * Revision 1.5 1998/10/09 04:33:27 rgb
1121 * Added 'klips_debug' prefix to all klips printk debug statements.
1122 * Fixed output formatting slightly.
1124 * Revision 1.4 1998/07/28 00:06:59 rgb
1125 * Add debug detail to tree traversing.
1127 * Revision 1.3 1998/07/14 18:07:58 rgb
1128 * Add a routine to clear the eroute tree.
1130 * Revision 1.2 1998/06/25 20:03:22 rgb
1131 * Cleanup #endif comments. Debug output for rj_init.
1133 * Revision 1.1 1998/06/18 21:30:22 henry
1134 * move sources from klips/src to klips/net/ipsec to keep stupid kernel
1135 * build scripts happier about symlinks
1137 * Revision 1.8 1998/05/25 20:34:15 rgb
1138 * Remove temporary ipsec_walk, rj_deltree and rj_delnodes functions.
1140 * Rename ipsec_rj_walker (ipsec_walk) to ipsec_rj_walker_procprint and
1141 * add ipsec_rj_walker_delete.
1143 * Recover memory for eroute table on unload of module.
1145 * Revision 1.7 1998/05/21 12:58:58 rgb
1146 * Moved 'extern' definitions to ipsec_radij.h to support /proc 3k limit fix.
1148 * Revision 1.6 1998/04/23 20:57:29 rgb
1149 * Cleaned up compiler warnings for unused debugging functions.
1151 * Revision 1.5 1998/04/22 16:51:38 rgb
1152 * Tidy up radij debug code from recent rash of modifications to debug code.
1154 * Revision 1.4 1998/04/21 21:28:56 rgb
1155 * Rearrange debug switches to change on the fly debug output from user
1156 * space. Only kernel changes checked in at this time. radij.c was also
1157 * changed to temporarily remove buggy debugging code in rj_delete causing
1158 * an OOPS and hence, netlink device open errors.
1160 * Revision 1.3 1998/04/14 17:30:37 rgb
1161 * Fix up compiling errors for radij tree memory reclamation.
1163 * Revision 1.2 1998/04/12 22:03:25 rgb
1164 * Updated ESP-3DES-HMAC-MD5-96,
1165 * ESP-DES-HMAC-MD5-96,
1167 * AH-HMAC-SHA1-96 since Henry started freeswan cvs repository
1168 * from old standards (RFC182[5-9] to new (as of March 1998) drafts.
1170 * Fixed eroute references in /proc/net/ipsec*.
1172 * Started to patch module unloading memory leaks in ipsec_netlink and
1173 * radij tree unloading.
1175 * Revision 1.1 1998/04/09 03:06:15 henry
1176 * sources moved up from linux/net/ipsec
1178 * Revision 1.1.1.1 1998/04/08 05:35:03 henry
1179 * RGB's ipsec-0.8pre2.tar.gz ipsec-0.8
1181 * Revision 0.4 1997/01/15 01:28:15 ji
1184 * Revision 0.3 1996/11/20 14:39:04 ji
1186 * Rationalized debugging code.
1188 * Revision 0.2 1996/11/02 00:18:33 ji
1189 * First limited release.