ferrosys 0.8.0

Pure-Rust filesystem formatter and reader: ext4, ext3, ext2, FAT32, FAT16, FAT12, exFAT, btrfs, and APFS — rootless, in userspace, byte-reproducible
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
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
//! Geometry: from a volume size and what the filesystem will hold to where every chunk sits
//! and how much metadata it may spend.
//!
//! [`plan_layout`] is the whole of it. It takes what a caller can state — how large the volume
//! is, how large a sector and a node are, how the two kinds of block group are replicated, what
//! features the filesystem carries, and how much content it will be given — and derives what
//! the format records: which chunks exist, how long each is, where it begins in the logical
//! address space, where each copy of it begins on the device, which superblock locations the
//! device has room for, and how many metadata blocks the whole of it may consume.
//!
//! This module is pure and deterministic: it computes numbers from numbers, performs no I/O,
//! reads no clock, and allocates nothing on a device. Planning before writing is what makes an
//! image reproducible — every placement is a value a caller can inspect, compare, and assert
//! against before a byte is emitted.
//!
//! # Two address spaces, advancing at different rates
//!
//! Every address above the chunk layer is logical, and a chunk maps a run of logical space onto
//! one or more copies on the device. A chunk therefore consumes **its length** of logical space
//! and **its length times its copy count** of the device, so the two cursors move apart as soon
//! as anything is mirrored. Both are laid out here, in one pass, so that a copy's physical
//! placement is a value rather than a thing a writer discovers as it goes.
//!
//! # The order chunks are laid down in, and the unallocated span before them
//!
//! The first mebibyte of the device holds no chunk. That much is the format: btrfs(5) leaves it
//! unused apart from the superblock at 64 KiB ("Bootloader support").
//!
//! What follows the first mebibyte is not always a chunk either. Where the pinned baseline
//! replicates a kind of block group, it leaves an unallocated span ahead of that kind's chunks,
//! exactly as long as the unreplicated chunks of that kind would be: the bootstrap system chunk
//! and an unreplicated metadata chunk where metadata is replicated, and an unreplicated data
//! chunk where data is. The layout here lays those chunks down and drops them, which reproduces
//! the spans at every pairing of profiles (observed).
//!
//! Reproducing that is deliberate, and it costs nothing: an unallocated span is device space and
//! logical space that no chunk claims, which a driver allocates from later exactly as it
//! allocates from the space past the last chunk. What it buys is that an image planned here and
//! an image the format's own tooling produces put the same chunk at the same address, which is
//! what makes every record in both comparable one for one — and a record-level comparison is the
//! sharpest evidence a from-scratch writer can be held to.
//!
//! # What a chunk's length comes from
//!
//! Each length is documented or observed. mkfs.btrfs(8) gives a metadata block group 256 MiB
//! below 50 GiB and 1 GiB above, and a data block group 1 GiB. The rest is the pinned
//! baseline's output, which the oracle tier holds this planner to chunk by chunk. The rule has
//! one shape: a preferred length per kind of block group where a tenth of the volume holds it,
//! and otherwise that tenth shared between the chunk's copies, rounded down to [`STRIPE_LEN`]
//! and held to a floor. The one surprise is that **the per-kind lengths apply only where the
//! block group is replicated**: an unmirrored chunk of any kind prefers eight mebibytes, so an
//! unmirrored data chunk is eight mebibytes where a mirrored one runs to a gibibyte.
//! [`chunk_length`] is where that is written down.

use super::MappedChunk;
use super::btree::levels_above;
use super::ondisk::{
    BlockGroupFlags, ChecksumType, Chunk, CompatRoFlags, DevItem, DirItem, Header, IncompatFlags,
    InodeItem, InodeRef, Item, KeyPtr, MAX_BLOCK_SIZE, MIN_BLOCK_SIZE, MIRRORS, RootItem,
    SUPER_INFO_SIZE, Stripe, holds_mirror,
};

#[cfg(feature = "serde")]
use serde::Serialize;

/// Bytes at the start of the device that no chunk may claim.
///
/// The first superblock sits at 64 KiB, inside this span, and btrfs(5) leaves the rest of it
/// unused ("Bootloader support").
pub const RESERVED_HEAD: u64 = 1 << 20;

/// The granularity a chunk's length is rounded down to.
///
/// The format records it per chunk, as the chunk item's stripe length. Every chunk the pinned
/// baseline writes records this value and is a whole number of them long (observed).
pub const STRIPE_LEN: u64 = 64 << 10;

/// The length of the system chunk a filesystem is bootstrapped with.
///
/// The pinned baseline's first system chunk is this long whatever the volume and the profiles
/// (observed).
pub const BOOTSTRAP_SYSTEM_CHUNK: u64 = 4 << 20;

/// The share of the volume no single chunk may exceed, as a divisor.
///
/// A tenth. It is what keeps a chunk on a small volume from being most of it.
pub const VOLUME_SHARE: u64 = 10;

/// The volume length above which a mirrored metadata chunk is allowed to reach a gibibyte
/// rather than a quarter of one.
pub const LARGE_VOLUME: u64 = 50 << 30;

/// The node size a filesystem takes where a caller names none and the sector is smaller.
pub const DEFAULT_NODE_SIZE: u32 = 16 << 10;

/// The sector size a filesystem takes where a caller names none.
///
/// Four kibibytes, the default mkfs.btrfs(8) documents and the one the pinned baseline writes.
/// It is a value rather than a property of the host, so two runs on two architectures plan the
/// same filesystem.
pub const DEFAULT_SECTOR_SIZE: u32 = 4096;

/// How a block group is replicated across the one device an image is.
///
/// The format defines striped and parity profiles besides, and each of them needs more than one
/// device to read — so they are absent here rather than refused: a layout that cannot be
/// expressed cannot be asked for by mistake.
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
#[non_exhaustive]
pub enum Profile {
    /// One copy.
    #[default]
    Single,
    /// Two copies on the one device, which is what protects metadata against a bad sector.
    Dup,
}

impl Profile {
    /// How many copies of each byte the device carries.
    #[must_use]
    pub const fn copies(self) -> u64 {
        match self {
            Self::Single => 1,
            Self::Dup => 2,
        }
    }

    /// The bit the format records this profile as, or an empty set for the unreplicated one.
    #[must_use]
    pub const fn flag(self) -> BlockGroupFlags {
        match self {
            Self::Single => BlockGroupFlags::from_bits(0),
            Self::Dup => BlockGroupFlags::DUP,
        }
    }
}

// The words the format's own tooling names these two by, so a profile read off a report is one
// a caller can ask for.
crate::naming::named_choice!(Profile {
    Profile::Single => "single",
    Profile::Dup => "dup",
});

crate::naming::serialize_as_name!(Profile);

/// The size of the smallest addressable unit of file data.
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
#[non_exhaustive]
pub enum SectorSize {
    /// [`DEFAULT_SECTOR_SIZE`].
    #[default]
    Auto,
    /// Exactly this many bytes: a power of two between [`MIN_BLOCK_SIZE`] and
    /// [`MAX_BLOCK_SIZE`].
    Bytes(u32),
}

/// The size of a tree block.
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
#[non_exhaustive]
pub enum NodeSize {
    /// [`DEFAULT_NODE_SIZE`], or the sector size where that is larger.
    #[default]
    Auto,
    /// Exactly this many bytes: a power of two, at least the sector size, and at most
    /// [`MAX_BLOCK_SIZE`].
    Bytes(u32),
}

/// How much a filesystem will be given, in the counts a metadata bound is computed from.
///
/// Every field is a count of records rather than of bytes on a host, because what metadata
/// costs is records: a file of one byte and a file of one mebibyte differ by their extents and
/// their checksums, not by their inodes. [`Content::EMPTY`] is a filesystem with nothing in it
/// but its own root directory, which is what an empty image is planned from.
#[derive(Clone, Copy, PartialEq, Eq, Debug, Default)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct Content {
    /// Directories, the root of each subvolume included.
    pub directories: u64,
    /// Files, symbolic links, and device, FIFO, and socket nodes.
    pub files: u64,
    /// Names, counted across every directory. A file with two links contributes two.
    pub names: u64,
    /// The longest name any of them is, in bytes. A bound needs the worst case, not the mean.
    pub longest_name: u32,
    /// The largest single value a record must carry beside a name, in bytes.
    ///
    /// An extended attribute's value, a symbolic link's target, or a file small enough to be
    /// stored inside the metadata — whichever of them is longest. One field rather than three,
    /// because what the bound needs is the widest record any of them produces and the three
    /// produce records of the same shape.
    pub longest_value: u64,
    /// Extended attributes, counted across every object.
    pub xattrs: u64,
    /// Subvolumes beyond the one every filesystem has.
    pub subvolumes: u64,
    /// Bytes of file data that will be stored in data extents rather than inside the metadata.
    pub data_bytes: u64,
    /// Extents those bytes will be split into.
    pub data_extents: u64,
}

impl Content {
    /// A filesystem holding nothing but the root directory of its one subvolume.
    pub const EMPTY: Self = Self {
        directories: 1,
        files: 0,
        names: 0,
        longest_name: 0,
        longest_value: 0,
        xattrs: 0,
        subvolumes: 0,
        data_bytes: 0,
        data_extents: 0,
    };
}

/// How many metadata blocks a layout is allowed to consume, and how many the system chunk is.
///
/// The number is a **bound and not an estimate**. The tree that records every allocated extent
/// records its own blocks too, so its size depends on its content — a circular dependency that
/// is resolved here by reserving generously and holding the writer to it, rather than by
/// iterating to a fixpoint that might not converge. A bound that turns out too small is an
/// assertion through [`Reservation::account`]; blocks reserved and not spent are free space in
/// the finished filesystem, which is not a defect.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct Reservation {
    /// Tree blocks the metadata block groups may hold.
    pub metadata_blocks: u64,
    /// Tree blocks the system block group may hold — the chunk tree, and nothing else.
    pub system_blocks: u64,
    /// The size of each of them, which is what turns either count into bytes.
    pub node_size: u32,
}

impl Reservation {
    /// Bytes of logical space the metadata blocks occupy.
    ///
    /// Saturating, for the reason the block count itself saturates: nothing bounds the content
    /// a caller describes, and a byte count that wrapped would be smaller than the blocks it is
    /// counting. What follows a saturated number is a volume that cannot hold it.
    #[must_use]
    pub const fn metadata_bytes(&self) -> u64 {
        self.metadata_blocks.saturating_mul(self.node_size as u64)
    }

    /// Bytes of logical space the system blocks occupy.
    #[must_use]
    pub const fn system_bytes(&self) -> u64 {
        self.system_blocks.saturating_mul(self.node_size as u64)
    }

    /// Hold a finished filesystem to what was reserved for it, and report the slack.
    ///
    /// This is the other half of reserving generously: a bound nobody checks is a guess. A
    /// writer calls this once it has emitted everything, and the answer is either how many
    /// blocks it did not need or the fact that the bound was wrong.
    ///
    /// **Both pools at once**, because there are two and either can be the one that was too
    /// small. The system pool holds the chunk tree alone, which is one leaf on a small
    /// filesystem and is not on a large one: a chunk record is a hundred and twelve bytes and a
    /// volume with tens of thousands of chunks has a chunk tree of megabytes, against a system
    /// chunk of four or eight.
    ///
    /// # Errors
    ///
    /// [`ReservationExceeded`] where more blocks were spent than reserved from either pool,
    /// naming which pool and both counts. That is a defect in the bound rather than in the
    /// filesystem, and it is reported rather than absorbed because a bound that silently grows
    /// is not a bound.
    pub const fn account(
        &self,
        metadata_blocks_used: u64,
        system_blocks_used: u64,
    ) -> Result<Slack, ReservationExceeded> {
        let Some(metadata_blocks) = self.metadata_blocks.checked_sub(metadata_blocks_used) else {
            return Err(ReservationExceeded {
                pool: Pool::Metadata,
                reserved: self.metadata_blocks,
                used: metadata_blocks_used,
            });
        };
        let Some(system_blocks) = self.system_blocks.checked_sub(system_blocks_used) else {
            return Err(ReservationExceeded {
                pool: Pool::System,
                reserved: self.system_blocks,
                used: system_blocks_used,
            });
        };
        Ok(Slack {
            metadata_blocks,
            system_blocks,
        })
    }
}

/// Which of a [`Reservation`]'s two pools a count is about.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub enum Pool {
    /// Every tree but the chunk tree.
    Metadata,
    /// The chunk tree, which lives in a block group of its own so that the map can be read
    /// before the map has been read.
    System,
}

impl Pool {
    /// The name this pool is known by.
    #[must_use]
    pub const fn as_str(self) -> &'static str {
        match self {
            Self::Metadata => "metadata",
            Self::System => "system",
        }
    }
}

crate::naming::serialize_as_name!(Pool);

/// Blocks reserved and not spent, per pool.
///
/// Free space in the finished filesystem rather than waste: a driver allocates from a block
/// group's unused part exactly as it allocates from any other free space.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct Slack {
    /// Metadata blocks reserved and not spent.
    pub metadata_blocks: u64,
    /// System blocks reserved and not spent.
    pub system_blocks: u64,
}

/// A filesystem that consumed more blocks than were reserved for it, from one of the two pools.
#[derive(Clone, Copy, PartialEq, Eq, Debug, thiserror::Error)]
#[error("the {} reservation of {reserved} blocks was exceeded: {used} were spent", pool.as_str())]
#[non_exhaustive]
pub struct ReservationExceeded {
    /// Which pool ran out.
    pub pool: Pool,
    /// Blocks the planner reserved from it.
    pub reserved: u64,
    /// Blocks the writer spent from it.
    pub used: u64,
}

/// A geometry that cannot be realized.
///
/// Not [`Copy`], where every other refusal this family produces from a request is: naming the
/// features a caller asked for and cannot have costs a string, and a refusal a person reads is
/// worth more than a value a caller can duplicate without saying so.
#[derive(Clone, PartialEq, Eq, Debug, thiserror::Error)]
#[non_exhaustive]
pub enum GeometryError {
    /// The sector size is not one the format defines.
    #[error(
        "sector size {bytes} is not a power of two between {MIN_BLOCK_SIZE} and {MAX_BLOCK_SIZE}"
    )]
    #[non_exhaustive]
    SectorSizeUnsupported {
        /// The size requested, in bytes.
        bytes: u32,
    },
    /// The node size is not one the format defines, or is smaller than a sector.
    ///
    /// A tree block smaller than the unit the device addresses cannot be written atomically,
    /// which is why the floor is the sector rather than the format's own minimum.
    #[error(
        "node size {bytes} is not a power of two between the {sector_size}-byte sector and \
         {MAX_BLOCK_SIZE}"
    )]
    #[non_exhaustive]
    NodeSizeUnsupported {
        /// The size requested, in bytes.
        bytes: u32,
        /// The sector size it has to be at least as large as.
        sector_size: u32,
    },
    /// The volume is too small to hold the chunks the requested profiles need.
    ///
    /// The two ways out are a larger volume and unreplicated metadata, and the difference
    /// between the two numbers says how much either would have to change: mirroring metadata
    /// costs a fixed sixty-four mebibytes more than not mirroring it, whatever the volume.
    #[error(
        "a volume of {volume_bytes} bytes is too small: {minimum} are needed for the chunks \
         these profiles require"
    )]
    #[non_exhaustive]
    VolumeTooSmall {
        /// The volume, in bytes.
        volume_bytes: u64,
        /// The fewest bytes these profiles can be laid out in.
        minimum: u64,
    },
    /// The content will not fit in the volume it was planned for.
    ///
    /// Distinct from [`VolumeTooSmall`](Self::VolumeTooSmall), which is about the empty
    /// filesystem's own overhead: this one is reached where the volume is large enough to be
    /// formatted and too small to hold what it was told it would be given.
    #[error(
        "a volume of {volume_bytes} bytes cannot hold this content: the chunks it needs span \
         {needed} bytes"
    )]
    #[non_exhaustive]
    ContentTooLarge {
        /// The volume, in bytes.
        volume_bytes: u64,
        /// Bytes of the device the planned chunks would occupy.
        needed: u64,
    },
    /// The chunk map outgrew the one system chunk that records it.
    ///
    /// Every chunk the layout keeps is a record in the chunk tree, and the chunk tree lives in
    /// the system block group — one chunk, laid down before the content's chunks exist, whose
    /// length is fixed by the metadata profile. Content large enough needs more
    /// chunk records than that chunk's blocks can hold, and the refusal is issued here, while
    /// the map is still arithmetic, rather than discovered by a writer that has already emitted
    /// the content. Replicating metadata doubles that chunk; otherwise the way out is less
    /// content.
    #[error(
        "this content needs {chunks} chunks, whose records need {needed_blocks} tree blocks, \
         and the system chunk holds {available_blocks}"
    )]
    #[non_exhaustive]
    ChunkMapTooLarge {
        /// Chunks the layout would keep.
        chunks: u64,
        /// Tree blocks their records need.
        needed_blocks: u64,
        /// Tree blocks the system chunk holds.
        available_blocks: u64,
    },
    /// A feature was asked for that this crate does not write.
    ///
    /// The `incompat` word is the format telling a reader in advance that the on-disk form
    /// differs from what a reader without the bit expects, so writing a filesystem that claims
    /// one this crate does not implement would produce an image no reader could trust. The
    /// refusal names the bits rather than the first of them, because a caller that asked for
    /// three unsupported features should learn about three.
    ///
    /// Named as well as numbered, and both halves are load-bearing: the words are what a
    /// caller asked for and what they would have to stop asking for, and the bits cover the
    /// one a later release of the format defines and this one has no word for.
    #[error("this crate does not write {names} ({bits:#x})")]
    #[non_exhaustive]
    FeatureUnsupported {
        /// The bits of the word that have no implementation here.
        bits: u64,
        /// The same bits, named — each as the word this crate reads for it, and each the
        /// format has not defined as its position.
        names: String,
    },
    /// A feature was asked for whose own prerequisites were not.
    ///
    /// Recording block groups in a tree of their own is defined only for a filesystem that
    /// also keeps free space in a tree and records holes by their absence, so the three are
    /// asked for together or not at all. This is refused rather than quietly dropped: a
    /// filesystem built without a feature its caller named is a filesystem other than the one
    /// that was described.
    #[error("the {feature} feature also requires {requires}")]
    #[non_exhaustive]
    FeatureIncoherent {
        /// The feature that was asked for.
        feature: &'static str,
        /// What it rests on and did not get.
        requires: &'static str,
    },
}

/// Every `incompat` bit this crate writes.
///
/// Narrower than [`SUPPORTED_INCOMPAT`](super::SUPPORTED_INCOMPAT), which is what it *reads*,
/// and the two are named apart because they answer different questions: reading a filesystem
/// carrying a feature needs the feature's on-disk form to be understood, and writing one needs
/// it to be produced. A bit outside this set is [`GeometryError::FeatureUnsupported`].
pub const WRITABLE_INCOMPAT: IncompatFlags = IncompatFlags::from_bits(
    IncompatFlags::MIXED_BACKREF.bits()
        | IncompatFlags::DEFAULT_SUBVOL.bits()
        | IncompatFlags::BIG_METADATA.bits()
        | IncompatFlags::EXTENDED_IREF.bits()
        | IncompatFlags::SKINNY_METADATA.bits()
        | IncompatFlags::NO_HOLES.bits()
        | IncompatFlags::METADATA_UUID.bits(),
);

/// Every `compat_ro` bit this crate writes.
pub const WRITABLE_COMPAT_RO: CompatRoFlags = CompatRoFlags::from_bits(
    CompatRoFlags::FREE_SPACE_TREE.bits()
        | CompatRoFlags::FREE_SPACE_TREE_VALID.bits()
        | CompatRoFlags::BLOCK_GROUP_TREE.bits(),
);

/// The `incompat` word a filesystem takes where a caller names none.
///
/// `BIG_METADATA` is absent here and set by the planner instead, exactly where a node is larger
/// than four kibibytes: a consequence of the node size rather than a choice.
pub const DEFAULT_INCOMPAT: IncompatFlags = IncompatFlags::from_bits(
    IncompatFlags::MIXED_BACKREF.bits()
        | IncompatFlags::EXTENDED_IREF.bits()
        | IncompatFlags::SKINNY_METADATA.bits()
        | IncompatFlags::NO_HOLES.bits(),
);

/// The `compat_ro` word a filesystem takes where a caller names none.
pub const DEFAULT_COMPAT_RO: CompatRoFlags = WRITABLE_COMPAT_RO;

/// How metadata and system block groups are replicated where a caller names nothing.
pub const DEFAULT_METADATA_PROFILE: Profile = Profile::Dup;

/// How data block groups are replicated where a caller names nothing.
pub const DEFAULT_DATA_PROFILE: Profile = Profile::Single;

/// What a caller states about the filesystem to be planned.
///
/// Built from a volume length and refined by the methods below, each of which consumes and
/// returns the request so a call reads as one expression.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct PlanRequest {
    /// The device the filesystem will occupy the whole of, in bytes.
    pub volume_bytes: u64,
    /// The smallest addressable unit of file data.
    pub sector_size: SectorSize,
    /// The size of a tree block.
    pub node_size: NodeSize,
    /// How metadata and system block groups are replicated. One choice covers both: the
    /// format's own tooling replicates the chunk tree exactly as it replicates the rest of the
    /// metadata, and a filesystem whose chunk tree is less protected than its inodes is
    /// protected by neither.
    pub metadata_profile: Profile,
    /// How data block groups are replicated.
    pub data_profile: Profile,
    /// Features whose on-disk form a reader must understand.
    pub incompat_flags: IncompatFlags,
    /// Features a reader may ignore as long as it never writes.
    pub compat_ro_flags: CompatRoFlags,
    /// What the filesystem will be given.
    pub content: Content,
}

impl PlanRequest {
    /// A request for a volume this many bytes long, at every default.
    #[must_use]
    pub const fn new(volume_bytes: u64) -> Self {
        Self {
            volume_bytes,
            sector_size: SectorSize::Auto,
            node_size: NodeSize::Auto,
            metadata_profile: DEFAULT_METADATA_PROFILE,
            data_profile: DEFAULT_DATA_PROFILE,
            incompat_flags: DEFAULT_INCOMPAT,
            compat_ro_flags: DEFAULT_COMPAT_RO,
            content: Content::EMPTY,
        }
    }

    /// Name the sector size.
    #[must_use]
    pub const fn sector_size(mut self, size: SectorSize) -> Self {
        self.sector_size = size;
        self
    }

    /// Name the node size.
    #[must_use]
    pub const fn node_size(mut self, size: NodeSize) -> Self {
        self.node_size = size;
        self
    }

    /// Name how metadata and system block groups are replicated.
    #[must_use]
    pub const fn metadata_profile(mut self, profile: Profile) -> Self {
        self.metadata_profile = profile;
        self
    }

    /// Name how data block groups are replicated.
    #[must_use]
    pub const fn data_profile(mut self, profile: Profile) -> Self {
        self.data_profile = profile;
        self
    }

    /// Name the two feature words.
    #[must_use]
    pub const fn features(mut self, incompat: IncompatFlags, compat_ro: CompatRoFlags) -> Self {
        self.incompat_flags = incompat;
        self.compat_ro_flags = compat_ro;
        self
    }

    /// Name what the filesystem will be given.
    #[must_use]
    pub const fn content(mut self, content: Content) -> Self {
        self.content = content;
        self
    }
}

/// Everything about a filesystem that is decided before a byte of it is written.
#[derive(Clone, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize))]
#[non_exhaustive]
pub struct BtrfsLayout {
    /// The device the filesystem occupies the whole of, in bytes.
    pub volume_bytes: u64,
    /// The smallest addressable unit of file data.
    pub sector_size: u32,
    /// The size of a tree block.
    pub node_size: u32,
    /// Features whose on-disk form a reader must understand, the ones the geometry implies
    /// included.
    pub incompat_flags: IncompatFlags,
    /// Features a reader may ignore as long as it never writes.
    pub compat_ro_flags: CompatRoFlags,
    /// Every chunk, in ascending logical order, with the device offset of each copy.
    ///
    /// The same shape the reader builds its map out of, so a plan can be translated through
    /// the one address-translation path this crate has rather than through a second one.
    pub chunks: Vec<MappedChunk>,
    /// Where each superblock copy the device has room for begins, in ascending order.
    pub superblock_mirrors: Vec<u64>,
    /// How much metadata the filesystem may spend.
    pub reservation: Reservation,
}

impl BtrfsLayout {
    /// Bytes of the device the chunks occupy, every copy counted.
    ///
    /// This is what a device record's used-bytes field holds: a mirrored chunk consumes twice
    /// its length, and the unallocated spans between chunks are not counted at all.
    #[must_use]
    pub fn device_bytes_used(&self) -> u64 {
        self.chunks
            .iter()
            .map(|chunk| chunk.length * chunk.copies.len() as u64)
            .sum()
    }

    /// One past the highest logical address any chunk covers.
    #[must_use]
    pub fn logical_end(&self) -> u64 {
        self.chunks
            .last()
            .map_or(RESERVED_HEAD, MappedChunk::logical_end)
    }

    /// Every chunk holding this kind of block group, in ascending logical order.
    pub fn chunks_of(&self, kind: BlockGroupFlags) -> impl Iterator<Item = &MappedChunk> {
        self.chunks
            .iter()
            .filter(move |chunk| chunk.flags.contains(kind))
    }
}

/// Plan a filesystem.
///
/// # Errors
///
/// [`GeometryError`], for a sector or node size the format does not define, a volume too small
/// for the profiles asked of it, content too large for the volume, a feature this crate does
/// not write, or a feature asked for without what it rests on.
pub fn plan_layout(request: &PlanRequest) -> Result<BtrfsLayout, GeometryError> {
    let (sector_size, node_size) = block_sizes(request)?;
    // The device is a whole number of sectors, and a length past the last whole one is not
    // part of it. Observed: the pinned `mkfs.btrfs` records 1073741824 bytes on a file of
    // 1073742337, and its `btrfs check` warns of a length that is not sector-aligned.
    let asked = request.volume_bytes;
    let mut aligned = *request;
    aligned.volume_bytes -= asked % u64::from(sector_size);
    let request = &aligned;

    let incompat = validated_features(request, node_size)?;
    let compat_ro = request.compat_ro_flags;

    let minimum = minimum_volume_bytes(request.metadata_profile, request.data_profile);
    if request.volume_bytes < minimum {
        return Err(GeometryError::VolumeTooSmall {
            volume_bytes: asked,
            minimum,
        });
    }

    let superblock_mirrors = held_mirrors(request.volume_bytes);
    let metadata_blocks = reserve_metadata(
        request,
        sector_size,
        node_size,
        compat_ro,
        superblock_mirrors.len() as u64,
    );
    let metadata_bytes = metadata_blocks.saturating_mul(u64::from(node_size));

    // A block group loses a window to every superblock copy one of its chunks lies over, and
    // which chunk lies over one is known only once the chunks are placed. So the chunks are
    // counted, placed, and counted again with what that placement lost, until a placement
    // loses no more than it was counted with. What is counted as lost only grows from round to
    // round, and no placement loses more than two windows a copy, so the rounds end.
    let mut lost = Lost::NONE;
    let chunks = loop {
        let pending = pending_chunks(request, metadata_bytes, lost)?;
        let chunks = place_pending(&pending, request.volume_bytes);
        let placed = Lost::of(&chunks, &superblock_mirrors);
        if placed.within(lost) {
            break chunks;
        }
        lost = lost.max(placed);
    };
    let reservation = Reservation {
        metadata_blocks,
        system_blocks: reserve_system(&chunks, &superblock_mirrors, node_size)?,
        node_size,
    };

    Ok(BtrfsLayout {
        volume_bytes: request.volume_bytes,
        sector_size,
        node_size,
        incompat_flags: incompat,
        compat_ro_flags: compat_ro,
        chunks,
        superblock_mirrors,
        reservation,
    })
}

/// The sector and node sizes a request resolves to, each validated.
///
/// Separate from [`plan_layout`] because a populated format needs both **before** it has a
/// layout: which files are small enough to live inside the metadata depends on the sector, and
/// what one record may weigh depends on the node — and those decisions are what the planner is
/// then told about. Two derivations of the defaulting rule would be two rules.
///
/// # Errors
///
/// [`GeometryError::SectorSizeUnsupported`] or [`GeometryError::NodeSizeUnsupported`] for a size
/// the format does not define, or a node smaller than a sector.
pub fn block_sizes(request: &PlanRequest) -> Result<(u32, u32), GeometryError> {
    let sector_size = match request.sector_size {
        SectorSize::Auto => DEFAULT_SECTOR_SIZE,
        SectorSize::Bytes(bytes) => bytes,
    };
    if !is_block_size(sector_size) {
        return Err(GeometryError::SectorSizeUnsupported { bytes: sector_size });
    }
    let node_size = match request.node_size {
        NodeSize::Auto => DEFAULT_NODE_SIZE.max(sector_size),
        NodeSize::Bytes(bytes) => bytes,
    };
    if !is_block_size(node_size) || node_size < sector_size {
        return Err(GeometryError::NodeSizeUnsupported {
            bytes: node_size,
            sector_size,
        });
    }
    Ok((sector_size, node_size))
}

/// Whether a size is one the format accepts for a sector or a node.
const fn is_block_size(bytes: u32) -> bool {
    bytes.is_power_of_two() && bytes >= MIN_BLOCK_SIZE && bytes <= MAX_BLOCK_SIZE
}

/// The feature words a filesystem will carry, with what the geometry implies folded in.
///
/// Two things happen here that a caller cannot state. `BIG_METADATA` is set exactly where a
/// tree block exceeds four kibibytes, so it follows from the node size rather than from a
/// request. btrfs(5) states the bit against the page size; four kibibytes is where the pinned
/// baseline sets it on a host of 4 KiB pages (observed), and a rule that does not depend on the
/// host — a word written per request would be wrong
/// on the one node size where the bit does not belong and right by transcription everywhere
/// else. And a feature whose prerequisites were not asked for is refused rather than dropped.
fn validated_features(
    request: &PlanRequest,
    node_size: u32,
) -> Result<IncompatFlags, GeometryError> {
    let unsupported = request.incompat_flags.without(WRITABLE_INCOMPAT);
    if !unsupported.is_empty() {
        let mut names = String::new();
        unsupported.describe(&mut names);
        return Err(GeometryError::FeatureUnsupported {
            bits: unsupported.bits(),
            names,
        });
    }
    let unsupported_ro = request.compat_ro_flags.without(WRITABLE_COMPAT_RO);
    if !unsupported_ro.is_empty() {
        let mut names = String::new();
        unsupported_ro.describe(&mut names);
        return Err(GeometryError::FeatureUnsupported {
            bits: unsupported_ro.bits(),
            names,
        });
    }

    if request
        .compat_ro_flags
        .contains(CompatRoFlags::BLOCK_GROUP_TREE)
    {
        if !request
            .compat_ro_flags
            .contains(CompatRoFlags::FREE_SPACE_TREE)
        {
            return Err(GeometryError::FeatureIncoherent {
                feature: "block-group-tree",
                requires: "free-space-tree",
            });
        }
        if !request.incompat_flags.contains(IncompatFlags::NO_HOLES) {
            return Err(GeometryError::FeatureIncoherent {
                feature: "block-group-tree",
                requires: "no-holes",
            });
        }
    }

    // The wide-block bit is what a node size larger than four kibibytes *means* here, so it is
    // set from the geometry rather than from
    // the request. A caller that asked for it at the one node size where it does not belong
    // asked for something the format does not define, and is told so — clearing it quietly
    // would be the same silent drop this function refuses a paragraph above.
    let mut incompat = request.incompat_flags;
    if node_size > MIN_BLOCK_SIZE {
        incompat |= IncompatFlags::BIG_METADATA;
    } else if incompat.contains(IncompatFlags::BIG_METADATA) {
        return Err(GeometryError::FeatureIncoherent {
            feature: "big-metadata",
            requires: "a node larger than four kibibytes",
        });
    }
    Ok(incompat)
}

/// The fewest bytes a volume can be and still hold these profiles' chunks.
///
/// These are the pinned baseline's own bounds, observed to the byte: it formats a volume of
/// each size and refuses one a byte smaller. Holding the planner to the same four numbers
/// keeps the two in agreement about which volumes are too small, and every layout planned at
/// or above them fits its device.
///
/// | metadata | data | smallest volume |
/// |---|---|---|
/// | `Single` | `Single` | 45 MiB |
/// | `Dup` | `Single` | 109 MiB |
/// | `Single` | `Dup` | 165 MiB |
/// | `Dup` | `Dup` | 229 MiB |
///
/// Replicating metadata adds 64 MiB to the bound and replicating data adds 120 MiB, whichever
/// the other profile is.
#[must_use]
pub const fn minimum_volume_bytes(metadata: Profile, data: Profile) -> u64 {
    const MIB: u64 = 1 << 20;
    match (metadata, data) {
        (Profile::Single, Profile::Single) => 45 * MIB,
        (Profile::Dup, Profile::Single) => 109 * MIB,
        (Profile::Single, Profile::Dup) => 165 * MIB,
        (Profile::Dup, Profile::Dup) => 229 * MIB,
    }
}

/// The length of one chunk.
///
/// A chunk takes its preferred length where a tenth of the volume holds it. Where it does not,
/// the tenth is shared out between the chunk's copies, rounded down to whole stripes, and held
/// to the chunk's floor. Which preferred length and which floor depend on what the chunk holds
/// **only where it is replicated**: an unreplicated chunk of any kind prefers eight mebibytes,
/// which is why an unreplicated data chunk is eight mebibytes on a volume where a replicated
/// one is a gibibyte.
///
/// | chunk | preferred | floor |
/// |---|---|---|
/// | unreplicated, any kind | 8 MiB | one stripe |
/// | replicated system | 8 MiB | one stripe |
/// | replicated metadata | 256 MiB up to [`LARGE_VOLUME`], 1 GiB above | 32 MiB |
/// | replicated data | 1 GiB | 64 MiB |
///
/// The replicated metadata and data lengths are the block group sizes mkfs.btrfs(8) gives.
/// Every other length, both floors that are not one stripe, and the tenth are the pinned
/// baseline's, observed chunk by chunk across volumes and profiles. A floor of one stripe binds
/// only below every [`minimum_volume_bytes`], and is this crate's: a chunk is never shorter
/// than the unit its length is counted in.
#[must_use]
pub const fn chunk_length(kind: BlockGroupFlags, profile: Profile, volume_bytes: u64) -> u64 {
    let (preferred, floor) = preference(kind, profile, volume_bytes);
    let share = volume_bytes / VOLUME_SHARE;
    if preferred <= share {
        return preferred;
    }
    let shared = round_down(share / profile.copies(), STRIPE_LEN);
    if shared > floor { shared } else { floor }
}

/// A chunk's preferred length and its floor, by what it holds and how it is replicated: the
/// table [`chunk_length`] gives.
const fn preference(kind: BlockGroupFlags, profile: Profile, volume_bytes: u64) -> (u64, u64) {
    const UNREPLICATED: (u64, u64) = (8 << 20, STRIPE_LEN);
    if !matches!(profile, Profile::Dup) {
        return UNREPLICATED;
    }
    if kind.contains(BlockGroupFlags::DATA) {
        (1 << 30, 64 << 20)
    } else if kind.contains(BlockGroupFlags::METADATA) {
        let preferred = if volume_bytes > LARGE_VOLUME {
            1 << 30
        } else {
            256 << 20
        };
        (preferred, 32 << 20)
    } else {
        UNREPLICATED
    }
}

/// `value` rounded down to a whole number of `unit`s.
const fn round_down(value: u64, unit: u64) -> u64 {
    value - value % unit
}

/// One chunk to be laid down, before its address is known.
struct Pending {
    kind: BlockGroupFlags,
    profile: Profile,
    length: u64,
    /// Whether the finished filesystem keeps it. A chunk laid down to bootstrap the filesystem
    /// and replaced once its replication is known is placed — it moves both cursors — and then
    /// dropped, which is what leaves an unallocated span where it was.
    keep: bool,
}

/// Every chunk to be laid down, in the order the pinned baseline's chunks fall in (observed at
/// every pairing of profiles), before any has an address.
///
/// The metadata bound and the content's data decide how many extra chunks are appended here,
/// and `lost` is what each kind of block group gives up to superblock copies on top of that:
/// space inside a chunk that holds no block is space the content cannot be counted against.
fn pending_chunks(
    request: &PlanRequest,
    metadata_bytes: u64,
    lost: Lost,
) -> Result<Vec<Pending>, GeometryError> {
    let volume = request.volume_bytes;
    let metadata = request.metadata_profile;
    let data = request.data_profile;
    let keeps_bootstrap_metadata = matches!(metadata, Profile::Single);
    let keeps_bootstrap_data = matches!(data, Profile::Single);

    let system = BlockGroupFlags::SYSTEM;
    let meta = BlockGroupFlags::METADATA;
    let dat = BlockGroupFlags::DATA;

    let mut pending = Vec::new();
    // First one unreplicated chunk of each kind. Those of a replicated kind are dropped once
    // placed, which leaves the spans the baseline leaves.
    pending.push(Pending {
        kind: system,
        profile: Profile::Single,
        length: BOOTSTRAP_SYSTEM_CHUNK,
        keep: keeps_bootstrap_metadata,
    });
    pending.push(Pending {
        kind: meta,
        profile: Profile::Single,
        length: chunk_length(meta, Profile::Single, volume),
        keep: keeps_bootstrap_metadata,
    });
    pending.push(Pending {
        kind: dat,
        profile: Profile::Single,
        length: chunk_length(dat, Profile::Single, volume),
        keep: keeps_bootstrap_data,
    });
    // Then the replicated ones, for whichever of the two kinds asked for replication. Each
    // replaces the bootstrap chunk of its kind rather than joining it.
    if !keeps_bootstrap_metadata {
        pending.push(Pending {
            kind: system,
            profile: metadata,
            length: chunk_length(system, metadata, volume),
            keep: true,
        });
        pending.push(Pending {
            kind: meta,
            profile: metadata,
            length: chunk_length(meta, metadata, volume),
            keep: true,
        });
    }
    if !keeps_bootstrap_data {
        pending.push(Pending {
            kind: dat,
            profile: data,
            length: chunk_length(dat, data, volume),
            keep: true,
        });
    }

    // What the content needs beyond the one chunk of each kind laid down above. An empty
    // filesystem needs none of it, which is what makes its layout the baseline's exactly.
    //
    // How many are needed is worked out as arithmetic and the device space they would take is
    // checked **before** any of them exists. Doing it the other way — appending chunks and
    // measuring afterwards — means a caller who names more content than any device could hold
    // gets an answer only after the planner has tried to build a chunk for every gibibyte of
    // it, and the refusal it was owed is a computation that does not end.
    let held = |kind: BlockGroupFlags| -> u64 {
        pending
            .iter()
            .filter(|entry| entry.keep && entry.kind.contains(kind))
            .map(|entry| entry.length)
            .sum()
    };
    let metadata_each = chunk_length(meta, metadata, volume);
    let extra_metadata = shortfall(
        metadata_bytes.saturating_add(lost.metadata),
        held(meta),
        metadata_each,
    );
    let data_each = chunk_length(dat, data, volume);
    let extra_data = shortfall(
        request.content.data_bytes.saturating_add(lost.data),
        held(dat),
        data_each,
    );

    let placed: u64 = pending
        .iter()
        .map(|entry| entry.length * entry.profile.copies())
        .sum();
    let needed = extra_metadata
        .checked_mul(metadata_each * metadata.copies())
        .and_then(|bytes| bytes.checked_add(extra_data.checked_mul(data_each * data.copies())?))
        .and_then(|bytes| bytes.checked_add(placed + RESERVED_HEAD));
    match needed {
        Some(needed) if needed <= volume => {}
        // An overflow is the same answer as a span past the end of the device, and saying so
        // needs a number: the volume is what the content did not fit in either way.
        _ => {
            return Err(GeometryError::ContentTooLarge {
                volume_bytes: volume,
                needed: needed.unwrap_or(u64::MAX),
            });
        }
    }

    for (count, kind, profile, length) in [
        (extra_metadata, meta, metadata, metadata_each),
        (extra_data, dat, data, data_each),
    ] {
        for _ in 0..count {
            pending.push(Pending {
                kind,
                profile,
                length,
                keep: true,
            });
        }
    }
    Ok(pending)
}

/// Lay every pending chunk out, advancing the logical and device cursors together.
fn place_pending(pending: &[Pending], volume: u64) -> Vec<MappedChunk> {
    let mut chunks = Vec::with_capacity(pending.len());
    let mut logical = RESERVED_HEAD;
    let mut physical = RESERVED_HEAD;
    for entry in pending {
        let copies = entry.profile.copies();
        if entry.keep {
            chunks.push(MappedChunk {
                logical,
                length: entry.length,
                flags: entry.kind | entry.profile.flag(),
                copies: (0..copies).map(|n| physical + n * entry.length).collect(),
            });
        }
        logical += entry.length;
        physical += entry.length * copies;
    }
    debug_assert!(
        physical <= volume,
        "the span was checked before it was placed"
    );
    chunks
}

/// How many chunks of `each` bytes it takes to cover what `held` leaves of `needed`.
///
/// Zero where what is held already covers it, which is every empty filesystem.
const fn shortfall(needed: u64, held: u64, each: u64) -> u64 {
    match needed.checked_sub(held) {
        Some(0) | None => 0,
        Some(short) => short.div_ceil(each),
    }
}

/// How much of a block group is left unallocated where a copy of its chunk lies over a
/// superblock copy: one stripe length.
pub(crate) const MIRROR_WINDOW: u64 = STRIPE_LEN;

/// Every superblock copy a device this long holds, in ascending order.
fn held_mirrors(volume_bytes: u64) -> Vec<u64> {
    MIRRORS
        .iter()
        .copied()
        .filter(|&at| holds_mirror(volume_bytes, at))
        .collect()
}

/// Where in `chunk` no block may be allocated: the logical address each window begins at,
/// ascending, each [`STRIPE_LEN`] long.
///
/// A superblock copy sits at a fixed offset on the device whatever chunk covers it, so a chunk
/// whose copy lies over one cannot hand out the logical addresses that map there: the superblock
/// is written over whatever block holds them. A mirrored chunk has a window wherever **either**
/// of its copies lies over a superblock copy, since every block is written to both.
///
/// The window is the stripe the superblock copy falls in, measured from the start of the
/// chunk's copy. That is what the pinned baseline leaves unallocated, in metadata and data block
/// groups alike, and it records the window as free space. It is observed rather than
/// documented: the format's documentation places the superblock copies on the device and says
/// nothing of a chunk that covers one. A chunk is a whole number of stripes long, so a window
/// never runs past the chunk's end. Every copy this planner places starts on a stripe boundary
/// of the device, so the stripe measured from the copy's start is also the device's.
pub(crate) fn mirror_windows(chunk: &MappedChunk, mirrors: &[u64]) -> Vec<u64> {
    let mut windows = Vec::new();
    for &copy in &chunk.copies {
        let copy_end = copy + chunk.length;
        for &at in mirrors {
            let end = at + SUPER_INFO_SIZE as u64;
            if end <= copy || at >= copy_end {
                continue;
            }
            let first = (at.max(copy) - copy) / MIRROR_WINDOW;
            let last = (end.min(copy_end) - 1 - copy) / MIRROR_WINDOW;
            windows.extend((first..=last).map(|stripe| chunk.logical + stripe * MIRROR_WINDOW));
        }
    }
    windows.sort_unstable();
    windows.dedup();
    windows
}

/// Bytes of `chunk` its mirror windows take.
fn window_bytes(chunk: &MappedChunk, mirrors: &[u64]) -> u64 {
    mirror_windows(chunk, mirrors).len() as u64 * MIRROR_WINDOW
}

/// Bytes each kind of block group gives up to superblock copies.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
struct Lost {
    metadata: u64,
    data: u64,
}

impl Lost {
    const NONE: Self = Self {
        metadata: 0,
        data: 0,
    };

    /// What these chunks give up to these superblock copies.
    fn of(chunks: &[MappedChunk], mirrors: &[u64]) -> Self {
        let lost = |kind: BlockGroupFlags| -> u64 {
            chunks
                .iter()
                .filter(|chunk| chunk.flags.contains(kind))
                .map(|chunk| window_bytes(chunk, mirrors))
                .sum()
        };
        Self {
            metadata: lost(BlockGroupFlags::METADATA),
            data: lost(BlockGroupFlags::DATA),
        }
    }

    /// Whether this loses no more of either kind than `counted` allowed for.
    const fn within(self, counted: Self) -> bool {
        self.metadata <= counted.metadata && self.data <= counted.data
    }

    /// The larger loss of each kind.
    fn max(self, other: Self) -> Self {
        Self {
            metadata: self.metadata.max(other.metadata),
            data: self.data.max(other.data),
        }
    }
}

// ---------------------------------------------------------------------------
// The metadata bound
//
// Every tree is bounded the same way: count the records it will hold and the largest each can
// be, divide into leaves, and add the internal nodes above them. The extent tree is the one
// exception and it has a section of its own below.

/// Records of `record_bytes` each, in blocks of `node_size`, leaves and internal nodes both.
fn blocks_for(records: u64, record_bytes: u64, node_size: u32) -> u64 {
    if records == 0 {
        // A tree with nothing in it is still a tree: it has a root, and the root is a block.
        return 1;
    }
    let capacity = u64::from(node_size) - Header::SIZE as u64;
    let per_leaf = (capacity / (Item::SIZE as u64 + record_bytes)).max(1);
    let leaves = records.div_ceil(per_leaf);
    levels_above(leaves, capacity / KeyPtr::SIZE as u64)
        .iter()
        .fold(leaves, |blocks, level| blocks.saturating_add(*level))
}

/// How many metadata blocks the filesystem may spend — every tree but the chunk tree, whose
/// pool is [`reserve_system`]'s.
///
/// The counts below are bounds rather than predictions, and each names the records it is
/// counting. Two of them are worth reading twice: the fs tree, because a name appears in three
/// records and a bound that counted it once would be short on every directory; and the extent
/// tree, because it records its own blocks.
///
/// Every sum here saturates. A count a caller states is a `u64` and nothing bounds one, so an
/// absurd content description has to produce an absurd bound rather than a wrapped one — a
/// bound that wrapped would be *small*, which is the one way a reservation can be wrong that
/// nothing downstream would notice until a writer had run out of room. What follows a saturated
/// bound is a volume that cannot hold it, which is a typed refusal.
///
/// `mirrors` is how many superblock copies the device holds. A data extent that reaches the
/// window a block group leaves around one is split there, so each copy can add one extent to
/// the content's own count, wherever the chunks turn out to be placed.
fn reserve_metadata(
    request: &PlanRequest,
    sector_size: u32,
    node_size: u32,
    compat_ro: CompatRoFlags,
    mirrors: u64,
) -> u64 {
    let content = &request.content;
    let name_bytes = u64::from(content.longest_name);
    let subvolumes = content.subvolumes.saturating_add(1);
    let data_extents = content.data_extents.saturating_add(mirrors);

    // The root tree: a record naming every tree, plus the directory that names the subvolumes.
    // Six trees are always there — the extent, device, filesystem, checksum, uuid, and data
    // relocation trees — and the two that follow are the ones a feature bit adds. A subvolume
    // costs three records rather than one: its own root record, the name the root directory
    // holds for it, and the position that name sits at.
    let trees = 6
        + u64::from(compat_ro.contains(CompatRoFlags::FREE_SPACE_TREE))
        + u64::from(compat_ro.contains(CompatRoFlags::BLOCK_GROUP_TREE));
    // Four more: the root tree has a directory of its own, whose inode, name for its parent, and
    // entry naming the default subvolume are three records, and the top-level subvolume's
    // reference back to it is a fourth.
    let root_records = trees
        .saturating_add(subvolumes.saturating_mul(3))
        .saturating_add(4);
    let root_tree = blocks_for(root_records, RootItem::SIZE as u64, node_size);

    // Every filesystem tree together. An object costs one inode record, and each of its names
    // costs three: the reference the inode carries, a record keyed by the name's hash for
    // lookup, and a record keyed by its position for reading a directory in order. A bound that
    // charged a name once would be short by two thirds on every directory, and short is the
    // direction that fails.
    //
    // Each object is charged **twice**, because a file's bytes are a record of their own wherever
    // they are small enough to live in the metadata — and so is a symbolic link's target, always.
    // Neither is in `data_extents`, which counts only what reaches a data block group, so a tree
    // of small files holds a record in five that counting once does not reach. What has kept
    // that from mattering is the size each record is charged at, which is the widest any of them
    // can be and is several times what an inode record actually weighs — a bound short in its
    // *count* and long in its *size* still holds, until a tree turns up where the sizes are even.
    // Counting what is there is the bound the derivation was supposed to be.
    let fs_records = content
        .directories
        .saturating_add(content.files.saturating_mul(2))
        .saturating_add(content.names.saturating_mul(3))
        .saturating_add(content.xattrs)
        .saturating_add(data_extents);
    let fs_trees = blocks_for(
        fs_records,
        (InodeItem::SIZE as u64)
            .max(InodeRef::SIZE as u64 + name_bytes)
            .max(DirItem::SIZE as u64 + name_bytes + content.longest_value),
        node_size,
    )
    .saturating_add(subvolumes);

    // The checksum tree: four bytes for every sector of data, packed into as few records as the
    // leaves will hold.
    let csum_bytes = content
        .data_bytes
        .div_ceil(u64::from(sector_size))
        .saturating_mul(CSUM_BYTES_PER_SECTOR);
    let csum_tree = blocks_for(
        csum_bytes.div_ceil(MAX_CSUM_RECORD),
        MAX_CSUM_RECORD,
        node_size,
    );

    // The device tree, the block-group tree, the free-space tree, and the uuid tree are each
    // bounded by the chunk count or the subvolume count, both small.
    let small_trees =
        (3 * blocks_for(64, 64, node_size)).saturating_add(blocks_for(subvolumes, 32, node_size));

    let outside_extent_tree = root_tree
        .saturating_add(fs_trees)
        .saturating_add(csum_tree)
        .saturating_add(small_trees);

    // The extent tree records every allocated extent, its own blocks included, so its size
    // depends on its content. There is no fixpoint to iterate towards: if the rest of the
    // metadata is `outside` blocks and one leaf holds `per_leaf` records, a tree of `e` blocks
    // must record `outside + e` extents, so `e >= outside / (per_leaf - 1)` and the smallest
    // bound is that quotient rounded up. Charging each extent twice covers its back-reference.
    let capacity = u64::from(node_size) - Header::SIZE as u64;
    let per_leaf = (capacity / (Item::SIZE as u64 + EXTENT_RECORD_BYTES)).max(2);
    let outside_records = outside_extent_tree
        .saturating_add(data_extents)
        .saturating_mul(2);
    let extent_tree = blocks_for(
        outside_records.saturating_add(outside_records.div_ceil(per_leaf - 1)),
        EXTENT_RECORD_BYTES,
        node_size,
    );

    let total = outside_extent_tree.saturating_add(extent_tree);
    // The bound is deliberately loose rather than exact, which is what makes it a bound: the
    // margin covers a tree gaining a level from an unlucky split and the extent records the
    // extent tree's own internal nodes need. Blocks reserved and not spent are free space.
    total.saturating_add(total / 8).saturating_add(8)
}

/// How many system blocks the filesystem may spend — the chunk tree, and nothing else.
///
/// Derived from the chunks actually planned rather than fixed: the chunk tree holds one record
/// per kept chunk plus the device record, and the extra data chunks a populated filesystem
/// appends grow that count with the content. A bound fixed here would be the one kind of bound
/// that fails exactly when the content is large — after every block of it has been written.
///
/// The bound is also checked against the system chunk's own capacity, less any window a
/// superblock copy takes from it, while the map is still arithmetic. That chunk's length is
/// fixed by the metadata profile rather than by the content, so a chunk map that
/// outgrows it is refused as [`GeometryError::ChunkMapTooLarge`] here rather than surfacing from
/// the writer as an exceeded reservation.
fn reserve_system(
    chunks: &[MappedChunk],
    mirrors: &[u64],
    node_size: u32,
) -> Result<u64, GeometryError> {
    // One record per chunk and one for the device, each charged at the widest record the chunk
    // tree will hold: a chunk record is a fixed head plus one stripe per copy.
    let count = chunks.len() as u64;
    let record_bytes = chunks
        .iter()
        .map(|chunk| Chunk::SIZE as u64 + chunk.copies.len() as u64 * Stripe::SIZE as u64)
        .max()
        .unwrap_or(Chunk::SIZE as u64)
        .max(DevItem::SIZE as u64);
    let needed_blocks = blocks_for(count.saturating_add(1), record_bytes, node_size);

    let available_blocks = chunks
        .iter()
        .find(|chunk| chunk.flags.contains(BlockGroupFlags::SYSTEM))
        .map_or(0, |chunk| {
            (chunk.length - window_bytes(chunk, mirrors)) / u64::from(node_size)
        });
    if needed_blocks > available_blocks {
        return Err(GeometryError::ChunkMapTooLarge {
            chunks: count,
            needed_blocks,
            available_blocks,
        });
    }
    Ok(needed_blocks)
}

/// Bytes of checksum a sector of data costs.
///
/// Read off the algorithm rather than written down, so a filesystem checksummed some other way
/// moves this number by moving the algorithm.
pub(crate) const CSUM_BYTES_PER_SECTOR: u64 =
    ChecksumType::CRC32C.digest_len().expect("crc32c has one") as u64;

/// The largest checksum record the writer emits, in bytes of checksum.
///
/// Checksums for consecutive sectors pack into one record, and a record is capped so that a leaf
/// holds more than one of them — at the smallest tree block the format defines, which is what
/// makes this a constant rather than a function of the node size. It is the writer's cap as well
/// as the bound's, so the reservation counts the records that are actually emitted.
pub(crate) const MAX_CSUM_RECORD: u64 = 2048;

/// The bytes an extent record and its back-reference occupy together.
const EXTENT_RECORD_BYTES: u64 = 64;

#[cfg(test)]
mod tests {
    use super::*;

    const GIB: u64 = 1 << 30;
    const MIB: u64 = 1 << 20;

    /// The layout the pinned baseline writes to a one-gibibyte volume at its own defaults, read
    /// out of such an image. Every number here is a measurement rather than a derivation, which
    /// is what makes it worth asserting a derivation against.
    const BASELINE_1G_DEFAULT: &[(u64, u64, &[u64])] = &[
        (13_631_488, 8_388_608, &[13_631_488]),
        (22_020_096, 8_388_608, &[22_020_096, 30_408_704]),
        (30_408_704, 53_673_984, &[38_797_312, 92_471_296]),
    ];

    /// The same volume with nothing replicated, where the chunks laid down to bootstrap the
    /// filesystem are the ones it keeps.
    const BASELINE_1G_SINGLE: &[(u64, u64, &[u64])] = &[
        (1_048_576, 4_194_304, &[1_048_576]),
        (5_242_880, 8_388_608, &[5_242_880]),
        (13_631_488, 8_388_608, &[13_631_488]),
    ];

    fn shape(layout: &BtrfsLayout) -> Vec<(u64, u64, Vec<u64>)> {
        layout
            .chunks
            .iter()
            .map(|chunk| (chunk.logical, chunk.length, chunk.copies.clone()))
            .collect()
    }

    fn expected(rows: &[(u64, u64, &[u64])]) -> Vec<(u64, u64, Vec<u64>)> {
        rows.iter()
            .map(|&(logical, length, copies)| (logical, length, copies.to_vec()))
            .collect()
    }

    #[test]
    fn a_default_volume_is_laid_out_the_way_the_baseline_lays_one_out() {
        let layout = plan_layout(&PlanRequest::new(GIB)).expect("a gibibyte is formattable");
        assert_eq!(shape(&layout), expected(BASELINE_1G_DEFAULT));
        // What a device record's used-bytes field holds: every copy of every chunk, and none of
        // the unallocated space between them.
        assert_eq!(layout.device_bytes_used(), 132_513_792);
    }

    #[test]
    fn nothing_replicated_keeps_the_chunks_the_bootstrap_laid_down() {
        let layout = plan_layout(
            &PlanRequest::new(GIB)
                .metadata_profile(Profile::Single)
                .data_profile(Profile::Single),
        )
        .expect("a gibibyte is formattable");
        assert_eq!(shape(&layout), expected(BASELINE_1G_SINGLE));
        assert_eq!(layout.device_bytes_used(), 20_971_520);
        // Nothing was replaced, so the first chunk begins where the reserved head ends and
        // there is no unallocated span at all.
        assert_eq!(layout.chunks[0].logical, RESERVED_HEAD);
    }

    #[test]
    fn replicating_metadata_leaves_the_span_the_replaced_chunks_occupied() {
        let layout = plan_layout(&PlanRequest::new(GIB)).expect("a gibibyte is formattable");
        let first = layout.chunks[0].logical;
        // The reserved head, the bootstrap system chunk, and the bootstrap metadata chunk: the
        // last of those is replaced, and the span it held stays unallocated.
        assert_eq!(
            first,
            RESERVED_HEAD
                + BOOTSTRAP_SYSTEM_CHUNK
                + chunk_length(BlockGroupFlags::METADATA, Profile::Single, GIB,)
        );
        assert!(first > RESERVED_HEAD);
    }

    #[test]
    fn an_unreplicated_chunk_takes_the_generic_rule_whatever_it_holds() {
        // The one genuinely surprising rule in the allocator: the per-kind preference applies
        // only to a replicated chunk. An unreplicated data chunk is eight mebibytes on a volume
        // where a replicated one is a gibibyte, and reading the per-kind rule as though it
        // applied to both would size it a hundred and twenty-eight times too large.
        let volume = 64 * GIB;
        assert_eq!(
            chunk_length(BlockGroupFlags::DATA, Profile::Single, volume),
            8 * MIB
        );
        assert_eq!(
            chunk_length(BlockGroupFlags::DATA, Profile::Dup, volume),
            GIB
        );
    }

    #[test]
    fn a_replicated_metadata_chunk_reaches_a_gibibyte_only_past_the_volume_that_earns_it() {
        let kind = BlockGroupFlags::METADATA;
        // The threshold is a strict comparison, as mkfs.btrfs(8)'s "larger than 50GiB" reads: a
        // volume of exactly fifty gibibytes takes the lower preferred length (observed) and one
        // byte more takes the higher. A tenth of either volume holds the preferred length, so the
        // step between them is the whole of the difference.
        assert_eq!(chunk_length(kind, Profile::Dup, LARGE_VOLUME), 256 * MIB);
        assert_eq!(chunk_length(kind, Profile::Dup, LARGE_VOLUME + 1), GIB);
        // A tenth of a hundred gibibytes is ten of them, which holds the preferred gibibyte.
        assert_eq!(chunk_length(kind, Profile::Dup, 100 * GIB), GIB);
    }

    #[test]
    fn below_every_minimum_a_chunk_is_never_shorter_than_one_stripe() {
        // Outside the volumes the planner accepts, and so this crate's choice rather than an
        // observation: no baseline formats a volume this small to be compared with.
        for volume in [0, 1, STRIPE_LEN, MIB, 10 * MIB] {
            for kind in [BlockGroupFlags::SYSTEM, BlockGroupFlags::METADATA] {
                for profile in [Profile::Single, Profile::Dup] {
                    let length = chunk_length(kind, profile, volume);
                    assert!(length >= STRIPE_LEN, "{kind:?} {profile:?} on {volume}");
                    assert_eq!(length % STRIPE_LEN, 0);
                }
            }
        }
        assert_eq!(
            chunk_length(BlockGroupFlags::SYSTEM, Profile::Single, 0),
            STRIPE_LEN
        );
    }

    #[test]
    fn no_chunk_takes_more_than_its_share_of_the_volume_once_the_volume_can_afford_a_floor() {
        for volume in [GIB, 4 * GIB, 40 * GIB, 400 * GIB, 4000 * GIB] {
            for kind in [
                BlockGroupFlags::DATA,
                BlockGroupFlags::METADATA,
                BlockGroupFlags::SYSTEM,
            ] {
                for profile in [Profile::Single, Profile::Dup] {
                    let length = chunk_length(kind, profile, volume);
                    assert!(
                        length <= volume / VOLUME_SHARE,
                        "{kind:?} {profile:?} on {volume}: {length}"
                    );
                    assert_eq!(length % STRIPE_LEN, 0, "{kind:?} {profile:?} on {volume}");
                }
            }
        }
    }

    #[test]
    fn the_two_address_spaces_advance_by_different_amounts_and_neither_overlaps() {
        for volume in [110 * MIB, 256 * MIB, GIB, 17 * GIB, 300 * GIB] {
            for metadata in [Profile::Single, Profile::Dup] {
                for data in [Profile::Single, Profile::Dup] {
                    if volume < minimum_volume_bytes(metadata, data) {
                        continue;
                    }
                    let layout = plan_layout(
                        &PlanRequest::new(volume)
                            .metadata_profile(metadata)
                            .data_profile(data),
                    )
                    .expect("a volume past the minimum");
                    let mut logical = RESERVED_HEAD;
                    let mut physical = RESERVED_HEAD;
                    for chunk in &layout.chunks {
                        assert!(chunk.logical >= logical, "{volume} {metadata:?} {data:?}");
                        assert!(chunk.copies[0] >= physical);
                        for pair in chunk.copies.windows(2) {
                            assert_eq!(pair[1] - pair[0], chunk.length, "copies are adjacent");
                        }
                        logical = chunk.logical_end();
                        physical = chunk.copies[chunk.copies.len() - 1] + chunk.length;
                        assert!(physical <= volume, "a copy is placed past the device");
                    }
                }
            }
        }
    }

    #[test]
    fn a_volume_too_small_for_its_profiles_is_refused_with_the_size_that_would_do() {
        // The four minima, measured against the pinned baseline: it accepts each of these to the
        // byte and refuses a mebibyte less.
        for (metadata, data, minimum) in [
            (Profile::Single, Profile::Single, 45 * MIB),
            (Profile::Dup, Profile::Single, 109 * MIB),
            (Profile::Single, Profile::Dup, 165 * MIB),
            (Profile::Dup, Profile::Dup, 229 * MIB),
        ] {
            assert_eq!(minimum_volume_bytes(metadata, data), minimum);
            let request = PlanRequest::new(minimum - 1)
                .metadata_profile(metadata)
                .data_profile(data);
            assert_eq!(
                plan_layout(&request),
                Err(GeometryError::VolumeTooSmall {
                    volume_bytes: minimum - 1,
                    minimum,
                })
            );
            let request = PlanRequest::new(minimum)
                .metadata_profile(metadata)
                .data_profile(data);
            assert!(plan_layout(&request).is_ok(), "{metadata:?} {data:?}");
        }
    }

    #[test]
    fn a_sector_or_node_size_the_format_does_not_define_is_refused() {
        for bytes in [0, 1, 512, 2048, 6144, 128 << 10] {
            assert_eq!(
                plan_layout(&PlanRequest::new(GIB).sector_size(SectorSize::Bytes(bytes))),
                Err(GeometryError::SectorSizeUnsupported { bytes })
            );
        }
        for bytes in [512, 2048, 24576, 128 << 10] {
            assert_eq!(
                plan_layout(&PlanRequest::new(GIB).node_size(NodeSize::Bytes(bytes))),
                Err(GeometryError::NodeSizeUnsupported {
                    bytes,
                    sector_size: DEFAULT_SECTOR_SIZE,
                })
            );
        }
        // A node smaller than the sector cannot be written atomically, whatever the format says
        // about the size on its own.
        assert_eq!(
            plan_layout(
                &PlanRequest::new(GIB)
                    .sector_size(SectorSize::Bytes(16384))
                    .node_size(NodeSize::Bytes(4096))
            ),
            Err(GeometryError::NodeSizeUnsupported {
                bytes: 4096,
                sector_size: 16384,
            })
        );
    }

    #[test]
    fn a_node_takes_the_sector_size_where_that_is_the_larger_of_the_two() {
        for (sector, node) in [
            (4096, 16384),
            (16384, 16384),
            (32768, 32768),
            (65536, 65536),
        ] {
            let layout = plan_layout(&PlanRequest::new(GIB).sector_size(SectorSize::Bytes(sector)))
                .expect("a gibibyte is formattable");
            assert_eq!(layout.node_size, node, "sector {sector}");
        }
    }

    #[test]
    fn a_feature_this_crate_does_not_write_is_refused_naming_every_bit_at_once() {
        let asked = DEFAULT_INCOMPAT | IncompatFlags::ZONED | IncompatFlags::RAID56;
        assert_eq!(
            plan_layout(&PlanRequest::new(GIB).features(asked, DEFAULT_COMPAT_RO)),
            Err(GeometryError::FeatureUnsupported {
                bits: IncompatFlags::ZONED.bits() | IncompatFlags::RAID56.bits(),
                // In the words `format -O` takes, so a caller told a feature cannot be
                // written is told it in the word they asked for it by.
                names: "raid56, zoned".to_string(),
            })
        );
    }

    #[test]
    fn a_feature_asked_for_without_what_it_rests_on_is_refused_rather_than_dropped() {
        // The baseline drops the feature, says so on the standard error, and exits zero — so a
        // caller that asked for it gets a filesystem other than the one it described and no
        // failure to notice. Refusing is the difference.
        let ro = CompatRoFlags::BLOCK_GROUP_TREE;
        assert_eq!(
            plan_layout(&PlanRequest::new(GIB).features(DEFAULT_INCOMPAT, ro)),
            Err(GeometryError::FeatureIncoherent {
                feature: "block-group-tree",
                requires: "free-space-tree",
            })
        );
        let ro = CompatRoFlags::BLOCK_GROUP_TREE | CompatRoFlags::FREE_SPACE_TREE;
        assert_eq!(
            plan_layout(
                &PlanRequest::new(GIB)
                    .features(DEFAULT_INCOMPAT.without(IncompatFlags::NO_HOLES), ro)
            ),
            Err(GeometryError::FeatureIncoherent {
                feature: "block-group-tree",
                requires: "no-holes",
            })
        );
    }

    #[test]
    fn asking_for_wide_blocks_at_a_four_kilobyte_node_is_refused_rather_than_cleared() {
        // The bit *is* the node size being larger, so asking for both at once asks for
        // something the format does not define. Clearing it quietly would be the silent drop
        // this crate refuses the baseline for.
        let asked = DEFAULT_INCOMPAT | IncompatFlags::BIG_METADATA;
        assert_eq!(
            plan_layout(
                &PlanRequest::new(GIB)
                    .node_size(NodeSize::Bytes(4096))
                    .features(asked, DEFAULT_COMPAT_RO)
            ),
            Err(GeometryError::FeatureIncoherent {
                feature: "big-metadata",
                requires: "a node larger than four kibibytes",
            })
        );
    }

    #[test]
    fn big_metadata_is_set_exactly_where_a_tree_block_exceeds_four_kibibytes() {
        for (sector, node, set) in [
            (4096u32, 4096u32, false),
            (4096, 16384, true),
            (4096, 8192, true),
            (65536, 65536, true),
        ] {
            let layout = plan_layout(
                &PlanRequest::new(GIB)
                    .sector_size(SectorSize::Bytes(sector))
                    .node_size(NodeSize::Bytes(node)),
            )
            .expect("a gibibyte is formattable");
            assert_eq!(
                layout.incompat_flags.contains(IncompatFlags::BIG_METADATA),
                set,
                "sector {sector} node {node}"
            );
        }
    }

    #[test]
    fn a_volume_is_planned_with_every_superblock_location_it_has_room_for() {
        // The boundary at each location is that offset plus a whole superblock, so a volume of
        // exactly the location's own size carries one fewer than a volume a superblock longer.
        // The two smallest volumes here are below what replicated metadata can be laid out in,
        // which is why they are planned unreplicated: the count is a property of the device's
        // length and of nothing else, so any layout that fits proves it.
        for (volume, expected) in [
            ((64 << 20) - 1, 1),
            (64 << 20, 1),
            ((64 << 20) + 4096, 2),
            (GIB, 2),
            (256 << 30, 2),
            ((256 << 30) + 4096, 3),
        ] {
            let request = PlanRequest::new(volume)
                .metadata_profile(Profile::Single)
                .data_profile(Profile::Single);
            let layout = plan_layout(&request).expect("past the minimum");
            assert_eq!(
                layout.superblock_mirrors.len(),
                expected,
                "a volume of {volume} bytes"
            );
            assert_eq!(layout.superblock_mirrors[0], MIRRORS[0]);
        }
    }

    #[test]
    fn an_empty_filesystem_is_reserved_more_metadata_than_one_costs() {
        // The pinned baseline spends nine tree blocks on an empty filesystem at a sixteen-
        // kibibyte node and eleven at a four-kibibyte one, the root tree having gained a level.
        // A bound below either would be a bound that is wrong on the simplest filesystem there
        // is.
        for (node, spent) in [(4096u32, 11u64), (16384, 9), (65536, 9)] {
            let layout = plan_layout(&PlanRequest::new(GIB).node_size(NodeSize::Bytes(node)))
                .expect("a gibibyte is formattable");
            assert!(
                layout.reservation.metadata_blocks >= spent,
                "node {node}: reserved {}, the baseline spends {spent}",
                layout.reservation.metadata_blocks
            );
            assert_eq!(layout.reservation.node_size, node);
            assert!(layout.reservation.system_blocks >= 1);
        }
    }

    #[test]
    fn the_reservation_always_fits_the_metadata_chunks_planned_for_it() {
        for volume in [110 * MIB, GIB, 17 * GIB, 300 * GIB] {
            for content in [
                Content::EMPTY,
                Content {
                    directories: 4_000,
                    files: 40_000,
                    names: 44_000,
                    longest_name: 255,
                    xattrs: 8_000,
                    subvolumes: 3,
                    data_bytes: 64 * MIB,
                    data_extents: 900,
                    ..Content::EMPTY
                },
            ] {
                let Ok(layout) = plan_layout(&PlanRequest::new(volume).content(content)) else {
                    continue;
                };
                // What the chunks can hold, which is their length less any window a superblock
                // copy takes from one of them.
                let planned: u64 = layout
                    .chunks_of(BlockGroupFlags::METADATA)
                    .map(|chunk| chunk.length - window_bytes(chunk, &layout.superblock_mirrors))
                    .sum();
                assert!(
                    planned >= layout.reservation.metadata_bytes(),
                    "a volume of {volume} bytes reserves more metadata than it plans room for"
                );
            }
        }
    }

    #[test]
    fn a_window_is_the_stripe_a_superblock_copy_falls_in_through_either_copy_of_a_chunk() {
        let chunk = |logical: u64, length: u64, copies: &[u64]| MappedChunk {
            logical,
            length,
            flags: BlockGroupFlags::METADATA | BlockGroupFlags::DUP,
            copies: copies.to_vec(),
        };
        // The first mirrored metadata chunk of a default one-gibibyte volume: its first copy
        // begins at thirty-seven mebibytes, so the copy at sixty-four is twenty-seven in.
        let first = chunk(30_408_704, 53_673_984, &[38_797_312, 92_471_296]);
        assert_eq!(
            mirror_windows(&first, &MIRRORS),
            [30_408_704 + (64 * MIB - 38_797_312)]
        );
        // The same chunk with its copies the other way round: the window is where the copy that
        // covers the superblock copy maps it, whichever copy that is.
        let second = chunk(30_408_704, 53_673_984, &[92_471_296, 38_797_312]);
        assert_eq!(
            mirror_windows(&second, &MIRRORS),
            mirror_windows(&first, &MIRRORS)
        );
        // A superblock copy the device does not hold takes nothing.
        assert!(mirror_windows(&first, &MIRRORS[..1]).is_empty());
        // A copy that begins exactly at the superblock copy has its window at its start, and one
        // that ends exactly there has none.
        let at = chunk(5 * MIB, 8 * MIB, &[64 * MIB]);
        assert_eq!(mirror_windows(&at, &MIRRORS), [5 * MIB]);
        let before = chunk(5 * MIB, 8 * MIB, &[56 * MIB]);
        assert!(mirror_windows(&before, &MIRRORS).is_empty());
        // A copy that does not begin on a stripe boundary still windows the stripe of the copy
        // that holds the superblock copy, measured from the copy's own start.
        let ragged = chunk(5 * MIB, 8 * MIB, &[64 * MIB - 4096]);
        assert_eq!(mirror_windows(&ragged, &MIRRORS), [5 * MIB]);
    }

    #[test]
    fn data_block_groups_hold_their_content_once_the_windows_are_taken_out() {
        // With nothing replicated, the data chunks a populated filesystem appends run straight
        // through the device past sixty-four mebibytes, so one of them holds that superblock copy
        // whenever the content reaches it. Content that fills the chunks to within a window of
        // their length is the case a planner counting lengths alone would leave a window short.
        let mut covered = 0;
        for data in (40 * MIB..120 * MIB).step_by((STRIPE_LEN / 4) as usize) {
            let request = PlanRequest::new(GIB)
                .metadata_profile(Profile::Single)
                .content(Content {
                    files: 1,
                    names: 1,
                    longest_name: 8,
                    data_bytes: data,
                    data_extents: data.div_ceil(MIB) * 2,
                    ..Content::EMPTY
                });
            let layout = plan_layout(&request).expect("the content fits the volume");
            let usable: u64 = layout
                .chunks_of(BlockGroupFlags::DATA)
                .map(|chunk| chunk.length - window_bytes(chunk, &layout.superblock_mirrors))
                .sum();
            assert!(
                usable >= data,
                "{data} bytes of content planned into {usable} bytes of data block groups"
            );
            covered += layout
                .chunks_of(BlockGroupFlags::DATA)
                .filter(|chunk| !mirror_windows(chunk, &layout.superblock_mirrors).is_empty())
                .count();
        }
        assert!(covered > 0, "no data chunk ever held a superblock copy");
    }

    #[test]
    fn the_system_reservation_grows_with_the_chunks_the_content_appends() {
        // Every kept chunk is a record in the chunk tree, and a populated filesystem appends
        // one data chunk per eight mebibytes of content at the default pairing — so at two
        // gibibytes of content the records outgrow the single leaf an empty filesystem needs
        // and the chunk tree gains a level.
        let empty = plan_layout(&PlanRequest::new(4 * GIB)).expect("formattable");
        assert_eq!(empty.reservation.system_blocks, 1);

        let populated = plan_layout(&PlanRequest::new(4 * GIB).content(Content {
            files: 1,
            names: 1,
            longest_name: 16,
            data_bytes: 2 * GIB,
            data_extents: 2048,
            ..Content::EMPTY
        }))
        .expect("two gibibytes of content fit a four-gibibyte volume");
        assert!(
            populated.reservation.system_blocks >= 3,
            "reserved {} system blocks for {} chunks",
            populated.reservation.system_blocks,
            populated.chunks.len()
        );
        assert!(populated.chunks.len() > empty.chunks.len());
    }

    #[test]
    fn a_chunk_map_the_system_chunk_cannot_record_is_refused_with_both_numbers() {
        // With nothing replicated the kept system chunk is the four-mebibyte bootstrap one,
        // and a terabyte volume holds more eight-mebibyte data chunks than four mebibytes of
        // chunk records can name. The refusal carries the ask and the ceiling, and it is issued
        // while the map is still arithmetic rather than after the content has been written.
        let request = PlanRequest::new(1024 * GIB)
            .metadata_profile(Profile::Single)
            .data_profile(Profile::Single)
            .content(Content {
                files: 1,
                names: 1,
                longest_name: 16,
                data_bytes: 300 * GIB,
                data_extents: 4096,
                ..Content::EMPTY
            });
        match plan_layout(&request) {
            Err(GeometryError::ChunkMapTooLarge {
                chunks,
                needed_blocks,
                available_blocks,
            }) => {
                assert!(chunks > 30_000, "{chunks} chunks");
                assert!(needed_blocks > available_blocks);
                assert_eq!(available_blocks, BOOTSTRAP_SYSTEM_CHUNK / 16384);
            }
            other => panic!("expected the chunk-map refusal, got {other:?}"),
        }
    }

    #[test]
    fn content_larger_than_the_volume_is_refused_rather_than_placed_past_its_end() {
        let request = PlanRequest::new(GIB).content(Content {
            longest_value: 0,
            data_bytes: 8 * GIB,
            data_extents: 8192,
            files: 1,
            ..Content::EMPTY
        });
        assert!(matches!(
            plan_layout(&request),
            Err(GeometryError::ContentTooLarge { .. })
        ));
    }

    #[test]
    fn content_no_device_could_hold_is_refused_rather_than_planned_a_chunk_at_a_time() {
        // The refusal has to be arithmetic. Appending a chunk per gibibyte first and measuring
        // afterwards would mean this call built two thousand million of them before answering,
        // which is a computation that does not end rather than the error it is owed.
        for data_bytes in [u64::MAX, u64::MAX / 2, 1 << 60] {
            let request = PlanRequest::new(GIB).content(Content {
                longest_value: 0,
                data_bytes,
                data_extents: 1 << 20,
                files: 1,
                ..Content::EMPTY
            });
            assert!(
                matches!(
                    plan_layout(&request),
                    Err(GeometryError::ContentTooLarge { .. })
                ),
                "{data_bytes} bytes of data on a gibibyte"
            );
        }
    }

    #[test]
    fn a_bound_too_large_to_represent_saturates_rather_than_wrapping() {
        // Nothing bounds a count a caller states, and a bound that wrapped would come out
        // *small* — the one way a reservation can be wrong that nothing downstream notices
        // until a writer has run out of room. What follows a saturated bound is a volume that
        // cannot hold it, which is a refusal.
        let request = PlanRequest::new(GIB).content(Content {
            longest_value: 0,
            directories: u64::MAX,
            files: u64::MAX,
            names: u64::MAX,
            longest_name: 255,
            xattrs: u64::MAX,
            subvolumes: u64::MAX,
            data_bytes: u64::MAX,
            data_extents: u64::MAX,
        });
        assert!(matches!(
            plan_layout(&request),
            Err(GeometryError::ContentTooLarge { .. })
        ));
    }

    #[test]
    fn a_name_costs_the_three_records_a_directory_entry_actually_is() {
        // A name is an inode reference, a record keyed by its hash, and a record keyed by its
        // position. A bound that charged one would be short by two thirds on every directory,
        // and short is the direction that fails.
        let base = plan_layout(&PlanRequest::new(17 * GIB).content(Content {
            directories: 1_000,
            files: 10_000,
            names: 0,
            longest_name: 255,
            ..Content::EMPTY
        }))
        .expect("plannable");
        let named = plan_layout(&PlanRequest::new(17 * GIB).content(Content {
            directories: 1_000,
            files: 10_000,
            names: 11_000,
            longest_name: 255,
            ..Content::EMPTY
        }))
        .expect("plannable");
        assert!(named.reservation.metadata_blocks > base.reservation.metadata_blocks);
    }

    #[test]
    fn a_reservation_that_was_exceeded_says_so_rather_than_absorbing_it() {
        let reservation = Reservation {
            metadata_blocks: 40,
            system_blocks: 2,
            node_size: 16384,
        };
        assert_eq!(
            reservation.account(24, 1),
            Ok(Slack {
                metadata_blocks: 16,
                system_blocks: 1,
            })
        );
        assert_eq!(
            reservation.account(40, 2),
            Ok(Slack {
                metadata_blocks: 0,
                system_blocks: 0,
            })
        );
        assert_eq!(
            reservation.account(41, 1),
            Err(ReservationExceeded {
                pool: Pool::Metadata,
                reserved: 40,
                used: 41,
            })
        );
        // Either pool can be the one that ran out, and the message says which. A chunk tree
        // grows with the chunk count, so the system pool is the one a very large volume
        // exhausts while the metadata pool has room to spare.
        assert_eq!(
            reservation.account(1, 3),
            Err(ReservationExceeded {
                pool: Pool::System,
                reserved: 2,
                used: 3,
            })
        );
        assert_eq!(
            reservation.account(1, 3).unwrap_err().to_string(),
            "the system reservation of 2 blocks was exceeded: 3 were spent"
        );
        assert_eq!(reservation.metadata_bytes(), 40 * 16384);
        assert_eq!(reservation.system_bytes(), 2 * 16384);
    }
}