vault

Atomic Bit Operations

13 min read

Atomic Bit Operations

The Linux kernel keeps thousands of boolean flags packed into bitmaps — arrays of unsigned long where each bit means something (a buffer is dirty, a device is online, a request is in flight). The atomic bit operations — set_bit, clear_bit, change_bit, and the value-returning test_and_set_bit, test_and_clear_bit, test_and_change_bit — let multiple CPUs flip individual bits of such a word without a lock and without clobbering each other’s neighbouring bits. They are atomic read-modify-write operations, but, exactly like atomic_t, atomicity is not ordering: the plain set_bit/clear_bit are atomic-but-unordered, while the test_and_* forms (which return the old bit) are fully ordered (Documentation/atomic_bitops.txt, v6.12). Each operation also has a __-prefixed non-atomic twin (__set_bit, __clear_bit) that is faster but only safe when no other CPU can touch the same word.

This note is pinned to Linux 6.12 LTS (released 2024-11-17). The API list, ordering rules, bit numbering, and x86/generic assembly below were read from the v6.12 source tree. It is the bit-granular sibling of Kernel Atomic Operations and atomic_t; read that note for the atomic_t type and the general atomic-vs-ordered framing this note builds on.

Mental Model

A bitmap is just an array of machine words treated as one long row of bits. Bit number nr does not mean “the nth array element” — it means the nth bit across the whole array. The kernel computes which word holds bit nr and which bit within that word using two macros from include/linux/bits.h:

#define BIT_MASK(nr)  (UL(1) << ((nr) % BITS_PER_LONG))
#define BIT_WORD(nr)  ((nr) / BITS_PER_LONG)

So bit 70 on a 64-bit kernel lives in word 70 / 64 = 1, at bit 70 % 64 = 6 of that word. The x86 header states the numbering convention bluntly: “bit 0 is the LSB [least-significant bit] of addr; bit 32 is the LSB of (addr+1)” (arch/x86/include/asm/bitops.h). The atomic operation then targets only that one bit, leaving the other 63 bits of the word untouched even if another CPU is concurrently flipping one of them.

flowchart TB
  subgraph BM["bitmap = unsigned long[2] on a 64-bit kernel"]
    W0["word[0]: bits 0..63<br/>(bit 0 = LSB)"]
    W1["word[1]: bits 64..127"]
  end
  OP["set_bit(70, map)"] --> CALC["BIT_WORD(70)=1<br/>BIT_MASK(70)=1&lt;&lt;6"]
  CALC --> RMW["atomic OR of mask<br/>into word[1]<br/>(other 63 bits untouched)"]
  RMW --> W1
  CPU2["another CPU:<br/>set_bit(65, map)"] -.->|"same word[1],<br/>different bit —<br/>both succeed"| W1

How set_bit locates and flips a single bit. What it shows: the bit number is divided by the word size to pick the array element (BIT_WORD) and the remainder picks the bit-in-word (BIT_MASK); the operation atomically ORs that mask into the chosen word. The insight to take: two CPUs setting different bits of the same word do not collide — the atomicity is per-word read-modify-write, so the second CPU’s OR cannot lose the first CPU’s bit. That is exactly why you cannot do this with a plain word |= mask, which would race.

The API and Its Two Tiers

atomic_bitops.txt organises the single-bit operations into three groups (the bitmap is always an unsigned long * and nr the bit index):

Non-RMW ops — test_bit() reads a single bit (and the acquire-ordered test_bit_acquire()). A pure load; it modifies nothing.

RMW atomic operations without return value — set_bit() (set bit to 1), clear_bit() (clear to 0), change_bit() (toggle), and clear_bit_unlock(). These perform the flip atomically but discard the previous value.

RMW atomic operations with return value — test_and_set_bit(), test_and_clear_bit(), test_and_change_bit(), and test_and_set_bit_lock(). The doc states plainly: “The test_and_{}_bit() operations return the original value of the bit.” This is the magic primitive: test_and_set_bit(nr, map) atomically sets the bit and tells you whether it was already set — a one-instruction “claim this resource if nobody else has” with no lock.

Barriers — smp_mb__{before,after}_atomic(), the same helpers as for atomic_t.

Then the critical sentence that defines the second tier: “All RMW atomic operations have a '__' prefixed variant which is non-atomic.” So __set_bit, __clear_bit, __change_bit, __test_and_set_bit, etc. exist and are not atomic — they are plain register read-modify-writes with no LOCK prefix and no LL/SC loop. They are faster, and correct only when the caller guarantees no concurrent access to that word (e.g. the word is local, or already protected by a lock the caller holds).

Ordering: identical rules to atomic_t

The ORDERING section of atomic_bitops.txt is deliberately the same as atomic_t’s:

Like with atomic_t, the rule of thumb is:

  • non-RMW operations are unordered;
  • RMW operations that have no return value are unordered;
  • RMW operations that have a return value are fully ordered.
  • RMW operations that are conditional are fully ordered.

Except for a successful test_and_set_bit_lock() which has ACQUIRE semantics, clear_bit_unlock() which has RELEASE semantics and test_bit_acquire which has ACQUIRE semantics.

Unpack this. set_bit() and clear_bit() (no return value) are atomic but unordered — they will not lose a concurrent bit flip on the same word, but they impose no ordering on your other memory accesses. This is a frequent source of bugs: setting a “data ready” bit with set_bit() does not guarantee another CPU sees your earlier data writes before it sees the bit. test_and_set_bit() and friends (with a return value) are fully ordered — equivalent, per the cross-referenced atomic_t.txt, to “an smp_mb() before and an smp_mb() after.” Because they are fully ordered they are safe to use as a lock-acquire/release pair with care, but the kernel provides dedicated forms for that:

  • test_and_set_bit_lock() — like test_and_set_bit() but with only ACQUIRE semantics on success (cheaper than full ordering; matches a lock acquire).
  • clear_bit_unlock() — like clear_bit() but with RELEASE semantics (matches a lock release).
  • test_bit_acquire() — an acquire-ordered single-bit load.

These three are the building blocks of bit-spinlocks and the PG_locked page-flag locking. The doc notes the barriers come from the same source as atomic_t: “Since a platform only has a single means of achieving atomic operations the same barriers as for atomic_t are used.”

The one difference from atomic_t worth noticing: for bitops the doc says “RMW operations that are conditional are fully ordered,” whereas atomic_t.txt says conditional ops are “unordered on FAILURE.” The test_and_*_bit operations are not really “conditional” in the cmpxchg sense — they always perform the RMW and always return the old bit — so the bitops phrasing reflects that they are unconditionally fully ordered when they return a value.

set_bit vs __set_bit: the correctness rule

This is the distinction that bites people. Both set a bit; the difference is whether other CPUs may be touching the same word concurrently.

Use set_bit() (atomic) when the word may be accessed concurrently — multiple CPUs, or an interrupt handler that touches the same flags word. The LOCK-prefixed instruction guarantees the read-modify-write is indivisible, so two CPUs setting different bits of the same word both succeed.

Use __set_bit() (non-atomic) only when you know no one else can touch that word right now — it is a local variable, or you hold a lock that serialises all access. It compiles to a plain bts with no LOCK, saving the cache-line-locking cost.

The danger: if you use __set_bit() where concurrency is possible, you get a classic lost-update race. CPU A reads the word, CPU B reads the same word, both OR in their bit, both write back — and whichever writes last wins, silently dropping the other CPU’s bit. There is no warning; the bug manifests as a flag mysteriously not being set. The reverse mistake (using atomic set_bit() where it is not needed) is merely a performance loss, not a correctness bug — which is why the safe default, when in doubt, is the atomic form.

atomic_bitops.txt flags one especially subtle non-atomic case: “In particular __clear_bit_unlock() suffers the same issue as atomic_set(), which is why the generic version maps to clear_bit_unlock().” The issue (from atomic_t.txt) is that a non-atomic store can break the atomicity of a concurrent RMW on a lock-based architecture; for the unlock path that matters, so the generic __clear_bit_unlock is implemented via the atomic clear_bit_unlock to stay safe.

Implementation: x86 BTS/BTR/BTC and the generic fallback

On x86 (arch/x86/include/asm/bitops.h, v6.12) the atomic bitops are hand-written inline assembly. The header’s comment explains the design choice: “These have to be done with inline assembly: that way the bit-setting is guaranteed to be atomic.” Here is set_bit:

static __always_inline void
arch_set_bit(long nr, volatile unsigned long *addr)
{
	if (__builtin_constant_p(nr)) {
		asm volatile(LOCK_PREFIX "orb %b1,%0"
			: CONST_MASK_ADDR(nr, addr)
			: "iq" (CONST_MASK(nr))
			: "memory");
	} else {
		asm volatile(LOCK_PREFIX __ASM_SIZE(bts) " %1,%0"
			: : RLONG_ADDR(addr), "Ir" (nr) : "memory");
	}
}

Two cases. If nr is a compile-time constant (__builtin_constant_p), the compiler knows exactly which byte holds the bit, so it emits a lock orb (locked OR on a byte) against just that byte using a precomputed CONST_MASK — cheaper than a full-word bit-test instruction. Otherwise (nr is a runtime value) it emits lock bts (bit-test-and-set) on the full word, where bts takes the bit index in a register. Either way the LOCK_PREFIX makes the read-modify-write atomic and the "memory" clobber is a compiler barrier. clear_bit uses lock btr (bit-test-and-reset) or lock andb; change_bit uses lock btc (bit-test-and-complement) or lock xorb.

The non-atomic __set_bit is the same instruction without the LOCK:

static __always_inline void
arch___set_bit(unsigned long nr, volatile unsigned long *addr)
{
	asm volatile(__ASM_SIZE(bts) " %1,%0" : : ADDR, "Ir" (nr) : "memory");
}

A bare bts — atomic on a uniprocessor (single instruction) but not across CPUs, because without LOCK the cache line is not held exclusive for the duration. This is the literal difference between the two tiers: one byte of opcode prefix.

The value-returning test_and_set_bit uses GEN_BINARY_RMWcc(LOCK_PREFIX __ASM_SIZE(bts), *addr, c, "Ir", nr) — lock bts plus reading the carry flag (c), into which bts deposits the old value of the bit. So the “test” half is free: the hardware instruction already reports the prior bit in a flag.

On architectures without dedicated atomic bit instructions, the generic implementation (include/asm-generic/bitops/atomic.h) builds bitops out of the atomic_long_* operations from Kernel Atomic Operations and atomic_t:

static __always_inline void
arch_set_bit(unsigned int nr, volatile unsigned long *p)
{
	p += BIT_WORD(nr);
	raw_atomic_long_or(BIT_MASK(nr), (atomic_long_t *)p);
}
 
static __always_inline int
arch_test_and_set_bit(unsigned int nr, volatile unsigned long *p)
{
	long old;
	unsigned long mask = BIT_MASK(nr);
	p += BIT_WORD(nr);
	old = raw_atomic_long_fetch_or(mask, (atomic_long_t *)p);
	return !!(old & mask);
}

set_bit advances the pointer to the right word (p += BIT_WORD(nr)) and atomically ORs in the mask via atomic_long_or — the unordered, no-return RMW. test_and_set_bit uses atomic_long_fetch_or (the fully-ordered value-returning form), grabs the old word, and returns whether the target bit was already set (!!(old & mask)). The mapping is exact: a no-return bitop → an unordered atomic_long_* op; a value-returning bitop → a fully-ordered atomic_long_fetch_* op. This is why the ordering rules match atomic_t’s — the generic bitops literally are atomic_t operations underneath. The non-atomic generic variants live in include/asm-generic/bitops/non-atomic.h, mapping __set_bit → generic___set_bit (a plain *p |= mask).

Worked Examples

Claiming a one-shot resource without a lock. A common pattern: a flag bit that should fire exactly once across all CPUs.

if (!test_and_set_bit(FLAG_INITIALISED, &dev->flags)) {
	/* We are the first; do the one-time init. */
	do_init(dev);
}

test_and_set_bit atomically sets the bit and returns the old value. Exactly one CPU sees the old value 0 (return false) and enters the branch; every other CPU sees 1. No lock, no race — and because it is fully ordered, the init’s memory writes are correctly ordered around the claim.

Per-CPU stats with no concurrency. When a flag word is per-CPU and only ever touched with preemption disabled, the non-atomic form is correct and faster:

__set_bit(STAT_SEEN, this_cpu_ptr(&cpu_flags));

No other CPU touches this word, so the LOCK prefix would be wasted cycles.

A flags word shared with an interrupt handler. If a hard-IRQ handler may set a bit in the same word, the process-context code must use the atomic set_bit() — the handler can interrupt the read-modify-write of a non-atomic __set_bit() mid-flight and the two updates collide. (Context-driven primitive choice is the recurring theme of Linux Kernel Synchronization MOC.)

Failure Modes and Common Misunderstandings

__set_bit under concurrency = silent lost bit. Already covered, but it is the number-one bitops bug: there is no crash, no warning, just a flag that occasionally fails to stick. Diagnosing it requires reasoning about whether the word is genuinely single-accessor.

Assuming set_bit orders surrounding memory. It does not (no return value → unordered). Publishing data and then set_bit(READY, ...) needs an explicit smp_mb__before_atomic() or use of an ordered variant, or the consumer may observe READY before the data. See Memory Barriers in the Linux Kernel.

Confusing the bit-granular bitops with atomic_t’s word-granular bitwise ops. atomic_or(mask, &v) ORs a whole mask into one atomic_t (one word); set_bit(nr, map) flips bit nr of a possibly multi-word bitmap. Different APIs for different jobs — see Kernel Atomic Operations and atomic_t for the word-level atomic_{and,or,xor} family.

test_bit is not atomic with a subsequent set_bit. Reading if (!test_bit(n, m)) set_bit(n, m); is a check-then-act race — two CPUs can both see the bit clear. That is precisely the gap test_and_set_bit exists to close; use it instead.

Big-endian bit numbering. The “bit 0 = LSB of addr” convention is the little-endian numbering used by these generic/set_bit operations. The kernel also has a separate _le/big-endian bitmap family (set_bit_le etc., in include/asm-generic/bitops/le.h) for on-disk and wire formats; do not mix them with the native ops on the same bitmap.

When to Choose What

Reach for atomic bitops when you have many boolean flags to pack densely and CPUs flip them concurrently — they are far cheaper than a lock per flag and pack 64 flags into one cache line. Use test_and_set_bit whenever you need the old value (claim-once, bit-spinlock acquire). Use test_and_set_bit_lock/clear_bit_unlock for the explicit lock/unlock pattern (weaker, cheaper acquire/release ordering). Drop to __set_bit/__clear_bit only when you can prove the word is single-accessor. If you need a single counter or flag rather than a packed array, an atomic_t (one bit or the whole int) is simpler than a 1-word bitmap. If the flags must be read-mostly and scale across hundreds of cores, the answer may be per-CPU data (Per-CPU Variables) rather than a shared bitmap at all.

Production Notes

Atomic bitops are everywhere in the kernel’s hot paths. Page flags (PG_locked, PG_dirty, PG_uptodate, …) are bits in struct page/folio flipped with set_bit/test_and_set_bit; PG_locked is acquired with test_and_set_bit_lock and released with clear_bit_unlock, which is exactly why those acquire/release-ordered bit variants exist. The block layer’s request flags, the network stack’s sk socket flags, and task_struct’s TIF_* thread-info flags are all atomic bitmaps. The bit-spinlock (bit_spin_lock) — a spinlock squeezed into a single bit to save space in densely-packed structures like the dcache hash — is built directly on test_and_set_bit_lock/clear_bit_unlock. Because these operations are unlocked and per-word, they are a key reason read-mostly kernel structures scale without a global lock.

See Also

Graph View

Backlinks