4
\$\begingroup\$

After writing a C++ simulator for malloc() and free(), (C++ imitation of glibc malloc(), free()),

I thought: "My simulator cannot expand the initial arena. Then how about giving the initial arena a really big one from the beginning? If I can't put the arena in the main memory, I can just have it on a disk file!"

So I wrote a polymorphic memory resource that utilizes a disk file.

FileArenaResource.h

#include "MemoryMappedFile.h"
#include <filesystem>
#include <memory_resource>
#include <stdexcept>

namespace frozenca {

class FileArenaResource : public std::pmr::memory_resource {
private:
  MemoryMappedFile file_;

public:
  FileArenaResource(const std::filesystem::path &path) : file_{path} {}

private:
  void *do_allocate(std::size_t bytes, std::size_t alignment) override {
    if (bytes % alignment) {
      throw std::invalid_argument("alloc bytes aren't aligned");
    } 
    if (bytes > file_.size()) {
      file_.resize(bytes);
    }
    return file_.data();
  }

  void do_deallocate(void *ptr, std::size_t bytes, std::size_t alignment) override {
    if (bytes % alignment) {
      throw std::invalid_argument("dealloc bytes aren't aligned");
    }
    if (ptr != file_.data()) {
      throw std::invalid_argument("dealloc arena pointer is not equal to begin of the file");
    }
    if (bytes != static_cast<std::size_t>(file_.size())) {
      throw std::invalid_argument("dealloc arena size is not equal to file size");
    }
  }

  bool do_is_equal(const std::pmr::memory_resource &other) const noexcept override {
    if (this == &other) {
      return true;
    }
    auto op = dynamic_cast<const FileArenaResource *>(&other);
    return op && op->file_ == file_;
  }
};

} // namespace frozenca

MemoryMappedFile.h (mostly copy-and-paste from boost::mapped_file, you can skip this)

#include <cassert>
#include <filesystem>
#include <stdexcept>

#if __linux__
#include <cerrno>
#include <fcntl.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
#elif _WIN32 || _WIN64
#include <windows.h>
#else
static_assert(false, "Unsupported OS\n");
#endif

namespace frozenca {

class MemoryMappedFile {
public:
  static inline constexpr std::size_t new_file_size_ = (1UL << 20UL);
#if __linux__
  using handle_type = int;
#elif _WIN32 || _WIN64
  using handle_type = HANDLE;
#else
  static_assert(false, "Unsupported OS\n");
#endif
  using path_type = std::filesystem::path::value_type;

private:
  const std::filesystem::path path_;
  void *data_ = nullptr;
  std::size_t size_ = 0;

  handle_type handle_ = 0;
  int flags_ = 0;
#if _WIN32 || _WIN64
  handle_type mapped_handle_ = 0;
#endif // Windows

public:
  MemoryMappedFile(const std::filesystem::path &path) : path_{path} {
    bool exists = std::filesystem::exists(path);
    open_file(path.c_str(), exists);
    map_file();
  }

  ~MemoryMappedFile() noexcept {
    if (!data_) {
      return;
    }
    bool error = false;
    error = !unmap_file() || error;
    error = !close_file() || error;
  }

private:
  void open_file(const path_type *path, bool exists) {
#if __linux__
    flags_ = O_RDWR;
    if (!exists) {
      flags_ |= (O_CREAT | O_TRUNC);
    }
#ifdef _LARGEFILE64_SOURCE
    flags |= O_LARGEFILE;
#endif
    errno = 0;
    handle_ = open(path, flags_, S_IRWXU);
    if (errno != 0) {
      throw std::runtime_error("file open failed\n");
    }

    if (!exists) {
      if (ftruncate(handle_, new_file_size_) == -1) {
        throw std::runtime_error("failed setting file size\n");
      }
    }

    struct stat info;
    bool success = (fstat(handle_, &info) != -1);
    size_ = info.st_size;
    if (!success) {
      throw std::runtime_error("failed querying file size\n");
    }
#elif _WIN32 || _WIN64
    DWORD dwDesiredAccess = GENERIC_READ | GENERIC_WRITE;
    DWORD dwCreationDisposition = exists ? OPEN_EXISTING : CREATE_ALWAYS;
    DWORD dwFlagsandAttributes = FILE_ATTRIBUTE_TEMPORARY;
    handle_ = CreateFileW(path, dwDesiredAccess, FILE_SHARE_READ, 0,
                          dwCreationDisposition, dwFlagsandAttributes, 0);
    if (handle_ == INVALID_HANDLE_VALUE) {
      throw std::runtime_error("file open failed\n");
    }

    if (!exists) {
      LONG sizehigh = (new_file_size_ >> (sizeof(LONG) * 8));
      LONG sizelow = (new_file_size_ & 0xffffffff);
      DWORD result = SetFilePointer(handle_, sizelow, &sizehigh, FILE_BEGIN);
      if ((result == INVALID_SET_FILE_POINTER && GetLastError() != NO_ERROR) ||
          !SetEndOfFile(handle_)) {
        throw std::runtime_error("failed setting file size\n");
      }
    }

    typedef BOOL(WINAPI * func)(HANDLE, PLARGE_INTEGER);
    HMODULE hmod = GetModuleHandleA("kernel32.dll");
    func get_size =
        reinterpret_cast<func>(GetProcAddress(hmod, "GetFileSizeEx"));
    if (get_size) {
      LARGE_INTEGER info;
      if (get_size(handle_, &info)) {
        std::int64_t size =
            ((static_cast<int64_t>(info.HighPart) << 32) | info.LowPart);
        size_ = static_cast<size_t>(size);
      } else {
        throw std::runtime_error("failed querying file size");
      }
    } else {
      DWORD hi = 0;
      DWORD low = 0;
      if ((low = GetFileSize(handle_, &hi)) != INVALID_FILE_SIZE) {
        std::int64_t size = (static_cast<int64_t>(hi) << 32) | low;
        size_ = static_cast<size_t>(size);
      } else {
        throw std::runtime_error("failed querying file size");
        return;
      }
    }
#else
    static_assert(false, "Unsupported OS\n");
#endif
  }

  void map_file() {
#if __linux__
    void *data =
        mmap(0, file_size_, PROT_READ | PROT_WRITE, MAP_SHARED, handle_, 0);
    if (data == reinterpret_cast<void *>(-1)) {
      throw std::runtime_error("failed mapping file");
    }
    data_ = data;
#elif _WIN32 || _WIN64
    DWORD protect = PAGE_READWRITE;
    mapped_handle_ = CreateFileMappingA(handle_, 0, protect, 0, 0, 0);
    if (!mapped_handle_) {
      throw std::runtime_error("failed mapping file");
    }

    DWORD access = FILE_MAP_WRITE;
    void *data = MapViewOfFileEx(mapped_handle_, access, 0, 0, size_, 0);
    if (!data) {
      throw std::runtime_error("failed mapping file");
    }
    data_ = data;
#else
    static_assert(false, "Unsupported OS\n");
#endif
  }

  bool close_file() noexcept {
#if __linux__
    return close(handle_) == 0;
#elif _WIN32 || _WIN64
    return CloseHandle(handle_);
#else
    static_assert(false, "Unsupported OS\n");
#endif
  }

  bool unmap_file() noexcept {
#if __linux__
    return (munmap(data_, file_size_) == 0);
#elif _WIN32 || _WIN64
    bool error = false;
    error = !UnmapViewOfFile(data_) || error;
    error = !CloseHandle(mapped_handle_) || error;
    mapped_handle_ = NULL;
    return !error;
#else
    static_assert(false, "Unsupported OS\n");
#endif
  }

public:
  void resize(std::ptrdiff_t new_size) {
    if (new_size < 0) {
      throw std::invalid_argument("new size < 0");
    }
    if (!data_) {
      throw std::runtime_error("file is closed\n");
    }
    if (!unmap_file()) {
      throw std::runtime_error("failed unmappping file\n");
    }
#if __linux__
    if (ftruncate(handle_, new_size) == -1) {
      throw std::runtime_error("failed resizing mapped file\n");
    }
#elif _WIN32 || _WIN64
    std::int64_t offset = SetFilePointer(handle_, 0, 0, FILE_CURRENT);
    if (offset == INVALID_SET_FILE_POINTER && GetLastError() != NO_ERROR) {
      throw std::runtime_error("failed querying file pointer");
    }
    LONG sizehigh = (new_size >> (sizeof(LONG) * 8));
    LONG sizelow = (new_size & 0xffffffff);
    DWORD result = SetFilePointer(handle_, sizelow, &sizehigh, FILE_BEGIN);
    if ((result == INVALID_SET_FILE_POINTER && GetLastError() != NO_ERROR) ||
        !SetEndOfFile(handle_)) {
      throw std::runtime_error("failed resizing mapped file");
    }
    sizehigh = (offset >> (sizeof(LONG) * 8));
    sizelow = (offset & 0xffffffff);
    SetFilePointer(handle_, sizelow, &sizehigh, FILE_BEGIN);
#else
    static_assert(false, "Unsupported OS\n");
#endif
    size_ = static_cast<std::size_t>(new_size);
    map_file();
  }

  [[nodiscard]] std::size_t size() const noexcept { return size_; }

  [[nodiscard]] void *data() noexcept { return data_; }

  [[nodiscard]] const void *data() const noexcept { return data_; }

  friend bool operator==(const MemoryMappedFile &mmfile1,
                         const MemoryMappedFile &mmfile2) {
    auto res =
        (mmfile1.path_ == mmfile2.path_ && mmfile1.data_ == mmfile2.data_ &&
         mmfile1.size_ == mmfile2.size_ && mmfile1.handle_ == mmfile2.handle_ &&
         mmfile1.flags_ == mmfile2.flags_);
#if _WIN32 || _WIN64
    res = res && (mmfile1.mapped_handle_ == mmfile2.mapped_handle_);
#endif // Windows
    return res;
  }

  friend bool operator!=(const MemoryMappedFile &mmfile1,
                         const MemoryMappedFile &mmfile2) {
    return !(mmfile1 == mmfile2);
  }
};

} // namespace frozenca

Changes in AllocManager.h (from (C++ imitation of glibc malloc(), free()))

  // ... all other code is the same ...

// store *all* chunks
  std::pmr::vector<unsigned char> all_chunks_;

public:
  AllocManagerDefault(std::size_t init_pool_size, std::pmr::memory_resource *mem_res =
                                                 std::pmr::get_default_resource())
      : curr_pool_size_{init_pool_size}, fast_bins_(num_fast_bins_, nullptr),
        small_bins_(num_small_bins_, nullptr),
        all_chunks_(init_pool_size,
                    std::pmr::polymorphic_allocator<unsigned char>(mem_res)) {
    assert(init_pool_size % chunk_alignment_ == 0);
    top_chunk_ = first_chunk();
    set_size(top_chunk_, init_pool_size);
  }

  // ... all other code is the same ...

Changes in test code:


int main() {

  namespace fc = frozenca;
  fc::FileArenaResource arena_res("database.bin");

  // two gigabytes
  // I've tried 1ULL << 34ULL (16GB), but my machine freezed... let's not overdo
  fc::AllocManagerDefault simulator(1UL << 31UL, &arena_res);

  // ... all other test code is the same ...
}

I saw that the memory resource successfully makes an 2GB file database.bin, now I will tweak my B-Tree (C++ : B-Tree in C++20 (+Iterator support)) using this memory resource.

\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

Portability

Your code only works on Linux and Windows, because those are the two operating systems you check for. But mmap() is a POSIX function, so in principle any POSIX-compliant operating system (including BSDs and macOS) will support it. See also how to determine if the operating system is POSIX in C.

Available disk space might be smaller than RAM

While a typical system has more disk space than RAM, this is not always the case. And even if the attached disks are large, not all space might be available to your program due to the disks already being full, or limits being placed on how much a given user is allowed to use.

Note that instead of mapping a file, you can also create an anonymous map. This is basically what malloc() and new nowadays do under the hood to get chunks of memory from the system. Windows has an equivalent. You can use this as a fallback in case you cannot create a large enough file, or do it the other way around: first try an anonymous map, if it doesn't work, fall back to a file.

Beware of memory overcommitment

It is possible to allocate more memory than you can actually use, or even more disk space than you can actually use. This is because often, memory is overcommitted in some way or another.

There might be ways to ensure memory is physically backed before using it. For RAM, you can do this with mlock(). For disk space, you can use posix_fallocate(). However, these calls can be inefficient, and they immediately cause less memory to be available to other users, even if that memory will not actually be used by the application requesting it.

Bad use of a polymorphic memory resource

I do not see the point of making FileArenaResource a polymorphic memory resource, nor using PMR for all_chunks_: there is nothing polymorphic about all_chunks_, it's just a single array of bytes, nothing more. You can only allocate something once from FileArenaResource.

all_chunks_ is a one-off thing, so I wouldn't try to force it to deallocate itself using RAII. But if you do want that, consider using a std::unique_ptr<unsigned char[], Deleter>, where Deleter is taking care of deallocating the mapped file.

\$\endgroup\$
1
  • \$\begingroup\$ You're right, I realized that I don't need FileArenaResource at all. I removed that, and changed all_chunks_ to just a single unique_ptr<unsigned char[], Deleter> so that it is allocated from MemoryMappedFile, allocator<unsigned char> or whatever depending on user choice, but not polymorphic. Thanks! \$\endgroup\$
    – frozenca
    Commented Jul 19, 2022 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.