1 /*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <trylock.h>
18 #include <atomic.h>
19 #include <stdint.h>
20 #include <stdio.h>
21 #include <heap.h>
22 #include <seos.h>
23
24 #define TIDX_HEAP_EXTRA 2 // must be >= 0; best if > 0, don't make it > 7, since it unnecessarily limits max heap size we can manage
25
26 #define TIDX_HEAP_BITS (TASK_IDX_BITS + TIDX_HEAP_EXTRA)
27
28 #define TIDX_MASK ((1 << TIDX_HEAP_BITS) - 1)
29 #define MAX_HEAP_ORDER (31 - TIDX_HEAP_BITS)
30
31 #if MAX_HEAP_ORDER < 16
32 # error Too little HEAP is available
33 #endif
34
35 struct HeapNode {
36
37 struct HeapNode* prev;
38 uint32_t size: MAX_HEAP_ORDER;
39 uint32_t used: 1;
40 uint32_t tidx: TIDX_HEAP_BITS; // TASK_IDX_BITS to uniquely identify task; + extra bits of redundant counter add extra protection
41 uint8_t data[];
42 };
43
44 #ifdef FORCE_HEAP_IN_DOT_DATA
45
46 static uint8_t __attribute__ ((aligned (8))) gHeap[HEAP_SIZE];
47
48 #define REAL_HEAP_SIZE ((HEAP_SIZE) &~ 7)
49 #define ALIGNED_HEAP_START (&gHeap)
50
51 #else
52
53 extern uint8_t __heap_end[], __heap_start[];
54 #define ALIGNED_HEAP_START (uint8_t*)((((uintptr_t)&__heap_start) + 7) &~ 7)
55 #define ALIGNED_HEAP_END (uint8_t*)(((uintptr_t)&__heap_end) &~ 7)
56
57 #define REAL_HEAP_SIZE (ALIGNED_HEAP_END - ALIGNED_HEAP_START)
58
59
60 #endif
61
62 static struct HeapNode* gHeapHead;
63 static TRYLOCK_DECL_STATIC(gHeapLock) = TRYLOCK_INIT_STATIC();
64 static volatile uint8_t gNeedFreeMerge = false; /* cannot be bool since its size is ill defined */
65 static struct HeapNode *gHeapTail;
66
heapPrvGetNext(struct HeapNode * node)67 static inline struct HeapNode* heapPrvGetNext(struct HeapNode* node)
68 {
69 return (gHeapTail == node) ? NULL : (struct HeapNode*)(node->data + node->size);
70 }
71
heapInit(void)72 bool heapInit(void)
73 {
74 uint32_t size = REAL_HEAP_SIZE;
75 struct HeapNode* node;
76
77 node = gHeapHead = (struct HeapNode*)ALIGNED_HEAP_START;
78
79 if (size < sizeof(struct HeapNode))
80 return false;
81
82 gHeapTail = node;
83
84 node->used = 0;
85 node->prev = NULL;
86 node->size = size - sizeof(struct HeapNode);
87
88 return true;
89 }
90
91 //called to merge free chunks in case free() was unable to last time it tried. only call with lock held please
heapMergeFreeChunks(void)92 static void heapMergeFreeChunks(void)
93 {
94 while (atomicXchgByte(&gNeedFreeMerge, false)) {
95 struct HeapNode *node = gHeapHead, *next;
96
97 while (node) {
98 next = heapPrvGetNext(node);
99
100 if (!node->used && next && !next->used) { /* merged */
101 node->size += sizeof(struct HeapNode) + next->size;
102
103 next = heapPrvGetNext(node);
104 if (next)
105 next->prev = node;
106 else
107 gHeapTail = node;
108 }
109 else
110 node = next;
111 }
112 }
113 }
114
heapAlloc(uint32_t sz)115 void* heapAlloc(uint32_t sz)
116 {
117 struct HeapNode *node, *best = NULL;
118 void* ret = NULL;
119
120 if (!trylockTryTake(&gHeapLock))
121 return NULL;
122
123 /* merge free chunks to help better use space */
124 heapMergeFreeChunks();
125
126 sz = (sz + 3) &~ 3;
127 node = gHeapHead;
128
129 while (node) {
130 if (!node->used && node->size >= sz && (!best || best->size > node->size)) {
131 best = node;
132 if (best->size == sz)
133 break;
134 }
135
136 node = heapPrvGetNext(node);
137 }
138
139 if (!best) //alloc failed
140 goto out;
141
142 if (best->size - sz > sizeof(struct HeapNode)) { //there is a point to split up the chunk
143
144 node = (struct HeapNode*)(best->data + sz);
145
146 node->used = 0;
147 node->tidx = 0;
148 node->size = best->size - sz - sizeof(struct HeapNode);
149 node->prev = best;
150
151 if (best != gHeapTail)
152 heapPrvGetNext(node)->prev = node;
153 else
154 gHeapTail = node;
155
156 best->size = sz;
157 }
158
159 best->used = 1;
160 best->tidx = osGetCurrentTid();
161 ret = best->data;
162
163 out:
164 trylockRelease(&gHeapLock);
165 return ret;
166 }
167
heapFree(void * ptr)168 void heapFree(void* ptr)
169 {
170 struct HeapNode *node, *t;
171 bool haveLock;
172
173 if (ptr == NULL) {
174 // NULL is a valid reply from heapAlloc, and thus it is not an error for
175 // us to receive it here. We just ignore it.
176 return;
177 }
178
179 haveLock = trylockTryTake(&gHeapLock);
180
181 node = ((struct HeapNode*)ptr) - 1;
182 node->used = 0;
183 node->tidx = 0;
184
185 if (haveLock) {
186
187 while (node->prev && !node->prev->used)
188 node = node->prev;
189
190 while ((t = heapPrvGetNext(node)) && !t->used) {
191 node->size += sizeof(struct HeapNode) + t->size;
192 if (gHeapTail == t)
193 gHeapTail = node;
194 }
195
196 if ((t = heapPrvGetNext(node)))
197 t->prev = node;
198
199 trylockRelease(&gHeapLock);
200 }
201 else
202 gNeedFreeMerge = true;
203 }
204
heapFreeAll(uint32_t tid)205 int heapFreeAll(uint32_t tid)
206 {
207 struct HeapNode *node;
208 bool haveLock;
209 int count = 0;
210
211 if (!tid)
212 return -1;
213
214 // this can only fail if called from interrupt
215 haveLock = trylockTryTake(&gHeapLock);
216 if (!haveLock)
217 return -1;
218
219 node = gHeapHead;
220 tid &= TIDX_MASK;
221 do {
222 if (node->tidx == tid) {
223 node->used = 0;
224 node->tidx = 0;
225 count++;
226 }
227 } while ((node = heapPrvGetNext(node)) != NULL);
228 gNeedFreeMerge = true;
229 trylockRelease(&gHeapLock);
230
231 return count;
232 }
233