The Lost Art of Structure Packing (2018)
catb.org
catb.org
I was recently doing that in the context of improving a language’s library support for something that had to go through the OS SDK. I don’t miss the days when that stuff was the norm.
struct Obj
{
int foo;
bool bar;
}
The bug was found when someone did something like:
void DoSomething(Obj obj)
{
if(!map.has(obj))
map.add(obj, new Whatever());
map[obj].blah(); //CRASH null pointer exception
}
Well, it can be because even though the struct looks like it takes 5 bytes, in reality it's 8 bytes because it's getting padded. So a naive hashing method that just looks at bits is hashing your 5 bytes of actual data + 3 bytes of garbage, which means that two "identical" objects are very unlikely to actually produce the same hash.
C++20 now has a "hashable" concept to help with this, but it still requires the programmer to be aware of structure packing.
E.g. if you initialize a C struct or C++ object the "usual way":
Obj obj = { };
There will most definitely be junk in the padding bytes.
Because not every structure was packed, depending on your include order, some structures would be packed differently in different compilation units.
Except, for the only structures this happened for, the packed packing was coincidentally the same as the default packing ... when the program was compiled 32-bits. Attempting to switch from a 32-bit executable to a 64-bit executable resulted in mysterious segfaults as different compilation units disagreed on where different fields were.
Fun times!
<shivers violently>
I'm sorry, you can easily solve this problem in K&R C from 1979.
EDIT: Based on some of the comments I'm getting here, it seems like some of you have never implemented a hashmap/generic interface in vanilla C and it shows. If you want a hashmap that is generic and you don't want to write/specify a hashing function for keys on map initialization, then what you're likely to end up doing is ensuring that keys are initialized consistently, providing key size on map initialization, and simply performing a hash on the key as though it were a buffer of bytes.
Suggesting that this is somehow any more fragile than anything else in C or that templates should be used instead, which is an absurd comment since templates do not exist in C, is ridiculous. This comment is replying to a comment about how solutions to this problem have existed since K&R C--and they have. You don't need templates to not ignore UB, although if you are using C++ you can certainly use templates (and also take advantage of the stronger type system) to work around issues like this.
The point is that avoiding undefined behavior in C/C++ hashmap implementations is not something that has only recently become possible. C solutions may be more fragile, but that doesn't stop them from being "correct" in that will yield correct behavior unless an error is made elsewhere. Code that makes assumptions about the values of padding without explicitly setting those values is NOT correct and for anyone who works in a language like C/C++ regularly, that should be obvious.
struct foo foo_inst; memset(&foo_inst, 0, sizeof(foo_inst));
will certainly result in all padding bytes being set to zero.
Note this is important enough that compiler folks consider it a bug if it doesn't work correctly. see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92486 for a recent example involving memset and memcpy.
memseting a structure to zero is commonly done in programs that send structure outside of the process (like passing it to communication or storage-related system calls) because the padding can leak sensitive information. That better work!
If the size of a structure didn't include the padding, then pointer arithmetic on structures wouldn't work correctly, and arrays of them would be broken/impossible. Arrays are the reason for the padding; given a struct foo * p, we need p + 1 to be properly aligned (for the sake of accessing all the members of * (p + 1). So struct foo cannot have a size like 5, if it contains a member of type int or anything else with alignment requirements.
edit: interestingly, Biriba is yet another game in the canasta family, my theory is that different groups were originally playing these differents variants, but when they gained knowledge of the more popular variant (burraco), they started playing it but kept calling it with the original name. I guess that up until the internet era, these games were mostly passed via oral knowledge in casual groups.
edit2: macchiavelli [1] is another very fun game of the same family, but a lot more puzzle solving oriented.
[1] https://en.wikipedia.org/wiki/Machiavelli_(Italian_card_game...
I appreciate your edits, by the way ;)
And it seem that I should double check which comment I'm editing before submitting :)
Which is to say that memset_s should just be called memset; there is no need for memset to be doing stupid things so that people must use memset_s.
I have no plans to use memset_s (ever), or to upstream any fix that involves using it unless the author provides a repro test case, and a proof that the problem can't be fixed with compiler options that make the problem go away with memset.
In the worst imaginable scenario, I will #define memset memset_s everywhere (after the inclusion of <string.h> of course, not before, and an #undef memset).
(The #undef memset may be enough, in fact, if the only problem is that memset is #define'd to some compiler built-in that doesn't properly implement classic C90 memset in all cases.)
There is no need for a broken memset that fails to set some of the bytes, so that a fixed one under a different name has to be used in its place.
If you're using memset such that it's okay for memset not to set some of the bytes, and you'd like them not to be set if that makes things faster, then you shouldn't be using memset. You're using a hammer to drive a screw: wrong tool.
C has perfectly good initialization and assignment for structures.
End of story; I'm going to walk away pretend I never read this subthread, re-joining the hordes of C programmers using memset in the normal way, adding to the countless lines of code that do it that way and are never going to be changed.
This bullshit will be backpedaled out of the standard eventually, you just wait.
Probably means the extra-secure variant, more secure than the regular non-optimized-away memset that really clears the memory, but without the flush.
{
struct foo x;
// sensitive calculation with x
memset(&x, 0, sizeof x);
}
I've been discussing only this case:
{
struct foo x;
memset(&x, 0, sizeof x);
// init x
syscall(&x, sizeof x);
}
That's a stupid and dangerous optimization that threatens a whole lot of code in the wild.
A good defense against this sort of time-wasting nonsense is "I'm not fixing anything without a repro test case; have a nice day".
Second of all, in a generic C interface keys are likely to be treated as void pointer and almost certainly are going to be moved around with memcpy etc. rather than returned/passed by value since doing so would make the interface non-generic.
E.g. "... being interpreted as a void * type."
Yes, it's true that generic C code will type-erase the key type. However it just takes a little refactoring in specific code to move the struct initialization across a call boundary from where it is passed to the generic code.
I'm skeptical about compilers optimizing memset not to cover padding between structure members.
Firstly, that would introduce security holes into a heck of a lot more existing code compared to code that uses a dead-store memset to wipe sensitive crypto.
Secondly, it wouldn't run any faster. Gaps in a structure and at the end exist in order to eliminate misalignment. Before most padding, there is a member that ends on a misaligned address. It's slower to update just that member, and leave the padding alone, than to clobber the padding.
For instance if we have a { char a; int b; char c; } structure, we gain nothing by zeroing just one byte of a, b and c.
In some compiler for an 8 bit system, this reasoning is likely false; I will worry about it when porting to that. Very little existing code will fit; you're coding from scratch for such things.
that is really dangerous to assume. memset is a compiler built-in in every relevant C++ compiler and the compiler definitely knows the type of the object that is behind your void* and knows if you're being nasty.
e.g. look at this code : https://gcc.godbolt.org/z/xh9BXs
it's UB, and the compiler knows it and inserts an "invalid opcode" instruction even if you try to hide a memset behind a void*-taking function
Another solution, more along the lines of what I was thinking, is simply to associate the hash table with a hashing function which processes the type as a structure, hashing the members individually rather than as a pad of memory.
C++ templates refine this by adding the ability to deduce the hashing function statically, and possibly inline it, which we could do with some preprocessing in C, along the lines of how those TAILQ macros from BSD work for linked lists.
This solution is probably what I would go for in most cases as well. The most compelling reasons I can think of for going the other way would be if there were a desire to use a specific hashing function/algorithm on all keys regardless of type or if there were a desire to have keys of different types in the same map.
The point is that C++20 adds a way to catch yourself before you make the exact type of mistake the grandparent comment talks about.
There is no way in C++ to get at the padding bytes unless you're using undefined behaviour. How does the hash function work? Pointer aliasing using reinterpret_cast? Pointer aliasing using C-style casts? Typing punning through the old union switcheroo?
int hash=0;
for(int i=0;i<sizeof(obj);i++)
hash += hashing_method(reintepret_cast<char*>(&obj)+i);
return hash;
We can argue whether that's a smart thing to do or not, but I wasn't in charge of implementing it - it's a relic from a codebase that's more than a decade old at this point. It's a simple hashing method that works with most types, but obviously dies horrendously in a case like this.
Just pack the struct and be done with it.
Generally you have several possibilities for how to escape this problem, but the simplest is to just add the padding and a static assert that the sizeof the struct is what you expect.
No, their contents has an unspecified value.
1. Arranging fields to pack things that are shorter than 4 bytes along 4 byte boundaries.
2. Manually arranging data buffers in very specific layouts (this is less about the original post, more about a different interpretation of "packing").
Aside from what I mentioned above, more commonly you will run into this in interop scenarios, such as calling C/C++ API's from C#. Thankfully those scenarios are few and far between.
https://www.nongnu.org/txr/txr-manpage.html#N-027D075C
This is the result of empirical investigation.
The description also covers allocation of non-bitfields (paragraph 3) and the padding of the structure (paragraph 9) which require few words.
I felt that the bitfield handling is so obscure that it had to be documented in detail. If someone is to know exactly what the layout will be, the documentation can't just be "oh, it will behave like a GCC struct". Well, what will that do? That is not adequately documented anywhere.
If I have to work with bitfields in just C, I can use that as a reference to understand what the compiler will do (at least if it's anything compatible with GCC).
The details are not obvious; like the fact that a zero width bitfield like "int : 0" that appears etween two members that are not bitfields actually does something. E.g. this has size 5:
struct {
char c1;
int : 0; // zero-width bit-field must be unnamed
char c2;
};
ISO C says (or did say in 1999) only this: "A bit-field declaration with no declarator, but only a colon and a width, indicates an unnamed bit-field.105) As a special case, a bit-field structure member with a width of 0 indicates that no further bit-field is to be packed into the unit in which the previous bit-field, if any, was placed."
No "further bit-field" is to be packed, but in this example there is neither a previous nor next bit field. So you might expect that there is no effect. In the GCC model of "all allocated so far are just bits", it has an effect.
Footnote 105 says just that "An unnamed bit-field structure member is useful for padding to conform to externally imposed layouts" which is more or less self-evident.
Oh wow; I just realized that the empty bit-field has an effect if it is the last member also:
struct { // now size 8!
char c1;
int : 0;
char c2;
int : 0;
};
It's a useful feature of GCC bit-fields because you can conform to certain external layouts without having to use bit-fields at all, other than the zero-width ones.
People like you who are willing and able to do this are pillars for the whole of our field. You're a hero. :)
https://itanium-cxx-abi.github.io/cxx-abi/abi.html
This was originally developed as a joint effort to make compilers ABI-compatible on Itanium, but it's also used (by GCC, clang, Intel's proprietary compiler and others) on x86-64.
An old Hacker News comment said that it's from Intel; it's not, it was a joint effort with lots of work from CodeSourcery and Red Hat folks.
"The size and alignment of a type which is a POD for the purpose of layout is as specified by the base (C) ABI"
The links in 1.5 Base Documents are old and broken.
Example:
Word : constant := 4; -- storage element is byte, 4 bytes per word
type State is (A,M,W,P); type Mode is (Fix, Dec, Exp, Signif);
type Byte_Mask is array (0..7) of Boolean; type State_Mask is array (State) of Boolean; type Mode_Mask is array (Mode) of Boolean;
type Program_Status_Word is record System_Mask : Byte_Mask;
Protection_Key : Integer range 0 .. 3;
Machine_State : State_Mask;
Interrupt_Cause : Interruption_Code;
Ilc : Integer range 0 .. 3;
Cc : Integer range 0 .. 3;
Program_Mask : Mode_Mask;
Inst_Address : Address;
end record;
for Program_Status_Word use
record
System_Mask at 0*Word range 0 .. 7;
Protection_Key at 0*Word range 10 .. 11; -- bits 8,9 unused
Machine_State at 0*Word range 12 .. 15;
Interrupt_Cause at 0*Word range 16 .. 31;
Ilc at 1*Word range 0 .. 1; -- second word
Cc at 1*Word range 2 .. 3;
Program_Mask at 1*Word range 4 .. 7;
Inst_Address at 1*Word range 8 .. 31;
end record;
for Program_Status_Word'Size use 8*System.Storage_Unit;
for Program_Status_Word'Alignment use 8;
I’m not sure why “use a different language” is such a common reply to any language specific discussion.
I keep hoping the Zig developer will do a deep dive on Ada and bring over more of this kind of precise control. A language where I have this kind of control over layout, but can still spell `end record;` as `}`, is ideal for some projects I have in mind.
AFAIK there are PoC 3rd party implementations for such tuples.
IMHO there are just as many arguments for automatic reordering as there are against it (e.g. creating structs that are layed over memory mapped IO registers, or just optimizing a struct for certain cache-efficient access patterns). In my opinion it's sufficient to know about the existance of alignment-padding, and how to work around it if needed (for instance reordering the struct members manually, or using #pragma pack)
People do quite often rely on the first struct element being at the start of the struct. Memcpy:ing directly between structs and network/disk is also common, but naughty. Both struct padding and endianness already break that.
Typically if I define a 8bit as the first element, I need to be certain those 8bits are first even if that wastes three more bytes to align on the next variable.
People will also do silly things like casting between types in ways that rely on similarly written structures having similar memory layouts. So C is probably a bad language to turn this on by default in
It seems like something like that could be useful rather than making programmers try to order their structs by hand.
There is almost never a difference to the user what order things are structured. Although to be fair this does get tricky with unions of structure over structure.
I always assumed that in C++, the memory layout could change a lot between compilers (the location of the pointer to the vtable for example). Do you know if it's true, and if the layout do change, could you give an example?
Usually, but not always. In most cases there is one efficient way to pack the structure and still maintain member alignment, but there's not requirement that the amount of padding looks like this.
> I always assumed that in C++, the memory layout could change a lot between compilers (the location of the pointer to the vtable for example). Do you know if it's true, and if the layout do change, could you give an example?
Yes, once you have a non-POD type the memory layout can be fairly arbitrary as you cannot really inspect it and compilers are free to lay it out as they wish.
However this isn't universally true. Some platforms might not have a well defined C ABI.
If you need to squeeze out all padding, use compiler directives like '#pragma pack', but be aware of the performance implications.