spsc::Queue corrupts its head/tail pointers upon wrapping, if capacity is non-power-of-two.

[Windfisch]

Hi,

spsc::Queue supports arbitrary capacities (i.e., non-power-of-two), but does not wrap its head and tail pointers correctly when en/dequeueing. Instead, only wrapping_add / wrapping_sub is used for pointer/index arithmetics, while an actual modulo operation is only used for accessing the array elements. Effectively, these pointers are incremented modulo 2^8 or whatever bitness the underlying integer has.

This is only sound if the capacity is a divisor of 2^8, i.e. only for power-of-two capacities. (((a+1) % b) % c == (a+1) % c iif b is a multiple of c, which is not the case here.)

The following test case illustrates this bug. (It can be inserted to the test suite in src/spsc/mod.rs and executed using cargo test --features 'serde','x86-sync-pool' spsc):

    #[test]
    fn overflow_tail() {
        let mut rb: Queue<i32, U5, u8> = Queue::u8();

        for i in 0..4 {
            rb.enqueue(i).unwrap();
        }
        for _ in 0..70 {
            for i in 0..4 {
                assert_eq!(rb.dequeue().unwrap(), i);
                rb.enqueue(i).unwrap();
            }
        }
    }

Possible solutions include:

1. Doing the modulo step on every write operation on head/tail; this will likely not incur additional costs, because now the modulo operation for accessing the array element becomes unneccessary. However, it will make a "queue full" condition indistinguable from "queue empty" (both yield head == tail).
2. Like 1, but with double the capacity as the modulus. This incurs an additional cost, because the second modulo will still be necessary. Additionally, this limits the allowed max capacity to half of what the underlying integer can hold.
3. Like 1, but wasting one element of queue space. In this case, "queue empty" is represented by head == tail, while "queue full" is head == tail + 1 (mod capacity).
4. Simply disallow non-power-of-two queue sizes.

[korken89]

Hi, thank you for catching this!
I have it on my todo for Thursday hacker night.

[korken89]

I have committed a fix in the const generics port