Home | History | Annotate | Download | only in src
      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