Blame

Date:
Message:
include sha2.h too where sha1.h is included In preparation for wide sha256 support; stsp@ agrees. Change done mechanically with find . -iname \*.[cy] -exec sam {} + X ,x/<sha1\.h>/i/\n#include <sha2.h>
Actions:
History | Blob | Raw File
  1 54be8251 2018-06-04 stsp /*

  2 619de35f 2022-04-22 thomas  * Copyright (c) 2022 Stefan Sperling <stsp@openbsd.org>

  3 54be8251 2018-06-04 stsp  *

  4 54be8251 2018-06-04 stsp  * Permission to use, copy, modify, and distribute this software for any

  5 54be8251 2018-06-04 stsp  * purpose with or without fee is hereby granted, provided that the above

  6 54be8251 2018-06-04 stsp  * copyright notice and this permission notice appear in all copies.

  7 54be8251 2018-06-04 stsp  *

  8 54be8251 2018-06-04 stsp  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES

  9 54be8251 2018-06-04 stsp  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF

 10 54be8251 2018-06-04 stsp  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR

 11 54be8251 2018-06-04 stsp  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES

 12 54be8251 2018-06-04 stsp  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN

 13 54be8251 2018-06-04 stsp  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF

 14 54be8251 2018-06-04 stsp  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

 15 54be8251 2018-06-04 stsp  */

 16 54be8251 2018-06-04 stsp 

 17 8b925c6c 2022-07-16 thomas #include <sys/queue.h>

 18 54be8251 2018-06-04 stsp #include <stdlib.h>

 19 619de35f 2022-04-22 thomas #include <stdint.h>

 20 54be8251 2018-06-04 stsp #include <string.h>

 21 588a8092 2023-02-23 thomas #include <sha1.h>

 22 588a8092 2023-02-23 thomas #include <sha2.h>

 23 54be8251 2018-06-04 stsp #include <stdio.h>

 24 54be8251 2018-06-04 stsp #include <zlib.h>

 25 c6f420bf 2018-06-04 stsp #include <limits.h>

 26 788c352e 2018-06-16 stsp #include <time.h>

 27 619de35f 2022-04-22 thomas #include <errno.h>

 28 54be8251 2018-06-04 stsp 

 29 dd038bc6 2021-09-21 thomas.ad #include "got_compat.h"

 30 dd038bc6 2021-09-21 thomas.ad 

 31 54be8251 2018-06-04 stsp #include "got_object.h"

 32 54be8251 2018-06-04 stsp #include "got_error.h"

 33 54be8251 2018-06-04 stsp 

 34 54be8251 2018-06-04 stsp #include "got_lib_delta.h"

 35 63581804 2018-07-09 stsp #include "got_lib_inflate.h"

 36 54be8251 2018-06-04 stsp #include "got_lib_object.h"

 37 54be8251 2018-06-04 stsp #include "got_lib_object_idset.h"

 38 619de35f 2022-04-22 thomas #include "got_lib_object_parse.h"

 39 54be8251 2018-06-04 stsp 

 40 619de35f 2022-04-22 thomas #define GOT_OBJECT_IDSET_MIN_BUCKETS	64

 41 54be8251 2018-06-04 stsp 

 42 54be8251 2018-06-04 stsp struct got_object_idset {

 43 619de35f 2022-04-22 thomas 	struct got_object_id_queue *ids;

 44 619de35f 2022-04-22 thomas 	size_t nbuckets;

 45 619de35f 2022-04-22 thomas 	unsigned int totelem;

 46 619de35f 2022-04-22 thomas 	unsigned int flags;

 47 619de35f 2022-04-22 thomas #define GOT_OBJECT_IDSET_F_TRAVERSAL	0x01

 48 619de35f 2022-04-22 thomas #define GOT_OBJECT_IDSET_F_NOMEM	0x02

 49 619de35f 2022-04-22 thomas 	SIPHASH_KEY key;

 50 54be8251 2018-06-04 stsp };

 51 54be8251 2018-06-04 stsp 

 52 54be8251 2018-06-04 stsp struct got_object_idset *

 53 60f2eee1 2018-07-08 stsp got_object_idset_alloc(void)

 54 54be8251 2018-06-04 stsp {

 55 54be8251 2018-06-04 stsp 	struct got_object_idset *set;

 56 619de35f 2022-04-22 thomas 	int i;

 57 54be8251 2018-06-04 stsp 

 58 984e8a45 2018-11-05 stsp 	set = malloc(sizeof(*set));

 59 54be8251 2018-06-04 stsp 	if (set == NULL)

 60 54be8251 2018-06-04 stsp 		return NULL;

 61 54be8251 2018-06-04 stsp 

 62 619de35f 2022-04-22 thomas 	set->ids = calloc(sizeof(set->ids[0]), GOT_OBJECT_IDSET_MIN_BUCKETS);

 63 619de35f 2022-04-22 thomas 	if (set->ids == NULL) {

 64 619de35f 2022-04-22 thomas 		free(set);

 65 619de35f 2022-04-22 thomas 		return NULL;

 66 619de35f 2022-04-22 thomas 	}

 67 619de35f 2022-04-22 thomas 	for (i = 0; i < GOT_OBJECT_IDSET_MIN_BUCKETS; i++)

 68 619de35f 2022-04-22 thomas 		STAILQ_INIT(&set->ids[i]);

 69 54be8251 2018-06-04 stsp 

 70 619de35f 2022-04-22 thomas 	set->totelem = 0;

 71 619de35f 2022-04-22 thomas 	set->nbuckets = GOT_OBJECT_IDSET_MIN_BUCKETS;

 72 619de35f 2022-04-22 thomas 	set->flags = 0;

 73 619de35f 2022-04-22 thomas 	arc4random_buf(&set->key, sizeof(set->key));

 74 54be8251 2018-06-04 stsp 	return set;

 75 54be8251 2018-06-04 stsp }

 76 54be8251 2018-06-04 stsp 

 77 54be8251 2018-06-04 stsp void

 78 54be8251 2018-06-04 stsp got_object_idset_free(struct got_object_idset *set)

 79 54be8251 2018-06-04 stsp {

 80 619de35f 2022-04-22 thomas 	size_t i;

 81 619de35f 2022-04-22 thomas 	struct got_object_qid *qid;

 82 54be8251 2018-06-04 stsp 

 83 619de35f 2022-04-22 thomas 	for (i = 0; i < set->nbuckets; i++) {

 84 619de35f 2022-04-22 thomas 		while (!STAILQ_EMPTY(&set->ids[i])) {

 85 619de35f 2022-04-22 thomas 			qid = STAILQ_FIRST(&set->ids[i]);

 86 619de35f 2022-04-22 thomas 			STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);

 87 619de35f 2022-04-22 thomas 			got_object_qid_free(qid);

 88 619de35f 2022-04-22 thomas 		}

 89 54be8251 2018-06-04 stsp 	}

 90 619de35f 2022-04-22 thomas 	/* User data should be freed by caller. */

 91 619de35f 2022-04-22 thomas 	free(set->ids);

 92 54be8251 2018-06-04 stsp 	free(set);

 93 54be8251 2018-06-04 stsp }

 94 54be8251 2018-06-04 stsp 

 95 619de35f 2022-04-22 thomas static uint64_t

 96 619de35f 2022-04-22 thomas idset_hash(struct got_object_idset *set, struct got_object_id *id)

 97 54be8251 2018-06-04 stsp {

 98 619de35f 2022-04-22 thomas 	return SipHash24(&set->key, id->sha1, sizeof(id->sha1));

 99 619de35f 2022-04-22 thomas }

100 54be8251 2018-06-04 stsp 

101 619de35f 2022-04-22 thomas static const struct got_error *

102 619de35f 2022-04-22 thomas idset_resize(struct got_object_idset *set, size_t nbuckets)

103 619de35f 2022-04-22 thomas {

104 619de35f 2022-04-22 thomas 	struct got_object_id_queue *ids;

105 619de35f 2022-04-22 thomas 	size_t i;

106 c6f420bf 2018-06-04 stsp 

107 619de35f 2022-04-22 thomas 	ids = calloc(nbuckets, sizeof(ids[0]));

108 619de35f 2022-04-22 thomas 	if (ids == NULL) {

109 619de35f 2022-04-22 thomas 		if (errno != ENOMEM)

110 619de35f 2022-04-22 thomas 			return got_error_from_errno("calloc");

111 619de35f 2022-04-22 thomas 		/* Proceed with our current amount of hash buckets. */

112 619de35f 2022-04-22 thomas 		set->flags |= GOT_OBJECT_IDSET_F_NOMEM;

113 619de35f 2022-04-22 thomas 		return NULL;

114 619de35f 2022-04-22 thomas 	}

115 54be8251 2018-06-04 stsp 

116 619de35f 2022-04-22 thomas 	for (i = 0; i < nbuckets; i++)

117 619de35f 2022-04-22 thomas 		STAILQ_INIT(&ids[i]);

118 54be8251 2018-06-04 stsp 

119 619de35f 2022-04-22 thomas 	arc4random_buf(&set->key, sizeof(set->key));

120 619de35f 2022-04-22 thomas 

121 619de35f 2022-04-22 thomas 	for (i = 0; i < set->nbuckets; i++) {

122 619de35f 2022-04-22 thomas 		while (!STAILQ_EMPTY(&set->ids[i])) {

123 619de35f 2022-04-22 thomas 			struct got_object_qid *qid;

124 619de35f 2022-04-22 thomas 			uint64_t idx;

125 619de35f 2022-04-22 thomas 			qid = STAILQ_FIRST(&set->ids[i]);

126 619de35f 2022-04-22 thomas 			STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);

127 ec242592 2022-04-22 thomas 			idx = idset_hash(set, &qid->id) % nbuckets;

128 619de35f 2022-04-22 thomas 			STAILQ_INSERT_HEAD(&ids[idx], qid, entry);

129 619de35f 2022-04-22 thomas 		}

130 9fad5d8c 2022-04-16 thomas 	}

131 9fad5d8c 2022-04-16 thomas 

132 619de35f 2022-04-22 thomas 	free(set->ids);

133 619de35f 2022-04-22 thomas 	set->ids = ids;

134 619de35f 2022-04-22 thomas 	set->nbuckets = nbuckets;

135 b36429ab 2018-11-05 stsp 	return NULL;

136 54be8251 2018-06-04 stsp }

137 54be8251 2018-06-04 stsp 

138 619de35f 2022-04-22 thomas static const struct got_error *

139 619de35f 2022-04-22 thomas idset_grow(struct got_object_idset *set)

140 54be8251 2018-06-04 stsp {

141 619de35f 2022-04-22 thomas 	size_t nbuckets;

142 54be8251 2018-06-04 stsp 

143 619de35f 2022-04-22 thomas 	if (set->flags & GOT_OBJECT_IDSET_F_NOMEM)

144 619de35f 2022-04-22 thomas 		return NULL;

145 619de35f 2022-04-22 thomas 

146 619de35f 2022-04-22 thomas 	if (set->nbuckets >= UINT_MAX / 2)

147 619de35f 2022-04-22 thomas 		nbuckets = UINT_MAX;

148 619de35f 2022-04-22 thomas 	else

149 619de35f 2022-04-22 thomas 		nbuckets = set->nbuckets * 2;

150 619de35f 2022-04-22 thomas 

151 619de35f 2022-04-22 thomas 	return idset_resize(set, nbuckets);

152 619de35f 2022-04-22 thomas }

153 619de35f 2022-04-22 thomas 

154 619de35f 2022-04-22 thomas const struct got_error *

155 619de35f 2022-04-22 thomas got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,

156 619de35f 2022-04-22 thomas     void *data)

157 619de35f 2022-04-22 thomas {

158 619de35f 2022-04-22 thomas 	const struct got_error *err;

159 619de35f 2022-04-22 thomas 	struct got_object_qid *qid;

160 619de35f 2022-04-22 thomas 	uint64_t idx;

161 619de35f 2022-04-22 thomas 	struct got_object_id_queue *head;

162 619de35f 2022-04-22 thomas 

163 619de35f 2022-04-22 thomas 	/* This function may resize the set. */

164 619de35f 2022-04-22 thomas 	if (set->flags & GOT_OBJECT_IDSET_F_TRAVERSAL)

165 619de35f 2022-04-22 thomas 		return got_error_msg(GOT_ERR_NOT_IMPL,

166 619de35f 2022-04-22 thomas 		    "cannot add elements to idset during traversal");

167 619de35f 2022-04-22 thomas 

168 619de35f 2022-04-22 thomas 	if (set->totelem == UINT_MAX)

169 619de35f 2022-04-22 thomas 		return got_error(GOT_ERR_NO_SPACE);

170 b6b86fd1 2022-08-30 thomas 

171 619de35f 2022-04-22 thomas 	err = got_object_qid_alloc_partial(&qid);

172 619de35f 2022-04-22 thomas 	if (err)

173 619de35f 2022-04-22 thomas 		return err;

174 ec242592 2022-04-22 thomas 	memcpy(&qid->id, id, sizeof(qid->id));

175 619de35f 2022-04-22 thomas 	qid->data = data;

176 619de35f 2022-04-22 thomas 

177 619de35f 2022-04-22 thomas 	idx = idset_hash(set, id) % set->nbuckets;

178 619de35f 2022-04-22 thomas 	head = &set->ids[idx];

179 619de35f 2022-04-22 thomas 	STAILQ_INSERT_HEAD(head, qid, entry);

180 619de35f 2022-04-22 thomas 	set->totelem++;

181 619de35f 2022-04-22 thomas 

182 619de35f 2022-04-22 thomas 	if (set->nbuckets < set->totelem)

183 619de35f 2022-04-22 thomas 		err = idset_grow(set);

184 619de35f 2022-04-22 thomas 

185 619de35f 2022-04-22 thomas 	return err;

186 619de35f 2022-04-22 thomas }

187 619de35f 2022-04-22 thomas 

188 619de35f 2022-04-22 thomas static struct got_object_qid *

189 619de35f 2022-04-22 thomas find_element(struct got_object_idset *set, struct got_object_id *id)

190 619de35f 2022-04-22 thomas {

191 619de35f 2022-04-22 thomas 	uint64_t idx = idset_hash(set, id) % set->nbuckets;

192 619de35f 2022-04-22 thomas 	struct got_object_id_queue *head = &set->ids[idx];

193 619de35f 2022-04-22 thomas 	struct got_object_qid *qid;

194 619de35f 2022-04-22 thomas 

195 619de35f 2022-04-22 thomas 	STAILQ_FOREACH(qid, head, entry) {

196 ec242592 2022-04-22 thomas 		if (got_object_id_cmp(&qid->id, id) == 0)

197 619de35f 2022-04-22 thomas 			return qid;

198 54be8251 2018-06-04 stsp 	}

199 54be8251 2018-06-04 stsp 

200 619de35f 2022-04-22 thomas 	return NULL;

201 54be8251 2018-06-04 stsp }

202 54be8251 2018-06-04 stsp 

203 984e8a45 2018-11-05 stsp void *

204 984e8a45 2018-11-05 stsp got_object_idset_get(struct got_object_idset *set, struct got_object_id *id)

205 984e8a45 2018-11-05 stsp {

206 619de35f 2022-04-22 thomas 	struct got_object_qid *qid = find_element(set, id);

207 619de35f 2022-04-22 thomas 	return qid ? qid->data : NULL;

208 984e8a45 2018-11-05 stsp }

209 984e8a45 2018-11-05 stsp 

210 54be8251 2018-06-04 stsp const struct got_error *

211 e7c810ea 2018-06-22 stsp got_object_idset_remove(void **data, struct got_object_idset *set,

212 54be8251 2018-06-04 stsp     struct got_object_id *id)

213 54be8251 2018-06-04 stsp {

214 619de35f 2022-04-22 thomas 	uint64_t idx;

215 619de35f 2022-04-22 thomas 	struct got_object_id_queue *head;

216 619de35f 2022-04-22 thomas 	struct got_object_qid *qid;

217 54be8251 2018-06-04 stsp 

218 441e144c 2018-06-22 stsp 	if (data)

219 441e144c 2018-06-22 stsp 		*data = NULL;

220 441e144c 2018-06-22 stsp 

221 984e8a45 2018-11-05 stsp 	if (set->totelem == 0)

222 c6f420bf 2018-06-04 stsp 		return got_error(GOT_ERR_NO_OBJ);

223 c6f420bf 2018-06-04 stsp 

224 3a4790b6 2022-03-22 thomas 	if (id == NULL) {

225 619de35f 2022-04-22 thomas 		/* Remove a "random" element. */

226 619de35f 2022-04-22 thomas 		for (idx = 0; idx < set->nbuckets; idx++) {

227 619de35f 2022-04-22 thomas 			head = &set->ids[idx];

228 619de35f 2022-04-22 thomas 			qid = STAILQ_FIRST(head);

229 619de35f 2022-04-22 thomas 			if (qid)

230 619de35f 2022-04-22 thomas 				break;

231 619de35f 2022-04-22 thomas 		}

232 3a4790b6 2022-03-22 thomas 	} else {

233 619de35f 2022-04-22 thomas 		idx = idset_hash(set, id) % set->nbuckets;

234 619de35f 2022-04-22 thomas 		head = &set->ids[idx];

235 619de35f 2022-04-22 thomas 		STAILQ_FOREACH(qid, head, entry) {

236 ec242592 2022-04-22 thomas 			if (got_object_id_cmp(&qid->id, id) == 0)

237 619de35f 2022-04-22 thomas 				break;

238 619de35f 2022-04-22 thomas 		}

239 619de35f 2022-04-22 thomas 		if (qid == NULL)

240 3a4790b6 2022-03-22 thomas 			return got_error_no_obj(id);

241 3a4790b6 2022-03-22 thomas 	}

242 54be8251 2018-06-04 stsp 

243 984e8a45 2018-11-05 stsp 	if (data)

244 619de35f 2022-04-22 thomas 		*data = qid->data;

245 619de35f 2022-04-22 thomas 	STAILQ_REMOVE(head, qid, got_object_qid, entry);

246 619de35f 2022-04-22 thomas 	got_object_qid_free(qid);

247 984e8a45 2018-11-05 stsp 	set->totelem--;

248 619de35f 2022-04-22 thomas 

249 984e8a45 2018-11-05 stsp 	return NULL;

250 54be8251 2018-06-04 stsp }

251 54be8251 2018-06-04 stsp 

252 54be8251 2018-06-04 stsp int

253 54be8251 2018-06-04 stsp got_object_idset_contains(struct got_object_idset *set,

254 54be8251 2018-06-04 stsp     struct got_object_id *id)

255 54be8251 2018-06-04 stsp {

256 619de35f 2022-04-22 thomas 	struct got_object_qid *qid = find_element(set, id);

257 619de35f 2022-04-22 thomas 	return qid ? 1 : 0;

258 54be8251 2018-06-04 stsp }

259 54be8251 2018-06-04 stsp 

260 cb103d04 2018-11-07 stsp const struct got_error *

261 cb103d04 2018-11-07 stsp got_object_idset_for_each(struct got_object_idset *set,

262 cb103d04 2018-11-07 stsp     const struct got_error *(*cb)(struct got_object_id *, void *, void *),

263 cb103d04 2018-11-07 stsp     void *arg)

264 54be8251 2018-06-04 stsp {

265 619de35f 2022-04-22 thomas 	const struct got_error *err = NULL;

266 619de35f 2022-04-22 thomas 	struct got_object_id_queue *head;

267 619de35f 2022-04-22 thomas 	struct got_object_qid *qid, *tmp;

268 619de35f 2022-04-22 thomas 	size_t i;

269 54be8251 2018-06-04 stsp 

270 619de35f 2022-04-22 thomas 	set->flags |= GOT_OBJECT_IDSET_F_TRAVERSAL;

271 619de35f 2022-04-22 thomas 	for (i = 0; i < set->nbuckets; i++) {

272 619de35f 2022-04-22 thomas 		head = &set->ids[i];

273 619de35f 2022-04-22 thomas 		STAILQ_FOREACH_SAFE(qid, head, entry, tmp) {

274 ec242592 2022-04-22 thomas 			err = (*cb)(&qid->id, qid->data, arg);

275 619de35f 2022-04-22 thomas 			if (err)

276 619de35f 2022-04-22 thomas 				goto done;

277 619de35f 2022-04-22 thomas 		}

278 cb103d04 2018-11-07 stsp 	}

279 619de35f 2022-04-22 thomas done:

280 619de35f 2022-04-22 thomas 	set->flags &= ~GOT_OBJECT_IDSET_F_TRAVERSAL;

281 619de35f 2022-04-22 thomas 	return err;

282 54be8251 2018-06-04 stsp }

283 c6f420bf 2018-06-04 stsp 

284 069f84d5 2018-06-11 stsp int

285 c6f420bf 2018-06-04 stsp got_object_idset_num_elements(struct got_object_idset *set)

286 c6f420bf 2018-06-04 stsp {

287 2bd394ff 2018-06-22 stsp 	return set->totelem;

288 c6f420bf 2018-06-04 stsp }