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 static 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 = new(EntryItem, n_iovec);
 993         if (!items)
 994                 return -ENOMEM;
 995
 996         for (i = 0; i < n_iovec; i++) {
 997                 uint64_t p;
 998                 Object *o;
 999
1000                 r = journal_file_append_data(f, iovec[i].iov_base, iovec[i].iov_len, &o, &p);
1001                 if (r < 0)
1002                         goto finish;
1003
1004                 xor_hash ^= le64toh(o->data.hash);
1005                 items[i].object_offset = htole64(p);
1006                 items[i].hash = o->data.hash;
1007         }
1008
1009         r = journal_file_append_entry_internal(f, ts, xor_hash, items, n_iovec, seqnum, ret, offset);
1010
1011         journal_file_post_change(f);
1012
1013 finish:
1014         free(items);
1015
1016         return r;
1017 }
1018
1019 static int generic_array_get(JournalFile *f,
1020                              uint64_t first,
1021                              uint64_t i,
1022                              Object **ret, uint64_t *offset) {
1023
1024         Object *o;
1025         uint64_t p, a;
1026         int r;
1027
1028         assert(f);
1029
1030         a = first;
1031         while (a > 0) {
1032                 uint64_t n;
1033
1034                 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
1035                 if (r < 0)
1036                         return r;
1037
1038                 n = journal_file_entry_array_n_items(o);
1039                 if (i < n) {
1040                         p = le64toh(o->entry_array.items[i]);
1041                         break;
1042                 }
1043
1044                 i -= n;
1045                 a = le64toh(o->entry_array.next_entry_array_offset);
1046         }
1047
1048         if (a <= 0 || p <= 0)
1049                 return 0;
1050
1051         r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
1052         if (r < 0)
1053                 return r;
1054
1055         if (ret)
1056                 *ret = o;
1057
1058         if (offset)
1059                 *offset = p;
1060
1061         return 1;
1062 }
1063
1064 static int generic_array_get_plus_one(JournalFile *f,
1065                                       uint64_t extra,
1066                                       uint64_t first,
1067                                       uint64_t i,
1068                                       Object **ret, uint64_t *offset) {
1069
1070         Object *o;
1071
1072         assert(f);
1073
1074         if (i == 0) {
1075                 int r;
1076
1077                 r = journal_file_move_to_object(f, OBJECT_ENTRY, extra, &o);
1078                 if (r < 0)
1079                         return r;
1080
1081                 if (ret)
1082                         *ret = o;
1083
1084                 if (offset)
1085                         *offset = extra;
1086
1087                 return 1;
1088         }
1089
1090         return generic_array_get(f, first, i-1, ret, offset);
1091 }
1092
1093 enum {
1094         TEST_FOUND,
1095         TEST_LEFT,
1096         TEST_RIGHT
1097 };
1098
1099 static int generic_array_bisect(JournalFile *f,
1100                                 uint64_t first,
1101                                 uint64_t n,
1102                                 uint64_t needle,
1103                                 int (*test_object)(JournalFile *f, uint64_t p, uint64_t needle),
1104                                 direction_t direction,
1105                                 Object **ret,
1106                                 uint64_t *offset,
1107                                 uint64_t *idx) {
1108
1109         uint64_t a, p, t = 0, i = 0, last_p = 0;
1110         bool subtract_one = false;
1111         Object *o, *array = NULL;
1112         int r;
1113
1114         assert(f);
1115         assert(test_object);
1116
1117         a = first;
1118         while (a > 0) {
1119                 uint64_t left, right, k, lp;
1120
1121                 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &array);
1122                 if (r < 0)
1123                         return r;
1124
1125                 k = journal_file_entry_array_n_items(array);
1126                 right = MIN(k, n);
1127                 if (right <= 0)
1128                         return 0;
1129
1130                 i = right - 1;
1131                 lp = p = le64toh(array->entry_array.items[i]);
1132                 if (p <= 0)
1133                         return -EBADMSG;
1134
1135                 r = test_object(f, p, needle);
1136                 if (r < 0)
1137                         return r;
1138
1139                 if (r == TEST_FOUND)
1140                         r = direction == DIRECTION_DOWN ? TEST_RIGHT : TEST_LEFT;
1141
1142                 if (r == TEST_RIGHT) {
1143                         left = 0;
1144                         right -= 1;
1145                         for (;;) {
1146                                 if (left == right) {
1147                                         if (direction == DIRECTION_UP)
1148                                                 subtract_one = true;
1149
1150                                         i = left;
1151                                         goto found;
1152                                 }
1153
1154                                 assert(left < right);
1155
1156                                 i = (left + right) / 2;
1157                                 p = le64toh(array->entry_array.items[i]);
1158                                 if (p <= 0)
1159                                         return -EBADMSG;
1160
1161                                 r = test_object(f, p, needle);
1162                                 if (r < 0)
1163                                         return r;
1164
1165                                 if (r == TEST_FOUND)
1166                                         r = direction == DIRECTION_DOWN ? TEST_RIGHT : TEST_LEFT;
1167
1168                                 if (r == TEST_RIGHT)
1169                                         right = i;
1170                                 else
1171                                         left = i + 1;
1172                         }
1173                 }
1174
1175                 if (k > n)
1176                         return 0;
1177
1178                 last_p = lp;
1179
1180                 n -= k;
1181                 t += k;
1182                 a = le64toh(array->entry_array.next_entry_array_offset);
1183         }
1184
1185         return 0;
1186
1187 found:
1188         if (subtract_one && t == 0 && i == 0)
1189                 return 0;
1190
1191         if (subtract_one && i == 0)
1192                 p = last_p;
1193         else if (subtract_one)
1194                 p = le64toh(array->entry_array.items[i-1]);
1195         else
1196                 p = le64toh(array->entry_array.items[i]);
1197
1198         r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
1199         if (r < 0)
1200                 return r;
1201
1202         if (ret)
1203                 *ret = o;
1204
1205         if (offset)
1206                 *offset = p;
1207
1208         if (idx)
1209                 *idx = t + i - (subtract_one ? 1 : 0);
1210
1211         return 1;
1212 }
1213
1214 static int generic_array_bisect_plus_one(JournalFile *f,
1215                                          uint64_t extra,
1216                                          uint64_t first,
1217                                          uint64_t n,
1218                                          uint64_t needle,
1219                                          int (*test_object)(JournalFile *f, uint64_t p, uint64_t needle),
1220                                          direction_t direction,
1221                                          Object **ret,
1222                                          uint64_t *offset,
1223                                          uint64_t *idx) {
1224
1225         int r;
1226
1227         assert(f);
1228         assert(test_object);
1229
1230         if (n <= 0)
1231                 return 0;
1232
1233         /* This bisects the array in object 'first', but first checks
1234          * an extra  */
1235         r = test_object(f, extra, needle);
1236         if (r < 0)
1237                 return r;
1238         else if (r == TEST_FOUND) {
1239                 Object *o;
1240
1241                 r = journal_file_move_to_object(f, OBJECT_ENTRY, extra, &o);
1242                 if (r < 0)
1243                         return r;
1244
1245                 if (ret)
1246                         *ret = o;
1247
1248                 if (offset)
1249                         *offset = extra;
1250
1251                 if (idx)
1252                         *idx = 0;
1253
1254                 return 1;
1255         } else if (r == TEST_RIGHT)
1256                 return 0;
1257
1258         r = generic_array_bisect(f, first, n-1, needle, test_object, direction, ret, offset, idx);
1259
1260         if (r > 0)
1261                 (*idx) ++;
1262
1263         return r;
1264 }
1265
1266 static int test_object_seqnum(JournalFile *f, uint64_t p, uint64_t needle) {
1267         Object *o;
1268         int r;
1269
1270         assert(f);
1271         assert(p > 0);
1272
1273         r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
1274         if (r < 0)
1275                 return r;
1276
1277         if (le64toh(o->entry.seqnum) == needle)
1278                 return TEST_FOUND;
1279         else if (le64toh(o->entry.seqnum) < needle)
1280                 return TEST_LEFT;
1281         else
1282                 return TEST_RIGHT;
1283 }
1284
1285 int journal_file_move_to_entry_by_seqnum(
1286                 JournalFile *f,
1287                 uint64_t seqnum,
1288                 direction_t direction,
1289                 Object **ret,
1290                 uint64_t *offset) {
1291
1292         return generic_array_bisect(f,
1293                                     le64toh(f->header->entry_array_offset),
1294                                     le64toh(f->header->n_entries),
1295                                     seqnum,
1296                                     test_object_seqnum,
1297                                     direction,
1298                                     ret, offset, NULL);
1299 }
1300
1301 static int test_object_realtime(JournalFile *f, uint64_t p, uint64_t needle) {
1302         Object *o;
1303         int r;
1304
1305         assert(f);
1306         assert(p > 0);
1307
1308         r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
1309         if (r < 0)
1310                 return r;
1311
1312         if (le64toh(o->entry.realtime) == needle)
1313                 return TEST_FOUND;
1314         else if (le64toh(o->entry.realtime) < needle)
1315                 return TEST_LEFT;
1316         else
1317                 return TEST_RIGHT;
1318 }
1319
1320 int journal_file_move_to_entry_by_realtime(
1321                 JournalFile *f,
1322                 uint64_t realtime,
1323                 direction_t direction,
1324                 Object **ret,
1325                 uint64_t *offset) {
1326
1327         return generic_array_bisect(f,
1328                                     le64toh(f->header->entry_array_offset),
1329                                     le64toh(f->header->n_entries),
1330                                     realtime,
1331                                     test_object_realtime,
1332                                     direction,
1333                                     ret, offset, NULL);
1334 }
1335
1336 static int test_object_monotonic(JournalFile *f, uint64_t p, uint64_t needle) {
1337         Object *o;
1338         int r;
1339
1340         assert(f);
1341         assert(p > 0);
1342
1343         r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
1344         if (r < 0)
1345                 return r;
1346
1347         if (le64toh(o->entry.monotonic) == needle)
1348                 return TEST_FOUND;
1349         else if (le64toh(o->entry.monotonic) < needle)
1350                 return TEST_LEFT;
1351         else
1352                 return TEST_RIGHT;
1353 }
1354
1355 int journal_file_move_to_entry_by_monotonic(
1356                 JournalFile *f,
1357                 sd_id128_t boot_id,
1358                 uint64_t monotonic,
1359                 direction_t direction,
1360                 Object **ret,
1361                 uint64_t *offset) {
1362
1363         char t[8+32+1] = "_BOOT_ID=";
1364         Object *o;
1365         int r;
1366
1367         sd_id128_to_string(boot_id, t + 8);
1368
1369         r = journal_file_find_data_object(f, t, strlen(t), &o, NULL);
1370         if (r < 0)
1371                 return r;
1372         else if (r == 0)
1373                 return -ENOENT;
1374
1375         return generic_array_bisect_plus_one(f,
1376                                              le64toh(o->data.entry_offset),
1377                                              le64toh(o->data.entry_array_offset),
1378                                              le64toh(o->data.n_entries),
1379                                              monotonic,
1380                                              test_object_monotonic,
1381                                              direction,
1382                                              ret, offset, NULL);
1383 }
1384
1385 static int test_object_offset(JournalFile *f, uint64_t p, uint64_t needle) {
1386         assert(f);
1387         assert(p > 0);
1388
1389         if (p == needle)
1390                 return TEST_FOUND;
1391         else if (p < needle)
1392                 return TEST_LEFT;
1393         else
1394                 return TEST_RIGHT;
1395 }
1396
1397 int journal_file_next_entry(
1398                 JournalFile *f,
1399                 Object *o, uint64_t p,
1400                 direction_t direction,
1401                 Object **ret, uint64_t *offset) {
1402
1403         uint64_t i, n;
1404         int r;
1405
1406         assert(f);
1407         assert(p > 0 || !o);
1408
1409         n = le64toh(f->header->n_entries);
1410         if (n <= 0)
1411                 return 0;
1412
1413         if (!o)
1414                 i = direction == DIRECTION_DOWN ? 0 : n - 1;
1415         else {
1416                 if (o->object.type != OBJECT_ENTRY)
1417                         return -EINVAL;
1418
1419                 r = generic_array_bisect(f,
1420                                          le64toh(f->header->entry_array_offset),
1421                                          le64toh(f->header->n_entries),
1422                                          p,
1423                                          test_object_offset,
1424                                          DIRECTION_DOWN,
1425                                          NULL, NULL,
1426                                          &i);
1427                 if (r <= 0)
1428                         return r;
1429
1430                 if (direction == DIRECTION_DOWN) {
1431                         if (i >= n - 1)
1432                                 return 0;
1433
1434                         i++;
1435                 } else {
1436                         if (i <= 0)
1437                                 return 0;
1438
1439                         i--;
1440                 }
1441         }
1442
1443         /* And jump to it */
1444         return generic_array_get(f,
1445                                  le64toh(f->header->entry_array_offset),
1446                                  i,
1447                                  ret, offset);
1448 }
1449
1450 int journal_file_skip_entry(
1451                 JournalFile *f,
1452                 Object *o, uint64_t p,
1453                 int64_t skip,
1454                 Object **ret, uint64_t *offset) {
1455
1456         uint64_t i, n;
1457         int r;
1458
1459         assert(f);
1460         assert(o);
1461         assert(p > 0);
1462
1463         if (o->object.type != OBJECT_ENTRY)
1464                 return -EINVAL;
1465
1466         r = generic_array_bisect(f,
1467                                  le64toh(f->header->entry_array_offset),
1468                                  le64toh(f->header->n_entries),
1469                                  p,
1470                                  test_object_offset,
1471                                  DIRECTION_DOWN,
1472                                  NULL, NULL,
1473                                  &i);
1474         if (r <= 0)
1475                 return r;
1476
1477         /* Calculate new index */
1478         if (skip < 0) {
1479                 if ((uint64_t) -skip >= i)
1480                         i = 0;
1481                 else
1482                         i = i - (uint64_t) -skip;
1483         } else
1484                 i  += (uint64_t) skip;
1485
1486         n = le64toh(f->header->n_entries);
1487         if (n <= 0)
1488                 return -EBADMSG;
1489
1490         if (i >= n)
1491                 i = n-1;
1492
1493         return generic_array_get(f,
1494                                  le64toh(f->header->entry_array_offset),
1495                                  i,
1496                                  ret, offset);
1497 }
1498
1499 int journal_file_next_entry_for_data(
1500                 JournalFile *f,
1501                 Object *o, uint64_t p,
1502                 uint64_t data_offset,
1503                 direction_t direction,
1504                 Object **ret, uint64_t *offset) {
1505
1506         uint64_t n, i;
1507         int r;
1508         Object *d;
1509
1510         assert(f);
1511         assert(p > 0 || !o);
1512
1513         r = journal_file_move_to_object(f, OBJECT_DATA, data_offset, &d);
1514         if (r < 0)
1515                 return r;
1516
1517         n = le64toh(d->data.n_entries);
1518         if (n <= 0)
1519                 return n;
1520
1521         if (!o)
1522                 i = direction == DIRECTION_DOWN ? 0 : n - 1;
1523         else {
1524                 if (o->object.type != OBJECT_ENTRY)
1525                         return -EINVAL;
1526
1527                 r = generic_array_bisect_plus_one(f,
1528                                                   le64toh(d->data.entry_offset),
1529                                                   le64toh(d->data.entry_array_offset),
1530                                                   le64toh(d->data.n_entries),
1531                                                   p,
1532                                                   test_object_offset,
1533                                                   DIRECTION_DOWN,
1534                                                   NULL, NULL,
1535                                                   &i);
1536
1537                 if (r <= 0)
1538                         return r;
1539
1540                 if (direction == DIRECTION_DOWN) {
1541                         if (i >= n - 1)
1542                                 return 0;
1543
1544                         i++;
1545                 } else {
1546                         if (i <= 0)
1547                                 return 0;
1548
1549                         i--;
1550                 }
1551
1552         }
1553
1554         return generic_array_get_plus_one(f,
1555                                           le64toh(d->data.entry_offset),
1556                                           le64toh(d->data.entry_array_offset),
1557                                           i,
1558                                           ret, offset);
1559 }
1560
1561 int journal_file_move_to_entry_by_seqnum_for_data(
1562                 JournalFile *f,
1563                 uint64_t data_offset,
1564                 uint64_t seqnum,
1565                 direction_t direction,
1566                 Object **ret, uint64_t *offset) {
1567
1568         Object *d;
1569         int r;
1570
1571         r = journal_file_move_to_object(f, OBJECT_DATA, data_offset, &d);
1572         if (r <= 0)
1573                 return r;
1574
1575         return generic_array_bisect_plus_one(f,
1576                                              le64toh(d->data.entry_offset),
1577                                              le64toh(d->data.entry_array_offset),
1578                                              le64toh(d->data.n_entries),
1579                                              seqnum,
1580                                              test_object_seqnum,
1581                                              direction,
1582                                              ret, offset, NULL);
1583 }
1584
1585 int journal_file_move_to_entry_by_realtime_for_data(
1586                 JournalFile *f,
1587                 uint64_t data_offset,
1588                 uint64_t realtime,
1589                 direction_t direction,
1590                 Object **ret, uint64_t *offset) {
1591
1592         Object *d;
1593         int r;
1594
1595         r = journal_file_move_to_object(f, OBJECT_DATA, data_offset, &d);
1596         if (r <= 0)
1597                 return r;
1598
1599         return generic_array_bisect_plus_one(f,
1600                                              le64toh(d->data.entry_offset),
1601                                              le64toh(d->data.entry_array_offset),
1602                                              le64toh(d->data.n_entries),
1603                                              realtime,
1604                                              test_object_realtime,
1605                                              direction,
1606                                              ret, offset, NULL);
1607 }
1608
1609 void journal_file_dump(JournalFile *f) {
1610         char a[33], b[33], c[33];
1611         Object *o;
1612         int r;
1613         uint64_t p;
1614
1615         assert(f);
1616
1617         printf("File Path: %s\n"
1618                "File ID: %s\n"
1619                "Machine ID: %s\n"
1620                "Boot ID: %s\n"
1621                "Arena size: %llu\n"
1622                "Objects: %lu\n"
1623                "Entries: %lu\n",
1624                f->path,
1625                sd_id128_to_string(f->header->file_id, a),
1626                sd_id128_to_string(f->header->machine_id, b),
1627                sd_id128_to_string(f->header->boot_id, c),
1628                (unsigned long long) le64toh(f->header->arena_size),
1629                (unsigned long) le64toh(f->header->n_objects),
1630                (unsigned long) le64toh(f->header->n_entries));
1631
1632         p = le64toh(f->header->arena_offset);
1633         while (p != 0) {
1634                 r = journal_file_move_to_object(f, -1, p, &o);
1635                 if (r < 0)
1636                         goto fail;
1637
1638                 switch (o->object.type) {
1639
1640                 case OBJECT_UNUSED:
1641                         printf("Type: OBJECT_UNUSED\n");
1642                         break;
1643
1644                 case OBJECT_DATA:
1645                         printf("Type: OBJECT_DATA\n");
1646                         break;
1647
1648                 case OBJECT_ENTRY:
1649                         printf("Type: OBJECT_ENTRY %llu %llu %llu\n",
1650                                (unsigned long long) le64toh(o->entry.seqnum),
1651                                (unsigned long long) le64toh(o->entry.monotonic),
1652                                (unsigned long long) le64toh(o->entry.realtime));
1653                         break;
1654
1655                 case OBJECT_FIELD_HASH_TABLE:
1656                         printf("Type: OBJECT_FIELD_HASH_TABLE\n");
1657                         break;
1658
1659                 case OBJECT_DATA_HASH_TABLE:
1660                         printf("Type: OBJECT_DATA_HASH_TABLE\n");
1661                         break;
1662
1663                 case OBJECT_ENTRY_ARRAY:
1664                         printf("Type: OBJECT_ENTRY_ARRAY\n");
1665                         break;
1666                 }
1667
1668                 if (o->object.flags & OBJECT_COMPRESSED)
1669                         printf("Flags: COMPRESSED\n");
1670
1671                 if (p == le64toh(f->header->tail_object_offset))
1672                         p = 0;
1673                 else
1674                         p = p + ALIGN64(le64toh(o->object.size));
1675         }
1676
1677         return;
1678 fail:
1679         log_error("File corrupt");
1680 }
1681
1682 int journal_file_open(
1683                 const char *fname,
1684                 int flags,
1685                 mode_t mode,
1686                 JournalFile *template,
1687                 JournalFile **ret) {
1688
1689         JournalFile *f;
1690         int r;
1691         bool newly_created = false;
1692
1693         assert(fname);
1694
1695         if ((flags & O_ACCMODE) != O_RDONLY &&
1696             (flags & O_ACCMODE) != O_RDWR)
1697                 return -EINVAL;
1698
1699         f = new0(JournalFile, 1);
1700         if (!f)
1701                 return -ENOMEM;
1702
1703         f->fd = -1;
1704         f->flags = flags;
1705         f->mode = mode;
1706         f->writable = (flags & O_ACCMODE) != O_RDONLY;
1707         f->prot = prot_from_flags(flags);
1708
1709         f->metrics.max_size = DEFAULT_MAX_SIZE;
1710         f->metrics.min_size = DEFAULT_MIN_SIZE;
1711         f->metrics.keep_free = DEFAULT_KEEP_FREE;
1712
1713         f->path = strdup(fname);
1714         if (!f->path) {
1715                 r = -ENOMEM;
1716                 goto fail;
1717         }
1718
1719         f->fd = open(f->path, f->flags|O_CLOEXEC, f->mode);
1720         if (f->fd < 0) {
1721                 r = -errno;
1722                 goto fail;
1723         }
1724
1725         if (fstat(f->fd, &f->last_stat) < 0) {
1726                 r = -errno;
1727                 goto fail;
1728         }
1729
1730         if (f->last_stat.st_size == 0 && f->writable) {
1731                 newly_created = true;
1732
1733                 r = journal_file_init_header(f, template);
1734                 if (r < 0)
1735                         goto fail;
1736
1737                 if (fstat(f->fd, &f->last_stat) < 0) {
1738                         r = -errno;
1739                         goto fail;
1740                 }
1741         }
1742
1743         if (f->last_stat.st_size < (off_t) sizeof(Header)) {
1744                 r = -EIO;
1745                 goto fail;
1746         }
1747
1748         f->header = mmap(NULL, PAGE_ALIGN(sizeof(Header)), prot_from_flags(flags), MAP_SHARED, f->fd, 0);
1749         if (f->header == MAP_FAILED) {
1750                 f->header = NULL;
1751                 r = -errno;
1752                 goto fail;
1753         }
1754
1755         if (!newly_created) {
1756                 r = journal_file_verify_header(f);
1757                 if (r < 0)
1758                         goto fail;
1759         }
1760
1761         if (f->writable) {
1762                 r = journal_file_refresh_header(f);
1763                 if (r < 0)
1764                         goto fail;
1765         }
1766
1767         if (newly_created) {
1768
1769                 r = journal_file_setup_field_hash_table(f);
1770                 if (r < 0)
1771                         goto fail;
1772
1773                 r = journal_file_setup_data_hash_table(f);
1774                 if (r < 0)
1775                         goto fail;
1776         }
1777
1778         r = journal_file_map_field_hash_table(f);
1779         if (r < 0)
1780                 goto fail;
1781
1782         r = journal_file_map_data_hash_table(f);
1783         if (r < 0)
1784                 goto fail;
1785
1786         if (ret)
1787                 *ret = f;
1788
1789         return 0;
1790
1791 fail:
1792         journal_file_close(f);
1793
1794         return r;
1795 }
1796
1797 int journal_file_rotate(JournalFile **f) {
1798         char *p;
1799         size_t l;
1800         JournalFile *old_file, *new_file = NULL;
1801         int r;
1802
1803         assert(f);
1804         assert(*f);
1805
1806         old_file = *f;
1807
1808         if (!old_file->writable)
1809                 return -EINVAL;
1810
1811         if (!endswith(old_file->path, ".journal"))
1812                 return -EINVAL;
1813
1814         l = strlen(old_file->path);
1815
1816         p = new(char, l + 1 + 16 + 1 + 32 + 1 + 16 + 1);
1817         if (!p)
1818                 return -ENOMEM;
1819
1820         memcpy(p, old_file->path, l - 8);
1821         p[l-8] = '@';
1822         sd_id128_to_string(old_file->header->seqnum_id, p + l - 8 + 1);
1823         snprintf(p + l - 8 + 1 + 32, 1 + 16 + 1 + 16 + 8 + 1,
1824                  "-%016llx-%016llx.journal",
1825                  (unsigned long long) le64toh((*f)->header->seqnum),
1826                  (unsigned long long) le64toh((*f)->header->tail_entry_realtime));
1827
1828         r = rename(old_file->path, p);
1829         free(p);
1830
1831         if (r < 0)
1832                 return -errno;
1833
1834         old_file->header->state = le32toh(STATE_ARCHIVED);
1835
1836         r = journal_file_open(old_file->path, old_file->flags, old_file->mode, old_file, &new_file);
1837         journal_file_close(old_file);
1838
1839         *f = new_file;
1840         return r;
1841 }
1842
1843 struct vacuum_info {
1844         off_t usage;
1845         char *filename;
1846
1847         uint64_t realtime;
1848         sd_id128_t seqnum_id;
1849         uint64_t seqnum;
1850 };
1851
1852 static int vacuum_compare(const void *_a, const void *_b) {
1853         const struct vacuum_info *a, *b;
1854
1855         a = _a;
1856         b = _b;
1857
1858         if (sd_id128_equal(a->seqnum_id, b->seqnum_id)) {
1859                 if (a->seqnum < b->seqnum)
1860                         return -1;
1861                 else if (a->seqnum > b->seqnum)
1862                         return 1;
1863                 else
1864                         return 0;
1865         }
1866
1867         if (a->realtime < b->realtime)
1868                 return -1;
1869         else if (a->realtime > b->realtime)
1870                 return 1;
1871         else
1872                 return memcmp(&a->seqnum_id, &b->seqnum_id, 16);
1873 }
1874
1875 int journal_directory_vacuum(const char *directory, uint64_t max_use, uint64_t min_free) {
1876         DIR *d;
1877         int r = 0;
1878         struct vacuum_info *list = NULL;
1879         unsigned n_list = 0, n_allocated = 0, i;
1880         uint64_t sum = 0;
1881
1882         assert(directory);
1883
1884         if (max_use <= 0)
1885                 max_use = DEFAULT_MAX_USE;
1886
1887         d = opendir(directory);
1888         if (!d)
1889                 return -errno;
1890
1891         for (;;) {
1892                 int k;
1893                 struct dirent buf, *de;
1894                 size_t q;
1895                 struct stat st;
1896                 char *p;
1897                 unsigned long long seqnum, realtime;
1898                 sd_id128_t seqnum_id;
1899
1900                 k = readdir_r(d, &buf, &de);
1901                 if (k != 0) {
1902                         r = -k;
1903                         goto finish;
1904                 }
1905
1906                 if (!de)
1907                         break;
1908
1909                 if (!dirent_is_file_with_suffix(de, ".journal"))
1910                         continue;
1911
1912                 q = strlen(de->d_name);
1913
1914                 if (q < 1 + 32 + 1 + 16 + 1 + 16 + 8)
1915                         continue;
1916
1917                 if (de->d_name[q-8-16-1] != '-' ||
1918                     de->d_name[q-8-16-1-16-1] != '-' ||
1919                     de->d_name[q-8-16-1-16-1-32-1] != '@')
1920                         continue;
1921
1922                 if (fstatat(dirfd(d), de->d_name, &st, AT_SYMLINK_NOFOLLOW) < 0)
1923                         continue;
1924
1925                 if (!S_ISREG(st.st_mode))
1926                         continue;
1927
1928                 p = strdup(de->d_name);
1929                 if (!p) {
1930                         r = -ENOMEM;
1931                         goto finish;
1932                 }
1933
1934                 de->d_name[q-8-16-1-16-1] = 0;
1935                 if (sd_id128_from_string(de->d_name + q-8-16-1-16-1-32, &seqnum_id) < 0) {
1936                         free(p);
1937                         continue;
1938                 }
1939
1940                 if (sscanf(de->d_name + q-8-16-1-16, "%16llx-%16llx.journal", &seqnum, &realtime) != 2) {
1941                         free(p);
1942                         continue;
1943                 }
1944
1945                 if (n_list >= n_allocated) {
1946                         struct vacuum_info *j;
1947
1948                         n_allocated = MAX(n_allocated * 2U, 8U);
1949                         j = realloc(list, n_allocated * sizeof(struct vacuum_info));
1950                         if (!j) {
1951                                 free(p);
1952                                 r = -ENOMEM;
1953                                 goto finish;
1954                         }
1955
1956                         list = j;
1957                 }
1958
1959                 list[n_list].filename = p;
1960                 list[n_list].usage = (uint64_t) st.st_blksize * (uint64_t) st.st_blocks;
1961                 list[n_list].seqnum = seqnum;
1962                 list[n_list].realtime = realtime;
1963                 list[n_list].seqnum_id = seqnum_id;
1964
1965                 sum += list[n_list].usage;
1966
1967                 n_list ++;
1968         }
1969
1970         qsort(list, n_list, sizeof(struct vacuum_info), vacuum_compare);
1971
1972         for(i = 0; i < n_list; i++) {
1973                 struct statvfs ss;
1974
1975                 if (fstatvfs(dirfd(d), &ss) < 0) {
1976                         r = -errno;
1977                         goto finish;
1978                 }
1979
1980                 if (sum <= max_use &&
1981                     (uint64_t) ss.f_bavail * (uint64_t) ss.f_bsize >= min_free)
1982                         break;
1983
1984                 if (unlinkat(dirfd(d), list[i].filename, 0) >= 0) {
1985                         log_debug("Deleted archived journal %s/%s.", directory, list[i].filename);
1986                         sum -= list[i].usage;
1987                 } else if (errno != ENOENT)
1988                         log_warning("Failed to delete %s/%s: %m", directory, list[i].filename);
1989         }
1990
1991 finish:
1992         for (i = 0; i < n_list; i++)
1993                 free(list[i].filename);
1994
1995         free(list);
1996
1997         if (d)
1998                 closedir(d);
1999
2000         return r;
2001 }