253089abeschrock * CDDL HEADER START
353089abeschrock *
453089abeschrock * The contents of this file are subject to the terms of the
553089abeschrock * Common Development and Distribution License (the "License").
653089abeschrock * You may not use this file except in compliance with the License.
753089abeschrock *
853089abeschrock * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
953089abeschrock * or http://www.opensolaris.org/os/licensing.
1053089abeschrock * See the License for the specific language governing permissions
1153089abeschrock * and limitations under the License.
1253089abeschrock *
1353089abeschrock * When distributing Covered Code, include this CDDL HEADER in each
1453089abeschrock * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
1553089abeschrock * If applicable, add the following below this CDDL HEADER, with the
1653089abeschrock * fields enclosed by brackets "[]" replaced with your own identifying
1753089abeschrock * information: Portions Copyright [yyyy] [name of copyright owner]
1853089abeschrock *
1953089abeschrock * CDDL HEADER END
2053089abeschrock */
2310e67aaMatthew Ahrens * Copyright (c) 2011, 2015 by Delphix. All rights reserved.
24c3d26abMatthew Ahrens * Copyright (c) 2014 Integros [integros.com]
2553089abeschrock */
2753089abeschrock#include <sys/arc.h>
2853089abeschrock#include <sys/bptree.h>
2953089abeschrock#include <sys/dmu.h>
3053089abeschrock#include <sys/dmu_objset.h>
3153089abeschrock#include <sys/dmu_tx.h>
3253089abeschrock#include <sys/dmu_traverse.h>
3353089abeschrock#include <sys/dsl_dataset.h>
3453089abeschrock#include <sys/dsl_dir.h>
3553089abeschrock#include <sys/dsl_pool.h>
3653089abeschrock#include <sys/dnode.h>
3753089abeschrock#include <sys/refcount.h>
3853089abeschrock#include <sys/spa.h>
4153089abeschrock * A bptree is a queue of root block pointers from destroyed datasets. When a
4253089abeschrock * dataset is destroyed its root block pointer is put on the end of the pool's
4353089abeschrock * bptree queue so the dataset's blocks can be freed asynchronously by
4453089abeschrock * dsl_scan_sync. This allows the delete operation to finish without traversing
4553089abeschrock * all the dataset's blocks.
4653089abeschrock *
47f717074Will Andrews * Note that while bt_begin and bt_end are only ever incremented in this code,
4853089abeschrock * they are effectively reset to 0 every time the entire bptree is freed because
4953089abeschrock * the bptree's object is destroyed and re-created.
5053089abeschrock */
5253089abeschrockstruct bptree_args {
5353089abeschrock	bptree_phys_t *ba_phys;	/* data in bonus buffer, dirtied if freeing */
5453089abeschrock	boolean_t ba_free;	/* true if freeing during traversal */
5653089abeschrock	bptree_itor_t *ba_func;	/* function to call for each blockpointer */
5753089abeschrock	void *ba_arg;		/* caller supplied argument to ba_func */
5853089abeschrock	dmu_tx_t *ba_tx;	/* caller supplied tx, NULL if not freeing */
5953089abeschrock} bptree_args_t;
6253089abeschrockbptree_alloc(objset_t *os, dmu_tx_t *tx)
6453089abeschrock	uint64_t obj;
6553089abeschrock	dmu_buf_t *db;
6653089abeschrock	bptree_phys_t *bt;
6853089abeschrock	obj = dmu_object_alloc(os, DMU_OTN_UINT64_METADATA,
7053089abeschrock	    sizeof (bptree_phys_t), tx);
7253089abeschrock	/*
7353089abeschrock	 * Bonus buffer contents are already initialized to 0, but for
7453089abeschrock	 * readability we make it explicit.
7553089abeschrock	 */
76b420f3aRichard Lowe	VERIFY3U(0, ==, dmu_bonus_hold(os, obj, FTAG, &db));
7753089abeschrock	dmu_buf_will_dirty(db, tx);
7853089abeschrock	bt = db->db_data;
7953089abeschrock	bt->bt_begin = 0;
8053089abeschrock	bt->bt_end = 0;
8153089abeschrock	bt->bt_bytes = 0;
8253089abeschrock	bt->bt_comp = 0;
8353089abeschrock	bt->bt_uncomp = 0;
8453089abeschrock	dmu_buf_rele(db, FTAG);
8653089abeschrock	return (obj);
9053089abeschrockbptree_free(objset_t *os, uint64_t obj, dmu_tx_t *tx)
9253089abeschrock	dmu_buf_t *db;
9353089abeschrock	bptree_phys_t *bt;
95b420f3aRichard Lowe	VERIFY3U(0, ==, dmu_bonus_hold(os, obj, FTAG, &db));
9653089abeschrock	bt = db->db_data;
9753089abeschrock	ASSERT3U(bt->bt_begin, ==, bt->bt_end);
98fb09f5aMadhav Suresh	ASSERT0(bt->bt_bytes);
99fb09f5aMadhav Suresh	ASSERT0(bt->bt_comp);
100fb09f5aMadhav Suresh	ASSERT0(bt->bt_uncomp);
10153089abeschrock	dmu_buf_rele(db, FTAG);
10353089abeschrock	return (dmu_object_free(os, obj, tx));
1067fd05acMatthew Ahrensboolean_t
1077fd05acMatthew Ahrensbptree_is_empty(objset_t *os, uint64_t obj)
1087fd05acMatthew Ahrens{
1097fd05acMatthew Ahrens	dmu_buf_t *db;
1107fd05acMatthew Ahrens	bptree_phys_t *bt;
1117fd05acMatthew Ahrens	boolean_t rv;
1127fd05acMatthew Ahrens
1137fd05acMatthew Ahrens	VERIFY0(dmu_bonus_hold(os, obj, FTAG, &db));
1147fd05acMatthew Ahrens	bt = db->db_data;
1157fd05acMatthew Ahrens	rv = (bt->bt_begin == bt->bt_end);
1167fd05acMatthew Ahrens	dmu_buf_rele(db, FTAG);
1177fd05acMatthew Ahrens	return (rv);
1187fd05acMatthew Ahrens}
1197fd05acMatthew Ahrens
12153089abeschrockbptree_add(objset_t *os, uint64_t obj, blkptr_t *bp, uint64_t birth_txg,
12253089abeschrock    uint64_t bytes, uint64_t comp, uint64_t uncomp, dmu_tx_t *tx)
12453089abeschrock	dmu_buf_t *db;
12553089abeschrock	bptree_phys_t *bt;
1267fd05acMatthew Ahrens	bptree_entry_phys_t bte = { 0 };
12853089abeschrock	/*
12953089abeschrock	 * bptree objects are in the pool mos, therefore they can only be
13053089abeschrock	 * modified in syncing context. Furthermore, this is only modified
13153089abeschrock	 * by the sync thread, so no locking is necessary.
13253089abeschrock	 */
13353089abeschrock	ASSERT(dmu_tx_is_syncing(tx));
135b420f3aRichard Lowe	VERIFY3U(0, ==, dmu_bonus_hold(os, obj, FTAG, &db));
13653089abeschrock	bt = db->db_data;
13853089abeschrock	bte.be_birth_txg = birth_txg;
13953089abeschrock	bte.be_bp = *bp;
14053089abeschrock	dmu_write(os, obj, bt->bt_end * sizeof (bte), sizeof (bte), &bte, tx);
14253089abeschrock	dmu_buf_will_dirty(db, tx);
14353089abeschrock	bt->bt_end++;
14453089abeschrock	bt->bt_bytes += bytes;
14553089abeschrock	bt->bt_comp += comp;
14653089abeschrock	bt->bt_uncomp += uncomp;
14753089abeschrock	dmu_buf_rele(db, FTAG);
15053089abeschrock/* ARGSUSED */
15153089abeschrockstatic int
1521b912ecGeorge Wilsonbptree_visit_cb(spa_t *spa, zilog_t *zilog, const blkptr_t *bp,
1537802d7bMatthew Ahrens    const zbookmark_phys_t *zb, const dnode_phys_t *dnp, void *arg)
15553089abeschrock	int err;
15653089abeschrock	struct bptree_args *ba = arg;
158a2cdcddPaul Dagnelie	if (bp == NULL || BP_IS_HOLE(bp))
15953089abeschrock		return (0);
16153089abeschrock	err = ba->ba_func(ba->ba_arg, bp, ba->ba_tx);
16253089abeschrock	if (err == 0 && ba->ba_free) {
16353089abeschrock		ba->ba_phys->bt_bytes -= bp_get_dsize_sync(spa, bp);
16453089abeschrock		ba->ba_phys->bt_comp -= BP_GET_PSIZE(bp);
16553089abeschrock		ba->ba_phys->bt_uncomp -= BP_GET_UCSIZE(bp);
16653089abeschrock	}
16753089abeschrock	return (err);
1707fd05acMatthew Ahrens/*
1717fd05acMatthew Ahrens * If "free" is set:
1727fd05acMatthew Ahrens *  - It is assumed that "func" will be freeing the block pointers.
1737fd05acMatthew Ahrens *  - If "func" returns nonzero, the bookmark will be remembered and
1747fd05acMatthew Ahrens *    iteration will be restarted from this point on next invocation.
1757fd05acMatthew Ahrens *  - If an i/o error is encountered (e.g. "func" returns EIO or ECKSUM),
1767fd05acMatthew Ahrens *    bptree_iterate will remember the bookmark, continue traversing
1777fd05acMatthew Ahrens *    any additional entries, and return 0.
1787fd05acMatthew Ahrens *
1797fd05acMatthew Ahrens * If "free" is not set, traversal will stop and return an error if
1807fd05acMatthew Ahrens * an i/o error is encountered.
1817fd05acMatthew Ahrens *
1827fd05acMatthew Ahrens * In either case, if zfs_free_leak_on_eio is set, i/o errors will be
1837fd05acMatthew Ahrens * ignored and traversal will continue (i.e. TRAVERSE_HARD will be passed to
1847fd05acMatthew Ahrens * traverse_dataset_destroyed()).
1857fd05acMatthew Ahrens */
18753089abeschrockbptree_iterate(objset_t *os, uint64_t obj, boolean_t free, bptree_itor_t func,
18853089abeschrock    void *arg, dmu_tx_t *tx)
1907fd05acMatthew Ahrens	boolean_t ioerr = B_FALSE;
19153089abeschrock	int err;
19253089abeschrock	uint64_t i;
19353089abeschrock	dmu_buf_t *db;
19453089abeschrock	struct bptree_args ba;
19653089abeschrock	ASSERT(!free || dmu_tx_is_syncing(tx));
19853089abeschrock	err = dmu_bonus_hold(os, obj, FTAG, &db);
19953089abeschrock	if (err != 0)
20053089abeschrock		return (err);
20253089abeschrock	if (free)
20353089abeschrock		dmu_buf_will_dirty(db, tx);
20553089abeschrock	ba.ba_phys = db->db_data;
20653089abeschrock	ba.ba_free = free;
20753089abeschrock	ba.ba_func = func;
20853089abeschrock	ba.ba_arg = arg;
20953089abeschrock	ba.ba_tx = tx;
21153089abeschrock	err = 0;
21253089abeschrock	for (i = ba.ba_phys->bt_begin; i < ba.ba_phys->bt_end; i++) {
21353089abeschrock		bptree_entry_phys_t bte;
214eb63303Tom Caputi		int flags = TRAVERSE_PREFETCH_METADATA | TRAVERSE_POST
215eb63303Tom Caputi		    | TRAVERSE_NO_DECRYPT;
21753089abeschrock		err = dmu_read(os, obj, i * sizeof (bte), sizeof (bte),
21853089abeschrock		    &bte, DMU_READ_NO_PREFETCH);
21953089abeschrock		if (err != 0)
22053089abeschrock			break;
2227fd05acMatthew Ahrens		if (zfs_free_leak_on_eio)
2238b36997Matthew Ahrens			flags |= TRAVERSE_HARD;
22410e67aaMatthew Ahrens		zfs_dbgmsg("bptree index %lld: traversing from min_txg=%lld "
2257fd05acMatthew Ahrens		    "bookmark %lld/%lld/%lld/%lld",
22610e67aaMatthew Ahrens		    (longlong_t)i,
22710e67aaMatthew Ahrens		    (longlong_t)bte.be_birth_txg,
2287fd05acMatthew Ahrens		    (longlong_t)bte.be_zb.zb_objset,
2297fd05acMatthew Ahrens		    (longlong_t)bte.be_zb.zb_object,
2307fd05acMatthew Ahrens		    (longlong_t)bte.be_zb.zb_level,
2317fd05acMatthew Ahrens		    (longlong_t)bte.be_zb.zb_blkid);
23253089abeschrock		err = traverse_dataset_destroyed(os->os_spa, &bte.be_bp,
2338b36997Matthew Ahrens		    bte.be_birth_txg, &bte.be_zb, flags,
23453089abeschrock		    bptree_visit_cb, &ba);
23553089abeschrock		if (free) {
2367fd05acMatthew Ahrens			/*
2377fd05acMatthew Ahrens			 * The callback has freed the visited block pointers.
2387fd05acMatthew Ahrens			 * Record our traversal progress on disk, either by
2397fd05acMatthew Ahrens			 * updating this record's bookmark, or by logically
2407fd05acMatthew Ahrens			 * removing this record by advancing bt_begin.
2417fd05acMatthew Ahrens			 */
2427fd05acMatthew Ahrens			if (err != 0) {
24353089abeschrock				/* save bookmark for future resume */
24453089abeschrock				ASSERT3U(bte.be_zb.zb_objset, ==,
24553089abeschrock				    ZB_DESTROYED_OBJSET);
246fb09f5aMadhav Suresh				ASSERT0(bte.be_zb.zb_level);
24753089abeschrock				dmu_write(os, obj, i * sizeof (bte),
24853089abeschrock				    sizeof (bte), &bte, tx);
2497fd05acMatthew Ahrens				if (err == EIO || err == ECKSUM ||
2507fd05acMatthew Ahrens				    err == ENXIO) {
2517fd05acMatthew Ahrens					/*
2527fd05acMatthew Ahrens					 * Skip the rest of this tree and
2537fd05acMatthew Ahrens					 * continue on to the next entry.
2547fd05acMatthew Ahrens					 */
2557fd05acMatthew Ahrens					err = 0;
2567fd05acMatthew Ahrens					ioerr = B_TRUE;
2577fd05acMatthew Ahrens				} else {
2587fd05acMatthew Ahrens					break;
2597fd05acMatthew Ahrens				}
2607fd05acMatthew Ahrens			} else if (ioerr) {
2618b36997Matthew Ahrens				/*
2627fd05acMatthew Ahrens				 * This entry is finished, but there were
2637fd05acMatthew Ahrens				 * i/o errors on previous entries, so we
2647fd05acMatthew Ahrens				 * can't adjust bt_begin.  Set this entry's
2657fd05acMatthew Ahrens				 * be_birth_txg such that it will be
2667fd05acMatthew Ahrens				 * treated as a no-op in future traversals.
2678b36997Matthew Ahrens				 */
2687fd05acMatthew Ahrens				bte.be_birth_txg = UINT64_MAX;
2697fd05acMatthew Ahrens				dmu_write(os, obj, i * sizeof (bte),
2707fd05acMatthew Ahrens				    sizeof (bte), &bte, tx);
2718b36997Matthew Ahrens			}
2728b36997Matthew Ahrens
2737fd05acMatthew Ahrens			if (!ioerr) {
2747fd05acMatthew Ahrens				ba.ba_phys->bt_begin++;
2757fd05acMatthew Ahrens				(void) dmu_free_range(os, obj,
2767fd05acMatthew Ahrens				    i * sizeof (bte), sizeof (bte), tx);
2777fd05acMatthew Ahrens			}
2787fd05acMatthew Ahrens		} else if (err != 0) {
2797fd05acMatthew Ahrens			break;
28053089abeschrock		}
28153089abeschrock	}
2837fd05acMatthew Ahrens	ASSERT(!free || err != 0 || ioerr ||
2847fd05acMatthew Ahrens	    ba.ba_phys->bt_begin == ba.ba_phys->bt_end);
28653089abeschrock	/* if all blocks are free there should be no used space */
28753089abeschrock	if (ba.ba_phys->bt_begin == ba.ba_phys->bt_end) {
2887fd05acMatthew Ahrens		if (zfs_free_leak_on_eio) {
2897fd05acMatthew Ahrens			ba.ba_phys->bt_bytes = 0;
2907fd05acMatthew Ahrens			ba.ba_phys->bt_comp = 0;
2917fd05acMatthew Ahrens			ba.ba_phys->bt_uncomp = 0;
2927fd05acMatthew Ahrens		}
2937fd05acMatthew Ahrens
294fb09f5aMadhav Suresh		ASSERT0(ba.ba_phys->bt_bytes);
295fb09f5aMadhav Suresh		ASSERT0(ba.ba_phys->bt_comp);
296fb09f5aMadhav Suresh		ASSERT0(ba.ba_phys->bt_uncomp);
29753089abeschrock	}
29953089abeschrock	dmu_buf_rele(db, FTAG);
30153089abeschrock	return (err);