use hashbrown::HashTable;
use rayon::prelude::*;
use crate::{
elf::{Group, constants::GRP_COMDAT},
error::{Error, Result},
symbol::{SHARDS, shard_of},
};
pub struct GroupDedup {
kept: Vec<SignatureSet>,
members: SectionRows,
discarded: usize,
retained: Vec<(usize, Vec<u16>)>,
}
impl Default for GroupDedup {
fn default() -> Self {
Self {
kept: (0..SHARDS).map(|_| SignatureSet::default()).collect(),
members: SectionRows::default(),
discarded: 0,
retained: Vec::new(),
}
}
}
#[derive(Clone, Copy)]
struct Membership {
group: u32,
discarded: bool,
}
impl Default for Membership {
fn default() -> Self {
Self {
group: NO_GROUP,
discarded: false,
}
}
}
const NO_GROUP: u32 = u32::MAX;
#[derive(Default)]
struct SignatureSet {
table: HashTable<(u64, u32, u32)>,
arena: Vec<u8>,
}
impl SignatureSet {
fn insert(&mut self, signature: &[u8], hash: u64) -> bool {
let Self { table, arena } = self;
let found = table.find(hash, |&(h, start, end)| {
h == hash
&& arena.get(start as usize..end as usize) == Some(signature)
});
if found.is_some() {
return false;
}
let Ok(start) = u32::try_from(arena.len()) else {
return true;
};
arena.extend_from_slice(signature);
let Ok(end) = u32::try_from(arena.len()) else {
arena.truncate(start as usize);
return true;
};
table.insert_unique(hash, (hash, start, end), |&(h, ..)| h);
true
}
fn reserve(&mut self, extra: usize) {
self.table.reserve(extra, |&(h, ..)| h);
}
}
#[derive(Default)]
struct SectionRows {
rows: Vec<Vec<Membership>>,
}
impl SectionRows {
fn get(&self, file: usize, section: u16) -> Membership {
self.rows
.get(file)
.and_then(|row| row.get(usize::from(section)))
.copied()
.unwrap_or_default()
}
fn slot(&mut self, file: usize, section: u16) -> Option<&mut Membership> {
if self.rows.len() <= file {
self.rows.resize_with(file.saturating_add(1), Vec::new);
}
let row = self.rows.get_mut(file)?;
let at = usize::from(section);
if row.len() <= at {
row.resize(at.saturating_add(1), Membership::default());
}
row.get_mut(at)
}
}
type FileVerdicts = (Vec<(u32, Vec<u16>)>, Vec<u16>);
#[derive(Clone, Copy)]
struct Claim<'data> {
file: u32,
group: u32,
hash: u64,
signature: &'data [u8],
}
impl GroupDedup {
pub fn new() -> Self {
Self::default()
}
pub fn scan_batch(&mut self, files: &[Vec<Group<'_>>]) -> Result<()> {
let mut shards: Vec<Vec<Claim<'_>>> = partition_claims(files);
let kept_lists: Vec<Vec<(u32, u32)>> = self
.kept
.par_iter_mut()
.zip(&mut shards)
.map(|(set, claims)| {
set.reserve(claims.len());
let mut kept = Vec::new();
for c in claims.drain(..) {
if set.insert(c.signature, c.hash) {
kept.push((c.file, c.group));
}
}
kept
})
.collect();
let mut kept: Vec<Vec<bool>> =
files.iter().map(|g| vec![false; g.len()]).collect();
for (file, group) in kept_lists.into_iter().flatten() {
if let Some(slot) = kept
.get_mut(file as usize)
.and_then(|row| row.get_mut(group as usize))
{
*slot = true;
}
}
self.record_batch(files, &kept)
}
fn record_batch(
&mut self,
files: &[Vec<Group<'_>>],
kept: &[Vec<bool>],
) -> Result<()> {
let mut work: Vec<FileVerdicts> = Vec::with_capacity(files.len());
for (file, groups) in files.iter().enumerate() {
let mut mine = (Vec::new(), Vec::new());
for (g, group) in groups.iter().enumerate() {
if group.flags & !GRP_COMDAT != 0 {
return Err(Error::Format("unsupported SHT_GROUP flags"));
}
let keep = group.flags & GRP_COMDAT == 0
|| group.signature.is_empty()
|| kept
.get(file)
.and_then(|row| row.get(g))
.copied()
.unwrap_or(false);
let sections: Vec<u16> = group
.members
.iter()
.filter_map(|&m| u16::try_from(m).ok())
.collect();
if !keep {
mine.1.extend(sections);
} else if sections.len() >= 2 {
let id = u32::try_from(self.retained.len())
.map_err(|_| Error::OutOfRange("section groups"))?;
self.retained.push((file, sections.clone()));
mine.0.push((id, sections));
}
}
work.push(mine);
}
if self.members.rows.len() < files.len() {
self.members.rows.resize_with(files.len(), Vec::new);
}
let counts: Vec<usize> = self
.members
.rows
.par_iter_mut()
.zip(&work)
.map(|(row, (retained, discarded))| {
let top = retained
.iter()
.flat_map(|(_, s)| s.iter())
.chain(discarded.iter())
.copied()
.max();
if let Some(top) = top {
let need = usize::from(top).saturating_add(1);
if row.len() < need {
row.resize(need, Membership::default());
}
}
for (id, sections) in retained {
for §ion in sections {
if let Some(slot) = row.get_mut(usize::from(section)) {
slot.group = *id;
}
}
}
let mut newly = 0usize;
for §ion in discarded {
if let Some(slot) = row.get_mut(usize::from(section))
&& !slot.discarded
{
slot.discarded = true;
newly = newly.saturating_add(1);
}
}
newly
})
.collect();
for n in counts {
self.discarded = self.discarded.saturating_add(n);
}
Ok(())
}
pub fn is_discarded(&self, file: usize, section: u16) -> bool {
self.discarded != 0 && self.members.get(file, section).discarded
}
pub const fn discarded_count(&self) -> usize {
self.discarded
}
pub fn group_members(&self, file: usize, section: u16) -> &[u16] {
if self.retained.is_empty() {
return &[];
}
let group = self.members.get(file, section).group;
self.retained
.get(group as usize)
.map_or(&[], |(_, members)| members.as_slice())
}
pub fn is_grouped(&self, file: usize, section: u16) -> bool {
!self.retained.is_empty()
&& self.members.get(file, section).group != NO_GROUP
}
pub fn scan(&mut self, file: usize, groups: &[Group<'_>]) -> Result<()> {
for group in groups {
if group.flags & !GRP_COMDAT != 0 {
return Err(Error::Format("unsupported SHT_GROUP flags"));
}
if group.flags & GRP_COMDAT == 0 || group.signature.is_empty() {
self.record_group(file, group.members)?;
continue;
}
let hash = group.signature_hash;
let won = self
.kept
.get_mut(shard_of(hash))
.is_some_and(|set| set.insert(group.signature, hash));
if won {
self.record_group(file, group.members)?;
} else {
self.record_members(file, group.members);
}
}
Ok(())
}
fn record_group(&mut self, file: usize, members: &[u32]) -> Result<()> {
let id = u32::try_from(self.retained.len())
.map_err(|_| Error::OutOfRange("section groups"))?;
let sections: Vec<u16> = members
.iter()
.filter_map(|&m| u16::try_from(m).ok())
.collect();
if sections.len() < 2 {
return Ok(());
}
for §ion in §ions {
if let Some(slot) = self.members.slot(file, section) {
slot.group = id;
}
}
self.retained.push((file, sections));
Ok(())
}
fn record_members(&mut self, file: usize, members: &[u32]) {
for &raw in members {
let Ok(section) = u16::try_from(raw) else {
continue;
};
if let Some(slot) = self.members.slot(file, section)
&& !slot.discarded
{
slot.discarded = true;
self.discarded = self.discarded.saturating_add(1);
}
}
}
}
fn partition_claims<'data>(
files: &[Vec<Group<'data>>],
) -> Vec<Vec<Claim<'data>>> {
let per_file: Vec<Vec<Vec<Claim<'data>>>> = files
.par_iter()
.enumerate()
.map(|(file, groups)| {
let mut buckets: Vec<Vec<Claim<'data>>> =
(0..SHARDS).map(|_| Vec::new()).collect();
for (g, group) in groups.iter().enumerate() {
if group.flags & !GRP_COMDAT != 0
|| group.flags & GRP_COMDAT == 0
|| group.signature.is_empty()
{
continue;
}
let claim = Claim {
file: u32::try_from(file).unwrap_or(u32::MAX),
group: u32::try_from(g).unwrap_or(u32::MAX),
hash: group.signature_hash,
signature: group.signature,
};
if let Some(bucket) = buckets.get_mut(shard_of(claim.hash)) {
bucket.push(claim);
}
}
buckets
})
.collect();
(0..SHARDS)
.into_par_iter()
.map(|s| {
let total =
per_file.iter().map(|b| b.get(s).map_or(0, Vec::len)).sum();
let mut shard = Vec::with_capacity(total);
for buckets in &per_file {
if let Some(bucket) = buckets.get(s) {
shard.extend_from_slice(bucket);
}
}
shard
})
.collect()
}