6 ms·

Yeah, it's called memset. Not sure if this bug is supposed to be subtle or something, but if you require the padding bytes to be consistent then you need to co

by shawxe 6y ago

Yeah, it's called memset. Not sure if this bug is supposed to be subtle or something, but if you require the padding bytes to be consistent then you need to consistently initialize your structs. Ignoring UB often leads to these sorts of bugs. 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.

saagarjha 6y ago
I don’t think memset is required to zero out padding bytes. The correct way to do this is to only access non-padding bytes.
- shawxe 6y ago
  sizeof(struct foo) is required to return the actual size, including padding, so struct foo foo_inst; memset(&foo_inst, 0, sizeof(foo_inst)); will certainly result in all padding bytes being set to zero.
  - saagarjha 6y ago
    sizeof will include padding, but there is no need for memset to actually perform a write that cannot be consistently observed.
    - deleted 6y ago
      [deleted]
    - icedchai 6y ago
      Are you saying memset does not have to write the entire struct? I understand it can be optimized out, but thought it if it was actually executed it had to set all of the specified bytes.
      - saagarjha 6y ago
        memset must write to the bytes that underly the members of the struct. What it does to padding bytes is not of consequence to you, as you cannot observe it as far as I understand. (That is, if you tried to read it out it would not necessarily be the value you had memset, or even be consistent across reads.)
        icedchai 6y ago
        memset definitely writes to padding bytes, as noted by several other folks here. you observe these padding bytes during serialization and deserialization (disk, network, memory mapped buffer, etc.) 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 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92486 for a recent example involving memset and memcpy.
        saagarjha 6y ago
        As mentioned in the bug report, the value of padding bytes is unspecified by the C standard. Actually, according to the linked Defect Report mentioned in the bug, there is a bit of discussion on whether the functions you mentioned should be entirely undefined to call or if some exceptions should be carved out. If the functions are legal to call, it is very likely that the results will be some arbitrary reification of the unspecified value.
- kazinator 6y ago
  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 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.
  - saagarjha 6y ago
    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 padding in C in a standards-compliant way to my knowledge, an optimizing compiler should be able to legally leave those bits alone.
    - gpderetta 6y ago
      Well, the contents of the padding bits is legally observable (with a memcpy for example) so the compiler can't assume they are unovservable.
      - saagarjha 6y ago
        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?
        6y ago
banachtarski 6y ago
Wrong answer. This is brittle and relies on the memory always being initialized correctly and will be prone to all sorts of issues in the wild. Better is just either templatize on the key type or store the size on the map.
- saagarjha 6y ago
  The answer is wrong more because it relies on padding bytes having consistent values than a lack of templating.
- shawxe 6y ago
  To be clear, there are obviously different/better ways to handle this in C++. We're talking about K&R C here.
  - banachtarski 6y ago
    Right I mentioned "store size of the key on the map" as the second option for K&R/Ansi C.
scatters 6y ago
memset, sure, then you copy the struct (return it or pass it by value) and the compiler won't bother copying the padding bytes. Or worse, an optimizing compiler will see that you're writing to padding bytes and helpfully no-op it.
- kazinator 6y ago
  A compiler that optimizes away memset is not one that could be used for targeting anything that sits on a network.
  - saagarjha 6y ago
    That immediately rules out GCC and Clang…
    - kazinator 6y ago
      I don't think so, unless we're mistaking memset for __builtin_memset.
      - scatters 6y ago
        GCC treats the two identically. See https://github.com/gcc-mirror/gcc/blob/229c0ef777161ec5adfb71ef1611af502541ccda/gcc/builtins.def#L93 https://github.com/gcc-mirror/gcc/blob/229c0ef777161ec5adfb7...
        kazinator 6y ago
        I see; because the sixth argument (BOTH_P) in that macro call is true.
- shawxe 6y ago
  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-generic.
kazinator 6y ago
One solution consists of using memset to initialize the structure to zero, and using memcpy to copy it instead of structure assignment. (Problem: pass-by-value in function calls won't use memcpy; abstractly, it uses member-for-member assignment which is not required to copy padding. A function that wants to calculate the correct has has to prepare a blank object with memset, then individually assign the fields into it from the incoming object.) 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.
- shawxe 6y ago
  > 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. 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.

by shawxe 6y ago

saagarjha 6y ago

I don’t think memset is required to zero out padding bytes. The correct way to do this is to only access non-padding bytes.

shawxe 6y ago
sizeof(struct foo) is required to return the actual size, including padding, so struct foo foo_inst; memset(&foo_inst, 0, sizeof(foo_inst)); will certainly result in all padding bytes being set to zero.
- saagarjha 6y ago
  sizeof will include padding, but there is no need for memset to actually perform a write that cannot be consistently observed.
  - deleted 6y ago
    [deleted]
  - icedchai 6y ago
    Are you saying memset does not have to write the entire struct? I understand it can be optimized out, but thought it if it was actually executed it had to set all of the specified bytes.
    - saagarjha 6y ago
      memset must write to the bytes that underly the members of the struct. What it does to padding bytes is not of consequence to you, as you cannot observe it as far as I understand. (That is, if you tried to read it out it would not necessarily be the value you had memset, or even be consistent across reads.)
      - icedchai 6y ago
        memset definitely writes to padding bytes, as noted by several other folks here. you observe these padding bytes during serialization and deserialization (disk, network, memory mapped buffer, etc.) 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 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=92486 for a recent example involving memset and memcpy.
        saagarjha 6y ago
        As mentioned in the bug report, the value of padding bytes is unspecified by the C standard. Actually, according to the linked Defect Report mentioned in the bug, there is a bit of discussion on whether the functions you mentioned should be entirely undefined to call or if some exceptions should be carved out. If the functions are legal to call, it is very likely that the results will be some arbitrary reification of the unspecified value.
kazinator 6y ago
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 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.
- saagarjha 6y ago
  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 padding in C in a standards-compliant way to my knowledge, an optimizing compiler should be able to legally leave those bits alone.
  - gpderetta 6y ago
    Well, the contents of the padding bits is legally observable (with a memcpy for example) so the compiler can't assume they are unovservable.
    - saagarjha 6y ago
      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?
      - 6y ago

banachtarski 6y ago

Wrong answer. This is brittle and relies on the memory always being initialized correctly and will be prone to all sorts of issues in the wild. Better is just either templatize on the key type or store the size on the map.

saagarjha 6y ago
The answer is wrong more because it relies on padding bytes having consistent values than a lack of templating.
shawxe 6y ago
To be clear, there are obviously different/better ways to handle this in C++. We're talking about K&R C here.
- banachtarski 6y ago
  Right I mentioned "store size of the key on the map" as the second option for K&R/Ansi C.

scatters 6y ago

memset, sure, then you copy the struct (return it or pass it by value) and the compiler won't bother copying the padding bytes. Or worse, an optimizing compiler will see that you're writing to padding bytes and helpfully no-op it.

kazinator 6y ago
A compiler that optimizes away memset is not one that could be used for targeting anything that sits on a network.
- saagarjha 6y ago
  That immediately rules out GCC and Clang…
  - kazinator 6y ago
    I don't think so, unless we're mistaking memset for __builtin_memset.
    - scatters 6y ago
      GCC treats the two identically. See https://github.com/gcc-mirror/gcc/blob/229c0ef777161ec5adfb71ef1611af502541ccda/gcc/builtins.def#L93 https://github.com/gcc-mirror/gcc/blob/229c0ef777161ec5adfb7...
      - kazinator 6y ago
        I see; because the sixth argument (BOTH_P) in that macro call is true.
shawxe 6y ago
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-generic.

kazinator 6y ago

One solution consists of using memset to initialize the structure to zero, and using memcpy to copy it instead of structure assignment. (Problem: pass-by-value in function calls won't use memcpy; abstractly, it uses member-for-member assignment which is not required to copy padding. A function that wants to calculate the correct has has to prepare a blank object with memset, then individually assign the fields into it from the incoming object.) 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.

shawxe 6y ago
> 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. 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.