"Fossies" - the Fresh Open Source Software Archive

Member "pktstat-1.8.5/frag.c" (10 Nov 2006, 8774 Bytes) of package /linux/privat/old/pktstat-1.8.5.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    1 /*
    2  * Fragment storage.
    3  *
    4  * Fragments are stored in keyed buckets.
    5  * A packet bucket is an ordered list of unique, indexed packets,
    6  * intended for eventual reassembly into a complete packet.
    7  * It is up to the caller to free a bucket when it is
    8  * no longer needed. Very old buckets are deleted automatically.
    9  */
   10 
   11 #if HAVE_CONFIG_H
   12 # include "config.h"
   13 #endif
   14 
   15 #if STDC_HEADERS
   16 # include <stdlib.h>
   17 # include <string.h>
   18 #endif
   19 
   20 #include "compat.h"
   21 
   22 #define LIST_REMOVE(o, pfx) do {                \
   23     if ((*(o)->pfx##_prevp = (o)->pfx##_next) != NULL)  \
   24         (o)->pfx##_next->pfx##_prevp = (o)->pfx##_prevp;    \
   25     /*  (o)->pfx##_prevp = NULL; */             \
   26     /*  (o)->pfx##_next  = NULL; */             \
   27     } while (0)
   28 
   29 #define LIST_INSERT(o, headp, pfx) do {             \
   30     (o)->pfx##_prevp = (headp);             \
   31     if (((o)->pfx##_next = *(headp)) != NULL)       \
   32         (o)->pfx##_next->pfx##_prevp = &(o)->pfx##_next;    \
   33     *(headp) = (o);                     \
   34     } while (0)
   35 
   36 #define LIST_NEXT(o, pfx) ((o)->pfx##_next)
   37 #define LIST_DECL(t, pfx)   t *pfx##_next, **pfx##_prevp
   38 
   39 struct frag {
   40     u_int32_t   index, next_index;
   41     LIST_DECL(struct frag, ordered);
   42     size_t      datalen;
   43 };
   44 #define FRAG_DATA(f)    ((char *)((f)+1))
   45 
   46 struct bucket {
   47     LIST_DECL(struct bucket, hash);
   48     struct bucket   *lru_fwd, *lru_back;    
   49     struct frag *first_frag;
   50 };
   51 #define BUCKET_KEY(b)   ((char *)((b)+1))
   52 
   53 #define HASHLEN     257
   54 
   55 struct fragtab {
   56     int     keylen;
   57     int     availbuckets;
   58     struct bucket   *lru_first, *lru_last;
   59     struct bucket   *buckets[HASHLEN];
   60 };
   61 
   62 /* Prototypes */
   63 static unsigned int hash(const void *key, int keylen);
   64 static void bucket_lru_remove(struct fragtab *fragtab, struct bucket *bucket);
   65 static void bucket_lru_insert(struct fragtab *fragtab, struct bucket *bucket);
   66 static void frag_delete(struct frag *frag);
   67 static struct frag **frag_find(struct frag **fragp, u_int32_t index);
   68 static struct bucket **bucket_find(struct fragtab *fragtab, const void *key);
   69 static void bucket_create(struct fragtab *fragtab, const void *key, 
   70         struct bucket **dest);
   71 static void frag_create(struct fragtab *fragtab, const void *data,
   72     size_t datalen, u_int32_t index, u_int32_t next_index,
   73     struct frag **dest);
   74 static void bucket_delete(struct fragtab *fragtab, struct bucket *bucket);
   75 
   76 /* Compute a hash index from a key string */
   77 static unsigned int
   78 hash(key, keylen)
   79     const void *key;
   80     int keylen;
   81 {
   82     unsigned int h = 0;
   83     unsigned char *p;
   84 
   85     for (p = (unsigned char *)key; keylen; keylen--, p++)
   86         h = (h << 1) ^ *p;
   87     return h % HASHLEN;
   88 }
   89 
   90 /* Remove a bucket from the lru list */
   91 static void
   92 bucket_lru_remove(fragtab, bucket)
   93     struct fragtab *fragtab;
   94     struct bucket *bucket;
   95 {
   96 
   97     if (bucket->lru_back)
   98         bucket->lru_back->lru_fwd = bucket->lru_fwd;
   99     else
  100         fragtab->lru_first = bucket->lru_fwd;
  101     if (bucket->lru_fwd)
  102         bucket->lru_fwd->lru_back = bucket->lru_back;
  103     else
  104         fragtab->lru_last = bucket->lru_back;
  105 }
  106 
  107 /* Place a (removed) bucket at the front of the lru list */
  108 static void
  109 bucket_lru_insert(fragtab, bucket)
  110     struct fragtab *fragtab;
  111     struct bucket *bucket;
  112 {
  113     if (fragtab->lru_first) {
  114         bucket->lru_fwd = fragtab->lru_first;
  115         fragtab->lru_first->lru_back = bucket;
  116         fragtab->lru_first = bucket;
  117         bucket->lru_back = NULL;
  118     } else {
  119         fragtab->lru_first = bucket;
  120         fragtab->lru_last = bucket;
  121         bucket->lru_fwd = NULL;
  122         bucket->lru_back = NULL;
  123     }
  124 }
  125 
  126 /* Unlink and deallocate a fragment */
  127 static void
  128 frag_delete(frag)
  129     struct frag *frag;
  130 {
  131     LIST_REMOVE(frag, ordered);
  132     free(frag);
  133 }
  134 
  135 /*
  136  * Returns a pointer to where the fragment of the given index
  137  * should be.
  138  */
  139 static struct frag **
  140 frag_find(fragp, index)
  141     struct frag **fragp;
  142     u_int32_t index;
  143 {
  144     while (*fragp && (*fragp)->index < index)
  145         fragp = &LIST_NEXT(*fragp, ordered);
  146     return fragp;
  147 }
  148 
  149 /*
  150  * Searches a chain in the hashtable for the bucket with the given key.
  151  * Returns the end of the chain, if not found.
  152  */
  153 static struct bucket **
  154 bucket_find(fragtab, key)
  155     struct fragtab *fragtab;
  156     const void *key;
  157 {
  158     struct bucket **bucketp;
  159     unsigned int keyhash;
  160 
  161     keyhash = hash(key, fragtab->keylen);
  162     bucketp = &fragtab->buckets[keyhash];
  163     while (*bucketp && memcmp(BUCKET_KEY(*bucketp), key, 
  164         fragtab->keylen) != 0)
  165         bucketp = &LIST_NEXT(*bucketp, hash);
  166     return bucketp;
  167 }
  168 
  169 /* Create and insert a new bucket */
  170 static void
  171 bucket_create(fragtab, key, dest)
  172     struct fragtab *fragtab;
  173     const void *key;
  174     struct bucket **dest;
  175 {
  176     struct bucket *bucket;
  177     size_t size;
  178 
  179     size = sizeof (struct bucket) + fragtab->keylen;
  180     bucket = (struct bucket *)malloc(size);
  181     if (!bucket)
  182         errx(1, "malloc");
  183     bucket->first_frag = NULL;
  184     memcpy(BUCKET_KEY(bucket), key, fragtab->keylen);
  185 
  186     LIST_INSERT(bucket, dest, hash);
  187 
  188     bucket_lru_insert(fragtab, bucket);
  189     fragtab->availbuckets--;
  190 }
  191 
  192 /* Create and insert a new fragment. */
  193 static void
  194 frag_create(fragtab, data, datalen, index, next_index, dest)
  195     struct fragtab *fragtab;
  196     const void *data;
  197     size_t datalen;
  198     u_int32_t index, next_index;
  199     struct frag **dest;
  200 {
  201     size_t size;
  202     struct frag* frag;
  203 
  204     size = sizeof (struct fragtab) + datalen;
  205     frag = (struct frag *)malloc(size);
  206     if (!frag)
  207         errx(1, "malloc");
  208     frag->index = index;
  209     frag->next_index = next_index;
  210     frag->datalen = datalen;
  211     memcpy(FRAG_DATA(frag), data, datalen);
  212 
  213     LIST_INSERT(frag, dest, ordered);
  214 }
  215 
  216 /* Delete a bucket and all the fragments it contains */
  217 static void
  218 bucket_delete(fragtab, bucket)
  219     struct fragtab *fragtab;
  220     struct bucket *bucket;
  221 {
  222     while (bucket->first_frag)
  223         frag_delete(bucket->first_frag);
  224     bucket_lru_remove(fragtab, bucket);
  225 
  226     LIST_REMOVE(bucket, hash);
  227     free(bucket);
  228     fragtab->availbuckets++;
  229 }
  230 
  231 /*
  232  * Allocate an empty fragment table
  233  */
  234 struct fragtab *
  235 fragtab_new(keylen, maxbuckets)
  236     int keylen, maxbuckets;
  237 {
  238     struct fragtab *fragtab;
  239     int i;
  240 
  241     fragtab = (struct fragtab *)malloc(sizeof (struct fragtab));
  242     if (!fragtab)
  243         errx(1, "malloc");
  244     fragtab->keylen = keylen;
  245     fragtab->availbuckets = maxbuckets;
  246     fragtab->lru_first = NULL;
  247     fragtab->lru_last = NULL;
  248     for (i = 0; i < HASHLEN; i++)
  249         fragtab->buckets[i] = NULL;
  250     return fragtab;
  251 }
  252 
  253 /*
  254  * Put a new fragment into the right bucket. A bucket is created
  255  * if there isnt one for the fragment already. The bucket is moved
  256  * to the young end of the lru list. 
  257  */
  258 void
  259 fragtab_put(fragtab, key, data, datalen, index, next_index)
  260     struct fragtab *fragtab;
  261     const void *key;
  262     const void *data;
  263     size_t datalen;
  264     u_int32_t index, next_index;
  265 {
  266     struct bucket **bucketp, *bucket;
  267     struct frag **fragp;
  268 
  269     bucketp = bucket_find(fragtab, key);
  270     if (!*bucketp) {
  271         if (fragtab->availbuckets < 0) 
  272             bucket_delete(fragtab, fragtab->lru_last);
  273         bucket_create(fragtab, key, bucketp);
  274     } else if (fragtab->lru_first != *bucketp) {
  275         /* Move to young end of list */
  276         bucket_lru_remove(fragtab, *bucketp);
  277         bucket_lru_insert(fragtab, *bucketp);
  278     }
  279     bucket = *bucketp;
  280 
  281     fragp = frag_find(&bucket->first_frag, index);
  282     if (*fragp && (*fragp)->index == index)
  283         frag_delete(*fragp);
  284     frag_create(fragtab, data, datalen, index, next_index, fragp);
  285 }
  286 
  287 /*
  288  * Return the data associated with a fragment at the given index,
  289  * or return NULL if it doesn't exist yet.
  290  */
  291 const void *
  292 fragtab_get(fragtab, key, index, datalenp)
  293     struct fragtab *fragtab;
  294     const void *key;
  295     u_int32_t index;
  296     size_t *datalenp;
  297 {
  298     struct bucket *bucket;
  299     struct frag *frag;
  300 
  301     bucket = *bucket_find(fragtab, key);
  302     if (bucket) {
  303         frag = *frag_find(&bucket->first_frag, index);
  304         if (frag && frag->index == index) {
  305             *datalenp = frag->datalen;
  306             return FRAG_DATA(frag);
  307         }
  308     }
  309     return NULL;
  310 }
  311 
  312 /*
  313  * Delete all fragments with the given key
  314  */
  315 void
  316 fragtab_del(fragtab, key)
  317     struct fragtab *fragtab;
  318     const void *key;
  319 {
  320     struct bucket *bucket;
  321 
  322     bucket = *bucket_find(fragtab, key);
  323     if (bucket)
  324         bucket_delete(fragtab, bucket);
  325 }
  326 
  327 /*
  328  * Return true if all the fragments of the bucket exist;
  329  * ie each fragment's next_index is equal to the next fragment's index
  330  */
  331 int
  332 fragtab_check(fragtab, key, first_index, last_index)
  333     struct fragtab *fragtab;
  334     const void *key;
  335     u_int32_t first_index, last_index;
  336 {
  337     struct bucket *bucket;
  338     struct frag *frag;
  339 
  340     bucket = *bucket_find(fragtab, key);
  341     if (bucket) {
  342         frag = bucket->first_frag;
  343         if (frag && frag->index == first_index)
  344         for (; frag; frag = LIST_NEXT(frag, ordered)) {
  345             if (LIST_NEXT(frag, ordered) == NULL) {
  346             if (frag->next_index == last_index)
  347                 /* at last fragment and it is last expected index */
  348                 return 1;
  349             } else if (frag->next_index != 
  350             LIST_NEXT(frag, ordered)->index) {
  351             /* missing fragments */
  352             break;
  353             }
  354         }
  355     }
  356     return 0;
  357 }
  358 
  359 /*
  360  * Destroy all storage associated with the fragment table
  361  */
  362 void
  363 fragtab_free(fragtab)
  364     struct fragtab *fragtab;
  365 {
  366     int i;
  367 
  368     for (i = 0; i < HASHLEN; i++)
  369         while (fragtab->buckets[i])
  370         bucket_delete(fragtab, fragtab->buckets[i]);
  371     free(fragtab);
  372 }