File indexing completed on 2024-12-22 04:10:29

 /*
  *  SPDX-FileCopyrightText: 2010 Dmitry Kazakov <dimula73@gmail.com>
  *
  *  SPDX-License-Identifier: GPL-2.0-or-later
  */
 
 #include "kis_debug.h"
 #include "kis_chunk_allocator.h"
 
 
 #define GAP_SIZE(low, high) ((high) - (low) > 0 ? (high) - (low) - 1 : 0)
 
 #define HAS_NEXT(list,iter) ((iter)!=(list).end())
 #define HAS_PREVIOUS(list,iter) ((iter)!=(list).begin())
 
 #define PEEK_NEXT(iter) (*(iter))
 #define PEEK_PREVIOUS(iter) (*((iter)-1))
 #define WRAP_PREVIOUS_CHUNK_DATA(iter) (KisChunk((iter)-1))
 
 
 KisChunkAllocator::KisChunkAllocator(quint64 slabSize, quint64 storeSize)
 {
     m_storeMaxSize = storeSize;
     m_storeSlabSize = slabSize;
 
     m_iterator = m_list.begin();
     m_storeSize = m_storeSlabSize;
     INIT_FAIL_COUNTER();
 }
 
 KisChunkAllocator::~KisChunkAllocator()
 {
 }
 
 KisChunk KisChunkAllocator::getChunk(quint64 size)
 {
     KisChunkDataListIterator startPosition = m_iterator;
     START_COUNTING();
 
     forever {
         if(tryInsertChunk(m_list, m_iterator, size))
             return WRAP_PREVIOUS_CHUNK_DATA(m_iterator);
 
         if(m_iterator == m_list.end())
             break;
 
         m_iterator++;
         REGISTER_STEP();
     }
 
     REGISTER_FAIL();
     m_iterator = m_list.begin();
 
     forever {
         if(tryInsertChunk(m_list, m_iterator, size))
             return WRAP_PREVIOUS_CHUNK_DATA(m_iterator);
 
         if(m_iterator == m_list.end() || m_iterator == startPosition)
             break;
 
         m_iterator++;
         REGISTER_STEP();
     }
 
     REGISTER_FAIL();
     m_iterator = m_list.end();
 
     while ((m_storeSize += m_storeSlabSize) <= m_storeMaxSize) {
         if(tryInsertChunk(m_list, m_iterator, size))
             return WRAP_PREVIOUS_CHUNK_DATA(m_iterator);
     }
 
     qFatal("KisChunkAllocator: out of swap space");
 
     // just let gcc be happy! :)
     return KisChunk(m_list.end());
 }
 
 bool KisChunkAllocator::tryInsertChunk(KisChunkDataList &list,
                                        KisChunkDataListIterator &iterator,
                                        quint64 size)
 {
     bool result = false;
     quint64 highBound = m_storeSize;
     quint64 lowBound = 0;
     quint64 shift = 0;
 
     if(HAS_NEXT(list, iterator))
         highBound = PEEK_NEXT(iterator).m_begin;
 
     if(HAS_PREVIOUS(list, iterator)) {
         lowBound = PEEK_PREVIOUS(iterator).m_end;
         shift = 1;
     }
 
     if(GAP_SIZE(lowBound, highBound) >= size) {
         list.insert(iterator, KisChunkData(lowBound + shift, size));
         result = true;
     }
 
     return result;
 }
 
 void KisChunkAllocator::freeChunk(KisChunk chunk)
 {
     if(m_iterator != m_list.end() && m_iterator == chunk.position()) {
         m_iterator = m_list.erase(m_iterator);
         return;
     }
 
     Q_ASSERT(chunk.position()->m_begin == chunk.begin());
     m_list.erase(chunk.position());
 }
 
 
 
 /**************************************************************/
 /*******             Debugging features                ********/
 /**************************************************************/
 
 
 void KisChunkAllocator::debugChunks()
 {
     quint64 idx = 0;
     KisChunkDataListIterator i;
 
     for(i = m_list.begin(); i != m_list.end(); ++i) {
         qInfo("chunk #%lld: [%lld %lld]", idx++, i->m_begin, i->m_end);
     }
 }
 
 bool KisChunkAllocator::sanityCheck(bool pleaseCrash)
 {
     bool failed = false;
     KisChunkDataListIterator i;
 
     for(i = m_list.begin(); i != m_list.end(); ++i) {
         if(HAS_PREVIOUS(m_list, i)) {
             if(PEEK_PREVIOUS(i).m_end >= i->m_begin) {
                 qWarning("Chunks overlapped: [%lld %lld], [%lld %lld]", PEEK_PREVIOUS(i).m_begin, PEEK_PREVIOUS(i).m_end, i->m_begin, i->m_end);
                 failed = true;
                 break;
             }
         }
     }
 
     i = m_list.end();
     if(HAS_PREVIOUS(m_list, i)) {
         if(PEEK_PREVIOUS(i).m_end >= m_storeSize) {
             warnKrita << "Last chunk exceeds the store size!";
             failed = true;
         }
     }
 
     if(failed && pleaseCrash)
         qFatal("KisChunkAllocator: sanity check failed!");
 
     return !failed;
 }
 
 qreal KisChunkAllocator::debugFragmentation(bool toStderr)
 {
     KisChunkDataListIterator i;
 
     quint64 totalSize = 0;
     quint64 allocated = 0;
     quint64 free = 0;
     qreal fragmentation = 0;
 
     for(i = m_list.begin(); i != m_list.end(); ++i) {
         allocated += i->m_end - i->m_begin + 1;
 
         if(HAS_PREVIOUS(m_list, i))
             free += GAP_SIZE(PEEK_PREVIOUS(i).m_end, i->m_begin);
         else
             free += i->m_begin;
     }
 
     i = m_list.end();
     if(HAS_PREVIOUS(m_list, i))
         totalSize = PEEK_PREVIOUS(i).m_end + 1;
 
     if(totalSize)
         fragmentation = qreal(free) / totalSize;
 
     if(toStderr) {
         qInfo() << "Hard store limit:\t" << m_storeMaxSize;
         qInfo() << "Slab size:\t\t" << m_storeSlabSize;
         qInfo() << "Num slabs:\t\t" << m_storeSize / m_storeSlabSize;
         qInfo() << "Store size:\t\t" << m_storeSize;
         qInfo() << "Total used:\t\t" << totalSize;
         qInfo() << "Allocated:\t\t" << allocated;
         qInfo() << "Free:\t\t\t" << free;
         qInfo() << "Fragmentation:\t\t" << fragmentation;
         DEBUG_FAIL_COUNTER();
     }
 
     Q_ASSERT(totalSize == allocated + free);
 
     return fragmentation;
 }