]>
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 | 173 | { |
2e09a79a JM |
174 | int amount; |
175 | int n; | |
28f540f4 | 176 | vm_address_t where; |
2e09a79a | 177 | header_t h; |
28f540f4 RM |
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 * | |
9dd346ff | 205 | malloc (size_t size) |
28f540f4 | 206 | { |
2e09a79a JM |
207 | int i, n; |
208 | free_list_t fl; | |
209 | header_t h; | |
28f540f4 RM |
210 | |
211 | if ((int) size < 0) /* sanity check */ | |
212 | return 0; | |
02eec644 | 213 | size += HEADER_SIZE; |
28f540f4 RM |
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 | */ | |
02eec644 MB |
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 | ||
28f540f4 RM |
253 | #ifdef DEBUG |
254 | fl->in_use += 1; | |
8a0746ae | 255 | #endif /* DEBUG */ |
28f540f4 RM |
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 | */ | |
02eec644 | 262 | HEADER_FREE (h) = fl; |
28f540f4 RM |
263 | /* |
264 | * Return pointer past the block header. | |
265 | */ | |
02eec644 | 266 | return ((char *) h) + HEADER_SIZE; |
28f540f4 RM |
267 | } |
268 | ||
269 | /* Declaration changed to standard one for GNU. */ | |
270 | void | |
9dd346ff | 271 | free (void *base) |
28f540f4 | 272 | { |
2e09a79a JM |
273 | header_t h; |
274 | free_list_t fl; | |
275 | int i; | |
28f540f4 RM |
276 | |
277 | if (base == 0) | |
278 | return; | |
279 | /* | |
280 | * Find free list for block. | |
281 | */ | |
02eec644 MB |
282 | h = (header_t) (base - HEADER_SIZE); |
283 | ||
284 | #ifdef MCHECK | |
285 | assert (HEADER_CHECK (h) == CHECK_BUSY); | |
6d52618b | 286 | #endif |
02eec644 MB |
287 | |
288 | fl = HEADER_FREE (h); | |
28f540f4 RM |
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); | |
02eec644 MB |
305 | HEADER_NEXT (h) = fl->head; |
306 | #ifdef MCHECK | |
307 | HEADER_CHECK (h) = CHECK_FREE; | |
6d52618b | 308 | #endif |
28f540f4 RM |
309 | fl->head = h; |
310 | #ifdef DEBUG | |
311 | fl->in_use -= 1; | |
8a0746ae | 312 | #endif /* DEBUG */ |
28f540f4 RM |
313 | spin_unlock(&fl->lock); |
314 | return; | |
315 | } | |
316 | ||
317 | /* Declaration changed to standard one for GNU. */ | |
318 | void * | |
9dd346ff | 319 | realloc (void *old_base, size_t new_size) |
28f540f4 | 320 | { |
2e09a79a JM |
321 | header_t h; |
322 | free_list_t fl; | |
323 | int i; | |
28f540f4 RM |
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 | */ | |
02eec644 MB |
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); | |
28f540f4 RM |
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 | /* | |
02eec644 MB |
351 | * Free list with index i contains blocks of size |
352 | * 2 ^ (i + * LOG2_MIN_SIZE) including header. | |
28f540f4 | 353 | */ |
02eec644 MB |
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 | ||
28f540f4 RM |
362 | /* |
363 | * Allocate new block, copy old bytes, and free old block. | |
364 | */ | |
365 | new_base = malloc(new_size); | |
02eec644 | 366 | if (new_base) |
9596d0dd UD |
367 | memcpy (new_base, old_base, |
368 | (int) (old_size < new_size ? old_size : new_size)); | |
02eec644 MB |
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 | ||
28f540f4 RM |
374 | return new_base; |
375 | } | |
376 | ||
377 | #ifdef DEBUG | |
378 | void | |
60d2f8f3 | 379 | print_malloc_free_list (void) |
28f540f4 | 380 | { |
2e09a79a JM |
381 | int i, size; |
382 | free_list_t fl; | |
383 | int n; | |
384 | header_t h; | |
28f540f4 RM |
385 | int total_used = 0; |
386 | int total_free = 0; | |
387 | ||
388 | fprintf(stderr, " Size In Use Free Total\n"); | |
350635a5 | 389 | for (i = 0, size = MIN_SIZE, fl = malloc_free_list; |
28f540f4 RM |
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; | |
02eec644 | 395 | for (n = 0, h = fl->head; h != 0; h = HEADER_NEXT (h), n += 1) |
28f540f4 RM |
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); | |
350635a5 OB |
402 | } |
403 | fprintf(stderr, " all sizes %10d %10d %10d\n", | |
28f540f4 RM |
404 | total_used, total_free, total_used + total_free); |
405 | } | |
8a0746ae | 406 | #endif /* DEBUG */ |
28f540f4 | 407 | |
e67f54ab ST |
408 | void |
409 | _hurd_malloc_fork_prepare(void) | |
28f540f4 RM |
410 | /* |
411 | * Prepare the malloc module for a fork by insuring that no thread is in a | |
412 | * malloc critical section. | |
413 | */ | |
414 | { | |
2e09a79a | 415 | int i; |
6d52618b | 416 | |
28f540f4 RM |
417 | for (i = 0; i < NBUCKETS; i++) { |
418 | spin_lock(&malloc_free_list[i].lock); | |
419 | } | |
420 | } | |
421 | ||
e67f54ab ST |
422 | void |
423 | _hurd_malloc_fork_parent(void) | |
28f540f4 RM |
424 | /* |
425 | * Called in the parent process after a fork() to resume normal operation. | |
426 | */ | |
427 | { | |
2e09a79a | 428 | int i; |
28f540f4 RM |
429 | |
430 | for (i = NBUCKETS-1; i >= 0; i--) { | |
431 | spin_unlock(&malloc_free_list[i].lock); | |
432 | } | |
433 | } | |
434 | ||
e67f54ab ST |
435 | void |
436 | _hurd_malloc_fork_child(void) | |
28f540f4 RM |
437 | /* |
438 | * Called in the child process after a fork() to resume normal operation. | |
439 | */ | |
440 | { | |
2e09a79a | 441 | int i; |
28f540f4 RM |
442 | |
443 | for (i = NBUCKETS-1; i >= 0; i--) { | |
444 | spin_unlock(&malloc_free_list[i].lock); | |
445 | } | |
446 | } | |
447 | \f | |
448 | ||
28f540f4 | 449 | text_set_element (_hurd_preinit_hook, malloc_init); |