Skip to content

Latest commit

 

History

History
179 lines (141 loc) · 9.76 KB

3_2-lock-structure.md

File metadata and controls

179 lines (141 loc) · 9.76 KB
Raw

3.2. The Lock Structure and Locking Operations

The lock structure is 8 bytes (64 bits) long.

  1. Count word:
  2. Bits 0..29 - read lock count (little-endian)
  3. Bit 30 - update lock flag
  4. Bit 31 - write lock flag
  5. Wait word: bits 32..63 - wait count (little-endian)

Try acquire read lock

  1. Read the lock state.
  2. If the write lock flag is set, or the wait count is non-zero, or the read lock count is 230 − 1, then the procedure fails.
  3. Make a copy of the count word, with the read lock count incremented.
  4. Perform a compare-and-swap (CAS) operation on the count word, comparing with the state that was read and swapping with the updated, made on the previous step. If the CAS operation succeeds, the procedure succeeds. If the CAS operation fails, the procedure fails.

Release read lock

  1. Read the lock state.
  2. If the read lock count is 0, then the procedure fails.
  3. Make a copy of the count word, with the read lock count decremented.
  4. Perform a CAS operation on the count word, comparing with the state that was read on the 1st step and swapping with the updated, made on the previous step. If the CAS operation succeeds, the procedure succeeds. If the CAS operation fails, continue this procedure, starting from the 1st step

There is formally an infinite loop in this procedure, but if implemented correctly (and only such implementations alter the lock structure) it should either fail or succeed in some finite number of iterations.

Try acquire update lock

  1. Read the lock state.
  2. If the update or write lock flag is set or the wait count is non-zero, then the procedure fails.
  3. Make a copy of the count word, with the update lock flag set.
  4. Perform a CAS operation on the count word, comparing with the state that was read and swapping with the updated, made on the previous step. If the CAS operation succeeds, the procedure succeeds. If the CAS operation fails, the procedure fails.

Release update lock

  1. Read the lock state.
  2. If the update lock flag is not set, then the procedure fails.
  3. Make a copy of the count word, with the update lock flag unset.
  4. Perform a CAS operation on the count word, comparing with the state that was read on the 1st step and swapping with the updated, made on the previous step. If the CAS operation succeeds, the procedure succeeds. If the CAS operation fails, continue this procedure, starting form the 1st step.

Time-limited read or update lock acquisition

Attempt to acquire the read or update lock using the corresponding try acquire procedure, until it succeeds, optionally inserting some directives aimed to yield the resources after failed attempts, for example, x86's PAUSE instruction, or an OS command to schedule another OS thread to the current CPU, or a runtime command to schedule another green thread to the current OS thread, or a command to clock down the current CPU, etc.

If the runtime of the Chronicle Map implementation has cooperative (rather than preemptive) scheduling of threads, thread switch must be enabled after failed attempts. Some explicit command is executed, letting the runtime to switch between green threads.

Possibility for thread switch is required to avoid dead locks between threads.

There is no single exact scheme that implementations should follow, it is unspecified. The implementation may vary for the read and update locks as well.

The reference Java implementation doesn't insert any resources yielding directives after failed acquisition attempts, for both read and update lock acquisition.

Implementations must not try to acquire the read or update lock indefinitely, after some finite number of failed attempts or some finite time elapsed since the time-limited lock acquisition procedure starts, the procedure must fail.

Indefinite lock acquisition is dead lock prone.

The reference Java implementation makes attempts to acquire the lock for 1 minute, then throws an exception.

Try acquire write lock

  1. (Optional step) Read the count word of the lock state.
  2. (Optional step) If the count word is non-zero, the procedure fails.
  3. Perform a CAS operation on the count word of the lock state, comparing 0 (i. e. the operation fails, if any bit of the count word is non-zero) and swapping with 0x80000000, i. e. a count word with the write lock flag set, the update lock flag not set, and the read lock count of zero. The result of the CAS operation is the result of the procedure.

The two optional steps should be performed, if the procedure most likely fails, and the steps should be skipped, if the procedure most likely succeeds. Implementations may have both versions of the procedure and call one depending on the context.

When the first two steps of the procedure are performed on x86, the cache line containing the lock structure is first moved to the Shared state (in terms of MESI protocol or it's successors in newer CPUs), then to the Modified state. When the first two steps are omitted, the cache line is moved directly to the Modified state, reducing bus traffic. On the other hand, when the first two steps are performed and cause the try acquire write lock procedure to fail early, bus locking is avoided, that increases scalability.

The reference Java implementation uses only the version of this procedure without the first two steps.

## Release write lock, or write to update lock downgrade, or write to read lock downgrade

Perform a CAS operation on the count word of the lock state, comparing 0x80000000 (i. e. a count word with the write lock flag set) and swapping with 0 (in case of releasing write lock), or 0x40000000 (in case of write to update lock downgrade), or 1 (in case of write to read lock downgrade). The result of the CAS operation is the result of the procedure.

Try upgrade update to write lock

Perform a CAS operation on the count word of the lock state, comparing 0x40000000 (i. e. a count word with the update lock flag set, the write lock flag not set, the read lock count of zero) and swapping with 0x80000000, i. e. a count word with the write lock flag set, the update lock flag not set, and the read lock count of zero. The result of the CAS operation is the result of the procedure.

Register wait

  1. Read the wait word of the lock structure.
  2. If the wait count is 231 − 1, the procedure fails: wait count overflow.
  3. Perform a CAS operation on the wait word of the lock structure, comparing the wait word that was read with a wait word with the wait count incremented. If the CAS operation fails, begin the register wait procedure from the start. If the CAS operation succeeds, the procedure succeeds.

Deregister wait

  1. Read the wait word of the lock structure.
  2. If the wait count is 0, the procedure fails: wait count underflow.
  3. Perform a CAS operation on the wait word of the lock structure, comparing the wait word that was read with a wait word with the wait count decremented. If the CAS operation fails, begin the deregister wait procedure from the start. If the CAS operation succeeds, the procedure succeeds.
## Time-limited write lock acquisition or update to write upgrade
  1. Perform the corresponding try acquire procedure (write lock or upgrade update to write lock). If the attempt succeeds, this procedure succeeds. If the attempt fails, continue with the following steps.
  2. Register a wait. If the register wait procedure fails, this time-limited procedure fails.
  3. Read the lock state.
  4. If the count word of the lock state is not equal to 0 (in case of acquiring the write lock) or 0x40000000 (in case of upgrading update to write lock), go to the 7th step.
  5. If the wait count is 0, this procedure fails.
  6. Perform a CAS operation on the whole lock structure, comparing the state, read on the 3rd step, with an updated state with the wait count decremented, and count word of 0x80000000 (the write lock flag set). If the CAS operation succeeds, the time-limited acquisition succeeds. If the CAS operation fails, continue with the 7th step.
  7. Check if this time-limited procedure has run out of the time limit or the number of attempts. If it is, the time-limited acquisition fails, deregister a wait before exiting from this procedure (the result of the deregister wait procedure doesn't matter). Otherwise, continue from the 3rd step of this procedure, optionally performing some directives aimed to yield the resources at first, as described in the section about time-limited read or update lock acquisition.

If the runtime of the Chronicle Map implementation has cooperative (rather than preemptive) scheduling of threads, thread switch must be enabled before continuing with the 3rd step. Some explicit command is executed, letting the runtime to switch between green threads.

Implementations doesn't make locking attempts indefinitely for the same reasons, as in case of acquiring read and update lock.

The reference Java implementation

Attempt, release and downgrade operations: VanillaReadWriteUpdateWithWaitsLockingStrategy

Time-limited operations: BigSegmentHeader