Deleted Added
sdiff udiff text old ( 262093 ) new ( 265740 )
full compact
range_tree.c (262093) range_tree.c (265740)
1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE

--- 9 unchanged lines hidden (view full) ---

18 *
19 * CDDL HEADER END
20 */
21/*
22 * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
24 */
25/*
1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE

--- 9 unchanged lines hidden (view full) ---

18 *
19 * CDDL HEADER END
20 */
21/*
22 * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
24 */
25/*
26 * Copyright (c) 2013 by Delphix. All rights reserved.
26 * Copyright (c) 2013, 2014 by Delphix. All rights reserved.
27 */
28
29#include <sys/zfs_context.h>
30#include <sys/spa.h>
31#include <sys/dmu.h>
32#include <sys/dnode.h>
33#include <sys/zio.h>
34#include <sys/range_tree.h>

--- 20 unchanged lines hidden (view full) ---

55{
56 range_seg_t *rs;
57 uint64_t hist[RANGE_TREE_HISTOGRAM_SIZE] = { 0 };
58 int i;
59
60 for (rs = avl_first(&rt->rt_root); rs != NULL;
61 rs = AVL_NEXT(&rt->rt_root, rs)) {
62 uint64_t size = rs->rs_end - rs->rs_start;
27 */
28
29#include <sys/zfs_context.h>
30#include <sys/spa.h>
31#include <sys/dmu.h>
32#include <sys/dnode.h>
33#include <sys/zio.h>
34#include <sys/range_tree.h>

--- 20 unchanged lines hidden (view full) ---

55{
56 range_seg_t *rs;
57 uint64_t hist[RANGE_TREE_HISTOGRAM_SIZE] = { 0 };
58 int i;
59
60 for (rs = avl_first(&rt->rt_root); rs != NULL;
61 rs = AVL_NEXT(&rt->rt_root, rs)) {
62 uint64_t size = rs->rs_end - rs->rs_start;
63 int idx = highbit(size) - 1;
63 int idx = highbit64(size) - 1;
64
65 hist[idx]++;
66 ASSERT3U(hist[idx], !=, 0);
67 }
68
69 for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++) {
70 if (hist[i] != rt->rt_histogram[i]) {
71 zfs_dbgmsg("i=%d, hist=%p, hist=%llu, rt_hist=%llu",
72 i, hist, hist[i], rt->rt_histogram[i]);
73 }
74 VERIFY3U(hist[i], ==, rt->rt_histogram[i]);
75 }
76}
77
78static void
79range_tree_stat_incr(range_tree_t *rt, range_seg_t *rs)
80{
81 uint64_t size = rs->rs_end - rs->rs_start;
64
65 hist[idx]++;
66 ASSERT3U(hist[idx], !=, 0);
67 }
68
69 for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++) {
70 if (hist[i] != rt->rt_histogram[i]) {
71 zfs_dbgmsg("i=%d, hist=%p, hist=%llu, rt_hist=%llu",
72 i, hist, hist[i], rt->rt_histogram[i]);
73 }
74 VERIFY3U(hist[i], ==, rt->rt_histogram[i]);
75 }
76}
77
78static void
79range_tree_stat_incr(range_tree_t *rt, range_seg_t *rs)
80{
81 uint64_t size = rs->rs_end - rs->rs_start;
82 int idx = highbit(size) - 1;
82 int idx = highbit64(size) - 1;
83
84 ASSERT3U(idx, <,
85 sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
86
87 ASSERT(MUTEX_HELD(rt->rt_lock));
88 rt->rt_histogram[idx]++;
89 ASSERT3U(rt->rt_histogram[idx], !=, 0);
90}
91
92static void
93range_tree_stat_decr(range_tree_t *rt, range_seg_t *rs)
94{
95 uint64_t size = rs->rs_end - rs->rs_start;
83
84 ASSERT3U(idx, <,
85 sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
86
87 ASSERT(MUTEX_HELD(rt->rt_lock));
88 rt->rt_histogram[idx]++;
89 ASSERT3U(rt->rt_histogram[idx], !=, 0);
90}
91
92static void
93range_tree_stat_decr(range_tree_t *rt, range_seg_t *rs)
94{
95 uint64_t size = rs->rs_end - rs->rs_start;
96 int idx = highbit(size) - 1;
96 int idx = highbit64(size) - 1;
97
98 ASSERT3U(idx, <,
99 sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
100
101 ASSERT(MUTEX_HELD(rt->rt_lock));
102 ASSERT3U(rt->rt_histogram[idx], !=, 0);
103 rt->rt_histogram[idx]--;
104}

--- 189 unchanged lines hidden (view full) ---

294 if (rt->rt_ops != NULL)
295 rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
296 }
297
298 rt->rt_space -= size;
299}
300
301static range_seg_t *
97
98 ASSERT3U(idx, <,
99 sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
100
101 ASSERT(MUTEX_HELD(rt->rt_lock));
102 ASSERT3U(rt->rt_histogram[idx], !=, 0);
103 rt->rt_histogram[idx]--;
104}

--- 189 unchanged lines hidden (view full) ---

294 if (rt->rt_ops != NULL)
295 rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
296 }
297
298 rt->rt_space -= size;
299}
300
301static range_seg_t *
302range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size,
303 avl_index_t *wherep)
302range_tree_find_impl(range_tree_t *rt, uint64_t start, uint64_t size)
304{
303{
305 range_seg_t rsearch, *rs;
304 avl_index_t where;
305 range_seg_t rsearch;
306 uint64_t end = start + size;
307
308 ASSERT(MUTEX_HELD(rt->rt_lock));
309 VERIFY(size != 0);
310
311 rsearch.rs_start = start;
312 rsearch.rs_end = end;
306 uint64_t end = start + size;
307
308 ASSERT(MUTEX_HELD(rt->rt_lock));
309 VERIFY(size != 0);
310
311 rsearch.rs_start = start;
312 rsearch.rs_end = end;
313 rs = avl_find(&rt->rt_root, &rsearch, wherep);
313 return (avl_find(&rt->rt_root, &rsearch, &where));
314}
314
315
315 if (rs != NULL && rs->rs_start <= start && rs->rs_end >= end)
316static range_seg_t *
317range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size)
318{
319 range_seg_t *rs = range_tree_find_impl(rt, start, size);
320 if (rs != NULL && rs->rs_start <= start && rs->rs_end >= start + size)
316 return (rs);
317 return (NULL);
318}
319
320void
321range_tree_verify(range_tree_t *rt, uint64_t off, uint64_t size)
322{
323 range_seg_t *rs;
321 return (rs);
322 return (NULL);
323}
324
325void
326range_tree_verify(range_tree_t *rt, uint64_t off, uint64_t size)
327{
328 range_seg_t *rs;
324 avl_index_t where;
325
326 mutex_enter(rt->rt_lock);
329
330 mutex_enter(rt->rt_lock);
327 rs = range_tree_find(rt, off, size, &where);
331 rs = range_tree_find(rt, off, size);
328 if (rs != NULL)
329 panic("freeing free block; rs=%p", (void *)rs);
330 mutex_exit(rt->rt_lock);
331}
332
333boolean_t
334range_tree_contains(range_tree_t *rt, uint64_t start, uint64_t size)
335{
332 if (rs != NULL)
333 panic("freeing free block; rs=%p", (void *)rs);
334 mutex_exit(rt->rt_lock);
335}
336
337boolean_t
338range_tree_contains(range_tree_t *rt, uint64_t start, uint64_t size)
339{
336 avl_index_t where;
340 return (range_tree_find(rt, start, size) != NULL);
341}
337
342
338 return (range_tree_find(rt, start, size, &where) != NULL);
343/*
344 * Ensure that this range is not in the tree, regardless of whether
345 * it is currently in the tree.
346 */
347void
348range_tree_clear(range_tree_t *rt, uint64_t start, uint64_t size)
349{
350 range_seg_t *rs;
351
352 while ((rs = range_tree_find_impl(rt, start, size)) != NULL) {
353 uint64_t free_start = MAX(rs->rs_start, start);
354 uint64_t free_end = MIN(rs->rs_end, start + size);
355 range_tree_remove(rt, free_start, free_end - free_start);
356 }
339}
340
341void
342range_tree_swap(range_tree_t **rtsrc, range_tree_t **rtdst)
343{
344 range_tree_t *rt;
345
346 ASSERT(MUTEX_HELD((*rtsrc)->rt_lock));

--- 45 unchanged lines hidden --- 		357}
358
359void
360range_tree_swap(range_tree_t **rtsrc, range_tree_t **rtdst)
361{
362 range_tree_t *rt;
363
364 ASSERT(MUTEX_HELD((*rtsrc)->rt_lock));

--- 45 unchanged lines hidden ---