UMASH: a fast and universal enough hash

We accidentally a whole hash function… but we had a good reason! Our MIT-licensed UMASH hash function is a decently fast non-cryptographic hash function that guarantees a worst-case bound on the probability of collision between any two inputs generated independently of the UMASH parameters. On the 2.5 GHz Intel 8175M servers that power Backtrace’s hosted offering, UMASH computes a 64-bit hash for short cached inputs of up to 64 bytes in 9-22 ns, and for longer ones at up to 22 GB/s, while guaranteeing that two distinct inputs of at most \(s\) bytes collide with probability less than \(\lceil s / 2048 \rceil \cdot 2^{-56}\)....

Triplefault: Djordje Todorovic on LLVM and debug information

Join us July 23rd at 4PM ET (8PM UTC), as Djordje Todorovic joins me to discuss the state of debug information in LLVM and the work that is happening to improve it. The event will be livestreamed at Triplefault. LLVM is a popular compiler backend that is the basis for toolchain across the Apple ecosystem, popular game consoles and more. Compared to compilers such as gcc, the quality of debug information in the presence of optimizations has historically been very poor for LLVM-based compilers....

How hard is it to guide test case generators with branch coverage feedback?

To make a long story short, it’s almost easy, now that tracing is available on commodity hardware, especially with a small library to handle platform-specific setup. Here’s a graph of the empirical distribution functions for the number of calls into OpenSSL 1.0.1f it takes for Hypothesis to find Heartbleed, given a description of the format for Heartbeat requests (“grammar”), and the same with additional branch coverage feedback (“bts”, for Intel Branch Trace Store)....

Talk: What every programmer should know about malloc

At CPPCon 2019, Samy Al Bahra, Paul Khuong and Hannes Frederic Sowa collaborated on presenting the foundations of malloc and the tips that helped them improve performance in the real world. Abstract Memory allocators are a critical part of the run-time system for languages such as C++. Over the last few decades, the requirements for general-purpose memory allocation have become significantly more complex with different allocators evolving to handle different workloads varying by process age, concurrency, allocation patterns, object sizes, access patterns and more....

Talk: Abusing your memory model for fun and profit

The most efficient concurrent C++ data structures used in the wild today usually achieve break-neck performance by either constraining their workload or constraining correctness to a particular memory model. At CPPCon 2019, Paul Khuong and Samy Al Bahra collaborated on a talk sharing success stories of workload specialization in real-world workloads over the last few years. Abstract The most efficient concurrent C++ data structures used in the wild today usually achieve break-neck performance by either constraining their workload or constraining correctness to a particular memory model....

A Workflow for Memory Error Checking

Memory error detection technologies such as valgrind and address sanitizer are a critical part of the toolkit for programmers doing manual memory management. These tools allow you to detect memory access errors, memory management bugs, race conditions and more, in your programs. They are heavily used in companies developing high quality software such as Google, Facebook, Mozilla and more. A general problem with all these tools is that there is no easy way to aggregate their errors and action on them....

Debug Information is Huge and What to do About It

Debug information is used by symbolic debuggers and the Backtrace platform to reconcile process executable state to the source-code form that is familiar to most software engineers. This information is responsible for mapping memory addresses and register values to function names, source code locations and describing variables. Some environments choose to omit debug information. Of the many reasons, the typically valid reasons are disk utilization and arguably, intellectual property protection....

Compile Once Debug Twice: Picking a compiler for debuggability

Have you ever had an assert get triggered only to result in a useless core dump with missing variable information or an invalid callstack? Common factors that go into selecting a C or C++ compiler are: availability, correctness, compilation speed and application performance. A factor that is often neglected is debug information quality, which symbolic debuggers use to reconcile application executable state to the source-code form that is familiar to most software engineers....

Building a Go Debugger

Earlier this year we published a post titled Implementing A Debugger: The Fundamentals. This post gave an overview of debuggers, what they do, and how they work. In today’s post, we build upon this knowledge and talk about our journey of extending Backtrace’s debugger to support Go. Intro If you have the time and haven’t read Implement A Debugger: The Fundemantals, we highly recommend you do so. This post builds upon terms and knowledge discussed there....

Post-Mortem Analysis: Stale Pointer Detection

We’ve previously posted a few blogs covering memory management, memory bugs, and post-mortem memory analysis. Now, we are excited to add another memory debug tool to Backtrace’s offering: stale pointer analysis. In this post, I will explain how this analysis works, its strengths, and its limitations. Introduction Among many memory errors, stale pointer is one of the subtlest and most difficult to debug. It happens when a memory region is freed or reallocated but the old references, aka aliases, to the memory are not updated properly....