Cygwin can't handle huge packfiles?

Hi,

I'm trying to get Git to manage a 5Gb source tree. Under linux, this
works like a charm. Under cygwin, however, I run in to difficulties.
For example:

$ git-clone sgp-wa/ sgp-wa.clone
fatal: packfile
./objects/pack/pack-56aa013a0234e198467ed37ae5db925764a6ee98.pack
cannot be mapped.
fatal: unexpected EOF
fetch-pack from '/cygdrive/e/Projects/sgp-wa/.git' failed.

To figure out what is happening, I printed the value of errno, which
turns out to be 12 (Cannot allocate memory). I'm not sure how mmap is
implemented in cygwin, but if they allocate memory and load the file
into it, then this error is not surprising, as the pack file in
question is 1.5Gb in size.

I'm not sure how to approach this problem. Any tips would be greatly
appreciated.

Thanks a lot!

Kees-Jan

Hi,

On Mon, 3 Apr 2006, Kees-Jan Dijkzeul wrote:

I'm trying to get Git to manage a 5Gb source tree. Under linux, this
works like a charm. Under cygwin, however, I run in to difficulties.
For example:

$ git-clone sgp-wa/ sgp-wa.clone
fatal: packfile
./objects/pack/pack-56aa013a0234e198467ed37ae5db925764a6ee98.pack
cannot be mapped.
fatal: unexpected EOF
fetch-pack from '/cygdrive/e/Projects/sgp-wa/.git' failed.

To figure out what is happening, I printed the value of errno, which
turns out to be 12 (Cannot allocate memory). I'm not sure how mmap is
implemented in cygwin, but if they allocate memory and load the file
into it, then this error is not surprising, as the pack file in
question is 1.5Gb in size.

The problem is not mmap() on cygwin, but that a fork() has to jump through 
loops to reinstall the open file descriptors on cygwin. If the 
corresponding file was deleted, that fails. Therefore, we work around that 
on cygwin by actually reading the file into memory, *not* mmap()ing it.

Hth,
Dscho

The problem is not mmap() on cygwin, but that a fork() has to jump through
loops to reinstall the open file descriptors on cygwin. If the
corresponding file was deleted, that fails. Therefore, we work around that
on cygwin by actually reading the file into memory, *not* mmap()ing it.

Maybe, but you aren't going to be able to handler much bigger packs
even on *nix.  Unless you go 64-bit, that is.

M.

On Mon, 3 Apr 2006, Johannes Schindelin wrote:

The problem is not mmap() on cygwin, but that a fork() has to jump through 
loops to reinstall the open file descriptors on cygwin. If the 
corresponding file was deleted, that fails. Therefore, we work around that 
on cygwin by actually reading the file into memory, *not* mmap()ing it.

Well, we could actually do a _real_ mmap on pack-files. The pack-files are 
much better mmap'ed - there we don't _want_ them to be removed while we're 
using them. It was the index file etc that was problematic.

Maybe the cygwin fake mmap should be triggered only for the index (and 
possibly the individual objects - if only because there doing a 
malloc+read may actually be faster).

Using malloc+read on pack-files is pretty wasteful, since we usually only 
use a very small part of them (ie if we have a 1.5GB pack-file, it's sad 
to read all of it, when we'd usually actually access just a small small 
fraction of it).

That said, I think git _does_ have problems with large pack-files. We have 
some 32-bit issues etc, and just virtual address space things. So for now, 
it's probably best to limit pack-files to the few-hundred-meg size, and 
create serveral smaller ones rather than one huge one.

		Linus

On Mon, 3 Apr 2006, Linus Torvalds wrote:

That said, I think git _does_ have problems with large pack-files. We have 
some 32-bit issues etc

I should clarify that. git _itself_ shouldn't have any 32-bit issues, but 
the packfile data structure does. The index has 32-bit offsets into 
individual pack-files. 

That's not hugely fundamental, but I didn't expect people to hit it this 
quickly. What kind of project has a 1.5GB pack-file _already_? I hope it's 
fifteen years of history (so that we'll have another fifteen years before 
we'll have to worry about 4GB pack-files ;)

			Linus

On 4/3/06, Kees-Jan Dijkzeul [off-list ref] wrote:

I'm trying to get Git to manage a 5Gb source tree. Under linux, this
works like a charm. Under cygwin, however, I run in to difficulties.
For example:

$ git-clone sgp-wa/ sgp-wa.clone
fatal: packfile
./objects/pack/pack-56aa013a0234e198467ed37ae5db925764a6ee98.pack
cannot be mapped.
fatal: unexpected EOF
fetch-pack from '/cygdrive/e/Projects/sgp-wa/.git' failed.

To figure out what is happening, I printed the value of errno, which
turns out to be 12 (Cannot allocate memory). I'm not sure how mmap is

mmap in git on cygwin does not mmaps anything,
but just reads the whole file in memory.

I'm not sure how to approach this problem. Any tips would be greatly
appreciated.

I ended up hacking gitfakemmap like in the attached patches (sorry for mime).
It's very ugly and unsafe hack, and it's actually exactly the reason why it was
never submitted. Still, it helps me (it speedups revlist, for
instance), and maybe
it'll help you.
It is a really good example what stupid windows restrictions can do to
a program.

The patch is against git as of 3-Apr-2005, ~10 CET

Hi,

On Mon, 3 Apr 2006, Linus Torvalds wrote:

On Mon, 3 Apr 2006, Johannes Schindelin wrote:

quoted

The problem is not mmap() on cygwin, but that a fork() has to jump through 
loops to reinstall the open file descriptors on cygwin. If the 
corresponding file was deleted, that fails. Therefore, we work around that 
on cygwin by actually reading the file into memory, *not* mmap()ing it.

Well, we could actually do a _real_ mmap on pack-files. The pack-files are 
much better mmap'ed - there we don't _want_ them to be removed while we're 
using them. It was the index file etc that was problematic.

Maybe the cygwin fake mmap should be triggered only for the index (and 
possibly the individual objects - if only because there doing a 
malloc+read may actually be faster).

I hit the problem *only* with "git-whatchanged -p". Which means that the 
upcoming we-no-longer-write-temp-files-for-diff version should make that 
gitfakemmap() hack obsolete. (I have not checked whether there are other 
places where a file is mmap()ed and then used by a fork()ed process.)

Ciao,
Dscho

On 4/3/06, Linus Torvalds [off-list ref] wrote:
[...]

That's not hugely fundamental, but I didn't expect people to hit it this
quickly. What kind of project has a 1.5GB pack-file _already_? I hope it's
fifteen years of history (so that we'll have another fifteen years before
we'll have to worry about 4GB pack-files ;)

I'm trying to get Git to manage my companies source tree. We're
writing software for digital TV sets. Anyway, the archive is about 5Gb
in size and contains binaries, zip files, excel sheets meeting minutes
and whatnot. So it doesn't compress very well. The 1.5Gb pack file
hardly contains any history at all (five commits or so). On the flip
side, for now I'll be the only one adding to the archive, so at least
it will not grow that fast ;-)

Anyway, to reconstitute the tree, I need very nearly the entire pack,
so limiting the pack size won't do much good, as git will still try to
allocate a total of 1.5Gb memory (which, unfortunately, isn't there
:-)

Inspired by a patch of Alex Riesen (thanks, Alex), I tried to use the
regular mmap for mapping pack files, only to discover that I compile
without defining "NO_MMAP", so I've been using the stock mmap all
along. So now I'm thinking that the cygwin mmap also does a
malloc-and-read, just like git does with NO_MMAP. So I'll continue to
investigate in that direction.

To be continued...

Groetjes,

Kees-Jan

Hi,

On Wed, 5 Apr 2006, Kees-Jan Dijkzeul wrote:

On 4/3/06, Linus Torvalds [off-list ref] wrote:
[...]

quoted

That's not hugely fundamental, but I didn't expect people to hit it this
quickly. What kind of project has a 1.5GB pack-file _already_? I hope it's
fifteen years of history (so that we'll have another fifteen years before
we'll have to worry about 4GB pack-files ;)

I'm trying to get Git to manage my companies source tree. We're
writing software for digital TV sets. Anyway, the archive is about 5Gb
in size and contains binaries, zip files, excel sheets meeting minutes
and whatnot. So it doesn't compress very well. The 1.5Gb pack file
hardly contains any history at all (five commits or so). On the flip
side, for now I'll be the only one adding to the archive, so at least
it will not grow that fast ;-)

Anyway, to reconstitute the tree, I need very nearly the entire pack,
so limiting the pack size won't do much good, as git will still try to
allocate a total of 1.5Gb memory (which, unfortunately, isn't there
:-)

Inspired by a patch of Alex Riesen (thanks, Alex), I tried to use the
regular mmap for mapping pack files, only to discover that I compile
without defining "NO_MMAP", so I've been using the stock mmap all
along. So now I'm thinking that the cygwin mmap also does a
malloc-and-read, just like git does with NO_MMAP. So I'll continue to
investigate in that direction.

I think cygwin's mmap() is based on the Win32 API equivalent, which could 
mean that it *is* memory mapped, but in a special area (which is smaller 
than 1.5 gigabyte). In this case, it would make sense to limit the pack 
size, thereby having several packs, and mmap() them as they are needed.

Hth,
Dscho

On Wed, Apr 05, 2006 at 04:14:20PM +0200, Johannes Schindelin wrote:

quoted

Inspired by a patch of Alex Riesen (thanks, Alex), I tried to use the
regular mmap for mapping pack files, only to discover that I compile
without defining "NO_MMAP", so I've been using the stock mmap all
along. So now I'm thinking that the cygwin mmap also does a
malloc-and-read, just like git does with NO_MMAP. So I'll continue to
investigate in that direction.

I think cygwin's mmap() is based on the Win32 API equivalent, which could 
mean that it *is* memory mapped, but in a special area (which is smaller 
than 1.5 gigabyte). In this case, it would make sense to limit the pack 
size, thereby having several packs, and mmap() them as they are needed.

Yes, cygwin's mmap uses CreateFileMapping and MapViewOfFile.  IIRC,
Windows might have a 2G limitation lurking under the hood somewhere but
I think that might be tweakable with some registry setting.

cgf

On Wed, Apr 05, 2006 at 05:08:44PM -0400, Christopher Faylor wrote:

On Wed, Apr 05, 2006 at 04:14:20PM +0200, Johannes Schindelin wrote:

quoted

quoted

Inspired by a patch of Alex Riesen (thanks, Alex), I tried to use the
regular mmap for mapping pack files, only to discover that I compile
without defining "NO_MMAP", so I've been using the stock mmap all
along. So now I'm thinking that the cygwin mmap also does a
malloc-and-read, just like git does with NO_MMAP. So I'll continue to
investigate in that direction.

I think cygwin's mmap() is based on the Win32 API equivalent, which could 
mean that it *is* memory mapped, but in a special area (which is smaller 
than 1.5 gigabyte). In this case, it would make sense to limit the pack 
size, thereby having several packs, and mmap() them as they are needed.

Yes, cygwin's mmap uses CreateFileMapping and MapViewOfFile.  IIRC,
Windows might have a 2G limitation lurking under the hood somewhere but
I think that might be tweakable with some registry setting.

Windows places its DLLs criss-cross through the memory space because
every DLL on the system has its own preferred place to be loaded (the
base address). This severely limits the amount of largest contiguous
memory block available, which is needed for one mmap() I think.

Several solutions exist:
  - enlarge the address space with the /3GB boot flag in boot.ini
  - rebase all DLLs with REBASE.EXE (part of platform sdk) .
    Just make them the same and fix them to a low address.
    Problem is rebasing system dlls since those are locked by the system.
  - at start of program before other DLLs are loaded,
    reserve an as large part of the memory as possible with
    VirtualAlloc()

-- 
Rutger Nijlunsing ---------------------------------- eludias ed dse.nl
never attribute to a conspiracy which can be explained by incompetence
----------------------------------------------------------------------

On Thu, Apr 06, 2006 at 01:27:39AM +0200, Rutger Nijlunsing wrote:

On Wed, Apr 05, 2006 at 05:08:44PM -0400, Christopher Faylor wrote:

quoted

On Wed, Apr 05, 2006 at 04:14:20PM +0200, Johannes Schindelin wrote:

quoted

quoted

Inspired by a patch of Alex Riesen (thanks, Alex), I tried to use the
regular mmap for mapping pack files, only to discover that I compile
without defining "NO_MMAP", so I've been using the stock mmap all
along. So now I'm thinking that the cygwin mmap also does a
malloc-and-read, just like git does with NO_MMAP. So I'll continue to
investigate in that direction.

I think cygwin's mmap() is based on the Win32 API equivalent, which could 
mean that it *is* memory mapped, but in a special area (which is smaller 
than 1.5 gigabyte). In this case, it would make sense to limit the pack 
size, thereby having several packs, and mmap() them as they are needed.

Yes, cygwin's mmap uses CreateFileMapping and MapViewOfFile.  IIRC,
Windows might have a 2G limitation lurking under the hood somewhere but
I think that might be tweakable with some registry setting.

Windows places its DLLs criss-cross through the memory space because
every DLL on the system has its own preferred place to be loaded (the
base address). This severely limits the amount of largest contiguous
memory block available, which is needed for one mmap() I think.

Several solutions exist:
 - enlarge the address space with the /3GB boot flag in boot.ini

Thanks.  The 3GB boot flag is what I was trying to remember.

 - rebase all DLLs with REBASE.EXE (part of platform sdk) .
   Just make them the same and fix them to a low address.
   Problem is rebasing system dlls since those are locked by the system.

Cygwin has its own version of rebase and a method for rebasing all of the
dlls in the distribution.  Using that may help squeeze out a little bit
of memory.

 - at start of program before other DLLs are loaded,
   reserve an as large part of the memory as possible with
   VirtualAlloc()

Cygwin actually uses this trick to try to push DLLs into their right
locations after a fork.  It sort of works but sometimes, in a child
proccess, Windows puts "stuff" in locations previously occupied by a
DLL.  I could swear that it does that just to be annoying...

There is a chicken/egg problem here in that Cygwin uses Doug Lea's malloc
and that version of malloc will use mmap when sbrk() fails -- as it is
apt to do when allocating gigabytes of memory.  So, using malloc is
not a way to avoid mmap.

cgf

Linus Torvalds [off-list ref] writes:

On Mon, 3 Apr 2006, Linus Torvalds wrote:

quoted

That said, I think git _does_ have problems with large pack-files. We have 
some 32-bit issues etc

I should clarify that. git _itself_ shouldn't have any 32-bit issues, but 
the packfile data structure does. The index has 32-bit offsets into 
individual pack-files. 

That's not hugely fundamental,...

Linus _does_ understand what he means, but let me clarify and
outline a possible future direction.

 * pack-*.pack file has the following format:

   - The header appears at the beginning and consists of the following:

     4-byte signature
     4-byte version number (network byte order)
     4-byte number of objects contained in the pack (network byte order)

     Observation: we cannot have more than 4G versions ;-) and
     more than 4G objects in a pack.

   - The header is followed by number of object entries, each of
     which looks like this:

     (undeltified representation)
     n-byte type and length (4-bit type, (n-1)*7+4-bit length)
     compressed data

     (deltified representation)
     n-byte type and length (4-bit type, (n-1)*7+4-bit length)
     20-byte base object name
     compressed delta data

     Observation: length of each object is encoded in a variable
     length format and is not constrained to 32-bit or anything.

  - The trailer records 20-byte SHA1 checksum of all of the above.

 * pack-*.idx file has the following format:

  - The header consists of 256 4-byte network byte order
    integers.  N-th entry of this table records the number of
    objects in the corresponding pack, the first byte of whose
    object name are smaller than N.

    Observation: we would need to extend this to an array of
    8-byte integers to go beyond 4G objects per pack, but it is
    not strictly necessary.

  - The header is followed by sorted 28-byte entries, one entry
    per object in the pack.  Each entry is:

    4-byte network byte order integer, recording where the
    object is stored in the packfile as the offset from the
    beginning.

    20-byte object name.

    Observation: we would definitely need to extend this to
    8-byte integer plus 20-byte object name to handle a packfile
    that is larger than 4GB.

  - The file is concluded with a trailer:

    A copy of the 20-byte SHA1 checksum at the end of
    corresponding packfile.

    20-byte SHA1-checksum of all of the above.

This is not fundamental, in that pack idx file is something we
can regenerate from a packfile.  The push/fetch transfer over
git native protocols does not even transfer pack idx file;
instead, the recipient uses git-index-pack to generate pack idx.
git-index-pack would need to be updated to update the necessary
fields to 8-byte integers, without breaking existing packfiles.

The code to read idx file currently has a sanity check logic to
make sure that the size of the idx file is consistent with
24-byte entries (the last entry in the header matches the number
of objects recorded in the pack).  So we could reliably tell
between the current 24-byte version and 28-byte "beyond 4GB"
version, and support both formats at the same time.

Even after we start supporting the 28-byte "beyond 4GB" format,
we can and we should continue writing the current 24-byte
version of pack idx file when the packfile offset can be
expressed with 32-bit.

Having said that, I have to warn that this is not for weak of
heart.  The necessary changes would be somewhat involved.


----------------------------------------------------------------

Pack idx file

	idx
	    +--------------------------------+
	    | fanout[0] = 2                  |-.
	    +--------------------------------+ |
	    | fanout[1]                      | |
	    +--------------------------------+ |
	    | fanout[2]                      | |
	    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
	    | fanout[255]                    | |
	    +--------------------------------+ |
main	    | offset                         | |
index	    | object name 00XXXXXXXXXXXXXXXX | |
table	    +--------------------------------+ | 
	    | offset                         | |
	    | object name 00XXXXXXXXXXXXXXXX | |
	    +--------------------------------+ |
	  .-| offset                         |<+
	  | | object name 01XXXXXXXXXXXXXXXX |
	  | +--------------------------------+
	  | | offset                         |
	  | | object name 01XXXXXXXXXXXXXXXX |
	  | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	  | | offset                         |
	  | | object name FFXXXXXXXXXXXXXXXX |
	  | +--------------------------------+
trailer	  | | packfile checksum              |
	  | +--------------------------------+
	  | | idxfile checksum               |
	  | +--------------------------------+
          .-------.      
                  |
Pack file entry: <+

     packed object header:
	1-byte type (bit 4-6)
	       size0 (bit 0-3)
               end-of-length (bit 7)
        n-byte sizeN (as long as MSB is set, each 7-bit)
		size0..sizeN form 4+7+7+..+7 bit integer, size0
		is the most significant part.
     packed object data:
        If it is not DELTA, then deflated bytes (the size above
		is the size before compression).
	If it is DELTA, then
	  20-byte base object name SHA1 (the size above is the
	  	size of the delta data that follows).
          delta data, deflated.

Junio C Hamano wrote:

 * pack-*.pack file has the following format:

[...]

 * pack-*.idx file has the following format:

[...]
Could you please put the information in parent post somewhere in
Documentation, for example Documentation/technical/pack-format.txt
(perhaps together with putting description of packing heuristic from
http://marc.theaimsgroup.com/?l=git&m=114134881923320 by Jon Loeliger in
Documentation/technical/pack-heuristics.txt even if it doesn't conform to
"serious documentation" standards)?

Thanks in advance
-- 
Jakub Narebski
Warsaw, Poland

On Fri, 7 Apr 2006, Junio C Hamano wrote:

Linus Torvalds [off-list ref] writes:

quoted

On Mon, 3 Apr 2006, Linus Torvalds wrote:

quoted

That said, I think git _does_ have problems with large pack-files. We have 
some 32-bit issues etc

I should clarify that. git _itself_ shouldn't have any 32-bit issues, but 
the packfile data structure does. The index has 32-bit offsets into 
individual pack-files. 

That's not hugely fundamental,...

Linus _does_ understand what he means, but let me clarify and
outline a possible future direction.

[...]

For the record, the delta code also has 32-bit limitations of its own 
presently.  It cannot encode a delta against a buffer which is larger 
than 4GB.

I however made sure the byte 0 could be used as a prefix for future 
encoding extensions, like 64-bit file offsets for example.


Nicolas