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_32_BIT_CONTIGUOUS, B_READ_AREA | B_WRITE_AREA); 79 // TODO: Use B_CONTIGUOUS when the TODOs regarding 64 bit physical 80 // addresses are fixed (if possible). 81 if (fArea < B_OK) { 82 TRACE_ERROR(("PMA: failed to create memory area\n")); 83 return; 84 } 85 86 physical_entry physicalEntry; 87 if (get_memory_map(fLogicalBase, roundedSize, &physicalEntry, 1) < B_OK) { 88 TRACE_ERROR(("PMA: failed to get memory map\n")); 89 return; 90 } 91 92 fPhysicalBase = physicalEntry.address; 93 fStatus = B_OK; 94 } 95 96 97 PhysicalMemoryAllocator::~PhysicalMemoryAllocator() 98 { 99 _Lock(); 100 101 for (int32 i = 0; i < fArrayCount; i++) 102 free(fArray[i]); 103 104 free(fArray); 105 free(fArrayLength); 106 free(fBlockSize); 107 free(fArrayOffset); 108 free(fName); 109 110 delete_area(fArea); 111 mutex_destroy(&fLock); 112 } 113 114 115 bool 116 PhysicalMemoryAllocator::_Lock() 117 { 118 return (mutex_lock(&fLock) == B_OK); 119 } 120 121 122 void 123 PhysicalMemoryAllocator::_Unlock() 124 { 125 mutex_unlock(&fLock); 126 } 127 128 129 status_t 130 PhysicalMemoryAllocator::Allocate(size_t size, void **logicalAddress, 131 void **physicalAddress) 132 { 133 // TODO: physicalAddress should be a phys_addr_t*! 134 #ifdef HAIKU_TARGET_PLATFORM_HAIKU 135 if (debug_debugger_running()) { 136 for (int32 i = 0; i < 64; i++) { 137 uint64 mask = 1LL << i; 138 if ((fDebugUseMap & mask) == 0) { 139 fDebugUseMap |= mask; 140 *logicalAddress = (void *)((uint8 *)fLogicalBase + fDebugBase 141 + i * fDebugChunkSize); 142 *physicalAddress = (void *)(fPhysicalBase + fDebugBase 143 + i * fDebugChunkSize); 144 return B_OK; 145 } 146 } 147 148 return B_NO_MEMORY; 149 } 150 #endif 151 152 if (size == 0 || size > fBlockSize[fArrayCount - 1]) { 153 TRACE_ERROR(("PMA: bad value for allocate (%ld bytes)\n", size)); 154 return B_BAD_VALUE; 155 } 156 157 size_t arrayLength = 0; 158 int32 arrayToUse = 0; 159 for (int32 i = 0; i < fArrayCount; i++) { 160 if (fBlockSize[i] >= size) { 161 arrayToUse = i; 162 arrayLength = fArrayLength[i]; 163 break; 164 } 165 } 166 167 int32 retries = 5000; 168 while (retries-- > 0) { 169 if (!_Lock()) 170 return B_ERROR; 171 172 TRACE(("PMA: will use array %ld (blocksize: %ld) to allocate %ld bytes\n", arrayToUse, fBlockSize[arrayToUse], size)); 173 uint8 *targetArray = fArray[arrayToUse]; 174 uint32 arrayOffset = fArrayOffset[arrayToUse] % arrayLength; 175 for (size_t i = arrayOffset + 1; i != arrayOffset; i++) { 176 if (i >= arrayLength) 177 i -= arrayLength; 178 179 if (targetArray[i] == 0) { 180 // found a free slot 181 fArrayOffset[arrayToUse] = i; 182 183 // fill upwards to the smallest block 184 uint32 fillSize = 1; 185 uint32 arrayIndex = i; 186 for (int32 j = arrayToUse; j >= 0; j--) { 187 memset(&fArray[j][arrayIndex], 1, fillSize); 188 fillSize <<= 1; 189 arrayIndex <<= 1; 190 } 191 192 // fill downwards to the biggest block 193 arrayIndex = i >> 1; 194 for (int32 j = arrayToUse + 1; j < fArrayCount; j++) { 195 fArray[j][arrayIndex]++; 196 if (fArray[j][arrayIndex] > 1) 197 break; 198 199 arrayIndex >>= 1; 200 } 201 202 _Unlock(); 203 size_t offset = fBlockSize[arrayToUse] * i; 204 *logicalAddress = (void *)((uint8 *)fLogicalBase + offset); 205 *physicalAddress = (void *)(fPhysicalBase + offset); 206 return B_OK; 207 } 208 } 209 210 // no slot found 211 _Unlock(); 212 213 TRACE_ERROR(("PMA: found no free slot to store %ld bytes (%ld tries left)\n", size, retries)); 214 // we provide a scratch space here, memory will probably be freed 215 // as soon as some other transfer is completed and cleaned up. 216 // just wait a bit to give other threads a chance to free some slots. 217 snooze(100); 218 } 219 220 return B_NO_MEMORY; 221 } 222 223 224 status_t 225 PhysicalMemoryAllocator::Deallocate(size_t size, void *logicalAddress, 226 void *physicalAddress) 227 { 228 // TODO: physicalAddress should be a phys_addr_t! 229 #ifdef HAIKU_TARGET_PLATFORM_HAIKU 230 if (debug_debugger_running()) { 231 uint32 index = ((uint8 *)logicalAddress - (uint8 *)fLogicalBase 232 - fDebugBase) / fDebugChunkSize; 233 fDebugUseMap &= ~(1LL << index); 234 return B_OK; 235 } 236 #endif 237 238 if (size == 0 || size > fBlockSize[fArrayCount - 1]) { 239 TRACE_ERROR(("PMA: bad value for deallocate (%ld bytes)\n", size)); 240 return B_BAD_VALUE; 241 } 242 243 int32 arrayToUse = 0; 244 for (int32 i = 0; i < fArrayCount; i++) { 245 if (fBlockSize[i] >= size) { 246 arrayToUse = i; 247 break; 248 } 249 } 250 251 uint32 offset; 252 if (logicalAddress) 253 offset = (uint32)logicalAddress - (uint32)fLogicalBase; 254 else if (physicalAddress) 255 offset = (addr_t)physicalAddress - fPhysicalBase; 256 else { 257 TRACE_ERROR(("PMA: no value given for either physical or logical address\n")); 258 return B_BAD_VALUE; 259 } 260 261 uint32 index = offset / fBlockSize[arrayToUse]; 262 if (index >= fArrayLength[arrayToUse]) { 263 TRACE_ERROR(("PMA: provided address resulted in invalid index\n")); 264 return B_BAD_VALUE; 265 } 266 267 TRACE(("PMA: will use array %ld (index: %ld) to deallocate %ld bytes\n", arrayToUse, index, size)); 268 if (fArray[arrayToUse][index] == 0) { 269 TRACE_ERROR(("PMA: address was not allocated!\n")); 270 return B_BAD_VALUE; 271 } 272 273 if (!_Lock()) 274 return B_ERROR; 275 276 // clear upwards to the smallest block 277 uint32 fillSize = 1; 278 uint32 arrayIndex = index; 279 for (int32 i = arrayToUse; i >= 0; i--) { 280 memset(&fArray[i][arrayIndex], 0, fillSize); 281 fillSize <<= 1; 282 arrayIndex <<= 1; 283 } 284 285 // clear downwards to the biggest block 286 arrayIndex = index >> 1; 287 for (int32 i = arrayToUse + 1; i < fArrayCount; i++) { 288 fArray[i][arrayIndex]--; 289 if (fArray[i][arrayIndex] > 0) 290 break; 291 292 arrayIndex >>= 1; 293 } 294 295 _Unlock(); 296 return B_OK; 297 } 298 299 300 void 301 PhysicalMemoryAllocator::PrintToStream() 302 { 303 dprintf("PhysicalMemoryAllocator \"%s\":\n", fName); 304 dprintf("\tMin block size:\t\t\t%ld bytes\n", fBlockSize[0]); 305 dprintf("\tMax block size:\t\t\t%ld bytes\n", fBlockSize[fArrayCount - 1]); 306 dprintf("\tMin count per block:\t%ld\n\n", fArrayLength[fArrayCount - 1]); 307 dprintf("\tArray count:\t\t\t%ld\n", fArrayCount); 308 309 dprintf("\tArray slots:\t\t\t% 8ld", fArrayLength[0]); 310 for (int32 i = 1; i < fArrayCount; i++) 311 dprintf(", % 8ld", fArrayLength[i]); 312 dprintf("\n"); 313 DumpFreeSlots(); 314 315 dprintf("\tBlock sizes:\t\t\t% 8ld", fBlockSize[0]); 316 for (int32 i = 1; i < fArrayCount; i++) 317 dprintf(", % 8ld", fBlockSize[i]); 318 dprintf("\n"); 319 DumpLastArray(); 320 dprintf("\n"); 321 322 dprintf("\tManaged memory:\t\t\t%ld bytes\n", fManagedMemory); 323 dprintf("\tGranularity:\t\t\t%ld bytes\n", fBlockSize[0]); 324 dprintf("\tMemory overhead:\t\t%ld bytes\n", fOverhead); 325 } 326 327 328 void 329 PhysicalMemoryAllocator::DumpArrays() 330 { 331 uint32 padding = 2; 332 for (int32 i = 0; i < fArrayCount; i++) { 333 dprintf("\tArray(%ld):\t", i); 334 for (size_t j = 0; j < fArrayLength[i]; j++) { 335 if (padding > 2) { 336 for (uint32 k = 0; k < (padding - 2) / 4; k++) 337 dprintf(" "); 338 dprintf("\\"); 339 for (uint32 k = 0; k < (padding - 2) / 4; k++) 340 dprintf("-"); 341 dprintf("%d", fArray[i][j]); 342 for (uint32 k = 0; k < (padding - 2) / 4; k++) 343 dprintf("-"); 344 dprintf("/"); 345 for (uint32 k = 0; k < (padding - 2) / 4 + 1; k++) 346 dprintf(" "); 347 } else { 348 dprintf("%d ", fArray[i][j]); 349 } 350 } 351 352 padding *= 2; 353 dprintf("\n"); 354 } 355 356 dprintf("\n"); 357 } 358 359 360 void 361 PhysicalMemoryAllocator::DumpLastArray() 362 { 363 dprintf("\tLast array:\t\t\t\t"); 364 for (size_t i = 0; i < fArrayLength[fArrayCount - 1]; i++) 365 dprintf("%d", fArray[fArrayCount - 1][i]); 366 dprintf("\n"); 367 } 368 369 370 void 371 PhysicalMemoryAllocator::DumpFreeSlots() 372 { 373 dprintf("\tFree slots:\t\t\t\t"); 374 for (int32 i = 0; i < fArrayCount; i++) { 375 uint32 freeSlots = 0; 376 for (size_t j = 0; j < fArrayLength[i]; j++) { 377 if (fArray[i][j] == 0) 378 freeSlots++; 379 } 380 381 if (i > 0) 382 dprintf(", % 8ld", freeSlots); 383 else 384 dprintf("% 8ld", freeSlots); 385 } 386 dprintf("\n"); 387 } 388