1 : /*
2 : Copyright (C) 2007, Bruce Ediger
3 :
4 : This file is part of cl.
5 :
6 : cl is free software; you can redistribute it and/or modify
7 : it under the terms of the GNU General Public License as published by
8 : the Free Software Foundation; either version 2 of the License, or
9 : (at your option) any later version.
10 :
11 : cl is distributed in the hope that it will be useful,
12 : but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : GNU General Public License for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with cl; if not, write to the Free Software
18 : Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 :
20 : */
21 : #include <stdio.h>
22 : #include <unistd.h> /* getpagesize() */
23 : #include <stdlib.h> /* malloc(), free() */
24 : #include <assert.h> /* malloc(), free() */
25 :
26 : #include <arena.h>
27 :
28 : #define roundup(x, y) ((((x)+((y)-1))/(y))*(y))
29 :
30 : union combo {
31 : char c;
32 : short s;
33 : int i;
34 : long l;
35 : long long ll;
36 : void *vp;
37 : char *cp;
38 : short *sp;
39 : int *ip;
40 : long *lp;
41 : float f;
42 : double d;
43 : };
44 :
45 : struct memory_arena {
46 : char *first_allocation;
47 : char *next_allocation;
48 : int sz; /* max free size */
49 : int remaining; /* how many bytes remain in allocation */
50 : struct memory_arena *next;
51 : int usage_info;
52 : int sn; /* serial number: malloc order */
53 : };
54 :
55 : static int pagesize = 0;
56 : static int headersize = 0;
57 : static int combosize = 0;
58 :
59 : /* Public way to get a new struct memory_arena
60 : * The first struct memory_arena in a chain constitutes a "dummy",
61 : * an empty head element of a FIFO (stack) of structs memory_arena.
62 : * The first allocation demanded from a memory arena will cause
63 : * the malloc() of one or more pages, and a 2nd element in the stack.
64 : */
65 : struct memory_arena *
66 : new_arena(int memory_info_flag)
67 70 : {
68 70 : struct memory_arena *ra = NULL;
69 :
70 70 : if (!pagesize)
71 : {
72 70 : combosize = sizeof(union combo);
73 70 : pagesize = getpagesize();
74 70 : headersize = roundup(sizeof(struct memory_arena), combosize);
75 : }
76 :
77 70 : ra = malloc(sizeof(*ra));
78 :
79 70 : ra->sz = 0;
80 70 : ra->remaining = 0;
81 70 : ra->first_allocation = ra->next_allocation = NULL;
82 70 : ra->next = NULL;
83 70 : ra->usage_info = memory_info_flag;
84 70 : ra->sn = 0;
85 :
86 70 : return ra;
87 : }
88 :
89 : void
90 : deallocate_arena(struct memory_arena *ma, int memory_info_flag)
91 69 : {
92 69 : int free_arena_cnt = 0;
93 69 : int maxsz = 0;
94 2279 : while (ma)
95 : {
96 2141 : struct memory_arena *tmp = ma->next;
97 :
98 2141 : if (ma->sz > maxsz) maxsz = ma->sz;
99 :
100 2141 : ma->next = NULL;
101 2141 : free(ma);
102 :
103 2141 : ma = tmp;
104 2141 : ++free_arena_cnt;
105 : }
106 :
107 69 : if (memory_info_flag)
108 : {
109 2 : fprintf(stderr, "Page size %d (0x%x)\n", pagesize, pagesize);
110 2 : fprintf(stderr, "Header size %d (0x%x)\n", headersize, headersize);
111 2 : fprintf(stderr, "Allocated %d arenas\n", free_arena_cnt);
112 2 : fprintf(stderr, "Max arena size %d (0x%x)\n", maxsz, maxsz);
113 : }
114 69 : }
115 :
116 : void
117 : free_arena_contents(struct memory_arena *ma)
118 5818 : {
119 5818 : int last_sn = ma->sn;
120 5818 : int max_sn = ma->sn;
121 5818 : int arena_count = 0;
122 :
123 5818 : ma = ma->next; /* dummy head node */
124 66373 : while (ma)
125 : {
126 54737 : ++arena_count;
127 :
128 54737 : if (ma->sn >= last_sn + 1)
129 : {
130 0 : fprintf(stderr, "Loop in chain of allocations: S/N %d, next S/N %d\n",
131 : last_sn, ma->sn);
132 0 : fprintf(stderr, "Allocated %d arenas\n", max_sn);
133 0 : break;
134 : } else
135 54737 : last_sn = ma->sn;
136 :
137 54737 : if (ma->sn > max_sn)
138 : {
139 0 : fprintf(stderr, "Chain of allocations out of order: max S/N %d, S/N %d\n",
140 : max_sn, ma->sn);
141 0 : fprintf(stderr, "Allocated %d arenas\n", max_sn);
142 0 : break;
143 : }
144 :
145 54737 : if (arena_count > max_sn)
146 : {
147 0 : fprintf(stderr, "Found at least %d allocations on chain, should only have %d\n",
148 : arena_count, max_sn);
149 0 : break;
150 : }
151 :
152 54737 : ma->remaining = ma->sz;
153 54737 : ma->next_allocation = ma->first_allocation;
154 54737 : ma = ma->next;
155 : }
156 5818 : }
157 :
158 : void *
159 : arena_alloc(struct memory_arena *ma, size_t size)
160 2145250 : {
161 2145250 : void *r = NULL;
162 : struct memory_arena *ca;
163 : size_t nsize;
164 :
165 2145250 : assert(NULL != ma);
166 :
167 : /* What you actually have to allocate to get to
168 : * a block "suitably aligned" for any use. */
169 2145250 : nsize = roundup(size, combosize);
170 :
171 2145250 : ca = ma->next;
172 :
173 1412756767 : while (ca && nsize > ca->remaining)
174 1408466267 : ca = ca->next;
175 :
176 2145250 : if (NULL == ca)
177 : {
178 :
179 : /* You could do something like moving all arenas with
180 : * less than combosize remaining into a 2nd list - one
181 : * that never gets checked, as combosize is the minimum
182 : * allocation possible. */
183 :
184 : /* create a new struct memory_arena of at least 1 page */
185 2073 : size_t arena_size = roundup((nsize + headersize), pagesize);
186 :
187 2073 : ca = malloc(arena_size);
188 :
189 2073 : ca->first_allocation = ((char *)ca) + headersize;
190 2073 : ca->next_allocation = ca->first_allocation;
191 2073 : ca->sz = arena_size - headersize;
192 2073 : ca->remaining = ca->sz;
193 :
194 : /* Each struct arena gets a unique serial number,
195 : * and the dummy "head" node sn field has a count of
196 : * how many structs arena reside in the list.
197 : */
198 2073 : ca->sn = ++ma->sn;
199 :
200 : /* since the next 2 lines make a FIFO stack of structs
201 : * arena, the serial numbers must decrease by one
202 : * as you walk the stack. */
203 2073 : ca->next = ma->next;
204 2073 : ma->next = ca;
205 : }
206 :
207 2145250 : r = ca->next_allocation;
208 2145250 : ca->next_allocation += nsize; /* next_allocation stays aligned */
209 2145250 : ca->remaining -= nsize;
210 :
211 2145250 : return r;
212 : }
213 :
|
