1d17db2df58754218a477e23fb7af05bdb54f384
[xonotic/gmqcc.git] / stat.c
1 /*
2  * Copyright (C) 2012, 2013
3  *     Dale Weiler
4  *     Wolfgang Bumiller
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a copy of
7  * this software and associated documentation files (the "Software"), to deal in
8  * the Software without restriction, including without limitation the rights to
9  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
10  * of the Software, and to permit persons to whom the Software is furnished to do
11  * so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in all
14  * copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22  * SOFTWARE.
23  */
24
25 #include <string.h>
26 #include <stdlib.h>
27
28 #include "gmqcc.h"
29
30 /*
31  * For the valgrind integration of our allocator. This allows us to have
32  * more `accurate` valgrind output for our allocator, and also secures the
33  * possible underflows (where one could obtain access to the redzone that
34  * represents info about that allocation).
35  */
36 #ifndef NVALGRIND
37 #   include <valgrind/valgrind.h>
38 #   include <valgrind/memcheck.h>
39 #else
40 #   define VALGRIND_MALLOCLIKE_BLOCK(PTR, ALLOC_SIZE, REDZONE_SIZE, ZEROED)
41 #   define VALGRIND_FREELIKE_BLOCK(PTR, REDZONE_SIZE)
42 #   define VALGRIND_MAKE_MEM_DEFINED(PTR, REDZONE_SIZE)
43 #   define VALGRIND_MAKE_MEM_NOACCESS(PTR, REDZONE_SIZE)
44 #endif
45
46 /*
47  * GMQCC performs tons of allocations, constructions, and crazyness
48  * all around. When trying to optimizes systems, or just get fancy
49  * statistics out of the compiler, it's often printf mess. This file
50  * implements the statistics system of the compiler. I.E the allocator
51  * we use to track allocations, and other systems of interest.
52  */
53 #define ST_SIZE 1024
54
55 typedef struct stat_mem_block_s {
56     const char              *file;
57     size_t                   line;
58     size_t                   size;
59     struct stat_mem_block_s *next;
60     struct stat_mem_block_s *prev;
61 } stat_mem_block_t;
62
63 typedef struct {
64     size_t key;
65     size_t value;
66 } stat_size_entry_t, **stat_size_table_t;
67
68 static uint64_t          stat_mem_allocated         = 0;
69 static uint64_t          stat_mem_deallocated       = 0;
70 static uint64_t          stat_mem_allocated_total   = 0;
71 static uint64_t          stat_mem_deallocated_total = 0;
72 static uint64_t          stat_mem_high              = 0;
73 static uint64_t          stat_mem_peak              = 0;
74 static uint64_t          stat_mem_strdups           = 0;
75 static uint64_t          stat_used_strdups          = 0;
76 static uint64_t          stat_used_vectors          = 0;
77 static uint64_t          stat_used_hashtables       = 0;
78 static uint64_t          stat_type_vectors          = 0;
79 static uint64_t          stat_type_hashtables       = 0;
80 static stat_size_table_t stat_size_vectors          = NULL;
81 static stat_size_table_t stat_size_hashtables       = NULL;
82 static stat_mem_block_t *stat_mem_block_root        = NULL;
83
84 /*
85  * A tiny size_t key-value hashtbale for tracking vector and hashtable
86  * sizes. We can use it for other things too, if we need to. This is
87  * very TIGHT, and efficent in terms of space though.
88  */
89 static stat_size_table_t stat_size_new(void) {
90     return (stat_size_table_t)memset(
91         mem_a(sizeof(stat_size_entry_t*) * ST_SIZE),
92         0, ST_SIZE * sizeof(stat_size_entry_t*)
93     );
94 }
95
96 static void stat_size_del(stat_size_table_t table) {
97     size_t i = 0;
98     for (; i < ST_SIZE; i++) if(table[i]) mem_d(table[i]);
99     mem_d(table);
100 }
101
102 static stat_size_entry_t *stat_size_get(stat_size_table_t table, size_t key) {
103     size_t hash = (key % ST_SIZE);
104     while (table[hash] && table[hash]->key != key)
105         hash = (hash + 1) % ST_SIZE;
106     return table[hash];
107 }
108 static void stat_size_put(stat_size_table_t table, size_t key, size_t value) {
109     size_t hash = (key % ST_SIZE);
110     while (table[hash] && table[hash]->key != key)
111         hash = (hash + 1) % ST_SIZE;
112     table[hash]        = (stat_size_entry_t*)mem_a(sizeof(stat_size_entry_t));
113     table[hash]->key   = key;
114     table[hash]->value = value;
115 }
116
117 /*
118  * A basic header of information wrapper allocator. Simply stores
119  * information as a header, returns the memory + 1 past it, can be
120  * retrieved again with - 1. Where type is stat_mem_block_t*.
121  */
122 void *stat_mem_allocate(size_t size, size_t line, const char *file) {
123     stat_mem_block_t *info = (stat_mem_block_t*)malloc(sizeof(stat_mem_block_t) + size);
124     void             *data = (void*)(info + 1);
125
126     if(GMQCC_UNLIKELY(!info))
127         return NULL;
128
129     info->line = line;
130     info->size = size;
131     info->file = file;
132     info->prev = NULL;
133     info->next = stat_mem_block_root;
134
135     /* likely since it only happens once */
136     if (GMQCC_LIKELY(stat_mem_block_root != NULL)) {
137         VALGRIND_MAKE_MEM_DEFINED(stat_mem_block_root, sizeof(stat_mem_block_t));
138         stat_mem_block_root->prev = info;
139         VALGRIND_MAKE_MEM_NOACCESS(stat_mem_block_root, sizeof(stat_mem_block_t));
140     }
141
142     stat_mem_block_root       = info;
143     stat_mem_allocated       += size;
144     stat_mem_high            += size;
145     stat_mem_allocated_total ++;
146
147     if (stat_mem_high > stat_mem_peak)
148         stat_mem_peak = stat_mem_high;
149
150     VALGRIND_MALLOCLIKE_BLOCK(data, size, sizeof(stat_mem_block_t), 0);
151     return data;
152 }
153
154 void stat_mem_deallocate(void *ptr) {
155     stat_mem_block_t *info = NULL;
156
157     if (GMQCC_UNLIKELY(!ptr))
158         return;
159
160     info = ((stat_mem_block_t*)ptr - 1);
161
162     /*
163      * we need access to the redzone that represents the info block
164      * so lets do that.
165      */
166     VALGRIND_MAKE_MEM_DEFINED(info, sizeof(stat_mem_block_t));
167
168     stat_mem_deallocated       += info->size;
169     stat_mem_high              -= info->size;
170     stat_mem_deallocated_total ++;
171
172     if (info->prev) {
173         /* just need access for a short period */
174         VALGRIND_MAKE_MEM_DEFINED(info->prev, sizeof(stat_mem_block_t));
175         info->prev->next = info->next;
176         /* don't need access anymore */
177         VALGRIND_MAKE_MEM_NOACCESS(info->prev, sizeof(stat_mem_block_t));
178     }
179     if (info->next) {
180         /* just need access for a short period */
181         VALGRIND_MAKE_MEM_DEFINED(info->next, sizeof(stat_mem_block_t));
182         info->next->prev = info->prev;
183         /* don't need access anymore */
184         VALGRIND_MAKE_MEM_NOACCESS(info->next, sizeof(stat_mem_block_t));
185     }
186
187     /* move ahead */
188     if (info == stat_mem_block_root)
189         stat_mem_block_root = info->next;
190
191     free(info);
192     VALGRIND_MAKE_MEM_NOACCESS(info, sizeof(stat_mem_block_t));
193     VALGRIND_FREELIKE_BLOCK(ptr, sizeof(stat_mem_block_t));
194 }
195
196 void *stat_mem_reallocate(void *ptr, size_t size, size_t line, const char *file) {
197     stat_mem_block_t *oldinfo = NULL;
198     stat_mem_block_t *newinfo;
199
200     if (GMQCC_UNLIKELY(!ptr))
201         return stat_mem_allocate(size, line, file);
202
203     /* stay consistent with glibc */
204     if (GMQCC_UNLIKELY(!size)) {
205         stat_mem_deallocate(ptr);
206         return NULL;
207     }
208
209     oldinfo = ((stat_mem_block_t*)ptr - 1);
210     newinfo = ((stat_mem_block_t*)malloc(sizeof(stat_mem_block_t) + size));
211
212     if (GMQCC_UNLIKELY(!newinfo)) {
213         stat_mem_deallocate(ptr);
214         return NULL;
215     }
216
217     VALGRIND_MALLOCLIKE_BLOCK(newinfo + 1, size, sizeof(stat_mem_block_t), 0);
218
219     /* we need access to the old info redzone */
220     VALGRIND_MAKE_MEM_DEFINED(oldinfo, sizeof(stat_mem_block_t));
221
222     memcpy(newinfo+1, oldinfo+1, oldinfo->size);
223
224     if (oldinfo->prev) {
225         /* just need access for a short period */
226         VALGRIND_MAKE_MEM_DEFINED(oldinfo->prev, sizeof(stat_mem_block_t));
227         oldinfo->prev->next = oldinfo->next;
228         /* don't need access anymore */
229         VALGRIND_MAKE_MEM_NOACCESS(oldinfo->prev, sizeof(stat_mem_block_t));
230     }
231
232     if (oldinfo->next) {
233         /* just need access for a short period */
234         VALGRIND_MAKE_MEM_DEFINED(oldinfo->next, sizeof(stat_mem_block_t));
235         oldinfo->next->prev = oldinfo->prev;
236         /* don't need access anymore */
237         VALGRIND_MAKE_MEM_NOACCESS(oldinfo->next, sizeof(stat_mem_block_t));
238     }
239
240     /* move ahead */
241     if (oldinfo == stat_mem_block_root)
242         stat_mem_block_root = oldinfo->next;
243
244     /* we need access to the redzone for the newinfo block */
245     VALGRIND_MAKE_MEM_DEFINED(newinfo, sizeof(stat_mem_block_t));
246
247     newinfo->line = line;
248     newinfo->size = size;
249     newinfo->file = file;
250     newinfo->prev = NULL;
251     newinfo->next = stat_mem_block_root;
252
253     /*
254      * likely since the only time there is no root is when it's
255      * being initialized first.
256      */
257     if (GMQCC_LIKELY(stat_mem_block_root != NULL)) {
258         /* we need access to the root */
259         VALGRIND_MAKE_MEM_DEFINED(stat_mem_block_root, sizeof(stat_mem_block_t));
260         stat_mem_block_root->prev = newinfo;
261         /* kill access */
262         VALGRIND_MAKE_MEM_NOACCESS(stat_mem_block_root, sizeof(stat_mem_block_t));
263     }
264
265     stat_mem_block_root = newinfo;
266     stat_mem_allocated -= oldinfo->size;
267     stat_mem_high      -= oldinfo->size;
268     stat_mem_allocated += newinfo->size;
269     stat_mem_high      += newinfo->size;
270
271     /*
272      * we're finished with the redzones, lets kill the access
273      * to them.
274      */
275     VALGRIND_MAKE_MEM_NOACCESS(newinfo, sizeof(stat_mem_block_t));
276     VALGRIND_MAKE_MEM_NOACCESS(oldinfo, sizeof(stat_mem_block_t));
277
278     if (stat_mem_high > stat_mem_peak)
279         stat_mem_peak = stat_mem_high;
280
281     free(oldinfo);
282     VALGRIND_FREELIKE_BLOCK(ptr, sizeof(stat_mem_block_t));
283     return newinfo + 1;
284 }
285
286 /*
287  * strdup does it's own malloc, we need to track malloc. We don't want
288  * to overwrite malloc though, infact, we can't really hook it at all
289  * without library specific assumptions. So we re implement strdup.
290  */
291 char *stat_mem_strdup(const char *src, size_t line, const char *file, bool empty) {
292     size_t len = 0;
293     char  *ptr = NULL;
294
295     if (!src)
296         return NULL;
297
298     len = strlen(src);
299     if (((!empty) ? len : true) && (ptr = (char*)stat_mem_allocate(len + 1, line, file))) {
300         memcpy(ptr, src, len);
301         ptr[len] = '\0';
302     }
303
304     stat_used_strdups ++;
305     stat_mem_strdups  += len;
306     return ptr;
307 }
308
309 /*
310  * The reallocate function for resizing vectors.
311  */
312 void _util_vec_grow(void **a, size_t i, size_t s) {
313     vector_t          *d = vec_meta(*a);
314     size_t             m = 0;
315     stat_size_entry_t *e = NULL;
316     void              *p = NULL;
317
318     if (*a) {
319         m = 2 * d->allocated + i;
320         p = mem_r(d, s * m + sizeof(vector_t));
321     } else {
322         m = i + 1;
323         p = mem_a(s * m + sizeof(vector_t));
324         ((vector_t*)p)->used = 0;
325         stat_used_vectors++;
326     }
327
328     if (!stat_size_vectors)
329         stat_size_vectors = stat_size_new();
330
331     if ((e = stat_size_get(stat_size_vectors, s))) {
332         e->value ++;
333     } else {
334         stat_size_put(stat_size_vectors, s, 1); /* start off with 1 */
335         stat_type_vectors++;
336     }
337
338     *a = (vector_t*)p + 1;
339     vec_meta(*a)->allocated = m;
340 }
341
342 /*
343  * Hash table for generic data, based on dynamic memory allocations
344  * all around.  This is the internal interface, please look for
345  * EXPOSED INTERFACE comment below
346  */
347 typedef struct hash_node_t {
348     char               *key;   /* the key for this node in table */
349     void               *value; /* pointer to the data as void*   */
350     struct hash_node_t *next;  /* next node (linked list)        */
351 } hash_node_t;
352
353 /*
354  * This is a patched version of the Murmur2 hashing function to use
355  * a proper pre-mix and post-mix setup. Infact this is Murmur3 for
356  * the most part just reinvented.
357  *
358  * Murmur 2 contains an inner loop such as:
359  * while (l >= 4) {
360  *      u32 k = *(u32*)d;
361  *      k *= m;
362  *      k ^= k >> r;
363  *      k *= m;
364  *
365  *      h *= m;
366  *      h ^= k;
367  *      d += 4;
368  *      l -= 4;
369  * }
370  *
371  * The two u32s that form the key are the same value x (pulled from data)
372  * this premix stage will perform the same results for both values. Unrolled
373  * this produces just:
374  *  x *= m;
375  *  x ^= x >> r;
376  *  x *= m;
377  *
378  *  h *= m;
379  *  h ^= x;
380  *  h *= m;
381  *  h ^= x;
382  *
383  * This appears to be fine, except what happens when m == 1? well x
384  * cancels out entierly, leaving just:
385  *  x ^= x >> r;
386  *  h ^= x;
387  *  h ^= x;
388  *
389  * So all keys hash to the same value, but how often does m == 1?
390  * well, it turns out testing x for all possible values yeilds only
391  * 172,013,942 unique results instead of 2^32. So nearly ~4.6 bits
392  * are cancelled out on average!
393  *
394  * This means we have a 14.5% (rounded) chance of colliding more, which
395  * results in another bucket/chain for the hashtable.
396  *
397  * We fix it buy upgrading the pre and post mix ssystems to align with murmur
398  * hash 3.
399  */
400 #if 1
401 #define GMQCC_ROTL32(X, R) (((X) << (R)) | ((X) >> (32 - (R))))
402 GMQCC_INLINE size_t util_hthash(hash_table_t *ht, const char *key) {
403     const unsigned char *data   = (const unsigned char *)key;
404     const size_t         len    = strlen(key);
405     const size_t         block  = len / 4;
406     const uint32_t       mask1  = 0xCC9E2D51;
407     const uint32_t       mask2  = 0x1B873593;
408     const uint32_t      *blocks = (const uint32_t*)(data + block * 4);
409     const unsigned char *tail   = (const unsigned char *)(data + block * 4);
410
411     size_t   i;
412     uint32_t k;
413     uint32_t h = 0x1EF0 ^ len;
414
415     for (i = -((int)block); i; i++) {
416         k  = blocks[i];
417         k *= mask1;
418         k  = GMQCC_ROTL32(k, 15);
419         k *= mask2;
420         h ^= k;
421         h  = GMQCC_ROTL32(h, 13);
422         h  = h * 5 + 0xE6546B64;
423     }
424
425     k = 0;
426     switch (len & 3) {
427         case 3:
428             k ^= tail[2] << 16;
429         case 2:
430             k ^= tail[1] << 8;
431         case 1:
432             k ^= tail[0];
433             k *= mask1;
434             k  = GMQCC_ROTL32(k, 15);
435             k *= mask2;
436             h ^= k;
437     }
438
439     h ^= len;
440     h ^= h >> 16;
441     h *= 0x85EBCA6B;
442     h ^= h >> 13;
443     h *= 0xC2B2AE35;
444     h ^= h >> 16;
445
446     return (size_t) (h % ht->size);
447 }
448 #undef GMQCC_ROTL32
449 #else
450 /* We keep the old for reference */
451 GMQCC_INLINE size_t util_hthash(hash_table_t *ht, const char *key) {
452     const uint32_t       mix   = 0x5BD1E995;
453     const uint32_t       rot   = 24;
454     size_t               size  = strlen(key);
455     uint32_t             hash  = 0x1EF0 /* LICRC TAB */  ^ size;
456     uint32_t             alias = 0;
457     const unsigned char *data  = (const unsigned char*)key;
458
459     while (size >= 4) {
460         alias  = (data[0] | (data[1] << 8) | (data[2] << 16) | (data[3] << 24));
461         alias *= mix;
462         alias ^= alias >> rot;
463         alias *= mix;
464
465         hash  *= mix;
466         hash  ^= alias;
467
468         data += 4;
469         size -= 4;
470     }
471
472     switch (size) {
473         case 3: hash ^= data[2] << 16;
474         case 2: hash ^= data[1] << 8;
475         case 1: hash ^= data[0];
476                 hash *= mix;
477     }
478
479     hash ^= hash >> 13;
480     hash *= mix;
481     hash ^= hash >> 15;
482
483     return (size_t) (hash % ht->size);
484 }
485 #endif
486
487 static hash_node_t *_util_htnewpair(const char *key, void *value) {
488     hash_node_t *node;
489     if (!(node = (hash_node_t*)mem_a(sizeof(hash_node_t))))
490         return NULL;
491
492     if (!(node->key = util_strdupe(key))) {
493         mem_d(node);
494         return NULL;
495     }
496
497     node->value = value;
498     node->next  = NULL;
499
500     return node;
501 }
502
503 /*
504  * EXPOSED INTERFACE for the hashtable implementation
505  * util_htnew(size)                             -- to make a new hashtable
506  * util_htset(table, key, value, sizeof(value)) -- to set something in the table
507  * util_htget(table, key)                       -- to get something from the table
508  * util_htdel(table)                            -- to delete the table
509  */
510 hash_table_t *util_htnew(size_t size) {
511     hash_table_t      *hashtable = NULL;
512     stat_size_entry_t *find      = NULL;
513
514     if (size < 1)
515         return NULL;
516
517     if (!stat_size_hashtables)
518         stat_size_hashtables = stat_size_new();
519
520     if (!(hashtable = (hash_table_t*)mem_a(sizeof(hash_table_t))))
521         return NULL;
522
523     if (!(hashtable->table = (hash_node_t**)mem_a(sizeof(hash_node_t*) * size))) {
524         mem_d(hashtable);
525         return NULL;
526     }
527
528     if ((find = stat_size_get(stat_size_hashtables, size)))
529         find->value++;
530     else {
531         stat_type_hashtables++;
532         stat_size_put(stat_size_hashtables, size, 1);
533     }
534
535     hashtable->size = size;
536     memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
537
538     stat_used_hashtables++;
539     return hashtable;
540 }
541
542 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
543     hash_node_t *newnode = NULL;
544     hash_node_t *next    = NULL;
545     hash_node_t *last    = NULL;
546
547     next = ht->table[bin];
548
549     while (next && next->key && strcmp(key, next->key) > 0)
550         last = next, next = next->next;
551
552     /* already in table, do a replace */
553     if (next && next->key && strcmp(key, next->key) == 0) {
554         next->value = value;
555     } else {
556         /* not found, grow a pair man :P */
557         newnode = _util_htnewpair(key, value);
558         if (next == ht->table[bin]) {
559             newnode->next  = next;
560             ht->table[bin] = newnode;
561         } else if (!next) {
562             last->next = newnode;
563         } else {
564             newnode->next = next;
565             last->next = newnode;
566         }
567     }
568 }
569
570 void util_htset(hash_table_t *ht, const char *key, void *value) {
571     util_htseth(ht, key, util_hthash(ht, key), value);
572 }
573
574 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
575     hash_node_t *pair = ht->table[bin];
576
577     while (pair && pair->key && strcmp(key, pair->key) > 0)
578         pair = pair->next;
579
580     if (!pair || !pair->key || strcmp(key, pair->key) != 0)
581         return NULL;
582
583     return pair->value;
584 }
585
586 void *util_htget(hash_table_t *ht, const char *key) {
587     return util_htgeth(ht, key, util_hthash(ht, key));
588 }
589
590 void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin);
591 void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin) {
592     hash_node_t *pair;
593     size_t len, keylen;
594     int cmp;
595
596     keylen = strlen(key);
597
598     pair = ht->table[bin];
599     while (pair && pair->key) {
600         len = strlen(pair->key);
601         if (len < keylen) {
602             pair = pair->next;
603             continue;
604         }
605         if (keylen == len) {
606             cmp = strcmp(key, pair->key);
607             if (cmp == 0)
608                 return pair->value;
609             if (cmp < 0)
610                 return NULL;
611             pair = pair->next;
612             continue;
613         }
614         cmp = strcmp(key, pair->key + len - keylen);
615         if (cmp == 0) {
616             uintptr_t up = (uintptr_t)pair->value;
617             up += len - keylen;
618             return (void*)up;
619         }
620         pair = pair->next;
621     }
622     return NULL;
623 }
624
625 /*
626  * Free all allocated data in a hashtable, this is quite the amount
627  * of work.
628  */
629 void util_htrem(hash_table_t *ht, void (*callback)(void *data)) {
630     size_t i = 0;
631
632     for (; i < ht->size; ++i) {
633         hash_node_t *n = ht->table[i];
634         hash_node_t *p;
635
636         /* free in list */
637         while (n) {
638             if (n->key)
639                 mem_d(n->key);
640             if (callback)
641                 callback(n->value);
642             p = n;
643             n = p->next;
644             mem_d(p);
645         }
646
647     }
648     /* free table */
649     mem_d(ht->table);
650     mem_d(ht);
651 }
652
653 void util_htrmh(hash_table_t *ht, const char *key, size_t bin, void (*cb)(void*)) {
654     hash_node_t **pair = &ht->table[bin];
655     hash_node_t *tmp;
656
657     while (*pair && (*pair)->key && strcmp(key, (*pair)->key) > 0)
658         pair = &(*pair)->next;
659
660     tmp = *pair;
661     if (!tmp || !tmp->key || strcmp(key, tmp->key) != 0)
662         return;
663
664     if (cb)
665         (*cb)(tmp->value);
666
667     *pair = tmp->next;
668     mem_d(tmp->key);
669     mem_d(tmp);
670 }
671
672 void util_htrm(hash_table_t *ht, const char *key, void (*cb)(void*)) {
673     util_htrmh(ht, key, util_hthash(ht, key), cb);
674 }
675
676 void util_htdel(hash_table_t *ht) {
677     util_htrem(ht, NULL);
678 }
679
680 /*
681  * The following functions below implement printing / dumping of statistical
682  * information.
683  */
684 static void stat_dump_mem_contents(stat_mem_block_t *memory, uint16_t cols) {
685     uint32_t i, j;
686     for (i = 0; i < memory->size + ((memory->size % cols) ? (cols - memory->size % cols) : 0); i++) {
687         if (i % cols == 0)    con_out(" 0x%06X: ", i);
688         if (i < memory->size) con_out("%02X " , 0xFF & ((unsigned char*)(memory + 1))[i]);
689         else                  con_out(" ");
690
691         if ((uint16_t)(i % cols) == (cols - 1)) {
692             for (j = i - (cols - 1); j <= i; j++) {
693                 con_out("%c",
694                     (j >= memory->size)
695                         ? ' '
696                         : (util_isprint(((unsigned char*)(memory + 1))[j]))
697                             ? 0xFF & ((unsigned char*)(memory + 1)) [j]
698                             : '.'
699                 );
700             }
701             con_out("\n");
702         }
703     }
704 }
705
706 static void stat_dump_mem_leaks(void) {
707     stat_mem_block_t *info;
708     /* we need access to the root for this */
709     VALGRIND_MAKE_MEM_DEFINED(stat_mem_block_root, sizeof(stat_mem_block_t));
710     for (info = stat_mem_block_root; info; info = info->next) {
711         /* we need access to the block */
712         VALGRIND_MAKE_MEM_DEFINED(info, sizeof(stat_mem_block_t));
713         con_out("lost: %u (bytes) at %s:%u\n",
714             info->size,
715             info->file,
716             info->line
717         );
718
719         stat_dump_mem_contents(info, OPTS_OPTION_U16(OPTION_MEMDUMPCOLS));
720
721         /*
722          * we're finished with the access, the redzone should be marked
723          * inaccesible so that invalid read/writes that could 'step-into'
724          * those redzones will show up as invalid read/writes in valgrind.
725          */
726         VALGRIND_MAKE_MEM_NOACCESS(info, sizeof(stat_mem_block_t));
727     }
728     VALGRIND_MAKE_MEM_NOACCESS(stat_mem_block_root, sizeof(stat_mem_block_t));
729 }
730
731 static void stat_dump_mem_info(void) {
732     con_out("Memory Information:\n\
733     Total allocations:   %llu\n\
734     Total deallocations: %llu\n\
735     Total allocated:     %f (MB)\n\
736     Total deallocated:   %f (MB)\n\
737     Total peak memory:   %f (MB)\n\
738     Total leaked memory: %f (MB) in %llu allocations\n",
739         stat_mem_allocated_total,
740         stat_mem_deallocated_total,
741         (float)(stat_mem_allocated)                        / 1048576.0f,
742         (float)(stat_mem_deallocated)                      / 1048576.0f,
743         (float)(stat_mem_peak)                             / 1048576.0f,
744         (float)(stat_mem_allocated - stat_mem_deallocated) / 1048576.0f,
745         stat_mem_allocated_total - stat_mem_deallocated_total
746     );
747 }
748
749 static void stat_dump_stats_table(stat_size_table_t table, const char *string, uint64_t *size) {
750     size_t i,j;
751
752     if (!table)
753         return;
754
755     for (i = 0, j = 1; i < ST_SIZE; i++) {
756         stat_size_entry_t *entry;
757
758         if (!(entry = table[i]))
759             continue;
760
761         con_out(string, (unsigned)j, (unsigned)entry->key, (unsigned)entry->value);
762         j++;
763
764         if (size)
765             *size += entry->key * entry->value;
766     }
767 }
768
769 void stat_info() {
770     if (OPTS_OPTION_BOOL(OPTION_MEMCHK) ||
771         OPTS_OPTION_BOOL(OPTION_STATISTICS)) {
772         uint64_t mem = 0;
773
774         con_out("Memory Statistics:\n\
775     Total vectors allocated:       %llu\n\
776     Total string duplicates:       %llu\n\
777     Total string duplicate memory: %f (MB)\n\
778     Total hashtables allocated:    %llu\n\
779     Total unique vector sizes:     %llu\n",
780             stat_used_vectors,
781             stat_used_strdups,
782             (float)(stat_mem_strdups) / 1048576.0f,
783             stat_used_hashtables,
784             stat_type_vectors
785         );
786
787         stat_dump_stats_table (
788             stat_size_vectors,
789             "        %2u| # of %5u byte vectors: %u\n",
790             &mem
791         );
792
793         con_out (
794             "    Total unique hashtable sizes: %llu\n",
795             stat_type_hashtables
796         );
797
798         stat_dump_stats_table (
799             stat_size_hashtables,
800             "        %2u| # of %5u element hashtables: %u\n",
801             NULL
802         );
803
804         con_out (
805             "    Total vector memory:          %f (MB)\n\n",
806             (float)(mem) / 1048576.0f
807         );
808     }
809
810     if (stat_size_vectors)
811         stat_size_del(stat_size_vectors);
812     if (stat_size_hashtables)
813         stat_size_del(stat_size_hashtables);
814
815     if (OPTS_OPTION_BOOL(OPTION_DEBUG) ||
816         OPTS_OPTION_BOOL(OPTION_MEMCHK))
817         stat_dump_mem_info();
818
819     if (OPTS_OPTION_BOOL(OPTION_DEBUG))
820         stat_dump_mem_leaks();
821 }
822 #undef ST_SIZE