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                         return -EBADMSG;
 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                 p = le64toh(o->data.next_hash_offset);
 641         }
 642
 643         return 0;
 644 }
 645
 646 int journal_file_find_data_object(
 647                 JournalFile *f,
 648                 const void *data, uint64_t size,
 649                 Object **ret, uint64_t *offset) {
 650
 651         uint64_t hash;
 652
 653         assert(f);
 654         assert(data || size == 0);
 655
 656         hash = hash64(data, size);
 657
 658         return journal_file_find_data_object_with_hash(f,
 659                                                        data, size, hash,
 660                                                        ret, offset);
 661 }
 662
 663 static int journal_file_append_data(JournalFile *f, const void *data, uint64_t size, Object **ret, uint64_t *offset) {
 664         uint64_t hash, p;
 665         uint64_t osize;
 666         Object *o;
 667         int r;
 668         bool compressed = false;
 669
 670         assert(f);
 671         assert(data || size == 0);
 672
 673         hash = hash64(data, size);
 674
 675         r = journal_file_find_data_object_with_hash(f, data, size, hash, &o, &p);
 676         if (r < 0)
 677                 return r;
 678         else if (r > 0) {
 679
 680                 if (ret)
 681                         *ret = o;
 682
 683                 if (offset)
 684                         *offset = p;
 685
 686                 return 0;
 687         }
 688
 689         osize = offsetof(Object, data.payload) + size;
 690         r = journal_file_append_object(f, OBJECT_DATA, osize, &o, &p);
 691         if (r < 0)
 692                 return r;
 693
 694         o->data.hash = htole64(hash);
 695
 696 #ifdef HAVE_XZ
 697         if (f->compress &&
 698             size >= COMPRESSION_SIZE_THRESHOLD) {
 699                 uint64_t rsize;
 700
 701                 compressed = compress_blob(data, size, o->data.payload, &rsize);
 702
 703                 if (compressed) {
 704                         o->object.size = htole64(offsetof(Object, data.payload) + rsize);
 705                         o->object.flags |= OBJECT_COMPRESSED;
 706
 707                         f->header->incompatible_flags = htole32(le32toh(f->header->incompatible_flags) | HEADER_INCOMPATIBLE_COMPRESSED);
 708
 709                         log_debug("Compressed data object %lu -> %lu", (unsigned long) size, (unsigned long) rsize);
 710                 }
 711         }
 712 #endif
 713
 714         if (!compressed)
 715                 memcpy(o->data.payload, data, size);
 716
 717         r = journal_file_link_data(f, o, p, hash);
 718         if (r < 0)
 719                 return r;
 720
 721         if (ret)
 722                 *ret = o;
 723
 724         if (offset)
 725                 *offset = p;
 726
 727         return 0;
 728 }
 729
 730 uint64_t journal_file_entry_n_items(Object *o) {
 731         assert(o);
 732         assert(o->object.type == htole64(OBJECT_ENTRY));
 733
 734         return (le64toh(o->object.size) - offsetof(Object, entry.items)) / sizeof(EntryItem);
 735 }
 736
 737 static uint64_t journal_file_entry_array_n_items(Object *o) {
 738         assert(o);
 739         assert(o->object.type == htole64(OBJECT_ENTRY_ARRAY));
 740
 741         return (le64toh(o->object.size) - offsetof(Object, entry_array.items)) / sizeof(uint64_t);
 742 }
 743
 744 static int link_entry_into_array(JournalFile *f,
 745                                  uint64_t *first,
 746                                  uint64_t *idx,
 747                                  uint64_t p) {
 748         int r;
 749         uint64_t n = 0, ap = 0, q, i, a, hidx;
 750         Object *o;
 751
 752         assert(f);
 753         assert(first);
 754         assert(idx);
 755         assert(p > 0);
 756
 757         a = le64toh(*first);
 758         i = hidx = le64toh(*idx);
 759         while (a > 0) {
 760
 761                 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
 762                 if (r < 0)
 763                         return r;
 764
 765                 n = journal_file_entry_array_n_items(o);
 766                 if (i < n) {
 767                         o->entry_array.items[i] = htole64(p);
 768                         *idx = htole64(hidx + 1);
 769                         return 0;
 770                 }
 771
 772                 i -= n;
 773                 ap = a;
 774                 a = le64toh(o->entry_array.next_entry_array_offset);
 775         }
 776
 777         if (hidx > n)
 778                 n = (hidx+1) * 2;
 779         else
 780                 n = n * 2;
 781
 782         if (n < 4)
 783                 n = 4;
 784
 785         r = journal_file_append_object(f, OBJECT_ENTRY_ARRAY,
 786                                        offsetof(Object, entry_array.items) + n * sizeof(uint64_t),
 787                                        &o, &q);
 788         if (r < 0)
 789                 return r;
 790
 791         o->entry_array.items[i] = htole64(p);
 792
 793         if (ap == 0)
 794                 *first = q;
 795         else {
 796                 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, ap, &o);
 797                 if (r < 0)
 798                         return r;
 799
 800                 o->entry_array.next_entry_array_offset = htole64(q);
 801         }
 802
 803         *idx = htole64(hidx + 1);
 804
 805         return 0;
 806 }
 807
 808 static int link_entry_into_array_plus_one(JournalFile *f,
 809                                           uint64_t *extra,
 810                                           uint64_t *first,
 811                                           uint64_t *idx,
 812                                           uint64_t p) {
 813
 814         int r;
 815
 816         assert(f);
 817         assert(extra);
 818         assert(first);
 819         assert(idx);
 820         assert(p > 0);
 821
 822         if (*idx == 0)
 823                 *extra = htole64(p);
 824         else {
 825                 uint64_t i;
 826
 827                 i = le64toh(*idx) - 1;
 828                 r = link_entry_into_array(f, first, &i, p);
 829                 if (r < 0)
 830                         return r;
 831         }
 832
 833         *idx = htole64(le64toh(*idx) + 1);
 834         return 0;
 835 }
 836
 837 static int journal_file_link_entry_item(JournalFile *f, Object *o, uint64_t offset, uint64_t i) {
 838         uint64_t p;
 839         int r;
 840         assert(f);
 841         assert(o);
 842         assert(offset > 0);
 843
 844         p = le64toh(o->entry.items[i].object_offset);
 845         if (p == 0)
 846                 return -EINVAL;
 847
 848         r = journal_file_move_to_object(f, OBJECT_DATA, p, &o);
 849         if (r < 0)
 850                 return r;
 851
 852         return link_entry_into_array_plus_one(f,
 853                                               &o->data.entry_offset,
 854                                               &o->data.entry_array_offset,
 855                                               &o->data.n_entries,
 856                                               offset);
 857 }
 858
 859 static int journal_file_link_entry(JournalFile *f, Object *o, uint64_t offset) {
 860         uint64_t n, i;
 861         int r;
 862
 863         assert(f);
 864         assert(o);
 865         assert(offset > 0);
 866         assert(o->object.type == OBJECT_ENTRY);
 867
 868         /* Link up the entry itself */
 869         r = link_entry_into_array(f,
 870                                   &f->header->entry_array_offset,
 871                                   &f->header->n_entries,
 872                                   offset);
 873         if (r < 0)
 874                 return r;
 875
 876         log_error("=> %s seqnr=%lu n_entries=%lu", f->path, (unsigned long) o->entry.seqnum, (unsigned long) f->header->n_entries);
 877
 878         if (f->header->head_entry_realtime == 0)
 879                 f->header->head_entry_realtime = o->entry.realtime;
 880
 881         f->header->tail_entry_realtime = o->entry.realtime;
 882         f->header->tail_entry_monotonic = o->entry.monotonic;
 883
 884         f->tail_entry_monotonic_valid = true;
 885
 886         /* Link up the items */
 887         n = journal_file_entry_n_items(o);
 888         for (i = 0; i < n; i++) {
 889                 r = journal_file_link_entry_item(f, o, offset, i);
 890                 if (r < 0)
 891                         return r;
 892         }
 893
 894         return 0;
 895 }
 896
 897 static int journal_file_append_entry_internal(
 898                 JournalFile *f,
 899                 const dual_timestamp *ts,
 900                 uint64_t xor_hash,
 901                 const EntryItem items[], unsigned n_items,
 902                 uint64_t *seqnum,
 903                 Object **ret, uint64_t *offset) {
 904         uint64_t np;
 905         uint64_t osize;
 906         Object *o;
 907         int r;
 908
 909         assert(f);
 910         assert(items || n_items == 0);
 911         assert(ts);
 912
 913         osize = offsetof(Object, entry.items) + (n_items * sizeof(EntryItem));
 914
 915         r = journal_file_append_object(f, OBJECT_ENTRY, osize, &o, &np);
 916         if (r < 0)
 917                 return r;
 918
 919         o->entry.seqnum = htole64(journal_file_seqnum(f, seqnum));
 920         memcpy(o->entry.items, items, n_items * sizeof(EntryItem));
 921         o->entry.realtime = htole64(ts->realtime);
 922         o->entry.monotonic = htole64(ts->monotonic);
 923         o->entry.xor_hash = htole64(xor_hash);
 924         o->entry.boot_id = f->header->boot_id;
 925
 926         r = journal_file_link_entry(f, o, np);
 927         if (r < 0)
 928                 return r;
 929
 930         if (ret)
 931                 *ret = o;
 932
 933         if (offset)
 934                 *offset = np;
 935
 936         return 0;
 937 }
 938
 939 static void journal_file_post_change(JournalFile *f) {
 940         assert(f);
 941
 942         /* inotify() does not receive IN_MODIFY events from file
 943          * accesses done via mmap(). After each access we hence
 944          * trigger IN_MODIFY by truncating the journal file to its
 945          * current size which triggers IN_MODIFY. */
 946
 947         __sync_synchronize();
 948
 949         if (ftruncate(f->fd, f->last_stat.st_size) < 0)
 950                 log_error("Failed to to truncate file to its own size: %m");
 951 }
 952
 953 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) {
 954         unsigned i;
 955         EntryItem *items;
 956         int r;
 957         uint64_t xor_hash = 0;
 958         struct dual_timestamp _ts;
 959
 960         assert(f);
 961         assert(iovec || n_iovec == 0);
 962
 963         if (!f->writable)
 964                 return -EPERM;
 965
 966         if (!ts) {
 967                 dual_timestamp_get(&_ts);
 968                 ts = &_ts;
 969         }
 970
 971         if (f->tail_entry_monotonic_valid &&
 972             ts->monotonic < le64toh(f->header->tail_entry_monotonic))
 973                 return -EINVAL;
 974
 975         if (ts->realtime < le64toh(f->header->tail_entry_realtime))
 976                 return -EINVAL;
 977
 978         items = new(EntryItem, n_iovec);
 979         if (!items)
 980                 return -ENOMEM;
 981
 982         for (i = 0; i < n_iovec; i++) {
 983                 uint64_t p;
 984                 Object *o;
 985
 986                 r = journal_file_append_data(f, iovec[i].iov_base, iovec[i].iov_len, &o, &p);
 987                 if (r < 0)
 988                         goto finish;
 989
 990                 xor_hash ^= le64toh(o->data.hash);
 991                 items[i].object_offset = htole64(p);
 992                 items[i].hash = o->data.hash;
 993         }
 994
 995         r = journal_file_append_entry_internal(f, ts, xor_hash, items, n_iovec, seqnum, ret, offset);
 996
 997         journal_file_post_change(f);
 998
 999 finish:
1000         free(items);
1001
1002         return r;
1003 }
1004
1005 static int generic_array_get(JournalFile *f,
1006                              uint64_t first,
1007                              uint64_t i,
1008                              Object **ret, uint64_t *offset) {
1009
1010         Object *o;
1011         uint64_t p, a;
1012         int r;
1013
1014         assert(f);
1015
1016         a = first;
1017         while (a > 0) {
1018                 uint64_t n;
1019
1020                 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
1021                 if (r < 0)
1022                         return r;
1023
1024                 n = journal_file_entry_array_n_items(o);
1025                 if (i < n) {
1026                         p = le64toh(o->entry_array.items[i]);
1027                         break;
1028                 }
1029
1030                 i -= n;
1031                 a = le64toh(o->entry_array.next_entry_array_offset);
1032         }
1033
1034         if (a <= 0 || p <= 0)
1035                 return 0;
1036
1037         r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
1038         if (r < 0)
1039                 return r;
1040
1041         if (ret)
1042                 *ret = o;
1043
1044         if (offset)
1045                 *offset = p;
1046
1047         return 1;
1048 }
1049
1050 static int generic_array_get_plus_one(JournalFile *f,
1051                                       uint64_t extra,
1052                                       uint64_t first,
1053                                       uint64_t i,
1054                                       Object **ret, uint64_t *offset) {
1055
1056         Object *o;
1057
1058         assert(f);
1059
1060         if (i == 0) {
1061                 int r;
1062
1063                 r = journal_file_move_to_object(f, OBJECT_ENTRY, extra, &o);
1064                 if (r < 0)
1065                         return r;
1066
1067                 if (ret)
1068                         *ret = o;
1069
1070                 if (offset)
1071                         *offset = extra;
1072
1073                 return 1;
1074         }
1075
1076         return generic_array_get(f, first, i-1, ret, offset);
1077 }
1078
1079 enum {
1080         TEST_FOUND,
1081         TEST_LEFT,
1082         TEST_RIGHT
1083 };
1084
1085 static int generic_array_bisect(JournalFile *f,
1086                                 uint64_t first,
1087                                 uint64_t n,
1088                                 uint64_t needle,
1089                                 int (*test_object)(JournalFile *f, uint64_t p, uint64_t needle),
1090                                 direction_t direction,
1091                                 Object **ret,
1092                                 uint64_t *offset,
1093                                 uint64_t *idx) {
1094
1095         uint64_t a, p, t = 0, i = 0, last_p = 0;
1096         bool subtract_one = false;
1097         Object *o, *array = NULL;
1098         int r;
1099
1100         assert(f);
1101         assert(test_object);
1102
1103         a = first;
1104         while (a > 0) {
1105                 uint64_t left, right, k, lp;
1106
1107                 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &array);
1108                 if (r < 0)
1109                         return r;
1110
1111                 k = journal_file_entry_array_n_items(array);
1112                 right = MIN(k, n);
1113                 if (right <= 0)
1114                         return 0;
1115
1116                 i = right - 1;
1117                 lp = p = le64toh(array->entry_array.items[i]);
1118                 if (p <= 0)
1119                         return -EBADMSG;
1120
1121                 r = test_object(f, p, needle);
1122                 if (r < 0)
1123                         return r;
1124
1125                 if (r == TEST_FOUND)
1126                         r = direction == DIRECTION_DOWN ? TEST_RIGHT : TEST_LEFT;
1127
1128                 if (r == TEST_RIGHT) {
1129                         left = 0;
1130                         right -= 1;
1131                         for (;;) {
1132                                 if (left == right) {
1133                                         if (direction == DIRECTION_UP)
1134                                                 subtract_one = true;
1135
1136                                         i = left;
1137                                         goto found;
1138                                 }
1139
1140                                 assert(left < right);
1141
1142                                 i = (left + right) / 2;
1143                                 p = le64toh(array->entry_array.items[i]);
1144                                 if (p <= 0)
1145                                         return -EBADMSG;
1146
1147                                 r = test_object(f, p, needle);
1148                                 if (r < 0)
1149                                         return r;
1150
1151                                 if (r == TEST_FOUND)
1152                                         r = direction == DIRECTION_DOWN ? TEST_RIGHT : TEST_LEFT;
1153
1154                                 if (r == TEST_RIGHT)
1155                                         right = i;
1156                                 else
1157                                         left = i + 1;
1158                         }
1159                 }
1160
1161                 if (k > n)
1162                         return 0;
1163
1164                 last_p = lp;
1165
1166                 n -= k;
1167                 t += k;
1168                 a = le64toh(array->entry_array.next_entry_array_offset);
1169         }
1170
1171         return 0;
1172
1173 found:
1174         if (subtract_one && t == 0 && i == 0)
1175                 return 0;
1176
1177         if (subtract_one && i == 0)
1178                 p = last_p;
1179         else if (subtract_one)
1180                 p = le64toh(array->entry_array.items[i-1]);
1181         else
1182                 p = le64toh(array->entry_array.items[i]);
1183
1184         r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
1185         if (r < 0)
1186                 return r;
1187
1188         if (ret)
1189                 *ret = o;
1190
1191         if (offset)
1192                 *offset = p;
1193
1194         if (idx)
1195                 *idx = t + i - (subtract_one ? 1 : 0);
1196
1197         return 1;
1198 }
1199
1200 static int generic_array_bisect_plus_one(JournalFile *f,
1201                                          uint64_t extra,
1202                                          uint64_t first,
1203                                          uint64_t n,
1204                                          uint64_t needle,
1205                                          int (*test_object)(JournalFile *f, uint64_t p, uint64_t needle),
1206                                          direction_t direction,
1207                                          Object **ret,
1208                                          uint64_t *offset,
1209                                          uint64_t *idx) {
1210
1211         int r;
1212
1213         assert(f);
1214         assert(test_object);
1215
1216         if (n <= 0)
1217                 return 0;
1218
1219         /* This bisects the array in object 'first', but first checks
1220          * an extra  */
1221         r = test_object(f, extra, needle);
1222         if (r < 0)
1223                 return r;
1224         else if (r == TEST_FOUND) {
1225                 Object *o;
1226
1227                 r = journal_file_move_to_object(f, OBJECT_ENTRY, extra, &o);
1228                 if (r < 0)
1229                         return r;
1230
1231                 if (ret)
1232                         *ret = o;
1233
1234                 if (offset)
1235                         *offset = extra;
1236
1237                 if (idx)
1238                         *idx = 0;
1239
1240                 return 1;
1241         } else if (r == TEST_RIGHT)
1242                 return 0;
1243
1244         r = generic_array_bisect(f, first, n-1, needle, test_object, direction, ret, offset, idx);
1245
1246         if (r > 0)
1247                 (*idx) ++;
1248
1249         return r;
1250 }
1251
1252 static int test_object_seqnum(JournalFile *f, uint64_t p, uint64_t needle) {
1253         Object *o;
1254         int r;
1255
1256         assert(f);
1257         assert(p > 0);
1258
1259         r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
1260         if (r < 0)
1261                 return r;
1262
1263         if (le64toh(o->entry.seqnum) == needle)
1264                 return TEST_FOUND;
1265         else if (le64toh(o->entry.seqnum) < needle)
1266                 return TEST_LEFT;
1267         else
1268                 return TEST_RIGHT;
1269 }
1270
1271 int journal_file_move_to_entry_by_seqnum(
1272                 JournalFile *f,
1273                 uint64_t seqnum,
1274                 direction_t direction,
1275                 Object **ret,
1276                 uint64_t *offset) {
1277
1278         return generic_array_bisect(f,
1279                                     le64toh(f->header->entry_array_offset),
1280                                     le64toh(f->header->n_entries),
1281                                     seqnum,
1282                                     test_object_seqnum,
1283                                     direction,
1284                                     ret, offset, NULL);
1285 }
1286
1287 static int test_object_realtime(JournalFile *f, uint64_t p, uint64_t needle) {
1288         Object *o;
1289         int r;
1290
1291         assert(f);
1292         assert(p > 0);
1293
1294         r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
1295         if (r < 0)
1296                 return r;
1297
1298         if (le64toh(o->entry.realtime) == needle)
1299                 return TEST_FOUND;
1300         else if (le64toh(o->entry.realtime) < needle)
1301                 return TEST_LEFT;
1302         else
1303                 return TEST_RIGHT;
1304 }
1305
1306 int journal_file_move_to_entry_by_realtime(
1307                 JournalFile *f,
1308                 uint64_t realtime,
1309                 direction_t direction,
1310                 Object **ret,
1311                 uint64_t *offset) {
1312
1313         return generic_array_bisect(f,
1314                                     le64toh(f->header->entry_array_offset),
1315                                     le64toh(f->header->n_entries),
1316                                     realtime,
1317                                     test_object_realtime,
1318                                     direction,
1319                                     ret, offset, NULL);
1320 }
1321
1322 static int test_object_monotonic(JournalFile *f, uint64_t p, uint64_t needle) {
1323         Object *o;
1324         int r;
1325
1326         assert(f);
1327         assert(p > 0);
1328
1329         r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
1330         if (r < 0)
1331                 return r;
1332
1333         if (le64toh(o->entry.monotonic) == needle)
1334                 return TEST_FOUND;
1335         else if (le64toh(o->entry.monotonic) < needle)
1336                 return TEST_LEFT;
1337         else
1338                 return TEST_RIGHT;
1339 }
1340
1341 int journal_file_move_to_entry_by_monotonic(
1342                 JournalFile *f,
1343                 sd_id128_t boot_id,
1344                 uint64_t monotonic,
1345                 direction_t direction,
1346                 Object **ret,
1347                 uint64_t *offset) {
1348
1349         char t[8+32+1] = "_BOOT_ID=";
1350         Object *o;
1351         int r;
1352
1353         sd_id128_to_string(boot_id, t + 8);
1354
1355         r = journal_file_find_data_object(f, t, strlen(t), &o, NULL);
1356         if (r < 0)
1357                 return r;
1358         else if (r == 0)
1359                 return -ENOENT;
1360
1361         return generic_array_bisect_plus_one(f,
1362                                              le64toh(o->data.entry_offset),
1363                                              le64toh(o->data.entry_array_offset),
1364                                              le64toh(o->data.n_entries),
1365                                              monotonic,
1366                                              test_object_monotonic,
1367                                              direction,
1368                                              ret, offset, NULL);
1369 }
1370
1371 static int test_object_offset(JournalFile *f, uint64_t p, uint64_t needle) {
1372         assert(f);
1373         assert(p > 0);
1374
1375         if (p == needle)
1376                 return TEST_FOUND;
1377         else if (p < needle)
1378                 return TEST_LEFT;
1379         else
1380                 return TEST_RIGHT;
1381 }
1382
1383 int journal_file_next_entry(
1384                 JournalFile *f,
1385                 Object *o, uint64_t p,
1386                 direction_t direction,
1387                 Object **ret, uint64_t *offset) {
1388
1389         uint64_t i, n;
1390         int r;
1391
1392         assert(f);
1393         assert(p > 0 || !o);
1394
1395         n = le64toh(f->header->n_entries);
1396         if (n <= 0)
1397                 return 0;
1398
1399         if (!o)
1400                 i = direction == DIRECTION_DOWN ? 0 : n - 1;
1401         else {
1402                 if (o->object.type != OBJECT_ENTRY)
1403                         return -EINVAL;
1404
1405                 r = generic_array_bisect(f,
1406                                          le64toh(f->header->entry_array_offset),
1407                                          le64toh(f->header->n_entries),
1408                                          p,
1409                                          test_object_offset,
1410                                          DIRECTION_DOWN,
1411                                          NULL, NULL,
1412                                          &i);
1413                 if (r <= 0)
1414                         return r;
1415
1416                 if (direction == DIRECTION_DOWN) {
1417                         if (i >= n - 1)
1418                                 return 0;
1419
1420                         i++;
1421                 } else {
1422                         if (i <= 0)
1423                                 return 0;
1424
1425                         i--;
1426                 }
1427         }
1428
1429         /* And jump to it */
1430         return generic_array_get(f,
1431                                  le64toh(f->header->entry_array_offset),
1432                                  i,
1433                                  ret, offset);
1434 }
1435
1436 int journal_file_skip_entry(
1437                 JournalFile *f,
1438                 Object *o, uint64_t p,
1439                 int64_t skip,
1440                 Object **ret, uint64_t *offset) {
1441
1442         uint64_t i, n;
1443         int r;
1444
1445         assert(f);
1446         assert(o);
1447         assert(p > 0);
1448
1449         if (o->object.type != OBJECT_ENTRY)
1450                 return -EINVAL;
1451
1452         r = generic_array_bisect(f,
1453                                  le64toh(f->header->entry_array_offset),
1454                                  le64toh(f->header->n_entries),
1455                                  p,
1456                                  test_object_offset,
1457                                  DIRECTION_DOWN,
1458                                  NULL, NULL,
1459                                  &i);
1460         if (r <= 0)
1461                 return r;
1462
1463         /* Calculate new index */
1464         if (skip < 0) {
1465                 if ((uint64_t) -skip >= i)
1466                         i = 0;
1467                 else
1468                         i = i - (uint64_t) -skip;
1469         } else
1470                 i  += (uint64_t) skip;
1471
1472         n = le64toh(f->header->n_entries);
1473         if (n <= 0)
1474                 return -EBADMSG;
1475
1476         if (i >= n)
1477                 i = n-1;
1478
1479         return generic_array_get(f,
1480                                  le64toh(f->header->entry_array_offset),
1481                                  i,
1482                                  ret, offset);
1483 }
1484
1485 int journal_file_next_entry_for_data(
1486                 JournalFile *f,
1487                 Object *o, uint64_t p,
1488                 uint64_t data_offset,
1489                 direction_t direction,
1490                 Object **ret, uint64_t *offset) {
1491
1492         uint64_t n, i;
1493         int r;
1494         Object *d;
1495
1496         assert(f);
1497         assert(p > 0 || !o);
1498
1499         r = journal_file_move_to_object(f, OBJECT_DATA, data_offset, &d);
1500         if (r < 0)
1501                 return r;
1502
1503         n = le64toh(d->data.n_entries);
1504         if (n <= 0)
1505                 return n;
1506
1507         if (!o)
1508                 i = direction == DIRECTION_DOWN ? 0 : n - 1;
1509         else {
1510                 if (o->object.type != OBJECT_ENTRY)
1511                         return -EINVAL;
1512
1513                 r = generic_array_bisect_plus_one(f,
1514                                                   le64toh(d->data.entry_offset),
1515                                                   le64toh(d->data.entry_array_offset),
1516                                                   le64toh(d->data.n_entries),
1517                                                   p,
1518                                                   test_object_offset,
1519                                                   DIRECTION_DOWN,
1520                                                   NULL, NULL,
1521                                                   &i);
1522
1523                 if (r <= 0)
1524                         return r;
1525
1526                 if (direction == DIRECTION_DOWN) {
1527                         if (i >= n - 1)
1528                                 return 0;
1529
1530                         i++;
1531                 } else {
1532                         if (i <= 0)
1533                                 return 0;
1534
1535                         i--;
1536                 }
1537
1538         }
1539
1540         return generic_array_get_plus_one(f,
1541                                           le64toh(d->data.entry_offset),
1542                                           le64toh(d->data.entry_array_offset),
1543                                           i,
1544                                           ret, offset);
1545 }
1546
1547 int journal_file_move_to_entry_by_seqnum_for_data(
1548                 JournalFile *f,
1549                 uint64_t data_offset,
1550                 uint64_t seqnum,
1551                 direction_t direction,
1552                 Object **ret, uint64_t *offset) {
1553
1554         Object *d;
1555         int r;
1556
1557         r = journal_file_move_to_object(f, OBJECT_DATA, data_offset, &d);
1558         if (r <= 0)
1559                 return r;
1560
1561         return generic_array_bisect_plus_one(f,
1562                                              le64toh(d->data.entry_offset),
1563                                              le64toh(d->data.entry_array_offset),
1564                                              le64toh(d->data.n_entries),
1565                                              seqnum,
1566                                              test_object_seqnum,
1567                                              direction,
1568                                              ret, offset, NULL);
1569 }
1570
1571 int journal_file_move_to_entry_by_realtime_for_data(
1572                 JournalFile *f,
1573                 uint64_t data_offset,
1574                 uint64_t realtime,
1575                 direction_t direction,
1576                 Object **ret, uint64_t *offset) {
1577
1578         Object *d;
1579         int r;
1580
1581         r = journal_file_move_to_object(f, OBJECT_DATA, data_offset, &d);
1582         if (r <= 0)
1583                 return r;
1584
1585         return generic_array_bisect_plus_one(f,
1586                                              le64toh(d->data.entry_offset),
1587                                              le64toh(d->data.entry_array_offset),
1588                                              le64toh(d->data.n_entries),
1589                                              realtime,
1590                                              test_object_realtime,
1591                                              direction,
1592                                              ret, offset, NULL);
1593 }
1594
1595 void journal_file_dump(JournalFile *f) {
1596         char a[33], b[33], c[33];
1597         Object *o;
1598         int r;
1599         uint64_t p;
1600
1601         assert(f);
1602
1603         printf("File Path: %s\n"
1604                "File ID: %s\n"
1605                "Machine ID: %s\n"
1606                "Boot ID: %s\n"
1607                "Arena size: %llu\n"
1608                "Objects: %lu\n"
1609                "Entries: %lu\n",
1610                f->path,
1611                sd_id128_to_string(f->header->file_id, a),
1612                sd_id128_to_string(f->header->machine_id, b),
1613                sd_id128_to_string(f->header->boot_id, c),
1614                (unsigned long long) le64toh(f->header->arena_size),
1615                (unsigned long) le64toh(f->header->n_objects),
1616                (unsigned long) le64toh(f->header->n_entries));
1617
1618         p = le64toh(f->header->arena_offset);
1619         while (p != 0) {
1620                 r = journal_file_move_to_object(f, -1, p, &o);
1621                 if (r < 0)
1622                         goto fail;
1623
1624                 switch (o->object.type) {
1625
1626                 case OBJECT_UNUSED:
1627                         printf("Type: OBJECT_UNUSED\n");
1628                         break;
1629
1630                 case OBJECT_DATA:
1631                         printf("Type: OBJECT_DATA\n");
1632                         break;
1633
1634                 case OBJECT_ENTRY:
1635                         printf("Type: OBJECT_ENTRY %llu %llu %llu\n",
1636                                (unsigned long long) le64toh(o->entry.seqnum),
1637                                (unsigned long long) le64toh(o->entry.monotonic),
1638                                (unsigned long long) le64toh(o->entry.realtime));
1639                         break;
1640
1641                 case OBJECT_FIELD_HASH_TABLE:
1642                         printf("Type: OBJECT_FIELD_HASH_TABLE\n");
1643                         break;
1644
1645                 case OBJECT_DATA_HASH_TABLE:
1646                         printf("Type: OBJECT_DATA_HASH_TABLE\n");
1647                         break;
1648
1649                 case OBJECT_ENTRY_ARRAY:
1650                         printf("Type: OBJECT_ENTRY_ARRAY\n");
1651                         break;
1652                 }
1653
1654                 if (o->object.flags & OBJECT_COMPRESSED)
1655                         printf("Flags: COMPRESSED\n");
1656
1657                 if (p == le64toh(f->header->tail_object_offset))
1658                         p = 0;
1659                 else
1660                         p = p + ALIGN64(le64toh(o->object.size));
1661         }
1662
1663         return;
1664 fail:
1665         log_error("File corrupt");
1666 }
1667
1668 int journal_file_open(
1669                 const char *fname,
1670                 int flags,
1671                 mode_t mode,
1672                 JournalFile *template,
1673                 JournalFile **ret) {
1674
1675         JournalFile *f;
1676         int r;
1677         bool newly_created = false;
1678
1679         assert(fname);
1680
1681         if ((flags & O_ACCMODE) != O_RDONLY &&
1682             (flags & O_ACCMODE) != O_RDWR)
1683                 return -EINVAL;
1684
1685         f = new0(JournalFile, 1);
1686         if (!f)
1687                 return -ENOMEM;
1688
1689         f->fd = -1;
1690         f->flags = flags;
1691         f->mode = mode;
1692         f->writable = (flags & O_ACCMODE) != O_RDONLY;
1693         f->prot = prot_from_flags(flags);
1694
1695         f->metrics.max_size = DEFAULT_MAX_SIZE;
1696         f->metrics.min_size = DEFAULT_MIN_SIZE;
1697         f->metrics.keep_free = DEFAULT_KEEP_FREE;
1698
1699         f->path = strdup(fname);
1700         if (!f->path) {
1701                 r = -ENOMEM;
1702                 goto fail;
1703         }
1704
1705         f->fd = open(f->path, f->flags|O_CLOEXEC, f->mode);
1706         if (f->fd < 0) {
1707                 r = -errno;
1708                 goto fail;
1709         }
1710
1711         if (fstat(f->fd, &f->last_stat) < 0) {
1712                 r = -errno;
1713                 goto fail;
1714         }
1715
1716         if (f->last_stat.st_size == 0 && f->writable) {
1717                 newly_created = true;
1718
1719                 r = journal_file_init_header(f, template);
1720                 if (r < 0)
1721                         goto fail;
1722
1723                 if (fstat(f->fd, &f->last_stat) < 0) {
1724                         r = -errno;
1725                         goto fail;
1726                 }
1727         }
1728
1729         if (f->last_stat.st_size < (off_t) sizeof(Header)) {
1730                 r = -EIO;
1731                 goto fail;
1732         }
1733
1734         f->header = mmap(NULL, PAGE_ALIGN(sizeof(Header)), prot_from_flags(flags), MAP_SHARED, f->fd, 0);
1735         if (f->header == MAP_FAILED) {
1736                 f->header = NULL;
1737                 r = -errno;
1738                 goto fail;
1739         }
1740
1741         if (!newly_created) {
1742                 r = journal_file_verify_header(f);
1743                 if (r < 0)
1744                         goto fail;
1745         }
1746
1747         if (f->writable) {
1748                 r = journal_file_refresh_header(f);
1749                 if (r < 0)
1750                         goto fail;
1751         }
1752
1753         if (newly_created) {
1754
1755                 r = journal_file_setup_field_hash_table(f);
1756                 if (r < 0)
1757                         goto fail;
1758
1759                 r = journal_file_setup_data_hash_table(f);
1760                 if (r < 0)
1761                         goto fail;
1762         }
1763
1764         r = journal_file_map_field_hash_table(f);
1765         if (r < 0)
1766                 goto fail;
1767
1768         r = journal_file_map_data_hash_table(f);
1769         if (r < 0)
1770                 goto fail;
1771
1772         if (ret)
1773                 *ret = f;
1774
1775         return 0;
1776
1777 fail:
1778         journal_file_close(f);
1779
1780         return r;
1781 }
1782
1783 int journal_file_rotate(JournalFile **f) {
1784         char *p;
1785         size_t l;
1786         JournalFile *old_file, *new_file = NULL;
1787         int r;
1788
1789         assert(f);
1790         assert(*f);
1791
1792         old_file = *f;
1793
1794         if (!old_file->writable)
1795                 return -EINVAL;
1796
1797         if (!endswith(old_file->path, ".journal"))
1798                 return -EINVAL;
1799
1800         l = strlen(old_file->path);
1801
1802         p = new(char, l + 1 + 16 + 1 + 32 + 1 + 16 + 1);
1803         if (!p)
1804                 return -ENOMEM;
1805
1806         memcpy(p, old_file->path, l - 8);
1807         p[l-8] = '@';
1808         sd_id128_to_string(old_file->header->seqnum_id, p + l - 8 + 1);
1809         snprintf(p + l - 8 + 1 + 32, 1 + 16 + 1 + 16 + 8 + 1,
1810                  "-%016llx-%016llx.journal",
1811                  (unsigned long long) le64toh((*f)->header->seqnum),
1812                  (unsigned long long) le64toh((*f)->header->tail_entry_realtime));
1813
1814         r = rename(old_file->path, p);
1815         free(p);
1816
1817         if (r < 0)
1818                 return -errno;
1819
1820         old_file->header->state = le32toh(STATE_ARCHIVED);
1821
1822         r = journal_file_open(old_file->path, old_file->flags, old_file->mode, old_file, &new_file);
1823         journal_file_close(old_file);
1824
1825         *f = new_file;
1826         return r;
1827 }
1828
1829 struct vacuum_info {
1830         off_t usage;
1831         char *filename;
1832
1833         uint64_t realtime;
1834         sd_id128_t seqnum_id;
1835         uint64_t seqnum;
1836 };
1837
1838 static int vacuum_compare(const void *_a, const void *_b) {
1839         const struct vacuum_info *a, *b;
1840
1841         a = _a;
1842         b = _b;
1843
1844         if (sd_id128_equal(a->seqnum_id, b->seqnum_id)) {
1845                 if (a->seqnum < b->seqnum)
1846                         return -1;
1847                 else if (a->seqnum > b->seqnum)
1848                         return 1;
1849                 else
1850                         return 0;
1851         }
1852
1853         if (a->realtime < b->realtime)
1854                 return -1;
1855         else if (a->realtime > b->realtime)
1856                 return 1;
1857         else
1858                 return memcmp(&a->seqnum_id, &b->seqnum_id, 16);
1859 }
1860
1861 int journal_directory_vacuum(const char *directory, uint64_t max_use, uint64_t min_free) {
1862         DIR *d;
1863         int r = 0;
1864         struct vacuum_info *list = NULL;
1865         unsigned n_list = 0, n_allocated = 0, i;
1866         uint64_t sum = 0;
1867
1868         assert(directory);
1869
1870         if (max_use <= 0)
1871                 max_use = DEFAULT_MAX_USE;
1872
1873         d = opendir(directory);
1874         if (!d)
1875                 return -errno;
1876
1877         for (;;) {
1878                 int k;
1879                 struct dirent buf, *de;
1880                 size_t q;
1881                 struct stat st;
1882                 char *p;
1883                 unsigned long long seqnum, realtime;
1884                 sd_id128_t seqnum_id;
1885
1886                 k = readdir_r(d, &buf, &de);
1887                 if (k != 0) {
1888                         r = -k;
1889                         goto finish;
1890                 }
1891
1892                 if (!de)
1893                         break;
1894
1895                 if (!dirent_is_file_with_suffix(de, ".journal"))
1896                         continue;
1897
1898                 q = strlen(de->d_name);
1899
1900                 if (q < 1 + 32 + 1 + 16 + 1 + 16 + 8)
1901                         continue;
1902
1903                 if (de->d_name[q-8-16-1] != '-' ||
1904                     de->d_name[q-8-16-1-16-1] != '-' ||
1905                     de->d_name[q-8-16-1-16-1-32-1] != '@')
1906                         continue;
1907
1908                 if (fstatat(dirfd(d), de->d_name, &st, AT_SYMLINK_NOFOLLOW) < 0)
1909                         continue;
1910
1911                 if (!S_ISREG(st.st_mode))
1912                         continue;
1913
1914                 p = strdup(de->d_name);
1915                 if (!p) {
1916                         r = -ENOMEM;
1917                         goto finish;
1918                 }
1919
1920                 de->d_name[q-8-16-1-16-1] = 0;
1921                 if (sd_id128_from_string(de->d_name + q-8-16-1-16-1-32, &seqnum_id) < 0) {
1922                         free(p);
1923                         continue;
1924                 }
1925
1926                 if (sscanf(de->d_name + q-8-16-1-16, "%16llx-%16llx.journal", &seqnum, &realtime) != 2) {
1927                         free(p);
1928                         continue;
1929                 }
1930
1931                 if (n_list >= n_allocated) {
1932                         struct vacuum_info *j;
1933
1934                         n_allocated = MAX(n_allocated * 2U, 8U);
1935                         j = realloc(list, n_allocated * sizeof(struct vacuum_info));
1936                         if (!j) {
1937                                 free(p);
1938                                 r = -ENOMEM;
1939                                 goto finish;
1940                         }
1941
1942                         list = j;
1943                 }
1944
1945                 list[n_list].filename = p;
1946                 list[n_list].usage = (uint64_t) st.st_blksize * (uint64_t) st.st_blocks;
1947                 list[n_list].seqnum = seqnum;
1948                 list[n_list].realtime = realtime;
1949                 list[n_list].seqnum_id = seqnum_id;
1950
1951                 sum += list[n_list].usage;
1952
1953                 n_list ++;
1954         }
1955
1956         qsort(list, n_list, sizeof(struct vacuum_info), vacuum_compare);
1957
1958         for(i = 0; i < n_list; i++) {
1959                 struct statvfs ss;
1960
1961                 if (fstatvfs(dirfd(d), &ss) < 0) {
1962                         r = -errno;
1963                         goto finish;
1964                 }
1965
1966                 if (sum <= max_use &&
1967                     (uint64_t) ss.f_bavail * (uint64_t) ss.f_bsize >= min_free)
1968                         break;
1969
1970                 if (unlinkat(dirfd(d), list[i].filename, 0) >= 0) {
1971                         log_debug("Deleted archived journal %s/%s.", directory, list[i].filename);
1972                         sum -= list[i].usage;
1973                 } else if (errno != ENOENT)
1974                         log_warning("Failed to delete %s/%s: %m", directory, list[i].filename);
1975         }
1976
1977 finish:
1978         for (i = 0; i < n_list; i++)
1979                 free(list[i].filename);
1980
1981         free(list);
1982
1983         if (d)
1984                 closedir(d);
1985
1986         return r;
1987 }