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 --- |