lib/support/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         unsigned 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         __le32 *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 = (__le32 *) 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         errcode_t retval;
 318         unsigned int ret;
 319         char *ddquot;
 320         struct quota_handle *h = dquot->dq_h;
 321         struct qtree_mem_dqinfo *info =
 322                         &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree;
 323         log_debug("writing ddquot 1: off=%llu, info->dqi_entry_size=%u",
 324                         dquot->dq_dqb.u.v2_mdqb.dqb_off,
 325                         info->dqi_entry_size);
 326         retval = ext2fs_get_mem(info->dqi_entry_size, &ddquot);
 327         if (retval) {
 328                 errno = ENOMEM;
 329                 log_err("Quota write failed (id %u): %s",
 330                         (unsigned int)dquot->dq_id, strerror(errno));
 331                 return;
 332         }
 333         memset(ddquot, 0, info->dqi_entry_size);
 334
 335         if (!dquot->dq_dqb.u.v2_mdqb.dqb_off)
 336                 dq_insert_tree(dquot->dq_h, dquot);
 337         info->dqi_ops->mem2disk_dqblk(ddquot, dquot);
 338         log_debug("writing ddquot 2: off=%llu, info->dqi_entry_size=%u",
 339                         dquot->dq_dqb.u.v2_mdqb.dqb_off,
 340                         info->dqi_entry_size);
 341         ret = h->e2fs_write(&h->qh_qf, dquot->dq_dqb.u.v2_mdqb.dqb_off, ddquot,
 342                         info->dqi_entry_size);
 343
 344         if (ret != info->dqi_entry_size) {
 345                 if (ret > 0)
 346                         errno = ENOSPC;
 347                 log_err("Quota write failed (id %u): %s",
 348                         (unsigned int)dquot->dq_id, strerror(errno));
 349         }
 350         ext2fs_free_mem(&ddquot);
 351 }
 352
 353 /* Free dquot entry in data block */
 354 static void free_dqentry(struct quota_handle *h, struct dquot *dquot,
 355                          unsigned int blk)
 356 {
 357         struct qt_disk_dqdbheader *dh;
 358         struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
 359         dqbuf_t buf = getdqbuf();
 360
 361         if (!buf)
 362                 return;
 363
 364         if (dquot->dq_dqb.u.v2_mdqb.dqb_off >> QT_BLKSIZE_BITS != blk)
 365                 log_err("Quota structure has offset to other block (%u) "
 366                         "than it should (%u).", blk,
 367                           (unsigned int) (dquot->dq_dqb.u.v2_mdqb.dqb_off >>
 368                                   QT_BLKSIZE_BITS));
 369
 370         read_blk(h, blk, buf);
 371         dh = (struct qt_disk_dqdbheader *)buf;
 372         dh->dqdh_entries =
 373                 ext2fs_cpu_to_le16(ext2fs_le16_to_cpu(dh->dqdh_entries) - 1);
 374
 375         if (!ext2fs_le16_to_cpu(dh->dqdh_entries)) {    /* Block got free? */
 376                 remove_free_dqentry(h, buf, blk);
 377                 put_free_dqblk(h, buf, blk);
 378         } else {
 379                 memset(buf + (dquot->dq_dqb.u.v2_mdqb.dqb_off &
 380                               ((1 << QT_BLKSIZE_BITS) - 1)),
 381                        0, info->dqi_entry_size);
 382
 383                 /* First free entry? */
 384                 if (ext2fs_le16_to_cpu(dh->dqdh_entries) ==
 385                                 qtree_dqstr_in_blk(info) - 1)
 386                         /* This will also write data block */
 387                         insert_free_dqentry(h, buf, blk);
 388                 else
 389                         write_blk(h, blk, buf);
 390         }
 391         dquot->dq_dqb.u.v2_mdqb.dqb_off = 0;
 392         freedqbuf(buf);
 393 }
 394
 395 /* Remove reference to dquot from tree */
 396 static void remove_tree(struct quota_handle *h, struct dquot *dquot,
 397                         unsigned int * blk, int depth)
 398 {
 399         dqbuf_t buf = getdqbuf();
 400         unsigned int newblk;
 401         __le32 *ref = (__le32 *) buf;
 402
 403         if (!buf)
 404                 return;
 405
 406         read_blk(h, *blk, buf);
 407         newblk = ext2fs_le32_to_cpu(ref[get_index(dquot->dq_id, depth)]);
 408         if (depth == QT_TREEDEPTH - 1) {
 409                 free_dqentry(h, dquot, newblk);
 410                 newblk = 0;
 411         } else {
 412                 remove_tree(h, dquot, &newblk, depth + 1);
 413         }
 414
 415         if (!newblk) {
 416                 int i;
 417
 418                 ref[get_index(dquot->dq_id, depth)] = ext2fs_cpu_to_le32(0);
 419
 420                 /* Block got empty? */
 421                 for (i = 0; i < QT_BLKSIZE && !buf[i]; i++);
 422
 423                 /* Don't put the root block into the free block list */
 424                 if (i == QT_BLKSIZE && *blk != QT_TREEOFF) {
 425                         put_free_dqblk(h, buf, *blk);
 426                         *blk = 0;
 427                 } else {
 428                         write_blk(h, *blk, buf);
 429                 }
 430         }
 431         freedqbuf(buf);
 432 }
 433
 434 /* Delete dquot from tree */
 435 void qtree_delete_dquot(struct dquot *dquot)
 436 {
 437         unsigned int tmp = QT_TREEOFF;
 438
 439         if (!dquot->dq_dqb.u.v2_mdqb.dqb_off)   /* Even not allocated? */
 440                 return;
 441         remove_tree(dquot->dq_h, dquot, &tmp, 0);
 442 }
 443
 444 /* Find entry in block */
 445 static ext2_loff_t find_block_dqentry(struct quota_handle *h,
 446                                       struct dquot *dquot, unsigned int blk)
 447 {
 448         struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
 449         dqbuf_t buf = getdqbuf();
 450         int i;
 451         char *ddquot = buf + sizeof(struct qt_disk_dqdbheader);
 452
 453         if (!buf)
 454                 return -ENOMEM;
 455
 456         read_blk(h, blk, buf);
 457         for (i = 0;
 458              i < qtree_dqstr_in_blk(info) && !info->dqi_ops->is_id(ddquot, dquot);
 459              i++)
 460                 ddquot += info->dqi_entry_size;
 461
 462         if (i == qtree_dqstr_in_blk(info))
 463                 log_err("Quota for id %u referenced but not present.",
 464                         dquot->dq_id);
 465         freedqbuf(buf);
 466         return (blk << QT_BLKSIZE_BITS) + sizeof(struct qt_disk_dqdbheader) +
 467                 i * info->dqi_entry_size;
 468 }
 469
 470 /* Find entry for given id in the tree */
 471 static ext2_loff_t find_tree_dqentry(struct quota_handle *h,
 472                                      struct dquot *dquot,
 473                                      unsigned int blk, int depth)
 474 {
 475         dqbuf_t buf = getdqbuf();
 476         ext2_loff_t ret = 0;
 477         __le32 *ref = (__le32 *) buf;
 478
 479         if (!buf)
 480                 return -ENOMEM;
 481
 482         read_blk(h, blk, buf);
 483         ret = 0;
 484         blk = ext2fs_le32_to_cpu(ref[get_index(dquot->dq_id, depth)]);
 485         if (!blk)       /* No reference? */
 486                 goto out_buf;
 487         if (depth < QT_TREEDEPTH - 1)
 488                 ret = find_tree_dqentry(h, dquot, blk, depth + 1);
 489         else
 490                 ret = find_block_dqentry(h, dquot, blk);
 491 out_buf:
 492         freedqbuf(buf);
 493         return ret;
 494 }
 495
 496 /* Find entry for given id in the tree - wrapper function */
 497 static inline ext2_loff_t find_dqentry(struct quota_handle *h,
 498                                        struct dquot *dquot)
 499 {
 500         return find_tree_dqentry(h, dquot, QT_TREEOFF, 0);
 501 }
 502
 503 /*
 504  *  Read dquot from disk.
 505  */
 506 struct dquot *qtree_read_dquot(struct quota_handle *h, qid_t id)
 507 {
 508         struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
 509         ext2_loff_t offset;
 510         unsigned int ret;
 511         char *ddquot;
 512         struct dquot *dquot = get_empty_dquot();
 513
 514         if (!dquot)
 515                 return NULL;
 516         if (ext2fs_get_mem(info->dqi_entry_size, &ddquot)) {
 517                 ext2fs_free_mem(&dquot);
 518                 return NULL;
 519         }
 520
 521         dquot->dq_id = id;
 522         dquot->dq_h = h;
 523         dquot->dq_dqb.u.v2_mdqb.dqb_off = 0;
 524         memset(&dquot->dq_dqb, 0, sizeof(struct util_dqblk));
 525
 526         offset = find_dqentry(h, dquot);
 527         if (offset > 0) {
 528                 dquot->dq_dqb.u.v2_mdqb.dqb_off = offset;
 529                 ret = h->e2fs_read(&h->qh_qf, offset, ddquot,
 530                         info->dqi_entry_size);
 531                 if (ret != info->dqi_entry_size) {
 532                         if (ret > 0)
 533                                 errno = EIO;
 534                         log_err("Cannot read quota structure for id %u: %s",
 535                                 dquot->dq_id, strerror(errno));
 536                 }
 537                 info->dqi_ops->disk2mem_dqblk(dquot, ddquot);
 538         }
 539         ext2fs_free_mem(&ddquot);
 540         return dquot;
 541 }
 542
 543 static int check_reference(struct quota_handle *h, unsigned int blk)
 544 {
 545         if (blk >= h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks) {
 546                 log_err("Illegal reference (%u >= %u) in %s quota file",
 547                         blk, h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks,
 548                         quota_type2name(h->qh_type));
 549                 return -1;
 550         }
 551         return 0;
 552 }
 553
 554 /*
 555  * Scan all dquots in file and call callback on each
 556  */
 557 #define set_bit(bmp, ind) ((bmp)[(ind) >> 3] |= (1 << ((ind) & 7)))
 558 #define get_bit(bmp, ind) ((bmp)[(ind) >> 3] & (1 << ((ind) & 7)))
 559
 560 static int report_block(struct dquot *dquot, unsigned int blk, char *bitmap,
 561                         int (*process_dquot) (struct dquot *, void *),
 562                         void *data)
 563 {
 564         struct qtree_mem_dqinfo *info =
 565                         &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree;
 566         dqbuf_t buf = getdqbuf();
 567         struct qt_disk_dqdbheader *dh;
 568         char *ddata;
 569         int entries, i;
 570
 571         if (!buf)
 572                 return -1;
 573
 574         set_bit(bitmap, blk);
 575         read_blk(dquot->dq_h, blk, buf);
 576         dh = (struct qt_disk_dqdbheader *)buf;
 577         ddata = buf + sizeof(struct qt_disk_dqdbheader);
 578         entries = ext2fs_le16_to_cpu(dh->dqdh_entries);
 579         for (i = 0; i < qtree_dqstr_in_blk(info);
 580                         i++, ddata += info->dqi_entry_size)
 581                 if (!qtree_entry_unused(info, ddata)) {
 582                         dquot->dq_dqb.u.v2_mdqb.dqb_off =
 583                                 (blk << QT_BLKSIZE_BITS) +
 584                                 sizeof(struct qt_disk_dqdbheader) +
 585                                 i * info->dqi_entry_size;
 586                         info->dqi_ops->disk2mem_dqblk(dquot, ddata);
 587                         if (process_dquot(dquot, data) < 0)
 588                                 break;
 589                 }
 590         freedqbuf(buf);
 591         return entries;
 592 }
 593
 594 static int report_tree(struct dquot *dquot, unsigned int blk, int depth,
 595                        char *bitmap,
 596                        int (*process_dquot) (struct dquot *, void *),
 597                        void *data)
 598 {
 599         int entries = 0, ret, i;
 600         dqbuf_t buf = getdqbuf();
 601         __le32 *ref = (__le32 *) buf;
 602
 603         if (!buf)
 604                 return 0;
 605
 606         read_blk(dquot->dq_h, blk, buf);
 607         if (depth == QT_TREEDEPTH - 1) {
 608                 for (i = 0; i < QT_BLKSIZE >> 2; i++) {
 609                         blk = ext2fs_le32_to_cpu(ref[i]);
 610                         if (check_reference(dquot->dq_h, blk)) {
 611                                 entries = -1;
 612                                 goto errout;
 613                         }
 614                         if (blk && !get_bit(bitmap, blk)) {
 615                                 ret = report_block(dquot, blk, bitmap,
 616                                                    process_dquot, data);
 617                                 if (ret < 0) {
 618                                         entries = ret;
 619                                         goto errout;
 620                                 }
 621                                 entries += ret;
 622                         }
 623                 }
 624         } else {
 625                 for (i = 0; i < QT_BLKSIZE >> 2; i++) {
 626                         blk = ext2fs_le32_to_cpu(ref[i]);
 627                         if (blk) {
 628                                 if (check_reference(dquot->dq_h, blk)) {
 629                                         entries = -1;
 630                                         goto errout;
 631                                 }
 632                                 ret = report_tree(dquot, blk, depth + 1,
 633                                                   bitmap, process_dquot,
 634                                                   data);
 635                                 if (ret < 0) {
 636                                         entries = ret;
 637                                         goto errout;
 638                                 }
 639                                 entries += ret;
 640                         }
 641                 }
 642         }
 643 errout:
 644         freedqbuf(buf);
 645         return entries;
 646 }
 647
 648 static unsigned int find_set_bits(char *bmp, int blocks)
 649 {
 650         unsigned int    used = 0;
 651         int             i;
 652
 653         for (i = 0; i < blocks; i++)
 654                 if (get_bit(bmp, i))
 655                         used++;
 656         return used;
 657 }
 658
 659 int qtree_scan_dquots(struct quota_handle *h,
 660                       int (*process_dquot) (struct dquot *, void *),
 661                       void *data)
 662 {
 663         int ret;
 664         char *bitmap;
 665         struct v2_mem_dqinfo *v2info = &h->qh_info.u.v2_mdqi;
 666         struct qtree_mem_dqinfo *info = &v2info->dqi_qtree;
 667         struct dquot *dquot = get_empty_dquot();
 668
 669         if (!dquot)
 670                 return -1;
 671
 672         dquot->dq_h = h;
 673         if (ext2fs_get_memzero((info->dqi_blocks + 7) >> 3, &bitmap)) {
 674                 ext2fs_free_mem(&dquot);
 675                 return -1;
 676         }
 677         ret = report_tree(dquot, QT_TREEOFF, 0, bitmap, process_dquot, data);
 678         if (ret < 0)
 679                 goto errout;
 680         v2info->dqi_used_entries = ret;
 681         v2info->dqi_data_blocks = find_set_bits(bitmap, info->dqi_blocks);
 682         ret = 0;
 683 errout:
 684         ext2fs_free_mem(&bitmap);
 685         ext2fs_free_mem(&dquot);
 686         return ret;
 687 }