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
9 * Subject to the GPL, version 2.
20 static const unsigned char mbit
[] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
22 static inline int testbit(char *str
, size_t slen
, int bitplace
)
26 if ((maskptr
= bitplace
>> 3) > slen
)
29 return (str
[maskptr
] & mbit
[bitplace
& 7]);
32 static inline int testbit_max(char *str
, int bitplace
, int maxbitplace
)
34 if (bitplace
>= maxbitplace
)
37 return (str
[bitplace
>> 3] & mbit
[bitplace
& 7]);
40 static int where_the_bit_differ(char *str1
, size_t l1
, char *str2
, size_t l2
)
44 while (str1
[p
] == str2
[p
])
49 while (testbit(str1
, l1
, bitloc
) == testbit(str2
, l2
, bitloc
))
55 static struct patricia_node
*new_node(void)
57 struct patricia_node
*n
= xzmalloc(sizeof(*n
));
64 static void free_node(struct patricia_node
*n
)
71 void ptree_display(struct patricia_node
*node
, int level
)
75 for (i
= 0; i
< level
; ++i
)
78 if (node
->l
== NULL
&& node
->r
== NULL
)
79 printf("leaf: (%s -> %d)\n", (char *) node
->key
, node
->value
.data
);
81 printf("thres: %d\n", node
->value
.thres_bit
);
84 ptree_display(node
->l
, level
+ 1);
86 ptree_display(node
->r
, level
+ 1);
90 void ptree_get_key(int data
, struct patricia_node
*node
,
91 struct patricia_node
**wanted
)
96 if (node
->l
== NULL
&& node
->r
== NULL
) {
97 if (node
->value
.data
== data
)
101 ptree_get_key(data
, node
->l
, wanted
);
103 ptree_get_key(data
, node
->r
, wanted
);
107 void ptree_get_key_addr(struct sockaddr_storage
*addr
, size_t alen
,
108 struct patricia_node
*node
, struct patricia_node
**wanted
)
113 if (node
->l
== NULL
&& node
->r
== NULL
) {
114 if (!memcmp(node
->addr
, addr
, node
->alen
))
118 ptree_get_key_addr(addr
, alen
, node
->l
, wanted
);
120 ptree_get_key_addr(addr
, alen
, node
->r
, wanted
);
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
)
127 if (node
->l
== NULL
&& node
->r
== NULL
) {
128 if (node
->addr
&& addr
)
129 memcpy(addr
, node
->addr
, node
->alen
);
131 (*alen
) = node
->alen
;
133 return node
->value
.data
;
136 if (testbit_max(str
, node
->value
.thres_bit
, maxbitplace
) != 0)
137 return ptree_search_data_r(node
->r
, str
, slen
, addr
, alen
, maxbitplace
);
139 return ptree_search_data_r(node
->l
, str
, slen
, addr
, alen
, maxbitplace
);
142 static int *ptree_search_data_r_p(struct patricia_node
*node
, char *str
,
143 size_t slen
, int maxbitplace
)
145 if (node
->l
== NULL
&& node
->r
== NULL
)
146 return &(node
->value
.data
);
148 if (testbit_max(str
, node
->value
.thres_bit
, maxbitplace
) != 0)
149 return ptree_search_data_r_p(node
->r
, str
, slen
, maxbitplace
);
151 return ptree_search_data_r_p(node
->l
, str
, slen
, maxbitplace
);
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
)
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
);
163 (*alen
) = node
->alen
;
165 return node
->value
.data
;
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
);
173 return ptree_search_data_r_x(node
->l
, str
, slen
, addr
, alen
, maxbitplace
);
176 int ptree_search_data_nearest(void *str
, size_t sstr
, struct sockaddr_storage
*addr
,
177 size_t *alen
, struct patricia_node
*root
)
182 return ptree_search_data_r(root
, str
, sstr
, addr
, alen
, sstr
* 8);
185 static int *ptree_search_data_nearest_ptr(char *str
, size_t sstr
,
186 struct patricia_node
*root
)
188 return ptree_search_data_r_p(root
, str
, sstr
, sstr
* 8);
191 int ptree_search_data_exact(void *str
, size_t sstr
, struct sockaddr_storage
*addr
,
192 size_t *alen
, struct patricia_node
*root
)
197 return ptree_search_data_r_x(root
, str
, sstr
, addr
, alen
, sstr
* 8);
200 static struct patricia_node
*ptree_make_root_node(char *str
, size_t sstr
,
201 int data
, struct sockaddr_storage
*addr
,
204 struct patricia_node
*n
= new_node();
206 n
->value
.data
= data
;
207 n
->key
= xmemdupz(str
, sstr
);
210 n
->addr
= xmemdupz(addr
, alen
);
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
)
222 struct patricia_node
*node
= (*parentlink
);
224 if (node
->value
.thres_bit
> bitloc
|| (node
->l
== NULL
&& node
->r
== NULL
)) {
225 struct patricia_node
*newleaf
, *newbranch
;
227 newleaf
= new_node();
228 newleaf
->value
.data
= data
;
229 newleaf
->key
= xmemdupz(str
, slen
);
230 newleaf
->klen
= slen
;
233 newleaf
->addr
= xmemdupz(addr
, alen
);
235 newleaf
->addr
= NULL
;
236 newleaf
->alen
= alen
;
238 newbranch
= new_node();
239 newbranch
->value
.thres_bit
= bitloc
;
240 (*parentlink
) = newbranch
;
242 if (testbit(str
, slen
, bitloc
) ==0) {
243 newbranch
->l
= newleaf
;
247 newbranch
->r
= newleaf
;
250 if (testbit(str
, slen
, node
->value
.thres_bit
) != 0)
251 ptree_add_entry_at(str
, slen
, bitloc
, data
, addr
, alen
, &(node
->r
));
253 ptree_add_entry_at(str
, slen
, bitloc
, data
, addr
, alen
, &(node
->l
));
257 int ptree_add_entry(void *str
, size_t sstr
, int data
, struct sockaddr_storage
*addr
,
258 size_t alen
, struct patricia_node
**root
)
260 int *ptr
, bitloc
, malicious
= 0;
261 struct patricia_node
*n
;
264 (*root
) = ptree_make_root_node(str
, sstr
, data
, addr
, alen
);
266 ptr
= ptree_search_data_nearest_ptr(str
, sstr
, (*root
));
267 n
= container_of(ptr
, struct patricia_node
, value
.data
);
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
)
274 else if (n
->alen
!= alen
)
276 else if ((n
->addr
&& !addr
) || (!n
->addr
&& addr
))
278 else if (n
->alen
== alen
&& n
->addr
&& addr
) {
279 if (memcmp(n
->addr
, addr
, alen
))
286 bitloc
= where_the_bit_differ(str
, sstr
, n
->key
, n
->klen
);
287 ptree_add_entry_at(str
, sstr
, bitloc
, data
, addr
, alen
, root
);
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
)
299 struct patricia_node
*b
;
301 if (now
->l
== NULL
&& now
->r
== NULL
) {
302 if (now
->klen
!= slen
)
304 if (memcmp(now
->key
, str
, slen
))
312 b
= (up
->r
== now
) ? up
->l
: up
->r
;
328 if (testbit_max(str
, now
->value
.thres_bit
, maxbitplace
) != 0)
329 ptree_remove_entry_r(now
->r
, now
, up
, str
, slen
, maxbitplace
, root
);
331 ptree_remove_entry_r(now
->l
, now
, up
, str
, slen
, maxbitplace
, root
);
335 void ptree_del_entry(void *str
, size_t sstr
, struct patricia_node
**root
)
340 ptree_remove_entry_r(*root
, NULL
, NULL
, str
, sstr
, sstr
* 8, root
);
343 void ptree_free(struct patricia_node
*node
)