10d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko// Copyright 2015 The Chromium Authors. All rights reserved. 20d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko// Use of this source code is governed by a BSD-style license that can be 30d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko// found in the LICENSE file. 40d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 50d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko#include "base/trace_event/heap_profiler_allocation_context.h" 60d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 70d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko#include <cstring> 80d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 90d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko#include "base/hash.h" 100d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko#include "base/macros.h" 110d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 120d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenkonamespace base { 130d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenkonamespace trace_event { 140d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 1594ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavezbool operator < (const StackFrame& lhs, const StackFrame& rhs) { 1694ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez return lhs.value < rhs.value; 1794ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez} 180d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 1994ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavezbool operator == (const StackFrame& lhs, const StackFrame& rhs) { 2094ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez return lhs.value == rhs.value; 2194ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez} 220d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 2394ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavezbool operator != (const StackFrame& lhs, const StackFrame& rhs) { 2494ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez return !(lhs.value == rhs.value); 250d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko} 260d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 2794ffa55491333f3dcc701befd0d2652922916d99Luis Hector ChavezBacktrace::Backtrace(): frame_count(0) {} 2894ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez 290d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenkobool operator==(const Backtrace& lhs, const Backtrace& rhs) { 3094ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez if (lhs.frame_count != rhs.frame_count) return false; 3194ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez return std::equal(lhs.frames, lhs.frames + lhs.frame_count, rhs.frames); 320d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko} 330d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 340c4f26a46430b8c503c65f5cae1d2b6876d53e30Luis Hector Chavezbool operator!=(const Backtrace& lhs, const Backtrace& rhs) { 350c4f26a46430b8c503c65f5cae1d2b6876d53e30Luis Hector Chavez return !(lhs == rhs); 360c4f26a46430b8c503c65f5cae1d2b6876d53e30Luis Hector Chavez} 370c4f26a46430b8c503c65f5cae1d2b6876d53e30Luis Hector Chavez 3894ffa55491333f3dcc701befd0d2652922916d99Luis Hector ChavezAllocationContext::AllocationContext(): type_name(nullptr) {} 3994ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez 400c4f26a46430b8c503c65f5cae1d2b6876d53e30Luis Hector ChavezAllocationContext::AllocationContext(const Backtrace& backtrace, 410c4f26a46430b8c503c65f5cae1d2b6876d53e30Luis Hector Chavez const char* type_name) 420c4f26a46430b8c503c65f5cae1d2b6876d53e30Luis Hector Chavez : backtrace(backtrace), type_name(type_name) {} 430c4f26a46430b8c503c65f5cae1d2b6876d53e30Luis Hector Chavez 440d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenkobool operator==(const AllocationContext& lhs, const AllocationContext& rhs) { 450d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko return (lhs.backtrace == rhs.backtrace) && (lhs.type_name == rhs.type_name); 460d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko} 470d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 480c4f26a46430b8c503c65f5cae1d2b6876d53e30Luis Hector Chavezbool operator!=(const AllocationContext& lhs, const AllocationContext& rhs) { 490c4f26a46430b8c503c65f5cae1d2b6876d53e30Luis Hector Chavez return !(lhs == rhs); 500c4f26a46430b8c503c65f5cae1d2b6876d53e30Luis Hector Chavez} 510d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko} // namespace trace_event 520d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko} // namespace base 530d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 540d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenkonamespace BASE_HASH_NAMESPACE { 550d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenkousing base::trace_event::AllocationContext; 560d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenkousing base::trace_event::Backtrace; 5794ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavezusing base::trace_event::StackFrame; 5894ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez 5994ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavezsize_t hash<StackFrame>::operator()(const StackFrame& frame) const { 6094ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez return hash<const void*>()(frame.value); 6194ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez} 620d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 630d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenkosize_t hash<Backtrace>::operator()(const Backtrace& backtrace) const { 6494ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez const void* values[Backtrace::kMaxFrameCount]; 6594ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez for (size_t i = 0; i != backtrace.frame_count; ++i) { 6694ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez values[i] = backtrace.frames[i].value; 6794ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez } 6894ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez return base::SuperFastHash( 6994ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez reinterpret_cast<const char*>(values), 7094ffa55491333f3dcc701befd0d2652922916d99Luis Hector Chavez static_cast<int>(backtrace.frame_count * sizeof(*values))); 710d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko} 720d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 730d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenkosize_t hash<AllocationContext>::operator()(const AllocationContext& ctx) const { 740d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko size_t backtrace_hash = hash<Backtrace>()(ctx.backtrace); 750d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 760d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // Multiplicative hash from [Knuth 1998]. Works best if |size_t| is 32 bits, 770d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // because the magic number is a prime very close to 2^32 / golden ratio, but 780d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // will still redistribute keys bijectively on 64-bit architectures because 790d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // the magic number is coprime to 2^64. 800d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko size_t type_hash = reinterpret_cast<size_t>(ctx.type_name) * 2654435761; 810d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 820d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // Multiply one side to break the commutativity of +. Multiplication with a 830d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // number coprime to |numeric_limits<size_t>::max() + 1| is bijective so 840d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko // randomness is preserved. 850d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko return (backtrace_hash * 3) + type_hash; 860d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko} 870d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko 880d205d712abd16eeed2f5d5b1052a367d23a223fAlex Vakulenko} // BASE_HASH_NAMESPACE 89