1 /*
2 ** Copyright (C) 2004-2020 by Carnegie Mellon University.
3 **
4 ** @OPENSOURCE_LICENSE_START@
5 ** See license information in ../../LICENSE.txt
6 ** @OPENSOURCE_LICENSE_END@
7 */
8
9 /*
10 * skbag.c
11 *
12 * Implementation of skbag according to skbag.h
13 *
14 */
15
16 #include <silk/silk.h>
17
18 RCSIDENT("$SiLK: skbag.c ef14e54179be 2020-04-14 21:57:45Z mthomas $");
19
20 #include <silk/redblack.h>
21 #include <silk/skbag.h>
22 #include <silk/skipaddr.h>
23 #include <silk/skmempool.h>
24 #include <silk/skstream.h>
25 #include <silk/utils.h>
26 #include "skheader_priv.h"
27
28
29 /*
30 * BAG FILE FORMAT NOTES
31 *
32 * All Bag files have a file format of FT_RWBAG (0x21).
33 *
34 * The initial record version number for Bag files was 1. These
35 * files have a 32-bit key and a 32-bit counter. These were the
36 * default rwbag output files prior to SiLK 0.8.0.
37 *
38 * Bag file record version 2 was introduced at SiLK 0.8.0. These
39 * files use a 32-bit key and a 64-bit counter. Files in this
40 * format may not use compression.
41 *
42 * A bug with compressed files introduced at SiLK 0.10.0 was fixed
43 * in SiLK 0.10.5 by bumping the version number of every SiLK file
44 * that supports compression, and all Bag files began to be written
45 * using record version 3.
46 *
47 * SiLK 3.0.0 introduced Bag file record version 4. These files
48 * support an arbitrary key size. The key and counter sizes for a
49 * file are specified in a Bag Header Entry (id = 6). The header
50 * entry also contains the type of the key and counter.
51 *
52 * For compatibility with SiLK 2.x, this library writes a version 3
53 * file unless the key contains IPv6 addresses. The library writes
54 * a header entry to these files, but SiLK 2.x ignores it.
55 *
56 */
57
58
59 /* LOCAL DEFINES AND TYPEDEFS */
60
61 /*
62 * Version number to write into the Bag's header.
63 *
64 * _COUNTER32 uses a 32-key and a 32-bit counter.
65 *
66 * _NO_COMPR uses a 32-key, a 64-bit counter, and the data section
67 * may not be compressed.
68 *
69 * _KEY_FIXED is identical to _COUNTER64 but may be compressed.
70 *
71 * _KEY_VARIES allows for variable key and value sizes.
72 */
73 #define RWBAG_FILE_VERS_COUNTER32 1
74 #define RWBAG_FILE_VERS_NO_COMPR 2
75 #define RWBAG_FILE_VERS_KEY_FIXED 3
76 #define RWBAG_FILE_VERS_KEY_VARIES 4
77
78
79 /* Whether to use memcpy() */
80 #ifndef SKBAG_USE_MEMCPY
81 #ifdef SK_HAVE_ALIGNED_ACCESS_REQUIRED
82 #define SKBAG_USE_MEMCPY 1
83 #else
84 #define SKBAG_USE_MEMCPY 0
85 #endif
86 #endif
87
88
89 /* Maximum number of octets allowed for keys and counters */
90 #define BAG_KEY_MAX_OCTETS 16
91 #define BAG_COUNTER_MAX_OCTETS 8
92
93
94 #if !SK_ENABLE_IPV6
95
96 /*
97 * BAG_KEY_TO_U32_V4(key, value)
98 *
99 * Given the skBagTypedKey_t 'key', fill 'value' with a uint32_t
100 * representation of that value.
101 */
102 #define BAG_KEY_TO_U32_V4(k2int_key, k2int_u32) \
103 switch ((k2int_key)->type) { \
104 case SKBAG_KEY_U8: \
105 k2int_u32 = (k2int_key)->val.u8; \
106 break; \
107 case SKBAG_KEY_U16: \
108 k2int_u32 = (k2int_key)->val.u16; \
109 break; \
110 case SKBAG_KEY_U32: \
111 k2int_u32 = (k2int_key)->val.u32; \
112 break; \
113 case SKBAG_KEY_IPADDR: \
114 k2int_u32 = skipaddrGetV4(&(k2int_key)->val.addr); \
115 break; \
116 default: \
117 skAbortBadCase((k2int_key)->type); \
118 }
119
120 #else /* #if !SK_ENABLE_IPV6 */
121
122 /*
123 * BAG_KEY_TO_U32_V6(key, value, is_v6)
124 *
125 * Given the skBagTypedKey_t 'key', fill 'value' with a uint32_t
126 * representation of that value. If 'key' contains an IPv6 address
127 * that is not an IPv4-encoded value, set 'is_v6' to 1. If 'value'
128 * can store the key, set is_v6 is 0.
129 */
130 #define BAG_KEY_TO_U32_V6(k2int_key, k2int_u32, k2int_isv6) \
131 switch ((k2int_key)->type) { \
132 case SKBAG_KEY_U8: \
133 k2int_isv6 = 0; \
134 k2int_u32 = (k2int_key)->val.u8; \
135 break; \
136 case SKBAG_KEY_U16: \
137 k2int_isv6 = 0; \
138 k2int_u32 = (k2int_key)->val.u16; \
139 break; \
140 case SKBAG_KEY_U32: \
141 k2int_isv6 = 0; \
142 k2int_u32 = (k2int_key)->val.u32; \
143 break; \
144 case SKBAG_KEY_IPADDR: \
145 k2int_isv6 = skipaddrGetAsV4(&(k2int_key)->val.addr, &(k2int_u32)); \
146 break; \
147 default: \
148 skAbortBadCase((k2int_key)->type); \
149 }
150
151 /*
152 * BAG_KEY_TO_IPV6(key, ipv6_array)
153 *
154 * Given the skBagTypedKey_t 'key', fill 'ipv6_array' with the
155 * byte-array representation of that value as an IPv6 address,
156 * where any integer value is written an an IPv4-encoded-IPv6
157 * address.
158 */
159 #define BAG_KEY_TO_IPV6(k2ip_key, k2ip_array) \
160 switch ((k2ip_key)->type) { \
161 case SKBAG_KEY_U8: \
162 memcpy((k2ip_array), bag_v4inv6, 15); \
163 k2ip_array[15] = key->val.u8; \
164 break; \
165 case SKBAG_KEY_U16: \
166 memcpy((k2ip_array), bag_v4inv6, 14); \
167 *(uint16_t*)(k2ip_array + 14) = htons(key->val.u16); \
168 break; \
169 case SKBAG_KEY_U32: \
170 memcpy((k2ip_array), bag_v4inv6, 12); \
171 *(uint32_t*)(k2ip_array + 12) = htonl(key->val.u32); \
172 break; \
173 case SKBAG_KEY_IPADDR: \
174 skipaddrGetAsV6(&(k2ip_key)->val.addr, k2ip_array); \
175 break; \
176 default: \
177 skAbortBadCase((k2ip_key)->type); \
178 }
179
180 #endif /* else if #if !SK_ENABLE_IPV6 */
181
182
183 /*
184 * BAG_CHECK_INPUT(bag, key, counter);
185 *
186 * Verify that 'bag', 'key', and 'counter' are not NULL, that the
187 * types of the skBagTypedKey_t 'key' and skBagTypedCounter_t
188 * 'counter' are valid for input (that is, are not ANY), and that
189 * the value of 'counter' is not bag_counter_invalid.
190 *
191 * Causes the function to return SKBAG_ERR_INPUT if any of those
192 * tests fail.
193 */
194 #define BAG_CHECK_INPUT(bci_bag, bci_key, bci_counter) \
195 if (NULL == bci_bag || NULL == bci_key || NULL == bci_counter \
196 || SKBAG_KEY_ANY == bci_key->type \
197 || SKBAG_COUNTER_ANY == bci_counter->type \
198 || bag_counter_invalid == bci_counter->val.u64) \
199 { \
200 return SKBAG_ERR_INPUT; \
201 }
202
203
204 /*
205 * BAG_COUNTER_SET(counter, value);
206 *
207 * Set 'counter', a pointer to an skBagTypedCounter_t, to 'value'.
208 * Note that 'value' is NOT a pointer.
209 */
210 #define BAG_COUNTER_SET(bcs_counter, bcs_value) \
211 { \
212 (bcs_counter)->type = SKBAG_COUNTER_U64; \
213 (bcs_counter)->val.u64 = (uint64_t)(bcs_value); \
214 }
215
216
217 /*
218 * BAG_COUNTER_SET_ZERO(counter);
219 *
220 * Set 'counter', a pointer to an skBagTypedCounter_t, to 0.
221 */
222 #define BAG_COUNTER_SET_ZERO(bcsz_counter) \
223 BAG_COUNTER_SET(bcsz_counter, 0)
224
225
226 /*
227 * BAG_COUNTER_IS_ZERO(counter);
228 *
229 * Return TRUE if 'counter' is the NULL counter.
230 */
231 #define BAG_COUNTER_IS_ZERO(cin_counter) \
232 (SKBAG_COUNTER_MIN == (cin_counter))
233
234
235 /*
236 * BAG_MEMCPY_COUNTER(dest, src);
237 *
238 * Set the counter pointer 'dest' to the value stored in the
239 * counter pointer 'src'.
240 */
241 #if SKBAG_USE_MEMCPY
242 #define BAG_MEMCPY_COUNTER(cc_counter_ptr, cc_value_ptr) \
243 memcpy((cc_counter_ptr), (cc_value_ptr), sizeof(uint64_t))
244 #else
245 #define BAG_MEMCPY_COUNTER(cc_counter_ptr, cc_value_ptr) \
246 (*(uint64_t*)(cc_counter_ptr) = *(uint64_t*)(cc_value_ptr))
247 #endif
248
249
250 /*
251 * BagTree
252 *
253 * The data structure used to store uint32_t keys has an array of
254 * nodes pointing to arrays of nodes that eventually point to an
255 * array of counters.
256 */
257
258 /* The number of initial entries to create in the memory pool.
259 * Nodes: 256 * (1 << 8) * sizeof(void*) ==> 524,288 bytes
260 * Counters: 256 * (1 << 8) * sizeof(uint64_t) ==> 524,288 bytes
261 */
262 #define BAGTREE_MEMPOOL_SIZE 0x100
263
264 /* The number of bits of the key in use at this 'level' */
265 #define BAGTREE_GET_LEVEL_BITS(gls_bag, gls_level) 8
266
267 /* The bit-offset into key at this 'level' */
268 #define BAGTREE_GET_LEVEL_OFFSET(glo_bag, glo_level) \
269 (((glo_bag)->levels - 1 - (glo_level)) \
270 * BAGTREE_GET_LEVEL_BITS(glo_bag, glo_level))
271
272 /* The number of nodes/leaves at this 'level' */
273 #define BAGTREE_GET_LEVEL_BLOCKS(glb_bag, glb_level) \
274 (1u << BAGTREE_GET_LEVEL_BITS(glo_bag, glo_level))
275
276 /* The portion of 'key' in-use at this 'level'; used to index into
277 * arrays of nodes and counters. */
278 #define BAGTREE_GET_KEY_BITS(gkb_key, gkb_bag, gkb_level) \
279 GET_MASKED_BITS((gkb_key), \
280 BAGTREE_GET_LEVEL_OFFSET((gkb_bag), (gkb_level)), \
281 BAGTREE_GET_LEVEL_BITS((gkb_bag), (gkb_level)))
282
283 /* nodes in the tree are pointers to arrays of other nodes or to
284 * arrays of counters */
285 typedef union bagtree_node_un bagtree_node_t;
286 union bagtree_node_un {
287 bagtree_node_t *child;
288 uint64_t *leaf;
289 };
290
291 /* this is the 'b_tree' element in skBag_st */
292 typedef struct bagtree_st {
293 sk_mempool_t *nodes;
294
295 /* similar to the 'nodes' member, but for counters */
296 sk_mempool_t *counters;
297
298 /* the root of the tree; this points to either a node block or a
299 * counter block */
300 bagtree_node_t root;
301
302 /* the number of levels in the tree */
303 uint32_t levels;
304 } bagtree_t;
305
306
307 /*
308 * Red Black Tree
309 *
310 * For IPv6 entries, the data is stored in a red-black tree.
311 *
312 * The data element of each node of the red-black tree is a
313 * bag_keycount128_t object that holds the IPv6 address and the
314 * 64bit counter.
315 *
316 * The bag_keycount128_t objects are stored in an sk_mempool_t.
317 * This allows us to allocate them in chunks, and it also makes for
318 * faster shut-down since we can deallocate them quickly.
319 *
320 */
321
322 /* Number of elements to allocate at one time in the mempool.
323 * 131,072 * sizeof(bag_keycount128_t) ==> 3,145,728 bytes */
324 #define BAG_REDBLACK_MEMPOOL_SIZE 0x80000
325
326 /* This is the node that is stored in the redblack tree for IPv6
327 * keys. */
328 typedef struct bag_keycount128_st {
329 uint8_t key[16];
330 uint64_t counter;
331 } bag_keycount128_t;
332
333 /* this is the 'b_rbt' element in skBag_st */
334 typedef struct bag_redblack_st {
335 /* the red-black tree */
336 struct rbtree *tree;
337
338 /* pool of 'bag_keycount128_t'. these are the data elements of
339 * the nodes in the red-black tree. */
340 sk_mempool_t *datum;
341 } bag_redblack_t;
342
343
344 /* whether to determine min/max when computing statistics. there is
345 * little need to do this in the library, since rwbagcat is the only
346 * tool that cares, and it computes that information independently. */
347 #define BAG_STATS_FIND_MIN_MAX 0
348
349 /* Definition of stats */
350 typedef struct bagstats_st {
351 /* count of internal nodes allocated */
352 uint64_t nodes;
353 /* number of bytes allocated to nodes */
354 uint64_t nodes_size;
355 /* count of entries inserted in the tree */
356 uint64_t unique_keys;
357 #if BAG_STATS_FIND_MIN_MAX
358 /* minimum (non-zero) counter value */
359 uint64_t min_counter;
360 /* maximum counter value */
361 uint64_t max_counter;
362 /* minimum key inserted */
363 uint64_t min_key;
364 /* maximum key inserted */
365 uint64_t max_key;
366 skipaddr_t min_ipkey;
367 skipaddr_t max_ipkey;
368 #endif /* 0 */
369 } bagstats_t;
370
371
372 /* The SiLK Bag */
373 struct skBag_st {
374 union data_un {
375 /* a tree of nodes and counters */
376 bagtree_t *b_tree;
377
378 #if SK_ENABLE_IPV6
379 /* a struct holding a red-black tree of key/counter pairs and
380 * a memory pool for the key/counter pairs */
381 bag_redblack_t *b_rbt;
382 #endif /* SK_ENABLE_IPV6 */
383 } d;
384
385 /* number of octets that make up the key */
386 uint16_t key_octets;
387
388 /* type of key and value */
389 skBagFieldType_t key_type;
390 skBagFieldType_t counter_type;
391
392 /* whether autoconversion is allowed */
393 uint8_t no_autoconvert;
394 };
395 /* typedef struct skBag_st skBag_t; // bagtree.h */
396
397
398 /* Definition of the iterator structure */
399 struct skBagIterator_st {
400 /* pointer to the bag to which this iterator was created */
401 const skBag_t *bag;
402 /* when working with a sorted keys, the number of keys and the
403 * current position in that list */
404 uint32_t pos;
405 uint32_t num_entries;
406
407 /* number of octets that made up the bag's key when the iterator
408 * was created. */
409 uint16_t key_octets;
410
411 unsigned sorted :1;
412
413 union iter_body_un {
414 #if SK_ENABLE_IPV6
415 struct iter_body_redblack_st {
416 /* read one element ahead so we can delete the current
417 * node */
418 RBLIST *rb_iter;
419 const bag_keycount128_t *next;
420 } i_rbt;
421 #endif /* SK_ENABLE_IPV6 */
422 struct iter_body_bagtree_st {
423 /* start searching for next entry using this key value */
424 uint32_t key;
425 /* stop iterating when key is this value */
426 uint32_t max_key;
427 unsigned no_more_entries :1;
428 } i_tree;
429 } d;
430 };
431 /* typedef struct skBagIterator_st skBagIterator_t; // bagtree.h */
432
433
434 /* operations on a bag */
435 typedef enum bag_operation_en {
436 BAG_OP_GET, BAG_OP_SET, BAG_OP_ADD, BAG_OP_SUBTRACT
437 } bag_operation_t;
438
439
440 /* contains the size and name for the various SKBAG_FIELD_*
441 * values. */
442 typedef struct bag_field_info_st {
443 size_t octets;
444 const char *name;
445 } bag_field_info_t;
446
447
448 /* when writing a Bag to a stream, this header entry is used to
449 * contain information about the bag. */
450 typedef struct sk_hentry_bag_st {
451 sk_header_entry_spec_t he_spec;
452 uint16_t key_type;
453 uint16_t key_length;
454 uint16_t counter_type;
455 uint16_t counter_length;
456 } sk_hentry_bag_t;
457
458
459 /* LOCAL VARIABLES */
460
461 #if SK_ENABLE_IPV6
462 static const uint8_t bag_v4inv6[16] = {
463 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0, 0, 0, 0
464 };
465 #endif
466
467 /* ensure that SKBAG_MAX_FIELD_BUFLEN is larger than maximum name */
468 static const bag_field_info_t bag_field_info[] = {
469 { 4, "sIPv4"}, /* SKBAG_FIELD_SIPv4 */
470 { 4, "dIPv4"}, /* SKBAG_FIELD_DIPv4 */
471 { 2, "sPort"}, /* SKBAG_FIELD_SPORT */
472 { 2, "dPort"}, /* SKBAG_FIELD_DPORT */
473 { 1, "protocol"}, /* SKBAG_FIELD_PROTO */
474 { 4, "packets"}, /* SKBAG_FIELD_PACKETS */
475 { 4, "bytes"}, /* SKBAG_FIELD_BYTES */
476 { 1, "flags"}, /* SKBAG_FIELD_FLAGS */
477
478 { 4, "sTime"}, /* SKBAG_FIELD_STARTTIME */
479 { 4, "duration"}, /* SKBAG_FIELD_ELAPSED */
480 { 4, "eTime"}, /* SKBAG_FIELD_ENDTIME */
481 { 2, "sensor"}, /* SKBAG_FIELD_SID */
482 { 2, "input"}, /* SKBAG_FIELD_INPUT */
483 { 2, "output"}, /* SKBAG_FIELD_OUTPUT */
484 { 4, "nhIPv4"}, /* SKBAG_FIELD_NHIPv4 */
485 { 1, "initialFlags"}, /* SKBAG_FIELD_INIT_FLAGS */
486
487 { 1, "sessionFlags"}, /* SKBAG_FIELD_REST_FLAGS */
488 { 1, "attributes"}, /* SKBAG_FIELD_TCP_STATE */
489 { 2, "application"}, /* SKBAG_FIELD_APPLICATION */
490 { 1, "class"}, /* SKBAG_FIELD_FTYPE_CLASS */
491 { 1, "type"}, /* SKBAG_FIELD_FTYPE_TYPE */
492 { 0, "starttime-msec"}, /* SKBAG_FIELD_STARTTIME_MSEC */
493 { 0, "endtime-msec"}, /* SKBAG_FIELD_ENDTIME_MSEC */
494 { 0, "elapsed-msec"}, /* SKBAG_FIELD_ELAPSED_MSEC */
495
496 { 2, "icmpTypeCode"}, /* SKBAG_FIELD_ICMP_TYPE_CODE */
497 {16, "sIPv6"}, /* SKBAG_FIELD_SIPv6 */
498 {16, "dIPv6"}, /* SKBAG_FIELD_DIPv6 */
499 {16, "nhIPv6"}, /* SKBAG_FIELD_NHIPv6 */
500 { 8, "records"}, /* SKBAG_FIELD_RECORDS */
501 { 8, "sum-packets"}, /* SKBAG_FIELD_SUM_PACKETS */
502 { 8, "sum-bytes"}, /* SKBAG_FIELD_SUM_BYTES */
503 { 8, "sum-duration"}, /* SKBAG_FIELD_SUM_ELAPSED */
504
505 { 4, "any-IPv4"}, /* SKBAG_FIELD_ANY_IPv4 */
506 {16, "any-IPv6"}, /* SKBAG_FIELD_ANY_IPv6 */
507 { 2, "any-port"}, /* SKBAG_FIELD_ANY_PORT */
508 { 2, "any-snmp"}, /* SKBAG_FIELD_ANY_SNMP */
509 { 4, "any-time"}, /* SKBAG_FIELD_ANY_TIME */
510 { 2, "sip-country"}, /* SKBAG_FIELD_SIP_COUNTRY */
511 { 2, "dip-country"}, /* SKBAG_FIELD_DIP_COUNTRY */
512 { 2, "any-country"}, /* SKBAG_FIELD_ANY_COUNTRY */
513
514 { 4, "sip-pmap"}, /* SKBAG_FIELD_SIP_PMAP */
515 { 4, "dip-pmap"}, /* SKBAG_FIELD_DIP_PMAP */
516 { 4, "any-ip-pmap"}, /* SKBAG_FIELD_ANY_IP_PMAP */
517 { 4, "sport-pmap"}, /* SKBAG_FIELD_SPORT_PMAP */
518 { 4, "dport-pmap"}, /* SKBAG_FIELD_DPORT_PMAP */
519 { 4, "any-port-pmap"} /* SKBAG_FIELD_ANY_PORT_PMAP */
520 };
521
522 static const bag_field_info_t bag_field_info_custom = {
523 SKBAG_OCTETS_CUSTOM, "custom" /* SKBAG_FIELD_CUSTOM */
524 };
525
526 /* number of non-custom SKBAG_FIELD_* values that are defined */
527 #define BAG_NUM_FIELDS \
528 ((skBagFieldType_t)(sizeof(bag_field_info)/sizeof(bag_field_info[0])))
529
530 /*
531 * field_ptr = BAG_GET_FIELD_INFO(field_id);
532 *
533 * Set the bag_field_info_t* 'field_ptr' to the structure indexed
534 * by 'field_id'. If 'field_id' is out of range or not supported;
535 * set 'field_ptr' to NULL.
536 */
537 #define BAG_GET_FIELD_INFO(bgbf_field_id) \
538 (((bgbf_field_id) < BAG_NUM_FIELDS) \
539 ? ((0 == bag_field_info[(bgbf_field_id)].octets) \
540 ? NULL \
541 : &bag_field_info[(bgbf_field_id)]) \
542 : ((SKBAG_FIELD_CUSTOM == (bgbf_field_id)) \
543 ? &bag_field_info_custom \
544 : NULL))
545
546 static const uint64_t bag_counter_invalid = UINT64_C(1) + SKBAG_COUNTER_MAX;
547
548 static const skBagTypedCounter_t bag_counter_zero = {
549 SKBAG_COUNTER_U64, { SKBAG_COUNTER_MIN }
550 };
551 static const skBagTypedCounter_t bag_counter_incr = {
552 SKBAG_COUNTER_U64, { 1 }
553 };
554
555
556 /* EXPORTED VARIABLES */
557
558 const skBagTypedCounter_t *skbag_counter_zero = &bag_counter_zero;
559 const skBagTypedCounter_t *skbag_counter_incr = &bag_counter_incr;
560
561
562 /* FUNCTION PROTOTYPES */
563
564 static int
565 bagtreeIterNext(
566 skBagIterator_t *iter,
567 uint32_t *key,
568 uint64_t *counter);
569 #if SK_ENABLE_IPV6
570 static skBagErr_t
571 bagOperationRedblack(
572 skBag_t *bag,
573 const uint8_t ipv6[16],
574 const uint64_t change_value,
575 skBagTypedCounter_t *result_value,
576 bag_operation_t op);
577 #endif /* SK_ENABLE_IPV6 */
578 static sk_header_entry_t *
579 bagHentryCreate(
580 uint16_t key_type,
581 uint16_t key_length,
582 uint16_t counter_type,
583 uint16_t counter_length);
584
585
586 /* FUNCTION DEFINITIONS */
587
588
589 /*
590 * ok = bagCheckTypesAndSizes(key_type,counter_type,&key_octets,&counter_octets);
591 *
592 * Verify that 'key_type' and 'counter_type' are known types. In
593 * addition, verify that 'key_octets' and 'counter_octets' are
594 * valid given the 'key_type' and 'counter_type'. If the
595 * 'key_octets' or 'counter_octets' are SKBAG_OCTETS_FIELD_DEFAULT,
596 * modify them to be the size to use in the bag.
597 */
598 static skBagErr_t
bagCheckTypesAndSizes(skBagFieldType_t key_type,skBagFieldType_t counter_type,size_t * key_octets,size_t * counter_octets)599 bagCheckTypesAndSizes(
600 skBagFieldType_t key_type,
601 skBagFieldType_t counter_type,
602 size_t *key_octets,
603 size_t *counter_octets)
604 {
605 const bag_field_info_t *bf;
606 uint32_t high_bits;
607
608 /* check the key type and octets */
609 bf = BAG_GET_FIELD_INFO(key_type);
610 if (NULL == bf) {
611 return SKBAG_ERR_INPUT;
612 }
613 if (SKBAG_OCTETS_FIELD_DEFAULT == *key_octets) {
614 /* use length based on key_type */
615 if (SKBAG_OCTETS_CUSTOM == bf->octets) {
616 /* DEFAULT is not a valid size for CUSTOM */
617 return SKBAG_ERR_INPUT;
618 } else if (8 == bf->octets) {
619 /* key size of 8 is not supported, so use 4 instead */
620 *key_octets = 4;
621 } else {
622 *key_octets = bf->octets;
623 }
624 } else if ((SKBAG_OCTETS_CUSTOM == *key_octets)
625 || (SKBAG_OCTETS_NO_CHANGE == *key_octets)
626 || (SKBAG_OCTETS_UNKNOWN == *key_octets)
627 || (*key_octets == 8)
628 || (*key_octets > BAG_KEY_MAX_OCTETS))
629 {
630 return SKBAG_ERR_INPUT;
631 }
632 /* ensure it is a power of 2 */
633 BITS_IN_WORD32(&high_bits, (uint32_t)*key_octets);
634 if (high_bits != 1) {
635 return SKBAG_ERR_INPUT;
636 }
637
638 /* repeat entire process for the counter */
639 bf = BAG_GET_FIELD_INFO(counter_type);
640 if (NULL == bf) {
641 return SKBAG_ERR_INPUT;
642 }
643 if (SKBAG_OCTETS_FIELD_DEFAULT == *counter_octets) {
644 /* use length based on counter_type */
645 if (SKBAG_OCTETS_CUSTOM == bf->octets) {
646 /* DEFAULT is not a valid size for CUSTOM */
647 return SKBAG_ERR_INPUT;
648 }
649 /* always use size of 8 */
650 *counter_octets = sizeof(uint64_t);
651 #if 0
652 /* #if 0 out since counter_octets must be 8 */
653 } else if ((SKBAG_OCTETS_CUSTOM == *counter_octets)
654 || (SKBAG_OCTETS_NO_CHANGE == *counter_octets)
655 || (SKBAG_OCTETS_UNKNOWN == *counter_octets)
656 || (*counter_octets > BAG_COUNTER_MAX_OCTETS))
657 {
658 return SKBAG_ERR_INPUT;
659 #endif /* 0 */
660 } else if (sizeof(uint64_t) != *counter_octets) {
661 return SKBAG_ERR_INPUT;
662 }
663
664 return SKBAG_OK;
665 }
666
667
668 /*
669 * cmp = bagCompareKeys8(a, b)
670 * cmp = bagCompareKeys16(a, b)
671 * cmp = bagCompareKeys32(a, b)
672 * cmp = bagCompareKeys64(a, b)
673 * cmp = bagCompareKeys128(a, b)
674 *
675 * Compare the values at 'a' and 'b', where 'a' and 'b' are
676 * pointers to values having the number of bits specified in the
677 * function name.
678 */
679 #if 0
680 static int
681 bagCompareKeys8(
682 const void *v_key_a,
683 const void *v_key_b)
684 {
685 if (*(uint8_t*)v_key_a < *(uint8_t*)v_key_b) {
686 return -1;
687 }
688 return (*(uint8_t*)v_key_a > *(uint8_t*)v_key_b);
689 }
690
691 static int
692 bagCompareKeys16(
693 const void *v_key_a,
694 const void *v_key_b)
695 {
696 #if SK_BIG_ENDIAN
697 return memcmp(v_key_a, v_key_b, 2);
698 #elif SKBAG_USE_MEMCPY
699 uint16_t key_a;
700 uint16_t key_b;
701
702 memcpy(&key_a, v_key_a, sizeof(uint16_t));
703 memcpy(&key_b, v_key_b, sizeof(uint16_t));
704
705 if (key_a < key_b) {
706 return -1;
707 }
708 return (key_a > key_b);
709 #else
710 if (*(uint16_t*)v_key_a < *(uint16_t*)v_key_b) {
711 return -1;
712 }
713 return (*(uint16_t*)v_key_a > *(uint16_t*)v_key_b);
714 #endif
715 }
716
717 static int
718 bagCompareKeys32(
719 const void *v_key_a,
720 const void *v_key_b)
721 {
722 #if SK_BIG_ENDIAN
723 return memcmp(v_key_a, v_key_b, 4);
724 #elif SKBAG_USE_MEMCPY
725 uint32_t key_a;
726 uint32_t key_b;
727
728 memcpy(&key_a, v_key_a, sizeof(uint32_t));
729 memcpy(&key_b, v_key_b, sizeof(uint32_t));
730
731 if (key_a < key_b) {
732 return -1;
733 }
734 return (key_a > key_b);
735 #else
736 if (*(uint32_t*)v_key_a < *(uint32_t*)v_key_b) {
737 return -1;
738 }
739 return (*(uint32_t*)v_key_a > *(uint32_t*)v_key_b);
740 #endif
741 }
742
743 static int
744 bagCompareKeys64(
745 const void *v_key_a,
746 const void *v_key_b)
747 {
748 #if SK_BIG_ENDIAN
749 return memcmp(v_key_a, v_key_b, 8);
750 #elif SKBAG_USE_MEMCPY
751 uint64_t key_a;
752 uint64_t key_b;
753
754 memcpy(&key_a, v_key_a, sizeof(uint64_t));
755 memcpy(&key_b, v_key_b, sizeof(uint64_t));
756
757 if (key_a < key_b) {
758 return -1;
759 }
760 return (key_a > key_b);
761 #else
762 if (*(uint64_t*)v_key_a < *(uint64_t*)v_key_b) {
763 return -1;
764 }
765 return (*(uint64_t*)v_key_a > *(uint64_t*)v_key_b);
766 #endif
767 }
768 #endif /* 0 */
769
770 #if SK_ENABLE_IPV6
771 static int
bagCompareKeys128(const void * v_key_a,const void * v_key_b,const void UNUSED (* config))772 bagCompareKeys128(
773 const void *v_key_a,
774 const void *v_key_b,
775 const void UNUSED(*config))
776 {
777 return memcmp(v_key_a, v_key_b, sizeof(bag_v4inv6));
778 }
779 #endif /* SK_ENABLE_IPV6 */
780
781
782 /*
783 * bagComputeStatsRedblack(bag, stats);
784 * bagComputeStatsTree(bag, stats);
785 * bagComputeStats(bag, stats);
786 *
787 * Given the bag 'bag', update the 'stats' structure with various
788 * statistics about the bag.
789 */
790 #if SK_ENABLE_IPV6
791 static void
bagComputeStatsRedblack(const skBag_t * bag,bagstats_t * stats)792 bagComputeStatsRedblack(
793 const skBag_t *bag,
794 bagstats_t *stats)
795 {
796 RBLIST *rb_iter;
797 bag_keycount128_t *node;
798
799 rb_iter = rbopenlist(bag->d.b_rbt->tree);
800 if (NULL == rb_iter) {
801 return;
802 }
803 while ((node = (bag_keycount128_t*)rbreadlist(rb_iter)) != NULL) {
804 ++stats->unique_keys;
805 #if BAG_STATS_FIND_MIN_MAX
806 skipaddrSetV6(&key, node->key);
807 if (skipaddrCompare(&key, &stats->min_ipkey) < 0) {
808 skipaddrCopy(&stats->min_ipkey, &key);
809 }
810 if (skipaddrCopy(&key, &stats->max_ipkey) > 0) {
811 skipaddrCopy(&stats->max_ipkey, &key);
812 }
813 if (node->counter < stats->min_counter) {
814 stats->min_counter = counter;
815 }
816 if (node->counter > stats->max_counter) {
817 stats->max_counter = counter;
818 }
819 #endif /* BAG_STATS_FIND_MIN_MAX */
820 }
821 rbcloselist(rb_iter);
822
823 stats->nodes = stats->unique_keys;
824 stats->nodes_size = (stats->nodes * sizeof(bag_keycount128_t));
825 }
826 #endif /* SK_ENABLE_IPV6 */
827
828 static void
bagComputeStatsTree(const skBag_t * bag,bagstats_t * stats)829 bagComputeStatsTree(
830 const skBag_t *bag,
831 bagstats_t *stats)
832 {
833 skBagIterator_t *iter;
834 uint32_t key;
835 uint64_t counter;
836
837 if (skBagIteratorCreate(bag, &iter)) {
838 return;
839 }
840 #if BAG_STATS_FIND_MIN_MAX
841 /* get the first key */
842 if (!bagtreeIterNext(iter, &key, &counter)) {
843 /* bag is empty */
844 return;
845 }
846 ++stats->unique_keys;
847 stats->min_key = stats->max_key = key;
848 stats->min_counter = stats->max_counter = counter;
849 #endif /* BAG_STATS_FIND_MIN_MAX */
850
851 while (bagtreeIterNext(iter, &key, &counter)) {
852 ++stats->unique_keys;
853 #if BAG_STATS_FIND_MIN_MAX
854 stats->max_key = key;
855 if (counter < stats->min_counter) {
856 stats->min_counter = counter;
857 } else if (counter > stats->max_counter) {
858 stats->max_counter = counter;
859 }
860 #endif
861 }
862 skBagIteratorDestroy(iter);
863
864 #if BAG_STATS_FIND_MIN_MAX
865 skipaddrSetV4(&stats->min_ipkey, &stats->min_key);
866 skipaddrSetV4(&stats->max_ipkey, &stats->max_key);
867 #endif
868 }
869
870 static void
bagComputeStats(const skBag_t * bag,bagstats_t * stats)871 bagComputeStats(
872 const skBag_t *bag,
873 bagstats_t *stats)
874 {
875 assert(bag);
876 assert(stats);
877
878 memset(stats, 0, sizeof(bagstats_t));
879 #if BAG_STATS_FIND_MIN_MAX
880 stats->min_key = SKBAG_KEY_MAX;
881 stats->min_counter = SKBAG_COUNTER_MAX;
882 #endif
883
884 switch (bag->key_octets) {
885 case 1:
886 case 2:
887 case 4:
888 bagComputeStatsTree(bag, stats);
889 break;
890 #if SK_ENABLE_IPV6
891 case 16:
892 bagComputeStatsRedblack(bag, stats);
893 break;
894 #endif /* SK_ENABLE_IPV6 */
895 case 8:
896 default:
897 skAbortBadCase(bag->key_octets);
898 }
899 }
900
901
902 /*
903 * hentry = bagHentryCopy(hentry);
904 *
905 * Create and return a new header entry for Bag files that is a
906 * copy of the header entry 'hentry'.
907 *
908 * This is the 'copy_fn' callback for skHentryTypeRegister().
909 */
910 static sk_header_entry_t *
bagHentryCopy(const sk_header_entry_t * hentry)911 bagHentryCopy(
912 const sk_header_entry_t *hentry)
913 {
914 const sk_hentry_bag_t *bag_hdr = (sk_hentry_bag_t*)hentry;
915
916 return bagHentryCreate(bag_hdr->key_type, bag_hdr->key_length,
917 bag_hdr->counter_type, bag_hdr->counter_length);
918 }
919
920
921 /*
922 * Create and return a new header entry for Bag files. 'key_type'
923 * is the type of the key, 'key_length' is the octet length of a
924 * key, 'counter_type' is the type of the counter, 'counter_length'
925 * is the octet length of a counter.
926 */
927 static sk_header_entry_t *
bagHentryCreate(uint16_t key_type,uint16_t key_length,uint16_t counter_type,uint16_t counter_length)928 bagHentryCreate(
929 uint16_t key_type,
930 uint16_t key_length,
931 uint16_t counter_type,
932 uint16_t counter_length)
933 {
934 sk_hentry_bag_t *bag_hdr;
935
936 bag_hdr = (sk_hentry_bag_t*)calloc(1, sizeof(sk_hentry_bag_t));
937 if (NULL == bag_hdr) {
938 return NULL;
939 }
940 bag_hdr->he_spec.hes_id = SK_HENTRY_BAG_ID;
941 bag_hdr->he_spec.hes_len = sizeof(sk_hentry_bag_t);
942 bag_hdr->key_type = key_type;
943 bag_hdr->key_length = key_length;
944 bag_hdr->counter_type = counter_type;
945 bag_hdr->counter_length = counter_length;
946
947 return (sk_header_entry_t*)bag_hdr;
948 }
949
950
951 /*
952 * bagHentryFree(hentry);
953 *
954 * Release any memory that is used by the in-memory representation
955 * of the file header for Bag files.
956 *
957 * This is the 'free_fn' callback for skHentryTypeRegister().
958 */
959 static void
bagHentryFree(sk_header_entry_t * hentry)960 bagHentryFree(
961 sk_header_entry_t *hentry)
962 {
963 sk_hentry_bag_t *bag_hdr = (sk_hentry_bag_t*)hentry;
964
965 if (bag_hdr) {
966 assert(skHeaderEntryGetTypeId(bag_hdr) == SK_HENTRY_BAG_ID);
967 bag_hdr->he_spec.hes_id = UINT32_MAX;
968 free(bag_hdr);
969 }
970 }
971
972
973 #define bagHentryGetKeyType(hentry) \
974 (((sk_hentry_bag_t*)(hentry))->key_type)
975
976 #define bagHentryGetKeyLength(hentry) \
977 (((sk_hentry_bag_t*)(hentry))->key_length)
978
979 #define bagHentryGetCounterType(hentry) \
980 (((sk_hentry_bag_t*)(hentry))->counter_type)
981
982 #define bagHentryGetCounterLength(hentry) \
983 (((sk_hentry_bag_t*)(hentry))->counter_length)
984
985
986
987 /*
988 * size = bagHentryPacker(hentry, buf, bufsiz);
989 *
990 * Pack the contents of the header entry for Bag files, 'hentry'
991 * into the buffer 'buf', whose size is 'bufsiz', for writing the
992 * file to disk.
993 *
994 * This the 'pack_fn' callback for skHentryTypeRegister().
995 */
996 static ssize_t
bagHentryPacker(const sk_header_entry_t * in_hentry,uint8_t * out_packed,size_t bufsize)997 bagHentryPacker(
998 const sk_header_entry_t *in_hentry,
999 uint8_t *out_packed,
1000 size_t bufsize)
1001 {
1002 sk_hentry_bag_t *bag_hdr = (sk_hentry_bag_t*)in_hentry;
1003 sk_hentry_bag_t tmp_hdr;
1004
1005 assert(in_hentry);
1006 assert(out_packed);
1007 assert(skHeaderEntryGetTypeId(bag_hdr) == SK_HENTRY_BAG_ID);
1008
1009 if (bufsize >= sizeof(sk_hentry_bag_t)) {
1010 skHeaderEntrySpecPack(&(bag_hdr->he_spec), (uint8_t *)&tmp_hdr,
1011 sizeof(tmp_hdr));
1012 tmp_hdr.key_type = htons(bag_hdr->key_type);
1013 tmp_hdr.key_length = htons(bag_hdr->key_length);
1014 tmp_hdr.counter_type = htons(bag_hdr->counter_type);
1015 tmp_hdr.counter_length = htons(bag_hdr->counter_length);
1016
1017 memcpy(out_packed, &tmp_hdr, sizeof(sk_hentry_bag_t));
1018 }
1019
1020 return sizeof(sk_hentry_bag_t);
1021 }
1022
1023
1024 /*
1025 * bagHentryPrint(hentry, fh);
1026 *
1027 * Print a textual representation of a file's Bag header entry in
1028 * 'hentry' to the FILE pointer 'fh'.
1029 *
1030 * This is the 'print_fn' callback for skHentryTypeRegister().
1031 */
1032 static void
bagHentryPrint(const sk_header_entry_t * hentry,FILE * fh)1033 bagHentryPrint(
1034 const sk_header_entry_t *hentry,
1035 FILE *fh)
1036 {
1037 sk_hentry_bag_t *bag_hdr = (sk_hentry_bag_t*)hentry;
1038 char key_buf[64];
1039 char counter_buf[64];
1040
1041 assert(skHeaderEntryGetTypeId(bag_hdr) == SK_HENTRY_BAG_ID);
1042
1043 if (!skBagFieldTypeAsString((skBagFieldType_t)bag_hdr->key_type,
1044 key_buf, sizeof(key_buf)))
1045 {
1046 snprintf(key_buf, sizeof(key_buf), "UNKNOWN[%" PRIu16 "]",
1047 bag_hdr->key_type);
1048 }
1049 if (!skBagFieldTypeAsString((skBagFieldType_t)bag_hdr->counter_type,
1050 counter_buf, sizeof(counter_buf)))
1051 {
1052 snprintf(counter_buf, sizeof(counter_buf), "UNKNOWN[%" PRIu16 "]",
1053 bag_hdr->counter_type);
1054 }
1055
1056 fprintf(fh, ("key: %s @ %" PRIu16 " octets; "
1057 "counter: %s @ %" PRIu16 " octets"),
1058 key_buf, bag_hdr->key_length,
1059 counter_buf, bag_hdr->counter_length);
1060 }
1061
1062
1063 /*
1064 * hentry = bagHentryUnpacker(buf);
1065 *
1066 * Unpack the data in 'buf' to create an in-memory representation
1067 * of a file's Bag header entry.
1068 *
1069 * This is the 'unpack_fn' callback for skHentryTypeRegister().
1070 */
1071 static sk_header_entry_t *
bagHentryUnpacker(uint8_t * in_packed)1072 bagHentryUnpacker(
1073 uint8_t *in_packed)
1074 {
1075 sk_hentry_bag_t *bag_hdr;
1076
1077 assert(in_packed);
1078
1079 /* create space for new header */
1080 bag_hdr = (sk_hentry_bag_t*)calloc(1, sizeof(sk_hentry_bag_t));
1081 if (NULL == bag_hdr) {
1082 return NULL;
1083 }
1084
1085 /* copy the spec */
1086 skHeaderEntrySpecUnpack(&(bag_hdr->he_spec), in_packed);
1087 assert(skHeaderEntryGetTypeId(bag_hdr) == SK_HENTRY_BAG_ID);
1088
1089 /* copy the data */
1090 if (bag_hdr->he_spec.hes_len != sizeof(sk_hentry_bag_t)) {
1091 free(bag_hdr);
1092 return NULL;
1093 }
1094 memcpy(&(bag_hdr->key_type),
1095 &(in_packed[sizeof(sk_header_entry_spec_t)]),
1096 sizeof(sk_hentry_bag_t) - sizeof(sk_header_entry_spec_t));
1097 bag_hdr->key_type = htons(bag_hdr->key_type);
1098 bag_hdr->key_length = htons(bag_hdr->key_length);
1099 bag_hdr->counter_type = htons(bag_hdr->counter_type);
1100 bag_hdr->counter_length = htons(bag_hdr->counter_length);
1101
1102 return (sk_header_entry_t*)bag_hdr;
1103 }
1104
1105
1106 /*
1107 * err = bagIterCreate(bag, iter, sorted);
1108 *
1109 * Helper function for skBagIteratorCreate() and
1110 * skBagIteratorCreateUnsorted(). Create a new iterator for 'bag'.
1111 */
1112 static skBagErr_t
bagIterCreate(const skBag_t * bag,skBagIterator_t ** iter,int sorted)1113 bagIterCreate(
1114 const skBag_t *bag,
1115 skBagIterator_t **iter,
1116 int sorted)
1117 {
1118 skBagErr_t rv;
1119
1120 /* check inputs */
1121 if (NULL == bag || NULL == iter) {
1122 return SKBAG_ERR_INPUT;
1123 }
1124
1125 /* allocate iterator */
1126 *iter = (skBagIterator_t*)calloc(1, sizeof(skBagIterator_t));
1127 if (NULL == *iter) {
1128 return SKBAG_ERR_MEMORY;
1129 }
1130
1131 (*iter)->bag = bag;
1132 (*iter)->key_octets = bag->key_octets;
1133 (*iter)->sorted = (sorted ? 1 : 0);
1134 rv = skBagIteratorReset(*iter);
1135 if (SKBAG_OK != rv) {
1136 skBagIteratorDestroy(*iter);
1137 *iter = NULL;
1138 }
1139 return rv;
1140 }
1141
1142
1143 /*
1144 * err = bagIterNextRedblack(iter, key, counter)
1145 * err = bagIterNextTree(iter, key, counter)
1146 *
1147 * Helper functions for skBagIteratorNext().
1148 *
1149 * Move 'iter' to the next value in the data structure and fill
1150 * 'key' and 'counter' with that value. Return SKBAG_OK on
1151 * success, or SKBAG_ERR_KEY_NOT_FOUND when the iterator has
1152 * visited all entries.
1153 */
1154 #if SK_ENABLE_IPV6
1155 static skBagErr_t
bagIterNextRedblack(skBagIterator_t * iter,skBagTypedKey_t * key,skBagTypedCounter_t * counter)1156 bagIterNextRedblack(
1157 skBagIterator_t *iter,
1158 skBagTypedKey_t *key,
1159 skBagTypedCounter_t *counter)
1160 {
1161 const bag_keycount128_t *node;
1162
1163 node = iter->d.i_rbt.next;
1164 if (NULL == node) {
1165 return SKBAG_ERR_KEY_NOT_FOUND;
1166 }
1167 iter->d.i_rbt.next
1168 = (const bag_keycount128_t*)rbreadlist(iter->d.i_rbt.rb_iter);
1169
1170 /* found an entry to return to user---assuming the key can hold an
1171 * ipaddr */
1172 switch (key->type) {
1173 case SKBAG_KEY_ANY:
1174 key->type = SKBAG_KEY_IPADDR;
1175 /* FALLTHROUGH */
1176
1177 case SKBAG_KEY_IPADDR:
1178 skipaddrSetV6(&key->val.addr, node->key);
1179 BAG_COUNTER_SET(counter, node->counter);
1180 return SKBAG_OK;
1181
1182 case SKBAG_KEY_U8:
1183 if (0 == memcmp(node->key, bag_v4inv6, 15)) {
1184 key->val.u8 = node->key[15];
1185 BAG_COUNTER_SET(counter, node->counter);
1186 return SKBAG_OK;
1187 }
1188 break;
1189
1190 case SKBAG_KEY_U16:
1191 if (0 == memcmp(node->key, bag_v4inv6, 14)) {
1192 #if SKBAG_USE_MEMCPY
1193 memcpy(&key->val.u16, &node->key[14], sizeof(uint16_t));
1194 key->val.u16 = ntohs(key->val.u16);
1195 #else
1196 key->val.u16 = ntohs(*(uint16_t*)&node->key[14]);
1197 #endif
1198 BAG_COUNTER_SET(counter, node->counter);
1199 return SKBAG_OK;
1200 }
1201 break;
1202
1203 case SKBAG_KEY_U32:
1204 if (0 == memcmp(node->key, bag_v4inv6, 12)) {
1205 #if SKBAG_USE_MEMCPY
1206 memcpy(&key->val.u32, &node->key[12], sizeof(uint32_t));
1207 key->val.u32 = ntohl(key->val.u32);
1208 #else
1209 key->val.u32 = ntohl(*(uint32_t*)&node->key[12]);
1210 #endif
1211 BAG_COUNTER_SET(counter, node->counter);
1212 return SKBAG_OK;
1213 }
1214 break;
1215 }
1216
1217 return SKBAG_ERR_KEY_NOT_FOUND;
1218 }
1219 #endif /* SK_ENABLE_IPV6 */
1220
1221 static skBagErr_t
bagIterNextTree(skBagIterator_t * iter,skBagTypedKey_t * key,skBagTypedCounter_t * counter)1222 bagIterNextTree(
1223 skBagIterator_t *iter,
1224 skBagTypedKey_t *key,
1225 skBagTypedCounter_t *counter)
1226 {
1227 uint32_t int_key;
1228 uint64_t int_counter;
1229
1230 if (!bagtreeIterNext(iter, &int_key, &int_counter)) {
1231 return SKBAG_ERR_KEY_NOT_FOUND;
1232 }
1233
1234 BAG_COUNTER_SET(counter, int_counter);
1235
1236 switch (key->type) {
1237 case SKBAG_KEY_U8:
1238 if (int_key > UINT8_MAX) {
1239 iter->d.i_tree.no_more_entries = 1;
1240 return SKBAG_ERR_KEY_NOT_FOUND;
1241 }
1242 key->val.u8 = (uint8_t)int_key;
1243 break;
1244
1245 case SKBAG_KEY_U16:
1246 if (int_key > UINT16_MAX) {
1247 iter->d.i_tree.no_more_entries = 1;
1248 return SKBAG_ERR_KEY_NOT_FOUND;
1249 }
1250 key->val.u16 = (uint16_t)int_key;
1251 break;
1252
1253 case SKBAG_KEY_ANY:
1254 key->type = SKBAG_KEY_U32;
1255 /* FALLTHROUGH */
1256
1257 case SKBAG_KEY_U32:
1258 key->val.u32 = int_key;
1259 break;
1260
1261 case SKBAG_KEY_IPADDR:
1262 skipaddrSetV4(&key->val.addr, &int_key);
1263 break;
1264 }
1265
1266 return SKBAG_OK;
1267 }
1268
1269
1270 /*
1271 * err = bagIterResetRedblack(iter)
1272 * err = bagIterResetTree(iter)
1273 *
1274 * Reset the iterator depending on what type of data structure the
1275 * bag contains.
1276 */
1277 #if SK_ENABLE_IPV6
1278 static skBagErr_t
bagIterResetRedblack(skBagIterator_t * iter)1279 bagIterResetRedblack(
1280 skBagIterator_t *iter)
1281 {
1282 iter->d.i_rbt.rb_iter = rbopenlist(iter->bag->d.b_rbt->tree);
1283 if (NULL == iter->d.i_rbt.rb_iter) {
1284 return SKBAG_ERR_MEMORY;
1285 }
1286 iter->d.i_rbt.next
1287 = (const bag_keycount128_t*)rbreadlist(iter->d.i_rbt.rb_iter);
1288 return SKBAG_OK;
1289 }
1290 #endif /* SK_ENABLE_IPV6 */
1291
1292 static skBagErr_t
bagIterResetTree(skBagIterator_t * iter)1293 bagIterResetTree(
1294 skBagIterator_t *iter)
1295 {
1296 iter->d.i_tree.key = 0;
1297 iter->d.i_tree.max_key = (UINT32_MAX
1298 >> (CHAR_BIT * (4 - iter->bag->key_octets)));
1299 iter->d.i_tree.no_more_entries = 0;
1300
1301 return SKBAG_OK;
1302 }
1303
1304
1305 /*
1306 * err = bagOperationRedblack(bag, key, counter, result, op)
1307 * err = bagOperationTree(bag, key, counter, result, op)
1308 *
1309 * Perform the operation 'op' on the counter at 'key' in 'bag'.
1310 *
1311 * If 'op' is GET, 'result' is set to the current counter. The
1312 * parameter 'counter' is ignored.
1313 *
1314 * If 'op' is SET, the counter is set to the value 'counter'. The
1315 * parameter 'result' is ignored.
1316 *
1317 * If 'op' is ADD or SUBTRACT, 'counter' is the value by which to
1318 * modify the current counter. In addition, if 'result' is
1319 * specified, it is set to the new value.
1320 */
1321 #if SK_ENABLE_IPV6
1322 static skBagErr_t
bagOperationRedblack(skBag_t * bag,const uint8_t ipv6[16],const uint64_t change_value,skBagTypedCounter_t * result_value,bag_operation_t op)1323 bagOperationRedblack(
1324 skBag_t *bag,
1325 const uint8_t ipv6[16],
1326 const uint64_t change_value,
1327 skBagTypedCounter_t *result_value,
1328 bag_operation_t op)
1329 {
1330 bag_redblack_t *brb;
1331 bag_keycount128_t *node = NULL;
1332 bag_keycount128_t wanted;
1333
1334 brb = bag->d.b_rbt;
1335
1336 memcpy(wanted.key, ipv6, sizeof(wanted.key));
1337
1338 /* check whether the value exists */
1339 node = (bag_keycount128_t*)rbfind(&wanted, brb->tree);
1340 if (node) {
1341 /* found it in the redblack tree */
1342 switch (op) {
1343 case BAG_OP_GET:
1344 BAG_COUNTER_SET(result_value, node->counter);
1345 break;
1346
1347 case BAG_OP_SET:
1348 if (BAG_COUNTER_IS_ZERO(change_value)) {
1349 rbdelete(node, brb->tree);
1350 skMemPoolElementFree(brb->datum, node);
1351 } else {
1352 node->counter = change_value;
1353 }
1354 break;
1355
1356 case BAG_OP_SUBTRACT:
1357 if (node->counter < change_value) {
1358 /* would underflow; return error */
1359 return SKBAG_ERR_OP_BOUNDS;
1360 }
1361 if (node->counter == change_value) {
1362 rbdelete(node, brb->tree);
1363 skMemPoolElementFree(brb->datum, node);
1364 if (result_value) {
1365 BAG_COUNTER_SET_ZERO(result_value);
1366 }
1367 } else {
1368 node->counter -= change_value;
1369 if (result_value) {
1370 BAG_COUNTER_SET(result_value, node->counter);
1371 }
1372 }
1373 break;
1374
1375 case BAG_OP_ADD:
1376 /* check whether (*counter + change_value > SKBAG_COUNTER_MAX) */
1377 if (node->counter > (SKBAG_COUNTER_MAX - change_value)) {
1378 /* would overflow, return error */
1379 return SKBAG_ERR_OP_BOUNDS;
1380 }
1381 node->counter += change_value;
1382 if (result_value) {
1383 BAG_COUNTER_SET(result_value, node->counter);
1384 }
1385 break;
1386 }
1387 } else {
1388 /* key was not found in the redblack tree */
1389 switch (op) {
1390 case BAG_OP_GET:
1391 BAG_COUNTER_SET_ZERO(result_value);
1392 break;
1393
1394 case BAG_OP_ADD:
1395 case BAG_OP_SET:
1396 if (BAG_COUNTER_IS_ZERO(change_value)) {
1397 /* nothing to do */
1398 if (result_value) {
1399 BAG_COUNTER_SET_ZERO(result_value);
1400 }
1401 break;
1402 }
1403 node = (bag_keycount128_t*)skMemPoolElementNew(brb->datum);
1404 if (NULL == node) {
1405 return SKBAG_ERR_MEMORY;
1406 }
1407 memcpy(node->key, ipv6, sizeof(node->key));
1408 node->counter = change_value;
1409 if (NULL == rbsearch(node, brb->tree)) {
1410 return SKBAG_ERR_MEMORY;
1411 }
1412 if (result_value) {
1413 BAG_COUNTER_SET(result_value, change_value);
1414 }
1415 break;
1416
1417 case BAG_OP_SUBTRACT:
1418 if (!BAG_COUNTER_IS_ZERO(change_value)) {
1419 /* would underflow; return error */
1420 return SKBAG_ERR_OP_BOUNDS;
1421 }
1422 if (result_value) {
1423 BAG_COUNTER_SET_ZERO(result_value);
1424 }
1425 break;
1426 }
1427 }
1428
1429 return SKBAG_OK;
1430 }
1431 #endif /* SK_ENABLE_IPV6 */
1432
1433 static skBagErr_t
bagOperationTree(skBag_t * bag,const uint32_t key,const uint64_t change_value,skBagTypedCounter_t * result_value,bag_operation_t op)1434 bagOperationTree(
1435 skBag_t *bag,
1436 const uint32_t key,
1437 const uint64_t change_value,
1438 skBagTypedCounter_t *result_value,
1439 bag_operation_t op)
1440 {
1441 bagtree_t *bt;
1442 bagtree_node_t *subtree;
1443 uint32_t lvl;
1444 uint32_t key_bits;
1445
1446 bt = bag->d.b_tree;
1447 subtree = &bt->root;
1448
1449 if (BAG_OP_GET == op || BAG_OP_SUBTRACT == op
1450 || BAG_COUNTER_IS_ZERO(change_value))
1451 {
1452 /* trace down to the counter, but do not allocate anything */
1453 for (lvl = 0; lvl < bt->levels - 1; ++lvl) {
1454 if (!subtree->child) {
1455 /* not found */
1456 if (BAG_OP_SUBTRACT == op
1457 && !BAG_COUNTER_IS_ZERO(change_value))
1458 {
1459 return SKBAG_ERR_OP_BOUNDS;
1460 }
1461 if (result_value) {
1462 BAG_COUNTER_SET_ZERO(result_value);
1463 }
1464 return SKBAG_OK;
1465 }
1466 key_bits = BAGTREE_GET_KEY_BITS(key, bt, lvl);
1467 subtree = &(subtree->child[key_bits]);
1468 }
1469 /* we are currently on the last node level, our child should
1470 * be a leaf */
1471 if (!subtree->leaf) {
1472 /* not found */
1473 if (BAG_OP_SUBTRACT == op
1474 && !BAG_COUNTER_IS_ZERO(change_value))
1475 {
1476 return SKBAG_ERR_OP_BOUNDS;
1477 }
1478 if (result_value) {
1479 BAG_COUNTER_SET_ZERO(result_value);
1480 }
1481 return SKBAG_OK;
1482 }
1483 /* key was in the tree */
1484 key_bits = BAGTREE_GET_KEY_BITS(key, bt, lvl);
1485 switch (op) {
1486 case BAG_OP_SET:
1487 subtree->leaf[key_bits] = change_value;
1488 break;
1489 case BAG_OP_GET:
1490 case BAG_OP_ADD:
1491 break;
1492 case BAG_OP_SUBTRACT:
1493 if (subtree->leaf[key_bits] < change_value) {
1494 /* would underflow, return error */
1495 return SKBAG_ERR_OP_BOUNDS;
1496 }
1497 subtree->leaf[key_bits] -= change_value;
1498 break;
1499 }
1500 if (result_value) {
1501 BAG_COUNTER_SET(result_value, subtree->leaf[key_bits]);
1502 }
1503 return SKBAG_OK;
1504 }
1505
1506 /* visit the nodes and allocate */
1507 for (lvl = 0; lvl < bt->levels - 1; ++lvl) {
1508 if (!subtree->child) {
1509 subtree->child = (bagtree_node_t*)skMemPoolElementNew(bt->nodes);
1510 if (NULL == subtree->child) {
1511 return SKBAG_ERR_MEMORY;
1512 }
1513 }
1514 key_bits = BAGTREE_GET_KEY_BITS(key, bt, lvl);
1515 subtree = &(subtree->child[key_bits]);
1516 }
1517 if (!subtree->leaf) {
1518 subtree->leaf = (uint64_t*)skMemPoolElementNew(bt->counters);
1519 if (NULL == subtree->leaf) {
1520 return SKBAG_ERR_MEMORY;
1521 }
1522 }
1523 key_bits = BAGTREE_GET_KEY_BITS(key, bt, lvl);
1524 switch (op) {
1525 case BAG_OP_SET:
1526 subtree->leaf[key_bits] = change_value;
1527 break;
1528 case BAG_OP_ADD:
1529 if (subtree->leaf[key_bits] > (SKBAG_COUNTER_MAX - change_value)) {
1530 /* would overflow, return error */
1531 return SKBAG_ERR_OP_BOUNDS;
1532 }
1533 subtree->leaf[key_bits] += change_value;
1534 if (result_value) {
1535 BAG_COUNTER_SET(result_value, subtree->leaf[key_bits]);
1536 }
1537 break;
1538 case BAG_OP_GET:
1539 case BAG_OP_SUBTRACT:
1540 skAbortBadCase(op);
1541 }
1542
1543 return SKBAG_OK;
1544 }
1545
1546
1547 /*
1548 * status = bagProcessStreamEntryAdd(fake_bag, key, counter, bag);
1549 *
1550 * The skBagStreamEntryFunc_t callback used by skBagAddFromStream().
1551 *
1552 * Add 'counter' to the existing counter for 'key' in 'bag'.
1553 */
1554 static skBagErr_t
bagProcessStreamEntryAdd(const skBag_t UNUSED (* fake_bag),const skBagTypedKey_t * key,const skBagTypedCounter_t * counter,void * v_bag)1555 bagProcessStreamEntryAdd(
1556 const skBag_t UNUSED(*fake_bag),
1557 const skBagTypedKey_t *key,
1558 const skBagTypedCounter_t *counter,
1559 void *v_bag)
1560 {
1561 return skBagCounterAdd((skBag_t*)v_bag, key, counter, NULL);
1562 }
1563
1564
1565 /*
1566 * status = bagProcessStreamEntryRead(fake_bag, key, counter, bag);
1567 *
1568 * The skBagStreamEntryFunc_t callback used by skBagRead().
1569 *
1570 * Callback function used by skBagRead(). Set the 'key' to
1571 * 'counter' in 'bag'.
1572 */
1573 static skBagErr_t
bagProcessStreamEntryRead(const skBag_t UNUSED (* fake_bag),const skBagTypedKey_t * key,const skBagTypedCounter_t * counter,void * v_bag)1574 bagProcessStreamEntryRead(
1575 const skBag_t UNUSED(*fake_bag),
1576 const skBagTypedKey_t *key,
1577 const skBagTypedCounter_t *counter,
1578 void *v_bag)
1579 {
1580 return skBagCounterSet(*(skBag_t**)v_bag, key, counter);
1581 }
1582
1583
1584 /*
1585 * status = bagProcessStreamInitAdd(fake_bag, v_dest_bag);
1586 *
1587 * The skBagStreamInitFunc_t callback used by skBagAddFromStream().
1588 *
1589 * Modifies the destination bag depending on the keys length/type
1590 * in the bag that is being read---the 'fake_bag'.
1591 */
1592 static skBagErr_t
bagProcessStreamInitAdd(const skBag_t * src,void * v_dest_bag)1593 bagProcessStreamInitAdd(
1594 const skBag_t *src,
1595 void *v_dest_bag)
1596 {
1597 skBag_t *dest = (skBag_t*)v_dest_bag;
1598
1599 if (dest->no_autoconvert && (dest->key_octets < src->key_octets)) {
1600 return SKBAG_ERR_KEY_RANGE;
1601 }
1602
1603 dest->key_type = skBagFieldTypeMerge(dest->key_type, src->key_type);
1604 dest->counter_type = skBagFieldTypeMerge(dest->counter_type,
1605 src->counter_type);
1606 return SKBAG_OK;
1607 }
1608
1609
1610 /*
1611 * status = bagProcessStreamInitRead(fake_bag, bag);
1612 *
1613 * The skBagStreamInitFunc_t callback used by skBagRead().
1614 *
1615 * Creates a new bag in the location specified by 'bag' based on
1616 * the parameters in 'fake_bag'.
1617 */
1618 static skBagErr_t
bagProcessStreamInitRead(const skBag_t * src,void * v_bag)1619 bagProcessStreamInitRead(
1620 const skBag_t *src,
1621 void *v_bag)
1622 {
1623 return skBagCreateTyped((skBag_t**)v_bag, src->key_type, src->counter_type,
1624 src->key_octets, sizeof(uint64_t));
1625 }
1626
1627
1628 /*
1629 * found = bagtreeIterNext(iter, &key, &counter);
1630 *
1631 * Fill 'key' and 'counter' with the next entry for the iterator
1632 * over the bagtree. Return 1 if found; 0 when no more entries.
1633 */
1634 static int
bagtreeIterNext(skBagIterator_t * iter,uint32_t * key,uint64_t * counter)1635 bagtreeIterNext(
1636 skBagIterator_t *iter,
1637 uint32_t *key,
1638 uint64_t *counter)
1639 {
1640 bagtree_t *bt;
1641 bagtree_node_t *subtree[BAG_KEY_MAX_OCTETS];
1642 uint32_t key_bits;
1643 uint32_t lvl;
1644
1645 bt = iter->bag->d.b_tree;
1646 subtree[0] = &bt->root;
1647 lvl = 0;
1648
1649 if (iter->d.i_tree.no_more_entries) {
1650 return 0;
1651 }
1652 if ((0 == iter->d.i_tree.key)
1653 && (NULL == subtree[0]->child))
1654 {
1655 /* empty tree */
1656 iter->d.i_tree.no_more_entries = 1;
1657 return 0;
1658 }
1659
1660 for (;;) {
1661 key_bits = BAGTREE_GET_KEY_BITS(iter->d.i_tree.key, bt, lvl);
1662 if (lvl < bt->levels - 1) {
1663 if (subtree[lvl]->child[key_bits].child) {
1664 subtree[lvl+1] = &subtree[lvl]->child[key_bits];
1665 ++lvl;
1666 continue;
1667 }
1668 do {
1669 ++key_bits;
1670 } while (key_bits < BAGTREE_GET_LEVEL_BLOCKS(bt, lvl)
1671 && NULL == subtree[lvl]->child[key_bits].child);
1672 if (key_bits < BAGTREE_GET_LEVEL_BLOCKS(bt, lvl)) {
1673 SET_MASKED_BITS(iter->d.i_tree.key,
1674 key_bits << BAGTREE_GET_LEVEL_OFFSET(bt, lvl),
1675 0, BAGTREE_GET_LEVEL_OFFSET(bt, lvl-1));
1676 subtree[lvl+1] = &subtree[lvl]->child[key_bits];
1677 ++lvl;
1678 continue;
1679 }
1680 } else {
1681 if (!BAG_COUNTER_IS_ZERO(subtree[lvl]->leaf[key_bits])) {
1682 *key = iter->d.i_tree.key;
1683 *counter = subtree[lvl]->leaf[key_bits];
1684 if (iter->d.i_tree.max_key == iter->d.i_tree.key) {
1685 iter->d.i_tree.no_more_entries = 1;
1686 } else {
1687 ++iter->d.i_tree.key;
1688 }
1689 return 1;
1690 }
1691 do {
1692 ++key_bits;
1693 } while (key_bits < BAGTREE_GET_LEVEL_BLOCKS(bt, lvl)
1694 && BAG_COUNTER_IS_ZERO(subtree[lvl]->leaf[key_bits]));
1695 if (key_bits != BAGTREE_GET_LEVEL_BLOCKS(bt, lvl)) {
1696 SET_MASKED_BITS(iter->d.i_tree.key,
1697 key_bits << BAGTREE_GET_LEVEL_OFFSET(bt, lvl),
1698 0, BAGTREE_GET_LEVEL_OFFSET(bt, lvl-1));
1699 *key = iter->d.i_tree.key;
1700 *counter = subtree[lvl]->leaf[key_bits];
1701 if (iter->d.i_tree.max_key == iter->d.i_tree.key) {
1702 iter->d.i_tree.no_more_entries = 1;
1703 } else {
1704 ++iter->d.i_tree.key;
1705 }
1706 return 1;
1707 }
1708 }
1709
1710 do {
1711 if (0 == lvl) {
1712 iter->d.i_tree.no_more_entries = 1;
1713 return 0;
1714 }
1715 --lvl;
1716 } while ((BAGTREE_GET_KEY_BITS(iter->d.i_tree.key, bt, lvl)
1717 == BAGTREE_GET_LEVEL_BLOCKS(bt, lvl)-1));
1718 iter->d.i_tree.key = (((iter->d.i_tree.key
1719 >> BAGTREE_GET_LEVEL_OFFSET(bt, lvl)) + 1)
1720 << BAGTREE_GET_LEVEL_OFFSET(bt, lvl));
1721 }
1722
1723 return 0; /* NOTREACHED */
1724 }
1725
1726
1727
1728 /* ******************************************************** */
1729 /* EXPORTED/PUBLIC FUNCTIONS START HERE */
1730 /* ******************************************************** */
1731
1732
1733 /* add an in-core bag to an in-core bag */
1734 skBagErr_t
skBagAddBag(skBag_t * dest,const skBag_t * src,skBagBoundsCallback_t bounds_cb,void * cb_data)1735 skBagAddBag(
1736 skBag_t *dest,
1737 const skBag_t *src,
1738 skBagBoundsCallback_t bounds_cb,
1739 void *cb_data)
1740 {
1741 skBagIterator_t *iter = NULL;
1742 skBagTypedKey_t key;
1743 skBagTypedCounter_t counter;
1744 skBagTypedCounter_t counter2;
1745 skBagErr_t rv;
1746 skBagErr_t rv2;
1747
1748 if (NULL == dest || NULL == src) {
1749 return SKBAG_ERR_INPUT;
1750 }
1751 if (dest->no_autoconvert && (dest->key_octets < src->key_octets)) {
1752 return SKBAG_ERR_KEY_RANGE;
1753 }
1754
1755 dest->key_type = skBagFieldTypeMerge(dest->key_type, src->key_type);
1756 dest->counter_type = skBagFieldTypeMerge(dest->counter_type,
1757 src->counter_type);
1758
1759 /* Set type of key and counter to 'ANY' */
1760 key.type = SKBAG_KEY_ANY;
1761 counter.type = SKBAG_COUNTER_ANY;
1762 rv = skBagIteratorCreateUnsorted(src, &iter);
1763 if (rv) {
1764 goto END;
1765 }
1766 while (skBagIteratorNextTyped(iter, &key, &counter) == SKBAG_OK) {
1767 rv = skBagCounterAdd(dest, &key, &counter, NULL);
1768 if (rv) {
1769 if (SKBAG_ERR_OP_BOUNDS != rv || NULL == bounds_cb) {
1770 goto END;
1771 }
1772 counter2.type = SKBAG_COUNTER_ANY;
1773 skBagCounterGet(dest, &key, &counter2);
1774 rv2 = bounds_cb(&key, &counter2, &counter, cb_data);
1775 if (rv2) {
1776 rv = rv2;
1777 goto END;
1778 }
1779 rv2 = skBagCounterSet(dest, &key, &counter2);
1780 if (rv2) {
1781 rv = rv2;
1782 goto END;
1783 }
1784 }
1785 }
1786
1787 END:
1788 if (iter) {
1789 skBagIteratorDestroy(iter);
1790 }
1791 return rv;
1792 }
1793
1794
1795 /* add contents of file to existing bag. increment counters for
1796 * overlapping keys. */
1797 skBagErr_t
skBagAddFromStream(skBag_t * bag,skstream_t * stream_in)1798 skBagAddFromStream(
1799 skBag_t *bag,
1800 skstream_t *stream_in)
1801 {
1802 if (NULL == bag) {
1803 return SKBAG_ERR_INPUT;
1804 }
1805
1806 return skBagProcessStreamTyped(stream_in, bag, &bagProcessStreamInitAdd,
1807 &bagProcessStreamEntryAdd);
1808 }
1809
1810
1811 void
skBagAutoConvertDisable(skBag_t * bag)1812 skBagAutoConvertDisable(
1813 skBag_t *bag)
1814 {
1815 bag->no_autoconvert = 1;
1816 }
1817
1818 void
skBagAutoConvertEnable(skBag_t * bag)1819 skBagAutoConvertEnable(
1820 skBag_t *bag)
1821 {
1822 bag->no_autoconvert = 0;
1823 }
1824
1825
1826 int
skBagAutoConvertIsEnabled(const skBag_t * bag)1827 skBagAutoConvertIsEnabled(
1828 const skBag_t *bag)
1829 {
1830 return !bag->no_autoconvert;
1831 }
1832
1833
1834 /*
1835 * status = skBagCopy(&dest, src);
1836 *
1837 * Make a new bag that is a deep copy of src, and set '*dest' to
1838 * it.
1839 */
1840 skBagErr_t
skBagCopy(skBag_t ** dest,const skBag_t * src)1841 skBagCopy(
1842 skBag_t **dest,
1843 const skBag_t *src)
1844 {
1845 skBag_t *bag;
1846 skBagErr_t rv;
1847
1848 if (NULL == dest || NULL == src) {
1849 return SKBAG_ERR_INPUT;
1850 }
1851
1852 rv = skBagCreateTyped(&bag, src->key_type, src->counter_type,
1853 src->key_octets, sizeof(uint64_t));
1854 if (rv) {
1855 return rv;
1856 }
1857
1858 switch (src->key_octets) {
1859 case 1:
1860 case 2:
1861 case 4:
1862 {
1863 skBagIterator_t *iter = NULL;
1864 uint32_t key;
1865 uint64_t counter;
1866
1867 rv = skBagIteratorCreate(src, &iter);
1868 if (rv) {
1869 goto END;
1870 }
1871 while (bagtreeIterNext(iter, &key, &counter)) {
1872 if (bagOperationTree(bag, key, counter, 0, BAG_OP_SET)) {
1873 rv = SKBAG_ERR_MEMORY;
1874 skBagIteratorDestroy(iter);
1875 goto END;
1876 }
1877 }
1878 skBagIteratorDestroy(iter);
1879 }
1880 break;
1881
1882 #if SK_ENABLE_IPV6
1883 case 16:
1884 {
1885 RBLIST *rb_iter;
1886 const bag_keycount128_t *srcnode;
1887 bag_keycount128_t *dstnode;
1888 bag_redblack_t *brb = bag->d.b_rbt;
1889
1890 rb_iter = rbopenlist(src->d.b_rbt->tree);
1891 if (NULL == rb_iter) {
1892 rv = SKBAG_ERR_MEMORY;
1893 goto END;
1894 }
1895 while ((srcnode = (const bag_keycount128_t*)rbreadlist(rb_iter))
1896 != NULL)
1897 {
1898 dstnode = (bag_keycount128_t*)skMemPoolElementNew(brb->datum);
1899 if (NULL == dstnode) {
1900 rbcloselist(rb_iter);
1901 rv = SKBAG_ERR_MEMORY;
1902 goto END;
1903 }
1904 memcpy(dstnode, srcnode, sizeof(bag_keycount128_t));
1905 if (NULL == rbsearch(dstnode, brb->tree)) {
1906 rbcloselist(rb_iter);
1907 rv = SKBAG_ERR_MEMORY;
1908 goto END;
1909 }
1910 }
1911 rbcloselist(rb_iter);
1912 }
1913 break;
1914 #endif /* SK_ENABLE_IPV6 */
1915
1916 case 8:
1917 default:
1918 skAbortBadCase(src->key_octets);
1919 }
1920
1921 *dest = bag;
1922 rv = SKBAG_OK;
1923
1924 END:
1925 if (SKBAG_OK != rv) {
1926 skBagDestroy(&bag);
1927 }
1928 return rv;
1929 }
1930
1931
1932 /* return number of unique keys in bag */
1933 uint64_t
skBagCountKeys(const skBag_t * bag)1934 skBagCountKeys(
1935 const skBag_t *bag)
1936 {
1937 bagstats_t stats;
1938
1939 bagComputeStats(bag, &stats);
1940 return stats.unique_keys;
1941 }
1942
1943
1944 /* add value 'counter_add' to counter for 'key'; create key if needed */
1945 skBagErr_t
skBagCounterAdd(skBag_t * bag,const skBagTypedKey_t * key,const skBagTypedCounter_t * counter_add,skBagTypedCounter_t * out_counter)1946 skBagCounterAdd(
1947 skBag_t *bag,
1948 const skBagTypedKey_t *key,
1949 const skBagTypedCounter_t *counter_add,
1950 skBagTypedCounter_t *out_counter)
1951 {
1952 uint32_t u32;
1953 skBagErr_t rv;
1954
1955 BAG_CHECK_INPUT(bag, key, counter_add);
1956
1957 #if !SK_ENABLE_IPV6
1958
1959 BAG_KEY_TO_U32_V4(key, u32);
1960
1961 #else
1962 {
1963 uint8_t ipv6[16];
1964 int is_v6;
1965 skBagFieldType_t key_type;
1966
1967 if (16 == bag->key_octets) {
1968 /* bag is ipv6, so convert key to ipv6 */
1969 BAG_KEY_TO_IPV6(key, ipv6);
1970 return bagOperationRedblack(bag, ipv6, counter_add->val.u64,
1971 out_counter, BAG_OP_ADD);
1972 }
1973
1974 BAG_KEY_TO_U32_V6(key, u32, is_v6);
1975
1976 if (is_v6) {
1977 /* key is IPv6; convert bag unless 'counter_add' is 0 */
1978 if (BAG_COUNTER_IS_ZERO(counter_add->val.u64)) {
1979 if (out_counter) {
1980 BAG_COUNTER_SET_ZERO(out_counter);
1981 }
1982 return SKBAG_OK;
1983 }
1984 if (bag->no_autoconvert) {
1985 return SKBAG_ERR_KEY_RANGE;
1986 }
1987 switch (bag->key_type) {
1988 case SKBAG_FIELD_SIPv4:
1989 key_type = SKBAG_FIELD_SIPv6;
1990 break;
1991 case SKBAG_FIELD_DIPv4:
1992 key_type = SKBAG_FIELD_DIPv6;
1993 break;
1994 case SKBAG_FIELD_NHIPv4:
1995 key_type = SKBAG_FIELD_NHIPv6;
1996 break;
1997 case SKBAG_FIELD_ANY_IPv4:
1998 key_type = SKBAG_FIELD_ANY_IPv6;
1999 break;
2000 default:
2001 key_type = bag->key_type;
2002 break;
2003 }
2004 rv = skBagModify(bag, key_type, bag->counter_type,
2005 sizeof(ipv6), sizeof(uint64_t));
2006 if (rv) {
2007 return rv;
2008 }
2009 BAG_KEY_TO_IPV6(key, ipv6);
2010 return bagOperationRedblack(bag, ipv6, counter_add->val.u64,
2011 out_counter, BAG_OP_ADD);
2012 }
2013 }
2014 #endif /* #else of #if !SK_ENABLE_IPV6 */
2015
2016 if ((bag->key_octets < 4)
2017 && (u32 >= (1u << (bag->key_octets * CHAR_BIT))))
2018 {
2019 /* key is out of range */
2020 if (BAG_COUNTER_IS_ZERO(counter_add->val.u64)) {
2021 if (out_counter) {
2022 BAG_COUNTER_SET_ZERO(out_counter);
2023 }
2024 return SKBAG_OK;
2025 }
2026 if (bag->no_autoconvert) {
2027 return SKBAG_ERR_KEY_RANGE;
2028 }
2029 rv = skBagModify(bag, bag->key_type, bag->counter_type,
2030 sizeof(uint32_t), sizeof(uint64_t));
2031 if (rv) {
2032 return rv;
2033 }
2034 }
2035
2036 return bagOperationTree(bag, u32, counter_add->val.u64,
2037 out_counter, BAG_OP_ADD);
2038 }
2039
2040
2041 size_t
skBagCounterFieldLength(const skBag_t UNUSED (* bag))2042 skBagCounterFieldLength(
2043 const skBag_t UNUSED(*bag))
2044 {
2045 return sizeof(uint64_t);
2046 }
2047
2048
2049 skBagFieldType_t
skBagCounterFieldName(const skBag_t * bag,char * buf,size_t buflen)2050 skBagCounterFieldName(
2051 const skBag_t *bag,
2052 char *buf,
2053 size_t buflen)
2054 {
2055 const bag_field_info_t *bf;
2056
2057 bf = BAG_GET_FIELD_INFO(bag->counter_type);
2058 if (NULL == bf) {
2059 bf = &bag_field_info_custom;
2060 }
2061 if (buf && buflen) {
2062 strncpy(buf, bf->name, buflen);
2063 buf[buflen-1] = '\0';
2064 }
2065
2066 return bag->counter_type;
2067 }
2068
2069
2070 skBagFieldType_t
skBagCounterFieldType(const skBag_t * bag)2071 skBagCounterFieldType(
2072 const skBag_t *bag)
2073 {
2074 return bag->counter_type;
2075 }
2076
2077
2078 /* get counter at 'key' */
2079 skBagErr_t
skBagCounterGet(const skBag_t * bag,const skBagTypedKey_t * key,skBagTypedCounter_t * out_counter)2080 skBagCounterGet(
2081 const skBag_t *bag,
2082 const skBagTypedKey_t *key,
2083 skBagTypedCounter_t *out_counter)
2084 {
2085 uint32_t u32;
2086
2087 if (NULL == bag || NULL == key || NULL == out_counter) {
2088 return SKBAG_ERR_INPUT;
2089 }
2090
2091 #if !SK_ENABLE_IPV6
2092
2093 BAG_KEY_TO_U32_V4(key, u32);
2094
2095 #else
2096 {
2097 uint8_t ipv6[16];
2098 int is_v6;
2099
2100 if (16 == bag->key_octets) {
2101 /* bag is ipv6, so convert key to ipv6 */
2102 BAG_KEY_TO_IPV6(key, ipv6);
2103 return bagOperationRedblack((skBag_t*)bag, ipv6, 0,
2104 out_counter, BAG_OP_GET);
2105 }
2106
2107 BAG_KEY_TO_U32_V6(key, u32, is_v6);
2108
2109 if (is_v6) {
2110 /* key is IPv6; so it is not in this bag */
2111 BAG_COUNTER_SET_ZERO(out_counter);
2112 return SKBAG_OK;
2113 }
2114 }
2115 #endif /* #else of #if !SK_ENABLE_IPV6 */
2116
2117 if ((bag->key_octets < 4)
2118 && (u32 >= (1u << (bag->key_octets * CHAR_BIT))))
2119 {
2120 /* key is out of range */
2121 BAG_COUNTER_SET_ZERO(out_counter);
2122 return SKBAG_OK;
2123 }
2124
2125 return bagOperationTree((skBag_t*)bag, u32, 0, out_counter, BAG_OP_GET);
2126 }
2127
2128
2129 /* set counter for 'key' to 'counter'. create key if needed */
2130 skBagErr_t
skBagCounterSet(skBag_t * bag,const skBagTypedKey_t * key,const skBagTypedCounter_t * counter)2131 skBagCounterSet(
2132 skBag_t *bag,
2133 const skBagTypedKey_t *key,
2134 const skBagTypedCounter_t *counter)
2135 {
2136 uint32_t u32;
2137 skBagErr_t rv = SKBAG_ERR_INPUT;
2138
2139 BAG_CHECK_INPUT(bag, key, counter);
2140
2141 #if !SK_ENABLE_IPV6
2142
2143 BAG_KEY_TO_U32_V4(key, u32);
2144
2145 #else
2146 {
2147 uint8_t ipv6[16];
2148 int is_v6;
2149 skBagFieldType_t key_type;
2150
2151 if (16 == bag->key_octets) {
2152 /* bag is ipv6, so convert key to ipv6 */
2153 BAG_KEY_TO_IPV6(key, ipv6);
2154 return bagOperationRedblack(bag, ipv6, counter->val.u64,
2155 NULL, BAG_OP_SET);
2156 }
2157
2158 BAG_KEY_TO_U32_V6(key, u32, is_v6);
2159
2160 if (is_v6) {
2161 /* key is IPv6; convert bag unless 'counter' is 0 */
2162 if (BAG_COUNTER_IS_ZERO(counter->val.u64)) {
2163 return SKBAG_OK;
2164 }
2165 if (bag->no_autoconvert) {
2166 return SKBAG_ERR_KEY_RANGE;
2167 }
2168 switch (bag->key_type) {
2169 case SKBAG_FIELD_SIPv4:
2170 key_type = SKBAG_FIELD_SIPv6;
2171 break;
2172 case SKBAG_FIELD_DIPv4:
2173 key_type = SKBAG_FIELD_DIPv6;
2174 break;
2175 case SKBAG_FIELD_NHIPv4:
2176 key_type = SKBAG_FIELD_NHIPv6;
2177 break;
2178 case SKBAG_FIELD_ANY_IPv4:
2179 key_type = SKBAG_FIELD_ANY_IPv6;
2180 break;
2181 default:
2182 key_type = bag->key_type;
2183 break;
2184 }
2185 rv = skBagModify(bag, key_type, bag->counter_type,
2186 sizeof(ipv6), sizeof(uint64_t));
2187 if (rv) {
2188 return rv;
2189 }
2190 BAG_KEY_TO_IPV6(key, ipv6);
2191 return bagOperationRedblack(bag, ipv6, counter->val.u64,
2192 NULL, BAG_OP_SET);
2193 }
2194 }
2195 #endif /* #else of #if !SK_ENABLE_IPV6 */
2196
2197 if ((bag->key_octets < 4)
2198 && (u32 >= (1u << (bag->key_octets * CHAR_BIT))))
2199 {
2200 /* key is out of range */
2201 if (BAG_COUNTER_IS_ZERO(counter->val.u64)) {
2202 return SKBAG_OK;
2203 }
2204 if (bag->no_autoconvert) {
2205 return SKBAG_ERR_KEY_RANGE;
2206 }
2207
2208 rv = skBagModify(bag, bag->key_type, bag->counter_type,
2209 sizeof(uint32_t), sizeof(uint64_t));
2210 if (rv) {
2211 return rv;
2212 }
2213 }
2214
2215 return bagOperationTree(bag, u32, counter->val.u64, NULL, BAG_OP_SET);
2216 }
2217
2218
2219 /* subtract 'counter_sub' from counter at 'key' */
2220 skBagErr_t
skBagCounterSubtract(skBag_t * bag,const skBagTypedKey_t * key,const skBagTypedCounter_t * counter_sub,skBagTypedCounter_t * out_counter)2221 skBagCounterSubtract(
2222 skBag_t *bag,
2223 const skBagTypedKey_t *key,
2224 const skBagTypedCounter_t *counter_sub,
2225 skBagTypedCounter_t *out_counter)
2226 {
2227 uint32_t u32;
2228
2229 BAG_CHECK_INPUT(bag, key, counter_sub);
2230
2231 #if !SK_ENABLE_IPV6
2232
2233 BAG_KEY_TO_U32_V4(key, u32);
2234
2235 #else
2236 {
2237 uint8_t ipv6[16];
2238 int is_v6;
2239
2240 if (16 == bag->key_octets) {
2241 /* bag is ipv6, so convert key to ipv6 */
2242 BAG_KEY_TO_IPV6(key, ipv6);
2243 return bagOperationRedblack(bag, ipv6, counter_sub->val.u64,
2244 out_counter, BAG_OP_SUBTRACT);
2245 }
2246
2247 BAG_KEY_TO_U32_V6(key, u32, is_v6);
2248
2249 if (is_v6) {
2250 /* key is IPv6, so it is not in this bag. subtraction would
2251 * underflow unless 'counter_sub' is 0 */
2252 if (BAG_COUNTER_IS_ZERO(counter_sub->val.u64)) {
2253 if (out_counter) {
2254 BAG_COUNTER_SET_ZERO(out_counter);
2255 }
2256 return SKBAG_OK;
2257 }
2258 return SKBAG_ERR_OP_BOUNDS;
2259 }
2260 }
2261 #endif /* #else of #if !SK_ENABLE_IPV6 */
2262
2263 if ((bag->key_octets < 4)
2264 && (u32 >= (1u << (bag->key_octets * CHAR_BIT))))
2265 {
2266 /* key is out of range */
2267 if (!BAG_COUNTER_IS_ZERO(counter_sub->val.u64)) {
2268 return SKBAG_ERR_OP_BOUNDS;
2269 }
2270 if (out_counter) {
2271 BAG_COUNTER_SET_ZERO(out_counter);
2272 }
2273 return SKBAG_OK;
2274 }
2275
2276 return bagOperationTree(bag, u32, counter_sub->val.u64,
2277 out_counter, BAG_OP_SUBTRACT);
2278 }
2279
2280
2281 skBagErr_t
skBagCreate(skBag_t ** bag)2282 skBagCreate(
2283 skBag_t **bag)
2284 {
2285 return skBagCreateTyped(bag, SKBAG_FIELD_CUSTOM, SKBAG_FIELD_CUSTOM,
2286 sizeof(uint32_t), sizeof(uint64_t));
2287 }
2288
2289
2290 skBagErr_t
skBagCreateTyped(skBag_t ** bag,skBagFieldType_t key_type,skBagFieldType_t counter_type,size_t key_octets,size_t counter_octets)2291 skBagCreateTyped(
2292 skBag_t **bag,
2293 skBagFieldType_t key_type,
2294 skBagFieldType_t counter_type,
2295 size_t key_octets,
2296 size_t counter_octets)
2297 {
2298 skBag_t *new_bag = NULL;
2299 skBagErr_t rv;
2300
2301 rv = bagCheckTypesAndSizes(key_type, counter_type,
2302 &key_octets, &counter_octets);
2303 if (rv) {
2304 return rv;
2305 }
2306
2307 /* allocate the bag */
2308 new_bag = (skBag_t*)calloc(1, sizeof(skBag_t));
2309 if (NULL == new_bag) {
2310 goto ERROR;
2311 }
2312
2313 new_bag->key_octets = (uint16_t)key_octets;
2314 new_bag->key_type = key_type;
2315 new_bag->counter_type = counter_type;
2316
2317 switch (new_bag->key_octets) {
2318 case 1:
2319 case 2:
2320 case 4:
2321 {
2322 bagtree_t *bt;
2323 bt = (bagtree_t*)calloc(1, sizeof(bagtree_t));
2324 if (NULL == bt) {
2325 goto ERROR;
2326 }
2327 bt->levels = new_bag->key_octets;
2328 if (skMemoryPoolCreate(&bt->nodes,
2329 (BAGTREE_GET_LEVEL_BLOCKS(bt, 0)
2330 * sizeof(bagtree_node_t)),
2331 BAGTREE_MEMPOOL_SIZE))
2332 {
2333 free(bt);
2334 goto ERROR;
2335 }
2336 if (skMemoryPoolCreate(&bt->counters,
2337 (BAGTREE_GET_LEVEL_BLOCKS(bt, bt->levels-1)
2338 * sizeof(uint64_t)),
2339 BAGTREE_MEMPOOL_SIZE))
2340 {
2341 skMemoryPoolDestroy(&bt->nodes);
2342 free(bt);
2343 goto ERROR;
2344 }
2345 new_bag->d.b_tree = bt;
2346 }
2347 break;
2348
2349 #if SK_ENABLE_IPV6
2350 case 16:
2351 {
2352 bag_redblack_t *brb;
2353 brb = (bag_redblack_t*)calloc(1, sizeof(bag_redblack_t));
2354 if (NULL == brb) {
2355 goto ERROR;
2356 }
2357 if (skMemoryPoolCreate(&brb->datum,
2358 sizeof(bag_keycount128_t),
2359 BAG_REDBLACK_MEMPOOL_SIZE))
2360 {
2361 free(brb);
2362 goto ERROR;
2363 }
2364 brb->tree = rbinit(&bagCompareKeys128, NULL);
2365 if (NULL == brb->tree) {
2366 skMemoryPoolDestroy(&brb->datum);
2367 free(brb);
2368 goto ERROR;
2369 }
2370 new_bag->d.b_rbt = brb;
2371 }
2372 break;
2373 #endif /* SK_ENABLE_IPV6 */
2374
2375 case 8:
2376 default:
2377 skAbortBadCase(new_bag->key_octets);
2378 }
2379
2380 /* set pointer and return OK */
2381 *bag = new_bag;
2382 return SKBAG_OK;
2383
2384 ERROR:
2385 if (new_bag) {
2386 free(new_bag);
2387 }
2388 return SKBAG_ERR_MEMORY;
2389 }
2390
2391
2392 void
skBagDestroy(skBag_t ** bag_ptr)2393 skBagDestroy(
2394 skBag_t **bag_ptr)
2395 {
2396 if (bag_ptr && *bag_ptr) {
2397 skBag_t *bag = *bag_ptr;
2398
2399 switch (bag->key_octets) {
2400 case 1:
2401 case 2:
2402 case 4:
2403 if (bag->d.b_tree) {
2404 bagtree_t *bt = bag->d.b_tree;
2405 if (bt->nodes) {
2406 skMemoryPoolDestroy(&bt->nodes);
2407 }
2408 if (bt->counters) {
2409 skMemoryPoolDestroy(&bt->counters);
2410 }
2411 free(bt);
2412 }
2413 break;
2414 #if SK_ENABLE_IPV6
2415 case 16:
2416 if (bag->d.b_rbt) {
2417 bag_redblack_t *brb = bag->d.b_rbt;
2418 if (brb->datum) {
2419 skMemoryPoolDestroy(&brb->datum);
2420 }
2421 if (brb->tree) {
2422 rbdestroy(brb->tree);
2423 }
2424 free(brb);
2425 }
2426 break;
2427 #endif /* SK_ENABLE_IPV6 */
2428 case 8:
2429 default:
2430 skAbortBadCase(bag->key_octets);
2431 }
2432 memset(bag, 0, sizeof(skBag_t));
2433 free(bag);
2434 *bag_ptr = NULL;
2435 }
2436 }
2437
2438
2439 char *
skBagFieldTypeAsString(skBagFieldType_t field,char * buf,size_t buflen)2440 skBagFieldTypeAsString(
2441 skBagFieldType_t field,
2442 char *buf,
2443 size_t buflen)
2444 {
2445 const bag_field_info_t *bf;
2446
2447 bf = BAG_GET_FIELD_INFO(field);
2448 if (NULL == bf) {
2449 return NULL;
2450 }
2451 if (strlen(bf->name) >= buflen) {
2452 return NULL;
2453 }
2454 strncpy(buf, bf->name, buflen);
2455 return buf;
2456 }
2457
2458
2459 size_t
skBagFieldTypeGetLength(skBagFieldType_t field)2460 skBagFieldTypeGetLength(
2461 skBagFieldType_t field)
2462 {
2463 const bag_field_info_t *bf;
2464
2465 bf = BAG_GET_FIELD_INFO(field);
2466 if (NULL == bf) {
2467 return SKBAG_OCTETS_UNKNOWN;
2468 }
2469 return bf->octets;
2470 }
2471
2472
2473 skBagErr_t
skBagFieldTypeIteratorBind(skBagFieldTypeIterator_t * ft_iter)2474 skBagFieldTypeIteratorBind(
2475 skBagFieldTypeIterator_t *ft_iter)
2476 {
2477 return skBagFieldTypeIteratorReset(ft_iter);
2478 }
2479
2480
2481 skBagErr_t
skBagFieldTypeIteratorNext(skBagFieldTypeIterator_t * ft_iter,skBagFieldType_t * field_type,size_t * field_octets,char * type_name,size_t type_name_len)2482 skBagFieldTypeIteratorNext(
2483 skBagFieldTypeIterator_t *ft_iter,
2484 skBagFieldType_t *field_type,
2485 size_t *field_octets,
2486 char *type_name,
2487 size_t type_name_len)
2488 {
2489 if (NULL == ft_iter) {
2490 return SKBAG_ERR_INPUT;
2491 }
2492 if (ft_iter->no_more_entries) {
2493 return SKBAG_ERR_KEY_NOT_FOUND;
2494 }
2495 if (field_type) {
2496 *field_type = ft_iter->val;
2497 }
2498 if (field_octets) {
2499 *field_octets = skBagFieldTypeGetLength(ft_iter->val);
2500 }
2501 if (type_name && type_name_len) {
2502 skBagFieldTypeAsString(ft_iter->val, type_name, type_name_len);
2503 }
2504 while (ft_iter->val < (skBagFieldType_t)(BAG_NUM_FIELDS - 1u)) {
2505 ft_iter->val = (skBagFieldType_t)(1 + (int)ft_iter->val);
2506 if (bag_field_info[ft_iter->val].octets > 0) {
2507 return SKBAG_OK;
2508 }
2509 /* else field is not currently supported; try next field */
2510 }
2511 if (SKBAG_FIELD_CUSTOM == ft_iter->val) {
2512 ft_iter->no_more_entries = 1;
2513 } else {
2514 ft_iter->val = SKBAG_FIELD_CUSTOM;
2515 }
2516 return SKBAG_OK;
2517 }
2518
2519
2520 skBagErr_t
skBagFieldTypeIteratorReset(skBagFieldTypeIterator_t * ft_iter)2521 skBagFieldTypeIteratorReset(
2522 skBagFieldTypeIterator_t *ft_iter)
2523 {
2524 if (NULL == ft_iter) {
2525 return SKBAG_ERR_INPUT;
2526 }
2527 ft_iter->no_more_entries = 0;
2528 ft_iter->val = (skBagFieldType_t)0;
2529 do {
2530 if (bag_field_info[ft_iter->val].octets > 0) {
2531 return SKBAG_OK;
2532 }
2533 /* else field is not currently supported; try next field */
2534 ft_iter->val = (skBagFieldType_t)(1 + (int)ft_iter->val);
2535
2536 } while (ft_iter->val < BAG_NUM_FIELDS);
2537 ft_iter->val = SKBAG_FIELD_CUSTOM;
2538 return SKBAG_OK;
2539 }
2540
2541
2542 skBagErr_t
skBagFieldTypeLookup(const char * type_name,skBagFieldType_t * field_type,size_t * field_octets)2543 skBagFieldTypeLookup(
2544 const char *type_name,
2545 skBagFieldType_t *field_type,
2546 size_t *field_octets)
2547 {
2548 const bag_field_info_t *bf;
2549 size_t i;
2550 skBagErr_t rv = SKBAG_ERR_INPUT;
2551
2552 if (0 == strcasecmp(bag_field_info_custom.name, type_name)) {
2553 i = SKBAG_FIELD_CUSTOM;
2554 bf = &bag_field_info_custom;
2555 rv = SKBAG_OK;
2556 } else {
2557 for (i = 0, bf = bag_field_info; i < BAG_NUM_FIELDS; ++i, ++bf) {
2558 if ((bf->octets > 0) && (0 == strcasecmp(bf->name, type_name))) {
2559 rv = SKBAG_OK;
2560 break;
2561 }
2562 }
2563 }
2564
2565 if (SKBAG_OK == rv) {
2566 if (field_type) {
2567 *field_type = (skBagFieldType_t)i;
2568 }
2569 if (field_octets) {
2570 *field_octets = bf->octets;
2571 }
2572 }
2573 return rv;
2574 }
2575
2576
2577 skBagFieldType_t
skBagFieldTypeMerge(skBagFieldType_t ftype1,skBagFieldType_t ftype2)2578 skBagFieldTypeMerge(
2579 skBagFieldType_t ftype1,
2580 skBagFieldType_t ftype2)
2581 {
2582 if (ftype1 == ftype2) {
2583 return ftype1;
2584 }
2585
2586 switch (ftype1) {
2587 case SKBAG_FIELD_SIPv4:
2588 case SKBAG_FIELD_DIPv4:
2589 case SKBAG_FIELD_NHIPv4:
2590 case SKBAG_FIELD_ANY_IPv4:
2591 switch (ftype2) {
2592 case SKBAG_FIELD_SIPv4:
2593 case SKBAG_FIELD_DIPv4:
2594 case SKBAG_FIELD_NHIPv4:
2595 case SKBAG_FIELD_ANY_IPv4:
2596 return SKBAG_FIELD_ANY_IPv4;
2597
2598 case SKBAG_FIELD_SIPv6:
2599 case SKBAG_FIELD_DIPv6:
2600 case SKBAG_FIELD_NHIPv6:
2601 case SKBAG_FIELD_ANY_IPv6:
2602 return SKBAG_FIELD_ANY_IPv6;
2603
2604 default:
2605 break;
2606 }
2607 break;
2608
2609 case SKBAG_FIELD_SIPv6:
2610 case SKBAG_FIELD_DIPv6:
2611 case SKBAG_FIELD_NHIPv6:
2612 case SKBAG_FIELD_ANY_IPv6:
2613 switch (ftype2) {
2614 case SKBAG_FIELD_SIPv4:
2615 case SKBAG_FIELD_DIPv4:
2616 case SKBAG_FIELD_NHIPv4:
2617 case SKBAG_FIELD_ANY_IPv4:
2618 case SKBAG_FIELD_SIPv6:
2619 case SKBAG_FIELD_DIPv6:
2620 case SKBAG_FIELD_NHIPv6:
2621 case SKBAG_FIELD_ANY_IPv6:
2622 return SKBAG_FIELD_ANY_IPv6;
2623 default:
2624 break;
2625 }
2626 break;
2627
2628 case SKBAG_FIELD_SPORT:
2629 case SKBAG_FIELD_DPORT:
2630 case SKBAG_FIELD_ANY_PORT:
2631 switch (ftype2) {
2632 case SKBAG_FIELD_SPORT:
2633 case SKBAG_FIELD_DPORT:
2634 case SKBAG_FIELD_ANY_PORT:
2635 return SKBAG_FIELD_ANY_PORT;
2636 default:
2637 break;
2638 }
2639 break;
2640
2641 case SKBAG_FIELD_INPUT:
2642 case SKBAG_FIELD_OUTPUT:
2643 case SKBAG_FIELD_ANY_SNMP:
2644 switch (ftype2) {
2645 case SKBAG_FIELD_INPUT:
2646 case SKBAG_FIELD_OUTPUT:
2647 case SKBAG_FIELD_ANY_SNMP:
2648 return SKBAG_FIELD_ANY_SNMP;
2649 default:
2650 break;
2651 }
2652 break;
2653
2654 case SKBAG_FIELD_PACKETS:
2655 case SKBAG_FIELD_SUM_PACKETS:
2656 switch (ftype2) {
2657 case SKBAG_FIELD_PACKETS:
2658 case SKBAG_FIELD_SUM_PACKETS:
2659 return SKBAG_FIELD_SUM_PACKETS;
2660 default:
2661 break;
2662 }
2663 break;
2664
2665 case SKBAG_FIELD_BYTES:
2666 case SKBAG_FIELD_SUM_BYTES:
2667 switch (ftype2) {
2668 case SKBAG_FIELD_BYTES:
2669 case SKBAG_FIELD_SUM_BYTES:
2670 return SKBAG_FIELD_SUM_BYTES;
2671 default:
2672 break;
2673 }
2674 break;
2675
2676 case SKBAG_FIELD_FLAGS:
2677 case SKBAG_FIELD_INIT_FLAGS:
2678 case SKBAG_FIELD_REST_FLAGS:
2679 switch (ftype2) {
2680 case SKBAG_FIELD_FLAGS:
2681 case SKBAG_FIELD_INIT_FLAGS:
2682 case SKBAG_FIELD_REST_FLAGS:
2683 return SKBAG_FIELD_FLAGS;
2684 default:
2685 break;
2686 }
2687 break;
2688
2689 case SKBAG_FIELD_STARTTIME:
2690 case SKBAG_FIELD_ENDTIME:
2691 case SKBAG_FIELD_ANY_TIME:
2692 switch (ftype2) {
2693 case SKBAG_FIELD_STARTTIME:
2694 case SKBAG_FIELD_ENDTIME:
2695 case SKBAG_FIELD_ANY_TIME:
2696 case SKBAG_FIELD_ELAPSED:
2697 case SKBAG_FIELD_SUM_ELAPSED:
2698 return SKBAG_FIELD_ANY_TIME;
2699 default:
2700 break;
2701 }
2702 break;
2703
2704 case SKBAG_FIELD_ELAPSED:
2705 case SKBAG_FIELD_SUM_ELAPSED:
2706 switch (ftype2) {
2707 case SKBAG_FIELD_ELAPSED:
2708 case SKBAG_FIELD_SUM_ELAPSED:
2709 return SKBAG_FIELD_SUM_ELAPSED;
2710
2711 case SKBAG_FIELD_STARTTIME:
2712 case SKBAG_FIELD_ENDTIME:
2713 case SKBAG_FIELD_ANY_TIME:
2714 return SKBAG_FIELD_ANY_TIME;
2715
2716 default:
2717 break;
2718 }
2719 break;
2720
2721 case SKBAG_FIELD_SIP_COUNTRY:
2722 case SKBAG_FIELD_DIP_COUNTRY:
2723 case SKBAG_FIELD_ANY_COUNTRY:
2724 switch (ftype2) {
2725 case SKBAG_FIELD_SIP_COUNTRY:
2726 case SKBAG_FIELD_DIP_COUNTRY:
2727 case SKBAG_FIELD_ANY_COUNTRY:
2728 return SKBAG_FIELD_ANY_COUNTRY;
2729 default:
2730 break;
2731 }
2732 break;
2733
2734 case SKBAG_FIELD_SIP_PMAP:
2735 case SKBAG_FIELD_DIP_PMAP:
2736 case SKBAG_FIELD_ANY_IP_PMAP:
2737 switch (ftype2) {
2738 case SKBAG_FIELD_SIP_PMAP:
2739 case SKBAG_FIELD_DIP_PMAP:
2740 case SKBAG_FIELD_ANY_IP_PMAP:
2741 return SKBAG_FIELD_ANY_IP_PMAP;
2742 default:
2743 break;
2744 }
2745 break;
2746
2747 case SKBAG_FIELD_SPORT_PMAP:
2748 case SKBAG_FIELD_DPORT_PMAP:
2749 case SKBAG_FIELD_ANY_PORT_PMAP:
2750 switch (ftype2) {
2751 case SKBAG_FIELD_SPORT_PMAP:
2752 case SKBAG_FIELD_DPORT_PMAP:
2753 case SKBAG_FIELD_ANY_PORT_PMAP:
2754 return SKBAG_FIELD_ANY_PORT_PMAP;
2755 default:
2756 break;
2757 }
2758 break;
2759
2760 default:
2761 break;
2762 }
2763
2764 return SKBAG_FIELD_CUSTOM;
2765 }
2766
2767
2768 /* create iterator */
2769 skBagErr_t
skBagIteratorCreate(const skBag_t * bag,skBagIterator_t ** iter)2770 skBagIteratorCreate(
2771 const skBag_t *bag,
2772 skBagIterator_t **iter)
2773 {
2774 return bagIterCreate(bag, iter, 1);
2775 }
2776
2777
2778 /* create iterator */
2779 skBagErr_t
skBagIteratorCreateUnsorted(const skBag_t * bag,skBagIterator_t ** iter)2780 skBagIteratorCreateUnsorted(
2781 const skBag_t *bag,
2782 skBagIterator_t **iter)
2783 {
2784 return bagIterCreate(bag, iter, 0);
2785 }
2786
2787
2788 /* destroy the iterator */
2789 skBagErr_t
skBagIteratorDestroy(skBagIterator_t * iter)2790 skBagIteratorDestroy(
2791 skBagIterator_t *iter)
2792 {
2793 if (NULL == iter) {
2794 return SKBAG_ERR_INPUT;
2795 }
2796 switch (iter->key_octets) {
2797 case 1:
2798 case 2:
2799 break;
2800 case 4:
2801 break;
2802 case 8:
2803 case 16:
2804 #if SK_ENABLE_IPV6
2805 if (iter->d.i_rbt.rb_iter) {
2806 rbcloselist(iter->d.i_rbt.rb_iter);
2807 }
2808 #endif /* SK_ENABLE_IPV6 */
2809 break;
2810 }
2811 memset(iter, 0, sizeof(*iter));
2812 free(iter);
2813 return SKBAG_OK;
2814 }
2815
2816
2817 skBagErr_t
skBagIteratorNextTyped(skBagIterator_t * iter,skBagTypedKey_t * key,skBagTypedCounter_t * counter)2818 skBagIteratorNextTyped(
2819 skBagIterator_t *iter,
2820 skBagTypedKey_t *key,
2821 skBagTypedCounter_t *counter)
2822 {
2823 /* check input */
2824 if (NULL == iter) {
2825 return SKBAG_ERR_INPUT;
2826 }
2827 assert(iter->bag);
2828
2829 if (iter->key_octets != iter->bag->key_octets) {
2830 return SKBAG_ERR_MODIFIED;
2831 }
2832
2833 if (NULL == iter->bag->d.b_tree) {
2834 return SKBAG_ERR_KEY_NOT_FOUND;
2835 }
2836 if (counter->type != SKBAG_COUNTER_ANY
2837 && counter->type != SKBAG_COUNTER_U64)
2838 {
2839 return SKBAG_ERR_INPUT;
2840 }
2841 switch (iter->bag->key_octets) {
2842 case 1:
2843 case 2:
2844 case 4:
2845 return bagIterNextTree(iter, key, counter);
2846 #if SK_ENABLE_IPV6
2847 case 16:
2848 return bagIterNextRedblack(iter, key, counter);
2849 #endif /* SK_ENABLE_IPV6 */
2850 case 8:
2851 default:
2852 skAbortBadCase(iter->bag->key_octets);
2853 }
2854
2855 return SKBAG_ERR_INPUT;
2856 }
2857
2858
2859 /* reset the iterator */
2860 skBagErr_t
skBagIteratorReset(skBagIterator_t * iter)2861 skBagIteratorReset(
2862 skBagIterator_t *iter)
2863 {
2864 if (NULL == iter) {
2865 return SKBAG_ERR_INPUT;
2866 }
2867 assert(iter->bag);
2868
2869 if (iter->key_octets != iter->bag->key_octets) {
2870 /* destroy the old data structure */
2871 switch (iter->key_octets) {
2872 case 1:
2873 case 2:
2874 case 4:
2875 break;
2876 #if SK_ENABLE_IPV6
2877 case 16:
2878 iter->d.i_rbt.next = NULL;
2879 if (iter->d.i_rbt.rb_iter) {
2880 rbcloselist(iter->d.i_rbt.rb_iter);
2881 iter->d.i_rbt.rb_iter = NULL;
2882 }
2883 break;
2884 #endif /* SK_ENABLE_IPV6 */
2885 case 8:
2886 default:
2887 skAbortBadCase(iter->bag->key_octets);
2888 }
2889 iter->key_octets = iter->bag->key_octets;
2890 }
2891
2892 iter->pos = 0;
2893
2894 if (NULL == iter->bag->d.b_tree) {
2895 return SKBAG_OK;
2896 }
2897 switch (iter->bag->key_octets) {
2898 case 1:
2899 case 2:
2900 case 4:
2901 return bagIterResetTree(iter);
2902 #if SK_ENABLE_IPV6
2903 case 16:
2904 return bagIterResetRedblack(iter);
2905 #endif /* SK_ENABLE_IPV6 */
2906 case 8:
2907 default:
2908 skAbortBadCase(iter->bag->key_octets);
2909 }
2910 }
2911
2912
2913 size_t
skBagKeyFieldLength(const skBag_t * bag)2914 skBagKeyFieldLength(
2915 const skBag_t *bag)
2916 {
2917 return bag->key_octets;
2918 }
2919
2920
2921 skBagFieldType_t
skBagKeyFieldName(const skBag_t * bag,char * buf,size_t buflen)2922 skBagKeyFieldName(
2923 const skBag_t *bag,
2924 char *buf,
2925 size_t buflen)
2926 {
2927 const bag_field_info_t *bf;
2928
2929 bf = BAG_GET_FIELD_INFO(bag->key_type);
2930 if (NULL == bf) {
2931 bf = &bag_field_info_custom;
2932 }
2933 if (buf && buflen) {
2934 strncpy(buf, bf->name, buflen);
2935 buf[buflen-1] = '\0';
2936 }
2937
2938 return bag->key_type;
2939 }
2940
2941
2942 skBagFieldType_t
skBagKeyFieldType(const skBag_t * bag)2943 skBagKeyFieldType(
2944 const skBag_t *bag)
2945 {
2946 return bag->key_type;
2947 }
2948
2949
2950 /* Read Bag from filename---a wrapper around skBagRead(). */
2951 skBagErr_t
skBagLoad(skBag_t ** bag,const char * filename)2952 skBagLoad(
2953 skBag_t **bag,
2954 const char *filename)
2955 {
2956 skstream_t *stream = NULL;
2957 skBagErr_t err = SKBAG_OK;
2958 ssize_t rv;
2959
2960 if (NULL == filename || NULL == bag) {
2961 return SKBAG_ERR_INPUT;
2962 }
2963
2964 if ((rv = skStreamCreate(&stream, SK_IO_READ, SK_CONTENT_SILK))
2965 || (rv = skStreamBind(stream, filename))
2966 || (rv = skStreamOpen(stream)))
2967 {
2968 skStreamPrintLastErr(stream, rv, &skAppPrintErr);
2969 err = SKBAG_ERR_READ;
2970 goto END;
2971 }
2972
2973 err = skBagRead(bag, stream);
2974
2975 END:
2976 skStreamDestroy(&stream);
2977 return err;
2978 }
2979
2980
2981 skBagErr_t
skBagModify(skBag_t * bag,skBagFieldType_t key_type,skBagFieldType_t counter_type,size_t key_octets,size_t counter_octets)2982 skBagModify(
2983 skBag_t *bag,
2984 skBagFieldType_t key_type,
2985 skBagFieldType_t counter_type,
2986 size_t key_octets,
2987 size_t counter_octets)
2988 {
2989 skBag_t *cpy = NULL;
2990 skBagIterator_t *iter = NULL;
2991 skBagTypedKey_t key;
2992 skBagTypedCounter_t counter;
2993 skBagErr_t rv;
2994
2995 /* a value of SKBAG_OCTETS_NO_CHANGE means keep the current size */
2996 if (SKBAG_OCTETS_NO_CHANGE == key_octets) {
2997 key_octets = bag->key_octets;
2998 } else if (SKBAG_OCTETS_FIELD_DEFAULT == key_octets) {
2999 key_octets = skBagFieldTypeGetLength(key_type);
3000 }
3001 if (SKBAG_OCTETS_NO_CHANGE == counter_octets) {
3002 counter_octets = sizeof(uint64_t);
3003 } else if (SKBAG_OCTETS_FIELD_DEFAULT == counter_octets) {
3004 counter_octets = skBagFieldTypeGetLength(counter_type);
3005 }
3006
3007 if (bag->key_octets == key_octets) {
3008 /* only need to change the types */
3009 bag->key_type = key_type;
3010 bag->counter_type = counter_type;
3011 return SKBAG_OK;
3012 }
3013
3014 rv = skBagCreateTyped(&cpy, key_type, counter_type,
3015 key_octets, counter_octets);
3016 if (rv) {
3017 goto END;
3018 }
3019
3020 /* Use the new octet lengths to set the type of the key and the
3021 * counter used by the iterator */
3022 switch (key_octets) {
3023 case 1:
3024 key.type = SKBAG_KEY_U8;
3025 break;
3026 case 2:
3027 key.type = SKBAG_KEY_U16;
3028 break;
3029 case 4:
3030 key.type = SKBAG_KEY_U32;
3031 break;
3032 case 16:
3033 key.type = SKBAG_KEY_IPADDR;
3034 break;
3035 default:
3036 skAbortBadCase(key_octets);
3037 }
3038 switch (counter_octets) {
3039 case 8:
3040 counter.type = SKBAG_COUNTER_U64;
3041 break;
3042 default:
3043 skAbortBadCase(key_octets);
3044 }
3045 rv = skBagIteratorCreateUnsorted(bag, &iter);
3046 if (rv) {
3047 goto END;
3048 }
3049 while (skBagIteratorNextTyped(iter, &key, &counter) == SKBAG_OK) {
3050 rv = skBagCounterSet(cpy, &key, &counter);
3051 if (rv) {
3052 goto END;
3053 }
3054 }
3055
3056 /* copy misc data from 'bag' to 'cpy' */
3057 cpy->no_autoconvert = bag->no_autoconvert;
3058
3059 END:
3060 if (iter) {
3061 skBagIteratorDestroy(iter);
3062 }
3063 if (SKBAG_OK == rv) {
3064 /* swap the innards of 'bag' and 'cpy' */
3065 skBag_t tmp;
3066 memcpy(&tmp, bag, sizeof(skBag_t));
3067 memcpy(bag, cpy, sizeof(skBag_t));
3068 memcpy(cpy, &tmp, sizeof(skBag_t));
3069 }
3070 skBagDestroy(&cpy);
3071 return rv;
3072 }
3073
3074
3075 /* print statistics for the bag */
3076 skBagErr_t
skBagPrintTreeStats(const skBag_t * bag,skstream_t * stream_out)3077 skBagPrintTreeStats(
3078 const skBag_t *bag,
3079 skstream_t *stream_out)
3080 {
3081 bagstats_t stats;
3082
3083 if (NULL == bag || NULL == stream_out) {
3084 return SKBAG_ERR_INPUT;
3085 }
3086
3087 bagComputeStats(bag, &stats);
3088
3089 skStreamPrint(stream_out, ("%18s: %" PRIu64 " (%" PRIu64 " bytes)\n"),
3090 "nodes allocated",
3091 stats.nodes, stats.nodes_size);
3092
3093 skStreamPrint(stream_out, "%18s: %.02f%%\n",
3094 "counter density",
3095 (100.0 * (double)stats.unique_keys
3096 / (double)stats.nodes));
3097
3098 #if BAG_STATS_FIND_MIN_MAX
3099 skStreamPrint(stream_out, ("%18s: %" PRIu64 " -> %" PRIu64 "\n"),
3100 "key range",
3101 stats.min_key, stats.max_key);
3102
3103 skStreamPrint(stream_out, ("%18s: %" PRIu64 " -> %" PRIu64 "\n"),
3104 "counter range",
3105 stats.min_counter, stats.max_counter);
3106 #endif /* BAG_STATS_FIND_MIN_MAX */
3107
3108 return SKBAG_OK;
3109 }
3110
3111
3112 skBagErr_t
skBagProcessStreamTyped(skstream_t * stream_in,void * cb_data,skBagStreamInitFunc_t cb_init_func,skBagStreamEntryFunc_t cb_entry_func)3113 skBagProcessStreamTyped(
3114 skstream_t *stream_in,
3115 void *cb_data,
3116 skBagStreamInitFunc_t cb_init_func,
3117 skBagStreamEntryFunc_t cb_entry_func)
3118 {
3119 skBag_t *bag = NULL;
3120 sk_file_header_t *hdr;
3121 sk_header_entry_t *hentry;
3122 int swap_flag;
3123 sk_file_version_t bag_version;
3124 size_t key_read_len;
3125 size_t counter_read_len;
3126 size_t entry_read_len;
3127 const bag_field_info_t *bf;
3128 skBagErr_t err = SKBAG_OK;
3129 skBagTypedKey_t key;
3130 skBagTypedCounter_t counter;
3131 uint32_t bits;
3132 ssize_t b;
3133 uint8_t entrybuf[128];
3134 union val_un {
3135 uint64_t u64;
3136 uint32_t u32;
3137 uint16_t u16;
3138 uint8_t u8;
3139 } val;
3140 ssize_t rv;
3141
3142 if (NULL == stream_in) {
3143 return SKBAG_ERR_INPUT;
3144 }
3145
3146 /* read header */
3147 rv = skStreamReadSilkHeader(stream_in, &hdr);
3148 if (rv) {
3149 skStreamPrintLastErr(stream_in, rv, &skAppPrintErr);
3150 return SKBAG_ERR_READ;
3151 }
3152
3153 rv = skStreamCheckSilkHeader(stream_in, FT_RWBAG, 1,
3154 RWBAG_FILE_VERS_KEY_VARIES, &skAppPrintErr);
3155 if (rv) {
3156 return SKBAG_ERR_HEADER;
3157 }
3158
3159 bag_version = skHeaderGetRecordVersion(hdr);
3160 if ((bag_version <= RWBAG_FILE_VERS_NO_COMPR) &&
3161 (SK_COMPMETHOD_NONE != skHeaderGetCompressionMethod(hdr)))
3162 {
3163 /*skAppPrintErr("Bag files prior to v2 do not support compression");*/
3164 return SKBAG_ERR_HEADER;
3165 }
3166
3167 swap_flag = !skHeaderIsNativeByteOrder(hdr);
3168
3169 /* allocate a bag so that the key and counter types and lengths
3170 * can be queried by the callback */
3171 bag = (skBag_t*)calloc(1, sizeof(skBag_t));
3172 if (NULL == bag) {
3173 return SKBAG_ERR_MEMORY;
3174 }
3175
3176 /* size of key and counter on disk. initialize assuming file
3177 * version v2 or v3 */
3178 key_read_len = sizeof(uint32_t);
3179 counter_read_len = sizeof(uint64_t);
3180
3181 if (RWBAG_FILE_VERS_COUNTER32 == bag_version) {
3182 /* file version v1 used 32bit counters */
3183 counter_read_len = sizeof(uint32_t);
3184 }
3185
3186 hentry = skHeaderGetFirstMatch(hdr, SK_HENTRY_BAG_ID);
3187 if (NULL == hentry) {
3188 /* file has no header entry, must be a pre-SiLK-3.0 file */
3189 if (RWBAG_FILE_VERS_KEY_VARIES <= bag_version) {
3190 /* this file version didn't exist prior to SiLK-3.0;
3191 * something is wrong */
3192 err = SKBAG_ERR_HEADER;
3193 goto END;
3194 }
3195 bag->key_type = SKBAG_FIELD_CUSTOM;
3196 bag->key_octets = (uint16_t)key_read_len;
3197 bag->counter_type = SKBAG_FIELD_CUSTOM;
3198 } else {
3199 /* SiLK-3.0 or later file; may have fixed or variable key and
3200 * counter sizes */
3201 if (RWBAG_FILE_VERS_KEY_VARIES == bag_version) {
3202 /* binary lengths of keys/counters vary */
3203 key_read_len = bagHentryGetKeyLength(hentry);
3204 counter_read_len = bagHentryGetCounterLength(hentry);
3205 }
3206
3207 bag->key_type = (skBagFieldType_t)bagHentryGetKeyType(hentry);
3208 bf = BAG_GET_FIELD_INFO(bag->key_type);
3209 if (NULL == bf) {
3210 /* don't recognize the field type; treat as custom */
3211 bag->key_type = SKBAG_FIELD_CUSTOM;
3212 bag->key_octets = bagHentryGetKeyLength(hentry);
3213 } else if (bf->octets == SKBAG_OCTETS_CUSTOM) {
3214 /* type was explicitly custom, get length from header */
3215 bag->key_octets = bagHentryGetKeyLength(hentry);
3216 } else {
3217 /* type is known; use the type's standard length unless it
3218 * is larger than the on-disk key size */
3219 bag->key_octets = (uint16_t)bf->octets;
3220 if (bag->key_octets > key_read_len) {
3221 bag->key_octets = (uint16_t)key_read_len;
3222 }
3223 }
3224
3225 bag->counter_type = (skBagFieldType_t)bagHentryGetCounterType(hentry);
3226 if (NULL == BAG_GET_FIELD_INFO(bag->counter_type)) {
3227 /* don't recognize the field type; treat as custom */
3228 bag->counter_type = SKBAG_FIELD_CUSTOM;
3229 }
3230 /* counter octets is always 8 */
3231 }
3232
3233 /* check that the lengths are not 0 and not too long, and verify
3234 * that everything is a power of 2 */
3235 BITS_IN_WORD32(&bits, bag->key_octets);
3236 if ((bag->key_octets > 16) || (bag->key_octets == 8) || (bits != 1)) {
3237 err = SKBAG_ERR_HEADER;
3238 goto END;
3239 }
3240 BITS_IN_WORD32(&bits, (uint32_t)key_read_len);
3241 if ((key_read_len > 16) || (key_read_len == 8) || (bits != 1)) {
3242 err = SKBAG_ERR_HEADER;
3243 goto END;
3244 }
3245 BITS_IN_WORD32(&bits, (uint32_t)counter_read_len);
3246 if ((counter_read_len > 8) || (bits != 1)) {
3247 err = SKBAG_ERR_HEADER;
3248 goto END;
3249 }
3250
3251 /* cannot read IPv6 bags in an IPv4-only compile of SiLK */
3252 #if !SK_ENABLE_IPV6
3253 if (key_read_len == 16 || bag->key_octets == 16) {
3254 err = SKBAG_ERR_HEADER;
3255 goto END;
3256 }
3257 #endif
3258
3259 /* compute size of a complete entry, and double check that sizes
3260 * are reasonable */
3261 entry_read_len = key_read_len + counter_read_len;
3262 if (entry_read_len > sizeof(entrybuf)) {
3263 skAbort();
3264 }
3265
3266 /* call the skBagStreamInitFunc_t */
3267 if (cb_init_func) {
3268 err = cb_init_func(bag, cb_data);
3269 if (SKBAG_OK != err) {
3270 goto END;
3271 }
3272 }
3273
3274 /* set up is complete; read key/counter pairs */
3275 while ((b = skStreamRead(stream_in, &entrybuf, entry_read_len))
3276 == (ssize_t)entry_read_len)
3277 {
3278 /* get the counter first */
3279 switch (counter_read_len) {
3280 case 1:
3281 BAG_COUNTER_SET(&counter, entrybuf[key_read_len]);
3282 break;
3283 case 2:
3284 #if SKBAG_USE_MEMCPY
3285 memcpy(&val.u16, (entrybuf + key_read_len), sizeof(val.u16));
3286 #else
3287 val.u16 = *(uint16_t*)(entrybuf + key_read_len);
3288 #endif
3289 if (swap_flag) {
3290 BAG_COUNTER_SET(&counter, BSWAP16(val.u16));
3291 } else {
3292 BAG_COUNTER_SET(&counter, val.u16);
3293 }
3294 break;
3295 case 4:
3296 #if SKBAG_USE_MEMCPY
3297 memcpy(&val.u32, (entrybuf + key_read_len), sizeof(val.u32));
3298 #else
3299 val.u32 = *(uint32_t*)(entrybuf + key_read_len);
3300 #endif
3301 if (swap_flag) {
3302 BAG_COUNTER_SET(&counter, BSWAP32(val.u32));
3303 } else {
3304 BAG_COUNTER_SET(&counter, val.u32);
3305 }
3306 break;
3307 case 8:
3308 #if SKBAG_USE_MEMCPY
3309 memcpy(&val.u64, (entrybuf + key_read_len), sizeof(val.u64));
3310 #else
3311 val.u64 = *(uint64_t*)(entrybuf + key_read_len);
3312 #endif
3313 if (swap_flag) {
3314 BAG_COUNTER_SET(&counter, BSWAP64(val.u64));
3315 } else {
3316 BAG_COUNTER_SET(&counter, val.u64);
3317 }
3318 break;
3319 default:
3320 skAbortBadCase(key_read_len);
3321 }
3322
3323 /* get the key and invoke the callback */
3324 switch (key_read_len) {
3325 case 1:
3326 key.type = SKBAG_KEY_U32;
3327 key.val.u32 = (uint32_t)entrybuf[0];
3328 err = cb_entry_func(bag, &key, &counter, cb_data);
3329 break;
3330
3331 case 2:
3332 #if SKBAG_USE_MEMCPY
3333 memcpy(&val.u16, entrybuf, sizeof(val.u16));
3334 #else
3335 val.u16 = *(uint16_t*)entrybuf;
3336 #endif
3337 key.type = SKBAG_KEY_U32;
3338 if (swap_flag) {
3339 key.val.u32 = (uint32_t)BSWAP16(val.u16);
3340 } else {
3341 key.val.u32 = (uint32_t)val.u16;
3342 }
3343 err = cb_entry_func(bag, &key, &counter, cb_data);
3344 break;
3345
3346 case 4:
3347 #if SKBAG_USE_MEMCPY
3348 memcpy(&val.u32, entrybuf, sizeof(val.u32));
3349 #else
3350 val.u32 = *(uint32_t*)entrybuf;
3351 #endif
3352 key.type = SKBAG_KEY_U32;
3353 if (swap_flag) {
3354 key.val.u32 = (uint32_t)BSWAP32(val.u32);
3355 } else {
3356 key.val.u32 = (uint32_t)val.u32;
3357 }
3358 err = cb_entry_func(bag, &key, &counter, cb_data);
3359 break;
3360
3361 #if SK_ENABLE_IPV6
3362 case 16:
3363 key.type = SKBAG_KEY_IPADDR;
3364 skipaddrSetV6(&key.val.addr, entrybuf);
3365 err = cb_entry_func(bag, &key, &counter, cb_data);
3366 break;
3367 #endif
3368
3369 case 8:
3370 default:
3371 skAbortBadCase(key_read_len);
3372 }
3373
3374 if (err != SKBAG_OK) {
3375 goto END;
3376 }
3377 }
3378
3379 /* check for a read error or a partially read entry */
3380 if (b != 0) {
3381 if (b == -1) {
3382 skStreamPrintLastErr(stream_in, b, &skAppPrintErr);
3383 } else {
3384 skAppPrintErr("Short read");
3385 }
3386 err = SKBAG_ERR_READ;
3387 goto END;
3388 }
3389
3390 err = SKBAG_OK;
3391
3392 END:
3393 if (bag) {
3394 skBagDestroy(&bag);
3395 }
3396 return err;
3397 }
3398
3399
3400 /* create bag and fill it with contents from file */
3401 skBagErr_t
skBagRead(skBag_t ** bag,skstream_t * stream_in)3402 skBagRead(
3403 skBag_t **bag,
3404 skstream_t *stream_in)
3405 {
3406 if (NULL == bag) {
3407 return SKBAG_ERR_INPUT;
3408 }
3409
3410 return skBagProcessStreamTyped(stream_in, bag, &bagProcessStreamInitRead,
3411 &bagProcessStreamEntryRead);
3412 }
3413
3414
3415 /* The prototype for this function is in skheader_priv.h */
3416 int
skBagRegisterHeaderEntry(sk_hentry_type_id_t entry_id)3417 skBagRegisterHeaderEntry(
3418 sk_hentry_type_id_t entry_id)
3419 {
3420 assert(SK_HENTRY_BAG_ID == entry_id);
3421 return (skHentryTypeRegister(
3422 entry_id, &bagHentryPacker, &bagHentryUnpacker,
3423 &bagHentryCopy, &bagHentryFree, &bagHentryPrint));
3424 }
3425
3426
3427 /* Write 'bag' to 'filename'--a wrapper around skBagWrite(). */
3428 skBagErr_t
skBagSave(const skBag_t * bag,const char * filename)3429 skBagSave(
3430 const skBag_t *bag,
3431 const char *filename)
3432 {
3433 skstream_t *stream = NULL;
3434 skBagErr_t err = SKBAG_OK;
3435 ssize_t rv;
3436
3437 if (NULL == filename || NULL == bag) {
3438 return SKBAG_ERR_INPUT;
3439 }
3440
3441 if ((rv = skStreamCreate(&stream, SK_IO_WRITE, SK_CONTENT_SILK))
3442 || (rv = skStreamBind(stream, filename))
3443 || (rv = skStreamOpen(stream)))
3444 {
3445 skStreamPrintLastErr(stream, rv, &skAppPrintErr);
3446 err = SKBAG_ERR_OUTPUT;
3447 goto END;
3448 }
3449
3450 err = skBagWrite(bag, stream);
3451
3452 rv = skStreamClose(stream);
3453 if (rv) {
3454 skStreamPrintLastErr(stream, rv, &skAppPrintErr);
3455 err = SKBAG_ERR_OUTPUT;
3456 }
3457
3458 END:
3459 skStreamDestroy(&stream);
3460 return err;
3461 }
3462
3463
3464 const char *
skBagStrerror(skBagErr_t err_code)3465 skBagStrerror(
3466 skBagErr_t err_code)
3467 {
3468 static char err_buf[32];
3469
3470 switch (err_code) {
3471 case SKBAG_OK:
3472 return "Success";
3473 case SKBAG_ERR_MEMORY:
3474 return "Memory allocation error";
3475 case SKBAG_ERR_KEY_NOT_FOUND:
3476 return "No more entries in bag";
3477 case SKBAG_ERR_INPUT:
3478 return "Invalid argument to function";
3479 case SKBAG_ERR_OP_BOUNDS:
3480 return "Overflow/Underflow in counter";
3481 case SKBAG_ERR_OUTPUT:
3482 return "Error writing to stream";
3483 case SKBAG_ERR_READ:
3484 return "Error reading from stream";
3485 case SKBAG_ERR_HEADER:
3486 return "File header values incompatible with this compile of SiLK";
3487 case SKBAG_ERR_KEY_RANGE:
3488 return "Key out of range for bag";
3489 case SKBAG_ERR_MODIFIED:
3490 return "Bag modified during iteration";
3491 }
3492
3493 snprintf(err_buf, sizeof(err_buf), "Unknown Error #%d", (int)err_code);
3494 return err_buf;
3495 }
3496
3497
3498 /* write bag to file */
3499 skBagErr_t
skBagWrite(const skBag_t * bag,skstream_t * stream_out)3500 skBagWrite(
3501 const skBag_t *bag,
3502 skstream_t *stream_out)
3503 {
3504 sk_file_header_t *hdr;
3505 sk_header_entry_t *bag_hdr;
3506 uint32_t key;
3507 uint64_t counter;
3508 skBagIterator_t *iter = NULL;
3509 ssize_t rv;
3510
3511 if (NULL == bag || NULL == stream_out) {
3512 return SKBAG_ERR_INPUT;
3513 }
3514
3515 hdr = skStreamGetSilkHeader(stream_out);
3516 skHeaderSetByteOrder(hdr, SILK_ENDIAN_NATIVE);
3517 skHeaderSetFileFormat(hdr, FT_RWBAG);
3518
3519 if (bag->key_octets <= 4) {
3520 /* write a SiLK-2 compatible bag */
3521 skHeaderSetRecordVersion(hdr, RWBAG_FILE_VERS_KEY_FIXED);
3522 skHeaderSetRecordLength(hdr, sizeof(uint32_t) + sizeof(uint64_t));
3523 bag_hdr = bagHentryCreate(bag->key_type, (uint16_t)sizeof(uint32_t),
3524 bag->counter_type,
3525 (uint16_t)sizeof(uint64_t));
3526 } else {
3527 /* write a SiLK-3.x+ style bag */
3528 skHeaderSetRecordVersion(hdr, RWBAG_FILE_VERS_KEY_VARIES);
3529 skHeaderSetRecordLength(hdr, bag->key_octets + sizeof(uint64_t));
3530 bag_hdr = bagHentryCreate(bag->key_type, bag->key_octets,
3531 bag->counter_type,
3532 (uint16_t)sizeof(uint64_t));
3533 }
3534 if (NULL == bag_hdr) {
3535 return SKBAG_ERR_MEMORY;
3536 }
3537
3538 rv = skHeaderAddEntry(hdr, bag_hdr);
3539 if (rv) {
3540 bagHentryFree(bag_hdr);
3541 return SKBAG_ERR_MEMORY;
3542 }
3543
3544 /* output header */
3545 rv = skStreamWriteSilkHeader(stream_out);
3546 if (rv) {
3547 return SKBAG_ERR_OUTPUT;
3548 }
3549
3550 /* write key/counter pairs */
3551 switch (bag->key_octets) {
3552 case 1:
3553 case 2:
3554 case 4:
3555 rv = skBagIteratorCreate(bag, &iter);
3556 if (rv) {
3557 return SKBAG_ERR_MEMORY;
3558 }
3559 while (bagtreeIterNext(iter, &key, &counter)) {
3560 rv = skStreamWrite(stream_out, &key, sizeof(uint32_t));
3561 rv += skStreamWrite(stream_out, &counter, sizeof(uint64_t));
3562 if (rv != sizeof(uint32_t)+sizeof(uint64_t)) {
3563 skBagIteratorDestroy(iter);
3564 return SKBAG_ERR_OUTPUT;
3565 }
3566 }
3567 skBagIteratorDestroy(iter);
3568 break;
3569
3570 #if SK_ENABLE_IPV6
3571 case 16:
3572 {
3573 RBLIST *rb_iter;
3574 const bag_keycount128_t *node;
3575
3576 rb_iter = rbopenlist(bag->d.b_rbt->tree);
3577 if (NULL == rb_iter) {
3578 return SKBAG_ERR_MEMORY;
3579 }
3580 assert(sizeof(*node) == bag->key_octets + sizeof(uint64_t));
3581 while ((node = (const bag_keycount128_t*)rbreadlist(rb_iter))
3582 != NULL)
3583 {
3584 rv = skStreamWrite(stream_out, node, sizeof(*node));
3585 if (rv != (int)sizeof(*node)) {
3586 rbcloselist(rb_iter);
3587 return SKBAG_ERR_OUTPUT;
3588 }
3589 }
3590 rbcloselist(rb_iter);
3591 }
3592 break;
3593 #endif /* SK_ENABLE_IPV6 */
3594
3595 case 8:
3596 default:
3597 skAbortBadCase(bag->key_octets);
3598 }
3599
3600 rv = skStreamFlush(stream_out);
3601 if (rv) {
3602 return SKBAG_ERR_OUTPUT;
3603 }
3604
3605 return SKBAG_OK;
3606 }
3607
3608
3609 /* ******************************************************** */
3610 /* LEGACY FUNCTIONS */
3611 /* ******************************************************** */
3612
3613
3614 #include <silk/bagtree.h>
3615
3616 #define MIN_LEVELS 1
3617 #define MAX_LEVELS 32
3618 #define MIN_KEY_SIZE 8
3619 #define MAX_KEY_SIZE 128
3620 #define MIN_LEVEL_BITS 1
3621 #define MAX_LEVEL_BITS 128
3622
3623
3624 typedef struct bag_legacy_proc_stream_st {
3625 skBagStreamFunc_t leg_func;
3626 void *leg_data;
3627 } bag_legacy_proc_stream_t;
3628
3629
3630 /*
3631 * Callback invoked by skBagProcessStreamTyped() to implement the
3632 * callback used by the legacy skBagProcessStream(), which expects a
3633 * signature of
3634 *
3635 * static skBagErr_t bagLegacyProcessStream(
3636 * const skBagKey_t *key,
3637 * const skBagCounter_t *counter,
3638 * void *cb_data);
3639 *
3640 */
3641 static skBagErr_t
bagLegacyProcessStream(const skBag_t UNUSED (* fake_bag),const skBagTypedKey_t * key,const skBagTypedCounter_t * counter,void * cb_data)3642 bagLegacyProcessStream(
3643 const skBag_t UNUSED(*fake_bag),
3644 const skBagTypedKey_t *key,
3645 const skBagTypedCounter_t *counter,
3646 void *cb_data)
3647 {
3648 bag_legacy_proc_stream_t *leg = (bag_legacy_proc_stream_t*)cb_data;
3649
3650 return leg->leg_func(&key->val.u32, &counter->val.u64, leg->leg_data);
3651 }
3652
3653
3654 skBagErr_t
skBagAddToCounter(skBag_t * bag,const skBagKey_t * key,const skBagCounter_t * counter_add)3655 skBagAddToCounter(
3656 skBag_t *bag,
3657 const skBagKey_t *key,
3658 const skBagCounter_t *counter_add)
3659 {
3660 skBagTypedKey_t k;
3661 skBagTypedCounter_t c;
3662
3663 k.type = SKBAG_KEY_U32;
3664 k.val.u32 = *key;
3665 c.type = SKBAG_COUNTER_U64;
3666 c.val.u64 = *counter_add;
3667
3668 return skBagCounterAdd(bag, &k, &c, NULL);
3669 }
3670
3671
3672 /* create a bag */
3673 skBagErr_t
skBagAlloc(skBag_t ** bag,skBagLevel_t levels,const skBagLevelsize_t * level_sizes)3674 skBagAlloc(
3675 skBag_t **bag,
3676 skBagLevel_t levels,
3677 const skBagLevelsize_t *level_sizes)
3678 {
3679 uint32_t key_bits = 0;
3680 uint32_t high_bits;
3681 skBagLevel_t lvl;
3682
3683 /* check the level array */
3684 if (levels < MIN_LEVELS || levels > MAX_LEVELS || NULL == level_sizes) {
3685 return SKBAG_ERR_INPUT;
3686 }
3687
3688 /* count total number of bits */
3689 for (lvl = 0; lvl < levels; ++lvl) {
3690 if (level_sizes[lvl] < MIN_LEVEL_BITS ||
3691 level_sizes[lvl] > MAX_LEVEL_BITS)
3692 {
3693 return SKBAG_ERR_INPUT;
3694 }
3695 key_bits += level_sizes[lvl];
3696 }
3697 if (key_bits < MIN_KEY_SIZE || key_bits > MAX_KEY_SIZE) {
3698 return SKBAG_ERR_INPUT;
3699 }
3700
3701 /* must be a power of 2 */
3702 BITS_IN_WORD32(&high_bits, key_bits);
3703 if (high_bits != 1) {
3704 return SKBAG_ERR_INPUT;
3705 }
3706
3707 return skBagCreateTyped(bag, SKBAG_FIELD_CUSTOM, SKBAG_FIELD_CUSTOM,
3708 key_bits / CHAR_BIT, sizeof(skBagCounter_t));
3709 }
3710
3711
3712 skBagErr_t
skBagDecrementCounter(skBag_t * bag,const skBagKey_t * key)3713 skBagDecrementCounter(
3714 skBag_t *bag,
3715 const skBagKey_t *key)
3716 {
3717 skBagTypedKey_t k;
3718
3719 k.type = SKBAG_KEY_U32;
3720 k.val.u32 = *key;
3721
3722 return skBagCounterSubtract(bag, &k, skbag_counter_incr, NULL);
3723 }
3724
3725
3726 /* destroy a bag */
3727 skBagErr_t
skBagFree(skBag_t * bag)3728 skBagFree(
3729 skBag_t *bag)
3730 {
3731 if (NULL == bag) {
3732 return SKBAG_ERR_INPUT;
3733 }
3734 skBagDestroy(&bag);
3735 return SKBAG_OK;
3736 }
3737
3738
3739 skBagErr_t
skBagGetCounter(skBag_t * bag,const skBagKey_t * key,skBagCounter_t * counter)3740 skBagGetCounter(
3741 skBag_t *bag,
3742 const skBagKey_t *key,
3743 skBagCounter_t *counter)
3744 {
3745 skBagTypedKey_t k;
3746 skBagTypedCounter_t c;
3747 skBagErr_t rv;
3748
3749 k.type = SKBAG_KEY_U32;
3750 k.val.u32 = *key;
3751
3752 rv = skBagCounterGet(bag, &k, &c);
3753 if (SKBAG_OK == rv) {
3754 *counter = c.val.u64;
3755 }
3756 return rv;
3757 }
3758
3759
3760 skBagErr_t
skBagIncrCounter(skBag_t * bag,const skBagKey_t * key)3761 skBagIncrCounter(
3762 skBag_t *bag,
3763 const skBagKey_t *key)
3764 {
3765 skBagTypedKey_t k;
3766
3767 k.type = SKBAG_KEY_U32;
3768 k.val.u32 = *key;
3769
3770 return skBagCounterAdd(bag, &k, skbag_counter_incr, NULL);
3771 }
3772
3773
3774 /* return next key/counter pair */
3775 skBagErr_t
skBagIteratorNext(skBagIterator_t * iter,skBagKey_t * key,skBagCounter_t * counter)3776 skBagIteratorNext(
3777 skBagIterator_t *iter,
3778 skBagKey_t *key,
3779 skBagCounter_t *counter)
3780 {
3781 skBagTypedKey_t k;
3782 skBagTypedCounter_t c;
3783 skBagErr_t rv;
3784
3785 k.type = SKBAG_KEY_U32;
3786 c.type = SKBAG_COUNTER_U64;
3787 rv = skBagIteratorNextTyped(iter, &k, &c);
3788 if (SKBAG_OK == rv) {
3789 *key = k.val.u32;
3790 *counter = c.val.u64;
3791 }
3792 return rv;
3793 }
3794
3795
3796 skBagErr_t
skBagProcessStream(skstream_t * stream,void * cb_data,skBagStreamFunc_t cb_func)3797 skBagProcessStream(
3798 skstream_t *stream,
3799 void *cb_data,
3800 skBagStreamFunc_t cb_func)
3801 {
3802 bag_legacy_proc_stream_t leg;
3803
3804 leg.leg_func = cb_func;
3805 leg.leg_data = cb_data;
3806
3807 return skBagProcessStreamTyped(stream, &leg, NULL, bagLegacyProcessStream);
3808 }
3809
3810
3811 skBagErr_t
skBagRemoveKey(skBag_t * bag,const skBagKey_t * key)3812 skBagRemoveKey(
3813 skBag_t *bag,
3814 const skBagKey_t *key)
3815 {
3816 skBagTypedKey_t k;
3817
3818 k.type = SKBAG_KEY_U32;
3819 k.val.u32 = *key;
3820
3821 return skBagCounterSet(bag, &k, skbag_counter_zero);
3822 }
3823
3824
3825 skBagErr_t
skBagSetCounter(skBag_t * bag,const skBagKey_t * key,const skBagCounter_t * counter)3826 skBagSetCounter(
3827 skBag_t *bag,
3828 const skBagKey_t *key,
3829 const skBagCounter_t *counter)
3830 {
3831 skBagTypedKey_t k;
3832 skBagTypedCounter_t c;
3833
3834 k.type = SKBAG_KEY_U32;
3835 k.val.u32 = *key;
3836 c.type = SKBAG_COUNTER_U64;
3837 c.val.u64 = *counter;
3838
3839 return skBagCounterSet(bag, &k, &c);
3840 }
3841
3842
3843 skBagErr_t
skBagSubtractFromCounter(skBag_t * bag,const skBagKey_t * key,const skBagCounter_t * counter_sub)3844 skBagSubtractFromCounter(
3845 skBag_t *bag,
3846 const skBagKey_t *key,
3847 const skBagCounter_t *counter_sub)
3848 {
3849 skBagTypedKey_t k;
3850 skBagTypedCounter_t c;
3851
3852 k.type = SKBAG_KEY_U32;
3853 k.val.u32 = *key;
3854 c.type = SKBAG_COUNTER_U64;
3855 c.val.u64 = *counter_sub;
3856
3857 return skBagCounterSubtract(bag, &k, &c, NULL);
3858 }
3859
3860
3861 /*
3862 ** Local Variables:
3863 ** mode:c
3864 ** indent-tabs-mode:nil
3865 ** c-basic-offset:4
3866 ** End:
3867 */
3868