1 // SPDX-License-Identifier: GPL-2.0
16 /// Keeps track of allocations in a process' mmap.
19 /// keeps track of allocations made in the mmap. For each allocation, we store a descriptor that
25     tree: RBTree<usize, Descriptor<T>>,  field
26     /// Contains an entry for every free range in `self.tree`. This tree sorts the ranges by size,
38     ) -> Self {  in from_array()
39         let mut tree = TreeRangeAllocator {  in from_array()  localVariable
40             tree: RBTree::new(),  in from_array()
47         for range in ranges.drain_all() {  in from_array()
48             let free_size = range.offset - free_offset;  in from_array()
51                 tree.free_tree  in from_array()
53                 let tree_node = alloc.tree.pop().unwrap();  in from_array()
54                 tree.tree.insert(  in from_array()
61                 tree.free_oneway_space = tree.free_oneway_space.saturating_sub(range.size);  in from_array()
65             let tree_node = alloc.tree.pop().unwrap();  in from_array()
68             tree.tree.insert(tree_node.into_node(range.offset, desc));  in from_array()
73             let free_size = size - free_offset;  in from_array()
75             tree.free_tree  in from_array()
77             let tree_node = alloc.tree.pop().unwrap();  in from_array()
78             tree.tree  in from_array()
82         tree  in from_array()
85     pub(crate) fn is_empty(&self) -> bool {  in is_empty()
86         let mut tree_iter = self.tree.values();  in is_empty()
99     pub(crate) fn total_size(&self) -> usize {  in total_size()
103     pub(crate) fn free_oneway_space(&self) -> usize {  in free_oneway_space()
107     pub(crate) fn count_buffers(&self) -> usize {  in count_buffers()
108         self.tree  in count_buffers()
114     pub(crate) fn debug_print(&self, m: &SeqFile) -> Result<()> {  in debug_print()
115         for desc in self.tree.values() {  in debug_print()
142     fn find_best_match(&mut self, size: usize) -> Option<&mut Descriptor<T>> {  in find_best_match()
145         self.tree.get_mut(offset)  in find_best_match()
156     ) -> Result<(usize, bool)> {  in reserve_new()
171         // (This will short-circut, so `low_oneway_space` is  in reserve_new()
178                 pr_warn!("ENOSPC from range_alloc.reserve_new - size: {}", size);  in reserve_new()
185                 // In case we need to break up the descriptor  in reserve_new()
186                 let new_desc = Descriptor::new(found_offset + size, found_size - size);  in reserve_new()
202             self.tree.insert(tree_node);  in reserve_new()
209     pub(crate) fn reservation_abort(&mut self, offset: usize) -> Result<FreedRange> {  in reservation_abort()
210         let mut cursor = self.tree.cursor_lower_bound_mut(&offset).ok_or_else(|| {  in reservation_abort()
212                 "EINVAL from range_alloc.reservation_abort - offset: {}",  in reservation_abort()
222                 "EINVAL from range_alloc.reservation_abort - offset: {}",  in reservation_abort()
234                     "EINVAL from range_alloc.reservation_abort - offset: {}",  in reservation_abort()
241                     "EPERM from range_alloc.reservation_abort - offset: {}",  in reservation_abort()
255         // Compute how large the next free region needs to be to include one more page in  in reservation_abort()
259             unalign => PAGE_SIZE - unalign,  in reservation_abort()
262         // in the newly freed range.  in reservation_abort()
291                     freed_range.start_page_idx -= 1;  in reservation_abort()
309     pub(crate) fn reservation_commit(&mut self, offset: usize, data: &mut Option<T>) -> Result {  in reservation_commit()
310         let desc = self.tree.get_mut(&offset).ok_or(ENOENT)?;  in reservation_commit()
328     pub(crate) fn reserve_existing(&mut self, offset: usize) -> Result<(usize, usize, Option<T>)> {  in reserve_existing()
329         let desc = self.tree.get_mut(&offset).ok_or_else(|| {  in reserve_existing()
331                 "ENOENT from range_alloc.reserve_existing - offset: {}",  in reserve_existing()
348                     "ENOENT from range_alloc.reserve_existing - offset: {}",  in reserve_existing()
362         for (_, desc) in self.tree.iter_mut() {  in take_for_each()
378     /// and at some point we'll catch them in the act.  This is more efficient
380     fn low_oneway_space(&self, calling_pid: Pid) -> bool {  in low_oneway_space()
383         for (_, desc) in self.tree.iter() {  in low_oneway_space()
407     fn new(offset: usize, size: usize) -> Self {  in new()
415     fn try_change_state<F, Data>(&mut self, f: F) -> Result<Data>  in try_change_state()
417         F: FnOnce(Option<TreeDescriptorState<T>>) -> (Option<TreeDescriptorState<T>>, Result<Data>),  in try_change_state()
437     pub(crate) fn try_new() -> Result<Self> {  in try_new()
451     ) -> (  in initialize()
466 /// An allocation for creating a tree from an `ArrayRangeAllocator`.
468     tree: KVec<RBTreeNodeReservation<usize, Descriptor<T>>>,  field
473     pub(crate) fn try_new(len: usize) -> Result<Self> {  in try_new()
476         let mut tree = KVec::with_capacity(num_descriptors, GFP_KERNEL)?;  in try_new()  localVariable
477         for _ in 0..num_descriptors {  in try_new()
478             tree.push(RBTreeNodeReservation::new(GFP_KERNEL)?, GFP_KERNEL)?;  in try_new()
482         for _ in 0..num_descriptors {  in try_new()
486         Ok(Self { tree, free_tree })  in try_new()