a bug when execute "git status" in git version 1.7.7.431.g89633

the error:
git: malloc.c:3096: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed.

When does this error occur? is it reproducible on any repository? Which OS?

The assertion is violated outside the source code of Git itself, so either Git calls malloc incorrectly, or this is a bug in your libc.

Matthieu Moy
http://www-verimag.imag.fr/~moy/

ok,when i finish compiling git 1.7.7.431.g89633，I use it to check Cyanogenod（an Android mod source） by “git status”，it happend this error！but when i reuse git v1.7.7，it is OK！so i think it is a bug in git 1.7.7.431.g89633！My OS is Ubuntu Linux 10.10，sorry for my bad english！ If you want to reproduce this error,please excute "git status" in https://github.com/CyanogenMod/android_packages_apps_DSPManager.git repo!

于2011年10月23日 星期日 16时25分28秒,Matthieu Moy写到:

Am 23.10.2011 10:35, schrieb John Hsing:

I can reproduce the malloc crash on Ubuntu 11.10 with these simple steps:

	$ a=android_packages_apps_DSPManager
	$ git-v1.7.7 clone https://github.com/CyanogenMod/$a.git
	Cloning into android_packages_apps_DSPManager...
	remote: Counting objects: 902, done.
	remote: Compressing objects: 100% (412/412), done.
	remote: Total 902 (delta 367), reused 838 (delta 324)
	Receiving objects: 100% (902/902), 136.78 KiB | 264 KiB/s, done.
	Resolving deltas: 100% (367/367), done.
	$ cd $a

	$ git-v1.7.7 status
	# On branch gingerbread
	nothing to commit (working directory clean)

	$ git-master status
	git: malloc.c:3096: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed.
	Aborted

Bisect points to 2548183ba, "fix phantom untracked files when core.ignorecase is set" from Jeff (cc:d). If I revert that patch from master (8963314c), git status works fine.

The following experimental patch fixes it for me as well, but I can't claim to know exactly why. In any case, estimate_cache_size() seems to guess too low.

René

---
 read-cache.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

index 01a0e25..b143bd3 100644
@@ -1257,7 +1257,7 @@ static inline size_t estimate_cache_size(size_t ondisk_size, unsigned int entrie
 	 * Alignment can cause differences. This should be "alignof", but
 	 * since that's a gcc'ism, just use the size of a pointer.
 	 */
-	per_entry += sizeof(void *);
+	per_entry += 2 * sizeof(void *);
 	return ondisk_size + entries*per_entry;
 }
 

Hmm. Interesting. I can't reproduce here. And I've been running with this patch for over a year, and never seen that. Given your fix, I guess it's related to pointer size. Are you on a 32-bit machine, by any chance?

-Peff

Am 23.10.2011 18:29, schrieb Jeff King:

Yes, it's a 32-bit VM. I think it's a case of unlucky filename lengths, combined with the rounding up to the next multiple of 8. The following table lists the actual size needed for entries based on the length of their name entry. Length calculation uses these offsets:

	offsetof(struct cache_entry, name) == 72
	offsetof(struct ondisk_cache_entry, name) == 62

	len  ce_size                 ondisk_ce_size          delta
	  1  (72 + 1 + 8) & ~7 = 80  (62 + 1 + 8) & ~7 = 64     16
	  2  (72 + 2 + 8) & ~7 = 80  (62 + 2 + 8) & ~7 = 72      8
	  3  (72 + 3 + 8) & ~7 = 80  (62 + 3 + 8) & ~7 = 72      8
	  4  (72 + 4 + 8) & ~7 = 80  (62 + 4 + 8) & ~7 = 72      8
	  5  (72 + 5 + 8) & ~7 = 80  (62 + 5 + 8) & ~7 = 72      8
	  6  (72 + 6 + 8) & ~7 = 80  (62 + 6 + 8) & ~7 = 72      8
	  7  (72 + 7 + 8) & ~7 = 80  (62 + 7 + 8) & ~7 = 72      8
	  8  (72 + 8 + 8) & ~7 = 88  (62 + 8 + 8) & ~7 = 72     16

So in 25% of the cases an entry needs 16 bytes more in memory than on disk and the rest needs 8 bytes more.

estimate_cache_size() calculates the amount of memory needed for the index, based on its on-disk representation. It simply adds the difference of the sizes of the two structs and the size of a pointer for each entry to its total size and returns that number. I have:

	sizeof(void *) == 4
	sizeof(struct cache_entry) == 72
	sizeof(struct ondisk_cache_entry) == 64

So each entry gets 72 - 64 + 4 = 12 bytes extra. If you happen to have a lot of filenames with a delta of 16 then the resulting size won't be enough to hold the in-memory index.

Is there a nice way to derive that we need 16 bytes per entry in the worst case, preferably without trying all eight possibilities as I did in the table above? My modular math is rusty..

René

estimate_cache_size() tries to guess how much memory is needed for the in-memory representation of an index file. It does that by using the file size, the number of entries and the difference of the sizes of the on-disk and in-memory structs -- without having to check the length of the name of each entry, which varies for each entry, but their sums are the same no matter the representation.

Except there can be a difference. First of all, the size is really calculated by ce_size and ondisk_ce_size based on offsetof(..., name), not sizeof, which can be different. And entries are padded with 1 to 8 NULs at the end (after the variable name) to make their total length a multiple of eight.

So in order to allocate enough memory to hold the index, change the delta calculation to be based on offsetof(..., name) and round up to the next multiple of eight.

On a 32-bit Linux, this delta was used before:

	sizeof(struct cache_entry)        == 72
	sizeof(struct ondisk_cache_entry) == 64
	                                    ---
	                                      8

The actual difference for an entry with a filename length of one was, however (find the definitions are in cache.h):

	offsetof(struct cache_entry, name)        == 72
	offsetof(struct ondisk_cache_entry, name) == 62

	ce_size        == (72 + 1 + 8) & ~7 == 80
	ondisk_ce_size == (62 + 1 + 8) & ~7 == 64
	                                      ---
	                                       16

So eight bytes less had been allocated for such entries. The new formula yields the correct delta:

	(72 - 62 + 7) & ~7 == 16

---
 read-cache.c            |    6 ++--
 t/t7510-status-index.sh |   50 +++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 53 insertions(+), 3 deletions(-)
 create mode 100755 t/t7510-status-index.sh

index 01a0e25..5790a91 100644
@@ -1249,9 +1249,9 @@ static void convert_from_disk(struct ondisk_cache_entry *ondisk, struct cache_en
 
 static inline size_t estimate_cache_size(size_t ondisk_size, unsigned int entries)
 {
-	long per_entry;
-
-	per_entry = sizeof(struct cache_entry) - sizeof(struct ondisk_cache_entry);
+	size_t fix_size_mem = offsetof(struct cache_entry, name);
+	size_t fix_size_dsk = offsetof(struct ondisk_cache_entry, name);
+	long per_entry = (fix_size_mem - fix_size_dsk + 7) & ~7;
 
 	/*
 	 * Alignment can cause differences. This should be "alignof", but

1.7.7

Am 24.10.2011 09:28, schrieb Junio C Hamano:

Err, yes, I forgot to mention in the commit message that on my test system the breakage occurs only after 2548183ba, "fix phantom untracked files when core.ignorecase is set", which adds the pointer dir_next to struct cache_entry. This seems to have caused an unlucky constellation of offsets and struct sizes for the size estimator.

Only a little, I suspect. If we've moved past the end then it's too late. And if we catch the error before it happens, dying is only slightly better than crashing.

Thanks.

This approach may be the most appropriate for the maintenance track, but for the purpose of going forward, I wonder if we really want to keep the "estimate and allocate a large pool, and carve out individual pieces".

This bulk-allocate dates back to the days when we didn't have ondisk vs incore representation differences, IIRC, and as the result we deliberately leak cache entries whenever an entry in the index is replaced with a new one. Does the overhead to allocate individually really kill us that much for say a tree with 30k files in it?

Am 24.10.2011 09:07, schrieb Junio C Hamano:

Probably not; unpack_trees() does that already. (It calls create_ce_entry() via unpack_nondirectories() via unpack_callback() via traverse_trees()).

René

Am 24.10.2011 09:07, schrieb Junio C Hamano:

Something like this (applies to master)? Very basic testing didn't show any slowdown of git status in the Linux repo.

-- >8 --
Subject: read-cache.c: allocate index entries individually

The code to estimate the in-memory size of the index based on its on-disk representation is subtly wrong for certain architecture-dependent struct layouts. Instead of fixing it, replace the code to keep the index entries in a single large block of memory and allocate each entry separately instead. This is both simpler and more flexible, as individual entries can now be freed. Actually using that added flexibility is left for a later patch.

---
Note: This patch was brought to you by the option --histogram, which produced nicer output than the default diff method.

 cache.h      |    1 -
 read-cache.c |   86 +++++++++++++++++++++++----------------------------------
 2 files changed, 35 insertions(+), 52 deletions(-)

index be07ec7..ec0e571 100644
@@ -316,7 +316,6 @@ struct index_state {
 	struct string_list *resolve_undo;
 	struct cache_tree *cache_tree;
 	struct cache_time timestamp;
-	void *alloc;
 	unsigned name_hash_initialized : 1,
 		 initialized : 1;
 	struct hash_table name_hash;

1.7.7

"git status" is slow. If your changes causes slowdown, it won't likely stand out while other fast commands may show (read_cache() is used in nearly all commands). So I tested using the following patch.

The result on linux-2.6 shows about 10-20 us slowdown per each read_cache() call (30-40 us on webkit, ~50k files) I think your patch is good enough :-)

-- 8< --

index 3139c19..c8b47bc 100644
@@ -444,6 +444,7 @@ TEST_PROGRAMS_NEED_X += test-string-pool
 TEST_PROGRAMS_NEED_X += test-subprocess
 TEST_PROGRAMS_NEED_X += test-svn-fe
 TEST_PROGRAMS_NEED_X += test-treap
+TEST_PROGRAMS_NEED_X += test-read-cache
 
 TEST_PROGRAMS = $(patsubst %,%$X,$(TEST_PROGRAMS_NEED_X))
 

index e69de29..1ad80a0 100644
@@ -0,0 +1,14 @@
+#include "cache.h"
+
+int main(int argc, char **argv)
+{
+	struct timeval tv1, tv2;
+	int i;
+
+	gettimeofday(&tv1, NULL);
+	for (i = 0; i < 100; i++)
+		read_cache();
+	gettimeofday(&tv2, NULL);
+	printf("%lu\n", (unsigned long)(tv2.tv_usec - tv1.tv_usec));
+	return 0;
+}

-- 8< --

That was with -O0 by the way. valgrind/massif shows about 200kb memory more with your patch on webkit repository (7.497 MB vs 7.285 MB), using the same test, so memory overhead is ok too.

Duy

Am 25.10.2011 02:01, schrieb Nguyen Thai Ngoc Duy:

We can reduce that a bit -- unless block allocation of index entries is still done somewhere.

-- >8 --
Subject: [PATCH 2/1] cache.h: put single NUL at end of struct cache_entry

Since in-memory index entries are allocated individually now, the variable slack at the end meant to provide an eight byte alignment is not needed anymore. Have a single NUL instead. This saves zero to seven bytes for an entry, depending on its filename length.

---

 cache.h |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

index ec0e571..bd106b5 100644
@@ -306,7 +306,7 @@ static inline unsigned int canon_mode(unsigned int mode)
 }
 
 #define flexible_size(STRUCT,len) ((offsetof(struct STRUCT,name) + (len) + 8) & ~7)
-#define cache_entry_size(len) flexible_size(cache_entry,len)
+#define cache_entry_size(len) (offsetof(struct cache_entry,name) + (len) + 1)
 #define ondisk_cache_entry_size(len) flexible_size(ondisk_cache_entry,len)
 #define ondisk_cache_entry_extended_size(len) flexible_size(ondisk_cache_entry_extended,len)
 

1.7.7

Yeah, and code reduction looks nice.

Am 23.10.2011 15:25, schrieb René Scharfe:

And valgrind reports the following errors (git was compiled with -O0 and -g) for master, but not for 1.7.7 nor master plus my ugly patch:

Invalid write of size 1
at 0x4029DE5: memcpy (mc_replace_strmem.c:635)
by 0x81159A5: convert_from_disk (read-cache.c:1247) by 0x8115BE4: read_index_from (read-cache.c:1326)
by 0x81157D7: read_index (read-cache.c:1202)
by 0x813A802: gitmodules_config (submodule.c:105)
by 0x806857E: cmd_status (commit.c:1209)
by 0x804B7F8: run_builtin (git.c:308)
by 0x804B956: handle_internal_command (git.c:466)
by 0x804BA4E: run_argv (git.c:512)
by 0x804BBC0: main (git.c:585)
Address 0x41f2d5e is 2 bytes after a block of size 6,356 alloc'd
at 0x4028876: malloc (vg_replace_malloc.c:236)
by 0x814C070: xmalloc (wrapper.c:35)
by 0x8115B8E: read_index_from (read-cache.c:1315)
by 0x81157D7: read_index (read-cache.c:1202)
by 0x813A802: gitmodules_config (submodule.c:105)
by 0x806857E: cmd_status (commit.c:1209)
by 0x804B7F8: run_builtin (git.c:308)
by 0x804B956: handle_internal_command (git.c:466)
by 0x804BA4E: run_argv (git.c:512)
by 0x804BBC0: main (git.c:585)

Syscall param lstat64(file_name) points to unaddressable byte(s)
at 0x4131D32: __lxstat64@@GLIBC_2.2 (lxstat64.c:48) by 0x81154DE: refresh_index (read-cache.c:1133)
by 0x8068687: cmd_status (commit.c:1226)
by 0x804B7F8: run_builtin (git.c:308)
by 0x804B956: handle_internal_command (git.c:466)
by 0x804BA4E: run_argv (git.c:512)
by 0x804BBC0: main (git.c:585)
Address 0x41f2d5c is 0 bytes after a block of size 6,356 alloc'd
at 0x4028876: malloc (vg_replace_malloc.c:236)
by 0x814C070: xmalloc (wrapper.c:35)
by 0x8115B8E: read_index_from (read-cache.c:1315)
by 0x81157D7: read_index (read-cache.c:1202)
by 0x813A802: gitmodules_config (submodule.c:105)
by 0x806857E: cmd_status (commit.c:1209)
by 0x804B7F8: run_builtin (git.c:308)
by 0x804B956: handle_internal_command (git.c:466)
by 0x804BA4E: run_argv (git.c:512)
by 0x804BBC0: main (git.c:585)

Invalid read of size 1
at 0x402A682: bcmp (mc_replace_strmem.c:679)
by 0x8113D12: df_name_compare (read-cache.c:387)
by 0x81478F9: do_compare_entry (unpack-trees.c:499) by 0x814791B: compare_entry (unpack-trees.c:504)
by 0x8148086: unpack_callback (unpack-trees.c:747) by 0x8145EA5: traverse_trees (tree-walk.c:407)
by 0x81477EB: traverse_trees_recursive (unpack-trees.c:460) by 0x814823D: unpack_callback (unpack-trees.c:809) by 0x8145EA5: traverse_trees (tree-walk.c:407)
by 0x81477EB: traverse_trees_recursive (unpack-trees.c:460) by 0x814823D: unpack_callback (unpack-trees.c:809) by 0x8145EA5: traverse_trees (tree-walk.c:407)
Address 0x41f2d5c is 0 bytes after a block of size 6,356 alloc'd
at 0x4028876: malloc (vg_replace_malloc.c:236)
by 0x814C070: xmalloc (wrapper.c:35)
by 0x8115B8E: read_index_from (read-cache.c:1315)
by 0x81157D7: read_index (read-cache.c:1202)
by 0x813A802: gitmodules_config (submodule.c:105)
by 0x806857E: cmd_status (commit.c:1209)
by 0x804B7F8: run_builtin (git.c:308)
by 0x804B956: handle_internal_command (git.c:466)
by 0x804BA4E: run_argv (git.c:512)
by 0x804BBC0: main (git.c:585)

Invalid read of size 1
at 0x8100E0E: hash_name (name-hash.c:28)
by 0x8100F3D: hash_index_entry (name-hash.c:78)
by 0x8100FD3: lazy_init_name_hash (name-hash.c:96) by 0x8101197: index_name_exists (name-hash.c:159)
by 0x80EADA9: dir_add_name (dir.c:596)
by 0x80EB8CD: read_directory_recursive (dir.c:994) by 0x80EB895: read_directory_recursive (dir.c:983) by 0x80EB895: read_directory_recursive (dir.c:983) by 0x80EB895: read_directory_recursive (dir.c:983) by 0x80EB895: read_directory_recursive (dir.c:983) by 0x80EB895: read_directory_recursive (dir.c:983) by 0x80EBCED: read_directory (dir.c:1101)
Address 0x41f2d5c is 0 bytes after a block of size 6,356 alloc'd
at 0x4028876: malloc (vg_replace_malloc.c:236)
by 0x814C070: xmalloc (wrapper.c:35)
by 0x8115B8E: read_index_from (read-cache.c:1315)
by 0x81157D7: read_index (read-cache.c:1202)
by 0x813A802: gitmodules_config (submodule.c:105)
by 0x806857E: cmd_status (commit.c:1209)
by 0x804B7F8: run_builtin (git.c:308)
by 0x804B956: handle_internal_command (git.c:466)
by 0x804BA4E: run_argv (git.c:512)
by 0x804BBC0: main (git.c:585)

Invalid read of size 1
at 0x402A687: bcmp (mc_replace_strmem.c:679)
by 0x8113DF4: cache_name_compare (read-cache.c:413) by 0x81010F8: same_name (name-hash.c:134)
by 0x81011E0: index_name_exists (name-hash.c:164)
by 0x80EADA9: dir_add_name (dir.c:596)
by 0x80EB8CD: read_directory_recursive (dir.c:994) by 0x80EB895: read_directory_recursive (dir.c:983) by 0x80EB895: read_directory_recursive (dir.c:983) by 0x80EB895: read_directory_recursive (dir.c:983) by 0x80EB895: read_directory_recursive (dir.c:983) by 0x80EB895: read_directory_recursive (dir.c:983) by 0x80EB895: read_directory_recursive (dir.c:983)
Address 0x41f2d5c is 0 bytes after a block of size 6,356 alloc'd
at 0x4028876: malloc (vg_replace_malloc.c:236)
by 0x814C070: xmalloc (wrapper.c:35)
by 0x8115B8E: read_index_from (read-cache.c:1315)
by 0x81157D7: read_index (read-cache.c:1202)
by 0x813A802: gitmodules_config (submodule.c:105)
by 0x806857E: cmd_status (commit.c:1209)
by 0x804B7F8: run_builtin (git.c:308)
by 0x804B956: handle_internal_command (git.c:466)
by 0x804BA4E: run_argv (git.c:512)
by 0x804BBC0: main (git.c:585)