count: Employ new code-snippet scheme (cont.)
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
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
@@ -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
@@ -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
PATCH 2/6 count: Fix uses of READ/WRITE_ONCE() in count_lim_app
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 3/6 count: Employ new scheme for snippet of count_lim_atomic
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 4/6 count: Employ new scheme for snippet of count_lim_sig
In reply to Akira YokosawaFrom 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
@@ -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 3int __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
PATCH 5/6 count: READ/WRITE_ONCE() tweaks for count_lim_sig
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 6/6 toolsoftrade: Proofread newly added sections
In reply to Akira YokosawaFrom 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
@@ -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
[PATCH 7/6] count: Fix typo (missing \lnref)
In reply to Akira YokosawaFrom 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
@@ -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
Paul E. McKenney
AppliedQuoted 6 lines · Akira Yokosawa
Hi Paul,
count_lim_sig.cwas 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 ofcount_lim_app
count: Fix uses of READ/WRITE_ONCE() incount_lim_app
count: Employ new scheme for snippet ofcount_lim_atomic
count: Employ new scheme for snippet ofcount_lim_sig
count: READ/WRITE_ONCE() tweaks forcount_lim_sig
toolsoftrade: Proofread newly added sectionsCodeSamples/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