1 // SPDX-License-Identifier: GPL-2.0-only
3 * vfsv0 quota IO operations on file
6 #include <linux/errno.h>
8 #include <linux/mount.h>
9 #include <linux/dqblk_v2.h>
10 #include <linux/kernel.h>
11 #include <linux/init.h>
12 #include <linux/module.h>
13 #include <linux/slab.h>
14 #include <linux/quotaops.h>
16 #include <asm/byteorder.h>
18 #include "quota_tree.h"
20 MODULE_AUTHOR("Jan Kara");
21 MODULE_DESCRIPTION("Quota trie support");
22 MODULE_LICENSE("GPL");
24 #define __QUOTA_QT_PARANOIA
26 static int __get_index(struct qtree_mem_dqinfo *info, qid_t id, int depth)
28 unsigned int epb = info->dqi_usable_bs >> 2;
30 depth = info->dqi_qtree_depth - depth - 1;
36 static int get_index(struct qtree_mem_dqinfo *info, struct kqid qid, int depth)
38 qid_t id = from_kqid(&init_user_ns, qid);
40 return __get_index(info, id, depth);
43 /* Number of entries in one blocks */
44 static int qtree_dqstr_in_blk(struct qtree_mem_dqinfo *info)
46 return (info->dqi_usable_bs - sizeof(struct qt_disk_dqdbheader))
47 / info->dqi_entry_size;
50 static char *getdqbuf(size_t size)
52 char *buf = kmalloc(size, GFP_NOFS);
55 "VFS: Not enough memory for quota buffers.\n");
59 static ssize_t read_blk(struct qtree_mem_dqinfo *info, uint blk, char *buf)
61 struct super_block *sb = info->dqi_sb;
63 memset(buf, 0, info->dqi_usable_bs);
64 return sb->s_op->quota_read(sb, info->dqi_type, buf,
65 info->dqi_usable_bs, (loff_t)blk << info->dqi_blocksize_bits);
68 static ssize_t write_blk(struct qtree_mem_dqinfo *info, uint blk, char *buf)
70 struct super_block *sb = info->dqi_sb;
73 ret = sb->s_op->quota_write(sb, info->dqi_type, buf,
74 info->dqi_usable_bs, (loff_t)blk << info->dqi_blocksize_bits);
75 if (ret != info->dqi_usable_bs) {
76 quota_error(sb, "dquota write failed");
83 static inline int do_check_range(struct super_block *sb, const char *val_name,
84 uint val, uint min_val, uint max_val)
86 if (val < min_val || val > max_val) {
87 quota_error(sb, "Getting %s %u out of range %u-%u",
88 val_name, val, min_val, max_val);
95 static int check_dquot_block_header(struct qtree_mem_dqinfo *info,
96 struct qt_disk_dqdbheader *dh)
100 err = do_check_range(info->dqi_sb, "dqdh_next_free",
101 le32_to_cpu(dh->dqdh_next_free), 0,
102 info->dqi_blocks - 1);
105 err = do_check_range(info->dqi_sb, "dqdh_prev_free",
106 le32_to_cpu(dh->dqdh_prev_free), 0,
107 info->dqi_blocks - 1);
112 /* Remove empty block from list and return it */
113 static int get_free_dqblk(struct qtree_mem_dqinfo *info)
115 char *buf = getdqbuf(info->dqi_usable_bs);
116 struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
121 if (info->dqi_free_blk) {
122 blk = info->dqi_free_blk;
123 ret = read_blk(info, blk, buf);
126 ret = check_dquot_block_header(info, dh);
129 info->dqi_free_blk = le32_to_cpu(dh->dqdh_next_free);
132 memset(buf, 0, info->dqi_usable_bs);
133 /* Assure block allocation... */
134 ret = write_blk(info, info->dqi_blocks, buf);
137 blk = info->dqi_blocks++;
139 mark_info_dirty(info->dqi_sb, info->dqi_type);
146 /* Insert empty block to the list */
147 static int put_free_dqblk(struct qtree_mem_dqinfo *info, char *buf, uint blk)
149 struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
152 dh->dqdh_next_free = cpu_to_le32(info->dqi_free_blk);
153 dh->dqdh_prev_free = cpu_to_le32(0);
154 dh->dqdh_entries = cpu_to_le16(0);
155 err = write_blk(info, blk, buf);
158 info->dqi_free_blk = blk;
159 mark_info_dirty(info->dqi_sb, info->dqi_type);
163 /* Remove given block from the list of blocks with free entries */
164 static int remove_free_dqentry(struct qtree_mem_dqinfo *info, char *buf,
167 char *tmpbuf = getdqbuf(info->dqi_usable_bs);
168 struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
169 uint nextblk = le32_to_cpu(dh->dqdh_next_free);
170 uint prevblk = le32_to_cpu(dh->dqdh_prev_free);
176 err = read_blk(info, nextblk, tmpbuf);
179 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free =
181 err = write_blk(info, nextblk, tmpbuf);
186 err = read_blk(info, prevblk, tmpbuf);
189 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_next_free =
191 err = write_blk(info, prevblk, tmpbuf);
195 info->dqi_free_entry = nextblk;
196 mark_info_dirty(info->dqi_sb, info->dqi_type);
199 dh->dqdh_next_free = dh->dqdh_prev_free = cpu_to_le32(0);
200 /* No matter whether write succeeds block is out of list */
201 if (write_blk(info, blk, buf) < 0)
202 quota_error(info->dqi_sb, "Can't write block (%u) "
203 "with free entries", blk);
210 /* Insert given block to the beginning of list with free entries */
211 static int insert_free_dqentry(struct qtree_mem_dqinfo *info, char *buf,
214 char *tmpbuf = getdqbuf(info->dqi_usable_bs);
215 struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
220 dh->dqdh_next_free = cpu_to_le32(info->dqi_free_entry);
221 dh->dqdh_prev_free = cpu_to_le32(0);
222 err = write_blk(info, blk, buf);
225 if (info->dqi_free_entry) {
226 err = read_blk(info, info->dqi_free_entry, tmpbuf);
229 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free =
231 err = write_blk(info, info->dqi_free_entry, tmpbuf);
236 info->dqi_free_entry = blk;
237 mark_info_dirty(info->dqi_sb, info->dqi_type);
244 /* Is the entry in the block free? */
245 int qtree_entry_unused(struct qtree_mem_dqinfo *info, char *disk)
249 for (i = 0; i < info->dqi_entry_size; i++)
254 EXPORT_SYMBOL(qtree_entry_unused);
256 /* Find space for dquot */
257 static uint find_free_dqentry(struct qtree_mem_dqinfo *info,
258 struct dquot *dquot, int *err)
261 struct qt_disk_dqdbheader *dh;
262 char *buf = getdqbuf(info->dqi_usable_bs);
270 dh = (struct qt_disk_dqdbheader *)buf;
271 if (info->dqi_free_entry) {
272 blk = info->dqi_free_entry;
273 *err = read_blk(info, blk, buf);
276 *err = check_dquot_block_header(info, dh);
280 blk = get_free_dqblk(info);
286 memset(buf, 0, info->dqi_usable_bs);
287 /* This is enough as the block is already zeroed and the entry
288 * list is empty... */
289 info->dqi_free_entry = blk;
290 mark_info_dirty(dquot->dq_sb, dquot->dq_id.type);
292 /* Block will be full? */
293 if (le16_to_cpu(dh->dqdh_entries) + 1 >= qtree_dqstr_in_blk(info)) {
294 *err = remove_free_dqentry(info, buf, blk);
296 quota_error(dquot->dq_sb, "Can't remove block (%u) "
297 "from entry free list", blk);
301 le16_add_cpu(&dh->dqdh_entries, 1);
302 /* Find free structure in block */
303 ddquot = buf + sizeof(struct qt_disk_dqdbheader);
304 for (i = 0; i < qtree_dqstr_in_blk(info); i++) {
305 if (qtree_entry_unused(info, ddquot))
307 ddquot += info->dqi_entry_size;
309 #ifdef __QUOTA_QT_PARANOIA
310 if (i == qtree_dqstr_in_blk(info)) {
311 quota_error(dquot->dq_sb, "Data block full but it shouldn't");
316 *err = write_blk(info, blk, buf);
318 quota_error(dquot->dq_sb, "Can't write quota data block %u",
322 dquot->dq_off = ((loff_t)blk << info->dqi_blocksize_bits) +
323 sizeof(struct qt_disk_dqdbheader) +
324 i * info->dqi_entry_size;
332 /* Insert reference to structure into the trie */
333 static int do_insert_tree(struct qtree_mem_dqinfo *info, struct dquot *dquot,
334 uint *treeblk, int depth)
336 char *buf = getdqbuf(info->dqi_usable_bs);
337 int ret = 0, newson = 0, newact = 0;
344 ret = get_free_dqblk(info);
348 memset(buf, 0, info->dqi_usable_bs);
351 ret = read_blk(info, *treeblk, buf);
353 quota_error(dquot->dq_sb, "Can't read tree quota "
354 "block %u", *treeblk);
359 newblk = le32_to_cpu(ref[get_index(info, dquot->dq_id, depth)]);
362 if (depth == info->dqi_qtree_depth - 1) {
363 #ifdef __QUOTA_QT_PARANOIA
365 quota_error(dquot->dq_sb, "Inserting already present "
366 "quota entry (block %u)",
367 le32_to_cpu(ref[get_index(info,
368 dquot->dq_id, depth)]));
373 newblk = find_free_dqentry(info, dquot, &ret);
375 ret = do_insert_tree(info, dquot, &newblk, depth+1);
377 if (newson && ret >= 0) {
378 ref[get_index(info, dquot->dq_id, depth)] =
380 ret = write_blk(info, *treeblk, buf);
381 } else if (newact && ret < 0) {
382 put_free_dqblk(info, buf, *treeblk);
389 /* Wrapper for inserting quota structure into tree */
390 static inline int dq_insert_tree(struct qtree_mem_dqinfo *info,
393 int tmp = QT_TREEOFF;
395 #ifdef __QUOTA_QT_PARANOIA
396 if (info->dqi_blocks <= QT_TREEOFF) {
397 quota_error(dquot->dq_sb, "Quota tree root isn't allocated!");
401 return do_insert_tree(info, dquot, &tmp, 0);
405 * We don't have to be afraid of deadlocks as we never have quotas on quota
408 int qtree_write_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
410 int type = dquot->dq_id.type;
411 struct super_block *sb = dquot->dq_sb;
413 char *ddquot = getdqbuf(info->dqi_entry_size);
418 /* dq_off is guarded by dqio_sem */
419 if (!dquot->dq_off) {
420 ret = dq_insert_tree(info, dquot);
422 quota_error(sb, "Error %zd occurred while creating "
428 spin_lock(&dquot->dq_dqb_lock);
429 info->dqi_ops->mem2disk_dqblk(ddquot, dquot);
430 spin_unlock(&dquot->dq_dqb_lock);
431 ret = sb->s_op->quota_write(sb, type, ddquot, info->dqi_entry_size,
433 if (ret != info->dqi_entry_size) {
434 quota_error(sb, "dquota write failed");
440 dqstats_inc(DQST_WRITES);
445 EXPORT_SYMBOL(qtree_write_dquot);
447 /* Free dquot entry in data block */
448 static int free_dqentry(struct qtree_mem_dqinfo *info, struct dquot *dquot,
451 struct qt_disk_dqdbheader *dh;
452 char *buf = getdqbuf(info->dqi_usable_bs);
457 if (dquot->dq_off >> info->dqi_blocksize_bits != blk) {
458 quota_error(dquot->dq_sb, "Quota structure has offset to "
459 "other block (%u) than it should (%u)", blk,
460 (uint)(dquot->dq_off >> info->dqi_blocksize_bits));
464 ret = read_blk(info, blk, buf);
466 quota_error(dquot->dq_sb, "Can't read quota data block %u",
470 dh = (struct qt_disk_dqdbheader *)buf;
471 ret = check_dquot_block_header(info, dh);
474 le16_add_cpu(&dh->dqdh_entries, -1);
475 if (!le16_to_cpu(dh->dqdh_entries)) { /* Block got free? */
476 ret = remove_free_dqentry(info, buf, blk);
478 ret = put_free_dqblk(info, buf, blk);
480 quota_error(dquot->dq_sb, "Can't move quota data block "
481 "(%u) to free list", blk);
486 (dquot->dq_off & ((1 << info->dqi_blocksize_bits) - 1)),
487 0, info->dqi_entry_size);
488 if (le16_to_cpu(dh->dqdh_entries) ==
489 qtree_dqstr_in_blk(info) - 1) {
490 /* Insert will write block itself */
491 ret = insert_free_dqentry(info, buf, blk);
493 quota_error(dquot->dq_sb, "Can't insert quota "
494 "data block (%u) to free entry list", blk);
498 ret = write_blk(info, blk, buf);
500 quota_error(dquot->dq_sb, "Can't write quota "
501 "data block %u", blk);
506 dquot->dq_off = 0; /* Quota is now unattached */
512 /* Remove reference to dquot from tree */
513 static int remove_tree(struct qtree_mem_dqinfo *info, struct dquot *dquot,
514 uint *blk, int depth)
516 char *buf = getdqbuf(info->dqi_usable_bs);
519 __le32 *ref = (__le32 *)buf;
523 ret = read_blk(info, *blk, buf);
525 quota_error(dquot->dq_sb, "Can't read quota data block %u",
529 newblk = le32_to_cpu(ref[get_index(info, dquot->dq_id, depth)]);
530 if (newblk < QT_TREEOFF || newblk >= info->dqi_blocks) {
531 quota_error(dquot->dq_sb, "Getting block too big (%u >= %u)",
532 newblk, info->dqi_blocks);
537 if (depth == info->dqi_qtree_depth - 1) {
538 ret = free_dqentry(info, dquot, newblk);
541 ret = remove_tree(info, dquot, &newblk, depth+1);
543 if (ret >= 0 && !newblk) {
545 ref[get_index(info, dquot->dq_id, depth)] = cpu_to_le32(0);
546 /* Block got empty? */
547 for (i = 0; i < (info->dqi_usable_bs >> 2) && !ref[i]; i++)
549 /* Don't put the root block into the free block list */
550 if (i == (info->dqi_usable_bs >> 2)
551 && *blk != QT_TREEOFF) {
552 put_free_dqblk(info, buf, *blk);
555 ret = write_blk(info, *blk, buf);
557 quota_error(dquot->dq_sb,
558 "Can't write quota tree block %u",
567 /* Delete dquot from tree */
568 int qtree_delete_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
570 uint tmp = QT_TREEOFF;
572 if (!dquot->dq_off) /* Even not allocated? */
574 return remove_tree(info, dquot, &tmp, 0);
576 EXPORT_SYMBOL(qtree_delete_dquot);
578 /* Find entry in block */
579 static loff_t find_block_dqentry(struct qtree_mem_dqinfo *info,
580 struct dquot *dquot, uint blk)
582 char *buf = getdqbuf(info->dqi_usable_bs);
589 ret = read_blk(info, blk, buf);
591 quota_error(dquot->dq_sb, "Can't read quota tree "
595 ddquot = buf + sizeof(struct qt_disk_dqdbheader);
596 for (i = 0; i < qtree_dqstr_in_blk(info); i++) {
597 if (info->dqi_ops->is_id(ddquot, dquot))
599 ddquot += info->dqi_entry_size;
601 if (i == qtree_dqstr_in_blk(info)) {
602 quota_error(dquot->dq_sb,
603 "Quota for id %u referenced but not present",
604 from_kqid(&init_user_ns, dquot->dq_id));
608 ret = ((loff_t)blk << info->dqi_blocksize_bits) + sizeof(struct
609 qt_disk_dqdbheader) + i * info->dqi_entry_size;
616 /* Find entry for given id in the tree */
617 static loff_t find_tree_dqentry(struct qtree_mem_dqinfo *info,
618 struct dquot *dquot, uint blk, int depth)
620 char *buf = getdqbuf(info->dqi_usable_bs);
622 __le32 *ref = (__le32 *)buf;
626 ret = read_blk(info, blk, buf);
628 quota_error(dquot->dq_sb, "Can't read quota tree block %u",
633 blk = le32_to_cpu(ref[get_index(info, dquot->dq_id, depth)]);
634 if (!blk) /* No reference? */
636 if (blk < QT_TREEOFF || blk >= info->dqi_blocks) {
637 quota_error(dquot->dq_sb, "Getting block too big (%u >= %u)",
638 blk, info->dqi_blocks);
643 if (depth < info->dqi_qtree_depth - 1)
644 ret = find_tree_dqentry(info, dquot, blk, depth+1);
646 ret = find_block_dqentry(info, dquot, blk);
652 /* Find entry for given id in the tree - wrapper function */
653 static inline loff_t find_dqentry(struct qtree_mem_dqinfo *info,
656 return find_tree_dqentry(info, dquot, QT_TREEOFF, 0);
659 int qtree_read_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
661 int type = dquot->dq_id.type;
662 struct super_block *sb = dquot->dq_sb;
667 #ifdef __QUOTA_QT_PARANOIA
668 /* Invalidated quota? */
669 if (!sb_dqopt(dquot->dq_sb)->files[type]) {
670 quota_error(sb, "Quota invalidated while reading!");
674 /* Do we know offset of the dquot entry in the quota file? */
675 if (!dquot->dq_off) {
676 offset = find_dqentry(info, dquot);
677 if (offset <= 0) { /* Entry not present? */
679 quota_error(sb,"Can't read quota structure "
681 from_kqid(&init_user_ns,
684 set_bit(DQ_FAKE_B, &dquot->dq_flags);
685 memset(&dquot->dq_dqb, 0, sizeof(struct mem_dqblk));
689 dquot->dq_off = offset;
691 ddquot = getdqbuf(info->dqi_entry_size);
694 ret = sb->s_op->quota_read(sb, type, ddquot, info->dqi_entry_size,
696 if (ret != info->dqi_entry_size) {
699 quota_error(sb, "Error while reading quota structure for id %u",
700 from_kqid(&init_user_ns, dquot->dq_id));
701 set_bit(DQ_FAKE_B, &dquot->dq_flags);
702 memset(&dquot->dq_dqb, 0, sizeof(struct mem_dqblk));
706 spin_lock(&dquot->dq_dqb_lock);
707 info->dqi_ops->disk2mem_dqblk(dquot, ddquot);
708 if (!dquot->dq_dqb.dqb_bhardlimit &&
709 !dquot->dq_dqb.dqb_bsoftlimit &&
710 !dquot->dq_dqb.dqb_ihardlimit &&
711 !dquot->dq_dqb.dqb_isoftlimit)
712 set_bit(DQ_FAKE_B, &dquot->dq_flags);
713 spin_unlock(&dquot->dq_dqb_lock);
716 dqstats_inc(DQST_READS);
719 EXPORT_SYMBOL(qtree_read_dquot);
721 /* Check whether dquot should not be deleted. We know we are
722 * the only one operating on dquot (thanks to dq_lock) */
723 int qtree_release_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
725 if (test_bit(DQ_FAKE_B, &dquot->dq_flags) &&
726 !(dquot->dq_dqb.dqb_curinodes | dquot->dq_dqb.dqb_curspace))
727 return qtree_delete_dquot(info, dquot);
730 EXPORT_SYMBOL(qtree_release_dquot);
732 static int find_next_id(struct qtree_mem_dqinfo *info, qid_t *id,
733 unsigned int blk, int depth)
735 char *buf = getdqbuf(info->dqi_usable_bs);
736 __le32 *ref = (__le32 *)buf;
738 unsigned int epb = info->dqi_usable_bs >> 2;
739 unsigned int level_inc = 1;
745 for (i = depth; i < info->dqi_qtree_depth - 1; i++)
748 ret = read_blk(info, blk, buf);
750 quota_error(info->dqi_sb,
751 "Can't read quota tree block %u", blk);
754 for (i = __get_index(info, *id, depth); i < epb; i++) {
755 if (ref[i] == cpu_to_le32(0)) {
759 if (depth == info->dqi_qtree_depth - 1) {
763 ret = find_next_id(info, id, le32_to_cpu(ref[i]), depth + 1);
776 int qtree_get_next_id(struct qtree_mem_dqinfo *info, struct kqid *qid)
778 qid_t id = from_kqid(&init_user_ns, *qid);
781 ret = find_next_id(info, &id, QT_TREEOFF, 0);
784 *qid = make_kqid(&init_user_ns, qid->type, id);
787 EXPORT_SYMBOL(qtree_get_next_id);