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.