<commit_before>/*
 * cache-membuffer.c: in-memory caching for Subversion
 *
 * ====================================================================
 *    Licensed to the Apache Software Foundation (ASF) under one
 *    or more contributor license agreements.  See the NOTICE file
 *    distributed with this work for additional information
 *    regarding copyright ownership.  The ASF licenses this file
 *    to you 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 <assert.h>
#include <apr_md5.h>
#include "svn_pools.h"
#include "svn_checksum.h"
#include "md5.h"
#include "svn_private_config.h"
#include "cache.h"
#include "svn_string.h"
#include "private/svn_dep_compat.h"

/*
 * A membuffer cache consists of two parts:
 *
 * 1. A linear data buffer containing a cached items in a serialized
 *    representation. There may be arbitrary gaps between entries.
 * 2. A directory of cache entries. This is organized similar to CPU
 *    data caches: for every possible key, there is exactly one group
 *    of entries that may contain the header info for an item with
 *    that given key. The result is a GROUP_SIZE-way associative cache.
 *
 * Only the begnnings of these two data parts are addressed through a
 * native pointer. All other references are expressed as offsets to
 * these array pointers. With that design, it is relatively easy to
 * share the same data structure between different processes and / or
 * to persist them on disk.
 *
 * The data buffer usage information is implicitly given by the directory
 * entries. Every *used* entry has a reference to the previous and the
 * next used dictionary entry - in the order their item data is stored
 * in the data buffer. So, removing data, for instance, is done simply
 * by unlinking it from the chain, marking it as unused and possibly
 * adjusting global list pointers.
 *
 * Insertion can occur at one position. It is marked by its offset in
 * the data buffer plus the index of the first used entry equal or
 * larger that position. If this gap is too small to accomodate the
 * new item, the insertion window is extended as described below. The
 * new entry will always be inserted at the bottom end of the window
 * and since the next used entry is known, properly sorted insertion
 * is possible.
 *
 * To make the cache perform robustly in a wide range of usage scenarios,
 * a randomized variant of LFU is used. Every item holds a (read)
 * hit counter and there is a global (read) hit counter. The more hits
 * an entry has in relation to the average, the more it is likely to be
 * kept using a rand()-based condition. The test is applied only to the
 * entry at the end of the insertion window. If it doesn't get evicted,
 * its being moved to the begin of that window and this window is moved.
 *
 * Moreover, the entry's hits get halfed to make that entry more likely
 * to be removed the next time, the sliding insertion / auto-removal
 * window comes by. As a result, frequently used entries are likely not
 * to be dropped until they get not used for a while. Also, even a cache
 * thrashing situation about 50% of the content survives every 50% of the
 * cache being re-written with new entries. For details on the fine-
 * tuning involved, see the comments in ensure_data_insertable().
 *
 * To limit the entry size and management overhead, the actual item keys
 * will not be stored but only their MD5 checksums, instead. This is
 * reasonably safe to do since users have only limited control over the
 * full keys, even if these are folder paths. So, it is very hard to
 * construct colliding keys.
 *
 * All access to the cached data needs to be serialized. Because we want<commit_msg>Fix a number of typos etc. plus add a short paragraph how svn_cache__t instances relate to the big singleton membuffer cache instance.<commit_after>/*
 * cache-membuffer.c: in-memory caching for Subversion
 *
 * ====================================================================
 *    Licensed to the Apache Software Foundation (ASF) under one
 *    or more contributor license agreements.  See the NOTICE file
 *    distributed with this work for additional information
 *    regarding copyright ownership.  The ASF licenses this file
 *    to you 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 <assert.h>
#include <apr_md5.h>
#include "svn_pools.h"
#include "svn_checksum.h"
#include "md5.h"
#include "svn_private_config.h"
#include "cache.h"
#include "svn_string.h"
#include "private/svn_dep_compat.h"

/*
 * This svn_cache__t implementation actually consists of two parts:
 * a shared (per-process) singleton membuffer cache instance and shallow
 * svn_cache__t frontend instances that each use different key spaces.
 * For data management, they all forward to the singleton membuffer cache.
 *
 * A membuffer cache consists of two parts:
 *
 * 1. A linear data buffer containing cached items in a serialized
 *    representation. There may be arbitrary gaps between entries.
 * 2. A directory of cache entries. This is organized similar to CPU
 *    data caches: for every possible key, there is exactly one group
 *    of entries that may contain the header info for an item with
 *    that given key. The result is a GROUP_SIZE-way associative cache.
 *
 * Only the start address of these two data parts are given as a native
 * pointer. All other references are expressed as offsets to these pointers.
 * With that design, it is relatively easy to share the same data structure
 * between different processes and / or to persist them on disk. These
 * out-of-process features have not been implemented, yet.
 *
 * The data buffer usage information is implicitly given by the directory
 * entries. Every USED entry has a reference to the previous and the next
 * used dictionary entry and this double-linked list is ordered by the
 * offsets of their item data within the the data buffer. So removing data,
 * for instance, is done simply by unlinking it from the chain, implicitly
 * marking the entry as well as the data buffer section previously
 * associated to it as unused.
 *
 * Insertion can occur at only one, sliding position. It is marked by its
 * offset in the data buffer plus the index of the first used entry at or
 * behind that position. If this gap is too small to accomodate the new
 * item, the insertion window is extended as described below. The new entry
 * will always be inserted at the bottom end of the window and since the
 * next used entry is known, properly sorted insertion is possible.
 *
 * To make the cache perform robustly in a wide range of usage scenarios,
 * a randomized variant of LFU is used. Every item holds a read hit counter
 * and there is a global read hit counter. The more hits an entry has in
 * relation to the average, the more it is likely to be kept using a rand()-
 * based condition. The test is applied only to the entry following the
 * insertion window. If it doesn't get evicted, it is moved to the begin of
 * that window and the window is moved.
 *
 * Moreover, the entry's hits get halfed to make that entry more likely to
 * be removed the next time the sliding insertion / removal window comes by.
 * As a result, frequently used entries are likely not to be dropped until
 * they get not used for a while. Also, even a cache thrashing situation
 * about 50% of the content survives every 50% of the cache being re-written
 * with new entries. For details on the fine-tuning involved, see the
 * comments in ensure_data_insertable().
 *
 * To limit the entry size and management overhead, not the actual item keys
 * but only their MD5 checksums will not be stored. This is reasonably safe
 * to do since users have only limited control over the full keys, even if
 * these contain folder paths. So, it is very hard to deliberately construct
 * colliding keys. Random checksum collisions can be shown to be extremely
 * unlikely.
 *
 * All access to the cached data needs to be serialized. Because we want
{'fraction_non_alphanumeric': 0.0798387975166104, 'fraction_numerical': 0.0028319355190066444, 'mean_word_length': 3.7427685950413223, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4726851', 'n_tokens_mistral': 2289, 'n_tokens_neox': 2215, 'n_words': 1349}