lib/reticulum/src/packet/hashlist.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const packet = @import("root.zig");
4
5 const TableLimits = struct {
6 hashes_max: usize,
7 };
8
9 const TableCapacity = struct {
10 hashes_max: usize,
11 storage_bytes: usize,
12
13 pub const DeriveError = error{ InvalidLimit, CapacityOverflow };
14
15 pub fn derive(limits: TableLimits) DeriveError!TableCapacity {
16 if (limits.hashes_max == 0) return error.InvalidLimit;
17 const hashes_max = limits.hashes_max;
18 const storage_bytes = alloc_phase.capacity.mul(
19 usize,
20 hashes_max,
21 @sizeOf(packet.Hash),
22 ) catch return error.CapacityOverflow;
23 return .{ .hashes_max = hashes_max, .storage_bytes = storage_bytes };
24 }
25 };
26
27 pub const Table = struct {
28 phase: alloc_phase.capacity.Phase,
29 capacity: Capacity,
30 storage: Storage,
31 hashes: []packet.Hash,
32 start: usize = 0,
33 len: usize = 0,
34 generation_len: usize = 0,
35
36 pub const storage_alignment: usize = 8;
37 pub const Storage = []align(storage_alignment) u8;
38 pub const Limits: type = TableLimits;
39 pub const Capacity: type = TableCapacity;
40 pub const InitError = Capacity.DeriveError || error{StorageLengthMismatch};
41 pub const work_limits: alloc_phase.capacity.WorkLimits = .{
42 .transition_steps_max = 1_000_001,
43 .cleanup_steps_per_call_max = 0,
44 .cleanup_calls_at_capacity_max = 0,
45 };
46 pub const claim: alloc_phase.capacity.Declaration = .{
47 .source = .{
48 .id = "reticulum.hashlist",
49 .kind = .phase_static,
50 .limit_source = .caller,
51 .storage = .{
52 .covered = &.{.{
53 .id = "caller_packet_hash_fifo",
54 .lifetime = .transferred,
55 .detail = "caller storage for a bounded FIFO of packet hashes",
56 }},
57 .excluded = &.{
58 "borrowed lookup hashes",
59 "encoded packets and wire hash computation",
60 },
61 },
62 .capacity = .{
63 .inputs = &.{alloc_phase.capacity.bindInput(
64 Limits,
65 "hashes_max",
66 "hashes_max",
67 )},
68 .type_selectors = &.{alloc_phase.capacity.bindType(packet.Hash, "hash")},
69 .nodes = &.{
70 .{ .input = 0 },
71 .{ .scale = .{
72 .node = 0,
73 .coefficient = .{ .size_of_concrete_type = 0 },
74 } },
75 },
76 .assertions = &.{.{
77 .scope = .closure_total,
78 .measure = .retained,
79 .relation = .exact,
80 .expression = 1,
81 }},
82 },
83 .overload = .{
84 .kind = .not_applicable,
85 .detail = "a new hash replaces the oldest hash when the FIFO is full",
86 },
87 .risks = .{
88 .transitive = .{
89 .status = .excluded,
90 .detail = "hash lookup and insertion call no allocating owner",
91 },
92 .foreign = .{
93 .status = .excluded,
94 .detail = "the hash FIFO crosses no foreign boundary",
95 },
96 },
97 .work = .{ .equation = "lookup scans at most hashes_max entries" },
98 .obligations = &.{
99 .{ .key = "reticulum_hashlist_capacity", .role = .capacity_model },
100 .{ .key = "reticulum_hashlist_replace", .role = .overload },
101 .{ .key = "reticulum_hashlist_work", .role = .work_bound },
102 },
103 },
104 .bindings = .{
105 .owner = @This(),
106 .seal = .{
107 .family = alloc_phase.capacity.selector(@This().activate),
108 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
109 },
110 .teardown = .{
111 .family = alloc_phase.capacity.selector(@This().deinit),
112 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
113 },
114 },
115 };
116
117 pub fn init(storage: Storage, limits: Limits) InitError!Table {
118 const capacity = try Capacity.derive(limits);
119 if (storage.len != capacity.storage_bytes) return error.StorageLengthMismatch;
120 return .{
121 .phase = .initialization,
122 .capacity = capacity,
123 .storage = storage,
124 .hashes = std.mem.bytesAsSlice(packet.Hash, storage),
125 };
126 }
127
128 pub fn activate(self: *Table) void {
129 std.debug.assert(self.phase == .initialization);
130 std.debug.assert(self.len == 0);
131 self.phase = .steady;
132 }
133
134 pub fn contains(self: *const Table, hash: packet.Hash) bool {
135 std.debug.assert(self.phase == .steady);
136 for (0..self.len) |offset| {
137 const index = (self.start + offset) % self.capacity.hashes_max;
138 if (std.mem.eql(u8, &self.hashes[index], &hash)) return true;
139 }
140 return false;
141 }
142
143 /// Adds the 32-byte SHA-256 digest that names a packet (*packet hash*) so
144 /// the caller recognizes a later copy of the same packet, and returns the
145 /// hash it pushed out, or null when it pushed none out. A hash the store
146 /// already holds is left where it is and null comes back. Once the store is
147 /// full the oldest hash leaves and the new one takes its slot, so the store
148 /// keeps the order the hashes arrived in, following Reticulum@1.5.0
149 /// RNS/Transport.py:167-168,803-805.
150 pub fn insert(self: *Table, hash: packet.Hash) ?packet.Hash {
151 std.debug.assert(self.phase == .steady);
152 std.debug.assert(self.len <= self.capacity.hashes_max);
153 if (self.contains(hash)) return null;
154 if (self.len < self.capacity.hashes_max) {
155 const index = (self.start + self.len) % self.capacity.hashes_max;
156 self.hashes[index] = hash;
157 self.len += 1;
158 self.generation_len += 1;
159 return null;
160 }
161 const evicted = self.hashes[self.start];
162 self.hashes[self.start] = hash;
163 self.start = (self.start + 1) % self.capacity.hashes_max;
164 if (self.generation_len < self.capacity.hashes_max) self.generation_len += 1;
165 return evicted;
166 }
167
168 /// Drops the hashes stored before the last rotation and keeps the ones
169 /// added since so the store keeps recent hashes and lets go of old ones on
170 /// a timer, following Reticulum@1.5.0 RNS/Transport.py:803-805. The call
171 /// returns with the store untouched until more than half its slots hold
172 /// hashes added since the last rotation.
173 pub fn rotate(self: *Table) void {
174 std.debug.assert(self.phase == .steady);
175 const threshold = self.capacity.hashes_max / 2;
176 if (self.generation_len <= threshold) return;
177 std.debug.assert(self.generation_len <= self.len);
178 const discarded = self.len - self.generation_len;
179 self.start = (self.start + discarded) % self.capacity.hashes_max;
180 self.len = self.generation_len;
181 self.generation_len = 0;
182 }
183
184 /// Removes a hash added since the last rotation and returns whether it was
185 /// there. A copy of that hash from before the last rotation stays. The
186 /// reference does this for a data packet of an encrypted session between
187 /// two endpoints (*link*) that arrived over a network interface (*carrier*)
188 /// the link does not run on, so the packet can be acted on again, following
189 /// Reticulum@1.5.0 RNS/Transport.py:2515-2516.
190 pub fn removeCurrent(self: *Table, hash: packet.Hash) bool {
191 std.debug.assert(self.phase == .steady);
192 std.debug.assert(self.generation_len <= self.len);
193 const first = self.len - self.generation_len;
194 for (first..self.len) |offset| {
195 const index = (self.start + offset) % self.capacity.hashes_max;
196 if (!std.mem.eql(u8, &self.hashes[index], &hash)) continue;
197 for (offset + 1..self.len) |later| {
198 const target = (self.start + later - 1) % self.capacity.hashes_max;
199 const source = (self.start + later) % self.capacity.hashes_max;
200 self.hashes[target] = self.hashes[source];
201 }
202 self.len -= 1;
203 self.generation_len -= 1;
204 std.debug.assert(self.generation_len <= self.len);
205 return true;
206 }
207 return false;
208 }
209
210 pub fn count(self: *const Table) usize {
211 std.debug.assert(self.phase == .steady);
212 return self.len;
213 }
214
215 pub fn deinit(self: *Table) Storage {
216 std.debug.assert(self.phase == .steady);
217 self.phase = .teardown;
218 const storage = self.storage;
219 self.* = undefined;
220 return storage;
221 }
222 };
223
224 comptime {
225 alloc_phase.capacity.requireProvisionedExactOwnerShape(Table);
226 }
227
228 test "hashlist admits maximum and evicts oldest at maximum plus one" {
229 comptime {
230 @stardustClaim(alloc_phase.capacity.witness(
231 Table,
232 "reticulum_hashlist_capacity",
233 ), null, null, null, null, null, null);
234 @stardustClaim(alloc_phase.capacity.witness(
235 Table,
236 "reticulum_hashlist_replace",
237 ), null, null, null, null, null, null);
238 @stardustClaim(alloc_phase.capacity.witness(
239 Table,
240 "reticulum_hashlist_work",
241 ), null, null, null, null, null, null);
242 }
243 const capacity = comptime TableCapacity.derive(.{ .hashes_max = 3 }) catch unreachable;
244 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
245 var table = try Table.init(&bytes, .{ .hashes_max = 3 });
246 table.activate();
247 defer _ = table.deinit();
248 for (1..4) |value| {
249 try std.testing.expect(table.insert(@splat(@as(u8, @intCast(value)))) == null);
250 }
251 try std.testing.expectEqual(@as(usize, 3), table.count());
252 try std.testing.expectEqual(@as(packet.Hash, @splat(1)), table.insert(@splat(4)).?);
253 try std.testing.expect(!table.contains(@splat(1)));
254 try std.testing.expect(table.contains(@splat(4)));
255 }
256
257 test "Reticulum@1.5.0 RNS/Transport.py:803-805 rotates bounded hash generations" {
258 const capacity = comptime TableCapacity.derive(.{ .hashes_max = 4 }) catch unreachable;
259 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
260 var table = try Table.init(&bytes, .{ .hashes_max = 4 });
261 table.activate();
262 defer _ = table.deinit();
263 for (1..4) |value| _ = table.insert(@splat(@as(u8, @intCast(value))));
264 table.rotate();
265 for (4..7) |value| _ = table.insert(@splat(@as(u8, @intCast(value))));
266 table.rotate();
267 try std.testing.expectEqual(@as(usize, 3), table.count());
268 try std.testing.expect(!table.contains(@splat(1)));
269 try std.testing.expect(table.contains(@splat(4)));
270 try std.testing.expect(table.contains(@splat(6)));
271 }
272
273 test "Reticulum@1.5.0 RNS/Transport.py:2515-2516 removes a hash from the current generation" {
274 const capacity = comptime TableCapacity.derive(.{ .hashes_max = 4 }) catch unreachable;
275 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
276 var table = try Table.init(&bytes, .{ .hashes_max = 4 });
277 table.activate();
278 defer _ = table.deinit();
279 for (1..4) |value| _ = table.insert(@splat(@as(u8, @intCast(value))));
280 table.rotate();
281 _ = table.insert(@splat(4));
282 try std.testing.expect(!table.removeCurrent(@splat(2)));
283 try std.testing.expect(table.contains(@splat(2)));
284 try std.testing.expect(table.removeCurrent(@splat(4)));
285 try std.testing.expect(!table.contains(@splat(4)));
286 _ = table.insert(@splat(5));
287 try std.testing.expectEqual(@as(packet.Hash, @splat(1)), table.insert(@splat(6)).?);
288 try std.testing.expect(table.removeCurrent(@splat(5)));
289 try std.testing.expectEqual(@as(usize, 3), table.count());
290 try std.testing.expect(table.contains(@splat(2)));
291 try std.testing.expect(table.contains(@splat(3)));
292 try std.testing.expect(table.contains(@splat(6)));
293 try std.testing.expect(!table.contains(@splat(5)));
294 }