]>
Commit | Line | Data |
---|---|---|
28f540f4 RM |
1 | #include <stdlib.h> |
2 | #include <string.h> | |
3 | ||
28f540f4 RM |
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 | ||
8a0746ae | 10 | /* |
28f540f4 RM |
11 | * Mach Operating System |
12 | * Copyright (c) 1991,1990,1989 Carnegie Mellon University | |
13 | * All Rights Reserved. | |
8a0746ae | 14 | * |
28f540f4 RM |
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. | |
8a0746ae | 20 | * |
28f540f4 RM |
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. | |
8a0746ae | 24 | * |
28f540f4 | 25 | * Carnegie Mellon requests users of this software to return to |
8a0746ae | 26 | * |
28f540f4 RM |
27 | * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU |
28 | * School of Computer Science | |
29 | * Carnegie Mellon University | |
30 | * Pittsburgh PA 15213-3890 | |
8a0746ae | 31 | * |
28f540f4 RM |
32 | * any improvements or extensions that they make and grant Carnegie Mellon |
33 | * the rights to redistribute these changes. | |
34 | */ | |
35 | /* | |
eff75b8d | 36 | * (pre-GNU) HISTORY |
28f540f4 RM |
37 | * |
38 | * Revision 2.7 91/05/14 17:57:34 mrt | |
39 | * Correcting copyright | |
6d52618b | 40 | * |
28f540f4 RM |
41 | * Revision 2.6 91/02/14 14:20:26 mrt |
42 | * Added new Mach copyright | |
43 | * [91/02/13 12:41:21 mrt] | |
6d52618b | 44 | * |
28f540f4 RM |
45 | * Revision 2.5 90/11/05 14:37:33 rpd |
46 | * Added malloc_fork* code. | |
47 | * [90/11/02 rwd] | |
6d52618b | 48 | * |
28f540f4 RM |
49 | * Add spin_lock_t. |
50 | * [90/10/31 rwd] | |
6d52618b | 51 | * |
28f540f4 RM |
52 | * Revision 2.4 90/08/07 14:31:28 rpd |
53 | * Removed RCS keyword nonsense. | |
6d52618b | 54 | * |
28f540f4 RM |
55 | * Revision 2.3 90/06/02 15:14:00 rpd |
56 | * Converted to new IPC. | |
57 | * [90/03/20 20:56:57 rpd] | |
6d52618b | 58 | * |
28f540f4 RM |
59 | * Revision 2.2 89/12/08 19:53:59 rwd |
60 | * Removed conditionals. | |
61 | * [89/10/23 rwd] | |
6d52618b | 62 | * |
28f540f4 RM |
63 | * Revision 2.1 89/08/03 17:09:46 rwd |
64 | * Created. | |
6d52618b | 65 | * |
28f540f4 RM |
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 | \f | |
02eec644 MB |
80 | #include <assert.h> |
81 | ||
28f540f4 | 82 | #include <cthreads.h> |
28f540f4 | 83 | |
02eec644 | 84 | #define MCHECK |
28f540f4 RM |
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 | */ | |
02eec644 MB |
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 | ||
28f540f4 RM |
115 | typedef union header { |
116 | union header *next; | |
117 | struct free_list *fl; | |
118 | } *header_t; | |
119 | ||
02eec644 MB |
120 | #define HEADER_SIZE sizeof (union header) |
121 | #define HEADER_NEXT(h) ((h)->next) | |
122 | #define HEADER_FREE(h) ((h)->fl) | |
28f540f4 | 123 | #define MIN_SIZE 8 /* minimum block size */ |
02eec644 MB |
124 | #define LOG2_MIN_SIZE 3 |
125 | ||
126 | #endif /* MCHECK */ | |
28f540f4 RM |
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 */ | |
8a0746ae | 133 | #endif /* DEBUG */ |
28f540f4 RM |
134 | } *free_list_t; |
135 | ||
136 | /* | |
02eec644 MB |
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. | |
28f540f4 RM |
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 | |
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 | /* 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 | ||
171 | static void | |
ebe3b3eb | 172 | more_memory(int size, free_list_t fl) |
28f540f4 RM |
173 | { |
174 | register int amount; | |
175 | register int n; | |
176 | vm_address_t where; | |
177 | register 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; | |
02eec644 | 183 | /* We lose vm_page_size - n*size bytes here. */ |
28f540f4 RM |
184 | } else { |
185 | amount = size; | |
186 | n = 1; | |
187 | } | |
02eec644 MB |
188 | |
189 | r = vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE); | |
190 | assert_perror (r); | |
191 | ||
28f540f4 RM |
192 | h = (header_t) where; |
193 | do { | |
02eec644 MB |
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); | |
28f540f4 RM |
200 | } while (--n != 0); |
201 | } | |
202 | ||
203 | /* Declaration changed to standard one for GNU. */ | |
204 | void * | |
205 | malloc(size) | |
206 | register size_t size; | |
207 | { | |
208 | register int i, n; | |
209 | register free_list_t fl; | |
210 | register header_t h; | |
211 | ||
212 | if ((int) size < 0) /* sanity check */ | |
213 | return 0; | |
02eec644 | 214 | size += HEADER_SIZE; |
28f540f4 RM |
215 | /* |
216 | * Find smallest power-of-two block size | |
217 | * big enough to hold requested size plus header. | |
218 | */ | |
219 | i = 0; | |
220 | n = MIN_SIZE; | |
221 | while (n < size) { | |
222 | i += 1; | |
223 | n <<= 1; | |
224 | } | |
225 | ASSERT(i < NBUCKETS); | |
226 | fl = &malloc_free_list[i]; | |
227 | spin_lock(&fl->lock); | |
228 | h = fl->head; | |
229 | if (h == 0) { | |
230 | /* | |
231 | * Free list is empty; | |
232 | * allocate more blocks. | |
233 | */ | |
234 | more_memory(n, fl); | |
235 | h = fl->head; | |
236 | if (h == 0) { | |
237 | /* | |
238 | * Allocation failed. | |
239 | */ | |
240 | spin_unlock(&fl->lock); | |
241 | return 0; | |
242 | } | |
243 | } | |
244 | /* | |
245 | * Pop block from free list. | |
246 | */ | |
02eec644 MB |
247 | fl->head = HEADER_NEXT (h); |
248 | ||
249 | #ifdef MCHECK | |
250 | assert (HEADER_CHECK (h) == CHECK_FREE); | |
251 | HEADER_CHECK (h) = CHECK_BUSY; | |
252 | #endif | |
253 | ||
28f540f4 RM |
254 | #ifdef DEBUG |
255 | fl->in_use += 1; | |
8a0746ae | 256 | #endif /* DEBUG */ |
28f540f4 RM |
257 | spin_unlock(&fl->lock); |
258 | /* | |
259 | * Store free list pointer in block header | |
260 | * so we can figure out where it goes | |
261 | * at free() time. | |
262 | */ | |
02eec644 | 263 | HEADER_FREE (h) = fl; |
28f540f4 RM |
264 | /* |
265 | * Return pointer past the block header. | |
266 | */ | |
02eec644 | 267 | return ((char *) h) + HEADER_SIZE; |
28f540f4 RM |
268 | } |
269 | ||
270 | /* Declaration changed to standard one for GNU. */ | |
271 | void | |
272 | free(base) | |
273 | void *base; | |
274 | { | |
275 | register header_t h; | |
276 | register free_list_t fl; | |
277 | register int i; | |
278 | ||
279 | if (base == 0) | |
280 | return; | |
281 | /* | |
282 | * Find free list for block. | |
283 | */ | |
02eec644 MB |
284 | h = (header_t) (base - HEADER_SIZE); |
285 | ||
286 | #ifdef MCHECK | |
287 | assert (HEADER_CHECK (h) == CHECK_BUSY); | |
6d52618b | 288 | #endif |
02eec644 MB |
289 | |
290 | fl = HEADER_FREE (h); | |
28f540f4 RM |
291 | i = fl - malloc_free_list; |
292 | /* | |
293 | * Sanity checks. | |
294 | */ | |
295 | if (i < 0 || i >= NBUCKETS) { | |
296 | ASSERT(0 <= i && i < NBUCKETS); | |
297 | return; | |
298 | } | |
299 | if (fl != &malloc_free_list[i]) { | |
300 | ASSERT(fl == &malloc_free_list[i]); | |
301 | return; | |
302 | } | |
303 | /* | |
304 | * Push block on free list. | |
305 | */ | |
306 | spin_lock(&fl->lock); | |
02eec644 MB |
307 | HEADER_NEXT (h) = fl->head; |
308 | #ifdef MCHECK | |
309 | HEADER_CHECK (h) = CHECK_FREE; | |
6d52618b | 310 | #endif |
28f540f4 RM |
311 | fl->head = h; |
312 | #ifdef DEBUG | |
313 | fl->in_use -= 1; | |
8a0746ae | 314 | #endif /* DEBUG */ |
28f540f4 RM |
315 | spin_unlock(&fl->lock); |
316 | return; | |
317 | } | |
318 | ||
319 | /* Declaration changed to standard one for GNU. */ | |
320 | void * | |
321 | realloc(old_base, new_size) | |
322 | void *old_base; | |
323 | size_t new_size; | |
324 | { | |
325 | register header_t h; | |
326 | register free_list_t fl; | |
327 | register int i; | |
328 | unsigned int old_size; | |
329 | char *new_base; | |
330 | ||
331 | if (old_base == 0) | |
332 | return malloc (new_size); | |
333 | ||
334 | /* | |
335 | * Find size of old block. | |
336 | */ | |
02eec644 MB |
337 | h = (header_t) (old_base - HEADER_SIZE); |
338 | #ifdef MCHECK | |
339 | assert (HEADER_CHECK (h) == CHECK_BUSY); | |
340 | #endif | |
341 | fl = HEADER_FREE (h); | |
28f540f4 RM |
342 | i = fl - malloc_free_list; |
343 | /* | |
344 | * Sanity checks. | |
345 | */ | |
346 | if (i < 0 || i >= NBUCKETS) { | |
347 | ASSERT(0 <= i && i < NBUCKETS); | |
348 | return 0; | |
349 | } | |
350 | if (fl != &malloc_free_list[i]) { | |
351 | ASSERT(fl == &malloc_free_list[i]); | |
352 | return 0; | |
353 | } | |
354 | /* | |
02eec644 MB |
355 | * Free list with index i contains blocks of size |
356 | * 2 ^ (i + * LOG2_MIN_SIZE) including header. | |
28f540f4 | 357 | */ |
02eec644 MB |
358 | old_size = (1 << (i + LOG2_MIN_SIZE)) - HEADER_SIZE; |
359 | ||
360 | if (new_size <= old_size | |
361 | && new_size > (((old_size + HEADER_SIZE) >> 1) - HEADER_SIZE)) | |
362 | /* The new size still fits in the same block, and wouldn't fit in | |
363 | the next smaller block! */ | |
364 | return old_base; | |
365 | ||
28f540f4 RM |
366 | /* |
367 | * Allocate new block, copy old bytes, and free old block. | |
368 | */ | |
369 | new_base = malloc(new_size); | |
02eec644 | 370 | if (new_base) |
9596d0dd UD |
371 | memcpy (new_base, old_base, |
372 | (int) (old_size < new_size ? old_size : new_size)); | |
02eec644 MB |
373 | |
374 | if (new_base || new_size == 0) | |
375 | /* Free OLD_BASE, but only if the malloc didn't fail. */ | |
376 | free (old_base); | |
377 | ||
28f540f4 RM |
378 | return new_base; |
379 | } | |
380 | ||
381 | #ifdef DEBUG | |
382 | void | |
383 | print_malloc_free_list() | |
384 | { | |
385 | register int i, size; | |
386 | register free_list_t fl; | |
387 | register int n; | |
388 | register header_t h; | |
389 | int total_used = 0; | |
390 | int total_free = 0; | |
391 | ||
392 | fprintf(stderr, " Size In Use Free Total\n"); | |
393 | for (i = 0, size = MIN_SIZE, fl = malloc_free_list; | |
394 | i < NBUCKETS; | |
395 | i += 1, size <<= 1, fl += 1) { | |
396 | spin_lock(&fl->lock); | |
397 | if (fl->in_use != 0 || fl->head != 0) { | |
398 | total_used += fl->in_use * size; | |
02eec644 | 399 | for (n = 0, h = fl->head; h != 0; h = HEADER_NEXT (h), n += 1) |
28f540f4 RM |
400 | ; |
401 | total_free += n * size; | |
402 | fprintf(stderr, "%10d %10d %10d %10d\n", | |
403 | size, fl->in_use, n, fl->in_use + n); | |
404 | } | |
405 | spin_unlock(&fl->lock); | |
406 | } | |
407 | fprintf(stderr, " all sizes %10d %10d %10d\n", | |
408 | total_used, total_free, total_used + total_free); | |
409 | } | |
8a0746ae | 410 | #endif /* DEBUG */ |
28f540f4 | 411 | |
6d52618b | 412 | static void |
ebe3b3eb | 413 | malloc_fork_prepare(void) |
28f540f4 RM |
414 | /* |
415 | * Prepare the malloc module for a fork by insuring that no thread is in a | |
416 | * malloc critical section. | |
417 | */ | |
418 | { | |
419 | register int i; | |
6d52618b | 420 | |
28f540f4 RM |
421 | for (i = 0; i < NBUCKETS; i++) { |
422 | spin_lock(&malloc_free_list[i].lock); | |
423 | } | |
424 | } | |
425 | ||
6d52618b | 426 | static void |
ebe3b3eb | 427 | malloc_fork_parent(void) |
28f540f4 RM |
428 | /* |
429 | * Called in the parent process after a fork() to resume normal operation. | |
430 | */ | |
431 | { | |
432 | register int i; | |
433 | ||
434 | for (i = NBUCKETS-1; i >= 0; i--) { | |
435 | spin_unlock(&malloc_free_list[i].lock); | |
436 | } | |
437 | } | |
438 | ||
ebe3b3eb TBB |
439 | static void |
440 | malloc_fork_child(void) | |
28f540f4 RM |
441 | /* |
442 | * Called in the child process after a fork() to resume normal operation. | |
443 | */ | |
444 | { | |
445 | register int i; | |
446 | ||
447 | for (i = NBUCKETS-1; i >= 0; i--) { | |
448 | spin_unlock(&malloc_free_list[i].lock); | |
449 | } | |
450 | } | |
451 | \f | |
452 | ||
453 | text_set_element (_hurd_fork_prepare_hook, malloc_fork_prepare); | |
454 | text_set_element (_hurd_fork_parent_hook, malloc_fork_parent); | |
455 | text_set_element (_hurd_fork_child_hook, malloc_fork_child); | |
456 | text_set_element (_hurd_preinit_hook, malloc_init); |