From: Corinna Vinschen <corinna-cygwin@cygwin.com>
To: cygwin@cygwin.com
Subject: Re: mixed usage of lock protection and lock-free List template class in thread.h
Date: Fri, 01 Dec 2017 17:15:00 -0000 [thread overview]
Message-ID: <20171201171536.GA4325@calimero.vinschen.de> (raw)
In-Reply-To: <1543396632.5417641.1512146709346@mail.yahoo.com>
[-- Attachment #1: Type: text/plain, Size: 3312 bytes --]
On Dec 1 16:45, Xiaofeng Liu via cygwin wrote:
> Lock protection and lock-free should never be mixed !
> https://cygwin.com/git/gitweb.cgi?p=newlib-cygwin.git;a=blob;f=winsup/cygwin/thread.h;hb=1f42dc2bcf58d3b8629eb13d53de3f69fc314b47#l110
>
> 110 template <class list_node> inline void 111 List_insert (list_node *&head, list_node *node) 112 { 113 if (!node) 114 return; 115 do 116 node->next = head; 117 while (InterlockedCompareExchangePointer ((PVOID volatile *) &head, 118 node, node->next) != node->next); 119 } 120 121 template <class list_node> inline void 122 List_remove (fast_mutex &mx, list_node *&head, list_node *node) 123 { 124 if (!node) 125 return; 126 mx.lock (); 127 if (head) 128 { 129 if (InterlockedCompareExchangePointer ((PVOID volatile *) &head, 130 node->next, node) != node) 131 { 132 list_node *cur = head; 133 134 while (cur->next && node != cur->next) 135 cur = cur->next; 136 if (node == cur->next) 137 cur->next = cur->next->next; 138 } 139 } 140 mx.unlock (); 141 }
> The symptom I met is a job hang with the following stack:
> #0 0x000000007711c2ea in ntdll!ZwWaitForMultipleObjects () from /cygdrive/c/Windows/SYSTEM32/ntdll.dll
> #1 0x000007fefd111430 in KERNELBASE!GetCurrentProcess () from /cygdrive/c/Windows/system32/KERNELBASE.dll
> #2 0x0000000076fc06c0 in WaitForMultipleObjects () from /cygdrive/c/Windows/system32/kernel32.dll
> #3 0x00000001800458ac in cygwait(void*, _LARGE_INTEGER*, unsigned int) () from /usr/bin/cygwin1.dll
> #4 0x000000018013d029 in pthread_cond::~pthread_cond() () from /usr/bin/cygwin1.dll
> #5 0x000000018013d0dd in pthread_cond::~pthread_cond() () from /usr/bin/cygwin1.dll
> #6 0x0000000180141196 in pthread_cond_destroy () from /usr/bin/cygwin1.dll
> #7 0x0000000180116d5b in _sigfe () from /usr/bin/cygwin1.dll
> #8 0x0000000100908e38 in std::_Sp_counted_ptr_inplace<std::__future_base::_Task_state<std::function<void ()>, std::allocator<int>, void ()>, std::allocator<int>, (__gnu_cxx::_Lock_policy)2>::_M_dispose() ()
> The problem with the current implementation for concurrent insert and delete is explained at WikipediaNon-blocking linked list
>
> My question is how to solve this ? Adding lock protection in List_insert (removing lock-freee) or implementing a complete lock-free List based on Harris's solution to use two CAS?
First of all, please, please, please fix your MUA! Just like your
mails to cygwin-patches a couple of weeks ago, your mails are pretty
much unreadable due to broken line wrapping.
Back to business: This code is working since 2003. So, is that just
a theoretical problem, or a practical one? If the latter, what is
broken exactly?
However, since you're asking, a lockless implementation where appropriate
is always welcome.
Thanks,
Corinna
--
Corinna Vinschen Please, send mails regarding Cygwin to
Cygwin Maintainer cygwin AT cygwin DOT com
Red Hat
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 819 bytes --]
next prev parent reply other threads:[~2017-12-01 17:15 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <1543396632.5417641.1512146709346.ref@mail.yahoo.com>
2017-12-01 16:45 ` Xiaofeng Liu via cygwin
2017-12-01 17:15 ` Corinna Vinschen [this message]
2018-02-14 6:47 ` Xiaofeng Liu via cygwin
2018-02-14 7:04 ` Xiaofeng Liu via cygwin
2018-02-14 7:37 ` Xiaofeng Liu via cygwin
2018-02-14 14:30 ` Corinna Vinschen
[not found] <451353526.1938418.1518798301806.ref@mail.yahoo.com>
2018-02-16 16:25 ` Xiaofeng Liu via cygwin
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20171201171536.GA4325@calimero.vinschen.de \
--to=corinna-cygwin@cygwin.com \
--cc=cygwin@cygwin.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).