dymokomi/luce-prism
Source of release 0.6.1
0.6.1 / src / wal / checkpoint.lucb
## Format 002: complete checksummed base + ordinary format-001 TXN1 suffix.
## The base is never a recoverable torn tail. All integers are little-endian.
from luce_std import files
import io
import memory
import wal.tree
import wal.storage_io as storage
from wal.bytes import Buffer, Reader, Crc32, checksum, compare, valid_key, max_key, max_value, max_records, corrupt, limit
pub let header: str = "PRISM-WAL-002\n"
pub let max_bytes: i64 = 268435456
pub let buffer_size: usize = 65536
let overhead: i64 = 62
struct Cursor:
var pending: tree.Node*?
var stack: tree.Node*?[64]
var depth: usize
func next() -> tree.Entry*?!:
while let node = self.pending:
if self.depth == self.stack.length: error(limit, "checkpoint index depth exceeds bound")
self.stack[self.depth] = node
self.depth += 1
self.pending = node.left
if self.depth == 0: return none
self.depth -= 1
let node = self.stack[self.depth] else trap("checkpoint cursor invariant")
self.pending = node.right
return node.item
pub func measure(root: tree.Node*?, generation: u64) -> i64!:
let records = tree.count(root)
if records > max_records or generation > 9223372036854775807 or (generation == 0 and records != 0):
error(limit, "invalid checkpoint generation/count")
var total: i64 = overhead
var seen: usize
var cursor = Cursor(pending = root)
while let item = try cursor.next():
let key = item.key.span()
let value = item.value.span()
try valid_key((str)key)
if value.length > max_value: error(limit, "checkpoint value exceeds bound")
let length = (i64)(24 + key.length + value.length)
if length > max_bytes - total: error(limit, "checkpoint exceeds journal size bound")
total += length
seen += 1
if seen != records: error(limit, "checkpoint index count mismatch")
return total
struct Sink:
var file: files.File*
var controls: storage.Controls
var buffer: u8[]
var used: usize
var total: i64
var crc: Crc32 = Crc32()
func flush() -> !:
if self.used == 0: return
try storage.write_all(self.file, self.controls, self.buffer[..<self.used])
self.used = 0
func put(data: const u8[], included: bool = true) -> !:
if included: self.crc.update(data)
self.total += (i64)data.length
var offset: usize
while offset < data.length:
let room = self.buffer.length - self.used
let amount = room if room < data.length - offset else data.length - offset
memory.copy(self.buffer[self.used..], data[offset..], amount)
self.used += amount
offset += amount
if self.used == self.buffer.length: try self.flush()
func uint(out: u8[], offset: usize, value: u64, width: usize):
for i in 0..<width: out[offset + i] = (u8)(value >> (i * 8))
pub func write(file: files.File*, controls: storage.Controls, root: tree.Node*?, generation: u64, size: i64) -> !:
let buffer = try new u8[buffer_size] --- in memory.heap
defer free(buffer) in memory.heap
var sink = Sink(file = file, controls = controls, buffer = buffer)
try sink.put(header.bytes)
var prefix: u8[32]
memory.copy(prefix, b"CKP2", 4)
uint(prefix, 4, generation, 8)
uint(prefix, 12, (u64)tree.count(root), 8)
uint(prefix, 20, (u64)(size - overhead), 8)
uint(prefix, 28, (u64)checksum(prefix[..<28]), 4)
try sink.put(prefix)
var cursor = Cursor(pending = root)
while let item = try cursor.next():
var record: u8[16]
memory.copy(record, b"ROW2", 4)
uint(record, 4, (u64)item.key.count, 4)
uint(record, 8, (u64)item.value.count, 4)
uint(record, 12, (u64)checksum(record[..<12]), 4)
var crc = Crc32()
crc.update(record)
crc.update(item.key.span())
crc.update(item.value.span())
var trailer: u8[8]
uint(trailer, 0, (u64)crc.finish(), 4)
memory.copy(trailer[4..], b"END2", 4)
try sink.put(record)
try sink.put(item.key.span())
try sink.put(item.value.span())
try sink.put(trailer)
var footer: u8[16]
memory.copy(footer, b"BASE-END", 8)
uint(footer, 8, (u64)sink.crc.finish(), 4)
uint(footer, 12, (u64)checksum(footer[..<12]), 4)
try sink.put(footer, false)
if sink.total != size: error(limit, "checkpoint size changed during encoding")
try sink.flush()
pub struct Base:
pub var root: tree.Node*?
pub var generation: u64
pub var records: usize
pub var end: i64
## Called with the descriptor positioned after the already-validated magic.
pub func read(file: files.File*, controls: storage.Controls, size: i64, build_index: bool = true) -> Base!:
if size < overhead or size > max_bytes: error(corrupt, "incomplete checkpoint base")
var prefix: u8[32]
try storage.read_exact(file, controls, prefix)
var meta = Reader(bytes = prefix)
if compare(try meta.take(4), b"CKP2") != 0: error(corrupt, "unknown checkpoint base")
let generation = try meta.uint(8)
let records = try meta.uint(8)
let data_size = try meta.uint(8)
if try meta.uint(4) != (u64)checksum(prefix[..<28]): error(corrupt, "invalid checkpoint header checksum")
if generation > 9223372036854775807 or records > (u64)max_records or (generation == 0 and records != 0):
error(corrupt, "invalid checkpoint generation/count")
if data_size > (u64)(max_bytes - overhead) or data_size > (u64)(size - overhead) or data_size < records * 25:
error(corrupt, "invalid or incomplete checkpoint size")
var aggregate = Crc32()
aggregate.update(header.bytes)
aggregate.update(prefix)
var root: tree.Node*?
errdefer tree.drop(root)
var previous: tree.Entry*?
var previous_key: Buffer
defer previous_key.close()
var data: Buffer
defer data.close()
var remaining = data_size
for index in 0..<(usize)records:
if remaining < 25: error(corrupt, "incomplete checkpoint record")
var record: u8[16]
try storage.read_exact(file, controls, record)
var info = Reader(bytes = record)
if compare(try info.take(4), b"ROW2") != 0: error(corrupt, "invalid checkpoint record tag")
let key_size = (usize)try info.uint(4)
let value_size = (usize)try info.uint(4)
if try info.uint(4) != (u64)checksum(record[..<12]): error(corrupt, "invalid checkpoint record prefix checksum")
if key_size == 0 or key_size > max_key or value_size > max_value:
error(corrupt, "invalid checkpoint key/value length")
let length = key_size + value_size
if (u64)length + 24 > remaining: error(corrupt, "checkpoint record exceeds declared base")
try data.reserve(length)
try storage.read_exact(file, controls, data.data[..<length])
data.count = length
let key = data.span()[..<key_size]
valid_key((str)key) catch failure: error(corrupt, "invalid checkpoint key")
if let prior = previous:
if compare(prior.key.span(), key) >= 0: error(corrupt, "checkpoint keys are duplicated or unordered")
if not build_index and previous_key.count > 0:
if compare(previous_key.span(), key) >= 0: error(corrupt, "checkpoint keys are duplicated or unordered")
var trailer: u8[8]
try storage.read_exact(file, controls, trailer)
var crc = Crc32()
crc.update(record)
crc.update(data.span())
var end = Reader(bytes = trailer)
if try end.uint(4) != (u64)crc.finish() or compare(try end.take(4), b"END2") != 0:
error(corrupt, "invalid checkpoint record trailer/checksum")
aggregate.update(record)
aggregate.update(data.span())
aggregate.update(trailer)
if build_index:
let item = try tree.entry(key, data.span()[key_size..])
defer tree.drop_entry(item)
let next = try tree.put(root, item)
tree.drop(root)
root = next
previous = item
else:
previous_key.count = 0
try previous_key.put(key)
remaining -= (u64)length + 24
if remaining != 0: error(corrupt, "checkpoint record count/byte mismatch")
var footer: u8[16]
try storage.read_exact(file, controls, footer)
var end = Reader(bytes = footer)
if compare(try end.take(8), b"BASE-END") != 0 or try end.uint(4) != (u64)aggregate.finish() or try end.uint(4) != (u64)checksum(footer[..<12]):
error(corrupt, "invalid checkpoint completeness footer")
return Base(root = root, generation = generation, records = (usize)records, end = overhead + (i64)data_size)