2 * Copyright (c) 2019, 2020 Stefan Sperling <stsp@openbsd.org>
4 * Permission to use, copy, modify, and distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 #include <sys/queue.h>
28 #include "got_compat.h"
30 #include "got_object.h"
31 #include "got_error.h"
33 #include "got_lib_delta.h"
34 #include "got_lib_inflate.h"
35 #include "got_lib_object.h"
36 #include "got_lib_delta_cache.h"
39 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
42 #define GOT_DELTA_CACHE_MIN_BUCKETS 64
43 #define GOT_DELTA_CACHE_MAX_BUCKETS 2048
44 #define GOT_DELTA_CACHE_MAX_CHAIN 2
45 #define GOT_DELTA_CACHE_MAX_DELTA_SIZE 1024
47 struct got_cached_delta {
53 struct got_delta_cache_head {
54 struct got_cached_delta entries[GOT_DELTA_CACHE_MAX_CHAIN];
58 struct got_delta_cache {
59 struct got_delta_cache_head *buckets;
60 unsigned int nbuckets;
67 int cache_maxtoolarge;
69 #define GOT_DELTA_CACHE_F_NOMEM 0x01
73 const struct got_error *
74 got_delta_cache_alloc(struct got_delta_cache **new)
76 const struct got_error *err;
77 struct got_delta_cache *cache;
81 cache = calloc(1, sizeof(*cache));
83 return got_error_from_errno("calloc");
85 cache->buckets = calloc(GOT_DELTA_CACHE_MIN_BUCKETS,
86 sizeof(cache->buckets[0]));
87 if (cache->buckets == NULL) {
88 err = got_error_from_errno("calloc");
92 cache->nbuckets = GOT_DELTA_CACHE_MIN_BUCKETS;
94 arc4random_buf(&cache->key, sizeof(cache->key));
100 got_delta_cache_free(struct got_delta_cache *cache)
102 struct got_cached_delta *delta;
105 #ifdef GOT_DELTA_CACHE_DEBUG
106 fprintf(stderr, "%s: delta cache: %u elements, %d searches, %d hits, "
107 "%d missed, %d evicted, %d too large (max %d)\n", getprogname(),
108 cache->totelem, cache->cache_search, cache->cache_hit,
109 cache->cache_miss, cache->cache_evict, cache->cache_toolarge,
110 cache->cache_maxtoolarge);
112 for (i = 0; i < cache->nbuckets; i++) {
113 struct got_delta_cache_head *head;
115 head = &cache->buckets[i];
116 for (j = 0; j < head->nchain; j++) {
117 delta = &head->entries[j];
121 free(cache->buckets);
126 delta_cache_hash(struct got_delta_cache *cache, off_t delta_offset)
128 return SipHash24(&cache->key, &delta_offset, sizeof(delta_offset));
131 #ifndef GOT_NO_DELTA_CACHE
132 static const struct got_error *
133 delta_cache_resize(struct got_delta_cache *cache, unsigned int nbuckets)
135 struct got_delta_cache_head *buckets;
138 buckets = calloc(nbuckets, sizeof(buckets[0]));
139 if (buckets == NULL) {
141 return got_error_from_errno("calloc");
142 /* Proceed with our current amount of hash buckets. */
143 cache->flags |= GOT_DELTA_CACHE_F_NOMEM;
147 arc4random_buf(&cache->key, sizeof(cache->key));
149 for (i = 0; i < cache->nbuckets; i++) {
151 for (j = 0; j < cache->buckets[i].nchain; j++) {
152 struct got_delta_cache_head *head;
153 struct got_cached_delta *delta;
155 delta = &cache->buckets[i].entries[j];
156 idx = delta_cache_hash(cache, delta->offset) % nbuckets;
157 head = &buckets[idx];
158 if (head->nchain < nitems(head->entries)) {
159 struct got_cached_delta *new_delta;
160 new_delta = &head->entries[head->nchain];
161 memcpy(new_delta, delta, sizeof(*new_delta));
170 free(cache->buckets);
171 cache->buckets = buckets;
172 cache->nbuckets = nbuckets;
176 static const struct got_error *
177 delta_cache_grow(struct got_delta_cache *cache)
179 unsigned int nbuckets;
181 if ((cache->flags & GOT_DELTA_CACHE_F_NOMEM) ||
182 cache->nbuckets == GOT_DELTA_CACHE_MAX_BUCKETS)
185 if (cache->nbuckets >= GOT_DELTA_CACHE_MAX_BUCKETS / 2)
186 nbuckets = GOT_DELTA_CACHE_MAX_BUCKETS;
188 nbuckets = cache->nbuckets * 2;
190 return delta_cache_resize(cache, nbuckets);
194 const struct got_error *
195 got_delta_cache_add(struct got_delta_cache *cache,
196 off_t delta_data_offset, uint8_t *delta_data, size_t delta_len)
198 #ifdef GOT_NO_DELTA_CACHE
199 return got_error(GOT_ERR_NO_SPACE);
201 const struct got_error *err = NULL;
202 struct got_cached_delta *delta;
203 struct got_delta_cache_head *head;
206 if (delta_len > GOT_DELTA_CACHE_MAX_DELTA_SIZE) {
207 cache->cache_toolarge++;
208 if (delta_len > cache->cache_maxtoolarge)
209 cache->cache_maxtoolarge = delta_len;
210 return got_error(GOT_ERR_NO_SPACE);
213 if (cache->nbuckets * 3 < cache->totelem * 4) {
214 err = delta_cache_grow(cache);
219 idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
220 head = &cache->buckets[idx];
221 if (head->nchain >= nitems(head->entries)) {
222 delta = &head->entries[head->nchain - 1];
224 memset(delta, 0, sizeof(*delta));
227 cache->cache_evict++;
230 delta = &head->entries[head->nchain];
231 delta->offset = delta_data_offset;
232 delta->data = delta_data;
233 delta->len = delta_len;
242 got_delta_cache_get(uint8_t **delta_data, size_t *delta_len,
243 struct got_delta_cache *cache, off_t delta_data_offset)
246 struct got_delta_cache_head *head;
247 struct got_cached_delta *delta;
250 idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
251 head = &cache->buckets[idx];
253 cache->cache_search++;
256 for (i = 0; i < head->nchain; i++) {
257 delta = &head->entries[i];
258 if (delta->offset != delta_data_offset)
262 struct got_cached_delta tmp;
263 memcpy(&tmp, &head->entries[0], sizeof(tmp));
264 memcpy(&head->entries[0], &head->entries[i],
265 sizeof(head->entries[0]));
266 memcpy(&head->entries[i], &tmp,
267 sizeof(head->entries[i]));
268 delta = &head->entries[0];
270 *delta_data = delta->data;
271 *delta_len = delta->len;