Meg's Mirrors

zig

1	const MappedFile = @This();
2
3	const builtin = @import("builtin");
4	const is_linux = builtin.os.tag == .linux;
5	const is_windows = builtin.os.tag == .windows;
6
7	const std = @import("std");
8	const Allocator = std.mem.Allocator;
9	const Io = std.Io;
10	const assert = std.debug.assert;
11	const linux = std.os.linux;
12	const windows = std.os.windows;
13
14	io: Io,
15	flags: packed struct {
16	block_size: Alignment,
17	copy_file_range_unsupported: bool,
18	fallocate_punch_hole_unsupported: bool,
19	fallocate_insert_range_unsupported: bool,
20	},
21	memory_map: Io.File.MemoryMap,
22	nodes: std.ArrayList(Node),
23	free_ni: Node.Index.Optional,
24	large: std.ArrayList(u64),
25	updates: std.ArrayList(Node.Index),
26	/// This progress node's estimated total items is increased once for each node appended to `updates`.
27	update_prog_node: std.Progress.Node,
28	writers: std.SinglyLinkedList,
29	io_err: ?IoError,
30	/// If locked, modifying the node layout is not allowed.
31	/// Modifying node content is always allowed.
32	nodes_lock: std.debug.SafetyLock = .{},
33
34	pub const growth_factor = 4;
35
36	pub const IoError = Io.UnexpectedError || error{
37	DiskQuota,
38	FileTooBig,
39	InputOutput,
40	NoSpaceLeft,
41	AccessDenied,
42	PermissionDenied,
43	SystemResources,
44	LockViolation,
45	LockedMemoryLimitExceeded,
46	ProcessFdQuotaExceeded,
47	SystemFdQuotaExceeded,
48	FileBusy,
49	DeviceBusy,
50	NoDevice,
51	PathAlreadyExists,
52	IsDir,
53	NotFile,
54	BrokenPipe,
55	NonResizable,
56	Unseekable,
57	};
58
59	pub const Error = Allocator.Error || Io.Cancelable || error{
60	/// Some I/O operation on the memory-mapped file failed. The underlying error is available in
61	/// the `MappedFile.io_err` field.
62	MappedFileIo,
63	};
64
65	/// This separate `Alignment` type exists because neither of the other options is really suitable:
66	///
67	/// * `std.mem.Alignment` is based on `usize`, which---while technically okay since the file is
68	/// memory-mapped---is in practice very annoying to work with in linker implementations
69	///
70	/// * `InternPool.Alignment` is based on `u64`, which is better, but it has the value `.none`, which
71	/// is also really annoying to handle, because no alignment is ever nullable in this API
72	///
73	/// At some point we should probably just change `InternPool.Alignment` to be non-optional, and add
74	/// a new `InternPool.Alignment.Optional` type for the case where it can actually be `.none`. At
75	/// that point we can transition this code to using `InternPool.Alignment` (although it should
76	/// probably be namespaced elsewhere, it has nothing to do with the `InternPool`!).
77	pub const Alignment = enum(u6) {
78	@"1" = 0,
79	@"2" = 1,
80	@"4" = 2,
81	@"8" = 3,
82	@"16" = 4,
83	@"32" = 5,
84	@"64" = 6,
85	_,
86
87	pub fn fromIp(a: @import("../InternPool.zig").Alignment) Alignment {
88	assert(a != .none);
89	return @bitCast(a);
90	}
91
92	pub fn toLog2Units(a: Alignment) u6 {
93	return @backingInt(a);
94	}
95
96	pub fn fromLog2Units(a: u6) Alignment {
97	return @fromBackingInt(a);
98	}
99
100	pub fn toByteUnits(a: Alignment) u64 {
101	return @as(u64, 1) << @backingInt(a);
102	}
103
104	pub fn fromByteUnits(n: u64) Alignment {
105	assert(std.math.isPowerOfTwo(n));
106	return @fromBackingInt(@intCast(@ctz(n)));
107	}
108
109	pub fn order(lhs: Alignment, rhs: Alignment) std.math.Order {
110	return std.math.order(@backingInt(lhs), @backingInt(rhs));
111	}
112
113	pub fn compare(lhs: Alignment, op: std.math.CompareOperator, rhs: Alignment) bool {
114	return std.math.compare(@backingInt(lhs), op, @backingInt(rhs));
115	}
116
117	pub fn max(lhs: Alignment, rhs: Alignment) Alignment {
118	return @fromBackingInt(@max(@backingInt(lhs), @backingInt(rhs)));
119	}
120
121	pub fn min(lhs: Alignment, rhs: Alignment) Alignment {
122	return @fromBackingInt(@min(@backingInt(lhs), @backingInt(rhs)));
123	}
124
125	pub inline fn of(comptime T: type) Alignment {
126	return comptime .fromByteUnits(@alignOf(T));
127	}
128
129	/// Given that a base address is known to be aligned to `a`, computes the known alignment of
130	/// that base address plus `off`.
131	pub fn offset(a: Alignment, off: u64) Alignment {
132	return .fromLog2Units(@min(a.toLog2Units(), @ctz(off)));
133	}
134
135	/// Align an address forwards to this alignment.
136	pub fn forward(a: Alignment, addr: u64) u64 {
137	const x = (@as(u64, 1) << @backingInt(a)) - 1;
138	return (addr + x) & ~x;
139	}
140
141	/// Align an address backwards to this alignment.
142	pub fn backward(a: Alignment, addr: u64) u64 {
143	const x = (@as(u64, 1) << @backingInt(a)) - 1;
144	return addr & ~x;
145	}
146
147	/// Check if an address is aligned to this amount.
148	pub fn check(a: Alignment, addr: u64) bool {
149	return @ctz(addr) >= @backingInt(a);
150	}
151	};
152
153	pub fn init(file: Io.File, gpa: Allocator, io: Io) (Allocator.Error || Io.Cancelable || IoError)!MappedFile {
154	var mf: MappedFile = .{
155	.io = io,
156	.flags = undefined,
157	.memory_map = .{
158	.file = file,
159	.memory = &.{},
160	.offset = 0,
161	.section = null,
162	},
163	.nodes = .empty,
164	.free_ni = .none,
165	.large = .empty,
166	.updates = .empty,
167	.update_prog_node = .none,
168	.writers = .{},
169	.io_err = null,
170	};
171	errdefer mf.deinit(gpa);
172	const size: u64, const block_size = stat: {
173	const stat = file.stat(io) catch |err| switch (err) {
174	error.Streaming => return error.PathAlreadyExists,
175	else => |e| return e,
176	};
177	if (stat.kind != .file) return error.PathAlreadyExists;
178	break :stat .{ stat.size, @max(std.heap.pageSize(), stat.block_size) };
179	};
180	mf.flags = .{
181	.block_size = .fromByteUnits(std.math.ceilPowerOfTwoAssert(usize, block_size)),
182	.copy_file_range_unsupported = false,
183	.fallocate_insert_range_unsupported = false,
184	.fallocate_punch_hole_unsupported = false,
185	};
186
187	const root_location: Node.Location = l: {
188	if (std.math.cast(u32, size)) |small_size| {
189	break :l .{ .small = .{ .offset = 0, .size = small_size } };
190	}
191	try mf.large.appendSlice(gpa, &.{ 0, size });
192	break :l .{ .large = .{ .index = 0 } };
193	};
194	try mf.nodes.append(gpa, .{
195	.parent = .none,
196	.prev = .none,
197	.next = .none,
198	.first = .none,
199	.last = .none,
200	.flags = .{
201	.alignment = mf.flags.block_size,
202	.position = .floating,
203	.bubbles_moved = true,
204	.enable_next_moved = false,
205	.location_tag = root_location,
206	.moved = false,
207	.resized = false,
208	.next_moved = false,
209	.has_content = false,
210	},
211	.location_payload = switch (root_location) {
212	.small => |small| .{ .small = small },
213	.large => |large| .{ .large = large },
214	},
215	});
216
217	mf.ensureTotalCapacity(@intCast(size)) catch |err| switch (err) {
218	error.MappedFileIo => return mf.io_err.?,
219	else => |e| return e,
220	};
221
222	return mf;
223	}
224
225	pub fn deinit(mf: *MappedFile, gpa: Allocator) void {
226	mf.unmap();
227	mf.nodes.deinit(gpa);
228	mf.large.deinit(gpa);
229	mf.updates.deinit(gpa);
230	mf.update_prog_node.end();
231	assert(mf.writers.first == null);
232	mf.* = undefined;
233	}
234
235	pub const Node = extern struct {
236	parent: Node.Index.Optional,
237	prev: Node.Index.Optional,
238	next: Node.Index.Optional,
239	first: Node.Index.Optional,
240	last: Node.Index.Optional,
241	flags: Flags,
242	location_payload: Location.Payload,
243
244	/// Any non-leaf node may designate its first N children as "header" nodes. This means that its
245	/// first N children must be densely packed together and positioned at the start of the parent.
246	/// The implementation guarantees that it will never re-order these nodes, nor will it introduce
247	/// padding between them.
248	///
249	/// Likewise, any non-leaf node may designate its *last* M children as "footer" nodes, which are
250	/// like header nodes except they are positioned at the *end* of the parent rather than the
251	/// start.
252	///
253	/// Nodes which are neither headers nor footers are called "floating". The implementation is
254	/// always free to re-order floating nodes relative to one another, and to add or remove padding
255	/// between them.
256	pub const Position = enum(u2) {
257	header,
258	footer,
259	floating,
260	};
261
262	pub const Flags = packed struct(u32) {
263	/// While the number of header and footer nodes within a parent node is logically a part of
264	/// that parent, we actually store this information on the child nodes for efficiency: this
265	/// field indicates whether each child is a header node, a footer node, or a floating node.
266	///
267	/// This value is meaningless for the root node, so is arbitrarily set to `.floating`.
268	position: Position,
269	/// For floating nodes, this node's offset into its parent will always be aligned to this
270	/// boundary. (This is not the case for header and footer nodes due to the requirement that
271	/// they be densely packed against the start/end of the parent node.)
272	///
273	/// This node's size will also always be aligned to this boundary. (This applies regardless
274	/// of whether this is a floating node, a header node, or a footer node.)
275	alignment: Alignment,
276	/// Whether `moved` events on this node bubble down to children.
277	bubbles_moved: bool,
278	/// Whether `next_moved` events are reported in `updates`.
279	enable_next_moved: bool,
280
281	location_tag: Location.Tag,
282	/// Whether this node has been moved.
283	moved: bool,
284	/// Whether this node has been resized.
285	resized: bool,
286	/// Whether the next sibling has moved or is a different node.
287	next_moved: bool,
288	/// Whether this node might contain initialized bytes.
289	has_content: bool,
290	unused: u17 = 0,
291	};
292
293	pub const Location = union(enum(u1)) {
294	small: extern struct {
295	/// Relative to `parent`.
296	offset: u32,
297	size: u32,
298	},
299	large: extern struct {
300	index: usize,
301	unused: @Int(.unsigned, 64 - @bitSizeOf(usize)) = 0,
302	},
303
304	pub const Tag = @typeInfo(Location).@"union".tag_type.?;
305	pub const Payload = extern union {
306	small: @FieldType(Location, "small"),
307	large: @FieldType(Location, "large"),
308	};
309
310	pub fn resolve(loc: Location, mf: *const MappedFile) [2]u64 {
311	return switch (loc) {
312	.small => |small| .{ small.offset, small.size },
313	.large => |large| mf.large.items[large.index..][0..2].*,
314	};
315	}
316	};
317
318	pub const FileLocation = struct {
319	offset: u64,
320	size: u64,
321
322	pub fn end(fl: FileLocation) u64 {
323	return fl.offset + fl.size;
324	}
325	};
326
327	pub const AddOptions = struct {
328	/// Must be aligned to the given `alignment`.
329	size: u64 = 0,
330	alignment: Alignment = .@"1",
331	bubbles_moved: bool = true,
332	enable_next_moved: bool = false,
333
334	moved: bool = false,
335	resized: bool = false,
336	next_moved: bool = false,
337	};
338
339	pub const Index = enum(u32) {
340	root,
341	_,
342
343	pub const Optional = enum(u32) {
344	none = std.math.maxInt(u32),
345	_,
346
347	pub fn unwrap(oi: Optional) ?Index {
348	return switch (oi) {
349	_ => @fromBackingInt(@backingInt(oi)),
350	.none => null,
351	};
352	}
353	pub fn wrap(i: Index) Optional {
354	const oi: Optional = @bitCast(i);
355	assert(oi != .none);
356	return oi;
357	}
358	};
359
360	fn get(ni: Node.Index, mf: *const MappedFile) *Node {
361	return &mf.nodes.items[@backingInt(ni)];
362	}
363
364	/// Adds a floating child node to `parent_ni`. Returns the index of the new child.
365	pub fn addFloatingChild(parent_ni: Node.Index, mf: *MappedFile, gpa: Allocator, opts: AddOptions) Error!Node.Index {
366	return mf.addNode(gpa, .{
367	.add_options = opts,
368	.position = .floating,
369	.parent = parent_ni,
370	.prev = parent_ni.lastHeader(mf),
371	});
372	}
373	/// Adds a header child node to `parent_ni`. Returns the index of the new child.
374	///
375	/// Asserts that `parent_ni` has no existing header children.
376	pub fn addOnlyHeaderChild(parent_ni: Node.Index, mf: *MappedFile, gpa: Allocator, opts: AddOptions) Error!Node.Index {
377	if (parent_ni.first(mf).unwrap()) |first_ni| {
378	assert(first_ni.position(mf) != .header); // `parent_ni` already has a header child
379	}
380	return parent_ni.addHeaderChildAfter(mf, gpa, .none, opts);
381	}
382	/// Adds a header child node to `parent_ni`. Returns the index of the new child.
383	///
384	/// If `prev_oni` is `.none`, the new child is placed at the very start of the parent,
385	/// before any existing header nodes.
386	///
387	/// Otherwise, asserts that `prev_oni` is a header node and a child of `parent_ni`, and
388	/// places the new child node immediately after `prev_oni`.
389	pub fn addHeaderChildAfter(parent_ni: Node.Index, mf: *MappedFile, gpa: Allocator, prev_oni: Node.Index.Optional, opts: AddOptions) Error!Node.Index {
390	return mf.addNode(gpa, .{
391	.add_options = opts,
392	.position = .header,
393	.parent = parent_ni,
394	.prev = prev_oni,
395	});
396	}
397	/// Adds a footer child node to `parent_ni`. Returns the index of the new child.
398	///
399	/// Asserts that `parent_ni` has no existing footer children.
400	pub fn addOnlyFooterChild(parent_ni: Node.Index, mf: *MappedFile, gpa: Allocator, opts: AddOptions) Error!Node.Index {
401	if (parent_ni.last(mf).unwrap()) |last_ni| {
402	assert(last_ni.position(mf) != .footer); // `parent_ni` already has a footer child
403	}
404	return parent_ni.addFooterChildBefore(mf, gpa, .none, opts);
405	}
406	/// Adds a footer child node to `parent_ni`. Returns the index of the new child.
407	///
408	/// If `next_oni` is `.none`, the new child is placed at the very end of the parent, after
409	/// any existing footer nodes.
410	///
411	/// Otherwise, asserts that `next_oni` is a footer node and a child of `parent_ni`, and
412	/// places the new child node immediately before `next_oni`.
413	pub fn addFooterChildBefore(parent_ni: Node.Index, mf: *MappedFile, gpa: Allocator, next_oni: Node.Index.Optional, opts: AddOptions) Error!Node.Index {
414	const prev_oni: Node.Index.Optional = prev: {
415	const next_ni = next_oni.unwrap() orelse {
416	break :prev parent_ni.last(mf);
417	};
418	break :prev next_ni.prev(mf);
419	};
420	return mf.addNode(gpa, .{
421	.add_options = opts,
422	.position = .footer,
423	.parent = parent_ni,
424	.prev = prev_oni,
425	});
426	}
427
428	/// Alias for `Optional.wrap`, provided for convenience when a result type is not available.
429	pub const toOptional = Optional.wrap;
430
431	pub fn parent(ni: Node.Index, mf: *const MappedFile) Node.Index.Optional {
432	return ni.get(mf).parent;
433	}
434
435	pub fn first(ni: Node.Index, mf: *const MappedFile) Node.Index.Optional {
436	return ni.get(mf).first;
437	}
438
439	pub fn last(ni: Node.Index, mf: *const MappedFile) Node.Index.Optional {
440	return ni.get(mf).last;
441	}
442
443	fn lastHeader(ni: Node.Index, mf: *const MappedFile) Node.Index.Optional {
444	var header_ni = ni.first(mf).unwrap() orelse return .none;
445	if (header_ni.position(mf) != .header) return .none;
446	while (true) {
447	const next_ni = header_ni.next(mf).unwrap() orelse break;
448	if (next_ni.position(mf) != .header) break;
449	header_ni = next_ni;
450	}
451	return .wrap(header_ni);
452	}
453	fn firstFooter(ni: Node.Index, mf: *const MappedFile) Node.Index.Optional {
454	var footer_ni = ni.last(mf).unwrap() orelse return .none;
455	if (footer_ni.position(mf) != .footer) return .none;
456	while (true) {
457	const prev_ni = footer_ni.prev(mf).unwrap() orelse break;
458	if (prev_ni.position(mf) != .footer) break;
459	footer_ni = prev_ni;
460	}
461	return .wrap(footer_ni);
462	}
463
464	/// Asserts that `ni` is not `.root`, because `Position` is meaningless for the root node.
465	pub fn position(ni: Node.Index, mf: *const MappedFile) Node.Position {
466	assert(ni != .root);
467	return ni.get(mf).flags.position;
468	}
469
470	pub fn next(ni: Node.Index, mf: *const MappedFile) Node.Index.Optional {
471	return ni.get(mf).next;
472	}
473	fn setNext(
474	ni: Node.Index,
475	gpa: Allocator,
476	next_ni: Node.Index.Optional,
477	mf: *MappedFile,
478	) Allocator.Error!void {
479	const next_ptr = &ni.get(mf).next;
480	if (next_ptr.* == next_ni) return;
481	next_ptr.* = next_ni;
482	try ni.nextMoved(gpa, mf);
483	}
484
485	pub fn prev(ni: Node.Index, mf: *const MappedFile) Node.Index.Optional {
486	return ni.get(mf).prev;
487	}
488
489	pub fn childrenMoved(ni: Node.Index, gpa: Allocator, mf: *MappedFile) Allocator.Error!void {
490	var child_oni = ni.get(mf).last;
491	while (child_oni.unwrap()) |child_ni| {
492	try child_ni.moved(gpa, mf);
493	child_oni = child_ni.get(mf).prev;
494	}
495	}
496
497	pub fn hasMoved(ni: Node.Index, mf: *const MappedFile) bool {
498	var parent_ni = ni;
499	while (parent_ni != .root) {
500	const parent_node = parent_ni.get(mf);
501	if (!parent_node.flags.bubbles_moved) break;
502	if (parent_node.flags.moved) return true;
503	parent_ni = parent_node.parent.unwrap().?;
504	}
505	return false;
506	}
507	pub fn moved(ni: Node.Index, gpa: Allocator, mf: *MappedFile) Allocator.Error!void {
508	try mf.updates.ensureUnusedCapacity(gpa, 2);
509	ni.movedAssumeCapacity(mf);
510	}
511	pub fn cleanMoved(ni: Node.Index, mf: *MappedFile) bool {
512	const node_moved = &ni.get(mf).flags.moved;
513	defer node_moved.* = false;
514	return node_moved.*;
515	}
516	pub fn movedAssumeCapacity(ni: Node.Index, mf: *MappedFile) void {
517	if (ni.hasMoved(mf)) return;
518	const node = ni.get(mf);
519	node.flags.moved = true;
520	if (node.prev.unwrap()) |prev_ni| {
521	prev_ni.nextMovedAssumeCapacity(mf);
522	}
523	if (node.flags.resized or node.flags.next_moved) return;
524	mf.updates.appendAssumeCapacity(ni);
525	mf.update_prog_node.increaseEstimatedTotalItems(1);
526	}
527
528	pub fn hasResized(ni: Node.Index, mf: *const MappedFile) bool {
529	return ni.get(mf).flags.resized;
530	}
531	pub fn resized(ni: Node.Index, gpa: Allocator, mf: *MappedFile) Allocator.Error!void {
532	try mf.updates.ensureUnusedCapacity(gpa, 1);
533	ni.resizedAssumeCapacity(mf);
534	}
535	pub fn cleanResized(ni: Node.Index, mf: *MappedFile) bool {
536	const node_resized = &ni.get(mf).flags.resized;
537	defer node_resized.* = false;
538	return node_resized.*;
539	}
540	pub fn resizedAssumeCapacity(ni: Node.Index, mf: *MappedFile) void {
541	const node = ni.get(mf);
542	if (node.flags.resized) return;
543	node.flags.resized = true;
544	if (node.flags.moved or node.flags.next_moved) return;
545	mf.updates.appendAssumeCapacity(ni);
546	mf.update_prog_node.increaseEstimatedTotalItems(1);
547	}
548
549	pub fn hasNextMoved(ni: Node.Index, mf: *const MappedFile) bool {
550	return ni.get(mf).flags.next_moved;
551	}
552	pub fn nextMoved(ni: Node.Index, gpa: Allocator, mf: *MappedFile) Allocator.Error!void {
553	try mf.updates.ensureUnusedCapacity(gpa, 1);
554	ni.nextMovedAssumeCapacity(mf);
555	}
556	pub fn cleanNextMoved(ni: Node.Index, mf: *MappedFile) bool {
557	const node_next_moved = &ni.get(mf).flags.next_moved;
558	defer node_next_moved.* = false;
559	return node_next_moved.*;
560	}
561	pub fn nextMovedAssumeCapacity(ni: Node.Index, mf: *MappedFile) void {
562	const node = ni.get(mf);
563	if (!node.flags.enable_next_moved or node.flags.next_moved) return;
564	node.flags.next_moved = true;
565	if (node.flags.moved or node.flags.resized) return;
566	mf.updates.appendAssumeCapacity(ni);
567	mf.update_prog_node.increaseEstimatedTotalItems(1);
568	}
569
570	pub fn alignment(ni: Node.Index, mf: *const MappedFile) Alignment {
571	return ni.get(mf).flags.alignment;
572	}
573
574	fn setLocation(ni: Node.Index, mf: *MappedFile, gpa: Allocator, offset: u64, size: u64) Allocator.Error!void {
575	try mf.large.ensureUnusedCapacity(gpa, 2);
576	try mf.updates.ensureUnusedCapacity(gpa, 2);
577	const node = ni.get(mf);
578	if (node.flags.position == .floating) {
579	assert(node.flags.alignment.check(offset));
580	}
581	assert(node.flags.alignment.check(size));
582	if (size == 0) node.flags.has_content = false;
583	switch (node.location()) {
584	.small => |small| {
585	if (small.offset != offset) ni.movedAssumeCapacity(mf);
586	if (small.size != size) ni.resizedAssumeCapacity(mf);
587	if (std.math.cast(u32, offset)) |small_offset| {
588	if (std.math.cast(u32, size)) |small_size| {
589	node.location_payload.small = .{
590	.offset = small_offset,
591	.size = small_size,
592	};
593	return;
594	}
595	}
596	defer mf.large.appendSliceAssumeCapacity(&.{ offset, size });
597	node.flags.location_tag = .large;
598	node.location_payload = .{ .large = .{ .index = mf.large.items.len } };
599	},
600	.large => |large| {
601	const large_items = mf.large.items[large.index..][0..2];
602	if (large_items[0] != offset) ni.movedAssumeCapacity(mf);
603	if (large_items[1] != size) ni.resizedAssumeCapacity(mf);
604	large_items.* = .{ offset, size };
605	},
606	}
607	}
608
609	pub fn location(ni: Node.Index, mf: *const MappedFile) Location {
610	return ni.get(mf).location();
611	}
612
613	pub fn fileLocation(
614	ni: Node.Index,
615	mf: *const MappedFile,
616	set_has_content: bool,
617	) FileLocation {
618	var offset, const size = ni.location(mf).resolve(mf);
619	var parent_ni = ni;
620	while (true) {
621	const parent_node = parent_ni.get(mf);
622	if (set_has_content) parent_node.flags.has_content = true;
623	if (parent_ni == .root) {
624	assert(parent_node.parent == .none);
625	break;
626	}
627	parent_ni = parent_node.parent.unwrap().?;
628	const parent_offset, _ = parent_ni.location(mf).resolve(mf);
629	offset += parent_offset;
630	}
631	return .{ .offset = offset, .size = size };
632	}
633
634	pub fn slice(ni: Node.Index, mf: *const MappedFile) []u8 {
635	const file_loc = ni.fileLocation(mf, true);
636	return mf.memory_map.memory[@intCast(file_loc.offset)..][0..@intCast(file_loc.size)];
637	}
638
639	pub fn sliceConst(ni: Node.Index, mf: *const MappedFile) []const u8 {
640	const file_loc = ni.fileLocation(mf, false);
641	return mf.memory_map.memory[@intCast(file_loc.offset)..][0..@intCast(file_loc.size)];
642	}
643
644	/// Ensures that the size of `ni` is at least `min_size`. Valid for any node.
645	///
646	/// Applies `growth_factor` if necessary (so the caller should *not* apply `growth_factor`).
647	pub fn ensureMinimumSize(ni: Node.Index, mf: *MappedFile, gpa: Allocator, min_size: u64) Error!void {
648	_, const current_size = ni.location(mf).resolve(mf);
649	if (current_size >= min_size) return;
650	const new_size = ni.alignment(mf).forward(min_size +| min_size / growth_factor);
651	try mf.growNode(gpa, ni, new_size, .{
652	.exact_size = false,
653	.move_footers = true,
654	});
655	mf.updateWriters();
656	}
657
658	/// Sets the size of `ni` to exactly `size`.
659	///
660	/// Asserts that `ni` is a leaf node, i.e. has no children.
661	///
662	/// Asserts that `size` is aligned to `ni.alignment(mf)`.
663	pub fn resizeLeaf(ni: Node.Index, mf: *MappedFile, gpa: Allocator, size: u64) Error!void {
664	assert(ni.first(mf) == .none);
665	// The alignment of `size` is asserted by `shrinkLeafNode` and `growNode`.
666	_, const old_size = ni.location(mf).resolve(mf);
667	switch (std.math.order(size, old_size)) {
668	.lt => try mf.shrinkLeafNode(gpa, ni, size),
669	.eq => {}, // `old_size` must be well-aligned, so `size` is too
670	.gt => try mf.growNode(gpa, ni, size, .{
671	.exact_size = true,
672	.move_footers = false, // irrelevant, since we have no footers
673	}),
674	}
675	mf.updateWriters();
676	}
677
678	/// Updates a node's alignment to exactly `new_alignment`. Valid for any node.
679	///
680	/// If the node's current offset or size is not sufficiently aligned, it will be moved
681	/// and/or resized to match the new alignment. The node's size may be increased by any
682	/// amount, as if `ensureMinimumSize` were used.
683	pub fn realign(
684	ni: Node.Index,
685	mf: *MappedFile,
686	gpa: Allocator,
687	new_alignment: Alignment,
688	) Error!void {
689	try mf.realignNode(gpa, ni, new_alignment);
690	mf.updateWriters();
691	}
692
693	pub fn writer(ni: Node.Index, mf: *MappedFile, gpa: Allocator, w: *Writer) void {
694	w.* = .{
695	.gpa = gpa,
696	.mf = mf,
697	.writer_node = .{},
698	.ni = ni,
699	.interface = .{
700	.buffer = ni.slice(mf),
701	.vtable = &Writer.vtable,
702	},
703	.err = null,
704	};
705	mf.writers.prepend(&w.writer_node);
706	}
707	};
708
709	pub fn location(node: *const Node) Location {
710	return switch (node.flags.location_tag) {
711	inline else => |tag| @unionInit(
712	Location,
713	@tagName(tag),
714	@field(node.location_payload, @tagName(tag)),
715	),
716	};
717	}
718
719	pub const Writer = struct {
720	gpa: Allocator,
721	mf: *MappedFile,
722	writer_node: std.SinglyLinkedList.Node,
723	ni: Node.Index,
724	interface: Io.Writer,
725	err: ?Error,
726
727	pub fn deinit(w: *Writer) void {
728	assert(w.mf.writers.popFirst() == &w.writer_node);
729	w.* = undefined;
730	}
731
732	const vtable: Io.Writer.VTable = .{
733	.drain = drain,
734	.sendFile = sendFile,
735	.flush = Io.Writer.noopFlush,
736	.rebase = growingRebase,
737	};
738
739	fn drain(
740	interface: *Io.Writer,
741	data: []const []const u8,
742	splat: usize,
743	) Io.Writer.Error!usize {
744	const pattern = data[data.len - 1];
745	const splat_len = pattern.len * splat;
746	const start_len = interface.end;
747	assert(data.len != 0);
748	for (data) |bytes| {
749	try growingRebase(interface, interface.end, bytes.len + splat_len + 1);
750	@memcpy(interface.buffer[interface.end..][0..bytes.len], bytes);
751	interface.end += bytes.len;
752	}
753	if (splat == 0) {
754	interface.end -= pattern.len;
755	} else switch (pattern.len) {
756	0 => {},
757	1 => {
758	@memset(interface.buffer[interface.end..][0 .. splat - 1], pattern[0]);
759	interface.end += splat - 1;
760	},
761	else => for (0..splat - 1) |_| {
762	@memcpy(interface.buffer[interface.end..][0..pattern.len], pattern);
763	interface.end += pattern.len;
764	},
765	}
766	return interface.end - start_len;
767	}
768
769	fn sendFile(
770	interface: *Io.Writer,
771	file_reader: *Io.File.Reader,
772	limit: Io.Limit,
773	) Io.Writer.FileError!usize {
774	if (limit == .nothing) return 0;
775	const pos = file_reader.logicalPos();
776	const additional = if (file_reader.getSize()) |size| size - pos else |_| std.atomic.cache_line;
777	if (additional == 0) return error.EndOfStream;
778	try growingRebase(interface, interface.end, limit.minInt64(additional));
779	switch (file_reader.mode) {
780	.positional => {
781	const fr_buf = file_reader.interface.buffered();
782	if (fr_buf.len > 0) {
783	const n = interface.write(fr_buf) catch unreachable;
784	file_reader.interface.toss(n);
785	return n;
786	}
787	const w: *Writer = @fieldParentPtr("interface", interface);
788	const n: usize = @intCast(w.mf.copyFileRange(
789	file_reader.file,
790	file_reader.pos,
791	w.ni.fileLocation(w.mf, true).offset + interface.end,
792	limit.minInt(interface.unusedCapacityLen()),
793	) catch |err| {
794	w.err = err;
795	return error.WriteFailed;
796	});
797	if (n == 0) return error.Unimplemented;
798	file_reader.pos += n;
799	interface.end += n;
800	return n;
801	},
802	.streaming,
803	.streaming_simple,
804	.positional_simple,
805	.failure,
806	=> {
807	const dest = limit.slice(interface.unusedCapacitySlice());
808	const n = try file_reader.interface.readSliceShort(dest);
809	if (n == 0) return error.EndOfStream;
810	interface.end += n;
811	return n;
812	},
813	}
814	}
815
816	fn growingRebase(
817	interface: *Io.Writer,
818	preserve: usize,
819	unused_capacity: usize,
820	) Io.Writer.Error!void {
821	_ = preserve;
822	const w: *Writer = @fieldParentPtr("interface", interface);
823	w.ni.ensureMinimumSize(w.mf, w.gpa, interface.end + unused_capacity) catch |err| {
824	w.err = err;
825	return error.WriteFailed;
826	};
827	}
828	};
829
830	comptime {
831	if (!std.debug.runtime_safety) assert(@sizeOf(Node) == 32);
832	}
833	};
834
835	/// Asserts that `opts.position` is compatible with `opts.prev` (i.e. that this addition will not
836	/// violate the requirement that header nodes come before floating nodes come before footer nodes).
837	fn addNode(mf: *MappedFile, gpa: Allocator, opts: struct {
838	add_options: Node.AddOptions,
839	position: Node.Position,
840	parent: Node.Index,
841	/// If `position == .floating`, this is just used as an initial value, and may be immediately
842	/// replaced when finding a location for this node. In this case, it is still necessary that
843	/// `prev` be compatible with `position` (so `prev` must be either a floating node or the last
844	/// header node in `parent`).
845	prev: Node.Index.Optional,
846	}) Error!Node.Index {
847	mf.nodes_lock.assertUnlocked();
848
849	try mf.nodes.ensureUnusedCapacity(gpa, 1);
850	try mf.large.ensureUnusedCapacity(gpa, 2);
851
852	const new_ni: Node.Index = new: {
853	if (mf.free_ni.unwrap()) |free_ni| {
854	mf.free_ni = free_ni.get(mf).next;
855	break :new free_ni;
856	}
857	const new_ni: Node.Index = @fromBackingInt(@intCast(mf.nodes.items.len));
858	_ = mf.nodes.addOneAssumeCapacity();
859	break :new new_ni;
860	};
861
862	const next_oni: Node.Index.Optional = if (opts.prev.unwrap()) |prev_ni| next: {
863	assert(prev_ni.parent(mf) == opts.parent.toOptional()); // `prev` is not a child of `parent`
864	break :next prev_ni.get(mf).next;
865	} else opts.parent.first(mf);
866
867	// Validate node ordering
868	switch (opts.position) {
869	.floating => {
870	if (opts.prev.unwrap()) |prev_ni| {
871	assert(prev_ni.position(mf) != .footer); // tried to add floating node after footer node
872	}
873	if (next_oni.unwrap()) |next_ni| {
874	assert(next_ni.position(mf) != .header); // tried to add floating node before header node
875	}
876	},
877	.header => if (opts.prev.unwrap()) |prev_ni| {
878	switch (prev_ni.position(mf)) {
879	.header => {},
880	.floating => unreachable, // tried to add header node after floating node
881	.footer => unreachable, // tried to add header node after footer node
882	}
883	},
884	.footer => if (next_oni.unwrap()) |next_ni| {
885	switch (next_ni.position(mf)) {
886	.header => unreachable, // tried to add footer node before header node
887	.floating => unreachable, // tried to add footer node before floating node
888	.footer => {},
889	}
890	},
891	}
892
893	// Initialize the node as empty with alignment 1
894	const location: Node.Location = loc: {
895	const offset: u64 = switch (opts.position) {
896	.header, .floating => offset: {
897	const prev_ni = opts.prev.unwrap() orelse break :offset 0;
898	const prev_offset, const prev_size = prev_ni.location(mf).resolve(mf);
899	break :offset prev_offset + prev_size;
900	},
901	.footer => offset: {
902	const next_ni = next_oni.unwrap() orelse {
903	_, const parent_size = opts.parent.location(mf).resolve(mf);
904	break :offset parent_size;
905	};
906	const next_offset, _ = next_ni.location(mf).resolve(mf);
907	break :offset next_offset;
908	},
909	};
910	if (std.math.cast(u32, offset)) |small_offset| {
911	break :loc .{ .small = .{ .offset = small_offset, .size = 0 } };
912	}
913	const large_index = mf.large.items.len;
914	mf.large.appendSliceAssumeCapacity(&.{ offset, 0 });
915	break :loc .{ .large = .{ .index = large_index } };
916	};
917	new_ni.get(mf).* = .{
918	.parent = .wrap(opts.parent),
919	.prev = .none,
920	.next = .none,
921	.first = .none,
922	.last = .none,
923	.flags = .{
924	.position = opts.position,
925	.alignment = .@"1",
926	.bubbles_moved = opts.add_options.bubbles_moved,
927	.enable_next_moved = opts.add_options.enable_next_moved,
928	.location_tag = location,
929	.moved = false,
930	.resized = false,
931	.next_moved = false,
932	.has_content = false,
933	},
934	.location_payload = switch (location) {
935	.small => |small| .{ .small = small },
936	.large => |large| .{ .large = large },
937	},
938	};
939
940	try mf.addNodesToChildListBefore(gpa, next_oni, new_ni, new_ni);
941
942	try mf.realignNode(gpa, new_ni, opts.add_options.alignment);
943	if (opts.add_options.size > 0) {
944	try mf.growNode(gpa, new_ni, opts.add_options.size, .{
945	.exact_size = true,
946	.move_footers = false, // irrelevant, since we have no footers
947	});
948	}
949	mf.updateWriters();
950
951	new_ni.get(mf).flags.moved = false;
952	new_ni.get(mf).flags.resized = false;
953	new_ni.get(mf).flags.next_moved = false;
954
955	if (opts.add_options.moved) try new_ni.moved(gpa, mf);
956	if (opts.add_options.resized) try new_ni.resized(gpa, mf);
957	if (opts.add_options.next_moved) try new_ni.nextMoved(gpa, mf);
958
959	return new_ni;
960	}
961
962	fn shrinkLeafNode(
963	mf: *MappedFile,
964	gpa: Allocator,
965	ni: Node.Index,
966	new_size: u64,
967	) Error!void {
968	mf.nodes_lock.assertUnlocked();
969
970	const old_offset, const old_size = ni.location(mf).resolve(mf);
971
972	assert(new_size < old_size);
973	assert(ni.alignment(mf).check(new_size));
974	assert(ni.first(mf) == .none); // `ni` must be a leaf node
975
976	const parent_ni = ni.parent(mf).unwrap() orelse {
977	assert(ni == .root);
978	mf.memory_map.write(mf.io) catch |err| {
979	mf.io_err = switch (err) {
980	error.Canceled => |e| return e,
981	error.WouldBlock => error.Unexpected, // file was not opened as non-blocking
982	error.NotOpenForWriting => error.Unexpected, // we definitely opened the file for writing
983	else => |e| e,
984	};
985	return error.MappedFileIo;
986	};
987	mf.memory_map.file.setLength(mf.io, new_size) catch |err| switch (err) {
988	error.Canceled => |e| return e,
989	else => |e| {
990	mf.io_err = e;
991	return error.MappedFileIo;
992	},
993	};
994	try mf.ensureTotalCapacityPrecise(@intCast(new_size));
995	try ni.setLocation(mf, gpa, old_offset, new_size);
996	return;
997	};
998
999	switch (ni.position(mf)) {
1000	.header => {
1001	const shift = old_size - new_size;
1002
1003	try ni.setLocation(mf, gpa, old_offset, new_size);
1004
1005	// We need to shift backwards all header nodes following us.
1006	const next_header_ni = ni.next(mf).unwrap() orelse return;
1007	if (next_header_ni.position(mf) != .header) return;
1008
1009	var header_ni = next_header_ni;
1010	while (true) {
1011	const old_header_off, const old_header_size = header_ni.location(mf).resolve(mf);
1012	try header_ni.setLocation(mf, gpa, old_header_off - shift, old_header_size);
1013
1014	const next_ni = header_ni.next(mf).unwrap() orelse break;
1015	if (next_ni.position(mf) != .header) break;
1016	header_ni = next_ni;
1017	}
1018
1019	// Now we must shift the actual header bytes of those nodes backwards.
1020	const parent_file_off = parent_ni.fileLocation(mf, false).offset;
1021	const move_src_off = old_offset + old_size;
1022	const move_dest_off = old_offset + new_size;
1023	assert(next_header_ni.location(mf).resolve(mf)[0] == move_dest_off); // `move_dest_off` because we already updated the location
1024	const move_size = size: {
1025	// `header_ni` is the last header in the parent.
1026	const last_off, const last_size = header_ni.location(mf).resolve(mf);
1027	const move_end = last_off + last_size;
1028	break :size move_end - move_dest_off; // `move_dest_off` because we already updated the location
1029	};
1030	try mf.moveRange(
1031	parent_file_off + move_src_off,
1032	parent_file_off + move_dest_off,
1033	move_size,
1034	);
1035	},
1036	.floating => {
1037	try ni.setLocation(mf, gpa, old_offset, new_size);
1038	},
1039	.footer => {
1040	const shift = old_size - new_size;
1041
1042	const new_offset = old_offset + shift;
1043	try ni.setLocation(mf, gpa, new_offset, new_size);
1044
1045	const prev_footers_size = prev_footers_size: {
1046	// We need to shift forwards all footer nodes preceding us.
1047	const prev_footer_ni = ni.prev(mf).unwrap() orelse {
1048	break :prev_footers_size 0;
1049	};
1050	if (prev_footer_ni.position(mf) != .footer) {
1051	break :prev_footers_size 0;
1052	}
1053
1054	var footer_ni = prev_footer_ni;
1055	while (true) {
1056	const old_footer_off, const old_footer_size = footer_ni.location(mf).resolve(mf);
1057	try footer_ni.setLocation(mf, gpa, old_footer_off + shift, old_footer_size);
1058
1059	const prev_ni = footer_ni.prev(mf).unwrap() orelse break;
1060	if (prev_ni.position(mf) != .footer) break;
1061	footer_ni = prev_ni;
1062	}
1063
1064	// `footer_ni` is the first footer in the parent. This expression gets its *new*
1065	// offset because we already did the `setLocation` calls.
1066	const first_footer_new_offset = footer_ni.location(mf).resolve(mf)[0];
1067
1068	break :prev_footers_size new_offset - first_footer_new_offset;
1069	};
1070
1071	// Now we must shift the actual footer bytes forwards, including our own.
1072	const parent_file_offset = parent_ni.fileLocation(mf, false).offset;
1073	try mf.moveRange(
1074	parent_file_offset + old_offset - prev_footers_size,
1075	parent_file_offset + new_offset - prev_footers_size,
1076	prev_footers_size + new_size,
1077	);
1078	},
1079	}
1080	}
1081
1082	const GrowOptions = struct {
1083	/// If `true`, the node size must be set to exactly the given size.
1084	///
1085	/// If `false`, the given size is a minimum, and the actual new node size may be larger.
1086	exact_size: bool,
1087	/// If `true`, footers within the resized node will be moved forwards to its new end.
1088	///
1089	/// If `false`, footers will all remain at their current offsets (so the nodes are in a
1090	/// temporarily invalid state), and moving them is the responsibility of the *caller*.
1091	move_footers: bool,
1092	};
1093
1094	/// Increases the size of a node.
1095	///
1096	/// Asserts that `new_size` is aligned to `ni.alignment(mf)`, even if `!grow_options.exact_size`.
1097	///
1098	/// Asserts that `new_size` is greater than the current size of `ni`.
1099	fn growNode(
1100	mf: *MappedFile,
1101	gpa: Allocator,
1102	ni: Node.Index,
1103	new_size: u64,
1104	grow_options: GrowOptions,
1105	) Error!void {
1106	mf.nodes_lock.assertUnlocked();
1107
1108	const node = ni.get(mf);
1109
1110	const old_offset, const old_size = node.location().resolve(mf);
1111
1112	assert(node.flags.alignment.check(old_size));
1113	assert(node.flags.alignment.check(new_size));
1114	assert(new_size > old_size);
1115
1116	const parent_ni = node.parent.unwrap() orelse {
1117	assert(ni == .root);
1118
1119	if (try mf.growNodeViaInsertRange(gpa, ni, new_size, grow_options)) {
1120	return;
1121	}
1122
1123	mf.memory_map.write(mf.io) catch |err| {
1124	mf.io_err = switch (err) {
1125	error.Canceled => |e| return e,
1126	error.WouldBlock => error.Unexpected, // file was not opened as non-blocking
1127	error.NotOpenForWriting => error.Unexpected, // we definitely opened the file for writing
1128	else => |e| e,
1129	};
1130	return error.MappedFileIo;
1131	};
1132	mf.memory_map.file.setLength(mf.io, new_size) catch |err| switch (err) {
1133	error.Canceled => |e| return e,
1134	else => |e| {
1135	mf.io_err = e;
1136	return error.MappedFileIo;
1137	},
1138	};
1139	try mf.ensureTotalCapacityPrecise(@intCast(new_size));
1140	try ni.setLocation(mf, gpa, old_offset, new_size);
1141	if (grow_options.move_footers) {
1142	// We need to move any footers to be at the *new* end of the file.
1143	if (ni.firstFooter(mf).unwrap()) |first_footer_ni| {
1144	const old_footers_offset, _ = first_footer_ni.location(mf).resolve(mf);
1145	const footers_size = old_size - old_footers_offset;
1146	try mf.moveRange(
1147	old_footers_offset,
1148	old_footers_offset + (new_size - old_size),
1149	footers_size,
1150	);
1151	// Also update the footers' locations.
1152	var cur_ni = first_footer_ni;
1153	while (true) {
1154	const old_footer_offset, const footer_size = cur_ni.location(mf).resolve(mf);
1155	try cur_ni.setLocation(mf, gpa, old_footer_offset + (new_size - old_size), footer_size);
1156	cur_ni = cur_ni.next(mf).unwrap() orelse break;
1157	}
1158	}
1159	}
1160	return;
1161	};
1162
1163	switch (node.flags.position) {
1164	.header => {
1165	if (try mf.growNodeViaInsertRange(gpa, ni, new_size, grow_options)) {
1166	return;
1167	}
1168
1169	try mf.ensureAdditionalHeaderCapacity(gpa, parent_ni, new_size - old_size);
1170
1171	// `old_offset` is still valid because header nodes don't move when the parent resizes.
1172
1173	const last_header_ni: Node.Index = last_header: {
1174	var header_ni = ni;
1175	while (true) {
1176	const next_ni = header_ni.next(mf).unwrap() orelse break;
1177	if (next_ni.position(mf) != .header) break;
1178	header_ni = next_ni;
1179	}
1180	break :last_header header_ni;
1181	};
1182	const last_header_offset, const last_header_size = last_header_ni.location(mf).resolve(mf);
1183	const old_headers_size = last_header_offset + last_header_size;
1184
1185	// This is the first footer *inside* of `ni`.
1186	const first_sub_footer_oni: Node.Index.Optional = footer: {
1187	if (!grow_options.move_footers) {
1188	// Pretend there are no footers so as to not move them.
1189	break :footer .none;
1190	}
1191	break :footer ni.firstFooter(mf);
1192	};
1193	const sub_footers_size = size: {
1194	const first_sub_footer_ni = first_sub_footer_oni.unwrap() orelse break :size 0;
1195	const first_sub_footer_offset, _ = first_sub_footer_ni.location(mf).resolve(mf);
1196	break :size old_size - first_sub_footer_offset;
1197	};
1198
1199	// We need to shift two things forwards; any header nodes which follow us, and any
1200	// footer nodes *within* us (since they need to be at the end of our new size).
1201	const parent_file_offset = parent_ni.fileLocation(mf, false).offset;
1202	try mf.moveRange(
1203	parent_file_offset + old_offset + old_size - sub_footers_size,
1204	parent_file_offset + old_offset + new_size - sub_footers_size,
1205	old_headers_size - (old_offset + old_size - sub_footers_size),
1206	);
1207
1208	// Any footers inside of us have had their offsets changed due to us growing:
1209	if (first_sub_footer_oni.unwrap()) |first_sub_footer_ni| {
1210	var cur_ni = first_sub_footer_ni;
1211	while (true) {
1212	const old_sub_footer_offset, const sub_footer_size = cur_ni.location(mf).resolve(mf);
1213	try cur_ni.setLocation(
1214	mf,
1215	gpa,
1216	old_sub_footer_offset + (new_size - old_size),
1217	sub_footer_size,
1218	);
1219	cur_ni = cur_ni.next(mf).unwrap() orelse break;
1220	}
1221	}
1222
1223	// Update the offsets of all header nodes following us:
1224	{
1225	var moved_header_ni = last_header_ni;
1226	while (moved_header_ni != ni) {
1227	assert(moved_header_ni.position(mf) == .header);
1228	const moved_header_offset, const moved_header_size = moved_header_ni.location(mf).resolve(mf);
1229	try moved_header_ni.setLocation(
1230	mf,
1231	gpa,
1232	moved_header_offset - old_size + new_size,
1233	moved_header_size,
1234	);
1235	moved_header_ni = moved_header_ni.prev(mf).unwrap().?;
1236	}
1237	}
1238
1239	// Finally, update our own size:
1240	try ni.setLocation(mf, gpa, old_offset, new_size);
1241	return;
1242	},
1243	.floating => {
1244	try mf.growFloatingNodeWithAlignment(gpa, ni, null, new_size, grow_options);
1245	},
1246	.footer => {
1247	if (try mf.growNodeViaInsertRange(gpa, ni, new_size, grow_options)) {
1248	return;
1249	}
1250
1251	// This is the first footer *inside* of `ni` (unrelated to the fact that `ni` is itself
1252	// a footer within its parent). We'll need this later in any case, so just find it now.
1253	const first_sub_footer_oni: Node.Index.Optional = footer: {
1254	if (!grow_options.move_footers) {
1255	// Pretend there are no nested footers so as to not move them.
1256	break :footer .none;
1257	}
1258	break :footer ni.firstFooter(mf);
1259	};
1260
1261	// We have two different strategies for growing a footer node, with different advantages
1262	// and disadvantages; so first we must decide which to use.
1263	const strat: union(enum) {
1264	/// Expand into pre-footer padding space in the parent node (growing the parent if
1265	/// necessary). This strategy has the benefit that it can reclaim padding bytes in
1266	/// the parent, but it has the disadvantage that it requires moving this node's
1267	/// existing content backwards in the file, which may be expensive (particularly
1268	/// since the src and dest ranges are likely to overlap).
1269	grow_backwards,
1270
1271	/// Grow the parent node with `GrowOptions.move_footers` set to `false`, and
1272	/// implicitly grow ourselves into the newly available space. This usually requires
1273	/// a lot less moving of bytes, but never reclaims unused space before the parent's
1274	/// footers, and is sometimes straight-up impossible.
1275	grow_parent_at_end: struct {
1276	add_size: u64,
1277	exact_size: bool,
1278	},
1279	} = strat: {
1280	// If this node is small, the move overhead is trivial, so prefer `.grow_backwards`
1281	// to avoid unnecessary growth of the parent node.
1282	if (old_size <= mf.flags.block_size.toByteUnits() * 2) {
1283	break :strat .grow_backwards;
1284	}
1285
1286	// It may also be worth doing `.grow_backwards` if the parent has a *lot* of space
1287	// we could grow into. More specifically, if "free space we can grow into" makes up
1288	// a significant proportion of the parent's total size, then that implies the parent
1289	// has quite poor utilization of space, *and* that we can significantly improve that
1290	// statistic by growing into that space.
1291	if (old_size + mf.availableFooterCapacity(parent_ni) >= new_size) {
1292	break :strat .grow_backwards;
1293	}
1294
1295	if (grow_options.exact_size) {
1296	const add_size = new_size - old_size;
1297	if (parent_ni.alignment(mf).check(add_size)) {
1298	break :strat .{ .grow_parent_at_end = .{
1299	.add_size = add_size,
1300	.exact_size = true,
1301	} };
1302	} else {
1303	// We *can't* ask the parent to grow by this much, so we have no choice.
1304	break :strat .grow_backwards;
1305	}
1306	}
1307
1308	if (parent_ni.alignment(mf).compare(.lt, node.flags.alignment)) {
1309	// Because the parent's alignment is less than our own, if we gave them the
1310	// freedom to pick a size, they might choose one which results in *us* having a
1311	// size incompatible with our alignment. Therefore, to prevent that, we need to
1312	// request an *exact* size from the parent in this case.
1313	break :strat .{ .grow_parent_at_end = .{
1314	.add_size = new_size - old_size,
1315	.exact_size = true,
1316	} };
1317	}
1318
1319	// The parent's alignment is greater than or equal to our own, so we only need to
1320	// give the parent a *minimum* size (although we need to ensure it matches their
1321	// alignment since it could be greater than our own).
1322	break :strat .{ .grow_parent_at_end = .{
1323	.add_size = parent_ni.alignment(mf).forward(new_size - old_size),
1324	.exact_size = false,
1325	} };
1326	};
1327
1328	switch (strat) {
1329	.grow_backwards => {
1330	// First, we might need to grow the parent to make enough space.
1331	{
1332	const available_size = mf.availableFooterCapacity(parent_ni);
1333	if (old_size + available_size < new_size) {
1334	_, const old_parent_size: u64 = parent_ni.location(mf).resolve(mf);
1335	const min_parent_size = old_parent_size + (new_size - old_size - available_size);
1336	const new_parent_size = parent_ni.alignment(mf).forward(
1337	min_parent_size +| min_parent_size / growth_factor,
1338	);
1339	try mf.growNode(gpa, parent_ni, new_parent_size, .{
1340	.exact_size = false,
1341	.move_footers = true,
1342	});
1343	assert(old_size + mf.availableFooterCapacity(parent_ni) >= new_size);
1344	}
1345	}
1346
1347	// Now we need to grow! To do that, we must move `ni` itself, and every footer
1348	// before it in `parent_ni`, backwards. Unlike header nodes, `ni` is included in
1349	// the shift, because the bytes we're adding need to go at the *end* of `ni`
1350	// rather than its start.
1351
1352	// This is the same as `parent_ni.firstFooter(mf)`, it's just more efficient to
1353	// start at `ni` than to start at `parent_ni.last(mf)`.
1354	const first_parent_footer_ni: Node.Index = first_footer: {
1355	var footer_ni = ni;
1356	while (true) {
1357	const prev_ni = footer_ni.prev(mf).unwrap() orelse break;
1358	if (prev_ni.position(mf) != .footer) break;
1359	footer_ni = prev_ni;
1360	}
1361	break :first_footer footer_ni;
1362	};
1363
1364	const shift = new_size - old_size;
1365
1366	// Update our own offset and size:
1367	try ni.setLocation(
1368	mf,
1369	gpa,
1370	node.location().resolve(mf)[0] - shift,
1371	new_size,
1372	);
1373
1374	// Any footers *inside* of `ni` have had their offsets changed, because they are
1375	// now positioned at the *new* end of `ni`:
1376	{
1377	var footer_oni = first_sub_footer_oni;
1378	while (footer_oni.unwrap()) |footer_ni| : (footer_oni = footer_ni.next(mf)) {
1379	const old_footer_offset, const footer_size = footer_ni.location(mf).resolve(mf);
1380	try footer_ni.setLocation(mf, gpa, old_footer_offset + shift, footer_size);
1381	}
1382	}
1383
1384	// Any footers *before* `ni` (in `parent_ni`) have been shifted backwards. We'll
1385	// also be moving their actual bytes in a moment, so track whether they have
1386	// content (if nothing does then we'll be able to skip the `moveRange`). That
1387	// flag is initially whether `ni` has content because we're shifting our own
1388	// bytes backwards too.
1389	var moved_has_content: bool = node.flags.has_content;
1390	{
1391	var footer_ni = first_parent_footer_ni;
1392	while (footer_ni != ni) : (footer_ni = footer_ni.next(mf).unwrap().?) {
1393	moved_has_content = moved_has_content or footer_ni.get(mf).flags.has_content;
1394	const old_footer_offset, const footer_size = footer_ni.location(mf).resolve(mf);
1395	try footer_ni.setLocation(mf, gpa, old_footer_offset - shift, footer_size);
1396	}
1397	}
1398
1399	if (moved_has_content) {
1400	// We moved at least one thing containing initialized bytes, so we need to
1401	// move the actual data. However, we should *not* move the bytes of any
1402	// nested footers inside of `ni`, because they've been "moved" to the end
1403	// of our new size, which is the same file location as before.
1404	const sub_footers_size = size: {
1405	const first_sub_footer_ni = first_sub_footer_oni.unwrap() orelse break :size 0;
1406	const first_sub_footer_offset, _ = first_sub_footer_ni.location(mf).resolve(mf);
1407	break :size new_size - first_sub_footer_offset;
1408	};
1409	const new_offset: u64, _ = node.location().resolve(mf);
1410	const new_footers_offset: u64, _ = first_parent_footer_ni.location(mf).resolve(mf);
1411	const parent_file_offset = parent_ni.fileLocation(mf, false).offset;
1412	try mf.moveRange(
1413	parent_file_offset + new_footers_offset + shift,
1414	parent_file_offset + new_footers_offset,
1415	(new_offset - new_footers_offset) + // accounts for every footer before `ni`
1416	(old_size - sub_footers_size), // accounts for `ni` itself, excluding nested footers
1417	);
1418	}
1419	},
1420	.grow_parent_at_end => |grow_parent| {
1421	_, const old_parent_size: u64 = parent_ni.location(mf).resolve(mf);
1422	try mf.growNode(gpa, parent_ni, old_parent_size + grow_parent.add_size, .{
1423	.exact_size = grow_parent.exact_size,
1424	.move_footers = false,
1425	});
1426	_, const new_parent_size: u64 = parent_ni.location(mf).resolve(mf);
1427	const shift = new_parent_size - old_parent_size;
1428
1429	// Here's what we have left to do:
1430	//
1431	// * Increase our own size by `shift` to absorb the added space.
1432	//
1433	// * If there are any footers *inside* `ni`, increase their offsets by `shift`.
1434	//
1435	// * If there are any footers *after* `ni` (inside `parent_ni`), increase their
1436	// offsets by `shift`.
1437	//
1438	// * Do a `moveRange` corresponding to those offset changes. This is a single
1439	// range which starts at the footers *inside* `ni`.
1440
1441	const actual_new_size = old_size + shift;
1442	if (grow_options.exact_size) {
1443	assert(actual_new_size == new_size);
1444	}
1445
1446	try ni.setLocation(
1447	mf,
1448	gpa,
1449	node.location().resolve(mf)[0],
1450	actual_new_size,
1451	);
1452
1453	// This will track whether any node with a changed offset actually contains
1454	// initialized bytes. If not, there'll be no need to call `moveRange`.
1455	var moved_has_content: bool = false;
1456
1457	// Set any nested footers' offsets (and include them in `moved_has_content`).
1458	{
1459	var footer_oni = first_sub_footer_oni;
1460	while (footer_oni.unwrap()) |footer_ni| : (footer_oni = footer_ni.next(mf)) {
1461	assert(footer_ni.position(mf) == .footer);
1462	moved_has_content = moved_has_content or footer_ni.get(mf).flags.has_content;
1463	const footer_old_offset: u64, const footer_size: u64 = footer_ni.location(mf).resolve(mf);
1464	try footer_ni.setLocation(mf, gpa, footer_old_offset + shift, footer_size);
1465	}
1466	}
1467
1468	// Now set offsets for footers after `ni` inside of `parent_ni`.
1469	{
1470	var footer_oni = ni.next(mf);
1471	while (footer_oni.unwrap()) |footer_ni| : (footer_oni = footer_ni.next(mf)) {
1472	assert(footer_ni.position(mf) == .footer);
1473	moved_has_content = moved_has_content or footer_ni.get(mf).flags.has_content;
1474	const footer_old_offset: u64, const footer_size: u64 = footer_ni.location(mf).resolve(mf);
1475	try footer_ni.setLocation(mf, gpa, footer_old_offset + shift, footer_size);
1476	}
1477	}
1478
1479	if (moved_has_content) {
1480	// We moved at least one footer containing initialized bytes, so we need to
1481	// move the actual data. Compute how big the footers inside `ni` are...
1482	const sub_footers_size: u64 = size: {
1483	const first_sub_footer_ni = first_sub_footer_oni.unwrap() orelse break :size 0;
1484	const first_sub_footer_offset, _ = first_sub_footer_ni.location(mf).resolve(mf);
1485	// `actual_new_size` is used here since we already updated the nested footers' offsets above.
1486	break :size actual_new_size - first_sub_footer_offset;
1487	};
1488	// ...and how big the footers *after* `ni`, inside `parent_ni`, are...
1489	const post_footers_size: u64 = old_parent_size - (old_offset + old_size);
1490	// ...and move them both.
1491	const parent_file_off = parent_ni.fileLocation(mf, false).offset;
1492	const total_move_size = sub_footers_size + post_footers_size;
1493	assert(total_move_size != 0);
1494	try mf.moveRange(
1495	parent_file_off + old_parent_size - total_move_size,
1496	parent_file_off + new_parent_size - total_move_size,
1497	total_move_size,
1498	);
1499	}
1500	},
1501	}
1502	},
1503	}
1504	}
1505
1506	/// Moves a floating node to an unused region with the given size, which may be greater than the
1507	/// current size. If `new_alignment` is not `null`, then the offset and size of the new region will
1508	/// have that alignment instead of `ni.alignment(mf)`.
1509	///
1510	/// Asserts that `ni` is a floating node (and not `.root`).
1511	///
1512	/// Asserts that `new_size` is aligned to `new_alignment orelse ni.alignment(mf)`.
1513	///
1514	/// Asserts that `new_size` is greater than or equal to the current size of `ni`.
1515	fn growFloatingNodeWithAlignment(
1516	mf: *MappedFile,
1517	gpa: Allocator,
1518	ni: Node.Index,
1519	new_alignment: ?Alignment,
1520	new_size: u64,
1521	grow_options: GrowOptions,
1522	) Error!void {
1523	mf.nodes_lock.assertUnlocked();
1524
1525	const parent_ni = ni.parent(mf).unwrap().?; // `ni` cannot be `.root`
1526	const old_offset, const old_size = ni.location(mf).resolve(mf);
1527
1528	const alignment = new_alignment orelse ni.alignment(mf);
1529
1530	assert(new_size >= old_size);
1531	assert(ni.position(mf) == .floating);
1532	assert(alignment.check(new_size));
1533
1534	grow_in_place: {
1535	if (!alignment.check(old_offset)) {
1536	break :grow_in_place;
1537	}
1538	const limit: u64 = limit: {
1539	const next_ni = ni.next(mf).unwrap() orelse break :limit parent_ni.location(mf).resolve(mf)[1];
1540	const next_offset, _ = next_ni.location(mf).resolve(mf);
1541	break :limit next_offset;
1542	};
1543	if (old_offset + new_size > limit) {
1544	break :grow_in_place; // the parent is not big enough
1545	}
1546	// Great, we can grow this node without changing its offset or moving any siblings.
1547	try ni.setLocation(mf, gpa, old_offset, new_size);
1548	if (grow_options.move_footers) {
1549	// If we have any footers, we need to move them to the end of our new size, and update
1550	// their offsets accordingly.
1551	if (ni.firstFooter(mf).unwrap()) |first_footer_ni| {
1552	var cur_ni = first_footer_ni;
1553	var footers_have_content = false;
1554	while (true) {
1555	footers_have_content = footers_have_content or cur_ni.get(mf).flags.has_content;
1556	const old_footer_offset, const footer_size = cur_ni.location(mf).resolve(mf);
1557	try cur_ni.setLocation(mf, gpa, old_footer_offset + (new_size - old_size), footer_size);
1558	cur_ni = cur_ni.next(mf).unwrap() orelse break;
1559	}
1560	if (footers_have_content) {
1561	const parent_file_off = parent_ni.fileLocation(mf, false).offset;
1562	// This gets the *new* offset because we already updated the offsets above.
1563	const new_footers_offset, _ = first_footer_ni.location(mf).resolve(mf);
1564	const footers_size = new_size - new_footers_offset;
1565	try mf.moveRange(
1566	parent_file_off + old_offset + old_size - footers_size,
1567	parent_file_off + old_offset + new_size - footers_size,
1568	footers_size,
1569	);
1570	}
1571	}
1572	}
1573	return;
1574	}
1575
1576	const new_loc: struct {
1577	offset: u64,
1578	prev: Node.Index.Optional,
1579	} = new_loc: {
1580	_, const parent_size = parent_ni.location(mf).resolve(mf);
1581
1582	{
1583	// See if there's space at the start of the parent.
1584	const last_header_oni = parent_ni.lastHeader(mf);
1585	const headers_end: u64 = if (last_header_oni.unwrap()) |last_header_ni| headers_end: {
1586	const last_header_off, const last_header_size = last_header_ni.location(mf).resolve(mf);
1587	break :headers_end last_header_off + last_header_size;
1588	} else 0;
1589	const limit: u64 = limit: {
1590	const after_header_oni: Node.Index.Optional = after_header: {
1591	if (last_header_oni.unwrap()) |last_header_ni| {
1592	break :after_header last_header_ni.next(mf);
1593	}
1594	break :after_header parent_ni.first(mf);
1595	};
1596	if (after_header_oni.unwrap()) |after_header_ni| {
1597	break :limit after_header_ni.location(mf).resolve(mf)[0];
1598	} else {
1599	break :limit parent_size;
1600	}
1601	};
1602	if (alignment.forward(headers_end) + new_size <= limit) {
1603	// There's space here!
1604	break :new_loc .{
1605	// Put ourselves at the *end* of this range, so that the free space remains at the start of the parent.
1606	.offset = alignment.backward(limit - new_size),
1607	.prev = last_header_oni,
1608	};
1609	}
1610	}
1611
1612	// Otherwise, use space at the end of the parent, or make space there if necessary.
1613
1614	const first_footer_oni = parent_ni.firstFooter(mf);
1615
1616	// We know there is a node before the footer[s], because `ni` itself is such a node.
1617	const prev_ni: Node.Index = if (first_footer_oni.unwrap()) |first_footer_ni| prev: {
1618	break :prev first_footer_ni.prev(mf).unwrap().?;
1619	} else prev: {
1620	break :prev parent_ni.last(mf).unwrap().?;
1621	};
1622
1623	const result_offset: u64 = result_offset: {
1624	if (prev_ni == ni and alignment.check(old_offset)) {
1625	// We're already at the end of the parent, and our offset is already well-aligned.
1626	// The only reason we didn't simply grow in place earlier is that the parent wasn't
1627	// big enough---but now we're resizing the parent anyway, so growing in-place stops
1628	// us from unnecessarily moving!
1629	break :result_offset old_offset;
1630	}
1631	// Otherwise, just move after the last node.
1632	const prev_offset, const prev_size = prev_ni.location(mf).resolve(mf);
1633	break :result_offset alignment.forward(prev_offset + prev_size);
1634	};
1635
1636	const footers_size: u64 = if (first_footer_oni.unwrap()) |first_footer_ni| footers_size: {
1637	const first_footer_offset, _ = first_footer_ni.location(mf).resolve(mf);
1638	break :footers_size parent_size - first_footer_offset;
1639	} else 0;
1640
1641	const min_parent_size = result_offset + new_size + footers_size;
1642	if (parent_size < min_parent_size) {
1643	// Okay, at this point we're planning to expand the parent---so before we actually do
1644	// that, let's first try the Linux "insert range" fast path. We didn't try it before now
1645	// because it would have been more efficient to just move ourselves into existing space.
1646	//
1647	// If we were given a custom alignment, we need to set `GrowOptions.exact_size` for the
1648	// "insert range" path, because that function is unaware of `new_alignment`.
1649	const insert_range_grow_options: GrowOptions = .{
1650	.exact_size = grow_options.exact_size or new_alignment != null,
1651	.move_footers = grow_options.move_footers,
1652	};
1653	if (alignment.check(old_offset) and
1654	try mf.growNodeViaInsertRange(gpa, ni, new_size, insert_range_grow_options))
1655	{
1656	// The Linux fast path did our job for us!
1657	return;
1658	}
1659
1660	// Grow the parent and move to the end of the parent.
1661	const new_parent_size = parent_ni.alignment(mf).forward(
1662	min_parent_size +| min_parent_size / growth_factor,
1663	);
1664	try mf.growNode(gpa, parent_ni, new_parent_size, .{
1665	.exact_size = false,
1666	.move_footers = true,
1667	});
1668	}
1669
1670	break :new_loc .{
1671	.offset = result_offset,
1672	.prev = .wrap(prev_ni),
1673	};
1674	};
1675
1676	// We've found our new location in `parent_ni`, now to actually move ourselves there.
1677
1678	// Footers need to move to a different place than the rest of our content.
1679	const footers_size: u64, const footers_have_content: bool = footers: {
1680	if (!grow_options.move_footers) {
1681	// Pretend there are no footers so as to not move them.
1682	break :footers .{ 0, false };
1683	}
1684	const first_footer_ni = ni.firstFooter(mf).unwrap() orelse {
1685	break :footers .{ 0, false };
1686	};
1687
1688	var cur_ni = first_footer_ni;
1689	var footers_have_content = false;
1690	while (true) {
1691	footers_have_content = footers_have_content or cur_ni.get(mf).flags.has_content;
1692	const old_footer_offset, const footer_size = cur_ni.location(mf).resolve(mf);
1693	// Our footers' offsets must change to be at the end of our new size.
1694	try cur_ni.setLocation(mf, gpa, old_footer_offset + (new_size - old_size), footer_size);
1695	cur_ni = cur_ni.next(mf).unwrap() orelse break;
1696	}
1697
1698	// This is the *new* offset because we already updated the offsets above.
1699	const new_footers_offset, _ = first_footer_ni.location(mf).resolve(mf);
1700	const footers_size = new_size - new_footers_offset;
1701
1702	break :footers .{ footers_size, footers_have_content };
1703	};
1704
1705	if (ni.get(mf).flags.has_content) {
1706	const parent_file_off = parent_ni.fileLocation(mf, false).offset;
1707	try mf.moveRange(
1708	parent_file_off + old_offset,
1709	parent_file_off + new_loc.offset,
1710	old_size - footers_size,
1711	);
1712	if (footers_have_content) try mf.moveRange(
1713	parent_file_off + old_offset + old_size - footers_size,
1714	parent_file_off + new_loc.offset + new_size - footers_size,
1715	footers_size,
1716	);
1717	} else {
1718	assert(!footers_have_content);
1719	}
1720
1721	try ni.setLocation(mf, gpa, new_loc.offset, new_size);
1722
1723	if (new_loc.prev != ni.toOptional()) {
1724	// We're potentially in a different place in `parent_ni`'s child list, so remove and re-add ourselves.
1725	try mf.removeNodesFromChildList(gpa, ni, ni);
1726	try mf.addNodesToChildListAfter(gpa, new_loc.prev, ni, ni);
1727	}
1728	}
1729
1730	/// Attempts to grow `ni` to `new_size` using `FALLOCATE_FL_INSERT_RANGE` on Linux. This strategy
1731	/// has the advantage that it does not require manually moving any bytes in the file, but has the
1732	/// disadvantages that it may increase the file size more than necessary, and that it changes the
1733	/// offsets of all following nodes, recursively.
1734	///
1735	/// If this strategy is inapplicable or unsuitable for this operation, this function returns `false`
1736	/// without changing any nodes' locations or invalidating any slices.
1737	///
1738	/// Otherwise, this function grows `ni` to `new_size` (maybe larger if `!grow_options.exact_size`),
1739	/// updates the location of `ni` and every node whose offset has changed, and returns `true`.
1740	fn growNodeViaInsertRange(
1741	mf: *MappedFile,
1742	gpa: Allocator,
1743	ni: Node.Index,
1744	new_size: u64,
1745	grow_options: GrowOptions,
1746	) Error!bool {
1747	if (!is_linux or mf.flags.fallocate_insert_range_unsupported) {
1748	return false;
1749	}
1750
1751	_, const old_size = ni.location(mf).resolve(mf);
1752
1753	// We don't compute the size of the range yet, because depending on `grow_options` we might want
1754	// to bump it based on our sibling and parent nodes' alignments. However, we can do an early
1755	// check for cases where we should obviously exit.
1756	const min_range_size: u64 = s: {
1757	const requested_size = new_size - old_size;
1758	if (mf.flags.block_size.check(requested_size)) {
1759	break :s requested_size;
1760	}
1761	if (!grow_options.exact_size and
1762	requested_size >= mf.flags.block_size.toByteUnits() * 2)
1763	{
1764	// We're growing by at least a few blocks, so allow ourselves to bump the size
1765	// slightly to give it the needed alignment.
1766	break :s mf.flags.block_size.forward(requested_size);
1767	}
1768	return false;
1769	};
1770	assert(min_range_size > 0);
1771	assert(mf.flags.block_size.check(min_range_size));
1772
1773	const range_file_offset: u64 = range_file_offset: {
1774	const node_file_offset = ni.fileLocation(mf, false).offset;
1775	const last_ni = ni.last(mf).unwrap() orelse {
1776	// If `ni` has no children (i.e. is a leaf node), we need to insert exactly at its end.
1777	const range_file_offset = node_file_offset + old_size;
1778	if (!mf.flags.block_size.check(range_file_offset)) {
1779	return false;
1780	}
1781	break :range_file_offset range_file_offset;
1782	};
1783	const pre_footer_oni: Node.Index.Optional, const footers_size: u64 = footers: {
1784	if (!grow_options.move_footers) {
1785	// Pretend there are no footers so as to not move them.
1786	break :footers .{ .wrap(last_ni), 0 };
1787	}
1788	const first_footer_ni = ni.firstFooter(mf).unwrap() orelse {
1789	break :footers .{ .wrap(last_ni), 0 };
1790	};
1791	const first_footer_offset, _ = first_footer_ni.location(mf).resolve(mf);
1792	break :footers .{ first_footer_ni.prev(mf), old_size - first_footer_offset };
1793	};
1794	const pre_footer_end: u64 = if (pre_footer_oni.unwrap()) |pre_footer_ni| end: {
1795	const pre_footer_off, const pre_footer_size = pre_footer_ni.location(mf).resolve(mf);
1796	break :end pre_footer_off + pre_footer_size;
1797	} else 0;
1798
1799	const min_file_offset = node_file_offset + pre_footer_end;
1800	const max_file_offset = node_file_offset + old_size - footers_size;
1801	// We can go anywhere between `min_file_offset` and `max_file_offset`.
1802	const candidate_file_offset = mf.flags.block_size.forward(min_file_offset);
1803	if (candidate_file_offset > max_file_offset) {
1804	return false;
1805	}
1806	break :range_file_offset candidate_file_offset;
1807	};
1808	assert(mf.flags.block_size.check(range_file_offset));
1809
1810	const range_size: u64 = range_size: {
1811	// For this strategy to be valid, the number of bytes we insert needs to be compatible with
1812	// the alignments of all nodes following us (and following our parents, their parents, etc).
1813	// We also probably don't want to trigger too many "node moved" events, since doing that
1814	// repeatedly could result in a lot of extra work. Therefore, while we traverse parents and
1815	// siblings to check their alignment requirements, we will also set an arbitrary limit on
1816	// the number of nodes we can move, and give up if we walk more than that.
1817	const max_moved_nodes = 32;
1818	var num_moved: u32 = 0;
1819	var cur_ni = ni;
1820	// Alignment required for `range_size`: initially the block size (required for the syscall),
1821	// then updated as we traverse based on how the operation would affect surrounding nodes.
1822	var need_range_align: Alignment = mf.flags.block_size.max(ni.alignment(mf));
1823	while (true) {
1824	// `cur_ni` will grow as a result of the range insertion. Its size must be well-aligned.
1825	need_range_align = need_range_align.max(cur_ni.alignment(mf));
1826
1827	// Siblings following `cur_ni` don't get bigger, but their offsets change.
1828	while (cur_ni.next(mf).unwrap()) |next_ni| {
1829	// Only floating children need well-aligned offsets.
1830	if (next_ni.position(mf) == .floating) {
1831	need_range_align = need_range_align.max(next_ni.alignment(mf));
1832	}
1833	num_moved += 1;
1834	if (num_moved > max_moved_nodes) return false;
1835	cur_ni = next_ni;
1836	}
1837
1838	// Move up to the parent.
1839	cur_ni = cur_ni.parent(mf).unwrap() orelse break;
1840	}
1841	// Traversal done. We didn't hit `max_moved_nodes`, so now we can use the computed alignment
1842	// requirement to figure out whether we're actually going to insert a range.
1843	if (need_range_align.check(min_range_size)) {
1844	break :range_size min_range_size;
1845	}
1846	// Perhaps we're allowed to grow by more than `min_range_size`?
1847	const candidate_range_size = need_range_align.forward(min_range_size);
1848	if (!grow_options.exact_size and
1849	// Allow growing by up to 50% more than was requested.
1850	candidate_range_size <= min_range_size +| min_range_size / 2)
1851	{
1852	break :range_size candidate_range_size;
1853	}
1854	return false;
1855	};
1856
1857	// This `range_size` is compatible with everyone's alignment requirements, and we won't move too
1858	// many nodes, so let's do it!
1859
1860	mf.memory_map.write(mf.io) catch |err| {
1861	mf.io_err = switch (err) {
1862	error.Canceled => |e| return e,
1863	error.WouldBlock => error.Unexpected, // file was not opened as non-blocking
1864	error.NotOpenForWriting => error.Unexpected, // we definitely opened the file for writing
1865	else => |e| e,
1866	};
1867	return error.MappedFileIo;
1868	};
1869
1870	// If we happen to be inserting at the very end of the file, we need to resize the file instead
1871	// of using `FALLOCATE_FL_INSERT_RANGE`.
1872	if (range_file_offset == Node.Index.root.location(mf).resolve(mf)[1]) {
1873	mf.memory_map.file.setLength(mf.io, range_file_offset + range_size) catch |err| switch (err) {
1874	error.Canceled => |e| return e,
1875	else => |e| {
1876	mf.io_err = e;
1877	return error.MappedFileIo;
1878	},
1879	};
1880	} else {
1881	while (true) switch (linux.errno(linux.fallocate(
1882	mf.memory_map.file.handle,
1883	linux.FALLOC.FL_INSERT_RANGE,
1884	@intCast(range_file_offset),
1885	@intCast(range_size),
1886	))) {
1887	.SUCCESS => break,
1888	.INTR => continue,
1889	.NOSYS, .OPNOTSUPP => {
1890	// After all that setup work, it turns out the operation is actually unsupported!
1891	mf.flags.fallocate_insert_range_unsupported = true;
1892	return false;
1893	},
1894	else => |e| {
1895	mf.io_err = switch (e) {
1896	.SUCCESS, .INTR, .NOSYS, .OPNOTSUPP => unreachable, // handled above
1897	.BADF => unreachable,
1898	.FBIG => unreachable,
1899	.INVAL => unreachable,
1900	.IO => error.InputOutput,
1901	.NODEV => error.NotFile,
1902	.NOSPC => error.NoSpaceLeft,
1903	.PERM => error.PermissionDenied,
1904	.SPIPE => error.Unseekable,
1905	.TXTBSY => error.FileBusy,
1906	else => std.posix.unexpectedErrno(e),
1907	};
1908	return error.MappedFileIo;
1909	},
1910	};
1911	}
1912
1913	// We did it! Now to update all the sizes and offsets. This loop is exactly the same shape as
1914	// above, except we're updating locations instead of checking alignments.
1915	var cur_ni = ni;
1916	while (true) {
1917	const this_offset, const this_old_size = cur_ni.location(mf).resolve(mf);
1918	if (cur_ni == .root) {
1919	try mf.ensureTotalCapacityPrecise(@intCast(this_old_size + range_size));
1920	}
1921	try cur_ni.setLocation(mf, gpa, this_offset, this_old_size + range_size);
1922
1923	while (cur_ni.next(mf).unwrap()) |next_ni| {
1924	const next_old_offset, const next_size = next_ni.location(mf).resolve(mf);
1925	try next_ni.setLocation(mf, gpa, next_old_offset + range_size, next_size);
1926	cur_ni = next_ni;
1927	}
1928
1929	cur_ni = cur_ni.parent(mf).unwrap() orelse break;
1930	}
1931
1932	if (grow_options.move_footers) {
1933	// The only thing left is to update the offsets of any footers inside of `ni`.
1934	if (ni.firstFooter(mf).unwrap()) |first_footer_ni| {
1935	var footer_ni = first_footer_ni;
1936	while (true) {
1937	const old_footer_offset, const footer_size = footer_ni.location(mf).resolve(mf);
1938	try footer_ni.setLocation(mf, gpa, old_footer_offset + range_size, footer_size);
1939	footer_ni = footer_ni.next(mf).unwrap() orelse break;
1940	}
1941	}
1942	}
1943
1944	return true;
1945	}
1946
1947	/// Ensures that `parent_ni` has at least `extra_capacity` padding bytes following its current
1948	/// headers, so that the headers can grow into that space.
1949	fn ensureAdditionalHeaderCapacity(
1950	mf: *MappedFile,
1951	gpa: Allocator,
1952	parent_ni: Node.Index,
1953	extra_capacity: u64,
1954	) Error!void {
1955	_, const parent_size = parent_ni.location(mf).resolve(mf);
1956
1957	const last_header_oni = parent_ni.lastHeader(mf);
1958	const first_footer_oni = parent_ni.firstFooter(mf);
1959
1960	const headers_size: u64 = headers_size: {
1961	const last_header_ni = last_header_oni.unwrap() orelse break :headers_size 0;
1962	const last_header_off, const last_header_size = last_header_ni.location(mf).resolve(mf);
1963	break :headers_size last_header_off + last_header_size;
1964	};
1965
1966	const footers_size: u64 = footers_size: {
1967	const first_footer_ni = first_footer_oni.unwrap() orelse break :footers_size 0;
1968	const first_footer_off, _ = first_footer_ni.location(mf).resolve(mf);
1969	break :footers_size parent_size - first_footer_off;
1970	};
1971
1972	const first_floating_oni: Node.Index.Optional = if (last_header_oni.unwrap()) |last_header_ni| first_floating: {
1973	const after_header_ni = last_header_ni.next(mf).unwrap() orelse break :first_floating .none;
1974	break :first_floating switch (after_header_ni.position(mf)) {
1975	.header => unreachable,
1976	.floating => .wrap(after_header_ni),
1977	.footer => .none,
1978	};
1979	} else first_floating: {
1980	const first_ni = parent_ni.first(mf).unwrap() orelse break :first_floating .none;
1981	break :first_floating switch (first_ni.position(mf)) {
1982	.header => unreachable,
1983	.floating => .wrap(first_ni),
1984	.footer => .none,
1985	};
1986	};
1987	const first_floating_ni = first_floating_oni.unwrap() orelse {
1988	// This node has only headers and footers.
1989	const min_parent_size = headers_size + extra_capacity + footers_size;
1990	if (parent_size < min_parent_size) {
1991	const new_parent_size = parent_ni.alignment(mf).forward(
1992	min_parent_size +| min_parent_size / growth_factor,
1993	);
1994	try mf.growNode(gpa, parent_ni, new_parent_size, .{
1995	.exact_size = false,
1996	.move_footers = true,
1997	});
1998	}
1999	return;
2000	};
2001
2002	const last_floating_ni = if (first_footer_oni.unwrap()) |first_footer_ni| last_floating: {
2003	break :last_floating first_footer_ni.prev(mf).unwrap().?;
2004	} else last_floating: {
2005	break :last_floating parent_ni.last(mf).unwrap().?;
2006	};
2007	assert(last_floating_ni.position(mf) == .floating); // we know `parent_ni` contains at least `first_floating_ni`
2008
2009	// Find the first floating child, if any, which does not overlap the new header space.
2010	const first_good_floating_oni: Node.Index.Optional = first_good_floating: {
2011	var floating_ni = first_floating_ni;
2012	while (true) {
2013	const floating_offset, _ = floating_ni.location(mf).resolve(mf);
2014	if (floating_offset >= headers_size + extra_capacity) {
2015	break :first_good_floating .wrap(floating_ni);
2016	}
2017	const next_ni = floating_ni.next(mf).unwrap() orelse {
2018	break :first_good_floating .none;
2019	};
2020	switch (next_ni.position(mf)) {
2021	.header => unreachable, // after the last header
2022	.floating => floating_ni = next_ni,
2023	.footer => break :first_good_floating .none,
2024	}
2025	}
2026	};
2027
2028	if (first_good_floating_oni == first_floating_ni.toOptional()) {
2029	// None of the floating children are in our way! That means there's already enough space.
2030	return;
2031	}
2032
2033	const last_moving_ni = if (first_good_floating_oni.unwrap()) |first_good_floating_ni| last_moving: {
2034	break :last_moving first_good_floating_ni.prev(mf).unwrap().?;
2035	} else last_moving: {
2036	break :last_moving last_floating_ni;
2037	};
2038
2039	// We are going to move all nodes between `first_floating_ni` and `last_moving_ni` to the end of
2040	// the parent. We'll move all the node data in one big block.
2041
2042	const moving_offset: u64 = first_floating_ni.location(mf).resolve(mf)[0];
2043	const moving_size: u64 = size: {
2044	const last_moving_off, const last_moving_size = last_moving_ni.location(mf).resolve(mf);
2045	break :size last_moving_off + last_moving_size - moving_offset;
2046	};
2047
2048	var moving_alignment: Alignment = .@"1";
2049	var moving_has_content = false; // optimization: no need to move data if it's all uninitialized
2050	{
2051	var cur_ni = first_floating_ni;
2052	while (true) {
2053	moving_alignment = moving_alignment.max(cur_ni.alignment(mf));
2054	moving_has_content = moving_has_content or cur_ni.get(mf).flags.has_content;
2055	if (cur_ni == last_moving_ni) break;
2056	cur_ni = cur_ni.next(mf).unwrap().?;
2057	}
2058	}
2059
2060	const first_free_offset = free_offset: {
2061	const last_floating_off, const last_floating_size = last_floating_ni.location(mf).resolve(mf);
2062	break :free_offset @max(last_floating_off + last_floating_size, headers_size + extra_capacity);
2063	};
2064	// Alignment is a little tricky here. We don't necessarily want the new offset to be aligned to
2065	// `moving_alignment` exactly, because if (e.g.) the first floating node is align(2) and the
2066	// second is align(4), then the overall range we're moving may not be 4-byte aligned even though
2067	// one of the nodes is. Instead, the old and new offsets must be congruent modulo the alignment.
2068	const aligned_dest_offset = moving_alignment.forward(first_free_offset);
2069	const dest_offset = aligned_dest_offset + (moving_offset - moving_alignment.backward(moving_offset));
2070	assert(dest_offset % moving_alignment.toByteUnits() == moving_offset % moving_alignment.toByteUnits());
2071
2072	// This expression is correct because `dest_offset` is after all floating nodes (except the ones
2073	// we're moving there of course).
2074	const min_parent_size = dest_offset + moving_size + footers_size;
2075	if (parent_size < min_parent_size) {
2076	const new_parent_size = parent_ni.alignment(mf).forward(
2077	min_parent_size +| min_parent_size / growth_factor,
2078	);
2079	try mf.growNode(gpa, parent_ni, new_parent_size, .{
2080	.exact_size = false,
2081	.move_footers = true,
2082	});
2083	}
2084
2085	if (moving_has_content) {
2086	const parent_file_off = parent_ni.fileLocation(mf, false).offset;
2087	try mf.moveRange(
2088	parent_file_off + moving_offset,
2089	parent_file_off + dest_offset,
2090	moving_size,
2091	);
2092	}
2093
2094	// Remove everything between `first_floating_ni` and `last_moving_ni` from the linked list, then
2095	// re-insert them in their new position.
2096	try mf.removeNodesFromChildList(gpa, first_floating_ni, last_moving_ni);
2097	try mf.addNodesToChildListBefore(gpa, first_footer_oni, first_floating_ni, last_moving_ni);
2098
2099	// Finally, we need to update the locations of all of those nodes.
2100	var cur_ni = first_floating_ni;
2101	while (true) {
2102	assert(cur_ni.position(mf) == .floating);
2103	const old_offset, const old_size = cur_ni.location(mf).resolve(mf);
2104	const new_offset = old_offset - moving_offset + dest_offset;
2105	assert(cur_ni.alignment(mf).check(new_offset));
2106	try cur_ni.setLocation(mf, gpa, new_offset, old_size);
2107	if (cur_ni == last_moving_ni) break;
2108	cur_ni = cur_ni.next(mf).unwrap().?;
2109	}
2110	}
2111
2112	/// Returns how many padding bytes `parent_ni` currently has directly preceding its footers, which
2113	/// footers can therefore grow into.
2114	fn availableFooterCapacity(mf: *const MappedFile, parent_ni: Node.Index) u64 {
2115	const first_footer_oni = parent_ni.firstFooter(mf);
2116
2117	const before_footers_oni: Node.Index.Optional, const footers_off: u64 = footers: {
2118	const first_footer_ni = first_footer_oni.unwrap() orelse {
2119	_, const parent_size = parent_ni.location(mf).resolve(mf);
2120	break :footers .{ parent_ni.last(mf), parent_size };
2121	};
2122	const first_footer_off, _ = first_footer_ni.location(mf).resolve(mf);
2123	break :footers .{ first_footer_ni.prev(mf), first_footer_off };
2124	};
2125
2126	const header_and_floating_end: u64 = end: {
2127	const before_footers_ni = before_footers_oni.unwrap() orelse break :end 0;
2128	const offset, const size = before_footers_ni.location(mf).resolve(mf);
2129	break :end offset + size;
2130	};
2131
2132	return footers_off - header_and_floating_end;
2133	}
2134
2135	fn removeNodesFromChildList(
2136	mf: *MappedFile,
2137	gpa: Allocator,
2138	first_remove_ni: Node.Index,
2139	last_remove_ni: Node.Index,
2140	) Allocator.Error!void {
2141	const parent_ni = first_remove_ni.parent(mf).unwrap().?;
2142	assert(last_remove_ni.parent(mf).unwrap().? == parent_ni);
2143
2144	const prev_oni = first_remove_ni.prev(mf);
2145	const next_oni = last_remove_ni.next(mf);
2146
2147	if (prev_oni.unwrap()) |prev_ni| {
2148	assert(prev_ni.next(mf).unwrap().? == first_remove_ni);
2149	try prev_ni.setNext(gpa, next_oni, mf);
2150	} else {
2151	assert(parent_ni.first(mf).unwrap().? == first_remove_ni);
2152	parent_ni.get(mf).first = next_oni;
2153	}
2154
2155	if (next_oni.unwrap()) |next_ni| {
2156	assert(next_ni.prev(mf).unwrap().? == last_remove_ni);
2157	next_ni.get(mf).prev = prev_oni;
2158	} else {
2159	assert(parent_ni.last(mf).unwrap().? == last_remove_ni);
2160	parent_ni.get(mf).last = prev_oni;
2161	}
2162	}
2163	/// Assumes `first_add_ni` and `last_add_ni` are connected, and that all nodes in between them
2164	/// already have their `parent` field correctly populated.
2165	///
2166	/// To add a single node, set `first_add_ni` equal to `last_add_ni`.
2167	fn addNodesToChildListBefore(
2168	mf: *MappedFile,
2169	gpa: Allocator,
2170	/// `null` means to add at the end of the parent.
2171	next_oni: Node.Index.Optional,
2172	first_add_ni: Node.Index,
2173	last_add_ni: Node.Index,
2174	) Allocator.Error!void {
2175	const parent_ni = first_add_ni.parent(mf).unwrap().?;
2176	assert(last_add_ni.parent(mf).unwrap().? == parent_ni);
2177	if (next_oni.unwrap()) |next_ni| {
2178	assert(next_ni.parent(mf).unwrap().? == parent_ni);
2179	}
2180
2181	const prev_oni: Node.Index.Optional = if (next_oni.unwrap()) |next_ni| prev: {
2182	break :prev next_ni.prev(mf);
2183	} else prev: {
2184	break :prev parent_ni.last(mf);
2185	};
2186
2187	first_add_ni.get(mf).prev = prev_oni;
2188	try last_add_ni.setNext(gpa, next_oni, mf);
2189
2190	if (prev_oni.unwrap()) |prev_ni| {
2191	assert(prev_ni.next(mf) == next_oni);
2192	try prev_ni.setNext(gpa, .wrap(first_add_ni), mf);
2193	} else {
2194	assert(parent_ni.first(mf) == next_oni);
2195	parent_ni.get(mf).first = .wrap(first_add_ni);
2196	}
2197
2198	if (next_oni.unwrap()) |next_ni| {
2199	assert(next_ni.prev(mf) == prev_oni);
2200	next_ni.get(mf).prev = .wrap(last_add_ni);
2201	} else {
2202	assert(parent_ni.last(mf) == prev_oni);
2203	parent_ni.get(mf).last = .wrap(last_add_ni);
2204	}
2205	}
2206	fn addNodesToChildListAfter(
2207	mf: *MappedFile,
2208	gpa: Allocator,
2209	/// `null` means to add at the start of the parent.
2210	prev_oni: Node.Index.Optional,
2211	first_add_ni: Node.Index,
2212	last_add_ni: Node.Index,
2213	) Allocator.Error!void {
2214	const next_oni: Node.Index.Optional = next: {
2215	if (prev_oni.unwrap()) |prev_ni| break :next prev_ni.next(mf);
2216	const parent_ni = first_add_ni.parent(mf).unwrap().?;
2217	break :next parent_ni.first(mf);
2218	};
2219	return mf.addNodesToChildListBefore(gpa, next_oni, first_add_ni, last_add_ni);
2220	}
2221
2222	fn realignNode(
2223	mf: *MappedFile,
2224	gpa: Allocator,
2225	ni: Node.Index,
2226	new_align: Alignment,
2227	) Error!void {
2228	mf.nodes_lock.assertUnlocked();
2229
2230	const old_offset, const old_size = ni.location(mf).resolve(mf);
2231
2232	if (ni == .root or ni.position(mf) != .floating) {
2233	// Only this node's size is aligned, not its offset.
2234	if (!new_align.check(old_size)) {
2235	assert(new_align.compare(.gt, ni.alignment(mf)));
2236	try mf.growNode(gpa, ni, new_align.forward(old_size), .{
2237	.exact_size = true, // because `growNode` is not aware that the size needs to match `new_align`
2238	.move_footers = true,
2239	});
2240	}
2241	} else {
2242	// This is a floating node, so its size and offset are both aligned.
2243	if (!new_align.check(old_offset) or !new_align.check(old_size)) {
2244	assert(new_align.compare(.gt, ni.alignment(mf)));
2245	try mf.growFloatingNodeWithAlignment(gpa, ni, new_align, new_align.forward(old_size), .{
2246	.exact_size = false,
2247	.move_footers = true,
2248	});
2249	}
2250	}
2251
2252	ni.get(mf).flags.alignment = new_align;
2253	}
2254
2255	fn updateWriters(mf: *MappedFile) void {
2256	var writers_it = mf.writers.first;
2257	while (writers_it) |writer_node| : (writers_it = writer_node.next) {
2258	const w: *Node.Writer = @fieldParentPtr("writer_node", writer_node);
2259	w.interface.buffer = w.ni.slice(mf);
2260	}
2261	}
2262
2263	fn moveRange(mf: *MappedFile, old_file_offset: u64, new_file_offset: u64, size: u64) Error!void {
2264	if (old_file_offset == new_file_offset) return;
2265
2266	if (old_file_offset >= new_file_offset + size or
2267	new_file_offset >= old_file_offset + size)
2268	{
2269	const n = try mf.copyFileRange(
2270	mf.memory_map.file,
2271	old_file_offset,
2272	new_file_offset,
2273	size,
2274	);
2275	@memcpy(
2276	mf.memory_map.memory[@intCast(new_file_offset + n)..][0..@intCast(size - n)],
2277	mf.memory_map.memory[@intCast(old_file_offset + n)..][0..@intCast(size - n)],
2278	);
2279
2280	try mf.zeroRange(old_file_offset, size);
2281
2282	return;
2283	}
2284
2285	// TODO: if the non-overlapping region is greater than or equal to a filesystem block, is it
2286	// ever worth doing multiple `copyFileRange` calls instead of a big `@memmove`?
2287
2288	@memmove(
2289	mf.memory_map.memory[@intCast(new_file_offset)..][0..@intCast(size)],
2290	mf.memory_map.memory[@intCast(old_file_offset)..][0..@intCast(size)],
2291	);
2292
2293	if (new_file_offset > old_file_offset) {
2294	const clear_size = new_file_offset - old_file_offset;
2295	assert(clear_size < size);
2296	try mf.zeroRange(old_file_offset, clear_size);
2297	} else {
2298	const clear_size = old_file_offset - new_file_offset;
2299	assert(clear_size < size);
2300	try mf.zeroRange(new_file_offset + size, clear_size);
2301	}
2302	}
2303	fn zeroRange(mf: *MappedFile, file_offset: u64, size: u64) Error!void {
2304	if (is_linux and
2305	!mf.flags.fallocate_punch_hole_unsupported and
2306	size >= mf.flags.block_size.toByteUnits() * 2 - 1)
2307	{
2308	while (true) switch (linux.errno(linux.fallocate(
2309	mf.memory_map.file.handle,
2310	linux.FALLOC.FL_PUNCH_HOLE | linux.FALLOC.FL_KEEP_SIZE,
2311	@intCast(file_offset),
2312	@intCast(size),
2313	))) {
2314	.SUCCESS => return,
2315	.INTR => continue,
2316	.NOSYS, .OPNOTSUPP => {
2317	mf.flags.fallocate_punch_hole_unsupported = true;
2318	break; // fall back to slow path
2319	},
2320	else => |e| {
2321	mf.io_err = switch (e) {
2322	.SUCCESS, .INTR, .NOSYS, .OPNOTSUPP => unreachable, // handled above
2323	.BADF => unreachable,
2324	.FBIG => unreachable,
2325	.INVAL => unreachable,
2326	.IO => error.InputOutput,
2327	.NODEV => error.NotFile,
2328	.NOSPC => error.NoSpaceLeft,
2329	.PERM => error.PermissionDenied,
2330	.SPIPE => error.Unseekable,
2331	.TXTBSY => error.FileBusy,
2332	else => std.posix.unexpectedErrno(e),
2333	};
2334	return error.MappedFileIo;
2335	},
2336	};
2337	}
2338	@memset(mf.memory_map.memory[@intCast(file_offset)..][0..@intCast(size)], 0);
2339	}
2340	fn copyFileRange(
2341	mf: *MappedFile,
2342	old_file: Io.File,
2343	old_file_offset: u64,
2344	new_file_offset: u64,
2345	size: u64,
2346	) Error!u64 {
2347	if (!is_linux or mf.flags.copy_file_range_unsupported) {
2348	return 0;
2349	}
2350
2351	const min_size = mf.flags.block_size.toByteUnits() * 2 - 1;
2352	if (size < min_size) return 0;
2353
2354	const io = mf.io;
2355	mf.memory_map.write(io) catch |err| {
2356	mf.io_err = switch (err) {
2357	error.Canceled => |e| return e,
2358	error.WouldBlock => error.Unexpected, // file was not opened as non-blocking
2359	error.NotOpenForWriting => error.Unexpected, // we definitely opened the file for writing
2360	else => |e| e,
2361	};
2362	return error.MappedFileIo;
2363	};
2364	var remaining_size = size;
2365	var old_file_offset_mut: i64 = @intCast(old_file_offset);
2366	var new_file_offset_mut: i64 = @intCast(new_file_offset);
2367	while (remaining_size >= min_size) {
2368	const copy_len = linux.copy_file_range(
2369	old_file.handle,
2370	&old_file_offset_mut,
2371	mf.memory_map.file.handle,
2372	&new_file_offset_mut,
2373	@intCast(remaining_size),
2374	0,
2375	);
2376	switch (linux.errno(copy_len)) {
2377	.SUCCESS => {
2378	if (copy_len == 0) break;
2379	remaining_size -= copy_len;
2380	if (remaining_size == 0) break;
2381	},
2382	.INTR => continue,
2383	.NOSYS, .OPNOTSUPP, .XDEV => {
2384	mf.flags.copy_file_range_unsupported = true;
2385	break;
2386	},
2387	else => |e| {
2388	mf.io_err = switch (e) {
2389	.SUCCESS, .INTR, .NOSYS, .OPNOTSUPP, .XDEV => unreachable, // handled above
2390	.BADF => unreachable,
2391	.FBIG => unreachable,
2392	.INVAL => unreachable,
2393	.OVERFLOW => unreachable,
2394	.IO => error.InputOutput,
2395	.ISDIR => error.IsDir,
2396	.NOMEM => error.SystemResources,
2397	.NOSPC => error.NoSpaceLeft,
2398	.PERM => error.PermissionDenied,
2399	.TXTBSY => error.FileBusy,
2400	else => std.posix.unexpectedErrno(e),
2401	};
2402	return error.MappedFileIo;
2403	},
2404	}
2405	}
2406	return size - remaining_size;
2407	}
2408
2409	pub fn ensureTotalCapacity(mf: *MappedFile, new_capacity: usize) Error!void {
2410	if (mf.memory_map.memory.len >= new_capacity) return;
2411	try mf.ensureTotalCapacityPrecise(new_capacity +| new_capacity / growth_factor);
2412	}
2413
2414	pub fn ensureTotalCapacityPrecise(mf: *MappedFile, new_capacity: usize) Error!void {
2415	if (mf.memory_map.memory.len >= new_capacity) return;
2416	const io = mf.io;
2417	const aligned_capacity: usize = @intCast(
2418	mf.flags.block_size.forward(new_capacity),
2419	);
2420
2421	if (mf.memory_map.memory.len > 0) {
2422	if (mf.memory_map.setLength(io, aligned_capacity)) |_| {
2423	return;
2424	} else |err| switch (err) {
2425	error.OperationUnsupported => {},
2426	error.OutOfMemory, error.Canceled => |e| return e,
2427	else => |e| {
2428	mf.io_err = e;
2429	return error.MappedFileIo;
2430	},
2431	}
2432
2433	mf.memory_map.write(io) catch |err| {
2434	mf.io_err = switch (err) {
2435	error.Canceled => |e| return e,
2436	error.WouldBlock => error.Unexpected, // file was not opened as non-blocking
2437	error.NotOpenForWriting => error.Unexpected, // we definitely opened the file for writing
2438	else => |e| e,
2439	};
2440	return error.MappedFileIo;
2441	};
2442	unmap(mf);
2443	}
2444
2445	const file = mf.memory_map.file;
2446	mf.memory_map = Io.File.MemoryMap.create(io, file, .{ .len = aligned_capacity }) catch |err| {
2447	mf.io_err = switch (err) {
2448	error.OutOfMemory, error.Canceled => |e| return e,
2449	error.WouldBlock => error.Unexpected, // file was not opened as non-blocking
2450	error.NotOpenForReading => error.Unexpected, // we definitely opened the file for writing
2451	else => |e| e,
2452	};
2453	return error.MappedFileIo;
2454	};
2455	}
2456
2457	pub fn unmap(mf: *MappedFile) void {
2458	if (mf.memory_map.memory.len == 0) return;
2459	const io = mf.io;
2460	const file = mf.memory_map.file;
2461	mf.memory_map.destroy(io);
2462	mf.memory_map.memory = &.{};
2463	mf.memory_map.file = file;
2464	}
2465
2466	pub fn flush(mf: *MappedFile) (Io.Cancelable || error{MappedFileIo})!void {
2467	mf.flushInner() catch |err| switch (err) {
2468	error.Canceled => |e| return e,
2469
2470	error.WouldBlock, // file was not opened as non-blocking
2471	error.NotOpenForWriting, // we definitely opened the file for writing
2472	error.ReadOnlyFileSystem, // again, we opened the file for writing
2473	=> {
2474	mf.io_err = error.Unexpected;
2475	return error.MappedFileIo;
2476	},
2477
2478	else => |e| {
2479	mf.io_err = e;
2480	return error.MappedFileIo;
2481	},
2482	};
2483	}
2484
2485	fn flushInner(mf: *MappedFile) (Io.File.WritePositionalError || Io.File.SetTimestampsError)!void {
2486	try mf.memory_map.write(mf.io);
2487	if (is_windows) try mf.memory_map.file.setTimestampsNow(mf.io);
2488	}
2489
2490	fn verify(mf: *MappedFile) void {
2491	const root = Node.Index.root.get(mf);
2492	assert(root.parent == .none);
2493	assert(root.prev == .none);
2494	assert(root.next == .none);
2495	mf.verifyNode(.root);
2496	}
2497	fn verifyNode(mf: *MappedFile, parent_ni: Node.Index) void {
2498	const parent = parent_ni.get(mf);
2499	_, const parent_size = parent.location().resolve(mf);
2500
2501	var prev_oni: Node.Index.Optional = .none;
2502	var prev_end: u64 = 0;
2503	var prev_pos: Node.Position = .header;
2504	var oni = parent.first;
2505	while (oni.unwrap()) |ni| {
2506	const node = ni.get(mf);
2507	assert(node.parent == parent_ni.toOptional());
2508	assert(node.prev == prev_oni);
2509
2510	const offset, const size = node.location().resolve(mf);
2511	const end = offset + size;
2512
2513	assert(node.flags.alignment.check(size));
2514	assert(offset >= prev_end);
2515	assert(end <= parent_size);
2516
2517	switch (node.flags.position) {
2518	.header => {
2519	assert(prev_pos == .header);
2520	assert(offset == prev_end);
2521	},
2522	.floating => {
2523	assert(prev_pos != .footer);
2524	assert(node.flags.alignment.check(offset));
2525	},
2526	.footer => {
2527	if (prev_pos == .footer) assert(offset == prev_end);
2528	},
2529	}
2530
2531	mf.verifyNode(ni);
2532
2533	prev_oni = .wrap(ni);
2534	prev_end = end;
2535	prev_pos = ni.position(mf);
2536
2537	oni = node.next;
2538	}
2539	assert(parent.last == prev_oni);
2540	if (prev_pos == .footer) {
2541	assert(prev_end == parent_size);
2542	}
2543	}
2544
2545	test "fuzz node operations" {
2546	try std.testing.fuzz({}, fuzzOneNodeOperations, .{});
2547	}
2548	fn fuzzOneNodeOperations(_: void, smith: *std.testing.Smith) anyerror!void {
2549	const gpa = std.testing.allocator;
2550	const io = std.testing.io;
2551
2552	var tmp_dir = std.testing.tmpDir(.{});
2553	defer tmp_dir.cleanup();
2554
2555	var tmp_file = try tmp_dir.dir.createFile(io, "test.mf", .{ .read = true });
2556	defer tmp_file.close(io);
2557
2558	var mf: MappedFile = try .init(tmp_file, gpa, io);
2559	defer mf.deinit(gpa);
2560
2561	var nodes: std.array_hash_map.Auto(MappedFile.Node.Index, struct {
2562	parent: MappedFile.Node.Index.Optional,
2563	position: MappedFile.Node.Position,
2564	num_headers: u32,
2565	num_footers: u32,
2566	/// For leaf nodes, this value is whether we have initialized the contents of the node or
2567	/// not. For non-leaf nodes, this value is unspecified and should be ignored.
2568	initialized: bool,
2569	}) = .empty;
2570	defer nodes.deinit(gpa);
2571
2572	// When initializing a leaf node, we will place its 4-byte node index at the start of its range,
2573	// and the bitwise NOT of its node index at the end of its range (both little-endian). This is
2574	// just a simple way to put distinct values we can validate at all node boundaries.
2575
2576	try nodes.putNoClobber(gpa, .root, .{
2577	.parent = .none,
2578	.position = .floating,
2579	.num_headers = 0,
2580	.num_footers = 0,
2581	.initialized = false,
2582	});
2583
2584	// Allow a range of alignments, with most nodes having a small alignment of 1--32 bytes (most
2585	// commonly 1 byte), but with a small chance for some large alignments too.
2586	const alignment_weights: []const std.testing.Smith.Weight = comptime &.{
2587	.value(Alignment, .@"1", 20),
2588	.value(Alignment, .@"2", 5),
2589	.value(Alignment, .@"4", 5),
2590	.value(Alignment, .@"8", 5),
2591	.value(Alignment, .@"16", 5),
2592	.value(Alignment, .@"32", 5),
2593	.value(Alignment, .fromByteUnits(0x200), 1),
2594	.value(Alignment, .fromByteUnits(0x400), 1),
2595	.value(Alignment, .fromByteUnits(0x800), 1),
2596	.value(Alignment, .fromByteUnits(0x1000), 1),
2597	.value(Alignment, .fromByteUnits(0x2000), 1),
2598	.value(Alignment, .fromByteUnits(0x4000), 1),
2599	.value(Alignment, .fromByteUnits(0x8000), 1),
2600	};
2601
2602	const min_nonzero_size = 2 * @sizeOf(MappedFile.Node.Index);
2603	const max_size = 0x10_000;
2604	const initial_size_weights: []const std.testing.Smith.Weight = comptime &.{
2605	// initially, make nodes just as likely to be empty as non-empty
2606	.value(u64, 0, max_size - min_nonzero_size + 1),
2607	.rangeAtMost(u64, min_nonzero_size, max_size, 1),
2608	};
2609
2610	while (!smith.eos()) switch (smith.value(enum { add, resize, realign })) {
2611	.add => {
2612	const parent_ni = nodes.keys()[smith.index(nodes.count())];
2613
2614	const alignment = smith.valueWeighted(Alignment, alignment_weights);
2615	const size = alignment.forward(smith.valueWeighted(u64, initial_size_weights));
2616
2617	const position = smith.valueWeighted(Node.Position, comptime &.{
2618	// make floating nodes more common than header and footer nodes
2619	.value(Node.Position, .header, 1),
2620	.value(Node.Position, .footer, 1),
2621	.value(Node.Position, .floating, 4),
2622	});
2623	const new_ni: Node.Index = switch (position) {
2624	.header => new_ni: {
2625	const parent_info = nodes.getPtr(parent_ni).?;
2626	const prev_oni: Node.Index.Optional = prev_oni: {
2627	const n = smith.valueRangeAtMost(u32, 0, parent_info.num_headers);
2628	if (n == 0) break :prev_oni .none;
2629	var cur_ni = parent_ni.first(&mf).unwrap().?;
2630	for (1..n) |_| cur_ni = cur_ni.next(&mf).unwrap().?;
2631	break :prev_oni .wrap(cur_ni);
2632	};
2633	const new_ni = try parent_ni.addHeaderChildAfter(&mf, gpa, prev_oni, .{
2634	.size = size,
2635	.alignment = alignment,
2636	});
2637	parent_info.num_headers += 1;
2638	break :new_ni new_ni;
2639	},
2640
2641	.floating => try parent_ni.addFloatingChild(&mf, gpa, .{
2642	.size = size,
2643	.alignment = alignment,
2644	}),
2645
2646	.footer => new_ni: {
2647	const parent_info = nodes.getPtr(parent_ni).?;
2648	const next_oni: Node.Index.Optional = next_oni: {
2649	const n = smith.valueRangeAtMost(u32, 0, parent_info.num_footers);
2650	if (n == 0) break :next_oni .none;
2651	var cur_ni = parent_ni.last(&mf).unwrap().?;
2652	for (1..n) |_| cur_ni = cur_ni.prev(&mf).unwrap().?;
2653	break :next_oni .wrap(cur_ni);
2654	};
2655	const new_ni = try parent_ni.addFooterChildBefore(&mf, gpa, next_oni, .{
2656	.size = size,
2657	.alignment = alignment,
2658	});
2659	parent_info.num_footers += 1;
2660	break :new_ni new_ni;
2661	},
2662	};
2663
2664	const initialize = size > 0 and smith.value(bool);
2665	if (initialize) {
2666	const slice = new_ni.slice(&mf);
2667	std.mem.writeInt(u32, slice[0..4], @backingInt(new_ni), .little);
2668	std.mem.writeInt(u32, slice[slice.len - 4 ..][0..4], ~@backingInt(new_ni), .little);
2669	}
2670
2671	try nodes.putNoClobber(gpa, new_ni, .{
2672	.parent = .wrap(parent_ni),
2673	.position = position,
2674	.num_headers = 0,
2675	.num_footers = 0,
2676	.initialized = initialize,
2677	});
2678	},
2679
2680	.resize => {
2681	const ni = nodes.keys()[smith.index(nodes.count())];
2682	const node_info = nodes.getPtr(ni).?;
2683
2684	const alignment = ni.alignment(&mf);
2685
2686	if (ni.first(&mf) == .none and smith.value(bool)) {
2687	// Since this is a leaf node, we can use `resizeLeaf`.
2688	const new_size = alignment.forward(smith.valueWeighted(u64, initial_size_weights));
2689	try ni.resizeLeaf(&mf, gpa, new_size);
2690	if (new_size == 0) {
2691	node_info.initialized = false;
2692	}
2693	} else {
2694	const min_size = alignment.forward(smith.valueWeighted(u64, initial_size_weights));
2695	try ni.ensureMinimumSize(&mf, gpa, min_size);
2696	}
2697
2698	if (ni.first(&mf) == .none) {
2699	// This is a leaf node, so it can contain data.
2700	if (node_info.initialized) {
2701	// It's already initialized, so we'll write the expected footer at the new end.
2702	const slice = ni.slice(&mf);
2703	std.mem.writeInt(u32, slice[slice.len - 4 ..][0..4], ~@backingInt(ni), .little);
2704	} else if (ni.location(&mf).resolve(&mf)[1] > 0) {
2705	// It was uninitialized, but it has a non-zero size, so maybe we'd like to
2706	// initialize it now?
2707	if (smith.value(bool)) {
2708	node_info.initialized = true;
2709	const slice = ni.slice(&mf);
2710	std.mem.writeInt(u32, slice[0..4], @backingInt(ni), .little);
2711	std.mem.writeInt(u32, slice[slice.len - 4 ..][0..4], ~@backingInt(ni), .little);
2712	}
2713	}
2714	}
2715	},
2716	.realign => {
2717	const ni = nodes.keys()[smith.index(nodes.count())];
2718	const new_alignment = smith.valueWeighted(Alignment, alignment_weights);
2719	if (new_alignment.compare(.gt, ni.alignment(&mf))) {
2720	_, const old_size = ni.location(&mf).resolve(&mf);
2721	try ni.realign(&mf, gpa, new_alignment);
2722	if (ni.first(&mf) == .none and nodes.get(ni).?.initialized) {
2723	const slice = ni.slice(&mf);
2724	@memmove(slice[slice.len - 4 ..][0..4], slice[old_size - 4 ..][0..4]);
2725	}
2726	}
2727	},
2728	};
2729
2730	mf.verify();
2731
2732	for (nodes.keys(), nodes.values()) |ni, expected| {
2733	try std.testing.expectEqual(expected.parent, ni.parent(&mf));
2734	if (ni != .root) {
2735	try std.testing.expectEqual(expected.position, ni.position(&mf));
2736	}
2737
2738	{
2739	var num_headers: u32 = 0;
2740	var header_oni = ni.lastHeader(&mf);
2741	while (header_oni.unwrap()) |header_ni| {
2742	num_headers += 1;
2743	header_oni = header_ni.prev(&mf);
2744	}
2745	try std.testing.expectEqual(expected.num_headers, num_headers);
2746	}
2747
2748	{
2749	var num_footers: u32 = 0;
2750	var footer_oni = ni.firstFooter(&mf);
2751	while (footer_oni.unwrap()) |footer_ni| {
2752	num_footers += 1;
2753	footer_oni = footer_ni.next(&mf);
2754	}
2755	try std.testing.expectEqual(expected.num_footers, num_footers);
2756	}
2757
2758	if (ni.first(&mf) == .none and expected.initialized) {
2759	const slice = ni.sliceConst(&mf);
2760	if (slice.len > 0) {
2761	try std.testing.expect(slice.len >= min_nonzero_size);
2762	const header = std.mem.readInt(u32, slice[0..4], .little);
2763	const footer = std.mem.readInt(u32, slice[slice.len - 4 ..][0..4], .little);
2764	try std.testing.expectEqual(@backingInt(ni), header);
2765	try std.testing.expectEqual(~@backingInt(ni), footer);
2766	}
2767	}
2768	}
2769	}