src/journal/journal-file.c

   1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
   2
   3 /***
   4   This file is part of systemd.
   5
   6   Copyright 2011 Lennart Poettering
   7
   8   systemd is free software; you can redistribute it and/or modify it
   9   under the terms of the GNU General Public License as published by
  10   the Free Software Foundation; either version 2 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   General Public License for more details.
  17
  18   You should have received a copy of the GNU General Public License
  19   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  20 ***/
  21
  22 #include <sys/mman.h>
  23 #include <errno.h>
  24 #include <sys/uio.h>
  25 #include <unistd.h>
  26 #include <sys/statvfs.h>
  27 #include <fcntl.h>
  28 #include <stddef.h>
  29
  30 #include "journal-def.h"
  31 #include "journal-file.h"
  32 #include "lookup3.h"
  33 #include "compress.h"
  34
  35 #define DEFAULT_DATA_HASH_TABLE_SIZE (2047ULL*16ULL)
  36 #define DEFAULT_FIELD_HASH_TABLE_SIZE (2047ULL*16ULL)
  37
  38 #define DEFAULT_WINDOW_SIZE (128ULL*1024ULL*1024ULL)
  39
  40 #define COMPRESSION_SIZE_THRESHOLD (64ULL)
  41
  42 static const char signature[] = { 'L', 'P', 'K', 'S', 'H', 'H', 'R', 'H' };
  43
  44 #define ALIGN64(x) (((x) + 7ULL) & ~7ULL)
  45
  46 void journal_file_close(JournalFile *f) {
  47         int t;
  48
  49         assert(f);
  50
  51         if (f->header && f->writable)
  52                 f->header->state = STATE_OFFLINE;
  53
  54
  55         for (t = 0; t < _WINDOW_MAX; t++)
  56                 if (f->windows[t].ptr)
  57                         munmap(f->windows[t].ptr, f->windows[t].size);
  58
  59         if (f->fd >= 0)
  60                 close_nointr_nofail(f->fd);
  61
  62         free(f->path);
  63
  64 #ifdef HAVE_XZ
  65         free(f->compress_buffer);
  66 #endif
  67
  68         free(f);
  69 }
  70
  71 static int journal_file_init_header(JournalFile *f, JournalFile *template) {
  72         Header h;
  73         ssize_t k;
  74         int r;
  75
  76         assert(f);
  77
  78         zero(h);
  79         memcpy(h.signature, signature, 8);
  80         h.arena_offset = htole64(ALIGN64(sizeof(h)));
  81
  82         r = sd_id128_randomize(&h.file_id);
  83         if (r < 0)
  84                 return r;
  85
  86         if (template) {
  87                 h.seqnum_id = template->header->seqnum_id;
  88                 h.seqnum = template->header->seqnum;
  89         } else
  90                 h.seqnum_id = h.file_id;
  91
  92         k = pwrite(f->fd, &h, sizeof(h), 0);
  93         if (k < 0)
  94                 return -errno;
  95
  96         if (k != sizeof(h))
  97                 return -EIO;
  98
  99         return 0;
 100 }
 101
 102 static int journal_file_refresh_header(JournalFile *f) {
 103         int r;
 104         sd_id128_t boot_id;
 105
 106         assert(f);
 107
 108         r = sd_id128_get_machine(&f->header->machine_id);
 109         if (r < 0)
 110                 return r;
 111
 112         r = sd_id128_get_boot(&boot_id);
 113         if (r < 0)
 114                 return r;
 115
 116         if (sd_id128_equal(boot_id, f->header->boot_id))
 117                 f->tail_entry_monotonic_valid = true;
 118
 119         f->header->boot_id = boot_id;
 120
 121         f->header->state = STATE_ONLINE;
 122         return 0;
 123 }
 124
 125 static int journal_file_verify_header(JournalFile *f) {
 126         assert(f);
 127
 128         if (memcmp(f->header, signature, 8))
 129                 return -EBADMSG;
 130
 131 #ifdef HAVE_XZ
 132         if ((le64toh(f->header->incompatible_flags) & ~HEADER_INCOMPATIBLE_COMPRESSED) != 0)
 133                 return -EPROTONOSUPPORT;
 134 #else
 135         if (f->header->incompatible_flags != 0)
 136                 return -EPROTONOSUPPORT;
 137 #endif
 138
 139         if ((uint64_t) f->last_stat.st_size < (le64toh(f->header->arena_offset) + le64toh(f->header->arena_size)))
 140                 return -ENODATA;
 141
 142         if (f->writable) {
 143                 uint32_t state;
 144                 sd_id128_t machine_id;
 145                 int r;
 146
 147                 r = sd_id128_get_machine(&machine_id);
 148                 if (r < 0)
 149                         return r;
 150
 151                 if (!sd_id128_equal(machine_id, f->header->machine_id))
 152                         return -EHOSTDOWN;
 153
 154                 state = f->header->state;
 155
 156                 if (state == STATE_ONLINE)
 157                         log_debug("Journal file %s is already online. Assuming unclean closing. Ignoring.", f->path);
 158                 else if (state == STATE_ARCHIVED)
 159                         return -ESHUTDOWN;
 160                 else if (state != STATE_OFFLINE)
 161                         log_debug("Journal file %s has unknown state %u. Ignoring.", f->path, state);
 162         }
 163
 164         return 0;
 165 }
 166
 167 static int journal_file_allocate(JournalFile *f, uint64_t offset, uint64_t size) {
 168         uint64_t old_size, new_size;
 169
 170         assert(f);
 171
 172         /* We assume that this file is not sparse, and we know that
 173          * for sure, since we always call posix_fallocate()
 174          * ourselves */
 175
 176         old_size =
 177                 le64toh(f->header->arena_offset) +
 178                 le64toh(f->header->arena_size);
 179
 180         new_size = PAGE_ALIGN(offset + size);
 181         if (new_size < le64toh(f->header->arena_offset))
 182                 new_size = le64toh(f->header->arena_offset);
 183
 184         if (new_size <= old_size)
 185                 return 0;
 186
 187         if (f->metrics.max_size > 0 &&
 188             new_size > f->metrics.max_size)
 189                 return -E2BIG;
 190
 191         if (new_size > f->metrics.min_size &&
 192             f->metrics.keep_free > 0) {
 193                 struct statvfs svfs;
 194
 195                 if (fstatvfs(f->fd, &svfs) >= 0) {
 196                         uint64_t available;
 197
 198                         available = svfs.f_bfree * svfs.f_bsize;
 199
 200                         if (available >= f->metrics.keep_free)
 201                                 available -= f->metrics.keep_free;
 202                         else
 203                                 available = 0;
 204
 205                         if (new_size - old_size > available)
 206                                 return -E2BIG;
 207                 }
 208         }
 209
 210         /* Note that the glibc fallocate() fallback is very
 211            inefficient, hence we try to minimize the allocation area
 212            as we can. */
 213         if (posix_fallocate(f->fd, old_size, new_size - old_size) < 0)
 214                 return -errno;
 215
 216         if (fstat(f->fd, &f->last_stat) < 0)
 217                 return -errno;
 218
 219         f->header->arena_size = new_size - htole64(f->header->arena_offset);
 220
 221         return 0;
 222 }
 223
 224 static int journal_file_map(
 225                 JournalFile *f,
 226                 uint64_t offset,
 227                 uint64_t size,
 228                 void **_window,
 229                 uint64_t *_woffset,
 230                 uint64_t *_wsize,
 231                 void **ret) {
 232
 233         uint64_t woffset, wsize;
 234         void *window;
 235
 236         assert(f);
 237         assert(size > 0);
 238         assert(ret);
 239
 240         woffset = offset & ~((uint64_t) page_size() - 1ULL);
 241         wsize = size + (offset - woffset);
 242         wsize = PAGE_ALIGN(wsize);
 243
 244         window = mmap(NULL, wsize, f->prot, MAP_SHARED, f->fd, woffset);
 245         if (window == MAP_FAILED)
 246                 return -errno;
 247
 248         if (_window)
 249                 *_window = window;
 250
 251         if (_woffset)
 252                 *_woffset = woffset;
 253
 254         if (_wsize)
 255                 *_wsize = wsize;
 256
 257         *ret = (uint8_t*) window + (offset - woffset);
 258
 259         return 0;
 260 }
 261
 262 static int journal_file_move_to(JournalFile *f, int wt, uint64_t offset, uint64_t size, void **ret) {
 263         void *p;
 264         uint64_t delta;
 265         int r;
 266         Window *w;
 267
 268         assert(f);
 269         assert(ret);
 270         assert(wt >= 0);
 271         assert(wt < _WINDOW_MAX);
 272
 273         w = f->windows + wt;
 274
 275         if (_likely_(w->ptr &&
 276                      w->offset <= offset &&
 277                      w->offset + w->size >= offset + size)) {
 278
 279                 *ret = (uint8_t*) w->ptr + (offset - w->offset);
 280                 return 0;
 281         }
 282
 283         if (w->ptr) {
 284                 if (munmap(w->ptr, w->size) < 0)
 285                         return -errno;
 286
 287                 w->ptr = NULL;
 288                 w->size = w->offset = 0;
 289         }
 290
 291         if (size < DEFAULT_WINDOW_SIZE) {
 292                 /* If the default window size is larger then what was
 293                  * asked for extend the mapping a bit in the hope to
 294                  * minimize needed remappings later on. We add half
 295                  * the window space before and half behind the
 296                  * requested mapping */
 297
 298                 delta = PAGE_ALIGN((DEFAULT_WINDOW_SIZE - size) / 2);
 299
 300                 if (offset < delta)
 301                         delta = offset;
 302
 303                 offset -= delta;
 304                 size += (DEFAULT_WINDOW_SIZE - delta);
 305         } else
 306                 delta = 0;
 307
 308         r = journal_file_map(f,
 309                              offset, size,
 310                              &w->ptr, &w->offset, &w->size,
 311                              &p);
 312
 313         if (r < 0)
 314                 return r;
 315
 316         *ret = (uint8_t*) p + delta;
 317         return 0;
 318 }
 319
 320 static bool verify_hash(Object *o) {
 321         uint64_t h1, h2;
 322
 323         assert(o);
 324
 325         if (o->object.type == OBJECT_DATA && !(o->object.flags & OBJECT_COMPRESSED)) {
 326                 h1 = le64toh(o->data.hash);
 327                 h2 = hash64(o->data.payload, le64toh(o->object.size) - offsetof(Object, data.payload));
 328         } else if (o->object.type == OBJECT_FIELD) {
 329                 h1 = le64toh(o->field.hash);
 330                 h2 = hash64(o->field.payload, le64toh(o->object.size) - offsetof(Object, field.payload));
 331         } else
 332                 return true;
 333
 334         return h1 == h2;
 335 }
 336
 337 int journal_file_move_to_object(JournalFile *f, int type, uint64_t offset, Object **ret) {
 338         int r;
 339         void *t;
 340         Object *o;
 341         uint64_t s;
 342
 343         assert(f);
 344         assert(ret);
 345         assert(type < _OBJECT_TYPE_MAX);
 346
 347         r = journal_file_move_to(f, type >= 0 ? type : WINDOW_UNKNOWN, offset, sizeof(ObjectHeader), &t);
 348         if (r < 0)
 349                 return r;
 350
 351         o = (Object*) t;
 352         s = le64toh(o->object.size);
 353
 354         if (s < sizeof(ObjectHeader))
 355                 return -EBADMSG;
 356
 357         if (type >= 0 && o->object.type != type)
 358                 return -EBADMSG;
 359
 360         if (s > sizeof(ObjectHeader)) {
 361                 r = journal_file_move_to(f, o->object.type, offset, s, &t);
 362                 if (r < 0)
 363                         return r;
 364
 365                 o = (Object*) t;
 366         }
 367
 368         if (!verify_hash(o))
 369                 return -EBADMSG;
 370
 371         *ret = o;
 372         return 0;
 373 }
 374
 375 static uint64_t journal_file_seqnum(JournalFile *f, uint64_t *seqnum) {
 376         uint64_t r;
 377
 378         assert(f);
 379
 380         r = le64toh(f->header->seqnum) + 1;
 381
 382         if (seqnum) {
 383                 /* If an external seqnum counter was passed, we update
 384                  * both the local and the external one, and set it to
 385                  * the maximum of both */
 386
 387                 if (*seqnum + 1 > r)
 388                         r = *seqnum + 1;
 389
 390                 *seqnum = r;
 391         }
 392
 393         f->header->seqnum = htole64(r);
 394
 395         if (f->header->first_seqnum == 0)
 396                 f->header->first_seqnum = htole64(r);
 397
 398         return r;
 399 }
 400
 401 static int journal_file_append_object(JournalFile *f, int type, uint64_t size, Object **ret, uint64_t *offset) {
 402         int r;
 403         uint64_t p;
 404         Object *tail, *o;
 405         void *t;
 406
 407         assert(f);
 408         assert(size >= sizeof(ObjectHeader));
 409         assert(offset);
 410         assert(ret);
 411
 412         p = le64toh(f->header->tail_object_offset);
 413         if (p == 0)
 414                 p = le64toh(f->header->arena_offset);
 415         else {
 416                 r = journal_file_move_to_object(f, -1, p, &tail);
 417                 if (r < 0)
 418                         return r;
 419
 420                 p += ALIGN64(le64toh(tail->object.size));
 421         }
 422
 423         r = journal_file_allocate(f, p, size);
 424         if (r < 0)
 425                 return r;
 426
 427         r = journal_file_move_to(f, type, p, size, &t);
 428         if (r < 0)
 429                 return r;
 430
 431         o = (Object*) t;
 432
 433         zero(o->object);
 434         o->object.type = type;
 435         o->object.size = htole64(size);
 436
 437         f->header->tail_object_offset = htole64(p);
 438         f->header->n_objects = htole64(le64toh(f->header->n_objects) + 1);
 439
 440         *ret = o;
 441         *offset = p;
 442
 443         return 0;
 444 }
 445
 446 static int journal_file_setup_data_hash_table(JournalFile *f) {
 447         uint64_t s, p;
 448         Object *o;
 449         int r;
 450
 451         assert(f);
 452
 453         s = DEFAULT_DATA_HASH_TABLE_SIZE;
 454         r = journal_file_append_object(f,
 455                                        OBJECT_DATA_HASH_TABLE,
 456                                        offsetof(Object, hash_table.items) + s,
 457                                        &o, &p);
 458         if (r < 0)
 459                 return r;
 460
 461         memset(o->hash_table.items, 0, s);
 462
 463         f->header->data_hash_table_offset = htole64(p + offsetof(Object, hash_table.items));
 464         f->header->data_hash_table_size = htole64(s);
 465
 466         return 0;
 467 }
 468
 469 static int journal_file_setup_field_hash_table(JournalFile *f) {
 470         uint64_t s, p;
 471         Object *o;
 472         int r;
 473
 474         assert(f);
 475
 476         s = DEFAULT_FIELD_HASH_TABLE_SIZE;
 477         r = journal_file_append_object(f,
 478                                        OBJECT_FIELD_HASH_TABLE,
 479                                        offsetof(Object, hash_table.items) + s,
 480                                        &o, &p);
 481         if (r < 0)
 482                 return r;
 483
 484         memset(o->hash_table.items, 0, s);
 485
 486         f->header->field_hash_table_offset = htole64(p + offsetof(Object, hash_table.items));
 487         f->header->field_hash_table_size = htole64(s);
 488
 489         return 0;
 490 }
 491
 492 static int journal_file_map_data_hash_table(JournalFile *f) {
 493         uint64_t s, p;
 494         void *t;
 495         int r;
 496
 497         assert(f);
 498
 499         p = le64toh(f->header->data_hash_table_offset);
 500         s = le64toh(f->header->data_hash_table_size);
 501
 502         r = journal_file_move_to(f,
 503                                  WINDOW_DATA_HASH_TABLE,
 504                                  p, s,
 505                                  &t);
 506         if (r < 0)
 507                 return r;
 508
 509         f->data_hash_table = t;
 510         return 0;
 511 }
 512
 513 static int journal_file_map_field_hash_table(JournalFile *f) {
 514         uint64_t s, p;
 515         void *t;
 516         int r;
 517
 518         assert(f);
 519
 520         p = le64toh(f->header->field_hash_table_offset);
 521         s = le64toh(f->header->field_hash_table_size);
 522
 523         r = journal_file_move_to(f,
 524                                  WINDOW_FIELD_HASH_TABLE,
 525                                  p, s,
 526                                  &t);
 527         if (r < 0)
 528                 return r;
 529
 530         f->field_hash_table = t;
 531         return 0;
 532 }
 533
 534 static int journal_file_link_data(JournalFile *f, Object *o, uint64_t offset, uint64_t hash) {
 535         uint64_t p, h;
 536         int r;
 537
 538         assert(f);
 539         assert(o);
 540         assert(offset > 0);
 541         assert(o->object.type == OBJECT_DATA);
 542
 543         o->data.next_hash_offset = o->data.next_field_offset = 0;
 544         o->data.entry_offset = o->data.entry_array_offset = 0;
 545         o->data.n_entries = 0;
 546
 547         h = hash % (le64toh(f->header->data_hash_table_size) / sizeof(HashItem));
 548         p = le64toh(f->data_hash_table[h].head_hash_offset);
 549         if (p == 0) {
 550                 /* Only entry in the hash table is easy */
 551                 f->data_hash_table[h].head_hash_offset = htole64(offset);
 552         } else {
 553                 /* Temporarily move back to the previous data object,
 554                  * to patch in pointer */
 555
 556                 r = journal_file_move_to_object(f, OBJECT_DATA, p, &o);
 557                 if (r < 0)
 558                         return r;
 559
 560                 o->data.next_hash_offset = htole64(offset);
 561
 562                 r = journal_file_move_to_object(f, OBJECT_DATA, offset, &o);
 563                 if (r < 0)
 564                         return r;
 565         }
 566
 567         f->data_hash_table[h].tail_hash_offset = htole64(offset);
 568
 569         return 0;
 570 }
 571
 572 int journal_file_find_data_object_with_hash(
 573                 JournalFile *f,
 574                 const void *data, uint64_t size, uint64_t hash,
 575                 Object **ret, uint64_t *offset) {
 576         uint64_t p, osize, h;
 577         int r;
 578
 579         assert(f);
 580         assert(data || size == 0);
 581
 582         osize = offsetof(Object, data.payload) + size;
 583
 584         if (f->header->data_hash_table_size == 0)
 585                 return -EBADMSG;
 586
 587         h = hash % (le64toh(f->header->data_hash_table_size) / sizeof(HashItem));
 588         p = le64toh(f->data_hash_table[h].head_hash_offset);
 589
 590         while (p > 0) {
 591                 Object *o;
 592
 593                 r = journal_file_move_to_object(f, OBJECT_DATA, p, &o);
 594                 if (r < 0)
 595                         return r;
 596
 597                 if (le64toh(o->data.hash) != hash)
 598                         goto next;
 599
 600                 if (o->object.flags & OBJECT_COMPRESSED) {
 601 #ifdef HAVE_XZ
 602                         uint64_t l, rsize;
 603
 604                         l = le64toh(o->object.size);
 605                         if (l <= offsetof(Object, data.payload))
 606                                 return -EBADMSG;
 607
 608                         l -= offsetof(Object, data.payload);
 609
 610                         if (!uncompress_blob(o->data.payload, l, &f->compress_buffer, &f->compress_buffer_size, &rsize))
 611                                 return -EBADMSG;
 612
 613                         if (rsize == size &&
 614                             memcmp(f->compress_buffer, data, size) == 0) {
 615
 616                                 if (ret)
 617                                         *ret = o;
 618
 619                                 if (offset)
 620                                         *offset = p;
 621
 622                                 return 1;
 623                         }
 624 #else
 625                         return -EPROTONOSUPPORT;
 626 #endif
 627
 628                 } else if (le64toh(o->object.size) == osize &&
 629                            memcmp(o->data.payload, data, size) == 0) {
 630
 631                         if (ret)
 632                                 *ret = o;
 633
 634                         if (offset)
 635                                 *offset = p;
 636
 637                         return 1;
 638                 }
 639
 640         next:
 641                 p = le64toh(o->data.next_hash_offset);
 642         }
 643
 644         return 0;
 645 }
 646
 647 int journal_file_find_data_object(
 648                 JournalFile *f,
 649                 const void *data, uint64_t size,
 650                 Object **ret, uint64_t *offset) {
 651
 652         uint64_t hash;
 653
 654         assert(f);
 655         assert(data || size == 0);
 656
 657         hash = hash64(data, size);
 658
 659         return journal_file_find_data_object_with_hash(f,
 660                                                        data, size, hash,
 661                                                        ret, offset);
 662 }
 663
 664 static int journal_file_append_data(JournalFile *f, const void *data, uint64_t size, Object **ret, uint64_t *offset) {
 665         uint64_t hash, p;
 666         uint64_t osize;
 667         Object *o;
 668         int r;
 669         bool compressed = false;
 670
 671         assert(f);
 672         assert(data || size == 0);
 673
 674         hash = hash64(data, size);
 675
 676         r = journal_file_find_data_object_with_hash(f, data, size, hash, &o, &p);
 677         if (r < 0)
 678                 return r;
 679         else if (r > 0) {
 680
 681                 if (ret)
 682                         *ret = o;
 683
 684                 if (offset)
 685                         *offset = p;
 686
 687                 return 0;
 688         }
 689
 690         osize = offsetof(Object, data.payload) + size;
 691         r = journal_file_append_object(f, OBJECT_DATA, osize, &o, &p);
 692         if (r < 0)
 693                 return r;
 694
 695         o->data.hash = htole64(hash);
 696
 697 #ifdef HAVE_XZ
 698         if (f->compress &&
 699             size >= COMPRESSION_SIZE_THRESHOLD) {
 700                 uint64_t rsize;
 701
 702                 compressed = compress_blob(data, size, o->data.payload, &rsize);
 703
 704                 if (compressed) {
 705                         o->object.size = htole64(offsetof(Object, data.payload) + rsize);
 706                         o->object.flags |= OBJECT_COMPRESSED;
 707
 708                         f->header->incompatible_flags = htole32(le32toh(f->header->incompatible_flags) | HEADER_INCOMPATIBLE_COMPRESSED);
 709
 710                         log_debug("Compressed data object %lu -> %lu", (unsigned long) size, (unsigned long) rsize);
 711                 }
 712         }
 713 #endif
 714
 715         if (!compressed)
 716                 memcpy(o->data.payload, data, size);
 717
 718         r = journal_file_link_data(f, o, p, hash);
 719         if (r < 0)
 720                 return r;
 721
 722         if (ret)
 723                 *ret = o;
 724
 725         if (offset)
 726                 *offset = p;
 727
 728         return 0;
 729 }
 730
 731 uint64_t journal_file_entry_n_items(Object *o) {
 732         assert(o);
 733         assert(o->object.type == htole64(OBJECT_ENTRY));
 734
 735         return (le64toh(o->object.size) - offsetof(Object, entry.items)) / sizeof(EntryItem);
 736 }
 737
 738 static uint64_t journal_file_entry_array_n_items(Object *o) {
 739         assert(o);
 740         assert(o->object.type == htole64(OBJECT_ENTRY_ARRAY));
 741
 742         return (le64toh(o->object.size) - offsetof(Object, entry_array.items)) / sizeof(uint64_t);
 743 }
 744
 745 static int link_entry_into_array(JournalFile *f,
 746                                  uint64_t *first,
 747                                  uint64_t *idx,
 748                                  uint64_t p) {
 749         int r;
 750         uint64_t n = 0, ap = 0, q, i, a, hidx;
 751         Object *o;
 752
 753         assert(f);
 754         assert(first);
 755         assert(idx);
 756         assert(p > 0);
 757
 758         a = le64toh(*first);
 759         i = hidx = le64toh(*idx);
 760         while (a > 0) {
 761
 762                 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
 763                 if (r < 0)
 764                         return r;
 765
 766                 n = journal_file_entry_array_n_items(o);
 767                 if (i < n) {
 768                         o->entry_array.items[i] = htole64(p);
 769                         *idx = htole64(hidx + 1);
 770                         return 0;
 771                 }
 772
 773                 i -= n;
 774                 ap = a;
 775                 a = le64toh(o->entry_array.next_entry_array_offset);
 776         }
 777
 778         if (hidx > n)
 779                 n = (hidx+1) * 2;
 780         else
 781                 n = n * 2;
 782
 783         if (n < 4)
 784                 n = 4;
 785
 786         r = journal_file_append_object(f, OBJECT_ENTRY_ARRAY,
 787                                        offsetof(Object, entry_array.items) + n * sizeof(uint64_t),
 788                                        &o, &q);
 789         if (r < 0)
 790                 return r;
 791
 792         o->entry_array.items[i] = htole64(p);
 793
 794         if (ap == 0)
 795                 *first = q;
 796         else {
 797                 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, ap, &o);
 798                 if (r < 0)
 799                         return r;
 800
 801                 o->entry_array.next_entry_array_offset = htole64(q);
 802         }
 803
 804         *idx = htole64(hidx + 1);
 805
 806         return 0;
 807 }
 808
 809 static int link_entry_into_array_plus_one(JournalFile *f,
 810                                           uint64_t *extra,
 811                                           uint64_t *first,
 812                                           uint64_t *idx,
 813                                           uint64_t p) {
 814
 815         int r;
 816
 817         assert(f);
 818         assert(extra);
 819         assert(first);
 820         assert(idx);
 821         assert(p > 0);
 822
 823         if (*idx == 0)
 824                 *extra = htole64(p);
 825         else {
 826                 uint64_t i;
 827
 828                 i = le64toh(*idx) - 1;
 829                 r = link_entry_into_array(f, first, &i, p);
 830                 if (r < 0)
 831                         return r;
 832         }
 833
 834         *idx = htole64(le64toh(*idx) + 1);
 835         return 0;
 836 }
 837
 838 static int journal_file_link_entry_item(JournalFile *f, Object *o, uint64_t offset, uint64_t i) {
 839         uint64_t p;
 840         int r;
 841         assert(f);
 842         assert(o);
 843         assert(offset > 0);
 844
 845         p = le64toh(o->entry.items[i].object_offset);
 846         if (p == 0)
 847                 return -EINVAL;
 848
 849         r = journal_file_move_to_object(f, OBJECT_DATA, p, &o);
 850         if (r < 0)
 851                 return r;
 852
 853         return link_entry_into_array_plus_one(f,
 854                                               &o->data.entry_offset,
 855                                               &o->data.entry_array_offset,
 856                                               &o->data.n_entries,
 857                                               offset);
 858 }
 859
 860 static int journal_file_link_entry(JournalFile *f, Object *o, uint64_t offset) {
 861         uint64_t n, i;
 862         int r;
 863
 864         assert(f);
 865         assert(o);
 866         assert(offset > 0);
 867         assert(o->object.type == OBJECT_ENTRY);
 868
 869         /* Link up the entry itself */
 870         r = link_entry_into_array(f,
 871                                   &f->header->entry_array_offset,
 872                                   &f->header->n_entries,
 873                                   offset);
 874         if (r < 0)
 875                 return r;
 876
 877         log_error("=> %s seqnr=%lu n_entries=%lu", f->path, (unsigned long) o->entry.seqnum, (unsigned long) f->header->n_entries);
 878
 879         if (f->header->head_entry_realtime == 0)
 880                 f->header->head_entry_realtime = o->entry.realtime;
 881
 882         f->header->tail_entry_realtime = o->entry.realtime;
 883         f->header->tail_entry_monotonic = o->entry.monotonic;
 884
 885         f->tail_entry_monotonic_valid = true;
 886
 887         /* Link up the items */
 888         n = journal_file_entry_n_items(o);
 889         for (i = 0; i < n; i++) {
 890                 r = journal_file_link_entry_item(f, o, offset, i);
 891                 if (r < 0)
 892                         return r;
 893         }
 894
 895         return 0;
 896 }
 897
 898 static int journal_file_append_entry_internal(
 899                 JournalFile *f,
 900                 const dual_timestamp *ts,
 901                 uint64_t xor_hash,
 902                 const EntryItem items[], unsigned n_items,
 903                 uint64_t *seqnum,
 904                 Object **ret, uint64_t *offset) {
 905         uint64_t np;
 906         uint64_t osize;
 907         Object *o;
 908         int r;
 909
 910         assert(f);
 911         assert(items || n_items == 0);
 912         assert(ts);
 913
 914         osize = offsetof(Object, entry.items) + (n_items * sizeof(EntryItem));
 915
 916         r = journal_file_append_object(f, OBJECT_ENTRY, osize, &o, &np);
 917         if (r < 0)
 918                 return r;
 919
 920         o->entry.seqnum = htole64(journal_file_seqnum(f, seqnum));
 921         memcpy(o->entry.items, items, n_items * sizeof(EntryItem));
 922         o->entry.realtime = htole64(ts->realtime);
 923         o->entry.monotonic = htole64(ts->monotonic);
 924         o->entry.xor_hash = htole64(xor_hash);
 925         o->entry.boot_id = f->header->boot_id;
 926
 927         r = journal_file_link_entry(f, o, np);
 928         if (r < 0)
 929                 return r;
 930
 931         if (ret)
 932                 *ret = o;
 933
 934         if (offset)
 935                 *offset = np;
 936
 937         return 0;
 938 }
 939
 940 static void journal_file_post_change(JournalFile *f) {
 941         assert(f);
 942
 943         /* inotify() does not receive IN_MODIFY events from file
 944          * accesses done via mmap(). After each access we hence
 945          * trigger IN_MODIFY by truncating the journal file to its
 946          * current size which triggers IN_MODIFY. */
 947
 948         __sync_synchronize();
 949
 950         if (ftruncate(f->fd, f->last_stat.st_size) < 0)
 951                 log_error("Failed to to truncate file to its own size: %m");
 952 }
 953
 954 int journal_file_append_entry(JournalFile *f, const dual_timestamp *ts, const struct iovec iovec[], unsigned n_iovec, uint64_t *seqnum, Object **ret, uint64_t *offset) {
 955         unsigned i;
 956         EntryItem *items;
 957         int r;
 958         uint64_t xor_hash = 0;
 959         struct dual_timestamp _ts;
 960
 961         assert(f);
 962         assert(iovec || n_iovec == 0);
 963
 964         if (!f->writable)
 965                 return -EPERM;
 966
 967         if (!ts) {
 968                 dual_timestamp_get(&_ts);
 969                 ts = &_ts;
 970         }
 971
 972         if (f->tail_entry_monotonic_valid &&
 973             ts->monotonic < le64toh(f->header->tail_entry_monotonic))
 974                 return -EINVAL;
 975
 976         if (ts->realtime < le64toh(f->header->tail_entry_realtime))
 977                 return -EINVAL;
 978
 979         items = new(EntryItem, n_iovec);
 980         if (!items)
 981                 return -ENOMEM;
 982
 983         for (i = 0; i < n_iovec; i++) {
 984                 uint64_t p;
 985                 Object *o;
 986
 987                 r = journal_file_append_data(f, iovec[i].iov_base, iovec[i].iov_len, &o, &p);
 988                 if (r < 0)
 989                         goto finish;
 990
 991                 xor_hash ^= le64toh(o->data.hash);
 992                 items[i].object_offset = htole64(p);
 993                 items[i].hash = o->data.hash;
 994         }
 995
 996         r = journal_file_append_entry_internal(f, ts, xor_hash, items, n_iovec, seqnum, ret, offset);
 997
 998         journal_file_post_change(f);
 999
1000 finish:
1001         free(items);
1002
1003         return r;
1004 }
1005
1006 static int generic_array_get(JournalFile *f,
1007                              uint64_t first,
1008                              uint64_t i,
1009                              Object **ret, uint64_t *offset) {
1010
1011         Object *o;
1012         uint64_t p, a;
1013         int r;
1014
1015         assert(f);
1016
1017         a = first;
1018         while (a > 0) {
1019                 uint64_t n;
1020
1021                 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
1022                 if (r < 0)
1023                         return r;
1024
1025                 n = journal_file_entry_array_n_items(o);
1026                 if (i < n) {
1027                         p = le64toh(o->entry_array.items[i]);
1028                         break;
1029                 }
1030
1031                 i -= n;
1032                 a = le64toh(o->entry_array.next_entry_array_offset);
1033         }
1034
1035         if (a <= 0 || p <= 0)
1036                 return 0;
1037
1038         r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
1039         if (r < 0)
1040                 return r;
1041
1042         if (ret)
1043                 *ret = o;
1044
1045         if (offset)
1046                 *offset = p;
1047
1048         return 1;
1049 }
1050
1051 static int generic_array_get_plus_one(JournalFile *f,
1052                                       uint64_t extra,
1053                                       uint64_t first,
1054                                       uint64_t i,
1055                                       Object **ret, uint64_t *offset) {
1056
1057         Object *o;
1058
1059         assert(f);
1060
1061         if (i == 0) {
1062                 int r;
1063
1064                 r = journal_file_move_to_object(f, OBJECT_ENTRY, extra, &o);
1065                 if (r < 0)
1066                         return r;
1067
1068                 if (ret)
1069                         *ret = o;
1070
1071                 if (offset)
1072                         *offset = extra;
1073
1074                 return 1;
1075         }
1076
1077         return generic_array_get(f, first, i-1, ret, offset);
1078 }
1079
1080 enum {
1081         TEST_FOUND,
1082         TEST_LEFT,
1083         TEST_RIGHT
1084 };
1085
1086 static int generic_array_bisect(JournalFile *f,
1087                                 uint64_t first,
1088                                 uint64_t n,
1089                                 uint64_t needle,
1090                                 int (*test_object)(JournalFile *f, uint64_t p, uint64_t needle),
1091                                 direction_t direction,
1092                                 Object **ret,
1093                                 uint64_t *offset,
1094                                 uint64_t *idx) {
1095
1096         uint64_t a, p, t = 0, i = 0, last_p = 0;
1097         bool subtract_one = false;
1098         Object *o, *array = NULL;
1099         int r;
1100
1101         assert(f);
1102         assert(test_object);
1103
1104         a = first;
1105         while (a > 0) {
1106                 uint64_t left, right, k, lp;
1107
1108                 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &array);
1109                 if (r < 0)
1110                         return r;
1111
1112                 k = journal_file_entry_array_n_items(array);
1113                 right = MIN(k, n);
1114                 if (right <= 0)
1115                         return 0;
1116
1117                 i = right - 1;
1118                 lp = p = le64toh(array->entry_array.items[i]);
1119                 if (p <= 0)
1120                         return -EBADMSG;
1121
1122                 r = test_object(f, p, needle);
1123                 if (r < 0)
1124                         return r;
1125
1126                 if (r == TEST_FOUND)
1127                         r = direction == DIRECTION_DOWN ? TEST_RIGHT : TEST_LEFT;
1128
1129                 if (r == TEST_RIGHT) {
1130                         left = 0;
1131                         right -= 1;
1132                         for (;;) {
1133                                 if (left == right) {
1134                                         if (direction == DIRECTION_UP)
1135                                                 subtract_one = true;
1136
1137                                         i = left;
1138                                         goto found;
1139                                 }
1140
1141                                 assert(left < right);
1142
1143                                 i = (left + right) / 2;
1144                                 p = le64toh(array->entry_array.items[i]);
1145                                 if (p <= 0)
1146                                         return -EBADMSG;
1147
1148                                 r = test_object(f, p, needle);
1149                                 if (r < 0)
1150                                         return r;
1151
1152                                 if (r == TEST_FOUND)
1153                                         r = direction == DIRECTION_DOWN ? TEST_RIGHT : TEST_LEFT;
1154
1155                                 if (r == TEST_RIGHT)
1156                                         right = i;
1157                                 else
1158                                         left = i + 1;
1159                         }
1160                 }
1161
1162                 if (k > n)
1163                         return 0;
1164
1165                 last_p = lp;
1166
1167                 n -= k;
1168                 t += k;
1169                 a = le64toh(array->entry_array.next_entry_array_offset);
1170         }
1171
1172         return 0;
1173
1174 found:
1175         if (subtract_one && t == 0 && i == 0)
1176                 return 0;
1177
1178         if (subtract_one && i == 0)
1179                 p = last_p;
1180         else if (subtract_one)
1181                 p = le64toh(array->entry_array.items[i-1]);
1182         else
1183                 p = le64toh(array->entry_array.items[i]);
1184
1185         r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
1186         if (r < 0)
1187                 return r;
1188
1189         if (ret)
1190                 *ret = o;
1191
1192         if (offset)
1193                 *offset = p;
1194
1195         if (idx)
1196                 *idx = t + i - (subtract_one ? 1 : 0);
1197
1198         return 1;
1199 }
1200
1201 static int generic_array_bisect_plus_one(JournalFile *f,
1202                                          uint64_t extra,
1203                                          uint64_t first,
1204                                          uint64_t n,
1205                                          uint64_t needle,
1206                                          int (*test_object)(JournalFile *f, uint64_t p, uint64_t needle),
1207                                          direction_t direction,
1208                                          Object **ret,
1209                                          uint64_t *offset,
1210                                          uint64_t *idx) {
1211
1212         int r;
1213
1214         assert(f);
1215         assert(test_object);
1216
1217         if (n <= 0)
1218                 return 0;
1219
1220         /* This bisects the array in object 'first', but first checks
1221          * an extra  */
1222         r = test_object(f, extra, needle);
1223         if (r < 0)
1224                 return r;
1225         else if (r == TEST_FOUND) {
1226                 Object *o;
1227
1228                 r = journal_file_move_to_object(f, OBJECT_ENTRY, extra, &o);
1229                 if (r < 0)
1230                         return r;
1231
1232                 if (ret)
1233                         *ret = o;
1234
1235                 if (offset)
1236                         *offset = extra;
1237
1238                 if (idx)
1239                         *idx = 0;
1240
1241                 return 1;
1242         } else if (r == TEST_RIGHT)
1243                 return 0;
1244
1245         r = generic_array_bisect(f, first, n-1, needle, test_object, direction, ret, offset, idx);
1246
1247         if (r > 0)
1248                 (*idx) ++;
1249
1250         return r;
1251 }
1252
1253 static int test_object_seqnum(JournalFile *f, uint64_t p, uint64_t needle) {
1254         Object *o;
1255         int r;
1256
1257         assert(f);
1258         assert(p > 0);
1259
1260         r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
1261         if (r < 0)
1262                 return r;
1263
1264         if (le64toh(o->entry.seqnum) == needle)
1265                 return TEST_FOUND;
1266         else if (le64toh(o->entry.seqnum) < needle)
1267                 return TEST_LEFT;
1268         else
1269                 return TEST_RIGHT;
1270 }
1271
1272 int journal_file_move_to_entry_by_seqnum(
1273                 JournalFile *f,
1274                 uint64_t seqnum,
1275                 direction_t direction,
1276                 Object **ret,
1277                 uint64_t *offset) {
1278
1279         return generic_array_bisect(f,
1280                                     le64toh(f->header->entry_array_offset),
1281                                     le64toh(f->header->n_entries),
1282                                     seqnum,
1283                                     test_object_seqnum,
1284                                     direction,
1285                                     ret, offset, NULL);
1286 }
1287
1288 static int test_object_realtime(JournalFile *f, uint64_t p, uint64_t needle) {
1289         Object *o;
1290         int r;
1291
1292         assert(f);
1293         assert(p > 0);
1294
1295         r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
1296         if (r < 0)
1297                 return r;
1298
1299         if (le64toh(o->entry.realtime) == needle)
1300                 return TEST_FOUND;
1301         else if (le64toh(o->entry.realtime) < needle)
1302                 return TEST_LEFT;
1303         else
1304                 return TEST_RIGHT;
1305 }
1306
1307 int journal_file_move_to_entry_by_realtime(
1308                 JournalFile *f,
1309                 uint64_t realtime,
1310                 direction_t direction,
1311                 Object **ret,
1312                 uint64_t *offset) {
1313
1314         return generic_array_bisect(f,
1315                                     le64toh(f->header->entry_array_offset),
1316                                     le64toh(f->header->n_entries),
1317                                     realtime,
1318                                     test_object_realtime,
1319                                     direction,
1320                                     ret, offset, NULL);
1321 }
1322
1323 static int test_object_monotonic(JournalFile *f, uint64_t p, uint64_t needle) {
1324         Object *o;
1325         int r;
1326
1327         assert(f);
1328         assert(p > 0);
1329
1330         r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
1331         if (r < 0)
1332                 return r;
1333
1334         if (le64toh(o->entry.monotonic) == needle)
1335                 return TEST_FOUND;
1336         else if (le64toh(o->entry.monotonic) < needle)
1337                 return TEST_LEFT;
1338         else
1339                 return TEST_RIGHT;
1340 }
1341
1342 int journal_file_move_to_entry_by_monotonic(
1343                 JournalFile *f,
1344                 sd_id128_t boot_id,
1345                 uint64_t monotonic,
1346                 direction_t direction,
1347                 Object **ret,
1348                 uint64_t *offset) {
1349
1350         char t[8+32+1] = "_BOOT_ID=";
1351         Object *o;
1352         int r;
1353
1354         sd_id128_to_string(boot_id, t + 8);
1355
1356         r = journal_file_find_data_object(f, t, strlen(t), &o, NULL);
1357         if (r < 0)
1358                 return r;
1359         else if (r == 0)
1360                 return -ENOENT;
1361
1362         return generic_array_bisect_plus_one(f,
1363                                              le64toh(o->data.entry_offset),
1364                                              le64toh(o->data.entry_array_offset),
1365                                              le64toh(o->data.n_entries),
1366                                              monotonic,
1367                                              test_object_monotonic,
1368                                              direction,
1369                                              ret, offset, NULL);
1370 }
1371
1372 static int test_object_offset(JournalFile *f, uint64_t p, uint64_t needle) {
1373         assert(f);
1374         assert(p > 0);
1375
1376         if (p == needle)
1377                 return TEST_FOUND;
1378         else if (p < needle)
1379                 return TEST_LEFT;
1380         else
1381                 return TEST_RIGHT;
1382 }
1383
1384 int journal_file_next_entry(
1385                 JournalFile *f,
1386                 Object *o, uint64_t p,
1387                 direction_t direction,
1388                 Object **ret, uint64_t *offset) {
1389
1390         uint64_t i, n;
1391         int r;
1392
1393         assert(f);
1394         assert(p > 0 || !o);
1395
1396         n = le64toh(f->header->n_entries);
1397         if (n <= 0)
1398                 return 0;
1399
1400         if (!o)
1401                 i = direction == DIRECTION_DOWN ? 0 : n - 1;
1402         else {
1403                 if (o->object.type != OBJECT_ENTRY)
1404                         return -EINVAL;
1405
1406                 r = generic_array_bisect(f,
1407                                          le64toh(f->header->entry_array_offset),
1408                                          le64toh(f->header->n_entries),
1409                                          p,
1410                                          test_object_offset,
1411                                          DIRECTION_DOWN,
1412                                          NULL, NULL,
1413                                          &i);
1414                 if (r <= 0)
1415                         return r;
1416
1417                 if (direction == DIRECTION_DOWN) {
1418                         if (i >= n - 1)
1419                                 return 0;
1420
1421                         i++;
1422                 } else {
1423                         if (i <= 0)
1424                                 return 0;
1425
1426                         i--;
1427                 }
1428         }
1429
1430         /* And jump to it */
1431         return generic_array_get(f,
1432                                  le64toh(f->header->entry_array_offset),
1433                                  i,
1434                                  ret, offset);
1435 }
1436
1437 int journal_file_skip_entry(
1438                 JournalFile *f,
1439                 Object *o, uint64_t p,
1440                 int64_t skip,
1441                 Object **ret, uint64_t *offset) {
1442
1443         uint64_t i, n;
1444         int r;
1445
1446         assert(f);
1447         assert(o);
1448         assert(p > 0);
1449
1450         if (o->object.type != OBJECT_ENTRY)
1451                 return -EINVAL;
1452
1453         r = generic_array_bisect(f,
1454                                  le64toh(f->header->entry_array_offset),
1455                                  le64toh(f->header->n_entries),
1456                                  p,
1457                                  test_object_offset,
1458                                  DIRECTION_DOWN,
1459                                  NULL, NULL,
1460                                  &i);
1461         if (r <= 0)
1462                 return r;
1463
1464         /* Calculate new index */
1465         if (skip < 0) {
1466                 if ((uint64_t) -skip >= i)
1467                         i = 0;
1468                 else
1469                         i = i - (uint64_t) -skip;
1470         } else
1471                 i  += (uint64_t) skip;
1472
1473         n = le64toh(f->header->n_entries);
1474         if (n <= 0)
1475                 return -EBADMSG;
1476
1477         if (i >= n)
1478                 i = n-1;
1479
1480         return generic_array_get(f,
1481                                  le64toh(f->header->entry_array_offset),
1482                                  i,
1483                                  ret, offset);
1484 }
1485
1486 int journal_file_next_entry_for_data(
1487                 JournalFile *f,
1488                 Object *o, uint64_t p,
1489                 uint64_t data_offset,
1490                 direction_t direction,
1491                 Object **ret, uint64_t *offset) {
1492
1493         uint64_t n, i;
1494         int r;
1495         Object *d;
1496
1497         assert(f);
1498         assert(p > 0 || !o);
1499
1500         r = journal_file_move_to_object(f, OBJECT_DATA, data_offset, &d);
1501         if (r < 0)
1502                 return r;
1503
1504         n = le64toh(d->data.n_entries);
1505         if (n <= 0)
1506                 return n;
1507
1508         if (!o)
1509                 i = direction == DIRECTION_DOWN ? 0 : n - 1;
1510         else {
1511                 if (o->object.type != OBJECT_ENTRY)
1512                         return -EINVAL;
1513
1514                 r = generic_array_bisect_plus_one(f,
1515                                                   le64toh(d->data.entry_offset),
1516                                                   le64toh(d->data.entry_array_offset),
1517                                                   le64toh(d->data.n_entries),
1518                                                   p,
1519                                                   test_object_offset,
1520                                                   DIRECTION_DOWN,
1521                                                   NULL, NULL,
1522                                                   &i);
1523
1524                 if (r <= 0)
1525                         return r;
1526
1527                 if (direction == DIRECTION_DOWN) {
1528                         if (i >= n - 1)
1529                                 return 0;
1530
1531                         i++;
1532                 } else {
1533                         if (i <= 0)
1534                                 return 0;
1535
1536                         i--;
1537                 }
1538
1539         }
1540
1541         return generic_array_get_plus_one(f,
1542                                           le64toh(d->data.entry_offset),
1543                                           le64toh(d->data.entry_array_offset),
1544                                           i,
1545                                           ret, offset);
1546 }
1547
1548 int journal_file_move_to_entry_by_seqnum_for_data(
1549                 JournalFile *f,
1550                 uint64_t data_offset,
1551                 uint64_t seqnum,
1552                 direction_t direction,
1553                 Object **ret, uint64_t *offset) {
1554
1555         Object *d;
1556         int r;
1557
1558         r = journal_file_move_to_object(f, OBJECT_DATA, data_offset, &d);
1559         if (r <= 0)
1560                 return r;
1561
1562         return generic_array_bisect_plus_one(f,
1563                                              le64toh(d->data.entry_offset),
1564                                              le64toh(d->data.entry_array_offset),
1565                                              le64toh(d->data.n_entries),
1566                                              seqnum,
1567                                              test_object_seqnum,
1568                                              direction,
1569                                              ret, offset, NULL);
1570 }
1571
1572 int journal_file_move_to_entry_by_realtime_for_data(
1573                 JournalFile *f,
1574                 uint64_t data_offset,
1575                 uint64_t realtime,
1576                 direction_t direction,
1577                 Object **ret, uint64_t *offset) {
1578
1579         Object *d;
1580         int r;
1581
1582         r = journal_file_move_to_object(f, OBJECT_DATA, data_offset, &d);
1583         if (r <= 0)
1584                 return r;
1585
1586         return generic_array_bisect_plus_one(f,
1587                                              le64toh(d->data.entry_offset),
1588                                              le64toh(d->data.entry_array_offset),
1589                                              le64toh(d->data.n_entries),
1590                                              realtime,
1591                                              test_object_realtime,
1592                                              direction,
1593                                              ret, offset, NULL);
1594 }
1595
1596 void journal_file_dump(JournalFile *f) {
1597         char a[33], b[33], c[33];
1598         Object *o;
1599         int r;
1600         uint64_t p;
1601
1602         assert(f);
1603
1604         printf("File Path: %s\n"
1605                "File ID: %s\n"
1606                "Machine ID: %s\n"
1607                "Boot ID: %s\n"
1608                "Arena size: %llu\n"
1609                "Objects: %lu\n"
1610                "Entries: %lu\n",
1611                f->path,
1612                sd_id128_to_string(f->header->file_id, a),
1613                sd_id128_to_string(f->header->machine_id, b),
1614                sd_id128_to_string(f->header->boot_id, c),
1615                (unsigned long long) le64toh(f->header->arena_size),
1616                (unsigned long) le64toh(f->header->n_objects),
1617                (unsigned long) le64toh(f->header->n_entries));
1618
1619         p = le64toh(f->header->arena_offset);
1620         while (p != 0) {
1621                 r = journal_file_move_to_object(f, -1, p, &o);
1622                 if (r < 0)
1623                         goto fail;
1624
1625                 switch (o->object.type) {
1626
1627                 case OBJECT_UNUSED:
1628                         printf("Type: OBJECT_UNUSED\n");
1629                         break;
1630
1631                 case OBJECT_DATA:
1632                         printf("Type: OBJECT_DATA\n");
1633                         break;
1634
1635                 case OBJECT_ENTRY:
1636                         printf("Type: OBJECT_ENTRY %llu %llu %llu\n",
1637                                (unsigned long long) le64toh(o->entry.seqnum),
1638                                (unsigned long long) le64toh(o->entry.monotonic),
1639                                (unsigned long long) le64toh(o->entry.realtime));
1640                         break;
1641
1642                 case OBJECT_FIELD_HASH_TABLE:
1643                         printf("Type: OBJECT_FIELD_HASH_TABLE\n");
1644                         break;
1645
1646                 case OBJECT_DATA_HASH_TABLE:
1647                         printf("Type: OBJECT_DATA_HASH_TABLE\n");
1648                         break;
1649
1650                 case OBJECT_ENTRY_ARRAY:
1651                         printf("Type: OBJECT_ENTRY_ARRAY\n");
1652                         break;
1653                 }
1654
1655                 if (o->object.flags & OBJECT_COMPRESSED)
1656                         printf("Flags: COMPRESSED\n");
1657
1658                 if (p == le64toh(f->header->tail_object_offset))
1659                         p = 0;
1660                 else
1661                         p = p + ALIGN64(le64toh(o->object.size));
1662         }
1663
1664         return;
1665 fail:
1666         log_error("File corrupt");
1667 }
1668
1669 int journal_file_open(
1670                 const char *fname,
1671                 int flags,
1672                 mode_t mode,
1673                 JournalFile *template,
1674                 JournalFile **ret) {
1675
1676         JournalFile *f;
1677         int r;
1678         bool newly_created = false;
1679
1680         assert(fname);
1681
1682         if ((flags & O_ACCMODE) != O_RDONLY &&
1683             (flags & O_ACCMODE) != O_RDWR)
1684                 return -EINVAL;
1685
1686         f = new0(JournalFile, 1);
1687         if (!f)
1688                 return -ENOMEM;
1689
1690         f->fd = -1;
1691         f->flags = flags;
1692         f->mode = mode;
1693         f->writable = (flags & O_ACCMODE) != O_RDONLY;
1694         f->prot = prot_from_flags(flags);
1695
1696         f->metrics.max_size = DEFAULT_MAX_SIZE;
1697         f->metrics.min_size = DEFAULT_MIN_SIZE;
1698         f->metrics.keep_free = DEFAULT_KEEP_FREE;
1699
1700         f->path = strdup(fname);
1701         if (!f->path) {
1702                 r = -ENOMEM;
1703                 goto fail;
1704         }
1705
1706         f->fd = open(f->path, f->flags|O_CLOEXEC, f->mode);
1707         if (f->fd < 0) {
1708                 r = -errno;
1709                 goto fail;
1710         }
1711
1712         if (fstat(f->fd, &f->last_stat) < 0) {
1713                 r = -errno;
1714                 goto fail;
1715         }
1716
1717         if (f->last_stat.st_size == 0 && f->writable) {
1718                 newly_created = true;
1719
1720                 r = journal_file_init_header(f, template);
1721                 if (r < 0)
1722                         goto fail;
1723
1724                 if (fstat(f->fd, &f->last_stat) < 0) {
1725                         r = -errno;
1726                         goto fail;
1727                 }
1728         }
1729
1730         if (f->last_stat.st_size < (off_t) sizeof(Header)) {
1731                 r = -EIO;
1732                 goto fail;
1733         }
1734
1735         f->header = mmap(NULL, PAGE_ALIGN(sizeof(Header)), prot_from_flags(flags), MAP_SHARED, f->fd, 0);
1736         if (f->header == MAP_FAILED) {
1737                 f->header = NULL;
1738                 r = -errno;
1739                 goto fail;
1740         }
1741
1742         if (!newly_created) {
1743                 r = journal_file_verify_header(f);
1744                 if (r < 0)
1745                         goto fail;
1746         }
1747
1748         if (f->writable) {
1749                 r = journal_file_refresh_header(f);
1750                 if (r < 0)
1751                         goto fail;
1752         }
1753
1754         if (newly_created) {
1755
1756                 r = journal_file_setup_field_hash_table(f);
1757                 if (r < 0)
1758                         goto fail;
1759
1760                 r = journal_file_setup_data_hash_table(f);
1761                 if (r < 0)
1762                         goto fail;
1763         }
1764
1765         r = journal_file_map_field_hash_table(f);
1766         if (r < 0)
1767                 goto fail;
1768
1769         r = journal_file_map_data_hash_table(f);
1770         if (r < 0)
1771                 goto fail;
1772
1773         if (ret)
1774                 *ret = f;
1775
1776         return 0;
1777
1778 fail:
1779         journal_file_close(f);
1780
1781         return r;
1782 }
1783
1784 int journal_file_rotate(JournalFile **f) {
1785         char *p;
1786         size_t l;
1787         JournalFile *old_file, *new_file = NULL;
1788         int r;
1789
1790         assert(f);
1791         assert(*f);
1792
1793         old_file = *f;
1794
1795         if (!old_file->writable)
1796                 return -EINVAL;
1797
1798         if (!endswith(old_file->path, ".journal"))
1799                 return -EINVAL;
1800
1801         l = strlen(old_file->path);
1802
1803         p = new(char, l + 1 + 16 + 1 + 32 + 1 + 16 + 1);
1804         if (!p)
1805                 return -ENOMEM;
1806
1807         memcpy(p, old_file->path, l - 8);
1808         p[l-8] = '@';
1809         sd_id128_to_string(old_file->header->seqnum_id, p + l - 8 + 1);
1810         snprintf(p + l - 8 + 1 + 32, 1 + 16 + 1 + 16 + 8 + 1,
1811                  "-%016llx-%016llx.journal",
1812                  (unsigned long long) le64toh((*f)->header->seqnum),
1813                  (unsigned long long) le64toh((*f)->header->tail_entry_realtime));
1814
1815         r = rename(old_file->path, p);
1816         free(p);
1817
1818         if (r < 0)
1819                 return -errno;
1820
1821         old_file->header->state = le32toh(STATE_ARCHIVED);
1822
1823         r = journal_file_open(old_file->path, old_file->flags, old_file->mode, old_file, &new_file);
1824         journal_file_close(old_file);
1825
1826         *f = new_file;
1827         return r;
1828 }
1829
1830 struct vacuum_info {
1831         off_t usage;
1832         char *filename;
1833
1834         uint64_t realtime;
1835         sd_id128_t seqnum_id;
1836         uint64_t seqnum;
1837 };
1838
1839 static int vacuum_compare(const void *_a, const void *_b) {
1840         const struct vacuum_info *a, *b;
1841
1842         a = _a;
1843         b = _b;
1844
1845         if (sd_id128_equal(a->seqnum_id, b->seqnum_id)) {
1846                 if (a->seqnum < b->seqnum)
1847                         return -1;
1848                 else if (a->seqnum > b->seqnum)
1849                         return 1;
1850                 else
1851                         return 0;
1852         }
1853
1854         if (a->realtime < b->realtime)
1855                 return -1;
1856         else if (a->realtime > b->realtime)
1857                 return 1;
1858         else
1859                 return memcmp(&a->seqnum_id, &b->seqnum_id, 16);
1860 }
1861
1862 int journal_directory_vacuum(const char *directory, uint64_t max_use, uint64_t min_free) {
1863         DIR *d;
1864         int r = 0;
1865         struct vacuum_info *list = NULL;
1866         unsigned n_list = 0, n_allocated = 0, i;
1867         uint64_t sum = 0;
1868
1869         assert(directory);
1870
1871         if (max_use <= 0)
1872                 max_use = DEFAULT_MAX_USE;
1873
1874         d = opendir(directory);
1875         if (!d)
1876                 return -errno;
1877
1878         for (;;) {
1879                 int k;
1880                 struct dirent buf, *de;
1881                 size_t q;
1882                 struct stat st;
1883                 char *p;
1884                 unsigned long long seqnum, realtime;
1885                 sd_id128_t seqnum_id;
1886
1887                 k = readdir_r(d, &buf, &de);
1888                 if (k != 0) {
1889                         r = -k;
1890                         goto finish;
1891                 }
1892
1893                 if (!de)
1894                         break;
1895
1896                 if (!dirent_is_file_with_suffix(de, ".journal"))
1897                         continue;
1898
1899                 q = strlen(de->d_name);
1900
1901                 if (q < 1 + 32 + 1 + 16 + 1 + 16 + 8)
1902                         continue;
1903
1904                 if (de->d_name[q-8-16-1] != '-' ||
1905                     de->d_name[q-8-16-1-16-1] != '-' ||
1906                     de->d_name[q-8-16-1-16-1-32-1] != '@')
1907                         continue;
1908
1909                 if (fstatat(dirfd(d), de->d_name, &st, AT_SYMLINK_NOFOLLOW) < 0)
1910                         continue;
1911
1912                 if (!S_ISREG(st.st_mode))
1913                         continue;
1914
1915                 p = strdup(de->d_name);
1916                 if (!p) {
1917                         r = -ENOMEM;
1918                         goto finish;
1919                 }
1920
1921                 de->d_name[q-8-16-1-16-1] = 0;
1922                 if (sd_id128_from_string(de->d_name + q-8-16-1-16-1-32, &seqnum_id) < 0) {
1923                         free(p);
1924                         continue;
1925                 }
1926
1927                 if (sscanf(de->d_name + q-8-16-1-16, "%16llx-%16llx.journal", &seqnum, &realtime) != 2) {
1928                         free(p);
1929                         continue;
1930                 }
1931
1932                 if (n_list >= n_allocated) {
1933                         struct vacuum_info *j;
1934
1935                         n_allocated = MAX(n_allocated * 2U, 8U);
1936                         j = realloc(list, n_allocated * sizeof(struct vacuum_info));
1937                         if (!j) {
1938                                 free(p);
1939                                 r = -ENOMEM;
1940                                 goto finish;
1941                         }
1942
1943                         list = j;
1944                 }
1945
1946                 list[n_list].filename = p;
1947                 list[n_list].usage = (uint64_t) st.st_blksize * (uint64_t) st.st_blocks;
1948                 list[n_list].seqnum = seqnum;
1949                 list[n_list].realtime = realtime;
1950                 list[n_list].seqnum_id = seqnum_id;
1951
1952                 sum += list[n_list].usage;
1953
1954                 n_list ++;
1955         }
1956
1957         qsort(list, n_list, sizeof(struct vacuum_info), vacuum_compare);
1958
1959         for(i = 0; i < n_list; i++) {
1960                 struct statvfs ss;
1961
1962                 if (fstatvfs(dirfd(d), &ss) < 0) {
1963                         r = -errno;
1964                         goto finish;
1965                 }
1966
1967                 if (sum <= max_use &&
1968                     (uint64_t) ss.f_bavail * (uint64_t) ss.f_bsize >= min_free)
1969                         break;
1970
1971                 if (unlinkat(dirfd(d), list[i].filename, 0) >= 0) {
1972                         log_debug("Deleted archived journal %s/%s.", directory, list[i].filename);
1973                         sum -= list[i].usage;
1974                 } else if (errno != ENOENT)
1975                         log_warning("Failed to delete %s/%s: %m", directory, list[i].filename);
1976         }
1977
1978 finish:
1979         for (i = 0; i < n_list; i++)
1980                 free(list[i].filename);
1981
1982         free(list);
1983
1984         if (d)
1985                 closedir(d);
1986
1987         return r;
1988 }