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
  17 struct ipv4hdr {
  18 #if defined(__LITTLE_ENDIAN_BITFIELD)
  19         __extension__ uint8_t h_ihl:4,
  20                               h_version:4;
  21 #elif defined (__BIG_ENDIAN_BITFIELD)
  22         __extension__ uint8_t h_version:4,
  23                               h_ihl:4;
  24 #else
  25 # error "Please fix <asm/byteorder.h>"
  26 #endif
  27         uint8_t h_tos;
  28         uint16_t h_tot_len;
  29         uint16_t h_id;
  30         uint16_t h_frag_off;
  31         uint8_t h_ttl;
  32         uint8_t h_protocol;
  33         uint16_t h_check;
  34         uint32_t h_saddr;
  35         uint32_t h_daddr;
  36 } __attribute__((packed));
  37
  38 struct ipv6hdr {
  39 #if defined(__LITTLE_ENDIAN_BITFIELD)
  40         __extension__ uint8_t priority:4,
  41                               version:4;
  42 #elif defined(__BIG_ENDIAN_BITFIELD)
  43         __extension__ uint8_t version:4,
  44                               priority:4;
  45 #else
  46 # error "Please fix <asm/byteorder.h>"
  47 #endif
  48         uint8_t flow_lbl[3];
  49         uint16_t payload_len;
  50         uint8_t nexthdr;
  51         uint8_t hop_limit;
  52         struct in6_addr saddr;
  53         struct in6_addr daddr;
  54 } __attribute__((packed));
  55
  56 static struct patricia_node *tree = NULL;
  57
  58 static struct rwlock tree_lock;
  59
  60 void trie_addr_lookup(char *buff, size_t len, int ipv4, int *fd,
  61                       struct sockaddr_storage *addr, size_t *alen)
  62 {
  63         void *data;
  64         size_t dlen;
  65         struct ipv4hdr *hdr4 = (void *) buff;
  66         struct ipv6hdr *hdr6 = (void *) buff;
  67
  68         data = ipv4 ? (void *) &hdr4->h_daddr : (void *) &hdr6->daddr;
  69         dlen = ipv4 ? sizeof(hdr4->h_daddr) : sizeof(hdr6->daddr);
  70
  71         if (unlikely((ipv4 && ((struct ipv4hdr *) buff)->h_version != 4) ||
  72                      (!ipv4 && ((struct ipv6hdr *) buff)->version  != 6))) {
  73                 memset(addr, 0, sizeof(*addr));
  74                 (*alen) = 0;
  75                 (*fd) = -1;
  76                 return;
  77         }
  78
  79         /* Always happens on the dst address */
  80         rwlock_rd_lock(&tree_lock);
  81         (*fd) = ptree_search_data_exact(data, dlen, addr, alen, tree);
  82         rwlock_unlock(&tree_lock);
  83 }
  84
  85 int trie_addr_maybe_update(char *buff, size_t len, int ipv4, int fd,
  86                            struct sockaddr_storage *addr, size_t alen)
  87 {
  88         int ret;
  89         void *data;
  90         size_t dlen;
  91         struct ipv4hdr *hdr4 = (void *) buff;
  92         struct ipv6hdr *hdr6 = (void *) buff;
  93
  94         data = ipv4 ? (void *) &hdr4->h_saddr : (void *) &hdr6->saddr;
  95         dlen = ipv4 ? sizeof(hdr4->h_saddr) : sizeof(hdr6->saddr);
  96
  97         if (unlikely((ipv4 && ((struct ipv4hdr *) buff)->h_version != 4) ||
  98                      (!ipv4 && ((struct ipv6hdr *) buff)->version  != 6)))
  99                 return -1;
 100
 101         /* Always happens on the src address */
 102         rwlock_wr_lock(&tree_lock);
 103         ret = ptree_maybe_add_entry(data, dlen, fd, addr, alen, &tree);
 104         rwlock_unlock(&tree_lock);
 105
 106         return ret;
 107 }
 108
 109 void trie_addr_remove(int fd)
 110 {
 111         int found = 1;
 112         struct patricia_node *n = NULL;
 113
 114         rwlock_wr_lock(&tree_lock);
 115
 116         while (found) {
 117                 ptree_get_key(fd, tree, &n);
 118                 if (n) {
 119                         ptree_del_entry(n->key, n->klen, &tree);
 120                         n = NULL;
 121                 } else
 122                         found = 0;
 123         }
 124
 125         rwlock_unlock(&tree_lock);
 126 }
 127
 128 void trie_addr_remove_addr(struct sockaddr_storage *addr, size_t alen)
 129 {
 130         int found = 1;
 131         struct patricia_node *n = NULL;
 132
 133         rwlock_wr_lock(&tree_lock);
 134
 135         while (found) {
 136                 ptree_get_key_addr(addr, alen, tree, &n);
 137                 if (n) {
 138                         ptree_del_entry(n->key, n->klen, &tree);
 139                         n = NULL;
 140                 } else
 141                         found = 0;
 142         }
 143
 144         rwlock_unlock(&tree_lock);
 145 }
 146
 147 void trie_init(void)
 148 {
 149         rwlock_init(&tree_lock);
 150 }
 151
 152 void trie_cleanup(void)
 153 {
 154         rwlock_wr_lock(&tree_lock);
 155         ptree_free(tree);
 156         rwlock_unlock(&tree_lock);
 157
 158         rwlock_destroy(&tree_lock);
 159 }