Re: [PATCH v8 1/8] btrfs: added helper functions to iterate backrefs
On 03.11.2011 11:32, Jan Schmidt wrote: > On 03.11.2011 02:41, Li Zefan wrote: >> (as this is going to be merged into mainline..) >> >>> +/* >>> + * calls iterate() for every inode that references the extent identified by >>> + * the given parameters. will use the path given as a parameter and return >>> it >>> + * released. >>> + * when the iterator function returns a non-zero value, iteration stops. >>> + */ >>> +int iterate_extent_inodes(struct btrfs_fs_info *fs_info, >>> + struct btrfs_path *path, >>> + u64 extent_item_objectid, >>> + u64 extent_offset, >>> + iterate_extent_inodes_t *iterate, void *ctx) >> >> While trying to use this API, I found there's a big defect in this function. >> >>fs_tree 1 fs_tree 2 >>\ / >> \/ >> \ / >> \/ >> node >> | >> | >> leaf (EXTENT_DATA item) >> >> In the above case, the function will find only 1 reference. > > Hum. You are right. > > I'm convinced that I've been at this point months ago, only I cannot > find code dealing with counts > 1 on nodes. I'll look for a fix in my > branches or make a new one. > > Currently, this is more of a best-effort resolver. Support for delayed > extents is missing, it should be used on commit roots to get a > consistent state. > The qgroups patch contains an implementation to find all roots for a given extent. A quite extensive part of qgroups is needed for that, so it might be easiest to build a new version on top of qgroups. Otherwise I could split qgroups in 2 parts to factor out that half. -Arne -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v8 1/8] btrfs: added helper functions to iterate backrefs
On 03.11.2011 02:41, Li Zefan wrote: > (as this is going to be merged into mainline..) > >> +/* >> + * calls iterate() for every inode that references the extent identified by >> + * the given parameters. will use the path given as a parameter and return >> it >> + * released. >> + * when the iterator function returns a non-zero value, iteration stops. >> + */ >> +int iterate_extent_inodes(struct btrfs_fs_info *fs_info, >> +struct btrfs_path *path, >> +u64 extent_item_objectid, >> +u64 extent_offset, >> +iterate_extent_inodes_t *iterate, void *ctx) > > While trying to use this API, I found there's a big defect in this function. > >fs_tree 1 fs_tree 2 >\ / > \/ > \ / > \/ > node > | > | > leaf (EXTENT_DATA item) > > In the above case, the function will find only 1 reference. Hum. You are right. I'm convinced that I've been at this point months ago, only I cannot find code dealing with counts > 1 on nodes. I'll look for a fix in my branches or make a new one. I also recognized that some "btrfs_" prefixes are missing for the exported functions. I'm going to change this on the next iteration as well. Currently, this is more of a best-effort resolver. Support for delayed extents is missing, it should be used on commit roots to get a consistent state. For the userspace part, at least the simple scenario outlined isn't crucial as "btrfs inspect-internal logical-resolve" will find each of the two paths, depending on the subvolume path you specify. It never finds both, though, which I agree it should. Sigh, -Jan -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH v8 1/8] btrfs: added helper functions to iterate backrefs
(as this is going to be merged into mainline..) > +/* > + * calls iterate() for every inode that references the extent identified by > + * the given parameters. will use the path given as a parameter and return it > + * released. > + * when the iterator function returns a non-zero value, iteration stops. > + */ > +int iterate_extent_inodes(struct btrfs_fs_info *fs_info, > + struct btrfs_path *path, > + u64 extent_item_objectid, > + u64 extent_offset, > + iterate_extent_inodes_t *iterate, void *ctx) While trying to use this API, I found there's a big defect in this function. fs_tree 1 fs_tree 2 \ / \/ \ / \/ node | | leaf (EXTENT_DATA item) In the above case, the function will find only 1 reference. -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH v8 1/8] btrfs: added helper functions to iterate backrefs
These helper functions iterate back references and call a function for each
backref. There is also a function to resolve an inode to a path in the
file system.
Signed-off-by: Jan Schmidt
---
fs/btrfs/Makefile |3 +-
fs/btrfs/backref.c | 764
fs/btrfs/backref.h | 62 +
fs/btrfs/ioctl.h | 11 +
4 files changed, 839 insertions(+), 1 deletions(-)
diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile
index 9b72dcf..c63f649 100644
--- a/fs/btrfs/Makefile
+++ b/fs/btrfs/Makefile
@@ -7,4 +7,5 @@ btrfs-y += super.o ctree.o extent-tree.o print-tree.o
root-tree.o dir-item.o \
extent_map.o sysfs.o struct-funcs.o xattr.o ordered-data.o \
extent_io.o volumes.o async-thread.o ioctl.o locking.o orphan.o \
export.o tree-log.o acl.o free-space-cache.o zlib.o lzo.o \
- compression.o delayed-ref.o relocation.o delayed-inode.o scrub.o
+ compression.o delayed-ref.o relocation.o delayed-inode.o backref.o \
+ scrub.o
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
new file mode 100644
index 000..5bca830
--- /dev/null
+++ b/fs/btrfs/backref.c
@@ -0,0 +1,764 @@
+/*
+ * Copyright (C) 2011 STRATO. All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public
+ * License v2 as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public
+ * License along with this program; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 021110-1307, USA.
+ */
+
+#include "ctree.h"
+#include "disk-io.h"
+#include "backref.h"
+
+struct __data_ref {
+ struct list_head list;
+ u64 inum;
+ u64 root;
+ u64 extent_data_item_offset;
+};
+
+struct __shared_ref {
+ struct list_head list;
+ u64 disk_byte;
+};
+
+static int __inode_info(u64 inum, u64 ioff, u8 key_type,
+ struct btrfs_root *fs_root, struct btrfs_path *path,
+ struct btrfs_key *found_key)
+{
+ int ret;
+ struct btrfs_key key;
+ struct extent_buffer *eb;
+
+ key.type = key_type;
+ key.objectid = inum;
+ key.offset = ioff;
+
+ ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
+ if (ret < 0)
+ return ret;
+
+ eb = path->nodes[0];
+ if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
+ ret = btrfs_next_leaf(fs_root, path);
+ if (ret)
+ return ret;
+ eb = path->nodes[0];
+ }
+
+ btrfs_item_key_to_cpu(eb, found_key, path->slots[0]);
+ if (found_key->type != key.type || found_key->objectid != key.objectid)
+ return 1;
+
+ return 0;
+}
+
+/*
+ * this makes the path point to (inum INODE_ITEM ioff)
+ */
+int inode_item_info(u64 inum, u64 ioff, struct btrfs_root *fs_root,
+ struct btrfs_path *path)
+{
+ struct btrfs_key key;
+ return __inode_info(inum, ioff, BTRFS_INODE_ITEM_KEY, fs_root, path,
+ &key);
+}
+
+static int inode_ref_info(u64 inum, u64 ioff, struct btrfs_root *fs_root,
+ struct btrfs_path *path, int strict,
+ u64 *out_parent_inum,
+ struct extent_buffer **out_iref_eb,
+ int *out_slot)
+{
+ int ret;
+ struct btrfs_key found_key;
+
+ ret = __inode_info(inum, ioff, BTRFS_INODE_REF_KEY, fs_root, path,
+ &found_key);
+
+ if (!ret) {
+ if (out_slot)
+ *out_slot = path->slots[0];
+ if (out_iref_eb)
+ *out_iref_eb = path->nodes[0];
+ if (out_parent_inum)
+ *out_parent_inum = found_key.offset;
+ }
+
+ btrfs_release_path(path);
+ return ret;
+}
+
+/*
+ * this iterates to turn a btrfs_inode_ref into a full filesystem path.
elements
+ * of the path are separated by '/' and the path is guaranteed to be
+ * 0-terminated. the path is only given within the current file system.
+ * Therefore, it never starts with a '/'. the caller is responsible to provide
+ * "size" bytes in "dest". the dest buffer will be filled backwards. finally,
+ * the start point of the resulting string is returned. this pointer is within
+ * dest, normally.
+ * in case the path buffer would overflow, the pointer is decremented further
+ * as if output was written to the buffer, though no more output is actually
+ * generated. that way, the caller
