/* * 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 #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 (clib_atomic_test_and_set (&h->lock)) CLIB_PAUSE (); 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_atomic_release (&h->lock); } } } /* 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_a
/*---------------------------------------------------------------------------
 * Copyright (c) 2009-2014 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.
 *---------------------------------------------------------------------------
 */
/*
 * IPv4 and IPv6 Fragmentation Nodes
 *
 * A packet sent to those nodes require the following
 * buffer attributes to be set:
 * ip_frag.header_offset :
 *     Where to find the IPv4 (or IPv6) header in the packet. Previous
 *     bytes are left untouched and copied in every fragment. The fragments
 *     are then appended. This option is used for fragmented packets
 *     that are encapsulated.
 * ip_frag.mtu :
 *     Maximum size of IP packets, header included, but ignoring
 *     the 'ip_frag.header_offset' copied bytes.
 * ip_frag.next_index :
 *     One of ip_frag_next_t, indicating to which exit node the fragments
 *     should be sent to.
 *
 */

#ifndef IP_FRAG_H
#define IP_FRAG_H

#include <vnet/vnet.h>
#include <vnet/ip/ip.api_enum.h>

#define IP_FRAG_FLAG_IP4_HEADER 0x01	//Encapsulating IPv4 header
#define IP_FRAG_FLAG_IP6_HEADER 0x02	//Encapsulating IPv6 header

#define IP4_FRAG_NODE_NAME "ip4-frag"
#define IP6_FRAG_NODE_NAME "ip6-frag"

extern vlib_node_registration_t ip4_frag_node;
extern vlib_node_registration_t ip6_frag_node;

typedef enum
{
  IP_FRAG_NEXT_IP_REWRITE,
  IP_FRAG_NEXT_IP_REWRITE_MIDCHAIN,
  IP_FRAG_NEXT_IP4_LOOKUP,
  IP_FRAG_NEXT_IP6_LOOKUP,
  IP_FRAG_NEXT_ICMP_ERROR,
  IP_FRAG_NEXT_DROP,
  IP_FRAG_N_NEXT
} ip_frag_next_t;

typedef vl_counter_ip_frag_enum_t ip_frag_error_t;

void ip_frag_set_vnet_buffer (vlib_buffer_t * b, u16 mtu,
			      u8 next_index, u8 flags);

extern ip_frag_error_t ip4_frag_do_fragment (vlib_main_t * vm,
					     u32 from_bi,
					     u16 mtu,
					     u16 encapsize, u32 ** buffer);
extern ip_frag_error_t ip6_frag_do_fragment (vlib_main_t * vm,
					     u32 from_bi,
					     u16 mtu,
					     u16 encapsize, u32 ** buffer);

#endif /* ifndef IP_FRAG_H */

/*
 * fd.io coding-style-patch-verification: ON
 *
 * Local Variables:
 * eval: (c-set-style "gnu")
 * End:
 */
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. */ clib_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. */ clib_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_alloc_with_lock (void *memory, uword size, int locked) { uword flags = 0; void *rv; if (memory != 0) flags |= MHEAP_FLAG_DISABLE_VM; #ifdef CLIB_HAVE_VEC128 flags |= MHEAP_FLAG_SMALL_OBJECT_CACHE; #endif rv = mheap_alloc_with_flags (memory, size, flags); if (rv && locked) { mheap_t *h = mheap_header (rv); h->flags |= MHEAP_FLAG_THREAD_SAFE; } return rv; } 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; 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; clib_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. */ clib_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_shmem (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); clib_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: */