bitkeeper revision 1.120 (3e6ca44cvMxdBQkw-MjBh0_JyTebvw)

hypervisor.c:
  Better synchronisation in page-table update code -- removed locking and replaced with cmpxchg (CAS)

1 files changed, 97 insertions, 79 deletions

diff --git a/xenolinux-2.4.21-pre4-sparse/arch/xeno/mm/hypervisor.c b/xenolinux-2.4.21-pre4-sparse/arch/xeno/mm/hypervisor.c
index 044c531d35..674d099d6b 100644
--- a/xenolinux-2.4.21-pre4-sparse/arch/xeno/mm/hypervisor.c
+++ b/xenolinux-2.4.21-pre4-sparse/arch/xeno/mm/hypervisor.c
@@ -13,17 +13,26 @@
 #include <asm/pgtable.h>
 
 /*
- * This suffices to protect us if we ever move to SMP domains.
- * Further, it protects us against interrupts. At the very least, this is
- * required for the network driver which flushes the update queue before
- * pushing new receive buffers.
+ * A note on atomicity of these operations. We assume that queue_xxx
+ * operations never occur in an asynchronous (eg. interrupt) context.
+ * Therefore they do not need to be synchronised w.r.t. each other.
+ * However, flush_update_queue may be called from an interrupt context
+ * (eg. this is done in the network driver).
+ * 
+ * We use lock-free techniques to synchronise on the queue index. If a
+ * queue_xxx operation finds this index changes while it runs, it will
+ * fail and retry.
+ * 
+ * Flush operations must synchronize with themselves. They do this by
+ * atomically updating the index to zero on entry. This effectively locks
+ * out any other asynchronous calls to a flush operation.
+ * 
+ * Debug routines synchronise by disabling interrupts. It's easier that way.
  */
-static spinlock_t update_lock = SPIN_LOCK_UNLOCKED;
 
 #define QUEUE_SIZE 2048
 static page_update_request_t update_queue[QUEUE_SIZE];
-unsigned int pt_update_queue_idx = 0;
-#define idx pt_update_queue_idx
+volatile unsigned int pt_update_queue_idx = 0;
 
 #if PT_UPDATE_DEBUG > 0
 page_update_debug_t update_debug_queue[QUEUE_SIZE] = {{0}};
@@ -33,7 +42,11 @@ static void DEBUG_allow_pt_reads(void)
 {
     pte_t *pte;
     page_update_request_t update;
+    unsigned int idx;
+    unsigned long flags;
     int i;
+    local_irq_save(flags);
+    idx = pt_update_queue_idx;
     for ( i = idx-1; i >= 0; i-- )
     {
         pte = update_debug_queue[i].ptep;
@@ -43,13 +56,17 @@ static void DEBUG_allow_pt_reads(void)
         update.val = update_debug_queue[i].pteval;
         HYPERVISOR_pt_update(&update, 1);
     }
+    local_irq_restore(flags);
 }
 static void DEBUG_disallow_pt_read(unsigned long pa)
 {
     pte_t *pte;
     pmd_t *pmd;
     pgd_t *pgd;
-    unsigned long pteval;
+    unsigned long pteval, flags;
+    unsigned int idx;
+    local_irq_save(flags);
+    idx = pt_update_queue_idx;
     /*
      * We may fault because of an already outstanding update.
      * That's okay -- it'll get fixed up in the fault handler.
@@ -65,6 +82,7 @@ static void DEBUG_disallow_pt_read(unsigned long pa)
     HYPERVISOR_pt_update(&update, 1);
     update_debug_queue[idx].ptep = pte;
     update_debug_queue[idx].pteval = pteval;
+    local_irq_restore(flags);
 }
 #endif
 
@@ -87,9 +105,8 @@ unsigned long pt_baseptr;
 
 void _flush_page_update_queue(void)
 {
-    unsigned long flags;
-    spin_lock_irqsave(&update_lock, flags);
-    if ( idx == 0 ) goto out;
+    unsigned int idx = xchg(&pt_update_queue_idx, 0);
+    if ( idx == 0 ) return;
 #if PT_UPDATE_DEBUG > 1
     printk("Flushing %d entries from pt update queue\n", idx);
 #endif
@@ -97,111 +114,112 @@ void _flush_page_update_queue(void)
     DEBUG_allow_pt_reads();
 #endif
     HYPERVISOR_pt_update(update_queue, idx);
-    idx = 0;
- out:
-    spin_unlock_irqrestore(&update_lock, flags);
-}
-
-static void increment_index(void)
-{
-    if ( ++idx == QUEUE_SIZE ) _flush_page_update_queue();
 }
 
 void queue_l1_entry_update(unsigned long ptr, unsigned long val)
 {
-    unsigned long flags;
-    spin_lock_irqsave(&update_lock, flags);
+    unsigned int idx;
 #if PT_UPDATE_DEBUG > 0
     DEBUG_disallow_pt_read(ptr);
 #endif
-    update_queue[idx].ptr = phys_to_machine(ptr);
-    update_queue[idx].val = val;
-    increment_index();
-    spin_unlock_irqrestore(&update_lock, flags);
+    do {
+        idx = pt_update_queue_idx;
+        update_queue[idx].ptr = phys_to_machine(ptr);
+        update_queue[idx].val = val;
+    } while ( cmpxchg(&pt_update_queue_idx, idx, idx+1) != idx );    
+    if ( idx == (QUEUE_SIZE-1) ) _flush_page_update_queue();
 }
 
 void queue_l2_entry_update(unsigned long ptr, unsigned long val)
 {
-    unsigned long flags;
-    spin_lock_irqsave(&update_lock, flags);
-    update_queue[idx].ptr = phys_to_machine(ptr);
-    update_queue[idx].val = val;
-    increment_index();
-    spin_unlock_irqrestore(&update_lock, flags);
+    unsigned int idx;
+    do {
+        idx = pt_update_queue_idx;
+        update_queue[idx].ptr = phys_to_machine(ptr);
+        update_queue[idx].val = val;
+    } while ( cmpxchg(&pt_update_queue_idx, idx, idx+1) != idx );
+    if ( idx == (QUEUE_SIZE-1) ) _flush_page_update_queue();
 }
 
 void queue_pt_switch(unsigned long ptr)
 {
-    unsigned long flags;
-    spin_lock_irqsave(&update_lock, flags);
-    update_queue[idx].ptr  = phys_to_machine(ptr);
-    update_queue[idx].ptr |= PGREQ_EXTENDED_COMMAND;
-    update_queue[idx].val  = PGEXT_NEW_BASEPTR;
-    increment_index();
-    spin_unlock_irqrestore(&update_lock, flags);
+    unsigned int idx;
+    do {
+        idx = pt_update_queue_idx;
+        update_queue[idx].ptr  = phys_to_machine(ptr);
+        update_queue[idx].ptr |= PGREQ_EXTENDED_COMMAND;
+        update_queue[idx].val  = PGEXT_NEW_BASEPTR;
+    } while ( cmpxchg(&pt_update_queue_idx, idx, idx+1) != idx );
+    if ( idx == (QUEUE_SIZE-1) ) _flush_page_update_queue();
 }
 
 void queue_tlb_flush(void)
 {
-    unsigned long flags;
-    spin_lock_irqsave(&update_lock, flags);
-    update_queue[idx].ptr  = PGREQ_EXTENDED_COMMAND;
-    update_queue[idx].val  = PGEXT_TLB_FLUSH;
-    increment_index();
-    spin_unlock_irqrestore(&update_lock, flags);
+    unsigned int idx;
+    do {
+        idx = pt_update_queue_idx;
+        update_queue[idx].ptr  = PGREQ_EXTENDED_COMMAND;
+        update_queue[idx].val  = PGEXT_TLB_FLUSH;
+    } while ( cmpxchg(&pt_update_queue_idx, idx, idx+1) != idx );
+    if ( idx == (QUEUE_SIZE-1) ) _flush_page_update_queue();
 }
 
 void queue_invlpg(unsigned long ptr)
 {
-    unsigned long flags;
-    spin_lock_irqsave(&update_lock, flags);
-    update_queue[idx].ptr  = PGREQ_EXTENDED_COMMAND;
-    update_queue[idx].val  = ptr & PAGE_MASK;
-    update_queue[idx].val |= PGEXT_INVLPG;
-    increment_index();
-    spin_unlock_irqrestore(&update_lock, flags);
+    unsigned int idx;
+    do {
+        idx = pt_update_queue_idx;
+        update_queue[idx].ptr  = PGREQ_EXTENDED_COMMAND;
+        update_queue[idx].val  = ptr & PAGE_MASK;
+        update_queue[idx].val |= PGEXT_INVLPG;
+    } while ( cmpxchg(&pt_update_queue_idx, idx, idx+1) != idx );
+    if ( idx == (QUEUE_SIZE-1) ) _flush_page_update_queue();
 }
 
 void queue_pgd_pin(unsigned long ptr)
 {
-    unsigned long flags;
-    spin_lock_irqsave(&update_lock, flags);
-    update_queue[idx].ptr  = phys_to_machine(ptr);
-    update_queue[idx].ptr |= PGREQ_EXTENDED_COMMAND;
-    update_queue[idx].val  = PGEXT_PIN_L2_TABLE;
-    increment_index();
-    spin_unlock_irqrestore(&update_lock, flags);
+    unsigned int idx;
+    do {
+        idx = pt_update_queue_idx;
+        update_queue[idx].ptr  = phys_to_machine(ptr);
+        update_queue[idx].ptr |= PGREQ_EXTENDED_COMMAND;
+        update_queue[idx].val  = PGEXT_PIN_L2_TABLE;
+    } while ( cmpxchg(&pt_update_queue_idx, idx, idx+1) != idx );
+    if ( idx == (QUEUE_SIZE-1) ) _flush_page_update_queue();
 }
 
 void queue_pgd_unpin(unsigned long ptr)
 {
-    unsigned long flags;
-    spin_lock_irqsave(&update_lock, flags);
-    update_queue[idx].ptr  = phys_to_machine(ptr);
-    update_queue[idx].ptr |= PGREQ_EXTENDED_COMMAND;
-    update_queue[idx].val  = PGEXT_UNPIN_TABLE;
-    increment_index();
-    spin_unlock_irqrestore(&update_lock, flags);
+    unsigned int idx;
+    do {
+        idx = pt_update_queue_idx;
+        update_queue[idx].ptr  = phys_to_machine(ptr);
+        update_queue[idx].ptr |= PGREQ_EXTENDED_COMMAND;
+        update_queue[idx].val  = PGEXT_UNPIN_TABLE;
+    } while ( cmpxchg(&pt_update_queue_idx, idx, idx+1) != idx );
+    if ( idx == (QUEUE_SIZE-1) ) _flush_page_update_queue();
 }
 
 void queue_pte_pin(unsigned long ptr)
 {
-    unsigned long flags;
-    spin_lock_irqsave(&update_lock, flags);
-    update_queue[idx].ptr  = phys_to_machine(ptr);
-    update_queue[idx].ptr |= PGREQ_EXTENDED_COMMAND;
-    update_queue[idx].val  = PGEXT_PIN_L1_TABLE;
-    increment_index();
-    spin_unlock_irqrestore(&update_lock, flags);
+    unsigned int idx;
+    do {
+        idx = pt_update_queue_idx;
+        update_queue[idx].ptr  = phys_to_machine(ptr);
+        update_queue[idx].ptr |= PGREQ_EXTENDED_COMMAND;
+        update_queue[idx].val  = PGEXT_PIN_L1_TABLE;
+    } while ( cmpxchg(&pt_update_queue_idx, idx, idx+1) != idx );
+    if ( idx == (QUEUE_SIZE-1) ) _flush_page_update_queue();
 }
 
 void queue_pte_unpin(unsigned long ptr)
 {
-    unsigned long flags;
-    spin_lock_irqsave(&update_lock, flags);
-    update_queue[idx].ptr  = phys_to_machine(ptr);
-    update_queue[idx].ptr |= PGREQ_EXTENDED_COMMAND;
-    update_queue[idx].val  = PGEXT_UNPIN_TABLE;
-    increment_index();
-    spin_unlock_irqrestore(&update_lock, flags);
+    unsigned int idx;
+    do {
+        idx = pt_update_queue_idx;
+        update_queue[idx].ptr  = phys_to_machine(ptr);
+        update_queue[idx].ptr |= PGREQ_EXTENDED_COMMAND;
+        update_queue[idx].val  = PGEXT_UNPIN_TABLE;
+    } while ( cmpxchg(&pt_update_queue_idx, idx, idx+1) != idx );
+    if ( idx == (QUEUE_SIZE-1) ) _flush_page_update_queue();
 }