diff --git a/libs/image/tiles3/KisTiledExtentManager.h b/libs/image/tiles3/KisTiledExtentManager.h --- a/libs/image/tiles3/KisTiledExtentManager.h +++ b/libs/image/tiles3/KisTiledExtentManager.h @@ -20,6 +20,7 @@ #define KISTILEDEXTENTMANAGER_H #include +#include #include #include #include "kritaimage_export.h" @@ -27,25 +28,59 @@ 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/KisTiledExtentManager.cpp b/libs/image/tiles3/KisTiledExtentManager.cpp --- a/libs/image/tiles3/KisTiledExtentManager.cpp +++ b/libs/image/tiles3/KisTiledExtentManager.cpp @@ -23,76 +23,267 @@ #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(); @@ -101,52 +292,56 @@ 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/kis_tile_data.cc b/libs/image/tiles3/kis_tile_data.cc --- a/libs/image/tiles3/kis_tile_data.cc +++ b/libs/image/tiles3/kis_tile_data.cc @@ -35,8 +35,33 @@ 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), @@ -45,7 +70,9 @@ m_pixelSize(pixelSize), m_store(store) { - m_store->checkFreeMemory(); + if (checkFreeMemory) { + m_store->checkFreeMemory(); + } m_data = allocateData(m_pixelSize); fillWithPixel(defPixel); @@ -72,7 +99,7 @@ m_pixelSize(rhs.m_pixelSize), m_store(rhs.m_store) { - if(checkFreeMemory) { + if (checkFreeMemory) { m_store->checkFreeMemory(); } m_data = allocateData(m_pixelSize); @@ -90,7 +117,7 @@ { 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); } } @@ -103,7 +130,7 @@ } KisTileData *clone = 0; - while(m_clonesStack.pop(clone)) { + while (m_clonesStack.pop(clone)) { delete clone; } @@ -120,15 +147,18 @@ { 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; @@ -136,15 +166,18 @@ 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; + } } } @@ -166,12 +199,12 @@ 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; } @@ -199,6 +232,7 @@ if (!failedToLock) { // purge the pools memory + m_cache.clear(); BoostPool4BPP::purge_memory(); BoostPool8BPP::purge_memory(); diff --git a/libs/image/tiles3/kis_tile_data_interface.h b/libs/image/tiles3/kis_tile_data_interface.h --- a/libs/image/tiles3/kis_tile_data_interface.h +++ b/libs/image/tiles3/kis_tile_data_interface.h @@ -41,13 +41,64 @@ 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); @@ -137,7 +188,7 @@ * * Effectively equivalent to: (mementoed() && numUsers() <= 1) */ - inline bool historical() const; + inline bool historical() const; /** * Used for swapping purposes only. @@ -202,7 +253,7 @@ * Iterator that points to a position in the list * where the tile data is stored */ - KisTileDataListIterator m_listIterator; + int m_tileNumber = -1; private: /** @@ -264,6 +315,8 @@ //qint32 m_timeStamp; KisTileDataStore *m_store; + static SimpleCache m_cache; + public: static const qint32 WIDTH; static const qint32 HEIGHT; diff --git a/libs/image/tiles3/kis_tile_data_store.h b/libs/image/tiles3/kis_tile_data_store.h --- a/libs/image/tiles3/kis_tile_data_store.h +++ b/libs/image/tiles3/kis_tile_data_store.h @@ -26,6 +26,7 @@ #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; @@ -59,26 +60,30 @@ * 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(); @@ -90,12 +95,14 @@ 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? @@ -131,11 +138,12 @@ */ 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(); @@ -159,18 +167,17 @@ 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 diff --git a/libs/image/tiles3/kis_tile_data_store.cc b/libs/image/tiles3/kis_tile_data_store.cc --- a/libs/image/tiles3/kis_tile_data_store.cc +++ b/libs/image/tiles3/kis_tile_data_store.cc @@ -70,9 +70,10 @@ : 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(); } @@ -82,10 +83,10 @@ 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(); } } @@ -102,7 +103,7 @@ m_pooler.forceUpdateMemoryStats(); } - QMutexLocker lock(&m_listLock); + QReadLocker lock(&m_iteratorLock); MemoryStatistics stats; @@ -121,34 +122,37 @@ 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); } @@ -184,18 +188,17 @@ 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; } @@ -207,14 +210,14 @@ 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 @@ -229,7 +232,7 @@ * m_listLock. */ - if(!td->data()) { + if (!td->data()) { td->m_swapLock.lockForWrite(); m_swappedStore.swapInTileData(td); @@ -238,7 +241,7 @@ td->m_swapLock.unlock(); } - m_listLock.unlock(); + m_iteratorLock.unlock(); /** * <-- In theory, livelock is possible here... @@ -255,9 +258,9 @@ */ 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; @@ -273,43 +276,48 @@ 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; @@ -320,7 +328,7 @@ { KisTileDataStoreIterator* iter = beginIteration(); KisTileData *item; - while(iter->hasNext()) { + while (iter->hasNext()) { item = iter->next(); iter->trySwapOut(item); } @@ -333,20 +341,22 @@ 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(); diff --git a/libs/image/tiles3/kis_tile_data_store_iterators.h b/libs/image/tiles3/kis_tile_data_store_iterators.h --- a/libs/image/tiles3/kis_tile_data_store_iterators.h +++ b/libs/image/tiles3/kis_tile_data_store_iterators.h @@ -18,6 +18,9 @@ #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, @@ -35,141 +38,132 @@ 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/tests/kis_tile_data_store_test.cpp b/libs/image/tiles3/tests/kis_tile_data_store_test.cpp --- a/libs/image/tiles3/tests/kis_tile_data_store_test.cpp +++ b/libs/image/tiles3/tests/kis_tile_data_store_test.cpp @@ -32,21 +32,28 @@ 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(); @@ -54,37 +61,37 @@ 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(); @@ -92,16 +99,16 @@ 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(); @@ -109,14 +116,14 @@ 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()