1use bytesize::ByteSize;
2#[cfg(feature = "metrics")]
3use openvm_stark_backend::memory_metering::INTERACTION_MEMORY_OVERHEAD;
4use openvm_stark_backend::memory_metering::{ProvingMemoryConfig, ProvingMemoryCounts};
5use serde::{Deserialize, Serialize};
6
7use crate::utils::{add_one_or_zero, next_power_of_two_or_zero};
8
9pub const DEFAULT_SEGMENT_CHECK_INSNS: u64 = 1000;
10
11pub const DEFAULT_MAX_MEMORY: usize = 15 << 30; #[derive(derive_new::new, Clone, Debug, Serialize, Deserialize)]
14pub struct Segment {
15 pub instret_start: u64,
16 pub num_insns: u64,
17 pub trace_heights: Vec<u32>,
18}
19
20#[derive(Clone, Copy, Debug)]
21pub struct SegmentationLimits {
22 pub max_trace_height_bits: u8,
23 pub max_memory: usize,
24 pub max_interactions: u32,
25}
26
27#[derive(Clone, Debug)]
28struct SegmentationParams {
29 air_names: Vec<String>,
30 widths: Vec<usize>,
31 interactions: Vec<usize>,
32 need_rot: Vec<bool>,
33 max_trace_height: u32,
34 max_memory: usize,
35 max_interactions: u32,
36 memory_config: ProvingMemoryConfig,
37 segment_check_insns: u64,
38}
39
40impl SegmentationParams {
41 fn new(
42 air_names: Vec<String>,
43 widths: Vec<usize>,
44 interactions: Vec<usize>,
45 need_rot: Vec<bool>,
46 limits: SegmentationLimits,
47 memory_config: ProvingMemoryConfig,
48 ) -> Self {
49 assert_eq!(air_names.len(), widths.len());
50 assert_eq!(air_names.len(), interactions.len());
51 assert_eq!(air_names.len(), need_rot.len());
52 assert!(
53 limits.max_trace_height_bits < u32::BITS as u8,
54 "max_trace_height_bits must be less than {}",
55 u32::BITS
56 );
57
58 let max_trace_height = 1u32
59 .checked_shl(u32::from(limits.max_trace_height_bits))
60 .expect("max_trace_height_bits must fit in u32 trace height");
61 assert!(
62 u64::from(max_trace_height) >= 2 * DEFAULT_SEGMENT_CHECK_INSNS,
63 "max_trace_height must be at least twice DEFAULT_SEGMENT_CHECK_INSNS"
64 );
65
66 Self {
67 air_names,
68 widths,
69 interactions,
70 need_rot,
71 max_trace_height,
72 max_memory: limits.max_memory,
73 max_interactions: limits.max_interactions,
74 memory_config,
75 segment_check_insns: DEFAULT_SEGMENT_CHECK_INSNS,
76 }
77 }
78}
79
80#[derive(Clone, Debug)]
81pub struct SegmentationCtx {
82 pub segments: Vec<Segment>,
83 params: SegmentationParams,
84 pub instret: u64,
85 pub instrets_until_check: u64,
86 pub(crate) checkpoint_trace_heights: Vec<u32>,
88 checkpoint_instret: u64,
90}
91
92#[derive(Clone, Copy, Debug)]
93enum SegmentationTrigger {
94 Height {
95 #[cfg(feature = "metrics")]
96 air_id: usize,
97 },
98 Memory,
99 Interactions,
100}
101
102#[cfg(feature = "metrics")]
103impl SegmentationTrigger {
104 fn reason(self) -> &'static str {
105 match self {
106 SegmentationTrigger::Height { .. } => "height",
107 SegmentationTrigger::Memory => "memory",
108 SegmentationTrigger::Interactions => "interactions",
109 }
110 }
111}
112
113#[derive(Default)]
114struct MeteredCounts {
115 unpadded_rows: usize,
117 padding_rows: usize,
119 main_unpadded_with_rot: usize,
121 main_padding_with_rot: usize,
123 main_unpadded_no_rot: usize,
125 main_padding_no_rot: usize,
127 interaction_cells_unpadded: usize,
129 interaction_cells_padding: usize,
131}
132
133struct MeteredMemoryBreakdown {
134 total: usize,
136 unpadded: usize,
138}
139
140impl SegmentationCtx {
141 pub fn new(
142 air_names: Vec<String>,
143 widths: Vec<usize>,
144 interactions: Vec<usize>,
145 need_rot: Vec<bool>,
146 limits: SegmentationLimits,
147 memory_config: ProvingMemoryConfig,
148 ) -> Self {
149 let num_airs = air_names.len();
150 let params = SegmentationParams::new(
151 air_names,
152 widths,
153 interactions,
154 need_rot,
155 limits,
156 memory_config,
157 );
158 Self {
159 segments: Vec::new(),
160 instrets_until_check: params.segment_check_insns,
161 params,
162 instret: 0,
163 checkpoint_trace_heights: vec![0; num_airs],
164 checkpoint_instret: 0,
165 }
166 }
167
168 #[inline(always)]
169 pub(crate) fn air_names(&self) -> &[String] {
170 &self.params.air_names
171 }
172
173 #[inline(always)]
174 pub(crate) fn widths(&self) -> &[usize] {
175 &self.params.widths
176 }
177
178 #[inline(always)]
179 pub(super) fn segment_check_insns(&self) -> u64 {
180 self.params.segment_check_insns
181 }
182
183 pub fn set_max_memory(&mut self, max_memory: usize) {
184 self.params.max_memory = max_memory;
185 }
186
187 #[inline(always)]
189 fn calculate_max_trace_height_with_name(&self, trace_heights: &[u32]) -> (u32, &str) {
190 trace_heights
191 .iter()
192 .enumerate()
193 .map(|(i, &height)| (next_power_of_two_or_zero(height as usize) as u32, i))
194 .max_by_key(|(height, _)| *height)
195 .map(|(height, idx)| (height, self.params.air_names[idx].as_str()))
196 .unwrap_or((0, "unknown"))
197 }
198
199 #[inline(always)]
201 fn counts_to_memory(
202 &self,
203 main_cnt_with_rot: usize,
204 main_cnt_no_rot: usize,
205 interaction_cells: usize,
206 ) -> (
207 usize, usize, usize, ) {
211 let estimate = self.params.memory_config.estimate(ProvingMemoryCounts::new(
212 main_cnt_with_rot,
213 main_cnt_no_rot,
214 interaction_cells,
215 ));
216 (estimate.total, estimate.main, estimate.interaction)
217 }
218
219 #[inline(always)]
222 fn calculate_count_breakdown(&self, trace_heights: &[u32]) -> MeteredCounts {
223 debug_assert_eq!(trace_heights.len(), self.params.widths.len());
224 debug_assert_eq!(trace_heights.len(), self.params.interactions.len());
225 debug_assert_eq!(trace_heights.len(), self.params.need_rot.len());
226
227 let mut counts = MeteredCounts::default();
228 for (((&height, &width), &interactions), &need_rot) in trace_heights
229 .iter()
230 .zip(self.params.widths.iter())
231 .zip(self.params.interactions.iter())
232 .zip(self.params.need_rot.iter())
233 {
234 let padded_height = next_power_of_two_or_zero(height as usize);
235 let unpadded_height = height as usize;
236 let padding_height = padded_height - unpadded_height;
237 counts.unpadded_rows += unpadded_height;
238 counts.padding_rows += padding_height;
239 let main_unpadded_cells = unpadded_height * width;
240 let main_padding_cells = padding_height * width;
241 if need_rot {
242 counts.main_unpadded_with_rot += main_unpadded_cells;
243 counts.main_padding_with_rot += main_padding_cells;
244 } else {
245 counts.main_unpadded_no_rot += main_unpadded_cells;
246 counts.main_padding_no_rot += main_padding_cells;
247 }
248 counts.interaction_cells_unpadded += unpadded_height * interactions;
249 counts.interaction_cells_padding += padding_height * interactions;
250 }
251 counts
252 }
253
254 #[inline(always)]
257 fn calculate_cell_counts(&self, trace_heights: &[u32]) -> (usize, usize, usize) {
258 debug_assert_eq!(trace_heights.len(), self.params.widths.len());
259 debug_assert_eq!(trace_heights.len(), self.params.interactions.len());
260 debug_assert_eq!(trace_heights.len(), self.params.need_rot.len());
261
262 let mut main_cnt_with_rot = 0;
263 let mut main_cnt_no_rot = 0;
264 let mut interaction_cells = 0;
265 for (((&height, &width), &interactions), &need_rot) in trace_heights
266 .iter()
267 .zip(self.params.widths.iter())
268 .zip(self.params.interactions.iter())
269 .zip(self.params.need_rot.iter())
270 {
271 let padded_height = next_power_of_two_or_zero(height as usize);
272 let main_cells = padded_height * width;
273 if need_rot {
274 main_cnt_with_rot += main_cells;
275 } else {
276 main_cnt_no_rot += main_cells;
277 }
278 interaction_cells += padded_height * interactions;
279 }
280 (main_cnt_with_rot, main_cnt_no_rot, interaction_cells)
281 }
282
283 #[inline(always)]
285 fn calculate_total_memory(
286 &self,
287 trace_heights: &[u32],
288 ) -> (
289 usize, usize, usize, ) {
293 let (main_cnt_with_rot, main_cnt_no_rot, interaction_cells) =
294 self.calculate_cell_counts(trace_heights);
295 self.counts_to_memory(main_cnt_with_rot, main_cnt_no_rot, interaction_cells)
296 }
297
298 #[inline(always)]
299 fn calculate_memory_breakdown(&self, counts: &MeteredCounts) -> MeteredMemoryBreakdown {
300 let unpadded = self.params.memory_config.estimate(ProvingMemoryCounts::new(
301 counts.main_unpadded_with_rot,
302 counts.main_unpadded_no_rot,
303 counts.interaction_cells_unpadded,
304 ));
305 let total = self.params.memory_config.estimate(ProvingMemoryCounts::new(
306 counts.main_unpadded_with_rot + counts.main_padding_with_rot,
307 counts.main_unpadded_no_rot + counts.main_padding_no_rot,
308 counts.interaction_cells_unpadded + counts.interaction_cells_padding,
309 ));
310
311 MeteredMemoryBreakdown {
312 total: total.total,
313 unpadded: unpadded.total,
314 }
315 }
316
317 #[inline(always)]
321 fn calculate_total_interactions(&self, trace_heights: &[u32]) -> u64 {
322 debug_assert_eq!(trace_heights.len(), self.params.interactions.len());
323
324 trace_heights
325 .iter()
326 .zip(self.params.interactions.iter())
327 .map(|(&height, &interactions)| add_one_or_zero(height) as u64 * interactions as u64)
328 .sum()
329 }
330
331 #[inline(always)]
332 pub(crate) fn should_segment(
333 &self,
334 instret: u64,
335 trace_heights: &[u32],
336 is_trace_height_constant: &[bool],
337 ) -> bool {
338 self.segmentation_trigger(instret, trace_heights, is_trace_height_constant)
339 .is_some()
340 }
341
342 #[inline(always)]
343 fn segmentation_trigger(
344 &self,
345 instret: u64,
346 trace_heights: &[u32],
347 is_trace_height_constant: &[bool],
348 ) -> Option<SegmentationTrigger> {
349 debug_assert_eq!(trace_heights.len(), is_trace_height_constant.len());
350 debug_assert_eq!(trace_heights.len(), self.params.air_names.len());
351 debug_assert_eq!(trace_heights.len(), self.params.widths.len());
352 debug_assert_eq!(trace_heights.len(), self.params.interactions.len());
353 debug_assert_eq!(trace_heights.len(), self.params.need_rot.len());
354
355 let instret_start = self
356 .segments
357 .last()
358 .map_or(0, |s| s.instret_start + s.num_insns);
359 let num_insns = instret - instret_start;
360
361 if num_insns == 0 {
363 return None;
364 }
365
366 let mut main_cnt_with_rot = 0usize;
367 let mut main_cnt_no_rot = 0usize;
368 let mut interaction_cells = 0usize;
369 for (i, ((((padded_height, width), interactions), is_constant), &need_rot)) in trace_heights
370 .iter()
371 .map(|&height| next_power_of_two_or_zero(height as usize) as u32)
372 .zip(self.params.widths.iter())
373 .zip(self.params.interactions.iter())
374 .zip(is_trace_height_constant.iter())
375 .zip(self.params.need_rot.iter())
376 .enumerate()
377 {
378 if !is_constant && padded_height > self.params.max_trace_height {
381 let air_name = unsafe { self.params.air_names.get_unchecked(i) };
382 tracing::info!(
383 "overshoot: instret {:10} | height ({:8}) > max ({:8}) | chip {:3} ({}) ",
384 instret,
385 padded_height,
386 self.params.max_trace_height,
387 i,
388 air_name,
389 );
390 return Some(SegmentationTrigger::Height {
391 #[cfg(feature = "metrics")]
392 air_id: i,
393 });
394 }
395 let main_cells = padded_height as usize * width;
396 if need_rot {
397 main_cnt_with_rot += main_cells;
398 } else {
399 main_cnt_no_rot += main_cells;
400 }
401 interaction_cells += padded_height as usize * interactions;
402 }
403
404 let (total_memory, main_memory, interaction_memory) =
405 self.counts_to_memory(main_cnt_with_rot, main_cnt_no_rot, interaction_cells);
406 if total_memory > self.params.max_memory {
407 tracing::info!(
408 "overshoot: instret {:10} | total memory ({:5}) > max ({:5}) | main ({:5}) | interaction ({:5})",
409 instret,
410 ByteSize::b(total_memory as u64),
411 ByteSize::b(self.params.max_memory as u64),
412 ByteSize::b(main_memory as u64),
413 ByteSize::b(interaction_memory as u64),
414 );
415 return Some(SegmentationTrigger::Memory);
416 }
417
418 let total_interactions = self.calculate_total_interactions(trace_heights);
419 if total_interactions > u64::from(self.params.max_interactions) {
420 tracing::info!(
421 "overshoot: instret {:10} | total interactions ({:10}) > max ({:10})",
422 instret,
423 total_interactions,
424 self.params.max_interactions
425 );
426 return Some(SegmentationTrigger::Interactions);
427 }
428
429 None
430 }
431
432 #[inline(always)]
433 pub fn check_and_segment(
434 &mut self,
435 instret: u64,
436 trace_heights: &mut [u32],
437 is_trace_height_constant: &[bool],
438 ) -> bool {
439 let trigger = self.segmentation_trigger(instret, trace_heights, is_trace_height_constant);
440 let should_segment = trigger.is_some();
441
442 #[cfg(feature = "metrics")]
443 if let Some(trigger) = trigger {
444 self.emit_segmentation_trigger_metric(trigger);
445 }
446
447 if should_segment {
448 self.create_segment_from_checkpoint(instret, trace_heights);
449 true
450 } else {
451 false
452 }
453 }
454
455 #[inline(always)]
456 fn create_segment_from_checkpoint(&mut self, instret: u64, trace_heights: &mut [u32]) {
457 let instret_start = self
458 .segments
459 .last()
460 .map_or(0, |s| s.instret_start + s.num_insns);
461
462 let (segment_instret, segment_heights) = if self.checkpoint_instret > instret_start {
463 (
464 self.checkpoint_instret,
465 self.checkpoint_trace_heights.clone(),
466 )
467 } else {
468 let trace_heights_str = trace_heights
469 .iter()
470 .zip(self.params.air_names.iter())
471 .filter(|(&height, _)| height > 0)
472 .map(|(&height, name)| format!(" {name} = {height}"))
473 .collect::<Vec<_>>()
474 .join("\n");
475 tracing::warn!(
476 "No valid checkpoint, creating segment using instret={instret}\ntrace_heights=[\n{trace_heights_str}\n]"
477 );
478 (instret, trace_heights.to_vec())
480 };
481
482 let num_insns = segment_instret - instret_start;
483 self.create_segment::<false>(instret_start, num_insns, segment_heights);
484 }
485
486 #[inline(always)]
488 pub(crate) fn initialize_segment(
489 &mut self,
490 trace_heights: &mut [u32],
491 is_trace_height_constant: &[bool],
492 ) {
493 let last_segment = self.segments.last().unwrap();
495 self.reset_trace_heights(
496 trace_heights,
497 &last_segment.trace_heights,
498 is_trace_height_constant,
499 );
500 }
501
502 #[inline(always)]
504 fn reset_trace_heights(
505 &self,
506 trace_heights: &mut [u32],
507 segment_heights: &[u32],
508 is_trace_height_constant: &[bool],
509 ) {
510 for ((trace_height, &segment_height), &is_trace_height_constant) in trace_heights
511 .iter_mut()
512 .zip(segment_heights.iter())
513 .zip(is_trace_height_constant.iter())
514 {
515 if !is_trace_height_constant {
516 *trace_height = trace_height.checked_sub(segment_height).unwrap();
517 }
518 }
519 }
520
521 #[inline(always)]
523 pub(crate) fn update_checkpoint(&mut self, instret: u64, trace_heights: &[u32]) {
524 self.checkpoint_trace_heights.copy_from_slice(trace_heights);
525 self.checkpoint_instret = instret;
526 }
527
528 #[inline(always)]
530 pub fn create_final_segment(&mut self, trace_heights: &[u32]) {
531 self.instret += self.params.segment_check_insns - self.instrets_until_check;
532 self.instrets_until_check = self.params.segment_check_insns;
533 let instret_start = self
534 .segments
535 .last()
536 .map_or(0, |s| s.instret_start + s.num_insns);
537
538 let num_insns = self.instret - instret_start;
539 self.create_segment::<true>(instret_start, num_insns, trace_heights.to_vec());
540 }
541
542 #[inline(always)]
544 fn create_segment<const IS_FINAL: bool>(
545 &mut self,
546 instret_start: u64,
547 num_insns: u64,
548 trace_heights: Vec<u32>,
549 ) {
550 debug_assert!(
551 num_insns > 0,
552 "Segment should contain at least one instruction"
553 );
554
555 self.log_segment_info::<IS_FINAL>(instret_start, num_insns, &trace_heights);
556 #[cfg(feature = "metrics")]
557 {
558 let segment = self.segments.len().to_string();
559 self.emit_metered_segment_metrics(&segment, &trace_heights);
560 self.emit_metered_air_metrics(&segment, &trace_heights);
561 }
562 self.segments.push(Segment {
563 instret_start,
564 num_insns,
565 trace_heights,
566 });
567 }
568
569 #[inline(always)]
573 fn calculate_memory_utilization(&self, trace_heights: &[u32]) -> f64 {
574 let counts = self.calculate_count_breakdown(trace_heights);
575 let memory = self.calculate_memory_breakdown(&counts);
576 if memory.total == 0 {
577 0.0
578 } else {
579 100.0 * memory.unpadded as f64 / memory.total as f64
580 }
581 }
582
583 #[inline(always)]
585 fn log_segment_info<const IS_FINAL: bool>(
586 &self,
587 instret_start: u64,
588 num_insns: u64,
589 trace_heights: &[u32],
590 ) {
591 let (max_trace_height, air_name) = self.calculate_max_trace_height_with_name(trace_heights);
592 let (total_memory, main_memory, interaction_memory) =
593 self.calculate_total_memory(trace_heights);
594 let total_interactions = self.calculate_total_interactions(trace_heights);
595 let utilization = self.calculate_memory_utilization(trace_heights);
596
597 let final_marker = if IS_FINAL { " [TERMINATED]" } else { "" };
598
599 tracing::info!(
600 "Segment {:3} | instret {:10} | {:8} instructions | {:5} memory ({:5}, {:5}) | {:10} interactions | {:8} max height ({}) | {:.2}% memory util{}",
601 self.segments.len(),
602 instret_start,
603 num_insns,
604 ByteSize::b(total_memory as u64),
605 ByteSize::b(main_memory as u64),
606 ByteSize::b(interaction_memory as u64),
607 total_interactions,
608 max_trace_height,
609 air_name,
610 utilization,
611 final_marker
612 );
613 }
614}
615
616#[cfg(feature = "metrics")]
617impl SegmentationCtx {
618 fn emit_segmentation_trigger_metric(&self, trigger: SegmentationTrigger) {
619 let segment = self.segments.len().to_string();
620 let reason = trigger.reason();
621 match trigger {
622 SegmentationTrigger::Height { air_id } => {
623 let labels = [
624 ("segment", segment),
625 ("reason", reason.to_string()),
626 ("air_id", air_id.to_string()),
627 ("air_name", self.params.air_names[air_id].clone()),
628 ];
629 metrics::counter!("segmentation_trigger", &labels).absolute(1);
630 }
631 SegmentationTrigger::Memory | SegmentationTrigger::Interactions => {
632 let labels = [("segment", segment), ("reason", reason.to_string())];
633 metrics::counter!("segmentation_trigger", &labels).absolute(1);
634 }
635 }
636 }
637
638 fn emit_metered_segment_metrics(&self, segment: &str, trace_heights: &[u32]) {
639 let counts = self.calculate_count_breakdown(trace_heights);
640 let memory = self.calculate_memory_breakdown(&counts);
641 let padding = memory.total - memory.unpadded;
642 let labels = [("segment", segment.to_string())];
643 metrics::counter!("metered_memory_bytes", &labels).absolute(memory.total as u64);
644 metrics::counter!("metered_memory_unpadded_bytes", &labels)
645 .absolute(memory.unpadded as u64);
646 metrics::counter!("metered_memory_padding_bytes", &labels).absolute(padding as u64);
647 metrics::counter!("metered_interaction_memory_overhead_bytes", &labels)
648 .absolute(INTERACTION_MEMORY_OVERHEAD as u64);
649 }
650
651 fn emit_metered_air_metrics(&self, segment: &str, trace_heights: &[u32]) {
652 let memory_config = self.params.memory_config;
653
654 for (air_id, ((((&height, &width), &interactions), &need_rot), air_name)) in trace_heights
655 .iter()
656 .zip(self.params.widths.iter())
657 .zip(self.params.interactions.iter())
658 .zip(self.params.need_rot.iter())
659 .zip(self.params.air_names.iter())
660 .enumerate()
661 {
662 let padded_height = next_power_of_two_or_zero(height as usize);
663 let unpadded_height = height as usize;
664 let padding_height = padded_height - unpadded_height;
665 if padded_height == 0 {
666 continue;
667 }
668 let labels = [
669 ("air_name", air_name.clone()),
670 ("air_id", air_id.to_string()),
671 ("segment", segment.to_string()),
672 ];
673 let unpadded_cells = unpadded_height * width;
674 let padding_cells = padding_height * width;
675 let interaction_cells_unpadded = unpadded_height * interactions;
677 let interaction_cells_padding = padding_height * interactions;
678 let main_secondary_unpadded =
679 memory_config.main_secondary_memory_bytes_for_rot(unpadded_cells, need_rot);
680 let main_secondary = memory_config
681 .main_secondary_memory_bytes_for_rot(unpadded_cells + padding_cells, need_rot);
682 let interaction_unpadded =
683 memory_config.interaction_memory_bytes_without_overhead(interaction_cells_unpadded);
684 let interaction_total = memory_config.interaction_memory_bytes_without_overhead(
685 interaction_cells_unpadded + interaction_cells_padding,
686 );
687
688 metrics::counter!("metered_rows_unpadded", &labels).absolute(height as u64);
689 metrics::counter!("metered_rows_padding", &labels).absolute(padding_height as u64);
690 metrics::counter!("metered_main_cells_unpadded", &labels)
691 .absolute(unpadded_cells as u64);
692 metrics::counter!("metered_main_cells_padding", &labels).absolute(padding_cells as u64);
693 metrics::counter!("metered_interaction_cells_unpadded", &labels)
694 .absolute(interaction_cells_unpadded as u64);
695 metrics::counter!("metered_interaction_cells_padding", &labels)
696 .absolute(interaction_cells_padding as u64);
697 metrics::counter!("metered_main_memory_unpadded_bytes", &labels)
698 .absolute(memory_config.main_memory_bytes(unpadded_cells) as u64);
699 metrics::counter!("metered_main_memory_padding_bytes", &labels)
700 .absolute(memory_config.main_memory_bytes(padding_cells) as u64);
701 metrics::counter!("metered_main_secondary_memory_unpadded_bytes", &labels)
702 .absolute(main_secondary_unpadded as u64);
703 metrics::counter!("metered_main_secondary_memory_padding_bytes", &labels)
704 .absolute((main_secondary - main_secondary_unpadded) as u64);
705 metrics::counter!("metered_interaction_memory_unpadded_bytes", &labels)
706 .absolute(interaction_unpadded as u64);
707 metrics::counter!("metered_interaction_memory_padding_bytes", &labels)
708 .absolute((interaction_total - interaction_unpadded) as u64);
709 }
710 }
711}