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