diff --git a/mercurial/branchmap.py b/mercurial/branchmap.py
--- a/mercurial/branchmap.py
+++ b/mercurial/branchmap.py
@@ -7,7 +7,7 @@
 
 from node import bin, hex, nullid, nullrev
 import encoding
-import util
+import util, repoview
 
 def _filename(repo):
     """name of a branchcache file for a given repo or repoview"""
@@ -63,16 +63,24 @@ def updatecache(repo):
     filtername = repo.filtername
     partial = repo._branchcaches.get(filtername)
 
+    revs = []
     if partial is None or not partial.validfor(repo):
         partial = read(repo)
         if partial is None:
-            partial = branchcache()
-
-    revs = list(cl.revs(start=partial.tiprev +1))
+            subsetname = repoview.subsettable.get(filtername)
+            if subsetname is None:
+                partial = branchcache()
+            else:
+                subset = repo.filtered(subsetname)
+                partial = subset.branchmap().copy()
+                extrarevs = subset.changelog.filteredrevs - cl.filteredrevs
+                revs.extend(r for  r in extrarevs if r <= partial.tiprev)
+    revs.extend(cl.revs(start=partial.tiprev + 1))
     if revs:
         ctxgen = (repo[r] for r in revs)
         partial.update(repo, ctxgen)
         partial.write(repo)
+    assert partial.validfor(repo)
     repo._branchcaches[repo.filtername] = partial
 
 class branchcache(dict):
diff --git a/tests/test-acl.t b/tests/test-acl.t
--- a/tests/test-acl.t
+++ b/tests/test-acl.t
@@ -140,6 +140,7 @@ Extension disabled for lack of acl.sourc
   query 1; heads
   searching for changes
   all remote heads known locally
+  invalid branchheads cache (unserved): tip differs
   listing keys for "bookmarks"
   3 changesets found
   list of changesets:
@@ -201,6 +202,7 @@ No [acl.allow]/[acl.deny]
   query 1; heads
   searching for changes
   all remote heads known locally
+  invalid branchheads cache (unserved): tip differs
   listing keys for "bookmarks"
   3 changesets found
   list of changesets:
@@ -272,6 +274,7 @@ Empty [acl.allow]
   query 1; heads
   searching for changes
   all remote heads known locally
+  invalid branchheads cache (unserved): tip differs
   listing keys for "bookmarks"
   3 changesets found
   list of changesets:
@@ -770,6 +773,7 @@ wilma can change files with a .txt exten
   query 1; heads
   searching for changes
   all remote heads known locally
+  invalid branchheads cache (unserved): tip differs
   listing keys for "bookmarks"
   3 changesets found
   list of changesets:
@@ -1087,6 +1091,7 @@ fred is always allowed
   query 1; heads
   searching for changes
   all remote heads known locally
+  invalid branchheads cache (unserved): tip differs
   listing keys for "bookmarks"
   3 changesets found
   list of changesets:
@@ -1162,6 +1167,7 @@ no one is allowed inside foo/Bar/
   query 1; heads
   searching for changes
   all remote heads known locally
+  invalid branchheads cache (unserved): tip differs
   listing keys for "bookmarks"
   3 changesets found
   list of changesets:
@@ -1313,6 +1319,7 @@ OS-level groups
   query 1; heads
   searching for changes
   all remote heads known locally
+  invalid branchheads cache (unserved): tip differs
   listing keys for "bookmarks"
   3 changesets found
   list of changesets:
@@ -1510,6 +1517,7 @@ Branch acl deny test
   query 1; heads
   searching for changes
   all remote heads known locally
+  invalid branchheads cache (unserved): tip differs
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
@@ -1821,6 +1829,7 @@ push foobar into the remote
   query 1; heads
   searching for changes
   all remote heads known locally
+  invalid branchheads cache (unserved): tip differs
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
@@ -1908,6 +1917,7 @@ Branch acl conflicting deny
   query 1; heads
   searching for changes
   all remote heads known locally
+  invalid branchheads cache (unserved): tip differs
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
@@ -2063,6 +2073,7 @@ Non-astro users must be denied
   query 1; heads
   searching for changes
   all remote heads known locally
+  invalid branchheads cache (unserved): tip differs
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
diff --git a/tests/test-fncache.t b/tests/test-fncache.t
--- a/tests/test-fncache.t
+++ b/tests/test-fncache.t
@@ -70,7 +70,7 @@ Non store repo:
   .hg/00changelog.i
   .hg/00manifest.i
   .hg/cache
-  .hg/cache/branchheads
+  .hg/cache/branchheads-unserved
   .hg/data
   .hg/data/tst.d.hg
   .hg/data/tst.d.hg/foo.i
@@ -98,7 +98,7 @@ Non fncache repo:
   .hg
   .hg/00changelog.i
   .hg/cache
-  .hg/cache/branchheads
+  .hg/cache/branchheads-unserved
   .hg/dirstate
   .hg/last-message.txt
   .hg/requires
diff --git a/tests/test-hardlinks.t b/tests/test-hardlinks.t
--- a/tests/test-hardlinks.t
+++ b/tests/test-hardlinks.t
@@ -196,7 +196,7 @@ r4 has hardlinks in the working dir (not
   $ nlinksdir r4
   2 r4/.hg/00changelog.i
   2 r4/.hg/branch
-  2 r4/.hg/cache/branchheads
+  2 r4/.hg/cache/branchheads-unserved
   2 r4/.hg/dirstate
   2 r4/.hg/hgrc
   2 r4/.hg/last-message.txt
@@ -226,7 +226,7 @@ Update back to revision 11 in r4 should 
   $ nlinksdir r4
   2 r4/.hg/00changelog.i
   1 r4/.hg/branch
-  2 r4/.hg/cache/branchheads
+  2 r4/.hg/cache/branchheads-unserved
   1 r4/.hg/dirstate
   2 r4/.hg/hgrc
   2 r4/.hg/last-message.txt
diff --git a/tests/test-inherit-mode.t b/tests/test-inherit-mode.t
--- a/tests/test-inherit-mode.t
+++ b/tests/test-inherit-mode.t
@@ -66,7 +66,7 @@ new directories are setgid
   00700 ./.hg/
   00600 ./.hg/00changelog.i
   00770 ./.hg/cache/
-  00660 ./.hg/cache/branchheads
+  00660 ./.hg/cache/branchheads-unserved
   00660 ./.hg/dirstate
   00660 ./.hg/last-message.txt
   00600 ./.hg/requires
@@ -111,7 +111,7 @@ group can still write everything
   00770 ../push/.hg/
   00660 ../push/.hg/00changelog.i
   00770 ../push/.hg/cache/
-  00660 ../push/.hg/cache/branchheads
+  00660 ../push/.hg/cache/branchheads-unserved
   00660 ../push/.hg/requires
   00770 ../push/.hg/store/
   00660 ../push/.hg/store/00changelog.i
diff --git a/tests/test-keyword.t b/tests/test-keyword.t
--- a/tests/test-keyword.t
+++ b/tests/test-keyword.t
@@ -747,7 +747,9 @@ Interrupted commit should not change sta
 Commit with multi-line message and custom expansion
 
   $ hg --debug commit -l log -d '2 0' -u 'User Name <user@example.com>'
+  invalid branchheads cache: tip differs
   a
+  invalid branchheads cache: tip differs
   overwriting a expanding keywords
   committed changeset 2:bb948857c743469b22bbf51f7ec8112279ca5d83
   $ rm log
@@ -789,6 +791,8 @@ remove with status checks
   $ hg debugrebuildstate
   $ hg remove a
   $ hg --debug commit -m rma
+  invalid branchheads cache: tip differs
+  invalid branchheads cache: tip differs
   committed changeset 3:d14c712653769de926994cf7fbb06c8fbd68f012
   $ hg status
   ? c
@@ -899,8 +903,10 @@ kwexpand x/a should abort
   [255]
   $ cd x
   $ hg --debug commit -m xa -d '3 0' -u 'User Name <user@example.com>'
+  invalid branchheads cache: tip differs
   x/a
    x/a: copy a:779c764182ce5d43e2b1eb66ce06d7b47bfe342e
+  invalid branchheads cache: tip differs
   overwriting x/a expanding keywords
   committed changeset 3:b4560182a3f9a358179fd2d835c15e9da379c1e4
   $ cat a
diff --git a/tests/test-newbranch.t b/tests/test-newbranch.t
--- a/tests/test-newbranch.t
+++ b/tests/test-newbranch.t
@@ -1,5 +1,15 @@
   $ branchcache=.hg/cache/branchheads
 
+  $ listbranchcaches() {
+  >    for f in .hg/cache/branchheads*;
+  >       do echo === $f ===;
+  >       cat $f;
+  >     done;
+  > }
+  $ purgebranchcaches() {
+  >     rm .hg/cache/branchheads*
+  > }
+
   $ hg init t
   $ cd t
 
@@ -112,7 +122,7 @@ Test for invalid branch cache:
   repository tip rolled back to revision 4 (undo commit)
   working directory now based on revisions 4 and 3
 
-  $ cp $branchcache .hg/bc-invalid
+  $ cp ${branchcache}-unserved .hg/bc-invalid
 
   $ hg log -r foo
   changeset:   4:adf1a74a7f7b
@@ -142,13 +152,16 @@ Test for invalid branch cache:
   modify a branch
   
   
-  $ rm $branchcache
+  $ purgebranchcaches
   $ echo corrupted > $branchcache
 
   $ hg log -qr foo
   4:adf1a74a7f7b
 
-  $ cat $branchcache
+  $ listbranchcaches
+  === .hg/cache/branchheads ===
+  corrupted
+  === .hg/cache/branchheads-unserved ===
   adf1a74a7f7b4cd193d12992f5d0d6a004ed21d6 4
   1c28f494dae69a2f8fc815059d257eccf3fcfe75 default
   adf1a74a7f7b4cd193d12992f5d0d6a004ed21d6 foo
@@ -162,7 +175,8 @@ Pushing just rev 0:
 
   $ hg push -qr 0 ../target
 
-  $ cat ../target/$branchcache
+  $ (cd ../target/; listbranchcaches)
+  === .hg/cache/branchheads-unserved ===
   db01e8ea3388fd3c7c94e1436ea2bd6a53d581c5 0
   db01e8ea3388fd3c7c94e1436ea2bd6a53d581c5 default
 
@@ -170,7 +184,8 @@ Pushing everything:
 
   $ hg push -qf ../target
 
-  $ cat ../target/$branchcache
+  $ (cd ../target/; listbranchcaches)
+  === .hg/cache/branchheads-unserved ===
   adf1a74a7f7b4cd193d12992f5d0d6a004ed21d6 4
   1c28f494dae69a2f8fc815059d257eccf3fcfe75 default
   adf1a74a7f7b4cd193d12992f5d0d6a004ed21d6 foo
diff --git a/tests/test-obsolete-divergent.t b/tests/test-obsolete-divergent.t
--- a/tests/test-obsolete-divergent.t
+++ b/tests/test-obsolete-divergent.t
@@ -62,6 +62,7 @@ A_1 have two direct and divergent succes
   $ newcase direct
   $ hg debugobsolete `getid A_0` `getid A_1`
   $ hg debugobsolete `getid A_0` `getid A_2`
+  invalid branchheads cache (unserved): tip differs
   $ hg log -G --hidden
   o  3:392fd25390da A_2
   |
@@ -103,6 +104,7 @@ indirect divergence with known changeset
   $ newcase indirect_known
   $ hg debugobsolete `getid A_0` `getid A_1`
   $ hg debugobsolete `getid A_0` `getid A_2`
+  invalid branchheads cache (unserved): tip differs
   $ mkcommit A_3
   created new head
   $ hg debugobsolete `getid A_2` `getid A_3`
@@ -141,6 +143,7 @@ indirect divergence with known changeset
   $ newcase indirect_unknown
   $ hg debugobsolete `getid A_0` aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
   $ hg debugobsolete aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa `getid A_1`
+  invalid branchheads cache (unserved): tip differs
   $ hg debugobsolete `getid A_0` `getid A_2`
   $ hg log -G --hidden
   o  3:392fd25390da A_2
@@ -172,6 +175,7 @@ do not take unknown node in account if t
   $ newcase final-unknown
   $ hg debugobsolete `getid A_0` `getid A_1`
   $ hg debugobsolete `getid A_1` `getid A_2`
+  invalid branchheads cache (unserved): tip differs
   $ hg debugobsolete `getid A_0` bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
   $ hg debugobsolete bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb cccccccccccccccccccccccccccccccccccccccc
   $ hg debugobsolete `getid A_1` dddddddddddddddddddddddddddddddddddddddd
@@ -188,6 +192,7 @@ divergence that converge again is not di
   $ newcase converged_divergence
   $ hg debugobsolete `getid A_0` `getid A_1`
   $ hg debugobsolete `getid A_0` `getid A_2`
+  invalid branchheads cache (unserved): tip differs
   $ mkcommit A_3
   created new head
   $ hg debugobsolete `getid A_1` `getid A_3`
@@ -434,6 +439,7 @@ successors-set. (report [A,B] not [A] + 
   $ newcase subset
   $ hg debugobsolete `getid A_0` `getid A_2`
   $ hg debugobsolete `getid A_0` `getid A_1` `getid A_2`
+  invalid branchheads cache (unserved): tip differs
   $ hg debugsuccessorssets 'desc('A_0')'
   007dc284c1f8
       82623d38b9ba 392fd25390da
diff --git a/tests/test-rebase-collapse.t b/tests/test-rebase-collapse.t
--- a/tests/test-rebase-collapse.t
+++ b/tests/test-rebase-collapse.t
@@ -274,7 +274,7 @@ also, the parent of a node that is a chi
   7:c65502d4178782309ce0574c5ae6ee9485a9bafa default
   6:c772a8b2dc17629cec88a19d09c926c4814b12c7 default
 
-  $ cat $TESTTMP/b2/.hg/cache/branchheads
+  $ cat $TESTTMP/b2/.hg/cache/branchheads-unserved
   c65502d4178782309ce0574c5ae6ee9485a9bafa 7
   c772a8b2dc17629cec88a19d09c926c4814b12c7 default
   c65502d4178782309ce0574c5ae6ee9485a9bafa default