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