ATP>Здравствуйте, remark, Вы писали:
ATP>Кстати Дмитрий, вы я смотрю хорошо разбираетесь в look-free алгоритмах. Не могли бы вы посмотреть на предмет look-free мой простенький аллокатор?
Полностью потокобезопасен, имеет всего три метода, при желании можно добавить нужные.
Из недостатков:
1. Имеет ограничение на максимальный объем выделяемого блока
2. Сначала набирает рабочий объем памяти используя стандартный метод аллокации
Allocate — выделить блок заданного размера
Free — освободить блок
Erase — освобождает весь текущий не используемый рабочий объем памяти
Использовался мной для переопределения стандартного new/delete. Быстрее стандартного в тысячи раз.
h.File:
////////////////////////////////////////////////////////////////////////
// class MemoryAllocator
////////////////////////////////////////////////////////////////////////class MemoryAllocator : public Mt::IAllocator
{
public:
////////////////////////////////////////////////////////////////////
// Construction/Destruction
MemoryAllocator(size_t nMaxAllocationBlockSize);
virtual ~MemoryAllocator();
////////////////////////////////////////////////////////////////////
// Implementation of IAllocator interfacevirtual void* Allocate(size_t nSize);
virtual void Free(void* pPointer);
virtual void Erase();
////////////////////////////////////////////////////////////////////
// Public methodsprivate:
/////////////////////////////////////////////////////////////////////
// Internal constants and type definitionsstruct MemoryPool;
struct MemoryBlock
{
MemoryPool* pPool; // Pointer to block owned pool
MemoryBlock* pNextBlock; // Pointer to next free memory block
};
struct MemoryPool
{
size_t nMaxSize; // Pool block maximum sizelong nAllocated; // Number of allocated blocks long nOccupied; // Number of occupied blocks
MemoryAllocator* pAllocator; // Pointer to owner memory allocator
MemoryBlock* pFirstBlock;// Pointer to first memory block
};
typedef MemoryPool* FreePools; // Holds pointers to first free blocks of memory pools
/////////////////////////////////////////////////////////////////////
// Protect class from coping
MemoryAllocator& operator=(const MemoryAllocator& reader);
/////////////////////////////////////////////////////////////////////
// Implementationstatic size_t GetMemoryPageSize();
static MemoryBlock* PointerToMemoryBlock(const void* pPointer);
static void* MemoryBlockToPointer(const MemoryBlock* pMemoryBlock);
static bool LockFreeCAS(MemoryBlock*& pCheck, MemoryBlock* pCompare, MemoryBlock* pNew);
static long LockFreeINC(long& nValue);
static long LockFreeDEC(long& nValue);
FreePools CreatePools() const;
MemoryPool* GetPool(size_t nSize) const;
void* AllocateMemoryBlock(MemoryPool* pMemoryPool) const;
/////////////////////////////////////////////////////////////////////
// Attributesconst size_t m_nMemoryPageSize; // Memory page sizeconst size_t m_nMinBlockSize; // Allocation block minimum size const size_t m_nMaxBlockSize; // Allocation block maximum size
FreePools m_pools; // Memory block poolsmutable size_t m_nPools; // Number of created pools
};
cpp.File:
////////////////////////////////////////////////////////////////////////
// class MemoryAllocator
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
// Construction/Destruction
MemoryAllocator::MemoryAllocator(size_t nMaxAllocationBlockSize)
: m_nMemoryPageSize(GetMemoryPageSize())
, m_nMinBlockSize(m_nMemoryPageSize / 8)
, m_nMaxBlockSize(nMaxAllocationBlockSize)
, m_pools(CreatePools())
{
}
MemoryAllocator::~MemoryAllocator()
{
Erase();
// Release pool array
::free(m_pools);
m_pools = NULL;
}
////////////////////////////////////////////////////////////////////////
// Implementation of IAllocator interfacevoid* MemoryAllocator::Allocate(size_t nSize)
{
MemoryPool* pMemoryPool = GetPool(nSize);
// Check does pool for specified block size existsif (pMemoryPool == NULL)
return NULL; // Block size is too large
// Statistic
LockFreeINC(pMemoryPool->nOccupied);
// Return newly allocated blockwhile (true) {
// Check if pool already has free memory block
MemoryBlock* pFreeBlock = pMemoryPool->pFirstBlock;
if (pFreeBlock == NULL) {
// Has no free block
// So we necessary to allocate new blockreturn AllocateMemoryBlock(pMemoryPool);
}
// Pool already has allocated free block(s)
// Trying to get first free block from pool
MemoryBlock* pNextBlock = pFreeBlock->pNextBlock;
if (LockFreeCAS(pMemoryPool->pFirstBlock, pFreeBlock, pNextBlock)) {
pFreeBlock->pNextBlock = NULL;
return MemoryBlockToPointer(pFreeBlock);
}
// Block got by another thread. Trying again
}
}
////////////////////////////////////////////////////////////////////////void MemoryAllocator::Free(void* pPointer)
{
if (pPointer == NULL)
return; // Do nothing on NULL pointer
// Get memory block pool
MemoryBlock* pMemoryBlock = PointerToMemoryBlock(pPointer);
MemoryPool* pMemoryPool = pMemoryBlock->pPool;
ASSERT(pMemoryPool != NULL);
ASSERT(pMemoryBlock->pNextBlock == NULL);
// Trying to return memory block to free lock poolwhile (true) {
MemoryBlock* pNextBlock = pMemoryPool->pFirstBlock;
pMemoryBlock->pNextBlock = pNextBlock;
if (LockFreeCAS(pMemoryPool->pFirstBlock, pNextBlock, pMemoryBlock))
break; // Memory block successfully returned to memory pool
// Another thread return it memory block. Trying again
}
// Statistic
LockFreeDEC(pMemoryPool->nOccupied);
}
////////////////////////////////////////////////////////////////////////void MemoryAllocator::Erase()
{
TRACE(L"\nAllocator Erase statistic:");
LONGLONG nTotalKBUsed = 0;
for (size_t n = 0; n < m_nPools; n++) {
MemoryPool memoryPool;
//Trying to set pool first block to zerowhile (true) {
memoryPool = m_pools[n];
MemoryBlock* pFirstBlock = memoryPool.pFirstBlock;
if (LockFreeCAS(m_pools[n].pFirstBlock, pFirstBlock, NULL))
break; // Pool cleared
// Pool changed try again
}
// Free memory pool blocks
size_t nBlockSize = (memoryPool.nMaxSize + sizeof(MemoryBlock)) / 1024;
nTotalKBUsed+= memoryPool.nAllocated * nBlockSize;
MemoryBlock* pMemoryBlock = memoryPool.pFirstBlock;
while (pMemoryBlock != NULL) {
char* pPointer = reinterpret_cast<char*>(pMemoryBlock);
pMemoryBlock = pMemoryBlock->pNextBlock;
::free(pPointer);
pPointer = NULL;
// Statistic
LockFreeDEC(m_pools[n].nAllocated);
}
TRACE(L"\n\t(%6d)Kb block was: allocated (%d) times, already in use (%d) blocks", nBlockSize, memoryPool.nAllocated, memoryPool.nOccupied);
}
TRACE(L"\nTotal memory was in use (%I64i)Kb", nTotalKBUsed);
}
////////////////////////////////////////////////////////////////////////
// Public methods
////////////////////////////////////////////////////////////////////////
// Implementation
size_t MemoryAllocator::GetMemoryPageSize()
{
SYSTEM_INFO si;
::GetSystemInfo(&si);
return si.dwPageSize;
}
////////////////////////////////////////////////////////////////////////
MemoryAllocator::MemoryBlock* MemoryAllocator::PointerToMemoryBlock(const void* pPointer)
{
return const_cast<MemoryBlock*>(reinterpret_cast<const MemoryBlock*>(static_cast<const char*>(pPointer) - sizeof(MemoryBlock)));
}
////////////////////////////////////////////////////////////////////////void* MemoryAllocator::MemoryBlockToPointer(const MemoryBlock* pMemoryBlock)
{
return const_cast<char*>(reinterpret_cast<const char*>(pMemoryBlock) + sizeof(MemoryBlock));
}
////////////////////////////////////////////////////////////////////////bool MemoryAllocator::LockFreeCAS(MemoryBlock*& pCheck, MemoryBlock* pCompare, MemoryBlock* pNew)
{
MemoryBlock* pOld = static_cast<MemoryBlock*>(::InterlockedCompareExchangePointer(reinterpret_cast<LPVOID*>(&pCheck), pNew, pCompare));
return pOld == pCompare;
}
////////////////////////////////////////////////////////////////////////long MemoryAllocator::LockFreeINC(long& nValue)
{
return ::InterlockedIncrement(&nValue);
}
////////////////////////////////////////////////////////////////////////long MemoryAllocator::LockFreeDEC(long& nValue)
{
return ::InterlockedDecrement(&nValue);
}
////////////////////////////////////////////////////////////////////////
MemoryAllocator::FreePools MemoryAllocator::CreatePools() const
{
ASSERT(m_nMinBlockSize >= sizeof(MemoryBlock));
ASSERT(m_nMinBlockSize <= m_nMaxBlockSize);
m_nPools = 0;
FreePools pools;
size_t nPoolBlockSize = m_nMinBlockSize;
// Fill fields equal for all pools
MemoryPool memoryPool;
memoryPool.nMaxSize = nPoolBlockSize - sizeof(MemoryBlock);
memoryPool.nAllocated = 0;
memoryPool.nOccupied = 0;
memoryPool.pAllocator = const_cast<MemoryAllocator*>(this);
memoryPool.pFirstBlock = NULL;
// Calculate necessary pool numberwhile (memoryPool.nMaxSize <= m_nMaxBlockSize) {
memoryPool.nMaxSize = nPoolBlockSize - sizeof(MemoryBlock);
m_nPools+= 1;
nPoolBlockSize*= 2;
}
if (m_nPools == 0)
return NULL; // Bas maximum block size
// Allocate pools array
pools = reinterpret_cast<FreePools>(malloc(sizeof(MemoryPool) * m_nPools));
// Fill pool specific fields
nPoolBlockSize = m_nMinBlockSize;
memoryPool.nMaxSize = nPoolBlockSize - sizeof(MemoryBlock);
for (size_t n = 0; n < m_nPools; n++) {
memoryPool.nMaxSize = nPoolBlockSize - sizeof(MemoryBlock);
pools[n] = memoryPool;
nPoolBlockSize*= 2;
}
// Return just created pools arrayreturn pools;
}
////////////////////////////////////////////////////////////////////////
MemoryAllocator::MemoryPool* MemoryAllocator::GetPool(size_t nSize) const
{
// Search pool for specified block size for (size_t n = 0; n < m_nPools; n++) {
if (nSize <= m_pools[n].nMaxSize)
return const_cast<MemoryPool*>(&m_pools[n]);
}
// Pool for specified size not foundreturn NULL;
}
////////////////////////////////////////////////////////////////////////void* MemoryAllocator::AllocateMemoryBlock(MemoryPool* pMemoryPool) const
{
ASSERT(pMemoryPool != NULL);
MemoryBlock* pMemoryBlock = reinterpret_cast<MemoryBlock*>(malloc(pMemoryPool->nMaxSize + sizeof(MemoryBlock)));
pMemoryBlock->pPool = pMemoryPool;
pMemoryBlock->pNextBlock = NULL;
// Statistic
LockFreeINC(pMemoryPool->nAllocated);
// Return pointer to user memoryreturn MemoryBlockToPointer(pMemoryBlock);
}
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Из недостатков: ATP>1. Имеет ограничение на максимальный объем выделяемого блока ATP>2. Сначала набирает рабочий объем памяти используя стандартный метод аллокации
платформоспецифик, и очевидно валится за милую душу.
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Здравствуйте, Sni4ok, Вы писали:
ATP>А можно словами, что у вас в выделенных фрагментах валится? У меня не валится ничего, да с чего бы это.
у меня ничего не валится, мне этот аллокатор не нужен, но если вы сначала выделяете память через malloc, а потом пытаетесь её использовать без проверки на выделение, то в случае если это выделение у вас неудалось, у вас всё упадёт.
Здравствуйте, Sni4ok, Вы писали:
S>Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>>Здравствуйте, Sni4ok, Вы писали:
ATP>>А можно словами, что у вас в выделенных фрагментах валится? У меня не валится ничего, да с чего бы это.
S>у меня ничего не валится, мне этот аллокатор не нужен, но если вы сначала выделяете память через malloc, а потом пытаетесь её использовать без проверки на выделение, то в случае если это выделение у вас неудалось, у вас всё упадёт.
1. Полностью согласен, не доглядел. Просто раньше у меня вместо malloc был new, а там как известно, исключение вылетает
2. Событие маловероятное, т.к. аллоцируется несколько байт.
3. Вопрос был по lock-free
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>>Здравствуйте, remark, Вы писали:
ATP>>Кстати Дмитрий, вы я смотрю хорошо разбираетесь в look-free алгоритмах. Не могли бы вы посмотреть на предмет look-free мой простенький аллокатор?
ATP>Полностью потокобезопасен, имеет всего три метода, при желании можно добавить нужные. ATP>Из недостатков: ATP>1. Имеет ограничение на максимальный объем выделяемого блока ATP>2. Сначала набирает рабочий объем памяти используя стандартный метод аллокации
1. Может быть ABA проблема в методе Allocate()
if (LockFreeCAS(pMemoryPool->pFirstBlock, pFreeBlock, pNextBlock)) {
Если со стека будет снято несколько элементов, а потом положено несколько, то pMemoryPool->pFirstBlock может быть равным pFreeBlock, однако pNextBlock уже будет не верным. Это может приводить к утечкам памяти.
2. Может свалится в методе Allocate() на чтении:
MemoryBlock* pNextBlock = pFreeBlock->pNextBlock;
pFreeBlock может быть уже освобождён в методе Erase().
3. Больше ошибок не вижу, но опять же могу не упомянуть Relacy Race Detector, который бы нашёл всё это в миг.
4. Остальное касательно масштабируемости и производительности.
Централизованные дизайны не масштабируются. Точка.
Масштабируемый аллокатор должен иметь локальные пулы памяти для каждого потока/процессора, и удовлетворять запросы аллокации из них. Как делать освобождение — это отдельная тема, тут много вариантов.
MemoryPool'ы необходимо отделить друг от друга прослойками для предотвращения ложного разделения (false-sharing). Ложное разделение может иметь катастрофически негативное влияние на производительность.
Такие slab-аллокатры зачастую делают headerless, т.е. вообще без заголовков блоков MemoryBlock. Хотя учитывая минимальный размер блока в 512 байт, это видимо не очень актуально.
В методе Erase() можно заменить CAS-цикл:
while (true) {
memoryPool = m_pools[n];
MemoryBlock* pFirstBlock = memoryPool.pFirstBlock;
if (LockFreeCAS(m_pools[n].pFirstBlock, pFirstBlock, NULL))
break; // Pool cleared
}
На один _InterlockedExchange(), который заменит m_pools[n].pFirstBlock на 0.
Там же, уменьшение nAllocated:
LockFreeDEC(m_pools[n].nAllocated);
можно вынести из цикла. Т.е. после цикла один раз уменьшить nAllocated на кол-во освобождённых блоков.
Выполнять атомарные операции над разделяемыми данными с сильной конкуренцией только ради отладочной статистики (nAllocated, nOccupied) я бы не стал. Я бы серьёзно рассмотрел вариант выполнения этих операций только если определен _DEBUG.
R>Если со стека будет снято несколько элементов, а потом положено несколько, то pMemoryPool->pFirstBlock может быть равным pFreeBlock, однако pNextBlock уже будет не верным. Это может приводить к утечкам памяти.
Да, я в курсе что здесь есть ABA проблема. Это еще один камень в огород CAS. С LL/SC в данной ситуации не было бы никакой ABA. А как можно выкрутиться, СAS64 применить и упаковывать в одно значение счетчик операций и адрес?
R>2. Может свалится в методе Allocate() на чтении: R>
R>pFreeBlock может быть уже освобождён в методе Erase().
Да — может. Тут проглядел. Но в принципе вопрос то был по lock-free.
R>3. Больше ошибок не вижу, но опять же могу не упомянуть Relacy Race Detector, который бы нашёл всё это в миг.
R>4. Остальное касательно масштабируемости и производительности. R>Централизованные дизайны не масштабируются. Точка. R>Масштабируемый аллокатор должен иметь локальные пулы памяти для каждого потока/процессора, и удовлетворять запросы аллокации из них. Как делать освобождение — это отдельная тема, тут много вариантов.
А какие тут проблемы с масштабируемостью?
R>MemoryPool'ы необходимо отделить друг от друга прослойками для предотвращения ложного разделения (false-sharing). Ложное разделение может иметь катастрофически негативное влияние на производительность.
Это что еще такое (false-sharing?
R>Выполнять атомарные операции над разделяемыми данными с сильной конкуренцией только ради отладочной статистики (nAllocated, nOccupied) я бы не стал. Я бы серьёзно рассмотрел вариант выполнения этих операций только если определен _DEBUG.
Это экспериментальный аллокатор написанный за 30 минут, он пока не претендует на использование в рабочих проектах, я только разбираюсь с ним пока.
R>Сходу вроде всё...
R>
R>>Если со стека будет снято несколько элементов, а потом положено несколько, то pMemoryPool->pFirstBlock может быть равным pFreeBlock, однако pNextBlock уже будет не верным. Это может приводить к утечкам памяти.
ATP>Да, я в курсе что здесь есть ABA проблема. Это еще один камень в огород CAS. С LL/SC в данной ситуации не было бы никакой ABA. А как можно выкрутиться, СAS64 применить и упаковывать в одно значение счетчик операций и адрес?
R>>2. Может свалится в методе Allocate() на чтении: R>>
R>>pFreeBlock может быть уже освобождён в методе Erase().
ATP>Да — может. Тут проглядел. Но в принципе вопрос то был по lock-free.
Ну а что же это как не следствие lock-free? Проблема управлением временем жизни объектов — угловая для non-blocking алгоритмов в не-GC окружении. Если бы ты использовал мьютексы вокруг всех функций, этой проблемы бы не было. Это именно следствие применения lock-free техник.
Я бы посоветовал тут использовать Interlocked SList API. Оно решает одновременно обе проблемы — ABA и возможные падения при обращениях к освобожденной памяти.
CAS64 использовать можно, но надо придумать как паковать указатель на 64-битной платформе, что бы осталось достаточно битов под счётчик. Плюс надо как-то обходить падение. Фактически ты скорее всего и переизобретёшь SList API, если решишь эти проблемы.
R>>3. Больше ошибок не вижу, но опять же могу не упомянуть Relacy Race Detector, который бы нашёл всё это в миг.
R>>4. Остальное касательно масштабируемости и производительности. R>>Централизованные дизайны не масштабируются. Точка. R>>Масштабируемый аллокатор должен иметь локальные пулы памяти для каждого потока/процессора, и удовлетворять запросы аллокации из них. Как делать освобождение — это отдельная тема, тут много вариантов.
ATP>А какие тут проблемы с масштабируемостью?
Её тут нет.
Смотри там в середине поста есть тест, где показана масштабируемость атомарных операций при высокой конкуренции: http://rsdn.ru/forum/winapi/2804596.aspx
R>>MemoryPool'ы необходимо отделить друг от друга прослойками для предотвращения ложного разделения (false-sharing). Ложное разделение может иметь катастрофически негативное влияние на производительность.
ATP>Это что еще такое (false-sharing?
R>>Выполнять атомарные операции над разделяемыми данными с сильной конкуренцией только ради отладочной статистики (nAllocated, nOccupied) я бы не стал. Я бы серьёзно рассмотрел вариант выполнения этих операций только если определен _DEBUG.
ATP>Это экспериментальный аллокатор написанный за 30 минут, он пока не претендует на использование в рабочих проектах, я только разбираюсь с ним пока.
Это ключевые моменты. Сам по себе "lock-free" в подавляющем большинстве случаев бесполезен.
Ну я так не могу "двигаться" сразу GC и т.д. Мне для начала хотелось бы понять как исправить CAS в конкретном примере и ответы на конкретные вопросы:
1. LL/SC в данном случае повели бы себя правильно? ABA проблемы с ними нет, так ?
2. Что бы решить ABA проблему в данном контексте нужно использовать CAS2? А как быть с CAS на архитектуре X если требуется атомарная замена двойного Х (например на 128-битной архитектуре всегда ли будет 256-х битный CAS)?
P.S. Я понимаю что вам наверное не интересно обсуждать такие простые вопросы, так как для вас уже все просто и позади, но все-таки мне бы хотелось понять почему нужно делать ТАК, а не просто услышать что нужно ТАК делать.
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Ну я так не могу "двигаться" сразу GC и т.д. Мне для начала хотелось бы понять как исправить CAS в конкретном примере и ответы на конкретные вопросы:
Сам CAS тут нельзя исправить, тут надо рассматривать в комплексе.
ATP>1. LL/SC в данном случае повели бы себя правильно? ABA проблемы с ними нет, так ?
Нет, сам по себе LL/SC не повёл бы себя правильно.
Например в комплексе тут можно использовать LL/SC и non-failing loads для загрузки next поля из узла, который может потенциально удалиться.
ATP>2. Что бы решить ABA проблему в данном контексте нужно использовать CAS2? А как быть с CAS на архитектуре X если требуется атомарная замена двойного Х
С CAS2 всё равно будет падать при обращениях к освобожденной памяти.
ATP>(например на 128-битной архитектуре всегда ли будет 256-х битный CAS)?
Здравствуйте, remark, Вы писали:
R>Нет, сам по себе LL/SC не повёл бы себя правильно. R>Например в комплексе тут можно использовать LL/SC и non-failing loads для загрузки next поля из узла, который может потенциально удалиться.
Хорошо, предположим нету у нас метода Erase, память всегда валидна. Тогда использование LL/SС вместо CAS спасет в данной ситуации?
R>С CAS2 всё равно будет падать при обращениях к освобожденной памяти.
Понял, понял — не тупой Я не сорю.
ATP>>(например на 128-битной архитектуре всегда ли будет 256-х битный CAS)?
R>Нет, таких гарантий никто не даёт.
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Здравствуйте, remark, Вы писали:
R>>Нет, сам по себе LL/SC не повёл бы себя правильно. R>>Например в комплексе тут можно использовать LL/SC и non-failing loads для загрузки next поля из узла, который может потенциально удалиться.
ATP>Хорошо, предположим нету у нас метода Erase, память всегда валидна. Тогда использование LL/SС вместо CAS спасет в данной ситуации?
Я не сорю.