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