Line data    Source code

       1             : 
       2             : /* Copyright (c) 2015-2016, Human Brain Project
       3             :  *                          Stefan.Eilemann@epfl.ch
       4             :  */
       5             : 
       6             : #include "NonMovingBaseAllocator.h"
       7             : 
       8             : #include <algorithm>
       9             : #include <cassert>
      10             : #include <map>
      11             : #include <string.h>
      12             : 
      13             : namespace zerobuf
      14             : {
      15         407 : NonMovingBaseAllocator::NonMovingBaseAllocator(const size_t staticSize,
      16         407 :                                                const size_t numDynamic)
      17             :     : _staticSize(staticSize)
      18         407 :     , _numDynamic(numDynamic)
      19             : {
      20         407 : }
      21             : 
      22         407 : NonMovingBaseAllocator::~NonMovingBaseAllocator()
      23             : {
      24         407 : }
      25             : 
      26         518 : uint8_t* NonMovingBaseAllocator::_moveAllocation(const size_t index,
      27             :                                                  const bool copy,
      28             :                                                  const size_t newOffset,
      29             :                                                  const size_t newSize)
      30             : {
      31         518 :     uint64_t& offset = _getOffset(index);
      32         518 :     uint64_t& size = _getSize(index);
      33         518 :     uint8_t* base = getData();
      34             : 
      35         518 :     if (copy && offset > 0)
      36          82 :         ::memmove(base + newOffset, base + offset,
      37         164 :                   std::min(size, uint64_t(newSize)));
      38             : 
      39         518 :     offset = newOffset;
      40         518 :     size = newSize;
      41         518 :     return base + newOffset;
      42             : }
      43             : 
      44        2385 : uint8_t* NonMovingBaseAllocator::updateAllocation(const size_t index,
      45             :                                                   const bool copy,
      46             :                                                   const size_t newSize)
      47             : {
      48        2385 :     uint64_t& oldOffset = _getOffset(index);
      49        2385 :     uint64_t& oldSize = _getSize(index);
      50             : 
      51        2385 :     if (oldSize >= newSize) // enough space, update and return
      52             :     {
      53        1120 :         oldSize = newSize;
      54        1120 :         if (newSize > 0)
      55         941 :             return getData() + oldOffset;
      56             : 
      57         179 :         oldOffset = 0;
      58         179 :         return nullptr;
      59             :     }
      60             : 
      61        1265 :     if (oldOffset != 0) // Check for space in current place
      62             :     {
      63         948 :         uint64_t nextOffset = getSize();
      64             : 
      65        4361 :         for (size_t i = 0; i < _numDynamic; ++i)
      66             :         {
      67        3413 :             const uint64_t offset = _getOffset(i);
      68        3413 :             if (offset != 0 && offset > oldOffset)
      69         581 :                 nextOffset = std::min(nextOffset, offset);
      70             :         }
      71             : 
      72         948 :         if (oldOffset + newSize < nextOffset) // enough space, update, return
      73             :         {
      74         747 :             oldSize = newSize;
      75         747 :             return getData() + oldOffset;
      76             :         }
      77             :     }
      78             : 
      79             :     // Check for a big enough hole
      80             :     //-- record allocations
      81             :     typedef std::map<size_t, size_t> ArrayMap; // offset -> size
      82        1036 :     ArrayMap arrays;                           // sort arrays by position
      83        6459 :     for (size_t i = 0; i < _numDynamic; ++i)
      84             :     {
      85        5941 :         const uint64_t offset = _getOffset(i);
      86        5941 :         if (i != index && offset >= _staticSize)
      87        3307 :             arrays[offset] = _getSize(i);
      88             :     }
      89             : 
      90             :     //-- find hole
      91         518 :     uint64_t start = _staticSize;
      92        3719 :     for (auto i = arrays.cbegin(); i != arrays.cend(); ++i)
      93             :     {
      94        3305 :         assert(i->first >= start);
      95        3305 :         if (i->first - start >= newSize)
      96         104 :             return _moveAllocation(index, copy, start, newSize);
      97             : 
      98        3201 :         start = i->first + i->second;
      99             :     }
     100             : 
     101             :     //-- check for space after last allocation
     102         414 :     if (getSize() - start >= newSize)
     103         113 :         return _moveAllocation(index, copy, start, newSize);
     104             : 
     105             :     // realloc space at the end
     106         301 :     if (start + newSize <= getSize())
     107             :         throw std::runtime_error(
     108           0 :             "Internal allocator error: allocation shrinks from " +
     109           0 :             std::to_string(getSize()) + " to " + std::to_string(start) + " + " +
     110           0 :             std::to_string(newSize));
     111             : 
     112         301 :     _resize(start + newSize);
     113         301 :     return _moveAllocation(index, copy, start, newSize);
     114             : }
     115             : 
     116          22 : void NonMovingBaseAllocator::compact(const float threshold)
     117             : {
     118          22 :     uint64_t dynamicSize = 0;
     119         195 :     for (size_t i = 0; i < _numDynamic; ++i)
     120         173 :         if (_getOffset(i) > 0)
     121         130 :             dynamicSize += _getSize(i);
     122             : 
     123          22 :     const uint64_t minSize = _staticSize + dynamicSize;
     124          22 :     if (float(getSize() - minSize) / float(minSize) < threshold)
     125          14 :         return;
     126             : 
     127             :     // OPT: Surely there is a clever algo to do this in place, but for now use
     128             :     //      two copies:
     129          16 :     std::unique_ptr<uint8_t[]> buffer(new uint8_t[dynamicSize]);
     130           8 :     uint8_t* iter = buffer.get();
     131          60 :     for (size_t i = 0; i < _numDynamic; ++i)
     132             :     {
     133          52 :         uint64_t& offset = _getOffset(i);
     134          52 :         if (offset == 0)
     135          22 :             continue;
     136             : 
     137          30 :         const uint64_t size = _getSize(i);
     138          30 :         const uint64_t newOffset = iter - buffer.get() + _staticSize;
     139          30 :         ::memcpy(iter, getData() + offset, size);
     140          30 :         iter += size;
     141          30 :         offset = newOffset;
     142             :     }
     143             : 
     144           8 :     _resize(minSize);
     145           8 :     ::memcpy(getData() + _staticSize, buffer.get(), dynamicSize);
     146             : }
     147             : }