/* * 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 #if LINUX_VERSION_CODE < KERNEL_VERSION(2, 6, 38) && \ !defined(AUTOCONF_INCLUDED) #include #endif #include /* printk() */ #include "libreswan/ipsec_param.h" #include /* kmalloc() */ #include /* error codes */ #include /* size_t */ #include /* mark_bh */ #include /* struct device, and other headers */ #include /* eth_type_trans */ #include /* struct iphdr */ #include # include #include #include #include "libreswan/radij.h" #include "libreswan/ipsec_encap.h" #include "libreswan/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 unsigned char *dumper; int dumper_len; 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); #ifdef RJ_DEBUG printk("addkey: duplicated: %d\n", keyduplicated); #endif 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 )) { #ifdef RJ_DEBUG printk("klips:radij.c: netmask = %p or b(%d)>t->rjb(%d)\n", netmask, b, t->rj_b); #endif 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; #ifdef RJ_DEBUG printk("klips:radij.c: m->rm_mask %p == netmask\n", netmask); #endif 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; #ifdef RJ_DEBUG printk("klips:radij.c: addroute done\n"); #endif 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 node that we started with\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 (;; ) { 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)); } 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; 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)); } /* Process leaves */ while ((rn = base)) { base = rn->rj_dupedkey; 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)); } 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; }