内存堆分配器库保持独立的结构？

2 回答

• 0

  我不知道，除了我的帽子之外，我还不知道任何可以使用的 jar 头实现 . 但是，使用C标准库中的花园种类容器，这似乎并不特别难以实现 .

  我建议使用两个 std::map 和一个 std::multimap 的简单方法 . 假设 bufaddr_t 是一个不透明的整数，表示外部缓冲区中的地址 . 由于我们讨论的是16 gig缓冲区，因此它必须是64位地址：

  typedef uint64_t memblockaddr_t;
  

  同样适用于已分配块的大小 .

  typedef uint64_t memblocksize_t;
  

  我想，只要不透明数据类型具有严格的弱排序，您就可以使用 memblockaddr_t 的其他内容 .

  第一部分很简单 . 跟踪所有已分配的块：

  std::map<memblockaddr_t, memblocksize_t> allocated;
  

  因此，当您在外部缓冲区中成功分配一块内存时，请将其插入此处 . 当您希望释放一块内存时，在此处查找已分配块的大小，并删除映射条目 . 很简单 .

  但那当然不是整个故事 . 现在，我们需要跟踪可用的未分配内存块 . 我们这样做：

  typedef std::multimap<memblocksize_t, memblockaddr_t> unallocated_t;
  
  unallocated_t unallocated;
  
  std::map<memblockaddr_t, unallocated_t::iterator> unallocated_lookup;
  

  unallocated 是外部缓冲区中所有未分配的块的集合，由块大小键入 . 关键是块大小 . 因此，当您需要分配特定大小的一块内存时，您可以简单地使用 lower_bound() 方法（或 upper_bound() ，如果您愿意）立即找到第一个块，其大小至少是您想要分配的大小 .

  当然，由于你可以有许多相同大小的块， unallocated 必须是 std::multimap .

  此外， unallocated_lookup 是一个由每个未分配的块的地址键入的映射，它为 unallocated 中的块块条目提供了迭代器 . 为什么你需要它会在一瞬间变得清晰 .

  所以：

  使用单个条目初始化一个新的，完全未分配的缓冲区：

  memblockaddr_t beginning=0; // Or, whatever represents the start of the buffer.
  auto p=unallocated.insert(std::make_pair(BUFFER_SIZE, beginning)).first;
  unallocated_lookup.insert(std::make_pair(beginning, p));
  

  然后：

  • 要分配一个块，请使用我上面提到的lower_bound（）/ upper_bound（）方法来查找至少一个大的第一个未分配的块，并从 unallocated 和 unallocated_lookup 中删除它的条目 . 如果需要解除分配（下面的步骤3） . 最后，将其插入 allocated 数组，以便记住分配的块的大小 .

  • 要解除分配块，请在 allocated 数组中查找，获取其大小，将其从 allocated 数组中删除，然后：

  • 将其插入 unallocated 和 unallocated_lookup ，类似于插入初始未分配块的方式，请参见上文 .

  • 但你还没有完成 . 然后，您必须使用 unallocated_lookup 在内存缓冲区中轻松查找前面未分配的块和以下未分配的块 . 如果它们中的任何一个或两个紧邻新释放的块，则必须将它们合并在一起 . 这应该是一个非常明显的过程 . 您可以简单地完成从 unallocated 和 unallocated_lookup 正式删除相邻块的动作，然后释放单个合并的块 .

  这是 unallocated_lookup 的真正目的，能够轻松地合并连续的未分配块 .

  据我所知，上述所有操作都具有对数复杂性 . 它们完全基于具有对数复杂性的 std::map 和 std::multimap 方法，而不是其他任何方法 .

  最后：

  取决于您的应用程序's behavior, you can easily tweak the implementation to internally round up the size of an allocated chunk to whatever multiple you wish. Or adjust the allocation strategy -- allocate from the smallest chunk that'足够大以满足分配请求，或者只是从大的未分配的块分配（简单，使用 end() 来查找它）等等...

  这是滚动您自己的实现的一个优点 - 您将总是有更大的灵活性来调整您自己的实现，然后您通常会有一些固定的外部库 .

  回复于 2024-04-29T15:08:16+08:00
• 1

  我正在发布我们实际上正在做的事情的更新 . 我最终实现了自己的远程内存分配器（下面的源代码） . 它在精神上类似于answer Sam suggests，但是在释放，加入等时使用boost侵入式RB树来避免一些log（N）查找 . 它在很多方面可能不太理想，但它对我们需要的东西运行得很好去做 . 如果您发现错误，请告诉我 .

  /*
   * Thread-safe remote memory allocator
   *
   * Author: Yuriy Romanenko
   * Copyright (c) 2015 Lytro, Inc.
   *
   */
  
  #pragma once
  
  #include <memory>
  #include <mutex>
  #include <cstdint>
  #include <cstdio>
  #include <functional>
  
  #include <boost/intrusive/rbtree.hpp>
  
  namespace bi = boost::intrusive;
  
  template<typename remote_ptr_t = void*,
           typename remote_size_t = size_t,
           typename remote_uintptr_t = uintptr_t>
  class RemoteAllocator
  {
      /* Internal structure used for keeping track of a contiguous block of
       * remote memory. It can be on one or two of the following RB trees:
       *    Free Chunks (sorted by size)
       *    All Chunks (sorted by remote pointer)
       */
      struct Chunk
      {
          bi::set_member_hook<> mRbFreeChunksHook;
          bi::set_member_hook<> mRbAllChunksHook;
  
          remote_uintptr_t mOffset;
          remote_size_t mSize;
          bool mFree;
  
          Chunk(remote_uintptr_t off, remote_size_t sz, bool fr)
                  : mOffset(off), mSize(sz), mFree(fr)
          {
  
          }
  
          bool contains(remote_uintptr_t off)
          {
              return (off >= mOffset) && (off < mOffset + mSize);
          }
      private:
          Chunk(const Chunk&);
          Chunk& operator=(const Chunk&);
      };
  
      struct ChunkCompareSize : public std::binary_function <Chunk,Chunk,bool>
      {
          bool operator() (const Chunk& x, const Chunk& y) const
          {
              return x.mSize < y.mSize;
          }
      };
      struct ChunkCompareOffset : public std::binary_function <Chunk,Chunk,bool>
      {
          bool operator() (const Chunk& x, const Chunk& y) const
          {
              return x.mOffset < y.mOffset;
          }
      };
  
      typedef bi::rbtree<Chunk,
                         bi::member_hook<Chunk,
                                         bi::set_member_hook<>,
                                         &Chunk::mRbFreeChunksHook>,
                         bi::compare< ChunkCompareSize > > FreeChunkTree;
  
      typedef bi::rbtree<Chunk,
                         bi::member_hook<Chunk,
                                         bi::set_member_hook<>,
                                         &Chunk::mRbAllChunksHook>,
                         bi::compare< ChunkCompareOffset > > AllChunkTree;
  
      // Thread safety lock
      std::mutex mLock;
      // Size of the entire pool
      remote_size_t mSize;
      // Start address of the pool
      remote_ptr_t mStartAddr;
  
      // Tree of free chunks
      FreeChunkTree mFreeChunks;
      // Tree of all chunks
      AllChunkTree mAllChunks;
  
      // This removes the chunk from both trees
      Chunk *unlinkChunk(Chunk *c)
      {
          mAllChunks.erase(mAllChunks.iterator_to(*c));
          if(c->mFree)
          {
              mFreeChunks.erase(mFreeChunks.iterator_to(*c));
          }
          return c;
      }
  
      // This reinserts the chunk into one or two trees, depending on mFree
      Chunk *relinkChunk(Chunk *c)
      {
          mAllChunks.insert_equal(*c);
          if(c->mFree)
          {
              mFreeChunks.insert_equal(*c);
          }
          return c;
      }
  
      /* This assumes c is 'free' and walks the mAllChunks tree to the left
       * joining any contiguous free chunks into this one
       */
      bool growFreeLeft(Chunk *c)
      {
          auto it = mAllChunks.iterator_to(*c);
          if(it != mAllChunks.begin())
          {
              it--;
              if(it->mFree)
              {
                  Chunk *left = unlinkChunk(&(*it));
                  unlinkChunk(c);
                  c->mOffset = left->mOffset;
                  c->mSize = left->mSize + c->mSize;
                  delete left;
                  relinkChunk(c);
                  return true;
              }
          }
          return false;
      }
      /* This assumes c is 'free' and walks the mAllChunks tree to the right
       * joining any contiguous free chunks into this one
       */
      bool growFreeRight(Chunk *c)
      {
          auto it = mAllChunks.iterator_to(*c);
          it++;
          if(it != mAllChunks.end())
          {
              if(it->mFree)
              {
                  Chunk *right = unlinkChunk(&(*it));
                  unlinkChunk(c);
                  c->mSize = right->mSize + c->mSize;
                  delete right;
                  relinkChunk(c);
                  return true;
              }
          }
          return false;
      }
  
  public:
      RemoteAllocator(remote_size_t size, remote_ptr_t startAddr) :
          mSize(size), mStartAddr(startAddr)
      {
          /* Initially we create one free chunk the size of the entire managed
           * memory pool, and add it to both trees
           */
          Chunk *all = new Chunk(reinterpret_cast<remote_uintptr_t>(mStartAddr),
                                 mSize,
                                 true);
          mAllChunks.insert_equal(*all);
          mFreeChunks.insert_equal(*all);
      }
  
      ~RemoteAllocator()
      {
          auto it = mAllChunks.begin();
  
          while(it != mAllChunks.end())
          {
              Chunk *pt = unlinkChunk(&(*it++));
              delete pt;
          }
      }
  
      remote_ptr_t malloc(remote_size_t bytes)
      {
          std::unique_lock<std::mutex> lock(mLock);
          auto fit = mFreeChunks.lower_bound(
                      Chunk(reinterpret_cast<remote_uintptr_t>(mStartAddr),
                            bytes,
                            true));
  
          /* Out of memory */
          if(fit == mFreeChunks.end())
              return remote_ptr_t{0};
  
          Chunk *ret = &(*fit);
          /* We need to split the chunk because it's not the exact size */
          /* Let's remove the node */
          mFreeChunks.erase(fit);
  
          if(ret->mSize != bytes)
          {
              Chunk *right, *left = ret;
  
              /* The following logic decides which way the heap grows
               * based on allocation size. I am not 100% sure this actually
               * helps with fragmentation with such a big threshold (50%)
               *
               * Check if we will occupy more than half of the chunk,
               * in that case, use the left side. */
              if(bytes > ret->mSize / 2)
              {
                  right = new Chunk(left->mOffset + bytes,
                                    left->mSize - bytes,
                                    true);
                  relinkChunk(right);
  
                  left->mSize = bytes;
                  left->mFree = false;
  
                  ret = left;
              }
              /* We'll be using less than half, let's use the right side. */
              else
              {
                  right = new Chunk(left->mOffset + left->mSize - bytes,
                                    bytes,
                                    false);
  
                  relinkChunk(right);
  
                  left->mSize = left->mSize - bytes;
                  mFreeChunks.insert_equal(*left);
  
                  ret = right;
              }
          }
          else
          {
              ret->mFree = false;
          }
  
          return reinterpret_cast<remote_ptr_t>(ret->mOffset);
      }
  
      remote_ptr_t malloc_aligned(remote_size_t bytes, remote_size_t alignment)
      {
          remote_size_t bufSize = bytes + alignment;
          remote_ptr_t mem = this->malloc(bufSize);
          remote_ptr_t ret = mem;
          if(mem)
          {
              remote_uintptr_t offset = reinterpret_cast<remote_uintptr_t>(mem);
              if(offset % alignment)
              {
                  offset = offset + (alignment - (offset % alignment));
              }
              ret = reinterpret_cast<remote_ptr_t>(offset);
          }
          return ret;
      }
  
      void free(remote_ptr_t ptr)
      {
          std::unique_lock<std::mutex> lock(mLock);
          Chunk ref(reinterpret_cast<remote_uintptr_t>(ptr), 0, false);
          auto it = mAllChunks.find(ref);
          if(it == mAllChunks.end())
          {
              it = mAllChunks.upper_bound(ref);
              it--;
          }
          if(!(it->contains(ref.mOffset)) || it->mFree)
              throw std::runtime_error("Could not find chunk to free");
  
          Chunk *chnk = &(*it);
          chnk->mFree = true;
          mFreeChunks.insert_equal(*chnk);
  
          /* Maximize space */
          while(growFreeLeft(chnk));
          while(growFreeRight(chnk));
      }
  
      void debugDump()
      {
          std::unique_lock<std::mutex> lock(mLock);
          int i = 0;
          printf("----------- All chunks -----------\n");
          for(auto it = mAllChunks.begin(); it != mAllChunks.end(); it++)
          {
              printf(" [%d] %lu -> %lu (%lu) %s\n",
                  i++,
                  it->mOffset,
                  it->mOffset + it->mSize,
                  it->mSize,
                  it->mFree ? "(FREE)" : "(NOT FREE)");
          }
          i = 0;
          printf("----------- Free chunks -----------\n");
          for(auto it = mFreeChunks.begin(); it != mFreeChunks.end(); it++)
          {
              printf(" [%d] %lu -> %lu (%lu) %s\n",
                  i++,
                  it->mOffset,
                  it->mOffset + it->mSize,
                  it->mSize,
                  it->mFree ? "(FREE)" : "(NOT FREE)");
          }
      }
  };
  

  回复于 2024-04-29T15:08:16+08:00