[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-kimageshop
Subject: Re: Deform brush and deadlocks
From: Dmitry Kazakov <dimula73 () gmail ! com>
Date: 2009-06-29 15:13:06
Message-ID: ae32c1ef0906290813w1646ed14k923fd521b032ba2e () mail ! gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
Well, i can't join your conversation fully right now. But there are some my
ideas:
1) We won't prevent two write iterators from writing to different lines with
exclusive access if we make a good recursive(!) read-write lock with
relocking for different type of access ability. It'll create quite a big
overhead, but it'll work.
2) I think we need locking in general. And we shouldn't (or can't) leave it
to the upper level. Example: deform-brush case. I don't know how it happened
exactly (didn't have time yet to investigate properly), but merging and
previewing was started in parallel with brush working. I think it's logical,
that merging should wait until a brush finishes it's work. Or we could allow
it to show half-done work? I think this is main question of our discussion.
We don't have any concurrency between painting tools (at least now), all
races happen while previewing. If we allowed layer-updater thread to show
user half-done work, the system would be much simplier.
In such a case we'd need write-locks only.
3) At the moment, i think the best variant is (if we decide to do locking at
all):
- Leave exclusive locks.
- Introduce a rule, that one thread won't have more than one read and one
write iterator simultaneously.
- Rewrite iterators (i planned it already, but i planned to do it after
mipmapping) is such a way, that it releases ALL cached tiles when goes to
sleep. In such a case we lower deadlock probability, but we don't solve the
problem itself, because a thread still can have locked tiles on entering the
sleep. It can be solved by joining together read and write iterators (or
their caches, or even more - per thread storage of locked tiles cache), but
there are some issues, e.g. we can't unlock a tile that we were writing to
if we can't get an access to some other tile for read. If we do - it'll be
an equivalent to no locking at all.
4) Locking with QRect.
If a tool would lock entire rect it needs before starting work - it would be
great! It would solve deadlock problem completely - as "Circular
wait<http://en.wikipedia.org/wiki/Circular_wait>condition" would be
removed. But in such a case we should rewrite entire
Krita codebase, shouldn't we?
PS:
Btw, locking rects would improve caching too. It could be based on rect
iterators... Just add random and line accessing abilities to
KisRectIterator... I like this idea... But it's too expensive...
[1] http://en.wikipedia.org/wiki/Circular_wait
On Mon, Jun 29, 2009 at 6:16 PM, C. Boemann <cbr@boemann.dk> wrote:
> [15:55] <boemann> boud: you know, if we make write access exclusive we
> also prevent two write iterators on say different lines from working
> [15:56] <boemann> as access is per tile and not per pixel
> [15:56] <-- fyanardi has left this server (Read error: 54 (Connection reset
> by
> peer)).
> [15:56] <boemann> that might break some algorithms
> [15:56] <boud> yes, indeed
> [15:57] <boemann> on the other hand two tiles accessing the same tiles
> shouldn't be allowed from a more top down perspective
> [15:57] <boud> better put that in a mail so dmitry sees it too
> [15:57] <boemann> i've told him before
> [15:57] --> fyanardi has joined this channel (n=edi@116.197.231.178).
> [15:58] <boud> not sure what you mwith two tiles accessing the same tiles
> [15:58] <boemann> two iterators
> [15:58] <-- slangkamp has left this server ("Konversation terminated!").
> [15:58] <boemann> now threads
> [15:58] <boemann> sorry
> [15:58] <boemann> on the other hand two threads accessing the same tiles
> shouldn't be allowed from a more top down perspective
> [15:59] <boud> yes
> [15:59] <boud> so two iterators in the same thread shouldn't be a problem
> [15:59] <boemann> i think that must be up to the algorithm writer
> [16:00] <boemann> but the example of drying filer together with user
> painting is a problem because there it isn't easy to tell the user not to
> draw
> [16:01] <boemann> on the other hand we don't want the drying filter to lock
> everything
> [16:01] <-- burmas has left this channel ("Konversation terminated!").
> [16:02] <boemann> so for cases where multiple operations are taking place
> at the same time we do need some kind of locking
> [16:02] <boemann> but we don't need it for cases where a single task is
> divided between threads
> [16:03] <boemann> and right now the only multiple operation usecase i can
> come up with is drying+user painting
> [16:04] <boud> yes... recomposition only needs read access and can wait
> until the user is done painting on a tile.
> [16:04] <boemann> yes
> [16:05] <boemann> i think that maybe if we in the future needs multiple
> operation locking we should then come up with another api
> [16:05] <boemann> something on top of the timemanager
> [16:05] <boemann> tile
> [16:06] <boemann> like a way to say: hey i'm locking this qrect for a while
> [16:06] <boud> yes
> [16:06] <boud> although that is more or less what you get when you lock a
> tile :-)
> [16:07] <boemann> true but we have just established that we can't in
> general lock tiles
> [16:07] <boemann> besides locking tiles adds overhead for no good reason
> in general
> [16:08] <boemann> only trouble with a new api is that current tools don't
> know about it and would probably need to be modified
> [16:08] <boemann> for that reason doing it in the tilemanager would be nice
> [16:09] <boud> besides, we don't want to bother filter or paintop writers
> with
> explicit locking or unlocking
> [16:09] <boemann> right
> [16:09] <boemann> idea:
> [16:10] <boemann> what if we provide a method:
> paintdev::setLockOtherUsers(bool)
> [16:11] <boemann> that would signal the taskmanager that tile access by
> this thread is exclusive
> [16:11] <boemann> other users of the paintdev would be locked out of the
> tile whenever the exclluve tile has a lock on it
> [16:11] <boemann> but in general tiles are not locked
> [16:12] <boemann> this exclusiveness can then be used by drying filter like
> stuff
> [16:12] <boud> I'm not sure I like that idea
> [16:12] <boemann> why
> [16:13] <boud> well, I might not get it, but I think it's too explicit
> [16:13] --> DetroitLibertyPe has joined this channel
> (n=Parrot_T@209-255-22-2.ip.mcleodusa.net).
> [16:13] <boud> and we would have to mutex around the getter for that paint
> device
> [16:13] <-- DetroitLibertyPe has left this channel.
> [16:13] <boud> I'm not sure I've got the real requirements clear, though
> [16:13] <boemann> we would have to do that with any locking mechanism
>
>
> _______________________________________________
> kimageshop mailing list
> kimageshop@kde.org
> https://mail.kde.org/mailman/listinfo/kimageshop
>
--
Dmitry Kazakov
[Attachment #5 (text/html)]
Well, i can't join your conversation fully right now. But there are some my \
ideas:<br><br>1) We won't prevent two write iterators from writing to different \
lines with exclusive access if we make a good recursive(!) read-write lock with \
relocking for different type of access ability. It'll create quite a big \
overhead, but it'll work.<br> <br>2) I think we need locking in general. And we \
shouldn't (or can't) leave it to the upper level. Example: deform-brush case. \
I don't know how it happened exactly (didn't have time yet to investigate \
properly), but merging and previewing was started in parallel with brush working. I \
think it's logical, that merging should wait until a brush finishes it's \
work. Or we could allow it to show half-done work? I think this is main question of \
our discussion. We don't have any concurrency between painting tools (at least \
now), all races happen while previewing. If we allowed layer-updater thread to show \
user half-done work, the system would be much simplier. <br> In such a case we'd \
need write-locks only. <br><br>3) At the moment, i think the best variant is (if we \
decide to do locking at all):<br>- Leave exclusive locks.<br>- Introduce a rule, that \
one thread won't have more than one read and one write iterator \
simultaneously.<br>
- Rewrite iterators (i planned it already, but i planned to do it after mipmapping) \
is such a way, that it releases ALL cached tiles when goes to sleep. In such a case \
we lower deadlock probability, but we don't solve the problem itself, because a \
thread still can have locked tiles on entering the sleep. It can be solved by joining \
together read and write iterators (or their caches, or even more - per thread storage \
of locked tiles cache), but there are some issues, e.g. we can't unlock a tile \
that we were writing to if we can't get an access to some other tile for read. If \
we do - it'll be an equivalent to no locking at all. <br> <br>4) Locking with \
QRect.<br>If a tool would lock entire rect it needs before starting work - it would \
be great! It would solve deadlock problem completely - as "<a \
href="http://en.wikipedia.org/wiki/Circular_wait" title="Circular wait" \
class="mw-redirect">Circular wait</a> condition" would be removed. But in such a \
case we should rewrite entire Krita codebase, shouldn't we?<br> <br>PS:<br>Btw, \
locking rects would improve caching too. It could be based on rect iterators... Just \
add random and line accessing abilities to KisRectIterator... I like this idea... But \
it's too expensive...<br><br>[1] <a \
href="http://en.wikipedia.org/wiki/Circular_wait">http://en.wikipedia.org/wiki/Circular_wait</a><br>
<br><br><div class="gmail_quote">On Mon, Jun 29, 2009 at 6:16 PM, C. Boemann <span \
dir="ltr"><<a href="mailto:cbr@boemann.dk" \
target="_blank">cbr@boemann.dk</a>></span> wrote:<br><blockquote \
class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt \
0pt 0.8ex; padding-left: 1ex;">
[15:55] <boemann> boud: you know, if we make write access exclusive we<br>
also prevent two write iterators on say different lines from working<br>
[15:56] <boemann> as access is per tile and not per pixel<br>
[15:56] <-- fyanardi has left this server (Read error: 54 (Connection reset by<br>
peer)).<br>
[15:56] <boemann> that might break some algorithms<br>
[15:56] <boud> yes, indeed<br>
[15:57] <boemann> on the other hand two tiles accessing the same tiles<br>
shouldn't be allowed from a more top down perspective<br>
[15:57] <boud> better put that in a mail so dmitry sees it too<br>
[15:57] <boemann> i've told him before<br>
[15:57] --> fyanardi has joined this channel (n=<a \
href="mailto:edi@116.197.231.178" target="_blank">edi@116.197.231.178</a>).<br> \
[15:58] <boud> not sure what you mwith two tiles accessing the same tiles<br> \
[15:58] <boemann> two iterators<br> [15:58] <-- slangkamp has left this \
server ("Konversation terminated!").<br> [15:58] <boemann> now \
threads<br> [15:58] <boemann> sorry<br>
[15:58] <boemann> on the other hand two threads accessing the same tiles<br>
shouldn't be allowed from a more top down perspective<br>
[15:59] <boud> yes<br>
[15:59] <boud> so two iterators in the same thread shouldn't be a \
problem<br> [15:59] <boemann> i think that must be up to the algorithm \
writer<br> [16:00] <boemann> but the example of drying filer together with \
user<br> painting is a problem because there it isn't easy to tell the user not \
to draw<br> [16:01] <boemann> on the other hand we don't want the drying \
filter to lock<br> everything<br>
[16:01] <-- burmas has left this channel ("Konversation \
terminated!").<br> [16:02] <boemann> so for cases where multiple \
operations are taking place<br> at the same time we do need some kind of locking<br>
[16:02] <boemann> but we don't need it for cases where a single task is<br>
divided between threads<br>
[16:03] <boemann> and right now the only multiple operation usecase i can<br>
come up with is drying+user painting<br>
[16:04] <boud> yes... recomposition only needs read access and can wait<br>
until the user is done painting on a tile.<br>
[16:04] <boemann> yes<br>
[16:05] <boemann> i think that maybe if we in the future needs multiple<br>
operation locking we should then come up with another api<br>
[16:05] <boemann> something on top of the timemanager<br>
[16:05] <boemann> tile<br>
[16:06] <boemann> like a way to say: hey i'm locking this qrect for a \
while<br> [16:06] <boud> yes<br>
[16:06] <boud> although that is more or less what you get when you lock a<br>
tile :-)<br>
[16:07] <boemann> true but we have just established that we can't in<br>
general lock tiles<br>
[16:07] <boemann> besides locking tiles adds overhead for no good reason<br>
in general<br>
[16:08] <boemann> only trouble with a new api is that current tools \
don't<br> know about it and would probably need to be modified<br>
[16:08] <boemann> for that reason doing it in the tilemanager would be nice<br>
[16:09] <boud> besides, we don't want to bother filter or paintop writers \
with<br> explicit locking or unlocking<br>
[16:09] <boemann> right<br>
[16:09] <boemann> idea:<br>
[16:10] <boemann> what if we provide a method:<br>
paintdev::setLockOtherUsers(bool)<br>
[16:11] <boemann> that would signal the taskmanager that tile access by<br>
this thread is exclusive<br>
[16:11] <boemann> other users of the paintdev would be locked out of the<br>
tile whenever the exclluve tile has a lock on it<br>
[16:11] <boemann> but in general tiles are not locked<br>
[16:12] <boemann> this exclusiveness can then be used by drying filter like<br>
stuff<br>
[16:12] <boud> I'm not sure I like that idea<br>
[16:12] <boemann> why<br>
[16:13] <boud> well, I might not get it, but I think it's too explicit<br>
[16:13] --> DetroitLibertyPe has joined this channel<br>
(n=<a href="mailto:Parrot_T@209-255-22-2.ip.mcleodusa.net" \
target="_blank">Parrot_T@209-255-22-2.ip.mcleodusa.net</a>).<br> [16:13] <boud> \
and we would have to mutex around the getter for that paint<br> device<br>
[16:13] <-- DetroitLibertyPe has left this channel.<br>
[16:13] <boud> I'm not sure I've got the real requirements clear, \
though<br> [16:13] <boemann> we would have to do that with any locking \
mechanism<br> <div><div></div><div><br>
<br>
_______________________________________________<br>
kimageshop mailing list<br>
<a href="mailto:kimageshop@kde.org" target="_blank">kimageshop@kde.org</a><br>
<a href="https://mail.kde.org/mailman/listinfo/kimageshop" \
target="_blank">https://mail.kde.org/mailman/listinfo/kimageshop</a><br> \
</div></div></blockquote></div><br><br clear="all"><br>-- <br>Dmitry Kazakov<br>
_______________________________________________
kimageshop mailing list
kimageshop@kde.org
https://mail.kde.org/mailman/listinfo/kimageshop
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic