Memory Pool Allocator

0

Hej,

Mam zagadkę, którą próbuje rozwikłać jak najefektywniej (problem z dealokacją).

Piszę memory allocatora, który może z własnej puli pamięci ustawionej na samym początku, przydzielać obiektom pamięć (o różnym rozmiarze) w czasie działania programu, aby uniknąć fragmentacji pamięci i też dla szybszego ogólnego działania programu:

Ogólnie wygląda to tak, jest blok pamięci, dwa wskaźniki na podstawę i szczyt apBaseAndCap[0-1], i dwa wskaźniki apFrame[0-1], które się przesuwają w zależności od ilości zaalokowanej pamięci:

 
typedef unsigned char u8;
typedef unsigned int uint;

#define ALIGNUP( nAddress, nBytes ) ( (((uintptr_t)nAddress) + (nBytes)-1) & (~((nBytes) -1 )) )

static int _nByteAlignment;		// alignment memory in bytes
static u8 *_pMemoryBlock;		// value returned by malloc()                   
static u8 *_apBaseAndCap[2];	// [0] ptr to base, [1] ptr to peak         
static u8 *_apFrame[2];		    // [0] ptr to lower frame, [1] ptr to higher frame    

// must be called once before start of the system
// nByteAlignment must by power of 2
// return 0 if success, or 1 if an error
int InitFrameMemorySystem(int nSizeInBytes, int nByteAlignment) {
    cout << "init" << endl;
	// nSizeInByte is a mulitiplicity of nByteAlignment
	nSizeInBytes = ALIGNUP(nSizeInBytes, nByteAlignment);
	
	// memory block allocation
	_pMemoryBlock = (u8*)malloc(nSizeInBytes + nByteAlignment);
	if(_pMemoryBlock == 0) {
		// there is no memory
		return 1;
	}
	
	_nByteAlignment = nByteAlignment;
	
	// set ptr to base
	_apBaseAndCap[0] = (u8*)ALIGNUP(_pMemoryBlock, nByteAlignment);                   
	
	// set ptr to peak
	_apBaseAndCap[1] = (u8*)ALIGNUP(_pMemoryBlock + nSizeInBytes, nByteAlignment);      
	
	// initialization of lower and higher frame
	_apFrame[0] = _apBaseAndCap[0];
    printf("lower frame : %d\n", _apFrame[0]);
	_apFrame[1] = _apBaseAndCap[1];
	printf("higher frame: %d\n", _apFrame[1]);
	// success
	return 0;
}

void ShutDownFrameMemorySystem() {
	free(_pMemoryBlock);
}

// return ptr to base of memory block
// or 0 if there is no more memory
// nHeapNum is the number of heap, 0=bottom, 1=peak
void * AllocFrameMemory(int nBytes, int nHeapNum) {
	// first make alignment to proper size
	nBytes = ALIGNUP(nBytes, _nByteAlignment);
    void * pMem;
	
    cout << "alloc nBytes: " << nBytes << " requested" << endl;

	// check if there is available memory
	if(_apFrame[0] + nBytes > _apFrame[1]) {
		// there is no memory
		return 0;
	}
	
	// memory allocation
	if(nHeapNum) {
		// allocation in higher heap, decrease ptr
		_apFrame[1] -= nBytes;
		pMem = _apFrame[1];
	}
	else {
		// allocation in lower heap, increase ptr
		pMem = _apFrame[0];
		_apFrame[0] += nBytes;
	}
	
    printf("allocated returning: %d\n", pMem);
    printf("alloc  lower frame : %d\n", _apFrame[0]);
	printf("alloc  higher frame: %d\n", _apFrame[1]);

	return (void*)pMem;
}

typedef struct {
	u8* pFrame;       // u8
    u8* ptrToAllocatedMemory;
	int nHeapNum;
} Frame_t;

// return frame (handler) which will be used 
// to free memory.
// nHeapNum is a heap number: 0=lower heap, 1=higher heap
Frame_t GetFrame(int nHeapNum) {
	Frame_t Frame;
	
	Frame.pFrame = _apFrame[nHeapNum];
	Frame.nHeapNum = nHeapNum;
	
	return Frame;
}

#define _HEAPNUM 1

Frame_t AllocateObject(int nSize, int nHeapNum) {
    Frame_t Frame;

    // allocate object
    Frame = GetFrame(_HEAPNUM);
    Frame.ptrToAllocatedMemory = (u8*)AllocFrameMemory(nSize, nHeapNum);
    if(Frame.ptrToAllocatedMemory == 0) {
        cout << " no more memory " << endl;
    }

    return Frame;
}

void ReleaseFrame(Frame_t Frame) {
	assert(Frame.nHeapNum == 1 || (uintptr_t)Frame.pFrame <= (uintptr_t)_apFrame[0]);
	assert(Frame.nHeapNum == 0 || (uintptr_t)Frame.pFrame >= (uintptr_t)_apFrame[1]);
	
	_apFrame[Frame.nHeapNum] = Frame.pFrame;
}

Alokacja śmiga, tylko mam problem z dealokacją.
Ponieważ powyższy system dostaje randomowy rozmiar z przedziału (16-1776 ) allokuje to jako int więc potrzebuje z allocatora np. 1776 x 4 = 7104b pamięci, więc allocator przydziela taki blok pamięci i przesyła to dalej do funkcji i zajmuje się nowym przydziałem pamięci.
Gdzieś indziej w systemie sobie siedzi deallocator, który musi zwolnić już nie potrzebną ramkę.
I moje pytanie, jak najefektywniej dla takiego przypadku napisać deallocator (release Frame) aby wiedział co ma zwolnić i aby uniknąć w tym allokatorze fragmentacji?

Lub może da się to zamienić na coś efektywniejszego, bo wszystko rozbija się o to, że w bardzo krótkim odstępie czasu jest allokowanych poprzez new dużo obiektów o różnym rozmiarze requestedSize:(16-1776) dla int * tmp = new int[requestedSize]; a gdzieś indziej są one zwalniane i przez to jest duża fragmentacja danych?

Dzięki za pomoc.

0

Aby uruchomić powyższy kod:

// jakies naglowki
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cassert>
#include <cstdint>


using namespace std;


int main() {
    int nSizeInBytes = (2000 * 32);
	InitFrameMemorySystem(nSizeInBytes, 2); // allocate block

    Frame_t Frame_1 = AllocateObject(1776, _HEAPNUM);
    Frame_t Frame_2 = AllocateObject(140, _HEAPNUM);
    Frame_t Frame_3 = AllocateObject(528, _HEAPNUM);
    Frame_t Frame_4 = AllocateObject(108, _HEAPNUM);
    Frame_t Frame_5 = AllocateObject(1776, _HEAPNUM);

    printf("available memory after alloc frame: %d\n", (_apFrame[1] - _apFrame[0]));

    ReleaseFrame(Frame_1);
    
    printf("available memory after dealloc frame: %d\n", (_apFrame[1] - _apFrame[0]));

    ShutDownFrameMemorySystem();    // deallocate memory block

	return 0;
} 

Kod dla testu, zonk będzie przy ReleaseFrame jak przy zwalnianiu ramki będzie już inna kolejność.

Dzięki za pomoc.

3

Pójdę na łatwizne i tylko zasugeruje poczytanie jak do problemu podeszli inni ludzie, np <a href=http://loki-lib.cvs.sourceforge.net/loki-lib/loki/include/loki/SmallObj.h?view=markup> Andrei Alexandrescu</a> na potrzeby swojej książki oraz jak zmodyfikował ten kod pan Rich Sposato. Daje to jakieś pojęcie jak zabrać się do tematu. No i jest też Boost

0

Dzięki za sugestię, poczytam.
Co do Boost to odpada, max co mogę wykorzystać to czysty C++ 11.

0

Nie musisz używać jak nie chcesz/nie możesz, ale boost jest opensource więc można coś od niego "zgapić" ;) Jeżeli dopiero poznajesz temat, to idealnym wg. mnie scenariuszem byłoby napisanie apki z alokatorem będącym cienkim wraperkiem nad czymś gotowym (SmallObjAllocator albo boost.pool), sprofilowanie valgrindem a potem zastąpienie bebechów czymś swoim.

1 użytkowników online, w tym zalogowanych: 0, gości: 1