qgroup.c

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