1 ab2f42e7 2019-11-10 stsp /*
  2 5aa81393 2020-01-06 stsp  * Copyright (c) 2019, 2020 Stefan Sperling <stsp@openbsd.org>
  3 ab2f42e7 2019-11-10 stsp  *
  4 ab2f42e7 2019-11-10 stsp  * Permission to use, copy, modify, and distribute this software for any
  5 ab2f42e7 2019-11-10 stsp  * purpose with or without fee is hereby granted, provided that the above
  6 ab2f42e7 2019-11-10 stsp  * copyright notice and this permission notice appear in all copies.
  7 ab2f42e7 2019-11-10 stsp  *
  8 ab2f42e7 2019-11-10 stsp  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  9 ab2f42e7 2019-11-10 stsp  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 10 ab2f42e7 2019-11-10 stsp  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 11 ab2f42e7 2019-11-10 stsp  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 12 ab2f42e7 2019-11-10 stsp  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 13 ab2f42e7 2019-11-10 stsp  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 14 ab2f42e7 2019-11-10 stsp  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 15 ab2f42e7 2019-11-10 stsp  */
 16 ab2f42e7 2019-11-10 stsp 
 17 ab2f42e7 2019-11-10 stsp 
 18 ab2f42e7 2019-11-10 stsp #include <stdlib.h>
 19 ab2f42e7 2019-11-10 stsp #include <string.h>
 20 ab2f42e7 2019-11-10 stsp #include <sha1.h>
 21 ab2f42e7 2019-11-10 stsp #include <stdio.h>
 22 ab2f42e7 2019-11-10 stsp #include <zlib.h>
 23 ab2f42e7 2019-11-10 stsp #include <limits.h>
 24 ab2f42e7 2019-11-10 stsp #include <time.h>
 25 ab2f42e7 2019-11-10 stsp 
 26 dd038bc6 2021-09-21 thomas.ad #include "got_compat.h"
 27 dd038bc6 2021-09-21 thomas.ad 
 28 ab2f42e7 2019-11-10 stsp #include "got_object.h"
 29 ab2f42e7 2019-11-10 stsp #include "got_error.h"
 30 ab2f42e7 2019-11-10 stsp 
 31 ab2f42e7 2019-11-10 stsp #include "got_lib_delta.h"
 32 ab2f42e7 2019-11-10 stsp #include "got_lib_inflate.h"
 33 ab2f42e7 2019-11-10 stsp #include "got_lib_object.h"
 34 ab2f42e7 2019-11-10 stsp #include "got_lib_delta_cache.h"
 35 ab2f42e7 2019-11-10 stsp 
 36 ab2f42e7 2019-11-10 stsp #ifndef nitems
 37 ab2f42e7 2019-11-10 stsp #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
 38 ab2f42e7 2019-11-10 stsp #endif
 39 ab2f42e7 2019-11-10 stsp 
 40 ab2f42e7 2019-11-10 stsp struct got_delta_cache_element {
 41 ab2f42e7 2019-11-10 stsp 	TAILQ_ENTRY(got_delta_cache_element) entry;
 42 ab2f42e7 2019-11-10 stsp 	off_t delta_data_offset;
 43 ab2f42e7 2019-11-10 stsp 	uint8_t *delta_data;
 44 ab2f42e7 2019-11-10 stsp 	size_t delta_len;
 45 ab2f42e7 2019-11-10 stsp };
 46 ab2f42e7 2019-11-10 stsp 
 47 ab2f42e7 2019-11-10 stsp TAILQ_HEAD(got_delta_cache_head, got_delta_cache_element);
 48 ab2f42e7 2019-11-10 stsp 
 49 ab2f42e7 2019-11-10 stsp struct got_delta_cache {
 50 ab2f42e7 2019-11-10 stsp 	struct got_delta_cache_head entries;
 51 ab2f42e7 2019-11-10 stsp 	int nelem;
 52 ab2f42e7 2019-11-10 stsp 	int maxelem;
 53 ab2f42e7 2019-11-10 stsp 	size_t maxelemsize;
 54 c3b318d0 2019-11-10 stsp 	int cache_search;
 55 c3b318d0 2019-11-10 stsp 	int cache_hit;
 56 c3b318d0 2019-11-10 stsp 	int cache_miss;
 57 c3b318d0 2019-11-10 stsp 	int cache_evict;
 58 c3b318d0 2019-11-10 stsp 	int cache_toolarge;
 59 ab2f42e7 2019-11-10 stsp };
 60 ab2f42e7 2019-11-10 stsp 
 61 ab2f42e7 2019-11-10 stsp struct got_delta_cache *
 62 ab2f42e7 2019-11-10 stsp got_delta_cache_alloc(int maxelem, size_t maxelemsize)
 63 ab2f42e7 2019-11-10 stsp {
 64 ab2f42e7 2019-11-10 stsp 	struct got_delta_cache *cache;
 65 ab2f42e7 2019-11-10 stsp 
 66 ab2f42e7 2019-11-10 stsp 	cache = calloc(1, sizeof(*cache));
 67 ab2f42e7 2019-11-10 stsp 	if (cache == NULL)
 68 ab2f42e7 2019-11-10 stsp 		return NULL;
 69 ab2f42e7 2019-11-10 stsp 
 70 ab2f42e7 2019-11-10 stsp 	TAILQ_INIT(&cache->entries);
 71 ab2f42e7 2019-11-10 stsp 	cache->maxelem = maxelem;
 72 ab2f42e7 2019-11-10 stsp 	cache->maxelemsize = maxelemsize;
 73 ab2f42e7 2019-11-10 stsp 	return cache;
 74 ab2f42e7 2019-11-10 stsp }
 75 ab2f42e7 2019-11-10 stsp 
 76 ab2f42e7 2019-11-10 stsp void
 77 ab2f42e7 2019-11-10 stsp got_delta_cache_free(struct got_delta_cache *cache)
 78 ab2f42e7 2019-11-10 stsp {
 79 ab2f42e7 2019-11-10 stsp 	struct got_delta_cache_element *entry;
 80 ab2f42e7 2019-11-10 stsp 
 81 c3b318d0 2019-11-10 stsp #ifdef GOT_OBJ_CACHE_DEBUG
 82 c3b318d0 2019-11-10 stsp 	fprintf(stderr, "%s: delta cache: %d elements, %d searches, %d hits, "
 83 c3b318d0 2019-11-10 stsp 	    "%d missed, %d evicted, %d too large\n", getprogname(), cache->nelem,
 84 c3b318d0 2019-11-10 stsp 	    cache->cache_search, cache->cache_hit, cache->cache_miss,
 85 c3b318d0 2019-11-10 stsp 	    cache->cache_evict, cache->cache_toolarge);
 86 c3b318d0 2019-11-10 stsp #endif
 87 ab2f42e7 2019-11-10 stsp 	while (!TAILQ_EMPTY(&cache->entries)) {
 88 ab2f42e7 2019-11-10 stsp 		entry = TAILQ_FIRST(&cache->entries);
 89 ab2f42e7 2019-11-10 stsp 		TAILQ_REMOVE(&cache->entries, entry, entry);
 90 ab2f42e7 2019-11-10 stsp 		free(entry->delta_data);
 91 ab2f42e7 2019-11-10 stsp 		free(entry);
 92 ab2f42e7 2019-11-10 stsp 	}
 93 ab2f42e7 2019-11-10 stsp 	free(cache);
 94 ab2f42e7 2019-11-10 stsp }
 95 ab2f42e7 2019-11-10 stsp 
 96 fa7a529e 2020-01-06 stsp #ifndef GOT_NO_OBJ_CACHE
 97 ab2f42e7 2019-11-10 stsp static void
 98 ab2f42e7 2019-11-10 stsp remove_least_used_element(struct got_delta_cache *cache)
 99 ab2f42e7 2019-11-10 stsp {
100 ab2f42e7 2019-11-10 stsp 	struct got_delta_cache_element *entry;
101 ab2f42e7 2019-11-10 stsp 
102 ab2f42e7 2019-11-10 stsp 	if (cache->nelem == 0)
103 ab2f42e7 2019-11-10 stsp 		return;
104 ab2f42e7 2019-11-10 stsp 
105 ab2f42e7 2019-11-10 stsp 	entry = TAILQ_LAST(&cache->entries, got_delta_cache_head);
106 ab2f42e7 2019-11-10 stsp 	TAILQ_REMOVE(&cache->entries, entry, entry);
107 ab2f42e7 2019-11-10 stsp 	free(entry->delta_data);
108 ab2f42e7 2019-11-10 stsp 	free(entry);
109 ab2f42e7 2019-11-10 stsp 	cache->nelem--;
110 c3b318d0 2019-11-10 stsp 	cache->cache_evict++;
111 ab2f42e7 2019-11-10 stsp }
112 fa7a529e 2020-01-06 stsp #endif
113 ab2f42e7 2019-11-10 stsp 
114 ab2f42e7 2019-11-10 stsp const struct got_error *
115 ab2f42e7 2019-11-10 stsp got_delta_cache_add(struct got_delta_cache *cache,
116 ab2f42e7 2019-11-10 stsp     off_t delta_data_offset, uint8_t *delta_data, size_t delta_len)
117 ab2f42e7 2019-11-10 stsp {
118 fa7a529e 2020-01-06 stsp #ifdef GOT_NO_OBJ_CACHE
119 fa7a529e 2020-01-06 stsp 	return got_error(GOT_ERR_NO_SPACE);
120 fa7a529e 2020-01-06 stsp #else
121 ab2f42e7 2019-11-10 stsp 	struct got_delta_cache_element *entry;
122 ab2f42e7 2019-11-10 stsp 
123 c3b318d0 2019-11-10 stsp 	if (delta_len > cache->maxelemsize) {
124 c3b318d0 2019-11-10 stsp 		cache->cache_toolarge++;
125 ab2f42e7 2019-11-10 stsp 		return got_error(GOT_ERR_NO_SPACE);
126 c3b318d0 2019-11-10 stsp 	}
127 ab2f42e7 2019-11-10 stsp 
128 ab2f42e7 2019-11-10 stsp 	if (cache->nelem >= cache->maxelem)
129 ab2f42e7 2019-11-10 stsp 		remove_least_used_element(cache);
130 ab2f42e7 2019-11-10 stsp 
131 ab2f42e7 2019-11-10 stsp 	entry = calloc(1, sizeof(*entry));
132 ab2f42e7 2019-11-10 stsp 	if (entry == NULL)
133 ab2f42e7 2019-11-10 stsp 		return got_error_from_errno("calloc");
134 ab2f42e7 2019-11-10 stsp 
135 ab2f42e7 2019-11-10 stsp 	entry->delta_data_offset = delta_data_offset;
136 ab2f42e7 2019-11-10 stsp 	entry->delta_data = delta_data;
137 ab2f42e7 2019-11-10 stsp 	entry->delta_len = delta_len;
138 ab2f42e7 2019-11-10 stsp 
139 ab2f42e7 2019-11-10 stsp 	TAILQ_INSERT_HEAD(&cache->entries, entry, entry);
140 ab2f42e7 2019-11-10 stsp 	cache->nelem++;
141 ab2f42e7 2019-11-10 stsp 	return NULL;
142 fa7a529e 2020-01-06 stsp #endif
143 ab2f42e7 2019-11-10 stsp }
144 ab2f42e7 2019-11-10 stsp 
145 ab2f42e7 2019-11-10 stsp void
146 ab2f42e7 2019-11-10 stsp got_delta_cache_get(uint8_t **delta_data, size_t *delta_len,
147 ab2f42e7 2019-11-10 stsp     struct got_delta_cache *cache, off_t delta_data_offset)
148 ab2f42e7 2019-11-10 stsp {
149 ab2f42e7 2019-11-10 stsp 	struct got_delta_cache_element *entry;
150 ab2f42e7 2019-11-10 stsp 
151 c3b318d0 2019-11-10 stsp 	cache->cache_search++;
152 ab2f42e7 2019-11-10 stsp 	*delta_data = NULL;
153 ab2f42e7 2019-11-10 stsp 	*delta_len = 0;
154 ab2f42e7 2019-11-10 stsp 	TAILQ_FOREACH(entry, &cache->entries, entry) {
155 ab2f42e7 2019-11-10 stsp 		if (entry->delta_data_offset != delta_data_offset)
156 ab2f42e7 2019-11-10 stsp 			continue;
157 c3b318d0 2019-11-10 stsp 		cache->cache_hit++;
158 ab2f42e7 2019-11-10 stsp 		if (entry != TAILQ_FIRST(&cache->entries)) {
159 ab2f42e7 2019-11-10 stsp 			TAILQ_REMOVE(&cache->entries, entry, entry);
160 ab2f42e7 2019-11-10 stsp 			TAILQ_INSERT_HEAD(&cache->entries, entry, entry);
161 ab2f42e7 2019-11-10 stsp 		}
162 ab2f42e7 2019-11-10 stsp 		*delta_data = entry->delta_data;
163 ab2f42e7 2019-11-10 stsp 		*delta_len = entry->delta_len;
164 ab2f42e7 2019-11-10 stsp 		return;
165 ab2f42e7 2019-11-10 stsp 	}
166 c3b318d0 2019-11-10 stsp 
167 c3b318d0 2019-11-10 stsp 	cache->cache_miss++;
168 ab2f42e7 2019-11-10 stsp }