* [PATCH] quota: Detect loops in quota tree
@ 2024-02-09 11:22 Jan Kara
2024-02-12 18:47 ` Kees Cook
0 siblings, 1 reply; 4+ messages in thread
From: Jan Kara @ 2024-02-09 11:22 UTC (permalink / raw)
To: linux-fsdevel; +Cc: Jan Kara
Syzbot has found that when it creates corrupted quota files where the
quota tree contains a loop, we will deadlock when tryling to insert a
dquot. Add loop detection into functions traversing the quota tree.
Signed-off-by: Jan Kara <jack@suse.cz>
---
fs/quota/quota_tree.c | 126 +++++++++++++++++++++++++++++++-----------
fs/quota/quota_v2.c | 15 +++--
2 files changed, 104 insertions(+), 37 deletions(-)
I plan to merge this fix into my tree.
diff --git a/fs/quota/quota_tree.c b/fs/quota/quota_tree.c
index 0f1493e0f6d0..bc8e7e16b164 100644
--- a/fs/quota/quota_tree.c
+++ b/fs/quota/quota_tree.c
@@ -21,6 +21,12 @@ MODULE_AUTHOR("Jan Kara");
MODULE_DESCRIPTION("Quota trie support");
MODULE_LICENSE("GPL");
+/*
+ * Maximum quota tree depth we support. Only to limit recursion when working
+ * with the tree.
+ */
+#define MAX_QTREE_DEPTH 6
+
#define __QUOTA_QT_PARANOIA
static int __get_index(struct qtree_mem_dqinfo *info, qid_t id, int depth)
@@ -327,27 +333,36 @@ static uint find_free_dqentry(struct qtree_mem_dqinfo *info,
/* Insert reference to structure into the trie */
static int do_insert_tree(struct qtree_mem_dqinfo *info, struct dquot *dquot,
- uint *treeblk, int depth)
+ uint *blks, int depth)
{
char *buf = kmalloc(info->dqi_usable_bs, GFP_NOFS);
int ret = 0, newson = 0, newact = 0;
__le32 *ref;
uint newblk;
+ int i;
if (!buf)
return -ENOMEM;
- if (!*treeblk) {
+ if (!blks[depth]) {
ret = get_free_dqblk(info);
if (ret < 0)
goto out_buf;
- *treeblk = ret;
+ for (i = 0; i < depth; i++)
+ if (ret == blks[i]) {
+ quota_error(dquot->dq_sb,
+ "Free block already used in tree: block %u",
+ ret);
+ ret = -EIO;
+ goto out_buf;
+ }
+ blks[depth] = ret;
memset(buf, 0, info->dqi_usable_bs);
newact = 1;
} else {
- ret = read_blk(info, *treeblk, buf);
+ ret = read_blk(info, blks[depth], buf);
if (ret < 0) {
quota_error(dquot->dq_sb, "Can't read tree quota "
- "block %u", *treeblk);
+ "block %u", blks[depth]);
goto out_buf;
}
}
@@ -357,8 +372,20 @@ static int do_insert_tree(struct qtree_mem_dqinfo *info, struct dquot *dquot,
info->dqi_blocks - 1);
if (ret)
goto out_buf;
- if (!newblk)
+ if (!newblk) {
newson = 1;
+ } else {
+ for (i = 0; i <= depth; i++)
+ if (newblk == blks[i]) {
+ quota_error(dquot->dq_sb,
+ "Cycle in quota tree detected: block %u index %u",
+ blks[depth],
+ get_index(info, dquot->dq_id, depth));
+ ret = -EIO;
+ goto out_buf;
+ }
+ }
+ blks[depth + 1] = newblk;
if (depth == info->dqi_qtree_depth - 1) {
#ifdef __QUOTA_QT_PARANOIA
if (newblk) {
@@ -370,16 +397,16 @@ static int do_insert_tree(struct qtree_mem_dqinfo *info, struct dquot *dquot,
goto out_buf;
}
#endif
- newblk = find_free_dqentry(info, dquot, &ret);
+ blks[depth + 1] = find_free_dqentry(info, dquot, &ret);
} else {
- ret = do_insert_tree(info, dquot, &newblk, depth+1);
+ ret = do_insert_tree(info, dquot, blks, depth + 1);
}
if (newson && ret >= 0) {
ref[get_index(info, dquot->dq_id, depth)] =
- cpu_to_le32(newblk);
- ret = write_blk(info, *treeblk, buf);
+ cpu_to_le32(blks[depth + 1]);
+ ret = write_blk(info, blks[depth], buf);
} else if (newact && ret < 0) {
- put_free_dqblk(info, buf, *treeblk);
+ put_free_dqblk(info, buf, blks[depth]);
}
out_buf:
kfree(buf);
@@ -390,7 +417,7 @@ static int do_insert_tree(struct qtree_mem_dqinfo *info, struct dquot *dquot,
static inline int dq_insert_tree(struct qtree_mem_dqinfo *info,
struct dquot *dquot)
{
- int tmp = QT_TREEOFF;
+ uint blks[MAX_QTREE_DEPTH] = { QT_TREEOFF };
#ifdef __QUOTA_QT_PARANOIA
if (info->dqi_blocks <= QT_TREEOFF) {
@@ -398,7 +425,11 @@ static inline int dq_insert_tree(struct qtree_mem_dqinfo *info,
return -EIO;
}
#endif
- return do_insert_tree(info, dquot, &tmp, 0);
+ if (info->dqi_qtree_depth >= MAX_QTREE_DEPTH) {
+ quota_error(dquot->dq_sb, "Quota tree depth too big!");
+ return -EIO;
+ }
+ return do_insert_tree(info, dquot, blks, 0);
}
/*
@@ -511,19 +542,20 @@ static int free_dqentry(struct qtree_mem_dqinfo *info, struct dquot *dquot,
/* Remove reference to dquot from tree */
static int remove_tree(struct qtree_mem_dqinfo *info, struct dquot *dquot,
- uint *blk, int depth)
+ uint *blks, int depth)
{
char *buf = kmalloc(info->dqi_usable_bs, GFP_NOFS);
int ret = 0;
uint newblk;
__le32 *ref = (__le32 *)buf;
+ int i;
if (!buf)
return -ENOMEM;
- ret = read_blk(info, *blk, buf);
+ ret = read_blk(info, blks[depth], buf);
if (ret < 0) {
quota_error(dquot->dq_sb, "Can't read quota data block %u",
- *blk);
+ blks[depth]);
goto out_buf;
}
newblk = le32_to_cpu(ref[get_index(info, dquot->dq_id, depth)]);
@@ -532,29 +564,38 @@ static int remove_tree(struct qtree_mem_dqinfo *info, struct dquot *dquot,
if (ret)
goto out_buf;
+ for (i = 0; i <= depth; i++)
+ if (newblk == blks[i]) {
+ quota_error(dquot->dq_sb,
+ "Cycle in quota tree detected: block %u index %u",
+ blks[depth],
+ get_index(info, dquot->dq_id, depth));
+ ret = -EIO;
+ goto out_buf;
+ }
if (depth == info->dqi_qtree_depth - 1) {
ret = free_dqentry(info, dquot, newblk);
- newblk = 0;
+ blks[depth + 1] = 0;
} else {
- ret = remove_tree(info, dquot, &newblk, depth+1);
+ blks[depth + 1] = newblk;
+ ret = remove_tree(info, dquot, blks, depth + 1);
}
- if (ret >= 0 && !newblk) {
- int i;
+ if (ret >= 0 && !blks[depth + 1]) {
ref[get_index(info, dquot->dq_id, depth)] = cpu_to_le32(0);
/* Block got empty? */
for (i = 0; i < (info->dqi_usable_bs >> 2) && !ref[i]; i++)
;
/* Don't put the root block into the free block list */
if (i == (info->dqi_usable_bs >> 2)
- && *blk != QT_TREEOFF) {
- put_free_dqblk(info, buf, *blk);
- *blk = 0;
+ && blks[depth] != QT_TREEOFF) {
+ put_free_dqblk(info, buf, blks[depth]);
+ blks[depth] = 0;
} else {
- ret = write_blk(info, *blk, buf);
+ ret = write_blk(info, blks[depth], buf);
if (ret < 0)
quota_error(dquot->dq_sb,
"Can't write quota tree block %u",
- *blk);
+ blks[depth]);
}
}
out_buf:
@@ -565,11 +606,15 @@ static int remove_tree(struct qtree_mem_dqinfo *info, struct dquot *dquot,
/* Delete dquot from tree */
int qtree_delete_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
{
- uint tmp = QT_TREEOFF;
+ uint blks[MAX_QTREE_DEPTH] = { QT_TREEOFF };
if (!dquot->dq_off) /* Even not allocated? */
return 0;
- return remove_tree(info, dquot, &tmp, 0);
+ if (info->dqi_qtree_depth >= MAX_QTREE_DEPTH) {
+ quota_error(dquot->dq_sb, "Quota tree depth too big!");
+ return -EIO;
+ }
+ return remove_tree(info, dquot, blks, 0);
}
EXPORT_SYMBOL(qtree_delete_dquot);
@@ -613,15 +658,17 @@ static loff_t find_block_dqentry(struct qtree_mem_dqinfo *info,
/* Find entry for given id in the tree */
static loff_t find_tree_dqentry(struct qtree_mem_dqinfo *info,
- struct dquot *dquot, uint blk, int depth)
+ struct dquot *dquot, uint *blks, int depth)
{
char *buf = kmalloc(info->dqi_usable_bs, GFP_NOFS);
loff_t ret = 0;
__le32 *ref = (__le32 *)buf;
+ uint blk;
+ int i;
if (!buf)
return -ENOMEM;
- ret = read_blk(info, blk, buf);
+ ret = read_blk(info, blks[depth], buf);
if (ret < 0) {
quota_error(dquot->dq_sb, "Can't read quota tree block %u",
blk);
@@ -636,8 +683,19 @@ static loff_t find_tree_dqentry(struct qtree_mem_dqinfo *info,
if (ret)
goto out_buf;
+ /* Check for cycles in the tree */
+ for (i = 0; i <= depth; i++)
+ if (blk == blks[i]) {
+ quota_error(dquot->dq_sb,
+ "Cycle in quota tree detected: block %u index %u",
+ blks[depth],
+ get_index(info, dquot->dq_id, depth));
+ ret = -EIO;
+ goto out_buf;
+ }
+ blks[depth + 1] = blk;
if (depth < info->dqi_qtree_depth - 1)
- ret = find_tree_dqentry(info, dquot, blk, depth+1);
+ ret = find_tree_dqentry(info, dquot, blks, depth + 1);
else
ret = find_block_dqentry(info, dquot, blk);
out_buf:
@@ -649,7 +707,13 @@ static loff_t find_tree_dqentry(struct qtree_mem_dqinfo *info,
static inline loff_t find_dqentry(struct qtree_mem_dqinfo *info,
struct dquot *dquot)
{
- return find_tree_dqentry(info, dquot, QT_TREEOFF, 0);
+ uint blks[MAX_QTREE_DEPTH] = { QT_TREEOFF };
+
+ if (info->dqi_qtree_depth >= MAX_QTREE_DEPTH) {
+ quota_error(dquot->dq_sb, "Quota tree depth too big!");
+ return -EIO;
+ }
+ return find_tree_dqentry(info, dquot, blks, 0);
}
int qtree_read_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
diff --git a/fs/quota/quota_v2.c b/fs/quota/quota_v2.c
index ae99e7b88205..7978ab671e0c 100644
--- a/fs/quota/quota_v2.c
+++ b/fs/quota/quota_v2.c
@@ -166,14 +166,17 @@ static int v2_read_file_info(struct super_block *sb, int type)
i_size_read(sb_dqopt(sb)->files[type]));
goto out_free;
}
- if (qinfo->dqi_free_blk >= qinfo->dqi_blocks) {
- quota_error(sb, "Free block number too big (%u >= %u).",
- qinfo->dqi_free_blk, qinfo->dqi_blocks);
+ if (qinfo->dqi_free_blk && (qinfo->dqi_free_blk <= QT_TREEOFF ||
+ qinfo->dqi_free_blk >= qinfo->dqi_blocks)) {
+ quota_error(sb, "Free block number %u out of range (%u, %u).",
+ qinfo->dqi_free_blk, QT_TREEOFF, qinfo->dqi_blocks);
goto out_free;
}
- if (qinfo->dqi_free_entry >= qinfo->dqi_blocks) {
- quota_error(sb, "Block with free entry too big (%u >= %u).",
- qinfo->dqi_free_entry, qinfo->dqi_blocks);
+ if (qinfo->dqi_free_entry && (qinfo->dqi_free_entry <= QT_TREEOFF ||
+ qinfo->dqi_free_entry >= qinfo->dqi_blocks)) {
+ quota_error(sb, "Block with free entry %u out of range (%u, %u).",
+ qinfo->dqi_free_entry, QT_TREEOFF,
+ qinfo->dqi_blocks);
goto out_free;
}
ret = 0;
--
2.35.3
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [PATCH] quota: Detect loops in quota tree
2024-02-09 11:22 [PATCH] quota: Detect loops in quota tree Jan Kara
@ 2024-02-12 18:47 ` Kees Cook
2024-02-12 23:48 ` Jan Kara
0 siblings, 1 reply; 4+ messages in thread
From: Kees Cook @ 2024-02-12 18:47 UTC (permalink / raw)
To: Jan Kara; +Cc: linux-fsdevel
On Fri, Feb 09, 2024 at 12:22:50PM +0100, Jan Kara wrote:
> [...]
> @@ -613,15 +658,17 @@ static loff_t find_block_dqentry(struct qtree_mem_dqinfo *info,
>
> /* Find entry for given id in the tree */
> static loff_t find_tree_dqentry(struct qtree_mem_dqinfo *info,
> - struct dquot *dquot, uint blk, int depth)
> + struct dquot *dquot, uint *blks, int depth)
> {
> char *buf = kmalloc(info->dqi_usable_bs, GFP_NOFS);
> loff_t ret = 0;
> __le32 *ref = (__le32 *)buf;
> + uint blk;
> + int i;
>
> if (!buf)
> return -ENOMEM;
> - ret = read_blk(info, blk, buf);
> + ret = read_blk(info, blks[depth], buf);
> if (ret < 0) {
> quota_error(dquot->dq_sb, "Can't read quota tree block %u",
> blk);
^^^
Coverity noticed this is used uninitialized. It should be "blks[depth]"
now, I think.
-Kees
--
Kees Cook
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] quota: Detect loops in quota tree
2024-02-12 18:47 ` Kees Cook
@ 2024-02-12 23:48 ` Jan Kara
2024-02-12 23:59 ` Kees Cook
0 siblings, 1 reply; 4+ messages in thread
From: Jan Kara @ 2024-02-12 23:48 UTC (permalink / raw)
To: Kees Cook; +Cc: Jan Kara, linux-fsdevel
On Mon 12-02-24 10:47:28, Kees Cook wrote:
> On Fri, Feb 09, 2024 at 12:22:50PM +0100, Jan Kara wrote:
> > [...]
> > @@ -613,15 +658,17 @@ static loff_t find_block_dqentry(struct qtree_mem_dqinfo *info,
> >
> > /* Find entry for given id in the tree */
> > static loff_t find_tree_dqentry(struct qtree_mem_dqinfo *info,
> > - struct dquot *dquot, uint blk, int depth)
> > + struct dquot *dquot, uint *blks, int depth)
> > {
> > char *buf = kmalloc(info->dqi_usable_bs, GFP_NOFS);
> > loff_t ret = 0;
> > __le32 *ref = (__le32 *)buf;
> > + uint blk;
> > + int i;
> >
> > if (!buf)
> > return -ENOMEM;
> > - ret = read_blk(info, blk, buf);
> > + ret = read_blk(info, blks[depth], buf);
> > if (ret < 0) {
> > quota_error(dquot->dq_sb, "Can't read quota tree block %u",
> > blk);
> ^^^
> Coverity noticed this is used uninitialized. It should be "blks[depth]"
> now, I think.
Yup, already pushed fix to my tree as 0-day notified me as well :) But
thanks for noticing!
Honza
--
Jan Kara <jack@suse.com>
SUSE Labs, CR
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] quota: Detect loops in quota tree
2024-02-12 23:48 ` Jan Kara
@ 2024-02-12 23:59 ` Kees Cook
0 siblings, 0 replies; 4+ messages in thread
From: Kees Cook @ 2024-02-12 23:59 UTC (permalink / raw)
To: Jan Kara; +Cc: linux-fsdevel
On Tue, Feb 13, 2024 at 12:48:56AM +0100, Jan Kara wrote:
> On Mon 12-02-24 10:47:28, Kees Cook wrote:
> > On Fri, Feb 09, 2024 at 12:22:50PM +0100, Jan Kara wrote:
> > > [...]
> > > @@ -613,15 +658,17 @@ static loff_t find_block_dqentry(struct qtree_mem_dqinfo *info,
> > >
> > > /* Find entry for given id in the tree */
> > > static loff_t find_tree_dqentry(struct qtree_mem_dqinfo *info,
> > > - struct dquot *dquot, uint blk, int depth)
> > > + struct dquot *dquot, uint *blks, int depth)
> > > {
> > > char *buf = kmalloc(info->dqi_usable_bs, GFP_NOFS);
> > > loff_t ret = 0;
> > > __le32 *ref = (__le32 *)buf;
> > > + uint blk;
> > > + int i;
> > >
> > > if (!buf)
> > > return -ENOMEM;
> > > - ret = read_blk(info, blk, buf);
> > > + ret = read_blk(info, blks[depth], buf);
> > > if (ret < 0) {
> > > quota_error(dquot->dq_sb, "Can't read quota tree block %u",
> > > blk);
> > ^^^
> > Coverity noticed this is used uninitialized. It should be "blks[depth]"
> > now, I think.
>
> Yup, already pushed fix to my tree as 0-day notified me as well :) But
> thanks for noticing!
Ah-ha! Thanks :)
--
Kees Cook
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2024-02-12 23:59 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2024-02-09 11:22 [PATCH] quota: Detect loops in quota tree Jan Kara
2024-02-12 18:47 ` Kees Cook
2024-02-12 23:48 ` Jan Kara
2024-02-12 23:59 ` Kees Cook
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).