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 #define BTRFS_QGROUP_NFILTERS_INCREASE (2 * BTRFS_QGROUP_FILTER_MAX)
  25
  26 struct qgroup_lookup {
  27         struct rb_root root;
  28 };
  29
  30 struct btrfs_qgroup {
  31         struct rb_node rb_node;
  32         struct rb_node sort_node;
  33         /*
  34          *all_parent_node is used to
  35          *filter a qgroup's all parent
  36          */
  37         struct rb_node all_parent_node;
  38         u64 qgroupid;
  39
  40         /*
  41          * info_item
  42          */
  43         u64 generation;
  44         u64 rfer;       /*referenced*/
  45         u64 rfer_cmpr;  /*referenced compressed*/
  46         u64 excl;       /*exclusive*/
  47         u64 excl_cmpr;  /*exclusive compressed*/
  48
  49         /*
  50          *limit_item
  51          */
  52         u64 flags;      /*which limits are set*/
  53         u64 max_rfer;
  54         u64 max_excl;
  55         u64 rsv_rfer;
  56         u64 rsv_excl;
  57
  58         /*qgroups this group is member of*/
  59         struct list_head qgroups;
  60         /*qgroups that are members of this group*/
  61         struct list_head members;
  62 };
  63
  64 /*
  65  * glue structure to represent the relations
  66  * between qgroups
  67  */
  68 struct btrfs_qgroup_list {
  69         struct list_head next_qgroup;
  70         struct list_head next_member;
  71         struct btrfs_qgroup *qgroup;
  72         struct btrfs_qgroup *member;
  73 };
  74
  75 /*
  76  * qgroupid,rfer,excl default to set
  77  */
  78 struct {
  79         char *name;
  80         char *column_name;
  81         int need_print;
  82 } btrfs_qgroup_columns[] = {
  83         {
  84                 .name           = "qgroupid",
  85                 .column_name    = "Qgroupid",
  86                 .need_print     = 1,
  87         },
  88         {
  89                 .name           = "rfer",
  90                 .column_name    = "Rfer",
  91                 .need_print     = 1,
  92         },
  93         {
  94                 .name           = "excl",
  95                 .column_name    = "Excl",
  96                 .need_print     = 1,
  97         },
  98         {       .name           = "max_rfer",
  99                 .column_name    = "Max_rfer",
 100                 .need_print     = 0,
 101         },
 102         {
 103                 .name           = "max_excl",
 104                 .column_name    = "Max_excl",
 105                 .need_print     = 0,
 106         },
 107         {
 108                 .name           = "parent",
 109                 .column_name    = "Parent",
 110                 .need_print     = 0,
 111         },
 112         {
 113                 .name           = "child",
 114                 .column_name    = "Child",
 115                 .need_print     = 0,
 116         },
 117         {
 118                 .name           = NULL,
 119                 .column_name    = NULL,
 120                 .need_print     = 0,
 121         },
 122 };
 123
 124 static btrfs_qgroup_filter_func all_filter_funcs[];
 125
 126 void btrfs_qgroup_setup_print_column(enum btrfs_qgroup_column_enum column)
 127 {
 128         int i;
 129
 130         BUG_ON(column < 0 || column > BTRFS_QGROUP_ALL);
 131
 132         if (column < BTRFS_QGROUP_ALL) {
 133                 btrfs_qgroup_columns[column].need_print = 1;
 134                 return;
 135         }
 136         for (i = 0; i < BTRFS_QGROUP_ALL; i++)
 137                 btrfs_qgroup_columns[i].need_print = 1;
 138 }
 139
 140 static void print_parent_column(struct btrfs_qgroup *qgroup)
 141 {
 142         struct btrfs_qgroup_list *list = NULL;
 143
 144         list_for_each_entry(list, &qgroup->qgroups, next_qgroup) {
 145                 printf("%llu/%llu", (list->qgroup)->qgroupid >> 48,
 146                       ((1ll << 48) - 1) & (list->qgroup)->qgroupid);
 147                 if (!list_is_last(&list->next_qgroup, &qgroup->qgroups))
 148                         printf(",");
 149         }
 150         if (list_empty(&qgroup->qgroups))
 151                 printf("---");
 152 }
 153
 154 static void print_child_column(struct btrfs_qgroup *qgroup)
 155 {
 156         struct btrfs_qgroup_list *list = NULL;
 157
 158         list_for_each_entry(list, &qgroup->members, next_member) {
 159                 printf("%llu/%llu", (list->member)->qgroupid >> 48,
 160                       ((1ll << 48) - 1) & (list->member)->qgroupid);
 161                 if (!list_is_last(&list->next_member, &qgroup->members))
 162                         printf(",");
 163         }
 164         if (list_empty(&qgroup->members))
 165                 printf("---");
 166 }
 167
 168 static void print_qgroup_column(struct btrfs_qgroup *qgroup,
 169                                 enum btrfs_qgroup_column_enum column)
 170 {
 171         BUG_ON(column >= BTRFS_QGROUP_ALL || column < 0);
 172
 173         switch (column) {
 174
 175         case BTRFS_QGROUP_QGROUPID:
 176                 printf("%llu/%llu", qgroup->qgroupid >> 48,
 177                        ((1ll << 48) - 1) & qgroup->qgroupid);
 178                 break;
 179         case BTRFS_QGROUP_RFER:
 180                 printf("%lld", qgroup->rfer);
 181                 break;
 182         case BTRFS_QGROUP_EXCL:
 183                 printf("%lld", qgroup->excl);
 184                 break;
 185         case BTRFS_QGROUP_PARENT:
 186                 print_parent_column(qgroup);
 187                 break;
 188         case BTRFS_QGROUP_MAX_RFER:
 189                 printf("%llu", qgroup->max_rfer);
 190                 break;
 191         case BTRFS_QGROUP_MAX_EXCL:
 192                 printf("%llu", qgroup->max_excl);
 193                 break;
 194         case BTRFS_QGROUP_CHILD:
 195                 print_child_column(qgroup);
 196                 break;
 197         default:
 198                 break;
 199         }
 200 }
 201
 202 static void print_single_qgroup_default(struct btrfs_qgroup *qgroup)
 203 {
 204         int i;
 205
 206         for (i = 0; i < BTRFS_QGROUP_ALL; i++) {
 207                 if (!btrfs_qgroup_columns[i].need_print)
 208                         continue;
 209                 print_qgroup_column(qgroup, i);
 210
 211                 if (i != BTRFS_QGROUP_ALL - 1)
 212                         printf(" ");
 213         }
 214         printf("\n");
 215 }
 216
 217 static void qgroup_lookup_init(struct qgroup_lookup *tree)
 218 {
 219         tree->root.rb_node = NULL;
 220 }
 221
 222 static int comp_entry_with_qgroupid(struct btrfs_qgroup *entry1,
 223                                     struct btrfs_qgroup *entry2,
 224                                     int is_descending)
 225 {
 226
 227         int ret;
 228
 229         if (entry1->qgroupid > entry2->qgroupid)
 230                 ret = 1;
 231         else if (entry1->qgroupid < entry2->qgroupid)
 232                 ret = -1;
 233         else
 234                 ret = 0;
 235
 236         return is_descending ? -ret : ret;
 237 }
 238
 239 /*
 240  * insert a new root into the tree.  returns the existing root entry
 241  * if one is already there.  qgroupid is used
 242  * as the key
 243  */
 244 static int qgroup_tree_insert(struct qgroup_lookup *root_tree,
 245                               struct btrfs_qgroup *ins)
 246 {
 247
 248         struct rb_node **p = &root_tree->root.rb_node;
 249         struct rb_node *parent = NULL;
 250         struct btrfs_qgroup *curr;
 251         int ret;
 252
 253         while (*p) {
 254                 parent = *p;
 255                 curr = rb_entry(parent, struct btrfs_qgroup, rb_node);
 256
 257                 ret = comp_entry_with_qgroupid(ins, curr, 0);
 258                 if (ret < 0)
 259                         p = &(*p)->rb_left;
 260                 else if (ret > 0)
 261                         p = &(*p)->rb_right;
 262                 else
 263                         return -EEXIST;
 264         }
 265         rb_link_node(&ins->rb_node, parent, p);
 266         rb_insert_color(&ins->rb_node, &root_tree->root);
 267         return 0;
 268 }
 269
 270 /*
 271  *find a given qgroupid in the tree. We return the smallest one,
 272  *rb_next can be used to move forward looking for more if required
 273  */
 274 static struct btrfs_qgroup *qgroup_tree_search(struct qgroup_lookup *root_tree,
 275                                                u64 qgroupid)
 276 {
 277         struct rb_node *n = root_tree->root.rb_node;
 278         struct btrfs_qgroup *entry;
 279         struct btrfs_qgroup tmp;
 280         int ret;
 281
 282         tmp.qgroupid = qgroupid;
 283
 284         while (n) {
 285                 entry = rb_entry(n, struct btrfs_qgroup, rb_node);
 286
 287                 ret = comp_entry_with_qgroupid(&tmp, entry, 0);
 288                 if (ret < 0)
 289                         n = n->rb_left;
 290                 else if (ret > 0)
 291                         n = n->rb_right;
 292                 else
 293                         return entry;
 294
 295         }
 296         return NULL;
 297 }
 298
 299 static int update_qgroup(struct qgroup_lookup *qgroup_lookup, u64 qgroupid,
 300                          u64 generation, u64 rfer, u64 rfer_cmpr, u64 excl,
 301                          u64 excl_cmpr, u64 flags, u64 max_rfer, u64 max_excl,
 302                          u64 rsv_rfer, u64 rsv_excl, struct btrfs_qgroup *pa,
 303                          struct btrfs_qgroup *child)
 304 {
 305         struct btrfs_qgroup *bq;
 306         struct btrfs_qgroup_list *list;
 307
 308         bq = qgroup_tree_search(qgroup_lookup, qgroupid);
 309         if (!bq || bq->qgroupid != qgroupid)
 310                 return -ENOENT;
 311
 312         if (generation)
 313                 bq->generation = generation;
 314         if (rfer)
 315                 bq->rfer = rfer;
 316         if (rfer_cmpr)
 317                 bq->rfer_cmpr = rfer_cmpr;
 318         if (excl)
 319                 bq->excl = excl;
 320         if (excl_cmpr)
 321                 bq->excl_cmpr = excl_cmpr;
 322         if (flags)
 323                 bq->flags = flags;
 324         if (max_rfer)
 325                 bq->max_rfer = max_rfer;
 326         if (max_excl)
 327                 bq->max_excl = max_excl;
 328         if (rsv_rfer)
 329                 bq->rsv_rfer = rsv_rfer;
 330         if (pa && child) {
 331                 list = malloc(sizeof(*list));
 332                 if (!list) {
 333                         fprintf(stderr, "memory allocation failed\n");
 334                         exit(1);
 335                 }
 336                 list->qgroup = pa;
 337                 list->member = child;
 338                 list_add_tail(&list->next_qgroup, &child->qgroups);
 339                 list_add_tail(&list->next_member, &pa->members);
 340         }
 341         return 0;
 342 }
 343
 344 static int add_qgroup(struct qgroup_lookup *qgroup_lookup, u64 qgroupid,
 345                       u64 generation, u64 rfer, u64 rfer_cmpr, u64 excl,
 346                       u64 excl_cmpr, u64 flags, u64 max_rfer, u64 max_excl,
 347                       u64 rsv_rfer, u64 rsv_excl, struct btrfs_qgroup *parent,
 348                       struct btrfs_qgroup *child)
 349 {
 350         struct btrfs_qgroup *bq;
 351         struct btrfs_qgroup_list *list;
 352         int ret;
 353
 354         ret = update_qgroup(qgroup_lookup, qgroupid, generation, rfer,
 355                             rfer_cmpr, excl, excl_cmpr, flags, max_rfer,
 356                             max_excl, rsv_rfer, rsv_excl, parent, child);
 357         if (!ret)
 358                 return 0;
 359
 360         bq = malloc(sizeof(*bq));
 361         if (!bq) {
 362                 printf("memory allocation failed\n");
 363                 exit(1);
 364         }
 365         memset(bq, 0, sizeof(*bq));
 366         if (qgroupid) {
 367                 bq->qgroupid = qgroupid;
 368                 INIT_LIST_HEAD(&bq->qgroups);
 369                 INIT_LIST_HEAD(&bq->members);
 370         }
 371         if (generation)
 372                 bq->generation = generation;
 373         if (rfer)
 374                 bq->rfer = rfer;
 375         if (rfer_cmpr)
 376                 bq->rfer_cmpr = rfer_cmpr;
 377         if (excl)
 378                 bq->excl = excl;
 379         if (excl_cmpr)
 380                 bq->excl_cmpr = excl_cmpr;
 381         if (flags)
 382                 bq->flags = flags;
 383         if (max_rfer)
 384                 bq->max_rfer = max_rfer;
 385         if (max_excl)
 386                 bq->max_excl = max_excl;
 387         if (rsv_rfer)
 388                 bq->rsv_rfer = rsv_rfer;
 389         if (parent && child) {
 390                 list = malloc(sizeof(*list));
 391                 if (!list) {
 392                         fprintf(stderr, "memory allocation failed\n");
 393                         exit(1);
 394                 }
 395                 list->qgroup = parent;
 396                 list->member = child;
 397                 list_add_tail(&list->next_qgroup, &child->qgroups);
 398                 list_add_tail(&list->next_member, &parent->members);
 399         }
 400         ret = qgroup_tree_insert(qgroup_lookup, bq);
 401         if (ret) {
 402                 printf("failed to insert tree %llu\n",
 403                        bq->qgroupid);
 404                 exit(1);
 405         }
 406         return ret;
 407 }
 408
 409 void __free_btrfs_qgroup(struct btrfs_qgroup *bq)
 410 {
 411         struct btrfs_qgroup_list *list;
 412         while (!list_empty(&bq->qgroups)) {
 413                 list = list_entry((&bq->qgroups)->next,
 414                                   struct btrfs_qgroup_list,
 415                                   next_qgroup);
 416                 list_del(&list->next_qgroup);
 417                 list_del(&list->next_member);
 418                 free(list);
 419         }
 420         while (!list_empty(&bq->members)) {
 421                 list = list_entry((&bq->members)->next,
 422                                   struct btrfs_qgroup_list,
 423                                   next_member);
 424                 list_del(&list->next_qgroup);
 425                 list_del(&list->next_member);
 426                 free(list);
 427         }
 428         free(bq);
 429 }
 430
 431 void __free_all_qgroups(struct qgroup_lookup *root_tree)
 432 {
 433         struct btrfs_qgroup *entry;
 434         struct rb_node *n;
 435
 436         n = rb_first(&root_tree->root);
 437         while (n) {
 438                 entry = rb_entry(n, struct btrfs_qgroup, rb_node);
 439                 rb_erase(n, &root_tree->root);
 440                 __free_btrfs_qgroup(entry);
 441
 442                 n = rb_first(&root_tree->root);
 443         }
 444 }
 445
 446 static int filter_all_parent_insert(struct qgroup_lookup *sort_tree,
 447                                     struct btrfs_qgroup *bq)
 448 {
 449         struct rb_node **p = &sort_tree->root.rb_node;
 450         struct rb_node *parent = NULL;
 451         struct btrfs_qgroup *curr;
 452         int ret;
 453
 454         while (*p) {
 455                 parent = *p;
 456                 curr = rb_entry(parent, struct btrfs_qgroup, all_parent_node);
 457
 458                 ret = comp_entry_with_qgroupid(bq, curr, 0);
 459                 if (ret < 0)
 460                         p = &(*p)->rb_left;
 461                 else if (ret > 0)
 462                         p = &(*p)->rb_right;
 463                 else
 464                         return -EEXIST;
 465         }
 466         rb_link_node(&bq->all_parent_node, parent, p);
 467         rb_insert_color(&bq->all_parent_node, &sort_tree->root);
 468         return 0;
 469 }
 470
 471 static int filter_by_all_parent(struct btrfs_qgroup *bq, u64 data)
 472 {
 473         struct qgroup_lookup lookup;
 474         struct qgroup_lookup *ql = &lookup;
 475         struct btrfs_qgroup_list *list;
 476         struct rb_node *n;
 477         struct btrfs_qgroup *qgroup =
 478                          (struct btrfs_qgroup *)(unsigned long)data;
 479
 480         if (data == 0)
 481                 return 0;
 482         if (bq->qgroupid == qgroup->qgroupid)
 483                 return 1;
 484
 485         qgroup_lookup_init(ql);
 486         filter_all_parent_insert(ql, qgroup);
 487         n = rb_first(&ql->root);
 488         while (n) {
 489                 qgroup = rb_entry(n, struct btrfs_qgroup, all_parent_node);
 490                 if (!list_empty(&qgroup->qgroups)) {
 491                         list_for_each_entry(list, &qgroup->qgroups,
 492                                             next_qgroup) {
 493                                 if ((list->qgroup)->qgroupid == bq->qgroupid)
 494                                         return 1;
 495                                 filter_all_parent_insert(ql, list->qgroup);
 496                         }
 497                 }
 498                 rb_erase(n, &ql->root);
 499                 n = rb_first(&ql->root);
 500         }
 501         return 0;
 502 }
 503
 504 static btrfs_qgroup_filter_func all_filter_funcs[] = {
 505         [BTRFS_QGROUP_FILTER_ALL_PARENT]        = filter_by_all_parent,
 506 };
 507
 508 struct btrfs_qgroup_filter_set *btrfs_qgroup_alloc_filter_set(void)
 509 {
 510         struct btrfs_qgroup_filter_set *set;
 511         int size;
 512
 513         size = sizeof(struct btrfs_qgroup_filter_set) +
 514                BTRFS_QGROUP_NFILTERS_INCREASE *
 515                sizeof(struct btrfs_qgroup_filter);
 516         set = malloc(size);
 517         if (!set) {
 518                 fprintf(stderr, "memory allocation failed\n");
 519                 exit(1);
 520         }
 521         memset(set, 0, size);
 522         set->total = BTRFS_QGROUP_NFILTERS_INCREASE;
 523
 524         return set;
 525 }
 526
 527 void btrfs_qgroup_free_filter_set(struct btrfs_qgroup_filter_set *filter_set)
 528 {
 529         free(filter_set);
 530 }
 531
 532 int btrfs_qgroup_setup_filter(struct btrfs_qgroup_filter_set **filter_set,
 533                               enum btrfs_qgroup_filter_enum filter, u64 data)
 534 {
 535         struct btrfs_qgroup_filter_set *set = *filter_set;
 536         int size;
 537
 538         BUG_ON(!set);
 539         BUG_ON(filter >= BTRFS_QGROUP_FILTER_MAX);
 540         BUG_ON(set->nfilters > set->total);
 541
 542         if (set->nfilters == set->total) {
 543                 size = set->total + BTRFS_QGROUP_NFILTERS_INCREASE;
 544                 size = sizeof(*set) + size * sizeof(struct btrfs_qgroup_filter);
 545
 546                 set = realloc(set, size);
 547                 if (!set) {
 548                         fprintf(stderr, "memory allocation failed\n");
 549                         exit(1);
 550                 }
 551                 memset(&set->filters[set->total], 0,
 552                        BTRFS_QGROUP_NFILTERS_INCREASE *
 553                        sizeof(struct btrfs_qgroup_filter));
 554                 set->total += BTRFS_QGROUP_NFILTERS_INCREASE;
 555                 *filter_set = set;
 556         }
 557         BUG_ON(set->filters[set->nfilters].filter_func);
 558         set->filters[set->nfilters].filter_func = all_filter_funcs[filter];
 559         set->filters[set->nfilters].data = data;
 560         set->nfilters++;
 561         return 0;
 562 }
 563
 564 static int filter_qgroup(struct btrfs_qgroup *bq,
 565                          struct btrfs_qgroup_filter_set *set)
 566 {
 567         int i, ret;
 568
 569         if (!set || !set->nfilters)
 570                 return 1;
 571         for (i = 0; i < set->nfilters; i++) {
 572                 if (!set->filters[i].filter_func)
 573                         break;
 574                 ret = set->filters[i].filter_func(bq, set->filters[i].data);
 575                 if (!ret)
 576                         return 0;
 577         }
 578         return 1;
 579 }
 580
 581 static void pre_process_filter_set(struct qgroup_lookup *lookup,
 582                                    struct btrfs_qgroup_filter_set *set)
 583 {
 584         int i;
 585         struct btrfs_qgroup *qgroup_for_filter = NULL;
 586
 587         for (i = 0; i < set->nfilters; i++) {
 588
 589                 if (set->filters[i].filter_func == filter_by_all_parent) {
 590                         qgroup_for_filter = qgroup_tree_search(lookup,
 591                                             set->filters[i].data);
 592                         set->filters[i].data =
 593                                  (u64)(unsigned long)qgroup_for_filter;
 594                 }
 595         }
 596 }
 597
 598 static int sort_tree_insert(struct qgroup_lookup *sort_tree,
 599                             struct btrfs_qgroup *bq)
 600 {
 601         struct rb_node **p = &sort_tree->root.rb_node;
 602         struct rb_node *parent = NULL;
 603         struct btrfs_qgroup *curr;
 604         int ret;
 605
 606         while (*p) {
 607                 parent = *p;
 608                 curr = rb_entry(parent, struct btrfs_qgroup, sort_node);
 609
 610                 ret = comp_entry_with_qgroupid(bq, curr, 0);
 611                 if (ret < 0)
 612                         p = &(*p)->rb_left;
 613                 else if (ret > 0)
 614                         p = &(*p)->rb_right;
 615                 else
 616                         return -EEXIST;
 617         }
 618         rb_link_node(&bq->sort_node, parent, p);
 619         rb_insert_color(&bq->sort_node, &sort_tree->root);
 620         return 0;
 621 }
 622
 623 static void __filter_all_qgroups(struct qgroup_lookup *all_qgroups,
 624                                  struct qgroup_lookup *sort_tree,
 625                                  struct btrfs_qgroup_filter_set *filter_set)
 626 {
 627         struct rb_node *n;
 628         struct btrfs_qgroup *entry;
 629         int ret;
 630
 631         qgroup_lookup_init(sort_tree);
 632         pre_process_filter_set(all_qgroups, filter_set);
 633
 634         n = rb_last(&all_qgroups->root);
 635         while (n) {
 636                 entry = rb_entry(n, struct btrfs_qgroup, rb_node);
 637
 638                 ret = filter_qgroup(entry, filter_set);
 639                 if (ret)
 640                         sort_tree_insert(sort_tree, entry);
 641
 642                 n = rb_prev(n);
 643         }
 644 }
 645 static int __qgroups_search(int fd, struct qgroup_lookup *qgroup_lookup)
 646 {
 647         int ret;
 648         struct btrfs_ioctl_search_args args;
 649         struct btrfs_ioctl_search_key *sk = &args.key;
 650         struct btrfs_ioctl_search_header *sh;
 651         unsigned long off = 0;
 652         unsigned int i;
 653         int e;
 654         struct btrfs_qgroup_info_item *info;
 655         struct btrfs_qgroup_limit_item *limit;
 656         struct btrfs_qgroup *bq;
 657         struct btrfs_qgroup *bq1;
 658         u64 a1;
 659         u64 a2;
 660         u64 a3;
 661         u64 a4;
 662         u64 a5;
 663
 664         memset(&args, 0, sizeof(args));
 665
 666         sk->tree_id = BTRFS_QUOTA_TREE_OBJECTID;
 667         sk->max_type = BTRFS_QGROUP_RELATION_KEY;
 668         sk->min_type = BTRFS_QGROUP_INFO_KEY;
 669         sk->max_objectid = (u64)-1;
 670         sk->max_offset = (u64)-1;
 671         sk->max_transid = (u64)-1;
 672         sk->nr_items = 4096;
 673
 674         qgroup_lookup_init(qgroup_lookup);
 675
 676         while (1) {
 677                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 678                 e = errno;
 679                 if (ret < 0) {
 680                         fprintf(stderr,
 681                                 "ERROR: can't perform the search - %s\n",
 682                                 strerror(e));
 683                         return ret;
 684                 }
 685                 /* the ioctl returns the number of item it found in nr_items */
 686                 if (sk->nr_items == 0)
 687                         break;
 688
 689                 off = 0;
 690                 /*
 691                  * for each item, pull the key out of the header and then
 692                  * read the root_ref item it contains
 693                  */
 694                 for (i = 0; i < sk->nr_items; i++) {
 695                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 696                                                                   off);
 697                         off += sizeof(*sh);
 698
 699                         if (sh->type == BTRFS_QGROUP_INFO_KEY) {
 700                                 info = (struct btrfs_qgroup_info_item *)
 701                                        (args.buf + off);
 702                                 a1 = btrfs_stack_qgroup_info_generation(info);
 703                                 a2 = btrfs_stack_qgroup_info_referenced(info);
 704                                 a3 =
 705                                   btrfs_stack_qgroup_info_referenced_compressed
 706                                   (info);
 707                                 a4 = btrfs_stack_qgroup_info_exclusive(info);
 708                                 a5 =
 709                                   btrfs_stack_qgroup_info_exclusive_compressed
 710                                   (info);
 711                                 add_qgroup(qgroup_lookup, sh->offset, a1, a2,
 712                                            a3, a4, a5, 0, 0, 0, 0, 0, 0, 0);
 713                         } else if (sh->type == BTRFS_QGROUP_LIMIT_KEY) {
 714                                 limit = (struct btrfs_qgroup_limit_item *)
 715                                     (args.buf + off);
 716
 717                                 a1 = btrfs_stack_qgroup_limit_flags(limit);
 718                                 a2 = btrfs_stack_qgroup_limit_max_referenced
 719                                      (limit);
 720                                 a3 = btrfs_stack_qgroup_limit_max_exclusive
 721                                      (limit);
 722                                 a4 = btrfs_stack_qgroup_limit_rsv_referenced
 723                                      (limit);
 724                                 a5 = btrfs_stack_qgroup_limit_rsv_exclusive
 725                                      (limit);
 726                                 add_qgroup(qgroup_lookup, sh->offset, 0, 0,
 727                                            0, 0, 0, a1, a2, a3, a4, a5, 0, 0);
 728                         } else if (sh->type == BTRFS_QGROUP_RELATION_KEY) {
 729                                 if (sh->offset < sh->objectid)
 730                                         goto skip;
 731                                 bq = qgroup_tree_search(qgroup_lookup,
 732                                                         sh->offset);
 733                                 if (!bq)
 734                                         goto skip;
 735                                 bq1 = qgroup_tree_search(qgroup_lookup,
 736                                                          sh->objectid);
 737                                 if (!bq1)
 738                                         goto skip;
 739                                 add_qgroup(qgroup_lookup, sh->offset, 0, 0,
 740                                            0, 0, 0, 0, 0, 0, 0, 0, bq, bq1);
 741                         } else
 742                                 goto done;
 743 skip:
 744                         off += sh->len;
 745
 746                         /*
 747                          * record the mins in sk so we can make sure the
 748                          * next search doesn't repeat this root
 749                          */
 750                         sk->min_type = sh->type;
 751                         sk->min_offset = sh->offset;
 752                         sk->min_objectid = sh->objectid;
 753                 }
 754                 sk->nr_items = 4096;
 755                 /*
 756                  * this iteration is done, step forward one qgroup for the next
 757                  * ioctl
 758                  */
 759                 if (sk->min_offset < (u64)-1)
 760                         sk->min_offset++;
 761                 else
 762                         break;
 763         }
 764
 765 done:
 766         return ret;
 767 }
 768
 769 static void print_all_qgroups(struct qgroup_lookup *qgroup_lookup)
 770 {
 771
 772         struct rb_node *n;
 773         struct btrfs_qgroup *entry;
 774
 775         n = rb_first(&qgroup_lookup->root);
 776         while (n) {
 777                 entry = rb_entry(n, struct btrfs_qgroup, sort_node);
 778                 print_single_qgroup_default(entry);
 779                 n = rb_next(n);
 780         }
 781 }
 782
 783 int btrfs_show_qgroups(int fd,
 784                        struct btrfs_qgroup_filter_set *filter_set)
 785 {
 786
 787         struct qgroup_lookup qgroup_lookup;
 788         struct qgroup_lookup sort_tree;
 789         int ret;
 790
 791         ret = __qgroups_search(fd, &qgroup_lookup);
 792         if (ret)
 793                 return ret;
 794         __filter_all_qgroups(&qgroup_lookup, &sort_tree,
 795                              filter_set);
 796         print_all_qgroups(&sort_tree);
 797
 798         __free_all_qgroups(&qgroup_lookup);
 799         btrfs_qgroup_free_filter_set(filter_set);
 800         return ret;
 801 }
 802
 803 u64 btrfs_get_path_rootid(int fd)
 804 {
 805         int  ret;
 806         struct btrfs_ioctl_ino_lookup_args args;
 807
 808         memset(&args, 0, sizeof(args));
 809         args.objectid = BTRFS_FIRST_FREE_OBJECTID;
 810
 811         ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
 812         if (ret < 0) {
 813                 fprintf(stderr,
 814                         "ERROR: can't perform the search -%s\n",
 815                         strerror(errno));
 816                 return ret;
 817         }
 818         return args.treeid;
 819 }
 820
 821 u64 parse_qgroupid(char *p)
 822 {
 823         char *s = strchr(p, '/');
 824         char *ptr_src_end = p + strlen(p);
 825         char *ptr_parse_end = NULL;
 826         u64 level;
 827         u64 id;
 828
 829         if (!s) {
 830                 id = strtoull(p, &ptr_parse_end, 10);
 831                 if (ptr_parse_end != ptr_src_end)
 832                         goto err;
 833                 return id;
 834         }
 835         level = strtoull(p, &ptr_parse_end, 10);
 836         if (ptr_parse_end != s)
 837                 goto err;
 838
 839         id = strtoull(s+1, &ptr_parse_end, 10);
 840         if (ptr_parse_end != ptr_src_end)
 841                 goto  err;
 842
 843         return (level << 48) | id;
 844 err:
 845         fprintf(stderr, "ERROR:invalid qgroupid\n");
 846         exit(-1);
 847 }
 848
 849 int qgroup_inherit_size(struct btrfs_qgroup_inherit *p)
 850 {
 851         return sizeof(*p) + sizeof(p->qgroups[0]) *
 852                             (p->num_qgroups + 2 * p->num_ref_copies +
 853                              2 * p->num_excl_copies);
 854 }
 855
 856 static int
 857 qgroup_inherit_realloc(struct btrfs_qgroup_inherit **inherit, int n, int pos)
 858 {
 859         struct btrfs_qgroup_inherit *out;
 860         int nitems = 0;
 861
 862         if (*inherit) {
 863                 nitems = (*inherit)->num_qgroups +
 864                          (*inherit)->num_ref_copies +
 865                          (*inherit)->num_excl_copies;
 866         }
 867
 868         out = calloc(sizeof(*out) + sizeof(out->qgroups[0]) * (nitems + n), 1);
 869         if (out == NULL) {
 870                 fprintf(stderr, "ERROR: Not enough memory\n");
 871                 return 13;
 872         }
 873
 874         if (*inherit) {
 875                 struct btrfs_qgroup_inherit *i = *inherit;
 876                 int s = sizeof(out->qgroups[0]);
 877
 878                 out->num_qgroups = i->num_qgroups;
 879                 out->num_ref_copies = i->num_ref_copies;
 880                 out->num_excl_copies = i->num_excl_copies;
 881                 memcpy(out->qgroups, i->qgroups, pos * s);
 882                 memcpy(out->qgroups + pos + n, i->qgroups + pos,
 883                        (nitems - pos) * s);
 884         }
 885         free(*inherit);
 886         *inherit = out;
 887
 888         return 0;
 889 }
 890
 891 int qgroup_inherit_add_group(struct btrfs_qgroup_inherit **inherit, char *arg)
 892 {
 893         int ret;
 894         u64 qgroupid = parse_qgroupid(arg);
 895         int pos = 0;
 896
 897         if (qgroupid == 0) {
 898                 fprintf(stderr, "ERROR: bad qgroup specification\n");
 899                 return 12;
 900         }
 901
 902         if (*inherit)
 903                 pos = (*inherit)->num_qgroups;
 904         ret = qgroup_inherit_realloc(inherit, 1, pos);
 905         if (ret)
 906                 return ret;
 907
 908         (*inherit)->qgroups[(*inherit)->num_qgroups++] = qgroupid;
 909
 910         return 0;
 911 }
 912
 913 int qgroup_inherit_add_copy(struct btrfs_qgroup_inherit **inherit, char *arg,
 914                             int type)
 915 {
 916         int ret;
 917         u64 qgroup_src;
 918         u64 qgroup_dst;
 919         char *p;
 920         int pos = 0;
 921
 922         p = strchr(arg, ':');
 923         if (!p) {
 924 bad:
 925                 fprintf(stderr, "ERROR: bad copy specification\n");
 926                 return 12;
 927         }
 928         *p = 0;
 929         qgroup_src = parse_qgroupid(arg);
 930         qgroup_dst = parse_qgroupid(p + 1);
 931         *p = ':';
 932
 933         if (!qgroup_src || !qgroup_dst)
 934                 goto bad;
 935
 936         if (*inherit)
 937                 pos = (*inherit)->num_qgroups +
 938                       (*inherit)->num_ref_copies * 2 * type;
 939
 940         ret = qgroup_inherit_realloc(inherit, 2, pos);
 941         if (ret)
 942                 return ret;
 943
 944         (*inherit)->qgroups[pos++] = qgroup_src;
 945         (*inherit)->qgroups[pos++] = qgroup_dst;
 946
 947         if (!type)
 948                 ++(*inherit)->num_ref_copies;
 949         else
 950                 ++(*inherit)->num_excl_copies;
 951
 952         return 0;
 953 }