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