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 { |
99 | long ; |
100 | union { |
101 | struct header *; |
102 | struct free_list *; |
103 | } ; |
104 | } *; |
105 | |
106 | #define sizeof (struct header) |
107 | #define (h) ((h)->u.next) |
108 | #define (h) ((h)->u.fl) |
109 | #define (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(size: 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 (size: 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(size: new_size); |
361 | if (new_base) |
362 | memcpy (dest: new_base, src: old_base, |
363 | n: (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 (base: 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); |
445 | |