1use std::sync::atomic::{AtomicBool, AtomicU64, Ordering};
27use std::sync::{Arc, Mutex, OnceLock, PoisonError, Weak};
28
29use crate::handle::{CLASSES, Handle, LAZY_CLASS, MAX_CLASS_INDEX, mix2};
30use crate::node::{Kind, View, flags};
31use crate::strings::{StringOrder, Strings};
32
33pub mod compact;
34mod memory;
35pub mod snapshot;
36pub use memory::StoreMemory;
37
38const SHARDS: usize = 256;
39const CHUNKS: usize = 31;
42const CAPS: [usize; 2] = [4, 8];
44
45static EMPTY_DATA: [Handle; 0] = [];
46
47const POISON_VIEW: View<'static> = View {
48 kind: Kind::Set,
49 lo: 0,
50 hash: 0,
51 sum: 0,
52 flags: 0,
53 data: &EMPTY_DATA,
54};
55
56fn class_of(len: usize, fl: u8) -> u8 {
59 if fl & (crate::node::flags::LAZY | crate::node::flags::VIEW) != 0 {
60 return LAZY_CLASS;
61 }
62 match len {
63 0..=4 => 0,
64 5..=8 => 1,
65 _ => 2,
66 }
67}
68
69fn interning_hash(kind: Kind, fl: u8, lo: i64, hash: u64, data: &[Handle]) -> u64 {
75 if fl & flags::NESTED_VIEW == 0 {
76 return hash;
77 }
78 let header = u64::from(kind as u8) | (u64::from(fl & !flags::CONCRETE) << 8);
79 let hash = mix2(mix2(hash, header), lo.cast_unsigned());
80 data.iter().fold(hash, |key, h| mix2(key, h.bits()))
81}
82
83fn same_identity(n: &View<'_>, kind: Kind, fl: u8, lo: i64, hash: u64, data: &[Handle]) -> bool {
86 n.kind == kind
87 && (n.flags & !flags::CONCRETE) == (fl & !flags::CONCRETE)
88 && n.lo == lo
89 && n.hash == hash
90 && n.data == data
91}
92
93#[derive(Clone, Copy)]
95struct Head {
96 kind: Kind,
97 flags: u8,
98 lo: i64,
99 hash: u64,
100 sum: u64,
101}
102
103trait Slot: Sized {
105 fn make(h: Head, data: &[Handle]) -> Self;
106 fn view(&self) -> View<'_>;
107}
108
109#[derive(Debug)]
111struct Inline<const K: usize> {
112 kind: Kind,
113 flags: u8,
114 len: u8,
115 lo: i64,
116 hash: u64,
117 sum: u64,
118 data: [Handle; K],
119}
120
121impl<const K: usize> Slot for Inline<K> {
122 fn make(
123 Head {
124 kind,
125 flags,
126 lo,
127 hash,
128 sum,
129 }: Head,
130 data: &[Handle],
131 ) -> Self {
132 let mut a = [Handle::EMPTY; K];
133 let n = data.len().min(K);
134 a[..n].copy_from_slice(&data[..n]);
135 #[allow(clippy::cast_possible_truncation, reason = "K is at most 8")]
136 let len = n as u8;
137 Self {
138 kind,
139 flags,
140 len,
141 lo,
142 hash,
143 sum,
144 data: a,
145 }
146 }
147
148 #[inline]
149 fn view(&self) -> View<'_> {
150 View {
151 kind: self.kind,
152 lo: self.lo,
153 hash: self.hash,
154 sum: self.sum,
155 flags: self.flags,
156 data: self
157 .data
158 .get(..usize::from(self.len))
159 .unwrap_or(&EMPTY_DATA),
160 }
161 }
162}
163
164#[derive(Debug)]
166struct Boxed {
167 kind: Kind,
168 flags: u8,
169 lo: i64,
170 hash: u64,
171 sum: u64,
172 data: Box<[Handle]>,
173}
174
175impl Slot for Boxed {
176 fn make(
177 Head {
178 kind,
179 flags,
180 lo,
181 hash,
182 sum,
183 }: Head,
184 data: &[Handle],
185 ) -> Self {
186 Self {
187 kind,
188 flags,
189 lo,
190 hash,
191 sum,
192 data: data.into(),
193 }
194 }
195
196 #[inline]
197 fn view(&self) -> View<'_> {
198 View {
199 kind: self.kind,
200 lo: self.lo,
201 hash: self.hash,
202 sum: self.sum,
203 flags: self.flags,
204 data: &self.data,
205 }
206 }
207}
208
209const BASE: u32 = 4;
212
213struct Column<T> {
215 chunks: [OnceLock<Box<[OnceLock<T>]>>; CHUNKS],
216}
217
218impl<T: Slot> Column<T> {
219 fn new() -> Self {
220 Self {
221 chunks: std::array::from_fn(|_| OnceLock::new()),
222 }
223 }
224
225 #[inline]
226 fn get(&self, (c, off): (usize, usize)) -> Option<&T> {
227 self.chunks.get(c)?.get()?.get(off)?.get()
228 }
229
230 fn allocated_bytes(&self) -> usize {
231 self.chunks
232 .iter()
233 .filter_map(OnceLock::get)
234 .map(|chunk| std::mem::size_of_val(chunk.as_ref()))
235 .sum()
236 }
237
238 fn put(&self, index: u64, node: T) -> bool {
240 let (c, off) = locate(index, BASE);
241 let Some(chunk) = self.chunks.get(c) else {
242 return false;
243 };
244 let chunk = chunk.get_or_init(|| {
245 (0..(1usize << (BASE as usize + c)))
246 .map(|_| OnceLock::new())
247 .collect()
248 });
249 chunk.get(off).is_some_and(|s| s.set(node).is_ok())
250 }
251}
252
253fn unpack(e: u64) -> (u8, u64) {
255 #[allow(clippy::cast_possible_truncation, reason = "packed entry")]
256 let local = (e as u32).wrapping_sub(1);
257 #[allow(clippy::cast_possible_truncation, reason = "three class bits")]
258 let class = (local >> LOCAL_CLASS_SHIFT) as u8;
259 (class, u64::from(local & ((1 << LOCAL_CLASS_SHIFT) - 1)))
260}
261
262#[inline]
266fn probe(table: &[AtomicU64], h32: u32, same: impl Fn(u8, u64) -> bool) -> Option<(u8, u64)> {
267 if table.is_empty() {
268 return None;
269 }
270 let mask = table.len() - 1;
271 let mut p = h32 as usize & mask;
272 loop {
273 let e = table[p].load(Ordering::Acquire);
274 if e == 0 {
275 return None;
276 }
277 #[allow(clippy::cast_possible_truncation, reason = "packed entry")]
278 if (e >> 32) as u32 == h32 {
279 let (class, i) = unpack(e);
280 if same(class, i) {
281 return Some((class, i));
282 }
283 }
284 p = (p + 1) & mask;
285 }
286}
287
288#[inline]
291fn locate(index: u64, base: u32) -> (usize, usize) {
292 let i = index + (1 << base);
293 let b = i.ilog2();
294 #[allow(
295 clippy::cast_possible_truncation,
296 reason = "bounded by CHUNKS and the chunk size"
297 )]
298 ((b - base) as usize, (i - (1 << b)) as usize)
299}
300
301struct Columns {
303 c4: Column<Inline<{ CAPS[0] }>>,
304 c8: Column<Inline<{ CAPS[1] }>>,
305 boxed: Column<Boxed>,
306 lazy: Column<Boxed>,
307}
308
309impl Columns {
310 fn new() -> Self {
311 Self {
312 c4: Column::new(),
313 c8: Column::new(),
314 boxed: Column::new(),
315 lazy: Column::new(),
316 }
317 }
318
319 #[allow(
320 clippy::inline_always,
321 reason = "the hottest read of the core; measured: a call here costs ~5% instructions on MCLamportMutex"
322 )]
323 #[inline(always)]
324 fn view(&self, class: u8, index: u64) -> Option<View<'_>> {
325 let at = locate(index, BASE);
326 if class == 0 {
327 self.c4.get(at).map(Slot::view)
328 } else if class == 1 {
329 self.c8.get(at).map(Slot::view)
330 } else if class == 2 {
331 self.boxed.get(at).map(Slot::view)
332 } else {
333 self.lazy.get(at).map(Slot::view)
334 }
335 }
336
337 fn put(&self, class: u8, index: u64, h: Head, d: &[Handle]) -> bool {
338 match class {
339 0 => self.c4.put(index, Slot::make(h, d)),
340 1 => self.c8.put(index, Slot::make(h, d)),
341 2 => self.boxed.put(index, Slot::make(h, d)),
342 3 => self.lazy.put(index, Slot::make(h, d)),
343 _ => false,
344 }
345 }
346}
347
348struct Index {
355 lens: [u64; CLASSES],
356 table: Table,
357 used: usize,
358 hits: u64,
359 misses: u64,
360 handles: u64,
361 boxed_payload_bytes: usize,
362 retired: Vec<RetiredTable>,
363 rehash_scratch_bytes: usize,
364 largest_rehash_scratch_bytes: usize,
365}
366
367type Table = Arc<[AtomicU64]>;
370
371struct RetiredTable {
374 table: Weak<[AtomicU64]>,
375}
376
377fn empty_table(cap: usize) -> Table {
378 (0..cap).map(|_| AtomicU64::new(0)).collect()
379}
380
381const LOCAL_CLASS_SHIFT: u32 = 29;
382
383impl Default for Index {
384 fn default() -> Self {
385 Self {
386 lens: [0; CLASSES],
387 table: empty_table(0),
388 used: 0,
389 hits: 0,
390 misses: 0,
391 handles: 0,
392 boxed_payload_bytes: 0,
393 retired: Vec::new(),
394 rehash_scratch_bytes: 0,
395 largest_rehash_scratch_bytes: 0,
396 }
397 }
398}
399
400impl Index {
401 fn grow(&mut self) {
404 let cap = (self.table.len() * 2).max(64);
405 let t: Vec<u64> = {
406 let mut t = vec![0u64; cap];
407 let mask = cap - 1;
408 for e in self.table.iter() {
409 let e = e.load(Ordering::Relaxed);
410 if e != 0 {
411 let mut p = (e >> 32) as usize & mask;
412 while t[p] != 0 {
413 p = (p + 1) & mask;
414 }
415 t[p] = e;
416 }
417 }
418 t
419 };
420 let scratch = t.capacity() * std::mem::size_of::<u64>();
421 self.rehash_scratch_bytes += scratch;
422 self.largest_rehash_scratch_bytes = self.largest_rehash_scratch_bytes.max(scratch);
423 if !self.table.is_empty() && Arc::strong_count(&self.table) > 1 {
424 self.retired.push(RetiredTable {
425 table: Arc::downgrade(&self.table),
426 });
427 }
428 self.table = t.into_iter().map(AtomicU64::new).collect();
429 }
430
431 fn memory_usage(&mut self, out: &mut StoreMemory) {
432 out.boxed_payload_bytes += self.boxed_payload_bytes;
433 out.current_table_bytes += std::mem::size_of_val(self.table.as_ref());
434 self.retired.retain(|retired| {
437 if let Some(table) = retired.table.upgrade() {
438 out.retired_table_bytes += std::mem::size_of_val(table.as_ref());
439 out.retired_tables += 1;
440 true
441 } else {
442 false
443 }
444 });
445 out.retirement_tracking_bytes +=
446 self.retired.capacity() * std::mem::size_of::<RetiredTable>();
447 out.rehash_scratch_bytes += self.rehash_scratch_bytes;
448 out.largest_rehash_scratch_bytes = out
449 .largest_rehash_scratch_bytes
450 .max(self.largest_rehash_scratch_bytes);
451 }
452}
453
454#[repr(align(128))]
456struct Shard {
457 index: Mutex<Index>,
458}
459
460#[repr(align(128))]
463#[derive(Default)]
464struct Generation(AtomicU64);
465
466#[repr(align(128))]
468#[derive(Default)]
469struct Padded(AtomicU64);
470
471const HIT_STRIPES: usize = 16;
473
474pub struct InternCache {
479 tables: Vec<Option<(u64, Table)>>,
480 hits: u64,
481 stripe: usize,
482 pub(crate) added: u64,
487}
488
489impl Default for InternCache {
490 fn default() -> Self {
491 static NEXT: AtomicU64 = AtomicU64::new(0);
492 #[allow(
493 clippy::cast_possible_truncation,
494 reason = "reduced modulo the stripes"
495 )]
496 let stripe = (NEXT.fetch_add(1, Ordering::Relaxed) as usize) % HIT_STRIPES;
497 Self {
498 tables: vec![None; SHARDS],
499 hits: 0,
500 stripe,
501 added: 0,
502 }
503 }
504}
505
506impl std::fmt::Debug for InternCache {
507 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
508 f.debug_struct("InternCache")
509 .field("hits", &self.hits)
510 .finish_non_exhaustive()
511 }
512}
513
514#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
516pub struct StoreStats {
517 pub hits: u64,
519 pub misses: u64,
521 pub nodes: u64,
523 pub handles: u64,
525 pub classes: [u64; CLASSES],
528}
529
530pub struct Store {
532 cols: Box<[Columns]>,
533 shards: Box<[Shard]>,
534 generations: Box<[Generation]>,
535 hits: Box<[Padded]>,
536 strings: Strings,
537 hashcons: bool,
538 semantics: Semantics,
539 poisoned: AtomicBool,
540 printer: OnceLock<crate::print::Printer>,
542 lazy_sets: AtomicBool,
545 draws: OnceLock<std::sync::Arc<dyn crate::random::Draws>>,
547 registers: OnceLock<std::sync::Arc<dyn crate::random::Registers>>,
549}
550
551#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
554pub struct Semantics {
555 pub string_order: StringOrder,
557 pub int_mode: crate::int::IntMode,
559 pub tlc_comparisons: bool,
563 pub tlc_exploration: bool,
567}
568
569impl Semantics {
570 #[must_use]
573 pub const fn tlc() -> Self {
574 Self {
575 string_order: StringOrder::Token,
576 int_mode: crate::int::IntMode::Tlc,
577 tlc_comparisons: true,
578 tlc_exploration: true,
579 }
580 }
581}
582
583impl std::fmt::Debug for Store {
584 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
585 f.debug_struct("Store")
586 .field("stats", &self.stats())
587 .finish()
588 }
589}
590
591impl Default for Store {
592 fn default() -> Self {
593 Self::new(true)
594 }
595}
596
597impl Store {
598 #[must_use]
601 pub fn new(hashcons: bool) -> Self {
602 Self::with_string_order(hashcons, StringOrder::Text)
603 }
604
605 #[must_use]
609 pub fn with_string_order(hashcons: bool, order: StringOrder) -> Self {
610 Self::with_semantics(
611 hashcons,
612 Semantics {
613 string_order: order,
614 ..Semantics::default()
615 },
616 )
617 }
618
619 #[must_use]
622 pub fn with_semantics(hashcons: bool, semantics: Semantics) -> Self {
623 Self {
624 cols: (0..SHARDS).map(|_| Columns::new()).collect(),
625 shards: (0..SHARDS)
626 .map(|_| Shard {
627 index: Mutex::new(Index::default()),
628 })
629 .collect(),
630 generations: (0..SHARDS).map(|_| Generation::default()).collect(),
631 hits: (0..HIT_STRIPES).map(|_| Padded::default()).collect(),
632 strings: Strings::new(semantics.string_order),
633 hashcons,
634 semantics,
635 poisoned: AtomicBool::new(false),
636 printer: OnceLock::new(),
637 lazy_sets: AtomicBool::new(false),
638 draws: OnceLock::new(),
639 registers: OnceLock::new(),
640 }
641 }
642
643 pub fn set_printer(&self, printer: crate::print::Printer) {
647 let _ = self.printer.set(printer);
648 }
649
650 pub fn note_lazy_sets(&self) {
656 self.lazy_sets.store(true, Ordering::Relaxed);
657 }
658
659 #[must_use]
661 pub fn lazy_sets(&self) -> bool {
662 self.lazy_sets.load(Ordering::Relaxed)
663 }
664
665 pub fn set_draws(&self, draws: std::sync::Arc<dyn crate::random::Draws>) {
668 let _ = self.draws.set(draws);
669 }
670
671 #[must_use]
673 pub fn draws(&self) -> Option<&std::sync::Arc<dyn crate::random::Draws>> {
674 self.draws.get()
675 }
676
677 pub fn set_registers(&self, registers: std::sync::Arc<dyn crate::random::Registers>) {
679 let _ = self.registers.set(registers);
680 }
681
682 #[must_use]
684 pub fn registers(&self) -> Option<&std::sync::Arc<dyn crate::random::Registers>> {
685 self.registers.get()
686 }
687
688 #[must_use]
690 pub fn printer(&self) -> Option<&crate::print::Printer> {
691 self.printer.get()
692 }
693
694 #[must_use]
696 pub fn hashcons(&self) -> bool {
697 self.hashcons
698 }
699
700 #[must_use]
702 pub fn semantics(&self) -> Semantics {
703 self.semantics
704 }
705
706 #[must_use]
708 pub fn int_mode(&self) -> crate::int::IntMode {
709 self.semantics.int_mode
710 }
711
712 #[must_use]
714 pub fn strings(&self) -> &Strings {
715 &self.strings
716 }
717
718 #[must_use]
720 pub fn poisoned(&self) -> bool {
721 self.poisoned.load(Ordering::Relaxed)
722 }
723
724 #[inline]
727 pub(crate) fn view(&self, h: Handle) -> View<'_> {
728 let (s, class, i) = h.persistent_parts();
729 if let Some(v) = self.cols.get(usize::from(s)).and_then(|c| c.view(class, i)) {
730 v
731 } else {
732 self.poisoned.store(true, Ordering::Relaxed);
733 POISON_VIEW
734 }
735 }
736
737 pub(crate) fn retained_view(&self, handle: Handle) -> Option<View<'_>> {
740 if !handle.is_persistent() {
741 return None;
742 }
743 let (shard, class, index) = handle.persistent_parts();
744 if index > MAX_CLASS_INDEX {
745 return None;
746 }
747 self.cols
748 .get(usize::from(shard))
749 .and_then(|c| c.view(class, index))
750 }
751
752 #[allow(clippy::too_many_arguments, reason = "the node header, flat")]
756 pub(crate) fn intern(
757 &self,
758 cache: &mut InternCache,
759 kind: Kind,
760 flags: u8,
761 lo: i64,
762 hash: u64,
763 sum: u64,
764 data: &[Handle],
765 ) -> Handle {
766 let index_hash = interning_hash(kind, flags, lo, hash, data);
767 #[allow(clippy::cast_possible_truncation, reason = "the top eight bits")]
768 let s = (index_hash >> 56) as u8;
769 let (Some(shard), Some(cols), Some(generation)) = (
770 self.shards.get(usize::from(s)),
771 self.cols.get(usize::from(s)),
772 self.generations.get(usize::from(s)),
773 ) else {
774 self.poisoned.store(true, Ordering::Relaxed);
775 return Handle::EMPTY;
776 };
777 #[allow(clippy::cast_possible_truncation, reason = "the low 32 bits")]
778 let h32 = index_hash as u32;
779 let same = |class: u8, i: u64| {
780 cols.view(class, i)
781 .is_some_and(|n| same_identity(&n, kind, flags, lo, hash, data))
782 };
783 if self.hashcons {
784 let g = generation.0.load(Ordering::Acquire);
786 let entry = cache.tables.get_mut(usize::from(s));
787 if let Some(entry) = entry {
788 if entry.as_ref().is_none_or(|(cg, _)| *cg != g) {
789 let index = shard.index.lock().unwrap_or_else(PoisonError::into_inner);
790 *entry = Some((
791 generation.0.load(Ordering::Relaxed),
792 Arc::clone(&index.table),
793 ));
794 }
795 if let Some((_, table)) = entry.as_ref()
796 && let Some(found) = probe(table, h32, same)
797 {
798 cache.hits += 1;
799 let (class, i) = found;
800 return Handle::persistent(s, class, i);
801 }
802 }
803 }
804 let mut index = shard.index.lock().unwrap_or_else(PoisonError::into_inner);
805 let mut slot = None;
806 if self.hashcons {
807 if (index.used + 1) * 4 > index.table.len() * 3 {
808 index.grow();
809 generation.0.fetch_add(1, Ordering::Release);
810 }
811 let mask = index.table.len() - 1;
812 let mut p = h32 as usize & mask;
813 loop {
814 let e = index.table[p].load(Ordering::Relaxed);
815 if e == 0 {
816 slot = Some(p);
817 break;
818 }
819 #[allow(clippy::cast_possible_truncation, reason = "packed entry")]
820 if (e >> 32) as u32 == h32 {
821 let (class, i) = unpack(e);
822 if same(class, i) {
823 index.hits += 1;
824 return Handle::persistent(s, class, i);
825 }
826 }
827 p = (p + 1) & mask;
828 }
829 }
830 let class = class_of(data.len(), flags);
831 let i = index.lens[usize::from(class)];
832 if i >= MAX_CLASS_INDEX
833 || !cols.put(
834 class,
835 i,
836 Head {
837 kind,
838 flags,
839 lo,
840 hash,
841 sum,
842 },
843 data,
844 )
845 {
846 self.poisoned.store(true, Ordering::Relaxed);
847 return Handle::EMPTY;
848 }
849 index.lens[usize::from(class)] += 1;
850 index.misses += 1;
851 cache.added += (std::mem::size_of::<Head>() + std::mem::size_of_val(data)) as u64;
852 index.handles += data.len() as u64;
853 index.boxed_payload_bytes += usize::from(class >= 2) * std::mem::size_of_val(data);
854 if let Some(p) = slot {
855 #[allow(
856 clippy::cast_possible_truncation,
857 reason = "bounded by MAX_CLASS_INDEX"
858 )]
859 let local = (u32::from(class) << LOCAL_CLASS_SHIFT) | i as u32;
860 index.table[p].store(
862 (u64::from(h32) << 32) | u64::from(local + 1),
863 Ordering::Release,
864 );
865 index.used += 1;
866 }
867 Handle::persistent(s, class, i)
868 }
869
870 pub(crate) fn flush_hits(&self, cache: &mut InternCache) {
872 if cache.hits != 0 {
873 if let Some(c) = self.hits.get(cache.stripe) {
874 c.0.fetch_add(cache.hits, Ordering::Relaxed);
875 }
876 cache.hits = 0;
877 }
878 }
879
880 #[must_use]
882 pub fn stats(&self) -> StoreStats {
883 let mut st = StoreStats::default();
884 for c in &self.hits {
885 st.hits += c.0.load(Ordering::Relaxed);
886 }
887 for shard in &self.shards {
888 let index = shard.index.lock().unwrap_or_else(PoisonError::into_inner);
889 st.hits += index.hits;
890 st.misses += index.misses;
891 st.handles += index.handles;
892 for (c, &n) in index.lens.iter().enumerate() {
893 st.nodes += n;
894 st.classes[c] += n;
895 }
896 }
897 st
898 }
899
900 #[must_use]
916 pub fn memory_usage(&self) -> StoreMemory {
917 let mut out = StoreMemory {
918 fixed_bytes: std::mem::size_of::<Self>()
919 + std::mem::size_of_val(self.cols.as_ref())
920 + std::mem::size_of_val(self.shards.as_ref())
921 + std::mem::size_of_val(self.generations.as_ref())
922 + std::mem::size_of_val(self.hits.as_ref()),
923 strings: self.strings.memory_usage(),
924 has_printer: self.printer.get().is_some(),
925 has_draws: self.draws.get().is_some(),
926 has_registers: self.registers.get().is_some(),
927 ..StoreMemory::default()
928 };
929 for (cols, shard) in self.cols.iter().zip(&self.shards) {
930 let mut index = shard.index.lock().unwrap_or_else(PoisonError::into_inner);
931 out.slab_bytes += cols.c4.allocated_bytes()
932 + cols.c8.allocated_bytes()
933 + cols.boxed.allocated_bytes()
934 + cols.lazy.allocated_bytes();
935 index.memory_usage(&mut out);
936 }
937 out
938 }
939}
940
941#[cfg(test)]
942mod tests {
943 use super::*;
944
945 #[test]
946 fn locate_covers_indices_contiguously() {
947 for base in [4u32, 6, 8] {
948 let mut prev = (0usize, 0usize);
949 assert_eq!(locate(0, base), (0, 0));
950 for i in 1..5000u64 {
951 let (c, off) = locate(i, base);
952 if c == prev.0 {
953 assert_eq!(off, prev.1 + 1);
954 } else {
955 assert_eq!((c, off), (prev.0 + 1, 0));
956 assert_eq!(prev.1 + 1, 1 << (base as usize + prev.0));
957 }
958 prev = (c, off);
959 }
960 let (c, _) = locate(MAX_CLASS_INDEX - 1, base);
961 assert!(c < CHUNKS, "the last index fits for base {base}");
962 }
963 }
964
965 fn int(v: i64) -> Handle {
966 Handle::int(v).unwrap_or(Handle::EMPTY)
967 }
968
969 #[test]
970 fn memory_counts_allocated_slabs_and_actual_boxed_payload() {
971 let store = Store::new(false);
972 let mut cache = InternCache::default();
973 let empty = store.memory_usage();
974 assert!(empty.fixed_bytes > 0);
975 assert_eq!(empty.slab_bytes, 0);
976 for i in 0..17 {
977 let _ = store.intern(&mut cache, Kind::Set, 0, 0, 0, 0, &[int(i)]);
978 }
979 let inline = store.memory_usage();
980 assert_eq!(
982 inline.slab_bytes,
983 48 * std::mem::size_of::<OnceLock<Inline<4>>>()
984 );
985 assert_eq!(inline.boxed_payload_bytes, 0);
986 let five = [int(0); 5];
987 let nine = [int(0); 9];
988 let two = [int(0); 2];
989 let _ = store.intern(&mut cache, Kind::Set, 0, 0, 0, 0, &five);
990 let _ = store.intern(&mut cache, Kind::Set, 0, 0, 0, 0, &nine);
991 let _ = store.intern(
992 &mut cache,
993 Kind::Fcn,
994 crate::node::flags::RECORD,
995 0,
996 0,
997 0,
998 &two,
999 );
1000 let all = store.memory_usage();
1001 assert_eq!(all.fixed_bytes, empty.fixed_bytes);
1002 assert_eq!(
1003 all.slab_bytes,
1004 inline.slab_bytes
1005 + 16 * std::mem::size_of::<OnceLock<Inline<8>>>()
1006 + 32 * std::mem::size_of::<OnceLock<Boxed>>()
1007 );
1008 assert_eq!(all.boxed_payload_bytes, 11 * std::mem::size_of::<Handle>());
1009 assert_eq!(
1010 all.current_table_bytes, 0,
1011 "hashcons-off has no index tables"
1012 );
1013 assert_eq!(all.retired_tables, 0);
1014 assert_eq!(all.rehash_scratch_bytes, 0);
1015 assert!(all.known_retained_bytes() > inline.known_retained_bytes());
1016 }
1017
1018 #[test]
1019 fn memory_counts_shared_retired_tables_until_the_last_reader_drops() {
1020 let store = Store::default();
1021 let hash = 0xabcd_0000_0000_1234;
1022 let mut first = InternCache::default();
1023 let mut second = InternCache::default();
1024 let mut writer = InternCache::default();
1025 let initial = store.intern(&mut first, Kind::Set, 0, 0, hash, 0, &[int(0)]);
1026 assert_eq!(
1027 store.intern(&mut first, Kind::Set, 0, 0, hash, 0, &[int(0)]),
1028 initial
1029 );
1030 assert_eq!(
1031 store.intern(&mut second, Kind::Set, 0, 0, hash, 0, &[int(0)]),
1032 initial
1033 );
1034 for i in 1..49 {
1035 let _ = store.intern(&mut writer, Kind::Set, 0, 0, hash, 0, &[int(i)]);
1036 }
1037 let memory = store.memory_usage();
1038 assert_eq!(memory.current_table_bytes, 128 * std::mem::size_of::<u64>());
1039 assert_eq!(memory.retired_table_bytes, 64 * std::mem::size_of::<u64>());
1040 assert_eq!(
1041 memory.retired_tables, 1,
1042 "three readers share one allocation"
1043 );
1044 assert!(memory.retirement_tracking_bytes >= std::mem::size_of::<RetiredTable>());
1045 assert_eq!(
1046 memory.rehash_scratch_bytes,
1047 192 * std::mem::size_of::<u64>()
1048 );
1049 assert_eq!(
1050 memory.largest_rehash_scratch_bytes,
1051 memory.current_table_bytes
1052 );
1053 let stats = store.stats();
1055 assert_eq!(store.memory_usage(), memory);
1056 assert_eq!(store.stats(), stats);
1057 drop(writer);
1058 drop(first);
1059 assert_eq!(
1060 store.memory_usage().retired_table_bytes,
1061 memory.retired_table_bytes
1062 );
1063 drop(second);
1064 let released = store.memory_usage();
1065 assert_eq!(released.retired_table_bytes, 0);
1066 assert_eq!(released.retired_tables, 0);
1067 assert_eq!(released.current_table_bytes, memory.current_table_bytes);
1068 assert_eq!(
1069 released.retirement_tracking_bytes,
1070 memory.retirement_tracking_bytes
1071 );
1072 let shard = &store.shards[0xab];
1073 assert!(
1074 shard
1075 .index
1076 .lock()
1077 .unwrap_or_else(PoisonError::into_inner)
1078 .retired
1079 .is_empty(),
1080 "dead Weak records are removed, without hiding spare Vec capacity"
1081 );
1082 }
1083
1084 #[test]
1085 fn memory_does_not_charge_hashcons_hits_as_new_payload() {
1086 let store = Store::default();
1087 let mut cache = InternCache::default();
1088 let data = [int(1); 12];
1089 let original = store.intern(&mut cache, Kind::Set, 0, 0, 19, 0, &data);
1090 let before = store.memory_usage();
1091 for _ in 0..20 {
1092 assert_eq!(
1093 store.intern(&mut cache, Kind::Set, 0, 0, 19, 0, &data),
1094 original
1095 );
1096 }
1097 assert_eq!(store.memory_usage(), before);
1098 assert_eq!(before.boxed_payload_bytes, std::mem::size_of_val(&data));
1099 assert_eq!(store.stats().nodes, 1);
1100 }
1101
1102 #[test]
1103 fn every_size_class_round_trips_and_dedupes() {
1104 let store = Store::default();
1105 let mut c = InternCache::default();
1106 let mut got = Vec::new();
1107 for len in [0i64, 1, 4, 5, 8, 9, 16, 17, 32, 33, 100] {
1108 let data: Vec<Handle> = (0..len).map(int).collect();
1109 let hash = crate::handle::mix64(len.unsigned_abs() + 1);
1110 let h = store.intern(&mut c, Kind::Set, 0, 7, hash, 3, &data);
1111 let v = store.view(h);
1112 assert_eq!(v.data, data.as_slice(), "len {len}");
1113 assert_eq!((v.kind, v.lo, v.hash, v.sum), (Kind::Set, 7, hash, 3));
1114 assert_eq!(
1115 store.intern(&mut c, Kind::Set, 0, 7, hash, 3, &data),
1116 h,
1117 "len {len}"
1118 );
1119 got.push(h);
1120 }
1121 store.flush_hits(&mut c);
1122 let st = store.stats();
1123 assert_eq!(st.nodes, got.len() as u64);
1124 assert_eq!(st.hits, got.len() as u64);
1125 assert_eq!(st.classes, [3, 2, 6, 0]);
1126 assert!(!store.poisoned());
1127 }
1128
1129 #[test]
1130 fn colliding_hashes_are_told_apart_and_the_table_grows() {
1131 let store = Store::default();
1132 let mut c = InternCache::default();
1133 let hash = 0xabcd_0000_0000_1234;
1135 let hs: Vec<Handle> = (0..500)
1136 .map(|i| store.intern(&mut c, Kind::Set, 0, 0, hash, 0, &[int(i)]))
1137 .collect();
1138 for (i, &h) in (0..).zip(&hs) {
1139 assert_eq!(store.view(h).data, &[int(i)]);
1140 assert_eq!(store.intern(&mut c, Kind::Set, 0, 0, hash, 0, &[int(i)]), h);
1141 }
1142 for i in 0..5000u64 {
1144 let hash = (0x11u64 << 56) | crate::handle::mix64(i) >> 8;
1145 let a = store.intern(&mut c, Kind::Set, 0, 0, hash, 0, &[int(1)]);
1146 assert_eq!(store.intern(&mut c, Kind::Set, 0, 0, hash, 0, &[int(1)]), a);
1147 }
1148 assert_eq!(store.stats().nodes, 5500);
1149 assert!(!store.poisoned());
1150 }
1151
1152 #[test]
1153 fn concurrent_interns_dedupe_while_tables_grow() {
1154 let store = std::sync::Arc::new(Store::default());
1158 let threads: Vec<_> = (0..8u64)
1159 .map(|t| {
1160 let store = std::sync::Arc::clone(&store);
1161 std::thread::spawn(move || {
1162 let mut c = InternCache::default();
1163 let mut out = vec![Handle::EMPTY; 20_011];
1164 for k in 0..20_011u64 {
1165 let i = (k * (2 * t + 1)) % 20_011; let hash = crate::handle::mix64(i);
1167 let v = i64::try_from(i).unwrap_or(0);
1168 out[usize::try_from(i).unwrap_or(0)] =
1169 store.intern(&mut c, Kind::Set, 0, 0, hash, 0, &[int(v)]);
1170 }
1171 store.flush_hits(&mut c);
1172 out
1173 })
1174 })
1175 .collect();
1176 let all: Vec<Vec<Handle>> = threads.into_iter().filter_map(|t| t.join().ok()).collect();
1177 assert_eq!(all.len(), 8);
1178 for (i, h) in (0..).zip(&all[0]) {
1179 assert_eq!(store.view(*h).data, &[int(i)]);
1180 }
1181 assert!(all.iter().all(|o| *o == all[0]));
1182 let st = store.stats();
1183 assert_eq!(st.nodes, 20_011);
1184 assert_eq!(st.hits + st.misses, 8 * 20_011);
1185 let memory = store.memory_usage();
1186 assert!(memory.current_table_bytes > 0);
1187 assert_eq!(
1188 memory.retired_tables, 0,
1189 "all worker caches have been dropped"
1190 );
1191 assert_eq!(memory.retired_table_bytes, 0);
1192 assert!(!store.poisoned());
1193 }
1194
1195 #[test]
1196 fn without_hashconsing_every_intern_inserts() {
1197 let store = Store::new(false);
1198 let mut c = InternCache::default();
1199 let a = store.intern(&mut c, Kind::Set, 0, 0, 9, 9, &[int(1)]);
1200 let b = store.intern(&mut c, Kind::Set, 0, 0, 9, 9, &[int(1)]);
1201 assert_ne!(a, b);
1202 assert_eq!(store.view(a).data, store.view(b).data);
1203 assert_eq!(store.stats().nodes, 2);
1204 }
1205
1206 #[test]
1207 fn foreign_handles_poison_the_store() {
1208 let store = Store::default();
1209 let v = store.view(Handle::persistent(3, 0, 99));
1210 assert_eq!(v.data.len(), 0);
1211 assert!(store.poisoned());
1212 }
1213}