MMappedUUIDHashTable.cpp

Go to the documentation of this file.

/**
 * @file MMappedUUIDHashTable.cpp
 * @brief Open-addressing hash table over a memory-mapped file: implementation.
 *
 * Implements all methods of @c MMappedUUIDHashTable declared in
 * @c MMappedUUIDHashTable.h:
 * - @c MMappedUUIDHashTable(): open/create the backing file and map it.
 * - @c ~MMappedUUIDHashTable(): sync and unmap.
 * - @c add(): insert a UUID and assign the next sequential integer.
 * - @c operator[](): look up an integer by UUID.
 * - @c sync(): flush dirty pages with @c msync().
 *
 * Internal helpers:
 * - @c mmap(): map (or remap) @p length bytes of the backing file.
 * - @c grow(): double the table size and rehash.
 * - @c find(): locate the slot index for a UUID (or @c NOTHING if absent).
 * - @c set(): write a key-value pair into the table.
 */
#include "MMappedUUIDHashTable.h"
 
#include <cassert>
#include <cerrno>
#include <cstdint>
#include <cstring>
#include <new>
#include <stdexcept>
#include <string>
#include <vector>
 
#include <fcntl.h>
#include <unistd.h>
 
#include <sys/mman.h>
 
MMappedUUIDHashTable::MMappedUUIDHashTable(const char *filename, bool read_only, uint64_t magic_value)
{
  fd=open(filename, O_CREAT|(read_only?O_RDONLY:O_RDWR), 0600); // flawfinder: ignore
  if(fd==-1)
    throw std::runtime_error(strerror(errno));
 
  auto size = lseek(fd, 0, SEEK_END);
  lseek(fd, 0, SEEK_SET);
 
  bool empty=false;
 
  if(size==0) {
    empty=true;
    size=table_t::sizeForLogSize(STARTING_LOG_SIZE);
    if(ftruncate(fd, size))
      throw std::runtime_error(strerror(errno));
  }
 
  mmap(size, read_only);
 
  if(empty) {
    table->magic     = magic_value;
    table->version   = 1;
    table->elem_size = static_cast<uint16_t>(sizeof(value_t));
    table->_reserved = 0;
    table->log_size = table_t::logSizeForSize(size);
    table->nb_elements = 0;
    table->next_value = 0;
    for(unsigned long i=0; i<table->capacity(); ++i) {
      table->t[i].value = NOTHING;
    }
  } else {
    if(table->magic != magic_value)
      throw std::runtime_error("ProvSQL mmap: wrong file type (magic mismatch)");
    if(table->version != 1)
      throw std::runtime_error("ProvSQL mmap: unsupported format version "
                               + std::to_string(table->version));
    if(table->elem_size != sizeof(value_t))
      throw std::runtime_error("ProvSQL mmap: element size mismatch (recompile required)");
  }
}
 
void MMappedUUIDHashTable::mmap(size_t length, bool read_only)
{
  table = reinterpret_cast<table_t *>(::mmap(
                                        NULL,
                                        length,
                                        PROT_READ|(read_only?0:PROT_WRITE),
                                        MAP_SHARED,
                                        fd,
                                        0));
  if(table == MAP_FAILED)
    throw std::runtime_error(strerror(errno));
}
 
void MMappedUUIDHashTable::grow()
{
  sync();
 
  std::vector<value_t> elements;
  elements.reserve(table->nb_elements);
  for(unsigned long i=0; i<table->capacity(); ++i)
    if(table->t[i].value != NOTHING)
      elements.push_back(table->t[i]);
 
  auto new_log_size = table->log_size+1;
  munmap(table, table_t::sizeForLogSize(table->log_size));
 
  auto new_size = table_t::sizeForLogSize(new_log_size);
  if(ftruncate(fd, new_size))
    throw std::runtime_error(strerror(errno));
  mmap(new_size, false);
 
  table->log_size = new_log_size;
  for(unsigned long i=0; i<table->capacity(); ++i) {
    table->t[i].value = NOTHING;
  }
  for(const auto &u: elements)
    set(u.uuid, u.value);
}
 
MMappedUUIDHashTable::~MMappedUUIDHashTable()
{
  munmap(table, table_t::sizeForLogSize(table->log_size));
  close(fd);
}
 
unsigned long MMappedUUIDHashTable::find(pg_uuid_t u) const
{
  auto k = hash(u);
  while(table->t[k].value != NOTHING &&
        std::memcmp(&table->t[k].uuid, &u, sizeof(pg_uuid_t))) {
    k = (k+1) % table->capacity();
  }
 
  return k;
}
 
unsigned long MMappedUUIDHashTable::operator[](pg_uuid_t u) const
{
  auto k = find(u);
 
  return table->t[k].value;
}
 
std::pair<unsigned long,bool> MMappedUUIDHashTable::add(pg_uuid_t u)
{
  auto k = find(u);
 
  if(table->t[k].value == NOTHING) {
    if(table->nb_elements >= MAXIMUM_LOAD_FACTOR * table->capacity()) {
      grow();
    }
    k = find(u);
    ++table->nb_elements;
    table->t[k].uuid = u;
    return std::make_pair(table->t[k].value = table->next_value++, true);
  } else
    return std::make_pair(table->t[k].value, false);
}
 
// Only used when growing the table, so no need to check/update nb_elements
void MMappedUUIDHashTable::set(pg_uuid_t u, unsigned long i)
{
  table->t[find(u)] = {u, i};
}
 
void MMappedUUIDHashTable::sync()
{
  msync(table, table_t::sizeForLogSize(table->log_size), MS_SYNC);
}