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