1/*
2 * Copyright 2006-2012, Haiku, Inc. All Rights Reserved.
3 * Distributed under the terms of the MIT License.
4 *
5 * Authors:
6 *		Axel D��rfler, axeld@pinc-software.de
7 */
8
9
10/*!	This class manages a pool of areas for one client. The client is supposed
11	to clone these areas into its own address space to access the data.
12	This mechanism is only used for bitmaps for far.
13*/
14
15
16// TODO: areas could be relocated if needed (to be able to resize them)
17//		However, this would require a lock whenever a block of memory
18//		allocated by this allocator is accessed.
19
20
21#include "ClientMemoryAllocator.h"
22
23#include <stdio.h>
24#include <stdlib.h>
25
26#include <Autolock.h>
27
28#include "ServerApp.h"
29
30
31typedef block_list::Iterator block_iterator;
32typedef chunk_list::Iterator chunk_iterator;
33
34
35ClientMemoryAllocator::ClientMemoryAllocator(ServerApp* application)
36	:
37	fApplication(application),
38	fLock("client memory lock")
39{
40}
41
42
43ClientMemoryAllocator::~ClientMemoryAllocator()
44{
45	// delete all areas and chunks/blocks that are still allocated
46
47	while (true) {
48		struct block* block = fFreeBlocks.RemoveHead();
49		if (block == NULL)
50			break;
51
52		free(block);
53	}
54
55	while (true) {
56		struct chunk* chunk = fChunks.RemoveHead();
57		if (chunk == NULL)
58			break;
59
60		delete_area(chunk->area);
61		free(chunk);
62	}
63}
64
65
66void*
67ClientMemoryAllocator::Allocate(size_t size, block** _address, bool& newArea)
68{
69	BAutolock locker(fLock);
70
71	// Search best matching free block from the list
72
73	block_iterator iterator = fFreeBlocks.GetIterator();
74	struct block* block;
75	struct block* best = NULL;
76
77	while ((block = iterator.Next()) != NULL) {
78		if (block->size >= size && (best == NULL || block->size < best->size))
79			best = block;
80	}
81
82	if (best == NULL) {
83		// We didn't find a free block - we need to allocate
84		// another chunk, or resize an existing chunk
85		best = _AllocateChunk(size, newArea);
86		if (best == NULL)
87			return NULL;
88	} else
89		newArea = false;
90
91	// We need to split the chunk into two parts: the one to keep
92	// and the one to give away
93
94	if (best->size == size) {
95		// The simple case: the free block has exactly the size we wanted to have
96		fFreeBlocks.Remove(best);
97		*_address = best;
98		return best->base;
99	}
100
101	// TODO: maybe we should have the user reserve memory in its object
102	//	for us, so we don't have to do this here...
103
104	struct block* usedBlock = (struct block*)malloc(sizeof(struct block));
105	if (usedBlock == NULL)
106		return NULL;
107
108	usedBlock->base = best->base;
109	usedBlock->size = size;
110	usedBlock->chunk = best->chunk;
111
112	best->base += size;
113	best->size -= size;
114
115	*_address = usedBlock;
116	return usedBlock->base;
117}
118
119
120void
121ClientMemoryAllocator::Free(block* freeBlock)
122{
123	if (freeBlock == NULL)
124		return;
125
126	BAutolock locker(fLock);
127
128	// search for an adjacent free block
129
130	block_iterator iterator = fFreeBlocks.GetIterator();
131	struct block* before = NULL;
132	struct block* after = NULL;
133	bool inFreeList = true;
134
135	if (freeBlock->size != freeBlock->chunk->size) {
136		// TODO: this could be done better if free blocks are sorted,
137		//	and if we had one free blocks list per chunk!
138		//	IOW this is a bit slow...
139
140		while (struct block* block = iterator.Next()) {
141			if (block->chunk != freeBlock->chunk)
142				continue;
143
144			if (block->base + block->size == freeBlock->base)
145				before = block;
146
147			if (block->base == freeBlock->base + freeBlock->size)
148				after = block;
149		}
150
151		if (before != NULL && after != NULL) {
152			// merge with adjacent blocks
153			before->size += after->size + freeBlock->size;
154			fFreeBlocks.Remove(after);
155			free(after);
156			free(freeBlock);
157			freeBlock = before;
158		} else if (before != NULL) {
159			before->size += freeBlock->size;
160			free(freeBlock);
161			freeBlock = before;
162		} else if (after != NULL) {
163			after->base -= freeBlock->size;
164			after->size += freeBlock->size;
165			free(freeBlock);
166			freeBlock = after;
167		} else
168			fFreeBlocks.Add(freeBlock);
169	} else
170		inFreeList = false;
171
172	if (freeBlock->size == freeBlock->chunk->size) {
173		// We can delete the chunk now
174		struct chunk* chunk = freeBlock->chunk;
175
176		if (inFreeList)
177			fFreeBlocks.Remove(freeBlock);
178		free(freeBlock);
179
180		fChunks.Remove(chunk);
181		delete_area(chunk->area);
182		fApplication->NotifyDeleteClientArea(chunk->area);
183
184		free(chunk);
185	}
186}
187
188
189void
190ClientMemoryAllocator::Dump()
191{
192	debug_printf("Application %" B_PRId32 ", %s: chunks:\n",
193		fApplication->ClientTeam(), fApplication->Signature());
194
195	chunk_list::Iterator iterator = fChunks.GetIterator();
196	int32 i = 0;
197	while (struct chunk* chunk = iterator.Next()) {
198		debug_printf("  [%4" B_PRId32 "] %p, area %" B_PRId32 ", base %p, "
199			"size %lu\n", i++, chunk, chunk->area, chunk->base, chunk->size);
200	}
201
202	debug_printf("free blocks:\n");
203
204	block_list::Iterator blockIterator = fFreeBlocks.GetIterator();
205	i = 0;
206	while (struct block* block = blockIterator.Next()) {
207		debug_printf("  [%6" B_PRId32 "] %p, chunk %p, base %p, size %lu\n",
208			i++, block, block->chunk, block->base, block->size);
209	}
210}
211
212
213struct block*
214ClientMemoryAllocator::_AllocateChunk(size_t size, bool& newArea)
215{
216	// round up to multiple of page size
217	size = (size + B_PAGE_SIZE - 1) & ~(B_PAGE_SIZE - 1);
218
219	// At first, try to resize our existing areas
220
221	chunk_iterator iterator = fChunks.GetIterator();
222	struct chunk* chunk;
223	while ((chunk = iterator.Next()) != NULL) {
224		status_t status = resize_area(chunk->area, chunk->size + size);
225		if (status == B_OK) {
226			newArea = false;
227			break;
228		}
229	}
230
231	// TODO: resize and relocate while holding the write lock
232
233	struct block* block;
234	uint8* address;
235
236	if (chunk == NULL) {
237		// TODO: temporary measurement as long as resizing areas doesn't
238		//	work the way we need (with relocating the area, if needed)
239		if (size < B_PAGE_SIZE * 32)
240			size = B_PAGE_SIZE * 32;
241
242		// create new area for this allocation
243		chunk = (struct chunk*)malloc(sizeof(struct chunk));
244		if (chunk == NULL)
245			return NULL;
246
247		block = (struct block*)malloc(sizeof(struct block));
248		if (block == NULL) {
249			free(chunk);
250			return NULL;
251		}
252
253		char name[B_OS_NAME_LENGTH];
254#ifdef HAIKU_TARGET_PLATFORM_LIBBE_TEST
255		strcpy(name, "client heap");
256#else
257		snprintf(name, sizeof(name), "heap:%" B_PRId32 ":%s",
258			fApplication->ClientTeam(), fApplication->SignatureLeaf());
259#endif
260		area_id area = create_area(name, (void**)&address, B_ANY_ADDRESS, size,
261			B_NO_LOCK, B_READ_AREA | B_WRITE_AREA);
262		if (area < B_OK) {
263			free(block);
264			free(chunk);
265			return NULL;
266		}
267
268		// add chunk to list
269
270		chunk->area = area;
271		chunk->base = address;
272		chunk->size = size;
273
274		fChunks.Add(chunk);
275		newArea = true;
276	} else {
277		// create new free block for this chunk
278		block = (struct block *)malloc(sizeof(struct block));
279		if (block == NULL)
280			return NULL;
281
282		address = chunk->base + chunk->size;
283		chunk->size += size;
284	}
285
286	// add block to free list
287
288	block->chunk = chunk;
289	block->base = address;
290	block->size = size;
291
292	fFreeBlocks.Add(block);
293
294	return block;
295}
296
297
298// #pragma mark -
299
300
301ClientMemory::ClientMemory()
302	:
303	fBlock(NULL)
304{
305}
306
307
308ClientMemory::~ClientMemory()
309{
310	if (fBlock != NULL)
311		fAllocator->Free(fBlock);
312}
313
314
315void*
316ClientMemory::Allocate(ClientMemoryAllocator* allocator, size_t size,
317	bool& newArea)
318{
319	fAllocator = allocator;
320	return fAllocator->Allocate(size, &fBlock, newArea);
321}
322
323
324area_id
325ClientMemory::Area()
326{
327	if (fBlock != NULL)
328		return fBlock->chunk->area;
329	return B_ERROR;
330}
331
332
333uint8*
334ClientMemory::Address()
335{
336	if (fBlock != NULL)
337		return fBlock->base;
338	return 0;
339}
340
341
342uint32
343ClientMemory::AreaOffset()
344{
345	if (fBlock != NULL)
346		return fBlock->base - fBlock->chunk->base;
347	return 0;
348}
349
350
351// #pragma mark -
352
353
354ClonedAreaMemory::ClonedAreaMemory()
355	:
356	fClonedArea(-1),
357	fOffset(0),
358	fBase(NULL)
359{
360}
361
362
363ClonedAreaMemory::~ClonedAreaMemory()
364{
365	if (fClonedArea >= 0)
366		delete_area(fClonedArea);
367}
368
369
370void*
371ClonedAreaMemory::Clone(area_id area, uint32 offset)
372{
373	fClonedArea = clone_area("server_memory", (void**)&fBase, B_ANY_ADDRESS,
374		B_READ_AREA | B_WRITE_AREA, area);
375	if (fBase == NULL)
376		return NULL;
377	fOffset = offset;
378	return Address();
379}
380
381
382area_id
383ClonedAreaMemory::Area()
384{
385	return fClonedArea;
386}
387
388
389uint8*
390ClonedAreaMemory::Address()
391{
392	return fBase + fOffset;
393}
394
395
396uint32
397ClonedAreaMemory::AreaOffset()
398{
399	return fOffset;
400}
401