diff options
Diffstat (limited to 'users/zseri/store-ref-scanner/src')
| -rw-r--r-- | users/zseri/store-ref-scanner/src/hbm.rs | 150 | ||||
| -rw-r--r-- | users/zseri/store-ref-scanner/src/lib.rs | 225 | ||||
| -rw-r--r-- | users/zseri/store-ref-scanner/src/spec.rs | 46 |
3 files changed, 421 insertions, 0 deletions
diff --git a/users/zseri/store-ref-scanner/src/hbm.rs b/users/zseri/store-ref-scanner/src/hbm.rs new file mode 100644 index 000000000000..810a0c99cf88 --- /dev/null +++ b/users/zseri/store-ref-scanner/src/hbm.rs @@ -0,0 +1,150 @@ +#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)] +pub struct HalfBytesMask(pub [u8; 16]); + +impl HalfBytesMask { + pub const B32_REVSHA256: HalfBytesMask = + HalfBytesMask([0, 0, 0, 0, 0, 0, 255, 3, 0, 0, 0, 0, 222, 127, 207, 7]); + + pub const B64_BLAKE2B256: HalfBytesMask = HalfBytesMask([ + 0, 0, 0, 0, 0, 8, 255, 3, 254, 255, 255, 135, 254, 255, 255, 7, + ]); + + #[inline] + #[proc_unroll::unroll] + pub const fn from_expanded(x: [bool; 128]) -> Self { + let mut ret = [0u8; 16]; + for idx in 0..16 { + let mut tmp = 0; + let fin = idx * 8; + macro_rules! bitx { + ($($a:expr),+) => {{ $( if x[fin + $a] { tmp += (1 << $a) as u8; } )+ }} + } + bitx!(0, 1, 2, 3, 4, 5, 6, 7); + ret[idx] = tmp; + } + Self(ret) + } + + /// create a mask by allowing all characters via the mask which are included in the given string + pub fn from_bytes(s: &[u8]) -> Self { + s.iter().fold(Self([0u8; 16]), |mut ret, &i| { + ret.set(i, true); + ret + }) + } + + #[proc_unroll::unroll] + pub const fn into_expanded(self) -> [bool; 128] { + let Self(ihbm) = self; + let mut ret = [false; 128]; + for idx in 0..16 { + let fin = idx * 8; + let curi = ihbm[idx]; + macro_rules! bitx { + ($($a:expr),+) => {{ $( ret[fin + $a] = (curi >> $a) & 0b1 != 0; )+ }} + } + bitx!(0, 1, 2, 3, 4, 5, 6, 7); + } + ret + } + + pub fn contains(&self, byte: u8) -> bool { + (self.0[usize::from(byte / 8)] >> u32::from(byte % 8)) & 0b1 != 0 + } + + pub fn set(&mut self, byte: u8, allow: bool) { + if byte >= 0x80 { + if cfg!(debug_assertions) { + panic!( + "tried to manipulate invalid byte {:?} in HalfBytesMask", + byte + ); + } else { + return; + } + } + let mut block = &mut self.0[usize::from(byte / 8)]; + let bitpat = (1 << u32::from(byte % 8)) as u8; + if allow { + *block |= bitpat; + } else { + *block &= !bitpat; + } + } + + #[cfg(test)] + fn count_ones(&self) -> u8 { + self.0 + .iter() + .map(|i| i.count_ones()) + .sum::<u32>() + .try_into() + .unwrap() + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn maskbase() { + assert_eq!(HalfBytesMask::B32_REVSHA256.count_ones(), 32); + assert_eq!(HalfBytesMask::B64_BLAKE2B256.count_ones(), 64); + } + + #[test] + fn dflmask() { + assert_eq!( + HalfBytesMask::from_expanded( + [ + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + ] + .map(|i| i != 0) + ), + Default::default(), + ); + + assert_eq!( + HalfBytesMask::from_expanded( + [ + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, + ] + .map(|i| i != 0) + ), + HalfBytesMask::B32_REVSHA256, + ); + + assert_eq!( + HalfBytesMask::from_expanded( + [ + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, + ] + .map(|i| i != 0) + ), + HalfBytesMask::B64_BLAKE2B256, + ); + } + + proptest::proptest! { + #[test] + fn hbm_roundtrip(s: [u8; 16]) { + let a = HalfBytesMask(s); + let b = a.into_expanded(); + let c = HalfBytesMask::from_expanded(b); + assert_eq!(a, c); + } + } +} diff --git a/users/zseri/store-ref-scanner/src/lib.rs b/users/zseri/store-ref-scanner/src/lib.rs new file mode 100644 index 000000000000..2cf94b42ccd7 --- /dev/null +++ b/users/zseri/store-ref-scanner/src/lib.rs @@ -0,0 +1,225 @@ +// TODO: make this no_std if possible + +use camino::Utf8PathBuf; + +mod hbm; +pub use hbm::HalfBytesMask; + +mod spec; +pub use spec::*; + +/// limit maximal length of store basename +const BASENAME_MAXLEN: usize = 255; + +/// this is a trait which implements the interface of possible inputs +/// (usually byte slices) +pub trait ScannerInput: AsRef<[u8]> + Sized { + /// Splits the input into two at the given index. + /// Afterwards self contains elements [at, len), and the returned input part contains elements [0, at). + fn split_to(&mut self, at: usize) -> Self; + fn finish(&mut self); +} + +impl ScannerInput for &[u8] { + fn split_to(&mut self, at: usize) -> Self { + let (a, b) = self.split_at(at); + *self = b; + a + } + + fn finish(&mut self) { + *self = &[]; + } +} + +impl ScannerInput for &mut [u8] { + fn split_to(&mut self, at: usize) -> Self { + // Lifetime dance taken from `impl Write for &mut [u8]`. + // Taken from crate `std`. + let (a, b) = core::mem::replace(self, &mut []).split_at_mut(at); + *self = b; + a + } + + fn finish(&mut self) { + *self = &mut []; + } +} + +/// this is the primary structure of this crate +/// +/// it represents a scanner which scans binary slices for store references, +/// and implements an iterator interfaces which returns these as byte slices. +pub struct StoreRefScanner<'x, Input: 'x> { + input: Input, + spec: &'x StoreSpec, +} + +/// Taken from crate `yz-string-utils`. +fn get_offset_of<T>(whole_buffer: &T, part: &T) -> usize +where + T: AsRef<[u8]> + ?Sized, +{ + // NOTE: originally I wanted to use offset_from() here once it's stable, + // but according to https://github.com/rust-lang/rust/issues/41079#issuecomment-657163887 + // this would be UB in cases where the code below isn't. + part.as_ref().as_ptr() as usize - whole_buffer.as_ref().as_ptr() as usize +} + +impl<'x, Input> StoreRefScanner<'x, Input> +where + Input: ScannerInput + 'x, +{ + pub fn new(input: Input, spec: &'x StoreSpec) -> Self { + for i in [&spec.valid_hashbytes, &spec.valid_restbytes] { + for j in [b'\0', b' ', b'\t', b'\n', b'/', b'\\'] { + assert!(!i.contains(j)); + } + } + Self { input, spec } + } +} + +impl<'x, Input: 'x> Iterator for StoreRefScanner<'x, Input> +where + Input: ScannerInput + 'x, +{ + type Item = Input; + + fn next(&mut self) -> Option<Input> { + let empty_path = camino::Utf8Path::new(""); + let hbl: usize = self.spec.hashbytes_len.into(); + while !self.input.as_ref().is_empty() { + if self.spec.path_to_store != empty_path { + let p2sas = self.spec.path_to_store.as_str(); + if self.input.as_ref().starts_with(p2sas.as_bytes()) { + self.input.split_to(p2sas.len()); + } else { + self.input.split_to(1); + continue; + } + } + let hsep = matches!(self.input.as_ref().iter().next(), Some(b'/') | Some(b'\\')); + self.input.split_to(1); + if hsep && self.spec.check_rest(self.input.as_ref()) { + // we have found a valid hash + // rest contains the store basename and all following components + // now let's search for the end + // and then cut off possible following components after the basename + let rlen = self + .input + .as_ref() + .iter() + .enumerate() + .take(BASENAME_MAXLEN) + .skip(hbl) + .find(|&(_, &i)| !self.spec.valid_restbytes.contains(i)) + .map(|(eosp, _)| eosp) + .unwrap_or(core::cmp::min(BASENAME_MAXLEN, self.input.as_ref().len())); + return Some(self.input.split_to(rlen)); + } + } + self.input.finish(); + None + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn simple_nix2() { + let drv: &[u8] = br#" + Derive([("out","","r:sha256","")],[("/nix/store/2ax7bvjdfkzim69q957i0jlg0nvmapg0-util-linux-2.37.2.drv",["dev"]),("/nix/store/6b55ssmh8pzqsc4q4kw1yl3kqvr4fvqj-bash-5.1-p12.drv",["out"]),("/nix/store/fp2vx24kczlzv84avds28wyzsmrn8kyv-source.drv",["out"]),("/nix/store/s6c2lm5hpsvdwnxq9y1g3ngncghjzc3k-stdenv-linux.drv",["out"]),("/nix/store/xlnzpf4mzghi8vl0krabrgcbnqk5qjf3-pkg-config-wrapper-0.29.2.drv",["out"])],["/nix/store/03sl46khd8gmjpsad7223m32ma965vy9-fix-static.patch","/nix/store/2q3z7587yhlz0i2xvfvvap42zk5carlv-bcache-udev-modern.patch","/nix/store/9krlzvny65gdc8s7kpb6lkx8cd02c25b-default-builder.sh"],"x86_64-linux","/0g15yibzzi3rmw29gqlbms05x9dbghbvh61v1qggydvmzh3bginw/bin/bash",["-e","/nix/store/9krlzvny65gdc8s7kpb6lkx8cd02c25b-default-builder.sh"],[("buildInputs","/0sdk1r4l43yw4g6lmqdhd92vhdfhlwz3m76jxzvzsqsv63czw2km"),("builder","/0g15yibzzi3rmw29gqlbms05x9dbghbvh61v1qggydvmzh3bginw/bin/bash"),("configureFlags",""),("depsBuildBuild",""),("depsBuildBuildPropagated",""),("depsBuildTarget",""),("depsBuildTargetPropagated",""),("depsHostHost",""),("depsHostHostPropagated",""),("depsTargetTarget",""),("depsTargetTargetPropagated",""),("doCheck",""),("doInstallCheck",""),("makeFlags","PREFIX=/1rz4g4znpzjwh1xymhjpm42vipw92pr73vdgl6xs1hycac8kf2n9 UDEVLIBDIR=/1rz4g4znpzjwh1xymhjpm42vipw92pr73vdgl6xs1hycac8kf2n9/lib/udev/"),("name","bcache-tools-1.0.7"),("nativeBuildInputs","/1kw0rwgdyq9q69wmmsa5d2kap6p52b0yldbzi4w17bhcq5g5cp2f"),("out","/1rz4g4znpzjwh1xymhjpm42vipw92pr73vdgl6xs1hycac8kf2n9"),("outputHashAlgo","sha256"),("outputHashMode","recursive"),("outputs","out"),("patches","/nix/store/2q3z7587yhlz0i2xvfvvap42zk5carlv-bcache-udev-modern.patch /nix/store/03sl46khd8gmjpsad7223m32ma965vy9-fix-static.patch"),("pname","bcache-tools"),("preBuild","sed -e \"s|/bin/sh|/0g15yibzzi3rmw29gqlbms05x9dbghbvh61v1qggydvmzh3bginw/bin/sh|\" -i *.rules\n"),("preInstall","mkdir -p \"$out/sbin\" \"$out/lib/udev/rules.d\" \"$out/share/man/man8\"\n"),("prePatch","sed -e \"/INSTALL.*initramfs\\/hook/d\" \\\n -e \"/INSTALL.*initcpio\\/install/d\" \\\n -e \"/INSTALL.*dracut\\/module-setup.sh/d\" \\\n -e \"s/pkg-config/$PKG_CONFIG/\" \\\n -i Makefile\n"),("propagatedBuildInputs",""),("propagatedNativeBuildInputs",""),("src","/nix/store/6izcafvfcbz19chi7hl20834g0fa043n-source"),("stdenv","/01ncyv8bxibj0imgfvmxgqy648n697bachil6aw6i46g1jk0bbds"),("strictDeps",""),("system","x86_64-linux"),("version","1.0.7")]) + "#; + // we convert everything into strings because it is way easier to compare elements in error messages + let refs: Vec<&str> = StoreRefScanner::new(drv, &*SPEC_DFL_NIX2) + .map(|i| core::str::from_utf8(i).unwrap()) + .collect(); + let refs_expect: Vec<&[u8]> = vec![ + b"2ax7bvjdfkzim69q957i0jlg0nvmapg0-util-linux-2.37.2.drv", + b"6b55ssmh8pzqsc4q4kw1yl3kqvr4fvqj-bash-5.1-p12.drv", + b"fp2vx24kczlzv84avds28wyzsmrn8kyv-source.drv", + b"s6c2lm5hpsvdwnxq9y1g3ngncghjzc3k-stdenv-linux.drv", + b"xlnzpf4mzghi8vl0krabrgcbnqk5qjf3-pkg-config-wrapper-0.29.2.drv", + b"03sl46khd8gmjpsad7223m32ma965vy9-fix-static.patch", + b"2q3z7587yhlz0i2xvfvvap42zk5carlv-bcache-udev-modern.patch", + b"9krlzvny65gdc8s7kpb6lkx8cd02c25b-default-builder.sh", + b"9krlzvny65gdc8s7kpb6lkx8cd02c25b-default-builder.sh", + b"2q3z7587yhlz0i2xvfvvap42zk5carlv-bcache-udev-modern.patch", + b"03sl46khd8gmjpsad7223m32ma965vy9-fix-static.patch", + b"6izcafvfcbz19chi7hl20834g0fa043n-source", + ]; + let refs_expect: Vec<&str> = refs_expect + .into_iter() + .map(|i| core::str::from_utf8(i).unwrap()) + .collect(); + assert_eq!(refs, refs_expect); + } + + #[test] + fn simple_yzix1() { + // I haven't yet produced any yzix derivation which included /yzixs absolute paths... + let fake: &[u8] = br#" + /yzixs/4Zx1PBoft1YyAuKdhjAY1seZFHloxQ+8voHQRkRMuys: ASCII text + /yzixs/dNE3yogD4JHKHzNa2t3jQMZddT8wjqlMDB0naDIFo0A: ASCII text + /yzixs/FMluSVOHLc4bxX7F4lBCXafNljBnDn+rAM5HzG7k8LI: unified diff output, ASCII text + /yzixs/g2G3GRL87hGEdw9cq2BZWqDQP_HeHSPRLbJ9P9KH+HI: unified diff output, ASCII text + /yzixs/H08Av1ZAONwFdzVLpFQm0Sc0dvyk0sbnk82waoBig7I: ASCII text + /yzixs/IndARQp+gaGDLS3K+PeyXdaRqAcCyS3EIbRXkkYjC94: unified diff output, ASCII text + /yzixs/IrLPnbkEolTAuWRxkXpuvVs6Imb1iB6wUJcI+fxWwkU: POSIX shell script, ASCII text executable + /yzixs/JsS_H3n3TSh2R6fiIzgOPZdjSmRkV71vGxstJJKPmr4: unified diff output, ASCII text + /yzixs/LZ6pQh1x8DRxZ2IYzetBRS4LuE__IXFjpOfQPxHVwpw: unified diff output, ASCII text + /yzixs/mEi2RPep9daRs0JUvwt1JsDfgYSph5sH_+_ihwn8IGQ: ASCII text + /yzixs/nd4DyljinP3auDMHL_LrpsRJkWQpSHQK2jqtyyzWcBA: POSIX shell script, ASCII text executable + /yzixs/nzpaknF0_ONSHtd0i_e1E3pkLF1QPeJQhAB7x9Ogo_M: unified diff output, ASCII text + /yzixs/UZ3uzVUUMC1gKGLw6tg_aLFwoFrJedXB3xbhEgQOaiY: unified diff output, ASCII text + /yzixs/VKyXxKTXsDGxYJ24YgbvCc1bZkA5twp3TC+Gbi4Kwd8: unified diff output, ASCII text + /yzixs/VPJMl8O1xkc1LsJznpoQrCrQO0Iy+ODCPsgoUBLiRZc: unified diff output, ASCII text + /yzixs/W6r1ow001ASHRj+gtRfyj9Fb_gCO_pBztX8WhYXVdIc: unified diff output, ASCII text + /yzixs/xvwEcXIob_rQynUEtQiQbwaDXEobTVKEGaBMir9oH9k: unified diff output, ASCII text + /yzixs/ZPvQbRJrtyeSITvW3FUZvw99hhNOO3CFqGgmWgScxcg: ASCII text + "#; + let refs: Vec<&str> = StoreRefScanner::new(fake, &*SPEC_DFL_YZIX1) + .map(|i| core::str::from_utf8(i).unwrap()) + .collect(); + let refs_expect: Vec<&[u8]> = vec![ + b"4Zx1PBoft1YyAuKdhjAY1seZFHloxQ+8voHQRkRMuys", + b"dNE3yogD4JHKHzNa2t3jQMZddT8wjqlMDB0naDIFo0A", + b"FMluSVOHLc4bxX7F4lBCXafNljBnDn+rAM5HzG7k8LI", + b"g2G3GRL87hGEdw9cq2BZWqDQP_HeHSPRLbJ9P9KH+HI", + b"H08Av1ZAONwFdzVLpFQm0Sc0dvyk0sbnk82waoBig7I", + b"IndARQp+gaGDLS3K+PeyXdaRqAcCyS3EIbRXkkYjC94", + b"IrLPnbkEolTAuWRxkXpuvVs6Imb1iB6wUJcI+fxWwkU", + b"JsS_H3n3TSh2R6fiIzgOPZdjSmRkV71vGxstJJKPmr4", + b"LZ6pQh1x8DRxZ2IYzetBRS4LuE__IXFjpOfQPxHVwpw", + b"mEi2RPep9daRs0JUvwt1JsDfgYSph5sH_+_ihwn8IGQ", + b"nd4DyljinP3auDMHL_LrpsRJkWQpSHQK2jqtyyzWcBA", + b"nzpaknF0_ONSHtd0i_e1E3pkLF1QPeJQhAB7x9Ogo_M", + b"UZ3uzVUUMC1gKGLw6tg_aLFwoFrJedXB3xbhEgQOaiY", + b"VKyXxKTXsDGxYJ24YgbvCc1bZkA5twp3TC+Gbi4Kwd8", + b"VPJMl8O1xkc1LsJznpoQrCrQO0Iy+ODCPsgoUBLiRZc", + b"W6r1ow001ASHRj+gtRfyj9Fb_gCO_pBztX8WhYXVdIc", + b"xvwEcXIob_rQynUEtQiQbwaDXEobTVKEGaBMir9oH9k", + b"ZPvQbRJrtyeSITvW3FUZvw99hhNOO3CFqGgmWgScxcg", + ]; + let refs_expect: Vec<&str> = refs_expect + .into_iter() + .map(|i| core::str::from_utf8(i).unwrap()) + .collect(); + assert_eq!(refs, refs_expect); + } + + proptest::proptest! { + #[test] + fn nocrash_nix2(s: Vec<u8>) { + let _ = StoreRefScanner::new(&s[..], &*SPEC_DFL_NIX2).count(); + } + + #[test] + fn nocrash_yzix1(s: Vec<u8>) { + let _ = StoreRefScanner::new(&s[..], &*SPEC_DFL_YZIX1).count(); + } + } +} diff --git a/users/zseri/store-ref-scanner/src/spec.rs b/users/zseri/store-ref-scanner/src/spec.rs new file mode 100644 index 000000000000..034779e8e8dc --- /dev/null +++ b/users/zseri/store-ref-scanner/src/spec.rs @@ -0,0 +1,46 @@ +use crate::hbm::HalfBytesMask; +use camino::Utf8PathBuf; +use once_cell::sync::Lazy; + +pub struct StoreSpec { + /// path to store without trailing slash + pub path_to_store: Utf8PathBuf, + + /// compressed map of allowed ASCII characters in hash part + pub valid_hashbytes: HalfBytesMask, + + /// compressed map of allowed ASCII characters in part after hash + pub valid_restbytes: HalfBytesMask, + + /// exact length of hash part of store paths + pub hashbytes_len: u8, +} + +impl StoreSpec { + pub(crate) fn check_rest(&self, rest: &[u8]) -> bool { + let hbl = self.hashbytes_len.into(); + rest.iter() + .take(hbl) + .take_while(|&&i| self.valid_hashbytes.contains(i)) + .count() + == hbl + } +} + +pub static SPEC_DFL_NIX2: Lazy<StoreSpec> = Lazy::new(|| StoreSpec { + path_to_store: "/nix/store".into(), + valid_hashbytes: HalfBytesMask::B32_REVSHA256, + valid_restbytes: HalfBytesMask::from_bytes( + b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+-._?=", + ), + hashbytes_len: 32, +}); + +pub static SPEC_DFL_YZIX1: Lazy<StoreSpec> = Lazy::new(|| StoreSpec { + path_to_store: "/yzixs".into(), + valid_hashbytes: HalfBytesMask::B64_BLAKE2B256, + valid_restbytes: HalfBytesMask::from_bytes( + b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+-._?=", + ), + hashbytes_len: 43, +}); |