}
static int journal_file_allocate(JournalFile *f, uint64_t offset, uint64_t size) {
- uint64_t old_size, new_size, file_size;
+ uint64_t old_size, new_size;
int r;
assert(f);
}
}
+ /* Increase by larger blocks at once */
+ new_size = ((new_size+FILE_SIZE_INCREASE-1) / FILE_SIZE_INCREASE) * FILE_SIZE_INCREASE;
+ if (f->metrics.max_size > 0 && new_size > f->metrics.max_size)
+ new_size = f->metrics.max_size;
+
/* Note that the glibc fallocate() fallback is very
inefficient, hence we try to minimize the allocation area
as we can. */
if (r != 0)
return -r;
- /* Increase the file size a bit further than this, so that we
- * we can create larger memory maps to cache */
- file_size = ((new_size+FILE_SIZE_INCREASE-1) / FILE_SIZE_INCREASE) * FILE_SIZE_INCREASE;
- if (file_size > (uint64_t) f->last_stat.st_size) {
- if (file_size > new_size)
- ftruncate(f->fd, file_size);
-
- if (fstat(f->fd, &f->last_stat) < 0)
- return -errno;
- }
+ if (fstat(f->fd, &f->last_stat) < 0)
+ return -errno;
f->header->arena_size = htole64(new_size - le64toh(f->header->header_size));
static uint64_t minimum_header_size(Object *o) {
- static uint64_t table[] = {
+ static const uint64_t table[] = {
[OBJECT_DATA] = sizeof(DataObject),
[OBJECT_FIELD] = sizeof(FieldObject),
[OBJECT_ENTRY] = sizeof(EntryObject),
if (r < 0)
return r;
- eq = memchr(data, '=', size);
+ if (!data)
+ eq = NULL;
+ else
+ eq = memchr(data, '=', size);
if (eq && eq > data) {
uint64_t fp;
Object *fo;
uint64_t array; /* the cached array */
uint64_t begin; /* the first item in the cached array */
uint64_t total; /* the total number of items in all arrays before this one in the chain */
+ uint64_t last_index; /* the last index we looked at, to optimize locality when bisecting */
} ChainCacheItem;
static void chain_cache_put(
uint64_t first,
uint64_t array,
uint64_t begin,
- uint64_t total) {
+ uint64_t total,
+ uint64_t last_index) {
if (!ci) {
/* If the chain item to cache for this chain is the
ci->array = array;
ci->begin = begin;
ci->total = total;
+ ci->last_index = last_index;
}
-static int generic_array_get(JournalFile *f,
- uint64_t first,
- uint64_t i,
- Object **ret, uint64_t *offset) {
+static int generic_array_get(
+ JournalFile *f,
+ uint64_t first,
+ uint64_t i,
+ Object **ret, uint64_t *offset) {
Object *o;
uint64_t p = 0, a, t = 0;
found:
/* Let's cache this item for the next invocation */
- chain_cache_put(f->chain_cache, ci, first, a, o->entry_array.items[0], t);
+ chain_cache_put(f->chain_cache, ci, first, a, o->entry_array.items[0], t, i);
r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
if (r < 0)
return 1;
}
-static int generic_array_get_plus_one(JournalFile *f,
- uint64_t extra,
- uint64_t first,
- uint64_t i,
- Object **ret, uint64_t *offset) {
+static int generic_array_get_plus_one(
+ JournalFile *f,
+ uint64_t extra,
+ uint64_t first,
+ uint64_t i,
+ Object **ret, uint64_t *offset) {
Object *o;
TEST_RIGHT
};
-static int generic_array_bisect(JournalFile *f,
- uint64_t first,
- uint64_t n,
- uint64_t needle,
- int (*test_object)(JournalFile *f, uint64_t p, uint64_t needle),
- direction_t direction,
- Object **ret,
- uint64_t *offset,
- uint64_t *idx) {
-
- uint64_t a, p, t = 0, i = 0, last_p = 0;
+static int generic_array_bisect(
+ JournalFile *f,
+ uint64_t first,
+ uint64_t n,
+ uint64_t needle,
+ int (*test_object)(JournalFile *f, uint64_t p, uint64_t needle),
+ direction_t direction,
+ Object **ret,
+ uint64_t *offset,
+ uint64_t *idx) {
+
+ uint64_t a, p, t = 0, i = 0, last_p = 0, last_index = (uint64_t) -1;
bool subtract_one = false;
Object *o, *array = NULL;
int r;
return r;
if (r == TEST_LEFT) {
- /* OK, what we are looking for is right of th
+ /* OK, what we are looking for is right of the
* begin of this EntryArray, so let's jump
* straight to previously cached array in the
* chain */
a = ci->array;
n -= ci->total;
t = ci->total;
+ last_index = ci->last_index;
}
}
if (r == TEST_RIGHT) {
left = 0;
right -= 1;
+
+ if (last_index != (uint64_t) -1) {
+ assert(last_index <= right);
+
+ /* If we cached the last index we
+ * looked at, let's try to not to jump
+ * too wildly around and see if we can
+ * limit the range to look at early to
+ * the immediate neighbors of the last
+ * index we looked at. */
+
+ if (last_index > 0) {
+ uint64_t x = last_index - 1;
+
+ p = le64toh(array->entry_array.items[x]);
+ if (p <= 0)
+ return -EBADMSG;
+
+ r = test_object(f, p, needle);
+ if (r < 0)
+ return r;
+
+ if (r == TEST_FOUND)
+ r = direction == DIRECTION_DOWN ? TEST_RIGHT : TEST_LEFT;
+
+ if (r == TEST_RIGHT)
+ right = x;
+ else
+ left = x + 1;
+ }
+
+ if (last_index < right) {
+ uint64_t y = last_index + 1;
+
+ p = le64toh(array->entry_array.items[y]);
+ if (p <= 0)
+ return -EBADMSG;
+
+ r = test_object(f, p, needle);
+ if (r < 0)
+ return r;
+
+ if (r == TEST_FOUND)
+ r = direction == DIRECTION_DOWN ? TEST_RIGHT : TEST_LEFT;
+
+ if (r == TEST_RIGHT)
+ right = y;
+ else
+ left = y + 1;
+ }
+ }
+
for (;;) {
if (left == right) {
if (direction == DIRECTION_UP)
}
assert(left < right);
-
i = (left + right) / 2;
+
p = le64toh(array->entry_array.items[i]);
if (p <= 0)
return -EBADMSG;
n -= k;
t += k;
+ last_index = (uint64_t) -1;
a = le64toh(array->entry_array.next_entry_array_offset);
}
return 0;
/* Let's cache this item for the next invocation */
- chain_cache_put(f->chain_cache, ci, first, a, array->entry_array.items[0], t);
+ chain_cache_put(f->chain_cache, ci, first, a, array->entry_array.items[0], t, subtract_one ? (i > 0 ? i-1 : (uint64_t) -1) : i);
if (subtract_one && i == 0)
p = last_p;
return 1;
}
-static int generic_array_bisect_plus_one(JournalFile *f,
- uint64_t extra,
- uint64_t first,
- uint64_t n,
- uint64_t needle,
- int (*test_object)(JournalFile *f, uint64_t p, uint64_t needle),
- direction_t direction,
- Object **ret,
- uint64_t *offset,
- uint64_t *idx) {
+
+static int generic_array_bisect_plus_one(
+ JournalFile *f,
+ uint64_t extra,
+ uint64_t first,
+ uint64_t n,
+ uint64_t needle,
+ int (*test_object)(JournalFile *f, uint64_t p, uint64_t needle),
+ direction_t direction,
+ Object **ret,
+ uint64_t *offset,
+ uint64_t *idx) {
int r;
bool step_back = false;
ts.monotonic = le64toh(o->entry.monotonic);
ts.realtime = le64toh(o->entry.realtime);
- if (to->tail_entry_monotonic_valid &&
- ts.monotonic < le64toh(to->header->tail_entry_monotonic))
- return -EINVAL;
-
n = journal_file_entry_n_items(o);
- items = alloca(sizeof(EntryItem) * n);
+ /* alloca() can't take 0, hence let's allocate at least one */
+ items = alloca(sizeof(EntryItem) * MAX(1u, n));
for (i = 0; i < n; i++) {
uint64_t l, h;
~ianmdlvl / elogind.git / blobdiff