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