Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Lost Art of Structure Packing (2018)

catb.org

Post reply on HN
Print view View original

71–80 of 120 posts

Re: The Lost Art of Structure Packing (2018)

#71

Post by saagarjha »

jcelerier wrote: post #57
shawxe wrote: post #42

Earlier quoted context omitted.

First of all, there is no way the compiler is going to optimize a call to memset(&foo, 0, sizeof(foo)) when &foo is being interpreted as a void pointer. That doesn't even make sense. 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-gen…

> First of all, there is no way the compiler is going to optimize a call to memset(&foo, 0, sizeof(foo)) when &foo is being interpreted as a void pointer. That doesn't even make sense. 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…

-Ofast makes non-compliant programs anyways, so it's not the best example.

Re: The Lost Art of Structure Packing (2018)

#72

Post by kazinator »

carapace wrote: post #70
kazinator wrote: post #22

I've documented how GCC does bitfield packing in the TXR reference manual. Or rather, the abstract algorithm used in the FFI to replicate it. 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…

That's awesome! It's the kind of detail that, when you need it you really need it, but it's often so hard to find, or locked in some proprietary deal. I can barely imagine the amount of work it must have taken to nail all that down. Congratulations, and thank you!

I tried numerous cases, and looked at the memory, and also read and wrote the structures with FFI to make sure they match what the C compiler is putting out, and fixed bugs along the way. For big endian investiations, I borrowed the big endian PPC machine courtesy of the GCC Compile Farm project.

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;
   };
This is basically because c1 is de-facto considered to be 8 allocated bits out of an int-wide cell, leaving 24 bits in that cell. The int : 0 sees that a field has been partially filled and so increments to the next int-wide field (according to my documented hypothesis).

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;
   };
This is predicted by my documentation, but it should be spelled out in an explicit remark.

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.

Re: The Lost Art of Structure Packing (2018)

#73

Post by karlding »

saalweachter wrote: post #14
gambiting wrote: post #10

Earlier quoted context omitted.

I work in video games, and very recently we had a sneaky bug in one of our AAA titles(that was already out!), where(in huge simplification) we had a struct that looked like: struct Obj { int foo; bool bar; } then we were storing those in a custom hashmap using these as keys, where the hashing function was basically hashing bits of each stored object, without any awareness of what's in the object. The bug was found wh…

In my first job, there was an interesting bug introduced by an un-terminated pragma-pack in a header file. 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.…

This is why I always use static_assert [0] to assert on the struct size in projects using C11+, or use a macro to create my own (using the negative array size trick) to cause a compile error if I can't use C11 as a sanity check for these cases. This saves a lot of potential headaches.

[0] https://en.cppreference.com/w/c/language/_Static_assert

Re: The Lost Art of Structure Packing (2018)

#74

Post by jcelerier »

saagarjha wrote: post #71
jcelerier wrote: post #57

Earlier quoted context omitted.

> First of all, there is no way the compiler is going to optimize a call to memset(&foo, 0, sizeof(foo)) when &foo is being interpreted as a void pointer. That doesn't even make sense. 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…

-Ofast makes non-compliant programs anyways, so it's not the best example.

I had -Ofast in there but you can check that it's the same with -O2

Re: The Lost Art of Structure Packing (2018)

#75

Post by SlowRobotAhead »

0xDEEPFAC wrote: post #68

Looks like what he really wants is to use Ada which has had much better support for low-level programming than C. 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 S…

I use C for embedded. I do the “lost art” of structure packing all the time. I don’t want ada.

I’m not sure why “use a different language” is such a common reply to any language specific discussion.

Re: The Lost Art of Structure Packing (2018)

#76

Post by SlowRobotAhead »

Natsu wrote: post #46

I'm sort of surprised there are no tools for this. I understand why having the compiler reorder things could be bad, though it seems like there should be room to tell the compiler it's okay to repack it for minimum space, but I don't even see any mention of a source-level tool that would just sort the items in a struct for you. It seems like something like that could be useful rather than making programmers try to or…

If you just order top down in structures from pointers, 32s, 16s, arrays, 8s, it’s almost entirely done without thinking.

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.

Re: The Lost Art of Structure Packing (2018)

#77

Post by carapace »

kazinator wrote: post #72
carapace wrote: post #70

Earlier quoted context omitted.

That's awesome! It's the kind of detail that, when you need it you really need it, but it's often so hard to find, or locked in some proprietary deal. I can barely imagine the amount of work it must have taken to nail all that down. Congratulations, and thank you!

I tried numerous cases, and looked at the memory, and also read and wrote the structures with FFI to make sure they match what the C compiler is putting out, and fixed bugs along the way. For big endian investiations, I borrowed the big endian PPC machine courtesy of the GCC Compile Farm project. The details are not obvious; like the fact that a zero width bitfield like "int : 0" that appears etween two members that…

Holy wow.

People like you who are willing and able to do this are pillars for the whole of our field. You're a hero. :)

Re: The Lost Art of Structure Packing (2018)

#78

Post by smcameron »

Natsu wrote: post #46

I'm sort of surprised there are no tools for this. I understand why having the compiler reorder things could be bad, though it seems like there should be room to tell the compiler it's okay to repack it for minimum space, but I don't even see any mention of a source-level tool that would just sort the items in a struct for you. It seems like something like that could be useful rather than making programmers try to or…

There's pahole https://lwn.net/Articles/335942/

Re: The Lost Art of Structure Packing (2018)

#79

Post by gpderetta »

saagarjha wrote: post #56
kazinator wrote: post #38

Earlier quoted context omitted.

memset is absolutely required to zero out padding bytes. Padding is part of the structure size, and memset hast to zero out exactly as many bytes as it is told. 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 str…

memset is not required to do anything if the side effects are not observable; this is the entire reason why memset_s needed to be added (and also why __attribute__((packed)) is recommended for anything that is being sent directly over the wire, if this kind of construction cannot be avoided). Compilers often inline and unroll small, constant-size memsets anyways, and since it is not possible to observe a consistent p…

Well, the contents of the padding bits is legally observable (with a memcpy for example) so the compiler can't assume they are unovservable.

Re: The Lost Art of Structure Packing (2018)

#80

Post by saagarjha »

gpderetta wrote: post #79
saagarjha wrote: post #56

Earlier quoted context omitted.

memset is not required to do anything if the side effects are not observable; this is the entire reason why memset_s needed to be added (and also why __attribute__((packed)) is recommended for anything that is being sent directly over the wire, if this kind of construction cannot be avoided). Compilers often inline and unroll small, constant-size memsets anyways, and since it is not possible to observe a consistent p…

Well, the contents of the padding bits is legally observable (with a memcpy for example) so the compiler can't assume they are unovservable.

As far as I understand, padding bits are indeterminate until you observe them via a memcpy into a buffer, at which point they will collapse (only in the buffer) to some arbitrary but now-constant value. Is this correct?
Post reply on HN