* [PATCH 0/3] Employ new scheme for code snippets (cont.)
@ 2018-11-25 14:44 Akira Yokosawa
2018-11-25 14:46 ` [PATCH 1/3] owned: Employ new snippet scheme Akira Yokosawa
2018-11-25 17:01 ` [PATCH 0/3] Employ new scheme for code snippets (cont.) Paul E. McKenney
0 siblings, 2 replies; 7+ messages in thread
From: Akira Yokosawa @ 2018-11-25 14:44 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From 4ebe85f38ed5f0e003847854b64bc8773bec8ebb Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 25 Nov 2018 23:30:16 +0900
Subject: [PATCH 0/3] Employ new scheme (cont.)
Hi Paul,
This is a set of patches to further apply the new scheme for snippets in
chapters "owned" and "defer". Further updates in "defer" will be submitted
shortly.
Thanks, Akira
--
Akira Yokosawa (3):
owned: Employ new snippet scheme
defer: Employ new snippet scheme for route_seq.c
defer: Employ new scheme for snippets of route_refcnt.c
CodeSamples/defer/route_refcnt.c | 67 +++++++++--------
CodeSamples/defer/route_seq.c | 42 +++++------
defer/defer.tex | 76 ++++----------------
defer/refcnt.tex | 152 +++++++++------------------------------
owned/owned.tex | 19 ++---
5 files changed, 115 insertions(+), 241 deletions(-)
--
2.7.4
^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH 1/3] owned: Employ new snippet scheme
2018-11-25 14:44 [PATCH 0/3] Employ new scheme for code snippets (cont.) Akira Yokosawa
@ 2018-11-25 14:46 ` Akira Yokosawa
2018-11-25 14:48 ` [PATCH 2/3] defer: Employ new snippet scheme for route_seq.c Akira Yokosawa
2018-11-25 14:50 ` [PATCH 3/3] defer: Employ new scheme for snippets of route_refcnt.c Akira Yokosawa
2018-11-25 17:01 ` [PATCH 0/3] Employ new scheme for code snippets (cont.) Paul E. McKenney
1 sibling, 2 replies; 7+ messages in thread
From: Akira Yokosawa @ 2018-11-25 14:46 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From c28ee5d0a127fefa6e9e4bd2156039c0e5e6653e Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sat, 24 Nov 2018 21:26:26 +0900
Subject: [PATCH 1/3] owned: Employ new snippet scheme
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
owned/owned.tex | 19 +++++++------------
1 file changed, 7 insertions(+), 12 deletions(-)
diff --git a/owned/owned.tex b/owned/owned.tex
index d584e82..d0063d3 100644
--- a/owned/owned.tex
+++ b/owned/owned.tex
@@ -57,18 +57,13 @@ first-class citizen.
Section~\ref{sec:toolsoftrade:Scripting Languages}
introduced the following example:
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\scriptsize
-\begin{verbatim}
- 1 compute_it 1 > compute_it.1.out &
- 2 compute_it 2 > compute_it.2.out &
- 3 wait
- 4 cat compute_it.1.out
- 5 cat compute_it.2.out
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\begin{VerbatimN}
+compute_it 1 > compute_it.1.out &
+compute_it 2 > compute_it.2.out &
+wait
+cat compute_it.1.out
+cat compute_it.2.out
+\end{VerbatimN}
This example runs two instances of the \co{compute_it} program in
parallel, as separate processes that do not share memory.
--
2.7.4
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [PATCH 2/3] defer: Employ new snippet scheme for route_seq.c
2018-11-25 14:46 ` [PATCH 1/3] owned: Employ new snippet scheme Akira Yokosawa
@ 2018-11-25 14:48 ` Akira Yokosawa
2018-11-25 14:50 ` [PATCH 3/3] defer: Employ new scheme for snippets of route_refcnt.c Akira Yokosawa
1 sibling, 0 replies; 7+ messages in thread
From: Akira Yokosawa @ 2018-11-25 14:48 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From 9bf0f2fcf35a1a627ca92204dc6dcda316616c71 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 25 Nov 2018 21:26:58 +0900
Subject: [PATCH 2/3] defer: Employ new snippet scheme for route_seq.c
Also mention the source file name.
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
CodeSamples/defer/route_seq.c | 42 ++++++++++++------------
defer/defer.tex | 76 +++++++++----------------------------------
2 files changed, 37 insertions(+), 81 deletions(-)
diff --git a/CodeSamples/defer/route_seq.c b/CodeSamples/defer/route_seq.c
index 042aed0..535ed09 100644
--- a/CodeSamples/defer/route_seq.c
+++ b/CodeSamples/defer/route_seq.c
@@ -23,18 +23,19 @@
#include "../api.h"
/* Route-table entry to be included in the routing list. */
-struct route_entry {
+//\begin{snippet}[labelbase=ln:defer:route_seq:lookup_add_del,commandchars=\\\[\]]
+struct route_entry { //\lnlbl{entry:b}
struct cds_list_head re_next;
unsigned long addr;
unsigned long iface;
-};
-
-CDS_LIST_HEAD(route_list);
-
-/*
- * Look up a route entry, return the corresponding interface.
- */
-unsigned long route_lookup(unsigned long addr)
+}; //\lnlbl{entry:e}
+ //\fcvexclude
+CDS_LIST_HEAD(route_list); //\lnlbl{entry:header}
+
+/* \fcvexclude
+ * Look up a route entry, return the corresponding interface. \fcvexclude
+ */ //\fcvexclude
+unsigned long route_lookup(unsigned long addr) //\lnlbl{lookup:b}
{
struct route_entry *rep;
unsigned long ret;
@@ -46,12 +47,12 @@ unsigned long route_lookup(unsigned long addr)
}
}
return ULONG_MAX;
-}
+} //\lnlbl{lookup:e}
-/*
- * Add an element to the route table.
- */
-int route_add(unsigned long addr, unsigned long interface)
+/* \fcvexclude
+ * Add an element to the route table. \fcvexclude
+ */ //\fcvexclude
+int route_add(unsigned long addr, unsigned long interface)//\lnlbl{add:b}
{
struct route_entry *rep;
@@ -62,12 +63,12 @@ int route_add(unsigned long addr, unsigned long interface)
rep->iface = interface;
cds_list_add(&rep->re_next, &route_list);
return 0;
-}
+} //\lnlbl{add:e}
-/*
- * Remove the specified element from the route table.
- */
-int route_del(unsigned long addr)
+/* \fcvexclude
+ * Remove the specified element from the route table. \fcvexclude
+ */ //\fcvexclude
+int route_del(unsigned long addr) //\lnlbl{del:b}
{
struct route_entry *rep;
@@ -79,7 +80,8 @@ int route_del(unsigned long addr)
}
}
return -ENOENT;
-}
+} //\lnlbl{del:e}
+//\end{snippet}
/*
* Clear all elements from the route table.
diff --git a/defer/defer.tex b/defer/defer.tex
index e396dbf..69437a3 100644
--- a/defer/defer.tex
+++ b/defer/defer.tex
@@ -69,80 +69,34 @@ list to evaluate a number of read-mostly synchronization techniques.
\end{figure}
\begin{listing}[tb]
-{ \scriptsize
-\begin{verbbox}
- 1 struct route_entry {
- 2 struct cds_list_head re_next;
- 3 unsigned long addr;
- 4 unsigned long iface;
- 5 };
- 6 CDS_LIST_HEAD(route_list);
- 7
- 8 unsigned long route_lookup(unsigned long addr)
- 9 {
-10 struct route_entry *rep;
-11 unsigned long ret;
-12
-13 cds_list_for_each_entry(rep,
-14 &route_list, re_next) {
-15 if (rep->addr == addr) {
-16 ret = rep->iface;
-17 return ret;
-18 }
-19 }
-20 return ULONG_MAX;
-21 }
-22
-23 int route_add(unsigned long addr,
-24 unsigned long interface)
-25 {
-26 struct route_entry *rep;
-27
-28 rep = malloc(sizeof(*rep));
-29 if (!rep)
-30 return -ENOMEM;
-31 rep->addr = addr;
-32 rep->iface = interface;
-33 cds_list_add(&rep->re_next, &route_list);
-34 return 0;
-35 }
-36
-37 int route_del(unsigned long addr)
-38 {
-39 struct route_entry *rep;
-40
-41 cds_list_for_each_entry(rep,
-42 &route_list, re_next) {
-43 if (rep->addr == addr) {
-44 cds_list_del(&rep->re_next);
-45 free(rep);
-46 return 0;
-47 }
-48 }
-49 return -ENOENT;
-50 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/defer/route_seq@lookup_add_del.fcv}
\caption{Sequential Pre-BSD Routing Table}
\label{lst:defer:Sequential Pre-BSD Routing Table}
\end{listing}
-Listing~\ref{lst:defer:Sequential Pre-BSD Routing Table}
+Listing~\ref{lst:defer:Sequential Pre-BSD Routing Table} (\path{route_sec.c})
shows a simple single-threaded implementation corresponding to
Figure~\ref{fig:defer:Pre-BSD Packet Routing List}.
-Lines~1-5 define a \co{route_entry} structure and line~6 defines
+\begin{lineref}[ln:defer:route_seq:lookup_add_del:entry]
+Lines~\lnref{b}-\lnref{e} define a \co{route_entry} structure and
+line~\lnref{header} defines
the \co{route_list} header.
-Lines~8-21 define \co{route_lookup()}, which sequentially searches
+\end{lineref}
+\begin{lineref}[ln:defer:route_seq:lookup_add_del:lookup]
+Lines~\lnref{b}-\lnref{e} define \co{route_lookup()}, which sequentially searches
\co{route_list}, returning the corresponding \co{->iface}, or
\co{ULONG_MAX} if there is no such route entry.
-Lines~23-35 define \co{route_add()}, which allocates a
+\end{lineref}
+\begin{lineref}[ln:defer:route_seq:lookup_add_del:add]
+Lines~\lnref{b}-\lnref{e} define \co{route_add()}, which allocates a
\co{route_entry} structure, initializes it, and adds it to the
list, returning \co{-ENOMEM} in case of memory-allocation failure.
-Finally, lines~37-50 define \co{route_del()}, which removes and
+\end{lineref}
+\begin{lineref}[ln:defer:route_seq:lookup_add_del:del]
+Finally, lines~\lnref{b}-\lnref{e} define \co{route_del()}, which removes and
frees the specified \co{route_entry} structure if it exists,
or returns \co{-ENOENT} otherwise.
+\end{lineref}
This single-threaded implementation serves as a prototype for the various
concurrent implementations in this chapter, and also as an estimate of
--
2.7.4
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [PATCH 3/3] defer: Employ new scheme for snippets of route_refcnt.c
2018-11-25 14:46 ` [PATCH 1/3] owned: Employ new snippet scheme Akira Yokosawa
2018-11-25 14:48 ` [PATCH 2/3] defer: Employ new snippet scheme for route_seq.c Akira Yokosawa
@ 2018-11-25 14:50 ` Akira Yokosawa
1 sibling, 0 replies; 7+ messages in thread
From: Akira Yokosawa @ 2018-11-25 14:50 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From 4ebe85f38ed5f0e003847854b64bc8773bec8ebb Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 25 Nov 2018 23:27:25 +0900
Subject: [PATCH 3/3] defer: Employ new scheme for snippets of route_refcnt.c
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
CodeSamples/defer/route_refcnt.c | 67 +++++++++--------
defer/refcnt.tex | 152 +++++++++------------------------------
2 files changed, 71 insertions(+), 148 deletions(-)
diff --git a/CodeSamples/defer/route_refcnt.c b/CodeSamples/defer/route_refcnt.c
index 8a48faf..4833919 100644
--- a/CodeSamples/defer/route_refcnt.c
+++ b/CodeSamples/defer/route_refcnt.c
@@ -22,26 +22,27 @@
#include "../api.h"
/* Route-table entry to be included in the routing list. */
+//\begin{snippet}[labelbase=ln:defer:route_refcnt:lookup,commandchars=\\\[\]]
struct route_entry {
- atomic_t re_refcnt;
+ atomic_t re_refcnt; //\lnlbl{entry:refcnt}
struct route_entry *re_next;
unsigned long addr;
unsigned long iface;
- int re_freed;
+ int re_freed; //\lnlbl{entry:freed}
};
-
+ //\fcvexclude
struct route_entry route_list;
-DEFINE_SPINLOCK(routelock);
+DEFINE_SPINLOCK(routelock); //\lnlbl{entry:routelock}
-static void re_free(struct route_entry *rep)
+static void re_free(struct route_entry *rep) //\lnlbl{re_free:b}
{
WRITE_ONCE(rep->re_freed, 1);
free(rep);
-}
+} //\lnlbl{re_free:e}
-/*
- * Look up a route entry, return the corresponding interface.
- */
+/* \fcvexclude
+ * Look up a route entry, return the corresponding interface. \fcvexclude
+ */ //\fcvexclude
unsigned long route_lookup(unsigned long addr)
{
int old;
@@ -54,23 +55,24 @@ retry:
repp = &route_list.re_next;
rep = NULL;
do {
- if (rep && atomic_dec_and_test(&rep->re_refcnt))
- re_free(rep);
+ if (rep && atomic_dec_and_test(&rep->re_refcnt)) //\lnlbl{lookup:relprev:b}
+ re_free(rep); //\lnlbl{lookup:relprev:e}
rep = READ_ONCE(*repp);
- if (rep == NULL)
+ if (rep == NULL) //\lnlbl{lookup:check_NULL}
return ULONG_MAX;
-
- /* Acquire a reference if the count is non-zero. */
- do {
- if (READ_ONCE(rep->re_freed))
- abort();
+ //\fcvexclude
+ /* Acquire a reference if the count is non-zero. */ //\fcvexclude
+ do { //\lnlbl{lookup:acq:b}
+ if (READ_ONCE(rep->re_freed)) //\lnlbl{lookup:check_uaf}
+ abort(); //\lnlbl{lookup:abort}
old = atomic_read(&rep->re_refcnt);
if (old <= 0)
goto retry;
new = old + 1;
- } while (atomic_cmpxchg(&rep->re_refcnt, old, new) != old);
-
- /* Advance to next. */
+ } while (atomic_cmpxchg(&rep->re_refcnt,
+ old, new) != old); //\lnlbl{lookup:acq:e}
+ //\fcvexclude
+ /* Advance to next. */ //\fcvexclude
repp = &rep->re_next;
} while (rep->addr != addr);
ret = rep->iface;
@@ -78,10 +80,12 @@ retry:
re_free(rep);
return ret;
}
+//\end{snippet}
/*
* Add an element to the route table.
*/
+//\begin{snippet}[labelbase=ln:defer:route_refcnt:add_del,commandchars=\\\[\]]
int route_add(unsigned long addr, unsigned long interface)
{
struct route_entry *rep;
@@ -92,23 +96,23 @@ int route_add(unsigned long addr, unsigned long interface)
atomic_set(&rep->re_refcnt, 1);
rep->addr = addr;
rep->iface = interface;
- spin_lock(&routelock);
+ spin_lock(&routelock); //\lnlbl{acq1}
rep->re_next = route_list.re_next;
- rep->re_freed = 0;
+ rep->re_freed = 0; //\lnlbl{init:freed}
route_list.re_next = rep;
- spin_unlock(&routelock);
+ spin_unlock(&routelock); //\lnlbl{rel1}
return 0;
}
-/*
- * Remove the specified element from the route table.
- */
+/* \fcvexclude
+ * Remove the specified element from the route table. \fcvexclude
+ */ //\fcvexclude
int route_del(unsigned long addr)
{
struct route_entry *rep;
struct route_entry **repp;
- spin_lock(&routelock);
+ spin_lock(&routelock); //\lnlbl{acq2}
repp = &route_list.re_next;
for (;;) {
rep = *repp;
@@ -116,16 +120,17 @@ int route_del(unsigned long addr)
break;
if (rep->addr == addr) {
*repp = rep->re_next;
- spin_unlock(&routelock);
- if (atomic_dec_and_test(&rep->re_refcnt))
- re_free(rep);
+ spin_unlock(&routelock); //\lnlbl{rel2}
+ if (atomic_dec_and_test(&rep->re_refcnt)) //\lnlbl{re_free:b}
+ re_free(rep); //\lnlbl{re_free:e}
return 0;
}
repp = &rep->re_next;
}
- spin_unlock(&routelock);
+ spin_unlock(&routelock); //\lnlbl{rel3}
return -ENOENT;
}
+//\end{snippet}
/*
* Clear all elements from the route table.
diff --git a/defer/refcnt.tex b/defer/refcnt.tex
index ebf9111..1ad5f97 100644
--- a/defer/refcnt.tex
+++ b/defer/refcnt.tex
@@ -4,115 +4,13 @@
\label{sec:defer:Reference Counting}
\begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
- 1 struct route_entry { /* BUGGY!!! */
- 2 atomic_t re_refcnt;
- 3 struct route_entry *re_next;
- 4 unsigned long addr;
- 5 unsigned long iface;
- 6 int re_freed;
- 7 };
- 8 struct route_entry route_list;
- 9 DEFINE_SPINLOCK(routelock);
-10
-11 static void re_free(struct route_entry *rep)
-12 {
-13 WRITE_ONCE(rep->re_freed, 1);
-14 free(rep);
-15 }
-16
-17 unsigned long route_lookup(unsigned long addr)
-18 {
-19 int old;
-20 int new;
-21 struct route_entry *rep;
-22 struct route_entry **repp;
-23 unsigned long ret;
-24
-25 retry:
-26 repp = &route_list.re_next;
-27 rep = NULL;
-28 do {
-29 if (rep &&
-30 atomic_dec_and_test(&rep->re_refcnt))
-31 re_free(rep);
-32 rep = READ_ONCE(*repp);
-33 if (rep == NULL)
-34 return ULONG_MAX;
-35 do {
-36 if (READ_ONCE(rep->re_freed))
-37 abort();
-38 old = atomic_read(&rep->re_refcnt);
-39 if (old <= 0)
-40 goto retry;
-41 new = old + 1;
-42 } while (atomic_cmpxchg(&rep->re_refcnt,
-43 old, new) != old);
-44 repp = &rep->re_next;
-45 } while (rep->addr != addr);
-46 ret = rep->iface;
-47 if (atomic_dec_and_test(&rep->re_refcnt))
-48 re_free(rep);
-49 return ret;
-50 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/defer/route_refcnt@lookup.fcv}
\caption{Reference-Counted Pre-BSD Routing Table Lookup (BUGGY!!!)}
\label{lst:defer:Reference-Counted Pre-BSD Routing Table Lookup}
\end{listing}
\begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
- 1 int route_add(unsigned long addr, /* BUGGY!!! */
- 2 unsigned long interface)
- 3 {
- 4 struct route_entry *rep;
- 5
- 6 rep = malloc(sizeof(*rep));
- 7 if (!rep)
- 8 return -ENOMEM;
- 9 atomic_set(&rep->re_refcnt, 1);
-10 rep->addr = addr;
-11 rep->iface = interface;
-12 spin_lock(&routelock);
-13 rep->re_next = route_list.re_next;
-14 rep->re_freed = 0;
-15 route_list.re_next = rep;
-16 spin_unlock(&routelock);
-17 return 0;
-18 }
-19
-20 int route_del(unsigned long addr)
-21 {
-22 struct route_entry *rep;
-23 struct route_entry **repp;
-24
-25 spin_lock(&routelock);
-26 repp = &route_list.re_next;
-27 for (;;) {
-28 rep = *repp;
-29 if (rep == NULL)
-30 break;
-31 if (rep->addr == addr) {
-32 *repp = rep->re_next;
-33 spin_unlock(&routelock);
-34 if (atomic_dec_and_test(&rep->re_refcnt))
-35 re_free(rep);
-36 return 0;
-37 }
-38 repp = &rep->re_next;
-39 }
-40 spin_unlock(&routelock);
-41 return -ENOENT;
-42 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/defer/route_refcnt@add_del.fcv}
\caption{Reference-Counted Pre-BSD Routing Table Add/Delete (BUGGY!!!)}
\label{lst:defer:Reference-Counted Pre-BSD Routing Table Add/Delete}
\end{listing}
@@ -143,18 +41,28 @@ shown in
Listing~\ref{lst:defer:Sequential Pre-BSD Routing Table},
only the differences will be discussed.
+\begin{lineref}[ln:defer:route_refcnt:lookup:entry]
Starting with
Listing~\ref{lst:defer:Reference-Counted Pre-BSD Routing Table Lookup},
-line~2 adds the actual reference counter, line~6 adds a \co{->re_freed}
-use-after-free check field, line~9 adds the \co{routelock} that will
+line~\lnref{refcnt} adds the actual reference counter,
+line~\lnref{freed} adds a \co{->re_freed}
+use-after-free check field,
+line~\lnref{routelock} adds the \co{routelock} that will
be used to synchronize concurrent updates,
-and lines~11-15 add \co{re_free()}, which sets
+\end{lineref}
+\begin{lineref}[ln:defer:route_refcnt:lookup:re_free]
+and lines~\lnref{b}-\lnref{e} add \co{re_free()}, which sets
\co{->re_freed}, enabling \co{route_lookup()} to check for
use-after-free bugs.
-In \co{route_lookup()} itself, lines~29-31 release the reference
+\end{lineref}
+\begin{lineref}[ln:defer:route_refcnt:lookup:lookup]
+In \co{route_lookup()} itself,
+lines~\lnref{relprev:b}-\lnref{relprev:e} release the reference
count of the prior element and free it if the count becomes zero,
-and lines~35-43 acquire a reference on the new element, with lines~36
-and~37 performing the use-after-free check.
+and lines~\lnref{acq:b}-\lnref{acq:e} acquire a reference on the new element,
+with lines~\lnref{check_uaf}
+and~\lnref{abort} performing the use-after-free check.
+\end{lineref}
\QuickQuiz{}
Why bother with a use-after-free check?
@@ -174,12 +82,16 @@ and~37 performing the use-after-free check.
of increasing the probability of finding bugs.
} \QuickQuizEnd
+\begin{lineref}[ln:defer:route_refcnt:add_del]
In Listing~\ref{lst:defer:Reference-Counted Pre-BSD Routing Table Add/Delete},
-lines~12, 16, 25, 33, and~40 introduce locking to synchronize
+lines~\lnref{acq1}, \lnref{rel1}, \lnref{acq2}, \lnref{rel2},
+and~\lnref{rel3} introduce locking to synchronize
concurrent updates.
-Line~14 initializes the \co{->re_freed} use-after-free-check field,
-and finally lines~34-35 invoke \co{re_free()} if the new value of
+Line~\lnref{init:freed} initializes the \co{->re_freed} use-after-free-check field,
+and finally lines~\lnref{re_free:b}-\lnref{re_free:e} invoke
+\co{re_free()} if the new value of
the reference count is zero.
+\end{lineref}
\QuickQuiz{}
Why doesn't \co{route_del()} in
@@ -249,7 +161,8 @@ But it gets worse.
Running multiple updater threads repeatedly invoking
\co{route_add()} and \co{route_del()} will quickly encounter the
-\co{abort()} statement on line~37 of
+\co{abort()} statement on
+line~\ref{ln:defer:route_refcnt:lookup:lookup:abort} of
Listing~\ref{lst:defer:Reference-Counted Pre-BSD Routing Table Lookup},
which indicates a use-after-free bug.
This in turn means that the reference counts are not only profoundly
@@ -260,8 +173,10 @@ One sequence of events leading to the use-after-free bug is as follows,
given the list shown in
Figure~\ref{fig:defer:Pre-BSD Packet Routing List}:
+\begin{lineref}[ln:defer:route_refcnt:lookup]
\begin{enumerate}
-\item Thread~A looks up address~42, reaching line~33 of
+\item Thread~A looks up address~42, reaching
+ line~\lnref{lookup:check_NULL} of
\co{route_lookup()} in
Listing~\ref{lst:defer:Reference-Counted Pre-BSD Routing Table Lookup}.
In other words, Thread~A has a pointer to the first element,
@@ -273,10 +188,13 @@ Figure~\ref{fig:defer:Pre-BSD Packet Routing List}:
field was equal to the value one, it invokes
\co{re_free()} to set the \co{->re_freed} field and to free the entry.
\item Thread~A continues execution of \co{route_lookup()}.
- Its \co{rep} pointer is non-\co{NULL}, but line~36 sees that
- its \co{->re_freed} field is non-zero, so line~37 invokes
+ Its \co{rep} pointer is non-\co{NULL}, but
+ line~\lnref{lookup:check_uaf} sees that
+ its \co{->re_freed} field is non-zero,
+ so line~\lnref{lookup:abort} invokes
\co{abort()}.
\end{enumerate}
+\end{lineref}
The problem is that the reference count is located in the object
to be protected, but that means that there is no protection during
--
2.7.4
^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [PATCH 0/3] Employ new scheme for code snippets (cont.)
2018-11-25 14:44 [PATCH 0/3] Employ new scheme for code snippets (cont.) Akira Yokosawa
2018-11-25 14:46 ` [PATCH 1/3] owned: Employ new snippet scheme Akira Yokosawa
@ 2018-11-25 17:01 ` Paul E. McKenney
2018-11-25 22:07 ` Akira Yokosawa
1 sibling, 1 reply; 7+ messages in thread
From: Paul E. McKenney @ 2018-11-25 17:01 UTC (permalink / raw)
To: Akira Yokosawa; +Cc: perfbook
On Sun, Nov 25, 2018 at 11:44:41PM +0900, Akira Yokosawa wrote:
> >From 4ebe85f38ed5f0e003847854b64bc8773bec8ebb Mon Sep 17 00:00:00 2001
> From: Akira Yokosawa <akiyks@gmail.com>
> Date: Sun, 25 Nov 2018 23:30:16 +0900
> Subject: [PATCH 0/3] Employ new scheme (cont.)
>
> Hi Paul,
>
> This is a set of patches to further apply the new scheme for snippets in
> chapters "owned" and "defer". Further updates in "defer" will be submitted
> shortly.
Good stuff, applied, thank you!
I also fixed a filename typo (my fault, not yours) and expanded a bit
on the topic of mechanical reference counting.
Thanx, Paul
> Thanks, Akira
> --
> Akira Yokosawa (3):
> owned: Employ new snippet scheme
> defer: Employ new snippet scheme for route_seq.c
> defer: Employ new scheme for snippets of route_refcnt.c
>
> CodeSamples/defer/route_refcnt.c | 67 +++++++++--------
> CodeSamples/defer/route_seq.c | 42 +++++------
> defer/defer.tex | 76 ++++----------------
> defer/refcnt.tex | 152 +++++++++------------------------------
> owned/owned.tex | 19 ++---
> 5 files changed, 115 insertions(+), 241 deletions(-)
>
> --
> 2.7.4
>
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH 0/3] Employ new scheme for code snippets (cont.)
2018-11-25 17:01 ` [PATCH 0/3] Employ new scheme for code snippets (cont.) Paul E. McKenney
@ 2018-11-25 22:07 ` Akira Yokosawa
2018-11-25 22:39 ` Paul E. McKenney
0 siblings, 1 reply; 7+ messages in thread
From: Akira Yokosawa @ 2018-11-25 22:07 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
On 2018/11/25 09:01:59 -0800, Paul E. McKenney wrote:
> On Sun, Nov 25, 2018 at 11:44:41PM +0900, Akira Yokosawa wrote:
>> >From 4ebe85f38ed5f0e003847854b64bc8773bec8ebb Mon Sep 17 00:00:00 2001
>> From: Akira Yokosawa <akiyks@gmail.com>
>> Date: Sun, 25 Nov 2018 23:30:16 +0900
>> Subject: [PATCH 0/3] Employ new scheme (cont.)
>>
>> Hi Paul,
>>
>> This is a set of patches to further apply the new scheme for snippets in
>> chapters "owned" and "defer". Further updates in "defer" will be submitted
>> shortly.
>
> Good stuff, applied, thank you!
>
> I also fixed a filename typo (my fault, not yours)
Well, it was *my* typo in 2/3 of the patch set. (There was no mention
of the file name.)
Thank you for catching it!
Akira
> and expanded a bit
> on the topic of mechanical reference counting.
>
> Thanx, Paul
>
>> Thanks, Akira
>> --
>> Akira Yokosawa (3):
>> owned: Employ new snippet scheme
>> defer: Employ new snippet scheme for route_seq.c
>> defer: Employ new scheme for snippets of route_refcnt.c
>>
>> CodeSamples/defer/route_refcnt.c | 67 +++++++++--------
>> CodeSamples/defer/route_seq.c | 42 +++++------
>> defer/defer.tex | 76 ++++----------------
>> defer/refcnt.tex | 152 +++++++++------------------------------
>> owned/owned.tex | 19 ++---
>> 5 files changed, 115 insertions(+), 241 deletions(-)
>>
>> --
>> 2.7.4
>>
>
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH 0/3] Employ new scheme for code snippets (cont.)
2018-11-25 22:07 ` Akira Yokosawa
@ 2018-11-25 22:39 ` Paul E. McKenney
0 siblings, 0 replies; 7+ messages in thread
From: Paul E. McKenney @ 2018-11-25 22:39 UTC (permalink / raw)
To: Akira Yokosawa; +Cc: perfbook
On Mon, Nov 26, 2018 at 07:07:12AM +0900, Akira Yokosawa wrote:
> On 2018/11/25 09:01:59 -0800, Paul E. McKenney wrote:
> > On Sun, Nov 25, 2018 at 11:44:41PM +0900, Akira Yokosawa wrote:
> >> >From 4ebe85f38ed5f0e003847854b64bc8773bec8ebb Mon Sep 17 00:00:00 2001
> >> From: Akira Yokosawa <akiyks@gmail.com>
> >> Date: Sun, 25 Nov 2018 23:30:16 +0900
> >> Subject: [PATCH 0/3] Employ new scheme (cont.)
> >>
> >> Hi Paul,
> >>
> >> This is a set of patches to further apply the new scheme for snippets in
> >> chapters "owned" and "defer". Further updates in "defer" will be submitted
> >> shortly.
> >
> > Good stuff, applied, thank you!
> >
> > I also fixed a filename typo (my fault, not yours)
>
> Well, it was *my* typo in 2/3 of the patch set. (There was no mention
> of the file name.)
True enough. My typo was instead leaving it out completely.
> Thank you for catching it!
And you! ;-)
Thanx, Paul
> Akira
>
> > and expanded a bit
> > on the topic of mechanical reference counting.
> >
> > Thanx, Paul
> >
> >> Thanks, Akira
> >> --
> >> Akira Yokosawa (3):
> >> owned: Employ new snippet scheme
> >> defer: Employ new snippet scheme for route_seq.c
> >> defer: Employ new scheme for snippets of route_refcnt.c
> >>
> >> CodeSamples/defer/route_refcnt.c | 67 +++++++++--------
> >> CodeSamples/defer/route_seq.c | 42 +++++------
> >> defer/defer.tex | 76 ++++----------------
> >> defer/refcnt.tex | 152 +++++++++------------------------------
> >> owned/owned.tex | 19 ++---
> >> 5 files changed, 115 insertions(+), 241 deletions(-)
> >>
> >> --
> >> 2.7.4
> >>
> >
>
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2018-11-26 9:31 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-11-25 14:44 [PATCH 0/3] Employ new scheme for code snippets (cont.) Akira Yokosawa
2018-11-25 14:46 ` [PATCH 1/3] owned: Employ new snippet scheme Akira Yokosawa
2018-11-25 14:48 ` [PATCH 2/3] defer: Employ new snippet scheme for route_seq.c Akira Yokosawa
2018-11-25 14:50 ` [PATCH 3/3] defer: Employ new scheme for snippets of route_refcnt.c Akira Yokosawa
2018-11-25 17:01 ` [PATCH 0/3] Employ new scheme for code snippets (cont.) Paul E. McKenney
2018-11-25 22:07 ` Akira Yokosawa
2018-11-25 22:39 ` Paul E. McKenney
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.