1 /*
2  * Implementation of new quotafile format
3  *
4  * Jan Kara <jack@suse.cz> - sponsored by SuSE CR
5  * Hyojun Kim <hyojun@google.com> - Ported to f2fs-tools
6  */
7 
8 #include "config.h"
9 #include <sys/types.h>
10 #include <errno.h>
11 #include <stdio.h>
12 #include <stdlib.h>
13 #include <string.h>
14 #include <unistd.h>
15 
16 #include "common.h"
17 #include "quotaio_tree.h"
18 #include "quotaio.h"
19 
20 typedef char *dqbuf_t;
21 
22 #define freedqbuf(buf)		quota_free_mem(&buf)
23 
24 static inline dqbuf_t getdqbuf(void)
25 {
26 	dqbuf_t buf;
27 	if (quota_get_memzero(QT_BLKSIZE, &buf)) {
28 		log_err("Failed to allocate dqbuf");
29 		return NULL;
30 	}
31 
32 	return buf;
33 }
34 
35 /* Is given dquot empty? */
36 int qtree_entry_unused(struct qtree_mem_dqinfo *info, char *disk)
37 {
38 	unsigned int i;
39 
40 	for (i = 0; i < info->dqi_entry_size; i++)
41 		if (disk[i])
42 			return 0;
43 	return 1;
44 }
45 
46 int qtree_dqstr_in_blk(struct qtree_mem_dqinfo *info)
47 {
48 	return (QT_BLKSIZE - sizeof(struct qt_disk_dqdbheader)) /
49 		info->dqi_entry_size;
50 }
51 
52 static int get_index(qid_t id, int depth)
53 {
54 	return (id >> ((QT_TREEDEPTH - depth - 1) * 8)) & 0xff;
55 }
56 
57 static inline void mark_quotafile_info_dirty(struct quota_handle *h)
58 {
59 	h->qh_io_flags |= IOFL_INFODIRTY;
60 }
61 
62 /* Read given block */
63 static void read_blk(struct quota_handle *h, unsigned int blk, dqbuf_t buf)
64 {
65 	int err;
66 
67 	err = h->read(&h->qh_qf, blk << QT_BLKSIZE_BITS, buf,
68 			QT_BLKSIZE);
69 	if (err < 0)
70 		log_err("Cannot read block %u: %s", blk, strerror(errno));
71 	else if (err != QT_BLKSIZE)
72 		memset(buf + err, 0, QT_BLKSIZE - err);
73 }
74 
75 /* Write block */
76 static int write_blk(struct quota_handle *h, unsigned int blk, dqbuf_t buf)
77 {
78 	int err;
79 
80 	err = h->write(&h->qh_qf, blk << QT_BLKSIZE_BITS, buf,
81 			QT_BLKSIZE);
82 	if (err < 0 && errno != ENOSPC)
83 		log_err("Cannot write block (%u): %s", blk, strerror(errno));
84 	if (err != QT_BLKSIZE)
85 		return -ENOSPC;
86 	return 0;
87 }
88 
89 /* Get free block in file (either from free list or create new one) */
90 static int get_free_dqblk(struct quota_handle *h)
91 {
92 	dqbuf_t buf = getdqbuf();
93 	struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
94 	struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
95 	int blk;
96 
97 	if (!buf)
98 		return -ENOMEM;
99 
100 	if (info->dqi_free_blk) {
101 		blk = info->dqi_free_blk;
102 		read_blk(h, blk, buf);
103 		info->dqi_free_blk = le32_to_cpu(dh->dqdh_next_free);
104 	} else {
105 		memset(buf, 0, QT_BLKSIZE);
106 		/* Assure block allocation... */
107 		if (write_blk(h, info->dqi_blocks, buf) < 0) {
108 			freedqbuf(buf);
109 			log_err("Cannot allocate new quota block "
110 				"(out of disk space).");
111 			return -ENOSPC;
112 		}
113 		blk = info->dqi_blocks++;
114 	}
115 	mark_quotafile_info_dirty(h);
116 	freedqbuf(buf);
117 	return blk;
118 }
119 
120 /* Put given block to free list */
121 static void put_free_dqblk(struct quota_handle *h, dqbuf_t buf,
122 			   unsigned int blk)
123 {
124 	struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
125 	struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
126 
127 	dh->dqdh_next_free = cpu_to_le32(info->dqi_free_blk);
128 	dh->dqdh_prev_free = cpu_to_le32(0);
129 	dh->dqdh_entries = cpu_to_le16(0);
130 	info->dqi_free_blk = blk;
131 	mark_quotafile_info_dirty(h);
132 	write_blk(h, blk, buf);
133 }
134 
135 /* Remove given block from the list of blocks with free entries */
136 static void remove_free_dqentry(struct quota_handle *h, dqbuf_t buf,
137 				unsigned int blk)
138 {
139 	dqbuf_t tmpbuf = getdqbuf();
140 	struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
141 	unsigned int nextblk = le32_to_cpu(dh->dqdh_next_free), prevblk =
142 		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 = 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 = cpu_to_le32(info->dqi_free_entry);
180 	dh->dqdh_prev_free = 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 				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 (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 		cpu_to_le16(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 = 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 			cpu_to_le32(newblk);
294 		ret = write_blk(h, *treeblk, buf);
295 		if (ret)
296 			goto out_buf;
297 	} else if (newact && ret < 0) {
298 		put_free_dqblk(h, buf, *treeblk);
299 	}
300 
301 out_buf:
302 	freedqbuf(buf);
303 	return ret;
304 }
305 
306 /* Wrapper for inserting quota structure into tree */
307 static int dq_insert_tree(struct quota_handle *h, struct dquot *dquot)
308 {
309 	unsigned int tmp = QT_TREEOFF;
310 	int err;
311 
312 	err = do_insert_tree(h, dquot, &tmp, 0);
313 	if (err < 0)
314 		log_err("Cannot write quota (id %u): %s",
315 			(unsigned int) dquot->dq_id, strerror(errno));
316 	return err;
317 }
318 
319 /* Write dquot to file */
320 int qtree_write_dquot(struct dquot *dquot)
321 {
322 	errcode_t retval;
323 	unsigned int ret;
324 	char *ddquot;
325 	struct quota_handle *h = dquot->dq_h;
326 	struct qtree_mem_dqinfo *info =
327 			&dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree;
328 
329 	log_debug("writing ddquot 1: off=%llu, info->dqi_entry_size=%u",
330 			dquot->dq_dqb.u.v2_mdqb.dqb_off,
331 			info->dqi_entry_size);
332 	retval = quota_get_mem(info->dqi_entry_size, &ddquot);
333 	if (retval) {
334 		log_err("Quota write failed (id %u): %s",
335 			(unsigned int)dquot->dq_id, strerror(errno));
336 		return -ENOMEM;
337 	}
338 	memset(ddquot, 0, info->dqi_entry_size);
339 
340 	if (!dquot->dq_dqb.u.v2_mdqb.dqb_off) {
341 		if (dq_insert_tree(dquot->dq_h, dquot)) {
342 			quota_free_mem(&ddquot);
343 			return -EIO;
344 		}
345 	}
346 	info->dqi_ops->mem2disk_dqblk(ddquot, dquot);
347 	log_debug("writing ddquot 2: off=%llu, info->dqi_entry_size=%u",
348 			dquot->dq_dqb.u.v2_mdqb.dqb_off,
349 			info->dqi_entry_size);
350 	ret = h->write(&h->qh_qf, dquot->dq_dqb.u.v2_mdqb.dqb_off, ddquot,
351 			info->dqi_entry_size);
352 
353 	if (ret != info->dqi_entry_size) {
354 		log_err("Quota write failed (id %u): %s",
355 			(unsigned int)dquot->dq_id, strerror(errno));
356 		quota_free_mem(&ddquot);
357 		return ret;
358 	}
359 	quota_free_mem(&ddquot);
360 	return 0;
361 }
362 
363 /* Free dquot entry in data block */
364 static void free_dqentry(struct quota_handle *h, struct dquot *dquot,
365 			 unsigned int blk)
366 {
367 	struct qt_disk_dqdbheader *dh;
368 	struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
369 	dqbuf_t buf = getdqbuf();
370 
371 	if (!buf)
372 		return;
373 
374 	if (dquot->dq_dqb.u.v2_mdqb.dqb_off >> QT_BLKSIZE_BITS != blk)
375 		log_err("Quota structure has offset to other block (%u) "
376 			"than it should (%u).", blk,
377 			  (unsigned int) (dquot->dq_dqb.u.v2_mdqb.dqb_off >>
378 				  QT_BLKSIZE_BITS));
379 
380 	read_blk(h, blk, buf);
381 	dh = (struct qt_disk_dqdbheader *)buf;
382 	dh->dqdh_entries =
383 		cpu_to_le16(le16_to_cpu(dh->dqdh_entries) - 1);
384 
385 	if (!le16_to_cpu(dh->dqdh_entries)) {	/* Block got free? */
386 		remove_free_dqentry(h, buf, blk);
387 		put_free_dqblk(h, buf, blk);
388 	} else {
389 		memset(buf + (dquot->dq_dqb.u.v2_mdqb.dqb_off &
390 			      ((1 << QT_BLKSIZE_BITS) - 1)),
391 		       0, info->dqi_entry_size);
392 
393 		/* First free entry? */
394 		if (le16_to_cpu(dh->dqdh_entries) ==
395 				qtree_dqstr_in_blk(info) - 1)
396 			/* This will also write data block */
397 			insert_free_dqentry(h, buf, blk);
398 		else
399 			write_blk(h, blk, buf);
400 	}
401 	dquot->dq_dqb.u.v2_mdqb.dqb_off = 0;
402 	freedqbuf(buf);
403 }
404 
405 /* Remove reference to dquot from tree */
406 static void remove_tree(struct quota_handle *h, struct dquot *dquot,
407 			unsigned int * blk, int depth)
408 {
409 	dqbuf_t buf = getdqbuf();
410 	unsigned int newblk;
411 	__le32 *ref = (__le32 *) buf;
412 
413 	if (!buf)
414 		return;
415 
416 	read_blk(h, *blk, buf);
417 	newblk = le32_to_cpu(ref[get_index(dquot->dq_id, depth)]);
418 	if (depth == QT_TREEDEPTH - 1) {
419 		free_dqentry(h, dquot, newblk);
420 		newblk = 0;
421 	} else {
422 		remove_tree(h, dquot, &newblk, depth + 1);
423 	}
424 
425 	if (!newblk) {
426 		int i;
427 
428 		ref[get_index(dquot->dq_id, depth)] = cpu_to_le32(0);
429 
430 		/* Block got empty? */
431 		for (i = 0; i < QT_BLKSIZE && !buf[i]; i++);
432 
433 		/* Don't put the root block into the free block list */
434 		if (i == QT_BLKSIZE && *blk != QT_TREEOFF) {
435 			put_free_dqblk(h, buf, *blk);
436 			*blk = 0;
437 		} else {
438 			write_blk(h, *blk, buf);
439 		}
440 	}
441 	freedqbuf(buf);
442 }
443 
444 /* Delete dquot from tree */
445 void qtree_delete_dquot(struct dquot *dquot)
446 {
447 	unsigned int tmp = QT_TREEOFF;
448 
449 	if (!dquot->dq_dqb.u.v2_mdqb.dqb_off)	/* Even not allocated? */
450 		return;
451 	remove_tree(dquot->dq_h, dquot, &tmp, 0);
452 }
453 
454 /* Find entry in block */
455 static long find_block_dqentry(struct quota_handle *h,
456 				      struct dquot *dquot, unsigned int blk)
457 {
458 	struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
459 	dqbuf_t buf = getdqbuf();
460 	int i;
461 	char *ddquot = buf + sizeof(struct qt_disk_dqdbheader);
462 
463 	if (!buf)
464 		return -ENOMEM;
465 
466 	read_blk(h, blk, buf);
467 	for (i = 0;
468 	     i < qtree_dqstr_in_blk(info) && !info->dqi_ops->is_id(ddquot, dquot);
469 	     i++)
470 		ddquot += info->dqi_entry_size;
471 
472 	if (i == qtree_dqstr_in_blk(info))
473 		log_err("Quota for id %u referenced but not present.",
474 			dquot->dq_id);
475 	freedqbuf(buf);
476 	return (blk << QT_BLKSIZE_BITS) + sizeof(struct qt_disk_dqdbheader) +
477 		i * info->dqi_entry_size;
478 }
479 
480 /* Find entry for given id in the tree */
481 static long find_tree_dqentry(struct quota_handle *h,
482 				     struct dquot *dquot,
483 				     unsigned int blk, int depth)
484 {
485 	dqbuf_t buf = getdqbuf();
486 	long ret = 0;
487 	__le32 *ref = (__le32 *) buf;
488 
489 	if (!buf)
490 		return -ENOMEM;
491 
492 	read_blk(h, blk, buf);
493 	ret = 0;
494 	blk = le32_to_cpu(ref[get_index(dquot->dq_id, depth)]);
495 	if (!blk)	/* No reference? */
496 		goto out_buf;
497 	if (depth < QT_TREEDEPTH - 1)
498 		ret = find_tree_dqentry(h, dquot, blk, depth + 1);
499 	else
500 		ret = find_block_dqentry(h, dquot, blk);
501 out_buf:
502 	freedqbuf(buf);
503 	return ret;
504 }
505 
506 /* Find entry for given id in the tree - wrapper function */
507 static inline long find_dqentry(struct quota_handle *h,
508 				       struct dquot *dquot)
509 {
510 	return find_tree_dqentry(h, dquot, QT_TREEOFF, 0);
511 }
512 
513 /*
514  *  Read dquot from disk.
515  */
516 struct dquot *qtree_read_dquot(struct quota_handle *h, qid_t id)
517 {
518 	struct qtree_mem_dqinfo *info = &h->qh_info.u.v2_mdqi.dqi_qtree;
519 	long offset;
520 	unsigned int ret;
521 	char *ddquot;
522 	struct dquot *dquot = get_empty_dquot();
523 
524 	if (!dquot)
525 		return NULL;
526 	if (quota_get_mem(info->dqi_entry_size, &ddquot)) {
527 		quota_free_mem(&dquot);
528 		return NULL;
529 	}
530 
531 	dquot->dq_id = id;
532 	dquot->dq_h = h;
533 	dquot->dq_dqb.u.v2_mdqb.dqb_off = 0;
534 	memset(&dquot->dq_dqb, 0, sizeof(struct util_dqblk));
535 
536 	offset = find_dqentry(h, dquot);
537 	if (offset > 0) {
538 		dquot->dq_dqb.u.v2_mdqb.dqb_off = offset;
539 		ret = h->read(&h->qh_qf, offset, ddquot,
540 			info->dqi_entry_size);
541 		if (ret != info->dqi_entry_size) {
542 			if (ret > 0)
543 				errno = EIO;
544 			log_err("Cannot read quota structure for id %u: %s",
545 				dquot->dq_id, strerror(errno));
546 		}
547 		info->dqi_ops->disk2mem_dqblk(dquot, ddquot);
548 	}
549 	quota_free_mem(&ddquot);
550 	return dquot;
551 }
552 
553 /*
554  * Scan all dquots in file and call callback on each
555  */
556 #define set_bit(bmp, ind) ((bmp)[(ind) >> 3] |= (1 << ((ind) & 7)))
557 #define get_bit(bmp, ind) ((bmp)[(ind) >> 3] & (1 << ((ind) & 7)))
558 
559 static int report_block(struct dquot *dquot, unsigned int blk, char *bitmap,
560 			int (*process_dquot) (struct dquot *, void *),
561 			void *data)
562 {
563 	struct qtree_mem_dqinfo *info =
564 			&dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree;
565 	dqbuf_t buf = getdqbuf();
566 	struct qt_disk_dqdbheader *dh;
567 	char *ddata;
568 	int entries, i;
569 
570 	if (!buf)
571 		return 0;
572 
573 	set_bit(bitmap, blk);
574 	read_blk(dquot->dq_h, blk, buf);
575 	dh = (struct qt_disk_dqdbheader *)buf;
576 	ddata = buf + sizeof(struct qt_disk_dqdbheader);
577 	entries = le16_to_cpu(dh->dqdh_entries);
578 	for (i = 0; i < qtree_dqstr_in_blk(info);
579 			i++, ddata += info->dqi_entry_size)
580 		if (!qtree_entry_unused(info, ddata)) {
581 			dquot->dq_dqb.u.v2_mdqb.dqb_off =
582 				(blk << QT_BLKSIZE_BITS) +
583 				sizeof(struct qt_disk_dqdbheader) +
584 				i * info->dqi_entry_size;
585 			info->dqi_ops->disk2mem_dqblk(dquot, ddata);
586 			if (process_dquot(dquot, data) < 0)
587 				break;
588 		}
589 	freedqbuf(buf);
590 	return entries;
591 }
592 
593 static int check_reference(struct quota_handle *h, unsigned int blk)
594 {
595 	if (blk >= h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks) {
596 		log_err("Illegal reference (%u >= %u) in %s quota file. "
597 			"Quota file is probably corrupted.\n"
598 			"Please run fsck (8) to fix it.",
599 			blk,
600 			h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks,
601 			quota_type2name(h->qh_type));
602 		return -1;
603 	}
604 	return 0;
605 }
606 
607 /* Return 0 for successful run */
608 static int report_tree(struct dquot *dquot, unsigned int blk, int depth,
609 		       char *bitmap, int *entries,
610 		       int (*process_dquot) (struct dquot *, void *),
611 		       void *data)
612 {
613 	int i;
614 	dqbuf_t buf = getdqbuf();
615 	__le32 *ref = (__le32 *) buf;
616 
617 	if (!buf)
618 		return -1;
619 
620 	read_blk(dquot->dq_h, blk, buf);
621 	for (i = 0; i < QT_BLKSIZE >> 2; i++) {
622 		blk = le32_to_cpu(ref[i]);
623 		if (blk == 0)
624 			continue;
625 
626 		if (check_reference(dquot->dq_h, blk))
627 			break;
628 
629 		if (depth == QT_TREEDEPTH - 1) {
630 			if (!get_bit(bitmap, blk))
631 				*entries += report_block(dquot, blk, bitmap,
632 							process_dquot, data);
633 		} else {
634 			if (report_tree(dquot, blk, depth + 1, bitmap, entries,
635 						process_dquot, data))
636 				break;
637 		}
638 	}
639 	freedqbuf(buf);
640 	return (i < QT_BLKSIZE >> 2) ? -1 : 0;
641 }
642 
643 static unsigned int find_set_bits(char *bmp, int blocks)
644 {
645 	unsigned int	used = 0;
646 	int		i;
647 
648 	for (i = 0; i < blocks; i++)
649 		if (get_bit(bmp, i))
650 			used++;
651 	return used;
652 }
653 
654 int qtree_scan_dquots(struct quota_handle *h,
655 		      int (*process_dquot) (struct dquot *, void *),
656 		      void *data)
657 {
658 	struct v2_mem_dqinfo *v2info = &h->qh_info.u.v2_mdqi;
659 	struct qtree_mem_dqinfo *info = &v2info->dqi_qtree;
660 	struct dquot *dquot = get_empty_dquot();
661 	char *bitmap = NULL;
662 	int ret = -1;
663 	int entries = 0;
664 
665 	if (!dquot)
666 		return -1;
667 
668 	dquot->dq_h = h;
669 	if (quota_get_memzero((info->dqi_blocks + 7) >> 3, &bitmap))
670 		goto out;
671 	if (report_tree(dquot, QT_TREEOFF, 0, bitmap, &entries, process_dquot,
672 				data))
673 		goto out;
674 
675 	v2info->dqi_used_entries = entries;
676 	v2info->dqi_data_blocks = find_set_bits(bitmap, info->dqi_blocks);
677 	ret = 0;
678 
679 out:
680 	if (bitmap)
681 		quota_free_mem(&bitmap);
682 	if (dquot)
683 		quota_free_mem(&dquot);
684 
685 	return ret;
686 }
687