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