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   return(tllp->t_current != TLL_NONE);
 129 }
 130
 131 int tll_locked_by_me(tll_t *tllp)
 132 {
 133   assert(self != NULL);
 134   return(tllp->t_owner == self && !(tllp->t_status & TLL_PEND));
 135 }
 136
 137 int tll_lock(tll_t *tllp, tll_access_t locktype)
 138 {
 139 /* Try to lock three-level-lock tll with type locktype */
 140
 141   assert(self != NULL);
 142   assert(tllp != NULL);
 143   assert(locktype != TLL_NONE);
 144
 145   self->w_next = NULL;
 146
 147   if (locktype != TLL_READ && locktype != TLL_READSER && locktype != TLL_WRITE)
 148         panic("Invalid lock type %d\n", locktype);
 149
 150   /* If this locking has pending locks, we wait */
 151   if (tllp->t_status & TLL_PEND)
 152         return tll_append(tllp, locktype);
 153
 154   /* If we already own this lock don't lock it again and return immediately */
 155   if (tllp->t_owner == self) {
 156         assert(tllp->t_status == TLL_DFLT);
 157         return(EBUSY);
 158   }
 159
 160   /* If this lock is not accessed by anyone, locktype is granted off the bat */
 161   if (tllp->t_current == TLL_NONE) {
 162         tllp->t_current = locktype;
 163         if (tllp->t_current == TLL_READ)
 164                 tllp->t_readonly = 1;
 165         else { /* Record owner if locktype is read-serialized or write-only */
 166                 tllp->t_owner = self;
 167         }
 168         if (tllp->t_current == TLL_WRITE)
 169                 assert(tllp->t_readonly == 0);
 170         return(OK);
 171   }
 172
 173   /* If the current lock is write-only, we have to wait for that lock to be
 174    * released (regardless of the value of locktype). */
 175   if (tllp->t_current == TLL_WRITE)
 176         return tll_append(tllp, locktype);
 177
 178   /* However, if it's not and we're requesting a write-only lock, we have to
 179    * wait until the last read access is released (additional read requests
 180    * after this write-only requests are to be queued) */
 181   if (locktype == TLL_WRITE)
 182         return tll_append(tllp, locktype);
 183
 184   /* We have to queue read and read-serialized requests if we have a write-only
 185    * request queued ("write bias") or when a read-serialized lock is trying to
 186    * upgrade to write-only. The current lock for this tll is either read or
 187    * read-serialized. */
 188   if (tllp->t_write != NULL || (tllp->t_status & TLL_UPGR)) {
 189         assert(!(tllp->t_status & TLL_PEND));
 190         return tll_append(tllp, locktype);
 191   }
 192
 193   /* If this lock is in read-serialized mode, we can allow read requests and
 194    * queue read-serialized requests */
 195   if (tllp->t_current == TLL_READSER) {
 196         if (locktype == TLL_READ && !(tllp->t_status & TLL_UPGR)) {
 197                 tllp->t_readonly++;
 198                 return(OK);
 199         } else
 200                 return tll_append(tllp, locktype);
 201   }
 202
 203   /* Finally, if the current lock is read-only, we can change it to
 204    * read-serialized if necessary without a problem. */
 205   tllp->t_current = locktype; /* Either read-only or read-serialized */
 206   if (tllp->t_current == TLL_READ) {    /* We now have an additional reader */
 207         tllp->t_readonly++;
 208         tllp->t_owner = NULL;
 209   } else {
 210         assert(tllp->t_current != TLL_WRITE);
 211         tllp->t_owner = self;           /* We now have a new owner */
 212         self->w_next = NULL;
 213   }
 214
 215   return(OK);
 216 }
 217
 218 int tll_haspendinglock(tll_t *tllp)
 219 {
 220 /* Is someone trying to obtain a lock? */
 221   assert(tllp != NULL);
 222
 223   /* Someone is trying to obtain a lock if either the write/read-only queue or
 224    * the read-serialized queue is not empty. */
 225   return(tllp->t_write != NULL || tllp->t_serial != NULL);
 226 }
 227
 228 int tll_unlock(tll_t *tllp)
 229 {
 230 /* Unlock a previously locked three-level-lock tll */
 231   int signal_owner = 0;
 232
 233   assert(self != NULL);
 234   assert(tllp != NULL);
 235
 236   if (tllp->t_owner == NULL || tllp->t_owner != self) {
 237         /* This unlock must have been done by a read-only lock */
 238         tllp->t_readonly--;
 239         assert(tllp->t_readonly >= 0);
 240         assert(tllp->t_current == TLL_READ || tllp->t_current == TLL_READSER);
 241
 242         /* If a read-serialized lock is trying to upgrade and there are no more
 243          * read-only locks, the lock can now be upgraded to write-only */
 244         if ((tllp->t_status & TLL_UPGR) && tllp->t_readonly == 0)
 245                 signal_owner = 1;
 246   }
 247
 248   if (tllp->t_owner == self && tllp->t_current == TLL_WRITE)
 249         assert(tllp->t_readonly == 0);
 250
 251   if(tllp->t_owner == self || (tllp->t_owner == NULL && tllp->t_readonly == 0)){
 252         /* Let another read-serialized or write-only request obtain access.
 253          * Write-only has priority, but only after the last read-only access
 254          * has left. Read-serialized access will only be granted if there is
 255          * no pending write-only access request. */
 256         struct worker_thread *new_owner;
 257         new_owner = NULL;
 258         tllp->t_owner = NULL;   /* Remove owner of lock */
 259
 260         if (tllp->t_write != NULL) {
 261                 if (tllp->t_readonly == 0) {
 262                         new_owner = tllp->t_write;
 263                         tllp->t_write = tllp->t_write->w_next;
 264                 }
 265         } else if (tllp->t_serial != NULL) {
 266                 new_owner = tllp->t_serial;
 267                 tllp->t_serial = tllp->t_serial->w_next;
 268         }
 269
 270         /* New owner is head of queue or NULL if no proc is available */
 271         if (new_owner != NULL) {
 272                 tllp->t_owner = new_owner;
 273                 tllp->t_owner->w_next = NULL;
 274                 assert(tllp->t_owner != self);
 275                 signal_owner = 1;
 276         }
 277   }
 278
 279   /* If no one is using this lock, mark it as not in use */
 280   if (tllp->t_owner == NULL) {
 281         if (tllp->t_readonly == 0)
 282                 tllp->t_current = TLL_NONE;
 283         else
 284                 tllp->t_current = TLL_READ;
 285   }
 286
 287   if (tllp->t_current == TLL_NONE || tllp->t_current == TLL_READ) {
 288         if (!signal_owner) {
 289                 tllp->t_owner = NULL;
 290         }
 291   }
 292
 293   /* If we have a new owner or the current owner managed to upgrade its lock,
 294    * tell it to start/continue running */
 295   if (signal_owner) {
 296         assert(!(tllp->t_status & TLL_PEND));
 297         tllp->t_status |= TLL_PEND;
 298         worker_signal(tllp->t_owner);
 299   }
 300
 301   return(OK);
 302 }
 303
 304 void tll_upgrade(tll_t *tllp)
 305 {
 306 /* Upgrade three-level-lock tll from read-serialized to write-only */
 307
 308   assert(self != NULL);
 309   assert(tllp != NULL);
 310   assert(tllp->t_owner == self);
 311   assert(tllp->t_current != TLL_READ); /* i.e., read-serialized or write-only*/
 312   if (tllp->t_current == TLL_WRITE) return;     /* Nothing to do */
 313   if (tllp->t_readonly != 0) {          /* Wait for readers to leave */
 314         assert(!(tllp->t_status & TLL_UPGR));
 315         tllp->t_status |= TLL_UPGR;
 316         worker_wait();
 317         tllp->t_status &= ~TLL_UPGR;
 318         tllp->t_status &= ~TLL_PEND;
 319         assert(tllp->t_readonly == 0);
 320   }
 321   tllp->t_current = TLL_WRITE;
 322 }