Skip to contentSkip to conversation

count: Employ new code-snippet scheme (cont.)

PATCH Applied Akira Yokosawa 2 participants 9 messages Oct 13, 2018 – Oct 15, 2018

lore
Share & tools
lore
#0 lore raw

cover count: Employ new code-snippet scheme (cont.)

Hi Paul,

count_lim_sig.c was a hard one to review for me regarding the usage of READ_ONCE()/WRITE_ONCE(). Patch #5 is my attempt to add several of them. There might be other combination of racy accesses.

Patches #1--#4 are trivial ones.

Patch #6 is the result of quick review of your recent addition to toolsoftrade. I'm not sure you like the addition of comments "/* BUGGY!!! */" to Lisitngs which look irrelevant to their captions.

Patches #5 and #6 are more likely to need your close look.

Thanks, Akira
--
Akira Yokosawa (6):
count: Employ new scheme for snippet of count_lim_app
count: Fix uses of READ/WRITE_ONCE() in count_lim_app
count: Employ new scheme for snippet of count_lim_atomic
count: Employ new scheme for snippet of count_lim_sig
count: READ/WRITE_ONCE() tweaks for count_lim_sig
toolsoftrade: Proofread newly added sections

 CodeSamples/count/count_lim_app.c    |  17 +-
 CodeSamples/count/count_lim_atomic.c | 209 ++++----
 CodeSamples/count/count_lim_sig.c    | 159 ++++---
 count/count.tex                      | 892 ++++++++++-------------------------
 toolsoftrade/toolsoftrade.tex        |  44 +-
 5 files changed, 494 insertions(+), 827 deletions(-)
Signature · 1 line
2.7.4
#1 lore raw

PATCH 1/6 count: Employ new scheme for snippet of count_lim_app

From ea84d6ff5dd7e0a0f89d8eacf844d920298584b9 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Mon, 8 Oct 2018 16:08:59 +0900
Subject: [PATCH 1/6] count: Employ new scheme for snippet of count_lim_app

---
 CodeSamples/count/count_lim_app.c | 11 ++++++++---
 count/count.tex                   | 40 ++++++---------------------------------
 2 files changed, 14 insertions(+), 37 deletions(-)
CodeSamples/count/count_lim_app.c +8 -3
index 0bdf6b0..1817c19 100644
@@ -21,6 +21,7 @@
 
 #include "../api.h"
 
+//\begin{snippet}[labelbase=ln:count:count_lim_app:variable,commandchars=\\\@\$]
 unsigned long __thread counter = 0;
 unsigned long __thread countermax = 0;
 unsigned long globalcountmax = 10000;
@@ -29,6 +30,7 @@ unsigned long globalreserve = 0;
 unsigned long *counterp[NR_THREADS] = { NULL };
 DEFINE_SPINLOCK(gblcnt_mutex);
 #define MAX_COUNTERMAX 100
+//\end{snippet}
 
 static void globalize_count(void)
 {
@@ -38,18 +40,21 @@ static void globalize_count(void)
 	countermax = 0;
 }
 
+//\begin{snippet}[labelbase=ln:count:count_lim_app:balance,commandchars=\\\[\]]
 static void balance_count(void)
 {
-	countermax = globalcountmax - globalcount - globalreserve;
+	countermax = globalcountmax -
+	             globalcount - globalreserve;
 	countermax /= num_online_threads();
-	if (countermax > MAX_COUNTERMAX)
-		countermax = MAX_COUNTERMAX;
+	if (countermax > MAX_COUNTERMAX)	//\lnlbl{enforce:b}
+		countermax = MAX_COUNTERMAX;	//\lnlbl{enforce:e}
 	globalreserve += countermax;
 	counter = countermax / 2;
 	if (counter > globalcount)
 		counter = globalcount;
 	globalcount -= counter;
 }
+//\end{snippet}
 
 int add_count(unsigned long delta)
 {
count/count.tex +6 -34
index 3598aac..90d0936 100644
@@ -1759,44 +1759,13 @@ This task is undertaken in the next section.
 \label{sec:count:Approximate Limit Counter Implementation}
 
 \begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
-  1 unsigned long __thread counter = 0;
-  2 unsigned long __thread countermax = 0;
-  3 unsigned long globalcountmax = 10000;
-  4 unsigned long globalcount = 0;
-  5 unsigned long globalreserve = 0;
-  6 unsigned long *counterp[NR_THREADS] = { NULL };
-  7 DEFINE_SPINLOCK(gblcnt_mutex);
-  8 #define MAX_COUNTERMAX 100
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/count/[email protected]}
 \caption{Approximate Limit Counter Variables}
 \label{lst:count:Approximate Limit Counter Variables}
 \end{listing}
 
 \begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
-  1 static void balance_count(void)
-  2 {
-  3   countermax = globalcountmax -
-  4                globalcount - globalreserve;
-  5   countermax /= num_online_threads();
-  6   if (countermax > MAX_COUNTERMAX)
-  7     countermax = MAX_COUNTERMAX;
-  8   globalreserve += countermax;
-  9   counter = countermax / 2;
- 10   if (counter > globalcount)
- 11     counter = globalcount;
- 12   globalcount -= counter;
- 13 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/count/[email protected]}
 \caption{Approximate Limit Counter Balancing}
 \label{lst:count:Approximate Limit Counter Balancing}
 \end{listing}
@@ -1813,12 +1782,15 @@ Listing~\ref{lst:count:Simple Limit Counter Variables},
 with the addition of \co{MAX_COUNTERMAX}, which sets the maximum
 permissible value of the per-thread \co{countermax} variable.
 
+\begin{lineref}[ln:count:count_lim_app:balance]
 Similarly,
 Listing~\ref{lst:count:Approximate Limit Counter Balancing}
 is identical to the \co{balance_count()} function in
 Listing~\ref{lst:count:Simple Limit Counter Utility Functions},
-with the addition of lines~6 and~7, which enforce the
+with the addition of
+lines~\lnref{enforce:b} and~\lnref{enforce:e}, which enforce the
 \co{MAX_COUNTERMAX} limit on the per-thread \co{countermax} variable.
+\end{lineref}
 
 \subsection{Approximate Limit Counter Discussion}
 
Signature · 1 line
2.7.4
#2 lore raw

PATCH 2/6 count: Fix uses of READ/WRITE_ONCE() in count_lim_app

In reply to Akira Yokosawa

From a3544822ccd81e63b98f3db3c428c1867c983e9a Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Mon, 8 Oct 2018 16:11:29 +0900
Subject: [PATCH 2/6] count: Fix uses of READ/WRITE_ONCE() in count_lim_app

---
 CodeSamples/count/count_lim_app.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
CodeSamples/count/count_lim_app.c +3 -3
index 1817c19..ad8f09f 100644
@@ -59,7 +59,7 @@ static void balance_count(void)
 int add_count(unsigned long delta)
 {
 	if (countermax - counter >= delta) {
-		counter += delta;
+		WRITE_ONCE(counter, counter + delta);
 		return 1;
 	}
 	spin_lock(&gblcnt_mutex);
@@ -77,7 +77,7 @@ int add_count(unsigned long delta)
 int sub_count(unsigned long delta)
 {
 	if (counter >= delta) {
-		counter -= delta;
+		WRITE_ONCE(counter, counter - delta);
 		return 1;
 	}
 	spin_lock(&gblcnt_mutex);
@@ -101,7 +101,7 @@ unsigned long read_count(void)
 	sum = globalcount;
 	for_each_thread(t)
 		if (counterp[t] != NULL)
-			sum += *counterp[t];
+			sum += READ_ONCE(*counterp[t]);
 	spin_unlock(&gblcnt_mutex);
 	return sum;
 }
Signature · 1 line
2.7.4
#3 lore raw

PATCH 3/6 count: Employ new scheme for snippet of count_lim_atomic

In reply to Akira Yokosawa

From 95838d3aa0446586b7e7ef84b942e2a51a3daa88 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Mon, 8 Oct 2018 19:45:06 +0900
Subject: [PATCH 3/6] count: Employ new scheme for snippet of count_lim_atomic

---
 CodeSamples/count/count_lim_atomic.c | 209 ++++++++--------
 count/count.tex                      | 457 ++++++++++++-----------------------
 2 files changed, 265 insertions(+), 401 deletions(-)
CodeSamples/count/count_lim_atomic.c +114 -95
index 491d700..6190a9f 100644
@@ -21,51 +21,58 @@
 
 #include "../api.h"
 
-atomic_t __thread counterandmax = ATOMIC_INIT(0);
-unsigned long globalcountmax = 1 << 25;
+static void balance_count(void);
+
+//\begin{snippet}[labelbase=ln:count:count_lim_atomic:var_access,commandchars=\\\@\$]
+atomic_t __thread counterandmax = ATOMIC_INIT(0);	//\lnlbl{var:candmax}
+unsigned long globalcountmax = 1 << 25;			//\lnlbl{var:def:b}
 unsigned long globalcount = 0;
 unsigned long globalreserve = 0;
 atomic_t *counterp[NR_THREADS] = { NULL };
-DEFINE_SPINLOCK(gblcnt_mutex);
-#define CM_BITS (sizeof(atomic_t) * 4)
-#define MAX_COUNTERMAX ((1 << CM_BITS) - 1)
+DEFINE_SPINLOCK(gblcnt_mutex);				//\lnlbl{var:def:e}
+#define CM_BITS (sizeof(atomic_t) * 4)			//\lnlbl{var:CM_BITS}
+#define MAX_COUNTERMAX ((1 << CM_BITS) - 1)		//\lnlbl{var:MAX_CMAX}
 
-static void split_counterandmax_int(int cami, int *c, int *cm)
+static __inline__ void					//\lnlbl{split_int:b}
+split_counterandmax_int(int cami, int *c, int *cm)
 {
-	*c = (cami >> CM_BITS) & MAX_COUNTERMAX;
-	*cm = cami & MAX_COUNTERMAX;
-}
+	*c = (cami >> CM_BITS) & MAX_COUNTERMAX;	//\lnlbl{split_int:msh}
+	*cm = cami & MAX_COUNTERMAX;			//\lnlbl{split_int:lsh}
+}							//\lnlbl{split_int:e}
 
-static void split_counterandmax(atomic_t *cam, int *old, int *c, int *cm)
+static __inline__ void					//\lnlbl{split:b}
+split_counterandmax(atomic_t *cam, int *old, int *c, int *cm)//\lnlbl{split:func}
 {
-	unsigned int cami = atomic_read(cam);
+	unsigned int cami = atomic_read(cam);		//\lnlbl{split:int}
 
-	*old = cami;
-	split_counterandmax_int(cami, c, cm);
-}
+	*old = cami;					//\lnlbl{split:old}
+	split_counterandmax_int(cami, c, cm);		//\lnlbl{split:split_int}
+}							//\lnlbl{split:e}
 
-static int merge_counterandmax(int c, int cm)
+static __inline__ int merge_counterandmax(int c, int cm)//\lnlbl{merge:b}
 {
 	unsigned int cami;
 
-	cami = (c << CM_BITS) | cm;
+	cami = (c << CM_BITS) | cm;			//\lnlbl{merge:merge}
 	return ((int)cami);
-}
+}							//\lnlbl{merge:e}
+//\end{snippet}
 
-static void globalize_count(void)
+//\begin{snippet}[labelbase=ln:count:count_lim_atomic:utility1,commandchars=\\\@\$]
+static void globalize_count(void)			//\lnlbl{globalize:b}
 {
 	int c;
 	int cm;
 	int old;
 
-	split_counterandmax(&counterandmax, &old, &c, &cm);
+	split_counterandmax(&counterandmax, &old, &c, &cm);//\lnlbl{globalize:split}
 	globalcount += c;
 	globalreserve -= cm;
 	old = merge_counterandmax(0, 0);
 	atomic_set(&counterandmax, old);
-}
+}							//\lnlbl{globalize:e}
 
-static void flush_local_count(void)
+static void flush_local_count(void)			//\lnlbl{flush:b}
 {
 	int c;
 	int cm;
@@ -73,85 +80,69 @@ static void flush_local_count(void)
 	int t;
 	int zero;
 
-	if (globalreserve == 0)
-		return;
-	zero = merge_counterandmax(0, 0);
-	for_each_thread(t)
-		if (counterp[t] != NULL) {
-			old = atomic_xchg(counterp[t], zero);
-			split_counterandmax_int(old, &c, &cm);
-			globalcount += c;
-			globalreserve -= cm;
-		}
-}
-
-static void balance_count(void)
-{
-	int c;
-	int cm;
-	int old;
-	unsigned long limit;
-
-	limit = globalcountmax - globalcount - globalreserve;
-	limit /= num_online_threads();
-	if (limit > MAX_COUNTERMAX)
-		cm = MAX_COUNTERMAX;
-	else
-		cm = limit;
-	globalreserve += cm;
-	c = cm / 2;
-	if (c > globalcount)
-		c = globalcount;
-	globalcount -= c;
-	old = merge_counterandmax(c, cm);
-	atomic_set(&counterandmax, old);
-}
-
-int add_count(unsigned long delta)
+	if (globalreserve == 0)				//\lnlbl{flush:checkrsv}
+		return;					//\lnlbl{flush:return:n}
+	zero = merge_counterandmax(0, 0);		//\lnlbl{flush:initzero}
+	for_each_thread(t)				//\lnlbl{flush:loop:b}
+		if (counterp[t] != NULL) {		//\lnlbl{flush:checkp}
+			old = atomic_xchg(counterp[t], zero);//\lnlbl{flush:atmxchg}
+			split_counterandmax_int(old, &c, &cm);//\lnlbl{flush:split}
+			globalcount += c;		//\lnlbl{flush:glbcnt}
+			globalreserve -= cm;		//\lnlbl{flush:glbrsv}
+		}					//\lnlbl{flush:loop:e}
+}							//\lnlbl{flush:e}
+//\end{snippet}
+
+//\begin{snippet}[labelbase=ln:count:count_lim_atomic:add_sub,commandchars=\\\@\$]
+int add_count(unsigned long delta)			//\lnlbl{add:b}
 {
 	int c;
 	int cm;
 	int old;
 	int new;
 
-	do {
-		split_counterandmax(&counterandmax, &old, &c, &cm);
-		if (delta > MAX_COUNTERMAX || c + delta > cm)
-			goto slowpath;
-		new = merge_counterandmax(c + delta, cm);
-	} while (atomic_cmpxchg(&counterandmax, old, new) != old);
-	return 1;
-slowpath:
-	spin_lock(&gblcnt_mutex);
-	globalize_count();
-	if (globalcountmax - globalcount - globalreserve < delta) {
-		flush_local_count();
-		if (globalcountmax - globalcount - globalreserve < delta) {
-			spin_unlock(&gblcnt_mutex);
-			return 0;
+	do {						//\lnlbl{add:fast:b}
+		split_counterandmax(&counterandmax, &old, &c, &cm);//\lnlbl{add:split}
+		if (delta > MAX_COUNTERMAX || c + delta > cm)//\lnlbl{add:check}
+			goto slowpath;			//\lnlbl{add:goto}
+		new = merge_counterandmax(c + delta, cm);//\lnlbl{add:merge}
+	} while (atomic_cmpxchg(&counterandmax,		//\lnlbl{add:atmcmpex}
+	                        old, new) != old);	//\lnlbl{add:loop:e}
+	return 1;					//\lnlbl{add:return:fs}
+slowpath:						//\lnlbl{add:slow:b}
+	spin_lock(&gblcnt_mutex);			//\lnlbl{add:acquire}
+	globalize_count();				//\lnlbl{add:globalize}
+	if (globalcountmax - globalcount -		//\lnlbl{add:checkglb:b}
+	    globalreserve < delta) {			//\lnlbl{add:checkglb:e}
+		flush_local_count();			//\lnlbl{add:flush}
+		if (globalcountmax - globalcount -	//\lnlbl{add:checkglb:nb}
+		    globalreserve < delta) {		//\lnlbl{add:checkglb:ne}
+			spin_unlock(&gblcnt_mutex);	//\lnlbl{add:release:f}
+			return 0;			//\lnlbl{add:return:sf}
 		}
 	}
-	globalcount += delta;
-	balance_count();
-	spin_unlock(&gblcnt_mutex);
-	return 1;
-}
+	globalcount += delta;				//\lnlbl{add:addglb}
+	balance_count();				//\lnlbl{add:balance}
+	spin_unlock(&gblcnt_mutex);			//\lnlbl{add:release:s}
+	return 1;					//\lnlbl{add:return:ss}
+}							//\lnlbl{add:e}
 
-int sub_count(unsigned long delta)
+int sub_count(unsigned long delta)			//\lnlbl{sub:b}
 {
 	int c;
 	int cm;
 	int old;
 	int new;
 
-	do {
+	do {						//\lnlbl{sub:fast:b}
 		split_counterandmax(&counterandmax, &old, &c, &cm);
 		if (delta > c)
-			goto slowpath;
+		  goto slowpath;
 		new = merge_counterandmax(c - delta, cm);
-	} while (atomic_cmpxchg(&counterandmax, old, new) != old);
-	return 1;
-slowpath:
+	} while (atomic_cmpxchg(&counterandmax,
+	                        old, new) != old);
+	return 1;					//\lnlbl{sub:fast:e}
+ slowpath:						//\lnlbl{sub:slow:b}
 	spin_lock(&gblcnt_mutex);
 	globalize_count();
 	if (globalcount < delta) {
@@ -164,10 +155,12 @@ slowpath:
 	globalcount -= delta;
 	balance_count();
 	spin_unlock(&gblcnt_mutex);
-	return 1;
-}
+	return 1;					//\lnlbl{sub:slow:e}
+}							//\lnlbl{sub:e}
+//\end{snippet}
 
-unsigned long read_count(void)
+//\begin{snippet}[labelbase=ln:count:count_lim_atomic:read,commandchars=\\\@\$]
+unsigned long read_count(void)				//\lnlbl{b}
 {
 	int c;
 	int cm;
@@ -175,22 +168,47 @@ unsigned long read_count(void)
 	int t;
 	unsigned long sum;
 
-	spin_lock(&gblcnt_mutex);
-	sum = globalcount;
-	for_each_thread(t)
+	spin_lock(&gblcnt_mutex);			//\lnlbl{acquire}
+	sum = globalcount;				//\lnlbl{initsum}
+	for_each_thread(t)				//\lnlbl{loop:b}
 		if (counterp[t] != NULL) {
-			split_counterandmax(counterp[t], &old, &c, &cm);
+			split_counterandmax(counterp[t], &old, &c, &cm);//\lnlbl{split}
 			sum += c;
-		}
-	spin_unlock(&gblcnt_mutex);
-	return sum;
-}
+		}					//\lnlbl{loop:e}
+	spin_unlock(&gblcnt_mutex);			//\lnlbl{release}
+	return sum;					//\lnlbl{return}
+}							//\lnlbl{e}
+//\end{snippet}
 
 void count_init(void)
 {
 }
 
-void count_register_thread(void)
+//\begin{snippet}[labelbase=ln:count:count_lim_atomic:utility2,commandchars=\\\@\$]
+static void balance_count(void)				//\lnlbl{balance:b}
+{
+	int c;
+	int cm;
+	int old;
+	unsigned long limit;
+
+	limit = globalcountmax - globalcount -
+	        globalreserve;
+	limit /= num_online_threads();
+	if (limit > MAX_COUNTERMAX)
+		cm = MAX_COUNTERMAX;
+	else
+		cm = limit;
+	globalreserve += cm;
+	c = cm / 2;
+	if (c > globalcount)
+		c = globalcount;
+	globalcount -= c;
+	old = merge_counterandmax(c, cm);
+	atomic_set(&counterandmax, old);		//\lnlbl{balance:atmcset}
+}							//\lnlbl{balance:e}
+
+void count_register_thread(void)			//\lnlbl{register:b}
 {
 	int idx = smp_thread_id();
 
@@ -199,7 +217,7 @@ void count_register_thread(void)
 	spin_unlock(&gblcnt_mutex);
 }
 
-void count_unregister_thread(int nthreadsexpected)
+void count_unregister_thread(int nthreadsexpected)	//\lnlbl{unregister:b}
 {
 	int idx = smp_thread_id();
 
@@ -208,6 +226,7 @@ void count_unregister_thread(int nthreadsexpected)
 	counterp[idx] = NULL;
 	spin_unlock(&gblcnt_mutex);
 }
+//\end{snippet}
 
 void count_cleanup(void)
 {
count/count.tex +151 -306

625 lines not on this page · raw message

Signature · 1 line
2.7.4
#4 lore raw

PATCH 4/6 count: Employ new scheme for snippet of count_lim_sig

In reply to Akira Yokosawa

From 3db4be0993d4c955dfed6a625c622c33b52bf2a5 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Tue, 9 Oct 2018 01:45:32 +0900
Subject: [PATCH 4/6] count: Employ new scheme for snippet of count_lim_sig

---
 CodeSamples/count/count_lim_sig.c | 148 +++++++-------
 count/count.tex                   | 395 ++++++++++----------------------------
 2 files changed, 184 insertions(+), 359 deletions(-)
CodeSamples/count/count_lim_sig.c +82 -66
index 5eae9ba..f22bfef 100644
@@ -22,77 +22,81 @@
 #include "../api.h"
 #include <signal.h>
 
-#define THEFT_IDLE	0
-#define THEFT_REQ	1
-#define	THEFT_ACK	2
-#define THEFT_READY	3
+//\begin{snippet}[labelbase=ln:count:count_lim_sig:data,commandchars=\\\@\$]
+#define THEFT_IDLE   0					//\lnlbl{value:b}
+#define THEFT_REQ    1
+#define	THEFT_ACK    2
+#define THEFT_READY  3
 
 int __thread theft = THEFT_IDLE;
-int __thread counting = 0;
-unsigned long __thread counter = 0;
+int __thread counting = 0;				//\lnlbl{value:e}
+unsigned long __thread counter = 0;			//\lnlbl{var:b}
 unsigned long __thread countermax = 0;
 unsigned long globalcountmax = 10000;
 unsigned long globalcount = 0;
 unsigned long globalreserve = 0;
 unsigned long *counterp[NR_THREADS] = { NULL };
-unsigned long *countermaxp[NR_THREADS] = { NULL };
-int *theftp[NR_THREADS] = { NULL };
+unsigned long *countermaxp[NR_THREADS] = { NULL };	//\lnlbl{maxp}
+int *theftp[NR_THREADS] = { NULL };			//\lnlbl{theftp}
 DEFINE_SPINLOCK(gblcnt_mutex);
-#define MAX_COUNTERMAX 100
+#define MAX_COUNTERMAX 100				//\lnlbl{var:e}
+//\end{snippet}
 
-static void globalize_count(void)
+//\begin{snippet}[labelbase=ln:count:count_lim_sig:migration,commandchars=\\\@\$]
+static void globalize_count(void)		//\lnlbl{globalize:b}
 {
 	globalcount += counter;
 	counter = 0;
 	globalreserve -= countermax;
 	countermax = 0;
-}
+}						//\lnlbl{globalize:e}
 
-static void flush_local_count_sig(int unused)
+static void flush_local_count_sig(int unused)	//\lnlbl{flush_sig:b}
 {
-	if (READ_ONCE(theft) != THEFT_REQ)
-		return;
-	smp_mb();
-	WRITE_ONCE(theft, THEFT_ACK);
-	if (!counting) {
-		WRITE_ONCE(theft, THEFT_READY);
+	if (READ_ONCE(theft) != THEFT_REQ)	//\lnlbl{flush_sig:check:REQ}
+		return;				//\lnlbl{flush_sig:return:n}
+	smp_mb();				//\lnlbl{flush_sig:mb:1}
+	WRITE_ONCE(theft, THEFT_ACK);		//\lnlbl{flush_sig:set:ACK}
+	if (!counting) {			//\lnlbl{flush_sig:check:fast}
+		WRITE_ONCE(theft, THEFT_READY);	//\lnlbl{flush_sig:set:READY}
 	}
 	smp_mb();
-}
+}						//\lnlbl{flush_sig:e}
 
-static void flush_local_count(void)
+static void flush_local_count(void)			//\lnlbl{flush:b}
 {
 	int t;
 	thread_id_t tid;
 
-	for_each_tid(t, tid)
-		if (theftp[t] != NULL) {
-			if (*countermaxp[t] == 0) {
-				WRITE_ONCE(*theftp[t], THEFT_READY);
-				continue;
+	for_each_tid(t, tid)				//\lnlbl{flush:loop:b}
+		if (theftp[t] != NULL) {		//\lnlbl{flush:skip}
+			if (*countermaxp[t] == 0) {	//\lnlbl{flush:checkmax}
+				WRITE_ONCE(*theftp[t], THEFT_READY);//\lnlbl{flush:READY}
+				continue;		//\lnlbl{flush:next}
 			}
-			WRITE_ONCE(*theftp[t], THEFT_REQ);
-			pthread_kill(tid, SIGUSR1);
-		}
-	for_each_tid(t, tid) {
-		if (theftp[t] == NULL)
-			continue;
-		while (READ_ONCE(*theftp[t]) != THEFT_READY) {
-			poll(NULL, 0, 1);
-			if (READ_ONCE(*theftp[t]) == THEFT_REQ)
-				pthread_kill(tid, SIGUSR1);
-		}
-		globalcount += *counterp[t];
+			WRITE_ONCE(*theftp[t], THEFT_REQ);//\lnlbl{flush:REQ}
+			pthread_kill(tid, SIGUSR1);	//\lnlbl{flush:signal}
+		}					//\lnlbl{flush:loop:e}
+	for_each_tid(t, tid) {				//\lnlbl{flush:loop2:b}
+		if (theftp[t] == NULL)			//\lnlbl{flush:skip:nonexist}
+			continue;			//\lnlbl{flush:next2}
+		while (READ_ONCE(*theftp[t]) != THEFT_READY) {//\lnlbl{flush:loop3:b}
+			poll(NULL, 0, 1);		//\lnlbl{flush:block}
+			if (READ_ONCE(*theftp[t]) == THEFT_REQ)//\lnlbl{flush:check:REQ}
+				pthread_kill(tid, SIGUSR1);//\lnlbl{flush:signal2}
+		}					//\lnlbl{flush:loop3:e}
+		globalcount += *counterp[t];		//\lnlbl{flush:thiev:b}
 		*counterp[t] = 0;
 		globalreserve -= *countermaxp[t];
-		*countermaxp[t] = 0;
-		WRITE_ONCE(*theftp[t], THEFT_IDLE);
-	}
-}
+		*countermaxp[t] = 0;			//\lnlbl{flush:thiev:e}
+		WRITE_ONCE(*theftp[t], THEFT_IDLE);	//\lnlbl{flush:IDLE}
+	}						//\lnlbl{flush:loop2:e}
+}							//\lnlbl{flush:e}
 
-static void balance_count(void)
+static void balance_count(void)				//\lnlbl{balance:b}
 {
-	countermax = globalcountmax - globalcount - globalreserve;
+	countermax = globalcountmax - globalcount -
+	             globalreserve;
 	countermax /= num_online_threads();
 	if (countermax > MAX_COUNTERMAX)
 		countermax = MAX_COUNTERMAX;
@@ -101,42 +105,49 @@ static void balance_count(void)
 	if (counter > globalcount)
 		counter = globalcount;
 	globalcount -= counter;
-}
+}							//\lnlbl{balance:e}
+//\end{snippet}
 
-int add_count(unsigned long delta)
+//\begin{snippet}[labelbase=ln:count:count_lim_sig:add,commandchars=\\\@\$]
+int add_count(unsigned long delta)			//\lnlbl{b}
 {
 	int fastpath = 0;
 
-	counting = 1;
-	barrier();
-	if (countermax - counter >= delta && READ_ONCE(theft) <= THEFT_REQ) {
-		counter += delta;
-		fastpath = 1;
+	counting = 1;					//\lnlbl{fast:b}
+	barrier();					//\lnlbl{barrier:1}
+	if (countermax - counter >= delta &&		//\lnlbl{check:b}
+	    READ_ONCE(theft) <= THEFT_REQ) {		//\lnlbl{check:e}
+		counter += delta;			//\lnlbl{add:f}
+		fastpath = 1;				//\lnlbl{fasttaken}
 	}
-	barrier();
-	counting = 0;
-	barrier();
-	if (READ_ONCE(theft) == THEFT_ACK) {
-		smp_mb();
-		WRITE_ONCE(theft, THEFT_READY);
+	barrier();					//\lnlbl{barrier:2}
+	counting = 0;					//\lnlbl{clearcnt}
+	barrier();					//\lnlbl{barrier:3}
+	if (READ_ONCE(theft) == THEFT_ACK) {		//\lnlbl{check:ACK}
+		smp_mb();				//\lnlbl{mb}
+		WRITE_ONCE(theft, THEFT_READY);		//\lnlbl{READY}
 	}
 	if (fastpath)
-		return 1;
-	spin_lock(&gblcnt_mutex);
+		return 1;				//\lnlbl{return:fs}
+	spin_lock(&gblcnt_mutex);			//\lnlbl{acquire}
 	globalize_count();
-	if (globalcountmax - globalcount - globalreserve < delta) {
+	if (globalcountmax - globalcount -
+	    globalreserve < delta) {
 		flush_local_count();
-		if (globalcountmax - globalcount - globalreserve < delta) {
-			spin_unlock(&gblcnt_mutex);
-			return 0;
+		if (globalcountmax - globalcount -
+		    globalreserve < delta) {
+			spin_unlock(&gblcnt_mutex);	//\lnlbl{release:f}
+			return 0;			//\lnlbl{return:sf}
 		}
 	}
 	globalcount += delta;
 	balance_count();
 	spin_unlock(&gblcnt_mutex);
-	return 1;
-}
+	return 1;					//\lnlbl{return:ss}
+}							//\lnlbl{e}
+//\end{snippet}
 
+//\begin{snippet}[labelbase=ln:count:count_lim_sig:sub,commandchars=\\\@\$]
 int sub_count(unsigned long delta)
 {
 	int fastpath = 0;
@@ -170,7 +181,9 @@ int sub_count(unsigned long delta)
 	spin_unlock(&gblcnt_mutex);
 	return 1;
 }
+//\end{snippet}
 
+//\begin{snippet}[labelbase=ln:count:count_lim_sig:read,commandchars=\\\@\$]
 unsigned long read_count(void)
 {
 	int t;
@@ -184,8 +197,10 @@ unsigned long read_count(void)
 	spin_unlock(&gblcnt_mutex);
 	return sum;
 }
+//\end{snippet}
 
-void count_init(void)
+//\begin{snippet}[labelbase=ln:count:count_lim_sig:initialization,commandchars=\\\@\$]
+void count_init(void)					//\lnlbl{init:b}
 {
 	struct sigaction sa;
 
@@ -196,7 +211,7 @@ void count_init(void)
 		perror("sigaction");
 		exit(EXIT_FAILURE);
 	}
-}
+}							//\lnlbl{init:e}
 
 void count_register_thread(void)
 {
@@ -220,6 +235,7 @@ void count_unregister_thread(int nthreadsexpected)
 	theftp[idx] = NULL;
 	spin_unlock(&gblcnt_mutex);
 }
+//\end{snippet}
 
 void count_cleanup(void)
 {
count/count.tex +102 -293

512 lines not on this page · raw message

Signature · 1 line
2.7.4
#5 lore raw

PATCH 5/6 count: READ/WRITE_ONCE() tweaks for count_lim_sig

In reply to Akira Yokosawa

From 58412bcf44e848153a8cd3f7eb42fa88be3857a9 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Fri, 12 Oct 2018 23:47:34 +0900
Subject: [PATCH 5/6] count: READ/WRITE_ONCE() tweaks for count_lim_sig

Add READ_ONCE()/WRITE_ONCE()s to comply with the guideline recently expanded in toolsoftrade.

Per-thread variable "counting" is shared with signal handler. Actual values used in this code (0 and 1) won't be affected by load/store tearing, but it should be a good practice to mark the updater in add_count()/sub_count() by WRITE_ONCE(). Reader side in the signal handler doesn't require the marking.

Per-thread variable "count" is updated in fastpaths of add_count()/sub_count(). It is read from read_count() while glbcnt_mutex is held, which has no effect on the update of "count". Such combination requires WRITE_ONCE() on the updater side and READ_ONCE() on the reader side.

Reads of "count" and "countmax" in the "if" statement of add_count()/sub_count() can race with the updates of those per-thread variables in slowpaths. To make the exclusive control by the "theft" variable apparent, move the conditionals involving the reads to "count" and "countmax" to behind the "&&" operators.

---
 CodeSamples/count/count_lim_sig.c | 21 +++++++++++----------
 1 file changed, 11 insertions(+), 10 deletions(-)
CodeSamples/count/count_lim_sig.c +11 -10
index f22bfef..c316426 100644
@@ -113,15 +113,15 @@ int add_count(unsigned long delta)			//\lnlbl{b}
 {
 	int fastpath = 0;
 
-	counting = 1;					//\lnlbl{fast:b}
+	WRITE_ONCE(counting, 1);			//\lnlbl{fast:b}
 	barrier();					//\lnlbl{barrier:1}
-	if (countermax - counter >= delta &&		//\lnlbl{check:b}
-	    READ_ONCE(theft) <= THEFT_REQ) {		//\lnlbl{check:e}
-		counter += delta;			//\lnlbl{add:f}
+	if (READ_ONCE(theft) <= THEFT_REQ &&		//\lnlbl{check:b}
+	    countermax - counter >= delta) {		//\lnlbl{check:e}
+		WRITE_ONCE(counter, counter + delta);	//\lnlbl{add:f}
 		fastpath = 1;				//\lnlbl{fasttaken}
 	}
 	barrier();					//\lnlbl{barrier:2}
-	counting = 0;					//\lnlbl{clearcnt}
+	WRITE_ONCE(counting, 0);			//\lnlbl{clearcnt}
 	barrier();					//\lnlbl{barrier:3}
 	if (READ_ONCE(theft) == THEFT_ACK) {		//\lnlbl{check:ACK}
 		smp_mb();				//\lnlbl{mb}
@@ -152,14 +152,15 @@ int sub_count(unsigned long delta)
 {
 	int fastpath = 0;
 
-	counting = 1;
+	WRITE_ONCE(counting, 1);
 	barrier();
-	if (counter >= delta && theft <= THEFT_REQ) {
-		counter -= delta;
+	if (READ_ONCE(theft) <= THEFT_REQ &&
+	    counter >= delta) {
+		WRITE_ONCE(counter, counter - delta);
 		fastpath = 1;
 	}
 	barrier();
-	counting = 0;
+	WRITE_ONCE(counting, 0);
 	barrier();
 	if (READ_ONCE(theft) == THEFT_ACK) {
 		smp_mb();
@@ -193,7 +194,7 @@ unsigned long read_count(void)
 	sum = globalcount;
 	for_each_thread(t)
 		if (counterp[t] != NULL)
-			sum += *counterp[t];
+			sum += READ_ONCE(*counterp[t]);
 	spin_unlock(&gblcnt_mutex);
 	return sum;
 }
Signature · 1 line
2.7.4
#6 lore raw

PATCH 6/6 toolsoftrade: Proofread newly added sections

In reply to Akira Yokosawa

From fe3b14155fd41569eb5224dd259213908cda4990 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sat, 13 Oct 2018 20:28:09 +0900
Subject: [PATCH 6/6] toolsoftrade: Proofread newly added sections

Miscellaneous fixes and tweaks done while skimming through the expanded sections.

Note on Listings 4.17, 4.22, and 4.25:
Comments of "/* BUGGY!!! */" are added consistently in both Listings 4.17 and 4.22. Listing 4.25 is no longer buggy, so the comments are removed.

---
 toolsoftrade/toolsoftrade.tex | 44 +++++++++++++++++++++----------------------
 1 file changed, 22 insertions(+), 22 deletions(-)
toolsoftrade/toolsoftrade.tex +22 -22
index f198517..f870420 100644
@@ -1764,7 +1764,7 @@ as a series of one-byte loads.
 If some other thread was concurrently setting \co{global_ptr} to
 \co{NULL}, the result might have all but one byte of the pointer
 set to zero, thus forming a ``wild pointer''.
-Stores using such a wild pointer could could corrupt arbitrary
+Stores using such a wild pointer could corrupt arbitrary
 regions of memory, resulting in rare and difficult-to-debug crashes.
 
 Worse yet, on (say) an 8-bit system with 16-bit pointers, the compiler
@@ -1852,16 +1852,16 @@ void shut_it_down(void)
 {
 	status = SHUTTING_DOWN; /* BUGGY!!! */\lnlbl[store:a]
 	start_shutdown();
-	while (!other_task_ready)\lnlbl[loop:b]
+	while (!other_task_ready) /* BUGGY!!! */\lnlbl[loop:b]
 		continue;\lnlbl[loop:e]
 	finish_shutdown();\lnlbl[finish]
-	status = SHUT_DOWN;\lnlbl[store:b]
+	status = SHUT_DOWN; /* BUGGY!!! */\lnlbl[store:b]
 	do_something_else();
 }
 
 void work_until_shut_down(void)
 {
-	while (status != SHUTTING_DOWN)\lnlbl[until:loop:b]
+	while (status != SHUTTING_DOWN) /* BUGGY!!! */\lnlbl[until:loop:b]
 		do_more_work();\lnlbl[until:loop:e]
 	other_task_ready = 1; /* BUGGY!!! */\lnlbl[other:store]
 }
@@ -1887,7 +1887,7 @@ lines~\lnref{until:loop:b} and~\lnref{until:loop:e}, and thus would never set
 would never exit its loop spanning
 lines~\lnref{loop:b} and~\lnref{loop:e}, even if
 the compiler chooses not to fuse the successive loads from
-\co{(!other_task_ready)} on line~\lnref{loop:b}.
+\co{other_task_ready} on line~\lnref{loop:b}.
 
 And there are more problems with the code in
 Listing~\ref{lst:toolsoftrade:C Compilers Can Fuse Stores},
@@ -2030,8 +2030,8 @@ Perhaps the most clear guidance is provided by this non-normative note:
 	that special hardware instructions are required to access
 	the object.
 	See 6.8.1 for detailed semantics.
-	In general, the semantics of volatile are intended to be the
-	same in C ++ as they are in C.
+	In general, the semantics of \co{volatile} are intended to be the
+	same in C++ as they are in C.
 \end{quote}
 
 This wording might be reassuring to those writing low-level code, except
@@ -2068,6 +2068,7 @@ constraints @@@ citation once LinuxMM.html appears @@@:
 	assembly-language instructions.
 	Concurrent code relies on this constraint in order to achieve
 	the desired ordering properties from combinations of volatile
+	accesses and other means discussed in
 	Section~\ref{sec:toolsoftrade:Assembling the Rest of a Solution}.
 \end{enumerate}
 
@@ -2093,11 +2094,11 @@ if (ptr != NULL && ptr < high_address)
 \end{listing}
 
 Using \co{READ_ONCE()} on
-line~~\ref{ln:toolsoftrade:Living Dangerously Early 1990s Style:temp} of
+line~\ref{ln:toolsoftrade:Living Dangerously Early 1990s Style:temp} of
 Listing~\ref{lst:toolsoftrade:Living Dangerously Early 1990s Style}
 avoids invented loads,
 resulting in the code shown in
-List~\ref{lst:toolsoftrade:Avoiding Danger, 2018 Style}.
+Listing~\ref{lst:toolsoftrade:Avoiding Danger, 2018 Style}.
 
 \begin{listing}[tbp]
 \begin{linelabel}[ln:toolsoftrade:Preventing Load Fusing]
@@ -2125,13 +2126,13 @@ void shut_it_down(void)
 	while (!READ_ONCE(other_task_ready)) /* BUGGY!!! */\lnlbl[loop:b]
 		continue;\lnlbl[loop:e]
 	finish_shutdown();\lnlbl[finish]
-	WRITE_ONCE(status, SHUT_DOWN);\lnlbl[store:b]
+	WRITE_ONCE(status, SHUT_DOWN); /* BUGGY!!! */\lnlbl[store:b]
 	do_something_else();
 }
 
 void work_until_shut_down(void)
 {
-	while (READ_ONCE(status) != SHUTTING_DOWN)\lnlbl[until:loop:b]
+	while (READ_ONCE(status) != SHUTTING_DOWN) /* BUGGY!!! */\lnlbl[until:loop:b]
 		do_more_work();\lnlbl[until:loop:e]
 	WRITE_ONCE(other_task_ready, 1); /* BUGGY!!! */\lnlbl[other:store]
 }
@@ -2169,7 +2170,7 @@ Listing~\ref{lst:toolsoftrade:Inviting an Invented Store},
 with the resulting code shown in
 Listing~\ref{lst:toolsoftrade:Disinviting an Invented Store}.
 
-To summarize, the \co{volatile} keyword can prevent prevent load
+To summarize, the \co{volatile} keyword can prevent load
 tearing and store tearing in cases where the loads and stores are
 machine-sized and properly aligned.
 It can also prevent load fusing, store fusing, invented loads, and
@@ -2232,7 +2233,7 @@ void shut_it_down(void)
 	WRITE_ONCE(status, SHUTTING_DOWN);
 	smp_mb(); \lnlbl[mb1]
 	start_shutdown();
-	while (!READ_ONCE(other_task_ready)) /* BUGGY!!! */\lnlbl[loop:b]
+	while (!READ_ONCE(other_task_ready))\lnlbl[loop:b]
 		continue;
 	smp_mb(); \lnlbl[mb2]
 	finish_shutdown();
@@ -2248,7 +2249,7 @@ void work_until_shut_down(void)
 		do_more_work();
 	}
 	smp_mb(); \lnlbl[mb5]
-	WRITE_ONCE(other_task_ready, 1); /* BUGGY!!! */\lnlbl[other:store]
+	WRITE_ONCE(other_task_ready, 1);\lnlbl[other:store]
 }
 \end{VerbatimL}
 \end{linelabel}
@@ -2268,11 +2269,10 @@ prevented store fusing and invention, and
 Listing~\ref{lst:toolsoftrade:Preventing Reordering}
 further prevents the remaining reordering by addition of
 \co{smp_mb()} on
-lines~\ref{ln:toolsoftrade:Preventing Reordering:mb1},
-lines~\ref{ln:toolsoftrade:Preventing Reordering:mb2},
-lines~\ref{ln:toolsoftrade:Preventing Reordering:mb3},
-lines~\ref{ln:toolsoftrade:Preventing Reordering:mb4}, and
-lines~\ref{ln:toolsoftrade:Preventing Reordering:mb5}.
+\begin{lineref}[ln:toolsoftrade:Preventing Reordering]
+lines~\lnref{mb1}, \lnref{mb2}, \lnref{mb3}, \lnref{mb4},
+and~\lnref{mb5}.
+\end{lineref}
 The \co{smp_mb()} macro is similar to \co{barrier()} shown in
 Listing~\ref{lst:toolsoftrade:Compiler Barrier Primitive (for GCC)},
 but with the empty string replaced by a string containing the
@@ -2333,7 +2333,7 @@ cases:
 	lock by a given owning CPU or thread, then all stores must use
 	\co{WRITE_ONCE()} and non-owning CPUs or threads that
 	are not holding the lock must use \co{READ_ONCE()} for loads.
-	The owning CPU or thread may uas plain loads, as may any
+	The owning CPU or thread may use plain loads, as may any
 	CPU or thread holding the lock.
 \item	If a shared variable is only modified while holding a given
 	lock, then all stores must use \co{WRITE_ONCE()}.
@@ -2343,7 +2343,7 @@ cases:
 \item	If a shared variable is only modified by a given owning CPU or
 	thread, then all stores must use \co{WRITE_ONCE()} and non-owning
 	CPUs or threads must use \co{READ_ONCE()} for loads.
-	The owning CPU or thread may used plain loads.
+	The owning CPU or thread may use plain loads.
 \end{enumerate}
 
 In most other cases, loads from and stores to a shared variable must
@@ -2353,7 +2353,7 @@ provide any ordering guarantees.
 See the above
 Section~\ref{sec:toolsoftrade:Assembling the Rest of a Solution} or
 Chapter~\ref{chp:Advanced Synchronization: Memory Ordering}
-information on providing ordering guarantees.
+for information on providing ordering guarantees.
 
 Examples of many of these data-race-avoidance patterns are presented in
 Chapter~\ref{chp:Counting}.
Signature · 1 line
2.7.4
#7 lore raw

[PATCH 7/6] count: Fix typo (missing \lnref)

In reply to Akira Yokosawa

From 8cf8ccf218f2a3b3a15911a6a4619c21627dfe37 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sun, 14 Oct 2018 08:09:49 +0900
Subject: [PATCH 7/6] count: Fix typo (missing \lnref)

---
Paul,

This fixes typo in Patch 4/6 ("count: Employ new scheme for snippet of count_lim_sig").

Thanks, Akira
--

 count/count.tex | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
count/count.tex +1 -1
index d8d60db..4d13394 100644
@@ -2421,7 +2421,7 @@ if (counting) {
 Lines~\lnref{b}-\lnref{e} shows \co{flush_local_count()}, which is called from the
 slowpath to flush all threads' local counts.
 The loop spanning
-lines~\lnref{loop:b}-{loop:e} advances the \co{theft} state for each
+lines~\lnref{loop:b}-\lnref{loop:e} advances the \co{theft} state for each
 thread that has local count, and also sends that thread a signal.
 Line~\lnref{skip} skips any non-existent threads.
 Otherwise, line~\lnref{checkmax} checks to see if the current thread holds any local
Signature · 1 line
2.7.4
#8 lore raw
In reply to Akira Yokosawa
Quoted 6 lines · Akira Yokosawa

Hi Paul,

count_lim_sig.c was a hard one to review for me regarding the usage of READ_ONCE()/WRITE_ONCE(). Patch #5 is my attempt to add several of them. There might be other combination of racy accesses.

Quoted 8 lines

Patches #1--#4 are trivial ones.

Patch #6 is the result of quick review of your recent addition to toolsoftrade. I'm not sure you like the addition of comments "/* BUGGY!!! */" to Lisitngs which look irrelevant to their captions.

Patches #5 and #6 are more likely to need your close look.

It looks good from what I can see, though your patch 6/6 should limit your confidence in this. ;-)

I folded your later 7/6 into 4/6.

Queued and pushed, thank you!!!

Thanx, Paul

Quoted 20 lines

Thanks, Akira
--
Akira Yokosawa (6):
count: Employ new scheme for snippet of count_lim_app
count: Fix uses of READ/WRITE_ONCE() in count_lim_app
count: Employ new scheme for snippet of count_lim_atomic
count: Employ new scheme for snippet of count_lim_sig
count: READ/WRITE_ONCE() tweaks for count_lim_sig
toolsoftrade: Proofread newly added sections

 CodeSamples/count/count_lim_app.c    |  17 +-
 CodeSamples/count/count_lim_atomic.c | 209 ++++----
 CodeSamples/count/count_lim_sig.c    | 159 ++++---
 count/count.tex                      | 892 ++++++++++-------------------------
 toolsoftrade/toolsoftrade.tex        |  44 +-
 5 files changed, 494 insertions(+), 827 deletions(-)
Signature · 1 line
2.7.4