1use std::sync::atomic::{AtomicU32, AtomicU64, Ordering};
4
5use crate::{Error, Inbox, Result};
6
7const STATE_BITS: u32 = 2;
11const OWNER_BITS: u32 = 16;
12const GENERATION_SHIFT: u32 = STATE_BITS + OWNER_BITS;
13const GENERATION_MAX: u64 = u64::MAX >> GENERATION_SHIFT;
14const FREE: u64 = 0;
15const RESERVED: u64 = 1;
16const ACTIVE: u64 = 2;
17
18#[derive(Clone, Copy, Debug, Eq, PartialEq)]
20pub struct WorkTicket {
21 pub lane: u16,
22 pub epoch: u64,
23 pub slot: u32,
24 pub claim: u64,
25}
26
27impl WorkTicket {
28 pub fn origin(self) -> usize {
29 ((self.claim >> STATE_BITS) & u64::from(u16::MAX)) as usize
30 }
31}
32
33#[repr(C, align(64))]
35pub(crate) struct Capacity {
36 policy: AtomicU64,
39 changes: AtomicU64,
40 cursor: AtomicU32,
41 occupied: AtomicU32,
46 execution: AtomicU32,
50 inbox_space_waiting: AtomicU32,
52 inbox_space_epoch: AtomicU64,
53 inline_exchange_epoch: AtomicU64,
54 _padding: [u8; 16],
55}
56
57const _: () = assert!(size_of::<Capacity>() == 64);
58
59pub(crate) const fn bytes(
60 lanes: usize,
61 slots: usize,
62) -> usize {
63 lanes * (size_of::<Capacity>() + slots * size_of::<AtomicU64>())
64 + lanes * lanes.div_ceil(64) * size_of::<AtomicU64>()
65}
66
67impl Inbox {
68 fn capacity_base(&self) -> *mut u8 {
69 unsafe {
70 self.base.add(
71 self.geometry.segment_bytes(self.lanes)
72 - bytes(self.lanes, self.geometry.capacity),
73 )
74 }
75 }
76
77 fn capacity_row(
78 &self,
79 lane: usize,
80 ) -> &Capacity {
81 unsafe { &*self.capacity_base().cast::<Capacity>().add(lane) }
82 }
83
84 fn work_slot(
85 &self,
86 lane: usize,
87 slot: usize,
88 ) -> &AtomicU64 {
89 unsafe {
90 &*self
91 .capacity_base()
92 .add(self.lanes * size_of::<Capacity>())
93 .cast::<AtomicU64>()
94 .add(lane * self.geometry.capacity + slot)
95 }
96 }
97
98 fn capacity_interest(
99 &self,
100 lane: usize,
101 word: usize,
102 ) -> &AtomicU64 {
103 unsafe {
104 &*self
105 .capacity_base()
106 .add(
107 self.lanes
108 * (size_of::<Capacity>()
109 + self.geometry.capacity * size_of::<AtomicU64>()),
110 )
111 .cast::<AtomicU64>()
112 .add(lane * self.lanes.div_ceil(64) + word)
113 }
114 }
115
116 pub fn work_capacity(
118 &self,
119 lane: usize,
120 ) -> Result<Option<usize>> {
121 self.check_lane(lane)?;
122 let limit =
123 self.capacity_row(lane).policy.load(Ordering::SeqCst) as u32;
124 Ok((limit != 0).then_some(limit as usize))
125 }
126
127 pub(crate) fn configure_capacity(
128 &self,
129 lane: usize,
130 limit: Option<usize>,
131 ) -> Result<()> {
132 self.validate_work_capacity(limit)?;
133 let limit = limit.unwrap_or(0) as u64;
134 let row = self.capacity_row(lane);
135 row.occupied.store(0, Ordering::SeqCst);
138 row.execution.store(0, Ordering::SeqCst);
139 row.policy.store(limit | (limit << 32), Ordering::SeqCst);
140 Ok(())
141 }
142
143 pub fn set_work_execution(
148 &self,
149 lane: usize,
150 execution: usize,
151 ) -> Result<()> {
152 self.check_lane(lane)?;
153 let window = self.work_capacity(lane)?.ok_or(Error::Malformed(
154 "an unbounded receiver has no window to run part of",
155 ))?;
156 if execution == 0 || execution > window {
157 return Err(Error::Malformed(
158 "work execution must be positive and within the window",
159 ));
160 }
161 let execution = if execution == window { 0 } else { execution };
162 self.capacity_row(lane)
163 .execution
164 .store(execution as u32, Ordering::SeqCst);
165 Ok(())
166 }
167
168 pub fn work_execution(
171 &self,
172 lane: usize,
173 ) -> Result<Option<usize>> {
174 let Some(window) = self.work_capacity(lane)? else {
175 return Ok(None);
176 };
177 let execution =
178 self.capacity_row(lane).execution.load(Ordering::SeqCst) as usize;
179 Ok(Some(if execution == 0 { window } else { execution.min(window) }))
180 }
181
182 pub fn work_load(
185 &self,
186 lane: usize,
187 ) -> Result<usize> {
188 self.check_lane(lane)?;
189 Ok(self.capacity_row(lane).occupied.load(Ordering::SeqCst) as usize)
190 }
191
192 pub(crate) fn update_work_capacity(
196 &self,
197 lane: usize,
198 limit: usize,
199 ) -> Result<()> {
200 self.check_lane(lane)?;
201 self.validate_work_capacity(Some(limit))?;
202 if self.consumers(lane)? == 0 {
203 return Err(Error::NoConsumer);
204 }
205 let row = self.capacity_row(lane);
206 let mut before = row.policy.load(Ordering::SeqCst);
207 loop {
208 let previous = before as u32 as usize;
209 if previous == 0 {
210 return Err(Error::Malformed(
211 "unbounded Link admission requires rejoin before setting a bound",
212 ));
213 }
214 if previous == limit {
215 return Ok(());
216 }
217 let window = ((before >> 32) as usize).max(limit);
218 let after = limit as u64 | ((window as u64) << 32);
219 match row.policy.compare_exchange(
220 before,
221 after,
222 Ordering::SeqCst,
223 Ordering::SeqCst,
224 ) {
225 Ok(_) => break,
226 Err(current) => before = current,
227 }
228 }
229 self.capacity_changed(lane);
230 Ok(())
231 }
232
233 fn admission_policy(
234 &self,
235 lane: usize,
236 ) -> Result<u64> {
237 let row = self.capacity_row(lane);
238 let mut policy = row.policy.load(Ordering::SeqCst);
239 loop {
240 let limit = policy as u32 as usize;
241 let window = (policy >> 32) as usize;
242 if limit == 0 || window == limit {
243 return Ok(policy);
244 }
245 if (limit..window).any(|index| {
248 self.work_slot(lane, index).load(Ordering::SeqCst) & 3 != FREE
249 }) {
250 return Err(Error::CapacityFull);
251 }
252 let trimmed = limit as u64 | ((limit as u64) << 32);
253 match row.policy.compare_exchange(
254 policy,
255 trimmed,
256 Ordering::SeqCst,
257 Ordering::SeqCst,
258 ) {
259 Ok(_) => return Ok(trimmed),
260 Err(current) => policy = current,
261 }
262 }
263 }
264
265 pub(crate) fn validate_work_capacity(
266 &self,
267 limit: Option<usize>,
268 ) -> Result<()> {
269 if limit.is_some_and(|n| n == 0 || n > self.geometry.capacity) {
270 return Err(Error::Malformed(
271 "work capacity must fit the inbox's admission slots",
272 ));
273 }
274 Ok(())
275 }
276
277 pub(crate) fn reserve_work(
280 &self,
281 lane: usize,
282 origin: usize,
283 ) -> Result<Option<WorkTicket>> {
284 self.check_lane(lane)?;
285 self.check_lane(origin)?;
286 if self.consumers(lane)? == 0 || self.consumers(origin)? == 0 {
287 return Err(Error::NoConsumer);
288 }
289 let epoch = self.lane_header(lane).epoch.load(Ordering::Acquire);
290 let origin_epoch =
291 self.lane_header(origin).epoch.load(Ordering::Acquire);
292 let policy = self.admission_policy(lane)?;
293 let limit = policy as u32 as usize;
294 if limit == 0 {
295 return Ok(None);
296 }
297 self.reserve_with_policy(lane, origin, epoch, origin_epoch, policy)
298 }
299
300 fn reserve_with_policy(
301 &self,
302 lane: usize,
303 origin: usize,
304 epoch: u64,
305 origin_epoch: u64,
306 policy: u64,
307 ) -> Result<Option<WorkTicket>> {
308 let limit = policy as u32 as usize;
309 let row = self.capacity_row(lane);
310 if row.occupied.load(Ordering::SeqCst) as usize >= limit {
313 return Err(Error::CapacityFull);
314 }
315 let start = row.cursor.fetch_add(1, Ordering::Relaxed) as usize % limit;
316 let mut exhausted = 0;
317 for offset in 0..limit {
318 let index = (start + offset) % limit;
319 let slot = self.work_slot(lane, index);
320 let before = slot.load(Ordering::SeqCst);
321 let generation = before >> GENERATION_SHIFT;
322 if generation == GENERATION_MAX {
323 exhausted += 1;
324 continue;
325 }
326 if before & 3 != FREE {
327 continue;
328 }
329 let claim = ((generation + 1) << GENERATION_SHIFT)
330 | ((origin as u64) << STATE_BITS)
331 | RESERVED;
332 if slot
333 .compare_exchange(
334 before,
335 claim,
336 Ordering::SeqCst,
337 Ordering::SeqCst,
338 )
339 .is_err()
340 {
341 continue;
342 }
343 row.occupied.fetch_add(1, Ordering::SeqCst);
344 let ticket = WorkTicket {
345 lane: lane as u16,
346 epoch,
347 slot: index as u32,
348 claim,
349 };
350 if row.policy.load(Ordering::SeqCst) != policy {
353 self.cancel_work(ticket);
354 return Err(Error::CapacityFull);
355 }
356 if self.lane_header(lane).epoch.load(Ordering::Acquire) != epoch
357 || self.lane_header(origin).epoch.load(Ordering::Acquire)
358 != origin_epoch
359 || self.consumers(lane)? == 0
360 || self.consumers(origin)? == 0
361 {
362 self.cancel_work(ticket);
363 return Err(Error::NoConsumer);
364 }
365 return Ok(Some(ticket));
366 }
367 if exhausted == limit {
368 return Err(Error::Malformed(
369 "work admission generations exhausted",
370 ));
371 }
372 Err(Error::CapacityFull)
373 }
374
375 fn ticket_slot(
376 &self,
377 ticket: WorkTicket,
378 ) -> Result<&AtomicU64> {
379 self.check_lane(usize::from(ticket.lane))?;
380 if ticket.slot as usize >= self.geometry.capacity
381 || ticket.claim & 3 != RESERVED
382 || ticket.claim >> GENERATION_SHIFT == 0
383 || ticket.origin() >= self.lanes
384 || self
385 .lane_header(usize::from(ticket.lane))
386 .epoch
387 .load(Ordering::Acquire)
388 != ticket.epoch
389 {
390 return Err(Error::StaleWork);
391 }
392 Ok(self.work_slot(usize::from(ticket.lane), ticket.slot as usize))
393 }
394
395 pub(crate) fn accept_work(
396 &self,
397 lane: usize,
398 ticket: WorkTicket,
399 ) -> Result<()> {
400 if usize::from(ticket.lane) != lane || self.consumers(lane)? == 0 {
401 return Err(Error::StaleWork);
402 }
403 self.ticket_slot(ticket)?
404 .compare_exchange(
405 ticket.claim,
406 ticket.claim ^ RESERVED ^ ACTIVE,
407 Ordering::AcqRel,
408 Ordering::Acquire,
409 )
410 .map_err(|_| Error::StaleWork)?;
411 Ok(())
412 }
413
414 pub fn check_work(
416 &self,
417 ticket: WorkTicket,
418 ) -> Result<()> {
419 if self.ticket_slot(ticket)?.load(Ordering::Acquire) != ticket.claim {
420 return Err(Error::StaleWork);
421 }
422 Ok(())
423 }
424
425 pub(crate) fn cancel_work(
426 &self,
427 ticket: WorkTicket,
428 ) {
429 self.release_work(ticket, RESERVED);
430 }
431
432 pub fn withdraw_work(
436 &self,
437 ticket: WorkTicket,
438 ) -> bool {
439 self.release_work(ticket, RESERVED)
440 }
441
442 pub(crate) fn complete_work(
443 &self,
444 ticket: WorkTicket,
445 ) {
446 self.release_work(ticket, ACTIVE);
447 }
448
449 fn release_work(
450 &self,
451 ticket: WorkTicket,
452 state: u64,
453 ) -> bool {
454 let Ok(slot) = self.ticket_slot(ticket) else { return false };
455 let expected = ticket.claim ^ RESERVED ^ state;
456 let free = ticket.claim & !((1 << GENERATION_SHIFT) - 1);
459 let lane = usize::from(ticket.lane);
460 if slot.load(Ordering::SeqCst) != expected {
461 return false;
462 }
463 let lowered = self.lower_occupied(lane);
464 if slot
465 .compare_exchange(
466 expected,
467 free,
468 Ordering::SeqCst,
469 Ordering::SeqCst,
470 )
471 .is_ok()
472 {
473 self.capacity_changed(lane);
474 true
475 } else {
476 if lowered {
477 self.capacity_row(lane).occupied.fetch_add(1, Ordering::SeqCst);
478 }
479 false
480 }
481 }
482
483 fn lower_occupied(
486 &self,
487 lane: usize,
488 ) -> bool {
489 self.capacity_row(lane)
490 .occupied
491 .try_update(Ordering::SeqCst, Ordering::SeqCst, |held| {
492 held.checked_sub(1)
493 })
494 .is_ok()
495 }
496
497 pub fn watch_capacity(
501 &self,
502 lane: usize,
503 origin: usize,
504 ) -> Result<()> {
505 self.check_lane(lane)?;
506 self.check_lane(origin)?;
507 self.capacity_interest(lane, origin / 64)
508 .fetch_or(1 << (origin % 64), Ordering::SeqCst);
509 Ok(())
510 }
511
512 pub fn advertise_inline_exchanges(
515 &self,
516 lane: usize,
517 epoch: u64,
518 ) -> Result<()> {
519 self.check_lane(lane)?;
520 if epoch == 0 || self.lane_epoch(lane)? != epoch {
521 return Err(Error::StaleWork);
522 }
523 self.capacity_row(lane)
524 .inline_exchange_epoch
525 .store(epoch, Ordering::Release);
526 Ok(())
527 }
528
529 pub fn inline_exchange_epoch(
531 &self,
532 lane: usize,
533 ) -> Option<u64> {
534 let epoch = self.lane_epoch(lane).ok()?;
535 (epoch != 0
536 && self
537 .capacity_row(lane)
538 .inline_exchange_epoch
539 .load(Ordering::Acquire)
540 == epoch)
541 .then_some(epoch)
542 }
543
544 pub(crate) fn advertise_inbox_space(
545 &self,
546 lane: usize,
547 epoch: u64,
548 ) {
549 self.capacity_row(lane)
550 .inbox_space_epoch
551 .store(epoch, Ordering::Release);
552 }
553
554 pub fn signals_inbox_space(
556 &self,
557 lane: usize,
558 epoch: u64,
559 ) -> bool {
560 epoch != 0
561 && self.check_lane(lane).is_ok()
562 && self.lane_epoch(lane).ok() == Some(epoch)
563 && self.capacity_row(lane).inbox_space_epoch.load(Ordering::Acquire)
564 == epoch
565 }
566
567 pub fn watch_inbox_space(
576 &self,
577 lane: usize,
578 epoch: u64,
579 origin: usize,
580 ) -> Result<bool> {
581 self.check_lane(lane)?;
582 self.check_lane(origin)?;
583 if !self.signals_inbox_space(lane, epoch) {
584 return Err(Error::NoConsumer);
585 }
586 self.watch_capacity(lane, origin)?;
587 self.capacity_row(lane).inbox_space_waiting.store(1, Ordering::SeqCst);
588 let admission = self.admits(lane)?;
589 if self.lane_epoch(lane)? != epoch
590 || admission == crate::Admission::NoConsumer
591 {
592 return Err(Error::NoConsumer);
593 }
594 Ok(admission == crate::Admission::Full)
595 }
596
597 pub(crate) fn inbox_space_changed(
599 &self,
600 lane: usize,
601 ) {
602 let waiting = &self.capacity_row(lane).inbox_space_waiting;
603 if waiting.load(Ordering::SeqCst) != 0
604 && waiting.swap(0, Ordering::SeqCst) != 0
605 {
606 self.capacity_changed(lane);
607 }
608 }
609
610 pub fn capacity_generation(
611 &self,
612 origin: usize,
613 ) -> Result<u64> {
614 self.check_lane(origin)?;
615 Ok(self.capacity_row(origin).changes.load(Ordering::SeqCst))
616 }
617
618 pub(crate) fn capacity_changed(
619 &self,
620 lane: usize,
621 ) {
622 for word in 0..self.lanes.div_ceil(64) {
623 let mut bits =
624 self.capacity_interest(lane, word).swap(0, Ordering::SeqCst);
625 while bits != 0 {
626 let bit = bits.trailing_zeros() as usize;
627 bits &= bits - 1;
628 let origin = word * 64 + bit;
629 if origin < self.lanes {
630 self.notify_capacity_observer(origin);
631 }
632 }
633 }
634 }
635
636 pub(crate) fn notify_capacity_observer(
637 &self,
638 lane: usize,
639 ) {
640 self.capacity_row(lane).changes.fetch_add(1, Ordering::SeqCst);
641 self.wake(lane, self.lane_header(lane));
642 }
643
644 pub(crate) fn recover_work(
647 &self,
648 gone: usize,
649 ) {
650 for lane in 0..self.lanes {
651 for index in 0..self.geometry.capacity {
652 let slot = self.work_slot(lane, index);
653 let before = slot.load(Ordering::Acquire);
654 let state = before & 3;
655 let origin =
656 ((before >> STATE_BITS) & u64::from(u16::MAX)) as usize;
657 if (lane == gone && state != FREE)
658 || (state == RESERVED && origin == gone)
659 {
660 let free = before & !((1 << GENERATION_SHIFT) - 1);
661 let lowered = self.lower_occupied(lane);
662 if slot
663 .compare_exchange(
664 before,
665 free,
666 Ordering::SeqCst,
667 Ordering::SeqCst,
668 )
669 .is_err()
670 && lowered
671 {
672 self.capacity_row(lane)
673 .occupied
674 .fetch_add(1, Ordering::SeqCst);
675 }
676 }
677 }
678 self.capacity_changed(lane);
682 }
683 }
684}
685
686#[cfg(unix)]
687mod owned {
688 use super::*;
689 use crate::LinkSegment;
690 use std::sync::Arc;
691
692 pub struct WorkReservation {
695 segment: Arc<LinkSegment>,
696 ticket: WorkTicket,
697 published: bool,
698 }
699
700 impl WorkReservation {
701 pub fn ticket(&self) -> WorkTicket {
702 self.ticket
703 }
704
705 pub fn publish(
706 mut self,
707 parts: &[&[u8]],
708 ) -> Result<u64> {
709 let position =
710 self.segment.inbox().write_work(self.ticket, parts)?;
711 self.published = true;
712 Ok(position)
713 }
714 }
715
716 impl Drop for WorkReservation {
717 fn drop(&mut self) {
718 if !self.published {
719 self.segment.inbox().cancel_work(self.ticket);
720 }
721 }
722 }
723
724 pub struct WorkExecution {
726 segment: Arc<LinkSegment>,
727 ticket: WorkTicket,
728 }
729
730 impl Drop for WorkExecution {
731 fn drop(&mut self) {
732 self.segment.inbox().complete_work(self.ticket);
733 }
734 }
735
736 impl LinkSegment {
737 pub fn update_work_capacity(
740 &self,
741 joined: &crate::Joined,
742 limit: usize,
743 ) -> Result<()> {
744 if !joined.belongs_to(self) {
745 return Err(Error::StaleWork);
746 }
747 self.inbox().update_work_capacity(joined.lane, limit)
748 }
749
750 pub fn reserve_work(
751 self: &Arc<Self>,
752 lane: usize,
753 origin: usize,
754 ) -> Result<Option<WorkReservation>> {
755 Ok(self.inbox().reserve_work(lane, origin)?.map(|ticket| {
756 WorkReservation {
757 segment: Arc::clone(self),
758 ticket,
759 published: false,
760 }
761 }))
762 }
763
764 pub fn accept_work(
765 self: &Arc<Self>,
766 lane: usize,
767 ticket: WorkTicket,
768 ) -> Result<WorkExecution> {
769 self.inbox().accept_work(lane, ticket)?;
770 Ok(WorkExecution { segment: Arc::clone(self), ticket })
771 }
772 }
773}
774
775#[cfg(unix)]
776pub use owned::{WorkExecution, WorkReservation};
777
778#[cfg(test)]
779#[path = "../tests/unit/admission.rs"]
780mod tests;