Adds 'hashlocks' and uses them for UCQs
authorBarret Rhoden <brho@cs.berkeley.edu>
Tue, 26 Jul 2011 21:37:47 +0000 (14:37 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:36:05 +0000 (17:36 -0700)
Hashlocks are just an array of spinlocks, and you pick your particular
lock based on some key's hash.  I'm curious to see if they are any
better than spinlocks, and at what point they are worth using.  For our
UCQ code - they probably aren't, but are rather cool.  We'd need some
serious event delivery to the same process in parallel to start
contending on the proc_lock.

kern/include/atomic.h
kern/include/env.h
kern/src/atomic.c
kern/src/process.c
kern/src/ucq.c

index 80d0877..0f1094b 100644 (file)
@@ -59,6 +59,26 @@ static inline void spin_lock_irqsave(spinlock_t *lock);
 static inline void spin_unlock_irqsave(spinlock_t *lock);
 static inline bool spin_lock_irq_enabled(spinlock_t *lock);
 
+/* Hash locks (array of spinlocks).  Most all users will want the default one,
+ * so point your pointer to one of them, though you could always kmalloc a
+ * bigger one.  In the future, they might be growable, etc, which init code may
+ * care about. */
+struct hashlock {
+       unsigned int            nr_entries;
+       struct spinlock         locks[];
+};
+#define HASHLOCK_DEFAULT_SZ 53         /* nice prime, might be a bit large */
+struct small_hashlock {
+       unsigned int            nr_entries;
+       struct spinlock         locks[HASHLOCK_DEFAULT_SZ];
+};
+
+void hashlock_init(struct hashlock *hl, unsigned int nr_entries);
+void hash_lock(struct hashlock *hl, long key);
+void hash_unlock(struct hashlock *hl, long key);
+void hash_lock_irqsave(struct hashlock *hl, long key);
+void hash_unlock_irqsave(struct hashlock *hl, long key);
+
 /* Seq locks */
 /* An example seq lock, built from the counter.  I don't particularly like this,
  * since it forces you to use a specific locking type.  */
index 45f2259..c0f43dc 100644 (file)
@@ -68,6 +68,10 @@ struct proc {
        struct namespace                        *ns;
        struct fs_struct                        fs_env;
        struct files_struct                     open_files;
+
+       /* UCQ hashlocks */
+       struct hashlock                         *ucq_hashlock;
+       struct small_hashlock           ucq_hl_noref;   /* don't reference directly */
 };
 
 /* Til we remove all Env references */
index dff950f..d7fcaf0 100644 (file)
@@ -9,6 +9,45 @@
 #include <error.h>
 #include <string.h>
 #include <assert.h>
+#include <hashtable.h>
+
+/* Inits a hashlock. */
+void hashlock_init(struct hashlock *hl, unsigned int nr_entries)
+{
+       hl->nr_entries = nr_entries;
+       /* this is the right way to do it, though memset is faster.  If we ever
+        * find that this is taking a lot of time, we can change it. */
+       for (int i = 0; i < hl->nr_entries; i++) {
+               spinlock_init(&hl->locks[i]);
+       }
+}
+
+/* Helper, gets the specific spinlock for a hl/key combo. */
+static spinlock_t *get_spinlock(struct hashlock *hl, long key)
+{
+       /* using the hashtable's generic hash function */
+       return &hl->locks[__generic_hash((void*)key) % hl->nr_entries];
+}
+
+void hash_lock(struct hashlock *hl, long key)
+{
+       spin_lock(get_spinlock(hl, key));
+}
+
+void hash_unlock(struct hashlock *hl, long key)
+{
+       spin_unlock(get_spinlock(hl, key));
+}
+
+void hash_lock_irqsave(struct hashlock *hl, long key)
+{
+       spin_lock_irqsave(get_spinlock(hl, key));
+}
+
+void hash_unlock_irqsave(struct hashlock *hl, long key)
+{
+       spin_unlock_irqsave(get_spinlock(hl, key));
+}
 
 // Must be called in a pair with waiton_checklist
 int commit_checklist_wait(checklist_t* list, checklist_mask_t* mask)
index d379285..5fe22aa 100644 (file)
@@ -326,6 +326,9 @@ error_t proc_alloc(struct proc **pp, struct proc *parent)
        p->open_files.max_fdset = NR_FILE_DESC_DEFAULT;
        p->open_files.fd = p->open_files.fd_array;
        p->open_files.open_fds = (struct fd_set*)&p->open_files.open_fds_init;
+       /* Init the ucq hash lock */
+       p->ucq_hashlock = (struct hashlock*)&p->ucq_hl_noref;
+       hashlock_init(p->ucq_hashlock, HASHLOCK_DEFAULT_SZ);
 
        atomic_inc(&num_envs);
        frontend_proc_init(p);
index fe4e4c5..3e413a3 100644 (file)
@@ -36,9 +36,9 @@ void send_ucq_msg(struct ucq *ucq, struct proc *p, struct event_msg *msg)
        if (PGOFF(my_slot) > 3000)
                warn("Abnormally high counter, there's probably something wrong!");
 grab_lock:
-       /* TODO: use a hashlock, instead of the proc lock.  think about irqsave.  do
-        * we send events from IRQ context?  The proc_lock isn't irqsave */
-       spin_lock(&p->proc_lock);
+       /* Lock, for this proc/ucq.  Using an irqsave, since we may want to send ucq
+        * messages from irq context. */
+       hash_lock_irqsave(p->ucq_hashlock, (long)ucq);
        /* Grab a potential slot (again, preventing another DoS) */
        my_slot = (uintptr_t)atomic_fetch_and_add(&ucq->prod_idx, 1);
        if (slot_is_good(my_slot))
@@ -60,11 +60,9 @@ grab_lock:
                /* Warn if we have a ridiculous amount of pages in the ucq */
                if (atomic_fetch_and_add(&ucq->nr_extra_pgs, 1) > UCQ_WARN_THRESH)
                        warn("Over %d pages in ucq %08p!\n", UCQ_WARN_THRESH, ucq);
-               /* TODO: use a proc_lock/mm_lock or call the external one.  Need to do
-                * this for now since we don't have hash locks yet HASH LOCK */
-               new_page = (struct ucq_page*)__do_mmap(p, 0, PGSIZE,
-                                                      PROT_READ | PROT_WRITE,
-                                                      MAP_ANON | MAP_POPULATE, 0, 0);
+               new_page = (struct ucq_page*)do_mmap(p, 0, PGSIZE,
+                                                    PROT_READ | PROT_WRITE,
+                                                    MAP_ANON | MAP_POPULATE, 0, 0);
                assert(new_page);
                assert(!PGOFF(new_page));
        } else {
@@ -88,7 +86,7 @@ unlock_lock:
        /* At this point, any normal (non-locking) producers can succeed in getting
         * a slot.  The ones that failed earlier will fight for the lock, then
         * quickly proceed when they get a good slot */
-       spin_unlock(&p->proc_lock);     /* TODO HASH LOCK */
+       hash_unlock_irqsave(p->ucq_hashlock, (long)ucq);
        /* Fall through to having a slot */
 have_slot:
        /* Sanity check on our slot. */
@@ -110,7 +108,7 @@ error_addr_unlock:
        /* Had a bad addr while holding the lock.  This is a bit more serious */
        warn("Bad addr in ucq page management!");
        ucq->prod_overflow = FALSE;
-       spin_unlock(&p->proc_lock);     /* TODO HASH LOCK */
+       hash_unlock_irqsave(p->ucq_hashlock, (long)ucq);
        /* Fall-through to normal error out */
 error_addr:
        warn("Invalid user address, not sending a message");