include/net/radix.h

   1 /*
   2  * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
   3  * Use is subject to license terms.
   4  *
   5  * Copyright (c) 1988, 1989, 1993
   6  *      The Regents of the University of California.  All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 4. Neither the name of the University nor the names of its contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  *
  32  *      @(#)radix.h     8.2 (Berkeley) 10/31/94
  33  * $FreeBSD: /repoman/r/ncvs/src/sys/net/radix.h,v 1.25.2.1 2005/01/31 23:26:23
  34  * imp Exp $
  35  */
  36
  37 #ifndef _RADIX_H_
  38 #define _RADIX_H_
  39
  40 #pragma ident   "%Z%%M% %I%     %E% SMI"
  41
  42 #ifdef  __cplusplus
  43 extern "C" {
  44 #endif
  45
  46 #ifdef _KERNEL
  47 #include <sys/mutex.h>
  48 #include <netinet/in.h>
  49 #endif
  50 #include <sys/sysmacros.h>
  51
  52 #ifdef MALLOC_DECLARE
  53 MALLOC_DECLARE(M_RTABLE);
  54 #endif
  55
  56 /*
  57  * Radix search tree node layout.
  58  */
  59
  60 struct radix_node {
  61         struct  radix_mask *rn_mklist;  /* list of masks contained in subtree */
  62         struct  radix_node *rn_parent;  /* parent */
  63         short   rn_bit;                 /* bit offset; -1-index(netmask) */
  64         char    rn_bmask;               /* node: mask for bit test */
  65         uchar_t rn_flags;               /* enumerated next */
  66 #define RNF_NORMAL      1               /* leaf contains normal route */
  67 #define RNF_ROOT        2               /* leaf is root leaf for tree */
  68 #define RNF_ACTIVE      4               /* This node is alive (for rtfree) */
  69         union {
  70                 struct {                        /* leaf only data: */
  71                         caddr_t rn_Key;         /* object of search */
  72                         caddr_t rn_Mask;        /* netmask, if present */
  73                         struct  radix_node *rn_Dupedkey;
  74                 } rn_leaf;
  75                 struct {                        /* node only data: */
  76                         int     rn_Off;         /* where to start compare */
  77                         struct  radix_node *rn_L; /* progeny */
  78                         struct  radix_node *rn_R; /* progeny */
  79                 } rn_node;
  80         }               rn_u;
  81 };
  82
  83
  84 #define rn_dupedkey     rn_u.rn_leaf.rn_Dupedkey
  85 #define rn_key          rn_u.rn_leaf.rn_Key
  86 #define rn_mask         rn_u.rn_leaf.rn_Mask
  87 #define rn_offset       rn_u.rn_node.rn_Off
  88 #define rn_left         rn_u.rn_node.rn_L
  89 #define rn_right        rn_u.rn_node.rn_R
  90
  91 /*
  92  * Annotations to tree concerning potential routes applying to subtrees.
  93  */
  94
  95 struct radix_mask {
  96         short   rm_bit;                 /* bit offset; -1-index(netmask) */
  97         char    rm_unused;              /* cf. rn_bmask */
  98         uchar_t rm_flags;               /* cf. rn_flags */
  99         struct  radix_mask *rm_mklist;  /* more masks to try */
 100         union   {
 101                 caddr_t rmu_mask;               /* the mask */
 102                 struct  radix_node *rmu_leaf;   /* for normal routes */
 103         }       rm_rmu;
 104         int     rm_refs;                /* # of references to this struct */
 105 };
 106
 107 #define rm_mask rm_rmu.rmu_mask
 108 #define rm_leaf rm_rmu.rmu_leaf         /* extra field would make 32 bytes */
 109
 110 typedef int walktree_f_t(struct radix_node *, void *);
 111 typedef boolean_t match_leaf_t(struct radix_node *, void *);
 112 typedef void (*lockf_t)(struct radix_node *);
 113
 114 struct radix_node_head {
 115         struct  radix_node *rnh_treetop;
 116         int     rnh_addrsize;           /* permit, but not require fixed keys */
 117         int     rnh_pktsize;            /* permit, but not require fixed keys */
 118         struct  radix_node *(*rnh_addaddr)      /* add based on sockaddr */
 119                 (void *v, void *mask,
 120                 struct radix_node_head *head, struct radix_node nodes[]);
 121         struct  radix_node *(*rnh_addpkt)       /* add based on packet hdr */
 122                 (void *v, void *mask,
 123                     struct radix_node_head *head, struct radix_node nodes[]);
 124         struct  radix_node *(*rnh_deladdr)      /* remove based on sockaddr */
 125                 (void *v, void *mask, struct radix_node_head *head);
 126         struct  radix_node *(*rnh_delpkt)       /* remove based on packet hdr */
 127                 (void *v, void *mask, struct radix_node_head *head);
 128         struct  radix_node *(*rnh_matchaddr)    /* locate based on sockaddr */
 129                 (void *v, struct radix_node_head *head);
 130         /* rnh_matchaddr_args: locate based on sockaddr and match_leaf_t() */
 131         struct  radix_node *(*rnh_matchaddr_args)
 132                 (void *v, struct radix_node_head *head,
 133                 match_leaf_t *f, void *w);
 134         struct  radix_node *(*rnh_lookup)       /* locate based on sockaddr */
 135                 (void *v, void *mask, struct radix_node_head *head);
 136         struct  radix_node *(*rnh_matchpkt)     /* locate based on packet hdr */
 137                 (void *v, struct radix_node_head *head);
 138         int     (*rnh_walktree)                 /* traverse tree */
 139                 (struct radix_node_head *head, walktree_f_t *f, void *w);
 140         int     (*rnh_walktree_mt)                      /* traverse tree */
 141                 (struct radix_node_head *head, walktree_f_t *f, void *w,
 142                 lockf_t lockf, lockf_t unlockf);
 143         /* rn_walktree_mt: MT safe version of rn_walktree */
 144         int     (*rnh_walktree_from)            /* traverse tree below a */
 145                 (struct radix_node_head *head, void *a, void *m,
 146                     walktree_f_t *f, void *w);
 147         void    (*rnh_close)    /* do something when the last ref drops */
 148                 (struct radix_node *rn, struct radix_node_head *head);
 149         struct  radix_node rnh_nodes[3];        /* empty tree for common case */
 150 #ifdef _KERNEL
 151         krwlock_t rnh_lock;                     /* locks entire radix tree */
 152 #endif
 153 };
 154
 155 #ifdef _KERNEL
 156 /*
 157  * BSD's sockaddr_in and sockadr have a sin_len and an sa_len
 158  * field respectively, as the first field in the structure, and
 159  * everything in radix.c assumes that the first byte of the "varg"
 160  * passed in tells the length of the key (the sockaddr).
 161  *
 162  * Since Solaris' sockaddr_in and sockadr, do not have these fields, we
 163  * define a BSD4-like sockaddr_in structure with rt_sin_len field to
 164  * make LEN macro wn radix.c to work correctly for Solaris
 165  * See comments around LEN() macro in ip/radix.c
 166  * The callers of functions of radix.c have to use this data structure
 167  */
 168 struct rt_sockaddr  {
 169         uint8_t         rt_sin_len;
 170         uint8_t         rt_sin_family;
 171         uint16_t        rt_sin_port;
 172         struct in_addr  rt_sin_addr;
 173         char            rt_sin_zero[8];
 174 };
 175
 176
 177 #define R_Malloc(p, c, n)  p = kmem_cache_alloc((c),  KM_NOSLEEP)
 178 #define R_Zalloc(p, c, n) \
 179                 if (p = kmem_cache_alloc((c), KM_NOSLEEP)) {\
 180                         bzero(p, n); \
 181                 }
 182 #define R_ZallocSleep(p, t, n)  p = (t) kmem_zalloc(n, KM_SLEEP)
 183 #define Free(p, c)  kmem_cache_free(c, p)
 184 #define FreeHead(p, n)  kmem_free(p, n)
 185
 186 typedef struct radix_node rn_t;
 187 typedef struct radix_mask rmsk_t;
 188 typedef struct radix_node_head rnh_t;
 189 typedef struct rt_sockaddr rt_sa_t;
 190
 191 #define RADIX_NODE_HEAD_LOCK_INIT(rnh)  \
 192         rw_init(&(rnh)->rnh_lock, NULL, RW_DEFAULT, NULL)
 193 #define RADIX_NODE_HEAD_RLOCK(rnh)      rw_enter(&(rnh)->rnh_lock, RW_READER)
 194 #define RADIX_NODE_HEAD_WLOCK(rnh)      rw_enter(&(rnh)->rnh_lock, RW_WRITER)
 195 #define RADIX_NODE_HEAD_UNLOCK(rnh)     rw_exit(&(rnh)->rnh_lock)
 196 #define RADIX_NODE_HEAD_DESTROY(rnh)    rw_destroy(&(rnh)->rnh_lock)
 197 #define RADIX_NODE_HEAD_LOCK_ASSERT(rnh) RW_WRITE_HELD(&(rnh)->rnh_lock)
 198
 199 #else /* _KERNEL */
 200
 201 #define R_Malloc(p, t, n) (p =  malloc((unsigned int)(n)))
 202 #define R_Zalloc(p, t, n) (p =  calloc(1, (unsigned int)(n)))
 203 #define R_ZallocSleep(p, t, n) R_Zalloc(p, t, n)
 204 #define Free(p, c) free((char *)p); /* c is ignored */
 205 #ifndef RADIX_NODE_HEAD_RLOCK
 206 #define RADIX_NODE_HEAD_RLOCK(x)        /* */
 207 #endif
 208 #ifndef RADIX_NODE_HEAD_WLOCK
 209 #define RADIX_NODE_HEAD_WLOCK(x)        /* */
 210 #endif
 211 #ifndef RADIX_NODE_HEAD_UNLOCK
 212 #define RADIX_NODE_HEAD_UNLOCK(x)       /* */
 213 #endif
 214
 215 #endif /* _KERNEL */
 216
 217 #ifndef min
 218 #define min MIN
 219 #endif
 220 #ifndef max
 221 #define max MAX
 222 #endif
 223
 224 void    rn_init(void);
 225 void    rn_fini(void);
 226 int     rn_inithead(void **, int);
 227 int     rn_freenode(struct radix_node *, void *);
 228 void    rn_freehead(struct radix_node_head *);
 229
 230 #ifdef  __cplusplus
 231 }
 232 #endif
 233
 234 #endif /* _RADIX_H_ */