Warning: That file was not part of the compilation database. It may have many parsing errors.

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

Warning: That file was not part of the compilation database. It may have many parsing errors.