]> git.xonotic.org Git - xonotic/gmqcc.git/blob - stat.c
0192a2fa71171143f41902fad8f0043745a86b36
[xonotic/gmqcc.git] / 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