VNFs/DPPD-PROX/kv_store_expire.h

   1 /*
   2 // Copyright (c) 2010-2017 Intel Corporation
   3 //
   4 // Licensed under the Apache License, Version 2.0 (the "License");
   5 // you may not use this file except in compliance with the License.
   6 // You may obtain a copy of the License at
   7 //
   8 //     http://www.apache.org/licenses/LICENSE-2.0
   9 //
  10 // Unless required by applicable law or agreed to in writing, software
  11 // distributed under the License is distributed on an "AS IS" BASIS,
  12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13 // See the License for the specific language governing permissions and
  14 // limitations under the License.
  15 */
  16
  17 #include <rte_hash_crc.h>
  18 #include <stdint.h>
  19
  20 #include "prox_malloc.h"
  21
  22 #define KV_STORE_BUCKET_DEPTH 8
  23
  24 struct kv_store_expire_entry {
  25         /* if set to 0, the entry is disabled */
  26         uint64_t timeout;
  27         /* Memory contains the key, followed by the actual value. */
  28         uint8_t  mem[0];
  29 };
  30
  31 struct kv_store_expire {
  32         size_t key_size;
  33         size_t entry_size;
  34         size_t bucket_mask;
  35         size_t bucket_size;
  36         uint64_t timeout;
  37
  38         void (*expire)(void *entry_value);
  39
  40         uint8_t mem[0];
  41 };
  42
  43 static struct kv_store_expire *kv_store_expire_create(uint32_t n_entries, size_t key_size, size_t value_size, int socket, void (*expire)(void *entry_value), uint64_t timeout)
  44 {
  45         struct kv_store_expire *ret;
  46         size_t memsize = 0;
  47         size_t bucket_size;
  48         size_t entry_size;
  49
  50         if (!rte_is_power_of_2(n_entries))
  51                 n_entries = rte_align32pow2(n_entries);
  52         entry_size = sizeof(struct kv_store_expire_entry) + key_size + value_size;
  53
  54         memsize += sizeof(struct kv_store_expire);
  55         memsize += entry_size * n_entries;
  56
  57         ret = prox_zmalloc(memsize, socket);
  58         if (ret == NULL)
  59                 return NULL;
  60
  61         ret->bucket_mask = n_entries / KV_STORE_BUCKET_DEPTH - 1;
  62         ret->bucket_size = entry_size * KV_STORE_BUCKET_DEPTH;
  63         ret->entry_size = entry_size;
  64         ret->key_size = key_size;
  65         ret->expire = expire;
  66         ret->timeout = timeout;
  67
  68         return ret;
  69 }
  70
  71 static size_t kv_store_expire_size(struct kv_store_expire *kv_store)
  72 {
  73         return (kv_store->bucket_mask + 1) * KV_STORE_BUCKET_DEPTH;
  74 }
  75
  76 static void entry_set_timeout(struct kv_store_expire_entry *entry, uint64_t timeout)
  77 {
  78         entry->timeout = timeout;
  79 }
  80
  81 static struct kv_store_expire_entry *entry_next(struct kv_store_expire *kv_store, struct kv_store_expire_entry *entry)
  82 {
  83         return (struct kv_store_expire_entry *)((uint8_t *)entry + kv_store->entry_size);
  84 }
  85
  86 static void *entry_key(__attribute__((unused)) struct kv_store_expire *kv_store, struct kv_store_expire_entry *entry)
  87 {
  88         return (uint8_t *)entry->mem;
  89 }
  90
  91 static void *entry_value(struct kv_store_expire *kv_store, struct kv_store_expire_entry *entry)
  92 {
  93         return (uint8_t *)entry->mem + kv_store->key_size;
  94 }
  95
  96 static struct kv_store_expire_entry *kv_store_expire_get_first(struct kv_store_expire *kv_store)
  97 {
  98         return (struct kv_store_expire_entry *)&kv_store->mem[0];
  99 }
 100
 101 static struct kv_store_expire_entry *kv_store_expire_get_first_in_bucket(struct kv_store_expire *kv_store, void *key)
 102 {
 103         uint32_t key_hash = rte_hash_crc(key, kv_store->key_size, 0);
 104         uint32_t bucket_idx = key_hash & kv_store->bucket_mask;
 105
 106         return (struct kv_store_expire_entry *)&kv_store->mem[bucket_idx * kv_store->bucket_size];
 107 }
 108
 109 static int entry_key_matches(struct kv_store_expire *kv_store, struct kv_store_expire_entry *entry, void *key)
 110 {
 111         return !memcmp(entry_key(kv_store, entry), key, kv_store->key_size);
 112 }
 113
 114 static struct kv_store_expire_entry *kv_store_expire_get(struct kv_store_expire *kv_store, void *key, uint64_t now)
 115 {
 116         struct kv_store_expire_entry *entry = kv_store_expire_get_first_in_bucket(kv_store, key);
 117
 118         for (int i = 0; i < KV_STORE_BUCKET_DEPTH; ++i) {
 119                 if (entry->timeout && entry->timeout >= now) {
 120                         if (entry_key_matches(kv_store, entry, key)) {
 121                                 entry->timeout = now + kv_store->timeout;
 122                                 return entry;
 123                         }
 124                 }
 125                 entry = entry_next(kv_store, entry);
 126         }
 127         return NULL;
 128 }
 129
 130 static struct kv_store_expire_entry *kv_store_expire_put(struct kv_store_expire *kv_store, void *key, uint64_t now)
 131 {
 132         struct kv_store_expire_entry *e = kv_store_expire_get_first_in_bucket(kv_store, key);
 133
 134         for (int i = 0; i < KV_STORE_BUCKET_DEPTH; ++i) {
 135                 if (e->timeout && e->timeout >= now) {
 136                         e = entry_next(kv_store, e);
 137                         continue;
 138                 }
 139                 if (!e->timeout) {
 140                         kv_store->expire(entry_value(kv_store, e));
 141                 }
 142
 143                 rte_memcpy(entry_key(kv_store, e), key, kv_store->key_size);
 144                 e->timeout = now + kv_store->timeout;
 145                 return e;
 146         }
 147
 148         return NULL;
 149 }
 150
 151 /* If the entry is not found, a put operation is tried and if that
 152    succeeds, that entry is returned. The bucket is full if NULL Is
 153    returned. */
 154 static struct kv_store_expire_entry *kv_store_expire_get_or_put(struct kv_store_expire *kv_store, void *key, uint64_t now)
 155 {
 156         struct kv_store_expire_entry *entry = kv_store_expire_get_first_in_bucket(kv_store, key);
 157         struct kv_store_expire_entry *v = NULL;
 158
 159         for (int i = 0; i < KV_STORE_BUCKET_DEPTH; ++i) {
 160                 if (entry->timeout && entry->timeout >= now) {
 161                         if (entry_key_matches(kv_store, entry, key)) {
 162                                 entry->timeout = now + kv_store->timeout;
 163                                 return entry;
 164                         }
 165                 }
 166                 else {
 167                         v = v? v : entry;
 168                 }
 169                 entry = entry_next(kv_store, entry);
 170         }
 171
 172         if (v) {
 173                 if (entry->timeout)
 174                         kv_store->expire(entry_value(kv_store, v));
 175                 rte_memcpy(entry_key(kv_store, v), key, kv_store->key_size);
 176                 v->timeout = now + kv_store->timeout;
 177                 return v;
 178         }
 179
 180         return NULL;
 181 }
 182
 183 static size_t kv_store_expire_expire_all(struct kv_store_expire *kv_store)
 184 {
 185         struct kv_store_expire_entry *entry = kv_store_expire_get_first(kv_store);
 186         size_t elems = kv_store_expire_size(kv_store);
 187         size_t expired = 0;
 188
 189         do {
 190                 if (entry->timeout) {
 191                         kv_store->expire(entry_value(kv_store, entry));
 192                         entry->timeout = 0;
 193                         expired++;
 194                 }
 195                 entry = entry_next(kv_store, entry);
 196         } while (--elems);
 197         return expired;
 198 }