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