Class: ThreadSafe::AtomicReferenceCacheBackend::Node

Inherits:
Object
  • Object
show all
Extended by:
Util::Volatile
Includes:
Util::CheapLockable
Defined in:
lib/thread_safe/atomic_reference_cache_backend.rb

Overview

Key-value entry. Nodes with a hash field of +MOVED+ are special, and do not contain user keys or values. Otherwise, keys are never +nil+, and +NULL+ +value+ fields indicate that a node is in the process of being deleted or created. For purposes of read-only access, a key may be read before a value, but can only be used after checking value to be +!= NULL+.

Constant Summary collapse

MOVED =

Encodings for special uses of Node hash fields. See above for explanation.

('10' << ('0' * bit_shift)).to_i(2)
LOCKED =

set/tested only as a bit

('01' << ('0' * bit_shift)).to_i(2)
WAITING =

both bits set/tested together

('11' << ('0' * bit_shift)).to_i(2)
HASH_BITS =

usable bits of normal node hash

('00' << ('1' * bit_shift)).to_i(2)
SPIN_LOCK_ATTEMPTS = 
Util::CPU_COUNT > 1 ? Util::CPU_COUNT * 2 : 0

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(hash, key, value, next_node = nil) ⇒ Node

Returns a new instance of Node.



243
244
245
246
247
248
249
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 243

def initialize(hash, key, value, next_node = nil)
  super()
  @key = key
  self.lazy_set_hash(hash)
  self.lazy_set_value(value)
  self.next = next_node
end

Instance Attribute Details

#key ⇒ Object (readonly)

Returns the value of attribute key.



241
242
243
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 241

def key
  @key
end

Class Method Details

.attr_volatile(*attr_names) ⇒ Object Originally defined in module Util::Volatile

Provides +volatile+ (in the JVM's sense) attribute accessors implemented atop of the +AtomicReference+s.

Usage: class Foo extend ThreadSafe::Util::Volatile attr_volatile :foo, :bar

def initialize(bar)
  super() # must super() into parent initializers before using the volatile attribute accessors
  self.bar = bar
end

def hello
  my_foo = foo # volatile read
  self.foo = 1 # volatile write
  cas_foo(1, 2) # => true | a strong CAS
end

end

.locked_hash?(hash) ⇒ Boolean

Returns:

  • (Boolean) 


326
327
328
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 326

def locked_hash?(hash)
  (hash & LOCKED) != 0
end

Instance Method Details

#key?(key) ⇒ Boolean

Returns:

  • (Boolean) 


281
282
283
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 281

def key?(key)
  @key.eql?(key)
end

#locked? ⇒ Boolean

Returns:

  • (Boolean) 


303
304
305
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 303

def locked?
  self.class.locked_hash?(hash)
end

#matches?(key, hash) ⇒ Boolean

Returns:

  • (Boolean) 


285
286
287
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 285

def matches?(key, hash)
  pure_hash == hash && key?(key)
end

#pure_hash ⇒ Object 



289
290
291
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 289

def pure_hash
  hash & HASH_BITS
end

#try_await_lock(table, i) ⇒ Object

Spins a while if +LOCKED+ bit set and this node is the first of its bin, and then sets +WAITING+ bits on hash field and blocks (once) if they are still set. It is OK for this method to return even if lock is not available upon exit, which enables these simple single-wait mechanics.

The corresponding signalling operation is performed within callers: Upon detecting that +WAITING+ has been set when unlocking lock (via a failed CAS from non-waiting +LOCKED+ state), unlockers acquire the +cheap_synchronize+ lock and perform a +cheap_broadcast+.



260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 260

def try_await_lock(table, i)
  if table && i >= 0 && i < table.size # bounds check, TODO: why are we bounds checking?
    spins = SPIN_LOCK_ATTEMPTS
    randomizer = base_randomizer = Util::XorShiftRandom.get
    while equal?(table.volatile_get(i)) && self.class.locked_hash?(my_hash = hash)
      if spins >= 0
        if (randomizer = (randomizer >> 1)).even? # spin at random
          if (spins -= 1) == 0
            Thread.pass # yield before blocking
          else
            randomizer = base_randomizer = Util::XorShiftRandom.xorshift(base_randomizer) if randomizer.zero?
          end
        end
      elsif cas_hash(my_hash, my_hash | WAITING)
        force_aquire_lock(table, i)
        break
      end
    end
  end
end

#try_lock_via_hash(node_hash = hash) ⇒ Object 



293
294
295
296
297
298
299
300
301
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 293

def try_lock_via_hash(node_hash = hash)
  if cas_hash(node_hash, locked_hash = node_hash | LOCKED)
    begin
      yield
    ensure
      unlock_via_hash(locked_hash, node_hash)
    end
  end
end

#unlock_via_hash(locked_hash, node_hash) ⇒ Object 



307
308
309
310
311
312
 
# File 'lib/thread_safe/atomic_reference_cache_backend.rb', line 307

def unlock_via_hash(locked_hash, node_hash)
  unless cas_hash(locked_hash, node_hash)
    self.hash = node_hash
    cheap_synchronize { cheap_broadcast }
  end
end