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_zbuf.h"
32 #include "got_lib_object.h"
33 #include "got_lib_object_idset.h"
34 
35 #ifndef nitems
36 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
37 #endif
38 
39 struct got_object_idset_element {
40 	TAILQ_ENTRY(got_object_idset_element) entry;
41 	struct got_object_id id;
42 	void *data;	/* API user data */
43 };
44 
45 struct got_object_idset {
46 	/*
47 	 * A set is implemented as a collection of 256 lists.
48 	 * The value of the first byte of an object ID determines
49 	 * which of these lists an object ID is stored in.
50 	 */
51 	TAILQ_HEAD(, got_object_idset_element) entries[0xff + 1];
52 	int nelem[0xff + 1];
53 	int totelem;
54 #define GOT_OBJECT_IDSET_MAX_ELEM INT_MAX
55 	enum got_object_idset_iteration_order order;
56 };
57 
58 struct got_object_idset *
59 got_object_idset_alloc(enum got_object_idset_iteration_order order)
60 {
61 	struct got_object_idset *set;
62 	int i;
63 
64 	set = calloc(1, sizeof(*set));
65 	if (set == NULL)
66 		return NULL;
67 
68 	set->order = order;
69 	for (i = 0; i < nitems(set->entries); i++)
70 		TAILQ_INIT(&set->entries[i]);
71 
72 	return set;
73 }
74 
75 void
76 got_object_idset_free(struct got_object_idset *set)
77 {
78 	struct got_object_idset_element *entry;
79 	int i;
80 
81 	for (i = 0; i < nitems(set->entries); i++) {
82 		while (!TAILQ_EMPTY(&set->entries[i])) {
83 			entry = TAILQ_FIRST(&set->entries[i]);
84 			TAILQ_REMOVE(&set->entries[i], entry, entry);
85 			/* User data should be freed by caller. */
86 			free(entry);
87 		}
88 	}
89 	free(set);
90 }
91 
92 const struct got_error *
93 got_object_idset_add(void **existing_data,
94     struct got_object_idset *set, struct got_object_id *id, void *data)
95 {
96 	struct got_object_idset_element *new, *entry;
97 	uint8_t i = id->sha1[0];
98 
99 	if (existing_data)
100 		*existing_data = NULL;
101 
102 	if (set->totelem >= GOT_OBJECT_IDSET_MAX_ELEM)
103 		return got_error(GOT_ERR_NO_SPACE);
104 
105 	new = calloc(1, sizeof(*new));
106 	if (new == NULL)
107 		return got_error_from_errno();
108 
109 	memcpy(&new->id, id, sizeof(new->id));
110 	new->data = data;
111 
112 	if (TAILQ_EMPTY(&set->entries[i]) ||
113 	    set->order == GOT_OBJECT_IDSET_ITERATE_RECENTLY_USED) {
114 		TAILQ_INSERT_HEAD(&set->entries[i], new, entry);
115 		set->nelem[i]++;
116 		set->totelem++;
117 		return NULL;
118 	}
119 
120 	/*
121 	 * Keep the list sorted by ID so that iterations of
122 	 * the set occur in a predictable order.
123 	 */
124 	TAILQ_FOREACH(entry, &set->entries[i], entry) {
125 		int cmp = got_object_id_cmp(&new->id, &entry->id);
126 		struct got_object_idset_element *next;
127 
128 		if (cmp == 0) {
129 			free(new);
130 			if (existing_data)
131 				*existing_data = entry->data;
132 			return got_error(GOT_ERR_OBJ_EXISTS);
133 		} else if (cmp < 0) {
134 			TAILQ_INSERT_BEFORE(entry, new, entry);
135 			set->nelem[i]++;
136 			set->totelem++;
137 			return NULL;
138 		}
139 
140 		next = TAILQ_NEXT(entry, entry);
141 		if (next == NULL) {
142 			TAILQ_INSERT_AFTER(&set->entries[i], entry, new, entry);
143 			set->nelem[i]++;
144 			set->totelem++;
145 			return NULL;
146 		} else if (got_object_id_cmp(&new->id, &next->id) > 0) {
147 			TAILQ_INSERT_BEFORE(next, new, entry);
148 			set->nelem[i]++;
149 			set->totelem++;
150 			return NULL;
151 		}
152 	}
153 
154 	return got_error(GOT_ERR_BAD_OBJ_ID); /* should not get here */
155 }
156 
157 void *
158 got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)
159 {
160 	struct got_object_idset_element *entry, *tmp;
161 	uint8_t i = id->sha1[0];
162 
163 	TAILQ_FOREACH_SAFE(entry, &set->entries[i], entry, tmp) {
164 		if (got_object_id_cmp(&entry->id, id) != 0)
165 			continue;
166 		if (set->order == GOT_OBJECT_IDSET_ITERATE_RECENTLY_USED &&
167 		    entry != TAILQ_FIRST(&set->entries[i])) {
168 			TAILQ_REMOVE(&set->entries[i], entry, entry);
169 			TAILQ_INSERT_HEAD(&set->entries[i], entry, entry);
170 		}
171 		return entry->data;
172 	}
173 
174 	return NULL;
175 }
176 
177 const struct got_error *
178 got_object_idset_remove(void **data, struct got_object_idset *set,
179     struct got_object_id *id)
180 {
181 	struct got_object_idset_element *entry, *tmp;
182 	uint8_t i = id->sha1[0];
183 
184 	if (data)
185 		*data = NULL;
186 
187 	if (set->nelem[i] == 0)
188 		return got_error(GOT_ERR_NO_OBJ);
189 
190 	TAILQ_FOREACH_SAFE(entry, &set->entries[i], entry, tmp) {
191 		if (got_object_id_cmp(&entry->id, id) == 0) {
192 			TAILQ_REMOVE(&set->entries[i], entry, entry);
193 			if (data)
194 				*data = entry->data;
195 			free(entry);
196 			set->nelem[i]--;
197 			set->totelem--;
198 			return NULL;
199 		}
200 	}
201 
202 	return got_error(GOT_ERR_NO_OBJ);
203 }
204 
205 const struct got_error *
206 got_object_idset_remove_random(void **data, struct got_object_idset *set)
207 {
208 	struct got_object_idset_element *entry, *tmp;
209 	int i, n, totelem;
210 
211 	if (data)
212 		*data = NULL;
213 
214 	if (set->totelem == 0)
215 		return got_error(GOT_ERR_NO_OBJ);
216 
217 	/* Pick a random element index across all lists. */
218 	if (set->totelem == 1)
219 		n = 0;
220 	else
221 		n = arc4random_uniform(set->totelem);
222 
223 	totelem = 0;
224 	for (i = 0; i < nitems(set->entries); i++) {
225 		/* Skip lists which don't contain the element we picked. */
226 		totelem += set->nelem[i];
227 		if (totelem == 0 || n > totelem - 1) {
228 			n -= set->nelem[i];
229 			continue;
230 		}
231 		TAILQ_FOREACH_SAFE(entry, &set->entries[i], entry, tmp) {
232 			if (n == 0) {
233 				TAILQ_REMOVE(&set->entries[i], entry, entry);
234 				if (data)
235 					*data = entry->data;
236 				free(entry);
237 				set->nelem[i]--;
238 				set->totelem--;
239 				return NULL;
240 			}
241 			n--;
242 		}
243 	}
244 
245 	return got_error(GOT_ERR_NO_OBJ);
246 }
247 
248 int
249 got_object_idset_contains(struct got_object_idset *set,
250     struct got_object_id *id)
251 {
252 	struct got_object_idset_element *entry;
253 	uint8_t i = id->sha1[0];
254 
255 	TAILQ_FOREACH(entry, &set->entries[i], entry) {
256 		if (got_object_id_cmp(&entry->id, id) == 0)
257 			return 1;
258 	}
259 
260 	return 0;
261 }
262 
263 void got_object_idset_for_each(struct got_object_idset *set,
264     void (*cb)(struct got_object_id *, void *, void *), void *arg)
265 {
266 	struct got_object_idset_element *entry;
267 	int i;
268 
269 	for (i = 0; i < nitems(set->entries); i++) {
270 		TAILQ_FOREACH(entry, &set->entries[i], entry)
271 			cb(&entry->id, entry->data, arg);
272 	}
273 }
274 
275 int
276 got_object_idset_num_elements(struct got_object_idset *set)
277 {
278 	return set->totelem;
279 }