1 #include <stdlib.h>
2 #include <string.h>
3 #include "set-hooks.h"
4
5 #include "hurdmalloc.h" /* XXX see that file */
6
7 #include <mach.h>
8 #include <mach/spin-lock.h>
9 #define vm_allocate __vm_allocate
10 #define vm_page_size __vm_page_size
11
12 /*
13 * Mach Operating System
14 * Copyright (c) 1991,1990,1989 Carnegie Mellon University
15 * All Rights Reserved.
16 *
17 * Permission to use, copy, modify and distribute this software and its
18 * documentation is hereby granted, provided that both the copyright
19 * notice and this permission notice appear in all copies of the
20 * software, derivative works or modified versions, and any portions
21 * thereof, and that both notices appear in supporting documentation.
22 *
23 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
24 * CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
25 * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
26 *
27 * Carnegie Mellon requests users of this software to return to
28 *
29 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
30 * School of Computer Science
31 * Carnegie Mellon University
32 * Pittsburgh PA 15213-3890
33 *
34 * any improvements or extensions that they make and grant Carnegie Mellon
35 * the rights to redistribute these changes.
36 */
37 /*
38 * (pre-GNU) HISTORY
39 *
40 * Revision 2.7 91/05/14 17:57:34 mrt
41 * Correcting copyright
42 *
43 * Revision 2.6 91/02/14 14:20:26 mrt
44 * Added new Mach copyright
45 * [91/02/13 12:41:21 mrt]
46 *
47 * Revision 2.5 90/11/05 14:37:33 rpd
48 * Added malloc_fork* code.
49 * [90/11/02 rwd]
50 *
51 * Add spin_lock_t.
52 * [90/10/31 rwd]
53 *
54 * Revision 2.4 90/08/07 14:31:28 rpd
55 * Removed RCS keyword nonsense.
56 *
57 * Revision 2.3 90/06/02 15:14:00 rpd
58 * Converted to new IPC.
59 * [90/03/20 20:56:57 rpd]
60 *
61 * Revision 2.2 89/12/08 19:53:59 rwd
62 * Removed conditionals.
63 * [89/10/23 rwd]
64 *
65 * Revision 2.1 89/08/03 17:09:46 rwd
66 * Created.
67 *
68 *
69 * 13-Sep-88 Eric Cooper (ecc) at Carnegie Mellon University
70 * Changed realloc() to copy min(old size, new size) bytes.
71 * Bug found by Mike Kupfer at Olivetti.
72 */
73 /*
74 * File: malloc.c
75 * Author: Eric Cooper, Carnegie Mellon University
76 * Date: July, 1988
77 *
78 * Memory allocator for use with multiple threads.
79 */
80
81
82 #include <assert.h>
83
84 #define MCHECK
85
86 /*
87 * Structure of memory block header.
88 * When free, next points to next block on free list.
89 * When allocated, fl points to free list.
90 * Size of header is 4 bytes, so minimum usable block size is 8 bytes.
91 */
92
93 #define CHECK_BUSY 0x8a3c743e
94 #define CHECK_FREE 0x66688b92
95
96 #ifdef MCHECK
97
98 typedef struct header {
99 long check;
100 union {
101 struct header *next;
102 struct free_list *fl;
103 } u;
104 } *header_t;
105
106 #define HEADER_SIZE sizeof (struct header)
107 #define HEADER_NEXT(h) ((h)->u.next)
108 #define HEADER_FREE(h) ((h)->u.fl)
109 #define HEADER_CHECK(h) ((h)->check)
110 #define MIN_SIZE 16
111 #define LOG2_MIN_SIZE 4
112
113 #else /* ! MCHECK */
114
115 typedef union header {
116 union header *next;
117 struct free_list *fl;
118 } *header_t;
119
120 #define HEADER_SIZE sizeof (union header)
121 #define HEADER_NEXT(h) ((h)->next)
122 #define HEADER_FREE(h) ((h)->fl)
123 #define MIN_SIZE 8 /* minimum block size */
124 #define LOG2_MIN_SIZE 3
125
126 #endif /* MCHECK */
127
128 typedef struct free_list {
129 spin_lock_t lock; /* spin lock for mutual exclusion */
130 header_t head; /* head of free list for this size */
131 #ifdef DEBUG
132 int in_use; /* # mallocs - # frees */
133 #endif /* DEBUG */
134 } *free_list_t;
135
136 /*
137 * Free list with index i contains blocks of size 2 ^ (i + LOG2_MIN_SIZE)
138 * including header. Smallest block size is MIN_SIZE, with MIN_SIZE -
139 * HEADER_SIZE bytes available to user. Size argument to malloc is a signed
140 * integer for sanity checking, so largest block size is 2^31.
141 */
142 #define NBUCKETS 29
143
144 static struct free_list malloc_free_list[NBUCKETS];
145
146 /* Initialization just sets everything to zero, but might be necessary on a
147 machine where spin_lock_init does otherwise, and is necessary when
148 running an executable that was written by something like Emacs's unexec.
149 It preserves the values of data variables like malloc_free_list, but
150 does not save the vm_allocate'd space allocated by this malloc. */
151
152 static void attribute_used_retain
153 malloc_init (void)
154 {
155 int i;
156 for (i = 0; i < NBUCKETS; ++i)
157 {
158 spin_lock_init (&malloc_free_list[i].lock);
159 malloc_free_list[i].head = NULL;
160 #ifdef DEBUG
161 malloc_free_list[i].in_use = 0;
162 #endif
163 }
164 }
165
166 static void
167 more_memory(int size, free_list_t fl)
168 {
169 int amount;
170 int n;
171 vm_address_t where;
172 header_t h;
173 kern_return_t r;
174
175 if (size <= vm_page_size) {
176 amount = vm_page_size;
177 n = vm_page_size / size;
178 /* We lose vm_page_size - n*size bytes here. */
179 } else {
180 amount = size;
181 n = 1;
182 }
183
184 r = vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE);
185 assert_perror (r);
186
187 h = (header_t) where;
188 do {
189 HEADER_NEXT (h) = fl->head;
190 #ifdef MCHECK
191 HEADER_CHECK (h) = CHECK_FREE;
192 #endif
193 fl->head = h;
194 h = (header_t) ((char *) h + size);
195 } while (--n != 0);
196 }
197
198 /* Declaration changed to standard one for GNU. */
199 void *
200 malloc (size_t size)
201 {
202 int i, n;
203 free_list_t fl;
204 header_t h;
205
206 if ((int) size < 0) /* sanity check */
207 return 0;
208 size += HEADER_SIZE;
209 /*
210 * Find smallest power-of-two block size
211 * big enough to hold requested size plus header.
212 */
213 i = 0;
214 n = MIN_SIZE;
215 while (n < size) {
216 i += 1;
217 n <<= 1;
218 }
219 assert(i < NBUCKETS);
220 fl = &malloc_free_list[i];
221 spin_lock(&fl->lock);
222 h = fl->head;
223 if (h == 0) {
224 /*
225 * Free list is empty;
226 * allocate more blocks.
227 */
228 more_memory(n, fl);
229 h = fl->head;
230 if (h == 0) {
231 /*
232 * Allocation failed.
233 */
234 spin_unlock(&fl->lock);
235 return 0;
236 }
237 }
238 /*
239 * Pop block from free list.
240 */
241 fl->head = HEADER_NEXT (h);
242
243 #ifdef MCHECK
244 assert (HEADER_CHECK (h) == CHECK_FREE);
245 HEADER_CHECK (h) = CHECK_BUSY;
246 #endif
247
248 #ifdef DEBUG
249 fl->in_use += 1;
250 #endif /* DEBUG */
251 spin_unlock(&fl->lock);
252 /*
253 * Store free list pointer in block header
254 * so we can figure out where it goes
255 * at free() time.
256 */
257 HEADER_FREE (h) = fl;
258 /*
259 * Return pointer past the block header.
260 */
261 return ((char *) h) + HEADER_SIZE;
262 }
263
264 /* Declaration changed to standard one for GNU. */
265 void
266 free (void *base)
267 {
268 header_t h;
269 free_list_t fl;
270 int i;
271
272 if (base == 0)
273 return;
274 /*
275 * Find free list for block.
276 */
277 h = (header_t) (base - HEADER_SIZE);
278
279 #ifdef MCHECK
280 assert (HEADER_CHECK (h) == CHECK_BUSY);
281 #endif
282
283 fl = HEADER_FREE (h);
284 i = fl - malloc_free_list;
285 /*
286 * Sanity checks.
287 */
288 if (i < 0 || i >= NBUCKETS) {
289 assert(0 <= i && i < NBUCKETS);
290 return;
291 }
292 if (fl != &malloc_free_list[i]) {
293 assert(fl == &malloc_free_list[i]);
294 return;
295 }
296 /*
297 * Push block on free list.
298 */
299 spin_lock(&fl->lock);
300 HEADER_NEXT (h) = fl->head;
301 #ifdef MCHECK
302 HEADER_CHECK (h) = CHECK_FREE;
303 #endif
304 fl->head = h;
305 #ifdef DEBUG
306 fl->in_use -= 1;
307 #endif /* DEBUG */
308 spin_unlock(&fl->lock);
309 return;
310 }
311
312 /* Declaration changed to standard one for GNU. */
313 void *
314 realloc (void *old_base, size_t new_size)
315 {
316 header_t h;
317 free_list_t fl;
318 int i;
319 unsigned int old_size;
320 char *new_base;
321
322 if (old_base == 0)
323 return malloc (new_size);
324
325 /*
326 * Find size of old block.
327 */
328 h = (header_t) (old_base - HEADER_SIZE);
329 #ifdef MCHECK
330 assert (HEADER_CHECK (h) == CHECK_BUSY);
331 #endif
332 fl = HEADER_FREE (h);
333 i = fl - malloc_free_list;
334 /*
335 * Sanity checks.
336 */
337 if (i < 0 || i >= NBUCKETS) {
338 assert(0 <= i && i < NBUCKETS);
339 return 0;
340 }
341 if (fl != &malloc_free_list[i]) {
342 assert(fl == &malloc_free_list[i]);
343 return 0;
344 }
345 /*
346 * Free list with index i contains blocks of size
347 * 2 ^ (i + * LOG2_MIN_SIZE) including header.
348 */
349 old_size = (1 << (i + LOG2_MIN_SIZE)) - HEADER_SIZE;
350
351 if (new_size <= old_size
352 && new_size > (((old_size + HEADER_SIZE) >> 1) - HEADER_SIZE))
353 /* The new size still fits in the same block, and wouldn't fit in
354 the next smaller block! */
355 return old_base;
356
357 /*
358 * Allocate new block, copy old bytes, and free old block.
359 */
360 new_base = malloc(new_size);
361 if (new_base)
362 memcpy (new_base, old_base,
363 (int) (old_size < new_size ? old_size : new_size));
364
365 if (new_base || new_size == 0)
366 /* Free OLD_BASE, but only if the malloc didn't fail. */
367 free (old_base);
368
369 return new_base;
370 }
371
372 #ifdef DEBUG
373 void
374 print_malloc_free_list (void)
375 {
376 int i, size;
377 free_list_t fl;
378 int n;
379 header_t h;
380 int total_used = 0;
381 int total_free = 0;
382
383 fprintf(stderr, " Size In Use Free Total\n");
384 for (i = 0, size = MIN_SIZE, fl = malloc_free_list;
385 i < NBUCKETS;
386 i += 1, size <<= 1, fl += 1) {
387 spin_lock(&fl->lock);
388 if (fl->in_use != 0 || fl->head != 0) {
389 total_used += fl->in_use * size;
390 for (n = 0, h = fl->head; h != 0; h = HEADER_NEXT (h), n += 1)
391 ;
392 total_free += n * size;
393 fprintf(stderr, "%10d %10d %10d %10d\n",
394 size, fl->in_use, n, fl->in_use + n);
395 }
396 spin_unlock(&fl->lock);
397 }
398 fprintf(stderr, " all sizes %10d %10d %10d\n",
399 total_used, total_free, total_used + total_free);
400 }
401 #endif /* DEBUG */
402
403 void
404 _hurd_malloc_fork_prepare(void)
405 /*
406 * Prepare the malloc module for a fork by insuring that no thread is in a
407 * malloc critical section.
408 */
409 {
410 int i;
411
412 for (i = 0; i < NBUCKETS; i++) {
413 spin_lock(&malloc_free_list[i].lock);
414 }
415 }
416
417 void
418 _hurd_malloc_fork_parent(void)
419 /*
420 * Called in the parent process after a fork() to resume normal operation.
421 */
422 {
423 int i;
424
425 for (i = NBUCKETS-1; i >= 0; i--) {
426 spin_unlock(&malloc_free_list[i].lock);
427 }
428 }
429
430 void
431 _hurd_malloc_fork_child(void)
432 /*
433 * Called in the child process after a fork() to resume normal operation.
434 */
435 {
436 int i;
437
438 for (i = NBUCKETS-1; i >= 0; i--) {
439 spin_unlock(&malloc_free_list[i].lock);
440 }
441 }
442
443
444 SET_RELHOOK (_hurd_preinit_hook, malloc_init);