patricia.c

   1 /*
   2  * netsniff-ng - the packet sniffing beast
   3  * By Daniel Borkmann <daniel@netsniff-ng.org>
   4  * Copyright 2011 Daniel Borkmann, rewritten
   5  * Copyright 1991-2007 Kawahara Lab., Kyoto University
   6  * Copyright 2000-2005 Shikano Lab., Nara Institute of Science and Technology
   7  * Copyright 2005-2007 Julius project team, Nagoya Institute of Technology
   8  * All rights reserved
   9  * Subject to the GPL, version 2.
  10  */
  11
  12 #include <stdio.h>
  13 #include <string.h>
  14 #include <errno.h>
  15
  16 #include "patricia.h"
  17 #include "built_in.h"
  18 #include "xmalloc.h"
  19
  20 static const unsigned char mbit[] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
  21
  22 static inline int testbit(char *str, size_t slen, int bitplace)
  23 {
  24         int maskptr;
  25
  26         if ((maskptr = bitplace >> 3) > slen)
  27                 return 0;
  28
  29         return (str[maskptr] & mbit[bitplace & 7]);
  30 }
  31
  32 static inline int testbit_max(char *str, int bitplace, int maxbitplace)
  33 {
  34         if (bitplace >= maxbitplace)
  35                 return 0;
  36
  37         return (str[bitplace >> 3] & mbit[bitplace & 7]);
  38 }
  39
  40 static int where_the_bit_differ(char *str1, size_t l1, char *str2, size_t l2)
  41 {
  42         int p = 0, bitloc;
  43
  44         while (str1[p] == str2[p])
  45                 p++;
  46
  47         bitloc = p * 8;
  48
  49         while (testbit(str1, l1, bitloc) == testbit(str2, l2, bitloc))
  50                 bitloc++;
  51
  52         return bitloc;
  53 }
  54
  55 static struct patricia_node *new_node(void)
  56 {
  57         struct patricia_node *n = xzmalloc(sizeof(*n));
  58
  59         n->l = n->r = NULL;
  60
  61         return n;
  62 }
  63
  64 static void free_node(struct patricia_node *n)
  65 {
  66         free(n->key);
  67         free(n->addr);
  68         xfree(n);
  69 }
  70
  71 void ptree_display(struct patricia_node *node, int level)
  72 {
  73         int i;
  74
  75         for (i = 0; i < level; ++i)
  76                 printf("-");
  77
  78         if (node->l == NULL && node->r == NULL)
  79                 printf("leaf: (%s -> %d)\n", (char *) node->key, node->value.data);
  80         else {
  81                 printf("thres: %d\n", node->value.thres_bit);
  82
  83                 if (node->l != NULL)
  84                         ptree_display(node->l, level + 1);
  85                 if (node->r != NULL)
  86                         ptree_display(node->r, level + 1);
  87         }
  88 }
  89
  90 void ptree_get_key(int data, struct patricia_node *node,
  91                    struct patricia_node **wanted)
  92 {
  93         if (!node)
  94                 return;
  95
  96         if (node->l == NULL && node->r == NULL) {
  97                 if (node->value.data == data)
  98                         (*wanted) = node;
  99         } else {
 100                 if (node->l != NULL)
 101                         ptree_get_key(data, node->l, wanted);
 102                 if (node->r != NULL)
 103                         ptree_get_key(data, node->r, wanted);
 104         }
 105 }
 106
 107 void ptree_get_key_addr(struct sockaddr_storage *addr, size_t alen,
 108                         struct patricia_node *node, struct patricia_node **wanted)
 109 {
 110         if (!node)
 111                 return;
 112
 113         if (node->l == NULL && node->r == NULL) {
 114                 if (!memcmp(node->addr, addr, node->alen))
 115                         (*wanted) = node;
 116         } else {
 117                 if (node->l != NULL)
 118                         ptree_get_key_addr(addr, alen, node->l, wanted);
 119                 if (node->r != NULL)
 120                         ptree_get_key_addr(addr, alen, node->r, wanted);
 121         }
 122 }
 123
 124 static int ptree_search_data_r(struct patricia_node *node, char *str, size_t slen,
 125                                struct sockaddr_storage *addr, size_t *alen, int maxbitplace)
 126 {
 127         if (node->l == NULL && node->r == NULL) {
 128                 if (node->addr && addr)
 129                         memcpy(addr, node->addr, node->alen);
 130
 131                 (*alen) = node->alen;
 132
 133                 return node->value.data;
 134         }
 135
 136         if (testbit_max(str, node->value.thres_bit, maxbitplace) != 0)
 137                 return ptree_search_data_r(node->r, str, slen, addr, alen, maxbitplace);
 138         else
 139                 return ptree_search_data_r(node->l, str, slen, addr, alen, maxbitplace);
 140 }
 141
 142 static int *ptree_search_data_r_p(struct patricia_node *node, char *str,
 143                                   size_t slen, int maxbitplace)
 144 {
 145         if (node->l == NULL && node->r == NULL)
 146                 return &(node->value.data);
 147
 148         if (testbit_max(str, node->value.thres_bit, maxbitplace) != 0)
 149                 return ptree_search_data_r_p(node->r, str, slen, maxbitplace);
 150         else
 151                 return ptree_search_data_r_p(node->l, str, slen, maxbitplace);
 152 }
 153
 154 static int ptree_search_data_r_x(struct patricia_node *node, char *str,
 155                                  size_t slen, struct sockaddr_storage *addr,
 156                                  size_t *alen, int maxbitplace)
 157 {
 158         if (node->l == NULL && node->r == NULL) {
 159                 if (node->klen == slen && !memcmp(str, node->key, node->klen)) {
 160                         if (node->addr && addr)
 161                                 memcpy(addr, node->addr, node->alen);
 162
 163                         (*alen) = node->alen;
 164
 165                         return node->value.data;
 166                 } else
 167                         return -ENOENT;
 168         }
 169
 170         if (testbit_max(str, node->value.thres_bit, maxbitplace) != 0)
 171                 return ptree_search_data_r_x(node->r, str, slen, addr, alen, maxbitplace);
 172         else
 173                 return ptree_search_data_r_x(node->l, str, slen, addr, alen, maxbitplace);
 174 }
 175
 176 int ptree_search_data_nearest(void *str, size_t sstr, struct sockaddr_storage *addr,
 177                               size_t *alen, struct patricia_node *root)
 178 {
 179         if (!root)
 180                 return -ENOENT;
 181
 182         return ptree_search_data_r(root, str, sstr, addr, alen, sstr * 8);
 183 }
 184
 185 static int *ptree_search_data_nearest_ptr(char *str, size_t sstr,
 186                                           struct patricia_node *root)
 187 {
 188         return ptree_search_data_r_p(root, str, sstr, sstr * 8);
 189 }
 190
 191 int ptree_search_data_exact(void *str, size_t sstr, struct sockaddr_storage *addr,
 192                             size_t *alen, struct patricia_node *root)
 193 {
 194         if (!root)
 195                 return -ENOENT;
 196
 197         return ptree_search_data_r_x(root, str, sstr, addr, alen, sstr * 8);
 198 }
 199
 200 static struct patricia_node *ptree_make_root_node(char *str, size_t sstr,
 201                                                   int data, struct sockaddr_storage *addr,
 202                                                   size_t alen)
 203 {
 204         struct patricia_node *n = new_node();
 205
 206         n->value.data = data;
 207         n->key = xmemdupz(str, sstr);
 208         n->klen = sstr;
 209         if (addr)
 210                 n->addr = xmemdupz(addr, alen);
 211         else
 212                 n->addr = NULL;
 213         n->alen = alen;
 214
 215         return n;
 216 }
 217
 218 static void ptree_add_entry_at(char *str, size_t slen, int bitloc, int data,
 219                                struct sockaddr_storage *addr, size_t alen,
 220                                struct patricia_node **parentlink)
 221 {
 222         struct patricia_node *node = (*parentlink);
 223
 224         if (node->value.thres_bit > bitloc || (node->l == NULL && node->r == NULL)) {
 225                 struct patricia_node *newleaf, *newbranch;
 226
 227                 newleaf = new_node();
 228                 newleaf->value.data = data;
 229                 newleaf->key = xmemdupz(str, slen);
 230                 newleaf->klen = slen;
 231
 232                 if (addr)
 233                         newleaf->addr = xmemdupz(addr, alen);
 234                 else
 235                         newleaf->addr = NULL;
 236                 newleaf->alen = alen;
 237
 238                 newbranch = new_node();
 239                 newbranch->value.thres_bit = bitloc;
 240                 (*parentlink) = newbranch;
 241
 242                 if (testbit(str, slen, bitloc) ==0) {
 243                         newbranch->l = newleaf;
 244                         newbranch->r = node;
 245                 } else {
 246                         newbranch->l = node;
 247                         newbranch->r = newleaf;
 248                 }
 249         } else {
 250                 if (testbit(str, slen, node->value.thres_bit) != 0)
 251                         ptree_add_entry_at(str, slen, bitloc, data, addr, alen, &(node->r));
 252                 else
 253                         ptree_add_entry_at(str, slen, bitloc, data, addr, alen, &(node->l));
 254         }
 255 }
 256
 257 int ptree_add_entry(void *str, size_t sstr, int data, struct sockaddr_storage *addr,
 258                     size_t alen, struct patricia_node **root)
 259 {
 260         int *ptr, bitloc, malicious = 0;
 261         struct patricia_node *n;
 262
 263         if (!(*root))
 264                 (*root) = ptree_make_root_node(str, sstr, data, addr, alen);
 265         else {
 266                 ptr = ptree_search_data_nearest_ptr(str, sstr, (*root));
 267                 n = container_of(ptr, struct patricia_node, value.data);
 268
 269                 if (n->klen == sstr && !memcmp(str, n->key, n->klen)) {
 270                         /* Make sure if entry exists, that we also have the
 271                          * same data, otherwise, we drop the packet */
 272                         if (n->value.data != data)
 273                                 malicious = 1;
 274                         else if (n->alen != alen)
 275                                 malicious = 1;
 276                         else if ((n->addr && !addr) || (!n->addr && addr))
 277                                 malicious = 1;
 278                         else if (n->alen == alen && n->addr && addr) {
 279                                 if (memcmp(n->addr, addr, alen))
 280                                         malicious = 1;
 281                         }
 282
 283                         return malicious;
 284                 }
 285
 286                 bitloc = where_the_bit_differ(str, sstr, n->key, n->klen);
 287                 ptree_add_entry_at(str, sstr, bitloc, data, addr, alen, root);
 288         }
 289
 290         return malicious;
 291 }
 292
 293 static void ptree_remove_entry_r(struct patricia_node *now,
 294                                  struct patricia_node *up,
 295                                  struct patricia_node *up2,
 296                                  char *str, size_t slen, int maxbitplace,
 297                                  struct patricia_node **root)
 298 {
 299         struct patricia_node *b;
 300
 301         if (now->l == NULL && now->r == NULL) {
 302                 if (now->klen != slen)
 303                         return;
 304                 if (memcmp(now->key, str, slen))
 305                         return;
 306                 if (up == NULL) {
 307                         *root = NULL;
 308                         free_node(now);
 309                         return;
 310                 }
 311
 312                 b = (up->r == now) ? up->l : up->r;
 313
 314                 if (up2 == NULL) {
 315                         *root = b;
 316                         free_node(now);
 317                         free_node(up);
 318                         return;
 319                 }
 320                 if (up2->l == up)
 321                         up2->l = b;
 322                 else
 323                         up2->r = b;
 324
 325                 free_node(now);
 326                 free_node(up);
 327         } else {
 328                 if (testbit_max(str, now->value.thres_bit, maxbitplace) != 0)
 329                         ptree_remove_entry_r(now->r, now, up, str, slen, maxbitplace, root);
 330                 else
 331                         ptree_remove_entry_r(now->l, now, up, str, slen, maxbitplace, root);
 332         }
 333 }
 334
 335 void ptree_del_entry(void *str, size_t sstr, struct patricia_node **root)
 336 {
 337         if (!(*root))
 338                 return;
 339
 340         ptree_remove_entry_r(*root, NULL, NULL, str, sstr, sstr * 8, root);
 341 }
 342
 343 void ptree_free(struct patricia_node *node)
 344 {
 345         if (!node)
 346                 return;
 347
 348         if (node->l)
 349                 ptree_free(node->l);
 350         if (node->r)
 351                 ptree_free(node->r);
 352
 353         free_node(node);
 354 }