Update from db 2.4.14.
[kopensolaris-gnu/glibc.git] / db2 / lock / lock.c
1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 1996, 1997, 1998
5  *      Sleepycat Software.  All rights reserved.
6  */
7
8 #include "config.h"
9
10 #ifndef lint
11 static const char sccsid[] = "@(#)lock.c        10.52 (Sleepycat) 5/10/98";
12 #endif /* not lint */
13
14 #ifndef NO_SYSTEM_INCLUDES
15 #include <sys/types.h>
16
17 #include <errno.h>
18 #include <string.h>
19 #endif
20
21 #include "db_int.h"
22 #include "shqueue.h"
23 #include "db_page.h"
24 #include "db_shash.h"
25 #include "lock.h"
26 #include "common_ext.h"
27 #include "db_am.h"
28
29 static void __lock_checklocker __P((DB_LOCKTAB *, struct __db_lock *, int));
30 static void __lock_freeobj __P((DB_LOCKTAB *, DB_LOCKOBJ *));
31 static int  __lock_get_internal __P((DB_LOCKTAB *, u_int32_t, u_int32_t,
32     const DBT *, db_lockmode_t, struct __db_lock **));
33 static int  __lock_put_internal __P((DB_LOCKTAB *, struct __db_lock *, int));
34 static void __lock_remove_waiter
35     __P((DB_LOCKTAB *, DB_LOCKOBJ *, struct __db_lock *, db_status_t));
36
37 int
38 lock_id(lt, idp)
39         DB_LOCKTAB *lt;
40         u_int32_t *idp;
41 {
42         u_int32_t id;
43
44         LOCK_LOCKREGION(lt);
45         if (lt->region->id >= DB_LOCK_MAXID)
46                 lt->region->id = 0;
47         id = ++lt->region->id;
48         UNLOCK_LOCKREGION(lt);
49
50         *idp = id;
51         return (0);
52 }
53
54 int
55 lock_vec(lt, locker, flags, list, nlist, elistp)
56         DB_LOCKTAB *lt;
57         u_int32_t locker, flags;
58         int nlist;
59         DB_LOCKREQ *list, **elistp;
60 {
61         struct __db_lock *lp;
62         DB_LOCKOBJ *sh_obj, *sh_locker;
63         int i, ret, run_dd;
64
65         /* Validate arguments. */
66         if ((ret =
67             __db_fchk(lt->dbenv, "lock_vec", flags, DB_LOCK_NOWAIT)) != 0)
68                 return (ret);
69
70         LOCK_LOCKREGION(lt);
71
72         if ((ret = __lock_validate_region(lt)) != 0) {
73                 UNLOCK_LOCKREGION(lt);
74                 return (ret);
75         }
76
77         ret = 0;
78         for (i = 0; i < nlist && ret == 0; i++) {
79                 switch (list[i].op) {
80                 case DB_LOCK_GET:
81                         ret = __lock_get_internal(lt, locker, flags,
82                             list[i].obj, list[i].mode, &lp);
83                         if (ret == 0) {
84                                 list[i].lock = LOCK_TO_OFFSET(lt, lp);
85                                 lt->region->nrequests++;
86                         }
87                         break;
88                 case DB_LOCK_PUT:
89                         lp = OFFSET_TO_LOCK(lt, list[i].lock);
90                         if (lp->holder != locker) {
91                                 ret = DB_LOCK_NOTHELD;
92                                 break;
93                         }
94                         list[i].mode = lp->mode;
95
96                         /* XXX Need to copy the object. ??? */
97                         ret = __lock_put_internal(lt, lp, 0);
98                         break;
99                 case DB_LOCK_PUT_ALL:
100                         /* Find the locker. */
101                         if ((ret = __lock_getobj(lt, locker,
102                             NULL, DB_LOCK_LOCKER, &sh_locker)) != 0)
103                                 break;
104
105                         for (lp = SH_LIST_FIRST(&sh_locker->heldby, __db_lock);
106                             lp != NULL;
107                             lp = SH_LIST_FIRST(&sh_locker->heldby, __db_lock)) {
108                                 if ((ret = __lock_put_internal(lt, lp, 1)) != 0)
109                                         break;
110                         }
111                         __lock_freeobj(lt, sh_locker);
112                         lt->region->nlockers--;
113                         break;
114                 case DB_LOCK_PUT_OBJ:
115
116                         /* Look up the object in the hash table. */
117                         HASHLOOKUP(lt->hashtab, __db_lockobj, links,
118                             list[i].obj, sh_obj, lt->region->table_size,
119                             __lock_ohash, __lock_cmp);
120                         if (sh_obj == NULL) {
121                                 ret = EINVAL;
122                                 break;
123                         }
124                         /*
125                          * Release waiters first, because they won't cause
126                          * anyone else to be awakened.  If we release the
127                          * lockers first, all the waiters get awakened
128                          * needlessly.
129                          */
130                         for (lp = SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock);
131                             lp != NULL;
132                             lp = SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock)) {
133                                 lt->region->nreleases += lp->refcount;
134                                 __lock_remove_waiter(lt, sh_obj, lp,
135                                     DB_LSTAT_NOGRANT);
136                                 __lock_checklocker(lt, lp, 1);
137                         }
138
139                         for (lp = SH_TAILQ_FIRST(&sh_obj->holders, __db_lock);
140                             lp != NULL;
141                             lp = SH_TAILQ_FIRST(&sh_obj->holders, __db_lock)) {
142
143                                 lt->region->nreleases += lp->refcount;
144                                 SH_LIST_REMOVE(lp, locker_links, __db_lock);
145                                 SH_TAILQ_REMOVE(&sh_obj->holders, lp, links,
146                                     __db_lock);
147                                 lp->status = DB_LSTAT_FREE;
148                                 SH_TAILQ_INSERT_HEAD(&lt->region->free_locks,
149                                     lp, links, __db_lock);
150                         }
151
152                         /* Now free the object. */
153                         __lock_freeobj(lt, sh_obj);
154                         break;
155 #ifdef DEBUG
156                 case DB_LOCK_DUMP:
157                         /* Find the locker. */
158                         if ((ret = __lock_getobj(lt, locker,
159                             NULL, DB_LOCK_LOCKER, &sh_locker)) != 0)
160                                 break;
161
162                         for (lp = SH_LIST_FIRST(&sh_locker->heldby, __db_lock);
163                             lp != NULL;
164                             lp = SH_LIST_NEXT(lp, locker_links, __db_lock)) {
165                                 __lock_printlock(lt, lp, 1);
166                                 ret = EINVAL;
167                         }
168                         if (ret == 0) {
169                                 __lock_freeobj(lt, sh_locker);
170                                 lt->region->nlockers--;
171                         }
172                         break;
173 #endif
174                 default:
175                         ret = EINVAL;
176                         break;
177                 }
178         }
179
180         if (lt->region->need_dd && lt->region->detect != DB_LOCK_NORUN) {
181                 run_dd = 1;
182                 lt->region->need_dd = 0;
183         } else
184                 run_dd = 0;
185
186         UNLOCK_LOCKREGION(lt);
187
188         if (ret == 0 && run_dd)
189                 lock_detect(lt, 0, lt->region->detect);
190
191         if (elistp && ret != 0)
192                 *elistp = &list[i - 1];
193         return (ret);
194 }
195
196 int
197 lock_get(lt, locker, flags, obj, lock_mode, lock)
198         DB_LOCKTAB *lt;
199         u_int32_t locker, flags;
200         const DBT *obj;
201         db_lockmode_t lock_mode;
202         DB_LOCK *lock;
203 {
204         struct __db_lock *lockp;
205         int ret;
206
207         /* Validate arguments. */
208         if ((ret =
209             __db_fchk(lt->dbenv, "lock_get", flags, DB_LOCK_NOWAIT)) != 0)
210                 return (ret);
211
212         LOCK_LOCKREGION(lt);
213
214         ret = __lock_validate_region(lt);
215         if (ret == 0 && (ret = __lock_get_internal(lt,
216             locker, flags, obj, lock_mode, &lockp)) == 0) {
217                 *lock = LOCK_TO_OFFSET(lt, lockp);
218                 lt->region->nrequests++;
219         }
220
221         UNLOCK_LOCKREGION(lt);
222         return (ret);
223 }
224
225 int
226 lock_put(lt, lock)
227         DB_LOCKTAB *lt;
228         DB_LOCK lock;
229 {
230         struct __db_lock *lockp;
231         int ret, run_dd;
232
233         LOCK_LOCKREGION(lt);
234
235         if ((ret = __lock_validate_region(lt)) != 0)
236                 return (ret);
237         else {
238                 lockp = OFFSET_TO_LOCK(lt, lock);
239                 ret = __lock_put_internal(lt, lockp, 0);
240         }
241
242         __lock_checklocker(lt, lockp, 0);
243
244         if (lt->region->need_dd && lt->region->detect != DB_LOCK_NORUN) {
245                 run_dd = 1;
246                 lt->region->need_dd = 0;
247         } else
248                 run_dd = 0;
249
250         UNLOCK_LOCKREGION(lt);
251
252         if (ret == 0 && run_dd)
253                 lock_detect(lt, 0, lt->region->detect);
254
255         return (ret);
256 }
257
258 static int
259 __lock_put_internal(lt, lockp, do_all)
260         DB_LOCKTAB *lt;
261         struct __db_lock *lockp;
262         int do_all;
263 {
264         struct __db_lock *lp_w, *lp_h, *next_waiter;
265         DB_LOCKOBJ *sh_obj;
266         int state_changed;
267
268         if (lockp->refcount == 0 || (lockp->status != DB_LSTAT_HELD &&
269             lockp->status != DB_LSTAT_WAITING) || lockp->obj == 0) {
270                 __db_err(lt->dbenv, "lock_put: invalid lock %lu",
271                     (u_long)((u_int8_t *)lockp - (u_int8_t *)lt->region));
272                 return (EINVAL);
273         }
274
275         if (do_all)
276                 lt->region->nreleases += lockp->refcount;
277         else
278                 lt->region->nreleases++;
279         if (do_all == 0 && lockp->refcount > 1) {
280                 lockp->refcount--;
281                 return (0);
282         }
283
284         /* Get the object associated with this lock. */
285         sh_obj = (DB_LOCKOBJ *)((u_int8_t *)lockp + lockp->obj);
286
287         /* Remove lock from locker list. */
288         SH_LIST_REMOVE(lockp, locker_links, __db_lock);
289
290         /* Remove this lock from its holders/waitlist. */
291         if (lockp->status != DB_LSTAT_HELD)
292                 __lock_remove_waiter(lt, sh_obj, lockp, DB_LSTAT_FREE);
293         else
294                 SH_TAILQ_REMOVE(&sh_obj->holders, lockp, links, __db_lock);
295
296         /*
297          * We need to do lock promotion.  We also need to determine if
298          * we're going to need to run the deadlock detector again.  If
299          * we release locks, and there are waiters, but no one gets promoted,
300          * then we haven't fundamentally changed the lockmgr state, so
301          * we may still have a deadlock and we have to run again.  However,
302          * if there were no waiters, or we actually promoted someone, then
303          * we are OK and we don't have to run it immediately.
304          */
305         for (lp_w = SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock),
306             state_changed = lp_w == NULL;
307             lp_w != NULL;
308             lp_w = next_waiter) {
309                 next_waiter = SH_TAILQ_NEXT(lp_w, links, __db_lock);
310                 for (lp_h = SH_TAILQ_FIRST(&sh_obj->holders, __db_lock);
311                     lp_h != NULL;
312                     lp_h = SH_TAILQ_NEXT(lp_h, links, __db_lock)) {
313                         if (CONFLICTS(lt, lp_h->mode, lp_w->mode) &&
314                             lp_h->holder != lp_w->holder)
315                                 break;
316                 }
317                 if (lp_h != NULL)       /* Found a conflict. */
318                         break;
319
320                 /* No conflict, promote the waiting lock. */
321                 SH_TAILQ_REMOVE(&sh_obj->waiters, lp_w, links, __db_lock);
322                 lp_w->status = DB_LSTAT_PENDING;
323                 SH_TAILQ_INSERT_TAIL(&sh_obj->holders, lp_w, links);
324
325                 /* Wake up waiter. */
326                 (void)__db_mutex_unlock(&lp_w->mutex, lt->reginfo.fd);
327                 state_changed = 1;
328         }
329
330         /* Check if object should be reclaimed. */
331         if (SH_TAILQ_FIRST(&sh_obj->holders, __db_lock) == NULL) {
332                 HASHREMOVE_EL(lt->hashtab, __db_lockobj,
333                     links, sh_obj, lt->region->table_size, __lock_lhash);
334                 if (sh_obj->lockobj.size > sizeof(sh_obj->objdata))
335                         __db_shalloc_free(lt->mem,
336                             SH_DBT_PTR(&sh_obj->lockobj));
337                 SH_TAILQ_INSERT_HEAD(&lt->region->free_objs, sh_obj, links,
338                     __db_lockobj);
339                 state_changed = 1;
340         }
341
342         /* Free lock. */
343         lockp->status = DB_LSTAT_FREE;
344         SH_TAILQ_INSERT_HEAD(&lt->region->free_locks, lockp, links, __db_lock);
345
346         /*
347          * If we did not promote anyone; we need to run the deadlock
348          * detector again.
349          */
350         if (state_changed == 0)
351                 lt->region->need_dd = 1;
352
353         return (0);
354 }
355
356 static int
357 __lock_get_internal(lt, locker, flags, obj, lock_mode, lockp)
358         DB_LOCKTAB *lt;
359         u_int32_t locker, flags;
360         const DBT *obj;
361         db_lockmode_t lock_mode;
362         struct __db_lock **lockp;
363 {
364         struct __db_lock *newl, *lp;
365         DB_LOCKOBJ *sh_obj, *sh_locker;
366         DB_LOCKREGION *lrp;
367         size_t newl_off;
368         int ihold, ret;
369
370         ret = 0;
371         /*
372          * Check that lock mode is valid.
373          */
374
375         lrp = lt->region;
376         if ((u_int32_t)lock_mode >= lrp->nmodes) {
377                 __db_err(lt->dbenv,
378                     "lock_get: invalid lock mode %lu\n", (u_long)lock_mode);
379                 return (EINVAL);
380         }
381
382         /* Allocate a new lock.  Optimize for the common case of a grant. */
383         if ((newl = SH_TAILQ_FIRST(&lrp->free_locks, __db_lock)) == NULL) {
384                 if ((ret = __lock_grow_region(lt, DB_LOCK_LOCK, 0)) != 0)
385                         return (ret);
386                 lrp = lt->region;
387                 newl = SH_TAILQ_FIRST(&lrp->free_locks, __db_lock);
388         }
389         newl_off = LOCK_TO_OFFSET(lt, newl);
390
391         /* Optimize for common case of granting a lock. */
392         SH_TAILQ_REMOVE(&lrp->free_locks, newl, links, __db_lock);
393
394         newl->mode = lock_mode;
395         newl->status = DB_LSTAT_HELD;
396         newl->holder = locker;
397         newl->refcount = 1;
398
399         if ((ret = __lock_getobj(lt, 0, obj, DB_LOCK_OBJTYPE, &sh_obj)) != 0)
400                 return (ret);
401
402         lrp = lt->region;                       /* getobj might have grown */
403         newl = OFFSET_TO_LOCK(lt, newl_off);
404
405         /* Now make new lock point to object */
406         newl->obj = SH_PTR_TO_OFF(newl, sh_obj);
407
408         /*
409          * Now we have a lock and an object and we need to see if we should
410          * grant the lock.  We use a FIFO ordering so we can only grant a
411          * new lock if it does not conflict with anyone on the holders list
412          * OR anyone on the waiters list.  The reason that we don't grant if
413          * there's a conflict is that this can lead to starvation (a writer
414          * waiting on a popularly read item will never be granted).  The
415          * downside of this is that a waiting reader can prevent an upgrade
416          * from reader to writer, which is not uncommon.
417          *
418          * There is one exception to the no-conflict rule.  If a lock is held
419          * by the requesting locker AND the new lock does not conflict with
420          * any other holders, then we grant the lock.  The most common place
421          * this happens is when the holder has a WRITE lock and a READ lock
422          * request comes in for the same locker.  If we do not grant the read
423          * lock, then we guarantee deadlock.
424          *
425          * In case of conflict, we put the new lock on the end of the waiters
426          * list.
427          */
428         ihold = 0;
429         for (lp = SH_TAILQ_FIRST(&sh_obj->holders, __db_lock);
430             lp != NULL;
431             lp = SH_TAILQ_NEXT(lp, links, __db_lock)) {
432                 if (locker == lp->holder) {
433                         if (lp->mode == lock_mode &&
434                             lp->status == DB_LSTAT_HELD) {
435                                 /* Lock is held, just inc the ref count. */
436                                 lp->refcount++;
437                                 SH_TAILQ_INSERT_HEAD(&lrp->free_locks,
438                                     newl, links, __db_lock);
439                                 *lockp = lp;
440                                 return (0);
441                         } else
442                                 ihold = 1;
443                 } else if (CONFLICTS(lt, lp->mode, lock_mode))
444                         break;
445         }
446
447         if (lp == NULL && !ihold)
448                 for (lp = SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock);
449                     lp != NULL;
450                     lp = SH_TAILQ_NEXT(lp, links, __db_lock)) {
451                         if (CONFLICTS(lt, lp->mode, lock_mode) &&
452                             locker != lp->holder)
453                                 break;
454                 }
455         if (lp == NULL)
456                 SH_TAILQ_INSERT_TAIL(&sh_obj->holders, newl, links);
457         else if (!(flags & DB_LOCK_NOWAIT))
458                 SH_TAILQ_INSERT_TAIL(&sh_obj->waiters, newl, links);
459         else {
460                 /* Free the lock and return an error. */
461                 newl->status = DB_LSTAT_FREE;
462                 SH_TAILQ_INSERT_HEAD(&lrp->free_locks, newl, links, __db_lock);
463                 return (DB_LOCK_NOTGRANTED);
464         }
465
466         /*
467          * This is really a blocker for the process, so initialize it
468          * set.  That way the current process will block when it tries
469          * to get it and the waking process will release it.
470          */
471         (void)__db_mutex_init(&newl->mutex,
472             MUTEX_LOCK_OFFSET(lt->region, &newl->mutex));
473         (void)__db_mutex_lock(&newl->mutex, lt->reginfo.fd);
474
475         /*
476          * Now, insert the lock onto its locker's list.
477          */
478         if ((ret =
479             __lock_getobj(lt, locker, NULL, DB_LOCK_LOCKER, &sh_locker)) != 0)
480                 return (ret);
481
482         lrp = lt->region;
483         SH_LIST_INSERT_HEAD(&sh_locker->heldby, newl, locker_links, __db_lock);
484
485         if (lp != NULL) {
486                 newl->status = DB_LSTAT_WAITING;
487                 lrp->nconflicts++;
488                 /*
489                  * We are about to wait; must release the region mutex.
490                  * Then, when we wakeup, we need to reacquire the region
491                  * mutex before continuing.
492                  */
493                 if (lrp->detect == DB_LOCK_NORUN)
494                         lt->region->need_dd = 1;
495                 UNLOCK_LOCKREGION(lt);
496
497                 /*
498                  * We are about to wait; before waiting, see if the deadlock
499                  * detector should be run.
500                  */
501                 if (lrp->detect != DB_LOCK_NORUN)
502                         ret = lock_detect(lt, 0, lrp->detect);
503
504                 (void)__db_mutex_lock(&newl->mutex, lt->reginfo.fd);
505
506                 LOCK_LOCKREGION(lt);
507                 if (newl->status != DB_LSTAT_PENDING) {
508                         /* Return to free list. */
509                         __lock_checklocker(lt, newl, 0);
510                         SH_TAILQ_INSERT_HEAD(&lrp->free_locks, newl, links,
511                             __db_lock);
512                         switch (newl->status) {
513                                 case DB_LSTAT_ABORTED:
514                                         ret = DB_LOCK_DEADLOCK;
515                                         break;
516                                 case DB_LSTAT_NOGRANT:
517                                         ret = DB_LOCK_NOTGRANTED;
518                                         break;
519                                 default:
520                                         ret = EINVAL;
521                                         break;
522                         }
523                         newl->status = DB_LSTAT_FREE;
524                         newl = NULL;
525                 } else
526                         newl->status = DB_LSTAT_HELD;
527         }
528
529         *lockp = newl;
530         return (ret);
531 }
532
533 /*
534  * __lock_is_locked --
535  *
536  * PUBLIC: int __lock_is_locked
537  * PUBLIC:    __P((DB_LOCKTAB *, u_int32_t, DBT *, db_lockmode_t));
538  */
539 int
540 __lock_is_locked(lt, locker, dbt, mode)
541         DB_LOCKTAB *lt;
542         u_int32_t locker;
543         DBT *dbt;
544         db_lockmode_t mode;
545 {
546         struct __db_lock *lp;
547         DB_LOCKOBJ *sh_obj;
548         DB_LOCKREGION *lrp;
549
550         lrp = lt->region;
551
552         /* Look up the object in the hash table. */
553         HASHLOOKUP(lt->hashtab, __db_lockobj, links,
554             dbt, sh_obj, lrp->table_size, __lock_ohash, __lock_cmp);
555         if (sh_obj == NULL)
556                 return (0);
557
558         for (lp = SH_TAILQ_FIRST(&sh_obj->holders, __db_lock);
559             lp != NULL;
560             lp = SH_TAILQ_FIRST(&sh_obj->holders, __db_lock)) {
561                 if (lp->holder == locker && lp->mode == mode)
562                         return (1);
563         }
564
565         return (0);
566 }
567
568 /*
569  * __lock_printlock --
570  *
571  * PUBLIC: void __lock_printlock __P((DB_LOCKTAB *, struct __db_lock *, int));
572  */
573 void
574 __lock_printlock(lt, lp, ispgno)
575         DB_LOCKTAB *lt;
576         struct __db_lock *lp;
577         int ispgno;
578 {
579         DB_LOCKOBJ *lockobj;
580         db_pgno_t pgno;
581         size_t obj;
582         u_int8_t *ptr;
583         const char *mode, *status;
584
585         switch (lp->mode) {
586         case DB_LOCK_IREAD:
587                 mode = "IREAD";
588                 break;
589         case DB_LOCK_IWR:
590                 mode = "IWR";
591                 break;
592         case DB_LOCK_IWRITE:
593                 mode = "IWRITE";
594                 break;
595         case DB_LOCK_NG:
596                 mode = "NG";
597                 break;
598         case DB_LOCK_READ:
599                 mode = "READ";
600                 break;
601         case DB_LOCK_WRITE:
602                 mode = "WRITE";
603                 break;
604         default:
605                 mode = "UNKNOWN";
606                 break;
607         }
608         switch (lp->status) {
609         case DB_LSTAT_ABORTED:
610                 status = "ABORT";
611                 break;
612         case DB_LSTAT_ERR:
613                 status = "ERROR";
614                 break;
615         case DB_LSTAT_FREE:
616                 status = "FREE";
617                 break;
618         case DB_LSTAT_HELD:
619                 status = "HELD";
620                 break;
621         case DB_LSTAT_NOGRANT:
622                 status = "NONE";
623                 break;
624         case DB_LSTAT_WAITING:
625                 status = "WAIT";
626                 break;
627         case DB_LSTAT_PENDING:
628                 status = "PENDING";
629                 break;
630         default:
631                 status = "UNKNOWN";
632                 break;
633         }
634         printf("\t%lx\t%s\t%lu\t%s\t",
635             (u_long)lp->holder, mode, (u_long)lp->refcount, status);
636
637         lockobj = (DB_LOCKOBJ *)((u_int8_t *)lp + lp->obj);
638         ptr = SH_DBT_PTR(&lockobj->lockobj);
639         if (ispgno) {
640                 /* Assume this is a DBT lock. */
641                 memcpy(&pgno, ptr, sizeof(db_pgno_t));
642                 printf("page %lu\n", (u_long)pgno);
643         } else {
644                 obj = (u_int8_t *)lp + lp->obj - (u_int8_t *)lt->region;
645                 printf("0x%lx ", (u_long)obj);
646                 __db_pr(ptr, lockobj->lockobj.size);
647                 printf("\n");
648         }
649 }
650
651 /*
652  * PUBLIC: int __lock_getobj  __P((DB_LOCKTAB *,
653  * PUBLIC:     u_int32_t, const DBT *, u_int32_t type, DB_LOCKOBJ **));
654  */
655 int
656 __lock_getobj(lt, locker, dbt, type, objp)
657         DB_LOCKTAB *lt;
658         u_int32_t locker, type;
659         const DBT *dbt;
660         DB_LOCKOBJ **objp;
661 {
662         DB_LOCKREGION *lrp;
663         DB_LOCKOBJ *sh_obj;
664         u_int32_t obj_size;
665         int ret;
666         void *p, *src;
667
668         lrp = lt->region;
669
670         /* Look up the object in the hash table. */
671         if (type == DB_LOCK_OBJTYPE) {
672                 HASHLOOKUP(lt->hashtab, __db_lockobj, links, dbt, sh_obj,
673                     lrp->table_size, __lock_ohash, __lock_cmp);
674                 obj_size = dbt->size;
675         } else {
676                 HASHLOOKUP(lt->hashtab, __db_lockobj, links, locker,
677                     sh_obj, lrp->table_size, __lock_locker_hash,
678                     __lock_locker_cmp);
679                 obj_size = sizeof(locker);
680         }
681
682         /*
683          * If we found the object, then we can just return it.  If
684          * we didn't find the object, then we need to create it.
685          */
686         if (sh_obj == NULL) {
687                 /* Create new object and then insert it into hash table. */
688                 if ((sh_obj =
689                     SH_TAILQ_FIRST(&lrp->free_objs, __db_lockobj)) == NULL) {
690                         if ((ret = __lock_grow_region(lt, DB_LOCK_OBJ, 0)) != 0)
691                                 return (ret);
692                         lrp = lt->region;
693                         sh_obj = SH_TAILQ_FIRST(&lrp->free_objs, __db_lockobj);
694                 }
695
696                 /*
697                  * If we can fit this object in the structure, do so instead
698                  * of shalloc-ing space for it.
699                  */
700                 if (obj_size <= sizeof(sh_obj->objdata))
701                         p = sh_obj->objdata;
702                 else
703                         if ((ret =
704                             __db_shalloc(lt->mem, obj_size, 0, &p)) != 0) {
705                                 if ((ret = __lock_grow_region(lt,
706                                     DB_LOCK_MEM, obj_size)) != 0)
707                                         return (ret);
708                                 lrp = lt->region;
709                                 /* Reacquire the head of the list. */
710                                 sh_obj = SH_TAILQ_FIRST(&lrp->free_objs,
711                                     __db_lockobj);
712                                 (void)__db_shalloc(lt->mem, obj_size, 0, &p);
713                         }
714
715                 src = type == DB_LOCK_OBJTYPE ? dbt->data : (void *)&locker;
716                 memcpy(p, src, obj_size);
717
718                 sh_obj->type = type;
719                 SH_TAILQ_REMOVE(&lrp->free_objs, sh_obj, links, __db_lockobj);
720
721                 SH_TAILQ_INIT(&sh_obj->waiters);
722                 if (type == DB_LOCK_LOCKER)
723                         SH_LIST_INIT(&sh_obj->heldby);
724                 else
725                         SH_TAILQ_INIT(&sh_obj->holders);
726                 sh_obj->lockobj.size = obj_size;
727                 sh_obj->lockobj.off = SH_PTR_TO_OFF(&sh_obj->lockobj, p);
728
729                 HASHINSERT(lt->hashtab,
730                     __db_lockobj, links, sh_obj, lrp->table_size, __lock_lhash);
731
732                 if (type == DB_LOCK_LOCKER)
733                         lrp->nlockers++;
734         }
735
736         *objp = sh_obj;
737         return (0);
738 }
739
740 /*
741  * Any lock on the waitlist has a process waiting for it.  Therefore, we
742  * can't return the lock to the freelist immediately.  Instead, we can
743  * remove the lock from the list of waiters, set the status field of the
744  * lock, and then let the process waking up return the lock to the
745  * free list.
746  */
747 static void
748 __lock_remove_waiter(lt, sh_obj, lockp, status)
749         DB_LOCKTAB *lt;
750         DB_LOCKOBJ *sh_obj;
751         struct __db_lock *lockp;
752         db_status_t status;
753 {
754         SH_TAILQ_REMOVE(&sh_obj->waiters, lockp, links, __db_lock);
755         lockp->status = status;
756
757         /* Wake whoever is waiting on this lock. */
758         (void)__db_mutex_unlock(&lockp->mutex, lt->reginfo.fd);
759 }
760
761 static void
762 __lock_checklocker(lt, lockp, do_remove)
763         DB_LOCKTAB *lt;
764         struct __db_lock *lockp;
765         int do_remove;
766 {
767         DB_LOCKOBJ *sh_locker;
768
769         if (do_remove)
770                 SH_LIST_REMOVE(lockp, locker_links, __db_lock);
771
772         /* if the locker list is NULL, free up the object. */
773         if (__lock_getobj(lt, lockp->holder, NULL, DB_LOCK_LOCKER, &sh_locker)
774             == 0 && SH_LIST_FIRST(&sh_locker->heldby, __db_lock) == NULL) {
775                 __lock_freeobj(lt, sh_locker);
776                     lt->region->nlockers--;
777         }
778 }
779
780 static void
781 __lock_freeobj(lt, obj)
782         DB_LOCKTAB *lt;
783         DB_LOCKOBJ *obj;
784 {
785         HASHREMOVE_EL(lt->hashtab,
786             __db_lockobj, links, obj, lt->region->table_size, __lock_lhash);
787         if (obj->lockobj.size > sizeof(obj->objdata))
788                 __db_shalloc_free(lt->mem, SH_DBT_PTR(&obj->lockobj));
789         SH_TAILQ_INSERT_HEAD(&lt->region->free_objs, obj, links, __db_lockobj);
790 }