2 * Eddie Kohler, Yandong Mao, Robert Morris
3 * Copyright (c) 2012-2013 President and Fellows of Harvard College
4 * Copyright (c) 2012-2013 Massachusetts Institute of Technology
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the "Software"),
8 * to deal in the Software without restriction, subject to the conditions
9 * listed in the Masstree LICENSE file. These conditions include: you must
10 * preserve this copyright notice, and you cannot mention the copyright
11 * holders in advertising related to the Software without their permission.
12 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
13 * notice is a summary of the Masstree LICENSE file; the license in that file
16 #ifndef MASSTREE_NODEVERSION_HH
17 #define MASSTREE_NODEVERSION_HH
18 #include "compiler.hh"
21 class basic_nodeversion {
23 typedef P traits_type;
24 typedef typename P::value_type value_type;
28 explicit basic_nodeversion(bool isleaf) {
29 v_ = isleaf ? (value_type) P::isleaf_bit : 0;
33 return v_ & P::isleaf_bit;
36 basic_nodeversion<P> stable() const {
37 return stable(relax_fence_function());
39 template <typename SF>
40 basic_nodeversion<P> stable(SF spin_function) const {
42 while (x & P::dirty_mask) {
49 template <typename SF>
50 basic_nodeversion<P> stable_annotated(SF spin_function) const {
52 while (x & P::dirty_mask) {
53 spin_function(basic_nodeversion<P>(x));
61 return v_ & P::lock_bit;
63 bool inserting() const {
64 return v_ & P::inserting_bit;
66 bool splitting() const {
67 return v_ & P::splitting_bit;
69 bool deleted() const {
70 return v_ & P::deleted_bit;
72 bool has_changed(basic_nodeversion<P> x) const {
74 return (x.v_ ^ v_) > P::lock_bit;
76 bool has_split() const {
77 return !(v_ & P::root_bit);
79 bool has_split(basic_nodeversion<P> x) const {
81 return (x.v_ ^ v_) >= P::vsplit_lowbit;
83 bool simple_has_split(basic_nodeversion<P> x) const {
84 return (x.v_ ^ v_) >= P::vsplit_lowbit;
87 basic_nodeversion<P> lock() {
90 basic_nodeversion<P> lock(basic_nodeversion<P> expected) {
91 return lock(expected, relax_fence_function());
93 template <typename SF>
94 basic_nodeversion<P> lock(basic_nodeversion<P> expected, SF spin_function) {
96 if (!(expected.v_ & P::lock_bit)
97 && bool_cmpxchg(&v_, expected.v_,
98 expected.v_ | P::lock_bit))
103 masstree_invariant(!(expected.v_ & P::dirty_mask));
104 expected.v_ |= P::lock_bit;
106 masstree_invariant(expected.v_ == v_);
113 void unlock(basic_nodeversion<P> x) {
114 masstree_invariant((fence(), x.v_ == v_));
115 masstree_invariant(x.v_ & P::lock_bit);
116 if (x.v_ & P::splitting_bit)
117 x.v_ = (x.v_ + P::vsplit_lowbit) & P::split_unlock_mask;
119 x.v_ = (x.v_ + ((x.v_ & P::inserting_bit) << 2)) & P::unlock_mask;
125 masstree_invariant(locked());
126 v_ |= P::inserting_bit;
129 basic_nodeversion<P> mark_insert(basic_nodeversion<P> current_version) {
130 masstree_invariant((fence(), v_ == current_version.v_));
131 masstree_invariant(current_version.v_ & P::lock_bit);
132 v_ = (current_version.v_ |= P::inserting_bit);
134 return current_version;
137 masstree_invariant(locked());
138 v_ |= P::splitting_bit;
141 void mark_change(bool is_split) {
142 masstree_invariant(locked());
143 v_ |= (is_split + 1) << P::inserting_shift;
146 basic_nodeversion<P> mark_deleted() {
147 masstree_invariant(locked());
148 v_ |= P::deleted_bit | P::splitting_bit;
152 void mark_deleted_tree() {
153 masstree_invariant(locked() && !has_split());
154 v_ |= P::deleted_bit;
161 void mark_nonroot() {
166 void assign_version(basic_nodeversion<P> x) {
170 value_type version_value() const {
173 value_type unlocked_version_value() const {
174 return v_ & P::unlock_mask;
180 basic_nodeversion(value_type v)
186 template <typename P>
187 class basic_singlethreaded_nodeversion {
189 typedef P traits_type;
190 typedef typename P::value_type value_type;
192 basic_singlethreaded_nodeversion() {
194 explicit basic_singlethreaded_nodeversion(bool isleaf) {
195 v_ = isleaf ? (value_type) P::isleaf_bit : 0;
198 bool isleaf() const {
199 return v_ & P::isleaf_bit;
202 basic_singlethreaded_nodeversion<P> stable() const {
205 template <typename SF>
206 basic_singlethreaded_nodeversion<P> stable(SF) const {
209 template <typename SF>
210 basic_singlethreaded_nodeversion<P> stable_annotated(SF) const {
214 bool locked() const {
217 bool inserting() const {
220 bool splitting() const {
223 bool deleted() const {
226 bool has_changed(basic_singlethreaded_nodeversion<P>) const {
229 bool has_split() const {
230 return !(v_ & P::root_bit);
232 bool has_split(basic_singlethreaded_nodeversion<P>) const {
235 bool simple_has_split(basic_singlethreaded_nodeversion<P>) const {
239 basic_singlethreaded_nodeversion<P> lock() {
242 basic_singlethreaded_nodeversion<P> lock(basic_singlethreaded_nodeversion<P>) {
245 template <typename SF>
246 basic_singlethreaded_nodeversion<P> lock(basic_singlethreaded_nodeversion<P>, SF) {
252 void unlock(basic_singlethreaded_nodeversion<P>) {
257 basic_singlethreaded_nodeversion<P> mark_insert(basic_singlethreaded_nodeversion<P>) {
263 void mark_change(bool is_split) {
267 basic_singlethreaded_nodeversion<P> mark_deleted() {
270 void mark_deleted_tree() {
271 v_ |= P::deleted_bit;
276 void mark_nonroot() {
280 void assign_version(basic_singlethreaded_nodeversion<P> x) {
284 value_type version_value() const {
287 value_type unlocked_version_value() const {
296 struct nodeversion32_parameters {
298 lock_bit = (1U << 0),
300 inserting_bit = (1U << 1),
301 splitting_bit = (1U << 2),
302 dirty_mask = inserting_bit | splitting_bit,
303 vinsert_lowbit = (1U << 3), // == inserting_bit << 2
304 vsplit_lowbit = (1U << 9),
305 unused1_bit = (1U << 28),
306 deleted_bit = (1U << 29),
307 root_bit = (1U << 30),
308 isleaf_bit = (1U << 31),
309 split_unlock_mask = ~(root_bit | unused1_bit | (vsplit_lowbit - 1)),
310 unlock_mask = ~(unused1_bit | (vinsert_lowbit - 1)),
314 typedef uint32_t value_type;
318 struct nodeversion64_parameters {
320 lock_bit = (1ULL << 8),
322 inserting_bit = (1ULL << 9),
323 splitting_bit = (1ULL << 10),
324 dirty_mask = inserting_bit | splitting_bit,
325 vinsert_lowbit = (1ULL << 11), // == inserting_bit << 2
326 vsplit_lowbit = (1ULL << 27),
327 unused1_bit = (1ULL << 60),
328 deleted_bit = (1ULL << 61),
329 root_bit = (1ULL << 62),
330 isleaf_bit = (1ULL << 63),
331 split_unlock_mask = ~(root_bit | unused1_bit | (vsplit_lowbit - 1)),
332 unlock_mask = ~(unused1_bit | (vinsert_lowbit - 1)),
336 typedef uint64_t value_type;
340 typedef basic_nodeversion<nodeversion32_parameters> nodeversion;
341 typedef basic_singlethreaded_nodeversion<nodeversion32_parameters> singlethreaded_nodeversion;