svn commit: r258372 - in vendor-sys/illumos/dist/uts/common/fs/zfs: . sys
Andriy Gapon
avg at FreeBSD.org
Wed Nov 20 10:50:55 UTC 2013
Author: avg
Date: Wed Nov 20 10:50:54 2013
New Revision: 258372
URL: http://svnweb.freebsd.org/changeset/base/258372
Log:
fix a screw up in r258371
Pointyhat to: avg
Added:
vendor-sys/illumos/dist/uts/common/fs/zfs/space_reftree.c (contents, props changed)
vendor-sys/illumos/dist/uts/common/fs/zfs/sys/range_tree.h (contents, props changed)
Replaced:
vendor-sys/illumos/dist/uts/common/fs/zfs/range_tree.c (contents, props changed)
vendor-sys/illumos/dist/uts/common/fs/zfs/sys/space_reftree.h (contents, props changed)
Added: vendor-sys/illumos/dist/uts/common/fs/zfs/range_tree.c
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ vendor-sys/illumos/dist/uts/common/fs/zfs/range_tree.c Wed Nov 20 10:50:54 2013 (r258372)
@@ -0,0 +1,391 @@
+/*
+ * CDDL HEADER START
+ *
+ * The contents of this file are subject to the terms of the
+ * Common Development and Distribution License (the "License").
+ * You may not use this file except in compliance with the License.
+ *
+ * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+ * or http://www.opensolaris.org/os/licensing.
+ * See the License for the specific language governing permissions
+ * and limitations under the License.
+ *
+ * When distributing Covered Code, include this CDDL HEADER in each
+ * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+ * If applicable, add the following below this CDDL HEADER, with the
+ * fields enclosed by brackets "[]" replaced with your own identifying
+ * information: Portions Copyright [yyyy] [name of copyright owner]
+ *
+ * CDDL HEADER END
+ */
+/*
+ * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
+ * Use is subject to license terms.
+ */
+/*
+ * Copyright (c) 2013 by Delphix. All rights reserved.
+ */
+
+#include <sys/zfs_context.h>
+#include <sys/spa.h>
+#include <sys/dmu.h>
+#include <sys/dnode.h>
+#include <sys/zio.h>
+#include <sys/range_tree.h>
+
+static kmem_cache_t *range_seg_cache;
+
+void
+range_tree_init(void)
+{
+ ASSERT(range_seg_cache == NULL);
+ range_seg_cache = kmem_cache_create("range_seg_cache",
+ sizeof (range_seg_t), 0, NULL, NULL, NULL, NULL, NULL, 0);
+}
+
+void
+range_tree_fini(void)
+{
+ kmem_cache_destroy(range_seg_cache);
+ range_seg_cache = NULL;
+}
+
+void
+range_tree_stat_verify(range_tree_t *rt)
+{
+ range_seg_t *rs;
+ uint64_t hist[RANGE_TREE_HISTOGRAM_SIZE] = { 0 };
+ int i;
+
+ for (rs = avl_first(&rt->rt_root); rs != NULL;
+ rs = AVL_NEXT(&rt->rt_root, rs)) {
+ uint64_t size = rs->rs_end - rs->rs_start;
+ int idx = highbit(size) - 1;
+
+ hist[idx]++;
+ ASSERT3U(hist[idx], !=, 0);
+ }
+
+ for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++) {
+ if (hist[i] != rt->rt_histogram[i]) {
+ zfs_dbgmsg("i=%d, hist=%p, hist=%llu, rt_hist=%llu",
+ i, hist, hist[i], rt->rt_histogram[i]);
+ }
+ VERIFY3U(hist[i], ==, rt->rt_histogram[i]);
+ }
+}
+
+static void
+range_tree_stat_incr(range_tree_t *rt, range_seg_t *rs)
+{
+ uint64_t size = rs->rs_end - rs->rs_start;
+ int idx = highbit(size) - 1;
+
+ ASSERT3U(idx, <,
+ sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
+
+ ASSERT(MUTEX_HELD(rt->rt_lock));
+ rt->rt_histogram[idx]++;
+ ASSERT3U(rt->rt_histogram[idx], !=, 0);
+}
+
+static void
+range_tree_stat_decr(range_tree_t *rt, range_seg_t *rs)
+{
+ uint64_t size = rs->rs_end - rs->rs_start;
+ int idx = highbit(size) - 1;
+
+ ASSERT3U(idx, <,
+ sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
+
+ ASSERT(MUTEX_HELD(rt->rt_lock));
+ ASSERT3U(rt->rt_histogram[idx], !=, 0);
+ rt->rt_histogram[idx]--;
+}
+
+/*
+ * NOTE: caller is responsible for all locking.
+ */
+static int
+range_tree_seg_compare(const void *x1, const void *x2)
+{
+ const range_seg_t *r1 = x1;
+ const range_seg_t *r2 = x2;
+
+ if (r1->rs_start < r2->rs_start) {
+ if (r1->rs_end > r2->rs_start)
+ return (0);
+ return (-1);
+ }
+ if (r1->rs_start > r2->rs_start) {
+ if (r1->rs_start < r2->rs_end)
+ return (0);
+ return (1);
+ }
+ return (0);
+}
+
+range_tree_t *
+range_tree_create(range_tree_ops_t *ops, void *arg, kmutex_t *lp)
+{
+ range_tree_t *rt;
+
+ rt = kmem_zalloc(sizeof (range_tree_t), KM_SLEEP);
+
+ avl_create(&rt->rt_root, range_tree_seg_compare,
+ sizeof (range_seg_t), offsetof(range_seg_t, rs_node));
+
+ rt->rt_lock = lp;
+ rt->rt_ops = ops;
+ rt->rt_arg = arg;
+
+ if (rt->rt_ops != NULL)
+ rt->rt_ops->rtop_create(rt, rt->rt_arg);
+
+ return (rt);
+}
+
+void
+range_tree_destroy(range_tree_t *rt)
+{
+ VERIFY0(rt->rt_space);
+
+ if (rt->rt_ops != NULL)
+ rt->rt_ops->rtop_destroy(rt, rt->rt_arg);
+
+ avl_destroy(&rt->rt_root);
+ kmem_free(rt, sizeof (*rt));
+}
+
+void
+range_tree_add(void *arg, uint64_t start, uint64_t size)
+{
+ range_tree_t *rt = arg;
+ avl_index_t where;
+ range_seg_t rsearch, *rs_before, *rs_after, *rs;
+ uint64_t end = start + size;
+ boolean_t merge_before, merge_after;
+
+ ASSERT(MUTEX_HELD(rt->rt_lock));
+ VERIFY(size != 0);
+
+ rsearch.rs_start = start;
+ rsearch.rs_end = end;
+ rs = avl_find(&rt->rt_root, &rsearch, &where);
+
+ if (rs != NULL && rs->rs_start <= start && rs->rs_end >= end) {
+ zfs_panic_recover("zfs: allocating allocated segment"
+ "(offset=%llu size=%llu)\n",
+ (longlong_t)start, (longlong_t)size);
+ return;
+ }
+
+ /* Make sure we don't overlap with either of our neighbors */
+ VERIFY(rs == NULL);
+
+ rs_before = avl_nearest(&rt->rt_root, where, AVL_BEFORE);
+ rs_after = avl_nearest(&rt->rt_root, where, AVL_AFTER);
+
+ merge_before = (rs_before != NULL && rs_before->rs_end == start);
+ merge_after = (rs_after != NULL && rs_after->rs_start == end);
+
+ if (merge_before && merge_after) {
+ avl_remove(&rt->rt_root, rs_before);
+ if (rt->rt_ops != NULL) {
+ rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);
+ rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);
+ }
+
+ range_tree_stat_decr(rt, rs_before);
+ range_tree_stat_decr(rt, rs_after);
+
+ rs_after->rs_start = rs_before->rs_start;
+ kmem_cache_free(range_seg_cache, rs_before);
+ rs = rs_after;
+ } else if (merge_before) {
+ if (rt->rt_ops != NULL)
+ rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);
+
+ range_tree_stat_decr(rt, rs_before);
+
+ rs_before->rs_end = end;
+ rs = rs_before;
+ } else if (merge_after) {
+ if (rt->rt_ops != NULL)
+ rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);
+
+ range_tree_stat_decr(rt, rs_after);
+
+ rs_after->rs_start = start;
+ rs = rs_after;
+ } else {
+ rs = kmem_cache_alloc(range_seg_cache, KM_SLEEP);
+ rs->rs_start = start;
+ rs->rs_end = end;
+ avl_insert(&rt->rt_root, rs, where);
+ }
+
+ if (rt->rt_ops != NULL)
+ rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
+
+ range_tree_stat_incr(rt, rs);
+ rt->rt_space += size;
+}
+
+void
+range_tree_remove(void *arg, uint64_t start, uint64_t size)
+{
+ range_tree_t *rt = arg;
+ avl_index_t where;
+ range_seg_t rsearch, *rs, *newseg;
+ uint64_t end = start + size;
+ boolean_t left_over, right_over;
+
+ ASSERT(MUTEX_HELD(rt->rt_lock));
+ VERIFY3U(size, !=, 0);
+ VERIFY3U(size, <=, rt->rt_space);
+
+ rsearch.rs_start = start;
+ rsearch.rs_end = end;
+ rs = avl_find(&rt->rt_root, &rsearch, &where);
+
+ /* Make sure we completely overlap with someone */
+ if (rs == NULL) {
+ zfs_panic_recover("zfs: freeing free segment "
+ "(offset=%llu size=%llu)",
+ (longlong_t)start, (longlong_t)size);
+ return;
+ }
+ VERIFY3U(rs->rs_start, <=, start);
+ VERIFY3U(rs->rs_end, >=, end);
+
+ left_over = (rs->rs_start != start);
+ right_over = (rs->rs_end != end);
+
+ range_tree_stat_decr(rt, rs);
+
+ if (rt->rt_ops != NULL)
+ rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
+
+ if (left_over && right_over) {
+ newseg = kmem_cache_alloc(range_seg_cache, KM_SLEEP);
+ newseg->rs_start = end;
+ newseg->rs_end = rs->rs_end;
+ range_tree_stat_incr(rt, newseg);
+
+ rs->rs_end = start;
+
+ avl_insert_here(&rt->rt_root, newseg, rs, AVL_AFTER);
+ if (rt->rt_ops != NULL)
+ rt->rt_ops->rtop_add(rt, newseg, rt->rt_arg);
+ } else if (left_over) {
+ rs->rs_end = start;
+ } else if (right_over) {
+ rs->rs_start = end;
+ } else {
+ avl_remove(&rt->rt_root, rs);
+ kmem_cache_free(range_seg_cache, rs);
+ rs = NULL;
+ }
+
+ if (rs != NULL) {
+ range_tree_stat_incr(rt, rs);
+
+ if (rt->rt_ops != NULL)
+ rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
+ }
+
+ rt->rt_space -= size;
+}
+
+static range_seg_t *
+range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size,
+ avl_index_t *wherep)
+{
+ range_seg_t rsearch, *rs;
+ uint64_t end = start + size;
+
+ ASSERT(MUTEX_HELD(rt->rt_lock));
+ VERIFY(size != 0);
+
+ rsearch.rs_start = start;
+ rsearch.rs_end = end;
+ rs = avl_find(&rt->rt_root, &rsearch, wherep);
+
+ if (rs != NULL && rs->rs_start <= start && rs->rs_end >= end)
+ return (rs);
+ return (NULL);
+}
+
+void
+range_tree_verify(range_tree_t *rt, uint64_t off, uint64_t size)
+{
+ range_seg_t *rs;
+ avl_index_t where;
+
+ mutex_enter(rt->rt_lock);
+ rs = range_tree_find(rt, off, size, &where);
+ if (rs != NULL)
+ panic("freeing free block; rs=%p", (void *)rs);
+ mutex_exit(rt->rt_lock);
+}
+
+boolean_t
+range_tree_contains(range_tree_t *rt, uint64_t start, uint64_t size)
+{
+ avl_index_t where;
+
+ return (range_tree_find(rt, start, size, &where) != NULL);
+}
+
+void
+range_tree_swap(range_tree_t **rtsrc, range_tree_t **rtdst)
+{
+ range_tree_t *rt;
+
+ ASSERT(MUTEX_HELD((*rtsrc)->rt_lock));
+ ASSERT0(range_tree_space(*rtdst));
+ ASSERT0(avl_numnodes(&(*rtdst)->rt_root));
+
+ rt = *rtsrc;
+ *rtsrc = *rtdst;
+ *rtdst = rt;
+}
+
+void
+range_tree_vacate(range_tree_t *rt, range_tree_func_t *func, void *arg)
+{
+ range_seg_t *rs;
+ void *cookie = NULL;
+
+ ASSERT(MUTEX_HELD(rt->rt_lock));
+
+ if (rt->rt_ops != NULL)
+ rt->rt_ops->rtop_vacate(rt, rt->rt_arg);
+
+ while ((rs = avl_destroy_nodes(&rt->rt_root, &cookie)) != NULL) {
+ if (func != NULL)
+ func(arg, rs->rs_start, rs->rs_end - rs->rs_start);
+ kmem_cache_free(range_seg_cache, rs);
+ }
+
+ bzero(rt->rt_histogram, sizeof (rt->rt_histogram));
+ rt->rt_space = 0;
+}
+
+void
+range_tree_walk(range_tree_t *rt, range_tree_func_t *func, void *arg)
+{
+ range_seg_t *rs;
+
+ ASSERT(MUTEX_HELD(rt->rt_lock));
+
+ for (rs = avl_first(&rt->rt_root); rs; rs = AVL_NEXT(&rt->rt_root, rs))
+ func(arg, rs->rs_start, rs->rs_end - rs->rs_start);
+}
+
+uint64_t
+range_tree_space(range_tree_t *rt)
+{
+ return (rt->rt_space);
+}
Added: vendor-sys/illumos/dist/uts/common/fs/zfs/space_reftree.c
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ vendor-sys/illumos/dist/uts/common/fs/zfs/space_reftree.c Wed Nov 20 10:50:54 2013 (r258372)
@@ -0,0 +1,159 @@
+/*
+ * CDDL HEADER START
+ *
+ * The contents of this file are subject to the terms of the
+ * Common Development and Distribution License (the "License").
+ * You may not use this file except in compliance with the License.
+ *
+ * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+ * or http://www.opensolaris.org/os/licensing.
+ * See the License for the specific language governing permissions
+ * and limitations under the License.
+ *
+ * When distributing Covered Code, include this CDDL HEADER in each
+ * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+ * If applicable, add the following below this CDDL HEADER, with the
+ * fields enclosed by brackets "[]" replaced with your own identifying
+ * information: Portions Copyright [yyyy] [name of copyright owner]
+ *
+ * CDDL HEADER END
+ */
+/*
+ * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
+ * Use is subject to license terms.
+ */
+/*
+ * Copyright (c) 2013 by Delphix. All rights reserved.
+ */
+
+#include <sys/zfs_context.h>
+#include <sys/range_tree.h>
+#include <sys/space_reftree.h>
+
+/*
+ * Space reference trees.
+ *
+ * A range tree is a collection of integers. Every integer is either
+ * in the tree, or it's not. A space reference tree generalizes
+ * the idea: it allows its members to have arbitrary reference counts,
+ * as opposed to the implicit reference count of 0 or 1 in a range tree.
+ * This representation comes in handy when computing the union or
+ * intersection of multiple space maps. For example, the union of
+ * N range trees is the subset of the reference tree with refcnt >= 1.
+ * The intersection of N range trees is the subset with refcnt >= N.
+ *
+ * [It's very much like a Fourier transform. Unions and intersections
+ * are hard to perform in the 'range tree domain', so we convert the trees
+ * into the 'reference count domain', where it's trivial, then invert.]
+ *
+ * vdev_dtl_reassess() uses computations of this form to determine
+ * DTL_MISSING and DTL_OUTAGE for interior vdevs -- e.g. a RAID-Z vdev
+ * has an outage wherever refcnt >= vdev_nparity + 1, and a mirror vdev
+ * has an outage wherever refcnt >= vdev_children.
+ */
+static int
+space_reftree_compare(const void *x1, const void *x2)
+{
+ const space_ref_t *sr1 = x1;
+ const space_ref_t *sr2 = x2;
+
+ if (sr1->sr_offset < sr2->sr_offset)
+ return (-1);
+ if (sr1->sr_offset > sr2->sr_offset)
+ return (1);
+
+ if (sr1 < sr2)
+ return (-1);
+ if (sr1 > sr2)
+ return (1);
+
+ return (0);
+}
+
+void
+space_reftree_create(avl_tree_t *t)
+{
+ avl_create(t, space_reftree_compare,
+ sizeof (space_ref_t), offsetof(space_ref_t, sr_node));
+}
+
+void
+space_reftree_destroy(avl_tree_t *t)
+{
+ space_ref_t *sr;
+ void *cookie = NULL;
+
+ while ((sr = avl_destroy_nodes(t, &cookie)) != NULL)
+ kmem_free(sr, sizeof (*sr));
+
+ avl_destroy(t);
+}
+
+static void
+space_reftree_add_node(avl_tree_t *t, uint64_t offset, int64_t refcnt)
+{
+ space_ref_t *sr;
+
+ sr = kmem_alloc(sizeof (*sr), KM_SLEEP);
+ sr->sr_offset = offset;
+ sr->sr_refcnt = refcnt;
+
+ avl_add(t, sr);
+}
+
+void
+space_reftree_add_seg(avl_tree_t *t, uint64_t start, uint64_t end,
+ int64_t refcnt)
+{
+ space_reftree_add_node(t, start, refcnt);
+ space_reftree_add_node(t, end, -refcnt);
+}
+
+/*
+ * Convert (or add) a range tree into a reference tree.
+ */
+void
+space_reftree_add_map(avl_tree_t *t, range_tree_t *rt, int64_t refcnt)
+{
+ range_seg_t *rs;
+
+ ASSERT(MUTEX_HELD(rt->rt_lock));
+
+ for (rs = avl_first(&rt->rt_root); rs; rs = AVL_NEXT(&rt->rt_root, rs))
+ space_reftree_add_seg(t, rs->rs_start, rs->rs_end, refcnt);
+}
+
+/*
+ * Convert a reference tree into a range tree. The range tree will contain
+ * all members of the reference tree for which refcnt >= minref.
+ */
+void
+space_reftree_generate_map(avl_tree_t *t, range_tree_t *rt, int64_t minref)
+{
+ uint64_t start = -1ULL;
+ int64_t refcnt = 0;
+ space_ref_t *sr;
+
+ ASSERT(MUTEX_HELD(rt->rt_lock));
+
+ range_tree_vacate(rt, NULL, NULL);
+
+ for (sr = avl_first(t); sr != NULL; sr = AVL_NEXT(t, sr)) {
+ refcnt += sr->sr_refcnt;
+ if (refcnt >= minref) {
+ if (start == -1ULL) {
+ start = sr->sr_offset;
+ }
+ } else {
+ if (start != -1ULL) {
+ uint64_t end = sr->sr_offset;
+ ASSERT(start <= end);
+ if (end > start)
+ range_tree_add(rt, start, end - start);
+ start = -1ULL;
+ }
+ }
+ }
+ ASSERT(refcnt == 0);
+ ASSERT(start == -1ULL);
+}
Added: vendor-sys/illumos/dist/uts/common/fs/zfs/sys/range_tree.h
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ vendor-sys/illumos/dist/uts/common/fs/zfs/sys/range_tree.h Wed Nov 20 10:50:54 2013 (r258372)
@@ -0,0 +1,96 @@
+/*
+ * CDDL HEADER START
+ *
+ * The contents of this file are subject to the terms of the
+ * Common Development and Distribution License (the "License").
+ * You may not use this file except in compliance with the License.
+ *
+ * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+ * or http://www.opensolaris.org/os/licensing.
+ * See the License for the specific language governing permissions
+ * and limitations under the License.
+ *
+ * When distributing Covered Code, include this CDDL HEADER in each
+ * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+ * If applicable, add the following below this CDDL HEADER, with the
+ * fields enclosed by brackets "[]" replaced with your own identifying
+ * information: Portions Copyright [yyyy] [name of copyright owner]
+ *
+ * CDDL HEADER END
+ */
+/*
+ * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
+ * Use is subject to license terms.
+ */
+
+/*
+ * Copyright (c) 2013 by Delphix. All rights reserved.
+ */
+
+#ifndef _SYS_RANGE_TREE_H
+#define _SYS_RANGE_TREE_H
+
+#include <sys/avl.h>
+#include <sys/dmu.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define RANGE_TREE_HISTOGRAM_SIZE 64
+
+typedef struct range_tree_ops range_tree_ops_t;
+
+typedef struct range_tree {
+ avl_tree_t rt_root; /* offset-ordered segment AVL tree */
+ uint64_t rt_space; /* sum of all segments in the map */
+ range_tree_ops_t *rt_ops;
+ void *rt_arg;
+
+ /*
+ * The rt_histogram maintains a histogram of ranges. Each bucket,
+ * rt_histogram[i], contains the number of ranges whose size is:
+ * 2^i <= size of range in bytes < 2^(i+1)
+ */
+ uint64_t rt_histogram[RANGE_TREE_HISTOGRAM_SIZE];
+ kmutex_t *rt_lock; /* pointer to lock that protects map */
+} range_tree_t;
+
+typedef struct range_seg {
+ avl_node_t rs_node; /* AVL node */
+ avl_node_t rs_pp_node; /* AVL picker-private node */
+ uint64_t rs_start; /* starting offset of this segment */
+ uint64_t rs_end; /* ending offset (non-inclusive) */
+} range_seg_t;
+
+struct range_tree_ops {
+ void (*rtop_create)(range_tree_t *rt, void *arg);
+ void (*rtop_destroy)(range_tree_t *rt, void *arg);
+ void (*rtop_add)(range_tree_t *rt, range_seg_t *rs, void *arg);
+ void (*rtop_remove)(range_tree_t *rt, range_seg_t *rs, void *arg);
+ void (*rtop_vacate)(range_tree_t *rt, void *arg);
+};
+
+typedef void range_tree_func_t(void *arg, uint64_t start, uint64_t size);
+
+void range_tree_init(void);
+void range_tree_fini(void);
+range_tree_t *range_tree_create(range_tree_ops_t *ops, void *arg, kmutex_t *lp);
+void range_tree_destroy(range_tree_t *rt);
+boolean_t range_tree_contains(range_tree_t *rt, uint64_t start, uint64_t size);
+uint64_t range_tree_space(range_tree_t *rt);
+void range_tree_verify(range_tree_t *rt, uint64_t start, uint64_t size);
+void range_tree_swap(range_tree_t **rtsrc, range_tree_t **rtdst);
+void range_tree_stat_verify(range_tree_t *rt);
+
+void range_tree_add(void *arg, uint64_t start, uint64_t size);
+void range_tree_remove(void *arg, uint64_t start, uint64_t size);
+
+void range_tree_vacate(range_tree_t *rt, range_tree_func_t *func, void *arg);
+void range_tree_walk(range_tree_t *rt, range_tree_func_t *func, void *arg);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _SYS_RANGE_TREE_H */
Added: vendor-sys/illumos/dist/uts/common/fs/zfs/sys/space_reftree.h
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ vendor-sys/illumos/dist/uts/common/fs/zfs/sys/space_reftree.h Wed Nov 20 10:50:54 2013 (r258372)
@@ -0,0 +1,57 @@
+/*
+ * CDDL HEADER START
+ *
+ * The contents of this file are subject to the terms of the
+ * Common Development and Distribution License (the "License").
+ * You may not use this file except in compliance with the License.
+ *
+ * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+ * or http://www.opensolaris.org/os/licensing.
+ * See the License for the specific language governing permissions
+ * and limitations under the License.
+ *
+ * When distributing Covered Code, include this CDDL HEADER in each
+ * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+ * If applicable, add the following below this CDDL HEADER, with the
+ * fields enclosed by brackets "[]" replaced with your own identifying
+ * information: Portions Copyright [yyyy] [name of copyright owner]
+ *
+ * CDDL HEADER END
+ */
+/*
+ * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
+ * Use is subject to license terms.
+ */
+
+/*
+ * Copyright (c) 2013 by Delphix. All rights reserved.
+ */
+
+#ifndef _SYS_SPACE_REFTREE_H
+#define _SYS_SPACE_REFTREE_H
+
+#include <sys/range_tree.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+typedef struct space_ref {
+ avl_node_t sr_node; /* AVL node */
+ uint64_t sr_offset; /* range offset (start or end) */
+ int64_t sr_refcnt; /* associated reference count */
+} space_ref_t;
+
+void space_reftree_create(avl_tree_t *t);
+void space_reftree_destroy(avl_tree_t *t);
+void space_reftree_add_seg(avl_tree_t *t, uint64_t start, uint64_t end,
+ int64_t refcnt);
+void space_reftree_add_map(avl_tree_t *t, range_tree_t *rt, int64_t refcnt);
+void space_reftree_generate_map(avl_tree_t *t, range_tree_t *rt,
+ int64_t minref);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _SYS_SPACE_REFTREE_H */
More information about the svn-src-vendor
mailing list