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

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

- (Node) initialize(hash, key, value, next_node = nil)

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

- (Object) key (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

+ (Object) attr_volatile(*attr_names) 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

+ (Boolean) locked_hash?(hash)

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

- (Boolean) key?(key)

Returns:

  • (Boolean) 


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

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

- (Boolean) locked?

Returns:

  • (Boolean) 


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

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

- (Boolean) matches?(key, hash)

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

- (Object) pure_hash 



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

def pure_hash
  hash & HASH_BITS
end

- (Object) try_await_lock(table, i)

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

- (Object) try_lock_via_hash(node_hash = hash) 



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

- (Object) unlock_via_hash(locked_hash, node_hash) 



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