Valgrind warnings

[alberts]

Hello

I have a loop that inserts 4 byte values into a HLL. It hits a Valgrind warning

With these parameters:

Log2m = 11;
Regwidth = 5;
Expthresh = -1;
Sparseon = 1;

it happens after inserting 160 elements.

It seems as if multiset_packed_size computes a too-small size for the packed buffer that has to be used.

Valgrind warnings look as follows. Line numbers are off because I've been playing with this part of the code outside Postgres.

==29406== Invalid read of size 8
==29406== at 0x40B2D2: bitstream_pack (byteswap.h:111)
==29406== by 0x40BBD8: multiset_pack (hll.c:245)
==29406== Address 0x548e387 is 311 bytes inside a block of size 317 alloc'd

==29406== Invalid write of size 8
==29406== at 0x40B2E4: bitstream_pack (hll.c:155)
==29406== by 0x40BBD8: multiset_pack (hll.c:245)
==29406== Address 0x548e387 is 311 bytes inside a block of size 317 alloc'd

which is this line: * (uint64_t *) bwcp->bwc_curp = qw;

Hopefully this is enough info to find the bug, otherwise I can dig more. I'm reasonably sure you can reproduce this with HLL running inside Postgres, but it's harder to Valgrind there.

I can also build a test against the original HLL source if that will help you.

Cheers

Albert

[alberts]

Hello

I've managed to reproduce this while running in Postgres. You don't see it when Valgrinding the code as-is, because I think the memory regions backing the pointers returned by palloc are quite big, which prevents Valgrind from detecting the overruns in the reads/writes. They did some Valgrind integration for Postgres 9.4, so maybe it will show up there.

Anyway, add these lines to hll_add:

void* buf = malloc(csz);
multiset_pack(&msa, (uint8_t *)buf, csz);
free(buf);

This makes it also pack into a buffer where Valgrind can track the accesses.

Run Postgres like this:

sudo -u postgres valgrind --trace-children=yes --leak-check=no --gen-suppressions=all --suppressions=valgrind.supp -v postgres -D /var/lib/pgsql/data -p 5432

valgrind.supp is in src/tools in Postgres git.

Then something like:

psql -f valgrind.sql hll_regress

valgrind.sql is here: https://gist.github.com/alberts/7950110

==23799== Invalid read of size 8
==23799==    at 0x1446E1C2: bitstream_pack (byteswap.h:111)
==23799==    by 0x1446F92C: multiset_pack (hll.c:483)
==23799==    by 0x1447078B: hll_add (hll.c:2050)
==23799==    by 0x57EC31: ExecMakeFunctionResult (execQual.c:1938)
==23799==    by 0x57E034: ExecEvalFuncArgs (execQual.c:1478)
==23799==    by 0x57EAE5: ExecMakeFunctionResult (execQual.c:1709)
==23799==    by 0x580F7C: ExecProject (execQual.c:5240)
==23799==    by 0x581309: ExecScan (execScan.c:207)
==23799==    by 0x57A937: ExecProcNode (execProcnode.c:400)
==23799==    by 0x58F6F4: ExecModifyTable (nodeModifyTable.c:918)
==23799==    by 0x57A977: ExecProcNode (execProcnode.c:377)
==23799==    by 0x5780BF: standard_ExecutorRun (execMain.c:1470)
==23799==  Address 0x151ae817 is 311 bytes inside a block of size 317 alloc'd
==23799==    at 0x4A06409: malloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==23799==    by 0x1447077A: hll_add (hll.c:2049)
==23799==    by 0x57EC31: ExecMakeFunctionResult (execQual.c:1938)
==23799==    by 0x57E034: ExecEvalFuncArgs (execQual.c:1478)
==23799==    by 0x57EAE5: ExecMakeFunctionResult (execQual.c:1709)
==23799==    by 0x580F7C: ExecProject (execQual.c:5240)
==23799==    by 0x581309: ExecScan (execScan.c:207)
==23799==    by 0x57A937: ExecProcNode (execProcnode.c:400)
==23799==    by 0x58F6F4: ExecModifyTable (nodeModifyTable.c:918)
==23799==    by 0x57A977: ExecProcNode (execProcnode.c:377)
==23799==    by 0x5780BF: standard_ExecutorRun (execMain.c:1470)
==23799==    by 0x64CB6D: ProcessQuery (pquery.c:185)

==23799== Invalid write of size 8
==23799==    at 0x1446E1D4: bitstream_pack (hll.c:385)
==23799==    by 0x1446F92C: multiset_pack (hll.c:483)
==23799==    by 0x1447078B: hll_add (hll.c:2050)
==23799==    by 0x57EC31: ExecMakeFunctionResult (execQual.c:1938)
==23799==    by 0x57E034: ExecEvalFuncArgs (execQual.c:1478)
==23799==    by 0x57EAE5: ExecMakeFunctionResult (execQual.c:1709)
==23799==    by 0x580F7C: ExecProject (execQual.c:5240)
==23799==    by 0x581309: ExecScan (execScan.c:207)
==23799==    by 0x57A937: ExecProcNode (execProcnode.c:400)
==23799==    by 0x58F6F4: ExecModifyTable (nodeModifyTable.c:918)
==23799==    by 0x57A977: ExecProcNode (execProcnode.c:377)
==23799==    by 0x5780BF: standard_ExecutorRun (execMain.c:1470)
==23799==  Address 0x151ae817 is 311 bytes inside a block of size 317 alloc'd
==23799==    at 0x4A06409: malloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==23799==    by 0x1447077A: hll_add (hll.c:2049)
==23799==    by 0x57EC31: ExecMakeFunctionResult (execQual.c:1938)
==23799==    by 0x57E034: ExecEvalFuncArgs (execQual.c:1478)
==23799==    by 0x57EAE5: ExecMakeFunctionResult (execQual.c:1709)
==23799==    by 0x580F7C: ExecProject (execQual.c:5240)
==23799==    by 0x581309: ExecScan (execScan.c:207)
==23799==    by 0x57A937: ExecProcNode (execProcnode.c:400)
==23799==    by 0x58F6F4: ExecModifyTable (nodeModifyTable.c:918)
==23799==    by 0x57A977: ExecProcNode (execProcnode.c:377)
==23799==    by 0x5780BF: standard_ExecutorRun (execMain.c:1470)
==23799==    by 0x64CB6D: ProcessQuery (pquery.c:185)

[alberts]

This issue also happens when packing to the calculated size after adding a first and a second 4-byte element to an hll_empty4(11, 5, 0, 0).

[alberts]

Basically, I think the problem is that the bitstream_pack function ends up touching memory it shouldn't because it works with 64-bit values and enough padding isn't always allocated.

@alberts literally just came to that conclusion myself.

I believe that least invasive fix here is to always round up to a multiple of 8 when in the MST_COMPRESSED section of multiset_packed_size.

[alberts]

Makes sense.

@alberts I'm getting Valgrind and PG set up on a non-Darwin machine, so I should be able to get working on this in just a bit.

Bad news: simply allocating enough bytes to round up to a multiple of 8 would force me to sacrifice the rigorous input/output byte-size checking that's currently in place. I don't feel like that's the right tradeoff.

I'm going to take a shot at reworking bitstream_pack and bitstream_unpack so that they never touch memory outside of the palloc'd buffer.