1 eb77ee11 2018-07-08 stsp /*
  2 eb77ee11 2018-07-08 stsp  * Copyright (c) 2018 Stefan Sperling <stsp@openbsd.org>
  3 eb77ee11 2018-07-08 stsp  *
  4 eb77ee11 2018-07-08 stsp  * Permission to use, copy, modify, and distribute this software for any
  5 eb77ee11 2018-07-08 stsp  * purpose with or without fee is hereby granted, provided that the above
  6 eb77ee11 2018-07-08 stsp  * copyright notice and this permission notice appear in all copies.
  7 eb77ee11 2018-07-08 stsp  *
  8 eb77ee11 2018-07-08 stsp  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  9 eb77ee11 2018-07-08 stsp  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 10 eb77ee11 2018-07-08 stsp  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 11 eb77ee11 2018-07-08 stsp  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 12 eb77ee11 2018-07-08 stsp  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 13 eb77ee11 2018-07-08 stsp  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 14 eb77ee11 2018-07-08 stsp  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 15 eb77ee11 2018-07-08 stsp  */
 16 eb77ee11 2018-07-08 stsp 
 17 eb77ee11 2018-07-08 stsp #include <sys/queue.h>
 18 eb77ee11 2018-07-08 stsp 
 19 eb77ee11 2018-07-08 stsp #include <stdlib.h>
 20 eb77ee11 2018-07-08 stsp #include <string.h>
 21 eb77ee11 2018-07-08 stsp #include <sha1.h>
 22 eb77ee11 2018-07-08 stsp #include <stdio.h>
 23 eb77ee11 2018-07-08 stsp #include <zlib.h>
 24 eb77ee11 2018-07-08 stsp #include <limits.h>
 25 eb77ee11 2018-07-08 stsp #include <time.h>
 26 eb77ee11 2018-07-08 stsp 
 27 eb77ee11 2018-07-08 stsp #include "got_object.h"
 28 eb77ee11 2018-07-08 stsp #include "got_error.h"
 29 eb77ee11 2018-07-08 stsp 
 30 eb77ee11 2018-07-08 stsp #include "got_lib_delta.h"
 31 63581804 2018-07-09 stsp #include "got_lib_inflate.h"
 32 eb77ee11 2018-07-08 stsp #include "got_lib_object.h"
 33 eb77ee11 2018-07-08 stsp #include "got_lib_object_idcache.h"
 34 eb77ee11 2018-07-08 stsp 
 35 eb77ee11 2018-07-08 stsp #ifndef nitems
 36 eb77ee11 2018-07-08 stsp #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
 37 eb77ee11 2018-07-08 stsp #endif
 38 eb77ee11 2018-07-08 stsp 
 39 eb77ee11 2018-07-08 stsp struct got_object_idcache_element {
 40 eb77ee11 2018-07-08 stsp 	TAILQ_ENTRY(got_object_idcache_element) entry;
 41 eb77ee11 2018-07-08 stsp 	struct got_object_id id;
 42 eb77ee11 2018-07-08 stsp 	void *data;	/* API user data */
 43 eb77ee11 2018-07-08 stsp };
 44 eb77ee11 2018-07-08 stsp 
 45 eb77ee11 2018-07-08 stsp TAILQ_HEAD(got_object_idcache_head, got_object_idcache_element);
 46 eb77ee11 2018-07-08 stsp 
 47 eb77ee11 2018-07-08 stsp struct got_object_idcache {
 48 bb7182a5 2018-09-16 stsp 	/*
 49 bb7182a5 2018-09-16 stsp 	 * The cache is implemented as a collection of 256 lists.
 50 bb7182a5 2018-09-16 stsp 	 * The value of the first byte of an object ID determines
 51 bb7182a5 2018-09-16 stsp 	 * which of these lists an object ID is stored in.
 52 bb7182a5 2018-09-16 stsp 	 */
 53 bb7182a5 2018-09-16 stsp 	struct got_object_idcache_head entries[0xff + 1];
 54 bb7182a5 2018-09-16 stsp 	int nelem[0xff + 1];
 55 bb7182a5 2018-09-16 stsp 	int totelem;
 56 eb77ee11 2018-07-08 stsp 	int maxelem;
 57 eb77ee11 2018-07-08 stsp };
 58 eb77ee11 2018-07-08 stsp 
 59 eb77ee11 2018-07-08 stsp struct got_object_idcache *
 60 eb77ee11 2018-07-08 stsp got_object_idcache_alloc(int maxelem)
 61 eb77ee11 2018-07-08 stsp {
 62 eb77ee11 2018-07-08 stsp 	struct got_object_idcache *cache;
 63 bb7182a5 2018-09-16 stsp 	int i;
 64 eb77ee11 2018-07-08 stsp 
 65 eb77ee11 2018-07-08 stsp 	cache = calloc(1, sizeof(*cache));
 66 eb77ee11 2018-07-08 stsp 	if (cache == NULL)
 67 eb77ee11 2018-07-08 stsp 		return NULL;
 68 eb77ee11 2018-07-08 stsp 
 69 bb7182a5 2018-09-16 stsp 	for (i = 0; i < nitems(cache->entries); i++)
 70 bb7182a5 2018-09-16 stsp 		TAILQ_INIT(&cache->entries[i]);
 71 eb77ee11 2018-07-08 stsp 	cache->maxelem = maxelem;
 72 eb77ee11 2018-07-08 stsp 	return cache;
 73 eb77ee11 2018-07-08 stsp }
 74 eb77ee11 2018-07-08 stsp 
 75 eb77ee11 2018-07-08 stsp void
 76 eb77ee11 2018-07-08 stsp got_object_idcache_free(struct got_object_idcache *cache)
 77 eb77ee11 2018-07-08 stsp {
 78 eb77ee11 2018-07-08 stsp 	struct got_object_idcache_element *entry;
 79 bb7182a5 2018-09-16 stsp 	int i;
 80 eb77ee11 2018-07-08 stsp 
 81 bb7182a5 2018-09-16 stsp 	for (i = 0; i < nitems(cache->entries); i++) {
 82 bb7182a5 2018-09-16 stsp 		while (!TAILQ_EMPTY(&cache->entries[i])) {
 83 bb7182a5 2018-09-16 stsp 			entry = TAILQ_FIRST(&cache->entries[i]);
 84 bb7182a5 2018-09-16 stsp 			TAILQ_REMOVE(&cache->entries[i], entry, entry);
 85 bb7182a5 2018-09-16 stsp 			/* User data should be freed by caller. */
 86 bb7182a5 2018-09-16 stsp 			free(entry);
 87 bb7182a5 2018-09-16 stsp 		}
 88 eb77ee11 2018-07-08 stsp 	}
 89 eb77ee11 2018-07-08 stsp 	free(cache);
 90 eb77ee11 2018-07-08 stsp }
 91 eb77ee11 2018-07-08 stsp 
 92 eb77ee11 2018-07-08 stsp const struct got_error *
 93 eb77ee11 2018-07-08 stsp got_object_idcache_add(struct got_object_idcache *cache,
 94 eb77ee11 2018-07-08 stsp     struct got_object_id *id, void *data)
 95 eb77ee11 2018-07-08 stsp {
 96 eb77ee11 2018-07-08 stsp 	struct got_object_idcache_element *entry;
 97 bb7182a5 2018-09-16 stsp 	uint8_t i = id->sha1[0];
 98 eb77ee11 2018-07-08 stsp 
 99 bb7182a5 2018-09-16 stsp 	if (cache->totelem >= cache->maxelem)
100 720ad641 2018-07-23 stsp 		return got_error(GOT_ERR_NO_SPACE);
101 eb77ee11 2018-07-08 stsp 
102 eb77ee11 2018-07-08 stsp 	entry = calloc(1, sizeof(*entry));
103 eb77ee11 2018-07-08 stsp 	if (entry == NULL)
104 eb77ee11 2018-07-08 stsp 		return got_error_from_errno();
105 eb77ee11 2018-07-08 stsp 
106 eb77ee11 2018-07-08 stsp 	memcpy(&entry->id, id, sizeof(entry->id));
107 eb77ee11 2018-07-08 stsp 	entry->data = data;
108 eb77ee11 2018-07-08 stsp 
109 bb7182a5 2018-09-16 stsp 	TAILQ_INSERT_HEAD(&cache->entries[i], entry, entry);
110 bb7182a5 2018-09-16 stsp 	cache->nelem[i]++;
111 bb7182a5 2018-09-16 stsp 	cache->totelem++;
112 eb77ee11 2018-07-08 stsp 	return NULL;
113 eb77ee11 2018-07-08 stsp }
114 eb77ee11 2018-07-08 stsp 
115 eb77ee11 2018-07-08 stsp void *
116 eb77ee11 2018-07-08 stsp got_object_idcache_get(struct got_object_idcache *cache, struct got_object_id *id)
117 eb77ee11 2018-07-08 stsp {
118 eb77ee11 2018-07-08 stsp 	struct got_object_idcache_element *entry;
119 bb7182a5 2018-09-16 stsp 	uint8_t i = id->sha1[0];
120 eb77ee11 2018-07-08 stsp 
121 bb7182a5 2018-09-16 stsp 	TAILQ_FOREACH(entry, &cache->entries[i], entry) {
122 c59b3346 2018-09-11 stsp 		if (memcmp(&entry->id.sha1, id->sha1, SHA1_DIGEST_LENGTH) != 0)
123 eb77ee11 2018-07-08 stsp 			continue;
124 bb7182a5 2018-09-16 stsp 		if (entry != TAILQ_FIRST(&cache->entries[i])) {
125 bb7182a5 2018-09-16 stsp 			TAILQ_REMOVE(&cache->entries[i], entry, entry);
126 bb7182a5 2018-09-16 stsp 			TAILQ_INSERT_HEAD(&cache->entries[i], entry, entry);
127 eb77ee11 2018-07-08 stsp 		}
128 eb77ee11 2018-07-08 stsp 		return entry->data;
129 eb77ee11 2018-07-08 stsp 	}
130 eb77ee11 2018-07-08 stsp 
131 eb77ee11 2018-07-08 stsp 	return NULL;
132 eb77ee11 2018-07-08 stsp }
133 eb77ee11 2018-07-08 stsp 
134 eb77ee11 2018-07-08 stsp const struct got_error *
135 eb77ee11 2018-07-08 stsp got_object_idcache_remove_least_used(void **data, struct got_object_idcache *cache)
136 eb77ee11 2018-07-08 stsp {
137 eb77ee11 2018-07-08 stsp 	struct got_object_idcache_element *entry;
138 bb7182a5 2018-09-16 stsp 	int i, idx = 0, maxelem = cache->nelem[0];
139 eb77ee11 2018-07-08 stsp 
140 eb77ee11 2018-07-08 stsp 	if (data)
141 eb77ee11 2018-07-08 stsp 		*data = NULL;
142 eb77ee11 2018-07-08 stsp 
143 bb7182a5 2018-09-16 stsp 	if (cache->totelem == 0)
144 eb77ee11 2018-07-08 stsp 		return got_error(GOT_ERR_NO_OBJ);
145 eb77ee11 2018-07-08 stsp 
146 bb7182a5 2018-09-16 stsp 	/* Remove least used element from longest list. */
147 bb7182a5 2018-09-16 stsp 	for (i = 0; i < nitems(cache->entries); i++) {
148 bb7182a5 2018-09-16 stsp 		if (maxelem < cache->nelem[i]) {
149 bb7182a5 2018-09-16 stsp 			idx = i;
150 bb7182a5 2018-09-16 stsp 			maxelem = cache->nelem[i];
151 bb7182a5 2018-09-16 stsp 		}
152 bb7182a5 2018-09-16 stsp 	}
153 bb7182a5 2018-09-16 stsp 	entry = TAILQ_LAST(&cache->entries[idx], got_object_idcache_head);
154 bb7182a5 2018-09-16 stsp 	TAILQ_REMOVE(&cache->entries[idx], entry, entry);
155 eb77ee11 2018-07-08 stsp 	if (data)
156 eb77ee11 2018-07-08 stsp 		*data = entry->data;
157 eb77ee11 2018-07-08 stsp 	free(entry);
158 bb7182a5 2018-09-16 stsp 	cache->nelem[idx]--;
159 bb7182a5 2018-09-16 stsp 	cache->totelem--;
160 eb77ee11 2018-07-08 stsp 	return NULL;
161 eb77ee11 2018-07-08 stsp }
162 eb77ee11 2018-07-08 stsp 
163 eb77ee11 2018-07-08 stsp int
164 eb77ee11 2018-07-08 stsp got_object_idcache_contains(struct got_object_idcache *cache,
165 eb77ee11 2018-07-08 stsp     struct got_object_id *id)
166 eb77ee11 2018-07-08 stsp {
167 eb77ee11 2018-07-08 stsp 	struct got_object_idcache_element *entry;
168 bb7182a5 2018-09-16 stsp 	uint8_t i = id->sha1[0];
169 eb77ee11 2018-07-08 stsp 
170 bb7182a5 2018-09-16 stsp 	TAILQ_FOREACH(entry, &cache->entries[i], entry) {
171 c59b3346 2018-09-11 stsp 		if (memcmp(&entry->id.sha1, id->sha1, SHA1_DIGEST_LENGTH) == 0)
172 eb77ee11 2018-07-08 stsp 			return 1;
173 eb77ee11 2018-07-08 stsp 	}
174 eb77ee11 2018-07-08 stsp 
175 eb77ee11 2018-07-08 stsp 	return 0;
176 eb77ee11 2018-07-08 stsp }
177 eb77ee11 2018-07-08 stsp 
178 eb77ee11 2018-07-08 stsp void got_object_idcache_for_each(struct got_object_idcache *cache,
179 eb77ee11 2018-07-08 stsp     void (*cb)(struct got_object_id *, void *, void *), void *arg)
180 eb77ee11 2018-07-08 stsp {
181 eb77ee11 2018-07-08 stsp 	struct got_object_idcache_element *entry;
182 bb7182a5 2018-09-16 stsp 	int i;
183 eb77ee11 2018-07-08 stsp 
184 bb7182a5 2018-09-16 stsp 	for (i = 0; i < nitems(cache->entries); i++) {
185 bb7182a5 2018-09-16 stsp 		TAILQ_FOREACH(entry, &cache->entries[i], entry)
186 bb7182a5 2018-09-16 stsp 			cb(&entry->id, entry->data, arg);
187 bb7182a5 2018-09-16 stsp 	}
188 eb77ee11 2018-07-08 stsp }
189 eb77ee11 2018-07-08 stsp 
190 eb77ee11 2018-07-08 stsp int
191 bb7182a5 2018-09-16 stsp got_object_idcache_num_elements(struct got_object_idcache *cache)
192 eb77ee11 2018-07-08 stsp {
193 bb7182a5 2018-09-16 stsp 	return cache->totelem;
194 eb77ee11 2018-07-08 stsp }