2 5aa81393 2020-01-06 stsp * Copyright (c) 2019, 2020 Stefan Sperling <stsp@openbsd.org>
4 ab2f42e7 2019-11-10 stsp * Permission to use, copy, modify, and distribute this software for any
5 ab2f42e7 2019-11-10 stsp * purpose with or without fee is hereby granted, provided that the above
6 ab2f42e7 2019-11-10 stsp * copyright notice and this permission notice appear in all copies.
8 ab2f42e7 2019-11-10 stsp * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 ab2f42e7 2019-11-10 stsp * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 ab2f42e7 2019-11-10 stsp * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 ab2f42e7 2019-11-10 stsp * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 ab2f42e7 2019-11-10 stsp * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 ab2f42e7 2019-11-10 stsp * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 ab2f42e7 2019-11-10 stsp * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 ab2f42e7 2019-11-10 stsp #include <stdlib.h>
19 ab2f42e7 2019-11-10 stsp #include <string.h>
20 ab2f42e7 2019-11-10 stsp #include <sha1.h>
21 ab2f42e7 2019-11-10 stsp #include <stdio.h>
22 ab2f42e7 2019-11-10 stsp #include <zlib.h>
23 ab2f42e7 2019-11-10 stsp #include <limits.h>
24 ab2f42e7 2019-11-10 stsp #include <time.h>
26 dd038bc6 2021-09-21 thomas.ad #include "got_compat.h"
28 ab2f42e7 2019-11-10 stsp #include "got_object.h"
29 ab2f42e7 2019-11-10 stsp #include "got_error.h"
31 ab2f42e7 2019-11-10 stsp #include "got_lib_delta.h"
32 ab2f42e7 2019-11-10 stsp #include "got_lib_inflate.h"
33 ab2f42e7 2019-11-10 stsp #include "got_lib_object.h"
34 ab2f42e7 2019-11-10 stsp #include "got_lib_delta_cache.h"
36 ab2f42e7 2019-11-10 stsp #ifndef nitems
37 ab2f42e7 2019-11-10 stsp #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
40 ab2f42e7 2019-11-10 stsp struct got_delta_cache_element {
41 ab2f42e7 2019-11-10 stsp TAILQ_ENTRY(got_delta_cache_element) entry;
42 ab2f42e7 2019-11-10 stsp off_t delta_data_offset;
43 ab2f42e7 2019-11-10 stsp uint8_t *delta_data;
44 ab2f42e7 2019-11-10 stsp size_t delta_len;
47 ab2f42e7 2019-11-10 stsp TAILQ_HEAD(got_delta_cache_head, got_delta_cache_element);
49 ab2f42e7 2019-11-10 stsp struct got_delta_cache {
50 ab2f42e7 2019-11-10 stsp struct got_delta_cache_head entries;
52 ab2f42e7 2019-11-10 stsp int maxelem;
53 ab2f42e7 2019-11-10 stsp size_t maxelemsize;
54 c3b318d0 2019-11-10 stsp int cache_search;
55 c3b318d0 2019-11-10 stsp int cache_hit;
56 c3b318d0 2019-11-10 stsp int cache_miss;
57 c3b318d0 2019-11-10 stsp int cache_evict;
58 c3b318d0 2019-11-10 stsp int cache_toolarge;
61 ab2f42e7 2019-11-10 stsp struct got_delta_cache *
62 ab2f42e7 2019-11-10 stsp got_delta_cache_alloc(int maxelem, size_t maxelemsize)
64 ab2f42e7 2019-11-10 stsp struct got_delta_cache *cache;
66 ab2f42e7 2019-11-10 stsp cache = calloc(1, sizeof(*cache));
67 ab2f42e7 2019-11-10 stsp if (cache == NULL)
68 ab2f42e7 2019-11-10 stsp return NULL;
70 ab2f42e7 2019-11-10 stsp TAILQ_INIT(&cache->entries);
71 ab2f42e7 2019-11-10 stsp cache->maxelem = maxelem;
72 ab2f42e7 2019-11-10 stsp cache->maxelemsize = maxelemsize;
73 ab2f42e7 2019-11-10 stsp return cache;
77 ab2f42e7 2019-11-10 stsp got_delta_cache_free(struct got_delta_cache *cache)
79 ab2f42e7 2019-11-10 stsp struct got_delta_cache_element *entry;
81 c3b318d0 2019-11-10 stsp #ifdef GOT_OBJ_CACHE_DEBUG
82 c3b318d0 2019-11-10 stsp fprintf(stderr, "%s: delta cache: %d elements, %d searches, %d hits, "
83 c3b318d0 2019-11-10 stsp "%d missed, %d evicted, %d too large\n", getprogname(), cache->nelem,
84 c3b318d0 2019-11-10 stsp cache->cache_search, cache->cache_hit, cache->cache_miss,
85 c3b318d0 2019-11-10 stsp cache->cache_evict, cache->cache_toolarge);
87 ab2f42e7 2019-11-10 stsp while (!TAILQ_EMPTY(&cache->entries)) {
88 ab2f42e7 2019-11-10 stsp entry = TAILQ_FIRST(&cache->entries);
89 ab2f42e7 2019-11-10 stsp TAILQ_REMOVE(&cache->entries, entry, entry);
90 ab2f42e7 2019-11-10 stsp free(entry->delta_data);
91 ab2f42e7 2019-11-10 stsp free(entry);
93 ab2f42e7 2019-11-10 stsp free(cache);
96 fa7a529e 2020-01-06 stsp #ifndef GOT_NO_OBJ_CACHE
98 ab2f42e7 2019-11-10 stsp remove_least_used_element(struct got_delta_cache *cache)
100 ab2f42e7 2019-11-10 stsp struct got_delta_cache_element *entry;
102 ab2f42e7 2019-11-10 stsp if (cache->nelem == 0)
105 ab2f42e7 2019-11-10 stsp entry = TAILQ_LAST(&cache->entries, got_delta_cache_head);
106 ab2f42e7 2019-11-10 stsp TAILQ_REMOVE(&cache->entries, entry, entry);
107 ab2f42e7 2019-11-10 stsp free(entry->delta_data);
108 ab2f42e7 2019-11-10 stsp free(entry);
109 ab2f42e7 2019-11-10 stsp cache->nelem--;
110 c3b318d0 2019-11-10 stsp cache->cache_evict++;
114 ab2f42e7 2019-11-10 stsp const struct got_error *
115 ab2f42e7 2019-11-10 stsp got_delta_cache_add(struct got_delta_cache *cache,
116 ab2f42e7 2019-11-10 stsp off_t delta_data_offset, uint8_t *delta_data, size_t delta_len)
118 fa7a529e 2020-01-06 stsp #ifdef GOT_NO_OBJ_CACHE
119 fa7a529e 2020-01-06 stsp return got_error(GOT_ERR_NO_SPACE);
121 ab2f42e7 2019-11-10 stsp struct got_delta_cache_element *entry;
123 c3b318d0 2019-11-10 stsp if (delta_len > cache->maxelemsize) {
124 c3b318d0 2019-11-10 stsp cache->cache_toolarge++;
125 ab2f42e7 2019-11-10 stsp return got_error(GOT_ERR_NO_SPACE);
128 ab2f42e7 2019-11-10 stsp if (cache->nelem >= cache->maxelem)
129 ab2f42e7 2019-11-10 stsp remove_least_used_element(cache);
131 ab2f42e7 2019-11-10 stsp entry = calloc(1, sizeof(*entry));
132 ab2f42e7 2019-11-10 stsp if (entry == NULL)
133 ab2f42e7 2019-11-10 stsp return got_error_from_errno("calloc");
135 ab2f42e7 2019-11-10 stsp entry->delta_data_offset = delta_data_offset;
136 ab2f42e7 2019-11-10 stsp entry->delta_data = delta_data;
137 ab2f42e7 2019-11-10 stsp entry->delta_len = delta_len;
139 ab2f42e7 2019-11-10 stsp TAILQ_INSERT_HEAD(&cache->entries, entry, entry);
140 ab2f42e7 2019-11-10 stsp cache->nelem++;
141 ab2f42e7 2019-11-10 stsp return NULL;
146 ab2f42e7 2019-11-10 stsp got_delta_cache_get(uint8_t **delta_data, size_t *delta_len,
147 ab2f42e7 2019-11-10 stsp struct got_delta_cache *cache, off_t delta_data_offset)
149 ab2f42e7 2019-11-10 stsp struct got_delta_cache_element *entry;
151 c3b318d0 2019-11-10 stsp cache->cache_search++;
152 ab2f42e7 2019-11-10 stsp *delta_data = NULL;
153 ab2f42e7 2019-11-10 stsp *delta_len = 0;
154 ab2f42e7 2019-11-10 stsp TAILQ_FOREACH(entry, &cache->entries, entry) {
155 ab2f42e7 2019-11-10 stsp if (entry->delta_data_offset != delta_data_offset)
157 c3b318d0 2019-11-10 stsp cache->cache_hit++;
158 ab2f42e7 2019-11-10 stsp if (entry != TAILQ_FIRST(&cache->entries)) {
159 ab2f42e7 2019-11-10 stsp TAILQ_REMOVE(&cache->entries, entry, entry);
160 ab2f42e7 2019-11-10 stsp TAILQ_INSERT_HEAD(&cache->entries, entry, entry);
162 ab2f42e7 2019-11-10 stsp *delta_data = entry->delta_data;
163 ab2f42e7 2019-11-10 stsp *delta_len = entry->delta_len;
167 c3b318d0 2019-11-10 stsp cache->cache_miss++;