libsa/malloc.c

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