1 | /*- |
---|
2 | * Copyright (c) 2014 Mateusz Guzik <mjg@FreeBSD.org> |
---|
3 | * |
---|
4 | * Redistribution and use in source and binary forms, with or without |
---|
5 | * modification, are permitted provided that the following conditions |
---|
6 | * are met: |
---|
7 | * 1. Redistributions of source code must retain the above copyright |
---|
8 | * notice, this list of conditions and the following disclaimer. |
---|
9 | * 2. Redistributions in binary form must reproduce the above copyright |
---|
10 | * notice, this list of conditions and the following disclaimer in the |
---|
11 | * documentation and/or other materials provided with the distribution. |
---|
12 | * |
---|
13 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND |
---|
14 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
---|
15 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
---|
16 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE |
---|
17 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
---|
18 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
---|
19 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
---|
20 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
---|
21 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
---|
22 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
---|
23 | * SUCH DAMAGE. |
---|
24 | * |
---|
25 | * $FreeBSD$ |
---|
26 | */ |
---|
27 | |
---|
28 | #ifndef _SYS_SEQ_H_ |
---|
29 | #define _SYS_SEQ_H_ |
---|
30 | |
---|
31 | #ifdef _KERNEL |
---|
32 | #include <sys/systm.h> |
---|
33 | #endif |
---|
34 | #include <sys/types.h> |
---|
35 | |
---|
36 | /* |
---|
37 | * seq_t may be included in structs visible to userspace |
---|
38 | */ |
---|
39 | typedef uint32_t seq_t; |
---|
40 | |
---|
41 | #ifdef _KERNEL |
---|
42 | |
---|
43 | /* |
---|
44 | * seq allows readers and writers to work with a consistent snapshot. Modifying |
---|
45 | * operations must be enclosed within a transaction delineated by |
---|
46 | * seq_write_beg/seq_write_end. The trick works by having the writer increment |
---|
47 | * the sequence number twice, at the beginning and end of the transaction. |
---|
48 | * The reader detects that the sequence number has not changed between its start |
---|
49 | * and end, and that the sequence number is even, to validate consistency. |
---|
50 | * |
---|
51 | * Some fencing (both hard fencing and compiler barriers) may be needed, |
---|
52 | * depending on the cpu. Modern AMD cpus provide strong enough guarantees to not |
---|
53 | * require any fencing by the reader or writer. |
---|
54 | * |
---|
55 | * Example usage: |
---|
56 | * |
---|
57 | * writers: |
---|
58 | * lock_exclusive(&obj->lock); |
---|
59 | * seq_write_begin(&obj->seq); |
---|
60 | * obj->var1 = ...; |
---|
61 | * obj->var2 = ...; |
---|
62 | * seq_write_end(&obj->seq); |
---|
63 | * unlock_exclusive(&obj->lock); |
---|
64 | * |
---|
65 | * readers: |
---|
66 | * int var1, var2; |
---|
67 | * seq_t seq; |
---|
68 | * |
---|
69 | * for (;;) { |
---|
70 | * seq = seq_read(&obj->seq); |
---|
71 | * var1 = obj->var1; |
---|
72 | * var2 = obj->var2; |
---|
73 | * if (seq_consistent(&obj->seq, seq)) |
---|
74 | * break; |
---|
75 | * } |
---|
76 | * ..... |
---|
77 | * |
---|
78 | * Writers may not block or sleep in any way. |
---|
79 | * |
---|
80 | * There are 2 minor caveats in this implementation: |
---|
81 | * |
---|
82 | * 1. There is no guarantee of progress. That is, a large number of writers can |
---|
83 | * interfere with the execution of the readers and cause the code to live-lock |
---|
84 | * in a loop trying to acquire a consistent snapshot. |
---|
85 | * |
---|
86 | * 2. If the reader loops long enough, the counter may overflow and eventually |
---|
87 | * wrap back to its initial value, fooling the reader into accepting the |
---|
88 | * snapshot. Given that this needs 4 billion transactional writes across a |
---|
89 | * single contended reader, it is unlikely to ever happen. |
---|
90 | */ |
---|
91 | |
---|
92 | /* A hack to get MPASS macro */ |
---|
93 | #include <sys/lock.h> |
---|
94 | |
---|
95 | #include <machine/cpu.h> |
---|
96 | |
---|
97 | static __inline bool |
---|
98 | seq_in_modify(seq_t seqp) |
---|
99 | { |
---|
100 | |
---|
101 | return (seqp & 1); |
---|
102 | } |
---|
103 | |
---|
104 | static __inline void |
---|
105 | seq_write_begin(seq_t *seqp) |
---|
106 | { |
---|
107 | |
---|
108 | critical_enter(); |
---|
109 | MPASS(!seq_in_modify(*seqp)); |
---|
110 | *seqp += 1; |
---|
111 | atomic_thread_fence_rel(); |
---|
112 | } |
---|
113 | |
---|
114 | static __inline void |
---|
115 | seq_write_end(seq_t *seqp) |
---|
116 | { |
---|
117 | |
---|
118 | atomic_store_rel_32(seqp, *seqp + 1); |
---|
119 | MPASS(!seq_in_modify(*seqp)); |
---|
120 | critical_exit(); |
---|
121 | } |
---|
122 | |
---|
123 | static __inline seq_t |
---|
124 | seq_load(const seq_t *seqp) |
---|
125 | { |
---|
126 | seq_t ret; |
---|
127 | |
---|
128 | for (;;) { |
---|
129 | ret = atomic_load_acq_32(__DECONST(seq_t *, seqp)); |
---|
130 | if (seq_in_modify(ret)) { |
---|
131 | cpu_spinwait(); |
---|
132 | continue; |
---|
133 | } |
---|
134 | break; |
---|
135 | } |
---|
136 | |
---|
137 | return (ret); |
---|
138 | } |
---|
139 | |
---|
140 | static __inline seq_t |
---|
141 | seq_consistent_nomb(const seq_t *seqp, seq_t oldseq) |
---|
142 | { |
---|
143 | |
---|
144 | return (*seqp == oldseq); |
---|
145 | } |
---|
146 | |
---|
147 | static __inline seq_t |
---|
148 | seq_consistent(const seq_t *seqp, seq_t oldseq) |
---|
149 | { |
---|
150 | |
---|
151 | atomic_thread_fence_acq(); |
---|
152 | return (seq_consistent_nomb(seqp, oldseq)); |
---|
153 | } |
---|
154 | |
---|
155 | #endif /* _KERNEL */ |
---|
156 | #endif /* _SYS_SEQ_H_ */ |
---|