2 eb77ee11 2018-07-08 stsp * Copyright (c) 2018 Stefan Sperling <stsp@openbsd.org>
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.
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.
17 eb77ee11 2018-07-08 stsp #include <sys/queue.h>
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>
27 eb77ee11 2018-07-08 stsp #include "got_object.h"
28 eb77ee11 2018-07-08 stsp #include "got_error.h"
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"
35 eb77ee11 2018-07-08 stsp #ifndef nitems
36 eb77ee11 2018-07-08 stsp #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
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 */
45 eb77ee11 2018-07-08 stsp TAILQ_HEAD(got_object_idcache_head, got_object_idcache_element);
47 eb77ee11 2018-07-08 stsp struct got_object_idcache {
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.
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;
59 eb77ee11 2018-07-08 stsp struct got_object_idcache *
60 eb77ee11 2018-07-08 stsp got_object_idcache_alloc(int maxelem)
62 eb77ee11 2018-07-08 stsp struct got_object_idcache *cache;
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;
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;
76 eb77ee11 2018-07-08 stsp got_object_idcache_free(struct got_object_idcache *cache)
78 eb77ee11 2018-07-08 stsp struct got_object_idcache_element *entry;
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);
89 eb77ee11 2018-07-08 stsp free(cache);
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)
96 eb77ee11 2018-07-08 stsp struct got_object_idcache_element *entry;
97 bb7182a5 2018-09-16 stsp uint8_t i = id->sha1[0];
99 bb7182a5 2018-09-16 stsp if (cache->totelem >= cache->maxelem)
100 720ad641 2018-07-23 stsp return got_error(GOT_ERR_NO_SPACE);
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();
106 eb77ee11 2018-07-08 stsp memcpy(&entry->id, id, sizeof(entry->id));
107 eb77ee11 2018-07-08 stsp entry->data = data;
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;
116 eb77ee11 2018-07-08 stsp got_object_idcache_get(struct got_object_idcache *cache, struct got_object_id *id)
118 eb77ee11 2018-07-08 stsp struct got_object_idcache_element *entry;
119 bb7182a5 2018-09-16 stsp uint8_t i = id->sha1[0];
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)
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);
128 eb77ee11 2018-07-08 stsp return entry->data;
131 eb77ee11 2018-07-08 stsp return NULL;
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)
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];
141 eb77ee11 2018-07-08 stsp *data = NULL;
143 bb7182a5 2018-09-16 stsp if (cache->totelem == 0)
144 eb77ee11 2018-07-08 stsp return got_error(GOT_ERR_NO_OBJ);
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]) {
150 bb7182a5 2018-09-16 stsp maxelem = cache->nelem[i];
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);
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;
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)
167 eb77ee11 2018-07-08 stsp struct got_object_idcache_element *entry;
168 bb7182a5 2018-09-16 stsp uint8_t i = id->sha1[0];
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)
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)
181 eb77ee11 2018-07-08 stsp struct got_object_idcache_element *entry;
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);
191 bb7182a5 2018-09-16 stsp got_object_idcache_num_elements(struct got_object_idcache *cache)
193 bb7182a5 2018-09-16 stsp return cache->totelem;