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 "fileops.h"
12 #include "map.h"
13 #include "global.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 ? 8192ULL : 256UL))
24 
25 size_t git_mwindow__window_size = DEFAULT_WINDOW_SIZE;
26 size_t git_mwindow__mapped_limit = DEFAULT_MAPPED_LIMIT;
27 
28 /* Whenever you want to read or modify this, grab git__mwindow_mutex */
29 static git_mwindow_ctl mem_ctl;
30 
31 /* Global list of mwindow files, to open packs once across repos */
32 git_strmap *git__pack_cache = NULL;
33 
git_mwindow_files_free(void)34 static void git_mwindow_files_free(void)
35 {
36 	git_strmap *tmp = git__pack_cache;
37 
38 	git__pack_cache = NULL;
39 	git_strmap_free(tmp);
40 }
41 
git_mwindow_global_init(void)42 int git_mwindow_global_init(void)
43 {
44 	assert(!git__pack_cache);
45 
46 	git__on_shutdown(git_mwindow_files_free);
47 	return git_strmap_alloc(&git__pack_cache);
48 }
49 
git_mwindow_get_pack(struct git_pack_file ** out,const char * path)50 int git_mwindow_get_pack(struct git_pack_file **out, const char *path)
51 {
52 	int error;
53 	char *packname;
54 	size_t pos;
55 	struct git_pack_file *pack;
56 
57 	if ((error = git_packfile__name(&packname, path)) < 0)
58 		return error;
59 
60 	if (git_mutex_lock(&git__mwindow_mutex) < 0) {
61 		git_error_set(GIT_ERROR_OS, "failed to lock mwindow mutex");
62 		return -1;
63 	}
64 
65 	pos = git_strmap_lookup_index(git__pack_cache, packname);
66 	git__free(packname);
67 
68 	if (git_strmap_valid_index(git__pack_cache, pos)) {
69 		pack = git_strmap_value_at(git__pack_cache, pos);
70 		git_atomic_inc(&pack->refcount);
71 
72 		git_mutex_unlock(&git__mwindow_mutex);
73 		*out = pack;
74 		return 0;
75 	}
76 
77 	/* If we didn't find it, we need to create it */
78 	if ((error = git_packfile_alloc(&pack, path)) < 0) {
79 		git_mutex_unlock(&git__mwindow_mutex);
80 		return error;
81 	}
82 
83 	git_atomic_inc(&pack->refcount);
84 
85 	git_strmap_insert(git__pack_cache, pack->pack_name, pack, &error);
86 	git_mutex_unlock(&git__mwindow_mutex);
87 
88 	if (error < 0) {
89 		git_packfile_free(pack);
90 		return -1;
91 	}
92 
93 	*out = pack;
94 	return 0;
95 }
96 
git_mwindow_put_pack(struct git_pack_file * pack)97 void git_mwindow_put_pack(struct git_pack_file *pack)
98 {
99 	int count;
100 	size_t pos;
101 
102 	if (git_mutex_lock(&git__mwindow_mutex) < 0)
103 		return;
104 
105 	/* put before get would be a corrupted state */
106 	assert(git__pack_cache);
107 
108 	pos = git_strmap_lookup_index(git__pack_cache, pack->pack_name);
109 	/* if we cannot find it, the state is corrupted */
110 	assert(git_strmap_valid_index(git__pack_cache, pos));
111 
112 	count = git_atomic_dec(&pack->refcount);
113 	if (count == 0) {
114 		git_strmap_delete_at(git__pack_cache, pos);
115 		git_packfile_free(pack);
116 	}
117 
118 	git_mutex_unlock(&git__mwindow_mutex);
119 	return;
120 }
121 
git_mwindow_free_all(git_mwindow_file * mwf)122 void git_mwindow_free_all(git_mwindow_file *mwf)
123 {
124 	if (git_mutex_lock(&git__mwindow_mutex)) {
125 		git_error_set(GIT_ERROR_THREAD, "unable to lock mwindow mutex");
126 		return;
127 	}
128 
129 	git_mwindow_free_all_locked(mwf);
130 
131 	git_mutex_unlock(&git__mwindow_mutex);
132 }
133 
134 /*
135  * Free all the windows in a sequence, typically because we're done
136  * with the file
137  */
git_mwindow_free_all_locked(git_mwindow_file * mwf)138 void git_mwindow_free_all_locked(git_mwindow_file *mwf)
139 {
140 	git_mwindow_ctl *ctl = &mem_ctl;
141 	size_t i;
142 
143 	/*
144 	 * Remove these windows from the global list
145 	 */
146 	for (i = 0; i < ctl->windowfiles.length; ++i){
147 		if (git_vector_get(&ctl->windowfiles, i) == mwf) {
148 			git_vector_remove(&ctl->windowfiles, i);
149 			break;
150 		}
151 	}
152 
153 	if (ctl->windowfiles.length == 0) {
154 		git_vector_free(&ctl->windowfiles);
155 		ctl->windowfiles.contents = NULL;
156 	}
157 
158 	while (mwf->windows) {
159 		git_mwindow *w = mwf->windows;
160 		assert(w->inuse_cnt == 0);
161 
162 		ctl->mapped -= w->window_map.len;
163 		ctl->open_windows--;
164 
165 		git_futils_mmap_free(&w->window_map);
166 
167 		mwf->windows = w->next;
168 		git__free(w);
169 	}
170 }
171 
172 /*
173  * Check if a window 'win' contains the address 'offset'
174  */
git_mwindow_contains(git_mwindow * win,git_off_t offset)175 int git_mwindow_contains(git_mwindow *win, git_off_t offset)
176 {
177 	git_off_t win_off = win->offset;
178 	return win_off <= offset
179 		&& offset <= (git_off_t)(win_off + win->window_map.len);
180 }
181 
182 /*
183  * Find the least-recently-used window in a file
184  */
git_mwindow_scan_lru(git_mwindow_file * mwf,git_mwindow ** lru_w,git_mwindow ** lru_l)185 static void git_mwindow_scan_lru(
186 	git_mwindow_file *mwf,
187 	git_mwindow **lru_w,
188 	git_mwindow **lru_l)
189 {
190 	git_mwindow *w, *w_l;
191 
192 	for (w_l = NULL, w = mwf->windows; w; w = w->next) {
193 		if (!w->inuse_cnt) {
194 			/*
195 			 * If the current one is more recent than the last one,
196 			 * store it in the output parameter. If lru_w is NULL,
197 			 * it's the first loop, so store it as well.
198 			 */
199 			if (!*lru_w || w->last_used < (*lru_w)->last_used) {
200 				*lru_w = w;
201 				*lru_l = w_l;
202 			}
203 		}
204 		w_l = w;
205 	}
206 }
207 
208 /*
209  * Close the least recently used window. You should check to see if
210  * the file descriptors need closing from time to time. Called under
211  * lock from new_window.
212  */
git_mwindow_close_lru(git_mwindow_file * mwf)213 static int git_mwindow_close_lru(git_mwindow_file *mwf)
214 {
215 	git_mwindow_ctl *ctl = &mem_ctl;
216 	size_t i;
217 	git_mwindow *lru_w = NULL, *lru_l = NULL, **list = &mwf->windows;
218 
219 	/* FIXME: Does this give us any advantage? */
220 	if(mwf->windows)
221 		git_mwindow_scan_lru(mwf, &lru_w, &lru_l);
222 
223 	for (i = 0; i < ctl->windowfiles.length; ++i) {
224 		git_mwindow *last = lru_w;
225 		git_mwindow_file *cur = git_vector_get(&ctl->windowfiles, i);
226 		git_mwindow_scan_lru(cur, &lru_w, &lru_l);
227 		if (lru_w != last)
228 			list = &cur->windows;
229 	}
230 
231 	if (!lru_w) {
232 		git_error_set(GIT_ERROR_OS, "failed to close memory window; couldn't find LRU");
233 		return -1;
234 	}
235 
236 	ctl->mapped -= lru_w->window_map.len;
237 	git_futils_mmap_free(&lru_w->window_map);
238 
239 	if (lru_l)
240 		lru_l->next = lru_w->next;
241 	else
242 		*list = lru_w->next;
243 
244 	git__free(lru_w);
245 	ctl->open_windows--;
246 
247 	return 0;
248 }
249 
250 /* This gets called under lock from git_mwindow_open */
new_window(git_mwindow_file * mwf,git_file fd,git_off_t size,git_off_t offset)251 static git_mwindow *new_window(
252 	git_mwindow_file *mwf,
253 	git_file fd,
254 	git_off_t size,
255 	git_off_t offset)
256 {
257 	git_mwindow_ctl *ctl = &mem_ctl;
258 	size_t walign = git_mwindow__window_size / 2;
259 	git_off_t len;
260 	git_mwindow *w;
261 
262 	w = git__malloc(sizeof(*w));
263 
264 	if (w == NULL)
265 		return NULL;
266 
267 	memset(w, 0x0, sizeof(*w));
268 	w->offset = (offset / walign) * walign;
269 
270 	len = size - w->offset;
271 	if (len > (git_off_t)git_mwindow__window_size)
272 		len = (git_off_t)git_mwindow__window_size;
273 
274 	ctl->mapped += (size_t)len;
275 
276 	while (git_mwindow__mapped_limit < ctl->mapped &&
277 			git_mwindow_close_lru(mwf) == 0) /* nop */;
278 
279 	/*
280 	 * We treat `mapped_limit` as a soft limit. If we can't find a
281 	 * window to close and are above the limit, we still mmap the new
282 	 * window.
283 	 */
284 
285 	if (git_futils_mmap_ro(&w->window_map, fd, w->offset, (size_t)len) < 0) {
286 		/*
287 		 * The first error might be down to memory fragmentation even if
288 		 * we're below our soft limits, so free up what we can and try again.
289 		 */
290 
291 		while (git_mwindow_close_lru(mwf) == 0)
292 			/* nop */;
293 
294 		if (git_futils_mmap_ro(&w->window_map, fd, w->offset, (size_t)len) < 0) {
295 			git__free(w);
296 			return NULL;
297 		}
298 	}
299 
300 	ctl->mmap_calls++;
301 	ctl->open_windows++;
302 
303 	if (ctl->mapped > ctl->peak_mapped)
304 		ctl->peak_mapped = ctl->mapped;
305 
306 	if (ctl->open_windows > ctl->peak_open_windows)
307 		ctl->peak_open_windows = ctl->open_windows;
308 
309 	return w;
310 }
311 
312 /*
313  * Open a new window, closing the least recenty used until we have
314  * enough space. Don't forget to add it to your list
315  */
git_mwindow_open(git_mwindow_file * mwf,git_mwindow ** cursor,git_off_t offset,size_t extra,unsigned int * left)316 unsigned char *git_mwindow_open(
317 	git_mwindow_file *mwf,
318 	git_mwindow **cursor,
319 	git_off_t offset,
320 	size_t extra,
321 	unsigned int *left)
322 {
323 	git_mwindow_ctl *ctl = &mem_ctl;
324 	git_mwindow *w = *cursor;
325 
326 	if (git_mutex_lock(&git__mwindow_mutex)) {
327 		git_error_set(GIT_ERROR_THREAD, "unable to lock mwindow mutex");
328 		return NULL;
329 	}
330 
331 	if (!w || !(git_mwindow_contains(w, offset) && git_mwindow_contains(w, offset + extra))) {
332 		if (w) {
333 			w->inuse_cnt--;
334 		}
335 
336 		for (w = mwf->windows; w; w = w->next) {
337 			if (git_mwindow_contains(w, offset) &&
338 				git_mwindow_contains(w, offset + extra))
339 				break;
340 		}
341 
342 		/*
343 		 * If there isn't a suitable window, we need to create a new
344 		 * one.
345 		 */
346 		if (!w) {
347 			w = new_window(mwf, mwf->fd, mwf->size, offset);
348 			if (w == NULL) {
349 				git_mutex_unlock(&git__mwindow_mutex);
350 				return NULL;
351 			}
352 			w->next = mwf->windows;
353 			mwf->windows = w;
354 		}
355 	}
356 
357 	/* If we changed w, store it in the cursor */
358 	if (w != *cursor) {
359 		w->last_used = ctl->used_ctr++;
360 		w->inuse_cnt++;
361 		*cursor = w;
362 	}
363 
364 	offset -= w->offset;
365 
366 	if (left)
367 		*left = (unsigned int)(w->window_map.len - offset);
368 
369 	git_mutex_unlock(&git__mwindow_mutex);
370 	return (unsigned char *) w->window_map.data + offset;
371 }
372 
git_mwindow_file_register(git_mwindow_file * mwf)373 int git_mwindow_file_register(git_mwindow_file *mwf)
374 {
375 	git_mwindow_ctl *ctl = &mem_ctl;
376 	int ret;
377 
378 	if (git_mutex_lock(&git__mwindow_mutex)) {
379 		git_error_set(GIT_ERROR_THREAD, "unable to lock mwindow mutex");
380 		return -1;
381 	}
382 
383 	if (ctl->windowfiles.length == 0 &&
384 	    git_vector_init(&ctl->windowfiles, 8, NULL) < 0) {
385 		git_mutex_unlock(&git__mwindow_mutex);
386 		return -1;
387 	}
388 
389 	ret = git_vector_insert(&ctl->windowfiles, mwf);
390 	git_mutex_unlock(&git__mwindow_mutex);
391 
392 	return ret;
393 }
394 
git_mwindow_file_deregister(git_mwindow_file * mwf)395 void git_mwindow_file_deregister(git_mwindow_file *mwf)
396 {
397 	git_mwindow_ctl *ctl = &mem_ctl;
398 	git_mwindow_file *cur;
399 	size_t i;
400 
401 	if (git_mutex_lock(&git__mwindow_mutex))
402 		return;
403 
404 	git_vector_foreach(&ctl->windowfiles, i, cur) {
405 		if (cur == mwf) {
406 			git_vector_remove(&ctl->windowfiles, i);
407 			git_mutex_unlock(&git__mwindow_mutex);
408 			return;
409 		}
410 	}
411 	git_mutex_unlock(&git__mwindow_mutex);
412 }
413 
git_mwindow_close(git_mwindow ** window)414 void git_mwindow_close(git_mwindow **window)
415 {
416 	git_mwindow *w = *window;
417 	if (w) {
418 		if (git_mutex_lock(&git__mwindow_mutex)) {
419 			git_error_set(GIT_ERROR_THREAD, "unable to lock mwindow mutex");
420 			return;
421 		}
422 
423 		w->inuse_cnt--;
424 		git_mutex_unlock(&git__mwindow_mutex);
425 		*window = NULL;
426 	}
427 }
428