diff --git a/mercurial/exchange.py b/mercurial/exchange.py
--- a/mercurial/exchange.py
+++ b/mercurial/exchange.py
@@ -83,6 +83,8 @@ class pushoperation(object):
         self.fallbackoutdatedphases = None
         # outgoing obsmarkers
         self.outobsmarkers = set()
+        # outgoing bookmarks
+        self.outbookmarks = []
 
     @util.propertycache
     def futureheads(self):
@@ -280,6 +282,24 @@ def _pushdiscoveryphase(pushop):
 def _pushdiscoveryobsmarkers(pushop):
     pushop.outobsmarkers = pushop.repo.obsstore
 
+@pushdiscovery('bookmarks')
+def _pushdiscoverybookmarks(pushop):
+    ui = pushop.ui
+    repo = pushop.repo.unfiltered()
+    remote = pushop.remote
+    ui.debug("checking for updated bookmarks\n")
+    ancestors = ()
+    if pushop.revs:
+        revnums = map(repo.changelog.rev, pushop.revs)
+        ancestors = repo.changelog.ancestors(revnums, inclusive=True)
+    remotebookmark = remote.listkeys('bookmarks')
+
+    comp = bookmarks.compare(repo, repo._bookmarks, remotebookmark, srchex=hex)
+    (addsrc, adddst, advsrc, advdst, diverge, differ, invalid) = comp
+    for b, scid, dcid in advsrc:
+        if not ancestors or repo[scid].rev() in ancestors:
+            pushop.outbookmarks.append((b, dcid, scid))
+
 def _pushcheckoutgoing(pushop):
     outgoing = pushop.outgoing
     unfi = pushop.repo.unfiltered()
@@ -616,20 +636,9 @@ def _pushbookmark(pushop):
     if pushop.ret == 0:
         return
     ui = pushop.ui
-    repo = pushop.repo.unfiltered()
     remote = pushop.remote
-    ui.debug("checking for updated bookmarks\n")
-    ancestors = ()
-    if pushop.revs:
-        revnums = map(repo.changelog.rev, pushop.revs)
-        ancestors = repo.changelog.ancestors(revnums, inclusive=True)
-    remotebookmark = remote.listkeys('bookmarks')
-    comp = bookmarks.compare(repo, repo._bookmarks, remotebookmark, srchex=hex)
-    (addsrc, adddst, advsrc, advdst, diverge, differ, invalid) = comp
-    for b, scid, dcid in advsrc:
-        if ancestors and repo[scid].rev() not in ancestors:
-            continue
-        if remote.pushkey('bookmarks', b, dcid, scid):
+    for b, old, new in pushop.outbookmarks:
+        if remote.pushkey('bookmarks', b, old, new):
             ui.status(_("updating bookmark %s\n") % b)
         else:
             ui.warn(_('updating bookmark %s failed!\n') % b)
diff --git a/tests/test-acl.t b/tests/test-acl.t
--- a/tests/test-acl.t
+++ b/tests/test-acl.t
@@ -83,6 +83,8 @@ Extension disabled for lack of a hook
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   listing keys for "bookmarks"
   3 changesets found
   list of changesets:
@@ -120,8 +122,6 @@ Extension disabled for lack of a hook
   updating the branch cache
   listing keys for "phases"
   try to push obsolete markers to remote
-  checking for updated bookmarks
-  listing keys for "bookmarks"
   repository tip rolled back to revision 0 (undo push)
   0:6675d58eff77
   
@@ -142,6 +142,8 @@ Extension disabled for lack of acl.sourc
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -182,8 +184,6 @@ Extension disabled for lack of acl.sourc
   updating the branch cache
   listing keys for "phases"
   try to push obsolete markers to remote
-  checking for updated bookmarks
-  listing keys for "bookmarks"
   repository tip rolled back to revision 0 (undo push)
   0:6675d58eff77
   
@@ -205,6 +205,8 @@ No [acl.allow]/[acl.deny]
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -255,8 +257,6 @@ No [acl.allow]/[acl.deny]
   updating the branch cache
   listing keys for "phases"
   try to push obsolete markers to remote
-  checking for updated bookmarks
-  listing keys for "bookmarks"
   repository tip rolled back to revision 0 (undo push)
   0:6675d58eff77
   
@@ -278,6 +278,8 @@ Empty [acl.allow]
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -346,6 +348,8 @@ fred is allowed inside foo/
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -419,6 +423,8 @@ Empty [acl.deny]
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -489,6 +495,8 @@ fred is allowed inside foo/, but not foo
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -564,6 +572,8 @@ fred is allowed inside foo/, but not foo
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -636,6 +646,8 @@ fred is allowed inside foo/, but not foo
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -710,6 +722,8 @@ barney is allowed everywhere
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -760,8 +774,6 @@ barney is allowed everywhere
   updating the branch cache
   listing keys for "phases"
   try to push obsolete markers to remote
-  checking for updated bookmarks
-  listing keys for "bookmarks"
   repository tip rolled back to revision 0 (undo push)
   0:6675d58eff77
   
@@ -790,6 +802,8 @@ wilma can change files with a .txt exten
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -871,6 +885,8 @@ file specified by acl.config does not ex
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -908,10 +924,10 @@ file specified by acl.config does not ex
   added 3 changesets with 3 changes to 3 files
   calling hook pretxnchangegroup.acl: hgext.acl.hook
   acl: checking access for user "barney"
-  error: pretxnchangegroup.acl hook raised an exception: [Errno *] *: '../acl.config' (glob)
+  error: pretxnchangegroup.acl hook raised an exception: [Errno 2] No such file or directory: '../acl.config'
   transaction abort!
   rollback completed
-  abort: *: ../acl.config (glob)
+  abort: No such file or directory: ../acl.config
   no rollback information available
   0:6675d58eff77
   
@@ -947,6 +963,8 @@ betty is allowed inside foo/ by a acl.co
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -1034,6 +1052,8 @@ acl.config can set only [acl.allow]/[acl
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -1084,8 +1104,6 @@ acl.config can set only [acl.allow]/[acl
   updating the branch cache
   listing keys for "phases"
   try to push obsolete markers to remote
-  checking for updated bookmarks
-  listing keys for "bookmarks"
   repository tip rolled back to revision 0 (undo push)
   0:6675d58eff77
   
@@ -1115,6 +1133,8 @@ fred is always allowed
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -1165,8 +1185,6 @@ fred is always allowed
   updating the branch cache
   listing keys for "phases"
   try to push obsolete markers to remote
-  checking for updated bookmarks
-  listing keys for "bookmarks"
   repository tip rolled back to revision 0 (undo push)
   0:6675d58eff77
   
@@ -1192,6 +1210,8 @@ no one is allowed inside foo/Bar/
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -1269,6 +1289,8 @@ OS-level groups
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -1320,8 +1342,6 @@ OS-level groups
   updating the branch cache
   listing keys for "phases"
   try to push obsolete markers to remote
-  checking for updated bookmarks
-  listing keys for "bookmarks"
   repository tip rolled back to revision 0 (undo push)
   0:6675d58eff77
   
@@ -1347,6 +1367,8 @@ OS-level groups
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   invalid branchheads cache (served): tip differs
   listing keys for "bookmarks"
   3 changesets found
@@ -1463,6 +1485,8 @@ No branch acls specified
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
@@ -1523,8 +1547,6 @@ No branch acls specified
   updating the branch cache
   listing keys for "phases"
   try to push obsolete markers to remote
-  checking for updated bookmarks
-  listing keys for "bookmarks"
   repository tip rolled back to revision 2 (undo push)
   2:fb35475503ef
   
@@ -1547,6 +1569,8 @@ Branch acl deny test
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
@@ -1627,6 +1651,8 @@ Branch acl empty allow test
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
@@ -1703,6 +1729,8 @@ Branch acl allow other
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
@@ -1773,6 +1801,8 @@ Branch acl allow other
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
@@ -1833,8 +1863,6 @@ Branch acl allow other
   updating the branch cache
   listing keys for "phases"
   try to push obsolete markers to remote
-  checking for updated bookmarks
-  listing keys for "bookmarks"
   repository tip rolled back to revision 2 (undo push)
   2:fb35475503ef
   
@@ -1862,6 +1890,8 @@ push foobar into the remote
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
@@ -1922,8 +1952,6 @@ push foobar into the remote
   updating the branch cache
   listing keys for "phases"
   try to push obsolete markers to remote
-  checking for updated bookmarks
-  listing keys for "bookmarks"
   repository tip rolled back to revision 2 (undo push)
   2:fb35475503ef
   
@@ -1950,6 +1978,8 @@ Branch acl conflicting deny
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
@@ -2025,6 +2055,8 @@ User 'astro' must not be denied
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
@@ -2085,8 +2117,6 @@ User 'astro' must not be denied
   updating the branch cache
   listing keys for "phases"
   try to push obsolete markers to remote
-  checking for updated bookmarks
-  listing keys for "bookmarks"
   repository tip rolled back to revision 2 (undo push)
   2:fb35475503ef
   
@@ -2107,6 +2137,8 @@ Non-astro users must be denied
   searching for changes
   all remote heads known locally
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   listing keys for "bookmarks"
   4 changesets found
   list of changesets:
diff --git a/tests/test-hook.t b/tests/test-hook.t
--- a/tests/test-hook.t
+++ b/tests/test-hook.t
@@ -211,10 +211,10 @@ test that prepushkey can prevent incomin
   pushing to ../a
   searching for changes
   listkeys hook: HG_NAMESPACE=phases HG_VALUES={'cb9a9f314b8b07ba71012fcdbc544b5a4d82ff5b': '1', 'publishing': 'True'}
+  listkeys hook: HG_NAMESPACE=bookmarks HG_VALUES={'bar': '0000000000000000000000000000000000000000', 'foo': '0000000000000000000000000000000000000000'}
   no changes found
   listkeys hook: HG_NAMESPACE=phases HG_VALUES={'cb9a9f314b8b07ba71012fcdbc544b5a4d82ff5b': '1', 'publishing': 'True'}
   listkeys hook: HG_NAMESPACE=bookmarks HG_VALUES={'bar': '0000000000000000000000000000000000000000', 'foo': '0000000000000000000000000000000000000000'}
-  listkeys hook: HG_NAMESPACE=bookmarks HG_VALUES={'bar': '0000000000000000000000000000000000000000', 'foo': '0000000000000000000000000000000000000000'}
   exporting bookmark baz
   prepushkey.forbid hook: HG_KEY=baz HG_NAMESPACE=bookmarks HG_NEW=0000000000000000000000000000000000000000
   abort: prepushkey hook exited with status 1
diff --git a/tests/test-http.t b/tests/test-http.t
--- a/tests/test-http.t
+++ b/tests/test-http.t
@@ -263,12 +263,12 @@ test http authentication
   "GET /?cmd=batch HTTP/1.1" 200 - x-hgarg-1:cmds=heads+%3Bknown+nodes%3D7f4e523d01f2cc3765ac8934da3d14db775ff872
   "GET /?cmd=listkeys HTTP/1.1" 401 - x-hgarg-1:namespace=phases
   "GET /?cmd=listkeys HTTP/1.1" 200 - x-hgarg-1:namespace=phases
+  "GET /?cmd=listkeys HTTP/1.1" 200 - x-hgarg-1:namespace=bookmarks
   "GET /?cmd=branchmap HTTP/1.1" 200 -
   "GET /?cmd=branchmap HTTP/1.1" 200 -
   "GET /?cmd=listkeys HTTP/1.1" 200 - x-hgarg-1:namespace=bookmarks
   "POST /?cmd=unbundle HTTP/1.1" 200 - x-hgarg-1:heads=686173686564+5eb5abfefeea63c80dd7553bcc3783f37e0c5524
   "GET /?cmd=listkeys HTTP/1.1" 200 - x-hgarg-1:namespace=phases
-  "GET /?cmd=listkeys HTTP/1.1" 200 - x-hgarg-1:namespace=bookmarks
 
 #endif
   $ cd ..
diff --git a/tests/test-obsolete.t b/tests/test-obsolete.t
--- a/tests/test-obsolete.t
+++ b/tests/test-obsolete.t
@@ -326,9 +326,9 @@ Check obsolete keys are exchanged only i
   $ hg --config extensions.debugkeys=debugkeys.py -R empty push tmpd
   pushing to tmpd
   listkeys phases
+  listkeys bookmarks
   no changes found
   listkeys phases
-  listkeys bookmarks
   [1]
 
 clone support
diff --git a/tests/test-push-warn.t b/tests/test-push-warn.t
--- a/tests/test-push-warn.t
+++ b/tests/test-push-warn.t
@@ -36,6 +36,8 @@
   query 2; still undecided: 1, sample size is: 1
   2 total queries
   listing keys for "phases"
+  checking for updated bookmarks
+  listing keys for "bookmarks"
   listing keys for "bookmarks"
   remote has heads on branch 'default' that are not known locally: 1c9246a22a0a
   new remote heads on branch 'default':
diff --git a/tests/test-treediscovery.t b/tests/test-treediscovery.t
--- a/tests/test-treediscovery.t
+++ b/tests/test-treediscovery.t
@@ -523,12 +523,12 @@ Both have new stuff in existing named br
   "GET /?cmd=capabilities HTTP/1.1" 200 -
   "GET /?cmd=heads HTTP/1.1" 200 -
   "GET /?cmd=listkeys HTTP/1.1" 200 - x-hgarg-1:namespace=phases
+  "GET /?cmd=listkeys HTTP/1.1" 200 - x-hgarg-1:namespace=bookmarks
   "GET /?cmd=branchmap HTTP/1.1" 200 -
   "GET /?cmd=branchmap HTTP/1.1" 200 -
   "GET /?cmd=listkeys HTTP/1.1" 200 - x-hgarg-1:namespace=bookmarks
   "POST /?cmd=unbundle HTTP/1.1" 200 - x-hgarg-1:heads=686173686564+1827a5bb63e602382eb89dd58f2ac9f3b007ad91
   "GET /?cmd=listkeys HTTP/1.1" 200 - x-hgarg-1:namespace=phases
-  "GET /?cmd=listkeys HTTP/1.1" 200 - x-hgarg-1:namespace=bookmarks
   "GET /?cmd=capabilities HTTP/1.1" 200 -
   "GET /?cmd=heads HTTP/1.1" 200 -
   "GET /?cmd=capabilities HTTP/1.1" 200 -