src/trie.c

   1 /*
   2  * netsniff-ng - the packet sniffing beast
   3  * By Daniel Borkmann <daniel@netsniff-ng.org>
   4  * Copyright 2011 Daniel Borkmann.
   5  * Subject to the GPL, version 2.
   6  */
   7
   8 #include <stdint.h>
   9 #include <string.h>
  10 #include <netinet/in.h>
  11 #include <asm/byteorder.h>
  12
  13 #include "patricia.h"
  14 #include "locking.h"
  15 #include "trie.h"
  16 #include "ipv4.h"
  17
  18 struct ipv6hdr {
  19 #if defined(__LITTLE_ENDIAN_BITFIELD)
  20         __extension__ uint8_t priority:4,
  21                               version:4;
  22 #elif defined(__BIG_ENDIAN_BITFIELD)
  23         __extension__ uint8_t version:4,
  24                               priority:4;
  25 #else
  26 # error "Please fix <asm/byteorder.h>"
  27 #endif
  28         uint8_t flow_lbl[3];
  29         uint16_t payload_len;
  30         uint8_t nexthdr;
  31         uint8_t hop_limit;
  32         struct in6_addr saddr;
  33         struct in6_addr daddr;
  34 } __attribute__((packed));
  35
  36 static struct patricia_node *tree = NULL;
  37
  38 static struct rwlock tree_lock;
  39
  40 void trie_addr_lookup(char *buff, size_t len, int ipv4, int *fd,
  41                       struct sockaddr_storage *addr, size_t *alen)
  42 {
  43         void *data;
  44         size_t dlen;
  45         struct ipv4hdr *hdr4 = (void *) buff;
  46         struct ipv6hdr *hdr6 = (void *) buff;
  47
  48         data = ipv4 ? (void *) &hdr4->h_daddr : (void *) &hdr6->daddr;
  49         dlen = ipv4 ? sizeof(hdr4->h_daddr) : sizeof(hdr6->daddr);
  50
  51         if (unlikely((ipv4 && ((struct ipv4hdr *) buff)->h_version != 4) ||
  52                      (!ipv4 && ((struct ipv6hdr *) buff)->version  != 6))) {
  53                 memset(addr, 0, sizeof(*addr));
  54                 (*alen) = 0;
  55                 (*fd) = -1;
  56                 return;
  57         }
  58
  59         /* Always happens on the dst address */
  60         rwlock_rd_lock(&tree_lock);
  61         (*fd) = ptree_search_data_exact(data, dlen, addr, alen, tree);
  62         rwlock_unlock(&tree_lock);
  63 }
  64
  65 int trie_addr_maybe_update(char *buff, size_t len, int ipv4, int fd,
  66                            struct sockaddr_storage *addr, size_t alen)
  67 {
  68         int ret;
  69         void *data;
  70         size_t dlen;
  71         struct ipv4hdr *hdr4 = (void *) buff;
  72         struct ipv6hdr *hdr6 = (void *) buff;
  73
  74         data = ipv4 ? (void *) &hdr4->h_saddr : (void *) &hdr6->saddr;
  75         dlen = ipv4 ? sizeof(hdr4->h_saddr) : sizeof(hdr6->saddr);
  76
  77         if (unlikely((ipv4 && ((struct ipv4hdr *) buff)->h_version != 4) ||
  78                      (!ipv4 && ((struct ipv6hdr *) buff)->version  != 6)))
  79                 return -1;
  80
  81         /* Always happens on the src address */
  82         rwlock_wr_lock(&tree_lock);
  83         ret = ptree_maybe_add_entry(data, dlen, fd, addr, alen, &tree);
  84         rwlock_unlock(&tree_lock);
  85
  86         return ret;
  87 }
  88
  89 void trie_addr_remove(int fd)
  90 {
  91         int found = 1;
  92         struct patricia_node *n = NULL;
  93
  94         rwlock_wr_lock(&tree_lock);
  95
  96         while (found) {
  97                 ptree_get_key(fd, tree, &n);
  98                 if (n) {
  99                         ptree_del_entry(n->key, n->klen, &tree);
 100                         n = NULL;
 101                 } else
 102                         found = 0;
 103         }
 104
 105         rwlock_unlock(&tree_lock);
 106 }
 107
 108 void trie_addr_remove_addr(struct sockaddr_storage *addr, size_t alen)
 109 {
 110         int found = 1;
 111         struct patricia_node *n = NULL;
 112
 113         rwlock_wr_lock(&tree_lock);
 114
 115         while (found) {
 116                 ptree_get_key_addr(addr, alen, tree, &n);
 117                 if (n) {
 118                         ptree_del_entry(n->key, n->klen, &tree);
 119                         n = NULL;
 120                 } else
 121                         found = 0;
 122         }
 123
 124         rwlock_unlock(&tree_lock);
 125 }
 126
 127 void trie_init(void)
 128 {
 129         rwlock_init(&tree_lock);
 130 }
 131
 132 void trie_cleanup(void)
 133 {
 134         rwlock_wr_lock(&tree_lock);
 135         ptree_free(tree);
 136         rwlock_unlock(&tree_lock);
 137
 138         rwlock_destroy(&tree_lock);
 139 }