1 /* 2 * Copyright 2007, Hugo Santos. All Rights Reserved. 3 * Distributed under the terms of the MIT License. 4 * 5 * Authors: 6 * Hugo Santos, hugosantos@gmail.com 7 */ 8 9 #include <Slab.h> 10 11 #include "slab_private.h" 12 13 #include <kernel.h> // for ROUNDUP 14 15 #include <stdio.h> 16 #include <string.h> 17 18 #define DEBUG_ALLOCATOR 19 //#define TEST_ALL_CACHES_DURING_BOOT 20 21 static const size_t kBlockSizes[] = { 22 16, 24, 32, 48, 64, 80, 96, 112, 23 128, 160, 192, 224, 256, 320, 384, 448, 24 512, 640, 768, 896, 1024, 1280, 1536, 1792, 25 2048, 2560, 3072, 3584, 4096, 4608, 5120, 5632, 26 6144, 6656, 7168, 7680, 8192, 27 0 28 }; 29 30 static const size_t kNumBlockSizes = sizeof(kBlockSizes) / sizeof(size_t) - 1; 31 32 static object_cache *sBlockCaches[kNumBlockSizes]; 33 static int32 sBlockCacheWaste[kNumBlockSizes]; 34 35 struct boundary_tag { 36 uint32 size; 37 #ifdef DEBUG_ALLOCATOR 38 uint32 magic; 39 #endif 40 }; 41 42 struct area_boundary_tag { 43 area_id area; 44 boundary_tag tag; 45 }; 46 47 48 static const uint32 kBoundaryMagic = 0x6da78d13; 49 50 51 static int 52 size_to_index(size_t size) 53 { 54 if (size <= 16) 55 return 0; 56 else if (size <= 32) 57 return 1 + (size - 16 - 1) / 8; 58 else if (size <= 128) 59 return 3 + (size - 32 - 1) / 16; 60 else if (size <= 256) 61 return 9 + (size - 128 - 1) / 32; 62 else if (size <= 512) 63 return 13 + (size - 256 - 1) / 64; 64 else if (size <= 1024) 65 return 17 + (size - 512 - 1) / 128; 66 else if (size <= 2048) 67 return 21 + (size - 1024 - 1) / 256; 68 else if (size <= 8192) 69 return 25 + (size - 2048 - 1) / 512; 70 71 return -1; 72 } 73 74 75 void * 76 block_alloc(size_t size) 77 { 78 int index = size_to_index(size + sizeof(boundary_tag)); 79 80 void *block; 81 boundary_tag *tag; 82 83 if (index < 0) { 84 void *pages; 85 area_id area = create_area("alloc'ed block", &pages, 86 B_ANY_KERNEL_ADDRESS, ROUNDUP(size + sizeof(area_boundary_tag), 87 B_PAGE_SIZE), B_NO_LOCK, B_READ_AREA | B_WRITE_AREA); 88 if (area < B_OK) 89 return NULL; 90 91 area_boundary_tag *areaTag = (area_boundary_tag *)pages; 92 areaTag->area = area; 93 tag = &areaTag->tag; 94 block = areaTag + 1; 95 } else { 96 tag = (boundary_tag *)object_cache_alloc(sBlockCaches[index], 0); 97 if (tag == NULL) 98 return NULL; 99 atomic_add(&sBlockCacheWaste[index], kBlockSizes[index] - size 100 - sizeof(boundary_tag)); 101 block = tag + 1; 102 } 103 104 tag->size = size; 105 106 #ifdef DEBUG_ALLOCATOR 107 tag->magic = kBoundaryMagic; 108 #endif 109 110 return block; 111 } 112 113 114 void 115 block_free(void *block) 116 { 117 boundary_tag *tag = (boundary_tag *)(((uint8 *)block) 118 - sizeof(boundary_tag)); 119 120 #ifdef DEBUG_ALLOCATOR 121 if (tag->magic != kBoundaryMagic) 122 panic("allocator: boundary tag magic doesn't match this universe"); 123 #endif 124 125 int index = size_to_index(tag->size + sizeof(boundary_tag)); 126 127 if (index < 0) { 128 area_boundary_tag *areaTag = (area_boundary_tag *)(((uint8 *)block) 129 - sizeof(area_boundary_tag)); 130 delete_area(areaTag->area); 131 } else { 132 atomic_add(&sBlockCacheWaste[index], -(kBlockSizes[index] - tag->size 133 - sizeof(boundary_tag))); 134 object_cache_free(sBlockCaches[index], tag); 135 } 136 } 137 138 139 static void 140 block_create_cache(size_t index, bool boot) 141 { 142 char name[32]; 143 snprintf(name, sizeof(name), "block cache: %lu", kBlockSizes[index]); 144 145 sBlockCaches[index] = create_object_cache_etc(name, kBlockSizes[index], 146 0, 0, boot ? CACHE_DURING_BOOT : 0, NULL, NULL, NULL, NULL); 147 if (sBlockCaches[index] == NULL) 148 panic("allocator: failed to init block cache"); 149 150 sBlockCacheWaste[index] = 0; 151 } 152 153 154 static int 155 show_waste(int argc, char *argv[]) 156 { 157 size_t total = 0; 158 159 for (size_t index = 0; index < kNumBlockSizes; index++) { 160 if (sBlockCacheWaste[index] > 0) { 161 kprintf("%lu: %lu\n", kBlockSizes[index], sBlockCacheWaste[index]); 162 total += sBlockCacheWaste[index]; 163 } 164 } 165 166 kprintf("total waste: %lu\n", total); 167 168 return 0; 169 } 170 171 172 void 173 block_allocator_init_boot() 174 { 175 for (int index = 0; kBlockSizes[index] != 0; index++) 176 block_create_cache(index, true); 177 178 add_debugger_command("show_waste", show_waste, 179 "show cache allocator's memory waste"); 180 } 181 182 183 void 184 block_allocator_init_rest() 185 { 186 #ifdef TEST_ALL_CACHES_DURING_BOOT 187 for (int index = 0; kBlockSizes[index] != 0; index++) { 188 block_free(block_alloc(kBlockSizes[index] - sizeof(boundary_tag))); 189 } 190 #endif 191 } 192 193