1 /*
2 * cache-inprocess.c: in-memory caching for Subversion
3 *
4 * ====================================================================
5 * Licensed to the Apache Software Foundation (ASF) under one
6 * or more contributor license agreements. See the NOTICE file
7 * distributed with this work for additional information
8 * regarding copyright ownership. The ASF licenses this file
9 * to you under the Apache License, Version 2.0 (the
10 * "License"); you may not use this file except in compliance
11 * with the License. You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing,
16 * software distributed under the License is distributed on an
17 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
18 * KIND, either express or implied. See the License for the
19 * specific language governing permissions and limitations
20 * under the License.
21 * ====================================================================
22 */
23
24 #include <assert.h>
25
26 #include "svn_pools.h"
27
28 #include "svn_private_config.h"
29
30 #include "cache.h"
31 #include "private/svn_mutex.h"
32
33 /* The (internal) cache object. */
34 typedef struct inprocess_cache_t {
35 /* A user-defined identifier for this cache instance. */
36 const char *id;
37
38 /* HASH maps a key (of size KLEN) to a struct cache_entry. */
39 apr_hash_t *hash;
40 apr_ssize_t klen;
41
42 /* Used to copy values into the cache. */
43 svn_cache__serialize_func_t serialize_func;
44
45 /* Used to copy values out of the cache. */
46 svn_cache__deserialize_func_t deserialize_func;
47
48 /* Maximum number of pages that this cache instance may allocate */
49 apr_uint64_t total_pages;
50 /* The number of pages we're allowed to allocate before having to
51 * try to reuse one. */
52 apr_uint64_t unallocated_pages;
53 /* Number of cache entries stored on each page. Must be at least 1. */
54 apr_uint64_t items_per_page;
55
56 /* A dummy cache_page serving as the head of a circular doubly
57 * linked list of cache_pages. SENTINEL->NEXT is the most recently
58 * used page, and SENTINEL->PREV is the least recently used page.
59 * All pages in this list are "full"; the page currently being
60 * filled (PARTIAL_PAGE) is not in the list. */
61 struct cache_page *sentinel;
62
63 /* A page currently being filled with entries, or NULL if there's no
64 * partially-filled page. This page is not in SENTINEL's list. */
65 struct cache_page *partial_page;
66 /* If PARTIAL_PAGE is not null, this is the number of entries
67 * currently on PARTIAL_PAGE. */
68 apr_uint64_t partial_page_number_filled;
69
70 /* The pool that the svn_cache__t itself, HASH, and all pages are
71 * allocated in; subpools of this pool are used for the cache_entry
72 * structs, as well as the dup'd values and hash keys.
73 */
74 apr_pool_t *cache_pool;
75
76 /* Sum of the SIZE members of all cache_entry elements that are
77 * accessible from HASH. This is used to make statistics available
78 * even if the sub-pools have already been destroyed.
79 */
80 apr_size_t data_size;
81
82 /* A lock for intra-process synchronization to the cache, or NULL if
83 * the cache's creator doesn't feel the cache needs to be
84 * thread-safe. */
85 svn_mutex__t *mutex;
86 } inprocess_cache_t;
87
88 /* A cache page; all items on the page are allocated from the same
89 * pool. */
90 struct cache_page {
91 /* Pointers for the LRU list anchored at the cache's SENTINEL.
92 * (NULL for the PARTIAL_PAGE.) */
93 struct cache_page *prev;
94 struct cache_page *next;
95
96 /* The pool in which cache_entry structs, hash keys, and dup'd
97 * values are allocated. The CACHE_PAGE structs are allocated
98 * in CACHE_POOL and have the same lifetime as the cache itself.
99 * (The cache will never allocate more than TOTAL_PAGES page
100 * structs (inclusive of the sentinel) from CACHE_POOL.)
101 */
102 apr_pool_t *page_pool;
103
104 /* A singly linked list of the entries on this page; used to remove
105 * them from the cache's HASH before reusing the page. */
106 struct cache_entry *first_entry;
107 };
108
109 /* An cache entry. */
110 struct cache_entry {
111 const void *key;
112
113 /* serialized value */
114 void *value;
115
116 /* length of the serialized value in bytes */
117 apr_size_t size;
118
119 /* The page it's on (needed so that the LRU list can be
120 * maintained). */
121 struct cache_page *page;
122
123 /* Next entry on the page. */
124 struct cache_entry *next_entry;
125 };
126
127
128 /* Removes PAGE from the doubly-linked list it is in (leaving its PREV
129 * and NEXT fields undefined). */
130 static void
remove_page_from_list(struct cache_page * page)131 remove_page_from_list(struct cache_page *page)
132 {
133 page->prev->next = page->next;
134 page->next->prev = page->prev;
135 }
136
137 /* Inserts PAGE after CACHE's sentinel. */
138 static void
insert_page(inprocess_cache_t * cache,struct cache_page * page)139 insert_page(inprocess_cache_t *cache,
140 struct cache_page *page)
141 {
142 struct cache_page *pred = cache->sentinel;
143
144 page->prev = pred;
145 page->next = pred->next;
146 page->prev->next = page;
147 page->next->prev = page;
148 }
149
150 /* If PAGE is in the circularly linked list (eg, its NEXT isn't NULL),
151 * move it to the front of the list. */
152 static svn_error_t *
move_page_to_front(inprocess_cache_t * cache,struct cache_page * page)153 move_page_to_front(inprocess_cache_t *cache,
154 struct cache_page *page)
155 {
156 /* This function is called whilst CACHE is locked. */
157
158 SVN_ERR_ASSERT(page != cache->sentinel);
159
160 if (! page->next)
161 return SVN_NO_ERROR;
162
163 remove_page_from_list(page);
164 insert_page(cache, page);
165
166 return SVN_NO_ERROR;
167 }
168
169 /* Return a copy of KEY inside POOL, using CACHE->KLEN to figure out
170 * how. */
171 static const void *
duplicate_key(inprocess_cache_t * cache,const void * key,apr_pool_t * pool)172 duplicate_key(inprocess_cache_t *cache,
173 const void *key,
174 apr_pool_t *pool)
175 {
176 if (cache->klen == APR_HASH_KEY_STRING)
177 return apr_pstrdup(pool, key);
178 else
179 return apr_pmemdup(pool, key, cache->klen);
180 }
181
182 static svn_error_t *
inprocess_cache_get_internal(char ** buffer,apr_size_t * size,inprocess_cache_t * cache,const void * key,apr_pool_t * result_pool)183 inprocess_cache_get_internal(char **buffer,
184 apr_size_t *size,
185 inprocess_cache_t *cache,
186 const void *key,
187 apr_pool_t *result_pool)
188 {
189 struct cache_entry *entry = apr_hash_get(cache->hash, key, cache->klen);
190
191 if (entry)
192 {
193 SVN_ERR(move_page_to_front(cache, entry->page));
194
195 /* duplicate the buffer entry */
196 *buffer = apr_palloc(result_pool, entry->size);
197 if (entry->size)
198 memcpy(*buffer, entry->value, entry->size);
199
200 *size = entry->size;
201 }
202 else
203 {
204 *buffer = NULL;
205 *size = 0;
206 }
207
208 return SVN_NO_ERROR;
209 }
210
211 static svn_error_t *
inprocess_cache_get(void ** value_p,svn_boolean_t * found,void * cache_void,const void * key,apr_pool_t * result_pool)212 inprocess_cache_get(void **value_p,
213 svn_boolean_t *found,
214 void *cache_void,
215 const void *key,
216 apr_pool_t *result_pool)
217 {
218 inprocess_cache_t *cache = cache_void;
219
220 if (key)
221 {
222 char* buffer;
223 apr_size_t size;
224
225 SVN_MUTEX__WITH_LOCK(cache->mutex,
226 inprocess_cache_get_internal(&buffer,
227 &size,
228 cache,
229 key,
230 result_pool));
231 /* deserialize the buffer content. Usually, this will directly
232 modify the buffer content directly. */
233 *found = (buffer != NULL);
234 if (!buffer || !size)
235 *value_p = NULL;
236 else
237 return cache->deserialize_func(value_p, buffer, size, result_pool);
238 }
239 else
240 {
241 *value_p = NULL;
242 *found = FALSE;
243 }
244
245 return SVN_NO_ERROR;
246 }
247
248 static svn_error_t *
inprocess_cache_has_key_internal(svn_boolean_t * found,inprocess_cache_t * cache,const void * key,apr_pool_t * scratch_pool)249 inprocess_cache_has_key_internal(svn_boolean_t *found,
250 inprocess_cache_t *cache,
251 const void *key,
252 apr_pool_t *scratch_pool)
253 {
254 *found = apr_hash_get(cache->hash, key, cache->klen) != NULL;
255
256 return SVN_NO_ERROR;
257 }
258
259 static svn_error_t *
inprocess_cache_has_key(svn_boolean_t * found,void * cache_void,const void * key,apr_pool_t * scratch_pool)260 inprocess_cache_has_key(svn_boolean_t *found,
261 void *cache_void,
262 const void *key,
263 apr_pool_t *scratch_pool)
264 {
265 inprocess_cache_t *cache = cache_void;
266
267 if (key)
268 SVN_MUTEX__WITH_LOCK(cache->mutex,
269 inprocess_cache_has_key_internal(found,
270 cache,
271 key,
272 scratch_pool));
273 else
274 *found = FALSE;
275
276 return SVN_NO_ERROR;
277 }
278
279 /* Removes PAGE from the LRU list, removes all of its entries from
280 * CACHE's hash, clears its pool, and sets its entry pointer to NULL.
281 * Finally, puts it in the "partial page" slot in the cache and sets
282 * partial_page_number_filled to 0. Must be called on a page actually
283 * in the list. */
284 static void
erase_page(inprocess_cache_t * cache,struct cache_page * page)285 erase_page(inprocess_cache_t *cache,
286 struct cache_page *page)
287 {
288 struct cache_entry *e;
289
290 remove_page_from_list(page);
291
292 for (e = page->first_entry;
293 e;
294 e = e->next_entry)
295 {
296 cache->data_size -= e->size;
297 apr_hash_set(cache->hash, e->key, cache->klen, NULL);
298 }
299
300 svn_pool_clear(page->page_pool);
301
302 page->first_entry = NULL;
303 page->prev = NULL;
304 page->next = NULL;
305
306 cache->partial_page = page;
307 cache->partial_page_number_filled = 0;
308 }
309
310
311 static svn_error_t *
inprocess_cache_set_internal(inprocess_cache_t * cache,const void * key,void * value,apr_pool_t * scratch_pool)312 inprocess_cache_set_internal(inprocess_cache_t *cache,
313 const void *key,
314 void *value,
315 apr_pool_t *scratch_pool)
316 {
317 struct cache_entry *existing_entry;
318
319 existing_entry = apr_hash_get(cache->hash, key, cache->klen);
320
321 /* Is it already here, but we can do the one-item-per-page
322 * optimization? */
323 if (existing_entry && cache->items_per_page == 1)
324 {
325 /* Special case! ENTRY is the *only* entry on this page, so
326 * why not wipe it (so as not to leak the previous value).
327 */
328 struct cache_page *page = existing_entry->page;
329
330 /* This can't be the partial page: items_per_page == 1
331 * *never* has a partial page (except for in the temporary state
332 * that we're about to fake). */
333 SVN_ERR_ASSERT(page->next != NULL);
334 SVN_ERR_ASSERT(cache->partial_page == NULL);
335
336 erase_page(cache, page);
337 existing_entry = NULL;
338 }
339
340 /* Is it already here, and we just have to leak the old value? */
341 if (existing_entry)
342 {
343 struct cache_page *page = existing_entry->page;
344
345 SVN_ERR(move_page_to_front(cache, page));
346 cache->data_size -= existing_entry->size;
347 if (value)
348 {
349 SVN_ERR(cache->serialize_func(&existing_entry->value,
350 &existing_entry->size,
351 value,
352 page->page_pool));
353 cache->data_size += existing_entry->size;
354 if (existing_entry->size == 0)
355 existing_entry->value = NULL;
356 }
357 else
358 {
359 existing_entry->value = NULL;
360 existing_entry->size = 0;
361 }
362
363 return SVN_NO_ERROR;
364 }
365
366 /* Do we not have a partial page to put it on, but we are allowed to
367 * allocate more? */
368 if (cache->partial_page == NULL && cache->unallocated_pages > 0)
369 {
370 cache->partial_page = apr_pcalloc(cache->cache_pool,
371 sizeof(*(cache->partial_page)));
372 cache->partial_page->page_pool = svn_pool_create(cache->cache_pool);
373 cache->partial_page_number_filled = 0;
374 (cache->unallocated_pages)--;
375 }
376
377 /* Do we really not have a partial page to put it on, even after the
378 * one-item-per-page optimization and checking the unallocated page
379 * count? */
380 if (cache->partial_page == NULL)
381 {
382 struct cache_page *oldest_page = cache->sentinel->prev;
383
384 SVN_ERR_ASSERT(oldest_page != cache->sentinel);
385
386 /* Erase the page and put it in cache->partial_page. */
387 erase_page(cache, oldest_page);
388 }
389
390 SVN_ERR_ASSERT(cache->partial_page != NULL);
391
392 {
393 struct cache_page *page = cache->partial_page;
394 struct cache_entry *new_entry = apr_pcalloc(page->page_pool,
395 sizeof(*new_entry));
396
397 /* Copy the key and value into the page's pool. */
398 new_entry->key = duplicate_key(cache, key, page->page_pool);
399 if (value)
400 {
401 SVN_ERR(cache->serialize_func(&new_entry->value,
402 &new_entry->size,
403 value,
404 page->page_pool));
405 cache->data_size += new_entry->size;
406 if (new_entry->size == 0)
407 new_entry->value = NULL;
408 }
409 else
410 {
411 new_entry->value = NULL;
412 new_entry->size = 0;
413 }
414
415 /* Add the entry to the page's list. */
416 new_entry->page = page;
417 new_entry->next_entry = page->first_entry;
418 page->first_entry = new_entry;
419
420 /* Add the entry to the hash, using the *entry's* copy of the
421 * key. */
422 apr_hash_set(cache->hash, new_entry->key, cache->klen, new_entry);
423
424 /* We've added something else to the partial page. */
425 (cache->partial_page_number_filled)++;
426
427 /* Is it full? */
428 if (cache->partial_page_number_filled >= cache->items_per_page)
429 {
430 insert_page(cache, page);
431 cache->partial_page = NULL;
432 }
433 }
434
435 return SVN_NO_ERROR;
436 }
437
438 static svn_error_t *
inprocess_cache_set(void * cache_void,const void * key,void * value,apr_pool_t * scratch_pool)439 inprocess_cache_set(void *cache_void,
440 const void *key,
441 void *value,
442 apr_pool_t *scratch_pool)
443 {
444 inprocess_cache_t *cache = cache_void;
445
446 if (key)
447 SVN_MUTEX__WITH_LOCK(cache->mutex,
448 inprocess_cache_set_internal(cache,
449 key,
450 value,
451 scratch_pool));
452
453 return SVN_NO_ERROR;
454 }
455
456 /* Baton type for svn_cache__iter. */
457 struct cache_iter_baton {
458 svn_iter_apr_hash_cb_t user_cb;
459 void *user_baton;
460 };
461
462 /* Call the user's callback with the actual value, not the
463 cache_entry. Implements the svn_iter_apr_hash_cb_t
464 prototype. */
465 static svn_error_t *
iter_cb(void * baton,const void * key,apr_ssize_t klen,void * val,apr_pool_t * pool)466 iter_cb(void *baton,
467 const void *key,
468 apr_ssize_t klen,
469 void *val,
470 apr_pool_t *pool)
471 {
472 struct cache_iter_baton *b = baton;
473 struct cache_entry *entry = val;
474 return (b->user_cb)(b->user_baton, key, klen, entry->value, pool);
475 }
476
477 static svn_error_t *
inprocess_cache_iter(svn_boolean_t * completed,void * cache_void,svn_iter_apr_hash_cb_t user_cb,void * user_baton,apr_pool_t * scratch_pool)478 inprocess_cache_iter(svn_boolean_t *completed,
479 void *cache_void,
480 svn_iter_apr_hash_cb_t user_cb,
481 void *user_baton,
482 apr_pool_t *scratch_pool)
483 {
484 inprocess_cache_t *cache = cache_void;
485 struct cache_iter_baton b;
486 b.user_cb = user_cb;
487 b.user_baton = user_baton;
488
489 SVN_MUTEX__WITH_LOCK(cache->mutex,
490 svn_iter_apr_hash(completed, cache->hash,
491 iter_cb, &b, scratch_pool));
492
493 return SVN_NO_ERROR;
494 }
495
496 static svn_error_t *
inprocess_cache_get_partial_internal(void ** value_p,svn_boolean_t * found,inprocess_cache_t * cache,const void * key,svn_cache__partial_getter_func_t func,void * baton,apr_pool_t * result_pool)497 inprocess_cache_get_partial_internal(void **value_p,
498 svn_boolean_t *found,
499 inprocess_cache_t *cache,
500 const void *key,
501 svn_cache__partial_getter_func_t func,
502 void *baton,
503 apr_pool_t *result_pool)
504 {
505 struct cache_entry *entry = apr_hash_get(cache->hash, key, cache->klen);
506 if (! entry)
507 {
508 *found = FALSE;
509 return SVN_NO_ERROR;
510 }
511
512 SVN_ERR(move_page_to_front(cache, entry->page));
513
514 *found = TRUE;
515 return func(value_p, entry->value, entry->size, baton, result_pool);
516 }
517
518 static svn_error_t *
inprocess_cache_get_partial(void ** value_p,svn_boolean_t * found,void * cache_void,const void * key,svn_cache__partial_getter_func_t func,void * baton,apr_pool_t * result_pool)519 inprocess_cache_get_partial(void **value_p,
520 svn_boolean_t *found,
521 void *cache_void,
522 const void *key,
523 svn_cache__partial_getter_func_t func,
524 void *baton,
525 apr_pool_t *result_pool)
526 {
527 inprocess_cache_t *cache = cache_void;
528
529 if (key)
530 SVN_MUTEX__WITH_LOCK(cache->mutex,
531 inprocess_cache_get_partial_internal(value_p,
532 found,
533 cache,
534 key,
535 func,
536 baton,
537 result_pool));
538 else
539 *found = FALSE;
540
541 return SVN_NO_ERROR;
542 }
543
544 static svn_error_t *
inprocess_cache_set_partial_internal(inprocess_cache_t * cache,const void * key,svn_cache__partial_setter_func_t func,void * baton,apr_pool_t * scratch_pool)545 inprocess_cache_set_partial_internal(inprocess_cache_t *cache,
546 const void *key,
547 svn_cache__partial_setter_func_t func,
548 void *baton,
549 apr_pool_t *scratch_pool)
550 {
551 struct cache_entry *entry = apr_hash_get(cache->hash, key, cache->klen);
552 if (entry)
553 {
554 SVN_ERR(move_page_to_front(cache, entry->page));
555
556 cache->data_size -= entry->size;
557 SVN_ERR(func(&entry->value,
558 &entry->size,
559 baton,
560 entry->page->page_pool));
561 cache->data_size += entry->size;
562 }
563
564 return SVN_NO_ERROR;
565 }
566
567 static svn_error_t *
inprocess_cache_set_partial(void * cache_void,const void * key,svn_cache__partial_setter_func_t func,void * baton,apr_pool_t * scratch_pool)568 inprocess_cache_set_partial(void *cache_void,
569 const void *key,
570 svn_cache__partial_setter_func_t func,
571 void *baton,
572 apr_pool_t *scratch_pool)
573 {
574 inprocess_cache_t *cache = cache_void;
575
576 if (key)
577 SVN_MUTEX__WITH_LOCK(cache->mutex,
578 inprocess_cache_set_partial_internal(cache,
579 key,
580 func,
581 baton,
582 scratch_pool));
583
584 return SVN_NO_ERROR;
585 }
586
587 static svn_boolean_t
inprocess_cache_is_cachable(void * cache_void,apr_size_t size)588 inprocess_cache_is_cachable(void *cache_void, apr_size_t size)
589 {
590 /* Be relatively strict: per page we should not allocate more than
591 * we could spare as "unused" memory.
592 * But in most cases, nobody will ask anyway. And in no case, this
593 * will be used for checks _inside_ the cache code.
594 */
595 inprocess_cache_t *cache = cache_void;
596 return size < SVN_ALLOCATOR_RECOMMENDED_MAX_FREE / cache->items_per_page;
597 }
598
599 static svn_error_t *
inprocess_cache_get_info_internal(inprocess_cache_t * cache,svn_cache__info_t * info,apr_pool_t * result_pool)600 inprocess_cache_get_info_internal(inprocess_cache_t *cache,
601 svn_cache__info_t *info,
602 apr_pool_t *result_pool)
603 {
604 info->id = apr_pstrdup(result_pool, cache->id);
605
606 info->used_entries = apr_hash_count(cache->hash);
607 info->total_entries = cache->items_per_page * cache->total_pages;
608
609 info->used_size = cache->data_size;
610 info->data_size = cache->data_size;
611 info->total_size = cache->data_size
612 + cache->items_per_page * sizeof(struct cache_page)
613 + info->used_entries * sizeof(struct cache_entry);
614
615 return SVN_NO_ERROR;
616 }
617
618
619 static svn_error_t *
inprocess_cache_get_info(void * cache_void,svn_cache__info_t * info,svn_boolean_t reset,apr_pool_t * result_pool)620 inprocess_cache_get_info(void *cache_void,
621 svn_cache__info_t *info,
622 svn_boolean_t reset,
623 apr_pool_t *result_pool)
624 {
625 inprocess_cache_t *cache = cache_void;
626
627 SVN_MUTEX__WITH_LOCK(cache->mutex,
628 inprocess_cache_get_info_internal(cache,
629 info,
630 result_pool));
631
632 return SVN_NO_ERROR;
633 }
634
635 static svn_cache__vtable_t inprocess_cache_vtable = {
636 inprocess_cache_get,
637 inprocess_cache_has_key,
638 inprocess_cache_set,
639 inprocess_cache_iter,
640 inprocess_cache_is_cachable,
641 inprocess_cache_get_partial,
642 inprocess_cache_set_partial,
643 inprocess_cache_get_info
644 };
645
646 svn_error_t *
svn_cache__create_inprocess(svn_cache__t ** cache_p,svn_cache__serialize_func_t serialize,svn_cache__deserialize_func_t deserialize,apr_ssize_t klen,apr_int64_t pages,apr_int64_t items_per_page,svn_boolean_t thread_safe,const char * id,apr_pool_t * pool)647 svn_cache__create_inprocess(svn_cache__t **cache_p,
648 svn_cache__serialize_func_t serialize,
649 svn_cache__deserialize_func_t deserialize,
650 apr_ssize_t klen,
651 apr_int64_t pages,
652 apr_int64_t items_per_page,
653 svn_boolean_t thread_safe,
654 const char *id,
655 apr_pool_t *pool)
656 {
657 svn_cache__t *wrapper = apr_pcalloc(pool, sizeof(*wrapper));
658 inprocess_cache_t *cache = apr_pcalloc(pool, sizeof(*cache));
659
660 cache->id = apr_pstrdup(pool, id);
661
662 SVN_ERR_ASSERT(klen == APR_HASH_KEY_STRING || klen >= 1);
663
664 cache->hash = apr_hash_make(pool);
665 cache->klen = klen;
666
667 cache->serialize_func = serialize;
668 cache->deserialize_func = deserialize;
669
670 SVN_ERR_ASSERT(pages >= 1);
671 cache->total_pages = pages;
672 cache->unallocated_pages = pages;
673 SVN_ERR_ASSERT(items_per_page >= 1);
674 cache->items_per_page = items_per_page;
675
676 cache->sentinel = apr_pcalloc(pool, sizeof(*(cache->sentinel)));
677 cache->sentinel->prev = cache->sentinel;
678 cache->sentinel->next = cache->sentinel;
679 /* The sentinel doesn't need a pool. (We're happy to crash if we
680 * accidentally try to treat it like a real page.) */
681
682 SVN_ERR(svn_mutex__init(&cache->mutex, thread_safe, pool));
683
684 cache->cache_pool = pool;
685
686 wrapper->vtable = &inprocess_cache_vtable;
687 wrapper->cache_internal = cache;
688 wrapper->pretend_empty = !!getenv("SVN_X_DOES_NOT_MARK_THE_SPOT");
689
690 *cache_p = wrapper;
691 return SVN_NO_ERROR;
692 }
693