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 <sha1.h>
23 #include <sha2.h>
24 #include <stdio.h>
25 #include <zlib.h>
26 #include <limits.h>
27 #include <time.h>
28 #include <errno.h>
29 #include <siphash.h>
30 
31 #include "got_object.h"
32 #include "got_error.h"
33 
34 #include "got_lib_delta.h"
35 #include "got_lib_inflate.h"
36 #include "got_lib_object.h"
37 #include "got_lib_delta_cache.h"
38 
39 #ifndef nitems
40 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
41 #endif
42 
43 #define GOT_DELTA_CACHE_MIN_BUCKETS	64
44 #define GOT_DELTA_CACHE_MAX_BUCKETS	2048
45 #define GOT_DELTA_CACHE_MAX_CHAIN	2
46 #define GOT_DELTA_CACHE_MAX_DELTA_SIZE	1024
47 
48 struct got_cached_delta {
49 	off_t offset;
50 	uint8_t *data;
51 	size_t len;
52 };
53 
54 struct got_delta_cache_head {
55 	struct got_cached_delta entries[GOT_DELTA_CACHE_MAX_CHAIN];
56 	unsigned int nchain;
57 };
58 
59 struct got_delta_cache {
60 	struct got_delta_cache_head *buckets;
61 	unsigned int nbuckets;
62 	unsigned int totelem;
63 	int cache_search;
64 	int cache_hit;
65 	int cache_miss;
66 	int cache_evict;
67 	int cache_toolarge;
68 	unsigned int flags;
69 #define GOT_DELTA_CACHE_F_NOMEM	0x01
70 	SIPHASH_KEY key;
71 };
72 
73 const struct got_error *
74 got_delta_cache_alloc(struct got_delta_cache **new)
75 {
76 	const struct got_error *err;
77 	struct got_delta_cache *cache;
78 
79 	*new = NULL;
80 
81 	cache = calloc(1, sizeof(*cache));
82 	if (cache == NULL)
83 		return got_error_from_errno("calloc");
84 
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");
89 		free(cache);
90 		return err;
91 	}
92 	cache->nbuckets = GOT_DELTA_CACHE_MIN_BUCKETS;
93 
94 	arc4random_buf(&cache->key, sizeof(cache->key));
95 	*new = cache;
96 	return NULL;
97 }
98 
99 void
100 got_delta_cache_free(struct got_delta_cache *cache)
101 {
102 	struct got_cached_delta *delta;
103 	unsigned int i;
104 
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\n", getprogname(),
108 	    cache->totelem, cache->cache_search, cache->cache_hit,
109 	    cache->cache_miss, cache->cache_evict, cache->cache_toolarge);
110 #endif
111 	for (i = 0; i < cache->nbuckets; i++) {
112 		struct got_delta_cache_head *head;
113 		int j;
114 		head = &cache->buckets[i];
115 		for (j = 0; j < head->nchain; j++) {
116 			delta = &head->entries[j];
117 			free(delta->data);
118 		}
119 	}
120 	free(cache->buckets);
121 	free(cache);
122 }
123 
124 static uint64_t
125 delta_cache_hash(struct got_delta_cache *cache, off_t delta_offset)
126 {
127 	return SipHash24(&cache->key, &delta_offset, sizeof(delta_offset));
128 }
129 
130 #ifndef GOT_NO_DELTA_CACHE
131 static const struct got_error *
132 delta_cache_resize(struct got_delta_cache *cache, unsigned int nbuckets)
133 {
134 	struct got_delta_cache_head *buckets;
135 	size_t i;
136 
137 	buckets = calloc(nbuckets, sizeof(buckets[0]));
138 	if (buckets == NULL) {
139 		if (errno != ENOMEM)
140 			return got_error_from_errno("calloc");
141 		/* Proceed with our current amount of hash buckets. */
142 		cache->flags |= GOT_DELTA_CACHE_F_NOMEM;
143 		return NULL;
144 	}
145 
146 	arc4random_buf(&cache->key, sizeof(cache->key));
147 
148 	for (i = 0; i < cache->nbuckets; i++) {
149 		unsigned int j;
150 		for (j = 0; j < cache->buckets[i].nchain; j++) {
151 			struct got_delta_cache_head *head;
152 			struct got_cached_delta *delta;
153 			uint64_t idx;
154 			delta = &cache->buckets[i].entries[j];
155 			idx = delta_cache_hash(cache, delta->offset) % nbuckets;
156 			head = &buckets[idx];
157 			if (head->nchain < nitems(head->entries)) {
158 				struct got_cached_delta *new_delta;
159 				new_delta = &head->entries[head->nchain];
160 				memcpy(new_delta, delta, sizeof(*new_delta));
161 				head->nchain++;
162 			} else {
163 				free(delta->data);
164 				cache->totelem--;
165 			}
166 		}
167 	}
168 
169 	free(cache->buckets);
170 	cache->buckets = buckets;
171 	cache->nbuckets = nbuckets;
172 	return NULL;
173 }
174 
175 static const struct got_error *
176 delta_cache_grow(struct got_delta_cache *cache)
177 {
178 	unsigned int nbuckets;
179 
180 	if ((cache->flags & GOT_DELTA_CACHE_F_NOMEM) ||
181 	    cache->nbuckets == GOT_DELTA_CACHE_MAX_BUCKETS)
182 		return NULL;
183 
184 	if (cache->nbuckets >= GOT_DELTA_CACHE_MAX_BUCKETS / 2)
185 		nbuckets = GOT_DELTA_CACHE_MAX_BUCKETS;
186 	else
187 		nbuckets = cache->nbuckets * 2;
188 
189 	return delta_cache_resize(cache, nbuckets);
190 }
191 #endif
192 
193 const struct got_error *
194 got_delta_cache_add(struct got_delta_cache *cache,
195     off_t delta_data_offset, uint8_t *delta_data, size_t delta_len)
196 {
197 #ifdef GOT_NO_DELTA_CACHE
198 	return got_error(GOT_ERR_NO_SPACE);
199 #else
200 	const struct got_error *err = NULL;
201 	struct got_cached_delta *delta;
202 	struct got_delta_cache_head *head;
203 	uint64_t idx;
204 
205 	if (delta_len > GOT_DELTA_CACHE_MAX_DELTA_SIZE) {
206 		cache->cache_toolarge++;
207 		return got_error(GOT_ERR_NO_SPACE);
208 	}
209 
210 	if (cache->nbuckets * 3 < cache->totelem * 4) {
211 		err = delta_cache_grow(cache);
212 		if (err)
213 			return err;
214 	}
215 
216 	idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
217 	head = &cache->buckets[idx];
218 	if (head->nchain >= nitems(head->entries)) {
219 		delta = &head->entries[head->nchain - 1];
220 		free(delta->data);
221 		memset(delta, 0, sizeof(*delta));
222 		head->nchain--;
223 		cache->totelem--;
224 		cache->cache_evict++;
225 	}
226 
227 	delta = &head->entries[head->nchain];
228 	delta->offset = delta_data_offset;
229 	delta->data = delta_data;
230 	delta->len = delta_len;
231 	head->nchain++;
232 	cache->totelem++;
233 
234 	return NULL;
235 #endif
236 }
237 
238 void
239 got_delta_cache_get(uint8_t **delta_data, size_t *delta_len,
240     struct got_delta_cache *cache, off_t delta_data_offset)
241 {
242 	uint64_t idx;
243 	struct got_delta_cache_head *head;
244 	struct got_cached_delta *delta;
245 	int i;
246 
247 	idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
248 	head = &cache->buckets[idx];
249 
250 	cache->cache_search++;
251 	*delta_data = NULL;
252 	*delta_len = 0;
253 	for (i = 0; i < head->nchain; i++) {
254 		delta = &head->entries[i];
255 		if (delta->offset != delta_data_offset)
256 			continue;
257 		cache->cache_hit++;
258 		if (i > 0) {
259 			struct got_cached_delta tmp;
260 			memcpy(&tmp, &head->entries[0], sizeof(tmp));
261 			memcpy(&head->entries[0], &head->entries[i],
262 			    sizeof(head->entries[0]));
263 			memcpy(&head->entries[i], &tmp,
264 			    sizeof(head->entries[i]));
265 			delta = &head->entries[0];
266 		}
267 		*delta_data = delta->data;
268 		*delta_len = delta->len;
269 		return;
270 	}
271 
272 	cache->cache_miss++;
273 }