C HOW can this out-of-range access inside struct go wrong?-CodePudding

#include <iostream>
#include <random>
using namespace std;

struct TradeMsg {
  int64_t timestamp; // 0->7
  char exchange; // 8
  char symbol[17]; // 9->25
  char sale_condition[4]; // 26 -> 29
  char source_of_trade; // 30
  uint8_t trade_correction;  // 31
  int64_t trade_volume; // 32->39
  int64_t trade_price; // 40->47
};
static_assert(sizeof(TradeMsg) == 48);

char buffer[1000000];

template<class T, size_t N=1>
int someFunc(char* buffer, T* output, int& cursor) {
    // read   process data from buffer. Return data in output. Set cursor to the last byte read   1.
    return cursor   (rand() % 20)   1; // dummy code
}

void parseData(TradeMsg* msg) {
    int cursor = 0;
    cursor = someFunc<int64_t>(buffer, &msg->timestamp, cursor);
    cursor = someFunc<char>(buffer, &msg->exchange, cursor);
    
    cursor  ;
    int i = 0;
    // i is GUARANTEED to be <= 17 after this loop,
    // edit: the input data in buffer[] guarantee that fact.
    while (buffer[cursor   i] != ',') {
        msg->symbol[i] = buffer[cursor   i];
        i  ;
    }
    msg->symbol[i] = '\n'; // might access symbol[17].
    cursor = cursor   i   1;
            
    for (i=0; i<4; i  ) msg->sale_condition[i] = buffer[cursor   i];
    cursor  = 5;
    
    //cursor = someFunc...
}

int main()
{
    TradeMsg a;
    a.symbol[17] = '\0';

    return 0;
}

I have this struct that is guaranteed to have predictable size. In the code, there is a case where the program tries to assign value to an array element past its size msg->symbol[17] = ... .

However, in that case, the assignment does not cause any harm as long as:

It is done before the next struct members (sale_condition) are assigned (no unexpected code reordering).
It does not modifies any previous members (timestamp, exchange).
It does not access any memory outside the struct.

I read that this is undefined behavior. But what kind of compiler optimization/code generation can make this go wrong? symbol[17] is pretty deep inside the middle of the struct, so I don't see how can the compiler generates an access outside it. Assume that platform is x86-64 only

CodePudding user response：

Various folks have pointed out debug-mode checks that will fire on access outside the bounds of an array member of a struct, with options like gcc -fsanitize=undefined. Separate from that, it's also legal for a compiler to use the assumption of non-overlap between member accesses to reorder two assignments which actually do alias:

@Peter in comments points out that the compiler is allowed to assume that accesses to msg->symbol[i] don't affect other struct members, and potentially delay msg->symbol[i] = '\n'; until after the loop that writes msg->sale_condition[i]. (i.e. sink that store to the bottom of the function).

There isn't a good reason you'd expect a compiler to want to do that in this function alone, but perhaps after inlining into some caller that also stored something there, it could be relevant. Or just because it's a DeathStation 9000 that exists in this thought experiment to break your code.

You could write this safely, although GCC compiles that worse

Since char* is allowed to alias any other object, you could offset a char* relative to the start of the whole struct, rather than to the start of the member array. Use offsetof to find the right start point like this:

#include <cstddef>

    ...
    ((char*)msg   offsetof(TradeMsg, symbol))[i] = '\n'; // might access symbol[17].

That's exactly equivalent to *((char*)msg offsetof(...) i) = '\n'; by definition of C 's [] operator, even though it lets you use [i] to index relative to the same position.

However, that does compile to less efficient asm with GCC11.2 -O2. (Godbolt), mostly because int i, cursor are narrower than pointer-width. The "safe" version that redoes indexing from the start of the struct does more indexing work in asm, not using the msg offsetof(symbol) pointer that it was already using as the base register in the loop.

# original version, with UB if `i` goes past the buffer.
# gcc11.2 -O2 -march=haswell.  -O3 fully unrolls into a chain of copy/branch

      ... partially peeled first iteration
.L3:                                      # do{
        mov     BYTE PTR [rbx 8 rax], dl   # store into msg->symbol[i]
        movsx   rdi, eax                   # not read inside the loop
        lea     ecx, [r8 rax]
        inc     rax
        movzx   edx, BYTE PTR buffer[rsi 1 rax]  # load from buffer
        cmp     dl, 44
        jne     .L3                       # }while(buffer[cursor i] != ',')
## End of copy-and-search loop.  
# Loops are identical up to this point except for MOVSX here vs. MOV in the no-UB version.
        movsx   rcx, ecx       # just redo sign extension of this calculation that was done repeatedly inside the loop just for this, apparently.
.L2:
        mov     BYTE PTR [rbx 9 rdi], 10   # store a newline
        mov     eax, 1                     # set up for next loop

# offsetof version, without UB

  # same loop, but with RDI and RSI usage switched.
  # And with    mov  esi, eax  zero extension instead of  movsx rdi, eax  sign extension
        cmp     dl, 44
        jne     .L3                       # }while(buffer[cursor i] != ',')

        add     esi, 9              # offsetof(TradeMsg, symbol)
        movsx   rcx, ecx            # more stuff getting sign extended.
        movsx   rsi, esi            # including something used in the newline store
.L2:
        mov     BYTE PTR [rbx rsi], 10
        mov     eax, 1                  # set up for next loop

The RCX calculation seems to just be for use by the next loop, setting sale_conditions.

BTW, the copy-and-search loop is like strcpy but with a ',' terminator. Unfortunately gcc/clang don't know how to optimize that; they compile to a slow byte-at-a-time loop, not e.g. an AVX512BW masked store using mask-1 from a vec == set1_epi8(',') compare, to get a mask selecting the bytes-before-',' instead of the comma element. (Probably needs a bithack to isolate that lowest-set-bit as the only set bit, though, unless it's safe to always copy 16 or 17 bytes separate from finding the ',' position, which could be done efficiently without masked stores or branching.)

Another option might be a union between a char[21] and struct{ char sym[17], sale[4];}, if you use a C implementation that allows C99-style union type-punning. (It's a GNU extension, and also supported by MSVC, but not necessarily literally every x86 compiler.)

Also, style-wise, shadowing int i = 0; with for( int i=0 ; i<4 ; i ) is poor style. Pick a different var name for that loop, like j. (Or if there is anything meaningful, a better name for i which has to survive across multiple loops.)

CodePudding user response：

In a few cases:

When variable guard is set up: https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html
In a C interpreter (yes they exist): https://root.cern/cling/

CodePudding user response：

Your symbol has a size of 17 Yet, you are trying to assign a value to the 18th index a.symbol[17] = '\0';

Remember your index value starts off at 0 not 1.

So you have two places that can go wrong. i can equal 17 which will cause an error and that last line I showed above will cause an error.