lib/simd/src/topology/model.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const simd = @import("../root.zig");
4
5 pub const max_logical_processors: usize = 1024;
6 pub const max_smt: usize = 16;
7 pub const LogicalProcessorSet = simd.bitset.BitSet4096(max_logical_processors);
8
9 pub const LP = packed struct {
10 cluster: u16 = 0,
11 core: u16 = 0,
12 package: u8 = 0,
13 smt: u8 = 0,
14 node: u8 = 0,
15 reserved: u8 = 0,
16 };
17
18 pub const Cluster = struct {
19 lps: LogicalProcessorSet = .{},
20 private_kib: u64 = 0,
21 shared_kib: u64 = 0,
22 reserved1: u64 = 0,
23 reserved2: u64 = 0,
24 reserved3: u64 = 0,
25 };
26
27 pub const Core = struct {
28 lps: LogicalProcessorSet = .{},
29 reserved: u64 = 0,
30 };
31
32 pub const Package = struct {
33 clusters: []const Cluster,
34 cores: []const Core,
35 };
36
37 pub const Cache = packed struct {
38 size_kib: u32 = 0,
39 sets: u32 = 0,
40 bytes_per_line: u16 = 0,
41 associativity: u16 = 0,
42 cores_sharing: u16 = 0,
43 reserved: u16 = 0,
44
45 pub const max_associativity: u16 = 128;
46 };
47
48 pub const ProcessorRecord = struct {
49 package_id: u64,
50 cluster_id: u64,
51 core_id: u64,
52 node: u8 = 0,
53 private_kib: u64 = 0,
54 shared_kib: u64 = 0,
55 };
56
57 pub const CapacityError = error{
58 EmptyTopology,
59 TooManyLogicalProcessors,
60 TooManyPackages,
61 TooManySiblings,
62 AllocationSizeOverflow,
63 };
64
65 pub const Error = std.mem.Allocator.Error || CapacityError;
66
67 pub fn computeCacheSets(cache: *Cache) bool {
68 if (cache.size_kib == 0) {
69 cache.sets = 0;
70 return true;
71 }
72 if (cache.bytes_per_line == 0 or cache.associativity == 0) return false;
73 const bytes = @as(u64, cache.size_kib) * 1024;
74 const computed = bytes / cache.bytes_per_line / cache.associativity;
75 if (computed > std.math.maxInt(u32)) return false;
76 if (cache.sets == 0) {
77 cache.sets = @intCast(computed);
78 return true;
79 }
80 const actual: u64 = cache.sets;
81 return actual >= computed and actual - computed <= 1;
82 }
83
84 const max_packages: usize = std.math.maxInt(u8) + 1;
85 const storage_alignment: std.mem.Alignment = std.mem.Alignment.of(Cluster)
86 .max(std.mem.Alignment.of(Core))
87 .max(std.mem.Alignment.of(Package))
88 .max(std.mem.Alignment.of(LP));
89
90 const PackageSize = struct {
91 clusters: usize = 0,
92 cores: usize = 0,
93 };
94
95 pub const TopologyLimits = struct {
96 records: []const ProcessorRecord,
97 };
98
99 pub const TopologyCapacity = struct {
100 logical_processors: usize = 0,
101 packages: usize = 0,
102 clusters: usize = 0,
103 cores: usize = 0,
104 storage_bytes: usize = 0,
105
106 pub fn derive(limits: TopologyLimits) CapacityError!TopologyCapacity {
107 var mapped_lps: [max_logical_processors]LP = @splat(.{});
108 var package_sizes: [max_packages]PackageSize = @splat(.{});
109 return inspectRecords(limits.records, &mapped_lps, &package_sizes);
110 }
111 };
112
113 pub const Topology = struct {
114 phase: alloc_phase.capacity.Phase = .initialization,
115 capacity: TopologyCapacity = .{},
116 allocation: ?[]align(storage_alignment.toByteUnits()) u8 = null,
117 packages: []const Package = &.{},
118 lps: []const LP = &.{},
119
120 pub const Limits: type = TopologyLimits;
121 pub const Capacity: type = TopologyCapacity;
122
123 pub const claim: alloc_phase.capacity.Declaration = .{
124 .source = .{
125 .id = "simd.topology_storage",
126 .kind = .phase_static,
127 .limit_source = .caller,
128 .storage = .{
129 .covered = &.{
130 .{
131 .id = "one_exact_topology_array_region_and_borrowed_views",
132 .lifetime = .steady,
133 .detail = "one exact topology array region and borrowed views",
134 },
135 },
136 .excluded = &.{
137 "caller-owned processor discovery records",
138 "operating-system queries and temporary relationship buffers",
139 },
140 },
141 .capacity = .{
142 .inputs = &.{},
143 .type_selectors = &.{},
144 .nodes = &.{
145 .{ .constant = 0 },
146 },
147 .assertions = &.{.{
148 .scope = .closure_total,
149 .measure = .retained,
150 .relation = .exact,
151 .expression = 0,
152 }},
153 },
154 .overload = .{
155 .kind = .reject_before_seal,
156 .detail = "empty oversize package and SMT bounds reject before allocation",
157 },
158 .risks = .{
159 .transitive = .{
160 .status = .witnessed,
161 .detail = "remapping placement and allocation cleanup are checked together",
162 },
163 .foreign = .{
164 .status = .excluded,
165 .detail = "native discovery completes before immutable topology storage is sealed",
166 },
167 },
168 .obligations = &.{
169 .{ .key = "simd_topology_capacity_capacity_model", .role = .capacity_model },
170 .{ .key = "simd_topology_capacity_overload", .role = .overload },
171 .{ .key = "simd_topology_remap", .role = .transitive_risk },
172 .{ .key = "simd_topology_oom", .role = .transitive_risk },
173 .{ .key = "simd_topology_native", .role = .foreign_risk },
174 },
175 },
176 .bindings = .{
177 .owner = @This(),
178 .seal = .{
179 .family = alloc_phase.capacity.selector(@This().activate),
180 .premise = .{
181 .class = .checked_semantic_fact,
182 .authority = .checker,
183 },
184 },
185 .teardown = .{
186 .family = alloc_phase.capacity.selector(@This().deinit),
187 .premise = .{
188 .class = .checked_semantic_fact,
189 .authority = .checker,
190 },
191 },
192 },
193 };
194
195 pub fn init(
196 allocator: std.mem.Allocator,
197 limits: Limits,
198 ) Error!Topology {
199 const records = limits.records;
200 var mapped_lps: [max_logical_processors]LP = @splat(.{});
201 var package_sizes: [max_packages]PackageSize = @splat(.{});
202 const capacity_value = try inspectRecords(records, &mapped_lps, &package_sizes);
203 const allocation = try allocator.alignedAlloc(
204 u8,
205 storage_alignment,
206 capacity_value.storage_bytes,
207 );
208 errdefer allocator.free(allocation);
209 @memset(allocation, 0);
210
211 var offset: usize = 0;
212 const packages = take(Package, allocation, &offset, capacity_value.packages);
213 const clusters = take(Cluster, allocation, &offset, capacity_value.clusters);
214 const cores = take(Core, allocation, &offset, capacity_value.cores);
215 const lps = take(LP, allocation, &offset, capacity_value.logical_processors);
216 std.debug.assert(offset == capacity_value.storage_bytes);
217 @memcpy(lps, mapped_lps[0..records.len]);
218 placePackageSlices(packages, clusters, cores, &package_sizes);
219 populateSets(packages, lps, records);
220 return .{
221 .phase = .initialization,
222 .capacity = capacity_value,
223 .allocation = allocation,
224 .packages = packages,
225 .lps = lps,
226 };
227 }
228
229 pub fn initFromRecords(
230 allocator: std.mem.Allocator,
231 records: []const ProcessorRecord,
232 ) Error!Topology {
233 var topology = try init(allocator, .{ .records = records });
234 topology.activate();
235 return topology;
236 }
237
238 pub fn activate(self: *Topology) void {
239 std.debug.assert(self.phase == .initialization);
240 std.debug.assert(self.capacity.logical_processors == self.lps.len);
241 self.phase = .steady;
242 }
243
244 pub fn deinit(self: *Topology, allocator: std.mem.Allocator) void {
245 std.debug.assert(self.phase != .teardown);
246 self.phase = .teardown;
247 if (self.allocation) |allocation| allocator.free(allocation);
248 self.allocation = null;
249 self.packages = &.{};
250 self.lps = &.{};
251 }
252
253 pub fn allocatedBytes(self: *const Topology) usize {
254 std.debug.assert(self.phase != .teardown);
255 return if (self.allocation) |allocation| allocation.len else 0;
256 }
257 };
258
259 fn inspectRecords(
260 records: []const ProcessorRecord,
261 mapped_lps: *[max_logical_processors]LP,
262 package_sizes: *[max_packages]PackageSize,
263 ) CapacityError!TopologyCapacity {
264 if (records.len == 0) return error.EmptyTopology;
265 if (records.len > max_logical_processors) return error.TooManyLogicalProcessors;
266 var package_count: usize = 0;
267 for (records, 0..) |record, index| {
268 const package = try mapPackage(records, mapped_lps, index, &package_count);
269 const cluster = mapMember(
270 records,
271 mapped_lps,
272 index,
273 package,
274 .cluster,
275 package_sizes[package].clusters,
276 );
277 if (cluster.is_new) package_sizes[package].clusters += 1;
278 const core = mapMember(
279 records,
280 mapped_lps,
281 index,
282 package,
283 .core,
284 package_sizes[package].cores,
285 );
286 if (core.is_new) package_sizes[package].cores += 1;
287 const smt = countSiblings(mapped_lps, index, package, core.index);
288 if (smt >= max_smt) return error.TooManySiblings;
289 mapped_lps[index] = .{
290 .cluster = @intCast(cluster.index),
291 .core = @intCast(core.index),
292 .package = @intCast(package),
293 .smt = @intCast(smt),
294 .node = record.node,
295 };
296 }
297 var cluster_count: usize = 0;
298 var core_count: usize = 0;
299 for (package_sizes[0..package_count]) |size| {
300 cluster_count = std.math.add(usize, cluster_count, size.clusters) catch
301 return error.AllocationSizeOverflow;
302 core_count = std.math.add(usize, core_count, size.cores) catch
303 return error.AllocationSizeOverflow;
304 }
305 return .{
306 .logical_processors = records.len,
307 .packages = package_count,
308 .clusters = cluster_count,
309 .cores = core_count,
310 .storage_bytes = try storageBytes(
311 records.len,
312 package_count,
313 cluster_count,
314 core_count,
315 ),
316 };
317 }
318
319 fn placePackageSlices(
320 packages: []Package,
321 clusters: []Cluster,
322 cores: []Core,
323 package_sizes: *const [max_packages]PackageSize,
324 ) void {
325 var cluster_offset: usize = 0;
326 var core_offset: usize = 0;
327 for (packages, package_sizes[0..packages.len]) |*package, size| {
328 package.* = .{
329 .clusters = clusters[cluster_offset..][0..size.clusters],
330 .cores = cores[core_offset..][0..size.cores],
331 };
332 cluster_offset += size.clusters;
333 core_offset += size.cores;
334 }
335 std.debug.assert(cluster_offset == clusters.len);
336 std.debug.assert(core_offset == cores.len);
337 }
338
339 fn populateSets(
340 packages: []Package,
341 lps: []const LP,
342 records: []const ProcessorRecord,
343 ) void {
344 for (lps, records, 0..) |lp, record, index| {
345 const package = &packages[lp.package];
346 const cluster = @constCast(&package.clusters[lp.cluster]);
347 const core = @constCast(&package.cores[lp.core]);
348 cluster.lps.set(index);
349 core.lps.set(index);
350 if (cluster.private_kib == 0) cluster.private_kib = record.private_kib;
351 if (cluster.shared_kib == 0) cluster.shared_kib = record.shared_kib;
352 }
353 }
354
355 const Member = enum {
356 cluster,
357 core,
358 };
359
360 const MappedMember = struct {
361 index: usize,
362 is_new: bool,
363 };
364
365 fn mapPackage(
366 records: []const ProcessorRecord,
367 lps: *const [max_logical_processors]LP,
368 index: usize,
369 package_count: *usize,
370 ) CapacityError!usize {
371 for (records[0..index], 0..) |prior, prior_index| {
372 if (prior.package_id == records[index].package_id) return lps[prior_index].package;
373 }
374 if (package_count.* == max_packages) return error.TooManyPackages;
375 const mapped = package_count.*;
376 package_count.* += 1;
377 return mapped;
378 }
379
380 fn mapMember(
381 records: []const ProcessorRecord,
382 lps: *const [max_logical_processors]LP,
383 index: usize,
384 package: usize,
385 member: Member,
386 next: usize,
387 ) MappedMember {
388 const wanted = memberId(records[index], member);
389 for (records[0..index], 0..) |prior, prior_index| {
390 const prior_lp = lps[prior_index];
391 if (prior_lp.package == package and memberId(prior, member) == wanted) {
392 return .{
393 .index = switch (member) {
394 .cluster => prior_lp.cluster,
395 .core => prior_lp.core,
396 },
397 .is_new = false,
398 };
399 }
400 }
401 return .{ .index = next, .is_new = true };
402 }
403
404 fn memberId(record: ProcessorRecord, member: Member) u64 {
405 return switch (member) {
406 .cluster => record.cluster_id,
407 .core => record.core_id,
408 };
409 }
410
411 fn countSiblings(
412 lps: *const [max_logical_processors]LP,
413 end: usize,
414 package: usize,
415 core: usize,
416 ) usize {
417 var count: usize = 0;
418 for (lps[0..end]) |lp| {
419 if (lp.package == package and lp.core == core) count += 1;
420 }
421 return count;
422 }
423
424 fn storageBytes(
425 lp_count: usize,
426 package_count: usize,
427 cluster_count: usize,
428 core_count: usize,
429 ) CapacityError!usize {
430 var offset: usize = 0;
431 try addTypeBytes(Package, &offset, package_count);
432 try addTypeBytes(Cluster, &offset, cluster_count);
433 try addTypeBytes(Core, &offset, core_count);
434 try addTypeBytes(LP, &offset, lp_count);
435 return offset;
436 }
437
438 fn addTypeBytes(comptime T: type, offset: *usize, count: usize) CapacityError!void {
439 offset.* = std.mem.Alignment.of(T).forward(offset.*);
440 const bytes = std.math.mul(usize, @sizeOf(T), count) catch
441 return error.AllocationSizeOverflow;
442 offset.* = std.math.add(usize, offset.*, bytes) catch
443 return error.AllocationSizeOverflow;
444 }
445
446 fn take(
447 comptime T: type,
448 allocation: []align(storage_alignment.toByteUnits()) u8,
449 offset: *usize,
450 count: usize,
451 ) []T {
452 offset.* = std.mem.Alignment.of(T).forward(offset.*);
453 const pointer: [*]T = @ptrCast(@alignCast(allocation.ptr + offset.*));
454 const values = pointer[0..count];
455 offset.* += @sizeOf(T) * count;
456 return values;
457 }
458
459 const SetAdder = struct {
460 set: *LogicalProcessorSet,
461
462 pub fn call(self: *@This(), index: usize) void {
463 self.set.set(index);
464 }
465 };
466
467 fn expectCoverage(topology: *const Topology) !void {
468 var cluster_union = LogicalProcessorSet{};
469 var core_union = LogicalProcessorSet{};
470 var cluster_total: usize = 0;
471 var core_total: usize = 0;
472 for (topology.packages) |package| {
473 try std.testing.expect(package.clusters.len != 0);
474 try std.testing.expect(package.cores.len != 0);
475 try std.testing.expect(package.clusters.len <= package.cores.len);
476 for (package.clusters) |cluster| {
477 cluster_total += cluster.lps.count();
478 var add = SetAdder{ .set = &cluster_union };
479 cluster.lps.foreach(&add);
480 }
481 for (package.cores) |core| {
482 core_total += core.lps.count();
483 var add = SetAdder{ .set = &core_union };
484 core.lps.foreach(&add);
485 }
486 }
487 try std.testing.expectEqual(topology.lps.len, cluster_total);
488 try std.testing.expectEqual(topology.lps.len, core_total);
489 try std.testing.expectEqual(topology.lps.len, cluster_union.count());
490 try std.testing.expectEqual(topology.lps.len, core_union.count());
491 }
492
493 fn checkInitFailures(allocator: std.mem.Allocator) !void {
494 const records = [_]ProcessorRecord{
495 .{ .package_id = 9, .cluster_id = 42, .core_id = 100 },
496 .{ .package_id = 9, .cluster_id = 42, .core_id = 100 },
497 .{ .package_id = 9, .cluster_id = 42, .core_id = 101 },
498 .{ .package_id = 4, .cluster_id = 7, .core_id = 5 },
499 };
500 var topology = try Topology.initFromRecords(allocator, &records);
501 topology.deinit(allocator);
502 }
503
504 test "Highway topology remaps opaque IDs and covers every logical processor" {
505 comptime {
506 alloc_phase.capacity.record(alloc_phase.capacity.witness(Topology, "simd_topology_remap"));
507 }
508
509 const records = [_]ProcessorRecord{
510 .{
511 .package_id = 9,
512 .cluster_id = 42,
513 .core_id = 100,
514 .node = 3,
515 .private_kib = 512,
516 .shared_kib = 4096,
517 },
518 .{ .package_id = 9, .cluster_id = 42, .core_id = 100, .node = 3 },
519 .{ .package_id = 9, .cluster_id = 42, .core_id = 101, .node = 3 },
520 .{
521 .package_id = 4,
522 .cluster_id = 7,
523 .core_id = 5,
524 .node = 8,
525 .private_kib = 1024,
526 },
527 .{ .package_id = 4, .cluster_id = 8, .core_id = 6, .node = 8 },
528 };
529 var topology = try Topology.initFromRecords(std.testing.allocator, &records);
530 defer topology.deinit(std.testing.allocator);
531 try std.testing.expectEqual(@as(usize, 2), topology.packages.len);
532 try std.testing.expectEqual(@as(usize, 5), topology.lps.len);
533 try std.testing.expectEqual(@as(usize, 1), topology.packages[0].clusters.len);
534 try std.testing.expectEqual(@as(usize, 2), topology.packages[0].cores.len);
535 try std.testing.expectEqual(@as(usize, 2), topology.packages[1].clusters.len);
536 try std.testing.expectEqual(@as(usize, 2), topology.packages[1].cores.len);
537 try std.testing.expectEqual(@as(u8, 0), topology.lps[0].smt);
538 try std.testing.expectEqual(@as(u8, 1), topology.lps[1].smt);
539 try std.testing.expectEqual(@as(u8, 8), topology.lps[4].node);
540 try std.testing.expectEqual(@as(u64, 512), topology.packages[0].clusters[0].private_kib);
541 try std.testing.expectEqual(@as(u64, 4096), topology.packages[0].clusters[0].shared_kib);
542 try expectCoverage(&topology);
543 }
544
545 test "Highway topology keeps one persistent bounded allocation" {
546 const records = [_]ProcessorRecord{
547 .{ .package_id = 0, .cluster_id = 0, .core_id = 0 },
548 .{ .package_id = 0, .cluster_id = 0, .core_id = 1 },
549 };
550 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{});
551 var topology = try Topology.initFromRecords(failing.allocator(), &records);
552 defer topology.deinit(failing.allocator());
553 try std.testing.expectEqual(@as(usize, 1), failing.alloc_index);
554 try std.testing.expectEqual(alloc_phase.capacity.Phase.steady, topology.phase);
555 try std.testing.expectEqual(topology.capacity.storage_bytes, topology.allocatedBytes());
556 try std.testing.expect(topology.allocatedBytes() >= @sizeOf(Cluster) + 2 * @sizeOf(Core));
557 }
558
559 test "Highway topology capacity matches its single-region placement" {
560 comptime {
561 alloc_phase.capacity.record(
562 alloc_phase.capacity.witness(Topology, "simd_topology_capacity_capacity_model"),
563 );
564 }
565 comptime {
566 alloc_phase.capacity.record(
567 alloc_phase.capacity.witness(Topology, "simd_topology_capacity_overload"),
568 );
569 }
570
571 const records = [_]ProcessorRecord{
572 .{ .package_id = 9, .cluster_id = 42, .core_id = 100 },
573 .{ .package_id = 9, .cluster_id = 42, .core_id = 100 },
574 .{ .package_id = 9, .cluster_id = 42, .core_id = 101 },
575 .{ .package_id = 4, .cluster_id = 7, .core_id = 5 },
576 .{ .package_id = 4, .cluster_id = 8, .core_id = 6 },
577 };
578 const capacity = try TopologyCapacity.derive(.{ .records = &records });
579 try std.testing.expectEqual(@as(usize, 5), capacity.logical_processors);
580 try std.testing.expectEqual(@as(usize, 2), capacity.packages);
581 try std.testing.expectEqual(@as(usize, 3), capacity.clusters);
582 try std.testing.expectEqual(@as(usize, 4), capacity.cores);
583 var independent_bytes: usize = 0;
584 independent_bytes = std.mem.Alignment.of(Package).forward(independent_bytes);
585 independent_bytes += @sizeOf(Package) * capacity.packages;
586 independent_bytes = std.mem.Alignment.of(Cluster).forward(independent_bytes);
587 independent_bytes += @sizeOf(Cluster) * capacity.clusters;
588 independent_bytes = std.mem.Alignment.of(Core).forward(independent_bytes);
589 independent_bytes += @sizeOf(Core) * capacity.cores;
590 independent_bytes = std.mem.Alignment.of(LP).forward(independent_bytes);
591 independent_bytes += @sizeOf(LP) * capacity.logical_processors;
592 try std.testing.expectEqual(independent_bytes, capacity.storage_bytes);
593 }
594
595 test "Highway topology rejects capacity violations before allocation" {
596 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{});
597 try std.testing.expectError(
598 error.EmptyTopology,
599 Topology.initFromRecords(failing.allocator(), &.{}),
600 );
601 var oversized: [max_logical_processors + 1]ProcessorRecord = undefined;
602 for (&oversized) |*record| record.* = .{
603 .package_id = 0,
604 .cluster_id = 0,
605 .core_id = 0,
606 };
607 try std.testing.expectError(
608 error.TooManyLogicalProcessors,
609 Topology.initFromRecords(failing.allocator(), &oversized),
610 );
611 var packages: [max_packages + 1]ProcessorRecord = undefined;
612 for (&packages, 0..) |*record, index| record.* = .{
613 .package_id = index,
614 .cluster_id = 0,
615 .core_id = 0,
616 };
617 try std.testing.expectError(
618 error.TooManyPackages,
619 Topology.initFromRecords(failing.allocator(), &packages),
620 );
621 var siblings: [max_smt + 1]ProcessorRecord = undefined;
622 for (&siblings) |*record| record.* = .{
623 .package_id = 0,
624 .cluster_id = 0,
625 .core_id = 0,
626 };
627 try std.testing.expectError(
628 error.TooManySiblings,
629 Topology.initFromRecords(failing.allocator(), &siblings),
630 );
631 try std.testing.expectEqual(@as(usize, 0), failing.alloc_index);
632 }
633
634 test "Highway topology construction is transactional under allocation failure" {
635 comptime {
636 alloc_phase.capacity.record(alloc_phase.capacity.witness(Topology, "simd_topology_oom"));
637 }
638
639 try std.testing.checkAllAllocationFailures(
640 std.testing.allocator,
641 checkInitFailures,
642 .{},
643 );
644 }
645
646 test "Highway cache sets derive from per-core geometry" {
647 var cache = Cache{
648 .size_kib = 1024,
649 .bytes_per_line = 64,
650 .associativity = 8,
651 .cores_sharing = 1,
652 };
653 try std.testing.expect(computeCacheSets(&cache));
654 try std.testing.expectEqual(@as(u32, 2048), cache.sets);
655 cache.sets -= 1;
656 try std.testing.expect(!computeCacheSets(&cache));
657 cache.sets += 2;
658 try std.testing.expect(computeCacheSets(&cache));
659 cache.sets += 1;
660 try std.testing.expect(!computeCacheSets(&cache));
661 cache = .{};
662 try std.testing.expect(computeCacheSets(&cache));
663 }
664
665 comptime {
666 alloc_phase.capacity.requireAllocatorExactOwnerShape(Topology);
667 }
668
669 comptime {
670 std.debug.assert(@sizeOf(LP) == 8);
671 std.debug.assert(@sizeOf(Cache) == 16);
672 std.debug.assert(@sizeOf(LogicalProcessorSet) == 136);
673 }