// Copyright 2022 The ChromiumOS Authors // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. use std::cmp::Ordering; use std::cmp::Reverse; use std::ops::Sub; use std::time::Duration; use anyhow::anyhow; use anyhow::bail; use anyhow::Result; use base::warn; fn abs_diff + Ord>(x: T, y: T) -> T { if x < y { y - x } else { x - y } } #[derive(Default, Debug, Clone, Copy, Eq, PartialEq)] pub struct CoreOffset { pub core: usize, pub offset: i128, } impl Ord for CoreOffset { // CoreOffsets are ordered by offset ascending, then by their core number ascending fn cmp(&self, other: &Self) -> Ordering { (self.offset, self.core).cmp(&(other.offset, other.core)) } } impl PartialOrd for CoreOffset { fn partial_cmp(&self, other: &Self) -> Option { Some(self.cmp(other)) } } #[derive(Default, Debug, Clone, Eq, PartialEq)] pub struct CoreGroup { pub cores: Vec, } impl CoreGroup { fn size(&self) -> usize { self.cores.len() } fn add(&self, core: CoreOffset, limit: u128) -> Result { let diff_from_min = abs_diff(self.cores.iter().min().unwrap().offset, core.offset) as u128; let diff_from_max = abs_diff(self.cores.iter().max().unwrap().offset, core.offset) as u128; let can_add = diff_from_min < limit && diff_from_max < limit; if can_add { let mut new = self.clone(); new.cores.push(core); Ok(new) } else { Err(anyhow!( "offset {} not within {} of all members of core group", core.offset, limit )) } } } #[derive(Default, Debug, Clone, Eq, PartialEq)] pub struct CoreGrouping { groups: Vec, } impl Ord for CoreGrouping { fn cmp(&self, other: &Self) -> Ordering { // Ordered by largest group size descending, then by number of groups ascending (Reverse(self.largest_group().size()), self.groups.len()) .cmp(&(Reverse(other.largest_group().size()), other.groups.len())) } } impl PartialOrd for CoreGrouping { fn partial_cmp(&self, other: &Self) -> Option { Some(self.cmp(other)) } } impl CoreGrouping { pub(super) fn new(groups: Vec) -> Result { // Other functions in this type rely on the fact that there is at least one CoreGroup. if groups.is_empty() { return Err(anyhow!("Cannot create an empty CoreGrouping.")); } Ok(CoreGrouping { groups }) } pub fn size(&self) -> usize { self.groups.len() } pub fn largest_group_index(&self) -> usize { // Sort by Reverse(size) then group index, and take the min. // We could sort by size then Reverse(index), but then getting the index out is hard. self.groups .iter() .enumerate() .map(|(i, g)| (Reverse(g.size()), i)) .min() .unwrap_or((Reverse(0), 0)) .1 } pub fn largest_group(&self) -> &CoreGroup { &self.groups[self.largest_group_index()] } pub fn core_grouping_bitmask(&self) -> u64 { // If there's only one group, then all cores are in sync if self.size() == 0 { return 0; } let mut bitmask = 0u64; let largest_group_index = self.largest_group_index(); for (i, group) in self.groups.iter().enumerate() { // The largest group is considered the in-sync group if i == largest_group_index { continue; } // Set the bitmask to 1 for all cores in all other groups for core in &group.cores { if core.core > 63 { warn!("Core grouping bitmask cannot contain core {}", core.core); continue; } bitmask |= 1 << core.core; } } bitmask } fn add_group(&mut self, group: CoreGroup) { self.groups.push(group) } fn add_core_to_last_group(&self, core: CoreOffset, in_sync_threshold: u128) -> Option { let last_group = self.groups.len() - 1; self.groups[last_group] .add(core, in_sync_threshold) .map(|new_group| { let mut new_grouping = self.clone(); new_grouping.groups[last_group] = new_group; new_grouping }) .ok() } } /// Group cores by their offsets that are within `in_sync_threshold` of each other. /// /// This uses a generic integer grouping algorithm. Because we're grouping within a threshold, /// there are potentially multiple ways we can group the integers, and we want to find the "best" /// grouping. Our definition of best grouping is: /// 1. The grouping who's largest group is the largest. /// 2. If there are multiple groupings with the same size largest group, take the one with the /// fewest groups. /// /// We could naively generate all possible groupings by iterating through the sorted integers and, /// for each grouping, either adding that integer as it's own group or adding it to the last group /// of that grouping. This could generate 2^N groupings, where N is the number of integers. Instead, /// we still iterate through the sorted integers and, for each grouping, we add it to the last /// group of that grouping. But we only add the integer as it's own group to the current best /// grouping. This optimization avoids creating groupings that we know will not be the "best" /// grouping, because adding the integer as it's own group means that all subsequent integers /// cannot be grouped with the existing groups, and thus we only care about the optimal existing /// groups. pub(super) fn group_core_offsets( offsets: &[(usize, i128)], in_sync_threshold: Duration, tsc_frequency: u64, ) -> Result { if offsets.is_empty() { bail!("Per-core offsets cannot be empty"); } // Convert threshold to TSC ticks let in_sync_threshold_ticks = in_sync_threshold.as_nanos() * tsc_frequency as u128 / 1_000_000_000u128; let mut cores: Vec = offsets .iter() .map(|(i, offset)| CoreOffset { core: *i, offset: *offset, }) .collect(); // Cores are sorted by their ascending by their offset then ascending by their core #. See the // Ord implementation for CoreOffset. cores.sort(); let mut grouping_options: Vec = vec![CoreGrouping::new(vec![CoreGroup { cores: vec![cores[0]], }])?]; for core in &cores[1..] { let mut best = grouping_options[0].clone(); best.add_group(CoreGroup { cores: vec![*core] }); let mut next_grouping_options = vec![best]; for grouping_option in &grouping_options { if let Some(new_grouping) = grouping_option.add_core_to_last_group(*core, in_sync_threshold_ticks) { next_grouping_options.push(new_grouping); } } next_grouping_options.sort(); grouping_options = next_grouping_options; } Ok(grouping_options[0].clone()) } #[cfg(test)] mod tests { use super::super::TscState; use super::*; #[test] fn test_simple_offset_grouping() { let offsets = vec![(0, 10), (1, 10), (2, 10), (3, 1000)]; let state = TscState::new(1_000_000_000, offsets, Duration::from_nanos(1)) .expect("TscState::new should not fail for this test"); let group0 = CoreGroup { cores: vec![ CoreOffset { core: 0, offset: 10, }, CoreOffset { core: 1, offset: 10, }, CoreOffset { core: 2, offset: 10, }, ], }; let group1 = CoreGroup { cores: vec![CoreOffset { core: 3, offset: 1000, }], }; assert_eq!( state.core_grouping, CoreGrouping::new(vec![group0.clone(), group1]) .expect("CoreGrouping::new should not fail here") ); assert_eq!(state.core_grouping.largest_group().clone(), group0); assert_eq!(state.core_grouping.core_grouping_bitmask(), 0b1000u64); } #[test] fn test_ambiguous_offset_grouping() { // Could be grouped in several ways: // - [10, 20] [30, 40] [50] <--- we like to have core0 be in a larger group // - [10] [20, 30] [40, 50] // - [10, 20] [30] [40, 50] let offsets = vec![(0, 10), (1, 20), (2, 30), (3, 40), (4, 50)]; let state = TscState::new(1_000_000_000, offsets, Duration::from_nanos(20)) .expect("TscState::new should not fail for this test"); let group0 = CoreGroup { cores: vec![ CoreOffset { core: 0, offset: 10, }, CoreOffset { core: 1, offset: 20, }, ], }; let group1 = CoreGroup { cores: vec![ CoreOffset { core: 2, offset: 30, }, CoreOffset { core: 3, offset: 40, }, ], }; let group2 = CoreGroup { cores: vec![CoreOffset { core: 4, offset: 50, }], }; assert_eq!( state.core_grouping, CoreGrouping::new(vec![group0.clone(), group1, group2]) .expect("CoreGrouping::new should not fail here") ); // largest_group should return the first group over other equally large groups assert_eq!(state.core_grouping.largest_group().clone(), group0); assert_eq!(state.core_grouping.core_grouping_bitmask(), 0b11100u64); } #[test] fn test_worst_case_grouping() { // Worst case for the grouping algorithm, where if your algorithm isn't smart you can // generate 2^129 groupings, which would be too large for a Vec to hold. This test just // verifies that we don't crash or run out of memory. let offsets = (0..129).map(|i| (i, 0)).collect(); TscState::new(1_000_000_000, offsets, Duration::from_nanos(1)) .expect("TscState::new should not fail for this test"); } }