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         return tll_append(tllp, locktype);
 190
 191   /* If this lock is in read-serialized mode, we can allow read requests and
 192    * queue read-serialized requests */
 193   if (tllp->t_current == TLL_READSER) {
 194         if (locktype == TLL_READ) {
 195                 tllp->t_readonly++;
 196                 return(OK);
 197         } else
 198                 return tll_append(tllp, locktype);
 199   }
 200
 201   /* Finally, if the current lock is read-only, we can change it to
 202    * read-serialized if necessary without a problem. */
 203   tllp->t_current = locktype; /* Either read-only or read-serialized */
 204   if (tllp->t_current == TLL_READ) {    /* We now have an additional reader */
 205         tllp->t_readonly++;
 206         tllp->t_owner = NULL;
 207   } else {
 208         assert(tllp->t_current != TLL_WRITE);
 209         tllp->t_owner = self;           /* We now have a new owner */
 210         self->w_next = NULL;
 211   }
 212
 213   return(OK);
 214 }
 215
 216 int tll_haspendinglock(tll_t *tllp)
 217 {
 218 /* Is someone trying to obtain a lock? */
 219   assert(tllp != NULL);
 220
 221   /* Someone is trying to obtain a lock if either the write/read-only queue or
 222    * the read-serialized queue is not empty. */
 223   return(tllp->t_write != NULL || tllp->t_serial != NULL);
 224 }
 225
 226 int tll_unlock(tll_t *tllp)
 227 {
 228 /* Unlock a previously locked three-level-lock tll */
 229   int signal_owner = 0;
 230
 231   assert(self != NULL);
 232   assert(tllp != NULL);
 233
 234   if (tllp->t_owner == NULL || tllp->t_owner != self) {
 235         /* This unlock must have been done by a read-only lock */
 236         tllp->t_readonly--;
 237         assert(tllp->t_readonly >= 0);
 238         assert(tllp->t_current == TLL_READ || tllp->t_current == TLL_READSER);
 239
 240         /* If a read-serialized lock is trying to upgrade and there are no more
 241          * read-only locks, the lock can now be upgraded to write-only */
 242         if ((tllp->t_status & TLL_UPGR) && tllp->t_readonly == 0)
 243                 signal_owner = 1;
 244   }
 245
 246   if (tllp->t_owner == self && tllp->t_current == TLL_WRITE)
 247         assert(tllp->t_readonly == 0);
 248
 249   if(tllp->t_owner == self || (tllp->t_owner == NULL && tllp->t_readonly == 0)){
 250         /* Let another read-serialized or write-only request obtain access.
 251          * Write-only has priority, but only after the last read-only access
 252          * has left. Read-serialized access will only be granted if there is
 253          * no pending write-only access request. */
 254         struct worker_thread *new_owner;
 255         new_owner = NULL;
 256         tllp->t_owner = NULL;   /* Remove owner of lock */
 257
 258         if (tllp->t_write != NULL) {
 259                 if (tllp->t_readonly == 0) {
 260                         new_owner = tllp->t_write;
 261                         tllp->t_write = tllp->t_write->w_next;
 262                 }
 263         } else if (tllp->t_serial != NULL) {
 264                 new_owner = tllp->t_serial;
 265                 tllp->t_serial = tllp->t_serial->w_next;
 266         }
 267
 268         /* New owner is head of queue or NULL if no proc is available */
 269         if (new_owner != NULL) {
 270                 tllp->t_owner = new_owner;
 271                 tllp->t_owner->w_next = NULL;
 272                 assert(tllp->t_owner != self);
 273                 signal_owner = 1;
 274         }
 275   }
 276
 277   /* If no one is using this lock, mark it as not in use */
 278   if (tllp->t_owner == NULL) {
 279         if (tllp->t_readonly == 0)
 280                 tllp->t_current = TLL_NONE;
 281         else
 282                 tllp->t_current = TLL_READ;
 283   }
 284
 285   if (tllp->t_current == TLL_NONE || tllp->t_current == TLL_READ) {
 286         if (!signal_owner) {
 287                 tllp->t_owner = NULL;
 288         }
 289   }
 290
 291   /* If we have a new owner or the current owner managed to upgrade its lock,
 292    * tell it to start/continue running */
 293   if (signal_owner) {
 294         assert(!(tllp->t_status & TLL_PEND));
 295         tllp->t_status |= TLL_PEND;
 296         worker_signal(tllp->t_owner);
 297   }
 298
 299   return(OK);
 300 }
 301
 302 void tll_upgrade(tll_t *tllp)
 303 {
 304 /* Upgrade three-level-lock tll from read-serialized to write-only */
 305
 306   assert(self != NULL);
 307   assert(tllp != NULL);
 308   assert(tllp->t_owner == self);
 309   assert(tllp->t_current != TLL_READ); /* i.e., read-serialized or write-only*/
 310   if (tllp->t_current == TLL_WRITE) return;     /* Nothing to do */
 311   if (tllp->t_readonly != 0) {          /* Wait for readers to leave */
 312         assert(!(tllp->t_status & TLL_UPGR));
 313         tllp->t_status |= TLL_UPGR;
 314         worker_wait();
 315         tllp->t_status &= ~TLL_UPGR;
 316         tllp->t_status &= ~TLL_PEND;
 317         assert(tllp->t_readonly == 0);
 318   }
 319   tllp->t_current = TLL_WRITE;
 320 }