1 /* from https://github.com/smealum/ctrulib
2 * modified to allow reducing __linear_heap_size at runtime */
3
4 #include <3ds.h>
5 #include <stdlib.h>
6 #include <3ds/util/rbtree.h>
7 #include "ctr_debug.h"
8
9 struct MemChunk
10 {
11 u8* addr;
12 u32 size;
13 };
14
15 struct MemBlock
16 {
17 MemBlock *prev, *next;
18 u8* base;
19 u32 size;
20
CreateMemBlock21 static MemBlock* Create(u8* base, u32 size)
22 {
23 auto b = (MemBlock*)malloc(sizeof(MemBlock));
24 if (!b) return nullptr;
25 b->prev = nullptr;
26 b->next = nullptr;
27 b->base = base;
28 b->size = size;
29 return b;
30 }
31 };
32
33 struct MemPool
34 {
35 MemBlock *first, *last;
36
ReadyMemPool37 bool Ready() { return first != nullptr; }
38
AddBlockMemPool39 void AddBlock(MemBlock* blk)
40 {
41 blk->prev = last;
42 if (last) last->next = blk;
43 if (!first) first = blk;
44 last = blk;
45 }
46
DelBlockMemPool47 void DelBlock(MemBlock* b)
48 {
49 auto prev = b->prev, &pNext = prev ? prev->next : first;
50 auto next = b->next, &nPrev = next ? next->prev : last;
51 pNext = next;
52 nPrev = prev;
53 free(b);
54 }
55
InsertBeforeMemPool56 void InsertBefore(MemBlock* b, MemBlock* p)
57 {
58 auto prev = b->prev, &pNext = prev ? prev->next : first;
59 b->prev = p;
60 p->next = b;
61 p->prev = prev;
62 pNext = p;
63 }
64
InsertAfterMemPool65 void InsertAfter(MemBlock* b, MemBlock* n)
66 {
67 auto next = b->next, &nPrev = next ? next->prev : last;
68 b->next = n;
69 n->prev = b;
70 n->next = next;
71 nPrev = n;
72 }
73
74 void CoalesceRight(MemBlock* b);
75
76 bool Allocate(MemChunk& chunk, u32 size, int align);
77 void Deallocate(const MemChunk& chunk);
78
DestroyMemPool79 void Destroy()
80 {
81 MemBlock* next = nullptr;
82 for (auto b = first; b; b = next)
83 {
84 next = b->next;
85 free(b);
86 }
87 first = nullptr;
88 last = nullptr;
89 }
90
91 #if 0
92 void Dump(const char* title);
93 #endif
94 u32 GetFreeSpace();
95 };
96
97 static rbtree_t sAddrMap;
98
99 struct addrMapNode
100 {
101 rbtree_node node;
102 MemChunk chunk;
103 };
104
105 #define getAddrMapNode(x) rbtree_item((x), addrMapNode, node)
106
addrMapNodeComparator(const rbtree_node_t * _lhs,const rbtree_node_t * _rhs)107 static int addrMapNodeComparator(const rbtree_node_t* _lhs, const rbtree_node_t* _rhs)
108 {
109 auto lhs = getAddrMapNode(_lhs)->chunk.addr;
110 auto rhs = getAddrMapNode(_rhs)->chunk.addr;
111 if (lhs < rhs)
112 return -1;
113 if (lhs > rhs)
114 return 1;
115 return 0;
116 }
117
addrMapNodeDestructor(rbtree_node_t * a)118 static void addrMapNodeDestructor(rbtree_node_t* a)
119 {
120 free(getAddrMapNode(a));
121 }
122
getNode(void * addr)123 static addrMapNode* getNode(void* addr)
124 {
125 addrMapNode n;
126 n.chunk.addr = (u8*)addr;
127 auto p = rbtree_find(&sAddrMap, &n.node);
128 return p ? getAddrMapNode(p) : nullptr;
129 }
130
newNode(const MemChunk & chunk)131 static addrMapNode* newNode(const MemChunk& chunk)
132 {
133 auto p = (addrMapNode*)malloc(sizeof(addrMapNode));
134 if (!p) return nullptr;
135 p->chunk = chunk;
136 return p;
137 }
138
delNode(addrMapNode * node)139 static void delNode(addrMapNode* node)
140 {
141 rbtree_remove(&sAddrMap, &node->node, addrMapNodeDestructor);
142 }
143
144 extern u32 __linear_heap, __linear_heap_size;
145
146 static MemPool sLinearPool;
147 static u32 sLinearPool_maxaddr;
148
linearInit(void)149 static bool linearInit(void)
150 {
151 auto blk = MemBlock::Create((u8*)__linear_heap, __linear_heap_size);
152 if (blk)
153 {
154 sLinearPool.AddBlock(blk);
155 sLinearPool_maxaddr = __linear_heap;
156 rbtree_init(&sAddrMap, addrMapNodeComparator);
157 return true;
158 }
159 return false;
160 }
161
linearMemAlign(size_t size,size_t alignment)162 void* linearMemAlign(size_t size, size_t alignment)
163 {
164 int shift;
165 /* Enforce minimum alignment */
166 if (alignment < 16)
167 alignment = 16;
168
169 /* Convert alignment to shift amount */
170 for (shift = 4; shift < 32; shift ++)
171 {
172 if ((1U<<shift) == alignment)
173 break;
174 }
175 if (shift == 32) /* Invalid alignment */
176 return nullptr;
177
178 /* Initialize the pool if it is not ready */
179 if (!sLinearPool.Ready() && !linearInit())
180 return nullptr;
181
182 /* Allocate the chunk */
183 MemChunk chunk;
184 if (!sLinearPool.Allocate(chunk, size, shift))
185 return nullptr;
186
187 auto node = newNode(chunk);
188 if (!node)
189 {
190 sLinearPool.Deallocate(chunk);
191 return nullptr;
192 }
193 if (rbtree_insert(&sAddrMap, &node->node));
194
195 if (sLinearPool_maxaddr < (u32)sLinearPool.last->base)
196 sLinearPool_maxaddr = (u32)sLinearPool.last->base;
197
198 return chunk.addr;
199 }
200
linearAlloc(size_t size)201 void* linearAlloc(size_t size)
202 {
203 #if 0
204 if(ctrConsole && ctrConsole->consoleInitialised)
205 {
206 printf("linearAlloc : 0x%08X\n", size);
207 DEBUG_HOLD();
208 }
209 #endif
210 return linearMemAlign(size, 0x80);
211 }
212
linearRealloc(void * mem,size_t size)213 void* linearRealloc(void* mem, size_t size)
214 {
215 /* TODO */
216 return NULL;
217 }
218
linearFree(void * mem)219 void linearFree(void* mem)
220 {
221 auto node = getNode(mem);
222 if (!node)
223 return;
224
225 /* Free the chunk */
226 sLinearPool.Deallocate(node->chunk);
227
228 /* Free the node */
229 delNode(node);
230 }
231
linearSpaceFree(void)232 u32 linearSpaceFree(void)
233 {
234 return sLinearPool.GetFreeSpace();
235 }
236
ctr_get_linear_free(void)237 extern "C" u32 ctr_get_linear_free(void)
238 {
239 if(sLinearPool.last->base + sLinearPool.last->size != (u8*)__linear_heap + __linear_heap_size)
240 return 0;
241 return sLinearPool.last->size;
242 }
243
ctr_get_linear_unused(void)244 extern "C" u32 ctr_get_linear_unused(void)
245 {
246 return __linear_heap + __linear_heap_size - sLinearPool_maxaddr;
247 }
248
ctr_linear_free_pages(u32 pages)249 extern "C" void ctr_linear_free_pages(u32 pages)
250 {
251 if(sLinearPool.last->base + sLinearPool.last->size != (u8*)__linear_heap + __linear_heap_size)
252 return;
253
254 u32 size = pages << 12;
255 if(size > sLinearPool.last->size)
256 return;
257
258 sLinearPool.last->size -= size;
259 __linear_heap_size -= size;
260 u32 tmp;
261 svcControlMemory(&tmp, __linear_heap + __linear_heap_size, 0x0, size,
262 MEMOP_FREE, (MemPerm)(MEMPERM_READ | MEMPERM_WRITE));
263
264 #if 0
265 printf("l:0x%08X-->0x%08X(-0x%08X) \n", sLinearPool.last->size + size, sLinearPool.last->size, size);
266 DEBUG_HOLD();
267 #endif
268 }
269
ctr_linear_get_stats(void)270 extern "C" void ctr_linear_get_stats(void)
271 {
272 printf("last:\n");
273 printf("0x%08X --> 0x%08X (0x%08X) \n", sLinearPool.last->base,
274 sLinearPool.last->base + sLinearPool.last->size, sLinearPool.last->size);
275 printf("free: 0x%08X unused: 0x%08X \n", ctr_get_linear_unused(), ctr_get_linear_free());
276 }
277