lib/sql/src/space.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const file = @import("file.zig");
3 const index_mod = @import("index.zig");
4 const page = @import("page.zig");
5 const row = @import("row.zig");
6 const table = @import("table.zig");
7 const tree_mod = @import("tree.zig");
8 const wal = @import("wal.zig");
9
10 const SpaceError = error{
11 TooManyRoots,
12 };
13
14 pub const Error = table.Error || index_mod.Error || tree_mod.Error || page.Error || SpaceError;
15
16 pub const max_roots: usize = 32;
17
18 pub const RootSpec = struct {
19 root_page: u32,
20 identity_page: u32 = 0,
21 };
22
23 pub const Options = struct {
24 meta_page: u32 = 1,
25 roots: []const RootSpec = &.{.{ .root_page = 2 }},
26 reserved_page_max: u32 = 0,
27 };
28
29 const Layout = struct {
30 meta_page: u32,
31 roots: [max_roots]RootSpec,
32 root_count: usize,
33 reserved_page_max: u32,
34
35 fn init(options: Options) Error!Layout {
36 if (options.meta_page == 0) return error.InvalidPageId;
37 if (options.roots.len == 0) return error.InvalidPageId;
38 if (options.roots.len > max_roots) return error.TooManyRoots;
39
40 var layout = Layout{
41 .meta_page = options.meta_page,
42 .roots = undefined,
43 .root_count = options.roots.len,
44 .reserved_page_max = @max(options.meta_page, options.reserved_page_max),
45 };
46 for (options.roots, 0..) |spec, offset| {
47 try layout.addRoot(spec, offset);
48 }
49 return layout;
50 }
51
52 fn addRoot(self: *Layout, spec: RootSpec, offset: usize) Error!void {
53 if (spec.root_page == 0 or spec.root_page == self.meta_page) {
54 return error.InvalidPageId;
55 }
56 if (spec.identity_page != 0) {
57 if (spec.identity_page == self.meta_page) return error.InvalidPageId;
58 if (spec.identity_page == spec.root_page) return error.InvalidPageId;
59 }
60 for (self.roots[0..offset]) |previous| {
61 if (previous.root_page == spec.root_page) return error.InvalidPageId;
62 if (spec.identity_page != 0 and previous.identity_page == spec.identity_page) {
63 return error.InvalidPageId;
64 }
65 if (previous.root_page == spec.identity_page) return error.InvalidPageId;
66 if (previous.identity_page == spec.root_page) return error.InvalidPageId;
67 }
68 self.roots[offset] = spec;
69 self.reserved_page_max = @max(
70 self.reserved_page_max,
71 @max(spec.root_page, spec.identity_page),
72 );
73 }
74 };
75
76 fn optionsForRoot(
77 meta_page: u32,
78 roots: []const RootSpec,
79 reserved_page_max: u32,
80 root_page: u32,
81 ) Error!tree_mod.Options {
82 for (roots) |spec| {
83 if (spec.root_page == root_page) return .{
84 .meta_page = meta_page,
85 .root_page = spec.root_page,
86 .identity_page = spec.identity_page,
87 .reserved_page_max = reserved_page_max,
88 };
89 }
90 return error.InvalidPageId;
91 }
92
93 pub const Reader = struct {
94 snapshot: file.Snapshot,
95 meta_page: u32,
96 roots: [max_roots]RootSpec,
97 root_count: usize,
98 reserved_page_max: u32,
99
100 pub fn open(snapshot: file.Snapshot, options: Options) Error!Reader {
101 const layout = try Layout.init(options);
102 return .{
103 .snapshot = snapshot,
104 .meta_page = layout.meta_page,
105 .roots = layout.roots,
106 .root_count = layout.root_count,
107 .reserved_page_max = layout.reserved_page_max,
108 };
109 }
110
111 pub fn treeOptions(self: *const Reader, root_page: u32) Error!tree_mod.Options {
112 return try optionsForRoot(
113 self.meta_page,
114 self.roots[0..self.root_count],
115 self.reserved_page_max,
116 root_page,
117 );
118 }
119
120 pub fn tree(self: *const Reader, root_page: u32) Error!tree_mod.Reader {
121 return try tree_mod.Reader.open(self.snapshot, try self.treeOptions(root_page));
122 }
123
124 pub fn rowidTable(self: *const Reader, root_page: u32) Error!table.Reader {
125 return try table.Reader.open(self.snapshot, .{ .tree = try self.treeOptions(root_page) });
126 }
127
128 pub fn index(
129 self: *const Reader,
130 root_page: u32,
131 columns: []const row.Column,
132 ) Error!index_mod.Reader {
133 return try index_mod.Reader.open(self.snapshot, .{
134 .tree = try self.treeOptions(root_page),
135 .columns = columns,
136 });
137 }
138 };
139
140 pub const Space = struct {
141 database: *file.Database,
142 meta_page: u32,
143 roots: [max_roots]RootSpec,
144 root_count: usize,
145 reserved_page_max: u32,
146
147 pub fn open(database: *file.Database, options: Options) Error!Space {
148 const layout = try Layout.init(options);
149 return .{
150 .database = database,
151 .meta_page = layout.meta_page,
152 .roots = layout.roots,
153 .root_count = layout.root_count,
154 .reserved_page_max = layout.reserved_page_max,
155 };
156 }
157
158 pub fn reader(self: *const Space, snapshot: file.Snapshot) Error!Reader {
159 return .{
160 .snapshot = snapshot,
161 .meta_page = self.meta_page,
162 .roots = self.roots,
163 .root_count = self.root_count,
164 .reserved_page_max = self.reserved_page_max,
165 };
166 }
167
168 pub fn treeOptions(self: *const Space, root_page: u32) Error!tree_mod.Options {
169 return try optionsForRoot(
170 self.meta_page,
171 self.roots[0..self.root_count],
172 self.reserved_page_max,
173 root_page,
174 );
175 }
176
177 pub fn tree(self: *const Space, root_page: u32) Error!tree_mod.Tree {
178 return try tree_mod.Tree.open(self.database, try self.treeOptions(root_page));
179 }
180
181 pub fn rowidTable(self: *const Space, root_page: u32) Error!table.Table {
182 return try table.Table.open(self.database, .{ .tree = try self.treeOptions(root_page) });
183 }
184
185 pub fn index(self: *const Space, root_page: u32, columns: []const row.Column) Error!index_mod.Index {
186 return try index_mod.Index.open(self.database, .{
187 .tree = try self.treeOptions(root_page),
188 .columns = columns,
189 });
190 }
191
192 pub fn beginWrite(self: *const Space) Error!tree_mod.Write {
193 return try tree_mod.Write.begin(self.database, .{
194 .meta_page = self.meta_page,
195 .reserved_page_max = self.reserved_page_max,
196 });
197 }
198 };
199
200 test "space rejects invalid roots" {
201 var tmp = std.testing.tmpDir(.{});
202 defer tmp.cleanup();
203
204 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
205 .paths = .{ .database = "space.db", .wal = "space.wal" },
206 .header = testingHeader(),
207 });
208 defer database.deinit();
209
210 try std.testing.expectError(error.InvalidPageId, Space.open(&database, .{ .roots = &.{} }));
211 try std.testing.expectError(error.InvalidPageId, Space.open(&database, .{ .meta_page = 1, .roots = &.{ .{ .root_page = 2 }, .{ .root_page = 2 } } }));
212 const space = try Space.open(&database, .{ .meta_page = 1, .roots = &.{ .{ .root_page = 2 }, .{ .root_page = 3 } } });
213 try std.testing.expectError(error.InvalidPageId, space.treeOptions(4));
214 }
215
216 test "space keeps table growth away from reserved index root" {
217 var tmp = std.testing.tmpDir(.{});
218 defer tmp.cleanup();
219
220 {
221 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
222 .paths = .{ .database = "space.db", .wal = "space.wal" },
223 .header = testingHeader(),
224 });
225 defer database.deinit();
226 try database.reserve(.{ .wal_frames = 480 });
227
228 const space = try Space.open(&database, .{ .meta_page = 1, .roots = &.{ .{ .root_page = 2 }, .{ .root_page = 3 } } });
229 var rows = try space.rowidTable(2);
230 var rowid: i64 = 0;
231 while (rowid < 180) : (rowid += 1) {
232 _ = try rows.put(rowid, &.{ .{ .integer = rowid }, .{ .text = "payload" } }, .{ .durability = .buffered });
233 }
234 {
235 var read = try database.beginRead();
236 defer read.deinit();
237 var index_root_image: [page.size]u8 = undefined;
238 try std.testing.expect(!(try read.snapshot().copyPage(
239 3,
240 &index_root_image,
241 )));
242 }
243
244 var secondary = try space.index(3, &.{});
245 rowid = 0;
246 while (rowid < 180) : (rowid += 1) {
247 _ = try secondary.put(rowid, &.{.{ .integer = @mod(rowid, 9) }}, .{ .durability = .buffered });
248 }
249 try database.syncWal();
250 }
251
252 var reopened = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
253 .paths = .{ .database = "space.db", .wal = "space.wal" },
254 .header = recoveredHeader(),
255 });
256 defer reopened.deinit();
257
258 const space = try Space.open(&reopened, .{ .meta_page = 1, .roots = &.{ .{ .root_page = 2 }, .{ .root_page = 3 } } });
259 var rows = try space.rowidTable(2);
260 var secondary = try space.index(3, &.{});
261
262 var lookup: index_mod.Scan = undefined;
263 try secondary.lookup(&lookup, std.testing.allocator, &.{.{ .integer = 4 }});
264 defer lookup.deinit();
265 var seen: usize = 0;
266 while (try lookup.next()) |entry| {
267 const bytes = (try rows.get(std.testing.allocator, entry.rowid)).?;
268 defer std.testing.allocator.free(bytes);
269 const view = try row.View.init(bytes);
270 try std.testing.expectEqual(entry.rowid, (try view.column(0)).integer);
271 try std.testing.expectEqual(@as(i64, 4), @mod(entry.rowid, 9));
272 seen += 1;
273 }
274 try std.testing.expect(seen > 0);
275 }
276
277 fn testingHeader() wal.Header {
278 return .{
279 .sequence = 901,
280 .salt = .{ .first = 0x9191_7272, .second = 0x6363_5454 },
281 };
282 }
283
284 fn recoveredHeader() wal.Header {
285 return .{
286 .sequence = 902,
287 .salt = .{ .first = 0xaaaa_8888, .second = 0x9999_bbbb },
288 };
289 }