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