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