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/AutoLock.h> 14 #include <util/kernel_cpp.h> 15 16 #include "PhysicalMemoryAllocator.h" 17 18 19 //#define TRACE_PHYSICAL_MEMORY_ALLOCATOR 20 #ifdef TRACE_PHYSICAL_MEMORY_ALLOCATOR 21 #define TRACE(x) dprintf x 22 #define TRACE_ERROR(x) dprintf x 23 #else 24 #define TRACE(x) /* nothing */ 25 #define TRACE_ERROR(x) dprintf x 26 #endif 27 28 29 PhysicalMemoryAllocator::PhysicalMemoryAllocator(const char *name, 30 size_t minSize, size_t maxSize, uint32 minCountPerBlock) 31 : fOverhead(0), 32 fStatus(B_NO_INIT), 33 fMemoryWaitersCount(0) 34 { 35 fName = strdup(name); 36 mutex_init_etc(&fLock, fName, MUTEX_FLAG_CLONE_NAME); 37 38 fArrayCount = 1; 39 size_t biggestSize = minSize; 40 while (biggestSize < maxSize) { 41 fArrayCount++; 42 biggestSize *= 2; 43 } 44 45 size_t size = fArrayCount * sizeof(uint8 *); 46 fArray = (uint8 **)malloc(size); 47 fOverhead += size; 48 49 size = fArrayCount * sizeof(size_t); 50 fBlockSize = (size_t *)malloc(size); 51 fArrayLength = (size_t *)malloc(size); 52 fArrayOffset = (size_t *)malloc(size); 53 fOverhead += size * 3; 54 55 size_t arraySlots = biggestSize / minSize; 56 for (int32 i = 0; i < fArrayCount; i++) { 57 size = arraySlots * minCountPerBlock * sizeof(uint8); 58 fArrayLength[i] = arraySlots * minCountPerBlock; 59 fBlockSize[i] = biggestSize / arraySlots; 60 fArrayOffset[i] = fArrayLength[i] - 1; 61 62 fArray[i] = (uint8 *)malloc(size); 63 memset(fArray[i], 0, fArrayLength[i]); 64 65 fOverhead += size; 66 arraySlots /= 2; 67 } 68 69 fManagedMemory = fBlockSize[0] * fArrayLength[0]; 70 71 size_t roundedSize = biggestSize * minCountPerBlock; 72 fDebugBase = roundedSize; 73 fDebugChunkSize = 128; 74 fDebugUseMap = 0; 75 roundedSize += sizeof(fDebugUseMap) * 8 * fDebugChunkSize; 76 roundedSize = (roundedSize + B_PAGE_SIZE - 1) & ~(B_PAGE_SIZE - 1); 77 78 fArea = create_area(fName, &fLogicalBase, B_ANY_KERNEL_ADDRESS, 79 roundedSize, B_32_BIT_CONTIGUOUS, 80 B_KERNEL_READ_AREA | B_KERNEL_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 mutex_lock(&fLock); 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 status_t 118 PhysicalMemoryAllocator::Allocate(size_t size, void **logicalAddress, 119 phys_addr_t *physicalAddress) 120 { 121 if (debug_debugger_running()) { 122 if (size > fDebugChunkSize) { 123 kprintf("usb allocation of %" B_PRIuSIZE 124 " does not fit debug chunk size %" B_PRIu32 "!\n", 125 size, fDebugChunkSize); 126 return B_NO_MEMORY; 127 } 128 129 for (size_t i = 0; i < sizeof(fDebugUseMap) * 8; i++) { 130 uint64 mask = 1LL << i; 131 if ((fDebugUseMap & mask) == 0) { 132 fDebugUseMap |= mask; 133 *logicalAddress = (void *)((uint8 *)fLogicalBase + fDebugBase 134 + i * fDebugChunkSize); 135 *physicalAddress = (phys_addr_t)(fPhysicalBase + fDebugBase 136 + i * fDebugChunkSize); 137 return B_OK; 138 } 139 } 140 141 return B_NO_MEMORY; 142 } 143 144 if (size == 0 || size > fBlockSize[fArrayCount - 1]) { 145 TRACE_ERROR(("PMA: bad value for allocate (%ld bytes)\n", size)); 146 return B_BAD_VALUE; 147 } 148 149 size_t arrayLength = 0; 150 int32 arrayToUse = 0; 151 for (int32 i = 0; i < fArrayCount; i++) { 152 if (fBlockSize[i] >= size) { 153 arrayToUse = i; 154 arrayLength = fArrayLength[i]; 155 break; 156 } 157 } 158 159 MutexLocker locker(&fLock); 160 if (!locker.IsLocked()) 161 return B_ERROR; 162 163 const bigtime_t limit = system_time() + 2 * 1000 * 1000; 164 do { 165 TRACE(("PMA: will use array %ld (blocksize: %ld) to allocate %ld bytes\n", arrayToUse, fBlockSize[arrayToUse], size)); 166 uint8 *targetArray = fArray[arrayToUse]; 167 uint32 arrayOffset = fArrayOffset[arrayToUse] % arrayLength; 168 for (size_t i = arrayOffset + 1; i != arrayOffset; i++) { 169 if (i >= arrayLength) 170 i -= arrayLength; 171 172 if (targetArray[i] == 0) { 173 // found a free slot 174 fArrayOffset[arrayToUse] = i; 175 176 // fill upwards to the smallest block 177 uint32 fillSize = 1; 178 uint32 arrayIndex = i; 179 for (int32 j = arrayToUse; j >= 0; j--) { 180 memset(&fArray[j][arrayIndex], 1, fillSize); 181 fillSize <<= 1; 182 arrayIndex <<= 1; 183 } 184 185 // fill downwards to the biggest block 186 arrayIndex = i >> 1; 187 for (int32 j = arrayToUse + 1; j < fArrayCount; j++) { 188 fArray[j][arrayIndex]++; 189 if (fArray[j][arrayIndex] > 1) 190 break; 191 192 arrayIndex >>= 1; 193 } 194 195 size_t offset = fBlockSize[arrayToUse] * i; 196 *logicalAddress = (void *)((uint8 *)fLogicalBase + offset); 197 *physicalAddress = (phys_addr_t)(fPhysicalBase + offset); 198 return B_OK; 199 } 200 } 201 202 // no slot found, we need to wait 203 204 ConditionVariableEntry entry; 205 fNoMemoryCondition.Add(&entry); 206 fMemoryWaitersCount++; 207 208 locker.Unlock(); 209 210 TRACE_ERROR(("PMA: found no free slot to store %ld bytes, waiting\n", 211 size)); 212 213 if (entry.Wait(B_RELATIVE_TIMEOUT, 1 * 1000 * 1000) == B_TIMED_OUT) 214 break; 215 216 if (!locker.Lock()) 217 return B_ERROR; 218 219 fMemoryWaitersCount--; 220 } while (system_time() < limit); 221 222 TRACE_ERROR(("PMA: timed out waiting for a free slot, giving up\n")); 223 return B_NO_MEMORY; 224 } 225 226 227 status_t 228 PhysicalMemoryAllocator::Deallocate(size_t size, void *logicalAddress, 229 phys_addr_t physicalAddress) 230 { 231 if (debug_debugger_running()) { 232 uint32 index = ((uint8 *)logicalAddress - (uint8 *)fLogicalBase 233 - fDebugBase) / fDebugChunkSize; 234 fDebugUseMap &= ~(1LL << index); 235 return B_OK; 236 } 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 phys_addr_t offset; 252 if (logicalAddress) 253 offset = (addr_t)logicalAddress - (addr_t)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 MutexLocker _(&fLock); 274 if (!_.IsLocked()) 275 return B_ERROR; 276 277 // clear upwards to the smallest block 278 uint32 fillSize = 1; 279 uint32 arrayIndex = index; 280 for (int32 i = arrayToUse; i >= 0; i--) { 281 memset(&fArray[i][arrayIndex], 0, fillSize); 282 fillSize <<= 1; 283 arrayIndex <<= 1; 284 } 285 286 // clear downwards to the biggest block 287 arrayIndex = index >> 1; 288 for (int32 i = arrayToUse + 1; i < fArrayCount; i++) { 289 fArray[i][arrayIndex]--; 290 if (fArray[i][arrayIndex] > 0) 291 break; 292 293 arrayIndex >>= 1; 294 } 295 296 if (fMemoryWaitersCount > 0) 297 fNoMemoryCondition.NotifyAll(); 298 299 return B_OK; 300 } 301 302 303 void 304 PhysicalMemoryAllocator::PrintToStream() 305 { 306 dprintf("PhysicalMemoryAllocator \"%s\":\n", fName); 307 dprintf("\tMin block size:\t\t\t%ld bytes\n", fBlockSize[0]); 308 dprintf("\tMax block size:\t\t\t%ld bytes\n", fBlockSize[fArrayCount - 1]); 309 dprintf("\tMin count per block:\t%ld\n\n", fArrayLength[fArrayCount - 1]); 310 dprintf("\tArray count:\t\t\t%" B_PRId32 "\n", fArrayCount); 311 312 dprintf("\tArray slots:\t\t\t% 8ld", fArrayLength[0]); 313 for (int32 i = 1; i < fArrayCount; i++) 314 dprintf(", % 8ld", fArrayLength[i]); 315 dprintf("\n"); 316 DumpFreeSlots(); 317 318 dprintf("\tBlock sizes:\t\t\t% 8ld", fBlockSize[0]); 319 for (int32 i = 1; i < fArrayCount; i++) 320 dprintf(", % 8ld", fBlockSize[i]); 321 dprintf("\n"); 322 DumpLastArray(); 323 dprintf("\n"); 324 325 dprintf("\tManaged memory:\t\t\t%ld bytes\n", fManagedMemory); 326 dprintf("\tGranularity:\t\t\t%ld bytes\n", fBlockSize[0]); 327 dprintf("\tMemory overhead:\t\t%ld bytes\n", fOverhead); 328 } 329 330 331 void 332 PhysicalMemoryAllocator::DumpArrays() 333 { 334 uint32 padding = 2; 335 for (int32 i = 0; i < fArrayCount; i++) { 336 dprintf("\tArray(%" B_PRId32 "):\t", i); 337 for (size_t j = 0; j < fArrayLength[i]; j++) { 338 if (padding > 2) { 339 for (uint32 k = 0; k < (padding - 2) / 4; k++) 340 dprintf(" "); 341 dprintf("\\"); 342 for (uint32 k = 0; k < (padding - 2) / 4; k++) 343 dprintf("-"); 344 dprintf("%d", fArray[i][j]); 345 for (uint32 k = 0; k < (padding - 2) / 4; k++) 346 dprintf("-"); 347 dprintf("/"); 348 for (uint32 k = 0; k < (padding - 2) / 4 + 1; k++) 349 dprintf(" "); 350 } else { 351 dprintf("%d ", fArray[i][j]); 352 } 353 } 354 355 padding *= 2; 356 dprintf("\n"); 357 } 358 359 dprintf("\n"); 360 } 361 362 363 void 364 PhysicalMemoryAllocator::DumpLastArray() 365 { 366 dprintf("\tLast array:\t\t\t\t"); 367 for (size_t i = 0; i < fArrayLength[fArrayCount - 1]; i++) 368 dprintf("%d", fArray[fArrayCount - 1][i]); 369 dprintf("\n"); 370 } 371 372 373 void 374 PhysicalMemoryAllocator::DumpFreeSlots() 375 { 376 dprintf("\tFree slots:\t\t\t\t"); 377 for (int32 i = 0; i < fArrayCount; i++) { 378 uint32 freeSlots = 0; 379 for (size_t j = 0; j < fArrayLength[i]; j++) { 380 if (fArray[i][j] == 0) 381 freeSlots++; 382 } 383 384 if (i > 0) 385 dprintf(", %8" B_PRIu32, freeSlots); 386 else 387 dprintf("%8" B_PRIu32, freeSlots); 388 } 389 dprintf("\n"); 390 } 391