jeudi 15 octobre 2020

right to left - increment after chain in return

I'm trying to build a single producer/single consumer lock-free thread safe ring buffer.

Here's piece the code:

#include <iostream>

struct RingBuffer {
    static constexpr size_t S = 2;
    
    int data[S];
    size_t start = 0;
    size_t end = 0;

    size_t mask(size_t i) const {
        return i & (S - 1);
    }

    bool full() const {
        return end - start == S;
    }
    size_t size() const {
        return end - start;
    }
    
    void push(int t) {
        size_t i = mask(end);
        data[i] = t;
        end++;
    }
    int shift() {
        return data[mask(start++)];
    }
};
 
int main()
{
    RingBuffer ringBuffer;
    
    // emulate t1 that will write
    if (!ringBuffer.full()) {
        int dataToWrite = 10;
        ringBuffer.push(dataToWrite);
    }
    
    // emulate t2 that will read
    if (ringBuffer.size() > 0) {
        int dataRead = ringBuffer.shift();
        std::cout << dataRead << std::endl;
    }
}

Write on the buffer will be performed by a single t1 thread. Read from the buffer will be performed by a single t2 thread.

For what I'm learning, the only concurrency problem here could be in the shift method:

return data[mask(start++)];

because the order of operations must be:

  1. do mask() with the current start value
  2. return data[] at the index returned from point 1
  3. than, increment start

But the code actually will do 1-3-2, not 1-2-3. The question are:

  1. is it possible to to 1-2-3 with this kind of code?
  2. using an -O3 optimization (gcc), can the order of the operations be changed, making the whole undefined? (i.e. on push(), move end++ before data[i] = t?)

Aucun commentaire:

Enregistrer un commentaire