{"thread":{"id":"7384","subject":"Understanding version 4 packs","startedAt":"2007-03-24T20:23:56Z","lastAt":"2007-03-27T06:55:31Z","messageCount":19,"participants":["Peter Eriksen","Nicolas Pitre","Shawn O. Pearce","Linus Torvalds","Jakub Narebski","Marco Costalba"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"37895","messageId":"20070324202356.GA20734@bohr.gbar.dtu.dk","threadId":"7384","inReplyTo":null,"subject":"Understanding version 4 packs","fromName":"Peter Eriksen","fromEmail":"s022018@student.dtu.dk","sentAt":"2007-03-24T20:23:56Z","receivedAt":"2007-03-24T20:23:56Z","isPatch":false,"sender":{"key":"s022018@student.dtu.dk","avatar":null},"body":"Hello Shawn (and Nicolas and other interested parties),\n\nI have been reading the commits in the\ngit://repo.or.cz/git/fastimport.git/ repository (git makes it quite easy\nto see what differs from mainline using \"git log master..pack4\"), and I\nthink, I have understood some of the details.\n\nThe easiest thing to get was the file name table, which is placed in the\nbeginning of the pack (after the header) using the format:\n\n+------------+-------------------------------+\n| NR_ENTRIES |  Compressed file name table   |\n+------------+-------------------------------+\n   4 bytes\n\nThe uncompressed file name table contains NR_ENTRIES entries,\nand looks like this:\n\n+------+--------------+------+------------------------+----\n| MODE |  Full path 1 | MODE |   Full path 2          | ...\n+------+--------------+------+------------------------+----\n 2 bytes   n1 bytes    2 bytes     n2 bytes     \n\nThe table is sorted by path then mode for easy binary lookup, and so\nthat pointers into this table can be compared directly instead of\ncomparing the corresponding paths and modes.\n\nThere is a new tree type called OBJ_DICT_TREE, which looks something\nlike the following:\n\n+-----------------+------------------------------------------------+----\n|  Table offset   |  SHA-1 of the blob corresponding to the path.  | ...\n+-----------------+------------------------------------------------+----\n      6 bytes                     20 bytes\n\nThese new tree objects will remain uncompressed in the pack file, but\nsorted with, and deltaed against other tree objects. All normal tree\nobjects are converted to OBJ_DICT_TREE when packing, and are converted\nback on the fly to callers who need an ordinary OBJ_TREE.\n\nThe index (.idx) files are extended to have a 4 byte pointer to the\noffset of this file name table in the pack file for easy lookup.\n\nThere is something similar with a table of common strings in commit\nobjects (e.g. author and timezone), and a new object OBJ_DICT_COMMIT,\nbut I have not understood that quite yet.\n\nIs there something, I have gotten wrong with regards to my\nunderstanding?\n\nRegards,\n\nPeter\n"},{"id":"37902","messageId":"alpine.LFD.0.83.0703241913110.18328@xanadu.home","threadId":"7384","inReplyTo":"20070324202356.GA20734@bohr.gbar.dtu.dk","subject":"Re: Understanding version 4 packs","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-24T23:24:17Z","receivedAt":"2007-03-24T23:24:17Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 24 Mar 2007, Peter Eriksen wrote:\n\n> There is a new tree type called OBJ_DICT_TREE, which looks something\n> like the following:\n> \n> +-----------------+------------------------------------------------+----\n> |  Table offset   |  SHA-1 of the blob corresponding to the path.  | ...\n> +-----------------+------------------------------------------------+----\n>       6 bytes                     20 bytes\n\nActually it is a 2-byte index in the path table, and a 4-byte index in a \ncommon SHA1 table.  So each tree entry is 6 bytes total.\n\n> These new tree objects will remain uncompressed in the pack file, but\n> sorted with, and deltaed against other tree objects. All normal tree\n> objects are converted to OBJ_DICT_TREE when packing, and are converted\n> back on the fly to callers who need an ordinary OBJ_TREE.\n\nRight.\n\n> The index (.idx) files are extended to have a 4 byte pointer to the\n> offset of this file name table in the pack file for easy lookup.\n\nRight.  And it will lose the SHA1 entries since they are already \navailable in the pack.\n\n> There is something similar with a table of common strings in commit\n> objects (e.g. author and timezone), and a new object OBJ_DICT_COMMIT,\n> but I have not understood that quite yet.\n> \n> Is there something, I have gotten wrong with regards to my\n> understanding?\n\nI don't think so.  Note that the code is still a work in progress and \nthe resulting pack/index is not yet fully conform to the format we \nenvisaged.\n\n\nNicolas\n"},{"id":"37919","messageId":"20070325083530.GA25523@bohr.gbar.dtu.dk","threadId":"7384","inReplyTo":"alpine.LFD.0.83.0703241913110.18328@xanadu.home","subject":"Re: Understanding version 4 packs","fromName":"Peter Eriksen","fromEmail":"s022018@student.dtu.dk","sentAt":"2007-03-25T08:35:30Z","receivedAt":"2007-03-25T08:35:30Z","isPatch":false,"sender":{"key":"s022018@student.dtu.dk","avatar":null},"body":"On Sat, Mar 24, 2007 at 07:24:17PM -0400, Nicolas Pitre wrote:\n> On Sat, 24 Mar 2007, Peter Eriksen wrote:\n> \n> > There is a new tree type called OBJ_DICT_TREE, which looks something\n> > like the following:\n> > \n> > +-----------------+------------------------------------------------+----\n> > |  Table offset   |  SHA-1 of the blob corresponding to the path.  | ...\n> > +-----------------+------------------------------------------------+----\n> >       6 bytes                     20 bytes\n> \n> Actually it is a 2-byte index in the path table, and a 4-byte index in a \n> common SHA1 table.  So each tree entry is 6 bytes total.\n\nWhat happens to the paths, that do not have a correponding entry in the\npath name table, because they are not among the 65535 most frequent\npaths in the pack?\n\n> > The index (.idx) files are extended to have a 4 byte pointer to the\n> > offset of this file name table in the pack file for easy lookup.\n> \n> Right.  And it will lose the SHA1 entries since they are already \n> available in the pack.\n\nDoes this mean, that the current index format will change from:\n\n  - The header is followed by sorted 24-byte entries, one entry\n    per object in the pack.  Each entry is:\n\n    4-byte network byte order integer, recording where the\n    object is stored in the packfile as the offset from the\n    beginning.\n\nto just 4-byte entries, and are the SHA-1 entries in that extra table\nof SHA-1's referenced by OBJ_DICT_TREE objects in the pack file?\n\nRegards,\n\nPeter\n\nP.S. I have updated my description of the pack format. Any comments are\nwelcome.\n\nOn disk format of version 4 packs (v0.1)\n=================================\n\nThere is a file name table, EXT_OBJ_FILENAME_TABLE, which is placed\nanywhere in the pack file, but before any OBJ_DICT_TREE objects, which\nare referencing the table, so that the pack can be easily streamed. It\nis using the format:\n\n+-------------------------------+\n|  Compressed file name table   |\n+-------------------------------+\n\nThe uncompressed file name table contains NR_ENTRIES entries,\nand looks like this:\n\n+------------+------+--------------+------+--------------------+----\n| NR_ENTRIES | MODE |  Full path 1 | MODE | Full path 2        | ...\n+------------+------+--------------+------+--------------------+----\n   4 bytes    2 bytes   n1 bytes    2 bytes     n2 bytes     \n\nMODE is a network-byte-order integer representing the mode of the path,\nand the path is a variable length, null-terminated string.\n\nThe table is sorted by path then mode for easy binary lookup, and so\nthat pointers into this table can be compared directly instead of\ncomparing the corresponding paths and modes. This table contains the\n65535 most used paths in the entire pack.\n\nThere is a new tree type called OBJ_DICT_TREE, which looks like the\nfollowing:\n\n+--------+----------------+----\n| P offs |   SHA-1 offs   | ...\n+--------+----------------+----\n  2 bytes      4 bytes\n\nThat is, each entry contains a 2-byte index into the path table, and a\ncorresponding 4-byte index into a SHA-1 table.\n\nThese new tree objects will remain uncompressed in the pack file, but\nsorted with, and deltaed against other tree objects. All normal tree\nobjects are converted to OBJ_DICT_TREE when packing, and are converted\nback on the fly to callers who need an ordinary OBJ_TREE.\n\nThe index (.idx) files are extended to have a 4 byte pointer to the\noffset of this file name table in the pack file for easy lookup.\n\nThere is something similar with a table, EXT_OBJ_IDENT_TABLE of common\nstrings in commit objects (e.g. author and timezone), and a new object\nOBJ_DICT_COMMIT, but I have not understood that quite yet.\n"},{"id":"37921","messageId":"20070325084641.GG25863@spearce.org","threadId":"7384","inReplyTo":"20070324202356.GA20734@bohr.gbar.dtu.dk","subject":"Re: Understanding version 4 packs","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-25T08:46:41Z","receivedAt":"2007-03-25T08:46:41Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Peter Eriksen <s022018@student.dtu.dk> wrote:\n> I have been reading the commits in the\n> git://repo.or.cz/git/fastimport.git/ repository (git makes it quite easy\n> to see what differs from mainline using \"git log master..pack4\"), and I\n> think, I have understood some of the details.\n\nJust to be clear, that branch is strictly a proposed prototype of\nwhat a pack version 4 *might* look like.  Absolutely nothing has\nbeen set into stone for that file format.\n\nA good chunk of that code needs to be reworked just to get it merged\nonto Junio's current 'master' as Nico and myself have been doing a\nnumber of cleanups and bug fixes in some of the affected areas.  ;-)\n \n> The easiest thing to get was the file name table, which is placed in the\n> beginning of the pack (after the header) using the format:\n\nThat's not true.  The filename table (EXTOBJ_FILENAME_TABLE) may\nappear at any position within the packfile (but like all objects\nit must appear somewhere after position 12, as that is where the\nheader ends).\n\nNow to help out the unpackers (index-pack and unpack-objects)\nwe have the convention that this table is written out before the\nfirst OBJ_DICT_TREE.  That way the unpacker can load the table and\nhave it ready to go when it sees the first OBJ_DICT_TREE.  If we\ndidn't have this rule the unpackers would need to hang into all\nOBJ_DICT_TREEs they see until they get the EXTOBJ_FILENAME_TABLE,\nthen they could actually process those pending OBJ_DICT_TREEs.\nThis is somewhat expensive on memory, and is just ugly to code.\n\nSo what you will find is that the EXTOBJ_FILENAME_TABLE is dumped\nout behind all of the commits, but before the first OBJ_DICT_TREE,\nand since all trees tend to get converted to an OBJ_DICT_TREE,\nthe EXTOBJ_FILENAME_TABLE is sandwiched exactly between the commits\nand the trees.\n\nSince the unpackers will probably never be smart enough to handle an\nOBJ_DICT_TREE before an EXTOBJ_FILENAME_TABLE, its likely that we'll\njust have the file format requirement that the EXTOBJ_FILENAME_TABLE\nmust appear before the first OBJ_DICT_TREE, but can otherwise appear\nat any position in the file.\n\nThe reason we put the EXTOBJ_FILENAME_TABLE behind the commits is\nwe often walk the commit chains (following parent pointers) without\nlooking at the trees at all.  Consider `git log`, in the default\nsettings we don't need the trees.  By keeping the filename table\nbehind the commits the OS read-ahead buffering gets a better chance\nat loading all of the data we need, and none of the data we don't.\n\nSo that's why its where it is.\n\n> +------------+-------------------------------+\n> | NR_ENTRIES |  Compressed file name table   |\n> +------------+-------------------------------+\n>    4 bytes\n\nNo.  A string table object (both the EXTOBJ_FILENAME_TABLE and the\nEXTOBJ_IDENT_TABLE) has its uncompressed size stored in the standard\n\"size\" field within the object header.  (This lets us malloc the\nproper buffer quickly.)  Immediately behind that object header is\nthe deflated table.\n\nThe deflated table looks like:\n\n+------------+-------+-------+-------+--------+----+\n| NR_ENTRIES | MODE1 | str1  | MODE2 | str2   | ...\n+------------+-------+-------+-------+--------+----+\n   4 bytes    2 bytes   n1    2 bytes   n2\n\nThe field NR_ENTRIES is in big-endian (network) byte order.\nEach MODE field is also in big-endian byte order.  Each string is\nnull terminated.  The lengths n1 and n2 in the diagram above would\ninclude the null terminating byte.  There is no end-of-table marker;\nthe way to know the you reach the end of a table is by counting\nNR_ENTRIES records out.\n\nI did consider making NR_ENTRIES a vint (variable length int), but\ndecided against it for the sake of simplicity.  ;-)\n\nFor starters its much easier to just treat the darn thing as a\n32 bit value and use ntohl.  Its also easier in the pack-objects\ncode, as I can reserve that space at the front of the table, as the\nsize is fixed.  Also, since its is actually inside of the deflated\nzlib stream, and null bytes are very common (string terminaters)\nany unnecessary leading nulls will probably compress quite well,\nas the null byte will probably get a relatively short encoding in\nthe compressed stream.\n\nThe MODE fields are the standard POSIX mode bits in an\nEXTOBJ_FILENAME_TABLE.\n\nIn an EXTOBJ_IDENT_TABLE the MODE fields actually store the\npreferred timezone offset (hours in the first/high byte, minutes\nin the second/low byte) of the user whose name/email is stored in\nthe string field.\n\n> The table is sorted by path then mode for easy binary lookup, and so\n> that pointers into this table can be compared directly instead of\n> comparing the corresponding paths and modes.\n\nUh, not quite.\n\nIn the case of EXTOBJ_FILENAME_TABLE we sort by name+type using\nthe messy base_name_compare.  In this sorting string entries whose\nmode match S_ISDIR (are directory modes) sort as though their name\nends with \"/\" (even though they actually don't).  If there is a tie,\nwe break the tie by sorting by the mode alone.\n\nIn the case of EXTOBJ_IDENT_TABLE we plan to sort by frequency of\noccurance only.  This sorting puts the most frequent users at the\nstart of the table, allowing us to reference the top 128 authors\nand committers in just 1 byte, and the next 16,257 top authors and\ncommitters in just 2 bytes (as we use vints to index into here,\nmore later).\n\n> There is a new tree type called OBJ_DICT_TREE, which looks something\n> like the following:\n> \n> +-----------------+------------------------------------------------+----\n> |  Table offset   |  SHA-1 of the blob corresponding to the path.  | ...\n> +-----------------+------------------------------------------------+----\n>       6 bytes                     20 bytes\n\nNo.  As Nico stated the records of an OBJ_DICT_TREE are actually only\n6 bytes each.\n\nActually an OBJ_DICT_TREE is *not* comprssed in the packfile.\nI want to stress this point, as its unlike most other object types\nwhere the data after the header is just a zlib stream.\n\nIts data looks like:\n\n+------------+-------+-------+-------+-------+----\n| NR_ENTRIES | name1 | hash1 | name2 | hash2 | ...\n+------------+-------+-------+-------+-------+----\n vint        2 bytes 4 bytes 2 bytes 4 bytes\n\nThe NR_ENTRIES field is our \"standard\" variable integer encoding\n(the encoding used by OBJ_OFS_DELTA).  It tells us how many tree\nentries to expect.\n\nname1 is an index into the packfile's sole EXTOBJ_FILENAME_TABLE.\nhash1 is an index into the packfile's sole SHA1 table.  This object\ntype hasn't been declared yet, but will be.  Both fields are in\nbig-endian / network byte order.\n \n> These new tree objects will remain uncompressed in the pack file, but\n> sorted with,\n\nYes, correct.\n\n> and deltaed against other tree objects.\n\n*only* against other OBJ_DICT_TREEs.  If a tree could not be\nconverted to an OBJ_DICT_TREE then it stays as an OBJ_TREE and only\ndeltas against other OBJ_TREEs.\n\n> All normal tree\n> objects are converted to OBJ_DICT_TREE when packing,\n\nAlmost.  We try to convert all trees to OBJ_DICT_TREE when packing,\nbut we cannot do so if the EXTOBJ_FILENAME_TABLE does not contain\none or more path/mode pairs required by that tree.  This can happen\nif the EXTOBJ_FILENAME_TABLE would need to contain more than 2**16\nentries, as the index into that table (name1 above) is strictly a\n16 bit unsigned value.\n\nThus we have a rule in pack-objects where we first sort the\nEXTOBJ_FILENAME_TABLE by frequency, clipping it to the top 2**16\nentries, then we resort it according to the name+mode sort.\n\n> and are converted\n> back on the fly to callers who need an ordinary OBJ_TREE.\n\nYes.  But we don't want to actually do that.  One of our\ngoals is to adjust tree-walk.c (and if needed its callers)\nto directly handle an OBJ_DICT_TREE.  This way we can avoid\na lot of costly decompression.\n\nFurther I think we can play a game with the delta encoder and\ndelta apply routines where we can even avoid applying OBJ_DICT_TREE\ndeltas when we are walking the tree; instead we can walk the deltas\ndirectly.\n\nThis is the primary motiviation for keeping the OBJ_DICT_TREE format\na fixed width record, even if it might waste a tiny amount of space\nfor some projects.\n \n> The index (.idx) files are extended to have a 4 byte pointer to the\n> offset of this file name table in the pack file for easy lookup.\n\nYes.  But these may become 64 bit offsets, to allow for very large\npackfiles.\n \n> There is something similar with a table of common strings in commit\n> objects (e.g. author and timezone), and a new object OBJ_DICT_COMMIT,\n> but I have not understood that quite yet.\n\nIts actually EXTOBJ_DICT_COMMIT.\n\nThe idea here is that author and committer strings appear very\ncommonly thoughout a project.  Look at Junio for example in\ngit.git, there are more than 3,000 commits with his name on them.\nThese compress rather poorly, and don't delta against each other\nvery well at all.  By pulling these common strings out to an\nEXTOBJ_IDENT_TABLE we can save some space.\n\nThe other idea is to store the tree and the parent commits in pure\nbinary (so SHA-1s are 20 bytes, not 40 bytes hex) and to avoid text\nheaders, so that we can parse the important fields of a commit that\nare needed for revision walking immediately from the raw pack data.\nSince SHA-1s are uncompressable we aren't actually losing any disk\nspace here either.  Actually in my early experiements (predates the\npackv4 code you looked at) this was saving about 63 bytes per commit.\n\n> Is there something, I have gotten wrong with regards to my\n> understanding?\n\nYou're close.  Not bad for no documentation!  ;-)\n\n-- \nShawn.\n"},{"id":"37925","messageId":"20070325091806.GH25863@spearce.org","threadId":"7384","inReplyTo":"20070325083530.GA25523@bohr.gbar.dtu.dk","subject":"Re: Understanding version 4 packs","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-25T09:18:07Z","receivedAt":"2007-03-25T09:18:07Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Peter Eriksen <s022018@student.dtu.dk> wrote:\n> On Sat, Mar 24, 2007 at 07:24:17PM -0400, Nicolas Pitre wrote:\n> > On Sat, 24 Mar 2007, Peter Eriksen wrote:\n> > \n> > > There is a new tree type called OBJ_DICT_TREE, which looks something\n> > > like the following:\n> > > \n> > > +-----------------+------------------------------------------------+----\n> > > |  Table offset   |  SHA-1 of the blob corresponding to the path.  | ...\n> > > +-----------------+------------------------------------------------+----\n> > >       6 bytes                     20 bytes\n> > \n> > Actually it is a 2-byte index in the path table, and a 4-byte index in a \n> > common SHA1 table.  So each tree entry is 6 bytes total.\n> \n> What happens to the paths, that do not have a correponding entry in the\n> path name table, because they are not among the 65535 most frequent\n> paths in the pack?\n\nThey don't appear in the table.  And any tree that uses them is\nforced to use the \"legacy\" OBJ_TREE encoding.  Which is what we\nhave now in pack v2, and in loose objects.\n \n> > > The index (.idx) files are extended to have a 4 byte pointer to the\n> > > offset of this file name table in the pack file for easy lookup.\n> > \n> > Right.  And it will lose the SHA1 entries since they are already \n> > available in the pack.\n> \n> Does this mean, that the current index format will change from:\n> \n>   - The header is followed by sorted 24-byte entries, one entry\n>     per object in the pack.  Each entry is:\n> \n>     4-byte network byte order integer, recording where the\n>     object is stored in the packfile as the offset from the\n>     beginning.\n> \n> to just 4-byte entries, and are the SHA-1 entries in that extra table\n> of SHA-1's referenced by OBJ_DICT_TREE objects in the pack file?\n\nor 8 byte entries (for 64 bit offsets, handling larger files).\nBut yes.\n\nWe will also still store the fan-out table at the start of the index,\nas its very useful at runtime when reading the packfile for random\naccess, but isn't required for accurate encoding/decoding of the\ndata in the packfile.\n\n> On disk format of version 4 packs (v0.1)\n> =================================\n> \n> There is a file name table, EXT_OBJ_FILENAME_TABLE, which is placed\n> anywhere in the pack file, but before any OBJ_DICT_TREE objects, which\n> are referencing the table, so that the pack can be easily streamed. It\n> is using the format:\n> \n> +-------------------------------+\n> |  Compressed file name table   |\n> +-------------------------------+\n> \n> The uncompressed file name table contains NR_ENTRIES entries,\n> and looks like this:\n> \n> +------------+------+--------------+------+--------------------+----\n> | NR_ENTRIES | MODE |  Full path 1 | MODE | Full path 2        | ...\n> +------------+------+--------------+------+--------------------+----\n>    4 bytes    2 bytes   n1 bytes    2 bytes     n2 bytes     \n> \n> MODE is a network-byte-order integer representing the mode of the path,\n> and the path is a variable length, null-terminated string.\n\nYes so far.\n \n> The table is sorted by path then mode for easy binary lookup, and so\n> that pointers into this table can be compared directly instead of\n> comparing the corresponding paths and modes. This table contains the\n> 65535 most used paths in the entire pack.\n\nSee my prior email about the sorting.  But yes.\n\n> There is a new tree type called OBJ_DICT_TREE, which looks like the\n> following:\n> \n> +--------+----------------+----\n> | P offs |   SHA-1 offs   | ...\n> +--------+----------------+----\n>   2 bytes      4 bytes\n\nSee my prior email; there's also that pesky record count at the start.\n\n> That is, each entry contains a 2-byte index into the path table, and a\n> corresponding 4-byte index into a SHA-1 table.\n> \n> These new tree objects will remain uncompressed in the pack file, but\n> sorted with, and deltaed against other tree objects. All normal tree\n> objects are converted to OBJ_DICT_TREE when packing, and are converted\n> back on the fly to callers who need an ordinary OBJ_TREE.\n\nYup, but see my prior email as there's also the rule that OBJ_DICT_TREE\ncannot delta against an OBJ_TREE (or vice-versa).\n\n> The index (.idx) files are extended to have a 4 byte pointer to the\n> offset of this file name table in the pack file for easy lookup.\n> \n> There is something similar with a table, EXT_OBJ_IDENT_TABLE of common\n> strings in commit objects (e.g. author and timezone), and a new object\n> OBJ_DICT_COMMIT, but I have not understood that quite yet.\n\nOBJ_DICT_COMMIT is rather simple:\n\n - stored uncompressed, like OBJ_DICT_TREE\n\n+---------+------+-------+------------+-------------+-------------+-----\n| RAW_LEN | tree | flags | parents... | commit_time | author_time | ...\n+---------+------+-------+------------+-------------+-------------+-----\n  vint     idref  1 byte   idref * n   4 bytes       4 bytes\n\nHere RAW_LEN is the total length of this commit when its in its\nstandard raw format, the one that is used to compute the SHA-1.\nThis helps the decoder when we need to recreate a normal commit.\nWe store this a vint just because we can.\n\nThe tree and parent idrefs are currently full 20-byte SHA-1s,\nbut these are likely to change to 4 byte SHA-1 indexes like in\nan OBJ_DICT_TREE.\n\nThe flags field is actually 3 fields crammed into 1 byte:\n\n  flags & 128 == if set, the author_time == commit_time and the\n  author_time field is not present in the stream;\n\n  flags & 64 == if set, the author == committer and the author ident\n  field is not present in the stream;\n\n  flags & 63 == number of parent idrefs (n above).  May be 0.\n  I'm actually considering making this flags & 31, leaving ourselves\n  a spare bit for the future.  Why?  You can't make a commit with\n  more than 16 parents right now.\n\nNow after the n parent idrefs (again, 20-byte SHA-1 but could also\nbe the 4 byte SHA-1 indexes) we always have the commit_time field,\nand optionally the author_time field (if flags & 128 == 0).\n\n [sidenote: after re-reading this, I don't like the definition of\n  flags & 128 == 1 implying there is 4 bytes *less* data in the\n  stream.  Every other place within Git we use a bit set to mean\n  *more* data follows, and a bit not set to mean *less* data\n  follows.  pack v4 is backwards here, and that's wrong.]\n\nThe commit_time field is a 4 byte big-endian seconds-since-epoch\nthing.  We're actually saying the high-bit must not be set here,\nleaving that room for future expansion.  We may just later redefine\nit to mean an unsigned time_t, or to mean its variable length\nencoded, or...  ;-)\n\nWhy commit_time, and why before the idents?  Because if you look at\nour revision walking code we care about commit_time to sort commits\nin struct commit_list.  Making it early where we can get to it fast\nhelps the commit walker skip through commits it doesn't want to show.\n\nThe author_time field is not present if flags & 128 is true.\nIf flags & 128 is false, its present, and uses the same encoding\nas commit_time.  Why is this field optional?  Because its not\nuncommon for it to match commit_time!  ;-)\n\n----+-----------+--------+---------------------\n... | committer | author | deflated_message ...\n----+-----------+--------+---------------------\n      vint         vint\n\nNow to finish out the object we have the committer as a variable\nlength integer index into EXTOBJ_IDENT_TABLE.  The author is\nthe same, except its optional and is only present if flags &\n64 is false.  Why?  Again, because it is commonf for author ==\ncommitter in many projects.\n\nThe remainder of the buffer is the zlib deflated message.\n\nNow the message is tricky.  When inflated it actually usually starts\nwith an LF.  Why?\n\nIn 'raw' format of a commit we consider the end of the header lines\nand the start of the message itself to be a single blank line.  But\nthere can be additional headers beyond tree/parent/author/committer.\nLike what?  The newer encoding header!\n\nSo commits that have no encoding header have their inflated message\nstarting with an LF.  Commits that actually used the encoding header\nhave their inflated message starting with 'encoding '.  So we can\ntell if there are additional headers (or not) in a given commit by\nlooking at the inflated message to see if the first character is\nan LF, or not.\n\nThis format allows us to store any additional headers that\nmight get developed, while still enjoying the benefits of the\nEXTOBJ_DICT_COMMIT encoding for the headers that are currently\nsomewhat important to Git.\n\n-- \nShawn.\n"},{"id":"37929","messageId":"20070325094033.GJ25863@spearce.org","threadId":"7384","inReplyTo":"20070325084641.GG25863@spearce.org","subject":"Re: Understanding version 4 packs","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-25T09:40:34Z","receivedAt":"2007-03-25T09:40:34Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"\"Shawn O. Pearce\" <spearce@spearce.org> wrote:\n> So what you will find is that the EXTOBJ_FILENAME_TABLE is dumped\n> out behind all of the commits, but before the first OBJ_DICT_TREE,\n> and since all trees tend to get converted to an OBJ_DICT_TREE,\n> the EXTOBJ_FILENAME_TABLE is sandwiched exactly between the commits\n> and the trees.\n...\n> The reason we put the EXTOBJ_FILENAME_TABLE behind the commits is\n> we often walk the commit chains (following parent pointers) without\n> looking at the trees at all.  Consider `git log`, in the default\n> settings we don't need the trees.  By keeping the filename table\n> behind the commits the OS read-ahead buffering gets a better chance\n> at loading all of the data we need, and none of the data we don't.\n> \n> So that's why its where it is.\n\nI just talked with Junio about this on #git.\n\nMy real reason for putting the EXTOBJ_FILENAME_TABLE here is\n\"lack of a better reason\".  I just didn't write that above.  ;-)\n\nWe want it before the first OBJ_DICT_TREE to help the unpackers.\n\nAnd just like we don't currently ever store the delta base for an\nOBJ_TREE before the first commit (as commits always get packed first)\nwe also don't store the EXTOBJ_FILENAME_TREE before the first commit.\n\nJunio raised the point that in large projects `git log -- asm/i386`\ncan be a very common/useful/necessary operation, and that in such\ncases we need to evaluate trees as part of the log operation.\nAny attempt to optimize for git-log without a path spec is wrong,\nwrong, wrong.  I agree.\n\nThe part I quoted above was not trying to imply that Nico and I\nare optimizing for using git-log without a path limiter.  It just\nread that way to Junio, and may read that way for others too.\nHence this follow-up.\n\nI'm open to suggestions about placement for EXTOBJ_FILENAME_TABLE,\nbut I think its current position between commits and trees is the\nprobably the best we can get.\n\n-- \nShawn.\n"},{"id":"37938","messageId":"Pine.LNX.4.64.0703251004580.6730@woody.linux-foundation.org","threadId":"7384","inReplyTo":"20070325091806.GH25863@spearce.org","subject":"Re: Understanding version 4 packs","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-03-25T17:09:14Z","receivedAt":"2007-03-25T17:09:14Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 25 Mar 2007, Shawn O. Pearce wrote:\n> >\n> > What happens to the paths, that do not have a correponding entry in the\n> > path name table, because they are not among the 65535 most frequent\n> > paths in the pack?\n> \n> They don't appear in the table.  And any tree that uses them is\n> forced to use the \"legacy\" OBJ_TREE encoding.  Which is what we\n> have now in pack v2, and in loose objects.\n\nWould it hurt too much to just make it four bytes, and avoid that issue?\n\nSpecial cases - and *especially* special cases that are hard to trigger in \nthe first place - equal bugs. And bugs are much much worse than trying to \nsave a little bit of space.\n\n> The author_time field is not present if flags & 128 is true.\n> If flags & 128 is false, its present, and uses the same encoding\n> as commit_time.  Why is this field optional?  Because its not\n> uncommon for it to match commit_time!  ;-)\n\nIf the author time is the same as the commit time, most of the time the \nauthor is the same as the committer too, no? So the field should be \nconditional not for the author_time, but for the combination, no?\n\nOur email-parsing tools (which is the most common reason for a committer \nnot being the same as the author) all take the author date from the email. \nSo I don't think author_time == committer_time except when the committer \nand the author are one and the same person.\n\n\t\t\tLinus\n"},{"id":"37941","messageId":"20070325203141.GA12376@spearce.org","threadId":"7384","inReplyTo":"Pine.LNX.4.64.0703251004580.6730@woody.linux-foundation.org","subject":"Re: Understanding version 4 packs","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-25T20:31:41Z","receivedAt":"2007-03-25T20:31:41Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Linus Torvalds <torvalds@linux-foundation.org> wrote:\n> On Sun, 25 Mar 2007, Shawn O. Pearce wrote:\n> > >\n> > > What happens to the paths, that do not have a correponding entry in the\n> > > path name table, because they are not among the 65535 most frequent\n> > > paths in the pack?\n> > \n> > They don't appear in the table.  And any tree that uses them is\n> > forced to use the \"legacy\" OBJ_TREE encoding.  Which is what we\n> > have now in pack v2, and in loose objects.\n> \n> Would it hurt too much to just make it four bytes, and avoid that issue?\n> \n> Special cases - and *especially* special cases that are hard to trigger in \n> the first place - equal bugs. And bugs are much much worse than trying to \n> save a little bit of space.\n\nWorth exploring.  When I get back to rebasing that topic onto\nJunio's tree I'll try a 4 byte index and see what kind of damage\nit does on space on large projects (Mozilla, linux-2.6, Eclipse).\nYou may be right, an 8 byte record may just be worth the cost.\n \n> > The author_time field is not present if flags & 128 is true.\n> > If flags & 128 is false, its present, and uses the same encoding\n> > as commit_time.  Why is this field optional?  Because its not\n> > uncommon for it to match commit_time!  ;-)\n> \n> If the author time is the same as the commit time, most of the time the \n> author is the same as the committer too, no? So the field should be \n> conditional not for the author_time, but for the combination, no?\n\nExcellent observation.  I'll make that change at the same time that I\nfix the meaning of flags & 128 to mean \"more data follows\".  Thanks!\n\n-- \nShawn.\n"},{"id":"37980","messageId":"alpine.LFD.0.83.0703252102520.3041@xanadu.home","threadId":"7384","inReplyTo":"20070325203141.GA12376@spearce.org","subject":"Re: Understanding version 4 packs","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-26T01:12:41Z","receivedAt":"2007-03-26T01:12:41Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 25 Mar 2007, Shawn O. Pearce wrote:\n\n> Linus Torvalds <torvalds@linux-foundation.org> wrote:\n> > On Sun, 25 Mar 2007, Shawn O. Pearce wrote:\n> > > >\n> > > > What happens to the paths, that do not have a correponding entry in the\n> > > > path name table, because they are not among the 65535 most frequent\n> > > > paths in the pack?\n> > > \n> > > They don't appear in the table.  And any tree that uses them is\n> > > forced to use the \"legacy\" OBJ_TREE encoding.  Which is what we\n> > > have now in pack v2, and in loose objects.\n> > \n> > Would it hurt too much to just make it four bytes, and avoid that issue?\n> > \n> > Special cases - and *especially* special cases that are hard to trigger in \n> > the first place - equal bugs. And bugs are much much worse than trying to \n> > save a little bit of space.\n> \n> Worth exploring.  When I get back to rebasing that topic onto\n> Junio's tree I'll try a 4 byte index and see what kind of damage\n> it does on space on large projects (Mozilla, linux-2.6, Eclipse).\n> You may be right, an 8 byte record may just be worth the cost.\n\nMaybe simply 3 bytes might be a good compromise too.  I doubt a single \npack is ever to contain 4G paths since it is limited to 4G _objects_ in \nthe first place.\n\nAnother approach is to have the path index field width as the first item \nin such an object.  This way it can be scalled as needed.\n\nBTW Shawn there is no need to store the number of tree records at the \nbeginning of the tree object since that can be deduced directly from the \nobject size stored in the object header.\n\n\nNicolas\n"},{"id":"37984","messageId":"20070326020257.GB13247@spearce.org","threadId":"7384","inReplyTo":"alpine.LFD.0.83.0703252102520.3041@xanadu.home","subject":"Re: Understanding version 4 packs","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-26T02:02:57Z","receivedAt":"2007-03-26T02:02:57Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre <nico@cam.org> wrote:\n> Maybe simply 3 bytes might be a good compromise too.  I doubt a single \n> pack is ever to contain 4G paths since it is limited to 4G _objects_ in \n> the first place.\n\n16M paths is also a lot. ;-)\n \n> BTW Shawn there is no need to store the number of tree records at the \n> beginning of the tree object since that can be deduced directly from the \n> object size stored in the object header.\n\nDoh.  Yes, of course.\n\n-- \nShawn.\n"},{"id":"38015","messageId":"eu818b$im6$2@sea.gmane.org","threadId":"7384","inReplyTo":"20070326020257.GB13247@spearce.org","subject":"Re: Understanding version 4 packs","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2007-03-26T08:49:07Z","receivedAt":"2007-03-26T08:49:07Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Shawn O. Pearce wrote:\n\n> Nicolas Pitre <nico@cam.org> wrote:\n\n>> BTW Shawn there is no need to store the number of tree records at the \n>> beginning of the tree object since that can be deduced directly from the \n>> object size stored in the object header.\n> \n> Doh.  Yes, of course.\n\nBut if it makes for easier _implementation_, perhaps it should stay...\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"38029","messageId":"e5bfff550703260516q5da5f46et8aab2ebadcd9cceb@mail.gmail.com","threadId":"7384","inReplyTo":"20070325091806.GH25863@spearce.org","subject":"Re: Understanding version 4 packs","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-03-26T12:16:11Z","receivedAt":"2007-03-26T12:16:11Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 3/25/07, Shawn O. Pearce <spearce@spearce.org> wrote:\n> Peter Eriksen <s022018@student.dtu.dk> wrote:\n> > On Sat, Mar 24, 2007 at 07:24:17PM -0400, Nicolas Pitre wrote:\n> > > On Sat, 24 Mar 2007, Peter Eriksen wrote:\n> > >\n> >\n> > The uncompressed file name table contains NR_ENTRIES entries,\n> > and looks like this:\n> >\n> > +------------+------+--------------+------+--------------------+----\n> > | NR_ENTRIES | MODE |  Full path 1 | MODE | Full path 2        | ...\n> > +------------+------+--------------+------+--------------------+----\n> >    4 bytes    2 bytes   n1 bytes    2 bytes     n2 bytes\n> >\n> > MODE is a network-byte-order integer representing the mode of the path,\n> > and the path is a variable length, null-terminated string.\n>\n> Yes so far.\n>\n\nPerhaps has been already evaluated and my comment is not pertinent\nbut, anyway...\n\nExperimenting with file names cache in qgit I have found a big saving\nsplitting the paths in base name and file name and indexing both:\n\ndrivers\\usb\\host\\ehci.h\ndrivers\\usb\\host\\ehci-pci.c\ndrivers\\usb\\host\\ohci-pci.c\nkernel\\sched.c\n\nbecame:\n\ndir names table\n\n0 drivers\\usb\\host\n1 kernel\n\n\nfile name table\n\n0 ehci.h\n1 ehci-pci.c\n2 ohci-pci.c\n\nIn this way a big saving is achieved in case of directories deep in\nthe tree (long paths) and a lot of files. Also after compressing the\ndifference is noticeable.\n\nRegarding MODE field an observation could be that is almost always the\nsame, so an idea could be to store a 'default mode' just after\nnr_entries and do not add the field any more except in case path mode\nis different from default mode. In case this could bring to unaligned\nentries another idea could be to store _all_ mode fields at the\nbeginning (or at the end and let deflate to remove almost everything\nmore easily)\n\n  Marco\n"},{"id":"38032","messageId":"alpine.LFD.0.83.0703260959310.3041@xanadu.home","threadId":"7384","inReplyTo":"eu818b$im6$2@sea.gmane.org","subject":"Re: Understanding version 4 packs","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-26T14:01:08Z","receivedAt":"2007-03-26T14:01:08Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 26 Mar 2007, Jakub Narebski wrote:\n\n> Shawn O. Pearce wrote:\n> \n> > Nicolas Pitre <nico@cam.org> wrote:\n> \n> >> BTW Shawn there is no need to store the number of tree records at the \n> >> beginning of the tree object since that can be deduced directly from the \n> >> object size stored in the object header.\n> > \n> > Doh.  Yes, of course.\n> \n> But if it makes for easier _implementation_, perhaps it should stay...\n\nNo.\n\nI don't think a division by 6 is that much of an implementation issue.\n\n\nNicolas\n"},{"id":"38034","messageId":"alpine.LFD.0.83.0703261015110.3041@xanadu.home","threadId":"7384","inReplyTo":"e5bfff550703260516q5da5f46et8aab2ebadcd9cceb@mail.gmail.com","subject":"Re: Understanding version 4 packs","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-26T14:27:39Z","receivedAt":"2007-03-26T14:27:39Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 26 Mar 2007, Marco Costalba wrote:\n\n> Experimenting with file names cache in qgit I have found a big saving\n> splitting the paths in base name and file name and indexing both:\n> \n> drivers\\usb\\host\\ehci.h\n> drivers\\usb\\host\\ehci-pci.c\n> drivers\\usb\\host\\ohci-pci.c\n> kernel\\sched.c\n> \n> became:\n> \n> dir names table\n> \n> 0 drivers\\usb\\host\n> 1 kernel\n> \n> \n> file name table\n> \n> 0 ehci.h\n> 1 ehci-pci.c\n> 2 ohci-pci.c\n> \n> In this way a big saving is achieved in case of directories deep in\n> the tree (long paths) and a lot of files. \n\nSure, but if you also consider drivers/usb/Makefile and drivers/Kconfig \nfor example then you start losing on space saving.  Maybe that makes \nsense for qgit but it has no advantage in a pack which contains every \npossible files.\n\n> Regarding MODE field an observation could be that is almost always the\n> same, so an idea could be to store a 'default mode' just after\n> nr_entries and do not add the field any more except in case path mode\n> is different from default mode.\n\nIf the mode is always the same, or most likely similar for many entries \nthen it will compress very well.  In fact in the current table format \nthe tree byte sequence NULL+16-bit-mode will be quite common and likely \nto deflate accordingly.  This is therefore not worth adding more complex \nhandling at runtime for deciding which mode to use, and still you'd have \nto store a flag for each path component to decide if the default mode \nshould be used or not anyway.\n\n> In case this could bring to unaligned\n> entries another idea could be to store _all_ mode fields at the\n> beginning (or at the end and let deflate to remove almost everything\n> more easily)\n\nThat's worth trying indeed.\n\n\nNicolas\n"},{"id":"38039","messageId":"e5bfff550703261010u67aa1207j1c6f0200bb7744a@mail.gmail.com","threadId":"7384","inReplyTo":"alpine.LFD.0.83.0703261015110.3041@xanadu.home","subject":"Re: Understanding version 4 packs","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-03-26T17:10:05Z","receivedAt":"2007-03-26T17:10:05Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 3/26/07, Nicolas Pitre <nico@cam.org> wrote:\n> On Mon, 26 Mar 2007, Marco Costalba wrote:\n>\n> > Experimenting with file names cache in qgit I have found a big saving\n> > splitting the paths in base name and file name and indexing both:\n> >\n> > drivers\\usb\\host\\ehci.h\n> > drivers\\usb\\host\\ehci-pci.c\n> > drivers\\usb\\host\\ohci-pci.c\n> > kernel\\sched.c\n> >\n> > became:\n> >\n> > dir names table\n> >\n> > 0 drivers\\usb\\host\n> > 1 kernel\n> >\n> >\n> > file name table\n> >\n> > 0 ehci.h\n> > 1 ehci-pci.c\n> > 2 ohci-pci.c\n> >\n> > In this way a big saving is achieved in case of directories deep in\n> > the tree (long paths) and a lot of files.\n>\n> Sure, but if you also consider drivers/usb/Makefile and drivers/Kconfig\n> for example then you start losing on space saving.\n\nIn your example you'd have:\n\ndrivers/usb/Makefile\ndrivers/Kconfig\n\nbecame\n\ndir names table\n0 drivers\n1 drivers/usb\n\nfile name table\n0 Makefile\n1 Kconfig\n\nI fail to see wher's the losing on space saving. More, you probably\nhave many paths both under 'drivers' and 'drivers/usb' and for each\nadded path it would be possible to avoid to store the prefix ('driver'\nor 'driver/usb').\n\nTo better clarify, OBJ_DICT_TREE data *currently* looks like:\n\n+------------+-------+-------+-------+-------+----\n| NR_ENTRIES | name1 | hash1 | name2 | hash2 | ...\n+------------+-------+-------+-------+-------+----\n  vint        2 bytes 4 bytes 2 bytes 4 bytes\n\nwhere name1 is an index into the packfile's sole EXTOBJ_FILENAME_TABLE.\n\nThe possible improve is to define OBJ_DICT_TREE like\n\n+------------+-------+-------+-------+-------+----\n| NR_ENTRIES | dir1   | fiile1 | hash1| dir 2| fiile2|...\n+------------+-------+-------+-------+-------+----\n  vint        2 bytes 2 bytes 2 bytes 4 bytes\n\nwhere dir1 is an index into a new EXTOBJ_DIRNAME_TABLE and file1 is an\nindex in a new  EXTOBJ_FILENAME_TABLE.\n\n\nEXTOBJ_FILENAME_TABLE is defined as the currently (but much smaller in\nsize!!) and keeps only the file names, not the full paths, while\nEXTOBJ_DIRNAME_TABLE is defined as EXTOBJ_FILENAME_TABLE but without\nMODE field (associated to files only) and is used to store the dir\nnames.\n\nDecopuling dir names from file names could improve saving space\nbecause the length of proposed EXTOBJ_FILENAME_TABLE +\nEXTOBJ_DIRNAME_TABLE < current EXTOBJ_FILENAME_TABLE.\n\n  Marco\n\nP.S: Of course now you'd save 2+2 bytes in OBJ_DICT_TREE instead of 2\nfor 'name' index.\nTo avoid this and keep the idea of decopuling dir and file names an\nstill use 2 bytes in OBJ_DICT_TREE a possible layout of\nEXTOBJ_FILENAME_TABLE could be:\n\n\n +------------+------+-------+-----------------+---\n-+----------------+-------+------+----------+\n | NR_ENTRIES | dirA  |  file name1 | ofs1| file name2 | ofs 2|dirB\n|file name3 | ofs3 | ....\n +------------+------+-------+-----------------+----\n+---------------+--------+------+----------+\n\nWhere ofs1 and ofs2 are 2-bytes values pointing to dirA, ofs3 points\nto dirB and so on.\n\nWhere the tree layout of the above example is:\n\ndirA \\ file name1\ndirA \\ file name2\ndirB \\ file name3\n\nWith this approach you have both the saving in case of directories\nwith many files and still 2 bytes per 'name' index in OBJ_DICT_TREE\n(that points to 'file name' field). This approach saves space as soon\nas directory names are longer then 2 chars.\n"},{"id":"38049","messageId":"alpine.LFD.0.83.0703261414130.3041@xanadu.home","threadId":"7384","inReplyTo":"e5bfff550703261010u67aa1207j1c6f0200bb7744a@mail.gmail.com","subject":"Re: Understanding version 4 packs","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-26T18:15:53Z","receivedAt":"2007-03-26T18:15:53Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 26 Mar 2007, Marco Costalba wrote:\n\n> On 3/26/07, Nicolas Pitre <nico@cam.org> wrote:\n> > On Mon, 26 Mar 2007, Marco Costalba wrote:\n> > \n> > > Experimenting with file names cache in qgit I have found a big saving\n> > > splitting the paths in base name and file name and indexing both:\n> > >\n> > > drivers\\usb\\host\\ehci.h\n> > > drivers\\usb\\host\\ehci-pci.c\n> > > drivers\\usb\\host\\ohci-pci.c\n> > > kernel\\sched.c\n> > >\n> > > became:\n> > >\n> > > dir names table\n> > >\n> > > 0 drivers\\usb\\host\n> > > 1 kernel\n> > >\n> > >\n> > > file name table\n> > >\n> > > 0 ehci.h\n> > > 1 ehci-pci.c\n> > > 2 ohci-pci.c\n> > >\n> > > In this way a big saving is achieved in case of directories deep in\n> > > the tree (long paths) and a lot of files.\n> > \n> > Sure, but if you also consider drivers/usb/Makefile and drivers/Kconfig\n                     ^^^^\n\n> In your example you'd have:\n> \n> drivers/usb/Makefile\n> drivers/Kconfig\n\nNo.  \"also\" was the key word here.\n\n\nNicolas\n"},{"id":"38052","messageId":"alpine.LFD.0.83.0703261417520.3041@xanadu.home","threadId":"7384","inReplyTo":"e5bfff550703261010u67aa1207j1c6f0200bb7744a@mail.gmail.com","subject":"Re: Understanding version 4 packs","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-03-26T18:43:03Z","receivedAt":"2007-03-26T18:43:03Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 26 Mar 2007, Marco Costalba wrote:\n\n> I fail to see wher's the losing on space saving. More, you probably\n> have many paths both under 'drivers' and 'drivers/usb' and for each\n> added path it would be possible to avoid to store the prefix ('driver'\n> or 'driver/usb').\n\nI'm under the impression you don't understand how tree objects work.\n\n> To better clarify, OBJ_DICT_TREE data *currently* looks like:\n> \n> +------------+-------+-------+-------+-------+----\n> | NR_ENTRIES | name1 | hash1 | name2 | hash2 | ...\n> +------------+-------+-------+-------+-------+----\n>  vint        2 bytes 4 bytes 2 bytes 4 bytes\n> \n> where name1 is an index into the packfile's sole EXTOBJ_FILENAME_TABLE.\n\nExact.\n\n> The possible improve is to define OBJ_DICT_TREE like\n> \n> +------------+-------+-------+-------+-------+----\n> | NR_ENTRIES | dir1   | fiile1 | hash1| dir 2| fiile2|...\n> +------------+-------+-------+-------+-------+----\n>  vint        2 bytes 2 bytes 2 bytes 4 bytes\n> \n> where dir1 is an index into a new EXTOBJ_DIRNAME_TABLE and file1 is an\n> index in a new  EXTOBJ_FILENAME_TABLE.\n\nYou definitely don't understand how tree objects are used.\n\nTree objects have no notion of full path at all.  They only contain \ndirectory component from a single path level only.\n\nIf you have the following files:\n\n\tdrivers/Kconfig\n\tdrivers/usb/Makefile\n\tdrivers/usb/host/ehci.h\n\tdrivers/usb/host/ehci-pci.c\n\tdrivers/usb/host/ohci-pci.c\n\tkernel/sched.c\n\nthen you'll start with one tree objects for the root directory that \ncontains:\n\n\tdrivers (tree)\n\tkernel (tree)\n\nThen a second tree object for the \"drivers\" directory that contains:\n\n\tKconfig (blob)\n\tusb (tree)\n\nThen a third tree object for the \"usb\" directory with:\n\n\tMakefile (blob)\n\thost (tree)\n\nThen the fourth tree object with:\n\n\tehci.h (blob)\n\tehci-pci.c (blob)\n\tohci-pci.c (blob)\n\nAnd finally a fifth tree object for the \"kernel\" directory with:\n\n\tsched.c (blob)\n\nHence, the path component table would contain:\n\n\tdrivers\n\tusb\n\thost\n\tKconfig\n\tMakefile\n\tehci.h\n\tehci-pci.c\n\tohci-pci.c\n\tsched.c\n\nalong with the mode bits for each of those path components, and this is \nwhat the new tree object would index into for each tree record.\n\n> EXTOBJ_FILENAME_TABLE is defined as the currently (but much smaller in\n> size!!) and keeps only the file names, not the full paths, while\n> EXTOBJ_DIRNAME_TABLE is defined as EXTOBJ_FILENAME_TABLE but without\n> MODE field (associated to files only) and is used to store the dir\n> names.\n> \n> Decopuling dir names from file names could improve saving space\n> because the length of proposed EXTOBJ_FILENAME_TABLE +\n> EXTOBJ_DIRNAME_TABLE < current EXTOBJ_FILENAME_TABLE.\n\nI hope the explanation above made it clear that what you're proposing \ncannot ever be smaller than current EXTOBJ_FILENAME_TABLE.\n\n\nNicolas\n"},{"id":"38111","messageId":"e5bfff550703262346q54853791scca3bab217a043aa@mail.gmail.com","threadId":"7384","inReplyTo":"alpine.LFD.0.83.0703261417520.3041@xanadu.home","subject":"Re: Understanding version 4 packs","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-03-27T06:46:20Z","receivedAt":"2007-03-27T06:46:20Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 3/26/07, Nicolas Pitre <nico@cam.org> wrote:\n> On Mon, 26 Mar 2007, Marco Costalba wrote:\n>\n> Hence, the path component table would contain:\n>\n>         drivers\n>         usb\n>         host\n>         Kconfig\n>         Makefile\n>         ehci.h\n>         ehci-pci.c\n>         ohci-pci.c\n>         sched.c\n>\n> along with the mode bits for each of those path components, and this is\n> what the new tree object would index into for each tree record.\n>\n\nNow I understand.\n\nJust a question. So getting full paths does it requires some additional work?\n\n Marco\n"},{"id":"38114","messageId":"20070327065531.GN13247@spearce.org","threadId":"7384","inReplyTo":"e5bfff550703262346q54853791scca3bab217a043aa@mail.gmail.com","subject":"Re: Understanding version 4 packs","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-03-27T06:55:31Z","receivedAt":"2007-03-27T06:55:31Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Marco Costalba <mcostalba@gmail.com> wrote:\n> On 3/26/07, Nicolas Pitre <nico@cam.org> wrote:\n> >Hence, the path component table would contain:\n> >\n> >        drivers\n> >        usb\n> >        host\n> >        Kconfig\n> >        Makefile\n> >        ehci.h\n> >        ehci-pci.c\n> >        ohci-pci.c\n> >        sched.c\n> >\n> >along with the mode bits for each of those path components, and this is\n> >what the new tree object would index into for each tree record.\n> \n> Just a question. So getting full paths does it requires some additional \n> work?\n\nNo.\n\nWhy?  Because Git already makes the full path by taking individual\npath components from each tree object and joins them together\n(adding a \"/\" between each component) before displaying it to an\napplication, or loading the path into the index file.  This is\nbecause of the fundemental (and quite nice!) structure of a tree.\n\n-- \nShawn.\n"}]}