stat.c

   1 #include <string.h>
   2 #include <stdlib.h>
   3 #include <ctype.h>
   4
   5 #include "gmqcc.h"
   6
   7 /*
   8  * GMQCC performs tons of allocations, constructions, and crazyness
   9  * all around. When trying to optimizes systems, or just get fancy
  10  * statistics out of the compiler, it's often printf mess. This file
  11  * implements the statistics system of the compiler. I.E the allocator
  12  * we use to track allocations, and other systems of interest.
  13  */
  14 #define ST_SIZE 1024
  15
  16 typedef struct stat_mem_block_s {
  17     const char              *file;
  18     size_t                   line;
  19     size_t                   size;
  20     struct stat_mem_block_s *next;
  21     struct stat_mem_block_s *prev;
  22 } stat_mem_block_t;
  23
  24 typedef struct {
  25     size_t key;
  26     size_t value;
  27 } stat_size_entry_t, **stat_size_table_t;
  28
  29 static uint64_t          stat_mem_allocated         = 0;
  30 static uint64_t          stat_mem_deallocated       = 0;
  31 static uint64_t          stat_mem_allocated_total   = 0;
  32 static uint64_t          stat_mem_deallocated_total = 0;
  33 static uint64_t          stat_mem_high              = 0;
  34 static uint64_t          stat_mem_peak              = 0;
  35 static uint64_t          stat_used_strdups          = 0;
  36 static uint64_t          stat_used_vectors          = 0;
  37 static uint64_t          stat_used_hashtables       = 0;
  38 static uint64_t          stat_type_vectors          = 0;
  39 static uint64_t          stat_type_hashtables       = 0;
  40 static stat_size_table_t stat_size_vectors          = NULL;
  41 static stat_size_table_t stat_size_hashtables       = NULL;
  42 static stat_mem_block_t *stat_mem_block_root        = NULL;
  43
  44 /*
  45  * A tiny size_t key-value hashtbale for tracking vector and hashtable
  46  * sizes. We can use it for other things too, if we need to. This is
  47  * very TIGHT, and efficent in terms of space though.
  48  */
  49 static stat_size_table_t stat_size_new() {
  50     return (stat_size_table_t)memset(
  51         mem_a(sizeof(stat_size_entry_t*) * ST_SIZE),
  52         0, ST_SIZE * sizeof(stat_size_entry_t*)
  53     );
  54 }
  55
  56 static void stat_size_del(stat_size_table_t table) {
  57     size_t i = 0;
  58     for (; i < ST_SIZE; i++) if(table[i]) mem_d(table[i]);
  59     mem_d(table);
  60 }
  61
  62 static stat_size_entry_t *stat_size_get(stat_size_table_t table, size_t key) {
  63     size_t hash = (key % ST_SIZE);
  64     while (table[hash] && table[hash]->key != key)
  65         hash = (hash + 1) % ST_SIZE;
  66     return table[hash];
  67 }
  68 static void stat_size_put(stat_size_table_t table, size_t key, size_t value) {
  69     size_t hash = (key % ST_SIZE);
  70     while (table[hash] && table[hash]->key != key)
  71         hash = (hash + 1) % ST_SIZE;
  72     table[hash] = (stat_size_entry_t*)mem_a(sizeof(stat_size_entry_t));
  73     table[hash]->key = key;
  74     table[hash]->value = value;
  75 }
  76
  77 /*
  78  * A basic header of information wrapper allocator. Simply stores
  79  * information as a header, returns the memory + 1 past it, can be
  80  * retrieved again with - 1. Where type is stat_mem_block_t*.
  81  */
  82 void *stat_mem_allocate(size_t size, size_t line, const char *file) {
  83     stat_mem_block_t *info = (stat_mem_block_t*)malloc(sizeof(stat_mem_block_t) + size);
  84     void             *data = (void*)(info + 1);
  85
  86     if(!info)
  87         return NULL;
  88
  89     info->line = line;
  90     info->size = size;
  91     info->file = file;
  92     info->prev = NULL;
  93     info->next = stat_mem_block_root;
  94
  95     if (stat_mem_block_root)
  96         stat_mem_block_root->prev = info;
  97
  98     stat_mem_block_root       = info;
  99     stat_mem_allocated       += size;
 100     stat_mem_high            += size;
 101     stat_mem_allocated_total ++;
 102
 103     if (stat_mem_high > stat_mem_peak)
 104         stat_mem_peak = stat_mem_high;
 105
 106     return data;
 107 }
 108
 109 void stat_mem_deallocate(void *ptr) {
 110     stat_mem_block_t *info = NULL;
 111
 112     if (!ptr)
 113         return;
 114
 115     info = ((stat_mem_block_t*)ptr - 1);
 116
 117     stat_mem_deallocated       += info->size;
 118     stat_mem_high              -= info->size;
 119     stat_mem_deallocated_total ++;
 120
 121     if (info->prev) info->prev->next = info->next;
 122     if (info->next) info->next->prev = info->prev;
 123
 124     /* move ahead */
 125     if (info == stat_mem_block_root)
 126         stat_mem_block_root = info->next;
 127
 128     free(info);
 129 }
 130
 131 void *stat_mem_reallocate(void *ptr, size_t size, size_t line, const char *file) {
 132     stat_mem_block_t *oldinfo = NULL;
 133     stat_mem_block_t *newinfo;
 134
 135     if (!ptr)
 136         return stat_mem_allocate(size, line, file);
 137
 138     /* stay consistent with glic */
 139     if (!size) {
 140         stat_mem_deallocate(ptr);
 141         return NULL;
 142     }
 143
 144     oldinfo = ((stat_mem_block_t*)ptr - 1);
 145     newinfo = ((stat_mem_block_t*)malloc(sizeof(stat_mem_block_t) + size));
 146
 147     if (!newinfo) {
 148         stat_mem_deallocate(ptr);
 149         return NULL;
 150     }
 151
 152     memcpy(newinfo+1, oldinfo+1, oldinfo->size);
 153
 154     if (oldinfo->prev) oldinfo->prev->next = oldinfo->next;
 155     if (oldinfo->next) oldinfo->next->prev = oldinfo->prev;
 156
 157     /* move ahead */
 158     if (oldinfo == stat_mem_block_root)
 159         stat_mem_block_root = oldinfo->next;
 160
 161     newinfo->line = line;
 162     newinfo->size = size;
 163     newinfo->file = file;
 164     newinfo->prev = NULL;
 165     newinfo->next = stat_mem_block_root;
 166
 167     if (stat_mem_block_root)
 168         stat_mem_block_root->prev = newinfo;
 169
 170     stat_mem_block_root = newinfo;
 171     stat_mem_allocated -= oldinfo->size;
 172     stat_mem_high      -= oldinfo->size;
 173     stat_mem_allocated += newinfo->size;
 174     stat_mem_high      += newinfo->size;
 175
 176     if (stat_mem_high > stat_mem_peak)
 177         stat_mem_peak = stat_mem_high;
 178
 179     free(oldinfo);
 180
 181     return newinfo + 1;
 182 }
 183
 184 /*
 185  * strdup does it's own malloc, we need to track malloc. We don't want
 186  * to overwrite malloc though, infact, we can't really hook it at all
 187  * without library specific assumptions. So we re implement strdup.
 188  */
 189 char *stat_mem_strdup(const char *src, size_t line, const char *file, bool empty) {
 190     size_t len = 0;
 191     char  *ptr = NULL;
 192
 193     if (!src)
 194         return NULL;
 195
 196     len = strlen(src);
 197     if (((!empty) ? len : true) && (ptr = (char*)stat_mem_allocate(len + 1, line, file))) {
 198         memcpy(ptr, src, len);
 199         ptr[len] = '\0';
 200     }
 201
 202     stat_used_strdups ++;
 203     return ptr;
 204 }
 205
 206 /*
 207  * The reallocate function for resizing vectors.
 208  */
 209 void _util_vec_grow(void **a, size_t i, size_t s) {
 210     vector_t          *d = vec_meta(*a);
 211     size_t             m = 0;
 212     stat_size_entry_t *e = NULL;
 213     void              *p = NULL;
 214
 215     if (*a) {
 216         m = 2 * d->allocated + i;
 217         p = mem_r(d, s * m + sizeof(vector_t));
 218     } else {
 219         m = i + 1;
 220         p = mem_a(s * m + sizeof(vector_t));
 221         ((vector_t*)p)->used = 0;
 222         stat_used_vectors++;
 223     }
 224
 225     if (!stat_size_vectors)
 226         stat_size_vectors = stat_size_new();
 227
 228     if ((e = stat_size_get(stat_size_vectors, s))) {
 229         e->value ++;
 230     } else {
 231         stat_size_put(stat_size_vectors, s, 1); /* start off with 1 */
 232         stat_type_vectors++;
 233     }
 234
 235     *a = (vector_t*)p + 1;
 236     vec_meta(*a)->allocated = m;
 237 }
 238
 239 /*
 240  * Hash table for generic data, based on dynamic memory allocations
 241  * all around.  This is the internal interface, please look for
 242  * EXPOSED INTERFACE comment below
 243  */
 244 typedef struct hash_node_t {
 245     char               *key;   /* the key for this node in table */
 246     void               *value; /* pointer to the data as void*   */
 247     struct hash_node_t *next;  /* next node (linked list)        */
 248 } hash_node_t;
 249
 250 GMQCC_INLINE size_t util_hthash(hash_table_t *ht, const char *key) {
 251     const uint32_t       mix   = 0x5BD1E995;
 252     const uint32_t       rot   = 24;
 253     size_t               size  = strlen(key);
 254     uint32_t             hash  = 0x1EF0 /* LICRC TAB */  ^ size;
 255     uint32_t             alias = 0;
 256     const unsigned char *data  = (const unsigned char*)key;
 257
 258     while (size >= 4) {
 259         alias  = (data[0] | (data[1] << 8) | (data[2] << 16) | (data[3] << 24));
 260         alias *= mix;
 261         alias ^= alias >> rot;
 262         alias *= mix;
 263
 264         hash  *= mix;
 265         hash  ^= alias;
 266
 267         data += 4;
 268         size -= 4;
 269     }
 270
 271     switch (size) {
 272         case 3: hash ^= data[2] << 16;
 273         case 2: hash ^= data[1] << 8;
 274         case 1: hash ^= data[0];
 275                 hash *= mix;
 276     }
 277
 278     hash ^= hash >> 13;
 279     hash *= mix;
 280     hash ^= hash >> 15;
 281
 282     return (size_t) (hash % ht->size);
 283 }
 284
 285 static hash_node_t *_util_htnewpair(const char *key, void *value) {
 286     hash_node_t *node;
 287     if (!(node = (hash_node_t*)mem_a(sizeof(hash_node_t))))
 288         return NULL;
 289
 290     if (!(node->key = util_strdupe(key))) {
 291         mem_d(node);
 292         return NULL;
 293     }
 294
 295     node->value = value;
 296     node->next  = NULL;
 297
 298     return node;
 299 }
 300
 301 /*
 302  * EXPOSED INTERFACE for the hashtable implementation
 303  * util_htnew(size)                             -- to make a new hashtable
 304  * util_htset(table, key, value, sizeof(value)) -- to set something in the table
 305  * util_htget(table, key)                       -- to get something from the table
 306  * util_htdel(table)                            -- to delete the table
 307  */
 308 hash_table_t *util_htnew(size_t size) {
 309     hash_table_t      *hashtable = NULL;
 310     stat_size_entry_t *find      = NULL;
 311
 312     if (size < 1)
 313         return NULL;
 314
 315     if (!stat_size_hashtables)
 316         stat_size_hashtables = stat_size_new();
 317
 318     if (!(hashtable = (hash_table_t*)mem_a(sizeof(hash_table_t))))
 319         return NULL;
 320
 321     if (!(hashtable->table = (hash_node_t**)mem_a(sizeof(hash_node_t*) * size))) {
 322         mem_d(hashtable);
 323         return NULL;
 324     }
 325
 326     if ((find = stat_size_get(stat_size_hashtables, size)))
 327         find->value++;
 328     else {
 329         stat_type_hashtables++;
 330         stat_size_put(stat_size_hashtables, size, 1);
 331     }
 332
 333     hashtable->size = size;
 334     memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
 335
 336     stat_used_hashtables++;
 337     return hashtable;
 338 }
 339
 340 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
 341     hash_node_t *newnode = NULL;
 342     hash_node_t *next    = NULL;
 343     hash_node_t *last    = NULL;
 344
 345     next = ht->table[bin];
 346
 347     while (next && next->key && strcmp(key, next->key) > 0)
 348         last = next, next = next->next;
 349
 350     /* already in table, do a replace */
 351     if (next && next->key && strcmp(key, next->key) == 0) {
 352         next->value = value;
 353     } else {
 354         /* not found, grow a pair man :P */
 355         newnode = _util_htnewpair(key, value);
 356         if (next == ht->table[bin]) {
 357             newnode->next  = next;
 358             ht->table[bin] = newnode;
 359         } else if (!next) {
 360             last->next = newnode;
 361         } else {
 362             newnode->next = next;
 363             last->next = newnode;
 364         }
 365     }
 366 }
 367
 368 void util_htset(hash_table_t *ht, const char *key, void *value) {
 369     util_htseth(ht, key, util_hthash(ht, key), value);
 370 }
 371
 372 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
 373     hash_node_t *pair = ht->table[bin];
 374
 375     while (pair && pair->key && strcmp(key, pair->key) > 0)
 376         pair = pair->next;
 377
 378     if (!pair || !pair->key || strcmp(key, pair->key) != 0)
 379         return NULL;
 380
 381     return pair->value;
 382 }
 383
 384 void *util_htget(hash_table_t *ht, const char *key) {
 385     return util_htgeth(ht, key, util_hthash(ht, key));
 386 }
 387
 388 void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin) {
 389     hash_node_t *pair;
 390     size_t len, keylen;
 391     int cmp;
 392
 393     keylen = strlen(key);
 394
 395     pair = ht->table[bin];
 396     while (pair && pair->key) {
 397         len = strlen(pair->key);
 398         if (len < keylen) {
 399             pair = pair->next;
 400             continue;
 401         }
 402         if (keylen == len) {
 403             cmp = strcmp(key, pair->key);
 404             if (cmp == 0)
 405                 return pair->value;
 406             if (cmp < 0)
 407                 return NULL;
 408             pair = pair->next;
 409             continue;
 410         }
 411         cmp = strcmp(key, pair->key + len - keylen);
 412         if (cmp == 0) {
 413             uintptr_t up = (uintptr_t)pair->value;
 414             up += len - keylen;
 415             return (void*)up;
 416         }
 417         pair = pair->next;
 418     }
 419     return NULL;
 420 }
 421
 422 /*
 423  * Free all allocated data in a hashtable, this is quite the amount
 424  * of work.
 425  */
 426 void util_htrem(hash_table_t *ht, void (*callback)(void *data)) {
 427     size_t i = 0;
 428     for (; i < ht->size; i++) {
 429         hash_node_t *n = ht->table[i];
 430         hash_node_t *p;
 431
 432         /* free in list */
 433         while (n) {
 434             if (n->key)
 435                 mem_d(n->key);
 436             if (callback)
 437                 callback(n->value);
 438             p = n;
 439             n = n->next;
 440             mem_d(p);
 441         }
 442
 443     }
 444     /* free table */
 445     mem_d(ht->table);
 446     mem_d(ht);
 447 }
 448
 449 void util_htrmh(hash_table_t *ht, const char *key, size_t bin, void (*cb)(void*)) {
 450     hash_node_t **pair = &ht->table[bin];
 451     hash_node_t *tmp;
 452
 453     while (*pair && (*pair)->key && strcmp(key, (*pair)->key) > 0)
 454         pair = &(*pair)->next;
 455
 456     tmp = *pair;
 457     if (!tmp || !tmp->key || strcmp(key, tmp->key) != 0)
 458         return;
 459
 460     if (cb)
 461         (*cb)(tmp->value);
 462
 463     *pair = tmp->next;
 464     mem_d(tmp->key);
 465     mem_d(tmp);
 466 }
 467
 468 void util_htrm(hash_table_t *ht, const char *key, void (*cb)(void*)) {
 469     util_htrmh(ht, key, util_hthash(ht, key), cb);
 470 }
 471
 472 void util_htdel(hash_table_t *ht) {
 473     util_htrem(ht, NULL);
 474 }
 475
 476 /*
 477  * The following functions below implement printing / dumping of statistical
 478  * information.
 479  */
 480 static void stat_dump_mem_contents(stat_mem_block_t *memory, uint16_t cols) {
 481     uint32_t i, j;
 482     for (i = 0; i < memory->size + ((memory->size % cols) ? (cols - memory->size % cols) : 0); i++) {
 483         if (i % cols == 0)    con_out(" 0x%06X: ", i);
 484         if (i < memory->size) con_out("%02X " , 0xFF & ((unsigned char*)(memory + 1))[i]);
 485         else                  con_out(" ");
 486
 487         if ((uint16_t)(i % cols) == (cols - 1)) {
 488             for (j = i - (cols - 1); j <= i; j++) {
 489                 con_out("%c",
 490                     (j >= memory->size)
 491                         ? ' '
 492                         : (isprint(((unsigned char*)(memory + 1))[j]))
 493                             ? 0xFF & ((unsigned char*)(memory + 1)) [j]
 494                             : '.'
 495                 );
 496             }
 497             con_out("\n");
 498         }
 499     }
 500 }
 501
 502 static void stat_dump_mem_leaks() {
 503     stat_mem_block_t *info;
 504     for (info = stat_mem_block_root; info; info = info->next) {
 505         con_out("lost: %u (bytes) at %s:%u\n",
 506             info->size,
 507             info->file,
 508             info->line
 509         );
 510
 511         stat_dump_mem_contents(info, OPTS_OPTION_U16(OPTION_MEMDUMPCOLS));
 512     }
 513 }
 514
 515 static void stat_dump_mem_info() {
 516     con_out("Memory information:\n\
 517     Total allocations:   %llu\n\
 518     Total deallocations: %llu\n\
 519     Total allocated:     %f (MB)\n\
 520     Total deallocated:   %f (MB)\n\
 521     Total peak memory:   %f (MB)\n\
 522     Total leaked memory: %f (MB) in %llu allocations\n",
 523         stat_mem_allocated_total,
 524         stat_mem_deallocated_total,
 525         (float)(stat_mem_allocated)                        / 1048576.0f,
 526         (float)(stat_mem_deallocated)                      / 1048576.0f,
 527         (float)(stat_mem_peak)                             / 1048576.0f,
 528         (float)(stat_mem_allocated - stat_mem_deallocated) / 1048576.0f,
 529         stat_mem_allocated_total - stat_mem_deallocated_total
 530     );
 531 }
 532
 533 static void stat_dump_stats_table(stat_size_table_t table, const char *string, uint64_t *size) {
 534     size_t i,j;
 535
 536     if (!table)
 537         return;
 538
 539     for (i = 0, j = 0; i < ST_SIZE; i++) {
 540         stat_size_entry_t *entry;
 541
 542         if (!(entry = table[i]))
 543             continue;
 544
 545         con_out(string, (unsigned)j, (unsigned)entry->key, (unsigned)entry->value);
 546         j++;
 547
 548         if (size)
 549             *size += entry->key * entry->value;
 550     }
 551 }
 552
 553 void stat_info() {
 554     if (OPTS_OPTION_BOOL(OPTION_DEBUG))
 555         stat_dump_mem_leaks();
 556
 557     if (OPTS_OPTION_BOOL(OPTION_DEBUG) ||
 558         OPTS_OPTION_BOOL(OPTION_MEMCHK))
 559         stat_dump_mem_info();
 560
 561     if (OPTS_OPTION_BOOL(OPTION_MEMCHK) ||
 562         OPTS_OPTION_BOOL(OPTION_STATISTICS)) {
 563         uint64_t mem = 0;
 564
 565         con_out("\nAdditional Statistics:\n\
 566     Total vectors allocated:    %llu\n\
 567     Total string duplicates:    %llu\n\
 568     Total hashtables allocated: %llu\n\
 569     Total unique vector sizes:  %llu\n",
 570             stat_used_vectors,
 571             stat_used_strdups,
 572             stat_used_hashtables,
 573             stat_type_vectors
 574         );
 575
 576         stat_dump_stats_table (
 577             stat_size_vectors,
 578             "        %2u| # of %4u byte vectors: %u\n",
 579             &mem
 580         );
 581
 582         con_out (
 583             "    Total unique hashtable sizes: %llu\n",
 584             stat_type_hashtables
 585         );
 586
 587         stat_dump_stats_table (
 588             stat_size_hashtables,
 589             "        %2u| # of %4u element hashtables: %u\n",
 590             NULL
 591         );
 592
 593         con_out (
 594             "    Total vector memory:          %f (MB)\n",
 595             (float)(mem) / 1048576.0f
 596         );
 597     }
 598
 599     if (stat_size_vectors)
 600         stat_size_del(stat_size_vectors);
 601     if (stat_size_hashtables)
 602         stat_size_del(stat_size_hashtables);
 603 }
 604 #undef ST_SIZE