All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
rlm_cache_rbtree.c
Go to the documentation of this file.
1 /*
2  * This program is is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 2 of the License, or (at
5  * your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software
14  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
15  */
16 
17 /**
18  * $Id: e6bb5fd790d07ef642206b534d093e4bfdadd73f $
19  * @file rlm_cache_rbtree.c
20  * @brief Simple rbtree based cache.
21  *
22  * @copyright 2014 The FreeRADIUS server project
23  */
24 #include <freeradius-devel/radiusd.h>
25 #include <freeradius-devel/heap.h>
26 #include <freeradius-devel/rad_assert.h>
27 #include "../../rlm_cache.h"
28 
29 #ifdef HAVE_PTHREAD_H
30 # define PTHREAD_MUTEX_LOCK pthread_mutex_lock
31 # define PTHREAD_MUTEX_UNLOCK pthread_mutex_unlock
32 #else
33 # define PTHREAD_MUTEX_LOCK(_x)
34 # define PTHREAD_MUTEX_UNLOCK(_x)
35 #endif
36 
37 typedef struct rlm_cache_rbtree {
38  rbtree_t *cache; //!< Tree for looking up cache keys.
39  fr_heap_t *heap; //!< For managing entry expiry.
40 
41 #ifdef HAVE_PTHREAD_H
42  pthread_mutex_t mutex; //!< Protect the tree from multiple readers/writers.
43 #endif
45 
46 typedef struct rlm_cache_rbtree_entry {
47  rlm_cache_entry_t fields; //!< Entry data.
48  size_t offset; //!< Offset used for heap.
50 
51 /** Compare two entries by key
52  *
53  * There may only be one entry with the same key.
54  */
55 static int cache_entry_cmp(void const *one, void const *two)
56 {
57  rlm_cache_entry_t const *a = one;
58  rlm_cache_entry_t const *b = two;
59 
60  if (a->key_len < b->key_len) return -1;
61  if (a->key_len > b->key_len) return +1;
62 
63  return memcmp(a->key, b->key, a->key_len);
64 }
65 
66 /** Compare two entries by expiry time
67  *
68  * There may be multiple entries with the same expiry time.
69  */
70 static int cache_heap_cmp(void const *one, void const *two)
71 {
72  rlm_cache_entry_t const *a = one;
73  rlm_cache_entry_t const *b = two;
74 
75  if (a->expires < b->expires) return -1;
76  if (a->expires > b->expires) return +1;
77 
78  return 0;
79 }
80 
81 /** Walk over the cache rbtree
82  *
83  * Used to free any entries left in the tree on detach.
84  *
85  * @param ctx unused.
86  * @param data to free.
87  * @return 2
88  */
89 static int _cache_entry_free(UNUSED void *ctx, void *data)
90 {
91  talloc_free(data);
92 
93  return 2;
94 }
95 
96 /** Cleanup a cache_rbtree instance
97  *
98  */
99 static int _mod_detach(rlm_cache_rbtree_t *driver)
100 {
101  if (driver->heap) fr_heap_delete(driver->heap);
102  if (driver->cache) {
104  rbtree_free(driver->cache);
105  }
106 
107 #ifdef HAVE_PTHREAD_H
108  pthread_mutex_destroy(&driver->mutex);
109 #endif
110  return 0;
111 }
112 
113 /** Create a new cache_rbtree instance
114  *
115  * @copydetails cache_instantiate_t
116  */
117 static int mod_instantiate(UNUSED CONF_SECTION *conf, UNUSED rlm_cache_config_t const *config, void *driver_inst)
118 {
119  rlm_cache_rbtree_t *driver = driver_inst;
120 
121  talloc_set_destructor(driver, _mod_detach);
122 
123  /*
124  * The cache.
125  */
126  driver->cache = rbtree_create(NULL, cache_entry_cmp, NULL, 0);
127  if (!driver->cache) {
128  ERROR("Failed to create cache");
129  return -1;
130  }
131  fr_talloc_link_ctx(driver, driver->cache);
132 
133  /*
134  * The heap of entries to expire.
135  */
136  driver->heap = fr_heap_create(cache_heap_cmp, offsetof(rlm_cache_rbtree_entry_t, offset));
137  if (!driver->heap) {
138  ERROR("Failed to create heap for the cache");
139  return -1;
140  }
141 
142 #ifdef HAVE_PTHREAD_H
143  if (pthread_mutex_init(&driver->mutex, NULL) < 0) {
144  ERROR("Failed initializing mutex: %s", fr_syserror(errno));
145  return -1;
146  }
147 #endif
148 
149  return 0;
150 }
151 
152 /** Custom allocation function for the driver
153  *
154  * Allows allocation of cache entry structures with additional fields.
155  *
156  * @copydetails cache_entry_alloc_t
157  */
158 static rlm_cache_entry_t *cache_entry_alloc(UNUSED rlm_cache_config_t const *config, UNUSED void *driver_inst,
159  REQUEST *request)
160 {
162 
163  c = talloc_zero(NULL, rlm_cache_rbtree_entry_t);
164  if (!c) {
165  RERROR("Failed allocating cache entry");
166  return NULL;
167  }
168 
169  return (rlm_cache_entry_t *)c;
170 }
171 
172 /** Locate a cache entry
173  *
174  * @note handle not used except for sanity checks.
175  *
176  * @copydetails cache_entry_find_t
177  */
179  UNUSED rlm_cache_config_t const *config, void *driver_inst,
180  REQUEST *request, void *handle, uint8_t const *key, size_t key_len)
181 {
182  rlm_cache_rbtree_t *driver = driver_inst;
183 
184  rlm_cache_entry_t *c, my_c;
185 
186  rad_assert(handle == request);
187 
188  /*
189  * Clear out old entries
190  */
191  c = fr_heap_peek(driver->heap);
192  if (c && (c->expires < request->timestamp.tv_sec)) {
193  fr_heap_extract(driver->heap, c);
194  rbtree_deletebydata(driver->cache, c);
195  talloc_free(c);
196  }
197 
198  /*
199  * Is there an entry for this key?
200  */
201  my_c.key = key;
202  my_c.key_len = key_len;
203  c = rbtree_finddata(driver->cache, &my_c);
204  if (!c) {
205  *out = NULL;
206  return CACHE_MISS;
207  }
208  *out = c;
209 
210  return CACHE_OK;
211 }
212 
213 /** Free an entry and remove it from the data store
214  *
215  * @note handle not used except for sanity checks.
216  *
217  * @copydetails cache_entry_expire_t
218  */
219 static cache_status_t cache_entry_expire(UNUSED rlm_cache_config_t const *config, void *driver_inst,
220  REQUEST *request, void *handle,
221  uint8_t const *key, size_t key_len)
222 {
223  rlm_cache_rbtree_t *driver = driver_inst;
224  rlm_cache_entry_t *c, my_c;
225 
226  rad_assert(handle == request);
227 
228  my_c.key = key;
229  my_c.key_len = key_len;
230  c = rbtree_finddata(driver->cache, &my_c);
231  if (!c) return CACHE_MISS;
232 
233  fr_heap_extract(driver->heap, c);
234  rbtree_deletebydata(driver->cache, c);
235  talloc_free(c);
236 
237  return CACHE_OK;
238 }
239 
240 /** Insert a new entry into the data store
241  *
242  * @note handle not used except for sanity checks.
243  *
244  * @copydetails cache_entry_insert_t
245  */
246 static cache_status_t cache_entry_insert(rlm_cache_config_t const *config, void *driver_inst,
247  REQUEST *request, void *handle,
248  rlm_cache_entry_t const *c)
249 {
250  cache_status_t status;
251 
252  rlm_cache_rbtree_t *driver = driver_inst;
253  rlm_cache_entry_t *my_c;
254 
255  rad_assert(handle == request);
256 
257  memcpy(&my_c, &c, sizeof(my_c));
258 
259  /*
260  * Allow overwriting
261  */
262  if (!rbtree_insert(driver->cache, my_c)) {
263  status = cache_entry_expire(config, driver_inst, request, handle, c->key, c->key_len);
264  if (status != CACHE_OK) rad_assert(0);
265 
266  if (!rbtree_insert(driver->cache, my_c)) {
267  RERROR("Failed adding entry");
268 
269  return CACHE_ERROR;
270  }
271  }
272 
273  if (!fr_heap_insert(driver->heap, my_c)) {
274  rbtree_deletebydata(driver->cache, my_c);
275  RERROR("Failed adding entry to expiry heap");
276 
277  return CACHE_ERROR;
278  }
279 
280  return CACHE_OK;
281 }
282 
283 /** Update the TTL of an entry
284  *
285  * @note handle not used except for sanity checks.
286  *
287  * @copydetails cache_entry_set_ttl_t
288  */
289 static cache_status_t cache_entry_set_ttl(UNUSED rlm_cache_config_t const *config, void *driver_inst,
290  REQUEST *request, UNUSED void *handle,
292 {
293  rlm_cache_rbtree_t *driver = driver_inst;
294  int ret;
295 
296  ret = fr_heap_extract(driver->heap, c);
297  rad_assert(ret == 1);
298  if (ret != 1) { /* Need this check if we're not building with asserts */
299  RERROR("Entry not in heap");
300  return CACHE_ERROR;
301  }
302 
303  if (!fr_heap_insert(driver->heap, c)) {
304  rbtree_deletebydata(driver->cache, c); /* make sure we don't leak entries... */
305  RERROR("Failed updating entry TTL. Entry was forcefully expired");
306  return CACHE_ERROR;
307  }
308  return CACHE_OK;
309 }
310 
311 /** Return the number of entries in the cache
312  *
313  * @note handle not used except for sanity checks.
314  *
315  * @copydetails cache_entry_count_t
316  */
317 static uint32_t cache_entry_count(UNUSED rlm_cache_config_t const *config, void *driver_inst,
318  REQUEST *request, void *handle)
319 {
320  rlm_cache_rbtree_t *driver = driver_inst;
321 
322  rad_assert(handle == request);
323 
324  return rbtree_num_elements(driver->cache);
325 }
326 
327 /** Lock the rbtree
328  *
329  * @note handle not used except for sanity checks.
330  *
331  * @copydetails cache_acquire_t
332  */
333 #ifdef HAVE_PTHREAD_H
334 static int cache_acquire(void **handle, UNUSED rlm_cache_config_t const *config, void *driver_inst,
335  REQUEST *request)
336 #else
337 static int cache_acquire(void **handle, UNUSED rlm_cache_config_t const *config, UNUSED void *driver_inst,
338  REQUEST *request)
339 #endif
340 {
341 #ifdef HAVE_PTHREAD_H
342  rlm_cache_rbtree_t *driver = driver_inst;
343 #endif
344 
345  PTHREAD_MUTEX_LOCK(&driver->mutex);
346 
347  *handle = request; /* handle is unused, this is just for sanity checking */
348 
349  RDEBUG3("Mutex acquired");
350 
351  return 0;
352 }
353 
354 /** Release an entry unlocking any mutexes
355  *
356  * @note handle not used except for sanity checks.
357  *
358  * @copydetails cache_release_t
359  */
360 #ifdef HAVE_PTHREAD_H
361 static void cache_release(UNUSED rlm_cache_config_t const *config, void *driver_inst, REQUEST *request,
362  rlm_cache_handle_t *handle)
363 #else
364 static void cache_release(UNUSED rlm_cache_config_t const *config, UNUSED void *driver_inst, REQUEST *request,
365  rlm_cache_handle_t *handle)
366 #endif
367 {
368 #ifdef HAVE_PTHREAD_H
369  rlm_cache_rbtree_t *driver = driver_inst;
370 #endif
371 
372  rad_assert(handle == request);
373 
374  PTHREAD_MUTEX_UNLOCK(&driver->mutex);
375 
376  RDEBUG3("Mutex released");
377 }
378 
380 cache_driver_t rlm_cache_rbtree = {
381  .name = "rlm_cache_rbtree",
382  .instantiate = mod_instantiate,
383  .inst_size = sizeof(rlm_cache_rbtree_t),
384  .alloc = cache_entry_alloc,
385 
386  .find = cache_entry_find,
387  .insert = cache_entry_insert,
388  .expire = cache_entry_expire,
389  .set_ttl = cache_entry_set_ttl,
390  .count = cache_entry_count,
391 
392  .acquire = cache_acquire,
393  .release = cache_release,
394 };
cache_driver_t rlm_cache_rbtree
Definition: rlm_cache.h:76
#define pthread_mutex_init(_x, _y)
Definition: rlm_eap.h:75
#define RERROR(fmt,...)
Definition: log.h:207
void rbtree_free(rbtree_t *tree)
Definition: rbtree.c:84
bool rbtree_deletebydata(rbtree_t *tree, void const *data)
Delete a node from the tree, based on given data, which MUST have come from rbtree_finddata().
Definition: rbtree.c:496
Fatal error.
Definition: rlm_cache.h:37
Cache entry notfound.
Definition: rlm_cache.h:39
static int cache_heap_cmp(void const *one, void const *two)
Compare two entries by expiry time.
#define UNUSED
Definition: libradius.h:134
static uint32_t cache_entry_count(UNUSED rlm_cache_config_t const *config, void *driver_inst, REQUEST *request, void *handle)
Return the number of entries in the cache.
void * rbtree_finddata(rbtree_t *tree, void const *data)
Find the user data.
Definition: rbtree.c:537
int fr_heap_extract(fr_heap_t *hp, void *data)
Definition: heap.c:147
cache_status_t
Definition: rlm_cache.h:35
void * fr_heap_peek(fr_heap_t *hp)
Definition: heap.c:207
size_t key_len
Length of key data.
Definition: rlm_cache.h:78
#define rad_assert(expr)
Definition: rad_assert.h:38
char const * fr_syserror(int num)
Guaranteed to be thread-safe version of strerror.
Definition: log.c:238
rbtree_t * cache
Tree for looking up cache keys.
int fr_heap_insert(fr_heap_t *hp, void *data)
Definition: heap.c:92
time_t expires
When the entry expires.
Definition: rlm_cache.h:81
rlm_cache_entry_t fields
Entry data.
static cache_status_t cache_entry_set_ttl(UNUSED rlm_cache_config_t const *config, void *driver_inst, REQUEST *request, UNUSED void *handle, rlm_cache_entry_t *c)
Update the TTL of an entry.
rbtree_t * rbtree_create(TALLOC_CTX *ctx, rb_comparator_t compare, rb_free_t node_free, int flags)
Create a new RED-BLACK tree.
Definition: rbtree.c:112
Definition: heap.c:16
void rlm_cache_handle_t
Definition: rlm_cache.h:31
int rbtree_walk(rbtree_t *tree, rb_order_t order, rb_walker_t compare, void *context)
Definition: rbtree.c:693
void fr_heap_delete(fr_heap_t *hp)
Definition: heap.c:36
static rlm_cache_entry_t * cache_entry_alloc(UNUSED rlm_cache_config_t const *config, UNUSED void *driver_inst, REQUEST *request)
Custom allocation function for the driver.
static void cache_release(UNUSED rlm_cache_config_t const *config, UNUSED void *driver_inst, REQUEST *request, rlm_cache_handle_t *handle)
Release an entry unlocking any mutexes.
#define PTHREAD_MUTEX_LOCK(_x)
static int _mod_detach(rlm_cache_rbtree_t *driver)
Cleanup a cache_rbtree instance.
static rs_t * conf
Definition: radsniff.c:46
static cache_status_t cache_entry_insert(rlm_cache_config_t const *config, void *driver_inst, REQUEST *request, void *handle, rlm_cache_entry_t const *c)
Insert a new entry into the data store.
fr_heap_t * heap
For managing entry expiry.
size_t offset
Offset used for heap.
uint8_t data[]
Definition: eap_pwd.h:625
static int cache_acquire(void **handle, UNUSED rlm_cache_config_t const *config, UNUSED void *driver_inst, REQUEST *request)
Lock the rbtree.
Cache entry found/updated.
Definition: rlm_cache.h:38
struct timeval timestamp
When we started processing the request.
Definition: radiusd.h:214
bool rbtree_insert(rbtree_t *tree, void *data)
Definition: rbtree.c:329
struct rlm_cache_rbtree_entry rlm_cache_rbtree_entry_t
static int mod_instantiate(UNUSED CONF_SECTION *conf, UNUSED rlm_cache_config_t const *config, void *driver_inst)
Create a new cache_rbtree instance.
int fr_talloc_link_ctx(TALLOC_CTX *parent, TALLOC_CTX *child)
Link a parent and a child context, so the child is freed before the parent.
Definition: misc.c:105
fr_heap_t * fr_heap_create(fr_heap_cmp_t cmp, size_t offset)
Definition: heap.c:44
static cache_status_t cache_entry_expire(UNUSED rlm_cache_config_t const *config, void *driver_inst, REQUEST *request, void *handle, uint8_t const *key, size_t key_len)
Free an entry and remove it from the data store.
struct rlm_cache_rbtree rlm_cache_rbtree_t
char const * name
Driver name.
Definition: rlm_cache.h:279
#define pthread_mutex_destroy(_x)
Definition: rlm_eap.h:76
uint8_t const * key
Key used to identify entry.
Definition: rlm_cache.h:77
static int cache_entry_cmp(void const *one, void const *two)
Compare two entries by key.
#define ERROR(fmt,...)
Definition: log.h:145
#define PTHREAD_MUTEX_UNLOCK(_x)
static cache_status_t cache_entry_find(rlm_cache_entry_t **out, UNUSED rlm_cache_config_t const *config, void *driver_inst, REQUEST *request, void *handle, uint8_t const *key, size_t key_len)
Locate a cache entry.
static int _cache_entry_free(UNUSED void *ctx, void *data)
Walk over the cache rbtree.
uint32_t rbtree_num_elements(rbtree_t *tree)
Definition: rbtree.c:727
#define RDEBUG3(fmt,...)
Definition: log.h:245
Configuration for the rlm_cache module.
Definition: rlm_cache.h:47