lock.c

Go to the documentation of this file.
00001 /*-
00002  * See the file LICENSE for redistribution information.
00003  *
00004  * Copyright (c) 1996, 1997, 1998, 1999, 2000
00005  *      Sleepycat Software.  All rights reserved.
00006  */
00007 
00008 #include "config.h"
00009 
00010 #ifndef lint
00011 static const char revid[] = "$Id: lock_8c-source.html,v 1.1 2008/06/08 10:19:51 sebdiaz Exp $";
00012 #endif /* not lint */
00013 
00014 #ifndef NO_SYSTEM_INCLUDES
00015 #include <sys/types.h>
00016 
00017 #include <errno.h>
00018 #include <string.h>
00019 #endif
00020 
00021 #ifdef  HAVE_RPC
00022 #include "db_server.h"
00023 #endif
00024 
00025 #include "db_int.h"
00026 #include "db_page.h"
00027 #include "db_shash.h"
00028 #include "lock.h"
00029 #include "log.h"
00030 #include "db_am.h"
00031 #include "txn.h"
00032 
00033 #ifdef  HAVE_RPC
00034 #include "gen_client_ext.h"
00035 #include "rpc_client_ext.h"
00036 #endif
00037 
00038 static int  __lock_checklocker __P((DB_LOCKTAB *,
00039     struct __db_lock *, u_int32_t, u_int32_t, int *));
00040 static int  __lock_get_internal __P((DB_LOCKTAB *, u_int32_t,
00041     u_int32_t, const DBT *, db_lockmode_t, DB_LOCK *));
00042 static int __lock_is_parent __P((DB_LOCKTAB *, u_int32_t, DB_LOCKER *));
00043 static int __lock_put_internal __P((DB_LOCKTAB *,
00044     struct __db_lock *, u_int32_t,  u_int32_t));
00045 static int __lock_put_nolock __P((DB_ENV *, DB_LOCK *, int *));
00046 static void __lock_remove_waiter __P((DB_LOCKOBJ *,
00047     struct __db_lock *, db_status_t));
00048 
00049 static const char __db_lock_err[] = "Lock table is out of available %s";
00050 static const char __db_lock_invalid[] = "%s: Lock is no longer valid";
00051 static const char __db_locker_invalid[] = "Locker is not valid";
00052 
00053 /*
00054  * CDB_lock_id --
00055  *      Generate a unique locker id.
00056  */
00057 int
00058 CDB_lock_id(dbenv, idp)
00059         DB_ENV *dbenv;
00060         u_int32_t *idp;
00061 {
00062         DB_LOCKTAB *lt;
00063         DB_LOCKREGION *region;
00064 
00065 #ifdef  HAVE_RPC
00066         if (F_ISSET(dbenv, DB_ENV_RPCCLIENT))
00067                 return (__dbcl_lock_id(dbenv, idp));
00068 #endif
00069 
00070         PANIC_CHECK(dbenv);
00071         ENV_REQUIRES_CONFIG(dbenv, dbenv->lk_handle, DB_INIT_LOCK);
00072 
00073         lt = dbenv->lk_handle;
00074         region = lt->reginfo.primary;
00075 
00076         /*
00077          * Note that we are letting locker IDs wrap.
00078          *
00079          * This is potentially dangerous in that it's conceivable that you
00080          * could be allocating a new locker id and still have someone using
00081          * it.  However, the alternatives are that we keep a bitmap of
00082          * locker ids or we forbid wrapping.  Both are probably bad.  The
00083          * bitmap of locker ids will take up 64 MB of space.  Forbidding
00084          * wrapping means that we'll run out of locker IDs after 2 billion.
00085          * In order for the wrap bug to fire, we'd need to have something
00086          * that stayed open while 2 billion locker ids were used up.  Since
00087          * we cache cursors it means that something would have to stay open
00088          * sufficiently long that we open and close a lot of files and a
00089          * lot of cursors within them.  Betting that this won't happen seems
00090          * to the lesser of the evils.
00091          */
00092         LOCKREGION(dbenv, lt);
00093         if (region->id >= DB_LOCK_MAXID)
00094                 region->id = 0;
00095         *idp = ++region->id;
00096         UNLOCKREGION(dbenv, lt);
00097 
00098         return (0);
00099 }
00100 
00101 /*
00102  * Vector lock routine.  This function takes a set of operations
00103  * and performs them all at once.  In addition, CDB_lock_vec provides
00104  * functionality for lock inheritance, releasing all locks for a
00105  * given locker (used during transaction commit/abort), releasing
00106  * all locks on a given object, and generating debugging information.
00107  */
00108 int
00109 CDB_lock_vec(dbenv, locker, flags, list, nlist, elistp)
00110         DB_ENV *dbenv;
00111         u_int32_t locker, flags;
00112         int nlist;
00113         DB_LOCKREQ *list, **elistp;
00114 {
00115         struct __db_lock *lp, *next_lock;
00116         DB_LOCKER *sh_locker, *sh_parent;
00117         DB_LOCKOBJ *sh_obj;
00118         DB_LOCKREGION *region;
00119         DB_LOCKTAB *lt;
00120         u_int32_t lndx, ndx;
00121         int did_abort, i, ret, run_dd;
00122 
00123 #ifdef  HAVE_RPC
00124         if (F_ISSET(dbenv, DB_ENV_RPCCLIENT))
00125                 return (__dbcl_lock_vec(dbenv, locker,
00126                     flags, list, nlist, elistp));
00127 #endif
00128         PANIC_CHECK(dbenv);
00129         ENV_REQUIRES_CONFIG(dbenv, dbenv->lk_handle, DB_INIT_LOCK);
00130 
00131         /* Validate arguments. */
00132         if ((ret = CDB___db_fchk(dbenv, "CDB_lock_vec", flags, DB_LOCK_NOWAIT)) != 0)
00133                 return (ret);
00134 
00135         lt = dbenv->lk_handle;
00136         region = lt->reginfo.primary;
00137 
00138         run_dd = 0;
00139         LOCKREGION(dbenv, (DB_LOCKTAB *)dbenv->lk_handle);
00140         for (i = 0, ret = 0; i < nlist && ret == 0; i++)
00141                 switch (list[i].op) {
00142                 case DB_LOCK_GET:
00143                         ret = __lock_get_internal(dbenv->lk_handle,
00144                             locker, flags,
00145                             list[i].obj, list[i].mode, &list[i].lock);
00146                         break;
00147                 case DB_LOCK_INHERIT:
00148 
00149                         /*
00150                          * Get the committing locker and mark it as deleted.
00151                          * This allows us to traverse the locker links without
00152                          * worrying that someone else is deleting locks out
00153                          * from under us.  However, if the locker doesn't
00154                          * exist, that just means that the child holds no
00155                          * locks, so inheritance is easy!
00156                          */
00157                         ndx = CDB___lock_locker_hash(locker) % region->table_size;
00158                         if ((ret = CDB___lock_getlocker(lt,
00159                             locker, ndx, 0, &sh_locker)) != 0 ||
00160                             sh_locker == NULL ||
00161                             F_ISSET(sh_locker, DB_LOCKER_DELETED)) {
00162                                 if (ret == 0 && sh_locker != NULL)
00163                                         ret = EACCES;
00164                                 CDB___db_err(dbenv, __db_locker_invalid);
00165                                 break;
00166                         }
00167 
00168                         /* Make sure we are a child transaction. */
00169                         if (sh_locker->parent_locker == INVALID_ROFF) {
00170                                 CDB___db_err(dbenv, "Not a child transaction");
00171                                 ret = EINVAL;
00172                                 break;
00173                         }
00174                         sh_parent = (DB_LOCKER *)
00175                             R_ADDR(&lt->reginfo, sh_locker->parent_locker);
00176                         F_SET(sh_locker, DB_LOCKER_DELETED);
00177 
00178                         /*
00179                          * Now, lock the parent locker; move locks from
00180                          * the committing list to the parent's list.
00181                          */
00182                         ndx = CDB___lock_locker_hash(locker) % region->table_size;
00183                         if (F_ISSET(sh_parent, DB_LOCKER_DELETED)) {
00184                                 if (ret == 0) {
00185                                         CDB___db_err(dbenv,
00186                                              "Parent locker is not valid");
00187                                         ret = EACCES;
00188                                 }
00189                                 break;
00190                         }
00191 
00192                         for (lp = SH_LIST_FIRST(&sh_locker->heldby, __db_lock);
00193                             lp != NULL;
00194                             lp = SH_LIST_FIRST(&sh_locker->heldby, __db_lock)) {
00195                                 SH_LIST_REMOVE(lp, locker_links, __db_lock);
00196                                 SH_LIST_INSERT_HEAD(&sh_parent->heldby, lp,
00197                                     locker_links, __db_lock);
00198                                 lp->holder = sh_parent->id;
00199                         }
00200 
00201                         /* Now free the original locker. */
00202                         ret = __lock_checklocker(lt,
00203                             NULL, locker, DB_LOCK_IGNOREDEL, NULL);
00204                         break;
00205                 case DB_LOCK_PUT:
00206                         ret = __lock_put_nolock(dbenv, &list[i].lock, &run_dd);
00207                         break;
00208                 case DB_LOCK_PUT_ALL:
00209                         /*
00210                          * Get the locker and mark it as deleted.  This
00211                          * allows us to traverse the locker links without
00212                          * worrying that someone else is deleting locks out
00213                          * from under us.  Since the locker may hold no
00214                          * locks (i.e., you could call abort before you've
00215                          * done any work), it's perfectly reasonable for there
00216                          * to be no locker; this is not an error.
00217                          */
00218                         ndx = CDB___lock_locker_hash(locker) % region->table_size;
00219                         if ((ret = CDB___lock_getlocker(lt,
00220                             locker, ndx, 0, &sh_locker)) != 0 ||
00221                             sh_locker == NULL ||
00222                             F_ISSET(sh_locker, DB_LOCKER_DELETED))
00223                                 /*
00224                                  * If ret is set, then we'll generate an
00225                                  * error.  If it's not set, we have nothing
00226                                  * to do.
00227                                  */
00228                                 break;
00229                         F_SET(sh_locker, DB_LOCKER_DELETED);
00230 
00231                         /* Now traverse the locks, releasing each one. */
00232                         for (lp = SH_LIST_FIRST(&sh_locker->heldby, __db_lock);
00233                             lp != NULL;
00234                             lp = SH_LIST_FIRST(&sh_locker->heldby, __db_lock)) {
00235                                 SH_LIST_REMOVE(lp, locker_links, __db_lock);
00236                                 sh_obj =
00237                                     (DB_LOCKOBJ *)((u_int8_t *)lp + lp->obj);
00238                                 SHOBJECT_LOCK(lt, region, sh_obj, lndx);
00239                                 ret = __lock_put_internal(lt,
00240                                     lp, lndx, DB_LOCK_FREE | DB_LOCK_DOALL);
00241                                 if (ret != 0)
00242                                         break;
00243                         }
00244                         ret = __lock_checklocker(lt,
00245                             NULL, locker, DB_LOCK_IGNOREDEL, NULL);
00246                         break;
00247                 case DB_LOCK_PUT_OBJ:
00248                         /* Remove all the locks associated with an object. */
00249                         OBJECT_LOCK(lt, region, list[i].obj, ndx);
00250                         if ((ret = CDB___lock_getobj(lt, list[i].obj,
00251                             ndx, 0, &sh_obj)) != 0 || sh_obj == NULL) {
00252                                 if (ret == 0)
00253                                         ret = EINVAL;
00254                                 break;
00255                         }
00256 
00257                         /*
00258                          * Go through both waiters and holders.  Don't bother
00259                          * to run promotion, because everyone is getting
00260                          * released.  The processes waiting will still get
00261                          * awakened as their waiters are released.
00262                          */
00263                         for (lp = SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock);
00264                             ret == 0 && lp != NULL;
00265                             lp = SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock))
00266                                 ret = __lock_put_internal(lt,
00267                                     lp, ndx, DB_LOCK_NOPROMOTE | DB_LOCK_DOALL);
00268 
00269                         /*
00270                          * On the last time around, the object will get
00271                          * reclaimed by __lock_put_internal, structure the
00272                          * loop carefully so we do not get bitten.
00273                          */
00274                         for (lp = SH_TAILQ_FIRST(&sh_obj->holders, __db_lock);
00275                             ret == 0 && lp != NULL;
00276                             lp = next_lock) {
00277                                 next_lock = SH_TAILQ_NEXT(lp, links, __db_lock);
00278                                 ret = __lock_put_internal(lt,
00279                                     lp, ndx, DB_LOCK_NOPROMOTE | DB_LOCK_DOALL);
00280                         }
00281                         break;
00282 #ifdef DEBUG
00283                 case DB_LOCK_DUMP:
00284                         /* Find the locker. */
00285                         ndx = CDB___lock_locker_hash(locker) % region->table_size;
00286                         if ((ret = CDB___lock_getlocker(lt,
00287                             locker, ndx, 0, &sh_locker)) != 0
00288                             || sh_locker == NULL
00289                             || F_ISSET(sh_locker, DB_LOCKER_DELETED))
00290                                 break;
00291 
00292                         for (lp = SH_LIST_FIRST(&sh_locker->heldby, __db_lock);
00293                             lp != NULL;
00294                             lp = SH_LIST_NEXT(lp, locker_links, __db_lock)) {
00295                                 CDB___lock_printlock(lt, lp, 1);
00296                         }
00297                         break;
00298 #endif
00299                 default:
00300                         CDB___db_err(dbenv,
00301                             "Invalid lock operation: %d", list[i].op);
00302                         ret = EINVAL;
00303                         break;
00304                 }
00305 
00306         if (ret == 0 && region->need_dd && region->detect != DB_LOCK_NORUN) {
00307                 run_dd = 1;
00308                 region->need_dd = 0;
00309         }
00310         UNLOCKREGION(dbenv, (DB_LOCKTAB *)dbenv->lk_handle);
00311 
00312         if (run_dd)
00313                 (void)CDB_lock_detect(dbenv, 0, region->detect, &did_abort);
00314 
00315         if (ret != 0 && elistp != NULL)
00316                 *elistp = &list[i - 1];
00317 
00318         return (ret);
00319 }
00320 
00321 /*
00322  * Lock acquisition routines.  There are two library interfaces:
00323  *
00324  * CDB_lock_get --
00325  *      original lock get interface that takes a locker id.
00326  *
00327  * All the work for CDB_lock_get (and for the GET option of CDB_lock_vec) is done
00328  * inside of lock_get_internal.
00329  */
00330 int
00331 CDB_lock_get(dbenv, locker, flags, obj, lock_mode, lock)
00332         DB_ENV *dbenv;
00333         u_int32_t locker, flags;
00334         const DBT *obj;
00335         db_lockmode_t lock_mode;
00336         DB_LOCK *lock;
00337 {
00338         int ret;
00339 
00340 #ifdef  HAVE_RPC
00341         if (F_ISSET(dbenv, DB_ENV_RPCCLIENT))
00342                 return (__dbcl_lock_get(dbenv, locker,
00343                     flags, obj, lock_mode, lock));
00344 #endif
00345         PANIC_CHECK(dbenv);
00346         ENV_REQUIRES_CONFIG(dbenv, dbenv->lk_handle, DB_INIT_LOCK);
00347 
00348         if (IS_RECOVERING(dbenv))
00349                 return (0);
00350 
00351         /* Validate arguments. */
00352         if ((ret = CDB___db_fchk(dbenv,
00353             "CDB_lock_get", flags, DB_LOCK_NOWAIT | DB_LOCK_UPGRADE)) != 0)
00354                 return (ret);
00355 
00356         if (lock == NULL)
00357                 return (EINVAL);
00358 
00359         LOCKREGION(dbenv, (DB_LOCKTAB *)dbenv->lk_handle);
00360         ret = __lock_get_internal(dbenv->lk_handle,
00361             locker, flags, obj, lock_mode, lock);
00362         UNLOCKREGION(dbenv, (DB_LOCKTAB *)dbenv->lk_handle);
00363         return (ret);
00364 }
00365 
00366 static int
00367 __lock_get_internal(lt, locker, flags, obj, lock_mode, lock)
00368         DB_LOCKTAB *lt;
00369         u_int32_t locker, flags;
00370         const DBT *obj;
00371         db_lockmode_t lock_mode;
00372         DB_LOCK *lock;
00373 {
00374         struct __db_lock *newl, *lp;
00375         DB_ENV *dbenv;
00376         DB_LOCKER *sh_locker;
00377         DB_LOCKOBJ *sh_obj;
00378         DB_LOCKREGION *region;
00379         u_int32_t locker_ndx;
00380         int did_abort, freed, ihold, on_locker_list, no_dd, ret;
00381 
00382         no_dd = ret = 0;
00383         on_locker_list = 0;
00384         region = lt->reginfo.primary;
00385         dbenv = lt->dbenv;
00386 
00387         /*
00388          * Check that the lock mode is valid.
00389          */
00390         if ((u_int32_t)lock_mode >= region->nmodes) {
00391                 CDB___db_err(dbenv,
00392                     "CDB_lock_get: invalid lock mode %lu\n", (u_long)lock_mode);
00393                 return (EINVAL);
00394         }
00395 
00396         /* Allocate a new lock.  Optimize for the common case of a grant. */
00397         region->nrequests++;
00398         if ((newl = SH_TAILQ_FIRST(&region->free_locks, __db_lock)) != NULL)
00399                 SH_TAILQ_REMOVE(&region->free_locks, newl, links, __db_lock);
00400         if (newl == NULL) {
00401                 CDB___db_err(dbenv, __db_lock_err, "locks");
00402                 return (ENOMEM);
00403         }
00404 
00405         /* Allocate a new object. */
00406         OBJECT_LOCK(lt, region, obj, lock->ndx);
00407         if ((ret = CDB___lock_getobj(lt, obj, lock->ndx, 1, &sh_obj)) != 0)
00408                 goto err;
00409 
00410         /* Get the locker, we may need it to find our parent. */
00411         locker_ndx = CDB___lock_locker_hash(locker) % region->table_size;
00412         if ((ret =
00413              CDB___lock_getlocker(lt, locker, locker_ndx, 1, &sh_locker)) != 0) {
00414                 /*
00415                  * XXX: Margo
00416                  * CLEANUP the object and the lock.
00417                  */
00418                 return (ret);
00419         }
00420 
00421         /*
00422          * Now we have a lock and an object and we need to see if we should
00423          * grant the lock.  We use a FIFO ordering so we can only grant a
00424          * new lock if it does not conflict with anyone on the holders list
00425          * OR anyone on the waiters list.  The reason that we don't grant if
00426          * there's a conflict is that this can lead to starvation (a writer
00427          * waiting on a popularly read item will never be granted).  The
00428          * downside of this is that a waiting reader can prevent an upgrade
00429          * from reader to writer, which is not uncommon.
00430          *
00431          * There is one exception to the no-conflict rule.  If a lock is held
00432          * by the requesting locker AND the new lock does not conflict with
00433          * any other holders, then we grant the lock.  The most common place
00434          * this happens is when the holder has a WRITE lock and a READ lock
00435          * request comes in for the same locker.  If we do not grant the read
00436          * lock, then we guarantee deadlock.
00437          *
00438          * In case of conflict, we put the new lock on the end of the waiters
00439          * list, unless we are upgrading in which case the locker goes on the
00440          * front of the list.
00441          */
00442         ihold = 0;
00443         for (lp = SH_TAILQ_FIRST(&sh_obj->holders, __db_lock);
00444             lp != NULL;
00445             lp = SH_TAILQ_NEXT(lp, links, __db_lock)) {
00446                 if (locker == lp->holder ||
00447                     __lock_is_parent(lt, lp->holder, sh_locker)) {
00448                         if (lp->mode == lock_mode &&
00449                             lp->status == DB_LSTAT_HELD) {
00450                                 if (LF_ISSET(DB_LOCK_UPGRADE))
00451                                         goto upgrade;
00452 
00453                                 /*
00454                                  * Lock is held, so we can increment the
00455                                  * reference count and return this lock.
00456                                  */
00457                                 lp->refcount++;
00458                                 lock->off = R_OFFSET(&lt->reginfo, lp);
00459                                 lock->gen = lp->gen;
00460 
00461                                 ret = 0;
00462                                 goto done;
00463                         } else
00464                                 ihold = 1;
00465                 } else if (CONFLICTS(lt, region, lp->mode, lock_mode))
00466                         break;
00467         }
00468 
00469         /*
00470          * Make the new lock point to the new object, initialize fields.
00471          *
00472          * This lock is not linked in anywhere, so we can muck with it
00473          * without holding any mutexes.
00474          */
00475         newl->holder = locker;
00476         newl->refcount = 1;
00477         newl->mode = lock_mode;
00478         newl->obj = SH_PTR_TO_OFF(newl, sh_obj);
00479         newl->status = DB_LSTAT_HELD;
00480 
00481         /*
00482          * If we are upgrading, then there are two scenarios.  Either
00483          * we had no conflicts, so we can do the upgrade.  Or, there
00484          * is a conflict and we should wait at the HEAD of the waiters
00485          * list.
00486          */
00487         if (LF_ISSET(DB_LOCK_UPGRADE)) {
00488                 if (lp == NULL)
00489                         goto upgrade;
00490 
00491                 /*
00492                  * There was a conflict, wait.  If this is the first waiter,
00493                  * add the object to the deadlock detector's list.
00494                  */
00495                 if (SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock) == NULL)
00496                         SH_TAILQ_INSERT_HEAD(&region->dd_objs,
00497                             sh_obj, dd_links, __db_lockobj);
00498 
00499                 SH_TAILQ_INSERT_HEAD(&sh_obj->waiters, newl, links, __db_lock);
00500                 goto llist;
00501         }
00502 
00503         if (lp == NULL && !ihold)
00504                 for (lp = SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock);
00505                     lp != NULL;
00506                     lp = SH_TAILQ_NEXT(lp, links, __db_lock)) {
00507                         if (CONFLICTS(lt, region, lp->mode, lock_mode) &&
00508                             locker != lp->holder)
00509                                 break;
00510                 }
00511         if (lp == NULL)
00512                 SH_TAILQ_INSERT_TAIL(&sh_obj->holders, newl, links);
00513         else if (!(flags & DB_LOCK_NOWAIT)) {
00514                 /*
00515                  * If this is the first waiter, add the object to the
00516                  * deadlock detector's list.
00517                  */
00518                 if (SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock) == NULL)
00519                         SH_TAILQ_INSERT_HEAD(&region->dd_objs,
00520                             sh_obj, dd_links, __db_lockobj);
00521                 SH_TAILQ_INSERT_TAIL(&sh_obj->waiters, newl, links);
00522         } else {
00523                 ret = DB_LOCK_NOTGRANTED;
00524                 if (SH_LIST_FIRST(&sh_locker->heldby, __db_lock) == NULL
00525                     && LOCKER_FREEABLE(sh_locker))
00526                         CDB___lock_freelocker( lt, region, sh_locker, locker_ndx);
00527                 region->nnowaits++;
00528                 goto err;
00529         }
00530 
00531 llist:
00532         /*
00533          * Now, insert the lock onto its locker's list.  If the locker does
00534          * not currently hold any locks, there's no reason to run a deadlock
00535          * detector, save that information.
00536          */
00537         on_locker_list = 1;
00538         no_dd = sh_locker->master_locker == INVALID_ROFF
00539             && SH_LIST_FIRST(&sh_locker->child_locker, __db_locker) == NULL
00540             && SH_LIST_FIRST(&sh_locker->heldby, __db_lock) == NULL;
00541 
00542         SH_LIST_INSERT_HEAD(&sh_locker->heldby, newl, locker_links, __db_lock);
00543 
00544         if (lp != NULL) {
00545                 /*
00546                  * This is really a blocker for the thread.  It should be
00547                  * initized locked, so that when we try to acquire it, we
00548                  * block.
00549                  */
00550                 newl->status = DB_LSTAT_WAITING;
00551                 region->nconflicts++;
00552                 if (region->detect == DB_LOCK_NORUN)
00553                         region->need_dd = 1;
00554                 UNLOCKREGION(dbenv, (DB_LOCKTAB *)dbenv->lk_handle);
00555 
00556                 /*
00557                  * We are about to wait; before waiting, see if the deadlock
00558                  * detector should be run.
00559                  */
00560                 if (region->detect != DB_LOCK_NORUN && !no_dd)
00561                         (void)CDB_lock_detect(dbenv, 0, region->detect, &did_abort);
00562 
00563                 MUTEX_LOCK(&newl->mutex, dbenv->lockfhp);
00564                 LOCKREGION(dbenv, (DB_LOCKTAB *)dbenv->lk_handle);
00565 
00566                 if (newl->status != DB_LSTAT_PENDING) {
00567                         (void)__lock_checklocker(lt,
00568                             newl, newl->holder, 0, &freed);
00569                         switch (newl->status) {
00570                                 case DB_LSTAT_ABORTED:
00571                                         on_locker_list = 0;
00572                                         ret = DB_LOCK_DEADLOCK;
00573                                         break;
00574                                 case DB_LSTAT_NOGRANT:
00575                                         ret = DB_LOCK_NOTGRANTED;
00576                                         break;
00577                                 default:
00578                                         ret = EINVAL;
00579                                         break;
00580                         }
00581                         goto err;
00582                 } else if (LF_ISSET(DB_LOCK_UPGRADE)) {
00583                         /*
00584                          * The lock that was just granted got put on the
00585                          * holders list.  Since we're upgrading some other
00586                          * lock, we've got to remove it here.
00587                          */
00588                         SH_TAILQ_REMOVE(
00589                             &sh_obj->holders, newl, links, __db_lock);
00590                         /*
00591                          * Ensure that the object is not believed to be on
00592                          * the object's lists, if we're traversing by locker.
00593                          */
00594                         newl->links.stqe_prev = -1;
00595                         goto upgrade;
00596                 } else
00597                         newl->status = DB_LSTAT_HELD;
00598         }
00599 
00600         lock->off = R_OFFSET(&lt->reginfo, newl);
00601         lock->gen = newl->gen;
00602 
00603         return (0);
00604 
00605 upgrade:/*
00606          * This was an upgrade, so return the new lock to the free list and
00607          * upgrade the mode of the original lock.
00608          */
00609         ((struct __db_lock *)R_ADDR(&lt->reginfo, lock->off))->mode = lock_mode;
00610 
00611         ret = 0;
00612         /* FALLTHROUGH */
00613 
00614 done:
00615 err:    newl->status = DB_LSTAT_FREE;
00616         if (on_locker_list) {
00617                 SH_LIST_REMOVE(newl, locker_links, __db_lock);
00618         }
00619         SH_TAILQ_INSERT_HEAD(&region->free_locks, newl, links, __db_lock);
00620         return (ret);
00621 }
00622 
00623 /*
00624  * Lock release routines.
00625  *
00626  * The user callable one is CDB_lock_put and the three we use internally are
00627  * __lock_put_nolock, __lock_put_internal and CDB___lock_downgrade.
00628  */
00629 int
00630 CDB_lock_put(dbenv, lock)
00631         DB_ENV *dbenv;
00632         DB_LOCK *lock;
00633 {
00634         DB_LOCKTAB *lt;
00635         int ret, run_dd;
00636 
00637 #ifdef  HAVE_RPC
00638         if (F_ISSET(dbenv, DB_ENV_RPCCLIENT))
00639                 return (__dbcl_lock_put(dbenv, lock));
00640 #endif
00641         PANIC_CHECK(dbenv);
00642         ENV_REQUIRES_CONFIG(dbenv, dbenv->lk_handle, DB_INIT_LOCK);
00643 
00644         if (IS_RECOVERING(dbenv))
00645                 return (0);
00646 
00647         lt = dbenv->lk_handle;
00648 
00649         LOCKREGION(dbenv, lt);
00650         ret = __lock_put_nolock(dbenv, lock, &run_dd);
00651         UNLOCKREGION(dbenv, lt);
00652 
00653         lock->off = LOCK_INVALID;
00654 
00655         if (ret == 0 && run_dd)
00656                 (void)CDB_lock_detect(dbenv, 0,
00657                     ((DB_LOCKREGION *)lt->reginfo.primary)->detect, NULL);
00658         return (ret);
00659 }
00660 
00661 static int
00662 __lock_put_nolock(dbenv, lock, runp)
00663         DB_ENV *dbenv;
00664         DB_LOCK *lock;
00665         int *runp;
00666 {
00667         struct __db_lock *lockp;
00668         DB_LOCKREGION *region;
00669         DB_LOCKTAB *lt;
00670         u_int32_t locker;
00671         int ret;
00672 
00673         lt = dbenv->lk_handle;
00674         region = lt->reginfo.primary;
00675 
00676         lockp = (struct __db_lock *)R_ADDR(&lt->reginfo, lock->off);
00677         if (lock->gen != lockp->gen) {
00678                 CDB___db_err(dbenv, __db_lock_invalid, "CDB_lock_put");
00679                 return(EACCES);
00680         }
00681 
00682         locker = lockp->holder;
00683         ret = __lock_put_internal(lt,
00684             lockp, lock->ndx, DB_LOCK_UNLINK | DB_LOCK_FREE);
00685 
00686         *runp = 0;
00687         if (ret == 0 && region->need_dd && region->detect != DB_LOCK_NORUN) {
00688                 *runp = 1;
00689                 region->need_dd = 0;
00690         }
00691 
00692         return (ret);
00693 }
00694 
00695 /*
00696  * CDB___lock_downgrade --
00697  *      Used by the concurrent access product to downgrade write locks
00698  * back to iwrite locks.
00699  *
00700  * PUBLIC: int CDB___lock_downgrade __P((DB_ENV *,
00701  * PUBLIC:     DB_LOCK *, db_lockmode_t, u_int32_t));
00702  */
00703 int
00704 CDB___lock_downgrade(dbenv, lock, new_mode, flags)
00705         DB_ENV *dbenv;
00706         DB_LOCK *lock;
00707         db_lockmode_t new_mode;
00708         u_int32_t flags;
00709 {
00710         struct __db_lock *lockp;
00711         DB_LOCKOBJ *obj;
00712         DB_LOCKREGION *region;
00713         DB_LOCKTAB *lt;
00714         int ret;
00715 
00716         COMPQUIET(flags, 0);
00717 
00718         PANIC_CHECK(dbenv);
00719 
00720         lt = dbenv->lk_handle;
00721         region = lt->reginfo.primary;
00722 
00723         LOCKREGION(dbenv, lt);
00724 
00725         lockp = (struct __db_lock *)R_ADDR(&lt->reginfo, lock->off);
00726         if (lock->gen != lockp->gen) {
00727                 CDB___db_err(dbenv, __db_lock_invalid, "lock_downgrade");
00728                 ret = EACCES;
00729                 goto out;
00730         }
00731 
00732         lockp->mode = new_mode;
00733 
00734         /* Get the object associated with this lock. */
00735         obj = (DB_LOCKOBJ *)((u_int8_t *)lockp + lockp->obj);
00736         (void)CDB___lock_promote(lt, obj);
00737 
00738         ++region->nreleases;
00739 out:    UNLOCKREGION(dbenv, lt);
00740 
00741         return (0);
00742 }
00743 
00744 static int
00745 __lock_put_internal(lt, lockp, obj_ndx, flags)
00746         DB_LOCKTAB *lt;
00747         struct __db_lock *lockp;
00748         u_int32_t obj_ndx;
00749         u_int32_t flags;
00750 {
00751         DB_LOCKOBJ *sh_obj;
00752         DB_LOCKREGION *region;
00753         int no_reclaim, ret, state_changed;
00754 
00755         region = lt->reginfo.primary;
00756         no_reclaim = ret = state_changed = 0;
00757 
00758         if (!OBJ_LINKS_VALID(lockp)) {
00759                 /*
00760                  * Someone removed this lock while we were doing a release
00761                  * by locker id.  We are trying to free this lock, but it's
00762                  * already been done; all we need to do is return it to the
00763                  * free list.
00764                  */
00765                 lockp->status = DB_LSTAT_FREE;
00766                 SH_TAILQ_INSERT_HEAD(
00767                     &region->free_locks, lockp, links, __db_lock);
00768                 return (0);
00769         }
00770 
00771         if (LF_ISSET(DB_LOCK_DOALL))
00772                 region->nreleases += lockp->refcount;
00773         else
00774                 region->nreleases++;
00775 
00776         if (!LF_ISSET(DB_LOCK_DOALL) && lockp->refcount > 1) {
00777                 lockp->refcount--;
00778                 return (0);
00779         }
00780 
00781         /* Increment generation number. */
00782         lockp->gen++;
00783 
00784         /* Get the object associated with this lock. */
00785         sh_obj = (DB_LOCKOBJ *)((u_int8_t *)lockp + lockp->obj);
00786 
00787         /* Remove this lock from its holders/waitlist. */
00788         if (lockp->status != DB_LSTAT_HELD)
00789                 __lock_remove_waiter(sh_obj, lockp, DB_LSTAT_FREE);
00790         else {
00791                 SH_TAILQ_REMOVE(&sh_obj->holders, lockp, links, __db_lock);
00792                 lockp->links.stqe_prev = -1;
00793         }
00794 
00795         if (LF_ISSET(DB_LOCK_NOPROMOTE))
00796                 state_changed = 0;
00797         else
00798                 state_changed = CDB___lock_promote(lt, sh_obj);
00799 
00800         if (LF_ISSET(DB_LOCK_UNLINK))
00801                 ret = __lock_checklocker(lt, lockp, lockp->holder, flags, NULL);
00802 
00803         /* Check if object should be reclaimed. */
00804         if (SH_TAILQ_FIRST(&sh_obj->holders, __db_lock) == NULL) {
00805                 HASHREMOVE_EL(lt->obj_tab,
00806                     obj_ndx, __db_lockobj, links, sh_obj);
00807                 if (sh_obj->lockobj.size > sizeof(sh_obj->objdata))
00808                         CDB___db_shalloc_free(lt->reginfo.addr,
00809                             SH_DBT_PTR(&sh_obj->lockobj));
00810                 SH_TAILQ_INSERT_HEAD(
00811                     &region->free_objs, sh_obj, links, __db_lockobj);
00812                 state_changed = 1;
00813         }
00814 
00815         /* Free lock. */
00816         if (!LF_ISSET(DB_LOCK_UNLINK) && LF_ISSET(DB_LOCK_FREE)) {
00817                 lockp->status = DB_LSTAT_FREE;
00818                 SH_TAILQ_INSERT_HEAD(
00819                     &region->free_locks, lockp, links, __db_lock);
00820         }
00821 
00822         /*
00823          * If we did not promote anyone; we need to run the deadlock
00824          * detector again.
00825          */
00826         if (state_changed == 0)
00827                 region->need_dd = 1;
00828 
00829         return (ret);
00830 }
00831 
00832 /*
00833  * Utility functions; listed alphabetically.
00834  */
00835 
00836 /*
00837  * __lock_checklocker --
00838  *      If a locker has no more locks, then we can free the object.
00839  * Return a boolean indicating whether we freed the object or not.
00840  *
00841  * Must be called without the locker's lock set.
00842  */
00843 static int
00844 __lock_checklocker(lt, lockp, locker, flags, freed)
00845         DB_LOCKTAB *lt;
00846         struct __db_lock *lockp;
00847         u_int32_t locker, flags;
00848         int *freed;
00849 {
00850         DB_ENV *dbenv;
00851         DB_LOCKER *sh_locker;
00852         DB_LOCKREGION *region;
00853         u_int32_t indx;
00854         int ret;
00855 
00856         dbenv = lt->dbenv;
00857         region = lt->reginfo.primary;
00858         ret = 0;
00859 
00860         if (freed != NULL)
00861                 *freed = 0;
00862 
00863         indx = CDB___lock_locker_hash(locker) % region->table_size;
00864 
00865         /* If the locker's list is NULL, free up the locker. */
00866         if ((ret = CDB___lock_getlocker(lt,
00867             locker, indx, 0, &sh_locker)) != 0 || sh_locker == NULL) {
00868                 if (ret == 0)
00869                         ret = EACCES;
00870                 CDB___db_err(lt->dbenv, __db_locker_invalid);
00871                 goto freelock;
00872         }
00873 
00874         if (F_ISSET(sh_locker, DB_LOCKER_DELETED)) {
00875                 LF_CLR(DB_LOCK_FREE);
00876                 if (!LF_ISSET(DB_LOCK_IGNOREDEL))
00877                         goto freelock;
00878         }
00879 
00880         if (LF_ISSET(DB_LOCK_UNLINK))
00881                 SH_LIST_REMOVE(lockp, locker_links, __db_lock);
00882 
00883         if (SH_LIST_FIRST(&sh_locker->heldby, __db_lock) == NULL
00884             && LOCKER_FREEABLE(sh_locker)) {
00885                 CDB___lock_freelocker( lt, region, sh_locker, indx);
00886                 if (freed != NULL)
00887                         *freed = 1;
00888         }
00889 
00890 freelock:
00891         if (LF_ISSET(DB_LOCK_FREE)) {
00892                 lockp->status = DB_LSTAT_FREE;
00893                 SH_TAILQ_INSERT_HEAD(
00894                     &region->free_locks, lockp, links, __db_lock);
00895         }
00896 
00897         return (ret);
00898 }
00899 
00900 /*
00901  * CDB___lock_addfamilylocker
00902  *      Put a locker entry in for a child transaction.
00903  *
00904  * PUBLIC: int CDB___lock_addfamilylocker __P((DB_ENV *, u_int32_t, u_int32_t));
00905  */
00906 int
00907 CDB___lock_addfamilylocker(dbenv, pid, id)
00908         DB_ENV *dbenv;
00909         u_int32_t pid, id;
00910 {
00911         DB_LOCKER *lockerp, *mlockerp;
00912         DB_LOCKREGION *region;
00913         DB_LOCKTAB *lt;
00914         u_int32_t ndx;
00915         int ret;
00916 
00917         lt = dbenv->lk_handle;
00918         region = lt->reginfo.primary;
00919         LOCKREGION(dbenv, lt);
00920 
00921         /* get/create the  parent locker info */
00922         ndx = CDB___lock_locker_hash(pid) % region->table_size;
00923         if ((ret = CDB___lock_getlocker(dbenv->lk_handle,
00924             pid, ndx, 1, &mlockerp)) != 0)
00925                 goto err;
00926 
00927         /*
00928          * We assume that only one thread can manipulate
00929          * a single transaction family.
00930          * Therefore the master locker cannot go away while
00931          * we manipulate it, nor can another child in the
00932          * family be created at the same time.
00933          */
00934         ndx = CDB___lock_locker_hash(id) % region->table_size;
00935         if ((ret = CDB___lock_getlocker(dbenv->lk_handle,
00936             id, ndx, 1, &lockerp)) != 0)
00937                 goto err;
00938 
00939         /* Point to our parent. */
00940         lockerp->parent_locker = R_OFFSET(&lt->reginfo, mlockerp);
00941 
00942         /* See if this locker is the family master. */
00943         if (mlockerp->master_locker == INVALID_ROFF)
00944                 lockerp->master_locker = R_OFFSET(&lt->reginfo, mlockerp);
00945         else {
00946                 lockerp->master_locker = mlockerp->master_locker;
00947                 mlockerp = R_ADDR(&lt->reginfo, mlockerp->master_locker);
00948         }
00949 
00950         /*
00951          * Link the child at the head of the master's list.
00952          * The guess is when looking for deadlock that
00953          * the most recent child is the one thats blocked.
00954          */
00955         SH_LIST_INSERT_HEAD(
00956             &mlockerp->child_locker, lockerp, child_link, __db_locker);
00957 
00958 err:
00959         UNLOCKREGION(dbenv, lt);
00960 
00961         return (ret);
00962 }
00963 
00964 /*
00965  * CDB___lock_freefamilylocker
00966  *      Remove a locker from the hash table and its family.
00967  *
00968  * This must be called without the locker bucket locked.
00969  *
00970  * PUBLIC: int CDB___lock_freefamilylocker  __P((DB_LOCKTAB *, u_int32_t));
00971  */
00972 int
00973 CDB___lock_freefamilylocker(lt, locker)
00974         DB_LOCKTAB *lt;
00975         u_int32_t locker;
00976 {
00977         DB_ENV *dbenv;
00978         DB_LOCKER *sh_locker;
00979         DB_LOCKREGION *region;
00980         u_int32_t indx;
00981         int ret;
00982 
00983         dbenv = lt->dbenv;
00984         region = lt->reginfo.primary;
00985 
00986         LOCKREGION(dbenv, lt);
00987         indx = CDB___lock_locker_hash(locker) % region->table_size;
00988 
00989         if ((ret = CDB___lock_getlocker(lt,
00990             locker, indx, 0, &sh_locker)) != 0 || sh_locker == NULL) {
00991                 if (ret == 0)
00992                         ret = EACCES;
00993                 goto freelock;
00994         }
00995         if (SH_LIST_FIRST(&sh_locker->heldby, __db_lock) != NULL) {
00996                 ret = EINVAL;
00997                 CDB___db_err(dbenv, "Freeing locker with locks");
00998                 goto freelock;
00999         }
01000 
01001         /* If this is part of a family, we must fix up its links. */
01002         if (sh_locker->master_locker != INVALID_ROFF)
01003                 SH_LIST_REMOVE(sh_locker, child_link, __db_locker);
01004 
01005         CDB___lock_freelocker(lt, region, sh_locker, indx);
01006 
01007 freelock:
01008         UNLOCKREGION(dbenv, lt);
01009         return (ret);
01010 }
01011 
01012 /*
01013  * CDB___lock_freelocker
01014  *      common code for deleting a locker.
01015  *
01016  * This must be called with the locker bucket locked.
01017  *
01018  * PUBLIC: void CDB___lock_freelocker __P((DB_LOCKTAB *,
01019  * PUBLIC:     DB_LOCKREGION *, DB_LOCKER *, u_int32_t));
01020  */
01021 void
01022 CDB___lock_freelocker(lt, region, sh_locker, indx)
01023         DB_LOCKTAB *lt;
01024         DB_LOCKREGION *region;
01025         DB_LOCKER *sh_locker;
01026         u_int32_t indx;
01027 
01028 {
01029         HASHREMOVE_EL(
01030             lt->locker_tab, indx, __db_locker, links, sh_locker);
01031         SH_TAILQ_INSERT_HEAD(
01032             &region->free_lockers, sh_locker, links, __db_locker);
01033         region->nlockers--;
01034 }
01035 /*
01036  * CDB___lock_getlocker --
01037  *      Get a locker in the locker hash table.  The create parameter
01038  * indicates if the locker should be created if it doesn't exist in
01039  * the table.
01040  *
01041  * This must be called with the locker bucket locked.
01042  *
01043  * PUBLIC: int CDB___lock_getlocker __P((DB_LOCKTAB *,
01044  * PUBLIC:     u_int32_t, u_int32_t, int, DB_LOCKER **));
01045  */
01046 int
01047 CDB___lock_getlocker(lt, locker, indx, create, retp)
01048         DB_LOCKTAB *lt;
01049         u_int32_t locker, indx;
01050         int create;
01051         DB_LOCKER **retp;
01052 {
01053         DB_ENV *dbenv;
01054         DB_LOCKER *sh_locker;
01055         DB_LOCKREGION *region;
01056 
01057         dbenv = lt->dbenv;
01058         region = lt->reginfo.primary;
01059 
01060         HASHLOOKUP(lt->locker_tab,
01061             indx, __db_locker, links, locker, sh_locker, CDB___lock_locker_cmp);
01062 
01063         /*
01064          * If we found the locker, then we can just return it.  If
01065          * we didn't find the locker, then we need to create it.
01066          */
01067         if (sh_locker == NULL && create) {
01068                 /* Create new locker and then insert it into hash table. */
01069                 if ((sh_locker = SH_TAILQ_FIRST(
01070                     &region->free_lockers, __db_locker)) == NULL) {
01071                         CDB___db_err(lt->dbenv, __db_lock_err, "locker entries");
01072                         return (ENOMEM);
01073                 }
01074                 SH_TAILQ_REMOVE(
01075                     &region->free_lockers, sh_locker, links, __db_locker);
01076                 if (++region->nlockers > region->maxnlockers)
01077                         region->maxnlockers = region->nlockers;
01078 
01079                 sh_locker->id = locker;
01080                 sh_locker->dd_id = 0;
01081                 sh_locker->master_locker = INVALID_ROFF;
01082                 sh_locker->parent_locker = INVALID_ROFF;
01083                 SH_LIST_INIT(&sh_locker->child_locker);
01084                 sh_locker->flags = 0;
01085                 SH_LIST_INIT(&sh_locker->heldby);
01086 
01087                 HASHINSERT(lt->locker_tab, indx, __db_locker, links, sh_locker);
01088         }
01089 
01090         *retp = sh_locker;
01091         return (0);
01092 }
01093 
01094 /*
01095  * CDB___lock_getobj --
01096  *      Get an object in the object hash table.  The create parameter
01097  * indicates if the object should be created if it doesn't exist in
01098  * the table.
01099  *
01100  * This must be called with the object bucket locked.
01101  *
01102  * PUBLIC: int CDB___lock_getobj __P((DB_LOCKTAB *,
01103  * PUBLIC:     const DBT *, u_int32_t, int, DB_LOCKOBJ **));
01104  */
01105 int
01106 CDB___lock_getobj(lt, obj, ndx, create, retp)
01107         DB_LOCKTAB *lt;
01108         const DBT *obj;
01109         u_int32_t ndx;
01110         int create;
01111         DB_LOCKOBJ **retp;
01112 {
01113         DB_ENV *dbenv;
01114         DB_LOCKOBJ *sh_obj;
01115         DB_LOCKREGION *region;
01116         int ret;
01117         void *p;
01118 
01119         dbenv = lt->dbenv;
01120         region = lt->reginfo.primary;
01121 
01122         /* Look up the object in the hash table. */
01123         HASHLOOKUP(lt->obj_tab,
01124             ndx, __db_lockobj, links, obj, sh_obj, CDB___lock_cmp);
01125 
01126         /*
01127          * If we found the object, then we can just return it.  If
01128          * we didn't find the object, then we need to create it.
01129          */
01130         if (sh_obj == NULL && create) {
01131                 /* Create new object and then insert it into hash table. */
01132                 if ((sh_obj =
01133                     SH_TAILQ_FIRST(&region->free_objs, __db_lockobj)) == NULL) {
01134                         CDB___db_err(lt->dbenv, __db_lock_err, "object entries");
01135                         ret = ENOMEM;
01136                         goto err;
01137                 }
01138 
01139                 /*
01140                  * If we can fit this object in the structure, do so instead
01141                  * of shalloc-ing space for it.
01142                  */
01143                 if (obj->size <= sizeof(sh_obj->objdata))
01144                         p = sh_obj->objdata;
01145                 else if ((ret = CDB___db_shalloc(
01146                     lt->reginfo.addr, obj->size, 0, &p)) != 0) {
01147                         CDB___db_err(dbenv, "No space for lock object storage");
01148                         goto err;
01149                 }
01150 
01151                 memcpy(p, obj->data, obj->size);
01152 
01153                 SH_TAILQ_REMOVE(
01154                     &region->free_objs, sh_obj, links, __db_lockobj);
01155 
01156                 SH_TAILQ_INIT(&sh_obj->waiters);
01157                 SH_TAILQ_INIT(&sh_obj->holders);
01158                 sh_obj->lockobj.size = obj->size;
01159                 sh_obj->lockobj.off = SH_PTR_TO_OFF(&sh_obj->lockobj, p);
01160 
01161                 HASHINSERT(lt->obj_tab, ndx, __db_lockobj, links, sh_obj);
01162         }
01163 
01164         *retp = sh_obj;
01165         return (0);
01166 
01167 err:    return (ret);
01168 }
01169 
01170 /*
01171  * __lock_is_parent --
01172  *      Given a locker and a transaction, return 1 if the locker is
01173  * an ancestor of the designcated transaction.  This is used to determine
01174  * if we should grant locks that appear to conflict, but don't because
01175  * the lock is already held by an ancestor.
01176  */
01177 static int
01178 __lock_is_parent(lt, locker, sh_locker)
01179         DB_LOCKTAB *lt;
01180         u_int32_t locker;
01181         DB_LOCKER *sh_locker;
01182 {
01183         DB_LOCKER *parent;
01184 
01185         parent = sh_locker;
01186         while (parent->parent_locker != INVALID_ROFF) {
01187                 parent = (DB_LOCKER *)
01188                      R_ADDR(&lt->reginfo, parent->parent_locker);
01189                 if (parent->id == locker)
01190                         return (1);
01191         }
01192 
01193         return (0);
01194 }
01195 
01196 /*
01197  * CDB___lock_promote --
01198  *
01199  * Look through the waiters and holders lists and decide which (if any)
01200  * locks can be promoted.   Promote any that are eligible.
01201  *
01202  * PUBLIC: int CDB___lock_promote __P((DB_LOCKTAB *, DB_LOCKOBJ *));
01203  */
01204 int
01205 CDB___lock_promote(lt, obj)
01206         DB_LOCKTAB *lt;
01207         DB_LOCKOBJ *obj;
01208 {
01209         struct __db_lock *lp_w, *lp_h, *next_waiter;
01210         DB_LOCKER *sh_locker;
01211         DB_LOCKREGION *region;
01212         u_int32_t locker_ndx;
01213         int had_waiters, state_changed;
01214 
01215         region = lt->reginfo.primary;
01216         had_waiters = 0;
01217 
01218         /*
01219          * We need to do lock promotion.  We also need to determine if we're
01220          * going to need to run the deadlock detector again.  If we release
01221          * locks, and there are waiters, but no one gets promoted, then we
01222          * haven't fundamentally changed the lockmgr state, so we may still
01223          * have a deadlock and we have to run again.  However, if there were
01224          * no waiters, or we actually promoted someone, then we are OK and we
01225          * don't have to run it immediately.
01226          *
01227          * During promotion, we look for state changes so we can return this
01228          * information to the caller.
01229          */
01230 
01231         for (lp_w = SH_TAILQ_FIRST(&obj->waiters, __db_lock),
01232             state_changed = lp_w == NULL;
01233             lp_w != NULL;
01234             lp_w = next_waiter) {
01235                 had_waiters = 1;
01236                 next_waiter = SH_TAILQ_NEXT(lp_w, links, __db_lock);
01237                 for (lp_h = SH_TAILQ_FIRST(&obj->holders, __db_lock);
01238                     lp_h != NULL;
01239                     lp_h = SH_TAILQ_NEXT(lp_h, links, __db_lock)) {
01240                         if (lp_h->holder != lp_w->holder &&
01241                             CONFLICTS(lt, region, lp_h->mode, lp_w->mode)) {
01242                                 
01243                                 locker_ndx = CDB___lock_locker_hash(lp_w->holder)
01244                                     % region->table_size;
01245                                 if ((CDB___lock_getlocker(lt, lp_w->holder,
01246                                     locker_ndx, 0, &sh_locker)) != 0) {
01247                                         DB_ASSERT(0);
01248                                         break;
01249                                 }
01250                         if (!__lock_is_parent(lt, lp_h->holder, sh_locker))
01251                                 break;
01252                         }
01253                 }
01254                 if (lp_h != NULL)       /* Found a conflict. */
01255                         break;
01256 
01257                 /* No conflict, promote the waiting lock. */
01258                 SH_TAILQ_REMOVE(&obj->waiters, lp_w, links, __db_lock);
01259                 lp_w->status = DB_LSTAT_PENDING;
01260                 SH_TAILQ_INSERT_TAIL(&obj->holders, lp_w, links);
01261 
01262                 /* Wake up waiter. */
01263                 MUTEX_UNLOCK(&lp_w->mutex);
01264                 state_changed = 1;
01265         }
01266 
01267         /*
01268          * If this object had waiters and doesn't any more, then we need
01269          * to remove it from the dd_obj list.
01270          */
01271         if (had_waiters && SH_TAILQ_FIRST(&obj->waiters, __db_lock) == NULL)
01272                 SH_TAILQ_REMOVE(&region->dd_objs, obj, dd_links, __db_lockobj);
01273         return (state_changed);
01274 }
01275 
01276 /*
01277  * __lock_remove_waiter --
01278  *      Any lock on the waitlist has a process waiting for it.  Therefore,
01279  * we can't return the lock to the freelist immediately.  Instead, we can
01280  * remove the lock from the list of waiters, set the status field of the
01281  * lock, and then let the process waking up return the lock to the
01282  * free list.
01283  *
01284  * This must be called with the Object bucket locked.
01285  */
01286 static void
01287 __lock_remove_waiter(sh_obj, lockp, status)
01288         DB_LOCKOBJ *sh_obj;
01289         struct __db_lock *lockp;
01290         db_status_t status;
01291 {
01292         int do_wakeup;
01293 
01294         do_wakeup = lockp->status == DB_LSTAT_WAITING;
01295 
01296         SH_TAILQ_REMOVE(&sh_obj->waiters, lockp, links, __db_lock);
01297         lockp->links.stqe_prev = -1;
01298         lockp->status = status;
01299 
01300         /*
01301          * Wake whoever is waiting on this lock.
01302          *
01303          * The MUTEX_UNLOCK macro normally resolves to a single argument,
01304          * keep the compiler quiet.
01305          */
01306         if (do_wakeup)
01307                 MUTEX_UNLOCK(&lockp->mutex);
01308 }
01309 
01310 /*
01311  * CDB___lock_printlock --
01312  *
01313  * PUBLIC: void CDB___lock_printlock __P((DB_LOCKTAB *, struct __db_lock *, int));
01314  */
01315 void
01316 CDB___lock_printlock(lt, lp, ispgno)
01317         DB_LOCKTAB *lt;
01318         struct __db_lock *lp;
01319         int ispgno;
01320 {
01321         DB_LOCKOBJ *lockobj;
01322         db_pgno_t pgno;
01323         u_int32_t *fidp;
01324         u_int8_t *ptr, type;
01325         const char *mode, *status;
01326 
01327         switch (lp->mode) {
01328         case DB_LOCK_IREAD:
01329                 mode = "IREAD";
01330                 break;
01331         case DB_LOCK_IWR:
01332                 mode = "IWR";
01333                 break;
01334         case DB_LOCK_IWRITE:
01335                 mode = "IWRITE";
01336                 break;
01337         case DB_LOCK_NG:
01338                 mode = "NG";
01339                 break;
01340         case DB_LOCK_READ:
01341                 mode = "READ";
01342                 break;
01343         case DB_LOCK_WRITE:
01344                 mode = "WRITE";
01345                 break;
01346         default:
01347                 mode = "UNKNOWN";
01348                 break;
01349         }
01350         switch (lp->status) {
01351         case DB_LSTAT_ABORTED:
01352                 status = "ABORT";
01353                 break;
01354         case DB_LSTAT_ERR:
01355                 status = "ERROR";
01356                 break;
01357         case DB_LSTAT_FREE:
01358                 status = "FREE";
01359                 break;
01360         case DB_LSTAT_HELD:
01361                 status = "HELD";
01362                 break;
01363         case DB_LSTAT_NOGRANT:
01364                 status = "NONE";
01365                 break;
01366         case DB_LSTAT_WAITING:
01367                 status = "WAIT";
01368                 break;
01369         case DB_LSTAT_PENDING:
01370                 status = "PENDING";
01371                 break;
01372         default:
01373                 status = "UNKNOWN";
01374                 break;
01375         }
01376         printf("\t%lx\t%s\t%lu\t%s\t",
01377             (u_long)lp->holder, mode, (u_long)lp->refcount, status);
01378 
01379         lockobj = (DB_LOCKOBJ *)((u_int8_t *)lp + lp->obj);
01380         ptr = SH_DBT_PTR(&lockobj->lockobj);
01381         if (ispgno && lockobj->lockobj.size == sizeof(struct __db_ilock)) {
01382                 /* Assume this is a DBT lock. */
01383                 memcpy(&pgno, ptr, sizeof(db_pgno_t));
01384                 fidp = (u_int32_t *)(ptr + sizeof(db_pgno_t));
01385                 type = *(u_int8_t *)(ptr + sizeof(db_pgno_t) + DB_FILE_ID_LEN);
01386                 printf("%s  %lu (%lu %lu %lu %lu %lu)\n",
01387                         type == DB_PAGE_LOCK ? "page" : "record",
01388                         (u_long)pgno,
01389                         (u_long)fidp[0], (u_long)fidp[1], (u_long)fidp[2],
01390                         (u_long)fidp[3], (u_long)fidp[4]);
01391         } else {
01392                 printf("0x%lx ", (u_long)R_OFFSET(&lt->reginfo, lockobj));
01393                 CDB___db_pr(ptr, lockobj->lockobj.size);
01394                 printf("\n");
01395         }
01396 }

Generated on Sun Jun 8 10:56:38 2008 for GNUmifluz by  doxygen 1.5.5