{"thread":{"id":"27340","subject":"AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","startedAt":"2011-05-12T17:15:03Z","lastAt":"2011-05-13T19:18:03Z","messageCount":18,"participants":["Andrew Lutomirski","Linus Torvalds","Johannes Sixt","Christian Couder","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"167749","messageId":"BANLkTi=kb_m-CfrpnD8qQTVYLGaDdgy_tg@mail.gmail.com","threadId":"27340","inReplyTo":null,"subject":"AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Andrew Lutomirski","fromEmail":"luto@mit.edu","sentAt":"2011-05-12T17:15:03Z","receivedAt":"2011-05-12T17:15:03Z","isPatch":false,"sender":{"key":"luto@mit.edu","avatar":null},"body":"On Thu, May 12, 2011 at 9:31 AM, Andrew Lutomirski wrote:\n> I just installed 9f381a6 (-linus from yesterday) on my Sandy Bridge\n> desktop, and it locks up hard within a few seconds of logging in.\n> netconsole says:\n>\n> [  506.629723] block group 24725422080 has an wrong amount of free space\n> [  506.629723] block group 24725422080 has an wrong amount of free space\n> [  506.808501] fuse init (API version 7.16)\n> [  506.819996] SELinux: initialized (dev fuse, type fuse), uses genfs_contexts\n> [  506.829847] SELinux: initialized (dev fusectl, type fusectl), uses\n> genfs_contexts\n> [  506.808501] fuse init (API version 7.16)\n> [  506.819996] SELinux: initialized (dev fuse, type fuse), uses genfs_contexts\n> [  506.829847] SELinux: initialized (dev fusectl, type fusectl), uses\n> genfs_contexts\n>\n> If it's any help, the system is locked so hard that the reset button\n> doesn't work.  It's an Intel DQ67SW board, which apparently doesn't\n> have the most reliable reset button in the world :)\n>\n> 2.6.38.{4,5,6} are all rock-solid on this box.\n>\n> I've started bisecting, but I don't expect to finish today.  I need to\n> do some work other than kernel hacking...\n\nOK, this sucks. In the course of bisecting this, I've hit two other\napparently unrelated bugs that prevent my from testing large numbers\nof kernels. Do I have two questions:\n\n1. Anyone have any ideas from looking at the log?\n\nIt looks like most of what's left is network code, so cc netdev.\n\n2. The !&$#@ bisection is skipping all over the place. I've seen\n2.6.37 versions and all manner of -rc's out of order. Linus, and\nother people who like pontificating about git bisection: is there any\nway to get the bisection to follow Linus' tree? I think that if\nbisect could be persuaded to consider only changes that are reached by\nfollowing only the *first* merge parent all the way from the bad\nrevision to the good revision, then the bisection would build versions\nthat were at least good enough for Linus to pull and might have fewer\nbisection-killing bugs.\n\n(This isn't a new idea [1], and git rev-list --bisect --first-parent\nisn't so bad except that it doesn't bisect.)\n\n\n\nHere's the log.\n\n$ git bisect log\n# bad: [9f381a61f58bb6487c93ce2233bb9992f8ea9211] Merge\ngit://git.kernel.org/pub/scm/linux/kernel/git/davem/net-2.6\n# good: [521cb40b0c44418a4fd36dc633f575813d59a43d] Linux 2.6.38\ngit bisect start 'HEAD' 'v2.6.38'\n# skip: [6899608533410557e6698cb9d4ff6df553916e98] Merge branch\n'for-linus' of git://codeaurora.org/quic/kernel/davidb/linux-msm\n# ******* This revision didn't build due to PSTORE.\n# ******* Fixed config for the rest but no point in retrying...\ngit bisect skip 6899608533410557e6698cb9d4ff6df553916e98\n# bad: [d3e458d78167102cc961237cfceef6fffc80c0b3] Merge branch\n'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tiwai/sound-2.6\ngit bisect bad d3e458d78167102cc961237cfceef6fffc80c0b3\n# good: [6445ced8670f37cfc2c5e24a9de9b413dbfc788d] Merge branch\n'staging-next' of\ngit://git.kernel.org/pub/scm/linux/kernel/git/gregkh/staging-2.6\ngit bisect good 6445ced8670f37cfc2c5e24a9de9b413dbfc788d\n# bad: [40c7f2112ce18fa5eb6dc209c50dd0f046790191] Merge branch\n'drm-core-next' of\ngit://git.kernel.org/pub/scm/linux/kernel/git/airlied/drm-2.6\ngit bisect bad 40c7f2112ce18fa5eb6dc209c50dd0f046790191\n# bad: [23b41168fc942a4a041325a04ecc1bd17d031a3e] netdevice: make\ninitial group visible to userspace\ngit bisect bad 23b41168fc942a4a041325a04ecc1bd17d031a3e\n# bad: [c0c84ef5c130f8871adbdaac2ba824b9195cb6d9] Merge branch\n'master' of git://git.kernel.org/pub/scm/linux/kernel/git/linville/wireless-next-2.6\ngit bisect bad c0c84ef5c130f8871adbdaac2ba824b9195cb6d9\n# skip: [3ad97fbcc233a295f2ccc2c6bdeb32323e360a5e] mac80211: remove\nunneeded check\n# ******* This revision hangs at edd=off\ngit bisect skip 3ad97fbcc233a295f2ccc2c6bdeb32323e360a5e\n# skip: [5bec3e5ade813ee4bdbab03af1bb6f85859272ea] ath9k: fix tx queue\nindex confusion in debugfs code\n# ******* This revision hangs at edd=off\ngit bisect skip 5bec3e5ade813ee4bdbab03af1bb6f85859272ea\n# skip: [c210de8f88215db31cf3529c9763fc3124d6e09d] ath5k: Fix fast\nchannel switching\n# ******* This revision hangs at edd=off\ngit bisect skip c210de8f88215db31cf3529c9763fc3124d6e09d\n\n# ******* For added fun, 479600777bb588724d044815415f7d708d06644b gets\nstuck in systemd initialization.\n\n--Andy\n"},{"id":"167751","messageId":"BANLkTi=YDZa+BRaG90vJsjrT9VxgySrDRQ@mail.gmail.com","threadId":"27340","inReplyTo":"BANLkTi=kb_m-CfrpnD8qQTVYLGaDdgy_tg@mail.gmail.com","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2011-05-12T17:37:53Z","receivedAt":"2011-05-12T17:37:53Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Thu, May 12, 2011 at 10:15 AM, Andrew Lutomirski wrote:\n>\n> OK, this sucks.  In the course of bisecting this, I've hit two other\n> apparently unrelated bugs that prevent my from testing large numbers\n> of kernels.  Do I have two questions:\n>\n> 1. Anyone have any ideas from looking at the log?\n\nNope, that doesn't look very helpful.\n\n> 2.  The !&$#@ bisection is skipping all over the place.  I've seen\n> 2.6.37 versions and all manner of -rc's out of order.\n\nThat's the _point_ of bisection. It jumps around. You can start off\ntrying to pick points on my development tree, but I only have a\nhundred merges or so. You're going to start delving into the actual\ndevelopment versions very quickly. And if you don't do it early,\nbisection is going to be much much slower, because it's not going to\npick half-way points.\n\nSo bisection works so well exactly because it picks points that are\nfar away from each other, and you should just totally ignore the\nversion number. It's meaningless. Looking at it just confuses you.\nDon't do it.\n\nNow, \"pick stable points\" would obviously be nice, but that is going\nto have to be manual. You can certainly make some helper scripts, and\nthat's where that \"--first-parent\" thing comes in. So if you want to,\njust use \"git bisect reset\" to the commit you want to test.\n\nIf you think it's networking, for example, and you've bisected into\nthere but aren't sure, do \"gitk --bisect\", find the point where I\nmerge, and pick that (and my parent), and \"git bisect reset\" those\npoints. That way you can verify that it's the networking merge (or\nverify that it isn't).\n\n Linus\n"},{"id":"167756","messageId":"4DCC2CFD.4010807@kdbg.org","threadId":"27340","inReplyTo":"BANLkTi=YDZa+BRaG90vJsjrT9VxgySrDRQ@mail.gmail.com","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2011-05-12T18:54:53Z","receivedAt":"2011-05-12T18:54:53Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 12.05.2011 19:37, schrieb Linus Torvalds:\n> If you think it's networking, for example, and you've bisected into\n> there but aren't sure, do \"gitk --bisect\", find the point where I\n> merge, and pick that (and my parent), and \"git bisect reset\" those\n> points.\n\nExcept that you should git reset --hard; git bisect reset gets you out\nof bisect-mode, no?\n\n-- Hannes\n"},{"id":"167758","messageId":"BANLkTimuSNHm_-tPV2EQZp6acDsei9f2Mw@mail.gmail.com","threadId":"27340","inReplyTo":"4DCC2CFD.4010807@kdbg.org","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2011-05-12T19:17:00Z","receivedAt":"2011-05-12T19:17:00Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Thu, May 12, 2011 at 11:54 AM, Johannes Sixt wrote:\n>\n> Except that you should git reset --hard; git bisect reset gets you out\n> of bisect-mode, no?\n\nYeah, sorry, my bad.\n\n Linus\n"},{"id":"167771","messageId":"BANLkTikMeyRTOB9q4PEAYWnZRZfk3wg=kQ@mail.gmail.com","threadId":"27340","inReplyTo":"BANLkTi=kb_m-CfrpnD8qQTVYLGaDdgy_tg@mail.gmail.com","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2011-05-13T08:20:54Z","receivedAt":"2011-05-13T08:20:54Z","isPatch":false,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Thu, May 12, 2011 at 7:15 PM, Andrew Lutomirski wrote:\n>\n> OK, this sucks.  In the course of bisecting this, I've hit two other\n> apparently unrelated bugs that prevent my from testing large numbers\n> of kernels.  Do I have two questions:\n>\n> 1. Anyone have any ideas from looking at the log?\n>\n> It looks like most of what's left is network code, so cc netdev.\n>\n> 2.  The !&$#@ bisection is skipping all over the place.  I've seen\n> 2.6.37 versions and all manner of -rc's out of order.  Linus, and\n> other people who like pontificating about git bisection: is there any\n> way to get the bisection to follow Linus' tree?  I think that if\n> bisect could be persuaded to consider only changes that are reached by\n> following only the *first* merge parent all the way from the bad\n> revision to the good revision, then the bisection would build versions\n> that were at least good enough for Linus to pull and might have fewer\n> bisection-killing bugs.\n>\n> (This isn't a new idea [1], and git rev-list --bisect --first-parent\n> isn't so bad except that it doesn't bisect.)\n\nDid you forget to put the reference [1] in your email? Was it this one\nyou were thinking about:\n\nhttp://thread.gmane.org/gmane.comp.version-control.git/165433/\n\n?\n\nThanks,\nChristian.\n"},{"id":"167800","messageId":"BANLkTi=dL+KyQ3Bm58_Uj4LP9WSpbzAfJA@mail.gmail.com","threadId":"27340","inReplyTo":"BANLkTikMeyRTOB9q4PEAYWnZRZfk3wg=kQ@mail.gmail.com","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Andrew Lutomirski","fromEmail":"luto@mit.edu","sentAt":"2011-05-13T13:38:18Z","receivedAt":"2011-05-13T13:38:18Z","isPatch":false,"sender":{"key":"luto@mit.edu","avatar":null},"body":"On Fri, May 13, 2011 at 4:20 AM, Christian Couder\n wrote:\n> On Thu, May 12, 2011 at 7:15 PM, Andrew Lutomirski wrote:\n>>\n>> OK, this sucks.  In the course of bisecting this, I've hit two other\n>> apparently unrelated bugs that prevent my from testing large numbers\n>> of kernels.  Do I have two questions:\n>>\n>> 1. Anyone have any ideas from looking at the log?\n>>\n>> It looks like most of what's left is network code, so cc netdev.\n>>\n>> 2.  The !&$#@ bisection is skipping all over the place.  I've seen\n>> 2.6.37 versions and all manner of -rc's out of order.  Linus, and\n>> other people who like pontificating about git bisection: is there any\n>> way to get the bisection to follow Linus' tree?  I think that if\n>> bisect could be persuaded to consider only changes that are reached by\n>> following only the *first* merge parent all the way from the bad\n>> revision to the good revision, then the bisection would build versions\n>> that were at least good enough for Linus to pull and might have fewer\n>> bisection-killing bugs.\n>>\n>> (This isn't a new idea [1], and git rev-list --bisect --first-parent\n>> isn't so bad except that it doesn't bisect.)\n>\n> Did you forget to put the reference [1] in your email? Was it this one\n> you were thinking about:\n>\n> http://thread.gmane.org/gmane.comp.version-control.git/165433/\n\nNo, it was this:\n\nhttp://stackoverflow.com/questions/5638211/how-do-you-get-git-bisect-to-ignore-merged-branches\n\n--Andy\n\n>\n> ?\n>\n> Thanks,\n> Christian.\n>\n"},{"id":"167801","messageId":"BANLkTinoGfj1NUzTveSH0vgwZczCaFr8HA@mail.gmail.com","threadId":"27340","inReplyTo":"BANLkTi=YDZa+BRaG90vJsjrT9VxgySrDRQ@mail.gmail.com","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Andrew Lutomirski","fromEmail":"luto@mit.edu","sentAt":"2011-05-13T13:39:14Z","receivedAt":"2011-05-13T13:39:14Z","isPatch":false,"sender":{"key":"luto@mit.edu","avatar":null},"body":"[resend because the Android gmail client apparently generates HTML\nemails even for plain text]\n\nOn Thu, May 12, 2011 at 1:37 PM, Linus Torvalds\n wrote:\n> On Thu, May 12, 2011 at 10:15 AM, Andrew Lutomirski wrote:\n>>\n>> OK, this sucks.  In the course of bisecting this, I've hit two other\n>> apparently unrelated bugs that prevent my from testing large numbers\n>> of kernels.  Do I have two questions:\n>>\n>> 1. Anyone have any ideas from looking at the log?\n>\n> Nope, that doesn't look very helpful.\n>\n>> 2.  The !&$#@ bisection is skipping all over the place.  I've seen\n>> 2.6.37 versions and all manner of -rc's out of order.\n>\n> That's the _point_ of bisection. It jumps around. You can start off\n> trying to pick points on my development tree, but I only have a\n> hundred merges or so. You're going to start delving into the actual\n> development versions very quickly. And if you don't do it early,\n> bisection is going to be much much slower, because it's not going to\n> pick half-way points.\n>\n> So bisection works so well exactly because it picks points that are\n> far away from each other, and you should just totally ignore the\n> version number. It's meaningless. Looking at it just confuses you.\n> Don't do it.\n>\n\nI actually had better results looking at the version number, saying\n\"blech\", and running git merge v2.6.38. (git bisect good gets a\nlittle confused if I feed it the merge result, but I can just lie.)\n\nAnyway, I must have made a mistake somewhere. The regression is in\ndrm (presumably i915) and it has a new thread now.\n\n--Andy\n"},{"id":"167805","messageId":"BANLkTi=NdVUUZ=_bACzyeMGS3JWs0EMbWA@mail.gmail.com","threadId":"27340","inReplyTo":"BANLkTi=dL+KyQ3Bm58_Uj4LP9WSpbzAfJA@mail.gmail.com","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Andrew Lutomirski","fromEmail":"luto@mit.edu","sentAt":"2011-05-13T14:56:54Z","receivedAt":"2011-05-13T14:56:54Z","isPatch":false,"sender":{"key":"luto@mit.edu","avatar":null},"body":"On Fri, May 13, 2011 at 9:38 AM, Andrew Lutomirski wrote:\n> On Fri, May 13, 2011 at 4:20 AM, Christian Couder\n> wrote:\n>> On Thu, May 12, 2011 at 7:15 PM, Andrew Lutomirski wrote:\n>>>\n>>> OK, this sucks.  In the course of bisecting this, I've hit two other\n>>> apparently unrelated bugs that prevent my from testing large numbers\n>>> of kernels.  Do I have two questions:\n>>>\n>>> 1. Anyone have any ideas from looking at the log?\n>>>\n>>> It looks like most of what's left is network code, so cc netdev.\n>>>\n>>> 2.  The !&$#@ bisection is skipping all over the place.  I've seen\n>>> 2.6.37 versions and all manner of -rc's out of order.  Linus, and\n>>> other people who like pontificating about git bisection: is there any\n>>> way to get the bisection to follow Linus' tree?  I think that if\n>>> bisect could be persuaded to consider only changes that are reached by\n>>> following only the *first* merge parent all the way from the bad\n>>> revision to the good revision, then the bisection would build versions\n>>> that were at least good enough for Linus to pull and might have fewer\n>>> bisection-killing bugs.\n>>>\n>>> (This isn't a new idea [1], and git rev-list --bisect --first-parent\n>>> isn't so bad except that it doesn't bisect.)\n>>\n>> Did you forget to put the reference [1] in your email? Was it this one\n>> you were thinking about:\n>>\n>> http://thread.gmane.org/gmane.comp.version-control.git/165433/\n>\n> No, it was this:\n>\n> http://stackoverflow.com/questions/5638211/how-do-you-get-git-bisect-to-ignore-merged-branches\n>\n\nSadly even that's not enough. I finished the bisection (by\nstandard-ish techniques but with a bit of overriding of git bisect's\nchoices and occasional merging of newer versions of -linus to get\nsomething that would boot) and it pointed to a commit that wasn't the\nculprit.\n\nThe problem is that 2.6.39-rc7 is bad, 2.6.38 (and 2.6.38.{5,6}) is\ngood, but 2.6.38-rc5 is bad and fails identically to 2.6.39-rc7. I\nthink that git bisect makes the assumption that ancestors of a good\ncommit are good, and that just isn't true for this bug.\n\nSo what I really want is a fancy version of git bisect that makes no\nassumptions about the relationship of good and bad commits in the\ngraph and just finds me a commit that is bad but for which all parents\nare good or vice versa.\n\nI'm currently bisecting the other way to find the commit before 2.6.38\nthat fixed the bug, since there's presumably less churn there than in\nthe early bits of 2.6.39.\n\n--Andy\n"},{"id":"167807","messageId":"BANLkTimE2GkkhcFZtNrYZASWp0LDhUx=GQ@mail.gmail.com","threadId":"27340","inReplyTo":"BANLkTi=NdVUUZ=_bACzyeMGS3JWs0EMbWA@mail.gmail.com","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2011-05-13T16:11:31Z","receivedAt":"2011-05-13T16:11:31Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Fri, May 13, 2011 at 7:56 AM, Andrew Lutomirski wrote:\n>\n> So what I really want is a fancy version of git bisect that makes no\n> assumptions about the relationship of good and bad commits in the\n> graph and just finds me a commit that is bad but for which all parents\n> are good or vice versa.\n\nEhh. That's the \"non-fancy\" way of testing, I'm afraid: if you cannot\nmake assumption about the relationship between good and bad commits,\nthen you have to test _every_ commit.\n\nSo yes, bisection has its problems. But they really do come from the\nfact that it's very efficient. When you have (on average) about ten\nthousand commits between releases, you have to make assumptions about\nthe relationships. But once you do that, the efficiency also results\nin a certain fragility.\n\nThink of it as a compression method: it generates the smallest\npossible set of test points for you. But it's a \"lossy\" compression -\nyou don't test everything. And it's extreme: it boils down 10k commit\nevents to about 13 bisection events. If anything goes wrong (like the\nbug not being entirely repeatable, or the bug comes and goes), it will\ngive the wrong answer.\n\nThe good news is that _usually_ it works really well. And when the\nchoice is between \"works really well for 10k commits but can have\nproblems\" and \"you need to test all 10k commits\", the \"can have\nproblems\" part turns out to be a pretty small downside ;)\n\n Linus\n"},{"id":"167808","messageId":"BANLkTikDafbCnsXPoidnMBAE0qtd9aC4oQ@mail.gmail.com","threadId":"27340","inReplyTo":"BANLkTimE2GkkhcFZtNrYZASWp0LDhUx=GQ@mail.gmail.com","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Andrew Lutomirski","fromEmail":"luto@mit.edu","sentAt":"2011-05-13T16:13:23Z","receivedAt":"2011-05-13T16:13:23Z","isPatch":false,"sender":{"key":"luto@mit.edu","avatar":null},"body":"On Fri, May 13, 2011 at 12:11 PM, Linus Torvalds\n wrote:\n> On Fri, May 13, 2011 at 7:56 AM, Andrew Lutomirski wrote:\n>>\n>> So what I really want is a fancy version of git bisect that makes no\n>> assumptions about the relationship of good and bad commits in the\n>> graph and just finds me a commit that is bad but for which all parents\n>> are good or vice versa.\n>\n> Ehh. That's the \"non-fancy\" way of testing, I'm afraid: if you cannot\n> make assumption about the relationship between good and bad commits,\n> then you have to test _every_ commit.\n>\n> So yes, bisection has its problems. But they really do come from the\n> fact that it's very efficient. When you have (on average) about ten\n> thousand commits between releases, you have to make assumptions about\n> the relationships. But once you do that, the efficiency also results\n> in a certain fragility.\n>\n> Think of it as a compression method: it generates the smallest\n> possible set of test points for you. But it's a \"lossy\" compression -\n> you don't test everything. And it's extreme: it boils down 10k commit\n> events to about 13 bisection events. If anything goes wrong (like the\n> bug not being entirely repeatable, or the bug comes and goes), it will\n> give the wrong answer.\n>\n> The good news is that _usually_ it works really well. And when the\n> choice is between \"works really well for 10k commits but can have\n> problems\" and \"you need to test all 10k commits\", the \"can have\n> problems\" part turns out to be a pretty small downside ;)\n\nIn conclusion, I found the problem. It's a clusterfuck and I think\nthere's no way that any bisection tool under any sane assumptions\ncould have found it. Patch coming in a couple seconds b/c I think it\nneeds to go in to 2.6.39.\n\n--Andy\n\n>\n>                                Linus\n>\n"},{"id":"167817","messageId":"BANLkTinyzBnksHk_rt8K2pmg90q5WyZX3w@mail.gmail.com","threadId":"27340","inReplyTo":"BANLkTimE2GkkhcFZtNrYZASWp0LDhUx=GQ@mail.gmail.com","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Andrew Lutomirski","fromEmail":"luto@mit.edu","sentAt":"2011-05-13T17:24:02Z","receivedAt":"2011-05-13T17:24:02Z","isPatch":false,"sender":{"key":"luto@mit.edu","avatar":null},"body":"On Fri, May 13, 2011 at 12:11 PM, Linus Torvalds\n wrote:\n> On Fri, May 13, 2011 at 7:56 AM, Andrew Lutomirski wrote:\n>>\n>> So what I really want is a fancy version of git bisect that makes no\n>> assumptions about the relationship of good and bad commits in the\n>> graph and just finds me a commit that is bad but for which all parents\n>> are good or vice versa.\n>\n> Ehh. That's the \"non-fancy\" way of testing, I'm afraid: if you cannot\n> make assumption about the relationship between good and bad commits,\n> then you have to test _every_ commit.\n\nActually, I disagree. I suspect, although I haven't convinced myself\nvery well yet, that if you assume that the bug was caused one or more\ntimes by some commit C that works but where all of C's parents don't\nwork (or vice versa), then there exists an algorithm that, at least\nfor most histories, will find such a commit in polylog tries given a\nstarting commit that works and another one that fails. But I have to\ndo real work before I think too much more about that.\n\nThat being said, even the fairly weak requirement I wanted wasn't really true...\n\n[I said in a different email:]\n>\n> In conclusion, I found the problem. It's a clusterfuck and I think\n> there's no way that any bisection tool under any sane assumptions\n> could have found it. Patch coming in a couple seconds b/c I think it\n> needs to go in to 2.6.39.\n\nI should clarify what the problem was for people who don't want to dig\naround the archives:\n\nI have a Sandy Bridge box, which means that I need to run a recent\nkernel for things to work decently. The bug was introduced once way\nback in the depths of time (i.e. before any kernel that I ever tried\nsince I got the machine). It was fixed shortly before 2.6.38 by\ncommit A. It was reintroduced in a merge B that was a little past A.\nB went in to 2.6.39-something via airlied's tree. B's other parent\nwas bad because it didn't contain A. It looks like this:\n\n-------------------------------.\n \\\n(bad pre-2.6.38-rc2)--. \\ (etc)\n \\ \\\n .--(good)-----B--(bad)-. \\\n / \\ \\\n(bad)---A--(good)--v2.6.38---------x-x-v2.6.39-rc7\n\n\n(A is a1656b9090f7008d2941c314f5a64724bea2ae37 and B is\n47ae63e0c2e5fdb582d471dc906eb29be94c732f)\n\n\nThe offending commit is B, but the bisection is screwed, because the\nseries of nonworking commits dangling off B looks just like any other\nseries of nonworking commits like the top line that have nothing to do\nwith the problem. Sure enough, my bisection ended up wandering into\ndark corners (like the networking tree), which were innocent.\n\nI found the problem by manually bisecting the --first-parent chain\nfrom v2.6.39-rc7 to v2.6.38 to figure out that the problem came from a\ndrm merge and then noticing that something was screwed up when the\nbisection pointed to a commit (in the right driver, even) that wasn't\nthe problem. (I even tried reverting it to no avail.) Bisection was\n*sure* it was the problem, though, because its parent was in v2.6.38.\n\nI thought that maybe the problem had been introduced more than once,\nso I tried v2.6.38-rc5, and it *failed*. (That's what caused a lot of\nmy confusion the first time around -- lots of commits that were \"good\"\n(in the sense that they would work if merged correctly into the\nv2.6.39 branch before B got there) failed instead.\n\nSo I bisected between v2.6.38 and v2.6.38-rc5 to find the commit that\nfixed the problem, since there had to be something. Once I found it,\na bunch of confused calls to git blame found the merge that undid the\nfix.\n\n> Think of it as a compression method: it generates the smallest\n> possible set of test points for you. But it's a \"lossy\" compression -\n> you don't test everything. And it's extreme: it boils down 10k commit\n> events to about 13 bisection events. If anything goes wrong (like the\n> bug not being entirely repeatable, or the bug comes and goes), it will\n> give the wrong answer.\n\nAs I just learned :)\n\n--Andy\n"},{"id":"167819","messageId":"BANLkTinVT=9+-HhwXcyLBwrnhX9F9Qz3ww@mail.gmail.com","threadId":"27340","inReplyTo":"BANLkTinyzBnksHk_rt8K2pmg90q5WyZX3w@mail.gmail.com","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2011-05-13T17:54:41Z","receivedAt":"2011-05-13T17:54:41Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Fri, May 13, 2011 at 10:24 AM, Andrew Lutomirski wrote:\n> On Fri, May 13, 2011 at 12:11 PM, Linus Torvalds\n> wrote:\n>>\n>> Ehh. That's the \"non-fancy\" way of testing, I'm afraid: if you cannot\n>> make assumption about the relationship between good and bad commits,\n>> then you have to test _every_ commit.\n>\n> Actually, I disagree.  I suspect, although I haven't convinced myself\n> very well yet, that if you assume that the bug was caused one or more\n> times by some commit C that works but where all of C's parents don't\n> work (or vice versa), then there exists an algorithm that, at least\n> for most histories, will find such a commit in polylog tries given a\n> starting commit that works and another one that fails.  But I have to\n> do real work before I think too much more about that.\n\nSo I do think we could probably add a few more concepts to git-bisect\nthat could be quite useful.\n\nFor example, in your case, since you had certain requirements of\nsupport that simply didn't exist earlier, something like\n\n git bisect requires v2.6.38\n\nwould have been really useful - telling git bisect that any commit\nthat cannot reach that required commit is not even worth testing.\n\nThat would still have been rather dangerous thing to say (it's not\nactually a _true_ requirement: there may well be points in the i915\ndevelopment tree that still had all the required sandybridge support,\nbut hadn't been merged into 38 yet), but it would have limited your\nbisection space to a degree that would have been useful.\n\nSo if that \"requirement\" wasn't actually true (and the bug was\nintroduced by a commit that was based on something before v2.6.38),\nthe bisect would have pinpointed the particular merge that brought the\ncommit in. So \"pinpointed\" might in this case mean \"thousands of\ncommits\", but it would still likely be a very useful end result.\n\nAnd no, git-bisect doesn't have that kind of concept. And it could\npotentially be quite useful.\n\nAnother thing that would be useful for git bisect would be the notion\nof \"git bisect cherry-pick\", which is useful for applying particular\ncommits that fix unrelated problems _while_ you bisect the one you're\ninterested in. You can currently do it manually, or by playing around\nwith 'git bisect run' and making hacky stuff, but it's a pain. You\ndidn't hit that case, but it's actually the most common problem there\nis with git bisect - having multiple _different_ bugs, rather than\nhaving the same bug show up twice.\n\nYet another issue - related to the \"multiple different bugs\" thing -\nis exactly the fact that 'git bisect' only has a concept of a \"single\nbug\". You cannot say \"this revision is good, that revision has bug A,\nthat revision has bug B\", where bug A might hide bug B and vice versa.\nIf you have multiple bugs and they change symptoms, it can be _really_\npainful to bisect things, because you have to basically always pick\none of them, and then re-do the whole thing after you've found the\nfirst one.\n\nSo there's no question that there might not be things we would want to\ndo with \"git bisect\".\n\nOf course, one of the real advantages of \"git bisect\" is that for many\ncases it's pretty simple. You can (and we absolutely rely on this)\nhave normal users that have _no_ idea about kernel development do a\nbisect - the only thing they need to be able to do is to compile and\ninstall their own kernel, and reliably recognize the problematic\nsymptoms.\n\nAnd that's really the biggest advantage of bisecting - it doesn't\n_always_ work, but it works often enough, and it's totally mindless.\nSo clever features and extra complexity and smart things that can be\ndone with it is often not all that useful - because a major user base\nis very much the \"I don't know kernel development, but I want to help\nand my machine shows badness\" kind of situation.\n\n Linus\n"},{"id":"167821","messageId":"4DCD79A0.7000500@kdbg.org","threadId":"27340","inReplyTo":"BANLkTinVT=9+-HhwXcyLBwrnhX9F9Qz3ww@mail.gmail.com","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2011-05-13T18:34:08Z","receivedAt":"2011-05-13T18:34:08Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 13.05.2011 19:54, schrieb Linus Torvalds:\n> For example, in your case, since you had certain requirements of\n> support that simply didn't exist earlier, something like\n> \n> git bisect requires v2.6.38\n> \n> would have been really useful - telling git bisect that any commit\n> that cannot reach that required commit is not even worth testing.\n\nYou can already have this with\n\n git bisect good v2.6.38\n\nIt sounds a bit unintuitive, but with a slight mind-twist it can even be\nregarded as correct in a mathematical sense: when the precondition is\nfalse, the result is true. ;-)\n\n-- Hannes\n"},{"id":"167822","messageId":"BANLkTi=smoaARKyzWxFjid-E7qehmyAX8w@mail.gmail.com","threadId":"27340","inReplyTo":"4DCD79A0.7000500@kdbg.org","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2011-05-13T18:41:46Z","receivedAt":"2011-05-13T18:41:46Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Fri, May 13, 2011 at 11:34 AM, Johannes Sixt wrote:\n> Am 13.05.2011 19:54, schrieb Linus Torvalds:\n>> For example, in your case, since you had certain requirements of\n>> support that simply didn't exist earlier, something like\n>>\n>>    git bisect requires v2.6.38\n>>\n>> would have been really useful - telling git bisect that any commit\n>> that cannot reach that required commit is not even worth testing.\n>\n> You can already have this with\n>\n>   git bisect good v2.6.38\n>\n> It sounds a bit unintuitive, but with a slight mind-twist it can even be\n> regarded as correct in a mathematical sense: when the precondition is\n> false, the result is true. ;-)\n\nNo. That's not the same thing AT ALL.\n\nWhen you say that v2.6.38 is good, that means that everything that can\nbe reached from 2.6.38 is good.\n\nNOT AT ALL the same thing as \"git bisect requires v2.6.38\" would be.\n\nThe \"requires v2.6.38\" would basically say that anything that doesn't\ncontain v2.6.38 is \"off-limits\". It's fine to call them \"good\", but\nthat's not the same thing as \"git bisect good v2.6.38\".\n\nWhy?\n\nThink about it. It's the \"reachable from v2.6.38\" vs \"cannot reach\nv2.6.38\" difference. That's a HUGE difference.\n\n Linus\n"},{"id":"167823","messageId":"4DCD7CBE.9010409@kdbg.org","threadId":"27340","inReplyTo":"BANLkTi=smoaARKyzWxFjid-E7qehmyAX8w@mail.gmail.com","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Johannes Sixt","fromEmail":"j6t@kdbg.org","sentAt":"2011-05-13T18:47:26Z","receivedAt":"2011-05-13T18:47:26Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Am 13.05.2011 20:41, schrieb Linus Torvalds:\n> On Fri, May 13, 2011 at 11:34 AM, Johannes Sixt wrote:\n>> git bisect good v2.6.38\n> \n> When you say that v2.6.38 is good, that means that everything that can\n> be reached from 2.6.38 is good.\n> \n> NOT AT ALL the same thing as \"git bisect requires v2.6.38\" would be.\n> \n> Think about it. It's the \"reachable from v2.6.38\" vs \"cannot reach\n> v2.6.38\" difference. That's a HUGE difference.\n\nOops, you're right, I got it upside-down.\n\nThanks,\n-- Hannes\n"},{"id":"167824","messageId":"7vliya77xl.fsf@alter.siamese.dyndns.org","threadId":"27340","inReplyTo":"BANLkTi=smoaARKyzWxFjid-E7qehmyAX8w@mail.gmail.com","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-05-13T18:48:54Z","receivedAt":"2011-05-13T18:48:54Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> When you say that v2.6.38 is good, that means that everything that can\n> be reached from 2.6.38 is good.\n>\n> NOT AT ALL the same thing as \"git bisect requires v2.6.38\" would be.\n>\n> The \"requires v2.6.38\" would basically say that anything that doesn't\n> contain v2.6.38 is \"off-limits\". It's fine to call them \"good\", but\n> that's not the same thing as \"git bisect good v2.6.38\".\n>\n> Why?\n>\n> Think about it. It's the \"reachable from v2.6.38\" vs \"cannot reach\n> v2.6.38\" difference. That's a HUGE difference.\n\nCould you please clarify \"off-limits\"?\n\nDo you mean \"anything before v2.6.38 did not even have this feature, so\nthe result of testing a version in that range does not give us any\ninformation\"? The feature didn't even exist, so a bug can never trigger,\nand seeing \"good\" from such a version does not mean everything reachable\nfrom it is good? Upon seeing \"bad\" result from a version before v2.6.38,\nwhat can we conclude? The breakage cannot possibly come from the feature\nthat is being checked, so the procedure to check itself is busted?\n"},{"id":"167825","messageId":"BANLkTi=dFhxWHHPiYi6P7Mn45J7dZXn=AQ@mail.gmail.com","threadId":"27340","inReplyTo":"7vliya77xl.fsf@alter.siamese.dyndns.org","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Andrew Lutomirski","fromEmail":"luto@mit.edu","sentAt":"2011-05-13T18:55:03Z","receivedAt":"2011-05-13T18:55:03Z","isPatch":false,"sender":{"key":"luto@mit.edu","avatar":null},"body":"On Fri, May 13, 2011 at 2:48 PM, Junio C Hamano wrote:\n> Linus Torvalds writes:\n>\n>> When you say that v2.6.38 is good, that means that everything that can\n>> be reached from 2.6.38 is good.\n>>\n>> NOT AT ALL the same thing as \"git bisect requires v2.6.38\" would be.\n>>\n>> The \"requires v2.6.38\" would basically say that anything that doesn't\n>> contain v2.6.38 is \"off-limits\". It's fine to call them \"good\", but\n>> that's not the same thing as \"git bisect good v2.6.38\".\n>>\n>> Why?\n>>\n>> Think about it. It's the \"reachable from v2.6.38\" vs \"cannot reach\n>> v2.6.38\" difference. That's a HUGE difference.\n>\n> Could you please clarify \"off-limits\"?\n>\n> Do you mean \"anything before v2.6.38 did not even have this feature, so\n> the result of testing a version in that range does not give us any\n> information\"?  The feature didn't even exist, so a bug can never trigger,\n> and seeing \"good\" from such a version does not mean everything reachable\n> from it is good?  Upon seeing \"bad\" result from a version before v2.6.38,\n> what can we conclude?  The breakage cannot possibly come from the feature\n> that is being checked, so the procedure to check itself is busted?\n>\n\nIn my case, if I'd given bisect a hint that commits that don't include\nv2.6.38 are unlikely to work for reasons unrelated to the bug, then\nthere should still have been enough revisions left for bisect to tell\nme \"the bug was introduced by the merge of the drm tree but I can't\ntell you more without testing off-limits revisions\". That would have\navoided testing three or four revisions that just failed to boot.\n\nIn my particular case I think it would also have avoided an\nunnecessary set of tests to figure out why the networking merge broke\nmy system when the networking merge did not, in fact, break my system.\n This is coincidence -- all of the commits that didn't have the change\nthat fixed the bug the first time around also didn't contain v2.6.38,\nso I never would have tested them.\n\nThis is maybe some further justification for a bisect mode that\nfollows the --first-parent path as long as possible -- it might take\none or two more kernel builds, but it avoids odd trips around the\nhistory that can hit random crap like that. (Of course, it could lead\nto different random crap, but what can you do?)\n\n--Andy\n\n--Andy\n\n>\n>\n"},{"id":"167826","messageId":"BANLkTinGOHX-fNuQqZr50nvUC4BTymwBNg@mail.gmail.com","threadId":"27340","inReplyTo":"7vliya77xl.fsf@alter.siamese.dyndns.org","subject":"Re: AAARGH bisection is hard (Re: [2.6.39 regression] X locks up hard right after logging in)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2011-05-13T19:18:03Z","receivedAt":"2011-05-13T19:18:03Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"On Fri, May 13, 2011 at 11:48 AM, Junio C Hamano wrote:\n>\n> Could you please clarify \"off-limits\"?\n>\n> Do you mean \"anything before v2.6.38 did not even have this feature, so\n> the result of testing a version in that range does not give us any\n> information\"?\n\nWell, I think it's useful in two cases.\n\nIt's useful for the \"before this version, the test we're doing doesn't\neven make sense and cannot succeed\" sense.\n\nThat doesn't have to be about hardware support, it could be any\nfeature. For example, in git, say that you noticed that\n--dirstat-by-file stopped working at some point. You know it was good\nwhen you merged it, so you'd do\n\n git bisect start\n git bisect good ac9666f84a59\n\nbut you'd also go \"that's also when I introduced the *test* for it, so\nI'll need to require that\":\n\n git bisect requires ac9666f84a59\n\nand then you can start it all off:\n\n git bisect bad\n git bisect run sh -c \"make test\"\n\nor whatever.\n\nBecause you don't want to go into the merges that were based on code\nthat didn't even _have_ that feature.\n\nOk, so that's a made-up and contrieved example (it would make more\nsense for when you add a whole new flag, and your test-script is\ntestign that new functionality), but it kind of explains the notion:\nit will not bother to run bisect on code that simply isn't _relevant_\nfor the issue you are bisecting.\n\n> Upon seeing \"bad\" result from a version before v2.6.38, what can we conclude?\n\nThe point would be that such versions aren't even _testable_. So the\nwhole \"seeing 'bad'\" concept is a NULL concept. It's like the above\n\"new command line flag to 'git'\" example: it's not that those commits\nmight not have broken something, but those commits are crazy to test.\n\nIf it turns out that a merge brought in the breakage, we'd have to do\na totally new kind of test thing. But from a bisect standpoint, it's\nalready very interesting if the end result is \"hey, you merged that\ncode that didn't even _support_ the feature we're testing, and that\nbroke it\". That gives quite a bit of information, and opens up new\navenues for testing.\n\nFor example, at that point, we might decide that \"Oh, ok, now I will\nneed to re-run the bisect for everthing that came in in that merge,\nbut I will do a new merge at that point to see which commit it is that\ndoesn't play nice with the new feature\".\n\n> The breakage cannot possibly come from the feature\n> that is being checked, so the procedure to check itself is busted?\n\nRight.\n\nHOWEVER.\n\nThere's another reason to say \"require version XYZ\", and that's\nessentially a \"I want to do a (quicker) high-level bisect\". Especially\nthe way the kernel merge window is done, it might be that versions\nprior to v2.6.38 work perfectly _fine_, but what you want to do is to\nquickly bisect down to which subsystem caused breakage.\n\nA good way to do that would be to just say \"requires v2.6.38\", and\nsuddenly the actual set of commits that we're going to bisect is going\nto be *much* smaller. We're basically throwing away all the individual\ncommits that were merged in the merge window, and saying something\nthat approximates to \"we are only interested in the merge points\".\n\nWhy would we do that? Just to get a quicker \"this is the problematic\nsubsystem\". So the \"requires xyz\" might be quite useful for that\nreason too.\n\n Linus\n"}]}