Luce packages
LuceLuce BaseLuciaOS

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)