diff options
Diffstat (limited to 'linux/net/ipsec/radij.c')
| -rw-r--r-- | linux/net/ipsec/radij.c | 992 |
1 files changed, 0 insertions, 992 deletions
diff --git a/linux/net/ipsec/radij.c b/linux/net/ipsec/radij.c deleted file mode 100644 index 7dbec8d37..000000000 --- a/linux/net/ipsec/radij.c +++ /dev/null @@ -1,992 +0,0 @@ -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; -} - |