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