src/lib/support/Pool.cpp

   1 /*
   2  *
   3  *    Copyright (c) 2020 Project CHIP Authors
   4  *    Copyright (c) 2013 Nest Labs, Inc.
   5  *    All rights reserved.
   6  *
   7  *    Licensed under the Apache License, Version 2.0 (the "License");
   8  *    you may not use this file except in compliance with the License.
   9  *    You may obtain a copy of the License at
  10  *
  11  *        http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  *    Unless required by applicable law or agreed to in writing, software
  14  *    distributed under the License is distributed on an "AS IS" BASIS,
  15  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  *    See the License for the specific language governing permissions and
  17  *    limitations under the License.
  18  */
  19
  20 #include <support/Pool.h>
  21
  22 #include <nlassert.h>
  23
  24 namespace chip {
  25
  26 StaticAllocatorBitmap::StaticAllocatorBitmap(void * storage, std::atomic<tBitChunkType> * usage, size_t capacity,
  27                                              size_t elementSize) :
  28     StaticAllocatorBase(capacity),
  29     mElements(storage), mElementSize(elementSize), mUsage(usage)
  30 {
  31     for (size_t word = 0; word * kBitChunkSize < Capacity(); ++word)
  32     {
  33         mUsage[word].store(0);
  34     }
  35 }
  36
  37 void * StaticAllocatorBitmap::Allocate()
  38 {
  39     for (size_t word = 0; word * kBitChunkSize < Capacity(); ++word)
  40     {
  41         auto & usage = mUsage[word];
  42         auto value   = usage.load(std::memory_order_relaxed);
  43         for (size_t offset = 0; offset < kBitChunkSize && offset + word * kBitChunkSize < Capacity(); ++offset)
  44         {
  45             if ((value & (kBit1 << offset)) == 0)
  46             {
  47                 if (usage.compare_exchange_strong(value, value | (kBit1 << offset)))
  48                 {
  49                     mAllocated++;
  50                     return At(word * kBitChunkSize + offset);
  51                 }
  52                 else
  53                 {
  54                     value = usage.load(std::memory_order_relaxed); // if there is a race, update new usage
  55                 }
  56             }
  57         }
  58     }
  59     return nullptr;
  60 }
  61
  62 void StaticAllocatorBitmap::Deallocate(void * element)
  63 {
  64     size_t index  = IndexOf(element);
  65     size_t word   = index / kBitChunkSize;
  66     size_t offset = index - (word * kBitChunkSize);
  67
  68     // ensure the element is in the pool
  69     assert(index < Capacity());
  70
  71     auto value = mUsage[word].fetch_and(~(kBit1 << offset));
  72     nlASSERT((value & (kBit1 << offset)) != 0); // assert fail when free an unused slot
  73     mAllocated--;
  74 }
  75
  76 } // namespace chip