folly::PicoSpinLock — 1-byte spinlock

1
// pointer는 보통 하위 3 bit이 0 (8-byte align)
2
// 가장 낮은 bit을 lock으로 사용 가능
3
folly::PicoSpinLock<uintptr_t> lock_ptr;
4
lock_ptr.init(reinterpret_cast<uintptr_t>(some_ptr));
5
{
6
  std::lock_guard g(lock_ptr);
7
  void* p = reinterpret_cast<void*>(lock_ptr.getData());
8
  // use p
9
}

1
#include <folly/synchronization/PicoSpinLock.h>
2

3
// 1. 기본 — uintptr_t 1 bit lock
4
folly::PicoSpinLock<uintptr_t> lock;
5
lock.init(0);                   // 데이터 초기화
6

7
// 2. lock / unlock
8
lock.lock();
9
auto data = lock.getData();
10
lock.setData(data + 1);
11
lock.unlock();
12

13
// 3. std::lock_guard 호환
14
{
15
  std::lock_guard g(lock);
16
  lock.setData(lock.getData() + 1);
17
}
18

19
// 4. try
20
if (lock.try_lock()) {
21
  lock.setData(...);
22
  lock.unlock();
23
}
24

25
// 5. bit 위치 선택 (custom)
26
folly::PicoSpinLock<uint64_t, /*lockBitPos=*/63> top_bit_lock;
27
// 최상위 bit을 lock으로, 하위 63 bit이 데이터

1
// 약식
2
template <typename IntType, size_t Bit = sizeof(IntType)*8 - 1>
3
class PicoSpinLock {
4
  std::atomic<IntType> data_;
5
  static constexpr IntType kLockMask = IntType(1) << Bit;
6
  static constexpr IntType kDataMask = ~kLockMask;
7
};

1
// 약식
2
void lock() {
3
  while (true) {
4
    IntType old = data_.load(std::memory_order_relaxed);
5
    IntType expected = old & kDataMask;     // lock bit = 0
6
    IntType desired  = expected | kLockMask;
7
    if (data_.compare_exchange_weak(expected, desired,
8
                                     std::memory_order_acquire)) {
9
      return;
10
    }
11
    cpu_pause();
12
  }
13
}

1
void unlock() {
2
  data_.fetch_and(kDataMask, std::memory_order_release);   // lock bit clear
3
}

1
IntType getData() const {
2
  return data_.load(std::memory_order_relaxed) & kDataMask;
3
}
4

5
void setData(IntType v) {
6
  // lock이 잡혀 있을 때만 호출하는 게 안전
7
  IntType old = data_.load(std::memory_order_relaxed);
8
  IntType desired = (v & kDataMask) | (old & kLockMask);
9
  data_.store(desired, std::memory_order_release);
10
}

1
// node에 next pointer + lock bit
2
struct Node {
3
  folly::PicoSpinLock<uintptr_t> next_locked;   // 8 byte
4
  Value value;
5
};
6

7
Node* next(Node* n) {
8
  std::lock_guard g(n->next_locked);
9
  return reinterpret_cast<Node*>(n->next_locked.getData());
10
}

1
folly::PicoSpinLock<uint32_t, 0> rc_lock;   // bit 0 = lock, bits 1-31 = count
2
rc_lock.init(0 | 1u);   // count = 0, lock bit can be flipped
3

4
void increment() {
5
  std::lock_guard g(rc_lock);
6
  rc_lock.setData(rc_lock.getData() + 2);   // count는 bit 1 이상
7
}

1
folly::PicoSpinLock<uintptr_t, 1> ptr_lock;   // bit 1 = lock, bit 0 = tag
2
// pointer가 4-byte align이면 하위 2 bit이 모두 사용 가능

1
// Bad — setData가 lock 없이 호출
2
folly::PicoSpinLock<uint64_t> psl;
3
psl.init(0);
4
psl.setData(42);   // 다른 thread가 lock 중이면 lock bit 덮음

1
// 주의 — bit 위치 충돌
2
folly::PicoSpinLock<uintptr_t, 0> ptr_lock;
3
void* ptr = malloc(64);     // 16-byte align — bit 0 사용 안 함
4
ptr_lock.init(uintptr_t(ptr));
5
// ptr 정렬이 1-byte라면 ptr의 bit 0가 lock과 충돌!

1
// Good — 매우 작은 객체에 lock 추가
2
struct Entry {
3
  folly::PicoSpinLock<uint64_t> data;   // 8 byte, lock + 63-bit payload
4
};
5
// vs
6
struct Entry {
7
  uint64_t data;
8
  std::mutex mu;                          // +40 byte
9
};