libsa/malloc.c

   1 /*
   2  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   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.
  11  *
  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
  14  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  15  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  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.
  19  *
  20  * @APPLE_LICENSE_HEADER_END@
  21  */
  22 #include <vm/vm_kern.h>
  23 #include <kern/queue.h>
  24 #include <string.h>
  25
  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;
  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 {
  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)));
  76 } malloc_block;
  77
  78
  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 };
 125
 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 *********************************************************************/
 144 __private_extern__
 145 void * malloc(size_t size) {
 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);
 161
 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;
 232
 233 } /* malloc() */
 234
 235
 236 /*********************************************************************
 237 * free()
 238 *
 239 * Moves a block from the allocated list to the free list. Neither
 240 * list is kept sorted!
 241 *********************************************************************/
 242 __private_extern__
 243 void free(void * address) {
 244     malloc_region * found_region = NULL;
 245     malloc_block  * found_block = NULL;
 246     malloc_block  * cur_block = NULL;
 247
 248    /* Find the block and region for the given address.
 249     */
 250     malloc_find_block(address, &found_block, &found_region);
 251
 252     if (found_block == NULL) {
 253         return;
 254         // FIXME: panic?
 255     }
 256
 257
 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);
 262
 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     }
 271
 272
 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     }
 279
 280
 281 #ifdef CLIENT_DEBUG
 282     current_block_total -= found_block->block_size;
 283 #endif CLIENT_DEBUG
 284
 285     return;
 286
 287 } /* free() */
 288
 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) {
 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
 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) {
 327     malloc_region * found_region = NULL;
 328     malloc_block  * found_block = NULL;
 329     void * new_address;
 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;
 395
 396 } /* realloc() */
 397
 398
 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(&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__
 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 }