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