Malloc broke Serenity's JPGLoader, or: how to win the lottery (2021)

https://sin-ack.github.io/posts/jpg-loader-bork/

by fanf2 • 2 years ago

235 64 2 years ago

sin-ack.github.io

I got Deja Vu upon seeing "Alien Lenna" and sure enough... I've seen and commented on this before: https://news.ycombinator.com/item?id=27374942 (2021)

dale_glass• 2 years ago

This is one of the reasons why many hashtable implementations introduce a random component into the algorithm. The order of elements changes on every run, so if you accidentally rely on the order, it's going to go wrong sooner rather than later.

It also very nicely prevents security issues, since if the hashing algorithm is fixed, it can be exploited for denial of service by coming up with keys that all fall into the same bucket.

zarzavat2• 2 years ago

Many implementations these days also go the opposite way, guaranteeing that hash tables always iterate in insertion order.

I prefer this because it means I don’t have to decide whether I need an ordered map or an unordered map. Often if I think I need an unordered map it turns out to be wrong for some subtle reason.

mort964• 2 years ago

JavaScript is probably the most notable example of that. It used to not have a guaranteed iteration order, but browsers implemented it in such a way that the iteration order was the insertion order, and then that eventually got standardized because websites started depending on it.

For general purpose hash maps in standard libraries, I think you ought to either randomize the iteration order so that it's different every time, or guarantee an iteration order. Leaving it unspecified but predictable in practice is a recipe to fall victim to Hyrum's Law (https://www.hyrumslaw.com/).

thinkharderdev2• 2 years ago

Isn't that just a different data structure? How do you preserve insertion order in a hash map?

dkersten2• 2 years ago

Often if I think I need an unordered map it turns out to be wrong for some subtle reason.

Huh. This hasn’t been my experience. I very rarely need maps to be ordered. In recent years, the only case I can remember is when serializing to TOML and wanting the keys to be written in a specific order. There have been the occasional other case where insertion order is what I wanted, but I almost never need ordering in map keys.

I prefer this because it means I don’t have to decide whether I need an ordered map or an unordered map.

I’m the opposite, I prefer to be given a choice so I can make the tradeoffs when I want to or need to. If you don’t want to choose, you are free to always choose ordered map, but even if ordered map is the default, there should always be a choice to use unordered map. It’s been very rare that I started with the wrong one and had to change.

When I write python or JavaScript I typically don’t care and will just use whatever is the default, but when I write C++, I very much do care and the vast majority of cases use phmap’s flat_hash_map, which has superior space and speed over std::map and std::unordered_map. For ordered maps I use tsl::ordered_map but that still comes at a cost over flat_hash_map and its unordered variants.

anal_reactor3• 2 years ago

At my previous company my boss made me angry after I already handed in my two weeks notice so I stopped caring, and I wrote code that depended on the insertion order into a map. Of course I didn't document it. Have fun guys.

IshKebab• 2 years ago

I prefer this because it means I don’t have to decide whether I need an ordered map or an unordered map.

Well only if you happen to insert your elements in order. If you want a proper ordered map like `std::map` in C++ or `BTreeMap` in Rust then you are out of luck (at least in Python and Javascript).

kccqzy• 2 years ago

I don't understand this reasoning. If there is a subtle reason wouldn't you take the time to think through it carefully? Are you in such a rush that you don't have time to decide the required data structure (ordered vs unordered)? Or do you have insufficient control of downstream software that you fear for unknown bugs caused by this? And since insertion order is often related to some other ordering in the input, you are comfortable that downstream software completely rely on this ordering even when it's undocumented? Genuinely curious because this kind of reasoning is alien to me.

TacticalCoder• 2 years ago

This is one of the reasons why many hashtable implementations introduce a random component into the algorithm.

If the random component is a seed that can be forced/stored/logged/reproduced then it's okay. Otherwise it's actually an horrible idea because it complicates debugging other issues.

Randomness is the enemy, not the friend.

It also very nicely prevents security issues, since if the hashing algorithm is fixed, it can be exploited for denial of service by coming up with keys that all fall into the same bucket.

Yeah, 20 years ago this was a thing to attack Java webservers: crafting URL with parameters so that they'd all end up in the same bucket. Big denial-of-service one. IIRC PHP webservers suffered from the exact same security issue.

It was fixed by implementing a hash table with a seed and that seed was, of course, under the control of the dev because...

Randomness is the enemy, not the friend.

jcelerier2• 2 years ago

I had to build SerenityOS from scratch about 4-5 times on a 2011 laptop with Sandy Bridge Mobile.

I mean, this is like trying to do Windows Vista development with a computer released in the timeframe between Windows 3.1 and Windows 95

elteto2• 2 years ago

Maybe in terms of time, but not in terms of actual performance. CPUs haven’t changed that much since 2011 (relatively speaking), but between Windows 3.1 and Vista we got x64 and multicore CPUs everywhere became the norm.

nicoburns• 2 years ago

CPUs haven’t changed that much since 2011 (relatively speaking)

Perhaps not relatively speaking, but my 2021 CPU is 10x faster than my 2015 CPU on workload which parallelise (which compiling generally does).

accrual• 2 years ago

Nice comparison. Indeed, the developer's CPU is about 13 years old. Vista was released internationally in early 2007, so a 13 year old CPU at release would've been released in 1994, about a year after the original Pentium was released. But many were still using their trusty 486 DX2-66 CPUs.

Quite impressive that a CPU from 13 years ago can still work on modern projects today when the same wasn't quite as true back then. And a CPU released today will (hopefully) be able to work satisfactorily beyond 2037. 8)

qingcharles• 2 years ago

My main desktop for the last year has been a 2011 Lenovo i5 running Windows 11 on dual monitors. Visual Studio runs great on it. Photoshop (the on-system AI tools can be a tiny bit sluggish). I probably have 200 tabs open in Chrome. Slack, WhatsApp. Three different browsers for testing. CapCut could be a little quicker when editing 4K, but it gets by just fine with complex 2K projects. The only thing I've hit the buffers with a little is complicated After Effects projects. It no likey those.

I do need to upgrade, but damn, for a system I basically saved from a Dumpster, it is decent.

jcelerier2• 2 years ago

Visual Studio runs great on it.

I'd really like to see a video of VS running great on such a machine. My experience with it is that it doesn't run great at all on a top-of-the-line 2022 laptop with laggy interactions left and right. For the kind of software VS is, literally any UI lag is completely unacceptable.

Ygg2• 2 years ago

Needs [2021] in title

elteto2• 2 years ago

Kudos on the debugging but also on that commit message. It managed to condense the cause and the fix into a couple of paragraphs.

russfink• 2 years ago

This isn’t Gunnar’s fault. The problem was whomever stored ordered data in a hash file.

I have been in this business for decades and I have run into the situation where changing the shape of memory uncovers bugs. Every time it causes many hours and days of debugging.

If programming weren’t hard, they wouldn’t need us to do it. (I’m not sure how much longer that phrase will hold up under large language models.)

chrisjj• 2 years ago

Indeed. And contrary to the title, the fault isn't malloc()'s either.

caboteria• 2 years ago

As long as LLMs are trained on code that has bugs, they'll suggest code that has bugs.

powercf• 2 years ago

This isn’t Gunnar’s fault. The problem was whomever stored ordered data in a hash file.

Yes. Even if it were, I don't think it needs to be mentioned in the commit message. Gunnar improved something, which triggered problems with old broken code. For his efforts he gets:

Gunnar, I like you, but please don't make me go through this again. :^)

shiomiru• 2 years ago

If the smiley face and the commit message's tone didn't make it clear that it's a joke, TFA explicitly ends with this:

Gunnar in particular was the one who uncovered this bug, and despite my satirical jab in the commit message helped uncover this very interesting bug, so he’s the one who made this post possible.

Gunnar is also credited right in the same commit message for help:

Credits to Andrew Kaster, bgianf, CxByte and Gunnar for the debugging help.

And judging from how the author of the actually broken code in question is (reasonably) not investigated or publicized, it seems quite obvious to me that the article's author is not trying to play the blame game.

tedunangst• 2 years ago

This seems like a case where a little more debugging would have saved time over brute force bisection. The logging to print component orders had to be done eventually anyway.

ddtaylor• 2 years ago

As a result, during the 1000 commits I ended up bisecting for, I had to build SerenityOS from scratch about 4-5 times on a 2011 laptop with Sandy Bridge Mobile. While this isn’t the fault of the project, I’m still mad.

I think SerenityOS has some folks that help each other out with resources and PCs for testing purposes.

jeffbee• 2 years ago

For whatever its worth, if we wait long enough C++ will include the equivalent of `malloc_good_size`. https://github.com/cplusplus/papers/issues/18

amelius• 2 years ago

TL;DR:

Someone used a HashTable to store objects that should be ordered, then iterated over it using the basic HashTable iterator

Malloc broke Serenity's JPGLoader, or: how to win the lottery (2021)

Related Stories