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