src/system/kernel/slab/allocator.cpp

   1 /*
   2  * Copyright 2010, Ingo Weinhold <ingo_weinhold@gmx.de>.
   3  * Copyright 2007, Hugo Santos. All Rights Reserved.
   4  * Distributed under the terms of the MIT License.
   5  */
   6
   7
   8 #include "slab_private.h"
   9
  10 #include <stdio.h>
  11 #include <string.h>
  12
  13 #include <algorithm>
  14
  15 #include <debug.h>
  16 #include <heap.h>
  17 #include <kernel.h> // for ROUNDUP
  18 #include <malloc.h>
  19 #include <vm/vm.h>
  20 #include <vm/VMAddressSpace.h>
  21
  22 #include "ObjectCache.h"
  23 #include "MemoryManager.h"
  24
  25
  26 #define DEBUG_ALLOCATOR
  27 //#define TEST_ALL_CACHES_DURING_BOOT
  28
  29 static const size_t kBlockSizes[] = {
  30         16, 24, 32, 48, 64, 80, 96, 112,
  31         128, 160, 192, 224, 256, 320, 384, 448,
  32         512, 640, 768, 896, 1024, 1280, 1536, 1792,
  33         2048, 2560, 3072, 3584, 4096, 4608, 5120, 5632,
  34         6144, 6656, 7168, 7680, 8192,
  35         0
  36 };
  37
  38 static const size_t kNumBlockSizes = sizeof(kBlockSizes) / sizeof(size_t) - 1;
  39
  40 static object_cache* sBlockCaches[kNumBlockSizes];
  41
  42 static addr_t sBootStrapMemory = 0;
  43 static size_t sBootStrapMemorySize = 0;
  44 static size_t sUsedBootStrapMemory = 0;
  45
  46
  47 RANGE_MARKER_FUNCTION_BEGIN(slab_allocator)
  48
  49
  50 static int
  51 size_to_index(size_t size)
  52 {
  53         if (size <= 16)
  54                 return 0;
  55         if (size <= 32)
  56                 return 1 + (size - 16 - 1) / 8;
  57         if (size <= 128)
  58                 return 3 + (size - 32 - 1) / 16;
  59         if (size <= 256)
  60                 return 9 + (size - 128 - 1) / 32;
  61         if (size <= 512)
  62                 return 13 + (size - 256 - 1) / 64;
  63         if (size <= 1024)
  64                 return 17 + (size - 512 - 1) / 128;
  65         if (size <= 2048)
  66                 return 21 + (size - 1024 - 1) / 256;
  67         if (size <= 8192)
  68                 return 25 + (size - 2048 - 1) / 512;
  69
  70         return -1;
  71 }
  72
  73
  74 void*
  75 block_alloc(size_t size, size_t alignment, uint32 flags)
  76 {
  77         if (alignment > kMinObjectAlignment) {
  78                 // Make size >= alignment and a power of two. This is sufficient, since
  79                 // all of our object caches with power of two sizes are aligned. We may
  80                 // waste quite a bit of memory, but memalign() is very rarely used
  81                 // in the kernel and always with power of two size == alignment anyway.
  82                 ASSERT((alignment & (alignment - 1)) == 0);
  83                 while (alignment < size)
  84                         alignment <<= 1;
  85                 size = alignment;
  86
  87                 // If we're not using an object cache, make sure that the memory
  88                 // manager knows it has to align the allocation.
  89                 if (size > kBlockSizes[kNumBlockSizes])
  90                         flags |= CACHE_ALIGN_ON_SIZE;
  91         }
  92
  93         // allocate from the respective object cache, if any
  94         int index = size_to_index(size);
  95         if (index >= 0)
  96                 return object_cache_alloc(sBlockCaches[index], flags);
  97
  98         // the allocation is too large for our object caches -- ask the memory
  99         // manager
 100         void* block;
 101         if (MemoryManager::AllocateRaw(size, flags, block) != B_OK)
 102                 return NULL;
 103
 104         return block;
 105 }
 106
 107
 108 void*
 109 block_alloc_early(size_t size)
 110 {
 111         int index = size_to_index(size);
 112         if (index >= 0 && sBlockCaches[index] != NULL)
 113                 return object_cache_alloc(sBlockCaches[index], CACHE_DURING_BOOT);
 114
 115         if (size > SLAB_CHUNK_SIZE_SMALL) {
 116                 // This is a sufficiently large allocation -- just ask the memory
 117                 // manager directly.
 118                 void* block;
 119                 if (MemoryManager::AllocateRaw(size, 0, block) != B_OK)
 120                         return NULL;
 121
 122                 return block;
 123         }
 124
 125         // A small allocation, but no object cache yet. Use the bootstrap memory.
 126         // This allocation must never be freed!
 127         if (sBootStrapMemorySize - sUsedBootStrapMemory < size) {
 128                 // We need more memory.
 129                 void* block;
 130                 if (MemoryManager::AllocateRaw(SLAB_CHUNK_SIZE_SMALL, 0, block) != B_OK)
 131                         return NULL;
 132                 sBootStrapMemory = (addr_t)block;
 133                 sBootStrapMemorySize = SLAB_CHUNK_SIZE_SMALL;
 134                 sUsedBootStrapMemory = 0;
 135         }
 136
 137         size_t neededSize = ROUNDUP(size, sizeof(double));
 138         if (sUsedBootStrapMemory + neededSize > sBootStrapMemorySize)
 139                 return NULL;
 140         void* block = (void*)(sBootStrapMemory + sUsedBootStrapMemory);
 141         sUsedBootStrapMemory += neededSize;
 142
 143         return block;
 144 }
 145
 146
 147 void
 148 block_free(void* block, uint32 flags)
 149 {
 150         if (block == NULL)
 151                 return;
 152
 153         ObjectCache* cache = MemoryManager::FreeRawOrReturnCache(block, flags);
 154         if (cache != NULL) {
 155                 // a regular small allocation
 156                 ASSERT(cache->object_size >= kBlockSizes[0]);
 157                 ASSERT(cache->object_size <= kBlockSizes[kNumBlockSizes - 1]);
 158                 ASSERT(cache == sBlockCaches[size_to_index(cache->object_size)]);
 159                 object_cache_free(cache, block, flags);
 160         }
 161 }
 162
 163
 164 void
 165 block_allocator_init_boot()
 166 {
 167         for (int index = 0; kBlockSizes[index] != 0; index++) {
 168                 char name[32];
 169                 snprintf(name, sizeof(name), "block allocator: %lu",
 170                         kBlockSizes[index]);
 171
 172                 uint32 flags = CACHE_DURING_BOOT;
 173                 size_t size = kBlockSizes[index];
 174
 175                 // align the power of two objects to their size
 176                 size_t alignment = (size & (size - 1)) == 0 ? size : 0;
 177
 178                 // For the larger allocation sizes disable the object depot, so we don't
 179                 // keep lot's of unused objects around.
 180                 if (size > 2048)
 181                         flags |= CACHE_NO_DEPOT;
 182
 183                 sBlockCaches[index] = create_object_cache_etc(name, size, alignment, 0,
 184                         0, 0, flags, NULL, NULL, NULL, NULL);
 185                 if (sBlockCaches[index] == NULL)
 186                         panic("allocator: failed to init block cache");
 187         }
 188 }
 189
 190
 191 void
 192 block_allocator_init_rest()
 193 {
 194 #ifdef TEST_ALL_CACHES_DURING_BOOT
 195         for (int index = 0; kBlockSizes[index] != 0; index++) {
 196                 block_free(block_alloc(kBlockSizes[index] - sizeof(boundary_tag)), 0,
 197                         0);
 198         }
 199 #endif
 200 }
 201
 202
 203 // #pragma mark - public API
 204
 205
 206 #if USE_SLAB_ALLOCATOR_FOR_MALLOC
 207
 208
 209 void*
 210 memalign(size_t alignment, size_t size)
 211 {
 212         return block_alloc(size, alignment, 0);
 213 }
 214
 215
 216 void *
 217 memalign_etc(size_t alignment, size_t size, uint32 flags)
 218 {
 219         return block_alloc(size, alignment, flags & CACHE_ALLOC_FLAGS);
 220 }
 221
 222
 223 void
 224 free_etc(void *address, uint32 flags)
 225 {
 226         block_free(address, flags & CACHE_ALLOC_FLAGS);
 227 }
 228
 229
 230 void*
 231 malloc(size_t size)
 232 {
 233         return block_alloc(size, 0, 0);
 234 }
 235
 236
 237 void
 238 free(void* address)
 239 {
 240         block_free(address, 0);
 241 }
 242
 243
 244 void*
 245 realloc(void* address, size_t newSize)
 246 {
 247         if (newSize == 0) {
 248                 block_free(address, 0);
 249                 return NULL;
 250         }
 251
 252         if (address == NULL)
 253                 return block_alloc(newSize, 0, 0);
 254
 255         size_t oldSize;
 256         ObjectCache* cache = MemoryManager::GetAllocationInfo(address, oldSize);
 257         if (cache == NULL && oldSize == 0) {
 258                 panic("block_realloc(): allocation %p not known", address);
 259                 return NULL;
 260         }
 261
 262         if (oldSize == newSize)
 263                 return address;
 264
 265         void* newBlock = block_alloc(newSize, 0, 0);
 266         if (newBlock == NULL)
 267                 return NULL;
 268
 269         memcpy(newBlock, address, std::min(oldSize, newSize));
 270
 271         block_free(address, 0);
 272
 273         return newBlock;
 274 }
 275
 276
 277 #endif  // USE_SLAB_ALLOCATOR_FOR_MALLOC
 278
 279
 280 RANGE_MARKER_FUNCTION_END(slab_allocator)