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
getdqbuf(void)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? */
qtree_entry_unused(struct qtree_mem_dqinfo * info,char * disk)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
qtree_dqstr_in_blk(struct qtree_mem_dqinfo * info)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
get_index(qid_t id,int depth)51 static int get_index(qid_t id, int depth)
52 {
53 return (id >> ((QT_TREEDEPTH - depth - 1) * 8)) & 0xff;
54 }
55
mark_quotafile_info_dirty(struct quota_handle * h)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 */
read_blk(struct quota_handle * h,unsigned int blk,dqbuf_t buf)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 */
write_blk(struct quota_handle * h,unsigned int blk,dqbuf_t buf)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) */
get_free_dqblk(struct quota_handle * h)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 */
put_free_dqblk(struct quota_handle * h,dqbuf_t buf,unsigned int blk)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 */
remove_free_dqentry(struct quota_handle * h,dqbuf_t buf,unsigned int blk)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 */
insert_free_dqentry(struct quota_handle * h,dqbuf_t buf,unsigned int blk)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 */
find_free_dqentry(struct quota_handle * h,struct dquot * dquot,int * err)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 */
do_insert_tree(struct quota_handle * h,struct dquot * dquot,unsigned int * treeblk,int depth)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 */
dq_insert_tree(struct quota_handle * h,struct dquot * dquot)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 */
qtree_write_dquot(struct dquot * dquot)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 */
free_dqentry(struct quota_handle * h,struct dquot * dquot,unsigned int blk)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 */
remove_tree(struct quota_handle * h,struct dquot * dquot,unsigned int * blk,int depth)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 */
qtree_delete_dquot(struct dquot * dquot)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 */
find_block_dqentry(struct quota_handle * h,struct dquot * dquot,unsigned int blk)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 */
find_tree_dqentry(struct quota_handle * h,struct dquot * dquot,unsigned int blk,int depth)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 */
find_dqentry(struct quota_handle * h,struct dquot * dquot)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 */
qtree_read_dquot(struct quota_handle * h,qid_t id)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 /*
544 * Scan all dquots in file and call callback on each
545 */
546 #define set_bit(bmp, ind) ((bmp)[(ind) >> 3] |= (1 << ((ind) & 7)))
547 #define get_bit(bmp, ind) ((bmp)[(ind) >> 3] & (1 << ((ind) & 7)))
548
report_block(struct dquot * dquot,unsigned int blk,char * bitmap,int (* process_dquot)(struct dquot *,void *),void * data)549 static int report_block(struct dquot *dquot, unsigned int blk, char *bitmap,
550 int (*process_dquot) (struct dquot *, void *),
551 void *data)
552 {
553 struct qtree_mem_dqinfo *info =
554 &dquot->dq_h->qh_info.u.v2_mdqi.dqi_qtree;
555 dqbuf_t buf = getdqbuf();
556 struct qt_disk_dqdbheader *dh;
557 char *ddata;
558 int entries, i;
559
560 if (!buf)
561 return 0;
562
563 set_bit(bitmap, blk);
564 read_blk(dquot->dq_h, blk, buf);
565 dh = (struct qt_disk_dqdbheader *)buf;
566 ddata = buf + sizeof(struct qt_disk_dqdbheader);
567 entries = ext2fs_le16_to_cpu(dh->dqdh_entries);
568 for (i = 0; i < qtree_dqstr_in_blk(info);
569 i++, ddata += info->dqi_entry_size)
570 if (!qtree_entry_unused(info, ddata)) {
571 dquot->dq_dqb.u.v2_mdqb.dqb_off =
572 (blk << QT_BLKSIZE_BITS) +
573 sizeof(struct qt_disk_dqdbheader) +
574 i * info->dqi_entry_size;
575 info->dqi_ops->disk2mem_dqblk(dquot, ddata);
576 if (process_dquot(dquot, data) < 0)
577 break;
578 }
579 freedqbuf(buf);
580 return entries;
581 }
582
check_reference(struct quota_handle * h,unsigned int blk)583 static void check_reference(struct quota_handle *h, unsigned int blk)
584 {
585 if (blk >= h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks)
586 log_err("Illegal reference (%u >= %u) in %s quota file. "
587 "Quota file is probably corrupted.\n"
588 "Please run e2fsck (8) to fix it.",
589 blk,
590 h->qh_info.u.v2_mdqi.dqi_qtree.dqi_blocks,
591 quota_type2name(h->qh_type));
592 }
593
report_tree(struct dquot * dquot,unsigned int blk,int depth,char * bitmap,int (* process_dquot)(struct dquot *,void *),void * data)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, 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 check_reference(dquot->dq_h, blk);
611 if (blk && !get_bit(bitmap, blk))
612 entries += report_block(dquot, blk, bitmap,
613 process_dquot, data);
614 }
615 } else {
616 for (i = 0; i < QT_BLKSIZE >> 2; i++) {
617 blk = ext2fs_le32_to_cpu(ref[i]);
618 if (blk) {
619 check_reference(dquot->dq_h, blk);
620 entries += report_tree(dquot, blk, depth + 1,
621 bitmap, process_dquot,
622 data);
623 }
624 }
625 }
626 freedqbuf(buf);
627 return entries;
628 }
629
find_set_bits(char * bmp,int blocks)630 static unsigned int find_set_bits(char *bmp, int blocks)
631 {
632 unsigned int used = 0;
633 int i;
634
635 for (i = 0; i < blocks; i++)
636 if (get_bit(bmp, i))
637 used++;
638 return used;
639 }
640
qtree_scan_dquots(struct quota_handle * h,int (* process_dquot)(struct dquot *,void *),void * data)641 int qtree_scan_dquots(struct quota_handle *h,
642 int (*process_dquot) (struct dquot *, void *),
643 void *data)
644 {
645 char *bitmap;
646 struct v2_mem_dqinfo *v2info = &h->qh_info.u.v2_mdqi;
647 struct qtree_mem_dqinfo *info = &v2info->dqi_qtree;
648 struct dquot *dquot = get_empty_dquot();
649
650 if (!dquot)
651 return -1;
652
653 dquot->dq_h = h;
654 if (ext2fs_get_memzero((info->dqi_blocks + 7) >> 3, &bitmap)) {
655 ext2fs_free_mem(&dquot);
656 return -1;
657 }
658 v2info->dqi_used_entries = report_tree(dquot, QT_TREEOFF, 0, bitmap,
659 process_dquot, data);
660 v2info->dqi_data_blocks = find_set_bits(bitmap, info->dqi_blocks);
661 ext2fs_free_mem(&bitmap);
662 ext2fs_free_mem(&dquot);
663 return 0;
664 }
665