fs/quota/quota_tree.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  *      vfsv0 quota IO operations on file
   4  */
   5
   6 #include <linux/errno.h>
   7 #include <linux/fs.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>
  15
  16 #include <asm/byteorder.h>
  17
  18 #include "quota_tree.h"
  19
  20 MODULE_AUTHOR("Jan Kara");
  21 MODULE_DESCRIPTION("Quota trie support");
  22 MODULE_LICENSE("GPL");
  23
  24 #define __QUOTA_QT_PARANOIA
  25
  26 static int __get_index(struct qtree_mem_dqinfo *info, qid_t id, int depth)
  27 {
  28         unsigned int epb = info->dqi_usable_bs >> 2;
  29
  30         depth = info->dqi_qtree_depth - depth - 1;
  31         while (depth--)
  32                 id /= epb;
  33         return id % epb;
  34 }
  35
  36 static int get_index(struct qtree_mem_dqinfo *info, struct kqid qid, int depth)
  37 {
  38         qid_t id = from_kqid(&init_user_ns, qid);
  39
  40         return __get_index(info, id, depth);
  41 }
  42
  43 /* Number of entries in one blocks */
  44 static int qtree_dqstr_in_blk(struct qtree_mem_dqinfo *info)
  45 {
  46         return (info->dqi_usable_bs - sizeof(struct qt_disk_dqdbheader))
  47                / info->dqi_entry_size;
  48 }
  49
  50 static ssize_t read_blk(struct qtree_mem_dqinfo *info, uint blk, char *buf)
  51 {
  52         struct super_block *sb = info->dqi_sb;
  53
  54         memset(buf, 0, info->dqi_usable_bs);
  55         return sb->s_op->quota_read(sb, info->dqi_type, buf,
  56                info->dqi_usable_bs, (loff_t)blk << info->dqi_blocksize_bits);
  57 }
  58
  59 static ssize_t write_blk(struct qtree_mem_dqinfo *info, uint blk, char *buf)
  60 {
  61         struct super_block *sb = info->dqi_sb;
  62         ssize_t ret;
  63
  64         ret = sb->s_op->quota_write(sb, info->dqi_type, buf,
  65                info->dqi_usable_bs, (loff_t)blk << info->dqi_blocksize_bits);
  66         if (ret != info->dqi_usable_bs) {
  67                 quota_error(sb, "dquota write failed");
  68                 if (ret >= 0)
  69                         ret = -EIO;
  70         }
  71         return ret;
  72 }
  73
  74 static inline int do_check_range(struct super_block *sb, const char *val_name,
  75                                  uint val, uint min_val, uint max_val)
  76 {
  77         if (val < min_val || val > max_val) {
  78                 quota_error(sb, "Getting %s %u out of range %u-%u",
  79                             val_name, val, min_val, max_val);
  80                 return -EUCLEAN;
  81         }
  82
  83         return 0;
  84 }
  85
  86 static int check_dquot_block_header(struct qtree_mem_dqinfo *info,
  87                                     struct qt_disk_dqdbheader *dh)
  88 {
  89         int err = 0;
  90
  91         err = do_check_range(info->dqi_sb, "dqdh_next_free",
  92                              le32_to_cpu(dh->dqdh_next_free), 0,
  93                              info->dqi_blocks - 1);
  94         if (err)
  95                 return err;
  96         err = do_check_range(info->dqi_sb, "dqdh_prev_free",
  97                              le32_to_cpu(dh->dqdh_prev_free), 0,
  98                              info->dqi_blocks - 1);
  99
 100         return err;
 101 }
 102
 103 /* Remove empty block from list and return it */
 104 static int get_free_dqblk(struct qtree_mem_dqinfo *info)
 105 {
 106         char *buf = kmalloc(info->dqi_usable_bs, GFP_NOFS);
 107         struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
 108         int ret, blk;
 109
 110         if (!buf)
 111                 return -ENOMEM;
 112         if (info->dqi_free_blk) {
 113                 blk = info->dqi_free_blk;
 114                 ret = read_blk(info, blk, buf);
 115                 if (ret < 0)
 116                         goto out_buf;
 117                 ret = check_dquot_block_header(info, dh);
 118                 if (ret)
 119                         goto out_buf;
 120                 info->dqi_free_blk = le32_to_cpu(dh->dqdh_next_free);
 121         }
 122         else {
 123                 memset(buf, 0, info->dqi_usable_bs);
 124                 /* Assure block allocation... */
 125                 ret = write_blk(info, info->dqi_blocks, buf);
 126                 if (ret < 0)
 127                         goto out_buf;
 128                 blk = info->dqi_blocks++;
 129         }
 130         mark_info_dirty(info->dqi_sb, info->dqi_type);
 131         ret = blk;
 132 out_buf:
 133         kfree(buf);
 134         return ret;
 135 }
 136
 137 /* Insert empty block to the list */
 138 static int put_free_dqblk(struct qtree_mem_dqinfo *info, char *buf, uint blk)
 139 {
 140         struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
 141         int err;
 142
 143         dh->dqdh_next_free = cpu_to_le32(info->dqi_free_blk);
 144         dh->dqdh_prev_free = cpu_to_le32(0);
 145         dh->dqdh_entries = cpu_to_le16(0);
 146         err = write_blk(info, blk, buf);
 147         if (err < 0)
 148                 return err;
 149         info->dqi_free_blk = blk;
 150         mark_info_dirty(info->dqi_sb, info->dqi_type);
 151         return 0;
 152 }
 153
 154 /* Remove given block from the list of blocks with free entries */
 155 static int remove_free_dqentry(struct qtree_mem_dqinfo *info, char *buf,
 156                                uint blk)
 157 {
 158         char *tmpbuf = kmalloc(info->dqi_usable_bs, GFP_NOFS);
 159         struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
 160         uint nextblk = le32_to_cpu(dh->dqdh_next_free);
 161         uint prevblk = le32_to_cpu(dh->dqdh_prev_free);
 162         int err;
 163
 164         if (!tmpbuf)
 165                 return -ENOMEM;
 166         if (nextblk) {
 167                 err = read_blk(info, nextblk, tmpbuf);
 168                 if (err < 0)
 169                         goto out_buf;
 170                 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free =
 171                                                         dh->dqdh_prev_free;
 172                 err = write_blk(info, nextblk, tmpbuf);
 173                 if (err < 0)
 174                         goto out_buf;
 175         }
 176         if (prevblk) {
 177                 err = read_blk(info, prevblk, tmpbuf);
 178                 if (err < 0)
 179                         goto out_buf;
 180                 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_next_free =
 181                                                         dh->dqdh_next_free;
 182                 err = write_blk(info, prevblk, tmpbuf);
 183                 if (err < 0)
 184                         goto out_buf;
 185         } else {
 186                 info->dqi_free_entry = nextblk;
 187                 mark_info_dirty(info->dqi_sb, info->dqi_type);
 188         }
 189         kfree(tmpbuf);
 190         dh->dqdh_next_free = dh->dqdh_prev_free = cpu_to_le32(0);
 191         /* No matter whether write succeeds block is out of list */
 192         if (write_blk(info, blk, buf) < 0)
 193                 quota_error(info->dqi_sb, "Can't write block (%u) "
 194                             "with free entries", blk);
 195         return 0;
 196 out_buf:
 197         kfree(tmpbuf);
 198         return err;
 199 }
 200
 201 /* Insert given block to the beginning of list with free entries */
 202 static int insert_free_dqentry(struct qtree_mem_dqinfo *info, char *buf,
 203                                uint blk)
 204 {
 205         char *tmpbuf = kmalloc(info->dqi_usable_bs, GFP_NOFS);
 206         struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
 207         int err;
 208
 209         if (!tmpbuf)
 210                 return -ENOMEM;
 211         dh->dqdh_next_free = cpu_to_le32(info->dqi_free_entry);
 212         dh->dqdh_prev_free = cpu_to_le32(0);
 213         err = write_blk(info, blk, buf);
 214         if (err < 0)
 215                 goto out_buf;
 216         if (info->dqi_free_entry) {
 217                 err = read_blk(info, info->dqi_free_entry, tmpbuf);
 218                 if (err < 0)
 219                         goto out_buf;
 220                 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free =
 221                                                         cpu_to_le32(blk);
 222                 err = write_blk(info, info->dqi_free_entry, tmpbuf);
 223                 if (err < 0)
 224                         goto out_buf;
 225         }
 226         kfree(tmpbuf);
 227         info->dqi_free_entry = blk;
 228         mark_info_dirty(info->dqi_sb, info->dqi_type);
 229         return 0;
 230 out_buf:
 231         kfree(tmpbuf);
 232         return err;
 233 }
 234
 235 /* Is the entry in the block free? */
 236 int qtree_entry_unused(struct qtree_mem_dqinfo *info, char *disk)
 237 {
 238         int i;
 239
 240         for (i = 0; i < info->dqi_entry_size; i++)
 241                 if (disk[i])
 242                         return 0;
 243         return 1;
 244 }
 245 EXPORT_SYMBOL(qtree_entry_unused);
 246
 247 /* Find space for dquot */
 248 static uint find_free_dqentry(struct qtree_mem_dqinfo *info,
 249                               struct dquot *dquot, int *err)
 250 {
 251         uint blk, i;
 252         struct qt_disk_dqdbheader *dh;
 253         char *buf = kmalloc(info->dqi_usable_bs, GFP_NOFS);
 254         char *ddquot;
 255
 256         *err = 0;
 257         if (!buf) {
 258                 *err = -ENOMEM;
 259                 return 0;
 260         }
 261         dh = (struct qt_disk_dqdbheader *)buf;
 262         if (info->dqi_free_entry) {
 263                 blk = info->dqi_free_entry;
 264                 *err = read_blk(info, blk, buf);
 265                 if (*err < 0)
 266                         goto out_buf;
 267                 *err = check_dquot_block_header(info, dh);
 268                 if (*err)
 269                         goto out_buf;
 270         } else {
 271                 blk = get_free_dqblk(info);
 272                 if ((int)blk < 0) {
 273                         *err = blk;
 274                         kfree(buf);
 275                         return 0;
 276                 }
 277                 memset(buf, 0, info->dqi_usable_bs);
 278                 /* This is enough as the block is already zeroed and the entry
 279                  * list is empty... */
 280                 info->dqi_free_entry = blk;
 281                 mark_info_dirty(dquot->dq_sb, dquot->dq_id.type);
 282         }
 283         /* Block will be full? */
 284         if (le16_to_cpu(dh->dqdh_entries) + 1 >= qtree_dqstr_in_blk(info)) {
 285                 *err = remove_free_dqentry(info, buf, blk);
 286                 if (*err < 0) {
 287                         quota_error(dquot->dq_sb, "Can't remove block (%u) "
 288                                     "from entry free list", blk);
 289                         goto out_buf;
 290                 }
 291         }
 292         le16_add_cpu(&dh->dqdh_entries, 1);
 293         /* Find free structure in block */
 294         ddquot = buf + sizeof(struct qt_disk_dqdbheader);
 295         for (i = 0; i < qtree_dqstr_in_blk(info); i++) {
 296                 if (qtree_entry_unused(info, ddquot))
 297                         break;
 298                 ddquot += info->dqi_entry_size;
 299         }
 300 #ifdef __QUOTA_QT_PARANOIA
 301         if (i == qtree_dqstr_in_blk(info)) {
 302                 quota_error(dquot->dq_sb, "Data block full but it shouldn't");
 303                 *err = -EIO;
 304                 goto out_buf;
 305         }
 306 #endif
 307         *err = write_blk(info, blk, buf);
 308         if (*err < 0) {
 309                 quota_error(dquot->dq_sb, "Can't write quota data block %u",
 310                             blk);
 311                 goto out_buf;
 312         }
 313         dquot->dq_off = ((loff_t)blk << info->dqi_blocksize_bits) +
 314                         sizeof(struct qt_disk_dqdbheader) +
 315                         i * info->dqi_entry_size;
 316         kfree(buf);
 317         return blk;
 318 out_buf:
 319         kfree(buf);
 320         return 0;
 321 }
 322
 323 /* Insert reference to structure into the trie */
 324 static int do_insert_tree(struct qtree_mem_dqinfo *info, struct dquot *dquot,
 325                           uint *treeblk, int depth)
 326 {
 327         char *buf = kmalloc(info->dqi_usable_bs, GFP_NOFS);
 328         int ret = 0, newson = 0, newact = 0;
 329         __le32 *ref;
 330         uint newblk;
 331
 332         if (!buf)
 333                 return -ENOMEM;
 334         if (!*treeblk) {
 335                 ret = get_free_dqblk(info);
 336                 if (ret < 0)
 337                         goto out_buf;
 338                 *treeblk = ret;
 339                 memset(buf, 0, info->dqi_usable_bs);
 340                 newact = 1;
 341         } else {
 342                 ret = read_blk(info, *treeblk, buf);
 343                 if (ret < 0) {
 344                         quota_error(dquot->dq_sb, "Can't read tree quota "
 345                                     "block %u", *treeblk);
 346                         goto out_buf;
 347                 }
 348         }
 349         ref = (__le32 *)buf;
 350         newblk = le32_to_cpu(ref[get_index(info, dquot->dq_id, depth)]);
 351         if (!newblk)
 352                 newson = 1;
 353         if (depth == info->dqi_qtree_depth - 1) {
 354 #ifdef __QUOTA_QT_PARANOIA
 355                 if (newblk) {
 356                         quota_error(dquot->dq_sb, "Inserting already present "
 357                                     "quota entry (block %u)",
 358                                     le32_to_cpu(ref[get_index(info,
 359                                                 dquot->dq_id, depth)]));
 360                         ret = -EIO;
 361                         goto out_buf;
 362                 }
 363 #endif
 364                 newblk = find_free_dqentry(info, dquot, &ret);
 365         } else {
 366                 ret = do_insert_tree(info, dquot, &newblk, depth+1);
 367         }
 368         if (newson && ret >= 0) {
 369                 ref[get_index(info, dquot->dq_id, depth)] =
 370                                                         cpu_to_le32(newblk);
 371                 ret = write_blk(info, *treeblk, buf);
 372         } else if (newact && ret < 0) {
 373                 put_free_dqblk(info, buf, *treeblk);
 374         }
 375 out_buf:
 376         kfree(buf);
 377         return ret;
 378 }
 379
 380 /* Wrapper for inserting quota structure into tree */
 381 static inline int dq_insert_tree(struct qtree_mem_dqinfo *info,
 382                                  struct dquot *dquot)
 383 {
 384         int tmp = QT_TREEOFF;
 385
 386 #ifdef __QUOTA_QT_PARANOIA
 387         if (info->dqi_blocks <= QT_TREEOFF) {
 388                 quota_error(dquot->dq_sb, "Quota tree root isn't allocated!");
 389                 return -EIO;
 390         }
 391 #endif
 392         return do_insert_tree(info, dquot, &tmp, 0);
 393 }
 394
 395 /*
 396  * We don't have to be afraid of deadlocks as we never have quotas on quota
 397  * files...
 398  */
 399 int qtree_write_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
 400 {
 401         int type = dquot->dq_id.type;
 402         struct super_block *sb = dquot->dq_sb;
 403         ssize_t ret;
 404         char *ddquot = kmalloc(info->dqi_entry_size, GFP_NOFS);
 405
 406         if (!ddquot)
 407                 return -ENOMEM;
 408
 409         /* dq_off is guarded by dqio_sem */
 410         if (!dquot->dq_off) {
 411                 ret = dq_insert_tree(info, dquot);
 412                 if (ret < 0) {
 413                         quota_error(sb, "Error %zd occurred while creating "
 414                                     "quota", ret);
 415                         kfree(ddquot);
 416                         return ret;
 417                 }
 418         }
 419         spin_lock(&dquot->dq_dqb_lock);
 420         info->dqi_ops->mem2disk_dqblk(ddquot, dquot);
 421         spin_unlock(&dquot->dq_dqb_lock);
 422         ret = sb->s_op->quota_write(sb, type, ddquot, info->dqi_entry_size,
 423                                     dquot->dq_off);
 424         if (ret != info->dqi_entry_size) {
 425                 quota_error(sb, "dquota write failed");
 426                 if (ret >= 0)
 427                         ret = -ENOSPC;
 428         } else {
 429                 ret = 0;
 430         }
 431         dqstats_inc(DQST_WRITES);
 432         kfree(ddquot);
 433
 434         return ret;
 435 }
 436 EXPORT_SYMBOL(qtree_write_dquot);
 437
 438 /* Free dquot entry in data block */
 439 static int free_dqentry(struct qtree_mem_dqinfo *info, struct dquot *dquot,
 440                         uint blk)
 441 {
 442         struct qt_disk_dqdbheader *dh;
 443         char *buf = kmalloc(info->dqi_usable_bs, GFP_NOFS);
 444         int ret = 0;
 445
 446         if (!buf)
 447                 return -ENOMEM;
 448         if (dquot->dq_off >> info->dqi_blocksize_bits != blk) {
 449                 quota_error(dquot->dq_sb, "Quota structure has offset to "
 450                         "other block (%u) than it should (%u)", blk,
 451                         (uint)(dquot->dq_off >> info->dqi_blocksize_bits));
 452                 ret = -EIO;
 453                 goto out_buf;
 454         }
 455         ret = read_blk(info, blk, buf);
 456         if (ret < 0) {
 457                 quota_error(dquot->dq_sb, "Can't read quota data block %u",
 458                             blk);
 459                 goto out_buf;
 460         }
 461         dh = (struct qt_disk_dqdbheader *)buf;
 462         ret = check_dquot_block_header(info, dh);
 463         if (ret)
 464                 goto out_buf;
 465         le16_add_cpu(&dh->dqdh_entries, -1);
 466         if (!le16_to_cpu(dh->dqdh_entries)) {   /* Block got free? */
 467                 ret = remove_free_dqentry(info, buf, blk);
 468                 if (ret >= 0)
 469                         ret = put_free_dqblk(info, buf, blk);
 470                 if (ret < 0) {
 471                         quota_error(dquot->dq_sb, "Can't move quota data block "
 472                                     "(%u) to free list", blk);
 473                         goto out_buf;
 474                 }
 475         } else {
 476                 memset(buf +
 477                        (dquot->dq_off & ((1 << info->dqi_blocksize_bits) - 1)),
 478                        0, info->dqi_entry_size);
 479                 if (le16_to_cpu(dh->dqdh_entries) ==
 480                     qtree_dqstr_in_blk(info) - 1) {
 481                         /* Insert will write block itself */
 482                         ret = insert_free_dqentry(info, buf, blk);
 483                         if (ret < 0) {
 484                                 quota_error(dquot->dq_sb, "Can't insert quota "
 485                                     "data block (%u) to free entry list", blk);
 486                                 goto out_buf;
 487                         }
 488                 } else {
 489                         ret = write_blk(info, blk, buf);
 490                         if (ret < 0) {
 491                                 quota_error(dquot->dq_sb, "Can't write quota "
 492                                             "data block %u", blk);
 493                                 goto out_buf;
 494                         }
 495                 }
 496         }
 497         dquot->dq_off = 0;      /* Quota is now unattached */
 498 out_buf:
 499         kfree(buf);
 500         return ret;
 501 }
 502
 503 /* Remove reference to dquot from tree */
 504 static int remove_tree(struct qtree_mem_dqinfo *info, struct dquot *dquot,
 505                        uint *blk, int depth)
 506 {
 507         char *buf = kmalloc(info->dqi_usable_bs, GFP_NOFS);
 508         int ret = 0;
 509         uint newblk;
 510         __le32 *ref = (__le32 *)buf;
 511
 512         if (!buf)
 513                 return -ENOMEM;
 514         ret = read_blk(info, *blk, buf);
 515         if (ret < 0) {
 516                 quota_error(dquot->dq_sb, "Can't read quota data block %u",
 517                             *blk);
 518                 goto out_buf;
 519         }
 520         newblk = le32_to_cpu(ref[get_index(info, dquot->dq_id, depth)]);
 521         if (newblk < QT_TREEOFF || newblk >= info->dqi_blocks) {
 522                 quota_error(dquot->dq_sb, "Getting block too big (%u >= %u)",
 523                             newblk, info->dqi_blocks);
 524                 ret = -EUCLEAN;
 525                 goto out_buf;
 526         }
 527
 528         if (depth == info->dqi_qtree_depth - 1) {
 529                 ret = free_dqentry(info, dquot, newblk);
 530                 newblk = 0;
 531         } else {
 532                 ret = remove_tree(info, dquot, &newblk, depth+1);
 533         }
 534         if (ret >= 0 && !newblk) {
 535                 int i;
 536                 ref[get_index(info, dquot->dq_id, depth)] = cpu_to_le32(0);
 537                 /* Block got empty? */
 538                 for (i = 0; i < (info->dqi_usable_bs >> 2) && !ref[i]; i++)
 539                         ;
 540                 /* Don't put the root block into the free block list */
 541                 if (i == (info->dqi_usable_bs >> 2)
 542                     && *blk != QT_TREEOFF) {
 543                         put_free_dqblk(info, buf, *blk);
 544                         *blk = 0;
 545                 } else {
 546                         ret = write_blk(info, *blk, buf);
 547                         if (ret < 0)
 548                                 quota_error(dquot->dq_sb,
 549                                             "Can't write quota tree block %u",
 550                                             *blk);
 551                 }
 552         }
 553 out_buf:
 554         kfree(buf);
 555         return ret;
 556 }
 557
 558 /* Delete dquot from tree */
 559 int qtree_delete_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
 560 {
 561         uint tmp = QT_TREEOFF;
 562
 563         if (!dquot->dq_off)     /* Even not allocated? */
 564                 return 0;
 565         return remove_tree(info, dquot, &tmp, 0);
 566 }
 567 EXPORT_SYMBOL(qtree_delete_dquot);
 568
 569 /* Find entry in block */
 570 static loff_t find_block_dqentry(struct qtree_mem_dqinfo *info,
 571                                  struct dquot *dquot, uint blk)
 572 {
 573         char *buf = kmalloc(info->dqi_usable_bs, GFP_NOFS);
 574         loff_t ret = 0;
 575         int i;
 576         char *ddquot;
 577
 578         if (!buf)
 579                 return -ENOMEM;
 580         ret = read_blk(info, blk, buf);
 581         if (ret < 0) {
 582                 quota_error(dquot->dq_sb, "Can't read quota tree "
 583                             "block %u", blk);
 584                 goto out_buf;
 585         }
 586         ddquot = buf + sizeof(struct qt_disk_dqdbheader);
 587         for (i = 0; i < qtree_dqstr_in_blk(info); i++) {
 588                 if (info->dqi_ops->is_id(ddquot, dquot))
 589                         break;
 590                 ddquot += info->dqi_entry_size;
 591         }
 592         if (i == qtree_dqstr_in_blk(info)) {
 593                 quota_error(dquot->dq_sb,
 594                             "Quota for id %u referenced but not present",
 595                             from_kqid(&init_user_ns, dquot->dq_id));
 596                 ret = -EIO;
 597                 goto out_buf;
 598         } else {
 599                 ret = ((loff_t)blk << info->dqi_blocksize_bits) + sizeof(struct
 600                   qt_disk_dqdbheader) + i * info->dqi_entry_size;
 601         }
 602 out_buf:
 603         kfree(buf);
 604         return ret;
 605 }
 606
 607 /* Find entry for given id in the tree */
 608 static loff_t find_tree_dqentry(struct qtree_mem_dqinfo *info,
 609                                 struct dquot *dquot, uint blk, int depth)
 610 {
 611         char *buf = kmalloc(info->dqi_usable_bs, GFP_NOFS);
 612         loff_t ret = 0;
 613         __le32 *ref = (__le32 *)buf;
 614
 615         if (!buf)
 616                 return -ENOMEM;
 617         ret = read_blk(info, blk, buf);
 618         if (ret < 0) {
 619                 quota_error(dquot->dq_sb, "Can't read quota tree block %u",
 620                             blk);
 621                 goto out_buf;
 622         }
 623         ret = 0;
 624         blk = le32_to_cpu(ref[get_index(info, dquot->dq_id, depth)]);
 625         if (!blk)       /* No reference? */
 626                 goto out_buf;
 627         if (blk < QT_TREEOFF || blk >= info->dqi_blocks) {
 628                 quota_error(dquot->dq_sb, "Getting block too big (%u >= %u)",
 629                             blk, info->dqi_blocks);
 630                 ret = -EUCLEAN;
 631                 goto out_buf;
 632         }
 633
 634         if (depth < info->dqi_qtree_depth - 1)
 635                 ret = find_tree_dqentry(info, dquot, blk, depth+1);
 636         else
 637                 ret = find_block_dqentry(info, dquot, blk);
 638 out_buf:
 639         kfree(buf);
 640         return ret;
 641 }
 642
 643 /* Find entry for given id in the tree - wrapper function */
 644 static inline loff_t find_dqentry(struct qtree_mem_dqinfo *info,
 645                                   struct dquot *dquot)
 646 {
 647         return find_tree_dqentry(info, dquot, QT_TREEOFF, 0);
 648 }
 649
 650 int qtree_read_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
 651 {
 652         int type = dquot->dq_id.type;
 653         struct super_block *sb = dquot->dq_sb;
 654         loff_t offset;
 655         char *ddquot;
 656         int ret = 0;
 657
 658 #ifdef __QUOTA_QT_PARANOIA
 659         /* Invalidated quota? */
 660         if (!sb_dqopt(dquot->dq_sb)->files[type]) {
 661                 quota_error(sb, "Quota invalidated while reading!");
 662                 return -EIO;
 663         }
 664 #endif
 665         /* Do we know offset of the dquot entry in the quota file? */
 666         if (!dquot->dq_off) {
 667                 offset = find_dqentry(info, dquot);
 668                 if (offset <= 0) {      /* Entry not present? */
 669                         if (offset < 0)
 670                                 quota_error(sb,"Can't read quota structure "
 671                                             "for id %u",
 672                                             from_kqid(&init_user_ns,
 673                                                       dquot->dq_id));
 674                         dquot->dq_off = 0;
 675                         set_bit(DQ_FAKE_B, &dquot->dq_flags);
 676                         memset(&dquot->dq_dqb, 0, sizeof(struct mem_dqblk));
 677                         ret = offset;
 678                         goto out;
 679                 }
 680                 dquot->dq_off = offset;
 681         }
 682         ddquot = kmalloc(info->dqi_entry_size, GFP_NOFS);
 683         if (!ddquot)
 684                 return -ENOMEM;
 685         ret = sb->s_op->quota_read(sb, type, ddquot, info->dqi_entry_size,
 686                                    dquot->dq_off);
 687         if (ret != info->dqi_entry_size) {
 688                 if (ret >= 0)
 689                         ret = -EIO;
 690                 quota_error(sb, "Error while reading quota structure for id %u",
 691                             from_kqid(&init_user_ns, dquot->dq_id));
 692                 set_bit(DQ_FAKE_B, &dquot->dq_flags);
 693                 memset(&dquot->dq_dqb, 0, sizeof(struct mem_dqblk));
 694                 kfree(ddquot);
 695                 goto out;
 696         }
 697         spin_lock(&dquot->dq_dqb_lock);
 698         info->dqi_ops->disk2mem_dqblk(dquot, ddquot);
 699         if (!dquot->dq_dqb.dqb_bhardlimit &&
 700             !dquot->dq_dqb.dqb_bsoftlimit &&
 701             !dquot->dq_dqb.dqb_ihardlimit &&
 702             !dquot->dq_dqb.dqb_isoftlimit)
 703                 set_bit(DQ_FAKE_B, &dquot->dq_flags);
 704         spin_unlock(&dquot->dq_dqb_lock);
 705         kfree(ddquot);
 706 out:
 707         dqstats_inc(DQST_READS);
 708         return ret;
 709 }
 710 EXPORT_SYMBOL(qtree_read_dquot);
 711
 712 /* Check whether dquot should not be deleted. We know we are
 713  * the only one operating on dquot (thanks to dq_lock) */
 714 int qtree_release_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
 715 {
 716         if (test_bit(DQ_FAKE_B, &dquot->dq_flags) &&
 717             !(dquot->dq_dqb.dqb_curinodes | dquot->dq_dqb.dqb_curspace))
 718                 return qtree_delete_dquot(info, dquot);
 719         return 0;
 720 }
 721 EXPORT_SYMBOL(qtree_release_dquot);
 722
 723 static int find_next_id(struct qtree_mem_dqinfo *info, qid_t *id,
 724                         unsigned int blk, int depth)
 725 {
 726         char *buf = kmalloc(info->dqi_usable_bs, GFP_NOFS);
 727         __le32 *ref = (__le32 *)buf;
 728         ssize_t ret;
 729         unsigned int epb = info->dqi_usable_bs >> 2;
 730         unsigned int level_inc = 1;
 731         int i;
 732
 733         if (!buf)
 734                 return -ENOMEM;
 735
 736         for (i = depth; i < info->dqi_qtree_depth - 1; i++)
 737                 level_inc *= epb;
 738
 739         ret = read_blk(info, blk, buf);
 740         if (ret < 0) {
 741                 quota_error(info->dqi_sb,
 742                             "Can't read quota tree block %u", blk);
 743                 goto out_buf;
 744         }
 745         for (i = __get_index(info, *id, depth); i < epb; i++) {
 746                 if (ref[i] == cpu_to_le32(0)) {
 747                         *id += level_inc;
 748                         continue;
 749                 }
 750                 if (depth == info->dqi_qtree_depth - 1) {
 751                         ret = 0;
 752                         goto out_buf;
 753                 }
 754                 ret = find_next_id(info, id, le32_to_cpu(ref[i]), depth + 1);
 755                 if (ret != -ENOENT)
 756                         break;
 757         }
 758         if (i == epb) {
 759                 ret = -ENOENT;
 760                 goto out_buf;
 761         }
 762 out_buf:
 763         kfree(buf);
 764         return ret;
 765 }
 766
 767 int qtree_get_next_id(struct qtree_mem_dqinfo *info, struct kqid *qid)
 768 {
 769         qid_t id = from_kqid(&init_user_ns, *qid);
 770         int ret;
 771
 772         ret = find_next_id(info, &id, QT_TREEOFF, 0);
 773         if (ret < 0)
 774                 return ret;
 775         *qid = make_kqid(&init_user_ns, qid->type, id);
 776         return 0;
 777 }
 778 EXPORT_SYMBOL(qtree_get_next_id);