diff options
Diffstat (limited to 'linux/net/ipsec/radij.c')
| -rw-r--r-- | linux/net/ipsec/radij.c | 992 |
1 files changed, 992 insertions, 0 deletions
diff --git a/linux/net/ipsec/radij.c b/linux/net/ipsec/radij.c new file mode 100644 index 000000000..7dbec8d37 --- /dev/null +++ b/linux/net/ipsec/radij.c @@ -0,0 +1,992 @@ +char radij_c_version[] = "RCSID $Id: radij.c,v 1.2 2004/06/13 19:57:50 as Exp $"; + +/* + * This file is defived from ${SRC}/sys/net/radix.c of BSD 4.4lite + * + * Variable and procedure names have been modified so that they don't + * conflict with the original BSD code, as a small number of modifications + * have been introduced and we may want to reuse this code in BSD. + * + * The `j' in `radij' is pronounced as a voiceless guttural (like a Greek + * chi or a German ch sound (as `doch', not as in `milch'), or even a + * spanish j as in Juan. It is not as far back in the throat like + * the corresponding Hebrew sound, nor is it a soft breath like the English h. + * It has nothing to do with the Dutch ij sound. + * + * Here is the appropriate copyright notice: + */ + +/* + * Copyright (c) 1988, 1989, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * @(#)radix.c 8.2 (Berkeley) 1/4/94 + */ + +/* + * Routines to build and maintain radix trees for routing lookups. + */ + +#include <linux/config.h> +#include <linux/version.h> +#include <linux/kernel.h> /* printk() */ + +#include "freeswan/ipsec_param.h" + +#ifdef MALLOC_SLAB +# include <linux/slab.h> /* kmalloc() */ +#else /* MALLOC_SLAB */ +# include <linux/malloc.h> /* kmalloc() */ +#endif /* MALLOC_SLAB */ +#include <linux/errno.h> /* error codes */ +#include <linux/types.h> /* size_t */ +#include <linux/interrupt.h> /* mark_bh */ + +#include <linux/netdevice.h> /* struct device, and other headers */ +#include <linux/etherdevice.h> /* eth_type_trans */ +#include <linux/ip.h> /* struct iphdr */ +#include <linux/skbuff.h> +#ifdef NET_21 +# include <asm/uaccess.h> +# include <linux/in6.h> +#endif /* NET_21 */ +#include <asm/checksum.h> +#include <net/ip.h> + +#include <freeswan.h> + +#include "freeswan/radij.h" +#include "freeswan/ipsec_encap.h" +#include "freeswan/ipsec_radij.h" + +int maj_keylen; +struct radij_mask *rj_mkfreelist; +struct radij_node_head *mask_rjhead; +static int gotOddMasks; +static char *maskedKey; +static char *rj_zeroes, *rj_ones; + +#define rj_masktop (mask_rjhead->rnh_treetop) +#ifdef Bcmp +# undef Bcmp +#endif /* Bcmp */ +#define Bcmp(a, b, l) (l == 0 ? 0 : memcmp((caddr_t)(b), (caddr_t)(a), (size_t)l)) +/* + * The data structure for the keys is a radix tree with one way + * branching removed. The index rj_b at an internal node n represents a bit + * position to be tested. The tree is arranged so that all descendants + * of a node n have keys whose bits all agree up to position rj_b - 1. + * (We say the index of n is rj_b.) + * + * There is at least one descendant which has a one bit at position rj_b, + * and at least one with a zero there. + * + * A route is determined by a pair of key and mask. We require that the + * bit-wise logical and of the key and mask to be the key. + * We define the index of a route to associated with the mask to be + * the first bit number in the mask where 0 occurs (with bit number 0 + * representing the highest order bit). + * + * We say a mask is normal if every bit is 0, past the index of the mask. + * If a node n has a descendant (k, m) with index(m) == index(n) == rj_b, + * and m is a normal mask, then the route applies to every descendant of n. + * If the index(m) < rj_b, this implies the trailing last few bits of k + * before bit b are all 0, (and hence consequently true of every descendant + * of n), so the route applies to all descendants of the node as well. + * + * The present version of the code makes no use of normal routes, + * but similar logic shows that a non-normal mask m such that + * index(m) <= index(n) could potentially apply to many children of n. + * Thus, for each non-host route, we attach its mask to a list at an internal + * node as high in the tree as we can go. + */ + +struct radij_node * +rj_search(v_arg, head) + void *v_arg; + struct radij_node *head; +{ + register struct radij_node *x; + register caddr_t v; + + for (x = head, v = v_arg; x->rj_b >= 0;) { + if (x->rj_bmask & v[x->rj_off]) + x = x->rj_r; + else + x = x->rj_l; + } + return (x); +}; + +struct radij_node * +rj_search_m(v_arg, head, m_arg) + struct radij_node *head; + void *v_arg, *m_arg; +{ + register struct radij_node *x; + register caddr_t v = v_arg, m = m_arg; + + for (x = head; x->rj_b >= 0;) { + if ((x->rj_bmask & m[x->rj_off]) && + (x->rj_bmask & v[x->rj_off])) + x = x->rj_r; + else + x = x->rj_l; + } + return x; +}; + +int +rj_refines(m_arg, n_arg) + void *m_arg, *n_arg; +{ + register caddr_t m = m_arg, n = n_arg; + register caddr_t lim, lim2 = lim = n + *(u_char *)n; + int longer = (*(u_char *)n++) - (int)(*(u_char *)m++); + int masks_are_equal = 1; + + if (longer > 0) + lim -= longer; + while (n < lim) { + if (*n & ~(*m)) + return 0; + if (*n++ != *m++) + masks_are_equal = 0; + + } + while (n < lim2) + if (*n++) + return 0; + if (masks_are_equal && (longer < 0)) + for (lim2 = m - longer; m < lim2; ) + if (*m++) + return 1; + return (!masks_are_equal); +} + + +struct radij_node * +rj_match(v_arg, head) + void *v_arg; + struct radij_node_head *head; +{ + caddr_t v = v_arg; + register struct radij_node *t = head->rnh_treetop, *x; + register caddr_t cp = v, cp2, cp3; + caddr_t cplim, mstart; + struct radij_node *saved_t, *top = t; + int off = t->rj_off, vlen = *(u_char *)cp, matched_off; + + /* + * Open code rj_search(v, top) to avoid overhead of extra + * subroutine call. + */ + for (; t->rj_b >= 0; ) { + if (t->rj_bmask & cp[t->rj_off]) + t = t->rj_r; + else + t = t->rj_l; + } + /* + * See if we match exactly as a host destination + */ + KLIPS_PRINT(debug_radij, + "klips_debug:rj_match: " + "* See if we match exactly as a host destination\n"); + + cp += off; cp2 = t->rj_key + off; cplim = v + vlen; + for (; cp < cplim; cp++, cp2++) + if (*cp != *cp2) + goto on1; + /* + * This extra grot is in case we are explicitly asked + * to look up the default. Ugh! + */ + if ((t->rj_flags & RJF_ROOT) && t->rj_dupedkey) + t = t->rj_dupedkey; + return t; +on1: + matched_off = cp - v; + saved_t = t; + KLIPS_PRINT(debug_radij, + "klips_debug:rj_match: " + "** try to match a leaf, t=0p%p\n", t); + do { + if (t->rj_mask) { + /* + * Even if we don't match exactly as a hosts; + * we may match if the leaf we wound up at is + * a route to a net. + */ + cp3 = matched_off + t->rj_mask; + cp2 = matched_off + t->rj_key; + for (; cp < cplim; cp++) + if ((*cp2++ ^ *cp) & *cp3++) + break; + if (cp == cplim) + return t; + cp = matched_off + v; + } + } while ((t = t->rj_dupedkey)); + t = saved_t; + /* start searching up the tree */ + KLIPS_PRINT(debug_radij, + "klips_debug:rj_match: " + "*** start searching up the tree, t=0p%p\n", + t); + do { + register struct radij_mask *m; + + t = t->rj_p; + KLIPS_PRINT(debug_radij, + "klips_debug:rj_match: " + "**** t=0p%p\n", + t); + if ((m = t->rj_mklist)) { + /* + * After doing measurements here, it may + * turn out to be faster to open code + * rj_search_m here instead of always + * copying and masking. + */ + /* off = min(t->rj_off, matched_off); */ + off = t->rj_off; + if (matched_off < off) + off = matched_off; + mstart = maskedKey + off; + do { + cp2 = mstart; + cp3 = m->rm_mask + off; + KLIPS_PRINT(debug_radij, + "klips_debug:rj_match: " + "***** cp2=0p%p cp3=0p%p\n", + cp2, cp3); + for (cp = v + off; cp < cplim;) + *cp2++ = *cp++ & *cp3++; + x = rj_search(maskedKey, t); + while (x && x->rj_mask != m->rm_mask) + x = x->rj_dupedkey; + if (x && + (Bcmp(mstart, x->rj_key + off, + vlen - off) == 0)) + return x; + } while ((m = m->rm_mklist)); + } + } while (t != top); + KLIPS_PRINT(debug_radij, + "klips_debug:rj_match: " + "***** not found.\n"); + return 0; +}; + +#ifdef RJ_DEBUG +int rj_nodenum; +struct radij_node *rj_clist; +int rj_saveinfo; +DEBUG_NO_STATIC void traverse(struct radij_node *); +#ifdef RJ_DEBUG2 +int rj_debug = 1; +#else +int rj_debug = 0; +#endif /* RJ_DEBUG2 */ +#endif /* RJ_DEBUG */ + +struct radij_node * +rj_newpair(v, b, nodes) + void *v; + int b; + struct radij_node nodes[2]; +{ + register struct radij_node *tt = nodes, *t = tt + 1; + t->rj_b = b; t->rj_bmask = 0x80 >> (b & 7); + t->rj_l = tt; t->rj_off = b >> 3; + tt->rj_b = -1; tt->rj_key = (caddr_t)v; tt->rj_p = t; + tt->rj_flags = t->rj_flags = RJF_ACTIVE; +#ifdef RJ_DEBUG + tt->rj_info = rj_nodenum++; t->rj_info = rj_nodenum++; + tt->rj_twin = t; tt->rj_ybro = rj_clist; rj_clist = tt; +#endif /* RJ_DEBUG */ + return t; +} + +struct radij_node * +rj_insert(v_arg, head, dupentry, nodes) + void *v_arg; + struct radij_node_head *head; + int *dupentry; + struct radij_node nodes[2]; +{ + caddr_t v = v_arg; + struct radij_node *top = head->rnh_treetop; + int head_off = top->rj_off, vlen = (int)*((u_char *)v); + register struct radij_node *t = rj_search(v_arg, top); + register caddr_t cp = v + head_off; + register int b; + struct radij_node *tt; + /* + *find first bit at which v and t->rj_key differ + */ + { + register caddr_t cp2 = t->rj_key + head_off; + register int cmp_res; + caddr_t cplim = v + vlen; + + while (cp < cplim) + if (*cp2++ != *cp++) + goto on1; + *dupentry = 1; + return t; +on1: + *dupentry = 0; + cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; + for (b = (cp - v) << 3; cmp_res; b--) + cmp_res >>= 1; + } + { + register struct radij_node *p, *x = top; + cp = v; + do { + p = x; + if (cp[x->rj_off] & x->rj_bmask) + x = x->rj_r; + else x = x->rj_l; + } while (b > (unsigned) x->rj_b); /* x->rj_b < b && x->rj_b >= 0 */ +#ifdef RJ_DEBUG + if (rj_debug) + printk("klips_debug:rj_insert: Going In:\n"), traverse(p); +#endif /* RJ_DEBUG */ + t = rj_newpair(v_arg, b, nodes); tt = t->rj_l; + if ((cp[p->rj_off] & p->rj_bmask) == 0) + p->rj_l = t; + else + p->rj_r = t; + x->rj_p = t; t->rj_p = p; /* frees x, p as temp vars below */ + if ((cp[t->rj_off] & t->rj_bmask) == 0) { + t->rj_r = x; + } else { + t->rj_r = tt; t->rj_l = x; + } +#ifdef RJ_DEBUG + if (rj_debug) + printk("klips_debug:rj_insert: Coming out:\n"), traverse(p); +#endif /* RJ_DEBUG */ + } + return (tt); +} + +struct radij_node * +rj_addmask(n_arg, search, skip) + int search, skip; + void *n_arg; +{ + caddr_t netmask = (caddr_t)n_arg; + register struct radij_node *x; + register caddr_t cp, cplim; + register int b, mlen, j; + int maskduplicated; + + mlen = *(u_char *)netmask; + if (search) { + x = rj_search(netmask, rj_masktop); + mlen = *(u_char *)netmask; + if (Bcmp(netmask, x->rj_key, mlen) == 0) + return (x); + } + R_Malloc(x, struct radij_node *, maj_keylen + 2 * sizeof (*x)); + if (x == 0) + return (0); + Bzero(x, maj_keylen + 2 * sizeof (*x)); + cp = (caddr_t)(x + 2); + Bcopy(netmask, cp, mlen); + netmask = cp; + x = rj_insert(netmask, mask_rjhead, &maskduplicated, x); + /* + * Calculate index of mask. + */ + cplim = netmask + mlen; + for (cp = netmask + skip; cp < cplim; cp++) + if (*(u_char *)cp != 0xff) + break; + b = (cp - netmask) << 3; + if (cp != cplim) { + if (*cp != 0) { + gotOddMasks = 1; + for (j = 0x80; j; b++, j >>= 1) + if ((j & *cp) == 0) + break; + } + } + x->rj_b = -1 - b; + return (x); +} + +#if 0 +struct radij_node * +#endif +int +rj_addroute(v_arg, n_arg, head, treenodes) + void *v_arg, *n_arg; + struct radij_node_head *head; + struct radij_node treenodes[2]; +{ + caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg; + register struct radij_node *t, *x=NULL, *tt; + struct radij_node *saved_tt, *top = head->rnh_treetop; + short b = 0, b_leaf; + int mlen, keyduplicated; + caddr_t cplim; + struct radij_mask *m, **mp; + + /* + * In dealing with non-contiguous masks, there may be + * many different routes which have the same mask. + * We will find it useful to have a unique pointer to + * the mask to speed avoiding duplicate references at + * nodes and possibly save time in calculating indices. + */ + if (netmask) { + x = rj_search(netmask, rj_masktop); + mlen = *(u_char *)netmask; + if (Bcmp(netmask, x->rj_key, mlen) != 0) { + x = rj_addmask(netmask, 0, top->rj_off); + if (x == 0) + return -ENOMEM; /* (0) rgb */ + } + netmask = x->rj_key; + b = -1 - x->rj_b; + } + /* + * Deal with duplicated keys: attach node to previous instance + */ + saved_tt = tt = rj_insert(v, head, &keyduplicated, treenodes); + if (keyduplicated) { + do { + if (tt->rj_mask == netmask) + return -EEXIST; /* -ENXIO; (0) rgb */ + t = tt; + if (netmask == 0 || + (tt->rj_mask && rj_refines(netmask, tt->rj_mask))) + break; + } while ((tt = tt->rj_dupedkey)); + /* + * If the mask is not duplicated, we wouldn't + * find it among possible duplicate key entries + * anyway, so the above test doesn't hurt. + * + * We sort the masks for a duplicated key the same way as + * in a masklist -- most specific to least specific. + * This may require the unfortunate nuisance of relocating + * the head of the list. + */ + if (tt && t == saved_tt) { + struct radij_node *xx = x; + /* link in at head of list */ + (tt = treenodes)->rj_dupedkey = t; + tt->rj_flags = t->rj_flags; + tt->rj_p = x = t->rj_p; + if (x->rj_l == t) x->rj_l = tt; else x->rj_r = tt; + saved_tt = tt; x = xx; + } else { + (tt = treenodes)->rj_dupedkey = t->rj_dupedkey; + t->rj_dupedkey = tt; + } +#ifdef RJ_DEBUG + t=tt+1; tt->rj_info = rj_nodenum++; t->rj_info = rj_nodenum++; + tt->rj_twin = t; tt->rj_ybro = rj_clist; rj_clist = tt; +#endif /* RJ_DEBUG */ + t = saved_tt; + tt->rj_key = (caddr_t) v; + tt->rj_b = -1; + tt->rj_flags = t->rj_flags & ~RJF_ROOT; + } + /* + * Put mask in tree. + */ + if (netmask) { + tt->rj_mask = netmask; + tt->rj_b = x->rj_b; + } + t = saved_tt->rj_p; + b_leaf = -1 - t->rj_b; + if (t->rj_r == saved_tt) x = t->rj_l; else x = t->rj_r; + /* Promote general routes from below */ + if (x->rj_b < 0) { + if (x->rj_mask && (x->rj_b >= b_leaf) && x->rj_mklist == 0) { + MKGet(m); + if (m) { + Bzero(m, sizeof *m); + m->rm_b = x->rj_b; + m->rm_mask = x->rj_mask; + x->rj_mklist = t->rj_mklist = m; + } + } + } else if (x->rj_mklist) { + /* + * Skip over masks whose index is > that of new node + */ + for (mp = &x->rj_mklist; (m = *mp); mp = &m->rm_mklist) + if (m->rm_b >= b_leaf) + break; + t->rj_mklist = m; *mp = 0; + } + /* Add new route to highest possible ancestor's list */ + if ((netmask == 0) || (b > t->rj_b )) + return 0; /* tt rgb */ /* can't lift at all */ + b_leaf = tt->rj_b; + do { + x = t; + t = t->rj_p; + } while (b <= t->rj_b && x != top); + /* + * Search through routes associated with node to + * insert new route according to index. + * For nodes of equal index, place more specific + * masks first. + */ + cplim = netmask + mlen; + for (mp = &x->rj_mklist; (m = *mp); mp = &m->rm_mklist) { + if (m->rm_b < b_leaf) + continue; + if (m->rm_b > b_leaf) + break; + if (m->rm_mask == netmask) { + m->rm_refs++; + tt->rj_mklist = m; + return 0; /* tt rgb */ + } + if (rj_refines(netmask, m->rm_mask)) + break; + } + MKGet(m); + if (m == 0) { + printk("klips_debug:rj_addroute: " + "Mask for route not entered\n"); + return 0; /* (tt) rgb */ + } + Bzero(m, sizeof *m); + m->rm_b = b_leaf; + m->rm_mask = netmask; + m->rm_mklist = *mp; + *mp = m; + tt->rj_mklist = m; + return 0; /* tt rgb */ +} + +int +rj_delete(v_arg, netmask_arg, head, node) + void *v_arg, *netmask_arg; + struct radij_node_head *head; + struct radij_node **node; +{ + register struct radij_node *t, *p, *x, *tt; + struct radij_mask *m, *saved_m, **mp; + struct radij_node *dupedkey, *saved_tt, *top; + caddr_t v, netmask; + int b, head_off, vlen; + + v = v_arg; + netmask = netmask_arg; + x = head->rnh_treetop; + tt = rj_search(v, x); + head_off = x->rj_off; + vlen = *(u_char *)v; + saved_tt = tt; + top = x; + if (tt == 0 || + Bcmp(v + head_off, tt->rj_key + head_off, vlen - head_off)) + return -EFAULT; /* (0) rgb */ + /* + * Delete our route from mask lists. + */ + if ((dupedkey = tt->rj_dupedkey)) { + if (netmask) + netmask = rj_search(netmask, rj_masktop)->rj_key; + while (tt->rj_mask != netmask) + if ((tt = tt->rj_dupedkey) == 0) + return -ENOENT; /* -ENXIO; (0) rgb */ + } + if (tt->rj_mask == 0 || (saved_m = m = tt->rj_mklist) == 0) + goto on1; + if (m->rm_mask != tt->rj_mask) { + printk("klips_debug:rj_delete: " + "inconsistent annotation\n"); + goto on1; + } + if (--m->rm_refs >= 0) + goto on1; + b = -1 - tt->rj_b; + t = saved_tt->rj_p; + if (b > t->rj_b) + goto on1; /* Wasn't lifted at all */ + do { + x = t; + t = t->rj_p; + } while (b <= t->rj_b && x != top); + for (mp = &x->rj_mklist; (m = *mp); mp = &m->rm_mklist) + if (m == saved_m) { + *mp = m->rm_mklist; + MKFree(m); + break; + } + if (m == 0) + printk("klips_debug:rj_delete: " + "couldn't find our annotation\n"); +on1: + /* + * Eliminate us from tree + */ + if (tt->rj_flags & RJF_ROOT) + return -EFAULT; /* (0) rgb */ +#ifdef RJ_DEBUG + /* Get us out of the creation list */ + for (t = rj_clist; t && t->rj_ybro != tt; t = t->rj_ybro) {} + if (t) t->rj_ybro = tt->rj_ybro; +#endif /* RJ_DEBUG */ + t = tt->rj_p; + if (dupedkey) { + if (tt == saved_tt) { + x = dupedkey; x->rj_p = t; + if (t->rj_l == tt) t->rj_l = x; else t->rj_r = x; + } else { + for (x = p = saved_tt; p && p->rj_dupedkey != tt;) + p = p->rj_dupedkey; + if (p) p->rj_dupedkey = tt->rj_dupedkey; + else printk("klips_debug:rj_delete: " + "couldn't find us\n"); + } + t = tt + 1; + if (t->rj_flags & RJF_ACTIVE) { +#ifndef RJ_DEBUG + *++x = *t; p = t->rj_p; +#else + b = t->rj_info; *++x = *t; t->rj_info = b; p = t->rj_p; +#endif /* RJ_DEBUG */ + if (p->rj_l == t) p->rj_l = x; else p->rj_r = x; + x->rj_l->rj_p = x; x->rj_r->rj_p = x; + } + goto out; + } + if (t->rj_l == tt) x = t->rj_r; else x = t->rj_l; + p = t->rj_p; + if (p->rj_r == t) p->rj_r = x; else p->rj_l = x; + x->rj_p = p; + /* + * Demote routes attached to us. + */ + if (t->rj_mklist) { + if (x->rj_b >= 0) { + for (mp = &x->rj_mklist; (m = *mp);) + mp = &m->rm_mklist; + *mp = t->rj_mklist; + } else { + for (m = t->rj_mklist; m;) { + struct radij_mask *mm = m->rm_mklist; + if (m == x->rj_mklist && (--(m->rm_refs) < 0)) { + x->rj_mklist = 0; + MKFree(m); + } else + printk("klips_debug:rj_delete: " + "Orphaned Mask 0p%p at 0p%p\n", m, x); + m = mm; + } + } + } + /* + * We may be holding an active internal node in the tree. + */ + x = tt + 1; + if (t != x) { +#ifndef RJ_DEBUG + *t = *x; +#else + b = t->rj_info; *t = *x; t->rj_info = b; +#endif /* RJ_DEBUG */ + t->rj_l->rj_p = t; t->rj_r->rj_p = t; + p = x->rj_p; + if (p->rj_l == x) p->rj_l = t; else p->rj_r = t; + } +out: + tt->rj_flags &= ~RJF_ACTIVE; + tt[1].rj_flags &= ~RJF_ACTIVE; + *node = tt; + return 0; /* (tt) rgb */ +} + +int +rj_walktree(h, f, w) + struct radij_node_head *h; + register int (*f)(struct radij_node *,void *); + void *w; +{ + int error; + struct radij_node *base, *next; + register struct radij_node *rn; + + if(!h || !f /* || !w */) { + return -ENODATA; + } + + rn = h->rnh_treetop; + /* + * This gets complicated because we may delete the node + * while applying the function f to it, so we need to calculate + * the successor node in advance. + */ + /* First time through node, go left */ + while (rn->rj_b >= 0) + rn = rn->rj_l; + for (;;) { +#ifdef CONFIG_IPSEC_DEBUG + if(debug_radij) { + printk("klips_debug:rj_walktree: " + "for: rn=0p%p rj_b=%d rj_flags=%x", + rn, + rn->rj_b, + rn->rj_flags); + rn->rj_b >= 0 ? + printk(" node off=%x\n", + rn->rj_off) : + printk(" leaf key = %08x->%08x\n", + (u_int)ntohl(((struct sockaddr_encap *)rn->rj_key)->sen_ip_src.s_addr), + (u_int)ntohl(((struct sockaddr_encap *)rn->rj_key)->sen_ip_dst.s_addr)) + ; + } +#endif /* CONFIG_IPSEC_DEBUG */ + base = rn; + /* If at right child go back up, otherwise, go right */ + while (rn->rj_p->rj_r == rn && (rn->rj_flags & RJF_ROOT) == 0) + rn = rn->rj_p; + /* Find the next *leaf* since next node might vanish, too */ + for (rn = rn->rj_p->rj_r; rn->rj_b >= 0;) + rn = rn->rj_l; + next = rn; +#ifdef CONFIG_IPSEC_DEBUG + if(debug_radij) { + printk("klips_debug:rj_walktree: " + "processing leaves, rn=0p%p rj_b=%d rj_flags=%x", + rn, + rn->rj_b, + rn->rj_flags); + rn->rj_b >= 0 ? + printk(" node off=%x\n", + rn->rj_off) : + printk(" leaf key = %08x->%08x\n", + (u_int)ntohl(((struct sockaddr_encap *)rn->rj_key)->sen_ip_src.s_addr), + (u_int)ntohl(((struct sockaddr_encap *)rn->rj_key)->sen_ip_dst.s_addr)) + ; + } +#endif /* CONFIG_IPSEC_DEBUG */ + /* Process leaves */ + while ((rn = base)) { + base = rn->rj_dupedkey; +#ifdef CONFIG_IPSEC_DEBUG + if(debug_radij) { + printk("klips_debug:rj_walktree: " + "while: base=0p%p rn=0p%p rj_b=%d rj_flags=%x", + base, + rn, + rn->rj_b, + rn->rj_flags); + rn->rj_b >= 0 ? + printk(" node off=%x\n", + rn->rj_off) : + printk(" leaf key = %08x->%08x\n", + (u_int)ntohl(((struct sockaddr_encap *)rn->rj_key)->sen_ip_src.s_addr), + (u_int)ntohl(((struct sockaddr_encap *)rn->rj_key)->sen_ip_dst.s_addr)) + ; + } +#endif /* CONFIG_IPSEC_DEBUG */ + if (!(rn->rj_flags & RJF_ROOT) && (error = (*f)(rn, w))) + return (-error); + } + rn = next; + if (rn->rj_flags & RJF_ROOT) + return (0); + } + /* NOTREACHED */ +} + +int +rj_inithead(head, off) + void **head; + int off; +{ + register struct radij_node_head *rnh; + register struct radij_node *t, *tt, *ttt; + if (*head) + return (1); + R_Malloc(rnh, struct radij_node_head *, sizeof (*rnh)); + if (rnh == NULL) + return (0); + Bzero(rnh, sizeof (*rnh)); + *head = rnh; + t = rj_newpair(rj_zeroes, off, rnh->rnh_nodes); + ttt = rnh->rnh_nodes + 2; + t->rj_r = ttt; + t->rj_p = t; + tt = t->rj_l; + tt->rj_flags = t->rj_flags = RJF_ROOT | RJF_ACTIVE; + tt->rj_b = -1 - off; + *ttt = *tt; + ttt->rj_key = rj_ones; + rnh->rnh_addaddr = rj_addroute; + rnh->rnh_deladdr = rj_delete; + rnh->rnh_matchaddr = rj_match; + rnh->rnh_walktree = rj_walktree; + rnh->rnh_treetop = t; + return (1); +} + +void +rj_init() +{ + char *cp, *cplim; + + if (maj_keylen == 0) { + printk("klips_debug:rj_init: " + "radij functions require maj_keylen be set\n"); + return; + } + R_Malloc(rj_zeroes, char *, 3 * maj_keylen); + if (rj_zeroes == NULL) + panic("rj_init"); + Bzero(rj_zeroes, 3 * maj_keylen); + rj_ones = cp = rj_zeroes + maj_keylen; + maskedKey = cplim = rj_ones + maj_keylen; + while (cp < cplim) + *cp++ = -1; + if (rj_inithead((void **)&mask_rjhead, 0) == 0) + panic("rj_init 2"); +} + +void +rj_preorder(struct radij_node *rn, int l) +{ + int i; + + if (rn == NULL){ + printk("klips_debug:rj_preorder: " + "NULL pointer\n"); + return; + } + + if (rn->rj_b >= 0){ + rj_preorder(rn->rj_l, l+1); + rj_preorder(rn->rj_r, l+1); + printk("klips_debug:"); + for (i=0; i<l; i++) + printk("*"); + printk(" off = %d\n", + rn->rj_off); + } else { + printk("klips_debug:"); + for (i=0; i<l; i++) + printk("@"); + printk(" flags = %x", + (u_int)rn->rj_flags); + if (rn->rj_flags & RJF_ACTIVE) { + printk(" @key=0p%p", + rn->rj_key); + printk(" key = %08x->%08x", + (u_int)ntohl(((struct sockaddr_encap *)rn->rj_key)->sen_ip_src.s_addr), + (u_int)ntohl(((struct sockaddr_encap *)rn->rj_key)->sen_ip_dst.s_addr)); + printk(" @mask=0p%p", + rn->rj_mask); + if (rn->rj_mask) + printk(" mask = %08x->%08x", + (u_int)ntohl(((struct sockaddr_encap *)rn->rj_mask)->sen_ip_src.s_addr), + (u_int)ntohl(((struct sockaddr_encap *)rn->rj_mask)->sen_ip_dst.s_addr)); + if (rn->rj_dupedkey) + printk(" dupedkey = 0p%p", + rn->rj_dupedkey); + } + printk("\n"); + } +} + +#ifdef RJ_DEBUG +DEBUG_NO_STATIC void traverse(struct radij_node *p) +{ + rj_preorder(p, 0); +} +#endif /* RJ_DEBUG */ + +void +rj_dumptrees(void) +{ + rj_preorder(rnh->rnh_treetop, 0); +} + +void +rj_free_mkfreelist(void) +{ + struct radij_mask *mknp, *mknp2; + + mknp = rj_mkfreelist; + while(mknp) + { + mknp2 = mknp; + mknp = mknp->rm_mklist; + kfree(mknp2); + } +} + +int +radijcleartree(void) +{ + return rj_walktree(rnh, ipsec_rj_walker_delete, NULL); +} + +int +radijcleanup(void) +{ + int error = 0; + + error = radijcleartree(); + + rj_free_mkfreelist(); + +/* rj_walktree(mask_rjhead, ipsec_rj_walker_delete, NULL); */ + if(mask_rjhead) { + kfree(mask_rjhead); + } + + if(rj_zeroes) { + kfree(rj_zeroes); + } + + if(rnh) { + kfree(rnh); + } + + return error; +} + |