swap/
present_list.rs

1// Copyright 2023 The ChromiumOS Authors
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#![deny(missing_docs)]
6
7use std::ops::Range;
8
9/// [PresentList] is a utility for tracking whether or not pages in an address space are present.
10///
11/// TODO(b/262379173): Use bit vector to represent the list instead of boolean vector.
12#[derive(Debug)]
13pub struct PresentList {
14    list: Vec<bool>,
15    /// Cursor used when iterating over pages present. All pages with indices less than the cursor
16    /// are known to be empty.
17    min_possible_idx: usize,
18}
19
20impl PresentList {
21    /// Allocates the list of state.
22    ///
23    /// # Arguments
24    ///
25    /// * `num_of_pages` - the number of pages in the region.
26    pub fn new(num_of_pages: usize) -> Self {
27        Self {
28            list: vec![false; num_of_pages],
29            min_possible_idx: num_of_pages,
30        }
31    }
32
33    /// Returns whether the page is present or not
34    ///
35    /// # Arguments
36    ///
37    /// * `idx` - the index in the list.
38    pub fn get(&self, idx: usize) -> Option<&bool> {
39        self.list.get(idx)
40    }
41
42    /// Marks the range of indices as present.
43    ///
44    /// # Arguments
45    ///
46    /// * `idx_range` - the indices of consecutive pages to be marked as present.
47    pub fn mark_as_present(&mut self, idx_range: Range<usize>) -> bool {
48        let result = self.update(idx_range, true);
49        // Setting 0 is faster than setting exact index by comparing the idx_range.start and current
50        // min_possible_idx because it does not have conditional branch. This may cause useless
51        // traversing on first_data_range(). But it should be acceptable because first_data_range()
52        // is called on swap in and swap out while mark_as_present() is called on moving the guest
53        // memory to the staging which is more latency-aware.
54        // TODO(kawasin): Use a branchless conditional move.
55        self.min_possible_idx = 0;
56        result
57    }
58
59    /// Clears the states of the pages.
60    ///
61    /// # Arguments
62    ///
63    /// * `idx_range` - the indices of consecutive pages to be cleared.
64    pub fn clear_range(&mut self, idx_range: Range<usize>) -> bool {
65        let result = self.update(idx_range.clone(), false);
66        // TODO(b/265758094): skip updating min_possible_idx on page fault handling.
67        if result
68            && idx_range.start <= self.min_possible_idx
69            && self.min_possible_idx < idx_range.end
70        {
71            self.min_possible_idx = idx_range.end;
72        }
73        result
74    }
75
76    fn update(&mut self, idx_range: Range<usize>, value: bool) -> bool {
77        if let Some(list) = self.list.get_mut(idx_range) {
78            for v in list {
79                *v = value;
80            }
81            true
82        } else {
83            false
84        }
85    }
86
87    /// Returns the first range of indices of consecutive pages present in the list.
88    ///
89    /// # Arguments
90    ///
91    /// * `max_pages` - the max size of the returned chunk even if the chunk of consecutive present
92    ///   pages is longer than this.
93    pub fn first_data_range(&mut self, max_pages: usize) -> Option<Range<usize>> {
94        if let Some(idx_range) = self.find_data_range(self.min_possible_idx, max_pages) {
95            // Update min_possible_idx otherwise min_possible_idx will not be updated on next
96            // clear_range().
97            self.min_possible_idx = idx_range.start;
98            Some(idx_range)
99        } else {
100            // Update min_possible_idx to skip traversing on next calls.
101            self.min_possible_idx = self.list.len();
102            None
103        }
104    }
105
106    /// Returns the first range of indices of consecutive pages present in the list after
107    /// `head_idx`.
108    ///
109    /// # Arguments
110    ///
111    /// * `head_idx` - The index to start seeking data with.
112    /// * `max_pages` - The max size of the returned chunk even if the chunk of consecutive present
113    ///   pages is longer than this.
114    pub fn find_data_range(&self, head_idx: usize, max_pages: usize) -> Option<Range<usize>> {
115        let head_idx = head_idx + self.list[head_idx..].iter().position(|v| *v)?;
116        let tail_idx = std::cmp::min(self.list.len() - head_idx, max_pages) + head_idx;
117        let tail_idx = self.list[head_idx + 1..tail_idx]
118            .iter()
119            .position(|v| !*v)
120            .map_or(tail_idx, |offset| offset + head_idx + 1);
121        Some(head_idx..tail_idx)
122    }
123
124    /// Returns the count of present pages in the list.
125    pub fn all_present_pages(&self) -> usize {
126        self.list[self.min_possible_idx..]
127            .iter()
128            .map(|v| usize::from(*v))
129            .sum()
130    }
131}
132
133#[cfg(test)]
134mod tests {
135
136    use super::*;
137
138    #[test]
139    fn get_default() {
140        let list = PresentList::new(200);
141
142        assert_eq!(*list.get(0).unwrap(), false);
143        assert_eq!(*list.get(10).unwrap(), false);
144    }
145
146    #[test]
147    fn get_out_of_range() {
148        let list = PresentList::new(200);
149
150        assert!(list.get(200).is_none());
151    }
152
153    #[test]
154    fn mark_as_present() {
155        let mut list = PresentList::new(200);
156
157        assert!(list.mark_as_present(10..12));
158        assert_eq!(*list.get(9).unwrap(), false);
159        assert_eq!(*list.get(10).unwrap(), true);
160        assert_eq!(*list.get(11).unwrap(), true);
161        assert_eq!(*list.get(12).unwrap(), false);
162    }
163
164    #[test]
165    fn mark_as_present_duplicated() {
166        let mut list = PresentList::new(200);
167
168        assert!(list.mark_as_present(10..12));
169        assert!(list.mark_as_present(11..13));
170        assert_eq!(*list.get(9).unwrap(), false);
171        assert_eq!(*list.get(10).unwrap(), true);
172        assert_eq!(*list.get(11).unwrap(), true);
173        assert_eq!(*list.get(12).unwrap(), true);
174        assert_eq!(*list.get(13).unwrap(), false);
175    }
176
177    #[test]
178    fn mark_as_present_out_of_range() {
179        let mut list = PresentList::new(200);
180
181        assert!(!list.mark_as_present(10..201));
182        assert_eq!(*list.get(10).unwrap(), false);
183    }
184
185    #[test]
186    fn clear_range() {
187        let mut list = PresentList::new(200);
188
189        assert!(list.mark_as_present(10..14));
190        assert!(list.clear_range(11..13));
191        assert_eq!(*list.get(9).unwrap(), false);
192        assert_eq!(*list.get(10).unwrap(), true);
193        assert_eq!(*list.get(11).unwrap(), false);
194        assert_eq!(*list.get(12).unwrap(), false);
195        assert_eq!(*list.get(13).unwrap(), true);
196        assert_eq!(*list.get(14).unwrap(), false);
197    }
198
199    #[test]
200    fn clear_range_duplicated() {
201        let mut list = PresentList::new(200);
202
203        assert!(list.mark_as_present(10..14));
204        assert!(list.clear_range(11..13));
205        assert!(list.clear_range(12..15));
206        assert_eq!(*list.get(9).unwrap(), false);
207        assert_eq!(*list.get(10).unwrap(), true);
208        assert_eq!(*list.get(11).unwrap(), false);
209        assert_eq!(*list.get(12).unwrap(), false);
210        assert_eq!(*list.get(13).unwrap(), false);
211        assert_eq!(*list.get(14).unwrap(), false);
212        assert_eq!(*list.get(15).unwrap(), false);
213    }
214
215    #[test]
216    fn clear_range_out_of_range() {
217        let mut list = PresentList::new(200);
218
219        assert!(list.mark_as_present(10..11));
220        assert!(!list.clear_range(10..201));
221        assert_eq!(*list.get(10).unwrap(), true);
222    }
223
224    #[test]
225    fn first_data_range() {
226        let mut list = PresentList::new(200);
227
228        list.mark_as_present(1..3);
229        list.mark_as_present(12..13);
230        list.mark_as_present(20..22);
231        list.mark_as_present(22..23);
232        list.mark_as_present(23..30);
233
234        assert_eq!(list.first_data_range(200).unwrap(), 1..3);
235        list.clear_range(1..3);
236        assert_eq!(list.first_data_range(200).unwrap(), 12..13);
237        list.clear_range(12..13);
238        assert_eq!(list.first_data_range(200).unwrap(), 20..30);
239        list.clear_range(20..30);
240        assert!(list.first_data_range(200).is_none());
241    }
242
243    #[test]
244    fn first_data_range_clear_partially() {
245        let mut list = PresentList::new(200);
246
247        list.mark_as_present(10..20);
248
249        list.clear_range(5..10);
250        assert_eq!(list.first_data_range(200).unwrap(), 10..20);
251        list.clear_range(5..12);
252        assert_eq!(list.first_data_range(200).unwrap(), 12..20);
253        list.clear_range(19..21);
254        assert_eq!(list.first_data_range(200).unwrap(), 12..19);
255        list.clear_range(16..17);
256        assert_eq!(list.first_data_range(200).unwrap(), 12..16);
257    }
258
259    #[test]
260    fn first_data_range_mark_after_clear() {
261        let mut list = PresentList::new(200);
262
263        list.mark_as_present(10..20);
264
265        list.clear_range(10..15);
266        assert_eq!(list.first_data_range(200).unwrap(), 15..20);
267        list.mark_as_present(5..15);
268        assert_eq!(list.first_data_range(200).unwrap(), 5..20);
269    }
270
271    #[test]
272    fn first_data_range_end_is_full() {
273        let mut list = PresentList::new(20);
274
275        list.mark_as_present(10..20);
276
277        assert_eq!(list.first_data_range(20).unwrap(), 10..20);
278    }
279
280    #[test]
281    fn first_data_range_max_pages() {
282        let mut list = PresentList::new(20);
283
284        list.mark_as_present(10..13);
285
286        assert_eq!(list.first_data_range(1).unwrap(), 10..11);
287        assert_eq!(list.first_data_range(2).unwrap(), 10..12);
288        assert_eq!(list.first_data_range(3).unwrap(), 10..13);
289        assert_eq!(list.first_data_range(4).unwrap(), 10..13);
290    }
291
292    #[test]
293    fn find_data_range() {
294        let mut list = PresentList::new(200);
295
296        list.mark_as_present(1..3);
297        list.mark_as_present(12..13);
298        list.mark_as_present(20..22);
299        list.mark_as_present(22..23);
300        list.mark_as_present(23..30);
301
302        assert_eq!(list.find_data_range(0, 200).unwrap(), 1..3);
303        assert_eq!(list.find_data_range(3, 200).unwrap(), 12..13);
304        assert_eq!(list.find_data_range(13, 200).unwrap(), 20..30);
305        assert_eq!(list.find_data_range(22, 5).unwrap(), 22..27);
306        assert!(list.find_data_range(30, 200).is_none());
307        assert!(list.find_data_range(200, 200).is_none());
308    }
309
310    #[test]
311    fn find_data_range_clear_partially() {
312        let mut list = PresentList::new(200);
313
314        list.mark_as_present(10..20);
315
316        list.clear_range(5..10);
317        assert_eq!(list.find_data_range(0, 200).unwrap(), 10..20);
318        list.clear_range(5..12);
319        assert_eq!(list.find_data_range(0, 200).unwrap(), 12..20);
320        list.clear_range(19..21);
321        assert_eq!(list.find_data_range(0, 200).unwrap(), 12..19);
322        list.clear_range(16..17);
323        assert_eq!(list.find_data_range(0, 200).unwrap(), 12..16);
324    }
325
326    #[test]
327    fn find_data_range_mark_after_clear() {
328        let mut list = PresentList::new(200);
329
330        list.mark_as_present(10..20);
331
332        list.clear_range(10..15);
333        assert_eq!(list.find_data_range(0, 200).unwrap(), 15..20);
334        list.mark_as_present(5..15);
335        assert_eq!(list.find_data_range(0, 200).unwrap(), 5..20);
336    }
337
338    #[test]
339    fn find_data_range_end_is_full() {
340        let mut list = PresentList::new(20);
341
342        list.mark_as_present(10..20);
343
344        assert_eq!(list.find_data_range(0, 20).unwrap(), 10..20);
345    }
346
347    #[test]
348    fn find_data_range_max_pages() {
349        let mut list = PresentList::new(20);
350
351        list.mark_as_present(10..13);
352
353        assert_eq!(list.find_data_range(0, 1).unwrap(), 10..11);
354        assert_eq!(list.find_data_range(0, 2).unwrap(), 10..12);
355        assert_eq!(list.find_data_range(0, 3).unwrap(), 10..13);
356        assert_eq!(list.find_data_range(0, 4).unwrap(), 10..13);
357    }
358
359    #[test]
360    fn all_present_pages() {
361        let mut list = PresentList::new(20);
362
363        list.mark_as_present(1..5);
364        list.mark_as_present(12..13);
365
366        assert_eq!(list.all_present_pages(), 5);
367    }
368}
swap/present_list.rs

swap/
present_list.rs
