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_parent(struct btrfs_qgroup *bq, u64 data)
 472 {
 473         struct btrfs_qgroup *qgroup =
 474                 (struct btrfs_qgroup *)(unsigned long)data;
 475
 476         if (data == 0)
 477                 return 0;
 478         if (qgroup->qgroupid == bq->qgroupid)
 479                 return 1;
 480         return 0;
 481 }
 482
 483 static int filter_by_all_parent(struct btrfs_qgroup *bq, u64 data)
 484 {
 485         struct qgroup_lookup lookup;
 486         struct qgroup_lookup *ql = &lookup;
 487         struct btrfs_qgroup_list *list;
 488         struct rb_node *n;
 489         struct btrfs_qgroup *qgroup =
 490                          (struct btrfs_qgroup *)(unsigned long)data;
 491
 492         if (data == 0)
 493                 return 0;
 494         if (bq->qgroupid == qgroup->qgroupid)
 495                 return 1;
 496
 497         qgroup_lookup_init(ql);
 498         filter_all_parent_insert(ql, qgroup);
 499         n = rb_first(&ql->root);
 500         while (n) {
 501                 qgroup = rb_entry(n, struct btrfs_qgroup, all_parent_node);
 502                 if (!list_empty(&qgroup->qgroups)) {
 503                         list_for_each_entry(list, &qgroup->qgroups,
 504                                             next_qgroup) {
 505                                 if ((list->qgroup)->qgroupid == bq->qgroupid)
 506                                         return 1;
 507                                 filter_all_parent_insert(ql, list->qgroup);
 508                         }
 509                 }
 510                 rb_erase(n, &ql->root);
 511                 n = rb_first(&ql->root);
 512         }
 513         return 0;
 514 }
 515
 516 static btrfs_qgroup_filter_func all_filter_funcs[] = {
 517         [BTRFS_QGROUP_FILTER_PARENT]            = filter_by_parent,
 518         [BTRFS_QGROUP_FILTER_ALL_PARENT]        = filter_by_all_parent,
 519 };
 520
 521 struct btrfs_qgroup_filter_set *btrfs_qgroup_alloc_filter_set(void)
 522 {
 523         struct btrfs_qgroup_filter_set *set;
 524         int size;
 525
 526         size = sizeof(struct btrfs_qgroup_filter_set) +
 527                BTRFS_QGROUP_NFILTERS_INCREASE *
 528                sizeof(struct btrfs_qgroup_filter);
 529         set = malloc(size);
 530         if (!set) {
 531                 fprintf(stderr, "memory allocation failed\n");
 532                 exit(1);
 533         }
 534         memset(set, 0, size);
 535         set->total = BTRFS_QGROUP_NFILTERS_INCREASE;
 536
 537         return set;
 538 }
 539
 540 void btrfs_qgroup_free_filter_set(struct btrfs_qgroup_filter_set *filter_set)
 541 {
 542         free(filter_set);
 543 }
 544
 545 int btrfs_qgroup_setup_filter(struct btrfs_qgroup_filter_set **filter_set,
 546                               enum btrfs_qgroup_filter_enum filter, u64 data)
 547 {
 548         struct btrfs_qgroup_filter_set *set = *filter_set;
 549         int size;
 550
 551         BUG_ON(!set);
 552         BUG_ON(filter >= BTRFS_QGROUP_FILTER_MAX);
 553         BUG_ON(set->nfilters > set->total);
 554
 555         if (set->nfilters == set->total) {
 556                 size = set->total + BTRFS_QGROUP_NFILTERS_INCREASE;
 557                 size = sizeof(*set) + size * sizeof(struct btrfs_qgroup_filter);
 558
 559                 set = realloc(set, size);
 560                 if (!set) {
 561                         fprintf(stderr, "memory allocation failed\n");
 562                         exit(1);
 563                 }
 564                 memset(&set->filters[set->total], 0,
 565                        BTRFS_QGROUP_NFILTERS_INCREASE *
 566                        sizeof(struct btrfs_qgroup_filter));
 567                 set->total += BTRFS_QGROUP_NFILTERS_INCREASE;
 568                 *filter_set = set;
 569         }
 570         BUG_ON(set->filters[set->nfilters].filter_func);
 571         set->filters[set->nfilters].filter_func = all_filter_funcs[filter];
 572         set->filters[set->nfilters].data = data;
 573         set->nfilters++;
 574         return 0;
 575 }
 576
 577 static int filter_qgroup(struct btrfs_qgroup *bq,
 578                          struct btrfs_qgroup_filter_set *set)
 579 {
 580         int i, ret;
 581
 582         if (!set || !set->nfilters)
 583                 return 1;
 584         for (i = 0; i < set->nfilters; i++) {
 585                 if (!set->filters[i].filter_func)
 586                         break;
 587                 ret = set->filters[i].filter_func(bq, set->filters[i].data);
 588                 if (!ret)
 589                         return 0;
 590         }
 591         return 1;
 592 }
 593
 594 static void pre_process_filter_set(struct qgroup_lookup *lookup,
 595                                    struct btrfs_qgroup_filter_set *set)
 596 {
 597         int i;
 598         struct btrfs_qgroup *qgroup_for_filter = NULL;
 599
 600         for (i = 0; i < set->nfilters; i++) {
 601
 602                 if (set->filters[i].filter_func == filter_by_all_parent
 603                     || set->filters[i].filter_func == filter_by_parent) {
 604                         qgroup_for_filter = qgroup_tree_search(lookup,
 605                                             set->filters[i].data);
 606                         set->filters[i].data =
 607                                  (u64)(unsigned long)qgroup_for_filter;
 608                 }
 609         }
 610 }
 611
 612 static int sort_tree_insert(struct qgroup_lookup *sort_tree,
 613                             struct btrfs_qgroup *bq)
 614 {
 615         struct rb_node **p = &sort_tree->root.rb_node;
 616         struct rb_node *parent = NULL;
 617         struct btrfs_qgroup *curr;
 618         int ret;
 619
 620         while (*p) {
 621                 parent = *p;
 622                 curr = rb_entry(parent, struct btrfs_qgroup, sort_node);
 623
 624                 ret = comp_entry_with_qgroupid(bq, curr, 0);
 625                 if (ret < 0)
 626                         p = &(*p)->rb_left;
 627                 else if (ret > 0)
 628                         p = &(*p)->rb_right;
 629                 else
 630                         return -EEXIST;
 631         }
 632         rb_link_node(&bq->sort_node, parent, p);
 633         rb_insert_color(&bq->sort_node, &sort_tree->root);
 634         return 0;
 635 }
 636
 637 static void __filter_all_qgroups(struct qgroup_lookup *all_qgroups,
 638                                  struct qgroup_lookup *sort_tree,
 639                                  struct btrfs_qgroup_filter_set *filter_set)
 640 {
 641         struct rb_node *n;
 642         struct btrfs_qgroup *entry;
 643         int ret;
 644
 645         qgroup_lookup_init(sort_tree);
 646         pre_process_filter_set(all_qgroups, filter_set);
 647
 648         n = rb_last(&all_qgroups->root);
 649         while (n) {
 650                 entry = rb_entry(n, struct btrfs_qgroup, rb_node);
 651
 652                 ret = filter_qgroup(entry, filter_set);
 653                 if (ret)
 654                         sort_tree_insert(sort_tree, entry);
 655
 656                 n = rb_prev(n);
 657         }
 658 }
 659 static int __qgroups_search(int fd, struct qgroup_lookup *qgroup_lookup)
 660 {
 661         int ret;
 662         struct btrfs_ioctl_search_args args;
 663         struct btrfs_ioctl_search_key *sk = &args.key;
 664         struct btrfs_ioctl_search_header *sh;
 665         unsigned long off = 0;
 666         unsigned int i;
 667         int e;
 668         struct btrfs_qgroup_info_item *info;
 669         struct btrfs_qgroup_limit_item *limit;
 670         struct btrfs_qgroup *bq;
 671         struct btrfs_qgroup *bq1;
 672         u64 a1;
 673         u64 a2;
 674         u64 a3;
 675         u64 a4;
 676         u64 a5;
 677
 678         memset(&args, 0, sizeof(args));
 679
 680         sk->tree_id = BTRFS_QUOTA_TREE_OBJECTID;
 681         sk->max_type = BTRFS_QGROUP_RELATION_KEY;
 682         sk->min_type = BTRFS_QGROUP_INFO_KEY;
 683         sk->max_objectid = (u64)-1;
 684         sk->max_offset = (u64)-1;
 685         sk->max_transid = (u64)-1;
 686         sk->nr_items = 4096;
 687
 688         qgroup_lookup_init(qgroup_lookup);
 689
 690         while (1) {
 691                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 692                 e = errno;
 693                 if (ret < 0) {
 694                         fprintf(stderr,
 695                                 "ERROR: can't perform the search - %s\n",
 696                                 strerror(e));
 697                         return ret;
 698                 }
 699                 /* the ioctl returns the number of item it found in nr_items */
 700                 if (sk->nr_items == 0)
 701                         break;
 702
 703                 off = 0;
 704                 /*
 705                  * for each item, pull the key out of the header and then
 706                  * read the root_ref item it contains
 707                  */
 708                 for (i = 0; i < sk->nr_items; i++) {
 709                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 710                                                                   off);
 711                         off += sizeof(*sh);
 712
 713                         if (sh->type == BTRFS_QGROUP_INFO_KEY) {
 714                                 info = (struct btrfs_qgroup_info_item *)
 715                                        (args.buf + off);
 716                                 a1 = btrfs_stack_qgroup_info_generation(info);
 717                                 a2 = btrfs_stack_qgroup_info_referenced(info);
 718                                 a3 =
 719                                   btrfs_stack_qgroup_info_referenced_compressed
 720                                   (info);
 721                                 a4 = btrfs_stack_qgroup_info_exclusive(info);
 722                                 a5 =
 723                                   btrfs_stack_qgroup_info_exclusive_compressed
 724                                   (info);
 725                                 add_qgroup(qgroup_lookup, sh->offset, a1, a2,
 726                                            a3, a4, a5, 0, 0, 0, 0, 0, 0, 0);
 727                         } else if (sh->type == BTRFS_QGROUP_LIMIT_KEY) {
 728                                 limit = (struct btrfs_qgroup_limit_item *)
 729                                     (args.buf + off);
 730
 731                                 a1 = btrfs_stack_qgroup_limit_flags(limit);
 732                                 a2 = btrfs_stack_qgroup_limit_max_referenced
 733                                      (limit);
 734                                 a3 = btrfs_stack_qgroup_limit_max_exclusive
 735                                      (limit);
 736                                 a4 = btrfs_stack_qgroup_limit_rsv_referenced
 737                                      (limit);
 738                                 a5 = btrfs_stack_qgroup_limit_rsv_exclusive
 739                                      (limit);
 740                                 add_qgroup(qgroup_lookup, sh->offset, 0, 0,
 741                                            0, 0, 0, a1, a2, a3, a4, a5, 0, 0);
 742                         } else if (sh->type == BTRFS_QGROUP_RELATION_KEY) {
 743                                 if (sh->offset < sh->objectid)
 744                                         goto skip;
 745                                 bq = qgroup_tree_search(qgroup_lookup,
 746                                                         sh->offset);
 747                                 if (!bq)
 748                                         goto skip;
 749                                 bq1 = qgroup_tree_search(qgroup_lookup,
 750                                                          sh->objectid);
 751                                 if (!bq1)
 752                                         goto skip;
 753                                 add_qgroup(qgroup_lookup, sh->offset, 0, 0,
 754                                            0, 0, 0, 0, 0, 0, 0, 0, bq, bq1);
 755                         } else
 756                                 goto done;
 757 skip:
 758                         off += sh->len;
 759
 760                         /*
 761                          * record the mins in sk so we can make sure the
 762                          * next search doesn't repeat this root
 763                          */
 764                         sk->min_type = sh->type;
 765                         sk->min_offset = sh->offset;
 766                         sk->min_objectid = sh->objectid;
 767                 }
 768                 sk->nr_items = 4096;
 769                 /*
 770                  * this iteration is done, step forward one qgroup for the next
 771                  * ioctl
 772                  */
 773                 if (sk->min_offset < (u64)-1)
 774                         sk->min_offset++;
 775                 else
 776                         break;
 777         }
 778
 779 done:
 780         return ret;
 781 }
 782
 783 static void print_all_qgroups(struct qgroup_lookup *qgroup_lookup)
 784 {
 785
 786         struct rb_node *n;
 787         struct btrfs_qgroup *entry;
 788
 789         n = rb_first(&qgroup_lookup->root);
 790         while (n) {
 791                 entry = rb_entry(n, struct btrfs_qgroup, sort_node);
 792                 print_single_qgroup_default(entry);
 793                 n = rb_next(n);
 794         }
 795 }
 796
 797 int btrfs_show_qgroups(int fd,
 798                        struct btrfs_qgroup_filter_set *filter_set)
 799 {
 800
 801         struct qgroup_lookup qgroup_lookup;
 802         struct qgroup_lookup sort_tree;
 803         int ret;
 804
 805         ret = __qgroups_search(fd, &qgroup_lookup);
 806         if (ret)
 807                 return ret;
 808         __filter_all_qgroups(&qgroup_lookup, &sort_tree,
 809                              filter_set);
 810         print_all_qgroups(&sort_tree);
 811
 812         __free_all_qgroups(&qgroup_lookup);
 813         btrfs_qgroup_free_filter_set(filter_set);
 814         return ret;
 815 }
 816
 817 u64 btrfs_get_path_rootid(int fd)
 818 {
 819         int  ret;
 820         struct btrfs_ioctl_ino_lookup_args args;
 821
 822         memset(&args, 0, sizeof(args));
 823         args.objectid = BTRFS_FIRST_FREE_OBJECTID;
 824
 825         ret = ioctl(fd, BTRFS_IOC_INO_LOOKUP, &args);
 826         if (ret < 0) {
 827                 fprintf(stderr,
 828                         "ERROR: can't perform the search -%s\n",
 829                         strerror(errno));
 830                 return ret;
 831         }
 832         return args.treeid;
 833 }
 834
 835 u64 parse_qgroupid(char *p)
 836 {
 837         char *s = strchr(p, '/');
 838         char *ptr_src_end = p + strlen(p);
 839         char *ptr_parse_end = NULL;
 840         u64 level;
 841         u64 id;
 842
 843         if (!s) {
 844                 id = strtoull(p, &ptr_parse_end, 10);
 845                 if (ptr_parse_end != ptr_src_end)
 846                         goto err;
 847                 return id;
 848         }
 849         level = strtoull(p, &ptr_parse_end, 10);
 850         if (ptr_parse_end != s)
 851                 goto err;
 852
 853         id = strtoull(s+1, &ptr_parse_end, 10);
 854         if (ptr_parse_end != ptr_src_end)
 855                 goto  err;
 856
 857         return (level << 48) | id;
 858 err:
 859         fprintf(stderr, "ERROR:invalid qgroupid\n");
 860         exit(-1);
 861 }
 862
 863 int qgroup_inherit_size(struct btrfs_qgroup_inherit *p)
 864 {
 865         return sizeof(*p) + sizeof(p->qgroups[0]) *
 866                             (p->num_qgroups + 2 * p->num_ref_copies +
 867                              2 * p->num_excl_copies);
 868 }
 869
 870 static int
 871 qgroup_inherit_realloc(struct btrfs_qgroup_inherit **inherit, int n, int pos)
 872 {
 873         struct btrfs_qgroup_inherit *out;
 874         int nitems = 0;
 875
 876         if (*inherit) {
 877                 nitems = (*inherit)->num_qgroups +
 878                          (*inherit)->num_ref_copies +
 879                          (*inherit)->num_excl_copies;
 880         }
 881
 882         out = calloc(sizeof(*out) + sizeof(out->qgroups[0]) * (nitems + n), 1);
 883         if (out == NULL) {
 884                 fprintf(stderr, "ERROR: Not enough memory\n");
 885                 return 13;
 886         }
 887
 888         if (*inherit) {
 889                 struct btrfs_qgroup_inherit *i = *inherit;
 890                 int s = sizeof(out->qgroups[0]);
 891
 892                 out->num_qgroups = i->num_qgroups;
 893                 out->num_ref_copies = i->num_ref_copies;
 894                 out->num_excl_copies = i->num_excl_copies;
 895                 memcpy(out->qgroups, i->qgroups, pos * s);
 896                 memcpy(out->qgroups + pos + n, i->qgroups + pos,
 897                        (nitems - pos) * s);
 898         }
 899         free(*inherit);
 900         *inherit = out;
 901
 902         return 0;
 903 }
 904
 905 int qgroup_inherit_add_group(struct btrfs_qgroup_inherit **inherit, char *arg)
 906 {
 907         int ret;
 908         u64 qgroupid = parse_qgroupid(arg);
 909         int pos = 0;
 910
 911         if (qgroupid == 0) {
 912                 fprintf(stderr, "ERROR: bad qgroup specification\n");
 913                 return 12;
 914         }
 915
 916         if (*inherit)
 917                 pos = (*inherit)->num_qgroups;
 918         ret = qgroup_inherit_realloc(inherit, 1, pos);
 919         if (ret)
 920                 return ret;
 921
 922         (*inherit)->qgroups[(*inherit)->num_qgroups++] = qgroupid;
 923
 924         return 0;
 925 }
 926
 927 int qgroup_inherit_add_copy(struct btrfs_qgroup_inherit **inherit, char *arg,
 928                             int type)
 929 {
 930         int ret;
 931         u64 qgroup_src;
 932         u64 qgroup_dst;
 933         char *p;
 934         int pos = 0;
 935
 936         p = strchr(arg, ':');
 937         if (!p) {
 938 bad:
 939                 fprintf(stderr, "ERROR: bad copy specification\n");
 940                 return 12;
 941         }
 942         *p = 0;
 943         qgroup_src = parse_qgroupid(arg);
 944         qgroup_dst = parse_qgroupid(p + 1);
 945         *p = ':';
 946
 947         if (!qgroup_src || !qgroup_dst)
 948                 goto bad;
 949
 950         if (*inherit)
 951                 pos = (*inherit)->num_qgroups +
 952                       (*inherit)->num_ref_copies * 2 * type;
 953
 954         ret = qgroup_inherit_realloc(inherit, 2, pos);
 955         if (ret)
 956                 return ret;
 957
 958         (*inherit)->qgroups[pos++] = qgroup_src;
 959         (*inherit)->qgroups[pos++] = qgroup_dst;
 960
 961         if (!type)
 962                 ++(*inherit)->num_ref_copies;
 963         else
 964                 ++(*inherit)->num_excl_copies;
 965
 966         return 0;
 967 }