lib/wayland/src/runtime/global.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const wayland = @import("../root.zig");
3
4 pub const default_retained_global_count: usize = 256;
5 pub const default_interface_name_byte_count_per_global: usize = 128;
6
7 pub const Global = struct {
8 registry_id: u32,
9 name: u32,
10 interface: []const u8,
11 version: u32,
12 };
13
14 const Entry = struct {
15 registry_id: u32,
16 name: u32,
17 interface_len: usize,
18 version: u32,
19 };
20
21 pub const Slot = ?Entry;
22
23 pub const Limits = struct {
24 retained_global_count: usize = default_retained_global_count,
25 interface_name_byte_count_per_global: usize =
26 default_interface_name_byte_count_per_global,
27 };
28
29 pub const CapacityError = error{CapacityOverflow};
30
31 pub const Capacity = struct {
32 retained_global_count: usize,
33 interface_name_byte_count_per_global: usize,
34 retained_global_bytes: usize,
35 interface_name_bytes: usize,
36 total_requested_bytes: usize,
37
38 pub fn derive(limits: Limits) CapacityError!Capacity {
39 const retained_global_bytes = std.math.mul(
40 usize,
41 limits.retained_global_count,
42 @sizeOf(Slot),
43 ) catch return error.CapacityOverflow;
44 const interface_name_bytes = std.math.mul(
45 usize,
46 limits.retained_global_count,
47 limits.interface_name_byte_count_per_global,
48 ) catch return error.CapacityOverflow;
49 const total_requested_bytes = std.math.add(
50 usize,
51 retained_global_bytes,
52 interface_name_bytes,
53 ) catch return error.CapacityOverflow;
54 return .{
55 .retained_global_count = limits.retained_global_count,
56 .interface_name_byte_count_per_global = limits.interface_name_byte_count_per_global,
57 .retained_global_bytes = retained_global_bytes,
58 .interface_name_bytes = interface_name_bytes,
59 .total_requested_bytes = total_requested_bytes,
60 };
61 }
62 };
63
64 pub const StorageError = error{
65 GlobalCapacityExceeded,
66 GlobalInterfaceNameCapacityExceeded,
67 };
68
69 pub const ModelError = error{
70 DuplicateGlobal,
71 InvalidVersion,
72 UnknownGlobal,
73 };
74
75 pub const Error = StorageError || ModelError;
76
77 pub const Status = struct {
78 global_capacity_rejection_count: u64 = 0,
79 global_interface_name_capacity_rejection_count: u64 = 0,
80 };
81
82 pub const Admission = struct {
83 slot_index: usize,
84 registry_id: u32,
85 name: u32,
86 interface_len: usize,
87 version: u32,
88 };
89
90 pub const default_capacity = Capacity.derive(.{}) catch unreachable;
91
92 pub const Set = struct {
93 session_allocator: std.mem.Allocator,
94 slots: []Slot,
95 interface_names: []u8,
96 interface_name_byte_count_per_global: usize,
97 count: usize = 0,
98 capacity_rejection_count: u64 = 0,
99 interface_name_capacity_rejection_count: u64 = 0,
100
101 pub fn init(
102 session_allocator: std.mem.Allocator,
103 capacity: Capacity,
104 ) std.mem.Allocator.Error!Set {
105 const slots = try session_allocator.alloc(Slot, capacity.retained_global_count);
106 errdefer if (slots.len != 0) session_allocator.free(slots);
107 @memset(slots, null);
108 return .{
109 .session_allocator = session_allocator,
110 .slots = slots,
111 .interface_names = try session_allocator.alloc(
112 u8,
113 capacity.interface_name_bytes,
114 ),
115 .interface_name_byte_count_per_global = capacity.interface_name_byte_count_per_global,
116 };
117 }
118
119 pub fn deinit(self: *Set) void {
120 self.assertValid();
121 if (self.interface_names.len != 0) self.session_allocator.free(self.interface_names);
122 if (self.slots.len != 0) self.session_allocator.free(self.slots);
123 self.* = undefined;
124 }
125
126 pub fn prepareAdd(
127 self: *Set,
128 registry_id: u32,
129 name: u32,
130 interface: []const u8,
131 version: u32,
132 ) Error!Admission {
133 self.assertValid();
134 if (version == 0) return error.InvalidVersion;
135 var available_slot: ?usize = null;
136 for (self.slots, 0..) |slot, slot_index| {
137 const entry = slot orelse {
138 if (available_slot == null) available_slot = slot_index;
139 continue;
140 };
141 if (entry.registry_id == registry_id and entry.name == name) {
142 return error.DuplicateGlobal;
143 }
144 }
145 if (interface.len > self.interface_name_byte_count_per_global) {
146 self.interface_name_capacity_rejection_count +|= 1;
147 return error.GlobalInterfaceNameCapacityExceeded;
148 }
149 const slot_index = available_slot orelse {
150 self.capacity_rejection_count +|= 1;
151 return error.GlobalCapacityExceeded;
152 };
153 return .{
154 .slot_index = slot_index,
155 .registry_id = registry_id,
156 .name = name,
157 .interface_len = interface.len,
158 .version = version,
159 };
160 }
161
162 pub fn commitAdd(
163 self: *Set,
164 admission: Admission,
165 interface: []const u8,
166 ) Global {
167 self.assertValid();
168 std.debug.assert(admission.slot_index < self.slots.len);
169 std.debug.assert(self.slots[admission.slot_index] == null);
170 std.debug.assert(interface.len == admission.interface_len);
171 std.debug.assert(interface.len <= self.interface_name_byte_count_per_global);
172 std.debug.assert(admission.version != 0);
173 const storage = self.interfaceStorage(admission.slot_index);
174 @memcpy(storage[0..interface.len], interface);
175 self.slots[admission.slot_index] = .{
176 .registry_id = admission.registry_id,
177 .name = admission.name,
178 .interface_len = interface.len,
179 .version = admission.version,
180 };
181 self.count += 1;
182 self.assertValid();
183 return self.globalAt(admission.slot_index);
184 }
185
186 pub fn add(
187 self: *Set,
188 registry_id: u32,
189 name: u32,
190 interface: []const u8,
191 version: u32,
192 ) Error!Global {
193 return self.commitAdd(
194 try self.prepareAdd(registry_id, name, interface, version),
195 interface,
196 );
197 }
198
199 pub fn get(self: *const Set, registry_id: u32, name: u32) ?Global {
200 self.assertValid();
201 for (self.slots, 0..) |slot, slot_index| {
202 const entry = slot orelse continue;
203 if (entry.registry_id == registry_id and entry.name == name) {
204 return self.globalAt(slot_index);
205 }
206 }
207 return null;
208 }
209
210 pub fn require(self: *const Set, registry_id: u32, name: u32) ModelError!Global {
211 return self.get(registry_id, name) orelse error.UnknownGlobal;
212 }
213
214 pub fn remove(self: *Set, registry_id: u32, name: u32) ModelError!void {
215 self.assertValid();
216 for (self.slots) |*slot| {
217 const entry = slot.* orelse continue;
218 if (entry.registry_id != registry_id or entry.name != name) continue;
219 slot.* = null;
220 std.debug.assert(self.count != 0);
221 self.count -= 1;
222 self.assertValid();
223 return;
224 }
225 return error.UnknownGlobal;
226 }
227
228 pub fn status(self: *const Set) Status {
229 self.assertValid();
230 const name_rejections = self.interface_name_capacity_rejection_count;
231 return .{
232 .global_capacity_rejection_count = self.capacity_rejection_count,
233 .global_interface_name_capacity_rejection_count = name_rejections,
234 };
235 }
236
237 fn globalAt(self: *const Set, slot_index: usize) Global {
238 const entry = self.slots[slot_index].?;
239 const storage = self.interfaceStorage(slot_index);
240 return .{
241 .registry_id = entry.registry_id,
242 .name = entry.name,
243 .interface = storage[0..entry.interface_len],
244 .version = entry.version,
245 };
246 }
247
248 fn interfaceStorage(self: *const Set, slot_index: usize) []u8 {
249 const offset = slot_index * self.interface_name_byte_count_per_global;
250 const end = offset + self.interface_name_byte_count_per_global;
251 std.debug.assert(end <= self.interface_names.len);
252 return self.interface_names[offset..end];
253 }
254
255 fn assertValid(self: *const Set) void {
256 std.debug.assert(self.count <= self.slots.len);
257 std.debug.assert(
258 self.interface_names.len ==
259 self.slots.len * self.interface_name_byte_count_per_global,
260 );
261 var count: usize = 0;
262 for (self.slots, 0..) |slot, slot_index| {
263 const entry = slot orelse continue;
264 count += 1;
265 std.debug.assert(entry.interface_len <= self.interface_name_byte_count_per_global);
266 for (self.slots[slot_index + 1 ..]) |other_slot| {
267 const other = other_slot orelse continue;
268 if (entry.registry_id == other.registry_id) {
269 std.debug.assert(entry.name != other.name);
270 }
271 }
272 }
273 std.debug.assert(count == self.count);
274 }
275 };
276
277 test "global capacity derives exact entry and stable name regions" {
278 try std.testing.expectEqual(
279 @as(usize, 256),
280 default_capacity.retained_global_count,
281 );
282 try std.testing.expectEqual(
283 @as(usize, 128),
284 default_capacity.interface_name_byte_count_per_global,
285 );
286 const capacity = try Capacity.derive(.{
287 .retained_global_count = 3,
288 .interface_name_byte_count_per_global = 5,
289 });
290 try std.testing.expectEqual(@as(usize, 3), capacity.retained_global_count);
291 try std.testing.expectEqual(@as(usize, 5), capacity.interface_name_byte_count_per_global);
292 try std.testing.expectEqual(3 * @sizeOf(Slot), capacity.retained_global_bytes);
293 try std.testing.expectEqual(@as(usize, 15), capacity.interface_name_bytes);
294 try std.testing.expectEqual(
295 capacity.retained_global_bytes + capacity.interface_name_bytes,
296 capacity.total_requested_bytes,
297 );
298 try std.testing.expectError(error.CapacityOverflow, Capacity.derive(.{
299 .retained_global_count = std.math.maxInt(usize),
300 .interface_name_byte_count_per_global = 2,
301 }));
302 }
303
304 test "default global names cover every generated interface with headroom" {
305 var maximum_name_len: usize = 0;
306 for (wayland.protocol.interfaces) |interface| {
307 maximum_name_len = @max(maximum_name_len, interface.name.len);
308 }
309 try std.testing.expect(
310 maximum_name_len * 2 <= default_interface_name_byte_count_per_global,
311 );
312 }
313
314 test "global storage acquires both regions before use" {
315 const capacity = try Capacity.derive(.{
316 .retained_global_count = 3,
317 .interface_name_byte_count_per_global = 5,
318 });
319 for (0..2) |fail_index| {
320 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{
321 .fail_index = fail_index,
322 });
323 try std.testing.expectError(error.OutOfMemory, Set.init(failing.allocator(), capacity));
324 }
325 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{
326 .fail_index = 2,
327 });
328 var set = try Set.init(failing.allocator(), capacity);
329 defer set.deinit();
330 try std.testing.expectEqual(@as(usize, 2), failing.allocations);
331 }
332
333 test "globals are scoped to the registry that announced them" {
334 var set = try Set.init(std.testing.allocator, default_capacity);
335 defer set.deinit();
336
337 const first = try set.add(2, 7, "wl_seat", 9);
338 _ = try set.add(3, 7, "wl_output", 4);
339 try std.testing.expectEqualStrings("wl_seat", first.interface);
340 try std.testing.expectEqualStrings("wl_output", (try set.require(3, 7)).interface);
341 try std.testing.expectError(error.DuplicateGlobal, set.add(2, 7, "wl_seat", 9));
342 try set.remove(2, 7);
343 try std.testing.expectError(error.UnknownGlobal, set.require(2, 7));
344 try std.testing.expectError(error.UnknownGlobal, set.remove(2, 7));
345 }
346
347 test "unrelated removal and slot reuse preserve global name views" {
348 const capacity = try Capacity.derive(.{
349 .retained_global_count = 2,
350 .interface_name_byte_count_per_global = 8,
351 });
352 var set = try Set.init(std.testing.allocator, capacity);
353 defer set.deinit();
354 const first = try set.add(2, 7, "wl_seat", 9);
355 _ = try set.add(2, 8, "wl_shm", 1);
356 const first_name_pointer = first.interface.ptr;
357
358 try set.remove(2, 8);
359 _ = try set.add(2, 9, "wl_touch", 1);
360 try std.testing.expectEqual(first_name_pointer, (try set.require(2, 7)).interface.ptr);
361 try std.testing.expectEqualStrings("wl_seat", first.interface);
362 }
363
364 test "global max plus one preserves storage and saturates status" {
365 const capacity = try Capacity.derive(.{
366 .retained_global_count = 1,
367 .interface_name_byte_count_per_global = 3,
368 });
369 var set = try Set.init(std.testing.allocator, capacity);
370 defer set.deinit();
371 const slots = set.slots.ptr;
372 const names = set.interface_names.ptr;
373
374 _ = try set.add(2, 7, "abc", 1);
375 try std.testing.expectError(error.GlobalCapacityExceeded, set.add(2, 8, "a", 1));
376 try set.remove(2, 7);
377 try std.testing.expectError(
378 error.GlobalInterfaceNameCapacityExceeded,
379 set.add(2, 8, "abcd", 1),
380 );
381 try std.testing.expectEqual(slots, set.slots.ptr);
382 try std.testing.expectEqual(names, set.interface_names.ptr);
383 try std.testing.expectEqual(@as(u64, 1), set.status().global_capacity_rejection_count);
384 try std.testing.expectEqual(
385 @as(u64, 1),
386 set.status().global_interface_name_capacity_rejection_count,
387 );
388
389 set.capacity_rejection_count = std.math.maxInt(u64);
390 set.interface_name_capacity_rejection_count = std.math.maxInt(u64);
391 _ = try set.add(2, 7, "abc", 1);
392 try std.testing.expectError(error.GlobalCapacityExceeded, set.add(2, 8, "a", 1));
393 try set.remove(2, 7);
394 try std.testing.expectError(
395 error.GlobalInterfaceNameCapacityExceeded,
396 set.add(2, 8, "abcd", 1),
397 );
398 try std.testing.expectEqual(
399 std.math.maxInt(u64),
400 set.status().global_capacity_rejection_count,
401 );
402 try std.testing.expectEqual(
403 std.math.maxInt(u64),
404 set.status().global_interface_name_capacity_rejection_count,
405 );
406 }
407
408 test "global admission does not mutate retained state" {
409 const capacity = try Capacity.derive(.{
410 .retained_global_count = 1,
411 .interface_name_byte_count_per_global = 8,
412 });
413 var set = try Set.init(std.testing.allocator, capacity);
414 defer set.deinit();
415
416 const admission = try set.prepareAdd(2, 7, "wl_seat", 9);
417 try std.testing.expect(set.get(2, 7) == null);
418 _ = set.commitAdd(admission, "wl_seat");
419 try std.testing.expectEqualStrings("wl_seat", (try set.require(2, 7)).interface);
420 }