LCOV - code coverage report
Current view: top level - lib/generic - lru.c Hit Total Coverage
Test: Knot Resolver 3.2.1-POSIX coverage report Lines: 104 134 77.6 %
Date: 2019-03-12 03:31:59
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*  Copyright (C) 2016-2018 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>
       2             : 
       3             :     This program is free software: you can redistribute it and/or modify
       4             :     it under the terms of the GNU General Public License as published by
       5             :     the Free Software Foundation, either version 3 of the License, or
       6             :     (at your option) any later version.
       7             : 
       8             :     This program is distributed in the hope that it will be useful,
       9             :     but WITHOUT ANY WARRANTY; without even the implied warranty of
      10             :     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      11             :     GNU General Public License for more details.
      12             : 
      13             :     You should have received a copy of the GNU General Public License
      14             :     along with this program.  If not, see <https://www.gnu.org/licenses/>.
      15             :  */
      16             : 
      17             : #include "lib/generic/lru.h"
      18             : #include "contrib/murmurhash3/murmurhash3.h"
      19             : #include "contrib/ucw/mempool.h"
      20             : 
      21             : typedef struct lru_group lru_group_t;
      22             : 
      23             : struct lru_item {
      24             :         uint16_t key_len, val_len; /**< Two bytes should be enough for our purposes. */
      25             :         char data[];
      26             :         /**< Place for both key and value.
      27             :          *
      28             :          * We use "char" to satisfy the C99+ aliasing rules.
      29             :          * See C99 section 6.5 Expressions, paragraph 7.
      30             :          * Any type can be accessed through char-pointer,
      31             :          * so we can use a common struct definition
      32             :          * for all types being held.
      33             :          *
      34             :          * The value address is restricted by val_alignment.
      35             :          * Approach: require slightly larger sizes from the allocator
      36             :          * and shift value on the closest address with val_alignment.
      37             :          */
      38             : };
      39             : 
      40             : /** @brief Round the value up to a multiple of mul (a power of two). */
      41      172745 : static inline size_t round_power(size_t size, size_t mult)
      42             : {
      43      172745 :         assert(__builtin_popcount(mult) == 1);
      44      172745 :         size_t res = ((size - 1) & ~(mult - 1)) + mult;
      45      172745 :         assert(__builtin_ctz(res) >= __builtin_ctz(mult));
      46      172745 :         assert(size <= res && res < size + mult);
      47      172745 :         return res;
      48             : }
      49             : 
      50             : /** @internal Compute the allocation size for an lru_item. */
      51        6823 : static uint item_size(const struct lru *lru, uint key_len, uint val_len)
      52             : {
      53        8769 :         uint key_end = offsetof(struct lru_item, data) + key_len;
      54        8769 :         return key_end + (lru->val_alignment - 1) + val_len;
      55             :         /*             ^^^ worst-case padding length
      56             :          * Well, we might compute the bound a bit more precisely,
      57             :          * as we know that lru_item will get alignment at least
      58             :          * some sizeof(void*) and we know all the lengths,
      59             :          * but let's not complicate it, as the gain would be small anyway. */
      60             : }
      61             : 
      62             : /** @internal Return pointer to value in an lru_item. */
      63      166710 : static void * item_val(const struct lru *lru, struct lru_item *it)
      64             : {
      65      172745 :         size_t key_end = it->data + it->key_len - (char *)NULL;
      66      169787 :         size_t val_begin = round_power(key_end, lru->val_alignment);
      67      172745 :         return (char *)NULL + val_begin;
      68             : }
      69             : 
      70             : /** @internal Free each item. */
      71          36 : KR_EXPORT void lru_free_items_impl(struct lru *lru)
      72             : {
      73          36 :         assert(lru);
      74      384026 :         for (size_t i = 0; i < (1 << (size_t)lru->log_groups); ++i) {
      75      172036 :                 lru_group_t *g = &lru->groups[i];
      76     1324575 :                 for (int j = 0; j < LRU_ASSOC; ++j)
      77     1152027 :                         mm_free(lru->mm, g->items[j]);
      78             :         }
      79          36 : }
      80             : 
      81             : /** @internal See lru_apply. */
      82           2 : KR_EXPORT void lru_apply_impl(struct lru *lru, lru_apply_fun f, void *baton)
      83             : {
      84           2 :         bool ok = lru && f;
      85           2 :         if (!ok) {
      86           0 :                 assert(false);
      87             :                 return;
      88             :         }
      89        4096 :         for (size_t i = 0; i < (1 << (size_t)lru->log_groups); ++i) {
      90           0 :                 lru_group_t *g = &lru->groups[i];
      91       12288 :                 for (uint j = 0; j < LRU_ASSOC; ++j) {
      92       12288 :                         struct lru_item *it = g->items[j];
      93       12288 :                         if (!it)
      94       12288 :                                 continue;
      95           0 :                         enum lru_apply_do ret =
      96           0 :                                 f(it->data, it->key_len, item_val(lru, it), baton);
      97           0 :                         switch(ret) {
      98           0 :                         case LRU_APPLY_DO_EVICT: // evict
      99           0 :                                 mm_free(lru->mm, it);
     100           0 :                                 g->items[j] = NULL;
     101           0 :                                 g->counts[j] = 0;
     102           0 :                                 g->hashes[j] = 0;
     103           0 :                                 break;
     104           0 :                         default:
     105           0 :                                 assert(ret == LRU_APPLY_DO_NOTHING);
     106             :                         }
     107             :                 }
     108             :         }
     109           2 : }
     110             : 
     111             : /** @internal See lru_create. */
     112          79 : KR_EXPORT struct lru * lru_create_impl(uint max_slots, uint val_alignment,
     113             :                                         knot_mm_t *mm_array, knot_mm_t *mm)
     114             : {
     115          79 :         assert(max_slots && __builtin_popcount(val_alignment) == 1);
     116          16 :         if (!max_slots)
     117           0 :                 return NULL;
     118             :         // let lru->log_groups = ceil(log2(max_slots / (float) assoc))
     119             :         //   without trying for efficiency
     120          79 :         uint group_count = (max_slots - 1) / LRU_ASSOC + 1;
     121          16 :         uint log_groups = 0;
     122         834 :         for (uint s = group_count - 1; s; s /= 2)
     123         755 :                 ++log_groups;
     124          79 :         group_count = 1 << log_groups;
     125          79 :         assert(max_slots <= group_count * LRU_ASSOC && group_count * LRU_ASSOC < 2 * max_slots);
     126             : 
     127             :         /* Get a sufficiently aligning mm_array if NULL is passed. */
     128          79 :         if (!mm_array) {
     129             :                 static knot_mm_t mm_array_default = { 0 };
     130          79 :                 if (!mm_array_default.ctx)
     131           4 :                         mm_ctx_init_aligned(&mm_array_default, __alignof(struct lru));
     132          16 :                 mm_array = &mm_array_default;
     133             :         }
     134          79 :         assert(mm_array->alloc != mm_malloc && mm_array->alloc != (knot_mm_alloc_t)mp_alloc);
     135             : 
     136          79 :         size_t size = offsetof(struct lru, groups[group_count]);
     137          79 :         struct lru *lru = mm_alloc(mm_array, size);
     138          79 :         if (unlikely(lru == NULL))
     139           0 :                 return NULL;
     140          79 :         *lru = (struct lru){
     141             :                 .mm = mm,
     142             :                 .mm_array = mm_array,
     143             :                 .log_groups = log_groups,
     144             :                 .val_alignment = val_alignment,
     145             :         };
     146             :         // zeros are a good init
     147          79 :         memset(lru->groups, 0, size - offsetof(struct lru, groups));
     148          79 :         return lru;
     149             : }
     150             : 
     151             : /** @internal Decrement all counters within a group. */
     152       25342 : static void group_dec_counts(lru_group_t *g) {
     153       26238 :         g->counts[LRU_TRACKED] = LRU_TRACKED;
     154      287813 :         for (uint i = 0; i < LRU_TRACKED + 1; ++i)
     155      262380 :                 if (likely(g->counts[i]))
     156       27135 :                         --g->counts[i];
     157       25342 : }
     158             : 
     159             : /** @internal Increment a counter within a group. */
     160      159905 : static void group_inc_count(lru_group_t *g, int i) {
     161      163994 :         if (likely(++(g->counts[i])))
     162      159905 :                 return;
     163           0 :         g->counts[i] = -1;
     164             :         // We could've decreased or halved all of them, but let's keep the max.
     165             : }
     166             : 
     167             : /** @internal Implementation of both getting and insertion.
     168             :  * Note: val_len is only meaningful if do_insert.
     169             :  *       *is_new is only meaningful when return value isn't NULL, contains
     170             :  *       true when returned lru entry has been allocated right now
     171             :  *       if return value is NULL, *is_new remains untouched.
     172             :  */
     173      318202 : KR_EXPORT void * lru_get_impl(struct lru *lru, const char *key, uint key_len,
     174             :                               uint val_len, bool do_insert, bool *is_new)
     175             : {
     176      322894 :         bool ok = lru && (key || !key_len) && key_len <= UINT16_MAX
     177      636404 :                    && (!do_insert || val_len <= UINT16_MAX);
     178      318202 :         if (!ok) {
     179           0 :                 assert(false);
     180             :                 return NULL; // reasonable fallback when not debugging
     181             :         }
     182      311399 :         bool is_new_entry = false;
     183             :         // find the right group
     184      318202 :         uint32_t khash = hash(key, key_len);
     185      318202 :         uint16_t khash_top = khash >> 16;
     186      318202 :         lru_group_t *g = &lru->groups[khash & ((1 << lru->log_groups) - 1)];
     187      311399 :         struct lru_item *it = NULL;
     188             :         uint i;
     189             :         // scan the *stored* elements in the group
     190      809605 :         for (i = 0; i < LRU_ASSOC; ++i) {
     191      646646 :                 if (g->hashes[i] == khash_top) {
     192      155243 :                         it = g->items[i];
     193      155243 :                         if (likely(it && it->key_len == key_len
     194             :                                         && (key_len == 0 || memcmp(it->data, key, key_len) == 0))) {
     195             :                                 /* Found a key, but trying to insert a value larger than available
     196             :                                  * space in the allocated slot, so the entry must be resized to fit. */
     197      155243 :                                 if (unlikely(do_insert && val_len > it->val_len)) {
     198           0 :                                         goto insert;
     199             :                                 } else {
     200      153100 :                                         goto found; // to reduce huge nesting depth     
     201             :                                 }
     202             :                         }
     203             :                 }
     204             :         }
     205             :         // key not found; first try an empty/counted-out place to insert
     206      162959 :         if (do_insert)
     207       10849 :                 for (i = 0; i < LRU_ASSOC; ++i)
     208       11669 :                         if (g->items[i] == NULL || g->counts[i] == 0)
     209        7791 :                                 goto insert;
     210             :         // check if we track key's count at least
     211     1076881 :         for (i = LRU_ASSOC; i < LRU_TRACKED; ++i) {
     212      925248 :                 if (g->hashes[i] == khash_top) {
     213           0 :                         group_inc_count(g, i);
     214           0 :                         if (!do_insert)
     215           0 :                                 return NULL;
     216             :                         // check if we trumped some stored key
     217           0 :                         for (uint j = 0; j < LRU_ASSOC; ++j)
     218           0 :                                 if (unlikely(g->counts[i] > g->counts[j])) {
     219             :                                         // evict key j, i.e. swap with i
     220           0 :                                         --g->counts[i]; // we increment it below
     221           0 :                                         SWAP(g->counts[i], g->counts[j]);
     222           0 :                                         SWAP(g->hashes[i], g->hashes[j]);
     223           0 :                                         i = j;
     224           0 :                                         goto insert;
     225             :                                 }
     226           0 :                         return NULL;
     227             :                 }
     228             :         }
     229             :         // not found at all: decrement all counts but only on every LRU_TRACKED occasion
     230      154208 :         if (g->counts[LRU_TRACKED])
     231      127970 :                 --g->counts[LRU_TRACKED];
     232             :         else
     233       25342 :                 group_dec_counts(g);
     234      151494 :         return NULL;
     235        7791 : insert: // insert into position i (incl. key)
     236        7765 :         assert(i < LRU_ASSOC);
     237        8751 :         g->hashes[i] = khash_top;
     238        8751 :         it = g->items[i];
     239        6805 :         uint new_size = item_size(lru, key_len, val_len);
     240        8751 :         if (it == NULL || new_size != item_size(lru, it->key_len, it->val_len)) {
     241             :                 // (re)allocate
     242        8744 :                 mm_free(lru->mm, it);
     243        8744 :                 it = g->items[i] = mm_alloc(lru->mm, new_size);
     244        8744 :                 if (it == NULL)
     245           0 :                         return NULL;
     246             :         }
     247        8751 :         it->key_len = key_len;
     248        8751 :         it->val_len = val_len;
     249        8751 :         if (key_len > 0) {
     250        8751 :                 memcpy(it->data, key, key_len);
     251             :         }
     252        9711 :         memset(item_val(lru, it), 0, val_len); // clear the value
     253        6805 :         is_new_entry = true;
     254      161877 : found: // key and hash OK on g->items[i]; now update stamps
     255      162022 :         assert(i < LRU_ASSOC);
     256      163994 :         group_inc_count(g, i);
     257      163994 :         if (is_new) {
     258       14623 :                 *is_new = is_new_entry;
     259             :         }
     260      166111 :         return item_val(lru, g->items[i]);
     261             : }
     262             : 

Generated by: LCOV version 1.13