lib/vfs/vfs_cache.c

111 free_unused(struct fs_cache *cache, size_t factor, size_t maximum)
118             unused_overburden = cache->unused_count;
120         else if (maximum > 0 && cache->unused_count > maximum) {
121             unused_overburden = cache->unused_count - maximum;
126             if (cache->unused_count > maximum) {
130                 unused_overburden = cache->unused_count;
134     else if (cache->unused_count > cache->capacity / factor) {
135         unused_overburden = cache->unused_count - cache->capacity/factor;
136         if (maximum > 0 && cache->unused_count > maximum) {
142         assert(cache->unused_count > 0);
143         assert(cache->first_unused);
144         size_t entry_index = cache->first_unused;
145         struct cache_entry *entry = &cache->entries[entry_index-1];
150             cache->entries[entry->next_unused-1].prev_unused = 0;
152         if (entry_index == cache->last_unused) {
153             cache->last_unused = 0;
155         cache->first_unused = entry->next_unused;
156         assert((cache->first_unused == 0) == (cache->last_unused == 0));
157         cache->unused_count--;
161             cache->entries[entry->next-1].prev = entry->prev;
164             cache->entries[entry->prev-1].next = entry->next;
168             size_t hash = hash_key(entry->key, cache->map_size);
169             assert(cache->map[hash] == entry_index);
170             cache->map[hash] = entry->next;
176         if (cache->first_free) {
177             entry->next = cache->first_free;
178             cache->entries[cache->first_free-1].prev = entry_index;
180         cache->first_free = entry_index;
185 cache_make_space(struct fs_cache *cache)
189     if (cache->capacity == 0) {
191         cache->entries = calloc(MIN_ALLOC, sizeof(*cache->entries));
192         if (!cache->entries) {
195         cache->capacity = MIN_ALLOC;
196         cache->first_free = 1;
197         for (size_t i = 1; i < cache->capacity; ++i) {
198             cache->entries[i-1].next = i+1;
199             cache->entries[i].prev = i;
204     size_t new_capacity = 2*cache->capacity;
205     if (new_capacity <= cache->max_capacity) {
208         new_entries = realloc(cache->entries,
209                 new_capacity*sizeof(*cache->entries));
215         cache->entries = new_entries;
216         memset(cache->entries + cache->capacity, 0,
217                 cache->capacity*sizeof(*cache->entries));
219         for (size_t i = cache->capacity + 1; i < new_capacity; i++) {
220             cache->entries[i-1].next = i+1;
221             cache->entries[i].prev = i;
223         cache->first_free = cache->capacity + 1;
224         cache->capacity = new_capacity;
230     free_unused(cache, 2, 10);
231     if (cache->first_free) {
237         free_unused(cache, f, 0);
238         if (cache->first_free) {
244     free_unused(cache, 0, 10);
245     if (cache->first_free) {
250     free_unused(cache, 0, 0);
251     if (cache->first_free) {
259 get_new_entry(struct fs_cache *cache, size_t hash, struct cache_entry **entry)
264     if (!cache->first_free) {
265         ERRRET(cache_make_space(cache));
266         if (!cache->first_free) {
272     size_t entry_index = cache->first_free;
273     cache->first_free = cache->entries[entry_index-1].next;
274     *entry = &cache->entries[entry_index-1];
281 remove_from_unused(struct fs_cache *cache, struct cache_entry *entry)
285     size_t entry_index = (entry - cache->entries) + 1;
287         assert(cache->first_unused != entry_index);
288         cache->entries[entry->prev_unused-1].next_unused = entry->next_unused;
291         assert(cache->first_unused == entry_index);
292         cache->first_unused = entry->next_unused;
295         assert(cache->last_unused != entry_index);
296         cache->entries[entry->next_unused-1].prev_unused = entry->prev_unused;
299         assert(cache->last_unused == entry_index);
300         cache->last_unused = entry->prev_unused;
303     cache->unused_count--;
307 fs_cache_acquire(struct fs_cache *cache, uint32_t key, void **item)
310     assert(cache);
312     if (!cache->entries) {
316     size_t hash = hash_key(key, cache->map_size);
317     size_t entry_index = cache->map[hash];
324     struct cache_entry *entry = &cache->entries[entry_index-1];
326         entry = &cache->entries[entry->next-1];
334         remove_from_unused(cache, entry);
344 fs_cache_put(struct fs_cache *cache, uint32_t key, void *item)
347     assert(cache);
350     size_t hash = hash_key(key, cache->map_size);
351     size_t entry_index = cache->map[hash];
356         err = get_new_entry(cache, hash, &entry);
358             entry_index = (entry - cache->entries) + 1;
359             cache->map[hash] = entry_index;
364         entry = &cache->entries[entry_index-1];
366             entry = &cache->entries[entry->next-1];
377                 remove_from_unused(cache, entry);
389             err = get_new_entry(cache, hash, &entry);
391                 entry_index = (entry - cache->entries) + 1;
393                 entry->prev = (prev - cache->entries) + 1;
408 fs_cache_release(struct fs_cache* cache, uint32_t key)
411     assert(cache);
413     if (!cache->entries) {
417     size_t hash = hash_key(key, cache->map_size);
418     size_t entry_index = cache->map[hash];
425     struct cache_entry *entry = &cache->entries[entry_index-1];
427         entry = &cache->entries[entry->next-1];
437         entry_index = (entry - cache->entries) + 1;
438         if (cache->unused_count > 0) {
439             assert(cache->first_unused);
440             assert(cache->last_unused);
441             cache->entries[cache->last_unused-1].next_unused = entry_index;
444             assert(!cache->first_unused);
445             assert(!cache->last_unused);
446             cache->first_unused = entry_index;
448         entry->prev_unused = cache->last_unused;
450         cache->last_unused = entry_index;
451         cache->unused_count++;
463     struct fs_cache *cache;
464     cache = calloc(1, sizeof(*cache));
465     if (!cache) {
471     cache->max_capacity = max_capacity;
479     cache->map_size = map_size;
480     cache->map = calloc(cache->map_size, sizeof(*cache->map));
481     if (!cache->map) {
482         free(cache);
486     *cache_p = cache;
491 fs_cache_free(struct fs_cache *cache)
495     if (!cache) {
499     for (size_t i = 0; i < cache->capacity; i++) {
500         if (cache->entries[i].item) {
501             free(cache->entries[i].item);
504     free(cache->entries);
505     free(cache->map);
506     free(cache);