Fearless Security: Memory Safety
hacks.mozilla.org
hacks.mozilla.org
The particular problem is that malloc/free is not free of charge. Different allocators have complex internal implementations, plus you lose easy sharing of complex structures and compaction. So if you're using a GC you probably program in a different way, eg using more shared immutable structures, exploiting the advantages of GC.
Edit: A bit later they brush off this old favourite for GC-haters: https://people.cs.umass.edu/~emery/pubs/gcvsmalloc.pdf claiming that GC requires 5x as much memory. The problem with this paper is it assumes that malloc/free is cost-free and instantaneous, and that your programmer always calls free at the exact moment that the memory is no longer needed, both of which are extremely unrealistic.
I think this is not so unrealistic if you use RAII.
I'm not sure about your
> So if you're using a GC you probably program in a different way, eg using more shared immutable structures
This is definitely not the case for mainstream GC languages like Java, which have truly awful support for immutability, to the point of having to write a separate type if you want it.
You can see how local variables just push something onto the stack, which is a small number of CPU instructions, while malloc is a big function, each step of which translates into many instructions, and which also has to deal with iterating through a data structure to find a big enough block.
Part 8: Implementing the virtual machine, where you do stack allocation/calls: https://www.nand2tetris.org/project08
Part 12: Implementing the OS, where you add the malloc/free utilities (Memory.jack): https://www.nand2tetris.org/project12
[1] It calls them alloc and deAlloc in the course.
I think I get that you're trying to explain how GC overhead is overstated and malloc()/free() is understated but your angle about "malloc not being free of charge" it isn't really the evidence you want to use.
As analogy, we can see that a Lamborghini is faster than a Hyundai. Let's say we state that the performance comparison is flawed because it it still takes the Lamborghini a non-zero amount of time to accelerate to 60 mph (or 100 km/hr) and Lamborghini is still consuming gasoline. While the cost datapoints are true, it still doesn't change the macro observation that the Hyundai is slower.
Also, you're misrepresenting the 2nd paper you cited. The authors do mention "overhead" of malloc. They do not assume that malloc is "cost-free" on page 4:
>3.2 malloc Overhead - When using allocators implemented in C, the oracular memory manager invokes allocation and deallocation functions through the Jikes VM SysCall foreign function call interface. While not free, these calls do not incur as much overhead as JNI invocations. Their total cost is just 11 instructions: six loads and stores, three registerto-register moves, one load-immediate, and one jump. This cost is similar to that of invoking memory operations in C and C++, where malloc and free are functions defined in an external library (e.g., libc.so).
In other words, even if malloc/free is not instantaneous and not cost-free, it can still be faster than GC. Neither paper's conclusions depend on malloc/free taking zero amounts of time or zero cpu instructions. If the papers are flawed, you have to explain it using different logic.
That's not even about malloc overhead, it's about the overhead of just calling C malloc. So actual malloc overhead is on top of that.
Malloc and free have pretty unpredictable runtime over time, once a lot of allocations and deallocations have been performed. That's why you don't use either in latency sensitive code, like with realtime requirements.
> In other words, even if malloc/free is not instantaneous and not cost-free, it can still be faster than GC.
Whoah, faster than GC in what regard? GC will probably win the throughput race, or average latency. Manual allocation will likely win the jitter race, lower latency standard deviation.
(I write low level code in C/C++, including kernel drivers and bare metal firmware with hard realtime requirements. Hopefully in the future in Rust or some other memory and concurrency safe language.)
Yes, that's another true statement about malloc but it also doesn't matter to the particular point I'm making. To continue your correct & true statements of malloc, we can add:
- malloc has to search the freelist; GC can be just a bump allocation which is faster
- malloc leads to fragmented memory; GC can reorganize and reconsolidate
- malloc doesn't have extra intelligence to assign pointers to shared memory structures (e.g. Java string pool stores identical strings only once based on hashes)
- ... a dozen other true statements about malloc
All those true statements (which most can agree on) isn't the misunderstanding. The issue is misusing those true statements as some type of convincing evidence to explain the papers' flaws. For example:
>Whoah, faster than GC in what regard?
Well, we can just use the total runtime of the the 2 papers benchmarks where there were lots of memory operations. (In other words, we can acknowledge that performance has multiple dimensions/axis but we can also look at the simple measurement of total wall clock time of benchmark code that doesn't do database access or floating point calculations.)
The C/C++ programs ran faster and took up less memory.
Ok, were there flaws in the benchmarks? Then lets explain the specific flaws.
Yes, I can say "malloc runtime is unpredictable" but that true statement doesn't actually explain anything about GC running slower than malloc/free in the papers. We can also say that "malloc is not cost free" as another true statement -- but that also doesn't actually explain the GC's longer elapsed time.
See the problem with those attempted explanations? They're all non-sequiturs.
...
> See the problem with those attempted explanations? They're all non-sequiturs.
I'm comparing GC vs manual memory management.
You (or the papers) are comparing different implementations of programs in different languages. That might be great for practical considerations for choosing implementation language, but is pointless when comparing those two different memory management strategies. Apples and oranges.
EDIT: I feel "Quantifying the Performance of Garbage Collection vs. Explicit Memory Management" paper is a bit dishonest. From the paper:
> The culprit here is garbage collection activity, which visits far more pages than the application itself [61]. As allocation intensity increases, the number of major garbage collections also increases. Since each garbage collection is likely to visit pages that have been evicted, the performance gap between the garbage collectors and explicit memory managers grows as the number of major collections increases.
Pages got evicted – so their heap ran out of physical RAM and started swapping to disk. Wow.
Yeah, GC uses much more RAM, that's a well known downside. Setting the benchmark up in such a way that causes the system to start swapping is not a fair way to compare GC and manual allocation throughput.
Fyi... the 2nd paper is using the same language of Java. It just compares different allocation strategies: explicit vs GC. (I think that paper is written in a confusing way.)
My original point back to op (rwmj) was that the computer scientists were quite aware that malloc had a non-zero cost. And pointing that out really doesn't challenge the paper's findings.
So putting all on the same bag doesn't work quite well.
The benchmark keeps a large live set and allocates aggressively, making it an unattractive scenario for many GCs.
The Boehm GC is being run with the following four distinct configurations:
- Four marker threads in parallel, trading CPU time for wall clock time and lower pause times.
- Single-threaded marking.
- GC disabled, all memory is freed explicitly.
- Incremental collection (using virtual memory).
The results, run on a Macbook Pro with a six core 2.6 GHz Core i7:
$ make benchmark DEPTH=21
# jemalloc explicit malloc()/free()
/usr/bin/time ./btree-jemalloc 21 >/dev/null
17.53 real 17.40 user 0.11 sys
# Boehm GC with four parallel marker threads
GC_MARKERS=4 /usr/bin/time ./btree-gc 21 >/dev/null
8.50 real 10.87 user 0.09 sys
# Boehm GC with single-threaded marking
GC_MARKERS=1 /usr/bin/time ./btree-gc 21 >/dev/null
10.40 real 10.33 user 0.05 sys
# Boehm GC with explicit deallocation
GC_MARKERS=1 /usr/bin/time ./btree-gc-free 21 >/dev/null
11.75 real 11.70 user 0.04 sys
# Boehm GC with incremental collection (single-threaded)
/usr/bin/time ./btree-gc-inc 21 >/dev/null
18.39 real 16.40 user 5.11 sys
# System malloc()/free()
/usr/bin/time ./btree-sysmalloc 21 >/dev/null
64.43 real 63.69 user 0.71 sys
But for throughput at least, the worries about GC overhead tend to be exaggerated.
In practice, any language with proper value types will also spend only a fairly small fraction on allocation and garbage collection, so overhead becomes less of a problem.
[1] https://gist.github.com/rbehrends/528fc713c24195b1c8aefda074...
There are also programs that allocate but never we-allocate memory. They are fast-terminating programs, ranging from a CLI utility to onboard software that controls a surface-to-air rocket.
But many programs still need more complex memory management done safely.
#include <string.h>
#include <stdio.h>
int main() {
char hello[5];
strcpy(hello, "hello");
printf("%s\n", hello);
}
(gcc warns about, interestingly clang does not)
If we want to be pedantic, all this talk of "fearless" wrt Rust is dangerous hyperbole. Once you move past juggling scalar values things get dicey, especially in C but also in so-called "safe" languages like Rust. And that, I think, was the previous poster's point--as you move away from dynamic allocation you tend to move toward using scalar (fixed-sized) objects.
One of the original points of emphasis of Rust was to favor scalar values rather than pointers and even references. To a limited but useful extent you can mimic this in C. Rust examples that simply use Vec miss the point--1) the str::repeat bug overflowed a Vec, and 2) just because C doesn't come with a built-in Vec doesn't mean you can't write one or use one.
In case someone is interested of the details, like I was: http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2018-10008...
This is completely misleading. The unsound check for integer overflow[0] was in 'safe' code but just because the code is not in an unsafe block does not absolve you of any potential bugs, and the subsequent writes to memory that were in an unsafe block clearly did not care about prior mistakes that were made. The PR that introduced the vulnerability[1] was due from switching a safe method to one that uses unsafe for performance reasons, I suggest checking out the commits for both the introduction of this bug as well as the commit that fixed it as they're both short and the actual bug only occurs on one short line.
It's also worth noting that the vulnerability could have been found using a fuzzer[2] that did not exist (for Rust) at the time but that does now exist, and that integer overflows are checked for on debug builds (but not for release builds by default, again due to performance reasons) but that in this particular vulnerability it would have been extremely unlikely that any legitimate code would have triggered this integer overflow.
The take away here isn't that 'even 'safe' languages get it wrong', but that unsafe operations are difficult to do correctly, and that's true in either C or Rust. There's further discussion[3] on this bug if anybody is interested.
[0] https://github.com/rust-lang/rust/pull/54397
[1] https://github.com/rust-lang/rust/pull/48657
[2] https://medium.com/@shnatsel/how-ive-found-vulnerability-in-...
[3] https://internals.rust-lang.org/t/pre-rfc-fixed-capacity-vie...
Move the declaration out of main and declare it statically. And, of course, don't copy large buffers into small ones.
https://www.fos.kuis.kyoto-u.ac.jp/~tanki/papers/memoryleak....
Well, that took about a minute in DuckDuckGo. :) Key words were "memory leaks" and "type system." For those wanting to find CompSci, adding type system in quotes to a property is a reliable way to find language work on that property. The word language can help, too, but the wording in PDF's varies on that more.
A major source of vulnerabilities is (still) the Javascript engine and that's (still) written in C++.
Even worse, as far as I know, Mozilla has no plans to rewrite even parts of Spidermonkey in Rust.
For some recent examples:
Here's a substantial part being rewritten in rust by Mozilla: https://github.com/CraneStation/cranelift/blob/master/spider...
I stand corrected though, every little bit helps. Here's hope they'll start using Rust in more places where it counts.
https://bugzilla.mozilla.org/show_bug.cgi?id=1493900
https://bugzilla.mozilla.org/show_bug.cgi?id=1493903
To be fair I'm not actually sure rust would fix either of the CVEs I linked. Both being about problems in the generated code (as I understand them from a glance), which is something inherently unsafe to do.
Edit: I realized you might be picking out the word "ARM" on that page. I know Crainlift also works on x86, and I assume it's intended to replace IonMonkey everywhere, not just on ARM chips.
I mean, if you just want to compile the code, sure.
Executing arbitrary machine code not generated by the rust compiler (i.e. by the JIT compiler you wrote in rust) is basically the definition of unsafe though...
One class of vulnerabilities in JS engines is use-after-move. A raw pointer is extracted, an allocating function is called (triggering a GC), then the raw pointer is used, pointing into nowhere. It's awkward to express in Rust that a function may modify state inaccessible from its parameters.
A second class of vulnerabilities is type-confusion. A value is resolved to (a pointer to) some concrete type, but some later code mutates the value. Now the concrete type is wrong. Again this possibility is awkward to express in Rust.
The problem is complicated by the NaN-boxing and JIT aspects of JS engines, which interfere with Rust's tree-ownership dreams.
People smarter and way better at Rust than myself are working on it; I'm excited by the prospect of novel solutions that can defeat entire classes of problems.
I'm excited to see a practical programming language that implements full dependent typing; languages like Idris are actually really good at dealing with precisely the kinds of situations you mention.
This feels like a hopeless problem; can any of Rust's powers be brought to bear here? Could Idris?
fn arrayLength(x: JSArray*) -> n: uint (requires nothing) (ensures length of x = n, changes nothing)
fn callToJson(x: JSValue*) -> JSValue* (requires nothing) (ensures nothing)
fn arrayAccess(x: JSArray*, m: uint) -> JSValue* (requires length of x > m) (changes nothing)
The stuff in parentheses after each function type are the preconditions and post-conditions respectively. So if you do something like:
let x = arrayLength(someArray)
for i in range(x) {
let element = arrayAccess(x-1)
}
let x = arrayLength(someArray)
for i in range(x) {
let element = arrayAccess(x-1)
let transformed = callToJson(element)
// ERROR: (requires length of x > m) not satisfied for all runs of loop body
}
Covering all the cases a JS engine would need without adding 10 million lines of proofs to the size of SpiderMonkey is still an open problem, but this general approach (known as Hoare Logic[1]) is very enticing, and the type systems that languages like Idris and F* have are definitely the closest to realizing it in more places. There are real software engineering efforts using descendants of Hoare logic like TLA+ (notably Amazon IIRC), but it's rare to see it even in huge projects like browsers.
It's also critical to note that the heap concept of F* is not a totally fixed part of the language; most of the specification of how heaps work are actually in the standard library. That level of flexibility is what I think makes these languages likely to become capable of tackling these problems: something like a JS engine or any optimizing compiler is exactly the kind of place where being able to come up with your own type-level verification model is worth the effort.
There will probably always be C++ code in Gecko, but I firmly believe that writing more components in Rust instead of C++ will (in general) improve security and developer productivity.
It still amazes me that we're actually shipping a browser with a CSS engine (and soon graphics engine!) written in Rust. Even more amazing is that these components are mostly shared with an entirely different browser engine.
This is not required of programmers in C, because the programmer could choose to delegate memory management to a memory management library, such as the Boehm-Demers-Weiser conservative garbage collector. [1]
My first experience with the boehm-gc was a long time ago, when I was using a very performance-intensive AI library. As an experiment, I modified it to use the boehm-gc and, surprisingly, it actually became faster.
I've since learned that such a speed improvement when manual memory management is replaced with the boehm-gc is not uncommon.
There are realtime GCs that can meet these hard requirements.
And even on the soft real time side, like rendering modern GUI, GC pauses causing frameskips (you have ~16ms to render each frame) makes your app look janky.
Even having to explicitly delegate memory management to a garbage collector is arguably manual memory management compared to other languages (It's a choice you have to make and adhere to, not a decision that's already been made for you).
Unlike manual memory collection which inevitably leads to memory leaks.
(And also, I'm not convinced that programming languages should be treated as having their own isolated developer communities, considering there is often a lot of overlap. Are we talking individual users? Companies? Language designers? Etc.)
C++11 introduced std::thread, with a couple of issues retified in later revisions, and apparently executors just failed C++20, delaying the introduction of a major part of async networking.
Language safety as well.
For me, in spite of the safety improvements in C++, I see the language being tailored for specific niches and no longer a full stack language, similar to how it is handled on modern desktop and mobile OSes.
And C will never catch up in security.
C and C++ are definitely being replaced by Rust now.