4374 dn_free_ranges should use range_tree_t
Reviewed by: George Wilson <george.wilson@delphix.com>
Reviewed by: Max Grossman <max.grossman@delphix.com>
Reviewed by: Christopher Siden <christopher.siden@delphix.com
Reviewed by: Garrett D'Amore <garrett@damore.org>
Reviewed by: Dan McDonald <danmcd@omniti.com>
Approved by: Dan McDonald <danmcd@omniti.com>

*** 21,31 ****
  /*
   * 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>
--- 21,31 ----
  /*
   * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
   * Use is subject to license terms.
   */
  /*
!  * Copyright (c) 2013, 2014 by Delphix. All rights reserved.
   */
  
  #include <sys/zfs_context.h>
  #include <sys/spa.h>
  #include <sys/dmu.h>
*** 58,68 ****
          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);
          }
  
--- 58,68 ----
          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 = highbit64(size) - 1;
  
                  hist[idx]++;
                  ASSERT3U(hist[idx], !=, 0);
          }
  
*** 77,87 ****
  
  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));
--- 77,87 ----
  
  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 = highbit64(size) - 1;
  
          ASSERT3U(idx, <,
              sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
  
          ASSERT(MUTEX_HELD(rt->rt_lock));
*** 91,101 ****
  
  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));
--- 91,101 ----
  
  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 = highbit64(size) - 1;
  
          ASSERT3U(idx, <,
              sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
  
          ASSERT(MUTEX_HELD(rt->rt_lock));
*** 297,343 ****
  
          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)
  {
--- 297,361 ----
  
          rt->rt_space -= size;
  }
  
  static range_seg_t *
! range_tree_find_impl(range_tree_t *rt, uint64_t start, uint64_t size)
  {
!         avl_index_t where;
!         range_seg_t rsearch;
          uint64_t end = start + size;
  
          ASSERT(MUTEX_HELD(rt->rt_lock));
          VERIFY(size != 0);
  
          rsearch.rs_start = start;
          rsearch.rs_end = end;
!         return (avl_find(&rt->rt_root, &rsearch, &where));
! }
  
! static range_seg_t *
! range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size)
! {
!         range_seg_t *rs = range_tree_find_impl(rt, start, size);
!         if (rs != NULL && rs->rs_start <= start && rs->rs_end >= start + size)
                  return (rs);
          return (NULL);
  }
  
  void
  range_tree_verify(range_tree_t *rt, uint64_t off, uint64_t size)
  {
          range_seg_t *rs;
  
          mutex_enter(rt->rt_lock);
!         rs = range_tree_find(rt, off, size);
          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)
  {
!         return (range_tree_find(rt, start, size) != NULL);
! }
  
! /*
!  * Ensure that this range is not in the tree, regardless of whether
!  * it is currently in the tree.
!  */
! void
! range_tree_clear(range_tree_t *rt, uint64_t start, uint64_t size)
! {
!         range_seg_t *rs;
! 
!         while ((rs = range_tree_find_impl(rt, start, size)) != NULL) {
!                 uint64_t free_start = MAX(rs->rs_start, start);
!                 uint64_t free_end = MIN(rs->rs_end, start + size);
!                 range_tree_remove(rt, free_start, free_end - free_start);
!         }
  }
  
  void
  range_tree_swap(range_tree_t **rtsrc, range_tree_t **rtdst)
  {