Iterating over a PageRangeInclusive can cause panic

[drzewiec]

I encountered what seems to be a bug (not certain though) while trying to iterate over a range of pages to count how many there are. Example code:

let start_page = Page::<Size1GiB>::from_start_address(0xffff_fff0_0000_0000).unwrap();
let end_page = Page::<Size1GiB>::containing_address(0xffff_ffff_ffff_ffff);
let page_range = Page::range_inclusive(start_page, end_page);

let mut num_pages: u64 = 0;
for page in page_range {
  num_pages += 1;
  println!("{}", num_pages);
}

This panics after printing out 63 iterations: panicked at 'attempt to add with overflow', /home/user/.cargo/registry/src/gb.xjqchip.workers.dev-1ecc6299db9ec823/x86_64-0.14.8/src/addr.rs:257:23. It's possible I'm doing something wrong here of course, but I'm having a hard time spotting it if so.

[drzewiec]

Had a bit of time to look this over, and I think that it's related to this:

x86_64/src/structures/paging/page.rs

Line 355 in a143355

self.start += 1;

I suspect that because I'm trying to iterate over pages close to the top of the address range, the code here is breaking because it adds 1 to the page regardless of whether or not that is possible.

Not sure of the best fix though. Could add a check to only add 1 to start if start < end, but I'm not sure what secondary effects that might have.

[Freax13]

I encountered what seems to be a bug (not certain though) while trying to iterate over a range of pages to count how many there are.

This is a bug, what you're trying to do here should work.

Had a bit of time to look this over, and I think that it's related to this:

x86_64/src/structures/paging/page.rs

Line 355 in a143355

self.start += 1;

I suspect that because I'm trying to iterate over pages close to the top of the address range, the code here is breaking because it adds 1 to the page regardless of whether or not that is possible.

I completely agree with your analysis.

Not sure of the best fix though. Could add a check to only add 1 to start if start < end, but I'm not sure what secondary effects that might have.

I think that would make the iterator yield the last address forever. I'm not too sure how to fix this either though.

Rust's RangeInclusive has a non-public field exhausted that tracks whether the last item has been yielded. All of PageRangeInclusive's are public though, so we can't add a new field without making a breaking change.

We could check whether start is the last possible page and decrement end instead if that's the case. This could still be regarded as a breaking change though because the user can observe the start and end fields.

Unrelated to the actual bug, but perhaps still useful for you: Page implements std::op::Sub. let num_pages = end_page - start_page; should work just fine.

[drzewiec]

I think that would make the iterator yield the last address forever. I'm not too sure how to fix this either though.

Yeah, you're right. I didn't spot that at first. I'm also struggling to think of a good way to fix this. Adding a field is probably the best way, but is a breaking change. I wouldn't really call decrementing end a breaking change personally, because I don't really see the state of variables as part of the API. But also, breaking changes aside, it seems like kind of an ugly hack. It seems like in the long run, it would be cleaner to add a field to fix this (even if that does mean the fix will be delayed).

[phil-opp]

A possible solution could be to add a checked_add function to Page, similar to the u64::checked_add function in the standard library. We can then use it in the Iterator implementation here and modify end instead when an overflow would happen (e.g. set it to 0).

By decreasing end only when an overflow would happen, I think this approach is non-breaking. It's not pretty and probably not optimal performance-wise, but I can't think of another backwards compatible way to fix this.

[Freax13]

A possible solution could be to add a checked_add function to Page, similar to the u64::checked_add function in the standard library. We can then use it in the Iterator implementation here and modify end instead when an overflow would happen (e.g. set it to 0).

Given that it's not entirely certain that Page will continue to implement Add, I don't think we should add checked_add right now. However since there is just one page address for each page size where adding 1 can fail (even with 5-level paging), we can probably just compare to those addresses directly.

[Freax13]

Closed by #351