stat.c

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