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
protect_allocations(struct allocator_struct * desc)46 void protect_allocations(struct allocator_struct *desc)
47 {
48 desc->blobs = NULL;
49 }
50
drop_all_allocations(struct allocator_struct * desc)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
free_one_entry(struct allocator_struct * desc,void * entry)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
allocate(struct allocator_struct * desc,unsigned int size)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
show_allocations(struct allocator_struct * x)123 void show_allocations(struct allocator_struct *x)
124 {
125 fprintf(stderr, "%s: %d 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
get_allocator_stats(struct allocator_struct * x,struct allocator_stats * s)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(asm_operand, "asmops");
145 ALLOCATOR(expression, "expressions");
146 ALLOCATOR(statement, "statements");
147 ALLOCATOR(string, "strings");
148 ALLOCATOR(scope, "scopes");
149 __DO_ALLOCATOR(void, 0, 1, "bytes", bytes);
150 ALLOCATOR(basic_block, "basic_block");
151 ALLOCATOR(entrypoint, "entrypoint");
152 ALLOCATOR(instruction, "instruction");
153 ALLOCATOR(multijmp, "multijmp");
154 ALLOCATOR(pseudo, "pseudo");
155
156
157