[Mesa-dev] [PATCH 3/3] util/disk_cache: use rand_xorshift128plus() to get our random int

[Timothy Arceri]

On 21/03/17 21:10, Nicolai Hähnle wrote:
> On 21.03.2017 09:57, Timothy Arceri wrote:
>> Otherwise for apps that don't seed the regular rand() we will always
>> remove old cache entries from the same dirs.
>> ---
>>  src/util/disk_cache.c | 9 +++++++--
>>  1 file changed, 7 insertions(+), 2 deletions(-)
>>
>> diff --git a/src/util/disk_cache.c b/src/util/disk_cache.c
>> index f2d67c9..f6ecf0b 100644
>> --- a/src/util/disk_cache.c
>> +++ b/src/util/disk_cache.c
>> @@ -34,20 +34,21 @@
>>  #include <sys/statvfs.h>
>>  #include <sys/mman.h>
>>  #include <unistd.h>
>>  #include <fcntl.h>
>>  #include <pwd.h>
>>  #include <errno.h>
>>  #include <dirent.h>
>>  #include "zlib.h"
>>
>>  #include "util/crc32.h"
>> +#include "util/rand_xor.h"
>>  #include "util/u_atomic.h"
>>  #include "util/u_queue.h"
>>  #include "util/mesa-sha1.h"
>>  #include "util/ralloc.h"
>>  #include "main/errors.h"
>>  #include "util/macros.h"
>>
>>  #include "disk_cache.h"
>>
>>  /* Number of bits to mask off from a cache key to get an index. */
>> @@ -354,20 +355,23 @@ disk_cache_create(const char *gpu_name, const
>> char *timestamp)
>>     cache->max_size = max_size;
>>
>>     /* A limit of 32 jobs was choosen as observations of Deus Ex
>> start-up times
>>      * showed that we reached at most 11 jobs on an Intel i5-6400
>> CPU at 2.70GHz
>>      * (a fairly modest desktop CPU). 1 thread was chosen because we
>> don't
>>      * really care about getting things to disk quickly just that it's
>> not
>>      * blocking other tasks.
>>      */
>>     util_queue_init(&cache->cache_queue, "disk_cache", 32, 1);
>>
>> +   /* Seed our rand function */
>> +   s_rand_xorshift128plus();
>> +
>>     ralloc_free(local);
>>
>>     return cache;
>>
>>   fail:
>>     if (fd != -1)
>>        close(fd);
>>     if (cache)
>>        ralloc_free(cache);
>>     ralloc_free(local);
>> @@ -569,22 +573,23 @@ evict_lru_item(struct disk_cache *cache)
>>     const char hex[] = "0123456789abcde";
>>     char *dir_path;
>>     int a, b;
>>     size_t size;
>>
>>     /* With a reasonably-sized, full cache, (and with keys generated
>>      * from a cryptographic hash), we can choose two random hex digits
>>      * and reasonably expect the directory to exist with a file in it.
>>      * Provides pseudo-LRU eviction to reduce checking all cache files.
>>      */
>> -   a = rand() % 16;
>> -   b = rand() % 16;
>> +   uint64_t rand64 = rand_xorshift128plus();
>> +   a = (rand64 >> 32) % 16;
>> +   b = (rand64 & 0xFFFFFFFF) % 16;
>
> Why not just
>
> a = rand64 & 0xf;
> b = (rand64 >> 4) & 0xf;
>
> ?

Because % 16 is meant to give you a uniform distribution of random 
numbers between 0-15. Thinking about this some more I don't think I 
should really be splitting the number in half. I should really call it 
twice, I was looking for an open-source 32-bit generator but only found 
papers not code so settled with this existing one.

>
> Actually, why not simplify even further by saying:
>
>>
>>     if (asprintf(&dir_path, "%s/%c%c", cache->path, hex[a], hex[b]) < 0)
>
> asprintf(..., "%s/%02x", ..., rand64 & 0xff)
>
> That would also fix the bug that the hex string is missing the final 'f'
> ;-)

Huh, hadn't noticed that. The joys of finish off prototype code :)

>
> Cheers,
> Nicolai
>
>>        return;
>>
>>     size = unlink_lru_file_from_directory(dir_path);
>>
>>     free(dir_path);
>>
>>     if (size) {
>>        p_atomic_add(cache->size, - (uint64_t)size);
>>
>