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