1 /* 2 * Copyright 2006, 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 { 32 fName = strdup(name); 33 if (benaphore_init(&fLock, fName) < B_OK) { 34 TRACE_ERROR(("PMA: failed to create benaphore lock\n")); 35 return; 36 } 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 roundedSize = (roundedSize + B_PAGE_SIZE - 1) & ~(B_PAGE_SIZE - 1); 73 74 fArea = create_area(fName, &fLogicalBase, B_ANY_KERNEL_ADDRESS, 75 roundedSize, B_FULL_LOCK | B_CONTIGUOUS, B_READ_AREA | B_WRITE_AREA); 76 if (fArea < B_OK) { 77 TRACE_ERROR(("PMA: failed to create memory area\n")); 78 return; 79 } 80 81 physical_entry physicalEntry; 82 if (get_memory_map(fLogicalBase, roundedSize, &physicalEntry, 1) < B_OK) { 83 TRACE_ERROR(("PMA: failed to get memory map\n")); 84 return; 85 } 86 87 fPhysicalBase = physicalEntry.address; 88 fStatus = B_OK; 89 } 90 91 92 PhysicalMemoryAllocator::~PhysicalMemoryAllocator() 93 { 94 _Lock(); 95 96 for (int32 i = 0; i < fArrayCount; i++) 97 free(fArray[i]); 98 99 free(fArray); 100 free(fArrayLength); 101 free(fBlockSize); 102 free(fArrayOffset); 103 free(fName); 104 105 delete_area(fArea); 106 benaphore_destroy(&fLock); 107 } 108 109 110 bool 111 PhysicalMemoryAllocator::_Lock() 112 { 113 return (benaphore_lock(&fLock) == B_OK); 114 } 115 116 117 void 118 PhysicalMemoryAllocator::_Unlock() 119 { 120 benaphore_unlock(&fLock); 121 } 122 123 124 status_t 125 PhysicalMemoryAllocator::Allocate(size_t size, void **logicalAddress, 126 void **physicalAddress) 127 { 128 if (size == 0 || size > fBlockSize[fArrayCount - 1]) { 129 TRACE_ERROR(("PMA: bad value for allocate (%ld bytes)\n", size)); 130 return B_BAD_VALUE; 131 } 132 133 size_t arrayLength = 0; 134 int32 arrayToUse = 0; 135 for (int32 i = 0; i < fArrayCount; i++) { 136 if (fBlockSize[i] >= size) { 137 arrayToUse = i; 138 arrayLength = fArrayLength[i]; 139 break; 140 } 141 } 142 143 int32 retries = 5000; 144 while (retries-- > 0) { 145 if (!_Lock()) 146 return B_ERROR; 147 148 TRACE(("PMA: will use array %ld (blocksize: %ld) to allocate %ld bytes\n", arrayToUse, fBlockSize[arrayToUse], size)); 149 uint8 *targetArray = fArray[arrayToUse]; 150 uint32 arrayOffset = fArrayOffset[arrayToUse] % arrayLength; 151 for (size_t i = arrayOffset + 1; i != arrayOffset; i++) { 152 if (i >= arrayLength) 153 i -= arrayLength; 154 155 if (targetArray[i] == 0) { 156 // found a free slot 157 fArrayOffset[arrayToUse] = i; 158 159 // fill upwards to the smallest block 160 uint32 fillSize = 1; 161 uint32 arrayIndex = i; 162 for (int32 j = arrayToUse; j >= 0; j--) { 163 memset(&fArray[j][arrayIndex], 1, fillSize); 164 fillSize <<= 1; 165 arrayIndex <<= 1; 166 } 167 168 // fill downwards to the biggest block 169 arrayIndex = i >> 1; 170 for (int32 j = arrayToUse + 1; j < fArrayCount; j++) { 171 fArray[j][arrayIndex]++; 172 if (fArray[j][arrayIndex] > 1) 173 break; 174 175 arrayIndex >>= 1; 176 } 177 178 _Unlock(); 179 size_t offset = fBlockSize[arrayToUse] * i; 180 *logicalAddress = (void *)((uint8 *)fLogicalBase + offset); 181 *physicalAddress = (void *)((uint8 *)fPhysicalBase + offset); 182 return B_OK; 183 } 184 } 185 186 // no slot found 187 _Unlock(); 188 189 TRACE_ERROR(("PMA: found no free slot to store %ld bytes (%ld tries left)\n", size, retries)); 190 // we provide a scratch space here, memory will probably be freed 191 // as soon as some other transfer is completed and cleaned up. 192 // just wait a bit to give other threads a chance to free some slots. 193 snooze(100); 194 } 195 196 return B_NO_MEMORY; 197 } 198 199 200 status_t 201 PhysicalMemoryAllocator::Deallocate(size_t size, void *logicalAddress, 202 void *physicalAddress) 203 { 204 if (size == 0 || size > fBlockSize[fArrayCount - 1]) { 205 TRACE_ERROR(("PMA: bad value for deallocate (%ld bytes)\n", size)); 206 return B_BAD_VALUE; 207 } 208 209 int32 arrayToUse = 0; 210 for (int32 i = 0; i < fArrayCount; i++) { 211 if (fBlockSize[i] >= size) { 212 arrayToUse = i; 213 break; 214 } 215 } 216 217 uint32 offset; 218 if (logicalAddress) 219 offset = (uint32)logicalAddress - (uint32)fLogicalBase; 220 else if (physicalAddress) 221 offset = (uint32)physicalAddress - (uint32)fPhysicalBase; 222 else { 223 TRACE_ERROR(("PMA: no value given for either physical or logical address\n")); 224 return B_BAD_VALUE; 225 } 226 227 uint32 index = offset / fBlockSize[arrayToUse]; 228 if (index >= fArrayLength[arrayToUse]) { 229 TRACE_ERROR(("PMA: provided address resulted in invalid index\n")); 230 return B_BAD_VALUE; 231 } 232 233 TRACE(("PMA: will use array %ld (index: %ld) to deallocate %ld bytes\n", arrayToUse, index, size)); 234 if (fArray[arrayToUse][index] == 0) { 235 TRACE_ERROR(("PMA: address was not allocated!\n")); 236 return B_BAD_VALUE; 237 } 238 239 if (!_Lock()) 240 return B_ERROR; 241 242 // clear upwards to the smallest block 243 uint32 fillSize = 1; 244 uint32 arrayIndex = index; 245 for (int32 i = arrayToUse; i >= 0; i--) { 246 memset(&fArray[i][arrayIndex], 0, fillSize); 247 fillSize <<= 1; 248 arrayIndex <<= 1; 249 } 250 251 // clear downwards to the biggest block 252 arrayIndex = index >> 1; 253 for (int32 i = arrayToUse + 1; i < fArrayCount; i++) { 254 fArray[i][arrayIndex]--; 255 if (fArray[i][arrayIndex] > 0) 256 break; 257 258 arrayIndex >>= 1; 259 } 260 261 _Unlock(); 262 return B_OK; 263 } 264 265 266 void 267 PhysicalMemoryAllocator::PrintToStream() 268 { 269 dprintf("PhysicalMemoryAllocator \"%s\":\n", fName); 270 dprintf("\tMin block size:\t\t\t%ld bytes\n", fBlockSize[0]); 271 dprintf("\tMax block size:\t\t\t%ld bytes\n", fBlockSize[fArrayCount - 1]); 272 dprintf("\tMin count per block:\t%ld\n\n", fArrayLength[fArrayCount - 1]); 273 dprintf("\tArray count:\t\t\t%ld\n", fArrayCount); 274 275 dprintf("\tArray slots:\t\t\t% 8ld", fArrayLength[0]); 276 for (int32 i = 1; i < fArrayCount; i++) 277 dprintf(", % 8ld", fArrayLength[i]); 278 dprintf("\n"); 279 DumpFreeSlots(); 280 281 dprintf("\tBlock sizes:\t\t\t% 8ld", fBlockSize[0]); 282 for (int32 i = 1; i < fArrayCount; i++) 283 dprintf(", % 8ld", fBlockSize[i]); 284 dprintf("\n"); 285 DumpLastArray(); 286 dprintf("\n"); 287 288 dprintf("\tManaged memory:\t\t\t%ld bytes\n", fManagedMemory); 289 dprintf("\tGranularity:\t\t\t%ld bytes\n", fBlockSize[0]); 290 dprintf("\tMemory overhead:\t\t%ld bytes\n", fOverhead); 291 } 292 293 294 void 295 PhysicalMemoryAllocator::DumpArrays() 296 { 297 uint32 padding = 2; 298 for (int32 i = 0; i < fArrayCount; i++) { 299 dprintf("\tArray(%ld):\t", i); 300 for (size_t j = 0; j < fArrayLength[i]; j++) { 301 if (padding > 2) { 302 for (uint32 k = 0; k < (padding - 2) / 4; k++) 303 dprintf(" "); 304 dprintf("\\"); 305 for (uint32 k = 0; k < (padding - 2) / 4; k++) 306 dprintf("-"); 307 dprintf("%d", fArray[i][j]); 308 for (uint32 k = 0; k < (padding - 2) / 4; k++) 309 dprintf("-"); 310 dprintf("/"); 311 for (uint32 k = 0; k < (padding - 2) / 4 + 1; k++) 312 dprintf(" "); 313 } else { 314 dprintf("%d ", fArray[i][j]); 315 } 316 } 317 318 padding *= 2; 319 dprintf("\n"); 320 } 321 322 dprintf("\n"); 323 } 324 325 326 void 327 PhysicalMemoryAllocator::DumpLastArray() 328 { 329 dprintf("\tLast array:\t\t\t\t"); 330 for (size_t i = 0; i < fArrayLength[fArrayCount - 1]; i++) 331 dprintf("%d", fArray[fArrayCount - 1][i]); 332 dprintf("\n"); 333 } 334 335 336 void 337 PhysicalMemoryAllocator::DumpFreeSlots() 338 { 339 dprintf("\tFree slots:\t\t\t\t"); 340 for (int32 i = 0; i < fArrayCount; i++) { 341 uint32 freeSlots = 0; 342 for (size_t j = 0; j < fArrayLength[i]; j++) { 343 if (fArray[i][j] == 0) 344 freeSlots++; 345 } 346 347 if (i > 0) 348 dprintf(", % 8ld", freeSlots); 349 else 350 dprintf("% 8ld", freeSlots); 351 } 352 dprintf("\n"); 353 } 354