1eda14cbcSMatt Macy /*
2eda14cbcSMatt Macy * CDDL HEADER START
3eda14cbcSMatt Macy *
4eda14cbcSMatt Macy * The contents of this file are subject to the terms of the
5eda14cbcSMatt Macy * Common Development and Distribution License (the "License").
6eda14cbcSMatt Macy * You may not use this file except in compliance with the License.
7eda14cbcSMatt Macy *
8eda14cbcSMatt Macy * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9*271171e0SMartin Matuska * or https://opensource.org/licenses/CDDL-1.0.
10eda14cbcSMatt Macy * See the License for the specific language governing permissions
11eda14cbcSMatt Macy * and limitations under the License.
12eda14cbcSMatt Macy *
13eda14cbcSMatt Macy * When distributing Covered Code, include this CDDL HEADER in each
14eda14cbcSMatt Macy * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15eda14cbcSMatt Macy * If applicable, add the following below this CDDL HEADER, with the
16eda14cbcSMatt Macy * fields enclosed by brackets "[]" replaced with your own identifying
17eda14cbcSMatt Macy * information: Portions Copyright [yyyy] [name of copyright owner]
18eda14cbcSMatt Macy *
19eda14cbcSMatt Macy * CDDL HEADER END
20eda14cbcSMatt Macy */
21eda14cbcSMatt Macy /*
22eda14cbcSMatt Macy * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
23eda14cbcSMatt Macy * Use is subject to license terms.
24eda14cbcSMatt Macy */
25eda14cbcSMatt Macy /*
26eda14cbcSMatt Macy * Copyright (c) 2013, 2019 by Delphix. All rights reserved.
27eda14cbcSMatt Macy */
28eda14cbcSMatt Macy
29eda14cbcSMatt Macy #include <sys/zfs_context.h>
30eda14cbcSMatt Macy #include <sys/range_tree.h>
31eda14cbcSMatt Macy #include <sys/space_reftree.h>
32eda14cbcSMatt Macy
33eda14cbcSMatt Macy /*
34eda14cbcSMatt Macy * Space reference trees.
35eda14cbcSMatt Macy *
36eda14cbcSMatt Macy * A range tree is a collection of integers. Every integer is either
37eda14cbcSMatt Macy * in the tree, or it's not. A space reference tree generalizes
38eda14cbcSMatt Macy * the idea: it allows its members to have arbitrary reference counts,
39eda14cbcSMatt Macy * as opposed to the implicit reference count of 0 or 1 in a range tree.
40eda14cbcSMatt Macy * This representation comes in handy when computing the union or
41eda14cbcSMatt Macy * intersection of multiple space maps. For example, the union of
42eda14cbcSMatt Macy * N range trees is the subset of the reference tree with refcnt >= 1.
43eda14cbcSMatt Macy * The intersection of N range trees is the subset with refcnt >= N.
44eda14cbcSMatt Macy *
45eda14cbcSMatt Macy * [It's very much like a Fourier transform. Unions and intersections
46eda14cbcSMatt Macy * are hard to perform in the 'range tree domain', so we convert the trees
47eda14cbcSMatt Macy * into the 'reference count domain', where it's trivial, then invert.]
48eda14cbcSMatt Macy *
49eda14cbcSMatt Macy * vdev_dtl_reassess() uses computations of this form to determine
50eda14cbcSMatt Macy * DTL_MISSING and DTL_OUTAGE for interior vdevs -- e.g. a RAID-Z vdev
51eda14cbcSMatt Macy * has an outage wherever refcnt >= vdev_nparity + 1, and a mirror vdev
52eda14cbcSMatt Macy * has an outage wherever refcnt >= vdev_children.
53eda14cbcSMatt Macy */
54eda14cbcSMatt Macy static int
space_reftree_compare(const void * x1,const void * x2)55eda14cbcSMatt Macy space_reftree_compare(const void *x1, const void *x2)
56eda14cbcSMatt Macy {
57eda14cbcSMatt Macy const space_ref_t *sr1 = (const space_ref_t *)x1;
58eda14cbcSMatt Macy const space_ref_t *sr2 = (const space_ref_t *)x2;
59eda14cbcSMatt Macy
60eda14cbcSMatt Macy int cmp = TREE_CMP(sr1->sr_offset, sr2->sr_offset);
61eda14cbcSMatt Macy if (likely(cmp))
62eda14cbcSMatt Macy return (cmp);
63eda14cbcSMatt Macy
64eda14cbcSMatt Macy return (TREE_PCMP(sr1, sr2));
65eda14cbcSMatt Macy }
66eda14cbcSMatt Macy
67eda14cbcSMatt Macy void
space_reftree_create(avl_tree_t * t)68eda14cbcSMatt Macy space_reftree_create(avl_tree_t *t)
69eda14cbcSMatt Macy {
70eda14cbcSMatt Macy avl_create(t, space_reftree_compare,
71eda14cbcSMatt Macy sizeof (space_ref_t), offsetof(space_ref_t, sr_node));
72eda14cbcSMatt Macy }
73eda14cbcSMatt Macy
74eda14cbcSMatt Macy void
space_reftree_destroy(avl_tree_t * t)75eda14cbcSMatt Macy space_reftree_destroy(avl_tree_t *t)
76eda14cbcSMatt Macy {
77eda14cbcSMatt Macy space_ref_t *sr;
78eda14cbcSMatt Macy void *cookie = NULL;
79eda14cbcSMatt Macy
80eda14cbcSMatt Macy while ((sr = avl_destroy_nodes(t, &cookie)) != NULL)
81eda14cbcSMatt Macy kmem_free(sr, sizeof (*sr));
82eda14cbcSMatt Macy
83eda14cbcSMatt Macy avl_destroy(t);
84eda14cbcSMatt Macy }
85eda14cbcSMatt Macy
86eda14cbcSMatt Macy static void
space_reftree_add_node(avl_tree_t * t,uint64_t offset,int64_t refcnt)87eda14cbcSMatt Macy space_reftree_add_node(avl_tree_t *t, uint64_t offset, int64_t refcnt)
88eda14cbcSMatt Macy {
89eda14cbcSMatt Macy space_ref_t *sr;
90eda14cbcSMatt Macy
91eda14cbcSMatt Macy sr = kmem_alloc(sizeof (*sr), KM_SLEEP);
92eda14cbcSMatt Macy sr->sr_offset = offset;
93eda14cbcSMatt Macy sr->sr_refcnt = refcnt;
94eda14cbcSMatt Macy
95eda14cbcSMatt Macy avl_add(t, sr);
96eda14cbcSMatt Macy }
97eda14cbcSMatt Macy
98eda14cbcSMatt Macy void
space_reftree_add_seg(avl_tree_t * t,uint64_t start,uint64_t end,int64_t refcnt)99eda14cbcSMatt Macy space_reftree_add_seg(avl_tree_t *t, uint64_t start, uint64_t end,
100eda14cbcSMatt Macy int64_t refcnt)
101eda14cbcSMatt Macy {
102eda14cbcSMatt Macy space_reftree_add_node(t, start, refcnt);
103eda14cbcSMatt Macy space_reftree_add_node(t, end, -refcnt);
104eda14cbcSMatt Macy }
105eda14cbcSMatt Macy
106eda14cbcSMatt Macy /*
107eda14cbcSMatt Macy * Convert (or add) a range tree into a reference tree.
108eda14cbcSMatt Macy */
109eda14cbcSMatt Macy void
space_reftree_add_map(avl_tree_t * t,range_tree_t * rt,int64_t refcnt)110eda14cbcSMatt Macy space_reftree_add_map(avl_tree_t *t, range_tree_t *rt, int64_t refcnt)
111eda14cbcSMatt Macy {
112eda14cbcSMatt Macy zfs_btree_index_t where;
113eda14cbcSMatt Macy
114eda14cbcSMatt Macy for (range_seg_t *rs = zfs_btree_first(&rt->rt_root, &where); rs; rs =
115eda14cbcSMatt Macy zfs_btree_next(&rt->rt_root, &where, &where)) {
116eda14cbcSMatt Macy space_reftree_add_seg(t, rs_get_start(rs, rt), rs_get_end(rs,
117eda14cbcSMatt Macy rt), refcnt);
118eda14cbcSMatt Macy }
119eda14cbcSMatt Macy }
120eda14cbcSMatt Macy
121eda14cbcSMatt Macy /*
122eda14cbcSMatt Macy * Convert a reference tree into a range tree. The range tree will contain
123eda14cbcSMatt Macy * all members of the reference tree for which refcnt >= minref.
124eda14cbcSMatt Macy */
125eda14cbcSMatt Macy void
space_reftree_generate_map(avl_tree_t * t,range_tree_t * rt,int64_t minref)126eda14cbcSMatt Macy space_reftree_generate_map(avl_tree_t *t, range_tree_t *rt, int64_t minref)
127eda14cbcSMatt Macy {
128eda14cbcSMatt Macy uint64_t start = -1ULL;
129eda14cbcSMatt Macy int64_t refcnt = 0;
130eda14cbcSMatt Macy space_ref_t *sr;
131eda14cbcSMatt Macy
132eda14cbcSMatt Macy range_tree_vacate(rt, NULL, NULL);
133eda14cbcSMatt Macy
134eda14cbcSMatt Macy for (sr = avl_first(t); sr != NULL; sr = AVL_NEXT(t, sr)) {
135eda14cbcSMatt Macy refcnt += sr->sr_refcnt;
136eda14cbcSMatt Macy if (refcnt >= minref) {
137eda14cbcSMatt Macy if (start == -1ULL) {
138eda14cbcSMatt Macy start = sr->sr_offset;
139eda14cbcSMatt Macy }
140eda14cbcSMatt Macy } else {
141eda14cbcSMatt Macy if (start != -1ULL) {
142eda14cbcSMatt Macy uint64_t end = sr->sr_offset;
143eda14cbcSMatt Macy ASSERT(start <= end);
144eda14cbcSMatt Macy if (end > start)
145eda14cbcSMatt Macy range_tree_add(rt, start, end - start);
146eda14cbcSMatt Macy start = -1ULL;
147eda14cbcSMatt Macy }
148eda14cbcSMatt Macy }
149eda14cbcSMatt Macy }
150eda14cbcSMatt Macy ASSERT(refcnt == 0);
151eda14cbcSMatt Macy ASSERT(start == -1ULL);
152eda14cbcSMatt Macy }
153