"Fossies" - the Fresh Open Source Software Archive

Member "haproxy-1.9.8/include/import/lru.h" (13 May 2019, 3759 Bytes) of package /linux/misc/haproxy-1.9.8.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "lru.h" see the Fossies "Dox" file reference documentation.

    1 /*
    2  * Copyright (C) 2015 Willy Tarreau <w@1wt.eu>
    3  *
    4  * Permission is hereby granted, free of charge, to any person obtaining
    5  * a copy of this software and associated documentation files (the
    6  * "Software"), to deal in the Software without restriction, including
    7  * without limitation the rights to use, copy, modify, merge, publish,
    8  * distribute, sublicense, and/or sell copies of the Software, and to
    9  * permit persons to whom the Software is furnished to do so, subject to
   10  * the following conditions:
   11  *
   12  * The above copyright notice and this permission notice shall be
   13  * included in all copies or substantial portions of the Software.
   14  *
   15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
   16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
   17  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
   18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
   19  * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
   20  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
   21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
   22  * OTHER DEALINGS IN THE SOFTWARE.
   23  */
   24 
   25 #include <eb64tree.h>
   26 
   27 /* The LRU supports a global cache shared between multiple domains and multiple
   28  * versions of their datasets. The purpose is not to have to flush the whole
   29  * LRU once a key is updated and not valid anymore (eg: ACL files), as well as
   30  * to reliably support concurrent accesses and handle conflicts gracefully. For
   31  * each key a pointer to a dataset and its internal data revision are stored.
   32  * All lookups verify that these elements match those passed by the caller and
   33  * only return a valid entry upon matching. Otherwise the entry is either
   34  * allocated or recycled and considered new. New entries are always initialized
   35  * with a NULL domain pointer which is used by the caller to detect that the
   36  * entry is new and must be populated. Such entries never expire and are
   37  * protected from the risk of being recycled. It's then the caller's
   38  * responsibility to perform the operation and commit the entry with its latest
   39  * result. This domain thus serves as a lock to protect the entry during all
   40  * the computation needed to update it. In a simple use case where the cache is
   41  * dedicated, it is recommended to pass the LRU head as the domain pointer and
   42  * for example zero as the revision. The most common use case for the caller
   43  * consists in simply checking that the return is not null and that the domain
   44  * is not null, then to use the result. The get() function returns null if it
   45  * cannot allocate a node (memory or key being currently updated).
   46  */
   47 struct lru64_list {
   48     struct lru64_list *n;
   49     struct lru64_list *p;
   50 };
   51 
   52 struct lru64_head {
   53     struct lru64_list list;
   54     struct eb_root keys;
   55     struct lru64  *spare;
   56     int cache_size;
   57     int cache_usage;
   58 };
   59 
   60 struct lru64 {
   61     struct eb64_node node;        /* indexing key, typically a hash64 */
   62     struct lru64_list lru;        /* LRU list */
   63     void *domain;                 /* who this data belongs to */
   64     unsigned long long revision;  /* data revision (to avoid use-after-free) */
   65     void *data;                   /* returned value, user decides how to use this */
   66     void (*free)(void *data);     /* function to release data, if needed */
   67 };
   68 
   69 
   70 struct lru64 *lru64_lookup(unsigned long long key, struct lru64_head *lru, void *domain, unsigned long long revision);
   71 struct lru64 *lru64_get(unsigned long long key, struct lru64_head *lru, void *domain, unsigned long long revision);
   72 void lru64_commit(struct lru64 *elem, void *data, void *domain, unsigned long long revision, void (*free)(void *));
   73 struct lru64_head *lru64_new(int size);
   74 int lru64_destroy(struct lru64_head *lru);
   75 void lru64_kill_oldest(struct lru64_head *lru, unsigned long int nb);