I love libdivide. Moving to libdivide-2.0 in hardened_malloc is an easy win.
16 byte malloc microbenchmark on Broadwell-E:
Hardware division: 1s
libdivide-1.1: 0.74s
libdivide-2.0: 0.71s
In a lightweight build:
Hardware division: 1s
libdivide-1.1: 0.62s
libdivide-2.0: 0.59s
Conversation
This is comparing to hardware-based division on a modern x86 CPU... so consider how much difference it makes on hardware without hardware-based division. The entire library is a single header with ~1.4k lines of code (~760 without C++ and SSE/AVX). Did I mention it's awesome?
1
6
It gives you compiler-style optimizations for division by a constant where the divisor is a runtime constant rather than a compile-time constant. In hardened_malloc, I use it to quickly perform division by the allocation size and slab size. It makes the out-of-line metadata fast.
2
4
Replying to
Wouldn't it be preferable to generate the constants statically at build time for all possible sizes rather than having wasteful init code and copies per process?
1
Replying to
The libdivide divisor structs are tiny: github.com/ridiculousfish. I could make a script to generate a constant array of these, but it wouldn't necessarily be faster and the memory usage isn't significant since it's just 2 of these structs for each size class allocator as a whole.
1
I have a lot of lower hanging fruit to address before considering that kind of micro-optimization. It's these 2 fields in the per-size-class slab allocator: github.com/GrapheneOS/har. It could be another one of these tables if I generated it when building: github.com/GrapheneOS/har.
1
Replying to
Imagine what happens if an attacker can corrupt the constants. Semantic constants should always be real rodata constants.
1
Replying to
The entirety of the mutable hardened_malloc state is in a statically allocated, dedicated metadata region that's never reused or mixed with anything else. There is no threat model where these being in there has any relevance to security. An attacker has no reason to mess with it.
1
The metadata region has a high entropy random base within a guard region and is only referenced via the `ro` global. If an attacker has arbitrary read and write primitives, they're beyond needing to target malloc metadata. If for some reason they do, the divisors don't matter.
1
Look at the 2 pointer fields above the divisors, both of which are runtime constants:
github.com/GrapheneOS/har
One points to the start of the size class region and the other to the metadata array within this metadata region. The intrusive lists are threaded through that array.
I could dedicate a page to those runtime constants to make them read-only like all the state in globals: github.com/GrapheneOS/har. I just don't have any reason to do it. There's also support for sealing / unsealing the entire metadata region via MPK but it doesn't accomplish much.
1
If CONFIG_SEAL_METADATA is enabled, MPK is used to make the metadata region inaccessible (no read or write), and it only toggles on thread-local access within malloc. It's not enabled by default because it doesn't accomplish much when it's already a dedicated, isolated region.
1
Show replies