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 	int cache_maxtoolarge;
69 	unsigned int flags;
70 #define GOT_DELTA_CACHE_F_NOMEM	0x01
71 	SIPHASH_KEY key;
72 };
73 
74 const struct got_error *
75 got_delta_cache_alloc(struct got_delta_cache **new)
76 {
77 	const struct got_error *err;
78 	struct got_delta_cache *cache;
79 
80 	*new = NULL;
81 
82 	cache = calloc(1, sizeof(*cache));
83 	if (cache == NULL)
84 		return got_error_from_errno("calloc");
85 
86 	cache->buckets = calloc(GOT_DELTA_CACHE_MIN_BUCKETS,
87 	    sizeof(cache->buckets[0]));
88 	if (cache->buckets == NULL) {
89 		err = got_error_from_errno("calloc");
90 		free(cache);
91 		return err;
92 	}
93 	cache->nbuckets = GOT_DELTA_CACHE_MIN_BUCKETS;
94 
95 	arc4random_buf(&cache->key, sizeof(cache->key));
96 	*new = cache;
97 	return NULL;
98 }
99 
100 void
101 got_delta_cache_free(struct got_delta_cache *cache)
102 {
103 	struct got_cached_delta *delta;
104 	unsigned int i;
105 
106 #ifdef GOT_DELTA_CACHE_DEBUG
107 	fprintf(stderr, "%s: delta cache: %u elements, %d searches, %d hits, "
108 	    "%d missed, %d evicted, %d too large (max %d)\n", getprogname(),
109 	    cache->totelem, cache->cache_search, cache->cache_hit,
110 	    cache->cache_miss, cache->cache_evict, cache->cache_toolarge,
111 	    cache->cache_maxtoolarge);
112 #endif
113 	for (i = 0; i < cache->nbuckets; i++) {
114 		struct got_delta_cache_head *head;
115 		int j;
116 		head = &cache->buckets[i];
117 		for (j = 0; j < head->nchain; j++) {
118 			delta = &head->entries[j];
119 			free(delta->data);
120 		}
121 	}
122 	free(cache->buckets);
123 	free(cache);
124 }
125 
126 static uint64_t
127 delta_cache_hash(struct got_delta_cache *cache, off_t delta_offset)
128 {
129 	return SipHash24(&cache->key, &delta_offset, sizeof(delta_offset));
130 }
131 
132 #ifndef GOT_NO_DELTA_CACHE
133 static const struct got_error *
134 delta_cache_resize(struct got_delta_cache *cache, unsigned int nbuckets)
135 {
136 	struct got_delta_cache_head *buckets;
137 	size_t i;
138 
139 	buckets = calloc(nbuckets, sizeof(buckets[0]));
140 	if (buckets == NULL) {
141 		if (errno != ENOMEM)
142 			return got_error_from_errno("calloc");
143 		/* Proceed with our current amount of hash buckets. */
144 		cache->flags |= GOT_DELTA_CACHE_F_NOMEM;
145 		return NULL;
146 	}
147 
148 	arc4random_buf(&cache->key, sizeof(cache->key));
149 
150 	for (i = 0; i < cache->nbuckets; i++) {
151 		unsigned int j;
152 		for (j = 0; j < cache->buckets[i].nchain; j++) {
153 			struct got_delta_cache_head *head;
154 			struct got_cached_delta *delta;
155 			uint64_t idx;
156 			delta = &cache->buckets[i].entries[j];
157 			idx = delta_cache_hash(cache, delta->offset) % nbuckets;
158 			head = &buckets[idx];
159 			if (head->nchain < nitems(head->entries)) {
160 				struct got_cached_delta *new_delta;
161 				new_delta = &head->entries[head->nchain];
162 				memcpy(new_delta, delta, sizeof(*new_delta));
163 				head->nchain++;
164 			} else {
165 				free(delta->data);
166 				cache->totelem--;
167 			}
168 		}
169 	}
170 
171 	free(cache->buckets);
172 	cache->buckets = buckets;
173 	cache->nbuckets = nbuckets;
174 	return NULL;
175 }
176 
177 static const struct got_error *
178 delta_cache_grow(struct got_delta_cache *cache)
179 {
180 	unsigned int nbuckets;
181 
182 	if ((cache->flags & GOT_DELTA_CACHE_F_NOMEM) ||
183 	    cache->nbuckets == GOT_DELTA_CACHE_MAX_BUCKETS)
184 		return NULL;
185 
186 	if (cache->nbuckets >= GOT_DELTA_CACHE_MAX_BUCKETS / 2)
187 		nbuckets = GOT_DELTA_CACHE_MAX_BUCKETS;
188 	else
189 		nbuckets = cache->nbuckets * 2;
190 
191 	return delta_cache_resize(cache, nbuckets);
192 }
193 #endif
194 
195 const struct got_error *
196 got_delta_cache_add(struct got_delta_cache *cache,
197     off_t delta_data_offset, uint8_t *delta_data, size_t delta_len)
198 {
199 #ifdef GOT_NO_DELTA_CACHE
200 	return got_error(GOT_ERR_NO_SPACE);
201 #else
202 	const struct got_error *err = NULL;
203 	struct got_cached_delta *delta;
204 	struct got_delta_cache_head *head;
205 	uint64_t idx;
206 
207 	if (delta_len > GOT_DELTA_CACHE_MAX_DELTA_SIZE) {
208 		cache->cache_toolarge++;
209 		if (delta_len > cache->cache_maxtoolarge)
210 			cache->cache_maxtoolarge = delta_len;
211 		return got_error(GOT_ERR_NO_SPACE);
212 	}
213 
214 	if (cache->nbuckets * 3 < cache->totelem * 4) {
215 		err = delta_cache_grow(cache);
216 		if (err)
217 			return err;
218 	}
219 
220 	idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
221 	head = &cache->buckets[idx];
222 	if (head->nchain >= nitems(head->entries)) {
223 		delta = &head->entries[head->nchain - 1];
224 		free(delta->data);
225 		memset(delta, 0, sizeof(*delta));
226 		head->nchain--;
227 		cache->totelem--;
228 		cache->cache_evict++;
229 	}
230 
231 	delta = &head->entries[head->nchain];
232 	delta->offset = delta_data_offset;
233 	delta->data = delta_data;
234 	delta->len = delta_len;
235 	head->nchain++;
236 	cache->totelem++;
237 
238 	return NULL;
239 #endif
240 }
241 
242 void
243 got_delta_cache_get(uint8_t **delta_data, size_t *delta_len,
244     struct got_delta_cache *cache, off_t delta_data_offset)
245 {
246 	uint64_t idx;
247 	struct got_delta_cache_head *head;
248 	struct got_cached_delta *delta;
249 	int i;
250 
251 	idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
252 	head = &cache->buckets[idx];
253 
254 	cache->cache_search++;
255 	*delta_data = NULL;
256 	*delta_len = 0;
257 	for (i = 0; i < head->nchain; i++) {
258 		delta = &head->entries[i];
259 		if (delta->offset != delta_data_offset)
260 			continue;
261 		cache->cache_hit++;
262 		if (i > 0) {
263 			struct got_cached_delta tmp;
264 			memcpy(&tmp, &head->entries[0], sizeof(tmp));
265 			memcpy(&head->entries[0], &head->entries[i],
266 			    sizeof(head->entries[0]));
267 			memcpy(&head->entries[i], &tmp,
268 			    sizeof(head->entries[i]));
269 			delta = &head->entries[0];
270 		}
271 		*delta_data = delta->data;
272 		*delta_len = delta->len;
273 		return;
274 	}
275 
276 	cache->cache_miss++;
277 }