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