1 /*
2 * GLX Hardware Device Driver common code
3 * Copyright (C) 1999 Wittawat Yamwong
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be included
13 * in all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
16 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * WITTAWAT YAMWONG, OR ANY OTHER CONTRIBUTORS BE LIABLE FOR ANY CLAIM,
19 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
20 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
21 * OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22 *
23 */
24
25 #include <assert.h>
26 #include <stdio.h>
27 #include <stdlib.h>
28
29 #include "compiler.h"
30 #include "mm.h"
31
32
33 void
mmDumpMemInfo(const struct mem_block * heap)34 mmDumpMemInfo(const struct mem_block *heap)
35 {
36 fprintf(stderr, "Memory heap %p:\n", (void *)heap);
37 if (heap == 0) {
38 fprintf(stderr, " heap == 0\n");
39 } else {
40 const struct mem_block *p;
41
42 for(p = heap->next; p != heap; p = p->next) {
43 fprintf(stderr, " Offset:%08x, Size:%08x, %c%c\n",p->ofs,p->size,
44 p->free ? 'F':'.',
45 p->reserved ? 'R':'.');
46 }
47
48 fprintf(stderr, "\nFree list:\n");
49
50 for(p = heap->next_free; p != heap; p = p->next_free) {
51 fprintf(stderr, " FREE Offset:%08x, Size:%08x, %c%c\n",p->ofs,p->size,
52 p->free ? 'F':'.',
53 p->reserved ? 'R':'.');
54 }
55
56 }
57 fprintf(stderr, "End of memory blocks\n");
58 }
59
60 struct mem_block *
mmInit(unsigned ofs,unsigned size)61 mmInit(unsigned ofs, unsigned size)
62 {
63 struct mem_block *heap, *block;
64
65 if (!size)
66 return NULL;
67
68 heap = calloc(1, sizeof(struct mem_block));
69 if (!heap)
70 return NULL;
71
72 block = calloc(1, sizeof(struct mem_block));
73 if (!block) {
74 free(heap);
75 return NULL;
76 }
77
78 heap->next = block;
79 heap->prev = block;
80 heap->next_free = block;
81 heap->prev_free = block;
82
83 block->heap = heap;
84 block->next = heap;
85 block->prev = heap;
86 block->next_free = heap;
87 block->prev_free = heap;
88
89 block->ofs = ofs;
90 block->size = size;
91 block->free = 1;
92
93 return heap;
94 }
95
96
97 static struct mem_block *
SliceBlock(struct mem_block * p,unsigned startofs,unsigned size,unsigned reserved,unsigned alignment)98 SliceBlock(struct mem_block *p,
99 unsigned startofs, unsigned size,
100 unsigned reserved, unsigned alignment)
101 {
102 struct mem_block *newblock;
103
104 /* break left [p, newblock, p->next], then p = newblock */
105 if (startofs > p->ofs) {
106 newblock = calloc(1, sizeof(struct mem_block));
107 if (!newblock)
108 return NULL;
109 newblock->ofs = startofs;
110 newblock->size = p->size - (startofs - p->ofs);
111 newblock->free = 1;
112 newblock->heap = p->heap;
113
114 newblock->next = p->next;
115 newblock->prev = p;
116 p->next->prev = newblock;
117 p->next = newblock;
118
119 newblock->next_free = p->next_free;
120 newblock->prev_free = p;
121 p->next_free->prev_free = newblock;
122 p->next_free = newblock;
123
124 p->size -= newblock->size;
125 p = newblock;
126 }
127
128 /* break right, also [p, newblock, p->next] */
129 if (size < p->size) {
130 newblock = calloc(1, sizeof(struct mem_block));
131 if (!newblock)
132 return NULL;
133 newblock->ofs = startofs + size;
134 newblock->size = p->size - size;
135 newblock->free = 1;
136 newblock->heap = p->heap;
137
138 newblock->next = p->next;
139 newblock->prev = p;
140 p->next->prev = newblock;
141 p->next = newblock;
142
143 newblock->next_free = p->next_free;
144 newblock->prev_free = p;
145 p->next_free->prev_free = newblock;
146 p->next_free = newblock;
147
148 p->size = size;
149 }
150
151 /* p = middle block */
152 p->free = 0;
153
154 /* Remove p from the free list:
155 */
156 p->next_free->prev_free = p->prev_free;
157 p->prev_free->next_free = p->next_free;
158
159 p->next_free = 0;
160 p->prev_free = 0;
161
162 p->reserved = reserved;
163 return p;
164 }
165
166
167 struct mem_block *
mmAllocMem(struct mem_block * heap,unsigned size,unsigned align2,unsigned startSearch)168 mmAllocMem(struct mem_block *heap, unsigned size, unsigned align2, unsigned startSearch)
169 {
170 struct mem_block *p;
171 const unsigned mask = (1 << align2)-1;
172 unsigned startofs = 0;
173 unsigned endofs;
174
175 if (!heap || !size)
176 return NULL;
177
178 for (p = heap->next_free; p != heap; p = p->next_free) {
179 assert(p->free);
180
181 startofs = (p->ofs + mask) & ~mask;
182 if ( startofs < startSearch ) {
183 startofs = startSearch;
184 }
185 endofs = startofs+size;
186 if (endofs <= (p->ofs+p->size))
187 break;
188 }
189
190 if (p == heap)
191 return NULL;
192
193 assert(p->free);
194 p = SliceBlock(p,startofs,size,0,mask+1);
195
196 return p;
197 }
198
199
200 struct mem_block *
mmFindBlock(struct mem_block * heap,unsigned start)201 mmFindBlock(struct mem_block *heap, unsigned start)
202 {
203 struct mem_block *p;
204
205 for (p = heap->next; p != heap; p = p->next) {
206 if (p->ofs == start)
207 return p;
208 }
209
210 return NULL;
211 }
212
213
214 static inline int
Join2Blocks(struct mem_block * p)215 Join2Blocks(struct mem_block *p)
216 {
217 /* XXX there should be some assertions here */
218
219 /* NOTE: heap->free == 0 */
220
221 if (p->free && p->next->free) {
222 struct mem_block *q = p->next;
223
224 assert(p->ofs + p->size == q->ofs);
225 p->size += q->size;
226
227 p->next = q->next;
228 q->next->prev = p;
229
230 q->next_free->prev_free = q->prev_free;
231 q->prev_free->next_free = q->next_free;
232
233 free(q);
234 return 1;
235 }
236 return 0;
237 }
238
239 int
mmFreeMem(struct mem_block * b)240 mmFreeMem(struct mem_block *b)
241 {
242 if (!b)
243 return 0;
244
245 if (b->free) {
246 fprintf(stderr, "block already free\n");
247 return -1;
248 }
249 if (b->reserved) {
250 fprintf(stderr, "block is reserved\n");
251 return -1;
252 }
253
254 b->free = 1;
255 b->next_free = b->heap->next_free;
256 b->prev_free = b->heap;
257 b->next_free->prev_free = b;
258 b->prev_free->next_free = b;
259
260 Join2Blocks(b);
261 if (b->prev != b->heap)
262 Join2Blocks(b->prev);
263
264 return 0;
265 }
266
267
268 void
mmDestroy(struct mem_block * heap)269 mmDestroy(struct mem_block *heap)
270 {
271 struct mem_block *p;
272
273 if (!heap)
274 return;
275
276 for (p = heap->next; p != heap; ) {
277 struct mem_block *next = p->next;
278 free(p);
279 p = next;
280 }
281
282 free(heap);
283 }
284