From patchwork Fri Feb 24 09:11:50 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Asahi Lina X-Patchwork-Id: 61200 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7300:7b8e:b0:9f:8c76:fea4 with SMTP id j14csp1211290dyk; Fri, 24 Feb 2023 01:14:07 -0800 (PST) X-Google-Smtp-Source: AK7set8R3ySqcXjziptAfrd5lc0TNucl2M7hgJ0dRihgsD41lUrrZpCHwCBMkb4KMYybILS/aNLz X-Received: by 2002:a62:7948:0:b0:5a8:482f:c32e with SMTP id u69-20020a627948000000b005a8482fc32emr16577052pfc.27.1677230047689; Fri, 24 Feb 2023 01:14:07 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1677230047; cv=none; d=google.com; s=arc-20160816; b=KoolWOJe20CVffvzocbjk9moPpkx1XucudBTvs81OrsCyazGgjGLCtt7IeYHhmZ6hZ O/YdFjKOHuVJXu3mkNXOPV9rDevB/clqcnDvyqQToqoaqviNmBoaKVhbwD1ccoHCm4GA vzA49Z0+fstK3CwHbBaR/adLzyNfMwT/d36XLuKQcMRqioetChWYoq+V/QtHGUn/tV4b bDmEiuvRaPlLhA2aw36A3NSd6yM734xP86jFEBybrtyOWJEUz/gC3eFEzqVdtZzXzK/s jOpngsBPzzOXbok+LRS7PcRlxS1ZgrUgWx+AV0vSxQhFcnsK7eCPRXtOlvXFtLbNB338 2UuA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:cc:to:in-reply-to:references:message-id :content-transfer-encoding:mime-version:subject:date:from :dkim-signature; bh=qTf+y+biogpsjCxSet3dcgEQ5As+CuBJIWvbNO55CIA=; b=FArp8SA19gl8qQk3Yd/h+OhMtFh8PVWoAJk/jn8m1NlR+2n4UjJLR972Owcwa4unqC cCzrwb9AZbJwIRPOUZO4sMRAlvXB/sPdl12dBZzrPEnyHSL7zE2KFp9LAyz3ko7/muwq vfLSyYeTjNiD+y0BfkdtBssAFTEaoXgP3GkD2HkqYUb55SXNdGyewx+m5vqcGKOQfpsR 58XbkMlcL/ZTA6zZ20/TXpyn07IV4nCliMwy9w/hUznN0nLwwNLwMoHJ7/5M1Z7V0uc9 TA18Z4F53tG2LsPeUF7xhKFUNuRneDkakt2cU101e2mJM1HqSWWsj6rqUFIAZQ6tuTv/ hOlw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@asahilina.net header.s=default header.b=UQisdBOX; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=asahilina.net Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id f4-20020a056a00238400b005a862e1759fsi29988274pfc.329.2023.02.24.01.13.54; Fri, 24 Feb 2023 01:14:07 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; dkim=pass header.i=@asahilina.net header.s=default header.b=UQisdBOX; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=asahilina.net Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229877AbjBXJM0 (ORCPT + 99 others); Fri, 24 Feb 2023 04:12:26 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:54310 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229810AbjBXJMR (ORCPT ); Fri, 24 Feb 2023 04:12:17 -0500 Received: from mail.marcansoft.com (marcansoft.com [212.63.210.85]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A210965CFD; Fri, 24 Feb 2023 01:12:14 -0800 (PST) Received: from [127.0.0.1] (localhost [127.0.0.1]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) (Authenticated sender: linasend@asahilina.net) by mail.marcansoft.com (Postfix) with ESMTPSA id 2D2ED3FA55; Fri, 24 Feb 2023 09:12:09 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=asahilina.net; s=default; t=1677229933; bh=rySOe8C+EOHBcINSIJX8QO1nEpuKvnx7nO+s+ewSOfE=; h=From:Date:Subject:References:In-Reply-To:To:Cc; b=UQisdBOXr/aBVNREW1ajga0fx1kylmLydkZ1A6SEte7+DuX+CrAhj86MBg8ziguPN tlSD413VcSsYZSOzp8cuguz+Q7VF3FJ8Aizf6x+KaegXXEe6CX2M7mZGbBMJPnAZv2 M1FuONlXRamn5MOLK5/GKKnUUAI7KrYamU1I9knhfTdMjr6HpgvpRvBbcmq1QJ5Qmw uscO69ncOFWcw3aBaQa7uc8ma1Kta1viLwIjr7uWrzAT7Tpy38OqM1WXxDVupQctH3 kG3zAef3n5Lpym14EiG6jhPh2ZlhVPd4+D6Kf5yBEUZYHi6v5o+Xe9GHtwcglvRd7i QXioyjHFpZP3g== From: Asahi Lina Date: Fri, 24 Feb 2023 18:11:50 +0900 Subject: [PATCH 4/4] rust: alloc: vec: Add some try_* methods we need MIME-Version: 1.0 Message-Id: <20230224-rust-vec-v1-4-733b5b5a57c5@asahilina.net> References: <20230224-rust-vec-v1-0-733b5b5a57c5@asahilina.net> In-Reply-To: <20230224-rust-vec-v1-0-733b5b5a57c5@asahilina.net> To: Miguel Ojeda , Alex Gaynor , Wedson Almeida Filho , Boqun Feng , Gary Guo , =?utf-8?q?Bj=C3=B6rn_Roy_Baron?= Cc: linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, asahi@lists.linux.dev, Asahi Lina X-Mailer: b4 0.12.0 X-Developer-Signature: v=1; a=ed25519-sha256; t=1677229917; l=12257; i=lina@asahilina.net; s=20230221; h=from:subject:message-id; bh=D79jXdo5FTKXLLha+LXra032tDEtF09O0Gra2CyUwtA=; b=ESmxTKHa/YudfQcXi8DOpmJs4uMj/rvNEuScGm/xTEWyhQ0wLGK2y+uj+btCcNtUVBCPaSh1Y u/gx1Ds7UTZBnoVDTkvg1G0w/0yaf5as1qym/tCZHf4GL56awYC/Z4Z X-Developer-Key: i=lina@asahilina.net; a=ed25519; pk=Qn8jZuOtR1m5GaiDfTrAoQ4NE1XoYVZ/wmt5YtXWFC4= X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1758703174024719503?= X-GMAIL-MSGID: =?utf-8?q?1758703174024719503?= From: Miguel Ojeda Add some missing fallible methods that we need. They are all marked as: #[stable(feature = "kernel", since = "1.0.0")] for easy identification. Lina: Extracted from commit 487d7578bd03 ("rust: alloc: add some `try_*` methods we need") in rust-for-linux/rust. Signed-off-by: Miguel Ojeda Signed-off-by: Asahi Lina --- rust/alloc/vec/mod.rs | 137 +++++++++++++++++++++++++++++++++++++++++- rust/alloc/vec/spec_extend.rs | 83 +++++++++++++++++++++++++ 2 files changed, 217 insertions(+), 3 deletions(-) diff --git a/rust/alloc/vec/mod.rs b/rust/alloc/vec/mod.rs index f77c7368d534..feb9262b5029 100644 --- a/rust/alloc/vec/mod.rs +++ b/rust/alloc/vec/mod.rs @@ -122,10 +122,8 @@ use self::spec_from_elem::SpecFromElem; #[cfg(not(no_global_oom_handling))] mod spec_from_elem; -#[cfg(not(no_global_oom_handling))] use self::set_len_on_drop::SetLenOnDrop; -#[cfg(not(no_global_oom_handling))] mod set_len_on_drop; #[cfg(not(no_global_oom_handling))] @@ -149,7 +147,8 @@ mod spec_from_iter; #[cfg(not(no_global_oom_handling))] use self::spec_extend::SpecExtend; -#[cfg(not(no_global_oom_handling))] +use self::spec_extend::TrySpecExtend; + mod spec_extend; /// A contiguous growable array type, written as `Vec`, short for 'vector'. @@ -1919,6 +1918,17 @@ impl Vec { self.len += count; } + /// Tries to append elements to `self` from other buffer. + #[inline] + unsafe fn try_append_elements(&mut self, other: *const [T]) -> Result<(), TryReserveError> { + let count = unsafe { (*other).len() }; + self.try_reserve(count)?; + let len = self.len(); + unsafe { ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(len), count) }; + self.len += count; + Ok(()) + } + /// Removes the specified range from the vector in bulk, returning all /// removed elements as an iterator. If the iterator is dropped before /// being fully consumed, it drops the remaining removed elements. @@ -2340,6 +2350,45 @@ impl Vec { } } + /// Tries to resize the `Vec` in-place so that `len` is equal to `new_len`. + /// + /// If `new_len` is greater than `len`, the `Vec` is extended by the + /// difference, with each additional slot filled with `value`. + /// If `new_len` is less than `len`, the `Vec` is simply truncated. + /// + /// This method requires `T` to implement [`Clone`], + /// in order to be able to clone the passed value. + /// If you need more flexibility (or want to rely on [`Default`] instead of + /// [`Clone`]), use [`Vec::resize_with`]. + /// If you only need to resize to a smaller size, use [`Vec::truncate`]. + /// + /// # Examples + /// + /// ``` + /// let mut vec = vec!["hello"]; + /// vec.try_resize(3, "world").unwrap(); + /// assert_eq!(vec, ["hello", "world", "world"]); + /// + /// let mut vec = vec![1, 2, 3, 4]; + /// vec.try_resize(2, 0).unwrap(); + /// assert_eq!(vec, [1, 2]); + /// + /// let mut vec = vec![42]; + /// let result = vec.try_resize(usize::MAX, 0); + /// assert!(result.is_err()); + /// ``` + #[stable(feature = "kernel", since = "1.0.0")] + pub fn try_resize(&mut self, new_len: usize, value: T) -> Result<(), TryReserveError> { + let len = self.len(); + + if new_len > len { + self.try_extend_with(new_len - len, ExtendElement(value)) + } else { + self.truncate(new_len); + Ok(()) + } + } + /// Clones and appends all elements in a slice to the `Vec`. /// /// Iterates over the slice `other`, clones each element, and then appends @@ -2365,6 +2414,30 @@ impl Vec { self.spec_extend(other.iter()) } + /// Tries to clone and append all elements in a slice to the `Vec`. + /// + /// Iterates over the slice `other`, clones each element, and then appends + /// it to this `Vec`. The `other` slice is traversed in-order. + /// + /// Note that this function is same as [`extend`] except that it is + /// specialized to work with slices instead. If and when Rust gets + /// specialization this function will likely be deprecated (but still + /// available). + /// + /// # Examples + /// + /// ``` + /// let mut vec = vec![1]; + /// vec.try_extend_from_slice(&[2, 3, 4]).unwrap(); + /// assert_eq!(vec, [1, 2, 3, 4]); + /// ``` + /// + /// [`extend`]: Vec::extend + #[stable(feature = "kernel", since = "1.0.0")] + pub fn try_extend_from_slice(&mut self, other: &[T]) -> Result<(), TryReserveError> { + self.try_spec_extend(other.iter()) + } + /// Copies elements from `src` range to the end of the vector. /// /// # Panics @@ -2504,6 +2577,36 @@ impl Vec { // len set by scope guard } } + + /// Try to extend the vector by `n` values, using the given generator. + fn try_extend_with>(&mut self, n: usize, mut value: E) -> Result<(), TryReserveError> { + self.try_reserve(n)?; + + unsafe { + let mut ptr = self.as_mut_ptr().add(self.len()); + // Use SetLenOnDrop to work around bug where compiler + // might not realize the store through `ptr` through self.set_len() + // don't alias. + let mut local_len = SetLenOnDrop::new(&mut self.len); + + // Write all elements except the last one + for _ in 1..n { + ptr::write(ptr, value.next()); + ptr = ptr.add(1); + // Increment the length in every step in case next() panics + local_len.increment_len(1); + } + + if n > 0 { + // We can write the last element directly without cloning needlessly + ptr::write(ptr, value.last()); + local_len.increment_len(1); + } + + // len set by scope guard + Ok(()) + } + } } impl Vec { @@ -2838,6 +2941,34 @@ impl Vec { } } + // leaf method to which various SpecFrom/SpecExtend implementations delegate when + // they have no further optimizations to apply + fn try_extend_desugared>(&mut self, mut iterator: I) -> Result<(), TryReserveError> { + // This is the case for a general iterator. + // + // This function should be the moral equivalent of: + // + // for item in iterator { + // self.push(item); + // } + while let Some(element) = iterator.next() { + let len = self.len(); + if len == self.capacity() { + let (lower, _) = iterator.size_hint(); + self.try_reserve(lower.saturating_add(1))?; + } + unsafe { + ptr::write(self.as_mut_ptr().add(len), element); + // Since next() executes user code which can panic we have to bump the length + // after each step. + // NB can't overflow since we would have had to alloc the address space + self.set_len(len + 1); + } + } + + Ok(()) + } + /// Creates a splicing iterator that replaces the specified range in the vector /// with the given `replace_with` iterator and yields the removed items. /// `replace_with` does not need to be the same length as `range`. diff --git a/rust/alloc/vec/spec_extend.rs b/rust/alloc/vec/spec_extend.rs index ade317ab96b2..94d3722b01a1 100644 --- a/rust/alloc/vec/spec_extend.rs +++ b/rust/alloc/vec/spec_extend.rs @@ -1,6 +1,7 @@ // SPDX-License-Identifier: Apache-2.0 OR MIT use crate::alloc::Allocator; +use crate::collections::{TryReserveError, TryReserveErrorKind}; use core::iter::TrustedLen; use core::ptr::{self}; use core::slice::{self}; @@ -8,10 +9,17 @@ use core::slice::{self}; use super::{IntoIter, SetLenOnDrop, Vec}; // Specialization trait used for Vec::extend +#[cfg(not(no_global_oom_handling))] pub(super) trait SpecExtend { fn spec_extend(&mut self, iter: I); } +// Specialization trait used for Vec::try_extend +pub(super) trait TrySpecExtend { + fn try_spec_extend(&mut self, iter: I) -> Result<(), TryReserveError>; +} + +#[cfg(not(no_global_oom_handling))] impl SpecExtend for Vec where I: Iterator, @@ -21,6 +29,16 @@ where } } +impl TrySpecExtend for Vec +where + I: Iterator, +{ + default fn try_spec_extend(&mut self, iter: I) -> Result<(), TryReserveError> { + self.try_extend_desugared(iter) + } +} + +#[cfg(not(no_global_oom_handling))] impl SpecExtend for Vec where I: TrustedLen, @@ -59,6 +77,39 @@ where } } +impl TrySpecExtend for Vec +where + I: TrustedLen, +{ + default fn try_spec_extend(&mut self, iterator: I) -> Result<(), TryReserveError> { + // This is the case for a TrustedLen iterator. + let (low, high) = iterator.size_hint(); + if let Some(additional) = high { + debug_assert_eq!( + low, + additional, + "TrustedLen iterator's size hint is not exact: {:?}", + (low, high) + ); + self.try_reserve(additional)?; + unsafe { + let mut ptr = self.as_mut_ptr().add(self.len()); + let mut local_len = SetLenOnDrop::new(&mut self.len); + iterator.for_each(move |element| { + ptr::write(ptr, element); + ptr = ptr.offset(1); + // NB can't overflow since we would have had to alloc the address space + local_len.increment_len(1); + }); + } + Ok(()) + } else { + Err(TryReserveErrorKind::CapacityOverflow.into()) + } + } +} + +#[cfg(not(no_global_oom_handling))] impl SpecExtend> for Vec { fn spec_extend(&mut self, mut iterator: IntoIter) { unsafe { @@ -68,6 +119,17 @@ impl SpecExtend> for Vec { } } +impl TrySpecExtend> for Vec { + fn try_spec_extend(&mut self, mut iterator: IntoIter) -> Result<(), TryReserveError> { + unsafe { + self.try_append_elements(iterator.as_slice() as _)?; + } + iterator.ptr = iterator.end; + Ok(()) + } +} + +#[cfg(not(no_global_oom_handling))] impl<'a, T: 'a, I, A: Allocator + 'a> SpecExtend<&'a T, I> for Vec where I: Iterator, @@ -78,6 +140,17 @@ where } } +impl<'a, T: 'a, I, A: Allocator + 'a> TrySpecExtend<&'a T, I> for Vec +where + I: Iterator, + T: Clone, +{ + default fn try_spec_extend(&mut self, iterator: I) -> Result<(), TryReserveError> { + self.try_spec_extend(iterator.cloned()) + } +} + +#[cfg(not(no_global_oom_handling))] impl<'a, T: 'a, A: Allocator + 'a> SpecExtend<&'a T, slice::Iter<'a, T>> for Vec where T: Copy, @@ -87,3 +160,13 @@ where unsafe { self.append_elements(slice) }; } } + +impl<'a, T: 'a, A: Allocator + 'a> TrySpecExtend<&'a T, slice::Iter<'a, T>> for Vec +where + T: Copy, +{ + fn try_spec_extend(&mut self, iterator: slice::Iter<'a, T>) -> Result<(), TryReserveError> { + let slice = iterator.as_slice(); + unsafe { self.try_append_elements(slice) } + } +}