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, NULL))) {
 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 = 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 %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