diff --git a/mercurial/bundle2.py b/mercurial/bundle2.py
--- a/mercurial/bundle2.py
+++ b/mercurial/bundle2.py
@@ -1788,7 +1788,7 @@ def _addpartsfromopts(ui, repo, bundler,
         addpartrevbranchcache(repo, bundler, outgoing)
 
     if opts.get(b'obsolescence', False):
-        obsmarkers = repo.obsstore.relevantmarkers(outgoing.missing)
+        obsmarkers = repo.obsstore.relevantmarkers(nodes=outgoing.missing)
         buildobsmarkerspart(
             bundler,
             obsmarkers,
diff --git a/mercurial/exchange.py b/mercurial/exchange.py
--- a/mercurial/exchange.py
+++ b/mercurial/exchange.py
@@ -703,8 +703,8 @@ def _pushdiscoveryobsmarkers(pushop):
     repo = pushop.repo
     # very naive computation, that can be quite expensive on big repo.
     # However: evolution is currently slow on them anyway.
-    nodes = (c.node() for c in repo.set(b'::%ln', pushop.futureheads))
-    pushop.outobsmarkers = pushop.repo.obsstore.relevantmarkers(nodes)
+    repo.revs(b'::%ln', pushop.futureheads)
+    pushop.outobsmarkers = pushop.repo.obsstore.relevantmarkers(revs=revs)
 
 
 @pushdiscovery(b'bookmarks')
@@ -2603,10 +2603,15 @@ def _getbundleobsmarkerpart(
 ):
     """add an obsolescence markers part to the requested bundle"""
     if kwargs.get('obsmarkers', False):
+        unfi_cl = repo.unfiltered().changelog
         if heads is None:
-            heads = repo.heads()
-        subset = [c.node() for c in repo.set(b'::%ln', heads)]
-        markers = repo.obsstore.relevantmarkers(subset)
+            headrevs = repo.changelog.headrevs()
+        else:
+            get_rev = unfi_cl.index.get_rev
+            headrevs = [get_rev(node) for node in heads]
+            headrevs = [rev for rev in headrevs if rev is not None]
+        revs = unfi_cl.ancestors(headrevs, inclusive=True)
+        markers = repo.obsstore.relevantmarkers(revs=revs)
         markers = obsutil.sortedmarkers(markers)
         bundle2.buildobsmarkerspart(bundler, markers)
 
diff --git a/mercurial/obsolete.py b/mercurial/obsolete.py
--- a/mercurial/obsolete.py
+++ b/mercurial/obsolete.py
@@ -771,10 +771,11 @@ class obsstore:
             _addchildren(self.children, markers)
         _checkinvalidmarkers(self.repo, markers)
 
-    def relevantmarkers(self, nodes):
-        """return a set of all obsolescence markers relevant to a set of nodes.
+    def relevantmarkers(self, nodes=None, revs=None):
+        """return a set of all obsolescence markers relevant to a set of
+        nodes or revisions.
 
-        "relevant" to a set of nodes mean:
+        "relevant" to a set of nodes or revisions mean:
 
         - marker that use this changeset as successor
         - prune marker of direct children on this changeset
@@ -782,13 +783,33 @@ class obsstore:
           markers
 
         It is a set so you cannot rely on order."""
+        if nodes is None:
+            nodes = set()
+        if revs is None:
+            revs = set()
 
-        pendingnodes = set(nodes)
-        seenmarkers = set()
-        seennodes = set(pendingnodes)
+        tonode = self.repo.unfiltered().changelog.node
+        pendingnodes = set()
         precursorsmarkers = self.predecessors
         succsmarkers = self.successors
         children = self.children
+        for node in nodes:
+            if (
+                node in precursorsmarkers
+                or node in succsmarkers
+                or node in children
+            ):
+                pendingnodes.add(node)
+        for rev in revs:
+            node = tonode(rev)
+            if (
+                node in precursorsmarkers
+                or node in succsmarkers
+                or node in children
+            ):
+                pendingnodes.add(node)
+        seenmarkers = set()
+        seennodes = pendingnodes.copy()
         while pendingnodes:
             direct = set()
             for current in pendingnodes:
diff --git a/mercurial/obsutil.py b/mercurial/obsutil.py
--- a/mercurial/obsutil.py
+++ b/mercurial/obsutil.py
@@ -108,7 +108,7 @@ def getmarkers(repo, nodes=None, exclusi
     elif exclusive:
         rawmarkers = exclusivemarkers(repo, nodes)
     else:
-        rawmarkers = repo.obsstore.relevantmarkers(nodes)
+        rawmarkers = repo.obsstore.relevantmarkers(nodes=nodes)
 
     for markerdata in rawmarkers:
         yield marker(repo, markerdata)