Btrfs-progs: introduce '-e' option to print max exclusive size of qgroups
[platform/upstream/btrfs-progs.git] / qgroup.c
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 struct qgroup_lookup {
25         struct rb_root root;
26 };
27
28 struct btrfs_qgroup {
29         struct rb_node rb_node;
30         u64 qgroupid;
31
32         /*
33          * info_item
34          */
35         u64 generation;
36         u64 rfer;       /*referenced*/
37         u64 rfer_cmpr;  /*referenced compressed*/
38         u64 excl;       /*exclusive*/
39         u64 excl_cmpr;  /*exclusive compressed*/
40
41         /*
42          *limit_item
43          */
44         u64 flags;      /*which limits are set*/
45         u64 max_rfer;
46         u64 max_excl;
47         u64 rsv_rfer;
48         u64 rsv_excl;
49
50         /*qgroups this group is member of*/
51         struct list_head qgroups;
52         /*qgroups that are members of this group*/
53         struct list_head members;
54 };
55
56 /*
57  * glue structure to represent the relations
58  * between qgroups
59  */
60 struct btrfs_qgroup_list {
61         struct list_head next_qgroup;
62         struct list_head next_member;
63         struct btrfs_qgroup *qgroup;
64         struct btrfs_qgroup *member;
65 };
66
67 /*
68  * qgroupid,rfer,excl default to set
69  */
70 struct {
71         char *name;
72         char *column_name;
73         int need_print;
74 } btrfs_qgroup_columns[] = {
75         {
76                 .name           = "qgroupid",
77                 .column_name    = "Qgroupid",
78                 .need_print     = 1,
79         },
80         {
81                 .name           = "rfer",
82                 .column_name    = "Rfer",
83                 .need_print     = 1,
84         },
85         {
86                 .name           = "excl",
87                 .column_name    = "Excl",
88                 .need_print     = 1,
89         },
90         {       .name           = "max_rfer",
91                 .column_name    = "Max_rfer",
92                 .need_print     = 0,
93         },
94         {
95                 .name           = "max_excl",
96                 .column_name    = "Max_excl",
97                 .need_print     = 0,
98         },
99         {
100                 .name           = "parent",
101                 .column_name    = "Parent",
102                 .need_print     = 0,
103         },
104         {
105                 .name           = "child",
106                 .column_name    = "Child",
107                 .need_print     = 0,
108         },
109         {
110                 .name           = NULL,
111                 .column_name    = NULL,
112                 .need_print     = 0,
113         },
114 };
115
116 void btrfs_qgroup_setup_print_column(enum btrfs_qgroup_column_enum column)
117 {
118         int i;
119
120         BUG_ON(column < 0 || column > BTRFS_QGROUP_ALL);
121
122         if (column < BTRFS_QGROUP_ALL) {
123                 btrfs_qgroup_columns[column].need_print = 1;
124                 return;
125         }
126         for (i = 0; i < BTRFS_QGROUP_ALL; i++)
127                 btrfs_qgroup_columns[i].need_print = 1;
128 }
129
130 static void print_parent_column(struct btrfs_qgroup *qgroup)
131 {
132         struct btrfs_qgroup_list *list = NULL;
133
134         list_for_each_entry(list, &qgroup->qgroups, next_qgroup) {
135                 printf("%llu/%llu", (list->qgroup)->qgroupid >> 48,
136                       ((1ll << 48) - 1) & (list->qgroup)->qgroupid);
137                 if (!list_is_last(&list->next_qgroup, &qgroup->qgroups))
138                         printf(",");
139         }
140         if (list_empty(&qgroup->qgroups))
141                 printf("---");
142 }
143
144 static void print_child_column(struct btrfs_qgroup *qgroup)
145 {
146         struct btrfs_qgroup_list *list = NULL;
147
148         list_for_each_entry(list, &qgroup->members, next_member) {
149                 printf("%llu/%llu", (list->member)->qgroupid >> 48,
150                       ((1ll << 48) - 1) & (list->member)->qgroupid);
151                 if (!list_is_last(&list->next_member, &qgroup->members))
152                         printf(",");
153         }
154         if (list_empty(&qgroup->members))
155                 printf("---");
156 }
157
158 static void print_qgroup_column(struct btrfs_qgroup *qgroup,
159                                 enum btrfs_qgroup_column_enum column)
160 {
161         BUG_ON(column >= BTRFS_QGROUP_ALL || column < 0);
162
163         switch (column) {
164
165         case BTRFS_QGROUP_QGROUPID:
166                 printf("%llu/%llu", qgroup->qgroupid >> 48,
167                        ((1ll << 48) - 1) & qgroup->qgroupid);
168                 break;
169         case BTRFS_QGROUP_RFER:
170                 printf("%lld", qgroup->rfer);
171                 break;
172         case BTRFS_QGROUP_EXCL:
173                 printf("%lld", qgroup->excl);
174                 break;
175         case BTRFS_QGROUP_PARENT:
176                 print_parent_column(qgroup);
177                 break;
178         case BTRFS_QGROUP_MAX_RFER:
179                 printf("%llu", qgroup->max_rfer);
180                 break;
181         case BTRFS_QGROUP_MAX_EXCL:
182                 printf("%llu", qgroup->max_excl);
183                 break;
184         case BTRFS_QGROUP_CHILD:
185                 print_child_column(qgroup);
186                 break;
187         default:
188                 break;
189         }
190 }
191
192 static void print_single_qgroup_default(struct btrfs_qgroup *qgroup)
193 {
194         int i;
195
196         for (i = 0; i < BTRFS_QGROUP_ALL; i++) {
197                 if (!btrfs_qgroup_columns[i].need_print)
198                         continue;
199                 print_qgroup_column(qgroup, i);
200
201                 if (i != BTRFS_QGROUP_ALL - 1)
202                         printf(" ");
203         }
204         printf("\n");
205 }
206
207 static void qgroup_lookup_init(struct qgroup_lookup *tree)
208 {
209         tree->root.rb_node = NULL;
210 }
211
212 static int comp_entry_with_qgroupid(struct btrfs_qgroup *entry1,
213                                     struct btrfs_qgroup *entry2,
214                                     int is_descending)
215 {
216
217         int ret;
218
219         if (entry1->qgroupid > entry2->qgroupid)
220                 ret = 1;
221         else if (entry1->qgroupid < entry2->qgroupid)
222                 ret = -1;
223         else
224                 ret = 0;
225
226         return is_descending ? -ret : ret;
227 }
228
229 /*
230  * insert a new root into the tree.  returns the existing root entry
231  * if one is already there.  qgroupid is used
232  * as the key
233  */
234 static int qgroup_tree_insert(struct qgroup_lookup *root_tree,
235                               struct btrfs_qgroup *ins)
236 {
237
238         struct rb_node **p = &root_tree->root.rb_node;
239         struct rb_node *parent = NULL;
240         struct btrfs_qgroup *curr;
241         int ret;
242
243         while (*p) {
244                 parent = *p;
245                 curr = rb_entry(parent, struct btrfs_qgroup, rb_node);
246
247                 ret = comp_entry_with_qgroupid(ins, curr, 0);
248                 if (ret < 0)
249                         p = &(*p)->rb_left;
250                 else if (ret > 0)
251                         p = &(*p)->rb_right;
252                 else
253                         return -EEXIST;
254         }
255         rb_link_node(&ins->rb_node, parent, p);
256         rb_insert_color(&ins->rb_node, &root_tree->root);
257         return 0;
258 }
259
260 /*
261  *find a given qgroupid in the tree. We return the smallest one,
262  *rb_next can be used to move forward looking for more if required
263  */
264 static struct btrfs_qgroup *qgroup_tree_search(struct qgroup_lookup *root_tree,
265                                                u64 qgroupid)
266 {
267         struct rb_node *n = root_tree->root.rb_node;
268         struct btrfs_qgroup *entry;
269         struct btrfs_qgroup tmp;
270         int ret;
271
272         tmp.qgroupid = qgroupid;
273
274         while (n) {
275                 entry = rb_entry(n, struct btrfs_qgroup, rb_node);
276
277                 ret = comp_entry_with_qgroupid(&tmp, entry, 0);
278                 if (ret < 0)
279                         n = n->rb_left;
280                 else if (ret > 0)
281                         n = n->rb_right;
282                 else
283                         return entry;
284
285         }
286         return NULL;
287 }
288
289 static int update_qgroup(struct qgroup_lookup *qgroup_lookup, u64 qgroupid,
290                          u64 generation, u64 rfer, u64 rfer_cmpr, u64 excl,
291                          u64 excl_cmpr, u64 flags, u64 max_rfer, u64 max_excl,
292                          u64 rsv_rfer, u64 rsv_excl, struct btrfs_qgroup *pa,
293                          struct btrfs_qgroup *child)
294 {
295         struct btrfs_qgroup *bq;
296         struct btrfs_qgroup_list *list;
297
298         bq = qgroup_tree_search(qgroup_lookup, qgroupid);
299         if (!bq || bq->qgroupid != qgroupid)
300                 return -ENOENT;
301
302         if (generation)
303                 bq->generation = generation;
304         if (rfer)
305                 bq->rfer = rfer;
306         if (rfer_cmpr)
307                 bq->rfer_cmpr = rfer_cmpr;
308         if (excl)
309                 bq->excl = excl;
310         if (excl_cmpr)
311                 bq->excl_cmpr = excl_cmpr;
312         if (flags)
313                 bq->flags = flags;
314         if (max_rfer)
315                 bq->max_rfer = max_rfer;
316         if (max_excl)
317                 bq->max_excl = max_excl;
318         if (rsv_rfer)
319                 bq->rsv_rfer = rsv_rfer;
320         if (pa && child) {
321                 list = malloc(sizeof(*list));
322                 if (!list) {
323                         fprintf(stderr, "memory allocation failed\n");
324                         exit(1);
325                 }
326                 list->qgroup = pa;
327                 list->member = child;
328                 list_add_tail(&list->next_qgroup, &child->qgroups);
329                 list_add_tail(&list->next_member, &pa->members);
330         }
331         return 0;
332 }
333
334 static int add_qgroup(struct qgroup_lookup *qgroup_lookup, u64 qgroupid,
335                       u64 generation, u64 rfer, u64 rfer_cmpr, u64 excl,
336                       u64 excl_cmpr, u64 flags, u64 max_rfer, u64 max_excl,
337                       u64 rsv_rfer, u64 rsv_excl, struct btrfs_qgroup *parent,
338                       struct btrfs_qgroup *child)
339 {
340         struct btrfs_qgroup *bq;
341         struct btrfs_qgroup_list *list;
342         int ret;
343
344         ret = update_qgroup(qgroup_lookup, qgroupid, generation, rfer,
345                             rfer_cmpr, excl, excl_cmpr, flags, max_rfer,
346                             max_excl, rsv_rfer, rsv_excl, parent, child);
347         if (!ret)
348                 return 0;
349
350         bq = malloc(sizeof(*bq));
351         if (!bq) {
352                 printf("memory allocation failed\n");
353                 exit(1);
354         }
355         memset(bq, 0, sizeof(*bq));
356         if (qgroupid) {
357                 bq->qgroupid = qgroupid;
358                 INIT_LIST_HEAD(&bq->qgroups);
359                 INIT_LIST_HEAD(&bq->members);
360         }
361         if (generation)
362                 bq->generation = generation;
363         if (rfer)
364                 bq->rfer = rfer;
365         if (rfer_cmpr)
366                 bq->rfer_cmpr = rfer_cmpr;
367         if (excl)
368                 bq->excl = excl;
369         if (excl_cmpr)
370                 bq->excl_cmpr = excl_cmpr;
371         if (flags)
372                 bq->flags = flags;
373         if (max_rfer)
374                 bq->max_rfer = max_rfer;
375         if (max_excl)
376                 bq->max_excl = max_excl;
377         if (rsv_rfer)
378                 bq->rsv_rfer = rsv_rfer;
379         if (parent && child) {
380                 list = malloc(sizeof(*list));
381                 if (!list) {
382                         fprintf(stderr, "memory allocation failed\n");
383                         exit(1);
384                 }
385                 list->qgroup = parent;
386                 list->member = child;
387                 list_add_tail(&list->next_qgroup, &child->qgroups);
388                 list_add_tail(&list->next_member, &parent->members);
389         }
390         ret = qgroup_tree_insert(qgroup_lookup, bq);
391         if (ret) {
392                 printf("failed to insert tree %llu\n",
393                        bq->qgroupid);
394                 exit(1);
395         }
396         return ret;
397 }
398
399 void __free_btrfs_qgroup(struct btrfs_qgroup *bq)
400 {
401         struct btrfs_qgroup_list *list;
402         while (!list_empty(&bq->qgroups)) {
403                 list = list_entry((&bq->qgroups)->next,
404                                   struct btrfs_qgroup_list,
405                                   next_qgroup);
406                 list_del(&list->next_qgroup);
407                 list_del(&list->next_member);
408                 free(list);
409         }
410         while (!list_empty(&bq->members)) {
411                 list = list_entry((&bq->members)->next,
412                                   struct btrfs_qgroup_list,
413                                   next_member);
414                 list_del(&list->next_qgroup);
415                 list_del(&list->next_member);
416                 free(list);
417         }
418         free(bq);
419 }
420
421 void __free_all_qgroups(struct qgroup_lookup *root_tree)
422 {
423         struct btrfs_qgroup *entry;
424         struct rb_node *n;
425
426         n = rb_first(&root_tree->root);
427         while (n) {
428                 entry = rb_entry(n, struct btrfs_qgroup, rb_node);
429                 rb_erase(n, &root_tree->root);
430                 __free_btrfs_qgroup(entry);
431
432                 n = rb_first(&root_tree->root);
433         }
434 }
435
436 static int __qgroups_search(int fd, struct qgroup_lookup *qgroup_lookup)
437 {
438         int ret;
439         struct btrfs_ioctl_search_args args;
440         struct btrfs_ioctl_search_key *sk = &args.key;
441         struct btrfs_ioctl_search_header *sh;
442         unsigned long off = 0;
443         unsigned int i;
444         int e;
445         struct btrfs_qgroup_info_item *info;
446         struct btrfs_qgroup_limit_item *limit;
447         struct btrfs_qgroup *bq;
448         struct btrfs_qgroup *bq1;
449         u64 a1;
450         u64 a2;
451         u64 a3;
452         u64 a4;
453         u64 a5;
454
455         memset(&args, 0, sizeof(args));
456
457         sk->tree_id = BTRFS_QUOTA_TREE_OBJECTID;
458         sk->max_type = BTRFS_QGROUP_RELATION_KEY;
459         sk->min_type = BTRFS_QGROUP_INFO_KEY;
460         sk->max_objectid = (u64)-1;
461         sk->max_offset = (u64)-1;
462         sk->max_transid = (u64)-1;
463         sk->nr_items = 4096;
464
465         qgroup_lookup_init(qgroup_lookup);
466
467         while (1) {
468                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
469                 e = errno;
470                 if (ret < 0) {
471                         fprintf(stderr,
472                                 "ERROR: can't perform the search - %s\n",
473                                 strerror(e));
474                         return ret;
475                 }
476                 /* the ioctl returns the number of item it found in nr_items */
477                 if (sk->nr_items == 0)
478                         break;
479
480                 off = 0;
481                 /*
482                  * for each item, pull the key out of the header and then
483                  * read the root_ref item it contains
484                  */
485                 for (i = 0; i < sk->nr_items; i++) {
486                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
487                                                                   off);
488                         off += sizeof(*sh);
489
490                         if (sh->type == BTRFS_QGROUP_INFO_KEY) {
491                                 info = (struct btrfs_qgroup_info_item *)
492                                        (args.buf + off);
493                                 a1 = btrfs_stack_qgroup_info_generation(info);
494                                 a2 = btrfs_stack_qgroup_info_referenced(info);
495                                 a3 =
496                                   btrfs_stack_qgroup_info_referenced_compressed
497                                   (info);
498                                 a4 = btrfs_stack_qgroup_info_exclusive(info);
499                                 a5 =
500                                   btrfs_stack_qgroup_info_exclusive_compressed
501                                   (info);
502                                 add_qgroup(qgroup_lookup, sh->offset, a1, a2,
503                                            a3, a4, a5, 0, 0, 0, 0, 0, 0, 0);
504                         } else if (sh->type == BTRFS_QGROUP_LIMIT_KEY) {
505                                 limit = (struct btrfs_qgroup_limit_item *)
506                                     (args.buf + off);
507
508                                 a1 = btrfs_stack_qgroup_limit_flags(limit);
509                                 a2 = btrfs_stack_qgroup_limit_max_referenced
510                                      (limit);
511                                 a3 = btrfs_stack_qgroup_limit_max_exclusive
512                                      (limit);
513                                 a4 = btrfs_stack_qgroup_limit_rsv_referenced
514                                      (limit);
515                                 a5 = btrfs_stack_qgroup_limit_rsv_exclusive
516                                      (limit);
517                                 add_qgroup(qgroup_lookup, sh->offset, 0, 0,
518                                            0, 0, 0, a1, a2, a3, a4, a5, 0, 0);
519                         } else if (sh->type == BTRFS_QGROUP_RELATION_KEY) {
520                                 if (sh->offset < sh->objectid)
521                                         goto skip;
522                                 bq = qgroup_tree_search(qgroup_lookup,
523                                                         sh->offset);
524                                 if (!bq)
525                                         goto skip;
526                                 bq1 = qgroup_tree_search(qgroup_lookup,
527                                                          sh->objectid);
528                                 if (!bq1)
529                                         goto skip;
530                                 add_qgroup(qgroup_lookup, sh->offset, 0, 0,
531                                            0, 0, 0, 0, 0, 0, 0, 0, bq, bq1);
532                         } else
533                                 goto done;
534 skip:
535                         off += sh->len;
536
537                         /*
538                          * record the mins in sk so we can make sure the
539                          * next search doesn't repeat this root
540                          */
541                         sk->min_type = sh->type;
542                         sk->min_offset = sh->offset;
543                         sk->min_objectid = sh->objectid;
544                 }
545                 sk->nr_items = 4096;
546                 /*
547                  * this iteration is done, step forward one qgroup for the next
548                  * ioctl
549                  */
550                 if (sk->min_offset < (u64)-1)
551                         sk->min_offset++;
552                 else
553                         break;
554         }
555
556 done:
557         return ret;
558 }
559
560 static void print_all_qgroups(struct qgroup_lookup *qgroup_lookup)
561 {
562
563         struct rb_node *n;
564         struct btrfs_qgroup *entry;
565
566         n = rb_first(&qgroup_lookup->root);
567         while (n) {
568                 entry = rb_entry(n, struct btrfs_qgroup, rb_node);
569                 print_single_qgroup_default(entry);
570                 n = rb_next(n);
571         }
572 }
573
574 int btrfs_show_qgroups(int fd)
575 {
576
577         struct qgroup_lookup qgroup_lookup;
578         int ret;
579
580         ret = __qgroups_search(fd, &qgroup_lookup);
581         if (ret)
582                 return ret;
583
584         print_all_qgroups(&qgroup_lookup);
585         __free_all_qgroups(&qgroup_lookup);
586
587         return ret;
588 }
589
590 u64 parse_qgroupid(char *p)
591 {
592         char *s = strchr(p, '/');
593         char *ptr_src_end = p + strlen(p);
594         char *ptr_parse_end = NULL;
595         u64 level;
596         u64 id;
597
598         if (!s) {
599                 id = strtoull(p, &ptr_parse_end, 10);
600                 if (ptr_parse_end != ptr_src_end)
601                         goto err;
602                 return id;
603         }
604         level = strtoull(p, &ptr_parse_end, 10);
605         if (ptr_parse_end != s)
606                 goto err;
607
608         id = strtoull(s+1, &ptr_parse_end, 10);
609         if (ptr_parse_end != ptr_src_end)
610                 goto  err;
611
612         return (level << 48) | id;
613 err:
614         fprintf(stderr, "ERROR:invalid qgroupid\n");
615         exit(-1);
616 }
617
618 int qgroup_inherit_size(struct btrfs_qgroup_inherit *p)
619 {
620         return sizeof(*p) + sizeof(p->qgroups[0]) *
621                             (p->num_qgroups + 2 * p->num_ref_copies +
622                              2 * p->num_excl_copies);
623 }
624
625 static int
626 qgroup_inherit_realloc(struct btrfs_qgroup_inherit **inherit, int n, int pos)
627 {
628         struct btrfs_qgroup_inherit *out;
629         int nitems = 0;
630
631         if (*inherit) {
632                 nitems = (*inherit)->num_qgroups +
633                          (*inherit)->num_ref_copies +
634                          (*inherit)->num_excl_copies;
635         }
636
637         out = calloc(sizeof(*out) + sizeof(out->qgroups[0]) * (nitems + n), 1);
638         if (out == NULL) {
639                 fprintf(stderr, "ERROR: Not enough memory\n");
640                 return 13;
641         }
642
643         if (*inherit) {
644                 struct btrfs_qgroup_inherit *i = *inherit;
645                 int s = sizeof(out->qgroups[0]);
646
647                 out->num_qgroups = i->num_qgroups;
648                 out->num_ref_copies = i->num_ref_copies;
649                 out->num_excl_copies = i->num_excl_copies;
650                 memcpy(out->qgroups, i->qgroups, pos * s);
651                 memcpy(out->qgroups + pos + n, i->qgroups + pos,
652                        (nitems - pos) * s);
653         }
654         free(*inherit);
655         *inherit = out;
656
657         return 0;
658 }
659
660 int qgroup_inherit_add_group(struct btrfs_qgroup_inherit **inherit, char *arg)
661 {
662         int ret;
663         u64 qgroupid = parse_qgroupid(arg);
664         int pos = 0;
665
666         if (qgroupid == 0) {
667                 fprintf(stderr, "ERROR: bad qgroup specification\n");
668                 return 12;
669         }
670
671         if (*inherit)
672                 pos = (*inherit)->num_qgroups;
673         ret = qgroup_inherit_realloc(inherit, 1, pos);
674         if (ret)
675                 return ret;
676
677         (*inherit)->qgroups[(*inherit)->num_qgroups++] = qgroupid;
678
679         return 0;
680 }
681
682 int qgroup_inherit_add_copy(struct btrfs_qgroup_inherit **inherit, char *arg,
683                             int type)
684 {
685         int ret;
686         u64 qgroup_src;
687         u64 qgroup_dst;
688         char *p;
689         int pos = 0;
690
691         p = strchr(arg, ':');
692         if (!p) {
693 bad:
694                 fprintf(stderr, "ERROR: bad copy specification\n");
695                 return 12;
696         }
697         *p = 0;
698         qgroup_src = parse_qgroupid(arg);
699         qgroup_dst = parse_qgroupid(p + 1);
700         *p = ':';
701
702         if (!qgroup_src || !qgroup_dst)
703                 goto bad;
704
705         if (*inherit)
706                 pos = (*inherit)->num_qgroups +
707                       (*inherit)->num_ref_copies * 2 * type;
708
709         ret = qgroup_inherit_realloc(inherit, 2, pos);
710         if (ret)
711                 return ret;
712
713         (*inherit)->qgroups[pos++] = qgroup_src;
714         (*inherit)->qgroups[pos++] = qgroup_dst;
715
716         if (!type)
717                 ++(*inherit)->num_ref_copies;
718         else
719                 ++(*inherit)->num_excl_copies;
720
721         return 0;
722 }