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. */
34typedef 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. */
90struct 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. */
110struct 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). */
130static void
131remove_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. */
138static void
139insert_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. */
152static svn_error_t *
153move_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. */
171static const void *
172duplicate_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
182static svn_error_t *
183inprocess_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
211static svn_error_t *
212inprocess_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
248static svn_error_t *
249inprocess_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
259static svn_error_t *
260inprocess_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. */
284static void
285erase_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
311static svn_error_t *
312inprocess_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
438static svn_error_t *
439inprocess_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. */
457struct 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. */
465static svn_error_t *
466iter_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
477static svn_error_t *
478inprocess_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
496static svn_error_t *
497inprocess_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
518static svn_error_t *
519inprocess_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
544static svn_error_t *
545inprocess_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
567static svn_error_t *
568inprocess_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
587static svn_boolean_t
588inprocess_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
599static svn_error_t *
600inprocess_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
619static svn_error_t *
620inprocess_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
635static 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
646svn_error_t *
647svn_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