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 
18 #include <stdlib.h>
19 #include <string.h>
20 #include <sha1.h>
21 #include <stdio.h>
22 #include <zlib.h>
23 #include <limits.h>
24 #include <time.h>
25 
26 #include "got_compat.h"
27 
28 #include "got_object.h"
29 #include "got_error.h"
30 
31 #include "got_lib_delta.h"
32 #include "got_lib_inflate.h"
33 #include "got_lib_object.h"
34 #include "got_lib_delta_cache.h"
35 
36 #ifndef nitems
37 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
38 #endif
39 
40 struct got_delta_cache_element {
41 	TAILQ_ENTRY(got_delta_cache_element) entry;
42 	off_t delta_data_offset;
43 	uint8_t *delta_data;
44 	size_t delta_len;
45 };
46 
47 TAILQ_HEAD(got_delta_cache_head, got_delta_cache_element);
48 
49 struct got_delta_cache {
50 	struct got_delta_cache_head entries;
51 	int nelem;
52 	int maxelem;
53 	size_t maxelemsize;
54 	int cache_search;
55 	int cache_hit;
56 	int cache_miss;
57 	int cache_evict;
58 	int cache_toolarge;
59 };
60 
61 struct got_delta_cache *
62 got_delta_cache_alloc(int maxelem, size_t maxelemsize)
63 {
64 	struct got_delta_cache *cache;
65 
66 	cache = calloc(1, sizeof(*cache));
67 	if (cache == NULL)
68 		return NULL;
69 
70 	TAILQ_INIT(&cache->entries);
71 	cache->maxelem = maxelem;
72 	cache->maxelemsize = maxelemsize;
73 	return cache;
74 }
75 
76 void
77 got_delta_cache_free(struct got_delta_cache *cache)
78 {
79 	struct got_delta_cache_element *entry;
80 
81 #ifdef GOT_OBJ_CACHE_DEBUG
82 	fprintf(stderr, "%s: delta cache: %d elements, %d searches, %d hits, "
83 	    "%d missed, %d evicted, %d too large\n", getprogname(), cache->nelem,
84 	    cache->cache_search, cache->cache_hit, cache->cache_miss,
85 	    cache->cache_evict, cache->cache_toolarge);
86 #endif
87 	while (!TAILQ_EMPTY(&cache->entries)) {
88 		entry = TAILQ_FIRST(&cache->entries);
89 		TAILQ_REMOVE(&cache->entries, entry, entry);
90 		free(entry->delta_data);
91 		free(entry);
92 	}
93 	free(cache);
94 }
95 
96 #ifndef GOT_NO_OBJ_CACHE
97 static void
98 remove_least_used_element(struct got_delta_cache *cache)
99 {
100 	struct got_delta_cache_element *entry;
101 
102 	if (cache->nelem == 0)
103 		return;
104 
105 	entry = TAILQ_LAST(&cache->entries, got_delta_cache_head);
106 	TAILQ_REMOVE(&cache->entries, entry, entry);
107 	free(entry->delta_data);
108 	free(entry);
109 	cache->nelem--;
110 	cache->cache_evict++;
111 }
112 #endif
113 
114 const struct got_error *
115 got_delta_cache_add(struct got_delta_cache *cache,
116     off_t delta_data_offset, uint8_t *delta_data, size_t delta_len)
117 {
118 #ifdef GOT_NO_OBJ_CACHE
119 	return got_error(GOT_ERR_NO_SPACE);
120 #else
121 	struct got_delta_cache_element *entry;
122 
123 	if (delta_len > cache->maxelemsize) {
124 		cache->cache_toolarge++;
125 		return got_error(GOT_ERR_NO_SPACE);
126 	}
127 
128 	if (cache->nelem >= cache->maxelem)
129 		remove_least_used_element(cache);
130 
131 	entry = calloc(1, sizeof(*entry));
132 	if (entry == NULL)
133 		return got_error_from_errno("calloc");
134 
135 	entry->delta_data_offset = delta_data_offset;
136 	entry->delta_data = delta_data;
137 	entry->delta_len = delta_len;
138 
139 	TAILQ_INSERT_HEAD(&cache->entries, entry, entry);
140 	cache->nelem++;
141 	return NULL;
142 #endif
143 }
144 
145 void
146 got_delta_cache_get(uint8_t **delta_data, size_t *delta_len,
147     struct got_delta_cache *cache, off_t delta_data_offset)
148 {
149 	struct got_delta_cache_element *entry;
150 
151 	cache->cache_search++;
152 	*delta_data = NULL;
153 	*delta_len = 0;
154 	TAILQ_FOREACH(entry, &cache->entries, entry) {
155 		if (entry->delta_data_offset != delta_data_offset)
156 			continue;
157 		cache->cache_hit++;
158 		if (entry != TAILQ_FIRST(&cache->entries)) {
159 			TAILQ_REMOVE(&cache->entries, entry, entry);
160 			TAILQ_INSERT_HEAD(&cache->entries, entry, entry);
161 		}
162 		*delta_data = entry->delta_data;
163 		*delta_len = entry->delta_len;
164 		return;
165 	}
166 
167 	cache->cache_miss++;
168 }