10713e232SGeorge Wilson /*
20713e232SGeorge Wilson * CDDL HEADER START
30713e232SGeorge Wilson *
40713e232SGeorge Wilson * The contents of this file are subject to the terms of the
50713e232SGeorge Wilson * Common Development and Distribution License (the "License").
60713e232SGeorge Wilson * You may not use this file except in compliance with the License.
70713e232SGeorge Wilson *
80713e232SGeorge Wilson * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
90713e232SGeorge Wilson * or http://www.opensolaris.org/os/licensing.
100713e232SGeorge Wilson * See the License for the specific language governing permissions
110713e232SGeorge Wilson * and limitations under the License.
120713e232SGeorge Wilson *
130713e232SGeorge Wilson * When distributing Covered Code, include this CDDL HEADER in each
140713e232SGeorge Wilson * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
150713e232SGeorge Wilson * If applicable, add the following below this CDDL HEADER, with the
160713e232SGeorge Wilson * fields enclosed by brackets "[]" replaced with your own identifying
170713e232SGeorge Wilson * information: Portions Copyright [yyyy] [name of copyright owner]
180713e232SGeorge Wilson *
190713e232SGeorge Wilson * CDDL HEADER END
200713e232SGeorge Wilson */
210713e232SGeorge Wilson /*
220713e232SGeorge Wilson * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
230713e232SGeorge Wilson * Use is subject to license terms.
240713e232SGeorge Wilson */
250713e232SGeorge Wilson /*
26*4d7988d6SPaul Dagnelie * Copyright (c) 2013, 2019 by Delphix. All rights reserved.
270713e232SGeorge Wilson */
280713e232SGeorge Wilson
290713e232SGeorge Wilson #include <sys/zfs_context.h>
300713e232SGeorge Wilson #include <sys/range_tree.h>
310713e232SGeorge Wilson #include <sys/space_reftree.h>
320713e232SGeorge Wilson
330713e232SGeorge Wilson /*
340713e232SGeorge Wilson * Space reference trees.
350713e232SGeorge Wilson *
360713e232SGeorge Wilson * A range tree is a collection of integers. Every integer is either
370713e232SGeorge Wilson * in the tree, or it's not. A space reference tree generalizes
380713e232SGeorge Wilson * the idea: it allows its members to have arbitrary reference counts,
390713e232SGeorge Wilson * as opposed to the implicit reference count of 0 or 1 in a range tree.
400713e232SGeorge Wilson * This representation comes in handy when computing the union or
410713e232SGeorge Wilson * intersection of multiple space maps. For example, the union of
420713e232SGeorge Wilson * N range trees is the subset of the reference tree with refcnt >= 1.
430713e232SGeorge Wilson * The intersection of N range trees is the subset with refcnt >= N.
440713e232SGeorge Wilson *
450713e232SGeorge Wilson * [It's very much like a Fourier transform. Unions and intersections
460713e232SGeorge Wilson * are hard to perform in the 'range tree domain', so we convert the trees
470713e232SGeorge Wilson * into the 'reference count domain', where it's trivial, then invert.]
480713e232SGeorge Wilson *
490713e232SGeorge Wilson * vdev_dtl_reassess() uses computations of this form to determine
500713e232SGeorge Wilson * DTL_MISSING and DTL_OUTAGE for interior vdevs -- e.g. a RAID-Z vdev
510713e232SGeorge Wilson * has an outage wherever refcnt >= vdev_nparity + 1, and a mirror vdev
520713e232SGeorge Wilson * has an outage wherever refcnt >= vdev_children.
530713e232SGeorge Wilson */
540713e232SGeorge Wilson static int
space_reftree_compare(const void * x1,const void * x2)550713e232SGeorge Wilson space_reftree_compare(const void *x1, const void *x2)
560713e232SGeorge Wilson {
57c4ab0d3fSGvozden Neskovic const space_ref_t *sr1 = (const space_ref_t *)x1;
58c4ab0d3fSGvozden Neskovic const space_ref_t *sr2 = (const space_ref_t *)x2;
590713e232SGeorge Wilson
60*4d7988d6SPaul Dagnelie int cmp = TREE_CMP(sr1->sr_offset, sr2->sr_offset);
61c4ab0d3fSGvozden Neskovic if (likely(cmp))
62c4ab0d3fSGvozden Neskovic return (cmp);
630713e232SGeorge Wilson
64*4d7988d6SPaul Dagnelie return (TREE_PCMP(sr1, sr2));
650713e232SGeorge Wilson }
660713e232SGeorge Wilson
670713e232SGeorge Wilson void
space_reftree_create(avl_tree_t * t)680713e232SGeorge Wilson space_reftree_create(avl_tree_t *t)
690713e232SGeorge Wilson {
700713e232SGeorge Wilson avl_create(t, space_reftree_compare,
710713e232SGeorge Wilson sizeof (space_ref_t), offsetof(space_ref_t, sr_node));
720713e232SGeorge Wilson }
730713e232SGeorge Wilson
740713e232SGeorge Wilson void
space_reftree_destroy(avl_tree_t * t)750713e232SGeorge Wilson space_reftree_destroy(avl_tree_t *t)
760713e232SGeorge Wilson {
770713e232SGeorge Wilson space_ref_t *sr;
780713e232SGeorge Wilson void *cookie = NULL;
790713e232SGeorge Wilson
800713e232SGeorge Wilson while ((sr = avl_destroy_nodes(t, &cookie)) != NULL)
810713e232SGeorge Wilson kmem_free(sr, sizeof (*sr));
820713e232SGeorge Wilson
830713e232SGeorge Wilson avl_destroy(t);
840713e232SGeorge Wilson }
850713e232SGeorge Wilson
860713e232SGeorge Wilson static void
space_reftree_add_node(avl_tree_t * t,uint64_t offset,int64_t refcnt)870713e232SGeorge Wilson space_reftree_add_node(avl_tree_t *t, uint64_t offset, int64_t refcnt)
880713e232SGeorge Wilson {
890713e232SGeorge Wilson space_ref_t *sr;
900713e232SGeorge Wilson
910713e232SGeorge Wilson sr = kmem_alloc(sizeof (*sr), KM_SLEEP);
920713e232SGeorge Wilson sr->sr_offset = offset;
930713e232SGeorge Wilson sr->sr_refcnt = refcnt;
940713e232SGeorge Wilson
950713e232SGeorge Wilson avl_add(t, sr);
960713e232SGeorge Wilson }
970713e232SGeorge Wilson
980713e232SGeorge Wilson void
space_reftree_add_seg(avl_tree_t * t,uint64_t start,uint64_t end,int64_t refcnt)990713e232SGeorge Wilson space_reftree_add_seg(avl_tree_t *t, uint64_t start, uint64_t end,
1009a686fbcSPaul Dagnelie int64_t refcnt)
1010713e232SGeorge Wilson {
1020713e232SGeorge Wilson space_reftree_add_node(t, start, refcnt);
1030713e232SGeorge Wilson space_reftree_add_node(t, end, -refcnt);
1040713e232SGeorge Wilson }
1050713e232SGeorge Wilson
1060713e232SGeorge Wilson /*
1070713e232SGeorge Wilson * Convert (or add) a range tree into a reference tree.
1080713e232SGeorge Wilson */
1090713e232SGeorge Wilson void
space_reftree_add_map(avl_tree_t * t,range_tree_t * rt,int64_t refcnt)1100713e232SGeorge Wilson space_reftree_add_map(avl_tree_t *t, range_tree_t *rt, int64_t refcnt)
1110713e232SGeorge Wilson {
112*4d7988d6SPaul Dagnelie zfs_btree_index_t where;
1130713e232SGeorge Wilson
114*4d7988d6SPaul Dagnelie for (range_seg_t *rs = zfs_btree_first(&rt->rt_root, &where); rs; rs =
115*4d7988d6SPaul Dagnelie zfs_btree_next(&rt->rt_root, &where, &where)) {
116*4d7988d6SPaul Dagnelie space_reftree_add_seg(t, rs_get_start(rs, rt), rs_get_end(rs,
117*4d7988d6SPaul Dagnelie rt), refcnt);
118*4d7988d6SPaul Dagnelie }
1190713e232SGeorge Wilson }
1200713e232SGeorge Wilson
1210713e232SGeorge Wilson /*
1220713e232SGeorge Wilson * Convert a reference tree into a range tree. The range tree will contain
1230713e232SGeorge Wilson * all members of the reference tree for which refcnt >= minref.
1240713e232SGeorge Wilson */
1250713e232SGeorge Wilson void
space_reftree_generate_map(avl_tree_t * t,range_tree_t * rt,int64_t minref)1260713e232SGeorge Wilson space_reftree_generate_map(avl_tree_t *t, range_tree_t *rt, int64_t minref)
1270713e232SGeorge Wilson {
1280713e232SGeorge Wilson uint64_t start = -1ULL;
1290713e232SGeorge Wilson int64_t refcnt = 0;
1300713e232SGeorge Wilson space_ref_t *sr;
1310713e232SGeorge Wilson
1320713e232SGeorge Wilson range_tree_vacate(rt, NULL, NULL);
1330713e232SGeorge Wilson
1340713e232SGeorge Wilson for (sr = avl_first(t); sr != NULL; sr = AVL_NEXT(t, sr)) {
1350713e232SGeorge Wilson refcnt += sr->sr_refcnt;
1360713e232SGeorge Wilson if (refcnt >= minref) {
1370713e232SGeorge Wilson if (start == -1ULL) {
1380713e232SGeorge Wilson start = sr->sr_offset;
1390713e232SGeorge Wilson }
1400713e232SGeorge Wilson } else {
1410713e232SGeorge Wilson if (start != -1ULL) {
1420713e232SGeorge Wilson uint64_t end = sr->sr_offset;
1430713e232SGeorge Wilson ASSERT(start <= end);
1440713e232SGeorge Wilson if (end > start)
1450713e232SGeorge Wilson range_tree_add(rt, start, end - start);
1460713e232SGeorge Wilson start = -1ULL;
1470713e232SGeorge Wilson }
1480713e232SGeorge Wilson }
1490713e232SGeorge Wilson }
1500713e232SGeorge Wilson ASSERT(refcnt == 0);
1510713e232SGeorge Wilson ASSERT(start == -1ULL);
1520713e232SGeorge Wilson }
153