Date: Thu, 18 Nov 2004 14:09:00 GMT From: David Xu <davidxu@FreeBSD.org> To: Perforce Change Reviews <perforce@freebsd.org> Subject: PERFORCE change 65403 for review Message-ID: <200411181409.iAIE90Q0059242@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://perforce.freebsd.org/chv.cgi?CH=65403 Change 65403 by davidxu@davidxu_alona on 2004/11/18 14:07:59 1.Change hash function to use golden ratio multiplication found Knuth book. The prime is specically selected which can be optimized by gcc. 2.Only calculate hash once in each function. Affected files ... .. //depot/projects/davidxu_ksedbg/src/sys/kern/kern_umtx.c#8 edit Differences ... ==== //depot/projects/davidxu_ksedbg/src/sys/kern/kern_umtx.c#8 (text+ko) ==== @@ -55,27 +55,26 @@ struct mtx uc_lock; /* lock for this chain. */ }; -#define UMTX_QUEUES 128 -#define UMTX_HASH(pid, umtx) \ - ((((uintptr_t)pid << 16) + (((uintptr_t)umtx >> 4) & 65535)) % UMTX_QUEUES) +#define GOLDEN_RATIO_PRIME 2654404609U +#define UMTX_QUEUES 128 +#define UMTX_SHIFTS (__WORD_BIT - 7) static struct umtxq_chain umtxq_chains[UMTX_QUEUES]; static MALLOC_DEFINE(M_UMTX, "umtx", "UMTX queue memory"); -#define UMTX_LOCK(td, umtx) \ - mtx_lock(&umtxq_chains[UMTX_HASH((td)->td_proc->p_pid, \ - (umtx))].uc_lock) -#define UMTX_UNLOCK(td, umtx) \ - mtx_unlock(&umtxq_chains[UMTX_HASH((td)->td_proc->p_pid, \ - (umtx))].uc_lock); -#define UMTX_MUTEX(td, umtx) \ - (&umtxq_chains[UMTX_HASH(td->td_proc->p_pid, umtx)].uc_lock) +#define UMTX_LOCK(chain) \ + mtx_lock(&umtxq_chains[chain].uc_lock) +#define UMTX_UNLOCK(chain) \ + mtx_unlock(&umtxq_chains[chain].uc_lock) +#define UMTX_MUTEX(chain) \ + (&umtxq_chains[chain].uc_lock) #define UMTX_CONTESTED LONG_MIN static void umtx_queues_init(void *); -static struct umtx_q *umtx_lookup(struct thread *, struct umtx *umtx); -static struct umtx_q *umtx_insert(struct thread *, struct umtx *umtx); +static int umtx_hash(unsigned, void *); +static struct umtx_q *umtx_lookup(struct thread *, struct umtx *, int); +static struct umtx_q *umtx_insert(struct thread *, struct umtx *, int); SYSINIT(umtx, SI_SUB_LOCK, SI_ORDER_MIDDLE, umtx_queues_init, NULL); @@ -91,18 +90,26 @@ } } +static inline int +umtx_hash(unsigned pid, void *umtx) +{ + unsigned n = (unsigned)umtx + pid; + + return (n * GOLDEN_RATIO_PRIME) >> UMTX_SHIFTS; +} + static struct umtx_q * -umtx_lookup(struct thread *td, struct umtx *umtx) +umtx_lookup(struct thread *td, struct umtx *umtx, int chain) { struct umtx_head *head; struct umtx_q *uq; pid_t pid; - mtx_assert(UMTXQ_MUTEX(td, umtx), MA_OWNED); + mtx_assert(UMTXQ_MUTEX(chain), MA_OWNED); pid = td->td_proc->p_pid; - head = &umtxq_chains[UMTX_HASH(td->td_proc->p_pid, umtx)].uc_queues; + head = &umtxq_chains[chain].uc_queues; LIST_FOREACH(uq, head, uq_next) { if (uq->uq_pid == pid && uq->uq_umtx == umtx) @@ -116,7 +123,7 @@ * Insert a thread onto the umtx queue. */ static struct umtx_q * -umtx_insert(struct thread *td, struct umtx *umtx) +umtx_insert(struct thread *td, struct umtx *umtx, int chain) { struct umtx_head *head; struct umtx_q *uq; @@ -124,19 +131,19 @@ pid = td->td_proc->p_pid; - if ((uq = umtx_lookup(td, umtx)) == NULL) { + if ((uq = umtx_lookup(td, umtx, chain)) == NULL) { struct umtx_q *ins; - UMTX_UNLOCK(td, umtx); + UMTX_UNLOCK(chain); ins = malloc(sizeof(*uq), M_UMTX, M_ZERO | M_WAITOK); - UMTX_LOCK(td, umtx); + UMTX_LOCK(chain); /* * Some one else could have succeeded while we were blocked * waiting on memory. */ - if ((uq = umtx_lookup(td, umtx)) == NULL) { - head = &umtxq_chains[UMTX_HASH(pid, umtx)].uc_queues; + if ((uq = umtx_lookup(td, umtx, chain)) == NULL) { + head = &umtxq_chains[chain].uc_queues; uq = ins; uq->uq_pid = pid; uq->uq_umtx = umtx; @@ -155,14 +162,17 @@ } static void -umtx_remove(struct umtx_q *uq, struct thread *td) +umtx_remove(struct umtx_q *uq, struct thread *td, struct umtx *umtx, + int chain) { TAILQ_REMOVE(&uq->uq_tdq, td, td_umtx); if (TAILQ_EMPTY(&uq->uq_tdq)) { LIST_REMOVE(uq, uq_next); + UMTX_UNLOCK(chain); free(uq, M_UMTX); - } + } else + UMTX_UNLOCK(chain); } int @@ -173,6 +183,7 @@ struct umtx *umtx; intptr_t owner; intptr_t old; + int chain; int error = 0; uq = NULL; @@ -182,6 +193,7 @@ * can fault on any access. */ umtx = uap->umtx; + chain = umtx_hash(td->td_proc->p_pid, umtx); for (;;) { /* @@ -221,9 +233,9 @@ if (error) return (error); - UMTX_LOCK(td, umtx); - uq = umtx_insert(td, umtx); - UMTX_UNLOCK(td, umtx); + UMTX_LOCK(chain); + uq = umtx_insert(td, umtx, chain); + UMTX_UNLOCK(chain); /* * Set the contested bit so that a release in user space @@ -236,9 +248,8 @@ /* The address was invalid. */ if (old == -1) { - UMTX_LOCK(td, umtx); - umtx_remove(uq, td); - UMTX_UNLOCK(td, umtx); + UMTX_LOCK(chain); + umtx_remove(uq, td, umtx, chain); return (EFAULT); } @@ -247,14 +258,13 @@ * and we need to retry or we lost a race to the thread * unlocking the umtx. */ - UMTX_LOCK(td, umtx); + UMTX_LOCK(chain); if (old == owner && (td->td_flags & TDF_UMTXWAKEUP) == 0) - error = msleep(td, UMTX_MUTEX(td, umtx), + error = msleep(td, UMTX_MUTEX(chain), td->td_priority | PCATCH, "umtx", 0); else error = 0; - umtx_remove(uq, td); - UMTX_UNLOCK(td, umtx); + umtx_remove(uq, td, umtx, chain); if (td->td_flags & TDF_UMTXWAKEUP) { /* @@ -285,6 +295,7 @@ struct thread *blocked, *blocked2; struct umtx *umtx; struct umtx_q *uq; + int chain; intptr_t owner; intptr_t old; @@ -316,6 +327,9 @@ return (EFAULT); if (old != owner) return (EINVAL); + + chain = umtx_hash(td->td_proc->p_pid, umtx); + /* * At the point, a new thread can lock the umtx before we * reach here, so contested bit will not be set, if there @@ -323,10 +337,10 @@ * contensted bit for them. */ blocked = NULL; - UMTX_LOCK(td, umtx); - uq = umtx_lookup(td, umtx); + UMTX_LOCK(chain); + uq = umtx_lookup(td, umtx, chain); if (uq == NULL) { - UMTX_UNLOCK(td, umtx); + UMTX_UNLOCK(chain); return (0); } blocked2 = NULL; @@ -336,7 +350,7 @@ mtx_unlock_spin(&sched_lock); blocked2 = TAILQ_NEXT(blocked, td_umtx); } - UMTX_UNLOCK(td, umtx); + UMTX_UNLOCK(chain); /* * If there is second thread waiting on umtx, set contested bit,
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200411181409.iAIE90Q0059242>