lib/wayland/src/runtime/object.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const wayland = @import("../root.zig");
3
4 pub const default_client_object_count: usize = wayland.ids.default_client_id_count;
5 pub const default_server_object_count: usize = 256;
6 pub const maximum_client_object_count: usize = wayland.ids.maximum_client_id_count;
7 pub const maximum_server_object_count: usize =
8 @as(usize, std.math.maxInt(u32) - wayland.ids.first_server_id) + 1;
9
10 pub const Origin = enum {
11 display,
12 client,
13 server,
14 };
15
16 pub const State = enum {
17 live,
18 retired_request,
19 retired_event,
20 };
21
22 pub const Entry = struct {
23 interface: *const wayland.protocol.schema.Interface,
24 version: u32,
25 origin: Origin,
26 state: State = .live,
27 };
28
29 pub const ClientSlot = ?Entry;
30
31 pub const ServerSlot = struct {
32 id: u32,
33 entry: Entry,
34 };
35
36 pub const Limits = struct {
37 client_object_count: usize = default_client_object_count,
38 server_object_count: usize = default_server_object_count,
39 };
40
41 pub const CapacityError = error{
42 ClientObjectStorageTooLarge,
43 ServerObjectStorageTooLarge,
44 CapacityOverflow,
45 };
46
47 pub const Capacity = struct {
48 client_object_count: usize,
49 server_object_count: usize,
50 client_slot_bytes: usize,
51 server_slot_bytes: usize,
52 total_requested_bytes: usize,
53
54 pub fn derive(limits: Limits) CapacityError!Capacity {
55 if (limits.client_object_count > maximum_client_object_count) {
56 return error.ClientObjectStorageTooLarge;
57 }
58 if (limits.server_object_count > maximum_server_object_count) {
59 return error.ServerObjectStorageTooLarge;
60 }
61 const client_slot_bytes = std.math.mul(
62 usize,
63 limits.client_object_count,
64 @sizeOf(ClientSlot),
65 ) catch return error.CapacityOverflow;
66 const server_slot_bytes = std.math.mul(
67 usize,
68 limits.server_object_count,
69 @sizeOf(ServerSlot),
70 ) catch return error.CapacityOverflow;
71 const total_requested_bytes = std.math.add(
72 usize,
73 client_slot_bytes,
74 server_slot_bytes,
75 ) catch return error.CapacityOverflow;
76 return .{
77 .client_object_count = limits.client_object_count,
78 .server_object_count = limits.server_object_count,
79 .client_slot_bytes = client_slot_bytes,
80 .server_slot_bytes = server_slot_bytes,
81 .total_requested_bytes = total_requested_bytes,
82 };
83 }
84 };
85
86 pub const StorageError = error{
87 ClientObjectCapacityExceeded,
88 ServerObjectCapacityExceeded,
89 };
90
91 pub const ModelError = error{
92 DuplicateObject,
93 InvalidObjectId,
94 InvalidVersion,
95 ObjectAlreadyRetired,
96 ObjectStillLive,
97 UnknownObject,
98 };
99
100 pub const Error = StorageError || ModelError;
101
102 pub const Status = struct {
103 client_object_capacity_rejection_count: u64 = 0,
104 server_object_capacity_rejection_count: u64 = 0,
105 };
106
107 pub const default_capacity = Capacity.derive(.{}) catch unreachable;
108
109 pub const Table = struct {
110 session_allocator: std.mem.Allocator,
111 display: ?Entry = null,
112 clients: []ClientSlot,
113 servers: []ServerSlot,
114 server_count: usize = 0,
115 server_live_count: usize = 0,
116 client_capacity_rejection_count: u64 = 0,
117 server_capacity_rejection_count: u64 = 0,
118
119 pub fn init(
120 session_allocator: std.mem.Allocator,
121 capacity: Capacity,
122 ) std.mem.Allocator.Error!Table {
123 const clients = try session_allocator.alloc(ClientSlot, capacity.client_object_count);
124 errdefer if (clients.len != 0) session_allocator.free(clients);
125 @memset(clients, null);
126 return .{
127 .session_allocator = session_allocator,
128 .clients = clients,
129 .servers = try session_allocator.alloc(ServerSlot, capacity.server_object_count),
130 };
131 }
132
133 pub fn deinit(self: *Table) void {
134 self.assertValid();
135 if (self.servers.len != 0) self.session_allocator.free(self.servers);
136 if (self.clients.len != 0) self.session_allocator.free(self.clients);
137 self.* = undefined;
138 }
139
140 pub fn addDisplay(
141 self: *Table,
142 interface: *const wayland.protocol.schema.Interface,
143 ) ModelError!void {
144 self.assertValid();
145 if (self.display != null) return error.DuplicateObject;
146 try validateVersion(interface, 1);
147 self.display = .{
148 .interface = interface,
149 .version = 1,
150 .origin = .display,
151 };
152 }
153
154 pub fn addClient(
155 self: *Table,
156 id: u32,
157 interface: *const wayland.protocol.schema.Interface,
158 version: u32,
159 ) Error!void {
160 self.assertValid();
161 const at = clientIndex(id) orelse return error.InvalidObjectId;
162 try validateVersion(interface, version);
163 if (at >= self.clients.len) {
164 self.client_capacity_rejection_count +|= 1;
165 return error.ClientObjectCapacityExceeded;
166 }
167 if (self.clients[at] != null) return error.DuplicateObject;
168 self.clients[at] = .{
169 .interface = interface,
170 .version = version,
171 .origin = .client,
172 };
173 }
174
175 pub fn addServer(
176 self: *Table,
177 id: u32,
178 interface: *const wayland.protocol.schema.Interface,
179 version: u32,
180 ) Error!void {
181 try self.validateServerInsertion(id);
182 try validateVersion(interface, version);
183 try self.ensureServerCapacity(1);
184 self.addServerAssumeCapacity(id, interface, version);
185 }
186
187 pub fn ensureServerCapacity(self: *Table, additional_live_count: usize) StorageError!void {
188 self.assertValid();
189 if (additional_live_count > self.servers.len - self.server_live_count) {
190 self.server_capacity_rejection_count +|= 1;
191 return error.ServerObjectCapacityExceeded;
192 }
193 }
194
195 pub fn validateServerInsertion(self: *const Table, id: u32) ModelError!void {
196 self.assertValid();
197 if (id < wayland.ids.first_server_id) return error.InvalidObjectId;
198 if (self.get(id)) |entry| {
199 if (entry.origin != .server or entry.state == .live) return error.DuplicateObject;
200 }
201 }
202
203 pub fn addServerAssumeCapacity(
204 self: *Table,
205 id: u32,
206 interface: *const wayland.protocol.schema.Interface,
207 version: u32,
208 ) void {
209 self.assertValid();
210 std.debug.assert(id >= wayland.ids.first_server_id);
211 std.debug.assert(version != 0);
212 std.debug.assert(version <= interface.version);
213 if (self.serverIndex(id)) |at| {
214 std.debug.assert(self.servers[at].entry.state != .live);
215 self.servers[at].entry = .{
216 .interface = interface,
217 .version = version,
218 .origin = .server,
219 };
220 self.server_live_count += 1;
221 self.assertValid();
222 return;
223 }
224 std.debug.assert(self.server_live_count < self.servers.len);
225 if (self.server_count == self.servers.len) {
226 self.removeServerAt(self.firstRetiredIndex().?);
227 }
228 const at = self.lowerBoundServer(id);
229 std.mem.copyBackwards(
230 ServerSlot,
231 self.servers[at + 1 .. self.server_count + 1],
232 self.servers[at..self.server_count],
233 );
234 self.servers[at] = .{
235 .id = id,
236 .entry = .{
237 .interface = interface,
238 .version = version,
239 .origin = .server,
240 },
241 };
242 self.server_count += 1;
243 self.server_live_count += 1;
244 self.assertValid();
245 }
246
247 pub fn get(self: *const Table, id: u32) ?Entry {
248 self.assertValid();
249 if (id == wayland.ids.display_id) return self.display;
250 if (clientIndex(id)) |at| {
251 if (at >= self.clients.len) return null;
252 return self.clients[at];
253 }
254 const at = self.serverIndex(id) orelse return null;
255 return self.servers[at].entry;
256 }
257
258 pub fn getLive(self: *const Table, id: u32) ?Entry {
259 const entry = self.get(id) orelse return null;
260 return if (entry.state == .live) entry else null;
261 }
262
263 pub fn require(self: *const Table, id: u32) ModelError!Entry {
264 return self.get(id) orelse error.UnknownObject;
265 }
266
267 pub fn requireLive(self: *const Table, id: u32) ModelError!Entry {
268 const entry = try self.require(id);
269 if (entry.state != .live) return error.UnknownObject;
270 return entry;
271 }
272
273 pub fn retire(self: *Table, id: u32, state: State) ModelError!void {
274 self.assertValid();
275 std.debug.assert(state != .live);
276 const entry = self.getPtr(id) orelse return error.UnknownObject;
277 if (entry.state != .live) return error.ObjectAlreadyRetired;
278 if (entry.origin == .server) {
279 std.debug.assert(self.server_live_count != 0);
280 self.server_live_count -= 1;
281 }
282 entry.state = state;
283 self.assertValid();
284 }
285
286 pub fn removeLive(self: *Table, id: u32) ModelError!Entry {
287 const entry = try self.requireLive(id);
288 switch (entry.origin) {
289 .display => self.display = null,
290 .client => self.clients[clientIndex(id).?] = null,
291 .server => self.removeServerAt(self.serverIndex(id).?),
292 }
293 self.assertValid();
294 return entry;
295 }
296
297 pub fn removeRetiredClient(self: *Table, id: u32) ModelError!Entry {
298 const entry = try self.require(id);
299 if (entry.origin != .client or entry.state == .live) return error.ObjectStillLive;
300 self.clients[clientIndex(id).?] = null;
301 self.assertValid();
302 return entry;
303 }
304
305 pub fn status(self: *const Table) Status {
306 self.assertValid();
307 return .{
308 .client_object_capacity_rejection_count = self.client_capacity_rejection_count,
309 .server_object_capacity_rejection_count = self.server_capacity_rejection_count,
310 };
311 }
312
313 fn getPtr(self: *Table, id: u32) ?*Entry {
314 if (id == wayland.ids.display_id) {
315 return if (self.display) |*entry| entry else null;
316 }
317 if (clientIndex(id)) |at| {
318 if (at >= self.clients.len) return null;
319 return if (self.clients[at]) |*entry| entry else null;
320 }
321 const at = self.serverIndex(id) orelse return null;
322 return &self.servers[at].entry;
323 }
324
325 fn serverIndex(self: *const Table, id: u32) ?usize {
326 if (id < wayland.ids.first_server_id) return null;
327 const at = self.lowerBoundServer(id);
328 if (at == self.server_count or self.servers[at].id != id) return null;
329 return at;
330 }
331
332 fn lowerBoundServer(self: *const Table, id: u32) usize {
333 var low: usize = 0;
334 var high = self.server_count;
335 while (low < high) {
336 const middle = low + (high - low) / 2;
337 if (self.servers[middle].id < id) {
338 low = middle + 1;
339 } else {
340 high = middle;
341 }
342 }
343 return low;
344 }
345
346 fn firstRetiredIndex(self: *const Table) ?usize {
347 for (self.servers[0..self.server_count], 0..) |slot, at| {
348 if (slot.entry.state != .live) return at;
349 }
350 return null;
351 }
352
353 fn removeServerAt(self: *Table, at: usize) void {
354 std.debug.assert(at < self.server_count);
355 if (self.servers[at].entry.state == .live) {
356 std.debug.assert(self.server_live_count != 0);
357 self.server_live_count -= 1;
358 }
359 std.mem.copyForwards(
360 ServerSlot,
361 self.servers[at .. self.server_count - 1],
362 self.servers[at + 1 .. self.server_count],
363 );
364 self.server_count -= 1;
365 }
366
367 fn assertValid(self: *const Table) void {
368 std.debug.assert(self.clients.len <= maximum_client_object_count);
369 std.debug.assert(self.servers.len <= maximum_server_object_count);
370 std.debug.assert(self.server_live_count <= self.server_count);
371 std.debug.assert(self.server_count <= self.servers.len);
372 if (self.display) |entry| std.debug.assert(entry.origin == .display);
373 for (self.clients) |slot| {
374 if (slot) |entry| std.debug.assert(entry.origin == .client);
375 }
376 var live_count: usize = 0;
377 for (self.servers[0..self.server_count], 0..) |slot, at| {
378 std.debug.assert(slot.id >= wayland.ids.first_server_id);
379 std.debug.assert(slot.entry.origin == .server);
380 if (at != 0) std.debug.assert(self.servers[at - 1].id < slot.id);
381 live_count += @intFromBool(slot.entry.state == .live);
382 }
383 std.debug.assert(live_count == self.server_live_count);
384 }
385 };
386
387 fn clientIndex(id: u32) ?usize {
388 if (id < wayland.ids.first_dynamic_id or id >= wayland.ids.first_server_id) return null;
389 return @intCast(id - wayland.ids.first_dynamic_id);
390 }
391
392 fn validateVersion(
393 interface: *const wayland.protocol.schema.Interface,
394 version: u32,
395 ) ModelError!void {
396 if (version == 0 or version > interface.version) return error.InvalidVersion;
397 }
398
399 test "object capacity derives exact client and server storage" {
400 try std.testing.expectEqual(@as(usize, 256), default_capacity.client_object_count);
401 try std.testing.expectEqual(@as(usize, 256), default_capacity.server_object_count);
402 const capacity = try Capacity.derive(.{
403 .client_object_count = 3,
404 .server_object_count = 5,
405 });
406 try std.testing.expectEqual(@as(usize, 3), capacity.client_object_count);
407 try std.testing.expectEqual(@as(usize, 5), capacity.server_object_count);
408 try std.testing.expectEqual(3 * @sizeOf(ClientSlot), capacity.client_slot_bytes);
409 try std.testing.expectEqual(5 * @sizeOf(ServerSlot), capacity.server_slot_bytes);
410 try std.testing.expectEqual(
411 capacity.client_slot_bytes + capacity.server_slot_bytes,
412 capacity.total_requested_bytes,
413 );
414 try std.testing.expectError(
415 error.ClientObjectStorageTooLarge,
416 Capacity.derive(.{ .client_object_count = maximum_client_object_count + 1 }),
417 );
418 try std.testing.expectError(
419 error.ServerObjectStorageTooLarge,
420 Capacity.derive(.{ .server_object_count = maximum_server_object_count + 1 }),
421 );
422 }
423
424 test "object table acquires both regions before use" {
425 const capacity = try Capacity.derive(.{
426 .client_object_count = 3,
427 .server_object_count = 5,
428 });
429 for (0..2) |fail_index| {
430 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{
431 .fail_index = fail_index,
432 });
433 try std.testing.expectError(error.OutOfMemory, Table.init(failing.allocator(), capacity));
434 }
435 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{
436 .fail_index = 2,
437 });
438 var table = try Table.init(failing.allocator(), capacity);
439 defer table.deinit();
440 try std.testing.expectEqual(@as(usize, 2), failing.allocations);
441 }
442
443 test "object table retains client tombstones through deletion acknowledgement" {
444 const display = &wayland.protocol.core.interfaces[0];
445 const registry = &wayland.protocol.core.interfaces[1];
446 var table = try Table.init(std.testing.allocator, default_capacity);
447 defer table.deinit();
448 try table.addDisplay(display);
449 try table.addClient(2, registry, 1);
450
451 try table.retire(2, .retired_request);
452 try std.testing.expect(table.getLive(2) == null);
453 try std.testing.expectEqual(State.retired_request, (try table.require(2)).state);
454 try std.testing.expectEqual(Origin.client, (try table.removeRetiredClient(2)).origin);
455 try std.testing.expectError(error.UnknownObject, table.require(2));
456 }
457
458 test "server IDs replace only retired server tombstones" {
459 const callback = &wayland.protocol.core.interfaces[2];
460 const id = wayland.ids.first_server_id;
461 var table = try Table.init(std.testing.allocator, default_capacity);
462 defer table.deinit();
463 try table.addServer(id, callback, 1);
464 try std.testing.expectError(error.DuplicateObject, table.addServer(id, callback, 1));
465 try table.retire(id, .retired_event);
466 try table.addServer(id, callback, 1);
467 try std.testing.expectEqual(State.live, (try table.require(id)).state);
468 try std.testing.expectError(error.InvalidObjectId, table.addServer(9, callback, 1));
469 }
470
471 test "server object storage reclaims retired slots and preserves sorted lookup" {
472 const callback = &wayland.protocol.core.interfaces[2];
473 const capacity = try Capacity.derive(.{
474 .client_object_count = 0,
475 .server_object_count = 2,
476 });
477 var table = try Table.init(std.testing.allocator, capacity);
478 defer table.deinit();
479 const base = wayland.ids.first_server_id;
480
481 try table.addServer(base + 10, callback, 1);
482 try table.addServer(base + 2, callback, 1);
483 try std.testing.expectEqual(base + 2, table.servers[0].id);
484 try std.testing.expectEqual(base + 10, table.servers[1].id);
485 try table.retire(base + 2, .retired_event);
486 try table.addServer(base + 5, callback, 1);
487 try std.testing.expect(table.get(base + 2) == null);
488 try std.testing.expectEqual(base + 5, table.servers[0].id);
489 try std.testing.expectEqual(base + 10, table.servers[1].id);
490 try table.retire(base + 10, .retired_request);
491 try table.addServer(base + 10, callback, 1);
492 try std.testing.expectEqual(State.live, (try table.require(base + 10)).state);
493 }
494
495 test "object max plus one preserves storage and saturates status" {
496 const registry = &wayland.protocol.core.interfaces[1];
497 const callback = &wayland.protocol.core.interfaces[2];
498 const capacity = try Capacity.derive(.{
499 .client_object_count = 1,
500 .server_object_count = 1,
501 });
502 var table = try Table.init(std.testing.allocator, capacity);
503 defer table.deinit();
504 const clients = table.clients.ptr;
505 const servers = table.servers.ptr;
506
507 try table.addClient(2, registry, 1);
508 try std.testing.expectError(
509 error.ClientObjectCapacityExceeded,
510 table.addClient(3, registry, 1),
511 );
512 try table.addServer(wayland.ids.first_server_id, callback, 1);
513 try std.testing.expectError(
514 error.ServerObjectCapacityExceeded,
515 table.addServer(wayland.ids.first_server_id + 1, callback, 1),
516 );
517 try std.testing.expectEqual(clients, table.clients.ptr);
518 try std.testing.expectEqual(servers, table.servers.ptr);
519 try std.testing.expectEqual(
520 @as(u64, 1),
521 table.status().client_object_capacity_rejection_count,
522 );
523 try std.testing.expectEqual(
524 @as(u64, 1),
525 table.status().server_object_capacity_rejection_count,
526 );
527
528 table.client_capacity_rejection_count = std.math.maxInt(u64);
529 table.server_capacity_rejection_count = std.math.maxInt(u64);
530 try std.testing.expectError(
531 error.ClientObjectCapacityExceeded,
532 table.addClient(3, registry, 1),
533 );
534 try std.testing.expectError(
535 error.ServerObjectCapacityExceeded,
536 table.ensureServerCapacity(1),
537 );
538 try std.testing.expectEqual(
539 std.math.maxInt(u64),
540 table.status().client_object_capacity_rejection_count,
541 );
542 try std.testing.expectEqual(
543 std.math.maxInt(u64),
544 table.status().server_object_capacity_rejection_count,
545 );
546 }
547
548 test "object table rejects client ranges and impossible versions" {
549 const registry = &wayland.protocol.core.interfaces[1];
550 var table = try Table.init(std.testing.allocator, default_capacity);
551 defer table.deinit();
552 try std.testing.expectError(
553 error.InvalidObjectId,
554 table.addClient(wayland.ids.first_server_id, registry, 1),
555 );
556 try std.testing.expectError(error.InvalidVersion, table.addClient(2, registry, 2));
557 }