diff --git a/libs/image/tiles3/KisTiledExtentManager.cpp b/libs/image/tiles3/KisTiledExtentManager.cpp index 9a71e0aa05..846a8b12f5 100644 --- a/libs/image/tiles3/KisTiledExtentManager.cpp +++ b/libs/image/tiles3/KisTiledExtentManager.cpp @@ -1,152 +1,348 @@ /* * Copyright (c) 2017 Dmitry Kazakov + * Copyright (c) 2018 Andrey Kamakin * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #include "KisTiledExtentManager.h" #include #include #include "kis_tile_data_interface.h" #include "kis_assert.h" #include "kis_global.h" +#include "kis_debug.h" -namespace { +KisTiledExtentManager::Data::Data() + : m_min(qint32_MAX), m_max(qint32_MIN), m_count(0) +{ + QWriteLocker lock(&m_migrationLock); + m_capacity = InitialBufferSize; + m_offset = 0; + m_buffer = new QAtomicInt[m_capacity]; +} + +KisTiledExtentManager::Data::~Data() +{ + QWriteLocker lock(&m_migrationLock); + delete[] m_buffer; +} -inline bool addTileToMap(int index, QMap *map) +inline bool KisTiledExtentManager::Data::add(qint32 index) { + QReadLocker lock(&m_migrationLock); + qint32 currentIndex = m_offset + index; + + if (currentIndex < 0 || currentIndex >= m_capacity) { + lock.unlock(); + migrate(index); + lock.relock(); + currentIndex = m_offset + index; + } + + KIS_ASSERT_RECOVER_NOOP(m_buffer[currentIndex].loadAcquire() >= 0); bool needsUpdateExtent = false; + QReadLocker rl(&m_extentLock); + + if (!m_buffer[currentIndex].loadAcquire()) { + rl.unlock(); + QWriteLocker wl(&m_extentLock); + + if (!m_buffer[currentIndex].load()) { + m_buffer[currentIndex].store(1); - auto it = map->find(index); + if (m_min > index) m_min = index; + if (m_max < index) m_max = index; - if (it == map->end()) { - map->insert(index, 1); - needsUpdateExtent = true; + ++m_count; + needsUpdateExtent = true; + } else { + m_buffer[currentIndex].ref(); + } } else { - KIS_ASSERT_RECOVER_NOOP(*it > 0); - (*it)++; + m_buffer[currentIndex].ref(); } return needsUpdateExtent; } -inline bool removeTileFromMap(int index, QMap *map) +inline bool KisTiledExtentManager::Data::remove(qint32 index) { + QReadLocker lock(&m_migrationLock); + qint32 currentIndex = m_offset + index; + + if (currentIndex < 0 || currentIndex >= m_capacity) { + lock.unlock(); + migrate(index); + lock.relock(); + currentIndex = m_offset + index; + } + + KIS_ASSERT_RECOVER_NOOP(m_buffer[currentIndex].loadAcquire() > 0); bool needsUpdateExtent = false; + QReadLocker rl(&m_extentLock); - auto it = map->find(index); + if (m_buffer[currentIndex].loadAcquire() == 1) { + rl.unlock(); + QWriteLocker wl(&m_extentLock); - if (it == map->end()) { - KIS_ASSERT_RECOVER_NOOP(0 && "sanity check failed: the tile has already been removed!"); - } else { - KIS_ASSERT_RECOVER_NOOP(*it > 0); - (*it)--; + if (m_buffer[currentIndex].load() == 1) { + m_buffer[currentIndex].store(0); - if (*it <= 0) { - map->erase(it); + if (m_min == index) updateMin(); + if (m_max == index) updateMax(); + + --m_count; needsUpdateExtent = true; + } else { + KIS_ASSERT_RECOVER_NOOP(0 && "sanity check failed: the tile has already been removed!"); } + } else { + m_buffer[currentIndex].deref(); } return needsUpdateExtent; } +void KisTiledExtentManager::Data::replace(const QVector &indexes) +{ + QWriteLocker lock(&m_migrationLock); + QWriteLocker l(&m_extentLock); + + for (qint32 i = 0; i < m_capacity; ++i) { + m_buffer[i].store(0); + } + + m_min = qint32_MAX; + m_max = qint32_MIN; + m_count = 0; + + Q_FOREACH (const qint32 index, indexes) { + unsafeAdd(index); + } +} + +void KisTiledExtentManager::Data::clear() +{ + QWriteLocker lock(&m_migrationLock); + QWriteLocker l(&m_extentLock); + + for (qint32 i = 0; i < m_capacity; ++i) { + m_buffer[i].store(0); + } + m_min = qint32_MAX; + m_max = qint32_MIN; + m_count = 0; } -KisTiledExtentManager::KisTiledExtentManager() +bool KisTiledExtentManager::Data::isEmpty() +{ + return m_count == 0; +} + +qint32 KisTiledExtentManager::Data::min() +{ + return m_min; +} + +qint32 KisTiledExtentManager::Data::max() +{ + return m_max; +} + +void KisTiledExtentManager::Data::unsafeAdd(qint32 index) +{ + qint32 currentIndex = m_offset + index; + + if (currentIndex < 0 || currentIndex >= m_capacity) { + unsafeMigrate(index); + currentIndex = m_offset + index; + } + + if (!m_buffer[currentIndex].fetchAndAddRelaxed(1)) { + if (m_min > index) m_min = index; + if (m_max < index) m_max = index; + ++m_count; + } +} + +void KisTiledExtentManager::Data::unsafeMigrate(qint32 index) +{ + qint32 oldCapacity = m_capacity; + qint32 currentIndex = m_offset + index; + + auto reallocFunc = [&](qint32 start) { + QAtomicInt *newBuffer = new QAtomicInt[m_capacity]; + + for (qint32 i = 0; i < oldCapacity; ++i) { + newBuffer[start + i].store(m_buffer[i].load()); + } + + delete[] m_buffer; + m_buffer = newBuffer; + }; + + if (currentIndex < 0) { + qint32 oldOffset = m_offset; + m_offset = -index; + qint32 start = m_offset - oldOffset; + qint32 count = m_max - m_min + 1; + qint32 capacity = m_offset + start + count; + + while (capacity >= m_capacity) { + m_capacity <<= 1; + } + + if (m_capacity != oldCapacity) { + reallocFunc(start); + } else { + for (qint32 i = count; i >= 0; --i) { + m_buffer[start + i].store(m_buffer[i].load()); + } + + for (qint32 i = 0; i < start; ++i) { + m_buffer[i].store(0); + } + } + } else { + while (currentIndex >= m_capacity) { + m_capacity <<= 1; + } + + if (m_capacity != oldCapacity) { + reallocFunc(0); + } + } +} + +void KisTiledExtentManager::Data::migrate(qint32 index) +{ + QWriteLocker lock(&m_migrationLock); + unsafeMigrate(index); +} + +void KisTiledExtentManager::Data::updateMin() { + qint32 start = m_min + m_offset + 1; + + for (qint32 i = start; i < m_capacity; ++i) { + qint32 current = m_buffer[i].load(); + + if (current > 0) { + m_min = current; + break; + } + } } -void KisTiledExtentManager::notifyTileAdded(int col, int row) +void KisTiledExtentManager::Data::updateMax() { - QMutexLocker l(&m_mutex); + qint32 start = m_max + m_offset - 1; + + for (qint32 i = start; i >= 0; --i) { + qint32 current = m_buffer[i].load(); + + if (current > 0) { + m_max = current; + break; + } + } +} +KisTiledExtentManager::KisTiledExtentManager() +{ +} + +void KisTiledExtentManager::notifyTileAdded(qint32 col, qint32 row) +{ bool needsUpdateExtent = false; - needsUpdateExtent |= addTileToMap(col, &m_colMap); - needsUpdateExtent |= addTileToMap(row, &m_rowMap); + needsUpdateExtent |= m_colsData.add(col); + needsUpdateExtent |= m_rowsData.add(row); if (needsUpdateExtent) { updateExtent(); } } -void KisTiledExtentManager::notifyTileRemoved(int col, int row) +void KisTiledExtentManager::notifyTileRemoved(qint32 col, qint32 row) { - QMutexLocker l(&m_mutex); - bool needsUpdateExtent = false; - needsUpdateExtent |= removeTileFromMap(col, &m_colMap); - needsUpdateExtent |= removeTileFromMap(row, &m_rowMap); + needsUpdateExtent |= m_colsData.remove(col); + needsUpdateExtent |= m_rowsData.remove(row); if (needsUpdateExtent) { updateExtent(); } } void KisTiledExtentManager::replaceTileStats(const QVector &indexes) { - QMutexLocker l(&m_mutex); - - m_colMap.clear(); - m_rowMap.clear(); + QVector colsIndexes; + QVector rowsIndexes; Q_FOREACH (const QPoint &index, indexes) { - addTileToMap(index.x(), &m_colMap); - addTileToMap(index.y(), &m_rowMap); + colsIndexes.append(index.x()); + rowsIndexes.append(index.y()); } + m_colsData.replace(colsIndexes); + m_rowsData.replace(rowsIndexes); updateExtent(); } void KisTiledExtentManager::clear() { - QMutexLocker l(&m_mutex); + m_colsData.clear(); + m_rowsData.clear(); - m_colMap.clear(); - m_rowMap.clear(); + QWriteLocker lock(&m_extentLock); m_currentExtent = QRect(qint32_MAX, qint32_MAX, 0, 0); - } QRect KisTiledExtentManager::extent() const { - QMutexLocker l(&m_mutex); + QReadLocker lock(&m_extentLock); return m_currentExtent; } void KisTiledExtentManager::updateExtent() { - KIS_ASSERT_RECOVER_RETURN(m_colMap.isEmpty() == m_rowMap.isEmpty()); + QReadLocker cl(&m_colsData.m_extentLock); + QReadLocker rl(&m_rowsData.m_extentLock); - // here we check for only one map for efficiency reasons - if (m_colMap.isEmpty()) { + bool colsEmpty = m_colsData.isEmpty(); + bool rowsEmpty = m_rowsData.isEmpty(); + KIS_ASSERT_RECOVER_RETURN(colsEmpty == rowsEmpty); + + if (colsEmpty && rowsEmpty) { + QWriteLocker lock(&m_extentLock); m_currentExtent = QRect(qint32_MAX, qint32_MAX, 0, 0); } else { - const int minX = m_colMap.firstKey() * KisTileData::WIDTH; - const int maxPlusOneX = (m_colMap.lastKey() + 1) * KisTileData::WIDTH; - const int minY = m_rowMap.firstKey() * KisTileData::HEIGHT; - const int maxPlusOneY = (m_rowMap.lastKey() + 1) * KisTileData::HEIGHT; + const qint32 minX = m_colsData.min() * KisTileData::WIDTH; + const qint32 maxPlusOneX = (m_colsData.max() + 1) * KisTileData::WIDTH; + const qint32 minY = m_rowsData.min() * KisTileData::HEIGHT; + const qint32 maxPlusOneY = (m_rowsData.max() + 1) * KisTileData::HEIGHT; + QWriteLocker lock(&m_extentLock); m_currentExtent = QRect(minX, minY, maxPlusOneX - minX, maxPlusOneY - minY); } } - diff --git a/libs/image/tiles3/KisTiledExtentManager.h b/libs/image/tiles3/KisTiledExtentManager.h index b4fa94b7c9..576fbd7746 100644 --- a/libs/image/tiles3/KisTiledExtentManager.h +++ b/libs/image/tiles3/KisTiledExtentManager.h @@ -1,51 +1,87 @@ /* * Copyright (c) 2017 Dmitry Kazakov + * Copyright (c) 2018 Andrey Kamakin * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #ifndef KISTILEDEXTENTMANAGER_H #define KISTILEDEXTENTMANAGER_H #include +#include #include #include #include "kritaimage_export.h" class KRITAIMAGE_EXPORT KisTiledExtentManager { + static const qint32 InitialBufferSize = 256; + + class Data + { + public: + Data(); + ~Data(); + + inline bool add(qint32 index); + inline bool remove(qint32 index); + void replace(const QVector &indexes); + void clear(); + bool isEmpty(); + qint32 min(); + qint32 max(); + + public: + QReadWriteLock m_extentLock; + + private: + inline void unsafeAdd(qint32 index); + inline void unsafeMigrate(qint32 index); + inline void migrate(qint32 index); + inline void updateMin(); + inline void updateMax(); + + private: + qint32 m_min; + qint32 m_max; + qint32 m_offset; + qint32 m_capacity; + qint32 m_count; + QAtomicInt *m_buffer; + QReadWriteLock m_migrationLock; + }; + public: KisTiledExtentManager(); - void notifyTileAdded(int col, int row); - void notifyTileRemoved(int col, int row); + void notifyTileAdded(qint32 col, qint32 row); + void notifyTileRemoved(qint32 col, qint32 row); void replaceTileStats(const QVector &indexes); - void clear(); - QRect extent() const; private: void updateExtent(); private: - mutable QMutex m_mutex; - QMap m_colMap; - QMap m_rowMap; + mutable QReadWriteLock m_extentLock; QRect m_currentExtent; + Data m_colsData; + Data m_rowsData; }; #endif // KISTILEDEXTENTMANAGER_H diff --git a/libs/image/tiles3/kis_tile_data.cc b/libs/image/tiles3/kis_tile_data.cc index fe8f5a09e3..beedd8be5d 100644 --- a/libs/image/tiles3/kis_tile_data.cc +++ b/libs/image/tiles3/kis_tile_data.cc @@ -1,242 +1,277 @@ /* * Copyright (c) 2009 Dmitry Kazakov + * Copyright (c) 2018 Andrey Kamakin * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #include "kis_tile_data.h" #include "kis_tile_data_store.h" #include #include #include "kis_tile_data_store_iterators.h" // BPP == bytes per pixel #define TILE_SIZE_4BPP (4 * __TILE_DATA_WIDTH * __TILE_DATA_HEIGHT) #define TILE_SIZE_8BPP (8 * __TILE_DATA_WIDTH * __TILE_DATA_HEIGHT) typedef boost::singleton_pool BoostPool4BPP; typedef boost::singleton_pool BoostPool8BPP; const qint32 KisTileData::WIDTH = __TILE_DATA_WIDTH; const qint32 KisTileData::HEIGHT = __TILE_DATA_HEIGHT; +SimpleCache KisTileData::m_cache; -KisTileData::KisTileData(qint32 pixelSize, const quint8 *defPixel, KisTileDataStore *store) +SimpleCache::~SimpleCache() +{ + clear(); +} + +void SimpleCache::clear() +{ + QWriteLocker l(&m_cacheLock); + quint8 *ptr = 0; + + while (m_4Pool.pop(ptr)) { + BoostPool4BPP::free(ptr); + } + + while (m_8Pool.pop(ptr)) { + BoostPool8BPP::free(ptr); + } + + while (m_16Pool.pop(ptr)) { + free(ptr); + } +} + + +KisTileData::KisTileData(qint32 pixelSize, const quint8 *defPixel, KisTileDataStore *store, bool checkFreeMemory) : m_state(NORMAL), m_mementoFlag(0), m_age(0), m_usersCount(0), m_refCount(0), m_pixelSize(pixelSize), m_store(store) { - m_store->checkFreeMemory(); + if (checkFreeMemory) { + m_store->checkFreeMemory(); + } m_data = allocateData(m_pixelSize); fillWithPixel(defPixel); } /** * Duplicating tiledata * + new object loaded in memory * + it's unlocked and has refCount==0 * * NOTE: the memory allocated by the pooler for clones is not counted * by the store in memoryHardLimit. The pooler has it's own slice of * memory and keeps track of the its size itself. So we should be able * to disable the memory check with checkFreeMemory, otherwise, there * is a deadlock. */ KisTileData::KisTileData(const KisTileData& rhs, bool checkFreeMemory) : m_state(NORMAL), m_mementoFlag(0), m_age(0), m_usersCount(0), m_refCount(0), m_pixelSize(rhs.m_pixelSize), m_store(rhs.m_store) { - if(checkFreeMemory) { + if (checkFreeMemory) { m_store->checkFreeMemory(); } m_data = allocateData(m_pixelSize); memcpy(m_data, rhs.data(), m_pixelSize * WIDTH * HEIGHT); } KisTileData::~KisTileData() { releaseMemory(); } void KisTileData::fillWithPixel(const quint8 *defPixel) { quint8 *it = m_data; - for (int i = 0; i < WIDTH*HEIGHT; i++, it += m_pixelSize) { + for (int i = 0; i < WIDTH * HEIGHT; i++, it += m_pixelSize) { memcpy(it, defPixel, m_pixelSize); } } void KisTileData::releaseMemory() { if (m_data) { freeData(m_data, m_pixelSize); m_data = 0; } KisTileData *clone = 0; - while(m_clonesStack.pop(clone)) { + while (m_clonesStack.pop(clone)) { delete clone; } Q_ASSERT(m_clonesStack.isEmpty()); } void KisTileData::allocateMemory() { Q_ASSERT(!m_data); m_data = allocateData(m_pixelSize); } quint8* KisTileData::allocateData(const qint32 pixelSize) { quint8 *ptr = 0; - switch(pixelSize) { - case 4: - ptr = (quint8*)BoostPool4BPP::malloc(); - break; - case 8: - ptr = (quint8*)BoostPool8BPP::malloc(); - break; - default: - ptr = (quint8*) malloc(pixelSize * WIDTH * HEIGHT); + if (!m_cache.pop(pixelSize, ptr)) { + switch (pixelSize) { + case 4: + ptr = (quint8*)BoostPool4BPP::malloc(); + break; + case 8: + ptr = (quint8*)BoostPool8BPP::malloc(); + break; + default: + ptr = (quint8*) malloc(pixelSize * WIDTH * HEIGHT); + break; + } } return ptr; } void KisTileData::freeData(quint8* ptr, const qint32 pixelSize) { - switch(pixelSize) { - case 4: - BoostPool4BPP::free(ptr); - break; - case 8: - BoostPool8BPP::free(ptr); - break; - default: - free(ptr); + if (!m_cache.push(pixelSize, ptr)) { + switch (pixelSize) { + case 4: + BoostPool4BPP::free(ptr); + break; + case 8: + BoostPool8BPP::free(ptr); + break; + default: + free(ptr); + break; + } } } //#define DEBUG_POOL_RELEASE #ifdef DEBUG_POOL_RELEASE #include #endif /* DEBUG_POOL_RELEASE */ void KisTileData::releaseInternalPools() { const int maxMigratedTiles = 100; if (KisTileDataStore::instance()->numTilesInMemory() < maxMigratedTiles) { QVector dataObjects; QVector memoryChunks; bool failedToLock = false; KisTileDataStoreIterator *iter = KisTileDataStore::instance()->beginIteration(); - while(iter->hasNext()) { + while (iter->hasNext()) { KisTileData *item = iter->next(); // first release all the clones KisTileData *clone = 0; - while(item->m_clonesStack.pop(clone)) { + while (item->m_clonesStack.pop(clone)) { delete clone; } // check if the tile data has actually been pooled if (item->m_pixelSize != 4 && item->m_pixelSize != 8) { continue; } // check if the tile has been swapped out if (item->m_data) { const bool locked = item->m_swapLock.tryLockForWrite(); if (!locked) { failedToLock = true; break; } const int chunkSize = item->m_pixelSize * WIDTH * HEIGHT; dataObjects << item; memoryChunks << QByteArray((const char*)item->m_data, chunkSize); } } if (!failedToLock) { // purge the pools memory + m_cache.clear(); BoostPool4BPP::purge_memory(); BoostPool8BPP::purge_memory(); auto it = dataObjects.begin(); auto chunkIt = memoryChunks.constBegin(); for (; it != dataObjects.end(); ++it, ++chunkIt) { KisTileData *item = *it; const int chunkSize = item->m_pixelSize * WIDTH * HEIGHT; item->m_data = allocateData(item->m_pixelSize); memcpy(item->m_data, chunkIt->data(), chunkSize); item->m_swapLock.unlock(); } } else { Q_FOREACH (KisTileData *item, dataObjects) { item->m_swapLock.unlock(); } warnKrita << "WARNING: Failed to lock the tiles while trying to release the pooled memory"; } KisTileDataStore::instance()->endIteration(iter); #ifdef DEBUG_POOL_RELEASE dbgKrita << "After purging unused memory:"; char command[256]; sprintf(command, "cat /proc/%d/status | grep -i vm", (int)getpid()); printf("--- %s ---\n", command); (void)system(command); #endif /* DEBUG_POOL_RELEASE */ } else { dbgKrita << "DEBUG: releasing of the pooled memory has been cancelled:" << "there are still" << KisTileDataStore::instance()->numTilesInMemory() << "tiles in memory"; } } diff --git a/libs/image/tiles3/kis_tile_data_interface.h b/libs/image/tiles3/kis_tile_data_interface.h index 3783aa40b8..5251477ed0 100644 --- a/libs/image/tiles3/kis_tile_data_interface.h +++ b/libs/image/tiles3/kis_tile_data_interface.h @@ -1,272 +1,327 @@ /* * Copyright (c) 2009 Dmitry Kazakov + * Copyright (c) 2018 Andrey Kamakin * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + #ifndef KIS_TILE_DATA_INTERFACE_H_ #define KIS_TILE_DATA_INTERFACE_H_ #include #include #include "kis_lockless_stack.h" #include "swap/kis_chunk_allocator.h" class KisTileData; class KisTileDataStore; /** * WARNING: Those definitions for internal use only! * Please use KisTileData::WIDTH/HEIGHT instead */ #define __TILE_DATA_WIDTH 64 #define __TILE_DATA_HEIGHT 64 typedef KisLocklessStack KisTileDataCache; typedef QLinkedList KisTileDataList; typedef KisTileDataList::iterator KisTileDataListIterator; typedef KisTileDataList::const_iterator KisTileDataListConstIterator; +class SimpleCache +{ +public: + SimpleCache() = default; + ~SimpleCache(); + + bool push(int pixelSize, quint8 *&ptr) + { + QReadLocker l(&m_cacheLock); + switch (pixelSize) { + case 4: + m_4Pool.push(ptr); + break; + case 8: + m_8Pool.push(ptr); + break; + case 16: + m_16Pool.push(ptr); + break; + default: + return false; + } + + return true; + } + + bool pop(int pixelSize, quint8 *&ptr) + { + QReadLocker l(&m_cacheLock); + switch (pixelSize) { + case 4: + return m_4Pool.pop(ptr); + case 8: + return m_8Pool.pop(ptr); + case 16: + return m_16Pool.pop(ptr); + default: + return false; + } + } + + void clear(); + +private: + QReadWriteLock m_cacheLock; + KisLocklessStack m_4Pool; + KisLocklessStack m_8Pool; + KisLocklessStack m_16Pool; +}; + + /** * Stores actual tile's data */ class KisTileData { public: - KisTileData(qint32 pixelSize, const quint8 *defPixel, KisTileDataStore *store); + KisTileData(qint32 pixelSize, const quint8 *defPixel, KisTileDataStore *store, bool checkFreeMemory = true); private: KisTileData(const KisTileData& rhs, bool checkFreeMemory = true); public: ~KisTileData(); enum EnumTileDataState { NORMAL = 0, COMPRESSED, SWAPPED }; /** * Information about data stored */ inline quint8* data() const; inline void setData(const quint8 *data); inline quint32 pixelSize() const; /** * Increments usersCount of a TD and refs shared pointer counter * Used by KisTile for COW */ inline bool acquire(); /** * Decrements usersCount of a TD and derefs shared pointer counter * Used by KisTile for COW */ inline bool release(); /** * Only refs shared pointer counter. * Used only by KisMementoManager without * consideration of COW. */ inline bool ref() const; /** * Only refs shared pointer counter. * Used only by KisMementoManager without * consideration of COW. */ inline bool deref(); /** * Creates a clone of the tile data safely. * It will try to use the cached clones. */ inline KisTileData* clone(); /** * Control the access of swapper to the tile data */ inline void blockSwapping(); inline void unblockSwapping(); /** * The position of the tile data in a swap file */ inline KisChunk swapChunk() const; inline void setSwapChunk(KisChunk chunk); /** * Show whether a tile data is a part of history */ inline bool mementoed() const; inline void setMementoed(bool value); /** * Controlling methods for setting 'age' marks */ inline int age() const; inline void resetAge(); inline void markOld(); /** * Returns number of tiles (or memento items), * referencing the tile data. */ inline qint32 numUsers() const; /** * Conveniece method. Returns true iff the tile data is linked to * information only and therefore can be swapped out easily. * * Effectively equivalent to: (mementoed() && numUsers() <= 1) */ - inline bool historical() const; + inline bool historical() const; /** * Used for swapping purposes only. * Frees the memory occupied by the tile data. * (the caller must save the data beforehand) */ void releaseMemory(); /** * Used for swapping purposes only. * Allocates memory for the tile data after * it has been freed in releaseMemory(). * NOTE: the new data can be not-initialized * and you must fill it yourself! * * \see releaseMemory() */ void allocateMemory(); /** * Releases internal pools, which keep blobs where the tiles are * stored. The point is that we don't allocate the tiles from * glibc directly, but use pools (implemented via boost) to * allocate bigger chunks. This method should be called when one * knows that we have just free'd quite a lot of memory and we * won't need it anymore. E.g. when a document has been closed. */ static void releaseInternalPools(); private: void fillWithPixel(const quint8 *defPixel); static quint8* allocateData(const qint32 pixelSize); static void freeData(quint8 *ptr, const qint32 pixelSize); private: friend class KisTileDataPooler; friend class KisTileDataPoolerTest; /** * A list of pre-duplicated tiledatas. * To make a COW faster, KisTileDataPooler thread duplicates * a tile beforehand and stores clones here, in this stack */ KisTileDataCache m_clonesStack; private: friend class KisTile; friend class KisTileDataStore; friend class KisTileDataStoreIterator; friend class KisTileDataStoreReverseIterator; friend class KisTileDataStoreClockIterator; /** * The state of the tile. * Filled in by tileDataStore and * checked in KisTile::acquireFor* * see also: comment for @m_data */ mutable EnumTileDataState m_state; /** * Iterator that points to a position in the list * where the tile data is stored */ - KisTileDataListIterator m_listIterator; + int m_tileNumber = -1; private: /** * The chunk of the swap file, that corresponds * to this tile data. Used by KisSwappedDataStore. */ KisChunk m_swapChunk; /** * The flag is set by KisMementoItem to show this * tile data is going down in history. * * (m_mementoFlag && m_usersCount == 1) means that * the only user of tile data is a memento manager. */ qint32 m_mementoFlag; /** * Counts up time after last access to the tile data. * 0 - recently accessed * 1+ - not recently accessed */ //FIXME: make memory aligned int m_age; /** * The primitive for controlling swapping of the tile. * lockForRead() - used by regular threads to ensure swapper * won't touch this tile data. * tryLockForWrite() - used by swapper to check no-one reads * this tile data */ QReadWriteLock m_swapLock; private: friend class KisLowMemoryTests; /** * FIXME: We should be able to work in const environment * even when actual data is swapped out to disk */ mutable quint8* m_data; /** * How many tiles/mementoes use * this tiledata through COW? */ mutable QAtomicInt m_usersCount; /** * Shared pointer counter */ mutable QAtomicInt m_refCount; qint32 m_pixelSize; //qint32 m_timeStamp; KisTileDataStore *m_store; + static SimpleCache m_cache; + public: static const qint32 WIDTH; static const qint32 HEIGHT; }; #endif /* KIS_TILE_DATA_INTERFACE_H_ */ diff --git a/libs/image/tiles3/kis_tile_data_store.cc b/libs/image/tiles3/kis_tile_data_store.cc index a541b6c045..bd0405a428 100644 --- a/libs/image/tiles3/kis_tile_data_store.cc +++ b/libs/image/tiles3/kis_tile_data_store.cc @@ -1,363 +1,374 @@ /* * Copyright (c) 2009 Dmitry Kazakov + * Copyright (c) 2018 Andrey Kamakin * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ // to disable assert when the leak tracker is active #include "config-memory-leak-tracker.h" #include #include "kis_tile_data_store.h" #include "kis_tile_data.h" #include "kis_debug.h" #include "kis_tile_data_store_iterators.h" Q_GLOBAL_STATIC(KisTileDataStore, s_instance) //#define DEBUG_PRECLONE #ifdef DEBUG_PRECLONE #include #define DEBUG_PRECLONE_ACTION(action, oldTD, newTD) \ printf("!!! %s:\t\t\t 0x%X -> 0x%X \t\t!!!\n", \ action, (quintptr)oldTD, (quintptr) newTD) #define DEBUG_FREE_ACTION(td) \ printf("Tile data free'd \t(0x%X)\n", td) #else #define DEBUG_PRECLONE_ACTION(action, oldTD, newTD) #define DEBUG_FREE_ACTION(td) #endif #ifdef DEBUG_HIT_MISS qint64 __preclone_miss = 0; qint64 __preclone_hit = 0; qint64 __preclone_miss_user_count = 0; qint64 __preclone_miss_age = 0; #define DEBUG_COUNT_PRECLONE_HIT(td) __preclone_hit++ #define DEBUG_COUNT_PRECLONE_MISS(td) __preclone_miss++; __preclone_miss_user_count+=td->numUsers(); __preclone_miss_age+=td->age() #define DEBUG_REPORT_PRECLONE_EFFICIENCY() \ dbgKrita << "Hits:" << __preclone_hit \ << "of" << __preclone_hit + __preclone_miss \ << "(" \ << qreal(__preclone_hit) / (__preclone_hit + __preclone_miss) \ << ")" \ << "miss users" << qreal(__preclone_miss_user_count) / __preclone_miss \ << "miss age" << qreal(__preclone_miss_age) / __preclone_miss #else #define DEBUG_COUNT_PRECLONE_HIT(td) #define DEBUG_COUNT_PRECLONE_MISS(td) #define DEBUG_REPORT_PRECLONE_EFFICIENCY() #endif KisTileDataStore::KisTileDataStore() : m_pooler(this), m_swapper(this), m_numTiles(0), - m_memoryMetric(0) + m_memoryMetric(0), + m_counter(1), + m_clockIndex(1) { - m_clockIterator = m_tileDataList.end(); m_pooler.start(); m_swapper.start(); } KisTileDataStore::~KisTileDataStore() { m_pooler.terminatePooler(); m_swapper.terminateSwapper(); - if(numTiles() > 0) { - errKrita << "Warning: some tiles have leaked:"; - errKrita << "\tTiles in memory:" << numTilesInMemory() << "\n" - << "\tTotal tiles:" << numTiles(); + if (numTiles() > 0) { + errKrita << "Warning: some tiles have leaked:"; + errKrita << "\tTiles in memory:" << numTilesInMemory() << "\n" + << "\tTotal tiles:" << numTiles(); } } KisTileDataStore* KisTileDataStore::instance() { return s_instance; } KisTileDataStore::MemoryStatistics KisTileDataStore::memoryStatistics() { // in case the pooler is disabled, we should force it // to update the stats if (!m_pooler.isRunning()) { m_pooler.forceUpdateMemoryStats(); } - QMutexLocker lock(&m_listLock); + QReadLocker lock(&m_iteratorLock); MemoryStatistics stats; const qint64 metricCoeff = KisTileData::WIDTH * KisTileData::HEIGHT; stats.realMemorySize = m_pooler.lastRealMemoryMetric() * metricCoeff; stats.historicalMemorySize = m_pooler.lastHistoricalMemoryMetric() * metricCoeff; stats.poolSize = m_pooler.lastPoolMemoryMetric() * metricCoeff; stats.totalMemorySize = memoryMetric() * metricCoeff + stats.poolSize; stats.swapSize = m_swappedStore.totalMemoryMetric() * metricCoeff; return stats; } inline void KisTileDataStore::registerTileDataImp(KisTileData *td) { - td->m_listIterator = m_tileDataList.insert(m_tileDataList.end(), td); - m_numTiles++; + int index = m_counter.fetchAndAddOrdered(1); + td->m_tileNumber = index; + m_tileDataMap.assign(index, td); + m_numTiles.ref(); m_memoryMetric += td->pixelSize(); } void KisTileDataStore::registerTileData(KisTileData *td) { - QMutexLocker lock(&m_listLock); + QReadLocker lock(&m_iteratorLock); registerTileDataImp(td); } inline void KisTileDataStore::unregisterTileDataImp(KisTileData *td) { - KisTileDataListIterator tempIterator = td->m_listIterator; - - if(m_clockIterator == tempIterator) { - m_clockIterator = tempIterator + 1; + if (m_clockIndex == td->m_tileNumber) { + do { + m_clockIndex.ref(); + } while (!m_tileDataMap.get(m_clockIndex.loadAcquire()) && m_clockIndex < m_counter); } - td->m_listIterator = m_tileDataList.end(); - m_tileDataList.erase(tempIterator); - m_numTiles--; + int index = td->m_tileNumber; + td->m_tileNumber = -1; + m_tileDataMap.erase(index); + m_numTiles.deref(); m_memoryMetric -= td->pixelSize(); } void KisTileDataStore::unregisterTileData(KisTileData *td) { - QMutexLocker lock(&m_listLock); + QReadLocker lock(&m_iteratorLock); unregisterTileDataImp(td); } KisTileData *KisTileDataStore::allocTileData(qint32 pixelSize, const quint8 *defPixel) { KisTileData *td = new KisTileData(pixelSize, defPixel, this); registerTileData(td); return td; } KisTileData *KisTileDataStore::duplicateTileData(KisTileData *rhs) { KisTileData *td = 0; if (rhs->m_clonesStack.pop(td)) { DEBUG_PRECLONE_ACTION("+ Pre-clone HIT", rhs, td); DEBUG_COUNT_PRECLONE_HIT(rhs); } else { rhs->blockSwapping(); td = new KisTileData(*rhs); rhs->unblockSwapping(); DEBUG_PRECLONE_ACTION("- Pre-clone #MISS#", rhs, td); DEBUG_COUNT_PRECLONE_MISS(rhs); } registerTileData(td); return td; } void KisTileDataStore::freeTileData(KisTileData *td) { Q_ASSERT(td->m_store == this); DEBUG_FREE_ACTION(td); - m_listLock.lock(); + m_iteratorLock.lockForRead(); td->m_swapLock.lockForWrite(); - if(!td->data()) { + if (!td->data()) { m_swappedStore.forgetTileData(td); - } - else { + } else { unregisterTileDataImp(td); } td->m_swapLock.unlock(); - m_listLock.unlock(); + m_iteratorLock.unlock(); delete td; } void KisTileDataStore::ensureTileDataLoaded(KisTileData *td) { // dbgKrita << "#### SWAP MISS! ####" << td << ppVar(td->mementoed()) << ppVar(td->age()) << ppVar(td->numUsers()); checkFreeMemory(); td->m_swapLock.lockForRead(); - while(!td->data()) { + while (!td->data()) { td->m_swapLock.unlock(); /** * The order of this heavy locking is very important. * Change it only in case, you really know what you are doing. */ - m_listLock.lock(); + m_iteratorLock.lockForRead(); /** * If someone has managed to load the td from swap, then, most * probably, they have already taken the swap lock. This may * lead to a deadlock, because COW mechanism breaks lock * ordering rules in duplicateTileData() (it takes m_listLock * while the swap lock is held). In our case it is enough just * to check whether the other thread has already fetched the * data. Please notice that we do not take both of the locks * while checking this, because holding m_listLock is * enough. Nothing can happen to the tile while we hold * m_listLock. */ - if(!td->data()) { + if (!td->data()) { td->m_swapLock.lockForWrite(); m_swappedStore.swapInTileData(td); registerTileDataImp(td); td->m_swapLock.unlock(); } - m_listLock.unlock(); + m_iteratorLock.unlock(); /** * <-- In theory, livelock is possible here... */ td->m_swapLock.lockForRead(); } } bool KisTileDataStore::trySwapTileData(KisTileData *td) { /** * This function is called with m_listLock acquired */ bool result = false; - if(!td->m_swapLock.tryLockForWrite()) return result; + if (!td->m_swapLock.tryLockForWrite()) return result; - if(td->data()) { + if (td->data()) { unregisterTileDataImp(td); if (m_swappedStore.trySwapOutTileData(td)) { result = true; } else { result = false; registerTileDataImp(td); } } td->m_swapLock.unlock(); return result; } KisTileDataStoreIterator* KisTileDataStore::beginIteration() { - m_listLock.lock(); - return new KisTileDataStoreIterator(m_tileDataList, this); + m_iteratorLock.lockForWrite(); + return new KisTileDataStoreIterator(m_tileDataMap, this); } void KisTileDataStore::endIteration(KisTileDataStoreIterator* iterator) { delete iterator; - m_listLock.unlock(); + m_iteratorLock.unlock(); } KisTileDataStoreReverseIterator* KisTileDataStore::beginReverseIteration() { - m_listLock.lock(); - return new KisTileDataStoreReverseIterator(m_tileDataList, this); + m_iteratorLock.lockForWrite(); + return new KisTileDataStoreReverseIterator(m_tileDataMap, this); } void KisTileDataStore::endIteration(KisTileDataStoreReverseIterator* iterator) { delete iterator; - m_listLock.unlock(); + m_iteratorLock.unlock(); DEBUG_REPORT_PRECLONE_EFFICIENCY(); } KisTileDataStoreClockIterator* KisTileDataStore::beginClockIteration() { - m_listLock.lock(); - return new KisTileDataStoreClockIterator(m_clockIterator, m_tileDataList, this); + m_iteratorLock.lockForWrite(); + return new KisTileDataStoreClockIterator(m_tileDataMap, m_clockIndex.loadAcquire(), this); } + void KisTileDataStore::endIteration(KisTileDataStoreClockIterator* iterator) { - m_clockIterator = iterator->getFinalPosition(); + m_clockIndex = iterator->getFinalPosition(); delete iterator; - m_listLock.unlock(); + m_iteratorLock.unlock(); } void KisTileDataStore::debugPrintList() { - KisTileData *item; - Q_FOREACH (item, m_tileDataList) { + QWriteLocker l(&m_iteratorLock); + ConcurrentMap::Iterator iter(m_tileDataMap); + KisTileData *item = 0; + + while (iter.isValid()) { + item = iter.getValue(); dbgTiles << "-------------------------\n" << "TileData:\t\t\t" << item << "\n refCount:\t" << item->m_refCount; } } void KisTileDataStore::debugSwapAll() { KisTileDataStoreIterator* iter = beginIteration(); KisTileData *item; - while(iter->hasNext()) { + while (iter->hasNext()) { item = iter->next(); iter->trySwapOut(item); } endIteration(iter); // dbgKrita << "Number of tiles:" << numTiles(); // dbgKrita << "Tiles in memory:" << numTilesInMemory(); // m_swappedStore.debugStatistics(); } void KisTileDataStore::debugClear() { - QMutexLocker lock(&m_listLock); + QWriteLocker l(&m_iteratorLock); + ConcurrentMap::Iterator iter(m_tileDataMap); - Q_FOREACH (KisTileData *item, m_tileDataList) { - delete item; + while (iter.isValid()) { + delete iter.getValue(); + iter.next(); } - m_tileDataList.clear(); - m_clockIterator = m_tileDataList.end(); - + m_counter = 1; + m_clockIndex = 1; m_numTiles = 0; m_memoryMetric = 0; } -void KisTileDataStore::testingRereadConfig() { +void KisTileDataStore::testingRereadConfig() +{ m_pooler.testingRereadConfig(); m_swapper.testingRereadConfig(); kickPooler(); } void KisTileDataStore::testingSuspendPooler() { m_pooler.terminatePooler(); } void KisTileDataStore::testingResumePooler() { m_pooler.start(); } diff --git a/libs/image/tiles3/kis_tile_data_store.h b/libs/image/tiles3/kis_tile_data_store.h index 4477c3b900..125e320a62 100644 --- a/libs/image/tiles3/kis_tile_data_store.h +++ b/libs/image/tiles3/kis_tile_data_store.h @@ -1,184 +1,193 @@ /* * Copyright (c) 2009 Dmitry Kazakov + * Copyright (c) 2018 Andrey Kamakin * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + #ifndef KIS_TILE_DATA_STORE_H_ #define KIS_TILE_DATA_STORE_H_ #include "kritaimage_export.h" #include #include "kis_tile_data_interface.h" #include "kis_tile_data_pooler.h" #include "swap/kis_tile_data_swapper.h" #include "swap/kis_swapped_data_store.h" +#include "3rdparty/lock_free_map/concurrent_map.h" class KisTileDataStoreIterator; class KisTileDataStoreReverseIterator; class KisTileDataStoreClockIterator; /** * Stores tileData objects. When needed compresses them and swaps. */ class KRITAIMAGE_EXPORT KisTileDataStore { public: KisTileDataStore(); ~KisTileDataStore(); static KisTileDataStore* instance(); void debugPrintList(); struct MemoryStatistics { qint64 totalMemorySize; qint64 realMemorySize; qint64 historicalMemorySize; qint64 poolSize; qint64 swapSize; }; MemoryStatistics memoryStatistics(); /** * Returns total number of tiles present: in memory * or in a swap file */ - inline qint32 numTiles() const { - return m_numTiles + m_swappedStore.numTiles(); + inline qint32 numTiles() const + { + return m_numTiles.loadAcquire() + m_swappedStore.numTiles(); } /** * Returns the number of tiles present in memory only */ - inline qint32 numTilesInMemory() const { - return m_numTiles; + inline qint32 numTilesInMemory() const + { + return m_numTiles.loadAcquire(); } - inline void checkFreeMemory() { + inline void checkFreeMemory() + { m_swapper.checkFreeMemory(); } /** * \see m_memoryMetric */ - inline qint64 memoryMetric() const { - return m_memoryMetric; + inline qint64 memoryMetric() const + { + return m_memoryMetric.loadAcquire(); } KisTileDataStoreIterator* beginIteration(); void endIteration(KisTileDataStoreIterator* iterator); KisTileDataStoreReverseIterator* beginReverseIteration(); void endIteration(KisTileDataStoreReverseIterator* iterator); KisTileDataStoreClockIterator* beginClockIteration(); void endIteration(KisTileDataStoreClockIterator* iterator); - inline KisTileData* createDefaultTileData(qint32 pixelSize, const quint8 *defPixel) { + inline KisTileData* createDefaultTileData(qint32 pixelSize, const quint8 *defPixel) + { return allocTileData(pixelSize, defPixel); } // Called by The Memento Manager after every commit - inline void kickPooler() { + inline void kickPooler() + { m_pooler.kick(); //FIXME: maybe, rename a function? m_swapper.kick(); } /** * Try swap out the tile data. * It may fail in case the tile is being accessed * at the same moment of time. */ bool trySwapTileData(KisTileData *td); /** * WARN: The following three method are only for usage * in KisTileData. Do not call them directly! */ KisTileData *duplicateTileData(KisTileData *rhs); void freeTileData(KisTileData *td); /** * Ensures that the tile data is totally present in memory * and it's swapping is blocked by holding td->m_swapLock * in a read mode. * PRECONDITIONS: td->m_swapLock is *unlocked* * m_listRWLock is *unlocked* * POSTCONDITIONS: td->m_data is in memory and * td->m_swapLock is locked * m_listRWLock is unlocked */ void ensureTileDataLoaded(KisTileData *td); + void registerTileData(KisTileData *td); + void unregisterTileData(KisTileData *td); + private: KisTileData *allocTileData(qint32 pixelSize, const quint8 *defPixel); - void registerTileData(KisTileData *td); - void unregisterTileData(KisTileData *td); inline void registerTileDataImp(KisTileData *td); inline void unregisterTileDataImp(KisTileData *td); void freeRegisteredTiles(); friend class DeadlockyThread; friend class KisLowMemoryTests; void debugSwapAll(); void debugClear(); friend class KisTiledDataManagerTest; void testingSuspendPooler(); void testingResumePooler(); friend class KisLowMemoryBenchmark; void testingRereadConfig(); private: KisTileDataPooler m_pooler; KisTileDataSwapper m_swapper; friend class KisTileDataStoreTest; friend class KisTileDataPoolerTest; KisSwappedDataStore m_swappedStore; - KisTileDataListIterator m_clockIterator; - - QMutex m_listLock; - KisTileDataList m_tileDataList; - qint32 m_numTiles; - /** * This metric is used for computing the volume * of memory occupied by tile data objects. * metric = num_bytes / (KisTileData::WIDTH * KisTileData::HEIGHT) */ - qint64 m_memoryMetric; + QAtomicInt m_numTiles; + QAtomicInt m_memoryMetric; + QAtomicInt m_counter; + QAtomicInt m_clockIndex; + ConcurrentMap m_tileDataMap; + QReadWriteLock m_iteratorLock; }; template inline T MiB_TO_METRIC(T value) { unsigned long long __MiB = 1ULL << 20; return value * (__MiB / (KisTileData::WIDTH * KisTileData::HEIGHT)); } #endif /* KIS_TILE_DATA_STORE_H_ */ diff --git a/libs/image/tiles3/kis_tile_data_store_iterators.h b/libs/image/tiles3/kis_tile_data_store_iterators.h index de3aaf87f6..a090e37df9 100644 --- a/libs/image/tiles3/kis_tile_data_store_iterators.h +++ b/libs/image/tiles3/kis_tile_data_store_iterators.h @@ -1,176 +1,172 @@ /* * Copyright (c) 2010 Dmitry Kazakov + * Copyright (c) 2018 Andrey Kamakin * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ + #ifndef KIS_TILE_DATA_STORE_ITERATORS_H_ #define KIS_TILE_DATA_STORE_ITERATORS_H_ +#include "kis_tile_data.h" +#include "kis_debug.h" + /** * KisTileDataStoreIterator, * KisTileDataStoreReverseIterator, * KisTileDataStoreClockIterator * - are general iterators for the contents of KisTileDataStore. * The store starts holding a lock when returns one of such * iterators, so no one will be able to change the list while * you are iterating. * * But be careful! You can't change the list while iterating either, * because it can invalidate the iterator. This is a general rule. */ class KisTileDataStoreIterator { public: - KisTileDataStoreIterator(KisTileDataList &list, KisTileDataStore *store) - : m_list(list), + KisTileDataStoreIterator(ConcurrentMap &map, KisTileDataStore *store) + : m_map(map), m_store(store) { - m_iterator = m_list.begin(); - m_end = m_list.end(); + m_iterator.setMap(m_map); } - inline KisTileData* peekNext() { - return *m_iterator; + inline KisTileData* peekNext() + { + return m_iterator.getValue(); } - inline KisTileData* next() { - return *(m_iterator++); + inline KisTileData* next() + { + KisTileData *current = m_iterator.getValue(); + m_iterator.next(); + return current; } - inline bool hasNext() const { - return m_iterator != m_end; + inline bool hasNext() const + { + return m_iterator.isValid(); } - inline bool trySwapOut(KisTileData *td) { - if(td->m_listIterator == m_iterator) - m_iterator++; + inline bool trySwapOut(KisTileData *td) + { + if (td == m_iterator.getValue()) { + m_iterator.next(); + } return m_store->trySwapTileData(td); } private: - KisTileDataList &m_list; - KisTileDataListIterator m_iterator; - KisTileDataListIterator m_end; + ConcurrentMap &m_map; + ConcurrentMap::Iterator m_iterator; KisTileDataStore *m_store; }; -class KisTileDataStoreReverseIterator +class KisTileDataStoreReverseIterator : public KisTileDataStoreIterator { public: - KisTileDataStoreReverseIterator(KisTileDataList &list, KisTileDataStore *store) - : m_list(list), - m_store(store) + KisTileDataStoreReverseIterator(ConcurrentMap &map, KisTileDataStore *store) + : KisTileDataStoreIterator(map, store) { - m_iterator = m_list.end(); - m_begin = m_list.begin(); - } - - inline KisTileData* peekNext() { - return *(m_iterator-1); - } - - inline KisTileData* next() { - return *(--m_iterator); - } - - inline bool hasNext() const { - return m_iterator != m_begin; - } - - inline bool trySwapOut(KisTileData *td) { - if(td->m_listIterator == m_iterator) - m_iterator++; - - return m_store->trySwapTileData(td); } - -private: - KisTileDataList &m_list; - KisTileDataListIterator m_iterator; - KisTileDataListIterator m_begin; - KisTileDataStore *m_store; }; class KisTileDataStoreClockIterator { public: - KisTileDataStoreClockIterator(KisTileDataListIterator startItem, KisTileDataList &list, KisTileDataStore *store) - : m_list(list), + KisTileDataStoreClockIterator(ConcurrentMap &map, + int startIndex, + KisTileDataStore *store) + : m_map(map), m_store(store) { - m_end = m_list.end(); + m_iterator.setMap(m_map); + m_finalPosition = m_iterator.getValue()->m_tileNumber; + m_startItem = m_map.get(startIndex); - if(startItem == m_list.begin() || - startItem == m_end) { - m_iterator = m_list.begin(); - m_startItem = m_end; + if (m_iterator.getValue() == m_startItem || !m_startItem) { + m_startItem = 0; m_endReached = true; - } - else { - m_startItem = startItem; - m_iterator = startItem; + } else { + while (m_iterator.getValue() != m_startItem) { + m_iterator.next(); + } m_endReached = false; } } - inline KisTileData* peekNext() { - if(m_iterator == m_end) { - m_iterator = m_list.begin(); + inline KisTileData* peekNext() + { + if (!m_iterator.isValid()) { + m_iterator.setMap(m_map); m_endReached = true; } - return *m_iterator; + return m_iterator.getValue(); } - inline KisTileData* next() { - if(m_iterator == m_end) { - m_iterator = m_list.begin(); + inline KisTileData* next() + { + if (!m_iterator.isValid()) { + m_iterator.setMap(m_map); m_endReached = true; } - return *(m_iterator++); + KisTileData *current = m_iterator.getValue(); + m_iterator.next(); + return current; } - inline bool hasNext() const { - return !(m_endReached && m_iterator == m_startItem); + inline bool hasNext() const + { + return !(m_endReached && m_iterator.getValue() == m_startItem); } - inline bool trySwapOut(KisTileData *td) { - if(td->m_listIterator == m_iterator) - m_iterator++; + inline bool trySwapOut(KisTileData *td) + { + if (td == m_iterator.getValue()) { + m_iterator.next(); + } return m_store->trySwapTileData(td); } private: friend class KisTileDataStore; - inline KisTileDataListIterator getFinalPosition() { - return m_iterator; + inline int getFinalPosition() + { + if (!m_iterator.isValid()) { + return m_finalPosition; + } + + return m_iterator.getValue()->m_tileNumber; } private: - KisTileDataList &m_list; + ConcurrentMap &m_map; + ConcurrentMap::Iterator m_iterator; + KisTileData *m_startItem; bool m_endReached; - KisTileDataListIterator m_iterator; - KisTileDataListIterator m_startItem; - KisTileDataListIterator m_end; KisTileDataStore *m_store; + int m_finalPosition; }; #endif /* KIS_TILE_DATA_STORE_ITERATORS_H_ */ diff --git a/libs/image/tiles3/kis_tile_hash_table2.h b/libs/image/tiles3/kis_tile_hash_table2.h index f468f46000..3d3a8fd3a3 100644 --- a/libs/image/tiles3/kis_tile_hash_table2.h +++ b/libs/image/tiles3/kis_tile_hash_table2.h @@ -1,371 +1,402 @@ +/* + * Copyright (c) 2018 Andrey Kamakin + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + #ifndef KIS_TILEHASHTABLE_2_H #define KIS_TILEHASHTABLE_2_H #include "kis_shared.h" #include "kis_shared_ptr.h" #include "3rdparty/lock_free_map/concurrent_map.h" #include "kis_tile.h" #define SANITY_CHECK /** * This is a template for a hash table that stores tiles (or some other * objects resembling tiles). Actually, this object should only have * col()/row() methods and be able to answer setNext()/next() requests to * be stored here. It is used in KisTiledDataManager and * KisMementoManager. * * How to use: * 1) each hash must be unique, otherwise tiles would rewrite each-other * 2) 0 key is reserved, so can't be used * 3) col and row must be less than 0x7FFF to guarantee uniqueness of hash for each pair */ template class KisTileHashTableIteratorTraits2; template class KisTileHashTableTraits2 { static constexpr bool isInherited = std::is_convertible::value; Q_STATIC_ASSERT_X(isInherited, "Template must inherit KisShared"); public: typedef T TileType; typedef KisSharedPtr TileTypeSP; typedef KisWeakSharedPtr TileTypeWSP; KisTileHashTableTraits2(KisMementoManager *mm); KisTileHashTableTraits2(const KisTileHashTableTraits2 &ht, KisMementoManager *mm); ~KisTileHashTableTraits2(); bool isEmpty() { return !m_numTiles.load(); } bool tileExists(qint32 col, qint32 row); /** * Returns a tile in position (col,row). If no tile exists, * returns null. * \param col column of the tile * \param row row of the tile */ TileTypeSP getExistingTile(qint32 col, qint32 row); /** * Returns a tile in position (col,row). If no tile exists, * creates a new one, attaches it to the list and returns. * \param col column of the tile * \param row row of the tile * \param newTile out-parameter, returns true if a new tile * was created */ TileTypeSP getTileLazy(qint32 col, qint32 row, bool& newTile); /** * Returns a tile in position (col,row). If no tile exists, * creates nothing, but returns shared default tile object * of the table. Be careful, this object has column and row * parameters set to (qint32_MIN, qint32_MIN). * \param col column of the tile * \param row row of the tile * \param existingTile returns true if the tile actually exists in the table * and it is not a lazily created default wrapper tile */ TileTypeSP getReadOnlyTileLazy(qint32 col, qint32 row, bool &existingTile); void addTile(TileTypeSP tile); bool deleteTile(TileTypeSP tile); bool deleteTile(qint32 col, qint32 row); void clear(); void setDefaultTileData(KisTileData *defaultTileData); KisTileData* defaultTileData(); qint32 numTiles() { return m_numTiles.load(); } void debugPrintInfo(); void debugMaxListLength(qint32 &min, qint32 &max); friend class KisTileHashTableIteratorTraits2; private: struct MemoryReclaimer { MemoryReclaimer(TileType *data) : d(data) {} void destroy() { TileTypeSP::deref(reinterpret_cast(this), d); this->MemoryReclaimer::~MemoryReclaimer(); delete this; } private: TileType *d; }; inline quint32 calculateHash(qint32 col, qint32 row) { #ifdef SANITY_CHECK KIS_ASSERT_RECOVER_NOOP(row < 0x7FFF && col < 0x7FFF) #endif // SANITY_CHECK if (col == 0 && row == 0) { col = 0x7FFF; row = 0x7FFF; } return ((static_cast(row) << 16) | (static_cast(col) & 0xFFFF)); } inline void insert(quint32 key, TileTypeSP value) { + QReadLocker l(&m_iteratorLock); TileTypeSP::ref(&value, value.data()); TileType *result = m_map.assign(key, value.data()); if (result) { m_map.getGC().enqueue(&MemoryReclaimer::destroy, new MemoryReclaimer(result)); } else { m_numTiles.fetchAndAddRelaxed(1); } m_map.getGC().update(m_map.migrationInProcess()); } inline bool erase(quint32 key) { bool wasDeleted = false; TileType *result = m_map.erase(key); if (result) { wasDeleted = true; m_numTiles.fetchAndSubRelaxed(1); m_map.getGC().enqueue(&MemoryReclaimer::destroy, new MemoryReclaimer(result)); } m_map.getGC().update(m_map.migrationInProcess()); return wasDeleted; } private: ConcurrentMap m_map; /** * We still need something to guard changes in m_defaultTileData, * otherwise there will be concurrent read/writes, resulting in broken memory. */ QReadWriteLock m_defaultPixelDataLock; + QReadWriteLock m_iteratorLock; QAtomicInt m_numTiles; KisTileData *m_defaultTileData; KisMementoManager *m_mementoManager; }; template class KisTileHashTableIteratorTraits2 { public: typedef T TileType; typedef KisSharedPtr TileTypeSP; typedef typename ConcurrentMap::Iterator Iterator; KisTileHashTableIteratorTraits2(KisTileHashTableTraits2 *ht) : m_ht(ht) { + m_ht->m_iteratorLock.lockForWrite(); m_iter.setMap(m_ht->m_map); } + ~KisTileHashTableIteratorTraits2() + { + m_ht->m_iteratorLock.unlock(); + } + void next() { m_iter.next(); } TileTypeSP tile() const { return TileTypeSP(m_iter.getValue()); } bool isDone() const { return !m_iter.isValid(); } void deleteCurrent() { m_ht->erase(m_iter.getKey()); next(); } void moveCurrentToHashTable(KisTileHashTableTraits2 *newHashTable) { TileTypeSP tile = m_iter.getValue(); next(); m_ht->deleteTile(tile); newHashTable->addTile(tile); } private: KisTileHashTableTraits2 *m_ht; Iterator m_iter; }; template KisTileHashTableTraits2::KisTileHashTableTraits2(KisMementoManager *mm) : m_numTiles(0), m_defaultTileData(0), m_mementoManager(mm) { } template KisTileHashTableTraits2::KisTileHashTableTraits2(const KisTileHashTableTraits2 &ht, KisMementoManager *mm) : KisTileHashTableTraits2(mm) { setDefaultTileData(ht.m_defaultTileData); + QWriteLocker l(const_cast(&ht.m_iteratorLock)); typename ConcurrentMap::Iterator iter(const_cast &>(ht.m_map)); + while (iter.isValid()) { insert(iter.getKey(), iter.getValue()); iter.next(); } } template KisTileHashTableTraits2::~KisTileHashTableTraits2() { clear(); m_map.getGC().flush(); setDefaultTileData(0); } template bool KisTileHashTableTraits2::tileExists(qint32 col, qint32 row) { return getExistingTile(col, row); } template typename KisTileHashTableTraits2::TileTypeSP KisTileHashTableTraits2::getExistingTile(qint32 col, qint32 row) { quint32 idx = calculateHash(col, row); TileTypeSP result = m_map.get(idx); m_map.getGC().update(m_map.migrationInProcess()); return result; } template typename KisTileHashTableTraits2::TileTypeSP KisTileHashTableTraits2::getTileLazy(qint32 col, qint32 row, bool &newTile) { + QReadLocker l(&m_iteratorLock); newTile = false; TileTypeSP tile; quint32 idx = calculateHash(col, row); typename ConcurrentMap::Mutator mutator = m_map.insertOrFind(idx); if (!mutator.getValue()) { { QReadLocker guard(&m_defaultPixelDataLock); tile = new TileType(col, row, m_defaultTileData, m_mementoManager); } TileTypeSP::ref(&tile, tile.data()); TileType *result = mutator.exchangeValue(tile.data()); if (result) { m_map.getGC().enqueue(&MemoryReclaimer::destroy, new MemoryReclaimer(result)); } else { newTile = true; m_numTiles.fetchAndAddRelaxed(1); } tile = m_map.get(idx); } else { tile = mutator.getValue(); } m_map.getGC().update(m_map.migrationInProcess()); return tile; } template typename KisTileHashTableTraits2::TileTypeSP KisTileHashTableTraits2::getReadOnlyTileLazy(qint32 col, qint32 row, bool &existingTile) { quint32 idx = calculateHash(col, row); TileTypeSP tile = m_map.get(idx); existingTile = tile; if (!existingTile) { QReadLocker guard(&m_defaultPixelDataLock); tile = new TileType(col, row, m_defaultTileData, 0); } m_map.getGC().update(m_map.migrationInProcess()); return tile; } template void KisTileHashTableTraits2::addTile(TileTypeSP tile) { quint32 idx = calculateHash(tile->col(), tile->row()); insert(idx, tile); } template bool KisTileHashTableTraits2::deleteTile(TileTypeSP tile) { return deleteTile(tile->col(), tile->row()); } template bool KisTileHashTableTraits2::deleteTile(qint32 col, qint32 row) { quint32 idx = calculateHash(col, row); return erase(idx); } template void KisTileHashTableTraits2::clear() { + QWriteLocker l(&m_iteratorLock); typename ConcurrentMap::Iterator iter(m_map); + while (iter.isValid()) { erase(iter.getKey()); iter.next(); } } template inline void KisTileHashTableTraits2::setDefaultTileData(KisTileData *defaultTileData) { QWriteLocker guard(&m_defaultPixelDataLock); if (m_defaultTileData) { m_defaultTileData->release(); m_defaultTileData = 0; } if (defaultTileData) { defaultTileData->acquire(); m_defaultTileData = defaultTileData; } } template inline KisTileData* KisTileHashTableTraits2::defaultTileData() { QReadLocker guard(&m_defaultPixelDataLock); return m_defaultTileData; } template void KisTileHashTableTraits2::debugPrintInfo() { } template void KisTileHashTableTraits2::debugMaxListLength(qint32 &min, qint32 &max) { } typedef KisTileHashTableTraits2 KisTileHashTable; typedef KisTileHashTableIteratorTraits2 KisTileHashTableIterator; typedef KisTileHashTableIteratorTraits2 KisTileHashTableConstIterator; #endif // KIS_TILEHASHTABLE_2_H diff --git a/libs/image/tiles3/tests/kis_tile_data_store_test.cpp b/libs/image/tiles3/tests/kis_tile_data_store_test.cpp index c4ee57dd76..7e8c1c88e5 100644 --- a/libs/image/tiles3/tests/kis_tile_data_store_test.cpp +++ b/libs/image/tiles3/tests/kis_tile_data_store_test.cpp @@ -1,185 +1,192 @@ /* * Copyright (c) 2010 Dmitry Kazakov * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #include "kis_tile_data_store_test.h" #include #include "kis_debug.h" #include "kis_image_config.h" #include "tiles3/kis_tiled_data_manager.h" #include "tiles_test_utils.h" #include "tiles3/kis_tile_data_store.h" #include "tiles3/kis_tile_data_store_iterators.h" void KisTileDataStoreTest::testClockIterator() { - KisTileDataStore::instance()->debugClear(); + KisTileDataStore *store = KisTileDataStore::instance(); + store->debugClear(); const qint32 pixelSize = 1; quint8 defaultPixel = 128; QList tileDataList; + KisTileData *item; - tileDataList.append(KisTileDataStore::instance()->createDefaultTileData(pixelSize, &defaultPixel)); - tileDataList.append(KisTileDataStore::instance()->createDefaultTileData(pixelSize, &defaultPixel)); - tileDataList.append(KisTileDataStore::instance()->createDefaultTileData(pixelSize, &defaultPixel)); + item = new KisTileData(pixelSize, &defaultPixel, store, false); + store->registerTileData(item); + tileDataList.append(item); + item = new KisTileData(pixelSize, &defaultPixel, store, false); + store->registerTileData(item); + tileDataList.append(item); + item = new KisTileData(pixelSize, &defaultPixel, store, false); + store->registerTileData(item); + tileDataList.append(item); /// First, full cycle! - KisTileDataStoreClockIterator *iter = KisTileDataStore::instance()->beginClockIteration(); - KisTileData *item; + KisTileDataStoreClockIterator *iter = store->beginClockIteration(); QVERIFY(iter->hasNext()); item = iter->next(); QCOMPARE(item, tileDataList[0]); QVERIFY(iter->hasNext()); item = iter->next(); - QCOMPARE(item, tileDataList[1]); + QCOMPARE(item, tileDataList[2]); QVERIFY(iter->hasNext()); item = iter->next(); - QCOMPARE(item, tileDataList[2]); + QCOMPARE(item, tileDataList[1]); QVERIFY(!iter->hasNext()); - KisTileDataStore::instance()->endIteration(iter); + store->endIteration(iter); /// Second, iterate until the second item! - iter = KisTileDataStore::instance()->beginClockIteration(); + iter = store->beginClockIteration(); QVERIFY(iter->hasNext()); item = iter->next(); QCOMPARE(item, tileDataList[0]); - KisTileDataStore::instance()->endIteration(iter); + store->endIteration(iter); /// Third, check the position restored! - iter = KisTileDataStore::instance()->beginClockIteration(); + iter = store->beginClockIteration(); QVERIFY(iter->hasNext()); item = iter->next(); - QCOMPARE(item, tileDataList[1]); + QCOMPARE(item, tileDataList[2]); QVERIFY(iter->hasNext()); item = iter->next(); - QCOMPARE(item, tileDataList[2]); + QCOMPARE(item, tileDataList[1]); QVERIFY(iter->hasNext()); item = iter->next(); QCOMPARE(item, tileDataList[0]); QVERIFY(!iter->hasNext()); - KisTileDataStore::instance()->endIteration(iter); + store->endIteration(iter); - /// By this moment KisTileDataStore::instance()->m_clockIterator has been set - /// onto the second (tileDataList[1]) item. + /// By this moment clock index has been set + /// onto the last item. /// Let's try remove it and see what will happen... - KisTileDataStore::instance()->freeTileData(tileDataList[1]); + store->freeTileData(tileDataList[0]); - iter = KisTileDataStore::instance()->beginClockIteration(); + iter = store->beginClockIteration(); QVERIFY(iter->hasNext()); item = iter->next(); QCOMPARE(item, tileDataList[2]); QVERIFY(iter->hasNext()); item = iter->next(); - QCOMPARE(item, tileDataList[0]); + QCOMPARE(item, tileDataList[1]); QVERIFY(!iter->hasNext()); - KisTileDataStore::instance()->endIteration(iter); + store->endIteration(iter); - KisTileDataStore::instance()->freeTileData(tileDataList[0]); - KisTileDataStore::instance()->freeTileData(tileDataList[2]); + store->freeTileData(tileDataList[2]); + store->freeTileData(tileDataList[1]); } void KisTileDataStoreTest::testLeaks() { KisTileDataStore::instance()->debugClear(); QCOMPARE(KisTileDataStore::instance()->numTiles(), 0); const qint32 pixelSize = 1; quint8 defaultPixel = 128; KisTiledDataManager *dm = new KisTiledDataManager(pixelSize, &defaultPixel); KisTileSP tile = dm->getTile(0, 0, true); tile->lockForWrite(); tile->unlock(); tile = 0; delete dm; QCOMPARE(KisTileDataStore::instance()->numTiles(), 0); } #define COLUMN2COLOR(col) (col%255) void KisTileDataStoreTest::testSwapping() { KisImageConfig config(false); config.setMemoryHardLimitPercent(100.0 / KisImageConfig::totalRAM()); config.setMemorySoftLimitPercent(0); KisTileDataStore::instance()->debugClear(); const qint32 pixelSize = 1; quint8 defaultPixel = 128; KisTiledDataManager dm(pixelSize, &defaultPixel); for(qint32 col = 0; col < 1000; col++) { KisTileSP tile = dm.getTile(col, 0, true); tile->lockForWrite(); KisTileData *td = tile->tileData(); QVERIFY(memoryIsFilled(defaultPixel, td->data(), TILESIZE)); memset(td->data(), COLUMN2COLOR(col), TILESIZE); QVERIFY(memoryIsFilled(COLUMN2COLOR(col), td->data(), TILESIZE)); tile->unlock(); } //KisTileDataStore::instance()->debugSwapAll(); for(qint32 col = 0; col < 1000; col++) { KisTileSP tile = dm.getTile(col, 0, true); tile->lockForRead(); KisTileData *td = tile->tileData(); QVERIFY(memoryIsFilled(COLUMN2COLOR(col), td->data(), TILESIZE)); tile->unlock(); } } QTEST_MAIN(KisTileDataStoreTest)