C++ Lock-free 메모리풀 구현

이전 글에서는 메모리풀의 개념과 싱글 스레드에서 사용할 메모리풀을 구현해 보았습니다. 이번 글은 thread-safe 한 메모리풀을 구현해 볼겁니다! 😄

✅ mutex 와 lock-free 로 만들 수 있는데 이번 글은 lock-free 를 이용해서 만들겠습니다.

🚀 Lock-free 메모리풀

✨ 공유 자원 _header 및 CAS 문제 해결을 위해 Tag 추가

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#ifndef __LF_MEMORY_POOL_H__
#define __LF_MEMORY_POOL_H__

#include<algorithm>
#include<cstring>
#include<atomic>

template<typename T, size_t capacity = 1024>
class LFMemoryPool {
    struct LinkedList {
        LinkedList *next;
    };
    using TaggedLinkedList = std::pair<LinkedList *, uint64_t>;

    static constexpr size_t alignment = std::max(alignof(T), alignof(LinkedList));
    static constexpr size_t blockSize = std::max(sizeof(T), sizeof(LinkedList));

public:
    LFMemoryPool()
        : _chunk{0,}
        , _header({nullptr, 0}) {
        TaggedLinkedList header = _header.load(std::memory_order_relaxed);

        header.first = reinterpret_cast<LinkedList*>(&_chunk[0]);
        _header.store(header, std::memory_order_relaxed);

        for(size_t idx = 0; idx < capacity - 1; idx++) {
            reinterpret_cast<LinkedList*>(&_chunk[idx * blockSize])->next = reinterpret_cast<LinkedList*>(&_chunk[(idx + 1) * blockSize]);
        }
        reinterpret_cast<LinkedList*>(&_chunk[(capacity - 1) * blockSize])->next = nullptr;
    }
    ~LFMemoryPool() {}

    T *allocate() {
        TaggedLinkedList header = _header.load(std::memory_order_relaxed);
        TaggedLinkedList desire;
        do {
            if(header.first != nullptr) {
                desire.first = header.first->next;
                desire.second = header.second + 1;
            } else {
                return nullptr;
            }
        } while(!_header.compare_exchange_weak(header, desire, std::memory_order_acquire, std::memory_order_relaxed));

        T *result = reinterpret_cast<T*>(header.first);
        return result;
    }

    void deallocate(T *p) {
        if(p) {
            TaggedLinkedList header = _header.load(std::memory_order_relaxed);
            TaggedLinkedList desire;
            do {
                reinterpret_cast<LinkedList*>(p)->next = header.first;
                desire.first = reinterpret_cast<LinkedList*>(p);
                desire.second = header.second + 1;
            } while(!_header.compare_exchange_weak(header, desire, std::memory_order_release, std::memory_order_relaxed));
        }
    }

    template<typename... Args>
    static void construct(T* p, Args&&... args) {
        ::new (p) T(std::forward<Args>(args)...);
    }

    static void destroy(T* p) {
        // 소멸자 호출 ($\text{T::\~T()}$)
        p->~T();
    }

private:
   alignas(alignment) char _chunk[blockSize * capacity];
   std::atomic<TaggedLinkedList> _header;
};

#endif //__LF_MEMORY_POOL_H__

✅ 13: CAS 성공할 때마다 태깅을 하기 위해 std::pair 타입으로 묶음
✅ 44, 58: CAS 연산 (thread-safe)

🧪 CAS 연산 성공시 메모리 순서를 acq_rel 이 아닌 acquire/release 인 이유
CAS 앞뒤로 읽고 쓰는 연산이 많아 버릇처럼 acq_rel을 사용했었는데 이는 잘못된 것
위 메모리풀은 CAS 연산 전에 모든 읽기/쓰기 연산이 끝남

✅ 정리

지금까지 메모리 가시성과 순서에 대한 개념을 확실하게 알지 못했었다.

🚀 Lock-free 메모리풀#

✅ 정리#

🚀 Lock-free 메모리풀

✅ 정리