2 ab2f42e7 2019-11-10 stsp * Copyright (c) 2019 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.
17 ab2f42e7 2019-11-10 stsp #include <sys/queue.h>
19 ab2f42e7 2019-11-10 stsp #include <stdlib.h>
20 ab2f42e7 2019-11-10 stsp #include <string.h>
21 ab2f42e7 2019-11-10 stsp #include <sha1.h>
22 ab2f42e7 2019-11-10 stsp #include <stdio.h>
23 ab2f42e7 2019-11-10 stsp #include <zlib.h>
24 ab2f42e7 2019-11-10 stsp #include <limits.h>
25 ab2f42e7 2019-11-10 stsp #include <time.h>
27 ab2f42e7 2019-11-10 stsp #include "got_object.h"
28 ab2f42e7 2019-11-10 stsp #include "got_error.h"
30 ab2f42e7 2019-11-10 stsp #include "got_lib_delta.h"
31 ab2f42e7 2019-11-10 stsp #include "got_lib_inflate.h"
32 ab2f42e7 2019-11-10 stsp #include "got_lib_object.h"
33 ab2f42e7 2019-11-10 stsp #include "got_lib_delta_cache.h"
35 ab2f42e7 2019-11-10 stsp #ifndef nitems
36 ab2f42e7 2019-11-10 stsp #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
39 ab2f42e7 2019-11-10 stsp struct got_delta_cache_element {
40 ab2f42e7 2019-11-10 stsp TAILQ_ENTRY(got_delta_cache_element) entry;
41 ab2f42e7 2019-11-10 stsp off_t delta_data_offset;
42 ab2f42e7 2019-11-10 stsp uint8_t *delta_data;
43 ab2f42e7 2019-11-10 stsp size_t delta_len;
46 ab2f42e7 2019-11-10 stsp TAILQ_HEAD(got_delta_cache_head, got_delta_cache_element);
48 ab2f42e7 2019-11-10 stsp struct got_delta_cache {
49 ab2f42e7 2019-11-10 stsp struct got_delta_cache_head entries;
51 ab2f42e7 2019-11-10 stsp int maxelem;
52 ab2f42e7 2019-11-10 stsp size_t maxelemsize;
55 ab2f42e7 2019-11-10 stsp struct got_delta_cache *
56 ab2f42e7 2019-11-10 stsp got_delta_cache_alloc(int maxelem, size_t maxelemsize)
58 ab2f42e7 2019-11-10 stsp struct got_delta_cache *cache;
60 ab2f42e7 2019-11-10 stsp cache = calloc(1, sizeof(*cache));
61 ab2f42e7 2019-11-10 stsp if (cache == NULL)
62 ab2f42e7 2019-11-10 stsp return NULL;
64 ab2f42e7 2019-11-10 stsp TAILQ_INIT(&cache->entries);
65 ab2f42e7 2019-11-10 stsp cache->maxelem = maxelem;
66 ab2f42e7 2019-11-10 stsp cache->maxelemsize = maxelemsize;
67 ab2f42e7 2019-11-10 stsp return cache;
71 ab2f42e7 2019-11-10 stsp got_delta_cache_free(struct got_delta_cache *cache)
73 ab2f42e7 2019-11-10 stsp struct got_delta_cache_element *entry;
75 ab2f42e7 2019-11-10 stsp while (!TAILQ_EMPTY(&cache->entries)) {
76 ab2f42e7 2019-11-10 stsp entry = TAILQ_FIRST(&cache->entries);
77 ab2f42e7 2019-11-10 stsp TAILQ_REMOVE(&cache->entries, entry, entry);
78 ab2f42e7 2019-11-10 stsp free(entry->delta_data);
79 ab2f42e7 2019-11-10 stsp free(entry);
81 ab2f42e7 2019-11-10 stsp free(cache);
85 ab2f42e7 2019-11-10 stsp remove_least_used_element(struct got_delta_cache *cache)
87 ab2f42e7 2019-11-10 stsp struct got_delta_cache_element *entry;
89 ab2f42e7 2019-11-10 stsp if (cache->nelem == 0)
92 ab2f42e7 2019-11-10 stsp entry = TAILQ_LAST(&cache->entries, got_delta_cache_head);
93 ab2f42e7 2019-11-10 stsp TAILQ_REMOVE(&cache->entries, entry, entry);
94 ab2f42e7 2019-11-10 stsp free(entry->delta_data);
95 ab2f42e7 2019-11-10 stsp free(entry);
96 ab2f42e7 2019-11-10 stsp cache->nelem--;
100 ab2f42e7 2019-11-10 stsp const struct got_error *
101 ab2f42e7 2019-11-10 stsp got_delta_cache_add(struct got_delta_cache *cache,
102 ab2f42e7 2019-11-10 stsp off_t delta_data_offset, uint8_t *delta_data, size_t delta_len)
104 ab2f42e7 2019-11-10 stsp struct got_delta_cache_element *entry;
106 ab2f42e7 2019-11-10 stsp if (delta_len > cache->maxelemsize)
107 ab2f42e7 2019-11-10 stsp return got_error(GOT_ERR_NO_SPACE);
109 ab2f42e7 2019-11-10 stsp if (cache->nelem >= cache->maxelem)
110 ab2f42e7 2019-11-10 stsp remove_least_used_element(cache);
112 ab2f42e7 2019-11-10 stsp entry = calloc(1, sizeof(*entry));
113 ab2f42e7 2019-11-10 stsp if (entry == NULL)
114 ab2f42e7 2019-11-10 stsp return got_error_from_errno("calloc");
116 ab2f42e7 2019-11-10 stsp entry->delta_data_offset = delta_data_offset;
117 ab2f42e7 2019-11-10 stsp entry->delta_data = delta_data;
118 ab2f42e7 2019-11-10 stsp entry->delta_len = delta_len;
120 ab2f42e7 2019-11-10 stsp TAILQ_INSERT_HEAD(&cache->entries, entry, entry);
121 ab2f42e7 2019-11-10 stsp cache->nelem++;
122 ab2f42e7 2019-11-10 stsp return NULL;
126 ab2f42e7 2019-11-10 stsp got_delta_cache_get(uint8_t **delta_data, size_t *delta_len,
127 ab2f42e7 2019-11-10 stsp struct got_delta_cache *cache, off_t delta_data_offset)
129 ab2f42e7 2019-11-10 stsp struct got_delta_cache_element *entry;
131 ab2f42e7 2019-11-10 stsp *delta_data = NULL;
132 ab2f42e7 2019-11-10 stsp *delta_len = 0;
133 ab2f42e7 2019-11-10 stsp TAILQ_FOREACH(entry, &cache->entries, entry) {
134 ab2f42e7 2019-11-10 stsp if (entry->delta_data_offset != delta_data_offset)
136 ab2f42e7 2019-11-10 stsp if (entry != TAILQ_FIRST(&cache->entries)) {
137 ab2f42e7 2019-11-10 stsp TAILQ_REMOVE(&cache->entries, entry, entry);
138 ab2f42e7 2019-11-10 stsp TAILQ_INSERT_HEAD(&cache->entries, entry, entry);
140 ab2f42e7 2019-11-10 stsp *delta_data = entry->delta_data;
141 ab2f42e7 2019-11-10 stsp *delta_len = entry->delta_len;