1 /* 2 * allocate.c - simple space-efficient blob allocator. 3 * 4 * Copyright (C) 2003 Transmeta Corp. 5 * 2003-2004 Linus Torvalds 6 * 7 * Permission is hereby granted, free of charge, to any person obtaining a copy 8 * of this software and associated documentation files (the "Software"), to deal 9 * in the Software without restriction, including without limitation the rights 10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 11 * copies of the Software, and to permit persons to whom the Software is 12 * furnished to do so, subject to the following conditions: 13 * 14 * The above copyright notice and this permission notice shall be included in 15 * all copies or substantial portions of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 23 * THE SOFTWARE. 24 * 25 * Simple allocator for data that doesn't get partially free'd. 26 * The tokenizer and parser allocate a _lot_ of small data structures 27 * (often just two-three bytes for things like small integers), 28 * and since they all depend on each other you can't free them 29 * individually _anyway_. So do something that is very space- 30 * efficient: allocate larger "blobs", and give out individual 31 * small bits and pieces of it with no maintenance overhead. 32 */ 33 #include <stdlib.h> 34 #include <stddef.h> 35 #include <stdio.h> 36 37 #include "lib.h" 38 #include "allocate.h" 39 #include "compat.h" 40 #include "token.h" 41 #include "symbol.h" 42 #include "scope.h" 43 #include "expression.h" 44 #include "linearize.h" 45 46 void protect_allocations(struct allocator_struct *desc) 47 { 48 desc->blobs = NULL; 49 } 50 51 void drop_all_allocations(struct allocator_struct *desc) 52 { 53 struct allocation_blob *blob = desc->blobs; 54 55 desc->blobs = NULL; 56 desc->allocations = 0; 57 desc->total_bytes = 0; 58 desc->useful_bytes = 0; 59 desc->freelist = NULL; 60 while (blob) { 61 struct allocation_blob *next = blob->next; 62 blob_free(blob, desc->chunking); 63 blob = next; 64 } 65 } 66 67 void free_one_entry(struct allocator_struct *desc, void *entry) 68 { 69 void **p = entry; 70 *p = desc->freelist; 71 desc->freelist = p; 72 } 73 74 void *allocate(struct allocator_struct *desc, unsigned int size) 75 { 76 unsigned long alignment = desc->alignment; 77 struct allocation_blob *blob = desc->blobs; 78 void *retval; 79 80 /* 81 * NOTE! The freelist only works with things that are 82 * (a) sufficiently aligned 83 * (b) use a constant size 84 * Don't try to free allocators that don't follow 85 * these rules. 86 */ 87 if (desc->freelist) { 88 void **p = desc->freelist; 89 retval = p; 90 desc->freelist = *p; 91 do { 92 *p = NULL; 93 p++; 94 } while ((size -= sizeof(void *)) > 0); 95 return retval; 96 } 97 98 desc->allocations++; 99 desc->useful_bytes += size; 100 size = (size + alignment - 1) & ~(alignment-1); 101 if (!blob || blob->left < size) { 102 unsigned int offset, chunking = desc->chunking; 103 struct allocation_blob *newblob = blob_alloc(chunking); 104 if (!newblob) 105 die("out of memory"); 106 if (size > chunking) 107 die("alloc too big"); 108 desc->total_bytes += chunking; 109 newblob->next = blob; 110 blob = newblob; 111 desc->blobs = newblob; 112 offset = offsetof(struct allocation_blob, data); 113 offset = (offset + alignment - 1) & ~(alignment-1); 114 blob->left = chunking - offset; 115 blob->offset = offset - offsetof(struct allocation_blob, data); 116 } 117 retval = blob->data + blob->offset; 118 blob->offset += size; 119 blob->left -= size; 120 return retval; 121 } 122 123 void show_allocations(struct allocator_struct *x) 124 { 125 fprintf(stderr, "%s: %lu allocations, %lu bytes (%lu total bytes, " 126 "%6.2f%% usage, %6.2f average size)\n", 127 x->name, x->allocations, x->useful_bytes, x->total_bytes, 128 100 * (double) x->useful_bytes / x->total_bytes, 129 (double) x->useful_bytes / x->allocations); 130 } 131 132 void get_allocator_stats(struct allocator_struct *x, struct allocator_stats *s) 133 { 134 s->name = x->name; 135 s->allocations = x->allocations; 136 s->useful_bytes = x->useful_bytes; 137 s->total_bytes = x->total_bytes; 138 } 139 140 ALLOCATOR(ident, "identifiers"); 141 ALLOCATOR(token, "tokens"); 142 ALLOCATOR(context, "contexts"); 143 ALLOCATOR(symbol, "symbols"); 144 ALLOCATOR(expression, "expressions"); 145 ALLOCATOR(statement, "statements"); 146 ALLOCATOR(string, "strings"); 147 ALLOCATOR(scope, "scopes"); 148 __DO_ALLOCATOR(void, 0, 1, "bytes", bytes); 149 ALLOCATOR(basic_block, "basic_block"); 150 ALLOCATOR(entrypoint, "entrypoint"); 151 ALLOCATOR(instruction, "instruction"); 152 ALLOCATOR(multijmp, "multijmp"); 153 ALLOCATOR(pseudo, "pseudo"); 154 155 156