1 ab2f42e7 2019-11-10 stsp /*
  2 5aa81393 2020-01-06 stsp  * Copyright (c) 2019, 2020 Stefan Sperling <stsp@openbsd.org>
  3 ab2f42e7 2019-11-10 stsp  *
  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.
  7 ab2f42e7 2019-11-10 stsp  *
  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.
 15 ab2f42e7 2019-11-10 stsp  */
 16 ab2f42e7 2019-11-10 stsp 
 17 ab2f42e7 2019-11-10 stsp #include <sys/queue.h>
 18 ab2f42e7 2019-11-10 stsp 
 19 ab2f42e7 2019-11-10 stsp #include <stdlib.h>
 20 ab2f42e7 2019-11-10 stsp #include <string.h>
 21 d89a2828 2022-07-05 stsp #include <stdint.h>
 22 ab2f42e7 2019-11-10 stsp #include <sha1.h>
 23 5822e79e 2023-02-23 op #include <sha2.h>
 24 ab2f42e7 2019-11-10 stsp #include <stdio.h>
 25 ab2f42e7 2019-11-10 stsp #include <zlib.h>
 26 ab2f42e7 2019-11-10 stsp #include <limits.h>
 27 ab2f42e7 2019-11-10 stsp #include <time.h>
 28 dac5c75e 2022-06-04 stsp #include <errno.h>
 29 dac5c75e 2022-06-04 stsp #include <siphash.h>
 30 ab2f42e7 2019-11-10 stsp 
 31 ab2f42e7 2019-11-10 stsp #include "got_object.h"
 32 ab2f42e7 2019-11-10 stsp #include "got_error.h"
 33 ab2f42e7 2019-11-10 stsp 
 34 ab2f42e7 2019-11-10 stsp #include "got_lib_delta.h"
 35 ab2f42e7 2019-11-10 stsp #include "got_lib_inflate.h"
 36 ab2f42e7 2019-11-10 stsp #include "got_lib_object.h"
 37 ab2f42e7 2019-11-10 stsp #include "got_lib_delta_cache.h"
 38 ab2f42e7 2019-11-10 stsp 
 39 ab2f42e7 2019-11-10 stsp #ifndef nitems
 40 ab2f42e7 2019-11-10 stsp #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
 41 ab2f42e7 2019-11-10 stsp #endif
 42 ab2f42e7 2019-11-10 stsp 
 43 1aaa1562 2023-04-24 stsp #define GOT_DELTA_CACHE_MIN_BUCKETS		64
 44 1aaa1562 2023-04-24 stsp #define GOT_DELTA_CACHE_MAX_BUCKETS		2048
 45 1aaa1562 2023-04-24 stsp #define GOT_DELTA_CACHE_MAX_CHAIN		2
 46 1aaa1562 2023-04-24 stsp #define GOT_DELTA_CACHE_MAX_DELTA_SIZE		1024
 47 1aaa1562 2023-04-24 stsp #define GOT_DELTA_CACHE_MAX_FULLTEXT_SIZE	524288
 48 dac5c75e 2022-06-04 stsp 
 49 1aaa1562 2023-04-24 stsp 
 50 dac5c75e 2022-06-04 stsp struct got_cached_delta {
 51 dac5c75e 2022-06-04 stsp 	off_t offset;
 52 dac5c75e 2022-06-04 stsp 	uint8_t *data;
 53 dac5c75e 2022-06-04 stsp 	size_t len;
 54 1aaa1562 2023-04-24 stsp 	uint8_t *fulltext;
 55 1aaa1562 2023-04-24 stsp 	size_t fulltext_len;
 56 ab2f42e7 2019-11-10 stsp };
 57 ab2f42e7 2019-11-10 stsp 
 58 dac5c75e 2022-06-04 stsp struct got_delta_cache_head {
 59 dac5c75e 2022-06-04 stsp 	struct got_cached_delta entries[GOT_DELTA_CACHE_MAX_CHAIN];
 60 dac5c75e 2022-06-04 stsp 	unsigned int nchain;
 61 dac5c75e 2022-06-04 stsp };
 62 ab2f42e7 2019-11-10 stsp 
 63 ab2f42e7 2019-11-10 stsp struct got_delta_cache {
 64 dac5c75e 2022-06-04 stsp 	struct got_delta_cache_head *buckets;
 65 dac5c75e 2022-06-04 stsp 	unsigned int nbuckets;
 66 dac5c75e 2022-06-04 stsp 	unsigned int totelem;
 67 c3b318d0 2019-11-10 stsp 	int cache_search;
 68 c3b318d0 2019-11-10 stsp 	int cache_hit;
 69 1aaa1562 2023-04-24 stsp 	int cache_hit_fulltext;
 70 c3b318d0 2019-11-10 stsp 	int cache_miss;
 71 c3b318d0 2019-11-10 stsp 	int cache_evict;
 72 c3b318d0 2019-11-10 stsp 	int cache_toolarge;
 73 1aaa1562 2023-04-24 stsp 	int cache_toolarge_fulltext;
 74 b77715b7 2023-04-18 stsp 	int cache_maxtoolarge;
 75 1aaa1562 2023-04-24 stsp 	int cache_maxtoolarge_fulltext;
 76 dac5c75e 2022-06-04 stsp 	unsigned int flags;
 77 dac5c75e 2022-06-04 stsp #define GOT_DELTA_CACHE_F_NOMEM	0x01
 78 dac5c75e 2022-06-04 stsp 	SIPHASH_KEY key;
 79 ab2f42e7 2019-11-10 stsp };
 80 ab2f42e7 2019-11-10 stsp 
 81 dac5c75e 2022-06-04 stsp const struct got_error *
 82 dac5c75e 2022-06-04 stsp got_delta_cache_alloc(struct got_delta_cache **new)
 83 ab2f42e7 2019-11-10 stsp {
 84 dac5c75e 2022-06-04 stsp 	const struct got_error *err;
 85 ab2f42e7 2019-11-10 stsp 	struct got_delta_cache *cache;
 86 ab2f42e7 2019-11-10 stsp 
 87 dac5c75e 2022-06-04 stsp 	*new = NULL;
 88 dac5c75e 2022-06-04 stsp 
 89 ab2f42e7 2019-11-10 stsp 	cache = calloc(1, sizeof(*cache));
 90 ab2f42e7 2019-11-10 stsp 	if (cache == NULL)
 91 dac5c75e 2022-06-04 stsp 		return got_error_from_errno("calloc");
 92 20282b02 2022-06-16 tracey 
 93 dac5c75e 2022-06-04 stsp 	cache->buckets = calloc(GOT_DELTA_CACHE_MIN_BUCKETS,
 94 dac5c75e 2022-06-04 stsp 	    sizeof(cache->buckets[0]));
 95 dac5c75e 2022-06-04 stsp 	if (cache->buckets == NULL) {
 96 dac5c75e 2022-06-04 stsp 		err = got_error_from_errno("calloc");
 97 dac5c75e 2022-06-04 stsp 		free(cache);
 98 dac5c75e 2022-06-04 stsp 		return err;
 99 dac5c75e 2022-06-04 stsp 	}
100 dac5c75e 2022-06-04 stsp 	cache->nbuckets = GOT_DELTA_CACHE_MIN_BUCKETS;
101 ab2f42e7 2019-11-10 stsp 
102 dac5c75e 2022-06-04 stsp 	arc4random_buf(&cache->key, sizeof(cache->key));
103 dac5c75e 2022-06-04 stsp 	*new = cache;
104 dac5c75e 2022-06-04 stsp 	return NULL;
105 ab2f42e7 2019-11-10 stsp }
106 ab2f42e7 2019-11-10 stsp 
107 ab2f42e7 2019-11-10 stsp void
108 ab2f42e7 2019-11-10 stsp got_delta_cache_free(struct got_delta_cache *cache)
109 ab2f42e7 2019-11-10 stsp {
110 dac5c75e 2022-06-04 stsp 	struct got_cached_delta *delta;
111 dac5c75e 2022-06-04 stsp 	unsigned int i;
112 ab2f42e7 2019-11-10 stsp 
113 b5e1b8cd 2022-12-01 stsp #ifdef GOT_DELTA_CACHE_DEBUG
114 dac5c75e 2022-06-04 stsp 	fprintf(stderr, "%s: delta cache: %u elements, %d searches, %d hits, "
115 1aaa1562 2023-04-24 stsp 	    "%d fulltext hits, %d missed, %d evicted, %d too large (max %d), "
116 1aaa1562 2023-04-24 stsp 	    "%d too large fulltext (max %d)\n",
117 1aaa1562 2023-04-24 stsp 	    getprogname(), cache->totelem, cache->cache_search,
118 1aaa1562 2023-04-24 stsp 	    cache->cache_hit, cache->cache_hit_fulltext,
119 b77715b7 2023-04-18 stsp 	    cache->cache_miss, cache->cache_evict, cache->cache_toolarge,
120 1aaa1562 2023-04-24 stsp 	    cache->cache_maxtoolarge,
121 1aaa1562 2023-04-24 stsp 	    cache->cache_toolarge_fulltext,
122 1aaa1562 2023-04-24 stsp 	    cache->cache_maxtoolarge_fulltext);
123 c3b318d0 2019-11-10 stsp #endif
124 dac5c75e 2022-06-04 stsp 	for (i = 0; i < cache->nbuckets; i++) {
125 dac5c75e 2022-06-04 stsp 		struct got_delta_cache_head *head;
126 dac5c75e 2022-06-04 stsp 		int j;
127 dac5c75e 2022-06-04 stsp 		head = &cache->buckets[i];
128 dac5c75e 2022-06-04 stsp 		for (j = 0; j < head->nchain; j++) {
129 dac5c75e 2022-06-04 stsp 			delta = &head->entries[j];
130 dac5c75e 2022-06-04 stsp 			free(delta->data);
131 dac5c75e 2022-06-04 stsp 		}
132 ab2f42e7 2019-11-10 stsp 	}
133 dac5c75e 2022-06-04 stsp 	free(cache->buckets);
134 ab2f42e7 2019-11-10 stsp 	free(cache);
135 ab2f42e7 2019-11-10 stsp }
136 ab2f42e7 2019-11-10 stsp 
137 dac5c75e 2022-06-04 stsp static uint64_t
138 dac5c75e 2022-06-04 stsp delta_cache_hash(struct got_delta_cache *cache, off_t delta_offset)
139 ab2f42e7 2019-11-10 stsp {
140 dac5c75e 2022-06-04 stsp 	return SipHash24(&cache->key, &delta_offset, sizeof(delta_offset));
141 dac5c75e 2022-06-04 stsp }
142 ab2f42e7 2019-11-10 stsp 
143 22f6beb0 2022-11-08 stsp #ifndef GOT_NO_DELTA_CACHE
144 dac5c75e 2022-06-04 stsp static const struct got_error *
145 dac5c75e 2022-06-04 stsp delta_cache_resize(struct got_delta_cache *cache, unsigned int nbuckets)
146 dac5c75e 2022-06-04 stsp {
147 dac5c75e 2022-06-04 stsp 	struct got_delta_cache_head *buckets;
148 dac5c75e 2022-06-04 stsp 	size_t i;
149 ab2f42e7 2019-11-10 stsp 
150 dac5c75e 2022-06-04 stsp 	buckets = calloc(nbuckets, sizeof(buckets[0]));
151 dac5c75e 2022-06-04 stsp 	if (buckets == NULL) {
152 dac5c75e 2022-06-04 stsp 		if (errno != ENOMEM)
153 dac5c75e 2022-06-04 stsp 			return got_error_from_errno("calloc");
154 dac5c75e 2022-06-04 stsp 		/* Proceed with our current amount of hash buckets. */
155 dac5c75e 2022-06-04 stsp 		cache->flags |= GOT_DELTA_CACHE_F_NOMEM;
156 dac5c75e 2022-06-04 stsp 		return NULL;
157 dac5c75e 2022-06-04 stsp 	}
158 dac5c75e 2022-06-04 stsp 
159 dac5c75e 2022-06-04 stsp 	arc4random_buf(&cache->key, sizeof(cache->key));
160 dac5c75e 2022-06-04 stsp 
161 dac5c75e 2022-06-04 stsp 	for (i = 0; i < cache->nbuckets; i++) {
162 dac5c75e 2022-06-04 stsp 		unsigned int j;
163 dac5c75e 2022-06-04 stsp 		for (j = 0; j < cache->buckets[i].nchain; j++) {
164 dac5c75e 2022-06-04 stsp 			struct got_delta_cache_head *head;
165 dac5c75e 2022-06-04 stsp 			struct got_cached_delta *delta;
166 dac5c75e 2022-06-04 stsp 			uint64_t idx;
167 dac5c75e 2022-06-04 stsp 			delta = &cache->buckets[i].entries[j];
168 dac5c75e 2022-06-04 stsp 			idx = delta_cache_hash(cache, delta->offset) % nbuckets;
169 dac5c75e 2022-06-04 stsp 			head = &buckets[idx];
170 dac5c75e 2022-06-04 stsp 			if (head->nchain < nitems(head->entries)) {
171 dac5c75e 2022-06-04 stsp 				struct got_cached_delta *new_delta;
172 dac5c75e 2022-06-04 stsp 				new_delta = &head->entries[head->nchain];
173 dac5c75e 2022-06-04 stsp 				memcpy(new_delta, delta, sizeof(*new_delta));
174 dac5c75e 2022-06-04 stsp 				head->nchain++;
175 b43d5a6c 2022-11-08 stsp 			} else {
176 dac5c75e 2022-06-04 stsp 				free(delta->data);
177 b43d5a6c 2022-11-08 stsp 				cache->totelem--;
178 b43d5a6c 2022-11-08 stsp 			}
179 dac5c75e 2022-06-04 stsp 		}
180 dac5c75e 2022-06-04 stsp 	}
181 dac5c75e 2022-06-04 stsp 
182 dac5c75e 2022-06-04 stsp 	free(cache->buckets);
183 dac5c75e 2022-06-04 stsp 	cache->buckets = buckets;
184 dac5c75e 2022-06-04 stsp 	cache->nbuckets = nbuckets;
185 dac5c75e 2022-06-04 stsp 	return NULL;
186 ab2f42e7 2019-11-10 stsp }
187 ab2f42e7 2019-11-10 stsp 
188 dac5c75e 2022-06-04 stsp static const struct got_error *
189 dac5c75e 2022-06-04 stsp delta_cache_grow(struct got_delta_cache *cache)
190 dac5c75e 2022-06-04 stsp {
191 dac5c75e 2022-06-04 stsp 	unsigned int nbuckets;
192 dac5c75e 2022-06-04 stsp 
193 dac5c75e 2022-06-04 stsp 	if ((cache->flags & GOT_DELTA_CACHE_F_NOMEM) ||
194 dac5c75e 2022-06-04 stsp 	    cache->nbuckets == GOT_DELTA_CACHE_MAX_BUCKETS)
195 dac5c75e 2022-06-04 stsp 		return NULL;
196 dac5c75e 2022-06-04 stsp 
197 dac5c75e 2022-06-04 stsp 	if (cache->nbuckets >= GOT_DELTA_CACHE_MAX_BUCKETS / 2)
198 dac5c75e 2022-06-04 stsp 		nbuckets = GOT_DELTA_CACHE_MAX_BUCKETS;
199 dac5c75e 2022-06-04 stsp 	else
200 dac5c75e 2022-06-04 stsp 		nbuckets = cache->nbuckets * 2;
201 dac5c75e 2022-06-04 stsp 
202 dac5c75e 2022-06-04 stsp 	return delta_cache_resize(cache, nbuckets);
203 dac5c75e 2022-06-04 stsp }
204 20282b02 2022-06-16 tracey #endif
205 dac5c75e 2022-06-04 stsp 
206 ab2f42e7 2019-11-10 stsp const struct got_error *
207 ab2f42e7 2019-11-10 stsp got_delta_cache_add(struct got_delta_cache *cache,
208 ab2f42e7 2019-11-10 stsp     off_t delta_data_offset, uint8_t *delta_data, size_t delta_len)
209 ab2f42e7 2019-11-10 stsp {
210 22f6beb0 2022-11-08 stsp #ifdef GOT_NO_DELTA_CACHE
211 fa7a529e 2020-01-06 stsp 	return got_error(GOT_ERR_NO_SPACE);
212 fa7a529e 2020-01-06 stsp #else
213 dac5c75e 2022-06-04 stsp 	const struct got_error *err = NULL;
214 dac5c75e 2022-06-04 stsp 	struct got_cached_delta *delta;
215 dac5c75e 2022-06-04 stsp 	struct got_delta_cache_head *head;
216 dac5c75e 2022-06-04 stsp 	uint64_t idx;
217 ab2f42e7 2019-11-10 stsp 
218 4264b841 2022-06-04 stsp 	if (delta_len > GOT_DELTA_CACHE_MAX_DELTA_SIZE) {
219 c3b318d0 2019-11-10 stsp 		cache->cache_toolarge++;
220 b77715b7 2023-04-18 stsp 		if (delta_len > cache->cache_maxtoolarge)
221 b77715b7 2023-04-18 stsp 			cache->cache_maxtoolarge = delta_len;
222 ab2f42e7 2019-11-10 stsp 		return got_error(GOT_ERR_NO_SPACE);
223 c3b318d0 2019-11-10 stsp 	}
224 ab2f42e7 2019-11-10 stsp 
225 dac5c75e 2022-06-04 stsp 	if (cache->nbuckets * 3 < cache->totelem * 4) {
226 dac5c75e 2022-06-04 stsp 		err = delta_cache_grow(cache);
227 dac5c75e 2022-06-04 stsp 		if (err)
228 dac5c75e 2022-06-04 stsp 			return err;
229 dac5c75e 2022-06-04 stsp 	}
230 ab2f42e7 2019-11-10 stsp 
231 dac5c75e 2022-06-04 stsp 	idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
232 dac5c75e 2022-06-04 stsp 	head = &cache->buckets[idx];
233 dac5c75e 2022-06-04 stsp 	if (head->nchain >= nitems(head->entries)) {
234 dac5c75e 2022-06-04 stsp 		delta = &head->entries[head->nchain - 1];
235 dac5c75e 2022-06-04 stsp 		free(delta->data);
236 1aaa1562 2023-04-24 stsp 		free(delta->fulltext);
237 dac5c75e 2022-06-04 stsp 		memset(delta, 0, sizeof(*delta));
238 dac5c75e 2022-06-04 stsp 		head->nchain--;
239 b43d5a6c 2022-11-08 stsp 		cache->totelem--;
240 b43d5a6c 2022-11-08 stsp 		cache->cache_evict++;
241 dac5c75e 2022-06-04 stsp 	}
242 ab2f42e7 2019-11-10 stsp 
243 dac5c75e 2022-06-04 stsp 	delta = &head->entries[head->nchain];
244 dac5c75e 2022-06-04 stsp 	delta->offset = delta_data_offset;
245 dac5c75e 2022-06-04 stsp 	delta->data = delta_data;
246 dac5c75e 2022-06-04 stsp 	delta->len = delta_len;
247 1aaa1562 2023-04-24 stsp 	delta->fulltext = NULL;
248 1aaa1562 2023-04-24 stsp 	delta->fulltext_len = 0;
249 dac5c75e 2022-06-04 stsp 	head->nchain++;
250 dac5c75e 2022-06-04 stsp 	cache->totelem++;
251 ab2f42e7 2019-11-10 stsp 
252 ab2f42e7 2019-11-10 stsp 	return NULL;
253 fa7a529e 2020-01-06 stsp #endif
254 ab2f42e7 2019-11-10 stsp }
255 ab2f42e7 2019-11-10 stsp 
256 1aaa1562 2023-04-24 stsp const struct got_error *
257 1aaa1562 2023-04-24 stsp got_delta_cache_add_fulltext(struct got_delta_cache *cache,
258 1aaa1562 2023-04-24 stsp     off_t delta_data_offset, uint8_t *fulltext, size_t fulltext_len)
259 1aaa1562 2023-04-24 stsp {
260 1aaa1562 2023-04-24 stsp #ifdef GOT_NO_DELTA_CACHE
261 1aaa1562 2023-04-24 stsp 	return got_error(GOT_ERR_NO_SPACE);
262 1aaa1562 2023-04-24 stsp #else
263 1aaa1562 2023-04-24 stsp 	struct got_cached_delta *delta;
264 1aaa1562 2023-04-24 stsp 	struct got_delta_cache_head *head;
265 1aaa1562 2023-04-24 stsp 	uint64_t idx;
266 1aaa1562 2023-04-24 stsp 	int i;
267 1aaa1562 2023-04-24 stsp 
268 1aaa1562 2023-04-24 stsp 	if (fulltext_len > GOT_DELTA_CACHE_MAX_FULLTEXT_SIZE) {
269 1aaa1562 2023-04-24 stsp 		cache->cache_toolarge_fulltext++;
270 1aaa1562 2023-04-24 stsp 		if (fulltext_len > cache->cache_maxtoolarge)
271 1aaa1562 2023-04-24 stsp 			cache->cache_maxtoolarge_fulltext = fulltext_len;
272 1aaa1562 2023-04-24 stsp 		return got_error(GOT_ERR_NO_SPACE);
273 1aaa1562 2023-04-24 stsp 	}
274 1aaa1562 2023-04-24 stsp 
275 1aaa1562 2023-04-24 stsp 	idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
276 1aaa1562 2023-04-24 stsp 	head = &cache->buckets[idx];
277 1aaa1562 2023-04-24 stsp 
278 1aaa1562 2023-04-24 stsp 	for (i = 0; i < head->nchain; i++) {
279 1aaa1562 2023-04-24 stsp 		delta = &head->entries[i];
280 1aaa1562 2023-04-24 stsp 		if (delta->offset != delta_data_offset)
281 1aaa1562 2023-04-24 stsp 			continue;
282 1aaa1562 2023-04-24 stsp 		if (i > 0) {
283 1aaa1562 2023-04-24 stsp 			struct got_cached_delta tmp;
284 2d6dd3ed 2023-04-24 stsp 
285 1aaa1562 2023-04-24 stsp 			memcpy(&tmp, &head->entries[0], sizeof(tmp));
286 1aaa1562 2023-04-24 stsp 			memcpy(&head->entries[0], &head->entries[i],
287 1aaa1562 2023-04-24 stsp 			    sizeof(head->entries[0]));
288 1aaa1562 2023-04-24 stsp 			memcpy(&head->entries[i], &tmp,
289 1aaa1562 2023-04-24 stsp 			    sizeof(head->entries[i]));
290 1aaa1562 2023-04-24 stsp 			delta = &head->entries[0];
291 1aaa1562 2023-04-24 stsp 		}
292 1aaa1562 2023-04-24 stsp 		delta->fulltext = malloc(fulltext_len);
293 1aaa1562 2023-04-24 stsp 		if (delta->fulltext == NULL)
294 1aaa1562 2023-04-24 stsp 			return got_error_from_errno("malloc");
295 1aaa1562 2023-04-24 stsp 		memcpy(delta->fulltext, fulltext, fulltext_len);
296 1aaa1562 2023-04-24 stsp 		delta->fulltext_len = fulltext_len;
297 1aaa1562 2023-04-24 stsp 		break;
298 1aaa1562 2023-04-24 stsp 	}
299 1aaa1562 2023-04-24 stsp 
300 1aaa1562 2023-04-24 stsp 	return NULL;
301 1aaa1562 2023-04-24 stsp #endif
302 1aaa1562 2023-04-24 stsp }
303 1aaa1562 2023-04-24 stsp 
304 ab2f42e7 2019-11-10 stsp void
305 ab2f42e7 2019-11-10 stsp got_delta_cache_get(uint8_t **delta_data, size_t *delta_len,
306 1aaa1562 2023-04-24 stsp     uint8_t **fulltext, size_t *fulltext_len,
307 ab2f42e7 2019-11-10 stsp     struct got_delta_cache *cache, off_t delta_data_offset)
308 ab2f42e7 2019-11-10 stsp {
309 dac5c75e 2022-06-04 stsp 	uint64_t idx;
310 dac5c75e 2022-06-04 stsp 	struct got_delta_cache_head *head;
311 dac5c75e 2022-06-04 stsp 	struct got_cached_delta *delta;
312 dac5c75e 2022-06-04 stsp 	int i;
313 ab2f42e7 2019-11-10 stsp 
314 dac5c75e 2022-06-04 stsp 	idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
315 dac5c75e 2022-06-04 stsp 	head = &cache->buckets[idx];
316 dac5c75e 2022-06-04 stsp 
317 c3b318d0 2019-11-10 stsp 	cache->cache_search++;
318 ab2f42e7 2019-11-10 stsp 	*delta_data = NULL;
319 ab2f42e7 2019-11-10 stsp 	*delta_len = 0;
320 1aaa1562 2023-04-24 stsp 	if (fulltext)
321 1aaa1562 2023-04-24 stsp 		*fulltext = NULL;
322 1aaa1562 2023-04-24 stsp 	if (fulltext_len)
323 1aaa1562 2023-04-24 stsp 		*fulltext_len = 0;
324 dac5c75e 2022-06-04 stsp 	for (i = 0; i < head->nchain; i++) {
325 dac5c75e 2022-06-04 stsp 		delta = &head->entries[i];
326 dac5c75e 2022-06-04 stsp 		if (delta->offset != delta_data_offset)
327 ab2f42e7 2019-11-10 stsp 			continue;
328 c3b318d0 2019-11-10 stsp 		cache->cache_hit++;
329 dac5c75e 2022-06-04 stsp 		if (i > 0) {
330 dac5c75e 2022-06-04 stsp 			struct got_cached_delta tmp;
331 dac5c75e 2022-06-04 stsp 			memcpy(&tmp, &head->entries[0], sizeof(tmp));
332 dac5c75e 2022-06-04 stsp 			memcpy(&head->entries[0], &head->entries[i],
333 dac5c75e 2022-06-04 stsp 			    sizeof(head->entries[0]));
334 dac5c75e 2022-06-04 stsp 			memcpy(&head->entries[i], &tmp,
335 dac5c75e 2022-06-04 stsp 			    sizeof(head->entries[i]));
336 dac5c75e 2022-06-04 stsp 			delta = &head->entries[0];
337 ab2f42e7 2019-11-10 stsp 		}
338 dac5c75e 2022-06-04 stsp 		*delta_data = delta->data;
339 dac5c75e 2022-06-04 stsp 		*delta_len = delta->len;
340 1aaa1562 2023-04-24 stsp 		if (fulltext && fulltext_len &&
341 1aaa1562 2023-04-24 stsp 		    delta->fulltext && delta->fulltext_len) {
342 1aaa1562 2023-04-24 stsp 			*fulltext = delta->fulltext;
343 1aaa1562 2023-04-24 stsp 			*fulltext_len = delta->fulltext_len;
344 1aaa1562 2023-04-24 stsp 			cache->cache_hit_fulltext++;
345 1aaa1562 2023-04-24 stsp 		}
346 1aaa1562 2023-04-24 stsp 
347 ab2f42e7 2019-11-10 stsp 		return;
348 ab2f42e7 2019-11-10 stsp 	}
349 c3b318d0 2019-11-10 stsp 
350 c3b318d0 2019-11-10 stsp 	cache->cache_miss++;
351 ab2f42e7 2019-11-10 stsp }