]>
Commit | Line | Data |
---|---|---|
28f540f4 RM |
1 | #include <stdlib.h> |
2 | #include <string.h> | |
ae49f218 | 3 | #include "set-hooks.h" |
28f540f4 | 4 | |
28f540f4 RM |
5 | #include "hurdmalloc.h" /* XXX see that file */ |
6 | ||
7 | #include <mach.h> | |
9446e02b | 8 | #include <mach/spin-lock.h> |
28f540f4 RM |
9 | #define vm_allocate __vm_allocate |
10 | #define vm_page_size __vm_page_size | |
11 | ||
8a0746ae | 12 | /* |
28f540f4 RM |
13 | * Mach Operating System |
14 | * Copyright (c) 1991,1990,1989 Carnegie Mellon University | |
15 | * All Rights Reserved. | |
8a0746ae | 16 | * |
28f540f4 RM |
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. | |
8a0746ae | 22 | * |
28f540f4 RM |
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. | |
8a0746ae | 26 | * |
28f540f4 | 27 | * Carnegie Mellon requests users of this software to return to |
8a0746ae | 28 | * |
28f540f4 RM |
29 | * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU |
30 | * School of Computer Science | |
31 | * Carnegie Mellon University | |
32 | * Pittsburgh PA 15213-3890 | |
8a0746ae | 33 | * |
28f540f4 RM |
34 | * any improvements or extensions that they make and grant Carnegie Mellon |
35 | * the rights to redistribute these changes. | |
36 | */ | |
37 | /* | |
eff75b8d | 38 | * (pre-GNU) HISTORY |
28f540f4 RM |
39 | * |
40 | * Revision 2.7 91/05/14 17:57:34 mrt | |
41 | * Correcting copyright | |
6d52618b | 42 | * |
28f540f4 RM |
43 | * Revision 2.6 91/02/14 14:20:26 mrt |
44 | * Added new Mach copyright | |
45 | * [91/02/13 12:41:21 mrt] | |
6d52618b | 46 | * |
28f540f4 RM |
47 | * Revision 2.5 90/11/05 14:37:33 rpd |
48 | * Added malloc_fork* code. | |
49 | * [90/11/02 rwd] | |
6d52618b | 50 | * |
28f540f4 RM |
51 | * Add spin_lock_t. |
52 | * [90/10/31 rwd] | |
6d52618b | 53 | * |
28f540f4 RM |
54 | * Revision 2.4 90/08/07 14:31:28 rpd |
55 | * Removed RCS keyword nonsense. | |
6d52618b | 56 | * |
28f540f4 RM |
57 | * Revision 2.3 90/06/02 15:14:00 rpd |
58 | * Converted to new IPC. | |
59 | * [90/03/20 20:56:57 rpd] | |
6d52618b | 60 | * |
28f540f4 RM |
61 | * Revision 2.2 89/12/08 19:53:59 rwd |
62 | * Removed conditionals. | |
63 | * [89/10/23 rwd] | |
6d52618b | 64 | * |
28f540f4 RM |
65 | * Revision 2.1 89/08/03 17:09:46 rwd |
66 | * Created. | |
6d52618b | 67 | * |
28f540f4 RM |
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 | \f | |
02eec644 MB |
82 | #include <assert.h> |
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 | ||
ae49f218 | 152 | static void attribute_used_retain |
28f540f4 RM |
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 | } | |
28f540f4 RM |
164 | } |
165 | ||
166 | static void | |
ebe3b3eb | 167 | more_memory(int size, free_list_t fl) |
28f540f4 | 168 | { |
2e09a79a JM |
169 | int amount; |
170 | int n; | |
28f540f4 | 171 | vm_address_t where; |
2e09a79a | 172 | header_t h; |
28f540f4 RM |
173 | kern_return_t r; |
174 | ||
175 | if (size <= vm_page_size) { | |
176 | amount = vm_page_size; | |
177 | n = vm_page_size / size; | |
02eec644 | 178 | /* We lose vm_page_size - n*size bytes here. */ |
28f540f4 RM |
179 | } else { |
180 | amount = size; | |
181 | n = 1; | |
182 | } | |
02eec644 MB |
183 | |
184 | r = vm_allocate(mach_task_self(), &where, (vm_size_t) amount, TRUE); | |
185 | assert_perror (r); | |
186 | ||
28f540f4 RM |
187 | h = (header_t) where; |
188 | do { | |
02eec644 MB |
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); | |
28f540f4 RM |
195 | } while (--n != 0); |
196 | } | |
197 | ||
198 | /* Declaration changed to standard one for GNU. */ | |
199 | void * | |
9dd346ff | 200 | malloc (size_t size) |
28f540f4 | 201 | { |
2e09a79a JM |
202 | int i, n; |
203 | free_list_t fl; | |
204 | header_t h; | |
28f540f4 RM |
205 | |
206 | if ((int) size < 0) /* sanity check */ | |
207 | return 0; | |
02eec644 | 208 | size += HEADER_SIZE; |
28f540f4 RM |
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 | } | |
9446e02b | 219 | assert(i < NBUCKETS); |
28f540f4 RM |
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 | */ | |
02eec644 MB |
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 | ||
28f540f4 RM |
248 | #ifdef DEBUG |
249 | fl->in_use += 1; | |
8a0746ae | 250 | #endif /* DEBUG */ |
28f540f4 RM |
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 | */ | |
02eec644 | 257 | HEADER_FREE (h) = fl; |
28f540f4 RM |
258 | /* |
259 | * Return pointer past the block header. | |
260 | */ | |
02eec644 | 261 | return ((char *) h) + HEADER_SIZE; |
28f540f4 RM |
262 | } |
263 | ||
264 | /* Declaration changed to standard one for GNU. */ | |
265 | void | |
9dd346ff | 266 | free (void *base) |
28f540f4 | 267 | { |
2e09a79a JM |
268 | header_t h; |
269 | free_list_t fl; | |
270 | int i; | |
28f540f4 RM |
271 | |
272 | if (base == 0) | |
273 | return; | |
274 | /* | |
275 | * Find free list for block. | |
276 | */ | |
02eec644 MB |
277 | h = (header_t) (base - HEADER_SIZE); |
278 | ||
279 | #ifdef MCHECK | |
280 | assert (HEADER_CHECK (h) == CHECK_BUSY); | |
6d52618b | 281 | #endif |
02eec644 MB |
282 | |
283 | fl = HEADER_FREE (h); | |
28f540f4 RM |
284 | i = fl - malloc_free_list; |
285 | /* | |
286 | * Sanity checks. | |
287 | */ | |
288 | if (i < 0 || i >= NBUCKETS) { | |
9446e02b | 289 | assert(0 <= i && i < NBUCKETS); |
28f540f4 RM |
290 | return; |
291 | } | |
292 | if (fl != &malloc_free_list[i]) { | |
9446e02b | 293 | assert(fl == &malloc_free_list[i]); |
28f540f4 RM |
294 | return; |
295 | } | |
296 | /* | |
297 | * Push block on free list. | |
298 | */ | |
299 | spin_lock(&fl->lock); | |
02eec644 MB |
300 | HEADER_NEXT (h) = fl->head; |
301 | #ifdef MCHECK | |
302 | HEADER_CHECK (h) = CHECK_FREE; | |
6d52618b | 303 | #endif |
28f540f4 RM |
304 | fl->head = h; |
305 | #ifdef DEBUG | |
306 | fl->in_use -= 1; | |
8a0746ae | 307 | #endif /* DEBUG */ |
28f540f4 RM |
308 | spin_unlock(&fl->lock); |
309 | return; | |
310 | } | |
311 | ||
312 | /* Declaration changed to standard one for GNU. */ | |
313 | void * | |
9dd346ff | 314 | realloc (void *old_base, size_t new_size) |
28f540f4 | 315 | { |
2e09a79a JM |
316 | header_t h; |
317 | free_list_t fl; | |
318 | int i; | |
28f540f4 RM |
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 | */ | |
02eec644 MB |
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); | |
28f540f4 RM |
333 | i = fl - malloc_free_list; |
334 | /* | |
335 | * Sanity checks. | |
336 | */ | |
337 | if (i < 0 || i >= NBUCKETS) { | |
9446e02b | 338 | assert(0 <= i && i < NBUCKETS); |
28f540f4 RM |
339 | return 0; |
340 | } | |
341 | if (fl != &malloc_free_list[i]) { | |
9446e02b | 342 | assert(fl == &malloc_free_list[i]); |
28f540f4 RM |
343 | return 0; |
344 | } | |
345 | /* | |
02eec644 MB |
346 | * Free list with index i contains blocks of size |
347 | * 2 ^ (i + * LOG2_MIN_SIZE) including header. | |
28f540f4 | 348 | */ |
02eec644 MB |
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 | ||
28f540f4 RM |
357 | /* |
358 | * Allocate new block, copy old bytes, and free old block. | |
359 | */ | |
360 | new_base = malloc(new_size); | |
02eec644 | 361 | if (new_base) |
9596d0dd UD |
362 | memcpy (new_base, old_base, |
363 | (int) (old_size < new_size ? old_size : new_size)); | |
02eec644 MB |
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 | ||
28f540f4 RM |
369 | return new_base; |
370 | } | |
371 | ||
372 | #ifdef DEBUG | |
373 | void | |
60d2f8f3 | 374 | print_malloc_free_list (void) |
28f540f4 | 375 | { |
2e09a79a JM |
376 | int i, size; |
377 | free_list_t fl; | |
378 | int n; | |
379 | header_t h; | |
28f540f4 RM |
380 | int total_used = 0; |
381 | int total_free = 0; | |
382 | ||
383 | fprintf(stderr, " Size In Use Free Total\n"); | |
350635a5 | 384 | for (i = 0, size = MIN_SIZE, fl = malloc_free_list; |
28f540f4 RM |
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; | |
02eec644 | 390 | for (n = 0, h = fl->head; h != 0; h = HEADER_NEXT (h), n += 1) |
28f540f4 RM |
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); | |
350635a5 OB |
397 | } |
398 | fprintf(stderr, " all sizes %10d %10d %10d\n", | |
28f540f4 RM |
399 | total_used, total_free, total_used + total_free); |
400 | } | |
8a0746ae | 401 | #endif /* DEBUG */ |
28f540f4 | 402 | |
e67f54ab ST |
403 | void |
404 | _hurd_malloc_fork_prepare(void) | |
28f540f4 RM |
405 | /* |
406 | * Prepare the malloc module for a fork by insuring that no thread is in a | |
407 | * malloc critical section. | |
408 | */ | |
409 | { | |
2e09a79a | 410 | int i; |
6d52618b | 411 | |
28f540f4 RM |
412 | for (i = 0; i < NBUCKETS; i++) { |
413 | spin_lock(&malloc_free_list[i].lock); | |
414 | } | |
415 | } | |
416 | ||
e67f54ab ST |
417 | void |
418 | _hurd_malloc_fork_parent(void) | |
28f540f4 RM |
419 | /* |
420 | * Called in the parent process after a fork() to resume normal operation. | |
421 | */ | |
422 | { | |
2e09a79a | 423 | int i; |
28f540f4 RM |
424 | |
425 | for (i = NBUCKETS-1; i >= 0; i--) { | |
426 | spin_unlock(&malloc_free_list[i].lock); | |
427 | } | |
428 | } | |
429 | ||
e67f54ab ST |
430 | void |
431 | _hurd_malloc_fork_child(void) | |
28f540f4 RM |
432 | /* |
433 | * Called in the child process after a fork() to resume normal operation. | |
434 | */ | |
435 | { | |
2e09a79a | 436 | int i; |
28f540f4 RM |
437 | |
438 | for (i = NBUCKETS-1; i >= 0; i--) { | |
439 | spin_unlock(&malloc_free_list[i].lock); | |
440 | } | |
441 | } | |
442 | \f | |
443 | ||
ae49f218 | 444 | SET_RELHOOK (_hurd_preinit_hook, malloc_init); |