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
}

int git_mwindow_get_pack(struct git_pack_file **out, const char *path)
{
	struct git_pack_file *pack;
67 68
	char *packname;
	int error;
69 70 71 72

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

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 80
	git__free(packname);

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

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

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 100
		git_packfile_free(pack, false);
		return error;
101
	}
102

103 104 105 106
	*out = pack;
	return 0;
}

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 113
	if ((error = git_mutex_lock(&git__mwindow_mutex)) < 0)
		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
{
lhchavez committed
138
	git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
139 140
	size_t i;

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

151 152 153
	if (ctl->windowfiles.length == 0) {
		git_vector_free(&ctl->windowfiles);
		ctl->windowfiles.contents = NULL;
154 155 156 157
	}

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

160 161
		ctl->mapped -= w->window_map.len;
		ctl->open_windows--;
162 163 164 165

		git_futils_mmap_free(&w->window_map);

		mwf->windows = w->next;
166
		git__free(w);
167
	}
168 169

	return 0;
170 171
}

172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187
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;
}

188
/*
189 190 191 192
 * 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.
193
 */
194
int git_mwindow_contains(git_mwindow *win, off64_t offset, off64_t extra)
195
{
196
	off64_t win_off = win->offset;
197
	return win_off <= offset
198
		&& (offset + extra) <= (off64_t)(win_off + win->window_map.len);
199 200
}

lhchavez committed
201 202 203
#define GIT_MWINDOW__LRU -1
#define GIT_MWINDOW__MRU 1

204
/*
lhchavez committed
205 206
 * 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
207 208
 * file to only have unused windows. If '*out_window' is non-null, it is used as
 * a starting point for the comparison.
lhchavez committed
209 210
 *
 * Returns whether such a window was found in the file.
211
 */
lhchavez committed
212 213 214 215 216 217
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)
218
{
lhchavez committed
219 220
	git_mwindow *w, *w_last;
	git_mwindow *lru_window = NULL, *lru_last = NULL;
221
	bool found = false;
lhchavez committed
222

223 224
	GIT_ASSERT_ARG(mwf);
	GIT_ASSERT_ARG(out_window);
lhchavez committed
225

226 227 228 229
	lru_window = *out_window;
	if (out_last)
		lru_last = *out_last;

lhchavez committed
230 231 232 233 234 235 236 237 238 239 240 241 242
	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.
		 */
243
		if (!lru_window || (comparison_sign * w->last_used) > lru_window->last_used) {
lhchavez committed
244 245
			lru_window = w;
			lru_last = w_last;
246
			found = true;
247 248
		}
	}
lhchavez committed
249

250
	if (!found)
lhchavez committed
251 252 253 254 255 256
		return false;

	*out_window = lru_window;
	if (out_last)
		*out_last = lru_last;
	return true;
257 258 259
}

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

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

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

lhchavez committed
282 283
	ctl->mapped -= lru_window->window_map.len;
	git_futils_mmap_free(&lru_window->window_map);
284

lhchavez committed
285 286
	if (lru_last)
		lru_last->next = lru_window->next;
287
	else
lhchavez committed
288
		*list = lru_window->next;
289

lhchavez committed
290
	git__free(lru_window);
291
	ctl->open_windows--;
292

293
	return 0;
294 295
}

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

lhchavez committed
310 311 312 313 314 315
	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;
		}
316 317
		if (!lru_window || lru_window->last_used > mru_window->last_used) {
			lru_window = mru_window;
lhchavez committed
318
			lru_file = current_file;
319
		}
320 321
	}

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

327
	*out = lru_file;
328 329 330
	return 0;
}

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

342
	w = git__calloc(1, sizeof(*w));
Russell Belfer committed
343

344
	if (w == NULL)
345
		return NULL;
346 347 348 349

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

	len = size - w->offset;
350 351
	if (len > (off64_t)git_mwindow__window_size)
		len = (off64_t)git_mwindow__window_size;
352

353
	ctl->mapped += (size_t)len;
354

Vicent Marti committed
355
	while (git_mwindow__mapped_limit < ctl->mapped &&
356
			git_mwindow_close_lru_window_locked() == 0) /* nop */;
357

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

364
	if (git_futils_mmap_ro(&w->window_map, fd, w->offset, (size_t)len) < 0) {
365 366 367 368 369
		/*
		 * 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.
		 */

370
		while (git_mwindow_close_lru_window_locked() == 0)
371 372 373 374 375 376
			/* nop */;

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

379 380
	ctl->mmap_calls++;
	ctl->open_windows++;
381

382 383
	if (ctl->mapped > ctl->peak_mapped)
		ctl->peak_mapped = ctl->mapped;
384

385 386
	if (ctl->open_windows > ctl->peak_open_windows)
		ctl->peak_open_windows = ctl->open_windows;
387 388 389 390 391 392 393 394

	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
 */
395 396 397
unsigned char *git_mwindow_open(
	git_mwindow_file *mwf,
	git_mwindow **cursor,
398
	off64_t offset,
399
	size_t extra,
400
	unsigned int *left)
401
{
lhchavez committed
402
	git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
403 404
	git_mwindow *w = *cursor;

405
	if (git_mutex_lock(&git__mwindow_mutex)) {
406
		git_error_set(GIT_ERROR_THREAD, "unable to lock mwindow mutex");
407 408 409
		return NULL;
	}

410
	if (!w || !(git_mwindow_contains(w, offset, extra))) {
411 412 413 414 415
		if (w) {
			w->inuse_cnt--;
		}

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

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

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

	offset -= w->offset;

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

447
	git_mutex_unlock(&git__mwindow_mutex);
448 449 450 451 452
	return (unsigned char *) w->window_map.data + offset;
}

int git_mwindow_file_register(git_mwindow_file *mwf)
{
453
	git_vector closed_files = GIT_VECTOR_INIT;
lhchavez committed
454
	git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
455 456 457
	int error;
	size_t i;
	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 462 463
		return -1;
	}

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
	}

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

485
	error = git_vector_insert(&ctl->windowfiles, mwf);
486
	git_mutex_unlock(&git__mwindow_mutex);
487 488
	if (error < 0)
		goto cleanup;
489

490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506
	/*
	 * 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;
507 508
}

509
void git_mwindow_file_deregister(git_mwindow_file *mwf)
510
{
lhchavez committed
511
	git_mwindow_ctl *ctl = &git_mwindow__mem_ctl;
512
	git_mwindow_file *cur;
513
	size_t i;
514

515 516
	if (git_mutex_lock(&git__mwindow_mutex))
		return;
517

518 519 520
	git_vector_foreach(&ctl->windowfiles, i, cur) {
		if (cur == mwf) {
			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 529 530 531
void git_mwindow_close(git_mwindow **window)
{
	git_mwindow *w = *window;
	if (w) {
532
		if (git_mutex_lock(&git__mwindow_mutex)) {
533
			git_error_set(GIT_ERROR_THREAD, "unable to lock mwindow mutex");
534 535 536
			return;
		}

537
		w->inuse_cnt--;
538
		git_mutex_unlock(&git__mwindow_mutex);
539 540 541
		*window = NULL;
	}
}