linux-kernel - Re: [PATCH 5/5] rust: alloc: add Vec::retain

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <CAJ-ks9k=SxS_zAATadm8SZkfcY2OciYNaty3=WEs2iv5nFJRyA@mail.gmail.com>
Date: Fri, 21 Mar 2025 11:24:30 -0400
From: Tamir Duberstein <tamird@...il.com>
To: Alice Ryhl <aliceryhl@...gle.com>
Cc: Danilo Krummrich <dakr@...nel.org>, rust-for-linux@...r.kernel.org, 
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH 5/5] rust: alloc: add Vec::retain

On Thu, Mar 20, 2025 at 9:57 AM Alice Ryhl <aliceryhl@...gle.com> wrote:
>
> This adds a common Vec method called `retain` that removes all elements
> that don't match a certain condition. Rust Binder uses it to find all
> processes that match a given pid.
>
> The stdlib retain method takes &T rather than &mut T and has a separate
> retain_mut for the &mut T case. However, this is considered an API
> mistake that can't be fixed now due to backwards compatibility. There's
> no reason for us to repeat that mistake.
>
> To verify the correctness of this implementation, you may run the
> following program in userspace:
>
>     fn retain<T>(vec: &mut Vec<T>, f: impl Fn(&T) -> bool) {
>         let mut num_kept = 0;
>         let mut next_to_check = 0;
>         while let Some(to_check) = vec.get_mut(next_to_check) {
>             if f(to_check) {
>                 vec.swap(num_kept, next_to_check);
>                 num_kept += 1;
>             }
>             next_to_check += 1;
>         }
>         vec.truncate(num_kept);
>     }
>
>     fn verify(c: &[bool]) {
>         let mut vec1: Vec<usize> = (0..c.len()).collect();
>         let mut vec2: Vec<usize> = (0..c.len()).collect();
>
>         vec1.retain(|i| c[*i]);
>         retain(&mut vec2, |i| c[*i]);
>
>         assert_eq!(vec1, vec2);
>     }
>
>     // Used to loop through all 2^n bit vectors.
>     fn add(value: &mut [bool]) -> bool {
>         let mut carry = true;
>         for v in value {
>             let new_v = carry != *v;
>             carry = carry && *v;
>             *v = new_v;
>         }
>         carry
>     }
>
>     fn main() {
>         for len in 0..10 {
>             let mut retain = vec![false; len];
>             while !add(&mut retain) {
>                 verify(&retain);
>             }
>         }
>         println!("ok!");
>     }

Now that we have kunit in rust-next, should we make this into a test?