* [PATCH v2 00/13] use rbtrees for preliminary backrefs
@ 2017-06-29 3:56 Edmund Nadolski
2017-06-29 3:56 ` [PATCH v2 01/13] btrfs: struct-funcs, constify readers Edmund Nadolski
` (13 more replies)
0 siblings, 14 replies; 22+ messages in thread
From: Edmund Nadolski @ 2017-06-29 3:56 UTC (permalink / raw)
To: enadolski, jeffm, linux-btrfs, lufq.fnst
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.)
Changes for v2:
Patch 06/13:
- Added changelog description.
Patch 07/13:
- Updated changelog description.
- Removed 'TODO' comment.
Patch 08/13:
- Added code for proper iteration of missing keys. This adds
a third rbtree (.indirect_missing_keys in struct preftrees)
plus the requisite code in add_prelim_ref(), add_missing_keys(),
resolve_indirect_refs(), and find_parent_nodes().
- Rename release_pref() to free_pref().
- Replace WARN() with BUG_ON().
- Remove 'TODO' comments and the unused 'merge_mode' enum.
The other patches have no functional changes. Some have diff
context changes due to the above modifications.
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 | 1067 ++++++++++++++++++------------------------
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, 767 insertions(+), 835 deletions(-)
--
2.10.2
^ permalink raw reply [flat|nested] 22+ messages in thread
* [PATCH v2 01/13] btrfs: struct-funcs, constify readers
2017-06-29 3:56 [PATCH v2 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
@ 2017-06-29 3:56 ` Edmund Nadolski
2017-06-29 3:56 ` [PATCH v2 02/13] btrfs: constify tracepoint arguments Edmund Nadolski
` (12 subsequent siblings)
13 siblings, 0 replies; 22+ messages in thread
From: Edmund Nadolski @ 2017-06-29 3:56 UTC (permalink / raw)
To: enadolski, jeffm, linux-btrfs, lufq.fnst
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 5bdd3666..6d9ec36 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -1435,7 +1435,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;
};
@@ -1469,18 +1469,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); \
@@ -1492,7 +1493,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)); \
@@ -1503,7 +1505,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); \
@@ -1518,9 +1521,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; \
} \
@@ -1532,7 +1535,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); \
} \
@@ -1857,7 +1860,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,
@@ -1886,28 +1889,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);
@@ -1943,8 +1946,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);
@@ -1952,7 +1955,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);
}
@@ -1964,8 +1967,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);
@@ -1973,7 +1976,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);
}
@@ -2000,25 +2003,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);
@@ -2050,7 +2053,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;
}
@@ -2069,7 +2072,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;
@@ -2089,12 +2092,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;
}
@@ -2128,12 +2131,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;
}
@@ -2190,51 +2193,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));
@@ -2254,7 +2257,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));
@@ -2322,7 +2325,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);
/*
@@ -2337,8 +2340,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);
@@ -2363,7 +2366,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;
}
@@ -2397,8 +2400,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;
}
@@ -2406,9 +2410,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;
@@ -2430,8 +2434,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 29a6111..3c8250e 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -5405,9 +5405,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;
@@ -5436,9 +5435,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;
@@ -5478,10 +5477,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;
@@ -5515,9 +5514,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 aeafdb3..327dd2f 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] 22+ messages in thread
* [PATCH v2 02/13] btrfs: constify tracepoint arguments
2017-06-29 3:56 [PATCH v2 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
2017-06-29 3:56 ` [PATCH v2 01/13] btrfs: struct-funcs, constify readers Edmund Nadolski
@ 2017-06-29 3:56 ` Edmund Nadolski
2017-06-29 3:56 ` [PATCH v2 03/13] btrfs: backref, constify some arguments Edmund Nadolski
` (11 subsequent siblings)
13 siblings, 0 replies; 22+ messages in thread
From: Edmund Nadolski @ 2017-06-29 3:56 UTC (permalink / raw)
To: enadolski, jeffm, linux-btrfs, lufq.fnst
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] 22+ messages in thread
* [PATCH v2 03/13] btrfs: backref, constify some arguments
2017-06-29 3:56 [PATCH v2 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
2017-06-29 3:56 ` [PATCH v2 01/13] btrfs: struct-funcs, constify readers Edmund Nadolski
2017-06-29 3:56 ` [PATCH v2 02/13] btrfs: constify tracepoint arguments Edmund Nadolski
@ 2017-06-29 3:56 ` Edmund Nadolski
2017-06-29 3:56 ` [PATCH v2 04/13] btrfs: backref, add unode_aux_to_inode_list helper Edmund Nadolski
` (10 subsequent siblings)
13 siblings, 0 replies; 22+ messages in thread
From: Edmund Nadolski @ 2017-06-29 3:56 UTC (permalink / raw)
To: enadolski, jeffm, linux-btrfs, lufq.fnst
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] 22+ messages in thread
* [PATCH v2 04/13] btrfs: backref, add unode_aux_to_inode_list helper
2017-06-29 3:56 [PATCH v2 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (2 preceding siblings ...)
2017-06-29 3:56 ` [PATCH v2 03/13] btrfs: backref, constify some arguments Edmund Nadolski
@ 2017-06-29 3:56 ` Edmund Nadolski
2017-06-29 3:56 ` [PATCH v2 05/13] btrfs: backref, cleanup __ namespace abuse Edmund Nadolski
` (9 subsequent siblings)
13 siblings, 0 replies; 22+ messages in thread
From: Edmund Nadolski @ 2017-06-29 3:56 UTC (permalink / raw)
To: enadolski, jeffm, linux-btrfs, lufq.fnst
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] 22+ messages in thread
* [PATCH v2 05/13] btrfs: backref, cleanup __ namespace abuse
2017-06-29 3:56 [PATCH v2 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (3 preceding siblings ...)
2017-06-29 3:56 ` [PATCH v2 04/13] btrfs: backref, add unode_aux_to_inode_list helper Edmund Nadolski
@ 2017-06-29 3:56 ` Edmund Nadolski
2017-06-29 3:56 ` [PATCH v2 06/13] btrfs: btrfs_check_shared should manage its own transaction Edmund Nadolski
` (8 subsequent siblings)
13 siblings, 0 replies; 22+ messages in thread
From: Edmund Nadolski @ 2017-06-29 3:56 UTC (permalink / raw)
To: enadolski, jeffm, linux-btrfs, lufq.fnst
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] 22+ messages in thread
* [PATCH v2 06/13] btrfs: btrfs_check_shared should manage its own transaction
2017-06-29 3:56 [PATCH v2 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (4 preceding siblings ...)
2017-06-29 3:56 ` [PATCH v2 05/13] btrfs: backref, cleanup __ namespace abuse Edmund Nadolski
@ 2017-06-29 3:56 ` Edmund Nadolski
2017-07-10 16:51 ` David Sterba
2017-06-29 3:56 ` [PATCH v2 07/13] btrfs: remove ref_tree implementation from backref.c Edmund Nadolski
` (7 subsequent siblings)
13 siblings, 1 reply; 22+ messages in thread
From: Edmund Nadolski @ 2017-06-29 3:56 UTC (permalink / raw)
To: enadolski, jeffm, linux-btrfs, lufq.fnst
Commit afce772e87c3 ("btrfs: fix check_shared for fiemap ioctl") added
transaction semantics around calls to btrfs_check_shared() in order to
provide accurate accounting of delayed refs. The transaction management
should be done inside btrfs_check_shared(), so that callers do not need
to manage transactions individually.
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 3c8250e..0661c8c 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;
@@ -4606,36 +4605,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] 22+ messages in thread
* [PATCH v2 07/13] btrfs: remove ref_tree implementation from backref.c
2017-06-29 3:56 [PATCH v2 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (5 preceding siblings ...)
2017-06-29 3:56 ` [PATCH v2 06/13] btrfs: btrfs_check_shared should manage its own transaction Edmund Nadolski
@ 2017-06-29 3:56 ` Edmund Nadolski
2017-07-10 16:53 ` David Sterba
2017-06-29 3:57 ` [PATCH v2 08/13] btrfs: convert prelimary reference tracking to use rbtrees Edmund Nadolski
` (6 subsequent siblings)
13 siblings, 1 reply; 22+ messages in thread
From: Edmund Nadolski @ 2017-06-29 3:56 UTC (permalink / raw)
To: enadolski, jeffm, linux-btrfs, lufq.fnst
Commit afce772e87c3 ("btrfs: fix check_shared for fiemap ioctl") added
the ref_tree code in backref.c to reduce backref searching for
shared extents under the FIEMAP ioctl. This code will not be
compatible with the upcoming rbtree changes for improved backref
searching, so this patch removes the ref_tree code. The rbtree
changes will provide the equivalent functionality for FIEMAP.
The above commit also introduced transaction semantics around calls to
btrfs_check_shared() in order to accurately account for delayed refs.
This functionality needs to be retained, so a complete revert of the
above commit is not desirable. This patch therefore removes the
ref_tree portion of the commit as above, however it does not remove
the transaction portion.
Signed-off-by: Edmund Nadolski <enadolski@suse.com>
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
fs/btrfs/backref.c | 355 ++---------------------------------------------------
1 file changed, 7 insertions(+), 348 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 35cfa38..6cac5ab 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);
@@ -1621,7 +1280,7 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr)
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);
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] 22+ messages in thread
* [PATCH v2 08/13] btrfs: convert prelimary reference tracking to use rbtrees
2017-06-29 3:56 [PATCH v2 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (6 preceding siblings ...)
2017-06-29 3:56 ` [PATCH v2 07/13] btrfs: remove ref_tree implementation from backref.c Edmund Nadolski
@ 2017-06-29 3:57 ` Edmund Nadolski
2017-07-10 16:59 ` David Sterba
2017-07-11 15:15 ` David Sterba
2017-06-29 3:57 ` [PATCH v2 09/13] btrfs: add a node counter to each of the rbtrees Edmund Nadolski
` (5 subsequent siblings)
13 siblings, 2 replies; 22+ messages in thread
From: Edmund Nadolski @ 2017-06-29 3:57 UTC (permalink / raw)
To: enadolski, jeffm, linux-btrfs, lufq.fnst
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 | 437 ++++++++++++++++++++++++++++++++++-------------------
1 file changed, 280 insertions(+), 157 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 6cac5ab..ebe8875 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -26,11 +26,6 @@
#include "delayed-ref.h"
#include "locking.h"
-enum merge_mode {
- MERGE_IDENTICAL_KEYS = 1,
- MERGE_IDENTICAL_PARENTS,
-};
-
/* Just an arbitrary number so we can be sure this happened */
#define BACKREF_FOUND_SHARED 6
@@ -129,7 +124,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 +134,18 @@ 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 */
+ struct preftree indirect_missing_keys;
+};
+
static struct kmem_cache *btrfs_prelim_ref_cache;
int __init btrfs_prelim_ref_init(void)
@@ -158,6 +165,108 @@ void btrfs_prelim_ref_exit(void)
kmem_cache_destroy(btrfs_prelim_ref_cache);
}
+static void free_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;
+ free_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)
+ free_pref(ref);
+
+ preftree->root = RB_ROOT;
+}
+
/*
* the rules for all callers of this function are:
* - obtaining the parent is the goal
@@ -196,7 +305,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 +352,31 @@ 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)
+{
+ struct preftree *tree = &preftrees->indirect;
+ if (!key)
+ tree = &preftrees->indirect_missing_keys;
+ return add_prelim_ref(tree, 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 +558,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) {
+ free_pref(ref);
continue;
+ }
+
if (root_objectid && ref->root_id != root_objectid) {
+ free_pref(ref);
ret = BACKREF_FOUND_SHARED;
goto out;
}
@@ -472,8 +621,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 */
+ free_pref(ref);
continue;
} else if (err) {
+ free_pref(ref);
ret = err;
goto out;
}
@@ -484,19 +636,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) {
+ free_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,44 +663,31 @@ 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 preftree *tree = &preftrees->indirect_missing_keys;
+ struct rb_node *node;
- list_for_each_entry(ref, head, list) {
- if (ref->parent)
- continue;
- if (ref->key_for_search.type)
- continue;
+ while ((node = rb_first(&tree->root))) {
+ ref = rb_entry(node, struct prelim_ref, rbnode);
+ rb_erase(node, &tree->root);
+
+ 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, ref->wanted_disk_byte, 0);
if (IS_ERR(eb)) {
+ free_pref(ref);
return PTR_ERR(eb);
} else if (!extent_buffer_uptodate(eb)) {
+ free_pref(ref);
free_extent_buffer(eb);
return -EIO;
}
@@ -552,73 +698,31 @@ 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);
+ prelim_ref_insert(&preftrees->indirect, ref);
}
return 0;
}
/*
- * 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;
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 sgn;
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) {
@@ -642,24 +746,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, &tmp_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 +786,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 +818,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 +874,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 +883,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 +911,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 +932,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 +963,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 +1006,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 +1048,16 @@ 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,
+ .indirect_missing_keys = PREFTREE_INIT
+ };
key.objectid = bytenr;
key.offset = (u64)-1;
@@ -996,9 +1120,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,
- &prefs_delayed, &total_refs,
- inum);
+ ret = add_delayed_refs(head, time_seq, &preftrees,
+ &total_refs, inum);
mutex_unlock(&head->mutex);
if (ret)
goto out;
@@ -1019,35 +1142,43 @@ 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);
+ WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect_missing_keys.root));
- 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 +1232,15 @@ 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);
+ prelim_release(&preftrees.indirect_missing_keys);
+
if (ret < 0)
free_inode_elem_list(eie);
return ret;
--
2.10.2
^ permalink raw reply related [flat|nested] 22+ messages in thread
* [PATCH v2 09/13] btrfs: add a node counter to each of the rbtrees
2017-06-29 3:56 [PATCH v2 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (7 preceding siblings ...)
2017-06-29 3:57 ` [PATCH v2 08/13] btrfs: convert prelimary reference tracking to use rbtrees Edmund Nadolski
@ 2017-06-29 3:57 ` Edmund Nadolski
2017-06-29 3:57 ` [PATCH v2 10/13] btrfs: backref, add tracepoints for prelim_ref insertion and merging Edmund Nadolski
` (4 subsequent siblings)
13 siblings, 0 replies; 22+ messages in thread
From: Edmund Nadolski @ 2017-06-29 3:57 UTC (permalink / raw)
To: enadolski, jeffm, linux-btrfs, lufq.fnst
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 ebe8875..5e5f8d7 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -136,9 +136,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 */
@@ -248,6 +249,7 @@ static void prelim_ref_insert(struct preftree *preftree,
}
}
+ preftree->count++;
rb_link_node(&newref->rbnode, parent, p);
rb_insert_color(&newref->rbnode, root);
}
@@ -265,6 +267,7 @@ static void prelim_release(struct preftree *preftree)
free_pref(ref);
preftree->root = RB_ROOT;
+ preftree->count = 0;
}
/*
@@ -602,6 +605,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) {
free_pref(ref);
--
2.10.2
^ permalink raw reply related [flat|nested] 22+ messages in thread
* [PATCH v2 10/13] btrfs: backref, add tracepoints for prelim_ref insertion and merging
2017-06-29 3:56 [PATCH v2 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (8 preceding siblings ...)
2017-06-29 3:57 ` [PATCH v2 09/13] btrfs: add a node counter to each of the rbtrees Edmund Nadolski
@ 2017-06-29 3:57 ` Edmund Nadolski
2017-07-11 17:29 ` David Sterba
2017-06-29 3:57 ` [PATCH v2 11/13] btrfs: add cond_resched() calls when resolving backrefs Edmund Nadolski
` (3 subsequent siblings)
13 siblings, 1 reply; 22+ messages in thread
From: Edmund Nadolski @ 2017-06-29 3:57 UTC (permalink / raw)
To: enadolski, jeffm, linux-btrfs, lufq.fnst
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 5e5f8d7..54180f4 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>
+
/* Just an arbitrary number so we can be sure this happened */
#define BACKREF_FOUND_SHARED 6
@@ -120,20 +122,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;
@@ -212,7 +200,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;
@@ -243,6 +232,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;
free_pref(newref);
return;
@@ -250,6 +241,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);
}
@@ -308,7 +300,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)
{
@@ -355,28 +348,30 @@ 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)
{
struct preftree *tree = &preftrees->indirect;
if (!key)
tree = &preftrees->indirect_missing_keys;
- return add_prelim_ref(tree, root_id, key, level, 0,
+ return add_prelim_ref(fs_info, tree, root_id, key, level, 0,
wanted_disk_byte, count, gfp_mask);
}
@@ -654,11 +649,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);
}
@@ -702,7 +697,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);
- prelim_ref_insert(&preftrees->indirect, ref);
+ prelim_ref_insert(fs_info, &preftrees->indirect, ref);
}
return 0;
}
@@ -711,7 +706,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)
{
@@ -754,8 +750,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, &tmp_op_key,
- ref->level + 1, node->bytenr,
+ ret = add_indirect_ref(fs_info, preftrees, ref->root,
+ &tmp_op_key, ref->level + 1,
+ node->bytenr,
node->ref_mod * sgn,
GFP_ATOMIC);
break;
@@ -766,9 +763,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;
}
@@ -790,8 +787,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;
@@ -802,8 +799,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;
@@ -821,7 +818,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)
{
@@ -878,7 +876,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: {
@@ -888,14 +887,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;
@@ -916,8 +915,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:
@@ -968,9 +968,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 */
@@ -980,15 +980,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 */
@@ -1010,8 +1011,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:
@@ -1124,8 +1126,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;
@@ -1145,8 +1147,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 74e4779..83f2d8c 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] 22+ messages in thread
* [PATCH v2 11/13] btrfs: add cond_resched() calls when resolving backrefs
2017-06-29 3:56 [PATCH v2 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (9 preceding siblings ...)
2017-06-29 3:57 ` [PATCH v2 10/13] btrfs: backref, add tracepoints for prelim_ref insertion and merging Edmund Nadolski
@ 2017-06-29 3:57 ` Edmund Nadolski
2017-06-29 3:57 ` [PATCH v2 12/13] btrfs: allow backref search checks for shared extents Edmund Nadolski
` (2 subsequent siblings)
13 siblings, 0 replies; 22+ messages in thread
From: Edmund Nadolski @ 2017-06-29 3:57 UTC (permalink / raw)
To: enadolski, jeffm, linux-btrfs, lufq.fnst
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 54180f4..3cd4f05 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -656,6 +656,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);
@@ -698,6 +699,7 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info,
btrfs_tree_read_unlock(eb);
free_extent_buffer(eb);
prelim_ref_insert(fs_info, &preftrees->indirect, ref);
+ cond_resched();
}
return 0;
}
@@ -1239,6 +1241,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] 22+ messages in thread
* [PATCH v2 12/13] btrfs: allow backref search checks for shared extents
2017-06-29 3:56 [PATCH v2 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (10 preceding siblings ...)
2017-06-29 3:57 ` [PATCH v2 11/13] btrfs: add cond_resched() calls when resolving backrefs Edmund Nadolski
@ 2017-06-29 3:57 ` Edmund Nadolski
2017-06-29 3:57 ` [PATCH v2 13/13] btrfs: clean up extraneous computations in add_delayed_refs Edmund Nadolski
2017-07-10 17:05 ` [PATCH v2 00/13] use rbtrees for preliminary backrefs David Sterba
13 siblings, 0 replies; 22+ messages in thread
From: Edmund Nadolski @ 2017-06-29 3:57 UTC (permalink / raw)
To: enadolski, jeffm, linux-btrfs, lufq.fnst
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 | 161 +++++++++++++++++++++++++++++++++++++----------------
1 file changed, 113 insertions(+), 48 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 3cd4f05..5011b2f 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -135,6 +135,25 @@ struct preftrees {
struct preftree indirect_missing_keys;
};
+/*
+ * 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)
@@ -195,14 +214,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;
@@ -234,12 +265,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;
free_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);
@@ -303,7 +342,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;
@@ -348,31 +388,32 @@ 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)
{
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, gfp_mask);
+ wanted_disk_byte, count, sc, gfp_mask);
}
static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
@@ -570,7 +611,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;
@@ -607,7 +648,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) {
free_pref(ref);
ret = BACKREF_FOUND_SHARED;
goto out;
@@ -649,11 +691,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();
@@ -698,7 +744,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);
- prelim_ref_insert(fs_info, &preftrees->indirect, ref);
+ prelim_ref_insert(fs_info, &preftrees->indirect, ref, NULL);
cond_resched();
}
return 0;
@@ -711,7 +757,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;
@@ -756,7 +802,7 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
&tmp_op_key, ref->level + 1,
node->bytenr,
node->ref_mod * sgn,
- GFP_ATOMIC);
+ sc, GFP_ATOMIC);
break;
}
case BTRFS_SHARED_BLOCK_REF_KEY: {
@@ -768,7 +814,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: {
@@ -784,15 +830,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: {
@@ -804,26 +850,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;
@@ -880,7 +935,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;
@@ -890,13 +945,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;
@@ -910,7 +965,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;
}
@@ -919,7 +974,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:
@@ -935,11 +990,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;
@@ -972,7 +1029,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 */
@@ -984,14 +1041,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 */
@@ -1007,7 +1064,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;
}
@@ -1015,7 +1072,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:
@@ -1035,20 +1092,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;
@@ -1129,7 +1189,7 @@ 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;
@@ -1151,11 +1211,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;
}
@@ -1170,8 +1230,7 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
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,
- root_objectid);
+ extent_item_pos, total_refs, sc);
if (ret)
goto out;
@@ -1190,7 +1249,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;
}
@@ -1294,7 +1354,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;
@@ -1337,7 +1397,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);
@@ -1393,6 +1453,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);
@@ -1413,7 +1478,7 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr)
ULIST_ITER_INIT(&uiter);
while (1) {
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] 22+ messages in thread
* [PATCH v2 13/13] btrfs: clean up extraneous computations in add_delayed_refs
2017-06-29 3:56 [PATCH v2 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (11 preceding siblings ...)
2017-06-29 3:57 ` [PATCH v2 12/13] btrfs: allow backref search checks for shared extents Edmund Nadolski
@ 2017-06-29 3:57 ` Edmund Nadolski
2017-07-10 17:05 ` [PATCH v2 00/13] use rbtrees for preliminary backrefs David Sterba
13 siblings, 0 replies; 22+ messages in thread
From: Edmund Nadolski @ 2017-06-29 3:57 UTC (permalink / raw)
To: enadolski, jeffm, linux-btrfs, lufq.fnst
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 5011b2f..7393a6f 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -764,7 +764,7 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
struct btrfs_key key;
struct btrfs_key tmp_op_key;
struct btrfs_key *op_key = NULL;
- int sgn;
+ int count;
int ret = 0;
if (extent_op && extent_op->update_key) {
@@ -783,15 +783,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 */
@@ -800,9 +800,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,
&tmp_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: {
@@ -811,9 +810,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;
}
@@ -836,9 +834,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: {
@@ -847,10 +844,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] 22+ messages in thread
* Re: [PATCH v2 06/13] btrfs: btrfs_check_shared should manage its own transaction
2017-06-29 3:56 ` [PATCH v2 06/13] btrfs: btrfs_check_shared should manage its own transaction Edmund Nadolski
@ 2017-07-10 16:51 ` David Sterba
0 siblings, 0 replies; 22+ messages in thread
From: David Sterba @ 2017-07-10 16:51 UTC (permalink / raw)
To: Edmund Nadolski; +Cc: jeffm, linux-btrfs, lufq.fnst
On Wed, Jun 28, 2017 at 09:56:58PM -0600, Edmund Nadolski wrote:
> Commit afce772e87c3 ("btrfs: fix check_shared for fiemap ioctl") added
> transaction semantics around calls to btrfs_check_shared() in order to
> provide accurate accounting of delayed refs. The transaction management
> should be done inside btrfs_check_shared(), so that callers do not need
> to manage transactions individually.
>
> Signed-off-by: Edmund Nadolski <enadolski@suse.com>
> Signed-off-by: Jeff Mahoney <jeffm@suse.com>
Reviewed-by: David Sterba <dsterba@suse.com>
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH v2 07/13] btrfs: remove ref_tree implementation from backref.c
2017-06-29 3:56 ` [PATCH v2 07/13] btrfs: remove ref_tree implementation from backref.c Edmund Nadolski
@ 2017-07-10 16:53 ` David Sterba
0 siblings, 0 replies; 22+ messages in thread
From: David Sterba @ 2017-07-10 16:53 UTC (permalink / raw)
To: Edmund Nadolski; +Cc: jeffm, linux-btrfs, lufq.fnst
On Wed, Jun 28, 2017 at 09:56:59PM -0600, Edmund Nadolski wrote:
> Commit afce772e87c3 ("btrfs: fix check_shared for fiemap ioctl") added
> the ref_tree code in backref.c to reduce backref searching for
> shared extents under the FIEMAP ioctl. This code will not be
> compatible with the upcoming rbtree changes for improved backref
> searching, so this patch removes the ref_tree code. The rbtree
> changes will provide the equivalent functionality for FIEMAP.
>
> The above commit also introduced transaction semantics around calls to
> btrfs_check_shared() in order to accurately account for delayed refs.
> This functionality needs to be retained, so a complete revert of the
> above commit is not desirable. This patch therefore removes the
> ref_tree portion of the commit as above, however it does not remove
> the transaction portion.
>
> Signed-off-by: Edmund Nadolski <enadolski@suse.com>
> Signed-off-by: Jeff Mahoney <jeffm@suse.com>
Reviewed-by: David Sterba <dsterba@suse.com>
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH v2 08/13] btrfs: convert prelimary reference tracking to use rbtrees
2017-06-29 3:57 ` [PATCH v2 08/13] btrfs: convert prelimary reference tracking to use rbtrees Edmund Nadolski
@ 2017-07-10 16:59 ` David Sterba
2017-07-11 15:15 ` David Sterba
1 sibling, 0 replies; 22+ messages in thread
From: David Sterba @ 2017-07-10 16:59 UTC (permalink / raw)
To: Edmund Nadolski; +Cc: jeffm, linux-btrfs, lufq.fnst
On Wed, Jun 28, 2017 at 09:57:00PM -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
You've added third rbtree, so the changelog should be updated.
> 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 | 437 ++++++++++++++++++++++++++++++++++-------------------
> 1 file changed, 280 insertions(+), 157 deletions(-)
>
> diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
> index 6cac5ab..ebe8875 100644
> --- a/fs/btrfs/backref.c
> +++ b/fs/btrfs/backref.c
> @@ -26,11 +26,6 @@
> #include "delayed-ref.h"
> #include "locking.h"
>
> -enum merge_mode {
> - MERGE_IDENTICAL_KEYS = 1,
> - MERGE_IDENTICAL_PARENTS,
> -};
> -
> /* Just an arbitrary number so we can be sure this happened */
> #define BACKREF_FOUND_SHARED 6
>
> @@ -129,7 +124,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 +134,18 @@ 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 */
> + struct preftree indirect_missing_keys;
> +};
> +
> static struct kmem_cache *btrfs_prelim_ref_cache;
>
> int __init btrfs_prelim_ref_init(void)
> @@ -158,6 +165,108 @@ void btrfs_prelim_ref_exit(void)
> kmem_cache_destroy(btrfs_prelim_ref_cache);
> }
>
> +static void free_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;
> + free_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)
> + free_pref(ref);
> +
> + preftree->root = RB_ROOT;
> +}
> +
> /*
> * the rules for all callers of this function are:
> * - obtaining the parent is the goal
> @@ -196,7 +305,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 +352,31 @@ 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)
> +{
> + struct preftree *tree = &preftrees->indirect;
> + if (!key)
> + tree = &preftrees->indirect_missing_keys;
> + return add_prelim_ref(tree, 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 +558,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
As it's 'three' now, this needs to be updated as well.
> + * 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) {
> + free_pref(ref);
> continue;
> + }
> +
> if (root_objectid && ref->root_id != root_objectid) {
> + free_pref(ref);
> ret = BACKREF_FOUND_SHARED;
> goto out;
> }
> @@ -472,8 +621,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 */
> + free_pref(ref);
> continue;
> } else if (err) {
> + free_pref(ref);
> ret = err;
> goto out;
> }
> @@ -484,19 +636,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) {
> + free_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,44 +663,31 @@ 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 preftree *tree = &preftrees->indirect_missing_keys;
> + struct rb_node *node;
>
> - list_for_each_entry(ref, head, list) {
> - if (ref->parent)
> - continue;
> - if (ref->key_for_search.type)
> - continue;
> + while ((node = rb_first(&tree->root))) {
> + ref = rb_entry(node, struct prelim_ref, rbnode);
> + rb_erase(node, &tree->root);
> +
> + 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, ref->wanted_disk_byte, 0);
> if (IS_ERR(eb)) {
> + free_pref(ref);
> return PTR_ERR(eb);
> } else if (!extent_buffer_uptodate(eb)) {
> + free_pref(ref);
> free_extent_buffer(eb);
> return -EIO;
> }
> @@ -552,73 +698,31 @@ 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);
> + prelim_ref_insert(&preftrees->indirect, ref);
> }
> return 0;
> }
>
> /*
> - * 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;
> 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 sgn;
> 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) {
> @@ -642,24 +746,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, &tmp_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 +786,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 +818,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 +874,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 +883,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 +911,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 +932,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 +963,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 +1006,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 +1048,16 @@ 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,
> + .indirect_missing_keys = PREFTREE_INIT
> + };
>
> key.objectid = bytenr;
> key.offset = (u64)-1;
> @@ -996,9 +1120,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,
> - &prefs_delayed, &total_refs,
> - inum);
> + ret = add_delayed_refs(head, time_seq, &preftrees,
> + &total_refs, inum);
> mutex_unlock(&head->mutex);
> if (ret)
> goto out;
> @@ -1019,35 +1142,43 @@ 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);
> + WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect_missing_keys.root));
>
> - 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 +1232,15 @@ 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);
> + prelim_release(&preftrees.indirect_missing_keys);
> +
> if (ret < 0)
> free_inode_elem_list(eie);
> return ret;
> --
> 2.10.2
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH v2 00/13] use rbtrees for preliminary backrefs
2017-06-29 3:56 [PATCH v2 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
` (12 preceding siblings ...)
2017-06-29 3:57 ` [PATCH v2 13/13] btrfs: clean up extraneous computations in add_delayed_refs Edmund Nadolski
@ 2017-07-10 17:05 ` David Sterba
13 siblings, 0 replies; 22+ messages in thread
From: David Sterba @ 2017-07-10 17:05 UTC (permalink / raw)
To: Edmund Nadolski; +Cc: jeffm, linux-btrfs, lufq.fnst
On Wed, Jun 28, 2017 at 09:56:52PM -0600, Edmund Nadolski wrote:
> 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
I'm merging patches 1-7 now, as they're fairly independent, no need to
keep them separate. 8 needs an update and the rest seems to depend on
it. I'll keep it in the for-next testing and replace with updated
version when it arrives.
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH v2 08/13] btrfs: convert prelimary reference tracking to use rbtrees
2017-06-29 3:57 ` [PATCH v2 08/13] btrfs: convert prelimary reference tracking to use rbtrees Edmund Nadolski
2017-07-10 16:59 ` David Sterba
@ 2017-07-11 15:15 ` David Sterba
2017-07-11 23:12 ` Edmund Nadolski
1 sibling, 1 reply; 22+ messages in thread
From: David Sterba @ 2017-07-11 15:15 UTC (permalink / raw)
To: Edmund Nadolski; +Cc: jeffm, linux-btrfs, lufq.fnst
On Wed, Jun 28, 2017 at 09:57:00PM -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>
I've bisected to this patch, the self-tests run at module load time
fail:
tests/qgroup-tests.c:272
270 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID,
271 nodesize, nodesize)) {
272 test_msg("Qgroup counts didn't match expected values\n");
273 return -EINVAL;
274 }
245 int btrfs_verify_qgroup_counts(struct btrfs_fs_info *fs_info, u64 qgroupid,
246 u64 rfer, u64 excl)
247 {
248 struct btrfs_qgroup *qgroup;
249
250 qgroup = find_qgroup_rb(fs_info, qgroupid);
251 if (!qgroup)
252 return -EINVAL;
253 if (qgroup->rfer != rfer || qgroup->excl != excl)
254 return -EINVAL;
255 return 0;
256 }
the second if fails, with 0 != 4096 || 0 != 4096
Tested branch was current for-next-test (top commit
8d73f8348287a3d3be10795f45d313f63cdcd72c), with
CONFIG_BTRFS_FS_RUN_SANITY_TESTS=y
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH v2 10/13] btrfs: backref, add tracepoints for prelim_ref insertion and merging
2017-06-29 3:57 ` [PATCH v2 10/13] btrfs: backref, add tracepoints for prelim_ref insertion and merging Edmund Nadolski
@ 2017-07-11 17:29 ` David Sterba
0 siblings, 0 replies; 22+ messages in thread
From: David Sterba @ 2017-07-11 17:29 UTC (permalink / raw)
To: Edmund Nadolski; +Cc: jeffm, linux-btrfs, lufq.fnst
On Wed, Jun 28, 2017 at 09:57:02PM -0600, Edmund Nadolski wrote:
> From: Jeff Mahoney <jeffm@suse.com>
> +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",
Please update the format according to the recommendations
https://btrfs.wiki.kernel.org/index.php/Development_notes#Tracepoints
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH v2 08/13] btrfs: convert prelimary reference tracking to use rbtrees
2017-07-11 15:15 ` David Sterba
@ 2017-07-11 23:12 ` Edmund Nadolski
2017-07-12 15:15 ` David Sterba
0 siblings, 1 reply; 22+ messages in thread
From: Edmund Nadolski @ 2017-07-11 23:12 UTC (permalink / raw)
To: dsterba, Edmund Nadolski, jeffm, linux-btrfs, lufq.fnst
On 07/11/2017 09:15 AM, David Sterba wrote:
> On Wed, Jun 28, 2017 at 09:57:00PM -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>
>
> I've bisected to this patch, the self-tests run at module load time
> fail:
>
> tests/qgroup-tests.c:272
>
> 270 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID,
> 271 nodesize, nodesize)) {
> 272 test_msg("Qgroup counts didn't match expected values\n");
> 273 return -EINVAL;
> 274 }
>
> 245 int btrfs_verify_qgroup_counts(struct btrfs_fs_info *fs_info, u64 qgroupid,
> 246 u64 rfer, u64 excl)
> 247 {
> 248 struct btrfs_qgroup *qgroup;
> 249
> 250 qgroup = find_qgroup_rb(fs_info, qgroupid);
> 251 if (!qgroup)
> 252 return -EINVAL;
> 253 if (qgroup->rfer != rfer || qgroup->excl != excl)
> 254 return -EINVAL;
> 255 return 0;
> 256 }
>
> the second if fails, with 0 != 4096 || 0 != 4096
>
> Tested branch was current for-next-test (top commit
> 8d73f8348287a3d3be10795f45d313f63cdcd72c), with
> CONFIG_BTRFS_FS_RUN_SANITY_TESTS=y
This looks like a consequence of an existing check in __resolve_indirect_ref():
if (btrfs_is_testing(fs_info)) {
srcu_read_unlock(&fs_info->subvol_srcu, index);
ret = -ENOENT;
goto out;
}
The existing code simply leaves the ref on the pref list, to be picked up later
in find_parent_nodes(), which will ulist_add() an entry onto the roots list for
it. The patch otoh when it sees -ENOENT just frees the ref so no entry is
ever added to the ulist.
The patch can be fixed to behave similarly to the existing code by
inserting the ref into the direct tree instead of freeing it. This seems
a bit odd since technically the ref isn't actually 'resolved'. Considering
that this code path is really just a special case for the sanity check when
the fs_info is in a BTRFS_FS_STATE_DUMMY_FS_INFO state, perhaps that's not
too great a concern. Thoughts?
Thanks,
Ed
^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: [PATCH v2 08/13] btrfs: convert prelimary reference tracking to use rbtrees
2017-07-11 23:12 ` Edmund Nadolski
@ 2017-07-12 15:15 ` David Sterba
0 siblings, 0 replies; 22+ messages in thread
From: David Sterba @ 2017-07-12 15:15 UTC (permalink / raw)
To: Edmund Nadolski; +Cc: dsterba, Edmund Nadolski, jeffm, linux-btrfs, lufq.fnst
On Tue, Jul 11, 2017 at 05:12:27PM -0600, Edmund Nadolski wrote:
>
>
> On 07/11/2017 09:15 AM, David Sterba wrote:
> > On Wed, Jun 28, 2017 at 09:57:00PM -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>
> >
> > I've bisected to this patch, the self-tests run at module load time
> > fail:
> >
> > tests/qgroup-tests.c:272
> >
> > 270 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID,
> > 271 nodesize, nodesize)) {
> > 272 test_msg("Qgroup counts didn't match expected values\n");
> > 273 return -EINVAL;
> > 274 }
> >
> > 245 int btrfs_verify_qgroup_counts(struct btrfs_fs_info *fs_info, u64 qgroupid,
> > 246 u64 rfer, u64 excl)
> > 247 {
> > 248 struct btrfs_qgroup *qgroup;
> > 249
> > 250 qgroup = find_qgroup_rb(fs_info, qgroupid);
> > 251 if (!qgroup)
> > 252 return -EINVAL;
> > 253 if (qgroup->rfer != rfer || qgroup->excl != excl)
> > 254 return -EINVAL;
> > 255 return 0;
> > 256 }
> >
> > the second if fails, with 0 != 4096 || 0 != 4096
> >
> > Tested branch was current for-next-test (top commit
> > 8d73f8348287a3d3be10795f45d313f63cdcd72c), with
> > CONFIG_BTRFS_FS_RUN_SANITY_TESTS=y
>
> This looks like a consequence of an existing check in __resolve_indirect_ref():
>
> if (btrfs_is_testing(fs_info)) {
> srcu_read_unlock(&fs_info->subvol_srcu, index);
> ret = -ENOENT;
> goto out;
> }
>
> The existing code simply leaves the ref on the pref list, to be picked up later
> in find_parent_nodes(), which will ulist_add() an entry onto the roots list for
> it. The patch otoh when it sees -ENOENT just frees the ref so no entry is
> ever added to the ulist.
>
> The patch can be fixed to behave similarly to the existing code by
> inserting the ref into the direct tree instead of freeing it. This seems
> a bit odd since technically the ref isn't actually 'resolved'. Considering
> that this code path is really just a special case for the sanity check when
> the fs_info is in a BTRFS_FS_STATE_DUMMY_FS_INFO state, perhaps that's not
> too great a concern. Thoughts?
Yeah, this has been introduced by d9ee522ba3ab51b7e3c6d and it wants to
take some shortcuts for the self-tests. I'm concerned because the module
does not load when the self-tests are enabled.
So at this moment I'd take simpler approach and work around it so we can
continue testing and then fix it properly (either populate the trees or
add more exceptions for the self-tests).
^ permalink raw reply [flat|nested] 22+ messages in thread
end of thread, other threads:[~2017-07-12 15:17 UTC | newest]
Thread overview: 22+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-06-29 3:56 [PATCH v2 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
2017-06-29 3:56 ` [PATCH v2 01/13] btrfs: struct-funcs, constify readers Edmund Nadolski
2017-06-29 3:56 ` [PATCH v2 02/13] btrfs: constify tracepoint arguments Edmund Nadolski
2017-06-29 3:56 ` [PATCH v2 03/13] btrfs: backref, constify some arguments Edmund Nadolski
2017-06-29 3:56 ` [PATCH v2 04/13] btrfs: backref, add unode_aux_to_inode_list helper Edmund Nadolski
2017-06-29 3:56 ` [PATCH v2 05/13] btrfs: backref, cleanup __ namespace abuse Edmund Nadolski
2017-06-29 3:56 ` [PATCH v2 06/13] btrfs: btrfs_check_shared should manage its own transaction Edmund Nadolski
2017-07-10 16:51 ` David Sterba
2017-06-29 3:56 ` [PATCH v2 07/13] btrfs: remove ref_tree implementation from backref.c Edmund Nadolski
2017-07-10 16:53 ` David Sterba
2017-06-29 3:57 ` [PATCH v2 08/13] btrfs: convert prelimary reference tracking to use rbtrees Edmund Nadolski
2017-07-10 16:59 ` David Sterba
2017-07-11 15:15 ` David Sterba
2017-07-11 23:12 ` Edmund Nadolski
2017-07-12 15:15 ` David Sterba
2017-06-29 3:57 ` [PATCH v2 09/13] btrfs: add a node counter to each of the rbtrees Edmund Nadolski
2017-06-29 3:57 ` [PATCH v2 10/13] btrfs: backref, add tracepoints for prelim_ref insertion and merging Edmund Nadolski
2017-07-11 17:29 ` David Sterba
2017-06-29 3:57 ` [PATCH v2 11/13] btrfs: add cond_resched() calls when resolving backrefs Edmund Nadolski
2017-06-29 3:57 ` [PATCH v2 12/13] btrfs: allow backref search checks for shared extents Edmund Nadolski
2017-06-29 3:57 ` [PATCH v2 13/13] btrfs: clean up extraneous computations in add_delayed_refs Edmund Nadolski
2017-07-10 17:05 ` [PATCH v2 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.