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

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

[John Hsing]

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.

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

[Matthieu Moy]

John Hsing <tsyj2007@gmail.com> writes:

> the error:

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

> 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.

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/

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

[John Hsing]

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写到:
> John Hsing <tsyj2007@gmail.com> writes:
>
>> the error:
>
> When does this error occur? is it reproducible on any repository? Which
> OS?
>
>> 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.
>
> 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.
>

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

[René Scharfe]

Am 23.10.2011 10:35, schrieb John Hsing:
> 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!

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(-)

diff --git a/read-cache.c b/read-cache.c
index 01a0e25..b143bd3 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -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;
 }
 

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

[René Scharfe]

Am 23.10.2011 15:25, schrieb René Scharfe:
> Am 23.10.2011 10:35, schrieb John Hsing:
>> 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!
> 
> 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

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)

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

[Jeff King]

On Sun, Oct 23, 2011 at 03:25:17PM +0200, René Scharfe wrote:

> I can reproduce the malloc crash on Ubuntu 11.10 with these simple steps:
> [...]
> 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.

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

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

[René Scharfe]

Am 23.10.2011 18:29, schrieb Jeff King:
> On Sun, Oct 23, 2011 at 03:25:17PM +0200, René Scharfe wrote:
> 
>> I can reproduce the malloc crash on Ubuntu 11.10 with these simple steps:
>> [...]
>> 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.
> 
> 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?

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é

[PATCH] read-cache.c: fix index memory allocation

[René Scharfe]

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

Reported-by: John Hsing <tsyj2007@gmail.com>
Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
---
 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

diff --git a/read-cache.c b/read-cache.c
index 01a0e25..5790a91 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -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
diff --git a/t/t7510-status-index.sh b/t/t7510-status-index.sh
new file mode 100755
index 0000000..bca359d
--- /dev/null
+++ b/t/t7510-status-index.sh
@@ -0,0 +1,50 @@
+#!/bin/sh
+
+test_description='git status with certain file name lengths'
+
+. ./test-lib.sh
+
+files="0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z"
+
+check() {
+	len=$1
+	prefix=$2
+
+	for i in $files
+	do
+		: >$prefix$i
+	done
+
+	test_expect_success "status, filename length $len" "
+		git add $prefix* &&
+		git status
+	"
+	rm $prefix* .git/index
+}
+
+check  1
+check  2 p
+check  3 pr
+check  4 pre
+check  5 pref
+check  6 prefi
+check  7 prefix
+check  8 prefix-
+check  9 prefix-p
+check 10 prefix-pr
+check 11 prefix-pre
+check 12 prefix-pref
+check 13 prefix-prefi
+check 14 prefix-prefix
+check 15 prefix-prefix-
+check 16 prefix-prefix-p
+check 17 prefix-prefix-pr
+check 18 prefix-prefix-pre
+check 19 prefix-prefix-pref
+check 20 prefix-prefix-prefi
+check 21 prefix-prefix-prefix
+check 22 prefix-prefix-prefix-
+check 23 prefix-prefix-prefix-p
+check 24 prefix-prefix-prefix-pr
+
+test_done
-- 
1.7.7

Re: [PATCH] read-cache.c: fix index memory allocation

[Junio C Hamano]

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?

Re: [PATCH] read-cache.c: fix index memory allocation

[René Scharfe]

Am 24.10.2011 09:07, schrieb Junio C Hamano:
> 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?

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

René

Re: [PATCH] read-cache.c: fix index memory allocation

[René Scharfe]

Am 24.10.2011 09:07, schrieb Junio C Hamano:
> 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?

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.

Suggested-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
---
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(-)

diff --git a/cache.h b/cache.h
index be07ec7..ec0e571 100644
--- a/cache.h
+++ b/cache.h
@@ -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;
diff --git a/read-cache.c b/read-cache.c
index 01a0e25..7f75bfa 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -1202,10 +1202,35 @@ int read_index(struct index_state *istate)
 	return read_index_from(istate, get_index_file());
 }
 
-static void convert_from_disk(struct ondisk_cache_entry *ondisk, struct cache_entry *ce)
+static struct cache_entry *create_from_disk(struct ondisk_cache_entry *ondisk)
 {
+	struct cache_entry *ce;
 	size_t len;
 	const char *name;
+	unsigned int flags;
+
+	/* On-disk flags are just 16 bits */
+	flags = ntohs(ondisk->flags);
+	len = flags & CE_NAMEMASK;
+
+	if (flags & CE_EXTENDED) {
+		struct ondisk_cache_entry_extended *ondisk2;
+		int extended_flags;
+		ondisk2 = (struct ondisk_cache_entry_extended *)ondisk;
+		extended_flags = ntohs(ondisk2->flags2) << 16;
+		/* We do not yet understand any bit out of CE_EXTENDED_FLAGS */
+		if (extended_flags & ~CE_EXTENDED_FLAGS)
+			die("Unknown index entry format %08x", extended_flags);
+		flags |= extended_flags;
+		name = ondisk2->name;
+	}
+	else
+		name = ondisk->name;
+
+	if (len == CE_NAMEMASK)
+		len = strlen(name);
+
+	ce = xmalloc(cache_entry_size(len));
 
 	ce->ce_ctime.sec = ntohl(ondisk->ctime.sec);
 	ce->ce_mtime.sec = ntohl(ondisk->mtime.sec);
@@ -1217,48 +1242,16 @@ static void convert_from_disk(struct ondisk_cache_entry *ondisk, struct cache_en
 	ce->ce_uid   = ntohl(ondisk->uid);
 	ce->ce_gid   = ntohl(ondisk->gid);
 	ce->ce_size  = ntohl(ondisk->size);
-	/* On-disk flags are just 16 bits */
-	ce->ce_flags = ntohs(ondisk->flags);
+	ce->ce_flags = flags;
 
 	hashcpy(ce->sha1, ondisk->sha1);
 
-	len = ce->ce_flags & CE_NAMEMASK;
-
-	if (ce->ce_flags & CE_EXTENDED) {
-		struct ondisk_cache_entry_extended *ondisk2;
-		int extended_flags;
-		ondisk2 = (struct ondisk_cache_entry_extended *)ondisk;
-		extended_flags = ntohs(ondisk2->flags2) << 16;
-		/* We do not yet understand any bit out of CE_EXTENDED_FLAGS */
-		if (extended_flags & ~CE_EXTENDED_FLAGS)
-			die("Unknown index entry format %08x", extended_flags);
-		ce->ce_flags |= extended_flags;
-		name = ondisk2->name;
-	}
-	else
-		name = ondisk->name;
-
-	if (len == CE_NAMEMASK)
-		len = strlen(name);
 	/*
 	 * NEEDSWORK: If the original index is crafted, this copy could
 	 * go unchecked.
 	 */
 	memcpy(ce->name, name, len + 1);
-}
-
-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);
-
-	/*
-	 * 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 *);
-	return ondisk_size + entries*per_entry;
+	return ce;
 }
 
 /* remember to discard_cache() before reading a different cache! */
@@ -1266,7 +1259,7 @@ int read_index_from(struct index_state *istate, const char *path)
 {
 	int fd, i;
 	struct stat st;
-	unsigned long src_offset, dst_offset;
+	unsigned long src_offset;
 	struct cache_header *hdr;
 	void *mmap;
 	size_t mmap_size;
@@ -1305,29 +1298,18 @@ int read_index_from(struct index_state *istate, const char *path)
 	istate->cache_nr = ntohl(hdr->hdr_entries);
 	istate->cache_alloc = alloc_nr(istate->cache_nr);
 	istate->cache = xcalloc(istate->cache_alloc, sizeof(struct cache_entry *));
-
-	/*
-	 * The disk format is actually larger than the in-memory format,
-	 * due to space for nsec etc, so even though the in-memory one
-	 * has room for a few  more flags, we can allocate using the same
-	 * index size
-	 */
-	istate->alloc = xmalloc(estimate_cache_size(mmap_size, istate->cache_nr));
 	istate->initialized = 1;
 
 	src_offset = sizeof(*hdr);
-	dst_offset = 0;
 	for (i = 0; i < istate->cache_nr; i++) {
 		struct ondisk_cache_entry *disk_ce;
 		struct cache_entry *ce;
 
 		disk_ce = (struct ondisk_cache_entry *)((char *)mmap + src_offset);
-		ce = (struct cache_entry *)((char *)istate->alloc + dst_offset);
-		convert_from_disk(disk_ce, ce);
+		ce = create_from_disk(disk_ce);
 		set_index_entry(istate, i, ce);
 
 		src_offset += ondisk_ce_size(ce);
-		dst_offset += ce_size(ce);
 	}
 	istate->timestamp.sec = st.st_mtime;
 	istate->timestamp.nsec = ST_MTIME_NSEC(st);
@@ -1361,11 +1343,15 @@ unmap:
 
 int is_index_unborn(struct index_state *istate)
 {
-	return (!istate->cache_nr && !istate->alloc && !istate->timestamp.sec);
+	return (!istate->cache_nr && !istate->timestamp.sec);
 }
 
 int discard_index(struct index_state *istate)
 {
+	int i;
+
+	for (i = 0; i < istate->cache_nr; i++)
+		free(istate->cache[i]);
 	resolve_undo_clear_index(istate);
 	istate->cache_nr = 0;
 	istate->cache_changed = 0;
@@ -1374,8 +1360,6 @@ int discard_index(struct index_state *istate)
 	istate->name_hash_initialized = 0;
 	free_hash(&istate->name_hash);
 	cache_tree_free(&(istate->cache_tree));
-	free(istate->alloc);
-	istate->alloc = NULL;
 	istate->initialized = 0;
 
 	/* no need to throw away allocated active_cache */
-- 
1.7.7

Re: [PATCH] read-cache.c: fix index memory allocation

[Nguyen Thai Ngoc Duy]

On Mon, Oct 24, 2011 at 11:59:14PM +0200, René Scharfe wrote:
> Am 24.10.2011 09:07, schrieb Junio C Hamano:
> > 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?
> 
> Something like this (applies to master)?  Very basic testing didn't show
> any slowdown of git status in the Linux repo.

"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< --
diff --git a/Makefile b/Makefile
index 3139c19..c8b47bc 100644
--- a/Makefile
+++ b/Makefile
@@ -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))
 
diff --git a/test-read-cache.c b/test-read-cache.c
index e69de29..1ad80a0 100644
--- a/test-read-cache.c
+++ b/test-read-cache.c
@@ -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< --

Re: [PATCH] read-cache.c: fix index memory allocation

[Nguyen Thai Ngoc Duy]

On Tue, Oct 25, 2011 at 10:34 AM, Nguyen Thai Ngoc Duy
<pclouds@gmail.com> wrote:
> "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 :-)

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

Re: [PATCH] read-cache.c: fix index memory allocation

[René Scharfe]

Am 25.10.2011 02:01, schrieb Nguyen Thai Ngoc Duy:
> On Tue, Oct 25, 2011 at 10:34 AM, Nguyen Thai Ngoc Duy
> <pclouds@gmail.com> wrote:
>> "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 :-)
> 
> 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.

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.

Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
---

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

diff --git a/cache.h b/cache.h
index ec0e571..bd106b5 100644
--- a/cache.h
+++ b/cache.h
@@ -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

Re: [PATCH] read-cache.c: fix index memory allocation

[Junio C Hamano]

René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:

> 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

Yeah, and code reduction looks nice.

Re: [PATCH] read-cache.c: fix index memory allocation

[Junio C Hamano]

René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:

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

> diff --git a/t/t7510-status-index.sh b/t/t7510-status-index.sh
> new file mode 100755
> index 0000000..bca359d
> --- /dev/null
> +++ b/t/t7510-status-index.sh
> @@ -0,0 +1,50 @@

Hmm, I cannot seem to make this fail this test without the fix on my
Fedora 14 i686 VM when applied to v1.7.6.4 (estimation code originates
cf55870 back in v1.7.6.1 days), but it does break on 'master'.

By the way, I'll move this to 7511.

Also would a patch like this help?

-- >8 --
Subject: [PATCH] read_index(): die on estimation error

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 read-cache.c |    7 ++++++-
 1 files changed, 6 insertions(+), 1 deletions(-)

diff --git a/read-cache.c b/read-cache.c
index 0a64103..2926615 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -1270,6 +1270,7 @@ int read_index_from(struct index_state *istate, const char *path)
 	int fd, i;
 	struct stat st;
 	unsigned long src_offset, dst_offset;
+	size_t bulk_alloc_size;
 	struct cache_header *hdr;
 	void *mmap;
 	size_t mmap_size;
@@ -1315,7 +1316,8 @@ int read_index_from(struct index_state *istate, const char *path)
 	 * has room for a few  more flags, we can allocate using the same
 	 * index size
 	 */
-	istate->alloc = xmalloc(estimate_cache_size(mmap_size, istate->cache_nr));
+	bulk_alloc_size = estimate_cache_size(mmap_size, istate->cache_nr);
+	istate->alloc = xmalloc(bulk_alloc_size);
 	istate->initialized = 1;
 
 	src_offset = sizeof(*hdr);
@@ -1331,7 +1333,9 @@ int read_index_from(struct index_state *istate, const char *path)
 
 		src_offset += ondisk_ce_size(ce);
 		dst_offset += ce_size(ce);
+		if (bulk_alloc_size <= dst_offset)
+			die("cache size estimation error");
 	}
 	istate->timestamp.sec = st.st_mtime;
 	istate->timestamp.nsec = ST_MTIME_NSEC(st);
 
-- 
1.7.7.1.504.gcc718

Re: [PATCH] read-cache.c: fix index memory allocation

[René Scharfe]

Am 24.10.2011 09:28, schrieb Junio C Hamano:
> René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:
> 
>>  t/t7510-status-index.sh |   50 +++++++++++++++++++++++++++++++++++++++++++++++
>>  2 files changed, 53 insertions(+), 3 deletions(-)
>>  create mode 100755 t/t7510-status-index.sh
> 
>> diff --git a/t/t7510-status-index.sh b/t/t7510-status-index.sh
>> new file mode 100755
>> index 0000000..bca359d
>> --- /dev/null
>> +++ b/t/t7510-status-index.sh
>> @@ -0,0 +1,50 @@
> 
> Hmm, I cannot seem to make this fail this test without the fix on my
> Fedora 14 i686 VM when applied to v1.7.6.4 (estimation code originates
> cf55870 back in v1.7.6.1 days), but it does break on 'master'.

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.

> By the way, I'll move this to 7511.
> 
> Also would a patch like this help?

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.

> -- >8 --
> Subject: [PATCH] read_index(): die on estimation error
> 
> Signed-off-by: Junio C Hamano <gitster@pobox.com>
> ---
>  read-cache.c |    7 ++++++-
>  1 files changed, 6 insertions(+), 1 deletions(-)
> 
> diff --git a/read-cache.c b/read-cache.c
> index 0a64103..2926615 100644
> --- a/read-cache.c
> +++ b/read-cache.c
> @@ -1270,6 +1270,7 @@ int read_index_from(struct index_state *istate, const char *path)
>  	int fd, i;
>  	struct stat st;
>  	unsigned long src_offset, dst_offset;
> +	size_t bulk_alloc_size;
>  	struct cache_header *hdr;
>  	void *mmap;
>  	size_t mmap_size;
> @@ -1315,7 +1316,8 @@ int read_index_from(struct index_state *istate, const char *path)
>  	 * has room for a few  more flags, we can allocate using the same
>  	 * index size
>  	 */
> -	istate->alloc = xmalloc(estimate_cache_size(mmap_size, istate->cache_nr));
> +	bulk_alloc_size = estimate_cache_size(mmap_size, istate->cache_nr);
> +	istate->alloc = xmalloc(bulk_alloc_size);
>  	istate->initialized = 1;
>  
>  	src_offset = sizeof(*hdr);
> @@ -1331,7 +1333,9 @@ int read_index_from(struct index_state *istate, const char *path)
>  
>  		src_offset += ondisk_ce_size(ce);
>  		dst_offset += ce_size(ce);
> +		if (bulk_alloc_size <= dst_offset)
> +			die("cache size estimation error");
>  	}
>  	istate->timestamp.sec = st.st_mtime;
>  	istate->timestamp.nsec = ST_MTIME_NSEC(st);
>