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