* [PATCH 01/12] Btrfs-progs: repair missing dir index
2014-10-10 20:57 Btrfs-progs: fix horrible things Josef Bacik
@ 2014-10-10 20:57 ` Josef Bacik
2014-10-10 20:57 ` [PATCH 02/12] Btrfs-progs: pull back backref.c and fix it up Josef Bacik
` (9 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Josef Bacik @ 2014-10-10 20:57 UTC (permalink / raw)
To: linux-btrfs
If we have an inode backref entry then we know enough to add back a missing dir
index. When messing with the inode backrefs we need to do all of that first
before we process the inode recs themselves as we may clear errors on the inode
recs as we fix the directory indexes. This adds the framework for fixing
backref errors and fixes missing dir index issues. Thanks,
Signed-off-by: Josef Bacik <jbacik@fb.com>
---
cmds-check.c | 121 +++++++++++++++++++++++++++++++++-
tests/fsck-tests/004-no-dir-index.img | Bin 0 -> 4096 bytes
2 files changed, 119 insertions(+), 2 deletions(-)
create mode 100644 tests/fsck-tests/004-no-dir-index.img
diff --git a/cmds-check.c b/cmds-check.c
index 76df5ae..a7e0840 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -1516,15 +1516,111 @@ static int repair_inode_orphan_item(struct btrfs_trans_handle *trans,
return ret;
}
+static int add_missing_dir_index(struct btrfs_root *root,
+ struct cache_tree *inode_cache,
+ struct inode_record *rec,
+ struct inode_backref *backref)
+{
+ struct btrfs_path *path;
+ struct btrfs_trans_handle *trans;
+ struct btrfs_dir_item *dir_item;
+ struct extent_buffer *leaf;
+ struct btrfs_key key;
+ struct btrfs_disk_key disk_key;
+ struct inode_record *dir_rec;
+ unsigned long name_ptr;
+ u32 data_size = sizeof(*dir_item) + backref->namelen;
+ int ret;
+
+ path = btrfs_alloc_path();
+ if (!path)
+ return -ENOMEM;
+
+ trans = btrfs_start_transaction(root, 1);
+ if (IS_ERR(trans)) {
+ btrfs_free_path(path);
+ return PTR_ERR(trans);
+ }
+
+ fprintf(stderr, "repairing missing dir index item for inode %llu\n",
+ (unsigned long long)rec->ino);
+ key.objectid = backref->dir;
+ key.type = BTRFS_DIR_INDEX_KEY;
+ key.offset = backref->index;
+
+ ret = btrfs_insert_empty_item(trans, root, path, &key, data_size);
+ BUG_ON(ret);
+
+ leaf = path->nodes[0];
+ dir_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dir_item);
+
+ disk_key.objectid = cpu_to_le64(rec->ino);
+ disk_key.type = BTRFS_INODE_ITEM_KEY;
+ disk_key.offset = 0;
+
+ btrfs_set_dir_item_key(leaf, dir_item, &disk_key);
+ btrfs_set_dir_type(leaf, dir_item, imode_to_type(rec->imode));
+ btrfs_set_dir_data_len(leaf, dir_item, 0);
+ btrfs_set_dir_name_len(leaf, dir_item, backref->namelen);
+ name_ptr = (unsigned long)(dir_item + 1);
+ write_extent_buffer(leaf, backref->name, name_ptr, backref->namelen);
+ btrfs_mark_buffer_dirty(leaf);
+ btrfs_free_path(path);
+ btrfs_commit_transaction(trans, root);
+
+ backref->found_dir_index = 1;
+ dir_rec = get_inode_rec(inode_cache, backref->dir, 0);
+ if (!dir_rec)
+ return 0;
+ dir_rec->found_size += backref->namelen;
+ if (dir_rec->found_size == dir_rec->isize &&
+ (dir_rec->errors & I_ERR_DIR_ISIZE_WRONG))
+ dir_rec->errors &= ~I_ERR_DIR_ISIZE_WRONG;
+ if (dir_rec->found_size != dir_rec->isize)
+ dir_rec->errors |= I_ERR_DIR_ISIZE_WRONG;
+
+ return 0;
+}
+
+static int repair_inode_backrefs(struct btrfs_root *root,
+ struct inode_record *rec,
+ struct cache_tree *inode_cache)
+{
+ struct inode_backref *tmp, *backref;
+ u64 root_dirid = btrfs_root_dirid(&root->root_item);
+ int ret = 0;
+
+ list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
+ /* Index 0 for root dir's are special, don't mess with it */
+ if (rec->ino == root_dirid && backref->index == 0)
+ continue;
+
+ if (!backref->found_dir_index && backref->found_inode_ref) {
+ ret = add_missing_dir_index(root, inode_cache, rec,
+ backref);
+ if (ret)
+ break;
+ }
+
+ if (backref->found_dir_item && backref->found_dir_index) {
+ if (!backref->errors && backref->found_inode_ref) {
+ list_del(&backref->list);
+ free(backref);
+ }
+ }
+ }
+
+ return ret;
+}
+
static int try_repair_inode(struct btrfs_root *root, struct inode_record *rec)
{
struct btrfs_trans_handle *trans;
struct btrfs_path *path;
int ret = 0;
- /* So far we just fix dir isize wrong */
if (!(rec->errors & (I_ERR_DIR_ISIZE_WRONG | I_ERR_NO_ORPHAN_ITEM)))
- return 1;
+ return rec->errors;
path = btrfs_alloc_path();
if (!path)
@@ -1562,6 +1658,27 @@ static int check_inode_recs(struct btrfs_root *root,
return 0;
}
+ /*
+ * We need to repair backrefs first because we could change some of the
+ * errors in the inode recs.
+ *
+ * For example, if we were missing a dir index then the directories
+ * isize would be wrong, so if we fixed the isize to what we thought it
+ * would be and then fixed the backref we'd still have a invalid fs, so
+ * we need to add back the dir index and then check to see if the isize
+ * is still wrong.
+ */
+ cache = search_cache_extent(inode_cache, 0);
+ while (repair && cache) {
+ node = container_of(cache, struct ptr_node, cache);
+ rec = node->data;
+ cache = next_cache_extent(cache);
+
+ if (list_empty(&rec->backrefs))
+ continue;
+ repair_inode_backrefs(root, rec, inode_cache);
+ }
+
rec = get_inode_rec(inode_cache, root_dirid, 0);
if (rec) {
ret = check_root_dir(rec);
diff --git a/tests/fsck-tests/004-no-dir-index.img b/tests/fsck-tests/004-no-dir-index.img
new file mode 100644
index 0000000000000000000000000000000000000000..6f2483e6e4285e6703096b67c5153b3da3309b7b
GIT binary patch
literal 4096
zcmeH|c{CJUAIEJ`%Gf3$Yh{TN(O65bwZcpzM#hrFj3rNlG!&ySmKlmlLp5Y4%QQq8
z3`QlwWEuM!qM{Lxb%uGF^PcmZ^PJ~-|9;PTpL_24-p~Erd+t5I@4e?<JR&vdi;8O<
z&wq;0cFW7H+aSD6JUnN)s>am@t^x&j!i`)W=1!q;d5+8PxO{tuc^bIt#*J|CANj|D
ze;oMVaUgVXXo8{^!z;RWI&1#nFXU<u7NZaAarQrf@bD18>zYkZ5>2AIq9!8@J!EA8
zXY=Hw$+BtVRMY{<_{I-+mBhd5?7sWjOecAB_c`)7%H`0>IPoUFIMuiJv=a}oFFH5s
zobIMmgCB5y6zEbxp0^{s_;2ame#h%0aVJVFkmr%Dk49Q@_er4cAvLJn9zYA<<*&XC
ze)lAVGsUm-O5%2jZO%$5O^JG>BBgibcmNZlpxVM#yha8nF<1ZcY({zf*Kf*t>->d_
zfZ0VM=yd1P4~bKh?g{O~LEW-VL?J*{OHPqB8p;3Eq;fcn$5YF=W5Fa!71BTi_<S##
z?$}-}R+EQkpSo*V=-~Vi*@h1)*YImhGsP-yE9z}KH0n^RHU4d3vALL8^fPnwM-CRB
zdtpiT(X-=P0R43#y>C69=6bP8uXC9ubv5p4fPgX4+M2OD^{cGS@fCmLJI)EeA|hE&
z*IS9FgrgCgN}I>B8FQ{-z9C&F>O*4J@i6q82+UGBF|9A4W2~jYTV}0s>n1`aS!R9m
z%zcXs6EUF1Zf1;sRBawDrpY`7o=b~yH2s^`lyiZua1dX*x>O-K2ytqy$$8?P@AXCR
zjlxUpoEvFveanC<JoO+TEX9W0KID8F@}3^dFj{)-ogqxDDF@fTYsG9lzzh!FAVZEj
zz0Eu~w`$OSijto|y}y!hU|xDNlOvQk9$LF?6VdHD&`~-Txxy)^=@fXCpcJFtnFbp9
z2|>TfE9s0$mX>(55vN?)0P+ohd)J63`AU_>TkO$@Db%_5(URXvQ(p;Jl9VQ0eb$dp
z!#)Y*8)YUIV<9#?(Pn7OvO@~q3nWwN?cv7E=V&VPxo$<>>_D*RSd>Cb%+kSLIb4Q&
z+6ZOs<L9$WBg_l-P*}$&+b0Cfui1W~F)esy1SH&=GhXF;rjqD#T2*D9L929pSmo2v
zvoP*eyqI<Dwft}mOG?GyvIN2(t6PjdW*;S5q*Q8BZ?VU{fY#P=HdA7%P@C-A5=`LN
zXj4c6sQ;_vNL#0HGt#10v+<@I{?~o<<MFxhLk5rlY5S-q2ZI@POo>2Ek@ldGQJKIE
ziHX3t!34T}W0CL!Xk(u6afk67J-o1j<J*2S0g^@{^qy#ViZI5p{{r@fh6w~K>v*}B
zMsdsUM&_p5DW-!n-Bgqd#r>Fdk(=}jpB*Kn2=@Vg%id3&4GS3szKH1;Fi3uS>La+k
zt&XNz<zS{K4D7dj6X#rA$e1`%5d<yfKaZHshV5uRtodnL>N9u}NJmq@@-{iaIjoQo
z8nvV7J&5Tn80kn_DgnMJi-fuREnj->99G0Q7>Jn8ffZb9Yqc&__1w`>oQ|ex<%Vu+
z37gVq|JZrGh|#NFA$(EOxl;IIaYa&_#@W(X*>uNb_&QhJ;$IQGli_uWS7Cqu%H8G2
zhwC)ReN$~AeA1$m=DtVfpCQbD``%7!UDaa#n4kOJUgkqDU_A*z5?0@kY|*!ty@pub
z)q)8e-FkDJUTA!lc)99m)u5~XWDkV`n(ikK$$@b5#U|?Ic8<jhWXWQh6*&ScWKq@P
zx1ajz&iQ`zDiW&xV^t9x%ap$XIQV{L|4+#Q)t8Q;+1Fs)LDEN%dnpYqS0{ZEH?KK-
zxIAflp+RfRKAD}lQUg}Sj%!Zc^#E>HVgLjyUZC{dicR!n38Qh>4>L5v?b<&iL$6<%
z0Hg#kwt`q+^TI!>_qvl@^qjyw$}K6ecgb2dL9Iv){V==fm}ZCjHFnc!pB(NR*-cx;
z70IR8O$*i+J%2qbg{K{}uTXFEvp7y^&qm>uE2L5Q0f&wX>gf5h!fDSBYmIC33Y+}m
zwKSobw2iwyirHZ)l~)5w>M(_2D13V6Z<~={TYEW6XzTawxZ1e`QVSU$QCTR%P_x~Z
zPcm{b%p(`fTo1=fy-6+g>NT4mm@It=WbDp<?^FEN+8cj7+cM>iM;CnbkU8AsqYE%z
zo3J;Xu7Q2D6t?$JI1Sr&E^nb+><kI0@P+U1Pxz0K7vC3DCfWKva<NW;JLe_!eQ9(>
zb^SnRz4R$9OxHWhXP>>7x)!Q!_F-^ZiZjiPL6Ygi?~%!up(SKRDSPtC=%Lb*-}fy2
zCiY|1F`&$Hp3N4YI5h_>D?87$Y9>UE9_^OV9<Z)HDSA6&X1VY6m?G$z7iF1))pX&|
zgZJ1O;p*E6xo$y*#>zdF+V{}GBAk(!bd?E2yB_d(xo<Dc-1ureMZP8u9`V?72(d&D
zh_hO$dns_xh9>_MaA0*UD`BJwf(_fFI;+|$8xk3e$&cGB`fh+J&CUXc>l|esBi0q)
zoPxx>ZN3CuR`?_Dzao#;vjlv6o|Vkx57nWN9xYcr-jHXuElQ9aO5q4lMjx6_kW(2!
z5~>0^UzoZIBG?q!Ca{*z3W}Nv&W~)631JPKw(etWISDn}L4akxT|qVNHfT{QdV<9o
zEqfLi<e7a#a`aT+fsMI^h?}IK{@P1Zj)$e}-8D!SKoujHm$C8U=}mUxEj536P*TNq
zle1<-Z!+^Xb-fZ!5y17G6pe67k8L)aIfzBifZ{mq>$9mnhUlDn$jvMK-(yGm)=u3u
zHJrCxt@V1jxHjU$7U4xzZSH)XB(ND&nr9(cobO<Y8VV$cP4Dkl(U}p%dMYgn3QFo4
zM7LNcpGV2gf%c}hAK8`BAhS;}I`Q65qvrQIlS~5DbS7NwIa?kyl$88sa*<uM(K{ys
zr|WORzZt!I(3!1pd<crZsaKOJ_k8%w+?af(2!4Q3w@S~mJ(sbS0T-RnfF2FsMOwD}
z^PS|VOKPMNL)zDnvMOH)A69OFPqY&40=q(QpwmFizAcXL##ZESAt#uuKYgp?^snFF
z7`g1^cEaE6DzN!iZ~=`%<;Q!7e|Y%ffQTnK%_5P?Ct_oMv1CKaBHBkg4MCB%RqcKv
zRRVfca((qzbsH;g!qS$7!I`p&OEE)`h=p6prr{#2nu2RZhA(R&S1P`d)BKyZ#tizb
zu3ciehCjZ7D4q$c(Lew0cXtQQ8TT`{x?H+i@wu2QDW$ql_R*6+X%5OiPaNC7V#tYY
zwTZl1G%V5|`pW#&3-x~GqP>50<#>43gbsmG_esm-s#$&%lej*=ln<7#rq`+{kBJ&G
zN0&OTutw^66^|oDw{!iJB|^K%W7)}J5TvUbl9O?Q(TAl?_*w+_7ivTycJXB&<$IvI
z?=Ii_eF6!}xr`Xzj+E8u(@S7e_QGfhDY`F|OdNd~)IWsnG{oGw{?(wqO`)0P<(ye=
zP98*GV%hx3WS+G?p|L4R+V;+EWD%OS*shB%KnI!FT@3?m=k%^OXz79D%P&#R^<NC-
zJ2LtRjNCLHdo>DP4ZOqlmv6F8U_SA~XW1^Nn(tj422mTkKpAAgiQ9!0pQ=Y@>vNsZ
Vz`wTS|0Ig(1o-l2+5Wd|{|(AQMP&d0
literal 0
HcmV?d00001
--
1.8.3.1
^ permalink raw reply related [flat|nested] 12+ messages in thread* [PATCH 02/12] Btrfs-progs: pull back backref.c and fix it up
2014-10-10 20:57 Btrfs-progs: fix horrible things Josef Bacik
2014-10-10 20:57 ` [PATCH 01/12] Btrfs-progs: repair missing dir index Josef Bacik
@ 2014-10-10 20:57 ` Josef Bacik
2014-10-10 20:57 ` [PATCH 03/12] Btrfs-progs: break out rbtree util functions Josef Bacik
` (8 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Josef Bacik @ 2014-10-10 20:57 UTC (permalink / raw)
To: linux-btrfs
This patch pulls back backref.c, adds a couple of helpers everywhere that it
needs, and cleans up backref.c to fit in btrfs-progs. Thanks,
Signed-off-by: Josef Bacik <jbacik@fb.com>
---
Makefile | 2 +-
backref.c | 1651 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
backref.h | 73 +++
ctree.c | 84 +++
ctree.h | 14 +
extent_io.c | 43 +-
extent_io.h | 2 +
kerncompat.h | 7 +
ulist.h | 15 +
9 files changed, 1878 insertions(+), 13 deletions(-)
create mode 100644 backref.c
create mode 100644 backref.h
diff --git a/Makefile b/Makefile
index 7cc7783..f954649 100644
--- a/Makefile
+++ b/Makefile
@@ -10,7 +10,7 @@ objects = ctree.o disk-io.o radix-tree.o extent-tree.o print-tree.o \
root-tree.o dir-item.o file-item.o inode-item.o inode-map.o \
extent-cache.o extent_io.o volumes.o utils.o repair.o \
qgroup.o raid6.o free-space-cache.o list_sort.o props.o \
- ulist.o qgroup-verify.o
+ ulist.o qgroup-verify.o backref.o
cmds_objects = cmds-subvolume.o cmds-filesystem.o cmds-device.o cmds-scrub.o \
cmds-inspect.o cmds-balance.o cmds-send.o cmds-receive.o \
cmds-quota.o cmds-qgroup.o cmds-replace.o cmds-check.o \
diff --git a/backref.c b/backref.c
new file mode 100644
index 0000000..593f936
--- /dev/null
+++ b/backref.c
@@ -0,0 +1,1651 @@
+/*
+ * 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 "kerncompat.h"
+#include "ctree.h"
+#include "disk-io.h"
+#include "backref.h"
+#include "ulist.h"
+#include "transaction.h"
+
+#define pr_debug(...) do { } while (0)
+
+struct extent_inode_elem {
+ u64 inum;
+ u64 offset;
+ struct extent_inode_elem *next;
+};
+
+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)
+{
+ u64 offset = 0;
+ struct extent_inode_elem *e;
+
+ if (!btrfs_file_extent_compression(eb, fi) &&
+ !btrfs_file_extent_encryption(eb, fi) &&
+ !btrfs_file_extent_other_encoding(eb, fi)) {
+ u64 data_offset;
+ u64 data_len;
+
+ data_offset = btrfs_file_extent_offset(eb, fi);
+ data_len = btrfs_file_extent_num_bytes(eb, fi);
+
+ if (extent_item_pos < data_offset ||
+ extent_item_pos >= data_offset + data_len)
+ return 1;
+ offset = extent_item_pos - data_offset;
+ }
+
+ e = kmalloc(sizeof(*e), GFP_NOFS);
+ if (!e)
+ return -ENOMEM;
+
+ e->next = *eie;
+ e->inum = key->objectid;
+ e->offset = key->offset + offset;
+ *eie = e;
+
+ return 0;
+}
+
+static void free_inode_elem_list(struct extent_inode_elem *eie)
+{
+ struct extent_inode_elem *eie_next;
+
+ for (; eie; eie = eie_next) {
+ eie_next = eie->next;
+ kfree(eie);
+ }
+}
+
+static int find_extent_in_eb(struct extent_buffer *eb, u64 wanted_disk_byte,
+ u64 extent_item_pos,
+ struct extent_inode_elem **eie)
+{
+ u64 disk_byte;
+ struct btrfs_key key;
+ struct btrfs_file_extent_item *fi;
+ int slot;
+ int nritems;
+ int extent_type;
+ int ret;
+
+ /*
+ * from the shared data ref, we only have the leaf but we need
+ * the key. thus, we must look into all items and see that we
+ * find one (some) with a reference to our extent item.
+ */
+ nritems = btrfs_header_nritems(eb);
+ for (slot = 0; slot < nritems; ++slot) {
+ btrfs_item_key_to_cpu(eb, &key, slot);
+ if (key.type != BTRFS_EXTENT_DATA_KEY)
+ continue;
+ fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
+ extent_type = btrfs_file_extent_type(eb, fi);
+ if (extent_type == BTRFS_FILE_EXTENT_INLINE)
+ continue;
+ /* don't skip BTRFS_FILE_EXTENT_PREALLOC, we can handle that */
+ disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
+ if (disk_byte != wanted_disk_byte)
+ continue;
+
+ ret = check_extent_in_eb(&key, eb, fi, extent_item_pos, eie);
+ if (ret < 0)
+ return ret;
+ }
+
+ return 0;
+}
+
+/*
+ * this structure records all encountered refs on the way up to the root
+ */
+struct __prelim_ref {
+ struct list_head list;
+ 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;
+};
+
+/*
+ * the rules for all callers of this function are:
+ * - obtaining the parent is the goal
+ * - if you add a key, you must know that it is a correct key
+ * - if you cannot add the parent or a correct key, then we will look into the
+ * block later to set a correct key
+ *
+ * delayed refs
+ * ============
+ * backref type | shared | indirect | shared | indirect
+ * information | tree | tree | data | data
+ * --------------------+--------+----------+--------+----------
+ * parent logical | y | - | - | -
+ * key to resolve | - | y | y | y
+ * tree block logical | - | - | - | -
+ * root for resolving | y | y | y | y
+ *
+ * - column 1: we've the parent -> done
+ * - column 2, 3, 4: we use the key to find the parent
+ *
+ * on disk refs (inline or keyed)
+ * ==============================
+ * backref type | shared | indirect | shared | indirect
+ * information | tree | tree | data | data
+ * --------------------+--------+----------+--------+----------
+ * parent logical | y | - | y | -
+ * key to resolve | - | - | - | y
+ * tree block logical | y | y | y | y
+ * root for resolving | - | y | y | y
+ *
+ * - 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)
+ * - 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,
+ struct btrfs_key *key, int level,
+ u64 parent, u64 wanted_disk_byte, int count,
+ gfp_t gfp_mask)
+{
+ struct __prelim_ref *ref;
+
+ if (root_id == BTRFS_DATA_RELOC_TREE_OBJECTID)
+ return 0;
+
+ ref = kmalloc(sizeof(*ref), gfp_mask);
+ if (!ref)
+ return -ENOMEM;
+
+ ref->root_id = root_id;
+ if (key)
+ ref->key_for_search = *key;
+ else
+ memset(&ref->key_for_search, 0, sizeof(ref->key_for_search));
+
+ ref->inode_list = NULL;
+ ref->level = level;
+ ref->count = count;
+ ref->parent = parent;
+ ref->wanted_disk_byte = wanted_disk_byte;
+ list_add_tail(&ref->list, head);
+
+ return 0;
+}
+
+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,
+ u64 total_refs)
+{
+ int ret = 0;
+ int slot;
+ struct extent_buffer *eb;
+ struct btrfs_key key;
+ struct btrfs_key *key_for_search = &ref->key_for_search;
+ struct btrfs_file_extent_item *fi;
+ struct extent_inode_elem *eie = NULL, *old = NULL;
+ u64 disk_byte;
+ u64 wanted_disk_byte = ref->wanted_disk_byte;
+ u64 count = 0;
+
+ if (level != 0) {
+ eb = path->nodes[level];
+ ret = ulist_add(parents, eb->start, 0, GFP_NOFS);
+ if (ret < 0)
+ return ret;
+ return 0;
+ }
+
+ /*
+ * We normally enter this function with the path already pointing to
+ * the first item to check. But sometimes, we may enter it with
+ * slot==nritems. In that case, go to the next leaf before we continue.
+ */
+ if (path->slots[0] >= btrfs_header_nritems(path->nodes[0]))
+ ret = btrfs_next_leaf(root, path);
+
+ while (!ret && count < total_refs) {
+ eb = path->nodes[0];
+ slot = path->slots[0];
+
+ btrfs_item_key_to_cpu(eb, &key, slot);
+
+ if (key.objectid != key_for_search->objectid ||
+ key.type != BTRFS_EXTENT_DATA_KEY)
+ break;
+
+ fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
+ disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
+
+ if (disk_byte == wanted_disk_byte) {
+ eie = NULL;
+ old = NULL;
+ count++;
+ if (extent_item_pos) {
+ ret = check_extent_in_eb(&key, eb, fi,
+ *extent_item_pos,
+ &eie);
+ if (ret < 0)
+ break;
+ }
+ if (ret > 0)
+ goto next;
+ ret = ulist_add_merge_ptr(parents, eb->start,
+ eie, (void **)&old, GFP_NOFS);
+ if (ret < 0)
+ break;
+ if (!ret && extent_item_pos) {
+ while (old->next)
+ old = old->next;
+ old->next = eie;
+ }
+ eie = NULL;
+ }
+next:
+ ret = btrfs_next_item(root, path);
+ }
+
+ if (ret > 0)
+ ret = 0;
+ else if (ret < 0)
+ free_inode_elem_list(eie);
+ return ret;
+}
+
+/*
+ * 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)
+{
+ struct btrfs_root *root;
+ struct btrfs_key root_key;
+ struct extent_buffer *eb;
+ int ret = 0;
+ int root_level;
+ int level = ref->level;
+
+ root_key.objectid = ref->root_id;
+ root_key.type = BTRFS_ROOT_ITEM_KEY;
+ root_key.offset = (u64)-1;
+
+ root = btrfs_read_fs_root(fs_info, &root_key);
+ if (IS_ERR(root)) {
+ ret = PTR_ERR(root);
+ goto out;
+ }
+
+ root_level = btrfs_root_level(&root->root_item);
+
+ if (root_level + 1 == level)
+ goto out;
+
+ path->lowest_level = level;
+ ret = btrfs_search_slot(NULL, root, &ref->key_for_search, path, 0, 0);
+
+ pr_debug("search slot in root %llu (level %d, ref count %d) returned "
+ "%d for key (%llu %u %llu)\n",
+ ref->root_id, level, ref->count, ret,
+ ref->key_for_search.objectid, ref->key_for_search.type,
+ ref->key_for_search.offset);
+ if (ret < 0)
+ goto out;
+
+ eb = path->nodes[level];
+ while (!eb) {
+ WARN_ON(!level);
+ if (!level) {
+ ret = 1;
+ goto out;
+ }
+ level--;
+ eb = path->nodes[level];
+ }
+
+ ret = add_all_parents(root, path, parents, ref, level, time_seq,
+ extent_item_pos, total_refs);
+out:
+ path->lowest_level = 0;
+ btrfs_release_path(path);
+ return ret;
+}
+
+/*
+ * 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)
+{
+ 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;
+
+ 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.
+ */
+ list_for_each_entry_safe(ref, ref_safe, head, list) {
+ if (ref->parent) /* already direct */
+ continue;
+ if (ref->count == 0)
+ continue;
+ 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.
+ */
+ if (err == -ENOENT) {
+ continue;
+ } else if (err) {
+ ret = err;
+ goto out;
+ }
+
+ /* we put the first parent into the ref at hand */
+ 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;
+
+ /* additional parents require new refs being added here */
+ while ((node = ulist_next(parents, &uiter))) {
+ new_ref = kmalloc(sizeof(*new_ref), GFP_NOFS);
+ if (!new_ref) {
+ ret = -ENOMEM;
+ goto out;
+ }
+ memcpy(new_ref, ref, sizeof(*ref));
+ new_ref->parent = node->val;
+ new_ref->inode_list = (struct extent_inode_elem *)
+ (uintptr_t)node->aux;
+ list_add(&new_ref->list, &ref->list);
+ }
+ ulist_reinit(parents);
+ }
+out:
+ ulist_free(parents);
+ 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 list_head *pos;
+ struct extent_buffer *eb;
+
+ list_for_each(pos, head) {
+ struct __prelim_ref *ref;
+ ref = list_entry(pos, struct __prelim_ref, list);
+
+ if (ref->parent)
+ continue;
+ if (ref->key_for_search.type)
+ continue;
+ BUG_ON(!ref->wanted_disk_byte);
+ eb = read_tree_block(fs_info->tree_root, ref->wanted_disk_byte,
+ fs_info->tree_root->leafsize, 0);
+ if (!eb || !extent_buffer_uptodate(eb)) {
+ free_extent_buffer(eb);
+ return -EIO;
+ }
+ if (btrfs_header_level(eb) == 0)
+ btrfs_item_key_to_cpu(eb, &ref->key_for_search, 0);
+ else
+ btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0);
+ free_extent_buffer(eb);
+ }
+ return 0;
+}
+
+/*
+ * merge two lists of backrefs and adjust counts accordingly
+ *
+ * mode = 1: merge identical keys, if key is set
+ * FIXME: if we add more keys in __add_prelim_ref, 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).
+ * mode = 2: merge identical parents
+ */
+static void __merge_refs(struct list_head *head, int mode)
+{
+ struct list_head *pos1;
+
+ list_for_each(pos1, head) {
+ struct list_head *n2;
+ struct list_head *pos2;
+ struct __prelim_ref *ref1;
+
+ ref1 = list_entry(pos1, struct __prelim_ref, list);
+
+ for (pos2 = pos1->next, n2 = pos2->next; pos2 != head;
+ pos2 = n2, n2 = pos2->next) {
+ struct __prelim_ref *ref2;
+ struct __prelim_ref *xchg;
+ struct extent_inode_elem *eie;
+
+ ref2 = list_entry(pos2, struct __prelim_ref, list);
+
+ if (mode == 1) {
+ if (!ref_for_same_block(ref1, ref2))
+ continue;
+ if (!ref1->parent && ref2->parent) {
+ xchg = ref1;
+ ref1 = ref2;
+ ref2 = xchg;
+ }
+ } 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);
+ kfree(ref2);
+ }
+
+ }
+}
+
+/*
+ * add all inline backrefs for bytenr to the list
+ */
+static int __add_inline_refs(struct btrfs_fs_info *fs_info,
+ struct btrfs_path *path, u64 bytenr,
+ int *info_level, struct list_head *prefs,
+ u64 *total_refs)
+{
+ int ret = 0;
+ int slot;
+ struct extent_buffer *leaf;
+ struct btrfs_key key;
+ struct btrfs_key found_key;
+ unsigned long ptr;
+ unsigned long end;
+ struct btrfs_extent_item *ei;
+ u64 flags;
+ u64 item_size;
+
+ /*
+ * enumerate all inline refs
+ */
+ leaf = path->nodes[0];
+ slot = path->slots[0];
+
+ item_size = btrfs_item_size_nr(leaf, slot);
+ BUG_ON(item_size < sizeof(*ei));
+
+ ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
+ flags = btrfs_extent_flags(leaf, ei);
+ *total_refs += btrfs_extent_refs(leaf, ei);
+ btrfs_item_key_to_cpu(leaf, &found_key, slot);
+
+ ptr = (unsigned long)(ei + 1);
+ end = (unsigned long)ei + item_size;
+
+ if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
+ flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
+ struct btrfs_tree_block_info *info;
+
+ info = (struct btrfs_tree_block_info *)ptr;
+ *info_level = btrfs_tree_block_level(leaf, info);
+ ptr += sizeof(struct btrfs_tree_block_info);
+ BUG_ON(ptr > end);
+ } else if (found_key.type == BTRFS_METADATA_ITEM_KEY) {
+ *info_level = found_key.offset;
+ } else {
+ BUG_ON(!(flags & BTRFS_EXTENT_FLAG_DATA));
+ }
+
+ while (ptr < end) {
+ struct btrfs_extent_inline_ref *iref;
+ u64 offset;
+ int type;
+
+ iref = (struct btrfs_extent_inline_ref *)ptr;
+ type = btrfs_extent_inline_ref_type(leaf, iref);
+ offset = btrfs_extent_inline_ref_offset(leaf, iref);
+
+ switch (type) {
+ case BTRFS_SHARED_BLOCK_REF_KEY:
+ 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;
+ int count;
+
+ 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);
+ break;
+ }
+ case BTRFS_TREE_BLOCK_REF_KEY:
+ 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;
+ int count;
+ u64 root;
+
+ dref = (struct btrfs_extent_data_ref *)(&iref->offset);
+ count = btrfs_extent_data_ref_count(leaf, dref);
+ key.objectid = btrfs_extent_data_ref_objectid(leaf,
+ dref);
+ key.type = BTRFS_EXTENT_DATA_KEY;
+ key.offset = btrfs_extent_data_ref_offset(leaf, dref);
+ root = btrfs_extent_data_ref_root(leaf, dref);
+ ret = __add_prelim_ref(prefs, root, &key, 0, 0,
+ bytenr, count, GFP_NOFS);
+ break;
+ }
+ default:
+ WARN_ON(1);
+ }
+ if (ret)
+ return ret;
+ ptr += btrfs_extent_inline_ref_size(type);
+ }
+
+ return 0;
+}
+
+/*
+ * 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 btrfs_root *extent_root = fs_info->extent_root;
+ int ret;
+ int slot;
+ struct extent_buffer *leaf;
+ struct btrfs_key key;
+
+ while (1) {
+ ret = btrfs_next_item(extent_root, path);
+ if (ret < 0)
+ break;
+ if (ret) {
+ ret = 0;
+ break;
+ }
+
+ slot = path->slots[0];
+ leaf = path->nodes[0];
+ btrfs_item_key_to_cpu(leaf, &key, slot);
+
+ if (key.objectid != bytenr)
+ break;
+ if (key.type < BTRFS_TREE_BLOCK_REF_KEY)
+ continue;
+ if (key.type > BTRFS_SHARED_DATA_REF_KEY)
+ break;
+
+ 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);
+ break;
+ case BTRFS_SHARED_DATA_REF_KEY: {
+ 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);
+ break;
+ }
+ case BTRFS_TREE_BLOCK_REF_KEY:
+ 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;
+ int count;
+ u64 root;
+
+ dref = btrfs_item_ptr(leaf, slot,
+ struct btrfs_extent_data_ref);
+ count = btrfs_extent_data_ref_count(leaf, dref);
+ key.objectid = btrfs_extent_data_ref_objectid(leaf,
+ dref);
+ key.type = BTRFS_EXTENT_DATA_KEY;
+ key.offset = btrfs_extent_data_ref_offset(leaf, dref);
+ root = btrfs_extent_data_ref_root(leaf, dref);
+ ret = __add_prelim_ref(prefs, root, &key, 0, 0,
+ bytenr, count, GFP_NOFS);
+ break;
+ }
+ default:
+ WARN_ON(1);
+ }
+ if (ret)
+ return ret;
+
+ }
+
+ return ret;
+}
+
+/*
+ * this adds all existing backrefs (inline backrefs, backrefs and delayed
+ * refs) for the given bytenr to the refs list, merges duplicates and resolves
+ * indirect refs to their parent bytenr.
+ * When roots are found, they're added to the roots list
+ *
+ * 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)
+{
+ struct btrfs_key key;
+ struct btrfs_path *path;
+ int info_level = 0;
+ int ret;
+ struct list_head prefs;
+ struct __prelim_ref *ref;
+ struct extent_inode_elem *eie = NULL;
+ u64 total_refs = 0;
+
+ INIT_LIST_HEAD(&prefs);
+
+ key.objectid = bytenr;
+ key.offset = (u64)-1;
+ if (btrfs_fs_incompat(fs_info,
+ BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA))
+ key.type = BTRFS_METADATA_ITEM_KEY;
+ else
+ key.type = BTRFS_EXTENT_ITEM_KEY;
+
+ path = btrfs_alloc_path();
+ if (!path)
+ return -ENOMEM;
+
+ ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0);
+ if (ret < 0)
+ goto out;
+ BUG_ON(ret == 0);
+
+ if (path->slots[0]) {
+ struct extent_buffer *leaf;
+ int slot;
+
+ path->slots[0]--;
+ leaf = path->nodes[0];
+ slot = path->slots[0];
+ btrfs_item_key_to_cpu(leaf, &key, slot);
+ if (key.objectid == bytenr &&
+ (key.type == BTRFS_EXTENT_ITEM_KEY ||
+ key.type == BTRFS_METADATA_ITEM_KEY)) {
+ ret = __add_inline_refs(fs_info, path, bytenr,
+ &info_level, &prefs,
+ &total_refs);
+ if (ret)
+ goto out;
+ ret = __add_keyed_refs(fs_info, path, bytenr,
+ info_level, &prefs);
+ if (ret)
+ goto out;
+ }
+ }
+ btrfs_release_path(path);
+
+ ret = __add_missing_keys(fs_info, &prefs);
+ if (ret)
+ goto out;
+
+ __merge_refs(&prefs, 1);
+
+ ret = __resolve_indirect_refs(fs_info, path, time_seq, &prefs,
+ extent_item_pos, total_refs);
+ if (ret)
+ goto out;
+
+ __merge_refs(&prefs, 2);
+
+ while (!list_empty(&prefs)) {
+ ref = list_first_entry(&prefs, struct __prelim_ref, list);
+ WARN_ON(ref->count < 0);
+ if (roots && ref->count && ref->root_id && ref->parent == 0) {
+ /* no parent == root of tree */
+ ret = ulist_add(roots, ref->root_id, 0, GFP_NOFS);
+ if (ret < 0)
+ goto out;
+ }
+ if (ref->count && ref->parent) {
+ if (extent_item_pos && !ref->inode_list &&
+ ref->level == 0) {
+ u32 bsz;
+ struct extent_buffer *eb;
+ bsz = btrfs_level_size(fs_info->extent_root,
+ ref->level);
+ eb = read_tree_block(fs_info->extent_root,
+ ref->parent, bsz, 0);
+ if (!eb || !extent_buffer_uptodate(eb)) {
+ free_extent_buffer(eb);
+ ret = -EIO;
+ goto out;
+ }
+ ret = find_extent_in_eb(eb, bytenr,
+ *extent_item_pos, &eie);
+ free_extent_buffer(eb);
+ if (ret < 0)
+ goto out;
+ ref->inode_list = eie;
+ }
+ ret = ulist_add_merge_ptr(refs, ref->parent,
+ ref->inode_list,
+ (void **)&eie, GFP_NOFS);
+ if (ret < 0)
+ goto out;
+ if (!ret && extent_item_pos) {
+ /*
+ * we've recorded that parent, so we must extend
+ * its inode list here
+ */
+ BUG_ON(!eie);
+ while (eie->next)
+ eie = eie->next;
+ eie->next = ref->inode_list;
+ }
+ eie = NULL;
+ }
+ list_del(&ref->list);
+ kfree(ref);
+ }
+
+out:
+ btrfs_free_path(path);
+ while (!list_empty(&prefs)) {
+ ref = list_first_entry(&prefs, struct __prelim_ref, list);
+ list_del(&ref->list);
+ kfree(ref);
+ }
+ if (ret < 0)
+ free_inode_elem_list(eie);
+ return ret;
+}
+
+static void free_leaf_list(struct ulist *blocks)
+{
+ struct ulist_node *node = NULL;
+ struct extent_inode_elem *eie;
+ struct ulist_iterator uiter;
+
+ ULIST_ITER_INIT(&uiter);
+ while ((node = ulist_next(blocks, &uiter))) {
+ if (!node->aux)
+ continue;
+ eie = (struct extent_inode_elem *)(uintptr_t)node->aux;
+ free_inode_elem_list(eie);
+ node->aux = 0;
+ }
+
+ ulist_free(blocks);
+}
+
+/*
+ * Finds all leafs with a reference to the specified combination of bytenr and
+ * offset. key_list_head will point to a list of corresponding keys (caller must
+ * free each list element). The leafs will be stored in the leafs ulist, which
+ * must be freed with ulist_free.
+ *
+ * returns 0 on success, <0 on error
+ */
+static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info, u64 bytenr,
+ u64 time_seq, struct ulist **leafs,
+ const u64 *extent_item_pos)
+{
+ int ret;
+
+ *leafs = ulist_alloc(GFP_NOFS);
+ if (!*leafs)
+ return -ENOMEM;
+
+ ret = find_parent_nodes(trans, fs_info, bytenr,
+ time_seq, *leafs, NULL, extent_item_pos);
+ if (ret < 0 && ret != -ENOENT) {
+ free_leaf_list(*leafs);
+ return ret;
+ }
+
+ return 0;
+}
+
+/*
+ * walk all backrefs for a given extent to find all roots that reference this
+ * extent. Walking a backref means finding all extents that reference this
+ * extent and in turn walk the backrefs of those, too. Naturally this is a
+ * recursive process, but here it is implemented in an iterative fashion: We
+ * find all referencing extents for the extent in question and put them on a
+ * list. In turn, we find all referencing extents for those, further appending
+ * to the list. The way we iterate the list allows adding more elements after
+ * the current while iterating. The process stops when we reach the end of the
+ * list. Found roots are added to the roots list.
+ *
+ * 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)
+{
+ struct ulist *tmp;
+ struct ulist_node *node = NULL;
+ struct ulist_iterator uiter;
+ int ret;
+
+ tmp = ulist_alloc(GFP_NOFS);
+ if (!tmp)
+ return -ENOMEM;
+ *roots = ulist_alloc(GFP_NOFS);
+ if (!*roots) {
+ ulist_free(tmp);
+ return -ENOMEM;
+ }
+
+ ULIST_ITER_INIT(&uiter);
+ while (1) {
+ ret = find_parent_nodes(trans, fs_info, bytenr,
+ time_seq, tmp, *roots, NULL);
+ if (ret < 0 && ret != -ENOENT) {
+ ulist_free(tmp);
+ ulist_free(*roots);
+ return ret;
+ }
+ node = ulist_next(tmp, &uiter);
+ if (!node)
+ break;
+ bytenr = node->val;
+ cond_resched();
+ }
+
+ ulist_free(tmp);
+ return 0;
+}
+
+int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info, u64 bytenr,
+ u64 time_seq, struct ulist **roots)
+{
+ return __btrfs_find_all_roots(trans, fs_info, bytenr, time_seq, roots);
+}
+
+/*
+ * 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 btrfs_find_item(fs_root, path, inum, ioff,
+ BTRFS_INODE_ITEM_KEY, &key);
+}
+
+static int inode_ref_info(u64 inum, u64 ioff, struct btrfs_root *fs_root,
+ struct btrfs_path *path,
+ struct btrfs_key *found_key)
+{
+ return btrfs_find_item(fs_root, path, inum, ioff,
+ BTRFS_INODE_REF_KEY, found_key);
+}
+
+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 ret, slot;
+ struct btrfs_key key;
+ struct btrfs_key found_key;
+ struct btrfs_inode_extref *extref;
+ struct extent_buffer *leaf;
+ unsigned long ptr;
+
+ key.objectid = inode_objectid;
+ btrfs_set_key_type(&key, BTRFS_INODE_EXTREF_KEY);
+ key.offset = start_off;
+
+ ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
+ if (ret < 0)
+ return ret;
+
+ while (1) {
+ leaf = path->nodes[0];
+ slot = path->slots[0];
+ if (slot >= btrfs_header_nritems(leaf)) {
+ /*
+ * If the item at offset is not found,
+ * btrfs_search_slot will point us to the slot
+ * where it should be inserted. In our case
+ * that will be the slot directly before the
+ * next INODE_REF_KEY_V2 item. In the case
+ * that we're pointing to the last slot in a
+ * leaf, we must move one leaf over.
+ */
+ ret = btrfs_next_leaf(root, path);
+ if (ret) {
+ if (ret >= 1)
+ ret = -ENOENT;
+ break;
+ }
+ continue;
+ }
+
+ btrfs_item_key_to_cpu(leaf, &found_key, slot);
+
+ /*
+ * Check that we're still looking at an extended ref key for
+ * this particular objectid. If we have different
+ * objectid or type then there are no more to be found
+ * in the tree and we can exit.
+ */
+ ret = -ENOENT;
+ if (found_key.objectid != inode_objectid)
+ break;
+ if (btrfs_key_type(&found_key) != BTRFS_INODE_EXTREF_KEY)
+ break;
+
+ ret = 0;
+ ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
+ extref = (struct btrfs_inode_extref *)ptr;
+ *ret_extref = extref;
+ if (found_off)
+ *found_off = found_key.offset;
+ break;
+ }
+
+ return ret;
+}
+
+/*
+ * this iterates to turn a name (from iref/extref) 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 can determine how much space would be
+ * required for the path to fit into the buffer. in that case, the returned
+ * value will be smaller than dest. callers must check this!
+ */
+char *btrfs_ref_to_path(struct btrfs_root *fs_root, struct btrfs_path *path,
+ u32 name_len, unsigned long name_off,
+ struct extent_buffer *eb_in, u64 parent,
+ char *dest, u32 size)
+{
+ int slot;
+ u64 next_inum;
+ int ret;
+ s64 bytes_left = ((s64)size) - 1;
+ struct extent_buffer *eb = eb_in;
+ struct btrfs_key found_key;
+ struct btrfs_inode_ref *iref;
+
+ if (bytes_left >= 0)
+ dest[bytes_left] = '\0';
+
+ while (1) {
+ bytes_left -= name_len;
+ if (bytes_left >= 0)
+ read_extent_buffer(eb, dest + bytes_left,
+ name_off, name_len);
+ if (eb != eb_in)
+ free_extent_buffer(eb);
+ ret = inode_ref_info(parent, 0, fs_root, path, &found_key);
+ if (ret > 0)
+ ret = -ENOENT;
+ if (ret)
+ break;
+
+ next_inum = found_key.offset;
+
+ /* regular exit ahead */
+ if (parent == next_inum)
+ break;
+
+ slot = path->slots[0];
+ eb = path->nodes[0];
+ /* make sure we can use eb after releasing the path */
+ if (eb != eb_in)
+ eb->refs++;
+ btrfs_release_path(path);
+ iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
+
+ name_len = btrfs_inode_ref_name_len(eb, iref);
+ name_off = (unsigned long)(iref + 1);
+
+ parent = next_inum;
+ --bytes_left;
+ if (bytes_left >= 0)
+ dest[bytes_left] = '/';
+ }
+
+ btrfs_release_path(path);
+
+ if (ret)
+ return ERR_PTR(ret);
+
+ return dest + bytes_left;
+}
+
+/*
+ * this makes the path point to (logical EXTENT_ITEM *)
+ * returns BTRFS_EXTENT_FLAG_DATA for data, BTRFS_EXTENT_FLAG_TREE_BLOCK for
+ * tree blocks and <0 on error.
+ */
+int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,
+ struct btrfs_path *path, struct btrfs_key *found_key,
+ u64 *flags_ret)
+{
+ int ret;
+ u64 flags;
+ u64 size = 0;
+ u32 item_size;
+ struct extent_buffer *eb;
+ struct btrfs_extent_item *ei;
+ struct btrfs_key key;
+
+ if (btrfs_fs_incompat(fs_info,
+ BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA))
+ key.type = BTRFS_METADATA_ITEM_KEY;
+ else
+ key.type = BTRFS_EXTENT_ITEM_KEY;
+ key.objectid = logical;
+ key.offset = (u64)-1;
+
+ ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
+ if (ret < 0)
+ return ret;
+
+ ret = btrfs_previous_extent_item(fs_info->extent_root, path, 0);
+ if (ret) {
+ if (ret > 0)
+ ret = -ENOENT;
+ return ret;
+ }
+ btrfs_item_key_to_cpu(path->nodes[0], found_key, path->slots[0]);
+ if (found_key->type == BTRFS_METADATA_ITEM_KEY)
+ size = fs_info->extent_root->leafsize;
+ else if (found_key->type == BTRFS_EXTENT_ITEM_KEY)
+ size = found_key->offset;
+
+ if (found_key->objectid > logical ||
+ found_key->objectid + size <= logical) {
+ pr_debug("logical %llu is not within any extent\n", logical);
+ return -ENOENT;
+ }
+
+ eb = path->nodes[0];
+ item_size = btrfs_item_size_nr(eb, path->slots[0]);
+ BUG_ON(item_size < sizeof(*ei));
+
+ ei = btrfs_item_ptr(eb, path->slots[0], struct btrfs_extent_item);
+ flags = btrfs_extent_flags(eb, ei);
+
+ pr_debug("logical %llu is at position %llu within the extent (%llu "
+ "EXTENT_ITEM %llu) flags %#llx size %u\n",
+ logical, logical - found_key->objectid, found_key->objectid,
+ found_key->offset, flags, item_size);
+
+ WARN_ON(!flags_ret);
+ if (flags_ret) {
+ if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
+ *flags_ret = BTRFS_EXTENT_FLAG_TREE_BLOCK;
+ else if (flags & BTRFS_EXTENT_FLAG_DATA)
+ *flags_ret = BTRFS_EXTENT_FLAG_DATA;
+ else
+ BUG_ON(1);
+ return 0;
+ }
+
+ return -EIO;
+}
+
+/*
+ * 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
+ * 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,
+ struct btrfs_extent_inline_ref **out_eiref,
+ int *out_type)
+{
+ unsigned long end;
+ u64 flags;
+ struct btrfs_tree_block_info *info;
+
+ if (!*ptr) {
+ /* first call */
+ flags = btrfs_extent_flags(eb, ei);
+ if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
+ if (key->type == BTRFS_METADATA_ITEM_KEY) {
+ /* a skinny metadata extent */
+ *out_eiref =
+ (struct btrfs_extent_inline_ref *)(ei + 1);
+ } else {
+ WARN_ON(key->type != BTRFS_EXTENT_ITEM_KEY);
+ info = (struct btrfs_tree_block_info *)(ei + 1);
+ *out_eiref =
+ (struct btrfs_extent_inline_ref *)(info + 1);
+ }
+ } else {
+ *out_eiref = (struct btrfs_extent_inline_ref *)(ei + 1);
+ }
+ *ptr = (unsigned long)*out_eiref;
+ if ((unsigned long)(*ptr) >= (unsigned long)ei + item_size)
+ return -ENOENT;
+ }
+
+ end = (unsigned long)ei + item_size;
+ *out_eiref = (struct btrfs_extent_inline_ref *)(*ptr);
+ *out_type = btrfs_extent_inline_ref_type(eb, *out_eiref);
+
+ *ptr += btrfs_extent_inline_ref_size(*out_type);
+ WARN_ON(*ptr > end);
+ if (*ptr == end)
+ return 1; /* last */
+
+ return 0;
+}
+
+/*
+ * 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).
+ * returns 0 if data was provided, 1 if there was no more data to provide or
+ * <0 on error.
+ */
+int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb,
+ struct btrfs_key *key, struct btrfs_extent_item *ei,
+ u32 item_size, u64 *out_root, u8 *out_level)
+{
+ int ret;
+ int type;
+ struct btrfs_tree_block_info *info;
+ struct btrfs_extent_inline_ref *eiref;
+
+ if (*ptr == (unsigned long)-1)
+ return 1;
+
+ while (1) {
+ ret = __get_extent_inline_ref(ptr, eb, key, ei, item_size,
+ &eiref, &type);
+ if (ret < 0)
+ return ret;
+
+ if (type == BTRFS_TREE_BLOCK_REF_KEY ||
+ type == BTRFS_SHARED_BLOCK_REF_KEY)
+ break;
+
+ if (ret == 1)
+ return 1;
+ }
+
+ /* we can treat both ref types equally here */
+ info = (struct btrfs_tree_block_info *)(ei + 1);
+ *out_root = btrfs_extent_inline_ref_offset(eb, eiref);
+ *out_level = btrfs_tree_block_level(eb, info);
+
+ if (ret == 1)
+ *ptr = (unsigned long)-1;
+
+ return 0;
+}
+
+static int iterate_leaf_refs(struct extent_inode_elem *inode_list,
+ u64 root, u64 extent_item_objectid,
+ iterate_extent_inodes_t *iterate, void *ctx)
+{
+ struct extent_inode_elem *eie;
+ int ret = 0;
+
+ for (eie = inode_list; eie; eie = eie->next) {
+ pr_debug("ref for %llu resolved, key (%llu EXTEND_DATA %llu), "
+ "root %llu\n", extent_item_objectid,
+ eie->inum, eie->offset, root);
+ ret = iterate(eie->inum, eie->offset, root, ctx);
+ if (ret) {
+ pr_debug("stopping iteration for %llu due to ret=%d\n",
+ extent_item_objectid, ret);
+ break;
+ }
+ }
+
+ return ret;
+}
+
+/*
+ * calls iterate() for every inode that references the extent identified by
+ * the given parameters.
+ * when the iterator function returns a non-zero value, iteration stops.
+ */
+int iterate_extent_inodes(struct btrfs_fs_info *fs_info,
+ u64 extent_item_objectid, u64 extent_item_pos,
+ int search_commit_root,
+ iterate_extent_inodes_t *iterate, void *ctx)
+{
+ int ret;
+ struct btrfs_trans_handle *trans = NULL;
+ struct ulist *refs = NULL;
+ struct ulist *roots = NULL;
+ struct ulist_node *ref_node = NULL;
+ struct ulist_node *root_node = NULL;
+ struct ulist_iterator ref_uiter;
+ struct ulist_iterator root_uiter;
+
+ pr_debug("resolving all inodes for extent %llu\n",
+ extent_item_objectid);
+
+ ret = btrfs_find_all_leafs(trans, fs_info, extent_item_objectid,
+ 0, &refs, &extent_item_pos);
+ if (ret)
+ goto out;
+
+ 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,
+ 0, &roots);
+ if (ret)
+ break;
+ ULIST_ITER_INIT(&root_uiter);
+ while (!ret && (root_node = ulist_next(roots, &root_uiter))) {
+ pr_debug("root %llu references leaf %llu, data list "
+ "%#llx\n", root_node->val, ref_node->val,
+ ref_node->aux);
+ ret = iterate_leaf_refs((struct extent_inode_elem *)
+ (uintptr_t)ref_node->aux,
+ root_node->val,
+ extent_item_objectid,
+ iterate, ctx);
+ }
+ ulist_free(roots);
+ }
+
+ free_leaf_list(refs);
+out:
+ return ret;
+}
+
+int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,
+ struct btrfs_path *path,
+ iterate_extent_inodes_t *iterate, void *ctx)
+{
+ int ret;
+ u64 extent_item_pos;
+ u64 flags = 0;
+ struct btrfs_key found_key;
+ int search_commit_root = 0;
+
+ ret = extent_from_logical(fs_info, logical, path, &found_key, &flags);
+ btrfs_release_path(path);
+ if (ret < 0)
+ return ret;
+ if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
+ return -EINVAL;
+
+ extent_item_pos = logical - found_key.objectid;
+ ret = iterate_extent_inodes(fs_info, found_key.objectid,
+ extent_item_pos, search_commit_root,
+ iterate, ctx);
+
+ return ret;
+}
+
+typedef int (iterate_irefs_t)(u64 parent, u32 name_len, unsigned long name_off,
+ struct extent_buffer *eb, void *ctx);
+
+static int iterate_inode_refs(u64 inum, struct btrfs_root *fs_root,
+ struct btrfs_path *path,
+ iterate_irefs_t *iterate, void *ctx)
+{
+ int ret = 0;
+ int slot;
+ u32 cur;
+ u32 len;
+ u32 name_len;
+ u64 parent = 0;
+ int found = 0;
+ struct extent_buffer *eb;
+ struct btrfs_item *item;
+ struct btrfs_inode_ref *iref;
+ struct btrfs_key found_key;
+
+ while (!ret) {
+ ret = inode_ref_info(inum, parent ? parent+1 : 0, fs_root, path,
+ &found_key);
+ if (ret < 0)
+ break;
+ if (ret) {
+ ret = found ? 0 : -ENOENT;
+ break;
+ }
+ ++found;
+
+ parent = found_key.offset;
+ slot = path->slots[0];
+ eb = btrfs_clone_extent_buffer(path->nodes[0]);
+ if (!eb) {
+ ret = -ENOMEM;
+ break;
+ }
+ extent_buffer_get(eb);
+ btrfs_release_path(path);
+
+ item = btrfs_item_nr(slot);
+ iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
+
+ for (cur = 0; cur < btrfs_item_size(eb, item); cur += len) {
+ name_len = btrfs_inode_ref_name_len(eb, iref);
+ /* path must be released before calling iterate()! */
+ pr_debug("following ref at offset %u for inode %llu in "
+ "tree %llu\n", cur, found_key.objectid,
+ fs_root->objectid);
+ ret = iterate(parent, name_len,
+ (unsigned long)(iref + 1), eb, ctx);
+ if (ret)
+ break;
+ len = sizeof(*iref) + name_len;
+ iref = (struct btrfs_inode_ref *)((char *)iref + len);
+ }
+ free_extent_buffer(eb);
+ }
+
+ btrfs_release_path(path);
+
+ return ret;
+}
+
+static int iterate_inode_extrefs(u64 inum, struct btrfs_root *fs_root,
+ struct btrfs_path *path,
+ iterate_irefs_t *iterate, void *ctx)
+{
+ int ret;
+ int slot;
+ u64 offset = 0;
+ u64 parent;
+ int found = 0;
+ struct extent_buffer *eb;
+ struct btrfs_inode_extref *extref;
+ struct extent_buffer *leaf;
+ u32 item_size;
+ u32 cur_offset;
+ unsigned long ptr;
+
+ while (1) {
+ ret = btrfs_find_one_extref(fs_root, inum, offset, path, &extref,
+ &offset);
+ if (ret < 0)
+ break;
+ if (ret) {
+ ret = found ? 0 : -ENOENT;
+ break;
+ }
+ ++found;
+
+ slot = path->slots[0];
+ eb = btrfs_clone_extent_buffer(path->nodes[0]);
+ if (!eb) {
+ ret = -ENOMEM;
+ break;
+ }
+ extent_buffer_get(eb);
+
+ btrfs_release_path(path);
+
+ leaf = path->nodes[0];
+ item_size = btrfs_item_size_nr(leaf, slot);
+ ptr = btrfs_item_ptr_offset(leaf, slot);
+ cur_offset = 0;
+
+ while (cur_offset < item_size) {
+ u32 name_len;
+
+ extref = (struct btrfs_inode_extref *)(ptr + cur_offset);
+ parent = btrfs_inode_extref_parent(eb, extref);
+ name_len = btrfs_inode_extref_name_len(eb, extref);
+ ret = iterate(parent, name_len,
+ (unsigned long)&extref->name, eb, ctx);
+ if (ret)
+ break;
+
+ cur_offset += btrfs_inode_extref_name_len(leaf, extref);
+ cur_offset += sizeof(*extref);
+ }
+ free_extent_buffer(eb);
+
+ offset++;
+ }
+
+ btrfs_release_path(path);
+
+ return ret;
+}
+
+static int iterate_irefs(u64 inum, struct btrfs_root *fs_root,
+ struct btrfs_path *path, iterate_irefs_t *iterate,
+ void *ctx)
+{
+ int ret;
+ int found_refs = 0;
+
+ ret = iterate_inode_refs(inum, fs_root, path, iterate, ctx);
+ if (!ret)
+ ++found_refs;
+ else if (ret != -ENOENT)
+ return ret;
+
+ ret = iterate_inode_extrefs(inum, fs_root, path, iterate, ctx);
+ if (ret == -ENOENT && found_refs)
+ return 0;
+
+ return ret;
+}
+
+/*
+ * returns 0 if the path could be dumped (probably truncated)
+ * returns <0 in case of an error
+ */
+static int inode_to_path(u64 inum, u32 name_len, unsigned long name_off,
+ struct extent_buffer *eb, void *ctx)
+{
+ struct inode_fs_paths *ipath = ctx;
+ char *fspath;
+ char *fspath_min;
+ int i = ipath->fspath->elem_cnt;
+ const int s_ptr = sizeof(char *);
+ u32 bytes_left;
+
+ bytes_left = ipath->fspath->bytes_left > s_ptr ?
+ ipath->fspath->bytes_left - s_ptr : 0;
+
+ fspath_min = (char *)ipath->fspath->val + (i + 1) * s_ptr;
+ fspath = btrfs_ref_to_path(ipath->fs_root, ipath->btrfs_path, name_len,
+ name_off, eb, inum, fspath_min, bytes_left);
+ if (IS_ERR(fspath))
+ return PTR_ERR(fspath);
+
+ if (fspath > fspath_min) {
+ ipath->fspath->val[i] = (u64)(unsigned long)fspath;
+ ++ipath->fspath->elem_cnt;
+ ipath->fspath->bytes_left = fspath - fspath_min;
+ } else {
+ ++ipath->fspath->elem_missed;
+ ipath->fspath->bytes_missing += fspath_min - fspath;
+ ipath->fspath->bytes_left = 0;
+ }
+
+ return 0;
+}
+
+/*
+ * this dumps all file system paths to the inode into the ipath struct, provided
+ * is has been created large enough. each path is zero-terminated and accessed
+ * from ipath->fspath->val[i].
+ * when it returns, there are ipath->fspath->elem_cnt number of paths available
+ * in ipath->fspath->val[]. when the allocated space wasn't sufficient, the
+ * number of missed paths in recored in ipath->fspath->elem_missed, otherwise,
+ * it's zero. ipath->fspath->bytes_missing holds the number of bytes that would
+ * have been needed to return all paths.
+ */
+int paths_from_inode(u64 inum, struct inode_fs_paths *ipath)
+{
+ return iterate_irefs(inum, ipath->fs_root, ipath->btrfs_path,
+ inode_to_path, ipath);
+}
+
+struct btrfs_data_container *init_data_container(u32 total_bytes)
+{
+ struct btrfs_data_container *data;
+ size_t alloc_bytes;
+
+ alloc_bytes = max_t(size_t, total_bytes, sizeof(*data));
+ data = vmalloc(alloc_bytes);
+ if (!data)
+ return ERR_PTR(-ENOMEM);
+
+ if (total_bytes >= sizeof(*data)) {
+ data->bytes_left = total_bytes - sizeof(*data);
+ data->bytes_missing = 0;
+ } else {
+ data->bytes_missing = sizeof(*data) - total_bytes;
+ data->bytes_left = 0;
+ }
+
+ data->elem_cnt = 0;
+ data->elem_missed = 0;
+
+ return data;
+}
+
+/*
+ * allocates space to return multiple file system paths for an inode.
+ * total_bytes to allocate are passed, note that space usable for actual path
+ * information will be total_bytes - sizeof(struct inode_fs_paths).
+ * the returned pointer must be freed with free_ipath() in the end.
+ */
+struct inode_fs_paths *init_ipath(s32 total_bytes, struct btrfs_root *fs_root,
+ struct btrfs_path *path)
+{
+ struct inode_fs_paths *ifp;
+ struct btrfs_data_container *fspath;
+
+ fspath = init_data_container(total_bytes);
+ if (IS_ERR(fspath))
+ return (void *)fspath;
+
+ ifp = kmalloc(sizeof(*ifp), GFP_NOFS);
+ if (!ifp) {
+ kfree(fspath);
+ return ERR_PTR(-ENOMEM);
+ }
+
+ ifp->btrfs_path = path;
+ ifp->fspath = fspath;
+ ifp->fs_root = fs_root;
+
+ return ifp;
+}
+
+void free_ipath(struct inode_fs_paths *ipath)
+{
+ if (!ipath)
+ return;
+ vfree(ipath->fspath);
+ kfree(ipath);
+}
diff --git a/backref.h b/backref.h
new file mode 100644
index 0000000..fd22b99
--- /dev/null
+++ b/backref.h
@@ -0,0 +1,73 @@
+/*
+ * 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.
+ */
+
+#ifndef __BTRFS_BACKREF__
+#define __BTRFS_BACKREF__
+
+#include "ulist.h"
+#include "extent_io.h"
+
+struct inode_fs_paths {
+ struct btrfs_path *btrfs_path;
+ struct btrfs_root *fs_root;
+ struct btrfs_data_container *fspath;
+};
+
+typedef int (iterate_extent_inodes_t)(u64 inum, u64 offset, u64 root,
+ void *ctx);
+
+int inode_item_info(u64 inum, u64 ioff, struct btrfs_root *fs_root,
+ struct btrfs_path *path);
+
+int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,
+ struct btrfs_path *path, struct btrfs_key *found_key,
+ u64 *flags);
+
+int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb,
+ struct btrfs_key *key, struct btrfs_extent_item *ei,
+ u32 item_size, u64 *out_root, u8 *out_level);
+
+int iterate_extent_inodes(struct btrfs_fs_info *fs_info,
+ u64 extent_item_objectid,
+ u64 extent_offset, int search_commit_root,
+ iterate_extent_inodes_t *iterate, void *ctx);
+
+int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,
+ struct btrfs_path *path,
+ iterate_extent_inodes_t *iterate, void *ctx);
+
+int paths_from_inode(u64 inum, struct inode_fs_paths *ipath);
+
+int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
+ struct btrfs_fs_info *fs_info, u64 bytenr,
+ u64 time_seq, struct ulist **roots);
+char *btrfs_ref_to_path(struct btrfs_root *fs_root, struct btrfs_path *path,
+ u32 name_len, unsigned long name_off,
+ struct extent_buffer *eb_in, u64 parent,
+ char *dest, u32 size);
+
+struct btrfs_data_container *init_data_container(u32 total_bytes);
+struct inode_fs_paths *init_ipath(s32 total_bytes, struct btrfs_root *fs_root,
+ struct btrfs_path *path);
+void free_ipath(struct inode_fs_paths *ipath);
+
+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);
+#endif
diff --git a/ctree.c b/ctree.c
index c085941..23399e2 100644
--- a/ctree.c
+++ b/ctree.c
@@ -1021,6 +1021,49 @@ void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
}
}
+int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *found_path,
+ u64 iobjectid, u64 ioff, u8 key_type,
+ struct btrfs_key *found_key)
+{
+ int ret;
+ struct btrfs_key key;
+ struct extent_buffer *eb;
+ struct btrfs_path *path;
+
+ key.type = key_type;
+ key.objectid = iobjectid;
+ key.offset = ioff;
+
+ if (found_path == NULL) {
+ path = btrfs_alloc_path();
+ if (!path)
+ return -ENOMEM;
+ } else
+ path = found_path;
+
+ ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
+ if ((ret < 0) || (found_key == NULL)) {
+ if (path != found_path)
+ btrfs_free_path(path);
+ 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;
+}
+
/*
* look for key in the tree. path is filled in with nodes along the way
* if key is found, we return zero and you can find the item in the leaf
@@ -2813,3 +2856,44 @@ int btrfs_previous_item(struct btrfs_root *root,
return 1;
}
+/*
+ * search in extent tree to find a previous Metadata/Data extent item with
+ * min objecitd.
+ *
+ * returns 0 if something is found, 1 if nothing was found and < 0 on error
+ */
+int btrfs_previous_extent_item(struct btrfs_root *root,
+ struct btrfs_path *path, u64 min_objectid)
+{
+ struct btrfs_key found_key;
+ struct extent_buffer *leaf;
+ u32 nritems;
+ int ret;
+
+ while (1) {
+ if (path->slots[0] == 0) {
+ ret = btrfs_prev_leaf(root, path);
+ if (ret != 0)
+ return ret;
+ } else {
+ path->slots[0]--;
+ }
+ leaf = path->nodes[0];
+ nritems = btrfs_header_nritems(leaf);
+ if (nritems == 0)
+ return 1;
+ if (path->slots[0] == nritems)
+ path->slots[0]--;
+
+ btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
+ if (found_key.objectid < min_objectid)
+ break;
+ if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
+ found_key.type == BTRFS_METADATA_ITEM_KEY)
+ return 0;
+ if (found_key.objectid == min_objectid &&
+ found_key.type < BTRFS_EXTENT_ITEM_KEY)
+ break;
+ }
+ return 1;
+}
diff --git a/ctree.h b/ctree.h
index 93b8585..eaab667 100644
--- a/ctree.h
+++ b/ctree.h
@@ -2253,6 +2253,8 @@ struct extent_buffer *read_node_slot(struct btrfs_root *root,
int btrfs_previous_item(struct btrfs_root *root,
struct btrfs_path *path, u64 min_objectid,
int type);
+int btrfs_previous_extent_item(struct btrfs_root *root,
+ struct btrfs_path *path, u64 min_objectid);
int btrfs_cow_block(struct btrfs_trans_handle *trans,
struct btrfs_root *root, struct extent_buffer *buf,
struct extent_buffer *parent, int parent_slot,
@@ -2281,6 +2283,9 @@ int btrfs_split_item(struct btrfs_trans_handle *trans,
int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
*root, struct btrfs_key *key, struct btrfs_path *p, int
ins_len, int cow);
+int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *found_path,
+ u64 iobjectid, u64 ioff, u8 key_type,
+ struct btrfs_key *found_key);
void btrfs_release_path(struct btrfs_path *p);
void add_root_to_dirty_list(struct btrfs_root *root);
struct btrfs_path *btrfs_alloc_path(void);
@@ -2313,6 +2318,15 @@ static inline int btrfs_insert_empty_item(struct btrfs_trans_handle *trans,
}
int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path);
+static inline int btrfs_next_item(struct btrfs_root *root,
+ struct btrfs_path *p)
+{
+ ++p->slots[0];
+ if (p->slots[0] >= btrfs_header_nritems(p->nodes[0]))
+ return btrfs_next_leaf(root, p);
+ return 0;
+}
+
int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path);
int btrfs_leaf_free_space(struct btrfs_root *root, struct extent_buffer *leaf);
void btrfs_fixup_low_keys(struct btrfs_root *root, struct btrfs_path *path,
diff --git a/extent_io.c b/extent_io.c
index 1df377d..21ed72e 100644
--- a/extent_io.c
+++ b/extent_io.c
@@ -569,7 +569,6 @@ static struct extent_buffer *__alloc_extent_buffer(struct extent_io_tree *tree,
u64 bytenr, u32 blocksize)
{
struct extent_buffer *eb;
- int ret;
eb = malloc(sizeof(struct extent_buffer) + blocksize);
if (!eb) {
@@ -589,17 +588,23 @@ static struct extent_buffer *__alloc_extent_buffer(struct extent_io_tree *tree,
eb->cache_node.size = blocksize;
INIT_LIST_HEAD(&eb->recow);
- free_some_buffers(tree);
- ret = insert_cache_extent(&tree->cache, &eb->cache_node);
- if (ret) {
- free(eb);
- return NULL;
- }
- list_add_tail(&eb->lru, &tree->lru);
- tree->cache_size += blocksize;
return eb;
}
+struct extent_buffer *btrfs_clone_extent_buffer(struct extent_buffer *src)
+{
+ struct extent_buffer *new;
+
+ new = __alloc_extent_buffer(NULL, src->start, src->len);
+ if (new == NULL)
+ return NULL;
+
+ copy_extent_buffer(new, src, 0, 0, src->len);
+ new->flags |= EXTENT_BUFFER_DUMMY;
+
+ return new;
+}
+
void free_extent_buffer(struct extent_buffer *eb)
{
if (!eb)
@@ -612,9 +617,11 @@ void free_extent_buffer(struct extent_buffer *eb)
BUG_ON(eb->flags & EXTENT_DIRTY);
list_del_init(&eb->lru);
list_del_init(&eb->recow);
- remove_cache_extent(&tree->cache, &eb->cache_node);
- BUG_ON(tree->cache_size < eb->len);
- tree->cache_size -= eb->len;
+ if (!(eb->flags & EXTENT_BUFFER_DUMMY)) {
+ BUG_ON(tree->cache_size < eb->len);
+ remove_cache_extent(&tree->cache, &eb->cache_node);
+ tree->cache_size -= eb->len;
+ }
free(eb);
}
}
@@ -663,12 +670,24 @@ struct extent_buffer *alloc_extent_buffer(struct extent_io_tree *tree,
list_move_tail(&eb->lru, &tree->lru);
eb->refs++;
} else {
+ int ret;
+
if (cache) {
eb = container_of(cache, struct extent_buffer,
cache_node);
free_extent_buffer(eb);
}
eb = __alloc_extent_buffer(tree, bytenr, blocksize);
+ if (!eb)
+ return NULL;
+ ret = insert_cache_extent(&tree->cache, &eb->cache_node);
+ if (ret) {
+ free(eb);
+ return NULL;
+ }
+ list_add_tail(&eb->lru, &tree->lru);
+ tree->cache_size += blocksize;
+ free_some_buffers(tree);
}
return eb;
}
diff --git a/extent_io.h b/extent_io.h
index 68fb9ce..acc316e 100644
--- a/extent_io.h
+++ b/extent_io.h
@@ -40,6 +40,7 @@
#define EXTENT_BUFFER_FILLED (1 << 8)
#define EXTENT_CSUM (1 << 9)
#define EXTENT_BAD_TRANSID (1 << 10)
+#define EXTENT_BUFFER_DUMMY (1 << 11)
#define EXTENT_IOBITS (EXTENT_LOCKED | EXTENT_WRITEBACK)
#define BLOCK_GROUP_DATA EXTENT_WRITEBACK
@@ -111,6 +112,7 @@ struct extent_buffer *find_first_extent_buffer(struct extent_io_tree *tree,
u64 start);
struct extent_buffer *alloc_extent_buffer(struct extent_io_tree *tree,
u64 bytenr, u32 blocksize);
+struct extent_buffer *btrfs_clone_extent_buffer(struct extent_buffer *src);
void free_extent_buffer(struct extent_buffer *eb);
int read_extent_from_disk(struct extent_buffer *eb,
unsigned long offset, unsigned long len);
diff --git a/kerncompat.h b/kerncompat.h
index 19c7fa5..ea34936 100644
--- a/kerncompat.h
+++ b/kerncompat.h
@@ -102,6 +102,9 @@ typedef __u32 u32;
typedef __u64 u64;
typedef __u16 u16;
typedef __u8 u8;
+typedef __s64 s64;
+typedef __s32 s32;
+
/*
* Continuing to define __KERNEL__ breaks others parts of the code, so
* we can just undefine it now that we have the correct headers...
@@ -113,6 +116,8 @@ typedef unsigned int __u32;
typedef unsigned long long u64;
typedef unsigned char u8;
typedef unsigned short u16;
+typedef long long s64;
+typedef int s32
#endif
@@ -263,6 +268,8 @@ static inline long IS_ERR(const void *ptr)
#define kzalloc(x, y) calloc(1, x)
#define kstrdup(x, y) strdup(x)
#define kfree(x) free(x)
+#define vmalloc(x) malloc(x)
+#define vfree(x) free(x)
#define BUG_ON(c) assert_trace(#c, __FILE__, __func__, __LINE__, !(c))
diff --git a/ulist.h b/ulist.h
index 2a0e948..9e0e4e0 100644
--- a/ulist.h
+++ b/ulist.h
@@ -58,6 +58,21 @@ void ulist_free(struct ulist *ulist);
int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask);
int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux,
u64 *old_aux, gfp_t gfp_mask);
+
+/* just like ulist_add_merge() but take a pointer for the aux data */
+static inline int ulist_add_merge_ptr(struct ulist *ulist, u64 val, void *aux,
+ void **old_aux, gfp_t gfp_mask)
+{
+#if BITS_PER_LONG == 32
+ u64 old64 = (uintptr_t)*old_aux;
+ int ret = ulist_add_merge(ulist, val, (uintptr_t)aux, &old64, gfp_mask);
+ *old_aux = (void *)((uintptr_t)old64);
+ return ret;
+#else
+ return ulist_add_merge(ulist, val, (u64)aux, (u64 *)old_aux, gfp_mask);
+#endif
+}
+
struct ulist_node *ulist_next(struct ulist *ulist,
struct ulist_iterator *uiter);
--
1.8.3.1
^ permalink raw reply related [flat|nested] 12+ messages in thread* [PATCH 03/12] Btrfs-progs: break out rbtree util functions
2014-10-10 20:57 Btrfs-progs: fix horrible things Josef Bacik
2014-10-10 20:57 ` [PATCH 01/12] Btrfs-progs: repair missing dir index Josef Bacik
2014-10-10 20:57 ` [PATCH 02/12] Btrfs-progs: pull back backref.c and fix it up Josef Bacik
@ 2014-10-10 20:57 ` Josef Bacik
2014-10-10 20:57 ` [PATCH 04/12] Btrfs-progs: update rbtree libs Josef Bacik
` (7 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Josef Bacik @ 2014-10-10 20:57 UTC (permalink / raw)
To: linux-btrfs
These were added to deal with duplicated functionality within btrfs-progs, but
we specifically copied rbtree.c from the kernel, so move these functions out
into their own file. This will make it easier to keep rbtree.c in sync. Thanks,
Signed-off-by: Josef Bacik <jbacik@fb.com>
---
Makefile | 2 +-
btrfs-list.c | 1 +
cmds-check.c | 1 +
disk-io.c | 1 +
extent-cache.c | 1 +
qgroup-verify.c | 1 +
rbtree-utils.c | 82 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
rbtree-utils.h | 45 +++++++++++++++++++++++++++++++
rbtree.c | 63 --------------------------------------------
rbtree.h | 22 ----------------
10 files changed, 133 insertions(+), 86 deletions(-)
create mode 100644 rbtree-utils.c
create mode 100644 rbtree-utils.h
diff --git a/Makefile b/Makefile
index f954649..a0afe3b 100644
--- a/Makefile
+++ b/Makefile
@@ -10,7 +10,7 @@ objects = ctree.o disk-io.o radix-tree.o extent-tree.o print-tree.o \
root-tree.o dir-item.o file-item.o inode-item.o inode-map.o \
extent-cache.o extent_io.o volumes.o utils.o repair.o \
qgroup.o raid6.o free-space-cache.o list_sort.o props.o \
- ulist.o qgroup-verify.o backref.o
+ ulist.o qgroup-verify.o backref.o rbtree-utils.o
cmds_objects = cmds-subvolume.o cmds-filesystem.o cmds-device.o cmds-scrub.o \
cmds-inspect.o cmds-balance.o cmds-send.o cmds-receive.o \
cmds-quota.o cmds-qgroup.o cmds-replace.o cmds-check.o \
diff --git a/btrfs-list.c b/btrfs-list.c
index 01ccca9..b6b8493 100644
--- a/btrfs-list.c
+++ b/btrfs-list.c
@@ -33,6 +33,7 @@
#include "utils.h"
#include <uuid/uuid.h>
#include "btrfs-list.h"
+#include "rbtree-utils.h"
#define BTRFS_LIST_NFILTERS_INCREASE (2 * BTRFS_LIST_FILTER_MAX)
#define BTRFS_LIST_NCOMPS_INCREASE (2 * BTRFS_LIST_COMP_MAX)
diff --git a/cmds-check.c b/cmds-check.c
index a7e0840..ff9c0d5 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -39,6 +39,7 @@
#include "free-space-cache.h"
#include "btrfsck.h"
#include "qgroup-verify.h"
+#include "rbtree-utils.h"
static u64 bytes_used = 0;
static u64 total_csum_bytes = 0;
diff --git a/disk-io.c b/disk-io.c
index 34c0a97..08be53a 100644
--- a/disk-io.c
+++ b/disk-io.c
@@ -34,6 +34,7 @@
#include "crc32c.h"
#include "utils.h"
#include "print-tree.h"
+#include "rbtree-utils.h"
static int check_tree_block(struct btrfs_root *root, struct extent_buffer *buf)
{
diff --git a/extent-cache.c b/extent-cache.c
index 84de87b..7656ab2 100644
--- a/extent-cache.c
+++ b/extent-cache.c
@@ -19,6 +19,7 @@
#include <stdlib.h>
#include "kerncompat.h"
#include "extent-cache.h"
+#include "rbtree-utils.h"
struct cache_extent_search_range {
u64 objectid;
diff --git a/qgroup-verify.c b/qgroup-verify.c
index 430f099..c0c61d0 100644
--- a/qgroup-verify.c
+++ b/qgroup-verify.c
@@ -28,6 +28,7 @@
#include "print-tree.h"
#include "utils.h"
#include "ulist.h"
+#include "rbtree-utils.h"
#include "qgroup-verify.h"
diff --git a/rbtree-utils.c b/rbtree-utils.c
new file mode 100644
index 0000000..7371bbb
--- /dev/null
+++ b/rbtree-utils.c
@@ -0,0 +1,82 @@
+/*
+ * Copyright (C) 2014 Facebook. 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 "rbtree-utils.h"
+
+int rb_insert(struct rb_root *root, struct rb_node *node,
+ rb_compare_nodes comp)
+{
+ struct rb_node **p = &root->rb_node;
+ struct rb_node *parent = NULL;
+ int ret;
+
+ while(*p) {
+ parent = *p;
+
+ ret = comp(parent, node);
+ if (ret < 0)
+ p = &(*p)->rb_left;
+ else if (ret > 0)
+ p = &(*p)->rb_right;
+ else
+ return -EEXIST;
+ }
+
+ rb_link_node(node, parent, p);
+ rb_insert_color(node, root);
+ return 0;
+}
+
+struct rb_node *rb_search(struct rb_root *root, void *key, rb_compare_keys comp,
+ struct rb_node **next_ret)
+{
+ struct rb_node *n = root->rb_node;
+ struct rb_node *parent = NULL;
+ int ret = 0;
+
+ while(n) {
+ parent = n;
+
+ ret = comp(n, key);
+ if (ret < 0)
+ n = n->rb_left;
+ else if (ret > 0)
+ n = n->rb_right;
+ else
+ return n;
+ }
+
+ if (!next_ret)
+ return NULL;
+
+ if (parent && ret > 0)
+ parent = rb_next(parent);
+
+ *next_ret = parent;
+ return NULL;
+}
+
+void rb_free_nodes(struct rb_root *root, rb_free_node free_node)
+{
+ struct rb_node *node;
+
+ while ((node = rb_first(root))) {
+ rb_erase(node, root);
+ free_node(node);
+ }
+}
diff --git a/rbtree-utils.h b/rbtree-utils.h
new file mode 100644
index 0000000..7298c72
--- /dev/null
+++ b/rbtree-utils.h
@@ -0,0 +1,45 @@
+/*
+ * Copyright (C) 2014 Facebook. 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.
+ */
+
+#ifndef __RBTREE_UTILS__
+#define __RBTREE_UTILS__
+
+#include "rbtree.h"
+
+/* The common insert/search/free functions */
+typedef int (*rb_compare_nodes)(struct rb_node *node1, struct rb_node *node2);
+typedef int (*rb_compare_keys)(struct rb_node *node, void *key);
+typedef void (*rb_free_node)(struct rb_node *node);
+
+int rb_insert(struct rb_root *root, struct rb_node *node,
+ rb_compare_nodes comp);
+/*
+ * In some cases, we need return the next node if we don't find the node we
+ * specify. At this time, we can use next_ret.
+ */
+struct rb_node *rb_search(struct rb_root *root, void *key, rb_compare_keys comp,
+ struct rb_node **next_ret);
+void rb_free_nodes(struct rb_root *root, rb_free_node free_node);
+
+#define FREE_RB_BASED_TREE(name, free_func) \
+static void free_##name##_tree(struct rb_root *root) \
+{ \
+ rb_free_nodes(root, free_func); \
+}
+
+#endif
diff --git a/rbtree.c b/rbtree.c
index 4c06b0c..6ad800f 100644
--- a/rbtree.c
+++ b/rbtree.c
@@ -387,66 +387,3 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
/* Copy the pointers/colour from the victim to the replacement */
*new = *victim;
}
-
-int rb_insert(struct rb_root *root, struct rb_node *node,
- rb_compare_nodes comp)
-{
- struct rb_node **p = &root->rb_node;
- struct rb_node *parent = NULL;
- int ret;
-
- while(*p) {
- parent = *p;
-
- ret = comp(parent, node);
- if (ret < 0)
- p = &(*p)->rb_left;
- else if (ret > 0)
- p = &(*p)->rb_right;
- else
- return -EEXIST;
- }
-
- rb_link_node(node, parent, p);
- rb_insert_color(node, root);
- return 0;
-}
-
-struct rb_node *rb_search(struct rb_root *root, void *key, rb_compare_keys comp,
- struct rb_node **next_ret)
-{
- struct rb_node *n = root->rb_node;
- struct rb_node *parent = NULL;
- int ret = 0;
-
- while(n) {
- parent = n;
-
- ret = comp(n, key);
- if (ret < 0)
- n = n->rb_left;
- else if (ret > 0)
- n = n->rb_right;
- else
- return n;
- }
-
- if (!next_ret)
- return NULL;
-
- if (parent && ret > 0)
- parent = rb_next(parent);
-
- *next_ret = parent;
- return NULL;
-}
-
-void rb_free_nodes(struct rb_root *root, rb_free_node free_node)
-{
- struct rb_node *node;
-
- while ((node = rb_first(root))) {
- rb_erase(node, root);
- free_node(node);
- }
-}
diff --git a/rbtree.h b/rbtree.h
index 48e5157..3add424 100644
--- a/rbtree.h
+++ b/rbtree.h
@@ -157,26 +157,4 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
*rb_link = node;
}
-
-/* The common insert/search/free functions */
-typedef int (*rb_compare_nodes)(struct rb_node *node1, struct rb_node *node2);
-typedef int (*rb_compare_keys)(struct rb_node *node, void *key);
-typedef void (*rb_free_node)(struct rb_node *node);
-
-int rb_insert(struct rb_root *root, struct rb_node *node,
- rb_compare_nodes comp);
-/*
- * In some cases, we need return the next node if we don't find the node we
- * specify. At this time, we can use next_ret.
- */
-struct rb_node *rb_search(struct rb_root *root, void *key, rb_compare_keys comp,
- struct rb_node **next_ret);
-void rb_free_nodes(struct rb_root *root, rb_free_node free_node);
-
-#define FREE_RB_BASED_TREE(name, free_func) \
-static void free_##name##_tree(struct rb_root *root) \
-{ \
- rb_free_nodes(root, free_func); \
-}
-
#endif /* _LINUX_RBTREE_H */
--
1.8.3.1
^ permalink raw reply related [flat|nested] 12+ messages in thread* [PATCH 04/12] Btrfs-progs: update rbtree libs
2014-10-10 20:57 Btrfs-progs: fix horrible things Josef Bacik
` (2 preceding siblings ...)
2014-10-10 20:57 ` [PATCH 03/12] Btrfs-progs: break out rbtree util functions Josef Bacik
@ 2014-10-10 20:57 ` Josef Bacik
2014-10-10 20:57 ` [PATCH 05/12] Btrfs-progs: lookup all roots that point to a corrupt block Josef Bacik
` (6 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Josef Bacik @ 2014-10-10 20:57 UTC (permalink / raw)
To: linux-btrfs
While debugging a broken fs we were seeing hangs in the rb_erase loops. The
rbtree was simple and wasn't corrupted so it appeared to be a bug in our rbtree
library. Updating to the kernels latest rbtree code made the infinite loop go
away, so pull it back. Thanks,
Signed-off-by: Josef Bacik <jbacik@fb.com>
---
kerncompat.h | 5 +
rbtree.c | 667 +++++++++++++++++++++++++++++++++--------------------
rbtree.h | 142 ++++--------
rbtree_augmented.h | 231 +++++++++++++++++++
4 files changed, 695 insertions(+), 350 deletions(-)
create mode 100644 rbtree_augmented.h
diff --git a/kerncompat.h b/kerncompat.h
index ea34936..a1336de 100644
--- a/kerncompat.h
+++ b/kerncompat.h
@@ -330,6 +330,11 @@ struct __una_u64 { __le64 x; } __attribute__((__packed__));
#define put_unaligned_le64(val,p) (((struct __una_u64 *)(p))->x = cpu_to_le64(val))
#endif
+#ifndef true
+#define true 1
+#define false 0
+#endif
+
#ifndef noinline
#define noinline
#endif
diff --git a/rbtree.c b/rbtree.c
index 6ad800f..92590a5 100644
--- a/rbtree.c
+++ b/rbtree.c
@@ -2,7 +2,8 @@
Red Black Trees
(C) 1999 Andrea Arcangeli <andrea@suse.de>
(C) 2002 David Woodhouse <dwmw2@infradead.org>
-
+ (C) 2012 Michel Lespinasse <walken@google.com>
+
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
@@ -20,276 +21,396 @@
linux/lib/rbtree.c
*/
-#include "rbtree.h"
-
-static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
-{
- struct rb_node *right = node->rb_right;
- struct rb_node *parent = rb_parent(node);
+#include "rbtree_augmented.h"
- if ((node->rb_right = right->rb_left))
- rb_set_parent(right->rb_left, node);
- right->rb_left = node;
-
- rb_set_parent(right, parent);
+/*
+ * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree
+ *
+ * 1) A node is either red or black
+ * 2) The root is black
+ * 3) All leaves (NULL) are black
+ * 4) Both children of every red node are black
+ * 5) Every simple path from root to leaves contains the same number
+ * of black nodes.
+ *
+ * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
+ * consecutive red nodes in a path and every red node is therefore followed by
+ * a black. So if B is the number of black nodes on every simple path (as per
+ * 5), then the longest possible path due to 4 is 2B.
+ *
+ * We shall indicate color with case, where black nodes are uppercase and red
+ * nodes will be lowercase. Unknown color nodes shall be drawn as red within
+ * parentheses and have some accompanying text comment.
+ */
- if (parent)
- {
- if (node == parent->rb_left)
- parent->rb_left = right;
- else
- parent->rb_right = right;
- }
- else
- root->rb_node = right;
- rb_set_parent(node, right);
+static inline void rb_set_black(struct rb_node *rb)
+{
+ rb->__rb_parent_color |= RB_BLACK;
}
-static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
+static inline struct rb_node *rb_red_parent(struct rb_node *red)
{
- struct rb_node *left = node->rb_left;
- struct rb_node *parent = rb_parent(node);
-
- if ((node->rb_left = left->rb_right))
- rb_set_parent(left->rb_right, node);
- left->rb_right = node;
-
- rb_set_parent(left, parent);
+ return (struct rb_node *)red->__rb_parent_color;
+}
- if (parent)
- {
- if (node == parent->rb_right)
- parent->rb_right = left;
- else
- parent->rb_left = left;
- }
- else
- root->rb_node = left;
- rb_set_parent(node, left);
+/*
+ * Helper function for rotations:
+ * - old's parent and color get assigned to new
+ * - old gets assigned new as a parent and 'color' as a color.
+ */
+static inline void
+__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
+ struct rb_root *root, int color)
+{
+ struct rb_node *parent = rb_parent(old);
+ new->__rb_parent_color = old->__rb_parent_color;
+ rb_set_parent_color(old, new, color);
+ __rb_change_child(old, new, parent, root);
}
-void rb_insert_color(struct rb_node *node, struct rb_root *root)
+static __always_inline void
+__rb_insert(struct rb_node *node, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
- struct rb_node *parent, *gparent;
-
- while ((parent = rb_parent(node)) && rb_is_red(parent))
- {
- gparent = rb_parent(parent);
-
- if (parent == gparent->rb_left)
- {
- {
- register struct rb_node *uncle = gparent->rb_right;
- if (uncle && rb_is_red(uncle))
- {
- rb_set_black(uncle);
- rb_set_black(parent);
- rb_set_red(gparent);
- node = gparent;
- continue;
- }
+ struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
+
+ while (true) {
+ /*
+ * Loop invariant: node is red
+ *
+ * If there is a black parent, we are done.
+ * Otherwise, take some corrective action as we don't
+ * want a red root or two consecutive red nodes.
+ */
+ if (!parent) {
+ rb_set_parent_color(node, NULL, RB_BLACK);
+ break;
+ } else if (rb_is_black(parent))
+ break;
+
+ gparent = rb_red_parent(parent);
+
+ tmp = gparent->rb_right;
+ if (parent != tmp) { /* parent == gparent->rb_left */
+ if (tmp && rb_is_red(tmp)) {
+ /*
+ * Case 1 - color flips
+ *
+ * G g
+ * / \ / \
+ * p u --> P U
+ * / /
+ * n n
+ *
+ * However, since g's parent might be red, and
+ * 4) does not allow this, we need to recurse
+ * at g.
+ */
+ rb_set_parent_color(tmp, gparent, RB_BLACK);
+ rb_set_parent_color(parent, gparent, RB_BLACK);
+ node = gparent;
+ parent = rb_parent(node);
+ rb_set_parent_color(node, parent, RB_RED);
+ continue;
}
- if (parent->rb_right == node)
- {
- register struct rb_node *tmp;
- __rb_rotate_left(parent, root);
- tmp = parent;
+ tmp = parent->rb_right;
+ if (node == tmp) {
+ /*
+ * Case 2 - left rotate at parent
+ *
+ * G G
+ * / \ / \
+ * p U --> n U
+ * \ /
+ * n p
+ *
+ * This still leaves us in violation of 4), the
+ * continuation into Case 3 will fix that.
+ */
+ parent->rb_right = tmp = node->rb_left;
+ node->rb_left = parent;
+ if (tmp)
+ rb_set_parent_color(tmp, parent,
+ RB_BLACK);
+ rb_set_parent_color(parent, node, RB_RED);
+ augment_rotate(parent, node);
parent = node;
- node = tmp;
+ tmp = node->rb_right;
}
- rb_set_black(parent);
- rb_set_red(gparent);
- __rb_rotate_right(gparent, root);
+ /*
+ * Case 3 - right rotate at gparent
+ *
+ * G P
+ * / \ / \
+ * p U --> n g
+ * / \
+ * n U
+ */
+ gparent->rb_left = tmp; /* == parent->rb_right */
+ parent->rb_right = gparent;
+ if (tmp)
+ rb_set_parent_color(tmp, gparent, RB_BLACK);
+ __rb_rotate_set_parents(gparent, parent, root, RB_RED);
+ augment_rotate(gparent, parent);
+ break;
} else {
- {
- register struct rb_node *uncle = gparent->rb_left;
- if (uncle && rb_is_red(uncle))
- {
- rb_set_black(uncle);
- rb_set_black(parent);
- rb_set_red(gparent);
- node = gparent;
- continue;
- }
+ tmp = gparent->rb_left;
+ if (tmp && rb_is_red(tmp)) {
+ /* Case 1 - color flips */
+ rb_set_parent_color(tmp, gparent, RB_BLACK);
+ rb_set_parent_color(parent, gparent, RB_BLACK);
+ node = gparent;
+ parent = rb_parent(node);
+ rb_set_parent_color(node, parent, RB_RED);
+ continue;
}
- if (parent->rb_left == node)
- {
- register struct rb_node *tmp;
- __rb_rotate_right(parent, root);
- tmp = parent;
+ tmp = parent->rb_left;
+ if (node == tmp) {
+ /* Case 2 - right rotate at parent */
+ parent->rb_left = tmp = node->rb_right;
+ node->rb_right = parent;
+ if (tmp)
+ rb_set_parent_color(tmp, parent,
+ RB_BLACK);
+ rb_set_parent_color(parent, node, RB_RED);
+ augment_rotate(parent, node);
parent = node;
- node = tmp;
+ tmp = node->rb_left;
}
- rb_set_black(parent);
- rb_set_red(gparent);
- __rb_rotate_left(gparent, root);
+ /* Case 3 - left rotate at gparent */
+ gparent->rb_right = tmp; /* == parent->rb_left */
+ parent->rb_left = gparent;
+ if (tmp)
+ rb_set_parent_color(tmp, gparent, RB_BLACK);
+ __rb_rotate_set_parents(gparent, parent, root, RB_RED);
+ augment_rotate(gparent, parent);
+ break;
}
}
-
- rb_set_black(root->rb_node);
}
-static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
- struct rb_root *root)
+/*
+ * Inline version for rb_erase() use - we want to be able to inline
+ * and eliminate the dummy_rotate callback there
+ */
+static __always_inline void
+____rb_erase_color(struct rb_node *parent, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{
- struct rb_node *other;
-
- while ((!node || rb_is_black(node)) && node != root->rb_node)
- {
- if (parent->rb_left == node)
- {
- other = parent->rb_right;
- if (rb_is_red(other))
- {
- rb_set_black(other);
- rb_set_red(parent);
- __rb_rotate_left(parent, root);
- other = parent->rb_right;
- }
- if ((!other->rb_left || rb_is_black(other->rb_left)) &&
- (!other->rb_right || rb_is_black(other->rb_right)))
- {
- rb_set_red(other);
- node = parent;
- parent = rb_parent(node);
+ struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
+
+ while (true) {
+ /*
+ * Loop invariants:
+ * - node is black (or NULL on first iteration)
+ * - node is not the root (parent is not NULL)
+ * - All leaf paths going through parent and node have a
+ * black node count that is 1 lower than other leaf paths.
+ */
+ sibling = parent->rb_right;
+ if (node != sibling) { /* node == parent->rb_left */
+ if (rb_is_red(sibling)) {
+ /*
+ * Case 1 - left rotate at parent
+ *
+ * P S
+ * / \ / \
+ * N s --> p Sr
+ * / \ / \
+ * Sl Sr N Sl
+ */
+ parent->rb_right = tmp1 = sibling->rb_left;
+ sibling->rb_left = parent;
+ rb_set_parent_color(tmp1, parent, RB_BLACK);
+ __rb_rotate_set_parents(parent, sibling, root,
+ RB_RED);
+ augment_rotate(parent, sibling);
+ sibling = tmp1;
}
- else
- {
- if (!other->rb_right || rb_is_black(other->rb_right))
- {
- struct rb_node *o_left;
- if ((o_left = other->rb_left))
- rb_set_black(o_left);
- rb_set_red(other);
- __rb_rotate_right(other, root);
- other = parent->rb_right;
+ tmp1 = sibling->rb_right;
+ if (!tmp1 || rb_is_black(tmp1)) {
+ tmp2 = sibling->rb_left;
+ if (!tmp2 || rb_is_black(tmp2)) {
+ /*
+ * Case 2 - sibling color flip
+ * (p could be either color here)
+ *
+ * (p) (p)
+ * / \ / \
+ * N S --> N s
+ * / \ / \
+ * Sl Sr Sl Sr
+ *
+ * This leaves us violating 5) which
+ * can be fixed by flipping p to black
+ * if it was red, or by recursing at p.
+ * p is red when coming from Case 1.
+ */
+ rb_set_parent_color(sibling, parent,
+ RB_RED);
+ if (rb_is_red(parent))
+ rb_set_black(parent);
+ else {
+ node = parent;
+ parent = rb_parent(node);
+ if (parent)
+ continue;
+ }
+ break;
}
- rb_set_color(other, rb_color(parent));
- rb_set_black(parent);
- if (other->rb_right)
- rb_set_black(other->rb_right);
- __rb_rotate_left(parent, root);
- node = root->rb_node;
- break;
+ /*
+ * Case 3 - right rotate at sibling
+ * (p could be either color here)
+ *
+ * (p) (p)
+ * / \ / \
+ * N S --> N Sl
+ * / \ \
+ * sl Sr s
+ * \
+ * Sr
+ */
+ sibling->rb_left = tmp1 = tmp2->rb_right;
+ tmp2->rb_right = sibling;
+ parent->rb_right = tmp2;
+ if (tmp1)
+ rb_set_parent_color(tmp1, sibling,
+ RB_BLACK);
+ augment_rotate(sibling, tmp2);
+ tmp1 = sibling;
+ sibling = tmp2;
}
- }
- else
- {
- other = parent->rb_left;
- if (rb_is_red(other))
- {
- rb_set_black(other);
- rb_set_red(parent);
- __rb_rotate_right(parent, root);
- other = parent->rb_left;
- }
- if ((!other->rb_left || rb_is_black(other->rb_left)) &&
- (!other->rb_right || rb_is_black(other->rb_right)))
- {
- rb_set_red(other);
- node = parent;
- parent = rb_parent(node);
+ /*
+ * Case 4 - left rotate at parent + color flips
+ * (p and sl could be either color here.
+ * After rotation, p becomes black, s acquires
+ * p's color, and sl keeps its color)
+ *
+ * (p) (s)
+ * / \ / \
+ * N S --> P Sr
+ * / \ / \
+ * (sl) sr N (sl)
+ */
+ parent->rb_right = tmp2 = sibling->rb_left;
+ sibling->rb_left = parent;
+ rb_set_parent_color(tmp1, sibling, RB_BLACK);
+ if (tmp2)
+ rb_set_parent(tmp2, parent);
+ __rb_rotate_set_parents(parent, sibling, root,
+ RB_BLACK);
+ augment_rotate(parent, sibling);
+ break;
+ } else {
+ sibling = parent->rb_left;
+ if (rb_is_red(sibling)) {
+ /* Case 1 - right rotate at parent */
+ parent->rb_left = tmp1 = sibling->rb_right;
+ sibling->rb_right = parent;
+ rb_set_parent_color(tmp1, parent, RB_BLACK);
+ __rb_rotate_set_parents(parent, sibling, root,
+ RB_RED);
+ augment_rotate(parent, sibling);
+ sibling = tmp1;
}
- else
- {
- if (!other->rb_left || rb_is_black(other->rb_left))
- {
- register struct rb_node *o_right;
- if ((o_right = other->rb_right))
- rb_set_black(o_right);
- rb_set_red(other);
- __rb_rotate_left(other, root);
- other = parent->rb_left;
+ tmp1 = sibling->rb_left;
+ if (!tmp1 || rb_is_black(tmp1)) {
+ tmp2 = sibling->rb_right;
+ if (!tmp2 || rb_is_black(tmp2)) {
+ /* Case 2 - sibling color flip */
+ rb_set_parent_color(sibling, parent,
+ RB_RED);
+ if (rb_is_red(parent))
+ rb_set_black(parent);
+ else {
+ node = parent;
+ parent = rb_parent(node);
+ if (parent)
+ continue;
+ }
+ break;
}
- rb_set_color(other, rb_color(parent));
- rb_set_black(parent);
- if (other->rb_left)
- rb_set_black(other->rb_left);
- __rb_rotate_right(parent, root);
- node = root->rb_node;
- break;
+ /* Case 3 - right rotate at sibling */
+ sibling->rb_right = tmp1 = tmp2->rb_left;
+ tmp2->rb_left = sibling;
+ parent->rb_left = tmp2;
+ if (tmp1)
+ rb_set_parent_color(tmp1, sibling,
+ RB_BLACK);
+ augment_rotate(sibling, tmp2);
+ tmp1 = sibling;
+ sibling = tmp2;
}
+ /* Case 4 - left rotate at parent + color flips */
+ parent->rb_left = tmp2 = sibling->rb_right;
+ sibling->rb_right = parent;
+ rb_set_parent_color(tmp1, sibling, RB_BLACK);
+ if (tmp2)
+ rb_set_parent(tmp2, parent);
+ __rb_rotate_set_parents(parent, sibling, root,
+ RB_BLACK);
+ augment_rotate(parent, sibling);
+ break;
}
}
- if (node)
- rb_set_black(node);
+}
+
+/* Non-inline version for rb_erase_augmented() use */
+void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
+{
+ ____rb_erase_color(parent, root, augment_rotate);
+}
+
+/*
+ * Non-augmented rbtree manipulation functions.
+ *
+ * We use dummy augmented callbacks here, and have the compiler optimize them
+ * out of the rb_insert_color() and rb_erase() function definitions.
+ */
+
+static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) {}
+static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {}
+static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}
+
+static const struct rb_augment_callbacks dummy_callbacks = {
+ dummy_propagate, dummy_copy, dummy_rotate
+};
+
+void rb_insert_color(struct rb_node *node, struct rb_root *root)
+{
+ __rb_insert(node, root, dummy_rotate);
}
void rb_erase(struct rb_node *node, struct rb_root *root)
{
- struct rb_node *child, *parent;
- int color;
-
- if (!node->rb_left)
- child = node->rb_right;
- else if (!node->rb_right)
- child = node->rb_left;
- else
- {
- struct rb_node *old = node, *left;
-
- node = node->rb_right;
- while ((left = node->rb_left) != NULL)
- node = left;
- child = node->rb_right;
- parent = rb_parent(node);
- color = rb_color(node);
-
- if (child)
- rb_set_parent(child, parent);
- if (parent == old) {
- parent->rb_right = child;
- parent = node;
- } else
- parent->rb_left = child;
-
- node->rb_parent_color = old->rb_parent_color;
- node->rb_right = old->rb_right;
- node->rb_left = old->rb_left;
-
- if (rb_parent(old))
- {
- if (rb_parent(old)->rb_left == old)
- rb_parent(old)->rb_left = node;
- else
- rb_parent(old)->rb_right = node;
- } else
- root->rb_node = node;
-
- rb_set_parent(old->rb_left, node);
- if (old->rb_right)
- rb_set_parent(old->rb_right, node);
- goto color;
- }
+ struct rb_node *rebalance;
+ rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
+ if (rebalance)
+ ____rb_erase_color(rebalance, root, dummy_rotate);
+}
- parent = rb_parent(node);
- color = rb_color(node);
-
- if (child)
- rb_set_parent(child, parent);
- if (parent)
- {
- if (parent->rb_left == node)
- parent->rb_left = child;
- else
- parent->rb_right = child;
- }
- else
- root->rb_node = child;
+/*
+ * Augmented rbtree manipulation functions.
+ *
+ * This instantiates the same __always_inline functions as in the non-augmented
+ * case, but this time with user-defined callbacks.
+ */
- color:
- if (color == RB_BLACK)
- __rb_erase_color(child, parent, root);
+void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
+{
+ __rb_insert(node, root, augment_rotate);
}
/*
* This function returns the first node (in sort order) of the tree.
*/
-struct rb_node *rb_first(struct rb_root *root)
+struct rb_node *rb_first(const struct rb_root *root)
{
struct rb_node *n;
@@ -301,7 +422,7 @@ struct rb_node *rb_first(struct rb_root *root)
return n;
}
-struct rb_node *rb_last(struct rb_root *root)
+struct rb_node *rb_last(const struct rb_root *root)
{
struct rb_node *n;
@@ -313,52 +434,59 @@ struct rb_node *rb_last(struct rb_root *root)
return n;
}
-struct rb_node *rb_next(struct rb_node *node)
+struct rb_node *rb_next(const struct rb_node *node)
{
struct rb_node *parent;
- if (rb_parent(node) == node)
+ if (RB_EMPTY_NODE(node))
return NULL;
- /* If we have a right-hand child, go down and then left as far
- as we can. */
+ /*
+ * If we have a right-hand child, go down and then left as far
+ * as we can.
+ */
if (node->rb_right) {
node = node->rb_right;
while (node->rb_left)
node=node->rb_left;
- return node;
+ return (struct rb_node *)node;
}
- /* No right-hand children. Everything down and left is
- smaller than us, so any 'next' node must be in the general
- direction of our parent. Go up the tree; any time the
- ancestor is a right-hand child of its parent, keep going
- up. First time it's a left-hand child of its parent, said
- parent is our 'next' node. */
+ /*
+ * No right-hand children. Everything down and left is smaller than us,
+ * so any 'next' node must be in the general direction of our parent.
+ * Go up the tree; any time the ancestor is a right-hand child of its
+ * parent, keep going up. First time it's a left-hand child of its
+ * parent, said parent is our 'next' node.
+ */
while ((parent = rb_parent(node)) && node == parent->rb_right)
node = parent;
return parent;
}
-struct rb_node *rb_prev(struct rb_node *node)
+struct rb_node *rb_prev(const struct rb_node *node)
{
struct rb_node *parent;
- if (rb_parent(node) == node)
+ if (RB_EMPTY_NODE(node))
return NULL;
- /* If we have a left-hand child, go down and then right as far
- as we can. */
+ /*
+ * If we have a left-hand child, go down and then right as far
+ * as we can.
+ */
if (node->rb_left) {
node = node->rb_left;
while (node->rb_right)
node=node->rb_right;
- return node;
+ return (struct rb_node *)node;
}
- /* No left-hand children. Go up till we find an ancestor which
- is a right-hand child of its parent */
+ /*
+ * No left-hand children. Go up till we find an ancestor which
+ * is a right-hand child of its parent.
+ */
while ((parent = rb_parent(node)) && node == parent->rb_left)
node = parent;
@@ -371,14 +499,7 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
struct rb_node *parent = rb_parent(victim);
/* Set the surrounding nodes to point to the replacement */
- if (parent) {
- if (victim == parent->rb_left)
- parent->rb_left = new;
- else
- parent->rb_right = new;
- } else {
- root->rb_node = new;
- }
+ __rb_change_child(victim, new, parent, root);
if (victim->rb_left)
rb_set_parent(victim->rb_left, new);
if (victim->rb_right)
@@ -387,3 +508,41 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
/* Copy the pointers/colour from the victim to the replacement */
*new = *victim;
}
+
+static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
+{
+ for (;;) {
+ if (node->rb_left)
+ node = node->rb_left;
+ else if (node->rb_right)
+ node = node->rb_right;
+ else
+ return (struct rb_node *)node;
+ }
+}
+
+struct rb_node *rb_next_postorder(const struct rb_node *node)
+{
+ const struct rb_node *parent;
+ if (!node)
+ return NULL;
+ parent = rb_parent(node);
+
+ /* If we're sitting on node, we've already seen our children */
+ if (parent && node == parent->rb_left && parent->rb_right) {
+ /* If we are the parent's left node, go to the parent's right
+ * node then all the way down to the left */
+ return rb_left_deepest_node(parent->rb_right);
+ } else
+ /* Otherwise we are the parent's right node, and the parent
+ * should be next */
+ return (struct rb_node *)parent;
+}
+
+struct rb_node *rb_first_postorder(const struct rb_root *root)
+{
+ if (!root->rb_node)
+ return NULL;
+
+ return rb_left_deepest_node(root->rb_node);
+}
diff --git a/rbtree.h b/rbtree.h
index 3add424..03c06d8 100644
--- a/rbtree.h
+++ b/rbtree.h
@@ -23,72 +23,7 @@
I know it's not the cleaner way, but in C (not in C++) to get
performances and genericity...
- Some example of insert and search follows here. The search is a plain
- normal search over an ordered tree. The insert instead must be implemented
- int two steps: as first thing the code must insert the element in
- order as a red leaf in the tree, then the support library function
- rb_insert_color() must be called. Such function will do the
- not trivial work to rebalance the rbtree if necessary.
-
------------------------------------------------------------------------
-static inline struct page * rb_search_page_cache(struct inode * inode,
- unsigned long offset)
-{
- struct rb_node * n = inode->i_rb_page_cache.rb_node;
- struct page * page;
-
- while (n)
- {
- page = rb_entry(n, struct page, rb_page_cache);
-
- if (offset < page->offset)
- n = n->rb_left;
- else if (offset > page->offset)
- n = n->rb_right;
- else
- return page;
- }
- return NULL;
-}
-
-static inline struct page * __rb_insert_page_cache(struct inode * inode,
- unsigned long offset,
- struct rb_node * node)
-{
- struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
- struct rb_node * parent = NULL;
- struct page * page;
-
- while (*p)
- {
- parent = *p;
- page = rb_entry(parent, struct page, rb_page_cache);
-
- if (offset < page->offset)
- p = &(*p)->rb_left;
- else if (offset > page->offset)
- p = &(*p)->rb_right;
- else
- return page;
- }
-
- rb_link_node(node, parent, p);
-
- return NULL;
-}
-
-static inline struct page * rb_insert_page_cache(struct inode * inode,
- unsigned long offset,
- struct rb_node * node)
-{
- struct page * ret;
- if ((ret = __rb_insert_page_cache(inode, offset, node)))
- goto out;
- rb_insert_color(node, &inode->i_rb_page_cache);
- out:
- return ret;
-}
------------------------------------------------------------------------
+ See Documentation/rbtree.txt for documentation and samples.
*/
#ifndef _LINUX_RBTREE_H
@@ -98,63 +33,78 @@ static inline struct page * rb_insert_page_cache(struct inode * inode,
#else
#include <btrfs/kerncompat.h>
#endif /* BTRFS_FLAT_INCLUDES */
-struct rb_node
-{
- unsigned long rb_parent_color;
-#define RB_RED 0
-#define RB_BLACK 1
+
+struct rb_node {
+ unsigned long __rb_parent_color;
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
/* The alignment might seem pointless, but allegedly CRIS needs it */
-struct rb_root
-{
+struct rb_root {
struct rb_node *rb_node;
};
-#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
-#define rb_color(r) ((r)->rb_parent_color & 1)
-#define rb_is_red(r) (!rb_color(r))
-#define rb_is_black(r) rb_color(r)
-#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
-#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
-static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
-{
- rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
-}
-static inline void rb_set_color(struct rb_node *rb, int color)
-{
- rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
-}
+#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
#define RB_ROOT (struct rb_root) { NULL, }
#define rb_entry(ptr, type, member) container_of(ptr, type, member)
-#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
-#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
-#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
+#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
+
+/* 'empty' nodes are nodes that are known not to be inserted in an rbree */
+#define RB_EMPTY_NODE(node) \
+ ((node)->__rb_parent_color == (unsigned long)(node))
+#define RB_CLEAR_NODE(node) \
+ ((node)->__rb_parent_color = (unsigned long)(node))
+
extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root *);
+
/* Find logical next and previous nodes in a tree */
-extern struct rb_node *rb_next(struct rb_node *);
-extern struct rb_node *rb_prev(struct rb_node *);
-extern struct rb_node *rb_first(struct rb_root *);
-extern struct rb_node *rb_last(struct rb_root *);
+extern struct rb_node *rb_next(const struct rb_node *);
+extern struct rb_node *rb_prev(const struct rb_node *);
+extern struct rb_node *rb_first(const struct rb_root *);
+extern struct rb_node *rb_last(const struct rb_root *);
+
+/* Postorder iteration - always visit the parent after its children */
+extern struct rb_node *rb_first_postorder(const struct rb_root *);
+extern struct rb_node *rb_next_postorder(const struct rb_node *);
/* Fast replacement of a single node without remove/rebalance/add/rebalance */
-extern void rb_replace_node(struct rb_node *victim, struct rb_node *xnew,
+extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
struct rb_root *root);
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
struct rb_node ** rb_link)
{
- node->rb_parent_color = (unsigned long )parent;
+ node->__rb_parent_color = (unsigned long)parent;
node->rb_left = node->rb_right = NULL;
*rb_link = node;
}
+
+#define rb_entry_safe(ptr, type, member) \
+ ({ typeof(ptr) ____ptr = (ptr); \
+ ____ptr ? rb_entry(____ptr, type, member) : NULL; \
+ })
+
+/**
+ * rbtree_postorder_for_each_entry_safe - iterate over rb_root in post order of
+ * given type safe against removal of rb_node entry
+ *
+ * @pos: the 'type *' to use as a loop cursor.
+ * @n: another 'type *' to use as temporary storage
+ * @root: 'rb_root *' of the rbtree.
+ * @field: the name of the rb_node field within 'type'.
+ */
+#define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \
+ for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
+ pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
+ typeof(*pos), field); 1; }); \
+ pos = n)
+
#endif /* _LINUX_RBTREE_H */
diff --git a/rbtree_augmented.h b/rbtree_augmented.h
new file mode 100644
index 0000000..079eb97
--- /dev/null
+++ b/rbtree_augmented.h
@@ -0,0 +1,231 @@
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <andrea@suse.de>
+ (C) 2002 David Woodhouse <dwmw2@infradead.org>
+ (C) 2012 Michel Lespinasse <walken@google.com>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ 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 02111-1307 USA
+
+ linux/include/linux/rbtree_augmented.h
+*/
+
+#ifndef _LINUX_RBTREE_AUGMENTED_H
+#define _LINUX_RBTREE_AUGMENTED_H
+
+#include "rbtree.h"
+
+/*
+ * Please note - only struct rb_augment_callbacks and the prototypes for
+ * rb_insert_augmented() and rb_erase_augmented() are intended to be public.
+ * The rest are implementation details you are not expected to depend on.
+ *
+ * See Documentation/rbtree.txt for documentation and samples.
+ */
+
+struct rb_augment_callbacks {
+ void (*propagate)(struct rb_node *node, struct rb_node *stop);
+ void (*copy)(struct rb_node *old, struct rb_node *new);
+ void (*rotate)(struct rb_node *old, struct rb_node *new);
+};
+
+extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
+static inline void
+rb_insert_augmented(struct rb_node *node, struct rb_root *root,
+ const struct rb_augment_callbacks *augment)
+{
+ __rb_insert_augmented(node, root, augment->rotate);
+}
+
+#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, \
+ rbtype, rbaugmented, rbcompute) \
+static inline void \
+rbname ## _propagate(struct rb_node *rb, struct rb_node *stop) \
+{ \
+ while (rb != stop) { \
+ rbstruct *node = rb_entry(rb, rbstruct, rbfield); \
+ rbtype augmented = rbcompute(node); \
+ if (node->rbaugmented == augmented) \
+ break; \
+ node->rbaugmented = augmented; \
+ rb = rb_parent(&node->rbfield); \
+ } \
+} \
+static inline void \
+rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new) \
+{ \
+ rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
+ rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
+ new->rbaugmented = old->rbaugmented; \
+} \
+static void \
+rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new) \
+{ \
+ rbstruct *old = rb_entry(rb_old, rbstruct, rbfield); \
+ rbstruct *new = rb_entry(rb_new, rbstruct, rbfield); \
+ new->rbaugmented = old->rbaugmented; \
+ old->rbaugmented = rbcompute(old); \
+} \
+rbstatic const struct rb_augment_callbacks rbname = { \
+ rbname ## _propagate, rbname ## _copy, rbname ## _rotate \
+};
+
+
+#define RB_RED 0
+#define RB_BLACK 1
+
+#define __rb_parent(pc) ((struct rb_node *)(pc & ~3))
+
+#define __rb_color(pc) ((pc) & 1)
+#define __rb_is_black(pc) __rb_color(pc)
+#define __rb_is_red(pc) (!__rb_color(pc))
+#define rb_color(rb) __rb_color((rb)->__rb_parent_color)
+#define rb_is_red(rb) __rb_is_red((rb)->__rb_parent_color)
+#define rb_is_black(rb) __rb_is_black((rb)->__rb_parent_color)
+
+static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+ rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
+}
+
+static inline void rb_set_parent_color(struct rb_node *rb,
+ struct rb_node *p, int color)
+{
+ rb->__rb_parent_color = (unsigned long)p | color;
+}
+
+static inline void
+__rb_change_child(struct rb_node *old, struct rb_node *new,
+ struct rb_node *parent, struct rb_root *root)
+{
+ if (parent) {
+ if (parent->rb_left == old)
+ parent->rb_left = new;
+ else
+ parent->rb_right = new;
+ } else
+ root->rb_node = new;
+}
+
+extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
+ void (*augment_rotate)(struct rb_node *old, struct rb_node *new));
+
+static __always_inline struct rb_node *
+__rb_erase_augmented(struct rb_node *node, struct rb_root *root,
+ const struct rb_augment_callbacks *augment)
+{
+ struct rb_node *child = node->rb_right, *tmp = node->rb_left;
+ struct rb_node *parent, *rebalance;
+ unsigned long pc;
+
+ if (!tmp) {
+ /*
+ * Case 1: node to erase has no more than 1 child (easy!)
+ *
+ * Note that if there is one child it must be red due to 5)
+ * and node must be black due to 4). We adjust colors locally
+ * so as to bypass __rb_erase_color() later on.
+ */
+ pc = node->__rb_parent_color;
+ parent = __rb_parent(pc);
+ __rb_change_child(node, child, parent, root);
+ if (child) {
+ child->__rb_parent_color = pc;
+ rebalance = NULL;
+ } else
+ rebalance = __rb_is_black(pc) ? parent : NULL;
+ tmp = parent;
+ } else if (!child) {
+ /* Still case 1, but this time the child is node->rb_left */
+ tmp->__rb_parent_color = pc = node->__rb_parent_color;
+ parent = __rb_parent(pc);
+ __rb_change_child(node, tmp, parent, root);
+ rebalance = NULL;
+ tmp = parent;
+ } else {
+ struct rb_node *successor = child, *child2;
+ tmp = child->rb_left;
+ if (!tmp) {
+ /*
+ * Case 2: node's successor is its right child
+ *
+ * (n) (s)
+ * / \ / \
+ * (x) (s) -> (x) (c)
+ * \
+ * (c)
+ */
+ parent = successor;
+ child2 = successor->rb_right;
+ augment->copy(node, successor);
+ } else {
+ /*
+ * Case 3: node's successor is leftmost under
+ * node's right child subtree
+ *
+ * (n) (s)
+ * / \ / \
+ * (x) (y) -> (x) (y)
+ * / /
+ * (p) (p)
+ * / /
+ * (s) (c)
+ * \
+ * (c)
+ */
+ do {
+ parent = successor;
+ successor = tmp;
+ tmp = tmp->rb_left;
+ } while (tmp);
+ parent->rb_left = child2 = successor->rb_right;
+ successor->rb_right = child;
+ rb_set_parent(child, successor);
+ augment->copy(node, successor);
+ augment->propagate(parent, successor);
+ }
+
+ successor->rb_left = tmp = node->rb_left;
+ rb_set_parent(tmp, successor);
+
+ pc = node->__rb_parent_color;
+ tmp = __rb_parent(pc);
+ __rb_change_child(node, successor, tmp, root);
+ if (child2) {
+ successor->__rb_parent_color = pc;
+ rb_set_parent_color(child2, parent, RB_BLACK);
+ rebalance = NULL;
+ } else {
+ unsigned long pc2 = successor->__rb_parent_color;
+ successor->__rb_parent_color = pc;
+ rebalance = __rb_is_black(pc2) ? parent : NULL;
+ }
+ tmp = successor;
+ }
+
+ augment->propagate(tmp, NULL);
+ return rebalance;
+}
+
+static __always_inline void
+rb_erase_augmented(struct rb_node *node, struct rb_root *root,
+ const struct rb_augment_callbacks *augment)
+{
+ struct rb_node *rebalance = __rb_erase_augmented(node, root, augment);
+ if (rebalance)
+ __rb_erase_color(rebalance, root, augment->rotate);
+}
+
+#endif /* _LINUX_RBTREE_AUGMENTED_H */
--
1.8.3.1
^ permalink raw reply related [flat|nested] 12+ messages in thread* [PATCH 05/12] Btrfs-progs: lookup all roots that point to a corrupt block
2014-10-10 20:57 Btrfs-progs: fix horrible things Josef Bacik
` (3 preceding siblings ...)
2014-10-10 20:57 ` [PATCH 04/12] Btrfs-progs: update rbtree libs Josef Bacik
@ 2014-10-10 20:57 ` Josef Bacik
2014-10-10 20:57 ` [PATCH 06/12] Btrfs-progs: reset chunk state if we restart check Josef Bacik
` (5 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Josef Bacik @ 2014-10-10 20:57 UTC (permalink / raw)
To: linux-btrfs
If we have a corrupt block that multiple snapshots point to we will only fix the
guy who originally pointed to the block, and then simply loop forever because we
keep finding the same bad block. So instead lookup all roots that point to this
block, and then search down to the block for each root and fix the block in all
snapshots. Thanks,
Signed-off-by: Josef Bacik <jbacik@fb.com>
---
cmds-check.c | 143 +++++++++++++++++++++++++++++------------------------------
1 file changed, 70 insertions(+), 73 deletions(-)
diff --git a/cmds-check.c b/cmds-check.c
index ff9c0d5..1deef77 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -40,6 +40,8 @@
#include "btrfsck.h"
#include "qgroup-verify.h"
#include "rbtree-utils.h"
+#include "backref.h"
+#include "ulist.h"
static u64 bytes_used = 0;
static u64 total_csum_bytes = 0;
@@ -2554,42 +2556,14 @@ static int swap_values(struct btrfs_root *root, struct btrfs_path *path,
static int fix_key_order(struct btrfs_trans_handle *trans,
struct btrfs_root *root,
- struct extent_buffer *buf)
+ struct btrfs_path *path)
{
- struct btrfs_path *path;
+ struct extent_buffer *buf;
struct btrfs_key k1, k2;
int i;
- int level;
+ int level = path->lowest_level;
int ret;
- k1.objectid = btrfs_header_owner(buf);
- k1.type = BTRFS_ROOT_ITEM_KEY;
- k1.offset = (u64)-1;
-
- root = btrfs_read_fs_root(root->fs_info, &k1);
- if (IS_ERR(root))
- return -EIO;
-
- record_root_in_trans(trans, root);
-
- path = btrfs_alloc_path();
- if (!path)
- return -EIO;
-
- level = btrfs_header_level(buf);
- path->lowest_level = level;
- path->skip_check_block = 1;
- if (level)
- btrfs_node_key_to_cpu(buf, &k1, 0);
- else
- btrfs_item_key_to_cpu(buf, &k1, 0);
-
- ret = btrfs_search_slot(trans, root, &k1, path, 0, 1);
- if (ret) {
- btrfs_free_path(path);
- return -EIO;
- }
-
buf = path->nodes[level];
for (i = 0; i < btrfs_header_nritems(buf) - 1; i++) {
if (level) {
@@ -2607,8 +2581,6 @@ static int fix_key_order(struct btrfs_trans_handle *trans,
btrfs_mark_buffer_dirty(buf);
i = 0;
}
-
- btrfs_free_path(path);
return ret;
}
@@ -2650,43 +2622,15 @@ static int delete_bogus_item(struct btrfs_trans_handle *trans,
static int fix_item_offset(struct btrfs_trans_handle *trans,
struct btrfs_root *root,
- struct extent_buffer *buf)
+ struct btrfs_path *path)
{
- struct btrfs_path *path;
- struct btrfs_key k1;
+ struct extent_buffer *buf;
int i;
- int level;
- int ret;
-
- k1.objectid = btrfs_header_owner(buf);
- k1.type = BTRFS_ROOT_ITEM_KEY;
- k1.offset = (u64)-1;
-
- root = btrfs_read_fs_root(root->fs_info, &k1);
- if (IS_ERR(root))
- return -EIO;
-
- record_root_in_trans(trans, root);
-
- path = btrfs_alloc_path();
- if (!path)
- return -EIO;
-
- level = btrfs_header_level(buf);
- path->lowest_level = level;
- path->skip_check_block = 1;
- if (level)
- btrfs_node_key_to_cpu(buf, &k1, 0);
- else
- btrfs_item_key_to_cpu(buf, &k1, 0);
-
- ret = btrfs_search_slot(trans, root, &k1, path, 0, 1);
- if (ret) {
- btrfs_free_path(path);
- return -EIO;
- }
+ int ret = 0;
- buf = path->nodes[level];
+ /* We should only get this for leaves */
+ BUG_ON(path->lowest_level);
+ buf = path->nodes[0];
again:
for (i = 0; i < btrfs_header_nritems(buf); i++) {
unsigned int shift = 0, offset;
@@ -2742,7 +2686,6 @@ again:
* progs this can be changed to something nicer.
*/
BUG_ON(ret);
- btrfs_free_path(path);
return ret;
}
@@ -2755,11 +2698,65 @@ static int try_to_fix_bad_block(struct btrfs_trans_handle *trans,
struct extent_buffer *buf,
enum btrfs_tree_block_status status)
{
- if (status == BTRFS_TREE_BLOCK_BAD_KEY_ORDER)
- return fix_key_order(trans, root, buf);
- if (status == BTRFS_TREE_BLOCK_INVALID_OFFSETS)
- return fix_item_offset(trans, root, buf);
- return -EIO;
+ struct ulist *roots;
+ struct ulist_node *node;
+ struct btrfs_root *search_root;
+ struct btrfs_path *path;
+ struct ulist_iterator iter;
+ struct btrfs_key root_key, key;
+ int ret;
+
+ if (status != BTRFS_TREE_BLOCK_BAD_KEY_ORDER &&
+ status != BTRFS_TREE_BLOCK_INVALID_OFFSETS)
+ return -EIO;
+
+ path = btrfs_alloc_path();
+ if (!path)
+ return -EIO;
+
+ ret = btrfs_find_all_roots(trans, root->fs_info, buf->start,
+ 0, &roots);
+ if (ret) {
+ btrfs_free_path(path);
+ return -EIO;
+ }
+
+ ULIST_ITER_INIT(&iter);
+ while ((node = ulist_next(roots, &iter))) {
+ root_key.objectid = node->val;
+ root_key.type = BTRFS_ROOT_ITEM_KEY;
+ root_key.offset = (u64)-1;
+
+ search_root = btrfs_read_fs_root(root->fs_info, &root_key);
+ if (IS_ERR(root)) {
+ ret = -EIO;
+ break;
+ }
+
+ record_root_in_trans(trans, search_root);
+
+ path->lowest_level = btrfs_header_level(buf);
+ path->skip_check_block = 1;
+ if (path->lowest_level)
+ btrfs_node_key_to_cpu(buf, &key, 0);
+ else
+ btrfs_item_key_to_cpu(buf, &key, 0);
+ ret = btrfs_search_slot(trans, search_root, &key, path, 0, 1);
+ if (ret) {
+ ret = -EIO;
+ break;
+ }
+ if (status == BTRFS_TREE_BLOCK_BAD_KEY_ORDER)
+ ret = fix_key_order(trans, search_root, path);
+ else if (status == BTRFS_TREE_BLOCK_INVALID_OFFSETS)
+ ret = fix_item_offset(trans, search_root, path);
+ if (ret)
+ break;
+ btrfs_release_path(path);
+ }
+ ulist_free(roots);
+ btrfs_free_path(path);
+ return ret;
}
static int check_block(struct btrfs_trans_handle *trans,
--
1.8.3.1
^ permalink raw reply related [flat|nested] 12+ messages in thread* [PATCH 06/12] Btrfs-progs: reset chunk state if we restart check
2014-10-10 20:57 Btrfs-progs: fix horrible things Josef Bacik
` (4 preceding siblings ...)
2014-10-10 20:57 ` [PATCH 05/12] Btrfs-progs: lookup all roots that point to a corrupt block Josef Bacik
@ 2014-10-10 20:57 ` Josef Bacik
2014-10-10 20:57 ` [PATCH 07/12] Btrfs-progs: re-search tree root if it changes Josef Bacik
` (4 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Josef Bacik @ 2014-10-10 20:57 UTC (permalink / raw)
To: linux-btrfs
If we hid a corrupt block that we fix and we restart the fsck loop you will get
lots of noise about duplicate block groups and such. This is because we don't
clear the block group and chunk cache when we do this restart. This patch fixes
that, which is a little tricky since the structs are linked together with
various linked lists, but this passed with a user who was hitting this problem.
Thanks,
Signed-off-by: Josef Bacik <jbacik@fb.com>
---
cmds-check.c | 13 ++++++++++++-
1 file changed, 12 insertions(+), 1 deletion(-)
diff --git a/cmds-check.c b/cmds-check.c
index 1deef77..e81a26c 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -3270,6 +3270,8 @@ static void free_chunk_record(struct cache_extent *cache)
struct chunk_record *rec;
rec = container_of(cache, struct chunk_record, cache);
+ list_del_init(&rec->list);
+ list_del_init(&rec->dextents);
free(rec);
}
@@ -3306,6 +3308,7 @@ static void free_block_group_record(struct cache_extent *cache)
struct block_group_record *rec;
rec = container_of(cache, struct block_group_record, cache);
+ list_del_init(&rec->list);
free(rec);
}
@@ -3339,6 +3342,10 @@ static void free_device_extent_record(struct cache_extent *cache)
struct device_extent_record *rec;
rec = container_of(cache, struct device_extent_record, cache);
+ if (!list_empty(&rec->chunk_list))
+ list_del_init(&rec->chunk_list);
+ if (!list_empty(&rec->device_list))
+ list_del_init(&rec->device_list);
free(rec);
}
@@ -6051,7 +6058,7 @@ static int check_device_used(struct device_record *dev_rec,
if (dev_extent_rec->objectid != dev_rec->devid)
break;
- list_del(&dev_extent_rec->device_list);
+ list_del_init(&dev_extent_rec->device_list);
total_byte += dev_extent_rec->length;
cache = next_cache_extent(cache);
}
@@ -6280,6 +6287,10 @@ again:
free_extent_cache_tree(&pending);
free_extent_cache_tree(&reada);
free_extent_cache_tree(&nodes);
+ free_chunk_cache_tree(&chunk_cache);
+ free_block_group_tree(&block_group_cache);
+ free_device_cache_tree(&dev_cache);
+ free_device_extent_tree(&dev_extent_cache);
free_extent_record_cache(root->fs_info, &extent_cache);
goto again;
}
--
1.8.3.1
^ permalink raw reply related [flat|nested] 12+ messages in thread* [PATCH 07/12] Btrfs-progs: re-search tree root if it changes
2014-10-10 20:57 Btrfs-progs: fix horrible things Josef Bacik
` (5 preceding siblings ...)
2014-10-10 20:57 ` [PATCH 06/12] Btrfs-progs: reset chunk state if we restart check Josef Bacik
@ 2014-10-10 20:57 ` Josef Bacik
2014-10-10 20:57 ` [PATCH 08/12] Btrfs-progs: delete bogus dir indexes Josef Bacik
` (3 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Josef Bacik @ 2014-10-10 20:57 UTC (permalink / raw)
To: linux-btrfs
If we change something while scanning fs-roots we need to redo our search so
that we get valid root items and have valid root cache. Thanks,
Signed-off-by: Josef Bacik <jbacik@fb.com>
---
cmds-check.c | 10 ++++++++--
1 file changed, 8 insertions(+), 2 deletions(-)
diff --git a/cmds-check.c b/cmds-check.c
index e81a26c..9522077 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -2171,7 +2171,7 @@ static int check_fs_roots(struct btrfs_root *root,
struct btrfs_path path;
struct btrfs_key key;
struct walk_control wc;
- struct extent_buffer *leaf;
+ struct extent_buffer *leaf, *tree_node;
struct btrfs_root *tmp_root;
struct btrfs_root *tree_root = root->fs_info->tree_root;
int ret;
@@ -2186,13 +2186,19 @@ static int check_fs_roots(struct btrfs_root *root,
memset(&wc, 0, sizeof(wc));
cache_tree_init(&wc.shared);
btrfs_init_path(&path);
-
+again:
key.offset = 0;
key.objectid = 0;
key.type = BTRFS_ROOT_ITEM_KEY;
ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
BUG_ON(ret < 0);
+ tree_node = tree_root->node;
while (1) {
+ if (tree_node != tree_root->node) {
+ free_root_recs_tree(root_cache);
+ btrfs_release_path(&path);
+ goto again;
+ }
leaf = path.nodes[0];
if (path.slots[0] >= btrfs_header_nritems(leaf)) {
ret = btrfs_next_leaf(tree_root, &path);
--
1.8.3.1
^ permalink raw reply related [flat|nested] 12+ messages in thread* [PATCH 08/12] Btrfs-progs: delete bogus dir indexes
2014-10-10 20:57 Btrfs-progs: fix horrible things Josef Bacik
` (6 preceding siblings ...)
2014-10-10 20:57 ` [PATCH 07/12] Btrfs-progs: re-search tree root if it changes Josef Bacik
@ 2014-10-10 20:57 ` Josef Bacik
2014-10-10 20:57 ` [PATCH 09/12] Btrfs-progs: add a dummy backref if our location is wrong Josef Bacik
` (2 subsequent siblings)
10 siblings, 0 replies; 12+ messages in thread
From: Josef Bacik @ 2014-10-10 20:57 UTC (permalink / raw)
To: linux-btrfs
We may run across dir indexes that are corrupt in such a way that it makes them
useless, such as having a bad location key or a bad name. In this case we can
just delete dir indexes that don't show up properly and then re-create what we
need. When we delete dir indexes however we need to restart scanning the fs
tree as we could have greated bogus inode recs if the location key was bad, so
set it up so that if we had to delete an dir index we go ahead and free up our
inode recs and return -EAGAIN to check_fs_roots so it knows to restart the loop.
Thanks,
Signed-off-by: Josef Bacik <jbacik@fb.com>
---
cmds-check.c | 137 +++++++++++++++++++++++++++++++++++++++++++++++++++--------
ctree.h | 9 ++++
dir-item.c | 101 +++++++++++++++++++++++++++++++++++++++++++
3 files changed, 229 insertions(+), 18 deletions(-)
diff --git a/cmds-check.c b/cmds-check.c
index 9522077..8fdc542 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -1585,35 +1585,99 @@ static int add_missing_dir_index(struct btrfs_root *root,
return 0;
}
+static int delete_dir_index(struct btrfs_root *root,
+ struct cache_tree *inode_cache,
+ struct inode_record *rec,
+ struct inode_backref *backref)
+{
+ struct btrfs_trans_handle *trans;
+ struct btrfs_dir_item *di;
+ struct btrfs_path *path;
+ int ret = 0;
+
+ path = btrfs_alloc_path();
+ if (!path)
+ return -ENOMEM;
+
+ trans = btrfs_start_transaction(root, 1);
+ if (IS_ERR(trans)) {
+ btrfs_free_path(path);
+ return PTR_ERR(trans);
+ }
+
+
+ fprintf(stderr, "Deleting bad dir index [%llu,%u,%llu] root %llu\n",
+ (unsigned long long)backref->dir,
+ BTRFS_DIR_INDEX_KEY, (unsigned long long)backref->index,
+ (unsigned long long)root->objectid);
+
+ di = btrfs_lookup_dir_index(trans, root, path, backref->dir,
+ backref->name, backref->namelen,
+ backref->index, -1);
+ if (IS_ERR(di)) {
+ ret = PTR_ERR(di);
+ btrfs_free_path(path);
+ btrfs_commit_transaction(trans, root);
+ if (ret == -ENOENT)
+ return 0;
+ return ret;
+ }
+
+ if (!di)
+ ret = btrfs_del_item(trans, root, path);
+ else
+ ret = btrfs_delete_one_dir_name(trans, root, path, di);
+ BUG_ON(ret);
+ btrfs_free_path(path);
+ btrfs_commit_transaction(trans, root);
+ return ret;
+}
+
static int repair_inode_backrefs(struct btrfs_root *root,
struct inode_record *rec,
- struct cache_tree *inode_cache)
+ struct cache_tree *inode_cache,
+ int delete)
{
struct inode_backref *tmp, *backref;
u64 root_dirid = btrfs_root_dirid(&root->root_item);
int ret = 0;
+ int repaired = 0;
list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
/* Index 0 for root dir's are special, don't mess with it */
if (rec->ino == root_dirid && backref->index == 0)
continue;
- if (!backref->found_dir_index && backref->found_inode_ref) {
- ret = add_missing_dir_index(root, inode_cache, rec,
- backref);
+ if (delete && backref->found_dir_index &&
+ !backref->found_inode_ref) {
+ ret = delete_dir_index(root, inode_cache, rec, backref);
if (ret)
break;
+ repaired++;
+ list_del(&backref->list);
+ free(backref);
}
- if (backref->found_dir_item && backref->found_dir_index) {
- if (!backref->errors && backref->found_inode_ref) {
- list_del(&backref->list);
- free(backref);
+ if (!delete && !backref->found_dir_index &&
+ backref->found_dir_item && backref->found_inode_ref) {
+ ret = add_missing_dir_index(root, inode_cache, rec,
+ backref);
+ if (ret)
+ break;
+ repaired++;
+ if (backref->found_dir_item &&
+ backref->found_dir_index &&
+ backref->found_dir_index) {
+ if (!backref->errors &&
+ backref->found_inode_ref) {
+ list_del(&backref->list);
+ free(backref);
+ }
}
}
- }
- return ret;
+ }
+ return ret ? ret : repaired;
}
static int try_repair_inode(struct btrfs_root *root, struct inode_record *rec)
@@ -1651,7 +1715,9 @@ static int check_inode_recs(struct btrfs_root *root,
struct ptr_node *node;
struct inode_record *rec;
struct inode_backref *backref;
+ int stage = 0;
int ret;
+ int err = 0;
u64 error = 0;
u64 root_dirid = btrfs_root_dirid(&root->root_item);
@@ -1665,22 +1731,52 @@ static int check_inode_recs(struct btrfs_root *root,
* We need to repair backrefs first because we could change some of the
* errors in the inode recs.
*
+ * We also need to go through and delete invalid backrefs first and then
+ * add the correct ones second. We do this because we may get EEXIST
+ * when adding back the correct index because we hadn't yet deleted the
+ * invalid index.
+ *
* For example, if we were missing a dir index then the directories
* isize would be wrong, so if we fixed the isize to what we thought it
* would be and then fixed the backref we'd still have a invalid fs, so
* we need to add back the dir index and then check to see if the isize
* is still wrong.
*/
- cache = search_cache_extent(inode_cache, 0);
- while (repair && cache) {
- node = container_of(cache, struct ptr_node, cache);
- rec = node->data;
- cache = next_cache_extent(cache);
+ while (stage < 3) {
+ stage++;
+ if (stage == 3 && !err)
+ break;
- if (list_empty(&rec->backrefs))
- continue;
- repair_inode_backrefs(root, rec, inode_cache);
+ cache = search_cache_extent(inode_cache, 0);
+ while (repair && cache) {
+ node = container_of(cache, struct ptr_node, cache);
+ rec = node->data;
+ cache = next_cache_extent(cache);
+
+ /* Need to free everything up and rescan */
+ if (stage == 3) {
+ remove_cache_extent(inode_cache, &node->cache);
+ free(node);
+ free_inode_rec(rec);
+ continue;
+ }
+
+ if (list_empty(&rec->backrefs))
+ continue;
+
+ ret = repair_inode_backrefs(root, rec, inode_cache,
+ stage == 1);
+ if (ret < 0) {
+ err = ret;
+ stage = 2;
+ break;
+ } if (ret > 0) {
+ err = -EAGAIN;
+ }
+ }
}
+ if (err)
+ return err;
rec = get_inode_rec(inode_cache, root_dirid, 0);
if (rec) {
@@ -2216,6 +2312,11 @@ again:
goto next;
}
ret = check_fs_root(tmp_root, root_cache, &wc);
+ if (ret == -EAGAIN) {
+ free_root_recs_tree(root_cache);
+ btrfs_release_path(&path);
+ goto again;
+ }
if (ret)
err = 1;
} else if (key.type == BTRFS_ROOT_REF_KEY ||
diff --git a/ctree.h b/ctree.h
index eaab667..89036de 100644
--- a/ctree.h
+++ b/ctree.h
@@ -2360,6 +2360,15 @@ struct btrfs_dir_item *btrfs_lookup_dir_item(struct btrfs_trans_handle *trans,
struct btrfs_path *path, u64 dir,
const char *name, int name_len,
int mod);
+struct btrfs_dir_item *btrfs_lookup_dir_index(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path, u64 dir,
+ const char *name, int name_len,
+ u64 index, int mod);
+int btrfs_delete_one_dir_name(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ struct btrfs_dir_item *di);
int btrfs_insert_xattr_item(struct btrfs_trans_handle *trans,
struct btrfs_root *root, const char *name,
u16 name_len, const void *data, u16 data_len,
diff --git a/dir-item.c b/dir-item.c
index 7b145ad..43ae364 100644
--- a/dir-item.c
+++ b/dir-item.c
@@ -16,6 +16,7 @@
* Boston, MA 021110-1307, USA.
*/
+#include <linux/limits.h>
#include "ctree.h"
#include "disk-io.h"
#include "hash.h"
@@ -219,6 +220,98 @@ struct btrfs_dir_item *btrfs_lookup_dir_item(struct btrfs_trans_handle *trans,
return btrfs_match_dir_item_name(root, path, name, name_len);
}
+struct btrfs_dir_item *btrfs_lookup_dir_index(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path, u64 dir,
+ const char *name, int name_len,
+ u64 index, int mod)
+{
+ int ret;
+ struct btrfs_key key;
+ int ins_len = mod < 0 ? -1 : 0;
+ int cow = mod != 0;
+
+ key.objectid = dir;
+ key.type = BTRFS_DIR_INDEX_KEY;
+ key.offset = index;
+
+ ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow);
+ if (ret < 0)
+ return ERR_PTR(ret);
+ if (ret > 0)
+ return ERR_PTR(-ENOENT);
+
+ return btrfs_match_dir_item_name(root, path, name, name_len);
+}
+
+/*
+ * given a pointer into a directory item, delete it. This
+ * handles items that have more than one entry in them.
+ */
+int btrfs_delete_one_dir_name(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ struct btrfs_dir_item *di)
+{
+
+ struct extent_buffer *leaf;
+ u32 sub_item_len;
+ u32 item_len;
+ int ret = 0;
+
+ leaf = path->nodes[0];
+ sub_item_len = sizeof(*di) + btrfs_dir_name_len(leaf, di) +
+ btrfs_dir_data_len(leaf, di);
+ item_len = btrfs_item_size_nr(leaf, path->slots[0]);
+ if (sub_item_len == item_len) {
+ ret = btrfs_del_item(trans, root, path);
+ } else {
+ /* MARKER */
+ unsigned long ptr = (unsigned long)di;
+ unsigned long start;
+
+ start = btrfs_item_ptr_offset(leaf, path->slots[0]);
+ memmove_extent_buffer(leaf, ptr, ptr + sub_item_len,
+ item_len - (ptr + sub_item_len - start));
+ btrfs_truncate_item(trans, root, path, item_len - sub_item_len, 1);
+ }
+ return ret;
+}
+
+int verify_dir_item(struct btrfs_root *root,
+ struct extent_buffer *leaf,
+ struct btrfs_dir_item *dir_item)
+{
+ u16 namelen = BTRFS_NAME_LEN;
+ u8 type = btrfs_dir_type(leaf, dir_item);
+
+ if (type >= BTRFS_FT_MAX) {
+ fprintf(stderr, "invalid dir item type: %d",
+ (int)type);
+ return 1;
+ }
+
+ if (type == BTRFS_FT_XATTR)
+ namelen = XATTR_NAME_MAX;
+
+ if (btrfs_dir_name_len(leaf, dir_item) > namelen) {
+ fprintf(stderr, "invalid dir item name len: %u",
+ (unsigned)btrfs_dir_data_len(leaf, dir_item));
+ return 1;
+ }
+
+ /* BTRFS_MAX_XATTR_SIZE is the same for all dir items */
+ if ((btrfs_dir_data_len(leaf, dir_item) +
+ btrfs_dir_name_len(leaf, dir_item)) > BTRFS_MAX_XATTR_SIZE(root)) {
+ fprintf(stderr, "invalid dir item name + data len: %u + %u",
+ (unsigned)btrfs_dir_name_len(leaf, dir_item),
+ (unsigned)btrfs_dir_data_len(leaf, dir_item));
+ return 1;
+ }
+
+ return 0;
+}
+
static struct btrfs_dir_item *btrfs_match_dir_item_name(struct btrfs_root *root,
struct btrfs_path *path,
const char *name, int name_len)
@@ -233,10 +326,18 @@ static struct btrfs_dir_item *btrfs_match_dir_item_name(struct btrfs_root *root,
leaf = path->nodes[0];
dir_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dir_item);
total_len = btrfs_item_size_nr(leaf, path->slots[0]);
+ if (verify_dir_item(root, leaf, dir_item))
+ return NULL;
+
while(cur < total_len) {
this_len = sizeof(*dir_item) +
btrfs_dir_name_len(leaf, dir_item) +
btrfs_dir_data_len(leaf, dir_item);
+ if (this_len > (total_len - cur)) {
+ fprintf(stderr, "invalid dir item size\n");
+ return NULL;
+ }
+
name_ptr = (unsigned long)(dir_item + 1);
if (btrfs_dir_name_len(leaf, dir_item) == name_len &&
--
1.8.3.1
^ permalink raw reply related [flat|nested] 12+ messages in thread* [PATCH 09/12] Btrfs-progs: add a dummy backref if our location is wrong
2014-10-10 20:57 Btrfs-progs: fix horrible things Josef Bacik
` (7 preceding siblings ...)
2014-10-10 20:57 ` [PATCH 08/12] Btrfs-progs: delete bogus dir indexes Josef Bacik
@ 2014-10-10 20:57 ` Josef Bacik
2014-10-10 20:57 ` [PATCH 10/12] Btrfs-progs: deal with mismatch index between dir index and inode ref Josef Bacik
2014-10-10 20:57 ` [PATCH 11/12] Btrfs-progs: add ability to corrupt dir items Josef Bacik
10 siblings, 0 replies; 12+ messages in thread
From: Josef Bacik @ 2014-10-10 20:57 UTC (permalink / raw)
To: linux-btrfs
If our location is bogus in our dir item we were just skipping the thing.
However in this case we want to just delete the dir index, so create a dummy
inode rec using BTRFS_MULTIPLE_OBJECTIDS and just add every backref we find to
the list so we know to straight up delete all of these items. Thanks,
Signed-off-by: Josef Bacik <jbacik@fb.com>
---
cmds-check.c | 8 +++++++-
1 file changed, 7 insertions(+), 1 deletion(-)
diff --git a/cmds-check.c b/cmds-check.c
index 8fdc542..ca890cc 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -551,6 +551,8 @@ static struct inode_backref *get_inode_backref(struct inode_record *rec,
struct inode_backref *backref;
list_for_each_entry(backref, &rec->backrefs, list) {
+ if (rec->ino == BTRFS_MULTIPLE_OBJECTIDS)
+ break;
if (backref->dir != dir || backref->namelen != namelen)
continue;
if (memcmp(name, backref->name, namelen))
@@ -990,7 +992,11 @@ static int process_dir_item(struct btrfs_root *root,
namebuf, len, filetype,
key->type, error);
} else {
- fprintf(stderr, "warning line %d\n", __LINE__);
+ fprintf(stderr, "invalid location in dir item %u\n",
+ location.type);
+ add_inode_backref(inode_cache, BTRFS_MULTIPLE_OBJECTIDS,
+ key->objectid, key->offset, namebuf,
+ len, filetype, key->type, error);
}
len = sizeof(*di) + name_len + data_len;
--
1.8.3.1
^ permalink raw reply related [flat|nested] 12+ messages in thread* [PATCH 10/12] Btrfs-progs: deal with mismatch index between dir index and inode ref
2014-10-10 20:57 Btrfs-progs: fix horrible things Josef Bacik
` (8 preceding siblings ...)
2014-10-10 20:57 ` [PATCH 09/12] Btrfs-progs: add a dummy backref if our location is wrong Josef Bacik
@ 2014-10-10 20:57 ` Josef Bacik
2014-10-10 20:57 ` [PATCH 11/12] Btrfs-progs: add ability to corrupt dir items Josef Bacik
10 siblings, 0 replies; 12+ messages in thread
From: Josef Bacik @ 2014-10-10 20:57 UTC (permalink / raw)
To: linux-btrfs
Sometimes we have a dir index and an inode ref that don't agree on the index.
In this case just assume that the inode ref is the ultimate authority on the
subject and delete the dir index. This means we have to not reset index if we
find a mismatched inode ref to make sure we delete the right dir index. Thanks,
Signed-off-by: Josef Bacik <jbacik@fb.com>
---
cmds-check.c | 9 ++++++---
1 file changed, 6 insertions(+), 3 deletions(-)
diff --git a/cmds-check.c b/cmds-check.c
index ca890cc..80fa244 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -608,9 +608,10 @@ static int add_inode_backref(struct cache_tree *inode_cache,
backref->errors |= REF_ERR_DUP_INODE_REF;
if (backref->found_dir_index && backref->index != index)
backref->errors |= REF_ERR_INDEX_UNMATCH;
+ else
+ backref->index = index;
backref->ref_type = itemtype;
- backref->index = index;
backref->found_inode_ref = 1;
} else {
BUG_ON(1);
@@ -1654,8 +1655,10 @@ static int repair_inode_backrefs(struct btrfs_root *root,
if (rec->ino == root_dirid && backref->index == 0)
continue;
- if (delete && backref->found_dir_index &&
- !backref->found_inode_ref) {
+ if (delete &&
+ ((backref->found_dir_index && !backref->found_inode_ref) ||
+ (backref->found_dir_index && backref->found_inode_ref &&
+ backref->errors & REF_ERR_INDEX_UNMATCH))) {
ret = delete_dir_index(root, inode_cache, rec, backref);
if (ret)
break;
--
1.8.3.1
^ permalink raw reply related [flat|nested] 12+ messages in thread* [PATCH 11/12] Btrfs-progs: add ability to corrupt dir items
2014-10-10 20:57 Btrfs-progs: fix horrible things Josef Bacik
` (9 preceding siblings ...)
2014-10-10 20:57 ` [PATCH 10/12] Btrfs-progs: deal with mismatch index between dir index and inode ref Josef Bacik
@ 2014-10-10 20:57 ` Josef Bacik
10 siblings, 0 replies; 12+ messages in thread
From: Josef Bacik @ 2014-10-10 20:57 UTC (permalink / raw)
To: linux-btrfs
In order to test the dir index corruption fixing patches in fsck we need to add
functionality to btrfs-corrupt-block to corrupt dir item fields. Thanks,
Signed-off-by: Josef Bacik <jbacik@fb.com>
---
btrfs-corrupt-block.c | 103 +++++++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 102 insertions(+), 1 deletion(-)
diff --git a/btrfs-corrupt-block.c b/btrfs-corrupt-block.c
index 3e36f90..66d9f02 100644
--- a/btrfs-corrupt-block.c
+++ b/btrfs-corrupt-block.c
@@ -111,6 +111,7 @@ static void print_usage(void)
fprintf(stderr, "\t-d Delete this item (must specify -K)\n");
fprintf(stderr, "\t-I An item to corrupt (must also specify the field "
"to corrupt and a root+key for the item)\n");
+ fprintf(stderr, "\t-D Corrupt a dir item, must specify key and field\n");
exit(1);
}
@@ -304,6 +305,12 @@ enum btrfs_file_extent_field {
BTRFS_FILE_EXTENT_BAD,
};
+enum btrfs_dir_item_field {
+ BTRFS_DIR_ITEM_NAME,
+ BTRFS_DIR_ITEM_LOCATION_OBJECTID,
+ BTRFS_DIR_ITEM_BAD,
+};
+
enum btrfs_metadata_block_field {
BTRFS_METADATA_BLOCK_GENERATION,
BTRFS_METADATA_BLOCK_SHIFT_ITEMS,
@@ -364,6 +371,15 @@ static enum btrfs_item_field convert_item_field(char *field)
return BTRFS_ITEM_BAD;
}
+static enum btrfs_dir_item_field convert_dir_item_field(char *field)
+{
+ if (!strncmp(field, "name", FIELD_BUF_LEN))
+ return BTRFS_DIR_ITEM_NAME;
+ if (!strncmp(field, "location_objectid", FIELD_BUF_LEN))
+ return BTRFS_DIR_ITEM_LOCATION_OBJECTID;
+ return BTRFS_DIR_ITEM_BAD;
+}
+
static u64 generate_u64(u64 orig)
{
u64 ret;
@@ -448,6 +464,80 @@ out:
return ret;
}
+static int corrupt_dir_item(struct btrfs_root *root, struct btrfs_key *key,
+ char *field)
+{
+ struct btrfs_trans_handle *trans;
+ struct btrfs_dir_item *di;
+ struct btrfs_path *path;
+ char *name;
+ struct btrfs_key location;
+ struct btrfs_disk_key disk_key;
+ unsigned long name_ptr;
+ enum btrfs_dir_item_field corrupt_field =
+ convert_dir_item_field(field);
+ u64 bogus;
+ u16 name_len;
+ int ret;
+
+ if (corrupt_field == BTRFS_DIR_ITEM_BAD) {
+ fprintf(stderr, "Invalid field %s\n", field);
+ return -EINVAL;
+ }
+
+ path = btrfs_alloc_path();
+ if (!path)
+ return -ENOMEM;
+
+ trans = btrfs_start_transaction(root, 1);
+ if (IS_ERR(trans)) {
+ btrfs_free_path(path);
+ return PTR_ERR(trans);
+ }
+
+ ret = btrfs_search_slot(trans, root, key, path, 0, 1);
+ if (ret) {
+ if (ret > 0)
+ ret = -ENOENT;
+ fprintf(stderr, "Error searching for dir item %d\n", ret);
+ goto out;
+ }
+
+ di = btrfs_item_ptr(path->nodes[0], path->slots[0],
+ struct btrfs_dir_item);
+
+ switch (corrupt_field) {
+ case BTRFS_DIR_ITEM_NAME:
+ name_len = btrfs_dir_name_len(path->nodes[0], di);
+ name = malloc(name_len);
+ if (!name) {
+ ret = -ENOMEM;
+ goto out;
+ }
+ name_ptr = (unsigned long)(di + 1);
+ read_extent_buffer(path->nodes[0], name, name_ptr, name_len);
+ name[0]++;
+ write_extent_buffer(path->nodes[0], name, name_ptr, name_len);
+ btrfs_mark_buffer_dirty(path->nodes[0]);
+ free(name);
+ goto out;
+ case BTRFS_DIR_ITEM_LOCATION_OBJECTID:
+ btrfs_dir_item_key_to_cpu(path->nodes[0], di, &location);
+ bogus = generate_u64(location.objectid);
+ location.objectid = bogus;
+ btrfs_cpu_key_to_disk(&disk_key, &location);
+ btrfs_set_dir_item_key(path->nodes[0], di, &disk_key);
+ btrfs_mark_buffer_dirty(path->nodes[0]);
+ goto out;
+ default:
+ ret = -EINVAL;
+ goto out;
+ }
+out:
+ btrfs_commit_transaction(trans, root);
+ btrfs_free_path(path);
+ return ret;
+}
static int corrupt_inode(struct btrfs_trans_handle *trans,
struct btrfs_root *root, u64 inode, char *field)
@@ -772,6 +862,7 @@ static struct option long_options[] = {
{ "key", 1, NULL, 'K'},
{ "delete", 0, NULL, 'd'},
{ "item", 0, NULL, 'I'},
+ { "dir-item", 0, NULL, 'D'},
{ 0, 0, 0, 0}
};
@@ -937,6 +1028,7 @@ int main(int ac, char **av)
int chunk_tree = 0;
int delete = 0;
int corrupt_item = 0;
+ int corrupt_di = 0;
u64 metadata_block = 0;
u64 inode = 0;
u64 file_extent = (u64)-1;
@@ -948,7 +1040,7 @@ int main(int ac, char **av)
while(1) {
int c;
- c = getopt_long(ac, av, "l:c:b:eEkuUi:f:x:m:K:dI",
+ c = getopt_long(ac, av, "l:c:b:eEkuUi:f:x:m:K:dID",
long_options, &option_index);
if (c < 0)
break;
@@ -1005,6 +1097,9 @@ int main(int ac, char **av)
case 'I':
corrupt_item = 1;
break;
+ case 'D':
+ corrupt_di = 1;
+ break;
default:
print_usage();
}
@@ -1113,6 +1208,12 @@ int main(int ac, char **av)
ret = corrupt_btrfs_item(root, &key, field);
goto out_close;
}
+ if (corrupt_di) {
+ if (!key.objectid || !strlen(field))
+ print_usage();
+ ret = corrupt_dir_item(root, &key, field);
+ goto out_close;
+ }
if (key.objectid || key.offset || key.type) {
if (!strlen(field))
print_usage();
--
1.8.3.1
^ permalink raw reply related [flat|nested] 12+ messages in thread