mwindow.c 12.6 KB
Newer Older
1
/*
Edward Thomson committed
2
 * Copyright (C) the libgit2 contributors. All rights reserved.
3
 *
Vicent Marti committed
4 5
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * 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 15 16
#include "strmap.h"
#include "pack.h"

17 18
#define DEFAULT_WINDOW_SIZE \
	(sizeof(void*) >= 8 \
Vicent Marti committed
19
		? 1 * 1024 * 1024 * 1024 \
20 21 22
		: 32 * 1024 * 1024)

#define DEFAULT_MAPPED_LIMIT \
23
	((1024 * 1024) * (sizeof(void*) >= 8 ? UINT64_C(8192) : UINT64_C(256)))
24

lhchavez committed
25 26
/* default is unlimited */
#define DEFAULT_FILE_LIMIT 0
27

Vicent Marti committed
28 29
size_t git_mwindow__window_size = DEFAULT_WINDOW_SIZE;
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 34
git_mutex git__mwindow_mutex;

35
/* Whenever you want to read or modify this, grab `git__mwindow_mutex` */
lhchavez committed
36
git_mwindow_ctl git_mwindow__mem_ctl;
37

38 39 40
/* Global list of mwindow files, to open packs once across repos */
git_strmap *git__pack_cache = NULL;

41
static void git_mwindow_global_shutdown(void)
42
{
43
	git_strmap *tmp = git__pack_cache;
44

45 46
	git_mutex_free(&git__mwindow_mutex);

47 48
	git__pack_cache = NULL;
	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 58 59
	if ((error = git_mutex_init(&git__mwindow_mutex)) < 0 ||
	    (error = git_strmap_new(&git__pack_cache)) < 0)
	    return error;
60

61
	return git_runtime_shutdown_register(git_mwindow_global_shutdown);
62 63
}

64 65 66 67
int git_mwindow_get_pack(
	struct git_pack_file **out,
	const char *path,
	git_oid_t oid_type)
68 69
{
	struct git_pack_file *pack;
70 71
	char *packname;
	int error;
72 73 74 75

	if ((error = git_packfile__name(&packname, path)) < 0)
		return error;

76
	if (git_mutex_lock(&git__mwindow_mutex) < 0) {
77
		git_error_set(GIT_ERROR_OS, "failed to lock mwindow mutex");
78
		return -1;
79
	}
80

81
	pack = git_strmap_get(git__pack_cache, packname);
82 83
	git__free(packname);

84
	if (pack != NULL) {
85
		git_atomic32_inc(&pack->refcount);
86 87 88 89 90 91
		git_mutex_unlock(&git__mwindow_mutex);
		*out = pack;
		return 0;
	}

	/* If we didn't find it, we need to create it */
92
	if ((error = git_packfile_alloc(&pack, path, oid_type)) < 0) {
93 94 95 96
		git_mutex_unlock(&git__mwindow_mutex);
		return error;
	}

97
	git_atomic32_inc(&pack->refcount);
98

99
	error = git_strmap_set(git__pack_cache, pack->pack_name, pack);
100
	git_mutex_unlock(&git__mwindow_mutex);
101
	if (error < 0) {
102 103
		git_packfile_free(pack, false);
		return error;
104
	}
105

106 107 108 109
	*out = pack;
	return 0;
}

110
int git_mwindow_put_pack(struct git_pack_file *pack)
111
{
112
	int count, error;
113
	struct git_pack_file *pack_to_delete = NULL;
114

115 116
	if ((error = git_mutex_lock(&git__mwindow_mutex)) < 0)
		return error;
117

118
	/* put before get would be a corrupted state */
119
	GIT_ASSERT(git__pack_cache);
120

121
	/* if we cannot find it, the state is corrupted */
122
	GIT_ASSERT(git_strmap_exists(git__pack_cache, pack->pack_name));
123

124
	count = git_atomic32_dec(&pack->refcount);
125
	if (count == 0) {
126
		git_strmap_delete(git__pack_cache, pack->pack_name);
127
		pack_to_delete = pack;
128 129
	}
	git_mutex_unlock(&git__mwindow_mutex);
130
	git_packfile_free(pack_to_delete, false);
131

132
	return 0;
133 134 135 136
}

/*
 * Free all the windows in a sequence, typically because we're done
137
 * with the file. Needs to hold the git__mwindow_mutex.
138
 */
139
static int git_mwindow_free_all_locked(git_mwindow_file *mwf)
140
{
lhchavez committed
141
	git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
142 143
	size_t i;

144 145 146
	/*
	 * Remove these windows from the global list
	 */
147 148 149
	for (i = 0; i < ctl->windowfiles.length; ++i){
		if (git_vector_get(&ctl->windowfiles, i) == mwf) {
			git_vector_remove(&ctl->windowfiles, i);
150 151 152 153
			break;
		}
	}

154 155 156
	if (ctl->windowfiles.length == 0) {
		git_vector_free(&ctl->windowfiles);
		ctl->windowfiles.contents = NULL;
157 158 159 160
	}

	while (mwf->windows) {
		git_mwindow *w = mwf->windows;
161
		GIT_ASSERT(w->inuse_cnt == 0);
162

163 164
		ctl->mapped -= w->window_map.len;
		ctl->open_windows--;
165 166 167 168

		git_futils_mmap_free(&w->window_map);

		mwf->windows = w->next;
169
		git__free(w);
170
	}
171 172

	return 0;
173 174
}

175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
int git_mwindow_free_all(git_mwindow_file *mwf)
{
	int error;

	if (git_mutex_lock(&git__mwindow_mutex)) {
		git_error_set(GIT_ERROR_THREAD, "unable to lock mwindow mutex");
		return -1;
	}

	error = git_mwindow_free_all_locked(mwf);

	git_mutex_unlock(&git__mwindow_mutex);

	return error;
}

191
/*
192 193 194 195
 * Check if a window 'win' contains both the address 'offset' and 'extra'.
 *
 * 'extra' is the size of the hash we're using as we always want to make sure
 * that it's contained.
196
 */
197
int git_mwindow_contains(git_mwindow *win, off64_t offset, off64_t extra)
198
{
199
	off64_t win_off = win->offset;
200
	return win_off <= offset
201
		&& (offset + extra) <= (off64_t)(win_off + win->window_map.len);
202 203
}

lhchavez committed
204 205 206
#define GIT_MWINDOW__LRU -1
#define GIT_MWINDOW__MRU 1

207
/*
lhchavez committed
208 209
 * Find the least- or most-recently-used window in a file that is not currently
 * being used. The 'only_unused' flag controls whether the caller requires the
210 211
 * file to only have unused windows. If '*out_window' is non-null, it is used as
 * a starting point for the comparison.
lhchavez committed
212 213
 *
 * Returns whether such a window was found in the file.
214
 */
lhchavez committed
215 216 217 218 219 220
static bool git_mwindow_scan_recently_used(
		git_mwindow_file *mwf,
		git_mwindow **out_window,
		git_mwindow **out_last,
		bool only_unused,
		int comparison_sign)
221
{
lhchavez committed
222 223
	git_mwindow *w, *w_last;
	git_mwindow *lru_window = NULL, *lru_last = NULL;
224
	bool found = false;
lhchavez committed
225

226 227
	GIT_ASSERT_ARG(mwf);
	GIT_ASSERT_ARG(out_window);
lhchavez committed
228

229 230 231 232
	lru_window = *out_window;
	if (out_last)
		lru_last = *out_last;

lhchavez committed
233 234 235 236 237 238 239 240 241 242 243 244 245
	for (w_last = NULL, w = mwf->windows; w; w_last = w, w = w->next) {
		if (w->inuse_cnt) {
			if (only_unused)
				return false;
			/* This window is currently being used. Skip it. */
			continue;
		}

		/*
		 * If the current one is more (or less) recent than the last one,
		 * store it in the output parameter. If lru_window is NULL,
		 * it's the first loop, so store it as well.
		 */
246
		if (!lru_window || (comparison_sign * w->last_used) > lru_window->last_used) {
lhchavez committed
247 248
			lru_window = w;
			lru_last = w_last;
249
			found = true;
250 251
		}
	}
lhchavez committed
252

253
	if (!found)
lhchavez committed
254 255 256 257 258 259
		return false;

	*out_window = lru_window;
	if (out_last)
		*out_last = lru_last;
	return true;
260 261 262
}

/*
lhchavez committed
263
 * Close the least recently used window (that is currently not being used) out
264
 * of all the files. Called under lock from new_window_locked.
265
 */
266
static int git_mwindow_close_lru_window_locked(void)
267
{
lhchavez committed
268
	git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
269
	git_mwindow_file *cur;
270
	size_t i;
lhchavez committed
271
	git_mwindow *lru_window = NULL, *lru_last = NULL, **list = NULL;
272

273
	git_vector_foreach(&ctl->windowfiles, i, cur) {
lhchavez committed
274 275
		if (git_mwindow_scan_recently_used(
				cur, &lru_window, &lru_last, false, GIT_MWINDOW__LRU)) {
276
			list = &cur->windows;
lhchavez committed
277
		}
278 279
	}

lhchavez committed
280
	if (!lru_window) {
281
		git_error_set(GIT_ERROR_OS, "failed to close memory window; couldn't find LRU");
282 283
		return -1;
	}
284

lhchavez committed
285 286
	ctl->mapped -= lru_window->window_map.len;
	git_futils_mmap_free(&lru_window->window_map);
287

lhchavez committed
288 289
	if (lru_last)
		lru_last->next = lru_window->next;
290
	else
lhchavez committed
291
		*list = lru_window->next;
292

lhchavez committed
293
	git__free(lru_window);
294
	ctl->open_windows--;
295

296
	return 0;
297 298
}

299
/*
300
 * Finds the file that does not have any open windows AND whose
301 302
 * most-recently-used window is the least-recently used one across all
 * currently open files.
lhchavez committed
303
 *
304
 * Called under lock from new_window_locked.
305
 */
306
static int git_mwindow_find_lru_file_locked(git_mwindow_file **out)
307
{
lhchavez committed
308 309 310
	git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
	git_mwindow_file *lru_file = NULL, *current_file = NULL;
	git_mwindow *lru_window = NULL;
311 312
	size_t i;

lhchavez committed
313 314 315 316 317 318
	git_vector_foreach(&ctl->windowfiles, i, current_file) {
		git_mwindow *mru_window = NULL;
		if (!git_mwindow_scan_recently_used(
				current_file, &mru_window, NULL, true, GIT_MWINDOW__MRU)) {
			continue;
		}
319 320
		if (!lru_window || lru_window->last_used > mru_window->last_used) {
			lru_window = mru_window;
lhchavez committed
321
			lru_file = current_file;
322
		}
323 324
	}

lhchavez committed
325
	if (!lru_file) {
326 327 328 329
		git_error_set(GIT_ERROR_OS, "failed to close memory window file; couldn't find LRU");
		return -1;
	}

330
	*out = lru_file;
331 332 333
	return 0;
}

334
/* This gets called under lock from git_mwindow_open */
335
static git_mwindow *new_window_locked(
336
	git_file fd,
337 338
	off64_t size,
	off64_t offset)
339
{
lhchavez committed
340
	git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
Vicent Marti committed
341
	size_t walign = git_mwindow__window_size / 2;
342
	off64_t len;
343 344
	git_mwindow *w;

345
	w = git__calloc(1, sizeof(*w));
Russell Belfer committed
346

347
	if (w == NULL)
348
		return NULL;
349 350 351 352

	w->offset = (offset / walign) * walign;

	len = size - w->offset;
353 354
	if (len > (off64_t)git_mwindow__window_size)
		len = (off64_t)git_mwindow__window_size;
355

356
	ctl->mapped += (size_t)len;
357

Vicent Marti committed
358
	while (git_mwindow__mapped_limit < ctl->mapped &&
359
			git_mwindow_close_lru_window_locked() == 0) /* nop */;
360

361
	/*
Vicent Marti committed
362
	 * We treat `mapped_limit` as a soft limit. If we can't find a
363 364 365
	 * window to close and are above the limit, we still mmap the new
	 * window.
	 */
366

367
	if (git_futils_mmap_ro(&w->window_map, fd, w->offset, (size_t)len) < 0) {
368 369 370 371 372
		/*
		 * The first error might be down to memory fragmentation even if
		 * we're below our soft limits, so free up what we can and try again.
		 */

373
		while (git_mwindow_close_lru_window_locked() == 0)
374 375 376 377 378 379
			/* nop */;

		if (git_futils_mmap_ro(&w->window_map, fd, w->offset, (size_t)len) < 0) {
			git__free(w);
			return NULL;
		}
380
	}
381

382 383
	ctl->mmap_calls++;
	ctl->open_windows++;
384

385 386
	if (ctl->mapped > ctl->peak_mapped)
		ctl->peak_mapped = ctl->mapped;
387

388 389
	if (ctl->open_windows > ctl->peak_open_windows)
		ctl->peak_open_windows = ctl->open_windows;
390 391 392 393 394 395 396 397

	return w;
}

/*
 * Open a new window, closing the least recenty used until we have
 * enough space. Don't forget to add it to your list
 */
398 399 400
unsigned char *git_mwindow_open(
	git_mwindow_file *mwf,
	git_mwindow **cursor,
401
	off64_t offset,
402
	size_t extra,
403
	unsigned int *left)
404
{
lhchavez committed
405
	git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
406 407
	git_mwindow *w = *cursor;

408
	if (git_mutex_lock(&git__mwindow_mutex)) {
409
		git_error_set(GIT_ERROR_THREAD, "unable to lock mwindow mutex");
410 411 412
		return NULL;
	}

413
	if (!w || !(git_mwindow_contains(w, offset, extra))) {
414 415 416 417 418
		if (w) {
			w->inuse_cnt--;
		}

		for (w = mwf->windows; w; w = w->next) {
419
			if (git_mwindow_contains(w, offset, extra))
420 421 422 423 424 425 426 427
				break;
		}

		/*
		 * If there isn't a suitable window, we need to create a new
		 * one.
		 */
		if (!w) {
428
			w = new_window_locked(mwf->fd, mwf->size, offset);
429 430
			if (w == NULL) {
				git_mutex_unlock(&git__mwindow_mutex);
431
				return NULL;
432
			}
433 434 435 436 437 438 439
			w->next = mwf->windows;
			mwf->windows = w;
		}
	}

	/* If we changed w, store it in the cursor */
	if (w != *cursor) {
440
		w->last_used = ctl->used_ctr++;
441 442 443 444 445 446 447
		w->inuse_cnt++;
		*cursor = w;
	}

	offset -= w->offset;

	if (left)
448
		*left = (unsigned int)(w->window_map.len - offset);
449

450
	git_mutex_unlock(&git__mwindow_mutex);
451 452 453 454 455
	return (unsigned char *) w->window_map.data + offset;
}

int git_mwindow_file_register(git_mwindow_file *mwf)
{
456
	git_vector closed_files = GIT_VECTOR_INIT;
lhchavez committed
457
	git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
458 459 460
	int error;
	size_t i;
	git_mwindow_file *closed_file = NULL;
461

462
	if (git_mutex_lock(&git__mwindow_mutex)) {
463
		git_error_set(GIT_ERROR_THREAD, "unable to lock mwindow mutex");
464 465 466
		return -1;
	}

467
	if (ctl->windowfiles.length == 0 &&
468
	    (error = git_vector_init(&ctl->windowfiles, 8, NULL)) < 0) {
469
		git_mutex_unlock(&git__mwindow_mutex);
470
		goto cleanup;
471 472
	}

lhchavez committed
473
	if (git_mwindow__file_limit) {
474
		git_mwindow_file *lru_file;
lhchavez committed
475
		while (git_mwindow__file_limit <= ctl->windowfiles.length &&
476 477 478
				git_mwindow_find_lru_file_locked(&lru_file) == 0) {
			if ((error = git_vector_insert(&closed_files, lru_file)) < 0) {
				/*
Dimitris Apostolou committed
479
				 * Exceeding the file limit seems preferable to being open to
480 481 482 483 484 485
				 * data races that can end up corrupting the heap.
				 */
				break;
			}
			git_mwindow_free_all_locked(lru_file);
		}
lhchavez committed
486
	}
487

488
	error = git_vector_insert(&ctl->windowfiles, mwf);
489
	git_mutex_unlock(&git__mwindow_mutex);
490 491
	if (error < 0)
		goto cleanup;
492

493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509
	/*
	 * Once we have released the global windowfiles lock, we can close each
	 * individual file. Before doing so, acquire that file's lock to avoid
	 * closing a file that is currently being used.
	 */
	git_vector_foreach(&closed_files, i, closed_file) {
		error = git_mutex_lock(&closed_file->lock);
		if (error < 0)
			continue;
		p_close(closed_file->fd);
		closed_file->fd = -1;
		git_mutex_unlock(&closed_file->lock);
	}

cleanup:
	git_vector_free(&closed_files);
	return error;
510 511
}

512
void git_mwindow_file_deregister(git_mwindow_file *mwf)
513
{
lhchavez committed
514
	git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
515
	git_mwindow_file *cur;
516
	size_t i;
517

518 519
	if (git_mutex_lock(&git__mwindow_mutex))
		return;
520

521 522 523
	git_vector_foreach(&ctl->windowfiles, i, cur) {
		if (cur == mwf) {
			git_vector_remove(&ctl->windowfiles, i);
524
			git_mutex_unlock(&git__mwindow_mutex);
525
			return;
526 527
		}
	}
528
	git_mutex_unlock(&git__mwindow_mutex);
529 530
}

531 532 533 534
void git_mwindow_close(git_mwindow **window)
{
	git_mwindow *w = *window;
	if (w) {
535
		if (git_mutex_lock(&git__mwindow_mutex)) {
536
			git_error_set(GIT_ERROR_THREAD, "unable to lock mwindow mutex");
537 538 539
			return;
		}

540
		w->inuse_cnt--;
541
		git_mutex_unlock(&git__mwindow_mutex);
542 543 544
		*window = NULL;
	}
}