From: Kent Overstreet <kent.overstreet@linux.dev>
To: Eric Biggers <ebiggers@kernel.org>
Cc: Lorenzo Stoakes <lstoakes@gmail.com>,
Christoph Hellwig <hch@infradead.org>,
linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org,
linux-bcachefs@vger.kernel.org,
Kent Overstreet <kent.overstreet@gmail.com>,
Andrew Morton <akpm@linux-foundation.org>,
Uladzislau Rezki <urezki@gmail.com>,
linux-mm@kvack.org
Subject: Re: [PATCH 07/32] mm: Bring back vmalloc_exec
Date: Sun, 14 May 2023 01:45:29 -0400 [thread overview]
Message-ID: <ZGB1eevk/u2ssIBT@moria.home.lan> (raw)
In-Reply-To: <20230513015752.GC3033@quark.localdomain>
On Fri, May 12, 2023 at 06:57:52PM -0700, Eric Biggers wrote:
> First, I wanted to mention that decoding of variable-length fields has been
> extensively studied for decompression algorithms, e.g. for Huffman decoding.
> And it turns out that it can be done branchlessly. The basic idea is that you
> have a branchless refill step that looks like the following:
>
> #define REFILL_BITS_BRANCHLESS() \
> bitbuf |= get_unaligned_u64(p) << bitsleft; \
> p += 7 - ((bitsleft >> 3) & 0x7); \
> bitsleft |= 56;
>
> That branchlessly ensures that 'bitbuf' contains '56 <= bitsleft <= 63' bits.
> Then, the needed number of bits can be removed and returned:
>
> #define READ_BITS(n) \
> REFILL_BITS_BRANCHLESS(); \
> tmp = bitbuf & (((u64)1 << (n)) - 1); \
> bitbuf >>= (n); \
> bitsleft -= (n); \
> tmp
>
> If you're interested, I can give you some references about the above method.
I might be interested in those references, new bit tricks and integer
encodings are always fun :)
> But, I really just wanted to mention it for completeness, since I think you'd
> actually want to go in a slightly different direction, since (a) you have all
> the field widths available from the beginning, as opposed to being interleaved
> into the bitstream itself (as is the case in Huffman decoding for example), so
> you're not limited to serialized decoding of each field, (b) your fields are up
> to 96 bits, and (c) you've selected a bitstream convention that seems to make it
> such that your stream *must* be read in aligned units of u64, so I don't think
> something like REFILL_BITS_BRANCHLESS() could work for you anyway.
>
> What I would suggest instead is preprocessing the list of 6 field lengths to
> create some information that can be used to extract all 6 fields branchlessly
> with no dependencies between different fields. (And you clearly *can* add a
> preprocessing step, as you already have one -- the dynamic code generator.)
>
> So, something like the following:
>
> const struct field_info *info = &format->fields[0];
>
> field0 = (in->u64s[info->word_idx] >> info->shift1) & info->mask;
> field0 |= in->u64s[info->word_idx - 1] >> info->shift2;
>
> ... but with the code for all 6 fields interleaved.
>
> On modern CPUs, I think that would be faster than your current C code.
>
> You could do better by creating variants that are specialized for specific
> common sets of parameters. During "preprocessing", you would select a variant
> and set an enum accordingly. During decoding, you would switch on that enum and
> call the appropriate variant. (This could also be done with a function pointer,
> of course, but indirect calls are slow these days...)
testing random btree updates:
dynamically generated unpack:
rand_insert: 20.0 MiB with 1 threads in 33 sec, 1609 nsec per iter, 607 KiB per sec
old C unpack:
rand_insert: 20.0 MiB with 1 threads in 35 sec, 1672 nsec per iter, 584 KiB per sec
the Eric Biggers special:
rand_insert: 20.0 MiB with 1 threads in 35 sec, 1676 nsec per iter, 583 KiB per sec
Tested two versions of your approach, one without a shift value, one
where we use a shift value to try to avoid unaligned access - second was
perhaps 1% faster
so it's not looking good. This benchmark doesn't even hit on
unpack_key() quite as much as I thought, so the difference is
significant.
diff --git a/fs/bcachefs/bkey.c b/fs/bcachefs/bkey.c
index 6d3a1c096f..128d96766c 100644
--- a/fs/bcachefs/bkey.c
+++ b/fs/bcachefs/bkey.c
@@ -7,6 +7,8 @@
#include "bset.h"
#include "util.h"
+#include <asm/unaligned.h>
+
#undef EBUG_ON
#ifdef DEBUG_BKEYS
@@ -19,9 +21,35 @@ const struct bkey_format bch2_bkey_format_current = BKEY_FORMAT_CURRENT;
struct bkey_format_processed bch2_bkey_format_postprocess(const struct bkey_format f)
{
- return (struct bkey_format_processed) {
- .f = f,
- };
+ struct bkey_format_processed ret = { .f = f, .aligned = true };
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+ unsigned offset = f.key_u64s * 64;
+#else
+ unsigned offset = KEY_PACKED_BITS_START;
+#endif
+
+ for (unsigned i = 0; i < BKEY_NR_FIELDS; i++) {
+ unsigned bits = f.bits_per_field[i];
+
+ if (bits & 7) {
+ ret.aligned = false;
+ break;
+ }
+
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+ offset -= bits;
+#endif
+
+ ret.shift[i] = min(offset & 63, 64 - bits);
+ ret.offset[i] = (offset - ret.shift[i]) / 8;
+ ret.mask[i] = bits ? ~0ULL >> (64 - bits) : 0;
+
+#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
+ offset += bits;
+#endif
+ }
+
+ return ret;
}
void bch2_bkey_packed_to_binary_text(struct printbuf *out,
@@ -191,6 +219,19 @@ static u64 get_inc_field(struct unpack_state *state, unsigned field)
return v + offset;
}
+__always_inline
+static u64 get_aligned_field(const struct bkey_format_processed *f,
+ const struct bkey_packed *in,
+ unsigned field_idx)
+{
+ u64 v = get_unaligned((u64 *) (((u8 *) in->_data) + f->offset[field_idx]));
+
+ v >>= f->shift[field_idx];
+ v &= f->mask[field_idx];
+
+ return v + le64_to_cpu(f->f.field_offset[field_idx]);
+}
+
__always_inline
static bool set_inc_field(struct pack_state *state, unsigned field, u64 v)
{
@@ -269,45 +310,57 @@ bool bch2_bkey_transform(const struct bkey_format *out_f,
return true;
}
-struct bkey __bch2_bkey_unpack_key(const struct bkey_format_processed *format_p,
+struct bkey __bch2_bkey_unpack_key(const struct bkey_format_processed *format,
const struct bkey_packed *in)
{
- const struct bkey_format *format = &format_p->f;
- struct unpack_state state = unpack_state_init(format, in);
struct bkey out;
- EBUG_ON(format->nr_fields != BKEY_NR_FIELDS);
- EBUG_ON(in->u64s < format->key_u64s);
+ EBUG_ON(format->f.nr_fields != BKEY_NR_FIELDS);
+ EBUG_ON(in->u64s < format->f.key_u64s);
EBUG_ON(in->format != KEY_FORMAT_LOCAL_BTREE);
- EBUG_ON(in->u64s - format->key_u64s + BKEY_U64s > U8_MAX);
+ EBUG_ON(in->u64s - format->f.key_u64s + BKEY_U64s > U8_MAX);
- out.u64s = BKEY_U64s + in->u64s - format->key_u64s;
+ out.u64s = BKEY_U64s + in->u64s - format->f.key_u64s;
out.format = KEY_FORMAT_CURRENT;
out.needs_whiteout = in->needs_whiteout;
out.type = in->type;
out.pad[0] = 0;
+ if (likely(format->aligned)) {
+#define x(id, field) out.field = get_aligned_field(format, in, id);
+ bkey_fields()
+#undef x
+ } else {
+ struct unpack_state state = unpack_state_init(&format->f, in);
+
#define x(id, field) out.field = get_inc_field(&state, id);
- bkey_fields()
+ bkey_fields()
#undef x
+ }
return out;
}
-struct bpos __bkey_unpack_pos(const struct bkey_format_processed *format_p,
+struct bpos __bkey_unpack_pos(const struct bkey_format_processed *format,
const struct bkey_packed *in)
{
- const struct bkey_format *format = &format_p->f;
- struct unpack_state state = unpack_state_init(format, in);
struct bpos out;
- EBUG_ON(format->nr_fields != BKEY_NR_FIELDS);
- EBUG_ON(in->u64s < format->key_u64s);
+ EBUG_ON(format->f.nr_fields != BKEY_NR_FIELDS);
+ EBUG_ON(in->u64s < format->f.key_u64s);
EBUG_ON(in->format != KEY_FORMAT_LOCAL_BTREE);
- out.inode = get_inc_field(&state, BKEY_FIELD_INODE);
- out.offset = get_inc_field(&state, BKEY_FIELD_OFFSET);
- out.snapshot = get_inc_field(&state, BKEY_FIELD_SNAPSHOT);
+ if (likely(format->aligned)) {
+ out.inode = get_aligned_field(format, in, BKEY_FIELD_INODE);
+ out.offset = get_aligned_field(format, in, BKEY_FIELD_OFFSET);
+ out.snapshot = get_aligned_field(format, in, BKEY_FIELD_SNAPSHOT);
+ } else {
+ struct unpack_state state = unpack_state_init(&format->f, in);
+
+ out.inode = get_inc_field(&state, BKEY_FIELD_INODE);
+ out.offset = get_inc_field(&state, BKEY_FIELD_OFFSET);
+ out.snapshot = get_inc_field(&state, BKEY_FIELD_SNAPSHOT);
+ }
return out;
}
diff --git a/fs/bcachefs/btree_types.h b/fs/bcachefs/btree_types.h
index 58ce60c37e..38c3ec6852 100644
--- a/fs/bcachefs/btree_types.h
+++ b/fs/bcachefs/btree_types.h
@@ -70,6 +70,10 @@ struct btree_bkey_cached_common {
struct bkey_format_processed {
struct bkey_format f;
+ bool aligned;
+ u8 offset[6];
+ u8 shift[6];
+ u64 mask[6];
};
struct btree {
diff --git a/fs/bcachefs/btree_update_interior.h b/fs/bcachefs/btree_update_interior.h
index dcfd7ceacc..72aedc1e34 100644
--- a/fs/bcachefs/btree_update_interior.h
+++ b/fs/bcachefs/btree_update_interior.h
@@ -181,7 +181,11 @@ static inline void btree_node_reset_sib_u64s(struct btree *b)
static inline void *btree_data_end(struct bch_fs *c, struct btree *b)
{
- return (void *) b->data + btree_bytes(c);
+ /*
+ * __bch2_bkey_unpack_key() may read up to 8 bytes past the end of the
+ * input buffer:
+ */
+ return (void *) b->data + btree_bytes(c) - 8;
}
static inline struct bkey_packed *unwritten_whiteouts_start(struct bch_fs *c,
next prev parent reply other threads:[~2023-05-14 5:45 UTC|newest]
Thread overview: 186+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-05-09 16:56 [PATCH 00/32] bcachefs - a new COW filesystem Kent Overstreet
2023-05-09 16:56 ` [PATCH 01/32] Compiler Attributes: add __flatten Kent Overstreet
2023-05-09 17:04 ` Miguel Ojeda
2023-05-09 17:24 ` Kent Overstreet
2023-05-09 16:56 ` [PATCH 02/32] locking/lockdep: lock_class_is_held() Kent Overstreet
2023-05-09 19:30 ` Peter Zijlstra
2023-05-09 20:11 ` Kent Overstreet
2023-05-09 16:56 ` [PATCH 03/32] locking/lockdep: lockdep_set_no_check_recursion() Kent Overstreet
2023-05-09 19:31 ` Peter Zijlstra
2023-05-09 19:57 ` Kent Overstreet
2023-05-09 20:18 ` Kent Overstreet
2023-05-09 20:27 ` Waiman Long
2023-05-09 20:35 ` Kent Overstreet
2023-05-09 21:37 ` Waiman Long
2023-05-10 8:59 ` Peter Zijlstra
2023-05-10 20:38 ` Kent Overstreet
2023-05-11 8:25 ` Peter Zijlstra
2023-05-11 9:32 ` Kent Overstreet
2023-05-12 20:49 ` Kent Overstreet
2023-05-09 16:56 ` [PATCH 04/32] locking: SIX locks (shared/intent/exclusive) Kent Overstreet
2023-05-11 12:14 ` Jan Engelhardt
2023-05-12 20:58 ` Kent Overstreet
2023-05-12 22:39 ` Jan Engelhardt
2023-05-12 23:26 ` Kent Overstreet
2023-05-12 23:49 ` Randy Dunlap
2023-05-13 0:17 ` Kent Overstreet
2023-05-13 0:45 ` Eric Biggers
2023-05-13 0:51 ` Kent Overstreet
2023-05-14 12:15 ` Jeff Layton
2023-05-15 2:39 ` Kent Overstreet
2023-05-09 16:56 ` [PATCH 05/32] MAINTAINERS: Add entry for six locks Kent Overstreet
2023-05-09 16:56 ` [PATCH 06/32] sched: Add task_struct->faults_disabled_mapping Kent Overstreet
2023-05-10 1:07 ` Jan Kara
2023-05-10 6:18 ` Kent Overstreet
2023-05-23 13:34 ` Jan Kara
2023-05-23 16:21 ` [Cluster-devel] " Christoph Hellwig
2023-05-23 16:35 ` Kent Overstreet
2023-05-24 6:43 ` Christoph Hellwig
2023-05-24 8:09 ` Kent Overstreet
2023-05-25 8:58 ` Christoph Hellwig
2023-05-25 20:50 ` Kent Overstreet
2023-05-26 8:06 ` Christoph Hellwig
2023-05-26 8:34 ` Kent Overstreet
2023-05-25 21:40 ` Kent Overstreet
2023-05-25 22:25 ` Andreas Grünbacher
2023-05-25 23:20 ` Kent Overstreet
2023-05-26 0:05 ` Andreas Grünbacher
2023-05-26 0:39 ` Kent Overstreet
2023-05-26 8:10 ` Christoph Hellwig
2023-05-26 8:38 ` Kent Overstreet
2023-05-23 16:49 ` Kent Overstreet
2023-05-25 8:47 ` Jan Kara
2023-05-25 21:36 ` Kent Overstreet
2023-05-25 22:45 ` Andreas Grünbacher
2023-05-25 22:04 ` Andreas Grünbacher
2023-05-09 16:56 ` [PATCH 07/32] mm: Bring back vmalloc_exec Kent Overstreet
2023-05-09 18:19 ` Lorenzo Stoakes
2023-05-09 20:15 ` Kent Overstreet
2023-05-09 20:46 ` Christoph Hellwig
2023-05-09 21:12 ` Lorenzo Stoakes
2023-05-09 21:29 ` Kent Overstreet
2023-05-10 6:48 ` Eric Biggers
2023-05-12 18:36 ` Kent Overstreet
2023-05-13 1:57 ` Eric Biggers
2023-05-13 19:28 ` Kent Overstreet
2023-05-14 5:45 ` Kent Overstreet [this message]
2023-05-14 18:43 ` Eric Biggers
2023-05-15 5:38 ` Kent Overstreet
2023-05-15 6:13 ` Eric Biggers
2023-05-15 6:18 ` Kent Overstreet
2023-05-15 7:13 ` Eric Biggers
2023-05-15 7:26 ` Kent Overstreet
2023-05-21 21:33 ` Eric Biggers
2023-05-21 22:04 ` Kent Overstreet
2023-05-15 10:29 ` David Laight
2023-05-10 11:56 ` David Laight
2023-05-09 21:43 ` Darrick J. Wong
2023-05-09 21:54 ` Kent Overstreet
2023-05-11 5:33 ` Theodore Ts'o
2023-05-11 5:44 ` Kent Overstreet
2023-05-13 13:25 ` Lorenzo Stoakes
2023-05-14 18:39 ` Christophe Leroy
2023-05-14 23:43 ` Kent Overstreet
2023-05-15 4:45 ` Christophe Leroy
2023-05-15 5:02 ` Kent Overstreet
2023-05-10 14:18 ` Christophe Leroy
2023-05-10 15:05 ` Johannes Thumshirn
2023-05-11 22:28 ` Kees Cook
2023-05-12 18:41 ` Kent Overstreet
2023-05-16 21:02 ` Kees Cook
2023-05-16 21:20 ` Kent Overstreet
2023-05-16 21:47 ` Matthew Wilcox
2023-05-16 21:57 ` Kent Overstreet
2023-05-17 5:28 ` Kent Overstreet
2023-05-17 14:04 ` Mike Rapoport
2023-05-17 14:18 ` Kent Overstreet
2023-05-17 15:44 ` Mike Rapoport
2023-05-17 15:59 ` Kent Overstreet
2023-06-17 4:13 ` Andy Lutomirski
2023-06-17 15:34 ` Kent Overstreet
2023-06-17 19:19 ` Andy Lutomirski
2023-06-17 20:08 ` Kent Overstreet
2023-06-17 20:35 ` Andy Lutomirski
2023-06-19 19:45 ` Kees Cook
2023-06-20 0:39 ` Kent Overstreet
2023-06-19 9:19 ` Mark Rutland
2023-06-19 10:47 ` Kent Overstreet
2023-06-19 12:47 ` Mark Rutland
2023-06-19 19:17 ` Kent Overstreet
2023-06-20 17:42 ` Andy Lutomirski
2023-06-20 18:08 ` Kent Overstreet
2023-06-20 18:15 ` Andy Lutomirski
2023-06-20 18:48 ` Dave Hansen
2023-06-20 20:18 ` Kent Overstreet
2023-06-20 20:42 ` Andy Lutomirski
2023-06-20 22:32 ` Andy Lutomirski
2023-06-20 22:43 ` Nadav Amit
2023-06-21 1:27 ` Andy Lutomirski
2023-05-09 16:56 ` [PATCH 08/32] fs: factor out d_mark_tmpfile() Kent Overstreet
2023-05-09 16:56 ` [PATCH 09/32] block: Add some exports for bcachefs Kent Overstreet
2023-05-09 16:56 ` [PATCH 10/32] block: Allow bio_iov_iter_get_pages() with bio->bi_bdev unset Kent Overstreet
2023-05-09 16:56 ` [PATCH 11/32] block: Bring back zero_fill_bio_iter Kent Overstreet
2023-05-09 16:56 ` [PATCH 12/32] block: Rework bio_for_each_segment_all() Kent Overstreet
2023-05-09 16:56 ` [PATCH 13/32] block: Rework bio_for_each_folio_all() Kent Overstreet
2023-05-09 16:56 ` [PATCH 14/32] block: Don't block on s_umount from __invalidate_super() Kent Overstreet
2023-05-09 16:56 ` [PATCH 15/32] bcache: move closures to lib/ Kent Overstreet
2023-05-10 1:10 ` Randy Dunlap
2023-05-09 16:56 ` [PATCH 16/32] MAINTAINERS: Add entry for closures Kent Overstreet
2023-05-09 17:05 ` Coly Li
2023-05-09 21:03 ` Randy Dunlap
2023-05-09 16:56 ` [PATCH 17/32] closures: closure_wait_event() Kent Overstreet
2023-05-09 16:56 ` [PATCH 18/32] closures: closure_nr_remaining() Kent Overstreet
2023-05-09 16:56 ` [PATCH 19/32] closures: Add a missing include Kent Overstreet
2023-05-09 16:56 ` [PATCH 20/32] vfs: factor out inode hash head calculation Kent Overstreet
2023-05-23 9:27 ` (subset) " Christian Brauner
2023-05-23 22:53 ` Dave Chinner
2023-05-24 6:44 ` Christoph Hellwig
2023-05-24 7:35 ` Dave Chinner
2023-05-24 8:31 ` Christian Brauner
2023-05-24 8:41 ` Kent Overstreet
2023-05-09 16:56 ` [PATCH 21/32] hlist-bl: add hlist_bl_fake() Kent Overstreet
2023-05-10 4:48 ` Dave Chinner
2023-05-23 9:27 ` (subset) " Christian Brauner
2023-05-09 16:56 ` [PATCH 22/32] vfs: inode cache conversion to hash-bl Kent Overstreet
2023-05-10 4:45 ` Dave Chinner
2023-05-16 15:45 ` Christian Brauner
2023-05-16 16:17 ` Kent Overstreet
2023-05-16 23:15 ` Dave Chinner
2023-05-22 13:04 ` Christian Brauner
2023-05-23 9:28 ` (subset) " Christian Brauner
2023-10-19 15:30 ` Mateusz Guzik
2023-10-19 15:59 ` Mateusz Guzik
2023-10-20 11:38 ` Dave Chinner
2023-10-20 17:49 ` Mateusz Guzik
2023-10-21 12:13 ` Mateusz Guzik
2023-10-23 5:10 ` Dave Chinner
2023-10-27 17:13 ` Mateusz Guzik
2023-10-27 18:36 ` Darrick J. Wong
2023-10-31 11:02 ` Christian Brauner
2023-10-31 11:31 ` Mateusz Guzik
2023-11-02 2:36 ` Kent Overstreet
2023-11-04 20:51 ` Dave Chinner
2023-05-09 16:56 ` [PATCH 23/32] iov_iter: copy_folio_from_iter_atomic() Kent Overstreet
2023-05-10 2:20 ` kernel test robot
2023-05-11 2:08 ` kernel test robot
2023-05-09 16:56 ` [PATCH 24/32] MAINTAINERS: Add entry for generic-radix-tree Kent Overstreet
2023-05-09 21:03 ` Randy Dunlap
2023-05-09 16:56 ` [PATCH 25/32] lib/generic-radix-tree.c: Don't overflow in peek() Kent Overstreet
2023-05-09 16:56 ` [PATCH 26/32] lib/generic-radix-tree.c: Add a missing include Kent Overstreet
2023-05-09 16:56 ` [PATCH 27/32] lib/generic-radix-tree.c: Add peek_prev() Kent Overstreet
2023-05-09 16:56 ` [PATCH 28/32] stacktrace: Export stack_trace_save_tsk Kent Overstreet
2023-06-19 9:10 ` Mark Rutland
2023-06-19 11:16 ` Kent Overstreet
2023-05-09 16:56 ` [PATCH 29/32] lib/string_helpers: string_get_size() now returns characters wrote Kent Overstreet
2023-07-12 19:58 ` Kees Cook
2023-07-12 20:19 ` Kent Overstreet
2023-07-12 22:38 ` Kees Cook
2023-07-12 23:53 ` Kent Overstreet
2023-07-12 20:23 ` Kent Overstreet
2023-05-09 16:56 ` [PATCH 30/32] lib: Export errname Kent Overstreet
2023-05-09 16:56 ` [PATCH 31/32] lib: add mean and variance module Kent Overstreet
2023-05-09 16:56 ` [PATCH 32/32] MAINTAINERS: Add entry for bcachefs Kent Overstreet
2023-05-09 21:04 ` Randy Dunlap
2023-05-09 21:07 ` Kent Overstreet
2023-06-15 20:41 ` [PATCH 00/32] bcachefs - a new COW filesystem Pavel Machek
2023-06-15 21:26 ` Kent Overstreet
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=ZGB1eevk/u2ssIBT@moria.home.lan \
--to=kent.overstreet@linux.dev \
--cc=akpm@linux-foundation.org \
--cc=ebiggers@kernel.org \
--cc=hch@infradead.org \
--cc=kent.overstreet@gmail.com \
--cc=linux-bcachefs@vger.kernel.org \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=lstoakes@gmail.com \
--cc=urezki@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).