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