store-io-format 0.6.0

On-disk formats for store-io: CRC32C, A/B slot headers and metadata codecs. Pure and allocation-free.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
//! Payload codecs of container format 2 (`docs/FORMAT.md`):
//! the 64-byte volume record, the table pages with their
//! 96-byte entries, and the region header with its extent list.
//!
//! Decoders never allocate and never panic. They check the layout and every
//! field the format defines on its own; rules that need the container (the
//! file length, the table area, the page copy's `meta_seq`) are checked
//! against [`EntryLimits`], which the caller fills from what it knows.
//! Payload lengths are exact: a longer payload is a newer layout, not extra
//! bytes to ignore.

use crate::codec::{Reader, Writer};
use crate::meta::{
    FillPattern, MetaError, NAME_MAX, RegionKind, RegionName, RegionState, VolumeMeta,
};

/// Encoded length of [`VolumeMeta2`].
pub const VOLUME_META2_LEN: usize = 64;
/// Length of a table page's header.
pub const PAGE_HEADER_LEN: usize = 24;
/// Length of one table entry.
pub const ENTRY2_LEN: usize = 96;
/// Length of a region header's fixed part.
pub const REGION_HEADER2_LEN: usize = 64;
/// Length of one extent in a region header.
pub const EXTENT_LEN: usize = 16;
/// Pages a container may have (`P < 2^30`, so region ids stay below 2^62).
pub const MAX_TABLE_PAGES: u32 = 1 << 30;
/// Entry flag: provisioned with `unwritten_ok`.
pub const FLAG_UNWRITTEN: u8 = 1 << 0;
/// Entry flag: growth limited to the capacity (`max_size`).
pub const FLAG_CAPPED: u8 = 1 << 1;
/// Must-understand entry flags this version knows.
pub const KNOWN_FLAGS: u8 = FLAG_UNWRITTEN | FLAG_CAPPED;

/// Container blocks and table slots: `log2` from 12 to 16 (4 KiB to 64 KiB).
pub const LOG2_RANGE: core::ops::RangeInclusive<u8> = 12..=16;

/// Entries per table page for a table slot of `1 << log2_table` bytes:
/// `floor((T - 128 - 24) / 96)` (169 at 16 KiB). `log2_table` is clamped to
/// [`LOG2_RANGE`] (the volume record's decoder refuses anything else).
#[must_use]
pub const fn entries_per_page(log2_table: u8) -> u16 {
    let l = if log2_table < 12 {
        12
    } else if log2_table > 16 {
        16
    } else {
        log2_table
    };
    let t = 1u32 << l;
    ((t - 128 - PAGE_HEADER_LEN as u32) / ENTRY2_LEN as u32) as u16
}

/// Most extents a region header can list at blocks of `1 << log2_block`:
/// `(B - 192) / 16` (244 at 4 KiB). `log2_block` is clamped to
/// [`LOG2_RANGE`].
#[must_use]
pub const fn max_extents(log2_block: u8) -> usize {
    let l = if log2_block < 12 {
        12
    } else if log2_block > 16 {
        16
    } else {
        log2_block
    };
    ((1usize << l) - 128 - REGION_HEADER2_LEN) / EXTENT_LEN
}

/// Largest slot object at blocks of `1 << log2_block`: `B - 192` (3,904 at
/// 4 KiB). `log2_block` is clamped to [`LOG2_RANGE`].
#[must_use]
pub const fn max_object(log2_block: u8) -> usize {
    let l = if log2_block < 12 {
        12
    } else if log2_block > 16 {
        16
    } else {
        log2_block
    };
    (1usize << l) - 128 - REGION_HEADER2_LEN
}

// ---------------------------------------------------------------------------
// Volume record (object 0)
// ---------------------------------------------------------------------------

/// The format-2 volume record: format 1's fields and the paged table's
/// geometry and clean-close flag.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct VolumeMeta2 {
    /// Format 1's fields (`table_offset` is `2B`; `features` 0).
    pub base: VolumeMeta,
    /// Table pages `P`, `1 <= P < 2^30`.
    pub table_pages: u32,
    /// Entries per page `E` (must equal [`entries_per_page`]).
    pub entries_per_page: u16,
    /// The last writer closed cleanly.
    pub clean_close: bool,
    /// Must-understand volume flags (none defined).
    pub flags: u32,
}

impl VolumeMeta2 {
    /// Encodes the record and returns the bytes written
    /// ([`VOLUME_META2_LEN`]).
    ///
    /// # Errors
    ///
    /// [`MetaError::Length`] if `out` is shorter than [`VOLUME_META2_LEN`].
    pub fn encode(&self, out: &mut [u8]) -> Result<usize, MetaError> {
        let n = self.base.encode(out)?;
        let mut w = Writer::new(out.get_mut(n..).ok_or(MetaError::Length)?);
        w.u32(self.table_pages)?;
        w.u16(self.entries_per_page)?;
        w.u8(u8::from(self.clean_close))?;
        w.u8(0)?;
        w.u32(self.flags)?;
        w.u32(0)?;
        Ok(n + w.position())
    }

    /// Decodes and validates a record of exactly [`VOLUME_META2_LEN`] bytes.
    ///
    /// # Errors
    ///
    /// [`MetaError::Field`] naming `features` or `flags` for a newer record
    /// (checked first); [`MetaError`] for anything else that is not
    /// format 2.
    pub fn decode(bytes: &[u8]) -> Result<Self, MetaError> {
        if bytes.len() != VOLUME_META2_LEN {
            return Err(MetaError::Length);
        }
        let mut r = Reader::new(&bytes[48..]);
        let table_pages = r.u32()?;
        let entries = r.u16()?;
        let clean_close = r.u8()?;
        let reserved0 = r.u8()?;
        let flags = r.u32()?;
        let reserved1 = r.u32()?;
        // Newer-format markers first, before any other field, so a newer
        // record is recognised as newer and never as damage: `features` (F1,
        // bytes 32..40), then `flags`.
        if bytes[32..40].iter().any(|&b| b != 0) {
            return Err(MetaError::Field("features"));
        }
        if flags != 0 {
            return Err(MetaError::Field("flags"));
        }
        let base = VolumeMeta::decode(&bytes[..48])?;
        if reserved0 != 0 || reserved1 != 0 {
            return Err(MetaError::Field("reserved"));
        }
        if base.table_offset != 2u64 << base.log2_block_size {
            return Err(MetaError::Field("table_offset"));
        }
        if table_pages == 0 || table_pages >= MAX_TABLE_PAGES {
            return Err(MetaError::Field("table_pages"));
        }
        if entries != entries_per_page(base.log2_table_slot_size) {
            return Err(MetaError::Field("entries_per_page"));
        }
        if clean_close > 1 {
            return Err(MetaError::Field("clean_close"));
        }
        Ok(Self {
            base,
            table_pages,
            entries_per_page: entries,
            clean_close: clean_close == 1,
            flags,
        })
    }

    /// Checks that the table area lies within a container of `file_len`
    /// bytes (spec ยง5; the decoder cannot know the file's length).
    ///
    /// # Errors
    ///
    /// [`MetaError::Field`] (`table_pages`) if it does not.
    pub fn check_file_len(&self, file_len: u64) -> Result<(), MetaError> {
        if self.table_end() > file_len {
            return Err(MetaError::Field("table_pages"));
        }
        Ok(())
    }

    /// The end of the table area: `2B + 2PT`.
    #[must_use]
    pub fn table_end(&self) -> u64 {
        let b = 1u64 << self.base.log2_block_size;
        let t = 1u64 << self.base.log2_table_slot_size;
        2 * b + 2 * u64::from(self.table_pages) * t
    }
}

// ---------------------------------------------------------------------------
// Table pages (object 2^61 | p)
// ---------------------------------------------------------------------------

/// A table page's header.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct PageHeader {
    /// The page's index `p` (must match the object id).
    pub page_index: u32,
    /// The next sequence number the page gives out; never decreases.
    pub next_seq: u32,
    /// Entries that follow.
    pub count: u16,
}

/// One table entry as stored: every field, before the per-entry checks
/// (an entry that fails them makes its region unavailable, and its span is
/// still needed, so the raw fields are always available).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct RawEntry {
    /// Sequence number in the page; region id `p << 32 | seq`.
    pub seq: u32,
    /// Kind code (`1..=3`).
    pub kind: u8,
    /// State code (`1`).
    pub state: u8,
    /// Must-understand flags.
    pub flags: u8,
    /// May-ignore flags.
    pub compat_flags: u8,
    /// The zero-padded name bytes.
    pub name: [u8; NAME_MAX],
    /// Space-accounting tag.
    pub tag: u32,
    /// Committed extents.
    pub extent_count: u16,
    /// The 2 reserved bytes at 38 (checked at page level: zero).
    reserved: u16,
    /// Header slot A's offset.
    pub header_a: u64,
    /// Header slot B's offset.
    pub header_b: u64,
    /// Usable length.
    pub data_size: u64,
    /// Reserved length (the extents' sum).
    pub capacity: u64,
    /// Lowest offset of the footprint.
    pub span_start: u64,
    /// One past the highest.
    pub span_end: u64,
    /// `meta_seq` of the page write that last changed the footprint.
    pub footprint_seq: u64,
}

/// A table entry that passed the per-entry checks.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Entry2 {
    /// Sequence number in the page.
    pub seq: u32,
    /// Region kind.
    pub kind: RegionKind,
    /// Must-understand flags (only known ones).
    pub flags: u8,
    /// May-ignore flags, kept verbatim.
    pub compat_flags: u8,
    /// Region name.
    pub name: RegionName,
    /// Space-accounting tag.
    pub tag: u32,
    /// Committed extents.
    pub extent_count: u16,
    /// Header slot A's offset.
    pub header_a: u64,
    /// Header slot B's offset.
    pub header_b: u64,
    /// Usable length.
    pub data_size: u64,
    /// Reserved length.
    pub capacity: u64,
    /// Lowest offset of the footprint.
    pub span_start: u64,
    /// One past the highest.
    pub span_end: u64,
    /// `meta_seq` of the page write that last changed the footprint.
    pub footprint_seq: u64,
}

impl Entry2 {
    /// The rules between an entry and its region's header (spec ยง9 step 3):
    /// the header names this region (`region_id`), kind and flags agree, the
    /// header is Ready, it lists the entry's extents or one more (never more
    /// for a slot region), and `data_size` is a whole number of the region's
    /// data blocks.
    ///
    /// # Errors
    ///
    /// [`MetaError::Field`] naming the first rule that fails.
    pub fn check_header(&self, region_id: u64, h: &RegionHeader2) -> Result<(), MetaError> {
        if h.region_id != region_id {
            return Err(MetaError::Field("region_id"));
        }
        if h.kind != self.kind {
            return Err(MetaError::Field("kind"));
        }
        if h.flags != self.flags {
            return Err(MetaError::Field("flags"));
        }
        if h.state != RegionState::Ready {
            return Err(MetaError::Field("state"));
        }
        let more = if self.kind == RegionKind::Slot { 0 } else { 1 };
        let (have, want) = (u32::from(h.extent_count), u32::from(self.extent_count));
        if have < want || have > want + more {
            return Err(MetaError::Field("extent_count"));
        }
        if self.data_size % (1u64 << h.log2_block.clamp(9, 16)) != 0 {
            return Err(MetaError::Unaligned);
        }
        Ok(())
    }

    /// The entry as stored (for writing it back).
    #[must_use]
    pub fn to_raw(&self) -> RawEntry {
        let mut name = [0u8; NAME_MAX];
        let s = self.name.as_str().as_bytes();
        name[..s.len()].copy_from_slice(s);
        RawEntry {
            seq: self.seq,
            kind: self.kind.to_u8(),
            state: RegionState::Ready.to_u8(),
            flags: self.flags,
            compat_flags: self.compat_flags,
            name,
            tag: self.tag,
            extent_count: self.extent_count,
            reserved: 0,
            header_a: self.header_a,
            header_b: self.header_b,
            data_size: self.data_size,
            capacity: self.capacity,
            span_start: self.span_start,
            span_end: self.span_end,
            footprint_seq: self.footprint_seq,
        }
    }
}

/// What the per-entry checks need from the container.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct EntryLimits {
    /// `log2(B)`.
    pub log2_block: u8,
    /// The end of the table area (`2B + 2PT`): nothing of a region before it.
    pub table_end: u64,
    /// The container file's length.
    pub file_len: u64,
    /// The `meta_seq` of the page copy holding the entry.
    pub page_meta_seq: u64,
}

impl RawEntry {
    fn read(r: &mut Reader<'_>) -> Result<Self, MetaError> {
        Ok(Self {
            seq: r.u32()?,
            kind: r.u8()?,
            state: r.u8()?,
            flags: r.u8()?,
            compat_flags: r.u8()?,
            name: r.array::<NAME_MAX>()?,
            tag: r.u32()?,
            extent_count: r.u16()?,
            reserved: r.u16()?,
            header_a: r.u64()?,
            header_b: r.u64()?,
            data_size: r.u64()?,
            capacity: r.u64()?,
            span_start: r.u64()?,
            span_end: r.u64()?,
            footprint_seq: r.u64()?,
        })
    }

    fn write(&self, w: &mut Writer<'_>) -> Result<(), MetaError> {
        w.u32(self.seq)?;
        w.u8(self.kind)?;
        w.u8(self.state)?;
        w.u8(self.flags)?;
        w.u8(self.compat_flags)?;
        w.bytes(&self.name)?;
        w.u32(self.tag)?;
        w.u16(self.extent_count)?;
        w.u16(0)?;
        w.u64(self.header_a)?;
        w.u64(self.header_b)?;
        w.u64(self.data_size)?;
        w.u64(self.capacity)?;
        w.u64(self.span_start)?;
        w.u64(self.span_end)?;
        w.u64(self.footprint_seq)?;
        Ok(())
    }

    /// The per-entry checks (spec ยง6). An entry that fails them makes its
    /// region unavailable; the page itself stands. The data-block rule is
    /// checked here as far as the entry alone allows (B for page regions,
    /// 512 bytes for append regions, which may use 512 B blocks); the
    /// region's own block comes from its header, and
    /// [`Entry2::check_header`] checks the rest.
    ///
    /// # Errors
    ///
    /// [`MetaError`] naming the first rule that fails (`flags` first, so an
    /// entry from a newer release is recognised as such).
    pub fn check(&self, lim: &EntryLimits) -> Result<Entry2, MetaError> {
        if self.flags & !KNOWN_FLAGS != 0 {
            return Err(MetaError::Field("flags"));
        }
        if !LOG2_RANGE.contains(&lim.log2_block) {
            return Err(MetaError::Field("log2_block"));
        }
        let kind = RegionKind::from_u8(self.kind)?;
        if RegionState::from_u8(self.state)? != RegionState::Ready {
            return Err(MetaError::Field("state"));
        }
        let name = RegionName::from_padded(self.name)?;
        if self.data_size > self.capacity {
            return Err(MetaError::Field("data_size"));
        }
        let block = 1u64 << lim.log2_block;
        if self.span_start >= self.span_end || self.span_end > lim.file_len {
            return Err(MetaError::Field("span"));
        }
        // The extents lie in the span (checked with the header), so their
        // sum, the capacity, cannot exceed it.
        if self.capacity > self.span_end - self.span_start {
            return Err(MetaError::Field("capacity"));
        }
        if self.span_start % block != 0 || self.span_end % block != 0 {
            return Err(MetaError::Unaligned);
        }
        for h in [self.header_a, self.header_b] {
            if h % block != 0 {
                return Err(MetaError::Unaligned);
            }
            let end = h.checked_add(block).ok_or(MetaError::Field("header"))?;
            if h < lim.table_end || h < self.span_start || end > self.span_end {
                return Err(MetaError::Field("header"));
            }
        }
        if self.header_a == self.header_b {
            return Err(MetaError::Field("header"));
        }
        if self.footprint_seq == 0 || self.footprint_seq > lim.page_meta_seq {
            return Err(MetaError::Field("footprint_seq"));
        }
        if kind == RegionKind::Slot {
            if self.extent_count != 0 || self.capacity != 0 || self.data_size != 0 {
                return Err(MetaError::Field("slot"));
            }
        } else if self.extent_count == 0 {
            return Err(MetaError::Field("extent_count"));
        } else if self.capacity == 0 {
            return Err(MetaError::Field("capacity"));
        }
        // Whole data blocks: B for every kind but append (512 B possible).
        let unit = if kind == RegionKind::Append {
            512
        } else {
            block
        };
        if self.capacity % block != 0 || self.data_size % unit != 0 {
            return Err(MetaError::Unaligned);
        }
        Ok(Entry2 {
            seq: self.seq,
            kind,
            flags: self.flags,
            compat_flags: self.compat_flags,
            name,
            tag: self.tag,
            extent_count: self.extent_count,
            header_a: self.header_a,
            header_b: self.header_b,
            data_size: self.data_size,
            capacity: self.capacity,
            span_start: self.span_start,
            span_end: self.span_end,
            footprint_seq: self.footprint_seq,
        })
    }

    /// The entry's name, when it decodes (whatever else fails): a name
    /// an unavailable entry keeps reserved.
    #[must_use]
    pub fn name(&self) -> Option<RegionName> {
        RegionName::from_padded(self.name).ok()
    }

    /// The entry's name and kind, when both decode (so an entry that fails
    /// the per-entry checks can still be named in a report).
    #[must_use]
    pub fn name_and_kind(&self) -> Option<(RegionName, RegionKind)> {
        Some((
            RegionName::from_padded(self.name).ok()?,
            RegionKind::from_u8(self.kind).ok()?,
        ))
    }

    /// The bytes an unavailable entry keeps reserved: its span widened to
    /// whole blocks, then clamped to the file and to past the table area
    /// (`None` when nothing is left).
    #[must_use]
    pub fn reserved_span(&self, lim: &EntryLimits) -> Option<(u64, u64)> {
        let block = 1u64 << lim.log2_block.clamp(12, 16);
        let start = (self.span_start - self.span_start % block).max(lim.table_end);
        let end = self
            .span_end
            .checked_next_multiple_of(block)
            .unwrap_or(u64::MAX)
            .min(lim.file_len);
        (start < end).then_some((start, end))
    }
}

/// Encodes a page and returns the payload length (`24 + 96 * entries`).
///
/// # Errors
///
/// [`MetaError::Length`] if `out` is too short or there are more than
/// `u16::MAX` entries.
pub fn encode_page(
    out: &mut [u8],
    h: &PageHeader,
    entries: &[RawEntry],
) -> Result<usize, MetaError> {
    let count = u16::try_from(entries.len()).map_err(|_| MetaError::Length)?;
    if count != h.count {
        return Err(MetaError::Field("count"));
    }
    let mut w = Writer::new(out);
    w.u32(h.page_index)?;
    w.u32(h.next_seq)?;
    w.u16(count)?;
    w.zeros(14)?;
    for e in entries {
        e.write(&mut w)?;
    }
    Ok(w.position())
}

/// A decoded page: its header and its entries, each checked or not by the
/// caller with [`RawEntry::check`].
#[derive(Debug, Clone, Copy)]
pub struct Page<'a> {
    /// The page header.
    pub header: PageHeader,
    entries: &'a [u8],
}

impl<'a> Page<'a> {
    /// The raw entries, in stored order.
    pub fn entries(&self) -> impl Iterator<Item = RawEntry> + 'a {
        self.entries.chunks_exact(ENTRY2_LEN).filter_map(|c| {
            // Every chunk is ENTRY2_LEN bytes, so reading one never fails.
            RawEntry::read(&mut Reader::new(c)).ok()
        })
    }
}

/// Decodes a page payload and applies the page checks (spec ยง6): a page
/// that fails them is lost.
///
/// # Errors
///
/// [`MetaError`] for the first page-level rule that fails.
pub fn decode_page(bytes: &[u8], page_index: u32, max_entries: u16) -> Result<Page<'_>, MetaError> {
    let mut r = Reader::new(bytes);
    let header = PageHeader {
        page_index: r.u32()?,
        next_seq: r.u32()?,
        count: r.u16()?,
    };
    if r.bytes(14)?.iter().any(|&b| b != 0) {
        return Err(MetaError::Field("reserved"));
    }
    if header.page_index != page_index {
        return Err(MetaError::Field("page_index"));
    }
    if header.count > max_entries || u32::from(header.count) > header.next_seq {
        return Err(MetaError::Field("count"));
    }
    let len = usize::from(header.count) * ENTRY2_LEN;
    if bytes.len() != PAGE_HEADER_LEN + len {
        return Err(MetaError::Length);
    }
    let entries = &bytes[PAGE_HEADER_LEN..];
    let page = Page { header, entries };
    // Seqs unique and below next_seq; reserved bytes zero. O(n^2) over at
    // most a few hundred entries, with no allocation.
    let seq_at = |c: &[u8]| u32::from_le_bytes([c[0], c[1], c[2], c[3]]);
    let chunks = || entries.chunks_exact(ENTRY2_LEN);
    for (i, c) in chunks().enumerate() {
        let seq = seq_at(c);
        if seq >= header.next_seq {
            return Err(MetaError::Field("seq"));
        }
        if c[38] != 0 || c[39] != 0 {
            return Err(MetaError::Field("reserved"));
        }
        if chunks().skip(i + 1).any(|d| seq_at(d) == seq) {
            return Err(MetaError::Duplicate);
        }
    }
    Ok(page)
}

// ---------------------------------------------------------------------------
// Region header (object 2^62 | region_id)
// ---------------------------------------------------------------------------

/// A format-2 region header's fixed part.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct RegionHeader2 {
    /// `p << 32 | seq`.
    pub region_id: u64,
    /// Region kind (as the entry).
    pub kind: RegionKind,
    /// Ready, or Released (forensic).
    pub state: RegionState,
    /// Fill pattern.
    pub fill: FillPattern,
    /// Must-understand flags (as the entry).
    pub flags: u8,
    /// May-ignore flags, kept verbatim.
    pub compat_flags: u8,
    /// The region's data block: `log2(B)`, or 9 for a 512 B append region.
    pub log2_block: u8,
    /// Extents listed (the entry's count, or one more after a crash inside
    /// a growth beyond capacity).
    pub extent_count: u16,
    /// The region's generation (`1` at provisioning).
    pub region_generation: u64,
    /// Key of the keyed fill (zero for zeros).
    pub fill_key: [u8; 16],
    /// A slot region's object length (others 0).
    pub object_len: u32,
}

/// One extent: `(offset, length)` in the file.
pub type Extent = (u64, u64);

/// Encodes a region header: the fixed part, then `extents` (append and page
/// regions) or `object` (slot regions). Returns the payload length.
///
/// # Errors
///
/// [`MetaError::Length`] if `out` is too short; [`MetaError::Field`] if
/// `extent_count` or `object_len` disagree with what is passed.
pub fn encode_region_header(
    out: &mut [u8],
    h: &RegionHeader2,
    extents: &[Extent],
    object: &[u8],
) -> Result<usize, MetaError> {
    let slot = h.kind == RegionKind::Slot;
    if usize::from(h.extent_count) != extents.len() || (slot && !extents.is_empty()) {
        return Err(MetaError::Field("extent_count"));
    }
    if h.object_len as usize != object.len() || (!slot && !object.is_empty()) {
        return Err(MetaError::Field("object_len"));
    }
    let mut w = Writer::new(out);
    w.u64(h.region_id)?;
    w.u8(h.kind.to_u8())?;
    w.u8(h.state.to_u8())?;
    w.u8(h.fill.to_u8())?;
    w.u8(h.flags)?;
    w.u8(h.compat_flags)?;
    w.u8(h.log2_block)?;
    w.u16(h.extent_count)?;
    w.u64(h.region_generation)?;
    w.bytes(&h.fill_key)?;
    w.u32(h.object_len)?;
    w.zeros(20)?;
    for &(off, len) in extents {
        w.u64(off)?;
        w.u64(len)?;
    }
    w.bytes(object)?;
    Ok(w.position())
}

/// A decoded region header: the fixed part and its extents or object.
#[derive(Debug, Clone, Copy)]
pub struct RegionHeaderView<'a> {
    /// The fixed part.
    pub header: RegionHeader2,
    tail: &'a [u8],
}

impl<'a> RegionHeaderView<'a> {
    /// The listed extents, in data order.
    pub fn extents(&self) -> impl Iterator<Item = Extent> + 'a {
        let n = usize::from(self.header.extent_count) * EXTENT_LEN;
        self.tail
            .get(..n)
            .unwrap_or(&[])
            .chunks_exact(EXTENT_LEN)
            .map(|c| {
                let mut a = [0u8; 8];
                let mut b = [0u8; 8];
                a.copy_from_slice(&c[..8]);
                b.copy_from_slice(&c[8..]);
                (u64::from_le_bytes(a), u64::from_le_bytes(b))
            })
    }

    /// A slot region's object.
    #[must_use]
    pub fn object(&self) -> &'a [u8] {
        if self.header.kind == RegionKind::Slot {
            self.tail
        } else {
            &[]
        }
    }
}

/// Decodes and validates a region header payload for a container of blocks
/// of `1 << log2_block` bytes and `file_len` bytes (spec ยง8).
///
/// # Errors
///
/// [`MetaError`] for the first rule that fails.
pub fn decode_region_header(
    bytes: &[u8],
    log2_block: u8,
    file_len: u64,
) -> Result<RegionHeaderView<'_>, MetaError> {
    if !LOG2_RANGE.contains(&log2_block) {
        return Err(MetaError::Field("log2_block"));
    }
    let mut r = Reader::new(bytes);
    let region_id = r.u64()?;
    let (kind, state, fill, flags) = (r.u8()?, r.u8()?, r.u8()?, r.u8()?);
    // Must-understand flags first: a header from a newer release is
    // recognised as such, not as a bad kind or fill.
    if flags & !KNOWN_FLAGS != 0 {
        return Err(MetaError::Field("flags"));
    }
    let kind = RegionKind::from_u8(kind)?;
    let state = RegionState::from_u8(state)?;
    let fill = FillPattern::from_u8(fill)?;
    let compat_flags = r.u8()?;
    let log2 = r.u8()?;
    let extent_count = r.u16()?;
    let region_generation = r.u64()?;
    let fill_key = r.array::<16>()?;
    let object_len = r.u32()?;
    if r.bytes(20)?.iter().any(|&b| b != 0) {
        return Err(MetaError::Field("reserved"));
    }
    if !(log2 == log2_block || (log2 == 9 && kind == RegionKind::Append)) {
        return Err(MetaError::Field("log2_block"));
    }
    if region_generation == 0 {
        return Err(MetaError::Field("region_generation"));
    }
    if fill == FillPattern::Zeros && fill_key != [0; 16] {
        return Err(MetaError::Field("fill_key"));
    }
    let tail = &bytes[REGION_HEADER2_LEN.min(bytes.len())..];
    if kind == RegionKind::Slot {
        if extent_count != 0 {
            return Err(MetaError::Field("extent_count"));
        }
        if tail.len() != object_len as usize || tail.len() > max_object(log2_block) {
            return Err(MetaError::Length);
        }
    } else {
        if object_len != 0
            || extent_count == 0
            || usize::from(extent_count) > max_extents(log2_block)
        {
            return Err(MetaError::Field("extent_count"));
        }
        if tail.len() != usize::from(extent_count) * EXTENT_LEN {
            return Err(MetaError::Length);
        }
    }
    let view = RegionHeaderView {
        header: RegionHeader2 {
            region_id,
            kind,
            state,
            fill,
            flags,
            compat_flags,
            log2_block: log2,
            extent_count,
            region_generation,
            fill_key,
            object_len,
        },
        tail,
    };
    let block = 1u64 << log2_block;
    for (off, len) in view.extents() {
        if len == 0 || off % block != 0 || len % block != 0 {
            return Err(MetaError::Unaligned);
        }
        match off.checked_add(len) {
            Some(end) if end <= file_len => {}
            _ => return Err(MetaError::Field("extent")),
        }
    }
    Ok(view)
}