servers/vfs/tll.c

   1 /* This file contains the implementation of the three-level-lock. */
   2
   3 #include "fs.h"
   4 #include "glo.h"
   5 #include "tll.h"
   6 #include "threads.h"
   7 #include <assert.h>
   8
   9 static int tll_append(tll_t *tllp, tll_access_t locktype);
  10
  11 static int tll_append(tll_t *tllp, tll_access_t locktype)
  12 {
  13   struct worker_thread *queue;
  14
  15   assert(self != NULL);
  16   assert(tllp != NULL);
  17   assert(locktype != TLL_NONE);
  18
  19   /* Read-only and write-only requests go to the write queue. Read-serialized
  20    * requests go to the serial queue. Then we wait for an event to signal it's
  21    * our turn to go. */
  22   queue = NULL;
  23   if (locktype == TLL_READ || locktype == TLL_WRITE) {
  24         if (tllp->t_write == NULL)
  25                 tllp->t_write = self;
  26         else
  27                 queue = tllp->t_write;
  28   } else {
  29         if (tllp->t_serial == NULL)
  30                 tllp->t_serial = self;
  31         else
  32                 queue = tllp->t_serial;
  33   }
  34
  35   if (queue != NULL) {  /* Traverse to end of queue */
  36         while (queue->w_next != NULL) queue = queue->w_next;
  37         queue->w_next = self;
  38   }
  39   self->w_next = NULL; /* End of queue */
  40
  41   /* Now wait for the event it's our turn */
  42   worker_wait();
  43
  44   tllp->t_current = locktype;
  45   tllp->t_status &= ~TLL_PEND;
  46   tllp->t_owner = self;
  47
  48   if (tllp->t_current == TLL_READ) {
  49         tllp->t_readonly++;
  50         tllp->t_owner = NULL;
  51   } else if (tllp->t_current == TLL_WRITE)
  52         assert(tllp->t_readonly == 0);
  53
  54   /* Due to the way upgrading and downgrading works, read-only requests are
  55    * scheduled to run after a downgraded lock is released (because they are
  56    * queued on the write-only queue which has priority). This results from the
  57    * fact that the downgrade operation cannot know whether the next locktype on
  58    * the write-only queue is really write-only or actually read-only. However,
  59    * that means that read-serialized requests stay queued, while they could run
  60    * simultaneously with read-only requests. See if there are any and grant
  61    * the head request access */
  62   if (tllp->t_current == TLL_READ && tllp->t_serial != NULL) {
  63         tllp->t_owner = tllp->t_serial;
  64         tllp->t_serial = tllp->t_serial->w_next;
  65         tllp->t_owner->w_next = NULL;
  66         assert(!(tllp->t_status & TLL_PEND));
  67         tllp->t_status |= TLL_PEND;
  68         worker_signal(tllp->t_owner);
  69   }
  70
  71   return(OK);
  72 }
  73
  74 void tll_downgrade(tll_t *tllp)
  75 {
  76 /* Downgrade three-level-lock tll from write-only to read-serialized, or from
  77  * read-serialized to read-only. Caveat: as we can't know whether the next
  78  * lock type on the write queue is actually read-only or write-only, we can't
  79  * grant access to that type. It will be granted access once we unlock. Also,
  80  * because we apply write-bias, we can't grant access to read-serialized
  81  * either, unless nothing is queued on the write-only stack. */
  82
  83   assert(self != NULL);
  84   assert(tllp != NULL);
  85   assert(tllp->t_owner == self);
  86
  87   switch(tllp->t_current) {
  88     case TLL_WRITE: tllp->t_current = TLL_READSER; break;
  89     case TLL_READSER:
  90         /* If nothing is queued on write-only, but there is a pending lock
  91          * requesting read-serialized, grant it and keep the lock type. */
  92
  93         if (tllp->t_write == NULL && tllp->t_serial != NULL) {
  94                 tllp->t_owner = tllp->t_serial;
  95                 tllp->t_serial = tllp->t_serial->w_next; /* Remove head */
  96                 tllp->t_owner->w_next = NULL;
  97                 assert(!(tllp->t_status & TLL_PEND));
  98                 tllp->t_status |= TLL_PEND;
  99                 worker_signal(tllp->t_owner);
 100         } else {
 101                 tllp->t_current = TLL_READ;
 102                 tllp->t_owner = NULL;
 103         }
 104         tllp->t_readonly++; /* Either way, there's one more read-only lock */
 105         break;
 106     default: panic("VFS: Incorrect lock state");
 107   }
 108
 109   if (tllp->t_current != TLL_WRITE && tllp->t_current != TLL_READSER)
 110         assert(tllp->t_owner == NULL);
 111 }
 112
 113 void tll_init(tll_t *tllp)
 114 {
 115 /* Initialize three-level-lock tll */
 116   assert(tllp != NULL);
 117
 118   tllp->t_current = TLL_NONE;
 119   tllp->t_readonly = 0;
 120   tllp->t_status = TLL_DFLT;
 121   tllp->t_write = NULL;
 122   tllp->t_serial = NULL;
 123   tllp->t_owner = NULL;
 124 }
 125
 126 int tll_islocked(tll_t *tllp)
 127 {
 128   assert(tllp >= (tll_t *) PAGE_SIZE);
 129   return(tllp->t_current != TLL_NONE);
 130 }
 131
 132 int tll_locked_by_me(tll_t *tllp)
 133 {
 134   assert(tllp >= (tll_t *) PAGE_SIZE);
 135   assert(self != NULL);
 136   return(tllp->t_owner == self && !(tllp->t_status & TLL_PEND));
 137 }
 138
 139 int tll_lock(tll_t *tllp, tll_access_t locktype)
 140 {
 141 /* Try to lock three-level-lock tll with type locktype */
 142
 143   assert(self != NULL);
 144   assert(tllp >= (tll_t *) PAGE_SIZE);
 145   assert(locktype != TLL_NONE);
 146
 147   self->w_next = NULL;
 148
 149   if (locktype != TLL_READ && locktype != TLL_READSER && locktype != TLL_WRITE)
 150         panic("Invalid lock type %d\n", locktype);
 151
 152   /* If this locking has pending locks, we wait */
 153   if (tllp->t_status & TLL_PEND)
 154         return tll_append(tllp, locktype);
 155
 156   /* If we already own this lock don't lock it again and return immediately */
 157   if (tllp->t_owner == self) {
 158         assert(tllp->t_status == TLL_DFLT);
 159         return(EBUSY);
 160   }
 161
 162   /* If this lock is not accessed by anyone, locktype is granted off the bat */
 163   if (tllp->t_current == TLL_NONE) {
 164         tllp->t_current = locktype;
 165         if (tllp->t_current == TLL_READ)
 166                 tllp->t_readonly = 1;
 167         else { /* Record owner if locktype is read-serialized or write-only */
 168                 tllp->t_owner = self;
 169         }
 170         if (tllp->t_current == TLL_WRITE)
 171                 assert(tllp->t_readonly == 0);
 172         return(OK);
 173   }
 174
 175   /* If the current lock is write-only, we have to wait for that lock to be
 176    * released (regardless of the value of locktype). */
 177   if (tllp->t_current == TLL_WRITE)
 178         return tll_append(tllp, locktype);
 179
 180   /* However, if it's not and we're requesting a write-only lock, we have to
 181    * wait until the last read access is released (additional read requests
 182    * after this write-only requests are to be queued) */
 183   if (locktype == TLL_WRITE)
 184         return tll_append(tllp, locktype);
 185
 186   /* We have to queue read and read-serialized requests if we have a write-only
 187    * request queued ("write bias") or when a read-serialized lock is trying to
 188    * upgrade to write-only. The current lock for this tll is either read or
 189    * read-serialized. */
 190   if (tllp->t_write != NULL || (tllp->t_status & TLL_UPGR)) {
 191         assert(!(tllp->t_status & TLL_PEND));
 192         return tll_append(tllp, locktype);
 193   }
 194
 195   /* If this lock is in read-serialized mode, we can allow read requests and
 196    * queue read-serialized requests */
 197   if (tllp->t_current == TLL_READSER) {
 198         if (locktype == TLL_READ && !(tllp->t_status & TLL_UPGR)) {
 199                 tllp->t_readonly++;
 200                 return(OK);
 201         } else
 202                 return tll_append(tllp, locktype);
 203   }
 204
 205   /* Finally, if the current lock is read-only, we can change it to
 206    * read-serialized if necessary without a problem. */
 207   tllp->t_current = locktype; /* Either read-only or read-serialized */
 208   if (tllp->t_current == TLL_READ) {    /* We now have an additional reader */
 209         tllp->t_readonly++;
 210         tllp->t_owner = NULL;
 211   } else {
 212         assert(tllp->t_current != TLL_WRITE);
 213         tllp->t_owner = self;           /* We now have a new owner */
 214         self->w_next = NULL;
 215   }
 216
 217   return(OK);
 218 }
 219
 220 int tll_haspendinglock(tll_t *tllp)
 221 {
 222 /* Is someone trying to obtain a lock? */
 223   assert(tllp != NULL);
 224
 225   /* Someone is trying to obtain a lock if either the write/read-only queue or
 226    * the read-serialized queue is not empty. */
 227   return(tllp->t_write != NULL || tllp->t_serial != NULL);
 228 }
 229
 230 int tll_unlock(tll_t *tllp)
 231 {
 232 /* Unlock a previously locked three-level-lock tll */
 233   int signal_owner = 0;
 234
 235   assert(self != NULL);
 236   assert(tllp != NULL);
 237
 238   if (tllp->t_owner == NULL || tllp->t_owner != self) {
 239         /* This unlock must have been done by a read-only lock */
 240         tllp->t_readonly--;
 241         assert(tllp->t_readonly >= 0);
 242         assert(tllp->t_current == TLL_READ || tllp->t_current == TLL_READSER);
 243
 244         /* If a read-serialized lock is trying to upgrade and there are no more
 245          * read-only locks, the lock can now be upgraded to write-only */
 246         if ((tllp->t_status & TLL_UPGR) && tllp->t_readonly == 0)
 247                 signal_owner = 1;
 248   }
 249
 250   if (tllp->t_owner == self && tllp->t_current == TLL_WRITE)
 251         assert(tllp->t_readonly == 0);
 252
 253   if(tllp->t_owner == self || (tllp->t_owner == NULL && tllp->t_readonly == 0)){
 254         /* Let another read-serialized or write-only request obtain access.
 255          * Write-only has priority, but only after the last read-only access
 256          * has left. Read-serialized access will only be granted if there is
 257          * no pending write-only access request. */
 258         struct worker_thread *new_owner;
 259         new_owner = NULL;
 260         tllp->t_owner = NULL;   /* Remove owner of lock */
 261
 262         if (tllp->t_write != NULL) {
 263                 if (tllp->t_readonly == 0) {
 264                         new_owner = tllp->t_write;
 265                         tllp->t_write = tllp->t_write->w_next;
 266                 }
 267         } else if (tllp->t_serial != NULL) {
 268                 new_owner = tllp->t_serial;
 269                 tllp->t_serial = tllp->t_serial->w_next;
 270         }
 271
 272         /* New owner is head of queue or NULL if no proc is available */
 273         if (new_owner != NULL) {
 274                 tllp->t_owner = new_owner;
 275                 tllp->t_owner->w_next = NULL;
 276                 assert(tllp->t_owner != self);
 277                 signal_owner = 1;
 278         }
 279   }
 280
 281   /* If no one is using this lock, mark it as not in use */
 282   if (tllp->t_owner == NULL) {
 283         if (tllp->t_readonly == 0)
 284                 tllp->t_current = TLL_NONE;
 285         else
 286                 tllp->t_current = TLL_READ;
 287   }
 288
 289   if (tllp->t_current == TLL_NONE || tllp->t_current == TLL_READ) {
 290         if (!signal_owner) {
 291                 tllp->t_owner = NULL;
 292         }
 293   }
 294
 295   /* If we have a new owner or the current owner managed to upgrade its lock,
 296    * tell it to start/continue running */
 297   if (signal_owner) {
 298         assert(!(tllp->t_status & TLL_PEND));
 299         tllp->t_status |= TLL_PEND;
 300         worker_signal(tllp->t_owner);
 301   }
 302
 303   return(OK);
 304 }
 305
 306 void tll_upgrade(tll_t *tllp)
 307 {
 308 /* Upgrade three-level-lock tll from read-serialized to write-only */
 309
 310   assert(self != NULL);
 311   assert(tllp != NULL);
 312   assert(tllp->t_owner == self);
 313   assert(tllp->t_current != TLL_READ); /* i.e., read-serialized or write-only*/
 314   if (tllp->t_current == TLL_WRITE) return;     /* Nothing to do */
 315   if (tllp->t_readonly != 0) {          /* Wait for readers to leave */
 316         assert(!(tllp->t_status & TLL_UPGR));
 317         tllp->t_status |= TLL_UPGR;
 318         worker_wait();
 319         tllp->t_status &= ~TLL_UPGR;
 320         tllp->t_status &= ~TLL_PEND;
 321         assert(tllp->t_readonly == 0);
 322   }
 323   tllp->t_current = TLL_WRITE;
 324 }