1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
4 This file is part of systemd.
6 Copyright 2012 Lennart Poettering
8 systemd is free software; you can redistribute it and/or modify it
9 under the terms of the GNU Lesser General Public License as published by
10 the Free Software Foundation; either version 2.1 of the License, or
11 (at your option) any later version.
13 systemd is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 Lesser General Public License for more details.
18 You should have received a copy of the GNU Lesser General Public License
19 along with systemd; If not, see <http://www.gnu.org/licenses/>.
30 #include "mmap-cache.h"
32 #define WINDOW_SIZE (8ULL*1024ULL*1024ULL)
34 #define DEFAULT_WINDOWS_MAX 64
35 #define DEFAULT_FDS_MAX 32
36 #define DEFAULT_CONTEXTS_MAX 32
38 typedef struct Window {
52 typedef struct FileDescriptor {
60 unsigned contexts_max;
67 unsigned lru_first, lru_last;
71 FileDescriptor *by_fd;
74 static int mmap_cache_peek_fd_index(MMapCache *m, int fd, unsigned *fd_index);
76 static void mmap_cache_window_unmap(MMapCache *m, unsigned w) {
80 assert(w < m->n_windows);
86 munmap(v->ptr, v->size);
90 static void mmap_cache_window_add_lru(MMapCache *m, unsigned w) {
94 assert(w < m->n_windows);
97 assert(v->n_ref == 0);
99 if (m->lru_last != (unsigned) -1) {
100 assert(m->windows[m->lru_last].lru_next == (unsigned) -1);
101 m->windows[m->lru_last].lru_next = w;
104 v->lru_prev = m->lru_last;
105 v->lru_next = (unsigned) -1;
108 if (m->lru_first == (unsigned) -1)
112 static void mmap_cache_window_remove_lru(MMapCache *m, unsigned w) {
116 assert(w < m->n_windows);
120 if (v->lru_prev == (unsigned) -1) {
121 assert(m->lru_first == w);
122 m->lru_first = v->lru_next;
124 assert(m->windows[v->lru_prev].lru_next == w);
125 m->windows[v->lru_prev].lru_next = v->lru_next;
128 if (v->lru_next == (unsigned) -1) {
129 assert(m->lru_last == w);
130 m->lru_last = v->lru_prev;
132 assert(m->windows[v->lru_next].lru_prev == w);
133 m->windows[v->lru_next].lru_prev = v->lru_prev;
137 static void mmap_cache_fd_add(MMapCache *m, unsigned fd_index, unsigned w) {
141 assert(fd_index < m->n_fds);
144 assert(m->by_fd[fd_index].fd == v->fd);
146 if (m->by_fd[fd_index].windows != (unsigned) -1) {
147 assert(m->windows[m->by_fd[fd_index].windows].by_fd_prev == (unsigned) -1);
148 m->windows[m->by_fd[fd_index].windows].by_fd_prev = w;
151 v->by_fd_next = m->by_fd[fd_index].windows;
152 v->by_fd_prev = (unsigned) -1;
154 m->by_fd[fd_index].windows = w;
157 static void mmap_cache_fd_remove(MMapCache *m, unsigned fd_index, unsigned w) {
161 assert(fd_index < m->n_fds);
164 assert(m->by_fd[fd_index].fd == v->fd);
165 assert(v->by_fd_next == (unsigned) -1 || m->windows[v->by_fd_next].fd == v->fd);
166 assert(v->by_fd_prev == (unsigned) -1 || m->windows[v->by_fd_prev].fd == v->fd);
168 if (v->by_fd_prev == (unsigned) -1) {
169 assert(m->by_fd[fd_index].windows == w);
170 m->by_fd[fd_index].windows = v->by_fd_next;
172 assert(m->windows[v->by_fd_prev].by_fd_next == w);
173 m->windows[v->by_fd_prev].by_fd_next = v->by_fd_next;
176 if (v->by_fd_next != (unsigned) -1) {
177 assert(m->windows[v->by_fd_next].by_fd_prev == w);
178 m->windows[v->by_fd_next].by_fd_prev = v->by_fd_prev;
182 static void mmap_cache_context_unset(MMapCache *m, unsigned c) {
187 assert(c < m->contexts_max);
189 if (m->by_context[c] == (unsigned) -1)
192 w = m->by_context[c];
193 m->by_context[c] = (unsigned) -1;
196 assert(v->n_ref > 0);
200 mmap_cache_window_add_lru(m, w);
203 static void mmap_cache_context_set(MMapCache *m, unsigned c, unsigned w) {
207 assert(c < m->contexts_max);
208 assert(w < m->n_windows);
210 if (m->by_context[c] == w)
213 mmap_cache_context_unset(m, c);
215 m->by_context[c] = w;
221 mmap_cache_window_remove_lru(m, w);
224 static void mmap_cache_free(MMapCache *m) {
231 for (w = 0; w < m->n_windows; w++)
232 mmap_cache_window_unmap(m, w);
242 MMapCache* mmap_cache_new(void) {
245 m = new0(MMapCache, 1);
249 m->contexts_max = DEFAULT_CONTEXTS_MAX;
250 m->fds_max = DEFAULT_FDS_MAX;
251 m->windows_max = DEFAULT_WINDOWS_MAX;
253 m->lru_first = (unsigned) -1;
254 m->lru_last = (unsigned) -1;
256 m->windows = new(Window, m->windows_max);
262 m->by_context = new(unsigned, m->contexts_max);
263 if (!m->by_context) {
267 memset(m->by_context, -1, m->contexts_max * sizeof(unsigned));
269 m->by_fd = new(FileDescriptor, m->fds_max);
278 MMapCache* mmap_cache_ref(MMapCache *m) {
280 assert(m->n_ref > 0);
286 MMapCache* mmap_cache_unref(MMapCache *m) {
288 assert(m->n_ref > 0);
298 static int mmap_cache_allocate_window(MMapCache *m, unsigned *w) {
305 if (m->n_windows < m->windows_max) {
306 *w = m->n_windows ++;
310 if (m->lru_first == (unsigned) -1)
315 assert(v->n_ref == 0);
317 mmap_cache_window_unmap(m, *w);
320 assert_se(mmap_cache_peek_fd_index(m, v->fd, &fd_index) > 0);
321 mmap_cache_fd_remove(m, fd_index, *w);
324 mmap_cache_window_remove_lru(m, *w);
329 static int mmap_cache_make_room(MMapCache *m) {
335 while (w != (unsigned) -1) {
339 assert(v->n_ref == 0);
342 mmap_cache_window_unmap(m, w);
352 static int mmap_cache_put(
367 uint64_t woffset, wsize;
372 assert(context < m->contexts_max);
376 woffset = offset & ~((uint64_t) page_size() - 1ULL);
377 wsize = size + (offset - woffset);
378 wsize = PAGE_ALIGN(wsize);
380 if (wsize < WINDOW_SIZE) {
383 delta = PAGE_ALIGN((WINDOW_SIZE - wsize) / 2);
394 /* Memory maps that are larger then the files
395 underneath have undefined behaviour. Hence, clamp
396 things to the file size if we know it */
398 if (woffset >= (uint64_t) st->st_size)
399 return -EADDRNOTAVAIL;
401 if (woffset + wsize > (uint64_t) st->st_size)
402 wsize = PAGE_ALIGN(st->st_size - woffset);
406 d = mmap(NULL, wsize, prot, MAP_SHARED, fd, woffset);
412 r = mmap_cache_make_room(m);
419 r = mmap_cache_allocate_window(m, &w);
435 mmap_cache_window_add_lru(m, w);
438 mmap_cache_fd_add(m, fd_index, w);
439 mmap_cache_context_set(m, context, w);
441 *ret = (uint8_t*) d + (offset - woffset);
445 static int fd_cmp(const void *_a, const void *_b) {
446 const FileDescriptor *a = _a, *b = _b;
456 static int mmap_cache_peek_fd_index(MMapCache *m, int fd, unsigned *fd_index) {
464 for (r = 0; r < m->n_fds; r++)
465 assert(m->by_fd[r].windows == (unsigned) -1 ||
466 m->windows[m->by_fd[r].windows].fd == m->by_fd[r].fd);
468 j = bsearch(&fd, m->by_fd, m->n_fds, sizeof(FileDescriptor), fd_cmp);
472 *fd_index = (unsigned) (j - m->by_fd);
476 static int mmap_cache_get_fd_index(MMapCache *m, int fd, unsigned *fd_index) {
484 r = mmap_cache_peek_fd_index(m, fd, fd_index);
488 if (m->n_fds >= m->fds_max) {
493 n = realloc(m->by_fd, sizeof(FileDescriptor) * k);
501 j = m->by_fd + m->n_fds ++;
503 j->windows = (unsigned) -1;
505 qsort(m->by_fd, m->n_fds, sizeof(FileDescriptor), fd_cmp);
507 return mmap_cache_peek_fd_index(m, fd, fd_index);
510 static bool mmap_cache_test_window(
518 assert(w < m->n_windows);
523 return offset >= v->offset &&
524 offset + size <= v->offset + v->size;
527 static int mmap_cache_current(
540 assert(context < m->contexts_max);
544 if (m->by_context[context] == (unsigned) -1)
547 w = m->by_context[context];
553 if (!mmap_cache_test_window(m, w, offset, size))
556 *ret = (uint8_t*) v->ptr + (offset - v->offset);
560 static int mmap_cache_find(
574 assert(fd_index < m->n_fds);
575 assert(context < m->contexts_max);
579 w = m->by_fd[fd_index].windows;
580 while (w != (unsigned) -1) {
584 if (mmap_cache_test_window(m, w, offset, size))
590 if (w == (unsigned) -1)
593 mmap_cache_context_set(m, context, w);
595 *ret = (uint8_t*) v->ptr + (offset - v->offset);
618 if (context >= m->contexts_max) {
622 /* Increase the number of contexts if necessary, and
623 * make sure we have twice the number of windows */
626 n = realloc(m->by_context, sizeof(unsigned) * k);
629 memset(n + m->contexts_max, -1, (k - m->contexts_max) * sizeof(unsigned));
633 k = MAX(m->windows_max, m->contexts_max*2);
634 w = realloc(m->windows, sizeof(Window) * k);
642 /* Maybe the current pointer for this context is already the
644 r = mmap_cache_current(m, fd, context, offset, size, ret);
648 /* Hmm, drop the reference to the current one, since it wasn't
650 mmap_cache_context_unset(m, context);
652 /* OK, let's find the chain for this FD */
653 r = mmap_cache_get_fd_index(m, fd, &fd_index);
657 /* And let's look through the available mmaps */
658 r = mmap_cache_find(m, fd, fd_index, context, offset, size, ret);
662 /* Not found? Then, let's add it */
663 return mmap_cache_put(m, fd, fd_index, prot, context, keep_always, offset, size, st, ret);
666 void mmap_cache_close_fd(MMapCache *m, int fd) {
667 unsigned fd_index, c, w;
673 r = mmap_cache_peek_fd_index(m, fd, &fd_index);
677 for (c = 0; c < m->contexts_max; c++) {
678 w = m->by_context[c];
679 if (w == (unsigned) -1)
682 if (m->windows[w].fd == fd)
683 mmap_cache_context_unset(m, c);
686 w = m->by_fd[fd_index].windows;
687 while (w != (unsigned) -1) {
693 mmap_cache_window_unmap(m, w);
694 mmap_cache_fd_remove(m, fd_index, w);
697 w = m->by_fd[fd_index].windows;
700 memmove(m->by_fd + fd_index, m->by_fd + fd_index + 1, (m->n_fds - (fd_index + 1)) * sizeof(FileDescriptor));
704 void mmap_cache_close_context(MMapCache *m, unsigned context) {
705 mmap_cache_context_unset(m, context);