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