src/mwindow.c

   1 /*
   2  * Copyright (C) the libgit2 contributors. All rights reserved.
   3  *
   4  * This file is part of libgit2, distributed under the GNU GPL v2 with
   5  * a Linking Exception. For full terms see the included COPYING file.
   6  */
   7
   8 #include "mwindow.h"
   9
  10 #include "vector.h"
  11 #include "futils.h"
  12 #include "map.h"
  13 #include "runtime.h"
  14 #include "strmap.h"
  15 #include "pack.h"
  16
  17 #define DEFAULT_WINDOW_SIZE \
  18         (sizeof(void*) >= 8 \
  19                 ? 1 * 1024 * 1024 * 1024 \
  20                 : 32 * 1024 * 1024)
  21
  22 #define DEFAULT_MAPPED_LIMIT \
  23         ((1024 * 1024) * (sizeof(void*) >= 8 ? UINT64_C(8192) : UINT64_C(256)))
  24
  25 /* default is unlimited */
  26 #define DEFAULT_FILE_LIMIT 0
  27
  28 size_t git_mwindow__window_size = DEFAULT_WINDOW_SIZE;
  29 size_t git_mwindow__mapped_limit = DEFAULT_MAPPED_LIMIT;
  30 size_t git_mwindow__file_limit = DEFAULT_FILE_LIMIT;
  31
  32 /* Mutex to control access to `git_mwindow__mem_ctl` and `git__pack_cache`. */
  33 git_mutex git__mwindow_mutex;
  34
  35 /* Whenever you want to read or modify this, grab `git__mwindow_mutex` */
  36 git_mwindow_ctl git_mwindow__mem_ctl;
  37
  38 /* Global list of mwindow files, to open packs once across repos */
  39 git_strmap *git__pack_cache = NULL;
  40
  41 static void git_mwindow_global_shutdown(void)
  42 {
  43         git_strmap *tmp = git__pack_cache;
  44
  45         git_mutex_free(&git__mwindow_mutex);
  46
  47         git__pack_cache = NULL;
  48         git_strmap_free(tmp);
  49 }
  50
  51 int git_mwindow_global_init(void)
  52 {
  53         int error;
  54
  55         GIT_ASSERT(!git__pack_cache);
  56
  57         if ((error = git_mutex_init(&git__mwindow_mutex)) < 0 ||
  58             (error = git_strmap_new(&git__pack_cache)) < 0)
  59             return error;
  60
  61         return git_runtime_shutdown_register(git_mwindow_global_shutdown);
  62 }
  63
  64 int git_mwindow_get_pack(struct git_pack_file **out, const char *path)
  65 {
  66         struct git_pack_file *pack;
  67         char *packname;
  68         int error;
  69
  70         if ((error = git_packfile__name(&packname, path)) < 0)
  71                 return error;
  72
  73         if (git_mutex_lock(&git__mwindow_mutex) < 0) {
  74                 git_error_set(GIT_ERROR_OS, "failed to lock mwindow mutex");
  75                 return -1;
  76         }
  77
  78         pack = git_strmap_get(git__pack_cache, packname);
  79         git__free(packname);
  80
  81         if (pack != NULL) {
  82                 git_atomic32_inc(&pack->refcount);
  83                 git_mutex_unlock(&git__mwindow_mutex);
  84                 *out = pack;
  85                 return 0;
  86         }
  87
  88         /* If we didn't find it, we need to create it */
  89         if ((error = git_packfile_alloc(&pack, path)) < 0) {
  90                 git_mutex_unlock(&git__mwindow_mutex);
  91                 return error;
  92         }
  93
  94         git_atomic32_inc(&pack->refcount);
  95
  96         error = git_strmap_set(git__pack_cache, pack->pack_name, pack);
  97         git_mutex_unlock(&git__mwindow_mutex);
  98         if (error < 0) {
  99                 git_packfile_free(pack, false);
 100                 return error;
 101         }
 102
 103         *out = pack;
 104         return 0;
 105 }
 106
 107 int git_mwindow_put_pack(struct git_pack_file *pack)
 108 {
 109         int count, error;
 110         struct git_pack_file *pack_to_delete = NULL;
 111
 112         if ((error = git_mutex_lock(&git__mwindow_mutex)) < 0)
 113                 return error;
 114
 115         /* put before get would be a corrupted state */
 116         GIT_ASSERT(git__pack_cache);
 117
 118         /* if we cannot find it, the state is corrupted */
 119         GIT_ASSERT(git_strmap_exists(git__pack_cache, pack->pack_name));
 120
 121         count = git_atomic32_dec(&pack->refcount);
 122         if (count == 0) {
 123                 git_strmap_delete(git__pack_cache, pack->pack_name);
 124                 pack_to_delete = pack;
 125         }
 126         git_mutex_unlock(&git__mwindow_mutex);
 127         git_packfile_free(pack_to_delete, false);
 128
 129         return 0;
 130 }
 131
 132 /*
 133  * Free all the windows in a sequence, typically because we're done
 134  * with the file. Needs to hold the git__mwindow_mutex.
 135  */
 136 static int git_mwindow_free_all_locked(git_mwindow_file *mwf)
 137 {
 138         git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
 139         size_t i;
 140
 141         /*
 142          * Remove these windows from the global list
 143          */
 144         for (i = 0; i < ctl->windowfiles.length; ++i){
 145                 if (git_vector_get(&ctl->windowfiles, i) == mwf) {
 146                         git_vector_remove(&ctl->windowfiles, i);
 147                         break;
 148                 }
 149         }
 150
 151         if (ctl->windowfiles.length == 0) {
 152                 git_vector_free(&ctl->windowfiles);
 153                 ctl->windowfiles.contents = NULL;
 154         }
 155
 156         while (mwf->windows) {
 157                 git_mwindow *w = mwf->windows;
 158                 GIT_ASSERT(w->inuse_cnt == 0);
 159
 160                 ctl->mapped -= w->window_map.len;
 161                 ctl->open_windows--;
 162
 163                 git_futils_mmap_free(&w->window_map);
 164
 165                 mwf->windows = w->next;
 166                 git__free(w);
 167         }
 168
 169         return 0;
 170 }
 171
 172 int git_mwindow_free_all(git_mwindow_file *mwf)
 173 {
 174         int error;
 175
 176         if (git_mutex_lock(&git__mwindow_mutex)) {
 177                 git_error_set(GIT_ERROR_THREAD, "unable to lock mwindow mutex");
 178                 return -1;
 179         }
 180
 181         error = git_mwindow_free_all_locked(mwf);
 182
 183         git_mutex_unlock(&git__mwindow_mutex);
 184
 185         return error;
 186 }
 187
 188 /*
 189  * Check if a window 'win' contains the address 'offset'
 190  */
 191 int git_mwindow_contains(git_mwindow *win, off64_t offset)
 192 {
 193         off64_t win_off = win->offset;
 194         return win_off <= offset
 195                 && offset <= (off64_t)(win_off + win->window_map.len);
 196 }
 197
 198 #define GIT_MWINDOW__LRU -1
 199 #define GIT_MWINDOW__MRU 1
 200
 201 /*
 202  * Find the least- or most-recently-used window in a file that is not currently
 203  * being used. The 'only_unused' flag controls whether the caller requires the
 204  * file to only have unused windows. If '*out_window' is non-null, it is used as
 205  * a starting point for the comparison.
 206  *
 207  * Returns whether such a window was found in the file.
 208  */
 209 static bool git_mwindow_scan_recently_used(
 210                 git_mwindow_file *mwf,
 211                 git_mwindow **out_window,
 212                 git_mwindow **out_last,
 213                 bool only_unused,
 214                 int comparison_sign)
 215 {
 216         git_mwindow *w, *w_last;
 217         git_mwindow *lru_window = NULL, *lru_last = NULL;
 218         bool found = false;
 219
 220         GIT_ASSERT_ARG(mwf);
 221         GIT_ASSERT_ARG(out_window);
 222
 223         lru_window = *out_window;
 224         if (out_last)
 225                 lru_last = *out_last;
 226
 227         for (w_last = NULL, w = mwf->windows; w; w_last = w, w = w->next) {
 228                 if (w->inuse_cnt) {
 229                         if (only_unused)
 230                                 return false;
 231                         /* This window is currently being used. Skip it. */
 232                         continue;
 233                 }
 234
 235                 /*
 236                  * If the current one is more (or less) recent than the last one,
 237                  * store it in the output parameter. If lru_window is NULL,
 238                  * it's the first loop, so store it as well.
 239                  */
 240                 if (!lru_window ||
 241                                 (comparison_sign == GIT_MWINDOW__LRU && lru_window->last_used > w->last_used) ||
 242                                 (comparison_sign == GIT_MWINDOW__MRU && lru_window->last_used < w->last_used)) {
 243                         lru_window = w;
 244                         lru_last = w_last;
 245                         found = true;
 246                 }
 247         }
 248
 249         if (!found)
 250                 return false;
 251
 252         *out_window = lru_window;
 253         if (out_last)
 254                 *out_last = lru_last;
 255         return true;
 256 }
 257
 258 /*
 259  * Close the least recently used window (that is currently not being used) out
 260  * of all the files. Called under lock from new_window_locked.
 261  */
 262 static int git_mwindow_close_lru_window_locked(void)
 263 {
 264         git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
 265         git_mwindow_file *cur;
 266         size_t i;
 267         git_mwindow *lru_window = NULL, *lru_last = NULL, **list = NULL;
 268
 269         git_vector_foreach(&ctl->windowfiles, i, cur) {
 270                 if (git_mwindow_scan_recently_used(
 271                                 cur, &lru_window, &lru_last, false, GIT_MWINDOW__LRU)) {
 272                         list = &cur->windows;
 273                 }
 274         }
 275
 276         if (!lru_window) {
 277                 git_error_set(GIT_ERROR_OS, "failed to close memory window; couldn't find LRU");
 278                 return -1;
 279         }
 280
 281         ctl->mapped -= lru_window->window_map.len;
 282         git_futils_mmap_free(&lru_window->window_map);
 283
 284         if (lru_last)
 285                 lru_last->next = lru_window->next;
 286         else
 287                 *list = lru_window->next;
 288
 289         git__free(lru_window);
 290         ctl->open_windows--;
 291
 292         return 0;
 293 }
 294
 295 /*
 296  * Finds the file that does not have any open windows AND whose
 297  * most-recently-used window is the least-recently used one across all
 298  * currently open files.
 299  *
 300  * Called under lock from new_window_locked.
 301  */
 302 static int git_mwindow_find_lru_file_locked(git_mwindow_file **out)
 303 {
 304         git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
 305         git_mwindow_file *lru_file = NULL, *current_file = NULL;
 306         git_mwindow *lru_window = NULL;
 307         size_t i;
 308
 309         git_vector_foreach(&ctl->windowfiles, i, current_file) {
 310                 git_mwindow *mru_window = NULL;
 311                 if (!git_mwindow_scan_recently_used(
 312                                 current_file, &mru_window, NULL, true, GIT_MWINDOW__MRU)) {
 313                         continue;
 314                 }
 315                 if (!lru_window || lru_window->last_used > mru_window->last_used) {
 316                         lru_window = mru_window;
 317                         lru_file = current_file;
 318                 }
 319         }
 320
 321         if (!lru_file) {
 322                 git_error_set(GIT_ERROR_OS, "failed to close memory window file; couldn't find LRU");
 323                 return -1;
 324         }
 325
 326         *out = lru_file;
 327         return 0;
 328 }
 329
 330 /* This gets called under lock from git_mwindow_open */
 331 static git_mwindow *new_window_locked(
 332         git_file fd,
 333         off64_t size,
 334         off64_t offset)
 335 {
 336         git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
 337         size_t walign = git_mwindow__window_size / 2;
 338         off64_t len;
 339         git_mwindow *w;
 340
 341         w = git__calloc(1, sizeof(*w));
 342
 343         if (w == NULL)
 344                 return NULL;
 345
 346         w->offset = (offset / walign) * walign;
 347
 348         len = size - w->offset;
 349         if (len > (off64_t)git_mwindow__window_size)
 350                 len = (off64_t)git_mwindow__window_size;
 351
 352         ctl->mapped += (size_t)len;
 353
 354         while (git_mwindow__mapped_limit < ctl->mapped &&
 355                         git_mwindow_close_lru_window_locked() == 0) /* nop */;
 356
 357         /*
 358          * We treat `mapped_limit` as a soft limit. If we can't find a
 359          * window to close and are above the limit, we still mmap the new
 360          * window.
 361          */
 362
 363         if (git_futils_mmap_ro(&w->window_map, fd, w->offset, (size_t)len) < 0) {
 364                 /*
 365                  * The first error might be down to memory fragmentation even if
 366                  * we're below our soft limits, so free up what we can and try again.
 367                  */
 368
 369                 while (git_mwindow_close_lru_window_locked() == 0)
 370                         /* nop */;
 371
 372                 if (git_futils_mmap_ro(&w->window_map, fd, w->offset, (size_t)len) < 0) {
 373                         git__free(w);
 374                         return NULL;
 375                 }
 376         }
 377
 378         ctl->mmap_calls++;
 379         ctl->open_windows++;
 380
 381         if (ctl->mapped > ctl->peak_mapped)
 382                 ctl->peak_mapped = ctl->mapped;
 383
 384         if (ctl->open_windows > ctl->peak_open_windows)
 385                 ctl->peak_open_windows = ctl->open_windows;
 386
 387         return w;
 388 }
 389
 390 /*
 391  * Open a new window, closing the least recenty used until we have
 392  * enough space. Don't forget to add it to your list
 393  */
 394 unsigned char *git_mwindow_open(
 395         git_mwindow_file *mwf,
 396         git_mwindow **cursor,
 397         off64_t offset,
 398         size_t extra,
 399         unsigned int *left)
 400 {
 401         git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
 402         git_mwindow *w = *cursor;
 403
 404         if (git_mutex_lock(&git__mwindow_mutex)) {
 405                 git_error_set(GIT_ERROR_THREAD, "unable to lock mwindow mutex");
 406                 return NULL;
 407         }
 408
 409         if (!w || !(git_mwindow_contains(w, offset) && git_mwindow_contains(w, offset + extra))) {
 410                 if (w) {
 411                         w->inuse_cnt--;
 412                 }
 413
 414                 for (w = mwf->windows; w; w = w->next) {
 415                         if (git_mwindow_contains(w, offset) &&
 416                                 git_mwindow_contains(w, offset + extra))
 417                                 break;
 418                 }
 419
 420                 /*
 421                  * If there isn't a suitable window, we need to create a new
 422                  * one.
 423                  */
 424                 if (!w) {
 425                         w = new_window_locked(mwf->fd, mwf->size, offset);
 426                         if (w == NULL) {
 427                                 git_mutex_unlock(&git__mwindow_mutex);
 428                                 return NULL;
 429                         }
 430                         w->next = mwf->windows;
 431                         mwf->windows = w;
 432                 }
 433         }
 434
 435         /* If we changed w, store it in the cursor */
 436         if (w != *cursor) {
 437                 w->last_used = ctl->used_ctr++;
 438                 w->inuse_cnt++;
 439                 *cursor = w;
 440         }
 441
 442         offset -= w->offset;
 443
 444         if (left)
 445                 *left = (unsigned int)(w->window_map.len - offset);
 446
 447         git_mutex_unlock(&git__mwindow_mutex);
 448         return (unsigned char *) w->window_map.data + offset;
 449 }
 450
 451 int git_mwindow_file_register(git_mwindow_file *mwf)
 452 {
 453         git_vector closed_files = GIT_VECTOR_INIT;
 454         git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
 455         int error;
 456         size_t i;
 457         git_mwindow_file *closed_file = NULL;
 458
 459         if (git_mutex_lock(&git__mwindow_mutex)) {
 460                 git_error_set(GIT_ERROR_THREAD, "unable to lock mwindow mutex");
 461                 return -1;
 462         }
 463
 464         if (ctl->windowfiles.length == 0 &&
 465             (error = git_vector_init(&ctl->windowfiles, 8, NULL)) < 0) {
 466                 git_mutex_unlock(&git__mwindow_mutex);
 467                 goto cleanup;
 468         }
 469
 470         if (git_mwindow__file_limit) {
 471                 git_mwindow_file *lru_file;
 472                 while (git_mwindow__file_limit <= ctl->windowfiles.length &&
 473                                 git_mwindow_find_lru_file_locked(&lru_file) == 0) {
 474                         if ((error = git_vector_insert(&closed_files, lru_file)) < 0) {
 475                                 /*
 476                                  * Exceeding the file limit seems preferrable to being open to
 477                                  * data races that can end up corrupting the heap.
 478                                  */
 479                                 break;
 480                         }
 481                         git_mwindow_free_all_locked(lru_file);
 482                 }
 483         }
 484
 485         error = git_vector_insert(&ctl->windowfiles, mwf);
 486         git_mutex_unlock(&git__mwindow_mutex);
 487         if (error < 0)
 488                 goto cleanup;
 489
 490         /*
 491          * Once we have released the global windowfiles lock, we can close each
 492          * individual file. Before doing so, acquire that file's lock to avoid
 493          * closing a file that is currently being used.
 494          */
 495         git_vector_foreach(&closed_files, i, closed_file) {
 496                 error = git_mutex_lock(&closed_file->lock);
 497                 if (error < 0)
 498                         continue;
 499                 p_close(closed_file->fd);
 500                 closed_file->fd = -1;
 501                 git_mutex_unlock(&closed_file->lock);
 502         }
 503
 504 cleanup:
 505         git_vector_free(&closed_files);
 506         return error;
 507 }
 508
 509 void git_mwindow_file_deregister(git_mwindow_file *mwf)
 510 {
 511         git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
 512         git_mwindow_file *cur;
 513         size_t i;
 514
 515         if (git_mutex_lock(&git__mwindow_mutex))
 516                 return;
 517
 518         git_vector_foreach(&ctl->windowfiles, i, cur) {
 519                 if (cur == mwf) {
 520                         git_vector_remove(&ctl->windowfiles, i);
 521                         git_mutex_unlock(&git__mwindow_mutex);
 522                         return;
 523                 }
 524         }
 525         git_mutex_unlock(&git__mwindow_mutex);
 526 }
 527
 528 void git_mwindow_close(git_mwindow **window)
 529 {
 530         git_mwindow *w = *window;
 531         if (w) {
 532                 if (git_mutex_lock(&git__mwindow_mutex)) {
 533                         git_error_set(GIT_ERROR_THREAD, "unable to lock mwindow mutex");
 534                         return;
 535                 }
 536
 537                 w->inuse_cnt--;
 538                 git_mutex_unlock(&git__mwindow_mutex);
 539                 *window = NULL;
 540         }
 541 }