1 /* 2 * Copyright 2006-2008, Haiku Inc. All rights reserved. 3 * Distributed under the terms of the MIT License. 4 * 5 * Authors: 6 * Michael Lotz <mmlr@mlotz.ch> 7 */ 8 9 #include <malloc.h> 10 #include <string.h> 11 #include <KernelExport.h> 12 #include <util/kernel_cpp.h> 13 #include "BeOSCompatibility.h" 14 #include "PhysicalMemoryAllocator.h" 15 16 17 //#define TRACE_PHYSICAL_MEMORY_ALLOCATOR 18 #ifdef TRACE_PHYSICAL_MEMORY_ALLOCATOR 19 #define TRACE(x) dprintf x 20 #define TRACE_ERROR(x) dprintf x 21 #else 22 #define TRACE(x) /* nothing */ 23 #define TRACE_ERROR(x) dprintf x 24 #endif 25 26 27 PhysicalMemoryAllocator::PhysicalMemoryAllocator(const char *name, 28 size_t minSize, size_t maxSize, uint32 minCountPerBlock) 29 : fOverhead(0), 30 fStatus(B_NO_INIT) 31 { 32 fName = strdup(name); 33 mutex_init_etc(&fLock, fName, MUTEX_FLAG_CLONE_NAME); 34 35 fArrayCount = 1; 36 size_t biggestSize = minSize; 37 while (biggestSize < maxSize) { 38 fArrayCount++; 39 biggestSize *= 2; 40 } 41 42 size_t size = fArrayCount * sizeof(uint8 *); 43 fArray = (uint8 **)malloc(size); 44 fOverhead += size; 45 46 size = fArrayCount * sizeof(size_t); 47 fBlockSize = (size_t *)malloc(size); 48 fArrayLength = (size_t *)malloc(size); 49 fArrayOffset = (size_t *)malloc(size); 50 fOverhead += size * 3; 51 52 size_t arraySlots = biggestSize / minSize; 53 for (int32 i = 0; i < fArrayCount; i++) { 54 size = arraySlots * minCountPerBlock * sizeof(uint8); 55 fArrayLength[i] = arraySlots * minCountPerBlock; 56 fBlockSize[i] = biggestSize / arraySlots; 57 fArrayOffset[i] = fArrayLength[i] - 1; 58 59 fArray[i] = (uint8 *)malloc(size); 60 memset(fArray[i], 0, fArrayLength[i]); 61 62 fOverhead += size; 63 arraySlots /= 2; 64 } 65 66 fManagedMemory = fBlockSize[0] * fArrayLength[0]; 67 68 size_t roundedSize = biggestSize * minCountPerBlock; 69 #ifdef HAIKU_TARGET_PLATFORM_HAIKU 70 fDebugBase = roundedSize; 71 fDebugChunkSize = 64; 72 fDebugUseMap = 0; 73 roundedSize += sizeof(fDebugUseMap) * 8 * fDebugChunkSize; 74 #endif 75 roundedSize = (roundedSize + B_PAGE_SIZE - 1) & ~(B_PAGE_SIZE - 1); 76 77 fArea = create_area(fName, &fLogicalBase, B_ANY_KERNEL_ADDRESS, 78 roundedSize, B_CONTIGUOUS, B_READ_AREA | B_WRITE_AREA); 79 if (fArea < B_OK) { 80 TRACE_ERROR(("PMA: failed to create memory area\n")); 81 return; 82 } 83 84 physical_entry physicalEntry; 85 if (get_memory_map(fLogicalBase, roundedSize, &physicalEntry, 1) < B_OK) { 86 TRACE_ERROR(("PMA: failed to get memory map\n")); 87 return; 88 } 89 90 fPhysicalBase = physicalEntry.address; 91 fStatus = B_OK; 92 } 93 94 95 PhysicalMemoryAllocator::~PhysicalMemoryAllocator() 96 { 97 _Lock(); 98 99 for (int32 i = 0; i < fArrayCount; i++) 100 free(fArray[i]); 101 102 free(fArray); 103 free(fArrayLength); 104 free(fBlockSize); 105 free(fArrayOffset); 106 free(fName); 107 108 delete_area(fArea); 109 mutex_destroy(&fLock); 110 } 111 112 113 bool 114 PhysicalMemoryAllocator::_Lock() 115 { 116 return (mutex_lock(&fLock) == B_OK); 117 } 118 119 120 void 121 PhysicalMemoryAllocator::_Unlock() 122 { 123 mutex_unlock(&fLock); 124 } 125 126 127 status_t 128 PhysicalMemoryAllocator::Allocate(size_t size, void **logicalAddress, 129 void **physicalAddress) 130 { 131 #ifdef HAIKU_TARGET_PLATFORM_HAIKU 132 if (debug_debugger_running()) { 133 for (int32 i = 0; i < 64; i++) { 134 uint64 mask = 1LL << i; 135 if ((fDebugUseMap & mask) == 0) { 136 fDebugUseMap |= mask; 137 *logicalAddress = (void *)((uint8 *)fLogicalBase + fDebugBase 138 + i * fDebugChunkSize); 139 *physicalAddress = (void *)((uint8 *)fPhysicalBase + fDebugBase 140 + i * fDebugChunkSize); 141 return B_OK; 142 } 143 } 144 145 return B_NO_MEMORY; 146 } 147 #endif 148 149 if (size == 0 || size > fBlockSize[fArrayCount - 1]) { 150 TRACE_ERROR(("PMA: bad value for allocate (%ld bytes)\n", size)); 151 return B_BAD_VALUE; 152 } 153 154 size_t arrayLength = 0; 155 int32 arrayToUse = 0; 156 for (int32 i = 0; i < fArrayCount; i++) { 157 if (fBlockSize[i] >= size) { 158 arrayToUse = i; 159 arrayLength = fArrayLength[i]; 160 break; 161 } 162 } 163 164 int32 retries = 5000; 165 while (retries-- > 0) { 166 if (!_Lock()) 167 return B_ERROR; 168 169 TRACE(("PMA: will use array %ld (blocksize: %ld) to allocate %ld bytes\n", arrayToUse, fBlockSize[arrayToUse], size)); 170 uint8 *targetArray = fArray[arrayToUse]; 171 uint32 arrayOffset = fArrayOffset[arrayToUse] % arrayLength; 172 for (size_t i = arrayOffset + 1; i != arrayOffset; i++) { 173 if (i >= arrayLength) 174 i -= arrayLength; 175 176 if (targetArray[i] == 0) { 177 // found a free slot 178 fArrayOffset[arrayToUse] = i; 179 180 // fill upwards to the smallest block 181 uint32 fillSize = 1; 182 uint32 arrayIndex = i; 183 for (int32 j = arrayToUse; j >= 0; j--) { 184 memset(&fArray[j][arrayIndex], 1, fillSize); 185 fillSize <<= 1; 186 arrayIndex <<= 1; 187 } 188 189 // fill downwards to the biggest block 190 arrayIndex = i >> 1; 191 for (int32 j = arrayToUse + 1; j < fArrayCount; j++) { 192 fArray[j][arrayIndex]++; 193 if (fArray[j][arrayIndex] > 1) 194 break; 195 196 arrayIndex >>= 1; 197 } 198 199 _Unlock(); 200 size_t offset = fBlockSize[arrayToUse] * i; 201 *logicalAddress = (void *)((uint8 *)fLogicalBase + offset); 202 *physicalAddress = (void *)((uint8 *)fPhysicalBase + offset); 203 return B_OK; 204 } 205 } 206 207 // no slot found 208 _Unlock(); 209 210 TRACE_ERROR(("PMA: found no free slot to store %ld bytes (%ld tries left)\n", size, retries)); 211 // we provide a scratch space here, memory will probably be freed 212 // as soon as some other transfer is completed and cleaned up. 213 // just wait a bit to give other threads a chance to free some slots. 214 snooze(100); 215 } 216 217 return B_NO_MEMORY; 218 } 219 220 221 status_t 222 PhysicalMemoryAllocator::Deallocate(size_t size, void *logicalAddress, 223 void *physicalAddress) 224 { 225 #ifdef HAIKU_TARGET_PLATFORM_HAIKU 226 if (debug_debugger_running()) { 227 uint32 index = ((uint8 *)logicalAddress - (uint8 *)fLogicalBase 228 - fDebugBase) / fDebugChunkSize; 229 fDebugUseMap &= ~(1LL << index); 230 return B_OK; 231 } 232 #endif 233 234 if (size == 0 || size > fBlockSize[fArrayCount - 1]) { 235 TRACE_ERROR(("PMA: bad value for deallocate (%ld bytes)\n", size)); 236 return B_BAD_VALUE; 237 } 238 239 int32 arrayToUse = 0; 240 for (int32 i = 0; i < fArrayCount; i++) { 241 if (fBlockSize[i] >= size) { 242 arrayToUse = i; 243 break; 244 } 245 } 246 247 uint32 offset; 248 if (logicalAddress) 249 offset = (uint32)logicalAddress - (uint32)fLogicalBase; 250 else if (physicalAddress) 251 offset = (uint32)physicalAddress - (uint32)fPhysicalBase; 252 else { 253 TRACE_ERROR(("PMA: no value given for either physical or logical address\n")); 254 return B_BAD_VALUE; 255 } 256 257 uint32 index = offset / fBlockSize[arrayToUse]; 258 if (index >= fArrayLength[arrayToUse]) { 259 TRACE_ERROR(("PMA: provided address resulted in invalid index\n")); 260 return B_BAD_VALUE; 261 } 262 263 TRACE(("PMA: will use array %ld (index: %ld) to deallocate %ld bytes\n", arrayToUse, index, size)); 264 if (fArray[arrayToUse][index] == 0) { 265 TRACE_ERROR(("PMA: address was not allocated!\n")); 266 return B_BAD_VALUE; 267 } 268 269 if (!_Lock()) 270 return B_ERROR; 271 272 // clear upwards to the smallest block 273 uint32 fillSize = 1; 274 uint32 arrayIndex = index; 275 for (int32 i = arrayToUse; i >= 0; i--) { 276 memset(&fArray[i][arrayIndex], 0, fillSize); 277 fillSize <<= 1; 278 arrayIndex <<= 1; 279 } 280 281 // clear downwards to the biggest block 282 arrayIndex = index >> 1; 283 for (int32 i = arrayToUse + 1; i < fArrayCount; i++) { 284 fArray[i][arrayIndex]--; 285 if (fArray[i][arrayIndex] > 0) 286 break; 287 288 arrayIndex >>= 1; 289 } 290 291 _Unlock(); 292 return B_OK; 293 } 294 295 296 void 297 PhysicalMemoryAllocator::PrintToStream() 298 { 299 dprintf("PhysicalMemoryAllocator \"%s\":\n", fName); 300 dprintf("\tMin block size:\t\t\t%ld bytes\n", fBlockSize[0]); 301 dprintf("\tMax block size:\t\t\t%ld bytes\n", fBlockSize[fArrayCount - 1]); 302 dprintf("\tMin count per block:\t%ld\n\n", fArrayLength[fArrayCount - 1]); 303 dprintf("\tArray count:\t\t\t%ld\n", fArrayCount); 304 305 dprintf("\tArray slots:\t\t\t% 8ld", fArrayLength[0]); 306 for (int32 i = 1; i < fArrayCount; i++) 307 dprintf(", % 8ld", fArrayLength[i]); 308 dprintf("\n"); 309 DumpFreeSlots(); 310 311 dprintf("\tBlock sizes:\t\t\t% 8ld", fBlockSize[0]); 312 for (int32 i = 1; i < fArrayCount; i++) 313 dprintf(", % 8ld", fBlockSize[i]); 314 dprintf("\n"); 315 DumpLastArray(); 316 dprintf("\n"); 317 318 dprintf("\tManaged memory:\t\t\t%ld bytes\n", fManagedMemory); 319 dprintf("\tGranularity:\t\t\t%ld bytes\n", fBlockSize[0]); 320 dprintf("\tMemory overhead:\t\t%ld bytes\n", fOverhead); 321 } 322 323 324 void 325 PhysicalMemoryAllocator::DumpArrays() 326 { 327 uint32 padding = 2; 328 for (int32 i = 0; i < fArrayCount; i++) { 329 dprintf("\tArray(%ld):\t", i); 330 for (size_t j = 0; j < fArrayLength[i]; j++) { 331 if (padding > 2) { 332 for (uint32 k = 0; k < (padding - 2) / 4; k++) 333 dprintf(" "); 334 dprintf("\\"); 335 for (uint32 k = 0; k < (padding - 2) / 4; k++) 336 dprintf("-"); 337 dprintf("%d", fArray[i][j]); 338 for (uint32 k = 0; k < (padding - 2) / 4; k++) 339 dprintf("-"); 340 dprintf("/"); 341 for (uint32 k = 0; k < (padding - 2) / 4 + 1; k++) 342 dprintf(" "); 343 } else { 344 dprintf("%d ", fArray[i][j]); 345 } 346 } 347 348 padding *= 2; 349 dprintf("\n"); 350 } 351 352 dprintf("\n"); 353 } 354 355 356 void 357 PhysicalMemoryAllocator::DumpLastArray() 358 { 359 dprintf("\tLast array:\t\t\t\t"); 360 for (size_t i = 0; i < fArrayLength[fArrayCount - 1]; i++) 361 dprintf("%d", fArray[fArrayCount - 1][i]); 362 dprintf("\n"); 363 } 364 365 366 void 367 PhysicalMemoryAllocator::DumpFreeSlots() 368 { 369 dprintf("\tFree slots:\t\t\t\t"); 370 for (int32 i = 0; i < fArrayCount; i++) { 371 uint32 freeSlots = 0; 372 for (size_t j = 0; j < fArrayLength[i]; j++) { 373 if (fArray[i][j] == 0) 374 freeSlots++; 375 } 376 377 if (i > 0) 378 dprintf(", % 8ld", freeSlots); 379 else 380 dprintf("% 8ld", freeSlots); 381 } 382 dprintf("\n"); 383 } 384