MPC TLB shootdowns
authorBarret Rhoden <brho@cs.berkeley.edu>
Fri, 30 Apr 2010 03:53:56 +0000 (20:53 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:35:46 +0000 (17:35 -0700)
This should work for now, though it doesn't actually check that other
cores receive the message before returning (which is a slight race).
See the discussion in the documentation for more details.  Could add a
checklist to be safe (though don't put in a barrier, unless you don't
include the caller, which is a minor pain).

Documentation/process-internals.txt
kern/include/process.h
kern/src/mm.c
kern/src/process.c

index c70ee55..3ef4e58 100644 (file)
@@ -13,7 +13,8 @@ Contents:
 4. Preemption and Notification Issues
 5. Current_tf
 6. Locking!
-7. TBD
+7. TLB Coherency
+8. TBD
 
 1. Reference Counting
 ===========================
@@ -739,5 +740,121 @@ answer is that the actual work of running the scheduler should be a routine
 kmsg, similar to how Linux sets a bit in the kernel that it checks on the way
 out to see if it should run the scheduler or not.
 
-7. TBD
+7. TLB Coherency
+===========================
+When changing or removing memory mappings, we need to do some form of a TLB
+shootdown.  Normally, this will require sending an IPI (immediate kmsg) to
+every vcore of a process to unmap the affected page.  Before allocating that
+page back out, we need to make sure that every TLB has been flushed.  
+
+One reason to use a kmsg over a simple handler is that we often want to pass a
+virtual address to flush for those architectures (like x86) that can
+invalidate a specific page.  Ideally, we'd use a broadcast kmsg (doesn't exist
+yet), though we already have simple broadcast IPIs.
+
+7.1 Initial Stuff
+---------------------------
+One big issue is whether or not to wait for a response from the other vcores
+that they have unmapped.  There are two concerns: 1) Page reuse and 2) User
+semantics.  We cannot give out the physical page while it may still be in a
+TLB (even to the same process.  Ask us about the pthread_test bug).
+
+The second case is a little more detailed.  The application may not like it if
+it thinks a page is unmapped or protected, and it does not generate a fault.
+I am less concerned about this, especially since we know that even if we don't
+wait to hear from every vcore, we know that the message was delivered and the
+IPI sent.  Any cores that are in userspace will have trapped and eventually
+handle the shootdown before having a chance to execute other user code.  The
+delays in the shootdown response are due to being in the kernel with
+interrupts disabled (it was an IMMEDIATE kmsg).
+
+7.2 RCU
+---------------------------
+One approach is similar to RCU.  Unmap the page, but don't put it on the free
+list.  Instead, don't reallocate it until we are sure every core (possibly
+just affected cores) had a chance to run its kmsg handlers.  This time is
+similar to the RCU grace periods.  Once the period is over, we can then truly
+free the page.
+
+This would require some sort of RCU-like mechanism and probably a per-core
+variable that has the timestamp of the last quiescent period.  Code caring
+about when this page (or pages) can be freed would have to check on all of the
+cores (probably in a bitmask for what needs to be freed).  It would make sense
+to amortize this over several RCU-like operations.
+
+7.3 Checklist
+---------------------------
+It might not suck that much to wait for a response if you already sent an IPI,
+though it incurs some more cache misses.  If you wanted to ensure all vcores
+ran the shootdown handler, you'd have them all toggle their bit in a checklist
+(unused for a while, check smp.c).  The only one who waits would be the
+caller, but there still are a bunch of cache misses in the handlers.  Maybe
+this isn't that big of a deal, and the RCU thing is an unnecessary
+optimization.
+
+7.4 Just Wait til a Context Switch
+---------------------------
+Another option is to not bother freeing the page until the entire process is
+descheduled.  This could be a very long time, and also will mess with
+userspace's semantics.  They would be running user code that could still
+access the old page, so in essence this is a lazy munmap/mprotect.  The
+process basically has the page in pergatory: it can't be reallocated, and it
+might be accessible, but can't be guaranteed to work.
+
+The main benefit of this is that you don't need to send the TLB shootdown IPI
+at all - so you don't interfere with the app.  Though in return, they have
+possibly weird semantics.  One aspect of these weird semantics is that the
+same virtual address could map to two different pages - that seems like a
+disaster waiting to happen.  We could also block that range of the virtual
+address space from being reallocated, but that gets even more tricky.
+
+One issue with just waiting and RCU is memory pressure.  If we actually need
+the page, we will need to enforce an unmapping, which sucks a little.
+
+7.5 Bulk vs Single
+---------------------------
+If there are a lot of pages being shot down, it'd be best to amortize the cost
+of the kernel messages, as well as the invlpg calls (single page shootdowns).
+One option would be for the kmsg to take a range, and not just a single
+address.  This would help with bulk munmap/mprotects.  Based on the number of
+these, perhaps a raw tlbflush (the entire TLB) would be worth while, instead
+of n single shots.  Odds are, that number is arch and possibly workload
+specific.
+
+For now, the plan will be to send a range and have them individually shot
+down.
+
+7.6 Don't do it
+---------------------------
+Either way, munmap/mprotect sucks in an MCP.  I recommend not doing it, and
+doing the appropriate mmap/munmap/mprotects in _S mode.  Unfortunately, even
+our crap pthread library munmaps on demand as threads are created and
+destroyed.  The vcore code probably does in the bowels of glibc's TLS code
+too, though at least that isn't on every user context switch.
+
+7.7 Local memory
+---------------------------
+Private local memory would help with this too.  If each vcore has its own
+range, we won't need to send TLB shootdowns for those areas, and we won't have
+to worry about weird application semantics.  The downside is we would need to
+do these mmaps in certain ranges in advance, and might not easily be able to
+do them remotely.  More on this when we actually design and build it.
+
+7.8 Future Hardware Support
+---------------------------
+It would be cool and interesting if we had the ability to remotely shootdown
+TLBs.  For instance, all cores with cr3 == X, shootdown range Y..Z.  It's
+basically what we'll do with the kernel message and the vcoremap, but with
+magic hardware.
+
+7.9 Current Status
+---------------------------
+For now, we just send a kernel message to all vcores to do a full TLB flush,
+and not to worry about checklists, waiting, or anything.  This is due to being
+short on time and not wanting to sort out the issue with ranges.  The way
+it'll get changed to is to send the kmsg with the range to the appropriate
+cores, and then maybe put the page on the end of the freelist (instead of the
+head).  More to come.
+
+8. TBD
 ===========================
index 141ed95..e8e0b85 100644 (file)
@@ -140,9 +140,9 @@ void proc_decref(struct proc *SAFE p, size_t count);
 #define current per_cpu_info[core_id()].cur_proc
 #define set_current_proc(p) per_cpu_info[core_id()].cur_proc = (p)
 
-/* Allows the kernel to figure out what *user* tf is on this core's stack.  Can be used
- * just like a pointer to a struct Trapframe.  Need these to be macros due to
- * some circular dependencies with smp.h.  This is done here instead of
+/* Allows the kernel to figure out what *user* tf is on this core's stack.  Can
+ * be used just like a pointer to a struct Trapframe.  Need these to be macros
+ * due to some circular dependencies with smp.h.  This is done here instead of
  * elsewhere (like trap.h) for other elliptical reasons.  Note the distinction
  * between kernel and user contexts.  The kernel always returns to its nested,
  * interrupted contexts via iret/etc.  We don't always do that for user
@@ -151,12 +151,17 @@ void proc_decref(struct proc *SAFE p, size_t count);
 #define set_current_tf(tf) per_cpu_info[core_id()].cur_tf = (tf)
 
 void abandon_core(void);
+/* Hold the proc_lock, since it'll use the vcoremapping to send an unmapping
+ * message for the region from start to end.  */
+void __proc_tlbshootdown(struct proc *p, uintptr_t start, uintptr_t end);
 
 /* Kernel message handlers for process management */
 void __startcore(trapframe_t *tf, uint32_t srcid, void *a0, void *a1, void *a2);
 void __notify(trapframe_t *tf, uint32_t srcid, void *a0, void *a1, void *a2);
 void __preempt(trapframe_t *tf, uint32_t srcid, void *a0, void *a1, void *a2);
 void __death(trapframe_t *tf, uint32_t srcid, void *a0, void *a1, void *a2);
+void __tlbshootdown(struct trapframe *tf, uint32_t srcid, void *a0, void *a1,
+                    void *a2);
 
 /* Arch Specific */
 void proc_init_trapframe(trapframe_t *SAFE tf, uint32_t vcoreid,
index 33232eb..988f417 100644 (file)
@@ -219,8 +219,10 @@ int __mprotect(struct proc* p, void* addr, size_t len, int prot)
                }
        }
 
-       //TODO: TLB shootdown - needs to be process wide
-       tlbflush();
+       /* TODO: (TLB) make this take a sensible range.  For now, it doesn't matter
+        * since we ignore it in the process code.  Also, make sure you are holding
+        * the proc_lock when calling this. */
+       __proc_tlbshootdown(p, 0, 0xffffffff);
        return 0;
 }
 
index de20ddc..f479677 100644 (file)
@@ -1481,6 +1481,42 @@ void proc_decref(struct proc *p, size_t count)
                panic("Too many decrefs!");
 }
 
+/* Stop running whatever context is on this core, load a known-good cr3, and
+ * 'idle'.  Note this leaves no trace of what was running. This "leaves the
+ * process's context. */
+void abandon_core(void)
+{
+       if (current)
+               __abandon_core();
+       smp_idle();
+}
+
+/* Will send a TLB shootdown message to every vcore in the main address space
+ * (aka, all vcores for now).  The message will take the start and end virtual
+ * addresses as well, in case we want to be more clever about how much we
+ * shootdown and batching our messages.  Should do the sanity about rounding up
+ * and down in this function too.
+ *
+ * Hold the proc_lock before calling this.
+ *
+ * Would be nice to have a broadcast kmsg at this point.  Note this may send a
+ * message to the calling core (interrupting it, possibly while holding the
+ * proc_lock).  We don't need to process routine messages since it's an
+ * immediate message. */
+void __proc_tlbshootdown(struct proc *p, uintptr_t start, uintptr_t end)
+{
+       uint32_t active_vcoreid = 0, pcoreid;
+       /* TODO: (TLB) sanity checks and rounding on the ranges */
+       for (int i = 0; i < p->procinfo->num_vcores; i++) {
+               /* find next active vcore */
+               active_vcoreid = get_busy_vcoreid(p, active_vcoreid);
+               pcoreid = p->procinfo->vcoremap[active_vcoreid].pcoreid;
+               send_kernel_message(pcoreid, __tlbshootdown, (void*)start, (void*)end,
+                                   (void*)0, KMSG_IMMEDIATE);
+               active_vcoreid++; /* for the next loop, skip the one we just used */
+       }
+}
+
 /* Kernel message handler to start a process's context on this core.  Tightly
  * coupled with proc_run().  Interrupts are disabled. */
 void __startcore(trapframe_t *tf, uint32_t srcid, void *a0, void *a1, void *a2)
@@ -1560,16 +1596,6 @@ void __notify(trapframe_t *tf, uint32_t srcid, void *a0, void *a1, void *a2)
        __proc_startcore(p, &local_tf);
 }
 
-/* Stop running whatever context is on this core, load a known-good cr3, and
- * 'idle'.  Note this leaves no trace of what was running. This "leaves the
- * process's context. */
-void abandon_core(void)
-{
-       if (current)
-               __abandon_core();
-       smp_idle();
-}
-
 void __preempt(trapframe_t *tf, uint32_t srcid, void *a0, void *a1, void *a2)
 {
        struct preempt_data *vcpd;
@@ -1620,6 +1646,15 @@ void __death(trapframe_t *tf, uint32_t srcid, void *SNT a0, void *SNT a1,
        abandon_core();
 }
 
+/* Kernel message handler, usually sent IMMEDIATE, to shoot down virtual
+ * addresses from a0 to a1. */
+void __tlbshootdown(struct trapframe *tf, uint32_t srcid, void *a0, void *a1,
+                    void *a2)
+{
+       /* TODO: (TLB) something more intelligent with the range */
+       tlbflush();
+}
+
 void print_idlecoremap(void)
 {
        spin_lock(&idle_lock);