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