bptree.c revision 9fa718d2f477620f14e3f2948dd03e3470add804
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi/*
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * CDDL HEADER START
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi *
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * The contents of this file are subject to the terms of the
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * Common Development and Distribution License (the "License").
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * You may not use this file except in compliance with the License.
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi *
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * or http://www.opensolaris.org/os/licensing.
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * See the License for the specific language governing permissions
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * and limitations under the License.
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi *
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * When distributing Covered Code, include this CDDL HEADER in each
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * If applicable, add the following below this CDDL HEADER, with the
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * fields enclosed by brackets "[]" replaced with your own identifying
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * information: Portions Copyright [yyyy] [name of copyright owner]
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi *
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * CDDL HEADER END
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi */
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi/*
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * Copyright (c) 2012 by Delphix. All rights reserved.
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi */
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi#include <sys/arc.h>
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi#include <sys/bptree.h>
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi#include <sys/dmu.h>
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi#include <sys/dmu_objset.h>
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi#include <sys/dmu_tx.h>
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi#include <sys/dmu_traverse.h>
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi#include <sys/dsl_dataset.h>
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi#include <sys/dsl_dir.h>
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi#include <sys/dsl_pool.h>
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi#include <sys/dnode.h>
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi#include <sys/refcount.h>
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi#include <sys/spa.h>
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi/*
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * A bptree is a queue of root block pointers from destroyed datasets. When a
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * dataset is destroyed its root block pointer is put on the end of the pool's
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * bptree queue so the dataset's blocks can be freed asynchronously by
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * dsl_scan_sync. This allows the delete operation to finish without traversing
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * all the dataset's blocks.
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi *
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * Note that while bt_begin and bt_end are only ever incremented in this code
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * they are effectively reset to 0 every time the entire bptree is freed because
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * the bptree's object is destroyed and re-created.
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi */
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchistruct bptree_args {
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bptree_phys_t *ba_phys; /* data in bonus buffer, dirtied if freeing */
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi boolean_t ba_free; /* true if freeing during traversal */
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bptree_itor_t *ba_func; /* function to call for each blockpointer */
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi void *ba_arg; /* caller supplied argument to ba_func */
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi dmu_tx_t *ba_tx; /* caller supplied tx, NULL if not freeing */
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi} bptree_args_t;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchiuint64_t
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchibptree_alloc(objset_t *os, dmu_tx_t *tx)
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi{
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi uint64_t obj;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi dmu_buf_t *db;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bptree_phys_t *bt;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi obj = dmu_object_alloc(os, DMU_OTN_UINT64_METADATA,
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi SPA_MAXBLOCKSIZE, DMU_OTN_UINT64_METADATA,
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi sizeof (bptree_phys_t), tx);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi /*
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * Bonus buffer contents are already initialized to 0, but for
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * readability we make it explicit.
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi */
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi VERIFY0(dmu_bonus_hold(os, obj, FTAG, &db));
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi dmu_buf_will_dirty(db, tx);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bt = db->db_data;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bt->bt_begin = 0;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bt->bt_end = 0;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bt->bt_bytes = 0;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bt->bt_comp = 0;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bt->bt_uncomp = 0;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi dmu_buf_rele(db, FTAG);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi return (obj);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi}
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchiint
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchibptree_free(objset_t *os, uint64_t obj, dmu_tx_t *tx)
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi{
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi dmu_buf_t *db;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bptree_phys_t *bt;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi VERIFY0(dmu_bonus_hold(os, obj, FTAG, &db));
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bt = db->db_data;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ASSERT3U(bt->bt_begin, ==, bt->bt_end);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ASSERT0(bt->bt_bytes);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ASSERT0(bt->bt_comp);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ASSERT0(bt->bt_uncomp);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi dmu_buf_rele(db, FTAG);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi return (dmu_object_free(os, obj, tx));
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi}
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchivoid
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchibptree_add(objset_t *os, uint64_t obj, blkptr_t *bp, uint64_t birth_txg,
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi uint64_t bytes, uint64_t comp, uint64_t uncomp, dmu_tx_t *tx)
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi{
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi dmu_buf_t *db;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bptree_phys_t *bt;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bptree_entry_phys_t bte;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi /*
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * bptree objects are in the pool mos, therefore they can only be
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * modified in syncing context. Furthermore, this is only modified
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi * by the sync thread, so no locking is necessary.
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi */
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ASSERT(dmu_tx_is_syncing(tx));
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi VERIFY0(dmu_bonus_hold(os, obj, FTAG, &db));
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bt = db->db_data;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bte.be_birth_txg = birth_txg;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bte.be_bp = *bp;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bzero(&bte.be_zb, sizeof (bte.be_zb));
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi dmu_write(os, obj, bt->bt_end * sizeof (bte), sizeof (bte), &bte, tx);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi dmu_buf_will_dirty(db, tx);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bt->bt_end++;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bt->bt_bytes += bytes;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bt->bt_comp += comp;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bt->bt_uncomp += uncomp;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi dmu_buf_rele(db, FTAG);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi}
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi/* ARGSUSED */
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchistatic int
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchibptree_visit_cb(spa_t *spa, zilog_t *zilog, const blkptr_t *bp, arc_buf_t *pbuf,
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi const zbookmark_t *zb, const dnode_phys_t *dnp, void *arg)
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi{
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi int err;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi struct bptree_args *ba = arg;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi if (bp == NULL)
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi return (0);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi err = ba->ba_func(ba->ba_arg, bp, ba->ba_tx);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi if (err == 0 && ba->ba_free) {
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ba->ba_phys->bt_bytes -= bp_get_dsize_sync(spa, bp);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ba->ba_phys->bt_comp -= BP_GET_PSIZE(bp);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ba->ba_phys->bt_uncomp -= BP_GET_UCSIZE(bp);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi }
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi return (err);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi}
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchiint
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchibptree_iterate(objset_t *os, uint64_t obj, boolean_t free, bptree_itor_t func,
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi void *arg, dmu_tx_t *tx)
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi{
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi int err;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi uint64_t i;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi dmu_buf_t *db;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi struct bptree_args ba;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ASSERT(!free || dmu_tx_is_syncing(tx));
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi err = dmu_bonus_hold(os, obj, FTAG, &db);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi if (err != 0)
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi return (err);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi if (free)
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi dmu_buf_will_dirty(db, tx);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ba.ba_phys = db->db_data;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ba.ba_free = free;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ba.ba_func = func;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ba.ba_arg = arg;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ba.ba_tx = tx;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi err = 0;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi for (i = ba.ba_phys->bt_begin; i < ba.ba_phys->bt_end; i++) {
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bptree_entry_phys_t bte;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ASSERT(!free || i == ba.ba_phys->bt_begin);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi err = dmu_read(os, obj, i * sizeof (bte), sizeof (bte),
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi &bte, DMU_READ_NO_PREFETCH);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi if (err != 0)
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi break;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi err = traverse_dataset_destroyed(os->os_spa, &bte.be_bp,
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bte.be_birth_txg, &bte.be_zb, TRAVERSE_POST,
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi bptree_visit_cb, &ba);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi if (free) {
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ASSERT(err == 0 || err == ERESTART);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi if (err != 0) {
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi /* save bookmark for future resume */
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ASSERT3U(bte.be_zb.zb_objset, ==,
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ZB_DESTROYED_OBJSET);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ASSERT0(bte.be_zb.zb_level);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi dmu_write(os, obj, i * sizeof (bte),
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi sizeof (bte), &bte, tx);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi break;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi } else {
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ba.ba_phys->bt_begin++;
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi (void) dmu_free_range(os, obj,
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi i * sizeof (bte), sizeof (bte), tx);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi }
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi }
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi }
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ASSERT(!free || err != 0 || ba.ba_phys->bt_begin == ba.ba_phys->bt_end);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi /* if all blocks are free there should be no used space */
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi if (ba.ba_phys->bt_begin == ba.ba_phys->bt_end) {
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ASSERT0(ba.ba_phys->bt_bytes);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ASSERT0(ba.ba_phys->bt_comp);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi ASSERT0(ba.ba_phys->bt_uncomp);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi }
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi dmu_buf_rele(db, FTAG);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi return (err);
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi}
d14abf155341d55053c76eeec58b787a456b753bRobert Mustacchi