From: Brown, Len <hidden> Date: 2006-01-09 08:06:36
Linus,
I think Tony has articulated the work-flow problem that
originally started this thread, as well as the fix.
I'll try to update the using-topic-branches document to capture this.
Some of the problem is that it doesn't quite capture what I'm doing
with my test/release branches.
My release branch really is just used as a transfer point to Linus.
I usually[1] don't leave patches sitting in "release" for long enough
that I'll be tempted to merge in from Linus ... once I decide that
some patches are ready to go to Linus I'll update "release" from Linus
(which will be a fast-forward, so no history) merge in the topic
branches, do one final sanity build, push to kernel.org and send
the "please pull" e-mail.
The huge majority of my "automatic update from upstream" merges
go into my test branch ... which never becomes part of the real
history as I never ask Linus to pull from it.
-Tony
[1] Sometimes I goof on this because I forget that I've applied
a trivial patch directly to the release branch without going through
a topic branch. I think I'll fix my update script to check
for this case.
I figured that checking some trivial patches directly into "release"
would be a convenient way to make sure I didn't forget to push them --
as they didn't depend on anything else in my tree. Okay.
To make sure that my test branch (where I generate my consolidated
plain patch, and what Andrew pulls) includes everything, I then pull
"release" into "test". Still good.
But then I decide I need to update my test tree from upstream.
I did this by pulling "linus" into "release", and then pulling
"release" into "test". This creates the book-keeping merge
in "release" that irritates gitk users.
This "flow", BTW, is a habit I picked up from the
"two-phase release strategy" that we used in bk days.
There I'd pull from upstream down into my to-linus tree and then pull
from the to-linus tree into the to-andrew tree.
I expect BK also created a merge cset, but apparently
nobody was looking at the history like they do with gitk today.
So if I simply don't pull from "linus" into a modified
"release" branch then the cluttered history issue goes away.
I should fetch "linus" into "release" right before I merge
the topic branches into "release" and push upstream.
The fetch is a clean fast-forward, and the merges all have
real content.
This will work as long as "release" doesn't get too old
to be pulled upstream without conflicts. Based on past
experience with low latency pulls upstream, I think this will be rare.
Andrew will still get cluttered history in the test tree,
but as he's focused on the content and not the (throw-away) history,
this is surely a non-issue.
So problem #1 is solved, yes?
Going forward...
I'm hopeful that gitk users will not be irritated also
by the liberal use of topic branches. I'm starting to like using
them quite a bit. Yes, it is true that I could cherry-pick
the topics out of their original context to re-manufacture linear
history. But that is extra work. Also, as you poined out,
there is real value in the real history because the context is accurate.
Further, I find that sometimes I need to augment a topic branch
with a follow-up patch. I can checkout the topic branch an plop
the follow-up right on the tip where it logically should live,
and (Tony's) scripts will remind me when the branch is not fully
pulled into test or release -- so it will never get misplaced.
In the case where a topic branch is a single commit, gitk users
will see both the original commit, as well as the merge commit
back into "release".
-Len
The huge majority of my "automatic update from upstream" merges
go into my test branch ... which never becomes part of the real
history as I never ask Linus to pull from it.
-Tony
[1] Sometimes I goof on this because I forget that I've applied
a trivial patch directly to the release branch without going through
a topic branch. I think I'll fix my update script to check
for this case.
I figured that checking some trivial patches directly into "release"
would be a convenient way to make sure I didn't forget to push them --
as they didn't depend on anything else in my tree. Okay.
One thing we could do is to make it easier to apply a patch to a
_non_current_ branch.
In other words, let's say that we want to encourage the separation of a
"development branch" and a "testing and use" branch (which I'd definitely
personally like to encourage people to do).
And one way to do that might be to teach "git-apply" to apply patches to a
non-active branch, and then you keep the "testing and use" branch as your
_checked_out_ branch (and it's going to be really dirty), but when you
actually apply patches you could do that to the "development" branch with
something like
git-apply -b development < patch-file
(Now, of course, that's only if you apply somebody elses patch - if you
actually do development _yourself_, you'd either have to check out the
development branch and do it there, or you'd move the patch you have in
your "ugly" checked-out testing branch into the development branch with
git diff | git-apply -b development
or something similar..)
Then you could always do "git pull . development" to pull in the
development stuff into your working branch - keeping the development
branch clean all the time.
Do you think that kind of workflow would be more palatable to you? It
shouldn't be /that/ hard to make git-apply branch-aware... (It was part of
my original plan, but it is more work than just using the working
directory, so I never finished the thought).
I'm hopeful that gitk users will not be irritated also
by the liberal use of topic branches.
"gitk" is actually pretty good at showing multiple branches. Try doing a
gitk --all -d
and you'll see all the topic branches in date order. The "-d" isn't
strictly necessary, and to some degree makes the output messier by
interleaving the commits from different branches, so you may not want to
do it, but it is sometimes nice to see the "relative dates" of individual
commits rather than the denser format that gitk defaults to.
In the case where a topic branch is a single commit, gitk users
will see both the original commit, as well as the merge commit
back into "release".
Yes, topic branches will always imply more commits, but I think they are
of the "nice" kind.
I definitely encourage people to use git as a distributed concurrent
development system ratehr than the "collection of patches" thing. Quilt is
much better at the collection of patches.
So I'd encourage topic branches - even within something like ACPI, you
might have separate topics ("interpreter" branch vs "x86" branch vs
"generic-acpi" branch).
And yes, that will make history sometimes messier too, and it will cause
more merges, but the difference there is that the merges will be
meaningful (ie merging the "acpi interpreter" branch into the generic ACPI
branch suddenly has _meaning_, even if there only ends up being a couple
of commits per merge).
Ok?
Linus
One thing we could do is to make it easier to apply a patch to a
_non_current_ branch.
[ ... ]
Do you think that kind of workflow would be more palatable to you? It
shouldn't be /that/ hard to make git-apply branch-aware... (It was part of
my original plan, but it is more work than just using the working
directory, so I never finished the thought).
Btw, this is true in a bigger sense: the things "git" does have largely
been driven by user needs. Initially mainly mine, but things like
"git-rebase" were from people who wanted to work as "sub-maintainers" (eg
Junio before he became the head honcho for git itself).
But if there are workflow problems, let's try to fix them. The "apply
patches directly to another branch" suggestion may not be sane (maybe it's
too confusing to apply a patch and not actually see it in the working
tree), but workflow suggestions in general are appreciated.
We've made switching branches about as efficient as it can be (but if the
differences are huge, the cost of re-writing the working directory is
never going to be low). But switching branches has the "confusion factor"
(ie you forget which branch you're on, and apply a patch to your working
branch instead of your development branch), so maybe there are other ways
of doing the same thing that might be sensible..
So send suggestions to the git lists. Maybe they're insane and can't be
done, but while I designed git to work with _my_ case (ie mostly merging
tons of different trees and then having occasional big batches of
patches), it's certainly _supposed_ to support other maintainers too..
Linus
But if there are workflow problems, let's try to fix them. The "apply
patches directly to another branch" suggestion may not be sane (maybe it's
too confusing to apply a patch and not actually see it in the working
tree), but workflow suggestions in general are appreciated.
This is sensible, thank you.
A very general workflow I've seen people use is more/less as
I outlined in my previous email:
tree A (linus' or trunk)
Project B (Tree B)
Project C (Tree C, depending on stuff in Project B)
Now this could be how the "managers" see things, but development,
could've "cloned" from Tree B and Tree C further, as is often
customary to have a a) per user tree, or b) per bug tree.
So pull/merge/fetch/whatever follows Tree A->B->C.
It is sensible to have another tree say, called something
like "for_linus" or "upstream" or "product" which includes
what has accumulated in C from B and in B from A, (eq diff(C-A)).
I.e. a "push" tree. So that I can tell you, "hey,
pull/fetch/merge/whatever the current verb en vogue is, from
here to get latest xyz".
What I also wanted to mention is that Tree B undeniably
depends on the _latest_ state of Tree A, since Project B
uses API/behaviour of the code in Tree A, so one cannot just
say they are independent. Similarly for Tree C/Project C,
is dependent on B, and dependent on A.
Also sometimes a bugfix in C, prompts a bugfix in A,
so that the bugfix in A doesn't apply unless the bugfix in C.
(To get things more complicated.)
I think this is more/less the most easier to see, understand and
follow workflow approach, which is also the case for other SCMs.
What are the commands to follow to make everyone happy when
pulling from such a development process?
FWIW, "git diff A C | send to Linus" would get you the
"no merge messages/ancestors I want to see" idea, if I understand
this thread correctly.
We've made switching branches about as efficient as it can be (but if the
differences are huge, the cost of re-writing the working directory is
never going to be low). But switching branches has the "confusion factor"
(ie you forget which branch you're on, and apply a patch to your working
branch instead of your development branch), so maybe there are other ways
of doing the same thing that might be sensible..
Yes. Ever since I started used git, I never used branch
switching, but I do have git branches and I do use git branching.
I basically have a branch per directory, whereby the object db
is shared as is remotes/refs/etc, HEAD and index are not shared
of course.
This allows me to do a simple and fast "cd" to change/go to a
different branch, since they are in different directories.
So the time I wait to switch branches is the time the filesystem
takes to do a "cd".
This also allows me to build/test/patch/work on branches
simultaneously.
Thank you,
Luben
Yes. Ever since I started used git, I never used branch
switching, but I do have git branches and I do use git branching.
I basically have a branch per directory, whereby the object db
is shared as is remotes/refs/etc, HEAD and index are not shared
of course.
This allows me to do a simple and fast "cd" to change/go to a
different branch, since they are in different directories.
So the time I wait to switch branches is the time the filesystem
takes to do a "cd".
This also allows me to build/test/patch/work on branches
simultaneously.
Yes. It has many advantages, and it's the approach I pushed pretty hard
originally, but the "many branches in the same tree" approach seems to
have become the more common one. Using many branches in the same tree is
definitely the better approach for _distribution_, but that doesn't
necessarily mean that it's the better one for development.
For example, you can have a git distribution tree with 20 different
branches on kernel.org, but do development in 20 different trees with just
one branch active - and when you do a "git push" to push out your branch
in your development tree, it just updates that one branch on the
distribution site.
So git certainly supports that kind of behaviour, but nobody I know
actually does it that way (not even me, but since I tend to just merge
other peoples code, I don't actually have multiple branches: I create
temporary branches for one-off things, but don't maintain them that way).
Linus
From: Martin Langhoff <hidden> Date: 2006-01-09 23:34:41
On 1/10/06, Linus Torvalds [off-list ref] wrote:
Using many branches in the same tree is
definitely the better approach for _distribution_, but that doesn't
necessarily mean that it's the better one for development.
(...)
So git certainly supports that kind of behaviour, but nobody I know
actually does it that way
Hrm! We do. http://locke.catalyst.net.nz/gitweb?p=moodle.git;a=heads
shows a lot of heads that share 99% of the code. The repo is ~90MB --
and we check each head out with cogito, develop and push. It is a
shared team repo, using git+ssh and sticky gid and umask 002.
Works pretty well I have to add. The only odd thing is that the
fastest way to actually start working on a new branch is to ssh on to
the server and cp moodle.git/refs/heads/{foo,bar} and then cg-clone
that bar branch away. Perhaps I should code up an 'cg-branch-add
--in-server' patch.
regards,
martin
A very general workflow I've seen people use is more/less as
I outlined in my previous email:
tree A (linus' or trunk)
Project B (Tree B)
Project C (Tree C, depending on stuff in Project B)
Now this could be how the "managers" see things, but development,
could've "cloned" from Tree B and Tree C further, as is often
customary to have a a) per user tree, or b) per bug tree.
So pull/merge/fetch/whatever follows Tree A->B->C.
It is sensible to have another tree say, called something
like "for_linus" or "upstream" or "product" which includes
what has accumulated in C from B and in B from A, (eq diff(C-A)).
I.e. a "push" tree. So that I can tell you, "hey,
pull/fetch/merge/whatever the current verb en vogue is, from
here to get latest xyz".
What I also wanted to mention is that Tree B undeniably
depends on the _latest_ state of Tree A, since Project B
uses API/behaviour of the code in Tree A, so one cannot just
say they are independent. Similarly for Tree C/Project C,
is dependent on B, and dependent on A.
Note that in the case where the _latest_ state of the tre you are tracking
really matters, then doing a "git pull" is absolutely and unquestionably
the right thing to do.
So if people thought that I don't want to have sub-maintainers pulling
from my tree _at_all_, then that was a mis-communication. I don't in any
way require a linear history, and criss-cross merges are supported
perfectly well by git, and even encouraged in those situations.
After all, if tree B starts using features that are new to tree A, then
the merge from A->B is required for functionality, and the synchronization
is a fundamental part of the history of development. In that cases, the
history complexity of the resulting tree is a result of real development
complexity.
Now, obviously, for various reasons we want to avoid having those kinds of
linkages as much as possible. We like to have develpment of different
subsystems as independent as possible, not because it makes for a "more
readable history", but because it makes it a lot easier to debug - if we
have three independent features/development trees, they can be debugged
independently too, while any linkages inevitably also mean that any bugs
end up being interlinked..
Linus
if we have three independent features/development trees, they can
be debugged independently too, while any linkages inevitably also
mean that any bugs end up being interlinked..
One example:
If I have ACPI, netdev, and swsusp trees change between an older
version and a newer one, and my net driver starts breaking during
suspend, I would be happiest debugging with the following set of
patches/trees (Heavily simplified):
^
|
[5]
|
broken
^ ^ ^
[2] [3] [4]
/ | \
netdev3 acpi3 swsusp3
^ ^ ^
| | |
netdev2 acpi2 swsusp2
^ ^ ^
| | |
netdev1 acpi1 swsusp1
^ ^ ^
\ | /
\ | /
\ | /
\|/
|
[1]
|
works
If the old version [1] works and the new one [5] doesn't, then I can
immediately test [2], [3], and [4]. If one of those doesn't work,
I've identified the problematic patchset and cut the debugging by
2/3. If they all work, then we know precisely that it's the
interactions between them, which also makes debugging a lot easier.
Cheers,
Kyle Moffett
--
There are two ways of constructing a software design. One way is to
make it so simple that there are obviously no deficiencies. And the
other way is to make it so complicated that there are no obvious
deficiencies. The first method is far more difficult.
-- C.A.R. Hoare
-
To unsubscribe from this list: send the line "unsubscribe linux-acpi" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
From: Martin Langhoff <hidden> Date: 2006-01-10 06:38:12
On 1/10/06, Kyle Moffett [off-list ref] wrote:
If they all work, then we know precisely that it's the
interactions between them, which also makes debugging a lot easier.
The more complex your tree structure is, the more the interactions are
likely to be part of the problem. Is git-bisect not useful in this
scenario?
cheers,
martin
-
To unsubscribe from this list: send the line "unsubscribe linux-acpi" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
If they all work, then we know precisely that it's the
interactions between them, which also makes debugging a lot easier.
The more complex your tree structure is, the more the interactions
are likely to be part of the problem. Is git-bisect not useful in
this scenario?
IIRC git-bisect just does an outright linearization of the whole tree
anyways, which makes git-bisect work everywhere, even in the presence
of difficult cross-merges. On the other hand, if you are git-
bisecting ACPI changes (perhaps due to some ACPI breakage), and ACPI
has 10 pulls from mainline, you _also_ have to wade through the
bisection of any other changes that occurred in mainline, even if
they're totally irrelevant. This is why it's useful to only pull
mainline into your tree (EX: ACPI) when you functionally depend on
changes there (as Linus so eloquently expounded upon).
Cheers,
Kyle Moffett
--
Q: Why do programmers confuse Halloween and Christmas?
A: Because OCT 31 == DEC 25.
The more complex your tree structure is, the more the interactions are
likely to be part of the problem. Is git-bisect not useful in this scenario?
IIRC git-bisect just does an outright linearization of the whole tree anyways,
which makes git-bisect work everywhere, even in the presence of difficult
cross-merges.
It's not really a linearization - at no time does git-bisect _order_ the
commits. After all, no linear order actually exists.
Instead, it really cuts the tree up into successively smaller parts.
Think of it as doing a binary search in a 2-dimensional surface - you
can't linearize the plane, but you can decide to test first one half of
the surface, and then depending on whether it was there, you can halve
that surface etc..
On the other hand, if you are git-bisecting ACPI changes
(perhaps due to some ACPI breakage), and ACPI has 10 pulls from mainline, you
_also_ have to wade through the bisection of any other changes that occurred
in mainline, even if they're totally irrelevant.
Yes. Although if you _know_ that the problem happened in a specific file
or specific subdirectory, you can actually tell "git bisect" to only
bother with changes to that file/directory/set-of-directories to speed up
the search.
IOW, if you absolutely know that it's ACPI-related, you can do something
like
git bisect start drivers/acpi arch/i386/kernel/acpi
to tell the bisect code that it should totally ignore anything that
doesn't touch those two directories.
However, if it turns out that you were wrong (and the ACPI breakage was
brought on by something that changed something else), "git bisect" will
just get confused and report the wrong commit, so this is really something
you should be careful with (and verify the end result by checking that
undoing that _particular_ commit really fixes things).
And yes, "git bisect" _will_ work with bugs that depend on two branches of
a merge: it will point to the merge commit itself as being the problem.
Now, at that point you really are screwed, and you'll have to figure out
why both branches work, but the combination of them do not.
Maybe it's as simple as just a merge done wrong (bad manual fixups), but
maybe it's a perfectly executed merge that just happens to have one branch
changing the assumptions that the other branch depended on.
Happily, that is not very common. I know people are using "git bisect",
and I don't think anybody has ever reported it so far. It will happen
eventually, but I'd actually expect it to be much more common that "git
bisect" will hit other - worse - problems, like bugs that "come and go",
and that a simple bisection simply cannot find because they aren't
totally repeatable.
Linus
From: Johannes Schindelin <hidden> Date: 2006-01-10 18:45:22
Hi,
On Tue, 10 Jan 2006, Linus Torvalds wrote:
On Tue, 10 Jan 2006, Kyle Moffett wrote:
quoted
On Jan 10, 2006, at 01:38, Martin Langhoff wrote:
quoted
The more complex your tree structure is, the more the interactions are
likely to be part of the problem. Is git-bisect not useful in this scenario?
IIRC git-bisect just does an outright linearization of the whole tree anyways,
which makes git-bisect work everywhere, even in the presence of difficult
cross-merges.
It's not really a linearization - at no time does git-bisect _order_ the
commits. After all, no linear order actually exists.
Instead, it really cuts the tree up into successively smaller parts.
Think of it as doing a binary search in a 2-dimensional surface - you
can't linearize the plane, but you can decide to test first one half of
the surface, and then depending on whether it was there, you can halve
that surface etc..
How?
If you bisect, you test a commit. If the commit is bad, you assume *all*
commits before that as bad. If it is good, you assume *all* commits after
that as good.
Now, if you have a 2-dimensional surface, you don't have a *point*, but
typically a *line* separating good from bad.
Further, the comparison with 2 dimensions is particularly bad. You
*have* partially linear development lines, it got *nothing* to do with
an area. The commits still make up a *list*, and it depends how you
*order* that list for bisect. (And don't tell me they are not ordered:
they are.)
If you order the commits by date, you don't get anything meaningful point
before which it is bad, and after which it is good.
So, how is bisect supposed to work if you don't have one straight
development line from bad to good?
Ciao,
Dscho
-
To unsubscribe from this list: send the line "unsubscribe linux-acpi" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Think of it as doing a binary search in a 2-dimensional surface - you
can't linearize the plane, but you can decide to test first one half of
the surface, and then depending on whether it was there, you can halve
that surface etc..
How?
If you bisect, you test a commit. If the commit is bad, you assume *all*
commits before that as bad. If it is good, you assume *all* commits after
that as good.
No, that's not how bisect works at all.
It's true that if a commit is bad, then all the commits _reachable_ from
that commit are considered bad.
And it's true that if a commit is good, then all commits that _reach_ that
commit are considered good.
But that doesn't mean that there is an ordering. The commits that fall
into the camp of being "neither good nor bad" are _not_ ordered. There are
commits in there that are not directly reachable from the good commit.
Now, if you have a 2-dimensional surface, you don't have a *point*, but
typically a *line* separating good from bad.
Exactly.
And a git graph is not really a two-dimensional surface, but exactly was
with a 2-dimensional surface, it is _not_ enough to have a *point* to
separate the good from bad.
You need to have a _set of points_ to separate the good from the bad. You
can think of it as a line that bisects the surface: if you were to print
out the development graph, the set of points literally _do_ form a virtual
line across the development surface.
(Actually, you can't in general print out the development graph on a
2-dimensional paper without having development lines that cross each
other, but you could actually do it in three dimensions, where the
"boundary" between good and bad is actually a 2-dimensional surface in
3-dimensional space).
But to describe the surface of "known good", you actually just need a list
of known good commits, and the "commits reachable from those commits"
_becomes_ the surface.
Further, the comparison with 2 dimensions is particularly bad.
No it is not. It's a very good comparison.
In a linearized model (one-dimensional, fully ordered set), the only thing
you need for bisection is two points: the beginning and the end.
In the git model, you need _many_ points to describe the area being
bisected. Exactly the same way as if you were to bisect a 2-dimensional
surface.
Now, the git history is _not_ really a two-dimensional surface, so it's
just an analogy, not an exact identity. But from a visualization
standpoint, it's a good way to think of each "git bisect" as adding a
_line_ on the surface rather than a point on a linear line.
So, how is bisect supposed to work if you don't have one straight
development line from bad to good?
Read the code.
I'm pretty proud of it. It's simple, and it's obvious once you think about
it, but it is pretty novel as far as I know. BK certainly had nothing
similar, not have I heard of anythign else that does it. Git _might_ be
the first thing that has ever done it, although it's simple enough that I
wouldn't be surprised if others have too.
Linus
Now, the git history is _not_ really a two-dimensional surface, so it's
just an analogy, not an exact identity. But from a visualization
standpoint, it's a good way to think of each "git bisect" as adding a
_line_ on the surface rather than a point on a linear line.
Actually, the way I think of it is akin to the "light cones" in physics. A
point in space-time doesn't define a fully ordered "before and after": but
it _does_ describe a "light cone" which tells you what is reachable from
that point, and what that point reaches. Within those cones, that
particular point ("commit") has a strict ordering.
And exactly as in physics, in git there's a lot of space that is _not_
ordered by that commit. And the way to bisect is basically to find the
right points in "git space" to create the right "light cone" that you
find the point where the git space that is reachable from that commit has
the same volume as the git space that isn't reachable.
And maybe that makes more sense to you (if you're into physics), or maybe
it makes less sense to you.
Now, since we always search the "git space" in the cone that is defined by
"reachable from the bad commit, but not reachable from any good commit",
the way we handle "bad" and "good" is actually not a mirror-image. If we
fine a new _bad_ commit, we know that it was reachable from the old bad
commit, and thus the old bad commit is now uninteresting: the new bad
commit forms a "past light cone" that is a strict subset of the old one,
so we can totally discard the old bad commit from any future
consideration. It doesn't tell us anything new.
In contrast, if we find a new _good_ commit, the "past light cone" (aka
"set of commits reachable from it") is -not- necessarily a proper superset
of the previous set of good commits, so when we find a good commit, we
still need to carry the _other_ good commits around, and the "known good"
universe is the _union_ of all the "good commit past lightcones".
Then the "unknown space" is the set difference of the "past lightcone of
the bad commit" and of this "union of past lightcones of good commits".
It's the space that is reachable from the known-bad commit, but not
reachable from any known-good commit.
So this means that when doing bisection, what we want to do is find the
point in git space that has _new_ "reachability" within that unknown space
that is as close to half that volume as space as possible. And that's
exactly what "git-rev-list --bisect" calculates.
So every time, we try to either move the "known bad" light-cone down in
time in the unknown space, _or_ we add a new "known good" light-cone. In
either case, the "unknown git space" keeps shrinking by half each time.
("by half" is not exact, because git space is not only quanticized, it
also has a rather strange "distance function". In other words, we're
talking about a rather strange space. The good news is that the space is
small enough that we can just enumerate every quantum and simply
calculate the volume it defines in that space. IOW, we do a very
brute-force thing, and it works fine).
Linus
they're totally irrelevant. This is why it's useful to only pull
mainline into your tree (EX: ACPI) when you functionally depend on
changes there (as Linus so eloquently expounded upon).
Sometimes the dependency is _behavioural_. For example certain
behaviour of other modules of the kernel changed and you want
to test that your module works ok with them under different
behaviour. In which case you may or may not have to
change your code after the fact.
Luben
-
To unsubscribe from this list: send the line "unsubscribe linux-acpi" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
I'm pretty proud of it. It's simple, and it's obvious once you think about
it, but it is pretty novel as far as I know. BK certainly had nothing
similar, not have I heard of anythign else that does it.
Actually, I've written a hackish script that tries to do simple-minded
bisection (read: it searched for the 50% point on the shortest path
between any-of-GOOD and any-of-BAD, instead of considering the whole
graph) on BK trees. I haven't exactly published the thing anyplace though,
because, well, it was ugly. :-/
Besides, actually working with the current bisection point is no problem
at all for git. Doing the same thing in BK's world view is *painful*,
esp. given the size of the kernel tree.
--
Matthias Urlichs | {M:U} IT Design @ m-u-it.de | smurf@smurf.noris.de
Disclaimer: The quote was selected randomly. Really. | http://smurf.noris.de
- -
Arthur felt at a bit of a loss. There was a whole Galaxy
of stuff out there for him, and he wondered if it was
churlish of him to complain to himself that it lacked just
two things: the world he was born on and the woman he loved.
From: Johannes Schindelin <hidden> Date: 2016-06-15 22:42:16
Hi,
[cut down the Cc: list, since this is getting special]
On Tue, 10 Jan 2006, Linus Torvalds wrote:
quoted
If you bisect, you test a commit. If the commit is bad, you assume *all*
commits before that as bad. If it is good, you assume *all* commits after
that as good.
No, that's not how bisect works at all.
Okay, so I got that wrong. But for a good reason: this is not the meaning
of bisection in my lectures. Doesn't matter.
It's true that if a commit is bad, then all the commits _reachable_ from
that commit are considered bad.
And it's true that if a commit is good, then all commits that _reach_ that
commit are considered good.
But that doesn't mean that there is an ordering. The commits that fall
into the camp of being "neither good nor bad" are _not_ ordered. There are
commits in there that are not directly reachable from the good commit.
Those commits not reachable from the good commit are of no interest. Let's
just ignore them.
quoted
Now, if you have a 2-dimensional surface, you don't have a *point*, but
typically a *line* separating good from bad.
Exactly.
And a git graph is not really a two-dimensional surface, but exactly was
with a 2-dimensional surface, it is _not_ enough to have a *point* to
separate the good from bad.
You need to have a _set of points_ to separate the good from the bad. You
can think of it as a line that bisects the surface: if you were to print
out the development graph, the set of points literally _do_ form a virtual
line across the development surface.
Okay, so there is a cut: Every directed path from good to bad has a single
commit which is the first bad. Let's call the set of all such bad commits
the cut set.
Is git-bisect capable of identifying all of the cut set, or just a single
one?
quoted
Further, the comparison with 2 dimensions is particularly bad.
No it is not. It's a very good comparison.
From your explanation I understand now why you like that comparison.
quoted
So, how is bisect supposed to work if you don't have one straight
development line from bad to good?
Read the code.
I'm pretty proud of it.
I bet nobody can tell ;-)
Well, I read the code. And I answer my own question from 18--19 lines ago:
git-bisect is not capable of identifying the cut set, but pretends that
there really is only one bad commit (see bisect_bad()).
That may be the best choice if all commits in the cut set except one are
merges. (It is the best if the cut set contains only one element.)
But I see two problems with that:
- a problem can be introduced independently in two different branches, and
occur in both of them before the merge (in which case bisect only
catches one of the commits), and
- AFAICT if the cut set is one merge and one regular commit, bisect could
identify the merge by error.
Of course, all this makes only a difference if the bisect has to cross a
merge.
BTW I think there is a thinko in git-rev-list.txt:
Thus, if 'git-rev-list --bisect foo ^bar ^baz' outputs 'midpoint', the
output of 'git-rev-list foo ^midpoint' and 'git-rev-list midpoint ^bar
^ this should be
'git-rev-list foo ^midpoint ^bar ^baz'
Those commits not reachable from the good commit are of no interest. Let's
just ignore them.
Note that to avoid confusion, start talking about -multiple- good commits
early.
So we have a list of "known good islands" in the git-space. And yes, we
want to ignore anything that is reachable from them.
And here the magic part of"git-bisect.sh" is around line 133:
... --not $(cd "$GIT_DIR" && ls refs/bisect/good-*) ...
It tells git-rev-parse to generate a list of commits that we're _not_
interested in, and that list will be one of the most critical parts of the
stuff we give to "git-rev-list --bisect".
So that part of the script is literally the part that says "ignore all of
git space that is reachable from the good commits", because we've listed
all the good commits as refs named "refs/bisect/good-*".
quoted
You need to have a _set of points_ to separate the good from the bad. You
can think of it as a line that bisects the surface: if you were to print
out the development graph, the set of points literally _do_ form a virtual
line across the development surface.
Okay, so there is a cut: Every directed path from good to bad has a single
commit which is the first bad. Let's call the set of all such bad commits
the cut set.
This set is uninteresting for two reasons:
- it's hard to calculate
- it's not the answer we want.
We want the _single_ commit that is the one that generates your "cut set".
Your "cut set" is really the "reachability border" from the single bad
commit we're interested in to all the possible development lines.
In practice, the "cut set" is just the "bad commit" plus all the merges
that merge that bad commit with somethign that wasn't reacable from it in
the first place.
So the "cut set" isn't interesting.
git-bisect is not capable of identifying the cut set, but pretends that
there really is only one bad commit (see bisect_bad()).
Not quite.
It could keep track of all bad commits (in fact, it does so in the log
file), but the fact is, none but the lastest bad commit we have found
matters.
By definition, "git bisect" is always going to test a commit that is
reachable from the previously known bad commit. Agreed? Anything else
would be insane - we know that we had a bad stat, and we're interested in
finding out how _that_ bad state happened, so we're only ever interested
in commits that are ancestors to that bad state.
So our search-space is _literally_ defined by two things:
- the surface of "known good" commits (which defines the commits that
aren't interesting).
This is the "--not refs/bisect/good-*" part
- the last "known bad" commit.
We'll always search the git commit space defined by these two knowns,
agreed?
Now, realize that if we find a new bad commit, since that bad commit was
by definition reachable from the _old_ bad commit (since we didn't even
search outside its reachability), then equally by definition the
reachability from that new bad commit is a strict superset of the
reachability of the old bad commit.
So when we find a new bad commit, the old bad commit is no longer
interesting.
So when you say "pretends that there really is only one bad commit", you
didn't realize that it's not about "pretending". It's very fundamental:
there is only ever _one_ bad commit that is interesting. It's the last one
we found.
Even if we started out with two bad commits (ie some person reported two
different versions as being bad), we're _still_ not interested in using
them both. We should pick one of them, because the reachability area
defined by two bad commits is always a superset of the reachability of
either one.
So having multiple bad commits is _never_ interesting.
But I see two problems with that:
- a problem can be introduced independently in two different branches, and
occur in both of them before the merge (in which case bisect only
catches one of the commits), and
This is fine. Depending on whatever random factors, we'll test one of them
first, and eventually find _one_ of the commits that fix it. If the exact
same bug was introduced somewhere else, and merged, then undoing just the
"one" bug will obviously undo the other one too.
If a _different_ bug was introduced (even if it had the same effects),
yes, you now have two separate bugs. And bisecting two bugs is hard. You
need to separate them out some way.
- AFAICT if the cut set is one merge and one regular commit, bisect could
identify the merge by error.
It will never identify a commit without having done a full bisection, so
if it ever had the choice of a "merge" and the "commit leading up to the
merge", it will always have tried the "commit leading up to the merge",
and decided that it was fundamentally more recent (had "smaller
reachability") that the merge, and pinpoint it.
BTW I think there is a thinko in git-rev-list.txt:
quoted
Thus, if 'git-rev-list --bisect foo ^bar ^baz' outputs 'midpoint', the
output of 'git-rev-list foo ^midpoint' and 'git-rev-list midpoint ^bar
^ this should be
'git-rev-list foo ^midpoint ^bar ^baz'
If a _different_ bug was introduced (even if it had the same effects),
yes, you now have two separate bugs. And bisecting two bugs is hard. You
need to separate them out some way.
Side note: this is seldom a problem in practice. If it was effectively the
same bug, just finding the one case that triggered it is sufficient: you
then know what to look for, and if undoing that one commit isn't enough to
fix it in the current tree (because the same bug existed in another form
on another branch), you wouldn't actually start bisecting again. You'd
start grepping the tree for other cases of that bug.
So the biggest advantage of "git bisect" is _not_ that you can just undo
the buggy commit. In fact, usually you don't even want to undo it, because
it probably had a raison-d'etre to begin with. The huge deal about "git
bisect" is that it pinpoints what caused the bug, and then the fix is
often something else.
Often it's a "Duh! I fixed one thing, but my fix didn't take Xyz into
account, so it now broke for another reason" moment.
Most bugs are stupid, in other words.
The _real_ problem with git bisect is when you have a non-technical user
(common) and there are silly bugs that you know of and already fixed that
aren't really a problem, but that are show-stoppers for the user who isn't
a kernel developer (or is, but doesn't know git). They're show-stoppers
not because we care about them, but because they make the "purely
mechanical" thing be one where you have to have some manual input.
Another problem (that I've not seen in practice yet, but that I bet _will_
be the worst issue) is non-reproducible bugs. They are the nastiest kind
to debug in the first place, and sadly, "git bisect" simply doesn't help
you with them. There, nothing but some luck and a lot of thinking and
testing will help you.
Linus
From: Johannes Schindelin <hidden> Date: 2016-06-15 22:42:16
Hi,
On Tue, 10 Jan 2006, Linus Torvalds wrote:
So having multiple bad commits is _never_ interesting.
Okay, I got it. A bug is supposed to be inherited by *all* its
descendants. Good.
I have to keep in mind that a commit is not actually a patch set, but can
be two or more (in case of a merge). So, a bug can be present in a
development line for a long, long time, but be visible only after a merge.
Since that commit can be compared to at least two trees, one of these
diffs must show the bug.
Thanks,
Dscho