PERFORCE change 65403 for review
David Xu
davidxu at FreeBSD.org
Thu Nov 18 06:09:01 PST 2004
http://perforce.freebsd.org/chv.cgi?CH=65403
Change 65403 by davidxu at 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,
More information about the p4-projects
mailing list