1 /**************************************************************************
3 * Copyright (C) 1999 Wittawat Yamwong
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:
12 * The above copyright notice and this permission notice shall be included
13 * in all copies or substantial portions of the Software.
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.
23 **************************************************************************/
26 #include "util/u_debug.h"
28 #include "util/u_memory.h"
29 #include "util/u_mm.h"
33 u_mmDumpMemInfo(const struct mem_block
*heap
)
35 debug_printf("Memory heap %p:\n", (void *) heap
);
37 debug_printf(" heap == 0\n");
40 const struct mem_block
*p
;
41 int total_used
= 0, total_free
= 0;
43 for (p
= heap
->next
; p
!= heap
; p
= p
->next
) {
44 debug_printf(" Offset:%08x, Size:%08x, %c%c\n", p
->ofs
, p
->size
,
46 p
->reserved
? 'R':'.');
48 total_free
+= p
->size
;
50 total_used
+= p
->size
;
53 debug_printf("'\nMemory stats: total = %d, used = %d, free = %d\n",
54 total_used
+ total_free
, total_used
, total_free
);
55 debug_printf("\nFree list:\n");
57 for (p
= heap
->next_free
; p
!= heap
; p
= p
->next_free
) {
58 debug_printf(" FREE Offset:%08x, Size:%08x, %c%c\n", p
->ofs
, p
->size
,
60 p
->reserved
? 'R':'.');
64 debug_printf("End of memory blocks\n");
69 u_mmInit(int ofs
, int size
)
71 struct mem_block
*heap
, *block
;
76 heap
= CALLOC_STRUCT(mem_block
);
80 block
= CALLOC_STRUCT(mem_block
);
88 heap
->next_free
= block
;
89 heap
->prev_free
= block
;
94 block
->next_free
= heap
;
95 block
->prev_free
= heap
;
105 static struct mem_block
*
106 SliceBlock(struct mem_block
*p
,
107 int startofs
, int size
,
108 int reserved
, UNUSED
int alignment
)
110 struct mem_block
*newblock
;
112 /* break left [p, newblock, p->next], then p = newblock */
113 if (startofs
> p
->ofs
) {
114 newblock
= CALLOC_STRUCT(mem_block
);
117 newblock
->ofs
= startofs
;
118 newblock
->size
= p
->size
- (startofs
- p
->ofs
);
120 newblock
->heap
= p
->heap
;
122 newblock
->next
= p
->next
;
124 p
->next
->prev
= newblock
;
127 newblock
->next_free
= p
->next_free
;
128 newblock
->prev_free
= p
;
129 p
->next_free
->prev_free
= newblock
;
130 p
->next_free
= newblock
;
132 p
->size
-= newblock
->size
;
136 /* break right, also [p, newblock, p->next] */
137 if (size
< p
->size
) {
138 newblock
= CALLOC_STRUCT(mem_block
);
141 newblock
->ofs
= startofs
+ size
;
142 newblock
->size
= p
->size
- size
;
144 newblock
->heap
= p
->heap
;
146 newblock
->next
= p
->next
;
148 p
->next
->prev
= newblock
;
151 newblock
->next_free
= p
->next_free
;
152 newblock
->prev_free
= p
;
153 p
->next_free
->prev_free
= newblock
;
154 p
->next_free
= newblock
;
159 /* p = middle block */
162 /* Remove p from the free list:
164 p
->next_free
->prev_free
= p
->prev_free
;
165 p
->prev_free
->next_free
= p
->next_free
;
170 p
->reserved
= reserved
;
176 u_mmAllocMem(struct mem_block
*heap
, int size
, int align2
, int startSearch
)
179 const int mask
= (1 << align2
)-1;
185 /* Make sure that a byte alignment isn't getting passed for our
186 * power-of-two alignment arg.
190 if (!heap
|| align2
< 0 || size
<= 0)
193 for (p
= heap
->next_free
; p
!= heap
; p
= p
->next_free
) {
196 startofs
= (p
->ofs
+ mask
) & ~mask
;
197 if ( startofs
< startSearch
) {
198 startofs
= startSearch
;
200 endofs
= startofs
+size
;
201 if (endofs
<= (p
->ofs
+p
->size
))
209 p
= SliceBlock(p
,startofs
,size
,0,mask
+1);
216 u_mmFindBlock(struct mem_block
*heap
, int start
)
220 for (p
= heap
->next
; p
!= heap
; p
= p
->next
) {
230 Join2Blocks(struct mem_block
*p
)
232 /* XXX there should be some assertions here */
234 /* NOTE: heap->free == 0 */
236 if (p
->free
&& p
->next
->free
) {
237 struct mem_block
*q
= p
->next
;
239 assert(p
->ofs
+ p
->size
== q
->ofs
);
245 q
->next_free
->prev_free
= q
->prev_free
;
246 q
->prev_free
->next_free
= q
->next_free
;
255 u_mmFreeMem(struct mem_block
*b
)
261 debug_printf("block already free\n");
265 debug_printf("block is reserved\n");
270 b
->next_free
= b
->heap
->next_free
;
271 b
->prev_free
= b
->heap
;
272 b
->next_free
->prev_free
= b
;
273 b
->prev_free
->next_free
= b
;
276 if (b
->prev
!= b
->heap
)
277 Join2Blocks(b
->prev
);
284 u_mmDestroy(struct mem_block
*heap
)
291 for (p
= heap
->next
; p
!= heap
; ) {
292 struct mem_block
*next
= p
->next
;