lib/wayland/src/ids.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 pub const display_id: u32 = 1;
4 pub const first_dynamic_id: u32 = 2;
5 pub const first_server_id: u32 = 0xff000000;
6 pub const maximum_client_id_count: usize = first_server_id - first_dynamic_id;
7 pub const default_client_id_count: usize = 256;
8
9 pub const Limits = struct {
10 client_id_count: usize = default_client_id_count,
11 };
12
13 pub const CapacityError = error{
14 ClientIdStorageTooLarge,
15 CapacityOverflow,
16 };
17
18 pub const Capacity = struct {
19 client_id_count: usize,
20 state_bytes: usize,
21 reusable_id_bytes: usize,
22 total_requested_bytes: usize,
23
24 pub fn derive(limits: Limits) CapacityError!Capacity {
25 if (limits.client_id_count > maximum_client_id_count) {
26 return error.ClientIdStorageTooLarge;
27 }
28 const state_bytes = std.math.mul(
29 usize,
30 limits.client_id_count,
31 @sizeOf(State),
32 ) catch return error.CapacityOverflow;
33 const reusable_id_bytes = std.math.mul(
34 usize,
35 limits.client_id_count,
36 @sizeOf(u32),
37 ) catch return error.CapacityOverflow;
38 const total_requested_bytes = std.math.add(
39 usize,
40 state_bytes,
41 reusable_id_bytes,
42 ) catch return error.CapacityOverflow;
43 return .{
44 .client_id_count = limits.client_id_count,
45 .state_bytes = state_bytes,
46 .reusable_id_bytes = reusable_id_bytes,
47 .total_requested_bytes = total_requested_bytes,
48 };
49 }
50 };
51
52 pub const StorageError = error{ClientIdCapacityExceeded};
53
54 pub const LifecycleError = error{
55 InvalidObjectId,
56 UnknownObject,
57 ObjectAlreadyRetired,
58 ObjectStillLive,
59 DeleteAlreadyAcknowledged,
60 };
61
62 pub const Error = StorageError || LifecycleError;
63
64 pub const Status = struct {
65 client_id_capacity_rejection_count: u64 = 0,
66 };
67
68 pub const default_capacity = Capacity.derive(.{}) catch unreachable;
69
70 const State = enum {
71 live,
72 awaiting_delete,
73 reusable,
74 };
75
76 pub const Pool = struct {
77 session_allocator: std.mem.Allocator,
78 states: []State,
79 reusable: []u32,
80 state_count: usize = 0,
81 reusable_count: usize = 0,
82 capacity_rejection_count: u64 = 0,
83
84 pub fn init(
85 session_allocator: std.mem.Allocator,
86 capacity: Capacity,
87 ) std.mem.Allocator.Error!Pool {
88 const states = try session_allocator.alloc(State, capacity.client_id_count);
89 errdefer if (states.len != 0) session_allocator.free(states);
90 return .{
91 .session_allocator = session_allocator,
92 .states = states,
93 .reusable = try session_allocator.alloc(u32, capacity.client_id_count),
94 };
95 }
96
97 pub fn deinit(self: *Pool) void {
98 self.assertValid();
99 if (self.reusable.len != 0) self.session_allocator.free(self.reusable);
100 if (self.states.len != 0) self.session_allocator.free(self.states);
101 self.* = undefined;
102 }
103
104 pub fn allocate(self: *Pool) StorageError!u32 {
105 self.assertValid();
106 if (self.reusable_count != 0) {
107 self.reusable_count -= 1;
108 const id = self.reusable[self.reusable_count];
109 self.states[index(id)] = .live;
110 return id;
111 }
112
113 if (self.state_count == self.states.len) {
114 self.capacity_rejection_count +|= 1;
115 return error.ClientIdCapacityExceeded;
116 }
117 const id = first_dynamic_id + @as(u32, @intCast(self.state_count));
118 self.states[self.state_count] = .live;
119 self.state_count += 1;
120 return id;
121 }
122
123 pub fn abandon(self: *Pool, id: u32) LifecycleError!void {
124 const at = try self.knownIndex(id);
125 switch (self.states[at]) {
126 .live => {
127 std.debug.assert(self.reusable_count < self.reusable.len);
128 self.states[at] = .reusable;
129 self.reusable[self.reusable_count] = id;
130 self.reusable_count += 1;
131 },
132 .awaiting_delete => return error.ObjectAlreadyRetired,
133 .reusable => return error.DeleteAlreadyAcknowledged,
134 }
135 }
136
137 pub fn retire(self: *Pool, id: u32) LifecycleError!void {
138 const at = try self.knownIndex(id);
139 switch (self.states[at]) {
140 .live => self.states[at] = .awaiting_delete,
141 .awaiting_delete => return error.ObjectAlreadyRetired,
142 .reusable => return error.DeleteAlreadyAcknowledged,
143 }
144 }
145
146 pub fn acknowledgeDelete(self: *Pool, id: u32) LifecycleError!void {
147 const at = try self.knownIndex(id);
148 switch (self.states[at]) {
149 .live => return error.ObjectStillLive,
150 .awaiting_delete => {
151 std.debug.assert(self.reusable_count < self.reusable.len);
152 self.reusable[self.reusable_count] = id;
153 self.reusable_count += 1;
154 self.states[at] = .reusable;
155 },
156 .reusable => return error.DeleteAlreadyAcknowledged,
157 }
158 }
159
160 pub fn isLive(self: *const Pool, id: u32) bool {
161 const at = self.knownIndex(id) catch return false;
162 return self.states[at] == .live;
163 }
164
165 pub fn status(self: *const Pool) Status {
166 self.assertValid();
167 return .{
168 .client_id_capacity_rejection_count = self.capacity_rejection_count,
169 };
170 }
171
172 fn knownIndex(self: *const Pool, id: u32) LifecycleError!usize {
173 self.assertValid();
174 if (id < first_dynamic_id or id >= first_server_id) return error.InvalidObjectId;
175 const at = index(id);
176 if (at >= self.state_count) return error.UnknownObject;
177 return at;
178 }
179
180 fn assertValid(self: *const Pool) void {
181 std.debug.assert(self.states.len == self.reusable.len);
182 std.debug.assert(self.states.len <= maximum_client_id_count);
183 std.debug.assert(self.state_count <= self.states.len);
184 std.debug.assert(self.reusable_count <= self.state_count);
185 }
186 };
187
188 fn index(id: u32) usize {
189 return @intCast(id - first_dynamic_id);
190 }
191
192 test "client ID capacity derives two exact storage regions" {
193 try std.testing.expectEqual(@as(usize, 256), default_capacity.client_id_count);
194 const capacity = try Capacity.derive(.{ .client_id_count = 3 });
195 try std.testing.expectEqual(@as(usize, 3), capacity.client_id_count);
196 try std.testing.expectEqual(3 * @sizeOf(State), capacity.state_bytes);
197 try std.testing.expectEqual(3 * @sizeOf(u32), capacity.reusable_id_bytes);
198 try std.testing.expectEqual(
199 capacity.state_bytes + capacity.reusable_id_bytes,
200 capacity.total_requested_bytes,
201 );
202 try std.testing.expectError(
203 error.ClientIdStorageTooLarge,
204 Capacity.derive(.{ .client_id_count = maximum_client_id_count + 1 }),
205 );
206 }
207
208 test "client ID storage is acquired before use" {
209 const capacity = try Capacity.derive(.{ .client_id_count = 3 });
210 for (0..2) |fail_index| {
211 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{
212 .fail_index = fail_index,
213 });
214 try std.testing.expectError(error.OutOfMemory, Pool.init(failing.allocator(), capacity));
215 }
216 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{
217 .fail_index = 2,
218 });
219 var pool = try Pool.init(failing.allocator(), capacity);
220 defer pool.deinit();
221 try std.testing.expectEqual(@as(usize, 2), failing.allocations);
222 }
223
224 test "object IDs become reusable only after delete_id acknowledgement" {
225 var pool = try Pool.init(std.testing.allocator, default_capacity);
226 defer pool.deinit();
227
228 try std.testing.expectEqual(@as(u32, 2), try pool.allocate());
229 try std.testing.expectEqual(@as(u32, 3), try pool.allocate());
230 try pool.retire(2);
231 try std.testing.expectEqual(@as(u32, 4), try pool.allocate());
232 try pool.acknowledgeDelete(2);
233 try std.testing.expectEqual(@as(u32, 2), try pool.allocate());
234 }
235
236 test "delete_id lifecycle rejects invalid transitions" {
237 var pool = try Pool.init(std.testing.allocator, default_capacity);
238 defer pool.deinit();
239
240 const id = try pool.allocate();
241 try std.testing.expectError(error.ObjectStillLive, pool.acknowledgeDelete(id));
242 try pool.retire(id);
243 try std.testing.expectError(error.ObjectAlreadyRetired, pool.retire(id));
244 try pool.acknowledgeDelete(id);
245 try std.testing.expectError(error.DeleteAlreadyAcknowledged, pool.acknowledgeDelete(id));
246 }
247
248 test "unsent object IDs can be abandoned without server acknowledgement" {
249 var pool = try Pool.init(std.testing.allocator, default_capacity);
250 defer pool.deinit();
251
252 const id = try pool.allocate();
253 try pool.abandon(id);
254 try std.testing.expectEqual(id, try pool.allocate());
255 try pool.abandon(id);
256 try std.testing.expectError(error.DeleteAlreadyAcknowledged, pool.abandon(id));
257 }
258
259 test "client ID max plus one preserves storage and saturates status" {
260 const capacity = try Capacity.derive(.{ .client_id_count = 2 });
261 var pool = try Pool.init(std.testing.allocator, capacity);
262 defer pool.deinit();
263 const states = pool.states.ptr;
264 const reusable = pool.reusable.ptr;
265
266 try std.testing.expectEqual(@as(u32, 2), try pool.allocate());
267 try std.testing.expectEqual(@as(u32, 3), try pool.allocate());
268 try std.testing.expectError(error.ClientIdCapacityExceeded, pool.allocate());
269 try std.testing.expectEqual(states, pool.states.ptr);
270 try std.testing.expectEqual(reusable, pool.reusable.ptr);
271 try std.testing.expectEqual(
272 @as(u64, 1),
273 pool.status().client_id_capacity_rejection_count,
274 );
275
276 pool.capacity_rejection_count = std.math.maxInt(u64);
277 try std.testing.expectError(error.ClientIdCapacityExceeded, pool.allocate());
278 try std.testing.expectEqual(
279 std.math.maxInt(u64),
280 pool.status().client_id_capacity_rejection_count,
281 );
282 }
283
284 test "every allocated ID has infallible rollback capacity" {
285 const capacity = try Capacity.derive(.{ .client_id_count = 65 });
286 var pool = try Pool.init(std.testing.allocator, capacity);
287 defer pool.deinit();
288
289 var allocated: [65]u32 = undefined;
290 for (&allocated) |*id| id.* = try pool.allocate();
291 for (allocated) |id| try pool.abandon(id);
292 for (0..allocated.len) |_| _ = try pool.allocate();
293 }