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 <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 fMemoryWaitersCount(0) 32 { 33 fName = strdup(name); 34 mutex_init_etc(&fLock, fName, MUTEX_FLAG_CLONE_NAME); 35 36 fArrayCount = 1; 37 size_t biggestSize = minSize; 38 while (biggestSize < maxSize) { 39 fArrayCount++; 40 biggestSize *= 2; 41 } 42 43 size_t size = fArrayCount * sizeof(uint8 *); 44 fArray = (uint8 **)malloc(size); 45 fOverhead += size; 46 47 size = fArrayCount * sizeof(size_t); 48 fBlockSize = (size_t *)malloc(size); 49 fArrayLength = (size_t *)malloc(size); 50 fArrayOffset = (size_t *)malloc(size); 51 fOverhead += size * 3; 52 53 size_t arraySlots = biggestSize / minSize; 54 for (int32 i = 0; i < fArrayCount; i++) { 55 size = arraySlots * minCountPerBlock * sizeof(uint8); 56 fArrayLength[i] = arraySlots * minCountPerBlock; 57 fBlockSize[i] = biggestSize / arraySlots; 58 fArrayOffset[i] = fArrayLength[i] - 1; 59 60 fArray[i] = (uint8 *)malloc(size); 61 memset(fArray[i], 0, fArrayLength[i]); 62 63 fOverhead += size; 64 arraySlots /= 2; 65 } 66 67 fManagedMemory = fBlockSize[0] * fArrayLength[0]; 68 69 size_t roundedSize = biggestSize * minCountPerBlock; 70 #ifdef HAIKU_TARGET_PLATFORM_HAIKU 71 fDebugBase = roundedSize; 72 fDebugChunkSize = 64; 73 fDebugUseMap = 0; 74 roundedSize += sizeof(fDebugUseMap) * 8 * fDebugChunkSize; 75 #endif 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, B_READ_AREA | B_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 #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 = (phys_addr_t)(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 if (!_Lock()) 168 return B_ERROR; 169 170 while (true) { 171 TRACE(("PMA: will use array %ld (blocksize: %ld) to allocate %ld bytes\n", arrayToUse, fBlockSize[arrayToUse], size)); 172 uint8 *targetArray = fArray[arrayToUse]; 173 uint32 arrayOffset = fArrayOffset[arrayToUse] % arrayLength; 174 for (size_t i = arrayOffset + 1; i != arrayOffset; i++) { 175 if (i >= arrayLength) 176 i -= arrayLength; 177 178 if (targetArray[i] == 0) { 179 // found a free slot 180 fArrayOffset[arrayToUse] = i; 181 182 // fill upwards to the smallest block 183 uint32 fillSize = 1; 184 uint32 arrayIndex = i; 185 for (int32 j = arrayToUse; j >= 0; j--) { 186 memset(&fArray[j][arrayIndex], 1, fillSize); 187 fillSize <<= 1; 188 arrayIndex <<= 1; 189 } 190 191 // fill downwards to the biggest block 192 arrayIndex = i >> 1; 193 for (int32 j = arrayToUse + 1; j < fArrayCount; j++) { 194 fArray[j][arrayIndex]++; 195 if (fArray[j][arrayIndex] > 1) 196 break; 197 198 arrayIndex >>= 1; 199 } 200 201 _Unlock(); 202 size_t offset = fBlockSize[arrayToUse] * i; 203 *logicalAddress = (void *)((uint8 *)fLogicalBase + offset); 204 *physicalAddress = (phys_addr_t)(fPhysicalBase + offset); 205 return B_OK; 206 } 207 } 208 209 // no slot found, we need to wait 210 211 ConditionVariableEntry entry; 212 fNoMemoryCondition.Add(&entry); 213 fMemoryWaitersCount++; 214 215 _Unlock(); 216 217 TRACE_ERROR(("PMA: found no free slot to store %ld bytes, waiting\n", 218 size)); 219 220 entry.Wait(); 221 222 if (!_Lock()) 223 return B_ERROR; 224 225 fMemoryWaitersCount--; 226 } 227 228 return B_NO_MEMORY; 229 } 230 231 232 status_t 233 PhysicalMemoryAllocator::Deallocate(size_t size, void *logicalAddress, 234 phys_addr_t physicalAddress) 235 { 236 #ifdef HAIKU_TARGET_PLATFORM_HAIKU 237 if (debug_debugger_running()) { 238 uint32 index = ((uint8 *)logicalAddress - (uint8 *)fLogicalBase 239 - fDebugBase) / fDebugChunkSize; 240 fDebugUseMap &= ~(1LL << index); 241 return B_OK; 242 } 243 #endif 244 245 if (size == 0 || size > fBlockSize[fArrayCount - 1]) { 246 TRACE_ERROR(("PMA: bad value for deallocate (%ld bytes)\n", size)); 247 return B_BAD_VALUE; 248 } 249 250 int32 arrayToUse = 0; 251 for (int32 i = 0; i < fArrayCount; i++) { 252 if (fBlockSize[i] >= size) { 253 arrayToUse = i; 254 break; 255 } 256 } 257 258 phys_addr_t offset; 259 if (logicalAddress) 260 offset = (addr_t)logicalAddress - (addr_t)fLogicalBase; 261 else if (physicalAddress) 262 offset = (addr_t)physicalAddress - fPhysicalBase; 263 else { 264 TRACE_ERROR(("PMA: no value given for either physical or logical address\n")); 265 return B_BAD_VALUE; 266 } 267 268 uint32 index = offset / fBlockSize[arrayToUse]; 269 if (index >= fArrayLength[arrayToUse]) { 270 TRACE_ERROR(("PMA: provided address resulted in invalid index\n")); 271 return B_BAD_VALUE; 272 } 273 274 TRACE(("PMA: will use array %ld (index: %ld) to deallocate %ld bytes\n", arrayToUse, index, size)); 275 if (fArray[arrayToUse][index] == 0) { 276 TRACE_ERROR(("PMA: address was not allocated!\n")); 277 return B_BAD_VALUE; 278 } 279 280 if (!_Lock()) 281 return B_ERROR; 282 283 // clear upwards to the smallest block 284 uint32 fillSize = 1; 285 uint32 arrayIndex = index; 286 for (int32 i = arrayToUse; i >= 0; i--) { 287 memset(&fArray[i][arrayIndex], 0, fillSize); 288 fillSize <<= 1; 289 arrayIndex <<= 1; 290 } 291 292 // clear downwards to the biggest block 293 arrayIndex = index >> 1; 294 for (int32 i = arrayToUse + 1; i < fArrayCount; i++) { 295 fArray[i][arrayIndex]--; 296 if (fArray[i][arrayIndex] > 0) 297 break; 298 299 arrayIndex >>= 1; 300 } 301 302 if (fMemoryWaitersCount > 0) 303 fNoMemoryCondition.NotifyAll(); 304 305 _Unlock(); 306 return B_OK; 307 } 308 309 310 void 311 PhysicalMemoryAllocator::PrintToStream() 312 { 313 dprintf("PhysicalMemoryAllocator \"%s\":\n", fName); 314 dprintf("\tMin block size:\t\t\t%ld bytes\n", fBlockSize[0]); 315 dprintf("\tMax block size:\t\t\t%ld bytes\n", fBlockSize[fArrayCount - 1]); 316 dprintf("\tMin count per block:\t%ld\n\n", fArrayLength[fArrayCount - 1]); 317 dprintf("\tArray count:\t\t\t%" B_PRId32 "\n", fArrayCount); 318 319 dprintf("\tArray slots:\t\t\t% 8ld", fArrayLength[0]); 320 for (int32 i = 1; i < fArrayCount; i++) 321 dprintf(", % 8ld", fArrayLength[i]); 322 dprintf("\n"); 323 DumpFreeSlots(); 324 325 dprintf("\tBlock sizes:\t\t\t% 8ld", fBlockSize[0]); 326 for (int32 i = 1; i < fArrayCount; i++) 327 dprintf(", % 8ld", fBlockSize[i]); 328 dprintf("\n"); 329 DumpLastArray(); 330 dprintf("\n"); 331 332 dprintf("\tManaged memory:\t\t\t%ld bytes\n", fManagedMemory); 333 dprintf("\tGranularity:\t\t\t%ld bytes\n", fBlockSize[0]); 334 dprintf("\tMemory overhead:\t\t%ld bytes\n", fOverhead); 335 } 336 337 338 void 339 PhysicalMemoryAllocator::DumpArrays() 340 { 341 uint32 padding = 2; 342 for (int32 i = 0; i < fArrayCount; i++) { 343 dprintf("\tArray(%" B_PRId32 "):\t", i); 344 for (size_t j = 0; j < fArrayLength[i]; j++) { 345 if (padding > 2) { 346 for (uint32 k = 0; k < (padding - 2) / 4; k++) 347 dprintf(" "); 348 dprintf("\\"); 349 for (uint32 k = 0; k < (padding - 2) / 4; k++) 350 dprintf("-"); 351 dprintf("%d", fArray[i][j]); 352 for (uint32 k = 0; k < (padding - 2) / 4; k++) 353 dprintf("-"); 354 dprintf("/"); 355 for (uint32 k = 0; k < (padding - 2) / 4 + 1; k++) 356 dprintf(" "); 357 } else { 358 dprintf("%d ", fArray[i][j]); 359 } 360 } 361 362 padding *= 2; 363 dprintf("\n"); 364 } 365 366 dprintf("\n"); 367 } 368 369 370 void 371 PhysicalMemoryAllocator::DumpLastArray() 372 { 373 dprintf("\tLast array:\t\t\t\t"); 374 for (size_t i = 0; i < fArrayLength[fArrayCount - 1]; i++) 375 dprintf("%d", fArray[fArrayCount - 1][i]); 376 dprintf("\n"); 377 } 378 379 380 void 381 PhysicalMemoryAllocator::DumpFreeSlots() 382 { 383 dprintf("\tFree slots:\t\t\t\t"); 384 for (int32 i = 0; i < fArrayCount; i++) { 385 uint32 freeSlots = 0; 386 for (size_t j = 0; j < fArrayLength[i]; j++) { 387 if (fArray[i][j] == 0) 388 freeSlots++; 389 } 390 391 if (i > 0) 392 dprintf(", %8" B_PRIu32, freeSlots); 393 else 394 dprintf("%8" B_PRIu32, freeSlots); 395 } 396 dprintf("\n"); 397 } 398