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
	:in-reply-to:references:subject:mime-version:content-type
	:content-transfer-encoding; q=dns; s=default; b=BMJ/1J4QeZVOkIZ/
	LqwylL9r+NSg92uITwZKTG6xwpNYH1UhRULFIjmwdV8UbqGmLYpJpTsB7BegGP5y
	LVGcObFq0Qw7fzd6wMaR0Ms37qUVsabhPnBWNDVvEIOkyLD5DBNjrxWUl+BU6Lgk
	G6erN4RdBvaE3UkSqFL+xxLwt5U=
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
	:in-reply-to:references:subject:mime-version:content-type
	:content-transfer-encoding; s=default; bh=HHFyBts52P4zXwfvG1zC6s
	qFuqg=; b=NSOB1MszmVwPMJ7fNUa5KdVFITqqNPvjmsfN2uzHh8OdVde0Rbx0As
	9jeh6bBy+PV3oAqHoRzRxEJ6IPpdBoEMkEVs6ZRj1nj4X9rcWESZSg2z1D1OzX9f
	MAtqiINurVhIUlfGlIyC/8Tksp594IGPmG335fnlcMztRKrGKH/BU=
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=-2.3 required=5.0 tests=AWL,BAYES_00,FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,FREEMAIL_REPLYTO_END_DIGIT,RCVD_IN_DNSWL_NONE,SPF_PASS,T_RP_MATCHES_RCVD autolearn=no version=3.3.2 spammy=H*x:KHTML, H*x:Chrome, H*x:AppleWebKit, H*x:Safari
X-HELO: sonic312-23.consmr.mail.gq1.yahoo.com
Date: Wed, 14 Feb 2018 07:37:38 +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: "cygwin AT cygwin DOT com" <cygwin AT cygwin DOT com>
Message-ID: <1541824013.551552.1518593858391@mail.yahoo.com>
In-Reply-To: <1460534026.545542.1518591843449@mail.yahoo.com>
References: <1543396632 DOT 5417641 DOT 1512146709346 DOT ref AT mail DOT yahoo DOT com> <1543396632 DOT 5417641 DOT 1512146709346 AT mail DOT yahoo DOT com> <20171201171536 DOT GA4325 AT calimero DOT vinschen DOT de> <1264797847 DOT 540865 DOT 1518590850864 AT mail DOT yahoo DOT com> <1460534026 DOT 545542 DOT 1518591843449 AT mail DOT yahoo DOT com>
Subject: Re: mixed usage of lock protection and lock-free List template class in thread.h
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by delorie.com id w1E7btbq012325

Sorry, I need send again for another try for the formatting.


(Yahoo deleted my spaces. Please reformat the code in your C++ editor if you want to use the code. Sorry!)
Here is the sample code that will hang in cygwin: test-thread.cpp
to compile: 
g++ -std=c++0x test-thread.cpp -lpthread 
In this code, mutex and cond need be created and destroyed very frequently, which could corrupt the static list object owned by some classes in thread.h. In my test, I have a computer of 8 threads to run cygwin, and the hang could happen when cond/mutex objects are created and destroyed for the order of 1 millions times within a few minutes.
Is this practical? Yes. My code for my product used a lot of std::future which use one mutex and one mutex for each object. The future objects are created and destroyed on the flight, so are for mutex and cond variables.  I can also observe that the peak memory kept increasing to a few hundred MB, and I suspect there is a MEMORY LEAK in cygwin kernel. 
I hope the format will be good. If not, I will try again.
Thanks. 

Xiaofeng

-----------------------------test-thread.cpp-------------------


#include <stdio.h> 
#include <stdlib.h> 
#include <thread> 
#include <vector> 
#include <string> 
#include <ctime> 
#include <climits> 
#include <cassert> 
#include <mutex> 

#include <condition_variable> 
#include <deque> 
#include <mutex> 
#include <pthread.h> 
#include <cstdint> 
using namespace std; 

template<class T> 
class Queue { 
typedef std::deque<T*> Container; 
public: 
Queue(int _capacity = std::numeric_limits<int>::max()) : capacity(_capacity), closed(false) {} 
bool enqueue(T* d) 
{ 
if (closed) return false; 
std::unique_lock<std::mutex> lock(mutex); 
if (d == 0) { closed = true; empty_cv.notify_all(); return true; } 
while (data.size() >= capacity) 
full_cv.wait(lock); 
data.push_back(d); 
empty_cv.notify_one(); 
return true; 
} 
T* dequeue() 
{ 
std::unique_lock<std::mutex> lock(mutex); 
while (data.empty() && !closed) 
empty_cv.wait(lock); 
if (data.size()) { 
T* d = data.front(); 
data.pop_front(); 
full_cv.notify_one(); 
return d; 
} else return 0; 
} 
size_t size() const { return data.size(); } 

private: 
std::mutex mutex; 
std::condition_variable full_cv, empty_cv; 
uint32_t capacity; 
bool closed; 
Container data; 
}; 

struct Node { 
int data; 
}; 

struct Job { 
Node* node; 
Queue<Node>* recycle; 
}; 

static Queue<Job> jobs; 

static void* handle_job(void* arg) 
{ 
long ithr = (long)arg; 
unsigned long seed = time(0) + ithr*1000000; 
int NS = 1000; 
while (Job* j = jobs.dequeue()) { 
struct timespec ts; 
ts.tv_sec = 0; 
seed = seed * 1103515245 + 12345; 
ts.tv_nsec = seed%NS; 
nanosleep(&ts, 0); 
j->recycle->enqueue(j->node); 
delete j; 
} 
} 

struct Task { 
Queue<Node> recycle; 
int size; // number of sub jobs 
Task(int N) : size(N) 
{ 
for (int i = 0; i<N; ++i) { 
Node* t = new Node(); 
t->data = i; 
Job* job = new Job; 
job->node = t; 
job->recycle = &recycle; 
jobs.enqueue(job); 
} 
} 
~Task() 
{ 
int i = 0; 
while (Node* t = recycle.dequeue()) { 
delete t; 
if (++i == size) break; 
} 
} 
}; 

static string timestamp() 
{ 
time_t t; 
struct tm tmp; 
char buf[80]; 
t = time(NULL); 
localtime_r(&t, &tmp); 
strftime(buf, sizeof(buf), "%d-%m-%Y %I:%M:%S", &tmp); 
return buf; 
} 

static void* create_task(void* arg) 
{ 
long ithr = (long)arg; 
int TASK_NUM = 1000000; 
int one_percent = TASK_NUM/100; 
int TASK_SUB_JOB_NUM = 1; 
int NS = 1000; 
unsigned long seed = time(0) + ithr*10000; 
int i = 0; 
for (; i < TASK_NUM; ++i) { 
struct timespec ts; 
ts.tv_sec = 0; 
seed = seed * 1103515245 + 12345; 
ts.tv_nsec = seed%NS; 
nanosleep(&ts, 0); 
if (i%one_percent == 0) { 
fprintf(stderr, "%s: create_task[%d]: %d%% done\n", timestamp().c_str(), ithr, i/one_percent); 
} 
Task task(TASK_SUB_JOB_NUM); 
} 
fprintf(stderr, "%s: create_task[%d]: %d%% done\n", timestamp().c_str(), ithr, i/one_percent); 
} 


int main() 
{ 
int NTHR_HANDLE_JOB = 4, NTHR_CREATE_TASK = 4; 
std::vector<pthread_t> threads(NTHR_HANDLE_JOB+NTHR_CREATE_TASK); 
int k = 0; 
for (long i = 0; i < NTHR_HANDLE_JOB; ++i) { 
pthread_create(&threads[k++], NULL, handle_job, (void*)i); 
} 
for (long i = 0; i < NTHR_CREATE_TASK; ++i) { 
pthread_create(&threads[k++], NULL, create_task, (void*)i); 
} 
// wait for create_task thread 
for (size_t i = NTHR_HANDLE_JOB; i < threads.size(); ++i) { 
pthread_join(threads[i], NULL); 
} 
jobs.enqueue(0); 
// wait for handle_job thread 
for (size_t i = 0; i < NTHR_HANDLE_JOB; ++i) 
pthread_join(threads[i], NULL); 
} 
----------------------------end of test-thread.cpp--------------------------

To: cygwin AT cygwin DOT com Sent: Friday, December 1, 2017 9:15 AM
Subject: Re: mixed usage of lock protection and lock-free List template class in thread.h


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

--
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