# Copyright (c) 2018 Cisco and/or its affiliates.
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at:
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""Drop rate search algorithms"""

from abc import ABCMeta, abstractmethod
from enum import Enum, unique


@unique
class SearchDirection(Enum):
    """Direction of linear search."""

    TOP_DOWN = 1
    BOTTOM_UP = 2


@unique
class SearchResults(Enum):
    """Result of the drop rate search."""

    SUCCESS = 1
    FAILURE = 2
    SUSPICIOUS = 3


@unique
class RateType(Enum):
    """Type of rate units."""

    PERCENTAGE = 1
    PACKETS_PER_SECOND = 2
    BITS_PER_SECOND = 3


@unique
class LossAcceptanceType(Enum):
    """Type of the loss acceptance criteria."""

    FRAMES = 1
    PERCENTAGE = 2


@unique
class SearchResultType(Enum):
    """Type of search result evaluation."""

    BEST_OF_N = 1
    WORST_OF_N = 2


class DropRateSearch(object):
    """Abstract class with search algorithm implementation."""

    __metaclass__ = ABCMeta

    def __init__(self):
        # duration of traffic run (binary, linear)
        self._duration = 60
        # initial start rate (binary, linear)
        self._rate_start = 100
        # step of the linear search, unit: RateType (self._rate_type)
        self._rate_linear_step = 10
        # last rate of the binary search, unit: RateType (self._rate_type)
        self._last_binary_rate = 0
        # linear search direction, permitted values: SearchDirection
        self._search_linear_direction = SearchDirection.TOP_DOWN
        # upper limit of search, unit: RateType (self._rate_type)
        self._rate_max = 100
        # lower limit of search, unit: RateType (self._rate_type)
        self._rate_min = 1
        # permitted values: RateType
        self._rate_type = RateType.PERCENTAGE
        # accepted loss during search, units: LossAcceptanceType
        self._loss_acceptance = 0
        # permitted values: LossAcceptanceType
        self._loss_acceptance_type = LossAcceptanceType.FRAMES
        # size of frames to send
        self._frame_size = "64"
        # binary convergence criterium type is self._rate_type
        self._binary_convergence_threshold = 5000
        # numbers of traffic runs during one rate step
        self._max_attempts = 1
        # type of search result evaluation, unit: SearchResultType
        self._search_result_type = SearchResultType.BEST_OF_N

        # result of search
        self._search_result = None
        self._search_result_rate = None

    @abstractmethod
    def get_latency(self):
        """Return min/avg/max latency.

        :returns: Latency stats.
        :rtype: list
        """
        pass

    @abstractmethod
    def measure_loss(self, rate, frame_size, loss_acceptance,
                     loss_acceptance_type, traffic_type, skip_warmup=False):
        """Send traffic from TG and measure count of dropped frames.

        :param rate: Offered traffic load.
        :param frame_size: Size of frame.
        :param loss_acceptance: Permitted drop ratio or frames count.
        :param loss_acceptance_type: Type of permitted loss.
        :param traffic_type: Traffic profile ([2,3]-node-L[2,3], ...).
        :param skip_warmup: Start TRex without warmup traffic if true.
        :type rate: int
        :type frame_size: str
        :type loss_acceptance: float
        :type loss_acceptance_type: LossAcceptanceType
        :type traffic_type: str
        :type traffic_type: bool
        :returns: Drop threshold exceeded? (True/False)
        :rtype: bool
        """
        pass

    def set_search_rate_boundaries(self, max_rate, min_rate):
        """Set search boundaries: min,max.

        :param max_rate: Upper value of search boundaries.
        :param min_rate: Lower value of search boundaries.
        :type max_rate: float
        :type min_rate: float
        :returns: nothing
        :raises ValueError: If min rate is lower than 0 or higher than max rate.
        """
        if float(min_rate) <= 0:
            raise ValueError("min_rate must be higher than 0")
        elif float(min_rate) > float(max_rate):
            raise ValueError("min_rate must be lower than max_rate")
        else:
            self._rate_max = float(max_rate)
            self._rate_min = float(min_rate)

    def set_loss_acceptance(self, loss_acceptance):
        """Set loss acceptance treshold for PDR search.

        :param loss_acceptance: Loss acceptance treshold for PDR search.
        :type loss_acceptance: str
        :returns: nothing
        :raises ValueError: If loss acceptance is lower than zero.
        """
        if float(loss_acceptance) < 0:
            raise ValueError("Loss acceptance must be higher or equal 0")
        else:
            self._loss_acceptance = float(loss_acceptance)

    def get_loss_acceptance(self):
        """Return configured loss acceptance treshold.

        :returns: Loss acceptance treshold.
        :rtype: float
        """
        return self._loss_acceptance

    def set_loss_acceptance_type_percentage(self):
        """Set loss acceptance treshold type to percentage.

        :returns: nothing
        """
        self._loss_acceptance_type = LossAcceptanceType.PERCENTAGE

    def set_loss_acceptance_type_frames(self):
        """Set loss acceptance treshold type to frames.

        :returns: nothing
        """
        self._loss_acceptance_type = LossAcceptanceType.FRAMES

    def loss_acceptance_type_is_percentage(self):
        """Return true if loss acceptance treshold type is percentage,
           false otherwise.

        :returns: True if loss acceptance treshold type is percentage.
        :rtype: boolean
        """
        return self._loss_acceptance_type == LossAcceptanceType.PERCENTAGE

    def set_search_linear_step(self, step_rate):
        """Set step size for linear search.

        :param step_rate: Linear search step size.
        :type step_rate: float
        :returns: nothing
        """
        self._rate_linear_step = float(step_rate)

    def set_search_rate_type_percentage(self):
        """Set rate type to percentage of linerate.

        :returns: nothing
        """
        self._set_search_rate_type(RateType.PERCENTAGE)

    def set_search_rate_type_bps(self):
        """Set rate type to bits per second.

        :returns: nothing
        """
        self._set_search_rate_type(RateType.BITS_PER_SECOND)

    def set_search_rate_type_pps(self):
        """Set rate type to packets per second.

        :returns: nothing
        """
        self._set_search_rate_type(RateType.PACKETS_PER_SECOND)

    def _set_search_rate_type(self, rate_type):
        """Set rate type to one of RateType-s.

        :param rate_type: Type of rate to set.
        :type rate_type: RateType
        :returns: nothing
        :raises Exception: If rate type is unknown.
        """
        if rate_type not in RateType:
            raise Exception("rate_type unknown: {}".format(rate_type))
        else:
            self._rate_type = rate_type

    def set_search_frame_size(self, frame_size):
        """Set size of frames to send.

        :param frame_size: Size of frames.
        :type frame_size: str
        :returns: nothing
        """
        self._frame_size = frame_size

    def set_duration(self, duration):
        """Set the duration of single traffic run.

        :param duration: Number of seconds for traffic to run.
        :type duration: int
        :returns: nothing
        ""&
/*
 * Copyright (c) 2015 Cisco and/or its affiliates.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/*
  Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus

  Permission is hereby granted, free of charge, to any person obtaining
  a copy of this software and associated documentation files (the
  "Software"), to deal in the Software without restriction, including
  without limitation the rights to use, copy, modify, merge, publish,
  distribute, sublicense, and/or sell copies of the Software, and to
  permit persons to whom the Software is furnished to do so, subject to
  the following conditions:

  The above copyright notice and this permission notice shall be
  included in all copies or substantial portions of the Software.

  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

#include <vppinfra/bitops.h>
#include <vppinfra/hash.h>
#include <vppinfra/format.h>
#include <vppinfra/mheap.h>
#include <vppinfra/os.h>
#include <vppinfra/time.h>

#ifdef CLIB_UNIX
#include <vppinfra/elf_clib.h>
#endif

static void mheap_get_trace (void *v, uword offset, uword size);
static void mheap_put_trace (void *v, uword offset, uword size);
static int mheap_trace_sort (const void *t1, const void *t2);

always_inline void
mheap_maybe_lock (void *v)
{
  mheap_t *h = mheap_header (v);
  if (v && (h->flags & MHEAP_FLAG_THREAD_SAFE))
    {
      u32 my_cpu = os_get_thread_index ();
      if (h->owner_cpu == my_cpu)
	{
	  h->recursion_count++;
	  return;
	}

      while (__sync_lock_test_and_set (&h->lock, 1))
	;

      h->owner_cpu = my_cpu;
      h->recursion_count = 1;
    }
}

always_inline void
mheap_maybe_unlock (void *v)
{
  mheap_t *h = mheap_header (v);
  if (v && h->flags & MHEAP_FLAG_THREAD_SAFE)
    {
      ASSERT (os_get_thread_index () == h->owner_cpu);
      if (--h->recursion_count == 0)
	{
	  h->owner_cpu = ~0;
	  CLIB_MEMORY_BARRIER ();
	  h->lock = 0;
	}
    }
}

/* Find bin for objects with size at least n_user_data_bytes. */
always_inline uword
user_data_size_to_bin_index (uword n_user_data_bytes)
{
  uword n_user_data_words;
  word small_bin, large_bin;

  /* User size must be at least big enough to hold free elt. */
  n_user_data_bytes = clib_max (n_user_data_bytes, MHEAP_MIN_USER_DATA_BYTES);

  /* Round to words. */
  n_user_data_words =
    (round_pow2 (n_user_data_bytes, MHEAP_USER_DATA_WORD_BYTES) /
     MHEAP_USER_DATA_WORD_BYTES);

  ASSERT (n_user_data_words > 0);
  small_bin =
    n_user_data_words -
    (MHEAP_MIN_USER_DATA_BYTES / MHEAP_USER_DATA_WORD_BYTES);
  ASSERT (small_bin >= 0);

  large_bin =
    MHEAP_N_SMALL_OBJECT_BINS + max_log2 (n_user_data_bytes) -
    MHEAP_LOG2_N_SMALL_OBJECT_BINS;

  return small_bin < MHEAP_N_SMALL_OBJECT_BINS ? small_bin : large_bin;
}

always_inline uword
mheap_elt_size_to_user_n_bytes (uword n_bytes)
{
  ASSERT (n_bytes >= sizeof (mheap_elt_t));
  return (n_bytes - STRUCT_OFFSET_OF (mheap_elt_t, user_data));
}

always_inline uword __attribute__ ((unused))
mheap_elt_size_to_user_n_words (uword n_bytes)
{
  ASSERT (n_bytes % MHEAP_USER_DATA_WORD_BYTES == 0);
  return mheap_elt_size_to_user_n_bytes (n_bytes) /
    MHEAP_USER_DATA_WORD_BYTES;
}

always_inline void
mheap_elt_set_size (void *v,
		    uword uoffset, uword n_user_data_bytes, uword is_free)
{
  mheap_elt_t *e, *n;

  e = mheap_elt_at_uoffset (v, uoffset);

  ASSERT (n_user_data_bytes % MHEAP_USER_DATA_WORD_BYTES == 0);

  e->n_user_data = n_user_data_bytes / MHEAP_USER_DATA_WORD_BYTES;
  e->is_free = is_free;
  ASSERT (e->prev_n_user_data * sizeof (e->user_data[0]) >=
	  MHEAP_MIN_USER_DATA_BYTES);

  n = mheap_next_elt (e);
  n->prev_n_user_data = e->n_user_data;
  n->prev_is_free = is_free;
}

always_inline void
set_first_free_elt_offset (mheap_t * h, uword bin, uword uoffset)
{
  uword i0, i1;

  h->first_free_elt_uoffset_by_bin[bin] = uoffset;

  i0 = bin / BITS (h->non_empty_free_elt_heads[0]);
  i1 = (uword) 1 << (uword) (bin % BITS (h->non_empty_free_elt_heads[0]));

  ASSERT (i0 < ARRAY_LEN (h->non_empty_free_elt_heads));
  if (h->first_free_elt_uoffset_by_bin[bin] == MHEAP_GROUNDED)
    h->non_empty_free_elt_heads[i0] &= ~i1;
  else
    h->non_empty_free_elt_heads[i0] |= i1;
}

always_inline void
set_free_elt (void *v, uword uoffset, uword n_user_data_bytes)
{
  mheap_t *h = mheap_header (v);
  mheap_elt_t *e = mheap_elt_at_uoffset (v, uoffset);
  mheap_elt_t *n = mheap_next_elt (e);
  uword bin = user_data_size_to_bin_index (n_user_data_bytes);

  ASSERT (n->prev_is_free);
  ASSERT (e->is_free);

  e->free_elt.prev_uoffset = MHEAP_GROUNDED;
  e->free_elt.next_uoffset = h->first_free_elt_uoffset_by_bin[bin];

  /* Fill in next free elt's previous pointer. */
  if (e->free_elt.next_uoffset != MHEAP_GROUNDED)
    {
      mheap_elt_t *nf = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
      ASSERT (nf->is_free);
      nf->free_elt.prev_uoffset = uoffset;
    }

  set_first_free_elt_offset (h, bin, uoffset);
}

always_inline void
new_free_elt (void *v, uword uoffset, uword n_user_data_bytes)
{
  mheap_elt_set_size (v, uoffset, n_user_data_bytes, /* is_free */ 1);
  set_free_elt (v, uoffset, n_user_data_bytes);
}

always_inline void
remove_free_elt (void *v, mheap_elt_t * e, uword bin)
{
  mheap_t *h = mheap_header (v);
  mheap_elt_t *p, *n;
#if CLIB_VEC64 > 0
  u64 no, po;
#else
  u32 no, po;
#endif

  no = e->free_elt.next_uoffset;

  n = no != MHEAP_GROUNDED ? mheap_elt_at_uoffset (v, no) : 0;
  po = e->free_elt.prev_uoffset;
  p = po != MHEAP_GROUNDED ? mheap_elt_at_uoffset (v, po) : 0;

  if (!p)
    set_first_free_elt_offset (h, bin, no);
  else
    p->free_elt.next_uoffset = no;

  if (n)
    n->free_elt.prev_uoffset = po;
}

always_inline void
remove_free_elt2 (void *v, mheap_elt_t * e)
{
  uword bin;
  bin = user_data_size_to_bin_index (mheap_elt_data_bytes (e));
  remove_free_elt (v, e, bin);
}

#define MHEAP_VM_MAP		(1 << 0)
#define MHEAP_VM_UNMAP		(1 << 1)
#define MHEAP_VM_NOMAP		(0 << 1)
#define MHEAP_VM_ROUND		(1 << 2)
#define MHEAP_VM_ROUND_UP	MHEAP_VM_ROUND
#define MHEAP_VM_ROUND_DOWN	(0 << 2)

static uword mheap_page_size;

static_always_inline uword
mheap_page_round (uword addr)
{
  return (addr + mheap_page_size - 1) & ~(mheap_page_size - 1);
}

static_always_inline uword
mheap_page_truncate (uword addr)
{
  return addr & ~(mheap_page_size - 1);
}

static_always_inline uword
mheap_vm (void *v, uword flags, clib_address_t start_addr, uword size)
{
  mheap_t *h = mheap_header (v);
  clib_address_t start_page, end_page, end_addr;
  uword mapped_bytes;

  ASSERT (!(h->flags & MHEAP_FLAG_DISABLE_VM));

  end_addr = start_addr + size;

  /* Round start/end address up to page boundary. */
  start_page = mheap_page_round (start_addr);

  if ((flags & MHEAP_VM_ROUND) == MHEAP_VM_ROUND_UP)
    end_page = mheap_page_round (end_addr);
  else
    end_page = mheap_page_truncate (end_addr);

  mapped_bytes = 0;
  if (end_page > start_page)
    {
      mapped_bytes = end_page - start_page;
      if (flags & MHEAP_VM_MAP)
	clib_mem_vm_map ((void *) start_page, end_page - start_page);
      else if (flags & MHEAP_VM_UNMAP)
	clib_mem_vm_unmap ((void *) start_page, end_page - start_page);
    }

  return mapped_bytes;
}

static_always_inline uword
mheap_vm_elt (void *v, uword flags, uword offset)
{
  mheap_elt_t *e;
  clib_address_t start_addr, end_addr;

  e = mheap_elt_at_uoffset (v, offset);
  start_addr = (clib_address_t) ((void *) e->user_data);
  end_addr = (clib_address_t) mheap_next_elt (e);
  return mheap_vm (v, flags, start_addr, end_addr - start_addr);
}

always_inline uword
mheap_small_object_cache_mask (mheap_small_object_cache_t * c, uword bin)
{
  uword mask;

/* $$$$ ELIOT FIXME: add Altivec version of this routine */
#if !defined (CLIB_HAVE_VEC128) || defined (__ALTIVEC__) || defined (__i386__)
  mask = 0;
#else
  u8x16 b = u8x16_splat (bin);

  ASSERT (bin < 256);

#define _(i) ((uword) u8x16_compare_byte_mask (u8x16_is_equal (b, c->bins.as_u8x16[i])) << (uword) ((i)*16))
  mask = _(0) | _(1);
  if (BITS (uword) > 32)
    mask |= _(2) | _(3);
#undef _

#endif
  return mask;
}

always_inline uword
mheap_get_small_object (mheap_t * h, uword bin)
{
  mheap_small_object_cache_t *c = &h->small_object_cache;
  uword mask = mheap_small_object_cache_mask (c, bin + 1);
  uword offset = MHEAP_GROUNDED;

  if (mask)
    {
      uword i = min_log2 (mask);
      uword o = c->offsets[i];
      ASSERT (o != MHEAP_GROUNDED);
      c->bins.as_u8[i] = 0;
      offset = o;
    }

  return offset;
}

always_inline uword
mheap_put_small_object (mheap_t * h, uword bin, uword offset)
{
  mheap_small_object_cache_t *c = &h->small_object_cache;
  uword free_mask = mheap_small_object_cache_mask (c, 0);
  uword b = bin + 1;
  uword i;

  if (free_mask != 0)
    {
      i = min_log2 (free_mask);
      c->bins.as_u8[i] = b;
      c->offsets[i] = offset;
      return 0;
    }
  else
    /* Nothing free with right size: cyclic replacement. */
    {
      uword old_offset;

      i = c->replacement_index++;
      i %= BITS (uword);
      c->bins.as_u8[i] = b;
      old_offset = c->offsets[i];
      c->offsets[i] = offset;

      /* Return old offset so it can be freed. */
      return old_offset;
    }
}

static uword
mheap_get_search_free_bin (void *v,
			   uword bin,
			   uword * n_user_data_bytes_arg,
			   uword align, uword align_offset)
{
  mheap_t *h = mheap_header (v);
  mheap_elt_t *e;

  /* Free object is at offset f0 ... f1;
     Allocatted object is at offset o0 ... o1. */
  word o0, o1, f0, f1, search_n_user_data_bytes;
  word lo_free_usize, hi_free_usize;

  ASSERT (h->first_free_elt_uoffset_by_bin[bin] != MHEAP_GROUNDED);
  e = mheap_elt_at_uoffset (v, h->first_free_elt_uoffset_by_bin[bin]);

  search_n_user_data_bytes = *n_user_data_bytes_arg;

  /* Silence compiler warning. */
  o0 = o1 = f0 = f1 = 0;

  h->stats.free_list.n_search_attempts += 1;

  /* Find an object that is large enough with correct alignment at given alignment offset. */
  while (1)
    {
      uword this_object_n_user_data_bytes = mheap_elt_data_bytes (e);

      ASSERT (e->is_free);
      if (bin < MHEAP_N_SMALL_OBJECT_BINS)
	ASSERT (this_object_n_user_data_bytes >= search_n_user_data_bytes);

      h->stats.free_list.n_objects_searched += 1;

      if (this_object_n_user_data_bytes < search_n_user_data_bytes)
	goto next;

      /* Bounds of free object: from f0 to f1. */
      f0 = ((void *) e->user_data - v);
      f1 = f0 + this_object_n_user_data_bytes;

      /* Place candidate object at end of free block and align as requested. */
      o0 = ((f1 - search_n_user_data_bytes) & ~(align - 1)) - align_offset;
      while (o0 < f0)
	o0 += align;

      /* Make sure that first free fragment is either empty or
         large enough to be valid. */
      while (1)
	{
	  lo_free_usize = o0 != f0 ? o0 - f0 - MHEAP_ELT_OVERHEAD_BYTES : 0;
	  if (o0 <= f0 || lo_free_usize >= (word) MHEAP_MIN_USER_DATA_BYTES)
	    break;
	  o0 -= align;
	}

      o1 = o0 + search_n_user_data_bytes;

      /* Does it fit? */
      if (o0 >= f0 && o1 <= f1)
	goto found;

    next:
      /* Reached end of free list without finding large enough object. */
      if (e->free_elt.next_uoffset == MHEAP_GROUNDED)
	return MHEAP_GROUNDED;

      /* Otherwise keep searching for large enough object. */
      e = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);
    }

found:
  /* Free fragment at end. */
  hi_free_usize = f1 != o1 ? f1 - o1 - MHEAP_ELT_OVERHEAD_BYTES : 0;

  /* If fragment at end is too small to be a new object,
     give user's object a bit more space than requested. */
  if (hi_free_usize < (word) MHEAP_MIN_USER_DATA_BYTES)
    {
      search_n_user_data_bytes += f1 - o1;
      o1 = f1;
      hi_free_usize = 0;
    }

  /* Need to make sure that relevant memory areas are mapped. */
  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
    {
      mheap_elt_t *f0_elt = mheap_elt_at_uoffset (v, f0);
      mheap_elt_t *f1_elt = mheap_elt_at_uoffset (v, f1);
      mheap_elt_t *o0_elt = mheap_elt_at_uoffset (v, o0);
      mheap_elt_t *o1_elt = mheap_elt_at_uoffset (v, o1);

      uword f0_page_start, f0_page_end;
      uword o0_page_start, o0_page_end;

      /* Free elt is mapped.  Addresses after that may not be mapped. */
      f0_page_start = mheap_page_round (pointer_to_uword (f0_elt->user_data));
      f0_page_end = mheap_page_truncate (pointer_to_uword (f1_elt));

      o0_page_start = mheap_page_truncate (pointer_to_uword (o0_elt));
      o0_page_end = mheap_page_round (pointer_to_uword (o1_elt->user_data));

      if (o0_page_start < f0_page_start)
	o0_page_start = f0_page_start;
      if (o0_page_end > f0_page_end)
	o0_page_end = f0_page_end;

      if (o0_page_end > o0_page_start)
	clib_mem_vm_map (uword_to_pointer (o0_page_start, void *),
			 o0_page_end - o0_page_start);
    }

  /* Remove free object from free list. */
  remove_free_elt (v, e, bin);

  /* Free fragment at begining. */
  if (lo_free_usize > 0)
    {
      ASSERT (lo_free_usize >= (word) MHEAP_MIN_USER_DATA_BYTES);
      mheap_elt_set_size (v, f0, lo_free_usize, /* is_free */ 1);
      new_free_elt (v, f0, lo_free_usize);
    }

  mheap_elt_set_size (v, o0, search_n_user_data_bytes, /* is_free */ 0);

  if (hi_free_usize > 0)
    {
      uword uo = o1 + MHEAP_ELT_OVERHEAD_BYTES;
      mheap_elt_set_size (v, uo, hi_free_usize, /* is_free */ 1);
      new_free_elt (v, uo, hi_free_usize);
    }

  /* Return actual size of block. */
  *n_user_data_bytes_arg = search_n_user_data_bytes;

  h->stats.free_list.n_objects_found += 1;

  return o0;
}

/* Search free lists for object with given size and alignment. */
static uword
mheap_get_search_free_list (void *v,
			    uword * n_user_bytes_arg,
			    uword align, uword align_offset)
{
  mheap_t *h = mheap_header (v);
  uword bin, n_user_bytes, i, bi;

  n_user_bytes = *n_user_bytes_arg;
  bin = user_data_size_to_bin_index (n_user_bytes);

  if (MHEAP_HAVE_SMALL_OBJECT_CACHE
      && (h->flags & MHEAP_FLAG_SMALL_OBJECT_CACHE)
      && bin < 255
      && align == STRUCT_SIZE_OF (mheap_elt_t, user_data[0])
      && align_offset == 0)
    {
      uword r = mheap_get_small_object (h, bin);
      h->stats.n_small_object_cache_attempts += 1;
      if (r != MHEAP_GROUNDED)
	{
	  h->stats.n_small_object_cache_hits += 1;
	  return r;
	}
    }

  for (i = bin / BITS (uword); i < ARRAY_LEN (h->non_empty_free_elt_heads);
       i++)
    {
      uword non_empty_bin_mask = h->non_empty_free_elt_heads[i];

      /* No need to search smaller bins. */
      if (i == bin / BITS (uword))
	non_empty_bin_mask &= ~pow2_mask (bin % BITS (uword));

      /* Search each occupied free bin which is large enough. */
      /* *INDENT-OFF* */
      foreach_set_bit (bi, non_empty_bin_mask,
      ({
        uword r =
          mheap_get_search_free_bin (v, bi + i * BITS (uword),
                                     n_user_bytes_arg,
                                     align,
                                     align_offset);
        if (r != MHEAP_GROUNDED) return r;
      }));
      /* *INDENT-ON* */
    }

  return MHEAP_GROUNDED;
}

static never_inline void *
mheap_get_extend_vector (void *v,
			 uword n_user_data_bytes,
			 uword align,
			 uword align_offset, uword * offset_return)
{
  /* Bounds of free and allocated objects (as above). */
  uword f0, f1, o0, o1;
  word free_size;
  mheap_t *h = mheap_header (v);
  mheap_elt_t *e;

  if (_vec_len (v) == 0)
    {
      _vec_len (v) = MHEAP_ELT_OVERHEAD_BYTES;

      /* Create first element of heap. */
      e = mheap_elt_at_uoffset (v, _vec_len (v));
      e->prev_n_user_data = MHEAP_N_USER_DATA_INVALID;
    }

  f0 = _vec_len (v);

  o0 = round_pow2 (f0, align) - align_offset;
  while (1)
    {
      free_size = o0 - f0 - MHEAP_ELT_OVERHEAD_BYTES;
      if (o0 == f0 || free_size >= (word) sizeof (mheap_elt_t))
	break;

      o0 += align;
    }

  o1 = o0 + n_user_data_bytes;
  f1 = o1 + MHEAP_ELT_OVERHEAD_BYTES;

  ASSERT (v != 0);
  h = mheap_header (v);

  /* Make sure we have space for object plus overhead. */
  if (f1 > h->max_size)
    {
      *offset_return = MHEAP_GROUNDED;
      return v;
    }

  _vec_len (v) = f1;

  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
    {
      mheap_elt_t *f0_elt = mheap_elt_at_uoffset (v, f0);
      mheap_elt_t *f1_elt = mheap_elt_at_uoffset (v, f1);

      uword f0_page = mheap_page_round (pointer_to_uword (f0_elt->user_data));
      uword f1_page = mheap_page_round (pointer_to_uword (f1_elt->user_data));

      if (f1_page > f0_page)
	mheap_vm (v, MHEAP_VM_MAP, f0_page, f1_page - f0_page);
    }

  if (free_size > 0)
    new_free_elt (v, f0, free_size);

  mheap_elt_set_size (v, o0, n_user_data_bytes, /* is_free */ 0);

  /* Mark last element. */
  e = mheap_elt_at_uoffset (v, f1);
  e->n_user_data = MHEAP_N_USER_DATA_INVALID;

  *offset_return = o0;

  return v;
}

void *
mheap_get_aligned (void *v,
		   uword n_user_data_bytes,
		   uword align, uword align_offset, uword * offset_return)
{
  mheap_t *h;
  uword offset;
  u64 cpu_times[2];

  cpu_times[0] = clib_cpu_time_now ();

  align = clib_max (align, STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));
  align = max_pow2 (align);

  /* Correct align offset to be smaller than alignment. */
  align_offset &= (align - 1);

  /* Align offset must be multiple of minimum object size. */
  if (align_offset % STRUCT_SIZE_OF (mheap_elt_t, user_data[0]) != 0)
    {
      *offset_return = MHEAP_GROUNDED;
      return v;
    }

  /* Round requested size. */
  n_user_data_bytes = clib_max (n_user_data_bytes, MHEAP_MIN_USER_DATA_BYTES);
  n_user_data_bytes =
    round_pow2 (n_user_data_bytes,
		STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));

  if (!v)
    v = mheap_alloc (0, 64 << 20);

  mheap_maybe_lock (v);

  h = mheap_header (v);

  if (h->flags & MHEAP_FLAG_VALIDATE)
    mheap_validate (v);

  /* First search free lists for object. */
  offset =
    mheap_get_search_free_list (v, &n_user_data_bytes, align, align_offset);

  h = mheap_header (v);

  /* If that fails allocate object at end of heap by extending vector. */
  if (offset == MHEAP_GROUNDED && _vec_len (v) < h->max_size)
    {
      v =
	mheap_get_extend_vector (v, n_user_data_bytes, align, align_offset,
				 &offset);
      h = mheap_header (v);
      h->stats.n_vector_expands += offset != MHEAP_GROUNDED;
    }

  *offset_return = offset;
  if (offset != MHEAP_GROUNDED)
    {
      h->n_elts += 1;

      if (h->flags & MHEAP_FLAG_TRACE)
	{
	  /* Recursion block for case when we are traceing main clib heap. */
	  h->flags &= ~MHEAP_FLAG_TRACE;

	  mheap_get_trace (v, offset, n_user_data_bytes);

	  h->flags |= MHEAP_FLAG_TRACE;
	}
    }

  if (h->flags & MHEAP_FLAG_VALIDATE)
    mheap_validate (v);

  mheap_maybe_unlock (v);

  cpu_times[1] = clib_cpu_time_now ();
  h->stats.n_clocks_get += cpu_times[1] - cpu_times[0];
  h->stats.n_gets += 1;

  return v;
}

static void
free_last_elt (void *v, mheap_elt_t * e)
{
  mheap_t *h = mheap_header (v);

  /* Possibly delete preceeding free element also. */
  if (e->prev_is_free)
    {
      e = mheap_prev_elt (e);
      remove_free_elt2 (v, e);
    }

  if (e->prev_n_user_data == MHEAP_N_USER_DATA_INVALID)
    {
      if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
	mheap_vm_elt (v, MHEAP_VM_UNMAP, mheap_elt_uoffset (v, e));
      _vec_len (v) = 0;
    }
  else
    {
      uword uo = mheap_elt_uoffset (v, e);
      if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
	mheap_vm_elt (v, MHEAP_VM_UNMAP, uo);
      e->n_user_data = MHEAP_N_USER_DATA_INVALID;
      _vec_len (v) = uo;
    }
}

void
mheap_put (void *v, uword uoffset)
{
  mheap_t *h;
  uword n_user_data_bytes, bin;
  mheap_elt_t *e, *n;
  uword trace_uoffset, trace_n_user_data_bytes;
  u64 cpu_times[2];

  cpu_times[0] = clib_cpu_time_now ();

  h = mheap_header (v);

  mheap_maybe_lock (v);

  if (h->flags & MHEAP_FLAG_VALIDATE)
    mheap_validate (v);

  ASSERT (h->n_elts > 0);
  h->n_elts--;
  h->stats.n_puts += 1;

  e = mheap_elt_at_uoffset (v, uoffset);
  n = mheap_next_elt (e);
  n_user_data_bytes = mheap_elt_data_bytes (e);

  trace_uoffset = uoffset;
  trace_n_user_data_bytes = n_user_data_bytes;

  bin = user_data_size_to_bin_index (n_user_data_bytes);
  if (MHEAP_HAVE_SMALL_OBJECT_CACHE
      && bin < 255 && (h->flags & MHEAP_FLAG_SMALL_OBJECT_CACHE))
    {
      uoffset = mheap_put_small_object (h, bin, uoffset);
      if (uoffset == 0)
	goto done;

      e = mheap_elt_at_uoffset (v, uoffset);
      n = mheap_next_elt (e);
      n_user_data_bytes = mheap_elt_data_bytes (e);
    }

  /* Assert that forward and back pointers are equal. */
  if (e->n_user_data != n->prev_n_user_data)
    os_panic ();

  /* Forward and backwards is_free must agree. */
  if (e->is_free != n->prev_is_free)
    os_panic ();

  /* Object was already freed. */
  if (e->is_free)
    os_panic ();

  /* Special case: delete last element in heap. */
  if (n->n_user_data == MHEAP_N_USER_DATA_INVALID)
    free_last_elt (v, e);

  else
    {
      uword f0, f1, n_combine;

      f0 = uoffset;
      f1 = f0 + n_user_data_bytes;
      n_combine = 0;

      if (e->prev_is_free)
	{
	  mheap_elt_t *p = mheap_prev_elt (e);
	  f0 = mheap_elt_uoffset (v, p);
	  remove_free_elt2 (v, p);
	  n_combine++;
	}

      if (n->is_free)
	{
	  mheap_elt_t *m = mheap_next_elt (n);
	  f1 = (void *) m - v;
	  remove_free_elt2 (v, n);
	  n_combine++;
	}

      if (n_combine)
	mheap_elt_set_size (v, f0, f1 - f0, /* is_free */ 1);
      else
	e->is_free = n->prev_is_free = 1;
      set_free_elt (v, f0, f1 - f0);

      if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
	mheap_vm_elt (v, MHEAP_VM_UNMAP, f0);
    }

done:
  h = mheap_header (v);

  if (h->flags & MHEAP_FLAG_TRACE)
    {
      /* Recursion block for case when we are traceing main clib heap. */
      h->flags &= ~MHEAP_FLAG_TRACE;

      mheap_put_trace (v, trace_uoffset, trace_n_user_data_bytes);

      h->flags |= MHEAP_FLAG_TRACE;
    }

  if (h->flags & MHEAP_FLAG_VALIDATE)
    mheap_validate (v);

  mheap_maybe_unlock (v);

  cpu_times[1] = clib_cpu_time_now ();
  h->stats.n_clocks_put += cpu_times[1] - cpu_times[0];
}

void *
mheap_alloc_with_flags (void *memory, uword memory_size, uword flags)
{
  mheap_t *h;
  void *v;
  uword size;

  if (!mheap_page_size)
    mheap_page_size = clib_mem_get_page_size ();

  if (!memory)
    {
      /* No memory given, try to VM allocate some. */
      memory = clib_mem_vm_alloc (memory_size);
      if (!memory)
	return 0;

      /* No memory region implies we have virtual memory. */
      flags &= ~MHEAP_FLAG_DISABLE_VM;
    }

  /* Make sure that given memory is page aligned. */
  {
    uword am, av, ah;

    am = pointer_to_uword (memory);
    av = mheap_page_round (am);
    v = uword_to_pointer (av, void *);
    h = mheap_header (v);
    ah = pointer_to_uword (h);
    while (ah < am)
      ah += mheap_page_size;

    h = uword_to_pointer (ah, void *);
    v = mheap_vector (h);

    if (PREDICT_FALSE (memory + memory_size < v))
      {
	/*
	 * This will happen when the requested memory_size is too
	 * small to cope with the heap header and/or memory alignment.
	 */
	clib_mem_vm_free (memory, memory_size);
	return 0;
      }

    size = memory + memory_size - v;
  }

  /* VM map header so we can use memory. */
  if (!(flags & MHEAP_FLAG_DISABLE_VM))
    clib_mem_vm_map (h, sizeof (h[0]));

  /* Zero vector header: both heap header and vector length. */
  memset (h, 0, sizeof (h[0]));
  _vec_len (v) = 0;

  h->vm_alloc_offset_from_header = (void *) h - memory;
  h->vm_alloc_size = memory_size;

  h->max_size = size;
  h->owner_cpu = ~0;

  /* Set flags based on those given less builtin-flags. */
  h->flags |= (flags & ~MHEAP_FLAG_TRACE);

  /* Unmap remainder of heap until we will be ready to use it. */
  if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
    mheap_vm (v, MHEAP_VM_UNMAP | MHEAP_VM_ROUND_UP,
	      (clib_address_t) v, h->max_size);

  /* Initialize free list heads to empty. */
  memset (h->first_free_elt_uoffset_by_bin, 0xFF,
	  sizeof (h->first_free_elt_uoffset_by_bin));

  return v;
}

void *
mheap_alloc (void *memory, uword size)
{
  uword flags = 0;

  if (memory != 0)
    flags |= MHEAP_FLAG_DISABLE_VM;

#ifdef CLIB_HAVE_VEC128
  flags |= MHEAP_FLAG_SMALL_OBJECT_CACHE;
#endif

  return mheap_alloc_with_flags (memory, size, flags);
}

void *
_mheap_free (void *v)
{
  mheap_t *h = mheap_header (v);

  if (v)
    clib_mem_vm_free ((void *) h - h->vm_alloc_offset_from_header,
		      h->vm_alloc_size);

  return 0;
}

/* Call user's function with each object in heap. */
void
mheap_foreach (void *v,
	       uword (*func) (void *arg, void *v, void *elt_data,
			      uword elt_size), void *arg)
{
  mheap_elt_t *e;
  u8 *stack_heap, *clib_mem_mheap_save;
  u8 tmp_heap_memory[16 * 1024];

  mheap_maybe_lock (v);

  if (vec_len (v) == 0)
    goto done;

  clib_mem_mheap_save = 0;
  stack_heap = 0;

  /* Allocate a new temporary heap on the stack.
     This is so that our hash table & user's callback function can
     themselves allocate memory somewhere without getting in the way
     of the heap we are looking at. */
  if (v == clib_mem_get_heap ())
    {
      stack_heap = mheap_alloc (tmp_heap_memory, sizeof (tmp_heap_memory));
      clib_mem_mheap_save = v;
      clib_mem_set_heap (stack_heap);
    }

  for (e = v;
       e->n_user_data != MHEAP_N_USER_DATA_INVALID; e = mheap_next_elt (e))
    {
      void *p = mheap_elt_data (v, e);
      if (e->is_free)
	continue;
      if ((*func) (arg, v, p, mheap_elt_data_bytes (e)))
	break;
    }

  /* Restore main CLIB heap. */
  if (clib_mem_mheap_save)
    clib_mem_set_heap (clib_mem_mheap_save);

done:
  mheap_maybe_unlock (v);
}

/* Bytes in mheap header overhead not including data bytes. */
always_inline uword
mheap_bytes_overhead (void *v)
{
  mheap_t *h = mheap_header (v);
  return v ? sizeof (h[0]) + h->n_elts * sizeof (mheap_elt_t) : 0;
}

/* Total number of bytes including both data and overhead. */
uword
mheap_bytes (void *v)
{
  return mheap_bytes_overhead (v) + vec_bytes (v);
}

static void
mheap_usage_no_lock (void *v, clib_mem_usage_t * usage)
{
  mheap_t *h = mheap_header (v);
  uword used = 0, free = 0, free_vm_unmapped = 0;

  if (vec_len (v) > 0)
    {
      mheap_elt_t *e;

      for (e = v;
	   e->n_user_data != MHEAP_N_USER_DATA_INVALID;
	   e = mheap_next_elt (e))
	{
	  uword size = mheap_elt_data_bytes (e);
	  if (e->is_free)
	    {
	      free += size;
	      if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
		free_vm_unmapped +=
		  mheap_vm_elt (v, MHEAP_VM_NOMAP, mheap_elt_uoffset (v, e));
	    }
	  else
	    used += size;
	}
    }

  usage->object_count = mheap_elts (v);
  usage->bytes_total = mheap_bytes (v);
  usage->bytes_overhead = mheap_bytes_overhead (v);
  usage->bytes_max = mheap_max_size (v);
  usage->bytes_used = used;
  usage->bytes_free = free;
  usage->bytes_free_reclaimed = free_vm_unmapped;
}

void
mheap_usage (void *v, clib_mem_usage_t * usage)
{
  mheap_maybe_lock (v);
  mheap_usage_no_lock (v, usage);
  mheap_maybe_unlock (v);
}

static u8 *
format_mheap_byte_count (u8 * s, va_list * va)
{
  uword n_bytes = va_arg (*va, uword);
  if (n_bytes < 1024)
    return format (s, "%wd", n_bytes);
  else
    return format (s, "%wdk", n_bytes / 1024);
}

/* Returns first corrupt heap element. */
static mheap_elt_t *
mheap_first_corrupt (void *v)
{
  mheap_elt_t *e, *n;

  if (vec_len (v) == 0)
    return 0;

  e = v;
  while (1)
    {
      if (e->n_user_data == MHEAP_N_USER_DATA_INVALID)
	break;

      n = mheap_next_elt (e);

      if (e->n_user_data != n->prev_n_user_data)
	return e;

      if (e->is_free != n->prev_is_free)
	return e;

      e = n;
    }

  return 0;
}

static u8 *
format_mheap_stats (u8 * s, va_list * va)
{
  mheap_t *h = va_arg (*va, mheap_t *);
  mheap_stats_t *st = &h->stats;
  u32 indent = format_get_indent (s);

  s =
    format (s,
	    "alloc. from small object cache: %Ld hits %Ld attempts (%.2f%%) replacements %d",
	    st->n_small_object_cache_hits, st->n_small_object_cache_attempts,
	    (st->n_small_object_cache_attempts !=
	     0 ? 100. * (f64) st->n_small_object_cache_hits /
	     (f64) st->n_small_object_cache_attempts : 0.),
	    h->small_object_cache.replacement_index);

  s =
    format (s,
	    "\n%Ualloc. from free-list: %Ld attempts, %Ld hits (%.2f%%), %Ld considered (per-attempt %.2f)",
	    format_white_space, indent, st->free_list.n_search_attempts,
	    st->free_list.n_objects_found,
	    (st->free_list.n_search_attempts !=
	     0 ? 100. * (f64) st->free_list.n_objects_found /
	     (f64) st->free_list.n_search_attempts : 0.),
	    st->free_list.n_objects_searched,
	    (st->free_list.n_search_attempts !=
	     0 ? (f64) st->free_list.n_objects_searched /
	     (f64) st->free_list.n_search_attempts : 0.));

  s = format (s, "\n%Ualloc. from vector-expand: %Ld",
	      format_white_space, indent, st->n_vector_expands);

  s = format (s, "\n%Uallocs: %Ld %.2f clocks/call",
	      format_white_space, indent,
	      st->n_gets, (f64) st->n_clocks_get / (f64) st->n_gets);

  s = format (s, "\n%Ufrees: %Ld %.2f clocks/call",
	      format_white_space, indent,
	      st->n_puts, (f64) st->n_clocks_put / (f64) st->n_puts);

  return s;
}

u8 *
format_mheap (u8 * s, va_list * va)
{
  void *v = va_arg (*va, u8 *);
  int verbose = va_arg (*va, int);

  mheap_t *h;
  uword i, size, indent;
  clib_mem_usage_t usage;
  mheap_elt_t *first_corrupt;

  mheap_maybe_lock (v);

  h = mheap_header (v);

  mheap_usage_no_lock (v, &usage);

  indent = format_get_indent (s);

  s =
    format (s,
	    "%d objects, %U of %U used, %U free, %U reclaimed, %U overhead",
	    usage.object_count, format_mheap_byte_count, usage.bytes_used,
	    format_mheap_byte_count, usage.bytes_total,
	    format_mheap_byte_count, usage.bytes_free,
	    format_mheap_byte_count, usage.bytes_free_reclaimed,
	    format_mheap_byte_count, usage.bytes_overhead);

  if (usage.bytes_max != ~0)
    s = format (s, ", %U capacity", format_mheap_byte_count, usage.bytes_max);

  /* Show histogram of sizes. */
  if (verbose > 1)
    {
      uword hist[MHEAP_N_BINS];
      mheap_elt_t *e;
      uword i, n_hist;

      memset (hist, 0, sizeof (hist));

      n_hist = 0;
      for (e = v;
	   e->n_user_data != MHEAP_N_USER_DATA_INVALID;
	   e = mheap_next_elt (e))
	{
	  uword n_user_data_bytes = mheap_elt_data_bytes (e);
	  uword bin = user_data_size_to_bin_index (n_user_data_bytes);
	  if (!e->is_free)
	    {
	      hist[bin] += 1;
	      n_hist += 1;
	    }
	}

      s = format (s, "\n%U%=12s%=12s%=16s",
		  format_white_space, indent + 2,
		  "Size", "Count", "Fraction");

      for (i = 0; i < ARRAY_LEN (hist); i++)
	{
	  if (hist[i] == 0)
	    continue;
	  s = format (s, "\n%U%12d%12wd%16.4f",
		      format_white_space, indent + 2,
		      MHEAP_MIN_USER_DATA_BYTES +
		      i * MHEAP_USER_DATA_WORD_BYTES, hist[i],
		      (f64) hist[i] / (f64) n_hist);
	}
    }

  if (verbose)
    s = format (s, "\n%U%U",
		format_white_space, indent + 2, format_mheap_stats, h);

  if ((h->flags & MHEAP_FLAG_TRACE) && vec_len (h->trace_main.traces) > 0)
    {
      /* Make a copy of traces since we'll be sorting them. */
      mheap_trace_t *t, *traces_copy;
      u32 indent, total_objects_traced;

      traces_copy = vec_dup (h->trace_main.traces);
      qsort (traces_copy, vec_len (traces_copy), sizeof (traces_copy[0]),
	     mheap_trace_sort);

      total_objects_traced = 0;
      s = format (s, "\n");
      vec_foreach (t, traces_copy)
      {
	/* Skip over free elements. */
	if (t->n_allocations == 0)
	  continue;

	total_objects_traced += t->n_allocations;

	/* When not verbose only report allocations of more than 1k. */
	if (!verbose && t->n_bytes < 1024)
	  continue;

	if (t == traces_copy)
	  s = format (s, "%=9s%=9s %=10s Traceback\n", "Bytes", "Count",
		      "Sample");
	s = format (s, "%9d%9d %p", t->n_bytes, t->n_allocations,
		    t->offset + v);
	indent = format_get_indent (s);
	for (i = 0; i < ARRAY_LEN (t->callers) && t->callers[i]; i++)
	  {
	    if (i > 0)
	      s = format (s, "%U", format_white_space, indent);
#ifdef CLIB_UNIX
	    s =
	      format (s, " %U\n", format_clib_elf_symbol_with_address,
		      t->callers[i]);
#else
	    s = format (s, " %p\n", t->callers[i]);
#endif
	  }
      }

      s = format (s, "%d total traced objects\n", total_objects_traced);

      vec_free (traces_copy);
    }

  first_corrupt = mheap_first_corrupt (v);
  if (first_corrupt)
    {
      size = mheap_elt_data_bytes (first_corrupt);
      s = format (s, "\n  first corrupt object: %p, size %wd\n  %U",
		  first_corrupt, size, format_hex_bytes, first_corrupt, size);
    }

  /* FIXME.  This output could be wrong in the unlikely case that format
     uses the same mheap as we are currently inspecting. */
  if (verbose > 1)
    {
      mheap_elt_t *e;
      uword i, o;

      s = format (s, "\n");

      e = mheap_elt_at_uoffset (v, 0);
      i = 0;
      while (1)
	{
	  if ((i % 8) == 0)
	    s = format (s, "%8d: ", i);

	  o = mheap_elt_uoffset (v, e);

	  if (e->is_free)
	    s = format (s, "(%8d) ", o);
	  else
	    s = format (s, " %8d  ", o);

	  if ((i % 8) == 7 || (i + 1) >= h->n_elts)
	    s = format (s, "\n");
	}
    }

  mheap_maybe_unlock (v);

  return s;
}

void
dmh (void *v)
{
  fformat (stderr, "%U", format_mheap, v, 1);
}

static void
mheap_validate_breakpoint ()
{
  os_panic ();
}

void
mheap_validate (void *v)
{
  mheap_t *h = mheap_header (v);
  uword i, s;

  uword elt_count, elt_size;
  uword free_count_from_free_lists, free_size_from_free_lists;
  uword small_elt_free_count, small_elt_free_size;

#define CHECK(x) if (! (x)) { mheap_validate_breakpoint (); os_panic (); }

  if (vec_len (v) == 0)
    return;

  mheap_maybe_lock (v);

  /* Validate number of elements and size. */
  free_size_from_free_lists = free_count_from_free_lists = 0;
  for (i = 0; i < ARRAY_LEN (h->first_free_elt_uoffset_by_bin); i++)
    {
      mheap_elt_t *e, *n;
      uword is_first;

      CHECK ((h->first_free_elt_uoffset_by_bin[i] != MHEAP_GROUNDED)
	     ==
	     ((h->non_empty_free_elt_heads[i /
					   BITS (uword)] & ((uword) 1 <<
							    (uword) (i %
								     BITS
								     (uword))))
	      != 0));

      if (h->first_free_elt_uoffset_by_bin[i] == MHEAP_GROUNDED)
	continue;

      e = mheap_elt_at_uoffset (v, h->first_free_elt_uoffset_by_bin[i]);
      is_first = 1;
      while (1)
	{
	  uword s;

	  n = mheap_next_elt (e);

	  /* Object must be marked free. */
	  CHECK (e->is_free);

	  /* Next object's previous free bit must also be set. */
	  CHECK (n->prev_is_free);

	  if (is_first)
	    CHECK (e->free_elt.prev_uoffset == MHEAP_GROUNDED);
	  is_first = 0;

	  s = mheap_elt_data_bytes (e);
	  CHECK (user_data_size_to_bin_index (s) == i);

	  free_count_from_free_lists += 1;
	  free_size_from_free_lists += s;

	  if (e->free_elt.next_uoffset == MHEAP_GROUNDED)
	    break;

	  n = mheap_elt_at_uoffset (v, e->free_elt.next_uoffset);

	  /* Check free element linkages. */
	  CHECK (n->free_elt.prev_uoffset == mheap_elt_uoffset (v, e));

	  e = n;
	}
    }

  /* Go through small object cache. */
  small_elt_free_count = small_elt_free_size = 0;
  for (i = 0; i < ARRAY_LEN (h->small_object_cache.bins.as_u8); i++)
    {
      if (h->small_object_cache.bins.as_u8[i] != 0)
	{
	  mheap_elt_t *e;
	  uword b = h->small_object_cache.bins.as_u8[i] - 1;
	  uword o = h->small_object_cache.offsets[i];
	  uword s;

	  e = mheap_elt_at_uoffset (v, o);

	  /* Object must be allocated. */
	  CHECK (!e->is_free);

	  s = mheap_elt_data_bytes (e);
	  CHECK (user_data_size_to_bin_index (s) == b);

	  small_elt_free_count += 1;
	  small_elt_free_size += s;
	}
    }

  {
    mheap_elt_t *e, *n;
    uword elt_free_size, elt_free_count;

    elt_count = elt_size = elt_free_size = elt_free_count = 0;
    for (e = v; e->n_user_data != MHEAP_N_USER_DATA_INVALID; e = n)
      {
	if (e->prev_n_user_data != MHEAP_N_USER_DATA_INVALID)
	  CHECK (e->prev_n_user_data * sizeof (e->user_data[0]) >=
		 MHEAP_MIN_USER_DATA_BYTES);

	CHECK (e->n_user_data * sizeof (e->user_data[0]) >=
	       MHEAP_MIN_USER_DATA_BYTES);

	n = mheap_next_elt (e);

	CHECK (e->is_free == n->prev_is_free);

	elt_count++;
	s = mheap_elt_data_bytes (e);
	elt_size += s;

	if (e->is_free)
	  {
	    elt_free_count++;
	    elt_free_size += s;
	  }

	/* Consecutive free objects should have been combined. */
	CHECK (!(e->prev_is_free && n->prev_is_free));
      }

    CHECK (free_count_from_free_lists == elt_free_count);
    CHECK (free_size_from_free_lists == elt_free_size);
    CHECK (elt_count == h->n_elts + elt_free_count + small_elt_free_count);
    CHECK (elt_size + (elt_count + 1) * MHEAP_ELT_OVERHEAD_BYTES ==
	   vec_len (v));
  }

  {
    mheap_elt_t *e, *n;

    for (e = v; e->n_user_data == MHEAP_N_USER_DATA_INVALID; e = n)
      {
	n = mheap_next_elt (e);
	CHECK (e->n_user_data == n->prev_n_user_data);
      }
  }

#undef CHECK

  mheap_maybe_unlock (v);

  h->validate_serial += 1;
}

static void
mheap_get_trace (void *v, uword offset, uword size)
{
  mheap_t *h;
  mheap_trace_main_t *tm;
  mheap_trace_t *t;
  uword i, n_callers, trace_index, *p;
  mheap_trace_t trace;

  /* Spurious Coverity warnings be gone. */
  memset (&trace, 0, sizeof (trace));

  n_callers = clib_backtrace (trace.callers, ARRAY_LEN (trace.callers),
			      /* Skip mheap_get_aligned's frame */ 1);
  if (n_callers == 0)
    return;

  for (i = n_callers; i < ARRAY_LEN (trace.callers); i++)
    trace.callers[i] = 0;

  h = mheap_header (v);
  tm = &h->trace_main;

  if (!tm->trace_by_callers)
    tm->trace_by_callers =
      hash_create_mem (0, sizeof (trace.callers), sizeof (uword));

  p = hash_get_mem (tm->trace_by_callers, &trace.callers);
  if (p)
    {
      trace_index = p[0];
      t = tm->traces + trace_index;
    }
  else
    {
      i = vec_len (tm->trace_free_list);
      if (i > 0)
	{
	  trace_index = tm->trace_free_list[i - 1];
	  _vec_len (tm->trace_free_list) = i - 1;
	}
      else
	{
	  mheap_trace_t *old_start = tm->traces;
	  mheap_trace_t *old_end = vec_end (tm->traces);

	  vec_add2 (tm->traces, t, 1);

	  if (tm->traces != old_start)
	    {
	      hash_pair_t *p;
	      mheap_trace_t *q;
            /* *INDENT-OFF* */
	    hash_foreach_pair (p, tm->trace_by_callers,
            ({
              q = uword_to_pointer (p->key, mheap_trace_t *);
              ASSERT (q >= old_start && q < old_end);
	      p->key = pointer_to_uword (tm->traces + (q - old_start));
	    }));
            /* *INDENT-ON* */
	    }
	  trace_index = t - tm->traces;
	}

      t = tm->traces + trace_index;
      t[0] = trace;
      t->n_allocations = 0;
      t->n_bytes = 0;
      hash_set_mem (tm->trace_by_callers, t->callers, trace_index);
    }

  t->n_allocations += 1;
  t->n_bytes += size;
  t->offset = offset;		/* keep a sample to autopsy */
  hash_set (tm->trace_index_by_offset, offset, t - tm->traces);
}

static void
mheap_put_trace (void *v, uword offset, uword size)
{
  mheap_t *h;
  mheap_trace_main_t *tm;
  mheap_trace_t *t;
  uword trace_index, *p;

  h = mheap_header (v);
  tm = &h->trace_main;
  p = hash_get (tm->trace_index_by_offset, offset);
  if (!p)
    return;

  trace_index = p[0];
  hash_unset (tm->trace_index_by_offset, offset);
  ASSERT (trace_index < vec_len (tm->traces));

  t = tm->traces + trace_index;
  ASSERT (t->n_allocations > 0);
  ASSERT (t->n_bytes >= size);
  t->n_allocations -= 1;
  t->n_bytes -= size;
  if (t->n_allocations == 0)
    {
      hash_unset_mem (tm->trace_by_callers, t->callers);
      vec_add1 (tm->trace_free_list, trace_index);
      memset (t, 0, sizeof (t[0]));
    }
}

static int
mheap_trace_sort (const void *_t1, const void *_t2)
{
  const mheap_trace_t *t1 = _t1;
  const mheap_trace_t *t2 = _t2;
  word cmp;

  cmp = (word) t2->n_bytes - (word) t1->n_bytes;
  if (!cmp)
    cmp = (word) t2->n_allocations - (word) t1->n_allocations;
  return cmp;
}

always_inline void
mheap_trace_main_free (mheap_trace_main_t * tm)
{
  vec_free (tm->traces);
  vec_free (tm->trace_free_list);
  hash_free (tm->trace_by_callers);
  hash_free (tm->trace_index_by_offset);
}

void
mheap_trace (void *v, int enable)
{
  mheap_t *h;

  h = mheap_header (v);

  if (enable)
    {
      h->flags |= MHEAP_FLAG_TRACE;
    }
  else
    {
      mheap_trace_main_free (&h->trace_main);
      h->flags &= ~MHEAP_FLAG_TRACE;
    }
}

/*
 * fd.io coding-style-patch-verification: ON
 *
 * Local Variables:
 * eval: (c-set-style "gnu")
 * End:
 */