markobjtemplate.tex

This approach, suggested off-list by JF Bastien, creates a
\co{depending_ptr}\footnote{
	Arbitrarily chosen name with no Google hits.}
template to which a pointer-like type is passed.
This approach allows implementers considerable freedom, as they can
hook into the \co{->} and \co{*} if need be, and also use the C++
\co{delete} keyword to prohibit problematic operations.
Implementations that might nevertheless carry out aggressive
optimizations that might break dependencies even for the non-problematic
operations might need to implement this template class in a manner
similar to the atomics template classes.

This approach would need to be augmented with a non-template solution
for C, for example, the object-modifier approach from
Section~\ref{sec:Object Modifier}.
Implementations that support both C and C++ would presumably relate
Section~\ref{sec:Object Modifier}'s
keyword to the templates in this section in a manner similar to
that used for atomics.

\begin{figure}[tbp]
{ \scriptsize
\begin{verbatim}
 1 template<typename T>
 2 class depending_ptr {
 3 public:
 4   typedef T* pointer;
 5   typedef T element_type;
 6
 7   // Constructors
 8   constexpr depending_ptr() noexcept;
 9   explicit depending_ptr(T* v) noexcept;
10   depending_ptr(nullptr_t) noexcept;
11   depending_ptr(const depending_ptr &d) noexcept;
12   depending_ptr(const depending_ptr &&d) noexcept;
13
14   // Assignment
15   depending_ptr& operator=(pointer p) noexcept;
16   depending_ptr& operator=(const depending_ptr &d) noexcept;
17   depending_ptr& operator=(const depending_ptr &&d) noexcept;
18   depending_ptr& operator=(nullptr_t) noexcept;
19
20   // Modifiers
21   void swap(depending_ptr& d) noexcept;
22
23   // Unary operators
24   // No operator!
25   // No prefix bitwise complement operator
26   element_type operator*() noexcept;
27   pointer operator->() noexcept;
28   depending_ptr<element_type> operator++();
29   depending_ptr<element_type> operator++(int);
30   depending_ptr<element_type> operator--();
31   depending_ptr<element_type> operator--(int);
32   pointer get() const noexcept;
33   explicit operator bool();
34   element_type operator[](size_t);
35
36   // Binary relational operators
37   bool operator==(depending_ptr v) noexcept;
38   bool operator!=(depending_ptr v) noexcept;
39   bool operator>(depending_ptr v) noexcept;
40   bool operator>=(depending_ptr v) noexcept;
41   bool operator<(depending_ptr v) noexcept;
42   bool operator<=(depending_ptr v) noexcept;
43   bool operator==(pointer v) noexcept;
44   bool operator!=(pointer v) noexcept;
45   bool operator>(pointer v) noexcept;
46   bool operator>=(pointer v) noexcept;
47   bool operator<(pointer v) noexcept;
48   bool operator<=(pointer v) noexcept;
49
50   // Other binary operators
51   depending_ptr<T> operator+(size_t idx);
52   depending_ptr<T> operator+=(size_t idx);
53   depending_ptr<T> operator-(size_t idx);
54   depending_ptr<T> operator-=(size_t idx);
55
56 private:
57   pointer dp_rep;
58 };
\end{verbatim}
}
\caption{Template: Declaration}
\label{fig:Template: Declaration}
\end{figure}

\begin{figure}[tbp]
{ \scriptsize
\begin{verbatim}
 1   bool pointer_cmp_eq_dep(void *p, void *q) noexcept;
 2   bool pointer_cmp_ne_dep(void *p, void *q) noexcept;
 3   bool pointer_cmp_gt_dep(void *p, void *q) noexcept;
 4   bool pointer_cmp_ge_dep(void *p, void *q) noexcept;
 5   bool pointer_cmp_lt_dep(void *p, void *q) noexcept;
 6   bool pointer_cmp_le_dep(void *p, void *q) noexcept;
\end{verbatim}
}
\caption{Dependency-Preserving Comparisons}
\label{fig:Dependency-Preserving Comparisons}
\end{figure}

\begin{figure}[tbp]
{ \scriptsize
\begin{verbatim}
 1 template<typename T>
 2 depending_ptr<T> rcu_consume(std::atomic<T*> *p)
 3 {
 4   volatile std::atomic<typename
 5            depending_ptr<T>::pointer> *q = p;
 6   // Change to memory_order_consume once it is fixed
 7   depending_ptr<T> temp(q->load(std::memory_order_relaxed));
 8
 9   return temp;
10 }
11
12 template<typename T>
13 depending_ptr<T> rcu_consume(T *p)
14 {
15   // Alternatively, could cast p to volatile atomic...
16   depending_ptr<T> temp(*(T *volatile *)&p);
17
18   return temp;
19 }
20
21 template<typename T>
22 T* rcu_store_release(std::atomic<T*> *p, T *v)
23 {
24   p->store(v, std::memory_order_release);
25   return v;
26 }
27
28 template<typename T>
29 T* rcu_store_release(T **p, T *v)
30 {
31   // Alternatively, could cast p to volatile atomic...
32   atomic_thread_fence(std::memory_order_release);
33   *((volatile T **)p) = v;
34   return v;
35 }
36
37 // Linux-kernel compatibility macros, not for atomics
38 #define rcu_dereference(p) rcu_consume(p)
39 #define rcu_assign_pointer(p, v) rcu_store_release(&(p), v)
\end{verbatim}
}
\caption{Dependency-Preserving Release and Consume}
\label{fig:Dependency-Preserving Release and Consume}
\end{figure}

Figure~\ref{fig:Template: Declaration}
shows the resulting template declaration, each member function of which
has a straightforward definition.
Note especially that the relational operators are defined in terms of the
\co{pointer_cmp_eq_dep()},
\co{pointer_cmp_ne_dep()},
\co{pointer_cmp_gt_dep()},
\co{pointer_cmp_ge_dep()},
\co{pointer_cmp_lt_dep()}, and
\co{pointer_cmp_le_dep()}
functions shown in
Figure~\ref{fig:Dependency-Preserving Comparisons},
so that as long as the first argument to a relational operator is of type
\co{class depending_ptr<T>},
pointers may be safely compared without risk of breaking dependency
chains.\footnote{
	That said, in the prototype implementation,
	these are not intrinsics, but rather separately compiled functions.
	In the absence of link-time optimizations, separate compilation
	preserves dependency chains in most implementations.}
In addition, the operators that cannot be safely applied to
dependency-bearing pointers are omitted.\footnote{
	The number of pointer-tagging algorithms should motivate
	allowing bitwise operations on dependency-bearing
	pointers, but this should be handled separately.}
Finally, Figure~\ref{fig:Dependency-Preserving Release and Consume}
shows how the Linux-kernel-style \co{rcu_dereference()} and
\co{rcu_assign_pointer()} macros could be implemented given this
templated approach.

\begin{figure}[tbp]
{ \scriptsize
\begin{verbatim}
 1 void *thread0(void *unused)
 2 {
 3   rcutest *p;
 4
 5   p = new rcutest();
 6   assert(p);
 7   p->a = 42;
 8   assert(p->a != 43);
 9   rcu_store_release(&gp, p);
10   return nullptr;
11 }
12
13 void *thread1(void *unused)
14 {
15   depending_ptr<rcutest> p;
16
17   p = rcu_consume(&gp);
18   if (p)
19     p->a = 43;
20   return nullptr;
21 }
\end{verbatim}
}
\caption{Template: Simple Case}
\label{fig:Template: Simple Case}
\end{figure}

\begin{figure}[tbp]
{ \scriptsize
\begin{verbatim}
 1 void *thread0(void *unused)
 2 {
 3   rcutest *p;
 4
 5   p = new rcutest();
 6   assert(p);
 7   p->a = 42;
 8   rcu_store_release(&gp, p);
 9   return nullptr;
10 }
11
12 void
13 thread1_help(depending_ptr<rcutest> q)
14 {
15   if (q)
16     assert(q->a == 42);
17 }
18
19 void *thread1(void *unused)
20 {
21   depending_ptr<rcutest> p;
22
23   p = rcu_consume(&gp);
24   thread1_help(p);
25   return nullptr;
26 }
\end{verbatim}
}
\caption{Template: In via Function Parameter}
\label{fig:Template: In via Function Parameter}
\end{figure}

\begin{figure}[tbp]
{ \scriptsize
\begin{verbatim}
 1 void *thread0(void *unused)
 2 {
 3   rcutest *p;
 4
 5   p = new rcutest();
 6   assert(p);
 7   p->a = 42;
 8   rcu_store_release(&gp, p);
 9   return nullptr;
10 }
11
12 depending_ptr<rcutest> thread1_help()
13 {
14   return rcu_consume(&gp);
15 }
16
17 void *thread1(void *unused)
18 {
19   depending_ptr<rcutest> p;
20
21   p = thread1_help();
22   if (p)
23     p->a = 43;
24   return nullptr;
25 }
\end{verbatim}
}
\caption{Template: Out via Function Return}
\label{fig:Template: Out via Function Return}
\end{figure}

\begin{figure}[tbp]
{ \scriptsize
\begin{verbatim}
 1 void *thread0(void *unused)
 2 {
 3   rcutest *p;
 4
 5   p = new rcutest();
 6   assert(p);
 7   p->a = 42;
 8   rcu_store_release(&gp, p);
 9
10   p = new rcutest();
11   assert(p);
12   p->a = 43;
13   rcu_store_release(&gsgp, p);
14
15   return nullptr;
16 }
17
18 depending_ptr<rcutest>
19 thread1_help(depending_ptr<rcutest> p)
20 {
21   if (p)
22     assert(p->a == 42);
23   return rcu_consume(&gsgp);
24 }
25
26 void *thread1(void *unused)
27 {
28   depending_ptr<rcutest> p;
29
30   p = rcu_consume(&gp);
31   p = thread1_help(p);
32   if (p)
33     assert(p->a == 43);
34   return nullptr;
35 }
\end{verbatim}
}
\caption{Template: In and Out, But Different Chains}
\label{fig:Template: In and Out, But Different Chains}
\end{figure}

\begin{figure}[tbp]
{ \scriptsize
\begin{verbatim}
 1 void *thread0(void *unused)
 2 {
 3   rcutest *p;
 4
 5   p = new rcutest();
 6   p->a = 42;
 7   rcu_store_release(&gp, p);
 8   return nullptr;
 9 }
10
11 void thread1_help1(depending_ptr<rcutest> q)
12 {
13   if (q)
14     assert(q->a == 42);
15 }
16
17 void thread1_help2(depending_ptr<rcutest> q)
18 {
19   if (q)
20     assert(q->a != 43);
21 }
22
23 void *thread1(void *unused)
24 {
25   depending_ptr<rcutest> p;
26
27   p = rcu_consume(&gp);
28   thread1_help1(p);
29   thread1_help2(p);
30   return nullptr;
31 }
\end{verbatim}
}
\caption{Template: Chain Fanning Out}
\label{fig:Template: Chain Fanning Out}
\end{figure}

\begin{figure}[tbp]
{ \scriptsize
\begin{verbatim}
 1 void *thread0(void *unused)
 2 {
 3   rcutest *p;
 4   rcutest1 *p1;
 5
 6   p = new rcutest();
 7   p->a = 42;
 8   rcu_store_release(&gp, p);
 9
10   p1 = new rcutest1();
11   p1->a = 41;
12   p1->rt.a = 42;
13   rcu_store_release(&g1p, p1);
14
15   return nullptr;
16 }
17
18 void thread1_help(depending_ptr<rcutest> q)
19 {
20   if (q)
21     assert(q->a == 42);
22 }
23
24 void *thread1(void *unused)
25 {
26   depending_ptr<rcutest> p;
27
28   p = rcu_consume(&gp);
29   thread1_help(p);
30   return nullptr;
31 }
32
33 void *thread2(void *unused)
34 {
35   depending_ptr<rcutest1> p1;
36
37   p1 = rcu_consume(&g1p);
38   thread1_help(depending_ptr<rcutest>(&p1->rt));
39   return nullptr;
40 }
\end{verbatim}
}
\caption{Template: Chain Fanning In}
\label{fig:Template: Chain Fanning In}
\end{figure}

\begin{figure}[tbp]
{ \scriptsize
\begin{verbatim}
 1 void *thread0(void *unused)
 2 {
 3   rcutest *p;
 4   rcutest1 *p1;
 5
 6   p = new rcutest();
 7   assert(p);
 8   p->a = 42;
 9   p->b = 43;
10   rcu_store_release(&gp, p);
11
12   p1 = new rcutest1();
13   assert(p1);
14   p1->a = 41;
15   p1->rt.a = 42;
16   p1->rt.b = 43;
17   rcu_store_release(&g1p, p1);
18
19   return nullptr;
20 }
21
22 void thread1a_help(depending_ptr<rcutest> q)
23 {
24   assert(q->a == 42);
25 }
26
27 void thread1b_help(depending_ptr<rcutest> q)
28 {
29   assert(q->b == 43);
30 }
31
32 void thread1_help(depending_ptr<rcutest> q)
33 {
34   if (q) {
35     thread1a_help(q);
36     thread1b_help(q);
37   }
38 }
39
40 void *thread1(void *unused)
41 {
42   depending_ptr<rcutest> p;
43
44   p = rcu_consume(&gp);
45   thread1_help(p);
46   return nullptr;
47 }
48
49 void *thread2(void *unused)
50 {
51   depending_ptr<rcutest1> p1;
52
53   p1 = rcu_consume(&g1p);
54   thread1_help(depending_ptr<rcutest>(&p1->rt));
55   return nullptr;
56 }
\end{verbatim}
}
\caption{Template: Chain Fanning In and Out}
\label{fig:Template: Chain Fanning In and Out}
\end{figure}

\begin{figure}[tbp]
{ \scriptsize
\begin{verbatim}
 1 void *thread0(void *unused)
 2 {
 3   rcutest *p;
 4   rcutest1 *p1;
 5
 6   p = new rcutest();
 7   assert(p);
 8   p->a = 42;
 9   p->b = 43;
10   rcu_store_release(&gp, p);
11
12   p1 = new rcutest1();
13   assert(p1);
14   p1->a = 41;
15   p1->rt.a = 42;
16   p1->rt.b = 43;
17   rcu_store_release(&g1p, p1);
18
19   return nullptr;
20 }
21
22 #ifdef FOO
23 void thread1a_help(depending_ptr<rcutest> q)
24 {
25   assert(q->a == 42);
26 }
27 #endif
28
29 void thread1b_help(depending_ptr<rcutest> q)
30 {
31   assert(q->b == 43);
32 }
33
34 void thread1_help(depending_ptr<rcutest> q)
35 {
36   if (q) {
37 #ifdef FOO
38     thread1a_help(q);
39 #endif
40     thread1b_help(q);
41   }
42 }
43
44 void *thread1(void *unused)
45 {
46   depending_ptr<rcutest> p;
47
48   p = rcu_consume(&gp);
49   thread1_help(p);
50   return nullptr;
51 }
52
53 void *thread2(void *unused)
54 {
55   depending_ptr<rcutest1> p1;
56
57   p1 = rcu_consume(&g1p);
58   thread1_help(depending_ptr<rcutest>(&p1->rt));
59   return nullptr;
60 }
\end{verbatim}
}
\caption{Template: Conditional Compilation of Chain Endpoints}
\label{fig:Template: Conditional Compilation of Chain Endpoints}
\end{figure}

\begin{figure}[tbp]
{ \scriptsize
\begin{verbatim}
 1 void *thread0(void *unused)
 2 {
 3   rcutest *p;
 4
 5   p = new rcutest();
 6   p->a = 42;
 7   assert(p->a != 43);
 8   rcu_store_release(&gp, p);
 9   return nullptr;
10 }
11
12 void *thread1(void *unused)
13 {
14   depending_ptr<rcutest> p;
15
16   p = rcu_consume(&gp);
17   if (p) {
18     assert(p->a == 42);
19     spin_lock(&p->lock);
20     p = std::kill_dependency(p);
21     p->a++;
22     spin_unlock(&p->lock);
23   }
24   return nullptr;
25 }
\end{verbatim}
}
\caption{Template: Handoff to Locking}
\label{fig:Template: Handoff to Locking}
\end{figure}

Figures~\ref{fig:Template: Simple Case}--\ref{fig:Template: Handoff to Locking}
show how templates can be applied to each of the examples
introduced in Section~\ref{sec:Representative Use Cases}.
As with the object-modifier approach in
Section~\ref{sec:Object Modifier},
these changes are straightforward markings of local variables, function
parameters, and return-value types.

Full source code for a prototype implementation
(and for this paper) may be downloaded from
{\small \co{https://github.com/paulmckrcu/2016markconsume.git}}.