1use rhdl::prelude::*;
36
37use crate::register::inspect_register;
38
39pub const MAX_HOSTS: usize = 15;
41
42#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
44pub struct ReaderConfig {
45 pub init: bool,
47 pub session: b64,
49 pub hosts: b32,
51 pub cooldown: b32,
54}
55
56#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
58pub struct HostRead {
59 pub valid: bool,
61 pub session: b64,
63 pub register: b32,
65 pub attempt: b64,
67}
68
69#[derive(Clone, Copy, Debug, PartialEq, Digital)]
71pub struct HostAnswer<const S: usize> {
72 pub valid: bool,
74 pub host: b5,
76 pub session: b64,
78 pub register: b32,
80 pub attempt: b64,
82 pub a: [b32; S],
84 pub b: [b32; S],
86}
87
88#[derive(Clone, Copy, Debug, PartialEq, Digital)]
90pub struct ReaderIn<const S: usize> {
91 pub cfg: ReaderConfig,
93 pub req: bool,
95 pub register: b32,
97 pub take: [bool; MAX_HOSTS],
99 pub answer: HostAnswer<S>,
101}
102
103#[derive(Clone, Copy, Debug, PartialEq, Digital)]
106pub struct ReaderOut<const P: usize> {
107 pub req_ready: bool,
109 pub out: [HostRead; MAX_HOSTS],
111 pub done: bool,
113 pub found: bool,
115 pub logical: b32,
117 pub payload: [b32; P],
119 pub retries: b32,
121 pub fault: bool,
123}
124
125impl<const S: usize> Default for HostAnswer<S> {
126 fn default() -> Self {
127 Self {
128 valid: false,
129 host: b5(0),
130 session: b64(0),
131 register: b32(0),
132 attempt: b64(0),
133 a: [b32(0); S],
134 b: [b32(0); S],
135 }
136 }
137}
138
139impl<const S: usize> Default for ReaderIn<S> {
140 fn default() -> Self {
141 Self {
142 cfg: ReaderConfig::default(),
143 req: false,
144 register: b32(0),
145 take: [false; MAX_HOSTS],
146 answer: HostAnswer::default(),
147 }
148 }
149}
150
151impl<const P: usize> Default for ReaderOut<P> {
152 fn default() -> Self {
153 Self {
154 req_ready: false,
155 out: [HostRead::default(); MAX_HOSTS],
156 done: false,
157 found: false,
158 logical: b32(0),
159 payload: [b32(0); P],
160 retries: b32(0),
161 fault: false,
162 }
163 }
164}
165
166#[derive(Clone, Copy, Debug, PartialEq, Digital)]
168pub struct ReaderState<const P: usize> {
169 pub cfg: ReaderConfig,
171 pub ready: bool,
173 pub busy: bool,
175 pub register: b32,
177 pub attempt: b64,
179 pub age: b32,
181 pub expired: bool,
183 pub chan: [HostRead; MAX_HOSTS],
185 pub want: [bool; MAX_HOSTS],
187 pub got: [bool; MAX_HOSTS],
189 pub count: b5,
191 pub found: bool,
193 pub logical: b32,
195 pub payload: [b32; P],
197 pub retries: b32,
199 pub fault: bool,
201}
202
203impl<const P: usize> ReaderState<P> {
204 pub fn idle() -> Self {
206 Self {
207 cfg: ReaderConfig::default(),
208 ready: false,
209 busy: false,
210 register: b32(0),
211 attempt: b64(0),
212 age: b32(0),
213 expired: false,
214 chan: [HostRead::default(); MAX_HOSTS],
215 want: [false; MAX_HOSTS],
216 got: [false; MAX_HOSTS],
217 count: b5(0),
218 found: false,
219 logical: b32(0),
220 payload: [b32(0); P],
221 retries: b32(0),
222 fault: false,
223 }
224 }
225}
226
227#[kernel]
230pub fn reader_step<const P: usize, const S: usize>(
231 i: ReaderIn<S>,
232 s: ReaderState<P>,
233) -> (ReaderOut<P>, ReaderState<P>) {
234 let (o, n, _observation) = reader_step_core::<P, S>(i, s);
235 (o, n)
236}
237
238#[derive(Clone, Copy, Debug, PartialEq, Digital)]
241struct SampleObservation {
242 valid: bool,
243 host: b5,
244 same_host_tie: bool,
245 conflicting_payloads: bool,
246}
247
248#[kernel]
249fn reader_step_core<const P: usize, const S: usize>(
250 i: ReaderIn<S>,
251 s: ReaderState<P>,
252) -> (ReaderOut<P>, ReaderState<P>, SampleObservation) {
253 let mut observed = SampleObservation {
254 valid: false,
255 host: b5(0),
256 same_host_tie: false,
257 conflicting_payloads: false,
258 };
259 let mut n = s;
260 let mut o = ReaderOut::<P> {
261 req_ready: false,
262 out: s.chan,
263 done: false,
264 found: false,
265 logical: b32(0),
266 payload: [b32(0); P],
267 retries: s.retries,
268 fault: s.fault,
269 };
270 let hosts: b5 = s.cfg.hosts.resize();
271 let majority = (hosts >> b5(1)) + b5(1);
272
273 if i.cfg.init && !s.ready {
275 let ok = i.cfg.session != b64(0)
276 && i.cfg.hosts >= b32(1)
277 && i.cfg.hosts <= b32(15)
278 && (i.cfg.hosts & b32(1)) == b32(1)
279 && i.cfg.cooldown != b32(0);
280 if ok {
281 n.cfg = i.cfg;
282 n.ready = true;
283 } else {
284 n.fault = true;
285 }
286 }
287
288 for h in 0..MAX_HOSTS {
290 if s.chan[h].valid && i.take[h] {
291 n.chan[h].valid = false;
292 }
293 }
294
295 let exhausted = s.attempt == b64(0xffff_ffff_ffff_ffff);
297 let take = s.ready && !s.fault && !s.busy && i.req && !exhausted;
298 o.req_ready = take;
299 let mut restart = false;
301 if take {
302 n.busy = true;
303 n.register = i.register;
304 restart = true;
305 }
306
307 if s.busy {
309 if s.age != b32(0xffff_ffff) {
310 n.age = s.age + b32(1);
311 }
312 if s.age >= s.cfg.cooldown {
313 n.expired = true;
314 }
315 }
316
317 let a = i.answer;
319 if s.busy
320 && a.valid
321 && a.session == s.cfg.session
322 && a.register == s.register
323 && a.attempt == s.attempt
324 && a.host < hosts
325 {
326 let mut fresh = false;
327 for h in 0..MAX_HOSTS {
328 if a.host == b5(h as u128) && !s.got[h] {
329 n.got[h] = true;
330 fresh = true;
331 }
332 }
333 if fresh {
334 n.count = s.count + b5(1);
335 let inspected = inspect_register::<P, S>(a.a, a.b);
336 let v = inspected.payload;
337 if inspected.valid && (!s.found || v[0] > s.logical) {
338 n.found = true;
339 n.logical = v[0];
340 n.payload = v;
341 }
342 if s.count < majority {
345 observed = SampleObservation {
346 valid: true,
347 host: a.host,
348 same_host_tie: inspected.same_host_tie,
349 conflicting_payloads: inspected.conflicting_payloads,
350 };
351 }
352 }
353 }
354
355 if s.busy && s.count >= majority {
357 let young = !s.expired && s.age < s.cfg.cooldown;
358 if young {
359 o.done = true;
360 o.found = s.found;
361 o.logical = s.logical;
362 o.payload = s.payload;
363 n.busy = false;
364 } else if exhausted {
365 n.fault = true;
366 n.busy = false;
367 } else {
368 n.retries = s.retries + b32(1);
369 restart = true;
370 }
371 }
372 if restart {
373 n.attempt = s.attempt + b64(1);
374 n.age = b32(0);
375 n.expired = false;
376 n.count = b5(0);
377 n.found = false;
378 n.logical = b32(0);
379 for h in 0..MAX_HOSTS {
380 n.got[h] = false;
381 n.want[h] = b5(h as u128) < hosts;
382 }
383 }
384
385 if s.busy && !restart {
388 for h in 0..MAX_HOSTS {
389 if s.want[h] && !s.chan[h].valid {
390 n.chan[h] = HostRead {
391 valid: true,
392 session: s.cfg.session,
393 register: s.register,
394 attempt: s.attempt,
395 };
396 n.want[h] = false;
397 }
398 }
399 }
400 (o, n, observed)
401}
402
403#[derive(Clone, Copy, Debug, PartialEq, Digital, Default)]
409pub struct ReaderTieReport {
410 pub valid: bool,
411 pub session: b64,
412 pub register: b32,
413 pub attempt: b64,
414 pub same_host_ties: [bool; MAX_HOSTS],
415 pub conflicting_payloads: [bool; MAX_HOSTS],
416}
417
418#[derive(Clone, Copy, Debug, PartialEq, Digital)]
420pub struct ObservedReaderOut<const P: usize> {
421 pub reader: ReaderOut<P>,
422 pub report: ReaderTieReport,
423}
424
425#[derive(Clone, Copy, Debug, PartialEq, Digital)]
427pub struct ObservedReaderState<const P: usize> {
428 pub reader: ReaderState<P>,
429 pub same_host_ties: [bool; MAX_HOSTS],
430 pub conflicting_payloads: [bool; MAX_HOSTS],
431}
432
433impl<const P: usize> ObservedReaderState<P> {
434 pub fn idle() -> Self {
435 Self {
436 reader: ReaderState::idle(),
437 same_host_ties: [false; MAX_HOSTS],
438 conflicting_payloads: [false; MAX_HOSTS],
439 }
440 }
441}
442
443#[kernel]
446pub fn observed_reader_step<const P: usize, const S: usize>(
447 i: ReaderIn<S>,
448 s: ObservedReaderState<P>,
449) -> (ObservedReaderOut<P>, ObservedReaderState<P>) {
450 let (reader, next_reader, observed) = reader_step_core::<P, S>(i, s.reader);
451 let mut n = ObservedReaderState::<P> {
452 reader: next_reader,
453 same_host_ties: s.same_host_ties,
454 conflicting_payloads: s.conflicting_payloads,
455 };
456 let mut report = ReaderTieReport {
457 valid: false,
458 session: b64(0),
459 register: b32(0),
460 attempt: b64(0),
461 same_host_ties: [false; MAX_HOSTS],
462 conflicting_payloads: [false; MAX_HOSTS],
463 };
464 for h in 0..MAX_HOSTS {
465 if observed.valid && observed.host == b5(h as u128) {
466 n.same_host_ties[h] = observed.same_host_tie;
467 n.conflicting_payloads[h] = observed.conflicting_payloads;
468 }
469 }
470 if reader.done {
471 report = ReaderTieReport {
474 valid: true,
475 session: s.reader.cfg.session,
476 register: s.reader.register,
477 attempt: s.reader.attempt,
478 same_host_ties: s.same_host_ties,
479 conflicting_payloads: s.conflicting_payloads,
480 };
481 }
482 if reader.done || next_reader.attempt != s.reader.attempt || next_reader.fault {
483 n.same_host_ties = [false; MAX_HOSTS];
484 n.conflicting_payloads = [false; MAX_HOSTS];
485 }
486 (ObservedReaderOut::<P> { reader, report }, n)
487}
488
489#[cfg(test)]
490mod tests {
491 use super::*;
492 use crate::register::{pack_subslot, subslot_of, subslot_words};
493
494 const P: usize = 4;
496 const S: usize = 7;
497 const _: () = assert!(subslot_words(P) == S);
498
499 fn host_reg(physical: u32, logical: u32) -> [[b32; S]; 2] {
502 let mut r = [[b32(0); S]; 2];
503 for g in 1..=physical {
504 let l = if g == physical { logical } else { g };
505 let payload = [b32(u128::from(l)), b32(u128::from(l * 10)), b32(0), b32(0)];
506 r[subslot_of(b32(u128::from(g))).raw() as usize] =
507 pack_subslot::<P, S>(b32(u128::from(g)), payload);
508 }
509 r
510 }
511
512 fn read_with(
514 mem: &[[[b32; S]; 2]],
515 delay: &[Option<u64>],
516 cooldown: u32,
517 cycles: u64,
518 ) -> Option<(ReaderOut<P>, u32)> {
519 read_recorded(mem, delay, cooldown, cycles, &mut Vec::new())
520 }
521
522 type Case = (ReaderIn<S>, ReaderState<P>);
523
524 fn read_recorded(
525 mem: &[[[b32; S]; 2]],
526 delay: &[Option<u64>],
527 cooldown: u32,
528 cycles: u64,
529 cases: &mut Vec<Case>,
530 ) -> Option<(ReaderOut<P>, u32)> {
531 let n = mem.len();
532 let mut s = ReaderState::<P>::idle();
533 let mut q: Vec<(u64, HostAnswer<S>)> = Vec::new();
534 let mut last = [HostRead::default(); MAX_HOSTS];
535 let mut last_take = [false; MAX_HOSTS];
536 for now in 0..cycles {
537 q.sort_by_key(|x| x.0);
538 let ans = if q.first().is_some_and(|x| x.0 <= now) {
539 q.remove(0).1
540 } else {
541 HostAnswer::default()
542 };
543 let mut take = [false; MAX_HOSTS];
544 for h in 0..n {
545 take[h] = s.chan[h].valid && delay[h].is_some();
546 }
547 let i = ReaderIn::<S> {
548 cfg: ReaderConfig {
549 init: now == 0,
550 session: b64(5),
551 hosts: b32(n as u128),
552 cooldown: b32(u128::from(cooldown)),
553 },
554 req: now == 2,
555 register: b32(0),
556 take,
557 answer: ans,
558 };
559 cases.push((i, s));
560 let (o, ns) = reader_step::<P, S>(i, s);
561 for h in 0..n {
562 if last[h].valid && !last_take[h] {
563 assert_eq!(
564 o.out[h], last[h],
565 "host {h}: an offer changed before it was taken"
566 );
567 }
568 if o.out[h].valid && take[h] {
569 let r = o.out[h];
570 q.push((
571 now + delay[h].unwrap(),
572 HostAnswer {
573 valid: true,
574 host: b5(h as u128),
575 session: r.session,
576 register: r.register,
577 attempt: r.attempt,
578 a: mem[h][0],
579 b: mem[h][1],
580 },
581 ));
582 }
583 }
584 last = o.out;
585 last_take = take;
586 s = ns;
587 if o.done {
588 return Some((o, s.retries.raw() as u32));
589 }
590 }
591 None
592 }
593
594 #[test]
597 fn the_highest_logical_incarnation_wins() {
598 let mem = [host_reg(2, 9), host_reg(5, 5), host_reg(5, 5)];
601 let (o, _) = read_with(&mem, &[Some(5), Some(6), Some(30)], 100, 500).unwrap();
602 assert!(o.found);
603 assert_eq!(o.logical.raw(), 9);
604 assert_eq!(o.payload[1].raw(), 90);
605 }
606
607 #[test]
609 fn a_stalled_host_does_not_block() {
610 let mem = [host_reg(4, 4), host_reg(4, 4), host_reg(4, 4)];
611 let (o, _) = read_with(&mem, &[None, Some(9), Some(3)], 100, 500).unwrap();
612 assert_eq!((o.found, o.logical.raw()), (true, 4));
613 }
614
615 #[test]
617 fn an_empty_register_reads_as_not_found() {
618 let mem = [host_reg(0, 0), host_reg(0, 0), host_reg(0, 0)];
619 let (o, _) = read_with(&mem, &[Some(2), Some(2), Some(2)], 100, 500).unwrap();
620 assert!(!o.found);
621 }
622
623 #[test]
626 fn a_slow_sample_is_never_accepted() {
627 let mem = [host_reg(1, 1), host_reg(1, 1), host_reg(1, 1)];
628 assert!(read_with(&mem, &[Some(3), Some(4), Some(5)], 100, 500).is_some());
629 assert!(read_with(&mem, &[Some(60), Some(60), Some(60)], 50, 3000).is_none());
630 }
631
632 #[test]
635 fn stale_answers_never_count() {
636 let mut s = ReaderState::<P>::idle();
637 let cfg = ReaderConfig {
638 init: true,
639 session: b64(5),
640 hosts: b32(3),
641 cooldown: b32(100),
642 };
643 let (_, s1) = reader_step::<P, S>(
644 ReaderIn {
645 cfg,
646 ..Default::default()
647 },
648 s,
649 );
650 s = s1;
651 let (_, s2) = reader_step::<P, S>(
652 ReaderIn {
653 req: true,
654 ..Default::default()
655 },
656 s,
657 );
658 s = s2;
659 let mem = host_reg(1, 1);
660 let stale = HostAnswer {
661 valid: true,
662 host: b5(0),
663 session: b64(5),
664 register: b32(0),
665 attempt: s.attempt + b64(7),
666 a: mem[0],
667 b: mem[1],
668 };
669 let (_, s3) = reader_step::<P, S>(
670 ReaderIn {
671 answer: stale,
672 ..Default::default()
673 },
674 s,
675 );
676 assert_eq!(s3.count.raw(), 0);
677 }
678
679 #[test]
681 fn exhausted_attempt_ids_fail_closed() {
682 let mut s = ReaderState::<P>::idle();
683 let cfg = ReaderConfig {
684 init: true,
685 session: b64(5),
686 hosts: b32(3),
687 cooldown: b32(100),
688 };
689 s = reader_step::<P, S>(
690 ReaderIn {
691 cfg,
692 ..Default::default()
693 },
694 s,
695 )
696 .1;
697 s.attempt = b64(0xffff_ffff_ffff_ffff);
698 let (o, _) = reader_step::<P, S>(
699 ReaderIn {
700 req: true,
701 ..Default::default()
702 },
703 s,
704 );
705 assert!(!o.req_ready);
706 }
707
708 #[test]
712 #[ignore = "Icarus (ivl) crashes compiling this testbench (draw_vpi.c buffer assertion, 2026-10-21); needs Verilator or a smaller trace"]
713 fn reader_matches_vm_and_generated_verilog() -> anyhow::Result<()> {
714 use rhdl::core::sim::testbench::kernel::test_kernel_vm_and_verilog;
715 let mut cases = Vec::new();
716 let mem = [host_reg(2, 9), host_reg(5, 5), host_reg(5, 5)];
717 read_recorded(&mem, &[None, Some(6), Some(9)], 100, 200, &mut cases);
718 read_recorded(&mem, &[Some(30), Some(30), Some(30)], 20, 150, &mut cases);
719 test_kernel_vm_and_verilog::<reader_step<P, S>, _, _, _>(
720 reader_step::<P, S>,
721 cases.into_iter(),
722 )?;
723 Ok(())
724 }
725}