Sunday, May 10, 2009

First step of tile engine

Today i've implemented the things projected in previous post. I couldn't imagine that multithreading programming is so exciting! =) It's a pretty good exercise for brains :)

The three classes mentioned earlier are committed to New tiles engine called "tiles3" ;). Some details are changed, but the idea remained the same. Of course you can't build krita with this engine =), but you can test some features of it with a simple test suite located in krita/image/tiles3/tests/test_tiles_cow/. The list of "features" is quite short yet. Atm it simply creates a few tiles and shares tile data between them with CopyOnWrite mechanism.

And there are a few issues i have already faced with. The main is deadlocks. There can be a plenty of situations when the tilesystem will be stuck in the lock forever. And the worst thing we can't use "Ostrich algorithm" suggested by Tannenbaum! =). At the moment i see the only solution for this problem: locking rules.

So "the first great locking rule" sounds like:
Everytime lock for read first.

E.g. if you want to copy some data from one tile to another (and they both share the same tiledata) you should acquire the source first, and only then acquire the destination.

Here is kind of "variations table". Imagine tile1 has already acquired some lock, but tile2 wants to acquire it too (both use the same tiledata).
A guess there are many rules to be discovered. But i hope they i'll be able to encapsulate them inside iterators.

Friday, May 8, 2009

Krita's tilesystem project idea

Some days ago i've thought over my GSoC project for Krita. Here are my ideas how to refactor KisTilesDataManager.

I'll begin with the lowest level: KisTile. New KisTile class will be an abstraction of a tile that doesn't store the actual data of the image itself (actual data is stored in tile-data object, that can be shared by several tiles). Tile-class will encapsulate locking and copy-on-write mechanisms.
Tile-data objects are created by special class that is in charge of storing, compressing and swapping data. It's name is KisTileDataStore. Tile-data objects are stored in linked list. New objects always added in the tail of the list so swapper thread can walk from head to tail and swap out old stuff; the old stuff will be accessed first.

Let's imagine the situation when we need to access some tile for read.
  1. We call tile->acquireForRead
  2. It acquires tile->m_tileData->m_RWLock for read
  3. Checks whether tile->m_tileData->m_state==NORMAL
    a) if not calls tileDataStore->getTileDataToMemory
  4. Allows user to read tile->m_tileData->m_data

Access for write:
  1. We call tile::acquireForWrite
  2. It acquires tile->m_tileData->m_RWLock for write
  3. Checks whether m_refCount==1 (we are the only user of tile-data)
    a) m_refCount--
    b) if not, COW. tile->m_tileData = tileDataStore->allocNewTileData()
  4. Checks whether tile->m_tileData->m_state==NORMAL
    a) if not calls tileDataStore->getTileDataToMemory()
  5. Allows user to read tile->m_tileData->m_data

Creating new tile object (KisTile::KisTile):
  1. tile->m_tileData = tileDataStore::getDefaultTileData()
    defaultTileData object is shared by all tiles, so it has m_refCount field higher than 1, so it'll be replaced by a new tile-date on the first write request.


Hi, dear All!
My name is Dmitry. I'm a student, programmer and photographer and am going to share some my thoughts about "programmism", "photographism" and "studentism" here =)