fair-acc
[3SP] Change Sequence index type to `std::size_t`
Currently, the Sequence class uses the type alias using signed_index_type = std::make_signed_t<std::size_t>; to represent indices. This choice can potentially lead to undefined behavior because of overflows, converting between signed and unsigned types, especially with large values, can result in incorrect indexing and arithmetic errors.
We should replace the signed index type with an unsigned
using index_type = std::size_t;
Additionally, we need to implement overflow protection to handle scenarios where the sequence index might wrap around its maximum value. In a CircularBuffer implementation, it is assumed that:
sequence + 1 > sequence
To maintain this invariant, we should introduce overflow checks and handle them appropriately to prevent undefined behavior.
"To maintain this invariant, we should introduce overflow checks and handle them appropriately to prevent undefined behavior."
How should CircularBuffer handle the overflow?
The handling of this edge case isn’t really discussed. Generally, this is a rare edge case, particularly in the case of uint64_t.
One possible solution could be to address this within the CircularBuffer. A potential approach is to “reset” all sequences in the CircularBuffer's ClaimStrategy. If the sequence reaches its maximum value and an overflow occurs on increment, we could shift all sequences back to the start while maintaining their relative positions.
But this has to be still checked what is the best strategy.
In contrast to the signed integer overflow, the unsigned integer overflow should be safe, notably in this case.
The main thing to watch out is the initialisation and first tag propagation which has often (but not always) being indicated with a -1.
The main unit tests (in order of increasing complexity), qa_Buffer -> qa_Block -> qa_Tag... should be sufficient to catch whether the modified/fixed implementation works.
@frankosterfeld please PM me w.r.t. the required SP effort and/or if you have further questions.
@RalphSteinhagen I gave this a quick shot, and at first, it seems easy enough: the initial sequence value was changed from -1 to 0 a few months back, and qa_buffer, qa_Block, qa_Tags still pass.
However, I get warnings from tag handling when mixing the signed tag index with now unsigned reader/writer positions. So I guess Tag::index would also have to become signed, to match the range of Sequence::index_type (std::size_t). This is where -1 is actually used and moving to std::size_t seems more complicated.