fs/btrfs/qgroup.c

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