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 #define GOT_DELTA_CACHE_MAX_FULLTEXT_SIZE       524288
  47
  48
  49 struct got_cached_delta {
  50         off_t offset;
  51         uint8_t *data;
  52         size_t len;
  53         uint8_t *fulltext;
  54         size_t fulltext_len;
  55 };
  56
  57 struct got_delta_cache_head {
  58         struct got_cached_delta entries[GOT_DELTA_CACHE_MAX_CHAIN];
  59         unsigned int nchain;
  60 };
  61
  62 struct got_delta_cache {
  63         struct got_delta_cache_head *buckets;
  64         unsigned int nbuckets;
  65         unsigned int totelem;
  66         int cache_search;
  67         int cache_hit;
  68         int cache_hit_fulltext;
  69         int cache_miss;
  70         int cache_evict;
  71         int cache_toolarge;
  72         int cache_toolarge_fulltext;
  73         int cache_maxtoolarge;
  74         int cache_maxtoolarge_fulltext;
  75         unsigned int flags;
  76 #define GOT_DELTA_CACHE_F_NOMEM 0x01
  77         SIPHASH_KEY key;
  78 };
  79
  80 const struct got_error *
  81 got_delta_cache_alloc(struct got_delta_cache **new)
  82 {
  83         const struct got_error *err;
  84         struct got_delta_cache *cache;
  85
  86         *new = NULL;
  87
  88         cache = calloc(1, sizeof(*cache));
  89         if (cache == NULL)
  90                 return got_error_from_errno("calloc");
  91
  92         cache->buckets = calloc(GOT_DELTA_CACHE_MIN_BUCKETS,
  93             sizeof(cache->buckets[0]));
  94         if (cache->buckets == NULL) {
  95                 err = got_error_from_errno("calloc");
  96                 free(cache);
  97                 return err;
  98         }
  99         cache->nbuckets = GOT_DELTA_CACHE_MIN_BUCKETS;
 100
 101         arc4random_buf(&cache->key, sizeof(cache->key));
 102         *new = cache;
 103         return NULL;
 104 }
 105
 106 void
 107 got_delta_cache_free(struct got_delta_cache *cache)
 108 {
 109         struct got_cached_delta *delta;
 110         unsigned int i;
 111
 112 #ifdef GOT_DELTA_CACHE_DEBUG
 113         fprintf(stderr, "%s: delta cache: %u elements, %d searches, %d hits, "
 114             "%d fulltext hits, %d missed, %d evicted, %d too large (max %d), "
 115             "%d too large fulltext (max %d)\n",
 116             getprogname(), cache->totelem, cache->cache_search,
 117             cache->cache_hit, cache->cache_hit_fulltext,
 118             cache->cache_miss, cache->cache_evict, cache->cache_toolarge,
 119             cache->cache_maxtoolarge,
 120             cache->cache_toolarge_fulltext,
 121             cache->cache_maxtoolarge_fulltext);
 122 #endif
 123         for (i = 0; i < cache->nbuckets; i++) {
 124                 struct got_delta_cache_head *head;
 125                 int j;
 126                 head = &cache->buckets[i];
 127                 for (j = 0; j < head->nchain; j++) {
 128                         delta = &head->entries[j];
 129                         free(delta->data);
 130                 }
 131         }
 132         free(cache->buckets);
 133         free(cache);
 134 }
 135
 136 static uint64_t
 137 delta_cache_hash(struct got_delta_cache *cache, off_t delta_offset)
 138 {
 139         return SipHash24(&cache->key, &delta_offset, sizeof(delta_offset));
 140 }
 141
 142 #ifndef GOT_NO_DELTA_CACHE
 143 static const struct got_error *
 144 delta_cache_resize(struct got_delta_cache *cache, unsigned int nbuckets)
 145 {
 146         struct got_delta_cache_head *buckets;
 147         size_t i;
 148
 149         buckets = calloc(nbuckets, sizeof(buckets[0]));
 150         if (buckets == NULL) {
 151                 if (errno != ENOMEM)
 152                         return got_error_from_errno("calloc");
 153                 /* Proceed with our current amount of hash buckets. */
 154                 cache->flags |= GOT_DELTA_CACHE_F_NOMEM;
 155                 return NULL;
 156         }
 157
 158         arc4random_buf(&cache->key, sizeof(cache->key));
 159
 160         for (i = 0; i < cache->nbuckets; i++) {
 161                 unsigned int j;
 162                 for (j = 0; j < cache->buckets[i].nchain; j++) {
 163                         struct got_delta_cache_head *head;
 164                         struct got_cached_delta *delta;
 165                         uint64_t idx;
 166                         delta = &cache->buckets[i].entries[j];
 167                         idx = delta_cache_hash(cache, delta->offset) % nbuckets;
 168                         head = &buckets[idx];
 169                         if (head->nchain < nitems(head->entries)) {
 170                                 struct got_cached_delta *new_delta;
 171                                 new_delta = &head->entries[head->nchain];
 172                                 memcpy(new_delta, delta, sizeof(*new_delta));
 173                                 head->nchain++;
 174                         } else {
 175                                 free(delta->data);
 176                                 cache->totelem--;
 177                         }
 178                 }
 179         }
 180
 181         free(cache->buckets);
 182         cache->buckets = buckets;
 183         cache->nbuckets = nbuckets;
 184         return NULL;
 185 }
 186
 187 static const struct got_error *
 188 delta_cache_grow(struct got_delta_cache *cache)
 189 {
 190         unsigned int nbuckets;
 191
 192         if ((cache->flags & GOT_DELTA_CACHE_F_NOMEM) ||
 193             cache->nbuckets == GOT_DELTA_CACHE_MAX_BUCKETS)
 194                 return NULL;
 195
 196         if (cache->nbuckets >= GOT_DELTA_CACHE_MAX_BUCKETS / 2)
 197                 nbuckets = GOT_DELTA_CACHE_MAX_BUCKETS;
 198         else
 199                 nbuckets = cache->nbuckets * 2;
 200
 201         return delta_cache_resize(cache, nbuckets);
 202 }
 203 #endif
 204
 205 const struct got_error *
 206 got_delta_cache_add(struct got_delta_cache *cache,
 207     off_t delta_data_offset, uint8_t *delta_data, size_t delta_len)
 208 {
 209 #ifdef GOT_NO_DELTA_CACHE
 210         return got_error(GOT_ERR_NO_SPACE);
 211 #else
 212         const struct got_error *err = NULL;
 213         struct got_cached_delta *delta;
 214         struct got_delta_cache_head *head;
 215         uint64_t idx;
 216
 217         if (delta_len > GOT_DELTA_CACHE_MAX_DELTA_SIZE) {
 218                 cache->cache_toolarge++;
 219                 if (delta_len > cache->cache_maxtoolarge)
 220                         cache->cache_maxtoolarge = delta_len;
 221                 return got_error(GOT_ERR_NO_SPACE);
 222         }
 223
 224         if (cache->nbuckets * 3 < cache->totelem * 4) {
 225                 err = delta_cache_grow(cache);
 226                 if (err)
 227                         return err;
 228         }
 229
 230         idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
 231         head = &cache->buckets[idx];
 232         if (head->nchain >= nitems(head->entries)) {
 233                 delta = &head->entries[head->nchain - 1];
 234                 free(delta->data);
 235                 free(delta->fulltext);
 236                 memset(delta, 0, sizeof(*delta));
 237                 head->nchain--;
 238                 cache->totelem--;
 239                 cache->cache_evict++;
 240         }
 241
 242         delta = &head->entries[head->nchain];
 243         delta->offset = delta_data_offset;
 244         delta->data = delta_data;
 245         delta->len = delta_len;
 246         delta->fulltext = NULL;
 247         delta->fulltext_len = 0;
 248         head->nchain++;
 249         cache->totelem++;
 250
 251         return NULL;
 252 #endif
 253 }
 254
 255 const struct got_error *
 256 got_delta_cache_add_fulltext(struct got_delta_cache *cache,
 257     off_t delta_data_offset, uint8_t *fulltext, size_t fulltext_len)
 258 {
 259 #ifdef GOT_NO_DELTA_CACHE
 260         return got_error(GOT_ERR_NO_SPACE);
 261 #else
 262         struct got_cached_delta *delta;
 263         struct got_delta_cache_head *head;
 264         uint64_t idx;
 265         int i;
 266
 267         if (fulltext_len > GOT_DELTA_CACHE_MAX_FULLTEXT_SIZE) {
 268                 cache->cache_toolarge_fulltext++;
 269                 if (fulltext_len > cache->cache_maxtoolarge)
 270                         cache->cache_maxtoolarge_fulltext = fulltext_len;
 271                 return got_error(GOT_ERR_NO_SPACE);
 272         }
 273
 274         idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
 275         head = &cache->buckets[idx];
 276
 277         for (i = 0; i < head->nchain; i++) {
 278                 delta = &head->entries[i];
 279                 if (delta->offset != delta_data_offset)
 280                         continue;
 281                 if (i > 0) {
 282                         struct got_cached_delta tmp;
 283
 284                         memcpy(&tmp, &head->entries[0], sizeof(tmp));
 285                         memcpy(&head->entries[0], &head->entries[i],
 286                             sizeof(head->entries[0]));
 287                         memcpy(&head->entries[i], &tmp,
 288                             sizeof(head->entries[i]));
 289                         delta = &head->entries[0];
 290                 }
 291                 delta->fulltext = malloc(fulltext_len);
 292                 if (delta->fulltext == NULL)
 293                         return got_error_from_errno("malloc");
 294                 memcpy(delta->fulltext, fulltext, fulltext_len);
 295                 delta->fulltext_len = fulltext_len;
 296                 break;
 297         }
 298
 299         return NULL;
 300 #endif
 301 }
 302
 303 void
 304 got_delta_cache_get(uint8_t **delta_data, size_t *delta_len,
 305     uint8_t **fulltext, size_t *fulltext_len,
 306     struct got_delta_cache *cache, off_t delta_data_offset)
 307 {
 308         uint64_t idx;
 309         struct got_delta_cache_head *head;
 310         struct got_cached_delta *delta;
 311         int i;
 312
 313         idx = delta_cache_hash(cache, delta_data_offset) % cache->nbuckets;
 314         head = &cache->buckets[idx];
 315
 316         cache->cache_search++;
 317         *delta_data = NULL;
 318         *delta_len = 0;
 319         if (fulltext)
 320                 *fulltext = NULL;
 321         if (fulltext_len)
 322                 *fulltext_len = 0;
 323         for (i = 0; i < head->nchain; i++) {
 324                 delta = &head->entries[i];
 325                 if (delta->offset != delta_data_offset)
 326                         continue;
 327                 cache->cache_hit++;
 328                 if (i > 0) {
 329                         struct got_cached_delta tmp;
 330                         memcpy(&tmp, &head->entries[0], sizeof(tmp));
 331                         memcpy(&head->entries[0], &head->entries[i],
 332                             sizeof(head->entries[0]));
 333                         memcpy(&head->entries[i], &tmp,
 334                             sizeof(head->entries[i]));
 335                         delta = &head->entries[0];
 336                 }
 337                 *delta_data = delta->data;
 338                 *delta_len = delta->len;
 339                 if (fulltext && fulltext_len &&
 340                     delta->fulltext && delta->fulltext_len) {
 341                         *fulltext = delta->fulltext;
 342                         *fulltext_len = delta->fulltext_len;
 343                         cache->cache_hit_fulltext++;
 344                 }
 345
 346                 return;
 347         }
 348
 349         cache->cache_miss++;
 350 }