2 5aa81393 2020-01-06 stsp * Copyright (c) 2019, 2020 Stefan Sperling <stsp@openbsd.org>
4 ab2f42e7 2019-11-10 stsp * Permission to use, copy, modify, and distribute this software for any
5 ab2f42e7 2019-11-10 stsp * purpose with or without fee is hereby granted, provided that the above
6 ab2f42e7 2019-11-10 stsp * copyright notice and this permission notice appear in all copies.
8 ab2f42e7 2019-11-10 stsp * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 ab2f42e7 2019-11-10 stsp * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 ab2f42e7 2019-11-10 stsp * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 ab2f42e7 2019-11-10 stsp * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 ab2f42e7 2019-11-10 stsp * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 ab2f42e7 2019-11-10 stsp * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 ab2f42e7 2019-11-10 stsp * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 8b925c6c 2022-07-16 thomas #include <sys/queue.h>
19 ab2f42e7 2019-11-10 stsp #include <stdlib.h>
20 ab2f42e7 2019-11-10 stsp #include <string.h>
21 26498a8b 2022-07-06 thomas #include <stdint.h>
22 ab2f42e7 2019-11-10 stsp #include <stdio.h>
23 ab2f42e7 2019-11-10 stsp #include <zlib.h>
24 ab2f42e7 2019-11-10 stsp #include <limits.h>
25 ab2f42e7 2019-11-10 stsp #include <time.h>
26 a5061f77 2022-06-13 thomas #include <errno.h>
28 dd038bc6 2021-09-21 thomas.ad #include "got_compat.h"
30 ab2f42e7 2019-11-10 stsp #include "got_object.h"
31 ab2f42e7 2019-11-10 stsp #include "got_error.h"
33 ab2f42e7 2019-11-10 stsp #include "got_lib_delta.h"
34 ab2f42e7 2019-11-10 stsp #include "got_lib_inflate.h"
35 ab2f42e7 2019-11-10 stsp #include "got_lib_object.h"
36 ab2f42e7 2019-11-10 stsp #include "got_lib_delta_cache.h"
38 ab2f42e7 2019-11-10 stsp #ifndef nitems
39 ab2f42e7 2019-11-10 stsp #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
42 f7a026c4 2023-04-28 thomas #define GOT_DELTA_CACHE_MIN_BUCKETS 64
43 f7a026c4 2023-04-28 thomas #define GOT_DELTA_CACHE_MAX_BUCKETS 2048
44 f7a026c4 2023-04-28 thomas #define GOT_DELTA_CACHE_MAX_CHAIN 2
45 f7a026c4 2023-04-28 thomas #define GOT_DELTA_CACHE_MAX_DELTA_SIZE 1024
46 f7a026c4 2023-04-28 thomas #define GOT_DELTA_CACHE_MAX_FULLTEXT_SIZE 524288
49 a5061f77 2022-06-13 thomas struct got_cached_delta {
50 a5061f77 2022-06-13 thomas off_t offset;
51 a5061f77 2022-06-13 thomas uint8_t *data;
52 a5061f77 2022-06-13 thomas size_t len;
53 f7a026c4 2023-04-28 thomas uint8_t *fulltext;
54 f7a026c4 2023-04-28 thomas size_t fulltext_len;
57 a5061f77 2022-06-13 thomas struct got_delta_cache_head {
58 a5061f77 2022-06-13 thomas struct got_cached_delta entries[GOT_DELTA_CACHE_MAX_CHAIN];
59 a5061f77 2022-06-13 thomas unsigned int nchain;
62 ab2f42e7 2019-11-10 stsp struct got_delta_cache {
63 a5061f77 2022-06-13 thomas struct got_delta_cache_head *buckets;
64 a5061f77 2022-06-13 thomas unsigned int nbuckets;
65 a5061f77 2022-06-13 thomas unsigned int totelem;
66 c3b318d0 2019-11-10 stsp int cache_search;
67 c3b318d0 2019-11-10 stsp int cache_hit;
68 f7a026c4 2023-04-28 thomas int cache_hit_fulltext;
69 c3b318d0 2019-11-10 stsp int cache_miss;
70 c3b318d0 2019-11-10 stsp int cache_evict;
71 c3b318d0 2019-11-10 stsp int cache_toolarge;
72 f7a026c4 2023-04-28 thomas int cache_toolarge_fulltext;
73 8c2f570d 2023-04-22 thomas int cache_maxtoolarge;
74 f7a026c4 2023-04-28 thomas int cache_maxtoolarge_fulltext;
75 a5061f77 2022-06-13 thomas unsigned int flags;
76 a5061f77 2022-06-13 thomas #define GOT_DELTA_CACHE_F_NOMEM 0x01
77 a5061f77 2022-06-13 thomas SIPHASH_KEY key;
80 a5061f77 2022-06-13 thomas const struct got_error *
81 a5061f77 2022-06-13 thomas got_delta_cache_alloc(struct got_delta_cache **new)
83 a5061f77 2022-06-13 thomas const struct got_error *err;
84 ab2f42e7 2019-11-10 stsp struct got_delta_cache *cache;
86 a5061f77 2022-06-13 thomas *new = NULL;
88 ab2f42e7 2019-11-10 stsp cache = calloc(1, sizeof(*cache));
89 ab2f42e7 2019-11-10 stsp if (cache == NULL)
90 a5061f77 2022-06-13 thomas return got_error_from_errno("calloc");
92 a5061f77 2022-06-13 thomas cache->buckets = calloc(GOT_DELTA_CACHE_MIN_BUCKETS,
93 a5061f77 2022-06-13 thomas sizeof(cache->buckets[0]));
94 a5061f77 2022-06-13 thomas if (cache->buckets == NULL) {
95 a5061f77 2022-06-13 thomas err = got_error_from_errno("calloc");
96 a5061f77 2022-06-13 thomas free(cache);
97 a5061f77 2022-06-13 thomas return err;
99 a5061f77 2022-06-13 thomas cache->nbuckets = GOT_DELTA_CACHE_MIN_BUCKETS;
101 a5061f77 2022-06-13 thomas arc4random_buf(&cache->key, sizeof(cache->key));
102 a5061f77 2022-06-13 thomas *new = cache;
103 a5061f77 2022-06-13 thomas return NULL;
107 ab2f42e7 2019-11-10 stsp got_delta_cache_free(struct got_delta_cache *cache)
109 a5061f77 2022-06-13 thomas struct got_cached_delta *delta;
110 a5061f77 2022-06-13 thomas unsigned int i;
112 cd9fd5e0 2022-12-01 thomas #ifdef GOT_DELTA_CACHE_DEBUG
113 a5061f77 2022-06-13 thomas fprintf(stderr, "%s: delta cache: %u elements, %d searches, %d hits, "
114 f7a026c4 2023-04-28 thomas "%d fulltext hits, %d missed, %d evicted, %d too large (max %d), "
115 f7a026c4 2023-04-28 thomas "%d too large fulltext (max %d)\n",
116 f7a026c4 2023-04-28 thomas getprogname(), cache->totelem, cache->cache_search,
117 f7a026c4 2023-04-28 thomas cache->cache_hit, cache->cache_hit_fulltext,
118 8c2f570d 2023-04-22 thomas cache->cache_miss, cache->cache_evict, cache->cache_toolarge,
119 f7a026c4 2023-04-28 thomas cache->cache_maxtoolarge,
120 f7a026c4 2023-04-28 thomas cache->cache_toolarge_fulltext,
121 f7a026c4 2023-04-28 thomas cache->cache_maxtoolarge_fulltext);
123 a5061f77 2022-06-13 thomas for (i = 0; i < cache->nbuckets; i++) {
124 a5061f77 2022-06-13 thomas struct got_delta_cache_head *head;
126 a5061f77 2022-06-13 thomas head = &cache->buckets[i];
127 a5061f77 2022-06-13 thomas for (j = 0; j < head->nchain; j++) {
128 a5061f77 2022-06-13 thomas delta = &head->entries[j];
129 a5061f77 2022-06-13 thomas free(delta->data);
132 a5061f77 2022-06-13 thomas free(cache->buckets);
133 ab2f42e7 2019-11-10 stsp free(cache);
136 a5061f77 2022-06-13 thomas static uint64_t
137 a5061f77 2022-06-13 thomas delta_cache_hash(struct got_delta_cache *cache, off_t delta_offset)
139 a5061f77 2022-06-13 thomas return SipHash24(&cache->key, &delta_offset, sizeof(delta_offset));
142 b5a8f744 2022-11-08 thomas #ifndef GOT_NO_DELTA_CACHE
143 a5061f77 2022-06-13 thomas static const struct got_error *
144 a5061f77 2022-06-13 thomas delta_cache_resize(struct got_delta_cache *cache, unsigned int nbuckets)
146 a5061f77 2022-06-13 thomas struct got_delta_cache_head *buckets;
147 a5061f77 2022-06-13 thomas size_t i;
149 a5061f77 2022-06-13 thomas buckets = calloc(nbuckets, sizeof(buckets[0]));
150 a5061f77 2022-06-13 thomas if (buckets == NULL) {
151 a5061f77 2022-06-13 thomas if (errno != ENOMEM)
152 a5061f77 2022-06-13 thomas return got_error_from_errno("calloc");
153 a5061f77 2022-06-13 thomas /* Proceed with our current amount of hash buckets. */
154 a5061f77 2022-06-13 thomas cache->flags |= GOT_DELTA_CACHE_F_NOMEM;
155 a5061f77 2022-06-13 thomas return NULL;
158 a5061f77 2022-06-13 thomas arc4random_buf(&cache->key, sizeof(cache->key));
160 a5061f77 2022-06-13 thomas for (i = 0; i < cache->nbuckets; i++) {
161 a5061f77 2022-06-13 thomas unsigned int j;
162 a5061f77 2022-06-13 thomas for (j = 0; j < cache->buckets[i].nchain; j++) {
163 a5061f77 2022-06-13 thomas struct got_delta_cache_head *head;
164 a5061f77 2022-06-13 thomas struct got_cached_delta *delta;
165 a5061f77 2022-06-13 thomas uint64_t idx;
166 a5061f77 2022-06-13 thomas delta = &cache->buckets[i].entries[j];
167 a5061f77 2022-06-13 thomas idx = delta_cache_hash(cache, delta->offset) % nbuckets;
168 a5061f77 2022-06-13 thomas head = &buckets[idx];
169 a5061f77 2022-06-13 thomas if (head->nchain < nitems(head->entries)) {
170 a5061f77 2022-06-13 thomas struct got_cached_delta *new_delta;
171 a5061f77 2022-06-13 thomas new_delta = &head->entries[head->nchain];
172 a5061f77 2022-06-13 thomas memcpy(new_delta, delta, sizeof(*new_delta));
173 a5061f77 2022-06-13 thomas head->nchain++;
175 a5061f77 2022-06-13 thomas free(delta->data);
176 c94b2859 2022-11-08 thomas cache->totelem--;
181 a5061f77 2022-06-13 thomas free(cache->buckets);
182 a5061f77 2022-06-13 thomas cache->buckets = buckets;
183 a5061f77 2022-06-13 thomas cache->nbuckets = nbuckets;
184 a5061f77 2022-06-13 thomas return NULL;
187 a5061f77 2022-06-13 thomas static const struct got_error *
188 a5061f77 2022-06-13 thomas delta_cache_grow(struct got_delta_cache *cache)
190 a5061f77 2022-06-13 thomas unsigned int nbuckets;
192 a5061f77 2022-06-13 thomas if ((cache->flags & GOT_DELTA_CACHE_F_NOMEM) ||
193 a5061f77 2022-06-13 thomas cache->nbuckets == GOT_DELTA_CACHE_MAX_BUCKETS)
194 a5061f77 2022-06-13 thomas return NULL;
196 a5061f77 2022-06-13 thomas if (cache->nbuckets >= GOT_DELTA_CACHE_MAX_BUCKETS / 2)
197 a5061f77 2022-06-13 thomas nbuckets = GOT_DELTA_CACHE_MAX_BUCKETS;
199 a5061f77 2022-06-13 thomas nbuckets = cache->nbuckets * 2;
201 a5061f77 2022-06-13 thomas return delta_cache_resize(cache, nbuckets);
205 ab2f42e7 2019-11-10 stsp const struct got_error *
206 ab2f42e7 2019-11-10 stsp got_delta_cache_add(struct got_delta_cache *cache,
207 ab2f42e7 2019-11-10 stsp off_t delta_data_offset, uint8_t *delta_data, size_t delta_len)
209 b5a8f744 2022-11-08 thomas #ifdef GOT_NO_DELTA_CACHE
210 fa7a529e 2020-01-06 stsp return got_error(GOT_ERR_NO_SPACE);
212 a5061f77 2022-06-13 thomas const struct got_error *err = NULL;
213 a5061f77 2022-06-13 thomas struct got_cached_delta *delta;
214 a5061f77 2022-06-13 thomas struct got_delta_cache_head *head;
215 a5061f77 2022-06-13 thomas uint64_t idx;
217 88b1b490 2022-06-13 thomas if (delta_len > GOT_DELTA_CACHE_MAX_DELTA_SIZE) {
218 c3b318d0 2019-11-10 stsp cache->cache_toolarge++;
219 8c2f570d 2023-04-22 thomas if (delta_len > cache->cache_maxtoolarge)
220 8c2f570d 2023-04-22 thomas cache->cache_maxtoolarge = delta_len;
221 ab2f42e7 2019-11-10 stsp return got_error(GOT_ERR_NO_SPACE);
224 a5061f77 2022-06-13 thomas if (cache->nbuckets * 3 < cache->totelem * 4) {
225 a5061f77 2022-06-13 thomas err = delta_cache_grow(cache);
227 a5061f77 2022-06-13 thomas return err;
230 a5061f77 2022-06-13 thomas idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
231 a5061f77 2022-06-13 thomas head = &cache->buckets[idx];
232 a5061f77 2022-06-13 thomas if (head->nchain >= nitems(head->entries)) {
233 a5061f77 2022-06-13 thomas delta = &head->entries[head->nchain - 1];
234 a5061f77 2022-06-13 thomas free(delta->data);
235 f7a026c4 2023-04-28 thomas free(delta->fulltext);
236 a5061f77 2022-06-13 thomas memset(delta, 0, sizeof(*delta));
237 a5061f77 2022-06-13 thomas head->nchain--;
238 c94b2859 2022-11-08 thomas cache->totelem--;
239 c94b2859 2022-11-08 thomas cache->cache_evict++;
242 a5061f77 2022-06-13 thomas delta = &head->entries[head->nchain];
243 a5061f77 2022-06-13 thomas delta->offset = delta_data_offset;
244 a5061f77 2022-06-13 thomas delta->data = delta_data;
245 a5061f77 2022-06-13 thomas delta->len = delta_len;
246 f7a026c4 2023-04-28 thomas delta->fulltext = NULL;
247 f7a026c4 2023-04-28 thomas delta->fulltext_len = 0;
248 a5061f77 2022-06-13 thomas head->nchain++;
249 a5061f77 2022-06-13 thomas cache->totelem++;
251 ab2f42e7 2019-11-10 stsp return NULL;
255 f7a026c4 2023-04-28 thomas const struct got_error *
256 f7a026c4 2023-04-28 thomas got_delta_cache_add_fulltext(struct got_delta_cache *cache,
257 f7a026c4 2023-04-28 thomas off_t delta_data_offset, uint8_t *fulltext, size_t fulltext_len)
259 f7a026c4 2023-04-28 thomas #ifdef GOT_NO_DELTA_CACHE
260 f7a026c4 2023-04-28 thomas return got_error(GOT_ERR_NO_SPACE);
262 f7a026c4 2023-04-28 thomas struct got_cached_delta *delta;
263 f7a026c4 2023-04-28 thomas struct got_delta_cache_head *head;
264 f7a026c4 2023-04-28 thomas uint64_t idx;
267 f7a026c4 2023-04-28 thomas if (fulltext_len > GOT_DELTA_CACHE_MAX_FULLTEXT_SIZE) {
268 f7a026c4 2023-04-28 thomas cache->cache_toolarge_fulltext++;
269 f7a026c4 2023-04-28 thomas if (fulltext_len > cache->cache_maxtoolarge)
270 f7a026c4 2023-04-28 thomas cache->cache_maxtoolarge_fulltext = fulltext_len;
271 f7a026c4 2023-04-28 thomas return got_error(GOT_ERR_NO_SPACE);
274 f7a026c4 2023-04-28 thomas idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
275 f7a026c4 2023-04-28 thomas head = &cache->buckets[idx];
277 f7a026c4 2023-04-28 thomas for (i = 0; i < head->nchain; i++) {
278 f7a026c4 2023-04-28 thomas delta = &head->entries[i];
279 f7a026c4 2023-04-28 thomas if (delta->offset != delta_data_offset)
280 f7a026c4 2023-04-28 thomas continue;
281 f7a026c4 2023-04-28 thomas if (i > 0) {
282 f7a026c4 2023-04-28 thomas struct got_cached_delta tmp;
284 f7a026c4 2023-04-28 thomas memcpy(&tmp, &head->entries[0], sizeof(tmp));
285 f7a026c4 2023-04-28 thomas memcpy(&head->entries[0], &head->entries[i],
286 f7a026c4 2023-04-28 thomas sizeof(head->entries[0]));
287 f7a026c4 2023-04-28 thomas memcpy(&head->entries[i], &tmp,
288 f7a026c4 2023-04-28 thomas sizeof(head->entries[i]));
289 f7a026c4 2023-04-28 thomas delta = &head->entries[0];
291 f7a026c4 2023-04-28 thomas delta->fulltext = malloc(fulltext_len);
292 f7a026c4 2023-04-28 thomas if (delta->fulltext == NULL)
293 f7a026c4 2023-04-28 thomas return got_error_from_errno("malloc");
294 f7a026c4 2023-04-28 thomas memcpy(delta->fulltext, fulltext, fulltext_len);
295 f7a026c4 2023-04-28 thomas delta->fulltext_len = fulltext_len;
299 f7a026c4 2023-04-28 thomas return NULL;
304 ab2f42e7 2019-11-10 stsp got_delta_cache_get(uint8_t **delta_data, size_t *delta_len,
305 f7a026c4 2023-04-28 thomas uint8_t **fulltext, size_t *fulltext_len,
306 ab2f42e7 2019-11-10 stsp struct got_delta_cache *cache, off_t delta_data_offset)
308 a5061f77 2022-06-13 thomas uint64_t idx;
309 a5061f77 2022-06-13 thomas struct got_delta_cache_head *head;
310 a5061f77 2022-06-13 thomas struct got_cached_delta *delta;
313 a5061f77 2022-06-13 thomas idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
314 a5061f77 2022-06-13 thomas head = &cache->buckets[idx];
316 c3b318d0 2019-11-10 stsp cache->cache_search++;
317 ab2f42e7 2019-11-10 stsp *delta_data = NULL;
318 ab2f42e7 2019-11-10 stsp *delta_len = 0;
319 f7a026c4 2023-04-28 thomas if (fulltext)
320 f7a026c4 2023-04-28 thomas *fulltext = NULL;
321 f7a026c4 2023-04-28 thomas if (fulltext_len)
322 f7a026c4 2023-04-28 thomas *fulltext_len = 0;
323 a5061f77 2022-06-13 thomas for (i = 0; i < head->nchain; i++) {
324 a5061f77 2022-06-13 thomas delta = &head->entries[i];
325 a5061f77 2022-06-13 thomas if (delta->offset != delta_data_offset)
327 c3b318d0 2019-11-10 stsp cache->cache_hit++;
328 a5061f77 2022-06-13 thomas if (i > 0) {
329 a5061f77 2022-06-13 thomas struct got_cached_delta tmp;
330 a5061f77 2022-06-13 thomas memcpy(&tmp, &head->entries[0], sizeof(tmp));
331 a5061f77 2022-06-13 thomas memcpy(&head->entries[0], &head->entries[i],
332 a5061f77 2022-06-13 thomas sizeof(head->entries[0]));
333 a5061f77 2022-06-13 thomas memcpy(&head->entries[i], &tmp,
334 a5061f77 2022-06-13 thomas sizeof(head->entries[i]));
335 a5061f77 2022-06-13 thomas delta = &head->entries[0];
337 a5061f77 2022-06-13 thomas *delta_data = delta->data;
338 a5061f77 2022-06-13 thomas *delta_len = delta->len;
339 f7a026c4 2023-04-28 thomas if (fulltext && fulltext_len &&
340 f7a026c4 2023-04-28 thomas delta->fulltext && delta->fulltext_len) {
341 f7a026c4 2023-04-28 thomas *fulltext = delta->fulltext;
342 f7a026c4 2023-04-28 thomas *fulltext_len = delta->fulltext_len;
343 f7a026c4 2023-04-28 thomas cache->cache_hit_fulltext++;
349 c3b318d0 2019-11-10 stsp cache->cache_miss++;
