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