Panic on generation overflowing instead of silent wrapping

[jieyouxu]

I was trying to implement my own GenerationalArena, but I am not sure how to ensure the memory safety of the generation counter. Is the following a potential memory soundness issue (unlikely in practice and not caught during running debug builds)?

Right now, a generation-aware index is encoded by the Index type:

https://github.com/fitzgen/generational-arena/blob/da208a4656670bfd889af2224900eee40bc2897a/src/lib.rs#L200-L203

Notice that generation is u64 (or any other u*, for this matter). Rust defines unsigned integer addition (RFC 560) to do two's complement wrap-around if overflow checks are disabled (default in release mode) and panic otherwise – in this case panicking is memory safe, but it's the unsigned integer wrap around which is concerning.

u64::MAX.wrapping_add(1) == 0

In remove, we monotonically increase the generation counter:

https://github.com/fitzgen/generational-arena/blob/da208a4656670bfd889af2224900eee40bc2897a/src/lib.rs#L508

And this code is correct – we need to monotonically increase the generation counter to deal with the ABA problem – if overflow panics.

But since this uses the default adding behavior for u64, impl Add<u64> for u64, it is possible that we violate the required monotonically increasing guarantee of the generation counter due to the overflow check being turned off (e.g. default in release mode) where we would default to wrap-around in runtime instead of panic – e.g. instead of the expected u64::MAX + 1 generation counter, we would get 0u64 with wrap around – and assuming a sufficiently large arena that ran for sufficiently long time, it may be possible that this generation is still alive within the arena.

Possible Mitigation Strategies

Assuming that this wrapping behavior may be problematic somehow, we could simply change

https://github.com/fitzgen/generational-arena/blob/da208a4656670bfd889af2224900eee40bc2897a/src/lib.rs#L508

to

self.generation = self.generation.checked_add(1)
    .expect("generation counter too large");

Which would panic instead of silently wrapping around even when overflow checks are turned off (since the overflow check here is forced). This would almost certainly cause performance regressions since we would have an additional panic branch even in --release mode.

[ghost]

I suggest, if possible, renaming the issue to "Panic on generation overflowing instead of silent wrapping", which better conveys your idea.

[jieyouxu]

I suggest, if possible, renaming the issue to "Panic on generation overflowing instead of silent wrapping", which better conveys your idea.

Thanks! That's a much better issue name than before!

[fitzgen]

If we assume the counter is stored in a register and that it takes 1 nanosecond to increment the counter (just allocating in the arena in a loop, let alone any usage pattern that could actually observe the results of the potential overflow, does a few orders of magnitude more work than that) it will be 584.6 years before the counter overflows.

This is not a practical concern, and not worth the overhead of dynamic checks for overflow.