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 21 class AbstractTraceEntryWithStackTrace; 22 struct kernel_args; 23 struct ObjectCache; 24 struct 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 42 class MemoryManager { 43 public: 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 71 private: 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 148 private: 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 215 private: 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 236 MemoryManager::MaintenanceNeeded() 237 { 238 return sMaintenanceNeeded; 239 } 240 241 242 /*static*/ inline void 243 MemoryManager::_PushFreeArea(Area* area) 244 { 245 _push(sFreeAreas, area); 246 sFreeAreaCount++; 247 } 248 249 250 /*static*/ inline MemoryManager::Area* 251 MemoryManager::_PopFreeArea() 252 { 253 if (sFreeAreaCount == 0) 254 return NULL; 255 256 sFreeAreaCount--; 257 return _pop(sFreeAreas); 258 } 259 260 261 /*static*/ inline addr_t 262 MemoryManager::_AreaBaseAddressForAddress(addr_t address) 263 { 264 return ROUNDDOWN((addr_t)address, SLAB_AREA_SIZE); 265 } 266 267 268 /*static*/ inline MemoryManager::Area* 269 MemoryManager::_AreaForAddress(addr_t address) 270 { 271 return (Area*)(_AreaBaseAddressForAddress(address) 272 + SLAB_AREA_STRUCT_OFFSET); 273 } 274 275 276 /*static*/ inline uint32 277 MemoryManager::_ChunkIndexForAddress(const MetaChunk* metaChunk, addr_t address) 278 { 279 return (address - metaChunk->chunkBase) / metaChunk->chunkSize; 280 } 281 282 283 /*static*/ inline addr_t 284 MemoryManager::_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 292 MemoryManager::_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 300 inline MemoryManager::Area* 301 MemoryManager::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* 310 MemoryManager::_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