Changeset 896ad9f in mainline

Timestamp:

2009-01-31T13:12:14Z (16 years ago)

Author:

Martin Decky <martin@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

53634f9

Parents:

7c98874

Message:

use pseudorandom generator to avoid even the longest path of livelock collisions

Location:

kernel/arch/ppc32

Files:

• include/mm/tlb.h (modified) (1 diff)
• src/exception.S (modified) (3 diffs)
• src/mm/tlb.c (modified) (7 diffs)

kernel/arch/ppc32/include/mm/tlb.h

@@ -60 +60 @@
 
 extern void pht_refill(int n, istate_t *istate);
-extern bool pht_real_refill(int n, istate_t *istate) __attribute__ ((section("K_UNMAPPED_TEXT_START")));
+extern bool pht_refill_real(int n, istate_t *istate) __attribute__ ((section("K_UNMAPPED_TEXT_START")));
 extern void pht_init(void);
 

kernel/arch/ppc32/src/exception.S

@@ -226 +226 @@
         mr r4, sp
         addi r4, r4, 8
-        bl pht_real_refill
+        bl pht_refill_real
         
         cmpwi r3, 0
@@ -238 +238 @@
         mr r4, sp
         addi r4, r4, 8
-        bl pht_real_refill
+        bl pht_refill_real
         
         cmpwi r3, 0
@@ -282 +282 @@
 
 iret_real:
-        
         lwz r0, 8(sp)
         lwz r2, 12(sp)

kernel/arch/ppc32/src/mm/tlb.c

@@ -41 +41 @@
 #include <print.h>
 #include <symtab.h>
+
+
+static unsigned int seed = 10;
+static unsigned int seed_real __attribute__ ((section("K_UNMAPPED_DATA_START"))) = 42;
 
 
@@ -126 +130 @@
 
 
+/** Pseudorandom generator
+ *
+ * A pretty standard linear congruential pseudorandom
+ * number generator (m = 2^32).
+ *
+ */
+#define RANDI(seed) \
+        ({ \
+                (seed) = 1103515245 * (seed) + 12345; \
+                (seed); \
+        })
+
+
 static void pht_insert(const uintptr_t vaddr, const pte_t *pte)
 {
@@ -181 +198 @@
                 
                 if (!found)
-                        i = page % 8;
-        }
-        
-        
+                        i = RANDI(seed) % 8;
+        }
         
         phte[base + i].v = 1;
@@ -195 +210 @@
         phte[base + i].wimg = (pte->page_cache_disable ? WIMG_NO_CACHE : 0);
         phte[base + i].pp = 2; // FIXME
-}
-
-
-static void pht_real_insert(const uintptr_t vaddr, const pfn_t pfn)
-{
-        uint32_t page = (vaddr >> 12) & 0xffff;
-        uint32_t api = (vaddr >> 22) & 0x3f;
-        
-        uint32_t vsid;
-        asm volatile (
-                "mfsrin %0, %1\n"
-                : "=r" (vsid)
-                : "r" (vaddr)
-        );
-        
-        uint32_t sdr1;
-        asm volatile (
-                "mfsdr1 %0\n"
-                : "=r" (sdr1)
-        );
-        phte_t *phte_physical = (phte_t *) (sdr1 & 0xffff0000);
-        
-        /* Primary hash (xor) */
-        uint32_t h = 0;
-        uint32_t hash = vsid ^ page;
-        uint32_t base = (hash & 0x3ff) << 3;
-        uint32_t i;
-        bool found = false;
-        
-        /* Find unused or colliding PTE in PTEG */
-        for (i = 0; i < 8; i++) {
-                if ((!phte_physical[base + i].v) ||
-                    ((phte_physical[base + i].vsid == vsid)
-                    && (phte_physical[base + i].api == api)
-                    && (phte_physical[base + i].h == 0))) {
-                        found = true;
-                        break;
-                }
-        }
-        
-        if (!found) {
-                /* Secondary hash (not) */
-                uint32_t base2 = (~hash & 0x3ff) << 3;
-                
-                /* Find unused or colliding PTE in PTEG */
-                for (i = 0; i < 8; i++) {
-                        if ((!phte_physical[base2 + i].v) ||
-                            ((phte_physical[base2 + i].vsid == vsid)
-                            && (phte_physical[base2 + i].api == api)
-                            && (phte_physical[base2 + i].h == 1))) {
-                                found = true;
-                                base = base2;
-                                h = 1;
-                                break;
-                        }
-                }
-                
-                if (!found) {
-                        i = page % 8;
-                        base = base2;
-                        h = 1;
-                }
-        }
-        
-        phte_physical[base + i].v = 1;
-        phte_physical[base + i].vsid = vsid;
-        phte_physical[base + i].h = h;
-        phte_physical[base + i].api = api;
-        phte_physical[base + i].rpn = pfn;
-        phte_physical[base + i].r = 0;
-        phte_physical[base + i].c = 0;
-        phte_physical[base + i].wimg = 0;
-        phte_physical[base + i].pp = 2; // FIXME
 }
 
@@ -337 +279 @@
  *
  */
-bool pht_real_refill(int n, istate_t *istate)
+bool pht_refill_real(int n, istate_t *istate)
 {
         uintptr_t badvaddr;
@@ -352 +294 @@
         );
         
-        if ((badvaddr >= PA2KA(0)) && (badvaddr < PA2KA(physmem))) {
-                pht_real_insert(badvaddr, KA2PA(badvaddr) >> 12);
-                return true;
-        }
-        
-        return false;
+        if ((badvaddr < PA2KA(0)) || (badvaddr >= PA2KA(physmem)))
+                return false;
+        
+        uint32_t page = (badvaddr >> 12) & 0xffff;
+        uint32_t api = (badvaddr >> 22) & 0x3f;
+        
+        uint32_t vsid;
+        asm volatile (
+                "mfsrin %0, %1\n"
+                : "=r" (vsid)
+                : "r" (badvaddr)
+        );
+        
+        uint32_t sdr1;
+        asm volatile (
+                "mfsdr1 %0\n"
+                : "=r" (sdr1)
+        );
+        phte_t *phte_real = (phte_t *) (sdr1 & 0xffff0000);
+        
+        /* Primary hash (xor) */
+        uint32_t h = 0;
+        uint32_t hash = vsid ^ page;
+        uint32_t base = (hash & 0x3ff) << 3;
+        uint32_t i;
+        bool found = false;
+        
+        /* Find unused or colliding PTE in PTEG */
+        for (i = 0; i < 8; i++) {
+                if ((!phte_real[base + i].v) ||
+                    ((phte_real[base + i].vsid == vsid)
+                    && (phte_real[base + i].api == api)
+                    && (phte_real[base + i].h == 0))) {
+                        found = true;
+                        break;
+                }
+        }
+        
+        if (!found) {
+                /* Secondary hash (not) */
+                uint32_t base2 = (~hash & 0x3ff) << 3;
+                
+                /* Find unused or colliding PTE in PTEG */
+                for (i = 0; i < 8; i++) {
+                        if ((!phte_real[base2 + i].v) ||
+                            ((phte_real[base2 + i].vsid == vsid)
+                            && (phte_real[base2 + i].api == api)
+                            && (phte_real[base2 + i].h == 1))) {
+                                found = true;
+                                base = base2;
+                                h = 1;
+                                break;
+                        }
+                }
+                
+                if (!found) {
+                        /* Use secondary hash to avoid collisions
+                           with usual PHT refill handler. */
+                        i = RANDI(seed_real) % 8;
+                        base = base2;
+                        h = 1;
+                }
+        }
+        
+        phte_real[base + i].v = 1;
+        phte_real[base + i].vsid = vsid;
+        phte_real[base + i].h = h;
+        phte_real[base + i].api = api;
+        phte_real[base + i].rpn = KA2PA(badvaddr) >> 12;
+        phte_real[base + i].r = 0;
+        phte_real[base + i].c = 0;
+        phte_real[base + i].wimg = 0;
+        phte_real[base + i].pp = 2; // FIXME
+        
+        return true;
 }
 
@@ -439 +450 @@
                         : "r" (sr << 28)
                 );
-                printf("vsid[%d]: VSID=%.*p (ASID=%d)%s%s\n", sr,
+                printf("sr[%02u]: vsid=%.*p (asid=%u)%s%s\n", sr,
                     sizeof(vsid) * 2, vsid & 0xffffff, (vsid & 0xffffff) >> 4,
                     ((vsid >> 30) & 1) ? " supervisor" : "",