[GBL] Add buffer overlapping check
Add itetools crate. It is used in testing.
Add 'is_overlap()' function to check provided buffers validity.
Bug: 312608785
Test: ./tools/bazel test @gbl//tests --extra_toolchains=@gbl//toolchain:all --verbose_failures
Change-Id: Ia09b5256c0be5fac9719c26fa97956c15dd4cbbe
diff --git a/gbl/integration/aosp_u-boot-mainline/workspace.bzl b/gbl/integration/aosp_u-boot-mainline/workspace.bzl
index 307d84d..5d5b653 100644
--- a/gbl/integration/aosp_u-boot-mainline/workspace.bzl
+++ b/gbl/integration/aosp_u-boot-mainline/workspace.bzl
@@ -21,7 +21,7 @@
load("@gbl//toolchain:gbl_workspace_util.bzl", "android_rust_prebuilts", "gbl_llvm_prebuilts")
load("@kernel_toolchain_info//:dict.bzl", "CLANG_VERSION")
-def rust_crate_build_file(name, deps = [], features = [], rustc_flags = []):
+def rust_crate_build_file(name, crate_name = "", deps = [], features = [], rustc_flags = []):
"""Generate BUILD file content for a rust crate
This helper is suitable for crates that have straightforward build rules. Specifically, the
@@ -30,6 +30,7 @@
Args:
name (String): name of the rust_library target.
+ crate_name (String): name of the rust_library crate, same as name by default.
deps (List of strings): The `deps` field.
features (List of strings): The `features` field.
rustc_flags (List of strings): The `rustc_flags` field.
@@ -37,6 +38,7 @@
Returns:
A string for the BUILD file content.
"""
+ crate_name = name if len(crate_name) == 0 else crate_name
deps = "[{}]".format(",".join(["\"{}\"".format(ele) for ele in deps]))
features = "[{}]".format(",".join(["\"{}\"".format(ele) for ele in features]))
rustc_flags = "[{}]".format(",".join(["\"{}\"".format(ele) for ele in rustc_flags]))
@@ -45,6 +47,7 @@
rust_library(
name = \"{}\",
+ crate_name = \"{}\",
srcs = glob(["**/*.rs"]),
crate_features = {},
edition = "2021",
@@ -52,7 +55,7 @@
visibility = ["//visibility:public"],
deps = {},
)
-""".format(name, features, rustc_flags, deps)
+""".format(name, crate_name, features, rustc_flags, deps)
def define_gbl_workspace(name = None):
"""Set up worksapce dependencies for GBL
@@ -198,6 +201,48 @@
)
native.new_local_repository(
+ name = "itertools",
+ path = "external/rust/crates/itertools",
+ build_file_content = rust_crate_build_file(
+ "itertools",
+ deps = ["@either"],
+ features = ["default", "use_std", "use_alloc"],
+ rustc_flags = ["-A", "dead_code"],
+ ),
+ )
+
+ native.new_local_repository(
+ name = "itertools_noalloc",
+ path = "external/rust/crates/itertools",
+ build_file_content = rust_crate_build_file(
+ "itertools_noalloc",
+ crate_name = "itertools",
+ features = [],
+ deps = ["@either_noalloc"],
+ rustc_flags = ["-A", "dead_code"],
+ ),
+ )
+
+ native.new_local_repository(
+ name = "either",
+ path = "external/rust/crates/either",
+ build_file_content = rust_crate_build_file(
+ "either",
+ features = ["default", "use_std"],
+ ),
+ )
+
+ native.new_local_repository(
+ name = "either_noalloc",
+ path = "external/rust/crates/either",
+ build_file_content = rust_crate_build_file(
+ "either_noalloc",
+ crate_name = "either",
+ features = [],
+ ),
+ )
+
+ native.new_local_repository(
name = "smoltcp",
path = "external/rust/crates/smoltcp",
build_file = "@gbl//smoltcp:BUILD.smoltcp.bazel",
diff --git a/gbl/libgbl/BUILD b/gbl/libgbl/BUILD
index df19be0..0555d47 100644
--- a/gbl/libgbl/BUILD
+++ b/gbl/libgbl/BUILD
@@ -20,6 +20,7 @@
["**/*.rs"],
exclude = ["tests/**/*.rs"],
),
+ aliases = {"@itertools_noalloc": "itertools_noalloc"},
edition = "2021",
visibility = ["//visibility:public"],
deps = [
@@ -31,6 +32,7 @@
"@gbl//libsafemath",
"@gbl//libstorage",
"@gbl//third_party/libzbi",
+ "@itertools_noalloc",
"@spin",
"@static_assertions",
"@zerocopy",
@@ -39,6 +41,7 @@
rust_test(
name = "libgbl_test",
+ aliases = {"@itertools_noalloc": "itertools_noalloc"},
compile_data = ["@gbl//libstorage/test:test_data"],
crate = ":libgbl",
crate_features = ["uuid"],
@@ -56,6 +59,8 @@
"@avb//:avb_test",
"@gbl//libavb:sysdeps",
"@gbl//libstorage:libstorage_testlib",
+ "@itertools",
+ "@itertools_noalloc",
"@static_assertions",
"@uuid",
],
diff --git a/gbl/libgbl/src/error.rs b/gbl/libgbl/src/error.rs
index fcc4a1a..acfe8be 100644
--- a/gbl/libgbl/src/error.rs
+++ b/gbl/libgbl/src/error.rs
@@ -42,6 +42,8 @@
/// AvbOps were already borrowed. This would happen on second `load_and_verify_image()` call
/// unless `reuse()` is called before.
AvbOpsBusy,
+ /// Buffers overlap and can cause undefined behavior and data corruption.
+ BufferOverlap,
}
impl Display for Error {
@@ -55,6 +57,7 @@
Error::OperationProhibited => write!(f, "Operation is prohibited"),
Error::Internal => write!(f, "Internal error"),
Error::AvbOpsBusy => write!(f, "AvbOps were already borrowed"),
+ Error::BufferOverlap => write!(f, "Buffers overlap"),
}
}
}
diff --git a/gbl/libgbl/src/lib.rs b/gbl/libgbl/src/lib.rs
index dc8912e..c170e4e 100644
--- a/gbl/libgbl/src/lib.rs
+++ b/gbl/libgbl/src/lib.rs
@@ -47,6 +47,7 @@
pub mod error;
pub mod fastboot;
pub mod ops;
+mod overlap;
/// The 'slots' module, containing types and traits for
/// querying and modifying slotted boot behavior.
@@ -63,6 +64,7 @@
};
use ops::GblUtils;
+use overlap::is_overlap;
// TODO: b/312607649 - Replace placeholders with actual structures: https://r.android.com/2721974, etc
/// TODO: b/312607649 - placeholder type
@@ -504,6 +506,16 @@
let vendor_boot_image = vendor_boot_image.ok_or(Error::MissingImage)?;
let init_boot_image = init_boot_image.ok_or(Error::MissingImage)?;
+ if is_overlap(&[
+ boot_image.0,
+ vendor_boot_image.0,
+ init_boot_image.0,
+ &ramdisk.0,
+ kernel_load_buffer,
+ ]) {
+ return Err(IntegrationError::GblNativeError(Error::BufferOverlap));
+ }
+
let info_struct = self.unpack_boot_image(&boot_image, Some(boot_target))?;
let kernel_image = self.kernel_load(&info_struct, boot_image, kernel_load_buffer)?;
diff --git a/gbl/libgbl/src/ops.rs b/gbl/libgbl/src/ops.rs
index 6063c4c..20e04c6 100644
--- a/gbl/libgbl/src/ops.rs
+++ b/gbl/libgbl/src/ops.rs
@@ -16,8 +16,6 @@
//!
#[cfg(feature = "alloc")]
extern crate alloc;
-#[cfg(test)]
-extern crate static_assertions;
use crate::error::{Error, Result as GblResult};
#[cfg(feature = "alloc")]
diff --git a/gbl/libgbl/src/overlap.rs b/gbl/libgbl/src/overlap.rs
new file mode 100644
index 0000000..20d129d
--- /dev/null
+++ b/gbl/libgbl/src/overlap.rs
@@ -0,0 +1,121 @@
+// Copyright 2024, The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//! Helper functions to verify image buffers
+use core::cmp::{max, min};
+extern crate itertools_noalloc;
+use itertools_noalloc::Itertools;
+
+/// Check if provided buffers overlap in any way.
+///
+/// Note that zero length buffer is considered to contain no elements.
+/// And would not overlap with any other buffer.
+///
+/// # Args
+///
+/// * `buffers`: slice of buffers to verify
+///
+/// # Returns
+///
+/// * true: if any of the buffers have common elements
+/// * false: if there are no common elements in buffers
+pub fn is_overlap(buffers: &[&[u8]]) -> bool {
+ // Compare each with each since we can't use alloc and sort buffers.
+ // Since the number of buffers we expect is not big, O(n^2) complexity will do.
+ //
+ // Note: this is nice way to find out if 2 ranges overlap:
+ // max(a_start, b_start) > min(a_end, b_end)) -> no overlap
+ buffers
+ .iter()
+ .filter(|buffer| !buffer.is_empty())
+ .map(|slice: &&[u8]| (slice.as_ptr(), slice.last_chunk::<1>().unwrap().as_ptr()))
+ .tuple_combinations()
+ .any(|((a_start, a_end), (b_start, b_end))| !(max(a_start, b_start) > min(a_end, b_end)))
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use itertools::Itertools;
+
+ // Creates slice of specified range: [first; last)
+ // Max range value is SIZE = 64;
+ fn get_range(first: usize, last: usize) -> &'static [u8] {
+ const SIZE: usize = 64;
+ assert!(first < SIZE);
+ assert!(last <= SIZE);
+ static BUFFER: &'static [u8; SIZE] = &[0; SIZE];
+ &BUFFER[first..last]
+ }
+
+ // Check if ranges overlap, testing all permutations
+ fn check_overlap(ranges_set: &[(usize, usize)]) -> bool {
+ ranges_set.iter().permutations(ranges_set.len()).all(|ranges| {
+ let ranges_slices: Vec<&[u8]> =
+ ranges.iter().map(|&(start, end)| get_range(*start, *end)).collect();
+ is_overlap(&ranges_slices)
+ })
+ }
+
+ // Check if ranges don't overlap, testing all permutations
+ fn check_not_overlap(ranges_set: &[(usize, usize)]) -> bool {
+ ranges_set.iter().permutations(ranges_set.len()).all(|ranges| {
+ let ranges_slices: Vec<&[u8]> =
+ ranges.iter().map(|&(start, end)| get_range(*start, *end)).collect();
+ !is_overlap(&ranges_slices)
+ })
+ }
+
+ #[test]
+ fn test_is_overlap_false() {
+ assert!(check_not_overlap(&[(10, 15), (20, 25), (30, 35)]));
+ }
+
+ #[test]
+ fn test_is_overlap_true() {
+ assert!(check_overlap(&[(10, 19), (15, 25)]));
+ }
+
+ #[test]
+ fn test_is_overlap_included() {
+ assert!(check_overlap(&[(10, 11), (10, 11)]));
+ assert!(check_overlap(&[(10, 12), (10, 12)]));
+ assert!(check_overlap(&[(10, 13), (11, 12)]));
+ assert!(check_overlap(&[(10, 14), (11, 13)]));
+ assert!(check_overlap(&[(10, 20), (15, 18)]));
+ assert!(check_overlap(&[(10, 20), (11, 19), (12, 18), (13, 17)]));
+ }
+
+ #[test]
+ fn test_is_overlap_touching() {
+ assert!(check_not_overlap(&[(10, 20), (20, 30), (30, 31)]));
+ }
+
+ #[test]
+ fn test_is_overlap_last_element() {
+ assert!(check_overlap(&[(10, 20), (19, 21)]));
+ }
+
+ #[test]
+ fn test_is_overlap_short() {
+ assert!(check_not_overlap(&[(10, 11), (11, 12), (12, 13)]));
+ }
+
+ #[test]
+ fn test_is_overlap_empty_slice() {
+ assert!(check_not_overlap(&[]));
+ assert!(check_not_overlap(&[(10, 10)]));
+ assert!(check_not_overlap(&[(10, 20), (10, 10), (20, 30), (11, 11), (23, 23)]));
+ }
+}
