compiler/luci-interpreter/include/luci_interpreter/BuddyMemoryManager.h

   1 /* Copyright (c) 2021 Samsung Electronics Co., Ltd. All Rights Reserved
   2  *
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at
   6  *
   7  *    http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15
  16 #include "luci_interpreter/MemoryManager.h"
  17
  18 #ifndef LUCI_INTERPRETER_BUDDY_MEMORY_MANAGER_H
  19 #define LUCI_INTERPRETER_BUDDY_MEMORY_MANAGER_H
  20
  21 namespace luci_interpreter
  22 {
  23
  24 class BuddyMemoryManager : public IMemoryManager
  25 {
  26 public:
  27   BuddyMemoryManager(uint8_t *memory_start, int32_t memSize);
  28
  29   void allocate_memory(luci_interpreter::Tensor &tensor) final;
  30   void release_memory(luci_interpreter::Tensor &tensor) final;
  31
  32 private:
  33   struct Block
  34   {
  35     Block *next_free;
  36     bool is_free;
  37     uint32_t size;
  38     // debug field
  39     Block *self;
  40   };
  41
  42   Block *_start_block;
  43   int32_t _num_blocks;
  44   uint32_t _size;
  45   Block *_free_blocks[32]{};
  46
  47   static int32_t lowerLog2(uint32_t val)
  48   {
  49     int32_t i = 0;
  50     while (val >>= 1)
  51       i++;
  52
  53     return i;
  54   }
  55
  56   void addToBlocks(Block *block, int32_t l)
  57   {
  58     if (!block)
  59       return;
  60
  61     block->next_free = _free_blocks[l];
  62     _free_blocks[l] = block;
  63   }
  64
  65   void removeFromBlocks(const Block *block, int32_t l)
  66   {
  67     if (!block)
  68       return;
  69
  70     Block *tmp = _free_blocks[l];
  71
  72     if (block == tmp)
  73     {
  74       _free_blocks[l] = block->next_free;
  75       return;
  76     }
  77
  78     while (tmp)
  79     {
  80       if (tmp->next_free == block)
  81       {
  82         tmp->next_free = block->next_free;
  83         return;
  84       }
  85
  86       tmp = tmp->next_free;
  87     }
  88   }
  89
  90   void divideBlock(Block *block, int32_t l)
  91   {
  92     int32_t size = ((block->size + sizeof(Block)) / 2) - sizeof(Block);
  93
  94     removeFromBlocks(block, l);
  95
  96     // there is no need to add to the free_blocks list here
  97     block->is_free = true;
  98     block->size = size;
  99     block->self = block;
 100
 101     Block *buddy;
 102     buddy = (Block *)((uint8_t *)block + sizeof(Block) + size);
 103     buddy->is_free = true;
 104     buddy->size = size;
 105     buddy->self = buddy;
 106
 107     addToBlocks(buddy, l - 1);
 108   }
 109
 110   Block *mergeBlock(Block *block)
 111   {
 112     Block *buddy;
 113
 114     const int32_t l = lowerLog2(block->size + sizeof(Block));
 115
 116     const int64_t address = ((uint8_t *)block - (uint8_t *)_start_block);
 117     buddy = (Block *)((address ^ (1 << l)) + (uint8_t *)_start_block);
 118
 119     if (!buddy->is_free || buddy->size != block->size)
 120       return nullptr;
 121
 122     if (block > buddy)
 123     {
 124       Block *x = block;
 125       block = buddy;
 126       buddy = x;
 127     }
 128
 129     removeFromBlocks(block, l);
 130     removeFromBlocks(buddy, l);
 131
 132     block->size = block->size * 2 + sizeof(Block);
 133     block->is_free = true;
 134     block->self = block;
 135
 136     addToBlocks(block, l + 1);
 137
 138     return block;
 139   }
 140 };
 141
 142 } // namespace luci_interpreter
 143
 144 #endif // LUCI_INTERPRETER_BUDDY_MEMORY_MANAGER_H