src/core/utils/heap.cpp

/*
 *  Copyright (c) 2017, The OpenThread Authors.
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions are met:
 *  1. Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *  2. Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *  3. Neither the name of the copyright holder nor the
 *     names of its contributors may be used to endorse or promote products
 *     derived from this software without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 *  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 *  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 *  ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 *  LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 *  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 *  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 *  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 *  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 *  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 *  POSSIBILITY OF SUCH DAMAGE.
 */

/**
 * @file
 *   This file implements heap.
 *
 */

#include "heap.hpp"

#if !OPENTHREAD_CONFIG_HEAP_EXTERNAL_ENABLE

#include <string.h>

#include "common/code_utils.hpp"
#include "common/debug.hpp"

namespace ot {
namespace Utils {

Heap::Heap(void)
{
    Block &super = BlockAt(kSuperBlockOffset);
    super.SetSize(kSuperBlockSize);

    Block &first = BlockRight(super);
    first.SetSize(kFirstBlockSize);

    Block &guard = BlockRight(first);
    guard.SetSize(Block::kGuardBlockSize);

    super.SetNext(BlockOffset(first));
    first.SetNext(BlockOffset(guard));

    mMemory.mFreeSize = kFirstBlockSize;
}

void *Heap::CAlloc(size_t aCount, size_t aSize)
{
    void *   ret  = nullptr;
    Block *  prev = nullptr;
    Block *  curr = nullptr;
    uint16_t size = static_cast<uint16_t>(aCount * aSize);

    VerifyOrExit(size);

    size += kAlignSize - 1 - kBlockRemainderSize;
    size &= ~(kAlignSize - 1);
    size += kBlockRemainderSize;

    prev = &BlockSuper();
    curr = &BlockNext(*prev);

    while (curr->GetSize() < size)
    {
        prev = curr;
        curr = &BlockNext(*curr);
    }

    VerifyOrExit(curr->IsFree());

    prev->SetNext(curr->GetNext());

    if (curr->GetSize() > size + sizeof(Block))
    {
        const uint16_t newBlockSize = curr->GetSize() - size - sizeof(Block);
        curr->SetSize(size);

        Block &newBlock = BlockRight(*curr);
        newBlock.SetSize(newBlockSize);
        newBlock.SetNext(0);

        if (prev->GetSize() < newBlockSize)
        {
            BlockInsert(*prev, newBlock);
        }
        else
        {
            BlockInsert(BlockSuper(), newBlock);
        }

        mMemory.mFreeSize -= sizeof(Block);
    }

    mMemory.mFreeSize -= curr->GetSize();

    curr->SetNext(0);

    memset(curr->GetPointer(), 0, size);
    ret = curr->GetPointer();

exit:
    return ret;
}

void Heap::BlockInsert(Block &aPrev, Block &aBlock)
{
    Block *prev = &aPrev;

    for (Block *block = &BlockNext(*prev); block->GetSize() < aBlock.GetSize(); block = &BlockNext(*block))
    {
        prev = block;
    }

    aBlock.SetNext(prev->GetNext());
    prev->SetNext(BlockOffset(aBlock));
}

Block &Heap::BlockPrev(const Block &aBlock)
{
    Block *prev = &BlockSuper();

    while (prev->GetNext() != BlockOffset(aBlock))
    {
        prev = &BlockNext(*prev);
    }

    return *prev;
}

void Heap::Free(void *aPointer)
{
    if (aPointer == nullptr)
    {
        return;
    }

    Block &block = BlockOf(aPointer);
    Block &right = BlockRight(block);

    mMemory.mFreeSize += block.GetSize();

    if (IsLeftFree(block))
    {
        Block *prev = &BlockSuper();
        Block *left = &BlockNext(*prev);

        mMemory.mFreeSize += sizeof(Block);

        for (const uint16_t offset = block.GetLeftNext(); left->GetNext() != offset; left = &BlockNext(*left))
        {
            prev = left;
        }

        // Remove left from free list.
        prev->SetNext(left->GetNext());
        left->SetNext(0);

        if (right.IsFree())
        {
            mMemory.mFreeSize += sizeof(Block);

            if (right.GetSize() > left->GetSize())
            {
                for (const uint16_t offset = BlockOffset(right); prev->GetNext() != offset; prev = &BlockNext(*prev))
                    ;
            }
            else
            {
                prev = &BlockPrev(right);
            }

            // Remove right from free list.
            prev->SetNext(right.GetNext());
            right.SetNext(0);

            // Add size of right.
            left->SetSize(left->GetSize() + right.GetSize() + sizeof(Block));
        }

        // Add size of current block.
        left->SetSize(left->GetSize() + block.GetSize() + sizeof(Block));

        BlockInsert(*prev, *left);
    }
    else
    {
        if (right.IsFree())
        {
            Block &prev = BlockPrev(right);
            prev.SetNext(right.GetNext());
            block.SetSize(block.GetSize() + right.GetSize() + sizeof(Block));
            BlockInsert(prev, block);

            mMemory.mFreeSize += sizeof(Block);
        }
        else
        {
            BlockInsert(BlockSuper(), block);
        }
    }
}

} // namespace Utils
} // namespace ot

#endif // !OPENTHREAD_CONFIG_HEAP_EXTERNAL_ENABLE