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