* [PATCH 00/13] use rbtrees for preliminary backrefs
@ 2017-06-20 16:06 Edmund Nadolski
2017-06-20 16:06 ` [PATCH 01/13] btrfs: struct-funcs, constify readers Edmund Nadolski
` (13 more replies)
0 siblings, 14 replies; 23+ messages in thread
From: Edmund Nadolski @ 2017-06-20 16:06 UTC (permalink / raw)
To: enadolski, linux-btrfs
This patch series attempts to improve the performance of backref
searches by changing the prelim_refs implementation to use
rbtrees instead of lists. This also aims to reduce the soft
lockup occurences that can result when a backref search consumes
too much cpu time.
Test runs of btrfs/130 show an improvement in the overall
run time of the test (shown below in seconds) as a function of
the number of extents:
nr_extents: 256 512 640 1024 2048
------------+-------+-----+-------+-------+------
unpatched: 20 186 375 2204 40419
patched: 12 93 203 1060 22007
(Note, the current default value for nr_extents in btrfs/130 is
4096, which takes a very long time to complete.)
Edmund Nadolski (6):
btrfs: btrfs_check_shared should manage its own transaction
btrfs: remove ref_tree implementation from backref.c
btrfs: convert prelimary reference tracking to use rbtrees
btrfs: add cond_resched() calls when resolving backrefs
btrfs: allow backref search checks for shared extents
btrfs: clean up extraneous computations in add_delayed_refs
Jeff Mahoney (7):
btrfs: struct-funcs, constify readers
btrfs: constify tracepoint arguments
btrfs: backref, constify some arguments
btrfs: backref, add unode_aux_to_inode_list helper
btrfs: backref, cleanup __ namespace abuse
btrfs: add a node counter to each of the rbtrees
btrfs: backref, add tracepoints for prelim_ref insertion and merging
fs/btrfs/async-thread.c | 6 +-
fs/btrfs/async-thread.h | 6 +-
fs/btrfs/backref.c | 1042 ++++++++++++++++++------------------------
fs/btrfs/backref.h | 16 +-
fs/btrfs/btrfs_inode.h | 4 +-
fs/btrfs/ctree.h | 128 +++---
fs/btrfs/extent_io.c | 46 +-
fs/btrfs/extent_io.h | 19 +-
fs/btrfs/struct-funcs.c | 9 +-
fs/btrfs/super.c | 1 +
include/trace/events/btrfs.h | 300 +++++++-----
11 files changed, 750 insertions(+), 827 deletions(-)
--
2.10.2
^ permalink raw reply [flat|nested] 23+ messages in thread
* [PATCH 01/13] btrfs: struct-funcs, constify readers
2017-06-20 16:06 [PATCH 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
@ 2017-06-20 16:06 ` Edmund Nadolski
2017-06-20 16:06 ` [PATCH 02/13] btrfs: constify tracepoint arguments Edmund Nadolski
` (12 subsequent siblings)
13 siblings, 0 replies; 23+ messages in thread
From: Edmund Nadolski @ 2017-06-20 16:06 UTC (permalink / raw)
To: enadolski, linux-btrfs
From: Jeff Mahoney <jeffm@suse.com>
We have reader helpers for most of the on-disk structures that use
an extent_buffer and pointer as offset into the buffer that are
read-only. We should mark them as const and, in turn, allow consumers
of these interfaces to mark the buffers const as well.
No impact on code, but serves as documentation that a buffer is intended
not to be modified.
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
fs/btrfs/ctree.h | 128 +++++++++++++++++++++++++-----------------------
fs/btrfs/extent_io.c | 24 +++++----
fs/btrfs/extent_io.h | 19 ++++---
fs/btrfs/struct-funcs.c | 9 ++--
4 files changed, 91 insertions(+), 89 deletions(-)
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 06bf56e..95764c1 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -1446,7 +1446,7 @@ do { \
#define BTRFS_INODE_ROOT_ITEM_INIT (1 << 31)
struct btrfs_map_token {
- struct extent_buffer *eb;
+ const struct extent_buffer *eb;
char *kaddr;
unsigned long offset;
};
@@ -1480,18 +1480,19 @@ static inline void btrfs_init_map_token (struct btrfs_map_token *token)
sizeof(((type *)0)->member)))
#define DECLARE_BTRFS_SETGET_BITS(bits) \
-u##bits btrfs_get_token_##bits(struct extent_buffer *eb, void *ptr, \
- unsigned long off, \
- struct btrfs_map_token *token); \
-void btrfs_set_token_##bits(struct extent_buffer *eb, void *ptr, \
+u##bits btrfs_get_token_##bits(const struct extent_buffer *eb, \
+ const void *ptr, unsigned long off, \
+ struct btrfs_map_token *token); \
+void btrfs_set_token_##bits(struct extent_buffer *eb, const void *ptr, \
unsigned long off, u##bits val, \
struct btrfs_map_token *token); \
-static inline u##bits btrfs_get_##bits(struct extent_buffer *eb, void *ptr, \
+static inline u##bits btrfs_get_##bits(const struct extent_buffer *eb, \
+ const void *ptr, \
unsigned long off) \
{ \
return btrfs_get_token_##bits(eb, ptr, off, NULL); \
} \
-static inline void btrfs_set_##bits(struct extent_buffer *eb, void *ptr, \
+static inline void btrfs_set_##bits(struct extent_buffer *eb, void *ptr,\
unsigned long off, u##bits val) \
{ \
btrfs_set_token_##bits(eb, ptr, off, val, NULL); \
@@ -1503,7 +1504,8 @@ DECLARE_BTRFS_SETGET_BITS(32)
DECLARE_BTRFS_SETGET_BITS(64)
#define BTRFS_SETGET_FUNCS(name, type, member, bits) \
-static inline u##bits btrfs_##name(struct extent_buffer *eb, type *s) \
+static inline u##bits btrfs_##name(const struct extent_buffer *eb, \
+ const type *s) \
{ \
BUILD_BUG_ON(sizeof(u##bits) != sizeof(((type *)0))->member); \
return btrfs_get_##bits(eb, s, offsetof(type, member)); \
@@ -1514,7 +1516,8 @@ static inline void btrfs_set_##name(struct extent_buffer *eb, type *s, \
BUILD_BUG_ON(sizeof(u##bits) != sizeof(((type *)0))->member); \
btrfs_set_##bits(eb, s, offsetof(type, member), val); \
} \
-static inline u##bits btrfs_token_##name(struct extent_buffer *eb, type *s, \
+static inline u##bits btrfs_token_##name(const struct extent_buffer *eb,\
+ const type *s, \
struct btrfs_map_token *token) \
{ \
BUILD_BUG_ON(sizeof(u##bits) != sizeof(((type *)0))->member); \
@@ -1529,9 +1532,9 @@ static inline void btrfs_set_token_##name(struct extent_buffer *eb, \
}
#define BTRFS_SETGET_HEADER_FUNCS(name, type, member, bits) \
-static inline u##bits btrfs_##name(struct extent_buffer *eb) \
+static inline u##bits btrfs_##name(const struct extent_buffer *eb) \
{ \
- type *p = page_address(eb->pages[0]); \
+ const type *p = page_address(eb->pages[0]); \
u##bits res = le##bits##_to_cpu(p->member); \
return res; \
} \
@@ -1543,7 +1546,7 @@ static inline void btrfs_set_##name(struct extent_buffer *eb, \
}
#define BTRFS_SETGET_STACK_FUNCS(name, type, member, bits) \
-static inline u##bits btrfs_##name(type *s) \
+static inline u##bits btrfs_##name(const type *s) \
{ \
return le##bits##_to_cpu(s->member); \
} \
@@ -1849,7 +1852,7 @@ static inline unsigned long btrfs_node_key_ptr_offset(int nr)
sizeof(struct btrfs_key_ptr) * nr;
}
-void btrfs_node_key(struct extent_buffer *eb,
+void btrfs_node_key(const struct extent_buffer *eb,
struct btrfs_disk_key *disk_key, int nr);
static inline void btrfs_set_node_key(struct extent_buffer *eb,
@@ -1878,28 +1881,28 @@ static inline struct btrfs_item *btrfs_item_nr(int nr)
return (struct btrfs_item *)btrfs_item_nr_offset(nr);
}
-static inline u32 btrfs_item_end(struct extent_buffer *eb,
+static inline u32 btrfs_item_end(const struct extent_buffer *eb,
struct btrfs_item *item)
{
return btrfs_item_offset(eb, item) + btrfs_item_size(eb, item);
}
-static inline u32 btrfs_item_end_nr(struct extent_buffer *eb, int nr)
+static inline u32 btrfs_item_end_nr(const struct extent_buffer *eb, int nr)
{
return btrfs_item_end(eb, btrfs_item_nr(nr));
}
-static inline u32 btrfs_item_offset_nr(struct extent_buffer *eb, int nr)
+static inline u32 btrfs_item_offset_nr(const struct extent_buffer *eb, int nr)
{
return btrfs_item_offset(eb, btrfs_item_nr(nr));
}
-static inline u32 btrfs_item_size_nr(struct extent_buffer *eb, int nr)
+static inline u32 btrfs_item_size_nr(const struct extent_buffer *eb, int nr)
{
return btrfs_item_size(eb, btrfs_item_nr(nr));
}
-static inline void btrfs_item_key(struct extent_buffer *eb,
+static inline void btrfs_item_key(const struct extent_buffer *eb,
struct btrfs_disk_key *disk_key, int nr)
{
struct btrfs_item *item = btrfs_item_nr(nr);
@@ -1935,8 +1938,8 @@ BTRFS_SETGET_STACK_FUNCS(stack_dir_name_len, struct btrfs_dir_item,
BTRFS_SETGET_STACK_FUNCS(stack_dir_transid, struct btrfs_dir_item,
transid, 64);
-static inline void btrfs_dir_item_key(struct extent_buffer *eb,
- struct btrfs_dir_item *item,
+static inline void btrfs_dir_item_key(const struct extent_buffer *eb,
+ const struct btrfs_dir_item *item,
struct btrfs_disk_key *key)
{
read_eb_member(eb, item, struct btrfs_dir_item, location, key);
@@ -1944,7 +1947,7 @@ static inline void btrfs_dir_item_key(struct extent_buffer *eb,
static inline void btrfs_set_dir_item_key(struct extent_buffer *eb,
struct btrfs_dir_item *item,
- struct btrfs_disk_key *key)
+ const struct btrfs_disk_key *key)
{
write_eb_member(eb, item, struct btrfs_dir_item, location, key);
}
@@ -1956,8 +1959,8 @@ BTRFS_SETGET_FUNCS(free_space_bitmaps, struct btrfs_free_space_header,
BTRFS_SETGET_FUNCS(free_space_generation, struct btrfs_free_space_header,
generation, 64);
-static inline void btrfs_free_space_key(struct extent_buffer *eb,
- struct btrfs_free_space_header *h,
+static inline void btrfs_free_space_key(const struct extent_buffer *eb,
+ const struct btrfs_free_space_header *h,
struct btrfs_disk_key *key)
{
read_eb_member(eb, h, struct btrfs_free_space_header, location, key);
@@ -1965,7 +1968,7 @@ static inline void btrfs_free_space_key(struct extent_buffer *eb,
static inline void btrfs_set_free_space_key(struct extent_buffer *eb,
struct btrfs_free_space_header *h,
- struct btrfs_disk_key *key)
+ const struct btrfs_disk_key *key)
{
write_eb_member(eb, h, struct btrfs_free_space_header, location, key);
}
@@ -1992,25 +1995,25 @@ static inline void btrfs_cpu_key_to_disk(struct btrfs_disk_key *disk,
disk->objectid = cpu_to_le64(cpu->objectid);
}
-static inline void btrfs_node_key_to_cpu(struct extent_buffer *eb,
- struct btrfs_key *key, int nr)
+static inline void btrfs_node_key_to_cpu(const struct extent_buffer *eb,
+ struct btrfs_key *key, int nr)
{
struct btrfs_disk_key disk_key;
btrfs_node_key(eb, &disk_key, nr);
btrfs_disk_key_to_cpu(key, &disk_key);
}
-static inline void btrfs_item_key_to_cpu(struct extent_buffer *eb,
- struct btrfs_key *key, int nr)
+static inline void btrfs_item_key_to_cpu(const struct extent_buffer *eb,
+ struct btrfs_key *key, int nr)
{
struct btrfs_disk_key disk_key;
btrfs_item_key(eb, &disk_key, nr);
btrfs_disk_key_to_cpu(key, &disk_key);
}
-static inline void btrfs_dir_item_key_to_cpu(struct extent_buffer *eb,
- struct btrfs_dir_item *item,
- struct btrfs_key *key)
+static inline void btrfs_dir_item_key_to_cpu(const struct extent_buffer *eb,
+ const struct btrfs_dir_item *item,
+ struct btrfs_key *key)
{
struct btrfs_disk_key disk_key;
btrfs_dir_item_key(eb, item, &disk_key);
@@ -2042,7 +2045,7 @@ BTRFS_SETGET_STACK_FUNCS(stack_header_nritems, struct btrfs_header,
nritems, 32);
BTRFS_SETGET_STACK_FUNCS(stack_header_bytenr, struct btrfs_header, bytenr, 64);
-static inline int btrfs_header_flag(struct extent_buffer *eb, u64 flag)
+static inline int btrfs_header_flag(const struct extent_buffer *eb, u64 flag)
{
return (btrfs_header_flags(eb) & flag) == flag;
}
@@ -2061,7 +2064,7 @@ static inline int btrfs_clear_header_flag(struct extent_buffer *eb, u64 flag)
return (flags & flag) == flag;
}
-static inline int btrfs_header_backref_rev(struct extent_buffer *eb)
+static inline int btrfs_header_backref_rev(const struct extent_buffer *eb)
{
u64 flags = btrfs_header_flags(eb);
return flags >> BTRFS_BACKREF_REV_SHIFT;
@@ -2081,12 +2084,12 @@ static inline unsigned long btrfs_header_fsid(void)
return offsetof(struct btrfs_header, fsid);
}
-static inline unsigned long btrfs_header_chunk_tree_uuid(struct extent_buffer *eb)
+static inline unsigned long btrfs_header_chunk_tree_uuid(const struct extent_buffer *eb)
{
return offsetof(struct btrfs_header, chunk_tree_uuid);
}
-static inline int btrfs_is_leaf(struct extent_buffer *eb)
+static inline int btrfs_is_leaf(const struct extent_buffer *eb)
{
return btrfs_header_level(eb) == 0;
}
@@ -2120,12 +2123,12 @@ BTRFS_SETGET_STACK_FUNCS(root_stransid, struct btrfs_root_item,
BTRFS_SETGET_STACK_FUNCS(root_rtransid, struct btrfs_root_item,
rtransid, 64);
-static inline bool btrfs_root_readonly(struct btrfs_root *root)
+static inline bool btrfs_root_readonly(const struct btrfs_root *root)
{
return (root->root_item.flags & cpu_to_le64(BTRFS_ROOT_SUBVOL_RDONLY)) != 0;
}
-static inline bool btrfs_root_dead(struct btrfs_root *root)
+static inline bool btrfs_root_dead(const struct btrfs_root *root)
{
return (root->root_item.flags & cpu_to_le64(BTRFS_ROOT_SUBVOL_DEAD)) != 0;
}
@@ -2182,51 +2185,51 @@ BTRFS_SETGET_STACK_FUNCS(backup_num_devices, struct btrfs_root_backup,
/* struct btrfs_balance_item */
BTRFS_SETGET_FUNCS(balance_flags, struct btrfs_balance_item, flags, 64);
-static inline void btrfs_balance_data(struct extent_buffer *eb,
- struct btrfs_balance_item *bi,
+static inline void btrfs_balance_data(const struct extent_buffer *eb,
+ const struct btrfs_balance_item *bi,
struct btrfs_disk_balance_args *ba)
{
read_eb_member(eb, bi, struct btrfs_balance_item, data, ba);
}
static inline void btrfs_set_balance_data(struct extent_buffer *eb,
- struct btrfs_balance_item *bi,
- struct btrfs_disk_balance_args *ba)
+ struct btrfs_balance_item *bi,
+ const struct btrfs_disk_balance_args *ba)
{
write_eb_member(eb, bi, struct btrfs_balance_item, data, ba);
}
-static inline void btrfs_balance_meta(struct extent_buffer *eb,
- struct btrfs_balance_item *bi,
+static inline void btrfs_balance_meta(const struct extent_buffer *eb,
+ const struct btrfs_balance_item *bi,
struct btrfs_disk_balance_args *ba)
{
read_eb_member(eb, bi, struct btrfs_balance_item, meta, ba);
}
static inline void btrfs_set_balance_meta(struct extent_buffer *eb,
- struct btrfs_balance_item *bi,
- struct btrfs_disk_balance_args *ba)
+ struct btrfs_balance_item *bi,
+ const struct btrfs_disk_balance_args *ba)
{
write_eb_member(eb, bi, struct btrfs_balance_item, meta, ba);
}
-static inline void btrfs_balance_sys(struct extent_buffer *eb,
- struct btrfs_balance_item *bi,
+static inline void btrfs_balance_sys(const struct extent_buffer *eb,
+ const struct btrfs_balance_item *bi,
struct btrfs_disk_balance_args *ba)
{
read_eb_member(eb, bi, struct btrfs_balance_item, sys, ba);
}
static inline void btrfs_set_balance_sys(struct extent_buffer *eb,
- struct btrfs_balance_item *bi,
- struct btrfs_disk_balance_args *ba)
+ struct btrfs_balance_item *bi,
+ const struct btrfs_disk_balance_args *ba)
{
write_eb_member(eb, bi, struct btrfs_balance_item, sys, ba);
}
static inline void
btrfs_disk_balance_args_to_cpu(struct btrfs_balance_args *cpu,
- struct btrfs_disk_balance_args *disk)
+ const struct btrfs_disk_balance_args *disk)
{
memset(cpu, 0, sizeof(*cpu));
@@ -2246,7 +2249,7 @@ btrfs_disk_balance_args_to_cpu(struct btrfs_balance_args *cpu,
static inline void
btrfs_cpu_balance_args_to_disk(struct btrfs_disk_balance_args *disk,
- struct btrfs_balance_args *cpu)
+ const struct btrfs_balance_args *cpu)
{
memset(disk, 0, sizeof(*disk));
@@ -2314,7 +2317,7 @@ BTRFS_SETGET_STACK_FUNCS(super_magic, struct btrfs_super_block, magic, 64);
BTRFS_SETGET_STACK_FUNCS(super_uuid_tree_generation, struct btrfs_super_block,
uuid_tree_generation, 64);
-static inline int btrfs_super_csum_size(struct btrfs_super_block *s)
+static inline int btrfs_super_csum_size(const struct btrfs_super_block *s)
{
u16 t = btrfs_super_csum_type(s);
/*
@@ -2329,8 +2332,8 @@ static inline int btrfs_super_csum_size(struct btrfs_super_block *s)
* this returns the address of the start of the last item,
* which is the stop of the leaf data stack
*/
-static inline unsigned int leaf_data_end(struct btrfs_fs_info *fs_info,
- struct extent_buffer *leaf)
+static inline unsigned int leaf_data_end(const struct btrfs_fs_info *fs_info,
+ const struct extent_buffer *leaf)
{
u32 nr = btrfs_header_nritems(leaf);
@@ -2355,7 +2358,7 @@ BTRFS_SETGET_STACK_FUNCS(stack_file_extent_compression,
struct btrfs_file_extent_item, compression, 8);
static inline unsigned long
-btrfs_file_extent_inline_start(struct btrfs_file_extent_item *e)
+btrfs_file_extent_inline_start(const struct btrfs_file_extent_item *e)
{
return (unsigned long)e + BTRFS_FILE_EXTENT_INLINE_DATA_START;
}
@@ -2389,8 +2392,9 @@ BTRFS_SETGET_FUNCS(file_extent_other_encoding, struct btrfs_file_extent_item,
* size of any extent headers. If a file is compressed on disk, this is
* the compressed size
*/
-static inline u32 btrfs_file_extent_inline_item_len(struct extent_buffer *eb,
- struct btrfs_item *e)
+static inline u32 btrfs_file_extent_inline_item_len(
+ const struct extent_buffer *eb,
+ struct btrfs_item *e)
{
return btrfs_item_size(eb, e) - BTRFS_FILE_EXTENT_INLINE_DATA_START;
}
@@ -2398,9 +2402,9 @@ static inline u32 btrfs_file_extent_inline_item_len(struct extent_buffer *eb,
/* this returns the number of file bytes represented by the inline item.
* If an item is compressed, this is the uncompressed size
*/
-static inline u32 btrfs_file_extent_inline_len(struct extent_buffer *eb,
- int slot,
- struct btrfs_file_extent_item *fi)
+static inline u32 btrfs_file_extent_inline_len(const struct extent_buffer *eb,
+ int slot,
+ const struct btrfs_file_extent_item *fi)
{
struct btrfs_map_token token;
@@ -2422,8 +2426,8 @@ static inline u32 btrfs_file_extent_inline_len(struct extent_buffer *eb,
/* btrfs_dev_stats_item */
-static inline u64 btrfs_dev_stats_value(struct extent_buffer *eb,
- struct btrfs_dev_stats_item *ptr,
+static inline u64 btrfs_dev_stats_value(const struct extent_buffer *eb,
+ const struct btrfs_dev_stats_item *ptr,
int index)
{
u64 val;
diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index cb4754e..7ee62f6 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -5406,9 +5406,8 @@ int read_extent_buffer_pages(struct extent_io_tree *tree,
return ret;
}
-void read_extent_buffer(struct extent_buffer *eb, void *dstv,
- unsigned long start,
- unsigned long len)
+void read_extent_buffer(const struct extent_buffer *eb, void *dstv,
+ unsigned long start, unsigned long len)
{
size_t cur;
size_t offset;
@@ -5437,9 +5436,9 @@ void read_extent_buffer(struct extent_buffer *eb, void *dstv,
}
}
-int read_extent_buffer_to_user(struct extent_buffer *eb, void __user *dstv,
- unsigned long start,
- unsigned long len)
+int read_extent_buffer_to_user(const struct extent_buffer *eb,
+ void __user *dstv,
+ unsigned long start, unsigned long len)
{
size_t cur;
size_t offset;
@@ -5479,10 +5478,10 @@ int read_extent_buffer_to_user(struct extent_buffer *eb, void __user *dstv,
* return 1 if the item spans two pages.
* return -EINVAL otherwise.
*/
-int map_private_extent_buffer(struct extent_buffer *eb, unsigned long start,
- unsigned long min_len, char **map,
- unsigned long *map_start,
- unsigned long *map_len)
+int map_private_extent_buffer(const struct extent_buffer *eb,
+ unsigned long start, unsigned long min_len,
+ char **map, unsigned long *map_start,
+ unsigned long *map_len)
{
size_t offset = start & (PAGE_SIZE - 1);
char *kaddr;
@@ -5516,9 +5515,8 @@ int map_private_extent_buffer(struct extent_buffer *eb, unsigned long start,
return 0;
}
-int memcmp_extent_buffer(struct extent_buffer *eb, const void *ptrv,
- unsigned long start,
- unsigned long len)
+int memcmp_extent_buffer(const struct extent_buffer *eb, const void *ptrv,
+ unsigned long start, unsigned long len)
{
size_t cur;
size_t offset;
diff --git a/fs/btrfs/extent_io.h b/fs/btrfs/extent_io.h
index 0f36017..a5b6617 100644
--- a/fs/btrfs/extent_io.h
+++ b/fs/btrfs/extent_io.h
@@ -449,14 +449,13 @@ static inline void extent_buffer_get(struct extent_buffer *eb)
atomic_inc(&eb->refs);
}
-int memcmp_extent_buffer(struct extent_buffer *eb, const void *ptrv,
- unsigned long start,
- unsigned long len);
-void read_extent_buffer(struct extent_buffer *eb, void *dst,
+int memcmp_extent_buffer(const struct extent_buffer *eb, const void *ptrv,
+ unsigned long start, unsigned long len);
+void read_extent_buffer(const struct extent_buffer *eb, void *dst,
unsigned long start,
unsigned long len);
-int read_extent_buffer_to_user(struct extent_buffer *eb, void __user *dst,
- unsigned long start,
+int read_extent_buffer_to_user(const struct extent_buffer *eb,
+ void __user *dst, unsigned long start,
unsigned long len);
void write_extent_buffer_fsid(struct extent_buffer *eb, const void *src);
void write_extent_buffer_chunk_tree_uuid(struct extent_buffer *eb,
@@ -486,10 +485,10 @@ void set_extent_buffer_uptodate(struct extent_buffer *eb);
void clear_extent_buffer_uptodate(struct extent_buffer *eb);
int extent_buffer_uptodate(struct extent_buffer *eb);
int extent_buffer_under_io(struct extent_buffer *eb);
-int map_private_extent_buffer(struct extent_buffer *eb, unsigned long offset,
- unsigned long min_len, char **map,
- unsigned long *map_start,
- unsigned long *map_len);
+int map_private_extent_buffer(const struct extent_buffer *eb,
+ unsigned long offset, unsigned long min_len,
+ char **map, unsigned long *map_start,
+ unsigned long *map_len);
void extent_range_clear_dirty_for_io(struct inode *inode, u64 start, u64 end);
void extent_range_redirty_for_io(struct inode *inode, u64 start, u64 end);
void extent_clear_unlock_delalloc(struct inode *inode, u64 start, u64 end,
diff --git a/fs/btrfs/struct-funcs.c b/fs/btrfs/struct-funcs.c
index 875c757..5e2b92d 100644
--- a/fs/btrfs/struct-funcs.c
+++ b/fs/btrfs/struct-funcs.c
@@ -50,8 +50,8 @@ static inline void put_unaligned_le8(u8 val, void *p)
*/
#define DEFINE_BTRFS_SETGET_BITS(bits) \
-u##bits btrfs_get_token_##bits(struct extent_buffer *eb, void *ptr, \
- unsigned long off, \
+u##bits btrfs_get_token_##bits(const struct extent_buffer *eb, \
+ const void *ptr, unsigned long off, \
struct btrfs_map_token *token) \
{ \
unsigned long part_offset = (unsigned long)ptr; \
@@ -90,7 +90,8 @@ u##bits btrfs_get_token_##bits(struct extent_buffer *eb, void *ptr, \
return res; \
} \
void btrfs_set_token_##bits(struct extent_buffer *eb, \
- void *ptr, unsigned long off, u##bits val, \
+ const void *ptr, unsigned long off, \
+ u##bits val, \
struct btrfs_map_token *token) \
{ \
unsigned long part_offset = (unsigned long)ptr; \
@@ -133,7 +134,7 @@ DEFINE_BTRFS_SETGET_BITS(16)
DEFINE_BTRFS_SETGET_BITS(32)
DEFINE_BTRFS_SETGET_BITS(64)
-void btrfs_node_key(struct extent_buffer *eb,
+void btrfs_node_key(const struct extent_buffer *eb,
struct btrfs_disk_key *disk_key, int nr)
{
unsigned long ptr = btrfs_node_key_ptr_offset(nr);
--
2.10.2
^ permalink raw reply related [flat|nested] 23+ messages in thread
* [PATCH 02/13] btrfs: constify tracepoint arguments
2017-06-20 16:06 [PATCH 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
2017-06-20 16:06 ` [PATCH 01/13] btrfs: struct-funcs, constify readers Edmund Nadolski
@ 2017-06-20 16:06 ` Edmund Nadolski
2017-06-20 16:06 ` [PATCH 03/13] btrfs: backref, constify some arguments Edmund Nadolski
` (11 subsequent siblings)
13 siblings, 0 replies; 23+ messages in thread
From: Edmund Nadolski @ 2017-06-20 16:06 UTC (permalink / raw)
To: enadolski, linux-btrfs
From: Jeff Mahoney <jeffm@suse.com>
Tracepoint arguments are all read-only. If we mark the arguments
as const, we're able to keep or convert those arguments to const
where appropriate.
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
fs/btrfs/async-thread.c | 6 +-
fs/btrfs/async-thread.h | 6 +-
fs/btrfs/btrfs_inode.h | 4 +-
include/trace/events/btrfs.h | 242 +++++++++++++++++++++++--------------------
4 files changed, 136 insertions(+), 122 deletions(-)
diff --git a/fs/btrfs/async-thread.c b/fs/btrfs/async-thread.c
index ff0b0be..e00c8a9 100644
--- a/fs/btrfs/async-thread.c
+++ b/fs/btrfs/async-thread.c
@@ -75,18 +75,18 @@ void btrfs_##name(struct work_struct *arg) \
}
struct btrfs_fs_info *
-btrfs_workqueue_owner(struct __btrfs_workqueue *wq)
+btrfs_workqueue_owner(const struct __btrfs_workqueue *wq)
{
return wq->fs_info;
}
struct btrfs_fs_info *
-btrfs_work_owner(struct btrfs_work *work)
+btrfs_work_owner(const struct btrfs_work *work)
{
return work->wq->fs_info;
}
-bool btrfs_workqueue_normal_congested(struct btrfs_workqueue *wq)
+bool btrfs_workqueue_normal_congested(const struct btrfs_workqueue *wq)
{
/*
* We could compare wq->normal->pending with num_online_cpus()
diff --git a/fs/btrfs/async-thread.h b/fs/btrfs/async-thread.h
index 1f95973..fc957e0 100644
--- a/fs/btrfs/async-thread.h
+++ b/fs/btrfs/async-thread.h
@@ -82,7 +82,7 @@ void btrfs_queue_work(struct btrfs_workqueue *wq,
void btrfs_destroy_workqueue(struct btrfs_workqueue *wq);
void btrfs_workqueue_set_max(struct btrfs_workqueue *wq, int max);
void btrfs_set_work_high_priority(struct btrfs_work *work);
-struct btrfs_fs_info *btrfs_work_owner(struct btrfs_work *work);
-struct btrfs_fs_info *btrfs_workqueue_owner(struct __btrfs_workqueue *wq);
-bool btrfs_workqueue_normal_congested(struct btrfs_workqueue *wq);
+struct btrfs_fs_info *btrfs_work_owner(const struct btrfs_work *work);
+struct btrfs_fs_info *btrfs_workqueue_owner(const struct __btrfs_workqueue *wq);
+bool btrfs_workqueue_normal_congested(const struct btrfs_workqueue *wq);
#endif
diff --git a/fs/btrfs/btrfs_inode.h b/fs/btrfs/btrfs_inode.h
index b8622e4..a68fbf6 100644
--- a/fs/btrfs/btrfs_inode.h
+++ b/fs/btrfs/btrfs_inode.h
@@ -207,7 +207,7 @@ struct btrfs_inode {
extern unsigned char btrfs_filetype_table[];
-static inline struct btrfs_inode *BTRFS_I(struct inode *inode)
+static inline struct btrfs_inode *BTRFS_I(const struct inode *inode)
{
return container_of(inode, struct btrfs_inode, vfs_inode);
}
@@ -231,7 +231,7 @@ static inline void btrfs_insert_inode_hash(struct inode *inode)
__insert_inode_hash(inode, h);
}
-static inline u64 btrfs_ino(struct btrfs_inode *inode)
+static inline u64 btrfs_ino(const struct btrfs_inode *inode)
{
u64 ino = inode->location.objectid;
diff --git a/include/trace/events/btrfs.h b/include/trace/events/btrfs.h
index cd99a36..42560fe 100644
--- a/include/trace/events/btrfs.h
+++ b/include/trace/events/btrfs.h
@@ -92,7 +92,7 @@ struct btrfs_qgroup;
TRACE_EVENT(btrfs_transaction_commit,
- TP_PROTO(struct btrfs_root *root),
+ TP_PROTO(const struct btrfs_root *root),
TP_ARGS(root),
@@ -113,7 +113,7 @@ TRACE_EVENT(btrfs_transaction_commit,
DECLARE_EVENT_CLASS(btrfs__inode,
- TP_PROTO(struct inode *inode),
+ TP_PROTO(const struct inode *inode),
TP_ARGS(inode),
@@ -151,21 +151,21 @@ DECLARE_EVENT_CLASS(btrfs__inode,
DEFINE_EVENT(btrfs__inode, btrfs_inode_new,
- TP_PROTO(struct inode *inode),
+ TP_PROTO(const struct inode *inode),
TP_ARGS(inode)
);
DEFINE_EVENT(btrfs__inode, btrfs_inode_request,
- TP_PROTO(struct inode *inode),
+ TP_PROTO(const struct inode *inode),
TP_ARGS(inode)
);
DEFINE_EVENT(btrfs__inode, btrfs_inode_evict,
- TP_PROTO(struct inode *inode),
+ TP_PROTO(const struct inode *inode),
TP_ARGS(inode)
);
@@ -192,8 +192,8 @@ DEFINE_EVENT(btrfs__inode, btrfs_inode_evict,
TRACE_EVENT_CONDITION(btrfs_get_extent,
- TP_PROTO(struct btrfs_root *root, struct btrfs_inode *inode,
- struct extent_map *map),
+ TP_PROTO(const struct btrfs_root *root, const struct btrfs_inode *inode,
+ const struct extent_map *map),
TP_ARGS(root, inode, map),
@@ -388,7 +388,8 @@ DEFINE_EVENT(
DECLARE_EVENT_CLASS(btrfs__ordered_extent,
- TP_PROTO(struct inode *inode, struct btrfs_ordered_extent *ordered),
+ TP_PROTO(const struct inode *inode,
+ const struct btrfs_ordered_extent *ordered),
TP_ARGS(inode, ordered),
@@ -440,36 +441,40 @@ DECLARE_EVENT_CLASS(btrfs__ordered_extent,
DEFINE_EVENT(btrfs__ordered_extent, btrfs_ordered_extent_add,
- TP_PROTO(struct inode *inode, struct btrfs_ordered_extent *ordered),
+ TP_PROTO(const struct inode *inode,
+ const struct btrfs_ordered_extent *ordered),
TP_ARGS(inode, ordered)
);
DEFINE_EVENT(btrfs__ordered_extent, btrfs_ordered_extent_remove,
- TP_PROTO(struct inode *inode, struct btrfs_ordered_extent *ordered),
+ TP_PROTO(const struct inode *inode,
+ const struct btrfs_ordered_extent *ordered),
TP_ARGS(inode, ordered)
);
DEFINE_EVENT(btrfs__ordered_extent, btrfs_ordered_extent_start,
- TP_PROTO(struct inode *inode, struct btrfs_ordered_extent *ordered),
+ TP_PROTO(const struct inode *inode,
+ const struct btrfs_ordered_extent *ordered),
TP_ARGS(inode, ordered)
);
DEFINE_EVENT(btrfs__ordered_extent, btrfs_ordered_extent_put,
- TP_PROTO(struct inode *inode, struct btrfs_ordered_extent *ordered),
+ TP_PROTO(const struct inode *inode,
+ const struct btrfs_ordered_extent *ordered),
TP_ARGS(inode, ordered)
);
DECLARE_EVENT_CLASS(btrfs__writepage,
- TP_PROTO(struct page *page, struct inode *inode,
- struct writeback_control *wbc),
+ TP_PROTO(const struct page *page, const struct inode *inode,
+ const struct writeback_control *wbc),
TP_ARGS(page, inode, wbc),
@@ -517,15 +522,15 @@ DECLARE_EVENT_CLASS(btrfs__writepage,
DEFINE_EVENT(btrfs__writepage, __extent_writepage,
- TP_PROTO(struct page *page, struct inode *inode,
- struct writeback_control *wbc),
+ TP_PROTO(const struct page *page, const struct inode *inode,
+ const struct writeback_control *wbc),
TP_ARGS(page, inode, wbc)
);
TRACE_EVENT(btrfs_writepage_end_io_hook,
- TP_PROTO(struct page *page, u64 start, u64 end, int uptodate),
+ TP_PROTO(const struct page *page, u64 start, u64 end, int uptodate),
TP_ARGS(page, start, end, uptodate),
@@ -558,7 +563,7 @@ TRACE_EVENT(btrfs_writepage_end_io_hook,
TRACE_EVENT(btrfs_sync_file,
- TP_PROTO(struct file *file, int datasync),
+ TP_PROTO(const struct file *file, int datasync),
TP_ARGS(file, datasync),
@@ -570,8 +575,8 @@ TRACE_EVENT(btrfs_sync_file,
),
TP_fast_assign(
- struct dentry *dentry = file->f_path.dentry;
- struct inode *inode = d_inode(dentry);
+ const struct dentry *dentry = file->f_path.dentry;
+ const struct inode *inode = d_inode(dentry);
TP_fast_assign_fsid(btrfs_sb(file->f_path.dentry->d_sb));
__entry->ino = inode->i_ino;
@@ -589,7 +594,7 @@ TRACE_EVENT(btrfs_sync_file,
TRACE_EVENT(btrfs_sync_fs,
- TP_PROTO(struct btrfs_fs_info *fs_info, int wait),
+ TP_PROTO(const struct btrfs_fs_info *fs_info, int wait),
TP_ARGS(fs_info, wait),
@@ -606,8 +611,8 @@ TRACE_EVENT(btrfs_sync_fs,
TRACE_EVENT(btrfs_add_block_group,
- TP_PROTO(struct btrfs_fs_info *fs_info,
- struct btrfs_block_group_cache *block_group, int create),
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct btrfs_block_group_cache *block_group, int create),
TP_ARGS(fs_info, block_group, create),
@@ -654,9 +659,9 @@ TRACE_EVENT(btrfs_add_block_group,
DECLARE_EVENT_CLASS(btrfs_delayed_tree_ref,
- TP_PROTO(struct btrfs_fs_info *fs_info,
- struct btrfs_delayed_ref_node *ref,
- struct btrfs_delayed_tree_ref *full_ref,
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct btrfs_delayed_ref_node *ref,
+ const struct btrfs_delayed_tree_ref *full_ref,
int action),
TP_ARGS(fs_info, ref, full_ref, action),
@@ -697,9 +702,9 @@ DECLARE_EVENT_CLASS(btrfs_delayed_tree_ref,
DEFINE_EVENT(btrfs_delayed_tree_ref, add_delayed_tree_ref,
- TP_PROTO(struct btrfs_fs_info *fs_info,
- struct btrfs_delayed_ref_node *ref,
- struct btrfs_delayed_tree_ref *full_ref,
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct btrfs_delayed_ref_node *ref,
+ const struct btrfs_delayed_tree_ref *full_ref,
int action),
TP_ARGS(fs_info, ref, full_ref, action)
@@ -707,9 +712,9 @@ DEFINE_EVENT(btrfs_delayed_tree_ref, add_delayed_tree_ref,
DEFINE_EVENT(btrfs_delayed_tree_ref, run_delayed_tree_ref,
- TP_PROTO(struct btrfs_fs_info *fs_info,
- struct btrfs_delayed_ref_node *ref,
- struct btrfs_delayed_tree_ref *full_ref,
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct btrfs_delayed_ref_node *ref,
+ const struct btrfs_delayed_tree_ref *full_ref,
int action),
TP_ARGS(fs_info, ref, full_ref, action)
@@ -717,9 +722,9 @@ DEFINE_EVENT(btrfs_delayed_tree_ref, run_delayed_tree_ref,
DECLARE_EVENT_CLASS(btrfs_delayed_data_ref,
- TP_PROTO(struct btrfs_fs_info *fs_info,
- struct btrfs_delayed_ref_node *ref,
- struct btrfs_delayed_data_ref *full_ref,
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct btrfs_delayed_ref_node *ref,
+ const struct btrfs_delayed_data_ref *full_ref,
int action),
TP_ARGS(fs_info, ref, full_ref, action),
@@ -764,9 +769,9 @@ DECLARE_EVENT_CLASS(btrfs_delayed_data_ref,
DEFINE_EVENT(btrfs_delayed_data_ref, add_delayed_data_ref,
- TP_PROTO(struct btrfs_fs_info *fs_info,
- struct btrfs_delayed_ref_node *ref,
- struct btrfs_delayed_data_ref *full_ref,
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct btrfs_delayed_ref_node *ref,
+ const struct btrfs_delayed_data_ref *full_ref,
int action),
TP_ARGS(fs_info, ref, full_ref, action)
@@ -774,9 +779,9 @@ DEFINE_EVENT(btrfs_delayed_data_ref, add_delayed_data_ref,
DEFINE_EVENT(btrfs_delayed_data_ref, run_delayed_data_ref,
- TP_PROTO(struct btrfs_fs_info *fs_info,
- struct btrfs_delayed_ref_node *ref,
- struct btrfs_delayed_data_ref *full_ref,
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct btrfs_delayed_ref_node *ref,
+ const struct btrfs_delayed_data_ref *full_ref,
int action),
TP_ARGS(fs_info, ref, full_ref, action)
@@ -784,9 +789,9 @@ DEFINE_EVENT(btrfs_delayed_data_ref, run_delayed_data_ref,
DECLARE_EVENT_CLASS(btrfs_delayed_ref_head,
- TP_PROTO(struct btrfs_fs_info *fs_info,
- struct btrfs_delayed_ref_node *ref,
- struct btrfs_delayed_ref_head *head_ref,
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct btrfs_delayed_ref_node *ref,
+ const struct btrfs_delayed_ref_head *head_ref,
int action),
TP_ARGS(fs_info, ref, head_ref, action),
@@ -814,9 +819,9 @@ DECLARE_EVENT_CLASS(btrfs_delayed_ref_head,
DEFINE_EVENT(btrfs_delayed_ref_head, add_delayed_ref_head,
- TP_PROTO(struct btrfs_fs_info *fs_info,
- struct btrfs_delayed_ref_node *ref,
- struct btrfs_delayed_ref_head *head_ref,
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct btrfs_delayed_ref_node *ref,
+ const struct btrfs_delayed_ref_head *head_ref,
int action),
TP_ARGS(fs_info, ref, head_ref, action)
@@ -824,9 +829,9 @@ DEFINE_EVENT(btrfs_delayed_ref_head, add_delayed_ref_head,
DEFINE_EVENT(btrfs_delayed_ref_head, run_delayed_ref_head,
- TP_PROTO(struct btrfs_fs_info *fs_info,
- struct btrfs_delayed_ref_node *ref,
- struct btrfs_delayed_ref_head *head_ref,
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct btrfs_delayed_ref_node *ref,
+ const struct btrfs_delayed_ref_head *head_ref,
int action),
TP_ARGS(fs_info, ref, head_ref, action)
@@ -846,8 +851,8 @@ DEFINE_EVENT(btrfs_delayed_ref_head, run_delayed_ref_head,
DECLARE_EVENT_CLASS(btrfs__chunk,
- TP_PROTO(struct btrfs_fs_info *fs_info, struct map_lookup *map,
- u64 offset, u64 size),
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct map_lookup *map, u64 offset, u64 size),
TP_ARGS(fs_info, map, offset, size),
@@ -880,24 +885,24 @@ DECLARE_EVENT_CLASS(btrfs__chunk,
DEFINE_EVENT(btrfs__chunk, btrfs_chunk_alloc,
- TP_PROTO(struct btrfs_fs_info *fs_info, struct map_lookup *map,
- u64 offset, u64 size),
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct map_lookup *map, u64 offset, u64 size),
TP_ARGS(fs_info, map, offset, size)
);
DEFINE_EVENT(btrfs__chunk, btrfs_chunk_free,
- TP_PROTO(struct btrfs_fs_info *fs_info, struct map_lookup *map,
- u64 offset, u64 size),
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct map_lookup *map, u64 offset, u64 size),
TP_ARGS(fs_info, map, offset, size)
);
TRACE_EVENT(btrfs_cow_block,
- TP_PROTO(struct btrfs_root *root, struct extent_buffer *buf,
- struct extent_buffer *cow),
+ TP_PROTO(const struct btrfs_root *root, const struct extent_buffer *buf,
+ const struct extent_buffer *cow),
TP_ARGS(root, buf, cow),
@@ -931,7 +936,7 @@ TRACE_EVENT(btrfs_cow_block,
TRACE_EVENT(btrfs_space_reservation,
- TP_PROTO(struct btrfs_fs_info *fs_info, char *type, u64 val,
+ TP_PROTO(const struct btrfs_fs_info *fs_info, char *type, u64 val,
u64 bytes, int reserve),
TP_ARGS(fs_info, type, val, bytes, reserve),
@@ -963,7 +968,7 @@ TRACE_EVENT(btrfs_space_reservation,
TRACE_EVENT(btrfs_trigger_flush,
- TP_PROTO(struct btrfs_fs_info *fs_info, u64 flags, u64 bytes,
+ TP_PROTO(const struct btrfs_fs_info *fs_info, u64 flags, u64 bytes,
int flush, char *reason),
TP_ARGS(fs_info, flags, bytes, flush, reason),
@@ -1004,7 +1009,7 @@ TRACE_EVENT(btrfs_trigger_flush,
TRACE_EVENT(btrfs_flush_space,
- TP_PROTO(struct btrfs_fs_info *fs_info, u64 flags, u64 num_bytes,
+ TP_PROTO(const struct btrfs_fs_info *fs_info, u64 flags, u64 num_bytes,
u64 orig_bytes, int state, int ret),
TP_ARGS(fs_info, flags, num_bytes, orig_bytes, state, ret),
@@ -1039,7 +1044,7 @@ TRACE_EVENT(btrfs_flush_space,
DECLARE_EVENT_CLASS(btrfs__reserved_extent,
- TP_PROTO(struct btrfs_fs_info *fs_info, u64 start, u64 len),
+ TP_PROTO(const struct btrfs_fs_info *fs_info, u64 start, u64 len),
TP_ARGS(fs_info, start, len),
@@ -1061,22 +1066,22 @@ DECLARE_EVENT_CLASS(btrfs__reserved_extent,
DEFINE_EVENT(btrfs__reserved_extent, btrfs_reserved_extent_alloc,
- TP_PROTO(struct btrfs_fs_info *fs_info, u64 start, u64 len),
+ TP_PROTO(const struct btrfs_fs_info *fs_info, u64 start, u64 len),
TP_ARGS(fs_info, start, len)
);
DEFINE_EVENT(btrfs__reserved_extent, btrfs_reserved_extent_free,
- TP_PROTO(struct btrfs_fs_info *fs_info, u64 start, u64 len),
+ TP_PROTO(const struct btrfs_fs_info *fs_info, u64 start, u64 len),
TP_ARGS(fs_info, start, len)
);
TRACE_EVENT(find_free_extent,
- TP_PROTO(struct btrfs_fs_info *fs_info, u64 num_bytes, u64 empty_size,
- u64 data),
+ TP_PROTO(const struct btrfs_fs_info *fs_info, u64 num_bytes,
+ u64 empty_size, u64 data),
TP_ARGS(fs_info, num_bytes, empty_size, data),
@@ -1101,8 +1106,8 @@ TRACE_EVENT(find_free_extent,
DECLARE_EVENT_CLASS(btrfs__reserve_extent,
- TP_PROTO(struct btrfs_fs_info *fs_info,
- struct btrfs_block_group_cache *block_group, u64 start,
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct btrfs_block_group_cache *block_group, u64 start,
u64 len),
TP_ARGS(fs_info, block_group, start, len),
@@ -1132,8 +1137,8 @@ DECLARE_EVENT_CLASS(btrfs__reserve_extent,
DEFINE_EVENT(btrfs__reserve_extent, btrfs_reserve_extent,
- TP_PROTO(struct btrfs_fs_info *fs_info,
- struct btrfs_block_group_cache *block_group, u64 start,
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct btrfs_block_group_cache *block_group, u64 start,
u64 len),
TP_ARGS(fs_info, block_group, start, len)
@@ -1141,8 +1146,8 @@ DEFINE_EVENT(btrfs__reserve_extent, btrfs_reserve_extent,
DEFINE_EVENT(btrfs__reserve_extent, btrfs_reserve_extent_cluster,
- TP_PROTO(struct btrfs_fs_info *fs_info,
- struct btrfs_block_group_cache *block_group, u64 start,
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct btrfs_block_group_cache *block_group, u64 start,
u64 len),
TP_ARGS(fs_info, block_group, start, len)
@@ -1150,7 +1155,7 @@ DEFINE_EVENT(btrfs__reserve_extent, btrfs_reserve_extent_cluster,
TRACE_EVENT(btrfs_find_cluster,
- TP_PROTO(struct btrfs_block_group_cache *block_group, u64 start,
+ TP_PROTO(const struct btrfs_block_group_cache *block_group, u64 start,
u64 bytes, u64 empty_size, u64 min_bytes),
TP_ARGS(block_group, start, bytes, empty_size, min_bytes),
@@ -1183,7 +1188,7 @@ TRACE_EVENT(btrfs_find_cluster,
TRACE_EVENT(btrfs_failed_cluster_setup,
- TP_PROTO(struct btrfs_block_group_cache *block_group),
+ TP_PROTO(const struct btrfs_block_group_cache *block_group),
TP_ARGS(block_group),
@@ -1200,8 +1205,9 @@ TRACE_EVENT(btrfs_failed_cluster_setup,
TRACE_EVENT(btrfs_setup_cluster,
- TP_PROTO(struct btrfs_block_group_cache *block_group,
- struct btrfs_free_cluster *cluster, u64 size, int bitmap),
+ TP_PROTO(const struct btrfs_block_group_cache *block_group,
+ const struct btrfs_free_cluster *cluster,
+ u64 size, int bitmap),
TP_ARGS(block_group, cluster, size, bitmap),
@@ -1235,12 +1241,13 @@ TRACE_EVENT(btrfs_setup_cluster,
struct extent_state;
TRACE_EVENT(alloc_extent_state,
- TP_PROTO(struct extent_state *state, gfp_t mask, unsigned long IP),
+ TP_PROTO(const struct extent_state *state,
+ gfp_t mask, unsigned long IP),
TP_ARGS(state, mask, IP),
TP_STRUCT__entry(
- __field(struct extent_state *, state)
+ __field(const struct extent_state *, state)
__field(gfp_t, mask)
__field(unsigned long, ip)
),
@@ -1252,17 +1259,17 @@ TRACE_EVENT(alloc_extent_state,
),
TP_printk("state=%p mask=%s caller=%pS", __entry->state,
- show_gfp_flags(__entry->mask), (void *)__entry->ip)
+ show_gfp_flags(__entry->mask), (const void *)__entry->ip)
);
TRACE_EVENT(free_extent_state,
- TP_PROTO(struct extent_state *state, unsigned long IP),
+ TP_PROTO(const struct extent_state *state, unsigned long IP),
TP_ARGS(state, IP),
TP_STRUCT__entry(
- __field(struct extent_state *, state)
+ __field(const struct extent_state *, state)
__field(unsigned long, ip)
),
@@ -1272,22 +1279,22 @@ TRACE_EVENT(free_extent_state,
),
TP_printk("state=%p caller=%pS", __entry->state,
- (void *)__entry->ip)
+ (const void *)__entry->ip)
);
DECLARE_EVENT_CLASS(btrfs__work,
- TP_PROTO(struct btrfs_work *work),
+ TP_PROTO(const struct btrfs_work *work),
TP_ARGS(work),
TP_STRUCT__entry_btrfs(
- __field( void *, work )
- __field( void *, wq )
- __field( void *, func )
- __field( void *, ordered_func )
- __field( void *, ordered_free )
- __field( void *, normal_work )
+ __field( const void *, work )
+ __field( const void *, wq )
+ __field( const void *, func )
+ __field( const void *, ordered_func )
+ __field( const void *, ordered_free )
+ __field( const void *, normal_work )
),
TP_fast_assign_btrfs(btrfs_work_owner(work),
@@ -1312,12 +1319,12 @@ DECLARE_EVENT_CLASS(btrfs__work,
*/
DECLARE_EVENT_CLASS(btrfs__work__done,
- TP_PROTO(struct btrfs_fs_info *fs_info, void *wtag),
+ TP_PROTO(const struct btrfs_fs_info *fs_info, const void *wtag),
TP_ARGS(fs_info, wtag),
TP_STRUCT__entry_btrfs(
- __field( void *, wtag )
+ __field( const void *, wtag )
),
TP_fast_assign_btrfs(fs_info,
@@ -1329,40 +1336,41 @@ DECLARE_EVENT_CLASS(btrfs__work__done,
DEFINE_EVENT(btrfs__work, btrfs_work_queued,
- TP_PROTO(struct btrfs_work *work),
+ TP_PROTO(const struct btrfs_work *work),
TP_ARGS(work)
);
DEFINE_EVENT(btrfs__work, btrfs_work_sched,
- TP_PROTO(struct btrfs_work *work),
+ TP_PROTO(const struct btrfs_work *work),
TP_ARGS(work)
);
DEFINE_EVENT(btrfs__work__done, btrfs_all_work_done,
- TP_PROTO(struct btrfs_fs_info *fs_info, void *wtag),
+ TP_PROTO(const struct btrfs_fs_info *fs_info, const void *wtag),
TP_ARGS(fs_info, wtag)
);
DEFINE_EVENT(btrfs__work, btrfs_ordered_sched,
- TP_PROTO(struct btrfs_work *work),
+ TP_PROTO(const struct btrfs_work *work),
TP_ARGS(work)
);
DECLARE_EVENT_CLASS(btrfs__workqueue,
- TP_PROTO(struct __btrfs_workqueue *wq, const char *name, int high),
+ TP_PROTO(const struct __btrfs_workqueue *wq,
+ const char *name, int high),
TP_ARGS(wq, name, high),
TP_STRUCT__entry_btrfs(
- __field( void *, wq )
+ __field( const void *, wq )
__string( name, name )
__field( int , high )
),
@@ -1381,19 +1389,20 @@ DECLARE_EVENT_CLASS(btrfs__workqueue,
DEFINE_EVENT(btrfs__workqueue, btrfs_workqueue_alloc,
- TP_PROTO(struct __btrfs_workqueue *wq, const char *name, int high),
+ TP_PROTO(const struct __btrfs_workqueue *wq,
+ const char *name, int high),
TP_ARGS(wq, name, high)
);
DECLARE_EVENT_CLASS(btrfs__workqueue_done,
- TP_PROTO(struct __btrfs_workqueue *wq),
+ TP_PROTO(const struct __btrfs_workqueue *wq),
TP_ARGS(wq),
TP_STRUCT__entry_btrfs(
- __field( void *, wq )
+ __field( const void *, wq )
),
TP_fast_assign_btrfs(btrfs_workqueue_owner(wq),
@@ -1405,7 +1414,7 @@ DECLARE_EVENT_CLASS(btrfs__workqueue_done,
DEFINE_EVENT(btrfs__workqueue_done, btrfs_workqueue_destroy,
- TP_PROTO(struct __btrfs_workqueue *wq),
+ TP_PROTO(const struct __btrfs_workqueue *wq),
TP_ARGS(wq)
);
@@ -1417,7 +1426,8 @@ DEFINE_EVENT(btrfs__workqueue_done, btrfs_workqueue_destroy,
DECLARE_EVENT_CLASS(btrfs__qgroup_rsv_data,
- TP_PROTO(struct inode *inode, u64 start, u64 len, u64 reserved, int op),
+ TP_PROTO(const struct inode *inode, u64 start, u64 len,
+ u64 reserved, int op),
TP_ARGS(inode, start, len, reserved, op),
@@ -1449,21 +1459,24 @@ DECLARE_EVENT_CLASS(btrfs__qgroup_rsv_data,
DEFINE_EVENT(btrfs__qgroup_rsv_data, btrfs_qgroup_reserve_data,
- TP_PROTO(struct inode *inode, u64 start, u64 len, u64 reserved, int op),
+ TP_PROTO(const struct inode *inode, u64 start, u64 len,
+ u64 reserved, int op),
TP_ARGS(inode, start, len, reserved, op)
);
DEFINE_EVENT(btrfs__qgroup_rsv_data, btrfs_qgroup_release_data,
- TP_PROTO(struct inode *inode, u64 start, u64 len, u64 reserved, int op),
+ TP_PROTO(const struct inode *inode, u64 start, u64 len,
+ u64 reserved, int op),
TP_ARGS(inode, start, len, reserved, op)
);
DECLARE_EVENT_CLASS(btrfs__qgroup_delayed_ref,
- TP_PROTO(struct btrfs_fs_info *fs_info, u64 ref_root, u64 reserved),
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ u64 ref_root, u64 reserved),
TP_ARGS(fs_info, ref_root, reserved),
@@ -1483,14 +1496,15 @@ DECLARE_EVENT_CLASS(btrfs__qgroup_delayed_ref,
DEFINE_EVENT(btrfs__qgroup_delayed_ref, btrfs_qgroup_free_delayed_ref,
- TP_PROTO(struct btrfs_fs_info *fs_info, u64 ref_root, u64 reserved),
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ u64 ref_root, u64 reserved),
TP_ARGS(fs_info, ref_root, reserved)
);
DECLARE_EVENT_CLASS(btrfs_qgroup_extent,
- TP_PROTO(struct btrfs_fs_info *fs_info,
- struct btrfs_qgroup_extent_record *rec),
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct btrfs_qgroup_extent_record *rec),
TP_ARGS(fs_info, rec),
@@ -1511,23 +1525,23 @@ DECLARE_EVENT_CLASS(btrfs_qgroup_extent,
DEFINE_EVENT(btrfs_qgroup_extent, btrfs_qgroup_account_extents,
- TP_PROTO(struct btrfs_fs_info *fs_info,
- struct btrfs_qgroup_extent_record *rec),
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct btrfs_qgroup_extent_record *rec),
TP_ARGS(fs_info, rec)
);
DEFINE_EVENT(btrfs_qgroup_extent, btrfs_qgroup_trace_extent,
- TP_PROTO(struct btrfs_fs_info *fs_info,
- struct btrfs_qgroup_extent_record *rec),
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct btrfs_qgroup_extent_record *rec),
TP_ARGS(fs_info, rec)
);
TRACE_EVENT(btrfs_qgroup_account_extent,
- TP_PROTO(struct btrfs_fs_info *fs_info, u64 bytenr,
+ TP_PROTO(const struct btrfs_fs_info *fs_info, u64 bytenr,
u64 num_bytes, u64 nr_old_roots, u64 nr_new_roots),
TP_ARGS(fs_info, bytenr, num_bytes, nr_old_roots, nr_new_roots),
@@ -1556,7 +1570,7 @@ TRACE_EVENT(btrfs_qgroup_account_extent,
TRACE_EVENT(qgroup_update_counters,
- TP_PROTO(struct btrfs_fs_info *fs_info, u64 qgid,
+ TP_PROTO(const struct btrfs_fs_info *fs_info, u64 qgid,
u64 cur_old_count, u64 cur_new_count),
TP_ARGS(fs_info, qgid, cur_old_count, cur_new_count),
--
2.10.2
^ permalink raw reply related [flat|nested] 23+ messages in thread
* [PATCH 03/13] btrfs: backref, constify some arguments
2017-06-20 16:06 [PATCH 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
2017-06-20 16:06 ` [PATCH 01/13] btrfs: struct-funcs, constify readers Edmund Nadolski
2017-06-20 16:06 ` [PATCH 02/13] btrfs: constify tracepoint arguments Edmund Nadolski
@ 2017-06-20 16:06 ` Edmund Nadolski
2017-06-20 16:06 ` [PATCH 04/13] btrfs: backref, add unode_aux_to_inode_list helper Edmund Nadolski
` (10 subsequent siblings)
13 siblings, 0 replies; 23+ messages in thread
From: Edmund Nadolski @ 2017-06-20 16:06 UTC (permalink / raw)
To: enadolski, linux-btrfs
From: Jeff Mahoney <jeffm@suse.com>
This constifies a few buffers used in the backref code.
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
fs/btrfs/backref.c | 29 ++++++++++++++++-------------
1 file changed, 16 insertions(+), 13 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index f723c11..9d6474d 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -299,10 +299,11 @@ static int ref_tree_add(struct ref_root *ref_tree, u64 root_id, u64 object_id,
return 0;
}
-static int check_extent_in_eb(struct btrfs_key *key, struct extent_buffer *eb,
- struct btrfs_file_extent_item *fi,
- u64 extent_item_pos,
- struct extent_inode_elem **eie)
+static int check_extent_in_eb(const struct btrfs_key *key,
+ const struct extent_buffer *eb,
+ const struct btrfs_file_extent_item *fi,
+ u64 extent_item_pos,
+ struct extent_inode_elem **eie)
{
u64 offset = 0;
struct extent_inode_elem *e;
@@ -344,9 +345,9 @@ static void free_inode_elem_list(struct extent_inode_elem *eie)
}
}
-static int find_extent_in_eb(struct extent_buffer *eb, u64 wanted_disk_byte,
- u64 extent_item_pos,
- struct extent_inode_elem **eie)
+static int find_extent_in_eb(const struct extent_buffer *eb,
+ u64 wanted_disk_byte, u64 extent_item_pos,
+ struct extent_inode_elem **eie)
{
u64 disk_byte;
struct btrfs_key key;
@@ -456,7 +457,7 @@ void btrfs_prelim_ref_exit(void)
*/
static int __add_prelim_ref(struct list_head *head, u64 root_id,
- struct btrfs_key *key, int level,
+ const struct btrfs_key *key, int level,
u64 parent, u64 wanted_disk_byte, int count,
gfp_t gfp_mask)
{
@@ -1649,7 +1650,7 @@ int btrfs_find_one_extref(struct btrfs_root *root, u64 inode_objectid,
struct btrfs_key key;
struct btrfs_key found_key;
struct btrfs_inode_extref *extref;
- struct extent_buffer *leaf;
+ const struct extent_buffer *leaf;
unsigned long ptr;
key.objectid = inode_objectid;
@@ -1806,7 +1807,7 @@ int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,
u64 flags;
u64 size = 0;
u32 item_size;
- struct extent_buffer *eb;
+ const struct extent_buffer *eb;
struct btrfs_extent_item *ei;
struct btrfs_key key;
@@ -1874,9 +1875,11 @@ int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,
* next ref. after the last ref was processed, 1 is returned.
* returns <0 on error
*/
-static int __get_extent_inline_ref(unsigned long *ptr, struct extent_buffer *eb,
- struct btrfs_key *key,
- struct btrfs_extent_item *ei, u32 item_size,
+static int __get_extent_inline_ref(unsigned long *ptr,
+ const struct extent_buffer *eb,
+ const struct btrfs_key *key,
+ const struct btrfs_extent_item *ei,
+ u32 item_size,
struct btrfs_extent_inline_ref **out_eiref,
int *out_type)
{
--
2.10.2
^ permalink raw reply related [flat|nested] 23+ messages in thread
* [PATCH 04/13] btrfs: backref, add unode_aux_to_inode_list helper
2017-06-20 16:06 [PATCH 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (2 preceding siblings ...)
2017-06-20 16:06 ` [PATCH 03/13] btrfs: backref, constify some arguments Edmund Nadolski
@ 2017-06-20 16:06 ` Edmund Nadolski
2017-06-20 16:06 ` [PATCH 05/13] btrfs: backref, cleanup __ namespace abuse Edmund Nadolski
` (9 subsequent siblings)
13 siblings, 0 replies; 23+ messages in thread
From: Edmund Nadolski @ 2017-06-20 16:06 UTC (permalink / raw)
To: enadolski, linux-btrfs
From: Jeff Mahoney <jeffm@suse.com>
Replacing the double cast and ternary conditional with a helper makes
the code easier on the eyes.
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
fs/btrfs/backref.c | 16 +++++++++++-----
1 file changed, 11 insertions(+), 5 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 9d6474d..4a7a4b0 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -682,6 +682,14 @@ static int __resolve_indirect_ref(struct btrfs_fs_info *fs_info,
return ret;
}
+static struct extent_inode_elem *
+unode_aux_to_inode_list(struct ulist_node *node)
+{
+ if (!node)
+ return NULL;
+ return (struct extent_inode_elem *)(uintptr_t)node->aux;
+}
+
/*
* resolve all indirect backrefs from the list
*/
@@ -736,8 +744,7 @@ static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info,
ULIST_ITER_INIT(&uiter);
node = ulist_next(parents, &uiter);
ref->parent = node ? node->val : 0;
- ref->inode_list = node ?
- (struct extent_inode_elem *)(uintptr_t)node->aux : NULL;
+ ref->inode_list = unode_aux_to_inode_list(node);
/* additional parents require new refs being added here */
while ((node = ulist_next(parents, &uiter))) {
@@ -749,8 +756,7 @@ static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info,
}
memcpy(new_ref, ref, sizeof(*ref));
new_ref->parent = node->val;
- new_ref->inode_list = (struct extent_inode_elem *)
- (uintptr_t)node->aux;
+ new_ref->inode_list = unode_aux_to_inode_list(node);
list_add(&new_ref->list, &ref->list);
}
ulist_reinit(parents);
@@ -1476,7 +1482,7 @@ static void free_leaf_list(struct ulist *blocks)
while ((node = ulist_next(blocks, &uiter))) {
if (!node->aux)
continue;
- eie = (struct extent_inode_elem *)(uintptr_t)node->aux;
+ eie = unode_aux_to_inode_list(node);
free_inode_elem_list(eie);
node->aux = 0;
}
--
2.10.2
^ permalink raw reply related [flat|nested] 23+ messages in thread
* [PATCH 05/13] btrfs: backref, cleanup __ namespace abuse
2017-06-20 16:06 [PATCH 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (3 preceding siblings ...)
2017-06-20 16:06 ` [PATCH 04/13] btrfs: backref, add unode_aux_to_inode_list helper Edmund Nadolski
@ 2017-06-20 16:06 ` Edmund Nadolski
2017-06-20 16:06 ` [PATCH 06/13] btrfs: btrfs_check_shared should manage its own transaction Edmund Nadolski
` (8 subsequent siblings)
13 siblings, 0 replies; 23+ messages in thread
From: Edmund Nadolski @ 2017-06-20 16:06 UTC (permalink / raw)
To: enadolski, linux-btrfs
From: Jeff Mahoney <jeffm@suse.com>
We typically use __ to indicate a helper routine that shouldn't be
called directly without understanding the proper context required
to do so. We use static functions to indicate that a function is
private to a particular C file. The backref code uses static
function and __ prefixes on nearly everything, which makes the code
difficult to read and establishes a pattern for future code that
shouldn't be followed. This patch drops all the unnecessary prefixes.
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
fs/btrfs/backref.c | 225 ++++++++++++++++++++++++++---------------------------
1 file changed, 109 insertions(+), 116 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 4a7a4b0..3725277 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -387,7 +387,7 @@ static int find_extent_in_eb(const struct extent_buffer *eb,
/*
* this structure records all encountered refs on the way up to the root
*/
-struct __prelim_ref {
+struct prelim_ref {
struct list_head list;
u64 root_id;
struct btrfs_key key_for_search;
@@ -403,7 +403,7 @@ static struct kmem_cache *btrfs_prelim_ref_cache;
int __init btrfs_prelim_ref_init(void)
{
btrfs_prelim_ref_cache = kmem_cache_create("btrfs_prelim_ref",
- sizeof(struct __prelim_ref),
+ sizeof(struct prelim_ref),
0,
SLAB_MEM_SPREAD,
NULL);
@@ -449,19 +449,17 @@ void btrfs_prelim_ref_exit(void)
*
* - column 1, 3: we've the parent -> done
* - column 2: we take the first key from the block to find the parent
- * (see __add_missing_keys)
+ * (see add_missing_keys)
* - column 4: we use the key to find the parent
*
* additional information that's available but not required to find the parent
* block might help in merging entries to gain some speed.
*/
-
-static int __add_prelim_ref(struct list_head *head, u64 root_id,
- const struct btrfs_key *key, int level,
- u64 parent, u64 wanted_disk_byte, int count,
- gfp_t gfp_mask)
+static int add_prelim_ref(struct list_head *head, u64 root_id,
+ const struct btrfs_key *key, int level, u64 parent,
+ u64 wanted_disk_byte, int count, gfp_t gfp_mask)
{
- struct __prelim_ref *ref;
+ struct prelim_ref *ref;
if (root_id == BTRFS_DATA_RELOC_TREE_OBJECTID)
return 0;
@@ -510,7 +508,7 @@ static int __add_prelim_ref(struct list_head *head, u64 root_id,
}
static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
- struct ulist *parents, struct __prelim_ref *ref,
+ struct ulist *parents, struct prelim_ref *ref,
int level, u64 time_seq, const u64 *extent_item_pos,
u64 total_refs)
{
@@ -600,11 +598,10 @@ static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
* resolve an indirect backref in the form (root_id, key, level)
* to a logical address
*/
-static int __resolve_indirect_ref(struct btrfs_fs_info *fs_info,
- struct btrfs_path *path, u64 time_seq,
- struct __prelim_ref *ref,
- struct ulist *parents,
- const u64 *extent_item_pos, u64 total_refs)
+static int resolve_indirect_ref(struct btrfs_fs_info *fs_info,
+ struct btrfs_path *path, u64 time_seq,
+ struct prelim_ref *ref, struct ulist *parents,
+ const u64 *extent_item_pos, u64 total_refs)
{
struct btrfs_root *root;
struct btrfs_key root_key;
@@ -693,17 +690,17 @@ unode_aux_to_inode_list(struct ulist_node *node)
/*
* resolve all indirect backrefs from the list
*/
-static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info,
- struct btrfs_path *path, u64 time_seq,
- struct list_head *head,
- const u64 *extent_item_pos, u64 total_refs,
- u64 root_objectid)
+static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
+ struct btrfs_path *path, u64 time_seq,
+ struct list_head *head,
+ const u64 *extent_item_pos, u64 total_refs,
+ u64 root_objectid)
{
int err;
int ret = 0;
- struct __prelim_ref *ref;
- struct __prelim_ref *ref_safe;
- struct __prelim_ref *new_ref;
+ struct prelim_ref *ref;
+ struct prelim_ref *ref_safe;
+ struct prelim_ref *new_ref;
struct ulist *parents;
struct ulist_node *node;
struct ulist_iterator uiter;
@@ -726,9 +723,9 @@ static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info,
ret = BACKREF_FOUND_SHARED;
goto out;
}
- err = __resolve_indirect_ref(fs_info, path, time_seq, ref,
- parents, extent_item_pos,
- total_refs);
+ err = resolve_indirect_ref(fs_info, path, time_seq, ref,
+ parents, extent_item_pos,
+ total_refs);
/*
* we can only tolerate ENOENT,otherwise,we should catch error
* and return directly.
@@ -766,8 +763,8 @@ static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info,
return ret;
}
-static inline int ref_for_same_block(struct __prelim_ref *ref1,
- struct __prelim_ref *ref2)
+static inline int ref_for_same_block(struct prelim_ref *ref1,
+ struct prelim_ref *ref2)
{
if (ref1->level != ref2->level)
return 0;
@@ -788,10 +785,10 @@ static inline int ref_for_same_block(struct __prelim_ref *ref1,
/*
* read tree blocks and add keys where required.
*/
-static int __add_missing_keys(struct btrfs_fs_info *fs_info,
- struct list_head *head)
+static int add_missing_keys(struct btrfs_fs_info *fs_info,
+ struct list_head *head)
{
- struct __prelim_ref *ref;
+ struct prelim_ref *ref;
struct extent_buffer *eb;
list_for_each_entry(ref, head, list) {
@@ -821,20 +818,20 @@ static int __add_missing_keys(struct btrfs_fs_info *fs_info,
/*
* merge backrefs and adjust counts accordingly
*
- * FIXME: For MERGE_IDENTICAL_KEYS, if we add more keys in __add_prelim_ref
+ * FIXME: For MERGE_IDENTICAL_KEYS, if we add more keys in add_prelim_ref
* then we can merge more here. Additionally, we could even add a key
* range for the blocks we looked into to merge even more (-> replace
* unresolved refs by those having a parent).
*/
-static void __merge_refs(struct list_head *head, enum merge_mode mode)
+static void merge_refs(struct list_head *head, enum merge_mode mode)
{
- struct __prelim_ref *pos1;
+ struct prelim_ref *pos1;
list_for_each_entry(pos1, head, list) {
- struct __prelim_ref *pos2 = pos1, *tmp;
+ struct prelim_ref *pos2 = pos1, *tmp;
list_for_each_entry_safe_continue(pos2, tmp, head, list) {
- struct __prelim_ref *ref1 = pos1, *ref2 = pos2;
+ struct prelim_ref *ref1 = pos1, *ref2 = pos2;
struct extent_inode_elem *eie;
if (!ref_for_same_block(ref1, ref2))
@@ -868,9 +865,9 @@ static void __merge_refs(struct list_head *head, enum merge_mode mode)
* add all currently queued delayed refs from this head whose seq nr is
* smaller or equal that seq to the list
*/
-static int __add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
- struct list_head *prefs, u64 *total_refs,
- u64 inum)
+static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
+ struct list_head *prefs, u64 *total_refs,
+ u64 inum)
{
struct btrfs_delayed_ref_node *node;
struct btrfs_delayed_extent_op *extent_op = head->extent_op;
@@ -907,19 +904,18 @@ static int __add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
struct btrfs_delayed_tree_ref *ref;
ref = btrfs_delayed_node_to_tree_ref(node);
- ret = __add_prelim_ref(prefs, ref->root, &op_key,
- ref->level + 1, 0, node->bytenr,
- node->ref_mod * sgn, GFP_ATOMIC);
+ ret = add_prelim_ref(prefs, ref->root, &op_key,
+ ref->level + 1, 0, node->bytenr,
+ node->ref_mod * sgn, GFP_ATOMIC);
break;
}
case BTRFS_SHARED_BLOCK_REF_KEY: {
struct btrfs_delayed_tree_ref *ref;
ref = btrfs_delayed_node_to_tree_ref(node);
- ret = __add_prelim_ref(prefs, 0, NULL,
- ref->level + 1, ref->parent,
- node->bytenr,
- node->ref_mod * sgn, GFP_ATOMIC);
+ ret = add_prelim_ref(prefs, 0, NULL, ref->level + 1,
+ ref->parent, node->bytenr,
+ node->ref_mod * sgn, GFP_ATOMIC);
break;
}
case BTRFS_EXTENT_DATA_REF_KEY: {
@@ -939,18 +935,18 @@ static int __add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
break;
}
- ret = __add_prelim_ref(prefs, ref->root, &key, 0, 0,
- node->bytenr,
- node->ref_mod * sgn, GFP_ATOMIC);
+ ret = add_prelim_ref(prefs, ref->root, &key, 0, 0,
+ node->bytenr, node->ref_mod * sgn,
+ GFP_ATOMIC);
break;
}
case BTRFS_SHARED_DATA_REF_KEY: {
struct btrfs_delayed_data_ref *ref;
ref = btrfs_delayed_node_to_data_ref(node);
- ret = __add_prelim_ref(prefs, 0, NULL, 0,
- ref->parent, node->bytenr,
- node->ref_mod * sgn, GFP_ATOMIC);
+ ret = add_prelim_ref(prefs, 0, NULL, 0, ref->parent,
+ node->bytenr, node->ref_mod * sgn,
+ GFP_ATOMIC);
break;
}
default:
@@ -966,10 +962,10 @@ static int __add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
/*
* add all inline backrefs for bytenr to the list
*/
-static int __add_inline_refs(struct btrfs_path *path, u64 bytenr,
- int *info_level, struct list_head *prefs,
- struct ref_root *ref_tree,
- u64 *total_refs, u64 inum)
+static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
+ int *info_level, struct list_head *prefs,
+ struct ref_root *ref_tree,
+ u64 *total_refs, u64 inum)
{
int ret = 0;
int slot;
@@ -1024,9 +1020,8 @@ static int __add_inline_refs(struct btrfs_path *path, u64 bytenr,
switch (type) {
case BTRFS_SHARED_BLOCK_REF_KEY:
- ret = __add_prelim_ref(prefs, 0, NULL,
- *info_level + 1, offset,
- bytenr, 1, GFP_NOFS);
+ ret = add_prelim_ref(prefs, 0, NULL, *info_level + 1,
+ offset, bytenr, 1, GFP_NOFS);
break;
case BTRFS_SHARED_DATA_REF_KEY: {
struct btrfs_shared_data_ref *sdref;
@@ -1034,8 +1029,8 @@ static int __add_inline_refs(struct btrfs_path *path, u64 bytenr,
sdref = (struct btrfs_shared_data_ref *)(iref + 1);
count = btrfs_shared_data_ref_count(leaf, sdref);
- ret = __add_prelim_ref(prefs, 0, NULL, 0, offset,
- bytenr, count, GFP_NOFS);
+ ret = add_prelim_ref(prefs, 0, NULL, 0, offset,
+ bytenr, count, GFP_NOFS);
if (ref_tree) {
if (!ret)
ret = ref_tree_add(ref_tree, 0, 0, 0,
@@ -1046,9 +1041,9 @@ static int __add_inline_refs(struct btrfs_path *path, u64 bytenr,
break;
}
case BTRFS_TREE_BLOCK_REF_KEY:
- ret = __add_prelim_ref(prefs, offset, NULL,
- *info_level + 1, 0,
- bytenr, 1, GFP_NOFS);
+ ret = add_prelim_ref(prefs, offset, NULL,
+ *info_level + 1, 0,
+ bytenr, 1, GFP_NOFS);
break;
case BTRFS_EXTENT_DATA_REF_KEY: {
struct btrfs_extent_data_ref *dref;
@@ -1068,8 +1063,8 @@ static int __add_inline_refs(struct btrfs_path *path, u64 bytenr,
}
root = btrfs_extent_data_ref_root(leaf, dref);
- ret = __add_prelim_ref(prefs, root, &key, 0, 0,
- bytenr, count, GFP_NOFS);
+ ret = add_prelim_ref(prefs, root, &key, 0, 0,
+ bytenr, count, GFP_NOFS);
if (ref_tree) {
if (!ret)
ret = ref_tree_add(ref_tree, root,
@@ -1095,10 +1090,10 @@ static int __add_inline_refs(struct btrfs_path *path, u64 bytenr,
/*
* add all non-inline backrefs for bytenr to the list
*/
-static int __add_keyed_refs(struct btrfs_fs_info *fs_info,
- struct btrfs_path *path, u64 bytenr,
- int info_level, struct list_head *prefs,
- struct ref_root *ref_tree, u64 inum)
+static int add_keyed_refs(struct btrfs_fs_info *fs_info,
+ struct btrfs_path *path, u64 bytenr,
+ int info_level, struct list_head *prefs,
+ struct ref_root *ref_tree, u64 inum)
{
struct btrfs_root *extent_root = fs_info->extent_root;
int ret;
@@ -1128,9 +1123,8 @@ static int __add_keyed_refs(struct btrfs_fs_info *fs_info,
switch (key.type) {
case BTRFS_SHARED_BLOCK_REF_KEY:
- ret = __add_prelim_ref(prefs, 0, NULL,
- info_level + 1, key.offset,
- bytenr, 1, GFP_NOFS);
+ ret = add_prelim_ref(prefs, 0, NULL, info_level + 1,
+ key.offset, bytenr, 1, GFP_NOFS);
break;
case BTRFS_SHARED_DATA_REF_KEY: {
struct btrfs_shared_data_ref *sdref;
@@ -1139,8 +1133,8 @@ static int __add_keyed_refs(struct btrfs_fs_info *fs_info,
sdref = btrfs_item_ptr(leaf, slot,
struct btrfs_shared_data_ref);
count = btrfs_shared_data_ref_count(leaf, sdref);
- ret = __add_prelim_ref(prefs, 0, NULL, 0, key.offset,
- bytenr, count, GFP_NOFS);
+ ret = add_prelim_ref(prefs, 0, NULL, 0, key.offset,
+ bytenr, count, GFP_NOFS);
if (ref_tree) {
if (!ret)
ret = ref_tree_add(ref_tree, 0, 0, 0,
@@ -1151,9 +1145,9 @@ static int __add_keyed_refs(struct btrfs_fs_info *fs_info,
break;
}
case BTRFS_TREE_BLOCK_REF_KEY:
- ret = __add_prelim_ref(prefs, key.offset, NULL,
- info_level + 1, 0,
- bytenr, 1, GFP_NOFS);
+ ret = add_prelim_ref(prefs, key.offset, NULL,
+ info_level + 1, 0,
+ bytenr, 1, GFP_NOFS);
break;
case BTRFS_EXTENT_DATA_REF_KEY: {
struct btrfs_extent_data_ref *dref;
@@ -1174,8 +1168,8 @@ static int __add_keyed_refs(struct btrfs_fs_info *fs_info,
}
root = btrfs_extent_data_ref_root(leaf, dref);
- ret = __add_prelim_ref(prefs, root, &key, 0, 0,
- bytenr, count, GFP_NOFS);
+ ret = add_prelim_ref(prefs, root, &key, 0, 0,
+ bytenr, count, GFP_NOFS);
if (ref_tree) {
if (!ret)
ret = ref_tree_add(ref_tree, root,
@@ -1230,7 +1224,7 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
int ret;
struct list_head prefs_delayed;
struct list_head prefs;
- struct __prelim_ref *ref;
+ struct prelim_ref *ref;
struct extent_inode_elem *eie = NULL;
struct ref_root *ref_tree = NULL;
u64 total_refs = 0;
@@ -1311,9 +1305,9 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
goto again;
}
spin_unlock(&delayed_refs->lock);
- ret = __add_delayed_refs(head, time_seq,
- &prefs_delayed, &total_refs,
- inum);
+ ret = add_delayed_refs(head, time_seq,
+ &prefs_delayed, &total_refs,
+ inum);
mutex_unlock(&head->mutex);
if (ret)
goto out;
@@ -1363,15 +1357,13 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
if (key.objectid == bytenr &&
(key.type == BTRFS_EXTENT_ITEM_KEY ||
key.type == BTRFS_METADATA_ITEM_KEY)) {
- ret = __add_inline_refs(path, bytenr,
- &info_level, &prefs,
- ref_tree, &total_refs,
- inum);
+ ret = add_inline_refs(path, bytenr, &info_level,
+ &prefs, ref_tree, &total_refs,
+ inum);
if (ret)
goto out;
- ret = __add_keyed_refs(fs_info, path, bytenr,
- info_level, &prefs,
- ref_tree, inum);
+ ret = add_keyed_refs(fs_info, path, bytenr, info_level,
+ &prefs, ref_tree, inum);
if (ret)
goto out;
}
@@ -1380,22 +1372,22 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
list_splice_init(&prefs_delayed, &prefs);
- ret = __add_missing_keys(fs_info, &prefs);
+ ret = add_missing_keys(fs_info, &prefs);
if (ret)
goto out;
- __merge_refs(&prefs, MERGE_IDENTICAL_KEYS);
+ merge_refs(&prefs, MERGE_IDENTICAL_KEYS);
- ret = __resolve_indirect_refs(fs_info, path, time_seq, &prefs,
- extent_item_pos, total_refs,
- root_objectid);
+ ret = resolve_indirect_refs(fs_info, path, time_seq, &prefs,
+ extent_item_pos, total_refs,
+ root_objectid);
if (ret)
goto out;
- __merge_refs(&prefs, MERGE_IDENTICAL_PARENTS);
+ merge_refs(&prefs, MERGE_IDENTICAL_PARENTS);
while (!list_empty(&prefs)) {
- ref = list_first_entry(&prefs, struct __prelim_ref, list);
+ ref = list_first_entry(&prefs, struct prelim_ref, list);
WARN_ON(ref->count < 0);
if (roots && ref->count && ref->root_id && ref->parent == 0) {
if (root_objectid && ref->root_id != root_objectid) {
@@ -1457,12 +1449,12 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
btrfs_free_path(path);
ref_root_free(ref_tree);
while (!list_empty(&prefs)) {
- ref = list_first_entry(&prefs, struct __prelim_ref, list);
+ ref = list_first_entry(&prefs, struct prelim_ref, list);
list_del(&ref->list);
kmem_cache_free(btrfs_prelim_ref_cache, ref);
}
while (!list_empty(&prefs_delayed)) {
- ref = list_first_entry(&prefs_delayed, struct __prelim_ref,
+ ref = list_first_entry(&prefs_delayed, struct prelim_ref,
list);
list_del(&ref->list);
kmem_cache_free(btrfs_prelim_ref_cache, ref);
@@ -1532,9 +1524,9 @@ static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
*
* returns 0 on success, < 0 on error.
*/
-static int __btrfs_find_all_roots(struct btrfs_trans_handle *trans,
- struct btrfs_fs_info *fs_info, u64 bytenr,
- u64 time_seq, struct ulist **roots)
+static int btrfs_find_all_roots_safe(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info, u64 bytenr,
+ u64 time_seq, struct ulist **roots)
{
struct ulist *tmp;
struct ulist_node *node = NULL;
@@ -1578,7 +1570,8 @@ int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
if (!trans)
down_read(&fs_info->commit_root_sem);
- ret = __btrfs_find_all_roots(trans, fs_info, bytenr, time_seq, roots);
+ ret = btrfs_find_all_roots_safe(trans, fs_info, bytenr,
+ time_seq, roots);
if (!trans)
up_read(&fs_info->commit_root_sem);
return ret;
@@ -1877,17 +1870,17 @@ int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,
* helper function to iterate extent inline refs. ptr must point to a 0 value
* for the first call and may be modified. it is used to track state.
* if more refs exist, 0 is returned and the next call to
- * __get_extent_inline_ref must pass the modified ptr parameter to get the
+ * get_extent_inline_ref must pass the modified ptr parameter to get the
* next ref. after the last ref was processed, 1 is returned.
* returns <0 on error
*/
-static int __get_extent_inline_ref(unsigned long *ptr,
- const struct extent_buffer *eb,
- const struct btrfs_key *key,
- const struct btrfs_extent_item *ei,
- u32 item_size,
- struct btrfs_extent_inline_ref **out_eiref,
- int *out_type)
+static int get_extent_inline_ref(unsigned long *ptr,
+ const struct extent_buffer *eb,
+ const struct btrfs_key *key,
+ const struct btrfs_extent_item *ei,
+ u32 item_size,
+ struct btrfs_extent_inline_ref **out_eiref,
+ int *out_type)
{
unsigned long end;
u64 flags;
@@ -1930,7 +1923,7 @@ static int __get_extent_inline_ref(unsigned long *ptr,
/*
* reads the tree block backref for an extent. tree level and root are returned
* through out_level and out_root. ptr must point to a 0 value for the first
- * call and may be modified (see __get_extent_inline_ref comment).
+ * call and may be modified (see get_extent_inline_ref comment).
* returns 0 if data was provided, 1 if there was no more data to provide or
* <0 on error.
*/
@@ -1946,7 +1939,7 @@ int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb,
return 1;
while (1) {
- ret = __get_extent_inline_ref(ptr, eb, key, ei, item_size,
+ ret = get_extent_inline_ref(ptr, eb, key, ei, item_size,
&eiref, &type);
if (ret < 0)
return ret;
@@ -2043,8 +2036,8 @@ int iterate_extent_inodes(struct btrfs_fs_info *fs_info,
ULIST_ITER_INIT(&ref_uiter);
while (!ret && (ref_node = ulist_next(refs, &ref_uiter))) {
- ret = __btrfs_find_all_roots(trans, fs_info, ref_node->val,
- tree_mod_seq_elem.seq, &roots);
+ ret = btrfs_find_all_roots_safe(trans, fs_info, ref_node->val,
+ tree_mod_seq_elem.seq, &roots);
if (ret)
break;
ULIST_ITER_INIT(&root_uiter);
--
2.10.2
^ permalink raw reply related [flat|nested] 23+ messages in thread
* [PATCH 06/13] btrfs: btrfs_check_shared should manage its own transaction
2017-06-20 16:06 [PATCH 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (4 preceding siblings ...)
2017-06-20 16:06 ` [PATCH 05/13] btrfs: backref, cleanup __ namespace abuse Edmund Nadolski
@ 2017-06-20 16:06 ` Edmund Nadolski
2017-06-27 15:40 ` David Sterba
2017-06-20 16:06 ` [PATCH 07/13] btrfs: remove ref_tree implementation from backref.c Edmund Nadolski
` (7 subsequent siblings)
13 siblings, 1 reply; 23+ messages in thread
From: Edmund Nadolski @ 2017-06-20 16:06 UTC (permalink / raw)
To: enadolski, linux-btrfs
Signed-off-by: Edmund Nadolski <enadolski@suse.com>
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
fs/btrfs/backref.c | 30 +++++++++++++++++++-----------
fs/btrfs/backref.h | 4 +---
fs/btrfs/extent_io.c | 22 +++-------------------
3 files changed, 23 insertions(+), 33 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 3725277..35cfa38 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -1580,20 +1580,21 @@ int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
/**
* btrfs_check_shared - tell us whether an extent is shared
*
- * @trans: optional trans handle
- *
* btrfs_check_shared uses the backref walking code but will short
* circuit as soon as it finds a root or inode that doesn't match the
* one passed in. This provides a significant performance benefit for
* callers (such as fiemap) which want to know whether the extent is
* shared but do not need a ref count.
*
+ * This attempts to allocate a transaction in order to account for
+ * delayed refs, but continues on even when the alloc fails.
+ *
* Return: 0 if extent is not shared, 1 if it is shared, < 0 on error.
*/
-int btrfs_check_shared(struct btrfs_trans_handle *trans,
- struct btrfs_fs_info *fs_info, u64 root_objectid,
- u64 inum, u64 bytenr)
+int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr)
{
+ struct btrfs_fs_info *fs_info = root->fs_info;
+ struct btrfs_trans_handle *trans;
struct ulist *tmp = NULL;
struct ulist *roots = NULL;
struct ulist_iterator uiter;
@@ -1609,14 +1610,18 @@ int btrfs_check_shared(struct btrfs_trans_handle *trans,
return -ENOMEM;
}
- if (trans)
- btrfs_get_tree_mod_seq(fs_info, &elem);
- else
+ trans = btrfs_join_transaction(root);
+ if (IS_ERR(trans)) {
+ trans = NULL;
down_read(&fs_info->commit_root_sem);
+ } else {
+ btrfs_get_tree_mod_seq(fs_info, &elem);
+ }
+
ULIST_ITER_INIT(&uiter);
while (1) {
ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp,
- roots, NULL, root_objectid, inum, 1);
+ roots, NULL, root->objectid, inum, 1);
if (ret == BACKREF_FOUND_SHARED) {
/* this is the only condition under which we return 1 */
ret = 1;
@@ -1631,10 +1636,13 @@ int btrfs_check_shared(struct btrfs_trans_handle *trans,
bytenr = node->val;
cond_resched();
}
- if (trans)
+
+ if (trans) {
btrfs_put_tree_mod_seq(fs_info, &elem);
- else
+ btrfs_end_transaction(trans);
+ } else {
up_read(&fs_info->commit_root_sem);
+ }
ulist_free(tmp);
ulist_free(roots);
return ret;
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 9c41fba..f9428aa 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -68,9 +68,7 @@ int btrfs_find_one_extref(struct btrfs_root *root, u64 inode_objectid,
u64 start_off, struct btrfs_path *path,
struct btrfs_inode_extref **ret_extref,
u64 *found_off);
-int btrfs_check_shared(struct btrfs_trans_handle *trans,
- struct btrfs_fs_info *fs_info, u64 root_objectid,
- u64 inum, u64 bytenr);
+int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr);
int __init btrfs_prelim_ref_init(void);
void btrfs_prelim_ref_exit(void);
diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 7ee62f6..ae31046 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -20,7 +20,6 @@
#include "locking.h"
#include "rcu-string.h"
#include "backref.h"
-#include "transaction.h"
static struct kmem_cache *extent_state_cache;
static struct kmem_cache *extent_buffer_cache;
@@ -4607,36 +4606,21 @@ int extent_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
flags |= (FIEMAP_EXTENT_DELALLOC |
FIEMAP_EXTENT_UNKNOWN);
} else if (fieinfo->fi_extents_max) {
- struct btrfs_trans_handle *trans;
-
u64 bytenr = em->block_start -
(em->start - em->orig_start);
disko = em->block_start + offset_in_extent;
/*
- * We need a trans handle to get delayed refs
- */
- trans = btrfs_join_transaction(root);
- /*
- * It's OK if we can't start a trans we can still check
- * from commit_root
- */
- if (IS_ERR(trans))
- trans = NULL;
-
- /*
* As btrfs supports shared space, this information
* can be exported to userspace tools via
* flag FIEMAP_EXTENT_SHARED. If fi_extents_max == 0
* then we're just getting a count and we can skip the
* lookup stuff.
*/
- ret = btrfs_check_shared(trans, root->fs_info,
- root->objectid,
- btrfs_ino(BTRFS_I(inode)), bytenr);
- if (trans)
- btrfs_end_transaction(trans);
+ ret = btrfs_check_shared(root,
+ btrfs_ino(BTRFS_I(inode)),
+ bytenr);
if (ret < 0)
goto out_free;
if (ret)
--
2.10.2
^ permalink raw reply related [flat|nested] 23+ messages in thread
* [PATCH 07/13] btrfs: remove ref_tree implementation from backref.c
2017-06-20 16:06 [PATCH 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (5 preceding siblings ...)
2017-06-20 16:06 ` [PATCH 06/13] btrfs: btrfs_check_shared should manage its own transaction Edmund Nadolski
@ 2017-06-20 16:06 ` Edmund Nadolski
2017-06-27 15:48 ` David Sterba
2017-06-20 16:06 ` [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees Edmund Nadolski
` (6 subsequent siblings)
13 siblings, 1 reply; 23+ messages in thread
From: Edmund Nadolski @ 2017-06-20 16:06 UTC (permalink / raw)
To: enadolski, linux-btrfs
The BACKREF_FOUND_SHARED checking will be addressed in an upcoming
patch.
Signed-off-by: Edmund Nadolski <enadolski@suse.com>
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
fs/btrfs/backref.c | 356 ++---------------------------------------------------
1 file changed, 8 insertions(+), 348 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 35cfa38..0d1e7cb 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -40,265 +40,6 @@ struct extent_inode_elem {
struct extent_inode_elem *next;
};
-/*
- * ref_root is used as the root of the ref tree that hold a collection
- * of unique references.
- */
-struct ref_root {
- struct rb_root rb_root;
-
- /*
- * The unique_refs represents the number of ref_nodes with a positive
- * count stored in the tree. Even if a ref_node (the count is greater
- * than one) is added, the unique_refs will only increase by one.
- */
- unsigned int unique_refs;
-};
-
-/* ref_node is used to store a unique reference to the ref tree. */
-struct ref_node {
- struct rb_node rb_node;
-
- /* For NORMAL_REF, otherwise all these fields should be set to 0 */
- u64 root_id;
- u64 object_id;
- u64 offset;
-
- /* For SHARED_REF, otherwise parent field should be set to 0 */
- u64 parent;
-
- /* Ref to the ref_mod of btrfs_delayed_ref_node */
- int ref_mod;
-};
-
-/* Dynamically allocate and initialize a ref_root */
-static struct ref_root *ref_root_alloc(void)
-{
- struct ref_root *ref_tree;
-
- ref_tree = kmalloc(sizeof(*ref_tree), GFP_NOFS);
- if (!ref_tree)
- return NULL;
-
- ref_tree->rb_root = RB_ROOT;
- ref_tree->unique_refs = 0;
-
- return ref_tree;
-}
-
-/* Free all nodes in the ref tree, and reinit ref_root */
-static void ref_root_fini(struct ref_root *ref_tree)
-{
- struct ref_node *node;
- struct rb_node *next;
-
- while ((next = rb_first(&ref_tree->rb_root)) != NULL) {
- node = rb_entry(next, struct ref_node, rb_node);
- rb_erase(next, &ref_tree->rb_root);
- kfree(node);
- }
-
- ref_tree->rb_root = RB_ROOT;
- ref_tree->unique_refs = 0;
-}
-
-static void ref_root_free(struct ref_root *ref_tree)
-{
- if (!ref_tree)
- return;
-
- ref_root_fini(ref_tree);
- kfree(ref_tree);
-}
-
-/*
- * Compare ref_node with (root_id, object_id, offset, parent)
- *
- * The function compares two ref_node a and b. It returns an integer less
- * than, equal to, or greater than zero , respectively, to be less than, to
- * equal, or be greater than b.
- */
-static int ref_node_cmp(struct ref_node *a, struct ref_node *b)
-{
- if (a->root_id < b->root_id)
- return -1;
- else if (a->root_id > b->root_id)
- return 1;
-
- if (a->object_id < b->object_id)
- return -1;
- else if (a->object_id > b->object_id)
- return 1;
-
- if (a->offset < b->offset)
- return -1;
- else if (a->offset > b->offset)
- return 1;
-
- if (a->parent < b->parent)
- return -1;
- else if (a->parent > b->parent)
- return 1;
-
- return 0;
-}
-
-/*
- * Search ref_node with (root_id, object_id, offset, parent) in the tree
- *
- * if found, the pointer of the ref_node will be returned;
- * if not found, NULL will be returned and pos will point to the rb_node for
- * insert, pos_parent will point to pos'parent for insert;
-*/
-static struct ref_node *__ref_tree_search(struct ref_root *ref_tree,
- struct rb_node ***pos,
- struct rb_node **pos_parent,
- u64 root_id, u64 object_id,
- u64 offset, u64 parent)
-{
- struct ref_node *cur = NULL;
- struct ref_node entry;
- int ret;
-
- entry.root_id = root_id;
- entry.object_id = object_id;
- entry.offset = offset;
- entry.parent = parent;
-
- *pos = &ref_tree->rb_root.rb_node;
-
- while (**pos) {
- *pos_parent = **pos;
- cur = rb_entry(*pos_parent, struct ref_node, rb_node);
-
- ret = ref_node_cmp(cur, &entry);
- if (ret > 0)
- *pos = &(**pos)->rb_left;
- else if (ret < 0)
- *pos = &(**pos)->rb_right;
- else
- return cur;
- }
-
- return NULL;
-}
-
-/*
- * Insert a ref_node to the ref tree
- * @pos used for specifiy the position to insert
- * @pos_parent for specifiy pos's parent
- *
- * success, return 0;
- * ref_node already exists, return -EEXIST;
-*/
-static int ref_tree_insert(struct ref_root *ref_tree, struct rb_node **pos,
- struct rb_node *pos_parent, struct ref_node *ins)
-{
- struct rb_node **p = NULL;
- struct rb_node *parent = NULL;
- struct ref_node *cur = NULL;
-
- if (!pos) {
- cur = __ref_tree_search(ref_tree, &p, &parent, ins->root_id,
- ins->object_id, ins->offset,
- ins->parent);
- if (cur)
- return -EEXIST;
- } else {
- p = pos;
- parent = pos_parent;
- }
-
- rb_link_node(&ins->rb_node, parent, p);
- rb_insert_color(&ins->rb_node, &ref_tree->rb_root);
-
- return 0;
-}
-
-/* Erase and free ref_node, caller should update ref_root->unique_refs */
-static void ref_tree_remove(struct ref_root *ref_tree, struct ref_node *node)
-{
- rb_erase(&node->rb_node, &ref_tree->rb_root);
- kfree(node);
-}
-
-/*
- * Update ref_root->unique_refs
- *
- * Call __ref_tree_search
- * 1. if ref_node doesn't exist, ref_tree_insert this node, and update
- * ref_root->unique_refs:
- * if ref_node->ref_mod > 0, ref_root->unique_refs++;
- * if ref_node->ref_mod < 0, do noting;
- *
- * 2. if ref_node is found, then get origin ref_node->ref_mod, and update
- * ref_node->ref_mod.
- * if ref_node->ref_mod is equal to 0,then call ref_tree_remove
- *
- * according to origin_mod and new_mod, update ref_root->items
- * +----------------+--------------+-------------+
- * | |new_count <= 0|new_count > 0|
- * +----------------+--------------+-------------+
- * |origin_count < 0| 0 | 1 |
- * +----------------+--------------+-------------+
- * |origin_count > 0| -1 | 0 |
- * +----------------+--------------+-------------+
- *
- * In case of allocation failure, -ENOMEM is returned and the ref_tree stays
- * unaltered.
- * Success, return 0
- */
-static int ref_tree_add(struct ref_root *ref_tree, u64 root_id, u64 object_id,
- u64 offset, u64 parent, int count)
-{
- struct ref_node *node = NULL;
- struct rb_node **pos = NULL;
- struct rb_node *pos_parent = NULL;
- int origin_count;
- int ret;
-
- if (!count)
- return 0;
-
- node = __ref_tree_search(ref_tree, &pos, &pos_parent, root_id,
- object_id, offset, parent);
- if (node == NULL) {
- node = kmalloc(sizeof(*node), GFP_NOFS);
- if (!node)
- return -ENOMEM;
-
- node->root_id = root_id;
- node->object_id = object_id;
- node->offset = offset;
- node->parent = parent;
- node->ref_mod = count;
-
- ret = ref_tree_insert(ref_tree, pos, pos_parent, node);
- ASSERT(!ret);
- if (ret) {
- kfree(node);
- return ret;
- }
-
- ref_tree->unique_refs += node->ref_mod > 0 ? 1 : 0;
-
- return 0;
- }
-
- origin_count = node->ref_mod;
- node->ref_mod += count;
-
- if (node->ref_mod > 0)
- ref_tree->unique_refs += origin_count > 0 ? 0 : 1;
- else if (node->ref_mod <= 0)
- ref_tree->unique_refs += origin_count > 0 ? -1 : 0;
-
- if (!node->ref_mod)
- ref_tree_remove(ref_tree, node);
-
- return 0;
-}
-
static int check_extent_in_eb(const struct btrfs_key *key,
const struct extent_buffer *eb,
const struct btrfs_file_extent_item *fi,
@@ -964,7 +705,6 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
*/
static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
int *info_level, struct list_head *prefs,
- struct ref_root *ref_tree,
u64 *total_refs, u64 inum)
{
int ret = 0;
@@ -1031,13 +771,6 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
count = btrfs_shared_data_ref_count(leaf, sdref);
ret = add_prelim_ref(prefs, 0, NULL, 0, offset,
bytenr, count, GFP_NOFS);
- if (ref_tree) {
- if (!ret)
- ret = ref_tree_add(ref_tree, 0, 0, 0,
- bytenr, count);
- if (!ret && ref_tree->unique_refs > 1)
- ret = BACKREF_FOUND_SHARED;
- }
break;
}
case BTRFS_TREE_BLOCK_REF_KEY:
@@ -1065,15 +798,6 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
root = btrfs_extent_data_ref_root(leaf, dref);
ret = add_prelim_ref(prefs, root, &key, 0, 0,
bytenr, count, GFP_NOFS);
- if (ref_tree) {
- if (!ret)
- ret = ref_tree_add(ref_tree, root,
- key.objectid,
- key.offset, 0,
- count);
- if (!ret && ref_tree->unique_refs > 1)
- ret = BACKREF_FOUND_SHARED;
- }
break;
}
default:
@@ -1092,8 +816,7 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
*/
static int add_keyed_refs(struct btrfs_fs_info *fs_info,
struct btrfs_path *path, u64 bytenr,
- int info_level, struct list_head *prefs,
- struct ref_root *ref_tree, u64 inum)
+ int info_level, struct list_head *prefs, u64 inum)
{
struct btrfs_root *extent_root = fs_info->extent_root;
int ret;
@@ -1135,13 +858,6 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
count = btrfs_shared_data_ref_count(leaf, sdref);
ret = add_prelim_ref(prefs, 0, NULL, 0, key.offset,
bytenr, count, GFP_NOFS);
- if (ref_tree) {
- if (!ret)
- ret = ref_tree_add(ref_tree, 0, 0, 0,
- bytenr, count);
- if (!ret && ref_tree->unique_refs > 1)
- ret = BACKREF_FOUND_SHARED;
- }
break;
}
case BTRFS_TREE_BLOCK_REF_KEY:
@@ -1170,15 +886,6 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
root = btrfs_extent_data_ref_root(leaf, dref);
ret = add_prelim_ref(prefs, root, &key, 0, 0,
bytenr, count, GFP_NOFS);
- if (ref_tree) {
- if (!ret)
- ret = ref_tree_add(ref_tree, root,
- key.objectid,
- key.offset, 0,
- count);
- if (!ret && ref_tree->unique_refs > 1)
- ret = BACKREF_FOUND_SHARED;
- }
break;
}
default:
@@ -1205,16 +912,13 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
* commit root.
* The special case is for qgroup to search roots in commit_transaction().
*
- * If check_shared is set to 1, any extent has more than one ref item, will
- * be returned BACKREF_FOUND_SHARED immediately.
- *
* FIXME some caching might speed things up
*/
static int find_parent_nodes(struct btrfs_trans_handle *trans,
struct btrfs_fs_info *fs_info, u64 bytenr,
u64 time_seq, struct ulist *refs,
struct ulist *roots, const u64 *extent_item_pos,
- u64 root_objectid, u64 inum, int check_shared)
+ u64 root_objectid, u64 inum)
{
struct btrfs_key key;
struct btrfs_path *path;
@@ -1226,7 +930,6 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
struct list_head prefs;
struct prelim_ref *ref;
struct extent_inode_elem *eie = NULL;
- struct ref_root *ref_tree = NULL;
u64 total_refs = 0;
INIT_LIST_HEAD(&prefs);
@@ -1258,18 +961,6 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
again:
head = NULL;
- if (check_shared) {
- if (!ref_tree) {
- ref_tree = ref_root_alloc();
- if (!ref_tree) {
- ret = -ENOMEM;
- goto out;
- }
- } else {
- ref_root_fini(ref_tree);
- }
- }
-
ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0);
if (ret < 0)
goto out;
@@ -1314,36 +1005,6 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
} else {
spin_unlock(&delayed_refs->lock);
}
-
- if (check_shared && !list_empty(&prefs_delayed)) {
- /*
- * Add all delay_ref to the ref_tree and check if there
- * are multiple ref items added.
- */
- list_for_each_entry(ref, &prefs_delayed, list) {
- if (ref->key_for_search.type) {
- ret = ref_tree_add(ref_tree,
- ref->root_id,
- ref->key_for_search.objectid,
- ref->key_for_search.offset,
- 0, ref->count);
- if (ret)
- goto out;
- } else {
- ret = ref_tree_add(ref_tree, 0, 0, 0,
- ref->parent, ref->count);
- if (ret)
- goto out;
- }
-
- }
-
- if (ref_tree->unique_refs > 1) {
- ret = BACKREF_FOUND_SHARED;
- goto out;
- }
-
- }
}
if (path->slots[0]) {
@@ -1358,12 +1019,11 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
(key.type == BTRFS_EXTENT_ITEM_KEY ||
key.type == BTRFS_METADATA_ITEM_KEY)) {
ret = add_inline_refs(path, bytenr, &info_level,
- &prefs, ref_tree, &total_refs,
- inum);
+ &prefs, &total_refs, inum);
if (ret)
goto out;
ret = add_keyed_refs(fs_info, path, bytenr, info_level,
- &prefs, ref_tree, inum);
+ &prefs, inum);
if (ret)
goto out;
}
@@ -1447,7 +1107,6 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
out:
btrfs_free_path(path);
- ref_root_free(ref_tree);
while (!list_empty(&prefs)) {
ref = list_first_entry(&prefs, struct prelim_ref, list);
list_del(&ref->list);
@@ -1502,7 +1161,7 @@ static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
return -ENOMEM;
ret = find_parent_nodes(trans, fs_info, bytenr, time_seq,
- *leafs, NULL, extent_item_pos, 0, 0, 0);
+ *leafs, NULL, extent_item_pos, 0, 0);
if (ret < 0 && ret != -ENOENT) {
free_leaf_list(*leafs);
return ret;
@@ -1545,7 +1204,7 @@ static int btrfs_find_all_roots_safe(struct btrfs_trans_handle *trans,
ULIST_ITER_INIT(&uiter);
while (1) {
ret = find_parent_nodes(trans, fs_info, bytenr, time_seq,
- tmp, *roots, NULL, 0, 0, 0);
+ tmp, *roots, NULL, 0, 0);
if (ret < 0 && ret != -ENOENT) {
ulist_free(tmp);
ulist_free(*roots);
@@ -1620,8 +1279,9 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr)
ULIST_ITER_INIT(&uiter);
while (1) {
+ /* TODO - short-circuit when only checking for shared... */
ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp,
- roots, NULL, root->objectid, inum, 1);
+ roots, NULL, root->objectid, inum);
if (ret == BACKREF_FOUND_SHARED) {
/* this is the only condition under which we return 1 */
ret = 1;
--
2.10.2
^ permalink raw reply related [flat|nested] 23+ messages in thread
* [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees
2017-06-20 16:06 [PATCH 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (6 preceding siblings ...)
2017-06-20 16:06 ` [PATCH 07/13] btrfs: remove ref_tree implementation from backref.c Edmund Nadolski
@ 2017-06-20 16:06 ` Edmund Nadolski
2017-06-26 17:07 ` Jeff Mahoney
2017-06-27 16:49 ` [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees David Sterba
2017-06-20 16:06 ` [PATCH 09/13] btrfs: add a node counter to each of the rbtrees Edmund Nadolski
` (5 subsequent siblings)
13 siblings, 2 replies; 23+ messages in thread
From: Edmund Nadolski @ 2017-06-20 16:06 UTC (permalink / raw)
To: enadolski, linux-btrfs
It's been known for a while that the use of multiple lists
that are periodically merged was an algorithmic problem within
btrfs. There are several workloads that don't complete in any
reasonable amount of time (e.g. btrfs/130) and others that cause
soft lockups.
The solution is to use a pair of rbtrees that do insertion merging
for both indirect and direct refs, with the former converting
refs into the latter. The result is a btrfs/130 workload that
used to take several hours now takes about half of that. This
runtime still isn't acceptable and a future patch will address that
by moving the rbtrees higher in the stack so the lookups can be
shared across multiple calls to find_parent_nodes.
Signed-off-by: Edmund Nadolski <enadolski@suse.com>
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
fs/btrfs/backref.c | 415 ++++++++++++++++++++++++++++++++++-------------------
1 file changed, 267 insertions(+), 148 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 0d1e7cb..daae7b6 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -129,7 +129,7 @@ static int find_extent_in_eb(const struct extent_buffer *eb,
* this structure records all encountered refs on the way up to the root
*/
struct prelim_ref {
- struct list_head list;
+ struct rb_node rbnode;
u64 root_id;
struct btrfs_key key_for_search;
int level;
@@ -139,6 +139,17 @@ struct prelim_ref {
u64 wanted_disk_byte;
};
+struct preftree {
+ struct rb_root root;
+};
+
+#define PREFTREE_INIT { .root = RB_ROOT }
+
+struct preftrees {
+ struct preftree direct; /* BTRFS_SHARED_[DATA|BLOCK]_REF_KEY */
+ struct preftree indirect; /* BTRFS_[TREE_BLOCK|EXTENT_DATA]_REF_KEY */
+};
+
static struct kmem_cache *btrfs_prelim_ref_cache;
int __init btrfs_prelim_ref_init(void)
@@ -158,6 +169,108 @@ void btrfs_prelim_ref_exit(void)
kmem_cache_destroy(btrfs_prelim_ref_cache);
}
+static void release_pref(struct prelim_ref *ref)
+{
+ kmem_cache_free(btrfs_prelim_ref_cache, ref);
+}
+
+/*
+ * Return 0 when both refs are for the same block (and can be merged).
+ * A -1 return indicates ref1 is a 'lower' block than ref2, while 1
+ * indicates a 'higher' block.
+ */
+static int prelim_ref_compare(struct prelim_ref *ref1,
+ struct prelim_ref *ref2)
+{
+ if (ref1->level < ref2->level)
+ return -1;
+ if (ref1->level > ref2->level)
+ return 1;
+ if (ref1->root_id < ref2->root_id)
+ return -1;
+ if (ref1->root_id > ref2->root_id)
+ return 1;
+ if (ref1->key_for_search.type < ref2->key_for_search.type)
+ return -1;
+ if (ref1->key_for_search.type > ref2->key_for_search.type)
+ return 1;
+ if (ref1->key_for_search.objectid < ref2->key_for_search.objectid)
+ return -1;
+ if (ref1->key_for_search.objectid > ref2->key_for_search.objectid)
+ return 1;
+ if (ref1->key_for_search.offset < ref2->key_for_search.offset)
+ return -1;
+ if (ref1->key_for_search.offset > ref2->key_for_search.offset)
+ return 1;
+ if (ref1->parent < ref2->parent)
+ return -1;
+ if (ref1->parent > ref2->parent)
+ return 1;
+
+ return 0;
+}
+
+/*
+ * Add @newref to the @root rbtree, merging identical refs.
+ *
+ * Callers should assumed that newref has been freed after calling.
+ */
+static void prelim_ref_insert(struct preftree *preftree,
+ struct prelim_ref *newref)
+{
+ struct rb_root *root;
+ struct rb_node **p;
+ struct rb_node *parent = NULL;
+ struct prelim_ref *ref;
+ int result;
+
+ root = &preftree->root;
+ p = &root->rb_node;
+
+ while (*p) {
+ parent = *p;
+ ref = rb_entry(parent, struct prelim_ref, rbnode);
+ result = prelim_ref_compare(ref, newref);
+ if (result < 0) {
+ p = &(*p)->rb_left;
+ } else if (result > 0) {
+ p = &(*p)->rb_right;
+ } else {
+ /* Identical refs, merge them and free @newref */
+ struct extent_inode_elem *eie = ref->inode_list;
+
+ while (eie && eie->next)
+ eie = eie->next;
+
+ if (!eie)
+ ref->inode_list = newref->inode_list;
+ else
+ eie->next = newref->inode_list;
+ ref->count += newref->count;
+ release_pref(newref);
+ return;
+ }
+ }
+
+ rb_link_node(&newref->rbnode, parent, p);
+ rb_insert_color(&newref->rbnode, root);
+}
+
+/*
+ * Release the entire tree. We don't care about internal consistency so
+ * just free everything and then reset the tree root.
+ */
+static void prelim_release(struct preftree *preftree)
+{
+ struct prelim_ref *ref, *next_ref;
+
+ rbtree_postorder_for_each_entry_safe(ref, next_ref, &preftree->root,
+ rbnode)
+ release_pref(ref);
+
+ preftree->root = RB_ROOT;
+}
+
/*
* the rules for all callers of this function are:
* - obtaining the parent is the goal
@@ -196,7 +309,7 @@ void btrfs_prelim_ref_exit(void)
* additional information that's available but not required to find the parent
* block might help in merging entries to gain some speed.
*/
-static int add_prelim_ref(struct list_head *head, u64 root_id,
+static int add_prelim_ref(struct preftree *preftree, u64 root_id,
const struct btrfs_key *key, int level, u64 parent,
u64 wanted_disk_byte, int count, gfp_t gfp_mask)
{
@@ -243,11 +356,29 @@ static int add_prelim_ref(struct list_head *head, u64 root_id,
ref->count = count;
ref->parent = parent;
ref->wanted_disk_byte = wanted_disk_byte;
- list_add_tail(&ref->list, head);
+ prelim_ref_insert(preftree, ref);
return 0;
}
+/* direct refs use root == 0, key == NULL */
+static int add_direct_ref(struct preftrees *preftrees, int level, u64 parent,
+ u64 wanted_disk_byte, int count, gfp_t gfp_mask)
+{
+ return add_prelim_ref(&preftrees->direct, 0, NULL, level, parent,
+ wanted_disk_byte, count, gfp_mask);
+}
+
+/* indirect refs use parent == 0 */
+static int add_indirect_ref(struct preftrees *preftrees, u64 root_id,
+ const struct btrfs_key *key, int level,
+ u64 wanted_disk_byte, int count, gfp_t gfp_mask)
+{
+ return add_prelim_ref(&preftrees->indirect, root_id, key, level, 0,
+ wanted_disk_byte, count, gfp_mask);
+}
+
+
static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
struct ulist *parents, struct prelim_ref *ref,
int level, u64 time_seq, const u64 *extent_item_pos,
@@ -429,38 +560,58 @@ unode_aux_to_inode_list(struct ulist_node *node)
}
/*
- * resolve all indirect backrefs from the list
+ * We maintain two separate rbtrees: one for indirect refs and one for
+ * direct refs. Each tree does merge on insertion. Once all of the
+ * refs have been located, we iterate over the indirect ref tree, resolve
+ * each reference and remove it from the indirect tree, and then insert
+ * the resolved reference into the direct tree, merging there too.
+ *
+ * New backrefs (i.e., for parent nodes) are added to the direct/indirect
+ * rbtrees as they are encountered. The new, indirect backrefs are
+ * resolved as above.
*/
static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
struct btrfs_path *path, u64 time_seq,
- struct list_head *head,
+ struct preftrees *preftrees,
const u64 *extent_item_pos, u64 total_refs,
u64 root_objectid)
{
int err;
int ret = 0;
- struct prelim_ref *ref;
- struct prelim_ref *ref_safe;
- struct prelim_ref *new_ref;
struct ulist *parents;
struct ulist_node *node;
struct ulist_iterator uiter;
+ struct rb_node *rnode;
parents = ulist_alloc(GFP_NOFS);
if (!parents)
return -ENOMEM;
/*
- * _safe allows us to insert directly after the current item without
- * iterating over the newly inserted items.
- * we're also allowed to re-assign ref during iteration.
+ * We could trade memory usage for performance here by iterating
+ * the tree, allocating new refs for each insertion, and then
+ * freeing the entire indirect tree when we're done. In some test
+ * cases, the tree can grow quite large (~200k objects).
*/
- list_for_each_entry_safe(ref, ref_safe, head, list) {
- if (ref->parent) /* already direct */
- continue;
- if (ref->count == 0)
+ while ((rnode = rb_first(&preftrees->indirect.root))) {
+ struct prelim_ref *ref;
+
+ ref = rb_entry(rnode, struct prelim_ref, rbnode);
+ if (WARN(ref->parent,
+ "BUG: direct ref found in indirect tree")) {
+ ret = -EINVAL;
+ goto out;
+ }
+
+ rb_erase(&ref->rbnode, &preftrees->indirect.root);
+
+ if (ref->count == 0) {
+ release_pref(ref);
continue;
+ }
+
if (root_objectid && ref->root_id != root_objectid) {
+ release_pref(ref);
ret = BACKREF_FOUND_SHARED;
goto out;
}
@@ -472,8 +623,11 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
* and return directly.
*/
if (err == -ENOENT) {
+ /* This only happens when we're doing sanity testing */
+ release_pref(ref);
continue;
} else if (err) {
+ release_pref(ref);
ret = err;
goto out;
}
@@ -484,19 +638,26 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
ref->parent = node ? node->val : 0;
ref->inode_list = unode_aux_to_inode_list(node);
- /* additional parents require new refs being added here */
+ /* Add a prelim_ref(s) for any other parent(s). */
while ((node = ulist_next(parents, &uiter))) {
+ struct prelim_ref *new_ref;
+
new_ref = kmem_cache_alloc(btrfs_prelim_ref_cache,
GFP_NOFS);
if (!new_ref) {
+ release_pref(ref);
ret = -ENOMEM;
goto out;
}
memcpy(new_ref, ref, sizeof(*ref));
new_ref->parent = node->val;
new_ref->inode_list = unode_aux_to_inode_list(node);
- list_add(&new_ref->list, &ref->list);
+ prelim_ref_insert(&preftrees->direct, new_ref);
}
+
+ /* Now it's a direct ref, put it in the the direct tree */
+ prelim_ref_insert(&preftrees->direct, ref);
+
ulist_reinit(parents);
}
out:
@@ -504,37 +665,22 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
return ret;
}
-static inline int ref_for_same_block(struct prelim_ref *ref1,
- struct prelim_ref *ref2)
-{
- if (ref1->level != ref2->level)
- return 0;
- if (ref1->root_id != ref2->root_id)
- return 0;
- if (ref1->key_for_search.type != ref2->key_for_search.type)
- return 0;
- if (ref1->key_for_search.objectid != ref2->key_for_search.objectid)
- return 0;
- if (ref1->key_for_search.offset != ref2->key_for_search.offset)
- return 0;
- if (ref1->parent != ref2->parent)
- return 0;
-
- return 1;
-}
-
/*
* read tree blocks and add keys where required.
*/
static int add_missing_keys(struct btrfs_fs_info *fs_info,
- struct list_head *head)
+ struct preftrees *preftrees)
{
struct prelim_ref *ref;
struct extent_buffer *eb;
+ struct rb_node *node = rb_first(&preftrees->indirect.root);
+
+ while (node) {
+ ref = rb_entry(node, struct prelim_ref, rbnode);
+ node = rb_next(&ref->rbnode);
+ if (WARN(ref->parent, "BUG: direct ref found in indirect tree"))
+ return -EINVAL;
- list_for_each_entry(ref, head, list) {
- if (ref->parent)
- continue;
if (ref->key_for_search.type)
continue;
BUG_ON(!ref->wanted_disk_byte);
@@ -557,57 +703,11 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info,
}
/*
- * merge backrefs and adjust counts accordingly
- *
- * FIXME: For MERGE_IDENTICAL_KEYS, if we add more keys in add_prelim_ref
- * then we can merge more here. Additionally, we could even add a key
- * range for the blocks we looked into to merge even more (-> replace
- * unresolved refs by those having a parent).
- */
-static void merge_refs(struct list_head *head, enum merge_mode mode)
-{
- struct prelim_ref *pos1;
-
- list_for_each_entry(pos1, head, list) {
- struct prelim_ref *pos2 = pos1, *tmp;
-
- list_for_each_entry_safe_continue(pos2, tmp, head, list) {
- struct prelim_ref *ref1 = pos1, *ref2 = pos2;
- struct extent_inode_elem *eie;
-
- if (!ref_for_same_block(ref1, ref2))
- continue;
- if (mode == MERGE_IDENTICAL_KEYS) {
- if (!ref1->parent && ref2->parent)
- swap(ref1, ref2);
- } else {
- if (ref1->parent != ref2->parent)
- continue;
- }
-
- eie = ref1->inode_list;
- while (eie && eie->next)
- eie = eie->next;
- if (eie)
- eie->next = ref2->inode_list;
- else
- ref1->inode_list = ref2->inode_list;
- ref1->count += ref2->count;
-
- list_del(&ref2->list);
- kmem_cache_free(btrfs_prelim_ref_cache, ref2);
- cond_resched();
- }
-
- }
-}
-
-/*
* add all currently queued delayed refs from this head whose seq nr is
* smaller or equal that seq to the list
*/
static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
- struct list_head *prefs, u64 *total_refs,
+ struct preftrees *preftrees, u64 *total_refs,
u64 inum)
{
struct btrfs_delayed_ref_node *node;
@@ -642,24 +742,30 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
*total_refs += (node->ref_mod * sgn);
switch (node->type) {
case BTRFS_TREE_BLOCK_REF_KEY: {
+ /* NORMAL INDIRECT METADATA backref */
struct btrfs_delayed_tree_ref *ref;
ref = btrfs_delayed_node_to_tree_ref(node);
- ret = add_prelim_ref(prefs, ref->root, &op_key,
- ref->level + 1, 0, node->bytenr,
- node->ref_mod * sgn, GFP_ATOMIC);
+ ret = add_indirect_ref(preftrees, ref->root, &op_key,
+ ref->level + 1, node->bytenr,
+ node->ref_mod * sgn,
+ GFP_ATOMIC);
break;
}
case BTRFS_SHARED_BLOCK_REF_KEY: {
+ /* SHARED DIRECT METADATA backref */
struct btrfs_delayed_tree_ref *ref;
ref = btrfs_delayed_node_to_tree_ref(node);
- ret = add_prelim_ref(prefs, 0, NULL, ref->level + 1,
+
+ ret = add_direct_ref(preftrees, ref->level + 1,
ref->parent, node->bytenr,
- node->ref_mod * sgn, GFP_ATOMIC);
+ node->ref_mod * sgn,
+ GFP_ATOMIC);
break;
}
case BTRFS_EXTENT_DATA_REF_KEY: {
+ /* NORMAL INDIRECT DATA backref */
struct btrfs_delayed_data_ref *ref;
ref = btrfs_delayed_node_to_data_ref(node);
@@ -676,17 +782,21 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
break;
}
- ret = add_prelim_ref(prefs, ref->root, &key, 0, 0,
- node->bytenr, node->ref_mod * sgn,
- GFP_ATOMIC);
+ ret = add_indirect_ref(preftrees, ref->root, &key, 0,
+ node->bytenr,
+ node->ref_mod * sgn,
+ GFP_ATOMIC);
break;
}
case BTRFS_SHARED_DATA_REF_KEY: {
+ /* SHARED DIRECT FULL backref */
struct btrfs_delayed_data_ref *ref;
ref = btrfs_delayed_node_to_data_ref(node);
- ret = add_prelim_ref(prefs, 0, NULL, 0, ref->parent,
- node->bytenr, node->ref_mod * sgn,
+
+ ret = add_direct_ref(preftrees, 0, ref->parent,
+ node->bytenr,
+ node->ref_mod * sgn,
GFP_ATOMIC);
break;
}
@@ -704,7 +814,7 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
* add all inline backrefs for bytenr to the list
*/
static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
- int *info_level, struct list_head *prefs,
+ int *info_level, struct preftrees *preftrees,
u64 *total_refs, u64 inum)
{
int ret = 0;
@@ -760,8 +870,8 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
switch (type) {
case BTRFS_SHARED_BLOCK_REF_KEY:
- ret = add_prelim_ref(prefs, 0, NULL, *info_level + 1,
- offset, bytenr, 1, GFP_NOFS);
+ ret = add_direct_ref(preftrees, *info_level + 1, offset,
+ bytenr, 1, GFP_NOFS);
break;
case BTRFS_SHARED_DATA_REF_KEY: {
struct btrfs_shared_data_ref *sdref;
@@ -769,14 +879,15 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
sdref = (struct btrfs_shared_data_ref *)(iref + 1);
count = btrfs_shared_data_ref_count(leaf, sdref);
- ret = add_prelim_ref(prefs, 0, NULL, 0, offset,
+
+ ret = add_direct_ref(preftrees, 0, offset,
bytenr, count, GFP_NOFS);
break;
}
case BTRFS_TREE_BLOCK_REF_KEY:
- ret = add_prelim_ref(prefs, offset, NULL,
- *info_level + 1, 0,
- bytenr, 1, GFP_NOFS);
+ ret = add_indirect_ref(preftrees, offset, NULL,
+ *info_level + 1, bytenr, 1,
+ GFP_NOFS);
break;
case BTRFS_EXTENT_DATA_REF_KEY: {
struct btrfs_extent_data_ref *dref;
@@ -796,8 +907,9 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
}
root = btrfs_extent_data_ref_root(leaf, dref);
- ret = add_prelim_ref(prefs, root, &key, 0, 0,
- bytenr, count, GFP_NOFS);
+
+ ret = add_indirect_ref(preftrees, root, &key, 0, bytenr,
+ count, GFP_NOFS);
break;
}
default:
@@ -816,7 +928,8 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
*/
static int add_keyed_refs(struct btrfs_fs_info *fs_info,
struct btrfs_path *path, u64 bytenr,
- int info_level, struct list_head *prefs, u64 inum)
+ int info_level, struct preftrees *preftrees,
+ u64 inum)
{
struct btrfs_root *extent_root = fs_info->extent_root;
int ret;
@@ -846,26 +959,31 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
switch (key.type) {
case BTRFS_SHARED_BLOCK_REF_KEY:
- ret = add_prelim_ref(prefs, 0, NULL, info_level + 1,
- key.offset, bytenr, 1, GFP_NOFS);
+ /* SHARED DIRECT METADATA backref */
+ ret = add_direct_ref(preftrees, info_level + 1,
+ key.offset, bytenr, 1,
+ GFP_NOFS);
break;
case BTRFS_SHARED_DATA_REF_KEY: {
+ /* SHARED DIRECT FULL backref */
struct btrfs_shared_data_ref *sdref;
int count;
sdref = btrfs_item_ptr(leaf, slot,
struct btrfs_shared_data_ref);
count = btrfs_shared_data_ref_count(leaf, sdref);
- ret = add_prelim_ref(prefs, 0, NULL, 0, key.offset,
- bytenr, count, GFP_NOFS);
+ ret = add_direct_ref(preftrees, 0, key.offset, bytenr,
+ count, GFP_NOFS);
break;
}
case BTRFS_TREE_BLOCK_REF_KEY:
- ret = add_prelim_ref(prefs, key.offset, NULL,
- info_level + 1, 0,
- bytenr, 1, GFP_NOFS);
+ /* NORMAL INDIRECT METADATA backref */
+ ret = add_indirect_ref(preftrees, key.offset, NULL,
+ info_level + 1, bytenr, 1,
+ GFP_NOFS);
break;
case BTRFS_EXTENT_DATA_REF_KEY: {
+ /* NORMAL INDIRECT DATA backref */
struct btrfs_extent_data_ref *dref;
int count;
u64 root;
@@ -884,8 +1002,8 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
}
root = btrfs_extent_data_ref_root(leaf, dref);
- ret = add_prelim_ref(prefs, root, &key, 0, 0,
- bytenr, count, GFP_NOFS);
+ ret = add_indirect_ref(preftrees, root, &key, 0, bytenr,
+ count, GFP_NOFS);
break;
}
default:
@@ -926,14 +1044,15 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
struct btrfs_delayed_ref_head *head;
int info_level = 0;
int ret;
- struct list_head prefs_delayed;
- struct list_head prefs;
struct prelim_ref *ref;
+ struct rb_node *node;
struct extent_inode_elem *eie = NULL;
+ /* total of both direct AND indirect refs! */
u64 total_refs = 0;
-
- INIT_LIST_HEAD(&prefs);
- INIT_LIST_HEAD(&prefs_delayed);
+ struct preftrees preftrees = {
+ .direct = PREFTREE_INIT,
+ .indirect = PREFTREE_INIT
+ };
key.objectid = bytenr;
key.offset = (u64)-1;
@@ -996,15 +1115,18 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
goto again;
}
spin_unlock(&delayed_refs->lock);
- ret = add_delayed_refs(head, time_seq,
- &prefs_delayed, &total_refs,
- inum);
+ ret = add_delayed_refs(head, time_seq, &preftrees,
+ &total_refs, inum);
mutex_unlock(&head->mutex);
if (ret)
goto out;
} else {
spin_unlock(&delayed_refs->lock);
}
+
+ /*
+ * TODO - implement short circuit for BACKREF_FOUND_SHARED
+ */
}
if (path->slots[0]) {
@@ -1019,35 +1141,41 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
(key.type == BTRFS_EXTENT_ITEM_KEY ||
key.type == BTRFS_METADATA_ITEM_KEY)) {
ret = add_inline_refs(path, bytenr, &info_level,
- &prefs, &total_refs, inum);
+ &preftrees, &total_refs, inum);
if (ret)
goto out;
ret = add_keyed_refs(fs_info, path, bytenr, info_level,
- &prefs, inum);
+ &preftrees, inum);
if (ret)
goto out;
}
}
- btrfs_release_path(path);
- list_splice_init(&prefs_delayed, &prefs);
+ btrfs_release_path(path);
- ret = add_missing_keys(fs_info, &prefs);
+ ret = add_missing_keys(fs_info, &preftrees);
if (ret)
goto out;
- merge_refs(&prefs, MERGE_IDENTICAL_KEYS);
-
- ret = resolve_indirect_refs(fs_info, path, time_seq, &prefs,
+ ret = resolve_indirect_refs(fs_info, path, time_seq, &preftrees,
extent_item_pos, total_refs,
root_objectid);
if (ret)
goto out;
- merge_refs(&prefs, MERGE_IDENTICAL_PARENTS);
+ WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect.root));
- while (!list_empty(&prefs)) {
- ref = list_first_entry(&prefs, struct prelim_ref, list);
+ /*
+ * This walks the tree of merged and resolved refs. Tree blocks are
+ * read in as needed. Unique entries are added to the ulist, and
+ * the list of found roots is updated.
+ *
+ * We release the entire tree in one go before returning.
+ */
+ node = rb_first(&preftrees.direct.root);
+ while (node) {
+ ref = rb_entry(node, struct prelim_ref, rbnode);
+ node = rb_next(&ref->rbnode);
WARN_ON(ref->count < 0);
if (roots && ref->count && ref->root_id && ref->parent == 0) {
if (root_objectid && ref->root_id != root_objectid) {
@@ -1101,23 +1229,14 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
}
eie = NULL;
}
- list_del(&ref->list);
- kmem_cache_free(btrfs_prelim_ref_cache, ref);
}
out:
btrfs_free_path(path);
- while (!list_empty(&prefs)) {
- ref = list_first_entry(&prefs, struct prelim_ref, list);
- list_del(&ref->list);
- kmem_cache_free(btrfs_prelim_ref_cache, ref);
- }
- while (!list_empty(&prefs_delayed)) {
- ref = list_first_entry(&prefs_delayed, struct prelim_ref,
- list);
- list_del(&ref->list);
- kmem_cache_free(btrfs_prelim_ref_cache, ref);
- }
+
+ prelim_release(&preftrees.direct);
+ prelim_release(&preftrees.indirect);
+
if (ret < 0)
free_inode_elem_list(eie);
return ret;
--
2.10.2
^ permalink raw reply related [flat|nested] 23+ messages in thread
* [PATCH 09/13] btrfs: add a node counter to each of the rbtrees
2017-06-20 16:06 [PATCH 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (7 preceding siblings ...)
2017-06-20 16:06 ` [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees Edmund Nadolski
@ 2017-06-20 16:06 ` Edmund Nadolski
2017-06-20 16:06 ` [PATCH 10/13] btrfs: backref, add tracepoints for prelim_ref insertion and merging Edmund Nadolski
` (4 subsequent siblings)
13 siblings, 0 replies; 23+ messages in thread
From: Edmund Nadolski @ 2017-06-20 16:06 UTC (permalink / raw)
To: enadolski, linux-btrfs
From: Jeff Mahoney <jeffm@suse.com>
This patch adds counters to each of the rbtrees so that we can tell
how large they are growing for a given workload. These counters
will be exported by tracepoints in the next patch.
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
fs/btrfs/backref.c | 6 +++++-
1 file changed, 5 insertions(+), 1 deletion(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index daae7b6..4018393 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -141,9 +141,10 @@ struct prelim_ref {
struct preftree {
struct rb_root root;
+ unsigned int count;
};
-#define PREFTREE_INIT { .root = RB_ROOT }
+#define PREFTREE_INIT { .root = RB_ROOT, .count = 0 }
struct preftrees {
struct preftree direct; /* BTRFS_SHARED_[DATA|BLOCK]_REF_KEY */
@@ -252,6 +253,7 @@ static void prelim_ref_insert(struct preftree *preftree,
}
}
+ preftree->count++;
rb_link_node(&newref->rbnode, parent, p);
rb_insert_color(&newref->rbnode, root);
}
@@ -269,6 +271,7 @@ static void prelim_release(struct preftree *preftree)
release_pref(ref);
preftree->root = RB_ROOT;
+ preftree->count = 0;
}
/*
@@ -604,6 +607,7 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
}
rb_erase(&ref->rbnode, &preftrees->indirect.root);
+ preftrees->indirect.count--;
if (ref->count == 0) {
release_pref(ref);
--
2.10.2
^ permalink raw reply related [flat|nested] 23+ messages in thread
* [PATCH 10/13] btrfs: backref, add tracepoints for prelim_ref insertion and merging
2017-06-20 16:06 [PATCH 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (8 preceding siblings ...)
2017-06-20 16:06 ` [PATCH 09/13] btrfs: add a node counter to each of the rbtrees Edmund Nadolski
@ 2017-06-20 16:06 ` Edmund Nadolski
2017-06-20 16:06 ` [PATCH 11/13] btrfs: add cond_resched() calls when resolving backrefs Edmund Nadolski
` (3 subsequent siblings)
13 siblings, 0 replies; 23+ messages in thread
From: Edmund Nadolski @ 2017-06-20 16:06 UTC (permalink / raw)
To: enadolski, linux-btrfs
From: Jeff Mahoney <jeffm@suse.com>
This patch adds a tracepoint event for prelim_ref insertion and
merging. For each, the ref being inserted or merged and the count
of tree nodes is issued.
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
fs/btrfs/backref.c | 117 ++++++++++++++++++++++---------------------
fs/btrfs/backref.h | 12 +++++
fs/btrfs/super.c | 1 +
include/trace/events/btrfs.h | 58 +++++++++++++++++++++
4 files changed, 131 insertions(+), 57 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 4018393..0dffd7e 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -26,6 +26,8 @@
#include "delayed-ref.h"
#include "locking.h"
+#include <trace/events/btrfs.h>
+
enum merge_mode {
MERGE_IDENTICAL_KEYS = 1,
MERGE_IDENTICAL_PARENTS,
@@ -125,20 +127,6 @@ static int find_extent_in_eb(const struct extent_buffer *eb,
return 0;
}
-/*
- * this structure records all encountered refs on the way up to the root
- */
-struct prelim_ref {
- struct rb_node rbnode;
- u64 root_id;
- struct btrfs_key key_for_search;
- int level;
- int count;
- struct extent_inode_elem *inode_list;
- u64 parent;
- u64 wanted_disk_byte;
-};
-
struct preftree {
struct rb_root root;
unsigned int count;
@@ -216,7 +204,8 @@ static int prelim_ref_compare(struct prelim_ref *ref1,
*
* Callers should assumed that newref has been freed after calling.
*/
-static void prelim_ref_insert(struct preftree *preftree,
+static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,
+ struct preftree *preftree,
struct prelim_ref *newref)
{
struct rb_root *root;
@@ -247,6 +236,8 @@ static void prelim_ref_insert(struct preftree *preftree,
ref->inode_list = newref->inode_list;
else
eie->next = newref->inode_list;
+ trace_btrfs_prelim_ref_merge(fs_info, ref, newref,
+ preftree->count);
ref->count += newref->count;
release_pref(newref);
return;
@@ -254,6 +245,7 @@ static void prelim_ref_insert(struct preftree *preftree,
}
preftree->count++;
+ trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count);
rb_link_node(&newref->rbnode, parent, p);
rb_insert_color(&newref->rbnode, root);
}
@@ -312,7 +304,8 @@ static void prelim_release(struct preftree *preftree)
* additional information that's available but not required to find the parent
* block might help in merging entries to gain some speed.
*/
-static int add_prelim_ref(struct preftree *preftree, u64 root_id,
+static int add_prelim_ref(const struct btrfs_fs_info *fs_info,
+ struct preftree *preftree, u64 root_id,
const struct btrfs_key *key, int level, u64 parent,
u64 wanted_disk_byte, int count, gfp_t gfp_mask)
{
@@ -359,26 +352,28 @@ static int add_prelim_ref(struct preftree *preftree, u64 root_id,
ref->count = count;
ref->parent = parent;
ref->wanted_disk_byte = wanted_disk_byte;
- prelim_ref_insert(preftree, ref);
+ prelim_ref_insert(fs_info, preftree, ref);
return 0;
}
/* direct refs use root == 0, key == NULL */
-static int add_direct_ref(struct preftrees *preftrees, int level, u64 parent,
+static int add_direct_ref(const struct btrfs_fs_info *fs_info,
+ struct preftrees *preftrees, int level, u64 parent,
u64 wanted_disk_byte, int count, gfp_t gfp_mask)
{
- return add_prelim_ref(&preftrees->direct, 0, NULL, level, parent,
- wanted_disk_byte, count, gfp_mask);
+ return add_prelim_ref(fs_info, &preftrees->direct, 0, NULL, level,
+ parent, wanted_disk_byte, count, gfp_mask);
}
/* indirect refs use parent == 0 */
-static int add_indirect_ref(struct preftrees *preftrees, u64 root_id,
+static int add_indirect_ref(const struct btrfs_fs_info *fs_info,
+ struct preftrees *preftrees, u64 root_id,
const struct btrfs_key *key, int level,
u64 wanted_disk_byte, int count, gfp_t gfp_mask)
{
- return add_prelim_ref(&preftrees->indirect, root_id, key, level, 0,
- wanted_disk_byte, count, gfp_mask);
+ return add_prelim_ref(fs_info, &preftrees->indirect, root_id, key,
+ level, 0, wanted_disk_byte, count, gfp_mask);
}
@@ -656,11 +651,11 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
memcpy(new_ref, ref, sizeof(*ref));
new_ref->parent = node->val;
new_ref->inode_list = unode_aux_to_inode_list(node);
- prelim_ref_insert(&preftrees->direct, new_ref);
+ prelim_ref_insert(fs_info, &preftrees->direct, new_ref);
}
/* Now it's a direct ref, put it in the the direct tree */
- prelim_ref_insert(&preftrees->direct, ref);
+ prelim_ref_insert(fs_info, &preftrees->direct, ref);
ulist_reinit(parents);
}
@@ -710,7 +705,8 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info,
* add all currently queued delayed refs from this head whose seq nr is
* smaller or equal that seq to the list
*/
-static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
+static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
+ struct btrfs_delayed_ref_head *head, u64 seq,
struct preftrees *preftrees, u64 *total_refs,
u64 inum)
{
@@ -750,8 +746,9 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
struct btrfs_delayed_tree_ref *ref;
ref = btrfs_delayed_node_to_tree_ref(node);
- ret = add_indirect_ref(preftrees, ref->root, &op_key,
- ref->level + 1, node->bytenr,
+ ret = add_indirect_ref(fs_info, preftrees, ref->root,
+ &op_key, ref->level + 1,
+ node->bytenr,
node->ref_mod * sgn,
GFP_ATOMIC);
break;
@@ -762,9 +759,9 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
ref = btrfs_delayed_node_to_tree_ref(node);
- ret = add_direct_ref(preftrees, ref->level + 1,
- ref->parent, node->bytenr,
- node->ref_mod * sgn,
+ ret = add_direct_ref(fs_info, preftrees,
+ ref->level + 1, ref->parent,
+ node->bytenr, node->ref_mod * sgn,
GFP_ATOMIC);
break;
}
@@ -786,8 +783,8 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
break;
}
- ret = add_indirect_ref(preftrees, ref->root, &key, 0,
- node->bytenr,
+ ret = add_indirect_ref(fs_info, preftrees, ref->root,
+ &key, 0, node->bytenr,
node->ref_mod * sgn,
GFP_ATOMIC);
break;
@@ -798,8 +795,8 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
ref = btrfs_delayed_node_to_data_ref(node);
- ret = add_direct_ref(preftrees, 0, ref->parent,
- node->bytenr,
+ ret = add_direct_ref(fs_info, preftrees, 0,
+ ref->parent, node->bytenr,
node->ref_mod * sgn,
GFP_ATOMIC);
break;
@@ -817,7 +814,8 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
/*
* add all inline backrefs for bytenr to the list
*/
-static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
+static int add_inline_refs(const struct btrfs_fs_info *fs_info,
+ struct btrfs_path *path, u64 bytenr,
int *info_level, struct preftrees *preftrees,
u64 *total_refs, u64 inum)
{
@@ -874,7 +872,8 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
switch (type) {
case BTRFS_SHARED_BLOCK_REF_KEY:
- ret = add_direct_ref(preftrees, *info_level + 1, offset,
+ ret = add_direct_ref(fs_info, preftrees,
+ *info_level + 1, offset,
bytenr, 1, GFP_NOFS);
break;
case BTRFS_SHARED_DATA_REF_KEY: {
@@ -884,14 +883,14 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
sdref = (struct btrfs_shared_data_ref *)(iref + 1);
count = btrfs_shared_data_ref_count(leaf, sdref);
- ret = add_direct_ref(preftrees, 0, offset,
+ ret = add_direct_ref(fs_info, preftrees, 0, offset,
bytenr, count, GFP_NOFS);
break;
}
case BTRFS_TREE_BLOCK_REF_KEY:
- ret = add_indirect_ref(preftrees, offset, NULL,
- *info_level + 1, bytenr, 1,
- GFP_NOFS);
+ ret = add_indirect_ref(fs_info, preftrees, offset,
+ NULL, *info_level + 1,
+ bytenr, 1, GFP_NOFS);
break;
case BTRFS_EXTENT_DATA_REF_KEY: {
struct btrfs_extent_data_ref *dref;
@@ -912,8 +911,9 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
root = btrfs_extent_data_ref_root(leaf, dref);
- ret = add_indirect_ref(preftrees, root, &key, 0, bytenr,
- count, GFP_NOFS);
+ ret = add_indirect_ref(fs_info, preftrees, root,
+ &key, 0, bytenr, count,
+ GFP_NOFS);
break;
}
default:
@@ -964,9 +964,9 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
switch (key.type) {
case BTRFS_SHARED_BLOCK_REF_KEY:
/* SHARED DIRECT METADATA backref */
- ret = add_direct_ref(preftrees, info_level + 1,
- key.offset, bytenr, 1,
- GFP_NOFS);
+ ret = add_direct_ref(fs_info, preftrees,
+ info_level + 1, key.offset,
+ bytenr, 1, GFP_NOFS);
break;
case BTRFS_SHARED_DATA_REF_KEY: {
/* SHARED DIRECT FULL backref */
@@ -976,15 +976,16 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
sdref = btrfs_item_ptr(leaf, slot,
struct btrfs_shared_data_ref);
count = btrfs_shared_data_ref_count(leaf, sdref);
- ret = add_direct_ref(preftrees, 0, key.offset, bytenr,
- count, GFP_NOFS);
+ ret = add_direct_ref(fs_info, preftrees, 0,
+ key.offset, bytenr, count,
+ GFP_NOFS);
break;
}
case BTRFS_TREE_BLOCK_REF_KEY:
/* NORMAL INDIRECT METADATA backref */
- ret = add_indirect_ref(preftrees, key.offset, NULL,
- info_level + 1, bytenr, 1,
- GFP_NOFS);
+ ret = add_indirect_ref(fs_info, preftrees, key.offset,
+ NULL, info_level + 1, bytenr,
+ 1, GFP_NOFS);
break;
case BTRFS_EXTENT_DATA_REF_KEY: {
/* NORMAL INDIRECT DATA backref */
@@ -1006,8 +1007,9 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
}
root = btrfs_extent_data_ref_root(leaf, dref);
- ret = add_indirect_ref(preftrees, root, &key, 0, bytenr,
- count, GFP_NOFS);
+ ret = add_indirect_ref(fs_info, preftrees, root,
+ &key, 0, bytenr, count,
+ GFP_NOFS);
break;
}
default:
@@ -1119,8 +1121,8 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
goto again;
}
spin_unlock(&delayed_refs->lock);
- ret = add_delayed_refs(head, time_seq, &preftrees,
- &total_refs, inum);
+ ret = add_delayed_refs(fs_info, head, time_seq,
+ &preftrees, &total_refs, inum);
mutex_unlock(&head->mutex);
if (ret)
goto out;
@@ -1144,8 +1146,9 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
if (key.objectid == bytenr &&
(key.type == BTRFS_EXTENT_ITEM_KEY ||
key.type == BTRFS_METADATA_ITEM_KEY)) {
- ret = add_inline_refs(path, bytenr, &info_level,
- &preftrees, &total_refs, inum);
+ ret = add_inline_refs(fs_info, path, bytenr,
+ &info_level, &preftrees,
+ &total_refs, inum);
if (ret)
goto out;
ret = add_keyed_refs(fs_info, path, bytenr, info_level,
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index f9428aa..e410335 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -72,4 +72,16 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr);
int __init btrfs_prelim_ref_init(void);
void btrfs_prelim_ref_exit(void);
+
+struct prelim_ref {
+ struct rb_node rbnode;
+ u64 root_id;
+ struct btrfs_key key_for_search;
+ int level;
+ int count;
+ struct extent_inode_elem *inode_list;
+ u64 parent;
+ u64 wanted_disk_byte;
+};
+
#endif
diff --git a/fs/btrfs/super.c b/fs/btrfs/super.c
index 3371213..66e7ed1 100644
--- a/fs/btrfs/super.c
+++ b/fs/btrfs/super.c
@@ -61,6 +61,7 @@
#include "tests/btrfs-tests.h"
#include "qgroup.h"
+#include "backref.h"
#define CREATE_TRACE_POINTS
#include <trace/events/btrfs.h>
diff --git a/include/trace/events/btrfs.h b/include/trace/events/btrfs.h
index 42560fe..1da36b0 100644
--- a/include/trace/events/btrfs.h
+++ b/include/trace/events/btrfs.h
@@ -26,6 +26,7 @@ struct btrfs_work;
struct __btrfs_workqueue;
struct btrfs_qgroup_extent_record;
struct btrfs_qgroup;
+struct prelim_ref;
#define show_ref_type(type) \
__print_symbolic(type, \
@@ -1636,6 +1637,63 @@ TRACE_EVENT(qgroup_meta_reserve,
show_root_type(__entry->refroot), __entry->diff)
);
+DECLARE_EVENT_CLASS(btrfs__prelim_ref,
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct prelim_ref *oldref,
+ const struct prelim_ref *newref, u64 tree_size),
+ TP_ARGS(fs_info, newref, oldref, tree_size),
+
+ TP_STRUCT__entry_btrfs(
+ __field( u64, root_id )
+ __field( u64, objectid )
+ __field( u8, type )
+ __field( u64, offset )
+ __field( int, level )
+ __field( int, old_count )
+ __field( u64, parent )
+ __field( u64, bytenr )
+ __field( int, mod_count )
+ __field( u64, tree_size )
+ ),
+
+ TP_fast_assign_btrfs(fs_info,
+ __entry->root_id = oldref->root_id;
+ __entry->objectid = oldref->key_for_search.objectid;
+ __entry->type = oldref->key_for_search.type;
+ __entry->offset = oldref->key_for_search.offset;
+ __entry->level = oldref->level;
+ __entry->old_count = oldref->count;
+ __entry->parent = oldref->parent;
+ __entry->bytenr = oldref->wanted_disk_byte;
+ __entry->mod_count = newref ? newref->count : 0;
+ __entry->tree_size = tree_size;
+ ),
+
+ TP_printk_btrfs("root=%llu, key=[%llu, %u, %llu], level=%d, count=[%d+%d=%d], parent=%llu, wanted_disk_byte=%llu, nodes=%llu",
+ (unsigned long long)__entry->root_id,
+ (unsigned long long)__entry->objectid, __entry->type,
+ (unsigned long long)__entry->offset, __entry->level,
+ __entry->old_count, __entry->mod_count,
+ __entry->old_count + __entry->mod_count,
+ (unsigned long long)__entry->parent,
+ (unsigned long long)__entry->bytenr,
+ (unsigned long long)__entry->tree_size)
+);
+
+DEFINE_EVENT(btrfs__prelim_ref, btrfs_prelim_ref_merge,
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct prelim_ref *oldref,
+ const struct prelim_ref *newref, u64 tree_size),
+ TP_ARGS(fs_info, oldref, newref, tree_size)
+);
+
+DEFINE_EVENT(btrfs__prelim_ref, btrfs_prelim_ref_insert,
+ TP_PROTO(const struct btrfs_fs_info *fs_info,
+ const struct prelim_ref *oldref,
+ const struct prelim_ref *newref, u64 tree_size),
+ TP_ARGS(fs_info, oldref, newref, tree_size)
+);
+
#endif /* _TRACE_BTRFS_H */
/* This part must be outside protection */
--
2.10.2
^ permalink raw reply related [flat|nested] 23+ messages in thread
* [PATCH 11/13] btrfs: add cond_resched() calls when resolving backrefs
2017-06-20 16:06 [PATCH 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (9 preceding siblings ...)
2017-06-20 16:06 ` [PATCH 10/13] btrfs: backref, add tracepoints for prelim_ref insertion and merging Edmund Nadolski
@ 2017-06-20 16:06 ` Edmund Nadolski
2017-06-20 16:06 ` [PATCH 12/13] btrfs: allow backref search checks for shared extents Edmund Nadolski
` (2 subsequent siblings)
13 siblings, 0 replies; 23+ messages in thread
From: Edmund Nadolski @ 2017-06-20 16:06 UTC (permalink / raw)
To: enadolski, linux-btrfs
Since backref resolution is CPU-intensive, the cond_resched calls
should help alleviate soft lockup occurences.
Signed-off-by: Edmund Nadolski <enadolski@suse.com>
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
fs/btrfs/backref.c | 3 +++
1 file changed, 3 insertions(+)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 0dffd7e..e95049a 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -658,6 +658,7 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
prelim_ref_insert(fs_info, &preftrees->direct, ref);
ulist_reinit(parents);
+ cond_resched();
}
out:
ulist_free(parents);
@@ -697,6 +698,7 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info,
btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0);
btrfs_tree_read_unlock(eb);
free_extent_buffer(eb);
+ cond_resched();
}
return 0;
}
@@ -1236,6 +1238,7 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
}
eie = NULL;
}
+ cond_resched();
}
out:
--
2.10.2
^ permalink raw reply related [flat|nested] 23+ messages in thread
* [PATCH 12/13] btrfs: allow backref search checks for shared extents
2017-06-20 16:06 [PATCH 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (10 preceding siblings ...)
2017-06-20 16:06 ` [PATCH 11/13] btrfs: add cond_resched() calls when resolving backrefs Edmund Nadolski
@ 2017-06-20 16:06 ` Edmund Nadolski
2017-06-20 16:06 ` [PATCH 13/13] btrfs: clean up extraneous computations in add_delayed_refs Edmund Nadolski
2017-06-27 17:06 ` [PATCH 00/13] use rbtrees for preliminary backrefs David Sterba
13 siblings, 0 replies; 23+ messages in thread
From: Edmund Nadolski @ 2017-06-20 16:06 UTC (permalink / raw)
To: enadolski, linux-btrfs
When called with a struct share_check, find_parent_nodes()
will detect a shared extent and immediately return with
BACKREF_SHARED_FOUND.
Signed-off-by: Edmund Nadolski <enadolski@suse.com>
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
fs/btrfs/backref.c | 165 ++++++++++++++++++++++++++++++++++++-----------------
1 file changed, 112 insertions(+), 53 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index e95049a..7f02c51 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -139,6 +139,25 @@ struct preftrees {
struct preftree indirect; /* BTRFS_[TREE_BLOCK|EXTENT_DATA]_REF_KEY */
};
+/*
+ * Checks for a shared extent during backref search.
+ *
+ * The share_count tracks prelim_refs (direct and indirect) having a
+ * ref->count >0:
+ * - incremented when a ref->count transitions to >0
+ * - decremented when a ref->count transitions to <1
+ */
+struct share_check {
+ u64 root_objectid;
+ u64 inum;
+ int share_count;
+};
+
+static inline int extent_is_shared(struct share_check *sc)
+{
+ return (sc && sc->share_count > 1) ? BACKREF_FOUND_SHARED : 0;
+}
+
static struct kmem_cache *btrfs_prelim_ref_cache;
int __init btrfs_prelim_ref_init(void)
@@ -199,14 +218,26 @@ static int prelim_ref_compare(struct prelim_ref *ref1,
return 0;
}
+void update_share_count(struct share_check *sc, int oldcount, int newcount)
+{
+ if ((!sc) || (oldcount == 0 && newcount < 1))
+ return;
+
+ if (oldcount > 0 && newcount < 1)
+ sc->share_count--;
+ else if (oldcount < 1 && newcount > 0)
+ sc->share_count++;
+}
+
/*
* Add @newref to the @root rbtree, merging identical refs.
*
- * Callers should assumed that newref has been freed after calling.
+ * Callers should assume that newref has been freed after calling.
*/
static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,
struct preftree *preftree,
- struct prelim_ref *newref)
+ struct prelim_ref *newref,
+ struct share_check *sc)
{
struct rb_root *root;
struct rb_node **p;
@@ -238,12 +269,20 @@ static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,
eie->next = newref->inode_list;
trace_btrfs_prelim_ref_merge(fs_info, ref, newref,
preftree->count);
+ /*
+ * A delayed ref can have newref->count < 0.
+ * The ref->count is updated to follow any
+ * BTRFS_[ADD|DROP]_DELAYED_REF actions.
+ */
+ update_share_count(sc, ref->count,
+ ref->count + newref->count);
ref->count += newref->count;
release_pref(newref);
return;
}
}
+ update_share_count(sc, 0, newref->count);
preftree->count++;
trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count);
rb_link_node(&newref->rbnode, parent, p);
@@ -307,7 +346,8 @@ static void prelim_release(struct preftree *preftree)
static int add_prelim_ref(const struct btrfs_fs_info *fs_info,
struct preftree *preftree, u64 root_id,
const struct btrfs_key *key, int level, u64 parent,
- u64 wanted_disk_byte, int count, gfp_t gfp_mask)
+ u64 wanted_disk_byte, int count,
+ struct share_check *sc, gfp_t gfp_mask)
{
struct prelim_ref *ref;
@@ -352,31 +392,31 @@ static int add_prelim_ref(const struct btrfs_fs_info *fs_info,
ref->count = count;
ref->parent = parent;
ref->wanted_disk_byte = wanted_disk_byte;
- prelim_ref_insert(fs_info, preftree, ref);
-
- return 0;
+ prelim_ref_insert(fs_info, preftree, ref, sc);
+ return extent_is_shared(sc);
}
/* direct refs use root == 0, key == NULL */
static int add_direct_ref(const struct btrfs_fs_info *fs_info,
struct preftrees *preftrees, int level, u64 parent,
- u64 wanted_disk_byte, int count, gfp_t gfp_mask)
+ u64 wanted_disk_byte, int count,
+ struct share_check *sc, gfp_t gfp_mask)
{
return add_prelim_ref(fs_info, &preftrees->direct, 0, NULL, level,
- parent, wanted_disk_byte, count, gfp_mask);
+ parent, wanted_disk_byte, count, sc, gfp_mask);
}
/* indirect refs use parent == 0 */
static int add_indirect_ref(const struct btrfs_fs_info *fs_info,
struct preftrees *preftrees, u64 root_id,
const struct btrfs_key *key, int level,
- u64 wanted_disk_byte, int count, gfp_t gfp_mask)
+ u64 wanted_disk_byte, int count,
+ struct share_check *sc, gfp_t gfp_mask)
{
return add_prelim_ref(fs_info, &preftrees->indirect, root_id, key,
- level, 0, wanted_disk_byte, count, gfp_mask);
+ level, 0, wanted_disk_byte, count, sc, gfp_mask);
}
-
static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
struct ulist *parents, struct prelim_ref *ref,
int level, u64 time_seq, const u64 *extent_item_pos,
@@ -572,7 +612,7 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
struct btrfs_path *path, u64 time_seq,
struct preftrees *preftrees,
const u64 *extent_item_pos, u64 total_refs,
- u64 root_objectid)
+ struct share_check *sc)
{
int err;
int ret = 0;
@@ -609,7 +649,8 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
continue;
}
- if (root_objectid && ref->root_id != root_objectid) {
+ if (sc && sc->root_objectid &&
+ ref->root_id != sc->root_objectid) {
release_pref(ref);
ret = BACKREF_FOUND_SHARED;
goto out;
@@ -651,11 +692,15 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
memcpy(new_ref, ref, sizeof(*ref));
new_ref->parent = node->val;
new_ref->inode_list = unode_aux_to_inode_list(node);
- prelim_ref_insert(fs_info, &preftrees->direct, new_ref);
+ prelim_ref_insert(fs_info, &preftrees->direct,
+ new_ref, NULL);
}
- /* Now it's a direct ref, put it in the the direct tree */
- prelim_ref_insert(fs_info, &preftrees->direct, ref);
+ /*
+ * Now it's a direct ref, put it in the the direct tree. We must
+ * do this last because the ref could be merged/freed here.
+ */
+ prelim_ref_insert(fs_info, &preftrees->direct, ref, NULL);
ulist_reinit(parents);
cond_resched();
@@ -710,7 +755,7 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info,
static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
struct btrfs_delayed_ref_head *head, u64 seq,
struct preftrees *preftrees, u64 *total_refs,
- u64 inum)
+ struct share_check *sc)
{
struct btrfs_delayed_ref_node *node;
struct btrfs_delayed_extent_op *extent_op = head->extent_op;
@@ -752,7 +797,7 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
&op_key, ref->level + 1,
node->bytenr,
node->ref_mod * sgn,
- GFP_ATOMIC);
+ sc, GFP_ATOMIC);
break;
}
case BTRFS_SHARED_BLOCK_REF_KEY: {
@@ -764,7 +809,7 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
ret = add_direct_ref(fs_info, preftrees,
ref->level + 1, ref->parent,
node->bytenr, node->ref_mod * sgn,
- GFP_ATOMIC);
+ sc, GFP_ATOMIC);
break;
}
case BTRFS_EXTENT_DATA_REF_KEY: {
@@ -780,15 +825,15 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
* Found a inum that doesn't match our known inum, we
* know it's shared.
*/
- if (inum && ref->objectid != inum) {
+ if (sc && sc->inum && ref->objectid != sc->inum) {
ret = BACKREF_FOUND_SHARED;
- break;
+ goto out;
}
ret = add_indirect_ref(fs_info, preftrees, ref->root,
&key, 0, node->bytenr,
node->ref_mod * sgn,
- GFP_ATOMIC);
+ sc, GFP_ATOMIC);
break;
}
case BTRFS_SHARED_DATA_REF_KEY: {
@@ -800,26 +845,35 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
ret = add_direct_ref(fs_info, preftrees, 0,
ref->parent, node->bytenr,
node->ref_mod * sgn,
- GFP_ATOMIC);
+ sc, GFP_ATOMIC);
break;
}
default:
WARN_ON(1);
}
- if (ret)
+ /*
+ * We must ignore BACKREF_FOUND_SHARED until all delayed
+ * refs have been checked.
+ */
+ if (ret && (ret != BACKREF_FOUND_SHARED))
break;
}
+ if (!ret)
+ ret = extent_is_shared(sc);
+out:
spin_unlock(&head->lock);
return ret;
}
/*
* add all inline backrefs for bytenr to the list
+ *
+ * Returns 0 on success, <0 on error, or BACKREF_FOUND_SHARED.
*/
static int add_inline_refs(const struct btrfs_fs_info *fs_info,
struct btrfs_path *path, u64 bytenr,
int *info_level, struct preftrees *preftrees,
- u64 *total_refs, u64 inum)
+ u64 *total_refs, struct share_check *sc)
{
int ret = 0;
int slot;
@@ -876,7 +930,7 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info,
case BTRFS_SHARED_BLOCK_REF_KEY:
ret = add_direct_ref(fs_info, preftrees,
*info_level + 1, offset,
- bytenr, 1, GFP_NOFS);
+ bytenr, 1, NULL, GFP_NOFS);
break;
case BTRFS_SHARED_DATA_REF_KEY: {
struct btrfs_shared_data_ref *sdref;
@@ -886,13 +940,13 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info,
count = btrfs_shared_data_ref_count(leaf, sdref);
ret = add_direct_ref(fs_info, preftrees, 0, offset,
- bytenr, count, GFP_NOFS);
+ bytenr, count, sc, GFP_NOFS);
break;
}
case BTRFS_TREE_BLOCK_REF_KEY:
ret = add_indirect_ref(fs_info, preftrees, offset,
NULL, *info_level + 1,
- bytenr, 1, GFP_NOFS);
+ bytenr, 1, NULL, GFP_NOFS);
break;
case BTRFS_EXTENT_DATA_REF_KEY: {
struct btrfs_extent_data_ref *dref;
@@ -906,7 +960,7 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info,
key.type = BTRFS_EXTENT_DATA_KEY;
key.offset = btrfs_extent_data_ref_offset(leaf, dref);
- if (inum && key.objectid != inum) {
+ if (sc && sc->inum && key.objectid != sc->inum) {
ret = BACKREF_FOUND_SHARED;
break;
}
@@ -915,7 +969,7 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info,
ret = add_indirect_ref(fs_info, preftrees, root,
&key, 0, bytenr, count,
- GFP_NOFS);
+ sc, GFP_NOFS);
break;
}
default:
@@ -931,11 +985,13 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info,
/*
* add all non-inline backrefs for bytenr to the list
+ *
+ * Returns 0 on success, <0 on error, or BACKREF_FOUND_SHARED.
*/
static int add_keyed_refs(struct btrfs_fs_info *fs_info,
struct btrfs_path *path, u64 bytenr,
int info_level, struct preftrees *preftrees,
- u64 inum)
+ struct share_check *sc)
{
struct btrfs_root *extent_root = fs_info->extent_root;
int ret;
@@ -968,7 +1024,7 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
/* SHARED DIRECT METADATA backref */
ret = add_direct_ref(fs_info, preftrees,
info_level + 1, key.offset,
- bytenr, 1, GFP_NOFS);
+ bytenr, 1, NULL, GFP_NOFS);
break;
case BTRFS_SHARED_DATA_REF_KEY: {
/* SHARED DIRECT FULL backref */
@@ -980,14 +1036,14 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
count = btrfs_shared_data_ref_count(leaf, sdref);
ret = add_direct_ref(fs_info, preftrees, 0,
key.offset, bytenr, count,
- GFP_NOFS);
+ sc, GFP_NOFS);
break;
}
case BTRFS_TREE_BLOCK_REF_KEY:
/* NORMAL INDIRECT METADATA backref */
ret = add_indirect_ref(fs_info, preftrees, key.offset,
NULL, info_level + 1, bytenr,
- 1, GFP_NOFS);
+ 1, NULL, GFP_NOFS);
break;
case BTRFS_EXTENT_DATA_REF_KEY: {
/* NORMAL INDIRECT DATA backref */
@@ -1003,7 +1059,7 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
key.type = BTRFS_EXTENT_DATA_KEY;
key.offset = btrfs_extent_data_ref_offset(leaf, dref);
- if (inum && key.objectid != inum) {
+ if (sc && sc->inum && key.objectid != sc->inum) {
ret = BACKREF_FOUND_SHARED;
break;
}
@@ -1011,7 +1067,7 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
root = btrfs_extent_data_ref_root(leaf, dref);
ret = add_indirect_ref(fs_info, preftrees, root,
&key, 0, bytenr, count,
- GFP_NOFS);
+ sc, GFP_NOFS);
break;
}
default:
@@ -1031,20 +1087,23 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
* indirect refs to their parent bytenr.
* When roots are found, they're added to the roots list
*
- * NOTE: This can return values > 0
- *
* If time_seq is set to SEQ_LAST, it will not search delayed_refs, and behave
* much like trans == NULL case, the difference only lies in it will not
* commit root.
* The special case is for qgroup to search roots in commit_transaction().
*
+ * @sc - if !NULL, then immediately return BACKREF_FOUND_SHARED when a
+ * shared extent is detected.
+ *
+ * Otherwise this returns 0 for success and <0 for an error.
+ *
* FIXME some caching might speed things up
*/
static int find_parent_nodes(struct btrfs_trans_handle *trans,
struct btrfs_fs_info *fs_info, u64 bytenr,
u64 time_seq, struct ulist *refs,
struct ulist *roots, const u64 *extent_item_pos,
- u64 root_objectid, u64 inum)
+ struct share_check *sc)
{
struct btrfs_key key;
struct btrfs_path *path;
@@ -1124,17 +1183,13 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
}
spin_unlock(&delayed_refs->lock);
ret = add_delayed_refs(fs_info, head, time_seq,
- &preftrees, &total_refs, inum);
+ &preftrees, &total_refs, sc);
mutex_unlock(&head->mutex);
if (ret)
goto out;
} else {
spin_unlock(&delayed_refs->lock);
}
-
- /*
- * TODO - implement short circuit for BACKREF_FOUND_SHARED
- */
}
if (path->slots[0]) {
@@ -1150,11 +1205,11 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
key.type == BTRFS_METADATA_ITEM_KEY)) {
ret = add_inline_refs(fs_info, path, bytenr,
&info_level, &preftrees,
- &total_refs, inum);
+ &total_refs, sc);
if (ret)
goto out;
ret = add_keyed_refs(fs_info, path, bytenr, info_level,
- &preftrees, inum);
+ &preftrees, sc);
if (ret)
goto out;
}
@@ -1167,8 +1222,7 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
goto out;
ret = resolve_indirect_refs(fs_info, path, time_seq, &preftrees,
- extent_item_pos, total_refs,
- root_objectid);
+ extent_item_pos, total_refs, sc);
if (ret)
goto out;
@@ -1187,7 +1241,8 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
node = rb_next(&ref->rbnode);
WARN_ON(ref->count < 0);
if (roots && ref->count && ref->root_id && ref->parent == 0) {
- if (root_objectid && ref->root_id != root_objectid) {
+ if (sc && sc->root_objectid &&
+ ref->root_id != sc->root_objectid) {
ret = BACKREF_FOUND_SHARED;
goto out;
}
@@ -1290,7 +1345,7 @@ static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
return -ENOMEM;
ret = find_parent_nodes(trans, fs_info, bytenr, time_seq,
- *leafs, NULL, extent_item_pos, 0, 0);
+ *leafs, NULL, extent_item_pos, NULL);
if (ret < 0 && ret != -ENOENT) {
free_leaf_list(*leafs);
return ret;
@@ -1333,7 +1388,7 @@ static int btrfs_find_all_roots_safe(struct btrfs_trans_handle *trans,
ULIST_ITER_INIT(&uiter);
while (1) {
ret = find_parent_nodes(trans, fs_info, bytenr, time_seq,
- tmp, *roots, NULL, 0, 0);
+ tmp, *roots, NULL, NULL);
if (ret < 0 && ret != -ENOENT) {
ulist_free(tmp);
ulist_free(*roots);
@@ -1389,6 +1444,11 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr)
struct ulist_node *node;
struct seq_list elem = SEQ_LIST_INIT(elem);
int ret = 0;
+ struct share_check shared = {
+ .root_objectid = root->objectid,
+ .inum = inum,
+ .share_count = 0,
+ };
tmp = ulist_alloc(GFP_NOFS);
roots = ulist_alloc(GFP_NOFS);
@@ -1408,9 +1468,8 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr)
ULIST_ITER_INIT(&uiter);
while (1) {
- /* TODO - short-circuit when only checking for shared... */
ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp,
- roots, NULL, root->objectid, inum);
+ roots, NULL, &shared);
if (ret == BACKREF_FOUND_SHARED) {
/* this is the only condition under which we return 1 */
ret = 1;
--
2.10.2
^ permalink raw reply related [flat|nested] 23+ messages in thread
* [PATCH 13/13] btrfs: clean up extraneous computations in add_delayed_refs
2017-06-20 16:06 [PATCH 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (11 preceding siblings ...)
2017-06-20 16:06 ` [PATCH 12/13] btrfs: allow backref search checks for shared extents Edmund Nadolski
@ 2017-06-20 16:06 ` Edmund Nadolski
2017-06-27 17:06 ` [PATCH 00/13] use rbtrees for preliminary backrefs David Sterba
13 siblings, 0 replies; 23+ messages in thread
From: Edmund Nadolski @ 2017-06-20 16:06 UTC (permalink / raw)
To: enadolski, linux-btrfs
Repeating the same computation in multiple places is not
necessary.
Signed-off-by: Edmund Nadolski <enadolski@suse.com>
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
fs/btrfs/backref.c | 30 +++++++++++++-----------------
1 file changed, 13 insertions(+), 17 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 7f02c51..05f37bb 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -761,7 +761,7 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
struct btrfs_delayed_extent_op *extent_op = head->extent_op;
struct btrfs_key key;
struct btrfs_key op_key = {0};
- int sgn;
+ int count;
int ret = 0;
if (extent_op && extent_op->update_key)
@@ -778,15 +778,15 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
WARN_ON(1);
continue;
case BTRFS_ADD_DELAYED_REF:
- sgn = 1;
+ count = node->ref_mod;
break;
case BTRFS_DROP_DELAYED_REF:
- sgn = -1;
+ count = node->ref_mod * -1;
break;
default:
BUG_ON(1);
}
- *total_refs += (node->ref_mod * sgn);
+ *total_refs += count;
switch (node->type) {
case BTRFS_TREE_BLOCK_REF_KEY: {
/* NORMAL INDIRECT METADATA backref */
@@ -795,9 +795,8 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
ref = btrfs_delayed_node_to_tree_ref(node);
ret = add_indirect_ref(fs_info, preftrees, ref->root,
&op_key, ref->level + 1,
- node->bytenr,
- node->ref_mod * sgn,
- sc, GFP_ATOMIC);
+ node->bytenr, count, sc,
+ GFP_ATOMIC);
break;
}
case BTRFS_SHARED_BLOCK_REF_KEY: {
@@ -806,9 +805,8 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
ref = btrfs_delayed_node_to_tree_ref(node);
- ret = add_direct_ref(fs_info, preftrees,
- ref->level + 1, ref->parent,
- node->bytenr, node->ref_mod * sgn,
+ ret = add_direct_ref(fs_info, preftrees, ref->level + 1,
+ ref->parent, node->bytenr, count,
sc, GFP_ATOMIC);
break;
}
@@ -831,9 +829,8 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
}
ret = add_indirect_ref(fs_info, preftrees, ref->root,
- &key, 0, node->bytenr,
- node->ref_mod * sgn,
- sc, GFP_ATOMIC);
+ &key, 0, node->bytenr, count, sc,
+ GFP_ATOMIC);
break;
}
case BTRFS_SHARED_DATA_REF_KEY: {
@@ -842,10 +839,9 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
ref = btrfs_delayed_node_to_data_ref(node);
- ret = add_direct_ref(fs_info, preftrees, 0,
- ref->parent, node->bytenr,
- node->ref_mod * sgn,
- sc, GFP_ATOMIC);
+ ret = add_direct_ref(fs_info, preftrees, 0, ref->parent,
+ node->bytenr, count, sc,
+ GFP_ATOMIC);
break;
}
default:
--
2.10.2
^ permalink raw reply related [flat|nested] 23+ messages in thread
* Re: [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees
2017-06-20 16:06 ` [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees Edmund Nadolski
@ 2017-06-26 17:07 ` Jeff Mahoney
2017-06-27 20:09 ` Jeff Mahoney
2017-06-27 16:49 ` [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees David Sterba
1 sibling, 1 reply; 23+ messages in thread
From: Jeff Mahoney @ 2017-06-26 17:07 UTC (permalink / raw)
To: Edmund Nadolski, linux-btrfs
[-- Attachment #1.1: Type: text/plain, Size: 2623 bytes --]
On 6/20/17 12:06 PM, Edmund Nadolski wrote:
> It's been known for a while that the use of multiple lists
> that are periodically merged was an algorithmic problem within
> btrfs. There are several workloads that don't complete in any
> reasonable amount of time (e.g. btrfs/130) and others that cause
> soft lockups.
>
> The solution is to use a pair of rbtrees that do insertion merging
> for both indirect and direct refs, with the former converting
> refs into the latter. The result is a btrfs/130 workload that
> used to take several hours now takes about half of that. This
> runtime still isn't acceptable and a future patch will address that
> by moving the rbtrees higher in the stack so the lookups can be
> shared across multiple calls to find_parent_nodes.
>
> Signed-off-by: Edmund Nadolski <enadolski@suse.com>
> Signed-off-by: Jeff Mahoney <jeffm@suse.com>
[...]
> @@ -504,37 +665,22 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
> return ret;
> }
>
> -static inline int ref_for_same_block(struct prelim_ref *ref1,
> - struct prelim_ref *ref2)
> -{
> - if (ref1->level != ref2->level)
> - return 0;
> - if (ref1->root_id != ref2->root_id)
> - return 0;
> - if (ref1->key_for_search.type != ref2->key_for_search.type)
> - return 0;
> - if (ref1->key_for_search.objectid != ref2->key_for_search.objectid)
> - return 0;
> - if (ref1->key_for_search.offset != ref2->key_for_search.offset)
> - return 0;
> - if (ref1->parent != ref2->parent)
> - return 0;
> -
> - return 1;
> -}
> -
> /*
> * read tree blocks and add keys where required.
> */
> static int add_missing_keys(struct btrfs_fs_info *fs_info,
> - struct list_head *head)
> + struct preftrees *preftrees)
> {
> struct prelim_ref *ref;
> struct extent_buffer *eb;
> + struct rb_node *node = rb_first(&preftrees->indirect.root);
> +
> + while (node) {
> + ref = rb_entry(node, struct prelim_ref, rbnode);
> + node = rb_next(&ref->rbnode);
> + if (WARN(ref->parent, "BUG: direct ref found in indirect tree"))
> + return -EINVAL;
>
> - list_for_each_entry(ref, head, list) {
> - if (ref->parent)
> - continue;
> if (ref->key_for_search.type)
> continue;
> BUG_ON(!ref->wanted_disk_byte);
Hi Ed -
I missed this in earlier review, but this can't work. We're modifying
the ref in a way that the comparator will care about -- so the node
would move in the tree.
It's not a fatal flaw and, in fact, leaves us an opening to fix a
separate locking issue.
-Jeff
--
Jeff Mahoney
SUSE Labs
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 06/13] btrfs: btrfs_check_shared should manage its own transaction
2017-06-20 16:06 ` [PATCH 06/13] btrfs: btrfs_check_shared should manage its own transaction Edmund Nadolski
@ 2017-06-27 15:40 ` David Sterba
0 siblings, 0 replies; 23+ messages in thread
From: David Sterba @ 2017-06-27 15:40 UTC (permalink / raw)
To: Edmund Nadolski; +Cc: linux-btrfs
On Tue, Jun 20, 2017 at 10:06:46AM -0600, Edmund Nadolski wrote:
At least some description should be put here, why the transaction is
being moved to btrfs_check_shared.
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 07/13] btrfs: remove ref_tree implementation from backref.c
2017-06-20 16:06 ` [PATCH 07/13] btrfs: remove ref_tree implementation from backref.c Edmund Nadolski
@ 2017-06-27 15:48 ` David Sterba
0 siblings, 0 replies; 23+ messages in thread
From: David Sterba @ 2017-06-27 15:48 UTC (permalink / raw)
To: Edmund Nadolski; +Cc: linux-btrfs, lufq.fnst
On Tue, Jun 20, 2017 at 10:06:47AM -0600, Edmund Nadolski wrote:
> The BACKREF_FOUND_SHARED checking will be addressed in an upcoming
> patch.
So this reverts the commit afce772e87c36c7f07f230a76d525025aaf09e41
"btrfs: fix check_shared for fiemap ioctl", this should be mentioned in
the changelog. Also the code is not that old, 09/2016 so I'd expect some
reasoning why reverting is the best option here, and also CC the
original author.
The ref_root is supposed to fix some problem, I get that you've chosen a
different approach to address but this would be good to have mentioned
in the changelog.
Both approaches do not seem to be compatible and could coexist so
removing the code is fine, although this would introduce the original
problem for a few commits. I don't think this is a problem.
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees
2017-06-20 16:06 ` [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees Edmund Nadolski
2017-06-26 17:07 ` Jeff Mahoney
@ 2017-06-27 16:49 ` David Sterba
2017-06-27 21:10 ` Jeff Mahoney
1 sibling, 1 reply; 23+ messages in thread
From: David Sterba @ 2017-06-27 16:49 UTC (permalink / raw)
To: Edmund Nadolski; +Cc: linux-btrfs
On Tue, Jun 20, 2017 at 10:06:48AM -0600, Edmund Nadolski wrote:
> It's been known for a while that the use of multiple lists
> that are periodically merged was an algorithmic problem within
> btrfs. There are several workloads that don't complete in any
> reasonable amount of time (e.g. btrfs/130) and others that cause
> soft lockups.
>
> The solution is to use a pair of rbtrees that do insertion merging
> for both indirect and direct refs, with the former converting
> refs into the latter. The result is a btrfs/130 workload that
> used to take several hours now takes about half of that. This
> runtime still isn't acceptable and a future patch will address that
> by moving the rbtrees higher in the stack so the lookups can be
> shared across multiple calls to find_parent_nodes.
>
> Signed-off-by: Edmund Nadolski <enadolski@suse.com>
> Signed-off-by: Jeff Mahoney <jeffm@suse.com>
> ---
> fs/btrfs/backref.c | 415 ++++++++++++++++++++++++++++++++++-------------------
> 1 file changed, 267 insertions(+), 148 deletions(-)
>
> diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
> index 0d1e7cb..daae7b6 100644
> --- a/fs/btrfs/backref.c
> +++ b/fs/btrfs/backref.c
> @@ -129,7 +129,7 @@ static int find_extent_in_eb(const struct extent_buffer *eb,
> * this structure records all encountered refs on the way up to the root
> */
> struct prelim_ref {
> - struct list_head list;
> + struct rb_node rbnode;
> u64 root_id;
> struct btrfs_key key_for_search;
> int level;
> @@ -139,6 +139,17 @@ struct prelim_ref {
> u64 wanted_disk_byte;
> };
>
> +struct preftree {
> + struct rb_root root;
> +};
> +
> +#define PREFTREE_INIT { .root = RB_ROOT }
> +
> +struct preftrees {
> + struct preftree direct; /* BTRFS_SHARED_[DATA|BLOCK]_REF_KEY */
> + struct preftree indirect; /* BTRFS_[TREE_BLOCK|EXTENT_DATA]_REF_KEY */
> +};
> +
> static struct kmem_cache *btrfs_prelim_ref_cache;
>
> int __init btrfs_prelim_ref_init(void)
> @@ -158,6 +169,108 @@ void btrfs_prelim_ref_exit(void)
> kmem_cache_destroy(btrfs_prelim_ref_cache);
> }
>
> +static void release_pref(struct prelim_ref *ref)
> +{
> + kmem_cache_free(btrfs_prelim_ref_cache, ref);
This is a bit confusing, 'release' in btrfs code is used to release the
resources but not to actually free the memory. See eg.
btrfs_release_path and btrfs_free_path. As the helper is trivial and I
don't see any other additions to it in the followup patches, I suggest
to drop and opencode it.
> +}
> +
> +/*
> + * Return 0 when both refs are for the same block (and can be merged).
> + * A -1 return indicates ref1 is a 'lower' block than ref2, while 1
> + * indicates a 'higher' block.
> + */
> +static int prelim_ref_compare(struct prelim_ref *ref1,
> + struct prelim_ref *ref2)
> +{
> + if (ref1->level < ref2->level)
> + return -1;
> + if (ref1->level > ref2->level)
> + return 1;
> + if (ref1->root_id < ref2->root_id)
> + return -1;
> + if (ref1->root_id > ref2->root_id)
> + return 1;
> + if (ref1->key_for_search.type < ref2->key_for_search.type)
> + return -1;
> + if (ref1->key_for_search.type > ref2->key_for_search.type)
> + return 1;
> + if (ref1->key_for_search.objectid < ref2->key_for_search.objectid)
> + return -1;
> + if (ref1->key_for_search.objectid > ref2->key_for_search.objectid)
> + return 1;
> + if (ref1->key_for_search.offset < ref2->key_for_search.offset)
> + return -1;
> + if (ref1->key_for_search.offset > ref2->key_for_search.offset)
> + return 1;
> + if (ref1->parent < ref2->parent)
> + return -1;
> + if (ref1->parent > ref2->parent)
> + return 1;
> +
> + return 0;
> +}
> +
> +/*
> + * Add @newref to the @root rbtree, merging identical refs.
> + *
> + * Callers should assumed that newref has been freed after calling.
> + */
> +static void prelim_ref_insert(struct preftree *preftree,
> + struct prelim_ref *newref)
> +{
> + struct rb_root *root;
> + struct rb_node **p;
> + struct rb_node *parent = NULL;
> + struct prelim_ref *ref;
> + int result;
> +
> + root = &preftree->root;
> + p = &root->rb_node;
> +
> + while (*p) {
> + parent = *p;
> + ref = rb_entry(parent, struct prelim_ref, rbnode);
> + result = prelim_ref_compare(ref, newref);
> + if (result < 0) {
> + p = &(*p)->rb_left;
> + } else if (result > 0) {
> + p = &(*p)->rb_right;
> + } else {
> + /* Identical refs, merge them and free @newref */
> + struct extent_inode_elem *eie = ref->inode_list;
> +
> + while (eie && eie->next)
> + eie = eie->next;
> +
> + if (!eie)
> + ref->inode_list = newref->inode_list;
> + else
> + eie->next = newref->inode_list;
> + ref->count += newref->count;
> + release_pref(newref);
> + return;
> + }
> + }
> +
> + rb_link_node(&newref->rbnode, parent, p);
> + rb_insert_color(&newref->rbnode, root);
> +}
> +
> +/*
> + * Release the entire tree. We don't care about internal consistency so
> + * just free everything and then reset the tree root.
> + */
> +static void prelim_release(struct preftree *preftree)
> +{
> + struct prelim_ref *ref, *next_ref;
> +
> + rbtree_postorder_for_each_entry_safe(ref, next_ref, &preftree->root,
> + rbnode)
> + release_pref(ref);
> +
> + preftree->root = RB_ROOT;
> +}
> +
> /*
> * the rules for all callers of this function are:
> * - obtaining the parent is the goal
> @@ -196,7 +309,7 @@ void btrfs_prelim_ref_exit(void)
> * additional information that's available but not required to find the parent
> * block might help in merging entries to gain some speed.
> */
> -static int add_prelim_ref(struct list_head *head, u64 root_id,
> +static int add_prelim_ref(struct preftree *preftree, u64 root_id,
> const struct btrfs_key *key, int level, u64 parent,
> u64 wanted_disk_byte, int count, gfp_t gfp_mask)
> {
> @@ -243,11 +356,29 @@ static int add_prelim_ref(struct list_head *head, u64 root_id,
> ref->count = count;
> ref->parent = parent;
> ref->wanted_disk_byte = wanted_disk_byte;
> - list_add_tail(&ref->list, head);
> + prelim_ref_insert(preftree, ref);
>
> return 0;
> }
>
> +/* direct refs use root == 0, key == NULL */
> +static int add_direct_ref(struct preftrees *preftrees, int level, u64 parent,
> + u64 wanted_disk_byte, int count, gfp_t gfp_mask)
> +{
> + return add_prelim_ref(&preftrees->direct, 0, NULL, level, parent,
> + wanted_disk_byte, count, gfp_mask);
> +}
> +
> +/* indirect refs use parent == 0 */
> +static int add_indirect_ref(struct preftrees *preftrees, u64 root_id,
> + const struct btrfs_key *key, int level,
> + u64 wanted_disk_byte, int count, gfp_t gfp_mask)
> +{
> + return add_prelim_ref(&preftrees->indirect, root_id, key, level, 0,
> + wanted_disk_byte, count, gfp_mask);
> +}
> +
> +
> static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
> struct ulist *parents, struct prelim_ref *ref,
> int level, u64 time_seq, const u64 *extent_item_pos,
> @@ -429,38 +560,58 @@ unode_aux_to_inode_list(struct ulist_node *node)
> }
>
> /*
> - * resolve all indirect backrefs from the list
> + * We maintain two separate rbtrees: one for indirect refs and one for
> + * direct refs. Each tree does merge on insertion. Once all of the
> + * refs have been located, we iterate over the indirect ref tree, resolve
> + * each reference and remove it from the indirect tree, and then insert
> + * the resolved reference into the direct tree, merging there too.
> + *
> + * New backrefs (i.e., for parent nodes) are added to the direct/indirect
> + * rbtrees as they are encountered. The new, indirect backrefs are
> + * resolved as above.
> */
> static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
> struct btrfs_path *path, u64 time_seq,
> - struct list_head *head,
> + struct preftrees *preftrees,
> const u64 *extent_item_pos, u64 total_refs,
> u64 root_objectid)
> {
> int err;
> int ret = 0;
> - struct prelim_ref *ref;
> - struct prelim_ref *ref_safe;
> - struct prelim_ref *new_ref;
> struct ulist *parents;
> struct ulist_node *node;
> struct ulist_iterator uiter;
> + struct rb_node *rnode;
>
> parents = ulist_alloc(GFP_NOFS);
> if (!parents)
> return -ENOMEM;
>
> /*
> - * _safe allows us to insert directly after the current item without
> - * iterating over the newly inserted items.
> - * we're also allowed to re-assign ref during iteration.
> + * We could trade memory usage for performance here by iterating
> + * the tree, allocating new refs for each insertion, and then
> + * freeing the entire indirect tree when we're done. In some test
> + * cases, the tree can grow quite large (~200k objects).
> */
> - list_for_each_entry_safe(ref, ref_safe, head, list) {
> - if (ref->parent) /* already direct */
> - continue;
> - if (ref->count == 0)
> + while ((rnode = rb_first(&preftrees->indirect.root))) {
> + struct prelim_ref *ref;
> +
> + ref = rb_entry(rnode, struct prelim_ref, rbnode);
> + if (WARN(ref->parent,
> + "BUG: direct ref found in indirect tree")) {
Is this meant as an assertion or do you expect this could also happen
during normal operation?
> + ret = -EINVAL;
> + goto out;
> + }
> +
> + rb_erase(&ref->rbnode, &preftrees->indirect.root);
> +
> + if (ref->count == 0) {
> + release_pref(ref);
> continue;
> + }
> +
> if (root_objectid && ref->root_id != root_objectid) {
> + release_pref(ref);
> ret = BACKREF_FOUND_SHARED;
> goto out;
> }
> @@ -472,8 +623,11 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
> * and return directly.
> */
> if (err == -ENOENT) {
> + /* This only happens when we're doing sanity testing */
> + release_pref(ref);
> continue;
> } else if (err) {
> + release_pref(ref);
> ret = err;
> goto out;
> }
> @@ -484,19 +638,26 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
> ref->parent = node ? node->val : 0;
> ref->inode_list = unode_aux_to_inode_list(node);
>
> - /* additional parents require new refs being added here */
> + /* Add a prelim_ref(s) for any other parent(s). */
> while ((node = ulist_next(parents, &uiter))) {
> + struct prelim_ref *new_ref;
> +
> new_ref = kmem_cache_alloc(btrfs_prelim_ref_cache,
> GFP_NOFS);
> if (!new_ref) {
> + release_pref(ref);
> ret = -ENOMEM;
> goto out;
> }
> memcpy(new_ref, ref, sizeof(*ref));
> new_ref->parent = node->val;
> new_ref->inode_list = unode_aux_to_inode_list(node);
> - list_add(&new_ref->list, &ref->list);
> + prelim_ref_insert(&preftrees->direct, new_ref);
> }
> +
> + /* Now it's a direct ref, put it in the the direct tree */
> + prelim_ref_insert(&preftrees->direct, ref);
> +
> ulist_reinit(parents);
> }
> out:
> @@ -504,37 +665,22 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
> return ret;
> }
>
> -static inline int ref_for_same_block(struct prelim_ref *ref1,
> - struct prelim_ref *ref2)
> -{
> - if (ref1->level != ref2->level)
> - return 0;
> - if (ref1->root_id != ref2->root_id)
> - return 0;
> - if (ref1->key_for_search.type != ref2->key_for_search.type)
> - return 0;
> - if (ref1->key_for_search.objectid != ref2->key_for_search.objectid)
> - return 0;
> - if (ref1->key_for_search.offset != ref2->key_for_search.offset)
> - return 0;
> - if (ref1->parent != ref2->parent)
> - return 0;
> -
> - return 1;
> -}
> -
> /*
> * read tree blocks and add keys where required.
> */
> static int add_missing_keys(struct btrfs_fs_info *fs_info,
> - struct list_head *head)
> + struct preftrees *preftrees)
> {
> struct prelim_ref *ref;
> struct extent_buffer *eb;
> + struct rb_node *node = rb_first(&preftrees->indirect.root);
> +
> + while (node) {
> + ref = rb_entry(node, struct prelim_ref, rbnode);
> + node = rb_next(&ref->rbnode);
> + if (WARN(ref->parent, "BUG: direct ref found in indirect tree"))
> + return -EINVAL;
>
> - list_for_each_entry(ref, head, list) {
> - if (ref->parent)
> - continue;
> if (ref->key_for_search.type)
> continue;
> BUG_ON(!ref->wanted_disk_byte);
> @@ -557,57 +703,11 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info,
> }
>
> /*
> - * merge backrefs and adjust counts accordingly
> - *
> - * FIXME: For MERGE_IDENTICAL_KEYS, if we add more keys in add_prelim_ref
> - * then we can merge more here. Additionally, we could even add a key
> - * range for the blocks we looked into to merge even more (-> replace
> - * unresolved refs by those having a parent).
> - */
> -static void merge_refs(struct list_head *head, enum merge_mode mode)
> -{
> - struct prelim_ref *pos1;
> -
> - list_for_each_entry(pos1, head, list) {
> - struct prelim_ref *pos2 = pos1, *tmp;
> -
> - list_for_each_entry_safe_continue(pos2, tmp, head, list) {
> - struct prelim_ref *ref1 = pos1, *ref2 = pos2;
> - struct extent_inode_elem *eie;
> -
> - if (!ref_for_same_block(ref1, ref2))
> - continue;
> - if (mode == MERGE_IDENTICAL_KEYS) {
> - if (!ref1->parent && ref2->parent)
> - swap(ref1, ref2);
> - } else {
> - if (ref1->parent != ref2->parent)
> - continue;
> - }
> -
> - eie = ref1->inode_list;
> - while (eie && eie->next)
> - eie = eie->next;
> - if (eie)
> - eie->next = ref2->inode_list;
> - else
> - ref1->inode_list = ref2->inode_list;
> - ref1->count += ref2->count;
> -
> - list_del(&ref2->list);
> - kmem_cache_free(btrfs_prelim_ref_cache, ref2);
> - cond_resched();
> - }
> -
> - }
> -}
> -
> -/*
> * add all currently queued delayed refs from this head whose seq nr is
> * smaller or equal that seq to the list
> */
> static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
> - struct list_head *prefs, u64 *total_refs,
> + struct preftrees *preftrees, u64 *total_refs,
> u64 inum)
> {
> struct btrfs_delayed_ref_node *node;
> @@ -642,24 +742,30 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
> *total_refs += (node->ref_mod * sgn);
> switch (node->type) {
> case BTRFS_TREE_BLOCK_REF_KEY: {
> + /* NORMAL INDIRECT METADATA backref */
> struct btrfs_delayed_tree_ref *ref;
>
> ref = btrfs_delayed_node_to_tree_ref(node);
> - ret = add_prelim_ref(prefs, ref->root, &op_key,
> - ref->level + 1, 0, node->bytenr,
> - node->ref_mod * sgn, GFP_ATOMIC);
> + ret = add_indirect_ref(preftrees, ref->root, &op_key,
> + ref->level + 1, node->bytenr,
> + node->ref_mod * sgn,
> + GFP_ATOMIC);
> break;
> }
> case BTRFS_SHARED_BLOCK_REF_KEY: {
> + /* SHARED DIRECT METADATA backref */
> struct btrfs_delayed_tree_ref *ref;
>
> ref = btrfs_delayed_node_to_tree_ref(node);
> - ret = add_prelim_ref(prefs, 0, NULL, ref->level + 1,
> +
> + ret = add_direct_ref(preftrees, ref->level + 1,
> ref->parent, node->bytenr,
> - node->ref_mod * sgn, GFP_ATOMIC);
> + node->ref_mod * sgn,
> + GFP_ATOMIC);
> break;
> }
> case BTRFS_EXTENT_DATA_REF_KEY: {
> + /* NORMAL INDIRECT DATA backref */
> struct btrfs_delayed_data_ref *ref;
> ref = btrfs_delayed_node_to_data_ref(node);
>
> @@ -676,17 +782,21 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
> break;
> }
>
> - ret = add_prelim_ref(prefs, ref->root, &key, 0, 0,
> - node->bytenr, node->ref_mod * sgn,
> - GFP_ATOMIC);
> + ret = add_indirect_ref(preftrees, ref->root, &key, 0,
> + node->bytenr,
> + node->ref_mod * sgn,
> + GFP_ATOMIC);
> break;
> }
> case BTRFS_SHARED_DATA_REF_KEY: {
> + /* SHARED DIRECT FULL backref */
> struct btrfs_delayed_data_ref *ref;
>
> ref = btrfs_delayed_node_to_data_ref(node);
> - ret = add_prelim_ref(prefs, 0, NULL, 0, ref->parent,
> - node->bytenr, node->ref_mod * sgn,
> +
> + ret = add_direct_ref(preftrees, 0, ref->parent,
> + node->bytenr,
> + node->ref_mod * sgn,
> GFP_ATOMIC);
> break;
> }
> @@ -704,7 +814,7 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
> * add all inline backrefs for bytenr to the list
> */
> static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
> - int *info_level, struct list_head *prefs,
> + int *info_level, struct preftrees *preftrees,
> u64 *total_refs, u64 inum)
> {
> int ret = 0;
> @@ -760,8 +870,8 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
>
> switch (type) {
> case BTRFS_SHARED_BLOCK_REF_KEY:
> - ret = add_prelim_ref(prefs, 0, NULL, *info_level + 1,
> - offset, bytenr, 1, GFP_NOFS);
> + ret = add_direct_ref(preftrees, *info_level + 1, offset,
> + bytenr, 1, GFP_NOFS);
> break;
> case BTRFS_SHARED_DATA_REF_KEY: {
> struct btrfs_shared_data_ref *sdref;
> @@ -769,14 +879,15 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
>
> sdref = (struct btrfs_shared_data_ref *)(iref + 1);
> count = btrfs_shared_data_ref_count(leaf, sdref);
> - ret = add_prelim_ref(prefs, 0, NULL, 0, offset,
> +
> + ret = add_direct_ref(preftrees, 0, offset,
> bytenr, count, GFP_NOFS);
> break;
> }
> case BTRFS_TREE_BLOCK_REF_KEY:
> - ret = add_prelim_ref(prefs, offset, NULL,
> - *info_level + 1, 0,
> - bytenr, 1, GFP_NOFS);
> + ret = add_indirect_ref(preftrees, offset, NULL,
> + *info_level + 1, bytenr, 1,
> + GFP_NOFS);
> break;
> case BTRFS_EXTENT_DATA_REF_KEY: {
> struct btrfs_extent_data_ref *dref;
> @@ -796,8 +907,9 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
> }
>
> root = btrfs_extent_data_ref_root(leaf, dref);
> - ret = add_prelim_ref(prefs, root, &key, 0, 0,
> - bytenr, count, GFP_NOFS);
> +
> + ret = add_indirect_ref(preftrees, root, &key, 0, bytenr,
> + count, GFP_NOFS);
> break;
> }
> default:
> @@ -816,7 +928,8 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr,
> */
> static int add_keyed_refs(struct btrfs_fs_info *fs_info,
> struct btrfs_path *path, u64 bytenr,
> - int info_level, struct list_head *prefs, u64 inum)
> + int info_level, struct preftrees *preftrees,
> + u64 inum)
> {
> struct btrfs_root *extent_root = fs_info->extent_root;
> int ret;
> @@ -846,26 +959,31 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
>
> switch (key.type) {
> case BTRFS_SHARED_BLOCK_REF_KEY:
> - ret = add_prelim_ref(prefs, 0, NULL, info_level + 1,
> - key.offset, bytenr, 1, GFP_NOFS);
> + /* SHARED DIRECT METADATA backref */
> + ret = add_direct_ref(preftrees, info_level + 1,
> + key.offset, bytenr, 1,
> + GFP_NOFS);
> break;
> case BTRFS_SHARED_DATA_REF_KEY: {
> + /* SHARED DIRECT FULL backref */
> struct btrfs_shared_data_ref *sdref;
> int count;
>
> sdref = btrfs_item_ptr(leaf, slot,
> struct btrfs_shared_data_ref);
> count = btrfs_shared_data_ref_count(leaf, sdref);
> - ret = add_prelim_ref(prefs, 0, NULL, 0, key.offset,
> - bytenr, count, GFP_NOFS);
> + ret = add_direct_ref(preftrees, 0, key.offset, bytenr,
> + count, GFP_NOFS);
> break;
> }
> case BTRFS_TREE_BLOCK_REF_KEY:
> - ret = add_prelim_ref(prefs, key.offset, NULL,
> - info_level + 1, 0,
> - bytenr, 1, GFP_NOFS);
> + /* NORMAL INDIRECT METADATA backref */
> + ret = add_indirect_ref(preftrees, key.offset, NULL,
> + info_level + 1, bytenr, 1,
> + GFP_NOFS);
> break;
> case BTRFS_EXTENT_DATA_REF_KEY: {
> + /* NORMAL INDIRECT DATA backref */
> struct btrfs_extent_data_ref *dref;
> int count;
> u64 root;
> @@ -884,8 +1002,8 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info,
> }
>
> root = btrfs_extent_data_ref_root(leaf, dref);
> - ret = add_prelim_ref(prefs, root, &key, 0, 0,
> - bytenr, count, GFP_NOFS);
> + ret = add_indirect_ref(preftrees, root, &key, 0, bytenr,
> + count, GFP_NOFS);
> break;
> }
> default:
> @@ -926,14 +1044,15 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
> struct btrfs_delayed_ref_head *head;
> int info_level = 0;
> int ret;
> - struct list_head prefs_delayed;
> - struct list_head prefs;
> struct prelim_ref *ref;
> + struct rb_node *node;
> struct extent_inode_elem *eie = NULL;
> + /* total of both direct AND indirect refs! */
> u64 total_refs = 0;
> -
> - INIT_LIST_HEAD(&prefs);
> - INIT_LIST_HEAD(&prefs_delayed);
> + struct preftrees preftrees = {
> + .direct = PREFTREE_INIT,
> + .indirect = PREFTREE_INIT
> + };
>
> key.objectid = bytenr;
> key.offset = (u64)-1;
> @@ -996,15 +1115,18 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
> goto again;
> }
> spin_unlock(&delayed_refs->lock);
> - ret = add_delayed_refs(head, time_seq,
> - &prefs_delayed, &total_refs,
> - inum);
> + ret = add_delayed_refs(head, time_seq, &preftrees,
> + &total_refs, inum);
> mutex_unlock(&head->mutex);
> if (ret)
> goto out;
> } else {
> spin_unlock(&delayed_refs->lock);
> }
> +
> + /*
> + * TODO - implement short circuit for BACKREF_FOUND_SHARED
> + */
Please don't add TODOs to code, they tend to stick there indefinetelly.
Although this is not the case in your patchset as it gets removed later,
we don't want to encourage such practice.
> }
>
> if (path->slots[0]) {
> @@ -1019,35 +1141,41 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
> (key.type == BTRFS_EXTENT_ITEM_KEY ||
> key.type == BTRFS_METADATA_ITEM_KEY)) {
> ret = add_inline_refs(path, bytenr, &info_level,
> - &prefs, &total_refs, inum);
> + &preftrees, &total_refs, inum);
> if (ret)
> goto out;
> ret = add_keyed_refs(fs_info, path, bytenr, info_level,
> - &prefs, inum);
> + &preftrees, inum);
> if (ret)
> goto out;
> }
> }
> - btrfs_release_path(path);
>
> - list_splice_init(&prefs_delayed, &prefs);
> + btrfs_release_path(path);
>
> - ret = add_missing_keys(fs_info, &prefs);
> + ret = add_missing_keys(fs_info, &preftrees);
> if (ret)
> goto out;
>
> - merge_refs(&prefs, MERGE_IDENTICAL_KEYS);
> -
> - ret = resolve_indirect_refs(fs_info, path, time_seq, &prefs,
> + ret = resolve_indirect_refs(fs_info, path, time_seq, &preftrees,
> extent_item_pos, total_refs,
> root_objectid);
> if (ret)
> goto out;
>
> - merge_refs(&prefs, MERGE_IDENTICAL_PARENTS);
> + WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect.root));
>
> - while (!list_empty(&prefs)) {
> - ref = list_first_entry(&prefs, struct prelim_ref, list);
> + /*
> + * This walks the tree of merged and resolved refs. Tree blocks are
> + * read in as needed. Unique entries are added to the ulist, and
> + * the list of found roots is updated.
> + *
> + * We release the entire tree in one go before returning.
> + */
> + node = rb_first(&preftrees.direct.root);
> + while (node) {
> + ref = rb_entry(node, struct prelim_ref, rbnode);
> + node = rb_next(&ref->rbnode);
> WARN_ON(ref->count < 0);
> if (roots && ref->count && ref->root_id && ref->parent == 0) {
> if (root_objectid && ref->root_id != root_objectid) {
> @@ -1101,23 +1229,14 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
> }
> eie = NULL;
> }
> - list_del(&ref->list);
> - kmem_cache_free(btrfs_prelim_ref_cache, ref);
> }
>
> out:
> btrfs_free_path(path);
> - while (!list_empty(&prefs)) {
> - ref = list_first_entry(&prefs, struct prelim_ref, list);
> - list_del(&ref->list);
> - kmem_cache_free(btrfs_prelim_ref_cache, ref);
> - }
> - while (!list_empty(&prefs_delayed)) {
> - ref = list_first_entry(&prefs_delayed, struct prelim_ref,
> - list);
> - list_del(&ref->list);
> - kmem_cache_free(btrfs_prelim_ref_cache, ref);
> - }
> +
> + prelim_release(&preftrees.direct);
> + prelim_release(&preftrees.indirect);
> +
> if (ret < 0)
> free_inode_elem_list(eie);
> return ret;
Overall, the patch appears big but I don't see a good way to split it,
only to introduce the helpers separately, not much else seems to be
independent.
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 00/13] use rbtrees for preliminary backrefs
2017-06-20 16:06 [PATCH 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (12 preceding siblings ...)
2017-06-20 16:06 ` [PATCH 13/13] btrfs: clean up extraneous computations in add_delayed_refs Edmund Nadolski
@ 2017-06-27 17:06 ` David Sterba
13 siblings, 0 replies; 23+ messages in thread
From: David Sterba @ 2017-06-27 17:06 UTC (permalink / raw)
To: Edmund Nadolski; +Cc: linux-btrfs
On Tue, Jun 20, 2017 at 10:06:40AM -0600, Edmund Nadolski wrote:
> This patch series attempts to improve the performance of backref
> searches by changing the prelim_refs implementation to use
> rbtrees instead of lists. This also aims to reduce the soft
> lockup occurences that can result when a backref search consumes
> too much cpu time.
>
> Test runs of btrfs/130 show an improvement in the overall
> run time of the test (shown below in seconds) as a function of
> the number of extents:
>
> nr_extents: 256 512 640 1024 2048
> ------------+-------+-----+-------+-------+------
> unpatched: 20 186 375 2204 40419
> patched: 12 93 203 1060 22007
About 50% improvement is really good.
> (Note, the current default value for nr_extents in btrfs/130 is
> 4096, which takes a very long time to complete.)
>
> Edmund Nadolski (6):
> btrfs: btrfs_check_shared should manage its own transaction
> btrfs: remove ref_tree implementation from backref.c
> btrfs: convert prelimary reference tracking to use rbtrees
> btrfs: add cond_resched() calls when resolving backrefs
> btrfs: allow backref search checks for shared extents
> btrfs: clean up extraneous computations in add_delayed_refs
>
> Jeff Mahoney (7):
> btrfs: struct-funcs, constify readers
> btrfs: constify tracepoint arguments
> btrfs: backref, constify some arguments
> btrfs: backref, add unode_aux_to_inode_list helper
> btrfs: backref, cleanup __ namespace abuse
> btrfs: add a node counter to each of the rbtrees
> btrfs: backref, add tracepoints for prelim_ref insertion and merging
Some of the patches are preparatory or cleanups that can be applied
independently, but for further patchset revisions please keep them all
so you don't need to depend on the current development patche queue.
I'll get to merging them soon and will let you know.
Per Jeff's comment under patch 8/13, I will not add thse patches to
for-next yet, please address the issues and resend.
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees
2017-06-26 17:07 ` Jeff Mahoney
@ 2017-06-27 20:09 ` Jeff Mahoney
2017-06-27 21:11 ` [PATCH] btrfs: backref, properly iterate the missing keys Jeff Mahoney
0 siblings, 1 reply; 23+ messages in thread
From: Jeff Mahoney @ 2017-06-27 20:09 UTC (permalink / raw)
To: Edmund Nadolski, linux-btrfs
[-- Attachment #1.1: Type: text/plain, Size: 3043 bytes --]
On 6/26/17 1:07 PM, Jeff Mahoney wrote:
> On 6/20/17 12:06 PM, Edmund Nadolski wrote:
>> It's been known for a while that the use of multiple lists
>> that are periodically merged was an algorithmic problem within
>> btrfs. There are several workloads that don't complete in any
>> reasonable amount of time (e.g. btrfs/130) and others that cause
>> soft lockups.
>>
>> The solution is to use a pair of rbtrees that do insertion merging
>> for both indirect and direct refs, with the former converting
>> refs into the latter. The result is a btrfs/130 workload that
>> used to take several hours now takes about half of that. This
>> runtime still isn't acceptable and a future patch will address that
>> by moving the rbtrees higher in the stack so the lookups can be
>> shared across multiple calls to find_parent_nodes.
>>
>> Signed-off-by: Edmund Nadolski <enadolski@suse.com>
>> Signed-off-by: Jeff Mahoney <jeffm@suse.com>
> [...]
>
>> @@ -504,37 +665,22 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
>> return ret;
>> }
>>
>> -static inline int ref_for_same_block(struct prelim_ref *ref1,
>> - struct prelim_ref *ref2)
>> -{
>> - if (ref1->level != ref2->level)
>> - return 0;
>> - if (ref1->root_id != ref2->root_id)
>> - return 0;
>> - if (ref1->key_for_search.type != ref2->key_for_search.type)
>> - return 0;
>> - if (ref1->key_for_search.objectid != ref2->key_for_search.objectid)
>> - return 0;
>> - if (ref1->key_for_search.offset != ref2->key_for_search.offset)
>> - return 0;
>> - if (ref1->parent != ref2->parent)
>> - return 0;
>> -
>> - return 1;
>> -}
>> -
>> /*
>> * read tree blocks and add keys where required.
>> */
>> static int add_missing_keys(struct btrfs_fs_info *fs_info,
>> - struct list_head *head)
>> + struct preftrees *preftrees)
>> {
>> struct prelim_ref *ref;
>> struct extent_buffer *eb;
>> + struct rb_node *node = rb_first(&preftrees->indirect.root);
>> +
>> + while (node) {
>> + ref = rb_entry(node, struct prelim_ref, rbnode);
>> + node = rb_next(&ref->rbnode);
>> + if (WARN(ref->parent, "BUG: direct ref found in indirect tree"))
>> + return -EINVAL;
>>
>> - list_for_each_entry(ref, head, list) {
>> - if (ref->parent)
>> - continue;
>> if (ref->key_for_search.type)
>> continue;
>> BUG_ON(!ref->wanted_disk_byte);
>
> Hi Ed -
>
> I missed this in earlier review, but this can't work. We're modifying
> the ref in a way that the comparator will care about -- so the node
> would move in the tree.
>
> It's not a fatal flaw and, in fact, leaves us an opening to fix a
> separate locking issue.
Ed and I discussed this offline. It turns out that this is a code bug
but not a functional bug. Once we hit add_missing_keys, we don't do any
more inserts or searches. We only iterate over every node and remove
each as we go, so the tree order doesn't matter. I'll post a fix shortly.
-Jeff
--
Jeff Mahoney
SUSE Labs
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees
2017-06-27 16:49 ` [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees David Sterba
@ 2017-06-27 21:10 ` Jeff Mahoney
2017-07-04 17:02 ` David Sterba
0 siblings, 1 reply; 23+ messages in thread
From: Jeff Mahoney @ 2017-06-27 21:10 UTC (permalink / raw)
To: dsterba, Edmund Nadolski, linux-btrfs
[-- Attachment #1.1: Type: text/plain, Size: 5812 bytes --]
On 6/27/17 12:49 PM, David Sterba wrote:
> On Tue, Jun 20, 2017 at 10:06:48AM -0600, Edmund Nadolski wrote:
>> It's been known for a while that the use of multiple lists
>> that are periodically merged was an algorithmic problem within
>> btrfs. There are several workloads that don't complete in any
>> reasonable amount of time (e.g. btrfs/130) and others that cause
>> soft lockups.
>>
>> The solution is to use a pair of rbtrees that do insertion merging
>> for both indirect and direct refs, with the former converting
>> refs into the latter. The result is a btrfs/130 workload that
>> used to take several hours now takes about half of that. This
>> runtime still isn't acceptable and a future patch will address that
>> by moving the rbtrees higher in the stack so the lookups can be
>> shared across multiple calls to find_parent_nodes.
>>
>> Signed-off-by: Edmund Nadolski <enadolski@suse.com>
>> Signed-off-by: Jeff Mahoney <jeffm@suse.com>
>> ---
>> fs/btrfs/backref.c | 415 ++++++++++++++++++++++++++++++++++-------------------
>> 1 file changed, 267 insertions(+), 148 deletions(-)
>>
>> diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
>> index 0d1e7cb..daae7b6 100644
>> --- a/fs/btrfs/backref.c
>> +++ b/fs/btrfs/backref.c
>> @@ -129,7 +129,7 @@ static int find_extent_in_eb(const struct extent_buffer *eb,
>> * this structure records all encountered refs on the way up to the root
>> */
>> struct prelim_ref {
>> - struct list_head list;
>> + struct rb_node rbnode;
>> u64 root_id;
>> struct btrfs_key key_for_search;
>> int level;
>> @@ -139,6 +139,17 @@ struct prelim_ref {
>> u64 wanted_disk_byte;
>> };
>>
>> +struct preftree {
>> + struct rb_root root;
>> +};
>> +
>> +#define PREFTREE_INIT { .root = RB_ROOT }
>> +
>> +struct preftrees {
>> + struct preftree direct; /* BTRFS_SHARED_[DATA|BLOCK]_REF_KEY */
>> + struct preftree indirect; /* BTRFS_[TREE_BLOCK|EXTENT_DATA]_REF_KEY */
>> +};
>> +
>> static struct kmem_cache *btrfs_prelim_ref_cache;
>>
>> int __init btrfs_prelim_ref_init(void)
>> @@ -158,6 +169,108 @@ void btrfs_prelim_ref_exit(void)
>> kmem_cache_destroy(btrfs_prelim_ref_cache);
>> }
>>
>> +static void release_pref(struct prelim_ref *ref)
>> +{
>> + kmem_cache_free(btrfs_prelim_ref_cache, ref);
>
> This is a bit confusing, 'release' in btrfs code is used to release the
> resources but not to actually free the memory. See eg.
> btrfs_release_path and btrfs_free_path. As the helper is trivial and I
> don't see any other additions to it in the followup patches, I suggest
> to drop and opencode it.
I don't mind renaming it to free_pref, but free_pref(ref) is a whole lot
easier to read and write than the alternative.
>> @@ -429,38 +560,58 @@ unode_aux_to_inode_list(struct ulist_node *node)
>> }
>>
>> /*
>> - * resolve all indirect backrefs from the list
>> + * We maintain two separate rbtrees: one for indirect refs and one for
>> + * direct refs. Each tree does merge on insertion. Once all of the
>> + * refs have been located, we iterate over the indirect ref tree, resolve
>> + * each reference and remove it from the indirect tree, and then insert
>> + * the resolved reference into the direct tree, merging there too.
>> + *
>> + * New backrefs (i.e., for parent nodes) are added to the direct/indirect
>> + * rbtrees as they are encountered. The new, indirect backrefs are
>> + * resolved as above.
>> */
>> static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
>> struct btrfs_path *path, u64 time_seq,
>> - struct list_head *head,
>> + struct preftrees *preftrees,
>> const u64 *extent_item_pos, u64 total_refs,
>> u64 root_objectid)
>> {
>> int err;
>> int ret = 0;
>> - struct prelim_ref *ref;
>> - struct prelim_ref *ref_safe;
>> - struct prelim_ref *new_ref;
>> struct ulist *parents;
>> struct ulist_node *node;
>> struct ulist_iterator uiter;
>> + struct rb_node *rnode;
>>
>> parents = ulist_alloc(GFP_NOFS);
>> if (!parents)
>> return -ENOMEM;
>>
>> /*
>> - * _safe allows us to insert directly after the current item without
>> - * iterating over the newly inserted items.
>> - * we're also allowed to re-assign ref during iteration.
>> + * We could trade memory usage for performance here by iterating
>> + * the tree, allocating new refs for each insertion, and then
>> + * freeing the entire indirect tree when we're done. In some test
>> + * cases, the tree can grow quite large (~200k objects).
>> */
>> - list_for_each_entry_safe(ref, ref_safe, head, list) {
>> - if (ref->parent) /* already direct */
>> - continue;
>> - if (ref->count == 0)
>> + while ((rnode = rb_first(&preftrees->indirect.root))) {
>> + struct prelim_ref *ref;
>> +
>> + ref = rb_entry(rnode, struct prelim_ref, rbnode);
>> + if (WARN(ref->parent,
>> + "BUG: direct ref found in indirect tree")) {
>
> Is this meant as an assertion or do you expect this could also happen
> during normal operation?
This one was mine.
It's not meant to be countered in normal operation, but I've been trying
to (and not always succeeding at) taking Linus's advice about gracefully
recovering from errors rather than crashing. Our other two tools are
BUG_ON, which will crash the kernel or ASSERT, which will crash the
kernel only if the check is enabled and happily break otherwise.
> Overall, the patch appears big but I don't see a good way to split it,
> only to introduce the helpers separately, not much else seems to be
> independent.
Is that a request to split the helpers out or an observation that doing
so would be the only reason to make it smaller?
-Jeff
--
Jeff Mahoney
SUSE Labs
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]
^ permalink raw reply [flat|nested] 23+ messages in thread
* [PATCH] btrfs: backref, properly iterate the missing keys
2017-06-27 20:09 ` Jeff Mahoney
@ 2017-06-27 21:11 ` Jeff Mahoney
0 siblings, 0 replies; 23+ messages in thread
From: Jeff Mahoney @ 2017-06-27 21:11 UTC (permalink / raw)
To: linux-btrfs; +Cc: Edmund Nadolski, David Sterba
[This should probably be rolled into Patch 8].
We iterate over the indirect tree looking for refs that don't have
key associated with them, look them up, and update the ref with the
resolved key. The problem is that when we resolve the key, we've
changed where the ref would be located in the tree, which means
searches and insertions would fail.
The good news is that it's not a visible bug since we don't actually search
for or insert new items into the tree at this point.
This patch uses a separate tree for those refs, resolves them, and inserts
them into the indirect tree. This has the benefit of letting us skip
the refs that don't need any attention and this is used in the next patch.
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
fs/btrfs/backref.c | 37 +++++++++++++++++++++++++------------
1 file changed, 25 insertions(+), 12 deletions(-)
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -132,6 +132,7 @@ struct preftree {
struct preftrees {
struct preftree direct; /* BTRFS_SHARED_[DATA|BLOCK]_REF_KEY */
struct preftree indirect; /* BTRFS_[TREE_BLOCK|EXTENT_DATA]_REF_KEY */
+ struct preftree indirect_missing_keys;
};
/*
@@ -406,8 +407,11 @@ static int add_indirect_ref(const struct
u64 wanted_disk_byte, int count,
struct share_check *sc, gfp_t gfp_mask)
{
- return add_prelim_ref(fs_info, &preftrees->indirect, root_id, key,
- level, 0, wanted_disk_byte, count, sc, gfp_mask);
+ struct preftree *tree = &preftrees->indirect;
+ if (!key)
+ tree = &preftrees->indirect_missing_keys;
+ return add_prelim_ref(fs_info, tree, root_id, key, level, 0,
+ wanted_disk_byte, count, sc, gfp_mask);
}
static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
@@ -707,22 +711,25 @@ static int add_missing_keys(struct btrfs
{
struct prelim_ref *ref;
struct extent_buffer *eb;
- struct rb_node *node = rb_first(&preftrees->indirect.root);
+ struct preftree *tree = &preftrees->indirect_missing_keys;
+ struct rb_node *node;
- while (node) {
+ while ((node = rb_first(&tree->root))) {
ref = rb_entry(node, struct prelim_ref, rbnode);
- node = rb_next(&ref->rbnode);
- BUG_ON(ref->parent); /* should not be a direct ref */
+ rb_erase(node, &tree->root);
- if (ref->key_for_search.type)
- continue;
+ BUG_ON(ref->parent); /* should not be a direct ref */
+ BUG_ON(ref->key_for_search.type);
BUG_ON(!ref->wanted_disk_byte);
+
eb = read_tree_block(fs_info->tree_root, ref->wanted_disk_byte,
0);
if (IS_ERR(eb)) {
+ release_pref(ref);
return PTR_ERR(eb);
} else if (!extent_buffer_uptodate(eb)) {
free_extent_buffer(eb);
+ release_pref(ref);
return -EIO;
}
btrfs_tree_read_lock(eb);
@@ -749,12 +756,15 @@ static int add_delayed_refs(const struct
struct btrfs_delayed_ref_node *node;
struct btrfs_delayed_extent_op *extent_op = head->extent_op;
struct btrfs_key key;
- struct btrfs_key op_key = {0};
+ struct btrfs_key tmp_op_key;
+ struct btrfs_key *op_key = NULL;
int count;
int ret = 0;
- if (extent_op && extent_op->update_key)
- btrfs_disk_key_to_cpu(&op_key, &extent_op->key);
+ if (extent_op && extent_op->update_key) {
+ btrfs_disk_key_to_cpu(&tmp_op_key, &extent_op->key);
+ op_key = &tmp_op_key;
+ }
spin_lock(&head->lock);
list_for_each_entry(node, &head->ref_list, list) {
@@ -783,7 +793,7 @@ static int add_delayed_refs(const struct
ref = btrfs_delayed_node_to_tree_ref(node);
ret = add_indirect_ref(fs_info, preftrees, ref->root,
- &op_key, ref->level + 1,
+ op_key, ref->level + 1,
node->bytenr, count, sc,
GFP_ATOMIC);
break;
@@ -1206,6 +1216,8 @@ again:
if (ret)
goto out;
+ WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect_missing_keys.root));
+
ret = resolve_indirect_refs(fs_info, path, time_seq, &preftrees,
extent_item_pos, total_refs, sc);
if (ret)
@@ -1289,6 +1301,7 @@ out:
prelim_release(&preftrees.direct);
prelim_release(&preftrees.indirect);
+ prelim_release(&preftrees.indirect_missing_keys);
if (ret < 0)
free_inode_elem_list(eie);
^ permalink raw reply [flat|nested] 23+ messages in thread
* Re: [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees
2017-06-27 21:10 ` Jeff Mahoney
@ 2017-07-04 17:02 ` David Sterba
0 siblings, 0 replies; 23+ messages in thread
From: David Sterba @ 2017-07-04 17:02 UTC (permalink / raw)
To: Jeff Mahoney; +Cc: dsterba, Edmund Nadolski, linux-btrfs
On Tue, Jun 27, 2017 at 05:10:58PM -0400, Jeff Mahoney wrote:
> On 6/27/17 12:49 PM, David Sterba wrote:
> > On Tue, Jun 20, 2017 at 10:06:48AM -0600, Edmund Nadolski wrote:
> >> It's been known for a while that the use of multiple lists
> >> that are periodically merged was an algorithmic problem within
> >> btrfs. There are several workloads that don't complete in any
> >> reasonable amount of time (e.g. btrfs/130) and others that cause
> >> soft lockups.
> >>
> >> The solution is to use a pair of rbtrees that do insertion merging
> >> for both indirect and direct refs, with the former converting
> >> refs into the latter. The result is a btrfs/130 workload that
> >> used to take several hours now takes about half of that. This
> >> runtime still isn't acceptable and a future patch will address that
> >> by moving the rbtrees higher in the stack so the lookups can be
> >> shared across multiple calls to find_parent_nodes.
> >>
> >> Signed-off-by: Edmund Nadolski <enadolski@suse.com>
> >> Signed-off-by: Jeff Mahoney <jeffm@suse.com>
> >> ---
> >> fs/btrfs/backref.c | 415 ++++++++++++++++++++++++++++++++++-------------------
> >> 1 file changed, 267 insertions(+), 148 deletions(-)
> >>
> >> diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
> >> index 0d1e7cb..daae7b6 100644
> >> --- a/fs/btrfs/backref.c
> >> +++ b/fs/btrfs/backref.c
> >> @@ -129,7 +129,7 @@ static int find_extent_in_eb(const struct extent_buffer *eb,
> >> * this structure records all encountered refs on the way up to the root
> >> */
> >> struct prelim_ref {
> >> - struct list_head list;
> >> + struct rb_node rbnode;
> >> u64 root_id;
> >> struct btrfs_key key_for_search;
> >> int level;
> >> @@ -139,6 +139,17 @@ struct prelim_ref {
> >> u64 wanted_disk_byte;
> >> };
> >>
> >> +struct preftree {
> >> + struct rb_root root;
> >> +};
> >> +
> >> +#define PREFTREE_INIT { .root = RB_ROOT }
> >> +
> >> +struct preftrees {
> >> + struct preftree direct; /* BTRFS_SHARED_[DATA|BLOCK]_REF_KEY */
> >> + struct preftree indirect; /* BTRFS_[TREE_BLOCK|EXTENT_DATA]_REF_KEY */
> >> +};
> >> +
> >> static struct kmem_cache *btrfs_prelim_ref_cache;
> >>
> >> int __init btrfs_prelim_ref_init(void)
> >> @@ -158,6 +169,108 @@ void btrfs_prelim_ref_exit(void)
> >> kmem_cache_destroy(btrfs_prelim_ref_cache);
> >> }
> >>
> >> +static void release_pref(struct prelim_ref *ref)
> >> +{
> >> + kmem_cache_free(btrfs_prelim_ref_cache, ref);
> >
> > This is a bit confusing, 'release' in btrfs code is used to release the
> > resources but not to actually free the memory. See eg.
> > btrfs_release_path and btrfs_free_path. As the helper is trivial and I
> > don't see any other additions to it in the followup patches, I suggest
> > to drop and opencode it.
>
> I don't mind renaming it to free_pref, but free_pref(ref) is a whole lot
> easier to read and write than the alternative.
>
> >> @@ -429,38 +560,58 @@ unode_aux_to_inode_list(struct ulist_node *node)
> >> }
> >>
> >> /*
> >> - * resolve all indirect backrefs from the list
> >> + * We maintain two separate rbtrees: one for indirect refs and one for
> >> + * direct refs. Each tree does merge on insertion. Once all of the
> >> + * refs have been located, we iterate over the indirect ref tree, resolve
> >> + * each reference and remove it from the indirect tree, and then insert
> >> + * the resolved reference into the direct tree, merging there too.
> >> + *
> >> + * New backrefs (i.e., for parent nodes) are added to the direct/indirect
> >> + * rbtrees as they are encountered. The new, indirect backrefs are
> >> + * resolved as above.
> >> */
> >> static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
> >> struct btrfs_path *path, u64 time_seq,
> >> - struct list_head *head,
> >> + struct preftrees *preftrees,
> >> const u64 *extent_item_pos, u64 total_refs,
> >> u64 root_objectid)
> >> {
> >> int err;
> >> int ret = 0;
> >> - struct prelim_ref *ref;
> >> - struct prelim_ref *ref_safe;
> >> - struct prelim_ref *new_ref;
> >> struct ulist *parents;
> >> struct ulist_node *node;
> >> struct ulist_iterator uiter;
> >> + struct rb_node *rnode;
> >>
> >> parents = ulist_alloc(GFP_NOFS);
> >> if (!parents)
> >> return -ENOMEM;
> >>
> >> /*
> >> - * _safe allows us to insert directly after the current item without
> >> - * iterating over the newly inserted items.
> >> - * we're also allowed to re-assign ref during iteration.
> >> + * We could trade memory usage for performance here by iterating
> >> + * the tree, allocating new refs for each insertion, and then
> >> + * freeing the entire indirect tree when we're done. In some test
> >> + * cases, the tree can grow quite large (~200k objects).
> >> */
> >> - list_for_each_entry_safe(ref, ref_safe, head, list) {
> >> - if (ref->parent) /* already direct */
> >> - continue;
> >> - if (ref->count == 0)
> >> + while ((rnode = rb_first(&preftrees->indirect.root))) {
> >> + struct prelim_ref *ref;
> >> +
> >> + ref = rb_entry(rnode, struct prelim_ref, rbnode);
> >> + if (WARN(ref->parent,
> >> + "BUG: direct ref found in indirect tree")) {
> >
> > Is this meant as an assertion or do you expect this could also happen
> > during normal operation?
>
> This one was mine.
>
> It's not meant to be countered in normal operation, but I've been trying
> to (and not always succeeding at) taking Linus's advice about gracefully
> recovering from errors rather than crashing. Our other two tools are
> BUG_ON, which will crash the kernel or ASSERT, which will crash the
> kernel only if the check is enabled and happily break otherwise.
Ok, so WARN is fine here.
> > Overall, the patch appears big but I don't see a good way to split it,
> > only to introduce the helpers separately, not much else seems to be
> > independent.
>
> Is that a request to split the helpers out or an observation that doing
> so would be the only reason to make it smaller?
That was my impression from the review, if there's more code in one
patch, it takes time to see which parts are important. So if the helpers
are separated out, it (subjectively) reduces the cognitive load. As
there was no clear way how to split the patch it was not a request but a
feedback from the review side.
^ permalink raw reply [flat|nested] 23+ messages in thread
end of thread, other threads:[~2017-07-04 17:03 UTC | newest]
Thread overview: 23+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-06-20 16:06 [PATCH 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
2017-06-20 16:06 ` [PATCH 01/13] btrfs: struct-funcs, constify readers Edmund Nadolski
2017-06-20 16:06 ` [PATCH 02/13] btrfs: constify tracepoint arguments Edmund Nadolski
2017-06-20 16:06 ` [PATCH 03/13] btrfs: backref, constify some arguments Edmund Nadolski
2017-06-20 16:06 ` [PATCH 04/13] btrfs: backref, add unode_aux_to_inode_list helper Edmund Nadolski
2017-06-20 16:06 ` [PATCH 05/13] btrfs: backref, cleanup __ namespace abuse Edmund Nadolski
2017-06-20 16:06 ` [PATCH 06/13] btrfs: btrfs_check_shared should manage its own transaction Edmund Nadolski
2017-06-27 15:40 ` David Sterba
2017-06-20 16:06 ` [PATCH 07/13] btrfs: remove ref_tree implementation from backref.c Edmund Nadolski
2017-06-27 15:48 ` David Sterba
2017-06-20 16:06 ` [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees Edmund Nadolski
2017-06-26 17:07 ` Jeff Mahoney
2017-06-27 20:09 ` Jeff Mahoney
2017-06-27 21:11 ` [PATCH] btrfs: backref, properly iterate the missing keys Jeff Mahoney
2017-06-27 16:49 ` [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees David Sterba
2017-06-27 21:10 ` Jeff Mahoney
2017-07-04 17:02 ` David Sterba
2017-06-20 16:06 ` [PATCH 09/13] btrfs: add a node counter to each of the rbtrees Edmund Nadolski
2017-06-20 16:06 ` [PATCH 10/13] btrfs: backref, add tracepoints for prelim_ref insertion and merging Edmund Nadolski
2017-06-20 16:06 ` [PATCH 11/13] btrfs: add cond_resched() calls when resolving backrefs Edmund Nadolski
2017-06-20 16:06 ` [PATCH 12/13] btrfs: allow backref search checks for shared extents Edmund Nadolski
2017-06-20 16:06 ` [PATCH 13/13] btrfs: clean up extraneous computations in add_delayed_refs Edmund Nadolski
2017-06-27 17:06 ` [PATCH 00/13] use rbtrees for preliminary backrefs David Sterba
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.