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 7 use 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)] 13 pub 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 20 impl PresentList { 21 /// Allocates the list of state. 22 /// 23 /// # Arguments 24 /// 25 /// * `num_of_pages` - the number of pages in the region. new(num_of_pages: usize) -> Self26 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. get(&self, idx: usize) -> Option<&bool>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. mark_as_present(&mut self, idx_range: Range<usize>) -> bool47 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. clear_range(&mut self, idx_range: Range<usize>) -> bool64 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 update(&mut self, idx_range: Range<usize>, value: bool) -> bool76 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. first_data_range(&mut self, max_pages: usize) -> Option<Range<usize>>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. find_data_range(&self, head_idx: usize, max_pages: usize) -> Option<Range<usize>>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. all_present_pages(&self) -> usize125 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)] 134 mod tests { 135 136 use super::*; 137 138 #[test] get_default()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] get_out_of_range()147 fn get_out_of_range() { 148 let list = PresentList::new(200); 149 150 assert!(list.get(200).is_none()); 151 } 152 153 #[test] mark_as_present()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] mark_as_present_duplicated()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] mark_as_present_out_of_range()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] clear_range()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] clear_range_duplicated()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] clear_range_out_of_range()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] first_data_range()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] first_data_range_clear_partially()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] first_data_range_mark_after_clear()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] first_data_range_end_is_full()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] first_data_range_max_pages()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] find_data_range()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] find_data_range_clear_partially()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] find_data_range_mark_after_clear()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] find_data_range_end_is_full()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] find_data_range_max_pages()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] all_present_pages()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 } 369