Skip to contentSkip to conversation

MIPS CP0 random register strategy

RFC In review Hervé Poussineau 2 participants 2 messages Jan 1, 2009 – Jan 3, 2009

lore
Share & tools
lore
#0 lore raw

RFC 1/1 MIPS CP0 random register strategy

Hello,

MIPS TLBWR instruction asks the CPU to randomly overwrite a TLB entry by the one we want to write. The TLB index needs to be between number of wired TLB entries and TLB count - 1. However, algorithm to choose which one to overwrite is implementation dependant.

After checking MIPS CPU documentations, 4 algorithms are emerging:
- Random register is decremented once at each clock tick
- Random register is decremented once after 'number of wired TLB entries' clock ticks
- Random register is decremented only after TLBWR instruction
- Random register uses a Not Last Used algorithm, ie whatever value which is not the previous one

At the moment, Qemu implementation seems to be more the 4th one, but can return the same value more than once. Due to this, NetBSD 1.6.2 on MIPS Magnum emulation crashes.

Attached patch tries to fix the problem by adding 4 methods to update Random value. Each CPU needs to define which Random algorithm it is using.
Patch also optimizes CP0_Random access, by not requiring call to a helper function Finally, it initializes CP0_Random even in user mode emulation, which was not the case before.

Please comment

Hervé

mips_timer.c +2 -16
Index: hw/mips_timer.c
===================================================================
@@ -4,25 +4,11 @@
 
 #define TIMER_FREQ	100 * 1000 * 1000
 
-/* XXX: do not use a global */
-uint32_t cpu_mips_get_random (CPUState *env)
-{
-    static uint32_t seed = 0;
-    uint32_t idx;
-    seed = seed * 314159 + 1;
-    idx = (seed >> 16) % (env->tlb->nb_tlb - env->CP0_Wired) + env->CP0_Wired;
-    return idx;
-}
-
 /* MIPS R4K timer */
 uint32_t cpu_mips_get_count (CPUState *env)
 {
-    if (env->CP0_Cause & (1 << CP0Ca_DC))
-        return env->CP0_Count;
-    else
-        return env->CP0_Count +
-            (uint32_t)muldiv64(qemu_get_clock(vm_clock),
-                               TIMER_FREQ, ticks_per_sec);
+    return (uint32_t)muldiv64(qemu_get_clock(vm_clock),
+                              TIMER_FREQ, ticks_per_sec);
 }
 
 static void cpu_mips_timer_update(CPUState *env)
cpu.h +7 -1
Index: target-mips/cpu.h
===================================================================
@@ -449,6 +449,8 @@
     uint32_t CP0_TCStatus_rw_bitmask; /* Read/write bits in CP0_TCStatus */
     int insn_flags; /* Supported instruction set */
 
+    void (*update_cp0_random) (struct CPUMIPSState *env);
+
     target_ulong tls_value; /* For usermode emulation */
 
     CPU_COMMON
@@ -470,6 +472,11 @@
 void r4k_do_tlbr (void);
 void mips_cpu_list (FILE *f, int (*cpu_fprintf)(FILE *f, const char *fmt, ...));
 
+void cp0_random_each_wired (CPUMIPSState *env);
+void cp0_random_each_tlbwr (CPUMIPSState *env);
+void cp0_random_each_instr (CPUMIPSState *env);
+void cp0_random_nlu (CPUMIPSState *env);
+
 void do_unassigned_access(target_phys_addr_t addr, int is_write, int is_exec,
                           int unused, int size);
 
@@ -565,7 +572,6 @@
 int cpu_mips_signal_handler(int host_signum, void *pinfo, void *puc);
 
 /* mips_timer.c */
-uint32_t cpu_mips_get_random (CPUState *env);
 uint32_t cpu_mips_get_count (CPUState *env);
 void cpu_mips_store_count (CPUState *env, uint32_t value);
 void cpu_mips_store_compare (CPUState *env, uint32_t value);
helper.c +39 -0
Index: target-mips/helper.c
===================================================================
@@ -626,3 +626,42 @@
         }
     }
 }
+
+void cp0_random_each_wired (CPUMIPSState *env)
+{
+    uint32_t instr_count;
+    instr_count = (int32_t)cpu_mips_get_count(env);
+    instr_count /= env->CP0_Wired + 1;
+    instr_count %= env->tlb->nb_tlb - env->CP0_Wired;
+    env->CP0_Random = (int32_t)instr_count + env->CP0_Wired;
+}
+
+void cp0_random_each_tlbwr (CPUMIPSState *env)
+{
+    env->CP0_Random--;
+    if (env->CP0_Random <= env->CP0_Wired)
+        env->CP0_Random = env->tlb->nb_tlb - 1;
+}
+
+void cp0_random_each_instr (CPUMIPSState *env)
+{
+    uint32_t instr_count;
+    instr_count = (int32_t)cpu_mips_get_count(env);
+    instr_count %= env->tlb->nb_tlb - env->CP0_Wired;
+    env->CP0_Random = (int32_t)instr_count + env->CP0_Wired;
+}
+
+void cp0_random_nlu (CPUMIPSState *env)
+{
+    static uint32_t seed = 0;
+    uint32_t idx;
+    seed = seed * 314159 + 1;
+    idx = (seed >> 16) % (env->tlb->nb_tlb - env->CP0_Wired) + env->CP0_Wired;
+    if (idx == env->CP0_Random) {
+        /* prevent same value twice */
+        idx++;
+        if (idx == env->tlb->nb_tlb)
+            idx = env->CP0_Wired;
+    }
+    env->CP0_Random = idx;
+}
helper.h +0 -1
Index: target-mips/helper.h
===================================================================
@@ -49,7 +49,6 @@
 DEF_HELPER_0(mfc0_mvpcontrol, tl)
 DEF_HELPER_0(mfc0_mvpconf0, tl)
 DEF_HELPER_0(mfc0_mvpconf1, tl)
-DEF_HELPER_0(mfc0_random, tl)
 DEF_HELPER_0(mfc0_tcstatus, tl)
 DEF_HELPER_0(mftc0_tcstatus, tl)
 DEF_HELPER_0(mfc0_tcbind, tl)
op_helper.c +8 -7
Index: target-mips/op_helper.c
===================================================================
@@ -616,11 +616,6 @@
     return env->mvp->CP0_MVPConf1;
 }
 
-target_ulong do_mfc0_random (void)
-{
-    return (int32_t)cpu_mips_get_random(env);
-}
-
 target_ulong do_mfc0_tcstatus (void)
 {
     return env->active_tc.CP0_TCStatus;
@@ -728,7 +723,10 @@
 
 target_ulong do_mfc0_count (void)
 {
-    return (int32_t)cpu_mips_get_count(env);
+    if (env->CP0_Cause & (1 << CP0Ca_DC))
+        return env->CP0_Count;
+    else
+        return env->CP0_Count + (int32_t)cpu_mips_get_count(env);
 }
 
 target_ulong do_mftc0_entryhi(void)
@@ -1590,8 +1588,11 @@
 
 void r4k_do_tlbwr (void)
 {
-    int r = cpu_mips_get_random(env);
+    int r;
 
+    env->update_cp0_random(env);
+    r = env->CP0_Random;
+
     r4k_invalidate_tlb(env, r, 1);
     r4k_fill_tlb(r);
 }
translate.c +2 -2
Index: target-mips/translate.c
===================================================================
@@ -2767,7 +2767,7 @@
     case 1:
         switch (sel) {
         case 0:
-            gen_helper_mfc0_random(t0);
+            gen_mfc0_load32(t0, offsetof(CPUState, CP0_Random));
             rn = "Random";
             break;
         case 1:
@@ -3964,7 +3964,7 @@
     case 1:
         switch (sel) {
         case 0:
-            gen_helper_mfc0_random(t0);
+            gen_mfc0_load32(t0, offsetof(CPUState, CP0_Random));
             rn = "Random";
             break;
         case 1:
translate_init.c +55 -1

172 lines not on this page · raw message

#1 lore raw
Quoted 1 line · Hervé Poussineau

Hello,

Hi!

Quoted 14 lines

MIPS TLBWR instruction asks the CPU to randomly overwrite a TLB entry by the one we want to write. The TLB index needs to be between number of wired TLB entries and TLB count - 1.
However, algorithm to choose which one to overwrite is implementation dependant.

After checking MIPS CPU documentations, 4 algorithms are emerging:
- Random register is decremented once at each clock tick
- Random register is decremented once after 'number of wired TLB entries' clock ticks
- Random register is decremented only after TLBWR instruction
- Random register uses a Not Last Used algorithm, ie whatever value which is not the previous one

Quoted 7 lines

At the moment, Qemu implementation seems to be more the 4th one, but can return the same value more than once.
Due to this, NetBSD 1.6.2 on MIPS Magnum emulation crashes.

Attached patch tries to fix the problem by adding 4 methods to update Random value.
Each CPU needs to define which Random algorithm it is using.

After looking to the patch, I am not sure we really want to implement the 4 different methods. On the 4 different methods, only the one which decrement the random register actually corresponds to what the real CPU does. The instruction rate in QEMU is not related to the clock ticks, which makes the two algorithms based on clock ticks non-accurate, and the LRU algorithm which is implemented is actually a random algorithm.

If we look at the 4 algorithm, what seems to be important is:
- having something more or less random
- not returning the same value twice

What about only modifying the current algorithm to fix the second point?

Quoted 2 lines

Patch also optimizes CP0_Random access, by not requiring call to a helper function

This seems to be wrong, two reads from CP0_Random will return the same value, which is wrong at least for some algorithms.

Quoted 2 lines

Finally, it initializes CP0_Random even in user mode emulation, which was not the case before.

Also please note, that you patch breaks the read from CP0_Count.

Aurelien

Signature · 4 lines
  .''`.  Aurelien Jarno	            | GPG: 1024D/F1BCDB73
 : :' :  Debian developer           | Electrical Engineer
 `. `'   [email protected]         | [email protected]
   `-    people.debian.org/~aurel32 | www.aurel32.net