From IdeA thinKING
요약
다양한 목적을 위해 간단히 사용할 수 있는 MemPool 클래스들을 작성합니다. 간단한 사용법은 다음과 같습니다.
class UserDefined : public MemPool<UserDefined> {
...
};
서론
C++ 에서 object를 new하거나 delete할때 메모리를 할당, 해제하는 작업은 기본적인 ::operator new와 ::operator delete를 사용하게 됩니다. 대부분의 경우 전혀 문제가 없습니다. 하지만 embedded 시스템과 같은 경우에는 메모리 단편화에 따른 메모리 부족이나 메모리를 할당, 해제하는 과정에 발생할 수 있는 성능 변화가 문제가 될 수 있습니다. (예를 들어 real-time 시스템에서는 특정 작업을 할때 소요되는 시간을 보장해야 할 경우들이 있습니다.) Embedded 시스템의 경우 대부분 object의 최대 필요 갯수를 미리 계산으로 알 수 있으므로 필요한 메모리를 미리 할당해 놓는 방식을 사용하면 이러한 단편화나 성능 변화에 따른 문제를 없앨 수 있습니다.
프로그램에 따라 ObjectPool과 같은 클래스를 따로 두어 이러한 문제를 해결할 수도 있으나 이미 작성되어 있는 프로그램에 적용하기에는 많은 부분의 코드를 변경해야 하며 사용법을 새로 익혀야 하는 등의 문제가 있습니다. 이 글에서는 이미 작성되어 있는 클래스에 base class를 하나 추가함으로써 위와 같은 내용을 적용할 수 있는 클래스를 작성해 보겠습니다.
MemPoolClass - 하나의 클래스만을 위한 MemPool
배경 지식
제일 먼저 하나의 클래스만을 위해 동작하는 MemPool을 작성해보겠습니다. 기본적인 idea는 간단합니다. MemPool 클래스에 class-specific한 operator new와 operator delete를 구현하여 이 클래스를 상속받는 모든 클래스는 이 operator들을 사용하게 하는 것입니다. 이때 문제는 어떻게 MemPool 클래스가 자신을 상속받을 클래스의 size를 미리 아는가 하는 것입니다.
이는 curiously recursive template이라고 알려진 방법을 통해 다음과 같이 해결할 수 있습니다.
template <class T>
class MemPool {
public:
static void* operator new(std::size_t size);
static void operator delete(void* p);
...
};
class UserDefined : public MemPool<UserDefined> {
...
};
이 방법을 통해 MemPool 클래스에서는 sizeof(T)로 자신을 상속받는 클래스의 size를 알 수 있습니다.
이제 operator new와 operator delete를 구현하기 위해 필요한 정보들을 알아봅시다.
먼저 미리 여러개의 sizeof(T)를 담을 수 있는 메모리를 한꺼번에 확보한 후 필요할 때 하나씩 꺼내주는 방법을 사용하여 메모리 단편화를 막을 수 있습니다.
다음으로 operator new에서 요청한 메모리를 복잡한 검색 없이 바로 찾을 수 있도록 사용하지 않고 있는 메모리 chunk들을 연결하고 있는 singly linked list를 사용할 수 있습니다.
예를 들어 초기 3개를 위한 메모리만을 할당하는 MemPool이라고 가정하면 메모리 상태는 다음과 같습니다.
free(1) -> [1. next(2) | buffer] -> [2. next(3) | buffer] -> [3. next(0) | buffer]
하나의 메모리 chunk는 next pointer와 실제 데이터를 담을 buffer로 이루어지고 각 chunk의 제일 앞 부분은 next pointer가 들어 있습니다. 그리고 각 next pointer는 다음 chunk의 제일 앞 부분을 가리키게 됩니다. 괄호안의 숫자는 가리키고 있는 메모리의 주소를 나타냅니다. 마지막 chunk의 next pointer는 마지막임을 나타내기 위해 0이 들어 있습니다.
이때 operator new가 불리게 되면 free pointer가 가리키고 있는 1번 주소를 return하고 free는 아래와 같이 그 다음 메모리 chunk인 2번을 가리키게 됩니다.
free(2) -> [2. next(3) | buffer] -> [3. next(0) | buffer]
한번 더 operator new가 불리게 되면 다음과 같은 그림이 됩니다.
free(3) -> [3. next(0) | buffer]
이때 1번 주소에 대해 operator delete가 불리면 이 1번을 free에 할당하고 1번의 next에는 현재 free가 가리키고 있는 3번을 할당하게 됩니다.
free(1) -> [1. next(3) | buffer] -> [3. next(0) | buffer]
만약 세개의 메모리 chunk가 다 사용이 되면 그림은 다음과 같이 바뀝니다.
free(0)
이때 다시 operator new가 불리면 어떻게 해야 할까요? 이때는 다음과 같이 새로 3개의 sizeof(T)를 위한 메모리를 할당합니다.
free(4) -> [4. next(5) | buffer] -> [5. next(6) | buffer] -> [6. next(0) | buffer]
그리고 아까 방식대로 제일 처음의 메모리 chunk를 돌려줍니다.
free(5) -> [5. next(6) | buffer] -> [6. next(0) | buffer]
이때 다시 1번 주소에 대해 operator delete가 불린다면? 역시 아무 문제가 없습니다. 어차피 모두 pointer를 사용하고 있으니 처음 할당했던 메모리건 나중에 할당했던 메모리건간에 서로 pointer로 가리키고 있으면 되니까요.
free(1) -> [1. next(5) | buffer] -> [5. next(6) | buffer] -> [6. next(0) | buffer]
이런 식으로 MemPool은 동작하게 됩니다. 덧붙여서 위의 그림들에서는 next를 위한 pointer를 따로 두고 사용하는 것처럼 그려졌지만 실제론 buffer의 제일 앞 부분을 next pointer로 사용하게 됩니다. 따라서 실제 사용할 크기외의 크기상의 overhead는 없습니다.
상세 구현
위에서 살펴본 내용을 바탕으로 다음과 같이 MemPoolClass를 만들어 보기로 합니다. MemPool뒤에 붙은 'Class'는 하나의 클래스에만 사용되는 MemPool임을 나타냅니다.
기본 구현
위의 내용을 모두 이해했다면 구현은 매우 간단합니다. 새로 들어간 template parameter인 OBJS_IN_A_BLOCK는 메모리 chunk가 부족할 때 한꺼번에 할당할 object의 갯수입니다. (위의 배경지식에서 3 으로 가정했던 숫자입니다.)
template <class T, int OBJS_IN_A_BLOCK = 50>
class MemPoolClass
{
public:
static void* operator new (size_t size) {
if (free_ == 0) {
allocate_block();
}
unsigned char* p = free_;
free_ = *reinterpret_cast<unsigned char**>(p);
return p;
}
static void operator delete (void* p) {
*reinterpret_cast<unsigned char**>(p) = free_;
free_ = static_cast<unsigned char*>(p);
}
private:
static void allocate_block() {
free_ = new unsigned char[sizeof(T) * OBJS_IN_A_BLOCK];
unsigned char** curr = reinterpret_cast<unsigned char**>(free_);
unsigned char* next = free_;
for (int i = 0; i < OBJS_IN_A_BLOCK - 1; ++i) {
next += sizeof(T);
*curr = next;
curr = reinterpret_cast<unsigned char**>(next);
}
*curr = 0;
}
static unsigned char* free_;
};
template <class T, int OBJS_IN_A_BLOCK>
unsigned char* MemPoolClass<T, OBJS_IN_A_BLOCK>::free_;
다양한 casting이 좀 복잡해 보이지만 실제론 배경지식에서 살펴봤던 내용을 그대로 코드로 옮긴 것입니다. 따라서 자세한 설명은 하지 않습니다.
문제점1 - sizeof(T) < sizeof(unsigned char*)인 경우
위의 코드는 몇가지 문제점을 가지고 있습니다. 첫번째로 위의 클래스는 buffer 부분의 제일 앞을 unsigned char pointer로 사용하고 있기 때문에 sizeof(T) < sizeof(unsigned char*) 일 경우 MemPool에서 사용하는 singly linked list가 제대로 동작하지 않게 됩니다.
이 문제를 해결할 수 있는 방법에는 몇가지가 있을 수 있습니다.
Modern C++ Design의 SmallObject 부분에 나온 방법으로 singly linked list에 pointer 대신 char 타입을 사용하는 것입니다. 이 방법을 사용하면 한 MemPool안에 가질 수 있는 chunk의 갯수는 255개로 제한되며 이를 극복하기 위해서는 책에 나온 것과 같은 layered 구조가 필요합니다.
sizeof(T) < sizeof(unsigned char*) 인 경우 강제로 sizeof(T)를 sizeof(unsigned char*)만큼으로 생각하여 메모리를 할당하는 것입니다. 하지만 이 경우에는 실제 사용되는 메모리에 비해 크기상의 낭비가 심합니다.
마지막으로 sizeof(T)가 sizeof(unsigned char*)보다 작은 경우 컴파일 에러를 발생시켜 이런 작은 클래스에는 MemPoolClass를 사용할 수 없도록 하는 방법입니다.
여기서는 가장 간단한 마지막 방법을 사용합니다. 다음과 같이 컴파일 에러를 발생시키기 위해 BOOST_STATIC_ASSERT를 사용할 수 있습니다. (boost는 기본적으로 설치되어 있을거라 생각하겠습니다.)
#include <boost/static_assert.hpp>
...
private:
static void allocate_block() {
BOOST_STATIC_ASSERT(sizeof(T) >= sizeof(unsigned char*));
...
문제점2 - 멀티 쓰레드 환경 고려
다음 문제로는 위의 클래스가 멀티 쓰레드 환경에서 사용될 때 적절한 lock이 필요하다는 사실입니다. 여기서는 policy-based design을 적용해보도록 하겠습니다. 기본적인 idea는 Modern C++ Design에 나왔던 내용을 바탕으로 하나 실제 Lock을 사용할 함수가 static 이기 때문에 인자가 없는 방식으로 변경하였습니다. 쓰레드 관련 라이브러리로는 역시 boost thread 라이브러리를 사용합니다.
template <class T>
class MTLock
{
friend class Lock;
public:
class Lock
{
public:
Lock() : lock(T::mutex_) {
}
private:
boost::mutex::scoped_lock lock;
};
private:
static boost::mutex mutex_;
};
template <class T>
boost::mutex MTLock<T>::mutex_;
template <class T>
class NoLock
{
public:
class Lock
{
};
};
이렇게 만든 Lock policy 클래스들을 사용하기 위해 MemPoolClass의 선언을 다음과 같이 수정합니다.
template <
class T,
int OBJS_IN_A_BLOCK = 50,
template <class> class LockModel = NoLock
>
class MemPoolClass : public LockModel<T>
{
...
위의 코드에서 보이는 것과 같이 기본 LockModel은 NoLock입니다. MemPoolClass에서 Lock을 사용해야 하는 곳은 free_ 멤버 변수를 사용하고 있는 operator new와 operator delete 입니다. 따라서 두 함수에 다음과 같이 적용합니다.
static void* operator new (size_t size) {
Lock lk; lk;
...
}
static void operator delete (void* p) {
Lock lk; lk;
...
}
Lock lk; 뒤에 다시 한번 lk를 써준 이유는 unused varible warning을 없애기 위해서입니다.
(여기서 LockModel 클래스들은 template 없이도 구현이 가능하나 나중에 object-based lock도 구현할 수 있도록 하기 위해 남겨두었습니다.)
문제점3 - MemPoolClass pointer에 대한 delete
다음 문제로 MemPoolClass는 destructor가 virtual이 아니기 때문에 다음과 같은 코드는 UserDefined클래스의 destructor가 제대로 호출되지 않는 문제가 있습니다.
class UserDefined : public MemPoolClass<UserDefined>
{
...
};
MemPoolClass<UserDefined>* p = new UserDefined;
delete p;
물론 MemPoolClass에 destructor를 virtual로 만들게 되면 해결되나 이렇게 수정할 경우 UserDefined 클래스의 크기가 쓸데없이 커질 수 있는 문제가 있습니다. 따라서 이 문제는 널리 알려진대로 destructor를 protected로 만들어서 해결합니다.
class MemPoolClass : public LockModel<T>
{
...
protected:
~MemPoolClass() {}
문제점4 - Leaf가 아닌 클래스에서 MemPoolClass를 상속받은 경우
마지막 문제를 알아보기 위해 다음과 같이 leaf가 아닌 클래스에서 MemPoolClass를 상속받는 경우를 생각해 봅시다.
class B : MemPoolClass< B>
{
char b[100];
};
class D : public B
{
char d[100];
};
D* d = new D;
여기서 실제로 D는 200바이트의 메모리가 필요하지만 MemPoolClass는 sizeof(B)를 가지고 생성되었기 때문에 return되는 메모리의 크기는 100바이트가 됩니다. (D는 B의 operator new와 operator delete를 사용하게 됩니다.)
이렇게 MemPoolSize는 항상 leaf 클래스에서만 사용되어야 함을 강제하기 위해서 assertion을 사용합니다. 이 경우엔 굳이 exception을 사용하지 않는 이유는 사용자의 코드가 D 클래스의 new를 한번만 하더라도 assertion error가 발생하기 때문에 쉽게 DEBUG 모드에서 찾을 수 있기 때문입니다. 물론 아시다시피 assertion은 RELEASE 모드에서는 runtime overhead가 전혀 없습니다.
수정된 코드는 아래와 같습니다.
static void* operator new (size_t size) {
assert(sizeof(T) == size);
...
디버깅 지원
MemPoolClass를 사용하면서 실행 중간에 현재 이 클래스의 object가 몇개나 new 되었는지 현재 사용가능한 chunk의 갯수는 몇개인지 안다면 디버깅에 도움이 될 수 있습니다. 따라서 다음과 같이 capacity()와 size()함수를 추가합니다. (이름은 눈치채셨듯이 std::vector에서 따왔습니다.)
class MemPoolClass : public LockModel<T>
{
...
static void* operator new (size_t size) {
Lock lk; lk;
++size_;
...
static void operator delete (void* p) {
Lock lk; lk;
if (size_ == 0) throw std::runtime_error("delete invalid pointer");
--size_;
...
static size_t capacity() {
return capacity_;
}
static size_t size() {
return size_;
}
private:
static void allocate_block() {
...
capacity_ += OBJS_IN_A_BLOCK;
}
...
static int capacity_;
static int size_;
};
...
template <class T, int OBJS_IN_A_BLOCK, template <class> class LockModel>
int MemPoolClass<T, OBJS_IN_A_BLOCK, LockModel>::capacity_;
template <class T, int OBJS_IN_A_BLOCK, template <class> class LockModel>
int MemPoolClass<T, OBJS_IN_A_BLOCK, LockModel>::size_;
만약 size_가 0보다 작아지는 경우는 어디선가 new 한 갯수보다 delete 한 갯수가 많은 문제가 발생한 것이므로 exception을 발생시킵니다. 위에서는 std::runtime_exception을 사용했습니다.
위에서 추가한 변수들을 사용하면 현재 할당된 메모리의 크기를 알 수 있으므로 사용자가 클래스 사용전에 원하는 만큼의 크기를 미리 할당할 수 있는 reserve() 함수를 구현할 수 있습니다. (역시 std::vector에서 이름을 따왔습니다.)
static void reserve(size_t size) {
Lock lk; lk;
if (capacity_ > size) return;
size_t needed = size - capacity_;
size_t count = needed / OBJS_IN_A_BLOCK;
if (needed % OBJS_IN_A_BLOCK != 0) ++count;
for (size_t i = 0; i < count; ++i) {
allocate_block();
}
}
위처럼 free_가 0이 아닌 경우에도 allocate_block()를 사용하기 위해서는 약간의 수정이 필요합니다.
static void allocate_block() {
...
unsigned char* prev = free_;
...
*curr = prev;
...
}
이 함수를 사용하여 만약 UserDefined라는 클래스의 object가 최대 10,000개까지 사용된다는 것을 알고 있다면 다음과 같이 10,000개를 위한 메모리를 미리 할당할 수 있습니다. 이런 방법으로 operator new와 delete의 수행 시간을 deterministic하게 만들 수 있습니다.
UserDefined::reserve(10000);
사용 예제
다음 사용 예제 코드를 참고하세요.
struct A : MemPoolClass<A>
{
char buf[99];
};
struct B : MemPoolClass< B>
{
char buf;
};
struct C : MemPoolClass<C, 100, MTLock>
{
char buf[99];
};
int main()
{
A::reserve(70);
cout << A::capacity() << endl;
A* a = new A;
//B* b = new B; ---- (1)
MemPoolClass<A>* p = new A;
//delete p; ---- (2)
}
- sizeof(B) < sizeof(unsigned char*) 이므로 BOOST_STATIC_ASSERT에 의해 에러 발생
- MemPoolClass의 소멸자가 protected이므로 에러 발생
마무리
이 글에서는 하나의 클래스에 적용 가능한 MemPool을 구현해 보았습니다. 다음 글에서는 여러 클래스가 한 MemPool을 공유할 수 있는 방법에 대해 알아보겠습니다.
