Missing origin in a vectorized loop

[ramosian-glider]

Originally reported on Google Code with ID 56

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#include <sanitizer/msan_interface.h>

static void variance(const unsigned char *src_ptr, int source_stride,
                     const unsigned char *ref_ptr, int recon_stride, int w,
                     int h, unsigned int *sse, int *sum) {
  int i, j;
  int diff;

  *sum = 0;
  *sse = 0;

  for (i = 0; i < h; i++) {
    for (j = 0; j < w; j++) {
      /* fprintf(stderr, "--\n"); */
      diff = src_ptr[j] - ref_ptr[j];
      *sum += diff;
      *sse += diff * diff;
    }

    src_ptr += source_stride;
    ref_ptr += recon_stride;
  }
}

__attribute__((noinline)) unsigned int vp8_variance16x16_c(
    const unsigned char *src_ptr, int source_stride,
    const unsigned char *ref_ptr, int recon_stride, unsigned int *sse) {
  unsigned int var;
  int avg;

  variance(src_ptr, source_stride, ref_ptr, recon_stride, 16, 16, &var, &avg);
  *sse = var;
  return (var - (((unsigned int)avg * avg) >> 8));
}

int main(void) {
  unsigned char *p;
  unsigned char *q;
  posix_memalign((void **)&p, 1024, 1024 * 1024);
  posix_memalign((void **)&q, 1024, 1024 * 1024);
  memset(q, 0, 1024 * 1024);
  unsigned int sse;
  unsigned int z = vp8_variance16x16_c(p, 1024, q, 1024, &sse);
  __msan_print_shadow(&z, sizeof(z));
  return 0;
}

Compile with -O2 -fsanitize=memory -fsanitize-memory-track-origins -xc.

Output:
Shadow map of [0x3fffa0da5f40, 0x3fffa0da5f44), 4 bytes:
0x3fffa0da5f40: ff000000 ........ ........ ........  |A . . .|

Origin A (origin_id 0):
  invalid origin id(0)


Uncommenting fprintf() call seems to break loop vectorization and "fixes" MSan.
MSan fails to propagate origin through the vectorized loop for some reason.

Reported by [email protected] on 2014-06-09 12:33:04

[ramosian-glider]

This comes from inexact instrumentation of shufflevector.
We pick origin that corresponds to the first not fully initialized operand, which is
a gross oversimplification.
It's very common for shufflevector to have partially uninitialized (often literally
undef) operands which do not make it the result. Even worse, they may affect shufflevector
result, but get dropped somewhere later.

It looks like we need to track vector origins per-element.

Reported by [email protected] on 2014-06-09 14:02:03

[ramosian-glider]

A workaround in r210472 should cover this case, but it is not a complete fix.

Reported by [email protected] on 2014-06-09 14:37:54

[ramosian-glider]

Adding Project:MemorySanitizer as part of GitHub migration.

Reported by [email protected] on 2015-07-30 09:22:26

• Labels added: ProjectMemorySanitizer

[eugenis]

A simplified test case for the vector origin issue:

#include <sanitizer/msan_interface.h>

typedef unsigned long V2x64 attribute((vector_size(16)));

int main() {
V2x64 a{0, 0};
__msan_allocated_memory(&a, 8);
__msan_allocated_memory(((char *)&a) + 8, 8);
__msan_print_shadow(&a, sizeof(a));
a <<= 1;
__msan_print_shadow(&a, sizeof(a));
}

Partial output:

Shadow map of [0x2ffd03e10240, 0x2ffd03e10250), 16 bytes:
0x2ffd03e10240: ffffffff ffffffff ffffffff ffffffff |A A B B|

Origin A (origin_id 2800001):
#1 0x48993f in main 1.cc:7:3

Origin B (origin_id 42000001):
#1 0x489958 in main 1.cc:8:3

Shadow map of [0x2ffd03e10240, 0x2ffd03e10250), 16 bytes:
0x2ffd03e10240: feffffff ffffffff feffffff ffffffff |A A A A|

Origin A (origin_id 92e00001):
#1 0x48993f in main 1.cc:7:3

Origin is propagated through <<= as a scalar i32 loaded at &a, so in the end both vector elements get the same origin.

If the first vector element is fully initialized, we may end up with garbage origin id.

[morehouse]

@eugenis: Any progress on this?

[eugenis]

No.