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