WIP: "More fair" LWLocks
Hi!
This subject was already raised multiple times [1], [2], [3]. In
short, our LWLock implementation has pathological behavior when shared
lockers constitute a continuous flood. In this case exclusive lock
waiters are not guaranteed to eventually get the lock. When shared
lock is held, other shared lockers goes without any queue. This is
why despite individual shared lock durations are small, when flood of
shared lockers is high enough then there might be no gap to process
exclusive lockers. Such behavior is periodically reported on
different LWLocks. And that leads to an idea of making our LWLocks
"more fair", which would make infinite starvation of exclusive lock
waiters impossible.
This idea was a subject of critics. And I can summarize arguments of
this critics as following:
1) LWLocks are designed to be unfair. Their unfairness is downside of
high performance in majority of scenarios.
2) Attempt to make LWLocks "more fair" would lead to unacceptable
general performance regression.
3) If exclusive locks waiters are faced with infinite starvation, then
that's not a problem of tLWLocks implementation, but that's a problem
of particular use case. So, we need to fix LWLocks use cases, not
LWLocks themselves.
I see some truth in these arguments. But I can't agree that we
shouldn't try to fix LWLocks unfairness. And I see following
arguments for that:
1) It doesn't look like we can ever fix all the LWLocks use cases in
the way, which would make infinite starvation impossible. Usage of
NUMA systems is rising, and more LWLocks use cases are becoming
pathological. For instance, there been much efforts placed to reduce
ProcArrayLock contention, but on multicore machine with heavy readonly
workload it might be still impossible to login or commit transaction.
Or another recent example: buffer mapping lock becomes reason of
eviction blocking [3].
2) The situation of infinite exclusive locker starvation is much worse
than just bad overall DBMS performance. We are doing our best on
removing high contention points in PostgreSQL. It's very good, but
it's an infinite race, assuming that new hardware platforms are
arriving. But situation when you can't connect to the database when
the system have free resources is much worse than situation when
PostgreSQL doesn't scale well enough on your brand new hardware.
3) It's not necessary to make LWLocks completely fair in order to
exclude infinite starvation of exclusive lockers. So, it's not
necessary to put all the shared lockers into the queue. In the
majority of cases, shared lockers might still go through directly, but
on some event we might decide that it's too much and they should to
the queue.
So, taking into account all of above I made some experiments with
patches making LWLocks "more fair". I'd like to share some
intermediate results. I've written two patches for comparison.
1) lwlock-far-1.patch
Shared locker goes to the queue if there is already somebody in the
queue, otherwise obtains lock immediately.
2) lwlock-far-2.patch
New flag LW_FLAG_FAIR is introduced. This flag is set when first
shared locker in the row releases the lock. When LW_FLAG_FAIR is set
and there is already somebody in the queue, then shared locker goes to
the queue. Basically it means that first shared locker "holds the
door" for other shared lockers to go without queue.
I run pgbench (read-write and read-only benchmarks) on Amazon
c5d.18xlarge virtual machine, which has 72 VCPU (approximately same
power as 36 physical cores). The results are attached
(lwlock-fair-ro.png and lwlock-fair-rw.png).
We can see that for read-only scenario there is no difference between
master and both of patches. That's expected, because in this scenario
no exclusive lock is obtained, so all shared lockers anyway go without
queue.
For read-write scenario we can see regression in both of patches. 1st
version of patch gives dramatic regression in 2.5-3 times. 2nd
version of patch behaves better, regression is about 15%, but it's
still unacceptable. However, I think idea, that some event triggers
path of shared lockers to the queue, is promising. We should just
select this triggering event better.
I'm going to continue my experiments trying to make "more fair"
LWLocks (almost) without performance regression. Any feedback is
welcome.
Links:
1. /messages/by-id/0A3221C70F24FB45833433255569204D1F578E83@G01JPEXMBYT05
2. /messages/by-id/CAPpHfdsytkTFMy3N-zfSo+kAuUx=u-7JG6q2bYB6Fpuw2cD5DQ@mail.gmail.com
3. /messages/by-id/CAPpHfdt_HFxNKFbSUaDg5QHxzKcvPBB5OhRengRpVDp6ubdrFg@mail.gmail.com
------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Attachments:
lwlock-fair-1.patchapplication/octet-stream; name=lwlock-fair-1.patchDownload
diff --git a/src/backend/storage/lmgr/lwlock.c b/src/backend/storage/lmgr/lwlock.c
index a6fda81feb6..9b99e5e3ce6 100644
--- a/src/backend/storage/lmgr/lwlock.c
+++ b/src/backend/storage/lmgr/lwlock.c
@@ -736,7 +736,7 @@ GetLWLockIdentifier(uint32 classId, uint16 eventId)
* Returns true if the lock isn't free and we need to wait.
*/
static bool
-LWLockAttemptLock(LWLock *lock, LWLockMode mode)
+LWLockAttemptLock(LWLock *lock, LWLockMode mode, bool wakeup)
{
uint32 old_state;
@@ -764,7 +764,10 @@ LWLockAttemptLock(LWLock *lock, LWLockMode mode)
}
else
{
- lock_free = (old_state & LW_VAL_EXCLUSIVE) == 0;
+ if (wakeup)
+ lock_free = (old_state & LW_VAL_EXCLUSIVE) == 0;
+ else
+ lock_free = (old_state & (LW_VAL_EXCLUSIVE | LW_FLAG_HAS_WAITERS)) == 0;
if (lock_free)
desired_state += LW_VAL_SHARED;
}
@@ -978,9 +981,11 @@ LWLockWakeup(LWLock *lock)
*
* NB: Mode can be LW_WAIT_UNTIL_FREE here!
*/
-static void
+static bool
LWLockQueueSelf(LWLock *lock, LWLockMode mode)
{
+ bool first;
+
/*
* If we don't have a PGPROC structure, there's no way to wait. This
* should never occur, since MyProc should only be null during shared
@@ -1002,9 +1007,15 @@ LWLockQueueSelf(LWLock *lock, LWLockMode mode)
/* LW_WAIT_UNTIL_FREE waiters are always at the front of the queue */
if (mode == LW_WAIT_UNTIL_FREE)
+ {
+ first = true;
proclist_push_head(&lock->waiters, MyProc->pgprocno, lwWaitLink);
+ }
else
+ {
+ first = proclist_is_empty(&lock->waiters);
proclist_push_tail(&lock->waiters, MyProc->pgprocno, lwWaitLink);
+ }
/* Can release the mutex now */
LWLockWaitListUnlock(lock);
@@ -1013,6 +1024,7 @@ LWLockQueueSelf(LWLock *lock, LWLockMode mode)
pg_atomic_fetch_add_u32(&lock->nwaiters, 1);
#endif
+ return first;
}
/*
@@ -1177,13 +1189,13 @@ LWLockAcquire(LWLock *lock, LWLockMode mode)
*/
for (;;)
{
- bool mustwait;
+ bool mustwait, first;
/*
* Try to grab the lock the first time, we're not in the waitqueue
* yet/anymore.
*/
- mustwait = LWLockAttemptLock(lock, mode);
+ mustwait = LWLockAttemptLock(lock, mode, !result);
if (!mustwait)
{
@@ -1203,10 +1215,10 @@ LWLockAcquire(LWLock *lock, LWLockMode mode)
*/
/* add to the queue */
- LWLockQueueSelf(lock, mode);
+ first = LWLockQueueSelf(lock, mode);
/* we're now guaranteed to be woken up if necessary */
- mustwait = LWLockAttemptLock(lock, mode);
+ mustwait = LWLockAttemptLock(lock, mode, (!result) || first);
/* ok, grabbed the lock the second time round, need to undo queueing */
if (!mustwait)
@@ -1310,7 +1322,7 @@ LWLockConditionalAcquire(LWLock *lock, LWLockMode mode)
HOLD_INTERRUPTS();
/* Check for the lock */
- mustwait = LWLockAttemptLock(lock, mode);
+ mustwait = LWLockAttemptLock(lock, mode, false);
if (mustwait)
{
@@ -1375,13 +1387,13 @@ LWLockAcquireOrWait(LWLock *lock, LWLockMode mode)
* NB: We're using nearly the same twice-in-a-row lock acquisition
* protocol as LWLockAcquire(). Check its comments for details.
*/
- mustwait = LWLockAttemptLock(lock, mode);
+ mustwait = LWLockAttemptLock(lock, mode, true);
if (mustwait)
{
LWLockQueueSelf(lock, LW_WAIT_UNTIL_FREE);
- mustwait = LWLockAttemptLock(lock, mode);
+ mustwait = LWLockAttemptLock(lock, mode, true);
if (mustwait)
{
lwlock-fair-2.patchapplication/octet-stream; name=lwlock-fair-2.patchDownload
diff --git a/src/backend/storage/lmgr/lwlock.c b/src/backend/storage/lmgr/lwlock.c
index a6fda81feb6..b03287cac4d 100644
--- a/src/backend/storage/lmgr/lwlock.c
+++ b/src/backend/storage/lmgr/lwlock.c
@@ -99,6 +99,7 @@ extern slock_t *ShmemLock;
#define LW_FLAG_HAS_WAITERS ((uint32) 1 << 30)
#define LW_FLAG_RELEASE_OK ((uint32) 1 << 29)
#define LW_FLAG_LOCKED ((uint32) 1 << 28)
+#define LW_FLAG_FAIR ((uint32) 1 << 27)
#define LW_VAL_EXCLUSIVE ((uint32) 1 << 24)
#define LW_VAL_SHARED 1
@@ -137,6 +138,7 @@ typedef struct LWLockHandle
{
LWLock *lock;
LWLockMode mode;
+ bool firstShared;
} LWLockHandle;
static int num_held_lwlocks = 0;
@@ -736,7 +738,7 @@ GetLWLockIdentifier(uint32 classId, uint16 eventId)
* Returns true if the lock isn't free and we need to wait.
*/
static bool
-LWLockAttemptLock(LWLock *lock, LWLockMode mode)
+LWLockAttemptLock(LWLock *lock, LWLockMode mode, bool wakeup, bool *firstShared)
{
uint32 old_state;
@@ -760,13 +762,24 @@ LWLockAttemptLock(LWLock *lock, LWLockMode mode)
{
lock_free = (old_state & LW_LOCK_MASK) == 0;
if (lock_free)
+ {
desired_state += LW_VAL_EXCLUSIVE;
+ desired_state &= ~LW_FLAG_FAIR;
+ }
}
else
{
- lock_free = (old_state & LW_VAL_EXCLUSIVE) == 0;
+ if (wakeup)
+ lock_free = (old_state & LW_VAL_EXCLUSIVE) == 0;
+ else
+ lock_free = ((old_state & LW_VAL_EXCLUSIVE) == 0) &&
+ ((old_state & (LW_FLAG_HAS_WAITERS | LW_FLAG_FAIR)) !=
+ (LW_FLAG_HAS_WAITERS | LW_FLAG_FAIR));
if (lock_free)
+ {
desired_state += LW_VAL_SHARED;
+ desired_state &= ~LW_FLAG_FAIR;
+ }
}
/*
@@ -789,6 +802,14 @@ LWLockAttemptLock(LWLock *lock, LWLockMode mode)
if (mode == LW_EXCLUSIVE)
lock->owner = MyProc;
#endif
+ if (mode == LW_SHARED)
+ {
+ if ((old_state & LW_SHARED_MASK) == 0)
+ *firstShared = true;
+ else
+ *firstShared = false;
+ }
+
return false;
}
else
@@ -978,9 +999,11 @@ LWLockWakeup(LWLock *lock)
*
* NB: Mode can be LW_WAIT_UNTIL_FREE here!
*/
-static void
+static bool
LWLockQueueSelf(LWLock *lock, LWLockMode mode)
{
+ bool first;
+
/*
* If we don't have a PGPROC structure, there's no way to wait. This
* should never occur, since MyProc should only be null during shared
@@ -1002,9 +1025,15 @@ LWLockQueueSelf(LWLock *lock, LWLockMode mode)
/* LW_WAIT_UNTIL_FREE waiters are always at the front of the queue */
if (mode == LW_WAIT_UNTIL_FREE)
+ {
+ first = true;
proclist_push_head(&lock->waiters, MyProc->pgprocno, lwWaitLink);
+ }
else
+ {
+ first = proclist_is_empty(&lock->waiters);
proclist_push_tail(&lock->waiters, MyProc->pgprocno, lwWaitLink);
+ }
/* Can release the mutex now */
LWLockWaitListUnlock(lock);
@@ -1013,6 +1042,7 @@ LWLockQueueSelf(LWLock *lock, LWLockMode mode)
pg_atomic_fetch_add_u32(&lock->nwaiters, 1);
#endif
+ return first;
}
/*
@@ -1122,6 +1152,7 @@ LWLockAcquire(LWLock *lock, LWLockMode mode)
{
PGPROC *proc = MyProc;
bool result = true;
+ bool firstShared = false;
int extraWaits = 0;
#ifdef LWLOCK_STATS
lwlock_stats *lwstats;
@@ -1177,13 +1208,13 @@ LWLockAcquire(LWLock *lock, LWLockMode mode)
*/
for (;;)
{
- bool mustwait;
+ bool mustwait, first;
/*
* Try to grab the lock the first time, we're not in the waitqueue
* yet/anymore.
*/
- mustwait = LWLockAttemptLock(lock, mode);
+ mustwait = LWLockAttemptLock(lock, mode, !result, &firstShared);
if (!mustwait)
{
@@ -1203,10 +1234,10 @@ LWLockAcquire(LWLock *lock, LWLockMode mode)
*/
/* add to the queue */
- LWLockQueueSelf(lock, mode);
+ first = LWLockQueueSelf(lock, mode);
/* we're now guaranteed to be woken up if necessary */
- mustwait = LWLockAttemptLock(lock, mode);
+ mustwait = LWLockAttemptLock(lock, mode, (!result) || first, &firstShared);
/* ok, grabbed the lock the second time round, need to undo queueing */
if (!mustwait)
@@ -1271,6 +1302,7 @@ LWLockAcquire(LWLock *lock, LWLockMode mode)
/* Add lock to list of locks held by this backend */
held_lwlocks[num_held_lwlocks].lock = lock;
+ held_lwlocks[num_held_lwlocks].firstShared = firstShared;
held_lwlocks[num_held_lwlocks++].mode = mode;
/*
@@ -1292,7 +1324,7 @@ LWLockAcquire(LWLock *lock, LWLockMode mode)
bool
LWLockConditionalAcquire(LWLock *lock, LWLockMode mode)
{
- bool mustwait;
+ bool mustwait, firstShared = false;
AssertArg(mode == LW_SHARED || mode == LW_EXCLUSIVE);
@@ -1310,7 +1342,7 @@ LWLockConditionalAcquire(LWLock *lock, LWLockMode mode)
HOLD_INTERRUPTS();
/* Check for the lock */
- mustwait = LWLockAttemptLock(lock, mode);
+ mustwait = LWLockAttemptLock(lock, mode, false, &firstShared);
if (mustwait)
{
@@ -1324,6 +1356,7 @@ LWLockConditionalAcquire(LWLock *lock, LWLockMode mode)
{
/* Add lock to list of locks held by this backend */
held_lwlocks[num_held_lwlocks].lock = lock;
+ held_lwlocks[num_held_lwlocks].firstShared = firstShared;
held_lwlocks[num_held_lwlocks++].mode = mode;
TRACE_POSTGRESQL_LWLOCK_CONDACQUIRE(T_NAME(lock), mode);
}
@@ -1348,7 +1381,8 @@ bool
LWLockAcquireOrWait(LWLock *lock, LWLockMode mode)
{
PGPROC *proc = MyProc;
- bool mustwait;
+ bool mustwait,
+ firstShared;
int extraWaits = 0;
#ifdef LWLOCK_STATS
lwlock_stats *lwstats;
@@ -1375,13 +1409,13 @@ LWLockAcquireOrWait(LWLock *lock, LWLockMode mode)
* NB: We're using nearly the same twice-in-a-row lock acquisition
* protocol as LWLockAcquire(). Check its comments for details.
*/
- mustwait = LWLockAttemptLock(lock, mode);
+ mustwait = LWLockAttemptLock(lock, mode, true, &firstShared);
if (mustwait)
{
LWLockQueueSelf(lock, LW_WAIT_UNTIL_FREE);
- mustwait = LWLockAttemptLock(lock, mode);
+ mustwait = LWLockAttemptLock(lock, mode, true, &firstShared);
if (mustwait)
{
@@ -1452,6 +1486,7 @@ LWLockAcquireOrWait(LWLock *lock, LWLockMode mode)
LOG_LWDEBUG("LWLockAcquireOrWait", lock, "succeeded");
/* Add lock to list of locks held by this backend */
held_lwlocks[num_held_lwlocks].lock = lock;
+ held_lwlocks[num_held_lwlocks].firstShared = firstShared;
held_lwlocks[num_held_lwlocks++].mode = mode;
TRACE_POSTGRESQL_LWLOCK_ACQUIRE_OR_WAIT(T_NAME(lock), mode);
}
@@ -1725,8 +1760,10 @@ void
LWLockRelease(LWLock *lock)
{
LWLockMode mode;
- uint32 oldstate;
- bool check_waiters;
+ uint32 oldstate,
+ sub;
+ bool check_waiters,
+ firstShared;
int i;
/*
@@ -1735,7 +1772,10 @@ LWLockRelease(LWLock *lock)
*/
for (i = num_held_lwlocks; --i >= 0;)
if (lock == held_lwlocks[i].lock)
+ {
+ firstShared = held_lwlocks[i].firstShared;
break;
+ }
if (i < 0)
elog(ERROR, "lock %s is not held", T_NAME(lock));
@@ -1753,14 +1793,23 @@ LWLockRelease(LWLock *lock)
* others, even if we still have to wakeup other waiters.
*/
if (mode == LW_EXCLUSIVE)
- oldstate = pg_atomic_sub_fetch_u32(&lock->state, LW_VAL_EXCLUSIVE);
+ sub = LW_VAL_EXCLUSIVE;
else
- oldstate = pg_atomic_sub_fetch_u32(&lock->state, LW_VAL_SHARED);
+ sub = LW_VAL_SHARED;
+
+ if (firstShared)
+ sub -= LW_FLAG_FAIR;
+
+ oldstate = pg_atomic_fetch_sub_u32(&lock->state, sub);
+
+ /* If we were first shared locker, LW_FLAG_FAIR shouldn't be set */
+ Assert(!(oldstate & LW_FLAG_FAIR) || !firstShared);
+
+ oldstate -= sub;
/* nobody else can have that kind of lock */
Assert(!(oldstate & LW_VAL_EXCLUSIVE));
-
/*
* We're still waiting for backends to get scheduled, don't wake them up
* again.
lwlock-fair-ro.pngimage/png; name=lwlock-fair-ro.pngDownload
�PNG
IHDR � � �KR[ sBIT|d� pHYs ��~� IDATx���wX����Q�G�x�`GQQ� R�����R��1��5j����h�M4����+���"�J�&�8�;>�?��?��&�����p;�3��{���fwyDD`�a�a�V���0�0�w�h�a�a��@3�0�0L� �a�a�a����0�0S,�f�a�a�:`4�4��'b���
ZgHH����u��xyya��}��ILLDHHH�4�/^���{��H/^���yc7�Nx<���{��g��
Z'�4&@3Sg���:t(
!`gg�Q�.�w�������������{CSS�[����)�����&&&�4iJJJj]wdd$���?t�������sg��YYYh������|'ND�&M�����d2�{��u�V888@MM
'N�����?�M�6���h��-~���l=��3� �a�:?~<,,,������l��������������I��~�z���G�F�N�����o����
���� g����5kp��9$&&������va���ptt���k��U+?~�^�����8C���Y�`gg�[�n�kEEE�����GDD�������J��V��TW}[�p!
�����{�cjj��K�b��I�����0n�8|����������1f�dff~h���w�/����XZZb���h��-��� �X���[���5���)v��U�'���,���������III\��'O���}}}�j�
?��3�6q�D��5>>>���ptt��g���G�q�#44�K+--�� �����];��}�����_a���������
:u�//�Z��v�Z�������U�V8w���|��u����amm])�����{�.V�X
:vvv���_ ���������];���a��eu%wss��]��m����?�����p�B�8q��7��---�a�t��� #G��;jR�~{Wpp0TUUq��l�����>�����}�v���BOO�f�B]>;~�x��,����0aB���x<l�����044��PVV���~ggg|������������m�����<==�>�����3���044���c�����kii��k��C�����T*Ezz:�
###XYYa���\���bL�8zzzh��-����j��������+�v�����sinnnX�l�������������*�:v��������-Z���������������={��;d�4��RSS���///�x<���@KK�;�x{{��/����9Ra ������ttt��K\�r�K ��a�0n�8���`���(..���?�����M�[�Nn�Lu��a1���B!�k�����);;����h��%DDI���CEEE4n�8@���DD���O���t��%��4w�\rvv&"���B277�={��D"�;w�������p����QTTI$3f�9����������6l�@������O7o�$"���`RSS��'O�T*��� rtt�������������C���T��z�� ���SZZ�x���]��?� �P(����#��uk�e�f����gQ�����\���� eee�������s�N�i����)S���/(88�R�P(��]�RZZeggS���i��m�����V���i��Ut��
���|||(77��������"##k��/^ z������T*���S��-�������Qvv6%%%���-��aaa���L�7o&�DB"���=J-Z�����D"�����z��Q���������$�)33�z��E�����
���cGJNN&�HD2��:w�L+V����z��YYY������(00�z��I������L���#333�����M���N��"""HWW�;�\]]�������H$���+*,+**�ttt����$��(55�bcc���?�zzz��sg���_��"##�i�����C*,,���G��_��d�����[&�J�����;FR���=JfffTXXHDD/_�$###:w�8p����(??���o�[DD������,�H$�a�266���b"*?�������GI&��H$���@rqq���JII!;;;��k�g�X �0�@(�H'O�$kkk""
��� .->>�R �6�%"*(( %%%JNN���S��=���:u*���p�N�<Y��V�ZQDD���+lopp0����{���#RWW������P`` �m������c��t���Z�OFFF��Piii��Q����W
�/^����r�bii)�Fu�����i�����L������B�������_�`M�6�V�V��*:{�,������#�?�=z$���\���>|8�^��Ve�
�% ����N�>M����j��Z������O}��!��@���B.���i��]�{�LF���Xcy=zT���B!����{���J������������J����� :<<��v�*��{����WWW�������������S��������s�FO�<I���t��U"*?�������w MD�k�.���"eee����'N������dnnNr�V� �"]]]���&���O�^���+�;w�����}�0��M�`�zbaa��-
�������w���[�2mmm���#==III������.�:x� 222��&&&�����(,, ����E�U���zb�X�\���P������ ����f�<z��^����=
�pz�������acc�M�6!$$M�6��Q����mmm����-�����W��������>}:����K��C�������?^�| ���j�T��];��+W����������O�������prr�?��^�x����d�� &`���8t�P���R���b $%%a��y�1���"BZZZ��effb��Q033�����Wi����&%%!==]�3�W�^��y
�Unczzz�t�P(����u��s��000���
���1v�X9r�������������(--��K�0e�DGGsy|}}!����U�j���q�F�i�� ���x����~�xTw��i�1Lc`4���������d��� �5k���T��-+,,DNNLMMaaaWWW���q���Bl�����XXX���~_�/�.\��}{�tCCC|��WHOOGNNN����Hn��c� ����W�")) <���unW�v����sp�����v��q�����K366V8�s���\/^\��utt����A����c��uk��(�����^�z�y������M��m�*����j�����C���������u�V��(���.����r�yqq1���j,o��E��xx�����q���J_������VVVru���S �?��������\���������*�e��x<n����DGG���PRRB��]���(ww�%K��M�6x��%:���+W�`�������������<��R���<Y�>c���h��'��=RSS������P�9 0b����!66"�+W�����S�p��U���b��eptt���|}}���S�������bcckl���/222�i�&������ QQQ����������T*EAA�m���iEqqq8�<JJJ���
�*�(PVV�X�D"�X,Fii) �e�������+ �q��Q<x� C�P>j�{�n<~����X�j���v����].Py��a����.����~��: 111�n(������JE��_���\��������>�L�>�W���G� o������Z�WPP mmm���"--��;����[7���`���(..�L&CLLw���#�z�j���"55[�l��,ooo<}��J��������c�������5y�d������s(++CZZ�<y ���_PXX���2�={������{������DX�bE��H�R��b�d2�d2�_��v��+W�p#������+W��C �������p���c��9r��o@EEFFF�J�X�re�_�*z������������1� �a���1c���kkkX[[sG������s��wo����G� 555�uW�X}}}��sP>�����8|�0LMMabb����Z�������?�����abb[[[\�p�^�U$a���������5��������j������&&&����r��������ooo$''CCC\����q��m���!((������ ��������wo�B�����***����gOl��[�l���`�e�edd����F���y�p����vw�ZO-���K�.������&O�\e���#00�F������o����Z���w�B ���C���]���8~�8���aeeCCCL�2o����
���������_eY8q�6n��[�'N����am����[7������?�@ ���w�}333���b����s'��� ��_����>}����}���+744T�9�V������Y�@CC�V� ���rw����:t(/^���c�� ��u+�����gOL�<�F�===�����-[B(B]]]���w-_�������B�~�0l�0�Y�>c���#E���KKK�������1oll,��o������4@�������)S�T{����D������Fx��E$&&������x�������'Y����m>�K�.5vSF!6�0
����(--Enn.1`� <�D"�?^�a�j/_���k�PVV���8l���n�f1L�X �0
�����Z�hee�Z]�4���L��������� ��<4��3P���Oe��a�Gii)�M�>��>}�`����9sfc7�a���p0�0�0L�h�a�a��@3�0�0L� ������pO;KNN���6d2Y���� ===t���A������������CBB����������
a���5��>l[_�z��||�������t��A��\2���h����ysV�����������?����[�nUJ�p�������<X����u+���V�{�g������b_������ ����c
�����7����,\�����P(�7�|��=}�������������8�����1j�(AGG����3g���/BII�{$������t�-}I;v,��=�������{s�Q��q��1�����Bhiia��ArOy�����������P�����n>@3�BIII����������m����3���Czz:lmm1c��*�355���K1i�����ORc����|�}�����m�r�d��3S������'���'��������#G� ���������8�z�
��u����u���SSS��w����v�Z�h��W�r�LMM�G�_�z�w��o��� ���}|��wx��%����c��7/_� <z���M�������+hjj���d��Yh�� ^�z��b���S<�D��B!�[�����HSS�&M�D�������}�RNN������G��C�p�����srqq!mmm�����5���KDD/^� $�H��h��=��uk���&+++��};W������6l�@FFFdbbB{���r���h�����G-Z��;v��]�HMM����HKK��/_^m_��b
�6m���oK�,!����+����+-]�����H[[��������r}T��?���"##IUU�TTTHKK�:t�@DDyyy4i�$211!SSSZ�d I�R����C����c������;�����,Y�����PH���';;;����#FPqq1�~��|||H �������d2Y�z�/_N�g�&"���R�����H$"555�������������������5��� ��m�����tuui���TVV�p{����K�.����i����������{������U������; 211�Y�fQII ���n�J666diiIDD�����_?�����-[�O?�����������]����K���Ya������;���"������
�>��n�D"!RQQ!UUU�������+��?~�:v�H��z��A������k��!;;;j�� I$Z�f
������6�l��������}���R���i���
���� eee���c�����2}��N�|�M��FNNN4�|deeE��]���0277'###��w/����dooO|>����)88�K;|�0YYY��7o�����SdllL�����!&&�;��6m��],��y��Y�f��Y3�7o��b��������O3g�$ooo����n��QBB�^��-���/��������9;;�H$"@ZZZ���E��_���0�����k���@:::���@��]���;O���cI__�988PFFF�������"555���""�E���������RUU���|*,,$UUU�������G����}�b,�f��P($GGG������T222�N�:���wI,S���)$$����Q������'I&����gI__�;�w���>��s��t��%����2�>q�%$$PYY]�x�444���;DT~WVV�e��Qii)�<y�444��w�����3�������G����?��'bE���H ��#
����@������G"��\]]��ku4Q����h���4u�T*,,�W�^Q��]����+88�TTT����$��H$�*����+���Qvv6�n���m�FDDAAA4m�4*--���R�|���`���s��}{"*��immM��u���~P�W;w��+ ���Pnn.%%%���!EFF*�����Sxx8��7���2e
�D"����&M�����������t��
�H$���j��5��?��kC�~�(;;�D"���9����$ ��s�(&&���F�I�����Bz��!����:�vss���lJJJ"[[[�?�����~����s����7I*����{I(rA�P(��;Rrr2�D"z�� ���SZZW��A��V�^M���WuV�^MZZZ����(%%Ea��G���� �������x�c����djjJ����v�����HYY����CR���,YB4s�L��t�����������L&����S��M����\yc��!����f��������???�LLLh��
T\\L���t��M""Z�l9::��W�(33�z��AK�.��Q���������(**�$ �3�F�IDT��=s�Lruu���T�J�t��5������������&]]]
'�DB����}!��<�}�v������"�J�t��m��HEo��+z���T��>>>���F ���������Gk�������E�o���w�����\����k�r��?6��yos�����1�����W/8::�S�NPSS����q��= �����
ooo())���8u������_�������\\\0`��*����A�-������
\�r�KWUU�������
ooohkkW�� )))�z�*��]uuu���c��)�����y�����CVVV�Z���[���jV��U$ -[����F������j��W��M�6AKKM�6������W�N�=0h� ())ACC�V���;�����������������HJJ���*z���M�Xg||<���q��eL�<iii(,,��K����Z��
���.�7o���{W����HHH@VV�����{w����`hhh�c�����#��� ����w�XZZb��i�Y�h�"���CCC'N����%������;c������_ ������b������B������_�m
���>�7o�������Cu��������M���#������555��y��3w�\XXX@CC���())����!�H`ii�-Z(,;((yyyU�������{����@ ��'55�f����~�-������ �~���������6>��3nyzz:tuu�����-[����Vt�eee��� (++c���HII�������4i�������
vvvPRRB�0z�h��������������������O�8|���PWW� IDAT�����#����/_��M�������r�����C�A�n������c�r�������2����}�������'''������'O����-���=�[������<U�'UUU������(++�K�.�������:O�8Qc���S�����RyHVXXX��(((�6�iX,�f����1����F����� ��F�������.��z�*^�|���t������
�U�����C__���8u�����t�Gdkjjr�xWzz:����������B��������|���^^^�EG����y�}U}PIII�H$h�����M�����*�����s=U�w������������f���khh����.]�������
'''\�v������������S�n�]�v����r�>}
___���@GG�/�;��~LJJBTT��g�����������!�J��W����z����^�:III��q�\�SRR���nl�� !!!h��)F�Uom�����S�N����t����������3gb����rn�* ��=yyy�?>$ ����yyy���G^^444������\����QTTw1�@ ������#]]]>111���/k�;%%��/-���r�U�c��soU�������,���*�T���}��w��U�i��������Q�`jj���������
///�9s���; @[[���r��������Mc�����������f^TT��� 4k����(**��'''+,���C��W_}�W�^!//�����x����)rrr���'''���������233+��j#22���h����UmiiiA$q�e2^�~���8�kaa555deeq�.??��V*�Q�����Z����c���x��9�?�o�����S���������{���kW������3�u�\\\j��������C�������@6L�X���3��uk���#??������w�faaWWW��Paa!�m�###��� %%��_�gH������������K�,�k�H$�J+���1cp��U$%%���!00Pa������NE���J�x���>77�����%K������������#7�Y���???������7�>}��q�={�`����;wn��YXX����LMM������X������PWWW���>������9����"88�?����q�� ���+��� H����W�u������];��* x��9JJJ��eK�l�R����\������]�Z���@3��q�p��q�9s2�b�/^Djj*�B!���R\�z��6���())�������e�������h�"��b<x� �w��u {���������_��_|�N�:A___a~�T
�X�L��Ac�]�e����8y�$$ V�Z���.������(++ 4k����/������2<{���t��������S���AFF6m�T�uO�8���ttt���\���\]]��m��I�&�-����`dd�pccc<��������x��5������ ���`AAttt����'O�`��m��������O��~H$H$���_������2�����D"<~������6�_����HII�w�}��#G(�o�/_Frr2��y���W��L �����}�vDEE��PTT��'OV�Ss\\��?������s�:Y�x1��S�K���2����������[������o_ ��x���pvvV�KGHH�\��/�������Blll�}PXX����7nnn �r��(((���>���q��-�����b�7���CZZ~���j�����>�%%%(((@TT `���X�j^�~���,�\��^nyY������I�&��/�@zz:d2n����PRR��������O�"""R�?��?~\�4��6�>�L&���TUU�<� �����T���'O���bH$8p���(�����q��a���2d�|>���0d�,_�EEE�v��;����������h�������c�
###XXX`���\����(���c���0a��r�|>6o��#F@OO���{�v:t���055�����b�
����j���4���|>���x���*��Z�
X�f
8
�Z������~��L�2fff������9�>|�p �?�v�� ���R�m�zzz6l��O�5?~<:v�KKKxxxpZm����_�~���F�=0s�L���)�������bn��m��PWW�r� ����_~�zzz�������h�����1o�<>|���5��a�DDD������>��O�|>��=������&&&���l�����011���P�m8p �t�{{{���`��� www�9:t@�.]jx����;w��������������%%%
���!LLL�������:�Y��G��E����7n����9s�pi������F����l�7o�Djj*:v�>�ggg���������HOO��
����������gg�z��~���/�����+1b�.m��E077��3����`���r#���|���8~�8LLL`kk�. �.]
t��vvv���3�.]���P���a�����k�����G`` �������%K�������rs���s��'�q�F`��u8q�
klSFF�
�i�����z|"��*�����O?���s��k����c���h��)
������(..F��M1z�hl����@7�����0��Ijj*��7n4vS��@,�f�a�a�:`S8�a���\����1�,��`���F��a�a��4�0�0����a�a�X �0�0�0u�h�a�a��@3�0�0L� �a�a�a����0�0S,�f�a�a�:`4�0�0����a�a�X �0�0�0u���
�T�����������WTT--��n�?������a�~n������������z+��U066������x/^���[c7���s�`��0X?7��
��s�ppp�����a�a��@3�0�0L� �a�a�a������D���T����n�?�@ @lll������������U�0�0Uct���������<�����PPP >�_c>"Bvv6RSSaee� -c�a�Q�M���X<7�6��0�0L�c#�uT]�|$�5�'�����l0d�Q}5�_�}qa�a�S�F����Cm�k�'�Q���hQ������?4v3�a�a�6X ]�TTx�����|���CE��M}� ��PVV��Z�0��w�2_WZN��!�~w#��a�il
�{h���A�/�O�v��3�QeZbb"�����={�������#���L<x 0�|CCCaaah��=z��� ���������+�-[�g��������X�~=��_���%%%<x0V�X���Dxyy�w���q�~��7�����;�~��9A�n�����5-��E��Q�g0�q @e���l&�0���������7<��'O��W�b��
E���q��e��w+W����� ��o��y����o���k��A�-�������������[��;w����� ���8L�0���c�3���<����@�� ����W������p�z^�VP����d�a>6�7dee;;; @�v���o_�x<���!11o�����?������ �H =z��7�|���T2�����>{�,��=�N�:
����C(�{��
��� �55B�sG����� ��� <@GLx�� �;_}�:0�0���@�
���q+))q���� �J�l�2���1118~�8w��1c�������<==q���Je-Z���hDGG#!!�'������ [�0����b ����@ r4��~�����0�G�F��Cus���J m���P�
m�q6��A.|��
��� {����?�����;w.�?��c��(((��xzzb��e;v,����������0���W���l�\���R8=/~Y��'�d�/�y����#�0�? ��H*���!���p�B,Z������d���~� ������=�<y� &��� ���h��=,X �3=z�����
&`3��]Y\J�GBm��J��"JC�bJ:�F�u��_��k i��2�0�&Qc7�S��U+����-���E�6mj]�TJ��5 0~��'s��OIm��V]�S����pssk�f��Qa!�_������+x�k-r���*������}��<�Jn��)R��������a�~n�}�v����p|D**<�o���`�d��B� H���`����G���8��k�������Y�������C�����<�<v�!�0�'���0U({��9A(������MU0{�>��jp�n[���bS�+�����~(���b�yR����b�?���g QR��s7(�yAy`(�X�-c�a>��a*��7�����=�;������EC�p��&����,�2v���M�;)#����2������c��/��i�ee(�reWnB� ��m����������]��0� `4�0��PYd�C�x�])�T��W<��5��Id�!��OP��^�����/�=�m�q��6�&��i����^�2����<������A:���XHcb!
�x��P� �A�Pru�I����0L�X �0��v4J����*L?�V�C���� K:M�X�!<���������}�t�����{�P.���# }�Vh��3�vQ���3$���u�[j����z�K����>E��Z���(5�ma�m:P�q��_(���N�/�e�a>�?��y~�D�0�4��>�W4v��yeeC��Hw O�M�^� h�.u��<����a,�c�gr��G��EZ�_w�����R\9�W� �. W����o�"��"��!6�c�O1�gK��i�g%P�b���C�+d�B�� �����@o(� �����0S5@D�o����;{ ��r��_Y��.���������������z��.777l����=z4=z��� |���
�l������0aB��.Y�������}�v3L]�L���P��k��)D�Od�*=t���;���N��T
S�>��~|������:p��0P �v�P��#=a[�$������D�+�Viw--EY�9�E��d:���P~G��^Pjm��me�a�5��T���`oo��ttt�i�&���������pwwGnn.�� t������A�p������o�>�������������svvv������s���U���|sg7Bnm��@,+E��������ZC�����������*�g �>}���Y��!��[�������Zr;��dv T�T����e���2 �Cp�����<P<����m�� BwZc�ltv�CC�v�Y�Lx`��^P��+�-^�� 8��'X�r�9FL3Bx-diW_&��
���Q�� ���! Z����AeU
g3�0u�`#��Z�Btt4 @&�������5k��o_a��5X�f
��]���H���#>>QQQ�1c�������+V������x����������3f`�����;���q��ixyyUY��R�����������[��L����F�3g�D���������COO{����������Z���KDX�p!"##����t�R�9 �n�:���JJJ\_�UVV��� XXX�� ������=�l��'O�`��(--���
���MMM���@[[_}��������k�����_~��\���w�U�1������|t~>
�O�U�p���
���Sa#����YX� ����&���0s�9�6S��)� ��C&qyd2������S�Gw���W����/ �7h�������T���m�\�X���$1|����-��~x��3H�m)55��@�����OM�v�0��i�)���C�-
q��1\�x ���777�]����� �����{w��������x�"������ pww����������|��� 0a����o�������3\�r~~~HKK���/ W�^��Q���9r�����>�����kW��� ::������������n�T��c��}��X�dI����w���r_���m��>� �t�R���s����^^^.]�To��0�A ^���&�[�#�6�a�� I��X�<m��AF�z��W?���@=,�d sKuH����2$$$�o��CP��y�i� �6�4�<�.+#$?��w����8���-��h �S��i!�uB��by�GhY�
��S=�$�*, T2�!�����!�R�����A��x����a��j� ����=z4 ���Wh���i}��5Cff&