From owner-p4-projects@FreeBSD.ORG Thu Nov 18 14:09:01 2004 Return-Path: Delivered-To: p4-projects@freebsd.org Received: by hub.freebsd.org (Postfix, from userid 32767) id D9F5B16A4D1; Thu, 18 Nov 2004 14:09:00 +0000 (GMT) Delivered-To: perforce@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 9C98016A4CE for ; Thu, 18 Nov 2004 14:09:00 +0000 (GMT) Received: from repoman.freebsd.org (repoman.freebsd.org [216.136.204.115]) by mx1.FreeBSD.org (Postfix) with ESMTP id 7BFB543D31 for ; Thu, 18 Nov 2004 14:09:00 +0000 (GMT) (envelope-from davidxu@freebsd.org) Received: from repoman.freebsd.org (localhost [127.0.0.1]) by repoman.freebsd.org (8.12.11/8.12.11) with ESMTP id iAIE90Jp059247 for ; Thu, 18 Nov 2004 14:09:00 GMT (envelope-from davidxu@freebsd.org) Received: (from perforce@localhost) by repoman.freebsd.org (8.12.11/8.12.11/Submit) id iAIE90Q0059242 for perforce@freebsd.org; Thu, 18 Nov 2004 14:09:00 GMT (envelope-from davidxu@freebsd.org) Date: Thu, 18 Nov 2004 14:09:00 GMT Message-Id: <200411181409.iAIE90Q0059242@repoman.freebsd.org> X-Authentication-Warning: repoman.freebsd.org: perforce set sender to davidxu@freebsd.org using -f From: David Xu To: Perforce Change Reviews Subject: PERFORCE change 65403 for review X-BeenThere: p4-projects@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: p4 projects tree changes List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 18 Nov 2004 14:09:01 -0000 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,