{"thread":{"id":"1022","subject":"kernel.org and GIT tree rebuilding","startedAt":"2005-06-25T04:20:09Z","lastAt":"2005-07-05T13:34:48Z","messageCount":38,"participants":["David S. Miller","Jeff Garzik","Junio C Hamano","Linus Torvalds","Chris Mason","Nicolas Pitre","Daniel Barkalow","Marco Costalba"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"5250","messageId":"20050624.212009.92584730.davem@davemloft.net","threadId":"1022","inReplyTo":null,"subject":"kernel.org and GIT tree rebuilding","fromName":"David S. Miller","fromEmail":"davem@davemloft.net","sentAt":"2005-06-25T04:20:09Z","receivedAt":"2005-06-25T04:20:09Z","isPatch":false,"sender":{"key":"davem@davemloft.net","avatar":null},"body":"\nTo get a clean history to push to Linus, I typically blow\naway my trees and make fresh ones to stick patches into\nwhich I want to merge.\n\nThat mostly works fine here on my local systems, but I know this\nbrings the master.org mirroring system to it's knees.  So what is the\ngenerally condoned way to do stuff like this in a more friendly way?\n\nShould I:\n\n1) Do a git pull from Linus's tree once he takes my changes, then\n   ask GIT to prune the tree?  How do I do that and how does it work?\n\n2) Should I use .git/object/ database symlinking?\n\n   Are there any scripts out there which do this automatically?\n   Something as simple to run as \"git-pull-script\" and it takes\n   care of using links when possible on a local filesystem.\n\nIt takes sometimes an hour for my tree updates on master.kernel.org\nto propagate to rsync.kernel.org so I can ask Linus to pull.\nThat's crazy.\n"},{"id":"5251","messageId":"42BCE026.8050405@pobox.com","threadId":"1022","inReplyTo":"20050624.212009.92584730.davem@davemloft.net","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Jeff Garzik","fromEmail":"jgarzik@pobox.com","sentAt":"2005-06-25T04:40:06Z","receivedAt":"2005-06-25T04:40:06Z","isPatch":false,"sender":{"key":"jgarzik@pobox.com","avatar":null},"body":"David S. Miller wrote:\n> To get a clean history to push to Linus, I typically blow\n> away my trees and make fresh ones to stick patches into\n> which I want to merge.\n> \n> That mostly works fine here on my local systems, but I know this\n> brings the master.org mirroring system to it's knees.  So what is the\n> generally condoned way to do stuff like this in a more friendly way?\n> \n> Should I:\n> \n> 1) Do a git pull from Linus's tree once he takes my changes, then\n>    ask GIT to prune the tree?  How do I do that and how does it work?\n\n> It takes sometimes an hour for my tree updates on master.kernel.org\n> to propagate to rsync.kernel.org so I can ask Linus to pull.\n> That's crazy.\n\nUnfortunately you cannot fix this by changing your actions.  This is the \ncumulative effect of all the git kernel trees on kernel.org.  It now \ntakes over an hour for my non-git changes to propagate from master to \nthe mirrors, as well.\n\nThis is all due to the rsync sweeps, which have to scan metric tons of \ninodes and dentries.  Orders of magnitude over the pre-git days.\n\nftpadmin@kernel.org folks are supposedly working on an inotify-based \nsystem, and an improved rsync application.  No ETA or details.\n\nAs an aside, cold-cache, git really punishes my disks.  Ted T'so noted \nthat it really drains laptop batteries, too.\n\n\n> 2) Should I use .git/object/ database symlinking?\n> \n>    Are there any scripts out there which do this automatically?\n>    Something as simple to run as \"git-pull-script\" and it takes\n>    care of using links when possible on a local filesystem.\n\nOn both kernel.org and locally, I use 'cp -al' to duplicate the initial \n.git/objects directory, and then rsync (->kernel.org) or git-pull-script \n(<-kernel.org) to update it after that.\n\nThat definitely helps.\n\nMaybe somebody needs to script a relink cron job for kernel.org?\n\n\tJeff\n\n\n"},{"id":"5252","messageId":"7vslz758ok.fsf@assigned-by-dhcp.cox.net","threadId":"1022","inReplyTo":"20050624.212009.92584730.davem@davemloft.net","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-06-25T05:04:11Z","receivedAt":"2005-06-25T05:04:11Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"DSM\" == David S Miller <davem@davemloft.net> writes:\n\nDSM> To get a clean history to push to Linus, I typically blow\nDSM> away my trees and make fresh ones to stick patches into\nDSM> which I want to merge.\n\nDSM> Should I:\n\nDSM> 1) Do a git pull from Linus's tree once he takes my changes, then\nDSM>    ask GIT to prune the tree?  How do I do that and how does it work?\n\nDSM> 2) Should I use .git/object/ database symlinking?\n\nDSM>    Are there any scripts out there which do this automatically?\nDSM>    Something as simple to run as \"git-pull-script\" and it takes\nDSM>    care of using links when possible on a local filesystem.\n\ngit-pull-script internally uses git-fetch-script which knows how\nto do the local tree using hardlinks.  Presumably, the following\nworkflow would work:\n\n (1) You hack away in your private tree, while you keep a \"to be\n     published\" clean tree, both on your local machine.\n\n (2) Do a GIT pull, merge in your private tree, to come up with\n     a clean set of changes in your private tree.  This is the\n     tree you \"typically blow away\".  Reordering the commits to\n     come up with a clean history since you last pulled from\n     Linus would also happen in this tree.\n\n (3) Once you have a commit that you want to publish (i.e. the\n     commit chain between that commit and the point you last\n     pulled from Linus is the \"clean history to push to Linus\"),\n     you go to your \"to be published\" clean tree, and run\n     git-fetch-script to fetch the commit you want to publish\n     from your private tree.  When you give an absolute path as\n     the \"remote repo\", git-local-pull with linking behaviour is\n     used by git-fetch-script; otherwise rsync backend is used\n     so you end up polluted object database.  This way you copy\n     only the clean stuff from your private tree.  Your HEAD in\n     this tree should be set to the commit you wanted to\n     publish.  Running git-prune would be nicer but if your\n     history is truly clean it should not be necessary.\n\n (4) Garbage collecting with git-prune your private tree is your\n     business.\n\n"},{"id":"5253","messageId":"Pine.LNX.4.58.0506242208210.11175@ppc970.osdl.org","threadId":"1022","inReplyTo":"42BCE026.8050405@pobox.com","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-25T05:23:05Z","receivedAt":"2005-06-25T05:23:05Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 25 Jun 2005, Jeff Garzik wrote:\n> \n> This is all due to the rsync sweeps, which have to scan metric tons of \n> inodes and dentries.  Orders of magnitude over the pre-git days.\n\nWell, the real solution is to use a git-aware protocol, not rsync.\n\nrsync is wonderful for prototyping, and I wanted to make the database \nrsync'able for that reason, but it clearly doesn't scale.\n\nI think I'll make a \"pack\"/\"unpack\" pair that just packs all the necessary\nobjects between two commits. Then you can basically sync the object file \nby doing\n\n\tgit-pack OLD..NEW | ssh other-end git-unpack\n\nand you'd basically be done. It looks pretty easy to do, too..\n\n\t\t\tLinus\n"},{"id":"5254","messageId":"42BCF02B.5090706@pobox.com","threadId":"1022","inReplyTo":"Pine.LNX.4.58.0506242208210.11175@ppc970.osdl.org","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Jeff Garzik","fromEmail":"jgarzik@pobox.com","sentAt":"2005-06-25T05:48:27Z","receivedAt":"2005-06-25T05:48:27Z","isPatch":false,"sender":{"key":"jgarzik@pobox.com","avatar":null},"body":"Linus Torvalds wrote:\n> \n> On Sat, 25 Jun 2005, Jeff Garzik wrote:\n> \n>>This is all due to the rsync sweeps, which have to scan metric tons of \n>>inodes and dentries.  Orders of magnitude over the pre-git days.\n> \n> \n> Well, the real solution is to use a git-aware protocol, not rsync.\n> \n> rsync is wonderful for prototyping, and I wanted to make the database \n> rsync'able for that reason, but it clearly doesn't scale.\n> \n> I think I'll make a \"pack\"/\"unpack\" pair that just packs all the necessary\n> objects between two commits. Then you can basically sync the object file \n> by doing\n> \n> \tgit-pack OLD..NEW | ssh other-end git-unpack\n> \n> and you'd basically be done. It looks pretty easy to do, too..\n\n\nThe problem is kernel.org mirroring, not individual pushes and pulls, \nreally.\n\nWould git-pack be the best solution for mirroring a bunch of git trees?\n\n\tJeff\n\n\n"},{"id":"5255","messageId":"Pine.LNX.4.58.0506242257450.11175@ppc970.osdl.org","threadId":"1022","inReplyTo":"42BCF02B.5090706@pobox.com","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-25T06:16:12Z","receivedAt":"2005-06-25T06:16:12Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 25 Jun 2005, Jeff Garzik wrote:\n> \n> The problem is kernel.org mirroring, not individual pushes and pulls, \n> really.\n> \n> Would git-pack be the best solution for mirroring a bunch of git trees?\n\nNo guarantees, but here's a rough plan:\n\n - I just committed a fairly trivial change to add a \"--objects\" flag to \n   git-rev-list, which allows you to basically say \"I want to see the \n   difference not just in commit ID's, but also trees and blobs\"\n\n   What does that mean? It means that in a mirroring schenario, you can, \n   for each git tree, do:\n\n\t(a) On the slave:\n\t\tcat .git/refs/*/* | sort | uniq > slave-ref-list\n\n\t(b) On the master:\n\t\tcat .git/refs/*/* | sort | uniq > master-ref-list\n\n\t(c) On the master:\n\n\t\tcmp $master-ref-list $slave-ref-list && exit 1\n\t\tlist=$(cat master-ref-list)\n\t\tfor i in $(cat slave-ref-list)\n\t\tdo\n\t\t\tlist=$list ^$i\n\t\tdone\n\t\tgit-rev-list --objects $list\n\n   and now that \"git-rev-list\" will list every object that needs to be \n   copied from the master to the slave. No need to read huge directories \n   etc, you get the list computed for you.\n\nyeah, it clearly needs some refining to be useful, but I think you can\nkind of see how it would work.\n\nNow, the secondary advantage of this is that once you don't use rsync as\nthe mirroring method, you can now change the filesystem object database\nlayout. In particular, the packing thing that Chris Mason was working on\nat some point suddenly becomes a lot more viable.\n\n(In fact, more than that. You can make a single packed blob for all\n\"historical\" objects, and that also gives you an efficient archive format\n- if you're not required to have the full filesystem layout, you could\nhave a much more efficient packing that you basically do once a week or\nsomething, so that you only keep the last week in the regular \"one file\nper object\" format).\n\n\t\tLinus\n"},{"id":"5277","messageId":"Pine.LNX.4.58.0506260905200.19755@ppc970.osdl.org","threadId":"1022","inReplyTo":"Pine.LNX.4.58.0506242257450.11175@ppc970.osdl.org","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-26T16:41:02Z","receivedAt":"2005-06-26T16:41:02Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 24 Jun 2005, Linus Torvalds wrote:\n> \n> yeah, it clearly needs some refining to be useful, but I think you can\n> kind of see how it would work.\n\nOk, here's how it works.\n\n - Pick a starting commit (or a hundred)\n\n - Pick an ending commit (or a hundred)\n\n - generate the list of objects in between them\n\n\tgit-rev-list --object end ^start > object-list\n\n - Pack that list of objects into an \"object pack\":\n\n\tgit-pack-objects out < object-list\n\n   (This actually generates two files: \"out.idx\" is the index file, \n   \"out.pack\" is the data file, but I'll make it concatenate the two at \n   some point)\n\n - move the pack-files over somewhere else\n\n - unpack them\n\n\tgit-unpack-objects out\n\nand you're done.\n\nNow, the reason I use \"pack\" and \"unpack\" instead of just \"tar\" to\ntransport the objects is that this allows me to do a fairly efficient\npacking. I wanted these pack-files to be independent (ie they do _not_\ndepend on any objects outside of the pack-file), but within the objects\ndescribed in the pack I cna do delta-compression.\n\nNow, that doesn't much help for small updates (where the objects are just \nunrelated and have no deltas), but it helps increasingly for big ones. The \nbiggest one obviously being the whole path from the start to the HEAD..\n\nFor example, the \"du -sh .git/objects\" for the git project itself is 17MB \nfor me, and I can do:\n\n\ttorvalds@ppc970:~/git> du -sh .git/objects \n\t17M     .git/objects\n\n\ttorvalds@ppc970:~/git> time git-rev-list --objects HEAD | git-pack-objects out\n\tPacking 3656 objects\n\n\treal    0m3.779s\n\tuser    0m3.169s\n\tsys     0m0.602s\n\n\ttorvalds@ppc970:~/git> ls -lh out.*\n\t-rw-rw-r--  1 torvalds torvalds  87K Jun 26 09:12 out.idx\n\t-rw-rw-r--  1 torvalds torvalds 2.0M Jun 26 09:12 out.pack\n\nie it packs down to a nice 2MB pack-file with a small index. Move that\nover to somewhere else, and unpack it, and you'll get all the regular\nobjects (it doesn't move tags and refs over, you'll have to do that\noutside of the packing).\n\nNow, you can trade off some packing time to get a better pack:\n\n\ttorvalds@ppc970:~/git> time git-rev-list --objects HEAD | git-pack-objects --window=100 out\n\tPacking 3656 objects\n\t\n\treal    0m11.953s\n\tuser    0m11.294s\n\tsys     0m0.663s\n\n\ttorvalds@ppc970:~/git> ls -lh out.*\n\t-rw-rw-r--  1 torvalds torvalds  87K Jun 26 09:14 out.idx\n\t-rw-rw-r--  1 torvalds torvalds 1.6M Jun 26 09:14 out.pack\n\nand if you want to allow deep delta chains (the default delta depth\nlimiting is 10), you can get even better results:\n\n\ttorvalds@ppc970:~/git> time git-rev-list --objects HEAD | git-pack-objects --window=100 --depth=100 out\n\tPacking 3656 objects\n\t\n\treal    0m12.374s\n\tuser    0m11.704s\n\tsys     0m0.659s\n\n\ttorvalds@ppc970:~/git> ls -lh out.*\n\t-rw-rw-r--  1 torvalds torvalds  87K Jun 26 09:16 out.idx\n\t-rw-rw-r--  1 torvalds torvalds 1.3M Jun 26 09:16 out.pack\n\nbut then unpacking will slightly heavier.\n\n(Doing the same for the kernel is obviously much more expensive just\nbecause the kernel is so much bigger. A big delta discovery window like\n100 takes about fifteen minutes to pack on my machine, but gets the\ncurrent kernel archive down to 70MB or so. That's ok for a monthly \"pack\nall the objects\" to keep size requirements down, but you clearly don't\nwant to do this all the time ;).\n\nNow, perhaps the more interesting part is that I also designed the pack\nformat so that it should be a good \"history\" format, not just a way to\nmove objects from one place to the other. Ie if you worry about diskspace,\nyou can pack everything up to the now into one big pack, and then remove\nthe original objects.\n\nDon't do that yet, btw - I haven't actually written the code to read stuff\nout of packs if we don't find it in the object directory yet, but the\nlayout is such that it should be straightforward and pretty efficient (but\nthere a deep delta chain obviously _will_ cause a performance hit).\n\nI actually like this approach better than having delta-objects in the\nfilesystem. Partly because the pack-file is self-contained, partly because\nit also solves the fs blocking issue, yet is still efficient to look up\nthe results without having hardlinks etc to duplicate objects virtually.  \nAnd when you do the packing by hand as an \"archival\" mechanism, it also\ndoesn't have any of the downsides that Chris' packing approach had.\n\nNico? Chris? Interested in giving it a look? It's kind of a combination of \nyour things, generalized and then made to have fast lookup with the index.\n\nFast lookup doesn't matter for a normal unpack, of course, and if I just\nalways wanted to unpack all the objects (ie just an object transfer\nmechanism) I'd have made the index be a toposort of the objects. But\nbecause I wanted to be able to use it as an archival format, I needed it\nto be \"random-access\" by object name. So the index is in fact a binary\ntree (well, sorted array, so the lookup degenerates into a binary search)\nwith a top-level index splitting up the contents based on the first byte\n(the same way the filesystem layout does).\n\n\t\tLinus\n"},{"id":"5280","messageId":"7vzmtdq7wy.fsf@assigned-by-dhcp.cox.net","threadId":"1022","inReplyTo":"Pine.LNX.4.58.0506260905200.19755@ppc970.osdl.org","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-06-26T18:39:41Z","receivedAt":"2005-06-26T18:39:41Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds <torvalds@osdl.org> writes:\n\nLT> I actually like this approach better than having delta-objects in the\nLT> filesystem. Partly because the pack-file is self-contained, partly because\nLT> it also solves the fs blocking issue, yet is still efficient to look up\nLT> the results without having hardlinks etc to duplicate objects virtually.  \nLT> And when you do the packing by hand as an \"archival\" mechanism, it also\nLT> doesn't have any of the downsides that Chris' packing approach had.\n\nAfter analyzing what is involved in making packed GIT integrated\ninto read_sha1_file() [*1*], I agree 100% with the above.  I\nmean no disrespect to what Nico has done (and I myself have done\nsome code to work with Nico's deltified objects when I did diffs\nand pull fixes), but it would help the code very much if we do\nnot have to worry about \"delta\" objects in GIT_OBJECT_DIRECTORY.\n\nMy preference is to do things in this order:\n\n (0) concatenate pack and idx files;\n\n (1) teach read_sha1_file() to read from packed GIT;\n\n (2) teach fsck-cache about packed GIT;\n\n (3) have people with deltified repositories convert them back\n     to undeltified (I think git-pack-objects would barf on such\n     repository);\n\n (4) drop \"delta\" objects from GIT_OBJECT_DIRECTORY; this means\n     that git-deltafy-script and git-mkdelta have to go.\n\n (5) tell git-*-pull about packed GIT;\n\n\n[Footnotes]\n\n*1* Here is the analysis I did last night, still assuming that\nwe would support \"delta\" objects in GIT_OBJECT_DIRECTORY.  The\n\"trickier\" map_sha1_file() users almost all involve \"delta\"\nobjects, and that is why I prefer dropping them.\n\n - Enhance GIT_ALTERNATE_OBJECT_DIRECTORIES mechanism so that\n   its component can be either a directory or a packed file.\n\n - sha1_file.c::find_sha1_file() has to be enhanced to express\n   not just path (in the current \"individual object file\"\n   case) but a pointer to a structure that describes a packed\n   file in the GIT_ALTERNATE_OBJECT_DIRECTORIES list with the\n   offset for the entry.\n\n - The change necessary to sha1_file.c::has_sha1_file() is\n   minimum.  find_sha1_file() updated along the above lines\n   would say if the thing exists or not anyway, so it can just\n   return true/false as it currently does pretty easily.\n\n - sha1_file.c::read_sha1_file() would be the primary piece to\n   unpack from the packed representation.\n\n - sha1_file.c::map_sha1_file() is trickier.  It has handful\n   callers outside sha1_file.c for valid reasons, so we will\n   need to audit the callers and have them fall back on\n   read_sha1_file() as appropriate.  Here is the result of my\n   first pass:\n\n   - (easy) sha1_delta_base() is used only when an object is\n     delitified, and if true get to the base object.  We can\n     just tell the caller our object is not deltified when it\n     resides in a packed file.\n\n   - (easy) sha1_file_size() is used by diffcore to measure the\n     expanded blob size.  Although the implementation obviously\n     has to be different, it would be trivial to find the size\n     if the object resides in a packed file.\n\n   - (easy) pack-objects.c::check_object() uses map_sha1_file() so that\n     it can unpack small to get the type of the object.  We\n     should be able to introduce a new interface (say,\n     sha1_file.c::sha1_object_type()) for doing this sort of\n     stuff.\n\n   - (harder) mkdelta.c::get_buffer(), object.c::parse_object()\n     and delta.c::process_delta() are trickier, because they\n     want to treat \"delta\" as a raw object (otherwise we would\n     have just done sha1_read_file() instead of\n     map/unpack_sha1_file pair).\n\n   - (harder) ssh-push.c::serve_object() also wants raw\n     representation to directly ship to the other end.\n"},{"id":"5282","messageId":"Pine.LNX.4.58.0506261206170.19755@ppc970.osdl.org","threadId":"1022","inReplyTo":"7vzmtdq7wy.fsf@assigned-by-dhcp.cox.net","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-26T19:19:07Z","receivedAt":"2005-06-26T19:19:07Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 26 Jun 2005, Junio C Hamano wrote:\n> \n> My preference is to do things in this order:\n> \n>  (0) concatenate pack and idx files;\n\nActually, I was originally planning to do that, but now that I have \nthought about what read_sha1_file() would actually do, I think it's more \nefficient to leave the index as a separate file.\n\nIn particular, what you'd normally do is that if you can't look up the\nfile in the regular object directory, you start going through the pack\nfiles. You can do it by having GIT_ALTERNATE_OBJECT_DIRECTORIES point to a\npack file, but I actually would prefer the notion of just adding a\n\n\t.git/objects/pack\n\nsubdirectory, and having object lookup just automatically open and map all \nindex files in that subdirectory.\n\nAnd the thing is, you really just want to map the index files, the data\nfiles can be so big that you can't afford to map them (ie a really big\nproject might have several pack-files a gig each or something like that).\n\nAnd the most efficient way to map just the index file is to keep it \nseparate, because then the \"stat()\" will just get the information \ndirectly, and you then just mmap that. \n\nThe alternative is to first read the index of the index (to figure out how\nbig the index is), and then map the rest. But that just seems a lot\nmessier than just mapping the index file directly.\n\nAnd when creating these things, we do need to create the data file (which \ncan be big enough that it doesn't fit in memory) first, so we have to have \na separate file for it, we can't just stream it out to stdout.\n\nNow, when _sending_ the pack-files, linearizing them is easy: you just \nsend the index first, and the data file immediately afterwards. The index \ntells how big it is, so there's no need to even add any markers: you can \ndo something like 'git-send-script' with something simple like\n\n\tgit-rev-list ... | git-pack-file tmp-pack &&\n\tcat tmp-pack.idx tmp-pack.data | ssh other git-receive-script\n\nSo let's just keep the index/data files separate.\n\n\t\tLinus\n"},{"id":"5285","messageId":"7vll4wq4va.fsf@assigned-by-dhcp.cox.net","threadId":"1022","inReplyTo":"Pine.LNX.4.58.0506261206170.19755@ppc970.osdl.org","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-06-26T19:45:29Z","receivedAt":"2005-06-26T19:45:29Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds <torvalds@osdl.org> writes:\n\nLT> On Sun, 26 Jun 2005, Junio C Hamano wrote:\n>> \n>> My preference is to do things in this order:\n>> \n>> (0) concatenate pack and idx files;\n\nLT> So let's just keep the index/data files separate.\n\nFair enough.  Having thought about it a bit more, if people\nagree, I think it would make more sense to rip out \"delta\"\nobject support first before doing read_sha1_file() and friends\nthat uses .git/objects/pack.\n\nMy \"preferred order\" now look like this:\n\n (1) have people with deltified repositories convert them back\n     to undeltified (I think git-pack-objects would barf on such\n     repository);\n\n (2) drop \"delta\" objects from GIT_OBJECT_DIRECTORY; this means\n     that git-deltafy-script and git-mkdelta have to go.\n\n (3) teach read_sha1_file() to read from packed GIT in\n     .git/objects/pack;\n\n (4) teach fsck-cache about packed GIT;\n\n (5) tell git-*-pull about packed GIT;\n"},{"id":"5288","messageId":"200506261652.59373.mason@suse.com","threadId":"1022","inReplyTo":"Pine.LNX.4.58.0506260905200.19755@ppc970.osdl.org","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-06-26T20:52:57Z","receivedAt":"2005-06-26T20:52:57Z","isPatch":false,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Sunday 26 June 2005 12:41, Linus Torvalds wrote:\n> On Fri, 24 Jun 2005, Linus Torvalds wrote:\n> > yeah, it clearly needs some refining to be useful, but I think you can\n> > kind of see how it would work.\n>\n> Ok, here's how it works.\n>\n>  - Pick a starting commit (or a hundred)\n>\n>  - Pick an ending commit (or a hundred)\n>\n>  - generate the list of objects in between them\n>\n> \tgit-rev-list --object end ^start > object-list\n>\n>  - Pack that list of objects into an \"object pack\":\n>\n> \tgit-pack-objects out < object-list\n\nWithout having read the code, the big thing that hurt performance in my early \npacked file work was compressing the whole packed file instead of individual \nsub-objects.  It takes more room to compress each object, but when I \ncompressed the whole thing read performance was quite bad.\n\n-chris\n"},{"id":"5289","messageId":"200506261703.16862.mason@suse.com","threadId":"1022","inReplyTo":"200506261652.59373.mason@suse.com","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-06-26T21:03:16Z","receivedAt":"2005-06-26T21:03:16Z","isPatch":false,"sender":{"key":"mason@suse.com","avatar":null},"body":"On Sunday 26 June 2005 16:52, Chris Mason wrote:\n> >\n> > \tgit-rev-list --object end ^start > object-list\n> >\n> >  - Pack that list of objects into an \"object pack\":\n> >\n> > \tgit-pack-objects out < object-list\n>\n> Without having read the code, the big thing that hurt performance in my\n> early packed file work was compressing the whole packed file instead of\n> individual sub-objects.  It takes more room to compress each object, but\n> when I compressed the whole thing read performance was quite bad.\n\nSorry, fat fingered the send key...\n\nThe hard links were the biggest problem with my packed file patches, I think \nthe dynamic lookup in a separate packed file index is the best way to go.\n\n-chris\n"},{"id":"5290","messageId":"Pine.LNX.4.58.0506261359370.19755@ppc970.osdl.org","threadId":"1022","inReplyTo":"200506261652.59373.mason@suse.com","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-26T21:40:59Z","receivedAt":"2005-06-26T21:40:59Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 26 Jun 2005, Chris Mason wrote:\n> \n> Without having read the code, the big thing that hurt performance in my early \n> packed file work was compressing the whole packed file instead of individual \n> sub-objects.  It takes more room to compress each object, but when I \n> compressed the whole thing read performance was quite bad.\n\nSince I wanted random-access, compressing the whole thing just wasn't an \noption.\n\nBesides, the big space savings come from finding deltas, which is \nobviously also a compression, just at a higher level. The biggest problem \nthere is to find a guess of objects to try to delta against, and right now \nthat part is pretty stupid and could possibly be improved (it just sorts \nobjects by size and tries to delta against \"close\" objects).\n\nTo generate a better sort _would_ actually be pretty close to doing a \nglobal compression (it really does boil down to the same thing: finding \nbig sub-sequences, except it's in a \"fragmented\" space), but one issue is \nthat I don't want to read in the whole data set in one go, so it would \nhave to be based on some rolling hash or something. Davide pointed to \nrzip, and a variation of that (which knows about object boundaries) might \nwork.\n\n(You can also sort by filename, if you want to try. I don't track\nfilenames at all there and it's actually non-trivial to do, so that would\nrequire some new and pretty nasty code, but it's possible in _theory_ at\nleast.)\n\nAnyway, that's all potential improvement for generating better packing,\nand it should certainly be possible without changing the format - just\ngenerate a better initial sort, in otder to find more deltas (or rather,\nfind them faster by using a smaller window size).\n\nSo the stupid sort I have now does actually work, but exactly because it's\nso stupid it wants a big window for best packing (because there might be a\nlot of objects that aren't interesting), which in turn is quite expensive.\nSo a better sort would make a smaller window more effective.\n\n[ Some numbers: a window of 10 objects is the default, and packs the\n  current kernel down to 77MB in 2m21s. A window of 20 objects improves\n  that packing to 71MB, but makes the packing time go up to 3m36s for me.  \n  And a window of 100 gets us down to 62M but takes 11m54s.\n\n  A window of 200 (with a delta depth of 200 too - likely _way_ too deep\n  for normal use) gives you a 59M pack, but takes 20m59s, so there's\n  definitely a point of diminishing returns.\n\n  This is all for the current HEAD, which takes up 264M the \"traditional\" \n  git way and takes 141M without any deltas, just packed tightly with no \n  filesystem blocking.\n\n  Now, as you can notice that's actually a slightly sub-linear increase in\n  time, because as we find a delta, we will only accept smaller deltas in\n  the future, so we can often stop comparing even before we've reached the\n  maximum window size, and so effort is slightly less than linear because \n  there's effectively a constant component to part of it.\n\n  Also, the good news is that you probably don't want to generate one \n  humungous pack archive anyway, but you're likely better off doing a new \n  incremental pack every few months. So we'll never have the situation \n  that creating a pack gets increasingly more costly, since at some point \n  you just say \"ok, I created a perfect pack for the first 4 months of\n  development, I'll now do subsequent packs on top of that instead\".\n\n  The other good news is that a pack is also a natural boundary for fsck \n  (as in \"ok, I found that object in a pack, so I won't bother going\n  deeper in the reachability chain\"), so if you start packing your\n  repository, fsck will only have to worry about the objects that are\n  unpacked. That makes them work really naturally for archiving, ie this \n  all means that you can avoid a lot of overhead by packing your history\n  every once in a while, with it all being entirely transparent.\n\n  In other words, if you just pack every month, you can basically \n  guarantee that fsck costs etc never really go up, and your diskspace \n  also goes up only very slowly. The packed format is quite efficient in \n  many ways, but it is totally immutable (ie you can't add anything to an \n  archive - a pack stays the way it always was, and if you want to pack \n  more you have to either re-do the pack or just create a new one) ]\n\n\t\tLinus\n"},{"id":"5293","messageId":"Pine.LNX.4.58.0506261528020.19755@ppc970.osdl.org","threadId":"1022","inReplyTo":"Pine.LNX.4.58.0506261359370.19755@ppc970.osdl.org","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-26T22:34:13Z","receivedAt":"2005-06-26T22:34:13Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 26 Jun 2005, Linus Torvalds wrote:\n> \n> (You can also sort by filename, if you want to try. I don't track\n> filenames at all there and it's actually non-trivial to do, so that would\n> require some new and pretty nasty code, but it's possible in _theory_ at\n> least.)\n\nHeh. It's actually very easy if you don't take the \"name\" too seriously, \nand you just pick some random one, namely the first one that was used to \nreach the entry.\n\nThen, you might sort the objects on a hash based on the name, and get \ntons of cheap deltas close-by.\n\nIt is _uglee_, but hey, it's a heuristic, and it happens to work pretty \nwell. It brought the kernel pack down to 59M even with just a small window \nof 10.\n\nThanks to Davide for making me think about this hack, although he talked \nabout something much more proper (and harder) than this quick and \nugly heuristic ;)\n\nThe main change is that \"git-rev-list --objects\" has been changed to show\nthe name the object was reached through.\n\n\t\t\tLinus\n"},{"id":"5326","messageId":"7vpsu7x94t.fsf@assigned-by-dhcp.cox.net","threadId":"1022","inReplyTo":"7v64vzyqyw.fsf_-_@assigned-by-dhcp.cox.net","subject":"[PATCH] Obtain sha1_file_info() for deltified pack entry properly.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-06-28T06:56:02Z","receivedAt":"2005-06-28T06:56:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I will be sending these three patches:\n\n    [PATCH 1/3] Obtain sha1_file_info() for deltified pack entry properly.\n    [PATCH 2/3] git-cat-file: use sha1_object_info() on '-t'.\n    [PATCH 3/3] git-cat-file: '-s' to find out object size.\n\nThe first one is slightly different from what I sent earlier to\nyou privately.  If you have already applied it, please apply the\n4-liner alternate patch attached to this message on top of it\nfor the fix included in the one in this series (and drop the\nfirst one, obviously).\n\nThe second and third patches fell out as a bonus while I was\ndebugging the sha1_file_info().  Especially the third one is in\n\"because we can do it so cheaply now\", not \"because I need to\nhave that feature\" category, and I do not mind too much if you\ndrop it, but I suspect somebody may find it useful.\n\nThe \"4-liner alternate patch\" follows.\n\n------------\nAdd missing use_packed_git() call.\n\nThe function sha1_object_info() was using packed GIT file\nwithout making sure it is mapped, which resulted in\nsegfaulting.\n\nWe would need to introduce unuse_packed_git() call and do proper\nuse counting to figure out when it is safe to unmap, but\ncurrently we do not unmap packed file yet.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\n sha1_file.c |    4 ++++\n 1 files changed, 4 insertions(+), 0 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -675,6 +675,10 @@ static int packed_object_info(struct pac\n \toffset = entry->offset;\n \tif (p->pack_size - 5 < offset)\n \t\tdie(\"object offset outside of pack file\");\n+\n+\tif (use_packed_git(p))\n+\t\tdie(\"cannot map packed file\");\n+\n \tpack = p->pack_base + offset;\n \tsize = (pack[1] << 24) + (pack[2] << 16) + (pack[3] << 8) + pack[4];\n \tleft = p->pack_size - offset - 5;\n------------------------------------------------\n"},{"id":"5328","messageId":"7vk6kfx91b.fsf@assigned-by-dhcp.cox.net","threadId":"1022","inReplyTo":"7vpsu7x94t.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Obtain sha1_file_info() for deltified pack entry properly.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-06-28T06:58:08Z","receivedAt":"2005-06-28T06:58:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"[PATCH 1/3] Obtain sha1_file_info() for deltified pack entry properly.\n\nThe initial one was not doing enough to figure things out\nwithout uncompressing too much.  It also fixes a potential\nsegfault resulting from missing use_packed_git() call.\n\nWe would need to introduce unuse_packed_git() call and do proper\nuse counting to figure out when it is safe to unmap, but\ncurrently we do not unmap packed file yet.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\n sha1_file.c |   73 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++---\n 1 files changed, 69 insertions(+), 4 deletions(-)\n\nd2f58b4aef500835489f30ac5df7985bc21e3c24\ndiff --git a/sha1_file.c b/sha1_file.c\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -601,9 +601,70 @@ void * unpack_sha1_file(void *map, unsig\n \treturn unpack_sha1_rest(&stream, hdr, *size);\n }\n \n-/* Returns 0 on fast-path success, returns 1 on deltified\n- * and need to unpack to see info.\n- */\n+static int packed_delta_info(unsigned char *base_sha1,\n+\t\t\t     unsigned long delta_size,\n+\t\t\t     unsigned long left,\n+\t\t\t     char *type,\n+\t\t\t     unsigned long *sizep)\n+{\n+\tunsigned char *data;\n+\tunsigned char delta_head[64];\n+\tint i;\n+\tunsigned char cmd;\n+\tunsigned long data_size, result_size, base_size, verify_base_size;\n+\tz_stream stream;\n+\tint st;\n+\n+\tif (left < 20)\n+\t\tdie(\"truncated pack file\");\n+\tif (sha1_object_info(base_sha1, type, &base_size))\n+\t\tdie(\"cannot get info for delta-pack base\");\n+\n+\tdata = base_sha1 + 20;\n+\tdata_size = left - 20;\n+\n+\tmemset(&stream, 0, sizeof(stream));\n+\n+\tstream.next_in = data;\n+\tstream.avail_in = data_size;\n+\tstream.next_out = delta_head;\n+\tstream.avail_out = sizeof(delta_head);\n+\n+\tinflateInit(&stream);\n+\tst = inflate(&stream, Z_FINISH);\n+\tinflateEnd(&stream);\n+\tif ((st != Z_STREAM_END) && stream.total_out != sizeof(delta_head))\n+\t\tdie(\"delta data unpack-initial failed\");\n+\n+\t/* Examine the initial part of the delta to figure out\n+\t * the result size.  Verify the base size while we are at it.\n+\t */\n+\tdata = delta_head;\n+\tverify_base_size = i = 0;\n+\tcmd = *data++;\n+\twhile (cmd) {\n+\t\tif (cmd & 1)\n+\t\t\tverify_base_size |= *data++ << i;\n+\t\ti += 8;\n+\t\tcmd >>= 1;\n+\t}\n+\n+\t/* Read the result size */\n+\tresult_size = i = 0;\n+\tcmd = *data++;\n+\twhile (cmd) {\n+\t\tif (cmd & 1)\n+\t\t\tresult_size |= *data++ << i;\n+\t\ti += 8;\n+\t\tcmd >>= 1;\n+\t}\n+\tif (verify_base_size != base_size)\n+\t\tdie(\"delta base size mismatch\");\n+\n+\t*sizep = result_size;\n+\treturn 0;\n+}\n+\n static int packed_object_info(struct pack_entry *entry,\n \t\t\t      char *type, unsigned long *sizep)\n {\n@@ -614,12 +675,16 @@ static int packed_object_info(struct pac\n \toffset = entry->offset;\n \tif (p->pack_size - 5 < offset)\n \t\tdie(\"object offset outside of pack file\");\n+\n+\tif (use_packed_git(p))\n+\t\tdie(\"cannot map packed file\");\n+\n \tpack = p->pack_base + offset;\n \tsize = (pack[1] << 24) + (pack[2] << 16) + (pack[3] << 8) + pack[4];\n \tleft = p->pack_size - offset - 5;\n \tswitch (*pack) {\n \tcase 'D':\n-\t\treturn 1;\n+\t\treturn packed_delta_info(pack+5, size, left, type, sizep);\n \t\tbreak;\n \tcase 'C':\n \t\tstrcpy(type, \"commit\");\n------------\n"},{"id":"5327","messageId":"7vfyv3x90a.fsf_-_@assigned-by-dhcp.cox.net","threadId":"1022","inReplyTo":"7vpsu7x94t.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH 2/3] git-cat-file: use sha1_object_info() on '-t'.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-06-28T06:58:45Z","receivedAt":"2005-06-28T06:58:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"When trying to find out the type of the object, there is no need\nto uncompress the whole object.  Just use sha1_object_info().\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\n cat-file.c |   10 ++++------\n 1 files changed, 4 insertions(+), 6 deletions(-)\n\nfcfdd3d74d359af32dd30aa9f4fe373cebb3e232\ndiff --git a/cat-file.c b/cat-file.c\n--- a/cat-file.c\n+++ b/cat-file.c\n@@ -16,13 +16,11 @@ int main(int argc, char **argv)\n \t\tusage(\"git-cat-file [-t | tagname] <sha1>\");\n \n \tif (!strcmp(\"-t\", argv[1])) {\n-\t\tbuf = read_sha1_file(sha1, type, &size);\n-\t\tif (buf) {\n-\t\t\tbuf = type;\n-\t\t\tsize = strlen(type);\n-\t\t\ttype[size] = '\\n';\n-\t\t\tsize++;\n+\t\tif (!sha1_object_info(sha1, type, &size)) {\n+\t\t\tprintf(\"%s\\n\", type);\n+\t\t\treturn 0;\n \t\t}\n+\t\tbuf = NULL;\n \t} else {\n \t\tbuf = read_object_with_reference(sha1, argv[1], &size, NULL);\n \t}\n------------\n"},{"id":"5329","messageId":"7v8y0vx8zd.fsf_-_@assigned-by-dhcp.cox.net","threadId":"1022","inReplyTo":"7vpsu7x94t.fsf@assigned-by-dhcp.cox.net","subject":"[PATCH 3/3] git-cat-file: '-s' to find out object size.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-06-28T06:59:18Z","receivedAt":"2005-06-28T06:59:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"We use sha1_object_info() now, and getting size is also trivial.\n\nI admit that this is more of \"because we can\" not \"because I see\nimmediate need for it\", though.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\n Documentation/git-cat-file.txt |   12 +++++++++---\n cat-file.c                     |   13 ++++++++++---\n 2 files changed, 19 insertions(+), 6 deletions(-)\n\ndcf2fc7609509985d4411fb13c6956bcf3c8560f\ndiff --git a/Documentation/git-cat-file.txt b/Documentation/git-cat-file.txt\n--- a/Documentation/git-cat-file.txt\n+++ b/Documentation/git-cat-file.txt\n@@ -9,12 +9,13 @@ git-cat-file - Provide content or type i\n \n SYNOPSIS\n --------\n-'git-cat-file' (-t | <type>) <object>\n+'git-cat-file' (-t | -s | <type>) <object>\n \n DESCRIPTION\n -----------\n Provides content or type of objects in the repository. The type\n-is required if '-t' is not being used to find the object type.\n+is required unless '-t' is used to find the object type,\n+or '-s' is used to find the object size.\n \n OPTIONS\n -------\n@@ -25,6 +26,10 @@ OPTIONS\n \tInstead of the content, show the object type identified by\n \t<object>.\n \n+-s::\n+\tInstead of the content, show the object size identified by\n+\t<object>.\n+\n <type>::\n \tTypically this matches the real type of <object> but asking\n \tfor a type that can trivially dereferenced from the given\n@@ -35,7 +40,8 @@ OPTIONS\n \n OUTPUT\n ------\n-If '-t' is specified, one of the <type>.\n+If '-t' is specified, one of the <type>.  If '-s' is specified,\n+the size of the <object> in bytes.\n \n Otherwise the raw (though uncompressed) contents of the <object> will\n be returned.\ndiff --git a/cat-file.c b/cat-file.c\n--- a/cat-file.c\n+++ b/cat-file.c\n@@ -13,11 +13,18 @@ int main(int argc, char **argv)\n \tunsigned long size;\n \n \tif (argc != 3 || get_sha1(argv[2], sha1))\n-\t\tusage(\"git-cat-file [-t | tagname] <sha1>\");\n+\t\tusage(\"git-cat-file [-t | -s | tagname] <sha1>\");\n \n-\tif (!strcmp(\"-t\", argv[1])) {\n+\tif (!strcmp(\"-t\", argv[1]) || !strcmp(\"-s\", argv[1])) {\n \t\tif (!sha1_object_info(sha1, type, &size)) {\n-\t\t\tprintf(\"%s\\n\", type);\n+\t\t\tswitch (argv[1][1]) {\n+\t\t\tcase 't':\n+\t\t\t\tprintf(\"%s\\n\", type);\n+\t\t\t\tbreak;\n+\t\t\tcase 's':\n+\t\t\t\tprintf(\"%lu\\n\", size);\n+\t\t\t\tbreak;\n+\t\t\t}\n \t\t\treturn 0;\n \t\t}\n \t\tbuf = NULL;\n------------\n"},{"id":"5354","messageId":"Pine.LNX.4.63.0506281351150.1667@localhost.localdomain","threadId":"1022","inReplyTo":"Pine.LNX.4.58.0506260905200.19755@ppc970.osdl.org","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-06-28T18:06:16Z","receivedAt":"2005-06-28T18:06:16Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 26 Jun 2005, Linus Torvalds wrote:\n\n> On Fri, 24 Jun 2005, Linus Torvalds wrote:\n> > \n> > yeah, it clearly needs some refining to be useful, but I think you can\n> > kind of see how it would work.\n> \n> Ok, here's how it works.\n> \n[...]\n> \n> Nico? Chris? Interested in giving it a look? It's kind of a combination of \n> your things, generalized and then made to have fast lookup with the index.\n\nWow !\n\nLook away for a few days and when you look back your own stuff has been \nyanked out!\n\nBut actually I like this packing thing.  Certainly much nicer to work \nwith and also more useful.  And, since the pack file has its own \nchecksum  it is possible to use that pack format (without the index \n(which can be recreated from the pack file alone anyway) for network \ntransfer.\n\nHere's one improvement to the pack format, breaking it early so it won't \naffect anyone at this point: compressed object header.  Instead of the \nfixed 5 byte header, this patch convert it to a variable size granted \nmost object are small enough to save on the storage of the significant \nsize bytes which will be zero and packing the non-zero byte position \nwith the object type.\n\nThis can save up to 2% or 21KB on the test I \nperformed with the git repository.\n\ndiff --git a/pack-objects.c b/pack-objects.c\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -7,7 +7,7 @@\n static const char pack_usage[] = \"git-pack-objects [--window=N] [--depth=N] base-name < object-list\";\n \n enum object_type {\n-\tOBJ_NONE,\n+\tOBJ_NONE = 0,\n \tOBJ_COMMIT,\n \tOBJ_TREE,\n \tOBJ_BLOB,\n@@ -55,7 +55,7 @@ static unsigned long write_object(struct\n \tchar type[10];\n \tvoid *buf = read_sha1_file(entry->sha1, type, &size);\n \tchar header[25];\n-\tunsigned hdrlen, datalen;\n+\tunsigned hdrlen, datalen, bit;\n \n \tif (!buf)\n \t\tdie(\"unable to read %s\", sha1_to_hex(entry->sha1));\n@@ -63,21 +63,33 @@ static unsigned long write_object(struct\n \t\tdie(\"object %s size inconsistency (%lu vs %lu)\", sha1_to_hex(entry->sha1), size, entry->size);\n \n \t/*\n-\t * The object header is a byte of 'type' followed by four bytes of\n-\t * length, except for deltas that has the 20 bytes of delta sha\n-\t * instead.\n+\t * The object header is one byte which low 4 bits represent the\n+\t * object type, the 4 upper bits indicates which of the following\n+\t * bytes are used to build the object size.  For delta objects the\n+\t * sha1 of the reference object is also appended.\n \t */\n-\theader[0] = \".CTB\"[entry->type];\n-\thdrlen = 5;\n+\theader[0] = entry->type;\n \tif (entry->delta) {\n-\t\theader[0] = 'D';\n-\t\tmemcpy(header+5, entry->delta, 20);\n+\t\theader[0] = OBJ_DELTA;\n \t\tbuf = delta_against(buf, size, entry);\n \t\tsize = entry->delta_size;\n-\t\thdrlen = 25;\n \t}\n-\tdatalen = htonl(size);\n-\tmemcpy(header+1, &datalen, 4);\n+\thdrlen = 1;\n+\tbit = (1 << 4);\n+\tdatalen = size;\n+\tdo {\n+\t\tif (datalen & 0xff) {\n+\t\t\theader[0] |= bit;\n+\t\t\theader[hdrlen++] = datalen;\n+\t\t}\n+\t\tbit <<= 1;\n+\t\tdatalen >>= 8;\n+\t} while (datalen);\n+\tif (entry->delta) {\n+\t\tmemcpy(header+hdrlen, entry->delta, 20);\n+\t\thdrlen += 20;\n+\t}\n+\n \tsha1write(f, header, hdrlen);\n \tdatalen = sha1write_compressed(f, buf, size);\n \tfree(buf);\ndiff --git a/unpack-objects.c b/unpack-objects.c\n--- a/unpack-objects.c\n+++ b/unpack-objects.c\n@@ -12,6 +12,16 @@ struct pack_entry {\n \tunsigned char sha1[20];\n };\n \n+enum object_type {\n+\tOBJ_NONE = 0,\n+\tOBJ_COMMIT,\n+\tOBJ_TREE,\n+\tOBJ_BLOB,\n+\tOBJ_DELTA\n+};\n+\n+static char *type_s[] = { NULL, \"commit\", \"tree\", \"blob\", \"delta\" };\n+\n static void *pack_base;\n static unsigned long pack_size;\n static void *index_base;\n@@ -92,7 +102,7 @@ static int check_index(void)\n }\n \n static int unpack_non_delta_entry(struct pack_entry *entry,\n-\t\t\t\t  int kind,\n+\t\t\t\t  char *type,\n \t\t\t\t  unsigned char *data,\n \t\t\t\t  unsigned long size,\n \t\t\t\t  unsigned long left)\n@@ -101,9 +111,8 @@ static int unpack_non_delta_entry(struct\n \tz_stream stream;\n \tchar *buffer;\n \tunsigned char sha1[20];\n-\tchar *type_s;\n \n-\tprintf(\"%s %c %lu\\n\", sha1_to_hex(entry->sha1), kind, size);\n+\tprintf(\"%s %s %lu\\n\", sha1_to_hex(entry->sha1), type, size);\n \tif (dry_run)\n \t\treturn 0;\n \n@@ -120,18 +129,12 @@ static int unpack_non_delta_entry(struct\n \tinflateEnd(&stream);\n \tif ((st != Z_STREAM_END) || stream.total_out != size)\n \t\tgoto err_finish;\n-\tswitch (kind) {\n-\tcase 'C': type_s = \"commit\"; break;\n-\tcase 'T': type_s = \"tree\"; break;\n-\tcase 'B': type_s = \"blob\"; break;\n-\tdefault: goto err_finish;\n-\t}\n-\tif (write_sha1_file(buffer, size, type_s, sha1) < 0)\n+\tif (write_sha1_file(buffer, size, type, sha1) < 0)\n \t\tdie(\"failed to write %s (%s)\",\n-\t\t    sha1_to_hex(entry->sha1), type_s);\n-\tprintf(\"%s %s\\n\", sha1_to_hex(sha1), type_s);\n+\t\t    sha1_to_hex(entry->sha1), type);\n+\tprintf(\"%s %s\\n\", sha1_to_hex(sha1), type);\n \tif (memcmp(sha1, entry->sha1, 20))\n-\t\tdie(\"resulting %s have wrong SHA1\", type_s);\n+\t\tdie(\"resulting %s have wrong SHA1\", type);\n \n  finish:\n \tst = 0;\n@@ -183,15 +186,13 @@ static int unpack_delta_entry(struct pac\n \t\tdie(\"truncated pack file\");\n \tdata = base_sha1 + 20;\n \tdata_size = left - 20;\n-\tprintf(\"%s D %lu\", sha1_to_hex(entry->sha1), delta_size);\n+\tprintf(\"%s delta %lu\", sha1_to_hex(entry->sha1), delta_size);\n \tprintf(\" %s\\n\", sha1_to_hex(base_sha1));\n \n \tif (dry_run)\n \t\treturn 0;\n \n-\t/* pack+5 is the base sha1, unless we have it, we need to\n-\t * unpack it first.\n-\t */\n+\t/* unless we have the base sha1, we need to unpack it first. */\n \tif (!has_sha1_file(base_sha1)) {\n \t\tstruct pack_entry *base;\n \t\tif (!find_pack_entry(base_sha1, &base))\n@@ -236,7 +237,9 @@ static int unpack_delta_entry(struct pac\n static void unpack_entry(struct pack_entry *entry)\n {\n \tunsigned long offset, size, left;\n-\tunsigned char *pack;\n+\tunsigned char *pack, sizebits;\n+\tenum object_type type;\n+\tint i;\n \n \t/* Have we done this one already due to deltas based on it? */\n \tif (lookup_object(entry->sha1))\n@@ -246,14 +249,25 @@ static void unpack_entry(struct pack_ent\n \tif (offset > pack_size - 5)\n \t\tdie(\"object offset outside of pack file\");\n \tpack = pack_base + offset;\n-\tsize = (pack[1] << 24) + (pack[2] << 16) + (pack[3] << 8) + pack[4];\n-\tleft = pack_size - offset - 5;\n-\tswitch (*pack) {\n-\tcase 'C': case 'T': case 'B':\n-\t\tunpack_non_delta_entry(entry, *pack, pack+5, size, left);\n+\tsizebits = *pack++;\n+\ttype = sizebits & 0x0f;\n+\tsizebits >>= 4;\n+\ti = size = 0;\n+\twhile (sizebits) {\n+\t\tif (sizebits & 1)\n+\t\t\tsize |= *pack++ << i;\n+\t\ti += 8;\n+\t\tsizebits >>= 1;\n+\t}\n+\tleft = pack_size - ((void *)pack - pack_base);\n+\tswitch (type) {\n+\t\tcase OBJ_COMMIT:\n+\t\tcase OBJ_TREE:\n+\t\tcase OBJ_BLOB:\n+\t\tunpack_non_delta_entry(entry, type_s[type], pack, size, left);\n \t\tbreak;\n-\tcase 'D':\n-\t\tunpack_delta_entry(entry, pack+5, size, left);\n+\tcase OBJ_DELTA:\n+\t\tunpack_delta_entry(entry, pack, size, left);\n \t\tbreak;\n \tdefault:\n \t\tdie(\"corrupted pack file\");\n"},{"id":"5359","messageId":"Pine.LNX.4.58.0506281201510.19755@ppc970.osdl.org","threadId":"1022","inReplyTo":"Pine.LNX.4.63.0506281351150.1667@localhost.localdomain","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-28T19:28:36Z","receivedAt":"2005-06-28T19:28:36Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 28 Jun 2005, Nicolas Pitre wrote:\n> \n> Here's one improvement to the pack format, breaking it early so it won't \n> affect anyone at this point: compressed object header.  Instead of the \n> fixed 5 byte header, this patch convert it to a variable size granted \n> most object are small enough to save on the storage of the significant \n> size bytes which will be zero and packing the non-zero byte position \n> with the object type.\n\nOk, this is against an older version and doesn't have that \"read_sha1\" \nthing, but yes, something like this would work.\n\nI'd prefer the encoding to be a bit different, though: make the size be\nencoded in seven bits per byte, with the high bit meaning \"more to come\". \nWe can use four bits from the \"type\" byte for the initial value, making \nlengths 0-15 be free.\n\n\tunsigned long size;\n\tunsigned char c;\n\n\tc = *pack++;\n\ttype = \n\tsize = c & 15;\n\ttype = (c >> 4) & 7;\n\twhile (c & 0x80) {\n\t\tc = *pack++;\n\t\tsize = (size << 7) + (pack & 0x7f);\n\t}\n\nor something. That's even denser.\n\nHowever, I also end up wanting to add a \"global header\" to the pack-file, \nthat contains at least the number of objects packed. We may not know how \nbig the pack-file will be, but we'll at least know how many objects it \nhas before we start writing it.\n\n\t\tLinus\n"},{"id":"5369","messageId":"Pine.LNX.4.63.0506281655140.1667@localhost.localdomain","threadId":"1022","inReplyTo":"Pine.LNX.4.58.0506281201510.19755@ppc970.osdl.org","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-06-28T21:08:48Z","receivedAt":"2005-06-28T21:08:48Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 28 Jun 2005, Linus Torvalds wrote:\n\n> \n> \n> On Tue, 28 Jun 2005, Nicolas Pitre wrote:\n> > \n> > Here's one improvement to the pack format, breaking it early so it won't \n> > affect anyone at this point: compressed object header.  Instead of the \n> > fixed 5 byte header, this patch convert it to a variable size granted \n> > most object are small enough to save on the storage of the significant \n> > size bytes which will be zero and packing the non-zero byte position \n> > with the object type.\n> \n> Ok, this is against an older version and doesn't have that \"read_sha1\" \n> thing, but yes, something like this would work.\n> \n> I'd prefer the encoding to be a bit different, though: make the size be\n> encoded in seven bits per byte, with the high bit meaning \"more to come\". \n> We can use four bits from the \"type\" byte for the initial value, making \n> lengths 0-15 be free.\n> \n> \tunsigned long size;\n> \tunsigned char c;\n> \n> \tc = *pack++;\n> \ttype = \n> \tsize = c & 15;\n> \ttype = (c >> 4) & 7;\n> \twhile (c & 0x80) {\n> \t\tc = *pack++;\n> \t\tsize = (size << 7) + (pack & 0x7f);\n> \t}\n> \n> or something. That's even denser.\n\nOK.  New patch below.\n\n> However, I also end up wanting to add a \"global header\" to the pack-file, \n> that contains at least the number of objects packed. We may not know how \n> big the pack-file will be, but we'll at least know how many objects it \n> has before we start writing it.\n\nProbably a version signature would be a good thing too.\n\n=====\n\nThis patch adds compressed object header.  Instead of the fixed 5 byte \nheader, this patch convert it to a variable size granted most object are \nsmall enough to save on the storage of the size's most significant bytes \nwhich are zero, even ffolding bits with the object type.  Objects up to \n2047 bytes in size will have a header of only 2 bytes.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\ndiff --git a/pack-objects.c b/pack-objects.c\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -3,24 +3,17 @@\n #include \"object.h\"\n #include \"delta.h\"\n #include \"csum-file.h\"\n+#include \"pack.h\"\n \n static const char pack_usage[] = \"git-pack-objects [--window=N] [--depth=N] {--stdout | base-name} < object-list\";\n \n-/*\n- * The object type is a single-character shorthand:\n- *  - 'C' for \"Commit\"\n- *  - 'T' for \"Tree\"\n- *  - 'B' for \"Blob\"\n- *  - 'G' for \"taG\"\n- *  - 'D' for \"Delta\"\n- */\n struct object_entry {\n \tunsigned char sha1[20];\n \tunsigned long size;\n \tunsigned long offset;\n \tunsigned int depth;\n \tunsigned int hash;\n-\tunsigned char type;\n+\tpacked_obj_type type;\n \tunsigned long delta_size;\n \tstruct object_entry *delta;\n };\n@@ -63,21 +56,30 @@ static unsigned long write_object(struct\n \t\tdie(\"object %s size inconsistency (%lu vs %lu)\", sha1_to_hex(entry->sha1), size, entry->size);\n \n \t/*\n-\t * The object header is a byte of 'type' followed by four bytes of\n-\t * length, except for deltas that has the 20 bytes of delta sha\n-\t * instead.\n+\t * The object header first byte has its low 4 bits representing the\n+\t * object type, the 4 upper bits indicating which of the following\n+\t * bytes are used to build the object size.  For delta objects the\n+\t * sha1 of the reference object is also appended.\n \t */\n \theader[0] = entry->type;\n-\thdrlen = 5;\n \tif (entry->delta) {\n-\t\theader[0] = 'D';\n-\t\tmemcpy(header+5, entry->delta, 20);\n+\t\theader[0] = PACKED_DELTA;\n \t\tbuf = delta_against(buf, size, entry);\n \t\tsize = entry->delta_size;\n-\t\thdrlen = 25;\n \t}\n-\tdatalen = htonl(size);\n-\tmemcpy(header+1, &datalen, 4);\n+\theader[0] |= size << 3;\n+\thdrlen = 1;\n+\tdatalen = size >> 4;\n+\twhile (datalen) {\n+\t\theader[hdrlen - 1] |= 0x80;\n+\t\theader[hdrlen++] = datalen;\n+\t\tdatalen >>= 7;\n+\t}\n+\tif (entry->delta) {\n+\t\tmemcpy(header+hdrlen, entry->delta, 20);\n+\t\thdrlen += 20;\n+\t}\n+\n \tsha1write(f, header, hdrlen);\n \tdatalen = sha1write_compressed(f, buf, size);\n \tfree(buf);\n@@ -168,13 +170,13 @@ static void check_object(struct object_e\n \n \tif (!sha1_object_info(entry->sha1, type, &entry->size)) {\n \t\tif (!strcmp(type, \"commit\")) {\n-\t\t\tentry->type = 'C';\n+\t\t\tentry->type = PACKED_COMMIT;\n \t\t} else if (!strcmp(type, \"tree\")) {\n-\t\t\tentry->type = 'T';\n+\t\t\tentry->type = PACKED_TREE;\n \t\t} else if (!strcmp(type, \"blob\")) {\n-\t\t\tentry->type = 'B';\n+\t\t\tentry->type = PACKED_BLOB;\n \t\t} else if (!strcmp(type, \"tag\")) {\n-\t\t\tentry->type = 'G';\n+\t\t\tentry->type = PACKED_TAG;\n \t\t} else\n \t\t\tdie(\"unable to pack object %s of type %s\",\n \t\t\t    sha1_to_hex(entry->sha1), type);\ndiff --git a/pack.h b/pack.h\nnew file mode 100644\n--- /dev/null\n+++ b/pack.h\n@@ -0,0 +1,19 @@\n+#ifndef PACK_H\n+#define PACK_H\n+\n+/*\n+ * The packed object type is stored in the low 3 bits of a byte.\n+ * The type value 0 is a reserved prefix if ever there is more than 7\n+ * object types, or any future format extensions.\n+ */\n+\n+typedef enum {\n+\tPACKED_RESERVED = 0,\n+\tPACKED_COMMIT = 1,\n+\tPACKED_TREE = 2,\n+\tPACKED_BLOB = 3,\n+\tPACKED_TAG = 4,\n+\tPACKED_DELTA = 7\n+} packed_obj_type;\n+\n+#endif\ndiff --git a/unpack-objects.c b/unpack-objects.c\n--- a/unpack-objects.c\n+++ b/unpack-objects.c\n@@ -1,6 +1,7 @@\n #include \"cache.h\"\n #include \"object.h\"\n #include \"delta.h\"\n+#include \"pack.h\"\n \n static int dry_run;\n static int nr_entries;\n@@ -12,6 +13,14 @@ struct pack_entry {\n \tunsigned char sha1[20];\n };\n \n+static char *type_s[] = {\n+\t[PACKED_COMMIT]\t= \"commit\",\n+\t[PACKED_TREE]\t= \"tree\",\n+\t[PACKED_BLOB]\t= \"blob\",\n+\t[PACKED_TAG]\t= \"tag\",\n+\t[PACKED_DELTA]\t\"delta\"\n+};\n+\n static void *pack_base;\n static unsigned long pack_size;\n static void *index_base;\n@@ -92,7 +101,7 @@ static int check_index(void)\n }\n \n static int unpack_non_delta_entry(struct pack_entry *entry,\n-\t\t\t\t  int kind,\n+\t\t\t\t  char *type,\n \t\t\t\t  unsigned char *data,\n \t\t\t\t  unsigned long size,\n \t\t\t\t  unsigned long left)\n@@ -101,9 +110,8 @@ static int unpack_non_delta_entry(struct\n \tz_stream stream;\n \tchar *buffer;\n \tunsigned char sha1[20];\n-\tchar *type_s;\n \n-\tprintf(\"%s %c %lu\\n\", sha1_to_hex(entry->sha1), kind, size);\n+\tprintf(\"%s %s %lu\\n\", sha1_to_hex(entry->sha1), type, size);\n \tif (dry_run)\n \t\treturn 0;\n \n@@ -120,22 +128,15 @@ static int unpack_non_delta_entry(struct\n \tinflateEnd(&stream);\n \tif ((st != Z_STREAM_END) || stream.total_out != size)\n \t\tgoto err_finish;\n-\tswitch (kind) {\n-\tcase 'C': type_s = \"commit\"; break;\n-\tcase 'T': type_s = \"tree\"; break;\n-\tcase 'B': type_s = \"blob\"; break;\n-\tcase 'G': type_s = \"tag\"; break;\n-\tdefault: goto err_finish;\n-\t}\n-\tif (write_sha1_file(buffer, size, type_s, sha1) < 0)\n+\tif (write_sha1_file(buffer, size, type, sha1) < 0)\n \t\tdie(\"failed to write %s (%s)\",\n-\t\t    sha1_to_hex(entry->sha1), type_s);\n-\tprintf(\"%s %s\\n\", sha1_to_hex(sha1), type_s);\n+\t\t    sha1_to_hex(entry->sha1), type);\n+\tprintf(\"%s %s\\n\", sha1_to_hex(sha1), type);\n \tif (memcmp(sha1, entry->sha1, 20))\n-\t\tdie(\"resulting %s have wrong SHA1\", type_s);\n+\t\tdie(\"resulting %s have wrong SHA1\", type);\n \n- finish:\n \tst = 0;\n+ finish:\n \tfree(buffer);\n \treturn st;\n  err_finish:\n@@ -184,15 +185,13 @@ static int unpack_delta_entry(struct pac\n \t\tdie(\"truncated pack file\");\n \tdata = base_sha1 + 20;\n \tdata_size = left - 20;\n-\tprintf(\"%s D %lu\", sha1_to_hex(entry->sha1), delta_size);\n+\tprintf(\"%s delta %lu\", sha1_to_hex(entry->sha1), delta_size);\n \tprintf(\" %s\\n\", sha1_to_hex(base_sha1));\n \n \tif (dry_run)\n \t\treturn 0;\n \n-\t/* pack+5 is the base sha1, unless we have it, we need to\n-\t * unpack it first.\n-\t */\n+\t/* unless we have the base sha1, we need to unpack it first. */\n \tif (!has_sha1_file(base_sha1)) {\n \t\tstruct pack_entry *base;\n \t\tif (!find_pack_entry(base_sha1, &base))\n@@ -237,7 +236,9 @@ static int unpack_delta_entry(struct pac\n static void unpack_entry(struct pack_entry *entry)\n {\n \tunsigned long offset, size, left;\n-\tunsigned char *pack;\n+\tunsigned char *pack, sizebits;\n+\tpacked_obj_type type;\n+\tint i;\n \n \t/* Have we done this one already due to deltas based on it? */\n \tif (lookup_object(entry->sha1))\n@@ -247,17 +248,28 @@ static void unpack_entry(struct pack_ent\n \tif (offset > pack_size - 5)\n \t\tdie(\"object offset outside of pack file\");\n \tpack = pack_base + offset;\n-\tsize = (pack[1] << 24) + (pack[2] << 16) + (pack[3] << 8) + pack[4];\n-\tleft = pack_size - offset - 5;\n-\tswitch (*pack) {\n-\tcase 'C': case 'T': case 'B': case 'G':\n-\t\tunpack_non_delta_entry(entry, *pack, pack+5, size, left);\n+\tsizebits = *pack++;\n+\ttype = sizebits & 0x07;\n+\tsize = (sizebits & ~0x80) >> 3;\n+\ti = 4;\n+\twhile (sizebits & 0x80) {\n+\t\tsizebits = *pack++;\n+\t\tsize |= (sizebits & ~0x80) << i;\n+\t\ti += 7;\n+\t}\n+\tleft = pack_size - ((void *)pack - pack_base);\n+\tswitch (type) {\n+\tcase PACKED_COMMIT:\n+\tcase PACKED_TREE:\n+\tcase PACKED_BLOB:\n+\tcase PACKED_TAG:\n+\t\tunpack_non_delta_entry(entry, type_s[type], pack, size, left);\n \t\tbreak;\n-\tcase 'D':\n-\t\tunpack_delta_entry(entry, pack+5, size, left);\n+\tcase PACKED_DELTA:\n+\t\tunpack_delta_entry(entry, pack, size, left);\n \t\tbreak;\n \tdefault:\n-\t\tdie(\"corrupted pack file\");\n+\t\tdie(\"corrupted pack file(unknown object type %d)\", type);\n \t}\n }\n \n"},{"id":"5370","messageId":"Pine.LNX.4.58.0506281424420.19755@ppc970.osdl.org","threadId":"1022","inReplyTo":"Pine.LNX.4.63.0506281655140.1667@localhost.localdomain","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-28T21:27:19Z","receivedAt":"2005-06-28T21:27:19Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 28 Jun 2005, Nicolas Pitre wrote:\n> \n> OK.  New patch below.\n\nDammit, I wasted all that time doing it myself.\n\nI just committed and pushed out my version. But mine also does sha1_file.c \nright, so that you can use a packed archive in .git/objects/pack. Yours \nhas some other cleanups, so..\n\nCan you double-check my version (it hasn't mirrored out yet, it seems, but \nit should be there soon).\n\n> Probably a version signature would be a good thing too.\n\nI did that too, same format as for the index file. Nothing checks it \nthough.\n\n\t\tLinus\n"},{"id":"5372","messageId":"7vvf3ytad7.fsf_-_@assigned-by-dhcp.cox.net","threadId":"1022","inReplyTo":"Pine.LNX.4.58.0506281424420.19755@ppc970.osdl.org","subject":"[PATCH] Bugfix: initialize pack_base to NULL.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-06-28T21:55:16Z","receivedAt":"2005-06-28T21:55:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This was causing random segfaults, because use_packed_git() got\nconfused by random garbage there.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\n sha1_file.c |    1 +\n 1 files changed, 1 insertions(+), 0 deletions(-)\n\nfacb119577a28bbb3f2ac1e5f8db37fd2f6d31d8\ndiff --git a/sha1_file.c b/sha1_file.c\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -395,6 +395,7 @@ static struct packed_git *add_packed_git\n \tp->pack_size = st.st_size;\n \tp->index_base = idx_map;\n \tp->next = NULL;\n+\tp->pack_base = NULL;\n \tp->pack_last_used = 0;\n \treturn p;\n }\n------------\n"},{"id":"5393","messageId":"Pine.LNX.4.63.0506282314320.1667@localhost.localdomain","threadId":"1022","inReplyTo":"Pine.LNX.4.58.0506281424420.19755@ppc970.osdl.org","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-06-29T03:55:46Z","receivedAt":"2005-06-29T03:55:46Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 28 Jun 2005, Linus Torvalds wrote:\n\n> \n> \n> On Tue, 28 Jun 2005, Nicolas Pitre wrote:\n> > \n> > OK.  New patch below.\n> \n> Dammit, I wasted all that time doing it myself.\n> \n> I just committed and pushed out my version. But mine also does sha1_file.c \n> right, so that you can use a packed archive in .git/objects/pack. Yours \n> has some other cleanups, so..\n> \n> Can you double-check my version (it hasn't mirrored out yet, it seems, but \n> it should be there soon).\n\nOK... See below the cleanups I merged from my version on top of yours:\n\n pack-objects.c   |   70 ++++++++++++++-----------------------------------------\n pack.h           |   17 ++++++++-----\n unpack-objects.c |   66 +++++++++++++++++++++++++--------------------------\n 3 files changed, 63 insertions(+), 90 deletions(-)\n\nI also restored my original object header size ordering (little endian) \nfor two reasons:\n\n - it is much simpler to generate and therefore allows for removing \n   quite some code\n\n - it allows for stable bit position which makes it much easier to look \n   at an hex dump of the binary data for manual debugging\n\nAlso a few code optimizations and one error return fix.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\ndiff --git a/pack-objects.c b/pack-objects.c\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -34,7 +34,7 @@ static void *delta_against(void *buf, un\n \tif (!otherbuf)\n \t\tdie(\"unable to read %s\", sha1_to_hex(entry->delta->sha1));\n         delta_buf = diff_delta(otherbuf, othersize,\n-\t\t\t       buf, size, &delta_size, ~0UL);\n+\t\t\t       buf, size, &delta_size, 0UL);\n         if (!delta_buf || delta_size != entry->delta_size)\n         \tdie(\"delta size changed\");\n         free(buf);\n@@ -42,54 +42,13 @@ static void *delta_against(void *buf, un\n \treturn delta_buf;\n }\n \n-/*\n- * The per-object header is a pretty dense thing, which is\n- *  - first byte: low four bits are \"size\", then three bits of \"type\",\n- *    and the high bit is \"size continues\".\n- *  - each byte afterwards: low seven bits are size continuation,\n- *    with the high bit being \"size continues\"\n- */\n-static int encode_header(enum object_type type, unsigned long size, unsigned char *hdr)\n-{\n-\tint n = 1, i;\n-\tunsigned char c;\n-\n-\tif (type < OBJ_COMMIT || type > OBJ_DELTA)\n-\t\tdie(\"bad type %d\", type);\n-\n-\t/*\n-\t * Shift the size up by 7 bits at a time,\n-\t * until you get bits in the \"high four\".\n-\t * That will be our beginning. We'll have\n-\t * four size bits in 28..31, then groups\n-\t * of seven in 21..27, 14..20, 7..13 and\n-\t * finally 0..6.\n-\t */\n-\tif (size) {\n-\t\tn = 5;\n-\t\twhile (!(size & 0xfe000000)) {\n-\t\t\tsize <<= 7;\n-\t\t\tn--;\n-\t\t}\n-\t}\n-\tc = (type << 4) | (size >> 28);\n-\tfor (i = 1; i < n; i++) {\n-\t\t*hdr++ = c | 0x80;\n-\t\tc = (size >> 21) & 0x7f;\n-\t\tsize <<= 7;\n-\t}\n-\t*hdr = c;\n-\treturn n;\n-}\n-\n static unsigned long write_object(struct sha1file *f, struct object_entry *entry)\n {\n \tunsigned long size;\n \tchar type[10];\n \tvoid *buf = read_sha1_file(entry->sha1, type, &size);\n-\tunsigned char header[10];\n+\tchar header[25];\n \tunsigned hdrlen, datalen;\n-\tenum object_type obj_type;\n \n \tif (!buf)\n \t\tdie(\"unable to read %s\", sha1_to_hex(entry->sha1));\n@@ -97,22 +56,31 @@ static unsigned long write_object(struct\n \t\tdie(\"object %s size inconsistency (%lu vs %lu)\", sha1_to_hex(entry->sha1), size, entry->size);\n \n \t/*\n-\t * The object header is a byte of 'type' followed by zero or\n-\t * more bytes of length.  For deltas, the 20 bytes of delta sha1\n-\t * follows that.\n+\t * The object header first byte has its low 3 bits representing the\n+\t * object type, the 4 upper bits indicating which of the following\n+\t * bytes are used to build the object size.  For delta objects the\n+\t * sha1 of the reference object is also appended.\n \t */\n-\tobj_type = entry->type;\n \tif (entry->delta) {\n+\t\theader[0] = OBJ_DELTA;\n \t\tbuf = delta_against(buf, size, entry);\n \t\tsize = entry->delta_size;\n-\t\tobj_type = OBJ_DELTA;\n+\t} else\n+\t\theader[0] = entry->type;\n+\theader[0] |= size << 3;\n+\thdrlen = 1;\n+\tdatalen = size >> 4;\n+\twhile (datalen) {\n+\t\theader[hdrlen - 1] |= 0x80;\n+\t\theader[hdrlen++] = datalen;\n+\t\tdatalen >>= 7;\n \t}\n-\thdrlen = encode_header(obj_type, size, header);\n-\tsha1write(f, header, hdrlen);\n \tif (entry->delta) {\n-\t\tsha1write(f, entry->delta, 20);\n+\t\tmemcpy(header+hdrlen, entry->delta, 20);\n \t\thdrlen += 20;\n \t}\n+\n+\tsha1write(f, header, hdrlen);\n \tdatalen = sha1write_compressed(f, buf, size);\n \tfree(buf);\n \treturn hdrlen + datalen;\ndiff --git a/pack.h b/pack.h\n--- a/pack.h\n+++ b/pack.h\n@@ -1,13 +1,18 @@\n #ifndef PACK_H\n #define PACK_H\n \n+/*\n+ * The packed object type is stored in the low 3 bits of a byte.\n+ * The type value 0 is a reserved prefix if ever there is more than 7\n+ * object types, or any future format extensions.\n+ */\n enum object_type {\n-\tOBJ_NONE,\n-\tOBJ_COMMIT,\n-\tOBJ_TREE,\n-\tOBJ_BLOB,\n-\tOBJ_TAG,\n-\tOBJ_DELTA,\n+\tOBJ_EXT = 0,\n+\tOBJ_COMMIT = 1,\n+\tOBJ_TREE = 2,\n+\tOBJ_BLOB = 3,\n+\tOBJ_TAG = 4,\n+\tOBJ_DELTA = 7\n };\n \n /*\ndiff --git a/unpack-objects.c b/unpack-objects.c\n--- a/unpack-objects.c\n+++ b/unpack-objects.c\n@@ -13,6 +13,14 @@ struct pack_entry {\n \tunsigned char sha1[20];\n };\n \n+static char *type_string[] = {\n+\t[OBJ_COMMIT]\t= \"commit\",\n+\t[OBJ_TREE]\t= \"tree\",\n+\t[OBJ_BLOB]\t= \"blob\",\n+\t[OBJ_TAG]\t= \"tag\",\n+\t[OBJ_DELTA]\t= \"delta\"\n+};\n+\n static void *pack_base;\n static unsigned long pack_size;\n static void *index_base;\n@@ -93,7 +101,7 @@ static int check_index(void)\n }\n \n static int unpack_non_delta_entry(struct pack_entry *entry,\n-\t\t\t\t  enum object_type kind,\n+\t\t\t\t  char *type,\n \t\t\t\t  unsigned char *data,\n \t\t\t\t  unsigned long size,\n \t\t\t\t  unsigned long left)\n@@ -102,9 +110,8 @@ static int unpack_non_delta_entry(struct\n \tz_stream stream;\n \tchar *buffer;\n \tunsigned char sha1[20];\n-\tchar *type;\n \n-\tprintf(\"%s %c %lu\\n\", sha1_to_hex(entry->sha1), \".CTBGD\"[kind], size);\n+\tprintf(\"%s %s %lu\\n\", sha1_to_hex(entry->sha1), type, size);\n \tif (dry_run)\n \t\treturn 0;\n \n@@ -121,13 +128,6 @@ static int unpack_non_delta_entry(struct\n \tinflateEnd(&stream);\n \tif ((st != Z_STREAM_END) || stream.total_out != size)\n \t\tgoto err_finish;\n-\tswitch (kind) {\n-\tcase OBJ_COMMIT: type = \"commit\"; break;\n-\tcase OBJ_TREE:   type = \"tree\"; break;\n-\tcase OBJ_BLOB:   type = \"blob\"; break;\n-\tcase OBJ_TAG:    type = \"tag\"; break;\n-\tdefault: goto err_finish;\n-\t}\n \tif (write_sha1_file(buffer, size, type, sha1) < 0)\n \t\tdie(\"failed to write %s (%s)\",\n \t\t    sha1_to_hex(entry->sha1), type);\n@@ -135,8 +135,8 @@ static int unpack_non_delta_entry(struct\n \tif (memcmp(sha1, entry->sha1, 20))\n \t\tdie(\"resulting %s have wrong SHA1\", type);\n \n- finish:\n \tst = 0;\n+ finish:\n \tfree(buffer);\n \treturn st;\n  err_finish:\n@@ -185,15 +185,13 @@ static int unpack_delta_entry(struct pac\n \t\tdie(\"truncated pack file\");\n \tdata = base_sha1 + 20;\n \tdata_size = left - 20;\n-\tprintf(\"%s D %lu\", sha1_to_hex(entry->sha1), delta_size);\n+\tprintf(\"%s delta %lu\", sha1_to_hex(entry->sha1), delta_size);\n \tprintf(\" %s\\n\", sha1_to_hex(base_sha1));\n \n \tif (dry_run)\n \t\treturn 0;\n \n-\t/* pack+5 is the base sha1, unless we have it, we need to\n-\t * unpack it first.\n-\t */\n+\t/* unless we have the base sha1, we need to unpack it first. */\n \tif (!has_sha1_file(base_sha1)) {\n \t\tstruct pack_entry *base;\n \t\tif (!find_pack_entry(base_sha1, &base))\n@@ -238,8 +236,9 @@ static int unpack_delta_entry(struct pac\n static void unpack_entry(struct pack_entry *entry)\n {\n \tunsigned long offset, size, left;\n-\tunsigned char *pack, c;\n-\tint type;\n+\tunsigned char c, *pack = pack_base;\n+\tint i;\n+\tenum object_type type;\n \n \t/* Have we done this one already due to deltas based on it? */\n \tif (lookup_object(entry->sha1))\n@@ -247,20 +246,17 @@ static void unpack_entry(struct pack_ent\n \n \toffset = ntohl(entry->offset);\n \tif (offset >= pack_size)\n-\t\tgoto bad;\n-\n-\tpack = pack_base + offset;\n-\tc = *pack++;\n-\toffset++;\n-\ttype = (c >> 4) & 7;\n-\tsize = (c & 15);\n+\t\tgoto out_of_bound;\n+\tc = pack[offset++];\n+\ttype = c & 0x07;\n+\tsize = (c & ~0x80) >> 3;\n+\ti = 4;\n \twhile (c & 0x80) {\n \t\tif (offset >= pack_size)\n-\t\t\tgoto bad;\n-\t\toffset++;\n-\t\tc = *pack++;\n-\t\tsize = (size << 7) + (c & 0x7f);\n-\t\t\n+\t\t\tgoto out_of_bound;\n+\t\tc = pack[offset++];\n+\t\tsize |= (c & ~0x80) << i;\n+\t\ti += 7;\n \t}\n \tleft = pack_size - offset;\n \tswitch (type) {\n@@ -268,14 +264,18 @@ static void unpack_entry(struct pack_ent\n \tcase OBJ_TREE:\n \tcase OBJ_BLOB:\n \tcase OBJ_TAG:\n-\t\tunpack_non_delta_entry(entry, type, pack, size, left);\n+\t\tunpack_non_delta_entry(entry, type_string[type],\n+\t\t\t\t       pack+offset, size, left);\n \t\treturn;\n \tcase OBJ_DELTA:\n-\t\tunpack_delta_entry(entry, pack, size, left);\n+\t\tunpack_delta_entry(entry, pack+offset, size, left);\n \t\treturn;\n+\tdefault:\n+\t\tdie(\"corrupted pack file(unknown object type %d)\", type);\n \t}\n-bad:\n-\tdie(\"corrupted pack file\");\n+\n+ out_of_bound:\n+\tdie(\"corrupted pack file (object offset out of bound)\");\n }\n \n /*\n"},{"id":"5396","messageId":"Pine.LNX.4.63.0506290111250.1667@localhost.localdomain","threadId":"1022","inReplyTo":"Pine.LNX.4.63.0506282314320.1667@localhost.localdomain","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-06-29T05:16:29Z","receivedAt":"2005-06-29T05:16:29Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 28 Jun 2005, Nicolas Pitre wrote:\n\n> OK... See below the cleanups I merged from my version on top of yours:\n\nOf course by the time I sent the above you already rewrote the ting to \nbe streamable.\n\nSo again :-) see below the cleanups I merged from my version on top of \nyours:\n\n pack-objects.c   |   70 ++++++++++++++-----------------------------------------\n pack.h           |   17 ++++++++-----\n unpack-objects.c |   29 ++++++++++++----------\n 3 files changed, 46 insertions(+), 70 deletions(-)\n\nI also restored my original object header size ordering (little endian) \nfor two reasons:\n\n - it is much simpler to generate and therefore allows for removing \n   quite some code\n\n - it allows for stable bit position which makes it much easier to look \n   at an hex dump of the binary data for manual debugging\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\ndiff --git a/pack-objects.c b/pack-objects.c\n--- a/pack-objects.c\n+++ b/pack-objects.c\n@@ -34,7 +34,7 @@ static void *delta_against(void *buf, un\n \tif (!otherbuf)\n \t\tdie(\"unable to read %s\", sha1_to_hex(entry->delta->sha1));\n         delta_buf = diff_delta(otherbuf, othersize,\n-\t\t\t       buf, size, &delta_size, ~0UL);\n+\t\t\t       buf, size, &delta_size, 0UL);\n         if (!delta_buf || delta_size != entry->delta_size)\n         \tdie(\"delta size changed\");\n         free(buf);\n@@ -42,54 +42,13 @@ static void *delta_against(void *buf, un\n \treturn delta_buf;\n }\n \n-/*\n- * The per-object header is a pretty dense thing, which is\n- *  - first byte: low four bits are \"size\", then three bits of \"type\",\n- *    and the high bit is \"size continues\".\n- *  - each byte afterwards: low seven bits are size continuation,\n- *    with the high bit being \"size continues\"\n- */\n-static int encode_header(enum object_type type, unsigned long size, unsigned char *hdr)\n-{\n-\tint n = 1, i;\n-\tunsigned char c;\n-\n-\tif (type < OBJ_COMMIT || type > OBJ_DELTA)\n-\t\tdie(\"bad type %d\", type);\n-\n-\t/*\n-\t * Shift the size up by 7 bits at a time,\n-\t * until you get bits in the \"high four\".\n-\t * That will be our beginning. We'll have\n-\t * four size bits in 28..31, then groups\n-\t * of seven in 21..27, 14..20, 7..13 and\n-\t * finally 0..6.\n-\t */\n-\tif (size) {\n-\t\tn = 5;\n-\t\twhile (!(size & 0xfe000000)) {\n-\t\t\tsize <<= 7;\n-\t\t\tn--;\n-\t\t}\n-\t}\n-\tc = (type << 4) | (size >> 28);\n-\tfor (i = 1; i < n; i++) {\n-\t\t*hdr++ = c | 0x80;\n-\t\tc = (size >> 21) & 0x7f;\n-\t\tsize <<= 7;\n-\t}\n-\t*hdr = c;\n-\treturn n;\n-}\n-\n static unsigned long write_object(struct sha1file *f, struct object_entry *entry)\n {\n \tunsigned long size;\n \tchar type[10];\n \tvoid *buf = read_sha1_file(entry->sha1, type, &size);\n-\tunsigned char header[10];\n+\tchar header[25];\n \tunsigned hdrlen, datalen;\n-\tenum object_type obj_type;\n \n \tif (!buf)\n \t\tdie(\"unable to read %s\", sha1_to_hex(entry->sha1));\n@@ -97,22 +56,31 @@ static unsigned long write_object(struct\n \t\tdie(\"object %s size inconsistency (%lu vs %lu)\", sha1_to_hex(entry->sha1), size, entry->size);\n \n \t/*\n-\t * The object header is a byte of 'type' followed by zero or\n-\t * more bytes of length.  For deltas, the 20 bytes of delta sha1\n-\t * follows that.\n+\t * The object header first byte has its low 3 bits representing the\n+\t * object type, the 4 upper bits indicating which of the following\n+\t * bytes are used to build the object size.  For delta objects the\n+\t * sha1 of the reference object is also appended.\n \t */\n-\tobj_type = entry->type;\n \tif (entry->delta) {\n+\t\theader[0] = OBJ_DELTA;\n \t\tbuf = delta_against(buf, size, entry);\n \t\tsize = entry->delta_size;\n-\t\tobj_type = OBJ_DELTA;\n+\t} else\n+\t\theader[0] = entry->type;\n+\theader[0] |= size << 3;\n+\thdrlen = 1;\n+\tdatalen = size >> 4;\n+\twhile (datalen) {\n+\t\theader[hdrlen - 1] |= 0x80;\n+\t\theader[hdrlen++] = datalen;\n+\t\tdatalen >>= 7;\n \t}\n-\thdrlen = encode_header(obj_type, size, header);\n-\tsha1write(f, header, hdrlen);\n \tif (entry->delta) {\n-\t\tsha1write(f, entry->delta, 20);\n+\t\tmemcpy(header+hdrlen, entry->delta, 20);\n \t\thdrlen += 20;\n \t}\n+\n+\tsha1write(f, header, hdrlen);\n \tdatalen = sha1write_compressed(f, buf, size);\n \tfree(buf);\n \treturn hdrlen + datalen;\ndiff --git a/pack.h b/pack.h\n--- a/pack.h\n+++ b/pack.h\n@@ -1,13 +1,18 @@\n #ifndef PACK_H\n #define PACK_H\n \n+/*\n+ * The packed object type is stored in the low 3 bits of a byte.\n+ * The type value 0 is a reserved prefix if ever there is more than 7\n+ * object types, or any future format extensions.\n+ */\n enum object_type {\n-\tOBJ_NONE,\n-\tOBJ_COMMIT,\n-\tOBJ_TREE,\n-\tOBJ_BLOB,\n-\tOBJ_TAG,\n-\tOBJ_DELTA,\n+\tOBJ_EXT = 0,\n+\tOBJ_COMMIT = 1,\n+\tOBJ_TREE = 2,\n+\tOBJ_BLOB = 3,\n+\tOBJ_TAG = 4,\n+\tOBJ_DELTA = 7\n };\n \n /*\ndiff --git a/unpack-objects.c b/unpack-objects.c\n--- a/unpack-objects.c\n+++ b/unpack-objects.c\n@@ -6,6 +6,14 @@\n static int dry_run;\n static const char unpack_usage[] = \"git-unpack-objects < pack-file\";\n \n+static char *type_string[] = {\n+\t[OBJ_COMMIT]\t= \"commit\",\n+\t[OBJ_TREE]\t= \"tree\",\n+\t[OBJ_BLOB]\t= \"blob\",\n+\t[OBJ_TAG]\t= \"tag\",\n+\t[OBJ_DELTA]\t= \"delta\"\n+};\n+\n /* We always read in 4kB chunks. */\n static unsigned char buffer[4096];\n static unsigned long offset, len, eof;\n@@ -139,19 +147,11 @@ static void added_object(unsigned char *\n \t}\n }\n \n-static int unpack_non_delta_entry(enum object_type kind, unsigned long size)\n+static int unpack_non_delta_entry(char *type, unsigned long size)\n {\n \tvoid *buf = get_data(size);\n \tunsigned char sha1[20];\n-\tchar *type;\n \n-\tswitch (kind) {\n-\tcase OBJ_COMMIT: type = \"commit\"; break;\n-\tcase OBJ_TREE:   type = \"tree\"; break;\n-\tcase OBJ_BLOB:   type = \"blob\"; break;\n-\tcase OBJ_TAG:    type = \"tag\"; break;\n-\tdefault: die(\"bad type %d\", kind);\n-\t}\n \tif (write_sha1_file(buf, size, type, sha1) < 0)\n \t\tdie(\"failed to write object\");\n \tadded_object(sha1, type, buf, size);\n@@ -184,26 +184,29 @@ static int unpack_delta_entry(unsigned l\n static void unpack_one(void)\n {\n \tunsigned char *pack, c;\n+\tunsigned int i;\n \tunsigned long size;\n \tenum object_type type;\n \n \tpack = fill(1);\n \tc = *pack;\n \tuse(1);\n-\ttype = (c >> 4) & 7;\n-\tsize = (c & 15);\n+\ttype = c & 0x07;\n+\tsize = (c & ~0x80) >> 3;\n+\ti = 4;\n \twhile (c & 0x80) {\n \t\tpack = fill(1);\n \t\tc = *pack++;\n \t\tuse(1);\n-\t\tsize = (size << 7) + (c & 0x7f);\n+\t\tsize |= (c & ~0x80) << i;\n+\t\ti += 7;\n \t}\n \tswitch (type) {\n \tcase OBJ_COMMIT:\n \tcase OBJ_TREE:\n \tcase OBJ_BLOB:\n \tcase OBJ_TAG:\n-\t\tunpack_non_delta_entry(type, size);\n+\t\tunpack_non_delta_entry(type_string[type], size);\n \t\treturn;\n \tcase OBJ_DELTA:\n \t\tunpack_delta_entry(size);\n"},{"id":"5399","messageId":"Pine.LNX.4.58.0506282243180.19755@ppc970.osdl.org","threadId":"1022","inReplyTo":"Pine.LNX.4.63.0506290111250.1667@localhost.localdomain","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-29T05:43:50Z","receivedAt":"2005-06-29T05:43:50Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 29 Jun 2005, Nicolas Pitre wrote:\n> \n> Of course by the time I sent the above you already rewrote the ting to \n> be streamable.\n\nAnd by the time you sent me a new version, I'd already taken part of your \nold one by hand ;)\n\n\t\tLinus\n"},{"id":"5402","messageId":"Pine.LNX.4.58.0506282252001.14331@ppc970.osdl.org","threadId":"1022","inReplyTo":"Pine.LNX.4.58.0506282243180.19755@ppc970.osdl.org","subject":"Re: kernel.org and GIT tree rebuilding","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-29T05:54:26Z","receivedAt":"2005-06-29T05:54:26Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 28 Jun 2005, Linus Torvalds wrote:\n> \n> On Wed, 29 Jun 2005, Nicolas Pitre wrote:\n> > \n> > Of course by the time I sent the above you already rewrote the ting to \n> > be streamable.\n> \n> And by the time you sent me a new version, I'd already taken part of your \n> old one by hand ;)\n\nBtw, I have the size/type bits reversed from your setup, but please don't \nchange that, since that would be yet another incompatible pack format \nchange, and I'd like to calm things down.\n\nAlso, I notice that you decode the sizes really strangely: you have a \n\"while() { }\" loop and two separate loads. It's much nicer to do it with a \n\"do { } while()\" loop and a single load, since not only is it less code, \na do-while loop compiles to better code than a while() loop (unless the \ncompiler is crazy, which it sometimes is).\n\n\t\tLinus\n"},{"id":"5409","messageId":"7v4qbhfxad.fsf_-_@assigned-by-dhcp.cox.net","threadId":"1022","inReplyTo":"Pine.LNX.4.58.0506282252001.14331@ppc970.osdl.org","subject":"Last mile for 1.0 again","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-06-29T07:16:10Z","receivedAt":"2005-06-29T07:16:10Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"LT\" == Linus Torvalds <torvalds@osdl.org> writes:\n\nLT> ..., but please don't \nLT> change that, since that would be yet another incompatible pack format \nLT> change, and I'd like to calm things down.\n\nCalming things down is good.  Some stuff we should be looking at\nduring calming down period are:\n\n - Ask expert help to verify our use of zlib is OK; Linus asked\n   for this in a message tonight.  I am not qualified to do this\n   myself.\n\n - There is currently nothing that verifies the SHA1 sums\n   embedded in idx and pack files.  A tool for it is needed\n   [*1*].  I may be doing this myself.\n\n - Although there is a hook in sha1_file() that allows mapping a\n   pack file on demand (and keep track of their uses for LRU\n   eviction), there is currently no code to actually evict a\n   mapped pack file.  We need to add some sort of use-reference\n   counting to lock down a pack file in use, if somebody is\n   inclined to do this.  I will not be doing this myself\n   immediately.\n\n - Think about what to do with the \"dumb server\" pull protocols\n   regarding packed archive files (think about http-pull).  I\n   will not be doing this myself.\n\n - Design \"smart server\" pull/push pair.  This can independently\n   and actively be done without impacting \"calming down\" period,\n   and I am assuming Dan is already looking into this.  This may\n   result in another \"deathmatch\" between Dan and Jason\n   Mcmullan, which would be fun to watch ;-).\n\n\nNot limited to \"calming down the packed GIT\", but bigger picture\npre-release preparation items I think we need to look into are:\n\n - Update \"Last mile for 1.0\" list.  I think the only thing that\n   is left from the one I posted on Jun 5th is the tutorials.\n\n   Anybody interested in adding more pages to the tutorials?  If\n   there is no taker, I may start continuing what is already\n   there, stealing example project outline from \"Arch meets\n   Hello World\" [*2*].\n\n - Double check the documentation, usage strings in the code and\n   what the code does still match.  Last time I checked, I think\n   some files in Documentation/ directory were not reachable\n   from the main GIT(1) page and were not touched by the build\n   process from Documentation/Makefile.  I will not be doing\n   this myself.\n\n - Blame/Annotate.  Does anybody have a fast and correct one\n   [*3*]?\n\n - Publicity.  Somebody may want to start preparing materials to\n   have us included in http://better-scm.berlios.de/comparison/\n\n\n[Footnotes]\n\n*1* One possibility is to add that to fsck-cache when --full is\nused, but I am somewhat reluctant to do it that way.  It would\nrequire you to place that \"suspicious\" pack under your\nrepository's .git/objects/pack in order to verify it, which can\nspread the damage before you know it.\n\nIn general, idx file is relatively small, so we _could_ check\nthe SHA1 sum for idx files when we map them at runtime in\ncheck_packed_git_idx().  However, verifying 1MB (kernel archive\ncase) idx file every time we run a single core GIT command may\nbe a price we would not want to pay, so I am not too\nenthusiastic about doing it.  We certainly would not want to do\nthis for pack files every time a pack is mapped at runtime (60MB\nkernel archive case).\n\n*2* http://regexps.srparish.net/www/tutorial/html/arch.html.\n\nI am not talking about stealing the concepts but just talking\nabout stealing the sample project on which example players work\nin the sample sessions.  I think its section on update/replay\nmatches closely to merge/rebase, for example.\n\n*3* I have what I wrote in Perl which does rename/copy/rewrite\nand multiple parents correctly, but it is way too slow for\non-demand use.\n"},{"id":"5411","messageId":"7vvf3xcwyo.fsf_-_@assigned-by-dhcp.cox.net","threadId":"1022","inReplyTo":"7v4qbhfxad.fsf_-_@assigned-by-dhcp.cox.net","subject":"[PATCH] Add git-verify-pack command.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-06-29T09:51:27Z","receivedAt":"2005-06-29T09:51:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Given a list of <pack>.idx files, this command validates the\nindex file and the corresponding .pack file for consistency.\n\nThis patch also uses the same validation mechanism in fsck-cache\nwhen the --full flag is used.\n\nDuring normal operation, sha1_file.c verifies that a given .idx\nfile matches the .pack file by comparing the SHA1 checksum\nstored in .idx file and .pack file as a minimum sanity check.\nWe may further want to check the pack signature and version when\nwe map the pack, but that would be a separate patch.\n\nEarlier, errors to map a pack file was not flagged fatal but led\nto a random fatal error later.  This version explicitly die()s\nwhen such an error is detected.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n---\n\n*** This actually covers two of the items I listed in the \"Last\n*** mile again\" message.  I ended up doing the LRU myself.\n\n*** Linus, what would be the practical/recommended/sane limit\n*** for mmap regions we would want to use?  Currently I start\n*** throwing away mapped packs when the total size of mapped\n*** packs exceeds 64MB.\n\n*** Currently, pack-objects/unpack-objects pair is not\n*** documented.  Any takers?\n\n*** Oh, again, Linus, what is your preferred way to get a\n*** cover-letter material (like this) for a single patch?  I\n*** always do a separate cover letter for multi-patch series\n*** with [PATCH 0/N], but do you prefer to get [PATCH 0/1] and\n*** [PATCH 1/1] for a single patch, or do you prefer to see\n*** commentaries after the three-dash line like this message\n*** does?\n\n Documentation/git-verify-pack.txt |   38 +++++++++++++++++++++\n Documentation/git.txt             |    3 ++\n Makefile                          |    5 ++-\n cache.h                           |    4 ++\n fsck-cache.c                      |    5 +++\n pack.h                            |    2 +\n sha1_file.c                       |   66 ++++++++++++++++++++++++++++---------\n t/t5300-pack-object.sh            |   38 +++++++++++++++++++++\n verify-pack.c                     |   26 +++++++++++++++\n verify_pack.c                     |   62 +++++++++++++++++++++++++++++++++++\n 10 files changed, 231 insertions(+), 18 deletions(-)\n create mode 100644 Documentation/git-verify-pack.txt\n create mode 100644 verify-pack.c\n create mode 100644 verify_pack.c\n\n8ac4f374a587c58b3d2ecc44220b6b866f769350\ndiff --git a/Documentation/git-verify-pack.txt b/Documentation/git-verify-pack.txt\nnew file mode 100644\n--- /dev/null\n+++ b/Documentation/git-verify-pack.txt\n@@ -0,0 +1,38 @@\n+git-verify-pack(1)\n+==================\n+v0.1, June 2005\n+\n+NAME\n+----\n+git-verify-pack - Validate packed GIT archive files.\n+\n+\n+SYNOPSIS\n+--------\n+'git-verify-pack' <pack>.idx ...\n+\n+\n+DESCRIPTION\n+-----------\n+Reads given idx file for packed GIT archive created with\n+git-pack-objects command and verifies idx file and the\n+corresponding pack file.\n+\n+OPTIONS\n+-------\n+<pack>.idx ...::\n+\tThe idx files to verify.\n+\n+\n+Author\n+------\n+Written by Junio C Hamano <junkio@cox.net>\n+\n+Documentation\n+--------------\n+Documentation by Junio C Hamano\n+\n+GIT\n+---\n+Part of the link:git.html[git] suite\n+\ndiff --git a/Documentation/git.txt b/Documentation/git.txt\n--- a/Documentation/git.txt\n+++ b/Documentation/git.txt\n@@ -110,6 +110,9 @@ link:git-tar-tree.html[git-tar-tree]::\n link:git-unpack-file.html[git-unpack-file]::\n \tCreates a temporary file with a blob's contents\n \n+link:git-verify-pack.html[git-verify-pack]::\n+\tValidates packed GIT archive files\n+\n The interrogate commands may create files - and you can force them to\n touch the working file set - but in general they don't\n \ndiff --git a/Makefile b/Makefile\n--- a/Makefile\n+++ b/Makefile\n@@ -36,7 +36,7 @@ PROG=   git-update-cache git-diff-files \n \tgit-diff-helper git-tar-tree git-local-pull git-write-blob \\\n \tgit-get-tar-commit-id git-apply git-stripspace \\\n \tgit-cvs2git git-diff-stages git-rev-parse git-patch-id \\\n-\tgit-pack-objects git-unpack-objects\n+\tgit-pack-objects git-unpack-objects git-verify-pack\n \n all: $(PROG)\n \n@@ -45,7 +45,7 @@ install: $(PROG) $(SCRIPTS)\n \n LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o \\\n \t tag.o date.o index.o diff-delta.o patch-delta.o entry.o \\\n-\t epoch.o refs.o csum-file.o\n+\t epoch.o refs.o csum-file.o verify_pack.o\n LIB_FILE=libgit.a\n LIB_H=cache.h object.h blob.h tree.h commit.h tag.h delta.h epoch.h csum-file.h pack.h\n \n@@ -124,6 +124,7 @@ git-rev-parse: rev-parse.c\n git-patch-id: patch-id.c\n git-pack-objects: pack-objects.c\n git-unpack-objects: unpack-objects.c\n+git-verify-pack: verify-pack.c\n \n git-http-pull: LIBS += -lcurl\n git-rev-list: LIBS += -lssl\ndiff --git a/cache.h b/cache.h\n--- a/cache.h\n+++ b/cache.h\n@@ -246,9 +246,13 @@ extern struct packed_git {\n \tunsigned int *index_base;\n \tvoid *pack_base;\n \tunsigned int pack_last_used;\n+\tunsigned int pack_use_cnt;\n \tchar pack_name[0]; /* something like \".git/objects/pack/xxxxx.pack\" */\n } *packed_git;\n extern void prepare_packed_git(void);\n+extern int use_packed_git(struct packed_git *);\n+extern void unuse_packed_git(struct packed_git *);\n+extern struct packed_git *add_packed_git(char *, int);\n extern int num_packed_objects(const struct packed_git *p);\n extern int nth_packed_object_sha1(const struct packed_git *, int, unsigned char*);\n \ndiff --git a/fsck-cache.c b/fsck-cache.c\n--- a/fsck-cache.c\n+++ b/fsck-cache.c\n@@ -6,6 +6,7 @@\n #include \"tree.h\"\n #include \"blob.h\"\n #include \"tag.h\"\n+#include \"pack.h\"\n \n #define REACHABLE 0x0001\n \n@@ -437,6 +438,10 @@ int main(int argc, char **argv)\n \t\t\talt_odb[j].name[-1] = '/';\n \t\t}\n \t\tprepare_packed_git();\n+\t\tfor (p = packed_git; p; p = p->next)\n+\t\t\t/* verify gives error messages itself */\n+\t\t\tverify_pack(p); \n+\n \t\tfor (p = packed_git; p; p = p->next) {\n \t\t\tint num = num_packed_objects(p);\n \t\t\tfor (i = 0; i < num; i++) {\ndiff --git a/pack.h b/pack.h\n--- a/pack.h\n+++ b/pack.h\n@@ -27,4 +27,6 @@ struct pack_header {\n \tunsigned int hdr_entries;\n };\n \n+extern int verify_pack(struct packed_git *);\n+\n #endif\ndiff --git a/sha1_file.c b/sha1_file.c\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -302,7 +302,7 @@ static int check_packed_git_idx(const ch\n \tindex = idx_map;\n \n \t/* check index map */\n-\tif (idx_size < 4*256 + 20)\n+\tif (idx_size < 4*256 + 20 + 20)\n \t\treturn error(\"index file too small\");\n \tnr = 0;\n \tfor (i = 0; i < 256; i++) {\n@@ -327,12 +327,29 @@ static int check_packed_git_idx(const ch\n \treturn 0;\n }\n \n-static void unuse_one_packed_git(void)\n+static int unuse_one_packed_git(void)\n {\n-\t/* NOTYET */\n+\tstruct packed_git *p, *lru = NULL;\n+\n+\tfor (p = packed_git; p; p = p->next) {\n+\t\tif (p->pack_use_cnt || !p->pack_base)\n+\t\t\tcontinue;\n+\t\tif (!lru || p->pack_last_used < lru->pack_last_used)\n+\t\t\tlru = p;\n+\t}\n+\tif (!lru)\n+\t\treturn 0;\n+\tmunmap(lru->pack_base, lru->pack_size);\n+\tlru->pack_base = NULL;\n+\treturn 1;\n+}\n+\n+void unuse_packed_git(struct packed_git *p)\n+{\n+\tp->pack_use_cnt--;\n }\n \n-static int use_packed_git(struct packed_git *p)\n+int use_packed_git(struct packed_git *p)\n {\n \tif (!p->pack_base) {\n \t\tint fd;\n@@ -340,28 +357,36 @@ static int use_packed_git(struct packed_\n \t\tvoid *map;\n \n \t\tpack_mapped += p->pack_size;\n-\t\twhile (PACK_MAX_SZ < pack_mapped)\n-\t\t\tunuse_one_packed_git();\n+\t\twhile (PACK_MAX_SZ < pack_mapped && unuse_one_packed_git())\n+\t\t\t; /* nothing */\n \t\tfd = open(p->pack_name, O_RDONLY);\n \t\tif (fd < 0)\n-\t\t\treturn -1;\n+\t\t\tdie(\"packfile %s cannot be opened\", p->pack_name);\n \t\tif (fstat(fd, &st)) {\n \t\t\tclose(fd);\n-\t\t\treturn -1;\n+\t\t\tdie(\"packfile %s cannot be opened\", p->pack_name);\n \t\t}\n \t\tif (st.st_size != p->pack_size)\n-\t\t\treturn -1;\n+\t\t\tdie(\"packfile %s size mismatch.\", p->pack_name);\n \t\tmap = mmap(NULL, p->pack_size, PROT_READ, MAP_PRIVATE, fd, 0);\n \t\tclose(fd);\n \t\tif (map == MAP_FAILED)\n-\t\t\treturn -1;\n+\t\t\tdie(\"packfile %s cannot be mapped.\", p->pack_name);\n \t\tp->pack_base = map;\n+\n+\t\t/* Check if the pack file matches with the index file.\n+\t\t * this is cheap.\n+\t\t */\n+\t\tif (memcmp((char*)(p->index_base) + p->index_size - 40,\n+\t\t\t   p->pack_base + p->pack_size - 20, 20))\n+\t\t\tdie(\"packfile %s does not match index.\", p->pack_name);\n \t}\n \tp->pack_last_used = pack_used_ctr++;\n+\tp->pack_use_cnt++;\n \treturn 0;\n }\n \n-static struct packed_git *add_packed_git(char *path, int path_len)\n+struct packed_git *add_packed_git(char *path, int path_len)\n {\n \tstruct stat st;\n \tstruct packed_git *p;\n@@ -388,6 +413,7 @@ static struct packed_git *add_packed_git\n \tp->next = NULL;\n \tp->pack_base = NULL;\n \tp->pack_last_used = 0;\n+\tp->pack_use_cnt = 0;\n \treturn p;\n }\n \n@@ -671,6 +697,7 @@ static int packed_object_info(struct pac\n \tunsigned long offset, size, left;\n \tunsigned char *pack;\n \tenum object_type kind;\n+\tint retval;\n \n \tif (use_packed_git(p))\n \t\tdie(\"cannot map packed file\");\n@@ -681,8 +708,9 @@ static int packed_object_info(struct pac\n \n \tswitch (kind) {\n \tcase OBJ_DELTA:\n-\t\treturn packed_delta_info(pack, size, left, type, sizep);\n-\t\tbreak;\n+\t\tretval = packed_delta_info(pack, size, left, type, sizep);\n+\t\tunuse_packed_git(p);\n+\t\treturn retval;\n \tcase OBJ_COMMIT:\n \t\tstrcpy(type, \"commit\");\n \t\tbreak;\n@@ -699,6 +727,7 @@ static int packed_object_info(struct pac\n \t\tdie(\"corrupted pack file\");\n \t}\n \t*sizep = size;\n+\tunuse_packed_git(p);\n \treturn 0;\n }\n \n@@ -785,6 +814,7 @@ static void *unpack_entry(struct pack_en\n \tunsigned long offset, size, left;\n \tunsigned char *pack;\n \tenum object_type kind;\n+\tvoid *retval;\n \n \tif (use_packed_git(p))\n \t\tdie(\"cannot map packed file\");\n@@ -794,7 +824,9 @@ static void *unpack_entry(struct pack_en\n \tleft = p->pack_size - offset;\n \tswitch (kind) {\n \tcase OBJ_DELTA:\n-\t\treturn unpack_delta_entry(pack, size, left, type, sizep);\n+\t\tretval = unpack_delta_entry(pack, size, left, type, sizep);\n+\t\tunuse_packed_git(p);\n+\t\treturn retval;\n \tcase OBJ_COMMIT:\n \t\tstrcpy(type, \"commit\");\n \t\tbreak;\n@@ -811,12 +843,14 @@ static void *unpack_entry(struct pack_en\n \t\tdie(\"corrupted pack file\");\n \t}\n \t*sizep = size;\n-\treturn unpack_non_delta_entry(pack, size, left);\n+\tretval = unpack_non_delta_entry(pack, size, left);\n+\tunuse_packed_git(p);\n+\treturn retval;\n }\n \n int num_packed_objects(const struct packed_git *p)\n {\n-\t/* See check_packed_git_idx and pack-objects.c */\n+\t/* See check_packed_git_idx() */\n \treturn (p->index_size - 20 - 20 - 4*256) / 24;\n }\n \ndiff --git a/t/t5300-pack-object.sh b/t/t5300-pack-object.sh\n--- a/t/t5300-pack-object.sh\n+++ b/t/t5300-pack-object.sh\n@@ -127,4 +127,42 @@ test_expect_success \\\n     } >current &&\n     diff expect current'\n \n+unset GIT_OBJECT_DIRECTORY\n+\n+test_expect_success \\\n+    'verify pack' \\\n+    'git-verify-pack test-1.idx test-2.idx'\n+\n+test_expect_success \\\n+    'corrupt a pack and see if verify catches' \\\n+    'cp test-1.idx test-3.idx &&\n+     cp test-2.pack test-3.pack &&\n+     if git-verify-pack test-3.idx\n+     then false\n+     else :;\n+     fi &&\n+\n+     cp test-1.pack test-3.pack &&\n+     dd if=/dev/zero of=test-3.pack count=1 bs=1 conv=notrunc seek=2 &&\n+     if git-verify-pack test-3.idx\n+     then false\n+     else :;\n+     fi &&\n+\n+     cp test-1.pack test-3.pack &&\n+     dd if=/dev/zero of=test-3.pack count=1 bs=1 conv=notrunc seek=7 &&\n+     if git-verify-pack test-3.idx\n+     then false\n+     else :;\n+     fi &&\n+\n+     cp test-1.pack test-3.pack &&\n+     dd if=/dev/zero of=test-3.pack count=1 bs=1 conv=notrunc seek=12 &&\n+     if git-verify-pack test-3.idx\n+     then false\n+     else :;\n+     fi &&\n+\n+     :'\n+\n test_done\ndiff --git a/verify-pack.c b/verify-pack.c\nnew file mode 100644\n--- /dev/null\n+++ b/verify-pack.c\n@@ -0,0 +1,26 @@\n+#include \"cache.h\"\n+#include \"pack.h\"\n+\n+static int verify_one_pack(char *arg)\n+{\n+\tstruct packed_git *g = add_packed_git(arg, strlen(arg));\n+\tif (!g)\n+\t\treturn -1;\n+\treturn verify_pack(g);\n+}\n+\n+int main(int ac, char **av)\n+{\n+\tint errs = 0;\n+\n+\twhile (1 < ac) {\n+\t\tchar path[PATH_MAX];\n+\t\tstrcpy(path, av[1]);\n+\t\tif (verify_one_pack(path))\n+\t\t\terrs++;\n+\t\telse\n+\t\t\tprintf(\"%s: OK\\n\", av[1]);\n+\t\tac--; av++;\n+\t}\n+\treturn !!errs;\n+}\ndiff --git a/verify_pack.c b/verify_pack.c\nnew file mode 100644\n--- /dev/null\n+++ b/verify_pack.c\n@@ -0,0 +1,62 @@\n+#include \"cache.h\"\n+#include \"pack.h\"\n+\n+static int verify_packfile(struct packed_git *p)\n+{\n+\tunsigned long index_size = p->index_size;\n+\tvoid *index_base = p->index_base;\n+\tSHA_CTX ctx;\n+\tunsigned char sha1[20];\n+\tunsigned long pack_size = p->pack_size;\n+\tvoid *pack_base;\n+\tstruct pack_header *hdr;\n+\tint nr_objects;\n+\n+\thdr = p->pack_base;\n+\tif (hdr->hdr_signature != htonl(PACK_SIGNATURE))\n+\t\treturn error(\"Packfile signature mismatch\", p->pack_name);\n+\tif (hdr->hdr_version != htonl(PACK_VERSION))\n+\t\treturn error(\"Packfile version %d different from ours %d\",\n+\t\t\t     ntohl(hdr->hdr_version), PACK_VERSION);\n+\tnr_objects = ntohl(hdr->hdr_entries);\n+\tif (num_packed_objects(p) != nr_objects)\n+\t\treturn error(\"Packfile claims to have %d objects, \"\n+\t\t\t     \"while idx size expects %d\", nr_objects,\n+\t\t\t     num_packed_objects(p));\n+\n+\tSHA1_Init(&ctx);\n+\tpack_base = p->pack_base;\n+\tSHA1_Update(&ctx, pack_base, pack_size - 20);\n+\tSHA1_Final(sha1, &ctx);\n+\tif (memcmp(sha1, index_base + index_size - 40, 20))\n+\t\treturn error(\"Packfile %s SHA1 mismatch with idx\",\n+\t\t\t     p->pack_name);\n+\tif (memcmp(sha1, pack_base + pack_size - 20, 20))\n+\t\treturn error(\"Packfile %s SHA1 mismatch with itself\",\n+\t\t\t     p->pack_name);\n+\treturn 0;\n+}\n+\n+\n+int verify_pack(struct packed_git *p)\n+{\n+\tunsigned long index_size = p->index_size;\n+\tvoid *index_base = p->index_base;\n+\tSHA_CTX ctx;\n+\tunsigned char sha1[20];\n+\tint ret;\n+\n+\t/* Verify SHA1 sum of the index file */\n+\tSHA1_Init(&ctx);\n+\tSHA1_Update(&ctx, index_base, index_size - 20);\n+\tSHA1_Final(sha1, &ctx);\n+\tif (memcmp(sha1, index_base + index_size - 20, 20))\n+\t\treturn error(\"Packfile index for %s SHA1 mismatch\",\n+\t\t\t     p->pack_name);\n+\n+\t/* Verify pack file */\n+\tuse_packed_git(p);\n+\tret = verify_packfile(p);\n+\tunuse_packed_git(p);\n+\treturn ret;\n+}\n------------\n"},{"id":"5416","messageId":"Pine.LNX.4.58.0506290911590.14331@ppc970.osdl.org","threadId":"1022","inReplyTo":"7vvf3xcwyo.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Add git-verify-pack command.","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-06-29T16:15:48Z","receivedAt":"2005-06-29T16:15:48Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 29 Jun 2005, Junio C Hamano wrote:\n> \n> *** Linus, what would be the practical/recommended/sane limit\n> *** for mmap regions we would want to use?  Currently I start\n> *** throwing away mapped packs when the total size of mapped\n> *** packs exceeds 64MB.\n\nHey, anybody who ever used BK had better have had 1GB of memory for any \nreal development. So 64MB is peanuts, but it sounds like a good guess.\n\n> *** Oh, again, Linus, what is your preferred way to get a\n> *** cover-letter material (like this) for a single patch?\n\nI don't want cover-letters for single patches, or necessarily even for\nshort series (1-3 entries). The cover letter is more interesting for large\nseries, or even with small series if the early patches don't make much\nsense on their own: then the cover-letter ends up being a useful place to\nexplain what the _sequence_ does, and why patch #2 that seems to be\ntotally useless and removes a feature is actually good (\"we'll\nre-implement it better in #5 after we've cleaned the code up\").\n\nSo generally commentaries after the three dashes is good, if the \ncommentary is \"local\", ie related not to a series. Only with non-local \nexplanations does a separate [0/N] thing make sense to me.\n\n\t\tLinus\n"},{"id":"5647","messageId":"Pine.LNX.4.21.0507041635350.30848-100000@iabervon.org","threadId":"1022","inReplyTo":"7v4qbhfxad.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: Last mile for 1.0 again","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-07-04T21:40:46Z","receivedAt":"2005-07-04T21:40:46Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Wed, 29 Jun 2005, Junio C Hamano wrote:\n\n>  - Blame/Annotate.  Does anybody have a fast and correct one\n\nHow about an option to git-rev-list to take a path, and (1) exclude any\nbranch where the version at that path ends up ignored in a merge and\n(2) not list any revision where the version at that path is identical to a\nparent?\n\nThis should give you the list of all commits which are directly\nresponsible for the present state of the file, which can then be formatted\nas desired.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"5649","messageId":"7vvf3qgs9l.fsf@assigned-by-dhcp.cox.net","threadId":"1022","inReplyTo":"Pine.LNX.4.21.0507041635350.30848-100000@iabervon.org","subject":"Re: Last mile for 1.0 again","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-07-04T21:45:10Z","receivedAt":"2005-07-04T21:45:10Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"DB\" == Daniel Barkalow <barkalow@iabervon.org> writes:\n\nDB> On Wed, 29 Jun 2005, Junio C Hamano wrote:\n>> - Blame/Annotate.  Does anybody have a fast and correct one\n\nDB> How about an option to git-rev-list to take a path, and (1) exclude any\nDB> branch where the version at that path ends up ignored in a merge and\nDB> (2) not list any revision where the version at that path is identical to a\nDB> parent?\n\nDB> This should give you the list of all commits which are directly\nDB> responsible for the present state of the file, which can then be formatted\nDB> as desired.\n\nSounds close enough if you do not care about copies and\ncomplete rewrites.\n"},{"id":"5650","messageId":"Pine.LNX.4.58.0507041459030.3570@g5.osdl.org","threadId":"1022","inReplyTo":"Pine.LNX.4.21.0507041635350.30848-100000@iabervon.org","subject":"Re: Last mile for 1.0 again","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-07-04T21:59:46Z","receivedAt":"2005-07-04T21:59:46Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 4 Jul 2005, Daniel Barkalow wrote:\n> \n> How about an option to git-rev-list to take a path, and (1) exclude any\n> branch where the version at that path ends up ignored in a merge and\n> (2) not list any revision where the version at that path is identical to a\n> parent?\n\nHmm. How is that different from \"git-whatchanged path\", really?\n\n\t\t\tLinus\n"},{"id":"5651","messageId":"Pine.LNX.4.21.0507041801040.30848-100000@iabervon.org","threadId":"1022","inReplyTo":"Pine.LNX.4.58.0507041459030.3570@g5.osdl.org","subject":"Re: Last mile for 1.0 again","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-07-04T22:41:19Z","receivedAt":"2005-07-04T22:41:19Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Mon, 4 Jul 2005, Linus Torvalds wrote:\n\n> On Mon, 4 Jul 2005, Daniel Barkalow wrote:\n> > \n> > How about an option to git-rev-list to take a path, and (1) exclude any\n> > branch where the version at that path ends up ignored in a merge and\n> > (2) not list any revision where the version at that path is identical to a\n> > parent?\n> \n> Hmm. How is that different from \"git-whatchanged path\", really?\n\nIt would short-circuit going up areas of the history which don't\ncontribute (i.e., lead up to a merge which took its version from a\ndifferent parent). It could also stop when it ran out of branches that\nhave the file at all. Neither of these is all that significant, I guess.\n\nJunio: what's missing from annotate/blame?\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"5654","messageId":"7vmzp2gohc.fsf@assigned-by-dhcp.cox.net","threadId":"1022","inReplyTo":"Pine.LNX.4.21.0507041801040.30848-100000@iabervon.org","subject":"Re: Last mile for 1.0 again","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-07-04T23:06:55Z","receivedAt":"2005-07-04T23:06:55Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"DB\" == Daniel Barkalow <barkalow@iabervon.org> writes:\n\nDB> Junio: what's missing from annotate/blame?\n\nWhich one are you talking about?\n\nWhat I use to generate http://members.cox.net/junkio/Summary.txt\nis an implementation of an algorithm I consider \"complete\" in\nthat it does rename/copy and complete rewrite correctly.  What\nis missing from the implementation is efficiency.\n\n------------\n#!/usr/bin/perl -w\n\nuse strict;\n\npackage main;\n$::debug = 0;\n\nsub read_blob {\n    my $sha1 = shift;\n    my $fh = undef;\n    my $result;\n    local ($/) = undef;\n    open $fh, '-|', 'git-cat-file', 'blob', $sha1\n\tor die \"cannot read blob $sha1\";\n    $result = join('', <$fh>);\n    close $fh\n\tor die \"failure while closing pipe to git-cat-file\";\n    return $result;\n}\n\nsub read_diff_raw {\n    my ($parent, $filename) = @_;\n    my $fh = undef;\n    local ($/) = \"\\0\";\n    my @result = (); \n    my ($meta, $status, $sha1_1, $sha1_2, $file1, $file2);\n\n    print STDERR \"* diff-cache --cached $parent $filename\\n\" if $::debug;\n    my $has_changes = 0;\n    open $fh, '-|', 'git-diff-cache', '--cached', '-z', $parent, $filename\n\tor die \"cannot read git-diff-cache $parent $filename\";\n    while (defined ($meta = <$fh>)) {\n\t$has_changes = 1;\n    }\n    close $fh\n\tor die \"failure while closing pipe to git-diff-cache\";\n    if (!$has_changes) {\n\treturn ();\n    }\n\n    $fh = undef;\n    print STDERR \"* diff-cache -B -C --find-copies-harder --cached $parent\\n\" if $::debug;\n    open($fh, '-|', 'git-diff-cache', '-B', '-C', '--find-copies-harder',\n\t '--cached', '-z', $parent)\n\tor die \"cannot read git-diff-cache with $parent\";\n    while (defined ($meta = <$fh>)) {\n\tchomp($meta);\n\t(undef, undef, $sha1_1, $sha1_2, $status) = split(/ /, $meta);\n\t$file1 = <$fh>;\n\tchomp($file1);\n\tif ($status =~ /^[CR]/) {\n\t    $file2 = <$fh>;\n\t    chomp($file2);\n\t} elsif ($status =~ /^D/) {\n\t    next;\n\t} else {\n\t    $file2 = $file1;\n\t}\n\tif ($file2 eq $filename) {\n\t    push @result, [$status, $sha1_1, $sha1_2, $file1, $file2];\n\t}\n    }\n    close $fh\n\tor die \"failure while closing pipe to git-diff-cache\";\n    return @result;\n}\n\nsub write_temp_blob {\n    my ($sha1, $temp) = @_;\n    my $fh = undef;\n    my $blob = read_blob($sha1);\n    open $fh, '>', $temp\n\tor die \"cannot open temporary file $temp\";\n    print $fh $blob;\n    close($fh);\n}\n\npackage Git::Patch;\nsub new {\n    my ($class, $sha1_1, $sha1_2) = @_;\n    my $self = bless [], $class;\n    my $fh = undef;\n    ::write_temp_blob($sha1_1, \"/tmp/blame-$$-1\");\n    ::write_temp_blob($sha1_2, \"/tmp/blame-$$-2\");\n    open $fh, '-|', 'diff', '-u0', \"/tmp/blame-$$-1\", \"/tmp/blame-$$-2\"\n\tor die \"cannot read diff\";\n    while (<$fh>) {\n\tif (/^\\@\\@ -(\\d+)(?:,(\\d+))? \\+(\\d+)(?:,(\\d+))? \\@\\@/) {\n\t    push @$self, [$1, (defined $2 ? $2 : 1),\n\t\t\t  $3, (defined $4 ? $4 : 1)];\n\t}\n    }\n    close $fh;\n    unlink \"/tmp/blame-$$-1\", \"/tmp/blame-$$-2\";\n    return $self;\n}\n\nsub find_parent_line {\n    my ($self, $commit_lineno) = @_;\n    my $ofs = 0;\n    for (@$self) {\n\tmy ($line_1, $len_1, $line_2, $len_2) = @$_;\n\tif ($commit_lineno < $line_2) {\n\t    return $commit_lineno - $ofs;\n\t}\n\tif ($line_2 <= $commit_lineno && $commit_lineno < $line_2 + $len_2) {\n\t    return -1; # changed by commit.\n\t}\n\t$ofs += ($len_1 - $len_2);\n    }\n    return $commit_lineno + $ofs;\n}\n\npackage Git::Commit;\n\nmy %author_name_canon = \n('Linus Torvalds <torvalds@ppc970.osdl.org.(none)>' =>\n 'Linus Torvalds <torvalds@ppc970.osdl.org>');\n\nsub canon_author_name {\n    my ($name) = @_;\n    if (exists $author_name_canon{$name}) {\n\treturn $author_name_canon{$name};\n    }\n    return $name;\n}\n\nsub new {\n    my $class = shift;\n    my $self = bless {\n\tPARENT => [],\n\tTREE => undef,\n\tAUTHOR => undef,\n\tCOMMITTER => undef,\n    }, $class;\n    my $commit_sha1 = shift;\n    $self->{SHA1} = $commit_sha1;\n    my $fh = undef;\n    open $fh, '-|', 'git-cat-file', 'commit', $commit_sha1\n\tor die \"cannot read commit object $commit_sha1\";\n    while (<$fh>) {\n\tchomp;\n\tif (/^tree ([0-9a-f]{40})$/) { $self->{TREE} = $1; }\n\telsif (/^parent ([0-9a-f]{40})$/) { push @{$self->{PARENT}}, $1; }\n\telsif (/^author ([^>]+>)/) {\n\t    $self->{AUTHOR} = canon_author_name($1);\n\t}\n\telsif (/^committer ([^>]+>)/) {\n\t    $self->{COMMITTER} = canon_author_name($1);\n\t}\n    }\n    close $fh\n\tor die \"failure while closing pipe to git-cat-file\";\n    return $self;\n}\n\nsub find_file {\n    my ($commit, $path) = @_;\n    my $result = undef;\n    my $fh = undef;\n    local ($/) = \"\\0\";\n    open $fh, '-|', 'git-ls-tree', '-z', '-r', '-d', $commit->{TREE}, $path\n\tor die \"cannot read git-ls-tree $commit->{TREE}\";\n    while (<$fh>) {\n\tchomp;\n\tif (/^[0-7]{6} blob ([0-9a-f]{40})\t(.*)$/) {\n\t    if ($2 ne $path) {\n\t\tdie \"$2 ne $path???\";\n\t    }\n\t    $result = $1;\n\t    last;\n\t}\n    }\n    close $fh\n\tor die \"failure while closing pipe to git-ls-tree\";\n    return $result;\n}\n\npackage Git::Blame;\nsub new {\n    my $class = shift;\n    my $self = bless {\n\tLINE => [],\n\tUNKNOWN => undef,\n\tWORK => [],\n    }, $class;\n    my $commit = shift;\n    my $filename = shift;\n    my $sha1 = $commit->find_file($filename);\n    my $blob = ::read_blob($sha1);\n    my @blob = (split(/\\n/, $blob));\n    for (my $i = 0; $i < @blob; $i++) {\n\t$self->{LINE}[$i] = +{\n\t    COMMIT => $commit,\n\t    FOUND => undef,\n\t    FILENAME => $filename,\n\t    LINENO => ($i + 1),\n\t};\n    }\n    $self->{UNKNOWN} = scalar @blob;\n    push @{$self->{WORK}}, [$commit, $filename];\n    return $self;\n}\n\nsub read_blame_cache {\n    my $self = shift;\n    my $filename = shift;\n    my $fh = undef;\n    my $pi = $self->{'PATHINFO'} = {};\n    open $fh, '<', $filename;\n    while (<$fh>) {\n\tchomp;\n\tmy ($commit, $parent, $path) = split(/\\t/, $_);\n\t$pi->{$path}{$commit}{$parent} = 1;\n    }\n    close $fh;\n}\n\nsub print {\n    my $self = shift;\n    my $line_termination = shift;\n    for (my $i = 0; $i < @{$self->{LINE}}; $i++) {\n\tmy $l = $self->{LINE}[$i];\n\tprint ($l->{FOUND} ? ':' : '?');;\n\tprint \"$l->{COMMIT}->{SHA1}\t\";\n\tprint \"$l->{COMMIT}->{AUTHOR}\t\";\n\tprint \"$l->{COMMIT}->{COMMITTER}\t\";\n\tprint \"$l->{LINENO}\t$l->{FILENAME}\";\n\tprint $line_termination;\n    }\n}\n\nsub take_responsibility {\n    my ($self, $commit) = @_;\n    for (my $i = 0; $i < @{$self->{LINE}}; $i++) {\n\tmy $l = $self->{LINE}[$i];\n\tif (! $l->{FOUND} && ($l->{COMMIT}->{SHA1} eq $commit->{SHA1})) {\n\t    $l->{FOUND} = 1;\n\t    $self->{UNKNOWN}--;\n\t}\n    }\n}\n\nsub blame_parent {\n    my ($self, $commit, $parent, $filename) = @_;\n    my @diff = ::read_diff_raw($parent->{SHA1}, $filename);\n    my $filename_in_parent;\n    my $passed_blame_to_parent = undef;\n    if (@diff == 0) {\n\t# We have not touched anything.  Blame parent for everything\n\t# that we are suspected for.\n\tfor (my $i = 0; $i < @{$self->{LINE}}; $i++) {\n\t    my $l = $self->{LINE}[$i];\n\t    if (! $l->{FOUND} && ($l->{COMMIT}->{SHA1} eq $commit->{SHA1})) {\n\t\t$l->{COMMIT} = $parent;\n\t\t$passed_blame_to_parent = 1;\n\t    }\n\t}\n\t$filename_in_parent = $filename;\n    }\n    elsif (@diff != 1) {\n\t# This should not happen.\n\tfor (@diff) {\n\t    print \"** @$_\\n\";\n\t}\n\tdie \"Oops\";\n    }\n    else {\n\tmy ($status, $sha1_1, $sha1_2, $file1, $file2) = @{$diff[0]};\n\tprint STDERR \"** $status $file1 $file2\\n\" if $::debug;\n\tif ($status =~ /N/ || $status =~ /M[0-9][0-9]/) {\n\t    # Either some of other parents created it, or we did.\n\t    # At this point the only thing we know is that this\n\t    # parent is not responsible for it.\n\t    ;\n\t}\n\telse {\n\t    my $patch = Git::Patch->new($sha1_1, $sha1_2);\n\t    $filename_in_parent = $file1;\n\t    for (my $i = 0; $i < @{$self->{LINE}}; $i++) {\n\t\tmy $l = $self->{LINE}[$i];\n\t\tif (! $l->{FOUND} && $l->{COMMIT}->{SHA1} eq $commit->{SHA1}) {\n\t\t    # We are suspected to have introduced this line.\n\t\t    # Does it exist in the parent?\n\t\t    my $lineno = $l->{LINENO};\n\t\t    my $parent_line = $patch->find_parent_line($lineno);\n\t\t    if ($parent_line < 0) {\n\t\t\t# No, we may be the guilty ones, or some other\n\t\t\t# parent might be.  We do not assign blame to\n\t\t\t# ourselves here yet.\n\t\t\t;\n\t\t    }\n\t\t    else {\n\t\t\t# This line is coming from the parent, so pass\n\t\t\t# blame to it.\n\t\t\t$l->{COMMIT} = $parent;\n\t\t\t$l->{FILENAME} = $file1;\n\t\t\t$l->{LINENO} = $parent_line;\n\t\t\t$passed_blame_to_parent = 1;\n\t\t    }\n\t\t}\n\t    }\n\t}\n    }\n    if ($passed_blame_to_parent && $self->{UNKNOWN}) {\n\tunshift @{$self->{WORK}},\n\t[$parent, $filename_in_parent];\n    }\n}\n\nsub assign {\n    my ($self, $commit, $filename) = @_;\n    # We do read-tree of the current commit and diff-cache\n    # with each parents, instead of running diff-tree.  This\n    # is because diff-tree does not look for copies hard enough.\n\n    if (exists $self->{'PATHINFO'} && exists $self->{'PATHINFO'}{$filename} &&\n\t!exists $self->{'PATHINFO'}{$filename}{$commit->{SHA1}} &&\n\t@{$commit->{PARENT}} == 1) {\n\t# This commit did not touch the path at all, and\n\t# has only one parent.  It is all that parent's fault.\n\n\tmy $parent = Git::Commit->new($commit->{PARENT}[0]);\n\tmy $passed_blame_to_parent = 0;\n\tfor (my $i = 0; $i < @{$self->{LINE}}; $i++) {\n\t    my $l = $self->{LINE}[$i];\n\t    if (! $l->{FOUND} &&\n\t\t($l->{COMMIT}->{SHA1} eq $commit->{SHA1})) {\n\t\t$l->{COMMIT} = $parent;\n\t\t$passed_blame_to_parent = 1;\n\t    }\n\t}\n\tif ($passed_blame_to_parent && $self->{UNKNOWN}) {\n\t    unshift @{$self->{WORK}},\n\t    [$parent, $filename];\n\t}\n\treturn;\n    }\n\n    print STDERR \"* read-tree  $commit->{SHA1}\\n\" if $::debug;\n    system('git-read-tree', '-m', $commit->{SHA1});\n    for my $parent (@{$commit->{PARENT}}) {\n\t$self->blame_parent($commit, Git::Commit->new($parent), $filename);\n    }\n    $self->take_responsibility($commit);\n}\n\nsub assign_blame {\n    my ($self) = @_;\n    while ($self->{UNKNOWN} && @{$self->{WORK}}) {\n\tmy $wk = shift @{$self->{WORK}};\n\tmy ($commit, $filename) = @$wk;\n\t$self->assign($commit, $filename);\n    }\n}\n\n\n\n################################################################\npackage main;\nmy $usage = \"blame [-z] <commit> filename\";\nmy $line_termination = \"\\n\";\n\n$::ENV{GIT_INDEX_FILE} = \"/tmp/blame-$$-index\";\nunlink($::ENV{GIT_INDEX_FILE});\n\nif ($ARGV[0] eq '-z') {\n    $line_termination = \"\\0\";\n    shift;\n}\n\nif (@ARGV != 2) {\n    die $usage;\n}\n\nmy $head_commit = Git::Commit->new($ARGV[0]);\nmy $filename = $ARGV[1];\nmy $blame = Git::Blame->new($head_commit, $filename);\nif (-f \".blame-cache\") {\n    $blame->read_blame_cache(\".blame-cache\");\n}\n\n$blame->assign_blame();\n$blame->print($line_termination);\n\nunlink($::ENV{GIT_INDEX_FILE});\n\n__END__\n\nHow does this work, and what do we do about merges?\n\nThe algorithm considers that the first parent is our main line of\ndevelopment and treats it somewhat special than other parents.  So we\npass on the blame to the first parent if a line has not changed from\nit.  For lines that have changed from the first parent, we must have\neither inherited that change from some other parent, or it could have\nbeen merge conflict resolution edit we did on our own.\n\nThe following picture illustrates how we pass on and assign blames.\n\nIn the sample, the original O was forked into A and B and then merged\ninto M.  Line 1, 2, and 4 did not change.  Line 3 and 5 are changed in\nA, and Line 5 and 6 are changed in B.  M made its own decision to\nresolve merge conflicts at Line 5 to something different from A and B:\n\n                A: 1 2 T 4 T 6\n               /               \\ \nO: 1 2 3 4 5 6                  M: 1 2 T 4 M S\n               \\               / \n                B: 1 2 3 4 S S\n\nIn the following picture, each line is annotated with a blame letter.\nA lowercase blame (e.g. \"a\" for \"1\") means that commit or its ancestor\nis the guilty party but we do not know which particular ancestor is\nresponsible for the change yet.  An uppercase blame means that we know\nthat commit is the guilty party.\n\nFirst we look at M (the HEAD) and initialize Git::Blame->{LINE} like\nthis:\n\n             M: 1 2 T 4 M S\n                m m m m m m\n\nThat is, we know all lines are results of modification made by some\nancestor of M, so we assign lowercase 'm' to all of them.\n\nThen we examine our first parent A.  Throughout the algorithm, we are\nalways only interested in the lines we are the suspect, but this being\nthe initial round, we are the suspect for all of them.  We notice that\n1 2 T 4 are the same as the parent A, so we pass the blame for these\nfour lines to A.  M and S are different from A, so we leave them as\nthey are (note that we do not immediately take the blame for them):\n\n             M: 1 2 T 4 M S\n                a a a a m m\n\nNext we go on to examine parent B.  Again, we are only interested in\nthe lines we are still the suspect (i.e. M and S).  We notice S is\nsomething we inherited from B, so we pass the blame on to it, like\nthis:\n\n             M: 1 2 T 4 M S\n                a a a a m b\n\nOnce we exhausted the parents, we look at the results and take\nresponsibility for the remaining ones that we are still the suspect:\n\n             M: 1 2 T 4 M S\n                a a a a M b\n\nWe are done with M.  And we know commits A and B need to be examined\nfurther, so we do them recursively.  When we look at A, we again only\nlook at the lines that A is the suspect:\n\n             A: 1 2 T 4 T 6\n                a a a a M b\n\nAmong 1 2 T 4, comparing against its parent O, we notice 1 2 4 are\nthe same so pass the blame for those lines to O:\n\n             A: 1 2 T 4 T 6\n                o o a o M b\n\nA is a non-merge commit; we have already exhausted the parents and\ntake responsibility for the remaining ones that A is the suspect:\n\n             A: 1 2 T 4 T 6\n                o o A o M b\n\nWe go on like this and the final result would become:\n\n             O: 1 2 3 4 5 6\n                O O A O M B\n"},{"id":"5657","messageId":"Pine.LNX.4.21.0507042137300.30848-100000@iabervon.org","threadId":"1022","inReplyTo":"7vmzp2gohc.fsf@assigned-by-dhcp.cox.net","subject":"Re: Last mile for 1.0 again","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-07-05T01:54:07Z","receivedAt":"2005-07-05T01:54:07Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Mon, 4 Jul 2005, Junio C Hamano wrote:\n\n> >>>>> \"DB\" == Daniel Barkalow <barkalow@iabervon.org> writes:\n> \n> DB> Junio: what's missing from annotate/blame?\n> \n> Which one are you talking about?\n> \n> What I use to generate http://members.cox.net/junkio/Summary.txt\n> is an implementation of an algorithm I consider \"complete\" in\n> that it does rename/copy and complete rewrite correctly.  What\n> is missing from the implementation is efficiency.\n\n[perl script]\n\n> How does this work, and what do we do about merges?\n\nI've got that part, but I'm not clear on how the rename/copy and complete\nrewrite stuff works.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"5659","messageId":"7v3bqthiso.fsf@assigned-by-dhcp.cox.net","threadId":"1022","inReplyTo":"Pine.LNX.4.21.0507042137300.30848-100000@iabervon.org","subject":"Re: Last mile for 1.0 again","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-07-05T06:24:23Z","receivedAt":"2005-07-05T06:24:23Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":">>>>> \"DB\" == Daniel Barkalow <barkalow@iabervon.org> writes:\n\nDB> [perl script]\n\n>> How does this work, and what do we do about merges?\n\nDB> I've got that part, but I'm not clear on how the rename/copy and complete\nDB> rewrite stuff works.\n\nRename/copy is simply about what files to use when comparing\nbetween two trees.  If you are tracking file F and find that a\ncommit created that file by renaming what was originally G, then\nyou compare old G and this F and assign blame for common lines\nto the ancestor of that commit (that had those lines in G), and\ntake responsibility of the rest yourself (or assign blame for\nthem to other parents).\n\nRewrite is easier.  If diff-tree -B says it is a complete\nrewrite, instead of assigning blame for lines that you are the\ncurrent suspect to any of your parents, you take blame for all\nof them yourself, without comparing the file with the parent to\nassign blame line-by-line.\n"},{"id":"5666","messageId":"20050705133448.21778.qmail@web26309.mail.ukl.yahoo.com","threadId":"1022","inReplyTo":"7v3bqthiso.fsf@assigned-by-dhcp.cox.net","subject":"Re: Last mile for 1.0 again","fromName":"Marco Costalba","fromEmail":"mcostalba@yahoo.it","sentAt":"2005-07-05T13:34:48Z","receivedAt":"2005-07-05T13:34:48Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"\n\n--- Junio C Hamano <junkio@cox.net> wrote:\n\n> >>>>> \"DB\" == Daniel Barkalow <barkalow@iabervon.org> writes:\n> \n> DB> [perl script]\n> \n> >> How does this work, and what do we do about merges?\n> \n\nChecking diffs of all the parents can be computational expensive. \n\nI'am developing a different alghoritm for qgit, where I know,\nbefore to run annotate all the revs that changed a given file.\n\nThe revs are saved in the shaHist list according to git-rev-list --merge-order.\n\nThe algoritm operates form the oldest to the newst calculating annotation for each \nfollowing rev.\n\nThis alghoritm takes advantage of the fact that mostly revs belong to 2 categories:\n\n1) revs of the same development-sequence (e.g. connected without merges)\n\n2) empty merges, i.e. merges where the file we are interested in\n is listed in only one merging branch\n\nIf a rev in shaHist does not belong to above categories a reach analisys must be performed\nin order to find the direct ancestor among all the previous revs in the list.\n\n\nSo starting from shaHist a ReachList rl is populated by getReachability(): \n\n\nvoid Annotate::getReachability(ReachList& rl, const QString& file, const QStringList& shaHist) {\n\n\trl.clear();\n\tQStringList::const_iterator it = shaHist.begin();\n\tRev* r = revLookup(*it);\n\trl.append(ReachInfo(*it, r->id, INITIAL));\n\tfor (it++; it != shaHist.end(); it++) {\n\t\t\n\t\tRev* r = revLookup(*it);\n\n\t\t// initial revision case\n\t\tif (r->parents.count() == 0) {\n\t\t\trl.append(ReachInfo(*it, r->id, INITIAL));\n\t\t\tcontinue;\n\t\t}\n\t\t// merge case\n\t\tif (r->parents.count() > 1) { \n\n\t\t\t// check empty merges diffing against previous in list\n\t\t\tQString prevSha = rl.last().sha;\n\t\t\tQString d = getFileDiff(*it, prevSha, file);\n\n\t\t\tif (d.isEmpty()) { \n\t\t\t\trl.append(ReachInfo(*it, r->id, EMPTY_MERGE));\n\t\t\t\trl.last().roots.append(prevSha);\n\t\t\t} else {\n\t\t\t\t// real merge: we need reach test.\n\t\t\t\tQStringList roots;\n\t\t\t\troots.clear();\n\t\t\t\tfor (uint i = 0; i < r->parents.count(); i++) {\n\n\t\t\t\t\t// here tree walking is performed\n\t\t\t\t\tQString root = getRoot(r->parents[i], rl);\t\t\t\t\n\t\t\t\t\tif (!root.isEmpty())\n\t\t\t\t\t\troots.append(root);\n\t\t\t\t}\n\t\t\t\trl.append(ReachInfo(*it, r->id, MERGE));\n\t\t\t\trl.last().roots = roots;\n\t\t\t\t}\n\t\t\t}\n\t\t\tcontinue;\n\t\t}\n\t\t// normal case: a revision with a single parent\n\t\tif (r->id == rl.last().id) { // same development sequence\n\n\t\t\tQString prevSha = rl.last().sha;\n\t\t\trl.append(ReachInfo(*it, r->id, SAME_BR)); // same branch\n\t\t\trl.last().roots.append(prevSha);\n\n\t\t} else { // different development sequence\n\n\t\t\tQString root = getRoot(*it, rl); // <-- here tree walking is performed\n\t\t\tif (!root.isEmpty()) {\n\t\t\t\trl.append(ReachInfo(*it, r->id, DIFF_BR));\n\t\t\t\trl.last().roots.append(root);\n\t\t\t} else\n\t\t\t\tqDebug(\"ASSERT getReachability: rev %s not reachable\",\n\t\t\t\t\t(*it).latin1());\n\t\t}\n\t}\n}\n\n\nThen ReachList rl is then used to compute correct annotations:\n\n\nvoid Annotate::run(const QString& file, const QStringList& shaHist, AnnotateHistory& ah) {\n\n\tQString d, diffTarget;\n\tQStringList t;\n\tint pos;\n\tReachList rl;\n\tah.clear();\n\n\tgetReachability(rl, file, shaHist);  // <-- here ReachList rl is calculated\n\n\tfor (uint i = 0; i < rl.count(); i++) {\n\n\t\tswitch(rl[i].type) { // <-- here ReachList rl is used to find annotations\n\n\t\tcase SAME_BR:\n\t\tcase DIFF_BR:\n\t\t\tdiffTarget = rl[i].roots.first();\n\t\t\td = getFileDiff(rl[i].sha, diffTarget, file);\n\t\t\tpos = shaHist.findIndex(diffTarget);\n\t\t\tah.append(processDiff(d, ah[pos], getAuthor(rl[i].sha, shaHist)));\n\t\t\tbreak;\n\t\tcase INITIAL:\n\t\t\tpos = shaHist.findIndex(rl[i].sha);\n\t\t\tah.append(getFirstAnnotation(file, shaHist, pos));\n\t\t\tbreak;\n\t\tcase EMPTY_MERGE:\n\t\t\tdiffTarget = rl[i].roots.first();\n\t\t\tpos = shaHist.findIndex(diffTarget);\n\t\t\tt = ah[pos]; // copy annotation from previous\n\t\t\tah.append(t);\n\t\t\tbreak;\n\t\tcase MERGE:\n\t\t\t// append annotation calculated on first root\n\t\t\tdiffTarget = rl[i].roots.first();\n\t\t\td = getFileDiff(rl[i].sha, diffTarget, file);\n\t\t\tpos = shaHist.findIndex(diffTarget);\n\t\t\tah.append(processDiff(d, ah[pos], \"Merge\"));\n\n\t\t\t// update annotation with all the others roots\n\t\t\tfor (uint j = 1; j < rl[i].roots.count(); j++) {\n\n\t\t\t\tdiffTarget = rl[i].roots[j];\n\t\t\t\td = getFileDiff(rl[i].sha, diffTarget, file);\n\t\t\t\tpos = shaHist.findIndex(diffTarget);\n\n\t\t\t\t// create an annotation calculated between root[i] and\n\t\t\t\t// the merge.\n\t\t\t\tQStringList scndAnn = processDiff(d, ah[pos],\n\t\t\t\t\t\t getAuthor(diffTarget, shaHist));\n\n\t\t\t\t// finally we unify the two annotations, so we catch\n\t\t\t\t// also the case of a 3-way merge\n\t\t\t\tunify(ah.last(), scndAnn);\n\t\t\t}\n\t\t\tbreak;\n\t\t}\n\t}\n}\n\n\nAdvantage of this algorithm is that reach analisys, i.e. tree walking, is\ndone, statistically, only for a small subset of revs.\n\nAnother side benefit is that correct annotation is calculated for each rev and\nnot only for newest one.\n\nOf course there are issues:\n\n1) A ordered list of revs (file history) must be known in advance. This is not a problem\n   for qgit because file history is calculated while loading revs.\n\n2) Does not takes in account file renames.\n\n\nHope this notes can help in ongoing discussion\n\nMarco\n\n\n__________________________________________________\nDo You Yahoo!?\nTired of spam?  Yahoo! Mail has the best spam protection around \nhttp://mail.yahoo.com \n"}]}