LCOV - code coverage report
Current view: top level - lib/generic - lru.h Hit Total Coverage
Test: Knot Resolver 3.2.1-POSIX coverage report Lines: 8 9 88.9 %
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             :  * @file lru.h
      18             :  * @brief A lossy cache.
      19             :  *
      20             :  * @note The implementation tries to keep frequent keys and avoid others,
      21             :  *  even if "used recently", so it may refuse to store it on lru_get_new().
      22             :  *  It uses hashing to split the problem pseudo-randomly into smaller groups,
      23             :  *  and within each it tries to approximate relative usage counts of several
      24             :  *  most frequent keys/hashes.  This tracking is done for *more* keys than
      25             :  *  those that are actually stored.
      26             :  *
      27             :  * Example usage:
      28             :  * @code{.c}
      29             :  *      // Define new LRU type
      30             :  *      typedef lru_t(int) lru_int_t;
      31             :  *
      32             :  *      // Create LRU
      33             :  *      lru_int_t *lru;
      34             :  *      lru_create(&lru, 5, NULL, NULL);
      35             :  *
      36             :  *      // Insert some values
      37             :  *      int *pi = lru_get_new(lru, "luke", strlen("luke"), NULL);
      38             :  *      if (pi)
      39             :  *              *pi = 42;
      40             :  *      pi = lru_get_new(lru, "leia", strlen("leia"), NULL);
      41             :  *      if (pi)
      42             :  *              *pi = 24;
      43             :  *
      44             :  *      // Retrieve values
      45             :  *      int *ret = lru_get_try(lru, "luke", strlen("luke"), NULL);
      46             :  *      if (!ret) printf("luke dropped out!\n");
      47             :  *          else  printf("luke's number is %d\n", *ret);
      48             :  *
      49             :  *      char *enemies[] = {"goro", "raiden", "subzero", "scorpion"};
      50             :  *      for (int i = 0; i < 4; ++i) {
      51             :  *              int *val = lru_get_new(lru, enemies[i], strlen(enemies[i]), NULL);
      52             :  *              if (val)
      53             :  *                      *val = i;
      54             :  *      }
      55             :  *
      56             :  *      // We're done
      57             :  *      lru_free(lru);
      58             :  * @endcode
      59             :  *
      60             :  * \addtogroup generics
      61             :  * @{
      62             :  */
      63             : 
      64             : #pragma once
      65             : 
      66             : #include <assert.h>
      67             : #include <stdint.h>
      68             : #include <stddef.h>
      69             : 
      70             : #include "contrib/ucw/lib.h"
      71             : #include "lib/utils.h"
      72             : #include "libknot/mm_ctx.h"
      73             : 
      74             : /* ================================ Interface ================================ */
      75             : 
      76             : /** @brief The type for LRU, parametrized by value type. */
      77             : #define lru_t(type) \
      78             :         union { \
      79             :                 type *pdata_t; /* only the *type* information is used */ \
      80             :                 struct lru lru; \
      81             :         }
      82             : 
      83             : /**
      84             :  * @brief Allocate and initialize an LRU with default associativity.
      85             :  *
      86             :  * The real limit on the number of slots can be a bit larger but less than double.
      87             :  *
      88             :  * @param ptable pointer to a pointer to the LRU
      89             :  * @param max_slots number of slots
      90             :  * @param mm_ctx_array memory context to use for the huge array, NULL for default
      91             :  *      If you pass your own, it needs to produce CACHE_ALIGNED allocations (ubsan).
      92             :  * @param mm_ctx memory context to use for individual key-value pairs, NULL for default
      93             :  *
      94             :  * @note The pointers to memory contexts need to remain valid
      95             :  *      during the whole life of the structure (or be NULL).
      96             :  */
      97             : #define lru_create(ptable, max_slots, mm_ctx_array, mm_ctx) do { \
      98             :         (void)(((__typeof__((*(ptable))->pdata_t))0) == (void *)0); /* typecheck lru_t */ \
      99             :         *(ptable) = (__typeof__(*(ptable))) \
     100             :                 lru_create_impl((max_slots), __alignof(*( (*(ptable))->pdata_t )), \
     101             :                                 (mm_ctx_array), (mm_ctx)); \
     102             :         } while (false)
     103             : 
     104             : /** @brief Free an LRU created by lru_create (it can be NULL). */
     105             : #define lru_free(table) \
     106             :         lru_free_impl(&(table)->lru)
     107             : 
     108             : /** @brief Reset an LRU to the empty state (but preserve any settings). */
     109             : #define lru_reset(table) \
     110             :         lru_reset_impl(&(table)->lru)
     111             : 
     112             : /**
     113             :  * @brief Find key in the LRU and return pointer to the corresponding value.
     114             :  *
     115             :  * @param table pointer to LRU
     116             :  * @param key_ lookup key
     117             :  * @param len_ key length
     118             :  * @return pointer to data or NULL if not found
     119             :  */
     120             : #define lru_get_try(table, key_, len_) \
     121             :         (__typeof__((table)->pdata_t)) \
     122             :                 lru_get_impl(&(table)->lru, (key_), (len_), -1, false, NULL)
     123             : 
     124             : /**
     125             :  * @brief Return pointer to value, inserting if needed (zeroed).
     126             :  *
     127             :  * @param table pointer to LRU
     128             :  * @param key_ lookup key
     129             :  * @param len_ key lengthkeys
     130             :  * @param is_new pointer to bool to store result of operation
     131             :  *             (true if entry is newly added, false otherwise; can be NULL).
     132             :  * @return pointer to data or NULL (can be even if memory could be allocated!)
     133             :  */
     134             : #define lru_get_new(table, key_, len_, is_new) \
     135             :         (__typeof__((table)->pdata_t)) \
     136             :                 lru_get_impl(&(table)->lru, (key_), (len_), \
     137             :                 sizeof(*(table)->pdata_t), true, is_new)
     138             : 
     139             : /**
     140             :  * @brief Apply a function to every item in LRU.
     141             :  *
     142             :  * @param table pointer to LRU
     143             :  * @param function enum lru_apply_do (*function)(const char *key, uint len, val_type *val, void *baton)
     144             :  *        See enum lru_apply_do for the return type meanings.
     145             :  * @param baton extra pointer passed to each function invocation
     146             :  */
     147             : #define lru_apply(table, function, baton) do { \
     148             :         lru_apply_fun_g(fun_dummy, __typeof__(*(table)->pdata_t)) = 0; \
     149             :         (void)(fun_dummy == (function)); /* produce a warning with incompatible function type */ \
     150             :         lru_apply_impl(&(table)->lru, (lru_apply_fun)(function), (baton)); \
     151             :         } while (false)
     152             : 
     153             : /** @brief Possible actions to do with an element. */
     154             : enum lru_apply_do {
     155             :         LRU_APPLY_DO_NOTHING,
     156             :         LRU_APPLY_DO_EVICT,
     157             :         /* maybe more in future*/
     158             : };
     159             : 
     160             : /**
     161             :  * @brief Return the real capacity - maximum number of keys holdable within.
     162             :  *
     163             :  * @param table pointer to LRU
     164             :  */
     165             : #define lru_capacity(table) lru_capacity_impl(&(table)->lru)
     166             : 
     167             : 
     168             : 
     169             : /* ======================== Inlined part of implementation ======================== */
     170             : /** @cond internal */
     171             : 
     172             : #define lru_apply_fun_g(name, val_type) \
     173             :         enum lru_apply_do (*(name))(const char *key, uint len, val_type *val, void *baton)
     174             : typedef lru_apply_fun_g(lru_apply_fun, void);
     175             : 
     176             : #if __GNUC__ >= 4
     177             :         #define CACHE_ALIGNED __attribute__((aligned(64)))
     178             : #else
     179             :         #define CACHE_ALIGNED
     180             : #endif
     181             : 
     182             : struct lru;
     183             : void lru_free_items_impl(struct lru *lru);
     184             : struct lru * lru_create_impl(uint max_slots, uint val_alignment,
     185             :                              knot_mm_t *mm_array, knot_mm_t *mm);
     186             : void * lru_get_impl(struct lru *lru, const char *key, uint key_len,
     187             :                     uint val_len, bool do_insert, bool *is_new);
     188             : void lru_apply_impl(struct lru *lru, lru_apply_fun f, void *baton);
     189             : 
     190             : struct lru_item;
     191             : 
     192             : #if SIZE_MAX > (1 << 32)
     193             :         /** @internal The number of keys stored within each group. */
     194             :         #define LRU_ASSOC 3
     195             : #else
     196             :         #define LRU_ASSOC 4
     197             : #endif
     198             : /** @internal The number of hashes tracked within each group: 10-1 or 12-1. */
     199             : #define LRU_TRACKED ((64 - sizeof(size_t) * LRU_ASSOC) / 4 - 1)
     200             : 
     201             : struct lru_group {
     202             :         uint16_t counts[LRU_TRACKED+1]; /*!< Occurrence counters; the last one is special. */
     203             :         uint16_t hashes[LRU_TRACKED+1]; /*!< Top halves of hashes; the last one is unused. */
     204             :         struct lru_item *items[LRU_ASSOC]; /*!< The full items. */
     205             : } CACHE_ALIGNED;
     206             : 
     207             : /* The sizes are chosen so lru_group just fits into a single x86 cache line. */
     208             : static_assert(64 == sizeof(struct lru_group)
     209             :                 && 64 == LRU_ASSOC * sizeof(void*) + (LRU_TRACKED+1) * 4,
     210             :                 "bad sizing for your sizeof(void*)");
     211             : 
     212             : struct lru {
     213             :         struct knot_mm *mm, /**< Memory context to use for keys. */
     214             :                 *mm_array; /**< Memory context to use for this structure itself. */
     215             :         uint log_groups; /**< Logarithm of the number of LRU groups. */
     216             :         uint val_alignment; /**< Alignment for the values. */
     217             :         struct lru_group groups[] CACHE_ALIGNED; /**< The groups of items. */
     218             : };
     219             : 
     220             : /** @internal See lru_free. */
     221          22 : static inline void lru_free_impl(struct lru *lru)
     222             : {
     223          22 :         if (!lru)
     224           0 :                 return;
     225          22 :         lru_free_items_impl(lru);
     226          22 :         mm_free(lru->mm_array, lru);
     227             : }
     228             : 
     229             : /** @internal See lru_reset. */
     230          12 : static inline void lru_reset_impl(struct lru *lru)
     231             : {
     232          12 :         lru_free_items_impl(lru);
     233          12 :         memset(lru->groups, 0, sizeof(lru->groups[0]) * (1 << lru->log_groups));
     234          12 : }
     235             : 
     236             : /** @internal See lru_capacity. */
     237             : static inline uint lru_capacity_impl(struct lru *lru)
     238             : {
     239             :         assert(lru);
     240             :         return (1 << lru->log_groups) * LRU_ASSOC;
     241             : }
     242             : 
     243             : /** @endcond */
     244             : /** @} (addtogroup generics) */

Generated by: LCOV version 1.13