LibSQL: Redesign heap storage to support arbitrary amounts of data

Previously, `Heap` would store serialized data in blocks of 1024 bytes
regardless of the actual length. Data longer than 1024 bytes was
silently truncated causing database corruption.

This changes the heap storage to prefix every block with two new fields:
the total data size in bytes, and the next block to retrieve if the data
is longer than what can be stored inside a single block. By chaining
blocks together, we can store arbitrary amounts of data without needing
to change anything of the logic in the rest of LibSQL.

As part of these changes, the "free list" is also removed from the heap
awaiting an actual implementation: it was never used.

Note that this bumps the database version from 3 to 4, and as such
invalidates (deletes) any database opened with LibSQL that is not
version 4.

1 files changed, 56 insertions, 24 deletions

diff --git a/Userland/Libraries/LibSQL/Heap.h b/Userland/Libraries/LibSQL/Heap.h
index 00ca39f7a9..62380ae2f2 100644
--- a/Userland/Libraries/LibSQL/Heap.h
+++ b/Userland/Libraries/LibSQL/Heap.h
@@ -1,5 +1,6 @@
 /*
  * Copyright (c) 2021, Jan de Visser <jan@de-visser.net>
+ * Copyright (c) 2023, Jelle Raaijmakers <jelle@gmta.nl>
  *
  * SPDX-License-Identifier: BSD-2-Clause
  */
@@ -16,6 +17,43 @@
 namespace SQL {
 
 /**
+ * A Block represents a single discrete chunk of 1024 bytes inside the Heap, and
+ * acts as the container format for the actual data we are storing. This structure
+ * is used for everything except block 0, the zero / super block.
+ *
+ * If data needs to be stored that is larger than 1016 bytes, Blocks are chained
+ * together by setting the next block index and the data is reconstructed by
+ * repeatedly reading blocks until the next block index is 0.
+ */
+class Block {
+public:
+    typedef u32 Index;
+
+    static constexpr u32 SIZE = 1024;
+    static constexpr u32 HEADER_SIZE = sizeof(u32) + sizeof(Index);
+    static constexpr u32 DATA_SIZE = SIZE - HEADER_SIZE;
+
+    Block(Index index, u32 size_in_bytes, Index next_block, ByteBuffer data)
+        : m_index(index)
+        , m_size_in_bytes(size_in_bytes)
+        , m_next_block(next_block)
+        , m_data(move(data))
+    {
+    }
+
+    Index index() const { return m_index; }
+    u32 size_in_bytes() const { return m_size_in_bytes; }
+    Index next_block() const { return m_next_block; }
+    ByteBuffer const& data() const { return m_data; }
+
+private:
+    Index m_index;
+    u32 m_size_in_bytes;
+    Index m_next_block;
+    ByteBuffer m_data;
+};
+
+/**
  * A Heap is a logical container for database (SQL) data. Conceptually a
  * Heap can be a database file, or a memory block, or another storage medium.
  * It contains datastructures, like B-Trees, hash_index tables, or tuple stores
@@ -23,30 +61,25 @@ namespace SQL {
  *
  * A Heap can be thought of the backing storage of a single database. It's
  * assumed that a single SQL database is backed by a single Heap.
- *
- * Currently only B-Trees and tuple stores are implemented.
  */
 class Heap : public Core::Object {
     C_OBJECT(Heap);
 
 public:
-    static constexpr u32 VERSION = 3;
-    static constexpr u32 BLOCK_SIZE = 1024;
+    static constexpr u32 VERSION = 4;
 
     virtual ~Heap() override;
 
     ErrorOr<void> open();
-    u32 size() const { return m_end_of_file; }
-    ErrorOr<ByteBuffer> read_block(u32);
-    [[nodiscard]] u32 new_record_pointer();
-    [[nodiscard]] bool valid() const { return static_cast<bool>(m_file); }
+    bool has_block(Block::Index) const;
+    [[nodiscard]] Block::Index request_new_block_index() { return m_next_block++; }
 
     u32 schemas_root() const { return m_schemas_root; }
 
     void set_schemas_root(u32 root)
     {
         m_schemas_root = root;
-        update_zero_block();
+        update_zero_block().release_value_but_fixme_should_propagate_errors();
     }
 
     u32 tables_root() const { return m_tables_root; }
@@ -54,7 +87,7 @@ public:
     void set_tables_root(u32 root)
     {
         m_tables_root = root;
-        update_zero_block();
+        update_zero_block().release_value_but_fixme_should_propagate_errors();
     }
 
     u32 table_columns_root() const { return m_table_columns_root; }
@@ -62,7 +95,7 @@ public:
     void set_table_columns_root(u32 root)
     {
         m_table_columns_root = root;
-        update_zero_block();
+        update_zero_block().release_value_but_fixme_should_propagate_errors();
     }
     u32 version() const { return m_version; }
 
@@ -74,31 +107,30 @@ public:
     void set_user_value(size_t index, u32 value)
     {
         m_user_values[index] = value;
-        update_zero_block();
+        update_zero_block().release_value_but_fixme_should_propagate_errors();
     }
 
-    void add_to_wal(u32 block, ByteBuffer& buffer)
-    {
-        dbgln_if(SQL_DEBUG, "Adding to WAL: block #{}, size {}", block, buffer.size());
-        dbgln_if(SQL_DEBUG, "{:hex-dump}", buffer.bytes().trim(8));
-        m_write_ahead_log.set(block, buffer);
-    }
+    ErrorOr<ByteBuffer> read_storage(Block::Index);
+    ErrorOr<void> write_storage(Block::Index, ReadonlyBytes);
 
     ErrorOr<void> flush();
 
 private:
     explicit Heap(DeprecatedString);
 
-    ErrorOr<void> write_block(u32, ByteBuffer&);
-    ErrorOr<void> seek_block(u32);
+    ErrorOr<ByteBuffer> read_raw_block(Block::Index);
+    ErrorOr<void> write_raw_block(Block::Index, ReadonlyBytes);
+    ErrorOr<void> write_raw_block_to_wal(Block::Index, ByteBuffer&&);
+
+    ErrorOr<Block> read_block(Block::Index);
+    ErrorOr<void> write_block(Block const&);
     ErrorOr<void> read_zero_block();
-    void initialize_zero_block();
-    void update_zero_block();
+    ErrorOr<void> initialize_zero_block();
+    ErrorOr<void> update_zero_block();
 
     OwnPtr<Core::BufferedFile> m_file;
-    u32 m_free_list { 0 };
+    Block::Index m_highest_block_written { 0 };
     u32 m_next_block { 1 };
-    u32 m_end_of_file { 1 };
     u32 m_schemas_root { 0 };
     u32 m_tables_root { 0 };
     u32 m_table_columns_root { 0 };