{"thread":{"id":"4532","subject":"Why so much time in the kernel?","startedAt":"2006-06-16T14:49:39Z","lastAt":"2006-06-16T18:32:42Z","messageCount":11,"participants":["Jon Smirl","Linus Torvalds","Jakub Narebski","Keith Packard","Nicolas Pitre"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"21882","messageId":"9e4733910606160749t4d7a541ev72a67383e96d86da@mail.gmail.com","threadId":"4532","inReplyTo":null,"subject":"Why so much time in the kernel?","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-06-16T14:49:39Z","receivedAt":"2006-06-16T14:49:39Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"I'm still working on importing Mozilla CVS. I'm at the phase now where\nall of the changeset have been identified. The scripts are pulling the\nchangesets one at a time out of CVS and putting them into git. I've\nbeen running this phase for 2 days now on a 3GB machine and it still\nisn't finished.\n\nI am spending over 40% of the time in the kernel. This looks to be\ncaused from forks and starting small tasks, is that the correct\ninterpretation? Is the number of process that have been run recorded\nany where? 1.4% of the time is spend in the dynamic linker.\n\nChecking with oprofile I see this:\n\n  18262372 41.0441 /home/good/vmlinux\n  5465741 12.2841 /usr/bin/cvs\n  4374336  9.8312 /lib/libc-2.4.so\n  3627709  8.1532 /lib/libcrypto.so.0.9.8a\n  2494610  5.6066 /usr/bin/oprofiled\n  2471238  5.5540 /usr/lib/libz.so.1.2.3\n   945349  2.1246 /usr/lib/perl5/5.8.8/i386-linux-thread-multi/CORE/libperl.so\n   933646  2.0983 /usr/local/bin/git-read-tree\n   758776  1.7053 /usr/local/bin/git-write-tree\n   642502  1.4440 /lib/ld-2.4.so\n   472903  1.0628 /nvidia\n   379254  0.8524 /usr/local/bin/git-pack-objects\n\nand breaking down the kernel number:\n\n3467889  18.9893  copy_page_range\n2190416  11.9941  unmap_vmas\n1156011   6.3300  page_fault\n887794    4.8613  release_pages\n860853    4.7138  page_remove_rmap\n633243    3.4675  get_page_from_freelist\n398773    2.1836  do_wp_page\n344422    1.8860  __mutex_lock_slowpath\n280070    1.5336  __handle_mm_fault\n241713    1.3236  do_page_fault\n238398    1.3054  __d_lookup\n236654    1.2959  vm_normal_page\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"21883","messageId":"Pine.LNX.4.64.0606160755170.5498@g5.osdl.org","threadId":"4532","inReplyTo":"9e4733910606160749t4d7a541ev72a67383e96d86da@mail.gmail.com","subject":"Re: Why so much time in the kernel?","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-16T15:06:58Z","receivedAt":"2006-06-16T15:06:58Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 16 Jun 2006, Jon Smirl wrote:\n> \n> I am spending over 40% of the time in the kernel. This looks to be\n> caused from forks and starting small tasks, is that the correct\n> interpretation?\n\nYes. Your kernel profile is all for stuff related to setting up and \ntearing down process space (well, __mutex_lock_slowpath at 1.88% and \n__d_lookup at 1.3% is not, but every single one before that does seem to \nbe about fork/exec/exit).\n\nI think it's both the CVS server that continually forks/exits (it doesn't \nactually do a exec at all - it seem sto be using fork/exit as a way to \ncontrol its memory usage - knowing that the OS will free all the temporary \nmemory on exit - I think the newer CVS development trees don't do this, \nbut that also seems to be why they leak memory like mad and eventually run \nout ;).\n\nAND it's git-cvsimport forking and exec'ing git helper processes. \n\nSo that process overhead is expected.\n\nWhat I would _not_ have expected is:\n\n>   933646  2.0983 /usr/local/bin/git-read-tree\n\nI don't see why git-read-tree is so hot for you. We should never need to \nread a tree when we're importing something, unless there are tons of \nbranches and we switch back and forth between them.\n\nI guess mozilla really does use a fair number of branches? \n\nMartin sent out a patch (that I don't think has been merged yet) to avoid \nthe git-read-tree overhead when switching branches. Look for an email with \na subject like \"cvsimport: keep one index per branch during import\", I \nsuspect that would speed up the git part a lot.\n\n(It will also avoid a few fork/exec's, but you'll still have most of them, \nso I don't think you'll see any really _fundamental_ changes to this, but \nthe git-read-tree overhead should be basically gone, and some of the \nlibz.so pressure would also be gone with it. It should also avoid \nrewriting the index file, so you'd get lower disk pressure, but it looks \nlike none of your problems are really due to IO, so again, that probably \nwon't make much of a difference for you).\n\n\t\t\tLinus\n"},{"id":"21884","messageId":"9e4733910606160825hb538d6fo4c9f1d7d9768e100@mail.gmail.com","threadId":"4532","inReplyTo":"Pine.LNX.4.64.0606160755170.5498@g5.osdl.org","subject":"Re: Why so much time in the kernel?","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-06-16T15:25:22Z","receivedAt":"2006-06-16T15:25:22Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 6/16/06, Linus Torvalds <torvalds@osdl.org> wrote:\n>\n>\n> On Fri, 16 Jun 2006, Jon Smirl wrote:\n> >\n> > I am spending over 40% of the time in the kernel. This looks to be\n> > caused from forks and starting small tasks, is that the correct\n> > interpretation?\n>\n> Yes. Your kernel profile is all for stuff related to setting up and\n> tearing down process space (well, __mutex_lock_slowpath at 1.88% and\n> __d_lookup at 1.3% is not, but every single one before that does seem to\n> be about fork/exec/exit).\n>\n> I think it's both the CVS server that continually forks/exits (it doesn't\n> actually do a exec at all - it seem sto be using fork/exit as a way to\n> control its memory usage - knowing that the OS will free all the temporary\n> memory on exit - I think the newer CVS development trees don't do this,\n> but that also seems to be why they leak memory like mad and eventually run\n> out ;).\n\nI am using cvs-1.11.21-3.2\nI can try running their development tree.\n\n>\n> AND it's git-cvsimport forking and exec'ing git helper processes.\n\nIs it worthwhile to make a library version of these? Svn has lib\nversions and they barely show up in oprofile. cvsimport is only using\n4-5 low level git funtions.\n\n>\n> So that process overhead is expected.\n>\n> What I would _not_ have expected is:\n>\n> >   933646  2.0983 /usr/local/bin/git-read-tree\n>\n> I don't see why git-read-tree is so hot for you. We should never need to\n> read a tree when we're importing something, unless there are tons of\n> branches and we switch back and forth between them.\n>\n> I guess mozilla really does use a fair number of branches?\n\nIs 1,800 a lot?\n\n>\n> Martin sent out a patch (that I don't think has been merged yet) to avoid\n> the git-read-tree overhead when switching branches. Look for an email with\n> a subject like \"cvsimport: keep one index per branch during import\", I\n> suspect that would speed up the git part a lot.\n\nI'll check this out\n\n> (It will also avoid a few fork/exec's, but you'll still have most of them,\n> so I don't think you'll see any really _fundamental_ changes to this, but\n> the git-read-tree overhead should be basically gone, and some of the\n> libz.so pressure would also be gone with it. It should also avoid\n> rewriting the index file, so you'd get lower disk pressure, but it looks\n> like none of your problems are really due to IO, so again, that probably\n> won't make much of a difference for you).\n\nI have been CPU bound for two days, disk activity is minor.\ngit-cvsimport is 250MB and I have 2GB of disk cache.\n\nAfter looking at this process for about a week it doesn't look like\nprocessing chronologically is the best strategy. cvsps can quickly\nwork out the changesets, 15 minutes. Then it might be better to walk\nthe CVS files one at a time generating git IDs for each revision. Next\nuse the IDs and changeset info to build the git trees. Finally pack\neverything. This strategy would minimize the work load on the CVS\nfiles (adding all those delta to get random revs).\n\nCan git build a repository in this manner? If this is feasible it may\nbe possible to do all of this in a single pass over the CVS tree by\nmodifying cvsps.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"21885","messageId":"Pine.LNX.4.64.0606160906250.5498@g5.osdl.org","threadId":"4532","inReplyTo":"9e4733910606160825hb538d6fo4c9f1d7d9768e100@mail.gmail.com","subject":"Re: Why so much time in the kernel?","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-16T16:09:14Z","receivedAt":"2006-06-16T16:09:14Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 16 Jun 2006, Jon Smirl wrote:\n>\n> I am using cvs-1.11.21-3.2\n> I can try running their development tree.\n\nNo, don't. We already know that 1.12 leaks memory and makes the cvsimport \nnot work at all.\n\n> > \n> > AND it's git-cvsimport forking and exec'ing git helper processes.\n> \n> Is it worthwhile to make a library version of these? Svn has lib\n> versions and they barely show up in oprofile. cvsimport is only using\n> 4-5 low level git funtions.\n\nEventually, I think that's where we'll get. We're already at the stage \nwhere most of the core could just be written as a library.\n\n> > I guess mozilla really does use a fair number of branches?\n> \n> Is 1,800 a lot?\n\nYeah. Although even just two is enough, if you just alternate committing \non them ;)\n\nSo it's actually not number of branches, it's more about frequency of \nthe branch changing in the cvsps output. And yes, you could probably \nimprove performance by sorting the changesets differently, but Martin's \nchange to use separate index files should make it all pretty moot.\n\n\t\tLinus\n"},{"id":"21886","messageId":"9e4733910606161000t53328571u10a350eca894ccdc@mail.gmail.com","threadId":"4532","inReplyTo":"Pine.LNX.4.64.0606160906250.5498@g5.osdl.org","subject":"Re: Why so much time in the kernel?","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-06-16T17:00:05Z","receivedAt":"2006-06-16T17:00:05Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"Is it a crazy idea to read the cvs files, compute an sha1 on each\nexpanded delta and then write the delta straight into a pack file? Are\nthe cvs and git delta formats the same? What about CVS's forward and\nreverse delta use? While this is going on, track the\nbranches/changsets in memory and then finish up by writing these trees\ninto the pack file too. This should take no more ram than cvsps needs\ncurrently.\n\nThis leaves the packfile is a non-optimal format but a repack should\nfix that, right?\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"21887","messageId":"e6uok3$vvq$1@sea.gmane.org","threadId":"4532","inReplyTo":"9e4733910606161000t53328571u10a350eca894ccdc@mail.gmail.com","subject":"Re: Why so much time in the kernel?","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-06-16T17:09:28Z","receivedAt":"2006-06-16T17:09:28Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Jon Smirl wrote:\n\n> Is it a crazy idea to read the cvs files, compute an sha1 on each\n> expanded delta and then write the delta straight into a pack file?\n\nThat's what parsecvs does (i.e. read *,v files directly).\nSee http://git.or.cz/gitwiki/InterfacesFrontendsAndTools\n\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"21890","messageId":"1150478968.6983.7.camel@neko.keithp.com","threadId":"4532","inReplyTo":"9e4733910606161000t53328571u10a350eca894ccdc@mail.gmail.com","subject":"Re: Why so much time in the kernel?","fromName":"Keith Packard","fromEmail":"keithp@keithp.com","sentAt":"2006-06-16T17:29:28Z","receivedAt":"2006-06-16T17:29:28Z","isPatch":false,"sender":{"key":"keithp@keithp.com","avatar":"https://gravatar.com/avatar/fa1f479cdd51322fe86215c955a81d296bbf66a1fe625f8a12d87a8ec7faf648?d=mp&s=160"},"body":"On Fri, 2006-06-16 at 13:00 -0400, Jon Smirl wrote:\n> Is it a crazy idea to read the cvs files, compute an sha1 on each\n> expanded delta and then write the delta straight into a pack file? Are\n> the cvs and git delta formats the same? What about CVS's forward and\n> reverse delta use?\n\nAt this point, merging blobs into packs isn't a significant part of the\ncomputational cost. parsecvs is spending all of its time in the\nquadratic traversal of the diff chains; fixing that to emit all of the\nversions in a single pass should speed up that part of the conversion\nprocess dramatically.\n\n>  While this is going on, track the\n> branches/changsets in memory and then finish up by writing these trees\n> into the pack file too. This should take no more ram than cvsps needs\n> currently.\n\ncvsps drops too much state on the floor making branch point and branch\ncontents inaccurate. What I'm hoping is that I can figure out a way to\ndiscard most of the per-version information by computing tree objects in\nreverse order, saving only the tree sha1 and other per-commit info, then\nstitch the commits together using that, without needing the full\nper-file data.\n\n-- \nkeith.packard@intel.com\n"},{"id":"21891","messageId":"9e4733910606161044h736c9675kc91ff77904c5a1d0@mail.gmail.com","threadId":"4532","inReplyTo":"1150478968.6983.7.camel@neko.keithp.com","subject":"Re: Why so much time in the kernel?","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-06-16T17:44:27Z","receivedAt":"2006-06-16T17:44:27Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 6/16/06, Keith Packard <keithp@keithp.com> wrote:\n> On Fri, 2006-06-16 at 13:00 -0400, Jon Smirl wrote:\n> > Is it a crazy idea to read the cvs files, compute an sha1 on each\n> > expanded delta and then write the delta straight into a pack file? Are\n> > the cvs and git delta formats the same? What about CVS's forward and\n> > reverse delta use?\n>\n> At this point, merging blobs into packs isn't a significant part of the\n> computational cost. parsecvs is spending all of its time in the\n> quadratic traversal of the diff chains; fixing that to emit all of the\n> versions in a single pass should speed up that part of the conversion\n> process dramatically.\n\nThat's not true for the state I am in. cvsps can compute the changeset\ntree in 15 minutes, cvs2svn can compute their version in a couple of\nhours. cvs2svn builds a much better tree.\n\nI've been extracting versions from cvs and adding them to git now for\n2.5 days and the process still isn't finished. It is completely CPU\nbound. It's just a loop of cvs co, add it to git, make tree, commit,\netc.\n\n> >  While this is going on, track the\n> > branches/changsets in memory and then finish up by writing these trees\n> > into the pack file too. This should take no more ram than cvsps needs\n> > currently.\n>\n> cvsps drops too much state on the floor making branch point and branch\n> contents inaccurate. What I'm hoping is that I can figure out a way to\n> discard most of the per-version information by computing tree objects in\n> reverse order, saving only the tree sha1 and other per-commit info, then\n> stitch the commits together using that, without needing the full\n> per-file data.\n\nI agree cvsps is dropping a lot.  My screen is full of \"Skipping\n#CVSPS_NO_BRANCH\" and\n\"Skipping SpiderMonkey140_NES40Rtm_Branch\" and \"Skipping\nSpiderMonkey140_BRANCH\" etc.\n\nWhat about the cvs2svn algorithm described in the attachment? A ram\nbased version could be faster. Compression could be acheived by\nswitching from using the full path to a version to the sha1 for it.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n\n\n                         How cvs2svn Works\n                         =================\n\nA cvs2svn run consists of eight passes.  Each pass saves the data it\nproduces to files on disk, so that a) we don't hold huge amounts of\nstate in memory, and b) the conversion process is resumable.\n\nPass 1:\n=======\n\nThe goal of this pass is to write to 'cvs2svn-data.revs' a summary of\nall the revisions for each RCS file.  Each revision will be\nrepresented by one line.  At the end of this stage, the revisions\n(i.e., the lines) will be grouped by RCS file, not by logical commits.\n\nWe walk over the repository, processing each RCS file with\nrcsparse.parse(), using cvs2svn's CollectData class, which is a\nsubclass of rcsparse.Sink(), the parser's callback class.  For each\nRCS file, the first thing the parser encounters is the administrative\nheader, including the head revision, the principal branch, symbolic\nnames, RCS comments, etc.  The main thing that happens here is that\nCollectData.define_tag() is invoked on each symbolic name and its\nattached revision, so all the tags and branches of this file get\ncollected.\n\nNext, the parser hits the revision summary section.  That's the part\nof the RCS file that looks like this:\n\n   1.6\n   date\t2002.06.12.04.54.12;\tauthor captnmark;\tstate Exp;\n   branches\n   \t1.6.2.1;\n   next\t1.5;\n\n   1.5\n   date\t2002.05.28.18.02.11;\tauthor captnmark;\tstate Exp;\n   branches;\n   next\t1.4;\n\n   [...]\n\nFor each revision summary, CollectData.define_revision() is invoked,\nrecording that revision's metadata in various variables of the\nCollectData class instance.\n\nAfter finishing the revision summaries, the parser invokes\nCollectData.tree_completed(), which loops over the revision\ninformation stored, determining if there are instances where a higher\nrevision was committed \"before\" a lower one (rare, but it can happen\nwhen there was clock skew on the repository machine).  If there are\nany, it \"resyncs\" the timestamp of the earlier rev to be just before\nthat of the later rev, but saves the original timestamp in\nself.rev_data[blah][2], so we can later write out a record to the\nresync file indicating that an adjustment was made (this makes it\npossible to catch the other parts of this commit and resync them\nsimilarly, more details below).\n\nNext, the parser encounters the *real* revision data, which has the\nlog messages and file contents.  For each revision, it invokes\nCollectData.set_revision_info(), which writes a new line to\ncvs2svn-data.revs.  The line is constructed by the CVSRevision class -\none of its many roles. Here is an example:\n\n   3dc32955 5afe9b4ba41843d8eb52ae7db47a43eaa9573254 3dc32954 3dc32956 C 1.1 1.2 1.3 1 1 1024 N * 0 0 foo/bar,v\n\nThe fields are:\n\n   1.  a fixed-width timestamp\n   2.  a digest of the log message + author\n   3.  a fixed-width timestamp indicating the timestamp of this\n       revision's previous revision (or \"*\", if it's the first\n       revision on this line of development).\n   4.  a fixed-width timestamp indicating the timestamp of this\n       revision's next revision (or \"*\", if it's the last revision on\n       this line of development).\n   5.  the type of change (\"A\"dd, \"C\"hange, or \"D\"elete)\n   6.  the revision number of the previous revision along this line of\n       development (or \"*\", if it's the first revision on this line of\n       development).\n   7.  the revision number\n   8.  the revision number of the next revision along this line of\n       development (or \"*\", if it's the last revision on this line of\n       development).\n   9.  1 if the RCS file is in the Attic, \"*\" if it isn't.\n   10. 1 is the RCS file has the executable bit set, \"*\" if not.\n   12. The size of the RCS file, in bytes.\n   12. \"N\" if this revision has non-empty deltatext, else \"E\" for empty\n   13. the RCS keyword substitution mode (\"k\", \"b\", etc), or \"*\" if none\n   14. the branch on which this commit happened, or \"*\" if not on a branch\n   15. the number of tags rooted at this revision (followed by their\n       names, space-delimited)\n   16. the number of branches rooted at this revision (followed by\n       their names, space-delimited)\n   17. the path of the RCS file in the repository\n\n(Of course, in the above example, fields 15 and 16 are \"0\", so they have\nno additional data.)\n\nAlso, for resync'd revisions, a line like this is written out to\n'cvs2svn-data.resync':\n\n   3d6c1329 18a215a05abea1c6c155dcc7283b88ae7ce23502 3d6c1328\n\nThe fields are:\n\n   NEW_TIMESTAMP   DIGEST   OLD_TIMESTAMP\n\n(The resync file will be explained later.)\n\nThat's it -- the RCS file is done.\n\nWhen every RCS file is done, Pass 1 is complete, and:\n\n   - cvs2svn-data.revs contains a summary of every RCS file's\n     revisions.  All the revisions for a given RCS file are grouped\n     together, but note that the groups are in no particular order.\n     In other words, you can't yet identify the commits from looking\n     at these lines; a multi-file commit will be scattered all over\n     the place.\n\n   - cvs2svn-data.resync contains a small amount of resync data, in\n     no particular order.\n\nPass 2:\n=======\n\nThis is where the resync file is used.  The goal of this pass is to\nconvert cvs2svn-data.revs to a new file, 'cvs2svn-data.c-revs' (clean\nrevs).  It's the same as the original file, except for some resync'd\ntimestamps.\n\nFirst, read the whole resync file into a hash table that maps each\nauthor+log digest to a list of lists.  Each sublist represents one of\nthe timestamp adjustments from Pass 1, and looks like this:\n\n   [old_time_lower, old_time_upper, new_time]\n\nThe reason to map each digest to a list of sublists, instead of to one\nlist, is that sometimes you'll get the same digest for unrelated\ncommits (for example, the same author commits many times using the\nempty log message, or a log message that just says \"Doc tweaks.\").  So\neach digest may need to \"fan out\" to cover multiple commits, but\nwithout accidentally unifying those commits.\n\nNow we loop over cvs2svn-data.revs, writing each line out to\n'cvs2svn-data.c-revs'.  Most lines are written out unchanged, but\nthose whose digest matches some resync entry, and appear to be part of\nthe same commit as one of the sublists in that entry, get tweaked.\nThe tweak is to adjust the commit time of the line to the new_time,\nwhich is taken from the resync hash and results from the adjustment\ndescribed in Pass 1.\n\nThe way we figure out whether a given line needs to be tweaked is to\nloop over all the sublists, seeing if this commit's original time\nfalls within the old<-->new time range for the current sublist.  If it\ndoes, we tweak the line before writing it out, and then conditionally\nadjust the sublist's range to account for the timestamp we just\nadjusted (since it could be an outlier).  Note that this could, in\ntheory, result in separate commits being accidentally unified, since\nwe might gradually adjust the two sides of the range such that they are\neventually more than COMMIT_THRESHOLD seconds apart.  However, this is\nreally a case of CVS not recording enough information to disambiguate\nthe commits; we'd know we have a time range that exceeds the\nCOMMIT_THRESHOLD, but we wouldn't necessarily know where to divide it\nup.  We could try some clever heuristic, but for now it's not\nimportant -- after all, we're talking about commits that weren't\nimportant enough to have a distinctive log message anyway, so does it\nreally matter if a couple of them accidentally get unified?  Probably\nnot.\n\nNOTE: We currently have a fairly major bug in our resync code.  The\nresync_bug test demonstrates it.  The bug is that, when resyncing in\npass 2, we take no care not to move cvs revisions before previous\ncvs revisions of the same file, thus creating the very problem we were\nattempting to avoid.\n\nPass 3:\n=======\n\nThis is where we deduce the changesets, that is, the grouping of file\nchanges into single commits.\n\nIt's very simple -- run 'sort' on cvs2svn-data.c-revs, converting it\nto 'cvs2svn-data.s-revs'.  Because of the way the data is laid out,\nthis causes commits with the same digest (that is, the same author and\nlog message) to be grouped together.  Poof!  We now have the CVS\nchanges grouped by logical commit.\n\nIn some cases, the changes in a given commit may be interleaved with\nother commits that went on at the same time, because the sort gives\nprecedence to date before log digest.  However, Pass 4 detects this by\nseeing that the log digest is different, and reseparates the commits.\n\nPass 4:\n=======\n\nThis pass has two primary objectives:\n\n1. Create a database that maps CVSRevision unique keys to the actual\n   CVSRevision string from the revs file (whose format is described\n   above in pass 1).  This results in a database containing one\n   key-value pair for each line in the revs file.  This gives us the\n   ability to pass around these smaller keys instead of whole CVS\n   revisions (which look like lines from the s-revs file).  See the\n   CVSRevision class for more details on what the unique key is.\n\n2. Find and create a database containing the last CVS revision that is\n   a source (also referred to as an \"opening\" revision) for all\n   symbolic names.  This will result in a database containing\n   key-value pairs whose key is the unique key for a CVSRevision, and\n   whose value is a list of symbolic names for which that CVSRevision\n   is the last \"opening.\"\n\n   The format for this file is:\n\n       cvs-symname-last-revs.db:\n            Key                      Value\n            CVS Revision             array of Symbolic names\n\n       For example:\n\n            1.38/foo/bar/baz.txt,v  --> [TAG11, BRANCH38]\n            1.93/foo/qux/bat.c,v    --> [TAG39]\n            1.4/foo/bar/baz.txt,v   --> [BRANCH48, BRANCH37]\n            1.18/foo/bar/quux.txt,v --> [TAG320, TAG1178]\n\nPass 5:\n=======\n\nPrimarily, this pass gathers CVS revisions into Subversion revisions\n(a Subversion revision is comprised of one or more CVS revisions)\nbefore we actually begin committing (where \"committing\" means either\nto a Subversion repository or to a dump file).\n\nThis pass does the following:\n\n1. Creates a database file to map Subversion Revision numbers to their\n   corresponding CVS Revisions (cvs2svn-svn-revnums-to-cvs-revs.db).\n   Creates another database file to map CVS Revisions to their\n   Subversion Revision numbers (cvs2svn-cvs-revs-to-svn-revnums.db).\n\n2. When a file is copied to a symbolic name in cvs2svn, there are a\n   range of valid Subversion revisions that we can copy the file from.\n   The first valid Subversion revision number for a symbolic name is\n   called the \"Opening\", and the first *invalid* Subversion revision\n   number encountered after the \"Opening\" is called the \"Closing\".  In\n   this pass, the SymbolingsLogger class writes one line to\n   cvs2svn-symbolic-names.txt per CVS file, per symbolic name, per\n   opening or closing.\n\n3. For each CVS Revision in s-revs, we write out a line (for each\n   symbolic name that it opens) to a symbolic-names.txt file if it is\n   the first possible source revision (the \"opening\" revision) for a\n   copy to create a branch or tag, or if it is the last possible\n   revision (the \"closing\" revision) for a copy to create a branch or\n   tag.  Not every opening will have a corresponding closing.\n\n   The format of each line is:\n\n       SYMBOLIC_NAME SVN_REVNUM TYPE CVSRevision.unique_key()\n\n   For example:\n\n       MY_TAG1 234 O 1.3/foo/bar/baz.txt,v\n       MY_BRANCH3 245 O 1.13/foo/qux/bat.c,v\n       MY_TAG1 241 C 1.4/foo/bar/baz.txt,v\n       MY_BRANCH_BLAH 201 O 1.1/foo/bar/quux.txt,v\n\n   Here is what the columns mean:\n\n   SYMBOLIC_NAME: The name of the branch or tag that starts or ends\n                  in this CVS Revision (There can be multiples per\n                  CVS rev)\n\n   SVN_REVNUM: The Subversion revision number that is the opening or\n               closing for this SYMBOLIC_NAME.\n\n   TYPE: \"O\" for Openings and \"C\" for Closings.\n\n   CVSRevision.unique_key(): This is a unique key that identifies\n                             the CVSRevision where this opening or\n                             closing happened.\n\n   See SymbolingsLogger for more details.\n\nPass 6:\n=======\n\nThis pass merely sorts cvs2svn-symbolic-names.txt into\ncvs2svn-symbolic-names-s.txt.  This orders the file first by symbolic\nname, and second by Subversion revision number, thus grouping all\nopenings and closings for each symbolic name together.\n\nPass 7:\n=======\n\nThis pass iterates through all the lines in\ncvs2svn-symbolic-names-s.txt, writing out a database file mapping\nSYMBOLIC_NAME to the file offset in SYMBOL_OPENINGS_CLOSINGS_SORTED\nwhere SYMBOLIC_NAME is first encountered.  This will allow us to seek\nto the various offsets in the file and sequentially read only the\nopenings and closings that we need.\n\nPass 8:\n=======\n\nThe 8th pass will has very little \"thinking\" to do--it basically going\nopens the svn-nums-to-cvs-revs.db and, starting with Subversion\nrevision 2 (revision 1 creates /trunk, /tags, and /branches), and\nsequentially play out all the commits to either a Subversion\nrepository or to a dumpfile.\n\nIn --dump-only mode, the result of this pass is a Subversion\nrepository dumpfile (suitable for input to 'svnadmin load').  The\ndumpfile is the data's last static stage: last chance to check over\nthe data, run it through svndumpfilter, move the dumpfile to another\nmachine, etc.\n\nHowever, when not in --dump-only mode, no full dumpfile is created for\nsubsequent load into a Subversion repository.  Instead, miniature\ndumpfiles represent a single revision are created, loaded into the\nrepository, and then removed.\n\nIn both modes, the dumpfile revisions are created by walking through\ncvs2svn-data.s-revs.\n\n                  ===============================\n                      Branches and Tags Plan.\n                  ===============================\n\nThis pass is also where tag and branch creation is done.  Since\nsubversion does tags and branches by copying from existing revisions\n(then maybe editing the copy, making subcopies underneath, etc), the\nbig question for cvs2svn is how to achieve the minimum number of\noperations per creation.  For example, if it's possible to get the\nright tag by just copying revision 53, then it's better to do that\nthan, say, copying revision 51 and then sub-copying in bits of\nrevision 52 and 53.\n\nAlso, since CVS does not version symbolic names, there is the\nsecondary question of *when* to create a particular tag or branch.\nFor example, a tag might have been made at any time after the youngest\ncommit included in it, or might even have been made piecemeal; and the\nsame is true for a branch, with the added constraint that for any\nparticular file, the branch must have been created before the first\ncommit on the branch.\n\nAnswering the second question first: cvs2svn creates tags as soon as\npossible and branches as late as possible.\n\nTags are created as soon cvs2svn encounters the last CVS Revision that\nis a source for that tag.  The whole tag is created in one Subversion\ncommit.\n\nFor branches, this is \"just in time\" creation -- the moment it sees\nthe first commit on a branch, it snaps the entire branch into\nexistence (or as much of it as possible), and then outputs the branch\ncommit.\n\nThe reason we say \"as much of it as possible\" is that it's possible to\nhave a branch where some files have branch commits occuring earlier\nthan the other files even have the source revisions from which the\nbranch sprouts (this can happen if the branch was created piecemeal,\nfor example).  In this case, we create as much of the branch as we\ncan, that is, as much of it as there are source revisions available to\ncopy, and leave the rest for later.  \"Later\" might mean just until\nother branch commits come in, or else during a cleanup stage that\nhappens at the end of this pass (about which more later).\n\nHow just-in-time branch creation works:\n\nIn order to make the \"best\" set of copies/deletes when creating a\nbranch, cvs2svn keeps track of two sets of trees while it's making\ncommits:\n\n   1. A skeleton mirror of the subversion repository, that is, an\n      array of revisions, with a tree hanging off each revision.  (The\n      \"array\" is actually implemented as an anydbm database itself,\n      mapping string representations of numbers to root keys.)\n\n   2. A tree for each CVS symbolic name, and the svn file/directory\n      revisions from which various parts of that tree could be copied.\n\nBoth tree sets live in anydbm databases, using the same basic schema:\nunique keys map to marshal.dumps() representations of dictionaries,\nwhich in turn map entry names to other unique keys:\n\n   root_key  ==> { entryname1 : entrykey1, entryname2 : entrykey2, ... }\n   entrykey1 ==> { entrynameX : entrykeyX, ... }\n   entrykey2 ==> { entrynameY : entrykeyY, ... }\n   entrykeyX ==> { etc, etc ...}\n   entrykeyY ==> { etc, etc ...}\n\n(The leaf nodes -- files -- are also dictionaries, for simplicity.)\n\nThe repository mirror allows cvs2svn to remember what paths exist in\nwhat revisions.\n\nFor details on how branches and tags are created, please see the\ndocstring the SymbolingsLogger class (and its methods).\n\n-*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*-\n- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -\n-*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*- -*-\n\nSome older notes and ideas about cvs2svn.  Not deleted, because they\nmay contain suggestions for future improvements in design.\n\n-----------------------------------------------------------------------\n\nAn email from John Gardiner Myers <jgmyers@speakeasy.net> about some\nconsiderations for the tool.\n\n------\nFrom: John Gardiner Myers <jgmyers@speakeasy.net>\nSubject: Thoughts on CVS to SVN conversion\nTo: gstein@lyra.org\nDate: Sun, 15 Apr 2001 17:47:10 -0700\n\nSome things you may want to consider for a CVS to SVN conversion utility:\n\nIf converting a CVS repository to SVN takes days, it would be good for\nthe conversion utility to keep its progress state on disk.  If the\nconversion fails halfway through due to a network outage or power\nfailure, that would allow the conversion to be resumed where it left off\ninstead of having to start over from an empty SVN repository.\n\nIt is a short step from there to allowing periodic updates of a\nread-only SVN repository from a read/write CVS repository.  This allows\nthe more relaxed conversion procedure:\n\n1) Create SVN repository writable only by the conversion tool.\n2) Update SVN repository from CVS repository.\n3) Announce the time of CVS to SVN cutover.\n4) Repeat step (2) as needed.\n5) Disable commits to CVS repository, making it read-only.\n6) Repeat step (2).\n7) Enable commits to SVN repository.\n8) Wait for developers to move their workspaces to SVN.\n9) Decomission the CVS repository.\n\nYou may forward this message or parts of it as you seem fit.\n------\n\n-----------------------------------------------------------------------\n\nFurther design thoughts from Greg Stein <gstein@lyra.org>\n\n* timestamp the beginning of the process. ignore any commits that\n  occur after that timestamp; otherwise, you could miss portions of a\n  commit (e.g. scan A; commit occurs to A and B; scan B; create SVN\n  revision for items in B; we missed A)\n\n* the above timestamp can also be used for John's \"grab any updates\n  that were missed in the previous pass.\"\n\n* for each file processed, watch out for simultaneous commits. this\n  may cause a problem during the reading/scanning/parsing of the file,\n  or the parse succeeds but the results are garbaged. this could be\n  fixed with a CVS lock, but I'd prefer read-only access.\n\n  algorithm: get the mtime before opening the file. if an error occurs\n  during reading, and the mtime has changed, then restart the file. if\n  the read is successful, but the mtime changed, then restart the\n  file.\n\n* use a separate log to track unique branches and non-branched forks\n  of revision history (Q: is it possible to create, say, 1.4.1.3\n  without a \"real\" branch?). this log can then be used to create a\n  /branches/ directory in the SVN repository.\n\n  Note: we want to determine some way to coalesce branches across\n  files. It can't be based on name, though, since the same branch name\n  could be used in multiple places, yet they are semantically\n  different branches. Given files R, S, and T with branch B, we can\n  tie those files' branch B into a \"semantic group\" whenever we see\n  commit groups on a branch touching multiple files. Files that are\n  have a (named) branch but no commits on it are simply ignored. For\n  each \"semantic group\" of a branch, we'd create a branch based on\n  their common ancestor, then make the changes on the children as\n  necessary. For single-file commits to a branch, we could use\n  heuristics (pathname analysis) to add these to a group (and log what\n  we did), or we could put them in a \"reject\" kind of file for a human\n  to tell us what to do (the human would edit a config file of some\n  kind to instruct the converter).\n\n* if we have access to the CVSROOT/history, then we could process tags\n  properly. otherwise, we can only use heuristics or configuration\n  info to group up tags (branches can use commits; there are no\n  commits associated with tags)\n\n* ideally, we store every bit of data from the ,v files to enable a\n  complete restoration of the CVS repository. this could be done by\n  storing properties with CVS revision numbers and stuff (i.e. all\n  metadata not already embodied by SVN would go into properties)\n\n* how do we track the \"states\"? I presume \"dead\" is simply deleting\n  the entry from SVN. what are the other legal states, and do we need\n  to do anything with them?\n\n* where do we put the \"description\"? how about locks, access list,\n  keyword flags, etc.\n\n* note that using something like the SourceForge repository will be an\n  ideal test case. people *move* their repositories there, which means\n  that all kinds of stuff can be found in those repositories, from\n  wherever people used to run them, and under whatever development\n  policies may have been used.\n\n  For example: I found one of the projects with a \"permissions 644;\"\n  line in the \"gnuplot\" repository.  Most RCS releases issue warnings\n  about that (although they properly handle/skip the lines), and CVS\n  ignores RCS newphrases altogether.\n\n"},{"id":"21898","messageId":"1150480925.6983.15.camel@neko.keithp.com","threadId":"4532","inReplyTo":"9e4733910606161044h736c9675kc91ff77904c5a1d0@mail.gmail.com","subject":"Re: Why so much time in the kernel?","fromName":"Keith Packard","fromEmail":"keithp@keithp.com","sentAt":"2006-06-16T18:02:05Z","receivedAt":"2006-06-16T18:02:05Z","isPatch":false,"sender":{"key":"keithp@keithp.com","avatar":"https://gravatar.com/avatar/fa1f479cdd51322fe86215c955a81d296bbf66a1fe625f8a12d87a8ec7faf648?d=mp&s=160"},"body":"On Fri, 2006-06-16 at 13:44 -0400, Jon Smirl wrote:\n\n> I've been extracting versions from cvs and adding them to git now for\n> 2.5 days and the process still isn't finished. It is completely CPU\n> bound. It's just a loop of cvs co, add it to git, make tree, commit,\n> etc.\n\nTo do all of mozilla using parsecvs (even with the quadratic algorithm)\ntakes about three hours on annarchy.freedesktop.org (two dual-core\nOpteron with 4GB memory), including all conversion to packs. The pack\ntime is a tiny fraction of that.\n\n> What about the cvs2svn algorithm described in the attachment? A ram\n> based version could be faster. Compression could be acheived by\n> switching from using the full path to a version to the sha1 for it.\n\nYes, parsecvs currently keeps everything in memory when doing the tree\nconversion, which means it grows to a huge size to compute the full tree\nof revisions. Computing git tree objects from the top down, then\ncomputing commit objects from the bottom up should allow us to free most\nof that during the full branch history computation process. I'm starting\na rewrite of parsecvs to try this approach and see how well it works.\n\nIf you've looked at the parsecvs source code, you'll notice it's a mess\nat present; I started by attempting to do pair-wise tree merges in a\nmistaken attempt to convert a linear term to log. Hacking that code into\nits present form should be viewed more as a demonstration of how the\noverall process can work, not as an optimal expression of the algorithm.\n\n-- \nkeith.packard@intel.com\n"},{"id":"21899","messageId":"Pine.LNX.4.64.0606161406260.16002@localhost.localdomain","threadId":"4532","inReplyTo":"9e4733910606161044h736c9675kc91ff77904c5a1d0@mail.gmail.com","subject":"Re: Why so much time in the kernel?","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-06-16T18:07:08Z","receivedAt":"2006-06-16T18:07:08Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 16 Jun 2006, Jon Smirl wrote:\n\n> On 6/16/06, Keith Packard <keithp@keithp.com> wrote:\n> > On Fri, 2006-06-16 at 13:00 -0400, Jon Smirl wrote:\n> > > Is it a crazy idea to read the cvs files, compute an sha1 on each\n> > > expanded delta and then write the delta straight into a pack file? Are\n> > > the cvs and git delta formats the same? What about CVS's forward and\n> > > reverse delta use?\n> > \n> > At this point, merging blobs into packs isn't a significant part of the\n> > computational cost. parsecvs is spending all of its time in the\n> > quadratic traversal of the diff chains; fixing that to emit all of the\n> > versions in a single pass should speed up that part of the conversion\n> > process dramatically.\n> \n> That's not true for the state I am in. cvsps can compute the changeset\n> tree in 15 minutes, cvs2svn can compute their version in a couple of\n> hours. cvs2svn builds a much better tree.\n\nDid you try parsecvs recently?\n\n\nNicolas\n"},{"id":"21902","messageId":"Pine.LNX.4.64.0606161132160.5498@g5.osdl.org","threadId":"4532","inReplyTo":"9e4733910606161000t53328571u10a350eca894ccdc@mail.gmail.com","subject":"Re: Why so much time in the kernel?","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-16T18:32:42Z","receivedAt":"2006-06-16T18:32:42Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 16 Jun 2006, Jon Smirl wrote:\n>\n> Is it a crazy idea to read the cvs files, compute an sha1 on each\n> expanded delta and then write the delta straight into a pack file? Are\n> the cvs and git delta formats the same? What about CVS's forward and\n> reverse delta use? While this is going on, track the\n> branches/changsets in memory and then finish up by writing these trees\n> into the pack file too. This should take no more ram than cvsps needs\n> currently.\n\nWhat you want is parsecvs, which does it much more like that.\n\n\t\tLinus\n"}]}