lib/delta_cache.c

   1 /*
   2  * Copyright (c) 2019, 2020 Stefan Sperling <stsp@openbsd.org>
   3  *
   4  * Permission to use, copy, modify, and distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 #include <sys/queue.h>
  18
  19 #include <stdlib.h>
  20 #include <string.h>
  21 #include <stdint.h>
  22 #include <stdio.h>
  23 #include <zlib.h>
  24 #include <limits.h>
  25 #include <time.h>
  26 #include <errno.h>
  27
  28 #include "got_compat.h"
  29
  30 #include "got_object.h"
  31 #include "got_error.h"
  32
  33 #include "got_lib_delta.h"
  34 #include "got_lib_inflate.h"
  35 #include "got_lib_object.h"
  36 #include "got_lib_delta_cache.h"
  37
  38 #ifndef nitems
  39 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
  40 #endif
  41
  42 #define GOT_DELTA_CACHE_MIN_BUCKETS     64
  43 #define GOT_DELTA_CACHE_MAX_BUCKETS     2048
  44 #define GOT_DELTA_CACHE_MAX_CHAIN       2
  45 #define GOT_DELTA_CACHE_MAX_DELTA_SIZE  1024
  46
  47 struct got_cached_delta {
  48         off_t offset;
  49         uint8_t *data;
  50         size_t len;
  51 };
  52
  53 struct got_delta_cache_head {
  54         struct got_cached_delta entries[GOT_DELTA_CACHE_MAX_CHAIN];
  55         unsigned int nchain;
  56 };
  57
  58 struct got_delta_cache {
  59         struct got_delta_cache_head *buckets;
  60         unsigned int nbuckets;
  61         unsigned int totelem;
  62         int cache_search;
  63         int cache_hit;
  64         int cache_miss;
  65         int cache_evict;
  66         int cache_toolarge;
  67         unsigned int flags;
  68 #define GOT_DELTA_CACHE_F_NOMEM 0x01
  69         SIPHASH_KEY key;
  70 };
  71
  72 const struct got_error *
  73 got_delta_cache_alloc(struct got_delta_cache **new)
  74 {
  75         const struct got_error *err;
  76         struct got_delta_cache *cache;
  77
  78         *new = NULL;
  79
  80         cache = calloc(1, sizeof(*cache));
  81         if (cache == NULL)
  82                 return got_error_from_errno("calloc");
  83
  84         cache->buckets = calloc(GOT_DELTA_CACHE_MIN_BUCKETS,
  85             sizeof(cache->buckets[0]));
  86         if (cache->buckets == NULL) {
  87                 err = got_error_from_errno("calloc");
  88                 free(cache);
  89                 return err;
  90         }
  91         cache->nbuckets = GOT_DELTA_CACHE_MIN_BUCKETS;
  92
  93         arc4random_buf(&cache->key, sizeof(cache->key));
  94         *new = cache;
  95         return NULL;
  96 }
  97
  98 void
  99 got_delta_cache_free(struct got_delta_cache *cache)
 100 {
 101         struct got_cached_delta *delta;
 102         unsigned int i;
 103
 104 #ifdef GOT_DELTA_CACHE_DEBUG
 105         fprintf(stderr, "%s: delta cache: %u elements, %d searches, %d hits, "
 106             "%d missed, %d evicted, %d too large\n", getprogname(),
 107             cache->totelem, cache->cache_search, cache->cache_hit,
 108             cache->cache_miss, cache->cache_evict, cache->cache_toolarge);
 109 #endif
 110         for (i = 0; i < cache->nbuckets; i++) {
 111                 struct got_delta_cache_head *head;
 112                 int j;
 113                 head = &cache->buckets[i];
 114                 for (j = 0; j < head->nchain; j++) {
 115                         delta = &head->entries[j];
 116                         free(delta->data);
 117                 }
 118         }
 119         free(cache->buckets);
 120         free(cache);
 121 }
 122
 123 static uint64_t
 124 delta_cache_hash(struct got_delta_cache *cache, off_t delta_offset)
 125 {
 126         return SipHash24(&cache->key, &delta_offset, sizeof(delta_offset));
 127 }
 128
 129 #ifndef GOT_NO_DELTA_CACHE
 130 static const struct got_error *
 131 delta_cache_resize(struct got_delta_cache *cache, unsigned int nbuckets)
 132 {
 133         struct got_delta_cache_head *buckets;
 134         size_t i;
 135
 136         buckets = calloc(nbuckets, sizeof(buckets[0]));
 137         if (buckets == NULL) {
 138                 if (errno != ENOMEM)
 139                         return got_error_from_errno("calloc");
 140                 /* Proceed with our current amount of hash buckets. */
 141                 cache->flags |= GOT_DELTA_CACHE_F_NOMEM;
 142                 return NULL;
 143         }
 144
 145         arc4random_buf(&cache->key, sizeof(cache->key));
 146
 147         for (i = 0; i < cache->nbuckets; i++) {
 148                 unsigned int j;
 149                 for (j = 0; j < cache->buckets[i].nchain; j++) {
 150                         struct got_delta_cache_head *head;
 151                         struct got_cached_delta *delta;
 152                         uint64_t idx;
 153                         delta = &cache->buckets[i].entries[j];
 154                         idx = delta_cache_hash(cache, delta->offset) % nbuckets;
 155                         head = &buckets[idx];
 156                         if (head->nchain < nitems(head->entries)) {
 157                                 struct got_cached_delta *new_delta;
 158                                 new_delta = &head->entries[head->nchain];
 159                                 memcpy(new_delta, delta, sizeof(*new_delta));
 160                                 head->nchain++;
 161                         } else {
 162                                 free(delta->data);
 163                                 cache->totelem--;
 164                         }
 165                 }
 166         }
 167
 168         free(cache->buckets);
 169         cache->buckets = buckets;
 170         cache->nbuckets = nbuckets;
 171         return NULL;
 172 }
 173
 174 static const struct got_error *
 175 delta_cache_grow(struct got_delta_cache *cache)
 176 {
 177         unsigned int nbuckets;
 178
 179         if ((cache->flags & GOT_DELTA_CACHE_F_NOMEM) ||
 180             cache->nbuckets == GOT_DELTA_CACHE_MAX_BUCKETS)
 181                 return NULL;
 182
 183         if (cache->nbuckets >= GOT_DELTA_CACHE_MAX_BUCKETS / 2)
 184                 nbuckets = GOT_DELTA_CACHE_MAX_BUCKETS;
 185         else
 186                 nbuckets = cache->nbuckets * 2;
 187
 188         return delta_cache_resize(cache, nbuckets);
 189 }
 190 #endif
 191
 192 const struct got_error *
 193 got_delta_cache_add(struct got_delta_cache *cache,
 194     off_t delta_data_offset, uint8_t *delta_data, size_t delta_len)
 195 {
 196 #ifdef GOT_NO_DELTA_CACHE
 197         return got_error(GOT_ERR_NO_SPACE);
 198 #else
 199         const struct got_error *err = NULL;
 200         struct got_cached_delta *delta;
 201         struct got_delta_cache_head *head;
 202         uint64_t idx;
 203
 204         if (delta_len > GOT_DELTA_CACHE_MAX_DELTA_SIZE) {
 205                 cache->cache_toolarge++;
 206                 return got_error(GOT_ERR_NO_SPACE);
 207         }
 208
 209         if (cache->nbuckets * 3 < cache->totelem * 4) {
 210                 err = delta_cache_grow(cache);
 211                 if (err)
 212                         return err;
 213         }
 214
 215         idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
 216         head = &cache->buckets[idx];
 217         if (head->nchain >= nitems(head->entries)) {
 218                 delta = &head->entries[head->nchain - 1];
 219                 free(delta->data);
 220                 memset(delta, 0, sizeof(*delta));
 221                 head->nchain--;
 222                 cache->totelem--;
 223                 cache->cache_evict++;
 224         }
 225
 226         delta = &head->entries[head->nchain];
 227         delta->offset = delta_data_offset;
 228         delta->data = delta_data;
 229         delta->len = delta_len;
 230         head->nchain++;
 231         cache->totelem++;
 232
 233         return NULL;
 234 #endif
 235 }
 236
 237 void
 238 got_delta_cache_get(uint8_t **delta_data, size_t *delta_len,
 239     struct got_delta_cache *cache, off_t delta_data_offset)
 240 {
 241         uint64_t idx;
 242         struct got_delta_cache_head *head;
 243         struct got_cached_delta *delta;
 244         int i;
 245
 246         idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
 247         head = &cache->buckets[idx];
 248
 249         cache->cache_search++;
 250         *delta_data = NULL;
 251         *delta_len = 0;
 252         for (i = 0; i < head->nchain; i++) {
 253                 delta = &head->entries[i];
 254                 if (delta->offset != delta_data_offset)
 255                         continue;
 256                 cache->cache_hit++;
 257                 if (i > 0) {
 258                         struct got_cached_delta tmp;
 259                         memcpy(&tmp, &head->entries[0], sizeof(tmp));
 260                         memcpy(&head->entries[0], &head->entries[i],
 261                             sizeof(head->entries[0]));
 262                         memcpy(&head->entries[i], &tmp,
 263                             sizeof(head->entries[i]));
 264                         delta = &head->entries[0];
 265                 }
 266                 *delta_data = delta->data;
 267                 *delta_len = delta->len;
 268                 return;
 269         }
 270
 271         cache->cache_miss++;
 272 }