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