1 /*
2  * Copyright (c) 2008-2020, OARC, Inc.
3  * Copyright (c) 2007-2008, Internet Systems Consortium, Inc.
4  * Copyright (c) 2003-2007, The Measurement Factory, Inc.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  *
14  * 2. Redistributions in binary form must reproduce the above copyright
15  *    notice, this list of conditions and the following disclaimer in
16  *    the documentation and/or other materials provided with the
17  *    distribution.
18  *
19  * 3. Neither the name of the copyright holder nor the names of its
20  *    contributors may be used to endorse or promote products derived
21  *    from this software without specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27  * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
29  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
31  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
33  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34  * POSSIBILITY OF SUCH DAMAGE.
35  */
36 
37 #include "config.h"
38 
39 #include "md_array.h"
40 
41 #include <stdlib.h>
42 #include <assert.h>
43 #include <string.h>
44 
45 #include "xmalloc.h"
46 #include "dataset_opt.h"
47 #include "dns_message.h"
48 #include "pcap.h"
49 #include "syslog_debug.h"
50 
51 /*
52  * Private
53  */
54 
55 struct d2sort {
56     char* label;
57     int   val;
58 };
59 
d2cmp(const void * a,const void * b)60 static int d2cmp(const void* a, const void* b)
61 {
62     /*
63      * descending sort order (larger to smaller)
64      */
65     return ((struct d2sort*)b)->val - ((struct d2sort*)a)->val;
66 }
67 
md_array_free(md_array * a)68 static void md_array_free(md_array* a)
69 {
70     if (a->name)
71         xfree((char*)a->name);
72     if (a->d1.type)
73         xfree((char*)a->d1.type);
74     if (a->d2.type)
75         xfree((char*)a->d2.type);
76     /* a->array contents were in an arena, so we don't need to free them. */
77     xfree(a);
78 }
79 
md_array_grow(md_array * a,int i1,int i2)80 static void md_array_grow(md_array* a, int i1, int i2)
81 {
82     int            new_d1_sz, new_d2_sz;
83     md_array_node* d1 = NULL;
84     int*           d2 = NULL;
85 
86     if (i1 < a->d1.alloc_sz && i2 < a->array[i1].alloc_sz)
87         return;
88 
89     /* dimension 1 */
90     new_d1_sz = a->d1.alloc_sz;
91     if (i1 >= a->d1.alloc_sz) {
92         /* pick a new size */
93         if (new_d1_sz == 0)
94             new_d1_sz = 2;
95         while (i1 >= new_d1_sz)
96             new_d1_sz = new_d1_sz << 1;
97 
98         /* allocate new array */
99         d1 = acalloc(new_d1_sz, sizeof(*d1));
100         if (NULL == d1) {
101             /* oops, undo! */
102             return;
103         }
104 
105         /* copy old contents to new array */
106         memcpy(d1, a->array, a->d1.alloc_sz * sizeof(*d1));
107 
108     } else {
109         d1 = a->array;
110     }
111 
112     /* dimension 2 */
113     new_d2_sz = d1[i1].alloc_sz;
114     if (i2 >= d1[i1].alloc_sz) {
115         /* pick a new size */
116         if (new_d2_sz == 0)
117             new_d2_sz = 2;
118         while (i2 >= new_d2_sz)
119             new_d2_sz = new_d2_sz << 1;
120 
121         /* allocate new array */
122         d2 = acalloc(new_d2_sz, sizeof(*d2));
123         if (NULL == d2) {
124             /* oops, undo! */
125             afree(d1);
126             return;
127         }
128 
129         /* copy old contents to new array */
130         memcpy(d2, d1[i1].array, d1[i1].alloc_sz * sizeof(*d2));
131     }
132 
133     if (d1 != a->array) {
134         if (a->array) {
135             dfprintf(0, "grew d1 of %s from %d to %d", a->name, a->d1.alloc_sz, new_d1_sz);
136             afree(a->array);
137         }
138         a->array       = d1;
139         a->d1.alloc_sz = new_d1_sz;
140     }
141     if (d2) {
142         if (a->array[i1].array) {
143             dfprintf(0, "grew d2[%d] of %s from %d to %d", i1, a->name, a->array[i1].alloc_sz, new_d2_sz);
144             afree(a->array[i1].array);
145         }
146         a->array[i1].array    = d2;
147         a->array[i1].alloc_sz = new_d2_sz;
148     }
149 
150     if (new_d2_sz > a->d2.alloc_sz)
151         a->d2.alloc_sz = new_d2_sz;
152 }
153 
154 /*
155  * Public
156  */
157 
md_array_create(const char * name,filter_list * fl,const char * type1,indexer * idx1,const char * type2,indexer * idx2)158 md_array* md_array_create(const char* name, filter_list* fl, const char* type1, indexer* idx1, const char* type2, indexer* idx2)
159 {
160     md_array* a = xcalloc(1, sizeof(*a));
161     if (NULL == a)
162         return NULL;
163     a->name = xstrdup(name);
164     if (a->name == NULL) {
165         md_array_free(a);
166         return NULL;
167     }
168     a->filter_list = fl;
169     a->d1.type     = xstrdup(type1);
170     if (a->d1.type == NULL) {
171         md_array_free(a);
172         return NULL;
173     }
174     a->d1.indexer  = idx1;
175     a->d1.alloc_sz = 0;
176     a->d2.type     = xstrdup(type2);
177     if (a->d2.type == NULL) {
178         md_array_free(a);
179         return NULL;
180     }
181     a->d2.indexer  = idx2;
182     a->d2.alloc_sz = 0;
183     a->array       = NULL; /* will be allocated when needed, in an arena. */
184     return a;
185 }
186 
md_array_clear(md_array * a)187 void md_array_clear(md_array* a)
188 {
189     /* a->array contents were in an arena, so we don't need to free them. */
190     a->array       = NULL;
191     a->d1.alloc_sz = 0;
192     if (a->d1.indexer->reset_fn)
193         a->d1.indexer->reset_fn();
194     a->d2.alloc_sz = 0;
195     if (a->d2.indexer->reset_fn)
196         a->d2.indexer->reset_fn();
197 }
198 
md_array_count(md_array * a,const void * vp)199 int md_array_count(md_array* a, const void* vp)
200 {
201     int          i1;
202     int          i2;
203     filter_list* fl;
204 
205     for (fl = a->filter_list; fl; fl = fl->next)
206         if (0 == fl->filter->func(vp, fl->filter->context))
207             return -1;
208 
209     if ((i1 = a->d1.indexer->index_fn(vp)) < 0)
210         return -1;
211     if ((i2 = a->d2.indexer->index_fn(vp)) < 0)
212         return -1;
213 
214     md_array_grow(a, i1, i2);
215 
216     assert(i1 < a->d1.alloc_sz);
217     assert(i2 < a->d2.alloc_sz);
218     return ++a->array[i1].array[i2];
219 }
220 
md_array_flush(md_array * a)221 void md_array_flush(md_array* a)
222 {
223     const void* vp;
224 
225     if (a->d1.indexer->flush_fn)
226         a->d1.indexer->flush_fn(flush_on);
227     if (a->d2.indexer->flush_fn)
228         a->d2.indexer->flush_fn(flush_on);
229 
230     if (a->d1.indexer->flush_fn) {
231         while ((vp = a->d1.indexer->flush_fn(flush_get))) {
232             md_array_count(a, vp);
233         }
234     }
235     if (a->d2.indexer->flush_fn) {
236         while ((vp = a->d2.indexer->flush_fn(flush_get))) {
237             md_array_count(a, vp);
238         }
239     }
240 
241     if (a->d1.indexer->flush_fn)
242         a->d1.indexer->flush_fn(flush_off);
243     if (a->d2.indexer->flush_fn)
244         a->d2.indexer->flush_fn(flush_off);
245 }
246 
md_array_print(md_array * a,md_array_printer * pr,FILE * fp)247 int md_array_print(md_array* a, md_array_printer* pr, FILE* fp)
248 {
249     const char* label1;
250     const char* label2;
251     int         i1;
252     int         i2;
253 
254     a->d1.indexer->iter_fn(NULL);
255     pr->start_array(fp, a->name);
256     pr->d1_type(fp, a->d1.type);
257     pr->d2_type(fp, a->d2.type);
258     pr->start_data(fp);
259     while ((i1 = a->d1.indexer->iter_fn(&label1)) > -1) {
260         int            skipped     = 0;
261         int            skipped_sum = 0;
262         int            nvals;
263         int            si = 0;
264         struct d2sort* sortme;
265 
266         if (i1 >= a->d1.alloc_sz)
267             /*
268              * Its okay (not a bug) for the indexer's index to be larger
269              * than the array size.  The indexer may have grown for use in a
270              * different array, but the filter prevented it from growing this
271              * particular array so far.
272              */
273             continue;
274 
275         pr->d1_begin(fp, label1);
276         a->d2.indexer->iter_fn(NULL);
277         nvals = a->d2.alloc_sz;
278 
279         sortme = xcalloc(nvals, sizeof(*sortme));
280         if (NULL == sortme) {
281             dsyslogf(LOG_CRIT, "Cant output %s file chunk due to malloc failure!", pr->format);
282             continue;
283         }
284 
285         while ((i2 = a->d2.indexer->iter_fn(&label2)) > -1) {
286             int val;
287             if (i2 >= a->array[i1].alloc_sz)
288                 continue;
289             val = a->array[i1].array[i2];
290             if (0 == val)
291                 continue;
292             if (a->opts.min_count && (a->opts.min_count > val)) {
293                 skipped++;
294                 skipped_sum += val;
295                 continue;
296             }
297             sortme[si].val   = val;
298             sortme[si].label = xstrdup(label2);
299             if (NULL == sortme[si].label)
300                 break;
301             si++;
302         }
303         assert(si <= nvals);
304         nvals = si;
305 
306         qsort(sortme, nvals, sizeof(*sortme), d2cmp);
307 
308         for (si = 0; si < nvals; si++) {
309             if (0 == a->opts.max_cells || si < a->opts.max_cells) {
310                 pr->print_element(fp, sortme[si].label, sortme[si].val);
311             } else {
312                 skipped++;
313                 skipped_sum += sortme[si].val;
314             }
315             xfree(sortme[si].label);
316         }
317         xfree(sortme);
318 
319         if (skipped) {
320             pr->print_element(fp, "-:SKIPPED:-", skipped);
321             pr->print_element(fp, "-:SKIPPED_SUM:-", skipped_sum);
322         }
323         pr->d1_end(fp, label1);
324     }
325     pr->finish_data(fp);
326     pr->finish_array(fp);
327     return 0;
328 }
329 
md_array_filter_list_append(filter_list ** fl,filter_defn * f)330 filter_list** md_array_filter_list_append(filter_list** fl, filter_defn* f)
331 {
332     *fl = xcalloc(1, sizeof(**fl));
333     if (NULL == (*fl))
334         return NULL;
335     (*fl)->filter = f;
336     return (&(*fl)->next);
337 }
338 
md_array_create_filter(const char * name,filter_func func,const void * context)339 filter_defn* md_array_create_filter(const char* name, filter_func func, const void* context)
340 {
341     filter_defn* f = xcalloc(1, sizeof(*f));
342     if (NULL == f)
343         return NULL;
344     f->name = xstrdup(name);
345     if (NULL == f->name) {
346         xfree(f);
347         return NULL;
348     }
349     f->func    = func;
350     f->context = context;
351     return f;
352 }
353