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