Re: [Qemu-devel] [PATCH pic32 v2 2/5] Fixed random index generation for TLBWR instruction. It was not quite random and did not skip Wired entries.

[Serge Vakulenko]

On Wed, Jul 1, 2015 at 3:11 AM, Aurelien Jarno <address@hidden> wrote:
> On 2015-06-30 21:12, Serge Vakulenko wrote:
>> Signed-off-by: Serge Vakulenko <address@hidden>
>> ---
>>  hw/mips/cputimer.c | 18 +++++-------------
>>  1 file changed, 5 insertions(+), 13 deletions(-)
>>
>> diff --git a/hw/mips/cputimer.c b/hw/mips/cputimer.c
>> index 4f02a9f..94a29df 100644
>> --- a/hw/mips/cputimer.c
>> +++ b/hw/mips/cputimer.c
>> @@ -25,21 +25,13 @@
>>  #include "qemu/timer.h"
>>  #include "sysemu/kvm.h"
>>
>> -#define TIMER_FREQ   100 * 1000 * 1000
>> -
>> -/* XXX: do not use a global */
>> +/* Generate a random TLB index.
>> + * Skip wired entries. */
>>  uint32_t cpu_mips_get_random (CPUMIPSState *env)
>>  {
>> -    static uint32_t lfsr = 1;
>> -    static uint32_t prev_idx = 0;
>> -    uint32_t idx;
>> -    /* Don't return same value twice, so get another value */
>> -    do {
>> -        lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & 0xd0000001u);
>> -        idx = lfsr % (env->tlb->nb_tlb - env->CP0_Wired) + env->CP0_Wired;
>> -    } while (idx == prev_idx);
>> -    prev_idx = idx;
>> -    return idx;
>> +    env->CP0_Random = env->CP0_Wired +
>> +        random() % (env->tlb->nb_tlb - env->CP0_Wired);
>> +    return env->CP0_Random;
>>  }
>>
>>  /* MIPS R4K timer */
>
> Can you please give us more details about what issue you are trying to
> fix there? Especially I don't understand about the "skip wired entries"
> part. It seems the original code handles the wired entries correctly,
> and at least your patch doesn't seem to change anything regarded that
> part.

The original code looks fine by itself. But when you try to run in for
nb_tlb=16 and CP0_Wired=1, you get a sequence:

15, 6, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7, 2, 7,
2, 7, 2, 7, 2...

This is what happens when 4.4bsd kernel starts on pic32mz processor.
It makes the VM subsystem a bit crazy. Later the sequence becomes
better, but I think it makes sense to improve it somehow.

> Secondly, I don't think calling random() is the correct thing to do.
> It's an expensive function that is not thread safe. Quoting the
> specification:
>
>   "Within the required constraints of the upper and lower bounds, the
>   manner in which the processor selects values for the Random register
>   is implementation-dependent."
>
> So it's fine if we use a PRNG like the current code, but I agree we
> might want to improve it if it has some issues. We want to keep its
> value reproducible though so that the icount mode works as expected.

I agree that random() is somewhat heavy routine, and we don't need so
much randomness here. OK, in the next version of this patch set I'll
propose another variant of simple random generator, like TLCG or
something.

> --
> Aurelien Jarno                          GPG: 4096R/1DDD8C9B
> address@hidden                 http://www.aurel32.net