Checklists
authorBarret Rhoden <brho@cs.berkeley.edu>
Fri, 17 Apr 2009 23:09:58 +0000 (16:09 -0700)
committerBarret Rhoden <brho@cs.berkeley.edu>
Fri, 17 Apr 2009 23:09:58 +0000 (16:09 -0700)
Implemented and passes some tests.  Some more BIT macros and atomic ops.

inc/types.h
kern/atomic.c
kern/atomic.h
kern/testing.c
kern/testing.h

index 684b00c..55ca187 100644 (file)
@@ -73,22 +73,45 @@ typedef int32_t off_t;
 // a uint64_t programatically
 #define UINT64(upper, lower) ( (((uint64_t)(upper)) << 32) | (lower) )
 
-#define BYTES_FOR_BITMASK(size) ((size) ? ((size) - 1) / 8 + 1 : 0)
-
-//#define DECL_BITMASK(name, size) (uint8_t COUNT(BYTES_FOR_BITMASK((size)))
-#define DECL_BITMASK(name, size) uint8_t \
-       (name)[BYTES_FOR_BITMASK((size))]
-
-#define CLR_BITMASK(name, size) (memset((name), 0, BYTES_FOR_BITMASK((size))))
-
-#define GET_BITMASK_BIT(name, bit) (((name)[(bit)/8] & (1 << ((bit) % 8))) ?1:0)
+/*********************** Bitmask stuff **********************/
+#define BYTES_FOR_BITMASK(size) (((size) - 1) / 8 + 1)
+#define BYTES_FOR_BITMASK_WITH_CHECK(size) ((size) ? ((size) - (1)) / (8) + (1) : (0))
+#define DECL_BITMASK(name, size) uint8_t (name)[BYTES_FOR_BITMASK((size))]
 
+#define GET_BITMASK_BIT(name, bit) (((name)[(bit)/8] & (1 << ((bit) % 8))) ? 1 : 0)
+// TODO - Need to do these atomically, or provide alternatives
 #define SET_BITMASK_BIT(name, bit) ((name)[(bit)/8] |= (1 << ((bit) % 8)))
-
 #define CLR_BITMASK_BIT(name, bit) ((name)[(bit)/8] &= ~(1 << ((bit) % 8)))
+#define CLR_BITMASK_BIT_ATOMIC(name, bit) (atomic_andb(&(name)[(bit)/8], ~(1 << ((bit) % 8))))
 
-
-
-
+#define CLR_BITMASK(name, size) (memset((name), 0, BYTES_FOR_BITMASK((size))))
+#define FILL_BITMASK(name, size) ({ \
+       memset((name), 255, BYTES_FOR_BITMASK((size))); \
+       (name)[BYTES_FOR_BITMASK((size))-1] >>= (((size) % 8) ? (8 - ((size) % 8)) : 0 );}) 
+
+#define COPY_BITMASK(newmask, oldmask, size) (memcpy((newmask), (oldmask), BYTES_FOR_BITMASK((size))))
+
+// this checks the entire last byte, so keep it 0 in the other macros
+#define BITMASK_IS_CLEAR(name, size) ({ \
+       uint32_t __n = BYTES_FOR_BITMASK((size)); \
+       bool clear = 1; \
+       while (__n-- > 0) { \
+               if ((name)[__n]) { \
+                       clear = 0; \
+                       break;\
+               }\
+       } \
+       clear; })
+
+#define PRINT_MASK(name, size) { \
+       int i;  \
+       for (i = 0; i < BYTES_FOR_BITMASK(size); i++) { \
+               int j;  \
+               for (j = 0; j < 8; j++) \
+                       printk("%x", ((name)[i] >> j) & 1);     \
+       } \
+       printk("\n"); \
+}
+/**************************************************************/
 
 #endif /* !JOS_INC_TYPES_H */
index c376380..9e2dd43 100644 (file)
@@ -1,6 +1,74 @@
+#include <inc/string.h>
+#include <inc/assert.h>
+
 #include <kern/atomic.h>
 #include <kern/apic.h>
 
+// Must be called in a pair with waiton_checklist
+int commit_checklist_wait(checklist_t* list, checklist_mask_t* mask)
+{
+       assert(list->mask.size == mask->size);
+       // possession of this lock means you can wait on it and set it
+       spin_lock_irqsave(&list->lock);
+       // wait til the list is available.  could have some adaptive thing here
+       // where it fails after X tries (like 500), gives up the lock, and returns
+       // an error code
+       while (!(BITMASK_IS_CLEAR(list->mask.bits, list->mask.size)))
+               cpu_relax();
+
+       // list is ours and clear, set it to the settings of our list
+       COPY_BITMASK(list->mask.bits, mask->bits, mask->size); 
+       return 0;
+}
+
+int commit_checklist_nowait(checklist_t* list, checklist_mask_t* mask)
+{
+       int e = 0;
+       if (e = commit_checklist_wait(list, mask))
+               return e;
+       // give up the lock, since we won't wait for completion
+       spin_unlock_irqsave(&list->lock);
+       return e;
+}
+// The deal with the lock:
+// what if two different actors are waiting on the list, but for different reasons?
+// part of the problem is we are doing both set and check via the same path
+//
+// aside: we made this a lot more difficult than the usual barriers or even 
+// the RCU grace-period checkers, since we have to worry about this construct
+// being used by others before we are done with it.
+//
+// how about this: if we want to wait on this later, we just don't release the
+// lock.  if we release it, then we don't care who comes in and grabs and starts
+// checking the list.  
+//     - regardless, there are going to be issues with people looking for a free 
+//     item.  even if they grab the lock, they may end up waiting a while and 
+//     wantint to bail (like test for a while, give up, move on, etc).  
+//     - still limited in that only the setter can check, and only one person
+//     can spinwait / check for completion.  if someone else tries to wait (wanting
+//     completion), they may miss it if someone else comes in and grabs the lock
+//     to use it for a new checklist
+//             - if we had the ability to sleep and get woken up, we could have a 
+//             queue.  actually, we could do a queue anyway, but they all spin
+//             and it's the bosses responsibility to *wake* them
+
+// Must be called after commit_checklist
+// Assumed we held the lock if we ever call this
+int waiton_checklist(checklist_t* list)
+{
+       // can consider breakout out early, like above, and erroring out
+       while (!(BITMASK_IS_CLEAR(list->mask.bits, list->mask.size)))
+               cpu_relax();
+       spin_unlock_irqsave(&list->lock);
+       return 0;
+}
+
+// CPU mask specific - this is how cores report in
+void down_checklist(checklist_t* list)
+{
+       CLR_BITMASK_BIT_ATOMIC(list->mask.bits, lapic_get_id());
+}
+
 // byte per cpu, as mentioned below
 void init_barrier_all(barrier_t* cpu_barrier)
 {
index 5ec0206..32a297e 100644 (file)
@@ -19,8 +19,38 @@ static inline void spin_lock_irqsave(volatile uint32_t* lock);
 static inline void spin_unlock_irqsave(volatile uint32_t* lock);
 static inline void atomic_inc(volatile uint32_t* number);
 static inline void atomic_dec(volatile uint32_t* number);
+static inline void atomic_andb(volatile uint8_t* number, uint8_t mask);
 
+/*********************** Checklist stuff **********************/
+typedef struct checklist_mask {
+       // only need an uint8_t, but we need the bits[] to be word aligned
+       uint32_t size;
+       volatile uint8_t (COUNT(BYTES_FOR_BITMASK(size)) bits)[];
+} checklist_mask_t;
 
+// mask contains an unspecified array, so it need to be at the bottom
+typedef struct checklist {
+       volatile uint32_t lock;
+       checklist_mask_t mask;
+} checklist_t;
+
+#define BUILD_ZEROS_ARRAY_255  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} 
+#define ZEROS_ARRAY(size)      \
+       BUILD_ZEROS_ARRAY_##size
+
+#define INIT_CHECKLIST(nm, sz) \
+       checklist_t nm = {0, {(sz), ZEROS_ARRAY(sz)}};
+#define INIT_CHECKLIST_MASK(nm, sz)    \
+       checklist_mask_t nm = {(sz), ZEROS_ARRAY(sz)};
+
+int commit_checklist_wait(checklist_t* list, checklist_mask_t* mask);
+int commit_checklist_nowait(checklist_t* list, checklist_mask_t* mask);
+int waiton_checklist(checklist_t* list);
+void down_checklist(checklist_t* list);
+// TODO - want a destroy checklist (when we have kmalloc, or whatever)
+/**************************************************************/
+
+/* Barrier: currently made for everyone barriering.  Change to use checklist */
 typedef struct barrier {
        volatile uint8_t COUNT(MAX_NUM_CPUS) cpu_array[MAX_NUM_CPUS]; 
     volatile uint8_t ready;
@@ -29,6 +59,7 @@ typedef struct barrier {
 void init_barrier_all(barrier_t* cpu_barrier);
 void barrier_all(barrier_t* cpu_barrier);
 
+/* Inlined functions declared above */
 static inline void spin_lock(volatile uint32_t* lock)
 {
        asm volatile(
@@ -82,4 +113,9 @@ static inline void atomic_dec(volatile uint32_t* number)
 {
        asm volatile("lock decl %0" : "=m"(*number) : : "cc");
 }
+
+static inline void atomic_andb(volatile uint8_t* number, uint8_t mask)
+{
+       asm volatile("lock andb %1,%0" : "=m"(*number) : "r"(mask) : "cc");
+}
 #endif /* !ROS_INC_ATOMIC_H */
index 537bf25..a2e9d8c 100644 (file)
@@ -201,34 +201,78 @@ void test_interrupts_irqsave(void)
 
 void test_bitmasks(void)
 {
-#define print_mask() { \
-       for (int i = 0; i < BYTES_FOR_BITMASK(258); i++) \
-               for (int j = 0; j < 8; j++) \
-                       printk("%x", (mask[i] >> j) & 1); \
-       printk("\n"); \
-} 
-
-       DECL_BITMASK(mask, 258);
+#define masksize 67
+       DECL_BITMASK(mask, masksize);
        printk("size of mask %d\n", sizeof(mask));
-       CLR_BITMASK(mask, 258);
-       print_mask();
+       CLR_BITMASK(mask, masksize);
+       PRINT_MASK(mask, masksize);
        printk("cleared\n");
        SET_BITMASK_BIT(mask, 0);
        SET_BITMASK_BIT(mask, 11);
        SET_BITMASK_BIT(mask, 17);
-       SET_BITMASK_BIT(mask, 257);
+       SET_BITMASK_BIT(mask, masksize-1);
        printk("bits set\n");
-       print_mask();
+       PRINT_MASK(mask, masksize);
+       DECL_BITMASK(mask2, masksize);
+       COPY_BITMASK(mask2, mask, masksize);
+       printk("copy of original mask, should be the same as the prev\n");
+       PRINT_MASK(mask2, masksize);
        CLR_BITMASK_BIT(mask, 11);
        printk("11 cleared\n");
-       print_mask();
+       PRINT_MASK(mask, masksize);
        printk("bit 17 is %d (should be 1)\n", GET_BITMASK_BIT(mask, 17));
        printk("bit 11 is %d (should be 0)\n", GET_BITMASK_BIT(mask, 11));
-       CLR_BITMASK(mask, 258);
-       print_mask();
+       FILL_BITMASK(mask, masksize);
+       PRINT_MASK(mask, masksize);
+       printk("should be all 1's, except for a few at the end\n");
+       printk("Is Clear?: %d (should be 0)\n", BITMASK_IS_CLEAR(mask,masksize));
+       CLR_BITMASK(mask, masksize);
+       PRINT_MASK(mask, masksize);
+       printk("Is Clear?: %d (should be 1)\n", BITMASK_IS_CLEAR(mask,masksize));
        printk("should be cleared\n");
 }
 
+checklist_t* the_global_list;
+
+void test_checklist_handler(struct Trapframe *tf)
+{
+       for (int i = 0; i < SMP_BOOT_TIMEOUT; i++);
+       for (int i = 0; i < SMP_BOOT_TIMEOUT; i++);
+       down_checklist(the_global_list);
+}
+
+extern uint8_t num_cpus;
+
+void test_checklists(void)
+{
+       INIT_CHECKLIST(a_list, MAX_NUM_CPUS);
+       the_global_list = &a_list;
+       printk("Checklist built, mask\n");
+       PRINT_MASK(a_list.mask.bits, a_list.mask.size);
+       SET_BITMASK_BIT(a_list.mask.bits, 11);
+       printk("Set bit 11\n");
+       PRINT_MASK(a_list.mask.bits, a_list.mask.size);
+
+       CLR_BITMASK(a_list.mask.bits, a_list.mask.size);
+       INIT_CHECKLIST_MASK(a_mask, MAX_NUM_CPUS);
+       FILL_BITMASK(a_mask.bits, num_cpus);
+       //CLR_BITMASK_BIT(a_mask.bits, lapic_get_id());
+       //SET_BITMASK_BIT(a_mask.bits, 1);
+       //printk("New mask (1, 17, 25):\n");
+       PRINT_MASK(a_mask.bits, a_mask.size);
+       printk("committing new mask\n");
+       commit_checklist_wait(&a_list, &a_mask);
+       printk("Old mask (copied onto) (1, 17, 25):\n");
+       PRINT_MASK(a_list.mask.bits, a_list.mask.size);
+       //smp_call_function_single(1, test_checklist_handler, 0);       
+       smp_call_function_all(test_checklist_handler, 0);       
+
+       printk("Waiting on checklist\n");
+       waiton_checklist(&a_list);      
+       printk("Done Waiting!\n");
+
+}
+
 /* Helper Functions */
 
 void test_hello_world_handler(struct Trapframe *tf)
index de2852b..443fd39 100644 (file)
@@ -16,6 +16,7 @@ void test_print_info(void);
 void test_barrier(void);
 void test_interrupts_irqsave(void);
 void test_bitmasks(void);
+void test_checklists(void);
 
 void test_hello_world_handler(struct Trapframe *tf);
 void test_print_info_handler(struct Trapframe *tf);