stat.c

   1 /*
   2  * Copyright (C) 2012, 2013, 2014
   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 typedef struct stat_mem_block_s stat_mem_block_t;
  31
  32 #define IDENT_SIZE 4
  33 #define IDENT_VEC  "vec"
  34 #define IDENT_MEM  "mem"
  35 #define IDENT_VEC_TOP (sizeof(vector_t) + IDENT_SIZE)
  36 #define IDENT_MEM_TOP (sizeof(stat_mem_block_t) + IDENT_SIZE)
  37
  38 /*
  39  * For the valgrind integration of our allocator. This allows us to have
  40  * more `accurate` valgrind output for our allocator, and also secures the
  41  * possible underflows (where one could obtain access to the redzone that
  42  * represents info about that allocation).
  43  */
  44 #ifndef NVALGRIND
  45 #   include <valgrind/valgrind.h>
  46 #   include <valgrind/memcheck.h>
  47 #else
  48 #   define VALGRIND_MALLOCLIKE_BLOCK(PTR, ALLOC_SIZE, REDZONE_SIZE, ZEROED)
  49 #   define VALGRIND_FREELIKE_BLOCK(PTR, REDZONE_SIZE)
  50 #   define VALGRIND_MAKE_MEM_DEFINED(PTR, REDZONE_SIZE)
  51 #   define VALGRIND_MAKE_MEM_NOACCESS(PTR, REDZONE_SIZE)
  52 #endif
  53
  54 /*
  55  * GMQCC performs tons of allocations, constructions, and crazyness
  56  * all around. When trying to optimizes systems, or just get fancy
  57  * statistics out of the compiler, it's often printf mess. This file
  58  * implements the statistics system of the compiler. I.E the allocator
  59  * we use to track allocations, and other systems of interest.
  60  */
  61 #define ST_SIZE 1024
  62
  63 struct stat_mem_block_s {
  64     const char              *file;
  65     size_t                   line;
  66     size_t                   size;
  67     const char              *expr;
  68     struct stat_mem_block_s *next;
  69     struct stat_mem_block_s *prev;
  70 };
  71
  72 typedef struct {
  73     size_t key;
  74     size_t value;
  75 } stat_size_entry_t, **stat_size_table_t;
  76
  77 static uint64_t          stat_mem_allocated         = 0;
  78 static uint64_t          stat_mem_deallocated       = 0;
  79 static uint64_t          stat_mem_allocated_total   = 0;
  80 static uint64_t          stat_mem_deallocated_total = 0;
  81 static uint64_t          stat_mem_high              = 0;
  82 static uint64_t          stat_mem_peak              = 0;
  83 static uint64_t          stat_mem_strdups           = 0;
  84 static uint64_t          stat_used_strdups          = 0;
  85 static uint64_t          stat_used_vectors          = 0;
  86 static uint64_t          stat_used_hashtables       = 0;
  87 static uint64_t          stat_type_vectors          = 0;
  88 static uint64_t          stat_type_hashtables       = 0;
  89 static stat_size_table_t stat_size_vectors          = NULL;
  90 static stat_size_table_t stat_size_hashtables       = NULL;
  91 static stat_mem_block_t *stat_mem_block_root        = NULL;
  92
  93 /*
  94  * A tiny size_t key-value hashtbale for tracking vector and hashtable
  95  * sizes. We can use it for other things too, if we need to. This is
  96  * very TIGHT, and efficent in terms of space though.
  97  */
  98 static stat_size_table_t stat_size_new(void) {
  99     return (stat_size_table_t)memset(
 100         mem_a(sizeof(stat_size_entry_t*) * ST_SIZE),
 101         0, ST_SIZE * sizeof(stat_size_entry_t*)
 102     );
 103 }
 104
 105 static void stat_size_del(stat_size_table_t table) {
 106     size_t i = 0;
 107     for (; i < ST_SIZE; i++) if(table[i]) mem_d(table[i]);
 108     mem_d(table);
 109 }
 110
 111 static stat_size_entry_t *stat_size_get(stat_size_table_t table, size_t key) {
 112     size_t hash = (key % ST_SIZE);
 113     while (table[hash] && table[hash]->key != key)
 114         hash = (hash + 1) % ST_SIZE;
 115     return table[hash];
 116 }
 117 static void stat_size_put(stat_size_table_t table, size_t key, size_t value) {
 118     size_t hash = (key % ST_SIZE);
 119     while (table[hash] && table[hash]->key != key)
 120         hash = (hash + 1) % ST_SIZE;
 121     table[hash]        = (stat_size_entry_t*)mem_a(sizeof(stat_size_entry_t));
 122     table[hash]->key   = key;
 123     table[hash]->value = value;
 124 }
 125
 126 /*
 127  * A basic header of information wrapper allocator. Simply stores
 128  * information as a header, returns the memory + 1 past it, can be
 129  * retrieved again with - 1. Where type is stat_mem_block_t*.
 130  */
 131 void *stat_mem_allocate(size_t size, size_t line, const char *file, const char *expr) {
 132     stat_mem_block_t *info = (stat_mem_block_t*)malloc(size + IDENT_MEM_TOP);
 133     void             *data = (void *)((char*)info + IDENT_MEM_TOP);
 134
 135     if(GMQCC_UNLIKELY(!info))
 136         return NULL;
 137
 138     info->line = line;
 139     info->size = size;
 140     info->file = file;
 141     info->expr = expr;
 142     info->prev = NULL;
 143     info->next = stat_mem_block_root;
 144
 145     /* Write identifier */
 146     memcpy(info + 1, IDENT_MEM, IDENT_SIZE);
 147
 148     /* likely since it only happens once */
 149     if (GMQCC_LIKELY(stat_mem_block_root != NULL)) {
 150         VALGRIND_MAKE_MEM_DEFINED(stat_mem_block_root, IDENT_MEM_TOP);
 151         stat_mem_block_root->prev = info;
 152         VALGRIND_MAKE_MEM_NOACCESS(stat_mem_block_root, IDENT_MEM_TOP);
 153     }
 154
 155     stat_mem_block_root       = info;
 156     stat_mem_allocated       += size;
 157     stat_mem_high            += size;
 158     stat_mem_allocated_total ++;
 159
 160     if (stat_mem_high > stat_mem_peak)
 161         stat_mem_peak = stat_mem_high;
 162
 163     VALGRIND_MALLOCLIKE_BLOCK(data, size, IDENT_MEM_TOP, 0);
 164     return data;
 165 }
 166
 167 void stat_mem_deallocate(void *ptr, size_t line, const char *file) {
 168     stat_mem_block_t *info  = NULL;
 169     char             *ident = (char *)ptr - IDENT_SIZE;
 170
 171     if (GMQCC_UNLIKELY(!ptr))
 172         return;
 173
 174     /* Validate usage */
 175     VALGRIND_MAKE_MEM_DEFINED(ident, IDENT_SIZE);
 176     if (!strcmp(ident, IDENT_VEC)) {
 177         vector_t         *vec   = (vector_t*)((char *)ptr - IDENT_VEC_TOP);
 178         stat_mem_block_t *block = (stat_mem_block_t*)((char *)vec - IDENT_MEM_TOP);
 179
 180         VALGRIND_MAKE_MEM_DEFINED(block, sizeof(stat_mem_block_t));
 181         con_err("internal warning: invalid use of mem_d:\n");
 182         con_err("internal warning:    vector (used elements: %u, allocated elements: %u)\n",
 183             (unsigned)vec->used,
 184             (unsigned)vec->allocated
 185         );
 186         con_err("internal warning:    vector was last (re)allocated with (size: %u (bytes), at location: %s:%u)\n",
 187             (unsigned)block->size,
 188             block->file,
 189             (unsigned)block->line
 190         );
 191         con_err("internal warning:    released with wrong routine at %s:%u\n", file, (unsigned)line);
 192         con_err("internal warning:    forwarding to vec_free, please fix it\n");
 193         VALGRIND_MAKE_MEM_NOACCESS(block, sizeof(stat_mem_block_t));
 194         VALGRIND_MAKE_MEM_NOACCESS(ident, IDENT_SIZE);
 195         vec_free(ptr);
 196         return;
 197     }
 198     VALGRIND_MAKE_MEM_NOACCESS(ident, IDENT_SIZE);
 199     info = (stat_mem_block_t*)((char *)ptr - IDENT_MEM_TOP);
 200
 201     /*
 202      * we need access to the redzone that represents the info block
 203      * so lets do that.
 204      */
 205     VALGRIND_MAKE_MEM_DEFINED(info, IDENT_MEM_TOP);
 206
 207     stat_mem_deallocated       += info->size;
 208     stat_mem_high              -= info->size;
 209     stat_mem_deallocated_total ++;
 210
 211     if (info->prev) {
 212         /* just need access for a short period */
 213         VALGRIND_MAKE_MEM_DEFINED(info->prev, IDENT_MEM_TOP);
 214         info->prev->next = info->next;
 215         /* don't need access anymore */
 216         VALGRIND_MAKE_MEM_NOACCESS(info->prev, IDENT_MEM_TOP);
 217     }
 218     if (info->next) {
 219         /* just need access for a short period */
 220         VALGRIND_MAKE_MEM_DEFINED(info->next, IDENT_MEM_TOP);
 221         info->next->prev = info->prev;
 222         /* don't need access anymore */
 223         VALGRIND_MAKE_MEM_NOACCESS(info->next, IDENT_MEM_TOP);
 224     }
 225
 226     /* move ahead */
 227     if (info == stat_mem_block_root)
 228         stat_mem_block_root = info->next;
 229
 230     free(info);
 231     VALGRIND_MAKE_MEM_NOACCESS(info, IDENT_MEM_TOP);
 232     VALGRIND_FREELIKE_BLOCK(ptr, IDENT_MEM_TOP);
 233 }
 234
 235 void *stat_mem_reallocate(void *ptr, size_t size, size_t line, const char *file, const char *expr) {
 236     stat_mem_block_t *oldinfo = NULL;
 237     stat_mem_block_t *newinfo;
 238
 239     if (GMQCC_UNLIKELY(!ptr))
 240         return stat_mem_allocate(size, line, file, expr);
 241
 242     /* stay consistent with glibc */
 243     if (GMQCC_UNLIKELY(!size)) {
 244         stat_mem_deallocate(ptr, line, file);
 245         return NULL;
 246     }
 247
 248     oldinfo = (stat_mem_block_t*)((char *)ptr - IDENT_MEM_TOP);
 249     newinfo = (stat_mem_block_t*)malloc(size + IDENT_MEM_TOP);
 250
 251     if (GMQCC_UNLIKELY(!newinfo)) {
 252         stat_mem_deallocate(ptr, line, file);
 253         return NULL;
 254     }
 255
 256     VALGRIND_MALLOCLIKE_BLOCK((char *)newinfo + IDENT_MEM_TOP, size, IDENT_MEM_TOP, 0);
 257
 258     /* we need access to the old info redzone */
 259     VALGRIND_MAKE_MEM_DEFINED(oldinfo, IDENT_MEM_TOP);
 260
 261     /* We need access to the new info redzone */
 262     VALGRIND_MAKE_MEM_DEFINED(newinfo, IDENT_MEM_TOP);
 263     memcpy((char *)(newinfo + 1), IDENT_MEM, IDENT_SIZE);
 264     memcpy((char *)newinfo + IDENT_MEM_TOP, (char *)oldinfo + IDENT_MEM_TOP, oldinfo->size);
 265     VALGRIND_MAKE_MEM_NOACCESS(newinfo, IDENT_MEM_TOP);
 266
 267     if (oldinfo->prev) {
 268         /* just need access for a short period */
 269         VALGRIND_MAKE_MEM_DEFINED(oldinfo->prev, IDENT_MEM_TOP);
 270         oldinfo->prev->next = oldinfo->next;
 271         /* don't need access anymore */
 272         VALGRIND_MAKE_MEM_NOACCESS(oldinfo->prev, IDENT_MEM_TOP);
 273     }
 274
 275     if (oldinfo->next) {
 276         /* just need access for a short period */
 277         VALGRIND_MAKE_MEM_DEFINED(oldinfo->next, IDENT_MEM_TOP);
 278         oldinfo->next->prev = oldinfo->prev;
 279         /* don't need access anymore */
 280         VALGRIND_MAKE_MEM_NOACCESS(oldinfo->next, IDENT_MEM_TOP);
 281     }
 282
 283     /* move ahead */
 284     if (oldinfo == stat_mem_block_root)
 285         stat_mem_block_root = oldinfo->next;
 286
 287     /* we need access to the redzone for the newinfo block */
 288     VALGRIND_MAKE_MEM_DEFINED(newinfo, IDENT_MEM_TOP);
 289
 290     newinfo->line = line;
 291     newinfo->size = size;
 292     newinfo->file = file;
 293     newinfo->expr = expr;
 294     newinfo->prev = NULL;
 295     newinfo->next = stat_mem_block_root;
 296
 297     /*
 298      * likely since the only time there is no root is when it's
 299      * being initialized first.
 300      */
 301     if (GMQCC_LIKELY(stat_mem_block_root != NULL)) {
 302         /* we need access to the root */
 303         VALGRIND_MAKE_MEM_DEFINED(stat_mem_block_root, IDENT_MEM_TOP);
 304         stat_mem_block_root->prev = newinfo;
 305         /* kill access */
 306         VALGRIND_MAKE_MEM_NOACCESS(stat_mem_block_root, IDENT_MEM_TOP);
 307     }
 308
 309     stat_mem_block_root = newinfo;
 310     stat_mem_allocated -= oldinfo->size;
 311     stat_mem_high      -= oldinfo->size;
 312     stat_mem_allocated += newinfo->size;
 313     stat_mem_high      += newinfo->size;
 314
 315     /*
 316      * we're finished with the redzones, lets kill the access
 317      * to them.
 318      */
 319     VALGRIND_MAKE_MEM_NOACCESS(newinfo, IDENT_MEM_TOP);
 320     VALGRIND_MAKE_MEM_NOACCESS(oldinfo, IDENT_MEM_TOP);
 321
 322     if (stat_mem_high > stat_mem_peak)
 323         stat_mem_peak = stat_mem_high;
 324
 325     free(oldinfo);
 326     VALGRIND_FREELIKE_BLOCK(ptr, IDENT_MEM_TOP);
 327     return (char *)newinfo + IDENT_MEM_TOP;
 328 }
 329
 330 /*
 331  * strdup does it's own malloc, we need to track malloc. We don't want
 332  * to overwrite malloc though, infact, we can't really hook it at all
 333  * without library specific assumptions. So we re implement strdup.
 334  */
 335 char *stat_mem_strdup(const char *src, size_t line, const char *file, bool empty) {
 336     size_t len = 0;
 337     char  *ptr = NULL;
 338
 339     if (!src)
 340         return NULL;
 341
 342     len = strlen(src);
 343     if (((!empty) ? len : true) && (ptr = (char*)stat_mem_allocate(len + 1, line, file, "strdup"))) {
 344         memcpy(ptr, src, len);
 345         ptr[len] = '\0';
 346     }
 347
 348     stat_used_strdups ++;
 349     stat_mem_strdups  += len;
 350     return ptr;
 351 }
 352
 353 /*
 354  * The reallocate function for resizing vectors.
 355  */
 356 void _util_vec_grow(void **a, size_t i, size_t s) {
 357     vector_t          *d = (vector_t*)((char *)*a - IDENT_VEC_TOP);
 358     size_t             m = 0;
 359     stat_size_entry_t *e = NULL;
 360     void              *p = NULL;
 361
 362     if (*a) {
 363         m = 2 * d->allocated + i;
 364         p = mem_r(d, s * m + IDENT_VEC_TOP);
 365     } else {
 366         m = i + 1;
 367         p = mem_a(s * m + IDENT_VEC_TOP);
 368         ((vector_t*)p)->used = 0;
 369         stat_used_vectors++;
 370     }
 371
 372     if (!stat_size_vectors)
 373         stat_size_vectors = stat_size_new();
 374
 375     if ((e = stat_size_get(stat_size_vectors, s))) {
 376         e->value ++;
 377     } else {
 378         stat_size_put(stat_size_vectors, s, 1); /* start off with 1 */
 379         stat_type_vectors++;
 380     }
 381
 382     d = (vector_t*)p;
 383     d->allocated = m;
 384     memcpy(d + 1, IDENT_VEC, IDENT_SIZE);
 385     *a = (void *)((char *)d + IDENT_VEC_TOP);
 386 }
 387
 388 void _util_vec_delete(void *data, size_t line, const char *file) {
 389     char *ident = (char *)data - IDENT_SIZE;
 390     if (!strcmp(ident, IDENT_MEM)) {
 391         stat_mem_block_t *block = (stat_mem_block_t*)((char *)data - IDENT_MEM_TOP);
 392         VALGRIND_MAKE_MEM_DEFINED(block, sizeof(stat_mem_block_t));
 393         con_err("internal warning: invalid use of vec_free:\n");
 394         con_err("internal warning:    memory block last allocated (size: %u (bytes), at %s:%u)\n",
 395             (unsigned)block->size,
 396             block->file,
 397             (unsigned)block->line);
 398         con_err("internal warning:    released with with wrong routine at %s:%u\n", file, (unsigned)line);
 399         con_err("internal warning:    forwarding to mem_d, please fix it\n");
 400         VALGRIND_MAKE_MEM_NOACCESS(block, sizeof(stat_mem_block_t));
 401         mem_d(data);
 402         return;
 403     }
 404     /* forward */
 405     stat_mem_deallocate((void*)(ident - sizeof(vector_t)), line, file);
 406 }
 407
 408 /*
 409  * Hash table for generic data, based on dynamic memory allocations
 410  * all around.  This is the internal interface, please look for
 411  * EXPOSED INTERFACE comment below
 412  */
 413 typedef struct hash_node_t {
 414     char               *key;   /* the key for this node in table */
 415     void               *value; /* pointer to the data as void*   */
 416     struct hash_node_t *next;  /* next node (linked list)        */
 417 } hash_node_t;
 418
 419
 420 size_t hash(const char *key);
 421 size_t util_hthash(hash_table_t *ht, const char *key) {
 422     return hash(key) % ht->size;
 423 }
 424
 425 static hash_node_t *_util_htnewpair(const char *key, void *value) {
 426     hash_node_t *node;
 427     if (!(node = (hash_node_t*)mem_a(sizeof(hash_node_t))))
 428         return NULL;
 429
 430     if (!(node->key = util_strdupe(key))) {
 431         mem_d(node);
 432         return NULL;
 433     }
 434
 435     node->value = value;
 436     node->next  = NULL;
 437
 438     return node;
 439 }
 440
 441 /*
 442  * EXPOSED INTERFACE for the hashtable implementation
 443  * util_htnew(size)                             -- to make a new hashtable
 444  * util_htset(table, key, value, sizeof(value)) -- to set something in the table
 445  * util_htget(table, key)                       -- to get something from the table
 446  * util_htdel(table)                            -- to delete the table
 447  */
 448 hash_table_t *util_htnew(size_t size) {
 449     hash_table_t      *hashtable = NULL;
 450     stat_size_entry_t *find      = NULL;
 451
 452     if (size < 1)
 453         return NULL;
 454
 455     if (!stat_size_hashtables)
 456         stat_size_hashtables = stat_size_new();
 457
 458     if (!(hashtable = (hash_table_t*)mem_a(sizeof(hash_table_t))))
 459         return NULL;
 460
 461     if (!(hashtable->table = (hash_node_t**)mem_a(sizeof(hash_node_t*) * size))) {
 462         mem_d(hashtable);
 463         return NULL;
 464     }
 465
 466     if ((find = stat_size_get(stat_size_hashtables, size)))
 467         find->value++;
 468     else {
 469         stat_type_hashtables++;
 470         stat_size_put(stat_size_hashtables, size, 1);
 471     }
 472
 473     hashtable->size = size;
 474     memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
 475
 476     stat_used_hashtables++;
 477     return hashtable;
 478 }
 479
 480 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
 481     hash_node_t *newnode = NULL;
 482     hash_node_t *next    = NULL;
 483     hash_node_t *last    = NULL;
 484
 485     next = ht->table[bin];
 486
 487     while (next && next->key && strcmp(key, next->key) > 0)
 488         last = next, next = next->next;
 489
 490     /* already in table, do a replace */
 491     if (next && next->key && strcmp(key, next->key) == 0) {
 492         next->value = value;
 493     } else {
 494         /* not found, grow a pair man :P */
 495         newnode = _util_htnewpair(key, value);
 496         if (next == ht->table[bin]) {
 497             newnode->next  = next;
 498             ht->table[bin] = newnode;
 499         } else if (!next) {
 500             last->next = newnode;
 501         } else {
 502             newnode->next = next;
 503             last->next = newnode;
 504         }
 505     }
 506 }
 507
 508 void util_htset(hash_table_t *ht, const char *key, void *value) {
 509     util_htseth(ht, key, util_hthash(ht, key), value);
 510 }
 511
 512 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
 513     hash_node_t *pair = ht->table[bin];
 514
 515     while (pair && pair->key && strcmp(key, pair->key) > 0)
 516         pair = pair->next;
 517
 518     if (!pair || !pair->key || strcmp(key, pair->key) != 0)
 519         return NULL;
 520
 521     return pair->value;
 522 }
 523
 524 void *util_htget(hash_table_t *ht, const char *key) {
 525     return util_htgeth(ht, key, util_hthash(ht, key));
 526 }
 527
 528 void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin);
 529 void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin) {
 530     hash_node_t *pair;
 531     size_t len, keylen;
 532     int cmp;
 533
 534     keylen = strlen(key);
 535
 536     pair = ht->table[bin];
 537     while (pair && pair->key) {
 538         len = strlen(pair->key);
 539         if (len < keylen) {
 540             pair = pair->next;
 541             continue;
 542         }
 543         if (keylen == len) {
 544             cmp = strcmp(key, pair->key);
 545             if (cmp == 0)
 546                 return pair->value;
 547             if (cmp < 0)
 548                 return NULL;
 549             pair = pair->next;
 550             continue;
 551         }
 552         cmp = strcmp(key, pair->key + len - keylen);
 553         if (cmp == 0) {
 554             uintptr_t up = (uintptr_t)pair->value;
 555             up += len - keylen;
 556             return (void*)up;
 557         }
 558         pair = pair->next;
 559     }
 560     return NULL;
 561 }
 562
 563 /*
 564  * Free all allocated data in a hashtable, this is quite the amount
 565  * of work.
 566  */
 567 void util_htrem(hash_table_t *ht, void (*callback)(void *data)) {
 568     size_t i = 0;
 569
 570     for (; i < ht->size; ++i) {
 571         hash_node_t *n = ht->table[i];
 572         hash_node_t *p;
 573
 574         /* free in list */
 575         while (n) {
 576             if (n->key)
 577                 mem_d(n->key);
 578             if (callback)
 579                 callback(n->value);
 580             p = n;
 581             n = p->next;
 582             mem_d(p);
 583         }
 584
 585     }
 586     /* free table */
 587     mem_d(ht->table);
 588     mem_d(ht);
 589 }
 590
 591 void util_htrmh(hash_table_t *ht, const char *key, size_t bin, void (*cb)(void*)) {
 592     hash_node_t **pair = &ht->table[bin];
 593     hash_node_t *tmp;
 594
 595     while (*pair && (*pair)->key && strcmp(key, (*pair)->key) > 0)
 596         pair = &(*pair)->next;
 597
 598     tmp = *pair;
 599     if (!tmp || !tmp->key || strcmp(key, tmp->key) != 0)
 600         return;
 601
 602     if (cb)
 603         (*cb)(tmp->value);
 604
 605     *pair = tmp->next;
 606     mem_d(tmp->key);
 607     mem_d(tmp);
 608 }
 609
 610 void util_htrm(hash_table_t *ht, const char *key, void (*cb)(void*)) {
 611     util_htrmh(ht, key, util_hthash(ht, key), cb);
 612 }
 613
 614 void util_htdel(hash_table_t *ht) {
 615     util_htrem(ht, NULL);
 616 }
 617
 618 /*
 619  * The following functions below implement printing / dumping of statistical
 620  * information.
 621  */
 622 static void stat_dump_mem_contents(stat_mem_block_t *block, uint16_t cols) {
 623     unsigned char *buffer = (unsigned char *)mem_a(cols);
 624     unsigned char *memory = (unsigned char *)(block + 1);
 625     size_t         i;
 626
 627     for (i = 0; i < block->size; i++) {
 628         if (!(i % 16)) {
 629             if (i != 0)
 630                 con_out(" %s\n", buffer);
 631             con_out(" 0x%08X: ", i);
 632         }
 633
 634         con_out(" %02X", memory[i]);
 635
 636         buffer[i % cols] = ((memory[i] < 0x20) || (memory[i] > 0x7E))
 637                             ? '.'
 638                             : memory[i];
 639
 640         buffer[(i % cols) + 1] = '\0';
 641     }
 642
 643     while ((i % cols) != 0) {
 644         con_out("   ");
 645         i++;
 646     }
 647
 648     con_out(" %s\n", buffer);
 649     mem_d(buffer);
 650 }
 651
 652 static void stat_dump_mem_leaks(void) {
 653     stat_mem_block_t *info;
 654     /* we need access to the root for this */
 655     VALGRIND_MAKE_MEM_DEFINED(stat_mem_block_root, sizeof(stat_mem_block_t));
 656     for (info = stat_mem_block_root; info; info = info->next) {
 657         /* we need access to the block */
 658         VALGRIND_MAKE_MEM_DEFINED(info, sizeof(stat_mem_block_t));
 659         con_out("lost: %u (bytes) at %s:%u from expression `%s`\n",
 660             info->size,
 661             info->file,
 662             info->line,
 663             info->expr
 664         );
 665
 666         stat_dump_mem_contents(info, OPTS_OPTION_U16(OPTION_MEMDUMPCOLS));
 667
 668         /*
 669          * we're finished with the access, the redzone should be marked
 670          * inaccesible so that invalid read/writes that could 'step-into'
 671          * those redzones will show up as invalid read/writes in valgrind.
 672          */
 673         VALGRIND_MAKE_MEM_NOACCESS(info, sizeof(stat_mem_block_t));
 674     }
 675     VALGRIND_MAKE_MEM_NOACCESS(stat_mem_block_root, sizeof(stat_mem_block_t));
 676 }
 677
 678 static void stat_dump_mem_info(void) {
 679     con_out("Memory Information:\n\
 680     Total allocations:   %llu\n\
 681     Total deallocations: %llu\n\
 682     Total allocated:     %f (MB)\n\
 683     Total deallocated:   %f (MB)\n\
 684     Total peak memory:   %f (MB)\n\
 685     Total leaked memory: %f (MB) in %llu allocations\n",
 686         stat_mem_allocated_total,
 687         stat_mem_deallocated_total,
 688         (float)(stat_mem_allocated)                        / 1048576.0f,
 689         (float)(stat_mem_deallocated)                      / 1048576.0f,
 690         (float)(stat_mem_peak)                             / 1048576.0f,
 691         (float)(stat_mem_allocated - stat_mem_deallocated) / 1048576.0f,
 692         stat_mem_allocated_total - stat_mem_deallocated_total
 693     );
 694 }
 695
 696 static void stat_dump_stats_table(stat_size_table_t table, const char *string, uint64_t *size) {
 697     size_t i,j;
 698
 699     if (!table)
 700         return;
 701
 702     for (i = 0, j = 1; i < ST_SIZE; i++) {
 703         stat_size_entry_t *entry;
 704
 705         if (!(entry = table[i]))
 706             continue;
 707
 708         con_out(string, (unsigned)j, (unsigned)entry->key, (unsigned)entry->value);
 709         j++;
 710
 711         if (size)
 712             *size += entry->key * entry->value;
 713     }
 714 }
 715
 716 void stat_info() {
 717     if (OPTS_OPTION_BOOL(OPTION_MEMCHK) ||
 718         OPTS_OPTION_BOOL(OPTION_STATISTICS)) {
 719         uint64_t mem = 0;
 720
 721         con_out("Memory Statistics:\n\
 722     Total vectors allocated:       %llu\n\
 723     Total string duplicates:       %llu\n\
 724     Total string duplicate memory: %f (MB)\n\
 725     Total hashtables allocated:    %llu\n\
 726     Total unique vector sizes:     %llu\n",
 727             stat_used_vectors,
 728             stat_used_strdups,
 729             (float)(stat_mem_strdups) / 1048576.0f,
 730             stat_used_hashtables,
 731             stat_type_vectors
 732         );
 733
 734         stat_dump_stats_table (
 735             stat_size_vectors,
 736             "        %2u| # of %5u byte vectors: %u\n",
 737             &mem
 738         );
 739
 740         con_out (
 741             "    Total unique hashtable sizes: %llu\n",
 742             stat_type_hashtables
 743         );
 744
 745         stat_dump_stats_table (
 746             stat_size_hashtables,
 747             "        %2u| # of %5u element hashtables: %u\n",
 748             NULL
 749         );
 750
 751         con_out (
 752             "    Total vector memory:          %f (MB)\n\n",
 753             (float)(mem) / 1048576.0f
 754         );
 755     }
 756
 757     if (stat_size_vectors)
 758         stat_size_del(stat_size_vectors);
 759     if (stat_size_hashtables)
 760         stat_size_del(stat_size_hashtables);
 761
 762     if (OPTS_OPTION_BOOL(OPTION_DEBUG) ||
 763         OPTS_OPTION_BOOL(OPTION_MEMCHK))
 764         stat_dump_mem_info();
 765
 766     if (OPTS_OPTION_BOOL(OPTION_DEBUG))
 767         stat_dump_mem_leaks();
 768 }
 769 #undef ST_SIZE