pack bitmap woes on Windows

pack bitmap woes on Windows

[Johannes Sixt]

Running test suite of 'next' on Windows fails in t5310-pack-bitmaps with
the following symptoms. I haven't followed the topic. Have there been
patches floating that addressed the problem in one way or another?

(gdb) run
Starting program: D:\Src\mingw-git\t\trash directory.t5310-pack-bitmaps/..\..\git.exe rev-list --test-bitmap HEAD
[New thread 3528.0x8d4]
Bitmap v1 test (20 entries loaded)
Found bitmap for 537ea4d3eb79c95f602873b1167c480006d2ac2d. 64 bits / 15873b36 checksum

Breakpoint 1, die (err=0x5939e9 "Out of memory, realloc failed") at usage.c:97
97              if (die_is_recursing()) {
(gdb) bt
#0  die (err=0x5939e9 "Out of memory, realloc failed") at usage.c:97
#1  0x00487c4c in xrealloc (ptr=0x12b10008, size=837107040) at wrapper.c:109
#2  0x0055572b in ewah_to_bitmap (ewah=0xe58c18) at ewah/bitmap.c:105
#3  0x005426fc in test_bitmap_walk (revs=0x22f93c) at pack-bitmap.c:954
#4  0x0046b6ae in cmd_rev_list (argc=2, argv=0x3e263c, prefix=0x0)
    at builtin/rev-list.c:329
#5  0x00402048 in run_builtin (p=0x56d41c, argc=3, argv=0x3e263c) at git.c:314
#6  0x0040224f in handle_builtin (argc=3, argv=0x3e263c) at git.c:487
#7  0x00402351 in run_argv (argcp=0x22ff50, argv=0x22ff38) at git.c:533
#8  0x0040257f in mingw_main (argc=3, av=0x3e2638) at git.c:616
#9  0x0040242e in main (argc=4, argv=0x3e2638) at git.c:551
(gdb) up
#1  0x00487c4c in xrealloc (ptr=0x12b10008, size=837107040) at wrapper.c:109
109                             die("Out of memory, realloc failed");
(gdb) up
#2  0x0055572b in ewah_to_bitmap (ewah=0xe58c18) at ewah/bitmap.c:105
105                             bitmap->words = ewah_realloc(
(gdb) l
100             ewah_iterator_init(&it, ewah);
101
102             while (ewah_iterator_next(&blowup, &it)) {
103                     if (i >= bitmap->word_alloc) {
104                             bitmap->word_alloc *= 1.5;
105                             bitmap->words = ewah_realloc(
106                                     bitmap->words, bitmap->word_alloc * sizeof(eword_t));
107                     }
108
109                     bitmap->words[i++] = blowup;
(gdb) info locals
bitmap = (struct bitmap *) 0xe58aa0
it = {buffer = 0xe58cd0, buffer_size = 2, pointer = 1, compressed = 52981705,
  literals = 0, rl = 2141159439, lw = 8259520, b = 1}
blowup = 18446744073709551615
i = 69758920
(gdb) info args
ewah = (struct ewah_bitmap *) 0xe58c18
(gdb)

This is after "not ok 3 - rev-list --test-bitmap verifies bitmaps".
Numerous further test cases fail, but I didn't look at them.

-- Hannes

Re: pack bitmap woes on Windows

[Erik Faye-Lund]

On Wed, Feb 12, 2014 at 8:27 AM, Johannes Sixt <j.sixt@viscovery.net> wrote:
> Running test suite of 'next' on Windows fails in t5310-pack-bitmaps with
> the following symptoms. I haven't followed the topic. Have there been
> patches floating that addressed the problem in one way or another?
>
> (gdb) run
> Starting program: D:\Src\mingw-git\t\trash directory.t5310-pack-bitmaps/..\..\git.exe rev-list --test-bitmap HEAD
> [New thread 3528.0x8d4]
> Bitmap v1 test (20 entries loaded)
> Found bitmap for 537ea4d3eb79c95f602873b1167c480006d2ac2d. 64 bits / 15873b36 checksum
>
> Breakpoint 1, die (err=0x5939e9 "Out of memory, realloc failed") at usage.c:97
> 97              if (die_is_recursing()) {
> (gdb) bt
> #0  die (err=0x5939e9 "Out of memory, realloc failed") at usage.c:97
> #1  0x00487c4c in xrealloc (ptr=0x12b10008, size=837107040) at wrapper.c:109

~800 megs is a pretty large allocation for 32-bit systems. What gives?

Re: pack bitmap woes on Windows

[Johannes Sixt]

Am 2/12/2014 12:56, schrieb Erik Faye-Lund:
> On Wed, Feb 12, 2014 at 8:27 AM, Johannes Sixt <j.sixt@viscovery.net> wrote:
>> Running test suite of 'next' on Windows fails in t5310-pack-bitmaps with
>> the following symptoms. I haven't followed the topic. Have there been
>> patches floating that addressed the problem in one way or another?
>>
>> (gdb) run
>> Starting program: D:\Src\mingw-git\t\trash directory.t5310-pack-bitmaps/..\..\git.exe rev-list --test-bitmap HEAD
>> [New thread 3528.0x8d4]
>> Bitmap v1 test (20 entries loaded)
>> Found bitmap for 537ea4d3eb79c95f602873b1167c480006d2ac2d. 64 bits / 15873b36 checksum
>>
>> Breakpoint 1, die (err=0x5939e9 "Out of memory, realloc failed") at usage.c:97
>> 97              if (die_is_recursing()) {
>> (gdb) bt
>> #0  die (err=0x5939e9 "Out of memory, realloc failed") at usage.c:97
>> #1  0x00487c4c in xrealloc (ptr=0x12b10008, size=837107040) at wrapper.c:109
> 
> ~800 megs is a pretty large allocation for 32-bit systems. What gives?

That's exactly the problem: why would a tiny repository from the test
suite require such a large allocation? (Not to mention that the allocation
ultimately fails in my case.)

Re: pack bitmap woes on Windows

[David Kastrup]

Johannes Sixt <j.sixt@viscovery.net> writes:

> Running test suite of 'next' on Windows fails in t5310-pack-bitmaps with
> the following symptoms. I haven't followed the topic. Have there been
> patches floating that addressed the problem in one way or another?
>
> (gdb) run
> Starting program: D:\Src\mingw-git\t\trash directory.t5310-pack-bitmaps/..\..\git.exe rev-list --test-bitmap HEAD
> [New thread 3528.0x8d4]
> Bitmap v1 test (20 entries loaded)
> Found bitmap for 537ea4d3eb79c95f602873b1167c480006d2ac2d. 64 bits / 15873b36 checksum

Does reverting a201c20b41a2f0725977bcb89a2a66135d776ba2 help?

-- 
David Kastrup

Re: pack bitmap woes on Windows

[Johannes Sixt]

Am 2/12/2014 13:55, schrieb David Kastrup:
> Johannes Sixt <j.sixt@viscovery.net> writes:
> 
>> Running test suite of 'next' on Windows fails in t5310-pack-bitmaps with
>> the following symptoms. I haven't followed the topic. Have there been
>> patches floating that addressed the problem in one way or another?
>>
>> (gdb) run
>> Starting program: D:\Src\mingw-git\t\trash directory.t5310-pack-bitmaps/..\..\git.exe rev-list --test-bitmap HEAD
>> [New thread 3528.0x8d4]
>> Bitmap v1 test (20 entries loaded)
>> Found bitmap for 537ea4d3eb79c95f602873b1167c480006d2ac2d. 64 bits / 15873b36 checksum
> 
> Does reverting a201c20b41a2f0725977bcb89a2a66135d776ba2 help?

YES! t5310 passes after reverting this commit.

-- Hannes

Re: pack bitmap woes on Windows

[David Kastrup]

Johannes Sixt <j.sixt@viscovery.net> writes:

> Am 2/12/2014 13:55, schrieb David Kastrup:
>> Johannes Sixt <j.sixt@viscovery.net> writes:
>> 
>>> Running test suite of 'next' on Windows fails in t5310-pack-bitmaps with
>>> the following symptoms. I haven't followed the topic. Have there been
>>> patches floating that addressed the problem in one way or another?
>>>
>>> (gdb) run
>>> Starting program: D:\Src\mingw-git\t\trash
>>> directory.t5310-pack-bitmaps/..\..\git.exe rev-list --test-bitmap
>>> HEAD
>>> [New thread 3528.0x8d4]
>>> Bitmap v1 test (20 entries loaded)
>>> Found bitmap for 537ea4d3eb79c95f602873b1167c480006d2ac2d. 64 bits
>>> / 15873b36 checksum
>> 
>> Does reverting a201c20b41a2f0725977bcb89a2a66135d776ba2 help?
>
> YES! t5310 passes after reverting this commit.

Oh.  I just looked through the backtrace until finding a routine
reasonably related with the regtest and checked for the last commit
changing it, then posted my question.

Then I looked through the diff of the patch and considered it
unconspicuous.  So I commenced reading through earlier commits.

I actually don't have a good idea what might be wrong here.  The code is
somewhat distasteful as it basically uses eword_t and uint64_t
interchangeably, but then this does match its current definition.

-- 
David Kastrup

Re: pack bitmap woes on Windows

[Duy Nguyen]

On Wed, Feb 12, 2014 at 8:23 PM, David Kastrup <dak@gnu.org> wrote:
> Johannes Sixt <j.sixt@viscovery.net> writes:
>
>> Am 2/12/2014 13:55, schrieb David Kastrup:
>>> Johannes Sixt <j.sixt@viscovery.net> writes:
>>>
>>>> Running test suite of 'next' on Windows fails in t5310-pack-bitmaps with
>>>> the following symptoms. I haven't followed the topic. Have there been
>>>> patches floating that addressed the problem in one way or another?
>>>>
>>>> (gdb) run
>>>> Starting program: D:\Src\mingw-git\t\trash
>>>> directory.t5310-pack-bitmaps/..\..\git.exe rev-list --test-bitmap
>>>> HEAD
>>>> [New thread 3528.0x8d4]
>>>> Bitmap v1 test (20 entries loaded)
>>>> Found bitmap for 537ea4d3eb79c95f602873b1167c480006d2ac2d. 64 bits
>>>> / 15873b36 checksum
>>>
>>> Does reverting a201c20b41a2f0725977bcb89a2a66135d776ba2 help?
>>
>> YES! t5310 passes after reverting this commit.
>
> Oh.  I just looked through the backtrace until finding a routine
> reasonably related with the regtest and checked for the last commit
> changing it, then posted my question.
>
> Then I looked through the diff of the patch and considered it
> unconspicuous.  So I commenced reading through earlier commits.
>
> I actually don't have a good idea what might be wrong here.  The code is
> somewhat distasteful as it basically uses eword_t and uint64_t
> interchangeably, but then this does match its current definition.

Perhaps __BYTE_ORDER or __BIG_ENDIAN is misdefined and the ntohll() is skipped?
-- 
Duy

Re: pack bitmap woes on Windows

[Erik Faye-Lund]

On Wed, Feb 12, 2014 at 3:09 PM, Duy Nguyen <pclouds@gmail.com> wrote:
> On Wed, Feb 12, 2014 at 8:23 PM, David Kastrup <dak@gnu.org> wrote:
>> Johannes Sixt <j.sixt@viscovery.net> writes:
>>
>>> Am 2/12/2014 13:55, schrieb David Kastrup:
>>>> Johannes Sixt <j.sixt@viscovery.net> writes:
>>>>
>>>>> Running test suite of 'next' on Windows fails in t5310-pack-bitmaps with
>>>>> the following symptoms. I haven't followed the topic. Have there been
>>>>> patches floating that addressed the problem in one way or another?
>>>>>
>>>>> (gdb) run
>>>>> Starting program: D:\Src\mingw-git\t\trash
>>>>> directory.t5310-pack-bitmaps/..\..\git.exe rev-list --test-bitmap
>>>>> HEAD
>>>>> [New thread 3528.0x8d4]
>>>>> Bitmap v1 test (20 entries loaded)
>>>>> Found bitmap for 537ea4d3eb79c95f602873b1167c480006d2ac2d. 64 bits
>>>>> / 15873b36 checksum
>>>>
>>>> Does reverting a201c20b41a2f0725977bcb89a2a66135d776ba2 help?
>>>
>>> YES! t5310 passes after reverting this commit.
>>
>> Oh.  I just looked through the backtrace until finding a routine
>> reasonably related with the regtest and checked for the last commit
>> changing it, then posted my question.
>>
>> Then I looked through the diff of the patch and considered it
>> unconspicuous.  So I commenced reading through earlier commits.
>>
>> I actually don't have a good idea what might be wrong here.  The code is
>> somewhat distasteful as it basically uses eword_t and uint64_t
>> interchangeably, but then this does match its current definition.
>
> Perhaps __BYTE_ORDER or __BIG_ENDIAN is misdefined and the ntohll() is skipped?

That is indeed the case.

Re: pack bitmap woes on Windows

[Erik Faye-Lund]

On Wed, Feb 12, 2014 at 3:22 PM, Erik Faye-Lund <kusmabite@gmail.com> wrote:
> On Wed, Feb 12, 2014 at 3:09 PM, Duy Nguyen <pclouds@gmail.com> wrote:
>> On Wed, Feb 12, 2014 at 8:23 PM, David Kastrup <dak@gnu.org> wrote:
>>> Johannes Sixt <j.sixt@viscovery.net> writes:
>>>
>>>> Am 2/12/2014 13:55, schrieb David Kastrup:
>>>>> Johannes Sixt <j.sixt@viscovery.net> writes:
>>>>>
>>>>>> Running test suite of 'next' on Windows fails in t5310-pack-bitmaps with
>>>>>> the following symptoms. I haven't followed the topic. Have there been
>>>>>> patches floating that addressed the problem in one way or another?
>>>>>>
>>>>>> (gdb) run
>>>>>> Starting program: D:\Src\mingw-git\t\trash
>>>>>> directory.t5310-pack-bitmaps/..\..\git.exe rev-list --test-bitmap
>>>>>> HEAD
>>>>>> [New thread 3528.0x8d4]
>>>>>> Bitmap v1 test (20 entries loaded)
>>>>>> Found bitmap for 537ea4d3eb79c95f602873b1167c480006d2ac2d. 64 bits
>>>>>> / 15873b36 checksum
>>>>>
>>>>> Does reverting a201c20b41a2f0725977bcb89a2a66135d776ba2 help?
>>>>
>>>> YES! t5310 passes after reverting this commit.
>>>
>>> Oh.  I just looked through the backtrace until finding a routine
>>> reasonably related with the regtest and checked for the last commit
>>> changing it, then posted my question.
>>>
>>> Then I looked through the diff of the patch and considered it
>>> unconspicuous.  So I commenced reading through earlier commits.
>>>
>>> I actually don't have a good idea what might be wrong here.  The code is
>>> somewhat distasteful as it basically uses eword_t and uint64_t
>>> interchangeably, but then this does match its current definition.
>>
>> Perhaps __BYTE_ORDER or __BIG_ENDIAN is misdefined and the ntohll() is skipped?
>
> That is indeed the case.

Looking a bit at it, the whole byte-order detection mess seems insane to me.

MinGW falls inside the "defined(__GNUC__) && (defined(__i386__) ||
defined(__x86_64__))"-block, but does not define __BYTE_ORDER.

It seems the author of a201c20b41a2f0725977bcb89a2a66135d776ba2
assumes __BYTE_ORDER was guaranteed to always be defined, probably
fooled by the following check:

#if !defined(__BYTE_ORDER)
# error "Cannot determine endianness"
#endif

However, that check is only performed if we're NOT building with GCC
on x86/x64 nor MSVC (which I don't think defined __BYTE_ORDER either)

The following would make __BYTE_ORDER a guarantee, and show that MinGW
does not define it:

---8<---

diff --git a/compat/bswap.h b/compat/bswap.h
index 120c6c1..c73bf0e 100644
--- a/compat/bswap.h
+++ b/compat/bswap.h
@@ -109,10 +109,6 @@ static inline uint64_t git_bswap64(uint64_t x)
 # endif
 #endif

-#if !defined(__BYTE_ORDER)
-# error "Cannot determine endianness"
-#endif
-
 #if __BYTE_ORDER == __BIG_ENDIAN
 # define ntohll(n) (n)
 # define htonll(n) (n)
@@ -123,6 +119,10 @@ static inline uint64_t git_bswap64(uint64_t x)

 #endif

+#if !defined(__BYTE_ORDER)
+# error "Cannot determine endianness"
+#endif
+
 /*
  * Performance might be improved if the CPU architecture is OK with
  * unaligned 32-bit loads and a fast ntohl() is available.

---8<---

But another level of insanity (IMO) is defining double-underscore
macros. These symbols are reserved for the implementation. Sure,
knowing we're on a given implementation and defining something *else*
dependent on them is fine. But defining them is just yuckiness, and
not very standard-kosher.

IMO, we should rather do the definition the other way around:

#if !defined(BYTE_ORDER)
# if defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && defined(__BIG_ENDIAN)
#  define BYTE_ORDER __BYTE_ORDER
#  define LITTLE_ENDIAN __LITTLE_ENDIAN
#  define BIG_ENDIAN __BIG_ENDIAN
# endif
#endif

...and only referred to BYTE_ORDER, LITTLE_ENDIAN and BIG_ENDIAN.


That way we'd follow closer to where opengroup are heading:

http://www.opengroup.org/austin/docs/austin_514.txt

Re: pack bitmap woes on Windows

[Jeff King]

On Wed, Feb 12, 2014 at 03:49:24PM +0100, Erik Faye-Lund wrote:

> It seems the author of a201c20b41a2f0725977bcb89a2a66135d776ba2
> assumes __BYTE_ORDER was guaranteed to always be defined, probably
> fooled by the following check:
> 
> #if !defined(__BYTE_ORDER)
> # error "Cannot determine endianness"
> #endif
> 
> However, that check is only performed if we're NOT building with GCC
> on x86/x64 nor MSVC (which I don't think defined __BYTE_ORDER either)
> 
> The following would make __BYTE_ORDER a guarantee, and show that MinGW
> does not define it:

Yes, that is the problem. Sorry, this got brought up earlier[1], but the
discussion went on and I did not notice that Brian's patch did not get
applied.

After re-reading the discussion, I think the patch below is the best
solution. Can you confirm that it fixes the problem for you?

-Peff

[1] http://thread.gmane.org/gmane.comp.version-control.git/241278

-- >8 --
Subject: ewah: unconditionally ntohll ewah data

Commit a201c20 tried to optimize out a loop like:

  for (i = 0; i < len; i++)
	  data[i] = ntohll(data[i]);

in the big-endian case, because we know that ntohll is a
noop, and we do not need to pay the cost of the loop at all.
However, it mistakenly assumed that __BYTE_ORDER was always
defined, whereas it may not be on systems which do not
define it by default, and where we did not need to define it
to set up the ntohll macro. This includes OS X and Windows.

We could muck with the ordering in compat/bswap.h to make
sure it is defined unconditionally, but it is simpler to
still to just execute the loop unconditionally. That avoids
the application code knowing anything about these magic
macros, and lets it depend only on having ntohll defined.

And since the resulting loop looks like (on a big-endian
system):

  for (i = 0; i < len; i++)
	  data[i] = data[i];

any decent compiler can probably optimize it out.

Original report and analysis by Brian Gernhardt.

Signed-off-by: Jeff King <peff@peff.net>
---
 ewah/ewah_io.c | 10 +++-------
 1 file changed, 3 insertions(+), 7 deletions(-)

diff --git a/ewah/ewah_io.c b/ewah/ewah_io.c
index 4a7fae6..f7f700e 100644
--- a/ewah/ewah_io.c
+++ b/ewah/ewah_io.c
@@ -113,6 +113,7 @@ int ewah_serialize(struct ewah_bitmap *self, int fd)
 int ewah_read_mmap(struct ewah_bitmap *self, void *map, size_t len)
 {
 	uint8_t *ptr = map;
+	size_t i;
 
 	self->bit_size = get_be32(ptr);
 	ptr += sizeof(uint32_t);
@@ -135,13 +136,8 @@ int ewah_read_mmap(struct ewah_bitmap *self, void *map, size_t len)
 	memcpy(self->buffer, ptr, self->buffer_size * sizeof(uint64_t));
 	ptr += self->buffer_size * sizeof(uint64_t);
 
-#if __BYTE_ORDER != __BIG_ENDIAN
-	{
-		size_t i;
-		for (i = 0; i < self->buffer_size; ++i)
-			self->buffer[i] = ntohll(self->buffer[i]);
-	}
-#endif
+	for (i = 0; i < self->buffer_size; ++i)
+		self->buffer[i] = ntohll(self->buffer[i]);
 
 	self->rlw = self->buffer + get_be32(ptr);
 
-- 
1.8.5.2.500.g8060133

Re: pack bitmap woes on Windows

[Johannes Sixt]

Am 2/12/2014 17:48, schrieb Jeff King:
> On Wed, Feb 12, 2014 at 03:49:24PM +0100, Erik Faye-Lund wrote:
> 
>> It seems the author of a201c20b41a2f0725977bcb89a2a66135d776ba2
>> assumes __BYTE_ORDER was guaranteed to always be defined, probably
>> fooled by the following check:
>>
>> #if !defined(__BYTE_ORDER)
>> # error "Cannot determine endianness"
>> #endif
>>
>> However, that check is only performed if we're NOT building with GCC
>> on x86/x64 nor MSVC (which I don't think defined __BYTE_ORDER either)
>>
>> The following would make __BYTE_ORDER a guarantee, and show that MinGW
>> does not define it:
> 
> Yes, that is the problem. Sorry, this got brought up earlier[1], but the
> discussion went on and I did not notice that Brian's patch did not get
> applied.
> 
> After re-reading the discussion, I think the patch below is the best
> solution. Can you confirm that it fixes the problem for you?

Yes, it fixes the problem! t5310-pack-bitmaps passes all tests with the patch.

Thanks,
-- Hannes

> 
> -Peff
> 
> [1] http://thread.gmane.org/gmane.comp.version-control.git/241278
> 
> -- >8 --
> Subject: ewah: unconditionally ntohll ewah data
> 
> Commit a201c20 tried to optimize out a loop like:
> 
>   for (i = 0; i < len; i++)
> 	  data[i] = ntohll(data[i]);
> 
> in the big-endian case, because we know that ntohll is a
> noop, and we do not need to pay the cost of the loop at all.
> However, it mistakenly assumed that __BYTE_ORDER was always
> defined, whereas it may not be on systems which do not
> define it by default, and where we did not need to define it
> to set up the ntohll macro. This includes OS X and Windows.
> 
> We could muck with the ordering in compat/bswap.h to make
> sure it is defined unconditionally, but it is simpler to
> still to just execute the loop unconditionally. That avoids
> the application code knowing anything about these magic
> macros, and lets it depend only on having ntohll defined.
> 
> And since the resulting loop looks like (on a big-endian
> system):
> 
>   for (i = 0; i < len; i++)
> 	  data[i] = data[i];
> 
> any decent compiler can probably optimize it out.
> 
> Original report and analysis by Brian Gernhardt.
> 
> Signed-off-by: Jeff King <peff@peff.net>
> ---
>  ewah/ewah_io.c | 10 +++-------
>  1 file changed, 3 insertions(+), 7 deletions(-)
> 
> diff --git a/ewah/ewah_io.c b/ewah/ewah_io.c
> index 4a7fae6..f7f700e 100644
> --- a/ewah/ewah_io.c
> +++ b/ewah/ewah_io.c
> @@ -113,6 +113,7 @@ int ewah_serialize(struct ewah_bitmap *self, int fd)
>  int ewah_read_mmap(struct ewah_bitmap *self, void *map, size_t len)
>  {
>  	uint8_t *ptr = map;
> +	size_t i;
>  
>  	self->bit_size = get_be32(ptr);
>  	ptr += sizeof(uint32_t);
> @@ -135,13 +136,8 @@ int ewah_read_mmap(struct ewah_bitmap *self, void *map, size_t len)
>  	memcpy(self->buffer, ptr, self->buffer_size * sizeof(uint64_t));
>  	ptr += self->buffer_size * sizeof(uint64_t);
>  
> -#if __BYTE_ORDER != __BIG_ENDIAN
> -	{
> -		size_t i;
> -		for (i = 0; i < self->buffer_size; ++i)
> -			self->buffer[i] = ntohll(self->buffer[i]);
> -	}
> -#endif
> +	for (i = 0; i < self->buffer_size; ++i)
> +		self->buffer[i] = ntohll(self->buffer[i]);
>  
>  	self->rlw = self->buffer + get_be32(ptr);
>  
>