fs/btrfs/qgroup.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (C) 2011 STRATO.  All rights reserved.
   4  */
   5
   6 #include <linux/sched.h>
   7 #include <linux/pagemap.h>
   8 #include <linux/writeback.h>
   9 #include <linux/blkdev.h>
  10 #include <linux/rbtree.h>
  11 #include <linux/slab.h>
  12 #include <linux/workqueue.h>
  13 #include <linux/btrfs.h>
  14 #include <linux/sched/mm.h>
  15
  16 #include "ctree.h"
  17 #include "transaction.h"
  18 #include "disk-io.h"
  19 #include "locking.h"
  20 #include "ulist.h"
  21 #include "backref.h"
  22 #include "extent_io.h"
  23 #include "qgroup.h"
  24 #include "block-group.h"
  25 #include "sysfs.h"
  26
  27 /* TODO XXX FIXME
  28  *  - subvol delete -> delete when ref goes to 0? delete limits also?
  29  *  - reorganize keys
  30  *  - compressed
  31  *  - sync
  32  *  - copy also limits on subvol creation
  33  *  - limit
  34  *  - caches for ulists
  35  *  - performance benchmarks
  36  *  - check all ioctl parameters
  37  */
  38
  39 /*
  40  * Helpers to access qgroup reservation
  41  *
  42  * Callers should ensure the lock context and type are valid
  43  */
  44
  45 static u64 qgroup_rsv_total(const struct btrfs_qgroup *qgroup)
  46 {
  47         u64 ret = 0;
  48         int i;
  49
  50         for (i = 0; i < BTRFS_QGROUP_RSV_LAST; i++)
  51                 ret += qgroup->rsv.values[i];
  52
  53         return ret;
  54 }
  55
  56 #ifdef CONFIG_BTRFS_DEBUG
  57 static const char *qgroup_rsv_type_str(enum btrfs_qgroup_rsv_type type)
  58 {
  59         if (type == BTRFS_QGROUP_RSV_DATA)
  60                 return "data";
  61         if (type == BTRFS_QGROUP_RSV_META_PERTRANS)
  62                 return "meta_pertrans";
  63         if (type == BTRFS_QGROUP_RSV_META_PREALLOC)
  64                 return "meta_prealloc";
  65         return NULL;
  66 }
  67 #endif
  68
  69 static void qgroup_rsv_add(struct btrfs_fs_info *fs_info,
  70                            struct btrfs_qgroup *qgroup, u64 num_bytes,
  71                            enum btrfs_qgroup_rsv_type type)
  72 {
  73         trace_qgroup_update_reserve(fs_info, qgroup, num_bytes, type);
  74         qgroup->rsv.values[type] += num_bytes;
  75 }
  76
  77 static void qgroup_rsv_release(struct btrfs_fs_info *fs_info,
  78                                struct btrfs_qgroup *qgroup, u64 num_bytes,
  79                                enum btrfs_qgroup_rsv_type type)
  80 {
  81         trace_qgroup_update_reserve(fs_info, qgroup, -(s64)num_bytes, type);
  82         if (qgroup->rsv.values[type] >= num_bytes) {
  83                 qgroup->rsv.values[type] -= num_bytes;
  84                 return;
  85         }
  86 #ifdef CONFIG_BTRFS_DEBUG
  87         WARN_RATELIMIT(1,
  88                 "qgroup %llu %s reserved space underflow, have %llu to free %llu",
  89                 qgroup->qgroupid, qgroup_rsv_type_str(type),
  90                 qgroup->rsv.values[type], num_bytes);
  91 #endif
  92         qgroup->rsv.values[type] = 0;
  93 }
  94
  95 static void qgroup_rsv_add_by_qgroup(struct btrfs_fs_info *fs_info,
  96                                      struct btrfs_qgroup *dest,
  97                                      struct btrfs_qgroup *src)
  98 {
  99         int i;
 100
 101         for (i = 0; i < BTRFS_QGROUP_RSV_LAST; i++)
 102                 qgroup_rsv_add(fs_info, dest, src->rsv.values[i], i);
 103 }
 104
 105 static void qgroup_rsv_release_by_qgroup(struct btrfs_fs_info *fs_info,
 106                                          struct btrfs_qgroup *dest,
 107                                           struct btrfs_qgroup *src)
 108 {
 109         int i;
 110
 111         for (i = 0; i < BTRFS_QGROUP_RSV_LAST; i++)
 112                 qgroup_rsv_release(fs_info, dest, src->rsv.values[i], i);
 113 }
 114
 115 static void btrfs_qgroup_update_old_refcnt(struct btrfs_qgroup *qg, u64 seq,
 116                                            int mod)
 117 {
 118         if (qg->old_refcnt < seq)
 119                 qg->old_refcnt = seq;
 120         qg->old_refcnt += mod;
 121 }
 122
 123 static void btrfs_qgroup_update_new_refcnt(struct btrfs_qgroup *qg, u64 seq,
 124                                            int mod)
 125 {
 126         if (qg->new_refcnt < seq)
 127                 qg->new_refcnt = seq;
 128         qg->new_refcnt += mod;
 129 }
 130
 131 static inline u64 btrfs_qgroup_get_old_refcnt(struct btrfs_qgroup *qg, u64 seq)
 132 {
 133         if (qg->old_refcnt < seq)
 134                 return 0;
 135         return qg->old_refcnt - seq;
 136 }
 137
 138 static inline u64 btrfs_qgroup_get_new_refcnt(struct btrfs_qgroup *qg, u64 seq)
 139 {
 140         if (qg->new_refcnt < seq)
 141                 return 0;
 142         return qg->new_refcnt - seq;
 143 }
 144
 145 /*
 146  * glue structure to represent the relations between qgroups.
 147  */
 148 struct btrfs_qgroup_list {
 149         struct list_head next_group;
 150         struct list_head next_member;
 151         struct btrfs_qgroup *group;
 152         struct btrfs_qgroup *member;
 153 };
 154
 155 static inline u64 qgroup_to_aux(struct btrfs_qgroup *qg)
 156 {
 157         return (u64)(uintptr_t)qg;
 158 }
 159
 160 static inline struct btrfs_qgroup* unode_aux_to_qgroup(struct ulist_node *n)
 161 {
 162         return (struct btrfs_qgroup *)(uintptr_t)n->aux;
 163 }
 164
 165 static int
 166 qgroup_rescan_init(struct btrfs_fs_info *fs_info, u64 progress_objectid,
 167                    int init_flags);
 168 static void qgroup_rescan_zero_tracking(struct btrfs_fs_info *fs_info);
 169
 170 /* must be called with qgroup_ioctl_lock held */
 171 static struct btrfs_qgroup *find_qgroup_rb(struct btrfs_fs_info *fs_info,
 172                                            u64 qgroupid)
 173 {
 174         struct rb_node *n = fs_info->qgroup_tree.rb_node;
 175         struct btrfs_qgroup *qgroup;
 176
 177         while (n) {
 178                 qgroup = rb_entry(n, struct btrfs_qgroup, node);
 179                 if (qgroup->qgroupid < qgroupid)
 180                         n = n->rb_left;
 181                 else if (qgroup->qgroupid > qgroupid)
 182                         n = n->rb_right;
 183                 else
 184                         return qgroup;
 185         }
 186         return NULL;
 187 }
 188
 189 /* must be called with qgroup_lock held */
 190 static struct btrfs_qgroup *add_qgroup_rb(struct btrfs_fs_info *fs_info,
 191                                           u64 qgroupid)
 192 {
 193         struct rb_node **p = &fs_info->qgroup_tree.rb_node;
 194         struct rb_node *parent = NULL;
 195         struct btrfs_qgroup *qgroup;
 196
 197         while (*p) {
 198                 parent = *p;
 199                 qgroup = rb_entry(parent, struct btrfs_qgroup, node);
 200
 201                 if (qgroup->qgroupid < qgroupid)
 202                         p = &(*p)->rb_left;
 203                 else if (qgroup->qgroupid > qgroupid)
 204                         p = &(*p)->rb_right;
 205                 else
 206                         return qgroup;
 207         }
 208
 209         qgroup = kzalloc(sizeof(*qgroup), GFP_ATOMIC);
 210         if (!qgroup)
 211                 return ERR_PTR(-ENOMEM);
 212
 213         qgroup->qgroupid = qgroupid;
 214         INIT_LIST_HEAD(&qgroup->groups);
 215         INIT_LIST_HEAD(&qgroup->members);
 216         INIT_LIST_HEAD(&qgroup->dirty);
 217
 218         rb_link_node(&qgroup->node, parent, p);
 219         rb_insert_color(&qgroup->node, &fs_info->qgroup_tree);
 220
 221         return qgroup;
 222 }
 223
 224 static void __del_qgroup_rb(struct btrfs_fs_info *fs_info,
 225                             struct btrfs_qgroup *qgroup)
 226 {
 227         struct btrfs_qgroup_list *list;
 228
 229         btrfs_sysfs_del_one_qgroup(fs_info, qgroup);
 230         list_del(&qgroup->dirty);
 231         while (!list_empty(&qgroup->groups)) {
 232                 list = list_first_entry(&qgroup->groups,
 233                                         struct btrfs_qgroup_list, next_group);
 234                 list_del(&list->next_group);
 235                 list_del(&list->next_member);
 236                 kfree(list);
 237         }
 238
 239         while (!list_empty(&qgroup->members)) {
 240                 list = list_first_entry(&qgroup->members,
 241                                         struct btrfs_qgroup_list, next_member);
 242                 list_del(&list->next_group);
 243                 list_del(&list->next_member);
 244                 kfree(list);
 245         }
 246         kfree(qgroup);
 247 }
 248
 249 /* must be called with qgroup_lock held */
 250 static int del_qgroup_rb(struct btrfs_fs_info *fs_info, u64 qgroupid)
 251 {
 252         struct btrfs_qgroup *qgroup = find_qgroup_rb(fs_info, qgroupid);
 253
 254         if (!qgroup)
 255                 return -ENOENT;
 256
 257         rb_erase(&qgroup->node, &fs_info->qgroup_tree);
 258         __del_qgroup_rb(fs_info, qgroup);
 259         return 0;
 260 }
 261
 262 /* must be called with qgroup_lock held */
 263 static int add_relation_rb(struct btrfs_fs_info *fs_info,
 264                            u64 memberid, u64 parentid)
 265 {
 266         struct btrfs_qgroup *member;
 267         struct btrfs_qgroup *parent;
 268         struct btrfs_qgroup_list *list;
 269
 270         member = find_qgroup_rb(fs_info, memberid);
 271         parent = find_qgroup_rb(fs_info, parentid);
 272         if (!member || !parent)
 273                 return -ENOENT;
 274
 275         list = kzalloc(sizeof(*list), GFP_ATOMIC);
 276         if (!list)
 277                 return -ENOMEM;
 278
 279         list->group = parent;
 280         list->member = member;
 281         list_add_tail(&list->next_group, &member->groups);
 282         list_add_tail(&list->next_member, &parent->members);
 283
 284         return 0;
 285 }
 286
 287 /* must be called with qgroup_lock held */
 288 static int del_relation_rb(struct btrfs_fs_info *fs_info,
 289                            u64 memberid, u64 parentid)
 290 {
 291         struct btrfs_qgroup *member;
 292         struct btrfs_qgroup *parent;
 293         struct btrfs_qgroup_list *list;
 294
 295         member = find_qgroup_rb(fs_info, memberid);
 296         parent = find_qgroup_rb(fs_info, parentid);
 297         if (!member || !parent)
 298                 return -ENOENT;
 299
 300         list_for_each_entry(list, &member->groups, next_group) {
 301                 if (list->group == parent) {
 302                         list_del(&list->next_group);
 303                         list_del(&list->next_member);
 304                         kfree(list);
 305                         return 0;
 306                 }
 307         }
 308         return -ENOENT;
 309 }
 310
 311 #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
 312 int btrfs_verify_qgroup_counts(struct btrfs_fs_info *fs_info, u64 qgroupid,
 313                                u64 rfer, u64 excl)
 314 {
 315         struct btrfs_qgroup *qgroup;
 316
 317         qgroup = find_qgroup_rb(fs_info, qgroupid);
 318         if (!qgroup)
 319                 return -EINVAL;
 320         if (qgroup->rfer != rfer || qgroup->excl != excl)
 321                 return -EINVAL;
 322         return 0;
 323 }
 324 #endif
 325
 326 /*
 327  * The full config is read in one go, only called from open_ctree()
 328  * It doesn't use any locking, as at this point we're still single-threaded
 329  */
 330 int btrfs_read_qgroup_config(struct btrfs_fs_info *fs_info)
 331 {
 332         struct btrfs_key key;
 333         struct btrfs_key found_key;
 334         struct btrfs_root *quota_root = fs_info->quota_root;
 335         struct btrfs_path *path = NULL;
 336         struct extent_buffer *l;
 337         int slot;
 338         int ret = 0;
 339         u64 flags = 0;
 340         u64 rescan_progress = 0;
 341
 342         if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags))
 343                 return 0;
 344
 345         fs_info->qgroup_ulist = ulist_alloc(GFP_KERNEL);
 346         if (!fs_info->qgroup_ulist) {
 347                 ret = -ENOMEM;
 348                 goto out;
 349         }
 350
 351         path = btrfs_alloc_path();
 352         if (!path) {
 353                 ret = -ENOMEM;
 354                 goto out;
 355         }
 356
 357         ret = btrfs_sysfs_add_qgroups(fs_info);
 358         if (ret < 0)
 359                 goto out;
 360         /* default this to quota off, in case no status key is found */
 361         fs_info->qgroup_flags = 0;
 362
 363         /*
 364          * pass 1: read status, all qgroup infos and limits
 365          */
 366         key.objectid = 0;
 367         key.type = 0;
 368         key.offset = 0;
 369         ret = btrfs_search_slot_for_read(quota_root, &key, path, 1, 1);
 370         if (ret)
 371                 goto out;
 372
 373         while (1) {
 374                 struct btrfs_qgroup *qgroup;
 375
 376                 slot = path->slots[0];
 377                 l = path->nodes[0];
 378                 btrfs_item_key_to_cpu(l, &found_key, slot);
 379
 380                 if (found_key.type == BTRFS_QGROUP_STATUS_KEY) {
 381                         struct btrfs_qgroup_status_item *ptr;
 382
 383                         ptr = btrfs_item_ptr(l, slot,
 384                                              struct btrfs_qgroup_status_item);
 385
 386                         if (btrfs_qgroup_status_version(l, ptr) !=
 387                             BTRFS_QGROUP_STATUS_VERSION) {
 388                                 btrfs_err(fs_info,
 389                                  "old qgroup version, quota disabled");
 390                                 goto out;
 391                         }
 392                         if (btrfs_qgroup_status_generation(l, ptr) !=
 393                             fs_info->generation) {
 394                                 flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
 395                                 btrfs_err(fs_info,
 396                                         "qgroup generation mismatch, marked as inconsistent");
 397                         }
 398                         fs_info->qgroup_flags = btrfs_qgroup_status_flags(l,
 399                                                                           ptr);
 400                         rescan_progress = btrfs_qgroup_status_rescan(l, ptr);
 401                         goto next1;
 402                 }
 403
 404                 if (found_key.type != BTRFS_QGROUP_INFO_KEY &&
 405                     found_key.type != BTRFS_QGROUP_LIMIT_KEY)
 406                         goto next1;
 407
 408                 qgroup = find_qgroup_rb(fs_info, found_key.offset);
 409                 if ((qgroup && found_key.type == BTRFS_QGROUP_INFO_KEY) ||
 410                     (!qgroup && found_key.type == BTRFS_QGROUP_LIMIT_KEY)) {
 411                         btrfs_err(fs_info, "inconsistent qgroup config");
 412                         flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
 413                 }
 414                 if (!qgroup) {
 415                         qgroup = add_qgroup_rb(fs_info, found_key.offset);
 416                         if (IS_ERR(qgroup)) {
 417                                 ret = PTR_ERR(qgroup);
 418                                 goto out;
 419                         }
 420                 }
 421                 ret = btrfs_sysfs_add_one_qgroup(fs_info, qgroup);
 422                 if (ret < 0)
 423                         goto out;
 424
 425                 switch (found_key.type) {
 426                 case BTRFS_QGROUP_INFO_KEY: {
 427                         struct btrfs_qgroup_info_item *ptr;
 428
 429                         ptr = btrfs_item_ptr(l, slot,
 430                                              struct btrfs_qgroup_info_item);
 431                         qgroup->rfer = btrfs_qgroup_info_rfer(l, ptr);
 432                         qgroup->rfer_cmpr = btrfs_qgroup_info_rfer_cmpr(l, ptr);
 433                         qgroup->excl = btrfs_qgroup_info_excl(l, ptr);
 434                         qgroup->excl_cmpr = btrfs_qgroup_info_excl_cmpr(l, ptr);
 435                         /* generation currently unused */
 436                         break;
 437                 }
 438                 case BTRFS_QGROUP_LIMIT_KEY: {
 439                         struct btrfs_qgroup_limit_item *ptr;
 440
 441                         ptr = btrfs_item_ptr(l, slot,
 442                                              struct btrfs_qgroup_limit_item);
 443                         qgroup->lim_flags = btrfs_qgroup_limit_flags(l, ptr);
 444                         qgroup->max_rfer = btrfs_qgroup_limit_max_rfer(l, ptr);
 445                         qgroup->max_excl = btrfs_qgroup_limit_max_excl(l, ptr);
 446                         qgroup->rsv_rfer = btrfs_qgroup_limit_rsv_rfer(l, ptr);
 447                         qgroup->rsv_excl = btrfs_qgroup_limit_rsv_excl(l, ptr);
 448                         break;
 449                 }
 450                 }
 451 next1:
 452                 ret = btrfs_next_item(quota_root, path);
 453                 if (ret < 0)
 454                         goto out;
 455                 if (ret)
 456                         break;
 457         }
 458         btrfs_release_path(path);
 459
 460         /*
 461          * pass 2: read all qgroup relations
 462          */
 463         key.objectid = 0;
 464         key.type = BTRFS_QGROUP_RELATION_KEY;
 465         key.offset = 0;
 466         ret = btrfs_search_slot_for_read(quota_root, &key, path, 1, 0);
 467         if (ret)
 468                 goto out;
 469         while (1) {
 470                 slot = path->slots[0];
 471                 l = path->nodes[0];
 472                 btrfs_item_key_to_cpu(l, &found_key, slot);
 473
 474                 if (found_key.type != BTRFS_QGROUP_RELATION_KEY)
 475                         goto next2;
 476
 477                 if (found_key.objectid > found_key.offset) {
 478                         /* parent <- member, not needed to build config */
 479                         /* FIXME should we omit the key completely? */
 480                         goto next2;
 481                 }
 482
 483                 ret = add_relation_rb(fs_info, found_key.objectid,
 484                                       found_key.offset);
 485                 if (ret == -ENOENT) {
 486                         btrfs_warn(fs_info,
 487                                 "orphan qgroup relation 0x%llx->0x%llx",
 488                                 found_key.objectid, found_key.offset);
 489                         ret = 0;        /* ignore the error */
 490                 }
 491                 if (ret)
 492                         goto out;
 493 next2:
 494                 ret = btrfs_next_item(quota_root, path);
 495                 if (ret < 0)
 496                         goto out;
 497                 if (ret)
 498                         break;
 499         }
 500 out:
 501         btrfs_free_path(path);
 502         fs_info->qgroup_flags |= flags;
 503         if (!(fs_info->qgroup_flags & BTRFS_QGROUP_STATUS_FLAG_ON))
 504                 clear_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags);
 505         else if (fs_info->qgroup_flags & BTRFS_QGROUP_STATUS_FLAG_RESCAN &&
 506                  ret >= 0)
 507                 ret = qgroup_rescan_init(fs_info, rescan_progress, 0);
 508
 509         if (ret < 0) {
 510                 ulist_free(fs_info->qgroup_ulist);
 511                 fs_info->qgroup_ulist = NULL;
 512                 fs_info->qgroup_flags &= ~BTRFS_QGROUP_STATUS_FLAG_RESCAN;
 513                 btrfs_sysfs_del_qgroups(fs_info);
 514         }
 515
 516         return ret < 0 ? ret : 0;
 517 }
 518
 519 /*
 520  * Called in close_ctree() when quota is still enabled.  This verifies we don't
 521  * leak some reserved space.
 522  *
 523  * Return false if no reserved space is left.
 524  * Return true if some reserved space is leaked.
 525  */
 526 bool btrfs_check_quota_leak(struct btrfs_fs_info *fs_info)
 527 {
 528         struct rb_node *node;
 529         bool ret = false;
 530
 531         if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags))
 532                 return ret;
 533         /*
 534          * Since we're unmounting, there is no race and no need to grab qgroup
 535          * lock.  And here we don't go post-order to provide a more user
 536          * friendly sorted result.
 537          */
 538         for (node = rb_first(&fs_info->qgroup_tree); node; node = rb_next(node)) {
 539                 struct btrfs_qgroup *qgroup;
 540                 int i;
 541
 542                 qgroup = rb_entry(node, struct btrfs_qgroup, node);
 543                 for (i = 0; i < BTRFS_QGROUP_RSV_LAST; i++) {
 544                         if (qgroup->rsv.values[i]) {
 545                                 ret = true;
 546                                 btrfs_warn(fs_info,
 547                 "qgroup %hu/%llu has unreleased space, type %d rsv %llu",
 548                                    btrfs_qgroup_level(qgroup->qgroupid),
 549                                    btrfs_qgroup_subvolid(qgroup->qgroupid),
 550                                    i, qgroup->rsv.values[i]);
 551                         }
 552                 }
 553         }
 554         return ret;
 555 }
 556
 557 /*
 558  * This is called from close_ctree() or open_ctree() or btrfs_quota_disable(),
 559  * first two are in single-threaded paths.And for the third one, we have set
 560  * quota_root to be null with qgroup_lock held before, so it is safe to clean
 561  * up the in-memory structures without qgroup_lock held.
 562  */
 563 void btrfs_free_qgroup_config(struct btrfs_fs_info *fs_info)
 564 {
 565         struct rb_node *n;
 566         struct btrfs_qgroup *qgroup;
 567
 568         while ((n = rb_first(&fs_info->qgroup_tree))) {
 569                 qgroup = rb_entry(n, struct btrfs_qgroup, node);
 570                 rb_erase(n, &fs_info->qgroup_tree);
 571                 __del_qgroup_rb(fs_info, qgroup);
 572         }
 573         /*
 574          * We call btrfs_free_qgroup_config() when unmounting
 575          * filesystem and disabling quota, so we set qgroup_ulist
 576          * to be null here to avoid double free.
 577          */
 578         ulist_free(fs_info->qgroup_ulist);
 579         fs_info->qgroup_ulist = NULL;
 580         btrfs_sysfs_del_qgroups(fs_info);
 581 }
 582
 583 static int add_qgroup_relation_item(struct btrfs_trans_handle *trans, u64 src,
 584                                     u64 dst)
 585 {
 586         int ret;
 587         struct btrfs_root *quota_root = trans->fs_info->quota_root;
 588         struct btrfs_path *path;
 589         struct btrfs_key key;
 590
 591         path = btrfs_alloc_path();
 592         if (!path)
 593                 return -ENOMEM;
 594
 595         key.objectid = src;
 596         key.type = BTRFS_QGROUP_RELATION_KEY;
 597         key.offset = dst;
 598
 599         ret = btrfs_insert_empty_item(trans, quota_root, path, &key, 0);
 600
 601         btrfs_mark_buffer_dirty(path->nodes[0]);
 602
 603         btrfs_free_path(path);
 604         return ret;
 605 }
 606
 607 static int del_qgroup_relation_item(struct btrfs_trans_handle *trans, u64 src,
 608                                     u64 dst)
 609 {
 610         int ret;
 611         struct btrfs_root *quota_root = trans->fs_info->quota_root;
 612         struct btrfs_path *path;
 613         struct btrfs_key key;
 614
 615         path = btrfs_alloc_path();
 616         if (!path)
 617                 return -ENOMEM;
 618
 619         key.objectid = src;
 620         key.type = BTRFS_QGROUP_RELATION_KEY;
 621         key.offset = dst;
 622
 623         ret = btrfs_search_slot(trans, quota_root, &key, path, -1, 1);
 624         if (ret < 0)
 625                 goto out;
 626
 627         if (ret > 0) {
 628                 ret = -ENOENT;
 629                 goto out;
 630         }
 631
 632         ret = btrfs_del_item(trans, quota_root, path);
 633 out:
 634         btrfs_free_path(path);
 635         return ret;
 636 }
 637
 638 static int add_qgroup_item(struct btrfs_trans_handle *trans,
 639                            struct btrfs_root *quota_root, u64 qgroupid)
 640 {
 641         int ret;
 642         struct btrfs_path *path;
 643         struct btrfs_qgroup_info_item *qgroup_info;
 644         struct btrfs_qgroup_limit_item *qgroup_limit;
 645         struct extent_buffer *leaf;
 646         struct btrfs_key key;
 647
 648         if (btrfs_is_testing(quota_root->fs_info))
 649                 return 0;
 650
 651         path = btrfs_alloc_path();
 652         if (!path)
 653                 return -ENOMEM;
 654
 655         key.objectid = 0;
 656         key.type = BTRFS_QGROUP_INFO_KEY;
 657         key.offset = qgroupid;
 658
 659         /*
 660          * Avoid a transaction abort by catching -EEXIST here. In that
 661          * case, we proceed by re-initializing the existing structure
 662          * on disk.
 663          */
 664
 665         ret = btrfs_insert_empty_item(trans, quota_root, path, &key,
 666                                       sizeof(*qgroup_info));
 667         if (ret && ret != -EEXIST)
 668                 goto out;
 669
 670         leaf = path->nodes[0];
 671         qgroup_info = btrfs_item_ptr(leaf, path->slots[0],
 672                                  struct btrfs_qgroup_info_item);
 673         btrfs_set_qgroup_info_generation(leaf, qgroup_info, trans->transid);
 674         btrfs_set_qgroup_info_rfer(leaf, qgroup_info, 0);
 675         btrfs_set_qgroup_info_rfer_cmpr(leaf, qgroup_info, 0);
 676         btrfs_set_qgroup_info_excl(leaf, qgroup_info, 0);
 677         btrfs_set_qgroup_info_excl_cmpr(leaf, qgroup_info, 0);
 678
 679         btrfs_mark_buffer_dirty(leaf);
 680
 681         btrfs_release_path(path);
 682
 683         key.type = BTRFS_QGROUP_LIMIT_KEY;
 684         ret = btrfs_insert_empty_item(trans, quota_root, path, &key,
 685                                       sizeof(*qgroup_limit));
 686         if (ret && ret != -EEXIST)
 687                 goto out;
 688
 689         leaf = path->nodes[0];
 690         qgroup_limit = btrfs_item_ptr(leaf, path->slots[0],
 691                                   struct btrfs_qgroup_limit_item);
 692         btrfs_set_qgroup_limit_flags(leaf, qgroup_limit, 0);
 693         btrfs_set_qgroup_limit_max_rfer(leaf, qgroup_limit, 0);
 694         btrfs_set_qgroup_limit_max_excl(leaf, qgroup_limit, 0);
 695         btrfs_set_qgroup_limit_rsv_rfer(leaf, qgroup_limit, 0);
 696         btrfs_set_qgroup_limit_rsv_excl(leaf, qgroup_limit, 0);
 697
 698         btrfs_mark_buffer_dirty(leaf);
 699
 700         ret = 0;
 701 out:
 702         btrfs_free_path(path);
 703         return ret;
 704 }
 705
 706 static int del_qgroup_item(struct btrfs_trans_handle *trans, u64 qgroupid)
 707 {
 708         int ret;
 709         struct btrfs_root *quota_root = trans->fs_info->quota_root;
 710         struct btrfs_path *path;
 711         struct btrfs_key key;
 712
 713         path = btrfs_alloc_path();
 714         if (!path)
 715                 return -ENOMEM;
 716
 717         key.objectid = 0;
 718         key.type = BTRFS_QGROUP_INFO_KEY;
 719         key.offset = qgroupid;
 720         ret = btrfs_search_slot(trans, quota_root, &key, path, -1, 1);
 721         if (ret < 0)
 722                 goto out;
 723
 724         if (ret > 0) {
 725                 ret = -ENOENT;
 726                 goto out;
 727         }
 728
 729         ret = btrfs_del_item(trans, quota_root, path);
 730         if (ret)
 731                 goto out;
 732
 733         btrfs_release_path(path);
 734
 735         key.type = BTRFS_QGROUP_LIMIT_KEY;
 736         ret = btrfs_search_slot(trans, quota_root, &key, path, -1, 1);
 737         if (ret < 0)
 738                 goto out;
 739
 740         if (ret > 0) {
 741                 ret = -ENOENT;
 742                 goto out;
 743         }
 744
 745         ret = btrfs_del_item(trans, quota_root, path);
 746
 747 out:
 748         btrfs_free_path(path);
 749         return ret;
 750 }
 751
 752 static int update_qgroup_limit_item(struct btrfs_trans_handle *trans,
 753                                     struct btrfs_qgroup *qgroup)
 754 {
 755         struct btrfs_root *quota_root = trans->fs_info->quota_root;
 756         struct btrfs_path *path;
 757         struct btrfs_key key;
 758         struct extent_buffer *l;
 759         struct btrfs_qgroup_limit_item *qgroup_limit;
 760         int ret;
 761         int slot;
 762
 763         key.objectid = 0;
 764         key.type = BTRFS_QGROUP_LIMIT_KEY;
 765         key.offset = qgroup->qgroupid;
 766
 767         path = btrfs_alloc_path();
 768         if (!path)
 769                 return -ENOMEM;
 770
 771         ret = btrfs_search_slot(trans, quota_root, &key, path, 0, 1);
 772         if (ret > 0)
 773                 ret = -ENOENT;
 774
 775         if (ret)
 776                 goto out;
 777
 778         l = path->nodes[0];
 779         slot = path->slots[0];
 780         qgroup_limit = btrfs_item_ptr(l, slot, struct btrfs_qgroup_limit_item);
 781         btrfs_set_qgroup_limit_flags(l, qgroup_limit, qgroup->lim_flags);
 782         btrfs_set_qgroup_limit_max_rfer(l, qgroup_limit, qgroup->max_rfer);
 783         btrfs_set_qgroup_limit_max_excl(l, qgroup_limit, qgroup->max_excl);
 784         btrfs_set_qgroup_limit_rsv_rfer(l, qgroup_limit, qgroup->rsv_rfer);
 785         btrfs_set_qgroup_limit_rsv_excl(l, qgroup_limit, qgroup->rsv_excl);
 786
 787         btrfs_mark_buffer_dirty(l);
 788
 789 out:
 790         btrfs_free_path(path);
 791         return ret;
 792 }
 793
 794 static int update_qgroup_info_item(struct btrfs_trans_handle *trans,
 795                                    struct btrfs_qgroup *qgroup)
 796 {
 797         struct btrfs_fs_info *fs_info = trans->fs_info;
 798         struct btrfs_root *quota_root = fs_info->quota_root;
 799         struct btrfs_path *path;
 800         struct btrfs_key key;
 801         struct extent_buffer *l;
 802         struct btrfs_qgroup_info_item *qgroup_info;
 803         int ret;
 804         int slot;
 805
 806         if (btrfs_is_testing(fs_info))
 807                 return 0;
 808
 809         key.objectid = 0;
 810         key.type = BTRFS_QGROUP_INFO_KEY;
 811         key.offset = qgroup->qgroupid;
 812
 813         path = btrfs_alloc_path();
 814         if (!path)
 815                 return -ENOMEM;
 816
 817         ret = btrfs_search_slot(trans, quota_root, &key, path, 0, 1);
 818         if (ret > 0)
 819                 ret = -ENOENT;
 820
 821         if (ret)
 822                 goto out;
 823
 824         l = path->nodes[0];
 825         slot = path->slots[0];
 826         qgroup_info = btrfs_item_ptr(l, slot, struct btrfs_qgroup_info_item);
 827         btrfs_set_qgroup_info_generation(l, qgroup_info, trans->transid);
 828         btrfs_set_qgroup_info_rfer(l, qgroup_info, qgroup->rfer);
 829         btrfs_set_qgroup_info_rfer_cmpr(l, qgroup_info, qgroup->rfer_cmpr);
 830         btrfs_set_qgroup_info_excl(l, qgroup_info, qgroup->excl);
 831         btrfs_set_qgroup_info_excl_cmpr(l, qgroup_info, qgroup->excl_cmpr);
 832
 833         btrfs_mark_buffer_dirty(l);
 834
 835 out:
 836         btrfs_free_path(path);
 837         return ret;
 838 }
 839
 840 static int update_qgroup_status_item(struct btrfs_trans_handle *trans)
 841 {
 842         struct btrfs_fs_info *fs_info = trans->fs_info;
 843         struct btrfs_root *quota_root = fs_info->quota_root;
 844         struct btrfs_path *path;
 845         struct btrfs_key key;
 846         struct extent_buffer *l;
 847         struct btrfs_qgroup_status_item *ptr;
 848         int ret;
 849         int slot;
 850
 851         key.objectid = 0;
 852         key.type = BTRFS_QGROUP_STATUS_KEY;
 853         key.offset = 0;
 854
 855         path = btrfs_alloc_path();
 856         if (!path)
 857                 return -ENOMEM;
 858
 859         ret = btrfs_search_slot(trans, quota_root, &key, path, 0, 1);
 860         if (ret > 0)
 861                 ret = -ENOENT;
 862
 863         if (ret)
 864                 goto out;
 865
 866         l = path->nodes[0];
 867         slot = path->slots[0];
 868         ptr = btrfs_item_ptr(l, slot, struct btrfs_qgroup_status_item);
 869         btrfs_set_qgroup_status_flags(l, ptr, fs_info->qgroup_flags);
 870         btrfs_set_qgroup_status_generation(l, ptr, trans->transid);
 871         btrfs_set_qgroup_status_rescan(l, ptr,
 872                                 fs_info->qgroup_rescan_progress.objectid);
 873
 874         btrfs_mark_buffer_dirty(l);
 875
 876 out:
 877         btrfs_free_path(path);
 878         return ret;
 879 }
 880
 881 /*
 882  * called with qgroup_lock held
 883  */
 884 static int btrfs_clean_quota_tree(struct btrfs_trans_handle *trans,
 885                                   struct btrfs_root *root)
 886 {
 887         struct btrfs_path *path;
 888         struct btrfs_key key;
 889         struct extent_buffer *leaf = NULL;
 890         int ret;
 891         int nr = 0;
 892
 893         path = btrfs_alloc_path();
 894         if (!path)
 895                 return -ENOMEM;
 896
 897         path->leave_spinning = 1;
 898
 899         key.objectid = 0;
 900         key.offset = 0;
 901         key.type = 0;
 902
 903         while (1) {
 904                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 905                 if (ret < 0)
 906                         goto out;
 907                 leaf = path->nodes[0];
 908                 nr = btrfs_header_nritems(leaf);
 909                 if (!nr)
 910                         break;
 911                 /*
 912                  * delete the leaf one by one
 913                  * since the whole tree is going
 914                  * to be deleted.
 915                  */
 916                 path->slots[0] = 0;
 917                 ret = btrfs_del_items(trans, root, path, 0, nr);
 918                 if (ret)
 919                         goto out;
 920
 921                 btrfs_release_path(path);
 922         }
 923         ret = 0;
 924 out:
 925         btrfs_free_path(path);
 926         return ret;
 927 }
 928
 929 int btrfs_quota_enable(struct btrfs_fs_info *fs_info)
 930 {
 931         struct btrfs_root *quota_root;
 932         struct btrfs_root *tree_root = fs_info->tree_root;
 933         struct btrfs_path *path = NULL;
 934         struct btrfs_qgroup_status_item *ptr;
 935         struct extent_buffer *leaf;
 936         struct btrfs_key key;
 937         struct btrfs_key found_key;
 938         struct btrfs_qgroup *qgroup = NULL;
 939         struct btrfs_trans_handle *trans = NULL;
 940         int ret = 0;
 941         int slot;
 942
 943         mutex_lock(&fs_info->qgroup_ioctl_lock);
 944         if (fs_info->quota_root)
 945                 goto out;
 946
 947         fs_info->qgroup_ulist = ulist_alloc(GFP_KERNEL);
 948         if (!fs_info->qgroup_ulist) {
 949                 ret = -ENOMEM;
 950                 goto out;
 951         }
 952
 953         ret = btrfs_sysfs_add_qgroups(fs_info);
 954         if (ret < 0)
 955                 goto out;
 956         /*
 957          * 1 for quota root item
 958          * 1 for BTRFS_QGROUP_STATUS item
 959          *
 960          * Yet we also need 2*n items for a QGROUP_INFO/QGROUP_LIMIT items
 961          * per subvolume. However those are not currently reserved since it
 962          * would be a lot of overkill.
 963          */
 964         trans = btrfs_start_transaction(tree_root, 2);
 965         if (IS_ERR(trans)) {
 966                 ret = PTR_ERR(trans);
 967                 trans = NULL;
 968                 goto out;
 969         }
 970
 971         /*
 972          * initially create the quota tree
 973          */
 974         quota_root = btrfs_create_tree(trans, BTRFS_QUOTA_TREE_OBJECTID);
 975         if (IS_ERR(quota_root)) {
 976                 ret =  PTR_ERR(quota_root);
 977                 btrfs_abort_transaction(trans, ret);
 978                 goto out;
 979         }
 980
 981         path = btrfs_alloc_path();
 982         if (!path) {
 983                 ret = -ENOMEM;
 984                 btrfs_abort_transaction(trans, ret);
 985                 goto out_free_root;
 986         }
 987
 988         key.objectid = 0;
 989         key.type = BTRFS_QGROUP_STATUS_KEY;
 990         key.offset = 0;
 991
 992         ret = btrfs_insert_empty_item(trans, quota_root, path, &key,
 993                                       sizeof(*ptr));
 994         if (ret) {
 995                 btrfs_abort_transaction(trans, ret);
 996                 goto out_free_path;
 997         }
 998
 999         leaf = path->nodes[0];
1000         ptr = btrfs_item_ptr(leaf, path->slots[0],
1001                                  struct btrfs_qgroup_status_item);
1002         btrfs_set_qgroup_status_generation(leaf, ptr, trans->transid);
1003         btrfs_set_qgroup_status_version(leaf, ptr, BTRFS_QGROUP_STATUS_VERSION);
1004         fs_info->qgroup_flags = BTRFS_QGROUP_STATUS_FLAG_ON |
1005                                 BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
1006         btrfs_set_qgroup_status_flags(leaf, ptr, fs_info->qgroup_flags);
1007         btrfs_set_qgroup_status_rescan(leaf, ptr, 0);
1008
1009         btrfs_mark_buffer_dirty(leaf);
1010
1011         key.objectid = 0;
1012         key.type = BTRFS_ROOT_REF_KEY;
1013         key.offset = 0;
1014
1015         btrfs_release_path(path);
1016         ret = btrfs_search_slot_for_read(tree_root, &key, path, 1, 0);
1017         if (ret > 0)
1018                 goto out_add_root;
1019         if (ret < 0) {
1020                 btrfs_abort_transaction(trans, ret);
1021                 goto out_free_path;
1022         }
1023
1024         while (1) {
1025                 slot = path->slots[0];
1026                 leaf = path->nodes[0];
1027                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
1028
1029                 if (found_key.type == BTRFS_ROOT_REF_KEY) {
1030
1031                         /* Release locks on tree_root before we access quota_root */
1032                         btrfs_release_path(path);
1033
1034                         ret = add_qgroup_item(trans, quota_root,
1035                                               found_key.offset);
1036                         if (ret) {
1037                                 btrfs_abort_transaction(trans, ret);
1038                                 goto out_free_path;
1039                         }
1040
1041                         qgroup = add_qgroup_rb(fs_info, found_key.offset);
1042                         if (IS_ERR(qgroup)) {
1043                                 ret = PTR_ERR(qgroup);
1044                                 btrfs_abort_transaction(trans, ret);
1045                                 goto out_free_path;
1046                         }
1047                         ret = btrfs_sysfs_add_one_qgroup(fs_info, qgroup);
1048                         if (ret < 0) {
1049                                 btrfs_abort_transaction(trans, ret);
1050                                 goto out_free_path;
1051                         }
1052                         ret = btrfs_search_slot_for_read(tree_root, &found_key,
1053                                                          path, 1, 0);
1054                         if (ret < 0) {
1055                                 btrfs_abort_transaction(trans, ret);
1056                                 goto out_free_path;
1057                         }
1058                         if (ret > 0) {
1059                                 /*
1060                                  * Shouldn't happen, but in case it does we
1061                                  * don't need to do the btrfs_next_item, just
1062                                  * continue.
1063                                  */
1064                                 continue;
1065                         }
1066                 }
1067                 ret = btrfs_next_item(tree_root, path);
1068                 if (ret < 0) {
1069                         btrfs_abort_transaction(trans, ret);
1070                         goto out_free_path;
1071                 }
1072                 if (ret)
1073                         break;
1074         }
1075
1076 out_add_root:
1077         btrfs_release_path(path);
1078         ret = add_qgroup_item(trans, quota_root, BTRFS_FS_TREE_OBJECTID);
1079         if (ret) {
1080                 btrfs_abort_transaction(trans, ret);
1081                 goto out_free_path;
1082         }
1083
1084         qgroup = add_qgroup_rb(fs_info, BTRFS_FS_TREE_OBJECTID);
1085         if (IS_ERR(qgroup)) {
1086                 ret = PTR_ERR(qgroup);
1087                 btrfs_abort_transaction(trans, ret);
1088                 goto out_free_path;
1089         }
1090         ret = btrfs_sysfs_add_one_qgroup(fs_info, qgroup);
1091         if (ret < 0) {
1092                 btrfs_abort_transaction(trans, ret);
1093                 goto out_free_path;
1094         }
1095
1096         ret = btrfs_commit_transaction(trans);
1097         trans = NULL;
1098         if (ret)
1099                 goto out_free_path;
1100
1101         /*
1102          * Set quota enabled flag after committing the transaction, to avoid
1103          * deadlocks on fs_info->qgroup_ioctl_lock with concurrent snapshot
1104          * creation.
1105          */
1106         spin_lock(&fs_info->qgroup_lock);
1107         fs_info->quota_root = quota_root;
1108         set_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags);
1109         spin_unlock(&fs_info->qgroup_lock);
1110
1111         ret = qgroup_rescan_init(fs_info, 0, 1);
1112         if (!ret) {
1113                 qgroup_rescan_zero_tracking(fs_info);
1114                 fs_info->qgroup_rescan_running = true;
1115                 btrfs_queue_work(fs_info->qgroup_rescan_workers,
1116                                  &fs_info->qgroup_rescan_work);
1117         }
1118
1119 out_free_path:
1120         btrfs_free_path(path);
1121 out_free_root:
1122         if (ret)
1123                 btrfs_put_root(quota_root);
1124 out:
1125         if (ret) {
1126                 ulist_free(fs_info->qgroup_ulist);
1127                 fs_info->qgroup_ulist = NULL;
1128                 if (trans)
1129                         btrfs_end_transaction(trans);
1130                 btrfs_sysfs_del_qgroups(fs_info);
1131         }
1132         mutex_unlock(&fs_info->qgroup_ioctl_lock);
1133         return ret;
1134 }
1135
1136 int btrfs_quota_disable(struct btrfs_fs_info *fs_info)
1137 {
1138         struct btrfs_root *quota_root;
1139         struct btrfs_trans_handle *trans = NULL;
1140         int ret = 0;
1141
1142         mutex_lock(&fs_info->qgroup_ioctl_lock);
1143         if (!fs_info->quota_root)
1144                 goto out;
1145
1146         /*
1147          * 1 For the root item
1148          *
1149          * We should also reserve enough items for the quota tree deletion in
1150          * btrfs_clean_quota_tree but this is not done.
1151          */
1152         trans = btrfs_start_transaction(fs_info->tree_root, 1);
1153         if (IS_ERR(trans)) {
1154                 ret = PTR_ERR(trans);
1155                 goto out;
1156         }
1157
1158         clear_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags);
1159         btrfs_qgroup_wait_for_completion(fs_info, false);
1160         spin_lock(&fs_info->qgroup_lock);
1161         quota_root = fs_info->quota_root;
1162         fs_info->quota_root = NULL;
1163         fs_info->qgroup_flags &= ~BTRFS_QGROUP_STATUS_FLAG_ON;
1164         spin_unlock(&fs_info->qgroup_lock);
1165
1166         btrfs_free_qgroup_config(fs_info);
1167
1168         ret = btrfs_clean_quota_tree(trans, quota_root);
1169         if (ret) {
1170                 btrfs_abort_transaction(trans, ret);
1171                 goto end_trans;
1172         }
1173
1174         ret = btrfs_del_root(trans, &quota_root->root_key);
1175         if (ret) {
1176                 btrfs_abort_transaction(trans, ret);
1177                 goto end_trans;
1178         }
1179
1180         list_del(&quota_root->dirty_list);
1181
1182         btrfs_tree_lock(quota_root->node);
1183         btrfs_clean_tree_block(quota_root->node);
1184         btrfs_tree_unlock(quota_root->node);
1185         btrfs_free_tree_block(trans, quota_root, quota_root->node, 0, 1);
1186
1187         btrfs_put_root(quota_root);
1188
1189 end_trans:
1190         ret = btrfs_end_transaction(trans);
1191 out:
1192         mutex_unlock(&fs_info->qgroup_ioctl_lock);
1193         return ret;
1194 }
1195
1196 static void qgroup_dirty(struct btrfs_fs_info *fs_info,
1197                          struct btrfs_qgroup *qgroup)
1198 {
1199         if (list_empty(&qgroup->dirty))
1200                 list_add(&qgroup->dirty, &fs_info->dirty_qgroups);
1201 }
1202
1203 /*
1204  * The easy accounting, we're updating qgroup relationship whose child qgroup
1205  * only has exclusive extents.
1206  *
1207  * In this case, all exclusive extents will also be exclusive for parent, so
1208  * excl/rfer just get added/removed.
1209  *
1210  * So is qgroup reservation space, which should also be added/removed to
1211  * parent.
1212  * Or when child tries to release reservation space, parent will underflow its
1213  * reservation (for relationship adding case).
1214  *
1215  * Caller should hold fs_info->qgroup_lock.
1216  */
1217 static int __qgroup_excl_accounting(struct btrfs_fs_info *fs_info,
1218                                     struct ulist *tmp, u64 ref_root,
1219                                     struct btrfs_qgroup *src, int sign)
1220 {
1221         struct btrfs_qgroup *qgroup;
1222         struct btrfs_qgroup_list *glist;
1223         struct ulist_node *unode;
1224         struct ulist_iterator uiter;
1225         u64 num_bytes = src->excl;
1226         int ret = 0;
1227
1228         qgroup = find_qgroup_rb(fs_info, ref_root);
1229         if (!qgroup)
1230                 goto out;
1231
1232         qgroup->rfer += sign * num_bytes;
1233         qgroup->rfer_cmpr += sign * num_bytes;
1234
1235         WARN_ON(sign < 0 && qgroup->excl < num_bytes);
1236         qgroup->excl += sign * num_bytes;
1237         qgroup->excl_cmpr += sign * num_bytes;
1238
1239         if (sign > 0)
1240                 qgroup_rsv_add_by_qgroup(fs_info, qgroup, src);
1241         else
1242                 qgroup_rsv_release_by_qgroup(fs_info, qgroup, src);
1243
1244         qgroup_dirty(fs_info, qgroup);
1245
1246         /* Get all of the parent groups that contain this qgroup */
1247         list_for_each_entry(glist, &qgroup->groups, next_group) {
1248                 ret = ulist_add(tmp, glist->group->qgroupid,
1249                                 qgroup_to_aux(glist->group), GFP_ATOMIC);
1250                 if (ret < 0)
1251                         goto out;
1252         }
1253
1254         /* Iterate all of the parents and adjust their reference counts */
1255         ULIST_ITER_INIT(&uiter);
1256         while ((unode = ulist_next(tmp, &uiter))) {
1257                 qgroup = unode_aux_to_qgroup(unode);
1258                 qgroup->rfer += sign * num_bytes;
1259                 qgroup->rfer_cmpr += sign * num_bytes;
1260                 WARN_ON(sign < 0 && qgroup->excl < num_bytes);
1261                 qgroup->excl += sign * num_bytes;
1262                 if (sign > 0)
1263                         qgroup_rsv_add_by_qgroup(fs_info, qgroup, src);
1264                 else
1265                         qgroup_rsv_release_by_qgroup(fs_info, qgroup, src);
1266                 qgroup->excl_cmpr += sign * num_bytes;
1267                 qgroup_dirty(fs_info, qgroup);
1268
1269                 /* Add any parents of the parents */
1270                 list_for_each_entry(glist, &qgroup->groups, next_group) {
1271                         ret = ulist_add(tmp, glist->group->qgroupid,
1272                                         qgroup_to_aux(glist->group), GFP_ATOMIC);
1273                         if (ret < 0)
1274                                 goto out;
1275                 }
1276         }
1277         ret = 0;
1278 out:
1279         return ret;
1280 }
1281
1282
1283 /*
1284  * Quick path for updating qgroup with only excl refs.
1285  *
1286  * In that case, just update all parent will be enough.
1287  * Or we needs to do a full rescan.
1288  * Caller should also hold fs_info->qgroup_lock.
1289  *
1290  * Return 0 for quick update, return >0 for need to full rescan
1291  * and mark INCONSISTENT flag.
1292  * Return < 0 for other error.
1293  */
1294 static int quick_update_accounting(struct btrfs_fs_info *fs_info,
1295                                    struct ulist *tmp, u64 src, u64 dst,
1296                                    int sign)
1297 {
1298         struct btrfs_qgroup *qgroup;
1299         int ret = 1;
1300         int err = 0;
1301
1302         qgroup = find_qgroup_rb(fs_info, src);
1303         if (!qgroup)
1304                 goto out;
1305         if (qgroup->excl == qgroup->rfer) {
1306                 ret = 0;
1307                 err = __qgroup_excl_accounting(fs_info, tmp, dst,
1308                                                qgroup, sign);
1309                 if (err < 0) {
1310                         ret = err;
1311                         goto out;
1312                 }
1313         }
1314 out:
1315         if (ret)
1316                 fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
1317         return ret;
1318 }
1319
1320 int btrfs_add_qgroup_relation(struct btrfs_trans_handle *trans, u64 src,
1321                               u64 dst)
1322 {
1323         struct btrfs_fs_info *fs_info = trans->fs_info;
1324         struct btrfs_qgroup *parent;
1325         struct btrfs_qgroup *member;
1326         struct btrfs_qgroup_list *list;
1327         struct ulist *tmp;
1328         unsigned int nofs_flag;
1329         int ret = 0;
1330
1331         /* Check the level of src and dst first */
1332         if (btrfs_qgroup_level(src) >= btrfs_qgroup_level(dst))
1333                 return -EINVAL;
1334
1335         /* We hold a transaction handle open, must do a NOFS allocation. */
1336         nofs_flag = memalloc_nofs_save();
1337         tmp = ulist_alloc(GFP_KERNEL);
1338         memalloc_nofs_restore(nofs_flag);
1339         if (!tmp)
1340                 return -ENOMEM;
1341
1342         mutex_lock(&fs_info->qgroup_ioctl_lock);
1343         if (!fs_info->quota_root) {
1344                 ret = -ENOTCONN;
1345                 goto out;
1346         }
1347         member = find_qgroup_rb(fs_info, src);
1348         parent = find_qgroup_rb(fs_info, dst);
1349         if (!member || !parent) {
1350                 ret = -EINVAL;
1351                 goto out;
1352         }
1353
1354         /* check if such qgroup relation exist firstly */
1355         list_for_each_entry(list, &member->groups, next_group) {
1356                 if (list->group == parent) {
1357                         ret = -EEXIST;
1358                         goto out;
1359                 }
1360         }
1361
1362         ret = add_qgroup_relation_item(trans, src, dst);
1363         if (ret)
1364                 goto out;
1365
1366         ret = add_qgroup_relation_item(trans, dst, src);
1367         if (ret) {
1368                 del_qgroup_relation_item(trans, src, dst);
1369                 goto out;
1370         }
1371
1372         spin_lock(&fs_info->qgroup_lock);
1373         ret = add_relation_rb(fs_info, src, dst);
1374         if (ret < 0) {
1375                 spin_unlock(&fs_info->qgroup_lock);
1376                 goto out;
1377         }
1378         ret = quick_update_accounting(fs_info, tmp, src, dst, 1);
1379         spin_unlock(&fs_info->qgroup_lock);
1380 out:
1381         mutex_unlock(&fs_info->qgroup_ioctl_lock);
1382         ulist_free(tmp);
1383         return ret;
1384 }
1385
1386 static int __del_qgroup_relation(struct btrfs_trans_handle *trans, u64 src,
1387                                  u64 dst)
1388 {
1389         struct btrfs_fs_info *fs_info = trans->fs_info;
1390         struct btrfs_qgroup *parent;
1391         struct btrfs_qgroup *member;
1392         struct btrfs_qgroup_list *list;
1393         struct ulist *tmp;
1394         bool found = false;
1395         unsigned int nofs_flag;
1396         int ret = 0;
1397         int ret2;
1398
1399         /* We hold a transaction handle open, must do a NOFS allocation. */
1400         nofs_flag = memalloc_nofs_save();
1401         tmp = ulist_alloc(GFP_KERNEL);
1402         memalloc_nofs_restore(nofs_flag);
1403         if (!tmp)
1404                 return -ENOMEM;
1405
1406         if (!fs_info->quota_root) {
1407                 ret = -ENOTCONN;
1408                 goto out;
1409         }
1410
1411         member = find_qgroup_rb(fs_info, src);
1412         parent = find_qgroup_rb(fs_info, dst);
1413         /*
1414          * The parent/member pair doesn't exist, then try to delete the dead
1415          * relation items only.
1416          */
1417         if (!member || !parent)
1418                 goto delete_item;
1419
1420         /* check if such qgroup relation exist firstly */
1421         list_for_each_entry(list, &member->groups, next_group) {
1422                 if (list->group == parent) {
1423                         found = true;
1424                         break;
1425                 }
1426         }
1427
1428 delete_item:
1429         ret = del_qgroup_relation_item(trans, src, dst);
1430         if (ret < 0 && ret != -ENOENT)
1431                 goto out;
1432         ret2 = del_qgroup_relation_item(trans, dst, src);
1433         if (ret2 < 0 && ret2 != -ENOENT)
1434                 goto out;
1435
1436         /* At least one deletion succeeded, return 0 */
1437         if (!ret || !ret2)
1438                 ret = 0;
1439
1440         if (found) {
1441                 spin_lock(&fs_info->qgroup_lock);
1442                 del_relation_rb(fs_info, src, dst);
1443                 ret = quick_update_accounting(fs_info, tmp, src, dst, -1);
1444                 spin_unlock(&fs_info->qgroup_lock);
1445         }
1446 out:
1447         ulist_free(tmp);
1448         return ret;
1449 }
1450
1451 int btrfs_del_qgroup_relation(struct btrfs_trans_handle *trans, u64 src,
1452                               u64 dst)
1453 {
1454         struct btrfs_fs_info *fs_info = trans->fs_info;
1455         int ret = 0;
1456
1457         mutex_lock(&fs_info->qgroup_ioctl_lock);
1458         ret = __del_qgroup_relation(trans, src, dst);
1459         mutex_unlock(&fs_info->qgroup_ioctl_lock);
1460
1461         return ret;
1462 }
1463
1464 int btrfs_create_qgroup(struct btrfs_trans_handle *trans, u64 qgroupid)
1465 {
1466         struct btrfs_fs_info *fs_info = trans->fs_info;
1467         struct btrfs_root *quota_root;
1468         struct btrfs_qgroup *qgroup;
1469         int ret = 0;
1470
1471         mutex_lock(&fs_info->qgroup_ioctl_lock);
1472         if (!fs_info->quota_root) {
1473                 ret = -ENOTCONN;
1474                 goto out;
1475         }
1476         quota_root = fs_info->quota_root;
1477         qgroup = find_qgroup_rb(fs_info, qgroupid);
1478         if (qgroup) {
1479                 ret = -EEXIST;
1480                 goto out;
1481         }
1482
1483         ret = add_qgroup_item(trans, quota_root, qgroupid);
1484         if (ret)
1485                 goto out;
1486
1487         spin_lock(&fs_info->qgroup_lock);
1488         qgroup = add_qgroup_rb(fs_info, qgroupid);
1489         spin_unlock(&fs_info->qgroup_lock);
1490
1491         if (IS_ERR(qgroup)) {
1492                 ret = PTR_ERR(qgroup);
1493                 goto out;
1494         }
1495         ret = btrfs_sysfs_add_one_qgroup(fs_info, qgroup);
1496 out:
1497         mutex_unlock(&fs_info->qgroup_ioctl_lock);
1498         return ret;
1499 }
1500
1501 int btrfs_remove_qgroup(struct btrfs_trans_handle *trans, u64 qgroupid)
1502 {
1503         struct btrfs_fs_info *fs_info = trans->fs_info;
1504         struct btrfs_qgroup *qgroup;
1505         struct btrfs_qgroup_list *list;
1506         int ret = 0;
1507
1508         mutex_lock(&fs_info->qgroup_ioctl_lock);
1509         if (!fs_info->quota_root) {
1510                 ret = -ENOTCONN;
1511                 goto out;
1512         }
1513
1514         qgroup = find_qgroup_rb(fs_info, qgroupid);
1515         if (!qgroup) {
1516                 ret = -ENOENT;
1517                 goto out;
1518         }
1519
1520         /* Check if there are no children of this qgroup */
1521         if (!list_empty(&qgroup->members)) {
1522                 ret = -EBUSY;
1523                 goto out;
1524         }
1525
1526         ret = del_qgroup_item(trans, qgroupid);
1527         if (ret && ret != -ENOENT)
1528                 goto out;
1529
1530         while (!list_empty(&qgroup->groups)) {
1531                 list = list_first_entry(&qgroup->groups,
1532                                         struct btrfs_qgroup_list, next_group);
1533                 ret = __del_qgroup_relation(trans, qgroupid,
1534                                             list->group->qgroupid);
1535                 if (ret)
1536                         goto out;
1537         }
1538
1539         spin_lock(&fs_info->qgroup_lock);
1540         del_qgroup_rb(fs_info, qgroupid);
1541         spin_unlock(&fs_info->qgroup_lock);
1542 out:
1543         mutex_unlock(&fs_info->qgroup_ioctl_lock);
1544         return ret;
1545 }
1546
1547 int btrfs_limit_qgroup(struct btrfs_trans_handle *trans, u64 qgroupid,
1548                        struct btrfs_qgroup_limit *limit)
1549 {
1550         struct btrfs_fs_info *fs_info = trans->fs_info;
1551         struct btrfs_qgroup *qgroup;
1552         int ret = 0;
1553         /* Sometimes we would want to clear the limit on this qgroup.
1554          * To meet this requirement, we treat the -1 as a special value
1555          * which tell kernel to clear the limit on this qgroup.
1556          */
1557         const u64 CLEAR_VALUE = -1;
1558
1559         mutex_lock(&fs_info->qgroup_ioctl_lock);
1560         if (!fs_info->quota_root) {
1561                 ret = -ENOTCONN;
1562                 goto out;
1563         }
1564
1565         qgroup = find_qgroup_rb(fs_info, qgroupid);
1566         if (!qgroup) {
1567                 ret = -ENOENT;
1568                 goto out;
1569         }
1570
1571         spin_lock(&fs_info->qgroup_lock);
1572         if (limit->flags & BTRFS_QGROUP_LIMIT_MAX_RFER) {
1573                 if (limit->max_rfer == CLEAR_VALUE) {
1574                         qgroup->lim_flags &= ~BTRFS_QGROUP_LIMIT_MAX_RFER;
1575                         limit->flags &= ~BTRFS_QGROUP_LIMIT_MAX_RFER;
1576                         qgroup->max_rfer = 0;
1577                 } else {
1578                         qgroup->max_rfer = limit->max_rfer;
1579                 }
1580         }
1581         if (limit->flags & BTRFS_QGROUP_LIMIT_MAX_EXCL) {
1582                 if (limit->max_excl == CLEAR_VALUE) {
1583                         qgroup->lim_flags &= ~BTRFS_QGROUP_LIMIT_MAX_EXCL;
1584                         limit->flags &= ~BTRFS_QGROUP_LIMIT_MAX_EXCL;
1585                         qgroup->max_excl = 0;
1586                 } else {
1587                         qgroup->max_excl = limit->max_excl;
1588                 }
1589         }
1590         if (limit->flags & BTRFS_QGROUP_LIMIT_RSV_RFER) {
1591                 if (limit->rsv_rfer == CLEAR_VALUE) {
1592                         qgroup->lim_flags &= ~BTRFS_QGROUP_LIMIT_RSV_RFER;
1593                         limit->flags &= ~BTRFS_QGROUP_LIMIT_RSV_RFER;
1594                         qgroup->rsv_rfer = 0;
1595                 } else {
1596                         qgroup->rsv_rfer = limit->rsv_rfer;
1597                 }
1598         }
1599         if (limit->flags & BTRFS_QGROUP_LIMIT_RSV_EXCL) {
1600                 if (limit->rsv_excl == CLEAR_VALUE) {
1601                         qgroup->lim_flags &= ~BTRFS_QGROUP_LIMIT_RSV_EXCL;
1602                         limit->flags &= ~BTRFS_QGROUP_LIMIT_RSV_EXCL;
1603                         qgroup->rsv_excl = 0;
1604                 } else {
1605                         qgroup->rsv_excl = limit->rsv_excl;
1606                 }
1607         }
1608         qgroup->lim_flags |= limit->flags;
1609
1610         spin_unlock(&fs_info->qgroup_lock);
1611
1612         ret = update_qgroup_limit_item(trans, qgroup);
1613         if (ret) {
1614                 fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
1615                 btrfs_info(fs_info, "unable to update quota limit for %llu",
1616                        qgroupid);
1617         }
1618
1619 out:
1620         mutex_unlock(&fs_info->qgroup_ioctl_lock);
1621         return ret;
1622 }
1623
1624 int btrfs_qgroup_trace_extent_nolock(struct btrfs_fs_info *fs_info,
1625                                 struct btrfs_delayed_ref_root *delayed_refs,
1626                                 struct btrfs_qgroup_extent_record *record)
1627 {
1628         struct rb_node **p = &delayed_refs->dirty_extent_root.rb_node;
1629         struct rb_node *parent_node = NULL;
1630         struct btrfs_qgroup_extent_record *entry;
1631         u64 bytenr = record->bytenr;
1632
1633         lockdep_assert_held(&delayed_refs->lock);
1634         trace_btrfs_qgroup_trace_extent(fs_info, record);
1635
1636         while (*p) {
1637                 parent_node = *p;
1638                 entry = rb_entry(parent_node, struct btrfs_qgroup_extent_record,
1639                                  node);
1640                 if (bytenr < entry->bytenr) {
1641                         p = &(*p)->rb_left;
1642                 } else if (bytenr > entry->bytenr) {
1643                         p = &(*p)->rb_right;
1644                 } else {
1645                         if (record->data_rsv && !entry->data_rsv) {
1646                                 entry->data_rsv = record->data_rsv;
1647                                 entry->data_rsv_refroot =
1648                                         record->data_rsv_refroot;
1649                         }
1650                         return 1;
1651                 }
1652         }
1653
1654         rb_link_node(&record->node, parent_node, p);
1655         rb_insert_color(&record->node, &delayed_refs->dirty_extent_root);
1656         return 0;
1657 }
1658
1659 int btrfs_qgroup_trace_extent_post(struct btrfs_fs_info *fs_info,
1660                                    struct btrfs_qgroup_extent_record *qrecord)
1661 {
1662         struct ulist *old_root;
1663         u64 bytenr = qrecord->bytenr;
1664         int ret;
1665
1666         ret = btrfs_find_all_roots(NULL, fs_info, bytenr, 0, &old_root, false);
1667         if (ret < 0) {
1668                 fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
1669                 btrfs_warn(fs_info,
1670 "error accounting new delayed refs extent (err code: %d), quota inconsistent",
1671                         ret);
1672                 return 0;
1673         }
1674
1675         /*
1676          * Here we don't need to get the lock of
1677          * trans->transaction->delayed_refs, since inserted qrecord won't
1678          * be deleted, only qrecord->node may be modified (new qrecord insert)
1679          *
1680          * So modifying qrecord->old_roots is safe here
1681          */
1682         qrecord->old_roots = old_root;
1683         return 0;
1684 }
1685
1686 int btrfs_qgroup_trace_extent(struct btrfs_trans_handle *trans, u64 bytenr,
1687                               u64 num_bytes, gfp_t gfp_flag)
1688 {
1689         struct btrfs_fs_info *fs_info = trans->fs_info;
1690         struct btrfs_qgroup_extent_record *record;
1691         struct btrfs_delayed_ref_root *delayed_refs;
1692         int ret;
1693
1694         if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags)
1695             || bytenr == 0 || num_bytes == 0)
1696                 return 0;
1697         record = kzalloc(sizeof(*record), gfp_flag);
1698         if (!record)
1699                 return -ENOMEM;
1700
1701         delayed_refs = &trans->transaction->delayed_refs;
1702         record->bytenr = bytenr;
1703         record->num_bytes = num_bytes;
1704         record->old_roots = NULL;
1705
1706         spin_lock(&delayed_refs->lock);
1707         ret = btrfs_qgroup_trace_extent_nolock(fs_info, delayed_refs, record);
1708         spin_unlock(&delayed_refs->lock);
1709         if (ret > 0) {
1710                 kfree(record);
1711                 return 0;
1712         }
1713         return btrfs_qgroup_trace_extent_post(fs_info, record);
1714 }
1715
1716 int btrfs_qgroup_trace_leaf_items(struct btrfs_trans_handle *trans,
1717                                   struct extent_buffer *eb)
1718 {
1719         struct btrfs_fs_info *fs_info = trans->fs_info;
1720         int nr = btrfs_header_nritems(eb);
1721         int i, extent_type, ret;
1722         struct btrfs_key key;
1723         struct btrfs_file_extent_item *fi;
1724         u64 bytenr, num_bytes;
1725
1726         /* We can be called directly from walk_up_proc() */
1727         if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags))
1728                 return 0;
1729
1730         for (i = 0; i < nr; i++) {
1731                 btrfs_item_key_to_cpu(eb, &key, i);
1732
1733                 if (key.type != BTRFS_EXTENT_DATA_KEY)
1734                         continue;
1735
1736                 fi = btrfs_item_ptr(eb, i, struct btrfs_file_extent_item);
1737                 /* filter out non qgroup-accountable extents  */
1738                 extent_type = btrfs_file_extent_type(eb, fi);
1739
1740                 if (extent_type == BTRFS_FILE_EXTENT_INLINE)
1741                         continue;
1742
1743                 bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
1744                 if (!bytenr)
1745                         continue;
1746
1747                 num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
1748
1749                 ret = btrfs_qgroup_trace_extent(trans, bytenr, num_bytes,
1750                                                 GFP_NOFS);
1751                 if (ret)
1752                         return ret;
1753         }
1754         cond_resched();
1755         return 0;
1756 }
1757
1758 /*
1759  * Walk up the tree from the bottom, freeing leaves and any interior
1760  * nodes which have had all slots visited. If a node (leaf or
1761  * interior) is freed, the node above it will have it's slot
1762  * incremented. The root node will never be freed.
1763  *
1764  * At the end of this function, we should have a path which has all
1765  * slots incremented to the next position for a search. If we need to
1766  * read a new node it will be NULL and the node above it will have the
1767  * correct slot selected for a later read.
1768  *
1769  * If we increment the root nodes slot counter past the number of
1770  * elements, 1 is returned to signal completion of the search.
1771  */
1772 static int adjust_slots_upwards(struct btrfs_path *path, int root_level)
1773 {
1774         int level = 0;
1775         int nr, slot;
1776         struct extent_buffer *eb;
1777
1778         if (root_level == 0)
1779                 return 1;
1780
1781         while (level <= root_level) {
1782                 eb = path->nodes[level];
1783                 nr = btrfs_header_nritems(eb);
1784                 path->slots[level]++;
1785                 slot = path->slots[level];
1786                 if (slot >= nr || level == 0) {
1787                         /*
1788                          * Don't free the root -  we will detect this
1789                          * condition after our loop and return a
1790                          * positive value for caller to stop walking the tree.
1791                          */
1792                         if (level != root_level) {
1793                                 btrfs_tree_unlock_rw(eb, path->locks[level]);
1794                                 path->locks[level] = 0;
1795
1796                                 free_extent_buffer(eb);
1797                                 path->nodes[level] = NULL;
1798                                 path->slots[level] = 0;
1799                         }
1800                 } else {
1801                         /*
1802                          * We have a valid slot to walk back down
1803                          * from. Stop here so caller can process these
1804                          * new nodes.
1805                          */
1806                         break;
1807                 }
1808
1809                 level++;
1810         }
1811
1812         eb = path->nodes[root_level];
1813         if (path->slots[root_level] >= btrfs_header_nritems(eb))
1814                 return 1;
1815
1816         return 0;
1817 }
1818
1819 /*
1820  * Helper function to trace a subtree tree block swap.
1821  *
1822  * The swap will happen in highest tree block, but there may be a lot of
1823  * tree blocks involved.
1824  *
1825  * For example:
1826  *  OO = Old tree blocks
1827  *  NN = New tree blocks allocated during balance
1828  *
1829  *           File tree (257)                  Reloc tree for 257
1830  * L2              OO                                NN
1831  *               /    \                            /    \
1832  * L1          OO      OO (a)                    OO      NN (a)
1833  *            / \     / \                       / \     / \
1834  * L0       OO   OO OO   OO                   OO   OO NN   NN
1835  *                  (b)  (c)                          (b)  (c)
1836  *
1837  * When calling qgroup_trace_extent_swap(), we will pass:
1838  * @src_eb = OO(a)
1839  * @dst_path = [ nodes[1] = NN(a), nodes[0] = NN(c) ]
1840  * @dst_level = 0
1841  * @root_level = 1
1842  *
1843  * In that case, qgroup_trace_extent_swap() will search from OO(a) to
1844  * reach OO(c), then mark both OO(c) and NN(c) as qgroup dirty.
1845  *
1846  * The main work of qgroup_trace_extent_swap() can be split into 3 parts:
1847  *
1848  * 1) Tree search from @src_eb
1849  *    It should acts as a simplified btrfs_search_slot().
1850  *    The key for search can be extracted from @dst_path->nodes[dst_level]
1851  *    (first key).
1852  *
1853  * 2) Mark the final tree blocks in @src_path and @dst_path qgroup dirty
1854  *    NOTE: In above case, OO(a) and NN(a) won't be marked qgroup dirty.
1855  *    They should be marked during previous (@dst_level = 1) iteration.
1856  *
1857  * 3) Mark file extents in leaves dirty
1858  *    We don't have good way to pick out new file extents only.
1859  *    So we still follow the old method by scanning all file extents in
1860  *    the leave.
1861  *
1862  * This function can free us from keeping two paths, thus later we only need
1863  * to care about how to iterate all new tree blocks in reloc tree.
1864  */
1865 static int qgroup_trace_extent_swap(struct btrfs_trans_handle* trans,
1866                                     struct extent_buffer *src_eb,
1867                                     struct btrfs_path *dst_path,
1868                                     int dst_level, int root_level,
1869                                     bool trace_leaf)
1870 {
1871         struct btrfs_key key;
1872         struct btrfs_path *src_path;
1873         struct btrfs_fs_info *fs_info = trans->fs_info;
1874         u32 nodesize = fs_info->nodesize;
1875         int cur_level = root_level;
1876         int ret;
1877
1878         BUG_ON(dst_level > root_level);
1879         /* Level mismatch */
1880         if (btrfs_header_level(src_eb) != root_level)
1881                 return -EINVAL;
1882
1883         src_path = btrfs_alloc_path();
1884         if (!src_path) {
1885                 ret = -ENOMEM;
1886                 goto out;
1887         }
1888
1889         if (dst_level)
1890                 btrfs_node_key_to_cpu(dst_path->nodes[dst_level], &key, 0);
1891         else
1892                 btrfs_item_key_to_cpu(dst_path->nodes[dst_level], &key, 0);
1893
1894         /* For src_path */
1895         atomic_inc(&src_eb->refs);
1896         src_path->nodes[root_level] = src_eb;
1897         src_path->slots[root_level] = dst_path->slots[root_level];
1898         src_path->locks[root_level] = 0;
1899
1900         /* A simplified version of btrfs_search_slot() */
1901         while (cur_level >= dst_level) {
1902                 struct btrfs_key src_key;
1903                 struct btrfs_key dst_key;
1904
1905                 if (src_path->nodes[cur_level] == NULL) {
1906                         struct btrfs_key first_key;
1907                         struct extent_buffer *eb;
1908                         int parent_slot;
1909                         u64 child_gen;
1910                         u64 child_bytenr;
1911
1912                         eb = src_path->nodes[cur_level + 1];
1913                         parent_slot = src_path->slots[cur_level + 1];
1914                         child_bytenr = btrfs_node_blockptr(eb, parent_slot);
1915                         child_gen = btrfs_node_ptr_generation(eb, parent_slot);
1916                         btrfs_node_key_to_cpu(eb, &first_key, parent_slot);
1917
1918                         eb = read_tree_block(fs_info, child_bytenr, child_gen,
1919                                              cur_level, &first_key);
1920                         if (IS_ERR(eb)) {
1921                                 ret = PTR_ERR(eb);
1922                                 goto out;
1923                         } else if (!extent_buffer_uptodate(eb)) {
1924                                 free_extent_buffer(eb);
1925                                 ret = -EIO;
1926                                 goto out;
1927                         }
1928
1929                         src_path->nodes[cur_level] = eb;
1930
1931                         btrfs_tree_read_lock(eb);
1932                         btrfs_set_lock_blocking_read(eb);
1933                         src_path->locks[cur_level] = BTRFS_READ_LOCK_BLOCKING;
1934                 }
1935
1936                 src_path->slots[cur_level] = dst_path->slots[cur_level];
1937                 if (cur_level) {
1938                         btrfs_node_key_to_cpu(dst_path->nodes[cur_level],
1939                                         &dst_key, dst_path->slots[cur_level]);
1940                         btrfs_node_key_to_cpu(src_path->nodes[cur_level],
1941                                         &src_key, src_path->slots[cur_level]);
1942                 } else {
1943                         btrfs_item_key_to_cpu(dst_path->nodes[cur_level],
1944                                         &dst_key, dst_path->slots[cur_level]);
1945                         btrfs_item_key_to_cpu(src_path->nodes[cur_level],
1946                                         &src_key, src_path->slots[cur_level]);
1947                 }
1948                 /* Content mismatch, something went wrong */
1949                 if (btrfs_comp_cpu_keys(&dst_key, &src_key)) {
1950                         ret = -ENOENT;
1951                         goto out;
1952                 }
1953                 cur_level--;
1954         }
1955
1956         /*
1957          * Now both @dst_path and @src_path have been populated, record the tree
1958          * blocks for qgroup accounting.
1959          */
1960         ret = btrfs_qgroup_trace_extent(trans, src_path->nodes[dst_level]->start,
1961                         nodesize, GFP_NOFS);
1962         if (ret < 0)
1963                 goto out;
1964         ret = btrfs_qgroup_trace_extent(trans,
1965                         dst_path->nodes[dst_level]->start,
1966                         nodesize, GFP_NOFS);
1967         if (ret < 0)
1968                 goto out;
1969
1970         /* Record leaf file extents */
1971         if (dst_level == 0 && trace_leaf) {
1972                 ret = btrfs_qgroup_trace_leaf_items(trans, src_path->nodes[0]);
1973                 if (ret < 0)
1974                         goto out;
1975                 ret = btrfs_qgroup_trace_leaf_items(trans, dst_path->nodes[0]);
1976         }
1977 out:
1978         btrfs_free_path(src_path);
1979         return ret;
1980 }
1981
1982 /*
1983  * Helper function to do recursive generation-aware depth-first search, to
1984  * locate all new tree blocks in a subtree of reloc tree.
1985  *
1986  * E.g. (OO = Old tree blocks, NN = New tree blocks, whose gen == last_snapshot)
1987  *         reloc tree
1988  * L2         NN (a)
1989  *          /    \
1990  * L1    OO        NN (b)
1991  *      /  \      /  \
1992  * L0  OO  OO    OO  NN
1993  *               (c) (d)
1994  * If we pass:
1995  * @dst_path = [ nodes[1] = NN(b), nodes[0] = NULL ],
1996  * @cur_level = 1
1997  * @root_level = 1
1998  *
1999  * We will iterate through tree blocks NN(b), NN(d) and info qgroup to trace
2000  * above tree blocks along with their counter parts in file tree.
2001  * While during search, old tree blocks OO(c) will be skipped as tree block swap
2002  * won't affect OO(c).
2003  */
2004 static int qgroup_trace_new_subtree_blocks(struct btrfs_trans_handle* trans,
2005                                            struct extent_buffer *src_eb,
2006                                            struct btrfs_path *dst_path,
2007                                            int cur_level, int root_level,
2008                                            u64 last_snapshot, bool trace_leaf)
2009 {
2010         struct btrfs_fs_info *fs_info = trans->fs_info;
2011         struct extent_buffer *eb;
2012         bool need_cleanup = false;
2013         int ret = 0;
2014         int i;
2015
2016         /* Level sanity check */
2017         if (cur_level < 0 || cur_level >= BTRFS_MAX_LEVEL - 1 ||
2018             root_level < 0 || root_level >= BTRFS_MAX_LEVEL - 1 ||
2019             root_level < cur_level) {
2020                 btrfs_err_rl(fs_info,
2021                         "%s: bad levels, cur_level=%d root_level=%d",
2022                         __func__, cur_level, root_level);
2023                 return -EUCLEAN;
2024         }
2025
2026         /* Read the tree block if needed */
2027         if (dst_path->nodes[cur_level] == NULL) {
2028                 struct btrfs_key first_key;
2029                 int parent_slot;
2030                 u64 child_gen;
2031                 u64 child_bytenr;
2032
2033                 /*
2034                  * dst_path->nodes[root_level] must be initialized before
2035                  * calling this function.
2036                  */
2037                 if (cur_level == root_level) {
2038                         btrfs_err_rl(fs_info,
2039         "%s: dst_path->nodes[%d] not initialized, root_level=%d cur_level=%d",
2040                                 __func__, root_level, root_level, cur_level);
2041                         return -EUCLEAN;
2042                 }
2043
2044                 /*
2045                  * We need to get child blockptr/gen from parent before we can
2046                  * read it.
2047                   */
2048                 eb = dst_path->nodes[cur_level + 1];
2049                 parent_slot = dst_path->slots[cur_level + 1];
2050                 child_bytenr = btrfs_node_blockptr(eb, parent_slot);
2051                 child_gen = btrfs_node_ptr_generation(eb, parent_slot);
2052                 btrfs_node_key_to_cpu(eb, &first_key, parent_slot);
2053
2054                 /* This node is old, no need to trace */
2055                 if (child_gen < last_snapshot)
2056                         goto out;
2057
2058                 eb = read_tree_block(fs_info, child_bytenr, child_gen,
2059                                      cur_level, &first_key);
2060                 if (IS_ERR(eb)) {
2061                         ret = PTR_ERR(eb);
2062                         goto out;
2063                 } else if (!extent_buffer_uptodate(eb)) {
2064                         free_extent_buffer(eb);
2065                         ret = -EIO;
2066                         goto out;
2067                 }
2068
2069                 dst_path->nodes[cur_level] = eb;
2070                 dst_path->slots[cur_level] = 0;
2071
2072                 btrfs_tree_read_lock(eb);
2073                 btrfs_set_lock_blocking_read(eb);
2074                 dst_path->locks[cur_level] = BTRFS_READ_LOCK_BLOCKING;
2075                 need_cleanup = true;
2076         }
2077
2078         /* Now record this tree block and its counter part for qgroups */
2079         ret = qgroup_trace_extent_swap(trans, src_eb, dst_path, cur_level,
2080                                        root_level, trace_leaf);
2081         if (ret < 0)
2082                 goto cleanup;
2083
2084         eb = dst_path->nodes[cur_level];
2085
2086         if (cur_level > 0) {
2087                 /* Iterate all child tree blocks */
2088                 for (i = 0; i < btrfs_header_nritems(eb); i++) {
2089                         /* Skip old tree blocks as they won't be swapped */
2090                         if (btrfs_node_ptr_generation(eb, i) < last_snapshot)
2091                                 continue;
2092                         dst_path->slots[cur_level] = i;
2093
2094                         /* Recursive call (at most 7 times) */
2095                         ret = qgroup_trace_new_subtree_blocks(trans, src_eb,
2096                                         dst_path, cur_level - 1, root_level,
2097                                         last_snapshot, trace_leaf);
2098                         if (ret < 0)
2099                                 goto cleanup;
2100                 }
2101         }
2102
2103 cleanup:
2104         if (need_cleanup) {
2105                 /* Clean up */
2106                 btrfs_tree_unlock_rw(dst_path->nodes[cur_level],
2107                                      dst_path->locks[cur_level]);
2108                 free_extent_buffer(dst_path->nodes[cur_level]);
2109                 dst_path->nodes[cur_level] = NULL;
2110                 dst_path->slots[cur_level] = 0;
2111                 dst_path->locks[cur_level] = 0;
2112         }
2113 out:
2114         return ret;
2115 }
2116
2117 static int qgroup_trace_subtree_swap(struct btrfs_trans_handle *trans,
2118                                 struct extent_buffer *src_eb,
2119                                 struct extent_buffer *dst_eb,
2120                                 u64 last_snapshot, bool trace_leaf)
2121 {
2122         struct btrfs_fs_info *fs_info = trans->fs_info;
2123         struct btrfs_path *dst_path = NULL;
2124         int level;
2125         int ret;
2126
2127         if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags))
2128                 return 0;
2129
2130         /* Wrong parameter order */
2131         if (btrfs_header_generation(src_eb) > btrfs_header_generation(dst_eb)) {
2132                 btrfs_err_rl(fs_info,
2133                 "%s: bad parameter order, src_gen=%llu dst_gen=%llu", __func__,
2134                              btrfs_header_generation(src_eb),
2135                              btrfs_header_generation(dst_eb));
2136                 return -EUCLEAN;
2137         }
2138
2139         if (!extent_buffer_uptodate(src_eb) || !extent_buffer_uptodate(dst_eb)) {
2140                 ret = -EIO;
2141                 goto out;
2142         }
2143
2144         level = btrfs_header_level(dst_eb);
2145         dst_path = btrfs_alloc_path();
2146         if (!dst_path) {
2147                 ret = -ENOMEM;
2148                 goto out;
2149         }
2150         /* For dst_path */
2151         atomic_inc(&dst_eb->refs);
2152         dst_path->nodes[level] = dst_eb;
2153         dst_path->slots[level] = 0;
2154         dst_path->locks[level] = 0;
2155
2156         /* Do the generation aware breadth-first search */
2157         ret = qgroup_trace_new_subtree_blocks(trans, src_eb, dst_path, level,
2158                                               level, last_snapshot, trace_leaf);
2159         if (ret < 0)
2160                 goto out;
2161         ret = 0;
2162
2163 out:
2164         btrfs_free_path(dst_path);
2165         if (ret < 0)
2166                 fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
2167         return ret;
2168 }
2169
2170 int btrfs_qgroup_trace_subtree(struct btrfs_trans_handle *trans,
2171                                struct extent_buffer *root_eb,
2172                                u64 root_gen, int root_level)
2173 {
2174         struct btrfs_fs_info *fs_info = trans->fs_info;
2175         int ret = 0;
2176         int level;
2177         struct extent_buffer *eb = root_eb;
2178         struct btrfs_path *path = NULL;
2179
2180         BUG_ON(root_level < 0 || root_level >= BTRFS_MAX_LEVEL);
2181         BUG_ON(root_eb == NULL);
2182
2183         if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags))
2184                 return 0;
2185
2186         if (!extent_buffer_uptodate(root_eb)) {
2187                 ret = btrfs_read_buffer(root_eb, root_gen, root_level, NULL);
2188                 if (ret)
2189                         goto out;
2190         }
2191
2192         if (root_level == 0) {
2193                 ret = btrfs_qgroup_trace_leaf_items(trans, root_eb);
2194                 goto out;
2195         }
2196
2197         path = btrfs_alloc_path();
2198         if (!path)
2199                 return -ENOMEM;
2200
2201         /*
2202          * Walk down the tree.  Missing extent blocks are filled in as
2203          * we go. Metadata is accounted every time we read a new
2204          * extent block.
2205          *
2206          * When we reach a leaf, we account for file extent items in it,
2207          * walk back up the tree (adjusting slot pointers as we go)
2208          * and restart the search process.
2209          */
2210         atomic_inc(&root_eb->refs);     /* For path */
2211         path->nodes[root_level] = root_eb;
2212         path->slots[root_level] = 0;
2213         path->locks[root_level] = 0; /* so release_path doesn't try to unlock */
2214 walk_down:
2215         level = root_level;
2216         while (level >= 0) {
2217                 if (path->nodes[level] == NULL) {
2218                         struct btrfs_key first_key;
2219                         int parent_slot;
2220                         u64 child_gen;
2221                         u64 child_bytenr;
2222
2223                         /*
2224                          * We need to get child blockptr/gen from parent before
2225                          * we can read it.
2226                           */
2227                         eb = path->nodes[level + 1];
2228                         parent_slot = path->slots[level + 1];
2229                         child_bytenr = btrfs_node_blockptr(eb, parent_slot);
2230                         child_gen = btrfs_node_ptr_generation(eb, parent_slot);
2231                         btrfs_node_key_to_cpu(eb, &first_key, parent_slot);
2232
2233                         eb = read_tree_block(fs_info, child_bytenr, child_gen,
2234                                              level, &first_key);
2235                         if (IS_ERR(eb)) {
2236                                 ret = PTR_ERR(eb);
2237                                 goto out;
2238                         } else if (!extent_buffer_uptodate(eb)) {
2239                                 free_extent_buffer(eb);
2240                                 ret = -EIO;
2241                                 goto out;
2242                         }
2243
2244                         path->nodes[level] = eb;
2245                         path->slots[level] = 0;
2246
2247                         btrfs_tree_read_lock(eb);
2248                         btrfs_set_lock_blocking_read(eb);
2249                         path->locks[level] = BTRFS_READ_LOCK_BLOCKING;
2250
2251                         ret = btrfs_qgroup_trace_extent(trans, child_bytenr,
2252                                                         fs_info->nodesize,
2253                                                         GFP_NOFS);
2254                         if (ret)
2255                                 goto out;
2256                 }
2257
2258                 if (level == 0) {
2259                         ret = btrfs_qgroup_trace_leaf_items(trans,
2260                                                             path->nodes[level]);
2261                         if (ret)
2262                                 goto out;
2263
2264                         /* Nonzero return here means we completed our search */
2265                         ret = adjust_slots_upwards(path, root_level);
2266                         if (ret)
2267                                 break;
2268
2269                         /* Restart search with new slots */
2270                         goto walk_down;
2271                 }
2272
2273                 level--;
2274         }
2275
2276         ret = 0;
2277 out:
2278         btrfs_free_path(path);
2279
2280         return ret;
2281 }
2282
2283 #define UPDATE_NEW      0
2284 #define UPDATE_OLD      1
2285 /*
2286  * Walk all of the roots that points to the bytenr and adjust their refcnts.
2287  */
2288 static int qgroup_update_refcnt(struct btrfs_fs_info *fs_info,
2289                                 struct ulist *roots, struct ulist *tmp,
2290                                 struct ulist *qgroups, u64 seq, int update_old)
2291 {
2292         struct ulist_node *unode;
2293         struct ulist_iterator uiter;
2294         struct ulist_node *tmp_unode;
2295         struct ulist_iterator tmp_uiter;
2296         struct btrfs_qgroup *qg;
2297         int ret = 0;
2298
2299         if (!roots)
2300                 return 0;
2301         ULIST_ITER_INIT(&uiter);
2302         while ((unode = ulist_next(roots, &uiter))) {
2303                 qg = find_qgroup_rb(fs_info, unode->val);
2304                 if (!qg)
2305                         continue;
2306
2307                 ulist_reinit(tmp);
2308                 ret = ulist_add(qgroups, qg->qgroupid, qgroup_to_aux(qg),
2309                                 GFP_ATOMIC);
2310                 if (ret < 0)
2311                         return ret;
2312                 ret = ulist_add(tmp, qg->qgroupid, qgroup_to_aux(qg), GFP_ATOMIC);
2313                 if (ret < 0)
2314                         return ret;
2315                 ULIST_ITER_INIT(&tmp_uiter);
2316                 while ((tmp_unode = ulist_next(tmp, &tmp_uiter))) {
2317                         struct btrfs_qgroup_list *glist;
2318
2319                         qg = unode_aux_to_qgroup(tmp_unode);
2320                         if (update_old)
2321                                 btrfs_qgroup_update_old_refcnt(qg, seq, 1);
2322                         else
2323                                 btrfs_qgroup_update_new_refcnt(qg, seq, 1);
2324                         list_for_each_entry(glist, &qg->groups, next_group) {
2325                                 ret = ulist_add(qgroups, glist->group->qgroupid,
2326                                                 qgroup_to_aux(glist->group),
2327                                                 GFP_ATOMIC);
2328                                 if (ret < 0)
2329                                         return ret;
2330                                 ret = ulist_add(tmp, glist->group->qgroupid,
2331                                                 qgroup_to_aux(glist->group),
2332                                                 GFP_ATOMIC);
2333                                 if (ret < 0)
2334                                         return ret;
2335                         }
2336                 }
2337         }
2338         return 0;
2339 }
2340
2341 /*
2342  * Update qgroup rfer/excl counters.
2343  * Rfer update is easy, codes can explain themselves.
2344  *
2345  * Excl update is tricky, the update is split into 2 parts.
2346  * Part 1: Possible exclusive <-> sharing detect:
2347  *      |       A       |       !A      |
2348  *  -------------------------------------
2349  *  B   |       *       |       -       |
2350  *  -------------------------------------
2351  *  !B  |       +       |       **      |
2352  *  -------------------------------------
2353  *
2354  * Conditions:
2355  * A:   cur_old_roots < nr_old_roots    (not exclusive before)
2356  * !A:  cur_old_roots == nr_old_roots   (possible exclusive before)
2357  * B:   cur_new_roots < nr_new_roots    (not exclusive now)
2358  * !B:  cur_new_roots == nr_new_roots   (possible exclusive now)
2359  *
2360  * Results:
2361  * +: Possible sharing -> exclusive     -: Possible exclusive -> sharing
2362  * *: Definitely not changed.           **: Possible unchanged.
2363  *
2364  * For !A and !B condition, the exception is cur_old/new_roots == 0 case.
2365  *
2366  * To make the logic clear, we first use condition A and B to split
2367  * combination into 4 results.
2368  *
2369  * Then, for result "+" and "-", check old/new_roots == 0 case, as in them
2370  * only on variant maybe 0.
2371  *
2372  * Lastly, check result **, since there are 2 variants maybe 0, split them
2373  * again(2x2).
2374  * But this time we don't need to consider other things, the codes and logic
2375  * is easy to understand now.
2376  */
2377 static int qgroup_update_counters(struct btrfs_fs_info *fs_info,
2378                                   struct ulist *qgroups,
2379                                   u64 nr_old_roots,
2380                                   u64 nr_new_roots,
2381                                   u64 num_bytes, u64 seq)
2382 {
2383         struct ulist_node *unode;
2384         struct ulist_iterator uiter;
2385         struct btrfs_qgroup *qg;
2386         u64 cur_new_count, cur_old_count;
2387
2388         ULIST_ITER_INIT(&uiter);
2389         while ((unode = ulist_next(qgroups, &uiter))) {
2390                 bool dirty = false;
2391
2392                 qg = unode_aux_to_qgroup(unode);
2393                 cur_old_count = btrfs_qgroup_get_old_refcnt(qg, seq);
2394                 cur_new_count = btrfs_qgroup_get_new_refcnt(qg, seq);
2395
2396                 trace_qgroup_update_counters(fs_info, qg, cur_old_count,
2397                                              cur_new_count);
2398
2399                 /* Rfer update part */
2400                 if (cur_old_count == 0 && cur_new_count > 0) {
2401                         qg->rfer += num_bytes;
2402                         qg->rfer_cmpr += num_bytes;
2403                         dirty = true;
2404                 }
2405                 if (cur_old_count > 0 && cur_new_count == 0) {
2406                         qg->rfer -= num_bytes;
2407                         qg->rfer_cmpr -= num_bytes;
2408                         dirty = true;
2409                 }
2410
2411                 /* Excl update part */
2412                 /* Exclusive/none -> shared case */
2413                 if (cur_old_count == nr_old_roots &&
2414                     cur_new_count < nr_new_roots) {
2415                         /* Exclusive -> shared */
2416                         if (cur_old_count != 0) {
2417                                 qg->excl -= num_bytes;
2418                                 qg->excl_cmpr -= num_bytes;
2419                                 dirty = true;
2420                         }
2421                 }
2422
2423                 /* Shared -> exclusive/none case */
2424                 if (cur_old_count < nr_old_roots &&
2425                     cur_new_count == nr_new_roots) {
2426                         /* Shared->exclusive */
2427                         if (cur_new_count != 0) {
2428                                 qg->excl += num_bytes;
2429                                 qg->excl_cmpr += num_bytes;
2430                                 dirty = true;
2431                         }
2432                 }
2433
2434                 /* Exclusive/none -> exclusive/none case */
2435                 if (cur_old_count == nr_old_roots &&
2436                     cur_new_count == nr_new_roots) {
2437                         if (cur_old_count == 0) {
2438                                 /* None -> exclusive/none */
2439
2440                                 if (cur_new_count != 0) {
2441                                         /* None -> exclusive */
2442                                         qg->excl += num_bytes;
2443                                         qg->excl_cmpr += num_bytes;
2444                                         dirty = true;
2445                                 }
2446                                 /* None -> none, nothing changed */
2447                         } else {
2448                                 /* Exclusive -> exclusive/none */
2449
2450                                 if (cur_new_count == 0) {
2451                                         /* Exclusive -> none */
2452                                         qg->excl -= num_bytes;
2453                                         qg->excl_cmpr -= num_bytes;
2454                                         dirty = true;
2455                                 }
2456                                 /* Exclusive -> exclusive, nothing changed */
2457                         }
2458                 }
2459
2460                 if (dirty)
2461                         qgroup_dirty(fs_info, qg);
2462         }
2463         return 0;
2464 }
2465
2466 /*
2467  * Check if the @roots potentially is a list of fs tree roots
2468  *
2469  * Return 0 for definitely not a fs/subvol tree roots ulist
2470  * Return 1 for possible fs/subvol tree roots in the list (considering an empty
2471  *          one as well)
2472  */
2473 static int maybe_fs_roots(struct ulist *roots)
2474 {
2475         struct ulist_node *unode;
2476         struct ulist_iterator uiter;
2477
2478         /* Empty one, still possible for fs roots */
2479         if (!roots || roots->nnodes == 0)
2480                 return 1;
2481
2482         ULIST_ITER_INIT(&uiter);
2483         unode = ulist_next(roots, &uiter);
2484         if (!unode)
2485                 return 1;
2486
2487         /*
2488          * If it contains fs tree roots, then it must belong to fs/subvol
2489          * trees.
2490          * If it contains a non-fs tree, it won't be shared with fs/subvol trees.
2491          */
2492         return is_fstree(unode->val);
2493 }
2494
2495 int btrfs_qgroup_account_extent(struct btrfs_trans_handle *trans, u64 bytenr,
2496                                 u64 num_bytes, struct ulist *old_roots,
2497                                 struct ulist *new_roots)
2498 {
2499         struct btrfs_fs_info *fs_info = trans->fs_info;
2500         struct ulist *qgroups = NULL;
2501         struct ulist *tmp = NULL;
2502         u64 seq;
2503         u64 nr_new_roots = 0;
2504         u64 nr_old_roots = 0;
2505         int ret = 0;
2506
2507         /*
2508          * If quotas get disabled meanwhile, the resouces need to be freed and
2509          * we can't just exit here.
2510          */
2511         if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags))
2512                 goto out_free;
2513
2514         if (new_roots) {
2515                 if (!maybe_fs_roots(new_roots))
2516                         goto out_free;
2517                 nr_new_roots = new_roots->nnodes;
2518         }
2519         if (old_roots) {
2520                 if (!maybe_fs_roots(old_roots))
2521                         goto out_free;
2522                 nr_old_roots = old_roots->nnodes;
2523         }
2524
2525         /* Quick exit, either not fs tree roots, or won't affect any qgroup */
2526         if (nr_old_roots == 0 && nr_new_roots == 0)
2527                 goto out_free;
2528
2529         BUG_ON(!fs_info->quota_root);
2530
2531         trace_btrfs_qgroup_account_extent(fs_info, trans->transid, bytenr,
2532                                         num_bytes, nr_old_roots, nr_new_roots);
2533
2534         qgroups = ulist_alloc(GFP_NOFS);
2535         if (!qgroups) {
2536                 ret = -ENOMEM;
2537                 goto out_free;
2538         }
2539         tmp = ulist_alloc(GFP_NOFS);
2540         if (!tmp) {
2541                 ret = -ENOMEM;
2542                 goto out_free;
2543         }
2544
2545         mutex_lock(&fs_info->qgroup_rescan_lock);
2546         if (fs_info->qgroup_flags & BTRFS_QGROUP_STATUS_FLAG_RESCAN) {
2547                 if (fs_info->qgroup_rescan_progress.objectid <= bytenr) {
2548                         mutex_unlock(&fs_info->qgroup_rescan_lock);
2549                         ret = 0;
2550                         goto out_free;
2551                 }
2552         }
2553         mutex_unlock(&fs_info->qgroup_rescan_lock);
2554
2555         spin_lock(&fs_info->qgroup_lock);
2556         seq = fs_info->qgroup_seq;
2557
2558         /* Update old refcnts using old_roots */
2559         ret = qgroup_update_refcnt(fs_info, old_roots, tmp, qgroups, seq,
2560                                    UPDATE_OLD);
2561         if (ret < 0)
2562                 goto out;
2563
2564         /* Update new refcnts using new_roots */
2565         ret = qgroup_update_refcnt(fs_info, new_roots, tmp, qgroups, seq,
2566                                    UPDATE_NEW);
2567         if (ret < 0)
2568                 goto out;
2569
2570         qgroup_update_counters(fs_info, qgroups, nr_old_roots, nr_new_roots,
2571                                num_bytes, seq);
2572
2573         /*
2574          * Bump qgroup_seq to avoid seq overlap
2575          */
2576         fs_info->qgroup_seq += max(nr_old_roots, nr_new_roots) + 1;
2577 out:
2578         spin_unlock(&fs_info->qgroup_lock);
2579 out_free:
2580         ulist_free(tmp);
2581         ulist_free(qgroups);
2582         ulist_free(old_roots);
2583         ulist_free(new_roots);
2584         return ret;
2585 }
2586
2587 int btrfs_qgroup_account_extents(struct btrfs_trans_handle *trans)
2588 {
2589         struct btrfs_fs_info *fs_info = trans->fs_info;
2590         struct btrfs_qgroup_extent_record *record;
2591         struct btrfs_delayed_ref_root *delayed_refs;
2592         struct ulist *new_roots = NULL;
2593         struct rb_node *node;
2594         u64 num_dirty_extents = 0;
2595         u64 qgroup_to_skip;
2596         int ret = 0;
2597
2598         delayed_refs = &trans->transaction->delayed_refs;
2599         qgroup_to_skip = delayed_refs->qgroup_to_skip;
2600         while ((node = rb_first(&delayed_refs->dirty_extent_root))) {
2601                 record = rb_entry(node, struct btrfs_qgroup_extent_record,
2602                                   node);
2603
2604                 num_dirty_extents++;
2605                 trace_btrfs_qgroup_account_extents(fs_info, record);
2606
2607                 if (!ret) {
2608                         /*
2609                          * Old roots should be searched when inserting qgroup
2610                          * extent record
2611                          */
2612                         if (WARN_ON(!record->old_roots)) {
2613                                 /* Search commit root to find old_roots */
2614                                 ret = btrfs_find_all_roots(NULL, fs_info,
2615                                                 record->bytenr, 0,
2616                                                 &record->old_roots, false);
2617                                 if (ret < 0)
2618                                         goto cleanup;
2619                         }
2620
2621                         /* Free the reserved data space */
2622                         btrfs_qgroup_free_refroot(fs_info,
2623                                         record->data_rsv_refroot,
2624                                         record->data_rsv,
2625                                         BTRFS_QGROUP_RSV_DATA);
2626                         /*
2627                          * Use SEQ_LAST as time_seq to do special search, which
2628                          * doesn't lock tree or delayed_refs and search current
2629                          * root. It's safe inside commit_transaction().
2630                          */
2631                         ret = btrfs_find_all_roots(trans, fs_info,
2632                                 record->bytenr, SEQ_LAST, &new_roots, false);
2633                         if (ret < 0)
2634                                 goto cleanup;
2635                         if (qgroup_to_skip) {
2636                                 ulist_del(new_roots, qgroup_to_skip, 0);
2637                                 ulist_del(record->old_roots, qgroup_to_skip,
2638                                           0);
2639                         }
2640                         ret = btrfs_qgroup_account_extent(trans, record->bytenr,
2641                                                           record->num_bytes,
2642                                                           record->old_roots,
2643                                                           new_roots);
2644                         record->old_roots = NULL;
2645                         new_roots = NULL;
2646                 }
2647 cleanup:
2648                 ulist_free(record->old_roots);
2649                 ulist_free(new_roots);
2650                 new_roots = NULL;
2651                 rb_erase(node, &delayed_refs->dirty_extent_root);
2652                 kfree(record);
2653
2654         }
2655         trace_qgroup_num_dirty_extents(fs_info, trans->transid,
2656                                        num_dirty_extents);
2657         return ret;
2658 }
2659
2660 /*
2661  * called from commit_transaction. Writes all changed qgroups to disk.
2662  */
2663 int btrfs_run_qgroups(struct btrfs_trans_handle *trans)
2664 {
2665         struct btrfs_fs_info *fs_info = trans->fs_info;
2666         int ret = 0;
2667
2668         if (!fs_info->quota_root)
2669                 return ret;
2670
2671         spin_lock(&fs_info->qgroup_lock);
2672         while (!list_empty(&fs_info->dirty_qgroups)) {
2673                 struct btrfs_qgroup *qgroup;
2674                 qgroup = list_first_entry(&fs_info->dirty_qgroups,
2675                                           struct btrfs_qgroup, dirty);
2676                 list_del_init(&qgroup->dirty);
2677                 spin_unlock(&fs_info->qgroup_lock);
2678                 ret = update_qgroup_info_item(trans, qgroup);
2679                 if (ret)
2680                         fs_info->qgroup_flags |=
2681                                         BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
2682                 ret = update_qgroup_limit_item(trans, qgroup);
2683                 if (ret)
2684                         fs_info->qgroup_flags |=
2685                                         BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
2686                 spin_lock(&fs_info->qgroup_lock);
2687         }
2688         if (test_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags))
2689                 fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_ON;
2690         else
2691                 fs_info->qgroup_flags &= ~BTRFS_QGROUP_STATUS_FLAG_ON;
2692         spin_unlock(&fs_info->qgroup_lock);
2693
2694         ret = update_qgroup_status_item(trans);
2695         if (ret)
2696                 fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
2697
2698         return ret;
2699 }
2700
2701 /*
2702  * Copy the accounting information between qgroups. This is necessary
2703  * when a snapshot or a subvolume is created. Throwing an error will
2704  * cause a transaction abort so we take extra care here to only error
2705  * when a readonly fs is a reasonable outcome.
2706  */
2707 int btrfs_qgroup_inherit(struct btrfs_trans_handle *trans, u64 srcid,
2708                          u64 objectid, struct btrfs_qgroup_inherit *inherit)
2709 {
2710         int ret = 0;
2711         int i;
2712         u64 *i_qgroups;
2713         bool committing = false;
2714         struct btrfs_fs_info *fs_info = trans->fs_info;
2715         struct btrfs_root *quota_root;
2716         struct btrfs_qgroup *srcgroup;
2717         struct btrfs_qgroup *dstgroup;
2718         bool need_rescan = false;
2719         u32 level_size = 0;
2720         u64 nums;
2721
2722         /*
2723          * There are only two callers of this function.
2724          *
2725          * One in create_subvol() in the ioctl context, which needs to hold
2726          * the qgroup_ioctl_lock.
2727          *
2728          * The other one in create_pending_snapshot() where no other qgroup
2729          * code can modify the fs as they all need to either start a new trans
2730          * or hold a trans handler, thus we don't need to hold
2731          * qgroup_ioctl_lock.
2732          * This would avoid long and complex lock chain and make lockdep happy.
2733          */
2734         spin_lock(&fs_info->trans_lock);
2735         if (trans->transaction->state == TRANS_STATE_COMMIT_DOING)
2736                 committing = true;
2737         spin_unlock(&fs_info->trans_lock);
2738
2739         if (!committing)
2740                 mutex_lock(&fs_info->qgroup_ioctl_lock);
2741         if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags))
2742                 goto out;
2743
2744         quota_root = fs_info->quota_root;
2745         if (!quota_root) {
2746                 ret = -EINVAL;
2747                 goto out;
2748         }
2749
2750         if (inherit) {
2751                 i_qgroups = (u64 *)(inherit + 1);
2752                 nums = inherit->num_qgroups + 2 * inherit->num_ref_copies +
2753                        2 * inherit->num_excl_copies;
2754                 for (i = 0; i < nums; ++i) {
2755                         srcgroup = find_qgroup_rb(fs_info, *i_qgroups);
2756
2757                         /*
2758                          * Zero out invalid groups so we can ignore
2759                          * them later.
2760                          */
2761                         if (!srcgroup ||
2762                             ((srcgroup->qgroupid >> 48) <= (objectid >> 48)))
2763                                 *i_qgroups = 0ULL;
2764
2765                         ++i_qgroups;
2766                 }
2767         }
2768
2769         /*
2770          * create a tracking group for the subvol itself
2771          */
2772         ret = add_qgroup_item(trans, quota_root, objectid);
2773         if (ret)
2774                 goto out;
2775
2776         /*
2777          * add qgroup to all inherited groups
2778          */
2779         if (inherit) {
2780                 i_qgroups = (u64 *)(inherit + 1);
2781                 for (i = 0; i < inherit->num_qgroups; ++i, ++i_qgroups) {
2782                         if (*i_qgroups == 0)
2783                                 continue;
2784                         ret = add_qgroup_relation_item(trans, objectid,
2785                                                        *i_qgroups);
2786                         if (ret && ret != -EEXIST)
2787                                 goto out;
2788                         ret = add_qgroup_relation_item(trans, *i_qgroups,
2789                                                        objectid);
2790                         if (ret && ret != -EEXIST)
2791                                 goto out;
2792                 }
2793                 ret = 0;
2794         }
2795
2796
2797         spin_lock(&fs_info->qgroup_lock);
2798
2799         dstgroup = add_qgroup_rb(fs_info, objectid);
2800         if (IS_ERR(dstgroup)) {
2801                 ret = PTR_ERR(dstgroup);
2802                 goto unlock;
2803         }
2804
2805         if (inherit && inherit->flags & BTRFS_QGROUP_INHERIT_SET_LIMITS) {
2806                 dstgroup->lim_flags = inherit->lim.flags;
2807                 dstgroup->max_rfer = inherit->lim.max_rfer;
2808                 dstgroup->max_excl = inherit->lim.max_excl;
2809                 dstgroup->rsv_rfer = inherit->lim.rsv_rfer;
2810                 dstgroup->rsv_excl = inherit->lim.rsv_excl;
2811
2812                 ret = update_qgroup_limit_item(trans, dstgroup);
2813                 if (ret) {
2814                         fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
2815                         btrfs_info(fs_info,
2816                                    "unable to update quota limit for %llu",
2817                                    dstgroup->qgroupid);
2818                         goto unlock;
2819                 }
2820         }
2821
2822         if (srcid) {
2823                 srcgroup = find_qgroup_rb(fs_info, srcid);
2824                 if (!srcgroup)
2825                         goto unlock;
2826
2827                 /*
2828                  * We call inherit after we clone the root in order to make sure
2829                  * our counts don't go crazy, so at this point the only
2830                  * difference between the two roots should be the root node.
2831                  */
2832                 level_size = fs_info->nodesize;
2833                 dstgroup->rfer = srcgroup->rfer;
2834                 dstgroup->rfer_cmpr = srcgroup->rfer_cmpr;
2835                 dstgroup->excl = level_size;
2836                 dstgroup->excl_cmpr = level_size;
2837                 srcgroup->excl = level_size;
2838                 srcgroup->excl_cmpr = level_size;
2839
2840                 /* inherit the limit info */
2841                 dstgroup->lim_flags = srcgroup->lim_flags;
2842                 dstgroup->max_rfer = srcgroup->max_rfer;
2843                 dstgroup->max_excl = srcgroup->max_excl;
2844                 dstgroup->rsv_rfer = srcgroup->rsv_rfer;
2845                 dstgroup->rsv_excl = srcgroup->rsv_excl;
2846
2847                 qgroup_dirty(fs_info, dstgroup);
2848                 qgroup_dirty(fs_info, srcgroup);
2849         }
2850
2851         if (!inherit)
2852                 goto unlock;
2853
2854         i_qgroups = (u64 *)(inherit + 1);
2855         for (i = 0; i < inherit->num_qgroups; ++i) {
2856                 if (*i_qgroups) {
2857                         ret = add_relation_rb(fs_info, objectid, *i_qgroups);
2858                         if (ret)
2859                                 goto unlock;
2860                 }
2861                 ++i_qgroups;
2862
2863                 /*
2864                  * If we're doing a snapshot, and adding the snapshot to a new
2865                  * qgroup, the numbers are guaranteed to be incorrect.
2866                  */
2867                 if (srcid)
2868                         need_rescan = true;
2869         }
2870
2871         for (i = 0; i <  inherit->num_ref_copies; ++i, i_qgroups += 2) {
2872                 struct btrfs_qgroup *src;
2873                 struct btrfs_qgroup *dst;
2874
2875                 if (!i_qgroups[0] || !i_qgroups[1])
2876                         continue;
2877
2878                 src = find_qgroup_rb(fs_info, i_qgroups[0]);
2879                 dst = find_qgroup_rb(fs_info, i_qgroups[1]);
2880
2881                 if (!src || !dst) {
2882                         ret = -EINVAL;
2883                         goto unlock;
2884                 }
2885
2886                 dst->rfer = src->rfer - level_size;
2887                 dst->rfer_cmpr = src->rfer_cmpr - level_size;
2888
2889                 /* Manually tweaking numbers certainly needs a rescan */
2890                 need_rescan = true;
2891         }
2892         for (i = 0; i <  inherit->num_excl_copies; ++i, i_qgroups += 2) {
2893                 struct btrfs_qgroup *src;
2894                 struct btrfs_qgroup *dst;
2895
2896                 if (!i_qgroups[0] || !i_qgroups[1])
2897                         continue;
2898
2899                 src = find_qgroup_rb(fs_info, i_qgroups[0]);
2900                 dst = find_qgroup_rb(fs_info, i_qgroups[1]);
2901
2902                 if (!src || !dst) {
2903                         ret = -EINVAL;
2904                         goto unlock;
2905                 }
2906
2907                 dst->excl = src->excl + level_size;
2908                 dst->excl_cmpr = src->excl_cmpr + level_size;
2909                 need_rescan = true;
2910         }
2911
2912 unlock:
2913         spin_unlock(&fs_info->qgroup_lock);
2914         if (!ret)
2915                 ret = btrfs_sysfs_add_one_qgroup(fs_info, dstgroup);
2916 out:
2917         if (!committing)
2918                 mutex_unlock(&fs_info->qgroup_ioctl_lock);
2919         if (need_rescan)
2920                 fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
2921         return ret;
2922 }
2923
2924 static bool qgroup_check_limits(const struct btrfs_qgroup *qg, u64 num_bytes)
2925 {
2926         if ((qg->lim_flags & BTRFS_QGROUP_LIMIT_MAX_RFER) &&
2927             qgroup_rsv_total(qg) + (s64)qg->rfer + num_bytes > qg->max_rfer)
2928                 return false;
2929
2930         if ((qg->lim_flags & BTRFS_QGROUP_LIMIT_MAX_EXCL) &&
2931             qgroup_rsv_total(qg) + (s64)qg->excl + num_bytes > qg->max_excl)
2932                 return false;
2933
2934         return true;
2935 }
2936
2937 static int qgroup_reserve(struct btrfs_root *root, u64 num_bytes, bool enforce,
2938                           enum btrfs_qgroup_rsv_type type)
2939 {
2940         struct btrfs_qgroup *qgroup;
2941         struct btrfs_fs_info *fs_info = root->fs_info;
2942         u64 ref_root = root->root_key.objectid;
2943         int ret = 0;
2944         struct ulist_node *unode;
2945         struct ulist_iterator uiter;
2946
2947         if (!is_fstree(ref_root))
2948                 return 0;
2949
2950         if (num_bytes == 0)
2951                 return 0;
2952
2953         if (test_bit(BTRFS_FS_QUOTA_OVERRIDE, &fs_info->flags) &&
2954             capable(CAP_SYS_RESOURCE))
2955                 enforce = false;
2956
2957         spin_lock(&fs_info->qgroup_lock);
2958         if (!fs_info->quota_root)
2959                 goto out;
2960
2961         qgroup = find_qgroup_rb(fs_info, ref_root);
2962         if (!qgroup)
2963                 goto out;
2964
2965         /*
2966          * in a first step, we check all affected qgroups if any limits would
2967          * be exceeded
2968          */
2969         ulist_reinit(fs_info->qgroup_ulist);
2970         ret = ulist_add(fs_info->qgroup_ulist, qgroup->qgroupid,
2971                         qgroup_to_aux(qgroup), GFP_ATOMIC);
2972         if (ret < 0)
2973                 goto out;
2974         ULIST_ITER_INIT(&uiter);
2975         while ((unode = ulist_next(fs_info->qgroup_ulist, &uiter))) {
2976                 struct btrfs_qgroup *qg;
2977                 struct btrfs_qgroup_list *glist;
2978
2979                 qg = unode_aux_to_qgroup(unode);
2980
2981                 if (enforce && !qgroup_check_limits(qg, num_bytes)) {
2982                         ret = -EDQUOT;
2983                         goto out;
2984                 }
2985
2986                 list_for_each_entry(glist, &qg->groups, next_group) {
2987                         ret = ulist_add(fs_info->qgroup_ulist,
2988                                         glist->group->qgroupid,
2989                                         qgroup_to_aux(glist->group), GFP_ATOMIC);
2990                         if (ret < 0)
2991                                 goto out;
2992                 }
2993         }
2994         ret = 0;
2995         /*
2996          * no limits exceeded, now record the reservation into all qgroups
2997          */
2998         ULIST_ITER_INIT(&uiter);
2999         while ((unode = ulist_next(fs_info->qgroup_ulist, &uiter))) {
3000                 struct btrfs_qgroup *qg;
3001
3002                 qg = unode_aux_to_qgroup(unode);
3003
3004                 qgroup_rsv_add(fs_info, qg, num_bytes, type);
3005         }
3006
3007 out:
3008         spin_unlock(&fs_info->qgroup_lock);
3009         return ret;
3010 }
3011
3012 /*
3013  * Free @num_bytes of reserved space with @type for qgroup.  (Normally level 0
3014  * qgroup).
3015  *
3016  * Will handle all higher level qgroup too.
3017  *
3018  * NOTE: If @num_bytes is (u64)-1, this means to free all bytes of this qgroup.
3019  * This special case is only used for META_PERTRANS type.
3020  */
3021 void btrfs_qgroup_free_refroot(struct btrfs_fs_info *fs_info,
3022                                u64 ref_root, u64 num_bytes,
3023                                enum btrfs_qgroup_rsv_type type)
3024 {
3025         struct btrfs_qgroup *qgroup;
3026         struct ulist_node *unode;
3027         struct ulist_iterator uiter;
3028         int ret = 0;
3029
3030         if (!is_fstree(ref_root))
3031                 return;
3032
3033         if (num_bytes == 0)
3034                 return;
3035
3036         if (num_bytes == (u64)-1 && type != BTRFS_QGROUP_RSV_META_PERTRANS) {
3037                 WARN(1, "%s: Invalid type to free", __func__);
3038                 return;
3039         }
3040         spin_lock(&fs_info->qgroup_lock);
3041
3042         if (!fs_info->quota_root)
3043                 goto out;
3044
3045         qgroup = find_qgroup_rb(fs_info, ref_root);
3046         if (!qgroup)
3047                 goto out;
3048
3049         if (num_bytes == (u64)-1)
3050                 /*
3051                  * We're freeing all pertrans rsv, get reserved value from
3052                  * level 0 qgroup as real num_bytes to free.
3053                  */
3054                 num_bytes = qgroup->rsv.values[type];
3055
3056         ulist_reinit(fs_info->qgroup_ulist);
3057         ret = ulist_add(fs_info->qgroup_ulist, qgroup->qgroupid,
3058                         qgroup_to_aux(qgroup), GFP_ATOMIC);
3059         if (ret < 0)
3060                 goto out;
3061         ULIST_ITER_INIT(&uiter);
3062         while ((unode = ulist_next(fs_info->qgroup_ulist, &uiter))) {
3063                 struct btrfs_qgroup *qg;
3064                 struct btrfs_qgroup_list *glist;
3065
3066                 qg = unode_aux_to_qgroup(unode);
3067
3068                 qgroup_rsv_release(fs_info, qg, num_bytes, type);
3069
3070                 list_for_each_entry(glist, &qg->groups, next_group) {
3071                         ret = ulist_add(fs_info->qgroup_ulist,
3072                                         glist->group->qgroupid,
3073                                         qgroup_to_aux(glist->group), GFP_ATOMIC);
3074                         if (ret < 0)
3075                                 goto out;
3076                 }
3077         }
3078
3079 out:
3080         spin_unlock(&fs_info->qgroup_lock);
3081 }
3082
3083 /*
3084  * Check if the leaf is the last leaf. Which means all node pointers
3085  * are at their last position.
3086  */
3087 static bool is_last_leaf(struct btrfs_path *path)
3088 {
3089         int i;
3090
3091         for (i = 1; i < BTRFS_MAX_LEVEL && path->nodes[i]; i++) {
3092                 if (path->slots[i] != btrfs_header_nritems(path->nodes[i]) - 1)
3093                         return false;
3094         }
3095         return true;
3096 }
3097
3098 /*
3099  * returns < 0 on error, 0 when more leafs are to be scanned.
3100  * returns 1 when done.
3101  */
3102 static int qgroup_rescan_leaf(struct btrfs_trans_handle *trans,
3103                               struct btrfs_path *path)
3104 {
3105         struct btrfs_fs_info *fs_info = trans->fs_info;
3106         struct btrfs_key found;
3107         struct extent_buffer *scratch_leaf = NULL;
3108         struct ulist *roots = NULL;
3109         u64 num_bytes;
3110         bool done;
3111         int slot;
3112         int ret;
3113
3114         mutex_lock(&fs_info->qgroup_rescan_lock);
3115         ret = btrfs_search_slot_for_read(fs_info->extent_root,
3116                                          &fs_info->qgroup_rescan_progress,
3117                                          path, 1, 0);
3118
3119         btrfs_debug(fs_info,
3120                 "current progress key (%llu %u %llu), search_slot ret %d",
3121                 fs_info->qgroup_rescan_progress.objectid,
3122                 fs_info->qgroup_rescan_progress.type,
3123                 fs_info->qgroup_rescan_progress.offset, ret);
3124
3125         if (ret) {
3126                 /*
3127                  * The rescan is about to end, we will not be scanning any
3128                  * further blocks. We cannot unset the RESCAN flag here, because
3129                  * we want to commit the transaction if everything went well.
3130                  * To make the live accounting work in this phase, we set our
3131                  * scan progress pointer such that every real extent objectid
3132                  * will be smaller.
3133                  */
3134                 fs_info->qgroup_rescan_progress.objectid = (u64)-1;
3135                 btrfs_release_path(path);
3136                 mutex_unlock(&fs_info->qgroup_rescan_lock);
3137                 return ret;
3138         }
3139         done = is_last_leaf(path);
3140
3141         btrfs_item_key_to_cpu(path->nodes[0], &found,
3142                               btrfs_header_nritems(path->nodes[0]) - 1);
3143         fs_info->qgroup_rescan_progress.objectid = found.objectid + 1;
3144
3145         scratch_leaf = btrfs_clone_extent_buffer(path->nodes[0]);
3146         if (!scratch_leaf) {
3147                 ret = -ENOMEM;
3148                 mutex_unlock(&fs_info->qgroup_rescan_lock);
3149                 goto out;
3150         }
3151         slot = path->slots[0];
3152         btrfs_release_path(path);
3153         mutex_unlock(&fs_info->qgroup_rescan_lock);
3154
3155         for (; slot < btrfs_header_nritems(scratch_leaf); ++slot) {
3156                 btrfs_item_key_to_cpu(scratch_leaf, &found, slot);
3157                 if (found.type != BTRFS_EXTENT_ITEM_KEY &&
3158                     found.type != BTRFS_METADATA_ITEM_KEY)
3159                         continue;
3160                 if (found.type == BTRFS_METADATA_ITEM_KEY)
3161                         num_bytes = fs_info->nodesize;
3162                 else
3163                         num_bytes = found.offset;
3164
3165                 ret = btrfs_find_all_roots(NULL, fs_info, found.objectid, 0,
3166                                            &roots, false);
3167                 if (ret < 0)
3168                         goto out;
3169                 /* For rescan, just pass old_roots as NULL */
3170                 ret = btrfs_qgroup_account_extent(trans, found.objectid,
3171                                                   num_bytes, NULL, roots);
3172                 if (ret < 0)
3173                         goto out;
3174         }
3175 out:
3176         if (scratch_leaf)
3177                 free_extent_buffer(scratch_leaf);
3178
3179         if (done && !ret) {
3180                 ret = 1;
3181                 fs_info->qgroup_rescan_progress.objectid = (u64)-1;
3182         }
3183         return ret;
3184 }
3185
3186 static void btrfs_qgroup_rescan_worker(struct btrfs_work *work)
3187 {
3188         struct btrfs_fs_info *fs_info = container_of(work, struct btrfs_fs_info,
3189                                                      qgroup_rescan_work);
3190         struct btrfs_path *path;
3191         struct btrfs_trans_handle *trans = NULL;
3192         int err = -ENOMEM;
3193         int ret = 0;
3194
3195         path = btrfs_alloc_path();
3196         if (!path)
3197                 goto out;
3198         /*
3199          * Rescan should only search for commit root, and any later difference
3200          * should be recorded by qgroup
3201          */
3202         path->search_commit_root = 1;
3203         path->skip_locking = 1;
3204
3205         err = 0;
3206         while (!err && !btrfs_fs_closing(fs_info)) {
3207                 trans = btrfs_start_transaction(fs_info->fs_root, 0);
3208                 if (IS_ERR(trans)) {
3209                         err = PTR_ERR(trans);
3210                         break;
3211                 }
3212                 if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags)) {
3213                         err = -EINTR;
3214                 } else {
3215                         err = qgroup_rescan_leaf(trans, path);
3216                 }
3217                 if (err > 0)
3218                         btrfs_commit_transaction(trans);
3219                 else
3220                         btrfs_end_transaction(trans);
3221         }
3222
3223 out:
3224         btrfs_free_path(path);
3225
3226         mutex_lock(&fs_info->qgroup_rescan_lock);
3227         if (err > 0 &&
3228             fs_info->qgroup_flags & BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT) {
3229                 fs_info->qgroup_flags &= ~BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
3230         } else if (err < 0) {
3231                 fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
3232         }
3233         mutex_unlock(&fs_info->qgroup_rescan_lock);
3234
3235         /*
3236          * only update status, since the previous part has already updated the
3237          * qgroup info.
3238          */
3239         trans = btrfs_start_transaction(fs_info->quota_root, 1);
3240         if (IS_ERR(trans)) {
3241                 err = PTR_ERR(trans);
3242                 trans = NULL;
3243                 btrfs_err(fs_info,
3244                           "fail to start transaction for status update: %d",
3245                           err);
3246         }
3247
3248         mutex_lock(&fs_info->qgroup_rescan_lock);
3249         if (!btrfs_fs_closing(fs_info))
3250                 fs_info->qgroup_flags &= ~BTRFS_QGROUP_STATUS_FLAG_RESCAN;
3251         if (trans) {
3252                 ret = update_qgroup_status_item(trans);
3253                 if (ret < 0) {
3254                         err = ret;
3255                         btrfs_err(fs_info, "fail to update qgroup status: %d",
3256                                   err);
3257                 }
3258         }
3259         fs_info->qgroup_rescan_running = false;
3260         complete_all(&fs_info->qgroup_rescan_completion);
3261         mutex_unlock(&fs_info->qgroup_rescan_lock);
3262
3263         if (!trans)
3264                 return;
3265
3266         btrfs_end_transaction(trans);
3267
3268         if (btrfs_fs_closing(fs_info)) {
3269                 btrfs_info(fs_info, "qgroup scan paused");
3270         } else if (err >= 0) {
3271                 btrfs_info(fs_info, "qgroup scan completed%s",
3272                         err > 0 ? " (inconsistency flag cleared)" : "");
3273         } else {
3274                 btrfs_err(fs_info, "qgroup scan failed with %d", err);
3275         }
3276 }
3277
3278 /*
3279  * Checks that (a) no rescan is running and (b) quota is enabled. Allocates all
3280  * memory required for the rescan context.
3281  */
3282 static int
3283 qgroup_rescan_init(struct btrfs_fs_info *fs_info, u64 progress_objectid,
3284                    int init_flags)
3285 {
3286         int ret = 0;
3287
3288         if (!init_flags) {
3289                 /* we're resuming qgroup rescan at mount time */
3290                 if (!(fs_info->qgroup_flags &
3291                       BTRFS_QGROUP_STATUS_FLAG_RESCAN)) {
3292                         btrfs_warn(fs_info,
3293                         "qgroup rescan init failed, qgroup rescan is not queued");
3294                         ret = -EINVAL;
3295                 } else if (!(fs_info->qgroup_flags &
3296                              BTRFS_QGROUP_STATUS_FLAG_ON)) {
3297                         btrfs_warn(fs_info,
3298                         "qgroup rescan init failed, qgroup is not enabled");
3299                         ret = -EINVAL;
3300                 }
3301
3302                 if (ret)
3303                         return ret;
3304         }
3305
3306         mutex_lock(&fs_info->qgroup_rescan_lock);
3307
3308         if (init_flags) {
3309                 if (fs_info->qgroup_flags & BTRFS_QGROUP_STATUS_FLAG_RESCAN) {
3310                         btrfs_warn(fs_info,
3311                                    "qgroup rescan is already in progress");
3312                         ret = -EINPROGRESS;
3313                 } else if (!(fs_info->qgroup_flags &
3314                              BTRFS_QGROUP_STATUS_FLAG_ON)) {
3315                         btrfs_warn(fs_info,
3316                         "qgroup rescan init failed, qgroup is not enabled");
3317                         ret = -EINVAL;
3318                 }
3319
3320                 if (ret) {
3321                         mutex_unlock(&fs_info->qgroup_rescan_lock);
3322                         return ret;
3323                 }
3324                 fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_RESCAN;
3325         }
3326
3327         memset(&fs_info->qgroup_rescan_progress, 0,
3328                 sizeof(fs_info->qgroup_rescan_progress));
3329         fs_info->qgroup_rescan_progress.objectid = progress_objectid;
3330         init_completion(&fs_info->qgroup_rescan_completion);
3331         mutex_unlock(&fs_info->qgroup_rescan_lock);
3332
3333         btrfs_init_work(&fs_info->qgroup_rescan_work,
3334                         btrfs_qgroup_rescan_worker, NULL, NULL);
3335         return 0;
3336 }
3337
3338 static void
3339 qgroup_rescan_zero_tracking(struct btrfs_fs_info *fs_info)
3340 {
3341         struct rb_node *n;
3342         struct btrfs_qgroup *qgroup;
3343
3344         spin_lock(&fs_info->qgroup_lock);
3345         /* clear all current qgroup tracking information */
3346         for (n = rb_first(&fs_info->qgroup_tree); n; n = rb_next(n)) {
3347                 qgroup = rb_entry(n, struct btrfs_qgroup, node);
3348                 qgroup->rfer = 0;
3349                 qgroup->rfer_cmpr = 0;
3350                 qgroup->excl = 0;
3351                 qgroup->excl_cmpr = 0;
3352                 qgroup_dirty(fs_info, qgroup);
3353         }
3354         spin_unlock(&fs_info->qgroup_lock);
3355 }
3356
3357 int
3358 btrfs_qgroup_rescan(struct btrfs_fs_info *fs_info)
3359 {
3360         int ret = 0;
3361         struct btrfs_trans_handle *trans;
3362
3363         ret = qgroup_rescan_init(fs_info, 0, 1);
3364         if (ret)
3365                 return ret;
3366
3367         /*
3368          * We have set the rescan_progress to 0, which means no more
3369          * delayed refs will be accounted by btrfs_qgroup_account_ref.
3370          * However, btrfs_qgroup_account_ref may be right after its call
3371          * to btrfs_find_all_roots, in which case it would still do the
3372          * accounting.
3373          * To solve this, we're committing the transaction, which will
3374          * ensure we run all delayed refs and only after that, we are
3375          * going to clear all tracking information for a clean start.
3376          */
3377
3378         trans = btrfs_join_transaction(fs_info->fs_root);
3379         if (IS_ERR(trans)) {
3380                 fs_info->qgroup_flags &= ~BTRFS_QGROUP_STATUS_FLAG_RESCAN;
3381                 return PTR_ERR(trans);
3382         }
3383         ret = btrfs_commit_transaction(trans);
3384         if (ret) {
3385                 fs_info->qgroup_flags &= ~BTRFS_QGROUP_STATUS_FLAG_RESCAN;
3386                 return ret;
3387         }
3388
3389         qgroup_rescan_zero_tracking(fs_info);
3390
3391         mutex_lock(&fs_info->qgroup_rescan_lock);
3392         fs_info->qgroup_rescan_running = true;
3393         btrfs_queue_work(fs_info->qgroup_rescan_workers,
3394                          &fs_info->qgroup_rescan_work);
3395         mutex_unlock(&fs_info->qgroup_rescan_lock);
3396
3397         return 0;
3398 }
3399
3400 int btrfs_qgroup_wait_for_completion(struct btrfs_fs_info *fs_info,
3401                                      bool interruptible)
3402 {
3403         int running;
3404         int ret = 0;
3405
3406         mutex_lock(&fs_info->qgroup_rescan_lock);
3407         running = fs_info->qgroup_rescan_running;
3408         mutex_unlock(&fs_info->qgroup_rescan_lock);
3409
3410         if (!running)
3411                 return 0;
3412
3413         if (interruptible)
3414                 ret = wait_for_completion_interruptible(
3415                                         &fs_info->qgroup_rescan_completion);
3416         else
3417                 wait_for_completion(&fs_info->qgroup_rescan_completion);
3418
3419         return ret;
3420 }
3421
3422 /*
3423  * this is only called from open_ctree where we're still single threaded, thus
3424  * locking is omitted here.
3425  */
3426 void
3427 btrfs_qgroup_rescan_resume(struct btrfs_fs_info *fs_info)
3428 {
3429         if (fs_info->qgroup_flags & BTRFS_QGROUP_STATUS_FLAG_RESCAN) {
3430                 mutex_lock(&fs_info->qgroup_rescan_lock);
3431                 fs_info->qgroup_rescan_running = true;
3432                 btrfs_queue_work(fs_info->qgroup_rescan_workers,
3433                                  &fs_info->qgroup_rescan_work);
3434                 mutex_unlock(&fs_info->qgroup_rescan_lock);
3435         }
3436 }
3437
3438 #define rbtree_iterate_from_safe(node, next, start)                             \
3439        for (node = start; node && ({ next = rb_next(node); 1;}); node = next)
3440
3441 static int qgroup_unreserve_range(struct btrfs_inode *inode,
3442                                   struct extent_changeset *reserved, u64 start,
3443                                   u64 len)
3444 {
3445         struct rb_node *node;
3446         struct rb_node *next;
3447         struct ulist_node *entry;
3448         int ret = 0;
3449
3450         node = reserved->range_changed.root.rb_node;
3451         if (!node)
3452                 return 0;
3453         while (node) {
3454                 entry = rb_entry(node, struct ulist_node, rb_node);
3455                 if (entry->val < start)
3456                         node = node->rb_right;
3457                 else
3458                         node = node->rb_left;
3459         }
3460
3461         if (entry->val > start && rb_prev(&entry->rb_node))
3462                 entry = rb_entry(rb_prev(&entry->rb_node), struct ulist_node,
3463                                  rb_node);
3464
3465         rbtree_iterate_from_safe(node, next, &entry->rb_node) {
3466                 u64 entry_start;
3467                 u64 entry_end;
3468                 u64 entry_len;
3469                 int clear_ret;
3470
3471                 entry = rb_entry(node, struct ulist_node, rb_node);
3472                 entry_start = entry->val;
3473                 entry_end = entry->aux;
3474                 entry_len = entry_end - entry_start + 1;
3475
3476                 if (entry_start >= start + len)
3477                         break;
3478                 if (entry_start + entry_len <= start)
3479                         continue;
3480                 /*
3481                  * Now the entry is in [start, start + len), revert the
3482                  * EXTENT_QGROUP_RESERVED bit.
3483                  */
3484                 clear_ret = clear_extent_bits(&inode->io_tree, entry_start,
3485                                               entry_end, EXTENT_QGROUP_RESERVED);
3486                 if (!ret && clear_ret < 0)
3487                         ret = clear_ret;
3488
3489                 ulist_del(&reserved->range_changed, entry->val, entry->aux);
3490                 if (likely(reserved->bytes_changed >= entry_len)) {
3491                         reserved->bytes_changed -= entry_len;
3492                 } else {
3493                         WARN_ON(1);
3494                         reserved->bytes_changed = 0;
3495                 }
3496         }
3497
3498         return ret;
3499 }
3500
3501 /*
3502  * Try to free some space for qgroup.
3503  *
3504  * For qgroup, there are only 3 ways to free qgroup space:
3505  * - Flush nodatacow write
3506  *   Any nodatacow write will free its reserved data space at run_delalloc_range().
3507  *   In theory, we should only flush nodatacow inodes, but it's not yet
3508  *   possible, so we need to flush the whole root.
3509  *
3510  * - Wait for ordered extents
3511  *   When ordered extents are finished, their reserved metadata is finally
3512  *   converted to per_trans status, which can be freed by later commit
3513  *   transaction.
3514  *
3515  * - Commit transaction
3516  *   This would free the meta_per_trans space.
3517  *   In theory this shouldn't provide much space, but any more qgroup space
3518  *   is needed.
3519  */
3520 static int try_flush_qgroup(struct btrfs_root *root)
3521 {
3522         struct btrfs_trans_handle *trans;
3523         int ret;
3524         bool can_commit = true;
3525
3526         /*
3527          * We don't want to run flush again and again, so if there is a running
3528          * one, we won't try to start a new flush, but exit directly.
3529          */
3530         if (test_and_set_bit(BTRFS_ROOT_QGROUP_FLUSHING, &root->state)) {
3531                 wait_event(root->qgroup_flush_wait,
3532                         !test_bit(BTRFS_ROOT_QGROUP_FLUSHING, &root->state));
3533                 return 0;
3534         }
3535
3536         /*
3537          * If current process holds a transaction, we shouldn't flush, as we
3538          * assume all space reservation happens before a transaction handle is
3539          * held.
3540          *
3541          * But there are cases like btrfs_delayed_item_reserve_metadata() where
3542          * we try to reserve space with one transction handle already held.
3543          * In that case we can't commit transaction, but at least try to end it
3544          * and hope the started data writes can free some space.
3545          */
3546         if (current->journal_info &&
3547             current->journal_info != BTRFS_SEND_TRANS_STUB)
3548                 can_commit = false;
3549
3550         ret = btrfs_start_delalloc_snapshot(root);
3551         if (ret < 0)
3552                 goto out;
3553         btrfs_wait_ordered_extents(root, U64_MAX, 0, (u64)-1);
3554
3555         trans = btrfs_join_transaction(root);
3556         if (IS_ERR(trans)) {
3557                 ret = PTR_ERR(trans);
3558                 goto out;
3559         }
3560
3561         if (can_commit)
3562                 ret = btrfs_commit_transaction(trans);
3563         else
3564                 ret = btrfs_end_transaction(trans);
3565 out:
3566         clear_bit(BTRFS_ROOT_QGROUP_FLUSHING, &root->state);
3567         wake_up(&root->qgroup_flush_wait);
3568         return ret;
3569 }
3570
3571 static int qgroup_reserve_data(struct btrfs_inode *inode,
3572                         struct extent_changeset **reserved_ret, u64 start,
3573                         u64 len)
3574 {
3575         struct btrfs_root *root = inode->root;
3576         struct extent_changeset *reserved;
3577         bool new_reserved = false;
3578         u64 orig_reserved;
3579         u64 to_reserve;
3580         int ret;
3581
3582         if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &root->fs_info->flags) ||
3583             !is_fstree(root->root_key.objectid) || len == 0)
3584                 return 0;
3585
3586         /* @reserved parameter is mandatory for qgroup */
3587         if (WARN_ON(!reserved_ret))
3588                 return -EINVAL;
3589         if (!*reserved_ret) {
3590                 new_reserved = true;
3591                 *reserved_ret = extent_changeset_alloc();
3592                 if (!*reserved_ret)
3593                         return -ENOMEM;
3594         }
3595         reserved = *reserved_ret;
3596         /* Record already reserved space */
3597         orig_reserved = reserved->bytes_changed;
3598         ret = set_record_extent_bits(&inode->io_tree, start,
3599                         start + len -1, EXTENT_QGROUP_RESERVED, reserved);
3600
3601         /* Newly reserved space */
3602         to_reserve = reserved->bytes_changed - orig_reserved;
3603         trace_btrfs_qgroup_reserve_data(&inode->vfs_inode, start, len,
3604                                         to_reserve, QGROUP_RESERVE);
3605         if (ret < 0)
3606                 goto out;
3607         ret = qgroup_reserve(root, to_reserve, true, BTRFS_QGROUP_RSV_DATA);
3608         if (ret < 0)
3609                 goto cleanup;
3610
3611         return ret;
3612
3613 cleanup:
3614         qgroup_unreserve_range(inode, reserved, start, len);
3615 out:
3616         if (new_reserved) {
3617                 extent_changeset_release(reserved);
3618                 kfree(reserved);
3619                 *reserved_ret = NULL;
3620         }
3621         return ret;
3622 }
3623
3624 /*
3625  * Reserve qgroup space for range [start, start + len).
3626  *
3627  * This function will either reserve space from related qgroups or do nothing
3628  * if the range is already reserved.
3629  *
3630  * Return 0 for successful reservation
3631  * Return <0 for error (including -EQUOT)
3632  *
3633  * NOTE: This function may sleep for memory allocation, dirty page flushing and
3634  *       commit transaction. So caller should not hold any dirty page locked.
3635  */
3636 int btrfs_qgroup_reserve_data(struct btrfs_inode *inode,
3637                         struct extent_changeset **reserved_ret, u64 start,
3638                         u64 len)
3639 {
3640         int ret;
3641
3642         ret = qgroup_reserve_data(inode, reserved_ret, start, len);
3643         if (ret <= 0 && ret != -EDQUOT)
3644                 return ret;
3645
3646         ret = try_flush_qgroup(inode->root);
3647         if (ret < 0)
3648                 return ret;
3649         return qgroup_reserve_data(inode, reserved_ret, start, len);
3650 }
3651
3652 /* Free ranges specified by @reserved, normally in error path */
3653 static int qgroup_free_reserved_data(struct btrfs_inode *inode,
3654                         struct extent_changeset *reserved, u64 start, u64 len)
3655 {
3656         struct btrfs_root *root = inode->root;
3657         struct ulist_node *unode;
3658         struct ulist_iterator uiter;
3659         struct extent_changeset changeset;
3660         int freed = 0;
3661         int ret;
3662
3663         extent_changeset_init(&changeset);
3664         len = round_up(start + len, root->fs_info->sectorsize);
3665         start = round_down(start, root->fs_info->sectorsize);
3666
3667         ULIST_ITER_INIT(&uiter);
3668         while ((unode = ulist_next(&reserved->range_changed, &uiter))) {
3669                 u64 range_start = unode->val;
3670                 /* unode->aux is the inclusive end */
3671                 u64 range_len = unode->aux - range_start + 1;
3672                 u64 free_start;
3673                 u64 free_len;
3674
3675                 extent_changeset_release(&changeset);
3676
3677                 /* Only free range in range [start, start + len) */
3678                 if (range_start >= start + len ||
3679                     range_start + range_len <= start)
3680                         continue;
3681                 free_start = max(range_start, start);
3682                 free_len = min(start + len, range_start + range_len) -
3683                            free_start;
3684                 /*
3685                  * TODO: To also modify reserved->ranges_reserved to reflect
3686                  * the modification.
3687                  *
3688                  * However as long as we free qgroup reserved according to
3689                  * EXTENT_QGROUP_RESERVED, we won't double free.
3690                  * So not need to rush.
3691                  */
3692                 ret = clear_record_extent_bits(&inode->io_tree, free_start,
3693                                 free_start + free_len - 1,
3694                                 EXTENT_QGROUP_RESERVED, &changeset);
3695                 if (ret < 0)
3696                         goto out;
3697                 freed += changeset.bytes_changed;
3698         }
3699         btrfs_qgroup_free_refroot(root->fs_info, root->root_key.objectid, freed,
3700                                   BTRFS_QGROUP_RSV_DATA);
3701         ret = freed;
3702 out:
3703         extent_changeset_release(&changeset);
3704         return ret;
3705 }
3706
3707 static int __btrfs_qgroup_release_data(struct btrfs_inode *inode,
3708                         struct extent_changeset *reserved, u64 start, u64 len,
3709                         int free)
3710 {
3711         struct extent_changeset changeset;
3712         int trace_op = QGROUP_RELEASE;
3713         int ret;
3714
3715         if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &inode->root->fs_info->flags))
3716                 return 0;
3717
3718         /* In release case, we shouldn't have @reserved */
3719         WARN_ON(!free && reserved);
3720         if (free && reserved)
3721                 return qgroup_free_reserved_data(inode, reserved, start, len);
3722         extent_changeset_init(&changeset);
3723         ret = clear_record_extent_bits(&inode->io_tree, start, start + len -1,
3724                                        EXTENT_QGROUP_RESERVED, &changeset);
3725         if (ret < 0)
3726                 goto out;
3727
3728         if (free)
3729                 trace_op = QGROUP_FREE;
3730         trace_btrfs_qgroup_release_data(&inode->vfs_inode, start, len,
3731                                         changeset.bytes_changed, trace_op);
3732         if (free)
3733                 btrfs_qgroup_free_refroot(inode->root->fs_info,
3734                                 inode->root->root_key.objectid,
3735                                 changeset.bytes_changed, BTRFS_QGROUP_RSV_DATA);
3736         ret = changeset.bytes_changed;
3737 out:
3738         extent_changeset_release(&changeset);
3739         return ret;
3740 }
3741
3742 /*
3743  * Free a reserved space range from io_tree and related qgroups
3744  *
3745  * Should be called when a range of pages get invalidated before reaching disk.
3746  * Or for error cleanup case.
3747  * if @reserved is given, only reserved range in [@start, @start + @len) will
3748  * be freed.
3749  *
3750  * For data written to disk, use btrfs_qgroup_release_data().
3751  *
3752  * NOTE: This function may sleep for memory allocation.
3753  */
3754 int btrfs_qgroup_free_data(struct btrfs_inode *inode,
3755                         struct extent_changeset *reserved, u64 start, u64 len)
3756 {
3757         return __btrfs_qgroup_release_data(inode, reserved, start, len, 1);
3758 }
3759
3760 /*
3761  * Release a reserved space range from io_tree only.
3762  *
3763  * Should be called when a range of pages get written to disk and corresponding
3764  * FILE_EXTENT is inserted into corresponding root.
3765  *
3766  * Since new qgroup accounting framework will only update qgroup numbers at
3767  * commit_transaction() time, its reserved space shouldn't be freed from
3768  * related qgroups.
3769  *
3770  * But we should release the range from io_tree, to allow further write to be
3771  * COWed.
3772  *
3773  * NOTE: This function may sleep for memory allocation.
3774  */
3775 int btrfs_qgroup_release_data(struct btrfs_inode *inode, u64 start, u64 len)
3776 {
3777         return __btrfs_qgroup_release_data(inode, NULL, start, len, 0);
3778 }
3779
3780 static void add_root_meta_rsv(struct btrfs_root *root, int num_bytes,
3781                               enum btrfs_qgroup_rsv_type type)
3782 {
3783         if (type != BTRFS_QGROUP_RSV_META_PREALLOC &&
3784             type != BTRFS_QGROUP_RSV_META_PERTRANS)
3785                 return;
3786         if (num_bytes == 0)
3787                 return;
3788
3789         spin_lock(&root->qgroup_meta_rsv_lock);
3790         if (type == BTRFS_QGROUP_RSV_META_PREALLOC)
3791                 root->qgroup_meta_rsv_prealloc += num_bytes;
3792         else
3793                 root->qgroup_meta_rsv_pertrans += num_bytes;
3794         spin_unlock(&root->qgroup_meta_rsv_lock);
3795 }
3796
3797 static int sub_root_meta_rsv(struct btrfs_root *root, int num_bytes,
3798                              enum btrfs_qgroup_rsv_type type)
3799 {
3800         if (type != BTRFS_QGROUP_RSV_META_PREALLOC &&
3801             type != BTRFS_QGROUP_RSV_META_PERTRANS)
3802                 return 0;
3803         if (num_bytes == 0)
3804                 return 0;
3805
3806         spin_lock(&root->qgroup_meta_rsv_lock);
3807         if (type == BTRFS_QGROUP_RSV_META_PREALLOC) {
3808                 num_bytes = min_t(u64, root->qgroup_meta_rsv_prealloc,
3809                                   num_bytes);
3810                 root->qgroup_meta_rsv_prealloc -= num_bytes;
3811         } else {
3812                 num_bytes = min_t(u64, root->qgroup_meta_rsv_pertrans,
3813                                   num_bytes);
3814                 root->qgroup_meta_rsv_pertrans -= num_bytes;
3815         }
3816         spin_unlock(&root->qgroup_meta_rsv_lock);
3817         return num_bytes;
3818 }
3819
3820 static int qgroup_reserve_meta(struct btrfs_root *root, int num_bytes,
3821                                 enum btrfs_qgroup_rsv_type type, bool enforce)
3822 {
3823         struct btrfs_fs_info *fs_info = root->fs_info;
3824         int ret;
3825
3826         if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags) ||
3827             !is_fstree(root->root_key.objectid) || num_bytes == 0)
3828                 return 0;
3829
3830         BUG_ON(num_bytes != round_down(num_bytes, fs_info->nodesize));
3831         trace_qgroup_meta_reserve(root, (s64)num_bytes, type);
3832         ret = qgroup_reserve(root, num_bytes, enforce, type);
3833         if (ret < 0)
3834                 return ret;
3835         /*
3836          * Record what we have reserved into root.
3837          *
3838          * To avoid quota disabled->enabled underflow.
3839          * In that case, we may try to free space we haven't reserved
3840          * (since quota was disabled), so record what we reserved into root.
3841          * And ensure later release won't underflow this number.
3842          */
3843         add_root_meta_rsv(root, num_bytes, type);
3844         return ret;
3845 }
3846
3847 int __btrfs_qgroup_reserve_meta(struct btrfs_root *root, int num_bytes,
3848                                 enum btrfs_qgroup_rsv_type type, bool enforce)
3849 {
3850         int ret;
3851
3852         ret = qgroup_reserve_meta(root, num_bytes, type, enforce);
3853         if (ret <= 0 && ret != -EDQUOT)
3854                 return ret;
3855
3856         ret = try_flush_qgroup(root);
3857         if (ret < 0)
3858                 return ret;
3859         return qgroup_reserve_meta(root, num_bytes, type, enforce);
3860 }
3861
3862 void btrfs_qgroup_free_meta_all_pertrans(struct btrfs_root *root)
3863 {
3864         struct btrfs_fs_info *fs_info = root->fs_info;
3865
3866         if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags) ||
3867             !is_fstree(root->root_key.objectid))
3868                 return;
3869
3870         /* TODO: Update trace point to handle such free */
3871         trace_qgroup_meta_free_all_pertrans(root);
3872         /* Special value -1 means to free all reserved space */
3873         btrfs_qgroup_free_refroot(fs_info, root->root_key.objectid, (u64)-1,
3874                                   BTRFS_QGROUP_RSV_META_PERTRANS);
3875 }
3876
3877 void __btrfs_qgroup_free_meta(struct btrfs_root *root, int num_bytes,
3878                               enum btrfs_qgroup_rsv_type type)
3879 {
3880         struct btrfs_fs_info *fs_info = root->fs_info;
3881
3882         if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags) ||
3883             !is_fstree(root->root_key.objectid))
3884                 return;
3885
3886         /*
3887          * reservation for META_PREALLOC can happen before quota is enabled,
3888          * which can lead to underflow.
3889          * Here ensure we will only free what we really have reserved.
3890          */
3891         num_bytes = sub_root_meta_rsv(root, num_bytes, type);
3892         BUG_ON(num_bytes != round_down(num_bytes, fs_info->nodesize));
3893         trace_qgroup_meta_reserve(root, -(s64)num_bytes, type);
3894         btrfs_qgroup_free_refroot(fs_info, root->root_key.objectid,
3895                                   num_bytes, type);
3896 }
3897
3898 static void qgroup_convert_meta(struct btrfs_fs_info *fs_info, u64 ref_root,
3899                                 int num_bytes)
3900 {
3901         struct btrfs_qgroup *qgroup;
3902         struct ulist_node *unode;
3903         struct ulist_iterator uiter;
3904         int ret = 0;
3905
3906         if (num_bytes == 0)
3907                 return;
3908         if (!fs_info->quota_root)
3909                 return;
3910
3911         spin_lock(&fs_info->qgroup_lock);
3912         qgroup = find_qgroup_rb(fs_info, ref_root);
3913         if (!qgroup)
3914                 goto out;
3915         ulist_reinit(fs_info->qgroup_ulist);
3916         ret = ulist_add(fs_info->qgroup_ulist, qgroup->qgroupid,
3917                        qgroup_to_aux(qgroup), GFP_ATOMIC);
3918         if (ret < 0)
3919                 goto out;
3920         ULIST_ITER_INIT(&uiter);
3921         while ((unode = ulist_next(fs_info->qgroup_ulist, &uiter))) {
3922                 struct btrfs_qgroup *qg;
3923                 struct btrfs_qgroup_list *glist;
3924
3925                 qg = unode_aux_to_qgroup(unode);
3926
3927                 qgroup_rsv_release(fs_info, qg, num_bytes,
3928                                 BTRFS_QGROUP_RSV_META_PREALLOC);
3929                 qgroup_rsv_add(fs_info, qg, num_bytes,
3930                                 BTRFS_QGROUP_RSV_META_PERTRANS);
3931                 list_for_each_entry(glist, &qg->groups, next_group) {
3932                         ret = ulist_add(fs_info->qgroup_ulist,
3933                                         glist->group->qgroupid,
3934                                         qgroup_to_aux(glist->group), GFP_ATOMIC);
3935                         if (ret < 0)
3936                                 goto out;
3937                 }
3938         }
3939 out:
3940         spin_unlock(&fs_info->qgroup_lock);
3941 }
3942
3943 void btrfs_qgroup_convert_reserved_meta(struct btrfs_root *root, int num_bytes)
3944 {
3945         struct btrfs_fs_info *fs_info = root->fs_info;
3946
3947         if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags) ||
3948             !is_fstree(root->root_key.objectid))
3949                 return;
3950         /* Same as btrfs_qgroup_free_meta_prealloc() */
3951         num_bytes = sub_root_meta_rsv(root, num_bytes,
3952                                       BTRFS_QGROUP_RSV_META_PREALLOC);
3953         trace_qgroup_meta_convert(root, num_bytes);
3954         qgroup_convert_meta(fs_info, root->root_key.objectid, num_bytes);
3955 }
3956
3957 /*
3958  * Check qgroup reserved space leaking, normally at destroy inode
3959  * time
3960  */
3961 void btrfs_qgroup_check_reserved_leak(struct btrfs_inode *inode)
3962 {
3963         struct extent_changeset changeset;
3964         struct ulist_node *unode;
3965         struct ulist_iterator iter;
3966         int ret;
3967
3968         extent_changeset_init(&changeset);
3969         ret = clear_record_extent_bits(&inode->io_tree, 0, (u64)-1,
3970                         EXTENT_QGROUP_RESERVED, &changeset);
3971
3972         WARN_ON(ret < 0);
3973         if (WARN_ON(changeset.bytes_changed)) {
3974                 ULIST_ITER_INIT(&iter);
3975                 while ((unode = ulist_next(&changeset.range_changed, &iter))) {
3976                         btrfs_warn(inode->root->fs_info,
3977                 "leaking qgroup reserved space, ino: %llu, start: %llu, end: %llu",
3978                                 btrfs_ino(inode), unode->val, unode->aux);
3979                 }
3980                 btrfs_qgroup_free_refroot(inode->root->fs_info,
3981                                 inode->root->root_key.objectid,
3982                                 changeset.bytes_changed, BTRFS_QGROUP_RSV_DATA);
3983
3984         }
3985         extent_changeset_release(&changeset);
3986 }
3987
3988 void btrfs_qgroup_init_swapped_blocks(
3989         struct btrfs_qgroup_swapped_blocks *swapped_blocks)
3990 {
3991         int i;
3992
3993         spin_lock_init(&swapped_blocks->lock);
3994         for (i = 0; i < BTRFS_MAX_LEVEL; i++)
3995                 swapped_blocks->blocks[i] = RB_ROOT;
3996         swapped_blocks->swapped = false;
3997 }
3998
3999 /*
4000  * Delete all swapped blocks record of @root.
4001  * Every record here means we skipped a full subtree scan for qgroup.
4002  *
4003  * Gets called when committing one transaction.
4004  */
4005 void btrfs_qgroup_clean_swapped_blocks(struct btrfs_root *root)
4006 {
4007         struct btrfs_qgroup_swapped_blocks *swapped_blocks;
4008         int i;
4009
4010         swapped_blocks = &root->swapped_blocks;
4011
4012         spin_lock(&swapped_blocks->lock);
4013         if (!swapped_blocks->swapped)
4014                 goto out;
4015         for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
4016                 struct rb_root *cur_root = &swapped_blocks->blocks[i];
4017                 struct btrfs_qgroup_swapped_block *entry;
4018                 struct btrfs_qgroup_swapped_block *next;
4019
4020                 rbtree_postorder_for_each_entry_safe(entry, next, cur_root,
4021                                                      node)
4022                         kfree(entry);
4023                 swapped_blocks->blocks[i] = RB_ROOT;
4024         }
4025         swapped_blocks->swapped = false;
4026 out:
4027         spin_unlock(&swapped_blocks->lock);
4028 }
4029
4030 /*
4031  * Add subtree roots record into @subvol_root.
4032  *
4033  * @subvol_root:        tree root of the subvolume tree get swapped
4034  * @bg:                 block group under balance
4035  * @subvol_parent/slot: pointer to the subtree root in subvolume tree
4036  * @reloc_parent/slot:  pointer to the subtree root in reloc tree
4037  *                      BOTH POINTERS ARE BEFORE TREE SWAP
4038  * @last_snapshot:      last snapshot generation of the subvolume tree
4039  */
4040 int btrfs_qgroup_add_swapped_blocks(struct btrfs_trans_handle *trans,
4041                 struct btrfs_root *subvol_root,
4042                 struct btrfs_block_group *bg,
4043                 struct extent_buffer *subvol_parent, int subvol_slot,
4044                 struct extent_buffer *reloc_parent, int reloc_slot,
4045                 u64 last_snapshot)
4046 {
4047         struct btrfs_fs_info *fs_info = subvol_root->fs_info;
4048         struct btrfs_qgroup_swapped_blocks *blocks = &subvol_root->swapped_blocks;
4049         struct btrfs_qgroup_swapped_block *block;
4050         struct rb_node **cur;
4051         struct rb_node *parent = NULL;
4052         int level = btrfs_header_level(subvol_parent) - 1;
4053         int ret = 0;
4054
4055         if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags))
4056                 return 0;
4057
4058         if (btrfs_node_ptr_generation(subvol_parent, subvol_slot) >
4059             btrfs_node_ptr_generation(reloc_parent, reloc_slot)) {
4060                 btrfs_err_rl(fs_info,
4061                 "%s: bad parameter order, subvol_gen=%llu reloc_gen=%llu",
4062                         __func__,
4063                         btrfs_node_ptr_generation(subvol_parent, subvol_slot),
4064                         btrfs_node_ptr_generation(reloc_parent, reloc_slot));
4065                 return -EUCLEAN;
4066         }
4067
4068         block = kmalloc(sizeof(*block), GFP_NOFS);
4069         if (!block) {
4070                 ret = -ENOMEM;
4071                 goto out;
4072         }
4073
4074         /*
4075          * @reloc_parent/slot is still before swap, while @block is going to
4076          * record the bytenr after swap, so we do the swap here.
4077          */
4078         block->subvol_bytenr = btrfs_node_blockptr(reloc_parent, reloc_slot);
4079         block->subvol_generation = btrfs_node_ptr_generation(reloc_parent,
4080                                                              reloc_slot);
4081         block->reloc_bytenr = btrfs_node_blockptr(subvol_parent, subvol_slot);
4082         block->reloc_generation = btrfs_node_ptr_generation(subvol_parent,
4083                                                             subvol_slot);
4084         block->last_snapshot = last_snapshot;
4085         block->level = level;
4086
4087         /*
4088          * If we have bg == NULL, we're called from btrfs_recover_relocation(),
4089          * no one else can modify tree blocks thus we qgroup will not change
4090          * no matter the value of trace_leaf.
4091          */
4092         if (bg && bg->flags & BTRFS_BLOCK_GROUP_DATA)
4093                 block->trace_leaf = true;
4094         else
4095                 block->trace_leaf = false;
4096         btrfs_node_key_to_cpu(reloc_parent, &block->first_key, reloc_slot);
4097
4098         /* Insert @block into @blocks */
4099         spin_lock(&blocks->lock);
4100         cur = &blocks->blocks[level].rb_node;
4101         while (*cur) {
4102                 struct btrfs_qgroup_swapped_block *entry;
4103
4104                 parent = *cur;
4105                 entry = rb_entry(parent, struct btrfs_qgroup_swapped_block,
4106                                  node);
4107
4108                 if (entry->subvol_bytenr < block->subvol_bytenr) {
4109                         cur = &(*cur)->rb_left;
4110                 } else if (entry->subvol_bytenr > block->subvol_bytenr) {
4111                         cur = &(*cur)->rb_right;
4112                 } else {
4113                         if (entry->subvol_generation !=
4114                                         block->subvol_generation ||
4115                             entry->reloc_bytenr != block->reloc_bytenr ||
4116                             entry->reloc_generation !=
4117                                         block->reloc_generation) {
4118                                 /*
4119                                  * Duplicated but mismatch entry found.
4120                                  * Shouldn't happen.
4121                                  *
4122                                  * Marking qgroup inconsistent should be enough
4123                                  * for end users.
4124                                  */
4125                                 WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG));
4126                                 ret = -EEXIST;
4127                         }
4128                         kfree(block);
4129                         goto out_unlock;
4130                 }
4131         }
4132         rb_link_node(&block->node, parent, cur);
4133         rb_insert_color(&block->node, &blocks->blocks[level]);
4134         blocks->swapped = true;
4135 out_unlock:
4136         spin_unlock(&blocks->lock);
4137 out:
4138         if (ret < 0)
4139                 fs_info->qgroup_flags |=
4140                         BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
4141         return ret;
4142 }
4143
4144 /*
4145  * Check if the tree block is a subtree root, and if so do the needed
4146  * delayed subtree trace for qgroup.
4147  *
4148  * This is called during btrfs_cow_block().
4149  */
4150 int btrfs_qgroup_trace_subtree_after_cow(struct btrfs_trans_handle *trans,
4151                                          struct btrfs_root *root,
4152                                          struct extent_buffer *subvol_eb)
4153 {
4154         struct btrfs_fs_info *fs_info = root->fs_info;
4155         struct btrfs_qgroup_swapped_blocks *blocks = &root->swapped_blocks;
4156         struct btrfs_qgroup_swapped_block *block;
4157         struct extent_buffer *reloc_eb = NULL;
4158         struct rb_node *node;
4159         bool found = false;
4160         bool swapped = false;
4161         int level = btrfs_header_level(subvol_eb);
4162         int ret = 0;
4163         int i;
4164
4165         if (!test_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags))
4166                 return 0;
4167         if (!is_fstree(root->root_key.objectid) || !root->reloc_root)
4168                 return 0;
4169
4170         spin_lock(&blocks->lock);
4171         if (!blocks->swapped) {
4172                 spin_unlock(&blocks->lock);
4173                 return 0;
4174         }
4175         node = blocks->blocks[level].rb_node;
4176
4177         while (node) {
4178                 block = rb_entry(node, struct btrfs_qgroup_swapped_block, node);
4179                 if (block->subvol_bytenr < subvol_eb->start) {
4180                         node = node->rb_left;
4181                 } else if (block->subvol_bytenr > subvol_eb->start) {
4182                         node = node->rb_right;
4183                 } else {
4184                         found = true;
4185                         break;
4186                 }
4187         }
4188         if (!found) {
4189                 spin_unlock(&blocks->lock);
4190                 goto out;
4191         }
4192         /* Found one, remove it from @blocks first and update blocks->swapped */
4193         rb_erase(&block->node, &blocks->blocks[level]);
4194         for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
4195                 if (RB_EMPTY_ROOT(&blocks->blocks[i])) {
4196                         swapped = true;
4197                         break;
4198                 }
4199         }
4200         blocks->swapped = swapped;
4201         spin_unlock(&blocks->lock);
4202
4203         /* Read out reloc subtree root */
4204         reloc_eb = read_tree_block(fs_info, block->reloc_bytenr,
4205                                    block->reloc_generation, block->level,
4206                                    &block->first_key);
4207         if (IS_ERR(reloc_eb)) {
4208                 ret = PTR_ERR(reloc_eb);
4209                 reloc_eb = NULL;
4210                 goto free_out;
4211         }
4212         if (!extent_buffer_uptodate(reloc_eb)) {
4213                 ret = -EIO;
4214                 goto free_out;
4215         }
4216
4217         ret = qgroup_trace_subtree_swap(trans, reloc_eb, subvol_eb,
4218                         block->last_snapshot, block->trace_leaf);
4219 free_out:
4220         kfree(block);
4221         free_extent_buffer(reloc_eb);
4222 out:
4223         if (ret < 0) {
4224                 btrfs_err_rl(fs_info,
4225                              "failed to account subtree at bytenr %llu: %d",
4226                              subvol_eb->start, ret);
4227                 fs_info->qgroup_flags |= BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT;
4228         }
4229         return ret;
4230 }
4231
4232 void btrfs_qgroup_destroy_extent_records(struct btrfs_transaction *trans)
4233 {
4234         struct btrfs_qgroup_extent_record *entry;
4235         struct btrfs_qgroup_extent_record *next;
4236         struct rb_root *root;
4237
4238         root = &trans->delayed_refs.dirty_extent_root;
4239         rbtree_postorder_for_each_entry_safe(entry, next, root, node) {
4240                 ulist_free(entry->old_roots);
4241                 kfree(entry);
4242         }
4243 }