]> git.saurik.com Git - apple/xnu.git/blame - libsa/malloc.c
xnu-344.34.tar.gz
[apple/xnu.git] / libsa / malloc.c
CommitLineData
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*********************************************************************/
34static inline size_t round_to_long(size_t size) {
35 return (size + sizeof(long int)) & ~(sizeof(long int) - 1);
36}
37
38
39typedef 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*********************************************************************/
47typedef 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*********************************************************************/
66typedef 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*********************************************************************/
102static malloc_region * malloc_create_region(vm_size_t size);
103static kern_return_t malloc_free_region(malloc_region * region);
104static malloc_block * malloc_create_block_in_region(
105 malloc_region * region,
106 size_t size);
107static void malloc_find_block(
108 void * address,
109 malloc_block ** block,
110 malloc_region ** region);
111static 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*********************************************************************/
121static queue_entry malloc_region_list = {
122 &malloc_region_list, // the "next" field
123 &malloc_region_list // the "prev" field
124};
1c79356b 125
de355530
A
126static queue_entry sorted_free_block_list = {
127 &sorted_free_block_list,
128 &sorted_free_block_list
129};
130
131#ifdef CLIENT_DEBUG
132static size_t malloc_hiwater_mark = 0;
133static long int num_regions = 0;
134
135static size_t current_block_total = 0;
136static double peak_usage = 0.0;
137static double min_usage = 100.0;
138#endif /* CLIENT_DEBUG */
139
140
141/*********************************************************************
142* malloc()
143*********************************************************************/
1c79356b
A
144__private_extern__
145void * 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__
243void 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__
298void 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__
326void * 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__
414malloc_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__
472kern_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__
494malloc_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(&region->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__
536void 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__
567void 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}