How should I make an `u128` addition operation atomic?

Question

Background:

I'm running in a multi-threaded environment where 64 bit values are being added to a global counter (u128) 25-50 times a second.

My Starting Point

I wrote a little snippet:

#[derive(Debug)]
pub struct AtomicU128 {
    lsv : AtomicU64,
    msv : AtomicU64,
}

impl AtomicU128 { 
    fn fetch_add(&self, value : u64) -> u128 {
        let mut previous = self.lsv.fetch_add(value, Ordering::SeqCst) as u128;
        
        previous += if previous + value as u128 > u64::MAX.into() {
            let x = self.msv.fetch_add(1, Ordering::SeqCst);
            x as u128
        } else { 0 };
        
        previous
    }
}

fn main() {
    let a_u128 : AtomicU128 = AtomicU128 { lsv: AtomicU64::new(u64::MAX), msv: AtomicU64::new(0), };
    
    a_u128.fetch_add(1);
    
    println!("{:?}",a_u128);
}

which has a gaping hole in how it's handling the lsv 64bit overflow.

If I wrap the operation in a Mutex, should I bother with the AtomicU64 types?

Edit:

I put the following together, but it feels a little cumbersome:

#[derive(Debug)]
struct AtomicU128 {
    inner: Mutex<u128>,
}

impl AtomicU128 {
    fn new(value: u128) -> Self {
        AtomicU128 {
            inner: Mutex::new(value),
        }
    }

    fn add(&self, value: u128) {
        let mut inner = self.inner.lock().unwrap();
        *inner += value;
    }

    fn get(&self) -> u128 {
        *self.inner.lock().unwrap()
    }
}

fn main() {
    let v = AtomicU128::new(u64::MAX.into());
    
    println!("Before {:?}",v.get());
    v.add(1);
    println!("After  {:?}",v.get());
}

Is there a better way to safely add to u128 types together?

Answer 1

32 into 96

You can add 32-bit integers into a 96-bit count by splitting the count into overlapping 64-bit ranges:

Let L = count mod 2⁶⁴

Let M = count >> 32 mod 2⁶⁴

Now, when you add x, you atomically add into L, set x = (x>>32) + carry, and atomically add into M.

When you read, you can consider the lower-order word to be "authoritative". If it doesn't match the overlapping bits in the higher-order word, then the difference between the values will let you deduce the appropriate correction.

64 into 128

If you want to 64-bit addends into a 128-bit count, you can split those addends into upper and lower 32-bit halves.

The upper 32-bit halves can be added into a 96-bit counth, and the lower 32-bit halves can be added into a 96-bit countl.

The total count is then always just (counth<<32) + countl. Note that observers may not see the two updates to countl and counth as atomic, but they will at least see the total count as monotonically increasing.