constraints: remove debugging and use the stripped() expression
[smatch.git] / allocate.c
blob502095ef2ed011007a67d43809c980a16dd0c8bc
1 /*
2 * allocate.c - simple space-efficient blob allocator.
4 * Copyright (C) 2003 Transmeta Corp.
5 * 2003-2004 Linus Torvalds
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:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
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.
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.
33 #include <stdlib.h>
34 #include <stddef.h>
35 #include <stdio.h>
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"
46 void protect_allocations(struct allocator_struct *desc)
48 desc->blobs = NULL;
51 void drop_all_allocations(struct allocator_struct *desc)
53 struct allocation_blob *blob = desc->blobs;
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;
67 void free_one_entry(struct allocator_struct *desc, void *entry)
69 void **p = entry;
70 *p = desc->freelist;
71 desc->freelist = p;
74 void *allocate(struct allocator_struct *desc, unsigned int size)
76 unsigned long alignment = desc->alignment;
77 struct allocation_blob *blob = desc->blobs;
78 void *retval;
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.
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;
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 desc->total_bytes += chunking;
107 newblob->next = blob;
108 blob = newblob;
109 desc->blobs = newblob;
110 offset = offsetof(struct allocation_blob, data);
111 offset = (offset + alignment - 1) & ~(alignment-1);
112 blob->left = chunking - offset;
113 blob->offset = offset - offsetof(struct allocation_blob, data);
115 retval = blob->data + blob->offset;
116 blob->offset += size;
117 blob->left -= size;
118 return retval;
121 void show_allocations(struct allocator_struct *x)
123 fprintf(stderr, "%s: %lu allocations, %lu bytes (%lu total bytes, "
124 "%6.2f%% usage, %6.2f average size)\n",
125 x->name, x->allocations, x->useful_bytes, x->total_bytes,
126 100 * (double) x->useful_bytes / x->total_bytes,
127 (double) x->useful_bytes / x->allocations);
130 void get_allocator_stats(struct allocator_struct *x, struct allocator_stats *s)
132 s->name = x->name;
133 s->allocations = x->allocations;
134 s->useful_bytes = x->useful_bytes;
135 s->total_bytes = x->total_bytes;
138 ALLOCATOR(ident, "identifiers");
139 ALLOCATOR(token, "tokens");
140 ALLOCATOR(context, "contexts");
141 ALLOCATOR(symbol, "symbols");
142 ALLOCATOR(expression, "expressions");
143 ALLOCATOR(statement, "statements");
144 ALLOCATOR(string, "strings");
145 ALLOCATOR(scope, "scopes");
146 __DO_ALLOCATOR(void, 0, 1, "bytes", bytes);
147 ALLOCATOR(basic_block, "basic_block");
148 ALLOCATOR(entrypoint, "entrypoint");
149 ALLOCATOR(instruction, "instruction");
150 ALLOCATOR(multijmp, "multijmp");
151 ALLOCATOR(pseudo, "pseudo");