]>
Commit | Line | Data |
---|---|---|
1c79356b A |
1 | /* |
2 | * Copyright (c) 2000 Apple Computer, Inc. All rights reserved. | |
3 | * | |
4 | * @APPLE_LICENSE_HEADER_START@ | |
5 | * | |
de355530 A |
6 | * The contents of this file constitute Original Code as defined in and |
7 | * are subject to the Apple Public Source License Version 1.1 (the | |
8 | * "License"). You may not use this file except in compliance with the | |
9 | * License. Please obtain a copy of the License at | |
10 | * http://www.apple.com/publicsource and read it before using this file. | |
1c79356b | 11 | * |
de355530 A |
12 | * This Original Code and all software distributed under the License are |
13 | * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER | |
1c79356b A |
14 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, |
15 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, | |
de355530 A |
16 | * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the |
17 | * License for the specific language governing rights and limitations | |
18 | * under the License. | |
1c79356b A |
19 | * |
20 | * @APPLE_LICENSE_HEADER_END@ | |
21 | */ | |
de355530 A |
22 | #include <vm/vm_kern.h> |
23 | #include <kern/queue.h> | |
1c79356b A |
24 | #include <string.h> |
25 | ||
de355530 A |
26 | #include <libsa/malloc.h> |
27 | ||
28 | #undef CLIENT_DEBUG | |
29 | ||
30 | ||
31 | /********************************************************************* | |
32 | * I'm not sure this is really necessary.... | |
33 | *********************************************************************/ | |
34 | static inline size_t round_to_long(size_t size) { | |
35 | return (size + sizeof(long int)) & ~(sizeof(long int) - 1); | |
36 | } | |
37 | ||
38 | ||
39 | typedef struct queue_entry queue_entry; | |
40 | ||
41 | /********************************************************************* | |
42 | * Structure for an allocation region. Each one is created using | |
43 | * kmem_alloc(), and the whole list of these is destroyed by calling | |
44 | * malloc_reset(). Client blocks are allocated from a linked list of these | |
45 | * regions, on a first-fit basis, and are never freed. | |
46 | *********************************************************************/ | |
47 | typedef struct malloc_region { | |
48 | queue_entry links; // Uses queue.h for linked list | |
49 | vm_size_t region_size; // total size w/ this bookeeping info | |
50 | ||
51 | queue_entry block_list; // list of allocated blocks; uses queue.h | |
52 | ||
53 | vm_size_t free_size; // size of unused area | |
54 | void * free_address; // points at the unused area | |
55 | ||
56 | char buffer[0]; // beginning of useable area | |
57 | } malloc_region; | |
1c79356b A |
58 | |
59 | ||
60 | /********************************************************************* | |
61 | * Structure for a client memory block. Contains linked-list pointers, | |
62 | * a size field giving the TOTAL size of the block, including this | |
63 | * header, and the address of the client's block. The client block | |
64 | * field is guaranteed to lie on a 16-byte boundary. | |
65 | *********************************************************************/ | |
66 | typedef struct malloc_block { | |
de355530 A |
67 | queue_entry links; // Uses queue.h for linked list |
68 | malloc_region * region; | |
69 | #ifdef CLIENT_DEBUG | |
70 | size_t request_size; | |
71 | #endif /* CLIENT_DEBUG */ | |
72 | size_t block_size; // total size w/ all bookeeping info | |
73 | ||
74 | // the client's memory block | |
75 | char buffer[0] __attribute__((aligned(16))); | |
d7e50217 | 76 | } malloc_block; |
1c79356b | 77 | |
1c79356b | 78 | |
de355530 A |
79 | /********************************************************************* |
80 | * Private functions. | |
81 | * | |
82 | * malloc_create_region() | |
83 | * size - The size in bytes of the region. This is rounded up | |
84 | * to a multiple of the VM page size. | |
85 | * Returns a pointer to the new region. | |
86 | * | |
87 | * malloc_free_region() | |
88 | * region - The region to free. | |
89 | * Returns whatever vm_deallocate() returns. | |
90 | * | |
91 | * malloc_create_block_in_region() | |
92 | * region - The region to alloate a block from. | |
93 | * size - The total size, including the header, of the block to | |
94 | * allocate. | |
95 | * Returns a pointer to the block, or NULL on failure. | |
96 | * | |
97 | * malloc_find_block() | |
98 | * address - The address of the client buffer to find a block for. | |
99 | * block (out) - The block header for the address. | |
100 | * region (out) - The region the block was found in, or NULL. | |
101 | *********************************************************************/ | |
102 | static malloc_region * malloc_create_region(vm_size_t size); | |
103 | static kern_return_t malloc_free_region(malloc_region * region); | |
104 | static malloc_block * malloc_create_block_in_region( | |
105 | malloc_region * region, | |
106 | size_t size); | |
107 | static void malloc_find_block( | |
108 | void * address, | |
109 | malloc_block ** block, | |
110 | malloc_region ** region); | |
111 | static void malloc_get_free_block( | |
112 | size_t size, | |
113 | malloc_block ** block, | |
114 | malloc_region ** region); | |
115 | ||
116 | ||
117 | /********************************************************************* | |
118 | * Pointers to the linked list of VM-allocated regions, and a high | |
119 | * water mark used in testing/debugging. | |
120 | *********************************************************************/ | |
121 | static queue_entry malloc_region_list = { | |
122 | &malloc_region_list, // the "next" field | |
123 | &malloc_region_list // the "prev" field | |
124 | }; | |
1c79356b | 125 | |
de355530 A |
126 | static queue_entry sorted_free_block_list = { |
127 | &sorted_free_block_list, | |
128 | &sorted_free_block_list | |
129 | }; | |
130 | ||
131 | #ifdef CLIENT_DEBUG | |
132 | static size_t malloc_hiwater_mark = 0; | |
133 | static long int num_regions = 0; | |
134 | ||
135 | static size_t current_block_total = 0; | |
136 | static double peak_usage = 0.0; | |
137 | static double min_usage = 100.0; | |
138 | #endif /* CLIENT_DEBUG */ | |
139 | ||
140 | ||
141 | /********************************************************************* | |
142 | * malloc() | |
143 | *********************************************************************/ | |
1c79356b A |
144 | __private_extern__ |
145 | void * malloc(size_t size) { | |
de355530 A |
146 | size_t need_size; |
147 | malloc_region * cur_region = NULL; | |
148 | malloc_region * use_region = NULL; | |
149 | malloc_block * client_block = NULL; | |
150 | void * client_buffer = NULL; | |
151 | ||
152 | /* Add the size of the block header to the request size. | |
153 | */ | |
154 | need_size = round_to_long(size + sizeof(malloc_block)); | |
155 | ||
156 | ||
157 | /* See if there's a previously-freed block that we can reuse. | |
158 | */ | |
159 | malloc_get_free_block(need_size, | |
160 | &client_block, &use_region); | |
1c79356b | 161 | |
de355530 A |
162 | |
163 | /* If we found a free block that we can reuse, then reuse it. | |
164 | */ | |
165 | if (client_block != NULL) { | |
166 | ||
167 | /* Remove the found block from the list of free blocks | |
168 | * and tack it onto the list of allocated blocks. | |
169 | */ | |
170 | queue_remove(&sorted_free_block_list, client_block, malloc_block *, links); | |
171 | queue_enter(&use_region->block_list, client_block, malloc_block *, links); | |
172 | ||
173 | client_buffer = client_block->buffer; | |
174 | // Don't return here! There's bookkeeping done below. | |
175 | ||
176 | } else { | |
177 | ||
178 | /* Didn't find a freed block to reuse. */ | |
179 | ||
180 | /* Look for a region with enough unused space to carve out a new block. | |
181 | */ | |
182 | queue_iterate(&malloc_region_list, cur_region, malloc_region *, links) { | |
183 | if (use_region == NULL && cur_region->free_size >= need_size) { | |
184 | use_region = cur_region; | |
185 | break; | |
186 | } | |
187 | } | |
188 | ||
189 | ||
190 | /* If we haven't found a region with room, create a new one and | |
191 | * put it at the end of the list of regions. | |
192 | */ | |
193 | if (use_region == NULL) { | |
194 | use_region = malloc_create_region(need_size); | |
195 | if (use_region == NULL) { | |
196 | return NULL; | |
197 | // FIXME: panic? | |
198 | } | |
199 | } | |
200 | ||
201 | /* Create a new block in the found/created region. | |
202 | */ | |
203 | client_block = malloc_create_block_in_region(use_region, need_size); | |
204 | if (client_block != NULL) { | |
205 | client_buffer = client_block->buffer; | |
206 | // Don't return here! There's bookkeeping done below. | |
207 | } | |
208 | } | |
209 | ||
210 | #ifdef CLIENT_DEBUG | |
211 | if (client_block != NULL) { | |
212 | size_t region_usage = malloc_region_usage(); | |
213 | double current_usage; | |
214 | ||
215 | current_block_total += client_block->block_size; | |
216 | if (region_usage > 0) { | |
217 | current_usage = (double)current_block_total / (double)malloc_region_usage(); | |
218 | if (current_usage > peak_usage) { | |
219 | peak_usage = current_usage; | |
220 | } | |
221 | ||
222 | if (current_usage < min_usage) { | |
223 | min_usage = current_usage; | |
224 | } | |
225 | } | |
226 | ||
227 | client_block->request_size = size; | |
228 | } | |
229 | #endif /* CLIENT_DEBUG */ | |
230 | ||
231 | return client_buffer; | |
1c79356b A |
232 | |
233 | } /* malloc() */ | |
234 | ||
235 | ||
236 | /********************************************************************* | |
237 | * free() | |
238 | * | |
de355530 A |
239 | * Moves a block from the allocated list to the free list. Neither |
240 | * list is kept sorted! | |
1c79356b A |
241 | *********************************************************************/ |
242 | __private_extern__ | |
243 | void free(void * address) { | |
de355530 A |
244 | malloc_region * found_region = NULL; |
245 | malloc_block * found_block = NULL; | |
246 | malloc_block * cur_block = NULL; | |
1c79356b | 247 | |
de355530 A |
248 | /* Find the block and region for the given address. |
249 | */ | |
250 | malloc_find_block(address, &found_block, &found_region); | |
1c79356b | 251 | |
de355530 A |
252 | if (found_block == NULL) { |
253 | return; | |
254 | // FIXME: panic? | |
255 | } | |
1c79356b | 256 | |
1c79356b | 257 | |
de355530 A |
258 | /* Remove the found block from the list of allocated blocks |
259 | * and tack it onto the list of free blocks. | |
260 | */ | |
261 | queue_remove(&found_region->block_list, found_block, malloc_block *, links); | |
1c79356b | 262 | |
de355530 A |
263 | found_block->links.next = NULL; |
264 | queue_iterate(&sorted_free_block_list, cur_block, malloc_block *, links) { | |
265 | if (cur_block->block_size > found_block->block_size) { | |
266 | queue_insert_before(&sorted_free_block_list, found_block, cur_block, | |
267 | malloc_block *, links); | |
268 | break; | |
269 | } | |
270 | } | |
1c79356b | 271 | |
1c79356b | 272 | |
de355530 A |
273 | /* If the "next" link is still NULL, then either the list is empty or the |
274 | * freed block has to go on the end, so just tack it on. | |
275 | */ | |
276 | if (found_block->links.next == NULL) { | |
277 | queue_enter(&sorted_free_block_list, found_block, malloc_block *, links); | |
278 | } | |
1c79356b | 279 | |
de355530 A |
280 | |
281 | #ifdef CLIENT_DEBUG | |
282 | current_block_total -= found_block->block_size; | |
283 | #endif /* CLIENT_DEBUG */ | |
284 | ||
285 | return; | |
286 | ||
287 | } /* free() */ | |
d7e50217 | 288 | |
1c79356b A |
289 | |
290 | /********************************************************************* | |
291 | * malloc_reset() | |
292 | * | |
293 | * Walks through the list of VM-allocated regions, destroying them | |
294 | * all. Any subsequent access by clients to allocated data will cause | |
295 | * a segmentation fault. | |
296 | *********************************************************************/ | |
297 | __private_extern__ | |
298 | void malloc_reset(void) { | |
de355530 A |
299 | malloc_region * cur_region; |
300 | ||
301 | while (! queue_empty(&malloc_region_list)) { | |
302 | kern_return_t kern_result; | |
303 | queue_remove_first(&malloc_region_list, cur_region, | |
304 | malloc_region *, links); | |
305 | kern_result = malloc_free_region(cur_region); | |
306 | if (kern_result != KERN_SUCCESS) { | |
307 | // what sort of error checking can we even do here? | |
308 | // printf("malloc_free_region() failed.\n"); | |
309 | // panic(); | |
310 | } | |
311 | } | |
312 | ||
1c79356b A |
313 | return; |
314 | ||
315 | } /* malloc_reset() */ | |
316 | ||
317 | ||
318 | /********************************************************************* | |
319 | * realloc() | |
320 | * | |
321 | * This function simply allocates a new block and copies the existing | |
322 | * data into it. Nothing too clever here, as cleanup and efficient | |
323 | * memory usage are not important in this allocator package. | |
324 | *********************************************************************/ | |
325 | __private_extern__ | |
326 | void * realloc(void * address, size_t new_client_size) { | |
de355530 A |
327 | malloc_region * found_region = NULL; |
328 | malloc_block * found_block = NULL; | |
1c79356b | 329 | void * new_address; |
de355530 A |
330 | size_t new_block_size; |
331 | size_t copy_bytecount; | |
332 | ||
333 | ||
334 | malloc_find_block(address, &found_block, &found_region); | |
335 | ||
336 | ||
337 | /* If we couldn't find the requested block, | |
338 | * the caller is in error so return NULL. | |
339 | */ | |
340 | if (found_block == NULL) { | |
341 | // printf("realloc() called with invalid block.\n"); | |
342 | return NULL; | |
343 | // FIXME: panic? | |
344 | } | |
345 | ||
346 | ||
347 | /* Figure out how much memory is actually needed. | |
348 | */ | |
349 | new_block_size = new_client_size + sizeof(malloc_block); | |
350 | ||
351 | ||
352 | /* If the new size is <= the current size, don't bother. | |
353 | */ | |
354 | if (new_block_size <= found_block->block_size) { | |
355 | #ifdef CLIENT_DEBUG | |
356 | if (new_client_size > found_block->request_size) { | |
357 | found_block->request_size = new_client_size; | |
358 | } | |
359 | #endif /* CLIENT_DEBUG */ | |
360 | return address; | |
361 | } | |
362 | ||
363 | ||
364 | /* Create a new block of the requested size. | |
365 | */ | |
366 | new_address = malloc(new_client_size); | |
367 | ||
368 | if (new_address == NULL) { | |
369 | // printf("error in realloc()\n"); | |
370 | return NULL; | |
371 | // FIXME: panic? | |
372 | } | |
373 | ||
374 | ||
375 | /* Copy the data from the old block to the new one. | |
376 | * Make sure to copy only the lesser of the existing and | |
377 | * requested new size. (Note: The code above currently | |
378 | * screens out a realloc to a smaller size, but it might | |
379 | * not always do that.) | |
380 | */ | |
381 | copy_bytecount = found_block->block_size - sizeof(malloc_block); | |
382 | ||
383 | if (new_client_size < copy_bytecount) { | |
384 | copy_bytecount = new_client_size; | |
385 | } | |
386 | ||
387 | memcpy(new_address, address, copy_bytecount); | |
388 | ||
389 | ||
390 | /* Free the old block. | |
391 | */ | |
392 | free(address); | |
393 | ||
394 | return (void *)new_address; | |
1c79356b A |
395 | |
396 | } /* realloc() */ | |
397 | ||
398 | ||
de355530 A |
399 | /********************************************************************* |
400 | ********************************************************************** | |
401 | ***** PACKAGE-INTERNAL FUNCTIONS BELOW HERE ***** | |
402 | ********************************************************************** | |
403 | *********************************************************************/ | |
404 | ||
405 | ||
406 | ||
407 | /********************************************************************* | |
408 | * malloc_create_region() | |
409 | * | |
410 | * Package-internal function. VM-allocates a new region and adds it to | |
411 | * the given region list. | |
412 | *********************************************************************/ | |
413 | __private_extern__ | |
414 | malloc_region * malloc_create_region(vm_size_t block_size) { | |
415 | ||
416 | malloc_region * new_region; | |
417 | vm_address_t vm_address; | |
418 | vm_size_t region_size; | |
419 | kern_return_t kern_result; | |
420 | ||
421 | ||
422 | /* Figure out how big the region needs to be and allocate it. | |
423 | */ | |
424 | region_size = block_size + sizeof(malloc_region); | |
425 | region_size = round_page(region_size); | |
426 | ||
427 | kern_result = kmem_alloc(kernel_map, | |
428 | &vm_address, region_size); | |
429 | ||
430 | if (kern_result != KERN_SUCCESS) { | |
431 | // printf("kmem_alloc() failed in malloc_create_region()\n"); | |
432 | return NULL; | |
433 | // panic(); | |
434 | } | |
435 | ||
436 | ||
437 | /* Cast the allocated pointer to a region header. | |
438 | */ | |
439 | new_region = (malloc_region *)vm_address; | |
440 | ||
441 | ||
442 | /* Initialize the region header fields and link it onto | |
443 | * the previous region. | |
444 | */ | |
445 | new_region->region_size = region_size; | |
446 | queue_init(&new_region->block_list); | |
447 | // queue_init(&new_region->free_list); | |
448 | ||
449 | new_region->free_size = region_size - sizeof(malloc_region); | |
450 | new_region->free_address = &new_region->buffer; | |
451 | ||
452 | queue_enter(&malloc_region_list, new_region, malloc_region *, links); | |
453 | ||
454 | /* If debugging, add the new region's size to the total. | |
455 | */ | |
456 | #ifdef CLIENT_DEBUG | |
457 | malloc_hiwater_mark += region_size; | |
458 | num_regions++; | |
459 | #endif /* CLIENT_DEBUG */ | |
460 | ||
461 | return new_region; | |
462 | ||
463 | } /* malloc_create_region() */ | |
464 | ||
465 | ||
466 | /********************************************************************* | |
467 | * malloc_free_region() | |
468 | * | |
469 | * Package-internal function. VM-deallocates the given region. | |
470 | *********************************************************************/ | |
471 | __private_extern__ | |
472 | kern_return_t malloc_free_region(malloc_region * region) { | |
473 | ||
474 | kmem_free(kernel_map, | |
475 | (vm_address_t)region, | |
476 | region->region_size); | |
477 | ||
478 | #ifdef CLIENT_DEBUG | |
479 | num_regions--; | |
480 | #endif /* CLIENT_DEBUG */ | |
481 | return KERN_SUCCESS; | |
482 | ||
483 | } /* malloc_free_region() */ | |
484 | ||
485 | ||
486 | /********************************************************************* | |
487 | * malloc_create_block_in_region() | |
488 | * | |
489 | * Package-internal function. Allocates a new block out of the given | |
490 | * region. The requested size must include the block header. If the | |
491 | * size requested is larger than the region's free size, returns NULL. | |
492 | *********************************************************************/ | |
493 | __private_extern__ | |
494 | malloc_block * malloc_create_block_in_region( | |
495 | malloc_region * region, | |
496 | size_t block_size) { | |
497 | ||
498 | malloc_block * new_block = NULL; | |
499 | ||
500 | ||
501 | /* Sanity checking. | |
502 | */ | |
503 | if (block_size > region->free_size) { | |
504 | return NULL; | |
505 | // FIXME: panic? | |
506 | } | |
507 | ||
508 | ||
509 | /* Carve out a new block. | |
510 | */ | |
511 | new_block = (malloc_block *)region->free_address; | |
512 | region->free_address = (char *)region->free_address + block_size; | |
513 | region->free_size -= block_size; | |
514 | ||
515 | memset(new_block, 0, sizeof(malloc_block)); | |
516 | ||
517 | new_block->region = region; | |
518 | new_block->block_size = block_size; | |
519 | ||
520 | /* Record the new block as the last one in the region. | |
521 | */ | |
522 | queue_enter(®ion->block_list, new_block, malloc_block *, links); | |
523 | ||
524 | return new_block; | |
525 | ||
526 | } /* malloc_create_block_in_region() */ | |
527 | ||
528 | ||
529 | /********************************************************************* | |
530 | * malloc_find_block() | |
531 | * | |
532 | * Package-internal function. Given a client buffer address, find the | |
533 | * malloc_block for it. | |
534 | *********************************************************************/ | |
535 | __private_extern__ | |
536 | void malloc_find_block(void * address, | |
537 | malloc_block ** block, | |
538 | malloc_region ** region) { | |
539 | ||
540 | malloc_region * cur_region; | |
541 | ||
542 | *block = NULL; | |
543 | *region = NULL; | |
544 | ||
545 | queue_iterate(&malloc_region_list, cur_region, malloc_region *, links) { | |
546 | ||
547 | malloc_block * cur_block; | |
548 | ||
549 | queue_iterate(&cur_region->block_list, cur_block, malloc_block *, links) { | |
550 | if (cur_block->buffer == address) { | |
551 | *block = cur_block; | |
552 | *region = cur_region; | |
553 | return; | |
554 | } | |
555 | } | |
556 | } | |
557 | ||
558 | return; | |
559 | ||
560 | } /* malloc_find_block() */ | |
561 | ||
562 | ||
563 | /********************************************************************* | |
564 | * malloc_get_free_block() | |
565 | *********************************************************************/ | |
566 | __private_extern__ | |
567 | void malloc_get_free_block( | |
568 | size_t size, | |
569 | malloc_block ** block, | |
570 | malloc_region ** region) { | |
571 | ||
572 | malloc_block * cur_block; | |
573 | size_t fit_threshold = 512; | |
574 | ||
575 | *block = NULL; | |
576 | *region = NULL; | |
577 | ||
578 | queue_iterate(&sorted_free_block_list, cur_block, malloc_block *, links) { | |
579 | ||
580 | /* If we find a block large enough, but not too large to waste memory, | |
581 | * pull it out and return it, along with its region. | |
582 | */ | |
583 | if (cur_block->block_size >= size && | |
584 | cur_block->block_size < (size + fit_threshold)) { | |
585 | ||
586 | queue_remove(&sorted_free_block_list, cur_block, malloc_block *, links); | |
587 | *block = cur_block; | |
588 | *region = cur_block->region; | |
589 | return; | |
590 | } | |
591 | } | |
592 | return; | |
593 | } |