X-Recipient:	archive-cygwin AT delorie DOT com
DomainKey-Signature:	a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id
	:list-unsubscribe:list-subscribe:list-archive:list-post
	:list-help:sender:date:from:reply-to:reply-to:to:message-id
	:subject:mime-version:references:content-type
	:content-transfer-encoding; q=dns; s=default; b=mTMfQG039nWbO8NB
	JbKzk37VnlAwVZ63KGPKVQetoBIdrOWOKgYS3LcwiQrnsu8tRUgyCLxt9k4ZQacC
	BSTgx7fNHzNliNaj2nrxTVz+ldmLOUUMEQ+BeSh7jF7uZwMjymX4pbspjVcwt3KV
	GfN1D4jQjm4nF+phbUMUFtD/+mM=
DKIM-Signature:	v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id
	:list-unsubscribe:list-subscribe:list-archive:list-post
	:list-help:sender:date:from:reply-to:reply-to:to:message-id
	:subject:mime-version:references:content-type
	:content-transfer-encoding; s=default; bh=vPL1fLzDELwndE390KdnIt
	7aoRY=; b=l/uw22BavtVO16ydG02xjoOxUL/UdZvXbz/+Ra3UwEk92tE23Cvsbx
	91zex5UqOc9fjshVxlLGwmfnqgvVCRtQy7tzUqyYAZ1goz2kmiZT7oqHHgCjzFxH
	YMW2+BIStC1xZFzx+CTh0sE18GSEUzZRb1en2OVJsiBw+1Eg8m+mo=
Mailing-List:	contact cygwin-help AT cygwin DOT com; run by ezmlm
List-Id:	<cygwin.cygwin.com>
List-Subscribe:	<mailto:cygwin-subscribe AT cygwin DOT com>
List-Archive:	<http://sourceware.org/ml/cygwin/>
List-Post:	<mailto:cygwin AT cygwin DOT com>
List-Help:	<mailto:cygwin-help AT cygwin DOT com>, <http://sourceware.org/ml/#faqs>
Sender:	cygwin-owner AT cygwin DOT com
Mail-Followup-To:	cygwin AT cygwin DOT com
Delivered-To:	mailing list cygwin AT cygwin DOT com
Authentication-Results:	sourceware.org; auth=none
X-Virus-Found:	No
X-Spam-SWARE-Status:	No, score=3.2 required=5.0 tests=AWL,BAYES_20,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,FREEMAIL_REPLYTO_END_DIGIT,HTML_MESSAGE,KB_WAM_FROM_NAME_SINGLEWORD,RCVD_IN_DNSWL_NONE,SPF_PASS,T_RP_MATCHES_RCVD autolearn=no version=3.3.2 spammy=assets, H*UA:Win64, H*UA:x64, H*x:Win64
X-HELO:	sonic304-22.consmr.mail.gq1.yahoo.com
Date:	Fri, 1 Dec 2017 16:45:09 +0000 (UTC)
From:	"Xiaofeng Liu via cygwin" <cygwin AT cygwin DOT com>
Reply-To:	Xiaofeng Liu <liuxf09 AT yahoo DOT com>
Reply-To:	Xiaofeng Liu <liuxf09 AT yahoo DOT com>
To:	The Cygwin Mailing List <cygwin AT cygwin DOT com>
Message-ID:	<1543396632.5417641.1512146709346@mail.yahoo.com>
Subject:	mixed usage of lock protection and lock-free List template class in thread.h
MIME-Version:	1.0
References:	<1543396632 DOT 5417641 DOT 1512146709346 DOT ref AT mail DOT yahoo DOT com>
X-IsSubscribed:	yes
X-MIME-Autoconverted:	from quoted-printable to 8bit by delorie.com id vB1GjkZa012577

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?
Thanks.
Xiaofeng Liu

  
|  
|   
|   
|   |    |

   |

  |
|  
|   |  
Non-blocking linked list
 Several strategies for implementing non-blocking lists have been suggested.  |   |

  |

  |

 

--
Problem reports:       http://cygwin.com/problems.html
FAQ:                   http://cygwin.com/faq/
Documentation:         http://cygwin.com/docs.html
Unsubscribe info:      http://cygwin.com/ml/#unsubscribe-simple

- Raw text -