add leveldb

11 files changed, 1059 insertions, 0 deletions

diff --git a/src/database/CMakeLists.txt b/src/database/CMakeLists.txt
new file mode 100644
index 00000000..f66578cb
--- /dev/null
+++ b/src/database/CMakeLists.txt
@@ -0,0 +1,16 @@
+idf_component_register(
+  SRCS "table.cpp" "env_esp.cpp" "database.cpp"
+  INCLUDE_DIRS "include"
+  REQUIRES "result" "span" "esp_psram" "fatfs")
+
+target_compile_options(${COMPONENT_LIB} PRIVATE ${EXTRA_WARNINGS})
+
+set(LEVELDB_BUILD_TESTS OFF)
+set(LEVELDB_BUILD_BENCHMARKS OFF)
+set(LEVELDB_INSTALL OFF)
+
+set(CMAKE_POLICY_DEFAULT_CMP0077 NEW)
+
+add_subdirectory($ENV{PROJ_PATH}/lib/leveldb ${CMAKE_CURRENT_BINARY_DIR}/leveldb)
+
+target_link_libraries(${COMPONENT_LIB} PUBLIC leveldb)
diff --git a/src/database/database.cpp b/src/database/database.cpp
new file mode 100644
index 00000000..7cfd0581
--- /dev/null
+++ b/src/database/database.cpp
@@ -0,0 +1,38 @@
+#include "database.hpp"
+
+#include "esp_log.h"
+#include "leveldb/cache.h"
+
+#include "env_esp.hpp"
+
+namespace database {
+
+static SingletonEnv<leveldb::EspEnv> sEnv;
+
+auto Database::Open() -> cpp::result<Database*, DatabaseError> {
+  leveldb::DB* db;
+  leveldb::Cache* cache = leveldb::NewLRUCache(24 * 1024);
+  leveldb::Options options;
+  options.env = sEnv.env();
+  options.create_if_missing = true;
+  options.write_buffer_size = 48 * 1024;
+  options.max_file_size = 32;
+  options.block_cache = cache;
+  options.block_size = 512;
+
+  auto status = leveldb::DB::Open(options, "/.db", &db);
+  if (!status.ok()) {
+    delete cache;
+    ESP_LOGE("DB", "failed to open db");
+    return cpp::fail(FAILED_TO_OPEN);
+  }
+
+  return new Database(db, cache);
+}
+
+Database::Database(leveldb::DB* db, leveldb::Cache* cache)
+    : db_(db), cache_(cache) {}
+
+Database::~Database() {}
+
+}  // namespace database
diff --git a/src/database/env_esp.cpp b/src/database/env_esp.cpp
new file mode 100644
index 00000000..e525900d
--- /dev/null
+++ b/src/database/env_esp.cpp
@@ -0,0 +1,483 @@
+#include "env_esp.hpp"
+
+#include <atomic>
+#include <cerrno>
+#include <cstddef>
+#include <cstdint>
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+#include <limits>
+#include <mutex>
+#include <queue>
+#include <set>
+#include <string>
+#include <thread>
+#include <type_traits>
+#include <utility>
+
+#include "esp_heap_caps.h"
+#include "esp_log.h"
+#include "ff.h"
+#include "freertos/FreeRTOS.h"
+#include "freertos/portmacro.h"
+#include "freertos/projdefs.h"
+#include "freertos/queue.h"
+#include "freertos/task.h"
+#include "leveldb/env.h"
+#include "leveldb/slice.h"
+#include "leveldb/status.h"
+
+namespace leveldb {
+
+std::string ErrToStr(FRESULT err) {
+  switch (err) {
+    case FR_OK:
+      return "FR_OK";
+    case FR_DISK_ERR:
+      return "FR_DISK_ERR";
+    case FR_INT_ERR:
+      return "FR_INT_ERR";
+    case FR_NOT_READY:
+      return "FR_NOT_READY";
+    case FR_NO_FILE:
+      return "FR_NO_FILE";
+    case FR_NO_PATH:
+      return "FR_NO_PATH";
+    case FR_INVALID_NAME:
+      return "FR_INVALID_NAME";
+    case FR_DENIED:
+      return "FR_DENIED";
+    case FR_EXIST:
+      return "FR_EXIST";
+    case FR_INVALID_OBJECT:
+      return "FR_INVALID_OBJECT";
+    case FR_WRITE_PROTECTED:
+      return "FR_WRITE_PROTECTED";
+    case FR_INVALID_DRIVE:
+      return "FR_INVALID_DRIVE";
+    case FR_NOT_ENABLED:
+      return "FR_NOT_ENABLED";
+    case FR_NO_FILESYSTEM:
+      return "FR_NO_FILESYSTEM";
+    case FR_MKFS_ABORTED:
+      return "FR_MKFS_ABORTED";
+    case FR_TIMEOUT:
+      return "FR_TIMEOUT";
+    case FR_LOCKED:
+      return "FR_LOCKED";
+    case FR_NOT_ENOUGH_CORE:
+      return "FR_NOT_ENOUGH_CORE";
+    case FR_TOO_MANY_OPEN_FILES:
+      return "FR_TOO_MANY_OPEN_FILES";
+    case FR_INVALID_PARAMETER:
+      return "FR_INVALID_PARAMETER";
+    default:
+      return "UNKNOWN";
+  }
+}
+
+Status EspError(const std::string& context, FRESULT err) {
+  if (err == FR_NO_FILE) {
+    return Status::NotFound(context, ErrToStr(err));
+  } else {
+    return Status::IOError(context, ErrToStr(err));
+  }
+}
+
+class EspSequentialFile final : public SequentialFile {
+ public:
+  EspSequentialFile(const std::string& filename, FIL file)
+      : file_(file), filename_(filename) {}
+  ~EspSequentialFile() override { f_close(&file_); }
+
+  Status Read(size_t n, Slice* result, char* scratch) override {
+    UINT read_size = 0;
+    FRESULT res = f_read(&file_, scratch, n, &read_size);
+    if (res != FR_OK) {  // Read error.
+      return EspError(filename_, res);
+    }
+    *result = Slice(scratch, read_size);
+    return Status::OK();
+  }
+
+  Status Skip(uint64_t n) override {
+    DWORD current_pos = f_tell(&file_);
+    FRESULT res = f_lseek(&file_, current_pos + n);
+    if (res != FR_OK) {
+      return EspError(filename_, res);
+    }
+    return Status::OK();
+  }
+
+ private:
+  FIL file_;
+  const std::string filename_;
+};
+
+// Implements random read access in a file using pread().
+//
+// Instances of this class are thread-safe, as required by the RandomAccessFile
+// API. Instances are immutable and Read() only calls thread-safe library
+// functions.
+class EspRandomAccessFile final : public RandomAccessFile {
+ public:
+  // The new instance takes ownership of |fd|. |fd_limiter| must outlive this
+  // instance, and will be used to determine if .
+  explicit EspRandomAccessFile(const std::string& filename)
+      : filename_(std::move(filename)) {}
+
+  ~EspRandomAccessFile() override {}
+
+  Status Read(uint64_t offset,
+              size_t n,
+              Slice* result,
+              char* scratch) const override {
+    FIL file;
+    FRESULT res = f_open(&file, filename_.c_str(), FA_READ);
+    if (res != FR_OK) {
+      return EspError(filename_, res);
+    }
+
+    res = f_lseek(&file, offset);
+    if (res != FR_OK) {
+      return EspError(filename_, res);
+    }
+
+    Status status;
+    UINT read_size = 0;
+    res = f_read(&file, scratch, n, &read_size);
+    if (res != FR_OK || read_size == 0) {
+      return EspError(filename_, res);
+    }
+    *result = Slice(scratch, read_size);
+
+    f_close(&file);
+
+    return status;
+  }
+
+ private:
+  const std::string filename_;
+};
+
+// TODO(jacqueline): LevelDB expects writes to this class to be buffered in
+// memory. FatFs already does in-memory buffering, but we should think about
+// whether to layer more on top.
+class EspWritableFile final : public WritableFile {
+ public:
+  EspWritableFile(std::string filename, FIL file)
+      : filename_(std::move(filename)), file_(file), is_open_(true) {}
+
+  ~EspWritableFile() override {
+    if (is_open_) {
+      // Ignoring any potential errors
+      Close();
+    }
+  }
+
+  Status Append(const Slice& data) override {
+    if (!is_open_) {
+      return EspError(filename_, FR_NOT_ENABLED);
+    }
+
+    size_t write_size = data.size();
+    const char* write_data = data.data();
+
+    UINT bytes_written = 0;
+    FRESULT res = f_write(&file_, write_data, write_size, &bytes_written);
+    if (res != FR_OK) {
+      return EspError(filename_, res);
+    }
+
+    return Status::OK();
+  }
+
+  Status Close() override {
+    is_open_ = false;
+    FRESULT res = f_close(&file_);
+    if (res != FR_OK) {
+      return EspError(filename_, res);
+    }
+    return Status::OK();
+  }
+
+  Status Flush() override { return Sync(); }
+
+  Status Sync() override {
+    if (!is_open_) {
+      return EspError(filename_, FR_NOT_ENABLED);
+    }
+    FRESULT res = f_sync(&file_);
+    if (res != FR_OK) {
+      return EspError(filename_, res);
+    }
+    return Status::OK();
+  }
+
+ private:
+  const std::string filename_;
+  FIL file_;
+  bool is_open_;
+};
+
+class EspFileLock : public FileLock {
+ public:
+  explicit EspFileLock(const std::string& filename) : filename_(filename) {}
+  const std::string& filename() { return filename_; }
+
+ private:
+  const std::string filename_;
+};
+
+
+class EspLogger final : public Logger {
+ public:
+  explicit EspLogger(FIL file) : file_(file) {}
+  ~EspLogger() override { f_close(&file_); }
+
+  void Logv(const char* format, std::va_list ap) override {
+    std::va_list args_copy;
+    va_copy(args_copy, ap);
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wformat-nonliteral"
+    std::size_t bytes_needed = snprintf(NULL, 0, format, args_copy);
+    char* output = reinterpret_cast<char*>(
+        heap_caps_calloc(bytes_needed, 1, MALLOC_CAP_SPIRAM));
+    snprintf(output, bytes_needed, format, args_copy);
+#pragma GCC diagnostic pop
+    va_end(args_copy);
+    ESP_LOGV("LEVELDB", "%s", output);
+    //f_puts(output, &file_);
+    free(reinterpret_cast<void*>(output));
+  }
+
+ private:
+  FIL file_;
+};
+
+  EspEnv::~EspEnv() {
+    ESP_LOGE("LEVELDB", "EspEnv singleton destroyed. Unsupported behavior!");
+  }
+
+  Status EspEnv::NewSequentialFile(const std::string& filename,
+                           SequentialFile** result) {
+    FIL file;
+    FRESULT res = f_open(&file, filename.c_str(), FA_READ);
+    if (res != FR_OK) {
+      *result = nullptr;
+      return EspError(filename, res);
+    }
+
+    *result = new EspSequentialFile(filename, file);
+    return Status::OK();
+  }
+
+  Status EspEnv::NewRandomAccessFile(const std::string& filename,
+                             RandomAccessFile** result) {
+    // EspRandomAccessFile doesn't try to open the file until it's needed, so
+    // we need to first ensure the file exists to handle the NotFound case
+    // correctly.
+    FILINFO info;
+    FRESULT res = f_stat(filename.c_str(), &info);
+    if (res != FR_OK) {
+      *result = nullptr;
+      return EspError(filename, res);
+    }
+
+    *result = new EspRandomAccessFile(filename);
+    return Status::OK();
+  }
+
+  Status EspEnv::NewWritableFile(const std::string& filename,
+                         WritableFile** result) {
+    FIL file;
+    FRESULT res = f_open(&file, filename.c_str(), FA_WRITE | FA_CREATE_ALWAYS);
+    if (res != FR_OK) {
+      *result = nullptr;
+      return EspError(filename, res);
+    }
+
+    *result = new EspWritableFile(filename, file);
+    return Status::OK();
+  }
+
+  Status EspEnv::NewAppendableFile(const std::string& filename,
+                           WritableFile** result) {
+    FIL file;
+    FRESULT res = f_open(&file, filename.c_str(), FA_WRITE | FA_OPEN_APPEND);
+    if (res != FR_OK) {
+      *result = nullptr;
+      return EspError(filename, res);
+    }
+
+    *result = new EspWritableFile(filename, file);
+    return Status::OK();
+  }
+
+  bool EspEnv::FileExists(const std::string& filename) {
+    FILINFO info;
+    return f_stat(filename.c_str(), &info) == FR_OK;
+  }
+
+  Status EspEnv::GetChildren(const std::string& directory_path,
+                     std::vector<std::string>* result) {
+    result->clear();
+
+    FF_DIR dir;
+    FRESULT res = f_opendir(&dir, directory_path.c_str());
+    if (res != FR_OK) {
+      return EspError(directory_path, res);
+    }
+
+    FILINFO info;
+    for (;;) {
+      res = f_readdir(&dir, &info);
+      if (res != FR_OK) {
+        return EspError(directory_path, res);
+      }
+      if (info.fname[0] == 0) {
+        break;
+      }
+      result->emplace_back(info.fname);
+    }
+
+    res = f_closedir(&dir);
+    if (res != FR_OK) {
+      return EspError(directory_path, res);
+    }
+
+    return Status::OK();
+  }
+
+  Status EspEnv::RemoveFile(const std::string& filename) {
+    FRESULT res = f_unlink(filename.c_str());
+    if (res != FR_OK) {
+      return EspError(filename, res);
+    }
+    return Status::OK();
+  }
+
+  Status EspEnv::CreateDir(const std::string& dirname) {
+    FRESULT res = f_mkdir(dirname.c_str());
+    if (res != FR_OK) {
+      return EspError(dirname, res);
+    }
+    return Status::OK();
+  }
+
+  Status EspEnv::RemoveDir(const std::string& dirname) {
+    return RemoveFile(dirname);
+  }
+
+  Status EspEnv::GetFileSize(const std::string& filename, uint64_t* size) {
+    FILINFO info;
+    FRESULT res = f_stat(filename.c_str(), &info);
+    if (res != FR_OK) {
+      *size = 0;
+      return EspError(filename, res);
+    }
+    *size = info.fsize;
+    return Status::OK();
+  }
+
+  Status EspEnv::RenameFile(const std::string& from, const std::string& to) {
+    FRESULT res = f_rename(from.c_str(), to.c_str());
+    if (res != FR_OK) {
+      return EspError(from, res);
+    }
+    return Status::OK();
+  }
+
+  Status EspEnv::LockFile(const std::string& filename, FileLock** lock) {
+    *lock = nullptr;
+
+    if (!locks_.Insert(filename)) {
+      return Status::IOError("lock " + filename, "already held by process");
+    }
+
+    *lock = new EspFileLock(filename);
+    return Status::OK();
+  }
+
+  Status EspEnv::UnlockFile(FileLock* lock) {
+    EspFileLock* posix_file_lock = static_cast<EspFileLock*>(lock);
+    locks_.Remove(posix_file_lock->filename());
+    delete posix_file_lock;
+    return Status::OK();
+  }
+
+  void EspEnv::StartThread(void (*thread_main)(void* thread_main_arg),
+                   void* thread_main_arg) {
+    std::thread new_thread(thread_main, thread_main_arg);
+    new_thread.detach();
+  }
+
+  Status EspEnv::GetTestDirectory(std::string* result) {
+    CreateDir("/tmp");
+    *result = "/tmp";
+    return Status::OK();
+  }
+
+  Status EspEnv::NewLogger(const std::string& filename, Logger** result) {
+    FIL file;
+    FRESULT res = f_open(&file, filename.c_str(), FA_WRITE | FA_OPEN_APPEND);
+    if (res != FR_OK) {
+      *result = nullptr;
+      return EspError(filename, res);
+    }
+
+    *result = new EspLogger(file);
+    return Status::OK();
+  }
+
+  uint64_t EspEnv::NowMicros() {
+    struct timeval tv_now;
+    gettimeofday(&tv_now, NULL);
+    return (int64_t)tv_now.tv_sec * 1000000L + (int64_t)tv_now.tv_usec;
+  }
+
+  void EspEnv::SleepForMicroseconds(int micros) {
+    vTaskDelay(pdMS_TO_TICKS(micros / 1000));
+  }
+
+extern "C" void BackgroundThreadEntryPoint(EspEnv* env) {
+  env->BackgroundThreadMain();
+}
+
+EspEnv::EspEnv()
+    : background_work_mutex_(),
+      started_background_thread_(false),
+      background_work_queue_(xQueueCreate(4, sizeof(BackgroundWorkItem))) {}
+
+void EspEnv::Schedule(
+    void (*background_work_function)(void* background_work_arg),
+    void* background_work_arg) {
+  background_work_mutex_.lock();
+
+  // Start the background thread, if we haven't done so already.
+  if (!started_background_thread_) {
+    started_background_thread_ = true;
+    xTaskCreate(reinterpret_cast<TaskFunction_t>(BackgroundThreadEntryPoint),
+                "LVL_ONEOFF", 2048, reinterpret_cast<void*>(this), 3, NULL);
+  }
+
+  BackgroundWorkItem item(background_work_function, background_work_arg);
+  xQueueSend(background_work_queue_, &item, portMAX_DELAY);
+
+  background_work_mutex_.unlock();
+}
+
+void EspEnv::BackgroundThreadMain() {
+  while (true) {
+    uint8_t buf[sizeof(BackgroundWorkItem)];
+    if (xQueueReceive(background_work_queue_, &buf, portMAX_DELAY)) {
+      BackgroundWorkItem* item = reinterpret_cast<BackgroundWorkItem*>(buf);
+      auto background_work_function = item->function;
+      void* background_work_arg = item->arg;
+      background_work_function(background_work_arg);
+    }
+  }
+}
+
+}  // namespace leveldb
diff --git a/src/database/include/database.hpp b/src/database/include/database.hpp
new file mode 100644
index 00000000..cfef0a7d
--- /dev/null
+++ b/src/database/include/database.hpp
@@ -0,0 +1,27 @@
+#pragma once
+
+#include <memory>
+
+#include "leveldb/cache.h"
+#include "leveldb/db.h"
+#include "result.hpp"
+
+namespace database {
+
+class Database {
+ public:
+  enum DatabaseError {
+    FAILED_TO_OPEN,
+  };
+  static auto Open() -> cpp::result<Database*, DatabaseError>;
+
+  ~Database();
+
+ private:
+  std::unique_ptr<leveldb::DB> db_;
+  std::unique_ptr<leveldb::Cache> cache_;
+
+  Database(leveldb::DB* db, leveldb::Cache* cache);
+};
+
+}  // namespace database
diff --git a/src/database/include/env_esp.hpp b/src/database/include/env_esp.hpp
new file mode 100644
index 00000000..c9b3fbc8
--- /dev/null
+++ b/src/database/include/env_esp.hpp
@@ -0,0 +1,152 @@
+#pragma once
+
+#include <mutex>
+#include <set>
+
+#include "freertos/FreeRTOS.h"
+#include "freertos/queue.h"
+#include "leveldb/env.h"
+#include "leveldb/status.h"
+
+namespace leveldb {
+
+// Tracks the files locked by EspEnv::LockFile().
+//
+// We maintain a separate set instead of relying on fcntl(F_SETLK) because
+// fcntl(F_SETLK) does not provide any protection against multiple uses from the
+// same process.
+//
+// Instances are thread-safe because all member data is guarded by a mutex.
+class InMemoryLockTable {
+ public:
+  bool Insert(const std::string& fname) {
+    mu_.lock();
+    bool succeeded = locked_files_.insert(fname).second;
+    mu_.unlock();
+    return succeeded;
+  }
+  void Remove(const std::string& fname) {
+    mu_.lock();
+    locked_files_.erase(fname);
+    mu_.unlock();
+  }
+
+ private:
+  std::mutex mu_;
+  std::set<std::string> locked_files_;
+};
+
+class EspEnv : public leveldb::Env {
+ public:
+  EspEnv();
+  ~EspEnv() override;
+
+  Status NewSequentialFile(const std::string& filename,
+                           SequentialFile** result) override;
+
+  Status NewRandomAccessFile(const std::string& filename,
+                             RandomAccessFile** result) override;
+
+  Status NewWritableFile(const std::string& filename,
+                         WritableFile** result) override;
+
+  Status NewAppendableFile(const std::string& filename,
+                           WritableFile** result) override;
+
+  bool FileExists(const std::string& filename) override;
+
+  Status GetChildren(const std::string& directory_path,
+                     std::vector<std::string>* result) override;
+
+  Status RemoveFile(const std::string& filename) override;
+
+  Status CreateDir(const std::string& dirname) override;
+
+  Status RemoveDir(const std::string& dirname) override;
+
+  Status GetFileSize(const std::string& filename, uint64_t* size) override;
+
+  Status RenameFile(const std::string& from, const std::string& to) override;
+
+  Status LockFile(const std::string& filename, FileLock** lock) override;
+
+  Status UnlockFile(FileLock* lock) override;
+
+  void Schedule(void (*background_work_function)(void* background_work_arg),
+                void* background_work_arg) override;
+
+  void StartThread(void (*thread_main)(void* thread_main_arg),
+                   void* thread_main_arg) override;
+
+  Status GetTestDirectory(std::string* result) override;
+
+  Status NewLogger(const std::string& filename, Logger** result) override;
+
+  uint64_t NowMicros() override;
+
+  void SleepForMicroseconds(int micros) override;
+
+  void BackgroundThreadMain();
+
+ private:
+  // Stores the work item data in a Schedule() call.
+  //
+  // Instances are constructed on the thread calling Schedule() and used on the
+  // background thread.
+  //
+  // This structure is thread-safe beacuse it is immutable.
+  struct BackgroundWorkItem {
+    explicit BackgroundWorkItem(void (*f)(void*), void* a)
+        : function(f), arg(a) {}
+
+    void (*const function)(void*);
+    void* const arg;
+  };
+
+  std::mutex background_work_mutex_;
+  bool started_background_thread_;
+
+  QueueHandle_t background_work_queue_;
+
+  InMemoryLockTable locks_;  // Thread-safe.
+};
+
+} // namespace leveldb
+
+namespace database {
+
+// Wraps an Env instance whose destructor is never created.
+//
+// Intended usage:
+//   using PlatformSingletonEnv = SingletonEnv<PlatformEnv>;
+//   void ConfigurePosixEnv(int param) {
+//     PlatformSingletonEnv::AssertEnvNotInitialized();
+//     // set global configuration flags.
+//   }
+//   Env* Env::Default() {
+//     static PlatformSingletonEnv default_env;
+//     return default_env.env();
+//   }
+template <typename EnvType>
+class SingletonEnv {
+ public:
+  SingletonEnv() {
+    static_assert(sizeof(env_storage_) >= sizeof(EnvType),
+                  "env_storage_ will not fit the Env");
+    static_assert(alignof(decltype(env_storage_)) >= alignof(EnvType),
+                  "env_storage_ does not meet the Env's alignment needs");
+    new (&env_storage_) EnvType();
+  }
+  ~SingletonEnv() = default;
+
+  SingletonEnv(const SingletonEnv&) = delete;
+  SingletonEnv& operator=(const SingletonEnv&) = delete;
+
+  leveldb::Env* env() { return reinterpret_cast<leveldb::Env*>(&env_storage_); }
+
+ private:
+  typename std::aligned_storage<sizeof(EnvType), alignof(EnvType)>::type
+      env_storage_;
+};
+
+} // namespace database
diff --git a/src/database/include/file_gatherer.hpp b/src/database/include/file_gatherer.hpp
new file mode 100644
index 00000000..47d40f88
--- /dev/null
+++ b/src/database/include/file_gatherer.hpp
@@ -0,0 +1,58 @@
+#pragma once
+
+#include <deque>
+#include <functional>
+#include <sstream>
+#include <string>
+
+#include "ff.h"
+
+namespace database {
+
+static_assert(sizeof(TCHAR) == sizeof(char), "TCHAR must be CHAR");
+
+template <typename Callback>
+auto FindFiles(FATFS* fs, const std::string& root, Callback cb) -> void {
+  std::deque<std::string> to_explore;
+  to_explore.push_back(root);
+
+  while (!to_explore.empty()) {
+    std::string next_path_str = to_explore.front();
+    const TCHAR* next_path = static_cast<const TCHAR*>(next_path_str.c_str());
+
+    DIR dir;
+    FRESULT res = f_opendir(&dir, next_path);
+    if (res != FR_OK) {
+      // TODO: log.
+      continue;
+    }
+
+    for (;;) {
+      FILINFO info;
+      res = f_readdir(&dir, &info);
+      if (info.fname == NULL) {
+        // No more files in the directory.
+        break;
+      } else if (info.fattrib & (AM_HID | AM_SYS)) {
+        // System or hidden file. Ignore it and move on.
+        continue;
+      } else {
+        std::stringstream full_path;
+        full_path << next_path_str << "/" << info.fname;
+
+        if (info.fattrib & AM_DIR) {
+          // This is a directory. Add it to the explore queue.
+          to_explore.push_back(full_path.str());
+        } else {
+          // This is a file! Let the callback know about it.
+          std::invoke(cb, full_path.str(), info);
+        }
+      }
+    }
+
+    f_closedir(&dir);
+    to_explore.pop_front();
+  }
+}
+
+}  // namespace database
diff --git a/src/database/include/table.hpp b/src/database/include/table.hpp
new file mode 100644
index 00000000..438c23b6
--- /dev/null
+++ b/src/database/include/table.hpp
@@ -0,0 +1,87 @@
+#pragma once
+
+#include <cstddef>
+#include <cstdint>
+#include <memory>
+#include <optional>
+#include <string>
+#include <utility>
+
+#include "esp32/himem.h"
+#include "ff.h"
+#include "span.hpp"
+#include "sys/_stdint.h"
+
+namespace database {
+
+// Types used for indexing into files on disk. These should, at minimum, match
+// the size of the types that the underlying filesystem uses to address within
+// files. FAT32 uses 32 bit address. If we drop this and just support exFAT, we
+// can change these to 64 bit types.
+typedef uint32_t Index_t;
+typedef Index_t IndexOffset_t;
+
+// The amount of memory that will be used to page database columns in from disk.
+// Currently we only use a single 'page' in PSRAM per column, but with some
+// refactoring we could easily page more.
+// Keep this value 32KiB-aligned for himem compatibility.
+extern const std::size_t kRamBlockSize;
+
+struct DatabaseHeader {
+  uint32_t magic_number;
+  uint16_t db_version;
+  Index_t num_indices;
+};
+
+struct DatabaseEntry {
+  uint8_t type;
+  std::string path;
+
+  std::string title;
+  std::string album;
+  std::string artist;
+  std::string album_artist;
+};
+
+struct IndexEntry {
+  uint8_t type;
+  IndexOffset_t path;
+
+  IndexOffset_t title;
+  IndexOffset_t album;
+  IndexOffset_t artist;
+  IndexOffset_t album_artist;
+};
+
+struct RowData {
+  std::unique_ptr<std::byte[]> arr;
+  std::size_t length;
+};
+
+// Representation of a single column of data. Each column is simply a tightly
+// packed list of [size, [bytes, ...]] pairs. Callers are responsible for
+// parsing and encoding the actual bytes themselves.
+class Column {
+ public:
+  static auto Open(std::string) -> std::optional<Column>;
+
+  Column(FIL file, std::size_t file_size);
+  ~Column();
+
+  auto ReadDataAtOffset(esp_himem_rangehandle_t, IndexOffset_t) -> RowData;
+  auto AppendRow(cpp::span<std::byte> row) -> bool;
+  auto FlushChanges() -> void;
+
+ private:
+  FIL file_;
+  IndexOffset_t length_;
+
+  esp_himem_handle_t block_;
+  std::pair<IndexOffset_t, IndexOffset_t> loaded_range_;
+
+  auto IsOffsetLoaded(IndexOffset_t offset) -> bool;
+  auto LoadOffsetFromDisk(cpp::span<std::byte> dest, IndexOffset_t offset)
+      -> bool;
+};
+
+}  // namespace database
diff --git a/src/database/include/table_reader.hpp b/src/database/include/table_reader.hpp
new file mode 100644
index 00000000..9f7cc4ee
--- /dev/null
+++ b/src/database/include/table_reader.hpp
@@ -0,0 +1,53 @@
+#pragma once
+
+#include <string>
+
+#include "result.hpp"
+#include "span.hpp"
+
+#include "table.hpp"
+
+namespace database {
+
+class TableReader {
+ public:
+  enum ReadError {
+    OUT_OF_RANGE,
+    IO_ERROR,
+    PARSE_ERROR,
+  };
+
+  auto ReadEntryAtIndex(Index_t index) -> cpp::result<DatabaseEntry, ReadError>;
+
+  template <typename T>
+  auto ReadColumnOffsetAtIndex(Column<T> col, Index_t index)
+      -> cpp::result<IndexOffset_t, ReadError>;
+
+  template <typename T>
+  auto ParseColumnAtIndex(Column<T> col, Index_t index)
+      -> cpp::result<T, ReadError> {
+    return ReadColumnOffsetAtIndex(col, index).map([&](IndexOffset_t offset) {
+      return ReadColumnAtOffset(col, offset);
+    });
+  }
+
+  template <typename T>
+  auto ParseColumnAtOffset(Column<T> col, IndexOffset_t offset)
+      -> cpp::result<T, ReadError> {
+    return ReadDataAtOffset(col.Filename(), offset)
+        .flat_map([&](cpp::span<std::byte> data) {
+          auto res = = col.ParseValue(data);
+          if (res) {
+            return *res;
+          } else {
+            return cpp::fail(PARSE_ERROR);
+          }
+        });
+  }
+
+ private:
+  auto ReadDataAtOffset(std::string filename, IndexOffset_t offset)
+      -> cpp::span<std::byte>;
+};
+
+}  // namespace database
diff --git a/src/database/include/table_writer.hpp b/src/database/include/table_writer.hpp
new file mode 100644
index 00000000..9e01dd9d
--- /dev/null
+++ b/src/database/include/table_writer.hpp
@@ -0,0 +1,5 @@
+#pragma once
+
+#include "table.hpp"
+
+namespace database {}  // namespace database
diff --git a/src/database/include/tag_processor.hpp b/src/database/include/tag_processor.hpp
new file mode 100644
index 00000000..0257fc92
--- /dev/null
+++ b/src/database/include/tag_processor.hpp
@@ -0,0 +1,3 @@
+#pragma once
+
+namespace database {}  // namespace database
diff --git a/src/database/table.cpp b/src/database/table.cpp
new file mode 100644
index 00000000..de425837
--- /dev/null
+++ b/src/database/table.cpp
@@ -0,0 +1,137 @@
+#include "table.hpp"
+
+#include <memory>
+#include <optional>
+
+#include "esp32/himem.h"
+#include "esp_err.h"
+#include "ff.h"
+
+namespace database {
+
+const std::size_t kRamBlockSize = 32 * 1024;
+
+auto Column::Open(std::string path) -> std::optional<Column> {
+  FILINFO info;
+  FRESULT res = f_stat(path.c_str(), &info);
+  if (res != FR_OK) {
+    return {};
+  }
+
+  FIL file;
+  res = f_open(&file, path.c_str(), FA_READ | FA_WRITE);
+  if (res != FR_OK) {
+    return {};
+  }
+
+  return std::make_optional<Column>(file, info.fsize);
+}
+
+Column::Column(FIL file, std::size_t file_size)
+    : file_(file), length_(file_size), loaded_range_(0, 0) {
+  ESP_ERROR_CHECK(esp_himem_alloc(kRamBlockSize, &block_));
+}
+
+Column::~Column() {
+  f_close(&file_);
+  esp_himem_free(block_);
+}
+
+auto Column::ReadDataAtOffset(esp_himem_rangehandle_t range,
+                              IndexOffset_t offset) -> RowData {
+  // To start, we always need to map our address space.
+  std::byte* paged_block;
+  esp_himem_map(block_, range, 0, 0, kRamBlockSize, 0,
+                reinterpret_cast<void**>(&paged_block));
+
+  // Next, we need to see how long the data we're returning is. This might
+  // already exist in memory.
+  if (!IsOffsetLoaded(offset) ||
+      !IsOffsetLoaded(offset + sizeof(std::size_t))) {
+    LoadOffsetFromDisk({paged_block, kRamBlockSize}, offset);
+  }
+
+  IndexOffset_t paged_offset = offset - loaded_range_.first;
+  std::size_t data_size =
+      *(reinterpret_cast<std::size_t*>(paged_block + paged_offset));
+
+  // Now that we have the size, we need to do the same thing again to get the
+  // real data. Hopefully this doesn't require an actual second disk read, since
+  // LoadOffsetFromDisk should load a generous amount after the offset we
+  // previously gave.
+  if (!IsOffsetLoaded(offset) || !IsOffsetLoaded(offset + data_size)) {
+    LoadOffsetFromDisk({paged_block, kRamBlockSize}, offset);
+  }
+
+  paged_offset = offset - loaded_range_.first + sizeof(IndexOffset_t);
+  cpp::span<std::byte> src(paged_block + paged_offset, data_size);
+
+  auto res = std::make_unique<std::byte[]>(data_size);
+  cpp::span<std::byte> dest(res.get(), data_size);
+
+  std::copy(src.begin(), src.end(), dest.begin());
+
+  // Finally, unmap from the range we were given to return it to its initial
+  // state.
+  esp_himem_unmap(range, paged_block, kRamBlockSize);
+
+  return {std::move(res), data_size};
+}
+
+auto Column::AppendRow(cpp::span<std::byte> row) -> bool {
+  FRESULT res = f_lseek(&file_, length_);
+  if (res != FR_OK) {
+    // TODO(jacqueline): Handle errors.
+    return false;
+  }
+
+  std::size_t bytes_written = 0;
+  std::size_t length = row.size_bytes();
+  res = f_write(&file_, &length, sizeof(std::size_t), &bytes_written);
+  if (res != FR_OK || bytes_written != sizeof(std::size_t)) {
+    // TODO(jacqueline): Handle errors.
+    return false;
+  }
+
+  res = f_write(&file_, row.data(), length, &bytes_written);
+  if (res != FR_OK || bytes_written != length) {
+    // TODO(jacqueline): Handle errors.
+    return false;
+  }
+
+  length_ += sizeof(std::size_t) + row.size_bytes();
+
+  return true;
+}
+
+auto Column::FlushChanges() -> void {
+  f_sync(&file_);
+}
+
+auto Column::IsOffsetLoaded(IndexOffset_t offset) -> bool {
+  return loaded_range_.first <= offset &&
+         loaded_range_.second > offset + sizeof(std::size_t);
+}
+
+auto Column::LoadOffsetFromDisk(cpp::span<std::byte> dest, IndexOffset_t offset)
+    -> bool {
+  FRESULT res = f_lseek(&file_, offset);
+  if (res != FR_OK) {
+    // TODO(jacqueline): Handle errors.
+    return false;
+  }
+
+  UINT bytes_read = 0;
+  res = f_read(&file_, dest.data(), dest.size(), &bytes_read);
+  if (res != FR_OK) {
+    // TODO(jacqueline): Handle errors.
+    return false;
+  }
+
+  loaded_range_.first = offset;
+  loaded_range_.second = offset + bytes_read;
+
+  return true;
+}
+
+}  // namespace database