1/*
2 * Copyright 2006, Haiku Inc.
3 * Copyright 2002, Thomas Kurschel.
4 *
5 * Distributed under the terms of the MIT license.
6 */
7
8/**	Memory manager used for graphics mem
9 *
10 *	It has the following features
11 *	- doesn't access memory to be managed
12 *	- memory block's owner is identified by tag,
13 *	  tag is verified during free, and all memory
14 *	  belonging to one tag can be freed at once
15 *	- multi-threading save
16 */
17
18#include "memory_manager.h"
19
20#include <KernelExport.h>
21#include <stdlib.h>
22
23
24//#define TRACE_MEMORY_MANAGER
25#ifdef TRACE_MEMORY_MANAGER
26#	define TRACE(x) dprintf x
27#else
28#	define TRACE(x) ;
29#endif
30
31
32// allocated memory block
33typedef struct mem_block {
34	struct mem_block *prev, *next;
35	uint32 base;
36	uint32 size;
37	void *tag;
38	bool allocated;
39} mem_block;
40
41// memory heap
42struct mem_info {
43	mem_block *first;
44	area_id heap_area;
45	uint32 block_size;
46	sem_id lock;
47	mem_block *heap;
48	mem_block *unused;
49	uint32 heap_entries;
50};
51
52
53/** merge "block" with successor */
54
55static void
56merge(mem_info *mem, mem_block *block)
57{
58	mem_block *next = block->next;
59
60	block->size += next->size;
61
62	if (next->next)
63		next->next->prev = block;
64
65	block->next = next->next;
66	next->next = mem->unused;
67	mem->unused = next;
68}
69
70
71/** free memory block including merge */
72
73static mem_block *
74freeblock(mem_info *mem, mem_block *block)
75{
76	mem_block *prev, *next;
77
78	block->allocated = false;
79	prev = block->prev;
80
81	if (prev && !prev->allocated) {
82		block = prev;
83		merge(mem, prev);
84	}
85
86	next = block->next;
87
88	if (next && !next->allocated)
89		merge(mem, block);
90
91	return block;
92}
93
94
95//	#pragma mark -
96
97
98/** Init memory manager.
99 *
100 *	\param start start of address space
101 *	\param length length of address space
102 *	\param blockSize - granularity
103 *	\param heapEntries - maximum number of blocks
104 */
105
106mem_info *
107mem_init(const char* name, uint32 start, uint32 length,
108	uint32 blockSize, uint32 heapEntries)
109{
110	mem_block *first;
111	mem_info *mem;
112	uint i;
113	uint32 size;
114
115	TRACE(("mem_init(name=%s, start=%lx, length=%lx, blockSize=%lx, heapEntries=%ld)\n",
116		name, start, length, blockSize, heapEntries));
117
118	mem = malloc(sizeof(*mem));
119	if (mem == NULL)
120		goto err1;
121
122	mem->block_size = blockSize;
123	mem->heap_entries = heapEntries;
124	mem->lock = create_sem(1, name);
125	if (mem->lock < 0)
126		goto err2;
127
128	// align size to B_PAGE_SIZE
129	size = heapEntries * sizeof(mem_block);
130	size = (size + B_PAGE_SIZE - 1) & ~(B_PAGE_SIZE - 1);
131
132	mem->heap_area = create_area(name, (void **)&mem->heap,
133		B_ANY_ADDRESS, size, B_FULL_LOCK, B_READ_AREA | B_WRITE_AREA);
134
135	if (mem->heap_area < 0 || mem->heap == NULL)
136		goto err3;
137
138	for (i = 1; i < heapEntries; ++i) {
139		mem->heap[i - 1].next = &mem->heap[i];
140	}
141
142	mem->heap[heapEntries - 1].next = NULL;
143	mem->unused = &mem->heap[1];
144
145	first = &mem->heap[0];
146	mem->first = first;
147
148	first->base = start;
149	first->size = length;
150	first->prev = first->next = NULL;
151	first->allocated = false;
152
153	return mem;
154
155err3:
156	delete_sem(mem->lock);
157err2:
158	free(mem);
159err1:
160	return NULL;
161}
162
163
164/** destroy heap */
165
166void
167mem_destroy(mem_info *mem)
168{
169	TRACE(("mem_destroy(mem %p)\n", mem));
170
171	delete_area(mem->heap_area);
172	delete_sem(mem->lock);
173	free(mem);
174}
175
176
177/** Allocate memory block
178 *
179 *	\param mem heap handle
180 *	\param size size in bytes
181 *	\param tag owner tag
182 *
183 *	\param blockID - returns block id
184 *	\param offset - returns start address of block
185 */
186
187status_t
188mem_alloc(mem_info *mem, uint32 size, void *tag, uint32 *blockID, uint32 *offset)
189{
190	mem_block *current, *newEntry;
191	status_t status;
192
193	TRACE(("mem_alloc(mem %p, size=%lx, tag=%p)\n", mem, size, tag));
194
195	status = acquire_sem(mem->lock);
196	if (status != B_OK)
197		return status;
198
199	// we assume block_size is power of two
200	size = (size + mem->block_size - 1) & ~(mem->block_size - 1);
201
202	// simple first fit
203	for (current = mem->first; current; current = current->next) {
204		if (!current->allocated && current->size >= size)
205			break;
206	}
207
208	if (current == NULL) {
209		TRACE(("mem_alloc: out of memory\n"));
210		goto err;
211	}
212
213	if (size != current->size) {
214		newEntry = mem->unused;
215
216		if (newEntry == NULL) {
217			TRACE(("mem_alloc: out of blocks\n"));
218			goto err;
219		}
220
221		mem->unused = newEntry->next;
222
223		newEntry->next = current->next;
224		newEntry->prev = current;
225		newEntry->allocated = false;
226		newEntry->base = current->base + size;
227		newEntry->size = current->size - size;
228
229		if (current->next)
230			current->next->prev = newEntry;
231
232		current->next = newEntry;
233		current->size = size;
234	}
235
236	current->allocated = true;
237	current->tag = tag;
238
239	*blockID = current - mem->heap + 1;
240	*offset = current->base;
241
242	release_sem(mem->lock);
243
244	TRACE(("mem_alloc(block_id=%ld, offset=%lx)\n", *blockID, *offset));
245	return B_OK;
246
247err:
248	release_sem(mem->lock);
249	return B_NO_MEMORY;
250}
251
252
253/** Free memory
254 *	\param mem heap handle
255 *	\param blockID block id
256 *	\param tag owner tag (must match tag passed to mem_alloc())
257 */
258
259status_t
260mem_free(mem_info *mem, uint32 blockID, void *tag)
261{
262	mem_block *block;
263	status_t status;
264
265	TRACE(("mem_free(mem %p, blockID=%ld, tag=%p)\n", mem, blockID, tag));
266
267	status = acquire_sem(mem->lock);
268	if (status != B_OK)
269		return status;
270
271	--blockID;
272
273	if (blockID >= mem->heap_entries) {
274		TRACE(("mem_free: invalid ID %lu\n", blockID));
275		goto err;
276	}
277
278	block = &mem->heap[blockID];
279	if (!block->allocated || block->tag != tag) {
280		TRACE(("mem_free: not owner\n"));
281		goto err;
282	}
283
284	freeblock(mem, block);
285
286	release_sem(mem->lock);
287	return B_OK;
288
289err:
290	release_sem(mem->lock);
291	return B_BAD_VALUE;
292}
293
294
295/** Free all memory belonging to owner "tag" */
296
297status_t
298mem_freetag(mem_info *mem, void *tag)
299{
300	mem_block *current;
301	status_t status;
302
303	TRACE(("mem_freetag(mem %p, tag=%p)\n", mem, tag));
304
305	status = acquire_sem(mem->lock);
306	if (status != B_OK)
307		return status;
308
309	for (current = mem->first; current; current = current->next) {
310		if (current->allocated && current->tag == tag)
311			current = freeblock(mem, current);
312	}
313
314	release_sem(mem->lock);
315	return B_OK;
316}
317