[Mesa-dev] [PATCH 1/3] util/disk_cache: use LRU eviction rather than random eviction (v2)

[Emil Velikov]

On 10 March 2017 at 10:51, Grazvydas Ignotas <notasas at gmail.com> wrote:
> On Fri, Mar 10, 2017 at 6:23 AM, Timothy Arceri <tarceri at itsqueeze.com> wrote:
>> On 07/03/17 12:25, Alan Swanson wrote:
>>>
>>> Still using random selection of two-character subdirectory in which
>>> to check cache files rather than scanning entire cache.
>>>
>>> v2: Factor out double strlen call
>>> ---
>>>  src/util/disk_cache.c | 78
>>> +++++++++++++++++++++++----------------------------
>>>  1 file changed, 35 insertions(+), 43 deletions(-)
>>>
>>> diff --git a/src/util/disk_cache.c b/src/util/disk_cache.c
>>> index 31a9336582..2a923be3dc 100644
>>> --- a/src/util/disk_cache.c
>>> +++ b/src/util/disk_cache.c
>>> @@ -438,70 +438,60 @@ make_cache_file_directory(struct disk_cache *cache,
>>> const cache_key key)
>>>     free(dir);
>>>  }
>>>
>>> -/* Given a directory path and predicate function, count all entries in
>>> - * that directory for which the predicate returns true. Then choose a
>>> - * random entry from among those counted.
>>> +/* Given a directory path and predicate function, find the entry with
>>> + * the oldest access time in that directory for which the predicate
>>> + * returns true.
>>>   *
>>>   * Returns: A malloc'ed string for the path to the chosen file, (or
>>>   * NULL on any error). The caller should free the string when
>>>   * finished.
>>>   */
>>>  static char *
>>> -choose_random_file_matching(const char *dir_path,
>>> -                            bool (*predicate)(const struct dirent *,
>>> -                                              const char *dir_path))
>>> +choose_lru_file_matching(const char *dir_path,
>>> +                         bool (*predicate)(const struct dirent *,
>>> +                                           const char *dir_path))
>>>  {
>>>     DIR *dir;
>>>     struct dirent *entry;
>>> -   unsigned int count, victim;
>>> +   struct stat sb;
>>> +   char *tmp, *lru_name = NULL;
>>> +   size_t len;
>>> +   time_t lru_atime = 0;
>>
>>
>> Please try to declare variables where they are used. The original version of
>> this file was written before we could use C99 features in Mesa.
>>
>>
>>
>>>     char *filename;
>>>
>>>     dir = opendir(dir_path);
>>>     if (dir == NULL)
>>>        return NULL;
>>>
>>> -   count = 0;
>>> -
>>> -   while (1) {
>>> -      entry = readdir(dir);
>>> -      if (entry == NULL)
>>> -         break;
>>> -      if (!predicate(entry, dir_path))
>>> -         continue;
>>> -
>>> -      count++;
>>> -   }
>>> -
>>> -   if (count == 0) {
>>> -      closedir(dir);
>>> -      return NULL;
>>> -   }
>>> -
>>> -   victim = rand() % count;
>>> -
>>> -   rewinddir(dir);
>>> -   count = 0;
>>> -
>>>     while (1) {
>>>        entry = readdir(dir);
>>>        if (entry == NULL)
>>>           break;
>>>        if (!predicate(entry, dir_path))
>>>           continue;
>>> -      if (count == victim)
>>> -         break;
>>>
>>> -      count++;
>>> +      if (fstatat(dirfd(dir), entry->d_name, &sb, 0) == 0) {
>>> +         if (!lru_atime || (sb.st_atime < lru_atime)) {
>>> +            len = strlen(entry->d_name) + 1;
>>> +            tmp = realloc(lru_name, len);
>>> +            if (tmp) {
>>> +               lru_name = tmp;
>>
>>
>> I don't think we need tmp here. Why not use lru_name directly?
>
> It *is* needed, otherwise if realloc fails, you'll leak old memory.
>
Indeed. Alternatively one can avoid all the strlen/realloc/free dances
by using NAME_MAX.

As per the POSIX manual
"The array d_name is of unspecified size, but shall contain a filename
of at most {NAME_MAX} bytes followed by a terminating null byte."

Not 100% sure if it'll play well with Hurd and similar platforms :-\

-Emil