/*- * Copyright (c) 2009 Luigi Rizzo Universita` di Pisa * * 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. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. */ #include __FBSDID("$FreeBSD: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_fw_table.c 200601 2009-12-16 10:48:40Z luigi $"); /* * Rule and pipe lookup support for ipfw. * ipfw and dummynet need to quickly find objects (rules, pipes) that may be dynamically created or destroyed. To address the problem, we label each new object with a unique 32-bit identifier whose low K bits are the index in a lookup table. All existing objects are referred by the lookup table, and identifiers are chosen so that for each slot there is at most one active object (whose identifier points to the slot). This is almost a hash table, except that we can pick the identifiers after looking at the table's occupation so we have a trivial hash function and are collision free. With this structure, operations are very fast and simple: - the table has N entries s[i] with two fields, 'id' and 'ptr', with N <= M = 2^k (M is an upper bound to the size of the table); - initially, all slots have s[i].id = i, and the pointers are used to build a freelist (tailq). - a slot is considered empty if ptr == NULL or s[0] <= ptr < s[N]. This is easy to detect and we can use ptr to build the freelist. - when a new object is created, we put it in the empty slot i at the head of the freelist, and set the id to s[i].id; - when an object is destroyed, we append its slot i to the end of the freelist, and set s[i].id += M (note M, not N). - on a lookup for id = X, we look at slot i = X & (M-1), and consider the lookup successful only if the slot is not empty and s[i].id == X; - wraps occur at most every F * 2^32/M operations, where F is the number of free slots. Because F is usually a reasonable fraction of M, we should not worry too much. - if the table fills up, we can extend it by increasing N - shrinking the table is more difficult as we might create collisions during the rehashing. * */ #include #ifdef _KERNEL #include #include #include #include #include #include MALLOC_DEFINE(M_IPFW_LUT, "ipfw_lookup", "IpFw lookup"); #define Malloc(n) malloc(n, M_IPFW_LUT, M_WAITOK) #define Calloc(n) calloc(n, M_IPFW_LUT, M_WAITOK | M_ZERO) #define Free(p) free(p, M_IPFW_LUT) #define log(x, arg...) #else /* !_KERNEL */ #include #include #include #include #define Malloc(n) malloc(n) #define Calloc(n) calloc(1, n) #define Free(p) free(p) #define log(x, arg...) fprintf(stderr, "%s: " x "\n", __FUNCTION__, ##arg) #endif /* !_KERNEL */ struct entry { uint32_t id; struct entry *ptr; }; struct lookup_table { int _size; int used; int mask; /* 2^k -1, used for hashing */ struct entry *f_head, *f_tail; /* freelist */ struct entry * s; /* slots, array of N entries */ }; static __inline int empty(struct lookup_table *head, const void *p) { const struct entry *ep = p; return (ep == NULL || (ep >= head->s && ep < &head->s[head->_size])); } /* * init or reinit a table */ struct lookup_table * ipfw_lut_init(struct lookup_table *head, int new_size, int mask) { int i; struct entry *s; /* the new slots */ struct entry *fh, *ft; /* the freelist */ if (head != NULL) { mask = head->mask; if (new_size <= head->_size) return head; if (new_size >= mask+1) { log("size larger than mask"); return NULL; } } else { log("old is null, initialize"); head = Calloc(sizeof(*head)); if (head == NULL) return NULL; if (new_size >= mask) mask = new_size; if (mask & (mask -1)) { for (i = 1; i < mask; i += i) ; log("mask %d not 2^k, round up to %d", mask, i); mask = i; } mask = head->mask = mask - 1; } s = Calloc(new_size * sizeof(*s)); if (s == NULL) return NULL; if (!head->s) { head->s = s; head->_size = 1; } fh = ft = NULL; /* remap the entries, adjust the freelist */ for (i = 0; i < new_size; i++) { s[i].id = (i >= head->_size) ? i : head->s[i].id; if (i < head->_size && !empty(head, head->s[i].ptr)) { s[i].ptr = head->s[i].ptr; continue; } if (fh == NULL) fh = &s[i]; else ft->ptr = &s[i]; ft = &s[i]; } head->f_head = fh; head->f_tail = ft; /* write lock on the structure, to protect the readers */ fh = head->s; head->s = s; head->_size = new_size; /* release write lock */ if (fh != s) Free(fh); log("done"); return head; } /* insert returns the id */ int ipfw_lut_insert(struct lookup_table *head, void *d) { struct entry *e; e = head->f_head; if (e == NULL) return -1; head->f_head = e->ptr; e->ptr = d; head->used++; return e->id; } /* delete, returns the original entry */ void * ipfw_lut_delete(struct lookup_table *head, int id) { int i = id & head->mask; void *result; struct entry *e; if (i >= head->_size) return NULL; e = &head->s[i]; if (e->id != id) return NULL; result = e->ptr; /* write lock to invalidate the entry to readers */ e->id += head->mask + 1; /* prepare for next insert */ e->ptr = NULL; /* release write lock */ if (head->f_head == NULL) head->f_head = e; else head->f_tail->ptr = e; head->f_tail = e; head->used--; return result; } void * ipfw_lut_lookup(struct lookup_table *head, int id) { int i = id & head->mask; struct entry *e; if (i >= head->_size) return NULL; e = &head->s[i]; return (e->id == id) ? e->ptr : NULL; } void ipfw_lut_dump(struct lookup_table *head) { int i; log("head %p size %d used %d freelist %d", head, head->_size, head->used, head->f_head ? head->f_head - head->s : -1); for (i = 0; i < head->_size; i++) { struct entry *e = &head->s[i]; char ee = empty(head, e->ptr) ? 'E' : ' '; log("%5d %5d %c %p", i, e->id, ee, ee == 'E' && e->ptr != NULL ? (void *)((struct entry *)e->ptr - head->s) : e->ptr); } } #ifndef _KERNEL void dump_p(struct lookup_table *p, int *map) { int i; for (i = 0; i < p->_size; i++) { int id = (int)ipfw_lut_lookup(p, map[i]); log("%3d: %3d: %c", map[i] % 64, i, id); } } int main(int argc, char *argv[]) { int i, j, l; #define S 1000 int map[S]; struct lookup_table *p; struct lookup_table *p1; const char *m = "nel mezzo del cammin di nostra vita mi ritrovai" " in una selva oscura e la diritta via era smarrita!"; fprintf(stderr, "testing lookup\n"); l = strlen(m); p = ipfw_lut_init(NULL, 120, 33); ipfw_lut_dump(p); for (i = 0; i < l; i++) { int x = m[i]; int id = ipfw_lut_insert(p, (void *)x); //ipfw_lut_dump(p); map[i] = id; for (j=0; j < 10; j++) { id = ipfw_lut_insert(p, (void *)'a'); // ipfw_lut_dump(p); ipfw_lut_delete(p, id); // ipfw_lut_dump(p); } // ipfw_lut_dump(p); } dump_p(p, map); p1 = ipfw_lut_init(p, 23, 0); if (!p1) return 1; dump_p(p1, map); p1 = ipfw_lut_init(p1, 120, 0); if (!p1) return 1; dump_p(p1, map); return 0; } #endif /* end of file */