Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Erratic StampedLock.unlock(long) behaviour?

I'm facing a strange behaviour about StampedLock. Here are the main problematic lines of code :

StampedLock lock = new StampedLock();
long stamp1 = lock.readLock();
System.out.printf("Read lock count: %d%n", lock.getReadLockCount());
lock.unlock(stamp1 + 2);
System.out.printf("Read lock count: %d%n", lock.getReadLockCount());

The strange behaviour is about how unlock "tolerates" wrong read stamp. Does it seem correct to you?


For reference here is the full code:

public class StampedLockExample {
  static StampedLock lock = new StampedLock();

  static void println(String message, Object... args) {
    System.out.printf(message, args);
    System.out.println();
  }

  static void printReadLockCount() {
    println("Lock count=%d", lock.getReadLockCount());
  }

  static long tryReadLock() {
    long stamp = lock.tryReadLock();
    println("Gets read lock (%d)", stamp);
    printReadLockCount();
    return stamp;
  }

  static long tryWriteLock() {
    long stamp = lock.tryWriteLock();
    println("Gets write lock (%d)", stamp);
    return stamp;
  }

  static long tryConvertToReadLock(long stamp) {
    long newOne = lock.tryConvertToReadLock(stamp);
    println("Gets read lock (%d -> %d)", stamp, newOne);
    printReadLockCount();
    return newOne;
  }

  static void tryUnlock(long stamp) {
    try {
      lock.unlock(stamp);
      println("Unlock (%d) successfully", stamp);
    } catch (IllegalMonitorStateException e) {
      println("Unlock (%d) failed", stamp);
    }
    printReadLockCount();
  }

  public static void main(String[] args) {
    println("%n--- Gets two read locks ---");
    long stamp1 = tryReadLock();
    long stamp2 = tryReadLock();
    long min = Math.min(stamp1, stamp2);
    long max = Math.max(stamp1, stamp2);

    println("%n--- Tries unlock (-1 / +2 / +4) ---");
    tryUnlock(min - 1);
    tryUnlock(max + 2);
    tryUnlock(max + 4);

    println("%n--- Gets write lock ---");
    long stamp3 = tryWriteLock();

    println("%n--- Tries unlock (-1 / +1) ---");
    tryUnlock(stamp3 - 1);
    tryUnlock(stamp3 + 1);

    println("%n--- Tries write > read conversion ---");
    long stamp4 = tryConvertToReadLock(stamp3);

    println("%n--- Tries unlock last write stamp (-1 / 0 / +1) ---");
    tryUnlock(stamp3 - 1);
    tryUnlock(stamp3);
    tryUnlock(stamp3 + 1);

    println("%n--- Tries unlock (-1 / +1) ---");
    tryUnlock(stamp4 - 1);
    tryUnlock(stamp4 + 1);
  }
}

Output:

--- Gets two read locks ---
Gets read lock (257)
Lock count=1
Gets read lock (258)
Lock count=2

--- Tries unlock (-1 / +2 / +4) ---
Unlock (256) failed
Lock count=2
Unlock (260) successfully
Lock count=1
Unlock (262) successfully
Lock count=0

--- Gets write lock ---
Gets write lock (384)

--- Tries unlock (-1 / +1) ---
Unlock (383) failed
Lock count=0
Unlock (385) failed
Lock count=0

--- Tries write > read conversion ---
Gets read lock (384 -> 513)
Lock count=1

--- Tries unlock last write stamp (-1 / 0 / +1) ---
Unlock (383) failed
Lock count=1
Unlock (384) failed
Lock count=1
Unlock (385) failed
Lock count=1

--- Tries unlock (-1 / +1) ---
Unlock (512) failed
Lock count=1
Unlock (514) successfully
Lock count=0
like image 911
LoganMzz Avatar asked Jun 04 '15 15:06

LoganMzz


2 Answers

Short answer:

Adding two to the stamp is modifying a portion of it which does not require validation in read-mode locks.

Long answer:

The stamp contains two pieces of information: a state sequence number, and how many readers there are. The state number is stored in the first 57 bits of the stamp, and the reader count is stored in the last 7 bits. So when you add 2 to the stamp, you are changing the reader count from 1 to 3, and leaving the state number unchanged. Since the StampedLock has only been acquired in read mode, just the state number is validated and the reader count is ignored. This makes sense because read locks should be able to unlock in any order.

For example: A read stamp is acquired from an existing StampedLock and has a state number of 4 and a reader count of 1. A second read stamp is acquired from the same StampedLock and has a state number of 4 and a reader count of 2. Note that the state numbers of the stamps are the same because the StampedLock's state has not changed in between acquisition of the stamps. The first read stamp is used in an unlock. The state number of the first stamp (4) matches the state number of the StampedLock (4), so that's fine. The reader count of the first stamp (1) does not match the reader count of the StampedLock (2), but that doesn't matter, because read locks should be able to unlock in any order. So the unlock succeeds.

Note that StampedLocks were designed to be high-performing read/write locks for internal utilities, not something to withstand malicious coding, so it is operating within its intended boundaries. I do think the Javadoc of unlock() is misleading though.

like image 198
heenenee Avatar answered Oct 14 '22 12:10

heenenee


the key part from the javadocs:

Stamps use finite representations, and are not cryptographically secure (i.e., a valid stamp may be guessable).

This means you should treat them as opaque values and not try to modify them in any way.

The may be guessable essentially is what your -1, +2, +4 arithmetics do. It's not just guessable but easy to do so if you got a good starting point for guessing, such as a previous token.

Additionally, StampedLock.validate(long) states:

Invoking this method with a value not obtained from tryOptimisticRead() or a locking method for this lock has no defined effect or result.

In other words: Any token value not directly obtained from one of the Lock's methods is not only invalid but also entails undefined behavior.

like image 22
the8472 Avatar answered Oct 14 '22 12:10

the8472