October, 2005
See www.cs.umb.edu/cs734/lm,
or equivalently /data/htdocs/cs734/lm
::::::::::::::
readme.txt, with edited-in
page numbers for this handout
::::::::::::::
Programming Project for
cs734, fall '05
Makefile: UNIX makefile (use
"make lma")
Makefile.Win32: Microsoft C
makefile (use "nmake lma")
lm.in1: test input file:
(use "lma<lm.in1>lm.out1", etc.)
lm.out1: output file for
supplied lm.c with RW not defined
(all read lock requests turn into write
lock requests)
lm.out1_rw: expected output
with working RW code.
Main files you need to
study, in order of handout:
edt.h: global header, some
comments on scanning lists, etc. pg. 1
ll1.h: singly-linked list
header pg. 2
ll2.h: 2-way (doubly-linked)
list header pg. 4
test_ll2.c: sample program
for LL2 pg. 5
ht.h: closed hashing header
pg. 6
test_ht.c: sample program
for HT pg. 8
lm.h: lock manager API
(public header) pg. 9
lm_private.h: lock manager
private header: LM data structures pg. 10
lm.c: lock manager source:
you edit this file.to add RW locks, WFG code
pg. 11
lmdrive.c: driver for lock
manager pg. 22
wfg.h: API for WFG
(waits-for graph) pg. 23
wfg_private.h: WFG private
header pg. 24
wfg.c: WFG implementation (not in this handout)
For adding
latches/semaphores (not in this handout):
latch.h: API for latches
semaphore.h: API for binary
semaphores
Supplied code for lists, closed hashing
if you think something's not working. You don't need to edit these.
Perhaps you don't even need to read
them. The headers are supposed
to say how to use them.
::::::::::::::
edt.h
::::::::::::::
/* edt.h: some basic global
types */
/* a word of computer memory
-- */
/* edt.h: top-level EDT
header with common definitions */
typedef char * Word;
/* our generic Ptr-- pointer
to pointer */
typedef Word * Ptr;
/* Positions in a sequence,
e.g., LL1 or LL2
Each sequence of N elements has N+2
positions:
Positions at each element, BOL
(beginning-of-list, before any elements)
and EOL (end-of-list, after all elements):
first_element ... last_element
^ ^ ^^^
^ ^
BOL
HOL
EOL
Thus in particular, an empty list has 2
positions, BOL and EOL.
Scans of sequences
To do a scan of a sequence, initialize a
handle at BOL and then
do a loop of next's until next returns
NULL. For example, with LL1
inithandle_ll1(&list_hdr, BOL,
&list_hand);
while (p = next_ll1) {
... }
Inserts in sequences
There are N+1 possible spots in which to
insert a new element in
a sequence.
If a handle is positioned at a certain element, an
insert using it as current will put the new
element in the position
*before* the current element. To insert an element at the end of
a sequence, either set up a handle
positioned at EOL and then insert at
the current position, or specify EOL in the
insert itself:
inithandle_ll1(&list_hdr, EOL,
&list_hand);
insert(&list_hand, &elt, CURR);
or
(EOL in insert overrides BOL of handle)
inithandle_ll1(&list_hdr, BOL,
&list_hand);
insert(&list_hand,
&elt, EOL);
Deletes in sequences
There are N possible spots for deletion, one
for each element.
The element to be deleted is the one
selected by the handle,
or in the delete itself (HOL specified in
the delete call overrides
the position of the handle.)
*/
/* beginning-of-list (before
first element) */
#define BOL 1
/* head-of-list (at first
element) */
#define HOL 2
/* current position of
handle */
#define CURR 3
/* end-of-list (after last
element) */
#define EOL 4
/* unknown position */
#define UNK 5
/* handle states */
#define HAND_CURR 0
#define HAND_BOL 1
#define HAND_EOL 2
#define HAND_UNK 3
#define HAND_NEW 4
::::::::::::::
ll1.h
::::::::::::::
/* LL1 header-- supplied
header for singly-linked lists
Requires user-supplied header file inclusion
following this one
to define one or more list-elment objects
(LEOs) that are to sit
on singly-linked lists such as this.
*/
/* The list pointer--include
in each LEO struct */
typedef Ptr LL1info;
/* 3 structs with
LL1-private fields--the application should not
access the members of these 3 structs (this
is done in the LL1 code) */
/* This struct contains the
offset of the list pointers (LL1info) in
each LEO (there might be other LL1's going
through each LEO.)
A variable of this type will be set up by
the app using these LL1s,
and will be filled in by the maketype_ll1
macro below.
*/
typedef struct {
int info_offset;
} LL1type;
/* the list header filled in
by make_ll1 below */
typedef struct {
int info_offset;
Ptr headp,tailp;
} LL1;
/* The handle (cursor)
object, filled in by inithand_ll1 below.
This is what tells us where we are in an LL1
list, while scanning it. */
typedef struct {
int info_offset; /* offset of the list pointers (LL1info) in each LEO */
Ptr prevp; /*
previous list pointer during scan */
char status; /*
flag for special cases */
LL1 *headerp; /*
pointer to header record of list */
} LL1hand;
/* The application uses the
following macro to set up a LL1type variable
(holding offset information), before making
any list headers.
The point is we need to know the offset of
the list-pointer in the LEO
before creating list headers.
The macro parameters are:
LEO_TYPE--the application's LEO struct type,
e.g. LCB;
INFO_FIELD--within LEO_TYPE, the LL1info
member name, e.g. txlistinfo;
LL1TYPE_PTR--the pointer to the LL1type variable being filled in here.
*/
#define
maketype_ll1(LEO_TYPE,INFO_FIELD,LL1TYPE_PTR) \
{ LEO_TYPE *trec; trec = (LEO_TYPE
*)0; \
maketyp_ll1(((Ptr)&trec->INFO_FIELD - (Ptr)trec),LL1TYPE_PTR); }
/* the app can query the
handle to see if it is at beginning of end of list */
#define bol_ll1(handle) (((LL1hand *)(handle))->status==HAND_BOL)
#define eol_ll1(handle) (((LL1hand *)(handle))->status==HAND_EOL)
/* helper to maketype_ll1:
not for direct app use */
int maketyp_ll1(int
info_offset,
LL1type *typep);
/* application uses the
following to make a list header.
The app needs to make the LL1type first,
using the maketype_ll1 macro above */
int make_ll1(LL1type *typep, /* ptr to LL1type variable filled in by
maketype_ll1 */
LL1 *hdrp); /*
ptr to LL1 object being made */
/* for scanning lists: make
a LL1hand at position BOL with inithandle_ll1,
then do a loop of next_ll1's */
int inithandle_ll1(LL1 *lh, /* list object */
int initcase, /* position: BOL, HOL, EOL */
LL1hand
*handle); /* resulting LL1hand filled
in */
/* returns ptr to current
LEO, or NULL if at BOL or EOL */
Ptr current_ll1(LL1hand
*handle);
/* returns Ptr to LEO or 0
at EOL/empty list */
Ptr next_ll1(LL1hand
*handle);
/* insert the LEO in the
list just before the current position (CURR),
or at EOL/HOL */
int insert_ll1(LL1hand
*handle, /* handle */
Ptr q,
/* put this wrapped rec
in */
int
position); /* CURR, HOL or EOL */
/* delete the LEO at HOL or
CURR */
Ptr delete_ll1(LL1hand
*handle,
int position); /* HOL or CURR */
::::::::::::::
ll2.h
::::::::::::::
/* LL2 header--supplied
header for 2-way linked lists
(also known as doubly-linked lists)
Requires user-supplied header file inclusion
following this one
to define one or more list-elment objects
(LEOs) that are to sit
on 2-way linked lists such as this.
*/
/* 4 structs with
LL2-private fields--the application should not
access the members of these 4 structs (this
is done by the LL2 code)
*/
/* The 2-way list
pointers--include in each LEO struct
*/
typedef struct {
Ptr nextp;
Ptr prevp;
} LL2info;
/* This struct contains the
offset of the list pointers (LL2info) in
each LEO (there might be other LL2's going
through each LEO.)
A variable of this type will be placed in
global data (typically)
of the app using these LL2s, and will be
filled in by the
maketype_ll2 macro below.
*/
typedef struct {
int info_offset;
} LL2type;
/* the list header filled in
by make_ll2 below */
typedef struct {
int info_offset;
LL2info head;
Ptr returncell; /* 0 to mark return to home */
Ptr origin; /*
save ptr passed to make */
} LL2;
/* The handle (cursor)
object filled in by inithand_ll2 below,
also filled in by corner_ll2. This is what tells us where
we are in an LL2 list, while scanning it, or
cornering onto it */
typedef struct {
int info_offset; /* offset of the list pointers (LL2info) in each LEO */
Ptr currp; /*
current LEO pointer (offset to info) */
char status; /*
flag for special cases */
LL2 *headerp; /*
pointer to header record of list */
} LL2hand;
/* The application uses the
following macro to set up a LL2type variable
(holding offset information), before making
any list headers.
The point is we need to know the offset of
the list-pointers in the LEO
before creating list headers.
The macro parameters are:
LEO_TYPE--the application's LEO struct type,
e.g. LCB;
INFO_FIELD--within LEO_TYPE, the LL2info
member name, e.g. waitqinfo;
LL2TYPE_PTR--the pointer to the LL2type
variable being filled in here.
*/
#define
maketype_ll2(LEO_TYPE,INFO_FIELD,LL2TYPE_PTR) \
{ LEO_TYPE *trec; trec = (LEO_TYPE
*)0; \
maketyp_ll2(((Ptr)&trec->INFO_FIELD - (Ptr)trec),LL2TYPE_PTR); }
/* used by maketype_ll2
macro: not for direct use by application */
int maketyp_ll2(int
info_offset,
LL2type *typep);
/* The application uses the
following to make a list header. The app needs
to make the LL2type first, using the
maketype_ll2 macro above.
*/
int make_ll2(LL2type *typep, /* ptr to LL2type var filled in by
maketype_ll2 */
LL2 *hdrp); /*
ptr to LL2 object being made */
/* the app can query the
handle to see if it is at beginning of end of list */
#define bol_ll2(handle) (((LL2hand *)(handle))->status==HAND_BOL)
#define eol_ll2(handle) (((LL2hand *)(handle))->status==HAND_EOL)
/* for scanning lists: make
a LL2hand at position BOL with inithandle_ll2,
then do next_ll2's, or start at EOL and do
prev_ll2's or ... */
int inithandle_ll2(LL2
*hdrp, /* list object */
int initcase, /* BOL, HOL, or EOL */
LL2hand
*handle); /* resulting LL2hand
filled in */
/* returns ptr to current
LEO, or NULL if at BOL or EOL */
Ptr current_ll2(LL2hand
*handle);
/* returns Ptr to LEO or 0
at EOL */
Ptr next_ll2(LL2hand
*handle);
/* returns Ptr to LEO or 0
at BOL */
Ptr prev_ll2(LL2hand
*handle);
/* initialize a handle from
an LEO pointer, for scanning from a
given list entry. Called "corner" because it can be
used to scan
along one type of list to a certain LEO, and
then pick up and
scan along another list through the same
LEO, like turning a
corner from one list to another */
int corner_ll2(LL2type
*typep, /* ptr to LL2type var filled in
by maketype_ll2 */
Ptr leop, /* LEO pointer */
LL2hand
*handle); /* resulting LL2hand filled
in */
/* insert the list entry in
the list just before the current position (CURR),
or at HOL or EOL */
int insert_ll2(LL2hand *handle, /* handle */
Ptr q,
/* put this LEO in */
int position); /* HOL, CURR or EOL */
Ptr delete_ll2(LL2hand
*handle, /* handle */
int position); /* HOL or CURR */
::::::::::::::
test_ll2.c
::::::::::::::
/* sample program for EDT
LL2 lists: a list of ints */
#include "edt.h"
#include "ll2.h"
#include <stdio.h>
/* set up an element struct
with an LL2info struct inside it */
/* put the "info"
structs first in the element layout */
typedef struct myelement {
LL2info myinfo;
int x;
} MyElement;
int main()
{
/* note that all these objects are on the stack: no mallocs are
needed! */
LL2type mytype; /* type
information struct */
LL2 mylist; /* list
header struct */
MyElement y; /* an
app element object */
LL2hand hand; /* a
list handle for insert and retrieval */
MyElement *p; /* for
looking at the element after it's in the list */
maketype_ll2(MyElement, myinfo, &mytype); /* fill in mytype
*/
make_ll2(&mytype, &mylist); /* fill in mylist */
y.x = 6; /* put an int
into an MyElement type */
/* set up a handle at EOL for insert */
inithandle_ll2(&mylist, EOL, &hand);
/* do insert (no copy of element done here) */
insert_ll2(&hand, (Ptr)&y, EOL);
/* now y is in the list */
/* reset handle at BOL */
inithandle_ll2(&mylist, BOL, &hand);
/* scan list with next and get element pointer (same as &y)
*/
p = (MyElement *)next_ll2(&hand);
printf("Got back %d, at p = %x, y at %x\n", p->x,
(int)p, (int)&y);
/* should be 6, then same address for p and &y */
}
::::::::::::::
ht.h
::::::::::::::
/* ht.h--closed hashing,
using an array passed in from app code
The array entries need no overhead pointers,
but the hashtable
manager does need to know where the key is
in the array entry, and
needs its own per-entry data to keep track
of entries in use
For cs734, assume keys are ints */
/* 3 structs with HT-private
fields--the application should not
access the members of these 3 structs (this
is done by the HT code) */
/* This struct contains the
offset of the key field in array entry
A variable of this type will be placed in
global data (typically)
of the app using these HTs, and will be
filled in by the
maketype_ht macro below. (Example:
lm.didHTtype)
*/
typedef struct {
int rec_size;
int key_offset,key_size;
} HTtype;
/* partial struct
declaration so we can use "struct httag *ht"
before struct httag is fully declared */
struct httag;
typedef int
(*PHashFn)(struct httag *ht, Ptr key);
/* The hash table manager
object. The user sets up an array and
also
one of these to manage it. It is filled in by make_ht, below.
(Example: lm.didHT for app's array
lm.didHDR)
*/
typedef struct httag {
HTtype *type;
int nbuckets;
int rec_size;
PHashFn hash;
int key_offset,key_size;
Ptr htdata; /*
address of array being managed */
int *status; /* status array--one entry for each
array entry */
} HT;
/* The handle (cursor)
object filled in by inithand_ht below,
also filled in by corner_ht. This is what tells us where
we are in the array, while scanning it, or
cornering onto it */
typedef struct {
HT *hdr; /*
header (pointer) for HT */
int status; /*
HAND_UNK/BOL/EOL/CURR/NEW, see edt.h */
int bucket;
} HThand;
/* The application uses the
following macro to set up a HTtype variable, before
making any hash table manager (HT)
objects. The parameters are:
ARRAY_ENTRY_TYPE--the application's array
entry type, for example Didtblentry
KEY_FIELD--within ARRAY_ENTRY_TYPE, the
member name of the key, for ex. "did"
HT_TYPEP--the pointer to the HTtype variable
being filled in here
*/
#define
maketype_ht(ARRAY_ENTRY_TYPE,KEY_FIELD,HT_TYPEP) { \
ARRAY_ENTRY_TYPE rec[1];
maketyp_ht(sizeof(rec), \
((char *)&rec->KEY_FIELD - (char
*)rec),sizeof(rec->KEY_FIELD),HT_TYPEP); }
/* called by maketype_ht
macro--not for direct app use */
int maketyp_ht(int rec_size,
int key_offset,
int key_size,
HTtype *typep);
/* The app uses the
following to make an HT object, i.e., a hash table
manager for the application-supplied array,
passed here into make_ht.
The app needs to make the HTtype variable
first, using the maketype_ht
macro above.
*/
int make_ht(HTtype
*typep, /* result from maketype_ht */
int nbuckets, /* # elements in the array (prime) */
void *array, /* the array itself */
HT *ht); /* pointer to the resulting
HT object */
/* for return values from
locate_ht */
#define HT_NEW 1
#define HT_OLD 2
#define HT_ERROR -1
/* locate_ht returns an
array index for an old key or a new index for
a new key.
The return value is HT_NEW if new key, HT_OLD if old key,
HT_ERROR if the hash table is full. Note: the application must call
insert_ht to make a new key's index (and
array element) officially in-use
*/
int locate_ht(HT *ht, /* ptr to the hash table manager object */
int *key, /* key */
int *iptr); /* resulting index to use in array */
/* mark the index'th entry
of the array as in-use */
int insert_ht(HT *ht, /* ptr to the hash table manager object */
int
index); /* array index previously
assigned via locate_ht */
/* mark the index'th entry
of the array as not-in-use */
int delete_ht(HT *ht, int
index);
/* for scanning the HT: call
inithandle_ht, then next_ht in a loop */
int inithandle_ht(HT
*ht, /* ptr to the hash table manager
object */
HThand
*handle); /* ptr to filled-in HThand
variable */
/* step to next in-use HT
entry */
Ptr next_ht(HThand
*handle); /* returns ptr to array entry
*/
/* return current HT entry
in HT scan */
Ptr current_ht(HThand
*handle); /* returns ptr to array entry */
/* use an index to start up
a handle */
int corner_ht(HT *ht, int
index, HThand *handle);
::::::::::::::
test_ht.c
::::::::::::::
/* sample program for EDT HT
mapping of ints to ints */
#include "edt.h"
#include "ht.h"
#include <stdio.h>
/* set up a table element
struct with domain and range elements in it */
typedef struct mytablement {
int x;
/* domain element */
int y;
/* range element */
} MyTabElement;
/* set up a table of these
elements, to be the hash table array */
#define N_TAB_ELTS 10
MyTabElement
mytable[N_TAB_ELTS];
int main()
{
/* note that all these objects are on the stack: could be
elsewhere of course */
HTtype myHTtype; /* type
information struct */
HT myHTobject; /*
individual HT object, points internally to mytable */
int x = 6; /* a
domain value */
int y = 10; /* a
range value for x */
int i; /* a
table index in mytable for the domain value */
int i1; /*
another table index */
HThand hand; /* a
handle for HT scan */
MyTabElement *p; /* an
element pointer for HT scan result */
maketype_ht(MyTabElement, x, &myHTtype); /* fill in
myHTtype */
make_ht(&myHTtype, N_TAB_ELTS, mytable,
&myHTobject); /* fill in myHTobject
*/
/* hash the 6 to some location i in the table */
if (locate_ht(&myHTobject, &x, &i) != HT_NEW) {
printf("problem with HT, this should be a new
element for table\n");
return 1;
}
mytable[i].x = x; /*
fill in mytable[i], hash table entry for x = 6 */
mytable[i].y = y;
if (insert_ht(&myHTobject, i) < 0) { /* claim spot i in HT */
printf("problem with HT insert\n");
return 2;
}
/* refind by locate-- */
if (locate_ht(&myHTobject, &x, &i1) != HT_OLD) {
printf("problem with HT, this should be an old
element for table\n");
return 3;
}
if (i != i1) {
printf("problem with HT, should get same i for same
x\n");
return 4;
}
/* set up a handle (at BOL) for scan of HT */
inithandle_ht(&myHTobject, &hand);
/* call next to get to first and only filled-in element here */
/* need to skip over unfilled-in spots */
while (p = (MyTabElement *)next_ht(&hand)) {
switch (hand.status) {
case HAND_NEW: break; /* not filled in yet */
case HAND_EOL: printf("shouldn't get here, since p
== 0 here\n");
break;
case HAND_CURR: printf("Got
back x = %d, y = %d\n", p->x, p->y);
/* should be 6 and 10 */
break;
default: printf("problem with HT\n");
}
}
return 0;
}
::::::::::::::
lm.h
::::::::::::::
/* lm.h: lock manager API */
#define LOCK_READ 1
#define LOCK_WRITE 2
#define NOWAIT 0
#define WAIT 1
#define DEADLOCK 2
#define TID_WAITING (-1)
#define BAD_LOCKTYPE (-2)
/* initialize lock manager
*/
void initlm(void);
/* lock: main entry point of
lock manager.
lktype gives function to do:
LOCK_READ:
set read lock on this rid for this tid
LOCK_WRITE: set write lock on this rid for
this tid
return value:
NOWAIT: successfully obtained the requested
lock
WAIT:
this transaction now needs to wait for a lock
DEADLOCK:
this transaction has been aborted
BAD_LOCKTYPE: lktype has unknown val (caller
error)
TID_WAITING: this tid is already waiting
(caller error)
*/
int lock(int lktype,
int tid,
int rid);
/* drop all locks for this
transaction. Called by TM at commit or
abort */
int droptxlocks(int tid);
/* print out lm data
structures */
void dump_lm(void);
::::::::::::::
lm_private.h
::::::::::::::
/* lm_private.h: Private
header for lock manager */
/* actual size of HDR hash
tables--required to be a prime number */
#define MAXDIDS 397 /* or 10007 */
#define MAXTIDS 99
/* the didHDR entry for a
data item on which locks are held-- */
/* waitqhand is kept here to
save the cost of inithandle on
each call--could be local otherwise */
typedef struct {
int did; /* data item id */
int latch; /* placeholder, not in use yet
*/
LL2 waitqhdr; /*
waitqhead/tail, etc. */
} Didtblentry;
/* the tidHDR entry for
transaction tid requesting locks-- */
typedef struct {
int tid; /* transaction id */
LL1 txlisthdr; /* list of locks for this tid */
int waitflag; /* true if this tx waiting on a
lock */
int visited; /* for current cycletest support
(outmoded) */
} Tidtblentry;
/* the LCB data--for one
lock (R or W) for one tid, one did */
typedef struct {
int tid;
int did; /* could be optimized away
*/
int hold;
/* true if this lock is held by this tx */
int lockmode; /* LOCK_READ or
LOCK_WRITE */
int didHDRidx, tidHDRidx; /* for ease of lookup in HDR arrays */
} LCBdata;
/* the whole LCB, the data
part wrapped up in a larger record */
typedef struct {
LL2info
waitqinfo; /* waitq next-pointer, prev-pointer */
LL1info txlistinfo; /* txlist
next-pointer */
LCBdata dat; /* lock entry itself, see just above */
} LCB;
/* Next is the global data
needed for the whole lock manager */
/* The "xxxtype"
members hold information about the next-pointer offsets,
etc., i.e., technical details for the data
structure code */
/* There are two big arrays,
didHDR and tidHDR, holding info on individual
data-items and transactions,
respectively. Each big array is managed
by a hash-table manager, represented here by
didHT and tidHT.
Thus to locate the right entry in tidHDR to
use for a certain tid,
call
locate_ht(lm.tidHT, tid, &tidHDRidx); This will fill in tidHDRidx,
the index to use in tidHDR. */
typedef struct {
HTtype didHTtype,tidHTtype; /* the types of the two hash tables */
LL2type waitqtype; /* waitq type, for corner onto waitlist */
HT didHT,tidHT; /* the two hash table manager objects */
Didtblentry didHDR[MAXDIDS]; /* the array of data-item headers */
Tidtblentry tidHDR[MAXTIDS]; /* the array of transaction (tx) headers */
} LM;
/* for fatal errors */
#define fatal(STR) {
(void)printf(STR); assert(0); }
::::::::::::::
lm.c
::::::::::::::
/* lock manager source file
*/
/* Copyright 1991, 2002 by
Elizabeth J. and Patrick E. O'Neil */
#include <stdio.h>
#include <assert.h>
#include <malloc.h>
#include "edt.h"
#include "ll1.h"
#include "ll2.h"
#include "ht.h"
#include "lm.h"
#include
"lm_private.h"
#include "wfg.h"
/* turn this on for debug
info printing */
/* #define TRACE */
/* Note: Text related to
read/write locks starts with "RW:" so you can
locate it easily. All spots needing RW edits are marked this
way.
However, no such help is provided for the WFG
assignment. */
/* Note: works properly with
exclusive locks if RW *not* defined */
/*#define RW */
/* lock-manager-private
functions
These are listed in call-down order, for
example, handle_conversion calls
only functions listed below its own prototype. The C code for
these functions is also in this order,
starting after the code
for init_lm and lock (themselves external
functions prototyped in lm.h)
*/
static int is_waiting(int
tid);
static int add_to_txlist(int
tid, LCB *lp);
static int add_to_waitq(int
lockmode, int tid, int did, LCB **lpp);
static LCB * find_held_lock(
LL2hand *waitqhandp, /* start from here in
waitq */
int tid); /*
tid we're looking for */
static int setup_txlist(int
tid, int * tidHDRidxp);
#ifdef RW
static int
ck_for_writer(LL2hand *waitqhandp);
static int
handle_conversion(int tid, /* the tid wanting conversion from R to W lock */
int didHDRidx, /* didHDR[didHDRidx] is init. with waithand at HOL */
LCB *oldlp, /* the tid's old read lock */
LCB **newlpp); /* returned: the tid's
write lock */
#endif
static int
delete_all_by_tid(int tid);
static void
delete_from_waitq(LCB *lp);
static int
delete_from_waitq_by_waitqhand(LL2hand *waitqhandp);
#ifdef RW
static int
adjust_readlocks(LCB *firstlp);
static void
analyze_scan_waitq(
LL2hand *waitqhandp, /* scan from here to 1st writer or EOL */
int *readercountp, /* returned count of readers before first
writer */
LCB **writerlpp); /* returned ptr to first writer */
#endif
static LCB * new_LCB(int
tid, int did, int didHDRidx, int lockmode, int hold);
#ifdef WFG
/* Suggested helpers for WFG
*/
static int
find_waiters (LL2hand *waitqhandp,
LCB **ppfirst,
LCB **pplast);
static int
find_waitees (LL2hand *waitqhandp,
LCB **ppfirst,
LCB **pplast);
#endif
/* useful for debugging */
static void dump_waitq(int
did);
static void
dump_transaction(int tid);
/* the lock manager master
data struct-- */
static LM lm; /* All the data structures are
in this */
/* waitqs are kept in
waits-for order, so that the holders of the
lock come before the waiters.
RW: In the RW case, there are two cases of
waitqs: ([ ] means optional)
--one held W: W hold, [waiters]
--one or more held Rs: R hold, R hold, ..., R hold, [W wait ...
waiters]
In the second case, the first W may have the
same tid with one of
*multiple* Rs. We avoid "R hold, W wait
[waiters]" with same-tid R and W
by converting the R to a W and discarding
the W as soon as the number
of Rs goes to one. The case of multiple same-tid R-W pairs is
not
permitted, because as soon as this happens,
it is a deadlock and the
tid with the second pair is aborted by
cycletest.
*/
/* initialize lock manager
data structures */
void initlm()
{
int i;
LL1type txlisttype;
initwfg(lm.waitqtype); /* init WFG
handling */
/* fill in global lm struct, the whole lock manager data
structure-- */
maketype_ht(Didtblentry,did,&lm.didHTtype);
maketype_ht(Tidtblentry,tid,&lm.tidHTtype);
if (make_ht(&lm.didHTtype, MAXDIDS, lm.didHDR,
&lm.didHT)<0)
fatal("Failed to make did HT manager\n");
if (make_ht(&lm.tidHTtype, MAXTIDS, lm.tidHDR,
&lm.tidHT)<0) /* and lm.tidHT */
fatal("Failed to make tid HT manager\n");
/* initialize a type of waitq's all using LL2info
waitqinfo's
offset in LCB for next-- */
maketype_ll2(LCB,waitqinfo,&lm.waitqtype); /* global type
vars */
/* loop thru HDR arrays, initializing them */
for (i=0; i<MAXDIDS; i++) {
make_ll2(&lm.waitqtype, &lm.didHDR[i].waitqhdr);
/* waitq header */
}
maketype_ll1(LCB,txlistinfo,&txlisttype); /* type just
needed here */
for (i=0; i<MAXTIDS; i++) {
make_ll1(&txlisttype, &lm.tidHDR[i].txlisthdr);
/* txlist header */
/* init handle to EOL, same as if just deleted last on
txlist-- */
}
}
/* return codes from
add_to_waitq-- */
/* found old lock instance
record (LCB) with same did and tid-- */
#define MATCHED_OLD_LCB 1
/* set up new LCB for this
did and tid-- */
#define MADE_NEW_LCB 2
/* non-0 return code by
delete_all_by_tid--transaction not found-- */
#define NO_TRANS 1
/* main entry point of lock
manager. lockmode gives function to do:
LOCK_READ:
set read lock on this did for this tid
LOCK_WRITE: set write lock on this did for
this tid
return value:
NOWAIT: successfully obtained the requested
lock
WAIT:
this transaction now needs to wait for a lock
DEADLOCK:
this transaction has been aborted
BAD_LOCKTYPE: lktype has unknown val (caller
error)
TID_WAITING: this tid is already waiting
(caller error)
*/
int lock(int lockmode,
int tid,
int did)
{
LCB *lp;
int
tidHDRidx;
/* provided cycletest linkage--replace this! */
extern int cycletest();
/* old C declaration: expect warning on compile */
/* references to functions in adj_glue.c--virtual graph
primitives
accessing lockmgr's txlists and waitqs in waits-for
relationship,
so that general cycletest algorithm can detect waits-for
cycles-- */
extern int bol_vert(void),set_vert_mark(void),get_vert_mark(void),bol_adj(void);
extern int fin_vert(void),fin_adj(void);
extern Ptr next_vert(void),next_adj(void);
/* end of provided cycletest linkage to be removed */
printf("Got to lock fn, with locktype = %d, tid = %d, did
= %d\n",
lockmode, tid, did);
switch (lockmode) {
case LOCK_READ:
#ifndef RW
/* without RW edits,
all locks are the same */
lockmode =
LOCK_WRITE;
#endif
case LOCK_WRITE:
/* first check if this transaction is waiting */
if (is_waiting(tid))
return TID_WAITING;
/* caller error */
/* create new txlist if nec. */
setup_txlist(tid, &tidHDRidx); /* WFG:
add node */
/* add to waitq, converting lock if approp.*/
switch (add_to_waitq(lockmode,tid,did,&lp)) {
case MATCHED_OLD_LCB: break; /* nothing much to do--matched
did and tid */
case MADE_NEW_LCB:
if (add_to_txlist(tid,lp)==TID_WAITING) { /* put on
appropriate txlist */
fatal("earlier waiting-tid check is
ineffective\n");
}
if (!lp->dat.hold && cycletest(tid, /* WFG: cycletest, compare to old one */
/* for
debugging help */
(Ptr)&lm,bol_vert,next_vert,fin_vert,
set_vert_mark,get_vert_mark,
bol_adj,next_adj,fin_adj)) {
return DEADLOCK;
}
break;
default:
fatal("Unknown return from add_to_waitq\n");
}
/*
end switch OLD/NEW */
return lp->dat.hold==1?NOWAIT:WAIT;
break; /*
end case LOCK_READ/WRITE */
default: return BAD_LOCKTYPE;
}
assert(0); /* not
reached */
}
int droptxlocks(int tid)
{
(void)delete_all_by_tid(tid); /* allow case
of none there */
return 0;
}
/* Called from lock()
Determine if this transaction is waiting.
Returns 1 if waiting, 0 if not
*/
static int
is_waiting(int tid)
{
int tidHDRidx; /* spot
in tidHDR array */
/* locate tid in its HT-- */
switch (locate_ht(&lm.tidHT, &tid, &tidHDRidx)) {
case HT_NEW:
return 0;
case HT_OLD: /*
this transaction has locks already */
return lm.tidHDR[tidHDRidx].waitflag;
default:
fatal("Error ret from locate_ht\n");
}
assert(0); /* can't
reach this */
return 0;
}
/* called from lock() */
/* create txlist if
necessary */
static int
setup_txlist(int tid, int *
tidHDRidxp)
{
int tidHDRidx; /* spot in tidHDR array */
int status;
#ifdef TRACE
printf(" setup_txlist: tid %d\n",
tid);
#endif
/* locate tid in its HT-- */
switch (status = locate_ht(&lm.tidHT,
&tid, &tidHDRidx)) {
case HT_NEW:
lm.tidHDR[tidHDRidx].tid = tid;
lm.tidHDR[tidHDRidx].waitflag = 0;
if (insert_ht(&lm.tidHT, tidHDRidx) < 0) /* claim HT slot */
fatal("tx insert failed\n");
break;
case HT_OLD: /* this transaction has locks already */
break;
default:
fatal("Error ret from locate_ht\n");
}
*tidHDRidxp = tidHDRidx;
return status;
}
/* called from lock() */
/* Drop lp's LCB into txlist
for tid */
static int
add_to_txlist(int tid,
LCB *lp)
{
int tidHDRidx; /* spot
in tidHDR array */
LL1hand txlisthand;
#ifdef TRACE
printf(" add_to_txlist: tid %d\n", tid);
#endif
/* locate tid in its HT-- */
switch (locate_ht(&lm.tidHT, &tid, &tidHDRidx)) {
case HT_NEW:
fatal("Should have txlist made by
setup_txlist\n");
case HT_OLD: /*
this transaction has locks already */
if (lm.tidHDR[tidHDRidx].waitflag)
return TID_WAITING;
lm.tidHDR[tidHDRidx].waitflag = !lp->dat.hold; /* new
trans. state */
inithandle_ll1(&lm.tidHDR[tidHDRidx].txlisthdr,EOL,&txlisthand);
if (insert_ll1(&txlisthand,(Ptr)lp,EOL)) /* at end of
txlist */
fatal("transaction insert failed\n");
lp->dat.tidHDRidx
= tidHDRidx; /* for LCB, back ptr to tid's HT entry */
break;
default:
fatal("Error ret from locate_ht\n");
}
lp->dat.tidHDRidx = tidHDRidx; /* save tidHDRidx for convenient lookups */
return 0;
}
/* Called from lock():
create LCB (if necessary) and put on waitq.
Hashes thru didHT to proper slot for did,
examines its waitq's
first LCB if there for special case that this
lock is already
held by this tid, in which case it returns
OLD with that matched
LCB pointer.
Else it breaks out a new LCB, puts it in the waitq
and returns the new LCB pointer. Does not add new LCB to txlist.
*/
static int add_to_waitq(int
lockmode,
int tid,
int did,
LCB **lpp) /*
new or old, matched by tid and did */
{
LCB *lp,*oldlp; /* ptrs to LCBs */
int hold;
int didHDRidx; /* spot in didHDR array */
LL2hand waitqhand;
#ifdef TRACE
printf(" add_to_waitq: lk %d, tid %d did
%d\n",lockmode, tid, did);
#endif
/* hash did via its HT, obtain didHDRidx for use in didHDR
array */
switch (locate_ht(&lm.didHT, &did, &didHDRidx)) {
case HT_NEW: /*
no problem, just set up house here */
lm.didHDR[didHDRidx].did = did;
lp = new_LCB(tid,did,didHDRidx,lockmode,/*hold*/ 1);/*
new LCB, hold=1 */
inithandle_ll2(&lm.didHDR[didHDRidx].waitqhdr,EOL,&waitqhand); /* make cursor at EOL */
if (insert_ll2(&waitqhand,(Ptr)lp,EOL)<0) /* only
one on waitq */
fatal("waitq insert failed\n");
if (insert_ht(&lm.didHT, didHDRidx)<0) /* claim new spot in HT */
fatal("HT insert failed\n");
break;
case HT_OLD: /*
this did has locks already */
/* position to first on waitq-- */
inithandle_ll2(&lm.didHDR[didHDRidx].waitqhdr,HOL,&waitqhand);
if ((lp = (LCB *)current_ll2(&waitqhand))==(LCB *)0)
fatal("OLD did has null waitq\n");
if (lp->dat.hold != 1)
fatal("First LCB on waitq doesn't hold
lock\n");
/* if this tid already holds a lock-- */
if ((oldlp = find_held_lock(&waitqhand,tid))) { /*
try to find it */
#ifdef RW
/* RW: EDIT
1
The
situation: We have just determined that this tid already
holds a
lock, with LCB at oldlp. So it is
requesting a new
lock when
it already has a lock on the did. In the RW case,
we have to
specially handle the case of old lock R, new lock W, a
lock
"conversion", because a W lock is stronger than an R lock.
On the
other hand, if the old lock, new lock combo is R, R
or W, R or
W, W, no special handling is needed.
Action to
do: Check if the new lock is a W and the old lock
for this
tid is an R, and if so call helper function
"handle_conversion" for this tid, did, and oldlp, and get back
enough
info to determine *lpp and whether to return
MATCHED_OLD_LCB or MADE_NEW_LCB from here. In the other
three
cases (R R, etc.) just return oldlp as an old LCB,
i.e., the same
old treatment.
*/
#else /* excl-locks code */
*lpp = oldlp; /*
found old matching lock */
return MATCHED_OLD_LCB;
#endif
}
hold = 0;
#ifdef RW
/* RW: EDIT 2
The
situation: We are about to create a new
LCB for this
lock request for
a did that already has a waitq, but doesn't
yet have any
LCBs for *this* tid on the waitq. We
need
to put it at the
end of the waitq whether or not it's a W or
an R. The question is: what value of hold to use?
Action to do: Check the waitq to see if the
new LCB can share an
R lock or not,
and set hold value appropriately.
*/
#endif
lp = new_LCB(tid,did,didHDRidx,lockmode,hold); /* make
new LCB */
if (insert_ll2(&waitqhand,(Ptr)lp,EOL)) /* put at end
of waitq */
fatal("waitq insert failed\n");
break;
default:
fatal("Error ret from locate_ht\n");
}
*lpp = lp; /*
return new LCB */
/* WFG: if new lock
requires wait, add edges to WFG here */
return MADE_NEW_LCB; /*
put in new LCB */
}
/* helper to add_to_waitq,
above */
/* Look thru holders of lock
for ones belonging to tid, return
ptr to LCB or null if none */
static LCB *
find_held_lock(LL2hand
*waitqhandp, /* start from here in waitq
*/
int tid) /* tid we're looking for */
{
LCB *lp;
LL2hand waitqhand;
#ifdef TRACE
printf(" find_held_lock: tid %d\n",tid);
#endif
waitqhand = *waitqhandp; /*
local copy of handle */
lp = (LCB *)current_ll2(&waitqhand); /* start with this one
*/
do {
if (lp->dat.tid == tid) return lp;
} while ((lp=(LCB *)next_ll2(&waitqhand)) &&
lp->dat.hold);
return (LCB *)0; /*
not held */
}
#ifdef RW /* RW:
EDIT 3 */
/* helper to add_to_waitq,
above */
/* check rest of waitq for
writer, return 1 if found */
static int
ck_for_writer(LL2hand *waitqhandp)
{
return 0; /*stub: no writers found */
}
/* Called from to
add_to_waitq, above RW: EDIT 4 */
/* This tid has a read lock,
wants a write lock. If it's the only reader,
convert R to W in place and return
MATCHED_OLD_REC.
Else put new write LCB behind readers, making
this transaction wait,
and return MADE_NEW_REC. (Later, this transaction will
convert the readlock to a writelock.) Here we don't set
the transaction's waitflag (the calling code
will do that),
just mark the new lock as not held.
WFG:
If there is a W after the the new W, its WFG edges need to be
repointed to the new W, i.e., There can't be an R after the new W (yet)
because we've put this W after the R's that
were there.
*/
static int
handle_conversion(int tid, /* the tid wanting conversion of
R to W */
int
didHDRidx, /* for the did */
LCB *oldlp, /* the tid's old read lock */
LCB
**newlpp) /* returned: the tid's resulting write lock */
{
return 0; /* stub */
}
#endif /* RW */
/* called from lock() and
commit(): delete all LCBs and txlist for tid */
static int
delete_all_by_tid(int tid)
{
LCB *lp;
int tidHDRidx; /* spot
in tidHDR array */
LL1hand txlisthand; /*
cur position (at head of list) on txlist during delete loop */
#ifdef TRACE
printf(" delete_all_by_tid: tid %d\n", tid);
#endif
/* locate tid in its HT-- */
switch (locate_ht(&lm.tidHT,&tid, &tidHDRidx)) {
case HT_NEW:
return NO_TRANS; /*
bad tid given? */
case HT_OLD:
while
(inithandle_ll1(&lm.tidHDR[tidHDRidx].txlisthdr,HOL,
&txlisthand)>=0) {
lp = (LCB
*)current_ll1(&txlisthand);
delete_from_waitq(lp); /*
if (!delete_ll1(&txlisthand,CURR)) /* and on
txlist */
fatal("Delete of txlist entry
failed\n");
free(lp);
}
if (delete_ht(&lm.tidHT, tidHDRidx)<0)
fatal("Delete of trans HT entry
failed\n");
break;
default:
fatal("Error ret from locate_ht\n");
}
/* WFG: need to
delete node for tid */
return 0;
}
/* success returns from
delete_from_waitq_by_waitqhand-- */
/* deleted last LCB from
waitq, so need to delete hash entry-- */
#define DELETED_LAST 1
/* left non-triv waitq--*/
#define DELETED_NONLAST 2
/* Helper to
delete_all_by_tid, above */
/* Delete lp's LCB, and, if
last for did, the did's HT entry too.
Promote appropriate
waiters.
After this, the LCB is still on the txlist */
static void
delete_from_waitq(LCB *lp)
{
LL2hand waitqhand;
#ifdef TRACE
printf(" delete_from_waitq\n");
#endif
if (corner_ll2(&lm.waitqtype,(Ptr)lp,&waitqhand)<0)
/* corner onto waitq */
fatal("Corner onto waitq failed\n");
/* delete LCB, and if held lock, promote waiters-- */
switch (delete_from_waitq_by_waitqhand(&waitqhand)) {
case DELETED_NONLAST: break; /*
leave nontrivial waitq as is */
case DELETED_LAST: /*
empty waitq, so delete did entry */
delete_ht(&lm.didHT, lp->dat.didHDRidx); /*free up
did entry in didHDR */
break;
default: fatal("Unknown return from
delete_from_waitq_by_waitqhand\n");
}
}
/* Delete current LCB of
waitqhandp from waitq and, if held lock, promote
waiters as appropriate. (This leaves the LCB
on the txlist) */
static int
delete_from_waitq_by_waitqhand(LL2hand
*waitqhandp)
{
LCB *dellp,*firstlp, *prevlp;
LL2hand waitqhand = *waitqhandp; /* use local copy of waitqhand */
LL2hand waitqhand1;
int tidHDRidx;
#ifdef TRACE
printf(" delete_from_waitq_by_waitqhand\n");
#endif
/* WFG: need to
delete WFG edges to/from this LCB */
dellp = (LCB *)delete_ll2(&waitqhand,CURR); /* take out of
waitq */
if ((firstlp = (LCB *)current_ll2(&waitqhand)) == (LCB *)0)
{
/* nothing after this one--is it now completely empty? */
if (prev_ll2(&waitqhand))
return DELETED_NONLAST; /*something left, but all before this one */
else
return DELETED_LAST; /* nothing left on waitq */
}
/* here with locks after deleted one on waitq--work on them if
nec. */
waitqhand1 = waitqhand;
/* don't change waitqhand */
prevlp = (LCB *)prev_ll2(&waitqhand1); /* to get prevlp */
#ifdef RW
/* RW: EDIT 5 */
/* some cases to
consider-- */
/* W(held, to-be-deleted)-R(waiting)... */
/* W(held, to-be-deleted)-W(waiting) */
/* R(held)-R(held,
to-be-deleted)-W(waiting)<--maybe same tid */
/* R(held, to-be-deleted) - R(held) -
W(waiting) <-- maybe... */
/* compatibles on
either side-- */
/* R(held)-W(waiting, to-be-deleted)-R(waiting)
*/
/*
The situation: We are
deleting a single LCB from a given waitq.
The LCB is specified
by a waitqhand, a cursor on the waitq for
this did. We've already deleted the LCB from the waitq,
so the
waitqhand is now
positioned on the LCB following the deleted
one, or at EOL if none
follow. We have already handled some
cases, so we're left
with the case that there are LCBs after
the deleted one, so
it's possible that we need to unblock
some tids.
Action to do: We have
two jobs to do here:
A. determining new
hold flag values and unblocking LCBs
B. detecting a
convertible R-W of the same tid by its being
at the start of
the waitq, and converting it to a single LCB.
These can be done in
either order. Note that for A., we can
ignore the status of
the deleted LCB if we want (its lockmode
and hold flags), since the status of
later entries is fully
determined by the
waitq contents other than the deleted entry.
Don't forget to
unblock multiple R-locks if appropriate.
*/
#else
/* exclusive locks--no sharing, so simple */
/* all done if prev there, holding or waiting */
if (prevlp)
return
DELETED_NONLAST;
/* here with no prev, so deleted held lock */
assert(dellp->dat.hold == 1);
/* firstlp/waitqhandp is the first LCB left after a deleted
holding writer
(exclusive locks case) */
if (firstlp->dat.hold==1)
fatal("Found
holder after deleting holder\n");
/* Here with locks after deleted one and a lock is actually
freed up.
With exclusive locks,
firstlp/waitqhandp is
the first waiter that
needs to unblock, after a deleted
singleton reader or
writer */
firstlp->dat.hold = 1; /*
promote 1 waiting writer */
tidHDRidx = firstlp->dat.tidHDRidx;
lm.tidHDR[tidHDRidx].waitflag = 0;
#endif
return DELETED_NONLAST;
}
#ifdef RW
/* Helper to delete_from_waitq_by_whand above,
called after a readlock
is deleted from a waitq. Check for read LCB
followed by write LCB
of the same tid at the left end of the waitq
and, in this case,
convert the read LCB to a write LCB and
discard the write LCB.
The firstlp argument points to an LCB that
may be the R or W
of the R-W pair, that is, the first LCB
after the deleted one.
WFG:
Note that after conversion, WFG edges to first (coalesced) lock may be
incomplete--if some R's or one W were
waiting on old W, should now wait on
coalesced LCB.
*/
static void
do_conversion(LCB *firstlp)
/* ptr to first lock after deleted one on waitq */
{
}
/* RW: provided helper
function:
Called from handle_conversion and (possibly)
adjust_readlocks.
Scan waitq, counting readers before the
first writer, and
finding the first writer, if any. Leaves waitqhand positioned
at first writer, if any */
static void
analyze_scan_waitq(
LL2hand *waitqhandp, /*
scan from here to 1st writer or EOL */
int *readercountp, /* returned count of readers */
LCB **writerlpp)
/* returned ptr to first writer
*/
{
int readercount = 0;
LCB *lp;
#ifdef TRACE
printf(" analyze_scan_waitq\n");
#endif
while ((lp=(LCB *)next_ll2(waitqhandp))) {
if (lp->dat.lockmode==LOCK_WRITE) {
*writerlpp = lp; /*
return first writer, holding or waiting */
*readercountp = readercount;
return;
} else if (lp->dat.hold)
readercount++; /*
holding reader */
else fatal("Reader waiting at or near beginning of
waitq\n");
}
/*
end while */
/* here at EOL, i.e., no writers */
*readercountp = readercount;
*writerlpp = (LCB *)0; /* none found */
}
#endif /* RW */
/* Create an LCB and fill in
everything except tidHDRidx, which is added
by add_to_txlist after the waitq editing is
finished. */
static LCB * new_LCB(int
tid,
int did,
int didHDRidx,
int lockmode,
int hold)
{
LCB *lp;
#ifdef TRACE
printf(" new_LCB\n");
#endif
lp = (LCB *)malloc(sizeof(LCB));
lp->dat.tid = tid;
lp->dat.did = did;
lp->dat.didHDRidx = didHDRidx;
lp->dat.lockmode = lockmode;
lp->dat.hold = hold;
return lp;
}
/* Helpers for WFG--add more functions here */
#ifdef WFG
/* WFG: find all waiters on
the CURR LCB on the waitq
* return:
1 -- found waiter(s)
*
0 -- found no waiter
*/
static int
find_waiters (LL2hand *waitqhandp,
LCB **ppfirst,
LCB **pplast)
{
return 0; /*
stub */
}
/* WFG: find all waitees
from the CURR LCB on the waitq
* return:
1 -- found waiter(s)
*
0 -- found no waiter
*/
static int
find_waitees (LL2hand *waitqhandp,
LCB **ppfirst,
LCB **pplast)
{
return 0; /*
stub */
}
#endif
void dump_lm()
{
HThand didhand;
HThand transhand;
Didtblentry *didentry;
Tidtblentry *transp;
printf("********WaitQs***************\n");
inithandle_ht(&lm.didHT, &didhand);
while ((didentry = (Didtblentry *)next_ht(&didhand))) {
if (didhand.status == HAND_NEW)
continue; /*
skip empty ones */
printf("waitq for did %d: ",didentry->did);
dump_waitq(didentry->did);
}
printf("********Transactions*********\n");
inithandle_ht(&lm.tidHT, &transhand);
while ((transp = (Tidtblentry *)next_ht(&transhand))) {
if (transhand.status == HAND_NEW)
continue;
printf("txlist for tid %d [%s]:
",transp->tid,
(transp->waitflag?"waiting":"running"));
dump_transaction(transp->tid);
}
printf("*****************************\n");
}
/* print out LCBs on
waitq--note useful in debugging */
static void
dump_waitq(int did)
{
LL2hand waitqhand;
LCB *lp;
Didtblentry *didentry;
int didHDRidx, tidHDRidx;
locate_ht(&lm.didHT, &did, &didHDRidx);
didentry = &lm.didHDR[didHDRidx];
inithandle_ll2(&didentry->waitqhdr,BOL,&waitqhand);
/* init waitq handle */
while ((lp = (LCB *)next_ll2(&waitqhand))) {
printf("(tid %d, mode %s, hold %d), ",
lp->dat.tid,lp->dat.lockmode ==
LOCK_WRITE?"W":"R",lp->dat.hold);
tidHDRidx = lp->dat.tidHDRidx;
if (!lp->dat.hold &&
!lm.tidHDR[tidHDRidx].waitflag)
printf("!!But tid is running!!");
}
printf("\n");
}
/* print out LCBs on txlist
*/
static void
dump_transaction(int tid)
{
LL1hand txlisthand;
LCB *lp;
Tidtblentry *tidentry; /* HT entry for tid */
int tidHDRidx;
locate_ht(&lm.tidHT, &tid, &tidHDRidx);
tidentry = &lm.tidHDR[tidHDRidx];
inithandle_ll1(&tidentry->txlisthdr,BOL,&txlisthand);
/* init waitq handle */
while ((lp = (LCB *)next_ll1(&txlisthand)))
/* #define BETTER */
#ifdef PRINT_MORE
printf("(tid %d, did %d, mode %s, hold %d, tididx
%d, didHDRidx %d), ",
lp->dat.tid, lp->dat.did, lp->dat.lockmode ==
LOCK_WRITE?"W":"R",
lp->dat.hold, lp->dat.tidHDRidx,
lp->dat.didHDRidx);
#else
printf("(did %d, mode %s, hold %d),
",
lp->dat.did, lp->dat.lockmode ==
LOCK_WRITE?"W":"R",lp->dat.hold);
#endif
printf("\n");
}
::::::::::::::
lmdrive.c
::::::::::::::
/* lmdrive.c: Program to
drive Database System Lock Manager */
#include <stdio.h>
#include "lm.h"
#define BUFLEN 100
int main (void)
{
char locktype; /*
lock type requested by user */
int tid, did; /*
transaction requesting lock, data item id */
int returnv; /*
return value from lock call */
char buf[BUFLEN];
initlm(); /*
initialize lock manager structures */
printf("Initialized empty system:\n");
while (1) { /* loop for user input */
dump_lm();
printf("\nEnter W 2 100 for W(2,100), etc. or C or
Q\n");
if (fgets(buf, BUFLEN, stdin) == 0)
break;
else if (sscanf(buf,"%c", &locktype) != 1)
break;
switch (locktype)
{
case 'W':
case 'R':
if (sscanf(buf, "%c %d %d",
&locktype, &tid, &did) != 3)
printf("bad line: %s\n", buf);
else
printf("%c %d %d\n", locktype, tid,
did);
returnv = lock(locktype=='R'?LOCK_READ:LOCK_WRITE,
tid, did);
break;
case 'C':
case 'A':
if (sscanf(buf, "%c %d", &locktype,
&tid)!= 2)
printf("bad line: %s\n", buf);
else
printf("%c %d\n", locktype, tid);
/* both commit and abort cause all locks to be
dropped */
returnv = droptxlocks(tid);
break;
default: printf("bad
line: %s\n", buf);
}
printf ("the value returned is %d (", returnv);
switch (returnv) {
case NOWAIT: printf("NOWAIT"); break;
case WAIT: printf("WAIT"); break;
case DEADLOCK: printf("DEADLOCK"); break;
case TID_WAITING: printf("TID_WAITING (caller
error)"); break;
case BAD_LOCKTYPE: printf("BAD_LOCKTYPE (caller
error)"); break;
}
printf(")\n");
if (returnv == DEADLOCK) {
printf("Deadlock, so calling droptxlocks for
victim tid %d\n", tid);
droptxlocks(tid);
/* finish abort (after TM work in real system) */
}
}
return 0;
}
::::::::::::::
wfg.h
::::::::::::::
/* wfg.h: wfg manager API */
#define CYCLE 0
#define NO_CYCLE 1
#define ERROR -1
/* initialize wfg manager,
passing waitqtype from lm.c */
void initwfg(LL2type
waitqtype);
/* add a node to the
WFGnode[] in parallel to the tidHDR[]*/
int wfg_addnode(int tid, int
WFGnodeidx);
/* add edges to the WFG with
LCBs from LCB11ptr to LCB12ptr WAITING FOR
LCBs from LCB21ptr to LCB22ptr, ignoring any
same-tid to-from pairs */
int wfg_addedge(LCB
*LCB11ptr, LCB *LCB12ptr, LCB *LCB21ptr, LCB *LCB22ptr);
/* delete edges from the WFG
with LCBs from LCB11ptr to LCB12ptr WAITING FOR
LCBs from LCB21ptr to LCB22ptr */
int wfg_deledge(LCB
*LCB11ptr, LCB *LCB12ptr, LCB *LCB21ptr, LCB *LCB22ptr);
/* delete a node at the end
of abort or commit of a tid by LM */
int wfg_delnode(int tid, int
WFGnodeidx);
/* start a depth-first
search from the tid with subscript WFGnodeidx*/
int wfg_dfs(int tid, int
tidWFGidx);
/* print out WFG data
structures */
void dump_wfg(void);
::::::::::::::
wfg_private.h
::::::::::::::
/* wfg_private.h: Private
header for waits-for-graph manager */
#define TRUE 1
#define FALSE 0
/* the WFGnode entry for
transaction tid requesting/releasing locks-- */
typedef struct {
int tid;
/* transaction id */
LL1 adjlisthdr; /* list of adjacent nodes for this tid */
int visited;
/* for new cycletest support */
} WFGnodeentry;
/* the ALB data--for one tid
and one adjacent tid */
typedef struct {
int tid1;
int tid2;
int tid1WFGidx, tid2WFGidx;
/* for ease of lookup in WFG array */
} ALBdata;
/* the whole ALB, the data
part wrapped up in a larger record with the
necessary list pointers*/
typedef struct {
LL1info adjlistinfo; /* adjlist next-pointer */
ALBdata dat; /* adjacency entry itself, see just above */
} ALB;
/* There is one big array,
WFGnode, parallel to the tidHDR. "parallel" means
that if position of tid 55 is tidHDR[2] then
it is WFGnode[2] in the WFG.*/
typedef struct {
WFGnodeentry WFGnode[MAXTIDS];
/* the array of WFG nodes */
LL2type waitqtype; /* from initialization from lm.c */
} WFG;