1fa9e4066Sahrens /* 2fa9e4066Sahrens * CDDL HEADER START 3fa9e4066Sahrens * 4fa9e4066Sahrens * The contents of this file are subject to the terms of the 5ecc2d604Sbonwick * Common Development and Distribution License (the "License"). 6ecc2d604Sbonwick * You may not use this file except in compliance with the License. 7fa9e4066Sahrens * 8fa9e4066Sahrens * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9fa9e4066Sahrens * or http://www.opensolaris.org/os/licensing. 10fa9e4066Sahrens * See the License for the specific language governing permissions 11fa9e4066Sahrens * and limitations under the License. 12fa9e4066Sahrens * 13fa9e4066Sahrens * When distributing Covered Code, include this CDDL HEADER in each 14fa9e4066Sahrens * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15fa9e4066Sahrens * If applicable, add the following below this CDDL HEADER, with the 16fa9e4066Sahrens * fields enclosed by brackets "[]" replaced with your own identifying 17fa9e4066Sahrens * information: Portions Copyright [yyyy] [name of copyright owner] 18fa9e4066Sahrens * 19fa9e4066Sahrens * CDDL HEADER END 20fa9e4066Sahrens */ 21fa9e4066Sahrens /* 22d6e555bdSGeorge Wilson * Copyright 2009 Sun Microsystems, Inc. All rights reserved. 23fa9e4066Sahrens * Use is subject to license terms. 24fa9e4066Sahrens */ 25fa9e4066Sahrens 2601f55e48SGeorge Wilson /* 27*814dcd43SSerapheim Dimitropoulos * Copyright (c) 2012, 2019 by Delphix. All rights reserved. 2801f55e48SGeorge Wilson */ 2901f55e48SGeorge Wilson 30fa9e4066Sahrens #ifndef _SYS_SPACE_MAP_H 31fa9e4066Sahrens #define _SYS_SPACE_MAP_H 32fa9e4066Sahrens 33fa9e4066Sahrens #include <sys/avl.h> 340713e232SGeorge Wilson #include <sys/range_tree.h> 35fa9e4066Sahrens #include <sys/dmu.h> 36fa9e4066Sahrens 37fa9e4066Sahrens #ifdef __cplusplus 38fa9e4066Sahrens extern "C" { 39fa9e4066Sahrens #endif 40fa9e4066Sahrens 410713e232SGeorge Wilson /* 420713e232SGeorge Wilson * The size of the space map object has increased to include a histogram. 430713e232SGeorge Wilson * The SPACE_MAP_SIZE_V0 designates the original size and is used to 440713e232SGeorge Wilson * maintain backward compatibility. 450713e232SGeorge Wilson */ 460713e232SGeorge Wilson #define SPACE_MAP_SIZE_V0 (3 * sizeof (uint64_t)) 472e4c9986SGeorge Wilson #define SPACE_MAP_HISTOGRAM_SIZE 32 480713e232SGeorge Wilson 490713e232SGeorge Wilson /* 500713e232SGeorge Wilson * The space_map_phys is the on-disk representation of the space map. 510713e232SGeorge Wilson * Consumers of space maps should never reference any of the members of this 520713e232SGeorge Wilson * structure directly. These members may only be updated in syncing context. 530713e232SGeorge Wilson * 540713e232SGeorge Wilson * Note the smp_object is no longer used but remains in the structure 550713e232SGeorge Wilson * for backward compatibility. 560713e232SGeorge Wilson */ 570713e232SGeorge Wilson typedef struct space_map_phys { 58555d674dSSerapheim Dimitropoulos /* object number: not needed but kept for backwards compatibility */ 59555d674dSSerapheim Dimitropoulos uint64_t smp_object; 60555d674dSSerapheim Dimitropoulos 61555d674dSSerapheim Dimitropoulos /* length of the object in bytes */ 62555d674dSSerapheim Dimitropoulos uint64_t smp_length; 63555d674dSSerapheim Dimitropoulos 64555d674dSSerapheim Dimitropoulos /* space allocated from the map */ 65555d674dSSerapheim Dimitropoulos int64_t smp_alloc; 66555d674dSSerapheim Dimitropoulos 67555d674dSSerapheim Dimitropoulos /* reserved */ 68555d674dSSerapheim Dimitropoulos uint64_t smp_pad[5]; 690713e232SGeorge Wilson 700713e232SGeorge Wilson /* 710713e232SGeorge Wilson * The smp_histogram maintains a histogram of free regions. Each 720713e232SGeorge Wilson * bucket, smp_histogram[i], contains the number of free regions 730713e232SGeorge Wilson * whose size is: 740713e232SGeorge Wilson * 2^(i+sm_shift) <= size of free region in bytes < 2^(i+sm_shift+1) 75*814dcd43SSerapheim Dimitropoulos * 76*814dcd43SSerapheim Dimitropoulos * Note that, if log space map feature is enabled, histograms of 77*814dcd43SSerapheim Dimitropoulos * space maps that belong to metaslabs will take into account any 78*814dcd43SSerapheim Dimitropoulos * unflushed changes for their metaslabs, even though the actual 79*814dcd43SSerapheim Dimitropoulos * space map doesn't have entries for these changes. 800713e232SGeorge Wilson */ 812e4c9986SGeorge Wilson uint64_t smp_histogram[SPACE_MAP_HISTOGRAM_SIZE]; 820713e232SGeorge Wilson } space_map_phys_t; 83ecc2d604Sbonwick 840713e232SGeorge Wilson /* 850713e232SGeorge Wilson * The space map object defines a region of space, its size, how much is 860713e232SGeorge Wilson * allocated, and the on-disk object that stores this information. 870713e232SGeorge Wilson * Consumers of space maps may only access the members of this structure. 885cabbc6bSPrashanth Sreenivasa * 895cabbc6bSPrashanth Sreenivasa * Note: the space_map may not be accessed concurrently; consumers 905cabbc6bSPrashanth Sreenivasa * must provide external locking if required. 910713e232SGeorge Wilson */ 92fa9e4066Sahrens typedef struct space_map { 93ecc2d604Sbonwick uint64_t sm_start; /* start of map */ 94ecc2d604Sbonwick uint64_t sm_size; /* size of map */ 95ecc2d604Sbonwick uint8_t sm_shift; /* unit shift */ 960713e232SGeorge Wilson objset_t *sm_os; /* objset for this map */ 970713e232SGeorge Wilson uint64_t sm_object; /* object id for this map */ 980713e232SGeorge Wilson uint32_t sm_blksz; /* block size for space map */ 990713e232SGeorge Wilson dmu_buf_t *sm_dbuf; /* space_map_phys_t dbuf */ 1000713e232SGeorge Wilson space_map_phys_t *sm_phys; /* on-disk space map */ 101fa9e4066Sahrens } space_map_t; 102fa9e4066Sahrens 103fa9e4066Sahrens /* 104fa9e4066Sahrens * debug entry 105fa9e4066Sahrens * 10617f11284SSerapheim Dimitropoulos * 2 2 10 50 10717f11284SSerapheim Dimitropoulos * +-----+-----+------------+----------------------------------+ 10817f11284SSerapheim Dimitropoulos * | 1 0 | act | syncpass | txg (lower bits) | 10917f11284SSerapheim Dimitropoulos * +-----+-----+------------+----------------------------------+ 11017f11284SSerapheim Dimitropoulos * 63 62 61 60 59 50 49 0 111fa9e4066Sahrens * 112fa9e4066Sahrens * 11317f11284SSerapheim Dimitropoulos * one-word entry 114fa9e4066Sahrens * 115fa9e4066Sahrens * 1 47 1 15 11617f11284SSerapheim Dimitropoulos * +-----------------------------------------------------------+ 117fa9e4066Sahrens * | 0 | offset (sm_shift units) | type | run | 11817f11284SSerapheim Dimitropoulos * +-----------------------------------------------------------+ 11917f11284SSerapheim Dimitropoulos * 63 62 16 15 14 0 12017f11284SSerapheim Dimitropoulos * 12117f11284SSerapheim Dimitropoulos * 12217f11284SSerapheim Dimitropoulos * two-word entry 12317f11284SSerapheim Dimitropoulos * 12417f11284SSerapheim Dimitropoulos * 2 2 36 24 12517f11284SSerapheim Dimitropoulos * +-----+-----+---------------------------+-------------------+ 12617f11284SSerapheim Dimitropoulos * | 1 1 | pad | run | vdev | 12717f11284SSerapheim Dimitropoulos * +-----+-----+---------------------------+-------------------+ 12817f11284SSerapheim Dimitropoulos * 63 62 61 60 59 24 23 0 12917f11284SSerapheim Dimitropoulos * 13017f11284SSerapheim Dimitropoulos * 1 63 13117f11284SSerapheim Dimitropoulos * +------+----------------------------------------------------+ 13217f11284SSerapheim Dimitropoulos * | type | offset | 13317f11284SSerapheim Dimitropoulos * +------+----------------------------------------------------+ 13417f11284SSerapheim Dimitropoulos * 63 62 0 13517f11284SSerapheim Dimitropoulos * 13617f11284SSerapheim Dimitropoulos * Note that a two-word entry will not strandle a block boundary. 13717f11284SSerapheim Dimitropoulos * If necessary, the last word of a block will be padded with a 13817f11284SSerapheim Dimitropoulos * debug entry (with act = syncpass = txg = 0). 139fa9e4066Sahrens */ 140fa9e4066Sahrens 14117f11284SSerapheim Dimitropoulos typedef enum { 14217f11284SSerapheim Dimitropoulos SM_ALLOC, 14317f11284SSerapheim Dimitropoulos SM_FREE 14417f11284SSerapheim Dimitropoulos } maptype_t; 14517f11284SSerapheim Dimitropoulos 14617f11284SSerapheim Dimitropoulos typedef struct space_map_entry { 14717f11284SSerapheim Dimitropoulos maptype_t sme_type; 14817f11284SSerapheim Dimitropoulos uint32_t sme_vdev; /* max is 2^24-1; SM_NO_VDEVID if not present */ 14917f11284SSerapheim Dimitropoulos uint64_t sme_offset; /* max is 2^63-1; units of sm_shift */ 15017f11284SSerapheim Dimitropoulos uint64_t sme_run; /* max is 2^36; units of sm_shift */ 15117f11284SSerapheim Dimitropoulos } space_map_entry_t; 15217f11284SSerapheim Dimitropoulos 15317f11284SSerapheim Dimitropoulos #define SM_NO_VDEVID (1 << SPA_VDEVBITS) 154fa9e4066Sahrens 15517f11284SSerapheim Dimitropoulos /* one-word entry constants */ 15617f11284SSerapheim Dimitropoulos #define SM_DEBUG_PREFIX 2 15717f11284SSerapheim Dimitropoulos #define SM_OFFSET_BITS 47 15817f11284SSerapheim Dimitropoulos #define SM_RUN_BITS 15 159fa9e4066Sahrens 16017f11284SSerapheim Dimitropoulos /* two-word entry constants */ 16117f11284SSerapheim Dimitropoulos #define SM2_PREFIX 3 16217f11284SSerapheim Dimitropoulos #define SM2_OFFSET_BITS 63 16317f11284SSerapheim Dimitropoulos #define SM2_RUN_BITS 36 16417f11284SSerapheim Dimitropoulos 16517f11284SSerapheim Dimitropoulos #define SM_PREFIX_DECODE(x) BF64_DECODE(x, 62, 2) 16617f11284SSerapheim Dimitropoulos #define SM_PREFIX_ENCODE(x) BF64_ENCODE(x, 62, 2) 16717f11284SSerapheim Dimitropoulos 16817f11284SSerapheim Dimitropoulos #define SM_DEBUG_ACTION_DECODE(x) BF64_DECODE(x, 60, 2) 16917f11284SSerapheim Dimitropoulos #define SM_DEBUG_ACTION_ENCODE(x) BF64_ENCODE(x, 60, 2) 170fa9e4066Sahrens #define SM_DEBUG_SYNCPASS_DECODE(x) BF64_DECODE(x, 50, 10) 171fa9e4066Sahrens #define SM_DEBUG_SYNCPASS_ENCODE(x) BF64_ENCODE(x, 50, 10) 172fa9e4066Sahrens #define SM_DEBUG_TXG_DECODE(x) BF64_DECODE(x, 0, 50) 173fa9e4066Sahrens #define SM_DEBUG_TXG_ENCODE(x) BF64_ENCODE(x, 0, 50) 174fa9e4066Sahrens 17517f11284SSerapheim Dimitropoulos #define SM_OFFSET_DECODE(x) BF64_DECODE(x, 16, SM_OFFSET_BITS) 17617f11284SSerapheim Dimitropoulos #define SM_OFFSET_ENCODE(x) BF64_ENCODE(x, 16, SM_OFFSET_BITS) 17717f11284SSerapheim Dimitropoulos #define SM_TYPE_DECODE(x) BF64_DECODE(x, 15, 1) 17817f11284SSerapheim Dimitropoulos #define SM_TYPE_ENCODE(x) BF64_ENCODE(x, 15, 1) 17917f11284SSerapheim Dimitropoulos #define SM_RUN_DECODE(x) (BF64_DECODE(x, 0, SM_RUN_BITS) + 1) 18017f11284SSerapheim Dimitropoulos #define SM_RUN_ENCODE(x) BF64_ENCODE((x) - 1, 0, SM_RUN_BITS) 18117f11284SSerapheim Dimitropoulos #define SM_RUN_MAX SM_RUN_DECODE(~0ULL) 18217f11284SSerapheim Dimitropoulos #define SM_OFFSET_MAX SM_OFFSET_DECODE(~0ULL) 18317f11284SSerapheim Dimitropoulos 18417f11284SSerapheim Dimitropoulos #define SM2_RUN_DECODE(x) (BF64_DECODE(x, SPA_VDEVBITS, SM2_RUN_BITS) + 1) 18517f11284SSerapheim Dimitropoulos #define SM2_RUN_ENCODE(x) BF64_ENCODE((x) - 1, SPA_VDEVBITS, SM2_RUN_BITS) 18617f11284SSerapheim Dimitropoulos #define SM2_VDEV_DECODE(x) BF64_DECODE(x, 0, SPA_VDEVBITS) 18717f11284SSerapheim Dimitropoulos #define SM2_VDEV_ENCODE(x) BF64_ENCODE(x, 0, SPA_VDEVBITS) 18817f11284SSerapheim Dimitropoulos #define SM2_TYPE_DECODE(x) BF64_DECODE(x, SM2_OFFSET_BITS, 1) 18917f11284SSerapheim Dimitropoulos #define SM2_TYPE_ENCODE(x) BF64_ENCODE(x, SM2_OFFSET_BITS, 1) 19017f11284SSerapheim Dimitropoulos #define SM2_OFFSET_DECODE(x) BF64_DECODE(x, 0, SM2_OFFSET_BITS) 19117f11284SSerapheim Dimitropoulos #define SM2_OFFSET_ENCODE(x) BF64_ENCODE(x, 0, SM2_OFFSET_BITS) 19217f11284SSerapheim Dimitropoulos #define SM2_RUN_MAX SM2_RUN_DECODE(~0ULL) 19317f11284SSerapheim Dimitropoulos #define SM2_OFFSET_MAX SM2_OFFSET_DECODE(~0ULL) 19417f11284SSerapheim Dimitropoulos 19517f11284SSerapheim Dimitropoulos boolean_t sm_entry_is_debug(uint64_t e); 19617f11284SSerapheim Dimitropoulos boolean_t sm_entry_is_single_word(uint64_t e); 19717f11284SSerapheim Dimitropoulos boolean_t sm_entry_is_double_word(uint64_t e); 19817f11284SSerapheim Dimitropoulos 19917f11284SSerapheim Dimitropoulos typedef int (*sm_cb_t)(space_map_entry_t *sme, void *arg); 2005cabbc6bSPrashanth Sreenivasa 2010713e232SGeorge Wilson int space_map_load(space_map_t *sm, range_tree_t *rt, maptype_t maptype); 202555d674dSSerapheim Dimitropoulos int space_map_load_length(space_map_t *sm, range_tree_t *rt, maptype_t maptype, 203555d674dSSerapheim Dimitropoulos uint64_t length); 204555d674dSSerapheim Dimitropoulos int space_map_iterate(space_map_t *sm, uint64_t length, 205555d674dSSerapheim Dimitropoulos sm_cb_t callback, void *arg); 20686714001SSerapheim Dimitropoulos int space_map_incremental_destroy(space_map_t *sm, sm_cb_t callback, void *arg, 20786714001SSerapheim Dimitropoulos dmu_tx_t *tx); 2080713e232SGeorge Wilson 209555d674dSSerapheim Dimitropoulos boolean_t space_map_histogram_verify(space_map_t *sm, range_tree_t *rt); 2100713e232SGeorge Wilson void space_map_histogram_clear(space_map_t *sm); 2110713e232SGeorge Wilson void space_map_histogram_add(space_map_t *sm, range_tree_t *rt, 2120713e232SGeorge Wilson dmu_tx_t *tx); 2130713e232SGeorge Wilson 2140713e232SGeorge Wilson uint64_t space_map_object(space_map_t *sm); 215555d674dSSerapheim Dimitropoulos int64_t space_map_allocated(space_map_t *sm); 2160713e232SGeorge Wilson uint64_t space_map_length(space_map_t *sm); 217*814dcd43SSerapheim Dimitropoulos uint64_t space_map_entries(space_map_t *sm, range_tree_t *rt); 218*814dcd43SSerapheim Dimitropoulos uint64_t space_map_nblocks(space_map_t *sm); 2190713e232SGeorge Wilson 2200713e232SGeorge Wilson void space_map_write(space_map_t *sm, range_tree_t *rt, maptype_t maptype, 22117f11284SSerapheim Dimitropoulos uint64_t vdev_id, dmu_tx_t *tx); 22217f11284SSerapheim Dimitropoulos uint64_t space_map_estimate_optimal_size(space_map_t *sm, range_tree_t *rt, 22317f11284SSerapheim Dimitropoulos uint64_t vdev_id); 22486714001SSerapheim Dimitropoulos void space_map_truncate(space_map_t *sm, int blocksize, dmu_tx_t *tx); 22586714001SSerapheim Dimitropoulos uint64_t space_map_alloc(objset_t *os, int blocksize, dmu_tx_t *tx); 2260713e232SGeorge Wilson void space_map_free(space_map_t *sm, dmu_tx_t *tx); 2275cabbc6bSPrashanth Sreenivasa void space_map_free_obj(objset_t *os, uint64_t smobj, dmu_tx_t *tx); 2280713e232SGeorge Wilson 2290713e232SGeorge Wilson int space_map_open(space_map_t **smp, objset_t *os, uint64_t object, 2305cabbc6bSPrashanth Sreenivasa uint64_t start, uint64_t size, uint8_t shift); 2310713e232SGeorge Wilson void space_map_close(space_map_t *sm); 2320713e232SGeorge Wilson 233fa9e4066Sahrens #ifdef __cplusplus 234fa9e4066Sahrens } 235fa9e4066Sahrens #endif 236fa9e4066Sahrens 237fa9e4066Sahrens #endif /* _SYS_SPACE_MAP_H */ 238