text: /*----------------------------------------------------------------------------
   * Tencent is pleased to support the open source community by making TencentOS
   * available.
   *
   * Copyright (C) 2019 THL A29 Limited, a Tencent company. All rights reserved.
   * If you have downloaded a copy of the TencentOS binary from Tencent, please
   * note that the TencentOS binary is licensed under the BSD 3-Clause License.
   *
   * If you have downloaded a copy of the TencentOS source code from Tencent,
   * please note that TencentOS source code is licensed under the BSD 3-Clause
   * License, except for the third-party components listed below which are
   * subject to different license terms. Your integration of TencentOS into your
   * own projects may require compliance with the BSD 3-Clause License, as well
   * as the other licenses applicable to the third-party components included
   * within TencentOS.
   *---------------------------------------------------------------------------*/
  
  /*
  ** Two Level Segregated Fit memory allocator, version 3.1.
  ** Written by Matthew Conte
  ** http://tlsf.baisoku.org
  **
  ** Based on the original documentation by Miguel Masmano:
  ** http://www.gii.upv.es/tlsf/main/docs
  **
  ** This implementation was written to the specification
  ** of the document, therefore no GPL restrictions apply.
  **
  ** Copyright (c) 2006-2016, Matthew Conte
  ** All rights reserved.
  **
  ** Redistribution and use in source and binary forms, with or without
  ** modification, are permitted provided that the following conditions are met:
  **     * Redistributions of source code must retain the above copyright
  **       notice, this list of conditions and the following disclaimer.
  **     * 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.
  **     * 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 MATTHEW CONTE 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.
  */
  
  #ifndef _TOS_MMHEAP_H_
  #define  _TOS_MMHEAP_H_
  
  #if TOS_CFG_MMHEAP_EN > 0u
  
  /**
   * log2 of number of linear subdivisions of block sizes. Larger
   * values require more memory in the control structure. Values of
   * 4 or 5 are typical.
   */
  #define K_MMHEAP_SL_INDEX_COUNT_LOG2    5
  
  /* All allocation sizes and addresses are aligned to 4 bytes. */
  #define K_MMHEAP_ALIGN_SIZE_LOG2        2
  #define K_MMHEAP_ALIGN_SIZE             (1 << K_MMHEAP_ALIGN_SIZE_LOG2)
  
  /*
   * We support allocations of sizes up to (1 << K_MMHEAP_FL_INDEX_MAX) bits.
   * However, because we linearly subdivide the second-level lists, and
   * our minimum size granularity is 4 bytes, it doesn't make sense to
   * create first-level lists for sizes smaller than K_MMHEAP_SL_INDEX_COUNT * 4,
   * or (1 << (K_MMHEAP_SL_INDEX_COUNT_LOG2 + 2)) bytes, as there we will be
   * trying to split size ranges into more slots than we have available.
   * Instead, we calculate the minimum threshold size, and place all
   * blocks below that size into the 0th first-level list.
   */
  #define K_MMHEAP_FL_INDEX_MAX           30
  #define K_MMHEAP_SL_INDEX_COUNT         (1 << K_MMHEAP_SL_INDEX_COUNT_LOG2)
  #define K_MMHEAP_FL_INDEX_SHIFT         (K_MMHEAP_SL_INDEX_COUNT_LOG2 + K_MMHEAP_ALIGN_SIZE_LOG2)
  #define K_MMHEAP_FL_INDEX_COUNT         (K_MMHEAP_FL_INDEX_MAX - K_MMHEAP_FL_INDEX_SHIFT + 1)
  
  #define K_MMHEAP_SMALL_BLOCK_SIZE       (1 << K_MMHEAP_FL_INDEX_SHIFT)
  
  #define K_MMHEAP_BLOCK_CURR_FREE        (1 << 0)
  #define K_MMHEAP_BLOCK_PREV_FREE        (1 << 1)
  #define K_MMHEAP_BLOCK_SIZE_MASK        ~(K_MMHEAP_BLOCK_CURR_FREE | K_MMHEAP_BLOCK_PREV_FREE)
  #define K_MMHEAP_BLOCK_STATE_MASK       (K_MMHEAP_BLOCK_CURR_FREE | K_MMHEAP_BLOCK_PREV_FREE)
  
  /**
   * Block structure.
   *
   * There are several implementation subtleties involved:
   * - The prev_phys_block field is only valid if the previous block is free.
   * - The prev_phys_block field is actually stored at the end of the
   *   previous block. It appears at the beginning of this structure only to
   *   simplify the implementation.
   * - The next_free / prev_free fields are only valid if the block is free.
   */
  typedef struct mmheap_blk_st {
      struct mmheap_blk_st *prev_phys_blk;
  
      size_t size;
  
      struct mmheap_blk_st *next_free;
      struct mmheap_blk_st *prev_free;
  } mmheap_blk_t;
  
  /**
   * A free block must be large enough to store its header minus the size of
   * the prev_phys_block field, and no larger than the number of addressable
   * bits for FL_INDEX.
   */
  #define K_MMHEAP_BLK_SIZE_MIN           (sizeof(mmheap_blk_t) - sizeof(mmheap_blk_t *))
  #define K_MMHEAP_BLK_SIZE_MAX           (1 << K_MMHEAP_FL_INDEX_MAX)
  
  #define K_MMHEAP_BLK_HEADER_OVERHEAD    (sizeof(size_t))
  #define K_MMHEAP_BLK_START_OFFSET       (TOS_OFFSET_OF_FIELD(mmheap_blk_t, size) + sizeof(size_t))
  
  /**
   * memory heap control
   */
  typedef struct k_mmheap_control_st {
      mmheap_blk_t    block_null; /**< Empty lists point at this block to indicate they are free. */
  
      uint32_t        fl_bitmap; /**< Bitmaps for free lists. */
      uint32_t        sl_bitmap[K_MMHEAP_FL_INDEX_COUNT];
  
      mmheap_blk_t   *blocks[K_MMHEAP_FL_INDEX_COUNT][K_MMHEAP_SL_INDEX_COUNT]; /**< Head of free lists. */
  } k_mmheap_ctl_t;
  
  /**
   * @brief Add a pool.
   * Add addtional pool to the heap.
   *
   * @attention None
   *
   * @param[in]   pool_start  start address of the pool.
   * @param[in]   pool_size   size of the pool.
   *
   * @return  errcode
   * @retval  #K_ERR_MMHEAP_INVALID_POOL_ADDR start address of the pool is invalid.
   * @retval  #K_ERR_MMHEAP_INVALID_POOL_SIZE size of the pool is invalid.
   * @retval  #K_ERR_NONE                     return successfully.
   */
  __API__ k_err_t tos_mmheap_pool_add(void *pool_start, size_t pool_size);
  
  /**
   * @brief Remove a pool.
   * Remove a pool from the heap.
   *
   * @attention None
   *
   * @param[in]   pool_start  start address of the pool.
   *
   * @return  None
   */
  __API__ void    tos_mmheap_pool_rmv(void *pool_start);
  
  /**
   * @brief Alloc memory.
   * Allocate size bytes and returns a pointer to the allocated memory.
   *
   * @attention size should no bigger than K_MMHEAP_BLK_SIZE_MAX.
   *
   * @param[in]   size    size of the memory.
   *
   * @return  the pointer to the allocated memory.
   */
  __API__ void   *tos_mmheap_alloc(size_t size);
  
  __API__ void   *tos_mmheap_calloc(size_t num, size_t size);
  
  /**
   * @brief Alloc start address aligned memory from the heap.
   * Alloc aligned address and specified size memory from the heap.
   *
   * @attention
   *
   * @param[in]   size    size of the memory.
   * @param[in]   align   address align mask of the memory.
   *
   * @return  the pointer to the allocated memory.
   */
  __API__ void   *tos_mmheap_aligned_alloc(size_t size, size_t align);
  
  /**
   * @brief Realloc memory from the heap.
   * Change the size of the memory block pointed to by ptr to size bytes.
   *
   * @attention
   * <ul>
   * <li> if ptr is K_NULL, then the call is equivalent to tos_mmheap_alloc(size), for all values of size.
   * <li> if ptr is if size is equal to zero, and ptr is not K_NULL, then the call is equivalent to tos_mmheap_free(ptr).
   * </ul>
   *
   * @param[in]   ptr     old pointer to the memory space.
   * @param[in]   size    new size of the memory space.
   *
   * @return  the new pointer to the allocated memory.
   */
  __API__ void   *tos_mmheap_realloc(void *ptr, size_t size);
  
  /**
   * @brief Free the memory.
   * Free the memory space pointed to by ptr, which must have been returned by a previous call to tos_mmheap_alloc(), tos_mmheap_aligned_alloc(), or tos_mmheap_realloc().
   *
   * @attention
   *
   * @param[in]   ptr     pointer to the memory.
   *
   * @return  None.
   */
  __API__ void    tos_mmheap_free(void *ptr);
  
  __KERNEL__ k_err_t mmheap_init(void *pool_start, size_t pool_size);
  
  #endif
  
  #endif /* _TOS_MMHEAP_H_ */
  
  