src/journal/mmap-cache.c

   1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
   2
   3 /***
   4   This file is part of systemd.
   5
   6   Copyright 2012 Lennart Poettering
   7
   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.
  12
  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.
  17
  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/>.
  20 ***/
  21
  22 #include <assert.h>
  23 #include <sys/mman.h>
  24 #include <errno.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27
  28 #include "util.h"
  29
  30 #include "mmap-cache.h"
  31
  32 #define WINDOW_SIZE (8ULL*1024ULL*1024ULL)
  33 #define WINDOWS_MAX 32
  34
  35 typedef struct Window {
  36         int fd;
  37         void *ptr;
  38         uint64_t offset;
  39         uint64_t size;
  40
  41         unsigned n_ref;
  42         unsigned lru_prev;
  43         unsigned lru_next;
  44
  45         unsigned by_fd_prev;
  46         unsigned by_fd_next;
  47 } Window;
  48
  49 typedef struct FileDescriptor {
  50         int fd;
  51         unsigned windows;
  52 } FileDescriptor;
  53
  54 struct MMapCache {
  55         unsigned n_ref;
  56
  57         unsigned contexts_max;
  58         unsigned windows_max;
  59         unsigned fds_max;
  60
  61         unsigned n_windows;
  62         unsigned n_fds;
  63
  64         unsigned lru_first, lru_last;
  65
  66         Window *windows;
  67         unsigned *by_context;
  68         FileDescriptor *by_fd;
  69 };
  70
  71 static void mmap_cache_window_unmap(MMapCache *m, unsigned w) {
  72         Window *v;
  73
  74         assert(m);
  75         assert(w < m->n_windows);
  76
  77         v = m->windows + w;
  78         if (!v->ptr)
  79                 return;
  80
  81         munmap(v->ptr, v->size);
  82         v->ptr = NULL;
  83 }
  84
  85 static void mmap_cache_window_add_lru(MMapCache *m, unsigned w) {
  86         Window *v;
  87
  88         assert(m);
  89         assert(w < m->n_windows);
  90
  91         v = m->windows + w;
  92         v->lru_prev = m->lru_last;
  93         v->lru_next = (unsigned) -1;
  94
  95         m->lru_last = w;
  96         if (m->lru_first == (unsigned) -1)
  97                 m->lru_first = w;
  98 }
  99
 100 static void mmap_cache_window_remove_lru(MMapCache *m, unsigned w) {
 101         Window *v;
 102
 103         assert(m);
 104         assert(w < m->n_windows);
 105
 106         v = m->windows + w;
 107
 108         if (v->lru_prev == (unsigned) -1)
 109                 m->lru_first = v->lru_next;
 110         else
 111                 m->windows[v->lru_prev].lru_next = v->lru_next;
 112
 113         if (v->lru_next == (unsigned) -1)
 114                 m->lru_last = v->lru_prev;
 115         else
 116                 m->windows[v->lru_next].lru_prev = v->lru_prev;
 117 }
 118
 119 static void mmap_cache_fd_add(MMapCache *m, unsigned fd_index, unsigned w) {
 120         Window *v;
 121
 122         assert(m);
 123         assert(fd_index < m->n_fds);
 124
 125         v = m->windows + w;
 126         v->by_fd_next = m->by_fd[fd_index].windows;
 127         v->by_fd_prev = (unsigned) -1;
 128
 129         m->by_fd[fd_index].windows = w;
 130 }
 131
 132 static void mmap_cache_fd_remove(MMapCache *m, unsigned fd_index, unsigned w) {
 133         Window *v;
 134
 135         assert(m);
 136         assert(fd_index < m->n_fds);
 137
 138         v = m->windows + w;
 139         if (v->by_fd_prev == (unsigned) -1)
 140                 m->by_fd[fd_index].windows = v->by_fd_next;
 141         else
 142                 m->windows[v->by_fd_prev].by_fd_next = v->by_fd_next;
 143
 144         if (v->by_fd_next != (unsigned) -1)
 145                 m->windows[v->by_fd_next].by_fd_prev = v->by_fd_prev;
 146 }
 147
 148 static void mmap_cache_context_unset(MMapCache *m, unsigned c) {
 149         Window *v;
 150         unsigned w;
 151
 152         assert(m);
 153         assert(c < m->contexts_max);
 154
 155         if (m->by_context[c] == (unsigned) -1)
 156                 return;
 157
 158         w = m->by_context[c];
 159         m->by_context[c] = (unsigned) -1;
 160
 161         v = m->windows + w;
 162         assert(v->n_ref > 0);
 163         v->n_ref --;
 164
 165         if (v->n_ref == 0)
 166                 mmap_cache_window_add_lru(m, w);
 167 }
 168
 169 static void mmap_cache_context_set(MMapCache *m, unsigned c, unsigned w) {
 170         Window *v;
 171
 172         assert(m);
 173         assert(c < m->contexts_max);
 174         assert(w < m->n_windows);
 175
 176         if (m->by_context[c] == w)
 177                 return;
 178
 179         mmap_cache_context_unset(m, c);
 180
 181         m->by_context[c] = w;
 182
 183         v = m->windows + w;
 184         v->n_ref ++;
 185         if (v->n_ref == 1)
 186                 mmap_cache_window_remove_lru(m, w);
 187 }
 188
 189 static void mmap_cache_free(MMapCache *m) {
 190
 191         assert(m);
 192
 193         if (m->windows) {
 194                 unsigned w;
 195
 196                 for (w = 0; w < m->n_windows; w++)
 197                         mmap_cache_window_unmap(m, w);
 198
 199                 free(m->windows);
 200         }
 201
 202         free(m->by_context);
 203         free(m->by_fd);
 204         free(m);
 205 }
 206
 207 MMapCache* mmap_cache_new(unsigned contexts_max, unsigned fds_max) {
 208         MMapCache *m;
 209
 210         assert(contexts_max > 0);
 211         assert(fds_max > 0);
 212
 213         m = new0(MMapCache, 1);
 214         if (!m)
 215                 return NULL;
 216
 217         m->contexts_max = contexts_max;
 218         m->fds_max = fds_max;
 219         m->windows_max = MAX(m->contexts_max, WINDOWS_MAX);
 220         m->n_ref = 1;
 221         m->lru_first = (unsigned) -1;
 222         m->lru_last = (unsigned) -1;
 223
 224         m->windows = new(Window, m->windows_max);
 225         if (!m->windows) {
 226                 mmap_cache_free(m);
 227                 return NULL;
 228         }
 229
 230         m->by_context = new(unsigned, m->contexts_max);
 231         if (!m->by_context) {
 232                 mmap_cache_free(m);
 233                 return NULL;
 234         }
 235
 236         memset(m->by_context, -1, m->contexts_max * sizeof(unsigned));
 237
 238         m->by_fd = new(FileDescriptor, m->fds_max);
 239         if (!m->by_fd) {
 240                 mmap_cache_free(m);
 241                 return NULL;
 242         }
 243
 244         return m;
 245 }
 246
 247 MMapCache* mmap_cache_ref(MMapCache *m) {
 248         assert(m);
 249         assert(m->n_ref > 0);
 250
 251         m->n_ref++;
 252         return m;
 253 }
 254
 255 MMapCache* mmap_cache_unref(MMapCache *m) {
 256         assert(m);
 257         assert(m->n_ref > 0);
 258
 259         if (m->n_ref == 1)
 260                 mmap_cache_free(m);
 261         else
 262                 m->n_ref--;
 263
 264         return NULL;
 265 }
 266
 267 static int mmap_cache_allocate_window(MMapCache *m, unsigned *w) {
 268         assert(m);
 269         assert(w);
 270
 271         if (m->n_windows < m->windows_max) {
 272                 *w = m->n_windows ++;
 273                 return 0;
 274         }
 275
 276         if (m->lru_first == (unsigned) -1)
 277                 return -E2BIG;
 278
 279         *w = m->lru_first;
 280         mmap_cache_window_unmap(m, *w);
 281         mmap_cache_window_remove_lru(m, *w);
 282
 283         return 0;
 284 }
 285
 286 static int mmap_cache_make_room(MMapCache *m) {
 287         unsigned w;
 288
 289         assert(m);
 290
 291         w = m->lru_first;
 292         while (w != (unsigned) -1) {
 293                 Window *v;
 294
 295                 v = m->windows + w;
 296
 297                 if (v->ptr) {
 298                         mmap_cache_window_unmap(m, w);
 299                         return 1;
 300                 }
 301
 302                 w = v->lru_next;
 303         }
 304
 305         return 0;
 306 }
 307
 308 static int mmap_cache_put(
 309                 MMapCache *m,
 310                 int fd,
 311                 unsigned fd_index,
 312                 int prot,
 313                 unsigned context,
 314                 uint64_t offset,
 315                 uint64_t size,
 316                 void **ret) {
 317
 318         unsigned w;
 319         Window *v;
 320         void *d;
 321         uint64_t woffset, wsize;
 322         int r;
 323
 324         assert(m);
 325         assert(fd >= 0);
 326         assert(context < m->contexts_max);
 327         assert(size > 0);
 328         assert(ret);
 329
 330         woffset = offset & ~((uint64_t) page_size() - 1ULL);
 331         wsize = size + (offset - woffset);
 332         wsize = PAGE_ALIGN(wsize);
 333
 334         if (wsize < WINDOW_SIZE) {
 335                 uint64_t delta;
 336
 337                 delta = (WINDOW_SIZE - wsize) / 2;
 338
 339                 if (delta > offset)
 340                         woffset = 0;
 341                 else
 342                         woffset -= delta;
 343
 344                 wsize = WINDOW_SIZE;
 345         }
 346
 347         for (;;) {
 348                 d = mmap(NULL, wsize, prot, MAP_SHARED, fd, woffset);
 349                 if (d != MAP_FAILED)
 350                         break;
 351                 if (errno != ENOMEM)
 352                         return -errno;
 353
 354                 r = mmap_cache_make_room(m);
 355                 if (r < 0)
 356                         return r;
 357                 if (r == 0)
 358                         return -ENOMEM;
 359         }
 360
 361         r = mmap_cache_allocate_window(m, &w);
 362         if (r < 0) {
 363                 munmap(d, wsize);
 364                 return r;
 365         }
 366
 367         v = m->windows + w;
 368         v->fd = fd;
 369         v->ptr = d;
 370         v->offset = woffset;
 371         v->size = wsize;
 372
 373         v->n_ref = 0;
 374         v->lru_prev = v->lru_next = (unsigned) -1;
 375
 376         mmap_cache_fd_add(m, fd_index, w);
 377         mmap_cache_context_set(m, context, w);
 378
 379         *ret = (uint8_t*) d + (offset - woffset);
 380         return 1;
 381 }
 382
 383 static int fd_cmp(const void *_a, const void *_b) {
 384         const FileDescriptor *a = _a, *b = _b;
 385
 386         if (a->fd < b->fd)
 387                 return -1;
 388         if (a->fd > b->fd)
 389                 return 1;
 390
 391         return 0;
 392 }
 393
 394 static int mmap_cache_get_fd_index(MMapCache *m, int fd, unsigned *fd_index) {
 395         FileDescriptor *j;
 396
 397         assert(m);
 398         assert(fd >= 0);
 399         assert(fd_index);
 400
 401         j = bsearch(&fd, m->by_fd, m->n_fds, sizeof(m->by_fd[0]), fd_cmp);
 402         if (!j) {
 403                 if (m->n_fds >= m->fds_max)
 404                         return -E2BIG;
 405
 406                 j = m->by_fd + m->n_fds ++;
 407                 j->fd = fd;
 408                 j->windows = (unsigned) -1;
 409
 410                 qsort(m->by_fd, m->n_fds, sizeof(m->by_fd[0]), fd_cmp);
 411                 j = bsearch(&fd, m->by_fd, m->n_fds, sizeof(m->by_fd[0]), fd_cmp);
 412         }
 413
 414         *fd_index = (unsigned) (j - m->by_fd);
 415         return 0;
 416 }
 417
 418 static bool mmap_cache_test_window(
 419                 MMapCache *m,
 420                 unsigned w,
 421                 uint64_t offset,
 422                 uint64_t size) {
 423         Window *v;
 424
 425         assert(m);
 426         assert(w < m->n_windows);
 427         assert(size > 0);
 428
 429         v = m->windows + w;
 430
 431         return offset >= v->offset &&
 432                 offset + size <= v->offset + v->size;
 433 }
 434
 435 static int mmap_cache_current(
 436                 MMapCache *m,
 437                 int fd,
 438                 unsigned context,
 439                 uint64_t offset,
 440                 uint64_t size,
 441                 void **ret) {
 442
 443         Window *v;
 444         unsigned w;
 445
 446         assert(m);
 447         assert(fd >= 0);
 448         assert(context < m->contexts_max);
 449         assert(size > 0);
 450         assert(ret);
 451
 452         if (m->by_context[context] == (unsigned) -1)
 453                 return 0;
 454
 455         w = m->by_context[context];
 456         v = m->windows + w;
 457
 458         if (v->fd != fd)
 459                 return 0;
 460
 461         if (!mmap_cache_test_window(m, w, offset, size))
 462                 return 0;
 463
 464         *ret = (uint8_t*) v->ptr + (offset - v->offset);
 465         return 1;
 466 }
 467
 468 static int mmap_cache_find(
 469                 MMapCache *m,
 470                 unsigned fd_index,
 471                 unsigned context,
 472                 uint64_t offset,
 473                 uint64_t size,
 474                 void **ret) {
 475
 476         Window *v = NULL;
 477         unsigned w;
 478
 479         assert(m);
 480         assert(fd_index < m->n_fds);
 481         assert(context < m->contexts_max);
 482         assert(size > 0);
 483         assert(ret);
 484
 485         w = m->by_fd[fd_index].windows;
 486         while (w != (unsigned) -1) {
 487                 if (mmap_cache_test_window(m, w, offset, size))
 488                         break;
 489
 490                 w = m->windows[w].by_fd_next;
 491         }
 492
 493         if (w == (unsigned) -1)
 494                 return 0;
 495
 496         mmap_cache_context_set(m, context, w);
 497
 498         v = m->windows + w;
 499         *ret = (uint8_t*) v->ptr + (offset - v->offset);
 500         return 1;
 501 }
 502
 503 int mmap_cache_get(
 504                 MMapCache *m,
 505                 int fd,
 506                 int prot,
 507                 unsigned context,
 508                 uint64_t offset,
 509                 uint64_t size,
 510                 void **ret) {
 511
 512         unsigned fd_index;
 513         int r;
 514
 515         assert(m);
 516         assert(fd >= 0);
 517         assert(context < m->contexts_max);
 518         assert(size > 0);
 519         assert(ret);
 520
 521         /* Maybe the current pointer for this context is already the
 522          * right one? */
 523         r = mmap_cache_current(m, fd, context, offset, size, ret);
 524         if (r != 0)
 525                 return r;
 526
 527         /* OK, let's find the chain for this FD */
 528         r = mmap_cache_get_fd_index(m, fd, &fd_index);
 529         if (r < 0)
 530                 return r;
 531
 532         /* And let's look through the available mmaps */
 533         r = mmap_cache_find(m, fd_index, context, offset, size, ret);
 534         if (r != 0)
 535                 return r;
 536
 537         /* Not found? Then, let's add it */
 538         return mmap_cache_put(m, fd, fd_index, prot, context, offset, size, ret);
 539 }
 540
 541 void mmap_cache_close_fd(MMapCache *m, int fd) {
 542         FileDescriptor *j;
 543         unsigned fd_index, c, w;
 544
 545         assert(m);
 546         assert(fd > 0);
 547
 548         j = bsearch(&fd, m->by_fd, m->n_fds, sizeof(m->by_fd[0]), fd_cmp);
 549         if (!j)
 550                 return;
 551         fd_index = (unsigned) (j - m->by_fd);
 552
 553         for (c = 0; c < m->contexts_max; c++) {
 554                 w = m->by_context[c];
 555                 if (w == (unsigned) -1)
 556                         continue;
 557
 558                 if (m->windows[w].fd == fd)
 559                         mmap_cache_context_unset(m, c);
 560         }
 561
 562         w = m->by_fd[fd_index].windows;
 563         while (w != (unsigned) -1) {
 564
 565                 mmap_cache_fd_remove(m, fd_index, w);
 566                 mmap_cache_window_unmap(m, w);
 567
 568                 w = m->by_fd[fd_index].windows;
 569         }
 570
 571         memmove(m->by_fd + fd_index, m->by_fd + fd_index + 1, (m->n_fds - (fd_index + 1)) * sizeof(FileDescriptor));
 572         m->n_fds --;
 573 }
 574
 575 void mmap_cache_close_context(MMapCache *m, unsigned context) {
 576         mmap_cache_context_unset(m, context);
 577 }