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