/* * 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 #include #include #include #include #include #ifdef CLIB_UNIX #include #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
"""
  Neighbour Entries

  object abstractions for ARP and ND
"""

from socket import inet_pton, inet_ntop, AF_INET, AF_INET6
from vpp_object import *
from util import mactobinary


def find_nbr(test, sw_if_index, ip_addr, is_static=0, inet=AF_INET, mac=None):
    nbrs = test.vapi.ip_neighbor_dump(sw_if_index,
                                      is_ipv6=1 if AF_INET6 == inet else 0)
    if inet == AF_INET:
        s = 4
    else:
        s = 16
    nbr_addr = inet_pton(inet, ip_addr)

    for n in nbrs:
        if nbr_addr == n.ip_address[:s] \
           and is_static == n.is_static:
            if mac:
                if n.mac_address == mactobinary(mac):
                    return True
            else:
                return True
    return False


class VppNeighbor(VppObject):
    """
    ARP Entry
    """

    def __init__(self, test, sw_if_index, mac_addr, nbr_addr,
                 af=AF_INET, is_static=False, is_no_fib_entry=0):
        self._test = test
        self.sw_if_index = sw_if_index
        self.mac_addr = mactobinary(mac_addr)
        self.af = af
        self.is_static = is_static
        self.is_no_fib_entry = is_no_fib_entry
        self.nbr_addr = nbr_addr
        self.nbr_addr_n = inet_pton(af, nbr_addr)

    def add_vpp_config(self):
        r = self._test.vapi.ip_neighbor_add_del(
            self.sw_if_index,
            self.mac_addr,
            self.nbr_addr_n,
            is_add=1,
            is_ipv6=1 if AF_INET6 == self.af else 0,
            is_static=self.is_static,
            is_no_adj_fib=self.is_no_fib_entry)
        self.stats_index = r.stats_index
        self._test.registry.register(self, self._test.logger)

    def remove_vpp_config(self):
        self._test.vapi.ip_neighbor_add_del(
            self.sw_if_index,
            self.mac_addr,
            self.nbr_addr_n,
            is_ipv6=1 if AF_INET6 == self.af else 0,
            is_add=0,
            is_static=self.is_static)

    def query_vpp_config(self):
        return find_nbr(self._test,
                        self.sw_if_index,
                        self.nbr_addr,
                        self.is_static,
                        self.af)

    def __str__(self):
        return self.object_id()

    def object_id(self):
        return ("%d:%s" % (self.sw_if_index, self.nbr_addr))

    def get_stats(self):
        c = self._test.statistics.get_counter("/net/adjacency")
        return c[0][self.stats_index]
_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; u32 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: */