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