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
  24 struct qgroup_lookup {
  25         struct rb_root root;
  26 };
  27
  28 struct btrfs_qgroup {
  29         struct rb_node rb_node;
  30         u64 qgroupid;
  31
  32         /*
  33          * info_item
  34          */
  35         u64 generation;
  36         u64 rfer;       /*referenced*/
  37         u64 rfer_cmpr;  /*referenced compressed*/
  38         u64 excl;       /*exclusive*/
  39         u64 excl_cmpr;  /*exclusive compressed*/
  40
  41         /*
  42          *limit_item
  43          */
  44         u64 flags;      /*which limits are set*/
  45         u64 max_rfer;
  46         u64 max_excl;
  47         u64 rsv_rfer;
  48         u64 rsv_excl;
  49
  50         /*qgroups this group is member of*/
  51         struct list_head qgroups;
  52         /*qgroups that are members of this group*/
  53         struct list_head members;
  54 };
  55
  56 /*
  57  * glue structure to represent the relations
  58  * between qgroups
  59  */
  60 struct btrfs_qgroup_list {
  61         struct list_head next_qgroup;
  62         struct list_head next_member;
  63         struct btrfs_qgroup *qgroup;
  64         struct btrfs_qgroup *member;
  65 };
  66
  67 /*
  68  * qgroupid,rfer,excl default to set
  69  */
  70 struct {
  71         char *name;
  72         char *column_name;
  73         int need_print;
  74 } btrfs_qgroup_columns[] = {
  75         {
  76                 .name           = "qgroupid",
  77                 .column_name    = "Qgroupid",
  78                 .need_print     = 1,
  79         },
  80         {
  81                 .name           = "rfer",
  82                 .column_name    = "Rfer",
  83                 .need_print     = 1,
  84         },
  85         {
  86                 .name           = "excl",
  87                 .column_name    = "Excl",
  88                 .need_print     = 1,
  89         },
  90         {
  91                 .name           = "parent",
  92                 .column_name    = "Parent",
  93                 .need_print     = 0,
  94         },
  95         {
  96                 .name           = NULL,
  97                 .column_name    = NULL,
  98                 .need_print     = 0,
  99         },
 100 };
 101
 102 void btrfs_qgroup_setup_print_column(enum btrfs_qgroup_column_enum column)
 103 {
 104         int i;
 105
 106         BUG_ON(column < 0 || column > BTRFS_QGROUP_ALL);
 107
 108         if (column < BTRFS_QGROUP_ALL) {
 109                 btrfs_qgroup_columns[column].need_print = 1;
 110                 return;
 111         }
 112         for (i = 0; i < BTRFS_QGROUP_ALL; i++)
 113                 btrfs_qgroup_columns[i].need_print = 1;
 114 }
 115
 116 static void print_parent_column(struct btrfs_qgroup *qgroup)
 117 {
 118         struct btrfs_qgroup_list *list = NULL;
 119
 120         list_for_each_entry(list, &qgroup->qgroups, next_qgroup) {
 121                 printf("%llu/%llu", (list->qgroup)->qgroupid >> 48,
 122                       ((1ll << 48) - 1) & (list->qgroup)->qgroupid);
 123                 if (!list_is_last(&list->next_qgroup, &qgroup->qgroups))
 124                         printf(",");
 125         }
 126         if (list_empty(&qgroup->qgroups))
 127                 printf("---");
 128 }
 129
 130 static void print_qgroup_column(struct btrfs_qgroup *qgroup,
 131                                 enum btrfs_qgroup_column_enum column)
 132 {
 133         BUG_ON(column >= BTRFS_QGROUP_ALL || column < 0);
 134
 135         switch (column) {
 136
 137         case BTRFS_QGROUP_QGROUPID:
 138                 printf("%llu/%llu", qgroup->qgroupid >> 48,
 139                        ((1ll << 48) - 1) & qgroup->qgroupid);
 140                 break;
 141         case BTRFS_QGROUP_RFER:
 142                 printf("%lld", qgroup->rfer);
 143                 break;
 144         case BTRFS_QGROUP_EXCL:
 145                 printf("%lld", qgroup->excl);
 146                 break;
 147         case BTRFS_QGROUP_PARENT:
 148                 print_parent_column(qgroup);
 149                 break;
 150         default:
 151                 break;
 152         }
 153 }
 154
 155 static void print_single_qgroup_default(struct btrfs_qgroup *qgroup)
 156 {
 157         int i;
 158
 159         for (i = 0; i < BTRFS_QGROUP_ALL; i++) {
 160                 if (!btrfs_qgroup_columns[i].need_print)
 161                         continue;
 162                 print_qgroup_column(qgroup, i);
 163
 164                 if (i != BTRFS_QGROUP_ALL - 1)
 165                         printf(" ");
 166         }
 167         printf("\n");
 168 }
 169
 170 static void qgroup_lookup_init(struct qgroup_lookup *tree)
 171 {
 172         tree->root.rb_node = NULL;
 173 }
 174
 175 static int comp_entry_with_qgroupid(struct btrfs_qgroup *entry1,
 176                                     struct btrfs_qgroup *entry2,
 177                                     int is_descending)
 178 {
 179
 180         int ret;
 181
 182         if (entry1->qgroupid > entry2->qgroupid)
 183                 ret = 1;
 184         else if (entry1->qgroupid < entry2->qgroupid)
 185                 ret = -1;
 186         else
 187                 ret = 0;
 188
 189         return is_descending ? -ret : ret;
 190 }
 191
 192 /*
 193  * insert a new root into the tree.  returns the existing root entry
 194  * if one is already there.  qgroupid is used
 195  * as the key
 196  */
 197 static int qgroup_tree_insert(struct qgroup_lookup *root_tree,
 198                               struct btrfs_qgroup *ins)
 199 {
 200
 201         struct rb_node **p = &root_tree->root.rb_node;
 202         struct rb_node *parent = NULL;
 203         struct btrfs_qgroup *curr;
 204         int ret;
 205
 206         while (*p) {
 207                 parent = *p;
 208                 curr = rb_entry(parent, struct btrfs_qgroup, rb_node);
 209
 210                 ret = comp_entry_with_qgroupid(ins, curr, 0);
 211                 if (ret < 0)
 212                         p = &(*p)->rb_left;
 213                 else if (ret > 0)
 214                         p = &(*p)->rb_right;
 215                 else
 216                         return -EEXIST;
 217         }
 218         rb_link_node(&ins->rb_node, parent, p);
 219         rb_insert_color(&ins->rb_node, &root_tree->root);
 220         return 0;
 221 }
 222
 223 /*
 224  *find a given qgroupid in the tree. We return the smallest one,
 225  *rb_next can be used to move forward looking for more if required
 226  */
 227 static struct btrfs_qgroup *qgroup_tree_search(struct qgroup_lookup *root_tree,
 228                                                u64 qgroupid)
 229 {
 230         struct rb_node *n = root_tree->root.rb_node;
 231         struct btrfs_qgroup *entry;
 232         struct btrfs_qgroup tmp;
 233         int ret;
 234
 235         tmp.qgroupid = qgroupid;
 236
 237         while (n) {
 238                 entry = rb_entry(n, struct btrfs_qgroup, rb_node);
 239
 240                 ret = comp_entry_with_qgroupid(&tmp, entry, 0);
 241                 if (ret < 0)
 242                         n = n->rb_left;
 243                 else if (ret > 0)
 244                         n = n->rb_right;
 245                 else
 246                         return entry;
 247
 248         }
 249         return NULL;
 250 }
 251
 252 static int update_qgroup(struct qgroup_lookup *qgroup_lookup, u64 qgroupid,
 253                          u64 generation, u64 rfer, u64 rfer_cmpr, u64 excl,
 254                          u64 excl_cmpr, u64 flags, u64 max_rfer, u64 max_excl,
 255                          u64 rsv_rfer, u64 rsv_excl, struct btrfs_qgroup *pa,
 256                          struct btrfs_qgroup *child)
 257 {
 258         struct btrfs_qgroup *bq;
 259         struct btrfs_qgroup_list *list;
 260
 261         bq = qgroup_tree_search(qgroup_lookup, qgroupid);
 262         if (!bq || bq->qgroupid != qgroupid)
 263                 return -ENOENT;
 264
 265         if (generation)
 266                 bq->generation = generation;
 267         if (rfer)
 268                 bq->rfer = rfer;
 269         if (rfer_cmpr)
 270                 bq->rfer_cmpr = rfer_cmpr;
 271         if (excl)
 272                 bq->excl = excl;
 273         if (excl_cmpr)
 274                 bq->excl_cmpr = excl_cmpr;
 275         if (flags)
 276                 bq->flags = flags;
 277         if (max_rfer)
 278                 bq->max_rfer = max_rfer;
 279         if (max_excl)
 280                 bq->max_excl = max_excl;
 281         if (rsv_rfer)
 282                 bq->rsv_rfer = rsv_rfer;
 283         if (pa && child) {
 284                 list = malloc(sizeof(*list));
 285                 if (!list) {
 286                         fprintf(stderr, "memory allocation failed\n");
 287                         exit(1);
 288                 }
 289                 list->qgroup = pa;
 290                 list->member = child;
 291                 list_add_tail(&list->next_qgroup, &child->qgroups);
 292                 list_add_tail(&list->next_member, &pa->members);
 293         }
 294         return 0;
 295 }
 296
 297 static int add_qgroup(struct qgroup_lookup *qgroup_lookup, u64 qgroupid,
 298                       u64 generation, u64 rfer, u64 rfer_cmpr, u64 excl,
 299                       u64 excl_cmpr, u64 flags, u64 max_rfer, u64 max_excl,
 300                       u64 rsv_rfer, u64 rsv_excl, struct btrfs_qgroup *parent,
 301                       struct btrfs_qgroup *child)
 302 {
 303         struct btrfs_qgroup *bq;
 304         struct btrfs_qgroup_list *list;
 305         int ret;
 306
 307         ret = update_qgroup(qgroup_lookup, qgroupid, generation, rfer,
 308                             rfer_cmpr, excl, excl_cmpr, flags, max_rfer,
 309                             max_excl, rsv_rfer, rsv_excl, parent, child);
 310         if (!ret)
 311                 return 0;
 312
 313         bq = malloc(sizeof(*bq));
 314         if (!bq) {
 315                 printf("memory allocation failed\n");
 316                 exit(1);
 317         }
 318         memset(bq, 0, sizeof(*bq));
 319         if (qgroupid) {
 320                 bq->qgroupid = qgroupid;
 321                 INIT_LIST_HEAD(&bq->qgroups);
 322                 INIT_LIST_HEAD(&bq->members);
 323         }
 324         if (generation)
 325                 bq->generation = generation;
 326         if (rfer)
 327                 bq->rfer = rfer;
 328         if (rfer_cmpr)
 329                 bq->rfer_cmpr = rfer_cmpr;
 330         if (excl)
 331                 bq->excl = excl;
 332         if (excl_cmpr)
 333                 bq->excl_cmpr = excl_cmpr;
 334         if (flags)
 335                 bq->flags = flags;
 336         if (max_rfer)
 337                 bq->max_rfer = max_rfer;
 338         if (max_excl)
 339                 bq->max_excl = max_excl;
 340         if (rsv_rfer)
 341                 bq->rsv_rfer = rsv_rfer;
 342         if (parent && child) {
 343                 list = malloc(sizeof(*list));
 344                 if (!list) {
 345                         fprintf(stderr, "memory allocation failed\n");
 346                         exit(1);
 347                 }
 348                 list->qgroup = parent;
 349                 list->member = child;
 350                 list_add_tail(&list->next_qgroup, &child->qgroups);
 351                 list_add_tail(&list->next_member, &parent->members);
 352         }
 353         ret = qgroup_tree_insert(qgroup_lookup, bq);
 354         if (ret) {
 355                 printf("failed to insert tree %llu\n",
 356                        bq->qgroupid);
 357                 exit(1);
 358         }
 359         return ret;
 360 }
 361
 362 void __free_btrfs_qgroup(struct btrfs_qgroup *bq)
 363 {
 364         struct btrfs_qgroup_list *list;
 365         while (!list_empty(&bq->qgroups)) {
 366                 list = list_entry((&bq->qgroups)->next,
 367                                   struct btrfs_qgroup_list,
 368                                   next_qgroup);
 369                 list_del(&list->next_qgroup);
 370                 list_del(&list->next_member);
 371                 free(list);
 372         }
 373         while (!list_empty(&bq->members)) {
 374                 list = list_entry((&bq->members)->next,
 375                                   struct btrfs_qgroup_list,
 376                                   next_member);
 377                 list_del(&list->next_qgroup);
 378                 list_del(&list->next_member);
 379                 free(list);
 380         }
 381         free(bq);
 382 }
 383
 384 void __free_all_qgroups(struct qgroup_lookup *root_tree)
 385 {
 386         struct btrfs_qgroup *entry;
 387         struct rb_node *n;
 388
 389         n = rb_first(&root_tree->root);
 390         while (n) {
 391                 entry = rb_entry(n, struct btrfs_qgroup, rb_node);
 392                 rb_erase(n, &root_tree->root);
 393                 __free_btrfs_qgroup(entry);
 394
 395                 n = rb_first(&root_tree->root);
 396         }
 397 }
 398
 399 static int __qgroups_search(int fd, struct qgroup_lookup *qgroup_lookup)
 400 {
 401         int ret;
 402         struct btrfs_ioctl_search_args args;
 403         struct btrfs_ioctl_search_key *sk = &args.key;
 404         struct btrfs_ioctl_search_header *sh;
 405         unsigned long off = 0;
 406         unsigned int i;
 407         int e;
 408         struct btrfs_qgroup_info_item *info;
 409         struct btrfs_qgroup_limit_item *limit;
 410         struct btrfs_qgroup *bq;
 411         struct btrfs_qgroup *bq1;
 412         u64 a1;
 413         u64 a2;
 414         u64 a3;
 415         u64 a4;
 416         u64 a5;
 417
 418         memset(&args, 0, sizeof(args));
 419
 420         sk->tree_id = BTRFS_QUOTA_TREE_OBJECTID;
 421         sk->max_type = BTRFS_QGROUP_RELATION_KEY;
 422         sk->min_type = BTRFS_QGROUP_INFO_KEY;
 423         sk->max_objectid = (u64)-1;
 424         sk->max_offset = (u64)-1;
 425         sk->max_transid = (u64)-1;
 426         sk->nr_items = 4096;
 427
 428         qgroup_lookup_init(qgroup_lookup);
 429
 430         while (1) {
 431                 ret = ioctl(fd, BTRFS_IOC_TREE_SEARCH, &args);
 432                 e = errno;
 433                 if (ret < 0) {
 434                         fprintf(stderr,
 435                                 "ERROR: can't perform the search - %s\n",
 436                                 strerror(e));
 437                         return ret;
 438                 }
 439                 /* the ioctl returns the number of item it found in nr_items */
 440                 if (sk->nr_items == 0)
 441                         break;
 442
 443                 off = 0;
 444                 /*
 445                  * for each item, pull the key out of the header and then
 446                  * read the root_ref item it contains
 447                  */
 448                 for (i = 0; i < sk->nr_items; i++) {
 449                         sh = (struct btrfs_ioctl_search_header *)(args.buf +
 450                                                                   off);
 451                         off += sizeof(*sh);
 452
 453                         if (sh->type == BTRFS_QGROUP_INFO_KEY) {
 454                                 info = (struct btrfs_qgroup_info_item *)
 455                                        (args.buf + off);
 456                                 a1 = btrfs_stack_qgroup_info_generation(info);
 457                                 a2 = btrfs_stack_qgroup_info_referenced(info);
 458                                 a3 =
 459                                   btrfs_stack_qgroup_info_referenced_compressed
 460                                   (info);
 461                                 a4 = btrfs_stack_qgroup_info_exclusive(info);
 462                                 a5 =
 463                                   btrfs_stack_qgroup_info_exclusive_compressed
 464                                   (info);
 465                                 add_qgroup(qgroup_lookup, sh->offset, a1, a2,
 466                                            a3, a4, a5, 0, 0, 0, 0, 0, 0, 0);
 467                         } else if (sh->type == BTRFS_QGROUP_LIMIT_KEY) {
 468                                 limit = (struct btrfs_qgroup_limit_item *)
 469                                     (args.buf + off);
 470
 471                                 a1 = btrfs_stack_qgroup_limit_flags(limit);
 472                                 a2 = btrfs_stack_qgroup_limit_max_referenced
 473                                      (limit);
 474                                 a3 = btrfs_stack_qgroup_limit_max_exclusive
 475                                      (limit);
 476                                 a4 = btrfs_stack_qgroup_limit_rsv_referenced
 477                                      (limit);
 478                                 a5 = btrfs_stack_qgroup_limit_rsv_exclusive
 479                                      (limit);
 480                                 add_qgroup(qgroup_lookup, sh->offset, 0, 0,
 481                                            0, 0, 0, a1, a2, a3, a4, a5, 0, 0);
 482                         } else if (sh->type == BTRFS_QGROUP_RELATION_KEY) {
 483                                 if (sh->offset < sh->objectid)
 484                                         goto skip;
 485                                 bq = qgroup_tree_search(qgroup_lookup,
 486                                                         sh->offset);
 487                                 if (!bq)
 488                                         goto skip;
 489                                 bq1 = qgroup_tree_search(qgroup_lookup,
 490                                                          sh->objectid);
 491                                 if (!bq1)
 492                                         goto skip;
 493                                 add_qgroup(qgroup_lookup, sh->offset, 0, 0,
 494                                            0, 0, 0, 0, 0, 0, 0, 0, bq, bq1);
 495                         } else
 496                                 goto done;
 497 skip:
 498                         off += sh->len;
 499
 500                         /*
 501                          * record the mins in sk so we can make sure the
 502                          * next search doesn't repeat this root
 503                          */
 504                         sk->min_type = sh->type;
 505                         sk->min_offset = sh->offset;
 506                         sk->min_objectid = sh->objectid;
 507                 }
 508                 sk->nr_items = 4096;
 509                 /*
 510                  * this iteration is done, step forward one qgroup for the next
 511                  * ioctl
 512                  */
 513                 if (sk->min_offset < (u64)-1)
 514                         sk->min_offset++;
 515                 else
 516                         break;
 517         }
 518
 519 done:
 520         return ret;
 521 }
 522
 523 static void print_all_qgroups(struct qgroup_lookup *qgroup_lookup)
 524 {
 525
 526         struct rb_node *n;
 527         struct btrfs_qgroup *entry;
 528
 529         n = rb_first(&qgroup_lookup->root);
 530         while (n) {
 531                 entry = rb_entry(n, struct btrfs_qgroup, rb_node);
 532                 print_single_qgroup_default(entry);
 533                 n = rb_next(n);
 534         }
 535 }
 536
 537 int btrfs_show_qgroups(int fd)
 538 {
 539
 540         struct qgroup_lookup qgroup_lookup;
 541         int ret;
 542
 543         ret = __qgroups_search(fd, &qgroup_lookup);
 544         if (ret)
 545                 return ret;
 546
 547         print_all_qgroups(&qgroup_lookup);
 548         __free_all_qgroups(&qgroup_lookup);
 549
 550         return ret;
 551 }
 552
 553 u64 parse_qgroupid(char *p)
 554 {
 555         char *s = strchr(p, '/');
 556         char *ptr_src_end = p + strlen(p);
 557         char *ptr_parse_end = NULL;
 558         u64 level;
 559         u64 id;
 560
 561         if (!s) {
 562                 id = strtoull(p, &ptr_parse_end, 10);
 563                 if (ptr_parse_end != ptr_src_end)
 564                         goto err;
 565                 return id;
 566         }
 567         level = strtoull(p, &ptr_parse_end, 10);
 568         if (ptr_parse_end != s)
 569                 goto err;
 570
 571         id = strtoull(s+1, &ptr_parse_end, 10);
 572         if (ptr_parse_end != ptr_src_end)
 573                 goto  err;
 574
 575         return (level << 48) | id;
 576 err:
 577         fprintf(stderr, "ERROR:invalid qgroupid\n");
 578         exit(-1);
 579 }
 580
 581 int qgroup_inherit_size(struct btrfs_qgroup_inherit *p)
 582 {
 583         return sizeof(*p) + sizeof(p->qgroups[0]) *
 584                             (p->num_qgroups + 2 * p->num_ref_copies +
 585                              2 * p->num_excl_copies);
 586 }
 587
 588 static int
 589 qgroup_inherit_realloc(struct btrfs_qgroup_inherit **inherit, int n, int pos)
 590 {
 591         struct btrfs_qgroup_inherit *out;
 592         int nitems = 0;
 593
 594         if (*inherit) {
 595                 nitems = (*inherit)->num_qgroups +
 596                          (*inherit)->num_ref_copies +
 597                          (*inherit)->num_excl_copies;
 598         }
 599
 600         out = calloc(sizeof(*out) + sizeof(out->qgroups[0]) * (nitems + n), 1);
 601         if (out == NULL) {
 602                 fprintf(stderr, "ERROR: Not enough memory\n");
 603                 return 13;
 604         }
 605
 606         if (*inherit) {
 607                 struct btrfs_qgroup_inherit *i = *inherit;
 608                 int s = sizeof(out->qgroups[0]);
 609
 610                 out->num_qgroups = i->num_qgroups;
 611                 out->num_ref_copies = i->num_ref_copies;
 612                 out->num_excl_copies = i->num_excl_copies;
 613                 memcpy(out->qgroups, i->qgroups, pos * s);
 614                 memcpy(out->qgroups + pos + n, i->qgroups + pos,
 615                        (nitems - pos) * s);
 616         }
 617         free(*inherit);
 618         *inherit = out;
 619
 620         return 0;
 621 }
 622
 623 int qgroup_inherit_add_group(struct btrfs_qgroup_inherit **inherit, char *arg)
 624 {
 625         int ret;
 626         u64 qgroupid = parse_qgroupid(arg);
 627         int pos = 0;
 628
 629         if (qgroupid == 0) {
 630                 fprintf(stderr, "ERROR: bad qgroup specification\n");
 631                 return 12;
 632         }
 633
 634         if (*inherit)
 635                 pos = (*inherit)->num_qgroups;
 636         ret = qgroup_inherit_realloc(inherit, 1, pos);
 637         if (ret)
 638                 return ret;
 639
 640         (*inherit)->qgroups[(*inherit)->num_qgroups++] = qgroupid;
 641
 642         return 0;
 643 }
 644
 645 int qgroup_inherit_add_copy(struct btrfs_qgroup_inherit **inherit, char *arg,
 646                             int type)
 647 {
 648         int ret;
 649         u64 qgroup_src;
 650         u64 qgroup_dst;
 651         char *p;
 652         int pos = 0;
 653
 654         p = strchr(arg, ':');
 655         if (!p) {
 656 bad:
 657                 fprintf(stderr, "ERROR: bad copy specification\n");
 658                 return 12;
 659         }
 660         *p = 0;
 661         qgroup_src = parse_qgroupid(arg);
 662         qgroup_dst = parse_qgroupid(p + 1);
 663         *p = ':';
 664
 665         if (!qgroup_src || !qgroup_dst)
 666                 goto bad;
 667
 668         if (*inherit)
 669                 pos = (*inherit)->num_qgroups +
 670                       (*inherit)->num_ref_copies * 2 * type;
 671
 672         ret = qgroup_inherit_realloc(inherit, 2, pos);
 673         if (ret)
 674                 return ret;
 675
 676         (*inherit)->qgroups[pos++] = qgroup_src;
 677         (*inherit)->qgroups[pos++] = qgroup_dst;
 678
 679         if (!type)
 680                 ++(*inherit)->num_ref_copies;
 681         else
 682                 ++(*inherit)->num_excl_copies;
 683
 684         return 0;
 685 }