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 67 static inline struct HeapNode* heapPrvGetNext(struct HeapNode* node) 68 { 69 return (gHeapTail == node) ? NULL : (struct HeapNode*)(node->data + node->size); 70 } 71 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 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 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 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 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
