2 * Copyright (C) 2012, 2013, 2014
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:
13 * The above copyright notice and this permission notice shall be included in all
14 * copies or substantial portions of the Software.
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
30 typedef struct stat_mem_block_s stat_mem_block_t;
33 #define IDENT_VEC "vec"
34 #define IDENT_MEM "mem"
35 #define IDENT_VEC_TOP (sizeof(vector_t) + IDENT_SIZE)
36 #define IDENT_MEM_TOP (sizeof(stat_mem_block_t) + IDENT_SIZE)
39 * For the valgrind integration of our allocator. This allows us to have
40 * more `accurate` valgrind output for our allocator, and also secures the
41 * possible underflows (where one could obtain access to the redzone that
42 * represents info about that allocation).
45 # include <valgrind/valgrind.h>
46 # include <valgrind/memcheck.h>
48 # define VALGRIND_MALLOCLIKE_BLOCK(PTR, ALLOC_SIZE, REDZONE_SIZE, ZEROED)
49 # define VALGRIND_FREELIKE_BLOCK(PTR, REDZONE_SIZE)
50 # define VALGRIND_MAKE_MEM_DEFINED(PTR, REDZONE_SIZE)
51 # define VALGRIND_MAKE_MEM_NOACCESS(PTR, REDZONE_SIZE)
55 * GMQCC performs tons of allocations, constructions, and crazyness
56 * all around. When trying to optimizes systems, or just get fancy
57 * statistics out of the compiler, it's often printf mess. This file
58 * implements the statistics system of the compiler. I.E the allocator
59 * we use to track allocations, and other systems of interest.
63 struct stat_mem_block_s {
68 struct stat_mem_block_s *next;
69 struct stat_mem_block_s *prev;
75 } stat_size_entry_t, **stat_size_table_t;
77 static uint64_t stat_mem_allocated = 0;
78 static uint64_t stat_mem_deallocated = 0;
79 static uint64_t stat_mem_allocated_total = 0;
80 static uint64_t stat_mem_deallocated_total = 0;
81 static uint64_t stat_mem_high = 0;
82 static uint64_t stat_mem_peak = 0;
83 static uint64_t stat_mem_strdups = 0;
84 static uint64_t stat_used_strdups = 0;
85 static uint64_t stat_used_vectors = 0;
86 static uint64_t stat_used_hashtables = 0;
87 static uint64_t stat_type_vectors = 0;
88 static uint64_t stat_type_hashtables = 0;
89 static stat_size_table_t stat_size_vectors = NULL;
90 static stat_size_table_t stat_size_hashtables = NULL;
91 static stat_mem_block_t *stat_mem_block_root = NULL;
94 * A tiny size_t key-value hashtbale for tracking vector and hashtable
95 * sizes. We can use it for other things too, if we need to. This is
96 * very TIGHT, and efficent in terms of space though.
98 static stat_size_table_t stat_size_new(void) {
99 return (stat_size_table_t)memset(
100 mem_a(sizeof(stat_size_entry_t*) * ST_SIZE),
101 0, ST_SIZE * sizeof(stat_size_entry_t*)
105 static void stat_size_del(stat_size_table_t table) {
107 for (; i < ST_SIZE; i++) if(table[i]) mem_d(table[i]);
111 static stat_size_entry_t *stat_size_get(stat_size_table_t table, size_t key) {
112 size_t hash = (key % ST_SIZE);
113 while (table[hash] && table[hash]->key != key)
114 hash = (hash + 1) % ST_SIZE;
117 static void stat_size_put(stat_size_table_t table, size_t key, size_t value) {
118 size_t hash = (key % ST_SIZE);
119 while (table[hash] && table[hash]->key != key)
120 hash = (hash + 1) % ST_SIZE;
121 table[hash] = (stat_size_entry_t*)mem_a(sizeof(stat_size_entry_t));
122 table[hash]->key = key;
123 table[hash]->value = value;
127 * A basic header of information wrapper allocator. Simply stores
128 * information as a header, returns the memory + 1 past it, can be
129 * retrieved again with - 1. Where type is stat_mem_block_t*.
131 void *stat_mem_allocate(size_t size, size_t line, const char *file, const char *expr) {
132 stat_mem_block_t *info = (stat_mem_block_t*)malloc(size + IDENT_MEM_TOP);
133 void *data = (void *)((char*)info + IDENT_MEM_TOP);
135 if(GMQCC_UNLIKELY(!info))
143 info->next = stat_mem_block_root;
145 /* Write identifier */
146 memcpy(info + 1, IDENT_MEM, IDENT_SIZE);
148 /* likely since it only happens once */
149 if (GMQCC_LIKELY(stat_mem_block_root != NULL)) {
150 VALGRIND_MAKE_MEM_DEFINED(stat_mem_block_root, IDENT_MEM_TOP);
151 stat_mem_block_root->prev = info;
152 VALGRIND_MAKE_MEM_NOACCESS(stat_mem_block_root, IDENT_MEM_TOP);
155 stat_mem_block_root = info;
156 stat_mem_allocated += size;
157 stat_mem_high += size;
158 stat_mem_allocated_total ++;
160 if (stat_mem_high > stat_mem_peak)
161 stat_mem_peak = stat_mem_high;
163 VALGRIND_MALLOCLIKE_BLOCK(data, size, IDENT_MEM_TOP, 0);
167 void stat_mem_deallocate(void *ptr, size_t line, const char *file) {
168 stat_mem_block_t *info = NULL;
169 char *ident = (char *)ptr - IDENT_SIZE;
171 if (GMQCC_UNLIKELY(!ptr))
175 VALGRIND_MAKE_MEM_DEFINED(ident, IDENT_SIZE);
176 if (!strcmp(ident, IDENT_VEC)) {
177 vector_t *vec = (vector_t*)((char *)ptr - IDENT_VEC_TOP);
178 stat_mem_block_t *block = (stat_mem_block_t*)((char *)vec - IDENT_MEM_TOP);
180 VALGRIND_MAKE_MEM_DEFINED(block, sizeof(stat_mem_block_t));
181 con_err("internal warning: invalid use of mem_d:\n");
182 con_err("internal warning: vector (used elements: %u, allocated elements: %u)\n",
184 (unsigned)vec->allocated
186 con_err("internal warning: vector was last (re)allocated with (size: %u (bytes), at location: %s:%u)\n",
187 (unsigned)block->size,
189 (unsigned)block->line
191 con_err("internal warning: released with wrong routine at %s:%u\n", file, (unsigned)line);
192 con_err("internal warning: forwarding to vec_free, please fix it\n");
193 VALGRIND_MAKE_MEM_NOACCESS(block, sizeof(stat_mem_block_t));
194 VALGRIND_MAKE_MEM_NOACCESS(ident, IDENT_SIZE);
198 VALGRIND_MAKE_MEM_NOACCESS(ident, IDENT_SIZE);
199 info = (stat_mem_block_t*)((char *)ptr - IDENT_MEM_TOP);
202 * we need access to the redzone that represents the info block
205 VALGRIND_MAKE_MEM_DEFINED(info, IDENT_MEM_TOP);
207 stat_mem_deallocated += info->size;
208 stat_mem_high -= info->size;
209 stat_mem_deallocated_total ++;
212 /* just need access for a short period */
213 VALGRIND_MAKE_MEM_DEFINED(info->prev, IDENT_MEM_TOP);
214 info->prev->next = info->next;
215 /* don't need access anymore */
216 VALGRIND_MAKE_MEM_NOACCESS(info->prev, IDENT_MEM_TOP);
219 /* just need access for a short period */
220 VALGRIND_MAKE_MEM_DEFINED(info->next, IDENT_MEM_TOP);
221 info->next->prev = info->prev;
222 /* don't need access anymore */
223 VALGRIND_MAKE_MEM_NOACCESS(info->next, IDENT_MEM_TOP);
227 if (info == stat_mem_block_root)
228 stat_mem_block_root = info->next;
231 VALGRIND_MAKE_MEM_NOACCESS(info, IDENT_MEM_TOP);
232 VALGRIND_FREELIKE_BLOCK(ptr, IDENT_MEM_TOP);
235 void *stat_mem_reallocate(void *ptr, size_t size, size_t line, const char *file, const char *expr) {
236 stat_mem_block_t *oldinfo = NULL;
237 stat_mem_block_t *newinfo;
239 if (GMQCC_UNLIKELY(!ptr))
240 return stat_mem_allocate(size, line, file, expr);
242 /* stay consistent with glibc */
243 if (GMQCC_UNLIKELY(!size)) {
244 stat_mem_deallocate(ptr, line, file);
248 oldinfo = (stat_mem_block_t*)((char *)ptr - IDENT_MEM_TOP);
249 newinfo = (stat_mem_block_t*)malloc(size + IDENT_MEM_TOP);
251 if (GMQCC_UNLIKELY(!newinfo)) {
252 stat_mem_deallocate(ptr, line, file);
256 VALGRIND_MALLOCLIKE_BLOCK((char *)newinfo + IDENT_MEM_TOP, size, IDENT_MEM_TOP, 0);
258 /* we need access to the old info redzone */
259 VALGRIND_MAKE_MEM_DEFINED(oldinfo, IDENT_MEM_TOP);
261 /* We need access to the new info redzone */
262 VALGRIND_MAKE_MEM_DEFINED(newinfo, IDENT_MEM_TOP);
263 memcpy((char *)(newinfo + 1), IDENT_MEM, IDENT_SIZE);
264 memcpy((char *)newinfo + IDENT_MEM_TOP, (char *)oldinfo + IDENT_MEM_TOP, oldinfo->size);
265 VALGRIND_MAKE_MEM_NOACCESS(newinfo, IDENT_MEM_TOP);
268 /* just need access for a short period */
269 VALGRIND_MAKE_MEM_DEFINED(oldinfo->prev, IDENT_MEM_TOP);
270 oldinfo->prev->next = oldinfo->next;
271 /* don't need access anymore */
272 VALGRIND_MAKE_MEM_NOACCESS(oldinfo->prev, IDENT_MEM_TOP);
276 /* just need access for a short period */
277 VALGRIND_MAKE_MEM_DEFINED(oldinfo->next, IDENT_MEM_TOP);
278 oldinfo->next->prev = oldinfo->prev;
279 /* don't need access anymore */
280 VALGRIND_MAKE_MEM_NOACCESS(oldinfo->next, IDENT_MEM_TOP);
284 if (oldinfo == stat_mem_block_root)
285 stat_mem_block_root = oldinfo->next;
287 /* we need access to the redzone for the newinfo block */
288 VALGRIND_MAKE_MEM_DEFINED(newinfo, IDENT_MEM_TOP);
290 newinfo->line = line;
291 newinfo->size = size;
292 newinfo->file = file;
293 newinfo->expr = expr;
294 newinfo->prev = NULL;
295 newinfo->next = stat_mem_block_root;
298 * likely since the only time there is no root is when it's
299 * being initialized first.
301 if (GMQCC_LIKELY(stat_mem_block_root != NULL)) {
302 /* we need access to the root */
303 VALGRIND_MAKE_MEM_DEFINED(stat_mem_block_root, IDENT_MEM_TOP);
304 stat_mem_block_root->prev = newinfo;
306 VALGRIND_MAKE_MEM_NOACCESS(stat_mem_block_root, IDENT_MEM_TOP);
309 stat_mem_block_root = newinfo;
310 stat_mem_allocated -= oldinfo->size;
311 stat_mem_high -= oldinfo->size;
312 stat_mem_allocated += newinfo->size;
313 stat_mem_high += newinfo->size;
316 * we're finished with the redzones, lets kill the access
319 VALGRIND_MAKE_MEM_NOACCESS(newinfo, IDENT_MEM_TOP);
320 VALGRIND_MAKE_MEM_NOACCESS(oldinfo, IDENT_MEM_TOP);
322 if (stat_mem_high > stat_mem_peak)
323 stat_mem_peak = stat_mem_high;
326 VALGRIND_FREELIKE_BLOCK(ptr, IDENT_MEM_TOP);
327 return (char *)newinfo + IDENT_MEM_TOP;
331 * strdup does it's own malloc, we need to track malloc. We don't want
332 * to overwrite malloc though, infact, we can't really hook it at all
333 * without library specific assumptions. So we re implement strdup.
335 char *stat_mem_strdup(const char *src, size_t line, const char *file, bool empty) {
343 if (((!empty) ? len : true) && (ptr = (char*)stat_mem_allocate(len + 1, line, file, "strdup"))) {
344 memcpy(ptr, src, len);
348 stat_used_strdups ++;
349 stat_mem_strdups += len;
354 * The reallocate function for resizing vectors.
356 void _util_vec_grow(void **a, size_t i, size_t s) {
357 vector_t *d = (vector_t*)((char *)*a - IDENT_VEC_TOP);
359 stat_size_entry_t *e = NULL;
363 m = 2 * d->allocated + i;
364 p = mem_r(d, s * m + IDENT_VEC_TOP);
367 p = mem_a(s * m + IDENT_VEC_TOP);
368 ((vector_t*)p)->used = 0;
372 if (!stat_size_vectors)
373 stat_size_vectors = stat_size_new();
375 if ((e = stat_size_get(stat_size_vectors, s))) {
378 stat_size_put(stat_size_vectors, s, 1); /* start off with 1 */
384 memcpy(d + 1, IDENT_VEC, IDENT_SIZE);
385 *a = (void *)((char *)d + IDENT_VEC_TOP);
388 void _util_vec_delete(void *data, size_t line, const char *file) {
389 char *ident = (char *)data - IDENT_SIZE;
390 if (!strcmp(ident, IDENT_MEM)) {
391 stat_mem_block_t *block = (stat_mem_block_t*)((char *)data - IDENT_MEM_TOP);
392 VALGRIND_MAKE_MEM_DEFINED(block, sizeof(stat_mem_block_t));
393 con_err("internal warning: invalid use of vec_free:\n");
394 con_err("internal warning: memory block last allocated (size: %u (bytes), at %s:%u)\n",
395 (unsigned)block->size,
397 (unsigned)block->line);
398 con_err("internal warning: released with with wrong routine at %s:%u\n", file, (unsigned)line);
399 con_err("internal warning: forwarding to mem_d, please fix it\n");
400 VALGRIND_MAKE_MEM_NOACCESS(block, sizeof(stat_mem_block_t));
405 stat_mem_deallocate((void*)(ident - sizeof(vector_t)), line, file);
409 * Hash table for generic data, based on dynamic memory allocations
410 * all around. This is the internal interface, please look for
411 * EXPOSED INTERFACE comment below
413 typedef struct hash_node_t {
414 char *key; /* the key for this node in table */
415 void *value; /* pointer to the data as void* */
416 struct hash_node_t *next; /* next node (linked list) */
420 size_t hash(const char *key);
421 size_t util_hthash(hash_table_t *ht, const char *key) {
422 return hash(key) % ht->size;
425 static hash_node_t *_util_htnewpair(const char *key, void *value) {
427 if (!(node = (hash_node_t*)mem_a(sizeof(hash_node_t))))
430 if (!(node->key = util_strdupe(key))) {
442 * EXPOSED INTERFACE for the hashtable implementation
443 * util_htnew(size) -- to make a new hashtable
444 * util_htset(table, key, value, sizeof(value)) -- to set something in the table
445 * util_htget(table, key) -- to get something from the table
446 * util_htdel(table) -- to delete the table
448 hash_table_t *util_htnew(size_t size) {
449 hash_table_t *hashtable = NULL;
450 stat_size_entry_t *find = NULL;
455 if (!stat_size_hashtables)
456 stat_size_hashtables = stat_size_new();
458 if (!(hashtable = (hash_table_t*)mem_a(sizeof(hash_table_t))))
461 if (!(hashtable->table = (hash_node_t**)mem_a(sizeof(hash_node_t*) * size))) {
466 if ((find = stat_size_get(stat_size_hashtables, size)))
469 stat_type_hashtables++;
470 stat_size_put(stat_size_hashtables, size, 1);
473 hashtable->size = size;
474 memset(hashtable->table, 0, sizeof(hash_node_t*) * size);
476 stat_used_hashtables++;
480 void util_htseth(hash_table_t *ht, const char *key, size_t bin, void *value) {
481 hash_node_t *newnode = NULL;
482 hash_node_t *next = NULL;
483 hash_node_t *last = NULL;
485 next = ht->table[bin];
487 while (next && next->key && strcmp(key, next->key) > 0)
488 last = next, next = next->next;
490 /* already in table, do a replace */
491 if (next && next->key && strcmp(key, next->key) == 0) {
494 /* not found, grow a pair man :P */
495 newnode = _util_htnewpair(key, value);
496 if (next == ht->table[bin]) {
497 newnode->next = next;
498 ht->table[bin] = newnode;
500 last->next = newnode;
502 newnode->next = next;
503 last->next = newnode;
508 void util_htset(hash_table_t *ht, const char *key, void *value) {
509 util_htseth(ht, key, util_hthash(ht, key), value);
512 void *util_htgeth(hash_table_t *ht, const char *key, size_t bin) {
513 hash_node_t *pair = ht->table[bin];
515 while (pair && pair->key && strcmp(key, pair->key) > 0)
518 if (!pair || !pair->key || strcmp(key, pair->key) != 0)
524 void *util_htget(hash_table_t *ht, const char *key) {
525 return util_htgeth(ht, key, util_hthash(ht, key));
528 void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin);
529 void *code_util_str_htgeth(hash_table_t *ht, const char *key, size_t bin) {
534 keylen = strlen(key);
536 pair = ht->table[bin];
537 while (pair && pair->key) {
538 len = strlen(pair->key);
544 cmp = strcmp(key, pair->key);
552 cmp = strcmp(key, pair->key + len - keylen);
554 uintptr_t up = (uintptr_t)pair->value;
564 * Free all allocated data in a hashtable, this is quite the amount
567 void util_htrem(hash_table_t *ht, void (*callback)(void *data)) {
570 for (; i < ht->size; ++i) {
571 hash_node_t *n = ht->table[i];
591 void util_htrmh(hash_table_t *ht, const char *key, size_t bin, void (*cb)(void*)) {
592 hash_node_t **pair = &ht->table[bin];
595 while (*pair && (*pair)->key && strcmp(key, (*pair)->key) > 0)
596 pair = &(*pair)->next;
599 if (!tmp || !tmp->key || strcmp(key, tmp->key) != 0)
610 void util_htrm(hash_table_t *ht, const char *key, void (*cb)(void*)) {
611 util_htrmh(ht, key, util_hthash(ht, key), cb);
614 void util_htdel(hash_table_t *ht) {
615 util_htrem(ht, NULL);
619 * The following functions below implement printing / dumping of statistical
622 static void stat_dump_mem_contents(stat_mem_block_t *block, uint16_t cols) {
623 unsigned char *buffer = (unsigned char *)mem_a(cols);
624 unsigned char *memory = (unsigned char *)(block + 1);
627 for (i = 0; i < block->size; i++) {
630 con_out(" %s\n", buffer);
631 con_out(" 0x%08X: ", i);
634 con_out(" %02X", memory[i]);
636 buffer[i % cols] = ((memory[i] < 0x20) || (memory[i] > 0x7E))
640 buffer[(i % cols) + 1] = '\0';
643 while ((i % cols) != 0) {
648 con_out(" %s\n", buffer);
652 static void stat_dump_mem_leaks(void) {
653 stat_mem_block_t *info;
654 /* we need access to the root for this */
655 VALGRIND_MAKE_MEM_DEFINED(stat_mem_block_root, sizeof(stat_mem_block_t));
656 for (info = stat_mem_block_root; info; info = info->next) {
657 /* we need access to the block */
658 VALGRIND_MAKE_MEM_DEFINED(info, sizeof(stat_mem_block_t));
659 con_out("lost: %u (bytes) at %s:%u from expression `%s`\n",
666 stat_dump_mem_contents(info, OPTS_OPTION_U16(OPTION_MEMDUMPCOLS));
669 * we're finished with the access, the redzone should be marked
670 * inaccesible so that invalid read/writes that could 'step-into'
671 * those redzones will show up as invalid read/writes in valgrind.
673 VALGRIND_MAKE_MEM_NOACCESS(info, sizeof(stat_mem_block_t));
675 VALGRIND_MAKE_MEM_NOACCESS(stat_mem_block_root, sizeof(stat_mem_block_t));
678 static void stat_dump_mem_info(void) {
679 con_out("Memory Information:\n\
680 Total allocations: %llu\n\
681 Total deallocations: %llu\n\
682 Total allocated: %f (MB)\n\
683 Total deallocated: %f (MB)\n\
684 Total peak memory: %f (MB)\n\
685 Total leaked memory: %f (MB) in %llu allocations\n",
686 stat_mem_allocated_total,
687 stat_mem_deallocated_total,
688 (float)(stat_mem_allocated) / 1048576.0f,
689 (float)(stat_mem_deallocated) / 1048576.0f,
690 (float)(stat_mem_peak) / 1048576.0f,
691 (float)(stat_mem_allocated - stat_mem_deallocated) / 1048576.0f,
692 stat_mem_allocated_total - stat_mem_deallocated_total
696 static void stat_dump_stats_table(stat_size_table_t table, const char *string, uint64_t *size) {
702 for (i = 0, j = 1; i < ST_SIZE; i++) {
703 stat_size_entry_t *entry;
705 if (!(entry = table[i]))
708 con_out(string, (unsigned)j, (unsigned)entry->key, (unsigned)entry->value);
712 *size += entry->key * entry->value;
717 if (OPTS_OPTION_BOOL(OPTION_MEMCHK) ||
718 OPTS_OPTION_BOOL(OPTION_STATISTICS)) {
721 con_out("Memory Statistics:\n\
722 Total vectors allocated: %llu\n\
723 Total string duplicates: %llu\n\
724 Total string duplicate memory: %f (MB)\n\
725 Total hashtables allocated: %llu\n\
726 Total unique vector sizes: %llu\n",
729 (float)(stat_mem_strdups) / 1048576.0f,
730 stat_used_hashtables,
734 stat_dump_stats_table (
736 " %2u| # of %5u byte vectors: %u\n",
741 " Total unique hashtable sizes: %llu\n",
745 stat_dump_stats_table (
746 stat_size_hashtables,
747 " %2u| # of %5u element hashtables: %u\n",
752 " Total vector memory: %f (MB)\n\n",
753 (float)(mem) / 1048576.0f
757 if (stat_size_vectors)
758 stat_size_del(stat_size_vectors);
759 if (stat_size_hashtables)
760 stat_size_del(stat_size_hashtables);
762 if (OPTS_OPTION_BOOL(OPTION_DEBUG) ||
763 OPTS_OPTION_BOOL(OPTION_MEMCHK))
764 stat_dump_mem_info();
766 if (OPTS_OPTION_BOOL(OPTION_DEBUG))
767 stat_dump_mem_leaks();