Something went wrong. Try again.
(I'm so sorry!) Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Something went wrong. Try again.
9.6 kB · 281 lines
Rust
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282// SPDX-License-Identifier: GPL-2.0
// Copyright (C) 2025 Google LLC.
use kernel::{ page::{PAGE_MASK, PAGE_SIZE}, prelude::*, seq_file::SeqFile, seq_print, task::Pid,};
use crate::range_alloc::{DescriptorState, FreedRange, Range};
/// Keeps track of allocations in a process' mmap.////// Each process has an mmap where the data for incoming transactions will be placed. This struct/// keeps track of allocations made in the mmap. For each allocation, we store a descriptor that/// has metadata related to the allocation. We also keep track of available free space.pub(super) struct ArrayRangeAllocator<T> { /// This stores all ranges that are allocated. Unlike the tree based allocator, we do *not* /// store the free ranges. /// /// Sorted by offset. pub(super) ranges: KVec<Range<T>>, size: usize, free_oneway_space: usize,}
struct FindEmptyRes { /// Which index in `ranges` should we insert the new range at? /// /// Inserting the new range at this index keeps `ranges` sorted. insert_at_idx: usize, /// Which offset should we insert the new range at? insert_at_offset: usize,}
impl<T> ArrayRangeAllocator<T> { pub(crate) fn new(size: usize, alloc: EmptyArrayAlloc<T>) -> Self { Self { ranges: alloc.ranges, size, free_oneway_space: size / 2, } }
pub(crate) fn free_oneway_space(&self) -> usize { self.free_oneway_space }
pub(crate) fn count_buffers(&self) -> usize { self.ranges.len() }
pub(crate) fn total_size(&self) -> usize { self.size }
pub(crate) fn is_full(&self) -> bool { self.ranges.len() == self.ranges.capacity() }
pub(crate) fn debug_print(&self, m: &SeqFile) -> Result<()> { for range in &self.ranges { seq_print!( m, " buffer {}: {} size {} pid {} oneway {}", 0, range.offset, range.size, range.state.pid(), range.state.is_oneway(), ); if let DescriptorState::Reserved(_) = range.state { seq_print!(m, " reserved\n"); } else { seq_print!(m, " allocated\n"); } } Ok(()) }
/// Find somewhere to put a new range. /// /// Unlike the tree implementation, we do not bother to find the smallest gap. The idea is that /// fragmentation isn't a big issue when we don't have many ranges. /// /// Returns the index that the new range should have in `self.ranges` after insertion. fn find_empty_range(&self, size: usize) -> Option<FindEmptyRes> { let after_last_range = self.ranges.last().map(Range::endpoint).unwrap_or(0);
if size <= self.total_size() - after_last_range { // We can put the range at the end, so just do that. Some(FindEmptyRes { insert_at_idx: self.ranges.len(), insert_at_offset: after_last_range, }) } else { let mut end_of_prev = 0; for (i, range) in self.ranges.iter().enumerate() { // Does it fit before the i'th range? if size <= range.offset - end_of_prev { return Some(FindEmptyRes { insert_at_idx: i, insert_at_offset: end_of_prev, }); } end_of_prev = range.endpoint(); } None } }
pub(crate) fn reserve_new( &mut self, debug_id: usize, size: usize, is_oneway: bool, pid: Pid, ) -> Result<(usize, bool)> { // Compute new value of free_oneway_space, which is set only on success. let new_oneway_space = if is_oneway { match self.free_oneway_space.checked_sub(size) { Some(new_oneway_space) => new_oneway_space, None => return Err(ENOSPC), } } else { self.free_oneway_space };
let FindEmptyRes { insert_at_idx, insert_at_offset, } = self.find_empty_range(size).ok_or(ENOSPC)?; self.free_oneway_space = new_oneway_space;
let new_range = Range { offset: insert_at_offset, size, state: DescriptorState::new(is_oneway, debug_id, pid), }; // Insert the value at the given index to keep the array sorted. self.ranges .insert_within_capacity(insert_at_idx, new_range) .ok() .unwrap();
// Start detecting spammers once we have less than 20% // of async space left (which is less than 10% of total // buffer size). // // (This will short-circuit, so `low_oneway_space` is // only called when necessary.) let oneway_spam_detected = is_oneway && new_oneway_space < self.size / 10 && self.low_oneway_space(pid);
Ok((insert_at_offset, oneway_spam_detected)) }
/// Find the amount and size of buffers allocated by the current caller. /// /// The idea is that once we cross the threshold, whoever is responsible /// for the low async space is likely to try to send another async transaction, /// and at some point we'll catch them in the act. This is more efficient /// than keeping a map per pid. fn low_oneway_space(&self, calling_pid: Pid) -> bool { let mut total_alloc_size = 0; let mut num_buffers = 0;
// Warn if this pid has more than 50 transactions, or more than 50% of // async space (which is 25% of total buffer size). Oneway spam is only // detected when the threshold is exceeded. for range in &self.ranges { if range.state.is_oneway() && range.state.pid() == calling_pid { total_alloc_size += range.size; num_buffers += 1; } } num_buffers > 50 || total_alloc_size > self.size / 4 }
pub(crate) fn reservation_abort(&mut self, offset: usize) -> Result<FreedRange> { // This could use a binary search, but linear scans are usually faster for small arrays. let i = self .ranges .iter() .position(|range| range.offset == offset) .ok_or(EINVAL)?; let range = &self.ranges[i];
if let DescriptorState::Allocated(_) = range.state { return Err(EPERM); }
let size = range.size; let offset = range.offset;
if range.state.is_oneway() { self.free_oneway_space += size; }
// This computes the range of pages that are no longer used by *any* allocated range. The // caller will mark them as unused, which means that they can be freed if the system comes // under memory pressure. let mut freed_range = FreedRange::interior_pages(offset, size); if offset % PAGE_SIZE != 0 { if i == 0 || self.ranges[i - 1].endpoint() <= (offset & PAGE_MASK) { freed_range.start_page_idx -= 1; } } if range.endpoint() % PAGE_SIZE != 0 { let page_after = (range.endpoint() & PAGE_MASK) + PAGE_SIZE; if i + 1 == self.ranges.len() || page_after <= self.ranges[i + 1].offset { freed_range.end_page_idx += 1; } }
self.ranges.remove(i)?; Ok(freed_range) }
pub(crate) fn reservation_commit(&mut self, offset: usize, data: &mut Option<T>) -> Result { // This could use a binary search, but linear scans are usually faster for small arrays. let range = self .ranges .iter_mut() .find(|range| range.offset == offset) .ok_or(ENOENT)?;
let DescriptorState::Reserved(reservation) = &range.state else { return Err(ENOENT); };
range.state = DescriptorState::Allocated(reservation.clone().allocate(data.take())); Ok(()) }
pub(crate) fn reserve_existing(&mut self, offset: usize) -> Result<(usize, usize, Option<T>)> { // This could use a binary search, but linear scans are usually faster for small arrays. let range = self .ranges .iter_mut() .find(|range| range.offset == offset) .ok_or(ENOENT)?;
let DescriptorState::Allocated(allocation) = &mut range.state else { return Err(ENOENT); };
let data = allocation.take(); let debug_id = allocation.reservation.debug_id; range.state = DescriptorState::Reserved(allocation.reservation.clone()); Ok((range.size, debug_id, data)) }
pub(crate) fn take_for_each<F: Fn(usize, usize, usize, Option<T>)>(&mut self, callback: F) { for range in self.ranges.iter_mut() { if let DescriptorState::Allocated(allocation) = &mut range.state { callback( range.offset, range.size, allocation.reservation.debug_id, allocation.data.take(), ); } } }}
pub(crate) struct EmptyArrayAlloc<T> { ranges: KVec<Range<T>>,}
impl<T> EmptyArrayAlloc<T> { pub(crate) fn try_new(capacity: usize) -> Result<Self> { Ok(Self { ranges: KVec::with_capacity(capacity, GFP_KERNEL)?, }) }}