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