fs/btrfs/qgroup.c

   1 /*
   2  * Copyright (C) 2011 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 <linux/sched.h>
  20 #include <linux/pagemap.h>
  21 #include <linux/writeback.h>
  22 #include <linux/blkdev.h>
  23 #include <linux/rbtree.h>
  24 #include <linux/slab.h>
  25 #include <linux/workqueue.h>
  26 #include <linux/btrfs.h>
  27
  28 #include "ctree.h"
  29 #include "transaction.h"
  30 #include "disk-io.h"
  31 #include "locking.h"
  32 #include "ulist.h"
  33 #include "backref.h"
  34 #include "extent_io.h"
  35 #include "qgroup.h"
  36
  37 /* TODO XXX FIXME
  38  *  - subvol delete -> delete when ref goes to 0? delete limits also?
  39  *  - reorganize keys
  40  *  - compressed
  41  *  - sync
  42  *  - copy also limits on subvol creation
  43  *  - limit
  44  *  - caches fuer ulists
  45  *  - performance benchmarks
  46  *  - check all ioctl parameters
  47  */
  48
  49 /*
  50  * one struct for each qgroup, organized in fs_info->qgroup_tree.
  51  */
  52 struct btrfs_qgroup {
  53         u64 qgroupid;
  54
  55         /*
  56          * state
  57          */
  58         u64 rfer;       /* referenced */
  59         u64 rfer_cmpr;  /* referenced compressed */
  60         u64 excl;       /* exclusive */
  61         u64 excl_cmpr;  /* exclusive compressed */
  62
  63         /*
  64          * limits
  65          */
  66         u64 lim_flags;  /* which limits are set */
  67         u64 max_rfer;
  68         u64 max_excl;
  69         u64 rsv_rfer;
  70         u64 rsv_excl;
  71
  72         /*
  73          * reservation tracking
  74          */
  75         u64 reserved;
  76
  77         /*
  78          * lists
  79          */
  80         struct list_head groups;  /* groups this group is member of */
  81         struct list_head members; /* groups that are members of this group */
  82         struct list_head dirty;   /* dirty groups */
  83         struct rb_node node;      /* tree of qgroups */
  84
  85         /*
  86          * temp variables for accounting operations
  87          */
  88         u64 old_refcnt;
  89         u64 new_refcnt;
  90 };
  91
  92 /*
  93  * glue structure to represent the relations between qgroups.
  94  */
  95 struct btrfs_qgroup_list {
  96         struct list_head next_group;
  97         struct list_head next_member;
  98         struct btrfs_qgroup *group;
  99         struct btrfs_qgroup *member;
 100 };
 101
 102 #define ptr_to_u64(x) ((u64)(uintptr_t)x)
 103 #define u64_to_ptr(x) ((struct btrfs_qgroup *)(uintptr_t)x)
 104
 105 static int
 106 qgroup_rescan_init(struct btrfs_fs_info *fs_info, u64 progress_objectid,
 107                    int init_flags);
 108 static void qgroup_rescan_zero_tracking(struct btrfs_fs_info *fs_info);
 109
 110 /* must be called with qgroup_ioctl_lock held */
 111 static struct btrfs_qgroup *find_qgroup_rb(struct btrfs_fs_info *fs_info,
 112                                            u64 qgroupid)
 113 {
 114         struct rb_node *n = fs_info->qgroup_tree.rb_node;
 115         struct btrfs_qgroup *qgroup;
 116
 117         while (n) {
 118                 qgroup = rb_entry(n, struct btrfs_qgroup, node);
 119                 if (qgroup->qgroupid < qgroupid)
 120                         n = n->rb_left;
 121                 else if (qgroup->qgroupid > qgroupid)
 122                         n = n->rb_right;
 123                 else
 124                         return qgroup;
 125         }
 126         return NULL;
 127 }
 128
 129 /* must be called with qgroup_lock held */
 130 static struct btrfs_qgroup *add_qgroup_rb(struct btrfs_fs_info *fs_info,
 131                                           u64 qgroupid)
 132 {
 133         struct rb_node **p = &fs_info->qgroup_tree.rb_node;
 134         struct rb_node *parent = NULL;
 135         struct btrfs_qgroup *qgroup;
 136
 137         while (*p) {
 138                 parent = *p;
 139                 qgroup = rb_entry(parent, struct btrfs_qgroup, node);
 140
 141                 if (qgroup->qgroupid < qgroupid)
 142                         p = &(*p)->rb_left;
 143                 else if (qgroup->qgroupid > qgroupid)
 144                         p = &(*p)->rb_right;
 145                 else
 146                         return qgroup;
 147         }
 148
 149         qgroup = kzalloc(sizeof(*qgroup), GFP_ATOMIC);
 150         if (!qgroup)
 151                 return ERR_PTR(-ENOMEM);
 152
 153         qgroup->qgroupid = qgroupid;
 154         INIT_LIST_HEAD(&qgroup->groups);
 155         INIT_LIST_HEAD(&qgroup->members);
 156         INIT_LIST_HEAD(&qgroup->dirty);
 157
 158         rb_link_node(&qgroup->node, parent, p);
 159         rb_insert_color(&qgroup->node, &fs_info->qgroup_tree);
 160
 161         return qgroup;
 162 }
 163
 164 static void __del_qgroup_rb(struct btrfs_qgroup *qgroup)
 165 {
 166         struct btrfs_qgroup_list *list;
 167
 168         list_del(&qgroup->dirty);
 169         while (!list_empty(&qgroup->groups)) {
 170                 list = list_first_entry(&qgroup->groups,
 171                                         struct btrfs_qgroup_list, next_group);
 172                 list_del(&list->next_group);
 173                 list_del(&list->next_member);
 174                 kfree(list);
 175         }
 176
 177         while (!list_empty(&qgroup->members)) {
 178                 list = list_first_entry(&qgroup->members,
 179                                         struct btrfs_qgroup_list, next_member);
 180                 list_del(&list->next_group);
 181                 list_del(&list->next_member);
 182                 kfree(list);
 183         }
 184         kfree(qgroup);
 185 }
 186
 187 /* must be called with qgroup_lock held */
 188 static int del_qgroup_rb(struct btrfs_fs_info *fs_info, u64 qgroupid)
 189 {
 190         struct btrfs_qgroup *qgroup = find_qgroup_rb(fs_info, qgroupid);
 191
 192         if (!qgroup)
 193                 return -ENOENT;
 194
 195         rb_erase(&qgroup->node, &fs_info->qgroup_tree);
 196         __del_qgroup_rb(qgroup);
 197         return 0;
 198 }
 199
 200 /* must be called with qgroup_lock held */
 201 static int add_relation_rb(struct btrfs_fs_info *fs_info,
 202                            u64 memberid, u64 parentid)
 203 {
 204         struct btrfs_qgroup *member;
 205         struct btrfs_qgroup *parent;
 206         struct btrfs_qgroup_list *list;
 207
 208         member = find_qgroup_rb(fs_info, memberid);
 209         parent = find_qgroup_rb(fs_info, parentid);
 210         if (!member || !parent)
 211                 return -ENOENT;
 212
 213         list = kzalloc(sizeof(*list), GFP_ATOMIC);
 214         if (!list)
 215                 return -ENOMEM;
 216
 217         list->group = parent;
 218         list->member = member;
 219         list_add_tail(&list->next_group, &member->groups);
 220         list_add_tail(&list->next_member, &parent->members);
 221
 222         return 0;
 223 }
 224
 225 /* must be called with qgroup_lock held */
 226 static int del_relation_rb(struct btrfs_fs_info *fs_info,
 227                            u64 memberid, u64 parentid)
 228 {
 229         struct btrfs_qgroup *member;
 230         struct btrfs_qgroup *parent;
 231         struct btrfs_qgroup_list *list;
 232
 233         member = find_qgroup_rb(fs_info, memberid);
 234         parent = find_qgroup_rb(fs_info, parentid);
 235         if (!member || !parent)
 236                 return -ENOENT;
 237
 238         list_for_each_entry(list, &member->groups, next_group) {
 239                 if (list->group == parent) {
 240                         list_del(&list->next_group);
 241                         list_del(&list->next_member);
 242                         kfree(list);
 243                         return 0;
 244                 }
 245         }
 246         return -ENOENT;
 247 }
 248
 249 #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
 250 int btrfs_verify_qgroup_counts(struct btrfs_fs_info *fs_info, u64 qgroupid,
 251                                u64 rfer, u64 excl)
 252 {
 253         struct btrfs_qgroup *qgroup;
 254
 255         qgroup = find_qgroup_rb(fs_info, qgroupid);
 256         if (!qgroup)
 257                 return -EINVAL;
 258         if (qgroup->rfer != rfer || qgroup->excl != excl)
 259                 return -EINVAL;
 260         return 0;
 261 }
 262 #endif
 263
 264 /*
 265  * The full config is read in one go, only called from open_ctree()
 266  * It doesn't use any locking, as at this point we're still single-threaded
 267  */
 268 int btrfs_read_qgroup_config(struct btrfs_fs_info *fs_info)
 269 {
 270         struct btrfs_key key;
 271         struct btrfs_key found_key;
 272         struct btrfs_root *quota_root = fs_info->quota_root;
 273         struct btrfs_path *path = NULL;
 274         struct extent_buffer *l;
 275         int slot;
 276         int ret = 0;
 277         u64 flags = 0;
 278         u64 rescan_progress = 0;
 279
 280         if (!fs_info->quota_enabled)
 281                 return 0;
 282
 283         fs_info->qgroup_ulist = ulist_alloc(GFP_NOFS);
 284         if (!fs_info->qgroup_ulist) {
 285                 ret = -ENOMEM;
 286                 goto out;
 287         }
 288
 289         path = btrfs_alloc_path();
 290         if (!path) {
 291                 ret = -ENOMEM;
 292                 goto out;
 293         }
 294
 295         /* default this to quota off, in case no status key is found */
 296         fs_info->qgroup_flags = 0;
 297
 298         /*
 299          * pass 1: read status, all qgroup infos and limits
 300          */
 301         key.objectid = 0;
 302         key.type = 0;
 303         key.offset = 0;
 304         ret = btrfs_search_slot_for_read(quota_root, &key, path, 1, 1);
 305         if (ret)
 306                 goto out;
 307
 308         while (1) {
 309                 struct btrfs_qgroup *qgroup;
 310
 311                 slot = path->slots[0];
 312                 l = path->nodes[0];
 313                 btrfs_item_key_to_cpu(l, &found_key, slot);
 314
 315                 if (found_key.type == BTRFS_QGROUP_STATUS_KEY) {
 316                         struct btrfs_qgroup_status_item *ptr;
 317
 318                         ptr = btrfs_item_ptr(l, slot,
 319                                              struct btrfs_qgroup_status_item);
 320
 321                         if (btrfs_qgroup_status_version(l, ptr) !=
 322                             BTRFS_QGROUP_STATUS_VERSION) {
 323                                 btrfs_err(fs_info,
 324                                  "old qgroup version, quota disabled");
 325                                 goto out;
 326                         }
 327                         if (btrfs_qgroup_status_generation(l, ptr) !=
 328                             fs_info->generation) {
 329                                 flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
 330                                 btrfs_err(fs_info,
 331                                         "qgroup generation mismatch, "
 332                                         "marked as inconsistent");
 333                         }
 334                         fs_info->qgroup_flags = btrfs_qgroup_status_flags(l,
 335                                                                           ptr);
 336                         rescan_progress = btrfs_qgroup_status_rescan(l, ptr);
 337                         goto next1;
 338                 }
 339
 340                 if (found_key.type != BTRFS_QGROUP_INFO_KEY &&
 341                     found_key.type != BTRFS_QGROUP_LIMIT_KEY)
 342                         goto next1;
 343
 344                 qgroup = find_qgroup_rb(fs_info, found_key.offset);
 345                 if ((qgroup && found_key.type == BTRFS_QGROUP_INFO_KEY) ||
 346                     (!qgroup && found_key.type == BTRFS_QGROUP_LIMIT_KEY)) {
 347                         btrfs_err(fs_info, "inconsitent qgroup config");
 348                         flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
 349                 }
 350                 if (!qgroup) {
 351                         qgroup = add_qgroup_rb(fs_info, found_key.offset);
 352                         if (IS_ERR(qgroup)) {
 353                                 ret = PTR_ERR(qgroup);
 354                                 goto out;
 355                         }
 356                 }
 357                 switch (found_key.type) {
 358                 case BTRFS_QGROUP_INFO_KEY: {
 359                         struct btrfs_qgroup_info_item *ptr;
 360
 361                         ptr = btrfs_item_ptr(l, slot,
 362                                              struct btrfs_qgroup_info_item);
 363                         qgroup->rfer = btrfs_qgroup_info_rfer(l, ptr);
 364                         qgroup->rfer_cmpr = btrfs_qgroup_info_rfer_cmpr(l, ptr);
 365                         qgroup->excl = btrfs_qgroup_info_excl(l, ptr);
 366                         qgroup->excl_cmpr = btrfs_qgroup_info_excl_cmpr(l, ptr);
 367                         /* generation currently unused */
 368                         break;
 369                 }
 370                 case BTRFS_QGROUP_LIMIT_KEY: {
 371                         struct btrfs_qgroup_limit_item *ptr;
 372
 373                         ptr = btrfs_item_ptr(l, slot,
 374                                              struct btrfs_qgroup_limit_item);
 375                         qgroup->lim_flags = btrfs_qgroup_limit_flags(l, ptr);
 376                         qgroup->max_rfer = btrfs_qgroup_limit_max_rfer(l, ptr);
 377                         qgroup->max_excl = btrfs_qgroup_limit_max_excl(l, ptr);
 378                         qgroup->rsv_rfer = btrfs_qgroup_limit_rsv_rfer(l, ptr);
 379                         qgroup->rsv_excl = btrfs_qgroup_limit_rsv_excl(l, ptr);
 380                         break;
 381                 }
 382                 }
 383 next1:
 384                 ret = btrfs_next_item(quota_root, path);
 385                 if (ret < 0)
 386                         goto out;
 387                 if (ret)
 388                         break;
 389         }
 390         btrfs_release_path(path);
 391
 392         /*
 393          * pass 2: read all qgroup relations
 394          */
 395         key.objectid = 0;
 396         key.type = BTRFS_QGROUP_RELATION_KEY;
 397         key.offset = 0;
 398         ret = btrfs_search_slot_for_read(quota_root, &key, path, 1, 0);
 399         if (ret)
 400                 goto out;
 401         while (1) {
 402                 slot = path->slots[0];
 403                 l = path->nodes[0];
 404                 btrfs_item_key_to_cpu(l, &found_key, slot);
 405
 406                 if (found_key.type != BTRFS_QGROUP_RELATION_KEY)
 407                         goto next2;
 408
 409                 if (found_key.objectid > found_key.offset) {
 410                         /* parent <- member, not needed to build config */
 411                         /* FIXME should we omit the key completely? */
 412                         goto next2;
 413                 }
 414
 415                 ret = add_relation_rb(fs_info, found_key.objectid,
 416                                       found_key.offset);
 417                 if (ret == -ENOENT) {
 418                         btrfs_warn(fs_info,
 419                                 "orphan qgroup relation 0x%llx->0x%llx",
 420                                 found_key.objectid, found_key.offset);
 421                         ret = 0;        /* ignore the error */
 422                 }
 423                 if (ret)
 424                         goto out;
 425 next2:
 426                 ret = btrfs_next_item(quota_root, path);
 427                 if (ret < 0)
 428                         goto out;
 429                 if (ret)
 430                         break;
 431         }
 432 out:
 433         fs_info->qgroup_flags |= flags;
 434         if (!(fs_info->qgroup_flags & BTRFS_QGROUP_STATUS_FLAG_ON)) {
 435                 fs_info->quota_enabled = 0;
 436                 fs_info->pending_quota_state = 0;
 437         } else if (fs_info->qgroup_flags & BTRFS_QGROUP_STATUS_FLAG_RESCAN &&
 438                    ret >= 0) {
 439                 ret = qgroup_rescan_init(fs_info, rescan_progress, 0);
 440         }
 441         btrfs_free_path(path);
 442
 443         if (ret < 0) {
 444                 ulist_free(fs_info->qgroup_ulist);
 445                 fs_info->qgroup_ulist = NULL;
 446                 fs_info->qgroup_flags &= ~BTRFS_QGROUP_STATUS_FLAG_RESCAN;
 447         }
 448
 449         return ret < 0 ? ret : 0;
 450 }
 451
 452 /*
 453  * This is called from close_ctree() or open_ctree() or btrfs_quota_disable(),
 454  * first two are in single-threaded paths.And for the third one, we have set
 455  * quota_root to be null with qgroup_lock held before, so it is safe to clean
 456  * up the in-memory structures without qgroup_lock held.
 457  */
 458 void btrfs_free_qgroup_config(struct btrfs_fs_info *fs_info)
 459 {
 460         struct rb_node *n;
 461         struct btrfs_qgroup *qgroup;
 462
 463         while ((n = rb_first(&fs_info->qgroup_tree))) {
 464                 qgroup = rb_entry(n, struct btrfs_qgroup, node);
 465                 rb_erase(n, &fs_info->qgroup_tree);
 466                 __del_qgroup_rb(qgroup);
 467         }
 468         /*
 469          * we call btrfs_free_qgroup_config() when umounting
 470          * filesystem and disabling quota, so we set qgroup_ulit
 471          * to be null here to avoid double free.
 472          */
 473         ulist_free(fs_info->qgroup_ulist);
 474         fs_info->qgroup_ulist = NULL;
 475 }
 476
 477 static int add_qgroup_relation_item(struct btrfs_trans_handle *trans,
 478                                     struct btrfs_root *quota_root,
 479                                     u64 src, u64 dst)
 480 {
 481         int ret;
 482         struct btrfs_path *path;
 483         struct btrfs_key key;
 484
 485         path = btrfs_alloc_path();
 486         if (!path)
 487                 return -ENOMEM;
 488
 489         key.objectid = src;
 490         key.type = BTRFS_QGROUP_RELATION_KEY;
 491         key.offset = dst;
 492
 493         ret = btrfs_insert_empty_item(trans, quota_root, path, &key, 0);
 494
 495         btrfs_mark_buffer_dirty(path->nodes[0]);
 496
 497         btrfs_free_path(path);
 498         return ret;
 499 }
 500
 501 static int del_qgroup_relation_item(struct btrfs_trans_handle *trans,
 502                                     struct btrfs_root *quota_root,
 503                                     u64 src, u64 dst)
 504 {
 505         int ret;
 506         struct btrfs_path *path;
 507         struct btrfs_key key;
 508
 509         path = btrfs_alloc_path();
 510         if (!path)
 511                 return -ENOMEM;
 512
 513         key.objectid = src;
 514         key.type = BTRFS_QGROUP_RELATION_KEY;
 515         key.offset = dst;
 516
 517         ret = btrfs_search_slot(trans, quota_root, &key, path, -1, 1);
 518         if (ret < 0)
 519                 goto out;
 520
 521         if (ret > 0) {
 522                 ret = -ENOENT;
 523                 goto out;
 524         }
 525
 526         ret = btrfs_del_item(trans, quota_root, path);
 527 out:
 528         btrfs_free_path(path);
 529         return ret;
 530 }
 531
 532 static int add_qgroup_item(struct btrfs_trans_handle *trans,
 533                            struct btrfs_root *quota_root, u64 qgroupid)
 534 {
 535         int ret;
 536         struct btrfs_path *path;
 537         struct btrfs_qgroup_info_item *qgroup_info;
 538         struct btrfs_qgroup_limit_item *qgroup_limit;
 539         struct extent_buffer *leaf;
 540         struct btrfs_key key;
 541
 542         if (btrfs_test_is_dummy_root(quota_root))
 543                 return 0;
 544
 545         path = btrfs_alloc_path();
 546         if (!path)
 547                 return -ENOMEM;
 548
 549         key.objectid = 0;
 550         key.type = BTRFS_QGROUP_INFO_KEY;
 551         key.offset = qgroupid;
 552
 553         /*
 554          * Avoid a transaction abort by catching -EEXIST here. In that
 555          * case, we proceed by re-initializing the existing structure
 556          * on disk.
 557          */
 558
 559         ret = btrfs_insert_empty_item(trans, quota_root, path, &key,
 560                                       sizeof(*qgroup_info));
 561         if (ret && ret != -EEXIST)
 562                 goto out;
 563
 564         leaf = path->nodes[0];
 565         qgroup_info = btrfs_item_ptr(leaf, path->slots[0],
 566                                  struct btrfs_qgroup_info_item);
 567         btrfs_set_qgroup_info_generation(leaf, qgroup_info, trans->transid);
 568         btrfs_set_qgroup_info_rfer(leaf, qgroup_info, 0);
 569         btrfs_set_qgroup_info_rfer_cmpr(leaf, qgroup_info, 0);
 570         btrfs_set_qgroup_info_excl(leaf, qgroup_info, 0);
 571         btrfs_set_qgroup_info_excl_cmpr(leaf, qgroup_info, 0);
 572
 573         btrfs_mark_buffer_dirty(leaf);
 574
 575         btrfs_release_path(path);
 576
 577         key.type = BTRFS_QGROUP_LIMIT_KEY;
 578         ret = btrfs_insert_empty_item(trans, quota_root, path, &key,
 579                                       sizeof(*qgroup_limit));
 580         if (ret && ret != -EEXIST)
 581                 goto out;
 582
 583         leaf = path->nodes[0];
 584         qgroup_limit = btrfs_item_ptr(leaf, path->slots[0],
 585                                   struct btrfs_qgroup_limit_item);
 586         btrfs_set_qgroup_limit_flags(leaf, qgroup_limit, 0);
 587         btrfs_set_qgroup_limit_max_rfer(leaf, qgroup_limit, 0);
 588         btrfs_set_qgroup_limit_max_excl(leaf, qgroup_limit, 0);
 589         btrfs_set_qgroup_limit_rsv_rfer(leaf, qgroup_limit, 0);
 590         btrfs_set_qgroup_limit_rsv_excl(leaf, qgroup_limit, 0);
 591
 592         btrfs_mark_buffer_dirty(leaf);
 593
 594         ret = 0;
 595 out:
 596         btrfs_free_path(path);
 597         return ret;
 598 }
 599
 600 static int del_qgroup_item(struct btrfs_trans_handle *trans,
 601                            struct btrfs_root *quota_root, u64 qgroupid)
 602 {
 603         int ret;
 604         struct btrfs_path *path;
 605         struct btrfs_key key;
 606
 607         path = btrfs_alloc_path();
 608         if (!path)
 609                 return -ENOMEM;
 610
 611         key.objectid = 0;
 612         key.type = BTRFS_QGROUP_INFO_KEY;
 613         key.offset = qgroupid;
 614         ret = btrfs_search_slot(trans, quota_root, &key, path, -1, 1);
 615         if (ret < 0)
 616                 goto out;
 617
 618         if (ret > 0) {
 619                 ret = -ENOENT;
 620                 goto out;
 621         }
 622
 623         ret = btrfs_del_item(trans, quota_root, path);
 624         if (ret)
 625                 goto out;
 626
 627         btrfs_release_path(path);
 628
 629         key.type = BTRFS_QGROUP_LIMIT_KEY;
 630         ret = btrfs_search_slot(trans, quota_root, &key, path, -1, 1);
 631         if (ret < 0)
 632                 goto out;
 633
 634         if (ret > 0) {
 635                 ret = -ENOENT;
 636                 goto out;
 637         }
 638
 639         ret = btrfs_del_item(trans, quota_root, path);
 640
 641 out:
 642         btrfs_free_path(path);
 643         return ret;
 644 }
 645
 646 static int update_qgroup_limit_item(struct btrfs_trans_handle *trans,
 647                                     struct btrfs_root *root,
 648                                     struct btrfs_qgroup *qgroup)
 649 {
 650         struct btrfs_path *path;
 651         struct btrfs_key key;
 652         struct extent_buffer *l;
 653         struct btrfs_qgroup_limit_item *qgroup_limit;
 654         int ret;
 655         int slot;
 656
 657         key.objectid = 0;
 658         key.type = BTRFS_QGROUP_LIMIT_KEY;
 659         key.offset = qgroup->qgroupid;
 660
 661         path = btrfs_alloc_path();
 662         if (!path)
 663                 return -ENOMEM;
 664
 665         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 666         if (ret > 0)
 667                 ret = -ENOENT;
 668
 669         if (ret)
 670                 goto out;
 671
 672         l = path->nodes[0];
 673         slot = path->slots[0];
 674         qgroup_limit = btrfs_item_ptr(l, slot, struct btrfs_qgroup_limit_item);
 675         btrfs_set_qgroup_limit_flags(l, qgroup_limit, qgroup->lim_flags);
 676         btrfs_set_qgroup_limit_max_rfer(l, qgroup_limit, qgroup->max_rfer);
 677         btrfs_set_qgroup_limit_max_excl(l, qgroup_limit, qgroup->max_excl);
 678         btrfs_set_qgroup_limit_rsv_rfer(l, qgroup_limit, qgroup->rsv_rfer);
 679         btrfs_set_qgroup_limit_rsv_excl(l, qgroup_limit, qgroup->rsv_excl);
 680
 681         btrfs_mark_buffer_dirty(l);
 682
 683 out:
 684         btrfs_free_path(path);
 685         return ret;
 686 }
 687
 688 static int update_qgroup_info_item(struct btrfs_trans_handle *trans,
 689                                    struct btrfs_root *root,
 690                                    struct btrfs_qgroup *qgroup)
 691 {
 692         struct btrfs_path *path;
 693         struct btrfs_key key;
 694         struct extent_buffer *l;
 695         struct btrfs_qgroup_info_item *qgroup_info;
 696         int ret;
 697         int slot;
 698
 699         if (btrfs_test_is_dummy_root(root))
 700                 return 0;
 701
 702         key.objectid = 0;
 703         key.type = BTRFS_QGROUP_INFO_KEY;
 704         key.offset = qgroup->qgroupid;
 705
 706         path = btrfs_alloc_path();
 707         if (!path)
 708                 return -ENOMEM;
 709
 710         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 711         if (ret > 0)
 712                 ret = -ENOENT;
 713
 714         if (ret)
 715                 goto out;
 716
 717         l = path->nodes[0];
 718         slot = path->slots[0];
 719         qgroup_info = btrfs_item_ptr(l, slot, struct btrfs_qgroup_info_item);
 720         btrfs_set_qgroup_info_generation(l, qgroup_info, trans->transid);
 721         btrfs_set_qgroup_info_rfer(l, qgroup_info, qgroup->rfer);
 722         btrfs_set_qgroup_info_rfer_cmpr(l, qgroup_info, qgroup->rfer_cmpr);
 723         btrfs_set_qgroup_info_excl(l, qgroup_info, qgroup->excl);
 724         btrfs_set_qgroup_info_excl_cmpr(l, qgroup_info, qgroup->excl_cmpr);
 725
 726         btrfs_mark_buffer_dirty(l);
 727
 728 out:
 729         btrfs_free_path(path);
 730         return ret;
 731 }
 732
 733 static int update_qgroup_status_item(struct btrfs_trans_handle *trans,
 734                                      struct btrfs_fs_info *fs_info,
 735                                     struct btrfs_root *root)
 736 {
 737         struct btrfs_path *path;
 738         struct btrfs_key key;
 739         struct extent_buffer *l;
 740         struct btrfs_qgroup_status_item *ptr;
 741         int ret;
 742         int slot;
 743
 744         key.objectid = 0;
 745         key.type = BTRFS_QGROUP_STATUS_KEY;
 746         key.offset = 0;
 747
 748         path = btrfs_alloc_path();
 749         if (!path)
 750                 return -ENOMEM;
 751
 752         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 753         if (ret > 0)
 754                 ret = -ENOENT;
 755
 756         if (ret)
 757                 goto out;
 758
 759         l = path->nodes[0];
 760         slot = path->slots[0];
 761         ptr = btrfs_item_ptr(l, slot, struct btrfs_qgroup_status_item);
 762         btrfs_set_qgroup_status_flags(l, ptr, fs_info->qgroup_flags);
 763         btrfs_set_qgroup_status_generation(l, ptr, trans->transid);
 764         btrfs_set_qgroup_status_rescan(l, ptr,
 765                                 fs_info->qgroup_rescan_progress.objectid);
 766
 767         btrfs_mark_buffer_dirty(l);
 768
 769 out:
 770         btrfs_free_path(path);
 771         return ret;
 772 }
 773
 774 /*
 775  * called with qgroup_lock held
 776  */
 777 static int btrfs_clean_quota_tree(struct btrfs_trans_handle *trans,
 778                                   struct btrfs_root *root)
 779 {
 780         struct btrfs_path *path;
 781         struct btrfs_key key;
 782         struct extent_buffer *leaf = NULL;
 783         int ret;
 784         int nr = 0;
 785
 786         path = btrfs_alloc_path();
 787         if (!path)
 788                 return -ENOMEM;
 789
 790         path->leave_spinning = 1;
 791
 792         key.objectid = 0;
 793         key.offset = 0;
 794         key.type = 0;
 795
 796         while (1) {
 797                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 798                 if (ret < 0)
 799                         goto out;
 800                 leaf = path->nodes[0];
 801                 nr = btrfs_header_nritems(leaf);
 802                 if (!nr)
 803                         break;
 804                 /*
 805                  * delete the leaf one by one
 806                  * since the whole tree is going
 807                  * to be deleted.
 808                  */
 809                 path->slots[0] = 0;
 810                 ret = btrfs_del_items(trans, root, path, 0, nr);
 811                 if (ret)
 812                         goto out;
 813
 814                 btrfs_release_path(path);
 815         }
 816         ret = 0;
 817 out:
 818         root->fs_info->pending_quota_state = 0;
 819         btrfs_free_path(path);
 820         return ret;
 821 }
 822
 823 int btrfs_quota_enable(struct btrfs_trans_handle *trans,
 824                        struct btrfs_fs_info *fs_info)
 825 {
 826         struct btrfs_root *quota_root;
 827         struct btrfs_root *tree_root = fs_info->tree_root;
 828         struct btrfs_path *path = NULL;
 829         struct btrfs_qgroup_status_item *ptr;
 830         struct extent_buffer *leaf;
 831         struct btrfs_key key;
 832         struct btrfs_key found_key;
 833         struct btrfs_qgroup *qgroup = NULL;
 834         int ret = 0;
 835         int slot;
 836
 837         mutex_lock(&fs_info->qgroup_ioctl_lock);
 838         if (fs_info->quota_root) {
 839                 fs_info->pending_quota_state = 1;
 840                 goto out;
 841         }
 842
 843         fs_info->qgroup_ulist = ulist_alloc(GFP_NOFS);
 844         if (!fs_info->qgroup_ulist) {
 845                 ret = -ENOMEM;
 846                 goto out;
 847         }
 848
 849         /*
 850          * initially create the quota tree
 851          */
 852         quota_root = btrfs_create_tree(trans, fs_info,
 853                                        BTRFS_QUOTA_TREE_OBJECTID);
 854         if (IS_ERR(quota_root)) {
 855                 ret =  PTR_ERR(quota_root);
 856                 goto out;
 857         }
 858
 859         path = btrfs_alloc_path();
 860         if (!path) {
 861                 ret = -ENOMEM;
 862                 goto out_free_root;
 863         }
 864
 865         key.objectid = 0;
 866         key.type = BTRFS_QGROUP_STATUS_KEY;
 867         key.offset = 0;
 868
 869         ret = btrfs_insert_empty_item(trans, quota_root, path, &key,
 870                                       sizeof(*ptr));
 871         if (ret)
 872                 goto out_free_path;
 873
 874         leaf = path->nodes[0];
 875         ptr = btrfs_item_ptr(leaf, path->slots[0],
 876                                  struct btrfs_qgroup_status_item);
 877         btrfs_set_qgroup_status_generation(leaf, ptr, trans->transid);
 878         btrfs_set_qgroup_status_version(leaf, ptr, BTRFS_QGROUP_STATUS_VERSION);
 879         fs_info->qgroup_flags = BTRFS_QGROUP_STATUS_FLAG_ON |
 880                                 BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
 881         btrfs_set_qgroup_status_flags(leaf, ptr, fs_info->qgroup_flags);
 882         btrfs_set_qgroup_status_rescan(leaf, ptr, 0);
 883
 884         btrfs_mark_buffer_dirty(leaf);
 885
 886         key.objectid = 0;
 887         key.type = BTRFS_ROOT_REF_KEY;
 888         key.offset = 0;
 889
 890         btrfs_release_path(path);
 891         ret = btrfs_search_slot_for_read(tree_root, &key, path, 1, 0);
 892         if (ret > 0)
 893                 goto out_add_root;
 894         if (ret < 0)
 895                 goto out_free_path;
 896
 897
 898         while (1) {
 899                 slot = path->slots[0];
 900                 leaf = path->nodes[0];
 901                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
 902
 903                 if (found_key.type == BTRFS_ROOT_REF_KEY) {
 904                         ret = add_qgroup_item(trans, quota_root,
 905                                               found_key.offset);
 906                         if (ret)
 907                                 goto out_free_path;
 908
 909                         qgroup = add_qgroup_rb(fs_info, found_key.offset);
 910                         if (IS_ERR(qgroup)) {
 911                                 ret = PTR_ERR(qgroup);
 912                                 goto out_free_path;
 913                         }
 914                 }
 915                 ret = btrfs_next_item(tree_root, path);
 916                 if (ret < 0)
 917                         goto out_free_path;
 918                 if (ret)
 919                         break;
 920         }
 921
 922 out_add_root:
 923         btrfs_release_path(path);
 924         ret = add_qgroup_item(trans, quota_root, BTRFS_FS_TREE_OBJECTID);
 925         if (ret)
 926                 goto out_free_path;
 927
 928         qgroup = add_qgroup_rb(fs_info, BTRFS_FS_TREE_OBJECTID);
 929         if (IS_ERR(qgroup)) {
 930                 ret = PTR_ERR(qgroup);
 931                 goto out_free_path;
 932         }
 933         spin_lock(&fs_info->qgroup_lock);
 934         fs_info->quota_root = quota_root;
 935         fs_info->pending_quota_state = 1;
 936         spin_unlock(&fs_info->qgroup_lock);
 937 out_free_path:
 938         btrfs_free_path(path);
 939 out_free_root:
 940         if (ret) {
 941                 free_extent_buffer(quota_root->node);
 942                 free_extent_buffer(quota_root->commit_root);
 943                 kfree(quota_root);
 944         }
 945 out:
 946         if (ret) {
 947                 ulist_free(fs_info->qgroup_ulist);
 948                 fs_info->qgroup_ulist = NULL;
 949         }
 950         mutex_unlock(&fs_info->qgroup_ioctl_lock);
 951         return ret;
 952 }
 953
 954 int btrfs_quota_disable(struct btrfs_trans_handle *trans,
 955                         struct btrfs_fs_info *fs_info)
 956 {
 957         struct btrfs_root *tree_root = fs_info->tree_root;
 958         struct btrfs_root *quota_root;
 959         int ret = 0;
 960
 961         mutex_lock(&fs_info->qgroup_ioctl_lock);
 962         if (!fs_info->quota_root)
 963                 goto out;
 964         spin_lock(&fs_info->qgroup_lock);
 965         fs_info->quota_enabled = 0;
 966         fs_info->pending_quota_state = 0;
 967         quota_root = fs_info->quota_root;
 968         fs_info->quota_root = NULL;
 969         fs_info->qgroup_flags &= ~BTRFS_QGROUP_STATUS_FLAG_ON;
 970         spin_unlock(&fs_info->qgroup_lock);
 971
 972         btrfs_free_qgroup_config(fs_info);
 973
 974         ret = btrfs_clean_quota_tree(trans, quota_root);
 975         if (ret)
 976                 goto out;
 977
 978         ret = btrfs_del_root(trans, tree_root, &quota_root->root_key);
 979         if (ret)
 980                 goto out;
 981
 982         list_del(&quota_root->dirty_list);
 983
 984         btrfs_tree_lock(quota_root->node);
 985         clean_tree_block(trans, tree_root->fs_info, quota_root->node);
 986         btrfs_tree_unlock(quota_root->node);
 987         btrfs_free_tree_block(trans, quota_root, quota_root->node, 0, 1);
 988
 989         free_extent_buffer(quota_root->node);
 990         free_extent_buffer(quota_root->commit_root);
 991         kfree(quota_root);
 992 out:
 993         mutex_unlock(&fs_info->qgroup_ioctl_lock);
 994         return ret;
 995 }
 996
 997 static void qgroup_dirty(struct btrfs_fs_info *fs_info,
 998                          struct btrfs_qgroup *qgroup)
 999 {
1000         if (list_empty(&qgroup->dirty))
1001                 list_add(&qgroup->dirty, &fs_info->dirty_qgroups);
1002 }
1003
1004 int btrfs_add_qgroup_relation(struct btrfs_trans_handle *trans,
1005                               struct btrfs_fs_info *fs_info, u64 src, u64 dst)
1006 {
1007         struct btrfs_root *quota_root;
1008         struct btrfs_qgroup *parent;
1009         struct btrfs_qgroup *member;
1010         struct btrfs_qgroup_list *list;
1011         int ret = 0;
1012
1013         /* Check the level of src and dst first */
1014         if (btrfs_qgroup_level(src) >= btrfs_qgroup_level(dst))
1015                 return -EINVAL;
1016
1017         mutex_lock(&fs_info->qgroup_ioctl_lock);
1018         quota_root = fs_info->quota_root;
1019         if (!quota_root) {
1020                 ret = -EINVAL;
1021                 goto out;
1022         }
1023         member = find_qgroup_rb(fs_info, src);
1024         parent = find_qgroup_rb(fs_info, dst);
1025         if (!member || !parent) {
1026                 ret = -EINVAL;
1027                 goto out;
1028         }
1029
1030         /* check if such qgroup relation exist firstly */
1031         list_for_each_entry(list, &member->groups, next_group) {
1032                 if (list->group == parent) {
1033                         ret = -EEXIST;
1034                         goto out;
1035                 }
1036         }
1037
1038         ret = add_qgroup_relation_item(trans, quota_root, src, dst);
1039         if (ret)
1040                 goto out;
1041
1042         ret = add_qgroup_relation_item(trans, quota_root, dst, src);
1043         if (ret) {
1044                 del_qgroup_relation_item(trans, quota_root, src, dst);
1045                 goto out;
1046         }
1047
1048         spin_lock(&fs_info->qgroup_lock);
1049         ret = add_relation_rb(quota_root->fs_info, src, dst);
1050         spin_unlock(&fs_info->qgroup_lock);
1051 out:
1052         mutex_unlock(&fs_info->qgroup_ioctl_lock);
1053         return ret;
1054 }
1055
1056 int __del_qgroup_relation(struct btrfs_trans_handle *trans,
1057                               struct btrfs_fs_info *fs_info, u64 src, u64 dst)
1058 {
1059         struct btrfs_root *quota_root;
1060         struct btrfs_qgroup *parent;
1061         struct btrfs_qgroup *member;
1062         struct btrfs_qgroup_list *list;
1063         int ret = 0;
1064         int err;
1065
1066         quota_root = fs_info->quota_root;
1067         if (!quota_root) {
1068                 ret = -EINVAL;
1069                 goto out;
1070         }
1071
1072         member = find_qgroup_rb(fs_info, src);
1073         parent = find_qgroup_rb(fs_info, dst);
1074         if (!member || !parent) {
1075                 ret = -EINVAL;
1076                 goto out;
1077         }
1078
1079         /* check if such qgroup relation exist firstly */
1080         list_for_each_entry(list, &member->groups, next_group) {
1081                 if (list->group == parent)
1082                         goto exist;
1083         }
1084         ret = -ENOENT;
1085         goto out;
1086 exist:
1087         ret = del_qgroup_relation_item(trans, quota_root, src, dst);
1088         err = del_qgroup_relation_item(trans, quota_root, dst, src);
1089         if (err && !ret)
1090                 ret = err;
1091
1092         spin_lock(&fs_info->qgroup_lock);
1093         del_relation_rb(fs_info, src, dst);
1094         spin_unlock(&fs_info->qgroup_lock);
1095 out:
1096         return ret;
1097 }
1098
1099 int btrfs_del_qgroup_relation(struct btrfs_trans_handle *trans,
1100                               struct btrfs_fs_info *fs_info, u64 src, u64 dst)
1101 {
1102         int ret = 0;
1103
1104         mutex_lock(&fs_info->qgroup_ioctl_lock);
1105         ret = __del_qgroup_relation(trans, fs_info, src, dst);
1106         mutex_unlock(&fs_info->qgroup_ioctl_lock);
1107
1108         return ret;
1109 }
1110
1111 int btrfs_create_qgroup(struct btrfs_trans_handle *trans,
1112                         struct btrfs_fs_info *fs_info, u64 qgroupid)
1113 {
1114         struct btrfs_root *quota_root;
1115         struct btrfs_qgroup *qgroup;
1116         int ret = 0;
1117
1118         mutex_lock(&fs_info->qgroup_ioctl_lock);
1119         quota_root = fs_info->quota_root;
1120         if (!quota_root) {
1121                 ret = -EINVAL;
1122                 goto out;
1123         }
1124         qgroup = find_qgroup_rb(fs_info, qgroupid);
1125         if (qgroup) {
1126                 ret = -EEXIST;
1127                 goto out;
1128         }
1129
1130         ret = add_qgroup_item(trans, quota_root, qgroupid);
1131         if (ret)
1132                 goto out;
1133
1134         spin_lock(&fs_info->qgroup_lock);
1135         qgroup = add_qgroup_rb(fs_info, qgroupid);
1136         spin_unlock(&fs_info->qgroup_lock);
1137
1138         if (IS_ERR(qgroup))
1139                 ret = PTR_ERR(qgroup);
1140 out:
1141         mutex_unlock(&fs_info->qgroup_ioctl_lock);
1142         return ret;
1143 }
1144
1145 int btrfs_remove_qgroup(struct btrfs_trans_handle *trans,
1146                         struct btrfs_fs_info *fs_info, u64 qgroupid)
1147 {
1148         struct btrfs_root *quota_root;
1149         struct btrfs_qgroup *qgroup;
1150         struct btrfs_qgroup_list *list;
1151         int ret = 0;
1152
1153         mutex_lock(&fs_info->qgroup_ioctl_lock);
1154         quota_root = fs_info->quota_root;
1155         if (!quota_root) {
1156                 ret = -EINVAL;
1157                 goto out;
1158         }
1159
1160         qgroup = find_qgroup_rb(fs_info, qgroupid);
1161         if (!qgroup) {
1162                 ret = -ENOENT;
1163                 goto out;
1164         } else {
1165                 /* check if there are no children of this qgroup */
1166                 if (!list_empty(&qgroup->members)) {
1167                         ret = -EBUSY;
1168                         goto out;
1169                 }
1170         }
1171         ret = del_qgroup_item(trans, quota_root, qgroupid);
1172
1173         while (!list_empty(&qgroup->groups)) {
1174                 list = list_first_entry(&qgroup->groups,
1175                                         struct btrfs_qgroup_list, next_group);
1176                 ret = __del_qgroup_relation(trans, fs_info,
1177                                            qgroupid,
1178                                            list->group->qgroupid);
1179                 if (ret)
1180                         goto out;
1181         }
1182
1183         spin_lock(&fs_info->qgroup_lock);
1184         del_qgroup_rb(quota_root->fs_info, qgroupid);
1185         spin_unlock(&fs_info->qgroup_lock);
1186 out:
1187         mutex_unlock(&fs_info->qgroup_ioctl_lock);
1188         return ret;
1189 }
1190
1191 int btrfs_limit_qgroup(struct btrfs_trans_handle *trans,
1192                        struct btrfs_fs_info *fs_info, u64 qgroupid,
1193                        struct btrfs_qgroup_limit *limit)
1194 {
1195         struct btrfs_root *quota_root;
1196         struct btrfs_qgroup *qgroup;
1197         int ret = 0;
1198
1199         mutex_lock(&fs_info->qgroup_ioctl_lock);
1200         quota_root = fs_info->quota_root;
1201         if (!quota_root) {
1202                 ret = -EINVAL;
1203                 goto out;
1204         }
1205
1206         qgroup = find_qgroup_rb(fs_info, qgroupid);
1207         if (!qgroup) {
1208                 ret = -ENOENT;
1209                 goto out;
1210         }
1211
1212         spin_lock(&fs_info->qgroup_lock);
1213         if (limit->flags & BTRFS_QGROUP_LIMIT_MAX_RFER)
1214                 qgroup->max_rfer = limit->max_rfer;
1215         if (limit->flags & BTRFS_QGROUP_LIMIT_MAX_EXCL)
1216                 qgroup->max_excl = limit->max_excl;
1217         if (limit->flags & BTRFS_QGROUP_LIMIT_RSV_RFER)
1218                 qgroup->rsv_rfer = limit->rsv_rfer;
1219         if (limit->flags & BTRFS_QGROUP_LIMIT_RSV_EXCL)
1220                 qgroup->rsv_excl = limit->rsv_excl;
1221         qgroup->lim_flags |= limit->flags;
1222
1223         spin_unlock(&fs_info->qgroup_lock);
1224
1225         ret = update_qgroup_limit_item(trans, quota_root, qgroup);
1226         if (ret) {
1227                 fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
1228                 btrfs_info(fs_info, "unable to update quota limit for %llu",
1229                        qgroupid);
1230         }
1231
1232 out:
1233         mutex_unlock(&fs_info->qgroup_ioctl_lock);
1234         return ret;
1235 }
1236
1237 static int comp_oper_exist(struct btrfs_qgroup_operation *oper1,
1238                            struct btrfs_qgroup_operation *oper2)
1239 {
1240         /*
1241          * Ignore seq and type here, we're looking for any operation
1242          * at all related to this extent on that root.
1243          */
1244         if (oper1->bytenr < oper2->bytenr)
1245                 return -1;
1246         if (oper1->bytenr > oper2->bytenr)
1247                 return 1;
1248         if (oper1->ref_root < oper2->ref_root)
1249                 return -1;
1250         if (oper1->ref_root > oper2->ref_root)
1251                 return 1;
1252         return 0;
1253 }
1254
1255 static int qgroup_oper_exists(struct btrfs_fs_info *fs_info,
1256                               struct btrfs_qgroup_operation *oper)
1257 {
1258         struct rb_node *n;
1259         struct btrfs_qgroup_operation *cur;
1260         int cmp;
1261
1262         spin_lock(&fs_info->qgroup_op_lock);
1263         n = fs_info->qgroup_op_tree.rb_node;
1264         while (n) {
1265                 cur = rb_entry(n, struct btrfs_qgroup_operation, n);
1266                 cmp = comp_oper_exist(cur, oper);
1267                 if (cmp < 0) {
1268                         n = n->rb_right;
1269                 } else if (cmp) {
1270                         n = n->rb_left;
1271                 } else {
1272                         spin_unlock(&fs_info->qgroup_op_lock);
1273                         return -EEXIST;
1274                 }
1275         }
1276         spin_unlock(&fs_info->qgroup_op_lock);
1277         return 0;
1278 }
1279
1280 static int comp_oper(struct btrfs_qgroup_operation *oper1,
1281                      struct btrfs_qgroup_operation *oper2)
1282 {
1283         if (oper1->bytenr < oper2->bytenr)
1284                 return -1;
1285         if (oper1->bytenr > oper2->bytenr)
1286                 return 1;
1287         if (oper1->ref_root < oper2->ref_root)
1288                 return -1;
1289         if (oper1->ref_root > oper2->ref_root)
1290                 return 1;
1291         if (oper1->seq < oper2->seq)
1292                 return -1;
1293         if (oper1->seq > oper2->seq)
1294                 return 1;
1295         if (oper1->type < oper2->type)
1296                 return -1;
1297         if (oper1->type > oper2->type)
1298                 return 1;
1299         return 0;
1300 }
1301
1302 static int insert_qgroup_oper(struct btrfs_fs_info *fs_info,
1303                               struct btrfs_qgroup_operation *oper)
1304 {
1305         struct rb_node **p;
1306         struct rb_node *parent = NULL;
1307         struct btrfs_qgroup_operation *cur;
1308         int cmp;
1309
1310         spin_lock(&fs_info->qgroup_op_lock);
1311         p = &fs_info->qgroup_op_tree.rb_node;
1312         while (*p) {
1313                 parent = *p;
1314                 cur = rb_entry(parent, struct btrfs_qgroup_operation, n);
1315                 cmp = comp_oper(cur, oper);
1316                 if (cmp < 0) {
1317                         p = &(*p)->rb_right;
1318                 } else if (cmp) {
1319                         p = &(*p)->rb_left;
1320                 } else {
1321                         spin_unlock(&fs_info->qgroup_op_lock);
1322                         return -EEXIST;
1323                 }
1324         }
1325         rb_link_node(&oper->n, parent, p);
1326         rb_insert_color(&oper->n, &fs_info->qgroup_op_tree);
1327         spin_unlock(&fs_info->qgroup_op_lock);
1328         return 0;
1329 }
1330
1331 /*
1332  * Record a quota operation for processing later on.
1333  * @trans: the transaction we are adding the delayed op to.
1334  * @fs_info: the fs_info for this fs.
1335  * @ref_root: the root of the reference we are acting on,
1336  * @bytenr: the bytenr we are acting on.
1337  * @num_bytes: the number of bytes in the reference.
1338  * @type: the type of operation this is.
1339  * @mod_seq: do we need to get a sequence number for looking up roots.
1340  *
1341  * We just add it to our trans qgroup_ref_list and carry on and process these
1342  * operations in order at some later point.  If the reference root isn't a fs
1343  * root then we don't bother with doing anything.
1344  *
1345  * MUST BE HOLDING THE REF LOCK.
1346  */
1347 int btrfs_qgroup_record_ref(struct btrfs_trans_handle *trans,
1348                             struct btrfs_fs_info *fs_info, u64 ref_root,
1349                             u64 bytenr, u64 num_bytes,
1350                             enum btrfs_qgroup_operation_type type, int mod_seq)
1351 {
1352         struct btrfs_qgroup_operation *oper;
1353         int ret;
1354
1355         if (!is_fstree(ref_root) || !fs_info->quota_enabled)
1356                 return 0;
1357
1358         oper = kmalloc(sizeof(*oper), GFP_NOFS);
1359         if (!oper)
1360                 return -ENOMEM;
1361
1362         oper->ref_root = ref_root;
1363         oper->bytenr = bytenr;
1364         oper->num_bytes = num_bytes;
1365         oper->type = type;
1366         oper->seq = atomic_inc_return(&fs_info->qgroup_op_seq);
1367         INIT_LIST_HEAD(&oper->elem.list);
1368         oper->elem.seq = 0;
1369
1370         trace_btrfs_qgroup_record_ref(oper);
1371
1372         if (type == BTRFS_QGROUP_OPER_SUB_SUBTREE) {
1373                 /*
1374                  * If any operation for this bytenr/ref_root combo
1375                  * exists, then we know it's not exclusively owned and
1376                  * shouldn't be queued up.
1377                  *
1378                  * This also catches the case where we have a cloned
1379                  * extent that gets queued up multiple times during
1380                  * drop snapshot.
1381                  */
1382                 if (qgroup_oper_exists(fs_info, oper)) {
1383                         kfree(oper);
1384                         return 0;
1385                 }
1386         }
1387
1388         ret = insert_qgroup_oper(fs_info, oper);
1389         if (ret) {
1390                 /* Shouldn't happen so have an assert for developers */
1391                 ASSERT(0);
1392                 kfree(oper);
1393                 return ret;
1394         }
1395         list_add_tail(&oper->list, &trans->qgroup_ref_list);
1396
1397         if (mod_seq)
1398                 btrfs_get_tree_mod_seq(fs_info, &oper->elem);
1399
1400         return 0;
1401 }
1402
1403 /*
1404  * The easy accounting, if we are adding/removing the only ref for an extent
1405  * then this qgroup and all of the parent qgroups get their refrence and
1406  * exclusive counts adjusted.
1407  */
1408 static int qgroup_excl_accounting(struct btrfs_fs_info *fs_info,
1409                                   struct btrfs_qgroup_operation *oper)
1410 {
1411         struct btrfs_qgroup *qgroup;
1412         struct ulist *tmp;
1413         struct btrfs_qgroup_list *glist;
1414         struct ulist_node *unode;
1415         struct ulist_iterator uiter;
1416         int sign = 0;
1417         int ret = 0;
1418
1419         tmp = ulist_alloc(GFP_NOFS);
1420         if (!tmp)
1421                 return -ENOMEM;
1422
1423         spin_lock(&fs_info->qgroup_lock);
1424         if (!fs_info->quota_root)
1425                 goto out;
1426         qgroup = find_qgroup_rb(fs_info, oper->ref_root);
1427         if (!qgroup)
1428                 goto out;
1429         switch (oper->type) {
1430         case BTRFS_QGROUP_OPER_ADD_EXCL:
1431                 sign = 1;
1432                 break;
1433         case BTRFS_QGROUP_OPER_SUB_EXCL:
1434                 sign = -1;
1435                 break;
1436         default:
1437                 ASSERT(0);
1438         }
1439         qgroup->rfer += sign * oper->num_bytes;
1440         qgroup->rfer_cmpr += sign * oper->num_bytes;
1441
1442         WARN_ON(sign < 0 && qgroup->excl < oper->num_bytes);
1443         qgroup->excl += sign * oper->num_bytes;
1444         qgroup->excl_cmpr += sign * oper->num_bytes;
1445         if (sign > 0)
1446                 qgroup->reserved -= oper->num_bytes;
1447
1448         qgroup_dirty(fs_info, qgroup);
1449
1450         /* Get all of the parent groups that contain this qgroup */
1451         list_for_each_entry(glist, &qgroup->groups, next_group) {
1452                 ret = ulist_add(tmp, glist->group->qgroupid,
1453                                 ptr_to_u64(glist->group), GFP_ATOMIC);
1454                 if (ret < 0)
1455                         goto out;
1456         }
1457
1458         /* Iterate all of the parents and adjust their reference counts */
1459         ULIST_ITER_INIT(&uiter);
1460         while ((unode = ulist_next(tmp, &uiter))) {
1461                 qgroup = u64_to_ptr(unode->aux);
1462                 qgroup->rfer += sign * oper->num_bytes;
1463                 qgroup->rfer_cmpr += sign * oper->num_bytes;
1464                 WARN_ON(sign < 0 && qgroup->excl < oper->num_bytes);
1465                 qgroup->excl += sign * oper->num_bytes;
1466                 if (sign > 0)
1467                         qgroup->reserved -= oper->num_bytes;
1468                 qgroup->excl_cmpr += sign * oper->num_bytes;
1469                 qgroup_dirty(fs_info, qgroup);
1470
1471                 /* Add any parents of the parents */
1472                 list_for_each_entry(glist, &qgroup->groups, next_group) {
1473                         ret = ulist_add(tmp, glist->group->qgroupid,
1474                                         ptr_to_u64(glist->group), GFP_ATOMIC);
1475                         if (ret < 0)
1476                                 goto out;
1477                 }
1478         }
1479         ret = 0;
1480 out:
1481         spin_unlock(&fs_info->qgroup_lock);
1482         ulist_free(tmp);
1483         return ret;
1484 }
1485
1486 /*
1487  * Walk all of the roots that pointed to our bytenr and adjust their refcnts as
1488  * properly.
1489  */
1490 static int qgroup_calc_old_refcnt(struct btrfs_fs_info *fs_info,
1491                                   u64 root_to_skip, struct ulist *tmp,
1492                                   struct ulist *roots, struct ulist *qgroups,
1493                                   u64 seq, int *old_roots, int rescan)
1494 {
1495         struct ulist_node *unode;
1496         struct ulist_iterator uiter;
1497         struct ulist_node *tmp_unode;
1498         struct ulist_iterator tmp_uiter;
1499         struct btrfs_qgroup *qg;
1500         int ret;
1501
1502         ULIST_ITER_INIT(&uiter);
1503         while ((unode = ulist_next(roots, &uiter))) {
1504                 /* We don't count our current root here */
1505                 if (unode->val == root_to_skip)
1506                         continue;
1507                 qg = find_qgroup_rb(fs_info, unode->val);
1508                 if (!qg)
1509                         continue;
1510                 /*
1511                  * We could have a pending removal of this same ref so we may
1512                  * not have actually found our ref root when doing
1513                  * btrfs_find_all_roots, so we need to keep track of how many
1514                  * old roots we find in case we removed ours and added a
1515                  * different one at the same time.  I don't think this could
1516                  * happen in practice but that sort of thinking leads to pain
1517                  * and suffering and to the dark side.
1518                  */
1519                 (*old_roots)++;
1520
1521                 ulist_reinit(tmp);
1522                 ret = ulist_add(qgroups, qg->qgroupid, ptr_to_u64(qg),
1523                                 GFP_ATOMIC);
1524                 if (ret < 0)
1525                         return ret;
1526                 ret = ulist_add(tmp, qg->qgroupid, ptr_to_u64(qg), GFP_ATOMIC);
1527                 if (ret < 0)
1528                         return ret;
1529                 ULIST_ITER_INIT(&tmp_uiter);
1530                 while ((tmp_unode = ulist_next(tmp, &tmp_uiter))) {
1531                         struct btrfs_qgroup_list *glist;
1532
1533                         qg = u64_to_ptr(tmp_unode->aux);
1534                         /*
1535                          * We use this sequence number to keep from having to
1536                          * run the whole list and 0 out the refcnt every time.
1537                          * We basically use sequnce as the known 0 count and
1538                          * then add 1 everytime we see a qgroup.  This is how we
1539                          * get how many of the roots actually point up to the
1540                          * upper level qgroups in order to determine exclusive
1541                          * counts.
1542                          *
1543                          * For rescan we want to set old_refcnt to seq so our
1544                          * exclusive calculations end up correct.
1545                          */
1546                         if (rescan)
1547                                 qg->old_refcnt = seq;
1548                         else if (qg->old_refcnt < seq)
1549                                 qg->old_refcnt = seq + 1;
1550                         else
1551                                 qg->old_refcnt++;
1552
1553                         if (qg->new_refcnt < seq)
1554                                 qg->new_refcnt = seq + 1;
1555                         else
1556                                 qg->new_refcnt++;
1557                         list_for_each_entry(glist, &qg->groups, next_group) {
1558                                 ret = ulist_add(qgroups, glist->group->qgroupid,
1559                                                 ptr_to_u64(glist->group),
1560                                                 GFP_ATOMIC);
1561                                 if (ret < 0)
1562                                         return ret;
1563                                 ret = ulist_add(tmp, glist->group->qgroupid,
1564                                                 ptr_to_u64(glist->group),
1565                                                 GFP_ATOMIC);
1566                                 if (ret < 0)
1567                                         return ret;
1568                         }
1569                 }
1570         }
1571         return 0;
1572 }
1573
1574 /*
1575  * We need to walk forward in our operation tree and account for any roots that
1576  * were deleted after we made this operation.
1577  */
1578 static int qgroup_account_deleted_refs(struct btrfs_fs_info *fs_info,
1579                                        struct btrfs_qgroup_operation *oper,
1580                                        struct ulist *tmp,
1581                                        struct ulist *qgroups, u64 seq,
1582                                        int *old_roots)
1583 {
1584         struct ulist_node *unode;
1585         struct ulist_iterator uiter;
1586         struct btrfs_qgroup *qg;
1587         struct btrfs_qgroup_operation *tmp_oper;
1588         struct rb_node *n;
1589         int ret;
1590
1591         ulist_reinit(tmp);
1592
1593         /*
1594          * We only walk forward in the tree since we're only interested in
1595          * removals that happened _after_  our operation.
1596          */
1597         spin_lock(&fs_info->qgroup_op_lock);
1598         n = rb_next(&oper->n);
1599         spin_unlock(&fs_info->qgroup_op_lock);
1600         if (!n)
1601                 return 0;
1602         tmp_oper = rb_entry(n, struct btrfs_qgroup_operation, n);
1603         while (tmp_oper->bytenr == oper->bytenr) {
1604                 /*
1605                  * If it's not a removal we don't care, additions work out
1606                  * properly with our refcnt tracking.
1607                  */
1608                 if (tmp_oper->type != BTRFS_QGROUP_OPER_SUB_SHARED &&
1609                     tmp_oper->type != BTRFS_QGROUP_OPER_SUB_EXCL)
1610                         goto next;
1611                 qg = find_qgroup_rb(fs_info, tmp_oper->ref_root);
1612                 if (!qg)
1613                         goto next;
1614                 ret = ulist_add(qgroups, qg->qgroupid, ptr_to_u64(qg),
1615                                 GFP_ATOMIC);
1616                 if (ret) {
1617                         if (ret < 0)
1618                                 return ret;
1619                         /*
1620                          * We only want to increase old_roots if this qgroup is
1621                          * not already in the list of qgroups.  If it is already
1622                          * there then that means it must have been re-added or
1623                          * the delete will be discarded because we had an
1624                          * existing ref that we haven't looked up yet.  In this
1625                          * case we don't want to increase old_roots.  So if ret
1626                          * == 1 then we know that this is the first time we've
1627                          * seen this qgroup and we can bump the old_roots.
1628                          */
1629                         (*old_roots)++;
1630                         ret = ulist_add(tmp, qg->qgroupid, ptr_to_u64(qg),
1631                                         GFP_ATOMIC);
1632                         if (ret < 0)
1633                                 return ret;
1634                 }
1635 next:
1636                 spin_lock(&fs_info->qgroup_op_lock);
1637                 n = rb_next(&tmp_oper->n);
1638                 spin_unlock(&fs_info->qgroup_op_lock);
1639                 if (!n)
1640                         break;
1641                 tmp_oper = rb_entry(n, struct btrfs_qgroup_operation, n);
1642         }
1643
1644         /* Ok now process the qgroups we found */
1645         ULIST_ITER_INIT(&uiter);
1646         while ((unode = ulist_next(tmp, &uiter))) {
1647                 struct btrfs_qgroup_list *glist;
1648
1649                 qg = u64_to_ptr(unode->aux);
1650                 if (qg->old_refcnt < seq)
1651                         qg->old_refcnt = seq + 1;
1652                 else
1653                         qg->old_refcnt++;
1654                 if (qg->new_refcnt < seq)
1655                         qg->new_refcnt = seq + 1;
1656                 else
1657                         qg->new_refcnt++;
1658                 list_for_each_entry(glist, &qg->groups, next_group) {
1659                         ret = ulist_add(qgroups, glist->group->qgroupid,
1660                                         ptr_to_u64(glist->group), GFP_ATOMIC);
1661                         if (ret < 0)
1662                                 return ret;
1663                         ret = ulist_add(tmp, glist->group->qgroupid,
1664                                         ptr_to_u64(glist->group), GFP_ATOMIC);
1665                         if (ret < 0)
1666                                 return ret;
1667                 }
1668         }
1669         return 0;
1670 }
1671
1672 /* Add refcnt for the newly added reference. */
1673 static int qgroup_calc_new_refcnt(struct btrfs_fs_info *fs_info,
1674                                   struct btrfs_qgroup_operation *oper,
1675                                   struct btrfs_qgroup *qgroup,
1676                                   struct ulist *tmp, struct ulist *qgroups,
1677                                   u64 seq)
1678 {
1679         struct ulist_node *unode;
1680         struct ulist_iterator uiter;
1681         struct btrfs_qgroup *qg;
1682         int ret;
1683
1684         ulist_reinit(tmp);
1685         ret = ulist_add(qgroups, qgroup->qgroupid, ptr_to_u64(qgroup),
1686                         GFP_ATOMIC);
1687         if (ret < 0)
1688                 return ret;
1689         ret = ulist_add(tmp, qgroup->qgroupid, ptr_to_u64(qgroup),
1690                         GFP_ATOMIC);
1691         if (ret < 0)
1692                 return ret;
1693         ULIST_ITER_INIT(&uiter);
1694         while ((unode = ulist_next(tmp, &uiter))) {
1695                 struct btrfs_qgroup_list *glist;
1696
1697                 qg = u64_to_ptr(unode->aux);
1698                 if (oper->type == BTRFS_QGROUP_OPER_ADD_SHARED) {
1699                         if (qg->new_refcnt < seq)
1700                                 qg->new_refcnt = seq + 1;
1701                         else
1702                                 qg->new_refcnt++;
1703                 } else {
1704                         if (qg->old_refcnt < seq)
1705                                 qg->old_refcnt = seq + 1;
1706                         else
1707                                 qg->old_refcnt++;
1708                 }
1709                 list_for_each_entry(glist, &qg->groups, next_group) {
1710                         ret = ulist_add(tmp, glist->group->qgroupid,
1711                                         ptr_to_u64(glist->group), GFP_ATOMIC);
1712                         if (ret < 0)
1713                                 return ret;
1714                         ret = ulist_add(qgroups, glist->group->qgroupid,
1715                                         ptr_to_u64(glist->group), GFP_ATOMIC);
1716                         if (ret < 0)
1717                                 return ret;
1718                 }
1719         }
1720         return 0;
1721 }
1722
1723 /*
1724  * This adjusts the counters for all referenced qgroups if need be.
1725  */
1726 static int qgroup_adjust_counters(struct btrfs_fs_info *fs_info,
1727                                   u64 root_to_skip, u64 num_bytes,
1728                                   struct ulist *qgroups, u64 seq,
1729                                   int old_roots, int new_roots, int rescan)
1730 {
1731         struct ulist_node *unode;
1732         struct ulist_iterator uiter;
1733         struct btrfs_qgroup *qg;
1734         u64 cur_new_count, cur_old_count;
1735
1736         ULIST_ITER_INIT(&uiter);
1737         while ((unode = ulist_next(qgroups, &uiter))) {
1738                 bool dirty = false;
1739
1740                 qg = u64_to_ptr(unode->aux);
1741                 /*
1742                  * Wasn't referenced before but is now, add to the reference
1743                  * counters.
1744                  */
1745                 if (qg->old_refcnt <= seq && qg->new_refcnt > seq) {
1746                         qg->rfer += num_bytes;
1747                         qg->rfer_cmpr += num_bytes;
1748                         dirty = true;
1749                 }
1750
1751                 /*
1752                  * Was referenced before but isn't now, subtract from the
1753                  * reference counters.
1754                  */
1755                 if (qg->old_refcnt > seq && qg->new_refcnt <= seq) {
1756                         qg->rfer -= num_bytes;
1757                         qg->rfer_cmpr -= num_bytes;
1758                         dirty = true;
1759                 }
1760
1761                 if (qg->old_refcnt < seq)
1762                         cur_old_count = 0;
1763                 else
1764                         cur_old_count = qg->old_refcnt - seq;
1765                 if (qg->new_refcnt < seq)
1766                         cur_new_count = 0;
1767                 else
1768                         cur_new_count = qg->new_refcnt - seq;
1769
1770                 /*
1771                  * If our refcount was the same as the roots previously but our
1772                  * new count isn't the same as the number of roots now then we
1773                  * went from having a exclusive reference on this range to not.
1774                  */
1775                 if (old_roots && cur_old_count == old_roots &&
1776                     (cur_new_count != new_roots || new_roots == 0)) {
1777                         WARN_ON(cur_new_count != new_roots && new_roots == 0);
1778                         qg->excl -= num_bytes;
1779                         qg->excl_cmpr -= num_bytes;
1780                         dirty = true;
1781                 }
1782
1783                 /*
1784                  * If we didn't reference all the roots before but now we do we
1785                  * have an exclusive reference to this range.
1786                  */
1787                 if ((!old_roots || (old_roots && cur_old_count != old_roots))
1788                     && cur_new_count == new_roots) {
1789                         qg->excl += num_bytes;
1790                         qg->excl_cmpr += num_bytes;
1791                         dirty = true;
1792                 }
1793
1794                 if (dirty)
1795                         qgroup_dirty(fs_info, qg);
1796         }
1797         return 0;
1798 }
1799
1800 /*
1801  * If we removed a data extent and there were other references for that bytenr
1802  * then we need to lookup all referenced roots to make sure we still don't
1803  * reference this bytenr.  If we do then we can just discard this operation.
1804  */
1805 static int check_existing_refs(struct btrfs_trans_handle *trans,
1806                                struct btrfs_fs_info *fs_info,
1807                                struct btrfs_qgroup_operation *oper)
1808 {
1809         struct ulist *roots = NULL;
1810         struct ulist_node *unode;
1811         struct ulist_iterator uiter;
1812         int ret = 0;
1813
1814         ret = btrfs_find_all_roots(trans, fs_info, oper->bytenr,
1815                                    oper->elem.seq, &roots);
1816         if (ret < 0)
1817                 return ret;
1818         ret = 0;
1819
1820         ULIST_ITER_INIT(&uiter);
1821         while ((unode = ulist_next(roots, &uiter))) {
1822                 if (unode->val == oper->ref_root) {
1823                         ret = 1;
1824                         break;
1825                 }
1826         }
1827         ulist_free(roots);
1828         btrfs_put_tree_mod_seq(fs_info, &oper->elem);
1829
1830         return ret;
1831 }
1832
1833 /*
1834  * If we share a reference across multiple roots then we may need to adjust
1835  * various qgroups referenced and exclusive counters.  The basic premise is this
1836  *
1837  * 1) We have seq to represent a 0 count.  Instead of looping through all of the
1838  * qgroups and resetting their refcount to 0 we just constantly bump this
1839  * sequence number to act as the base reference count.  This means that if
1840  * anybody is equal to or below this sequence they were never referenced.  We
1841  * jack this sequence up by the number of roots we found each time in order to
1842  * make sure we don't have any overlap.
1843  *
1844  * 2) We first search all the roots that reference the area _except_ the root
1845  * we're acting on currently.  This makes up the old_refcnt of all the qgroups
1846  * before.
1847  *
1848  * 3) We walk all of the qgroups referenced by the root we are currently acting
1849  * on, and will either adjust old_refcnt in the case of a removal or the
1850  * new_refcnt in the case of an addition.
1851  *
1852  * 4) Finally we walk all the qgroups that are referenced by this range
1853  * including the root we are acting on currently.  We will adjust the counters
1854  * based on the number of roots we had and will have after this operation.
1855  *
1856  * Take this example as an illustration
1857  *
1858  *                      [qgroup 1/0]
1859  *                   /         |          \
1860  *              [qg 0/0]   [qg 0/1]     [qg 0/2]
1861  *                 \          |            /
1862  *                [        extent           ]
1863  *
1864  * Say we are adding a reference that is covered by qg 0/0.  The first step
1865  * would give a refcnt of 1 to qg 0/1 and 0/2 and a refcnt of 2 to qg 1/0 with
1866  * old_roots being 2.  Because it is adding new_roots will be 1.  We then go
1867  * through qg 0/0 which will get the new_refcnt set to 1 and add 1 to qg 1/0's
1868  * new_refcnt, bringing it to 3.  We then walk through all of the qgroups, we
1869  * notice that the old refcnt for qg 0/0 < the new refcnt, so we added a
1870  * reference and thus must add the size to the referenced bytes.  Everything
1871  * else is the same so nothing else changes.
1872  */
1873 static int qgroup_shared_accounting(struct btrfs_trans_handle *trans,
1874                                     struct btrfs_fs_info *fs_info,
1875                                     struct btrfs_qgroup_operation *oper)
1876 {
1877         struct ulist *roots = NULL;
1878         struct ulist *qgroups, *tmp;
1879         struct btrfs_qgroup *qgroup;
1880         struct seq_list elem = SEQ_LIST_INIT(elem);
1881         u64 seq;
1882         int old_roots = 0;
1883         int new_roots = 0;
1884         int ret = 0;
1885
1886         if (oper->elem.seq) {
1887                 ret = check_existing_refs(trans, fs_info, oper);
1888                 if (ret < 0)
1889                         return ret;
1890                 if (ret)
1891                         return 0;
1892         }
1893
1894         qgroups = ulist_alloc(GFP_NOFS);
1895         if (!qgroups)
1896                 return -ENOMEM;
1897
1898         tmp = ulist_alloc(GFP_NOFS);
1899         if (!tmp) {
1900                 ulist_free(qgroups);
1901                 return -ENOMEM;
1902         }
1903
1904         btrfs_get_tree_mod_seq(fs_info, &elem);
1905         ret = btrfs_find_all_roots(trans, fs_info, oper->bytenr, elem.seq,
1906                                    &roots);
1907         btrfs_put_tree_mod_seq(fs_info, &elem);
1908         if (ret < 0) {
1909                 ulist_free(qgroups);
1910                 ulist_free(tmp);
1911                 return ret;
1912         }
1913         spin_lock(&fs_info->qgroup_lock);
1914         qgroup = find_qgroup_rb(fs_info, oper->ref_root);
1915         if (!qgroup)
1916                 goto out;
1917         seq = fs_info->qgroup_seq;
1918
1919         /*
1920          * So roots is the list of all the roots currently pointing at the
1921          * bytenr, including the ref we are adding if we are adding, or not if
1922          * we are removing a ref.  So we pass in the ref_root to skip that root
1923          * in our calculations.  We set old_refnct and new_refcnt cause who the
1924          * hell knows what everything looked like before, and it doesn't matter
1925          * except...
1926          */
1927         ret = qgroup_calc_old_refcnt(fs_info, oper->ref_root, tmp, roots, qgroups,
1928                                      seq, &old_roots, 0);
1929         if (ret < 0)
1930                 goto out;
1931
1932         /*
1933          * Now adjust the refcounts of the qgroups that care about this
1934          * reference, either the old_count in the case of removal or new_count
1935          * in the case of an addition.
1936          */
1937         ret = qgroup_calc_new_refcnt(fs_info, oper, qgroup, tmp, qgroups,
1938                                      seq);
1939         if (ret < 0)
1940                 goto out;
1941
1942         /*
1943          * ...in the case of removals.  If we had a removal before we got around
1944          * to processing this operation then we need to find that guy and count
1945          * his references as if they really existed so we don't end up screwing
1946          * up the exclusive counts.  Then whenever we go to process the delete
1947          * everything will be grand and we can account for whatever exclusive
1948          * changes need to be made there.  We also have to pass in old_roots so
1949          * we have an accurate count of the roots as it pertains to this
1950          * operations view of the world.
1951          */
1952         ret = qgroup_account_deleted_refs(fs_info, oper, tmp, qgroups, seq,
1953                                           &old_roots);
1954         if (ret < 0)
1955                 goto out;
1956
1957         /*
1958          * We are adding our root, need to adjust up the number of roots,
1959          * otherwise old_roots is the number of roots we want.
1960          */
1961         if (oper->type == BTRFS_QGROUP_OPER_ADD_SHARED) {
1962                 new_roots = old_roots + 1;
1963         } else {
1964                 new_roots = old_roots;
1965                 old_roots++;
1966         }
1967         fs_info->qgroup_seq += old_roots + 1;
1968
1969
1970         /*
1971          * And now the magic happens, bless Arne for having a pretty elegant
1972          * solution for this.
1973          */
1974         qgroup_adjust_counters(fs_info, oper->ref_root, oper->num_bytes,
1975                                qgroups, seq, old_roots, new_roots, 0);
1976 out:
1977         spin_unlock(&fs_info->qgroup_lock);
1978         ulist_free(qgroups);
1979         ulist_free(roots);
1980         ulist_free(tmp);
1981         return ret;
1982 }
1983
1984 /*
1985  * Process a reference to a shared subtree. This type of operation is
1986  * queued during snapshot removal when we encounter extents which are
1987  * shared between more than one root.
1988  */
1989 static int qgroup_subtree_accounting(struct btrfs_trans_handle *trans,
1990                                      struct btrfs_fs_info *fs_info,
1991                                      struct btrfs_qgroup_operation *oper)
1992 {
1993         struct ulist *roots = NULL;
1994         struct ulist_node *unode;
1995         struct ulist_iterator uiter;
1996         struct btrfs_qgroup_list *glist;
1997         struct ulist *parents;
1998         int ret = 0;
1999         int err;
2000         struct btrfs_qgroup *qg;
2001         u64 root_obj = 0;
2002         struct seq_list elem = SEQ_LIST_INIT(elem);
2003
2004         parents = ulist_alloc(GFP_NOFS);
2005         if (!parents)
2006                 return -ENOMEM;
2007
2008         btrfs_get_tree_mod_seq(fs_info, &elem);
2009         ret = btrfs_find_all_roots(trans, fs_info, oper->bytenr,
2010                                    elem.seq, &roots);
2011         btrfs_put_tree_mod_seq(fs_info, &elem);
2012         if (ret < 0)
2013                 goto out;
2014
2015         if (roots->nnodes != 1)
2016                 goto out;
2017
2018         ULIST_ITER_INIT(&uiter);
2019         unode = ulist_next(roots, &uiter); /* Only want 1 so no need to loop */
2020         /*
2021          * If we find our ref root then that means all refs
2022          * this extent has to the root have not yet been
2023          * deleted. In that case, we do nothing and let the
2024          * last ref for this bytenr drive our update.
2025          *
2026          * This can happen for example if an extent is
2027          * referenced multiple times in a snapshot (clone,
2028          * etc). If we are in the middle of snapshot removal,
2029          * queued updates for such an extent will find the
2030          * root if we have not yet finished removing the
2031          * snapshot.
2032          */
2033         if (unode->val == oper->ref_root)
2034                 goto out;
2035
2036         root_obj = unode->val;
2037         BUG_ON(!root_obj);
2038
2039         spin_lock(&fs_info->qgroup_lock);
2040         qg = find_qgroup_rb(fs_info, root_obj);
2041         if (!qg)
2042                 goto out_unlock;
2043
2044         qg->excl += oper->num_bytes;
2045         qg->excl_cmpr += oper->num_bytes;
2046         qgroup_dirty(fs_info, qg);
2047
2048         /*
2049          * Adjust counts for parent groups. First we find all
2050          * parents, then in the 2nd loop we do the adjustment
2051          * while adding parents of the parents to our ulist.
2052          */
2053         list_for_each_entry(glist, &qg->groups, next_group) {
2054                 err = ulist_add(parents, glist->group->qgroupid,
2055                                 ptr_to_u64(glist->group), GFP_ATOMIC);
2056                 if (err < 0) {
2057                         ret = err;
2058                         goto out_unlock;
2059                 }
2060         }
2061
2062         ULIST_ITER_INIT(&uiter);
2063         while ((unode = ulist_next(parents, &uiter))) {
2064                 qg = u64_to_ptr(unode->aux);
2065                 qg->excl += oper->num_bytes;
2066                 qg->excl_cmpr += oper->num_bytes;
2067                 qgroup_dirty(fs_info, qg);
2068
2069                 /* Add any parents of the parents */
2070                 list_for_each_entry(glist, &qg->groups, next_group) {
2071                         err = ulist_add(parents, glist->group->qgroupid,
2072                                         ptr_to_u64(glist->group), GFP_ATOMIC);
2073                         if (err < 0) {
2074                                 ret = err;
2075                                 goto out_unlock;
2076                         }
2077                 }
2078         }
2079
2080 out_unlock:
2081         spin_unlock(&fs_info->qgroup_lock);
2082
2083 out:
2084         ulist_free(roots);
2085         ulist_free(parents);
2086         return ret;
2087 }
2088
2089 /*
2090  * btrfs_qgroup_account_ref is called for every ref that is added to or deleted
2091  * from the fs. First, all roots referencing the extent are searched, and
2092  * then the space is accounted accordingly to the different roots. The
2093  * accounting algorithm works in 3 steps documented inline.
2094  */
2095 static int btrfs_qgroup_account(struct btrfs_trans_handle *trans,
2096                                 struct btrfs_fs_info *fs_info,
2097                                 struct btrfs_qgroup_operation *oper)
2098 {
2099         int ret = 0;
2100
2101         if (!fs_info->quota_enabled)
2102                 return 0;
2103
2104         BUG_ON(!fs_info->quota_root);
2105
2106         mutex_lock(&fs_info->qgroup_rescan_lock);
2107         if (fs_info->qgroup_flags & BTRFS_QGROUP_STATUS_FLAG_RESCAN) {
2108                 if (fs_info->qgroup_rescan_progress.objectid <= oper->bytenr) {
2109                         mutex_unlock(&fs_info->qgroup_rescan_lock);
2110                         return 0;
2111                 }
2112         }
2113         mutex_unlock(&fs_info->qgroup_rescan_lock);
2114
2115         ASSERT(is_fstree(oper->ref_root));
2116
2117         trace_btrfs_qgroup_account(oper);
2118
2119         switch (oper->type) {
2120         case BTRFS_QGROUP_OPER_ADD_EXCL:
2121         case BTRFS_QGROUP_OPER_SUB_EXCL:
2122                 ret = qgroup_excl_accounting(fs_info, oper);
2123                 break;
2124         case BTRFS_QGROUP_OPER_ADD_SHARED:
2125         case BTRFS_QGROUP_OPER_SUB_SHARED:
2126                 ret = qgroup_shared_accounting(trans, fs_info, oper);
2127                 break;
2128         case BTRFS_QGROUP_OPER_SUB_SUBTREE:
2129                 ret = qgroup_subtree_accounting(trans, fs_info, oper);
2130                 break;
2131         default:
2132                 ASSERT(0);
2133         }
2134         return ret;
2135 }
2136
2137 /*
2138  * Needs to be called everytime we run delayed refs, even if there is an error
2139  * in order to cleanup outstanding operations.
2140  */
2141 int btrfs_delayed_qgroup_accounting(struct btrfs_trans_handle *trans,
2142                                     struct btrfs_fs_info *fs_info)
2143 {
2144         struct btrfs_qgroup_operation *oper;
2145         int ret = 0;
2146
2147         while (!list_empty(&trans->qgroup_ref_list)) {
2148                 oper = list_first_entry(&trans->qgroup_ref_list,
2149                                         struct btrfs_qgroup_operation, list);
2150                 list_del_init(&oper->list);
2151                 if (!ret || !trans->aborted)
2152                         ret = btrfs_qgroup_account(trans, fs_info, oper);
2153                 spin_lock(&fs_info->qgroup_op_lock);
2154                 rb_erase(&oper->n, &fs_info->qgroup_op_tree);
2155                 spin_unlock(&fs_info->qgroup_op_lock);
2156                 btrfs_put_tree_mod_seq(fs_info, &oper->elem);
2157                 kfree(oper);
2158         }
2159         return ret;
2160 }
2161
2162 /*
2163  * called from commit_transaction. Writes all changed qgroups to disk.
2164  */
2165 int btrfs_run_qgroups(struct btrfs_trans_handle *trans,
2166                       struct btrfs_fs_info *fs_info)
2167 {
2168         struct btrfs_root *quota_root = fs_info->quota_root;
2169         int ret = 0;
2170         int start_rescan_worker = 0;
2171
2172         if (!quota_root)
2173                 goto out;
2174
2175         if (!fs_info->quota_enabled && fs_info->pending_quota_state)
2176                 start_rescan_worker = 1;
2177
2178         fs_info->quota_enabled = fs_info->pending_quota_state;
2179
2180         spin_lock(&fs_info->qgroup_lock);
2181         while (!list_empty(&fs_info->dirty_qgroups)) {
2182                 struct btrfs_qgroup *qgroup;
2183                 qgroup = list_first_entry(&fs_info->dirty_qgroups,
2184                                           struct btrfs_qgroup, dirty);
2185                 list_del_init(&qgroup->dirty);
2186                 spin_unlock(&fs_info->qgroup_lock);
2187                 ret = update_qgroup_info_item(trans, quota_root, qgroup);
2188                 if (ret)
2189                         fs_info->qgroup_flags |=
2190                                         BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
2191                 ret = update_qgroup_limit_item(trans, quota_root, qgroup);
2192                 if (ret)
2193                         fs_info->qgroup_flags |=
2194                                         BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
2195                 spin_lock(&fs_info->qgroup_lock);
2196         }
2197         if (fs_info->quota_enabled)
2198                 fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_ON;
2199         else
2200                 fs_info->qgroup_flags &= ~BTRFS_QGROUP_STATUS_FLAG_ON;
2201         spin_unlock(&fs_info->qgroup_lock);
2202
2203         ret = update_qgroup_status_item(trans, fs_info, quota_root);
2204         if (ret)
2205                 fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
2206
2207         if (!ret && start_rescan_worker) {
2208                 ret = qgroup_rescan_init(fs_info, 0, 1);
2209                 if (!ret) {
2210                         qgroup_rescan_zero_tracking(fs_info);
2211                         btrfs_queue_work(fs_info->qgroup_rescan_workers,
2212                                          &fs_info->qgroup_rescan_work);
2213                 }
2214                 ret = 0;
2215         }
2216
2217 out:
2218
2219         return ret;
2220 }
2221
2222 /*
2223  * copy the acounting information between qgroups. This is necessary when a
2224  * snapshot or a subvolume is created
2225  */
2226 int btrfs_qgroup_inherit(struct btrfs_trans_handle *trans,
2227                          struct btrfs_fs_info *fs_info, u64 srcid, u64 objectid,
2228                          struct btrfs_qgroup_inherit *inherit)
2229 {
2230         int ret = 0;
2231         int i;
2232         u64 *i_qgroups;
2233         struct btrfs_root *quota_root = fs_info->quota_root;
2234         struct btrfs_qgroup *srcgroup;
2235         struct btrfs_qgroup *dstgroup;
2236         u32 level_size = 0;
2237         u64 nums;
2238
2239         mutex_lock(&fs_info->qgroup_ioctl_lock);
2240         if (!fs_info->quota_enabled)
2241                 goto out;
2242
2243         if (!quota_root) {
2244                 ret = -EINVAL;
2245                 goto out;
2246         }
2247
2248         if (inherit) {
2249                 i_qgroups = (u64 *)(inherit + 1);
2250                 nums = inherit->num_qgroups + 2 * inherit->num_ref_copies +
2251                        2 * inherit->num_excl_copies;
2252                 for (i = 0; i < nums; ++i) {
2253                         srcgroup = find_qgroup_rb(fs_info, *i_qgroups);
2254                         if (!srcgroup) {
2255                                 ret = -EINVAL;
2256                                 goto out;
2257                         }
2258
2259                         if ((srcgroup->qgroupid >> 48) <= (objectid >> 48)) {
2260                                 ret = -EINVAL;
2261                                 goto out;
2262                         }
2263                         ++i_qgroups;
2264                 }
2265         }
2266
2267         /*
2268          * create a tracking group for the subvol itself
2269          */
2270         ret = add_qgroup_item(trans, quota_root, objectid);
2271         if (ret)
2272                 goto out;
2273
2274         if (srcid) {
2275                 struct btrfs_root *srcroot;
2276                 struct btrfs_key srckey;
2277
2278                 srckey.objectid = srcid;
2279                 srckey.type = BTRFS_ROOT_ITEM_KEY;
2280                 srckey.offset = (u64)-1;
2281                 srcroot = btrfs_read_fs_root_no_name(fs_info, &srckey);
2282                 if (IS_ERR(srcroot)) {
2283                         ret = PTR_ERR(srcroot);
2284                         goto out;
2285                 }
2286
2287                 rcu_read_lock();
2288                 level_size = srcroot->nodesize;
2289                 rcu_read_unlock();
2290         }
2291
2292         /*
2293          * add qgroup to all inherited groups
2294          */
2295         if (inherit) {
2296                 i_qgroups = (u64 *)(inherit + 1);
2297                 for (i = 0; i < inherit->num_qgroups; ++i) {
2298                         ret = add_qgroup_relation_item(trans, quota_root,
2299                                                        objectid, *i_qgroups);
2300                         if (ret)
2301                                 goto out;
2302                         ret = add_qgroup_relation_item(trans, quota_root,
2303                                                        *i_qgroups, objectid);
2304                         if (ret)
2305                                 goto out;
2306                         ++i_qgroups;
2307                 }
2308         }
2309
2310
2311         spin_lock(&fs_info->qgroup_lock);
2312
2313         dstgroup = add_qgroup_rb(fs_info, objectid);
2314         if (IS_ERR(dstgroup)) {
2315                 ret = PTR_ERR(dstgroup);
2316                 goto unlock;
2317         }
2318
2319         if (inherit && inherit->flags & BTRFS_QGROUP_INHERIT_SET_LIMITS) {
2320                 dstgroup->lim_flags = inherit->lim.flags;
2321                 dstgroup->max_rfer = inherit->lim.max_rfer;
2322                 dstgroup->max_excl = inherit->lim.max_excl;
2323                 dstgroup->rsv_rfer = inherit->lim.rsv_rfer;
2324                 dstgroup->rsv_excl = inherit->lim.rsv_excl;
2325
2326                 ret = update_qgroup_limit_item(trans, quota_root, dstgroup);
2327                 if (ret) {
2328                         fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
2329                         btrfs_info(fs_info, "unable to update quota limit for %llu",
2330                                dstgroup->qgroupid);
2331                         goto unlock;
2332                 }
2333         }
2334
2335         if (srcid) {
2336                 srcgroup = find_qgroup_rb(fs_info, srcid);
2337                 if (!srcgroup)
2338                         goto unlock;
2339
2340                 /*
2341                  * We call inherit after we clone the root in order to make sure
2342                  * our counts don't go crazy, so at this point the only
2343                  * difference between the two roots should be the root node.
2344                  */
2345                 dstgroup->rfer = srcgroup->rfer;
2346                 dstgroup->rfer_cmpr = srcgroup->rfer_cmpr;
2347                 dstgroup->excl = level_size;
2348                 dstgroup->excl_cmpr = level_size;
2349                 srcgroup->excl = level_size;
2350                 srcgroup->excl_cmpr = level_size;
2351
2352                 /* inherit the limit info */
2353                 dstgroup->lim_flags = srcgroup->lim_flags;
2354                 dstgroup->max_rfer = srcgroup->max_rfer;
2355                 dstgroup->max_excl = srcgroup->max_excl;
2356                 dstgroup->rsv_rfer = srcgroup->rsv_rfer;
2357                 dstgroup->rsv_excl = srcgroup->rsv_excl;
2358
2359                 qgroup_dirty(fs_info, dstgroup);
2360                 qgroup_dirty(fs_info, srcgroup);
2361         }
2362
2363         if (!inherit)
2364                 goto unlock;
2365
2366         i_qgroups = (u64 *)(inherit + 1);
2367         for (i = 0; i < inherit->num_qgroups; ++i) {
2368                 ret = add_relation_rb(quota_root->fs_info, objectid,
2369                                       *i_qgroups);
2370                 if (ret)
2371                         goto unlock;
2372                 ++i_qgroups;
2373         }
2374
2375         for (i = 0; i <  inherit->num_ref_copies; ++i) {
2376                 struct btrfs_qgroup *src;
2377                 struct btrfs_qgroup *dst;
2378
2379                 src = find_qgroup_rb(fs_info, i_qgroups[0]);
2380                 dst = find_qgroup_rb(fs_info, i_qgroups[1]);
2381
2382                 if (!src || !dst) {
2383                         ret = -EINVAL;
2384                         goto unlock;
2385                 }
2386
2387                 dst->rfer = src->rfer - level_size;
2388                 dst->rfer_cmpr = src->rfer_cmpr - level_size;
2389                 i_qgroups += 2;
2390         }
2391         for (i = 0; i <  inherit->num_excl_copies; ++i) {
2392                 struct btrfs_qgroup *src;
2393                 struct btrfs_qgroup *dst;
2394
2395                 src = find_qgroup_rb(fs_info, i_qgroups[0]);
2396                 dst = find_qgroup_rb(fs_info, i_qgroups[1]);
2397
2398                 if (!src || !dst) {
2399                         ret = -EINVAL;
2400                         goto unlock;
2401                 }
2402
2403                 dst->excl = src->excl + level_size;
2404                 dst->excl_cmpr = src->excl_cmpr + level_size;
2405                 i_qgroups += 2;
2406         }
2407
2408 unlock:
2409         spin_unlock(&fs_info->qgroup_lock);
2410 out:
2411         mutex_unlock(&fs_info->qgroup_ioctl_lock);
2412         return ret;
2413 }
2414
2415 int btrfs_qgroup_reserve(struct btrfs_root *root, u64 num_bytes)
2416 {
2417         struct btrfs_root *quota_root;
2418         struct btrfs_qgroup *qgroup;
2419         struct btrfs_fs_info *fs_info = root->fs_info;
2420         u64 ref_root = root->root_key.objectid;
2421         int ret = 0;
2422         struct ulist_node *unode;
2423         struct ulist_iterator uiter;
2424
2425         if (!is_fstree(ref_root))
2426                 return 0;
2427
2428         if (num_bytes == 0)
2429                 return 0;
2430
2431         spin_lock(&fs_info->qgroup_lock);
2432         quota_root = fs_info->quota_root;
2433         if (!quota_root)
2434                 goto out;
2435
2436         qgroup = find_qgroup_rb(fs_info, ref_root);
2437         if (!qgroup)
2438                 goto out;
2439
2440         /*
2441          * in a first step, we check all affected qgroups if any limits would
2442          * be exceeded
2443          */
2444         ulist_reinit(fs_info->qgroup_ulist);
2445         ret = ulist_add(fs_info->qgroup_ulist, qgroup->qgroupid,
2446                         (uintptr_t)qgroup, GFP_ATOMIC);
2447         if (ret < 0)
2448                 goto out;
2449         ULIST_ITER_INIT(&uiter);
2450         while ((unode = ulist_next(fs_info->qgroup_ulist, &uiter))) {
2451                 struct btrfs_qgroup *qg;
2452                 struct btrfs_qgroup_list *glist;
2453
2454                 qg = u64_to_ptr(unode->aux);
2455
2456                 if ((qg->lim_flags & BTRFS_QGROUP_LIMIT_MAX_RFER) &&
2457                     qg->reserved + (s64)qg->rfer + num_bytes >
2458                     qg->max_rfer) {
2459                         ret = -EDQUOT;
2460                         goto out;
2461                 }
2462
2463                 if ((qg->lim_flags & BTRFS_QGROUP_LIMIT_MAX_EXCL) &&
2464                     qg->reserved + (s64)qg->excl + num_bytes >
2465                     qg->max_excl) {
2466                         ret = -EDQUOT;
2467                         goto out;
2468                 }
2469
2470                 list_for_each_entry(glist, &qg->groups, next_group) {
2471                         ret = ulist_add(fs_info->qgroup_ulist,
2472                                         glist->group->qgroupid,
2473                                         (uintptr_t)glist->group, GFP_ATOMIC);
2474                         if (ret < 0)
2475                                 goto out;
2476                 }
2477         }
2478         ret = 0;
2479         /*
2480          * no limits exceeded, now record the reservation into all qgroups
2481          */
2482         ULIST_ITER_INIT(&uiter);
2483         while ((unode = ulist_next(fs_info->qgroup_ulist, &uiter))) {
2484                 struct btrfs_qgroup *qg;
2485
2486                 qg = u64_to_ptr(unode->aux);
2487
2488                 qg->reserved += num_bytes;
2489         }
2490
2491 out:
2492         spin_unlock(&fs_info->qgroup_lock);
2493         return ret;
2494 }
2495
2496 void btrfs_qgroup_free(struct btrfs_root *root, u64 num_bytes)
2497 {
2498         struct btrfs_root *quota_root;
2499         struct btrfs_qgroup *qgroup;
2500         struct btrfs_fs_info *fs_info = root->fs_info;
2501         struct ulist_node *unode;
2502         struct ulist_iterator uiter;
2503         u64 ref_root = root->root_key.objectid;
2504         int ret = 0;
2505
2506         if (!is_fstree(ref_root))
2507                 return;
2508
2509         if (num_bytes == 0)
2510                 return;
2511
2512         spin_lock(&fs_info->qgroup_lock);
2513
2514         quota_root = fs_info->quota_root;
2515         if (!quota_root)
2516                 goto out;
2517
2518         qgroup = find_qgroup_rb(fs_info, ref_root);
2519         if (!qgroup)
2520                 goto out;
2521
2522         ulist_reinit(fs_info->qgroup_ulist);
2523         ret = ulist_add(fs_info->qgroup_ulist, qgroup->qgroupid,
2524                         (uintptr_t)qgroup, GFP_ATOMIC);
2525         if (ret < 0)
2526                 goto out;
2527         ULIST_ITER_INIT(&uiter);
2528         while ((unode = ulist_next(fs_info->qgroup_ulist, &uiter))) {
2529                 struct btrfs_qgroup *qg;
2530                 struct btrfs_qgroup_list *glist;
2531
2532                 qg = u64_to_ptr(unode->aux);
2533
2534                 qg->reserved -= num_bytes;
2535
2536                 list_for_each_entry(glist, &qg->groups, next_group) {
2537                         ret = ulist_add(fs_info->qgroup_ulist,
2538                                         glist->group->qgroupid,
2539                                         (uintptr_t)glist->group, GFP_ATOMIC);
2540                         if (ret < 0)
2541                                 goto out;
2542                 }
2543         }
2544
2545 out:
2546         spin_unlock(&fs_info->qgroup_lock);
2547 }
2548
2549 void assert_qgroups_uptodate(struct btrfs_trans_handle *trans)
2550 {
2551         if (list_empty(&trans->qgroup_ref_list) && !trans->delayed_ref_elem.seq)
2552                 return;
2553         btrfs_err(trans->root->fs_info,
2554                 "qgroups not uptodate in trans handle %p:  list is%s empty, "
2555                 "seq is %#x.%x",
2556                 trans, list_empty(&trans->qgroup_ref_list) ? "" : " not",
2557                 (u32)(trans->delayed_ref_elem.seq >> 32),
2558                 (u32)trans->delayed_ref_elem.seq);
2559         BUG();
2560 }
2561
2562 /*
2563  * returns < 0 on error, 0 when more leafs are to be scanned.
2564  * returns 1 when done.
2565  */
2566 static int
2567 qgroup_rescan_leaf(struct btrfs_fs_info *fs_info, struct btrfs_path *path,
2568                    struct btrfs_trans_handle *trans, struct ulist *qgroups,
2569                    struct ulist *tmp, struct extent_buffer *scratch_leaf)
2570 {
2571         struct btrfs_key found;
2572         struct ulist *roots = NULL;
2573         struct seq_list tree_mod_seq_elem = SEQ_LIST_INIT(tree_mod_seq_elem);
2574         u64 num_bytes;
2575         u64 seq;
2576         int new_roots;
2577         int slot;
2578         int ret;
2579
2580         path->leave_spinning = 1;
2581         mutex_lock(&fs_info->qgroup_rescan_lock);
2582         ret = btrfs_search_slot_for_read(fs_info->extent_root,
2583                                          &fs_info->qgroup_rescan_progress,
2584                                          path, 1, 0);
2585
2586         pr_debug("current progress key (%llu %u %llu), search_slot ret %d\n",
2587                  fs_info->qgroup_rescan_progress.objectid,
2588                  fs_info->qgroup_rescan_progress.type,
2589                  fs_info->qgroup_rescan_progress.offset, ret);
2590
2591         if (ret) {
2592                 /*
2593                  * The rescan is about to end, we will not be scanning any
2594                  * further blocks. We cannot unset the RESCAN flag here, because
2595                  * we want to commit the transaction if everything went well.
2596                  * To make the live accounting work in this phase, we set our
2597                  * scan progress pointer such that every real extent objectid
2598                  * will be smaller.
2599                  */
2600                 fs_info->qgroup_rescan_progress.objectid = (u64)-1;
2601                 btrfs_release_path(path);
2602                 mutex_unlock(&fs_info->qgroup_rescan_lock);
2603                 return ret;
2604         }
2605
2606         btrfs_item_key_to_cpu(path->nodes[0], &found,
2607                               btrfs_header_nritems(path->nodes[0]) - 1);
2608         fs_info->qgroup_rescan_progress.objectid = found.objectid + 1;
2609
2610         btrfs_get_tree_mod_seq(fs_info, &tree_mod_seq_elem);
2611         memcpy(scratch_leaf, path->nodes[0], sizeof(*scratch_leaf));
2612         slot = path->slots[0];
2613         btrfs_release_path(path);
2614         mutex_unlock(&fs_info->qgroup_rescan_lock);
2615
2616         for (; slot < btrfs_header_nritems(scratch_leaf); ++slot) {
2617                 btrfs_item_key_to_cpu(scratch_leaf, &found, slot);
2618                 if (found.type != BTRFS_EXTENT_ITEM_KEY &&
2619                     found.type != BTRFS_METADATA_ITEM_KEY)
2620                         continue;
2621                 if (found.type == BTRFS_METADATA_ITEM_KEY)
2622                         num_bytes = fs_info->extent_root->nodesize;
2623                 else
2624                         num_bytes = found.offset;
2625
2626                 ulist_reinit(qgroups);
2627                 ret = btrfs_find_all_roots(NULL, fs_info, found.objectid, 0,
2628                                            &roots);
2629                 if (ret < 0)
2630                         goto out;
2631                 spin_lock(&fs_info->qgroup_lock);
2632                 seq = fs_info->qgroup_seq;
2633                 fs_info->qgroup_seq += roots->nnodes + 1; /* max refcnt */
2634
2635                 new_roots = 0;
2636                 ret = qgroup_calc_old_refcnt(fs_info, 0, tmp, roots, qgroups,
2637                                              seq, &new_roots, 1);
2638                 if (ret < 0) {
2639                         spin_unlock(&fs_info->qgroup_lock);
2640                         ulist_free(roots);
2641                         goto out;
2642                 }
2643
2644                 ret = qgroup_adjust_counters(fs_info, 0, num_bytes, qgroups,
2645                                              seq, 0, new_roots, 1);
2646                 if (ret < 0) {
2647                         spin_unlock(&fs_info->qgroup_lock);
2648                         ulist_free(roots);
2649                         goto out;
2650                 }
2651                 spin_unlock(&fs_info->qgroup_lock);
2652                 ulist_free(roots);
2653         }
2654 out:
2655         btrfs_put_tree_mod_seq(fs_info, &tree_mod_seq_elem);
2656
2657         return ret;
2658 }
2659
2660 static void btrfs_qgroup_rescan_worker(struct btrfs_work *work)
2661 {
2662         struct btrfs_fs_info *fs_info = container_of(work, struct btrfs_fs_info,
2663                                                      qgroup_rescan_work);
2664         struct btrfs_path *path;
2665         struct btrfs_trans_handle *trans = NULL;
2666         struct ulist *tmp = NULL, *qgroups = NULL;
2667         struct extent_buffer *scratch_leaf = NULL;
2668         int err = -ENOMEM;
2669         int ret = 0;
2670
2671         path = btrfs_alloc_path();
2672         if (!path)
2673                 goto out;
2674         qgroups = ulist_alloc(GFP_NOFS);
2675         if (!qgroups)
2676                 goto out;
2677         tmp = ulist_alloc(GFP_NOFS);
2678         if (!tmp)
2679                 goto out;
2680         scratch_leaf = kmalloc(sizeof(*scratch_leaf), GFP_NOFS);
2681         if (!scratch_leaf)
2682                 goto out;
2683
2684         err = 0;
2685         while (!err) {
2686                 trans = btrfs_start_transaction(fs_info->fs_root, 0);
2687                 if (IS_ERR(trans)) {
2688                         err = PTR_ERR(trans);
2689                         break;
2690                 }
2691                 if (!fs_info->quota_enabled) {
2692                         err = -EINTR;
2693                 } else {
2694                         err = qgroup_rescan_leaf(fs_info, path, trans,
2695                                                  qgroups, tmp, scratch_leaf);
2696                 }
2697                 if (err > 0)
2698                         btrfs_commit_transaction(trans, fs_info->fs_root);
2699                 else
2700                         btrfs_end_transaction(trans, fs_info->fs_root);
2701         }
2702
2703 out:
2704         kfree(scratch_leaf);
2705         ulist_free(qgroups);
2706         ulist_free(tmp);
2707         btrfs_free_path(path);
2708
2709         mutex_lock(&fs_info->qgroup_rescan_lock);
2710         fs_info->qgroup_flags &= ~BTRFS_QGROUP_STATUS_FLAG_RESCAN;
2711
2712         if (err > 0 &&
2713             fs_info->qgroup_flags & BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT) {
2714                 fs_info->qgroup_flags &= ~BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
2715         } else if (err < 0) {
2716                 fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
2717         }
2718         mutex_unlock(&fs_info->qgroup_rescan_lock);
2719
2720         /*
2721          * only update status, since the previous part has alreay updated the
2722          * qgroup info.
2723          */
2724         trans = btrfs_start_transaction(fs_info->quota_root, 1);
2725         if (IS_ERR(trans)) {
2726                 err = PTR_ERR(trans);
2727                 btrfs_err(fs_info,
2728                           "fail to start transaction for status update: %d\n",
2729                           err);
2730                 goto done;
2731         }
2732         ret = update_qgroup_status_item(trans, fs_info, fs_info->quota_root);
2733         if (ret < 0) {
2734                 err = ret;
2735                 btrfs_err(fs_info, "fail to update qgroup status: %d\n",
2736                           err);
2737                 btrfs_abort_transaction(trans, fs_info->quota_root, err);
2738                 goto done;
2739         }
2740         btrfs_end_transaction(trans, fs_info->quota_root);
2741
2742         if (err >= 0) {
2743                 btrfs_info(fs_info, "qgroup scan completed%s",
2744                         err > 0 ? " (inconsistency flag cleared)" : "");
2745         } else {
2746                 btrfs_err(fs_info, "qgroup scan failed with %d", err);
2747         }
2748
2749 done:
2750         complete_all(&fs_info->qgroup_rescan_completion);
2751 }
2752
2753 /*
2754  * Checks that (a) no rescan is running and (b) quota is enabled. Allocates all
2755  * memory required for the rescan context.
2756  */
2757 static int
2758 qgroup_rescan_init(struct btrfs_fs_info *fs_info, u64 progress_objectid,
2759                    int init_flags)
2760 {
2761         int ret = 0;
2762
2763         if (!init_flags &&
2764             (!(fs_info->qgroup_flags & BTRFS_QGROUP_STATUS_FLAG_RESCAN) ||
2765              !(fs_info->qgroup_flags & BTRFS_QGROUP_STATUS_FLAG_ON))) {
2766                 ret = -EINVAL;
2767                 goto err;
2768         }
2769
2770         mutex_lock(&fs_info->qgroup_rescan_lock);
2771         spin_lock(&fs_info->qgroup_lock);
2772
2773         if (init_flags) {
2774                 if (fs_info->qgroup_flags & BTRFS_QGROUP_STATUS_FLAG_RESCAN)
2775                         ret = -EINPROGRESS;
2776                 else if (!(fs_info->qgroup_flags & BTRFS_QGROUP_STATUS_FLAG_ON))
2777                         ret = -EINVAL;
2778
2779                 if (ret) {
2780                         spin_unlock(&fs_info->qgroup_lock);
2781                         mutex_unlock(&fs_info->qgroup_rescan_lock);
2782                         goto err;
2783                 }
2784                 fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_RESCAN;
2785         }
2786
2787         memset(&fs_info->qgroup_rescan_progress, 0,
2788                 sizeof(fs_info->qgroup_rescan_progress));
2789         fs_info->qgroup_rescan_progress.objectid = progress_objectid;
2790
2791         spin_unlock(&fs_info->qgroup_lock);
2792         mutex_unlock(&fs_info->qgroup_rescan_lock);
2793
2794         init_completion(&fs_info->qgroup_rescan_completion);
2795
2796         memset(&fs_info->qgroup_rescan_work, 0,
2797                sizeof(fs_info->qgroup_rescan_work));
2798         btrfs_init_work(&fs_info->qgroup_rescan_work,
2799                         btrfs_qgroup_rescan_helper,
2800                         btrfs_qgroup_rescan_worker, NULL, NULL);
2801
2802         if (ret) {
2803 err:
2804                 btrfs_info(fs_info, "qgroup_rescan_init failed with %d", ret);
2805                 return ret;
2806         }
2807
2808         return 0;
2809 }
2810
2811 static void
2812 qgroup_rescan_zero_tracking(struct btrfs_fs_info *fs_info)
2813 {
2814         struct rb_node *n;
2815         struct btrfs_qgroup *qgroup;
2816
2817         spin_lock(&fs_info->qgroup_lock);
2818         /* clear all current qgroup tracking information */
2819         for (n = rb_first(&fs_info->qgroup_tree); n; n = rb_next(n)) {
2820                 qgroup = rb_entry(n, struct btrfs_qgroup, node);
2821                 qgroup->rfer = 0;
2822                 qgroup->rfer_cmpr = 0;
2823                 qgroup->excl = 0;
2824                 qgroup->excl_cmpr = 0;
2825         }
2826         spin_unlock(&fs_info->qgroup_lock);
2827 }
2828
2829 int
2830 btrfs_qgroup_rescan(struct btrfs_fs_info *fs_info)
2831 {
2832         int ret = 0;
2833         struct btrfs_trans_handle *trans;
2834
2835         ret = qgroup_rescan_init(fs_info, 0, 1);
2836         if (ret)
2837                 return ret;
2838
2839         /*
2840          * We have set the rescan_progress to 0, which means no more
2841          * delayed refs will be accounted by btrfs_qgroup_account_ref.
2842          * However, btrfs_qgroup_account_ref may be right after its call
2843          * to btrfs_find_all_roots, in which case it would still do the
2844          * accounting.
2845          * To solve this, we're committing the transaction, which will
2846          * ensure we run all delayed refs and only after that, we are
2847          * going to clear all tracking information for a clean start.
2848          */
2849
2850         trans = btrfs_join_transaction(fs_info->fs_root);
2851         if (IS_ERR(trans)) {
2852                 fs_info->qgroup_flags &= ~BTRFS_QGROUP_STATUS_FLAG_RESCAN;
2853                 return PTR_ERR(trans);
2854         }
2855         ret = btrfs_commit_transaction(trans, fs_info->fs_root);
2856         if (ret) {
2857                 fs_info->qgroup_flags &= ~BTRFS_QGROUP_STATUS_FLAG_RESCAN;
2858                 return ret;
2859         }
2860
2861         qgroup_rescan_zero_tracking(fs_info);
2862
2863         btrfs_queue_work(fs_info->qgroup_rescan_workers,
2864                          &fs_info->qgroup_rescan_work);
2865
2866         return 0;
2867 }
2868
2869 int btrfs_qgroup_wait_for_completion(struct btrfs_fs_info *fs_info)
2870 {
2871         int running;
2872         int ret = 0;
2873
2874         mutex_lock(&fs_info->qgroup_rescan_lock);
2875         spin_lock(&fs_info->qgroup_lock);
2876         running = fs_info->qgroup_flags & BTRFS_QGROUP_STATUS_FLAG_RESCAN;
2877         spin_unlock(&fs_info->qgroup_lock);
2878         mutex_unlock(&fs_info->qgroup_rescan_lock);
2879
2880         if (running)
2881                 ret = wait_for_completion_interruptible(
2882                                         &fs_info->qgroup_rescan_completion);
2883
2884         return ret;
2885 }
2886
2887 /*
2888  * this is only called from open_ctree where we're still single threaded, thus
2889  * locking is omitted here.
2890  */
2891 void
2892 btrfs_qgroup_rescan_resume(struct btrfs_fs_info *fs_info)
2893 {
2894         if (fs_info->qgroup_flags & BTRFS_QGROUP_STATUS_FLAG_RESCAN)
2895                 btrfs_queue_work(fs_info->qgroup_rescan_workers,
2896                                  &fs_info->qgroup_rescan_work);
2897 }