lib/object_cache.c

   1 /*
   2  * Copyright (c) 2018 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/time.h>
  18 #include <sys/queue.h>
  19 #include <sys/resource.h>
  20
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <stdint.h>
  24 #include <string.h>
  25 #include <limits.h>
  26 #include <zlib.h>
  27
  28 #include "got_compat.h"
  29 #include "got_error.h"
  30 #include "got_object.h"
  31
  32 #include "got_lib_delta.h"
  33 #include "got_lib_inflate.h"
  34 #include "got_lib_object.h"
  35 #include "got_lib_object_idset.h"
  36 #include "got_lib_object_cache.h"
  37
  38 /*
  39  * XXX This should be reworked to track cache size and usage in bytes,
  40  * rather than tracking N elements capped to a maximum element size.
  41  */
  42 #define GOT_OBJECT_CACHE_SIZE_OBJ       256
  43 #define GOT_OBJECT_CACHE_SIZE_TREE      256
  44 #define GOT_OBJECT_CACHE_SIZE_COMMIT    64
  45 #define GOT_OBJECT_CACHE_SIZE_TAG       256
  46 #define GOT_OBJECT_CACHE_SIZE_RAW       16
  47 #define GOT_OBJECT_CACHE_MAX_ELEM_SIZE  1048576 /* 1 MB */
  48
  49 const struct got_error *
  50 got_object_cache_init(struct got_object_cache *cache,
  51     enum got_object_cache_type type)
  52 {
  53         struct rlimit rl;
  54
  55         memset(cache, 0, sizeof(*cache));
  56
  57         cache->idset = got_object_idset_alloc();
  58         if (cache->idset == NULL)
  59                 return got_error_from_errno("got_object_idset_alloc");
  60
  61         cache->type = type;
  62         switch (type) {
  63         case GOT_OBJECT_CACHE_TYPE_OBJ:
  64                 cache->size = GOT_OBJECT_CACHE_SIZE_OBJ;
  65                 break;
  66         case GOT_OBJECT_CACHE_TYPE_TREE:
  67                 cache->size = GOT_OBJECT_CACHE_SIZE_TREE;
  68                 break;
  69         case GOT_OBJECT_CACHE_TYPE_COMMIT:
  70                 cache->size = GOT_OBJECT_CACHE_SIZE_COMMIT;
  71                 break;
  72         case GOT_OBJECT_CACHE_TYPE_TAG:
  73                 cache->size = GOT_OBJECT_CACHE_SIZE_TAG;
  74                 break;
  75         case GOT_OBJECT_CACHE_TYPE_RAW:
  76                 if (getrlimit(RLIMIT_NOFILE, &rl) == -1)
  77                         return got_error_from_errno("getrlimit");
  78                 cache->size = GOT_OBJECT_CACHE_SIZE_RAW;
  79                 if (cache->size > rl.rlim_cur / 16)
  80                         cache->size = rl.rlim_cur / 16;
  81                 break;
  82         }
  83         return NULL;
  84 }
  85
  86 static size_t
  87 get_size_obj(struct got_object *obj)
  88 {
  89         size_t size = sizeof(*obj);
  90         struct got_delta *delta;
  91
  92         if ((obj->flags & GOT_OBJ_FLAG_DELTIFIED) == 0)
  93                 return size;
  94
  95         STAILQ_FOREACH(delta, &obj->deltas.entries, entry) {
  96                 if (SIZE_MAX - sizeof(*delta) < size)
  97                         return SIZE_MAX;
  98                 size += sizeof(*delta);
  99         }
 100
 101         return size;
 102 }
 103
 104 static size_t
 105 get_size_tree(struct got_tree_object *tree)
 106 {
 107         size_t size = sizeof(*tree);
 108
 109         size += sizeof(struct got_tree_entry) * tree->nentries;
 110         return size;
 111 }
 112
 113 static size_t
 114 get_size_commit(struct got_commit_object *commit)
 115 {
 116         size_t size = sizeof(*commit);
 117         struct got_object_qid *qid;
 118
 119         size += sizeof(*commit->tree_id);
 120         size += strlen(commit->author);
 121         size += strlen(commit->committer);
 122         size += strlen(commit->logmsg);
 123
 124         STAILQ_FOREACH(qid, &commit->parent_ids, entry)
 125                 size += sizeof(*qid) + sizeof(qid->id);
 126
 127         return size;
 128 }
 129
 130 static size_t
 131 get_size_tag(struct got_tag_object *tag)
 132 {
 133         size_t size = sizeof(*tag);
 134
 135         size += strlen(tag->tag);
 136         size += strlen(tag->tagger);
 137         size += strlen(tag->tagmsg);
 138
 139         return size;
 140 }
 141
 142 static size_t
 143 get_size_raw(struct got_raw_object *raw)
 144 {
 145         return sizeof(*raw);
 146 }
 147
 148 const struct got_error *
 149 got_object_cache_add(struct got_object_cache *cache, struct got_object_id *id,
 150     void *item)
 151 {
 152         const struct got_error *err = NULL;
 153         struct got_object_cache_entry *ce;
 154         int nelem;
 155         size_t size;
 156
 157         switch (cache->type) {
 158         case GOT_OBJECT_CACHE_TYPE_OBJ:
 159                 size = get_size_obj((struct got_object *)item);
 160                 break;
 161         case GOT_OBJECT_CACHE_TYPE_TREE:
 162                 size = get_size_tree((struct got_tree_object *)item);
 163                 break;
 164         case GOT_OBJECT_CACHE_TYPE_COMMIT:
 165                 size = get_size_commit((struct got_commit_object *)item);
 166                 break;
 167         case GOT_OBJECT_CACHE_TYPE_TAG:
 168                 size = get_size_tag((struct got_tag_object *)item);
 169                 break;
 170         case GOT_OBJECT_CACHE_TYPE_RAW:
 171                 size = get_size_raw((struct got_raw_object *)item);
 172                 break;
 173         default:
 174                 return got_error(GOT_ERR_OBJ_TYPE);
 175         }
 176
 177         if (size > GOT_OBJECT_CACHE_MAX_ELEM_SIZE) {
 178 #ifdef GOT_OBJ_CACHE_DEBUG
 179                 char *id_str;
 180                 if (got_object_id_str(&id_str, id) != NULL)
 181                         return got_error_from_errno("got_object_id_str");
 182                 fprintf(stderr, "%s: not caching ", getprogname());
 183                 switch (cache->type) {
 184                 case GOT_OBJECT_CACHE_TYPE_OBJ:
 185                         fprintf(stderr, "object");
 186                         break;
 187                 case GOT_OBJECT_CACHE_TYPE_TREE:
 188                         fprintf(stderr, "tree");
 189                         break;
 190                 case GOT_OBJECT_CACHE_TYPE_COMMIT:
 191                         fprintf(stderr, "commit");
 192                         break;
 193                 case GOT_OBJECT_CACHE_TYPE_TAG:
 194                         fprintf(stderr, "tag");
 195                         break;
 196                 case GOT_OBJECT_CACHE_TYPE_RAW:
 197                         fprintf(stderr, "raw");
 198                         break;
 199                 }
 200                 fprintf(stderr, " %s (%zd bytes; %zd MB)\n", id_str, size,
 201                     size/1024/1024);
 202                 free(id_str);
 203 #endif
 204                 cache->cache_toolarge++;
 205                 return got_error(GOT_ERR_OBJ_TOO_LARGE);
 206         }
 207
 208         nelem = got_object_idset_num_elements(cache->idset);
 209         if (nelem >= cache->size) {
 210                 err = got_object_idset_remove((void **)&ce,
 211                     cache->idset, NULL);
 212                 if (err)
 213                         return err;
 214                 switch (cache->type) {
 215                 case GOT_OBJECT_CACHE_TYPE_OBJ:
 216                         got_object_close(ce->data.obj);
 217                         break;
 218                 case GOT_OBJECT_CACHE_TYPE_TREE:
 219                         got_object_tree_close(ce->data.tree);
 220                         break;
 221                 case GOT_OBJECT_CACHE_TYPE_COMMIT:
 222                         got_object_commit_close(ce->data.commit);
 223                         break;
 224                 case GOT_OBJECT_CACHE_TYPE_TAG:
 225                         got_object_tag_close(ce->data.tag);
 226                         break;
 227                 case GOT_OBJECT_CACHE_TYPE_RAW:
 228                         got_object_raw_close(ce->data.raw);
 229                         break;
 230                 }
 231                 memset(ce, 0, sizeof(*ce));
 232                 cache->cache_evict++;
 233         } else {
 234                 ce = malloc(sizeof(*ce));
 235                 if (ce == NULL)
 236                         return got_error_from_errno("malloc");
 237         }
 238
 239         memcpy(&ce->id, id, sizeof(ce->id));
 240         switch (cache->type) {
 241         case GOT_OBJECT_CACHE_TYPE_OBJ:
 242                 ce->data.obj = (struct got_object *)item;
 243                 break;
 244         case GOT_OBJECT_CACHE_TYPE_TREE:
 245                 ce->data.tree = (struct got_tree_object *)item;
 246                 break;
 247         case GOT_OBJECT_CACHE_TYPE_COMMIT:
 248                 ce->data.commit = (struct got_commit_object *)item;
 249                 break;
 250         case GOT_OBJECT_CACHE_TYPE_TAG:
 251                 ce->data.tag = (struct got_tag_object *)item;
 252                 break;
 253         case GOT_OBJECT_CACHE_TYPE_RAW:
 254                 ce->data.raw = (struct got_raw_object *)item;
 255                 break;
 256         }
 257
 258         err = got_object_idset_add(cache->idset, id, ce);
 259         if (err)
 260                 free(ce);
 261         else if (size > cache->max_cached_size)
 262                 cache->max_cached_size = size;
 263         return err;
 264 }
 265
 266 void *
 267 got_object_cache_get(struct got_object_cache *cache, struct got_object_id *id)
 268 {
 269         struct got_object_cache_entry *ce;
 270
 271         cache->cache_searches++;
 272         ce = got_object_idset_get(cache->idset, id);
 273         if (ce) {
 274                 cache->cache_hit++;
 275                 switch (cache->type) {
 276                 case GOT_OBJECT_CACHE_TYPE_OBJ:
 277                         return ce->data.obj;
 278                 case GOT_OBJECT_CACHE_TYPE_TREE:
 279                         return ce->data.tree;
 280                 case GOT_OBJECT_CACHE_TYPE_COMMIT:
 281                         return ce->data.commit;
 282                 case GOT_OBJECT_CACHE_TYPE_TAG:
 283                         return ce->data.tag;
 284                 case GOT_OBJECT_CACHE_TYPE_RAW:
 285                         return ce->data.raw;
 286                 }
 287         }
 288
 289         cache->cache_miss++;
 290         return NULL;
 291 }
 292
 293 #ifdef GOT_OBJ_CACHE_DEBUG
 294 static void
 295 print_cache_stats(struct got_object_cache *cache, const char *name)
 296 {
 297         fprintf(stderr, "%s: %s cache: %d elements, %d searches, %d hits, "
 298             "%d missed, %d evicted, %d too large, max cached %zd bytes\n",
 299             getprogname(), name,
 300             cache->idset ? got_object_idset_num_elements(cache->idset) : -1,
 301             cache->cache_searches, cache->cache_hit,
 302             cache->cache_miss, cache->cache_evict, cache->cache_toolarge,
 303             cache->max_cached_size);
 304 }
 305
 306 static const struct got_error *
 307 check_refcount(struct got_object_id *id, void *data, void *arg)
 308 {
 309         struct got_object_cache *cache = arg;
 310         struct got_object_cache_entry *ce = data;
 311         struct got_object *obj;
 312         struct got_tree_object *tree;
 313         struct got_commit_object *commit;
 314         struct got_tag_object *tag;
 315         struct got_raw_object *raw;
 316         char *id_str;
 317
 318         if (got_object_id_str(&id_str, id) != NULL)
 319                 return NULL;
 320
 321         switch (cache->type) {
 322         case GOT_OBJECT_CACHE_TYPE_OBJ:
 323                 obj = ce->data.obj;
 324                 if (obj->refcnt == 1)
 325                         break;
 326                 fprintf(stderr, "object %s has %d unclaimed references\n",
 327                     id_str, obj->refcnt - 1);
 328                 break;
 329         case GOT_OBJECT_CACHE_TYPE_TREE:
 330                 tree = ce->data.tree;
 331                 if (tree->refcnt == 1)
 332                         break;
 333                 fprintf(stderr, "tree %s has %d unclaimed references\n",
 334                     id_str, tree->refcnt - 1);
 335                 break;
 336         case GOT_OBJECT_CACHE_TYPE_COMMIT:
 337                 commit = ce->data.commit;
 338                 if (commit->refcnt == 1)
 339                         break;
 340                 fprintf(stderr, "commit %s has %d unclaimed references\n",
 341                     id_str, commit->refcnt - 1);
 342                 break;
 343         case GOT_OBJECT_CACHE_TYPE_TAG:
 344                 tag = ce->data.tag;
 345                 if (tag->refcnt == 1)
 346                         break;
 347                 fprintf(stderr, "tag %s has %d unclaimed references\n",
 348                     id_str, tag->refcnt - 1);
 349                 break;
 350         case GOT_OBJECT_CACHE_TYPE_RAW:
 351                 raw = ce->data.raw;
 352                 if (raw->refcnt == 1)
 353                         break;
 354                 fprintf(stderr, "raw %s has %d unclaimed references\n",
 355                     id_str, raw->refcnt - 1);
 356                 break;
 357         }
 358         free(id_str);
 359         return NULL;
 360 }
 361 #endif
 362
 363 static const struct got_error *
 364 free_entry(struct got_object_id *id, void *data, void *arg)
 365 {
 366         struct got_object_cache *cache = arg;
 367         struct got_object_cache_entry *ce = data;
 368
 369         switch (cache->type) {
 370         case GOT_OBJECT_CACHE_TYPE_OBJ:
 371                 got_object_close(ce->data.obj);
 372                 break;
 373         case GOT_OBJECT_CACHE_TYPE_TREE:
 374                 got_object_tree_close(ce->data.tree);
 375                 break;
 376         case GOT_OBJECT_CACHE_TYPE_COMMIT:
 377                 got_object_commit_close(ce->data.commit);
 378                 break;
 379         case GOT_OBJECT_CACHE_TYPE_TAG:
 380                 got_object_tag_close(ce->data.tag);
 381                 break;
 382         case GOT_OBJECT_CACHE_TYPE_RAW:
 383                 got_object_raw_close(ce->data.raw);
 384                 break;
 385         }
 386
 387         free(ce);
 388
 389         return NULL;
 390 }
 391
 392 void
 393 got_object_cache_close(struct got_object_cache *cache)
 394 {
 395 #ifdef GOT_OBJ_CACHE_DEBUG
 396         switch (cache->type) {
 397         case GOT_OBJECT_CACHE_TYPE_OBJ:
 398                 print_cache_stats(cache, "object");
 399                 break;
 400         case GOT_OBJECT_CACHE_TYPE_TREE:
 401                 print_cache_stats(cache, "tree");
 402                 break;
 403         case GOT_OBJECT_CACHE_TYPE_COMMIT:
 404                 print_cache_stats(cache, "commit");
 405                 break;
 406         case GOT_OBJECT_CACHE_TYPE_TAG:
 407                 print_cache_stats(cache, "tag");
 408                 break;
 409         case GOT_OBJECT_CACHE_TYPE_RAW:
 410                 print_cache_stats(cache, "raw");
 411                 break;
 412         }
 413
 414         if (cache->idset)
 415                 got_object_idset_for_each(cache->idset, check_refcount, cache);
 416 #endif
 417
 418         if (cache->idset) {
 419                 got_object_idset_for_each(cache->idset, free_entry, cache);
 420                 got_object_idset_free(cache->idset);
 421                 cache->idset = NULL;
 422         }
 423         cache->size = 0;
 424 }