?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
btrfs-progs: check: Output verbose error when fsck found a bug in any tree
[btrfs-progs-unstable/devel.git] / qgroup.c
blobfffdbb12ea3d65d07c331daa2b58e46ffe5cfec0
1 /*
2 * Copyright (C) 2012 STRATO. All rights reserved.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
17 */
18
19 #include "qgroup.h"
20 #include <sys/ioctl.h>
21 #include "ctree.h"
22 #include "ioctl.h"
23 #include "utils.h"
24 #include <errno.h>
25
26 #define BTRFS_QGROUP_NFILTERS_INCREASE (2 * BTRFS_QGROUP_FILTER_MAX)
27 #define BTRFS_QGROUP_NCOMPS_INCREASE (2 * BTRFS_QGROUP_COMP_MAX)
28
29 struct qgroup_lookup {
30 struct rb_root root;
31 };
32
33 struct btrfs_qgroup {
34 struct rb_node rb_node;
35 struct rb_node sort_node;
36 /*
37 *all_parent_node is used to
38 *filter a qgroup's all parent
39 */
40 struct rb_node all_parent_node;
41 u64 qgroupid;
42
43 /*
44 * info_item
45 */
46 u64 generation;
47 u64 rfer; /*referenced*/
48 u64 rfer_cmpr; /*referenced compressed*/
49 u64 excl; /*exclusive*/
50 u64 excl_cmpr; /*exclusive compressed*/
51
52 /*
53 *limit_item
54 */
55 u64 flags; /*which limits are set*/
56 u64 max_rfer;
57 u64 max_excl;
58 u64 rsv_rfer;
59 u64 rsv_excl;
60
61 /*qgroups this group is member of*/
62 struct list_head qgroups;
63 /*qgroups that are members of this group*/
64 struct list_head members;
65 };
66
67 /*
68 * glue structure to represent the relations
69 * between qgroups
70 */
71 struct btrfs_qgroup_list {
72 struct list_head next_qgroup;
73 struct list_head next_member;
74 struct btrfs_qgroup *qgroup;
75 struct btrfs_qgroup *member;
76 };
77
78 /*
79 * qgroupid,rfer,excl default to set
80 */
81 static struct {
82 char *name;
83 char *column_name;
84 int need_print;
85 unsigned unit_mode;
86 int max_len;
87 } btrfs_qgroup_columns[] = {
88 {
89 .name = "qgroupid",
90 .column_name = "Qgroupid",
91 .need_print = 1,
92 .unit_mode = 0,
93 .max_len = 8,
94 },
95 {
96 .name = "rfer",
97 .column_name = "Rfer",
98 .need_print = 1,
99 .unit_mode = UNITS_DEFAULT,
100 .max_len = 12,
101 },
102 {
103 .name = "excl",
104 .column_name = "Excl",
105 .need_print = 1,
106 .unit_mode = UNITS_DEFAULT,
107 .max_len = 12,
108 },
109 { .name = "max_rfer",
110 .column_name = "Max_rfer",
111 .need_print = 0,
112 .unit_mode = UNITS_DEFAULT,
113 .max_len = 12,
114 },
115 {
116 .name = "max_excl",
117 .column_name = "Max_excl",
118 .need_print = 0,
119 .unit_mode = UNITS_DEFAULT,
120 .max_len = 12,
121 },
122 {
123 .name = "parent",
124 .column_name = "Parent",
125 .need_print = 0,
126 .unit_mode = 0,
127 .max_len = 7,
128 },
129 {
130 .name = "child",
131 .column_name = "Child",
132 .need_print = 0,
133 .unit_mode = 0,
134 .max_len = 5,
135 },
136 {
137 .name = NULL,
138 .column_name = NULL,
139 .need_print = 0,
140 .unit_mode = 0,
141 },
142 };
143
144 static btrfs_qgroup_filter_func all_filter_funcs[];
145 static btrfs_qgroup_comp_func all_comp_funcs[];
146
147 void btrfs_qgroup_setup_print_column(enum btrfs_qgroup_column_enum column)
148 {
149 int i;
150
151 ASSERT(0 <= column && column <= BTRFS_QGROUP_ALL);
152
153 if (column < BTRFS_QGROUP_ALL) {
154 btrfs_qgroup_columns[column].need_print = 1;
155 return;
156 }
157 for (i = 0; i < BTRFS_QGROUP_ALL; i++)
158 btrfs_qgroup_columns[i].need_print = 1;
159 }
160
161 void btrfs_qgroup_setup_units(unsigned unit_mode)
162 {
163 btrfs_qgroup_columns[BTRFS_QGROUP_RFER].unit_mode = unit_mode;
164 btrfs_qgroup_columns[BTRFS_QGROUP_EXCL].unit_mode = unit_mode;
165 btrfs_qgroup_columns[BTRFS_QGROUP_MAX_RFER].unit_mode = unit_mode;
166 btrfs_qgroup_columns[BTRFS_QGROUP_MAX_EXCL].unit_mode = unit_mode;
167 }
168
169 static int print_parent_column(struct btrfs_qgroup *qgroup)
170 {
171 struct btrfs_qgroup_list *list = NULL;
172 int len = 0;
173
174 list_for_each_entry(list, &qgroup->qgroups, next_qgroup) {
175 len += printf("%llu/%llu",
176 btrfs_qgroup_level(list->qgroup->qgroupid),
177 btrfs_qgroup_subvid(list->qgroup->qgroupid));
178 if (!list_is_last(&list->next_qgroup, &qgroup->qgroups))
179 len += printf(",");
180 }
181 if (list_empty(&qgroup->qgroups))
182 len += printf("---");
183
184 return len;
185 }
186
187 static int print_child_column(struct btrfs_qgroup *qgroup)
188 {
189 struct btrfs_qgroup_list *list = NULL;
190 int len = 0;
191
192 list_for_each_entry(list, &qgroup->members, next_member) {
193 len += printf("%llu/%llu",
194 btrfs_qgroup_level(list->member->qgroupid),
195 btrfs_qgroup_subvid(list->member->qgroupid));
196 if (!list_is_last(&list->next_member, &qgroup->members))
197 len += printf(",");
198 }
199 if (list_empty(&qgroup->members))
200 len += printf("---");
201
202 return len;
203 }
204
205 static void print_qgroup_column_add_blank(enum btrfs_qgroup_column_enum column,
206 int len)
207 {
208 len = btrfs_qgroup_columns[column].max_len - len;
209 while (len--)
210 printf(" ");
211 }
212
213 static void print_qgroup_column(struct btrfs_qgroup *qgroup,
214 enum btrfs_qgroup_column_enum column)
215 {
216 int len;
217 int unit_mode = btrfs_qgroup_columns[column].unit_mode;
218 int max_len = btrfs_qgroup_columns[column].max_len;
219
220 ASSERT(0 <= column && column < BTRFS_QGROUP_ALL);
221
222 switch (column) {
223
224 case BTRFS_QGROUP_QGROUPID:
225 len = printf("%llu/%llu",
226 btrfs_qgroup_level(qgroup->qgroupid),
227 btrfs_qgroup_subvid(qgroup->qgroupid));
228 print_qgroup_column_add_blank(BTRFS_QGROUP_QGROUPID, len);
229 break;
230 case BTRFS_QGROUP_RFER:
231 len = printf("%*s", max_len, pretty_size_mode(qgroup->rfer, unit_mode));
232 break;
233 case BTRFS_QGROUP_EXCL:
234 len = printf("%*s", max_len, pretty_size_mode(qgroup->excl, unit_mode));
235 break;
236 case BTRFS_QGROUP_PARENT:
237 len = print_parent_column(qgroup);
238 print_qgroup_column_add_blank(BTRFS_QGROUP_PARENT, len);
239 break;
240 case BTRFS_QGROUP_MAX_RFER:
241 if (qgroup->flags & BTRFS_QGROUP_LIMIT_MAX_RFER)
242 len = printf("%*s", max_len, pretty_size_mode(qgroup->max_rfer, unit_mode));
243 else
244 len = printf("%*s", max_len, "none");
245 break;
246 case BTRFS_QGROUP_MAX_EXCL:
247 if (qgroup->flags & BTRFS_QGROUP_LIMIT_MAX_EXCL)
248 len = printf("%*s", max_len, pretty_size_mode(qgroup->max_excl, unit_mode));
249 else
250 len = printf("%*s", max_len, "none");
251 break;
252 case BTRFS_QGROUP_CHILD:
253 len = print_child_column(qgroup);
254 print_qgroup_column_add_blank(BTRFS_QGROUP_CHILD, len);
255 break;
256 default:
257 break;
258 }
259 }
260
261 static void print_single_qgroup_table(struct btrfs_qgroup *qgroup)
262 {
263 int i;
264
265 for (i = 0; i < BTRFS_QGROUP_ALL; i++) {
266 if (!btrfs_qgroup_columns[i].need_print)
267 continue;
268 print_qgroup_column(qgroup, i);
269
270 if (i != BTRFS_QGROUP_CHILD)
271 printf(" ");
272 }
273 printf("\n");
274 }
275
276 static void print_table_head(void)
277 {
278 int i;
279 int len;
280 int max_len;
281
282 for (i = 0; i < BTRFS_QGROUP_ALL; i++) {
283 max_len = btrfs_qgroup_columns[i].max_len;
284 if (!btrfs_qgroup_columns[i].need_print)
285 continue;
286 if ((i == BTRFS_QGROUP_QGROUPID) | (i == BTRFS_QGROUP_PARENT) |
287 (i == BTRFS_QGROUP_CHILD))
288 printf("%-*s", max_len, btrfs_qgroup_columns[i].name);
289 else
290 printf("%*s", max_len, btrfs_qgroup_columns[i].name);
291 printf(" ");
292 }
293 printf("\n");
294 for (i = 0; i < BTRFS_QGROUP_ALL; i++) {
295 max_len = btrfs_qgroup_columns[i].max_len;
296 if (!btrfs_qgroup_columns[i].need_print)
297 continue;
298 if ((i == BTRFS_QGROUP_QGROUPID) | (i == BTRFS_QGROUP_PARENT) |
299 (i == BTRFS_QGROUP_CHILD)) {
300 len = strlen(btrfs_qgroup_columns[i].name);
301 while (len--)
302 printf("-");
303 len = max_len - strlen(btrfs_qgroup_columns[i].name);
304 while (len--)
305 printf(" ");
306 } else {
307 len = max_len - strlen(btrfs_qgroup_columns[i].name);
308 while (len--)
309 printf(" ");
310 len = strlen(btrfs_qgroup_columns[i].name);
311 while (len--)
312 printf("-");
313 }
314 printf(" ");
315 }
316 printf("\n");
317 }
318
319 static void qgroup_lookup_init(struct qgroup_lookup *tree)
320 {
321 tree->root.rb_node = NULL;
322 }
323
324 static int comp_entry_with_qgroupid(struct btrfs_qgroup *entry1,
325 struct btrfs_qgroup *entry2,
326 int is_descending)
327 {
328
329 int ret;
330
331 if (entry1->qgroupid > entry2->qgroupid)
332 ret = 1;
333 else if (entry1->qgroupid < entry2->qgroupid)
334 ret = -1;
335 else
336 ret = 0;
337
338 return is_descending ? -ret : ret;
339 }
340
341 static int comp_entry_with_rfer(struct btrfs_qgroup *entry1,
342 struct btrfs_qgroup *entry2,
343 int is_descending)
344 {
345 int ret;
346
347 if (entry1->rfer > entry2->rfer)
348 ret = 1;
349 else if (entry1->rfer < entry2->rfer)
350 ret = -1;
351 else
352 ret = 0;
353
354 return is_descending ? -ret : ret;
355 }
356
357 static int comp_entry_with_excl(struct btrfs_qgroup *entry1,
358 struct btrfs_qgroup *entry2,
359 int is_descending)
360 {
361 int ret;
362
363 if (entry1->excl > entry2->excl)
364 ret = 1;
365 else if (entry1->excl < entry2->excl)
366 ret = -1;
367 else
368 ret = 0;
369
370 return is_descending ? -ret : ret;
371 }
372
373 static int comp_entry_with_max_rfer(struct btrfs_qgroup *entry1,
374 struct btrfs_qgroup *entry2,
375 int is_descending)
376 {
377 int ret;
378
379 if (entry1->max_rfer > entry2->max_rfer)
380 ret = 1;
381 else if (entry1->max_rfer < entry2->max_rfer)
382 ret = -1;
383 else
384 ret = 0;
385
386 return is_descending ? -ret : ret;
387 }
388
389 static int comp_entry_with_max_excl(struct btrfs_qgroup *entry1,
390 struct btrfs_qgroup *entry2,
391 int is_descending)
392 {
393 int ret;
394
395 if (entry1->max_excl > entry2->max_excl)
396 ret = 1;
397 else if (entry1->max_excl < entry2->max_excl)
398 ret = -1;
399 else
400 ret = 0;
401
402 return is_descending ? -ret : ret;
403 }
404
405 static btrfs_qgroup_comp_func all_comp_funcs[] = {
406 [BTRFS_QGROUP_COMP_QGROUPID] = comp_entry_with_qgroupid,
407 [BTRFS_QGROUP_COMP_RFER] = comp_entry_with_rfer,
408 [BTRFS_QGROUP_COMP_EXCL] = comp_entry_with_excl,
409 [BTRFS_QGROUP_COMP_MAX_RFER] = comp_entry_with_max_rfer,
410 [BTRFS_QGROUP_COMP_MAX_EXCL] = comp_entry_with_max_excl
411 };
412
413 static char *all_sort_items[] = {
414 [BTRFS_QGROUP_COMP_QGROUPID] = "qgroupid",
415 [BTRFS_QGROUP_COMP_RFER] = "rfer",
416 [BTRFS_QGROUP_COMP_EXCL] = "excl",
417 [BTRFS_QGROUP_COMP_MAX_RFER] = "max_rfer",
418 [BTRFS_QGROUP_COMP_MAX_EXCL] = "max_excl",
419 [BTRFS_QGROUP_COMP_MAX] = NULL,
420 };
421
422 static int btrfs_qgroup_get_sort_item(char *sort_name)
423 {
424 int i;
425
426 for (i = 0; i < BTRFS_QGROUP_COMP_MAX; i++) {
427 if (strcmp(sort_name, all_sort_items[i]) == 0)
428 return i;
429 }
430 return -1;
431 }
432
433 struct btrfs_qgroup_comparer_set *btrfs_qgroup_alloc_comparer_set(void)
434 {
435 struct btrfs_qgroup_comparer_set *set;
436 int size;
437 size = sizeof(struct btrfs_qgroup_comparer_set) +
438 BTRFS_QGROUP_NCOMPS_INCREASE *
439 sizeof(struct btrfs_qgroup_comparer);
440 set = calloc(1, size);
441 if (!set) {
442 error("memory allocation failed");
443 exit(1);
444 }
445
446 set->total = BTRFS_QGROUP_NCOMPS_INCREASE;
447
448 return set;
449 }
450
451 int btrfs_qgroup_setup_comparer(struct btrfs_qgroup_comparer_set **comp_set,
452 enum btrfs_qgroup_comp_enum comparer,
453 int is_descending)
454 {
455 struct btrfs_qgroup_comparer_set *set = *comp_set;
456 int size;
457
458 ASSERT(set != NULL);
459 ASSERT(comparer < BTRFS_QGROUP_COMP_MAX);
460 ASSERT(set->ncomps <= set->total);
461
462 if (set->ncomps == set->total) {
463 void *tmp;
464
465 size = set->total + BTRFS_QGROUP_NCOMPS_INCREASE;
466 size = sizeof(*set) +
467 size * sizeof(struct btrfs_qgroup_comparer);
468 tmp = set;
469 set = realloc(set, size);
470 if (!set) {
471 error("memory allocation failed");
472 free(tmp);
473 exit(1);
474 }
475
476 memset(&set->comps[set->total], 0,
477 BTRFS_QGROUP_NCOMPS_INCREASE *
478 sizeof(struct btrfs_qgroup_comparer));
479 set->total += BTRFS_QGROUP_NCOMPS_INCREASE;
480 *comp_set = set;
481 }
482
483 ASSERT(set->comps[set->ncomps].comp_func == NULL);
484
485 set->comps[set->ncomps].comp_func = all_comp_funcs[comparer];
486 set->comps[set->ncomps].is_descending = is_descending;
487 set->ncomps++;
488 return 0;
489 }
490
491 static int sort_comp(struct btrfs_qgroup *entry1, struct btrfs_qgroup *entry2,
492 struct btrfs_qgroup_comparer_set *set)
493 {
494 int qgroupid_compared = 0;
495 int i, ret = 0;
496
497 if (!set || !set->ncomps)
498 goto comp_qgroupid;
499
500 for (i = 0; i < set->ncomps; i++) {
501 if (!set->comps[i].comp_func)
502 break;
503
504 ret = set->comps[i].comp_func(entry1, entry2,
505 set->comps[i].is_descending);
506 if (ret)
507 return ret;
508
509 if (set->comps[i].comp_func == comp_entry_with_qgroupid)
510 qgroupid_compared = 1;
511 }
512
513 if (!qgroupid_compared) {
514 comp_qgroupid:
515 ret = comp_entry_with_qgroupid(entry1, entry2, 0);
516 }
517
518 return ret;
519 }
520
521 /*
522 * insert a new root into the tree. returns the existing root entry
523 * if one is already there. qgroupid is used
524 * as the key
525 */
526 static int qgroup_tree_insert(struct qgroup_lookup *root_tree,
527 struct btrfs_qgroup *ins)
528 {
529
530 struct rb_node **p = &root_tree->root.rb_node;
531 struct rb_node *parent = NULL;
532 struct btrfs_qgroup *curr;
533 int ret;
534
535 while (*p) {
536 parent = *p;
537 curr = rb_entry(parent, struct btrfs_qgroup, rb_node);
538
539 ret = comp_entry_with_qgroupid(ins, curr, 0);
540 if (ret < 0)
541 p = &(*p)->rb_left;
542 else if (ret > 0)
543 p = &(*p)->rb_right;
544 else
545 return -EEXIST;
546 }
547 rb_link_node(&ins->rb_node, parent, p);
548 rb_insert_color(&ins->rb_node, &root_tree->root);
549 return 0;
550 }
551
552 /*
553 *find a given qgroupid in the tree. We return the smallest one,
554 *rb_next can be used to move forward looking for more if required
555 */
556 static struct btrfs_qgroup *qgroup_tree_search(struct qgroup_lookup *root_tree,
557 u64 qgroupid)
558 {
559 struct rb_node *n = root_tree->root.rb_node;
560 struct btrfs_qgroup *entry;
561 struct btrfs_qgroup tmp;
562 int ret;
563
564 tmp.qgroupid = qgroupid;
565
566 while (n) {
567 entry = rb_entry(n, struct btrfs_qgroup, rb_node);
568
569 ret = comp_entry_with_qgroupid(&tmp, entry, 0);
570 if (ret < 0)
571 n = n->rb_left;
572 else if (ret > 0)
573 n = n->rb_right;
574 else
575 return entry;
576
577 }
578 return NULL;
579 }
580
581 static int update_qgroup(struct qgroup_lookup *qgroup_lookup, u64 qgroupid,
582 u64 generation, u64 rfer, u64 rfer_cmpr, u64 excl,
583 u64 excl_cmpr, u64 flags, u64 max_rfer, u64 max_excl,
584 u64 rsv_rfer, u64 rsv_excl, struct btrfs_qgroup *pa,
585 struct btrfs_qgroup *child)
586 {
587 struct btrfs_qgroup *bq;
588 struct btrfs_qgroup_list *list;
589
590 bq = qgroup_tree_search(qgroup_lookup, qgroupid);
591 if (!bq || bq->qgroupid != qgroupid)
592 return -ENOENT;
593
594 if (generation)
595 bq->generation = generation;
596 if (rfer)
597 bq->rfer = rfer;
598 if (rfer_cmpr)
599 bq->rfer_cmpr = rfer_cmpr;
600 if (excl)
601 bq->excl = excl;
602 if (excl_cmpr)
603 bq->excl_cmpr = excl_cmpr;
604 if (flags)
605 bq->flags = flags;
606 if (max_rfer)
607 bq->max_rfer = max_rfer;
608 if (max_excl)
609 bq->max_excl = max_excl;
610 if (rsv_rfer)
611 bq->rsv_rfer = rsv_rfer;
612 if (pa && child) {
613 list = malloc(sizeof(*list));
614 if (!list) {
615 error("memory allocation failed");
616 exit(1);
617 }
618 list->qgroup = pa;
619 list->member = child;
620 list_add_tail(&list->next_qgroup, &child->qgroups);
621 list_add_tail(&list->next_member, &pa->members);
622 }
623 return 0;
624 }
625
626 static int add_qgroup(struct qgroup_lookup *qgroup_lookup, u64 qgroupid,
627 u64 generation, u64 rfer, u64 rfer_cmpr, u64 excl,
628 u64 excl_cmpr, u64 flags, u64 max_rfer, u64 max_excl,
629 u64 rsv_rfer, u64 rsv_excl, struct btrfs_qgroup *parent,
630 struct btrfs_qgroup *child)
631 {
632 struct btrfs_qgroup *bq;
633 struct btrfs_qgroup_list *list;
634 int ret;
635
636 ret = update_qgroup(qgroup_lookup, qgroupid, generation, rfer,
637 rfer_cmpr, excl, excl_cmpr, flags, max_rfer,
638 max_excl, rsv_rfer, rsv_excl, parent, child);
639 if (!ret)
640 return 0;
641
642 bq = calloc(1, sizeof(*bq));
643 if (!bq) {
644 error("memory allocation failed");
645 exit(1);
646 }
647 if (qgroupid) {
648 bq->qgroupid = qgroupid;
649 INIT_LIST_HEAD(&bq->qgroups);
650 INIT_LIST_HEAD(&bq->members);
651 }
652 if (generation)
653 bq->generation = generation;
654 if (rfer)
655 bq->rfer = rfer;
656 if (rfer_cmpr)
657 bq->rfer_cmpr = rfer_cmpr;
658 if (excl)
659 bq->excl = excl;
660 if (excl_cmpr)
661 bq->excl_cmpr = excl_cmpr;
662 if (flags)
663 bq->flags = flags;
664 if (max_rfer)
665 bq->max_rfer = max_rfer;
666 if (max_excl)
667 bq->max_excl = max_excl;
668 if (rsv_rfer)
669 bq->rsv_rfer = rsv_rfer;
670 if (parent && child) {
671 list = malloc(sizeof(*list));
672 if (!list) {
673 error("memory allocation failed");
674 exit(1);
675 }
676 list->qgroup = parent;
677 list->member = child;
678 list_add_tail(&list->next_qgroup, &child->qgroups);
679 list_add_tail(&list->next_member, &parent->members);
680 }
681 ret = qgroup_tree_insert(qgroup_lookup, bq);
682 if (ret) {
683 error("failed to insert %llu into tree: %s",
684 (unsigned long long)bq->qgroupid, strerror(-ret));
685 exit(1);
686 }
687 return ret;
688 }
689
690 static void __free_btrfs_qgroup(struct btrfs_qgroup *bq)
691 {
692 struct btrfs_qgroup_list *list;
693 while (!list_empty(&bq->qgroups)) {
694 list = list_entry((&bq->qgroups)->next,
695 struct btrfs_qgroup_list,
696 next_qgroup);
697 list_del(&list->next_qgroup);
698 list_del(&list->next_member);
699 free(list);
700 }
701 while (!list_empty(&bq->members)) {
702 list = list_entry((&bq->members)->next,
703 struct btrfs_qgroup_list,
704 next_member);
705 list_del(&list->next_qgroup);
706 list_del(&list->next_member);
707 free(list);
708 }
709 free(bq);
710 }
711
712 static void __free_all_qgroups(struct qgroup_lookup *root_tree)
713 {
714 struct btrfs_qgroup *entry;
715 struct rb_node *n;
716
717 n = rb_first(&root_tree->root);
718 while (n) {
719 entry = rb_entry(n, struct btrfs_qgroup, rb_node);
720 rb_erase(n, &root_tree->root);
721 __free_btrfs_qgroup(entry);
722
723 n = rb_first(&root_tree->root);
724 }
725 }
726
727 static int filter_all_parent_insert(struct qgroup_lookup *sort_tree,
728 struct btrfs_qgroup *bq)
729 {
730 struct rb_node **p = &sort_tree->root.rb_node;
731 struct rb_node *parent = NULL;
732 struct btrfs_qgroup *curr;
733 int ret;
734
735 while (*p) {
736 parent = *p;
737 curr = rb_entry(parent, struct btrfs_qgroup, all_parent_node);
738
739 ret = comp_entry_with_qgroupid(bq, curr, 0);
740 if (ret < 0)
741 p = &(*p)->rb_left;
742 else if (ret > 0)
743 p = &(*p)->rb_right;
744 else
745 return -EEXIST;
746 }
747 rb_link_node(&bq->all_parent_node, parent, p);
748 rb_insert_color(&bq->all_parent_node, &sort_tree->root);
749 return 0;
750 }
751
752 static int filter_by_parent(struct btrfs_qgroup *bq, u64 data)
753 {
754 struct btrfs_qgroup *qgroup =
755 (struct btrfs_qgroup *)(unsigned long)data;
756
757 if (data == 0)
758 return 0;
759 if (qgroup->qgroupid == bq->qgroupid)
760 return 1;
761 return 0;
762 }
763
764 static int filter_by_all_parent(struct btrfs_qgroup *bq, u64 data)
765 {
766 struct qgroup_lookup lookup;
767 struct qgroup_lookup *ql = &lookup;
768 struct btrfs_qgroup_list *list;
769 struct rb_node *n;
770 struct btrfs_qgroup *qgroup =
771 (struct btrfs_qgroup *)(unsigned long)data;
772
773 if (data == 0)
774 return 0;
775 if (bq->qgroupid == qgroup->qgroupid)
776 return 1;
777
778 qgroup_lookup_init(ql);
779 filter_all_parent_insert(ql, qgroup);
780 n = rb_first(&ql->root);
781 while (n) {
782 qgroup = rb_entry(n, struct btrfs_qgroup, all_parent_node);
783 if (!list_empty(&qgroup->qgroups)) {
784 list_for_each_entry(list, &qgroup->qgroups,
785 next_qgroup) {
786 if ((list->qgroup)->qgroupid == bq->qgroupid)
787 return 1;
788 filter_all_parent_insert(ql, list->qgroup);
789 }
790 }
791 rb_erase(n, &ql->root);
792 n = rb_first(&ql->root);
793 }
794 return 0;
795 }
796
797 static btrfs_qgroup_filter_func all_filter_funcs[] = {
798 [BTRFS_QGROUP_FILTER_PARENT] = filter_by_parent,
799 [BTRFS_QGROUP_FILTER_ALL_PARENT] = filter_by_all_parent,
800 };
801
802 struct btrfs_qgroup_filter_set *btrfs_qgroup_alloc_filter_set(void)
803 {
804 struct btrfs_qgroup_filter_set *set;
805 int size;
806
807 size = sizeof(struct btrfs_qgroup_filter_set) +
808 BTRFS_QGROUP_NFILTERS_INCREASE *
809 sizeof(struct btrfs_qgroup_filter);
810 set = calloc(1, size);
811 if (!set) {
812 error("memory allocation failed");
813 exit(1);
814 }
815 set->total = BTRFS_QGROUP_NFILTERS_INCREASE;
816
817 return set;
818 }
819
820 int btrfs_qgroup_setup_filter(struct btrfs_qgroup_filter_set **filter_set,
821 enum btrfs_qgroup_filter_enum filter, u64 data)
822 {
823 struct btrfs_qgroup_filter_set *set = *filter_set;
824 int size;
825
826 ASSERT(set != NULL);
827 ASSERT(filter < BTRFS_QGROUP_FILTER_MAX);
828 ASSERT(set->nfilters <= set->total);
829
830 if (set->nfilters == set->total) {
831 void *tmp;
832
833 size = set->total + BTRFS_QGROUP_NFILTERS_INCREASE;
834 size = sizeof(*set) + size * sizeof(struct btrfs_qgroup_filter);
835
836 tmp = set;
837 set = realloc(set, size);
838 if (!set) {
839 error("memory allocation failed");
840 free(tmp);
841 exit(1);
842 }
843 memset(&set->filters[set->total], 0,
844 BTRFS_QGROUP_NFILTERS_INCREASE *
845 sizeof(struct btrfs_qgroup_filter));
846 set->total += BTRFS_QGROUP_NFILTERS_INCREASE;
847 *filter_set = set;
848 }
849
850 ASSERT(set->filters[set->nfilters].filter_func == NULL);
851 set->filters[set->nfilters].filter_func = all_filter_funcs[filter];
852 set->filters[set->nfilters].data = data;
853 set->nfilters++;
854 return 0;
855 }
856
857 static int filter_qgroup(struct btrfs_qgroup *bq,
858 struct btrfs_qgroup_filter_set *set)
859 {
860 int i, ret;
861
862 if (!set || !set->nfilters)
863 return 1;
864 for (i = 0; i < set->nfilters; i++) {
865 if (!set->filters[i].filter_func)
866 break;
867 ret = set->filters[i].filter_func(bq, set->filters[i].data);
868 if (!ret)
869 return 0;
870 }
871 return 1;
872 }
873
874 static void pre_process_filter_set(struct qgroup_lookup *lookup,
875 struct btrfs_qgroup_filter_set *set)
876 {
877 int i;
878 struct btrfs_qgroup *qgroup_for_filter = NULL;
879
880 for (i = 0; i < set->nfilters; i++) {
881
882 if (set->filters[i].filter_func == filter_by_all_parent
883 || set->filters[i].filter_func == filter_by_parent) {
884 qgroup_for_filter = qgroup_tree_search(lookup,
885 set->filters[i].data);
886 set->filters[i].data =
887 (u64)(unsigned long)qgroup_for_filter;
888 }
889 }
890 }
891
892 static int sort_tree_insert(struct qgroup_lookup *sort_tree,
893 struct btrfs_qgroup *bq,
894 struct btrfs_qgroup_comparer_set *comp_set)
895 {
896 struct rb_node **p = &sort_tree->root.rb_node;
897 struct rb_node *parent = NULL;
898 struct btrfs_qgroup *curr;
899 int ret;
900
901 while (*p) {
902 parent = *p;
903 curr = rb_entry(parent, struct btrfs_qgroup, sort_node);
904
905 ret = sort_comp(bq, curr, comp_set);
906 if (ret < 0)
907 p = &(*p)->rb_left;
908 else if (ret > 0)
909 p = &(*p)->rb_right;
910 else
911 return -EEXIST;
912 }
913 rb_link_node(&bq->sort_node, parent, p);
914 rb_insert_color(&bq->sort_node, &sort_tree->root);
915 return 0;
916 }
917
918 static void __update_columns_max_len(struct btrfs_qgroup *bq,
919 enum btrfs_qgroup_column_enum column)
920 {
921 struct btrfs_qgroup_list *list = NULL;
922 char tmp[100];
923 int len;
924 unsigned unit_mode = btrfs_qgroup_columns[column].unit_mode;
925
926 ASSERT(0 <= column && column < BTRFS_QGROUP_ALL);
927
928 switch (column) {
929
930 case BTRFS_QGROUP_QGROUPID:
931 sprintf(tmp, "%llu/%llu",
932 btrfs_qgroup_level(bq->qgroupid),
933 btrfs_qgroup_subvid(bq->qgroupid));
934 len = strlen(tmp);
935 if (btrfs_qgroup_columns[column].max_len < len)
936 btrfs_qgroup_columns[column].max_len = len;
937 break;
938 case BTRFS_QGROUP_RFER:
939 len = strlen(pretty_size_mode(bq->rfer, unit_mode));
940 if (btrfs_qgroup_columns[column].max_len < len)
941 btrfs_qgroup_columns[column].max_len = len;
942 break;
943 case BTRFS_QGROUP_EXCL:
944 len = strlen(pretty_size_mode(bq->excl, unit_mode));
945 if (btrfs_qgroup_columns[column].max_len < len)
946 btrfs_qgroup_columns[column].max_len = len;
947 break;
948 case BTRFS_QGROUP_MAX_RFER:
949 len = strlen(pretty_size_mode(bq->max_rfer, unit_mode));
950 if (btrfs_qgroup_columns[column].max_len < len)
951 btrfs_qgroup_columns[column].max_len = len;
952 break;
953 case BTRFS_QGROUP_MAX_EXCL:
954 len = strlen(pretty_size_mode(bq->max_excl, unit_mode));
955 if (btrfs_qgroup_columns[column].max_len < len)
956 btrfs_qgroup_columns[column].max_len = len;
957 break;
958 case BTRFS_QGROUP_PARENT:
959 len = 0;
960 list_for_each_entry(list, &bq->qgroups, next_qgroup) {
961 len += sprintf(tmp, "%llu/%llu",
962 btrfs_qgroup_level(list->qgroup->qgroupid),
963 btrfs_qgroup_subvid(list->qgroup->qgroupid));
964 if (!list_is_last(&list->next_qgroup, &bq->qgroups))
965 len += 1;
966 }
967 if (btrfs_qgroup_columns[column].max_len < len)
968 btrfs_qgroup_columns[column].max_len = len;
969 break;
970 case BTRFS_QGROUP_CHILD:
971 len = 0;
972 list_for_each_entry(list, &bq->members, next_member) {
973 len += sprintf(tmp, "%llu/%llu",
974 btrfs_qgroup_level(list->member->qgroupid),
975 btrfs_qgroup_subvid(list->member->qgroupid));
976 if (!list_is_last(&list->next_member, &bq->members))
977 len += 1;
978 }
979 if (btrfs_qgroup_columns[column].max_len < len)
980 btrfs_qgroup_columns[column].max_len = len;
981 break;
982 default:
983 break;
984 }
985
986 }
987
988 static void update_columns_max_len(struct btrfs_qgroup *bq)
989 {
990 int i;
991
992 for (i = 0; i < BTRFS_QGROUP_ALL; i++) {
993 if (!btrfs_qgroup_columns[i].need_print)
994 continue;
995 __update_columns_max_len(bq, i);
996 }
997 }
998
999 static void __filter_and_sort_qgroups(struct qgroup_lookup *all_qgroups,
1000 struct qgroup_lookup *sort_tree,
1001 struct btrfs_qgroup_filter_set *filter_set,
1002 struct btrfs_qgroup_comparer_set *comp_set)
1003 {
1004 struct rb_node *n;
1005 struct btrfs_qgroup *entry;
1006 int ret;
1007
1008 qgroup_lookup_init(sort_tree);
1009 pre_process_filter_set(all_qgroups, filter_set);
1010
1011 n = rb_last(&all_qgroups->root);
1012 while (n) {
1013 entry = rb_entry(n, struct btrfs_qgroup, rb_node);
1014
1015 ret = filter_qgroup(entry, filter_set);
1016 if (ret) {
1017 sort_tree_insert(sort_tree, entry, comp_set);
1018
1019 update_columns_max_len(entry);
1020 }
1021 n = rb_prev(n);
1022 }
1023 }
1024
1025 static inline void print_status_flag_warning(u64 flags)
1026 {
1027 if (!(flags & BTRFS_QGROUP_STATUS_FLAG_ON))
1028 warning("quota disabled, qgroup data may be out of date");
1029 else if (flags & BTRFS_QGROUP_STATUS_FLAG_RESCAN)
1030 warning("rescan is running, qgroup data may be incorrect");
1031 else if (flags & BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT)
1032 warning("qgroup data inconsistent, rescan recommended");
1033 }
1034
1035 static int __qgroups_search(int fd, struct qgroup_lookup *qgroup_lookup)
1036 {
1037 int ret;
1038 struct btrfs_ioctl_search_args args;
1039 struct btrfs_ioctl_search_key *sk = &args.key;
1040 struct btrfs_ioctl_search_header *sh;
1041 unsigned long off = 0;
1042 unsigned int i;
1043 struct btrfs_qgroup_info_item *info;
1044 struct btrfs_qgroup_limit_item *limit;
1045 struct btrfs_qgroup *bq;
1046 struct btrfs_qgroup *bq1;
1047 u64 a1;
1048 u64 a2;
1049 u64 a3;
1050 u64 a4;
1051 u64 a5;
1052
1053 memset(&args, 0, sizeof(args));
1054
1055 sk->tree_id = BTRFS_QUOTA_TREE_OBJECTID;
1056 sk->max_type = BTRFS_QGROUP_RELATION_KEY;
1057 sk->min_type = BTRFS_QGROUP_STATUS_KEY;
1058 sk->max_objectid = (u64)-1;
1059 sk->max_offset = (u64)-1;
1060 sk->max_transid = (u64)-1;
1061 sk->nr_items = 4096;
1062
1063 qgroup_lookup_init(qgroup_lookup);
1064
1065 while (1) {
1066 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
1067 if (ret < 0)
1068 return -errno;
1069
1070 /* the ioctl returns the number of item it found in nr_items */
1071 if (sk->nr_items == 0)
1072 break;
1073
1074 off = 0;
1075 /*
1076 * for each item, pull the key out of the header and then
1077 * read the root_ref item it contains
1078 */
1079 for (i = 0; i < sk->nr_items; i++) {
1080 sh = (struct btrfs_ioctl_search_header *)(args.buf +
1081 off);
1082 off += sizeof(*sh);
1083
1084 if (btrfs_search_header_type(sh)
1085 == BTRFS_QGROUP_STATUS_KEY) {
1086 struct btrfs_qgroup_status_item *si;
1087 u64 flags;
1088
1089 si = (struct btrfs_qgroup_status_item *)
1090 (args.buf + off);
1091 flags = btrfs_stack_qgroup_status_flags(si);
1092 print_status_flag_warning(flags);
1093 } else if (btrfs_search_header_type(sh)
1094 == BTRFS_QGROUP_INFO_KEY) {
1095 info = (struct btrfs_qgroup_info_item *)
1096 (args.buf + off);
1097 a1 = btrfs_stack_qgroup_info_generation(info);
1098 a2 = btrfs_stack_qgroup_info_referenced(info);
1099 a3 =
1100 btrfs_stack_qgroup_info_referenced_compressed
1101 (info);
1102 a4 = btrfs_stack_qgroup_info_exclusive(info);
1103 a5 =
1104 btrfs_stack_qgroup_info_exclusive_compressed
1105 (info);
1106 add_qgroup(qgroup_lookup,
1107 btrfs_search_header_offset(sh), a1,
1108 a2, a3, a4, a5, 0, 0, 0, 0, 0, NULL,
1109 NULL);
1110 } else if (btrfs_search_header_type(sh)
1111 == BTRFS_QGROUP_LIMIT_KEY) {
1112 limit = (struct btrfs_qgroup_limit_item *)
1113 (args.buf + off);
1114
1115 a1 = btrfs_stack_qgroup_limit_flags(limit);
1116 a2 = btrfs_stack_qgroup_limit_max_referenced
1117 (limit);
1118 a3 = btrfs_stack_qgroup_limit_max_exclusive
1119 (limit);
1120 a4 = btrfs_stack_qgroup_limit_rsv_referenced
1121 (limit);
1122 a5 = btrfs_stack_qgroup_limit_rsv_exclusive
1123 (limit);
1124 add_qgroup(qgroup_lookup,
1125 btrfs_search_header_offset(sh), 0,
1126 0, 0, 0, 0, a1, a2, a3, a4, a5,
1127 NULL, NULL);
1128 } else if (btrfs_search_header_type(sh)
1129 == BTRFS_QGROUP_RELATION_KEY) {
1130 if (btrfs_search_header_offset(sh)
1131 < btrfs_search_header_objectid(sh))
1132 goto skip;
1133 bq = qgroup_tree_search(qgroup_lookup,
1134 btrfs_search_header_offset(sh));
1135 if (!bq)
1136 goto skip;
1137 bq1 = qgroup_tree_search(qgroup_lookup,
1138 btrfs_search_header_objectid(sh));
1139 if (!bq1)
1140 goto skip;
1141 add_qgroup(qgroup_lookup,
1142 btrfs_search_header_offset(sh), 0,
1143 0, 0, 0, 0, 0, 0, 0, 0, 0, bq, bq1);
1144 } else
1145 goto done;
1146 skip:
1147 off += btrfs_search_header_len(sh);
1148
1149 /*
1150 * record the mins in sk so we can make sure the
1151 * next search doesn't repeat this root
1152 */
1153 sk->min_type = btrfs_search_header_type(sh);
1154 sk->min_offset = btrfs_search_header_offset(sh);
1155 sk->min_objectid = btrfs_search_header_objectid(sh);
1156 }
1157 sk->nr_items = 4096;
1158 /*
1159 * this iteration is done, step forward one qgroup for the next
1160 * ioctl
1161 */
1162 if (sk->min_offset < (u64)-1)
1163 sk->min_offset++;
1164 else
1165 break;
1166 }
1167
1168 done:
1169 return ret;
1170 }
1171
1172 static void print_all_qgroups(struct qgroup_lookup *qgroup_lookup)
1173 {
1174
1175 struct rb_node *n;
1176 struct btrfs_qgroup *entry;
1177
1178 print_table_head();
1179
1180 n = rb_first(&qgroup_lookup->root);
1181 while (n) {
1182 entry = rb_entry(n, struct btrfs_qgroup, sort_node);
1183 print_single_qgroup_table(entry);
1184 n = rb_next(n);
1185 }
1186 }
1187
1188 int btrfs_show_qgroups(int fd,
1189 struct btrfs_qgroup_filter_set *filter_set,
1190 struct btrfs_qgroup_comparer_set *comp_set)
1191 {
1192
1193 struct qgroup_lookup qgroup_lookup;
1194 struct qgroup_lookup sort_tree;
1195 int ret;
1196
1197 ret = __qgroups_search(fd, &qgroup_lookup);
1198 if (ret)
1199 return ret;
1200 __filter_and_sort_qgroups(&qgroup_lookup, &sort_tree,
1201 filter_set, comp_set);
1202 print_all_qgroups(&sort_tree);
1203
1204 __free_all_qgroups(&qgroup_lookup);
1205 free(filter_set);
1206 free(comp_set);
1207 return ret;
1208 }
1209
1210 int btrfs_qgroup_parse_sort_string(const char *opt_arg,
1211 struct btrfs_qgroup_comparer_set **comps)
1212 {
1213 int order;
1214 int flag;
1215 char *p;
1216 char **ptr_argv;
1217 int what_to_sort;
1218 char *opt_tmp;
1219 int ret = 0;
1220
1221 opt_tmp = strdup(opt_arg);
1222 if (!opt_tmp)
1223 return -ENOMEM;
1224
1225 while ((p = strtok(opt_tmp, ",")) != NULL) {
1226 flag = 0;
1227 ptr_argv = all_sort_items;
1228
1229 while (*ptr_argv) {
1230 if (strcmp(*ptr_argv, p) == 0) {
1231 flag = 1;
1232 break;
1233 } else {
1234 p++;
1235 if (strcmp(*ptr_argv, p) == 0) {
1236 flag = 1;
1237 p--;
1238 break;
1239 }
1240 p--;
1241 }
1242 ptr_argv++;
1243 }
1244
1245 if (flag == 0) {
1246 ret = -1;
1247 goto out;
1248 } else {
1249 if (*p == '+') {
1250 order = 0;
1251 p++;
1252 } else if (*p == '-') {
1253 order = 1;
1254 p++;
1255 } else
1256 order = 0;
1257
1258 what_to_sort = btrfs_qgroup_get_sort_item(p);
1259 if (what_to_sort < 0) {
1260 ret = -1;
1261 goto out;
1262 }
1263 btrfs_qgroup_setup_comparer(comps, what_to_sort, order);
1264 }
1265 free(opt_tmp);
1266 opt_tmp = NULL;
1267 }
1268
1269 out:
1270 free(opt_tmp);
1271 return ret;
1272 }
1273
1274 int qgroup_inherit_size(struct btrfs_qgroup_inherit *p)
1275 {
1276 return sizeof(*p) + sizeof(p->qgroups[0]) *
1277 (p->num_qgroups + 2 * p->num_ref_copies +
1278 2 * p->num_excl_copies);
1279 }
1280
1281 static int
1282 qgroup_inherit_realloc(struct btrfs_qgroup_inherit **inherit, int n, int pos)
1283 {
1284 struct btrfs_qgroup_inherit *out;
1285 int nitems = 0;
1286
1287 if (*inherit) {
1288 nitems = (*inherit)->num_qgroups +
1289 (*inherit)->num_ref_copies +
1290 (*inherit)->num_excl_copies;
1291 }
1292
1293 out = calloc(sizeof(*out) + sizeof(out->qgroups[0]) * (nitems + n), 1);
1294 if (out == NULL) {
1295 error("not enough memory");
1296 return -ENOMEM;
1297 }
1298
1299 if (*inherit) {
1300 struct btrfs_qgroup_inherit *i = *inherit;
1301 int s = sizeof(out->qgroups[0]);
1302
1303 out->num_qgroups = i->num_qgroups;
1304 out->num_ref_copies = i->num_ref_copies;
1305 out->num_excl_copies = i->num_excl_copies;
1306 memcpy(out->qgroups, i->qgroups, pos * s);
1307 memcpy(out->qgroups + pos + n, i->qgroups + pos,
1308 (nitems - pos) * s);
1309 }
1310 free(*inherit);
1311 *inherit = out;
1312
1313 return 0;
1314 }
1315
1316 int qgroup_inherit_add_group(struct btrfs_qgroup_inherit **inherit, char *arg)
1317 {
1318 int ret;
1319 u64 qgroupid = parse_qgroupid(arg);
1320 int pos = 0;
1321
1322 if (qgroupid == 0) {
1323 error("invalid qgroup specification, qgroupid must not 0");
1324 return -EINVAL;
1325 }
1326
1327 if (*inherit)
1328 pos = (*inherit)->num_qgroups;
1329 ret = qgroup_inherit_realloc(inherit, 1, pos);
1330 if (ret)
1331 return ret;
1332
1333 (*inherit)->qgroups[(*inherit)->num_qgroups++] = qgroupid;
1334
1335 return 0;
1336 }
1337
1338 int qgroup_inherit_add_copy(struct btrfs_qgroup_inherit **inherit, char *arg,
1339 int type)
1340 {
1341 int ret;
1342 u64 qgroup_src;
1343 u64 qgroup_dst;
1344 char *p;
1345 int pos = 0;
1346
1347 p = strchr(arg, ':');
1348 if (!p) {
1349 bad:
1350 error("invalid copy specification, missing separator :");
1351 return -EINVAL;
1352 }
1353 *p = 0;
1354 qgroup_src = parse_qgroupid(arg);
1355 qgroup_dst = parse_qgroupid(p + 1);
1356 *p = ':';
1357
1358 if (!qgroup_src || !qgroup_dst)
1359 goto bad;
1360
1361 if (*inherit)
1362 pos = (*inherit)->num_qgroups +
1363 (*inherit)->num_ref_copies * 2 * type;
1364
1365 ret = qgroup_inherit_realloc(inherit, 2, pos);
1366 if (ret)
1367 return ret;
1368
1369 (*inherit)->qgroups[pos++] = qgroup_src;
1370 (*inherit)->qgroups[pos++] = qgroup_dst;
1371
1372 if (!type)
1373 ++(*inherit)->num_ref_copies;
1374 else
1375 ++(*inherit)->num_excl_copies;
1376
1377 return 0;
1378 }
(deprecated) Btrfs progs developments and patch integration