folly::MicroLock — 1-byte 락

1
glibc pthread_mutex_t :   40 bytes
2
libc++ std::mutex     :   40 bytes
3
MSVC std::mutex       :   80 bytes

1
// 1억 개 작은 객체에 각자 mutex
2
struct Slot {
3
  std::mutex mu;     // 40 byte
4
  uint32_t   value;  // 4 byte
5
};                   // sizeof = 48 byte. mu가 90%

1
#include <folly/MicroLock.h>
2

3
struct Slot {
4
  folly::MicroLock lock;  // 1 byte
5
  uint32_t         value;  // 4 byte (padding 포함 8 byte)
6
};

1
#include <folly/MicroLock.h>
2

3
folly::MicroLock m;
4

5
m.lock();
6
// critical section
7
m.unlock();
8

9
// RAII
10
{
11
  std::lock_guard lk(m);   // 표준 lock_guard 사용 가능
12
  // ...
13
}
14

15
// try_lock
16
if (m.try_lock()) {
17
  // ...
18
  m.unlock();
19
}

1
struct Slot {
2
  folly::MicroLock lock;
3
  uint32_t value;
4
};
5

6
Slot s{};   // lock은 zero-init 상태 — 자동으로 unlocked
7

8
// 또는
9
s.lock.init();   // 명시적 init

1
// folly/MicroLock.h 약식
2
class MicroLock {
3
 public:
4
  void lock() noexcept {
5
    if (LIKELY(tryLock())) return;
6
    lockSlow();
7
  }
8

9
  bool try_lock() noexcept {
10
    uint8_t expected = 0;
11
    return lock_.compare_exchange_strong(
12
      expected, kLockedBit, std::memory_order_acquire);
13
  }
14

15
  void unlock() noexcept {
16
    uint8_t prev = lock_.fetch_and(~kLockedBit, std::memory_order_release);
17
    if (prev & kWaitersBit) {
18
      futexWake(reinterpret_cast<uint32_t*>(&lock_), 1);
19
    }
20
  }
21

22
 private:
23
  static constexpr uint8_t kLockedBit  = 0x01;
24
  static constexpr uint8_t kWaitersBit = 0x02;
25
  // 나머지 6-bit: user data 또는 wait queue 메타
26

27
  std::atomic<uint8_t> lock_;
28

29
  void lockSlow() noexcept {
30
    for (;;) {
31
      uint8_t cur = lock_.load(std::memory_order_relaxed);
32
      if (!(cur & kLockedBit)) {
33
        if (lock_.compare_exchange_weak(
34
              cur, cur | kLockedBit, std::memory_order_acquire)) {
35
          return;
36
        }
37
        continue;
38
      }
39
      // mark as having waiters
40
      if (!(cur & kWaitersBit)) {
41
        lock_.fetch_or(kWaitersBit, std::memory_order_relaxed);
42
      }
43
      // futex wait
44
      futexWait(reinterpret_cast<uint32_t*>(&lock_),
45
                static_cast<uint32_t>(cur | kWaitersBit));
46
    }
47
  }
48
};

1
// futex 호출이 lock 변수의 정수 비교로 trigger됨
2
// fast path는 user-space에서 1 instruction CAS
3
// slow path만 kernel

1
folly::MicroLock m;
2

3
m.lock();
4
uint8_t userBits = m.load() & 0xFC;   // 상위 6-bit
5
m.unlock();
6

7
// lock과 동시에 user data 갱신
8
{
9
  std::lock_guard lk(m);
10
  setUserData(m, newBits);   // critical section 안에서 6-bit 사용
11
}

1
struct Chunk {
2
  folly::MicroLock lock;   // 1 byte
3
  uint8_t          countAndFlags;
4
  uint16_t         epoch;
5
  // 4 byte 안에 동기화 + 메타 다 들어감
6
  uint8_t          data[60];
7
};

1
// 1. MicroLock을 condition_variable과 함께
2
folly::MicroLock m;
3
std::condition_variable cv;   // 호환 안 됨 — std::mutex가 필요
4

5
// 2. recursive 사용
6
folly::MicroLock m;
7
{
8
  std::lock_guard lk(m);
9
  {
10
    std::lock_guard lk2(m);   // deadlock — non-recursive
11
  }
12
}
13

14
// 3. 6-bit user data 변경을 race
15
m.unlock();
16
m.setUserBits(newVal);   // 다른 thread가 lock 시도 중일 수 있음
17
// → lock 안에서 변경
18

19
// 4. heap에 1-byte alloc
20
auto* m = new folly::MicroLock;   // sizeof는 1이지만 alignment + malloc header로 32+ byte
21
delete m;
22
// → 1-byte 객체 따로 alloc은 의미 없음. 다른 데이터와 함께 묶어야.