(KO) CUBRID 락프리 free list — 백버퍼 블록 할당기를 가진 타입드 노드 풀

목차

• 학술적 배경
• DBMS 공통 설계 패턴
• CUBRID의 구현
• 소스 코드 가이드
• 소스 검증 (2026-05-07 기준)
• CUBRID 너머 — 비교 설계와 연구 프론티어
• 출처

학술적 배경

Free list는 가능한 가장 단순한 메모리 풀이다. 자유 객체의 단일 연결 리스트. 할당은 head를 pop, 해제는 head로 push다. Treiber 스택의 두 단계 CAS 프로토콜이 그대로 적용된다. 교과서적 다룸은 Herlihy & Shavit, The Art of Multiprocessor Programming, 11장 §Concurrent Stacks and Elimination — 같은 모양을 추상 원소가 아니라 타입이 정해진 재사용 객체에 적용한 것이다.

흥미로운 설계 긴장은 다음과 같다.

1. head에 무엇을 둘 것인가? 단일 전역 head는 매 alloc/release 에서 코어 사이를 튕긴다. 표준 완화는 elimination(head를 건드리 지 않고 alloc과 release를 짝짓기)와 partitioning(CPU별 free list 에 cross-shard stealing) 이다.
2. 언제 free list를 키울 것인가? 고정 크기 풀이 가장 단순하나 부하 아래에서 고갈된다. 자라는 풀은 블록 할당기와 그것을 부르는 전략이 필요하다. 고갈 시 on-demand 블록은 호출 스레드를 멈추게 하고, init에 미리 할당하면 메모리를 낭비한다.
3. ABA를 어떻게 막는가? 주소를 재활용하는 모든 free list가 정통 Treiber 스택 ABA 문제와 정면 충돌한다. pop이 head를 읽고 head->next를 계산한 뒤 head를 head->next로 CAS한다. 완화책 은 태그된 포인터(head 워드의 추가 비트), hazard pointer(스레드별 발행된 참조), 또는 트랜잭션 기반 회수(어떤 리더도 pop된 노드를 들고 있을 수 없게 될 때까지 재사용 지연)다.

CUBRID의 lockfree::freelist<T>는 다음을 고른다. 단일 available 리스트 head, 게으른 성장을 위한 한 블록 백버퍼, 그리고 ABA가 한정 되도록 tran::table / tran::descriptor 프레임워크를 사용. 백버퍼 가 설계의 특징적인 요소다.

성장 분할 상환 수단으로서의 백버퍼

available 리스트가 비어 있는 상태에서 claim()이 그것을 발견하면, 실패하거나, 스핀하거나, 새 블록을 할당해야 한다. 할당은 비싸다 (malloc + N typed-init 호출). 동시 할당자가 또한 경쟁한다. 세 스레드 가 동시에 빈 리스트를 발견하고 각자 alloc_block을 부르면, 한 블록 이면 충분한데 세 블록을 받게 된다.

백버퍼 패턴은 이렇다. 이미 만들어 둔 한 블록을 옆에 보관해 두고, available 리스트가 비면 백버퍼를 available 리스트로 원자적으로 swap 한 뒤, 새 백버퍼를 비동기적으로 만든다. 경쟁은 이제 한정된다. 백버퍼 swap은 정확히 한 스레드만 성공하고, 나머지는 swap이 끝났음을 보고 available 리스트를 다시 시도하는데, 그때쯤이면 방금 swap된 블록이 거기 있다.

CUBRID의 free list는 백버퍼 사전 할당을 적극적으로 돌린다. 모든 성공한 swap에서 free list가 즉시 다음 백버퍼를 할당한다. 그래서 정상 상태에서는 free list가 메모리 두 블록을 들고 있다. 한 블록은 m_available_list, 한 블록은 m_backbuffer_*.

on_reclaim — 재활용 전 타입 정리

raw 바이트(단순히 malloc/free로부터의 void*)만 재활용하는 free list는 할당기에 계약을 부과하지 않는다. 타입드 free list는 사용 사이 에 타입이 자기 자신을 정리하게 해야 한다. 파일 핸들 닫기, 부 할당 해제, 상태 청소 같은 일이다. free list가 강제하는 모양은 다음과 같다.

• 페이로드 타입 T는 on_reclaim() 메서드를 선언해야 한다(템플릿 인스턴스화에서 SFINAE로 컴파일 타임 확인).
• free list의 reclaim()이 노드를 available 리스트로 push하기 전에 m_t.on_reclaim()을 부른다.

lockfree::hashmap의 freelist_node_data이 정통 예시다. on_reclaim이 테이블별 lf_entry_descriptor::f_uninit 콜백을 부른다. 따라서 해시맵 엔트리의 사용자 정의 소멸자(부 뮤텍스 해제, 페이로드 버퍼 free 등)가 모든 재활용에서 돈다.

DBMS 공통 설계 패턴

자료구조별 free list

모든 DBMS는 락프리 엔트리에 풀링된 할당기를 쓴다. 매 삽입에 malloc, 매 삭제에 free는 너무 느리다. 모양은 다음과 같다.

• PostgreSQL은 수명별 키잉(top-level / per-transaction / per-tuple) 된 MemoryContext arena를 쓴다. 락프리 아님. 컨텍스트는 백엔드 단위.
• InnoDB는 mem_heap_t arena + 해시 엔트리용 사적 free list (hash_table_t::heap)를 쓴다. 뮤텍스 보호.
• MySQL은 고정 크기 객체용 슬랩 할당기를 가진다.
• CUBRID는 락프리 해시맵마다(그리고 풀링된 타입드 노드를 원하는 다른 자료구조마다) free list 한 개를 두고, tran::table 회수 위에 올라탄다.

CUBRID 접근은 자료구조별이다. 스레드별이나 트랜잭션별이 아니다. 트레이드오프: 각 해시맵이 자기 풀을 자기 낭비율로 가지지만, 풀들이 자료구조 사이로 새지 않는다(해시맵을 은퇴시키면 자기 free list만 청소된다).

블록 할당기 + 백버퍼

한 번에 K 객체 할당, 블록으로 push 패턴은 표준이다. “한 블록을 옆에 보관” 변종은 보편적이지 않다. Java의 ConcurrentLinkedDeque는 이를 안 한다. Folly의 SmallVector는 한다(용량이 두 배로 커지고, 새 버퍼를 옛것이 비기 전까지 옆에 보관). CUBRID free list가 백버퍼 편에 있는 이유는, 전형적인 워크로드가 버스트 은퇴(vacuum sweep, 해시맵 clear)와 버스트 claim(replay, repopulate)이 번갈아 일어나 기 때문이다. 백버퍼가 그 비대칭을 흡수한다.

학술 ↔ CUBRID 매핑

개념	CUBRID 이름
타입드 노드 풀	lockfree::freelist<T>
풀 노드	freelist<T>::free_node (tran::reclaimable_node 상속)
Available 스택 head	m_available_list (std::atomic<free_node *>)
백버퍼 head/tail	m_backbuffer_head, m_backbuffer_tail (std::atomic<free_node *>)
블록 크기(init 매개변수)	m_block_size (≥ 2 강제)
On-reclaim 훅	T::on_reclaim () (호출자 제공)
풀별 회수	m_trantable (모든 free list가 자기 tran::table 소유)
Available에서 할당	pop_from_available ()
Swap으로 할당	swap_backbuffer ()
강제 할당	force_alloc_block () (백버퍼 우회)
통계: alloc 수	m_alloc_count
통계: available 수	m_available_count
통계: 백버퍼 수	m_bb_count
통계: 강제 할당 수	m_forced_alloc_count
통계: 은퇴 수	m_retired_count

CUBRID의 구현

두 클래스 — freelist<T>와 freelist<T>::free_node

// lockfree::freelist<T> — src/base/lockfree_freelist.hpp:42
template <class T>
class freelist {
public:
  class free_node;

  freelist () = delete;
  freelist (tran::system &transys, size_t block_size, size_t initial_block_count = 1);
  ~freelist ();

  free_node *claim (tran::descriptor &);
  free_node *claim (tran::index);

  void retire (tran::descriptor &, free_node &);
  void retire (tran::index, free_node &);

  // 통계:
  size_t get_alloc_count () const;
  size_t get_available_count () const;
  size_t get_backbuffer_count () const;
  size_t get_forced_allocation_count () const;
  size_t get_retired_count () const;
  size_t get_claimed_count () const;       // = alloc - (available + backbuffer + retired)

  tran::system &get_transaction_system ();
  tran::table  &get_transaction_table ();

private:
  tran::system &m_transys;
  tran::table  *m_trantable;          // 소유: 소멸자에서 delete
  size_t        m_block_size;
  std::atomic<free_node *> m_available_list;
  std::atomic<free_node *> m_backbuffer_head;
  std::atomic<free_node *> m_backbuffer_tail;
  std::atomic<size_t>      m_available_count;
  std::atomic<size_t>      m_alloc_count;
  std::atomic<size_t>      m_bb_count;
  std::atomic<size_t>      m_forced_alloc_count;
  std::atomic<size_t>      m_retired_count;

  void swap_backbuffer ();
  void alloc_backbuffer ();
  void force_alloc_block ();
  void alloc_list (free_node *&head, free_node *&tail);
  void dealloc_list (free_node *head);
  free_node *pop_from_available ();
  void push_to_list (free_node &head, free_node &tail, std::atomic<free_node *> &dest);
  void clear_free_nodes ();
  void final_sanity_checks () const;
  void check_my_pointer (free_node *node);
};

// lockfree::freelist<T>::free_node — src/base/lockfree_freelist.hpp:104
template <class T>
class freelist<T>::free_node : public tran::reclaimable_node {
public:
  free_node ();
  ~free_node () = default;
  T &get_data ();
  void reclaim () final override;       // delete 대신 재활용
private:
  friend freelist;
  void set_owner (freelist &m_freelist);
  void set_freelist_next (free_node *next);
  void reset_freelist_next ();
  free_node *get_freelist_next ();
  freelist *m_owner;
  T m_t;                                 // 페이로드
};

free_node이 tran::reclaimable_node을 상속하므로, 은퇴된 노드는 디스크립터의 은퇴 링 위에서 상속받은 m_retired_next 필드로 산다. 회수가 결국 발화하면, 상속받은 reclaim() 가상 함수가 노드를 m_available_list로 다시 push하는 재활용 경로다.

m_retired_next의 영리한 오버로드:

• 노드가 디스크립터의 은퇴 링 위에 있는 동안 m_retired_next은 retire-ring 링크다.
• 노드가 free list의 available 리스트 위에 있는 동안 m_retired_next 은 free list 링크다.
• 노드는 한 번에 정확히 그 둘 중 하나에 있을 뿐이므로, 필드는 재사용된다.

free_node::set_freelist_next와 get_freelist_next은 사적 접근자 이며, m_retired_next을 free list 링크로(올바른 반환 타입 free_node *로. 베이스의 reclaimable_node *이 아니라) 노출시킨다.

생성 — 적극적 사전 할당

// freelist<T>::freelist — src/base/lockfree_freelist.hpp:138
freelist (tran::system &transys, size_t block_size,
          size_t initial_block_count = 1)
  : m_transys (transys),
    m_trantable (new tran::table (transys)),     // 자기 tran 테이블 소유
    m_block_size (block_size),
    /* 카운터들은 0으로 초기화 */
{
  if (initial_block_count <= 1) {
    m_block_size /= 2;
    initial_block_count = 2;
  }

  alloc_backbuffer ();
  for (size_t i = 0; i < initial_block_count; i++)
    swap_backbuffer ();      // available 리스트 사전 채우기
}

init에서 세 가지가 일어난다.

1. free list가 공유 tran::system에서 자기 tran::table을 만든 다. 모든 free list가 별개의 회수 도메인이다. free list A에서 노드 은퇴가 free list B의 전역 tranid를 bump하지 않는다.
2. 블록 크기 최소 2, 초기 블록 수 최소 2 규칙. 호출자가 initial_block_count = 1을 요청하면, 생성자가 블록 크기를 절반 으로 나누고 블록 수를 두 배로 만든다. 이는 정상 상태에 백버퍼와 available 리스트에 항상 적어도 한 블록씩 있도록 보장한다.
3. init이 available 리스트를 initial_block_count 블록으로 적극 적으로 채운다. 백버퍼는 요청된 것보다 추가 한 블록이다. init 이후 free list는 메모리 initial_block_count + 1 총 블록을 가지 며, initial_block_count개가 즉시 claim 가능하다.

claim — 핫 할당 경로

// freelist<T>::claim (descriptor 형) — src/base/lockfree_freelist.hpp:291
free_node *claim (tran::descriptor &tdes)
{
  tdes.start_tran ();                           // 브래킷
  tdes.reclaim_retired_list ();                 // 분할 상환 정리

  free_node *node;
  size_t count = 0;
  for (node = pop_from_available (); node == NULL && count < 100;
       node = pop_from_available (), ++count) {
    // 백버퍼 할당기가 오래 선점됨 — swap 강제
    swap_backbuffer ();
  }
  while (node == NULL) {
    // 백버퍼도 여전히 실패; available에 직접 강제 할당
    force_alloc_block ();
    node = pop_from_available ();
  }

  m_available_count--;
  check_my_pointer (node);
  return node;
}

확장 사다리는 다음과 같다.

1. 빠른 경로. m_available_list에서 pop. 대부분의 호출이 여기서 성공.
2. 빈 available 리스트, pop이 NULL 반환. 최대 100 재시도 사이클. 각 사이클이 swap_backbuffer()을 불러 백버퍼의 블록을 available 리스트로 옮긴다. 백버퍼도 비어 있으면(swap과 재구축 사이에 백버퍼 할당기가 선점됨), swap_backbuffer은 no-op이고 다음 반복이 pop 을 다시 시도한다.
3. 빈-available + 빈-백버퍼 사이클 100회 후, 강제 할당. force_alloc_block이 alloc_list + push_to_list (m_available_list) 을 직접 한다. 백버퍼 프로토콜을 완전히 우회한다. “백버퍼 할당기 가 깊이 선점됨” 비상구다.

상단의 tdes.start_tran()이 EBR 브래킷이다. m_available_list의 모든 읽기, 모든 CAS-pop이 디스크립터의 트랜잭션 윈도우 안에서 일어 난다. 브래킷은 claim 안에서 닫히지 않는다. 계약은 트랜잭션 이 시작된 채로 남는다(헤더 주석)이다. 호출자가 트랜잭션을 종료할 책임을 진다(보통은 claim된 노드를 자료구조에 삽입하고 삽입 안에서 트랜잭션을 종료).

pop_from_available — 명시된 ABA 윈도우

// freelist<T>::pop_from_available — src/base/lockfree_freelist.hpp:322
free_node *pop_from_available ()
{
  free_node *rhead = NULL, *rhead_copy = NULL, *next;
  do {
    rhead = m_available_list;
    if (rhead == NULL) return NULL;
    next = rhead->get_freelist_next ();
    rhead_copy = rhead;
    // todo: this is a dangerous preemption point; if I am preempted here, and
    // thread 2 comes and does:
    //   - second thread gets same rhead and successfully moves m_available_list
    //     to next
    //   - third thread gets next and successfully moves m_available_list to
    //     next->next
    //   - second thread retires rhead. m_available_list becomes rhead and its
    //     next becomes next->next
    //   - I wake up, compare exchange m_available_list successfully because it
    //     is rhead again, but next will become the item third thread already
    //     claimed.
  } while (!m_available_list.compare_exchange_weak (rhead_copy, next));
  rhead->reset_freelist_next ();
  return rhead;
}

주석이 정통 ABA 시나리오를 그대로 명명한다. m_available_list의 CAS는 head가 다시 rhead인 경우에 성공한다. 그러나 rhead이 그 사이에 pop되고 은퇴되고 다시 push됐다면, 우리가 저장한 next 포인터 는 stale이고 우리가 리스트를 망가뜨린다.

완화책은 알고리즘이 아니라 시간이다. 은퇴된 노드는 다음 길을 거쳐야 한다.

1. 디스크립터의 은퇴 링,
2. min_active_tranid > retire_tranid 대기(어떤 리더의 트랜잭션 윈도우도 은퇴 이전이 아니라는 의미),
3. reclaim()으로 회수,
4. m_available_list로 다시 push.

백버퍼 패턴이 이 거리를 늘린다. 대부분의 은퇴자는 디스크립터의 은퇴 링 → reclaim() → free list의 available로 가지만, in-flight 백버퍼 블록이 있으면 백버퍼 블록은 swap_backbuffer이 그것을 available로 옮길 때까지 기다린다. 총 시간이 경험적으로 충분히 길어 서 pop_from_available의 ABA 윈도우가 실제로 부딪히지 않지만, 알고리즘으로 제거되는 것은 아니다.

주석의 todo 표시가 설계의 미해결 이슈다. 태그된 포인터 재설계 (head 포인터 상위 16비트를 세대 태그로) 는 윈도우를 닫지만 free_node * 정렬을 제약한다. CUBRID는 이를 도입하지 않았다. 백버퍼 시간이 운영 완화책이다.

swap_backbuffer — 옆 블록을 들여오기

// freelist<T>::swap_backbuffer — src/base/lockfree_freelist.hpp:169
void swap_backbuffer ()
{
  free_node *bb_head = m_backbuffer_head;
  if (bb_head == NULL) return;          // 누가 이미 swap

  free_node *bb_head_copy = bb_head;
  if (!m_backbuffer_head.compare_exchange_strong (bb_head_copy, NULL))
    return;                             // 누가 swap 중

  free_node *bb_tail = m_backbuffer_tail.exchange (NULL);
  assert (bb_tail != NULL);

  m_available_count += m_bb_count.exchange (0);
  push_to_list (*bb_head, *bb_tail, m_available_list);

  alloc_backbuffer ();                  // 다음 백버퍼 만들기 시작
}

프로토콜은 다음과 같다.

1. 백버퍼 claim. m_backbuffer_head을 현재 포인터에서 NULL로 CAS. 실패는 누가 이미 swap 중이라는 뜻. 진 사람은 즉시 반환.
2. Tail detach. m_backbuffer_tail을 NULL로 어토믹 exchange. pre-CAS head와 exchange된 tail이 splice할 블록을 한정한다.
3. Available로 splice. push_to_list이 표준 CAS-loop push다. tail->next = available_head로 set, available_head을 available_head에서 block_head로 CAS.
4. 다음 백버퍼 만들기 시작. alloc_backbuffer이 신선한 블록을 new하고 이제 빈 m_backbuffer_head/m_backbuffer_tail에 CAS-설치한다.

alloc_backbuffer이 다음 claimer로부터 malloc/init 비용을 숨긴다. swap_backbuffer이 반환할 때쯤이면 핫 패스(pop_from_available)는 이미 다시 채워졌고, 다음 swap의 대상 블록은 병렬로 만들어지고 있다.

force_alloc_block — 비상구

// freelist<T>::force_alloc_block — src/base/lockfree_freelist.hpp:213
void force_alloc_block ()
{
  free_node *new_head = NULL, *new_tail = NULL;
  alloc_list (new_head, new_tail);
  m_available_count += m_block_size;
  ++m_forced_alloc_count;
  push_to_list (*new_head, *new_tail, m_available_list);
}

백버퍼를 완전히 우회하고, 할당해서 available로 곧장 push한다. claim의 백버퍼-empty 루프 100회 탈출에서 발화. m_forced_alloc_count 로 추적되어 모니터링이 이 경로에 닿는 풀을 표시할 수 있다.

retire — 공개 은퇴 원시 함수

// freelist<T>::retire — src/base/lockfree_freelist.hpp:358
void retire (tran::descriptor &tdes, free_node &node)
{
  assert (node.get_freelist_next () == NULL);
  ++m_retired_count;
  check_my_pointer (&node);
  tdes.retire_node (node);                   // 디스크립터의 은퇴 링에 넘김
}

free list는 tdes.retire_node()에 위임한다. 이는 다음을 한다.

• 전역 tranid bump(start_tran_and_increment_id 경유).
• 디스크립터의 기존 은퇴 접두사 분할 상환 회수.
• 노드의 m_retire_tranid 스탬핑과 디스크립터의 은퇴 링 link.

free list의 m_retired_count은 전역 카운터(은퇴 시 atomic inc, 회수 시 atomic dec)다. 관찰성에는 유용하지만 정확성에는 아니다.

free_node::reclaim — 재활용 훅

// freelist<T>::free_node::reclaim — src/base/lockfree_freelist.hpp:523
void free_node::reclaim () final override
{
  m_t.on_reclaim ();                          // 페이로드의 정리 훅
  m_retired_next = NULL;                      // 은퇴 링에서 분리
  --m_owner->m_retired_count;
  ++m_owner->m_available_count;
  m_owner->push_to_list (*this, *this, m_owner->m_available_list);
}

세 단계.

1. 페이로드 정리. m_t.on_reclaim(). 해시맵의 freelist_node_data은 이로써 테이블별 lf_entry_descriptor::f_uninit을 부른다. 다른 소비자는 타입이 정의한 소멸자 같은 루틴.
2. 카운터. retired 감소, available 증가.
3. Push. m_available_list로 표준 CAS-loop push. 노드는 이제 pop_from_available에서 claim 가능하다.

final override 한정자는 의도적이다. 추가 오버라이드가 허용되지 않는다. 노드가 은퇴됨에서 claimable로 전이하는 유일한 장소다.

clear_free_nodes — 소멸자 정리. 스레드 안전 아님

// freelist<T>::clear_free_nodes — src/base/lockfree_freelist.hpp:267
void clear_free_nodes ()       // not thread safe!
{
  final_sanity_checks ();
  dealloc_list (m_backbuffer_head.load ());
  m_backbuffer_head = NULL;
  m_backbuffer_tail = NULL;
  dealloc_list (m_available_list.load ());
  m_available_list = NULL;
  m_available_count = m_bb_count = m_alloc_count = 0;
}

소멸자만 사용. 다른 스레드가 free list를 만지지 않는다고 가정. 헤더 주석이 이를 명시한다. 두 리스트로 들어가 각 free_node을 직접 delete하고 카운터를 0으로 만든다. final_sanity_checks (디버그에서만 활성)은 available + 백버퍼 카운트가 m_alloc_count 와 같음을 검증하고 두 리스트를 워크해 확인한다.

get_claimed_count — 파생 통계

free list는 m_alloc_count(이제까지 할당된 총수), m_available_count(현재 claim 가능), m_bb_count(현재 백버퍼에 있는 수), m_retired_count(현재 회수 대기 중) 을 추적한다. claimed 카운트 호출자가 현재 들고 있는 수 — 는 파생된다.

size_t get_claimed_count () const {
  size_t alloc = m_alloc_count;
  size_t unused = m_available_count + m_bb_count + m_retired_count;
  return (alloc > unused) ? (alloc - unused) : 0;
}

unused 합계 카운터는 seq_cst로 load된다. 산술이 트랜잭션 안이 아니므로, 빠른 retire와 claim 버스트가 일시적 음수(0으로 클램프)를 낼 수 있다. 모니터링용으로는 충분히 좋다.

컴포넌트 개요

flowchart LR
  Caller["호출자 (예: 해시맵 insert)"]
  Caller --> Claim["claim(tdes)"]
  Claim --> Pop["pop_from_available()"]
  Pop -- empty --> Swap["swap_backbuffer()"]
  Swap --> BB["m_backbuffer_head/tail"]
  Swap -.다음 alloc.-> AllocBB["alloc_backbuffer()"]
  Swap --> Avail["m_available_list"]
  Pop --> Avail
  Swap -- 여전히 empty --> Force["force_alloc_block()"]
  Force --> Avail

  Caller --> Retire["retire(tdes, node)"]
  Retire --> Tdes["tran::descriptor"]
  Tdes --> RetRing["m_retired_head/tail 링"]
  RetRing -.tranid bump + min-스캔.-> Reclaim["free_node::reclaim()"]
  Reclaim --> OnReclaim["T::on_reclaim()"]
  Reclaim --> Avail

  Avail --> Pop

통계 요약

카운터	의미	갱신 시점
m_alloc_count	이제까지 만든 free_node의 총 수	alloc_list (블록 alloc)
m_available_count	현재 m_available_list 위에 있는 수	pop_from_available (-1), reclaim (+1), swap (+block_size)
m_bb_count	현재 백버퍼 안	alloc_backbuffer (+block_size), swap (exchange로 0)
m_forced_alloc_count	백버퍼 비상구 발화 횟수	force_alloc_block
m_retired_count	어떤 디스크립터의 은퇴 링에 있는 수	retire (+1), reclaim (-1)

건강한 free list는 m_forced_alloc_count이 작고(이상적으로는 정상 상태에서 0), m_retired_count이 회수 지연으로 한정되며, m_available_count + m_bb_count이 한두 블록 크기 근처다.

Legacy LF_FREELIST와의 비교

legacy lf_freelist(lock_free.h:231+)는 같은 일을 다른 모양으로 한다.

struct lf_freelist {
  void *available;            // 단일 available 스택 head (Treiber)
  int   block_size;
  int   alloc_cnt;
  int   available_cnt;
  int   retired_cnt;
  LF_ENTRY_DESCRIPTOR *entry_desc;  // f_alloc/f_free 콜백 사용
  LF_TRAN_SYSTEM      *tran_system; // 공유 전역. 소유 아님
};

modern 설계와의 차이는 다음과 같다.

• 백버퍼 없음. legacy free list는 lf_freelist_claim이 lf_stack_pop (&freelist->available, edesc)이 NULL을 반환하면 lf_freelist_alloc_block으로 on-demand로 블록을 할당한다. 헤더 주석이 다중 스레드가 동시에 블록을 할당하려고 경쟁하는 점을 인정하며 block_size이 충분히 낮다면 받아들일 수 있다 (lock_free.c:840-842)고 한다.
• f_alloc/f_free 콜백 — new/delete 대신. 각 블록은 디스 크립터의 f_alloc을 엔트리별로 부르며 만들고, 회수는 f_free을 부른다. modern free list는 자기 타입드 할당을 소유한다.
• max_alloc_cnt 한도. legacy free list는 alloc_cnt을 추적 하고, entry_desc->max_alloc_cnt(기본 2,147,483,647)을 넘어 자라지 않는다. 한도 도달 시 retire가 일어나면, legacy lf_freelist_transport이 은퇴자를 재활용 대신 f_free한다. modern free list는 한도가 없다. 한 번 할당되면 free list 수명 동안 블록이 산다.
• 공유 LF_TRAN_SYSTEM. 단일 legacy LF_TRAN_SYSTEM이 같은 도메인 안의 다수 free list 아래에 깔린다. modern free list는 자기 tran::table을 소유. 회수 압력이 풀별이다.
• lf_freelist_transport이 legacy 회수 워커. 스레드별 은퇴 리스트 를 워크하며 이건 free(한도 초과)와 available로 옮김(여전히 한도 안)을 분류한다. modern 코드는 descriptor::reclaim_retired_list와 노드별 reclaim() 가상 함수를 부른다.

마이그레이션 경로: 해시맵 소비자가 (enable_new_lfhash로) legacy에서 modern 해시맵으로 넘어가면, 전역 LF_TRAN_SYSTEM + lf_freelist을 테이블별 tran::table + lockfree::freelist로 바꾼다. 동작은 관찰 적으로 같다(엔트리 claim, retire, 재활용). 부기는 더 단순하다.

메모리 순서

free list의 모든 어토믹은 seq_cst 기본값을 쓴다. 핫 연산은 다음 과 같다.

• m_available_list.compare_exchange_weak(pop과 push) — seq_cst.
• m_backbuffer_head.compare_exchange_strong(swap을 위한 백버퍼 claim) — seq_cst.
• m_backbuffer_tail.exchange(swap 도중 tail detach) — seq_cst.
• 카운터 ++ / -- / += — seq_cst RMW.

x86에서 seq_cst 오버헤드는 작다(추가 펜스 한두 개). ARM에서는 사소 하지 않다. acquire/release로 조이는 측정 캠페인은 없다.

소스 코드 가이드

공개 표면

• lockfree::freelist<T> (클래스 템플릿) — lockfree_freelist.hpp:42
• freelist::freelist (tran::system &, size_t, size_t) — :138
• freelist::~freelist — :259
• freelist::claim (tran::descriptor &) — :291
• freelist::claim (tran::index) — :284
• freelist::retire (tran::descriptor &, free_node &) — :358
• freelist::retire (tran::index, free_node &) — :351
• freelist::get_alloc_count / get_available_count / ... — :382+
• freelist::get_transaction_system / get_transaction_table — :433 / :440
• freelist<T>::free_node — :104
• free_node::get_data — :534
• free_node::reclaim — :523 (final override)

사적 내부

• freelist::swap_backbuffer — :169
• freelist::alloc_backbuffer — :194
• freelist::force_alloc_block — :213
• freelist::alloc_list — :227
• freelist::dealloc_list — :247
• freelist::pop_from_available — :322
• freelist::push_to_list — :368
• freelist::clear_free_nodes — :267
• freelist::final_sanity_checks — :447
• freelist::check_my_pointer — :476

위치 힌트 (2026-05-07 기준)

심볼	파일	라인
lockfree::freelist<T> (클래스 템플릿)	src/base/lockfree_freelist.hpp	42
freelist<T>::free_node (클래스)	src/base/lockfree_freelist.hpp	104
freelist::freelist (생성자)	src/base/lockfree_freelist.hpp	138
freelist::swap_backbuffer	src/base/lockfree_freelist.hpp	169
freelist::alloc_backbuffer	src/base/lockfree_freelist.hpp	194
freelist::force_alloc_block	src/base/lockfree_freelist.hpp	213
freelist::alloc_list	src/base/lockfree_freelist.hpp	227
freelist::~freelist	src/base/lockfree_freelist.hpp	259
freelist::clear_free_nodes	src/base/lockfree_freelist.hpp	267
freelist::claim (descriptor)	src/base/lockfree_freelist.hpp	291
freelist::pop_from_available	src/base/lockfree_freelist.hpp	322
freelist::retire (descriptor)	src/base/lockfree_freelist.hpp	358
freelist::push_to_list	src/base/lockfree_freelist.hpp	368
freelist::get_claimed_count	src/base/lockfree_freelist.hpp	418
free_node::reclaim	src/base/lockfree_freelist.hpp	523
lf_freelist_alloc_block (legacy)	src/base/lock_free.c	621
lf_freelist_claim (legacy)	src/base/lock_free.c	760
lf_freelist_retire (legacy)	src/base/lock_free.c	873
lf_freelist_transport (legacy)	src/base/lock_free.c	934

소스 검증 (2026-05-07 기준)

검증된 사실

• free list가 자기 tran::table을 소유한다. 생성자가 m_trantable = new tran::table (transys)을 lockfree_freelist.hpp:141에서 호출. 소멸자가 delete m_trantable 을 :261에서 호출.
• 블록 크기 최소 2. 생성자가 :152에서 assert (block_size > 1) 을 강제. :154-158의 initial_block_count <= 1 분기가 블록 크기 를 절반으로 나누고 카운트를 두 배로 만들어 init에 ≥ 2 블록을 보장.
• pop_from_available의 ABA 윈도우는 소스에 명시되어 있다. :336-342의 다중 라인 주석이 정확한 경쟁 시나리오를 묘사한다. 현재 구현에 태그된 포인터 완화책 없음.
• force_alloc_block은 백버퍼-empty 사이클 100회 후 비상구. claim이 :298에서 100 swap 시도까지 루프하다가 :306의 force_alloc_block while-loop으로 빠진다.
• free_node::reclaim은 final override. lockfree_freelist.hpp:112에 선언. 추가 오버라이드 허용 없음.
• 통계는 seq_cst 어토믹. 모든 카운터(m_alloc_count, m_available_count, m_bb_count, m_forced_alloc_count, m_retired_count)가 :82-86에서 std::atomic<size_t>로 선언.
• claim은 트랜잭션을 종료하지 않는다. :53의 헤더 주석이 “transaction will remain started!”이라고 한다. 호출자가 종료 책임.
• free 노드의 m_retired_next이 free list 링크로 재사용된다. :502-518의 set_freelist_next / get_freelist_next이 상속받은 tran::reclaimable_node::m_retired_next을 캐스트해 노출.

풀리지 않은 질문

1. pop_from_available ABA 윈도우가 운영에서 부딪힌 적 있는가? 주석은 명시되어 있다. 양쪽 모두에 대한 테스트 증거는 없다. 타깃된 스트레스 테스트(next 읽기와 CAS 사이에 워커 스레드에 의도적 SIGSTOP/SIGCONT)가 경험적 답을 알려줄 것이다. 운영 머신-년 N년 동안 부딪히지 않았다면 백버퍼 시간이 사실상의 완화책이다. 부딪혔다면 태그된 포인터 재설계의 우선순위가 올라간다.
2. swap-loop 한도의 매직 넘버 100은 왜? force_alloc_block으로 빠지기 전 count < 100 한도가 소스에 동기 부여되어 있지 않다. 경험적으로 튜닝됐을 수도, 자리 잡이용일 수도 있다. 스트레스 아래에서 초점 잡힌 리뷰가 가치 있다.
3. legacy와의 할당 한도 패리티. legacy lf_freelist은 entry_desc->max_alloc_cnt을 존중한다. modern freelist<T>은 한도가 없다. 한 번 블록이 할당되면 free list 수명 동안 산다. 장기 가동 서버에서 버스트 부하라면 메모리 워터마크 우려다. 조사: 어떤 소비자가 메모리를 한정하기 위해 legacy 한도에 의존 하는가? 그렇다면 modern free list는 한도 + 축소 경로가 필요하다.
4. alloc_backbuffer이 NULL 기대값으로 compare_exchange_strong 을 쓰는 점. :204에서 함수가 m_backbuffer_tail.compare_exchange_strong (dummy_null, new_bb_tail)을 한다. tail이 현재 NULL일 때만 성공 (swap_backbuffer이 tail을 NULL로 exchange한 직후가 그렇다. 첫 init 호출에서도 tail이 NULL). 그러나 두 번째 alloc_backbuffer 가 (예: 거의 동시 두 swap에서) 경쟁하면? CAS는 실패하고, 두 번째 alloc_backbuffer은 이미 설치된 백버퍼 head로 push_to_list 할 것이다. 그 경쟁 아래에서의 동작은 그럴듯하지만 분명히 옳지는 않다. 초점 잡힌 리뷰가 가치 있다.
5. 부하 아래의 final_sanity_checks 불변식. :447-472의 디버그 전용 검사가 m_available_count + m_bb_count == m_alloc_count을 단언한다. m_retired_count을 무시한다. 즉 소멸 시점에 in-flight retire가 없음을 가정한다. 소멸자는 모든 소비자가 free list 사용 을 멈춘 후(via clear_free_nodes) 도므로 합리적인 사전 조건이다. 그러나 미래 변경이 final_sanity_checks을 수명 중에 부른다면 단언은 잘못이다.

CUBRID 너머 — 비교 설계와 연구 프론티어

• pop_from_available ABA 윈도우 닫기 위한 태그된 포인터. free_node *의 상위 비트(또는 std::atomic<__int128>)에 16비트 세대 카운터를 넣는다. 모든 push가 태그를 bump하고, 모든 pop이 태그 동등성을 검사. 명시된 ABA 위험을 포인터 산술 규율 비용으로 제거.
• Hazard-pointer 기반 free list (Michael 2004). pop된 노드용 스레드별 hazard pointer 슬롯. 어떤 스레드도 그 주소를 hazard로 들고 있지 않을 때만 회수. 핫 워크로드에서 EBR보다 싼 read-side 발행.
• CPU별 샤드된 free list와 stealing. 단일 m_available_list을 CPU별 한 개로 교체(sched_getcpu()). 로컬에서 할당. 로컬이 비면 이웃에서 훔침. head 포인터 위 캐시 라인 튕김을 제거하지만, 더 많 은 메모리와 더 복잡한 sanity-check 회계가 든다.
• 노드별 리스트 대신 연결된 블록 리스트. free list의 available 리스트가 개별 노드가 아니라 노드 블록의 리스트가 될 수 있다. 각 블록이 K 노드를 들고, pop이 head 블록에서 한 노드를 줌(빈 블록은 다음으로 이동). CAS 빈도가 K로 줄어든다. 캐시 라인의 단위가 노드 가 아니라 블록이 되어야 한다.
• 한도 + 축소. in-use 카운트의 high-water mark를 추적해, free list가 과잉 공급되면(in-use가 할당된 양보다 훨씬 작으면) clear 나 유지보수 데몬 틱에서 축소. legacy 패리티 갭(open question 3) 을 닫는다.

출처

• 소스 파일 (CUBRID 소스 트리, /data/hgryoo/references/cubrid/):
  • src/base/lockfree_freelist.hpp (헤더 전용 템플릿. 구현 전체)
  • src/base/lockfree_transaction_descriptor.hpp (freelist::claim/ retire이 올라타는 디스크립터)
  • src/base/lockfree_transaction_table.hpp (freelist이 내부적 으로 만드는 테이블)
  • src/base/lockfree_transaction_reclaimable.hpp (free_node이 상속받는 베이스 클래스)
  • src/base/lockfree_hashmap.hpp (주요 소비자. freelist<freelist_node_data> 경유)
  • src/base/lock_free.h, src/base/lock_free.c (legacy lf_freelist 대응)
• 인용한 교과서 챕터:
  • Herlihy & Shavit, The Art of Multiprocessor Programming, 11장 §Concurrent Stacks and Elimination — pop_from_available과 push_to_list의 핵심에 있는 Treiber- 스택 패턴.
• 기반 논문:
  • Treiber, R. K. “Systems Programming: Coping with Parallelism.” IBM Almaden RJ 5118, 1986 — 정통 Treiber 스택과 그 ABA 노출.
  • Michael, M. M. “Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects.” IEEE TPDS 15(8), 2004 — free list가 채택하지 않은 대안 회수 모델.
• 본 저장소의 자매 분석서:
  • cubrid-lockfree-overview.md — 우산 문서, 두 세대 지도.
  • cubrid-lockfree-transaction.md — free list가 플러그인되는 회수 프레임워크.
  • cubrid-lockfree-hashmap.md — 주요 소비자. freelist_node_data::on_reclaim을 설명.