# hazarc

[![Crates.io](https://img.shields.io/crates/v/hazarc.svg)](https://crates.io/crates/hazarc)
[![Documentation](https://docs.rs/hazarc/badge.svg)](https://docs.rs/hazarc)
[![CI](https://github.com/wyfo/hazarc/actions/workflows/ci.yml/badge.svg)](https://github.com/wyfo/hazarc/actions/workflows/ci.yml)
[![License](https://img.shields.io/badge/license-MIT_OR_Apache--2.0-blue.svg)](https://github.com/wyfo/hazarc#license)

A wait-free `AtomicArc` optimized for read-intensive use cases.

## Acknowledgement

This library is based on the brilliant idea behind [`arc-swap`](https://crates.io/crates/arc-swap) from [Michal Vaner](https://github.com/vorner): mixing hazard pointer-based protection with atomic reference counting.

## Examples

```rust
use hazarc::AtomicArc;

struct Config { /* ... */ }

fn update_config(shared_cfg: &AtomicArc<Config>, /* ... */) {
    shared_cfg.store(/* ... */);
}

fn task(shared_cfg: &AtomicArc<Config>) {
    loop {
        let cfg = shared_cfg.load();
        /* ... */
    }
}
```

`AtomicArc::load` is already very fast, but `Cache::load` is blazingly fast.

```rust
use std::sync::Arc;
use hazarc::AtomicArc;

struct Config { /* ... */ }

fn update_config(shared_cfg: &AtomicArc<Config>, /* ... */) {
    shared_cfg.store(/* ... */);
}

fn spawn_task(shared_cfg: Arc<AtomicArc<Config>>) {
    thread::spawn(move || {
        let mut cache = hazarc::Cache::new(shared_cfg);
        loop {
            let cfg = cache.load();
            /* ... */
        }
    });
}
```

With custom domains, it can be used in a `no_std` environment.

```rust
#![no_std]
extern crate alloc;

use alloc::sync::Arc;
use hazarc::{AtomicArc, domain::Domain};

hazarc::pthread_domain!(NoStdDomain(2)); // 2 hazard pointer slots
fn register_domain_cleanup() {
    extern "C" fn deallocate_domain() {
        unsafe { NoStdDomain::static_list().deallocate() };
    }
    unsafe { libc::atexit(deallocate_domain) };
}

struct Config { /* ... */ }

fn update_config(shared_cfg: &AtomicArc<Config, NoStdDomain>, /* ... */) {
    shared_cfg.store(/* ... */);
}

fn task(shared_cfg: &AtomicArc<Config, NoStdDomain>) {
    loop {
        let cfg = shared_cfg.load();
        /* ... */
    }
}
```

## Write policy

`AtomicArc` has a generic `WritePolicy` parameter with the following variants:
- `Serialized`: writes on a given `AtomicArc` should be serialized — with a mutex, a MPSC task, etc. Concurrent writes are still safe with this policy, but can provoke non-monotonic reads, i.e. a subsequent load may observe an older value than a previous load.
- `Concurrent` (the default): writes on a given `AtomicArc` can be concurrent. This adds a small overhead to the non-critical path of reads, and a larger overhead to writes on 32-bit platforms.

## Wait-freedom

### Load

#### Thread-local access

`AtomicArc::load` relies on a domain's thread-local node which is lazily allocated and inserted in the domain's global list on first access. As a consequence, the first `AtomicArc::load` for a given domain may not be wait-free.

It is however possible to access the thread-local node explicitly before using `AtomicArc`, making all subsequent accesses wait-free. Another solution is to pre-allocate the number of nodes required by the program. In that case, insertion into the domain's global list is bounded by the number of allocated nodes, and thread-local accesses are wait-free.

#### Concurrent writes on 32-bit platforms

Concurrent writes require handling the ABA problem with a generation counter, which can overflow on 32-bit platforms. On overflow, the thread-local node has to be released, and subsequent `AtomicArc::load` call may allocate a new node. As a consequence, wait-freedom is only guaranteed for at least 2^31 consecutive loads.

### Store

`AtomicArc::store`, which wraps `AtomicArc::swap`, scans the whole domain's global list, executing a bounded number of atomic operations on each node. If the number of nodes is bounded as well — which should be the case most of the time — then the whole operation is wait-free.

If there are concurrent writes on the same `AtomicArc`, they may execute `AtomicArc::load` internally, with the same consequences on wait-freedom.

## Safety

This library uses unsafe code to deal with `AtomicPtr` manipulation and DST allocations. It is extensively tested with [`miri`](https://github.com/rust-lang/miri) to ensure its soundness, including over multiple weak memory model permutations.
 
## Differences with `arc-swap`

- Custom domains to reduce contention and add `no_std` support
- Manual/automatic domain deallocation
- Wait-free `AtomicArc::swap` — `ArcSwap::swap` is only lock-free
- Optimized `Serialized` write policy
- Less atomic RMW instructions
- `AtomicArc::load` critical path fully inlined
- [Better performance](benches/README.md), especially on ARM architecture
- Null pointer/`None` load optimized
- Ergonomic API for `Option`, `AtomicOptionArc<T>::load` returns `Option<ArcBorrow<T>>`

## License

Licensed under either of

- [Apache License, Version 2.0](LICENSE-APACHE)
- [MIT license](LICENSE-MIT)

at your option.