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         memset(m->by_context, -1, m->contexts_max * sizeof(unsigned));
 236
 237         m->by_fd = new(FileDescriptor, m->fds_max);
 238         if (!m->by_fd) {
 239                 mmap_cache_free(m);
 240                 return NULL;
 241         }
 242
 243         return m;
 244 }
 245
 246 MMapCache* mmap_cache_ref(MMapCache *m) {
 247         assert(m);
 248         assert(m->n_ref > 0);
 249
 250         m->n_ref++;
 251         return m;
 252 }
 253
 254 MMapCache* mmap_cache_unref(MMapCache *m) {
 255         assert(m);
 256         assert(m->n_ref > 0);
 257
 258         if (m->n_ref == 1)
 259                 mmap_cache_free(m);
 260         else
 261                 m->n_ref--;
 262
 263         return NULL;
 264 }
 265
 266 static int mmap_cache_allocate_window(MMapCache *m, unsigned *w) {
 267         assert(m);
 268         assert(w);
 269
 270         if (m->n_windows < m->windows_max) {
 271                 *w = m->n_windows ++;
 272                 return 0;
 273         }
 274
 275         if (m->lru_first == (unsigned) -1)
 276                 return -E2BIG;
 277
 278         *w = m->lru_first;
 279         mmap_cache_window_unmap(m, *w);
 280         mmap_cache_window_remove_lru(m, *w);
 281
 282         return 0;
 283 }
 284
 285 static int mmap_cache_make_room(MMapCache *m) {
 286         unsigned w;
 287
 288         assert(m);
 289
 290         w = m->lru_first;
 291         while (w != (unsigned) -1) {
 292                 Window *v;
 293
 294                 v = m->windows + w;
 295
 296                 if (v->ptr) {
 297                         mmap_cache_window_unmap(m, w);
 298                         return 1;
 299                 }
 300
 301                 w = v->lru_next;
 302         }
 303
 304         return 0;
 305 }
 306
 307 static int mmap_cache_put(
 308                 MMapCache *m,
 309                 int fd,
 310                 unsigned fd_index,
 311                 int prot,
 312                 unsigned context,
 313                 uint64_t offset,
 314                 uint64_t size,
 315                 void **ret) {
 316
 317         unsigned w;
 318         Window *v;
 319         void *d;
 320         uint64_t woffset, wsize;
 321         int r;
 322
 323         assert(m);
 324         assert(fd >= 0);
 325         assert(context < m->contexts_max);
 326         assert(size > 0);
 327         assert(ret);
 328
 329         woffset = offset & ~((uint64_t) page_size() - 1ULL);
 330         wsize = size + (offset - woffset);
 331         wsize = PAGE_ALIGN(wsize);
 332
 333         if (wsize < WINDOW_SIZE) {
 334                 uint64_t delta;
 335
 336                 delta = PAGE_ALIGN((WINDOW_SIZE - wsize) / 2);
 337
 338                 if (delta > offset)
 339                         woffset = 0;
 340                 else
 341                         woffset -= delta;
 342
 343                 wsize = WINDOW_SIZE;
 344         }
 345
 346         for (;;) {
 347                 d = mmap(NULL, wsize, prot, MAP_SHARED, fd, woffset);
 348                 if (d != MAP_FAILED)
 349                         break;
 350                 if (errno != ENOMEM)
 351                         return -errno;
 352
 353                 r = mmap_cache_make_room(m);
 354                 if (r < 0)
 355                         return r;
 356                 if (r == 0)
 357                         return -ENOMEM;
 358         }
 359
 360         r = mmap_cache_allocate_window(m, &w);
 361         if (r < 0) {
 362                 munmap(d, wsize);
 363                 return r;
 364         }
 365
 366         v = m->windows + w;
 367         v->fd = fd;
 368         v->ptr = d;
 369         v->offset = woffset;
 370         v->size = wsize;
 371
 372         v->n_ref = 0;
 373         v->lru_prev = v->lru_next = (unsigned) -1;
 374
 375         mmap_cache_fd_add(m, fd_index, w);
 376         mmap_cache_context_set(m, context, w);
 377
 378         *ret = (uint8_t*) d + (offset - woffset);
 379         return 1;
 380 }
 381
 382 static int fd_cmp(const void *_a, const void *_b) {
 383         const FileDescriptor *a = _a, *b = _b;
 384
 385         if (a->fd < b->fd)
 386                 return -1;
 387         if (a->fd > b->fd)
 388                 return 1;
 389
 390         return 0;
 391 }
 392
 393 static int mmap_cache_get_fd_index(MMapCache *m, int fd, unsigned *fd_index) {
 394         FileDescriptor *j;
 395
 396         assert(m);
 397         assert(fd >= 0);
 398         assert(fd_index);
 399
 400         j = bsearch(&fd, m->by_fd, m->n_fds, sizeof(m->by_fd[0]), fd_cmp);
 401         if (!j) {
 402                 if (m->n_fds >= m->fds_max)
 403                         return -E2BIG;
 404
 405                 j = m->by_fd + m->n_fds ++;
 406                 j->fd = fd;
 407                 j->windows = (unsigned) -1;
 408
 409                 qsort(m->by_fd, m->n_fds, sizeof(m->by_fd[0]), fd_cmp);
 410                 j = bsearch(&fd, m->by_fd, m->n_fds, sizeof(m->by_fd[0]), fd_cmp);
 411         }
 412
 413         *fd_index = (unsigned) (j - m->by_fd);
 414         return 0;
 415 }
 416
 417 static bool mmap_cache_test_window(
 418                 MMapCache *m,
 419                 unsigned w,
 420                 uint64_t offset,
 421                 uint64_t size) {
 422         Window *v;
 423
 424         assert(m);
 425         assert(w < m->n_windows);
 426         assert(size > 0);
 427
 428         v = m->windows + w;
 429
 430         return offset >= v->offset &&
 431                 offset + size <= v->offset + v->size;
 432 }
 433
 434 static int mmap_cache_current(
 435                 MMapCache *m,
 436                 int fd,
 437                 unsigned context,
 438                 uint64_t offset,
 439                 uint64_t size,
 440                 void **ret) {
 441
 442         Window *v;
 443         unsigned w;
 444
 445         assert(m);
 446         assert(fd >= 0);
 447         assert(context < m->contexts_max);
 448         assert(size > 0);
 449         assert(ret);
 450
 451         if (m->by_context[context] == (unsigned) -1)
 452                 return 0;
 453
 454         w = m->by_context[context];
 455         v = m->windows + w;
 456
 457         if (v->fd != fd)
 458                 return 0;
 459
 460         if (!mmap_cache_test_window(m, w, offset, size))
 461                 return 0;
 462
 463         *ret = (uint8_t*) v->ptr + (offset - v->offset);
 464         return 1;
 465 }
 466
 467 static int mmap_cache_find(
 468                 MMapCache *m,
 469                 unsigned fd_index,
 470                 unsigned context,
 471                 uint64_t offset,
 472                 uint64_t size,
 473                 void **ret) {
 474
 475         Window *v = NULL;
 476         unsigned w;
 477
 478         assert(m);
 479         assert(fd_index < m->n_fds);
 480         assert(context < m->contexts_max);
 481         assert(size > 0);
 482         assert(ret);
 483
 484         w = m->by_fd[fd_index].windows;
 485         while (w != (unsigned) -1) {
 486                 if (mmap_cache_test_window(m, w, offset, size))
 487                         break;
 488
 489                 w = m->windows[w].by_fd_next;
 490         }
 491
 492         if (w == (unsigned) -1)
 493                 return 0;
 494
 495         mmap_cache_context_set(m, context, w);
 496
 497         v = m->windows + w;
 498         *ret = (uint8_t*) v->ptr + (offset - v->offset);
 499         return 1;
 500 }
 501
 502 int mmap_cache_get(
 503                 MMapCache *m,
 504                 int fd,
 505                 int prot,
 506                 unsigned context,
 507                 uint64_t offset,
 508                 uint64_t size,
 509                 void **ret) {
 510
 511         unsigned fd_index;
 512         int r;
 513
 514         assert(m);
 515         assert(fd >= 0);
 516         assert(context < m->contexts_max);
 517         assert(size > 0);
 518         assert(ret);
 519
 520         /* Maybe the current pointer for this context is already the
 521          * right one? */
 522         r = mmap_cache_current(m, fd, context, offset, size, ret);
 523         if (r != 0)
 524                 return r;
 525
 526         /* OK, let's find the chain for this FD */
 527         r = mmap_cache_get_fd_index(m, fd, &fd_index);
 528         if (r < 0)
 529                 return r;
 530
 531         /* And let's look through the available mmaps */
 532         r = mmap_cache_find(m, fd_index, context, offset, size, ret);
 533         if (r != 0)
 534                 return r;
 535
 536         /* Not found? Then, let's add it */
 537         return mmap_cache_put(m, fd, fd_index, prot, context, offset, size, ret);
 538 }
 539
 540 void mmap_cache_close_fd(MMapCache *m, int fd) {
 541         FileDescriptor *j;
 542         unsigned fd_index, c, w;
 543
 544         assert(m);
 545         assert(fd > 0);
 546
 547         j = bsearch(&fd, m->by_fd, m->n_fds, sizeof(m->by_fd[0]), fd_cmp);
 548         if (!j)
 549                 return;
 550         fd_index = (unsigned) (j - m->by_fd);
 551
 552         for (c = 0; c < m->contexts_max; c++) {
 553                 w = m->by_context[c];
 554                 if (w == (unsigned) -1)
 555                         continue;
 556
 557                 if (m->windows[w].fd == fd)
 558                         mmap_cache_context_unset(m, c);
 559         }
 560
 561         w = m->by_fd[fd_index].windows;
 562         while (w != (unsigned) -1) {
 563
 564                 mmap_cache_fd_remove(m, fd_index, w);
 565                 mmap_cache_window_unmap(m, w);
 566
 567                 w = m->by_fd[fd_index].windows;
 568         }
 569
 570         memmove(m->by_fd + fd_index, m->by_fd + fd_index + 1, (m->n_fds - (fd_index + 1)) * sizeof(FileDescriptor));
 571         m->n_fds --;
 572 }
 573
 574 void mmap_cache_close_context(MMapCache *m, unsigned context) {
 575         mmap_cache_context_unset(m, context);
 576 }