/*
* Copyright (C) 2016 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include <trylock.h>
#include <atomic.h>
#include <stdint.h>
#include <stdio.h>
#include <heap.h>
#include <seos.h>
#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
#define TIDX_HEAP_BITS (TASK_IDX_BITS + TIDX_HEAP_EXTRA)
#define TIDX_MASK ((1 << TIDX_HEAP_BITS) - 1)
#define MAX_HEAP_ORDER (31 - TIDX_HEAP_BITS)
#if MAX_HEAP_ORDER < 16
# error Too little HEAP is available
#endif
struct HeapNode {
struct HeapNode* prev;
uint32_t size: MAX_HEAP_ORDER;
uint32_t used: 1;
uint32_t tidx: TIDX_HEAP_BITS; // TASK_IDX_BITS to uniquely identify task; + extra bits of redundant counter add extra protection
uint8_t data[];
};
#ifdef FORCE_HEAP_IN_DOT_DATA
static uint8_t __attribute__ ((aligned (8))) gHeap[HEAP_SIZE];
#define REAL_HEAP_SIZE ((HEAP_SIZE) &~ 7)
#define ALIGNED_HEAP_START (&gHeap)
#else
extern uint8_t __heap_end[], __heap_start[];
#define ALIGNED_HEAP_START (uint8_t*)((((uintptr_t)&__heap_start) + 7) &~ 7)
#define ALIGNED_HEAP_END (uint8_t*)(((uintptr_t)&__heap_end) &~ 7)
#define REAL_HEAP_SIZE (ALIGNED_HEAP_END - ALIGNED_HEAP_START)
#endif
static struct HeapNode* gHeapHead;
static TRYLOCK_DECL_STATIC(gHeapLock) = TRYLOCK_INIT_STATIC();
static volatile uint8_t gNeedFreeMerge = false; /* cannot be bool since its size is ill defined */
static struct HeapNode *gHeapTail;
static inline struct HeapNode* heapPrvGetNext(struct HeapNode* node)
{
return (gHeapTail == node) ? NULL : (struct HeapNode*)(node->data + node->size);
}
bool heapInit(void)
{
uint32_t size = REAL_HEAP_SIZE;
struct HeapNode* node;
node = gHeapHead = (struct HeapNode*)ALIGNED_HEAP_START;
if (size < sizeof(struct HeapNode))
return false;
gHeapTail = node;
node->used = 0;
node->prev = NULL;
node->size = size - sizeof(struct HeapNode);
return true;
}
//called to merge free chunks in case free() was unable to last time it tried. only call with lock held please
static void heapMergeFreeChunks(void)
{
while (atomicXchgByte(&gNeedFreeMerge, false)) {
struct HeapNode *node = gHeapHead, *next;
while (node) {
next = heapPrvGetNext(node);
if (!node->used && next && !next->used) { /* merged */
node->size += sizeof(struct HeapNode) + next->size;
next = heapPrvGetNext(node);
if (next)
next->prev = node;
else
gHeapTail = node;
}
else
node = next;
}
}
}
void* heapAlloc(uint32_t sz)
{
struct HeapNode *node, *best = NULL;
void* ret = NULL;
if (!trylockTryTake(&gHeapLock))
return NULL;
/* merge free chunks to help better use space */
heapMergeFreeChunks();
sz = (sz + 3) &~ 3;
node = gHeapHead;
while (node) {
if (!node->used && node->size >= sz && (!best || best->size > node->size)) {
best = node;
if (best->size == sz)
break;
}
node = heapPrvGetNext(node);
}
if (!best) //alloc failed
goto out;
if (best->size - sz > sizeof(struct HeapNode)) { //there is a point to split up the chunk
node = (struct HeapNode*)(best->data + sz);
node->used = 0;
node->tidx = 0;
node->size = best->size - sz - sizeof(struct HeapNode);
node->prev = best;
if (best != gHeapTail)
heapPrvGetNext(node)->prev = node;
else
gHeapTail = node;
best->size = sz;
}
best->used = 1;
best->tidx = osGetCurrentTid();
ret = best->data;
out:
trylockRelease(&gHeapLock);
return ret;
}
void heapFree(void* ptr)
{
struct HeapNode *node, *t;
bool haveLock;
if (ptr == NULL) {
// NULL is a valid reply from heapAlloc, and thus it is not an error for
// us to receive it here. We just ignore it.
return;
}
haveLock = trylockTryTake(&gHeapLock);
node = ((struct HeapNode*)ptr) - 1;
node->used = 0;
node->tidx = 0;
if (haveLock) {
while (node->prev && !node->prev->used)
node = node->prev;
while ((t = heapPrvGetNext(node)) && !t->used) {
node->size += sizeof(struct HeapNode) + t->size;
if (gHeapTail == t)
gHeapTail = node;
}
if ((t = heapPrvGetNext(node)))
t->prev = node;
trylockRelease(&gHeapLock);
}
else
gNeedFreeMerge = true;
}
int heapFreeAll(uint32_t tid)
{
struct HeapNode *node;
bool haveLock;
int count = 0;
if (!tid)
return -1;
// this can only fail if called from interrupt
haveLock = trylockTryTake(&gHeapLock);
if (!haveLock)
return -1;
tid &= TIDX_MASK;
for (node = gHeapHead; node; node = heapPrvGetNext(node)) {
if (node->tidx == tid) {
node->used = 0;
node->tidx = 0;
count++;
}
}
gNeedFreeMerge = count > 0;
trylockRelease(&gHeapLock);
return count;
}
int heapGetFreeSize(int *numChunks, int *largestChunk)
{
struct HeapNode *node;
bool haveLock;
int bytes = 0;
*numChunks = *largestChunk = 0;
// this can only fail if called from interrupt
haveLock = trylockTryTake(&gHeapLock);
if (!haveLock)
return -1;
for (node = gHeapHead; node; node = heapPrvGetNext(node)) {
if (!node->used) {
if (node->size > *largestChunk)
*largestChunk = node->size;
bytes += node->size + sizeof(struct HeapNode);
(*numChunks)++;
}
}
trylockRelease(&gHeapLock);
return bytes;
}
int heapGetTaskSize(uint32_t tid)
{
struct HeapNode *node;
bool haveLock;
int bytes = 0;
// this can only fail if called from interrupt
haveLock = trylockTryTake(&gHeapLock);
if (!haveLock)
return -1;
tid &= TIDX_MASK;
for (node = gHeapHead; node; node = heapPrvGetNext(node)) {
if (node->used && node->tidx == tid) {
bytes += node->size + sizeof(struct HeapNode);
}
}
trylockRelease(&gHeapLock);
return bytes;
}