1 /*
2 ** Copyright (C) 2016-2020 by Carnegie Mellon University.
3 **
4 ** @OPENSOURCE_LICENSE_START@
5 ** See license information in ../../LICENSE.txt
6 ** @OPENSOURCE_LICENSE_END@
7 */
8
9 #include <silk/silk.h>
10
11 RCSIDENT("$SiLK: skaggbag.c ef14e54179be 2020-04-14 21:57:45Z mthomas $");
12
13 #include <silk/skaggbag.h>
14 #include <silk/skipaddr.h>
15 #include <silk/redblack.h>
16 #include <silk/utils.h>
17 #include "skheader_priv.h"
18
19
20 /*
21 * Provides support for tracing the functions that implement the
22 * AggBag code.
23 */
24 #ifndef AGGBAG_TRACE
25 #define AGGBAG_TRACE 0
26 #endif
27
28
29 /**
30 * ab_layout_t describes the fields that comprise the key or the
31 * counter of an AggBag. The definition of this type is below.
32 */
33 typedef struct ab_layout_st ab_layout_t;
34
35 /**
36 * rbtree_node_t represents the node of the red black tree that is
37 * used to implement the AggBag data structure. The definition of
38 * this type is below.
39 */
40 typedef struct rbtree_node_st rbtree_node_t;
41
42 /**
43 * sk_aggbag_t is the AggBag data structure.
44 */
45 struct sk_aggbag_st {
46 /* Description of the key ([0]) and counter ([1]) fields. */
47 const ab_layout_t *layout[2];
48
49 /* The top of the tree */
50 rbtree_node_t *root;
51 /* Options to use when writing the AggBag */
52 const sk_aggbag_options_t *options;
53 /* Number of items in the tree */
54 size_t size;
55 /* Length of a single data item in the tree */
56 size_t data_len;
57 /* Size to use when allocating an rbtree_node_t */
58 size_t node_size;
59 /* True once certain operations have occurred on the AggBag that
60 * make it impossible to change the fields */
61 unsigned fixed_fields : 1;
62 };
63 /* typedef struct sk_aggbag_st sk_aggbag_t; */
64
65
66 /**
67 * This value must be larger than the maximum SKAGGBAG_FIELD_*
68 * identifier that is supported by the code.
69 */
70 #define AB_LAYOUT_BMAP_SIZE 65536
71
72
73 /**
74 * ab_field_t describes an individual field in the key or counter.
75 * The ab_layout_t has an array of these.
76 */
77 struct ab_field_st {
78 /* The octet length of this field */
79 uint16_t f_len;
80 /* The octet offset of this field from the first field in the
81 * ab_layout_t */
82 uint16_t f_offset;
83 /* The type of this field */
84 sk_aggbag_type_t f_type;
85 };
86 typedef struct ab_field_st ab_field_t;
87
88
89 /*
90 * ab_layout_t describes the fields that comprise the key or the
91 * counter of an AggBag. Create via abLayoutCreate() and destroy
92 * via abLayoutDestroy().
93 */
94 struct ab_layout_st {
95 /* A bitmap of the fields in this layout. Used to compare
96 * layouts between different AggBag structures */
97 BITMAP_DECLARE(bitmap, AB_LAYOUT_BMAP_SIZE);
98 /* Number of times this layout has been referenced */
99 unsigned int ref_count;
100 /* Number of fields in this layout */
101 unsigned int field_count;
102 /* Sum of the octet lengths of the fields in this layout */
103 unsigned int field_octets;
104 /* List of fields in this layout */
105 ab_field_t *fields;
106 };
107 /* typedef struct ab_layout_st ab_layout_t; // ABOVE */
108
109
110 /**
111 * ab_type_info_t is a structure that describes an individual field
112 * type that the AggBag code supports.
113 */
114 struct ab_type_info_st {
115 const char *ti_name;
116 uint8_t ti_octets;
117 sk_aggbag_type_t ti_type;
118 uint8_t ti_key_counter;
119 };
120 typedef struct ab_type_info_st ab_type_info_t;
121
122
123 /*
124 * Whether the custom field is supported. The code assumes this is
125 * off. Enabling the custom field requires more changes than just
126 * setting this parameter to a true value.
127 */
128 #define AB_SUPPORT_CUSTOM 0
129
130
131 /* LOCAL VARIABLES */
132
133 /*
134 * A data structure to hold all the ab_layout_t structures that
135 * have been defined.
136 */
137 static struct rbtree *layouts;
138
139 /*
140 * The number of those layouts.
141 */
142 static unsigned int layouts_count;
143
144
145 static const ab_type_info_t ab_type_info_key[] = {
146 {"sIPv4", 4, SKAGGBAG_FIELD_SIPv4, SK_AGGBAG_KEY},
147 {"dIPv4", 4, SKAGGBAG_FIELD_DIPv4, SK_AGGBAG_KEY},
148 {"sPort", 2, SKAGGBAG_FIELD_SPORT, SK_AGGBAG_KEY},
149 {"dPort", 2, SKAGGBAG_FIELD_DPORT, SK_AGGBAG_KEY},
150 {"protocol", 1, SKAGGBAG_FIELD_PROTO, SK_AGGBAG_KEY},
151 {"packets", 4, SKAGGBAG_FIELD_PACKETS, SK_AGGBAG_KEY},
152 {"bytes", 4, SKAGGBAG_FIELD_BYTES, SK_AGGBAG_KEY},
153 {"flags", 1, SKAGGBAG_FIELD_FLAGS, SK_AGGBAG_KEY},
154 {"sTime", 4, SKAGGBAG_FIELD_STARTTIME, SK_AGGBAG_KEY},
155 {"duration", 4, SKAGGBAG_FIELD_ELAPSED, SK_AGGBAG_KEY},
156 {"eTime", 4, SKAGGBAG_FIELD_ENDTIME, SK_AGGBAG_KEY},
157 {"sensor", 2, SKAGGBAG_FIELD_SID, SK_AGGBAG_KEY},
158 {"input", 2, SKAGGBAG_FIELD_INPUT, SK_AGGBAG_KEY},
159 {"output", 2, SKAGGBAG_FIELD_OUTPUT, SK_AGGBAG_KEY},
160 {"nhIPv4", 4, SKAGGBAG_FIELD_NHIPv4, SK_AGGBAG_KEY},
161 {"initialFlags", 1, SKAGGBAG_FIELD_INIT_FLAGS, SK_AGGBAG_KEY},
162 {"sessionFlags", 1, SKAGGBAG_FIELD_REST_FLAGS, SK_AGGBAG_KEY},
163 {"attributes", 1, SKAGGBAG_FIELD_TCP_STATE, SK_AGGBAG_KEY},
164 {"application", 2, SKAGGBAG_FIELD_APPLICATION, SK_AGGBAG_KEY},
165 {"class", 1, SKAGGBAG_FIELD_FTYPE_CLASS, SK_AGGBAG_KEY},
166 {"type", 1, SKAGGBAG_FIELD_FTYPE_TYPE, SK_AGGBAG_KEY},
167 {NULL,/*sTime-ms*/ 0, SKAGGBAG_FIELD_INVALID, SK_AGGBAG_KEY},
168 {NULL,/*eTime-ms*/ 0, SKAGGBAG_FIELD_INVALID, SK_AGGBAG_KEY},
169 {NULL,/*dur-ms*/ 0, SKAGGBAG_FIELD_INVALID, SK_AGGBAG_KEY},
170 {"icmpType", 1, SKAGGBAG_FIELD_ICMP_TYPE, SK_AGGBAG_KEY},
171 {"icmpCode", 1, SKAGGBAG_FIELD_ICMP_CODE, SK_AGGBAG_KEY},
172 {"sIPv6", 16, SKAGGBAG_FIELD_SIPv6, SK_AGGBAG_KEY},
173 {"dIPv6", 16, SKAGGBAG_FIELD_DIPv6, SK_AGGBAG_KEY},
174 {"nhIPv6", 16, SKAGGBAG_FIELD_NHIPv6, SK_AGGBAG_KEY},
175 {"any-IPv4", 4, SKAGGBAG_FIELD_ANY_IPv4, SK_AGGBAG_KEY},
176 {"any-IPv6", 16, SKAGGBAG_FIELD_ANY_IPv6, SK_AGGBAG_KEY},
177 {"any-port", 2, SKAGGBAG_FIELD_ANY_PORT, SK_AGGBAG_KEY},
178 {"any-snmp", 2, SKAGGBAG_FIELD_ANY_SNMP, SK_AGGBAG_KEY},
179 {"any-time", 4, SKAGGBAG_FIELD_ANY_TIME, SK_AGGBAG_KEY},
180 {"custom-key", 8, SKAGGBAG_FIELD_CUSTOM_KEY, SK_AGGBAG_KEY},
181 {"scc", 2, SKAGGBAG_FIELD_SIP_COUNTRY, SK_AGGBAG_KEY},
182 {"dcc", 2, SKAGGBAG_FIELD_DIP_COUNTRY, SK_AGGBAG_KEY},
183 {"any-cc", 2, SKAGGBAG_FIELD_ANY_COUNTRY, SK_AGGBAG_KEY},
184 {"sip-pmap", 4, SKAGGBAG_FIELD_SIP_PMAP, SK_AGGBAG_KEY},
185 {"dip-pmap", 4, SKAGGBAG_FIELD_DIP_PMAP, SK_AGGBAG_KEY},
186 {"any-ip-pmap", 4, SKAGGBAG_FIELD_ANY_IP_PMAP, SK_AGGBAG_KEY},
187 {"sport-pmap", 4, SKAGGBAG_FIELD_SPORT_PMAP, SK_AGGBAG_KEY},
188 {"dport-pmap", 4, SKAGGBAG_FIELD_DPORT_PMAP, SK_AGGBAG_KEY},
189 {"any-port-pmap", 4, SKAGGBAG_FIELD_ANY_PORT_PMAP, SK_AGGBAG_KEY}
190 };
191
192 static const size_t ab_type_info_key_max = (sizeof(ab_type_info_key)
193 / sizeof(ab_type_info_key[0]));
194
195 static const ab_type_info_t ab_type_info_counter[] = {
196 {"records", 8, SKAGGBAG_FIELD_RECORDS, SK_AGGBAG_COUNTER},
197 {"sum-packets", 8, SKAGGBAG_FIELD_SUM_PACKETS, SK_AGGBAG_COUNTER},
198 {"sum-bytes", 8, SKAGGBAG_FIELD_SUM_BYTES, SK_AGGBAG_COUNTER},
199 {"sum-duration", 8, SKAGGBAG_FIELD_SUM_ELAPSED, SK_AGGBAG_COUNTER},
200 {"custom-counter", 8, SKAGGBAG_FIELD_CUSTOM_COUNTER, SK_AGGBAG_COUNTER}
201 };
202
203 static const size_t ab_type_info_counter_max =
204 (sizeof(ab_type_info_counter) / sizeof(ab_type_info_counter[0]));
205
206
207 #if AB_SUPPORT_CUSTOM
208 #define SKAGGBAG_FIELD_CUSTOM 65535
209 #define KEY_VALUE (SK_AGGBAG_KEY | SK_AGGBAG_COUNTER)
210
211 static const ab_type_info_t ab_custom_info = {
212 "custom", 0, SKAGGBAG_FIELD_CUSTOM, KEY_VALUE
213 };
214 #endif /* AB_SUPPORT_CUSTOM */
215
216
217 /* AGGBAG OPTIONS */
218
219 enum aggbag_options_en {
220 OPT_AGGBAG_INVOCATION_STRIP
221 /* , OPT_AGGBAG_RECORD_VERSION */
222 };
223 static const struct option aggbag_options[] = {
224 {"invocation-strip", NO_ARG, 0, OPT_AGGBAG_INVOCATION_STRIP},
225 /* {"record-version", REQUIRED_ARG, 0, OPT_AGGBAG_RECORD_VERSION}, */
226 {0, 0, 0, 0} /* sentinel entry */
227 };
228 static const char *aggbag_options_help[] = {
229 ("Strip invocation history from the Aggregate Bag\n"
230 "\tfile. Def. Record command used to create the file"),
231 /* "Specify version when writing AggBag records.\n", */
232 (char*)NULL
233 };
234
235
236
237 /* LOCAL FUNCTION PROTOTYPES */
238
239 static int
240 abLayoutFieldSorter(
241 const void *v_a,
242 const void *v_b);
243 static const ab_type_info_t *
244 aggBagGetTypeInfo(
245 uint16_t field_type);
246 static sk_aggbag_type_t
247 aggBagHentryGetFieldType(
248 const sk_header_entry_t *hentry,
249 unsigned int key_counter,
250 unsigned int pos);
251
252
253 /* **************************************************************** */
254 /* **************************************************************** */
255 /* Support for tracing/debuging the code */
256 /* **************************************************************** */
257 /* **************************************************************** */
258
259 #if AGGBAG_TRACE
260 #ifdef SK_HAVE_C99___FUNC__
261 #define ABTRACE_V(...) abTrace(__func__, __LINE__, __VA_ARGS__)
262 #else
263 #define ABTRACE_V(...) abTrace(__FILE__, __LINE__, __VA_ARGS__)
264 #endif /* SK_HAVE_C99___FUNC__ */
265 #define ABTRACEQ_V(...) abTraceQuiet(__VA_ARGS__)
266
267 #define ABTRACE(t_t) ABTRACE_V t_t
268 #define ABTRACEQ(q_q) ABTRACEQ_V q_q
269
270 #define V(v_v) (void *)(v_v)
271
272 static void abTrace(const char *func, int lineno, const char *fmt, ...)
273 SK_CHECK_PRINTF(3, 4);
274 static void abTraceQuiet(const char *fmt, ...)
275 SK_CHECK_PRINTF(1, 2);
276
277 static void
abTrace(const char * func,int lineno,const char * fmt,...)278 abTrace(
279 const char *func,
280 int lineno,
281 const char *fmt,
282 ...)
283 {
284 va_list ap;
285
286 #ifdef SK_HAVE_C99___FUNC__
287 fprintf(stderr, "%s():%d: ", func, lineno);
288 #else
289 fprintf(stderr, "%s:%d: ", func, lineno);
290 #endif
291 va_start(ap, fmt);
292 vfprintf(stderr, fmt, ap);
293 va_end(ap);
294 }
295
296 static void
abTraceQuiet(const char * fmt,...)297 abTraceQuiet(
298 const char *fmt,
299 ...)
300 {
301 va_list ap;
302
303 va_start(ap, fmt);
304 vfprintf(stderr, fmt, ap);
305 va_end(ap);
306 }
307 #endif /* AGGBAG_TRACE */
308
309 #ifndef ABTRACE
310 #define ABTRACE(x_x)
311 #define ABTRACEQ(x_x)
312 #endif /* #ifndef ABTRACE */
313
314
315
316 /* **************************************************************** */
317 /* **************************************************************** */
318 /* AggBag uses a red black tree. This is the rbtree implementation */
319 /* **************************************************************** */
320 /* **************************************************************** */
321
322 /*
323 * Red Black balanced tree library
324 *
325 * This code is based on the following:
326 * http://eternallyconfuzzled.com/jsw_home.aspx
327 *
328 * ************************************************************
329 *
330 * Red Black balanced tree library
331 *
332 * > Created (Julienne Walker): August 23, 2003
333 * > Modified (Julienne Walker): March 14, 2008
334 *
335 * This code is in the public domain. Anyone may
336 * use it or change it in any way that they see
337 * fit. The author assumes no responsibility for
338 * damages incurred through use of the original
339 * code or any variations thereof.
340 *
341 * It is requested, but not required, that due
342 * credit is given to the original author and
343 * anyone who has modified the code through
344 * a header comment, such as this one.
345 *
346 * ************************************************************
347 *
348 */
349
350 /*
351 * rbtree_node_t defines the elements in the red-black tree.
352 *
353 * The size of an rbtree_node_t is variable, though all nodes in a
354 * tree have the same size, which is given by the 'data_len' member
355 * of an sk_aggbag_t.
356 *
357 * The final member of this structure uses bytes 0 to data_len-1
358 * for the data and the final byte (at position 'data_len') for the
359 * color.
360 */
361 struct rbtree_node_st {
362 /* The children: Left (0) and Right (1) */
363 rbtree_node_t *link[2];
364 /* Variable-sized: User-defined content and final byte is color */
365 uint8_t data_color[1];
366 };
367 /* typedef struct rbtree_node_st rbtree_node_t; // ABOVE */
368
369 /**
370 * Since the data-size is variable and the color follows it, create
371 * a structure to hold the maximum sized data object.
372 */
373 struct rbtree_false_root_st {
374 rbtree_node_t *link[2];
375 uint8_t data_color[SKAGGBAG_AGGREGATE_MAXLEN + 1u];
376 };
377 typedef struct rbtree_false_root_st rbtree_false_root_t;
378
379 /**
380 * sk_rbtree_status_t defines the values returned by the functions
381 * declared below.
382 */
383 enum sk_rbtree_status_en {
384 SK_RBTREE_OK = 0,
385 SK_RBTREE_ERR_DUPLICATE = -1,
386 SK_RBTREE_ERR_NOT_FOUND = -2,
387 SK_RBTREE_ERR_ALLOC = -3,
388 SK_RBTREE_ERR_PARAM = -4
389 };
390 typedef enum sk_rbtree_status_en sk_rbtree_status_t;
391
392 /**
393 * Signature of a user-defined function for printing the data.
394 */
395 typedef void
396 (*sk_rbtree_print_data_fn_t)(
397 const sk_aggbag_t *tree,
398 FILE *fp,
399 const void *data);
400
401 /* Tallest allowable tree */
402 #ifndef RBT_HEIGHT_LIMIT
403 #define RBT_HEIGHT_LIMIT 64
404 #endif
405
406 /* Color of a node */
407 #define RBT_BLACK 0
408 #define RBT_RED 1
409
410 /* The tree uses an array[2] for the left and right nodes */
411 #define RBT_LEFT 0
412 #define RBT_RIGHT 1
413
414 /* Typedef for the terminal node */
415 #define RBT_NIL ((rbtree_node_t *)&rbt_false_root)
416
417 /*
418 * Compare the octet array in 'rcd_a' with the array in 'rcd_b' for
419 * the tree 'rcd_tree'.
420 */
421 #define rbtree_compare_data(rcd_tree, rcd_a, rcd_b) \
422 memcmp((rcd_a), (rcd_b), (rcd_tree)->layout[0]->field_octets)
423
424 /*
425 * Return true if 'rnir_node' is red. If the return value is
426 * false, 'rnir_node' must be black.
427 */
428 #define rbtree_node_is_red(rnir_tree, rnir_node) \
429 (RBT_RED == (rnir_node)->data_color[(rnir_tree)->data_len])
430
431 /*
432 * Helper for rbtree_set_node_black(), rbtree_set_node_red()
433 *
434 * Set color of 'rsnc_node' in 'rsnc_tree' to 'rsnc_color'.
435 */
436 #define rbtree_set_node_color(rsnc_tree, rsnc_node, rsnc_color) \
437 (rsnc_node)->data_color[(rsnc_tree)->data_len] = rsnc_color
438
439 /*
440 * Set color of 'rsnb_node' in 'rsnb_tree' to BLACK.
441 */
442 #define rbtree_set_node_black(rsnb_tree, rsnb_node) \
443 rbtree_set_node_color(rsnb_tree, rsnb_node, RBT_BLACK)
444
445 /*
446 * Set color of 'rsnr_node' in 'rsnr_tree' to RED.
447 */
448 #define rbtree_set_node_red(rsnr_tree, rsnr_node) \
449 rbtree_set_node_color(rsnr_tree, rsnr_node, RBT_RED)
450
451 /*
452 * Copy 'rsnd_data' into the node 'rsnd_node' of the tree
453 * 'rsnd_tree'.
454 */
455 #define rbtree_set_node_data(rsnd_tree, rsnd_node, rsnd_data) \
456 memcpy((rsnd_node)->data_color, (rsnd_data), (rsnd_tree)->data_len)
457
458 /**
459 * sk_rbtree_iter_t is a handle for iterating over the objects in
460 * the Red Black Tree Structure.
461 */
462 struct sk_rbtree_iter_st {
463 /* Paired tree */
464 const sk_aggbag_t *tree;
465 /* Current node */
466 const rbtree_node_t *cur;
467 /* Data on previous node */
468 const void *prev_data;
469 /* Traversal path */
470 const rbtree_node_t *path[RBT_HEIGHT_LIMIT];
471 /* Current depth in 'path' */
472 size_t depth;
473 };
474 typedef struct sk_rbtree_iter_st sk_rbtree_iter_t;
475
476 #if 0
477 /*
478 * The red-black tree sk_rbtree_t. Not defined since the
479 * sk_aggbag_t structure incorporates it directly.
480 */
481 struct sk_rbtree_st {
482 /* The top of the tree */
483 rbtree_node_t *root;
484 /* The comparison function */
485 sk_rbtree_cmp_fn_t cmp_fn;
486 /* The data free() function: May be NULL */
487 sk_rbtree_free_fn_t free_fn;
488 /* User's context pointer */
489 const void *ctx;
490 /* Number of items in the tree */
491 size_t size;
492 /* Length of a single data item in the tree */
493 size_t data_len;
494 /* Size to use when allocating an rbtree_node_t */
495 size_t node_size;
496 };
497 typedef struct sk_rbtree_st sk_rbtree_t;
498 #endif /* 0 */
499
500 /* LOCAL VARIABLES */
501
502 /*
503 * Global variable used as the terminal node.
504 */
505 static const rbtree_false_root_t rbt_false_root = {{RBT_NIL, RBT_NIL}, {0}};
506
507 /* FUNCTION DEFINITIONS */
508
509 /**
510 * Perform a single red black rotation in the specified direction.
511 * This function assumes that all nodes are valid for a rotation.
512 *
513 * 'root' is the original root to rotate around.
514 * 'dir' is the direction to rotate (0 = left, 1 = right).
515 *
516 * Return the new root ater rotation
517 */
518 static rbtree_node_t *
rbtree_rotate_single(const sk_aggbag_t * tree,rbtree_node_t * root,int dir)519 rbtree_rotate_single(
520 const sk_aggbag_t *tree,
521 rbtree_node_t *root,
522 int dir)
523 {
524 rbtree_node_t *save = root->link[!dir];
525
526 root->link[!dir] = save->link[dir];
527 save->link[dir] = root;
528
529 rbtree_set_node_red(tree, root);
530 rbtree_set_node_black(tree, save);
531
532 return save;
533 }
534
535
536 /**
537 * Perform a double red black rotation in the specified direction.
538 * This function assumes that all nodes are valid for a rotation.
539 *
540 * 'root' is the original root to rotate around.
541 * 'dir' is the direction to rotate (0 = left, 1 = right).
542 *
543 * Return the new root after rotation.
544 */
545 static rbtree_node_t *
rbtree_rotate_double(const sk_aggbag_t * tree,rbtree_node_t * root,int dir)546 rbtree_rotate_double(
547 const sk_aggbag_t *tree,
548 rbtree_node_t *root,
549 int dir)
550 {
551 root->link[!dir] = rbtree_rotate_single(tree, root->link[!dir], !dir);
552
553 return rbtree_rotate_single(tree, root, dir);
554 }
555
556
557 /**
558 * Initialize the iterator object 'iter' and attach it to 'tree'.
559 * The user-specified direction 'dir' determines whether to begin
560 * iterator at the smallest (0) or largest (1) valued node.
561 *
562 * Return a pointer to the smallest or largest data value.
563 */
564 static void *
rbtree_iter_start(sk_rbtree_iter_t * iter,const sk_aggbag_t * tree,int dir)565 rbtree_iter_start(
566 sk_rbtree_iter_t *iter,
567 const sk_aggbag_t *tree,
568 int dir)
569 {
570 iter->tree = tree;
571 iter->cur = tree->root;
572 iter->depth = 0;
573
574 if (RBT_NIL == iter->cur) {
575 return NULL;
576 }
577 while (iter->cur->link[dir] != RBT_NIL) {
578 assert(iter->depth < RBT_HEIGHT_LIMIT);
579 iter->path[iter->depth++] = iter->cur;
580 iter->cur = iter->cur->link[dir];
581 }
582 return (void*)iter->cur->data_color;
583 }
584
585
586 /**
587 * Move the initialized iterator 'iter' in the user-specified
588 * direction 'dir' (0 = ascending, 1 = descending).
589 *
590 * Return a pointer to the next data value in the specified
591 * direction.
592 *
593 */
594 static void *
rbtree_iter_move(sk_rbtree_iter_t * iter,int dir)595 rbtree_iter_move(
596 sk_rbtree_iter_t *iter,
597 int dir)
598 {
599 if (iter->cur->link[dir] != RBT_NIL) {
600 /* Continue down this branch */
601 assert(iter->depth < RBT_HEIGHT_LIMIT);
602 iter->path[iter->depth++] = iter->cur;
603 iter->cur = iter->cur->link[dir];
604
605 while (iter->cur->link[!dir] != RBT_NIL) {
606 assert(iter->depth < RBT_HEIGHT_LIMIT);
607 iter->path[iter->depth++] = iter->cur;
608 iter->cur = iter->cur->link[!dir];
609 }
610 } else {
611 /* Move to the next branch */
612 const rbtree_node_t *last;
613
614 do {
615 if (0 == iter->depth) {
616 iter->cur = RBT_NIL;
617 return NULL;
618 }
619 last = iter->cur;
620 iter->cur = iter->path[--iter->depth];
621 } while (last == iter->cur->link[dir]);
622 }
623
624 return ((iter->cur == RBT_NIL) ? NULL : (void*)iter->cur->data_color);
625 }
626
627
628 /**
629 * Print the address of the data pointer.
630 *
631 * This is a helper function for rbtree_node_debug_print() to print
632 * the data when the user does not provide a printing function.
633 *
634 * Must have the signature of sk_rbtree_print_data_fn_t.
635 */
636 static void
rbtree_node_default_data_printer(const sk_aggbag_t * tree,FILE * fp,const void * data)637 rbtree_node_default_data_printer(
638 const sk_aggbag_t *tree,
639 FILE *fp,
640 const void *data)
641 {
642 SK_UNUSED_PARAM(tree);
643 fprintf(fp, "%p", (void *)data);
644 }
645
646
647 /**
648 * Print the address of the data pointer.
649 *
650 * This is a helper function for rbtree_node_debug_print() to print
651 * the data when the user does not provide a printing function.
652 */
653 static void
rbtree_node_debug_print(const sk_aggbag_t * tree,const rbtree_node_t * node,FILE * fp,sk_rbtree_print_data_fn_t print_data,int indentation)654 rbtree_node_debug_print(
655 const sk_aggbag_t *tree,
656 const rbtree_node_t *node,
657 FILE *fp,
658 sk_rbtree_print_data_fn_t print_data,
659 int indentation)
660 {
661 unsigned int i;
662
663 if (node != RBT_NIL) {
664 ++indentation;
665 fprintf(fp,
666 "Tree: %*s %p: left=%p, right=%p, color=%s, data=",
667 indentation, "", (void *)node,
668 (void *)node->link[RBT_LEFT], (void *)node->link[RBT_RIGHT],
669 (rbtree_node_is_red(tree, node) ? "RED" : "BLACK"));
670 print_data(tree, fp, node->data_color);
671 fprintf(fp, "\n");
672 for (i = RBT_LEFT; i <= RBT_RIGHT; ++i) {
673 rbtree_node_debug_print(
674 tree, node->link[i], fp, print_data, indentation);
675 }
676 }
677 }
678
679
680 static int
rbtree_assert(const sk_aggbag_t * tree,const rbtree_node_t * root,FILE * fp)681 rbtree_assert(
682 const sk_aggbag_t *tree,
683 const rbtree_node_t *root,
684 FILE *fp)
685 {
686 const rbtree_node_t *ln;
687 const rbtree_node_t *rn;
688 unsigned int lh, rh;
689
690 if (RBT_NIL == root) {
691 return 1;
692 }
693
694 ln = root->link[RBT_LEFT];
695 rn = root->link[RBT_RIGHT];
696
697 /* Consecutive red links */
698 if (rbtree_node_is_red(tree, root)) {
699 if (rbtree_node_is_red(tree, ln) || rbtree_node_is_red(tree, rn)) {
700 fprintf(fp, "Red violation at %p\n", (void *)root);
701 return 0;
702 }
703 }
704
705 lh = rbtree_assert(tree, ln, fp);
706 rh = rbtree_assert(tree, rn, fp);
707
708 /* Invalid binary search tree */
709 if ((ln != RBT_NIL
710 && rbtree_compare_data(tree, ln->data_color, root->data_color) >= 0)
711 || (rn != RBT_NIL
712 && rbtree_compare_data(tree, rn->data_color, root->data_color)<=0))
713 {
714 fprintf(fp, "Binary tree violation at %p\n", (void *)root);
715 return 0;
716 }
717
718 /* Black height mismatch */
719 if (lh != 0 && rh != 0 && lh != rh) {
720 fprintf(fp, "Black violation at %p (left = %u, right = %u\n",
721 (void *)root, lh, rh);
722 return 0;
723 }
724
725 /* Only count black links */
726 if (lh != 0 && rh != 0) {
727 return rbtree_node_is_red(tree, root) ? lh : lh + 1;
728 }
729 return 0;
730 }
731
732
733 /*
734 * Destroy the nodes on the tree.
735 */
736 static void
sk_rbtree_destroy(sk_aggbag_t * tree)737 sk_rbtree_destroy(
738 sk_aggbag_t *tree)
739 {
740 rbtree_node_t *node;
741 rbtree_node_t *save;
742
743 if (!tree || !tree->root || tree->root == RBT_NIL) {
744 return;
745 }
746
747 /* Rotate away the left links so that we can treat this like the
748 * destruction of a linked list */
749 node = tree->root;
750 for (;;) {
751 if (RBT_NIL != node->link[RBT_LEFT]) {
752 /* Rotate away the left link and check again */
753 save = node->link[RBT_LEFT];
754 node->link[RBT_LEFT] = save->link[RBT_RIGHT];
755 save->link[RBT_RIGHT] = node;
756 node = save;
757 } else {
758 /* No left links, just kill the node and move on */
759 save = node->link[RBT_RIGHT];
760 free(node);
761 if (RBT_NIL == save) {
762 break;
763 }
764 node = save;
765 }
766 }
767 }
768
769
770 /*
771 * Find the node in 'tree' that has 'data' as its key.
772 */
773 static rbtree_node_t *
sk_rbtree_find(const sk_aggbag_t * tree,const void * data)774 sk_rbtree_find(
775 const sk_aggbag_t *tree,
776 const void *data)
777 {
778 const rbtree_node_t *node;
779 const uint8_t *u_data = (const uint8_t *)data;
780 size_t i;
781 int cmp;
782
783 assert(tree);
784 assert(tree->data_len);
785
786 ABTRACE(("searching for key ="));
787 for (i = 0; i < tree->layout[0]->field_octets; ++i, ++u_data) {
788 ABTRACEQ((" %02x", *u_data));
789 }
790 ABTRACEQ(("\n"));
791
792 node = tree->root;
793 ABTRACE(("root = %p, RBT_NIL = %p\n", V(node), V(RBT_NIL)));
794 while (node != RBT_NIL) {
795 ABTRACE(("node's data ="));
796 u_data = node->data_color;
797 for (i = 0; i < tree->data_len; ++i, ++u_data) {
798 if (i == tree->layout[0]->field_octets) {
799 ABTRACEQ((" |"));
800 }
801 ABTRACEQ((" %02x", *u_data));
802 }
803 ABTRACEQ((" | %02x\n", *u_data));
804
805 cmp = rbtree_compare_data(tree, node->data_color, data);
806 ABTRACE(("node = %p, cmp = %d\n", V(node), cmp));
807 if (cmp < 0) {
808 node = node->link[RBT_RIGHT];
809 } else if (cmp > 0) {
810 node = node->link[RBT_LEFT];
811 } else {
812 return (rbtree_node_t *)node;
813 }
814 /* If the tree supports duplicates, they should be chained to
815 * the right subtree for this to work */
816 /* node = node->link[cmp < 0]; */
817 }
818 ABTRACE(("return NULL\n"));
819 return NULL;
820 }
821
822
823 /*
824 * Add 'key' and 'counter' to 'tree', overwriting an existing 'key'
825 * with 'counter'.
826 */
827 static int
sk_rbtree_insert(sk_aggbag_t * tree,const void * key_data,const void * counter_data)828 sk_rbtree_insert(
829 sk_aggbag_t *tree,
830 const void *key_data,
831 const void *counter_data)
832 {
833 rbtree_false_root_t head;
834 rbtree_node_t *t, *g, *p, *q;
835 int dir, last, cmp;
836 int inserted = 0;
837 int rv = SK_RBTREE_OK;
838
839 assert(tree);
840 assert(tree->data_len);
841
842 memset(&head, 0, sizeof(head));
843 head.link[0] = head.link[1] = RBT_NIL;
844
845 /* 't' is great-grandparent; 'g' is grandparent; 'p' is parent;
846 * and 'q' is iterator. */
847 t = g = p = (rbtree_node_t *)&head;
848 q = t->link[RBT_RIGHT] = tree->root;
849 dir = last = RBT_RIGHT;
850
851 #if AGGBAG_TRACE
852 {
853 size_t i;
854 const uint8_t *u;
855
856 ABTRACE(("t = p = g = &head = %p, RBT_NIL = %p, q = tree->root = %p",
857 V(t), V(RBT_NIL), V(q)));
858 ABTRACEQ((" data ="));
859 u = (const uint8_t *)key_data;
860 for (i = 0; i < tree->layout[0]->field_octets; ++i, ++u) {
861 ABTRACEQ((" %02x", *u));
862 }
863 ABTRACEQ((" |"));
864 u = (const uint8_t *)counter_data;
865 for (i = 0; i < tree->layout[1]->field_octets; ++i, ++u) {
866 ABTRACEQ((" %02x", *u));
867 }
868 ABTRACEQ(("\n"));
869 }
870 #endif /* AGGBAG_TRACE */
871
872 /* Search down the tree for a place to insert */
873 for (;;) {
874 if (q == RBT_NIL) {
875 uint8_t *node_data;
876
877 /* Insert a new node at the first null link */
878 q = (rbtree_node_t*)malloc(tree->node_size);
879 if (NULL == q) {
880 return SK_RBTREE_ERR_ALLOC;
881 }
882 inserted = 1;
883 node_data = q->data_color;
884
885 rbtree_set_node_red(tree, q);
886 /* do not use macro here since we copy the key and counter
887 * data separately */
888 memcpy(node_data, key_data, tree->layout[0]->field_octets);
889 memcpy(node_data + tree->layout[0]->field_octets, counter_data,
890 tree->layout[1]->field_octets);
891 q->link[RBT_LEFT] = q->link[RBT_RIGHT] = RBT_NIL;
892
893 ABTRACE(("inserted new node %p as %s child of %p\n",
894 V(q), (dir ? "RIGHT" : "LEFT"), V(p)));
895
896 p->link[dir] = q;
897 ++tree->size;
898 } else if (rbtree_node_is_red(tree, q->link[RBT_LEFT])
899 && rbtree_node_is_red(tree, q->link[RBT_RIGHT]))
900 {
901 /* Simple red violation: color flip */
902 ABTRACE(("simple red violation on q = %p\n", V(q)));
903
904 rbtree_set_node_red(tree, q);
905 rbtree_set_node_black(tree, q->link[RBT_LEFT]);
906 rbtree_set_node_black(tree, q->link[RBT_RIGHT]);
907 }
908
909 if (rbtree_node_is_red(tree, p) && rbtree_node_is_red(tree, q)) {
910 /* Hard red violation: rotations necessary */
911 int dir2 = (t->link[RBT_RIGHT] == g);
912
913 ABTRACE((("hard red violation on p = %p, q = %p, g = %p, t = %p,"
914 " performing %s rotation\n"),
915 V(p), V(q), V(g), V(t),
916 ((q == p->link[last]) ? "single" : "double")));
917
918 if (q == p->link[last]) {
919 t->link[dir2] = rbtree_rotate_single(tree, g, !last);
920 } else {
921 t->link[dir2] = rbtree_rotate_double(tree, g, !last);
922 }
923 }
924
925 /* Stop working if we inserted a node */
926 if (inserted) {
927 ABTRACE(("stop after insertion\n"));
928 break;
929 }
930
931 /* Choose a direction and check for a match */
932 cmp = rbtree_compare_data(tree, q->data_color, key_data);
933 if (0 == cmp) {
934 uint8_t *node_data = q->data_color;
935 memcpy(node_data + tree->layout[0]->field_octets, counter_data,
936 tree->layout[1]->field_octets);
937 rv = SK_RBTREE_ERR_DUPLICATE;
938 ABTRACE(("stop after duplicate\n"));
939 break;
940 }
941
942 last = dir;
943 dir = (cmp < 0);
944
945 /* Move the helpers down */
946 t = g;
947 g = p;
948 p = q;
949 q = q->link[dir];
950 ABTRACE(("descent direction is %d, t = %p, g = %p, p = %p, q = %p\n",
951 dir, V(t), V(g), V(p), V(q)));
952
953 }
954
955 ABTRACE(("updating root from %p[%s] to %p[black]\n",
956 V(tree->root),
957 (rbtree_node_is_red(tree, tree->root) ? "red" : "black"),
958 V(head.link[RBT_RIGHT])));
959
960 /* Update the root (it may be different) */
961 tree->root = head.link[RBT_RIGHT];
962
963 /* Make the root black for simplified logic */
964 rbtree_set_node_black(tree, tree->root);
965
966 return rv;
967 }
968
969
970 /*
971 * Remove from 'tree' the node whose key is 'data'. Return
972 * SK_RBTREE_OK if removed or SK_RBTREE_ERR_NOT_FOUND if no node
973 * has the key 'data'.
974 */
975 static int
sk_rbtree_remove(sk_aggbag_t * tree,const void * data)976 sk_rbtree_remove(
977 sk_aggbag_t *tree,
978 const void *data)
979 {
980 rbtree_false_root_t head;
981 rbtree_node_t *q, *p, *g, *s; /* Helpers */
982 rbtree_node_t *f; /* Found item */
983 int dir;
984 int last;
985 int cmp;
986 int rv = SK_RBTREE_ERR_NOT_FOUND;
987
988 assert(tree);
989 assert(tree->data_len);
990
991 if (RBT_NIL == tree->root) {
992 return rv;
993 }
994 memset(&head, 0, sizeof(head));
995 head.link[0] = head.link[1] = RBT_NIL;
996
997 /* Set up our helpers */
998 p = NULL;
999 q = (rbtree_node_t *)&head;
1000 q->link[RBT_RIGHT] = tree->root;
1001 dir = RBT_RIGHT;
1002 f = NULL;
1003
1004 /* Search and push a red node down to fix red violations as we
1005 * go */
1006 do {
1007 /* Move the helpers down */
1008 g = p;
1009 p = q;
1010 q = q->link[dir];
1011
1012 cmp = rbtree_compare_data(tree, q->data_color, data);
1013 last = dir;
1014 dir = cmp < 0;
1015
1016 /* Save the node with matching data and keep going; we'll do
1017 * removal tasks at the end */
1018 if (0 == cmp) {
1019 f = q;
1020 }
1021
1022 /* Push the red node down with rotations and color flips */
1023 if (!rbtree_node_is_red(tree, q)
1024 && !rbtree_node_is_red(tree, q->link[dir]))
1025 {
1026 if (rbtree_node_is_red(tree, q->link[!dir])) {
1027 p = p->link[last] = rbtree_rotate_single(tree, q, dir);
1028 } else if ((s = p->link[!last]) != RBT_NIL) {
1029 if (!rbtree_node_is_red(tree, s->link[RBT_LEFT])
1030 && !rbtree_node_is_red(tree, s->link[RBT_RIGHT]))
1031 {
1032 /* Color flip */
1033 rbtree_set_node_black(tree, p);
1034 rbtree_set_node_red(tree, s);
1035 rbtree_set_node_red(tree, q);
1036 } else {
1037 int dir2 = (g->link[RBT_RIGHT] == p);
1038
1039 if (rbtree_node_is_red(tree, s->link[last])) {
1040 g->link[dir2] = rbtree_rotate_double(tree, p, last);
1041 } else if (rbtree_node_is_red(tree, s->link[!last])) {
1042 g->link[dir2] = rbtree_rotate_single(tree, p, last);
1043 }
1044
1045 /* Ensure correct coloring */
1046 rbtree_set_node_red(tree, q);
1047 rbtree_set_node_red(tree, g->link[dir2]);
1048 rbtree_set_node_black(tree,g->link[dir2]->link[RBT_LEFT]);
1049 rbtree_set_node_black(tree,g->link[dir2]->link[RBT_RIGHT]);
1050 }
1051 }
1052 }
1053 } while (q->link[dir] != RBT_NIL);
1054
1055 /* Replace and remove the saved node */
1056 if (f != NULL) {
1057 rbtree_set_node_data(tree, f, q->data_color);
1058 p->link[p->link[RBT_RIGHT] == q] =
1059 q->link[q->link[RBT_LEFT] == RBT_NIL];
1060 free(q);
1061 --tree->size;
1062 rv = SK_RBTREE_OK;
1063 }
1064
1065 /* Update the root (it may be different) */
1066 tree->root = head.link[RBT_RIGHT];
1067
1068 /* Make the root black for simplified logic */
1069 rbtree_set_node_black(tree, tree->root);
1070
1071 return rv;
1072 }
1073
1074
1075 #if 0
1076 static size_t
1077 sk_rbtree_size(
1078 const sk_aggbag_t *tree)
1079 {
1080 return tree->size;
1081 }
1082 #endif /* 0 */
1083
1084
1085 static sk_rbtree_iter_t *
sk_rbtree_iter_create(const sk_aggbag_t * tree)1086 sk_rbtree_iter_create(
1087 const sk_aggbag_t *tree)
1088 {
1089 sk_rbtree_iter_t *iter;
1090
1091 iter = (sk_rbtree_iter_t*)calloc(1, sizeof(sk_rbtree_iter_t));
1092 if (iter) {
1093 iter->prev_data = rbtree_iter_start(iter, tree, 0);
1094 }
1095 return iter;
1096 }
1097
1098
1099 static void
sk_rbtree_iter_free(sk_rbtree_iter_t * iter)1100 sk_rbtree_iter_free(
1101 sk_rbtree_iter_t *iter)
1102 {
1103 free(iter);
1104 }
1105
1106
1107 #if 0
1108 static void *
1109 sk_rbtree_iter_bind_first(
1110 sk_rbtree_iter_t *iter,
1111 const sk_aggbag_t *tree)
1112 {
1113 /* Min value */
1114 return rbtree_iter_start(iter, tree, 0);
1115 }
1116
1117
1118 static void *
1119 sk_rbtree_iter_bind_last(
1120 sk_rbtree_iter_t *iter,
1121 const sk_aggbag_t *tree)
1122 {
1123 /* Max value */
1124 return rbtree_iter_start(iter, tree, 1);
1125 }
1126 #endif /* 0 */
1127
1128
1129 static const void *
sk_rbtree_iter_next(sk_rbtree_iter_t * iter)1130 sk_rbtree_iter_next(
1131 sk_rbtree_iter_t *iter)
1132 {
1133 const void *data;
1134
1135 /* Toward larger items */
1136 data = iter->prev_data;
1137 iter->prev_data = rbtree_iter_move(iter, 1);
1138 return data;
1139 }
1140
1141
1142 #if 0
1143 static void *
1144 sk_rbtree_iter_prev(
1145 sk_rbtree_iter_t *iter)
1146 {
1147 /* Toward smaller items */
1148 return rbtree_iter_move(iter, 0);
1149 }
1150 #endif /* 0 */
1151
1152
1153 static void
sk_rbtree_debug_print(const sk_aggbag_t * tree,FILE * fp,sk_rbtree_print_data_fn_t print_data)1154 sk_rbtree_debug_print(
1155 const sk_aggbag_t *tree,
1156 FILE *fp,
1157 sk_rbtree_print_data_fn_t print_data)
1158 {
1159 if (NULL == tree) {
1160 fprintf(fp, "Tree: Pointer is NULL\n");
1161 return;
1162 }
1163 if (NULL == print_data) {
1164 print_data = rbtree_node_default_data_printer;
1165 }
1166
1167 fprintf(fp, "Tree: %p has %" SK_PRIuZ " nodes\n", (void*)tree, tree->size);
1168 rbtree_node_debug_print(tree, tree->root, fp, print_data, 0);
1169
1170 rbtree_assert(tree, tree->root, fp);
1171 }
1172
1173
1174
1175 /* **************************************************************** */
1176 /* **************************************************************** */
1177 /* For serializing an AggBag, this is the header that describes the
1178 * key and the counter and the functions to manipulate it. */
1179 /* **************************************************************** */
1180 /* **************************************************************** */
1181
1182 /**
1183 * When writing a Bag to a stream, this header entry is used to
1184 * contain information about the bag.
1185 */
1186 typedef struct sk_hentry_aggbag_st {
1187 sk_header_entry_spec_t he_spec;
1188 uint32_t header_version;
1189 /* Total number of fields: both keys and counters */
1190 uint16_t field_count;
1191 /* Number of fields that are keys */
1192 uint16_t key_count;
1193 uint16_t *fields;
1194 } sk_hentry_aggbag_t;
1195
1196 /*
1197 * Version to specify in the header entry. Version 1 uses a bitmap
1198 * with 64 entries.
1199 */
1200 #define AB_HENTRY_VERSION 1
1201
1202 /*
1203 * Create and return a new header entry for AggBag files that is a
1204 * copy of the header entry 'hentry'.
1205 *
1206 * This is the 'copy_fn' callback for skHentryTypeRegister().
1207 */
1208 static sk_header_entry_t *
aggBagHentryCopy(const sk_header_entry_t * hentry)1209 aggBagHentryCopy(
1210 const sk_header_entry_t *hentry)
1211 {
1212 const sk_hentry_aggbag_t *ab_hdr = (const sk_hentry_aggbag_t *)hentry;
1213 sk_hentry_aggbag_t *new_hdr;
1214
1215 assert(SK_HENTRY_AGGBAG_ID == skHeaderEntryGetTypeId(hentry));
1216 assert(AB_HENTRY_VERSION == ab_hdr->header_version);
1217
1218 new_hdr = (sk_hentry_aggbag_t *)malloc(sizeof(*new_hdr));
1219 if (NULL == new_hdr) {
1220 return NULL;
1221 }
1222 memcpy(new_hdr, ab_hdr, sizeof(*new_hdr));
1223 new_hdr->fields = (uint16_t *)calloc(new_hdr->field_count,sizeof(uint16_t));
1224 if (NULL == new_hdr->fields) {
1225 free(new_hdr);
1226 return NULL;
1227 }
1228 memcpy(new_hdr->fields, ab_hdr->fields,
1229 new_hdr->field_count * sizeof(uint16_t));
1230
1231 return (sk_header_entry_t *)new_hdr;
1232 }
1233
1234 /*
1235 * Create and return a new header entry for AggBag files. 'key_type'
1236 * is the type of the key, 'key_length' is the octet length of a
1237 * key, 'counter_type' is the type of the counter, 'counter_length'
1238 * is the octet length of a counter.
1239 */
1240 static sk_header_entry_t *
aggBagHentryCreate(const sk_aggbag_t * ab)1241 aggBagHentryCreate(
1242 const sk_aggbag_t *ab)
1243 {
1244 sk_hentry_aggbag_t *ab_hdr;
1245 uint16_t *u16;
1246 unsigned int i;
1247 unsigned int field_count;
1248 size_t len;
1249
1250 if (NULL == ab->layout[0] || NULL == ab->layout[1]) {
1251 return NULL;
1252 }
1253 if (ab->layout[0]->field_count + ab->layout[1]->field_count > UINT16_MAX) {
1254 return NULL;
1255 }
1256
1257 field_count= ab->layout[0]->field_count + ab->layout[1]->field_count;
1258
1259 /* compute the required length of the header */
1260 len = (sizeof(ab_hdr->he_spec) + sizeof(uint32_t)
1261 + (sizeof(uint16_t) * (2 + field_count)));
1262
1263 ABTRACE(("Computed length of header is %" SK_PRIuZ "\n", len));
1264 ab_hdr = (sk_hentry_aggbag_t*)calloc(1, sizeof(sk_hentry_aggbag_t));
1265 if (NULL == ab_hdr) {
1266 return NULL;
1267 }
1268 ab_hdr->he_spec.hes_id = SK_HENTRY_AGGBAG_ID;
1269 ab_hdr->he_spec.hes_len = len;
1270 ab_hdr->header_version = AB_HENTRY_VERSION;
1271 ab_hdr->key_count = ab->layout[0]->field_count;
1272 ab_hdr->field_count = field_count;
1273
1274 ab_hdr->fields = (uint16_t *)calloc(field_count, sizeof(uint16_t));
1275 if (NULL == ab_hdr->fields) {
1276 free(ab_hdr);
1277 return NULL;
1278 }
1279 u16 = ab_hdr->fields;
1280 for (i = 0; i < ab->layout[0]->field_count; ++i, ++u16) {
1281 *u16 = ab->layout[0]->fields[i].f_type;
1282 }
1283 for (i = 0; i < ab->layout[1]->field_count; ++i, ++u16) {
1284 *u16 = ab->layout[1]->fields[i].f_type;
1285 }
1286
1287 ABTRACE(("Created new aggbag header entry %p\n", V(ab_hdr)));
1288 return (sk_header_entry_t*)ab_hdr;
1289 }
1290
1291 /*
1292 * Release any memory that is used by the in-memory representation
1293 * of the file header for AggBag files.
1294 *
1295 * This is the 'free_fn' callback for skHentryTypeRegister().
1296 */
1297 static void
aggBagHentryFree(sk_header_entry_t * hentry)1298 aggBagHentryFree(
1299 sk_header_entry_t *hentry)
1300 {
1301 sk_hentry_aggbag_t *ab_hdr = (sk_hentry_aggbag_t *)hentry;
1302
1303 if (ab_hdr) {
1304 assert(skHeaderEntryGetTypeId(ab_hdr) == SK_HENTRY_AGGBAG_ID);
1305 ab_hdr->he_spec.hes_id = UINT32_MAX;
1306 free(ab_hdr->fields);
1307 free(ab_hdr);
1308 }
1309 }
1310
1311 #define aggBagHentryGetCounterCount(hentry) \
1312 ((unsigned int)(((sk_hentry_aggbag_t *)(hentry))->field_count \
1313 - ((sk_hentry_aggbag_t *)(hentry))->key_count))
1314
1315 #define aggBagHentryGetCounterFieldType(hentry, pos) \
1316 aggBagHentryGetFieldType((hentry), SK_AGGBAG_COUNTER, (pos))
1317
1318 #define aggBagHentryGetKeyCount(hentry) \
1319 (((sk_hentry_aggbag_t *)(hentry))->key_count)
1320
1321 static sk_aggbag_type_t
aggBagHentryGetFieldType(const sk_header_entry_t * hentry,unsigned int key_counter,unsigned int pos)1322 aggBagHentryGetFieldType(
1323 const sk_header_entry_t *hentry,
1324 unsigned int key_counter,
1325 unsigned int pos)
1326 {
1327 const sk_hentry_aggbag_t *ab_hdr = (const sk_hentry_aggbag_t *)hentry;
1328
1329 assert(SK_AGGBAG_KEY == key_counter || SK_AGGBAG_COUNTER == key_counter);
1330
1331 if (NULL == ab_hdr || NULL == ab_hdr->fields) {
1332 return SKAGGBAG_FIELD_INVALID;
1333 }
1334 if (SK_AGGBAG_KEY == key_counter) {
1335 if (pos >= ab_hdr->key_count) {
1336 return SKAGGBAG_FIELD_INVALID;
1337 }
1338 return (sk_aggbag_type_t)ab_hdr->fields[pos];
1339 } else {
1340 pos += ab_hdr->key_count;
1341 if (pos >= ab_hdr->field_count) {
1342 return SKAGGBAG_FIELD_INVALID;
1343 }
1344 return (sk_aggbag_type_t)ab_hdr->fields[pos];
1345 }
1346 }
1347
1348 #define aggBagHentryGetKeyFieldType(hentry, pos) \
1349 aggBagHentryGetFieldType((hentry), SK_AGGBAG_KEY, (pos))
1350
1351 #define aggBagHentryGetVersion(hentry) \
1352 (((sk_hentry_aggbag_t *)(hentry))->header_version)
1353
1354 /*
1355 * Pack the contents of the header entry for AggBag files,
1356 * 'in_hentry' into the buffer 'out_packed', whose size is
1357 * 'bufsize', for writing the file to disk.
1358 *
1359 * This the 'pack_fn' callback for skHentryTypeRegister().
1360 */
1361 static ssize_t
aggBagHentryPacker(const sk_header_entry_t * in_hentry,uint8_t * out_packed,size_t bufsize)1362 aggBagHentryPacker(
1363 const sk_header_entry_t *in_hentry,
1364 uint8_t *out_packed,
1365 size_t bufsize)
1366 {
1367 sk_hentry_aggbag_t *ab_hdr = (sk_hentry_aggbag_t *)in_hentry;
1368 unsigned int i;
1369 uint32_t u32;
1370 uint16_t u16;
1371 size_t len;
1372 uint8_t *b;
1373
1374 assert(in_hentry);
1375 assert(out_packed);
1376 assert(skHeaderEntryGetTypeId(ab_hdr) == SK_HENTRY_AGGBAG_ID);
1377
1378 /* compute the required size */
1379 len = (sizeof(ab_hdr->he_spec) + sizeof(uint32_t)
1380 + (sizeof(uint16_t) * (2 + ab_hdr->field_count)));
1381 if (len > ab_hdr->he_spec.hes_len) {
1382 ab_hdr->he_spec.hes_len = len;
1383 }
1384
1385 if (bufsize >= len) {
1386 b = out_packed;
1387 skHeaderEntrySpecPack(&(ab_hdr->he_spec), b, len);
1388 b += sizeof(ab_hdr->he_spec);
1389 u32 = htonl(ab_hdr->header_version);
1390 memcpy(b, &u32, sizeof(u32));
1391 b += sizeof(u32);
1392 u16 = htons(ab_hdr->field_count);
1393 memcpy(b, &u16, sizeof(u16));
1394 b += sizeof(u16);
1395 u16 = htons(ab_hdr->key_count);
1396 memcpy(b, &u16, sizeof(u16));
1397 b += sizeof(u16);
1398 for (i = 0; i < ab_hdr->field_count; ++i) {
1399 u16 = htons(ab_hdr->fields[i]);
1400 memcpy(b, &u16, sizeof(u16));
1401 b += sizeof(u16);
1402 }
1403 assert((ssize_t)bufsize >= (b - out_packed));
1404 }
1405
1406 return len;
1407 }
1408
1409 /*
1410 * Print a textual representation of a file's AggBag header entry in
1411 * 'hentry' to the FILE pointer 'fh'.
1412 *
1413 * This is the 'print_fn' callback for skHentryTypeRegister().
1414 */
1415 static void
aggBagHentryPrint(const sk_header_entry_t * hentry,FILE * fh)1416 aggBagHentryPrint(
1417 const sk_header_entry_t *hentry,
1418 FILE *fh)
1419 {
1420 const sk_hentry_aggbag_t *ab_hdr = (const sk_hentry_aggbag_t *)hentry;
1421 const ab_type_info_t *info;
1422 char sep;
1423 unsigned int i;
1424
1425 assert(ab_hdr);
1426 assert(skHeaderEntryGetTypeId(ab_hdr) == SK_HENTRY_AGGBAG_ID);
1427
1428 fprintf(fh, "key:");
1429 sep = ' ';
1430 for (i = 0; i < ab_hdr->key_count; ++i) {
1431 if (NULL == (info = aggBagGetTypeInfo(ab_hdr->fields[i]))) {
1432 fprintf(fh, "%cUNKNOWN[%u]", sep, ab_hdr->fields[i]);
1433 } else {
1434 assert(SK_AGGBAG_COUNTER != info->ti_key_counter);
1435 fprintf(fh, "%c%s", sep, info->ti_name);
1436 }
1437 sep = ',';
1438 }
1439
1440 fprintf(fh, "; counter:");
1441 sep = ' ';
1442 for ( ; i < ab_hdr->field_count; ++i) {
1443 if (NULL == (info = aggBagGetTypeInfo(ab_hdr->fields[i]))) {
1444 fprintf(fh, "%cUNKNOWN[%u]", sep, ab_hdr->fields[i]);
1445 } else {
1446 assert(SK_AGGBAG_KEY != info->ti_key_counter);
1447 fprintf(fh, "%c%s", sep, info->ti_name);
1448 }
1449 sep = ',';
1450 }
1451 }
1452
1453 /*
1454 * Unpack the data in 'in_packed' to create an in-memory
1455 * representation of a file's AggBag header entry.
1456 *
1457 * This is the 'unpack_fn' callback for skHentryTypeRegister().
1458 */
1459 static sk_header_entry_t *
aggBagHentryUnpacker(uint8_t * in_packed)1460 aggBagHentryUnpacker(
1461 uint8_t *in_packed)
1462 {
1463 sk_hentry_aggbag_t *ab_hdr;
1464 const uint8_t *b;
1465 unsigned int i;
1466 uint32_t u32;
1467 uint16_t u16;
1468 size_t len;
1469
1470 assert(in_packed);
1471
1472 /* create space for new header */
1473 ab_hdr = (sk_hentry_aggbag_t *)calloc(1, sizeof(sk_hentry_aggbag_t));
1474 if (NULL == ab_hdr) {
1475 ABTRACE(("Header allocation failed\n"));
1476 return NULL;
1477 }
1478
1479 /* copy the spec */
1480 b = in_packed;
1481 skHeaderEntrySpecUnpack(&(ab_hdr->he_spec), in_packed);
1482 assert(skHeaderEntryGetTypeId(ab_hdr) == SK_HENTRY_AGGBAG_ID);
1483 len = ab_hdr->he_spec.hes_len;
1484 ABTRACE(("Header length is %" SK_PRIuZ "\n", len));
1485 assert(len > sizeof(ab_hdr->he_spec));
1486 b += sizeof(ab_hdr->he_spec);
1487 len -= sizeof(ab_hdr->he_spec);
1488
1489 /* header_version */
1490 if (len < sizeof(uint32_t)) {
1491 ABTRACE(("Remaining header length (%" SK_PRIuZ ") is too small\n",
1492 len));
1493 free(ab_hdr);
1494 return NULL;
1495 }
1496 memcpy(&u32, b, sizeof(u32));
1497 ab_hdr->header_version = ntohl(u32);
1498 b += sizeof(u32);
1499 len -= sizeof(u32);
1500 if (AB_HENTRY_VERSION != ab_hdr->header_version) {
1501 ABTRACE(("Header version (%u) is unsupported\n",
1502 ab_hdr->header_version));
1503 free(ab_hdr);
1504 return NULL;
1505 }
1506
1507 /* field_count */
1508 if (len < sizeof(uint16_t)) {
1509 ABTRACE(("Remaining header length (%" SK_PRIuZ ") is too small\n",
1510 len));
1511 free(ab_hdr);
1512 return NULL;
1513 }
1514 memcpy(&u16, b, sizeof(u16));
1515 ab_hdr->field_count = ntohs(u16);
1516 b += sizeof(u16);
1517 len -= sizeof(u16);
1518 if (ab_hdr->field_count < 2) {
1519 ABTRACE(("Field count (%u) is too small\n", ab_hdr->field_count));
1520 free(ab_hdr);
1521 return NULL;
1522 }
1523
1524 /* key_count */
1525 if (len < sizeof(uint16_t)) {
1526 ABTRACE(("Remaining header length (%" SK_PRIuZ ") is too small\n",
1527 len));
1528 free(ab_hdr);
1529 return NULL;
1530 }
1531 memcpy(&u16, b, sizeof(u16));
1532 ab_hdr->key_count = ntohs(u16);
1533 b += sizeof(u16);
1534 len -= sizeof(u16);
1535 if (ab_hdr->key_count >= ab_hdr->field_count) {
1536 ABTRACE(("Key count (%u) should not be larger than field count (%u)\n",
1537 ab_hdr->key_count, ab_hdr->field_count));
1538 free(ab_hdr);
1539 return NULL;
1540 }
1541
1542 /* remainder of length is for the fields */
1543 if (len != ab_hdr->field_count * sizeof(uint16_t)) {
1544 ABTRACE((("Remaining header length (%" SK_PRIuZ ") does not"
1545 " match expected length (%u %" SK_PRIuZ "-byte fieldIDs)\n"),
1546 len, ab_hdr->field_count, sizeof(uint16_t)));
1547 free(ab_hdr);
1548 return NULL;
1549 }
1550
1551 /* allocate an array for the fields */
1552 ab_hdr->fields = (uint16_t *)calloc(ab_hdr->field_count, sizeof(uint16_t));
1553 if (NULL == ab_hdr->fields) {
1554 ABTRACE(("Unable to allocate array of %u %" SK_PRIuZ "-byte fieldIDs\n",
1555 ab_hdr->field_count, sizeof(uint16_t)));
1556 free(ab_hdr);
1557 return NULL;
1558 }
1559
1560 /* fill that array */
1561 for (i = 0; i < ab_hdr->field_count; ++i) {
1562 memcpy(&u16, b, sizeof(u16));
1563 ab_hdr->fields[i] = ntohs(u16);
1564 b += sizeof(u16);
1565 }
1566
1567 return (sk_header_entry_t*)ab_hdr;
1568 }
1569
1570
1571 /**
1572 * A function called during application setup that registers the
1573 * callback functions needed to operate on the AggBag header entry.
1574 *
1575 * The prototype for this function is in skheader_priv.h
1576 */
1577 int
skAggBagRegisterHeaderEntry(sk_hentry_type_id_t entry_id)1578 skAggBagRegisterHeaderEntry(
1579 sk_hentry_type_id_t entry_id)
1580 {
1581 assert(SK_HENTRY_AGGBAG_ID == entry_id);
1582 return (skHentryTypeRegister(
1583 entry_id, &aggBagHentryPacker, &aggBagHentryUnpacker,
1584 &aggBagHentryCopy, &aggBagHentryFree, &aggBagHentryPrint));
1585 }
1586
1587
1588
1589 /* **************************************************************** */
1590 /* **************************************************************** */
1591 /* Functions to handle the ab_layout_t which describes the fields
1592 * that comprise an aggregate key or counter */
1593 /* **************************************************************** */
1594 /* **************************************************************** */
1595
1596 /**
1597 * Comparison function required by the redblack tree code to
1598 * compare two ab_layout_t structures.
1599 */
1600 static int
abLayoutCompare(const void * v_lo_a,const void * v_lo_b,const void * config)1601 abLayoutCompare(
1602 const void *v_lo_a,
1603 const void *v_lo_b,
1604 const void *config)
1605 {
1606 const ab_layout_t *lo_a = (ab_layout_t *)v_lo_a;
1607 const ab_layout_t *lo_b = (ab_layout_t *)v_lo_b;
1608
1609 SK_UNUSED_PARAM(config);
1610
1611 return ((lo_a->field_count == lo_b->field_count)
1612 ? memcmp(lo_a->bitmap, lo_b->bitmap, sizeof(lo_a->bitmap))
1613 : (lo_a->field_count > lo_b->field_count ? 1 : -1));
1614 }
1615
1616
1617 /**
1618 * Check for a layout that matches the fields specified in
1619 * 'fields'. If found (regardless of field ordering), increment
1620 * its reference count and return it. Otherwise create a new one
1621 * and return it.
1622 */
1623 static const ab_layout_t *
abLayoutCreate(unsigned int field_count,const sk_aggbag_type_t fields[])1624 abLayoutCreate(
1625 unsigned int field_count,
1626 const sk_aggbag_type_t fields[])
1627 {
1628 const ab_type_info_t *info;
1629 ab_layout_t *lo_found;
1630 ab_layout_t *lo_new = NULL;
1631 ab_layout_t search;
1632 ab_field_t *f;
1633 unsigned int i;
1634
1635 search.field_count = 0;
1636 BITMAP_INIT(search.bitmap);
1637 for (i = 0; i < field_count; ++i) {
1638 if (0 == BITMAP_GETBIT(search.bitmap, fields[i])) {
1639 BITMAP_SETBIT(search.bitmap, fields[i]);
1640 ++search.field_count;
1641 }
1642 }
1643 ABTRACE(("search bmap: %08x ... %08x\n",
1644 search.bitmap[0], search.bitmap[0xc000 >> 5]));
1645 #if AGGBAG_TRACE && 0
1646 ABTRACE(("search bmap:"));
1647 for (i = 0; (i << 5) < AB_LAYOUT_BMAP_SIZE; ++i) {
1648 ABTRACEQ((" %08x", search.bitmap[i]));
1649 }
1650 ABTRACEQ(("\n"));
1651 #endif /* AGGBAG_TRACE */
1652
1653 if (NULL == layouts) {
1654 layouts = rbinit(&abLayoutCompare, NULL);
1655 if (NULL == layouts) {
1656 goto ERROR;
1657 }
1658 } else {
1659 lo_found = (ab_layout_t *)rbfind(&search, layouts);
1660 if (lo_found) {
1661 ABTRACE(("match found %p\n", V(lo_found)));
1662 ++lo_found->ref_count;
1663 return lo_found;
1664 }
1665 }
1666
1667 lo_new = (ab_layout_t *)calloc(1, sizeof(*lo_new));
1668 if (NULL == lo_new) {
1669 return NULL;
1670 }
1671
1672 BITMAP_INIT(lo_new->bitmap);
1673 lo_new->fields = ((ab_field_t *)
1674 malloc(search.field_count * sizeof(ab_field_t)));
1675 if (NULL == lo_new->fields) {
1676 goto ERROR;
1677 }
1678 f = lo_new->fields;
1679
1680 /* set the field types */
1681 for (i = 0; i < field_count; ++i) {
1682 if (0 == BITMAP_GETBIT(lo_new->bitmap, fields[i])) {
1683 BITMAP_SETBIT(lo_new->bitmap, fields[i]);
1684 f->f_type = fields[i];
1685 ++lo_new->field_count;
1686 ++f;
1687 }
1688 }
1689 assert(search.field_count == lo_new->field_count);
1690 assert(0 == memcmp(search.bitmap, lo_new->bitmap, sizeof(search.bitmap)));
1691
1692 /* sort the fields by ID */
1693 skQSort(lo_new->fields, lo_new->field_count, sizeof(ab_field_t),
1694 &abLayoutFieldSorter);
1695
1696 /* set lengths and offsets for each field */
1697 for (i = 0, f = lo_new->fields; i < lo_new->field_count; ++i, ++f) {
1698 info = aggBagGetTypeInfo(f->f_type);
1699 assert(info);
1700 f->f_len = info->ti_octets;
1701 f->f_offset = lo_new->field_octets;
1702 lo_new->field_octets += f->f_len;
1703 }
1704
1705 ABTRACE(("new bmap: %08x ... %08x\n",
1706 lo_new->bitmap[0], lo_new->bitmap[0xc000 >> 5]));
1707 lo_found = (ab_layout_t *)rbsearch(lo_new, layouts);
1708 if (lo_found != lo_new) {
1709 skAbort();
1710 }
1711
1712 ABTRACE(("new layout %p fields %p count %u\n",
1713 V(lo_new), V(lo_new->fields), lo_new->field_count));
1714 for (i = 0; i < lo_new->field_count; ++i) {
1715 ABTRACEQ((" field %u type %d, len %2u, offset %2u,",
1716 i, lo_new->fields[i].f_type, lo_new->fields[i].f_len,
1717 lo_new->fields[i].f_offset));
1718 info = aggBagGetTypeInfo(lo_new->fields[i].f_type);
1719 assert(info);
1720 ABTRACEQ((" name '%s'\n", info->ti_name));
1721 }
1722
1723 lo_new->ref_count = 1;
1724 ++layouts_count;
1725
1726 return lo_found;
1727
1728 ERROR:
1729 if (layouts && !layouts_count) {
1730 rbdestroy(layouts);
1731 layouts = NULL;
1732 }
1733 if (lo_new) {
1734 if (lo_new->fields) {
1735 free(lo_new->fields);
1736 }
1737 free(lo_new);
1738 }
1739 return NULL;
1740 }
1741
1742
1743 /**
1744 * Decrement the reference count of the layout in 'layout' and
1745 * destroy it if its reference count is 0.
1746 *
1747 * Also, destroy the redblack tree of existing layouts if all
1748 * layouts have been destroyed.
1749 */
1750 static void
abLayoutDestroy(const ab_layout_t * layout)1751 abLayoutDestroy(
1752 const ab_layout_t *layout)
1753 {
1754 if (layout) {
1755 ab_layout_t *LO = (ab_layout_t *)layout;
1756 const void *found;
1757
1758 if (LO->ref_count > 1) {
1759 --LO->ref_count;
1760 return;
1761 }
1762
1763 /* remove from redblack tree */
1764 if (layouts) {
1765 found = rbdelete(LO, layouts);
1766 if (found) {
1767 --layouts_count;
1768 }
1769 if (0 == layouts_count) {
1770 rbdestroy(layouts);
1771 layouts = NULL;
1772 }
1773 }
1774
1775 free(LO->fields);
1776 free(LO);
1777 }
1778 }
1779
1780
1781 /**
1782 * A callback function used by skQSort() to sort the fields that
1783 * comprise the key and counter.
1784 */
1785 static int
abLayoutFieldSorter(const void * v_a,const void * v_b)1786 abLayoutFieldSorter(
1787 const void *v_a,
1788 const void *v_b)
1789 {
1790 const ab_field_t *a = (const ab_field_t *)v_a;
1791 const ab_field_t *b = (const ab_field_t *)v_b;
1792
1793 ABTRACE(("sorter a = %u, b = %u ==> %d\n",
1794 a->f_type, b->f_type, (int)a->f_type - (int)b->f_type));
1795
1796 return ((int)a->f_type - (int)b->f_type);
1797 }
1798
1799
1800 /* **************************************************************** */
1801 /* **************************************************************** */
1802 /* Internal functions that operate on the AggBag structure. */
1803 /* **************************************************************** */
1804 /* **************************************************************** */
1805
1806
1807 /**
1808 * Initialize the aggregate 'agg' and the field iterator
1809 * 'field_iter' to work on the key or counter fields of 'ab'
1810 * depending other whether 'key_counter_flag' is SK_AGGBAG_KEY or
1811 * SK_AGGBAG_COUNTER.
1812 */
1813 static void
aggBagInitializeAggregate(const sk_aggbag_t * ab,unsigned int key_counter_flag,sk_aggbag_aggregate_t * agg,sk_aggbag_field_t * field_iter)1814 aggBagInitializeAggregate(
1815 const sk_aggbag_t *ab,
1816 unsigned int key_counter_flag,
1817 sk_aggbag_aggregate_t *agg,
1818 sk_aggbag_field_t *field_iter)
1819 {
1820 unsigned int idx;
1821
1822 assert(SK_AGGBAG_KEY == key_counter_flag
1823 || SK_AGGBAG_COUNTER == key_counter_flag);
1824 idx = (SK_AGGBAG_COUNTER == key_counter_flag);
1825
1826 if (ab && ab->layout[idx]) {
1827 if (agg) {
1828 agg->opaque = ab->layout[idx];
1829 memset(agg->data, 0, ab->layout[idx]->field_octets);
1830 }
1831 if (field_iter) {
1832 field_iter->opaque = ab->layout[idx];
1833 field_iter->pos = 0;
1834 }
1835 }
1836 }
1837
1838
1839 /**
1840 * Return the type info structure for the type whose ID is
1841 * 'field_type', or return NULL if no such type exists.
1842 */
1843 static const ab_type_info_t *
aggBagGetTypeInfo(uint16_t field_type)1844 aggBagGetTypeInfo(
1845 uint16_t field_type)
1846 {
1847 size_t cur;
1848
1849 if ((size_t)field_type < ab_type_info_key_max) {
1850 if (ab_type_info_key[field_type].ti_octets > 0) {
1851 assert(field_type == ab_type_info_key[field_type].ti_type);
1852 return &ab_type_info_key[field_type];
1853 }
1854 } else if (field_type >= SKAGGBAG_FIELD_RECORDS
1855 && ((cur = field_type - SKAGGBAG_FIELD_RECORDS)
1856 < ab_type_info_counter_max))
1857 {
1858 if (ab_type_info_counter[cur].ti_octets > 0) {
1859 assert(field_type == ab_type_info_counter[cur].ti_type);
1860 return &ab_type_info_counter[cur];
1861 }
1862 #if AB_SUPPORT_CUSTOM
1863 } else if (SKAGGBAG_FIELD_CUSTOM == field_type) {
1864 return &ab_custom_info;
1865 #endif /* AB_SUPPORT_CUSTOM */
1866 }
1867 return NULL;
1868 }
1869
1870
1871 /*
1872 * status = aggbagOptionsHandler(cData, opt_index, opt_arg);
1873 *
1874 * Parse an option that was registered by skAggBagOptionsRegister().
1875 * Return 0 on success, or non-zero on failure.
1876 */
1877 static int
aggbagOptionsHandler(clientData cData,int opt_index,char * opt_arg)1878 aggbagOptionsHandler(
1879 clientData cData,
1880 int opt_index,
1881 char *opt_arg)
1882 {
1883 sk_aggbag_options_t *ab_opts = (sk_aggbag_options_t*)cData;
1884
1885 SK_UNUSED_PARAM(opt_arg);
1886
1887 switch (opt_index) {
1888 #if 0
1889 case OPT_AGGBAG_RECORD_VERSION:
1890 uint32_t tmp32;
1891 int rv;
1892 rv = skStringParseUint32(&tmp32, opt_arg, AGGBAG_REC_VERSION_MIN,
1893 AGGBAG_REC_VERSION_MAX);
1894 if (rv) {
1895 skAppPrintErr("Invalid %s '%s': %s",
1896 aggbag_options_record_version[0].name, opt_arg,
1897 skStringParseStrerror(rv));
1898 return -1;
1899 }
1900 if (1 == tmp32) {
1901 skAppPrintErr("Invalid %s '%s': Illegal version number",
1902 aggbag_options_record_version[0].name,
1903 opt_arg);
1904 return -1;
1905 }
1906 ab_opts->record_version = (uint16_t)tmp32;
1907 break;
1908 #endif /* 0 */
1909 case OPT_AGGBAG_INVOCATION_STRIP:
1910 ab_opts->invocation_strip = 1;
1911 break;
1912
1913 default:
1914 skAbortBadCase(opt_index);
1915 }
1916
1917 return 0;
1918 }
1919
1920
1921 /**
1922 * Print the contents of 'data' to 'fp'. For debugging.
1923 */
1924 static void
aggBagPrintData(const sk_aggbag_t * tree,FILE * fp,const void * data)1925 aggBagPrintData(
1926 const sk_aggbag_t *tree,
1927 FILE *fp,
1928 const void *data)
1929 {
1930 const uint8_t *u_data = (const uint8_t *)data;
1931 unsigned int i;
1932
1933 for (i = 0; i < tree->data_len; ++i, ++u_data) {
1934 if (i == tree->layout[0]->field_octets) {
1935 fprintf(fp, " |");
1936 }
1937 fprintf(fp, " %02x", *u_data);
1938 }
1939 }
1940
1941
1942 /**
1943 * Create a new layout from the 'field_count' fields in the array
1944 * 'fields' and store the layout in the either the key or counter
1945 * of 'ab' depending other whether 'key_counter_flag' is
1946 * SK_AGGBAG_KEY or SK_AGGBAG_COUNTER.
1947 */
1948 static int
aggBagSetLayout(sk_aggbag_t * ab,unsigned int key_counter_flag,unsigned int field_count,const sk_aggbag_type_t fields[])1949 aggBagSetLayout(
1950 sk_aggbag_t *ab,
1951 unsigned int key_counter_flag,
1952 unsigned int field_count,
1953 const sk_aggbag_type_t fields[])
1954 {
1955 const ab_type_info_t *info;
1956 const ab_layout_t *new_lo;
1957 unsigned int i;
1958 unsigned int idx;
1959
1960 assert(ab);
1961 assert(SK_AGGBAG_KEY == key_counter_flag
1962 || SK_AGGBAG_COUNTER == key_counter_flag);
1963
1964 if (ab->fixed_fields) {
1965 return SKAGGBAG_E_FIXED_FIELDS;
1966 }
1967 idx = (SK_AGGBAG_COUNTER == key_counter_flag);
1968
1969 /* confirm types make sense */
1970 for (i = 0; i < field_count; ++i) {
1971 info = aggBagGetTypeInfo(fields[i]);
1972 if (NULL == info || 0 == (info->ti_key_counter & key_counter_flag)) {
1973 return SKAGGBAG_E_FIELD_CLASS;
1974 }
1975 #if !SK_ENABLE_IPV6
1976 if (16 == info->ti_octets) {
1977 return SKAGGBAG_E_UNSUPPORTED_IPV6;
1978 }
1979 #endif
1980 }
1981
1982 #if AGGBAG_TRACE
1983 ABTRACE(("%s layout (%u fields): %u",
1984 (SK_AGGBAG_KEY == key_counter_flag) ? "key" : "counter",
1985 field_count, fields[0]));
1986 for (i = 1; i < field_count; ++i) {
1987 ABTRACEQ((", %u", fields[i]));
1988 }
1989 ABTRACEQ(("\n"));
1990 #endif /* AGGBAG_TRACE */
1991
1992 new_lo = abLayoutCreate(field_count, fields);
1993 if (NULL == new_lo) {
1994 return SKAGGBAG_E_ALLOC;
1995 }
1996
1997 abLayoutDestroy(ab->layout[idx]);
1998 ab->layout[idx] = new_lo;
1999
2000 /* update values used by the red-black tree */
2001 ab->data_len
2002 = (((ab->layout[0]) ? ab->layout[0]->field_octets : 0)
2003 + ((ab->layout[1]) ? ab->layout[1]->field_octets : 0));
2004 ab->node_size = (offsetof(rbtree_node_t, data_color) + ab->data_len + 1u);
2005
2006 return SKAGGBAG_OK;
2007
2008
2009 }
2010
2011
2012
2013 /* **************************************************************** */
2014 /* **************************************************************** */
2015 /* Public functions that operate on the AggBag structure. */
2016 /* **************************************************************** */
2017 /* **************************************************************** */
2018
2019 int
skAggBagAddAggBag(sk_aggbag_t * ab_augend,const sk_aggbag_t * ab_addend)2020 skAggBagAddAggBag(
2021 sk_aggbag_t *ab_augend,
2022 const sk_aggbag_t *ab_addend)
2023 {
2024 sk_aggbag_iter_t iter = SK_AGGBAG_ITER_INITIALIZER;
2025 unsigned int i;
2026
2027 for (i = 0; i < 2; ++i) {
2028 if (ab_augend->layout[i] != ab_addend->layout[i]) {
2029 return ((0 == i)
2030 ? SKAGGBAG_E_FIELDS_DIFFER_KEY
2031 : SKAGGBAG_E_FIELDS_DIFFER_COUNTER);
2032 }
2033 }
2034
2035 skAggBagIteratorBind(&iter, ab_addend);
2036
2037 while (skAggBagIteratorNext(&iter) == SK_ITERATOR_OK) {
2038 skAggBagKeyCounterAdd(ab_augend, &iter.key, &iter.counter, NULL);
2039 }
2040 skAggBagIteratorFree(&iter);
2041
2042 return SKAGGBAG_OK;
2043 }
2044
2045
2046 int
skAggBagSubtractAggBag(sk_aggbag_t * ab_minuend,const sk_aggbag_t * ab_subtrahend)2047 skAggBagSubtractAggBag(
2048 sk_aggbag_t *ab_minuend,
2049 const sk_aggbag_t *ab_subtrahend)
2050 {
2051 sk_aggbag_iter_t iter = SK_AGGBAG_ITER_INITIALIZER;
2052 unsigned int i;
2053
2054 for (i = 0; i < 2; ++i) {
2055 if (ab_minuend->layout[i] != ab_subtrahend->layout[i]) {
2056 return ((0 == i)
2057 ? SKAGGBAG_E_FIELDS_DIFFER_KEY
2058 : SKAGGBAG_E_FIELDS_DIFFER_COUNTER);
2059 }
2060 }
2061
2062 skAggBagIteratorBind(&iter, ab_subtrahend);
2063
2064 while (skAggBagIteratorNext(&iter) == SK_ITERATOR_OK) {
2065 skAggBagKeyCounterSubtract(ab_minuend, &iter.key, &iter.counter, NULL);
2066 }
2067 skAggBagIteratorFree(&iter);
2068
2069 return SKAGGBAG_OK;
2070 }
2071
2072
2073 int
skAggBagAggregateGetDatetime(const sk_aggbag_aggregate_t * agg,const sk_aggbag_field_t * field_iter,sktime_t * time_value)2074 skAggBagAggregateGetDatetime(
2075 const sk_aggbag_aggregate_t *agg,
2076 const sk_aggbag_field_t *field_iter,
2077 sktime_t *time_value)
2078 {
2079 const ab_layout_t *layout;
2080 const ab_field_t *field;
2081 uint64_t tmp;
2082
2083 assert(agg);
2084 assert(field_iter);
2085 assert(agg->opaque == field_iter->opaque);
2086 assert(agg->opaque);
2087
2088 layout = (const ab_layout_t *)agg->opaque;
2089 if (field_iter->pos >= layout->field_count) {
2090 return SKAGGBAG_E_BAD_INDEX;
2091 }
2092 field = &layout->fields[field_iter->pos];
2093
2094 switch (field->f_type) {
2095 case SKAGGBAG_FIELD_STARTTIME:
2096 case SKAGGBAG_FIELD_ENDTIME:
2097 case SKAGGBAG_FIELD_ANY_TIME:
2098 assert(sizeof(sktime_t) == field->f_len);
2099 memcpy(&tmp, agg->data + field->f_offset, field->f_len);
2100 *time_value = (sktime_t)ntoh64(tmp);
2101 break;
2102 default:
2103 return SKAGGBAG_E_GET_SET_MISMATCH;
2104 }
2105
2106 return SKAGGBAG_OK;
2107 }
2108
2109 int
skAggBagAggregateGetIPAddress(const sk_aggbag_aggregate_t * agg,const sk_aggbag_field_t * field_iter,skipaddr_t * ip_value)2110 skAggBagAggregateGetIPAddress(
2111 const sk_aggbag_aggregate_t *agg,
2112 const sk_aggbag_field_t *field_iter,
2113 skipaddr_t *ip_value)
2114 {
2115 const ab_layout_t *layout;
2116 const ab_field_t *field;
2117
2118 assert(agg);
2119 assert(field_iter);
2120 assert(agg->opaque == field_iter->opaque);
2121 assert(agg->opaque);
2122
2123 layout = (const ab_layout_t *)agg->opaque;
2124 if (field_iter->pos >= layout->field_count) {
2125 return SKAGGBAG_E_BAD_INDEX;
2126 }
2127 field = &layout->fields[field_iter->pos];
2128
2129 switch (field->f_type) {
2130 case SKAGGBAG_FIELD_SIPv4:
2131 case SKAGGBAG_FIELD_DIPv4:
2132 case SKAGGBAG_FIELD_NHIPv4:
2133 case SKAGGBAG_FIELD_ANY_IPv4:
2134 {
2135 uint32_t tmp;
2136 assert(sizeof(tmp) == field->f_len);
2137 memcpy(&tmp, agg->data + field->f_offset, sizeof(tmp));
2138 tmp = ntohl(tmp);
2139 skipaddrSetV4(ip_value, &tmp);
2140 }
2141 break;
2142 case SKAGGBAG_FIELD_SIPv6:
2143 case SKAGGBAG_FIELD_DIPv6:
2144 case SKAGGBAG_FIELD_NHIPv6:
2145 case SKAGGBAG_FIELD_ANY_IPv6:
2146 #if !SK_ENABLE_IPV6
2147 return SKAGGBAG_E_UNSUPPORTED_IPV6;
2148 #else
2149 assert(16 == field->f_len);
2150 skipaddrSetV6(ip_value, agg->data + field->f_offset);
2151 break;
2152 #endif /* SK_ENABLE_IPV6 */
2153 default:
2154 return SKAGGBAG_E_GET_SET_MISMATCH;
2155 }
2156
2157 return SKAGGBAG_OK;
2158 }
2159
2160 int
skAggBagAggregateGetUnsigned(const sk_aggbag_aggregate_t * agg,const sk_aggbag_field_t * field_iter,uint64_t * unsigned_value)2161 skAggBagAggregateGetUnsigned(
2162 const sk_aggbag_aggregate_t *agg,
2163 const sk_aggbag_field_t *field_iter,
2164 uint64_t *unsigned_value)
2165 {
2166 const ab_layout_t *layout;
2167 const ab_field_t *field;
2168
2169 assert(agg);
2170 assert(field_iter);
2171 assert(agg->opaque == field_iter->opaque);
2172 assert(agg->opaque);
2173
2174 layout = (const ab_layout_t *)agg->opaque;
2175 if (field_iter->pos >= layout->field_count) {
2176 return SKAGGBAG_E_BAD_INDEX;
2177 }
2178 field = &layout->fields[field_iter->pos];
2179
2180 switch (field->f_type) {
2181 case SKAGGBAG_FIELD_SIPv4:
2182 case SKAGGBAG_FIELD_DIPv4:
2183 case SKAGGBAG_FIELD_NHIPv4:
2184 case SKAGGBAG_FIELD_ANY_IPv4:
2185 case SKAGGBAG_FIELD_SIPv6:
2186 case SKAGGBAG_FIELD_DIPv6:
2187 case SKAGGBAG_FIELD_NHIPv6:
2188 case SKAGGBAG_FIELD_ANY_IPv6:
2189 /* case SKAGGBAG_FIELD_STARTTIME: */
2190 /* case SKAGGBAG_FIELD_ENDTIME: */
2191 /* case SKAGGBAG_FIELD_ANY_TIME: */
2192 return SKAGGBAG_E_GET_SET_MISMATCH;
2193 default:
2194 break;
2195 }
2196
2197 switch (field->f_len) {
2198 case 1:
2199 *unsigned_value = agg->data[field->f_offset];
2200 break;
2201 case 2:
2202 {
2203 uint16_t tmp;
2204 assert(sizeof(tmp) == field->f_len);
2205 memcpy(&tmp, agg->data + field->f_offset, sizeof(tmp));
2206 *unsigned_value = ntohs(tmp);
2207 }
2208 break;
2209 case 4:
2210 {
2211 uint32_t tmp;
2212 assert(sizeof(tmp) == field->f_len);
2213 memcpy(&tmp, agg->data + field->f_offset, sizeof(tmp));
2214 *unsigned_value = ntohl(tmp);
2215 }
2216 break;
2217 case 8:
2218 assert(sizeof(*unsigned_value) == field->f_len);
2219 memcpy(unsigned_value, agg->data + field->f_offset,
2220 sizeof(*unsigned_value));
2221 *unsigned_value = ntoh64(*unsigned_value);
2222 break;
2223 case 16:
2224 return SKAGGBAG_E_GET_SET_MISMATCH;
2225 default:
2226 skAbortBadCase(field->f_len);
2227 }
2228
2229 return SKAGGBAG_OK;
2230 }
2231
2232 int
skAggBagAggregateSetDatetime(sk_aggbag_aggregate_t * agg,const sk_aggbag_field_t * field_iter,sktime_t time_value)2233 skAggBagAggregateSetDatetime(
2234 sk_aggbag_aggregate_t *agg,
2235 const sk_aggbag_field_t *field_iter,
2236 sktime_t time_value)
2237 {
2238 const ab_layout_t *layout;
2239 const ab_field_t *field;
2240 uint64_t tmp;
2241
2242 assert(agg);
2243 assert(field_iter);
2244 assert(agg->opaque == field_iter->opaque);
2245 assert(agg->opaque);
2246 assert(sizeof(tmp) == sizeof(time_value));
2247
2248 layout = (const ab_layout_t *)agg->opaque;
2249 if (field_iter->pos >= layout->field_count) {
2250 return SKAGGBAG_E_BAD_INDEX;
2251 }
2252 field = &layout->fields[field_iter->pos];
2253
2254 switch (field->f_type) {
2255 case SKAGGBAG_FIELD_STARTTIME:
2256 case SKAGGBAG_FIELD_ENDTIME:
2257 case SKAGGBAG_FIELD_ANY_TIME:
2258 assert(sizeof(sktime_t) == field->f_len);
2259 tmp = hton64((uint64_t)time_value);
2260 memcpy(agg->data + field->f_offset, &tmp, field->f_len);
2261 break;
2262 default:
2263 return SKAGGBAG_E_GET_SET_MISMATCH;
2264 }
2265
2266 return SKAGGBAG_OK;
2267 }
2268
2269 int
skAggBagAggregateSetIPAddress(sk_aggbag_aggregate_t * agg,const sk_aggbag_field_t * field_iter,const skipaddr_t * ip_value)2270 skAggBagAggregateSetIPAddress(
2271 sk_aggbag_aggregate_t *agg,
2272 const sk_aggbag_field_t *field_iter,
2273 const skipaddr_t *ip_value)
2274 {
2275 const ab_layout_t *layout;
2276 const ab_field_t *field;
2277
2278 assert(agg);
2279 assert(field_iter);
2280 assert(agg->opaque == field_iter->opaque);
2281 assert(agg->opaque);
2282
2283 layout = (const ab_layout_t *)agg->opaque;
2284 if (field_iter->pos >= layout->field_count) {
2285 return SKAGGBAG_E_BAD_INDEX;
2286 }
2287 field = &layout->fields[field_iter->pos];
2288
2289 switch (field->f_type) {
2290 case SKAGGBAG_FIELD_SIPv4:
2291 case SKAGGBAG_FIELD_DIPv4:
2292 case SKAGGBAG_FIELD_NHIPv4:
2293 case SKAGGBAG_FIELD_ANY_IPv4:
2294 {
2295 uint32_t tmp;
2296 assert(sizeof(tmp) == field->f_len);
2297 if (skipaddrGetAsV4(ip_value, &tmp)) {
2298 return SKAGGBAG_E_GET_SET_MISMATCH;
2299 }
2300 tmp = htonl(tmp);
2301 memcpy(agg->data + field->f_offset, &tmp, field->f_len);
2302 }
2303 break;
2304 case SKAGGBAG_FIELD_SIPv6:
2305 case SKAGGBAG_FIELD_DIPv6:
2306 case SKAGGBAG_FIELD_NHIPv6:
2307 case SKAGGBAG_FIELD_ANY_IPv6:
2308 #if !SK_ENABLE_IPV6
2309 return SKAGGBAG_E_UNSUPPORTED_IPV6;
2310 #else
2311 assert(16 == field->f_len);
2312 skipaddrGetAsV6(ip_value, agg->data + field->f_offset);
2313 break;
2314 #endif /* SK_ENABLE_IPV6 */
2315 default:
2316 return SKAGGBAG_E_GET_SET_MISMATCH;
2317 }
2318
2319 return SKAGGBAG_OK;
2320 }
2321
2322 int
skAggBagAggregateSetUnsigned(sk_aggbag_aggregate_t * agg,const sk_aggbag_field_t * field_iter,uint64_t unsigned_value)2323 skAggBagAggregateSetUnsigned(
2324 sk_aggbag_aggregate_t *agg,
2325 const sk_aggbag_field_t *field_iter,
2326 uint64_t unsigned_value)
2327 {
2328 const ab_layout_t *layout;
2329 const ab_field_t *field;
2330
2331 assert(agg);
2332 assert(field_iter);
2333 assert(agg->opaque == field_iter->opaque);
2334 assert(agg->opaque);
2335
2336 layout = (const ab_layout_t *)agg->opaque;
2337 if (field_iter->pos >= layout->field_count) {
2338 return SKAGGBAG_E_BAD_INDEX;
2339 }
2340 field = &layout->fields[field_iter->pos];
2341
2342 ABTRACE(("set unsigned id = %u, value = %" PRIu64 "\n",
2343 field->f_type, unsigned_value));
2344
2345 switch (field->f_type) {
2346 case SKAGGBAG_FIELD_SIPv4:
2347 case SKAGGBAG_FIELD_DIPv4:
2348 case SKAGGBAG_FIELD_NHIPv4:
2349 case SKAGGBAG_FIELD_ANY_IPv4:
2350 case SKAGGBAG_FIELD_SIPv6:
2351 case SKAGGBAG_FIELD_DIPv6:
2352 case SKAGGBAG_FIELD_NHIPv6:
2353 case SKAGGBAG_FIELD_ANY_IPv6:
2354 /* case SKAGGBAG_FIELD_STARTTIME: */
2355 /* case SKAGGBAG_FIELD_ENDTIME: */
2356 /* case SKAGGBAG_FIELD_ANY_TIME: */
2357 return SKAGGBAG_E_GET_SET_MISMATCH;
2358 default:
2359 break;
2360 }
2361
2362 switch (field->f_len) {
2363 case 1:
2364 agg->data[field->f_offset] = unsigned_value;
2365 break;
2366 case 2:
2367 {
2368 uint16_t tmp = unsigned_value;
2369 assert(sizeof(tmp) == field->f_len);
2370 tmp = htons(tmp);
2371 memcpy(agg->data + field->f_offset, &tmp, sizeof(tmp));
2372 }
2373 break;
2374 case 4:
2375 {
2376 uint32_t tmp = unsigned_value;
2377 assert(sizeof(tmp) == field->f_len);
2378 tmp = htonl(tmp);
2379 memcpy(agg->data + field->f_offset, &tmp, sizeof(tmp));
2380 }
2381 break;
2382 case 8:
2383 assert(sizeof(unsigned_value) == field->f_len);
2384 unsigned_value = hton64(unsigned_value);
2385 memcpy(agg->data + field->f_offset, &unsigned_value,
2386 sizeof(unsigned_value));
2387 break;
2388 case 16:
2389 return SKAGGBAG_E_GET_SET_MISMATCH;
2390 default:
2391 skAbortBadCase(field->f_len);
2392 }
2393
2394 return SKAGGBAG_OK;
2395 }
2396
2397
2398 int
skAggBagCreate(sk_aggbag_t ** ab_param)2399 skAggBagCreate(
2400 sk_aggbag_t **ab_param)
2401 {
2402 sk_aggbag_t *ab;
2403
2404 if (NULL == ab_param) {
2405 return SKAGGBAG_E_NULL_PARM;
2406 }
2407
2408 ab = (sk_aggbag_t *)calloc(1, sizeof(sk_aggbag_t));
2409 if (NULL == ab) {
2410 *ab_param = NULL;
2411 return SKAGGBAG_E_ALLOC;
2412 }
2413
2414 /* Initialize values used by the red-black tree */
2415 ab->root = RBT_NIL;
2416 ab->size = 0;
2417 ab->data_len = 0;
2418 ab->node_size = (offsetof(rbtree_node_t, data_color) + ab->data_len + 1u);
2419
2420 *ab_param = ab;
2421 return SKAGGBAG_OK;
2422 }
2423
2424 void
skAggBagDestroy(sk_aggbag_t ** ab_param)2425 skAggBagDestroy(
2426 sk_aggbag_t **ab_param)
2427 {
2428 sk_aggbag_t *ab;
2429
2430 if (ab_param && *ab_param) {
2431 ab = *ab_param;
2432 *ab_param = NULL;
2433
2434 sk_rbtree_destroy(ab);
2435 abLayoutDestroy(ab->layout[0]);
2436 abLayoutDestroy(ab->layout[1]);
2437 free(ab);
2438 }
2439 }
2440
2441
2442 sk_aggbag_type_t
skAggBagFieldIterGetType(const sk_aggbag_field_t * field_iter)2443 skAggBagFieldIterGetType(
2444 const sk_aggbag_field_t *field_iter)
2445 {
2446 const ab_layout_t *layout;
2447
2448 assert(field_iter);
2449 assert(field_iter->opaque);
2450
2451 layout = (const ab_layout_t *)field_iter->opaque;
2452 if (field_iter->pos >= layout->field_count) {
2453 return SKAGGBAG_FIELD_INVALID;
2454 }
2455 return layout->fields[field_iter->pos].f_type;
2456 }
2457
2458 int
skAggBagFieldIterNext(sk_aggbag_field_t * field_iter)2459 skAggBagFieldIterNext(
2460 sk_aggbag_field_t *field_iter)
2461 {
2462 const ab_layout_t *layout;
2463
2464 assert(field_iter);
2465 if (field_iter && field_iter->opaque) {
2466 ++field_iter->pos;
2467 layout = (const ab_layout_t *)field_iter->opaque;
2468 if (layout->field_count > field_iter->pos) {
2469 return SK_ITERATOR_OK;
2470 }
2471 field_iter->pos = layout->field_count;
2472 }
2473 return SK_ITERATOR_NO_MORE_ENTRIES;
2474 }
2475
2476 void
skAggBagFieldIterReset(sk_aggbag_field_t * field_iter)2477 skAggBagFieldIterReset(
2478 sk_aggbag_field_t *field_iter)
2479 {
2480 assert(field_iter);
2481 if (field_iter) {
2482 field_iter->pos = 0;
2483 }
2484 }
2485
2486
2487 const char *
skAggBagFieldTypeGetName(sk_aggbag_type_t field_type)2488 skAggBagFieldTypeGetName(
2489 sk_aggbag_type_t field_type)
2490 {
2491 const ab_type_info_t *info;
2492
2493 info = aggBagGetTypeInfo(field_type);
2494 if (info) {
2495 return info->ti_name;
2496 }
2497 return NULL;
2498 }
2499
2500
2501 void
skAggBagFieldTypeIteratorBind(sk_aggbag_type_iter_t * type_iter,unsigned int key_counter_flag)2502 skAggBagFieldTypeIteratorBind(
2503 sk_aggbag_type_iter_t *type_iter,
2504 unsigned int key_counter_flag)
2505 {
2506 assert(type_iter);
2507 if (type_iter) {
2508 type_iter->key_counter_flag = key_counter_flag;
2509 skAggBagFieldTypeIteratorReset(type_iter);
2510 }
2511 }
2512
2513
2514 const char *
skAggBagFieldTypeIteratorNext(sk_aggbag_type_iter_t * type_iter,sk_aggbag_type_t * field_type)2515 skAggBagFieldTypeIteratorNext(
2516 sk_aggbag_type_iter_t *type_iter,
2517 sk_aggbag_type_t *field_type)
2518 {
2519 const ab_type_info_t *info = NULL;
2520 size_t cur;
2521
2522 /* when entering this function, type_iter is expected to be on the
2523 * type to return */
2524
2525 assert(type_iter);
2526 if (NULL == type_iter) {
2527 goto END;
2528 }
2529
2530 if (type_iter->pos >= SKAGGBAG_FIELD_INVALID) {
2531 #if AB_SUPPORT_CUSTOM
2532 if (SKAGGBAG_FIELD_CUSTOM == type_iter->pos) {
2533 info = &ab_custom_info;
2534 type_iter->pos = SKAGGBAG_FIELD_INVALID;
2535 }
2536 #endif /* AB_SUPPORT_CUSTOM */
2537 goto END;
2538 }
2539
2540 if (SK_AGGBAG_KEY == type_iter->key_counter_flag) {
2541 cur = type_iter->pos;
2542 if (cur >= ab_type_info_key_max) {
2543 /* value out of range */
2544 goto END;
2545 }
2546 info = &ab_type_info_key[cur];
2547 /* update type_iter for next iteration */
2548 for (++cur; cur < ab_type_info_key_max; ++cur) {
2549 if (ab_type_info_key[cur].ti_octets > 0) {
2550 type_iter->pos = (sk_aggbag_type_t)cur;
2551 goto END;
2552 }
2553 }
2554
2555 } else if (SK_AGGBAG_COUNTER == type_iter->key_counter_flag) {
2556 if (type_iter->pos < SKAGGBAG_FIELD_RECORDS
2557 || ((cur = type_iter->pos - SKAGGBAG_FIELD_RECORDS)
2558 >= ab_type_info_counter_max))
2559 {
2560 /* value out of range */
2561 goto END;
2562 }
2563 info = &ab_type_info_counter[cur];
2564 for (++cur; cur < ab_type_info_counter_max; ++cur) {
2565 if (ab_type_info_counter[cur].ti_octets > 0) {
2566 type_iter->pos
2567 = (sk_aggbag_type_t)(SKAGGBAG_FIELD_RECORDS + cur);
2568 goto END;
2569 }
2570 }
2571
2572 } else {
2573 assert((SK_AGGBAG_KEY == type_iter->key_counter_flag)
2574 || (SK_AGGBAG_COUNTER == type_iter->key_counter_flag));
2575 }
2576
2577 #if AB_SUPPORT_CUSTOM
2578 type_iter->pos = SKAGGBAG_FIELD_CUSTOM;
2579 #else
2580 type_iter->pos = SKAGGBAG_FIELD_INVALID;
2581 #endif /* AB_SUPPORT_CUSTOM */
2582
2583 END:
2584 if (field_type) {
2585 if (info) {
2586 *field_type = info->ti_type;
2587 } else {
2588 *field_type = SKAGGBAG_FIELD_INVALID;
2589 }
2590 }
2591 if (info) {
2592 return info->ti_name;
2593 }
2594 return NULL;
2595 }
2596
2597
2598 void
skAggBagFieldTypeIteratorReset(sk_aggbag_type_iter_t * type_iter)2599 skAggBagFieldTypeIteratorReset(
2600 sk_aggbag_type_iter_t *type_iter)
2601 {
2602 assert(type_iter);
2603 if (type_iter) {
2604 switch (type_iter->key_counter_flag) {
2605 case SK_AGGBAG_KEY:
2606 type_iter->pos = SKAGGBAG_FIELD_SIPv4;
2607 break;
2608 case SK_AGGBAG_COUNTER:
2609 type_iter->pos = SKAGGBAG_FIELD_RECORDS;
2610 break;
2611 default:
2612 type_iter->pos = SKAGGBAG_FIELD_INVALID;
2613 type_iter->key_counter_flag = SK_AGGBAG_KEY;
2614 break;
2615 }
2616 }
2617 }
2618
2619
2620 void
skAggBagInitializeCounter(const sk_aggbag_t * ab,sk_aggbag_aggregate_t * counter,sk_aggbag_field_t * counter_iter)2621 skAggBagInitializeCounter(
2622 const sk_aggbag_t *ab,
2623 sk_aggbag_aggregate_t *counter,
2624 sk_aggbag_field_t *counter_iter)
2625 {
2626 aggBagInitializeAggregate(ab, SK_AGGBAG_COUNTER, counter, counter_iter);
2627 }
2628
2629 void
skAggBagInitializeKey(const sk_aggbag_t * ab,sk_aggbag_aggregate_t * key,sk_aggbag_field_t * key_iter)2630 skAggBagInitializeKey(
2631 const sk_aggbag_t *ab,
2632 sk_aggbag_aggregate_t *key,
2633 sk_aggbag_field_t *key_iter)
2634 {
2635 aggBagInitializeAggregate(ab, SK_AGGBAG_KEY, key, key_iter);
2636 }
2637
2638
2639 void
skAggBagIteratorBind(sk_aggbag_iter_t * iter,const sk_aggbag_t * ab)2640 skAggBagIteratorBind(
2641 sk_aggbag_iter_t *iter,
2642 const sk_aggbag_t *ab)
2643 {
2644 sk_rbtree_iter_t *it;
2645
2646 if (ab && iter) {
2647 memset(iter, 0, sizeof(*iter));
2648 it = sk_rbtree_iter_create(ab);
2649 if (NULL == it) {
2650 return;
2651 }
2652 skAggBagInitializeKey(ab, &iter->key, &iter->key_field_iter);
2653 skAggBagInitializeCounter(
2654 ab, &iter->counter, &iter->counter_field_iter);
2655 iter->opaque = it;
2656 }
2657 }
2658
2659 void
skAggBagIteratorFree(sk_aggbag_iter_t * iter)2660 skAggBagIteratorFree(
2661 sk_aggbag_iter_t *iter)
2662 {
2663 if (iter) {
2664 if (iter->opaque) {
2665 sk_rbtree_iter_free((sk_rbtree_iter_t *)iter->opaque);
2666 }
2667 memset(iter, 0, sizeof(*iter));
2668 }
2669 }
2670
2671 int
skAggBagIteratorNext(sk_aggbag_iter_t * iter)2672 skAggBagIteratorNext(
2673 sk_aggbag_iter_t *iter)
2674 {
2675 sk_rbtree_iter_t *it;
2676 const void *data;
2677 size_t key_len;
2678
2679 if (NULL == iter || NULL == iter->opaque) {
2680 return SK_ITERATOR_NO_MORE_ENTRIES;
2681 }
2682 it = (sk_rbtree_iter_t *)iter->opaque;
2683 data = sk_rbtree_iter_next(it);
2684 if (NULL == data) {
2685 return SK_ITERATOR_NO_MORE_ENTRIES;
2686 }
2687 key_len = ((ab_layout_t *)iter->key.opaque)->field_octets;
2688 memcpy(iter->key.data, data, key_len);
2689 memcpy(iter->counter.data, (const uint8_t *)data + key_len,
2690 ((ab_layout_t *)iter->counter.opaque)->field_octets);
2691 iter->key_field_iter.pos = 0;
2692 iter->counter_field_iter.pos = 0;
2693
2694 return SK_ITERATOR_OK;
2695 }
2696
2697 void
skAggBagIteratorReset(sk_aggbag_iter_t * iter)2698 skAggBagIteratorReset(
2699 sk_aggbag_iter_t *iter)
2700 {
2701 sk_rbtree_iter_t *it;
2702
2703 if (iter) {
2704 it = (sk_rbtree_iter_t *)iter->opaque;
2705 it->prev_data = rbtree_iter_start(it, it->tree, 0);
2706 }
2707 }
2708
2709
2710 int
skAggBagKeyCounterAdd(sk_aggbag_t * ab,const sk_aggbag_aggregate_t * key,const sk_aggbag_aggregate_t * counter,sk_aggbag_aggregate_t * new_counter)2711 skAggBagKeyCounterAdd(
2712 sk_aggbag_t *ab,
2713 const sk_aggbag_aggregate_t *key,
2714 const sk_aggbag_aggregate_t *counter,
2715 sk_aggbag_aggregate_t *new_counter)
2716 {
2717 const ab_layout_t *layout;
2718 const ab_field_t *f;
2719 rbtree_node_t *node;
2720 unsigned int i;
2721 uint64_t dst;
2722 uint64_t src;
2723
2724 if (NULL == ab || NULL == key || NULL == counter) {
2725 return SKAGGBAG_E_NULL_PARM;
2726 }
2727 if (NULL == ab->layout[0] || NULL == ab->layout[1]) {
2728 return ((NULL == ab->layout[0])
2729 ? SKAGGBAG_E_UNDEFINED_KEY : SKAGGBAG_E_UNDEFINED_COUNTER);
2730 }
2731
2732 if (ab->layout[0] != key->opaque) {
2733 return SKAGGBAG_E_FIELDS_DIFFER_KEY;
2734 }
2735 if (ab->layout[1] != counter->opaque) {
2736 return SKAGGBAG_E_FIELDS_DIFFER_COUNTER;
2737 }
2738 if (new_counter) {
2739 new_counter->opaque = counter->opaque;
2740 }
2741 ab->fixed_fields = 1;
2742
2743 node = sk_rbtree_find(ab, key->data);
2744 if (NULL == node) {
2745 sk_rbtree_insert(ab, key->data, counter->data);
2746 if (new_counter) {
2747 memcpy(new_counter->data, counter->data,
2748 ab->layout[1]->field_octets);
2749 }
2750 } else {
2751 layout = ab->layout[1];
2752 for (i = 0, f = layout->fields; i < layout->field_count; ++i, ++f) {
2753 assert(sizeof(uint64_t) == f->f_len);
2754 memcpy(&dst,
2755 node->data_color+ ab->layout[0]->field_octets+ f->f_offset,
2756 f->f_len);
2757 memcpy(&src, counter->data + f->f_offset, f->f_len);
2758 dst = ntoh64(dst);
2759 src = ntoh64(src);
2760 if (dst >= UINT64_MAX - src) {
2761 dst = UINT64_MAX;
2762 } else {
2763 dst += src;
2764 }
2765 dst = hton64(dst);
2766 memcpy(node->data_color+ ab->layout[0]->field_octets+ f->f_offset,
2767 &dst, f->f_len);
2768 if (new_counter) {
2769 memcpy(new_counter->data + f->f_offset, &dst, f->f_len);
2770 }
2771 }
2772 }
2773 if (/* DISABLES CODE*/ (0)) {
2774 sk_rbtree_debug_print(ab, stderr, aggBagPrintData);
2775 }
2776
2777 return SKAGGBAG_OK;
2778 }
2779
2780 int
skAggBagKeyCounterGet(const sk_aggbag_t * ab,const sk_aggbag_aggregate_t * key,sk_aggbag_aggregate_t * counter)2781 skAggBagKeyCounterGet(
2782 const sk_aggbag_t *ab,
2783 const sk_aggbag_aggregate_t *key,
2784 sk_aggbag_aggregate_t *counter)
2785 {
2786 rbtree_node_t *node;
2787
2788 if (NULL == ab || NULL == key || NULL == counter) {
2789 return SKAGGBAG_E_NULL_PARM;
2790 }
2791 if (NULL == ab->layout[0] || NULL == ab->layout[1]) {
2792 return ((NULL == ab->layout[0])
2793 ? SKAGGBAG_E_UNDEFINED_KEY : SKAGGBAG_E_UNDEFINED_COUNTER);
2794 }
2795
2796 if (ab->layout[0] != key->opaque) {
2797 return SKAGGBAG_E_FIELDS_DIFFER_KEY;
2798 }
2799
2800 counter->opaque = ab->layout[1];
2801
2802 node = sk_rbtree_find(ab, key->data);
2803 if (NULL == node) {
2804 memset(counter->data, 0, ab->layout[1]->field_octets);
2805 } else {
2806 memcpy(counter->data, node->data_color + ab->layout[0]->field_octets,
2807 ab->layout[1]->field_octets);
2808 }
2809
2810 return SKAGGBAG_OK;
2811 }
2812
2813 int
skAggBagKeyCounterRemove(sk_aggbag_t * ab,const sk_aggbag_aggregate_t * key)2814 skAggBagKeyCounterRemove(
2815 sk_aggbag_t *ab,
2816 const sk_aggbag_aggregate_t *key)
2817 {
2818 if (NULL == ab || NULL == key) {
2819 return SKAGGBAG_E_NULL_PARM;
2820 }
2821 if (NULL == ab->layout[0] || NULL == ab->layout[1]) {
2822 return ((NULL == ab->layout[0])
2823 ? SKAGGBAG_E_UNDEFINED_KEY : SKAGGBAG_E_UNDEFINED_COUNTER);
2824 }
2825
2826 if (ab->layout[0] != key->opaque) {
2827 return SKAGGBAG_E_FIELDS_DIFFER_KEY;
2828 }
2829
2830 ab->fixed_fields = 1;
2831
2832 sk_rbtree_remove(ab, key->data);
2833 return SKAGGBAG_OK;
2834 }
2835
2836 int
skAggBagKeyCounterSet(sk_aggbag_t * ab,const sk_aggbag_aggregate_t * key,const sk_aggbag_aggregate_t * counter)2837 skAggBagKeyCounterSet(
2838 sk_aggbag_t *ab,
2839 const sk_aggbag_aggregate_t *key,
2840 const sk_aggbag_aggregate_t *counter)
2841 {
2842 if (NULL == ab || NULL == key || NULL == counter) {
2843 return SKAGGBAG_E_NULL_PARM;
2844 }
2845 if (NULL == ab->layout[0] || NULL == ab->layout[1]) {
2846 return ((NULL == ab->layout[0])
2847 ? SKAGGBAG_E_UNDEFINED_KEY : SKAGGBAG_E_UNDEFINED_COUNTER);
2848 }
2849
2850 if (ab->layout[0] != key->opaque) {
2851 return SKAGGBAG_E_FIELDS_DIFFER_KEY;
2852 }
2853 if (ab->layout[1] != counter->opaque) {
2854 return SKAGGBAG_E_FIELDS_DIFFER_COUNTER;
2855 }
2856
2857 ab->fixed_fields = 1;
2858
2859 switch (sk_rbtree_insert(ab, key->data, counter->data)) {
2860 case SK_RBTREE_OK:
2861 case SK_RBTREE_ERR_DUPLICATE:
2862 return SKAGGBAG_OK;
2863 case SK_RBTREE_ERR_ALLOC:
2864 return SKAGGBAG_E_ALLOC;
2865 default:
2866 return SKAGGBAG_E_INSERT;
2867 }
2868 }
2869
2870 int
skAggBagKeyCounterSubtract(sk_aggbag_t * ab,const sk_aggbag_aggregate_t * key,const sk_aggbag_aggregate_t * counter,sk_aggbag_aggregate_t * new_counter)2871 skAggBagKeyCounterSubtract(
2872 sk_aggbag_t *ab,
2873 const sk_aggbag_aggregate_t *key,
2874 const sk_aggbag_aggregate_t *counter,
2875 sk_aggbag_aggregate_t *new_counter)
2876 {
2877 const ab_layout_t *layout;
2878 const ab_field_t *f;
2879 rbtree_node_t *node;
2880 unsigned int i;
2881 uint64_t dst;
2882 uint64_t src;
2883
2884 if (NULL == ab || NULL == key || NULL == counter) {
2885 return SKAGGBAG_E_NULL_PARM;
2886 }
2887 if (NULL == ab->layout[0] || NULL == ab->layout[1]) {
2888 return ((NULL == ab->layout[0])
2889 ? SKAGGBAG_E_UNDEFINED_KEY : SKAGGBAG_E_UNDEFINED_COUNTER);
2890 }
2891
2892 if (ab->layout[0] != key->opaque) {
2893 return SKAGGBAG_E_FIELDS_DIFFER_KEY;
2894 }
2895 if (ab->layout[1] != counter->opaque) {
2896 return SKAGGBAG_E_FIELDS_DIFFER_COUNTER;
2897 }
2898 if (new_counter) {
2899 new_counter->opaque = counter->opaque;
2900 }
2901
2902 ab->fixed_fields = 1;
2903
2904 node = sk_rbtree_find(ab, key->data);
2905 if (node) {
2906 layout = ab->layout[1];
2907 for (i = 0, f = layout->fields; i < layout->field_count; ++i, ++f) {
2908 assert(sizeof(uint64_t) == f->f_len);
2909 memcpy(&dst,
2910 node->data_color+ ab->layout[0]->field_octets+ f->f_offset,
2911 f->f_len);
2912 memcpy(&src, counter->data + f->f_offset, f->f_len);
2913 dst = ntoh64(dst);
2914 src = ntoh64(src);
2915 if (dst <= src) {
2916 dst = 0;
2917 } else {
2918 dst -= src;
2919 }
2920 dst = hton64(dst);
2921 memcpy(node->data_color+ ab->layout[0]->field_octets+ f->f_offset,
2922 &dst, f->f_len);
2923 if (new_counter) {
2924 memcpy(new_counter->data + f->f_offset, &dst, f->f_len);
2925 }
2926 }
2927 }
2928
2929 return SKAGGBAG_OK;
2930 }
2931
2932
2933 /* Read 'ab' from filename---a wrapper around skAggBagRead(). */
2934 int
skAggBagLoad(sk_aggbag_t ** ab,const char * filename)2935 skAggBagLoad(
2936 sk_aggbag_t **ab,
2937 const char *filename)
2938 {
2939 skstream_t *stream = NULL;
2940 int err = SKAGGBAG_OK;
2941 ssize_t rv;
2942
2943 if (NULL == filename || NULL == ab) {
2944 ABTRACE(("Got a null parameter ab=%p, filename=%p\n",
2945 V(ab), V(filename)));
2946 return SKAGGBAG_E_NULL_PARM;
2947 }
2948
2949 ABTRACE(("Creating stream for file '%s'\n", filename));
2950 if ((rv = skStreamCreate(&stream, SK_IO_READ, SK_CONTENT_SILK))
2951 || (rv = skStreamBind(stream, filename))
2952 || (rv = skStreamOpen(stream)))
2953 {
2954 ABTRACE(("Failed to create stream\n"));
2955 err = SKAGGBAG_E_READ;
2956 goto END;
2957 }
2958
2959 ABTRACE(("Reading from stream...\n"));
2960 err = skAggBagRead(ab, stream);
2961
2962 END:
2963 ABTRACE(("Destroying stream and returning %d\n", err));
2964 skStreamDestroy(&stream);
2965 return err;
2966 }
2967
2968
2969
2970
2971 /* Set the parameters to use when writing an Aggbag */
2972 void
skAggBagOptionsBind(sk_aggbag_t * ab,const sk_aggbag_options_t * ab_opts)2973 skAggBagOptionsBind(
2974 sk_aggbag_t *ab,
2975 const sk_aggbag_options_t *ab_opts)
2976 {
2977 assert(ab);
2978 ab->options = ab_opts;
2979 }
2980
2981 /* Initialize 'ab_opts' and register options */
2982 int
skAggBagOptionsRegister(sk_aggbag_options_t * ab_opts)2983 skAggBagOptionsRegister(
2984 sk_aggbag_options_t *ab_opts)
2985 {
2986 assert(ab_opts);
2987 assert(sizeof(aggbag_options)/sizeof(aggbag_options[0])
2988 == sizeof(aggbag_options_help)/sizeof(aggbag_options_help[0]));
2989
2990 if (skOptionsRegister(aggbag_options, aggbagOptionsHandler,
2991 (clientData)ab_opts)
2992 || skOptionsNotesRegister(ab_opts->existing_silk_files
2993 ? &ab_opts->note_strip
2994 : NULL)
2995 || skCompMethodOptionsRegister(&ab_opts->comp_method))
2996 {
2997 return -1;
2998 }
2999 return 0;
3000 }
3001
3002 /* Clean up memory used by the Aggbag options */
3003 void
skAggBagOptionsTeardown(void)3004 skAggBagOptionsTeardown(
3005 void)
3006 {
3007 skOptionsNotesTeardown();
3008 }
3009
3010 /* Print the usage strings for the options that the library registers */
3011 void
skAggBagOptionsUsage(FILE * fh)3012 skAggBagOptionsUsage(
3013 FILE *fh)
3014 {
3015 unsigned int i;
3016
3017 for (i = 0; aggbag_options[i].name; ++i) {
3018 fprintf(fh, "--%s %s. %s\n",
3019 aggbag_options[i].name, SK_OPTION_HAS_ARG(aggbag_options[i]),
3020 aggbag_options_help[i]);
3021 }
3022 skOptionsNotesUsage(fh);
3023 skCompMethodOptionsUsage(fh);
3024 }
3025
3026
3027 int
skAggBagRead(sk_aggbag_t ** ab_param,skstream_t * stream)3028 skAggBagRead(
3029 sk_aggbag_t **ab_param,
3030 skstream_t *stream)
3031 {
3032 sk_aggbag_t *ab = NULL;
3033 sk_file_header_t *hdr;
3034 sk_header_entry_t *hentry;
3035 int swap_flag;
3036 size_t entry_read_len;
3037 unsigned int i;
3038 sk_aggbag_type_t field_array[UINT8_MAX];
3039 int err = SKAGGBAG_OK;
3040 ssize_t b;
3041 uint8_t entrybuf[128];
3042 ssize_t rv;
3043
3044 if (NULL == ab_param || NULL == stream) {
3045 ABTRACE(("Got a null parameter ab_param=%p, stream=%p\n",
3046 V(ab_param), V(stream)));
3047 return SKAGGBAG_E_NULL_PARM;
3048 }
3049
3050 /* read header */
3051 ABTRACE(("Reading stream header\n"));
3052 rv = skStreamReadSilkHeader(stream, &hdr);
3053 if (rv) {
3054 ABTRACE(("Failure while reading stream header\n"));
3055 return SKAGGBAG_E_READ;
3056 }
3057
3058 ABTRACE(("Checking stream header\n"));
3059 rv = skStreamCheckSilkHeader(stream, FT_AGGREGATEBAG, 1,1, &skAppPrintErr);
3060 if (rv) {
3061 ABTRACE(("Failure while checking stream header\n"));
3062 return SKAGGBAG_E_HEADER;
3063 }
3064
3065 swap_flag = !skHeaderIsNativeByteOrder(hdr);
3066
3067 ABTRACE(("Checking for aggbag header entry\n"));
3068 hentry = skHeaderGetFirstMatch(hdr, SK_HENTRY_AGGBAG_ID);
3069 if (NULL == hentry) {
3070 ABTRACE(("Failure while checking for aggbag header entry \n"));
3071 return SKAGGBAG_E_HEADER;
3072 }
3073 if (AB_HENTRY_VERSION != aggBagHentryGetVersion(hentry)) {
3074 ABTRACE(("Aggbag header entry version (%u) is not supported\n",
3075 aggBagHentryGetVersion(hentry)));
3076 return SKAGGBAG_E_HEADER;
3077 }
3078
3079 /* allocate the new aggbag */
3080 ABTRACE(("Creating a new aggbag\n"));
3081 err = skAggBagCreate(&ab);
3082 if (err) {
3083 ABTRACE(("Failure (%d) while creating new aggbag\n", err));
3084 return err;
3085 }
3086
3087 for (i = 0; i < aggBagHentryGetKeyCount(hentry); ++i) {
3088 field_array[i] = aggBagHentryGetKeyFieldType(hentry, i);
3089 }
3090 err = aggBagSetLayout(ab, SK_AGGBAG_KEY, i, field_array);
3091 if (err) {
3092 ABTRACE(("Failure (%d) while setting key layout\n", err));
3093 goto END;
3094 }
3095
3096 for (i = 0; i < aggBagHentryGetCounterCount(hentry); ++i) {
3097 field_array[i] = aggBagHentryGetCounterFieldType(hentry, i);
3098 }
3099 err = aggBagSetLayout(ab, SK_AGGBAG_COUNTER, i, field_array);
3100 if (err) {
3101 ABTRACE(("Failure (%d) while setting counter layout\n", err));
3102 goto END;
3103 }
3104
3105 /* compute size of a complete entry, and double check that sizes
3106 * are reasonable */
3107 entry_read_len = ab->layout[0]->field_octets + ab->layout[1]->field_octets;
3108 if (entry_read_len != skHeaderGetRecordLength(hdr)) {
3109 ABTRACE((("Record length reported in header"
3110 " (%" SK_PRIuZ ") does not match computed entry length"
3111 " (%" SK_PRIuZ "==key=%u + counter=%u)\n"),
3112 skHeaderGetRecordLength(hdr), entry_read_len,
3113 ab->layout[0]->field_octets, ab->layout[1]->field_octets));
3114 goto END;
3115 }
3116
3117 ab->fixed_fields = 1;
3118
3119 /* set up is complete; read key/counter pairs */
3120 if (!swap_flag) {
3121 ABTRACE(("Starting to read data from stream\n"));
3122 while ((b = skStreamRead(stream, &entrybuf, entry_read_len))
3123 == (ssize_t)entry_read_len)
3124 {
3125 if (sk_rbtree_insert(ab, entrybuf,
3126 entrybuf + ab->layout[0]->field_octets)
3127 != SK_RBTREE_OK)
3128 {
3129 err = SKAGGBAG_E_ALLOC;
3130 goto END;
3131 }
3132 }
3133 ABTRACE(("Finished reading data from stream\n"));
3134 } else {
3135 /* FIXME: Values in tree always in big endian. no need for
3136 * this branch of the read function */
3137 union val_un {
3138 uint64_t u64;
3139 uint32_t u32;
3140 uint16_t u16;
3141 uint8_t u8;
3142 } val;
3143 const ab_field_t *f;
3144 unsigned int field_count;
3145 unsigned int q;
3146 uint8_t *buf;
3147
3148 ABTRACE(("Starting to read data from stream\n"));
3149 while ((b = skStreamRead(stream, &entrybuf, entry_read_len))
3150 == (ssize_t)entry_read_len)
3151 {
3152 for (q = 0; q < 2; ++q) {
3153 f = ab->layout[q]->fields;
3154 field_count = ab->layout[q]->field_count;
3155 if (0 == q) {
3156 buf = entrybuf;
3157 } else {
3158 buf = entrybuf + ab->layout[0]->field_octets;
3159 }
3160 for (i = 0; i < field_count; ++i, ++f) {
3161 switch (f->f_len) {
3162 case 1:
3163 case 16:
3164 break;
3165 case 2:
3166 memcpy(&val.u16, buf + f->f_offset, f->f_len);
3167 val.u16 = BSWAP16(val.u16);
3168 memcpy(buf + f->f_offset, &val.u16, f->f_len);
3169 break;
3170 case 4:
3171 memcpy(&val.u32, buf + f->f_offset, f->f_len);
3172 val.u32 = BSWAP32(val.u32);
3173 memcpy(buf + f->f_offset, &val.u32, f->f_len);
3174 break;
3175 case 8:
3176 memcpy(&val.u64, buf + f->f_offset, f->f_len);
3177 val.u64 = BSWAP64(val.u64);
3178 memcpy(buf + f->f_offset, &val.u64, f->f_len);
3179 break;
3180 default:
3181 skAbortBadCase(f->f_len);
3182 }
3183 }
3184 }
3185 if (sk_rbtree_insert(ab, entrybuf,
3186 entrybuf + ab->layout[0]->field_octets)
3187 != SK_RBTREE_OK)
3188 {
3189 err = SKAGGBAG_E_ALLOC;
3190 goto END;
3191 }
3192 }
3193 ABTRACE(("Finished reading data from stream\n"));
3194 }
3195
3196 ABTRACE(("Checking the integrity of the red black tree returns %d\n",
3197 rbtree_assert(ab, ab->root, stderr)));
3198
3199 /* check for a read error or a partially read entry */
3200 if (b != 0) {
3201 ABTRACE(("Result of read return unexpected value %" SK_PRIdZ "\n", b));
3202 err = SKAGGBAG_E_READ;
3203 ABTRACE(("Returning error code %d\n", err));
3204 goto END;
3205 }
3206
3207 ABTRACE(("Reading aggbag from file was successful\n"));
3208 *ab_param = ab;
3209 err = SKAGGBAG_OK;
3210
3211 END:
3212 if (err) {
3213 skAggBagDestroy(&ab);
3214 }
3215 return err;
3216 }
3217
3218
3219 /* Write 'ab' to 'filename'--a wrapper around skAggBagWrite(). */
3220 int
skAggBagSave(const sk_aggbag_t * ab,const char * filename)3221 skAggBagSave(
3222 const sk_aggbag_t *ab,
3223 const char *filename)
3224 {
3225 skstream_t *stream = NULL;
3226 int err = SKAGGBAG_OK;
3227 ssize_t rv;
3228
3229 if (NULL == filename || NULL == ab) {
3230 return SKAGGBAG_E_NULL_PARM;
3231 }
3232
3233 if ((rv = skStreamCreate(&stream, SK_IO_WRITE, SK_CONTENT_SILK))
3234 || (rv = skStreamBind(stream, filename))
3235 || (rv = skStreamOpen(stream)))
3236 {
3237 err = SKAGGBAG_E_WRITE;
3238 goto END;
3239 }
3240
3241 err = skAggBagWrite(ab, stream);
3242
3243 rv = skStreamClose(stream);
3244 if (rv) {
3245 err = SKAGGBAG_E_WRITE;
3246 }
3247
3248 END:
3249 skStreamDestroy(&stream);
3250 return err;
3251 }
3252
3253
3254 int
skAggBagSetCounterFields(sk_aggbag_t * ab,unsigned int field_count,const sk_aggbag_type_t fields[])3255 skAggBagSetCounterFields(
3256 sk_aggbag_t *ab,
3257 unsigned int field_count,
3258 const sk_aggbag_type_t fields[])
3259 {
3260 if (NULL == ab || 0 == field_count || NULL == fields) {
3261 return SKAGGBAG_E_NULL_PARM;
3262 }
3263
3264 return aggBagSetLayout(ab, SK_AGGBAG_COUNTER, field_count, fields);
3265 }
3266
3267 int
skAggBagSetKeyFields(sk_aggbag_t * ab,unsigned int field_count,const sk_aggbag_type_t fields[])3268 skAggBagSetKeyFields(
3269 sk_aggbag_t *ab,
3270 unsigned int field_count,
3271 const sk_aggbag_type_t fields[])
3272 {
3273 if (NULL == ab || 0 == field_count || NULL == fields) {
3274 return SKAGGBAG_E_NULL_PARM;
3275 }
3276
3277 return aggBagSetLayout(ab, SK_AGGBAG_KEY, field_count, fields);
3278 }
3279
3280
3281 const char *
skAggBagStrerror(int err_code)3282 skAggBagStrerror(
3283 int err_code)
3284 {
3285 static char buf[PATH_MAX];
3286
3287 switch ((sk_aggbag_retval_t)err_code) {
3288 case SKAGGBAG_OK:
3289 return "Aggregate Bag command succeeded";
3290 case SKAGGBAG_E_ALLOC:
3291 return "Allocation failed";
3292 case SKAGGBAG_E_NULL_PARM:
3293 return "NULL or invalid parameter passed to function";
3294 case SKAGGBAG_E_FIXED_FIELDS:
3295 return "Aggregate Bag's fields are immutable";
3296 case SKAGGBAG_E_UNDEFINED_KEY:
3297 return "Aggregate Bag's key fields are undefined";
3298 case SKAGGBAG_E_UNDEFINED_COUNTER:
3299 return "Aggregate Bag's counter fields are undefined";
3300 case SKAGGBAG_E_FIELD_CLASS:
3301 return "Incorrect field type (key vs counter)";
3302 case SKAGGBAG_E_FIELDS_DIFFER_KEY:
3303 return "Set of key fields do not match";
3304 case SKAGGBAG_E_FIELDS_DIFFER_COUNTER:
3305 return "Set of counter fields do not match";
3306 case SKAGGBAG_E_GET_SET_MISMATCH:
3307 return "Incorrect get/set function called for field type";
3308 case SKAGGBAG_E_BAD_INDEX:
3309 return "Iterator points to invalid field";
3310 case SKAGGBAG_E_READ:
3311 return "Error while reading Aggregate Bag from stream";
3312 case SKAGGBAG_E_WRITE:
3313 return "Error while writing Aggregate Bag to stream";
3314 case SKAGGBAG_E_HEADER:
3315 return "File header contains unexpected value";
3316 case SKAGGBAG_E_INSERT:
3317 return "Unexpected error during insert";
3318 case SKAGGBAG_E_UNSUPPORTED_IPV6:
3319 return "SiLK is compiled without IPv6 support";
3320 }
3321
3322 snprintf(buf, sizeof(buf),
3323 "Unrecognized Aggregate Bag error code (%d)", err_code);
3324 return buf;
3325 }
3326
3327
3328 int
skAggBagWrite(const sk_aggbag_t * ab,skstream_t * stream)3329 skAggBagWrite(
3330 const sk_aggbag_t *ab,
3331 skstream_t *stream)
3332 {
3333 uint8_t zero_buf[SKAGGBAG_AGGREGATE_MAXLEN];
3334 sk_rbtree_iter_t *it;
3335 sk_file_header_t *hdr;
3336 sk_header_entry_t *hentry;
3337 const uint8_t *data;
3338 ssize_t rv;
3339
3340 if (NULL == ab || NULL == stream) {
3341 ABTRACE(("Got a null parameter ab=%p, stream=%p\n", V(ab), V(stream)));
3342 return SKAGGBAG_E_NULL_PARM;
3343 }
3344
3345 if (NULL == ab->layout[0] || NULL == ab->layout[1]) {
3346 ABTRACE(("AggBag is not fully configured, key = %p, counter = %p\n",
3347 V(ab->layout[0]), V(ab->layout[1])));
3348 return ((NULL == ab->layout[0])
3349 ? SKAGGBAG_E_UNDEFINED_KEY : SKAGGBAG_E_UNDEFINED_COUNTER);
3350 }
3351
3352 hdr = skStreamGetSilkHeader(stream);
3353 ABTRACE(("Header for stream %p is %p\n", V(stream), V(hdr)));
3354 skHeaderSetByteOrder(hdr, SILK_ENDIAN_NATIVE);
3355 skHeaderSetFileFormat(hdr, FT_AGGREGATEBAG);
3356 skHeaderSetRecordVersion(hdr, 1);
3357 skHeaderSetRecordLength(hdr, ab->data_len);
3358
3359 hentry = aggBagHentryCreate(ab);
3360 ABTRACE(("Created the aggbag header entry %p\n", V(hentry)));
3361 if (NULL == hentry) {
3362 return SKAGGBAG_E_ALLOC;
3363 }
3364
3365 rv = skHeaderAddEntry(hdr, hentry);
3366 ABTRACE(("Result of adding hentry to header is %" SK_PRIdZ "\n", rv));
3367 if (rv) {
3368 aggBagHentryFree(hentry);
3369 return SKAGGBAG_E_ALLOC;
3370 }
3371
3372 /* write the file's header */
3373 ABTRACE(("Preparing to write header\n"));
3374 rv = skStreamWriteSilkHeader(stream);
3375 ABTRACE(("Result of writing header is %" SK_PRIdZ "\n", rv));
3376 if (rv) {
3377 return SKAGGBAG_E_WRITE;
3378 }
3379
3380 #if 0
3381 /* THIS BLOCK OF CODE WRITES THE FIELDS TO THE OUTPUT IN ORDER OF
3382 * THEIR FIELD IDS, LOWEST FIELD ID (e.g., sIPv4) FIRST. */
3383 sk_aggbag_field_t fields[AB_LAYOUT_BMAP_SIZE];
3384 sk_aggbag_field_t *f;
3385 uint8_t buffer[UINT16_MAX];
3386 uint8_t *b;
3387
3388 /* determine the fields in numerical order */
3389 field_count = 0;
3390 for (i = 0; i < sizeof(ab->layout[0]->bitmap)/sizeof(uint32_t); ++i) {
3391 uint32_t merged;
3392
3393 merged = ab->layout[0]->bitmap[i] | ab->layout[1]->bitmap[i];
3394 do {
3395 j = 1 + (i << 5);
3396 if ((merged & 0xffff) == 0) {
3397 merged >>= 16;
3398 j += 16;
3399 }
3400 if ((merged & 0xff) == 0) {
3401 merged >>= 8;
3402 j += 8;
3403 }
3404 if ((merged & 0xf) == 0) {
3405 merged >>= 4;
3406 j += 4;
3407 }
3408 if ((merged & 0x3) == 0) {
3409 merged >>= 2;
3410 j += 2;
3411 }
3412 j -= merged & 0x1;
3413 merged >>= 1;
3414 fields[field_count] = j;
3415 ++field_count;
3416 } while (merged);
3417 }
3418
3419 ab_field_t fields[AB_LAYOUT_BMAP_SIZE];
3420 unsigned int field_count;
3421 ab_field_t *f;
3422
3423 field_count = ab->layout[0]->field_count;
3424 memcpy(fields, ab->layout[0]->fields, field_count * sizeof(ab_field_t));
3425
3426 memcpy(fields + field_count, ab->layout[1]->fields,
3427 ab->layout[1]->field_count * sizeof(ab_field_t));
3428 field_count += ab->layout[1]->field_count;
3429
3430 ABTRACE(("Fields in unsorted order:\n"));
3431 for (i = 0, f = fields; i < ab->layout[0]->field_count; ++i, ++f) {
3432 const ab_type_info_t *info = aggBagGetTypeInfo(f->f_type);
3433 ABTRACEQ((" %u %3u %3u %s(%u)\n",
3434 i, f->f_offset, f->f_len, info->ti_name, f->f_type));
3435 }
3436 for ( ; i < field_count; ++i, ++f) {
3437 const ab_type_info_t *info = aggBagGetTypeInfo(f->f_type);
3438 f->f_offset += ab->layout[0]->field_octets;
3439 ABTRACEQ((" %u %3u %3u %s(%u)\n",
3440 i, f->f_offset, f->f_len, info->ti_name, f->f_type));
3441 }
3442
3443 skQSort(fields, field_count, sizeof(ab_field_t), &abLayoutFieldSorter);
3444
3445 ABTRACE(("Fields in sorted order:\n"));
3446 for (i = 0, f = fields; i < field_count; ++i, ++f) {
3447 const ab_type_info_t *info = aggBagGetTypeInfo(f->f_type);
3448 ABTRACEQ((" %u %3u %3u %s(%u)\n",
3449 i, f->f_offset, f->f_len, info->ti_name, f->f_type));
3450 }
3451
3452 /* create an iterator to visit the contents */
3453 ABTRACE(("Creating redblack iterator\n"));
3454 it = sk_rbtree_iter_create(ab);
3455 if (NULL == it) {
3456 ABTRACE(("Failure while creating redblack iterator\n"));
3457 return SKAGGBAG_E_ALLOC;
3458 }
3459
3460 /* write keys and counters */
3461 ABTRACE(("Writing keys and counters...\n"));
3462 while ((data = (const uint8_t *)sk_rbtree_iter_next(it)) != NULL) {
3463 b = buffer;
3464 for (i = 0, f = fields; i < field_count; ++i, ++f) {
3465 memcpy(b, data + f->f_offset, f->f_len);
3466 b += f->f_len;
3467 }
3468 rv = skStreamWrite(stream, buffer, ab->data_len);
3469 if (rv != (ssize_t)ab->data_len) {
3470 sk_rbtree_iter_free(it);
3471 return SKAGGBAG_E_WRITE;
3472 }
3473 }
3474 ABTRACE(("Writing keys and counters...done.\n"));
3475 /* FROM HERE, SHOULD FLUSH STREAM AND RETURN. DO NOT FALL INTO
3476 * THE CODE BELOW */
3477 #endif /* 0 */
3478
3479 memset(zero_buf, 0, sizeof(zero_buf));
3480
3481 /* create an iterator to visit the contents */
3482 ABTRACE(("Creating iterator to visit bag contents\n"));
3483 it = sk_rbtree_iter_create(ab);
3484 if (NULL == it) {
3485 ABTRACE(("Failure while creating iterator to visit bag contents\n"));
3486 return SKAGGBAG_E_ALLOC;
3487 }
3488
3489 /* write keys and counters */
3490 ABTRACE(("Iterating over keys and counters...\n"));
3491 while ((data = (const uint8_t *)sk_rbtree_iter_next(it)) != NULL) {
3492 /* only print counters that are non-zero */
3493 if (0 != memcmp(zero_buf, data + ab->layout[0]->field_octets,
3494 ab->layout[1]->field_octets))
3495 {
3496 rv = skStreamWrite(stream, data, ab->data_len);
3497 if (rv != (ssize_t)ab->data_len) {
3498 sk_rbtree_iter_free(it);
3499 return SKAGGBAG_E_WRITE;
3500 }
3501 }
3502 }
3503
3504 ABTRACE(("Iterating over keys and counters...done.\n"));
3505 sk_rbtree_iter_free(it);
3506
3507 ABTRACE(("Flushing stream and returning\n"));
3508 rv = skStreamFlush(stream);
3509 if (rv) {
3510 return SKAGGBAG_E_WRITE;
3511 }
3512
3513 return SKAGGBAG_OK;
3514 }
3515
3516
3517 #if 0
3518 /**
3519 * Clear any memory that was allocated on 'key'.
3520 */
3521 void
3522 skAggBagClearKey(
3523 const sk_aggbag_t *ab,
3524 sk_aggbag_aggregate_t *key);
3525
3526 /**
3527 * Initialize 'key_field_iter' to iterate over the fields that
3528 * comprise the aggregate key in 'ab' and initialize
3529 * 'counter_field_iter' to iterate over the fields that comprise
3530 * the aggregate counter in 'ab'. Either 'key_field_iter' or
3531 * 'counter_field_iter' may be NULL.
3532 *
3533 * After calling this function, a call to skAggBagFieldIterNext()
3534 * on 'key_field_iter' or 'counter_field_iter' sets the iterator to
3535 * first field in the key or the counter, respectively.
3536 *
3537 * Take no action if 'ab' is NULL.
3538 */
3539 void
3540 skAggBagFieldItersBind(
3541 const sk_aggbag_t *ab,
3542 sk_aggbag_field_t *key_field_iter,
3543 sk_aggbag_field_t *counter_field_iter);
3544 #endif /* 0 */
3545
3546
3547 /*
3548 ** Local Variables:
3549 ** mode:c
3550 ** indent-tabs-mode:nil
3551 ** c-basic-offset:4
3552 ** End:
3553 */
3554