1 /*
2  * Copyright (c) 2018 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 
27 #include "got_object.h"
28 #include "got_error.h"
29 
30 #include "got_lib_delta.h"
31 #include "got_lib_inflate.h"
32 #include "got_lib_object.h"
33 #include "got_lib_object_idcache.h"
34 
35 #ifndef nitems
36 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
37 #endif
38 
39 struct got_object_idcache_element {
40 	TAILQ_ENTRY(got_object_idcache_element) entry;
41 	struct got_object_id id;
42 	void *data;	/* API user data */
43 };
44 
45 TAILQ_HEAD(got_object_idcache_head, got_object_idcache_element);
46 
47 struct got_object_idcache {
48 	/*
49 	 * The cache is implemented as a collection of 256 lists.
50 	 * The value of the first byte of an object ID determines
51 	 * which of these lists an object ID is stored in.
52 	 */
53 	struct got_object_idcache_head entries[0xff + 1];
54 	int nelem[0xff + 1];
55 	int totelem;
56 	int maxelem;
57 };
58 
59 struct got_object_idcache *
60 got_object_idcache_alloc(int maxelem)
61 {
62 	struct got_object_idcache *cache;
63 	int i;
64 
65 	cache = calloc(1, sizeof(*cache));
66 	if (cache == NULL)
67 		return NULL;
68 
69 	for (i = 0; i < nitems(cache->entries); i++)
70 		TAILQ_INIT(&cache->entries[i]);
71 	cache->maxelem = maxelem;
72 	return cache;
73 }
74 
75 void
76 got_object_idcache_free(struct got_object_idcache *cache)
77 {
78 	struct got_object_idcache_element *entry;
79 	int i;
80 
81 	for (i = 0; i < nitems(cache->entries); i++) {
82 		while (!TAILQ_EMPTY(&cache->entries[i])) {
83 			entry = TAILQ_FIRST(&cache->entries[i]);
84 			TAILQ_REMOVE(&cache->entries[i], entry, entry);
85 			/* User data should be freed by caller. */
86 			free(entry);
87 		}
88 	}
89 	free(cache);
90 }
91 
92 const struct got_error *
93 got_object_idcache_add(struct got_object_idcache *cache,
94     struct got_object_id *id, void *data)
95 {
96 	struct got_object_idcache_element *entry;
97 	uint8_t i = id->sha1[0];
98 
99 	if (cache->totelem >= cache->maxelem)
100 		return got_error(GOT_ERR_NO_SPACE);
101 
102 	entry = malloc(sizeof(*entry));
103 	if (entry == NULL)
104 		return got_error_from_errno();
105 
106 	memcpy(&entry->id, id, sizeof(entry->id));
107 	entry->data = data;
108 
109 	TAILQ_INSERT_HEAD(&cache->entries[i], entry, entry);
110 	cache->nelem[i]++;
111 	cache->totelem++;
112 	return NULL;
113 }
114 
115 void *
116 got_object_idcache_get(struct got_object_idcache *cache, struct got_object_id *id)
117 {
118 	struct got_object_idcache_element *entry;
119 	uint8_t i = id->sha1[0];
120 
121 	TAILQ_FOREACH(entry, &cache->entries[i], entry) {
122 		if (memcmp(&entry->id.sha1, id->sha1, SHA1_DIGEST_LENGTH) != 0)
123 			continue;
124 		if (entry != TAILQ_FIRST(&cache->entries[i])) {
125 			TAILQ_REMOVE(&cache->entries[i], entry, entry);
126 			TAILQ_INSERT_HEAD(&cache->entries[i], entry, entry);
127 		}
128 		return entry->data;
129 	}
130 
131 	return NULL;
132 }
133 
134 const struct got_error *
135 got_object_idcache_remove_one(void **data, struct got_object_idcache *cache,
136     struct got_object_id *id)
137 {
138 	struct got_object_idcache_element *entry;
139 	uint8_t idx = id->sha1[0];
140 
141 	if (data)
142 		*data = NULL;
143 
144 	if (cache->totelem == 0)
145 		return got_error(GOT_ERR_NO_OBJ);
146 
147 	if (cache->nelem[idx] == 0) {
148 		/* Remove an element from the longest list. */
149 		int i, maxelem = cache->nelem[0];
150 		idx = 0;
151 		for (i = 0; i < nitems(cache->entries); i++) {
152 			if (maxelem < cache->nelem[i]) {
153 				idx = i;
154 				maxelem = cache->nelem[i];
155 			}
156 		}
157 	}
158 
159 	entry = TAILQ_LAST(&cache->entries[idx], got_object_idcache_head);
160 	TAILQ_REMOVE(&cache->entries[idx], entry, entry);
161 	if (data)
162 		*data = entry->data;
163 	free(entry);
164 	cache->nelem[idx]--;
165 	cache->totelem--;
166 	return NULL;
167 }
168 
169 int
170 got_object_idcache_contains(struct got_object_idcache *cache,
171     struct got_object_id *id)
172 {
173 	struct got_object_idcache_element *entry;
174 	uint8_t i = id->sha1[0];
175 
176 	TAILQ_FOREACH(entry, &cache->entries[i], entry) {
177 		if (memcmp(&entry->id.sha1, id->sha1, SHA1_DIGEST_LENGTH) == 0)
178 			return 1;
179 	}
180 
181 	return 0;
182 }
183 
184 void got_object_idcache_for_each(struct got_object_idcache *cache,
185     void (*cb)(struct got_object_id *, void *, void *), void *arg)
186 {
187 	struct got_object_idcache_element *entry;
188 	int i;
189 
190 	for (i = 0; i < nitems(cache->entries); i++) {
191 		TAILQ_FOREACH(entry, &cache->entries[i], entry)
192 			cb(&entry->id, entry->data, arg);
193 	}
194 }
195 
196 int
197 got_object_idcache_num_elements(struct got_object_idcache *cache)
198 {
199 	return cache->totelem;
200 }