1 // Copyright (c) 2014, Robert Escriva
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are met:
6 //
7 // * Redistributions of source code must retain the above copyright notice,
8 // this list of conditions and the following disclaimer.
9 // * 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 // * Neither the name of this project nor the names of its contributors may
13 // be used to endorse or promote products derived from this software
14 // without specific prior written permission.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 // POSSIBILITY OF SUCH DAMAGE.
27
28 #define __STDC_LIMIT_MACROS
29
30 // e
31 #include "e/atomic.h"
32 #include "e/seqno_collector.h"
33
34 using namespace e::atomic;
35 using e::seqno_collector;
36
37 struct seqno_collector::run
38 {
runseqno_collector::run39 run() { for (size_t i = 0; i < 8; ++i) { nums[i] = 0; } }
40 uint64_t nums[8];
41 } __attribute__ ((aligned (64)));
42
seqno_collector(garbage_collector * gc)43 seqno_collector :: seqno_collector(garbage_collector* gc)
44 : m_gc(gc)
45 , m_runs(gc)
46 , m_lb_hint(0)
47 {
48 assert(sizeof(run) == 64);
49 }
50
~seqno_collector()51 seqno_collector :: ~seqno_collector() throw ()
52 {
53 for (run_map_t::iterator it = m_runs.begin(); it != m_runs.end(); ++it)
54 {
55 if (m_runs.del(it->first))
56 {
57 m_gc->collect(it->second, garbage_collector::free_ptr<run>);
58 }
59 }
60 }
61
62 void
collect(uint64_t seqno)63 seqno_collector :: collect(uint64_t seqno)
64 {
65 const uint64_t idx = seqno & ~511ULL;
66 run* r = get_run(idx);
67 collect(seqno, idx, r);
68 }
69
70 void
collect_up_to(uint64_t seqno)71 seqno_collector :: collect_up_to(uint64_t seqno)
72 {
73 assert(seqno < UINT64_MAX);
74 const uint64_t idx = seqno & ~511ULL;
75 run* r = get_run(idx);
76 set_hint(idx);
77
78 for (uint64_t i = idx; i < seqno; ++i)
79 {
80 collect(i, idx, r);
81 }
82
83 for (run_map_t::iterator it = m_runs.begin(); it != m_runs.end(); ++it)
84 {
85 if (false && it->first < idx &&
86 m_runs.del(it->first))
87 {
88 m_gc->collect(it->second, garbage_collector::free_ptr<run>);
89 }
90 }
91 }
92
93 void
lower_bound(uint64_t * seqno)94 seqno_collector :: lower_bound(uint64_t* seqno)
95 {
96 while (true)
97 {
98 uint64_t lb = load_64_nobarrier(&m_lb_hint);
99 run* r = NULL;
100
101 if (!m_runs.get(lb, &r))
102 {
103 *seqno = lb;
104 return;
105 }
106
107 assert(r);
108 size_t i = 0;
109 uint64_t witness = 0;
110
111 for (; i < 8; ++i)
112 {
113 if ((witness = compare_and_swap_64_nobarrier(&r->nums[i], UINT64_MAX, UINT64_MAX)) != UINT64_MAX)
114 {
115 break;
116 }
117 }
118
119 if (i >= 8)
120 {
121 continue;
122 }
123
124 *seqno = lb + i * 64;
125
126 while ((witness & 1))
127 {
128 ++*seqno;
129 witness >>= 1;
130 }
131
132 return;
133 }
134 }
135
136 seqno_collector::run*
get_run(uint64_t idx)137 seqno_collector :: get_run(uint64_t idx)
138 {
139 run* r = NULL;
140
141 // fill in r with a run that's in the table for idx
142 while (true)
143 {
144 if (!m_runs.get(idx, &r))
145 {
146 r = new run();
147
148 if (m_runs.put_ine(idx, r))
149 {
150 break;
151 }
152
153 delete r;
154 r = NULL;
155 continue;
156 }
157 else
158 {
159 break;
160 }
161 }
162
163 assert(r);
164 return r;
165 }
166
167 void
collect(uint64_t seqno,uint64_t idx,run * r)168 seqno_collector :: collect(uint64_t seqno, uint64_t idx, run* r)
169 {
170 const uint64_t diff = (seqno - idx);
171 const uint64_t byte = diff >> 6;
172 const uint64_t bit = diff & 63ULL;
173
174 uint64_t expect = load_64_nobarrier(&r->nums[byte]);
175 uint64_t newval = expect | (1ULL << bit);
176 uint64_t witness;
177
178 while ((witness = compare_and_swap_64_nobarrier(&r->nums[byte], expect, newval)) != expect)
179 {
180 expect = witness;
181 newval = expect | (1ULL << bit);
182 }
183
184 if (newval == UINT64_MAX)
185 {
186 compress(idx, r);
187 }
188 }
189
190 void
compress(uint64_t idx,run * r)191 seqno_collector :: compress(uint64_t idx, run* r)
192 {
193 for (size_t i = 0; i < 8; ++i)
194 {
195 if (compare_and_swap_64_nobarrier(&r->nums[i], UINT64_MAX, UINT64_MAX) != UINT64_MAX)
196 {
197 return;
198 }
199 }
200
201 if (load_64_nobarrier(&m_lb_hint) != idx)
202 {
203 return;
204 }
205
206 set_hint(idx + 512);
207
208 if (m_runs.del(idx))
209 {
210 m_gc->collect(r, garbage_collector::free_ptr<run>);
211 r = get_run(idx + 512);
212 compress(idx + 512, r);
213 }
214 }
215
216 void
set_hint(uint64_t idx)217 seqno_collector :: set_hint(uint64_t idx)
218 {
219 uint64_t expect = load_64_nobarrier(&m_lb_hint);
220 uint64_t newval = idx;
221 uint64_t witness;
222
223 while (expect < newval &&
224 (witness = compare_and_swap_64_nobarrier(&m_lb_hint, expect, newval)) != expect)
225 {
226 expect = witness;
227 }
228 }
229