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