src/journal/mmap-cache.c

	mmap-cache.c revision f65425cbc4385b4f5b20ded641cbb07ad6a0938f
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen/***
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen  This file is part of systemd.
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen  Copyright 2012 Lennart Poettering
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen  systemd is free software; you can redistribute it and/or modify it
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen  under the terms of the GNU Lesser General Public License as published by
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen  the Free Software Foundation; either version 2.1 of the License, or
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen  (at your option) any later version.
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen  systemd is distributed in the hope that it will be useful, but
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen  WITHOUT ANY WARRANTY; without even the implied warranty of
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen  Lesser General Public License for more details.
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen  You should have received a copy of the GNU Lesser General Public License
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen  along with systemd; If not, see <http://www.gnu.org/licenses/>.
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen***/
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen
b5efdb8af40ea759a1ea584c1bc44ecc81dd00ceLennart Poettering#include <assert.h>
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen#include <sys/mman.h>
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen#include <errno.h>
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich#include <stdlib.h>
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen#include <string.h>
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen#include "util.h"
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen#include "mmap-cache.h"
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen
a2ba62c719224a4b47751623ca5e8b0333f49721Lennart Poettering#define WINDOW_SIZE (8ULL*1024ULL*1024ULL)
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen#define WINDOWS_MAX 32
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersentypedef struct Window {
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen        int fd;
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen        void *ptr;
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen        uint64_t offset;
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen        uint64_t size;
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen        unsigned n_ref;
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen        unsigned lru_prev;
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen        unsigned lru_next;
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen
a2ba62c719224a4b47751623ca5e8b0333f49721Lennart Poettering        unsigned by_fd_prev;
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen        unsigned by_fd_next;
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen} Window;
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersentypedef struct FileDescriptor {
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen        int fd;
a2ba62c719224a4b47751623ca5e8b0333f49721Lennart Poettering        unsigned windows;
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen} FileDescriptor;
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersenstruct MMapCache {
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen        unsigned n_ref;
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen        unsigned contexts_max;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        unsigned windows_max;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        unsigned fds_max;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        unsigned n_windows;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        unsigned n_fds;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        unsigned lru_first, lru_last;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        Window *windows;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        unsigned *by_context;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        FileDescriptor *by_fd;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich};
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovichstatic int mmap_cache_peek_fd_index(MMapCache *m, int fd, unsigned *fd_index);
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovichstatic void mmap_cache_window_unmap(MMapCache *m, unsigned w) {
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        Window *v;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        assert(m);
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        assert(w < m->n_windows);
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        v = m->windows + w;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        if (!v->ptr)
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich                return;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        munmap(v->ptr, v->size);
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        v->ptr = NULL;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich}
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovichstatic void mmap_cache_window_add_lru(MMapCache *m, unsigned w) {
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        Window *v;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        assert(m);
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        assert(w < m->n_windows);
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        v = m->windows + w;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        assert(v->n_ref == 0);
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        if (m->lru_last != (unsigned) -1) {
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich                assert(m->windows[m->lru_last].lru_next == (unsigned) -1);
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich                m->windows[m->lru_last].lru_next = w;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        }
5bb14c8651b017983bb9cbd1444969c7a1bda14eTom Gundersen
5bb14c8651b017983bb9cbd1444969c7a1bda14eTom Gundersen        v->lru_prev = m->lru_last;
5bb14c8651b017983bb9cbd1444969c7a1bda14eTom Gundersen        v->lru_next = (unsigned) -1;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        m->lru_last = w;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        if (m->lru_first == (unsigned) -1)
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich                m->lru_first = w;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich}
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovichstatic void mmap_cache_window_remove_lru(MMapCache *m, unsigned w) {
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        Window *v;
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        assert(m);
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        assert(w < m->n_windows);
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich
5347925a59530bd4e6616eb8c8d43a02c3e14c46Tom Gundersen        v = m->windows + w;
5347925a59530bd4e6616eb8c8d43a02c3e14c46Tom Gundersen
7c99d940c11e4da1863a218b6b70dd16e65b7518Tom Gundersen        if (v->lru_prev == (unsigned) -1) {
7c99d940c11e4da1863a218b6b70dd16e65b7518Tom Gundersen                assert(m->lru_first == w);
7c99d940c11e4da1863a218b6b70dd16e65b7518Tom Gundersen                m->lru_first = v->lru_next;
7c99d940c11e4da1863a218b6b70dd16e65b7518Tom Gundersen        } else {
12e0f830f592ec4c6bb49ac7ae1e0e84f74105e3Tom Gundersen                assert(m->windows[v->lru_prev].lru_next == w);
7c99d940c11e4da1863a218b6b70dd16e65b7518Tom Gundersen                m->windows[v->lru_prev].lru_next = v->lru_next;
5347925a59530bd4e6616eb8c8d43a02c3e14c46Tom Gundersen        }
5347925a59530bd4e6616eb8c8d43a02c3e14c46Tom Gundersen
5347925a59530bd4e6616eb8c8d43a02c3e14c46Tom Gundersen        if (v->lru_next == (unsigned) -1) {
5347925a59530bd4e6616eb8c8d43a02c3e14c46Tom Gundersen                assert(m->lru_last == w);
5347925a59530bd4e6616eb8c8d43a02c3e14c46Tom Gundersen                m->lru_last = v->lru_prev;
5347925a59530bd4e6616eb8c8d43a02c3e14c46Tom Gundersen        } else {
12e0f830f592ec4c6bb49ac7ae1e0e84f74105e3Tom Gundersen                assert(m->windows[v->lru_next].lru_prev == w);
5347925a59530bd4e6616eb8c8d43a02c3e14c46Tom Gundersen                m->windows[v->lru_next].lru_prev = v->lru_prev;
5347925a59530bd4e6616eb8c8d43a02c3e14c46Tom Gundersen        }
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen}
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersenstatic void mmap_cache_fd_add(MMapCache *m, unsigned fd_index, unsigned w) {
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen        Window *v;
505f8da7325591defe5f751f328bd26915267602Tom Gundersen
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen        assert(m);
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen        assert(fd_index < m->n_fds);
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen
505f8da7325591defe5f751f328bd26915267602Tom Gundersen        v = m->windows + w;
12e0f830f592ec4c6bb49ac7ae1e0e84f74105e3Tom Gundersen        assert(m->by_fd[fd_index].fd == v->fd);
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen        if (m->by_fd[fd_index].windows != (unsigned) -1) {
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen                assert(m->windows[m->by_fd[fd_index].windows].by_fd_prev == (unsigned) -1);
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen                m->windows[m->by_fd[fd_index].windows].by_fd_prev = w;
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        }
f0213e3796b4dd66e546e2de4d677db319f9171bTom Gundersen
f0213e3796b4dd66e546e2de4d677db319f9171bTom Gundersen        v->by_fd_next = m->by_fd[fd_index].windows;
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        v->by_fd_prev = (unsigned) -1;
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        m->by_fd[fd_index].windows = w;
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen}
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersenstatic void mmap_cache_fd_remove(MMapCache *m, unsigned fd_index, unsigned w) {
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        Window *v;
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        assert(m);
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        assert(fd_index < m->n_fds);
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        v = m->windows + w;
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        assert(m->by_fd[fd_index].fd == v->fd);
3ac8e5433f20bfb5e12b918252643106a2de52afTom Gundersen        assert(v->by_fd_next == (unsigned) -1 || m->windows[v->by_fd_next].fd == v->fd);
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        assert(v->by_fd_prev == (unsigned) -1 || m->windows[v->by_fd_prev].fd == v->fd);
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen
3ac8e5433f20bfb5e12b918252643106a2de52afTom Gundersen        if (v->by_fd_prev == (unsigned) -1) {
3ac8e5433f20bfb5e12b918252643106a2de52afTom Gundersen                assert(m->by_fd[fd_index].windows == w);
3ac8e5433f20bfb5e12b918252643106a2de52afTom Gundersen                m->by_fd[fd_index].windows = v->by_fd_next;
3ac8e5433f20bfb5e12b918252643106a2de52afTom Gundersen        } else {
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen                assert(m->windows[v->by_fd_prev].by_fd_next == w);
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen                m->windows[v->by_fd_prev].by_fd_next = v->by_fd_next;
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        }
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        if (v->by_fd_next != (unsigned) -1) {
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen                assert(m->windows[v->by_fd_next].by_fd_prev == w);
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen                m->windows[v->by_fd_next].by_fd_prev = v->by_fd_prev;
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        }
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen}
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersenstatic void mmap_cache_context_unset(MMapCache *m, unsigned c) {
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        Window *v;
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        unsigned w;
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        assert(m);
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        assert(c < m->contexts_max);
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen        if (m->by_context[c] == (unsigned) -1)
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen                return;
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen        w = m->by_context[c];
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen        m->by_context[c] = (unsigned) -1;
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen        v = m->windows + w;
5347925a59530bd4e6616eb8c8d43a02c3e14c46Tom Gundersen        assert(v->n_ref > 0);
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen        v->n_ref --;
09bee74d7a5f266b175baa19892fa84a9da51d7fTom Gundersen
e1ea665edac17d75fce01b72dadfa3211b60df2cEugene Yakubovich        if (v->n_ref == 0)
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen                mmap_cache_window_add_lru(m, w);
9505d3c6deda0452c22ab2ed47bca74b98d87a17Tom Gundersen}
12e0f830f592ec4c6bb49ac7ae1e0e84f74105e3Tom Gundersen
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersenstatic void mmap_cache_context_set(MMapCache *m, unsigned c, unsigned w) {
5347925a59530bd4e6616eb8c8d43a02c3e14c46Tom Gundersen        Window *v;
5347925a59530bd4e6616eb8c8d43a02c3e14c46Tom Gundersen
5347925a59530bd4e6616eb8c8d43a02c3e14c46Tom Gundersen        assert(m);
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen        assert(c < m->contexts_max);
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen        assert(w < m->n_windows);
12e0f830f592ec4c6bb49ac7ae1e0e84f74105e3Tom Gundersen
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen        if (m->by_context[c] == w)
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen                return;
12e0f830f592ec4c6bb49ac7ae1e0e84f74105e3Tom Gundersen
12e0f830f592ec4c6bb49ac7ae1e0e84f74105e3Tom Gundersen        mmap_cache_context_unset(m, c);
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen        m->by_context[c] = w;
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen
505f8da7325591defe5f751f328bd26915267602Tom Gundersen        v = m->windows + w;
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen        v->n_ref ++;
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen        if (v->n_ref == 1)
f579559b3a14c1f1ef96c372e7626c4733e6ef7dTom Gundersen                mmap_cache_window_remove_lru(m, w);
}

static void mmap_cache_free(MMapCache *m) {

        assert(m);

        if (m->windows) {
                unsigned w;

                for (w = 0; w < m->n_windows; w++)
                        mmap_cache_window_unmap(m, w);

                free(m->windows);
        }

        free(m->by_context);
        free(m->by_fd);
        free(m);
}

MMapCache* mmap_cache_new(unsigned contexts_max, unsigned fds_max) {
        MMapCache *m;

        assert(contexts_max > 0);
        assert(fds_max > 0);

        m = new0(MMapCache, 1);
        if (!m)
                return NULL;

        m->contexts_max = contexts_max;
        m->fds_max = fds_max;
        m->windows_max = MAX(m->contexts_max, WINDOWS_MAX);
        m->n_ref = 1;
        m->lru_first = (unsigned) -1;
        m->lru_last = (unsigned) -1;

        m->windows = new(Window, m->windows_max);
        if (!m->windows) {
                mmap_cache_free(m);
                return NULL;
        }

        m->by_context = new(unsigned, m->contexts_max);
        if (!m->by_context) {
                mmap_cache_free(m);
                return NULL;
        }
        memset(m->by_context, -1, m->contexts_max * sizeof(unsigned));

        m->by_fd = new(FileDescriptor, m->fds_max);
        if (!m->by_fd) {
                mmap_cache_free(m);
                return NULL;
        }

        return m;
}

MMapCache* mmap_cache_ref(MMapCache *m) {
        assert(m);
        assert(m->n_ref > 0);

        m->n_ref++;
        return m;
}

MMapCache* mmap_cache_unref(MMapCache *m) {
        assert(m);
        assert(m->n_ref > 0);

        if (m->n_ref == 1)
                mmap_cache_free(m);
        else
                m->n_ref--;

        return NULL;
}

static int mmap_cache_allocate_window(MMapCache *m, unsigned *w) {
        Window *v;
        unsigned fd_index;

        assert(m);
        assert(w);

        if (m->n_windows < m->windows_max) {
                *w = m->n_windows ++;
                return 0;
        }

        if (m->lru_first == (unsigned) -1)
                return -E2BIG;

        *w = m->lru_first;
        v = m->windows + *w;
        assert(v->n_ref == 0);

        mmap_cache_window_unmap(m, *w);

        if (v->fd >= 0) {
                assert_se(mmap_cache_peek_fd_index(m, v->fd, &fd_index) > 0);
                mmap_cache_fd_remove(m, fd_index, *w);
        }

        mmap_cache_window_remove_lru(m, *w);

        return 0;
}

static int mmap_cache_make_room(MMapCache *m) {
        unsigned w;

        assert(m);

        w = m->lru_first;
        while (w != (unsigned) -1) {
                Window *v;

                v = m->windows + w;

                if (v->ptr) {
                        mmap_cache_window_unmap(m, w);
                        return 1;
                }

                w = v->lru_next;
        }

        return 0;
}

static int mmap_cache_put(
                MMapCache *m,
                int fd,
                unsigned fd_index,
                int prot,
                unsigned context,
                uint64_t offset,
                uint64_t size,
                void **ret) {

        unsigned w;
        Window *v;
        void *d;
        uint64_t woffset, wsize;
        int r;

        assert(m);
        assert(fd >= 0);
        assert(context < m->contexts_max);
        assert(size > 0);
        assert(ret);

        woffset = offset & ~((uint64_t) page_size() - 1ULL);
        wsize = size + (offset - woffset);
        wsize = PAGE_ALIGN(wsize);

        if (wsize < WINDOW_SIZE) {
                uint64_t delta;

                delta = PAGE_ALIGN((WINDOW_SIZE - wsize) / 2);

                if (delta > offset)
                        woffset = 0;
                else
                        woffset -= delta;

                wsize = WINDOW_SIZE;
        }

        for (;;) {
                d = mmap(NULL, wsize, prot, MAP_SHARED, fd, woffset);
                if (d != MAP_FAILED)
                        break;
                if (errno != ENOMEM)
                        return -errno;

                r = mmap_cache_make_room(m);
                if (r < 0)
                        return r;
                if (r == 0)
                        return -ENOMEM;
        }

        r = mmap_cache_allocate_window(m, &w);
        if (r < 0) {
                munmap(d, wsize);
                return r;
        }

        v = m->windows + w;
        v->fd = fd;
        v->ptr = d;
        v->offset = woffset;
        v->size = wsize;

        v->n_ref = 0;
        mmap_cache_window_add_lru(m, w);
        mmap_cache_fd_add(m, fd_index, w);
        mmap_cache_context_set(m, context, w);

        *ret = (uint8_t*) d + (offset - woffset);
        return 1;
}

static int fd_cmp(const void *_a, const void *_b) {
        const FileDescriptor *a = _a, *b = _b;

        if (a->fd < b->fd)
                return -1;
        if (a->fd > b->fd)
                return 1;

        return 0;
}

static int mmap_cache_peek_fd_index(MMapCache *m, int fd, unsigned *fd_index) {
        FileDescriptor *j;
        unsigned r;

        assert(m);
        assert(fd >= 0);
        assert(fd_index);

        for (r = 0; r < m->n_fds; r++)
                assert(m->by_fd[r].windows == (unsigned) -1 ||
                       m->windows[m->by_fd[r].windows].fd == m->by_fd[r].fd);

        j = bsearch(&fd, m->by_fd, m->n_fds, sizeof(FileDescriptor), fd_cmp);
        if (!j)
                return 0;

        *fd_index = (unsigned) (j - m->by_fd);
        return 1;
}

static int mmap_cache_get_fd_index(MMapCache *m, int fd, unsigned *fd_index) {
        FileDescriptor *j;
        int r;

        assert(m);
        assert(fd >= 0);
        assert(fd_index);

        r = mmap_cache_peek_fd_index(m, fd, fd_index);
        if (r != 0)
                return r;

        if (m->n_fds >= m->fds_max)
                return -E2BIG;

        j = m->by_fd + m->n_fds ++;
        j->fd = fd;
        j->windows = (unsigned) -1;

        qsort(m->by_fd, m->n_fds, sizeof(FileDescriptor), fd_cmp);

        return mmap_cache_peek_fd_index(m, fd, fd_index);
}

static bool mmap_cache_test_window(
                MMapCache *m,
                unsigned w,
                uint64_t offset,
                uint64_t size) {
        Window *v;

        assert(m);
        assert(w < m->n_windows);
        assert(size > 0);

        v = m->windows + w;

        return offset >= v->offset &&
                offset + size <= v->offset + v->size;
}

static int mmap_cache_current(
                MMapCache *m,
                int fd,
                unsigned context,
                uint64_t offset,
                uint64_t size,
                void **ret) {

        Window *v;
        unsigned w;

        assert(m);
        assert(fd >= 0);
        assert(context < m->contexts_max);
        assert(size > 0);
        assert(ret);

        if (m->by_context[context] == (unsigned) -1)
                return 0;

        w = m->by_context[context];
        v = m->windows + w;

        if (v->fd != fd)
                return 0;

        if (!mmap_cache_test_window(m, w, offset, size))
                return 0;

        *ret = (uint8_t*) v->ptr + (offset - v->offset);
        return 1;
}

static int mmap_cache_find(
                MMapCache *m,
                int fd,
                unsigned fd_index,
                unsigned context,
                uint64_t offset,
                uint64_t size,
                void **ret) {

        Window *v = NULL;
        unsigned w;

        assert(m);
        assert(fd >= 0);
        assert(fd_index < m->n_fds);
        assert(context < m->contexts_max);
        assert(size > 0);
        assert(ret);

        w = m->by_fd[fd_index].windows;
        while (w != (unsigned) -1) {
                v = m->windows + w;
                assert(v->fd == fd);

                if (mmap_cache_test_window(m, w, offset, size))
                        break;

                w = v->by_fd_next;
        }

        if (w == (unsigned) -1)
                return 0;

        mmap_cache_context_set(m, context, w);

        *ret = (uint8_t*) v->ptr + (offset - v->offset);
        return 1;
}

int mmap_cache_get(
                MMapCache *m,
                int fd,
                int prot,
                unsigned context,
                uint64_t offset,
                uint64_t size,
                void **ret) {

        unsigned fd_index;
        int r;

        assert(m);
        assert(fd >= 0);
        assert(context < m->contexts_max);
        assert(size > 0);
        assert(ret);

        /* Maybe the current pointer for this context is already the
         * right one? */
        r = mmap_cache_current(m, fd, context, offset, size, ret);
        if (r != 0)
                return r;

        /* Hmm, drop the reference to the current one, since it wasn't
         * good enough */
        mmap_cache_context_unset(m, context);

        /* OK, let's find the chain for this FD */
        r = mmap_cache_get_fd_index(m, fd, &fd_index);
        if (r < 0)
                return r;

        /* And let's look through the available mmaps */
        r = mmap_cache_find(m, fd, fd_index, context, offset, size, ret);
        if (r != 0)
                return r;

        /* Not found? Then, let's add it */
        return mmap_cache_put(m, fd, fd_index, prot, context, offset, size, ret);
}

void mmap_cache_close_fd(MMapCache *m, int fd) {
        unsigned fd_index, c, w;
        int r;

        assert(m);
        assert(fd > 0);

        r = mmap_cache_peek_fd_index(m, fd, &fd_index);
        if (r <= 0)
                return;

        for (c = 0; c < m->contexts_max; c++) {
                w = m->by_context[c];
                if (w == (unsigned) -1)
                        continue;

                if (m->windows[w].fd == fd)
                        mmap_cache_context_unset(m, c);
        }

        w = m->by_fd[fd_index].windows;
        while (w != (unsigned) -1) {
                Window *v;

                v = m->windows + w;
                assert(v->fd == fd);

                mmap_cache_window_unmap(m, w);
                mmap_cache_fd_remove(m, fd_index, w);
                v->fd = -1;

                w = m->by_fd[fd_index].windows;
        }

        memmove(m->by_fd + fd_index, m->by_fd + fd_index + 1, (m->n_fds - (fd_index + 1)) * sizeof(FileDescriptor));
        m->n_fds --;
}

void mmap_cache_close_fd_range(MMapCache *m, int fd, uint64_t p) {
        unsigned fd_index, c, w;
        int r;

        assert(m);
        assert(fd > 0);

        /* This drops all windows that include space right of the
         * specified offset. This is useful to ensure that after the
         * file size is extended we drop our mappings of the end and
         * create it anew, since otherwise it is undefined whether
         * mapping will continue to work as intended. */

        r = mmap_cache_peek_fd_index(m, fd, &fd_index);
        if (r <= 0)
                return;

        for (c = 0; c < m->contexts_max; c++) {
                w = m->by_context[c];

                if (w != (unsigned) -1 && m->windows[w].fd == fd)
                        mmap_cache_context_unset(m, c);
        }

        w = m->by_fd[fd_index].windows;
        while (w != (unsigned) -1) {
                Window *v;

                v = m->windows + w;
                assert(v->fd == fd);
                assert(v->by_fd_next == (unsigned) -1 ||
                       m->windows[v->by_fd_next].fd == fd);

                if (v->offset + v->size > p) {

                        mmap_cache_window_unmap(m, w);
                        mmap_cache_fd_remove(m, fd_index, w);
                        v->fd = -1;

                        w = m->by_fd[fd_index].windows;
                } else
                        w = v->by_fd_next;
        }
}

void mmap_cache_close_context(MMapCache *m, unsigned context) {
        mmap_cache_context_unset(m, context);
}