Malloc broke Serenity's JPGLoader, or: how to win the lottery
sin-ack.github.io
sin-ack.github.io
Why this code was written this way instead of just checking against the ID by linearly iterating over the Components, I have no idea.
There's another comment here that shows their JPEG decoder only supports 1 or 3 components. Using a hash table for at most 3 entries is astronomical overkill! The field for the number of components in a JPEG file is only a byte - so even if you were to support more than 3 components, it would be 255 at most, and sane JPEG files are unlikely to have more than 4 in practice. So fixed-size arrays are the perfect solution. I have a very good idea why it was written like that, however: the mere availability and ease of use of abstract data structures naturally leads to their overuse by what seems to be an overwhelming majority of developers, and the eagerness to "futureproof" and add unnecessary complexity is also very common.
Overcomplexity creates bugs, and (leaky) abstractions hide them. Even if the complexity (and bug) isn't visible in your code, it's still there. If the initial code had been reviewed by me, it most certainly would not pass.
I am saying this as someone who has actually written a JPEG decoder --- it is not as difficult as it may sound, and I highly recommend giving it a try --- and also witnessed (and fixed) the messes that people get in with overcomplicating things. Perhaps that slight "architecture astronaut" mentality comes from starting with a higher-level language; I started with Asm and my preferred language is usually C, and I haven't seen the tendency to overcomplicate much in others who did the same.
The reason the Components were in a hash table was that they would then be checked against the component ordering in a “Start of Scan” section to make sure all the components in the SOS section are in the expected order.
For comparison, this is the corresponding code in my JPEG decoder. I didn't even bother using a loop:
if(read_byte()!= cids[0])
data_error("SOS scan first component must match");
hts[0] = read_byte(); /* high nybble: DC table index; low nybble: AC table index */
if(read_byte() != cids[1])
data_error("SOS scan second component must match");
hts[1] = read_byte();
if(read_byte() != cids[2])
data_error("SOS scan third component must match");
hts[2] = read_byte();To give some context, iterating over an array of three small items takes worst case roughly 100ns(cache miss), best case 1ns(l1 cache hit). Most common hashmap implementations (like std::unordered_map) dynamically allocate items so they're stored randomly in memory, giving roughly 300ns worst case(3 cache misses), 3ns best case(3 l1 cache hits) for iterating over them. So using a hash map is going to be 3x slower without even accounting for the time spent hashing, and 3x more likely to hit the worse case due to requiring three cachelines still in the l1 cache for best performance as opposed to just one. If regularly adding/deleting items, using a std::unordered_map would literally be orders of magnitude slower due to using malloc/free for each item added/removed.
This all comes from the specification requiring even load factors arbitrarily close to 1 and to still have amortized constant time insertion, lookup and deletion.
If all your objects are doomed to die where there were born, you better put them in the right place. (So an array is good for C-like languages.)
Though it's less important on languages with compacting garbage collectors, because there allocation can be just a pointer bump, which is pretty similar to what you do for stack allocation.
See also this Scheme implementation which allocates everything on the C stack:
> Previous Schemes for implementing full tail-recursion when compiling into C have required some form of "trampoline" to pop the stack. We propose solving the tail-recursion problem in the same manner as Standard ML of New Jersey, by allocating all frames in the (garbage-collected) heap. The Scheme program is translated into continuation-passing style, so the target C functions never return. The C stack pointer then becomes the allocation pointer for a Cheney-style copying garbage collection scheme. Our Scheme can use C function calls, C arguments, C variable-arity functions, and separate compilation without requiring complex block-compilation of entire programs. Introduction IEEE Scheme [IEEE90] requires that all functions be properly tail-recursive, in order that tail-recursive programs not require an unbounded amount of stack space. Several Scheme compilers have targeted the C language [Bartlett89], because C is an efficient systems programming language which is available on nearly ev...
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.7...
Do keep in mind that some languages like Scheme (because of call/cc) and Haskell (because of laziness) in general don't have a single stack. See eg https://en.wikipedia.org/wiki/Parent_pointer_tree for what Scheme needs to do.
Of course, allocation of variables with hierarchically nested lifetimes (ie stack allocation) is still an important and common special case that your compiler/interpreter should probably recognize and handle well.
Escape analysis is a well studied field after all. https://en.wikipedia.org/wiki/Escape_analysis
Here is the given reason for using a HashMap: https://github.com/SerenityOS/serenity/commit/f107c7065230c6...
The code switches out a static array of size 3 for a hash table, in order to handle that incoming IDs (used as indexes in the array, then keys in the hash) can go up to 255 instead of just 2.
I would think that upping the array to size 256 would still be cheaper (or at least not a lot more expensive) in terms of memory used than adding a full hash table, but I have not inspected Serenity's hash implementation to validate that claim. It would almost certainly be cheaper in terms of performance, especially from less memory allocations.
Always start with an array if the problem allows for it, even if you need to reallocate sometimes, or have to scan linearly. Measure performance before using a map or linked list.
That said, linearly scanning is not much different from a hash map with linear probing that has no empty slots left, so it's not necessarily obvious that the hash map actually takes that much more space.
I'd still just use a plain array, but my point was that hash maps aren't necessarily big and unwieldy.
Even if not optimal, it definitely looks less unreasonable as a choice now that the original motivation found.
And if it had been “fixed” in the simple way without finding the original motivation, it very well may have introduced a different edge-case bug.
So one important lesson here, is always try to do some “due dilligence” to track down why code was written how it was before changing it, even if (or especially if) you assume it was just shoddy coding. (What’s the metaphor/aphorism used about this? I remember there is one, but can't recall/find it now).
(And also reminds us of the importance of good granular commits with good commit messages, to leave that history! Much easier to find original motivation than in a pre-version-controlled world).
> Overcomplexity creates bugs, and (leaky) abstractions hide them. Even if the complexity (and bug) isn't visible in your code, it's still there. If the initial code had been reviewed by me, it most certainly would not pass.
I suspect in this case the problem is trying to use this style of coding in a language like C++.
If you implement this in eg Python, using the hash table would have been perfectly natural and the simplest way to do it. (And a modern enough Python would guarantee your ordering.)
In Java, Haskell or Rust etc something else might have been simplest.
Or perhaps the code is shared with some other project which does require the added complexity.
I disagree. Simplicity of the code is most vital to avoid bugs, and if a hash table is what the language typically uses to represent key value mappings, that is what should be used, for 3 or 3 million items.
Keep the code idiomatic, and only optimize where necessary.
A good implementation of a hash table has a special fast path for tiny runtime sizes.
A good compiler could bound the size of the hash table, and switch out the implementation if its size can be bounded at compile time.
Sure, in this case, it didn't work so well. But the principle of idiomatic code still stands.
If you're using a language where all you have are hash tables (PHP comes to mind), then there's no way around it; but it's insanity to overlook simplicity.
https://abseil.io/docs/cpp/guides/container#iteration-order-...
Even when told that the Lua manual clearly states the undefined order since 20 years, they do not cease to complain. They do not realize this change helped them to discover a serious bug in their code (the order could differ even before that change). Sigh.
You can now have a guess, what one of the lesser enlightened forks of LuaJIT did ...
And to be fair it’s a pain in the ass to debug and find out why something happens to implicitly depend on iteration order (float stability is common but not alone). And their code did work beforehand, for most values of work.
The biggest pain in the ass is that — at least in python - while you can set the hash seed explicitely if you don’t the langage doesn’t tell you. This makes reproducing the issue very annoying when only some seeds trigger it.
> the order could differ even before that change
While the order could differ I assume it was deterministic and nothing influencing those bits had changed in a while.
And now, as predicted by core developer Raymond Hettinger in his Modern Dictionaries talk, Python's dicts are now guaranteed to be ordered by default (as of 3.7).
Clearly this is a landmine that many people step on. Why not remove it?
Look at Python, Ruby, PHP - they have defined iteration order to be insertion order. Javascript also have predictable order though the order is a bit more complex. Go is the outlier in that it defines it as guaranteed to be random. But both choices are just fine.
That is a bit too strong am assertion: you can decorrelate the two when you build the collection, but the naive set up is very much that hash randomisation will randomise iteration order.
With a sufficient number of users of an API, it does not matter what you promise in the contract: all observable behaviors of your system will be depended on by somebody.
If you need defined ordering in your type, use it. Otherwise, don't specify it.
What happened here is a perfect example of what an optimiser might come up with and resulting systems will be so brittle and delicate that a whole new form of cargo cult might develop around them :D
Doesn’t matter which one as long as it’s not solely developmental.
It would not quite be instant though, the body would first have to run out of the existing supply then break down as operations stop. If you pick the right protein (e.g. something affecting the muscles or brain) I’d think the timescale would be minutes if not seconds.
If you can only edit one cell or a small number if them then probably not, you can definitely cause long-term issues (e.g. cancers) but I would not think instant death an option.
I think the GP was talking more about existing genetic defects leading to sudden issues down the line though.
https://www.youtube.com/watch?v=JZE3_0qvrMg
The talk was presumably better live because Hyrum doesn't have a microphone, so his interjections are hard to follow, but it's a good way to illustrate.
Some of the examples are much like this story, you design this sophisticated, heavily optimised unordered container for millions of items, and then your users put three items into it, and they depend on the order of those items and you "broke" their code by not having this behaviour you never promised and it made no sense to depend on.
And the defence mentioned in this thread (randomise things which aren't guaranteed to have stability) is introduced because these are Google employees, they know about Hyrum, it just isn't enough. Sure the code failed when I tried to store 40 items due to your randomisation, but I found it worked OK with ten items as then the randomisation was defeated, so now I store ten items, and then your latest change broke that...
The pathological use of data structure is why stuff like making the constructor for empty strings very cheap has a big effect on some codebases. Rust const-ified String::new() because an empty string doesn't need any heap store. So this means code which loops over a large array setting all the members to the empty string is only about as expensive as looping over an integer array setting all the integers to zero, it doesn't incur a heap allocation, or a function call. Of course modifying these strings now takes on the expense of allocating, but guess how often people who do stuff like this never actually touch the string...
reminds me of a time my extension started glitching because localStorage stopped returning results in same order they were put in :o) Now that I think about it it happened somewhere around 2017-2018, did google drop it into Chrome at this point?
"Shift left" just means that you shift the feedback to the developer farther left in the build process, closer (in time and space) to when the mistake was made.
This was previously a special object (collections.OrderedDict) but is now the default behavior of every dict:
https://docs.python.org/3/library/collections.html#ordereddi...
Infuriatingly, this behavior is _not_ preserved for the set type.
if anything, it should be an another type, but this would also be against the go philosophy.
...which is completely fine. it isn't very difficult to work around and keeps the language simple, even if i'd prefer to have the option built-in.
This kind of behaviour should be visible on the application design and not depend on implementation details.
Not really since it’s Go (“lol no generics”): there’s no easy way to swap the builtin hashmap for an other associative array with deterministic behaviour and you will lose something (definitely performances, likely either convenience or type-safety, possibly both).
Yes it sucks not having generics, why should the built-in contribute to bad practices of relying into interaction behaviors, thus cripling any performance improvements to the data structure?
If you need ordered iteration to stay deterministic, extract the keys, sort them, then iterate over the (now-sorted) slice of keys?
If the order matters, you should defensively make SURE you are iterating in that order. If the order doesn't matter, the fact that each iteration over the map is different helps you not fall into a "I know this" trap.
Which turns out to be pretty inconvenient in Go. So more likely you’d do something like copy the keys to a slice, sort the slice, then iterate that to get the map values.
Incidentally, that’s exactly what the json package does when encoding a map.
For evidence, see:
https://github.com/golang/go/issues/6719
if (context.component_count != 1 && context.component_count != 3) {
dbgln_if(JPG_DEBUG, "{}: Unsupported number of components in SOF: {}!", stream.offset(), context.component_count);
return false;
}From the user perspective, a change to malloc really did break JPGLoader. That it broke this by revealing a pre-existing fault in the code is interesting to note. Especially for the developers. But it does not change the user experience.
It's a beautiful portrait, and a standard in image compression comparison. Deal with it.
I strongly dislike that prudish and puritan zealots now exploit the ideals of feminism and social justice to push forward the idea that we should be afraid of sex and our bodies. They're not "doing it for the women in tech", but because of their own issues with sexuality.
http://www.cs.umd.edu/users/oleary/faculty/node8.html
Alternatives:
J. Gutbezahl, How Negative Expectancies and Attitudes Undermine Females' Math Confidence and Performance: A Review of the Literature. https://eric.ed.gov/?id=ED380279
E. Spertus, Why are There so Few Female Computer Scientists? https://hdl.handle.net/1721.1/7040
The 30 (!) year old Spertus paper even states that most of the data collected was anecdotal.
If you mean "correct" as in "true", it's an opinion. I don't know what I could post that would sway you on a matter of opinion.
Sorry I'll reword. The question asked was "How is Lenna's picture disturbing or suggestive?"
So don't focus on the word "correct" as much as the "explain why". They asked "how" and they did not get an answer.
You linked to a page that doesn't help answer that question, because it only has the same quote.
Lots of things are opinions. But you can justify an opinion, explain an opinion.
If I was going to argue against using Lena, I'd say things about the context of the image and why that's a problem. Any problems with the 512x512 image itself are much less obvious, and I think it's fair to want a more detailed argument on that front.
That's pretty straightforward, from the link I posted, and not the same quote or person.
They didn't ask why not to use Lena, they were asking about that specific quote.
There is a big difference between "the association with playboy is disturbing" and "the picture is disturbing".
The O'Leary quote seems to be talking entirely about the picture, the 512x512 one.
You've given a lot of resources for the former, but they were asking about the latter.
And while "suggestive" is pretty subjective, "woman with bare shoulder" is not self-evidently suggestive.
For example, you said "If I was going to argue against using Lena, I'd say things about the context of the image"
Then summarily dismissed a quote about the context of the image. It's funny.
The context is relevant to that, as you said yourself.
The wikipedia link gives some of that context. I provided one example. Cropping out the nudity doesn't change the context.
Right. Which is a subset of the possible reasons to not use it. Everything about playboy is outside that subset, and does not answer the question, despite being a reason not to use it.
Much like "It's a violation of copyright" would also be a reason not to use the image that doesn't answer the question.
http://www.lenna.org/full/len_full.html
While the test image itself doesn't show much, the fact that it originated from Playboy magazine is widely known – and presumably has contributed to the image's popularity. It's a sort of in-joke: you can't understand it just by seeing it, you need the context. But it's an in-joke that recalls sexist tropes.
Sex-related sure, but why do you think that's sexist? Because playboy discriminated against male models?
Seriously, I doubt you can find any picture at all, where no person find reasons to be offended.
And I bet most people did not know, that the picture in question is from Playboy, I did not. But still, so what?
It shows a attractive women in a slightly seductive pose. Is that really sexist? Why?
It's a shame that a ~naked body is "disturbing" for US-Females.
BTW: Why so many human killing machines as alternatives? I feel offended now.
I think this account by Maddie Zug [0] summaries most peoples objections to the image. Women just want to participate in tech, but the male dominated field already makes it hard enough, especially when images with a very sexual origin (again, it isn't the pretty woman, but the origin of the pretty woman) are used. It is that difficult to use another picture from the above database?
"I retired from modeling a long time ago. It’s time I retired from tech, too.” - Lena Söderberg
[0]: https://www.washingtonpost.com/opinions/a-playboy-centerfold...
[1]: https://www.sfgate.com/news/article/How-a-Nude-Playboy-Photo...
These kinds of errors are extremely common in much more mature libraries, including OpenCV, as well as HLSL or GLSL. No disrespect, but it sounds like you've never really touched graphics programming before. Color spaces are literally just a bag of numbers.
A good analogy is coordinate systems. There's no type difference between an x-coordinate or a y-coordinate; they're just numbers and are defined by their ordinal position in an (x, y) tuple.
https://entropymine.wordpress.com/2018/10/22/how-is-a-jpeg-i...
foo(5, 42, 99) is just a bad interface. foo(red(5), green(42), blue(99)) gives the compiler enough to whine about.
no human unit difference does not imply no type difference. Types are tools to write correct programs, we should use them at the maximum !
D3DFMT_A8R8G8B8 (Direct3D 9) is equivalent to DXGI_FORMAT_B8G8R8A8_UNORM (DXGI / Direct3D 10+). Note that one enumeration lists the components in reverse order of the other, and that this is correct! https://docs.microsoft.com/en-us/windows/win32/direct3d10/d3... .
Documentation often completely omits information endian or encoding - and when it doesn't, it's often hidden away where you'll never find it, and usually assumes x86/x64/little-endian processors. The behavior on big-endian machines is best found out through testing - even if the documentation is clear, the documentation stands a good chances of lying, and CI probably doesn't test on big-endian meaning bugs have likely arisen, and there's a good chance your copy of the library is old and doesn't contain any bugfixes.
In light of all of the above, RGB vs BGR confusion is one of the most natural points of confusion to run across when dealing with image formats. "Just use the type system!" ignores where these bugs crop up - (de)serialization, converting streams of bytes to types or vicea versa. Someone must write the code, declaration, whatever - and the type system has no means of ensuring that correctly matches whatever not-computer-readable spec that the (de)serialization is supposed to match - and so it will, frequently, be understandably incorrect.
You're mistaken.
The author originally suspected - or hypothesized - that was possibly the bug, but the actual cause detailed in the post ended up being different (nondeterministic hashmap iteration over components) and the final patch does not include the initially proposed "fix" of swapping the red and blue components as was shown towards the very top of the article. The original order was correct. Swapping red/blue would've just been canceling out one bug by adding another.
https://github.com/SerenityOS/serenity/commit/a10ad24c760bfe...
> The type system can prevent this flaw.
The type system can add some roadbumps to encourage centralizing the conversion of "untyped" disk bytes to typed r/g/b components or a typed color component, but that conversion must still occur somewhere, and it can be written backwards at that somewhere, and one of those somewheres will be inside JPGLoader.cpp. That's the fundamental job of a JPEG loader - conversion of an untyped byte stream into useful types for the rest of the program to use. Additional use of the type system might limit where within JPGLoader.cpp such a component swapping flaw might be likely, but it's never going to prevent it for all of JPGLoader.cpp.
The existence of the Color type already makes such a flaw fairly unlikely outside of JPGLoader.cpp and similar conversion points. That's sufficient use of the type system. More within JPGLoader.cpp, while possible, would be overkill based on my own experience with color conversion and swapped component bugs. Hell, to play devil's adovcate, further use of the type system could cause such flaws! The extra code is likely to cause additional reviewer fatigue in code reviews. Reviewer fatigue causes inattention. Inattention causes the reviewer to miss swapped or nondeterministics components. Perhaps such inattention caused this bug!
I would be in favor of replacing:
const Color color { (u8)block.y[pixel_index], (u8)block.cb[pixel_index], (u8)block.cr[pixel_index] };
const auto color = Color::from_rgb((u8)block.r[pixel_index], (u8)block.g[pixel_index], (u8)block.b[pixel_index]);
It's still possible to have a copy+paste bug with my replacement by using r/g/g as input instead of r/g/b or similar, but I've seen such bugs even with per-component types - just need the first copy to be mistaken and copy+pasted all over.
Color color;
for (size_t c=0; c<3; ++c) color[c] = (u8)block[c][pixel_index];
and one which probably is succinct as well ?
https://doc.rust-lang.org/rust-by-example/generics/new_types...
So this would look something like:
// single field tuple structs
struct R(u8);
struct G(u8);
struct B(u8);
// using a tuple struct
struct Color(R, G, B);
// or using a struct with named fields
struct Color {
r: R,
g: G,
b: B,
}
u8[] a
...
Color( a[0], a[1], a[2])
Color( a[2], a[1], a[0])
Also, you’ll need types for every single color space. Do you mean sRGB (https://en.wikipedia.org/wiki/SRGB), Adobe RGB (https://en.wikipedia.org/wiki/Adobe_RGB_color_space), scRGB (https://en.wikipedia.org/wiki/ScRGB), etc. Since that set isn’t fixed (every device potentially had its own RGB gamut) you’ll need a programming language that can create types at run time if you want to write a program that dynamically handles all kinds of devices.
struct R(u8);
struct G(u8);
struct B(u8);
struct Color(R, G, B);
u8[] a;
...
Color( a[0], a[1], a[2])
let r: R = R(a[2]);
let g: G = G(a[1]);
let b: B = B(a[0]);
Color(b, g, r);
Types in Rust don't exist at runtime, they're a compile-time concept, so creating types at runtime doesn't make sense. This sort of thing is generally approached by having the compiler monomorphize generics in places where various representations overlap, and otherwise just having a separate set of types for each non-compatible representation. The correct library would then be picked dynamically from the set of available options compiled into the binary.
For external functions, it's not an optimization but an ABI requirement (for at least some ABIs) and even for TU-internal functions compilers tend to stick closely to the ABI.
https://docs.microsoft.com/en-us/windows/win32/api/wingdi/nf...
(If you still manage to get the ordering wrong even when you're forced to write the name of this macro... then programming is probably not for you.)
Edit: I just noticed the return type is "void". This error is entirely due to the destruction of MSDN; my copy of WIN32.HLP has the correct definition.
Humility is key to prevent disasters, and ordering will be gotten wrong as long as there is no type checking and we are relying on people to double check the ordering. A mistake can happen because of a temporary lack of attention, tiredness, confusion, distraction, interruption… I hope any experienced programmer is aware of this, or maybe they should avoid programming?
Ideally, 1 and 2 are of different types (which may not always be practical).
It could make it easier to spot an error if 1 and 2 are in fact variables that have a name (RGB(R(green), G(red), B(blue))) screems HEY SOMEHTING IS WRONG THERE).
https://pdimov.github.io/blog/2020/09/07/named-parameters-in...
it would be quite cool if c++ did have c99's equivalent of designated initializers, and without the restrictions of
1. following decl-order while doing the initializations and
2. omitting unwanted or unneeded parameter values
Can't remember the details.
It’s not for side-projects though? And it seems like a good idea to avoid reallocations if you can still grow in-place.