Blame

Date:
Message:
fix id_hash
Actions:
History | Blob | Raw File
  1 54be8251 2018-06-04 stsp /*

  2 cbc287dc 2022-04-19 stsp  * 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 54be8251 2018-06-04 stsp #include <sys/queue.h>

 18 54be8251 2018-06-04 stsp 

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

 20 cbc287dc 2022-04-19 stsp #include <stdint.h>

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

 22 54be8251 2018-06-04 stsp #include <sha1.h>

 23 e83f12a6 2023-02-12 op #include <sha2.h>

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

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

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

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

 28 cbc287dc 2022-04-19 stsp #include <errno.h>

 29 cbc287dc 2022-04-19 stsp #include <siphash.h>

 30 54be8251 2018-06-04 stsp 

 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 f7f02f54 2023-02-13 op #include "got_lib_hash.h"

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

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

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

 39 cbc287dc 2022-04-19 stsp #include "got_lib_object_parse.h"

 40 54be8251 2018-06-04 stsp 

 41 cbc287dc 2022-04-19 stsp #define GOT_OBJECT_IDSET_MIN_BUCKETS	64

 42 54be8251 2018-06-04 stsp 

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

 44 cbc287dc 2022-04-19 stsp 	struct got_object_id_queue *ids;

 45 cbc287dc 2022-04-19 stsp 	size_t nbuckets;

 46 cbc287dc 2022-04-19 stsp 	unsigned int totelem;

 47 cbc287dc 2022-04-19 stsp 	unsigned int flags;

 48 cbc287dc 2022-04-19 stsp #define GOT_OBJECT_IDSET_F_TRAVERSAL	0x01

 49 cbc287dc 2022-04-19 stsp #define GOT_OBJECT_IDSET_F_NOMEM	0x02

 50 cbc287dc 2022-04-19 stsp 	SIPHASH_KEY key;

 51 54be8251 2018-06-04 stsp };

 52 54be8251 2018-06-04 stsp 

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

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

 55 54be8251 2018-06-04 stsp {

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

 57 cbc287dc 2022-04-19 stsp 	int i;

 58 54be8251 2018-06-04 stsp 

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

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

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

 62 54be8251 2018-06-04 stsp 

 63 cbc287dc 2022-04-19 stsp 	set->ids = calloc(sizeof(set->ids[0]), GOT_OBJECT_IDSET_MIN_BUCKETS);

 64 cbc287dc 2022-04-19 stsp 	if (set->ids == NULL) {

 65 cbc287dc 2022-04-19 stsp 		free(set);

 66 cbc287dc 2022-04-19 stsp 		return NULL;

 67 cbc287dc 2022-04-19 stsp 	}

 68 cbc287dc 2022-04-19 stsp 	for (i = 0; i < GOT_OBJECT_IDSET_MIN_BUCKETS; i++)

 69 cbc287dc 2022-04-19 stsp 		STAILQ_INIT(&set->ids[i]);

 70 54be8251 2018-06-04 stsp 

 71 cbc287dc 2022-04-19 stsp 	set->totelem = 0;

 72 cbc287dc 2022-04-19 stsp 	set->nbuckets = GOT_OBJECT_IDSET_MIN_BUCKETS;

 73 cbc287dc 2022-04-19 stsp 	set->flags = 0;

 74 cbc287dc 2022-04-19 stsp 	arc4random_buf(&set->key, sizeof(set->key));

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

 76 54be8251 2018-06-04 stsp }

 77 54be8251 2018-06-04 stsp 

 78 54be8251 2018-06-04 stsp void

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

 80 54be8251 2018-06-04 stsp {

 81 cbc287dc 2022-04-19 stsp 	size_t i;

 82 cbc287dc 2022-04-19 stsp 	struct got_object_qid *qid;

 83 54be8251 2018-06-04 stsp 

 84 cbc287dc 2022-04-19 stsp 	for (i = 0; i < set->nbuckets; i++) {

 85 cbc287dc 2022-04-19 stsp 		while (!STAILQ_EMPTY(&set->ids[i])) {

 86 cbc287dc 2022-04-19 stsp 			qid = STAILQ_FIRST(&set->ids[i]);

 87 cbc287dc 2022-04-19 stsp 			STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);

 88 cbc287dc 2022-04-19 stsp 			got_object_qid_free(qid);

 89 cbc287dc 2022-04-19 stsp 		}

 90 54be8251 2018-06-04 stsp 	}

 91 cbc287dc 2022-04-19 stsp 	/* User data should be freed by caller. */

 92 cbc287dc 2022-04-19 stsp 	free(set->ids);

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

 94 54be8251 2018-06-04 stsp }

 95 54be8251 2018-06-04 stsp 

 96 cbc287dc 2022-04-19 stsp static uint64_t

 97 cbc287dc 2022-04-19 stsp idset_hash(struct got_object_idset *set, struct got_object_id *id)

 98 54be8251 2018-06-04 stsp {

 99 f7f02f54 2023-02-13 op 	return SipHash24(&set->key, id->hash,

100 f7f02f54 2023-02-13 op 	    got_hash_digest_length(id->algo));

101 cbc287dc 2022-04-19 stsp }

102 54be8251 2018-06-04 stsp 

103 cbc287dc 2022-04-19 stsp static const struct got_error *

104 cbc287dc 2022-04-19 stsp idset_resize(struct got_object_idset *set, size_t nbuckets)

105 cbc287dc 2022-04-19 stsp {

106 cbc287dc 2022-04-19 stsp 	struct got_object_id_queue *ids;

107 cbc287dc 2022-04-19 stsp 	size_t i;

108 c6f420bf 2018-06-04 stsp 

109 cbc287dc 2022-04-19 stsp 	ids = calloc(nbuckets, sizeof(ids[0]));

110 cbc287dc 2022-04-19 stsp 	if (ids == NULL) {

111 cbc287dc 2022-04-19 stsp 		if (errno != ENOMEM)

112 cbc287dc 2022-04-19 stsp 			return got_error_from_errno("calloc");

113 cbc287dc 2022-04-19 stsp 		/* Proceed with our current amount of hash buckets. */

114 cbc287dc 2022-04-19 stsp 		set->flags |= GOT_OBJECT_IDSET_F_NOMEM;

115 cbc287dc 2022-04-19 stsp 		return NULL;

116 cbc287dc 2022-04-19 stsp 	}

117 54be8251 2018-06-04 stsp 

118 cbc287dc 2022-04-19 stsp 	for (i = 0; i < nbuckets; i++)

119 cbc287dc 2022-04-19 stsp 		STAILQ_INIT(&ids[i]);

120 54be8251 2018-06-04 stsp 

121 cbc287dc 2022-04-19 stsp 	arc4random_buf(&set->key, sizeof(set->key));

122 cbc287dc 2022-04-19 stsp 

123 cbc287dc 2022-04-19 stsp 	for (i = 0; i < set->nbuckets; i++) {

124 cbc287dc 2022-04-19 stsp 		while (!STAILQ_EMPTY(&set->ids[i])) {

125 cbc287dc 2022-04-19 stsp 			struct got_object_qid *qid;

126 cbc287dc 2022-04-19 stsp 			uint64_t idx;

127 cbc287dc 2022-04-19 stsp 			qid = STAILQ_FIRST(&set->ids[i]);

128 cbc287dc 2022-04-19 stsp 			STAILQ_REMOVE(&set->ids[i], qid, got_object_qid, entry);

129 d7b5a0e8 2022-04-20 stsp 			idx = idset_hash(set, &qid->id) % nbuckets;

130 cbc287dc 2022-04-19 stsp 			STAILQ_INSERT_HEAD(&ids[idx], qid, entry);

131 cbc287dc 2022-04-19 stsp 		}

132 a7472cb3 2022-04-14 stsp 	}

133 a7472cb3 2022-04-14 stsp 

134 cbc287dc 2022-04-19 stsp 	free(set->ids);

135 cbc287dc 2022-04-19 stsp 	set->ids = ids;

136 cbc287dc 2022-04-19 stsp 	set->nbuckets = nbuckets;

137 b36429ab 2018-11-05 stsp 	return NULL;

138 54be8251 2018-06-04 stsp }

139 54be8251 2018-06-04 stsp 

140 cbc287dc 2022-04-19 stsp static const struct got_error *

141 cbc287dc 2022-04-19 stsp idset_grow(struct got_object_idset *set)

142 54be8251 2018-06-04 stsp {

143 cbc287dc 2022-04-19 stsp 	size_t nbuckets;

144 54be8251 2018-06-04 stsp 

145 cbc287dc 2022-04-19 stsp 	if (set->flags & GOT_OBJECT_IDSET_F_NOMEM)

146 cbc287dc 2022-04-19 stsp 		return NULL;

147 cbc287dc 2022-04-19 stsp 

148 cbc287dc 2022-04-19 stsp 	if (set->nbuckets >= UINT_MAX / 2)

149 cbc287dc 2022-04-19 stsp 		nbuckets = UINT_MAX;

150 cbc287dc 2022-04-19 stsp 	else

151 cbc287dc 2022-04-19 stsp 		nbuckets = set->nbuckets * 2;

152 cbc287dc 2022-04-19 stsp 

153 cbc287dc 2022-04-19 stsp 	return idset_resize(set, nbuckets);

154 cbc287dc 2022-04-19 stsp }

155 cbc287dc 2022-04-19 stsp 

156 cbc287dc 2022-04-19 stsp const struct got_error *

157 cbc287dc 2022-04-19 stsp got_object_idset_add(struct got_object_idset *set, struct got_object_id *id,

158 cbc287dc 2022-04-19 stsp     void *data)

159 cbc287dc 2022-04-19 stsp {

160 cbc287dc 2022-04-19 stsp 	const struct got_error *err;

161 cbc287dc 2022-04-19 stsp 	struct got_object_qid *qid;

162 cbc287dc 2022-04-19 stsp 	uint64_t idx;

163 cbc287dc 2022-04-19 stsp 	struct got_object_id_queue *head;

164 cbc287dc 2022-04-19 stsp 

165 cbc287dc 2022-04-19 stsp 	/* This function may resize the set. */

166 cbc287dc 2022-04-19 stsp 	if (set->flags & GOT_OBJECT_IDSET_F_TRAVERSAL)

167 cbc287dc 2022-04-19 stsp 		return got_error_msg(GOT_ERR_NOT_IMPL,

168 cbc287dc 2022-04-19 stsp 		    "cannot add elements to idset during traversal");

169 cbc287dc 2022-04-19 stsp 

170 cbc287dc 2022-04-19 stsp 	if (set->totelem == UINT_MAX)

171 cbc287dc 2022-04-19 stsp 		return got_error(GOT_ERR_NO_SPACE);

172 5e91dae4 2022-08-30 stsp 

173 cbc287dc 2022-04-19 stsp 	err = got_object_qid_alloc_partial(&qid);

174 cbc287dc 2022-04-19 stsp 	if (err)

175 cbc287dc 2022-04-19 stsp 		return err;

176 d7b5a0e8 2022-04-20 stsp 	memcpy(&qid->id, id, sizeof(qid->id));

177 cbc287dc 2022-04-19 stsp 	qid->data = data;

178 cbc287dc 2022-04-19 stsp 

179 cbc287dc 2022-04-19 stsp 	idx = idset_hash(set, id) % set->nbuckets;

180 cbc287dc 2022-04-19 stsp 	head = &set->ids[idx];

181 cbc287dc 2022-04-19 stsp 	STAILQ_INSERT_HEAD(head, qid, entry);

182 cbc287dc 2022-04-19 stsp 	set->totelem++;

183 cbc287dc 2022-04-19 stsp 

184 cbc287dc 2022-04-19 stsp 	if (set->nbuckets < set->totelem)

185 cbc287dc 2022-04-19 stsp 		err = idset_grow(set);

186 cbc287dc 2022-04-19 stsp 

187 cbc287dc 2022-04-19 stsp 	return err;

188 cbc287dc 2022-04-19 stsp }

189 cbc287dc 2022-04-19 stsp 

190 cbc287dc 2022-04-19 stsp static struct got_object_qid *

191 cbc287dc 2022-04-19 stsp find_element(struct got_object_idset *set, struct got_object_id *id)

192 cbc287dc 2022-04-19 stsp {

193 cbc287dc 2022-04-19 stsp 	uint64_t idx = idset_hash(set, id) % set->nbuckets;

194 cbc287dc 2022-04-19 stsp 	struct got_object_id_queue *head = &set->ids[idx];

195 cbc287dc 2022-04-19 stsp 	struct got_object_qid *qid;

196 cbc287dc 2022-04-19 stsp 

197 cbc287dc 2022-04-19 stsp 	STAILQ_FOREACH(qid, head, entry) {

198 d7b5a0e8 2022-04-20 stsp 		if (got_object_id_cmp(&qid->id, id) == 0)

199 cbc287dc 2022-04-19 stsp 			return qid;

200 54be8251 2018-06-04 stsp 	}

201 54be8251 2018-06-04 stsp 

202 cbc287dc 2022-04-19 stsp 	return NULL;

203 54be8251 2018-06-04 stsp }

204 54be8251 2018-06-04 stsp 

205 984e8a45 2018-11-05 stsp void *

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

207 984e8a45 2018-11-05 stsp {

208 cbc287dc 2022-04-19 stsp 	struct got_object_qid *qid = find_element(set, id);

209 cbc287dc 2022-04-19 stsp 	return qid ? qid->data : NULL;

210 984e8a45 2018-11-05 stsp }

211 984e8a45 2018-11-05 stsp 

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

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

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

215 54be8251 2018-06-04 stsp {

216 cbc287dc 2022-04-19 stsp 	uint64_t idx;

217 cbc287dc 2022-04-19 stsp 	struct got_object_id_queue *head;

218 cbc287dc 2022-04-19 stsp 	struct got_object_qid *qid;

219 54be8251 2018-06-04 stsp 

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

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

222 441e144c 2018-06-22 stsp 

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

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

225 c6f420bf 2018-06-04 stsp 

226 0ae61b79 2022-03-21 stsp 	if (id == NULL) {

227 cbc287dc 2022-04-19 stsp 		/* Remove a "random" element. */

228 cbc287dc 2022-04-19 stsp 		for (idx = 0; idx < set->nbuckets; idx++) {

229 cbc287dc 2022-04-19 stsp 			head = &set->ids[idx];

230 cbc287dc 2022-04-19 stsp 			qid = STAILQ_FIRST(head);

231 cbc287dc 2022-04-19 stsp 			if (qid)

232 cbc287dc 2022-04-19 stsp 				break;

233 cbc287dc 2022-04-19 stsp 		}

234 0ae61b79 2022-03-21 stsp 	} else {

235 cbc287dc 2022-04-19 stsp 		idx = idset_hash(set, id) % set->nbuckets;

236 cbc287dc 2022-04-19 stsp 		head = &set->ids[idx];

237 cbc287dc 2022-04-19 stsp 		STAILQ_FOREACH(qid, head, entry) {

238 d7b5a0e8 2022-04-20 stsp 			if (got_object_id_cmp(&qid->id, id) == 0)

239 cbc287dc 2022-04-19 stsp 				break;

240 cbc287dc 2022-04-19 stsp 		}

241 cbc287dc 2022-04-19 stsp 		if (qid == NULL)

242 0ae61b79 2022-03-21 stsp 			return got_error_no_obj(id);

243 0ae61b79 2022-03-21 stsp 	}

244 54be8251 2018-06-04 stsp 

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

246 cbc287dc 2022-04-19 stsp 		*data = qid->data;

247 cbc287dc 2022-04-19 stsp 	STAILQ_REMOVE(head, qid, got_object_qid, entry);

248 cbc287dc 2022-04-19 stsp 	got_object_qid_free(qid);

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

250 cbc287dc 2022-04-19 stsp 

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

252 54be8251 2018-06-04 stsp }

253 54be8251 2018-06-04 stsp 

254 54be8251 2018-06-04 stsp int

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

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

257 54be8251 2018-06-04 stsp {

258 cbc287dc 2022-04-19 stsp 	struct got_object_qid *qid = find_element(set, id);

259 cbc287dc 2022-04-19 stsp 	return qid ? 1 : 0;

260 54be8251 2018-06-04 stsp }

261 54be8251 2018-06-04 stsp 

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

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

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

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

266 54be8251 2018-06-04 stsp {

267 cbc287dc 2022-04-19 stsp 	const struct got_error *err = NULL;

268 cbc287dc 2022-04-19 stsp 	struct got_object_id_queue *head;

269 cbc287dc 2022-04-19 stsp 	struct got_object_qid *qid, *tmp;

270 cbc287dc 2022-04-19 stsp 	size_t i;

271 54be8251 2018-06-04 stsp 

272 cbc287dc 2022-04-19 stsp 	set->flags |= GOT_OBJECT_IDSET_F_TRAVERSAL;

273 cbc287dc 2022-04-19 stsp 	for (i = 0; i < set->nbuckets; i++) {

274 cbc287dc 2022-04-19 stsp 		head = &set->ids[i];

275 cbc287dc 2022-04-19 stsp 		STAILQ_FOREACH_SAFE(qid, head, entry, tmp) {

276 d7b5a0e8 2022-04-20 stsp 			err = (*cb)(&qid->id, qid->data, arg);

277 cbc287dc 2022-04-19 stsp 			if (err)

278 cbc287dc 2022-04-19 stsp 				goto done;

279 cbc287dc 2022-04-19 stsp 		}

280 cb103d04 2018-11-07 stsp 	}

281 cbc287dc 2022-04-19 stsp done:

282 cbc287dc 2022-04-19 stsp 	set->flags &= ~GOT_OBJECT_IDSET_F_TRAVERSAL;

283 cbc287dc 2022-04-19 stsp 	return err;

284 54be8251 2018-06-04 stsp }

285 c6f420bf 2018-06-04 stsp 

286 069f84d5 2018-06-11 stsp int

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

288 c6f420bf 2018-06-04 stsp {

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

290 c6f420bf 2018-06-04 stsp }