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