Home | History | Annotate | Download | only in quota
      1 /*
      2  * Implementation of new quotafile format
      3  *
      4  * Jan Kara <jack (at) 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 }
    656