6 ms·

In the "bump up" version you could remove both the checked_add branches and replace them with a single check at the end, making the amount of branches the same.

In the "bump up" version you could remove both the checked_add branches and replace them with a single check at the end, making the amount of branches the same. Quick example: https://godbolt.org/z/rdv4qnrs8 https://godbolt.org/z/rdv4qnrs8. *edited to update the example, realized I messed up the comparison logic.

ridiculous_fish 3y ago
I think this doesn't work because `aligned + size` may wrap all the way around into the valid region again. For example if aligned == ptr + 1, and size is usize::MAX, we will end up with new_ptr == ptr and the allocation will wrongly succeed.
- dev_dwarf 3y ago
  Interesting point. I modified my example to test what you described. I had to play with the compilation flags to get the allocs to not be optimized out and to not panic when the integer overflow happens, but otherwise I didn't change the logic. I'm pretty sure my implementation is correctly handling the case you mention, evidenced by it returning a null pointer. Link: https://godbolt.org/z/f1jGW6Pa3 https://godbolt.org/z/f1jGW6Pa3 Update: NVM, definitely not being handled correctly. https://godbolt.org/z/cMTe1o979 https://godbolt.org/z/cMTe1o979
  - deleted 3y ago
    [deleted]
- loeg 3y ago
  The straightforward answer is: don't tolerate ridiculous alignments.
  - saagarjha 3y ago
    You'd need to check for that, though.
    - loeg 3y ago
      No, just restrict the domain of the alignment input to like, u8. Maybe u16. Either way, it is easy to ensure your bump allocation space is far enough away from SIZE_MAX.
sltkr 3y ago
That version is unsafe: what if size == 0xfff..fff and alignment is needed? You will end up with ptr <= new_ptr < end, seemingly a valid result, but actually with not enough space. edit: code moved to a toplevel comment
- loeg 3y ago
  No allocator can be expected to allocate usize::MAX, so it doesn't really matter.
  - dev_dwarf 3y ago
    Agreed. The question really is if you should demand the user to enforce that constraint on the size they pass to you, or if the function itself should signal an error in that case.
    - loeg 3y ago
      I think it would be pretty reasonable to have an input type for that parameter that isn't a full usize and is instead some more restricted type that can only represent smaller values. The alignment parameter could be, like, u8, or maybe u16.
      - dev_dwarf 3y ago
        For the alignment parameter I agree.
        loeg 3y ago
        For both.
      - sltkr 3y ago
        This still doesn't solve the overflow problem. It's also too limiting: with u8 you can't ask for page-aligned data, and with u16 not for hugepage-aligned data. Granted, those aren't exactly prime use cases for a bump allocator, but it seems like poor design to limit the API unnecessarily.

ridiculous_fish 3y ago

I think this doesn't work because `aligned + size` may wrap all the way around into the valid region again. For example if aligned == ptr + 1, and size is usize::MAX, we will end up with new_ptr == ptr and the allocation will wrongly succeed.

dev_dwarf 3y ago
Interesting point. I modified my example to test what you described. I had to play with the compilation flags to get the allocs to not be optimized out and to not panic when the integer overflow happens, but otherwise I didn't change the logic. I'm pretty sure my implementation is correctly handling the case you mention, evidenced by it returning a null pointer. Link: https://godbolt.org/z/f1jGW6Pa3 https://godbolt.org/z/f1jGW6Pa3 Update: NVM, definitely not being handled correctly. https://godbolt.org/z/cMTe1o979 https://godbolt.org/z/cMTe1o979
- deleted 3y ago
  [deleted]
loeg 3y ago
The straightforward answer is: don't tolerate ridiculous alignments.
- saagarjha 3y ago
  You'd need to check for that, though.
  - loeg 3y ago
    No, just restrict the domain of the alignment input to like, u8. Maybe u16. Either way, it is easy to ensure your bump allocation space is far enough away from SIZE_MAX.

sltkr 3y ago

That version is unsafe: what if size == 0xfff..fff and alignment is needed? You will end up with ptr <= new_ptr < end, seemingly a valid result, but actually with not enough space. edit: code moved to a toplevel comment

loeg 3y ago
No allocator can be expected to allocate usize::MAX, so it doesn't really matter.
- dev_dwarf 3y ago
  Agreed. The question really is if you should demand the user to enforce that constraint on the size they pass to you, or if the function itself should signal an error in that case.
  - loeg 3y ago
    I think it would be pretty reasonable to have an input type for that parameter that isn't a full usize and is instead some more restricted type that can only represent smaller values. The alignment parameter could be, like, u8, or maybe u16.
    - dev_dwarf 3y ago
      For the alignment parameter I agree.
      - loeg 3y ago
        For both.
    - sltkr 3y ago
      This still doesn't solve the overflow problem. It's also too limiting: with u8 you can't ask for page-aligned data, and with u16 not for hugepage-aligned data. Granted, those aren't exactly prime use cases for a bump allocator, but it seems like poor design to limit the API unnecessarily.