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