2 * See the file LICENSE for redistribution information.
4 * Copyright (c) 1996, 1997
5 * Sleepycat Software. All rights reserved.
11 static const char sccsid[] = "@(#)lock.c 10.31 (Sleepycat) 8/17/97";
14 #ifndef NO_SYSTEM_INCLUDES
15 #include <sys/types.h>
33 #include "common_ext.h"
36 static void __lock_checklocker __P((DB_LOCKTAB *, struct __db_lock *, int));
37 static int __lock_count_locks __P((DB_LOCKREGION *));
38 static int __lock_count_objs __P((DB_LOCKREGION *));
39 static int __lock_create __P((const char *, int, DB_ENV *));
40 static void __lock_freeobj __P((DB_LOCKTAB *, DB_LOCKOBJ *));
41 static int __lock_get_internal __P((DB_LOCKTAB *, u_int32_t, int, const DBT *,
42 db_lockmode_t, struct __db_lock **));
43 static int __lock_grow_region __P((DB_LOCKTAB *, int, size_t));
44 static int __lock_put_internal __P((DB_LOCKTAB *, struct __db_lock *, int));
45 static void __lock_remove_waiter
46 __P((DB_LOCKTAB *, DB_LOCKOBJ *, struct __db_lock *, db_status_t));
47 static void __lock_reset_region __P((DB_LOCKTAB *));
48 static int __lock_validate_region __P((DB_LOCKTAB *));
50 static void __lock_dump_locker __P((DB_LOCKTAB *, DB_LOCKOBJ *));
51 static void __lock_dump_object __P((DB_LOCKTAB *, DB_LOCKOBJ *));
52 static void __lock_printlock __P((DB_LOCKTAB *, struct __db_lock *, int));
56 * Create and initialize a lock region in shared memory.
61 * Create the lock region. Returns an errno. In most cases,
62 * the errno should be that returned by __db_ropen, in which case
63 * an EAGAIN means that we should retry, and an EEXIST means that
64 * the region exists and we didn't need to create it. Any other
65 * sort of errno should be treated as a system error, leading to a
66 * failure of the original interface call.
69 __lock_create(path, mode, dbenv)
75 struct lock_header *tq_head;
76 struct obj_header *obj_head;
81 int fd, lock_modes, nelements, ret;
82 u_int8_t *conflicts, *curaddr;
84 maxlocks = dbenv == NULL || dbenv->lk_max == 0 ?
85 DB_LOCK_DEFAULT_N : dbenv->lk_max;
86 lock_modes = dbenv == NULL || dbenv->lk_modes == 0 ?
87 DB_LOCK_RW_N : dbenv->lk_modes;
88 conflicts = dbenv == NULL || dbenv->lk_conflicts == NULL ?
89 (u_int8_t *)db_rw_conflicts : dbenv->lk_conflicts;
92 __db_rcreate(dbenv, DB_APP_NONE, path, DB_DEFAULT_LOCK_FILE, mode,
93 LOCK_REGION_SIZE(lock_modes, maxlocks, __db_tablesize(maxlocks)),
97 /* Region exists; now initialize it. */
98 lrp->table_size = __db_tablesize(maxlocks);
99 lrp->magic = DB_LOCKMAGIC;
100 lrp->version = DB_LOCKVERSION;
102 lrp->maxlocks = maxlocks;
104 lrp->detect = DB_LOCK_NORUN;
105 lrp->numobjs = maxlocks;
107 lrp->mem_bytes = ALIGN(STRING_SIZE(maxlocks), sizeof(size_t));
108 lrp->increment = lrp->hdr.size / 2;
109 lrp->nmodes = lock_modes;
116 * As we write the region, we've got to maintain the alignment
117 * for the structures that follow each chunk. This information
118 * ends up being encapsulated both in here as well as in the
119 * lock.h file for the XXX_SIZE macros.
121 /* Initialize conflict matrix. */
122 curaddr = (u_int8_t *)lrp + sizeof(DB_LOCKREGION);
123 memcpy(curaddr, conflicts, lock_modes * lock_modes);
124 curaddr += lock_modes * lock_modes;
127 * Initialize hash table.
129 curaddr = (u_int8_t *)ALIGNP(curaddr, LOCK_HASH_ALIGN);
130 lrp->hash_off = curaddr - (u_int8_t *)lrp;
131 nelements = lrp->table_size;
132 __db_hashinit(curaddr, nelements);
133 curaddr += nelements * sizeof(DB_HASHTAB);
136 * Initialize locks onto a free list. Since locks contains mutexes,
137 * we need to make sure that each lock is aligned on a MUTEX_ALIGNMENT
140 curaddr = (u_int8_t *)ALIGNP(curaddr, MUTEX_ALIGNMENT);
141 tq_head = &lrp->free_locks;
142 SH_TAILQ_INIT(tq_head);
144 for (i = 0; i++ < maxlocks;
145 curaddr += ALIGN(sizeof(struct __db_lock), MUTEX_ALIGNMENT)) {
146 lp = (struct __db_lock *)curaddr;
147 lp->status = DB_LSTAT_FREE;
148 SH_TAILQ_INSERT_HEAD(tq_head, lp, links, __db_lock);
151 /* Initialize objects onto a free list. */
152 obj_head = &lrp->free_objs;
153 SH_TAILQ_INIT(obj_head);
155 for (i = 0; i++ < maxlocks; curaddr += sizeof(DB_LOCKOBJ)) {
156 op = (DB_LOCKOBJ *)curaddr;
157 SH_TAILQ_INSERT_HEAD(obj_head, op, links, __db_lockobj);
161 * Initialize the string space; as for all shared memory allocation
162 * regions, this requires size_t alignment, since we store the
163 * lengths of malloc'd areas in the area..
165 curaddr = (u_int8_t *)ALIGNP(curaddr, sizeof(size_t));
166 lrp->mem_off = curaddr - (u_int8_t *)lrp;
167 __db_shalloc_init(curaddr, lrp->mem_bytes);
169 /* Release the lock. */
170 (void)__db_mutex_unlock(&lrp->hdr.lock, fd);
172 /* Now unmap the region. */
173 if ((ret = __db_rclose(dbenv, fd, lrp)) != 0) {
174 (void)lock_unlink(path, 1 /* force */, dbenv);
182 lock_open(path, flags, mode, dbenv, ltp)
191 /* Validate arguments. */
192 #ifdef HAVE_SPINLOCKS
193 #define OKFLAGS (DB_CREATE | DB_THREAD)
195 #define OKFLAGS (DB_CREATE)
197 if ((ret = __db_fchk(dbenv, "lock_open", flags, OKFLAGS)) != 0)
201 * Create the lock table structure.
203 if ((lt = (DB_LOCKTAB *)calloc(1, sizeof(DB_LOCKTAB))) == NULL) {
204 __db_err(dbenv, "%s", strerror(errno));
210 * Now, create the lock region if it doesn't already exist.
213 retry: if (LF_ISSET(DB_CREATE) &&
214 (ret = __lock_create(path, mode, dbenv)) != 0)
215 if (ret == EAGAIN && ++retry_cnt < 3) {
216 (void)__db_sleep(1, 0);
218 } else if (ret == EEXIST) /* We did not create the region */
224 * Finally, open the region, map it in, and increment the
228 retry1: if ((ret = __db_ropen(dbenv, DB_APP_NONE, path, DB_DEFAULT_LOCK_FILE,
229 LF_ISSET(~(DB_CREATE | DB_THREAD)), <->fd, <->region)) != 0) {
230 if (ret == EAGAIN && ++retry_cnt < 3) {
231 (void)__db_sleep(1, 0);
237 if (lt->region->magic != DB_LOCKMAGIC) {
238 __db_err(dbenv, "lock_open: Bad magic number");
243 /* Check for automatic deadlock detection. */
244 if (dbenv->lk_detect != DB_LOCK_NORUN) {
245 if (lt->region->detect != DB_LOCK_NORUN &&
246 dbenv->lk_detect != DB_LOCK_DEFAULT &&
247 lt->region->detect != dbenv->lk_detect) {
249 "lock_open: incompatible deadlock detector mode");
253 if (lt->region->detect == DB_LOCK_NORUN)
254 lt->region->detect = dbenv->lk_detect;
257 /* Set up remaining pointers into region. */
258 lt->conflicts = (u_int8_t *)lt->region + sizeof(DB_LOCKREGION);
260 (DB_HASHTAB *)((u_int8_t *)lt->region + lt->region->hash_off);
261 lt->mem = (void *)((u_int8_t *)lt->region + lt->region->mem_off);
262 lt->reg_size = lt->region->hdr.size;
267 /* Error handling. */
268 out: if (lt->region != NULL)
269 (void)__db_rclose(lt->dbenv, lt->fd, lt->region);
270 if (LF_ISSET(DB_CREATE))
271 (void)lock_unlink(path, 1, lt->dbenv);
284 if (lt->region->id >= DB_LOCK_MAXID)
286 id = ++lt->region->id;
287 UNLOCK_LOCKREGION(lt);
294 lock_vec(lt, locker, flags, list, nlist, elistp)
298 DB_LOCKREQ *list, **elistp;
300 struct __db_lock *lp;
301 DB_LOCKOBJ *sh_obj, *sh_locker;
304 /* Validate arguments. */
306 __db_fchk(lt->dbenv, "lock_vec", flags, DB_LOCK_NOWAIT)) != 0)
311 if ((ret = __lock_validate_region(lt)) != 0) {
312 UNLOCK_LOCKREGION(lt);
317 for (i = 0; i < nlist && ret == 0; i++) {
318 switch (list[i].op) {
320 ret = __lock_get_internal(lt, locker, flags,
321 list[i].obj, list[i].mode, &lp);
323 list[i].lock = LOCK_TO_OFFSET(lt, lp);
326 lp = OFFSET_TO_LOCK(lt, list[i].lock);
327 if (lp->holder != locker) {
328 ret = DB_LOCK_NOTHELD;
331 list[i].mode = lp->mode;
333 /* XXX Need to copy the object. ??? */
334 ret = __lock_put_internal(lt, lp, 0);
336 case DB_LOCK_PUT_ALL:
337 /* Find the locker. */
338 if ((ret = __lock_getobj(lt, locker,
339 NULL, DB_LOCK_LOCKER, &sh_locker)) != 0)
342 for (lp = SH_LIST_FIRST(&sh_locker->heldby, __db_lock);
344 lp = SH_LIST_FIRST(&sh_locker->heldby, __db_lock)) {
345 if ((ret = __lock_put_internal(lt, lp, 0)) != 0)
348 __lock_freeobj(lt, sh_locker);
349 lt->region->nlockers--;
351 case DB_LOCK_PUT_OBJ:
353 /* Look up the object in the hash table. */
354 __db_hashlookup(lt->hashtab, __db_lockobj, links,
355 list[i].obj, sh_obj, lt->region->table_size,
356 __lock_ohash, __lock_cmp);
357 if (sh_obj == NULL) {
362 * Release waiters first, because they won't cause
363 * anyone else to be awakened. If we release the
364 * lockers first, all the waiters get awakened
367 for (lp = SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock);
369 lp = SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock)) {
370 lt->region->nreleases += lp->refcount;
371 __lock_remove_waiter(lt, sh_obj, lp,
373 __lock_checklocker(lt, lp, 1);
376 for (lp = SH_TAILQ_FIRST(&sh_obj->holders, __db_lock);
378 lp = SH_TAILQ_FIRST(&sh_obj->holders, __db_lock)) {
380 lt->region->nreleases += lp->refcount;
381 SH_LIST_REMOVE(lp, locker_links, __db_lock);
382 SH_TAILQ_REMOVE(&sh_obj->holders, lp, links,
384 lp->status = DB_LSTAT_FREE;
385 SH_TAILQ_INSERT_HEAD(<->region->free_locks,
386 lp, links, __db_lock);
389 /* Now free the object. */
390 __lock_freeobj(lt, sh_obj);
394 /* Find the locker. */
395 if ((ret = __lock_getobj(lt, locker,
396 NULL, DB_LOCK_LOCKER, &sh_locker)) != 0)
399 for (lp = SH_LIST_FIRST(&sh_locker->heldby, __db_lock);
401 lp = SH_LIST_NEXT(lp, locker_links, __db_lock)) {
402 __lock_printlock(lt, lp, 1);
406 __lock_freeobj(lt, sh_locker);
407 lt->region->nlockers--;
417 if (lt->region->need_dd && lt->region->detect != DB_LOCK_NORUN) {
419 lt->region->need_dd = 0;
423 UNLOCK_LOCKREGION(lt);
425 if (ret == 0 && run_dd)
426 lock_detect(lt, 0, lt->region->detect);
428 if (elistp && ret != 0)
429 *elistp = &list[i - 1];
434 lock_get(lt, locker, flags, obj, lock_mode, lock)
439 db_lockmode_t lock_mode;
442 struct __db_lock *lockp;
445 /* Validate arguments. */
447 __db_fchk(lt->dbenv, "lock_get", flags, DB_LOCK_NOWAIT)) != 0)
452 ret = __lock_validate_region(lt);
453 if (ret == 0 && (ret = __lock_get_internal(lt,
454 locker, flags, obj, lock_mode, &lockp)) == 0) {
455 *lock = LOCK_TO_OFFSET(lt, lockp);
456 lt->region->nrequests++;
459 UNLOCK_LOCKREGION(lt);
468 struct __db_lock *lockp;
473 if ((ret = __lock_validate_region(lt)) != 0)
476 lockp = OFFSET_TO_LOCK(lt, lock);
477 ret = __lock_put_internal(lt, lockp, 0);
480 __lock_checklocker(lt, lockp, 0);
482 if (lt->region->need_dd && lt->region->detect != DB_LOCK_NORUN) {
484 lt->region->need_dd = 0;
488 UNLOCK_LOCKREGION(lt);
490 if (ret == 0 && run_dd)
491 lock_detect(lt, 0, lt->region->detect);
502 if ((ret = __db_rclose(lt->dbenv, lt->fd, lt->region)) != 0)
505 /* Free lock table. */
511 lock_unlink(path, force, dbenv)
516 return (__db_runlink(dbenv,
517 DB_APP_NONE, path, DB_DEFAULT_LOCK_FILE, force));
521 * XXX This looks like it could be void, but I'm leaving it returning
522 * an int because I think it will have to when we go through and add
523 * the appropriate error checking for the EINTR on mutexes.
526 __lock_put_internal(lt, lockp, do_all)
528 struct __db_lock *lockp;
531 struct __db_lock *lp_w, *lp_h, *next_waiter;
535 if (lockp->refcount == 0 || (lockp->status != DB_LSTAT_HELD &&
536 lockp->status != DB_LSTAT_WAITING) || lockp->obj == 0) {
537 __db_err(lt->dbenv, "lock_put: invalid lock %lu",
538 (u_long)((u_int8_t *)lockp - (u_int8_t *)lt->region));
543 lt->region->nreleases += lockp->refcount;
545 lt->region->nreleases++;
546 if (do_all == 0 && lockp->refcount > 1) {
551 /* Get the object associated with this lock. */
552 sh_obj = (DB_LOCKOBJ *)((u_int8_t *)lockp + lockp->obj);
554 /* Remove lock from locker list. */
555 SH_LIST_REMOVE(lockp, locker_links, __db_lock);
557 /* Remove this lock from its holders/waitlist. */
558 if (lockp->status != DB_LSTAT_HELD)
559 __lock_remove_waiter(lt, sh_obj, lockp, DB_LSTAT_FREE);
561 SH_TAILQ_REMOVE(&sh_obj->holders, lockp, links, __db_lock);
564 * We need to do lock promotion. We also need to determine if
565 * we're going to need to run the deadlock detector again. If
566 * we release locks, and there are waiters, but no one gets promoted,
567 * then we haven't fundamentally changed the lockmgr state, so
568 * we may still have a deadlock and we have to run again. However,
569 * if there were no waiters, or we actually promoted someone, then
570 * we are OK and we don't have to run it immediately.
572 for (lp_w = SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock),
573 state_changed = lp_w == NULL;
575 lp_w = next_waiter) {
576 next_waiter = SH_TAILQ_NEXT(lp_w, links, __db_lock);
577 for (lp_h = SH_TAILQ_FIRST(&sh_obj->holders, __db_lock);
579 lp_h = SH_TAILQ_NEXT(lp_h, links, __db_lock)) {
580 if (CONFLICTS(lt, lp_h->mode, lp_w->mode) &&
581 lp_h->holder != lp_w->holder)
584 if (lp_h != NULL) /* Found a conflict. */
587 /* No conflict, promote the waiting lock. */
588 SH_TAILQ_REMOVE(&sh_obj->waiters, lp_w, links, __db_lock);
589 lp_w->status = DB_LSTAT_PENDING;
590 SH_TAILQ_INSERT_TAIL(&sh_obj->holders, lp_w, links);
592 /* Wake up waiter. */
593 (void)__db_mutex_unlock(&lp_w->mutex, lt->fd);
597 /* Check if object should be reclaimed. */
598 if (SH_TAILQ_FIRST(&sh_obj->holders, __db_lock) == NULL) {
599 __db_hashremove_el(lt->hashtab, __db_lockobj, links, sh_obj,
600 lt->region->table_size, __lock_lhash);
601 __db_shalloc_free(lt->mem, SH_DBT_PTR(&sh_obj->lockobj));
602 SH_TAILQ_INSERT_HEAD(<->region->free_objs, sh_obj, links,
608 lockp->status = DB_LSTAT_FREE;
609 SH_TAILQ_INSERT_HEAD(<->region->free_locks, lockp, links, __db_lock);
612 * If we did not promote anyone; we need to run the deadlock
615 if (state_changed == 0)
616 lt->region->need_dd = 1;
622 __lock_get_internal(lt, locker, flags, obj, lock_mode, lockp)
627 db_lockmode_t lock_mode;
628 struct __db_lock **lockp;
630 struct __db_lock *newl, *lp;
631 DB_LOCKOBJ *sh_obj, *sh_locker;
638 * Check that lock mode is valid.
642 if ((u_int32_t)lock_mode >= lrp->nmodes) {
644 "lock_get: invalid lock mode %lu\n", (u_long)lock_mode);
648 /* Allocate a new lock. Optimize for the common case of a grant. */
649 if ((newl = SH_TAILQ_FIRST(&lrp->free_locks, __db_lock)) == NULL) {
650 if ((ret = __lock_grow_region(lt, DB_LOCK_LOCK, 0)) != 0)
653 newl = SH_TAILQ_FIRST(&lrp->free_locks, __db_lock);
655 newl_off = LOCK_TO_OFFSET(lt, newl);
657 /* Optimize for common case of granting a lock. */
658 SH_TAILQ_REMOVE(&lrp->free_locks, newl, links, __db_lock);
660 newl->mode = lock_mode;
661 newl->status = DB_LSTAT_HELD;
662 newl->holder = locker;
666 __lock_getobj(lt, 0, (DBT *)obj, DB_LOCK_OBJTYPE, &sh_obj)) != 0)
669 lrp = lt->region; /* getobj might have grown */
670 newl = OFFSET_TO_LOCK(lt, newl_off);
672 /* Now make new lock point to object */
673 newl->obj = SH_PTR_TO_OFF(newl, sh_obj);
676 * Now we have a lock and an object and we need to see if we should
677 * grant the lock. We use a FIFO ordering so we can only grant a
678 * new lock if it does not conflict with anyone on the holders list
679 * OR anyone on the waiters list. In case of conflict, we put the
680 * new lock on the end of the waiters list.
682 for (lp = SH_TAILQ_FIRST(&sh_obj->holders, __db_lock);
684 lp = SH_TAILQ_NEXT(lp, links, __db_lock)) {
685 if (CONFLICTS(lt, lp->mode, lock_mode) &&
686 locker != lp->holder)
688 else if (lp->holder == locker && lp->mode == lock_mode &&
689 lp->status == DB_LSTAT_HELD) {
690 /* Lock is already held, just inc the ref count. */
692 SH_TAILQ_INSERT_HEAD(&lrp->free_locks, newl, links,
700 for (lp = SH_TAILQ_FIRST(&sh_obj->waiters, __db_lock);
702 lp = SH_TAILQ_NEXT(lp, links, __db_lock)) {
703 if (CONFLICTS(lt, lp->mode, lock_mode) &&
704 locker != lp->holder)
708 SH_TAILQ_INSERT_TAIL(&sh_obj->holders, newl, links);
709 else if (!(flags & DB_LOCK_NOWAIT))
710 SH_TAILQ_INSERT_TAIL(&sh_obj->waiters, newl, links);
712 /* Free the lock and return an error. */
713 newl->status = DB_LSTAT_FREE;
714 SH_TAILQ_INSERT_HEAD(&lrp->free_locks, newl, links, __db_lock);
715 return (DB_LOCK_NOTGRANTED);
719 * This is really a blocker for the process, so initialize it
720 * set. That way the current process will block when it tries
721 * to get it and the waking process will release it.
723 (void)__db_mutex_init(&newl->mutex,
724 MUTEX_LOCK_OFFSET(lt->region, &newl->mutex));
725 (void)__db_mutex_lock(&newl->mutex, lt->fd,
726 lt->dbenv == NULL ? NULL : lt->dbenv->db_yield);
729 * Now, insert the lock onto its locker's list.
732 __lock_getobj(lt, locker, NULL, DB_LOCK_LOCKER, &sh_locker)) != 0)
736 SH_LIST_INSERT_HEAD(&sh_locker->heldby, newl, locker_links, __db_lock);
739 newl->status = DB_LSTAT_WAITING;
742 * We are about to wait; must release the region mutex.
743 * Then, when we wakeup, we need to reacquire the region
744 * mutex before continuing.
746 if (lrp->detect == DB_LOCK_NORUN)
747 lt->region->need_dd = 1;
748 UNLOCK_LOCKREGION(lt);
751 * We are about to wait; before waiting, see if the deadlock
752 * detector should be run.
754 if (lrp->detect != DB_LOCK_NORUN)
755 ret = lock_detect(lt, 0, lrp->detect);
757 (void)__db_mutex_lock(&newl->mutex,
758 lt->fd, lt->dbenv == NULL ? NULL : lt->dbenv->db_yield);
761 if (newl->status != DB_LSTAT_PENDING) {
762 /* Return to free list. */
763 __lock_checklocker(lt, newl, 0);
764 SH_TAILQ_INSERT_HEAD(&lrp->free_locks, newl, links,
766 switch (newl->status) {
767 case DB_LSTAT_ABORTED:
768 ret = DB_LOCK_DEADLOCK;
770 case DB_LSTAT_NOGRANT:
771 ret = DB_LOCK_NOTGRANTED;
777 newl->status = DB_LSTAT_FREE;
780 newl->status = DB_LSTAT_HELD;
788 * This is called at every interface to verify if the region
789 * has changed size, and if so, to remap the region in and
790 * reset the process pointers.
793 __lock_validate_region(lt)
798 if (lt->reg_size == lt->region->hdr.size)
801 /* Grow the region. */
802 if ((ret = __db_rremap(lt->dbenv, lt->region,
803 lt->reg_size, lt->region->hdr.size, lt->fd, <->region)) != 0)
806 __lock_reset_region(lt);
812 * We have run out of space; time to grow the region.
815 __lock_grow_region(lt, which, howmuch)
820 struct __db_lock *newl;
821 struct lock_header *lock_head;
822 struct obj_header *obj_head;
825 float lock_ratio, obj_ratio;
826 size_t incr, oldsize, used;
827 u_int32_t i, newlocks, newmem, newobjs;
828 int ret, usedlocks, usedmem, usedobjs;
832 oldsize = lrp->hdr.size;
833 incr = lrp->increment;
835 /* Figure out how much of each sort of space we have. */
836 usedmem = lrp->mem_bytes - __db_shalloc_count(lt->mem);
837 usedobjs = lrp->numobjs - __lock_count_objs(lrp);
838 usedlocks = lrp->maxlocks - __lock_count_locks(lrp);
841 * Figure out what fraction of the used space belongs to each
842 * different type of "thing" in the region. Then partition the
843 * new space up according to this ratio.
846 usedlocks * ALIGN(sizeof(struct __db_lock), MUTEX_ALIGNMENT) +
847 usedobjs * sizeof(DB_LOCKOBJ);
849 lock_ratio = usedlocks *
850 ALIGN(sizeof(struct __db_lock), MUTEX_ALIGNMENT) / (float)used;
851 obj_ratio = usedobjs * sizeof(DB_LOCKOBJ) / (float)used;
853 newlocks = (u_int32_t)(lock_ratio *
854 incr / ALIGN(sizeof(struct __db_lock), MUTEX_ALIGNMENT));
855 newobjs = (u_int32_t)(obj_ratio * incr / sizeof(DB_LOCKOBJ));
857 (newobjs * sizeof(DB_LOCKOBJ) +
858 newlocks * ALIGN(sizeof(struct __db_lock), MUTEX_ALIGNMENT));
861 * Make sure we allocate enough memory for the object being
868 incr += newlocks * sizeof(struct __db_lock);
874 incr += newobjs * sizeof(DB_LOCKOBJ);
878 if (newmem < howmuch * 2) {
879 incr += howmuch * 2 - newmem;
880 newmem = howmuch * 2;
885 newmem += ALIGN(incr, sizeof(size_t)) - incr;
886 incr = ALIGN(incr, sizeof(size_t));
889 * Since we are going to be allocating locks at the beginning of the
890 * new chunk, we need to make sure that the chunk is MUTEX_ALIGNMENT
891 * aligned. We did not guarantee this when we created the region, so
892 * we may need to pad the old region by extra bytes to ensure this
895 incr += ALIGN(oldsize, MUTEX_ALIGNMENT) - oldsize;
898 "Growing lock region: %lu locks %lu objs %lu bytes",
899 (u_long)newlocks, (u_long)newobjs, (u_long)newmem);
901 if ((ret = __db_rgrow(lt->dbenv, lt->fd, incr)) != 0)
903 if ((ret = __db_rremap(lt->dbenv,
904 lt->region, oldsize, oldsize + incr, lt->fd, <->region)) != 0)
906 __lock_reset_region(lt);
908 /* Update region parameters. */
910 lrp->increment = incr << 1;
911 lrp->maxlocks += newlocks;
912 lrp->numobjs += newobjs;
913 lrp->mem_bytes += newmem;
915 curaddr = (u_int8_t *)lrp + oldsize;
916 curaddr = (u_int8_t *)ALIGNP(curaddr, MUTEX_ALIGNMENT);
918 /* Put new locks onto the free list. */
919 lock_head = &lrp->free_locks;
920 for (i = 0; i++ < newlocks;
921 curaddr += ALIGN(sizeof(struct __db_lock), MUTEX_ALIGNMENT)) {
922 newl = (struct __db_lock *)curaddr;
923 SH_TAILQ_INSERT_HEAD(lock_head, newl, links, __db_lock);
926 /* Put new objects onto the free list. */
927 obj_head = &lrp->free_objs;
928 for (i = 0; i++ < newobjs; curaddr += sizeof(DB_LOCKOBJ)) {
929 op = (DB_LOCKOBJ *)curaddr;
930 SH_TAILQ_INSERT_HEAD(obj_head, op, links, __db_lockobj);
933 *((size_t *)curaddr) = newmem - sizeof(size_t);
934 curaddr += sizeof(size_t);
935 __db_shalloc_free(lt->mem, curaddr);
942 __lock_dump_region(lt, flags)
946 struct __db_lock *lp;
953 printf("Lock region parameters\n");
954 printf("%s:0x%x\t%s:%lu\t%s:%lu\t%s:%lu\n%s:%lu\t%s:%lu\t%s:%lu\t\n",
955 "magic ", lrp->magic,
956 "version ", (u_long)lrp->version,
957 "processes ", (u_long)lrp->hdr.refcnt,
958 "maxlocks ", (u_long)lrp->maxlocks,
959 "table size ", (u_long)lrp->table_size,
960 "nmodes ", (u_long)lrp->nmodes,
961 "numobjs ", (u_long)lrp->numobjs);
962 printf("%s:%lu\t%s:%lu\t%s:%lu\n%s:%lu\t%s:%lu\t%s:%lu\n",
963 "size ", (u_long)lrp->hdr.size,
964 "nlockers ", (u_long)lrp->nlockers,
965 "hash_off ", (u_long)lrp->hash_off,
966 "increment ", (u_long)lrp->increment,
967 "mem_off ", (u_long)lrp->mem_off,
968 "mem_bytes ", (u_long)lrp->mem_bytes);
969 #ifndef HAVE_SPINLOCKS
970 printf("Mutex: off %lu", (u_long)lrp->hdr.lock.off);
972 #ifdef MUTEX_STATISTICS
973 printf(" waits %lu nowaits %lu",
974 (u_long)lrp->hdr.lock.mutex_set_wait,
975 (u_long)lrp->hdr.lock.mutex_set_nowait);
977 printf("\n%s:%lu\t%s:%lu\t%s:%lu\t%s:%lu\n",
978 "nconflicts ", (u_long)lrp->nconflicts,
979 "nrequests ", (u_long)lrp->nrequests,
980 "nreleases ", (u_long)lrp->nreleases,
981 "ndeadlocks ", (u_long)lrp->ndeadlocks);
982 printf("need_dd %lu\n", (u_long)lrp->need_dd);
983 if (flags & LOCK_DEBUG_CONF) {
984 printf("\nConflict matrix\n");
986 for (i = 0; i < lrp->nmodes; i++) {
987 for (j = 0; j < lrp->nmodes; j++)
989 (u_long)lt->conflicts[i * lrp->nmodes + j]);
994 for (i = 0; i < lrp->table_size; i++) {
995 op = SH_TAILQ_FIRST(<->hashtab[i], __db_lockobj);
996 if (op != NULL && flags & LOCK_DEBUG_BUCKET)
997 printf("Bucket %lu:\n", (unsigned long)i);
999 if (op->type == DB_LOCK_LOCKER &&
1000 flags & LOCK_DEBUG_LOCKERS)
1001 __lock_dump_locker(lt, op);
1002 else if (flags & LOCK_DEBUG_OBJECTS &&
1003 op->type == DB_LOCK_OBJTYPE)
1004 __lock_dump_object(lt, op);
1005 op = SH_TAILQ_NEXT(op, links, __db_lockobj);
1009 if (flags & LOCK_DEBUG_LOCK) {
1010 printf("\nLock Free List\n");
1011 for (lp = SH_TAILQ_FIRST(&lrp->free_locks, __db_lock);
1013 lp = SH_TAILQ_NEXT(lp, links, __db_lock)) {
1014 printf("0x%x: %lu\t%lu\t%lu\t0x%x\n", (u_int)lp,
1015 (u_long)lp->holder, (u_long)lp->mode,
1016 (u_long)lp->status, (u_int)lp->obj);
1020 if (flags & LOCK_DEBUG_LOCK) {
1021 printf("\nObject Free List\n");
1022 for (op = SH_TAILQ_FIRST(&lrp->free_objs, __db_lockobj);
1024 op = SH_TAILQ_NEXT(op, links, __db_lockobj))
1025 printf("0x%x\n", (u_int)op);
1028 if (flags & LOCK_DEBUG_MEM) {
1029 printf("\nMemory Free List\n");
1030 __db_shalloc_dump(stdout, lt->mem);
1035 __lock_dump_locker(lt, op)
1039 struct __db_lock *lp;
1043 ptr = SH_DBT_PTR(&op->lockobj);
1044 memcpy(&locker, ptr, sizeof(u_int32_t));
1045 printf("L %lu", (u_long)locker);
1047 lp = SH_LIST_FIRST(&op->heldby, __db_lock);
1052 for (; lp != NULL; lp = SH_LIST_NEXT(lp, locker_links, __db_lock))
1053 __lock_printlock(lt, lp, 0);
1057 __lock_dump_object(lt, op)
1061 struct __db_lock *lp;
1065 ptr = SH_DBT_PTR(&op->lockobj);
1066 for (j = 0; j < op->lockobj.size; ptr++, j++)
1067 printf("%c", (int)*ptr);
1072 SH_TAILQ_FIRST(&op->holders, __db_lock);
1074 lp = SH_TAILQ_NEXT(lp, links, __db_lock))
1075 __lock_printlock(lt, lp, 0);
1076 lp = SH_TAILQ_FIRST(&op->waiters, __db_lock);
1079 for (; lp != NULL; lp = SH_TAILQ_NEXT(lp, links, __db_lock))
1080 __lock_printlock(lt, lp, 0);
1085 __lock_is_locked(lt, locker, dbt, mode)
1091 struct __db_lock *lp;
1097 /* Look up the object in the hash table. */
1098 __db_hashlookup(lt->hashtab, __db_lockobj, links,
1099 dbt, sh_obj, lrp->table_size, __lock_ohash, __lock_cmp);
1103 for (lp = SH_TAILQ_FIRST(&sh_obj->holders, __db_lock);
1105 lp = SH_TAILQ_FIRST(&sh_obj->holders, __db_lock)) {
1106 if (lp->holder == locker && lp->mode == mode)
1114 __lock_printlock(lt, lp, ispgno)
1116 struct __db_lock *lp;
1119 DB_LOCKOBJ *lockobj;
1132 case DB_LOCK_IWRITE:
1148 switch (lp->status) {
1149 case DB_LSTAT_ABORTED:
1161 case DB_LSTAT_NOGRANT:
1164 case DB_LSTAT_WAITING:
1167 case DB_LSTAT_PENDING:
1174 printf("\t%lu\t%s\t%lu\t%s\t",
1175 (u_long)lp->holder, mode, (u_long)lp->refcount, stat);
1177 lockobj = (DB_LOCKOBJ *)((u_int8_t *)lp + lp->obj);
1178 ptr = SH_DBT_PTR(&lockobj->lockobj);
1180 /* Assume this is a DBT lock. */
1181 memcpy(&pgno, ptr, sizeof(db_pgno_t));
1182 printf("page %lu\n", (u_long)pgno);
1184 obj = (u_int8_t *)lp + lp->obj - (u_int8_t *)lt->region;
1185 printf("0x%lx ", (u_long)obj);
1186 __db_pr(ptr, lockobj->lockobj.size);
1194 __lock_count_locks(lrp)
1197 struct __db_lock *newl;
1201 for (newl = SH_TAILQ_FIRST(&lrp->free_locks, __db_lock);
1203 newl = SH_TAILQ_NEXT(newl, links, __db_lock))
1210 __lock_count_objs(lrp)
1217 for (obj = SH_TAILQ_FIRST(&lrp->free_objs, __db_lockobj);
1219 obj = SH_TAILQ_NEXT(obj, links, __db_lockobj))
1226 * PUBLIC: int __lock_getobj __P((DB_LOCKTAB *,
1227 * PUBLIC: u_int32_t, DBT *, u_int32_t type, DB_LOCKOBJ **));
1230 __lock_getobj(lt, locker, dbt, type, objp)
1232 u_int32_t locker, type;
1244 /* Look up the object in the hash table. */
1245 if (type == DB_LOCK_OBJTYPE) {
1246 __db_hashlookup(lt->hashtab, __db_lockobj, links, dbt, sh_obj,
1247 lrp->table_size, __lock_ohash, __lock_cmp);
1248 obj_size = dbt->size;
1250 __db_hashlookup(lt->hashtab, __db_lockobj, links, locker,
1251 sh_obj, lrp->table_size, __lock_locker_hash,
1253 obj_size = sizeof(locker);
1257 * If we found the object, then we can just return it. If
1258 * we didn't find the object, then we need to create it.
1260 if (sh_obj == NULL) {
1261 /* Create new object and then insert it into hash table. */
1262 if ((sh_obj = SH_TAILQ_FIRST(&lrp->free_objs, __db_lockobj))
1264 if ((ret = __lock_grow_region(lt, DB_LOCK_OBJ, 0)) != 0)
1267 sh_obj = SH_TAILQ_FIRST(&lrp->free_objs, __db_lockobj);
1269 if ((ret = __db_shalloc(lt->mem, obj_size, 0, &p)) != 0) {
1270 if ((ret = __lock_grow_region(lt,
1271 DB_LOCK_MEM, obj_size)) != 0)
1274 /* Reacquire the head of the list. */
1275 sh_obj = SH_TAILQ_FIRST(&lrp->free_objs, __db_lockobj);
1276 (void)__db_shalloc(lt->mem, obj_size, 0, &p);
1278 sh_obj->type = type;
1279 src = type == DB_LOCK_OBJTYPE ? dbt->data : (void *)&locker;
1280 memcpy(p, src, obj_size);
1281 SH_TAILQ_REMOVE(&lrp->free_objs, sh_obj, links, __db_lockobj);
1283 SH_TAILQ_INIT(&sh_obj->waiters);
1284 if (type == DB_LOCK_LOCKER)
1285 SH_LIST_INIT(&sh_obj->heldby);
1287 SH_TAILQ_INIT(&sh_obj->holders);
1288 sh_obj->lockobj.size = obj_size;
1289 sh_obj->lockobj.off = SH_PTR_TO_OFF(&sh_obj->lockobj, p);
1291 __db_hashinsert(lt->hashtab, __db_lockobj, links, sh_obj,
1292 lrp->table_size, __lock_lhash);
1294 if (type == DB_LOCK_LOCKER)
1303 * Any lock on the waitlist has a process waiting for it. Therefore, we
1304 * can't return the lock to the freelist immediately. Instead, we can
1305 * remove the lock from the list of waiters, set the status field of the
1306 * lock, and then let the process waking up return the lock to the
1310 __lock_remove_waiter(lt, sh_obj, lockp, status)
1313 struct __db_lock *lockp;
1316 SH_TAILQ_REMOVE(&sh_obj->waiters, lockp, links, __db_lock);
1317 lockp->status = status;
1319 /* Wake whoever is waiting on this lock. */
1320 (void)__db_mutex_unlock(&lockp->mutex, lt->fd);
1324 __lock_freeobj(lt, obj)
1328 __db_hashremove_el(lt->hashtab, __db_lockobj, links,
1329 obj, lt->region->table_size, __lock_lhash);
1330 __db_shalloc_free(lt->mem, SH_DBT_PTR(&obj->lockobj));
1331 SH_TAILQ_INSERT_HEAD(<->region->free_objs, obj, links, __db_lockobj);
1335 __lock_checklocker(lt, lockp, do_remove)
1337 struct __db_lock *lockp;
1340 DB_LOCKOBJ *sh_locker;
1343 SH_LIST_REMOVE(lockp, locker_links, __db_lock);
1345 /* if the locker list is NULL, free up the object. */
1346 if (__lock_getobj(lt, lockp->holder, NULL, DB_LOCK_LOCKER, &sh_locker)
1347 == 0 && SH_LIST_FIRST(&sh_locker->heldby, __db_lock) == NULL) {
1348 __lock_freeobj(lt, sh_locker);
1349 lt->region->nlockers--;
1354 __lock_reset_region(lt)
1357 lt->conflicts = (u_int8_t *)lt->region + sizeof(DB_LOCKREGION);
1359 (DB_HASHTAB *)((u_int8_t *)lt->region + lt->region->hash_off);
1360 lt->mem = (void *)((u_int8_t *)lt->region + lt->region->mem_off);
1361 lt->reg_size = lt->region->hdr.size;