Biblioteka alokatorów pamięci, która przechowuje oddzielne struktury?

Question

Oto mój problem: potrzebuję zarządzać pamięcią w zdalnym, ciągłym buforze, którego mój program nie może odczytać ani zapisać. Musi mieć semantykę malloc()/free() i ustawienie wspomagające minimalne wyrównanie i unikanie fragmentacji (gdy tylko jest to możliwe). Ponieważ nie mogę bezpośrednio odczytać lub zapisać do tego bufora, potrzebuję użyć lokalnych struktur do zarządzania wszystkimi alokacjami.

Już używam doładowania, więc jeśli coś do zrobienia w środku może być masowane, aby to zrobić, byłoby świetnie. Jednak nie mam nic przeciwko używaniu biblioteki C lub czegoś podobnego.

Jako przykład muszę non-IPC wersję:

boost::interprocess::basic_managed_external_buffer< 
        char, 
        boost::interprocess::rbtree_best_fit< 
              boost::interprocess::mutex_family, 
              boost::interprocess::offset_ptr<void>, 
              SOME_ALIGNMENT>, 
        boost::interprocess::iset_index> 

najlepiej z malloc/free semantyki zamiast new/delete ale bez kiedykolwiek rzeczywiście odczytu lub zapisu do bufora bazowego (i przechowywanie wszystkich informacji o alokacji/struktur danych w oddzielnym buforze)

Jakieś pomysły?

P.S. Nie chcę, aby przykład boost :: interroces był mylący, po prostu znam interfejs, więc używam go jako przykładu. Aplikacja nie jest w rzeczywistości interprocesowa, a alokator będzie używany tylko z mojej aplikacji.

W szczególności chciałbym móc zarządzać zewnętrznym buforem 16 GB z rozmiarami alokacji od 128 bajtów aż do 512 MB. Jest to ściśle 64-bitowy kod, ale nawet wtedy wolałbym, aby typ wskaźnika był parametrem szablonu, więc mogę użyć jawnie uint64_t.

Answer 1

Zamieszczam aktualizację tego, co faktycznie zrobiliśmy. Zlikwidowałem implementację własnego programu do zdalnego przydzielania pamięci (źródło poniżej). Jest on duchowo podobny do answer Sam suggests, ale wykorzystuje inwazyjne drzewa RB, aby uniknąć niektórych wyszukiwań log (N) podczas zwalniania, łączenia itp. Jest bezpieczny dla wątków i obsługuje różne typy zdalnego wskaźnika/przesunięcia jako parametry szablonu. Prawdopodobnie nie jest to idealne rozwiązanie na wiele sposobów, ale działało wystarczająco dobrze na to, czego potrzebowaliśmy. Jeśli znajdziesz błędy, daj mi znać.

/* 
* 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)"); 
     } 
    } 
}; 

Answer 2

Nie wiem, z góry mojego kapelusza, o jakiejkolwiek puszkowanej implementacji, z której można korzystać. Jednak wydaje się, że nie jest to szczególnie trudne do zrealizowania, używając tylko kontenerów odmiany ogrodowej w standardowej bibliotece C++.

Polecam proste podejście, które używa dwóch std::map s i jednego std::multimap. Powiedzmy, że bufaddr_t jest nieprzezroczystą liczbą całkowitą, która reprezentuje adres w zewnętrznym buforze. Ponieważ mówimy o buforze 16-gigabitowym, musi to być adres 64-bitowy:

typedef uint64_t memblockaddr_t; 

Podobnie jak rozmiar przydzielonego bloku.

typedef uint64_t memblocksize_t; 

Można by, jak sądzę, należy użyć coś innego dla memblockaddr_t, dopóki nieprzezroczysty typ danych ma ścisły słaby zamówieniu.

Pierwsza część jest łatwa. Śledzenie wszystkich przydzielonych bloków:

std::map<memblockaddr_t, memblocksize_t> allocated; 

Po pomyślnym przydzieleniu fragmentu pamięci w buforze zewnętrznym należy go wstawić tutaj. Jeśli chcesz zwolnić część pamięci, wyszukaj tutaj rozmiar przydzielonego bloku i usuń wpis mapy. Wystarczająco proste.

Ale to oczywiście nie jest cała historia. Teraz musimy śledzić dostępne, nieprzydzielone bloki pamięci. Zróbmy to w ten sposób:

typedef std::multimap<memblocksize_t, memblockaddr_t> unallocated_t; 

unallocated_t unallocated; 

std::map<memblockaddr_t, unallocated_t::iterator> unallocated_lookup; 

unallocated to zbiór wszystkich nieprzypisanych kawałki w buforze zewnętrznego zamocowanej przez wielkość porcji. Kluczem jest rozmiar porcji.Tak więc, kiedy potrzebujesz przydzielić kawałek pamięci o określonym rozmiarze, możesz po prostu użyć metody lower_bound() (lub upper_bound(), jeśli wolisz), aby od razu znaleźć pierwszą porcję, której rozmiar jest najmniejszy, jak chcesz przydzielić.

A ponieważ możesz oczywiście mieć wiele kawałków o tym samym rozmiarze, unallocated musi być std::multimap.

Ponadto, unallocated_lookup jest mapą wpisaną przez adres każdej nieprzydzielonej porcji, która daje iterator dla wpisu tego kawałka w unallocated. Dlaczego tego potrzebujesz, stanie się jasne za chwilę.

Tak więc:

Inicjalizacja nowy, całkowicie nieprzydzielone bufor z jednej pozycji:

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)); 

następnie:

1. przydzielić bloku użyć LOWER_BOUND()/UPPER_BOUND() podejście, jak wspomniałem powyżej, aby znaleźć pierwszy nieprzydzielony fragment, który jest co najmniej tak duży i usunąć jego wpis z unallocated i unallocated_lookup. Jeśli jest to coś więcej niż to, czego potrzebujesz, zwróć nadmiar z powrotem do puli, tak jakby dodatkowa kwota, której nie potrzebujesz, jest zwalniana (krok 3 poniżej). Na koniec wstaw tę tablicę do tablicy allocated, aby zapamiętać, jak dużą jest przydzieloną porcję.

2. Aby deallocate blok, szukać go w tablicy allocated, aby uzyskać jego rozmiar, należy go usunąć z tablicy allocated, a następnie:

3. Włóż go do unallocated i unallocated_lookup, podobnie jak początkowe nieprzydzielony fragment został wstawiony, patrz wyżej.

4. Ale jeszcze nie skończyłeś. Następnie należy użyć unallocated_lookup, aby w sposób trywialny wyszukać poprzednią nieprzydzieloną porcję i następujący nieprzydzielony fragment w buforze pamięci. Jeśli którykolwiek z nich albo sąsiaduje bezpośrednio z nowo uwolnionym fragmentem, musisz połączyć je razem. To powinien być bardzo oczywisty proces. Możesz po prostu przejść przez proces oficjalnego usuwania sąsiadujących fragmentów pojedynczo, od unallocated i unallocated_lookup, a następnie zwalniając pojedynczą, scaloną porcję.

To jest prawdziwy cel unallocated_lookup, aby móc łatwo łączyć sąsiadujące nieprzydzielonych kawałki.

O ile mi wiadomo, wszystkie powyższe operacje mają logarytmiczną złożoność. Są one całkowicie oparte na metodach std::map i std::multimap, które mają złożoność logarytmiczną i nic więcej.

Wreszcie:

zależności zachowanie swojej aplikacji, można łatwo dostosować do wdrażania wewnętrznie zaokrąglić w górę rozmiaru przydzielonego fragmentu do wielokrotnego cokolwiek chcesz. Lub dostosuj strategię alokacji - przydzielaj od najmniejszej porcji, która jest wystarczająco duża, aby spełnić żądanie alokacji, lub po prostu przydzielaj z dużej nieprzydzielonej porcji (proste, użyj end(), aby ją znaleźć), itd ...

Jest to jedna z korzyści w rozwijaniu własnej implementacji - zawsze będziesz mieć znacznie większą elastyczność w dostosowywaniu własnej implementacji, wtedy zwykle będziesz mieć dostępną bibliotekę zewnętrzną.