summaryrefslogtreecommitdiff
path: root/fs/quota/quota_tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/quota/quota_tree.c')
-rw-r--r--fs/quota/quota_tree.c316
1 files changed, 253 insertions, 63 deletions
diff --git a/fs/quota/quota_tree.c b/fs/quota/quota_tree.c
index d65877fbe8f4..afceef3ddfaa 100644
--- a/fs/quota/quota_tree.c
+++ b/fs/quota/quota_tree.c
@@ -1,3 +1,4 @@
+// SPDX-License-Identifier: GPL-2.0-only
/*
* vfsv0 quota IO operations on file
*/
@@ -20,12 +21,17 @@ 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, struct kqid qid, int depth)
+static int __get_index(struct qtree_mem_dqinfo *info, qid_t id, int depth)
{
unsigned int epb = info->dqi_usable_bs >> 2;
- qid_t id = from_kqid(&init_user_ns, qid);
depth = info->dqi_qtree_depth - depth - 1;
while (depth--)
@@ -33,6 +39,13 @@ static int get_index(struct qtree_mem_dqinfo *info, struct kqid qid, int depth)
return id % epb;
}
+static int get_index(struct qtree_mem_dqinfo *info, struct kqid qid, int depth)
+{
+ qid_t id = from_kqid(&init_user_ns, qid);
+
+ return __get_index(info, id, depth);
+}
+
/* Number of entries in one blocks */
static int qtree_dqstr_in_blk(struct qtree_mem_dqinfo *info)
{
@@ -40,22 +53,13 @@ static int qtree_dqstr_in_blk(struct qtree_mem_dqinfo *info)
/ info->dqi_entry_size;
}
-static char *getdqbuf(size_t size)
-{
- char *buf = kmalloc(size, GFP_NOFS);
- if (!buf)
- printk(KERN_WARNING
- "VFS: Not enough memory for quota buffers.\n");
- return buf;
-}
-
static ssize_t read_blk(struct qtree_mem_dqinfo *info, uint blk, char *buf)
{
struct super_block *sb = info->dqi_sb;
memset(buf, 0, info->dqi_usable_bs);
return sb->s_op->quota_read(sb, info->dqi_type, buf,
- info->dqi_usable_bs, blk << info->dqi_blocksize_bits);
+ info->dqi_usable_bs, (loff_t)blk << info->dqi_blocksize_bits);
}
static ssize_t write_blk(struct qtree_mem_dqinfo *info, uint blk, char *buf)
@@ -64,7 +68,7 @@ static ssize_t write_blk(struct qtree_mem_dqinfo *info, uint blk, char *buf)
ssize_t ret;
ret = sb->s_op->quota_write(sb, info->dqi_type, buf,
- info->dqi_usable_bs, blk << info->dqi_blocksize_bits);
+ info->dqi_usable_bs, (loff_t)blk << info->dqi_blocksize_bits);
if (ret != info->dqi_usable_bs) {
quota_error(sb, "dquota write failed");
if (ret >= 0)
@@ -73,10 +77,44 @@ static ssize_t write_blk(struct qtree_mem_dqinfo *info, uint blk, char *buf)
return ret;
}
+static inline int do_check_range(struct super_block *sb, const char *val_name,
+ uint val, uint min_val, uint max_val)
+{
+ if (val < min_val || val > max_val) {
+ quota_error(sb, "Getting %s %u out of range %u-%u",
+ val_name, val, min_val, max_val);
+ return -EUCLEAN;
+ }
+
+ return 0;
+}
+
+static int check_dquot_block_header(struct qtree_mem_dqinfo *info,
+ struct qt_disk_dqdbheader *dh)
+{
+ int err = 0;
+
+ err = do_check_range(info->dqi_sb, "dqdh_next_free",
+ le32_to_cpu(dh->dqdh_next_free), 0,
+ info->dqi_blocks - 1);
+ if (err)
+ return err;
+ err = do_check_range(info->dqi_sb, "dqdh_prev_free",
+ le32_to_cpu(dh->dqdh_prev_free), 0,
+ info->dqi_blocks - 1);
+ if (err)
+ return err;
+ err = do_check_range(info->dqi_sb, "dqdh_entries",
+ le16_to_cpu(dh->dqdh_entries), 0,
+ qtree_dqstr_in_blk(info));
+
+ return err;
+}
+
/* Remove empty block from list and return it */
static int get_free_dqblk(struct qtree_mem_dqinfo *info)
{
- char *buf = getdqbuf(info->dqi_usable_bs);
+ char *buf = kmalloc(info->dqi_usable_bs, GFP_KERNEL);
struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
int ret, blk;
@@ -87,6 +125,9 @@ static int get_free_dqblk(struct qtree_mem_dqinfo *info)
ret = read_blk(info, blk, buf);
if (ret < 0)
goto out_buf;
+ ret = check_dquot_block_header(info, dh);
+ if (ret)
+ goto out_buf;
info->dqi_free_blk = le32_to_cpu(dh->dqdh_next_free);
}
else {
@@ -125,7 +166,7 @@ static int put_free_dqblk(struct qtree_mem_dqinfo *info, char *buf, uint blk)
static int remove_free_dqentry(struct qtree_mem_dqinfo *info, char *buf,
uint blk)
{
- char *tmpbuf = getdqbuf(info->dqi_usable_bs);
+ char *tmpbuf = kmalloc(info->dqi_usable_bs, GFP_KERNEL);
struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
uint nextblk = le32_to_cpu(dh->dqdh_next_free);
uint prevblk = le32_to_cpu(dh->dqdh_prev_free);
@@ -172,7 +213,7 @@ out_buf:
static int insert_free_dqentry(struct qtree_mem_dqinfo *info, char *buf,
uint blk)
{
- char *tmpbuf = getdqbuf(info->dqi_usable_bs);
+ char *tmpbuf = kmalloc(info->dqi_usable_bs, GFP_KERNEL);
struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
int err;
@@ -220,7 +261,7 @@ static uint find_free_dqentry(struct qtree_mem_dqinfo *info,
{
uint blk, i;
struct qt_disk_dqdbheader *dh;
- char *buf = getdqbuf(info->dqi_usable_bs);
+ char *buf = kmalloc(info->dqi_usable_bs, GFP_KERNEL);
char *ddquot;
*err = 0;
@@ -234,6 +275,9 @@ static uint find_free_dqentry(struct qtree_mem_dqinfo *info,
*err = read_blk(info, blk, buf);
if (*err < 0)
goto out_buf;
+ *err = check_dquot_block_header(info, dh);
+ if (*err)
+ goto out_buf;
} else {
blk = get_free_dqblk(info);
if ((int)blk < 0) {
@@ -277,7 +321,7 @@ static uint find_free_dqentry(struct qtree_mem_dqinfo *info,
blk);
goto out_buf;
}
- dquot->dq_off = (blk << info->dqi_blocksize_bits) +
+ dquot->dq_off = ((loff_t)blk << info->dqi_blocksize_bits) +
sizeof(struct qt_disk_dqdbheader) +
i * info->dqi_entry_size;
kfree(buf);
@@ -289,34 +333,59 @@ out_buf:
/* 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 = getdqbuf(info->dqi_usable_bs);
+ char *buf = kmalloc(info->dqi_usable_bs, GFP_KERNEL);
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;
}
}
ref = (__le32 *)buf;
newblk = le32_to_cpu(ref[get_index(info, dquot->dq_id, depth)]);
- if (!newblk)
+ ret = do_check_range(dquot->dq_sb, "block", newblk, 0,
+ info->dqi_blocks - 1);
+ if (ret)
+ goto out_buf;
+ 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) {
@@ -328,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);
@@ -348,8 +417,19 @@ out_buf:
static inline int dq_insert_tree(struct qtree_mem_dqinfo *info,
struct dquot *dquot)
{
- int tmp = QT_TREEOFF;
- return do_insert_tree(info, dquot, &tmp, 0);
+ uint blks[MAX_QTREE_DEPTH] = { QT_TREEOFF };
+
+#ifdef __QUOTA_QT_PARANOIA
+ if (info->dqi_blocks <= QT_TREEOFF) {
+ quota_error(dquot->dq_sb, "Quota tree root isn't allocated!");
+ return -EIO;
+ }
+#endif
+ 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);
}
/*
@@ -361,12 +441,12 @@ int qtree_write_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
int type = dquot->dq_id.type;
struct super_block *sb = dquot->dq_sb;
ssize_t ret;
- char *ddquot = getdqbuf(info->dqi_entry_size);
+ char *ddquot = kmalloc(info->dqi_entry_size, GFP_KERNEL);
if (!ddquot)
return -ENOMEM;
- /* dq_off is guarded by dqio_mutex */
+ /* dq_off is guarded by dqio_sem */
if (!dquot->dq_off) {
ret = dq_insert_tree(info, dquot);
if (ret < 0) {
@@ -376,9 +456,9 @@ int qtree_write_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
return ret;
}
}
- spin_lock(&dq_data_lock);
+ spin_lock(&dquot->dq_dqb_lock);
info->dqi_ops->mem2disk_dqblk(ddquot, dquot);
- spin_unlock(&dq_data_lock);
+ spin_unlock(&dquot->dq_dqb_lock);
ret = sb->s_op->quota_write(sb, type, ddquot, info->dqi_entry_size,
dquot->dq_off);
if (ret != info->dqi_entry_size) {
@@ -400,7 +480,7 @@ static int free_dqentry(struct qtree_mem_dqinfo *info, struct dquot *dquot,
uint blk)
{
struct qt_disk_dqdbheader *dh;
- char *buf = getdqbuf(info->dqi_usable_bs);
+ char *buf = kmalloc(info->dqi_usable_bs, GFP_KERNEL);
int ret = 0;
if (!buf)
@@ -409,6 +489,7 @@ static int free_dqentry(struct qtree_mem_dqinfo *info, struct dquot *dquot,
quota_error(dquot->dq_sb, "Quota structure has offset to "
"other block (%u) than it should (%u)", blk,
(uint)(dquot->dq_off >> info->dqi_blocksize_bits));
+ ret = -EIO;
goto out_buf;
}
ret = read_blk(info, blk, buf);
@@ -418,6 +499,9 @@ static int free_dqentry(struct qtree_mem_dqinfo *info, struct dquot *dquot,
goto out_buf;
}
dh = (struct qt_disk_dqdbheader *)buf;
+ ret = check_dquot_block_header(info, dh);
+ if (ret)
+ goto out_buf;
le16_add_cpu(&dh->dqdh_entries, -1);
if (!le16_to_cpu(dh->dqdh_entries)) { /* Block got free? */
ret = remove_free_dqentry(info, buf, blk);
@@ -458,45 +542,60 @@ out_buf:
/* 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 = getdqbuf(info->dqi_usable_bs);
+ char *buf = kmalloc(info->dqi_usable_bs, GFP_KERNEL);
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)]);
+ ret = do_check_range(dquot->dq_sb, "block", newblk, QT_TREEOFF,
+ info->dqi_blocks - 1);
+ 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:
@@ -507,11 +606,15 @@ out_buf:
/* 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);
@@ -519,7 +622,7 @@ EXPORT_SYMBOL(qtree_delete_dquot);
static loff_t find_block_dqentry(struct qtree_mem_dqinfo *info,
struct dquot *dquot, uint blk)
{
- char *buf = getdqbuf(info->dqi_usable_bs);
+ char *buf = kmalloc(info->dqi_usable_bs, GFP_KERNEL);
loff_t ret = 0;
int i;
char *ddquot;
@@ -545,7 +648,7 @@ static loff_t find_block_dqentry(struct qtree_mem_dqinfo *info,
ret = -EIO;
goto out_buf;
} else {
- ret = (blk << info->dqi_blocksize_bits) + sizeof(struct
+ ret = ((loff_t)blk << info->dqi_blocksize_bits) + sizeof(struct
qt_disk_dqdbheader) + i * info->dqi_entry_size;
}
out_buf:
@@ -555,26 +658,44 @@ out_buf:
/* 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 = getdqbuf(info->dqi_usable_bs);
+ char *buf = kmalloc(info->dqi_usable_bs, GFP_KERNEL);
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);
+ blks[depth]);
goto out_buf;
}
ret = 0;
blk = le32_to_cpu(ref[get_index(info, dquot->dq_id, depth)]);
if (!blk) /* No reference? */
goto out_buf;
+ ret = do_check_range(dquot->dq_sb, "block", blk, QT_TREEOFF,
+ info->dqi_blocks - 1);
+ 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:
@@ -586,7 +707,13 @@ out_buf:
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)
@@ -621,7 +748,7 @@ int qtree_read_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
}
dquot->dq_off = offset;
}
- ddquot = getdqbuf(info->dqi_entry_size);
+ ddquot = kmalloc(info->dqi_entry_size, GFP_KERNEL);
if (!ddquot)
return -ENOMEM;
ret = sb->s_op->quota_read(sb, type, ddquot, info->dqi_entry_size,
@@ -636,14 +763,14 @@ int qtree_read_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
kfree(ddquot);
goto out;
}
- spin_lock(&dq_data_lock);
+ spin_lock(&dquot->dq_dqb_lock);
info->dqi_ops->disk2mem_dqblk(dquot, ddquot);
if (!dquot->dq_dqb.dqb_bhardlimit &&
!dquot->dq_dqb.dqb_bsoftlimit &&
!dquot->dq_dqb.dqb_ihardlimit &&
!dquot->dq_dqb.dqb_isoftlimit)
set_bit(DQ_FAKE_B, &dquot->dq_flags);
- spin_unlock(&dq_data_lock);
+ spin_unlock(&dquot->dq_dqb_lock);
kfree(ddquot);
out:
dqstats_inc(DQST_READS);
@@ -661,3 +788,66 @@ int qtree_release_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
return 0;
}
EXPORT_SYMBOL(qtree_release_dquot);
+
+static int find_next_id(struct qtree_mem_dqinfo *info, qid_t *id,
+ unsigned int blk, int depth)
+{
+ char *buf = kmalloc(info->dqi_usable_bs, GFP_KERNEL);
+ __le32 *ref = (__le32 *)buf;
+ ssize_t ret;
+ unsigned int epb = info->dqi_usable_bs >> 2;
+ unsigned int level_inc = 1;
+ int i;
+
+ if (!buf)
+ return -ENOMEM;
+
+ for (i = depth; i < info->dqi_qtree_depth - 1; i++)
+ level_inc *= epb;
+
+ ret = read_blk(info, blk, buf);
+ if (ret < 0) {
+ quota_error(info->dqi_sb,
+ "Can't read quota tree block %u", blk);
+ goto out_buf;
+ }
+ for (i = __get_index(info, *id, depth); i < epb; i++) {
+ uint blk_no = le32_to_cpu(ref[i]);
+
+ if (blk_no == 0) {
+ *id += level_inc;
+ continue;
+ }
+ ret = do_check_range(info->dqi_sb, "block", blk_no, 0,
+ info->dqi_blocks - 1);
+ if (ret)
+ goto out_buf;
+ if (depth == info->dqi_qtree_depth - 1) {
+ ret = 0;
+ goto out_buf;
+ }
+ ret = find_next_id(info, id, blk_no, depth + 1);
+ if (ret != -ENOENT)
+ break;
+ }
+ if (i == epb) {
+ ret = -ENOENT;
+ goto out_buf;
+ }
+out_buf:
+ kfree(buf);
+ return ret;
+}
+
+int qtree_get_next_id(struct qtree_mem_dqinfo *info, struct kqid *qid)
+{
+ qid_t id = from_kqid(&init_user_ns, *qid);
+ int ret;
+
+ ret = find_next_id(info, &id, QT_TREEOFF, 0);
+ if (ret < 0)
+ return ret;
+ *qid = make_kqid(&init_user_ns, qid->type, id);
+ return 0;
+}
+EXPORT_SYMBOL(qtree_get_next_id);
generated by cgit (git 2.34.1) at 2025-12-25 08:54:22 +0000