sys/net/radix.h

   1 /*
   2  * Copyright (c) 1988, 1989, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. Neither the name of the University nor the names of its contributors
  14  *    may be used to endorse or promote products derived from this software
  15  *    without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  *
  29  *      @(#)radix.h     8.2 (Berkeley) 10/31/94
  30  * $FreeBSD: src/sys/net/radix.h,v 1.16.2.1 2000/05/03 19:17:11 wollman Exp $
  31  */
  32
  33 #ifndef _NET_RADIX_H_
  34 #define _NET_RADIX_H_
  35
  36 #include <sys/types.h>
  37
  38 /*
  39  * Radix search tree node layout.
  40  */
  41
  42 struct radix_node {
  43         struct  radix_mask *rn_mklist;  /* masks contained in subtree */
  44         struct  radix_node *rn_parent;  /* parent */
  45         int     rn_bit;         /* node: bit offset; leaf: -1-index(netmask) */
  46         u_char  rn_flags;       /* enumerated next */
  47 #define RNF_NORMAL      1       /* leaf contains normal route */
  48 #define RNF_ROOT        2       /* leaf is root node (embedded in the tree) */
  49 #define RNF_ACTIVE      4       /* node is alive (for rtfree) */
  50         union {
  51                 /* leaf-only data: */
  52                 struct {
  53                         /* object of search; point to the key passed by the
  54                          * caller */
  55                         const u_char *rn_Key;
  56                         /* optional netmask; if present, point to the rn_key
  57                          * of a node in the mask tree */
  58                         const u_char *rn_Mask;
  59                         /* chain of routes with the same key but differnt
  60                          * netmasks. */
  61                         struct  radix_node *rn_Dupedkey;
  62                 } rn_leaf;
  63                 /* node-only data: */
  64                 struct {
  65                         int     rn_Offset;      /* where to start compare */
  66                         u_char  rn_Bmask;       /* byte mask for bit test */
  67                         struct  radix_node *rn_Left; /* progeny */
  68                         struct  radix_node *rn_Right; /* progeny */
  69                 } rn_node;
  70         }       rn_u;
  71 #ifdef RN_DEBUG
  72         int rn_info;
  73         struct radix_node *rn_twin;
  74         struct radix_node *rn_ybro;
  75 #endif
  76 };
  77
  78 #define rn_dupedkey     rn_u.rn_leaf.rn_Dupedkey
  79 #define rn_key          rn_u.rn_leaf.rn_Key
  80 #define rn_mask         rn_u.rn_leaf.rn_Mask
  81 #define rn_offset       rn_u.rn_node.rn_Offset
  82 #define rn_bmask        rn_u.rn_node.rn_Bmask
  83 #define rn_left         rn_u.rn_node.rn_Left
  84 #define rn_right        rn_u.rn_node.rn_Right
  85
  86 /*
  87  * We do this statically now because the dynamic initialization
  88  * occurs too late and has an ordering problem w/ pf preloads
  89  * vs protocol domains.
  90  */
  91 #define RN_MAXKEYLEN    32
  92 #define RN_MAXKEYONES   { -1, -1, -1, -1, -1, -1, -1, -1,       \
  93                           -1, -1, -1, -1, -1, -1, -1, -1,       \
  94                           -1, -1, -1, -1, -1, -1, -1, -1,       \
  95                           -1, -1, -1, -1, -1, -1, -1, -1 }
  96
  97 /*
  98  * Annotations to tree concerning potential routes applying to subtrees.
  99  */
 100
 101 struct radix_mask {
 102         int     rm_bit;                 /* bit offset; -1-index(netmask) */
 103         char    rm_unused;
 104         u_char  rm_flags;               /* cf. rn_flags */
 105         struct  radix_mask *rm_next;    /* list of more masks to try */
 106         union   {
 107                 const u_char *rmu_mask;         /* the mask */
 108                 struct  radix_node *rmu_leaf;   /* for normal routes */
 109         }       rm_rmu;
 110         int     rm_refs;                /* # of references to this struct */
 111 };
 112
 113 #define rm_mask rm_rmu.rmu_mask
 114 #define rm_leaf rm_rmu.rmu_leaf
 115
 116 typedef int walktree_f_t (struct radix_node *, void *);
 117 typedef void freenode_f_t (struct radix_node *);
 118
 119 struct radix_node_head {
 120         struct  radix_node *rnh_treetop;
 121
 122         /* add based on sockaddr */
 123         struct  radix_node *(*rnh_addaddr)
 124                     (const void *key, const void *mask,
 125                      struct radix_node_head *head, struct radix_node nodes[]);
 126
 127         /* remove based on sockaddr */
 128         struct  radix_node *(*rnh_deladdr)
 129                     (const void *key, const void *mask,
 130                      struct radix_node_head *head);
 131
 132         /* locate based on sockaddr */
 133         struct  radix_node *(*rnh_matchaddr)
 134                     (const void *key, struct radix_node_head *head);
 135
 136         /* locate based on sockaddr */
 137         struct  radix_node *(*rnh_lookup)
 138                     (const void *key, const void *mask,
 139                      struct radix_node_head *head);
 140
 141         /* traverse tree */
 142         int     (*rnh_walktree)
 143                     (struct radix_node_head *head, walktree_f_t *f, void *w);
 144
 145         /* traverse tree below a */
 146         int     (*rnh_walktree_from)
 147                     (struct radix_node_head *head, const void *addr,
 148                      const void *mask, walktree_f_t *f, void *w);
 149
 150         /*
 151          * Do something when the last ref drops.
 152          * A (*rnh_close)() routine
 153          *      can clear RTF_UP
 154          *      can remove a route from the radix tree
 155          *      cannot change the reference count
 156          *      cannot deallocate the route
 157          */
 158         void    (*rnh_close)
 159                     (struct radix_node *rn, struct radix_node_head *head);
 160
 161         /*
 162          * Embedded nodes (flagged with RNF_ROOT) for an empty tree:
 163          * - left node
 164          * - top/root node (pointed by rnh_treetop)
 165          * - right node
 166          */
 167         struct  radix_node rnh_nodes[3];
 168
 169         /* unused entries */
 170         int     rnh_addrsize;           /* permit, but not require fixed keys */
 171         int     rnh_pktsize;            /* permit, but not require fixed keys */
 172         struct  radix_node *(*rnh_addpkt)       /* add based on packet hdr */
 173                     (const void *v, const void *mask,
 174                      struct radix_node_head *head, struct radix_node nodes[]);
 175         struct  radix_node *(*rnh_delpkt)       /* remove based on packet hdr */
 176                     (const void *v, const void *mask,
 177                      struct radix_node_head *head);
 178
 179         /* traverse tree starting from a */
 180         int     (*rnh_walktree_at)
 181                     (struct radix_node_head *head, const void *addr,
 182                      const void *mask, walktree_f_t *f, void *w);
 183
 184         struct radix_node_head *rnh_maskhead;
 185 };
 186
 187 #ifdef _KERNEL
 188
 189 #ifdef MALLOC_DECLARE
 190 MALLOC_DECLARE(M_RTABLE);
 191 #endif
 192
 193 #define R_Malloc(p, t, n) \
 194         (p = (t) kmalloc((n), M_RTABLE, M_INTWAIT | M_NULLOK))
 195 #define R_Free(p)       kfree(p, M_RTABLE)
 196
 197 #else /* !_KERNEL */
 198
 199 #include <stdbool.h>
 200
 201 #define R_Malloc(p, t, n)       (p = (t) malloc((n)))
 202 #define R_Free(p)               free(p)
 203
 204 #endif /* _KERNEL */
 205
 206 void                     rn_init(void);
 207 int                      rn_inithead(struct radix_node_head **head,
 208                                      struct radix_node_head *maskhead,
 209                                      int off_bytes);
 210 void                     rn_freehead(struct radix_node_head *head);
 211 void                     rn_flush(struct radix_node_head *head,
 212                                   freenode_f_t *f);
 213 void                     rn_freemask(struct radix_node *rn);
 214 struct radix_node_head  *rn_cpumaskhead(int cpu);
 215 bool                     rn_refines(const void *m, const void *n);
 216 struct radix_node       *rn_addmask(const void *mask, bool search, int skip,
 217                                     struct radix_node_head *maskhead);
 218 struct radix_node       *rn_addroute(const void *key, const void *mask,
 219                                      struct radix_node_head *head,
 220                                      struct radix_node nodes[2]);
 221 struct radix_node       *rn_delete(const void *key, const void *mask,
 222                                    struct radix_node_head *head);
 223 struct radix_node       *rn_lookup(const void *key, const void *mask,
 224                                    struct radix_node_head *head);
 225 struct radix_node       *rn_match(const void *key,
 226                                   struct radix_node_head *head);
 227
 228 #endif /* _NET_RADIX_H_ */