An Application Locking Facility (part 3)

In my last two blog posts, I presented the idea of an Application Locking Mechanism and I also presented a prototype.  I would now like to present the full implementation of this facility.  This is the final post in this series.

//
//  The magic number is used to help detect data corruption in the lock
//  structure.
//

#define LOCK_MAGIC              314157

//
//  The number of entries in a lock queue.
//

#define LOCK_QUEUE_SIZE           1024

//
//  Possible values for lock queue entries.
//

#define LOCK_NONE                    0

#define LOCK_READ                    1

#define LOCK_WRITE                   2

//
//  The lock structure.
//

struct lock_t
{
uintmagic;        // lock magic number

uintmutex;        // protects this data structure

intqueue[LOCK_QUEUE_SIZE];        // queue of users

inthead;                          // start of queue

inttail;                          // end of queue
};

//
//  proc = init_lock.
//  return = void.
//  param lock = struct lock_t * : lock structure.
//
//  Initialize a lock structure.
//

void
init_lock (struct lock_t *lock)
{
intindex;

lock->magic = LOCK_MAGIC;

lock->mutex = 0;

for (index = lock->head; index < LOCK_QUEUE_SIZE; index++)
lock->queue[index] = LOCK_NONE;

lock->head = 0;

lock->tail = -1;
}

//
//  proc = check_lock.
//  return = void.
//  param lock = struct lock_t * : lock structure.
//
//  Sanity check a lock structure.
//

void
check_lock (struct lock_t *lock)
{
intindex;

ASSERT(lock->magic == LOCK_MAGIC)

ASSERT(lock->head >= 0)

ASSERT(lock->head < LOCK_QUEUE_SIZE)

ASSERT(lock->tail >= -1)

ASSERT(lock->tail < LOCK_QUEUE_SIZE)

for (index = lock->head; index < LOCK_QUEUE_SIZE; index++)
{
ASSERT(lock->queue[index] == LOCK_NONE ||
lock->queue[index] == LOCK_READ ||
lock->queue[index] == LOCK_WRITE)
}
}

//
//  proc = index_dec.
//  return = int : the previous index in the queue.
//  param index = int : queue index.
//
//  Decrement an index in a lock queue.
//

int
index_dec (int index)
{
intprev;

prev = index–;

if (prev == -1)
prev = LOCK_QUEUE_SIZE – 1;

return prev;
}

//
//  proc = index_inc.
//  return = int : the next index in the queue.
//  param index = int : queue index.
//
//  Increment an index in a lock queue.
//

int
index_inc (int index)
{
intnext;

next = index++;

if (next >= LOCK_QUEUE_SIZE)
next = 0;

return next;
}

//
//  proc = queue_add.
//  return = int : the queue index for this item.
//  param lock = struct lock_t * : lock structure.
//  param type = int : lock type (LOCK_READ or LOCK_WRITE).
//
//  Add an item to a lock queue.
//

int
queue_add (struct lock_t *lock, int type)
{
check_lock(lock);

ASSERT(type == LOCK_READ || type == LOCK_WRITE)

lock->tail = index_inc(lock->tail);
ASSERT(lock->queue[lock->tail] == LOCK_NONE)

lock->queue[lock->tail] = type;

return lock->tail;
}

//
//  proc = queue_del.
//  return = void.
//  param lock = struct lock_t * : lock structure.
//  param index = int : queue index.
//
//  Removed an item from a lock queue.
//

void
queue_del (struct lock_t *lock, int index)
{
check_lock(lock);

ASSERT(index >= 0)

ASSERT(index < LOCK_QUEUE_SIZE)

ASSERT(lock->queue[index] == LOCK_READ || lock->queue[index] == LOCK_WRITE)

lock->queue[index] = LOCK_NONE;

while (1)
{
if (lock->queue[lock->head] == LOCK_NONE)
lock->head = index_inc(lock->head);
else
break;

if (lock->head == lock->tail)
break;
}

while (1)
{
if (lock->queue[lock->tail] == LOCK_NONE)
lock->tail = index_dec(lock->tail);
else
break;

if (lock->head == lock->tail)
break;
}
}

//
//  proc = read_lock.
//  return = int : queue index for token.
//  param lock = struct lock_t * : lock structure.
//
//  Perform a Read Lock.
//  This function will call sleep(0) until the lock is available.
//

int
read_lock (struct lock_t *lock)
{
intindex;
intitem;

spinlock(&lock->mutex);

lock_check(lock);

item = queue_add(lock, LOCK_READ);

while (1)
{
for (index = lock->head; ; index = index_inc(index))
{
if (lock->queue[index] == LOCK_WRITE)
{
lock->mutex = 0;
sleep(0);
spinlock(&lock->mutex);
lock_check(lock);
break;
}

if (index == item)
{
lock->mutex = 0;
return item;
}
}
}
}

//
//  proc = read_unlock.
//  return = void.
//  param lock = struct lock_t * : lock structure.
//  param index = int : queue index – return from read_lock().
//
//  Perform a Read Unlock.
//

void
read_unlock (struct lock_t *lock, int index)
{
spinlock(&lock->mutex);

lock_check(lock);

queue_del(lock, index);

lock->mutex = 0;
}

//
//  proc = write_lock.
//  return = int : queue index for token.
//  param lock = struct lock_t * : lock structure.
//
//  Perform a Write Lock.
//  This function will call sleep(0) until the lock is available.
//

int
write_lock (struct lock_t *lock)
{
intindex;
intitem;

spinlock(&lock->mutex);

lock_check(lock);

item = queue_add(lock, LOCK_WRITE);

while (1)
{
for (index = lock->head; ; index = index_inc(index))
{
if (index == item)
{
lock->mutex = 0;
return item;
}
else
{
lock->mutex = 0;
sleep(0);
spinlock(&lock->mutex);
lock_check(lock);
break;
}
}
}
}

//
//  proc = write_unlock.
//  return = void.
//  param lock = struct lock_t * : lock structure.
//  param index = int : queue index – return from write_lock().
//
//  Perform a Write Unlock.
//

void
write_unlock (struct lock_t *lock, int index)
{
spinlock(&lock->mutex);

lock_check(lock);

queue_del(lock, index);

lock->mutex = 0;
}