lib/quota/quotaio_tree.c

   1 /*
   2  * Implementation of new quotafile format
   3  *
   4  * Jan Kara <jack@suse.cz> - sponsored by SuSE CR
   5  */
   6
   7 #include "config.h"
   8 #include <sys/types.h>
   9 #include <errno.h>
  10 #include <stdio.h>
  11 #include <stdlib.h>
  12 #include <string.h>
  13 #include <unistd.h>
  14
  15 #include "common.h"
  16 #include "quotaio_tree.h"
  17 #include "quotaio.h"
  18
  19 typedef char *dqbuf_t;
  20
  21 #define freedqbuf(buf)          ext2fs_free_mem(&buf)
  22
  23 static inline dqbuf_t getdqbuf(void)
  24 {
  25         dqbuf_t buf;
  26         if (ext2fs_get_memzero(QT_BLKSIZE, &buf)) {
  27                 log_err("Failed to allocate dqbuf");
  28                 return NULL;
  29         }
  30
  31         return buf;
  32 }
  33
  34 /* Is given dquot empty? */
  35 int qtree_entry_unused(struct qtree_mem_dqinfo *info, char *disk)
  36 {
  37         int i;
  38
  39         for (i = 0; i < info->dqi_entry_size; i++)
  40                 if (disk[i])
  41                         return 0;
  42         return 1;
  43 }
  44
  45 int qtree_dqstr_in_blk(struct qtree_mem_dqinfo *info)
  46 {
  47         return (QT_BLKSIZE - sizeof(struct qt_disk_dqdbheader)) /
  48                 info->dqi_entry_size;
  49 }
  50
  51 static int get_index(qid_t id, int depth)
  52 {
  53         return (id >> ((QT_TREEDEPTH - depth - 1) * 8)) & 0xff;
  54 }
  55
  56 static inline void mark_quotafile_info_dirty(struct quota_handle *h)
  57 {
  58         h->qh_io_flags |= IOFL_INFODIRTY;
  59 }
  60
  61 /* Read given block */
  62 static void read_blk(struct quota_handle *h, unsigned int blk, dqbuf_t buf)
  63 {
  64         int err;
  65
  66         err = h->e2fs_read(&h->qh_qf, blk << QT_BLKSIZE_BITS, buf,
  67                         QT_BLKSIZE);
  68         if (err < 0)
  69                 log_err("Cannot read block %u: %s", blk, strerror(errno));
  70         else if (err != QT_BLKSIZE)
  71                 memset(buf + err, 0, QT_BLKSIZE - err);
  72 }
  73
  74 /* Write block */
  75 static int write_blk(struct quota_handle *h, unsigned int blk, dqbuf_t buf)
  76 {
  77         int err;
  78
  79         err = h->e2fs_write(&h->qh_qf, blk << QT_BLKSIZE_BITS, buf,
  80                         QT_BLKSIZE);
  81         if (err < 0 && errno != ENOSPC)
  82                 log_err("Cannot write block (%u): %s", blk, strerror(errno));
  83         if (err != QT_BLKSIZE)
  84                 return -ENOSPC;
  85         return 0;
  86 }
  87
  88 /* Get free block in file (either from free list or create new one) */
  89 static int get_free_dqblk(struct quota_handle *h)
  90 {
  91         dqbuf_t buf = getdqbuf();
  92         struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
  93         struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
  94         int blk;
  95
  96         if (!buf)
  97                 return -ENOMEM;
  98
  99         if (info->dqi_free_blk) {
 100                 blk = info->dqi_free_blk;
 101                 read_blk(h, blk, buf);
 102                 info->dqi_free_blk = ext2fs_le32_to_cpu(dh->dqdh_next_free);
 103         } else {
 104                 memset(buf, 0, QT_BLKSIZE);
 105                 /* Assure block allocation... */
 106                 if (write_blk(h, info->dqi_blocks, buf) < 0) {
 107                         freedqbuf(buf);
 108                         log_err("Cannot allocate new quota block "
 109                                 "(out of disk space).");
 110                         return -ENOSPC;
 111                 }
 112                 blk = info->dqi_blocks++;
 113         }
 114         mark_quotafile_info_dirty(h);
 115         freedqbuf(buf);
 116         return blk;
 117 }
 118
 119 /* Put given block to free list */
 120 static void put_free_dqblk(struct quota_handle *h, dqbuf_t buf,
 121                            unsigned int blk)
 122 {
 123         struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
 124         struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
 125
 126         dh->dqdh_next_free = ext2fs_cpu_to_le32(info->dqi_free_blk);
 127         dh->dqdh_prev_free = ext2fs_cpu_to_le32(0);
 128         dh->dqdh_entries = ext2fs_cpu_to_le16(0);
 129         info->dqi_free_blk = blk;
 130         mark_quotafile_info_dirty(h);
 131         write_blk(h, blk, buf);
 132 }
 133
 134 /* Remove given block from the list of blocks with free entries */
 135 static void remove_free_dqentry(struct quota_handle *h, dqbuf_t buf,
 136                                 unsigned int blk)
 137 {
 138         dqbuf_t tmpbuf = getdqbuf();
 139         struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
 140         unsigned int nextblk = ext2fs_le32_to_cpu(dh->dqdh_next_free), prevblk =
 141
 142                 ext2fs_le32_to_cpu(dh->dqdh_prev_free);
 143
 144         if (!tmpbuf)
 145                 return;
 146
 147         if (nextblk) {
 148                 read_blk(h, nextblk, tmpbuf);
 149                 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free =
 150                                 dh->dqdh_prev_free;
 151                 write_blk(h, nextblk, tmpbuf);
 152         }
 153         if (prevblk) {
 154                 read_blk(h, prevblk, tmpbuf);
 155                 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_next_free =
 156                                 dh->dqdh_next_free;
 157                 write_blk(h, prevblk, tmpbuf);
 158         } else {
 159                 h->qh_info.u.v2_mdqi.dqi_qtree.dqi_free_entry = nextblk;
 160                 mark_quotafile_info_dirty(h);
 161         }
 162         freedqbuf(tmpbuf);
 163         dh->dqdh_next_free = dh->dqdh_prev_free = ext2fs_cpu_to_le32(0);
 164         write_blk(h, blk, buf); /* No matter whether write succeeds
 165                                  * block is out of list */
 166 }
 167
 168 /* Insert given block to the beginning of list with free entries */
 169 static void insert_free_dqentry(struct quota_handle *h, dqbuf_t buf,
 170                                 unsigned int blk)
 171 {
 172         dqbuf_t tmpbuf = getdqbuf();
 173         struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
 174         struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
 175
 176         if (!tmpbuf)
 177                 return;
 178
 179         dh->dqdh_next_free = ext2fs_cpu_to_le32(info->dqi_free_entry);
 180         dh->dqdh_prev_free = ext2fs_cpu_to_le32(0);
 181         write_blk(h, blk, buf);
 182         if (info->dqi_free_entry) {
 183                 read_blk(h, info->dqi_free_entry, tmpbuf);
 184                 ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free =
 185                                 ext2fs_cpu_to_le32(blk);
 186                 write_blk(h, info->dqi_free_entry, tmpbuf);
 187         }
 188         freedqbuf(tmpbuf);
 189         info->dqi_free_entry = blk;
 190         mark_quotafile_info_dirty(h);
 191 }
 192
 193 /* Find space for dquot */
 194 static unsigned int find_free_dqentry(struct quota_handle *h,
 195                                       struct dquot *dquot, int *err)
 196 {
 197         int blk, i;
 198         struct qt_disk_dqdbheader *dh;
 199         struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
 200         char *ddquot;
 201         dqbuf_t buf;
 202
 203         *err = 0;
 204         buf = getdqbuf();
 205         if (!buf) {
 206                 *err = -ENOMEM;
 207                 return 0;
 208         }
 209
 210         dh = (struct qt_disk_dqdbheader *)buf;
 211         if (info->dqi_free_entry) {
 212                 blk = info->dqi_free_entry;
 213                 read_blk(h, blk, buf);
 214         } else {
 215                 blk = get_free_dqblk(h);
 216                 if (blk < 0) {
 217                         freedqbuf(buf);
 218                         *err = blk;
 219                         return 0;
 220                 }
 221                 memset(buf, 0, QT_BLKSIZE);
 222                 info->dqi_free_entry = blk;
 223                 mark_quotafile_info_dirty(h);
 224         }
 225
 226         /* Block will be full? */
 227         if (ext2fs_le16_to_cpu(dh->dqdh_entries) + 1 >=
 228             qtree_dqstr_in_blk(info))
 229                 remove_free_dqentry(h, buf, blk);
 230
 231         dh->dqdh_entries =
 232                 ext2fs_cpu_to_le16(ext2fs_le16_to_cpu(dh->dqdh_entries) + 1);
 233         /* Find free structure in block */
 234         ddquot = buf + sizeof(struct qt_disk_dqdbheader);
 235         for (i = 0;
 236              i < qtree_dqstr_in_blk(info) && !qtree_entry_unused(info, ddquot);
 237              i++)
 238                 ddquot += info->dqi_entry_size;
 239
 240         if (i == qtree_dqstr_in_blk(info))
 241                 log_err("find_free_dqentry(): Data block full unexpectedly.");
 242
 243         write_blk(h, blk, buf);
 244         dquot->dq_dqb.u.v2_mdqb.dqb_off =
 245                 (blk << QT_BLKSIZE_BITS) + sizeof(struct qt_disk_dqdbheader) +
 246                 i * info->dqi_entry_size;
 247         freedqbuf(buf);
 248         return blk;
 249 }
 250
 251 /* Insert reference to structure into the trie */
 252 static int do_insert_tree(struct quota_handle *h, struct dquot *dquot,
 253                           unsigned int * treeblk, int depth)
 254 {
 255         dqbuf_t buf;
 256         int newson = 0, newact = 0;
 257         __u32 *ref;
 258         unsigned int newblk;
 259         int ret = 0;
 260
 261         log_debug("inserting in tree: treeblk=%u, depth=%d", *treeblk, depth);
 262         buf = getdqbuf();
 263         if (!buf)
 264                 return -ENOMEM;
 265
 266         if (!*treeblk) {
 267                 ret = get_free_dqblk(h);
 268                 if (ret < 0)
 269                         goto out_buf;
 270                 *treeblk = ret;
 271                 memset(buf, 0, QT_BLKSIZE);
 272                 newact = 1;
 273         } else {
 274                 read_blk(h, *treeblk, buf);
 275         }
 276
 277         ref = (__u32 *) buf;
 278         newblk = ext2fs_le32_to_cpu(ref[get_index(dquot->dq_id, depth)]);
 279         if (!newblk)
 280                 newson = 1;
 281         if (depth == QT_TREEDEPTH - 1) {
 282                 if (newblk)
 283                         log_err("Inserting already present quota entry "
 284                                 "(block %u).",
 285                                 ref[get_index(dquot->dq_id, depth)]);
 286                 newblk = find_free_dqentry(h, dquot, &ret);
 287         } else {
 288                 ret = do_insert_tree(h, dquot, &newblk, depth + 1);
 289         }
 290
 291         if (newson && ret >= 0) {
 292                 ref[get_index(dquot->dq_id, depth)] =
 293                         ext2fs_cpu_to_le32(newblk);
 294                 write_blk(h, *treeblk, buf);
 295         } else if (newact && ret < 0) {
 296                 put_free_dqblk(h, buf, *treeblk);
 297         }
 298
 299 out_buf:
 300         freedqbuf(buf);
 301         return ret;
 302 }
 303
 304 /* Wrapper for inserting quota structure into tree */
 305 static void dq_insert_tree(struct quota_handle *h, struct dquot *dquot)
 306 {
 307         unsigned int tmp = QT_TREEOFF;
 308
 309         if (do_insert_tree(h, dquot, &tmp, 0) < 0)
 310                 log_err("Cannot write quota (id %u): %s",
 311                         (unsigned int) dquot->dq_id, strerror(errno));
 312 }
 313
 314 /* Write dquot to file */
 315 void qtree_write_dquot(struct dquot *dquot)
 316 {
 317         ssize_t ret;
 318         char *ddquot;
 319         struct quota_handle *h = dquot->dq_h;
 320         struct qtree_mem_dqinfo *info =
 321                         &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree;
 322         log_debug("writing ddquot 1: off=%llu, info->dqi_entry_size=%u",
 323                         dquot->dq_dqb.u.v2_mdqb.dqb_off,
 324                         info->dqi_entry_size);
 325         ret = ext2fs_get_mem(info->dqi_entry_size, &ddquot);
 326         if (ret) {
 327                 errno = ENOMEM;
 328                 log_err("Quota write failed (id %u): %s",
 329                         (unsigned int)dquot->dq_id, strerror(errno));
 330                 return;
 331         }
 332         memset(ddquot, 0, info->dqi_entry_size);
 333
 334         if (!dquot->dq_dqb.u.v2_mdqb.dqb_off)
 335                 dq_insert_tree(dquot->dq_h, dquot);
 336         info->dqi_ops->mem2disk_dqblk(ddquot, dquot);
 337         log_debug("writing ddquot 2: off=%llu, info->dqi_entry_size=%u",
 338                         dquot->dq_dqb.u.v2_mdqb.dqb_off,
 339                         info->dqi_entry_size);
 340         ret = h->e2fs_write(&h->qh_qf, dquot->dq_dqb.u.v2_mdqb.dqb_off, ddquot,
 341                         info->dqi_entry_size);
 342
 343         if (ret != info->dqi_entry_size) {
 344                 if (ret > 0)
 345                         errno = ENOSPC;
 346                 log_err("Quota write failed (id %u): %s",
 347                         (unsigned int)dquot->dq_id, strerror(errno));
 348         }
 349         ext2fs_free_mem(&ddquot);
 350 }
 351
 352 /* Free dquot entry in data block */
 353 static void free_dqentry(struct quota_handle *h, struct dquot *dquot,
 354                          unsigned int blk)
 355 {
 356         struct qt_disk_dqdbheader *dh;
 357         struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
 358         dqbuf_t buf = getdqbuf();
 359
 360         if (!buf)
 361                 return;
 362
 363         if (dquot->dq_dqb.u.v2_mdqb.dqb_off >> QT_BLKSIZE_BITS != blk)
 364                 log_err("Quota structure has offset to other block (%u) "
 365                         "than it should (%u).", blk,
 366                           (unsigned int) (dquot->dq_dqb.u.v2_mdqb.dqb_off >>
 367                                   QT_BLKSIZE_BITS));
 368
 369         read_blk(h, blk, buf);
 370         dh = (struct qt_disk_dqdbheader *)buf;
 371         dh->dqdh_entries =
 372                 ext2fs_cpu_to_le16(ext2fs_le16_to_cpu(dh->dqdh_entries) - 1);
 373
 374         if (!ext2fs_le16_to_cpu(dh->dqdh_entries)) {    /* Block got free? */
 375                 remove_free_dqentry(h, buf, blk);
 376                 put_free_dqblk(h, buf, blk);
 377         } else {
 378                 memset(buf + (dquot->dq_dqb.u.v2_mdqb.dqb_off &
 379                               ((1 << QT_BLKSIZE_BITS) - 1)),
 380                        0, info->dqi_entry_size);
 381
 382                 /* First free entry? */
 383                 if (ext2fs_le16_to_cpu(dh->dqdh_entries) ==
 384                                 qtree_dqstr_in_blk(info) - 1)
 385                         /* This will also write data block */
 386                         insert_free_dqentry(h, buf, blk);
 387                 else
 388                         write_blk(h, blk, buf);
 389         }
 390         dquot->dq_dqb.u.v2_mdqb.dqb_off = 0;
 391         freedqbuf(buf);
 392 }
 393
 394 /* Remove reference to dquot from tree */
 395 static void remove_tree(struct quota_handle *h, struct dquot *dquot,
 396                         unsigned int * blk, int depth)
 397 {
 398         dqbuf_t buf = getdqbuf();
 399         unsigned int newblk;
 400         __u32 *ref = (__u32 *) buf;
 401
 402         if (!buf)
 403                 return;
 404
 405         read_blk(h, *blk, buf);
 406         newblk = ext2fs_le32_to_cpu(ref[get_index(dquot->dq_id, depth)]);
 407         if (depth == QT_TREEDEPTH - 1) {
 408                 free_dqentry(h, dquot, newblk);
 409                 newblk = 0;
 410         } else {
 411                 remove_tree(h, dquot, &newblk, depth + 1);
 412         }
 413
 414         if (!newblk) {
 415                 int i;
 416
 417                 ref[get_index(dquot->dq_id, depth)] = ext2fs_cpu_to_le32(0);
 418
 419                 /* Block got empty? */
 420                 for (i = 0; i < QT_BLKSIZE && !buf[i]; i++);
 421
 422                 /* Don't put the root block into the free block list */
 423                 if (i == QT_BLKSIZE && *blk != QT_TREEOFF) {
 424                         put_free_dqblk(h, buf, *blk);
 425                         *blk = 0;
 426                 } else {
 427                         write_blk(h, *blk, buf);
 428                 }
 429         }
 430         freedqbuf(buf);
 431 }
 432
 433 /* Delete dquot from tree */
 434 void qtree_delete_dquot(struct dquot *dquot)
 435 {
 436         unsigned int tmp = QT_TREEOFF;
 437
 438         if (!dquot->dq_dqb.u.v2_mdqb.dqb_off)   /* Even not allocated? */
 439                 return;
 440         remove_tree(dquot->dq_h, dquot, &tmp, 0);
 441 }
 442
 443 /* Find entry in block */
 444 static ext2_loff_t find_block_dqentry(struct quota_handle *h,
 445                                       struct dquot *dquot, unsigned int blk)
 446 {
 447         struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
 448         dqbuf_t buf = getdqbuf();
 449         int i;
 450         char *ddquot = buf + sizeof(struct qt_disk_dqdbheader);
 451
 452         if (!buf)
 453                 return -ENOMEM;
 454
 455         read_blk(h, blk, buf);
 456         for (i = 0;
 457              i < qtree_dqstr_in_blk(info) && !info->dqi_ops->is_id(ddquot, dquot);
 458              i++)
 459                 ddquot += info->dqi_entry_size;
 460
 461         if (i == qtree_dqstr_in_blk(info))
 462                 log_err("Quota for id %u referenced but not present.",
 463                         dquot->dq_id);
 464         freedqbuf(buf);
 465         return (blk << QT_BLKSIZE_BITS) + sizeof(struct qt_disk_dqdbheader) +
 466                 i * info->dqi_entry_size;
 467 }
 468
 469 /* Find entry for given id in the tree */
 470 static ext2_loff_t find_tree_dqentry(struct quota_handle *h,
 471                                      struct dquot *dquot,
 472                                      unsigned int blk, int depth)
 473 {
 474         dqbuf_t buf = getdqbuf();
 475         ext2_loff_t ret = 0;
 476         __u32 *ref = (__u32 *) buf;
 477
 478         if (!buf)
 479                 return -ENOMEM;
 480
 481         read_blk(h, blk, buf);
 482         ret = 0;
 483         blk = ext2fs_le32_to_cpu(ref[get_index(dquot->dq_id, depth)]);
 484         if (!blk)       /* No reference? */
 485                 goto out_buf;
 486         if (depth < QT_TREEDEPTH - 1)
 487                 ret = find_tree_dqentry(h, dquot, blk, depth + 1);
 488         else
 489                 ret = find_block_dqentry(h, dquot, blk);
 490 out_buf:
 491         freedqbuf(buf);
 492         return ret;
 493 }
 494
 495 /* Find entry for given id in the tree - wrapper function */
 496 static inline ext2_loff_t find_dqentry(struct quota_handle *h,
 497                                        struct dquot *dquot)
 498 {
 499         return find_tree_dqentry(h, dquot, QT_TREEOFF, 0);
 500 }
 501
 502 /*
 503  *  Read dquot from disk.
 504  */
 505 struct dquot *qtree_read_dquot(struct quota_handle *h, qid_t id)
 506 {
 507         struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
 508         ext2_loff_t offset;
 509         ssize_t ret;
 510         char *ddquot;
 511         struct dquot *dquot = get_empty_dquot();
 512
 513         if (!dquot)
 514                 return NULL;
 515         if (ext2fs_get_mem(info->dqi_entry_size, &ddquot)) {
 516                 ext2fs_free_mem(&dquot);
 517                 return NULL;
 518         }
 519
 520         dquot->dq_id = id;
 521         dquot->dq_h = h;
 522         dquot->dq_dqb.u.v2_mdqb.dqb_off = 0;
 523         memset(&dquot->dq_dqb, 0, sizeof(struct util_dqblk));
 524
 525         offset = find_dqentry(h, dquot);
 526         if (offset > 0) {
 527                 dquot->dq_dqb.u.v2_mdqb.dqb_off = offset;
 528                 ret = h->e2fs_read(&h->qh_qf, offset, ddquot,
 529                         info->dqi_entry_size);
 530                 if (ret != info->dqi_entry_size) {
 531                         if (ret > 0)
 532                                 errno = EIO;
 533                         log_err("Cannot read quota structure for id %u: %s",
 534                                 dquot->dq_id, strerror(errno));
 535                 }
 536                 info->dqi_ops->disk2mem_dqblk(dquot, ddquot);
 537         }
 538         ext2fs_free_mem(&ddquot);
 539         return dquot;
 540 }
 541
 542 /*
 543  * Scan all dquots in file and call callback on each
 544  */
 545 #define set_bit(bmp, ind) ((bmp)[(ind) >> 3] |= (1 << ((ind) & 7)))
 546 #define get_bit(bmp, ind) ((bmp)[(ind) >> 3] & (1 << ((ind) & 7)))
 547
 548 static int report_block(struct dquot *dquot, unsigned int blk, char *bitmap,
 549                         int (*process_dquot) (struct dquot *, void *),
 550                         void *data)
 551 {
 552         struct qtree_mem_dqinfo *info =
 553                         &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree;
 554         dqbuf_t buf = getdqbuf();
 555         struct qt_disk_dqdbheader *dh;
 556         char *ddata;
 557         int entries, i;
 558
 559         if (!buf)
 560                 return 0;
 561
 562         set_bit(bitmap, blk);
 563         read_blk(dquot->dq_h, blk, buf);
 564         dh = (struct qt_disk_dqdbheader *)buf;
 565         ddata = buf + sizeof(struct qt_disk_dqdbheader);
 566         entries = ext2fs_le16_to_cpu(dh->dqdh_entries);
 567         for (i = 0; i < qtree_dqstr_in_blk(info);
 568                         i++, ddata += info->dqi_entry_size)
 569                 if (!qtree_entry_unused(info, ddata)) {
 570                         dquot->dq_dqb.u.v2_mdqb.dqb_off =
 571                                 (blk << QT_BLKSIZE_BITS) +
 572                                 sizeof(struct qt_disk_dqdbheader) +
 573                                 i * info->dqi_entry_size;
 574                         info->dqi_ops->disk2mem_dqblk(dquot, ddata);
 575                         if (process_dquot(dquot, data) < 0)
 576                                 break;
 577                 }
 578         freedqbuf(buf);
 579         return entries;
 580 }
 581
 582 static void check_reference(struct quota_handle *h, unsigned int blk)
 583 {
 584         if (blk >= h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks)
 585                 log_err("Illegal reference (%u >= %u) in %s quota file. "
 586                         "Quota file is probably corrupted.\n"
 587                         "Please run e2fsck (8) to fix it.",
 588                         blk,
 589                         h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks,
 590                         quota_type2name(h->qh_type));
 591 }
 592
 593 static int report_tree(struct dquot *dquot, unsigned int blk, int depth,
 594                        char *bitmap,
 595                        int (*process_dquot) (struct dquot *, void *),
 596                        void *data)
 597 {
 598         int entries = 0, i;
 599         dqbuf_t buf = getdqbuf();
 600         __u32 *ref = (__u32 *) buf;
 601
 602         if (!buf)
 603                 return 0;
 604
 605         read_blk(dquot->dq_h, blk, buf);
 606         if (depth == QT_TREEDEPTH - 1) {
 607                 for (i = 0; i < QT_BLKSIZE >> 2; i++) {
 608                         blk = ext2fs_le32_to_cpu(ref[i]);
 609                         check_reference(dquot->dq_h, blk);
 610                         if (blk && !get_bit(bitmap, blk))
 611                                 entries += report_block(dquot, blk, bitmap,
 612                                                         process_dquot, data);
 613                 }
 614         } else {
 615                 for (i = 0; i < QT_BLKSIZE >> 2; i++) {
 616                         blk = ext2fs_le32_to_cpu(ref[i]);
 617                         if (blk) {
 618                                 check_reference(dquot->dq_h, blk);
 619                                 entries += report_tree(dquot, blk, depth + 1,
 620                                                        bitmap, process_dquot,
 621                                                        data);
 622                         }
 623                 }
 624         }
 625         freedqbuf(buf);
 626         return entries;
 627 }
 628
 629 static unsigned int find_set_bits(char *bmp, int blocks)
 630 {
 631         unsigned int i, used = 0;
 632
 633         for (i = 0; i < blocks; i++)
 634                 if (get_bit(bmp, i))
 635                         used++;
 636         return used;
 637 }
 638
 639 int qtree_scan_dquots(struct quota_handle *h,
 640                       int (*process_dquot) (struct dquot *, void *),
 641                       void *data)
 642 {
 643         char *bitmap;
 644         struct v2_mem_dqinfo *v2info = &h->qh_info.u.v2_mdqi;
 645         struct qtree_mem_dqinfo *info = &v2info->dqi_qtree;
 646         struct dquot *dquot = get_empty_dquot();
 647
 648         if (!dquot)
 649                 return -1;
 650
 651         dquot->dq_h = h;
 652         if (ext2fs_get_memzero((info->dqi_blocks + 7) >> 3, &bitmap)) {
 653                 ext2fs_free_mem(&dquot);
 654                 return -1;
 655         }
 656         v2info->dqi_used_entries = report_tree(dquot, QT_TREEOFF, 0, bitmap,
 657                                                process_dquot, data);
 658         v2info->dqi_data_blocks = find_set_bits(bitmap, info->dqi_blocks);
 659         ext2fs_free_mem(&bitmap);
 660         ext2fs_free_mem(&dquot);
 661         return 0;
 662 }