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