Live data from Hacker News

Lossless compression with Brotli

blogs.dropbox.com

11–20 of 66 posts

Re: Lossless compression with Brotli

#11
post #3

Awesome to see the contributed back their custom allocator that lets you allocate from a fixed block: https://github.com/dropbox/rust-alloc-no-stdlib Solid stuff from the looks of it.

Now I have a huge hankering to whip up a frame-based allocator, as used to be popular in game and graphics programming. For those unfamiliar, the idea is that you segregate allocation of memory objects of different sizes into their own fixed blocks. This provides a means to control memory fragmentation, and avoids hitting the typically slow system allocator with a lot of small allocations/deallocations.

Fancy frame allocators would actually use a fairly standard malloc-style interface, but transparently place allocations of different sizes in their own regions. The allocator would internally use the slow system malloc to create and expand the fixed blocks it uses for its own allocations. During development, the frame allocator would be used to profile and optimize the actual object allocation sizes being made. E.g. sometimes it might make sense to pad some objects to consolidate the number of allocation-size regions. As the project progresses, the initial block allocations for each allocation size would be adjusted so that the system malloc was called very infrequently, usually only at application startup.

Re: Lossless compression with Brotli

#12
post #3

Awesome to see the contributed back their custom allocator that lets you allocate from a fixed block: https://github.com/dropbox/rust-alloc-no-stdlib Solid stuff from the looks of it.

Now I have a huge hankering to whip up a frame-based allocator, as used to be popular in game and graphics programming. For those unfamiliar, the idea is that you segregate allocation of memory objects of different sizes into their own fixed blocks. This provides a means to control memory fragmentation, and avoids hitting the typically slow system allocator with a lot of small allocations/deallocations. Fancy frame a…

It might be possible that jemalloc already does this? Rust uses it by default, and while I don't recall the specifics jemalloc does a bunch of things in userspace wrapped around malloc that make it better than malloc.

Rust makes it easy to swap out the allocator too, so I'd love to see an allocator lib specifically focused on size management :)

Re: Lossless compression with Brotli

#13
post #4
post #2

Somewhat interesting for those who missed it - another rust/brotli project was a target for afl-rust. IIRC it didn't find any memory safety issues, but it definitely exposed a few panic crashes: https://github.com/frewsxcv/afl.rs (discussion https://news.ycombinator.com/item?id=11936983 ) I don't think they mentioned fuzzing their Brotli decompressor in this article, but I hope they try afl-rust.

Apparently this( https://github.com/dropbox/rust-brotli ) is much faster than the one( https://github.com/ende76/brotli-rs ) fuzzed by afl.rs. Like 10x faster. See https://github.com/ende76/brotli-rs/issues/24 .

Relevant comment from ende76 on why brotli-rs is relatively slow and what the goals of the project are/were:

"Yes, performance has not been a focus point at all so far. I've started this project as a a way to get familiar with Rust, and also with the Brotli spec. For the implementation, I have made it a point to work only from the spec, while avoiding looking at the reference implementation, because another goal was helping to improve the Brotli spec itself. I do believe that there are a number of places where copies could be avoided, and other places where I used clone() simply because at the time I was unable otherwise to appease the borrow checker.

For a performance-oriented implementation, I would probably take the test cases and experiences so far, and start over with a new implementation."

Re: Lossless compression with Brotli

#14

I'm having a hard time understanding the motivations for porting to rust... If they were going to run the whole thing in a SECCOMP container anyway, there is little damage a compromised C library could do. If reasoning about uninitialized memory would take a review of the entire brotli code base, didn't the rust port require that anyway? (speaking as someone who has done a couple of cross-language rewrites)

> If they were going to run the whole thing in a SECCOMP container anyway, there is little damage a compromised C library could do.

They can't block everything with SECCOMP, the code still has to be useful. It also must still do it's job correctly, which it won't if it's compromised.

> If reasoning about uninitialized memory would take a review of the entire brotli code base, didn't the rust port require that anyway? (speaking as someone who has done a couple of cross-language rewrites)

But even if you go through the whole original codebase (which I assume was in C or C++), and kept it in that same memory unsafe language, you don't have any guarantees that you caught even a subset of possible classes of memory safety bugs.

Re: Lossless compression with Brotli

#15

Earlier quoted context omitted.

Now I have a huge hankering to whip up a frame-based allocator, as used to be popular in game and graphics programming. For those unfamiliar, the idea is that you segregate allocation of memory objects of different sizes into their own fixed blocks. This provides a means to control memory fragmentation, and avoids hitting the typically slow system allocator with a lot of small allocations/deallocations. Fancy frame a…

It might be possible that jemalloc already does this? Rust uses it by default, and while I don't recall the specifics jemalloc does a bunch of things in userspace wrapped around malloc that make it better than malloc. Rust makes it easy to swap out the allocator too, so I'd love to see an allocator lib specifically focused on size management :)

Yes, this is precisely how jemalloc works.

Re: Lossless compression with Brotli

#16

I'm having a hard time understanding the motivations for porting to rust... If they were going to run the whole thing in a SECCOMP container anyway, there is little damage a compromised C library could do. If reasoning about uninitialized memory would take a review of the entire brotli code base, didn't the rust port require that anyway? (speaking as someone who has done a couple of cross-language rewrites)

> If they were going to run the whole thing in a SECCOMP container anyway, there is little damage a compromised C library could do.

Not really. For instance, a compromised library can still rewrite the file you're storing in DropBox to contain different contents, which could ultimately result in remote code execution when you redownloaded it. Seccomp only makes sure the decompression server is safe from a rogue process.

Re: Lossless compression with Brotli

#19

I'm having a hard time understanding the motivations for porting to rust... If they were going to run the whole thing in a SECCOMP container anyway, there is little damage a compromised C library could do. If reasoning about uninitialized memory would take a review of the entire brotli code base, didn't the rust port require that anyway? (speaking as someone who has done a couple of cross-language rewrites)

> If they were going to run the whole thing in a SECCOMP container anyway, there is little damage a compromised C library could do. Not really. For instance, a compromised library can still rewrite the file you're storing in DropBox to contain different contents, which could ultimately result in remote code execution when you redownloaded it. Seccomp only makes sure the decompression server is safe from a rogue proce…

The file's sha256sum can be verified before the file is sent to any users, so there's no chance of RCE there, even with a hypothetical C brotli-- but a reproducible decompression is key.

Additionally, if you want to do the decompression on client-side, facilities like SECCOMP simply may not be available on that platform. And in that case, having a language like Rust to guard against RCE is an excellent idea. Also it is easiest to maintain the same code running on all platforms rather than C code where SECCOMP is available and Rust code where it is not.

Re: Lossless compression with Brotli

#20

I'm having a hard time understanding the motivations for porting to rust... If they were going to run the whole thing in a SECCOMP container anyway, there is little damage a compromised C library could do. If reasoning about uninitialized memory would take a review of the entire brotli code base, didn't the rust port require that anyway? (speaking as someone who has done a couple of cross-language rewrites)

> If they were going to run the whole thing in a SECCOMP container anyway, there is little damage a compromised C library could do. Not really. For instance, a compromised library can still rewrite the file you're storing in DropBox to contain different contents, which could ultimately result in remote code execution when you redownloaded it. Seccomp only makes sure the decompression server is safe from a rogue proce…

[deleted]
Post reply on HN