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 <SupportDefs.h>
13 #include <util/AutoLock.h>
14 #include <util/kernel_cpp.h>
15
16 #include "PhysicalMemoryAllocator.h"
17
18
19 //#define TRACE_PHYSICAL_MEMORY_ALLOCATOR
20 #ifdef TRACE_PHYSICAL_MEMORY_ALLOCATOR
21 #define TRACE(x) dprintf x
22 #define TRACE_ERROR(x) dprintf x
23 #else
24 #define TRACE(x) /* nothing */
25 #define TRACE_ERROR(x) dprintf x
26 #endif
27
28
PhysicalMemoryAllocator(const char * name,size_t minSize,size_t maxSize,uint32 minCountPerBlock)29 PhysicalMemoryAllocator::PhysicalMemoryAllocator(const char *name,
30 size_t minSize, size_t maxSize, uint32 minCountPerBlock)
31 : fOverhead(0),
32 fStatus(B_NO_INIT),
33 fMemoryWaitersCount(0)
34 {
35 fName = strdup(name);
36 mutex_init_etc(&fLock, fName, MUTEX_FLAG_CLONE_NAME);
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 fDebugBase = roundedSize;
73 fDebugChunkSize = 128;
74 fDebugUseMap = 0;
75 roundedSize += sizeof(fDebugUseMap) * 8 * fDebugChunkSize;
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,
80 B_KERNEL_READ_AREA | B_KERNEL_WRITE_AREA);
81 if (fArea < B_OK) {
82 TRACE_ERROR(("PMA: failed to create memory area\n"));
83 return;
84 }
85
86 physical_entry physicalEntry;
87 if (get_memory_map(fLogicalBase, roundedSize, &physicalEntry, 1) < B_OK) {
88 TRACE_ERROR(("PMA: failed to get memory map\n"));
89 return;
90 }
91
92 fPhysicalBase = physicalEntry.address;
93
94 fNoMemoryCondition.Init(this, "USB PMA");
95 fStatus = B_OK;
96 }
97
98
~PhysicalMemoryAllocator()99 PhysicalMemoryAllocator::~PhysicalMemoryAllocator()
100 {
101 mutex_lock(&fLock);
102
103 for (int32 i = 0; i < fArrayCount; i++)
104 free(fArray[i]);
105
106 free(fArray);
107 free(fArrayLength);
108 free(fBlockSize);
109 free(fArrayOffset);
110 free(fName);
111
112 delete_area(fArea);
113 mutex_destroy(&fLock);
114 }
115
116
117 status_t
Allocate(size_t size,void ** logicalAddress,phys_addr_t * physicalAddress)118 PhysicalMemoryAllocator::Allocate(size_t size, void **logicalAddress,
119 phys_addr_t *physicalAddress)
120 {
121 if (debug_debugger_running()) {
122 if (size > fDebugChunkSize) {
123 kprintf("usb allocation of %" B_PRIuSIZE
124 " does not fit debug chunk size %" B_PRIu32 "!\n",
125 size, fDebugChunkSize);
126 return B_NO_MEMORY;
127 }
128
129 for (size_t i = 0; i < sizeof(fDebugUseMap) * 8; i++) {
130 uint64 mask = 1LL << i;
131 if ((fDebugUseMap & mask) == 0) {
132 fDebugUseMap |= mask;
133 *logicalAddress = (void *)((uint8 *)fLogicalBase + fDebugBase
134 + i * fDebugChunkSize);
135 *physicalAddress = (phys_addr_t)(fPhysicalBase + fDebugBase
136 + i * fDebugChunkSize);
137 return B_OK;
138 }
139 }
140
141 return B_NO_MEMORY;
142 }
143
144 if (size == 0 || size > fBlockSize[fArrayCount - 1]) {
145 TRACE_ERROR(("PMA: bad value for allocate (%ld bytes)\n", size));
146 return B_BAD_VALUE;
147 }
148
149 size_t arrayLength = 0;
150 int32 arrayToUse = 0;
151 for (int32 i = 0; i < fArrayCount; i++) {
152 if (fBlockSize[i] >= size) {
153 arrayToUse = i;
154 arrayLength = fArrayLength[i];
155 break;
156 }
157 }
158
159 MutexLocker locker(&fLock);
160 if (!locker.IsLocked())
161 return B_ERROR;
162
163 const bigtime_t limit = system_time() + 2 * 1000 * 1000;
164 do {
165 TRACE(("PMA: will use array %ld (blocksize: %ld) to allocate %ld bytes\n", arrayToUse, fBlockSize[arrayToUse], size));
166 uint8 *targetArray = fArray[arrayToUse];
167 uint32 arrayOffset = fArrayOffset[arrayToUse] % arrayLength;
168 for (size_t i = arrayOffset + 1; i != arrayOffset; i++) {
169 if (i >= arrayLength)
170 i -= arrayLength;
171
172 if (targetArray[i] == 0) {
173 // found a free slot
174 fArrayOffset[arrayToUse] = i;
175
176 // fill upwards to the smallest block
177 uint32 fillSize = 1;
178 uint32 arrayIndex = i;
179 for (int32 j = arrayToUse; j >= 0; j--) {
180 memset(&fArray[j][arrayIndex], 1, fillSize);
181 fillSize <<= 1;
182 arrayIndex <<= 1;
183 }
184
185 // fill downwards to the biggest block
186 arrayIndex = i >> 1;
187 for (int32 j = arrayToUse + 1; j < fArrayCount; j++) {
188 fArray[j][arrayIndex]++;
189 if (fArray[j][arrayIndex] > 1)
190 break;
191
192 arrayIndex >>= 1;
193 }
194
195 size_t offset = fBlockSize[arrayToUse] * i;
196 *logicalAddress = (void *)((uint8 *)fLogicalBase + offset);
197 *physicalAddress = (phys_addr_t)(fPhysicalBase + offset);
198 return B_OK;
199 }
200 }
201
202 // no slot found, we need to wait
203
204 ConditionVariableEntry entry;
205 fNoMemoryCondition.Add(&entry);
206 fMemoryWaitersCount++;
207
208 locker.Unlock();
209
210 TRACE_ERROR(("PMA: found no free slot to store %ld bytes, waiting\n",
211 size));
212
213 if (entry.Wait(B_RELATIVE_TIMEOUT, 1 * 1000 * 1000) == B_TIMED_OUT)
214 break;
215
216 if (!locker.Lock())
217 return B_ERROR;
218
219 fMemoryWaitersCount--;
220 } while (system_time() < limit);
221
222 TRACE_ERROR(("PMA: timed out waiting for a free slot, giving up\n"));
223 return B_NO_MEMORY;
224 }
225
226
227 status_t
Deallocate(size_t size,void * logicalAddress,phys_addr_t physicalAddress)228 PhysicalMemoryAllocator::Deallocate(size_t size, void *logicalAddress,
229 phys_addr_t physicalAddress)
230 {
231 if (debug_debugger_running()) {
232 uint32 index = ((uint8 *)logicalAddress - (uint8 *)fLogicalBase
233 - fDebugBase) / fDebugChunkSize;
234 fDebugUseMap &= ~(1LL << index);
235 return B_OK;
236 }
237
238 if (size == 0 || size > fBlockSize[fArrayCount - 1]) {
239 TRACE_ERROR(("PMA: bad value for deallocate (%ld bytes)\n", size));
240 return B_BAD_VALUE;
241 }
242
243 int32 arrayToUse = 0;
244 for (int32 i = 0; i < fArrayCount; i++) {
245 if (fBlockSize[i] >= size) {
246 arrayToUse = i;
247 break;
248 }
249 }
250
251 phys_addr_t offset;
252 if (logicalAddress)
253 offset = (addr_t)logicalAddress - (addr_t)fLogicalBase;
254 else if (physicalAddress)
255 offset = (addr_t)physicalAddress - fPhysicalBase;
256 else {
257 TRACE_ERROR(("PMA: no value given for either physical or logical address\n"));
258 return B_BAD_VALUE;
259 }
260
261 uint32 index = offset / fBlockSize[arrayToUse];
262 if (index >= fArrayLength[arrayToUse]) {
263 TRACE_ERROR(("PMA: provided address resulted in invalid index\n"));
264 return B_BAD_VALUE;
265 }
266
267 TRACE(("PMA: will use array %ld (index: %ld) to deallocate %ld bytes\n", arrayToUse, index, size));
268 if (fArray[arrayToUse][index] == 0) {
269 TRACE_ERROR(("PMA: address was not allocated!\n"));
270 return B_BAD_VALUE;
271 }
272
273 MutexLocker _(&fLock);
274 if (!_.IsLocked())
275 return B_ERROR;
276
277 // clear upwards to the smallest block
278 uint32 fillSize = 1;
279 uint32 arrayIndex = index;
280 for (int32 i = arrayToUse; i >= 0; i--) {
281 memset(&fArray[i][arrayIndex], 0, fillSize);
282 fillSize <<= 1;
283 arrayIndex <<= 1;
284 }
285
286 // clear downwards to the biggest block
287 arrayIndex = index >> 1;
288 for (int32 i = arrayToUse + 1; i < fArrayCount; i++) {
289 fArray[i][arrayIndex]--;
290 if (fArray[i][arrayIndex] > 0)
291 break;
292
293 arrayIndex >>= 1;
294 }
295
296 if (fMemoryWaitersCount > 0)
297 fNoMemoryCondition.NotifyAll();
298
299 return B_OK;
300 }
301
302
303 void
PrintToStream()304 PhysicalMemoryAllocator::PrintToStream()
305 {
306 dprintf("PhysicalMemoryAllocator \"%s\":\n", fName);
307 dprintf("\tMin block size:\t\t\t%ld bytes\n", fBlockSize[0]);
308 dprintf("\tMax block size:\t\t\t%ld bytes\n", fBlockSize[fArrayCount - 1]);
309 dprintf("\tMin count per block:\t%ld\n\n", fArrayLength[fArrayCount - 1]);
310 dprintf("\tArray count:\t\t\t%" B_PRId32 "\n", fArrayCount);
311
312 dprintf("\tArray slots:\t\t\t% 8ld", fArrayLength[0]);
313 for (int32 i = 1; i < fArrayCount; i++)
314 dprintf(", % 8ld", fArrayLength[i]);
315 dprintf("\n");
316 DumpFreeSlots();
317
318 dprintf("\tBlock sizes:\t\t\t% 8ld", fBlockSize[0]);
319 for (int32 i = 1; i < fArrayCount; i++)
320 dprintf(", % 8ld", fBlockSize[i]);
321 dprintf("\n");
322 DumpLastArray();
323 dprintf("\n");
324
325 dprintf("\tManaged memory:\t\t\t%ld bytes\n", fManagedMemory);
326 dprintf("\tGranularity:\t\t\t%ld bytes\n", fBlockSize[0]);
327 dprintf("\tMemory overhead:\t\t%ld bytes\n", fOverhead);
328 }
329
330
331 void
DumpArrays()332 PhysicalMemoryAllocator::DumpArrays()
333 {
334 uint32 padding = 2;
335 for (int32 i = 0; i < fArrayCount; i++) {
336 dprintf("\tArray(%" B_PRId32 "):\t", i);
337 for (size_t j = 0; j < fArrayLength[i]; j++) {
338 if (padding > 2) {
339 for (uint32 k = 0; k < (padding - 2) / 4; k++)
340 dprintf(" ");
341 dprintf("\\");
342 for (uint32 k = 0; k < (padding - 2) / 4; k++)
343 dprintf("-");
344 dprintf("%d", fArray[i][j]);
345 for (uint32 k = 0; k < (padding - 2) / 4; k++)
346 dprintf("-");
347 dprintf("/");
348 for (uint32 k = 0; k < (padding - 2) / 4 + 1; k++)
349 dprintf(" ");
350 } else {
351 dprintf("%d ", fArray[i][j]);
352 }
353 }
354
355 padding *= 2;
356 dprintf("\n");
357 }
358
359 dprintf("\n");
360 }
361
362
363 void
DumpLastArray()364 PhysicalMemoryAllocator::DumpLastArray()
365 {
366 dprintf("\tLast array:\t\t\t\t");
367 for (size_t i = 0; i < fArrayLength[fArrayCount - 1]; i++)
368 dprintf("%d", fArray[fArrayCount - 1][i]);
369 dprintf("\n");
370 }
371
372
373 void
DumpFreeSlots()374 PhysicalMemoryAllocator::DumpFreeSlots()
375 {
376 dprintf("\tFree slots:\t\t\t\t");
377 for (int32 i = 0; i < fArrayCount; i++) {
378 uint32 freeSlots = 0;
379 for (size_t j = 0; j < fArrayLength[i]; j++) {
380 if (fArray[i][j] == 0)
381 freeSlots++;
382 }
383
384 if (i > 0)
385 dprintf(", %8" B_PRIu32, freeSlots);
386 else
387 dprintf("%8" B_PRIu32, freeSlots);
388 }
389 dprintf("\n");
390 }
391