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) {
341 mmap_cache_window_unmap(m
, w
);
351 static int mmap_cache_put(
364 uint64_t woffset
, wsize
;
369 assert(context
< m
->contexts_max
);
373 woffset
= offset
& ~((uint64_t) page_size() - 1ULL);
374 wsize
= size
+ (offset
- woffset
);
375 wsize
= PAGE_ALIGN(wsize
);
377 if (wsize
< WINDOW_SIZE
) {
380 delta
= PAGE_ALIGN((WINDOW_SIZE
- wsize
) / 2);
391 d
= mmap(NULL
, wsize
, prot
, MAP_SHARED
, fd
, woffset
);
397 r
= mmap_cache_make_room(m
);
404 r
= mmap_cache_allocate_window(m
, &w
);
417 mmap_cache_window_add_lru(m
, w
);
418 mmap_cache_fd_add(m
, fd_index
, w
);
419 mmap_cache_context_set(m
, context
, w
);
421 *ret
= (uint8_t*) d
+ (offset
- woffset
);
425 static int fd_cmp(const void *_a
, const void *_b
) {
426 const FileDescriptor
*a
= _a
, *b
= _b
;
436 static int mmap_cache_peek_fd_index(MMapCache
*m
, int fd
, unsigned *fd_index
) {
444 for (r
= 0; r
< m
->n_fds
; r
++)
445 assert(m
->by_fd
[r
].windows
== (unsigned) -1 ||
446 m
->windows
[m
->by_fd
[r
].windows
].fd
== m
->by_fd
[r
].fd
);
448 j
= bsearch(&fd
, m
->by_fd
, m
->n_fds
, sizeof(FileDescriptor
), fd_cmp
);
452 *fd_index
= (unsigned) (j
- m
->by_fd
);
456 static int mmap_cache_get_fd_index(MMapCache
*m
, int fd
, unsigned *fd_index
) {
464 r
= mmap_cache_peek_fd_index(m
, fd
, fd_index
);
468 if (m
->n_fds
>= m
->fds_max
) {
473 n
= realloc(m
->by_fd
, sizeof(FileDescriptor
) * k
);
481 j
= m
->by_fd
+ m
->n_fds
++;
483 j
->windows
= (unsigned) -1;
485 qsort(m
->by_fd
, m
->n_fds
, sizeof(FileDescriptor
), fd_cmp
);
487 return mmap_cache_peek_fd_index(m
, fd
, fd_index
);
490 static bool mmap_cache_test_window(
498 assert(w
< m
->n_windows
);
503 return offset
>= v
->offset
&&
504 offset
+ size
<= v
->offset
+ v
->size
;
507 static int mmap_cache_current(
520 assert(context
< m
->contexts_max
);
524 if (m
->by_context
[context
] == (unsigned) -1)
527 w
= m
->by_context
[context
];
533 if (!mmap_cache_test_window(m
, w
, offset
, size
))
536 *ret
= (uint8_t*) v
->ptr
+ (offset
- v
->offset
);
540 static int mmap_cache_find(
554 assert(fd_index
< m
->n_fds
);
555 assert(context
< m
->contexts_max
);
559 w
= m
->by_fd
[fd_index
].windows
;
560 while (w
!= (unsigned) -1) {
564 if (mmap_cache_test_window(m
, w
, offset
, size
))
570 if (w
== (unsigned) -1)
573 mmap_cache_context_set(m
, context
, w
);
575 *ret
= (uint8_t*) v
->ptr
+ (offset
- v
->offset
);
596 if (context
>= m
->contexts_max
) {
600 /* Increase the number of contexts if necessary, and
601 * make sure we have twice the number of windows */
604 n
= realloc(m
->by_context
, sizeof(unsigned) * k
);
607 memset(n
+ m
->contexts_max
, -1, (k
- m
->contexts_max
) * sizeof(unsigned));
611 k
= MAX(m
->windows_max
, m
->contexts_max
*2);
612 w
= realloc(m
->windows
, sizeof(Window
) * k
);
620 /* Maybe the current pointer for this context is already the
622 r
= mmap_cache_current(m
, fd
, context
, offset
, size
, ret
);
626 /* Hmm, drop the reference to the current one, since it wasn't
628 mmap_cache_context_unset(m
, context
);
630 /* OK, let's find the chain for this FD */
631 r
= mmap_cache_get_fd_index(m
, fd
, &fd_index
);
635 /* And let's look through the available mmaps */
636 r
= mmap_cache_find(m
, fd
, fd_index
, context
, offset
, size
, ret
);
640 /* Not found? Then, let's add it */
641 return mmap_cache_put(m
, fd
, fd_index
, prot
, context
, offset
, size
, ret
);
644 void mmap_cache_close_fd(MMapCache
*m
, int fd
) {
645 unsigned fd_index
, c
, w
;
651 r
= mmap_cache_peek_fd_index(m
, fd
, &fd_index
);
655 for (c
= 0; c
< m
->contexts_max
; c
++) {
656 w
= m
->by_context
[c
];
657 if (w
== (unsigned) -1)
660 if (m
->windows
[w
].fd
== fd
)
661 mmap_cache_context_unset(m
, c
);
664 w
= m
->by_fd
[fd_index
].windows
;
665 while (w
!= (unsigned) -1) {
671 mmap_cache_window_unmap(m
, w
);
672 mmap_cache_fd_remove(m
, fd_index
, w
);
675 w
= m
->by_fd
[fd_index
].windows
;
678 memmove(m
->by_fd
+ fd_index
, m
->by_fd
+ fd_index
+ 1, (m
->n_fds
- (fd_index
+ 1)) * sizeof(FileDescriptor
));
682 void mmap_cache_close_fd_range(MMapCache
*m
, int fd
, uint64_t p
) {
683 unsigned fd_index
, c
, w
;
689 /* This drops all windows that include space right of the
690 * specified offset. This is useful to ensure that after the
691 * file size is extended we drop our mappings of the end and
692 * create it anew, since otherwise it is undefined whether
693 * mapping will continue to work as intended. */
695 r
= mmap_cache_peek_fd_index(m
, fd
, &fd_index
);
699 for (c
= 0; c
< m
->contexts_max
; c
++) {
700 w
= m
->by_context
[c
];
702 if (w
!= (unsigned) -1 && m
->windows
[w
].fd
== fd
)
703 mmap_cache_context_unset(m
, c
);
706 w
= m
->by_fd
[fd_index
].windows
;
707 while (w
!= (unsigned) -1) {
712 assert(v
->by_fd_next
== (unsigned) -1 ||
713 m
->windows
[v
->by_fd_next
].fd
== fd
);
715 if (v
->offset
+ v
->size
> p
) {
717 mmap_cache_window_unmap(m
, w
);
718 mmap_cache_fd_remove(m
, fd_index
, w
);
721 w
= m
->by_fd
[fd_index
].windows
;
727 void mmap_cache_close_context(MMapCache
*m
, unsigned context
) {
728 mmap_cache_context_unset(m
, context
);