Prevent std :: atomic overflow

Question

I have an atomic counter ( std::atomic<uint32_t> count ) that handles sequentially increasing values ​​for multiple threads.

 uint32_t my_val = ++count; 

Before I get my_val , I want to make sure that the increment will not overflow (i.e.: return to 0)

 if (count == std::numeric_limits<uint32_t>::max()) throw std::runtime_error("count overflow"); 

I think this is a naive check, because if the check is performed by two threads before incrementing the counter, the second thread to increment will get 0 back

 if (count == std::numeric_limits<uint32_t>::max()) // if 2 threads execute this throw std::runtime_error("count overflow"); uint32_t my_val = ++count; // before either gets here - possible overflow 

I suppose I need to use the CAS operation to make sure that when I increment the counter, I really prevent a possible overflow.

So my questions are:

• Is my implementation correct?
• How effective is it (in particular, I need to double-check max )?

My code (with a working example) follows:

 #include <iostream> #include <atomic> #include <limits> #include <stdexcept> #include <thread> std::atomic<uint16_t> count; uint16_t get_val() // called by multiple threads { uint16_t my_val; do { my_val = count; // make sure I get the next value if (count.compare_exchange_strong(my_val, my_val + 1)) { // if I got the next value, make sure we don't overflow if (my_val == std::numeric_limits<uint16_t>::max()) { count = std::numeric_limits<uint16_t>::max() - 1; throw std::runtime_error("count overflow"); } break; } // if I didn't then check if there are still numbers available if (my_val == std::numeric_limits<uint16_t>::max()) { count = std::numeric_limits<uint16_t>::max() - 1; throw std::runtime_error("count overflow"); } // there are still numbers available, so try again } while (1); return my_val + 1; } void run() try { while (1) { if (get_val() == 0) exit(1); } } catch(const std::runtime_error& e) { // overflow } int main() { while (1) { count = 1; std::thread a(run); std::thread b(run); std::thread c(run); std::thread d(run); a.join(); b.join(); c.join(); d.join(); std::cout << "."; } return 0; } 

Answer 1

Yes, you need to use the CAS operation.

 std::atomic<uint16_t> g_count; uint16_t get_next() { uint16_t new_val = 0; do { uint16_t cur_val = g_count; // 1 if (cur_val == std::numeric_limits<uint16_t>::max()) { // 2 throw std::runtime_error("count overflow"); } new_val = cur_val + 1; // 3 } while(!std::atomic_compare_exchange_weak(&g_count, &cur_val, new_val)); // 4 return new_val; } 

The idea is this: the g_count == std::numeric_limits<uint16_t>::max() , get_next() function will always throw an exception.

Steps:

• Get current counter value
• If this is the maximum value, throw an exception (there are no more numbers available)
• Get a new value as an increment of the current value
• Try to atomize a new value. If we could not install it (this has already been done by another thread), try again.

Answer 2

If efficiency is a big problem, I suggest not being so strict on the check. I assume that under normal use, overflow will not be a problem, but do you really need the full 65K range (uint16 is used in your example)?

It would be easier if you allowed some maximum number of running threads. This is a reasonable limit, since no program has an unlimited amount of concurrency. Therefore, if you have N threads, you can simply reduce the overflow limit to 65K - N To compare, if you overflow, you do not need CAS:

 uint16_t current = count.load(std::memory_order_relaxed); if( current >= (std::numeric_limits<uint16_t>::max() - num_threads - 1) ) throw std::runtime_error("count overflow"); count.fetch_add(1,std::memory_order_relaxed); 

This creates a soft overflow condition. If two threads arrive at once, both of them will potentially pass, but this is normal, since the count variable itself never overflows. Any future receipts at this point will logically overflow (until the account is reduced again).

Answer 3

It seems to me that there is still a race condition in which count will be set to 0 instantly, so that another thread will see the value 0.

Suppose count is in std::numeric_limits<uint16_t>::max() , and two threads are trying to get an extra value. The moment Thread 1 executes count.compare_exchange_strong(my_val, my_val + 1) , the counter is set to 0 and that Thread 2 will see if get_val() will happen to call and complete before Thread 1 can restore count to max() .