silo/masstree/nodeversion.hh

   1 /* Masstree
   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
   5  *
   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
  14  * is legally binding.
  15  */
  16 #ifndef MASSTREE_NODEVERSION_HH
  17 #define MASSTREE_NODEVERSION_HH
  18 #include "compiler.hh"
  19
  20 template <typename P>
  21 class basic_nodeversion {
  22   public:
  23     typedef P traits_type;
  24     typedef typename P::value_type value_type;
  25
  26     basic_nodeversion() {
  27     }
  28     explicit basic_nodeversion(bool isleaf) {
  29         v_ = isleaf ? (value_type) P::isleaf_bit : 0;
  30     }
  31
  32     bool isleaf() const {
  33         return v_ & P::isleaf_bit;
  34     }
  35
  36     basic_nodeversion<P> stable() const {
  37         return stable(relax_fence_function());
  38     }
  39     template <typename SF>
  40     basic_nodeversion<P> stable(SF spin_function) const {
  41         value_type x = v_;
  42         while (x & P::dirty_mask) {
  43             spin_function();
  44             x = v_;
  45         }
  46         acquire_fence();
  47         return x;
  48     }
  49     template <typename SF>
  50     basic_nodeversion<P> stable_annotated(SF spin_function) const {
  51         value_type x = v_;
  52         while (x & P::dirty_mask) {
  53             spin_function(basic_nodeversion<P>(x));
  54             x = v_;
  55         }
  56         acquire_fence();
  57         return x;
  58     }
  59
  60     bool locked() const {
  61         return v_ & P::lock_bit;
  62     }
  63     bool inserting() const {
  64         return v_ & P::inserting_bit;
  65     }
  66     bool splitting() const {
  67         return v_ & P::splitting_bit;
  68     }
  69     bool deleted() const {
  70         return v_ & P::deleted_bit;
  71     }
  72     bool has_changed(basic_nodeversion<P> x) const {
  73         fence();
  74         return (x.v_ ^ v_) > P::lock_bit;
  75     }
  76     bool has_split() const {
  77         return !(v_ & P::root_bit);
  78     }
  79     bool has_split(basic_nodeversion<P> x) const {
  80         fence();
  81         return (x.v_ ^ v_) >= P::vsplit_lowbit;
  82     }
  83     bool simple_has_split(basic_nodeversion<P> x) const {
  84         return (x.v_ ^ v_) >= P::vsplit_lowbit;
  85     }
  86
  87     basic_nodeversion<P> lock() {
  88         return lock(*this);
  89     }
  90     basic_nodeversion<P> lock(basic_nodeversion<P> expected) {
  91         return lock(expected, relax_fence_function());
  92     }
  93     template <typename SF>
  94     basic_nodeversion<P> lock(basic_nodeversion<P> expected, SF spin_function) {
  95         while (1) {
  96             if (!(expected.v_ & P::lock_bit)
  97                 && bool_cmpxchg(&v_, expected.v_,
  98                                 expected.v_ | P::lock_bit))
  99                 break;
 100             spin_function();
 101             expected.v_ = v_;
 102         }
 103         masstree_invariant(!(expected.v_ & P::dirty_mask));
 104         expected.v_ |= P::lock_bit;
 105         acquire_fence();
 106         masstree_invariant(expected.v_ == v_);
 107         return expected;
 108     }
 109
 110     void unlock() {
 111         unlock(*this);
 112     }
 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;
 118         else
 119             x.v_ = (x.v_ + ((x.v_ & P::inserting_bit) << 2)) & P::unlock_mask;
 120         release_fence();
 121         v_ = x.v_;
 122     }
 123
 124     void mark_insert() {
 125         masstree_invariant(locked());
 126         v_ |= P::inserting_bit;
 127         acquire_fence();
 128     }
 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);
 133         acquire_fence();
 134         return current_version;
 135     }
 136     void mark_split() {
 137         masstree_invariant(locked());
 138         v_ |= P::splitting_bit;
 139         acquire_fence();
 140     }
 141     void mark_change(bool is_split) {
 142         masstree_invariant(locked());
 143         v_ |= (is_split + 1) << P::inserting_shift;
 144         acquire_fence();
 145     }
 146     basic_nodeversion<P> mark_deleted() {
 147         masstree_invariant(locked());
 148         v_ |= P::deleted_bit | P::splitting_bit;
 149         acquire_fence();
 150         return *this;
 151     }
 152     void mark_deleted_tree() {
 153         masstree_invariant(locked() && !has_split());
 154         v_ |= P::deleted_bit;
 155         acquire_fence();
 156     }
 157     void mark_root() {
 158         v_ |= P::root_bit;
 159         acquire_fence();
 160     }
 161     void mark_nonroot() {
 162         v_ &= ~P::root_bit;
 163         acquire_fence();
 164     }
 165
 166     void assign_version(basic_nodeversion<P> x) {
 167         v_ = x.v_;
 168     }
 169
 170     value_type version_value() const {
 171         return v_;
 172     }
 173     value_type unlocked_version_value() const {
 174         return v_ & P::unlock_mask;
 175     }
 176
 177   private:
 178     value_type v_;
 179
 180     basic_nodeversion(value_type v)
 181         : v_(v) {
 182     }
 183 };
 184
 185
 186 template <typename P>
 187 class basic_singlethreaded_nodeversion {
 188   public:
 189     typedef P traits_type;
 190     typedef typename P::value_type value_type;
 191
 192     basic_singlethreaded_nodeversion() {
 193     }
 194     explicit basic_singlethreaded_nodeversion(bool isleaf) {
 195         v_ = isleaf ? (value_type) P::isleaf_bit : 0;
 196     }
 197
 198     bool isleaf() const {
 199         return v_ & P::isleaf_bit;
 200     }
 201
 202     basic_singlethreaded_nodeversion<P> stable() const {
 203         return *this;
 204     }
 205     template <typename SF>
 206     basic_singlethreaded_nodeversion<P> stable(SF) const {
 207         return *this;
 208     }
 209     template <typename SF>
 210     basic_singlethreaded_nodeversion<P> stable_annotated(SF) const {
 211         return *this;
 212     }
 213
 214     bool locked() const {
 215         return false;
 216     }
 217     bool inserting() const {
 218         return false;
 219     }
 220     bool splitting() const {
 221         return false;
 222     }
 223     bool deleted() const {
 224         return false;
 225     }
 226     bool has_changed(basic_singlethreaded_nodeversion<P>) const {
 227         return false;
 228     }
 229     bool has_split() const {
 230         return !(v_ & P::root_bit);
 231     }
 232     bool has_split(basic_singlethreaded_nodeversion<P>) const {
 233         return false;
 234     }
 235     bool simple_has_split(basic_singlethreaded_nodeversion<P>) const {
 236         return false;
 237     }
 238
 239     basic_singlethreaded_nodeversion<P> lock() {
 240         return *this;
 241     }
 242     basic_singlethreaded_nodeversion<P> lock(basic_singlethreaded_nodeversion<P>) {
 243         return *this;
 244     }
 245     template <typename SF>
 246     basic_singlethreaded_nodeversion<P> lock(basic_singlethreaded_nodeversion<P>, SF) {
 247         return *this;
 248     }
 249
 250     void unlock() {
 251     }
 252     void unlock(basic_singlethreaded_nodeversion<P>) {
 253     }
 254
 255     void mark_insert() {
 256     }
 257     basic_singlethreaded_nodeversion<P> mark_insert(basic_singlethreaded_nodeversion<P>) {
 258         return *this;
 259     }
 260     void mark_split() {
 261         v_ &= ~P::root_bit;
 262     }
 263     void mark_change(bool is_split) {
 264         if (is_split)
 265             mark_split();
 266     }
 267     basic_singlethreaded_nodeversion<P> mark_deleted() {
 268         return *this;
 269     }
 270     void mark_deleted_tree() {
 271         v_ |= P::deleted_bit;
 272     }
 273     void mark_root() {
 274         v_ |= P::root_bit;
 275     }
 276     void mark_nonroot() {
 277         v_ &= ~P::root_bit;
 278     }
 279
 280     void assign_version(basic_singlethreaded_nodeversion<P> x) {
 281         v_ = x.v_;
 282     }
 283
 284     value_type version_value() const {
 285         return v_;
 286     }
 287     value_type unlocked_version_value() const {
 288         return v_;
 289     }
 290
 291   private:
 292     value_type v_;
 293 };
 294
 295
 296 struct nodeversion32_parameters {
 297     enum {
 298         lock_bit = (1U << 0),
 299         inserting_shift = 1,
 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)),
 311         top_stable_bits = 4
 312     };
 313
 314     typedef uint32_t value_type;
 315 };
 316
 317
 318 struct nodeversion64_parameters {
 319     enum {
 320         lock_bit = (1ULL << 8),
 321         inserting_shift = 9,
 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)),
 333         top_stable_bits = 4
 334     };
 335
 336     typedef uint64_t value_type;
 337 };
 338
 339
 340 typedef basic_nodeversion<nodeversion32_parameters> nodeversion;
 341 typedef basic_singlethreaded_nodeversion<nodeversion32_parameters> singlethreaded_nodeversion;
 342
 343 #endif