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