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
29PhysicalMemoryAllocator::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
99PhysicalMemoryAllocator::~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
117status_t
118PhysicalMemoryAllocator::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
227status_t
228PhysicalMemoryAllocator::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
303void
304PhysicalMemoryAllocator::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
331void
332PhysicalMemoryAllocator::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
363void
364PhysicalMemoryAllocator::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
373void
374PhysicalMemoryAllocator::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