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