fs/quota/quota_tree.c

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