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
  34 #define DEFAULT_WINDOWS_MAX 64
  35 #define DEFAULT_FDS_MAX 32
  36 #define DEFAULT_CONTEXTS_MAX 32
  37
  38 typedef struct Window {
  39         int fd;
  40         void *ptr;
  41         uint64_t offset;
  42         uint64_t size;
  43
  44         unsigned n_ref;
  45         unsigned lru_prev;
  46         unsigned lru_next;
  47
  48         unsigned by_fd_prev;
  49         unsigned by_fd_next;
  50 } Window;
  51
  52 typedef struct FileDescriptor {
  53         int fd;
  54         unsigned windows;
  55 } FileDescriptor;
  56
  57 struct MMapCache {
  58         unsigned n_ref;
  59
  60         unsigned contexts_max;
  61         unsigned windows_max;
  62         unsigned fds_max;
  63
  64         unsigned n_windows;
  65         unsigned n_fds;
  66
  67         unsigned lru_first, lru_last;
  68
  69         Window *windows;
  70         unsigned *by_context;
  71         FileDescriptor *by_fd;
  72 };
  73
  74 static int mmap_cache_peek_fd_index(MMapCache *m, int fd, unsigned *fd_index);
  75
  76 static void mmap_cache_window_unmap(MMapCache *m, unsigned w) {
  77         Window *v;
  78
  79         assert(m);
  80         assert(w < m->n_windows);
  81
  82         v = m->windows + w;
  83         if (!v->ptr)
  84                 return;
  85
  86         munmap(v->ptr, v->size);
  87         v->ptr = NULL;
  88 }
  89
  90 static void mmap_cache_window_add_lru(MMapCache *m, unsigned w) {
  91         Window *v;
  92
  93         assert(m);
  94         assert(w < m->n_windows);
  95
  96         v = m->windows + w;
  97         assert(v->n_ref == 0);
  98
  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;
 102         }
 103
 104         v->lru_prev = m->lru_last;
 105         v->lru_next = (unsigned) -1;
 106
 107         m->lru_last = w;
 108         if (m->lru_first == (unsigned) -1)
 109                 m->lru_first = w;
 110 }
 111
 112 static void mmap_cache_window_remove_lru(MMapCache *m, unsigned w) {
 113         Window *v;
 114
 115         assert(m);
 116         assert(w < m->n_windows);
 117
 118         v = m->windows + w;
 119
 120         if (v->lru_prev == (unsigned) -1) {
 121                 assert(m->lru_first == w);
 122                 m->lru_first = v->lru_next;
 123         } else {
 124                 assert(m->windows[v->lru_prev].lru_next == w);
 125                 m->windows[v->lru_prev].lru_next = v->lru_next;
 126         }
 127
 128         if (v->lru_next == (unsigned) -1) {
 129                 assert(m->lru_last == w);
 130                 m->lru_last = v->lru_prev;
 131         } else {
 132                 assert(m->windows[v->lru_next].lru_prev == w);
 133                 m->windows[v->lru_next].lru_prev = v->lru_prev;
 134         }
 135 }
 136
 137 static void mmap_cache_fd_add(MMapCache *m, unsigned fd_index, unsigned w) {
 138         Window *v;
 139
 140         assert(m);
 141         assert(fd_index < m->n_fds);
 142
 143         v = m->windows + w;
 144         assert(m->by_fd[fd_index].fd == v->fd);
 145
 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;
 149         }
 150
 151         v->by_fd_next = m->by_fd[fd_index].windows;
 152         v->by_fd_prev = (unsigned) -1;
 153
 154         m->by_fd[fd_index].windows = w;
 155 }
 156
 157 static void mmap_cache_fd_remove(MMapCache *m, unsigned fd_index, unsigned w) {
 158         Window *v;
 159
 160         assert(m);
 161         assert(fd_index < m->n_fds);
 162
 163         v = m->windows + w;
 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);
 167
 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;
 171         } else {
 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;
 174         }
 175
 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;
 179         }
 180 }
 181
 182 static void mmap_cache_context_unset(MMapCache *m, unsigned c) {
 183         Window *v;
 184         unsigned w;
 185
 186         assert(m);
 187         assert(c < m->contexts_max);
 188
 189         if (m->by_context[c] == (unsigned) -1)
 190                 return;
 191
 192         w = m->by_context[c];
 193         m->by_context[c] = (unsigned) -1;
 194
 195         v = m->windows + w;
 196         assert(v->n_ref > 0);
 197         v->n_ref --;
 198
 199         if (v->n_ref == 0)
 200                 mmap_cache_window_add_lru(m, w);
 201 }
 202
 203 static void mmap_cache_context_set(MMapCache *m, unsigned c, unsigned w) {
 204         Window *v;
 205
 206         assert(m);
 207         assert(c < m->contexts_max);
 208         assert(w < m->n_windows);
 209
 210         if (m->by_context[c] == w)
 211                 return;
 212
 213         mmap_cache_context_unset(m, c);
 214
 215         m->by_context[c] = w;
 216
 217         v = m->windows + w;
 218         v->n_ref ++;
 219
 220         if (v->n_ref == 1)
 221                 mmap_cache_window_remove_lru(m, w);
 222 }
 223
 224 static void mmap_cache_free(MMapCache *m) {
 225
 226         assert(m);
 227
 228         if (m->windows) {
 229                 unsigned w;
 230
 231                 for (w = 0; w < m->n_windows; w++)
 232                         mmap_cache_window_unmap(m, w);
 233
 234                 free(m->windows);
 235         }
 236
 237         free(m->by_context);
 238         free(m->by_fd);
 239         free(m);
 240 }
 241
 242 MMapCache* mmap_cache_new(void) {
 243         MMapCache *m;
 244
 245         m = new0(MMapCache, 1);
 246         if (!m)
 247                 return NULL;
 248
 249         m->contexts_max = DEFAULT_CONTEXTS_MAX;
 250         m->fds_max = DEFAULT_FDS_MAX;
 251         m->windows_max = DEFAULT_WINDOWS_MAX;
 252         m->n_ref = 1;
 253         m->lru_first = (unsigned) -1;
 254         m->lru_last = (unsigned) -1;
 255
 256         m->windows = new(Window, m->windows_max);
 257         if (!m->windows) {
 258                 mmap_cache_free(m);
 259                 return NULL;
 260         }
 261
 262         m->by_context = new(unsigned, m->contexts_max);
 263         if (!m->by_context) {
 264                 mmap_cache_free(m);
 265                 return NULL;
 266         }
 267         memset(m->by_context, -1, m->contexts_max * sizeof(unsigned));
 268
 269         m->by_fd = new(FileDescriptor, m->fds_max);
 270         if (!m->by_fd) {
 271                 mmap_cache_free(m);
 272                 return NULL;
 273         }
 274
 275         return m;
 276 }
 277
 278 MMapCache* mmap_cache_ref(MMapCache *m) {
 279         assert(m);
 280         assert(m->n_ref > 0);
 281
 282         m->n_ref++;
 283         return m;
 284 }
 285
 286 MMapCache* mmap_cache_unref(MMapCache *m) {
 287         assert(m);
 288         assert(m->n_ref > 0);
 289
 290         if (m->n_ref == 1)
 291                 mmap_cache_free(m);
 292         else
 293                 m->n_ref--;
 294
 295         return NULL;
 296 }
 297
 298 static int mmap_cache_allocate_window(MMapCache *m, unsigned *w) {
 299         Window *v;
 300         unsigned fd_index;
 301
 302         assert(m);
 303         assert(w);
 304
 305         if (m->n_windows < m->windows_max) {
 306                 *w = m->n_windows ++;
 307                 return 0;
 308         }
 309
 310         if (m->lru_first == (unsigned) -1)
 311                 return -E2BIG;
 312
 313         *w = m->lru_first;
 314         v = m->windows + *w;
 315         assert(v->n_ref == 0);
 316
 317         mmap_cache_window_unmap(m, *w);
 318
 319         if (v->fd >= 0) {
 320                 assert_se(mmap_cache_peek_fd_index(m, v->fd, &fd_index) > 0);
 321                 mmap_cache_fd_remove(m, fd_index, *w);
 322         }
 323
 324         mmap_cache_window_remove_lru(m, *w);
 325
 326         return 0;
 327 }
 328
 329 static int mmap_cache_make_room(MMapCache *m) {
 330         unsigned w;
 331
 332         assert(m);
 333
 334         w = m->lru_first;
 335         while (w != (unsigned) -1) {
 336                 Window *v;
 337
 338                 v = m->windows + w;
 339                 assert(v->n_ref == 0);
 340
 341                 if (v->ptr) {
 342                         mmap_cache_window_unmap(m, w);
 343                         return 1;
 344                 }
 345
 346                 w = v->lru_next;
 347         }
 348
 349         return 0;
 350 }
 351
 352 static int mmap_cache_put(
 353                 MMapCache *m,
 354                 int fd,
 355                 unsigned fd_index,
 356                 int prot,
 357                 unsigned context,
 358                 bool keep_always,
 359                 uint64_t offset,
 360                 uint64_t size,
 361                 struct stat *st,
 362                 void **ret) {
 363
 364         unsigned w;
 365         Window *v;
 366         void *d;
 367         uint64_t woffset, wsize;
 368         int r;
 369
 370         assert(m);
 371         assert(fd >= 0);
 372         assert(context < m->contexts_max);
 373         assert(size > 0);
 374         assert(ret);
 375
 376         woffset = offset & ~((uint64_t) page_size() - 1ULL);
 377         wsize = size + (offset - woffset);
 378         wsize = PAGE_ALIGN(wsize);
 379
 380         if (wsize < WINDOW_SIZE) {
 381                 uint64_t delta;
 382
 383                 delta = PAGE_ALIGN((WINDOW_SIZE - wsize) / 2);
 384
 385                 if (delta > offset)
 386                         woffset = 0;
 387                 else
 388                         woffset -= delta;
 389
 390                 wsize = WINDOW_SIZE;
 391         }
 392
 393         if (st) {
 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 */
 397
 398                 if (woffset >= (uint64_t) st->st_size)
 399                         return -EADDRNOTAVAIL;
 400
 401                 if (woffset + wsize > (uint64_t) st->st_size)
 402                         wsize = PAGE_ALIGN(st->st_size - woffset);
 403         }
 404
 405         for (;;) {
 406                 d = mmap(NULL, wsize, prot, MAP_SHARED, fd, woffset);
 407                 if (d != MAP_FAILED)
 408                         break;
 409                 if (errno != ENOMEM)
 410                         return -errno;
 411
 412                 r = mmap_cache_make_room(m);
 413                 if (r < 0)
 414                         return r;
 415                 if (r == 0)
 416                         return -ENOMEM;
 417         }
 418
 419         r = mmap_cache_allocate_window(m, &w);
 420         if (r < 0) {
 421                 munmap(d, wsize);
 422                 return r;
 423         }
 424
 425         v = m->windows + w;
 426         v->fd = fd;
 427         v->ptr = d;
 428         v->offset = woffset;
 429         v->size = wsize;
 430
 431         if (keep_always)
 432                 v->n_ref = 1;
 433         else {
 434                 v->n_ref = 0;
 435                 mmap_cache_window_add_lru(m, w);
 436         }
 437
 438         mmap_cache_fd_add(m, fd_index, w);
 439         mmap_cache_context_set(m, context, w);
 440
 441         *ret = (uint8_t*) d + (offset - woffset);
 442         return 1;
 443 }
 444
 445 static int fd_cmp(const void *_a, const void *_b) {
 446         const FileDescriptor *a = _a, *b = _b;
 447
 448         if (a->fd < b->fd)
 449                 return -1;
 450         if (a->fd > b->fd)
 451                 return 1;
 452
 453         return 0;
 454 }
 455
 456 static int mmap_cache_peek_fd_index(MMapCache *m, int fd, unsigned *fd_index) {
 457         FileDescriptor *j;
 458         unsigned r;
 459
 460         assert(m);
 461         assert(fd >= 0);
 462         assert(fd_index);
 463
 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);
 467
 468         j = bsearch(&fd, m->by_fd, m->n_fds, sizeof(FileDescriptor), fd_cmp);
 469         if (!j)
 470                 return 0;
 471
 472         *fd_index = (unsigned) (j - m->by_fd);
 473         return 1;
 474 }
 475
 476 static int mmap_cache_get_fd_index(MMapCache *m, int fd, unsigned *fd_index) {
 477         FileDescriptor *j;
 478         int r;
 479
 480         assert(m);
 481         assert(fd >= 0);
 482         assert(fd_index);
 483
 484         r = mmap_cache_peek_fd_index(m, fd, fd_index);
 485         if (r != 0)
 486                 return r;
 487
 488         if (m->n_fds >= m->fds_max) {
 489                 unsigned k;
 490                 FileDescriptor *n;
 491
 492                 k = m->n_fds * 2;
 493                 n = realloc(m->by_fd, sizeof(FileDescriptor) * k);
 494                 if (!n)
 495                         return -ENOMEM;
 496
 497                 m->fds_max = k;
 498                 m->by_fd = n;
 499         }
 500
 501         j = m->by_fd + m->n_fds ++;
 502         j->fd = fd;
 503         j->windows = (unsigned) -1;
 504
 505         qsort(m->by_fd, m->n_fds, sizeof(FileDescriptor), fd_cmp);
 506
 507         return mmap_cache_peek_fd_index(m, fd, fd_index);
 508 }
 509
 510 static bool mmap_cache_test_window(
 511                 MMapCache *m,
 512                 unsigned w,
 513                 uint64_t offset,
 514                 uint64_t size) {
 515         Window *v;
 516
 517         assert(m);
 518         assert(w < m->n_windows);
 519         assert(size > 0);
 520
 521         v = m->windows + w;
 522
 523         return offset >= v->offset &&
 524                 offset + size <= v->offset + v->size;
 525 }
 526
 527 static int mmap_cache_current(
 528                 MMapCache *m,
 529                 int fd,
 530                 unsigned context,
 531                 uint64_t offset,
 532                 uint64_t size,
 533                 void **ret) {
 534
 535         Window *v;
 536         unsigned w;
 537
 538         assert(m);
 539         assert(fd >= 0);
 540         assert(context < m->contexts_max);
 541         assert(size > 0);
 542         assert(ret);
 543
 544         if (m->by_context[context] == (unsigned) -1)
 545                 return 0;
 546
 547         w = m->by_context[context];
 548         v = m->windows + w;
 549
 550         if (v->fd != fd)
 551                 return 0;
 552
 553         if (!mmap_cache_test_window(m, w, offset, size))
 554                 return 0;
 555
 556         *ret = (uint8_t*) v->ptr + (offset - v->offset);
 557         return 1;
 558 }
 559
 560 static int mmap_cache_find(
 561                 MMapCache *m,
 562                 int fd,
 563                 unsigned fd_index,
 564                 unsigned context,
 565                 uint64_t offset,
 566                 uint64_t size,
 567                 void **ret) {
 568
 569         Window *v = NULL;
 570         unsigned w;
 571
 572         assert(m);
 573         assert(fd >= 0);
 574         assert(fd_index < m->n_fds);
 575         assert(context < m->contexts_max);
 576         assert(size > 0);
 577         assert(ret);
 578
 579         w = m->by_fd[fd_index].windows;
 580         while (w != (unsigned) -1) {
 581                 v = m->windows + w;
 582                 assert(v->fd == fd);
 583
 584                 if (mmap_cache_test_window(m, w, offset, size))
 585                         break;
 586
 587                 w = v->by_fd_next;
 588         }
 589
 590         if (w == (unsigned) -1)
 591                 return 0;
 592
 593         mmap_cache_context_set(m, context, w);
 594
 595         *ret = (uint8_t*) v->ptr + (offset - v->offset);
 596         return 1;
 597 }
 598
 599 int mmap_cache_get(
 600                 MMapCache *m,
 601                 int fd,
 602                 int prot,
 603                 unsigned context,
 604                 bool keep_always,
 605                 uint64_t offset,
 606                 uint64_t size,
 607                 struct stat *st,
 608                 void **ret) {
 609
 610         unsigned fd_index;
 611         int r;
 612
 613         assert(m);
 614         assert(fd >= 0);
 615         assert(size > 0);
 616         assert(ret);
 617
 618         if (context >= m->contexts_max) {
 619                 unsigned k, *n;
 620                 Window *w;
 621
 622                 /* Increase the number of contexts if necessary, and
 623                  * make sure we have twice the number of windows */
 624
 625                 k = context * 2;
 626                 n = realloc(m->by_context, sizeof(unsigned) * k);
 627                 if (!n)
 628                         return -ENOMEM;
 629                 memset(n + m->contexts_max, -1, (k - m->contexts_max) * sizeof(unsigned));
 630                 m->contexts_max = k;
 631                 m->by_context = n;
 632
 633                 k = MAX(m->windows_max, m->contexts_max*2);
 634                 w = realloc(m->windows, sizeof(Window) * k);
 635                 if (!w)
 636                         return -ENOMEM;
 637
 638                 m->windows_max = k;
 639                 m->windows = w;
 640         }
 641
 642         /* Maybe the current pointer for this context is already the
 643          * right one? */
 644         r = mmap_cache_current(m, fd, context, offset, size, ret);
 645         if (r != 0)
 646                 return r;
 647
 648         /* Hmm, drop the reference to the current one, since it wasn't
 649          * good enough */
 650         mmap_cache_context_unset(m, context);
 651
 652         /* OK, let's find the chain for this FD */
 653         r = mmap_cache_get_fd_index(m, fd, &fd_index);
 654         if (r < 0)
 655                 return r;
 656
 657         /* And let's look through the available mmaps */
 658         r = mmap_cache_find(m, fd, fd_index, context, offset, size, ret);
 659         if (r != 0)
 660                 return r;
 661
 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);
 664 }
 665
 666 void mmap_cache_close_fd(MMapCache *m, int fd) {
 667         unsigned fd_index, c, w;
 668         int r;
 669
 670         assert(m);
 671         assert(fd > 0);
 672
 673         r = mmap_cache_peek_fd_index(m, fd, &fd_index);
 674         if (r <= 0)
 675                 return;
 676
 677         for (c = 0; c < m->contexts_max; c++) {
 678                 w = m->by_context[c];
 679                 if (w == (unsigned) -1)
 680                         continue;
 681
 682                 if (m->windows[w].fd == fd)
 683                         mmap_cache_context_unset(m, c);
 684         }
 685
 686         w = m->by_fd[fd_index].windows;
 687         while (w != (unsigned) -1) {
 688                 Window *v;
 689
 690                 v = m->windows + w;
 691                 assert(v->fd == fd);
 692
 693                 mmap_cache_window_unmap(m, w);
 694                 mmap_cache_fd_remove(m, fd_index, w);
 695                 v->fd = -1;
 696
 697                 w = m->by_fd[fd_index].windows;
 698         }
 699
 700         memmove(m->by_fd + fd_index, m->by_fd + fd_index + 1, (m->n_fds - (fd_index + 1)) * sizeof(FileDescriptor));
 701         m->n_fds --;
 702 }
 703
 704 void mmap_cache_close_context(MMapCache *m, unsigned context) {
 705         mmap_cache_context_unset(m, context);
 706 }