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>

*** 18,28 ****
   *
   * CDDL HEADER END
   */
  /*
   * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
!  * Copyright (c) 2013 by Delphix. All rights reserved.
   * Copyright (c) 2013 by Saso Kiselkov. All rights reserved.
   */
  
  #include <sys/zfs_context.h>
  #include <sys/dmu.h>
--- 18,28 ----
   *
   * CDDL HEADER END
   */
  /*
   * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
!  * Copyright (c) 2011, 2014 by Delphix. All rights reserved.
   * Copyright (c) 2013 by Saso Kiselkov. All rights reserved.
   */
  
  #include <sys/zfs_context.h>
  #include <sys/dmu.h>
*** 691,701 ****
           * alignment from the same area of the metaslab (i.e. same cursor
           * bucket) but it does not guarantee that other allocations sizes
           * may exist in the same region.
           */
          uint64_t align = size & -size;
!         uint64_t *cursor = &msp->ms_lbas[highbit(align) - 1];
          avl_tree_t *t = &msp->ms_tree->rt_root;
  
          return (metaslab_block_picker(t, cursor, size, align));
  }
  
--- 691,701 ----
           * alignment from the same area of the metaslab (i.e. same cursor
           * bucket) but it does not guarantee that other allocations sizes
           * may exist in the same region.
           */
          uint64_t align = size & -size;
!         uint64_t *cursor = &msp->ms_lbas[highbit64(align) - 1];
          avl_tree_t *t = &msp->ms_tree->rt_root;
  
          return (metaslab_block_picker(t, cursor, size, align));
  }
  
*** 728,738 ****
           * alignment from the same area of the metaslab (i.e. same cursor
           * bucket) but it does not guarantee that other allocations sizes
           * may exist in the same region.
           */
          uint64_t align = size & -size;
!         uint64_t *cursor = &msp->ms_lbas[highbit(align) - 1];
          range_tree_t *rt = msp->ms_tree;
          avl_tree_t *t = &rt->rt_root;
          uint64_t max_size = metaslab_block_maxsize(msp);
          int free_pct = range_tree_space(rt) * 100 / msp->ms_size;
  
--- 728,738 ----
           * alignment from the same area of the metaslab (i.e. same cursor
           * bucket) but it does not guarantee that other allocations sizes
           * may exist in the same region.
           */
          uint64_t align = size & -size;
!         uint64_t *cursor = &msp->ms_lbas[highbit64(align) - 1];
          range_tree_t *rt = msp->ms_tree;
          avl_tree_t *t = &rt->rt_root;
          uint64_t max_size = metaslab_block_maxsize(msp);
          int free_pct = range_tree_space(rt) * 100 / msp->ms_size;
  
*** 844,854 ****
  metaslab_ndf_alloc(metaslab_t *msp, uint64_t size)
  {
          avl_tree_t *t = &msp->ms_tree->rt_root;
          avl_index_t where;
          range_seg_t *rs, rsearch;
!         uint64_t hbit = highbit(size);
          uint64_t *cursor = &msp->ms_lbas[hbit - 1];
          uint64_t max_size = metaslab_block_maxsize(msp);
  
          ASSERT(MUTEX_HELD(&msp->ms_lock));
          ASSERT3U(avl_numnodes(t), ==, avl_numnodes(&msp->ms_size_tree));
--- 844,854 ----
  metaslab_ndf_alloc(metaslab_t *msp, uint64_t size)
  {
          avl_tree_t *t = &msp->ms_tree->rt_root;
          avl_index_t where;
          range_seg_t *rs, rsearch;
!         uint64_t hbit = highbit64(size);
          uint64_t *cursor = &msp->ms_lbas[hbit - 1];
          uint64_t max_size = metaslab_block_maxsize(msp);
  
          ASSERT(MUTEX_HELD(&msp->ms_lock));
          ASSERT3U(avl_numnodes(t), ==, avl_numnodes(&msp->ms_size_tree));
*** 1087,1097 ****
           * metaslab.
           */
          if (msp->ms_sm == NULL) {
                  vdev_t *vd = msp->ms_group->mg_vd;
  
!                 i = highbit(msp->ms_size) - 1;
                  sectors = msp->ms_size >> vd->vdev_ashift;
                  return (sectors * i * vd->vdev_ashift);
          }
  
          if (msp->ms_sm->sm_dbuf->db_size != sizeof (space_map_phys_t))
--- 1087,1097 ----
           * metaslab.
           */
          if (msp->ms_sm == NULL) {
                  vdev_t *vd = msp->ms_group->mg_vd;
  
!                 i = highbit64(msp->ms_size) - 1;
                  sectors = msp->ms_size >> vd->vdev_ashift;
                  return (sectors * i * vd->vdev_ashift);
          }
  
          if (msp->ms_sm->sm_dbuf->db_size != sizeof (space_map_phys_t))