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 "mm.h"
30
31
32 void
mmDumpMemInfo(const struct mem_block * heap)33 mmDumpMemInfo(const struct mem_block *heap)
34 {
35 fprintf(stderr, "Memory heap %p:\n", (void *)heap);
36 if (heap == 0) {
37 fprintf(stderr, " heap == 0\n");
38 } else {
39 const struct mem_block *p;
40
41 for(p = heap->next; p != heap; p = p->next) {
42 fprintf(stderr, " Offset:%08x, Size:%08x, %c%c\n",p->ofs,p->size,
43 p->free ? 'F':'.',
44 p->reserved ? 'R':'.');
45 }
46
47 fprintf(stderr, "\nFree list:\n");
48
49 for(p = heap->next_free; p != heap; p = p->next_free) {
50 fprintf(stderr, " FREE Offset:%08x, Size:%08x, %c%c\n",p->ofs,p->size,
51 p->free ? 'F':'.',
52 p->reserved ? 'R':'.');
53 }
54
55 }
56 fprintf(stderr, "End of memory blocks\n");
57 }
58
59 struct mem_block *
mmInit(unsigned ofs,unsigned size)60 mmInit(unsigned ofs, unsigned size)
61 {
62 struct mem_block *heap, *block;
63
64 if (!size)
65 return NULL;
66
67 heap = calloc(1, sizeof(struct mem_block));
68 if (!heap)
69 return NULL;
70
71 block = calloc(1, sizeof(struct mem_block));
72 if (!block) {
73 free(heap);
74 return NULL;
75 }
76
77 heap->next = block;
78 heap->prev = block;
79 heap->next_free = block;
80 heap->prev_free = block;
81
82 block->heap = heap;
83 block->next = heap;
84 block->prev = heap;
85 block->next_free = heap;
86 block->prev_free = heap;
87
88 block->ofs = ofs;
89 block->size = size;
90 block->free = 1;
91
92 return heap;
93 }
94
95
96 static struct mem_block *
SliceBlock(struct mem_block * p,unsigned startofs,unsigned size,unsigned reserved,unsigned alignment)97 SliceBlock(struct mem_block *p,
98 unsigned startofs, unsigned size,
99 unsigned reserved, unsigned alignment)
100 {
101 struct mem_block *newblock;
102
103 /* break left [p, newblock, p->next], then p = newblock */
104 if (startofs > p->ofs) {
105 newblock = calloc(1, sizeof(struct mem_block));
106 if (!newblock)
107 return NULL;
108 newblock->ofs = startofs;
109 newblock->size = p->size - (startofs - p->ofs);
110 newblock->free = 1;
111 newblock->heap = p->heap;
112
113 newblock->next = p->next;
114 newblock->prev = p;
115 p->next->prev = newblock;
116 p->next = newblock;
117
118 newblock->next_free = p->next_free;
119 newblock->prev_free = p;
120 p->next_free->prev_free = newblock;
121 p->next_free = newblock;
122
123 p->size -= newblock->size;
124 p = newblock;
125 }
126
127 /* break right, also [p, newblock, p->next] */
128 if (size < p->size) {
129 newblock = calloc(1, sizeof(struct mem_block));
130 if (!newblock)
131 return NULL;
132 newblock->ofs = startofs + size;
133 newblock->size = p->size - size;
134 newblock->free = 1;
135 newblock->heap = p->heap;
136
137 newblock->next = p->next;
138 newblock->prev = p;
139 p->next->prev = newblock;
140 p->next = newblock;
141
142 newblock->next_free = p->next_free;
143 newblock->prev_free = p;
144 p->next_free->prev_free = newblock;
145 p->next_free = newblock;
146
147 p->size = size;
148 }
149
150 /* p = middle block */
151 p->free = 0;
152
153 /* Remove p from the free list:
154 */
155 p->next_free->prev_free = p->prev_free;
156 p->prev_free->next_free = p->next_free;
157
158 p->next_free = 0;
159 p->prev_free = 0;
160
161 p->reserved = reserved;
162 return p;
163 }
164
165
166 struct mem_block *
mmAllocMem(struct mem_block * heap,unsigned size,unsigned align2,unsigned startSearch)167 mmAllocMem(struct mem_block *heap, unsigned size, unsigned align2, unsigned startSearch)
168 {
169 struct mem_block *p;
170 const unsigned mask = (1 << align2)-1;
171 unsigned startofs = 0;
172 unsigned endofs;
173
174 if (!heap || !size)
175 return NULL;
176
177 for (p = heap->next_free; p != heap; p = p->next_free) {
178 assert(p->free);
179
180 startofs = (p->ofs + mask) & ~mask;
181 if ( startofs < startSearch ) {
182 startofs = startSearch;
183 }
184 endofs = startofs+size;
185 if (endofs <= (p->ofs+p->size))
186 break;
187 }
188
189 if (p == heap)
190 return NULL;
191
192 assert(p->free);
193 p = SliceBlock(p,startofs,size,0,mask+1);
194
195 return p;
196 }
197
198
199 struct mem_block *
mmFindBlock(struct mem_block * heap,unsigned start)200 mmFindBlock(struct mem_block *heap, unsigned start)
201 {
202 struct mem_block *p;
203
204 for (p = heap->next; p != heap; p = p->next) {
205 if (p->ofs == start)
206 return p;
207 }
208
209 return NULL;
210 }
211
212
213 static inline int
Join2Blocks(struct mem_block * p)214 Join2Blocks(struct mem_block *p)
215 {
216 /* XXX there should be some assertions here */
217
218 /* NOTE: heap->free == 0 */
219
220 if (p->free && p->next->free) {
221 struct mem_block *q = p->next;
222
223 assert(p->ofs + p->size == q->ofs);
224 p->size += q->size;
225
226 p->next = q->next;
227 q->next->prev = p;
228
229 q->next_free->prev_free = q->prev_free;
230 q->prev_free->next_free = q->next_free;
231
232 free(q);
233 return 1;
234 }
235 return 0;
236 }
237
238 int
mmFreeMem(struct mem_block * b)239 mmFreeMem(struct mem_block *b)
240 {
241 if (!b)
242 return 0;
243
244 if (b->free) {
245 fprintf(stderr, "block already free\n");
246 return -1;
247 }
248 if (b->reserved) {
249 fprintf(stderr, "block is reserved\n");
250 return -1;
251 }
252
253 b->free = 1;
254 b->next_free = b->heap->next_free;
255 b->prev_free = b->heap;
256 b->next_free->prev_free = b;
257 b->prev_free->next_free = b;
258
259 Join2Blocks(b);
260 if (b->prev != b->heap)
261 Join2Blocks(b->prev);
262
263 return 0;
264 }
265
266
267 void
mmDestroy(struct mem_block * heap)268 mmDestroy(struct mem_block *heap)
269 {
270 struct mem_block *p;
271
272 if (!heap)
273 return;
274
275 for (p = heap->next; p != heap; ) {
276 struct mem_block *next = p->next;
277 free(p);
278 p = next;
279 }
280
281 free(heap);
282 }
283