dummynet2/ip_fw_lookup.c

   1 /*-
   2  * Copyright (c) 2009 Luigi Rizzo Universita` di Pisa
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  14  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  16  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  17  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  18  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  19  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  20  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  21  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  22  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  23  * SUCH DAMAGE.
  24  */
  25
  26 #include <sys/cdefs.h>
  27 __FBSDID("$FreeBSD: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_fw_table.c 200601 2009-12-16 10:48:40Z luigi $");
  28
  29 /*
  30  * Rule and pipe lookup support for ipfw.
  31  *
  32
  33 ipfw and dummynet need to quickly find objects (rules, pipes)
  34 that may be dynamically created or destroyed.
  35 To address the problem, we label each new object with a unique
  36 32-bit identifier whose low K bits are the index in a lookup
  37 table. All existing objects are referred by the lookup table,
  38 and identifiers are chosen so that for each slot there is
  39 at most one active object (whose identifier points to the slot).
  40 This is almost a hash table, except that we can pick the
  41 identifiers after looking at the table's occupation so
  42 we have a trivial hash function and are collision free.
  43
  44 With this structure, operations are very fast and simple:
  45 - the table has N entries s[i] with two fields, 'id' and 'ptr',
  46   with N <= M = 2^k (M is an upper bound to the size of the table);
  47 - initially, all slots have s[i].id = i, and the pointers
  48   are used to build a freelist (tailq).
  49 - a slot is considered empty if ptr == NULL or s[0] <= ptr < s[N].
  50   This is easy to detect and we can use ptr to build the freelist.
  51 - when a new object is created, we put it in the empty slot i at the
  52   head of the freelist, and set the id to s[i].id;
  53 - when an object is destroyed, we append its slot i to the end
  54   of the freelist, and set s[i].id += M (note M, not N).
  55 - on a lookup for id = X, we look at slot i = X & (M-1),
  56   and consider the lookup successful only if the slot is not
  57   empty and s[i].id == X;
  58 - wraps occur at most every F * 2^32/M operations, where F is
  59   the number of free slots. Because F is usually a reasonable
  60   fraction of M, we should not worry too much.
  61 - if the table fills up, we can extend it by increasing N
  62 - shrinking the table is more difficult as we might create
  63   collisions during the rehashing.
  64  *
  65  */
  66
  67 #include <sys/cdefs.h>
  68 #ifdef _KERNEL
  69 #include <sys/param.h>
  70 #include <sys/systm.h>
  71 #include <sys/malloc.h>
  72 #include <sys/kernel.h>
  73 #include <sys/lock.h>
  74 #include <sys/rwlock.h>
  75 MALLOC_DEFINE(M_IPFW_LUT, "ipfw_lookup", "IpFw lookup");
  76 #define Malloc(n)       malloc(n, M_IPFW_LUT, M_WAITOK)
  77 #define Calloc(n)       calloc(n, M_IPFW_LUT, M_WAITOK | M_ZERO)
  78 #define Free(p)         free(p, M_IPFW_LUT)
  79
  80 #define log(x, arg...)
  81
  82 #else /* !_KERNEL */
  83 #include <sys/types.h>
  84 #include <stdio.h>
  85 #include <stdlib.h>
  86 #include <string.h>
  87 #define Malloc(n)       malloc(n)
  88 #define Calloc(n)       calloc(1, n)
  89 #define Free(p)         free(p)
  90 #define log(x, arg...)  fprintf(stderr, "%s: " x "\n", __FUNCTION__, ##arg)
  91 #endif /* !_KERNEL */
  92
  93 struct entry {
  94         uint32_t        id;
  95         struct entry    *ptr;
  96 };
  97
  98 struct lookup_table {
  99         int _size;
 100         int used;
 101         int mask; /* 2^k -1, used for hashing */
 102         struct entry *f_head, *f_tail; /* freelist */
 103         struct entry *  s;      /* slots, array of N entries */
 104 };
 105
 106 static __inline int empty(struct lookup_table *head, const void *p)
 107 {
 108         const struct entry *ep = p;
 109         return (ep == NULL ||
 110                 (ep >= head->s && ep < &head->s[head->_size]));
 111 }
 112
 113 /*
 114  * init or reinit a table
 115  */
 116 struct lookup_table *
 117 ipfw_lut_init(struct lookup_table *head, int new_size, int mask)
 118 {
 119         int i;
 120         struct entry *s;        /* the new slots */
 121         struct entry *fh, *ft;  /* the freelist */
 122
 123         if (head != NULL) {
 124                 mask = head->mask;
 125                 if (new_size <= head->_size)
 126                         return head;
 127                 if (new_size >= mask+1) {
 128                         log("size larger than mask");
 129                         return NULL;
 130                 }
 131         } else {
 132                 log("old is null, initialize");
 133                 head = Calloc(sizeof(*head));
 134                 if (head == NULL)
 135                         return NULL;
 136                 if (new_size >= mask)
 137                         mask = new_size;
 138                 if (mask & (mask -1)) {
 139                         for (i = 1; i < mask; i += i)
 140                             ;
 141                         log("mask %d not 2^k, round up to %d", mask, i);
 142                         mask = i;
 143                 }
 144                 mask = head->mask = mask - 1;
 145         }
 146
 147         s = Calloc(new_size * sizeof(*s));
 148         if (s == NULL)
 149                 return NULL;
 150         if (!head->s) {
 151                 head->s = s;
 152                 head->_size = 1;
 153         }
 154         fh = ft = NULL;
 155         /* remap the entries, adjust the freelist */
 156         for (i = 0; i < new_size; i++) {
 157                 s[i].id = (i >= head->_size) ? i : head->s[i].id;
 158                 if (i < head->_size && !empty(head, head->s[i].ptr)) {
 159                         s[i].ptr = head->s[i].ptr;
 160                         continue;
 161                 }
 162                 if (fh == NULL)
 163                         fh = &s[i];
 164                 else
 165                         ft->ptr = &s[i];
 166                 ft = &s[i];
 167         }
 168         head->f_head = fh;
 169         head->f_tail = ft;
 170
 171         /* write lock on the structure, to protect the readers */
 172         fh = head->s;
 173         head->s = s;
 174         head->_size = new_size;
 175         /* release write lock */
 176         if (fh != s)
 177                 Free(fh);
 178         log("done");
 179         return head;
 180 }
 181
 182 /* insert returns the id */
 183 int
 184 ipfw_lut_insert(struct lookup_table *head, void *d)
 185 {
 186         struct entry *e;
 187
 188         e = head->f_head;
 189         if (e == NULL)
 190                 return -1;
 191         head->f_head = e->ptr;
 192         e->ptr = d;
 193         head->used++;
 194         return e->id;
 195 }
 196
 197 /* delete, returns the original entry */
 198 void *
 199 ipfw_lut_delete(struct lookup_table *head, int id)
 200 {
 201         int i = id & head->mask;
 202         void *result;
 203         struct entry *e;
 204
 205         if (i >= head->_size)
 206                 return NULL;
 207         e = &head->s[i];
 208         if (e->id != id)
 209                 return NULL;
 210         result = e->ptr;
 211         /* write lock to invalidate the entry to readers */
 212         e->id += head->mask + 1; /* prepare for next insert */
 213         e->ptr = NULL;
 214         /* release write lock */
 215         if (head->f_head == NULL)
 216                 head->f_head = e;
 217         else
 218                 head->f_tail->ptr = e;
 219         head->f_tail = e;
 220         head->used--;
 221         return result;
 222 }
 223
 224 void *
 225 ipfw_lut_lookup(struct lookup_table *head, int id)
 226 {
 227         int i = id & head->mask;
 228         struct entry *e;
 229
 230         if (i >= head->_size)
 231                 return NULL;
 232         e = &head->s[i];
 233         return (e->id == id) ? e->ptr : NULL;
 234 }
 235
 236 void
 237 ipfw_lut_dump(struct lookup_table *head)
 238 {
 239         int i;
 240
 241         log("head %p size %d used %d freelist %d",
 242             head, head->_size, head->used, head->f_head ?
 243                     head->f_head - head->s : -1);
 244         for (i = 0; i < head->_size; i++) {
 245                 struct entry *e = &head->s[i];
 246                 char ee = empty(head, e->ptr) ? 'E' : ' ';
 247                 log("%5d  %5d %c %p", i, e->id, ee,
 248                     ee == 'E' && e->ptr != NULL ?
 249                     (void *)((struct entry *)e->ptr - head->s) : e->ptr);
 250         }
 251 }
 252
 253 #ifndef _KERNEL
 254 void dump_p(struct lookup_table *p, int *map)
 255 {
 256         int i;
 257         for (i = 0; i < p->_size; i++) {
 258             int id = (int)ipfw_lut_lookup(p, map[i]);
 259             log("%3d: %3d: %c", map[i] % 64, i, id);
 260         }
 261 }
 262 int main(int argc, char *argv[])
 263 {
 264         int i, j, l;
 265 #define S 1000
 266         int map[S];
 267         struct lookup_table *p;
 268         struct lookup_table *p1;
 269         const char *m = "nel mezzo del cammin di nostra vita mi ritrovai"
 270                 " in una selva oscura e la diritta via era smarrita!";
 271
 272         fprintf(stderr, "testing lookup\n");
 273
 274         l = strlen(m);
 275
 276         p = ipfw_lut_init(NULL, 120, 33);
 277
 278         ipfw_lut_dump(p);
 279         for (i = 0; i < l; i++) {
 280             int x = m[i];
 281             int id = ipfw_lut_insert(p, (void *)x);
 282             //ipfw_lut_dump(p);
 283             map[i] = id;
 284             for (j=0; j < 10; j++) {
 285                     id = ipfw_lut_insert(p, (void *)'a');
 286                     // ipfw_lut_dump(p);
 287                     ipfw_lut_delete(p, id);
 288                     // ipfw_lut_dump(p);
 289             }
 290         //    ipfw_lut_dump(p);
 291         }
 292         dump_p(p, map);
 293         p1 = ipfw_lut_init(p, 23, 0);
 294         if (!p1)
 295                 return 1;
 296         dump_p(p1, map);
 297         p1 = ipfw_lut_init(p1, 120, 0);
 298         if (!p1)
 299                 return 1;
 300         dump_p(p1, map);
 301         return 0;
 302 }
 303 #endif
 304 /* end of file */