Re: [PATCH v4 08/23] ewah: compressed bitmap implementation

[Jonathan Nieder <jrnieder@gmail.com>]

Hi,

Jeff King wrote:

> EWAH is a word-aligned compressed variant of a bitset (i.e. a data
> structure that acts as a 0-indexed boolean array for many entries).

I suspect that for some callers it's not word-aligned.

Without the following squashed in, commits 212f2ffb and later fail t5310
on some machines[1].

On ARMv5:

	expecting success: 
		git rev-list --test-bitmap HEAD

	*** Error in `/«PKGBUILDDIR»/git': realloc(): invalid pointer: 0x008728b0 ***
	Aborted
	not ok 3 - rev-list --test-bitmap verifies bitmaps

On sparc:

	expecting success: 
		git rev-list --test-bitmap HEAD

	Bus error
	not ok 3 - rev-list --test-bitmap verifies bitmaps

Hopefully it's possible to get the alignment right in the caller
and tweak the signature to require that instead of using unaligned
reads like this.  There's still something wrong after this patch ---
the new result is a NULL pointer dereference in t5310.7 "enumerate
--objects (full bitmap)".

  (gdb) run
  Starting program: /home/jrnieder/src/git/git rev-list --objects --use-bitmap-index HEAD
  [Thread debugging using libthread_db enabled]
  Using host libthread_db library "/lib/sparc-linux-gnu/libthread_db.so.1".
  537ea4d3eb79c95f602873b1167c480006d2ac2d
[...]
  ec635144f60048986bc560c5576355344005e6e7

  Program received signal SIGSEGV, Segmentation fault.
  0x001321c0 in sha1_to_hex (sha1=0x0) at hex.c:68
  68                      unsigned int val = *sha1++;
  (gdb) bt
  #0  0x001321c0 in sha1_to_hex (sha1=0x0) at hex.c:68
  #1  0x000b839c in show_object_fast (sha1=0x0, type=OBJ_TREE, exclude=0, name_hash=0, found_pack=0x2b8480, found_offset=4338) at builtin/rev-list.c:270
  #2  0x00158abc in show_objects_for_type (objects=0x2b2498, type_filter=0x2b0fb0, object_type=OBJ_TREE, show_reach=0xb834c <show_object_fast>) at pack-bitmap.c:640
  #3  0x001592d0 in traverse_bitmap_commit_list (show_reachable=0xb834c <show_object_fast>) at pack-bitmap.c:818
  #4  0x000b894c in cmd_rev_list (argc=2, argv=0xffffd688, prefix=0x0) at builtin/rev-list.c:369
  #5  0x00014024 in run_builtin (p=0x256e38 <commands+1020>, argc=4, argv=0xffffd688) at git.c:314
  #6  0x00014330 in handle_builtin (argc=4, argv=0xffffd688) at git.c:487
  #7  0x000144a8 in run_argv (argcp=0xffffd5ec, argv=0xffffd5a0) at git.c:533
  #8  0x000146fc in main (argc=4, av=0xffffd684) at git.c:616
  (gdb) frame 2
  #2  0x00158abc in show_objects_for_type (objects=0x2b2498, type_filter=0x2b0fb0, object_type=OBJ_TREE, show_reach=0xb834c <show_object_fast>) at pack-bitmap.c:640
  640                             show_reach(sha1, object_type, 0, hash, bitmap_git.pack, entry->offset);
  (gdb) p entry->nr
  $1 = 4294967295

Line numbers are in the context of 8e6341d9.  Ideas?

[1] ARMv5 and sparc:
https://buildd.debian.org/status/logs.php?pkg=git&suite=experimental

diff --git a/ewah/ewah_io.c b/ewah/ewah_io.c
index aed0da6..696a8ec 100644
--- a/ewah/ewah_io.c
+++ b/ewah/ewah_io.c
@@ -110,25 +110,38 @@ int ewah_serialize(struct ewah_bitmap *self, int fd)
 	return ewah_serialize_to(self, write_helper, (void *)(intptr_t)fd);
 }
 
+#define get_be32(p) ( \
+	(*((unsigned char *)(p) + 0) << 24) | \
+	(*((unsigned char *)(p) + 1) << 16) | \
+	(*((unsigned char *)(p) + 2) <<  8) | \
+	(*((unsigned char *)(p) + 3) <<  0) )
+
+#define get_be64(p) ( \
+	((uint64_t) get_be32(p) << 32) | \
+	get_be32((unsigned char *)(p) + 4) )
+
 int ewah_read_mmap(struct ewah_bitmap *self, void *map, size_t len)
 {
-	uint32_t *read32 = map;
-	eword_t *read64;
+	unsigned char *p = map;
 	size_t i;
 
-	self->bit_size = ntohl(*read32++);
-	self->buffer_size = self->alloc_size = ntohl(*read32++);
+	self->bit_size = get_be32(p);
+	p += 4;
+	self->buffer_size = self->alloc_size = get_be32(p);
+	p += 4;
 	self->buffer = ewah_realloc(self->buffer,
 		self->alloc_size * sizeof(eword_t));
 
 	if (!self->buffer)
 		return -1;
 
-	for (i = 0, read64 = (void *)read32; i < self->buffer_size; ++i)
-		self->buffer[i] = ntohll(*read64++);
+	for (i = 0; i < self->buffer_size; ++i) {
+		self->buffer[i] = get_be64(p);
+		p += 8;
+	}
 
-	read32 = (void *)read64;
-	self->rlw = self->buffer + ntohl(*read32++);
+	self->rlw = self->buffer + get_be32(p);
+	p += 4;
 
 	return (3 * 4) + (self->buffer_size * 8);
 }