3rd level of locking

[John Stone]

1. locking on class which is working with file, so that seek, read, write are done atomically
2. logical locking - from the user of Data class point of view

now comes 3rd, which I'm calling "internal locking"
example from Data::unlock: there are many things you must do:
check whether it is valid record in db
check whether it was logically locked
check whether it was logically locked by the this client,
logically unlock it
.. and perhaps some other statements (logging, etc.)

All the above actions should be done atomically on one record, so no other thread is allowed to jump in and read or change record/lock data of this record, because they could be wrong until whole operation is complete. I came to this conclusion, because no matter how I organized calls in (lock, unlock, delete) I could still find race condition, which leaded to incorrect results.

How are you dealing with Data methods? How are you assuring, that some operation on record is done atomically?

[Musab Al-Rawi]

but i think that those lock and unlock can be done by calling the lock() and unlock() in DBMain, that's the provided interface.

[John Stone]

Originally posted by Musab Al-Rawi:
but i think that those lock and unlock can be done by calling the lock() and unlock() in DBMain, that's the provided interface.

I don't understand what you are trying to say.
I'm talking about Data class implementation. When the user of your Data class (or DBMain interface) calls unlock, there are number of things you do in Data::unlock(). So there is possibility for other thread to jump in, in the middle and start working with the same record.
[ August 29, 2007: Message edited by: John Stone ]

[Musab Al-Rawi]

Oh ok gotcha.

But still I believe that you don't need that 3rd level of locking. if whoever trys to manipulate a record has to lock() it first then you won't fall in race condition.

what about create(), update(), delete() etc methods of DBMain, do they need to call lock() and unlock() of DBMain. or is it enough for them to use the DB locking-layer?

[John Stone]

Consider this example with cookie:

- let's suppose that record must be locked before it can be deleted
- let's suppose you can't unlock deleted record
- record 1 is locked, client have cookie
- now client starts 2 threads, one with delete, one with unlock

Possible outcomes:
- first thread deletes record, then second thread tries to unlock it, but fails
- second thread unlocks record and first thread will fail to delete it

in either case you would fail, but..

but if your delete method looks like:

 if isRecordLocked() {
     db.deleteRecord(recNo);
 }

then you are performing delete in multiple steps,.. so you can pass the condition that record is locked,.. now the 2nd thread jumps in, unlock record and then the first one will delete record, which is no more locked

(I'll think about better example)

[Musab Al-Rawi]

hi,

so you are suggesting that the client can start threads to manipulate data?

If I got you right you are complicating things.
i suggest that consider this flow/senario:
- client 1 locks record (for deleting)
- client 2 locks record (for updating)
- client 1 deletes the record
- client 1 unlocks the record
- client 2 gets record doesn't exist exception.

regards

[John Stone]

Perhaps, I am.

Another example:

// Locks a record so that it can only be updated or deleted by this client.
// If the specified record is already locked, the current thread gives up
// the CPU and consumes no CPU cycles until the record is unlocked.
public void lock...;
 
// Deletes a record, making the record number and associated disk
// storage available for reuse. 
public void delete...;

Here we see:
if the record is locked -> then it can be deleted only by this client.

But, is the opposite direction true?
If the record is not locked should we allow delete? If I am strictly following assignment, then I have to answer: yes.
Assignment is not saying, that you should lock before delete. Assignment just says, that if the record is locked only client, who locked it, can delete it.

Now consider this situation:
client 1 wants to lock record
client 2 is deleting unlocked record (he doesn't have to lock it first)

client 1 passes all checks for lock/record validity and is about to put a lock in e.g. some map.
client 2 deletes record just at the exact moment

And client 1 ends up with lock on non-existing record.

(I know that many ranchers specified extra requirement, that record which is uptated/deleted should be locked first and are probably avoiding problem I described)

[Jar Jaquiso]

Hello John,

I think you're being to strict on the requirements. Remember that the specifications also state that This document deliberately leaves some issues unspecified. So it's up to you to provide a good solution when in doubt.

I know that many ranchers specified extra requirement, that record which is uptated/deleted should be locked first and are probably avoiding problem I described

Others have done this 'cause this is the obvious solution to the problem.

Best regards,

Jar

[John Stone]

Originally posted by Jar Jaquiso:
I think you're being to strict on the requirements.

I agree, but I have much money in it :-).

[Mark Ebeling]

John,
I don't know if this helps, but I put in a LockManager similar to what Andrew shows in his book (pg. 158). Then I only allow access to the delete method in my Data class as follows:

public void deleteRecord(long recNo, long lockCookie)
      throws RecordNotFoundException, SecurityException{
        if (lockMgr.reservedContractors.get(recNo).isKey(lockCookie)){
            db.deleteContractorRecord(recNo);
        }
    }    

This way you can only delete if you have locked the record first, and have the actual key. The LockManger just decouples the locking from the data access. You either have the correct lock or not. I will definitely define all my conclusions in my choices.txt, but I think this is how others have coded and passed.

[John Stone]

Originally posted by Mark Ebeling:
John,
I don't know if this helps, but I put in a LockManager similar to what Andrew shows in his book (pg. 158). Then I only allow access to the delete method in my Data class as follows:

public void deleteRecord(long recNo, long lockCookie)
      throws RecordNotFoundException, SecurityException{
        if (lockMgr.reservedContractors.get(recNo).isKey(lockCookie)){
            db.deleteContractorRecord(recNo);
        }
    }    

This way you can only delete if you have locked the record first, and have the actual key. The LockManger just decouples the locking from the data access. You either have the correct lock or not. I will definitely define all my conclusions in my choices.txt, but I think this is how others have coded and passed.

This is exactly kind of code, which is vulnerable to multiple-threads-with-same-cookie issue.

Again example with your code:
===
Thread 1 has locked record,.. and is about to delete it.

(Thread 1) pass the condition:

if (lockMgr.reservedContractors.get(recNo).isKey(lockCookie)){

And now thread 2 comes in. Thread 2 wants to unlock record. It has correct cookie, so record is unlocked.

Thread 3 comes in and wants to lock record, which is OK, record is not locked. Thread 3 locks record..

Live goes on,..

And thread 1 is again on turn and executes the rest of delete:

db.deleteContractorRecord(recNo);

Record is deleted, and thread 3 have lock on it.
===

[Mark Ebeling]

John,
If I am wrong let me know. But I thought Thread 1 ( client 1 ) would be the only thread to have the correct cookie.
How could Thread 2 (client 2) come along with the correct cookie also and unlock? Only thread 1 has cookie since it locked the record.
What am I missing?

Thanks,

Oh, and I wanted to add that I am assuming (in my choices.txt) that each thread must call methods in Data in the following order:
1) Data.lockRecord();
2) Data.update/deleteRecord();
3) Data.unlock();
[ August 31, 2007: Message edited by: Mark Ebeling ]

[John Stone]

It is not very likely, that Sun will test for this, I'm just saying, that it is possible to exploit that implementation.

How two threads can have same cookie?
They share it.

Thread 1 locks record and receives cookie, after this operation it stores cookie in place where everybody else can read it. (This could be done in many ways)
Or the thread 1 can just spawn 3 more (or 15) new threads and 'give' just received cookie to them. (e.g. as a parameter in constructor)

I know, that you are not implementing it this way, but you never know what kind of tests Sun prepared, perhaps they are also testing for this, but it doesn't reflect on your score, because too many rancher had 80/80 from locking with your approach.

[Mark Ebeling]

Well, at least I am on track for my project. Boy, sounds like you have had some experience with some Rogue developers.

[Tomas Klubal]

Originally posted by John Stone:
It is not very likely, that Sun will test for this, I'm just saying, that it is possible to exploit that implementation.

How two threads can have same cookie?
They share it.

Thread 1 locks record and receives cookie, after this operation it stores cookie in place where everybody else can read it. (This could be done in many ways)
Or the thread 1 can just spawn 3 more (or 15) new threads and 'give' just received cookie to them. (e.g. as a parameter in constructor)

I know, that you are not implementing it this way, but you never know what kind of tests Sun prepared, perhaps they are also testing for this, but it doesn't reflect on your score, because too many rancher had 80/80 from locking with your approach.