1/* 2 * Copyright 2010, Ingo Weinhold <ingo_weinhold@gmx.de>. 3 * Distributed under the terms of the MIT License. 4 */ 5#ifndef MEMORY_MANAGER_H 6#define MEMORY_MANAGER_H 7 8 9#include <KernelExport.h> 10 11#include <condition_variable.h> 12#include <kernel.h> 13#include <lock.h> 14#include <util/DoublyLinkedList.h> 15#include <util/OpenHashTable.h> 16 17#include "slab_debug.h" 18#include "slab_private.h" 19 20 21class AbstractTraceEntryWithStackTrace; 22struct kernel_args; 23struct ObjectCache; 24struct VMArea; 25 26 27#define SLAB_CHUNK_SIZE_SMALL B_PAGE_SIZE 28#define SLAB_CHUNK_SIZE_MEDIUM (16 * B_PAGE_SIZE) 29#define SLAB_CHUNK_SIZE_LARGE (128 * B_PAGE_SIZE) 30#define SLAB_AREA_SIZE (2048 * B_PAGE_SIZE) 31 // TODO: These sizes have been chosen with 4 KB pages in mind. 32#define SLAB_AREA_STRUCT_OFFSET B_PAGE_SIZE 33 // The offset from the start of the area to the Area structure. This space 34 // is not mapped and will trip code writing beyond the previous area's 35 // bounds. 36 37#define SLAB_META_CHUNKS_PER_AREA (SLAB_AREA_SIZE / SLAB_CHUNK_SIZE_LARGE) 38#define SLAB_SMALL_CHUNKS_PER_META_CHUNK \ 39 (SLAB_CHUNK_SIZE_LARGE / SLAB_CHUNK_SIZE_SMALL) 40 41 42class MemoryManager { 43public: 44 static void Init(kernel_args* args); 45 static void InitPostArea(); 46 47 static status_t Allocate(ObjectCache* cache, uint32 flags, 48 void*& _pages); 49 static void Free(void* pages, uint32 flags); 50 51 static status_t AllocateRaw(size_t size, uint32 flags, 52 void*& _pages); 53 static ObjectCache* FreeRawOrReturnCache(void* pages, 54 uint32 flags); 55 56 static size_t AcceptableChunkSize(size_t size); 57 static ObjectCache* GetAllocationInfo(void* address, 58 size_t& _size); 59 static ObjectCache* CacheForAddress(void* address); 60 61 static bool MaintenanceNeeded(); 62 static void PerformMaintenance(); 63 64#if SLAB_MEMORY_MANAGER_ALLOCATION_TRACKING 65 static bool AnalyzeAllocationCallers( 66 AllocationTrackingCallback& callback); 67#endif 68 69 static ObjectCache* DebugObjectCacheForAddress(void* address); 70 71private: 72 struct Tracing; 73 74 struct Area; 75 76 struct Chunk { 77 union { 78 Chunk* next; 79 addr_t reference; 80 }; 81 }; 82 83 struct MetaChunk : DoublyLinkedListLinkImpl<MetaChunk> { 84 size_t chunkSize; 85 addr_t chunkBase; 86 size_t totalSize; 87 uint16 chunkCount; 88 uint16 usedChunkCount; 89 uint16 firstFreeChunk; // *some* free range 90 uint16 lastFreeChunk; // inclusive 91 Chunk chunks[SLAB_SMALL_CHUNKS_PER_META_CHUNK]; 92 Chunk* freeChunks; 93 94 Area* GetArea() const; 95 }; 96 97 friend struct MetaChunk; 98 typedef DoublyLinkedList<MetaChunk> MetaChunkList; 99 100 struct Area : DoublyLinkedListLinkImpl<Area> { 101 Area* next; 102 VMArea* vmArea; 103 size_t reserved_memory_for_mapping; 104 uint16 usedMetaChunkCount; 105 bool fullyMapped; 106 MetaChunk metaChunks[SLAB_META_CHUNKS_PER_AREA]; 107 108 addr_t BaseAddress() const 109 { 110 return (addr_t)this - SLAB_AREA_STRUCT_OFFSET; 111 } 112 }; 113 114 typedef DoublyLinkedList<Area> AreaList; 115 116 struct AreaHashDefinition { 117 typedef addr_t KeyType; 118 typedef Area ValueType; 119 120 size_t HashKey(addr_t key) const 121 { 122 return key / SLAB_AREA_SIZE; 123 } 124 125 size_t Hash(const Area* value) const 126 { 127 return HashKey(value->BaseAddress()); 128 } 129 130 bool Compare(addr_t key, const Area* value) const 131 { 132 return key == value->BaseAddress(); 133 } 134 135 Area*& GetLink(Area* value) const 136 { 137 return value->next; 138 } 139 }; 140 141 typedef BOpenHashTable<AreaHashDefinition> AreaTable; 142 143 struct AllocationEntry { 144 ConditionVariable condition; 145 thread_id thread; 146 }; 147 148private: 149 static status_t _AllocateChunks(size_t chunkSize, 150 uint32 chunkCount, uint32 flags, 151 MetaChunk*& _metaChunk, Chunk*& _chunk); 152 static bool _GetChunks(MetaChunkList* metaChunkList, 153 size_t chunkSize, uint32 chunkCount, 154 MetaChunk*& _metaChunk, Chunk*& _chunk); 155 static bool _GetChunk(MetaChunkList* metaChunkList, 156 size_t chunkSize, MetaChunk*& _metaChunk, 157 Chunk*& _chunk); 158 static void _FreeChunk(Area* area, MetaChunk* metaChunk, 159 Chunk* chunk, addr_t chunkAddress, 160 bool alreadyUnmapped, uint32 flags); 161 162 static void _PrepareMetaChunk(MetaChunk* metaChunk, 163 size_t chunkSize); 164 165 static void _PushFreeArea(Area* area); 166 static Area* _PopFreeArea(); 167 168 static void _AddArea(Area* area); 169 static status_t _AllocateArea(uint32 flags, Area*& _area); 170 static void _FreeArea(Area* area, bool areaRemoved, 171 uint32 flags); 172 173 static status_t _MapChunk(VMArea* vmArea, addr_t address, 174 size_t size, size_t reserveAdditionalMemory, 175 uint32 flags); 176 static status_t _UnmapChunk(VMArea* vmArea, addr_t address, 177 size_t size, uint32 flags); 178 179 static void _UnmapFreeChunksEarly(Area* area); 180 static void _ConvertEarlyArea(Area* area); 181 182 static void _RequestMaintenance(); 183 184 static addr_t _AreaBaseAddressForAddress(addr_t address); 185 static Area* _AreaForAddress(addr_t address); 186 static uint32 _ChunkIndexForAddress( 187 const MetaChunk* metaChunk, addr_t address); 188 static addr_t _ChunkAddress(const MetaChunk* metaChunk, 189 const Chunk* chunk); 190 static bool _IsChunkFree(const MetaChunk* metaChunk, 191 const Chunk* chunk); 192 static bool _IsChunkInFreeList(const MetaChunk* metaChunk, 193 const Chunk* chunk); 194 static void _CheckMetaChunk(MetaChunk* metaChunk); 195 196 static int _DumpRawAllocations(int argc, char** argv); 197 static void _PrintMetaChunkTableHeader(bool printChunks); 198 static void _DumpMetaChunk(MetaChunk* metaChunk, 199 bool printChunks, bool printHeader); 200 static int _DumpMetaChunk(int argc, char** argv); 201 static void _DumpMetaChunks(const char* name, 202 MetaChunkList& metaChunkList, 203 bool printChunks); 204 static int _DumpMetaChunks(int argc, char** argv); 205 static int _DumpArea(int argc, char** argv); 206 static int _DumpAreas(int argc, char** argv); 207 208#if SLAB_MEMORY_MANAGER_ALLOCATION_TRACKING 209 static void _AddTrackingInfo(void* allocation, size_t size, 210 AbstractTraceEntryWithStackTrace* entry); 211 static AllocationTrackingInfo* _TrackingInfoFor(void* allocation, 212 size_t size); 213#endif 214 215private: 216 static const size_t kAreaAdminSize 217 = ROUNDUP(sizeof(Area), B_PAGE_SIZE); 218 219 static mutex sLock; 220 static rw_lock sAreaTableLock; 221 static kernel_args* sKernelArgs; 222 static AreaTable sAreaTable; 223 static Area* sFreeAreas; 224 static int sFreeAreaCount; 225 static MetaChunkList sFreeCompleteMetaChunks; 226 static MetaChunkList sFreeShortMetaChunks; 227 static MetaChunkList sPartialMetaChunksSmall; 228 static MetaChunkList sPartialMetaChunksMedium; 229 static AllocationEntry* sAllocationEntryCanWait; 230 static AllocationEntry* sAllocationEntryDontWait; 231 static bool sMaintenanceNeeded; 232}; 233 234 235/*static*/ inline bool 236MemoryManager::MaintenanceNeeded() 237{ 238 return sMaintenanceNeeded; 239} 240 241 242/*static*/ inline void 243MemoryManager::_PushFreeArea(Area* area) 244{ 245 _push(sFreeAreas, area); 246 sFreeAreaCount++; 247} 248 249 250/*static*/ inline MemoryManager::Area* 251MemoryManager::_PopFreeArea() 252{ 253 if (sFreeAreaCount == 0) 254 return NULL; 255 256 sFreeAreaCount--; 257 return _pop(sFreeAreas); 258} 259 260 261/*static*/ inline addr_t 262MemoryManager::_AreaBaseAddressForAddress(addr_t address) 263{ 264 return ROUNDDOWN((addr_t)address, SLAB_AREA_SIZE); 265} 266 267 268/*static*/ inline MemoryManager::Area* 269MemoryManager::_AreaForAddress(addr_t address) 270{ 271 return (Area*)(_AreaBaseAddressForAddress(address) 272 + SLAB_AREA_STRUCT_OFFSET); 273} 274 275 276/*static*/ inline uint32 277MemoryManager::_ChunkIndexForAddress(const MetaChunk* metaChunk, addr_t address) 278{ 279 return (address - metaChunk->chunkBase) / metaChunk->chunkSize; 280} 281 282 283/*static*/ inline addr_t 284MemoryManager::_ChunkAddress(const MetaChunk* metaChunk, const Chunk* chunk) 285{ 286 return metaChunk->chunkBase 287 + (chunk - metaChunk->chunks) * metaChunk->chunkSize; 288} 289 290 291/*static*/ inline bool 292MemoryManager::_IsChunkFree(const MetaChunk* metaChunk, const Chunk* chunk) 293{ 294 return chunk->next == NULL 295 || (chunk->next >= metaChunk->chunks 296 && chunk->next < metaChunk->chunks + metaChunk->chunkCount); 297} 298 299 300inline MemoryManager::Area* 301MemoryManager::MetaChunk::GetArea() const 302{ 303 return _AreaForAddress((addr_t)this); 304} 305 306 307#if SLAB_MEMORY_MANAGER_ALLOCATION_TRACKING 308 309/*static*/ inline AllocationTrackingInfo* 310MemoryManager::_TrackingInfoFor(void* allocation, size_t size) 311{ 312 return (AllocationTrackingInfo*)((uint8*)allocation + size 313 - sizeof(AllocationTrackingInfo)); 314} 315 316#endif // SLAB_MEMORY_MANAGER_ALLOCATION_TRACKING 317 318 319#endif // MEMORY_MANAGER_H 320