##// END OF EJS Templates
upstream » mercurial-mirror
RSS

Clone from https://www.mercurial-scm.org/repo/hg-all

setdiscovery: fix hang when #heads>200 (issue2971)...
Peter Arrenbrecht -
r15063:c20688b7 stable
parent child Browse files
Show More
Show file before | Show file after | Hide comments
@@ -1,194 +1,194
1 1 # setdiscovery.py - improved discovery of common nodeset for mercurial
2 2 #
3 3 # Copyright 2010 Benoit Boissinot <bboissin@gmail.com>
4 4 # and Peter Arrenbrecht <peter@arrenbrecht.ch>
5 5 #
6 6 # This software may be used and distributed according to the terms of the
7 7 # GNU General Public License version 2 or any later version.
8 8
9 9 from node import nullid
10 10 from i18n import _
11 11 import random, collections, util, dagutil
12 12
13 13 def _updatesample(dag, nodes, sample, always, quicksamplesize=0):
14 14 # if nodes is empty we scan the entire graph
15 15 if nodes:
16 16 heads = dag.headsetofconnecteds(nodes)
17 17 else:
18 18 heads = dag.heads()
19 19 dist = {}
20 20 visit = collections.deque(heads)
21 21 seen = set()
22 22 factor = 1
23 23 while visit:
24 24 curr = visit.popleft()
25 25 if curr in seen:
26 26 continue
27 27 d = dist.setdefault(curr, 1)
28 28 if d > factor:
29 29 factor *= 2
30 30 if d == factor:
31 31 if curr not in always: # need this check for the early exit below
32 32 sample.add(curr)
33 33 if quicksamplesize and (len(sample) >= quicksamplesize):
34 34 return
35 35 seen.add(curr)
36 36 for p in dag.parents(curr):
37 37 if not nodes or p in nodes:
38 38 dist.setdefault(p, d + 1)
39 39 visit.append(p)
40 40
41 41 def _setupsample(dag, nodes, size):
42 42 if len(nodes) <= size:
43 43 return set(nodes), None, 0
44 always = set(dag.heads())
44 always = dag.headsetofconnecteds(nodes)
45 45 desiredlen = size - len(always)
46 46 if desiredlen <= 0:
47 47 # This could be bad if there are very many heads, all unknown to the
48 48 # server. We're counting on long request support here.
49 49 return always, None, desiredlen
50 50 return always, set(), desiredlen
51 51
52 52 def _takequicksample(dag, nodes, size, initial):
53 53 always, sample, desiredlen = _setupsample(dag, nodes, size)
54 54 if sample is None:
55 55 return always
56 56 if initial:
57 57 fromset = None
58 58 else:
59 59 fromset = nodes
60 60 _updatesample(dag, fromset, sample, always, quicksamplesize=desiredlen)
61 61 sample.update(always)
62 62 return sample
63 63
64 64 def _takefullsample(dag, nodes, size):
65 65 always, sample, desiredlen = _setupsample(dag, nodes, size)
66 66 if sample is None:
67 67 return always
68 68 # update from heads
69 69 _updatesample(dag, nodes, sample, always)
70 70 # update from roots
71 71 _updatesample(dag.inverse(), nodes, sample, always)
72 72 assert sample
73 73 if len(sample) > desiredlen:
74 74 sample = set(random.sample(sample, desiredlen))
75 75 elif len(sample) < desiredlen:
76 76 more = desiredlen - len(sample)
77 77 sample.update(random.sample(list(nodes - sample - always), more))
78 78 sample.update(always)
79 79 return sample
80 80
81 81 def findcommonheads(ui, local, remote,
82 82 initialsamplesize=100,
83 83 fullsamplesize=200,
84 84 abortwhenunrelated=True):
85 85 '''Return a tuple (common, anyincoming, remoteheads) used to identify
86 86 missing nodes from or in remote.
87 87
88 88 shortcutlocal determines whether we try use direct access to localrepo if
89 89 remote is actually local.
90 90 '''
91 91 roundtrips = 0
92 92 cl = local.changelog
93 93 dag = dagutil.revlogdag(cl)
94 94
95 95 # early exit if we know all the specified remote heads already
96 96 ui.debug("query 1; heads\n")
97 97 roundtrips += 1
98 98 ownheads = dag.heads()
99 99 sample = ownheads
100 100 if remote.local():
101 101 # stopgap until we have a proper localpeer that supports batch()
102 102 srvheadhashes = remote.heads()
103 103 yesno = remote.known(dag.externalizeall(sample))
104 104 elif remote.capable('batch'):
105 105 batch = remote.batch()
106 106 srvheadhashesref = batch.heads()
107 107 yesnoref = batch.known(dag.externalizeall(sample))
108 108 batch.submit()
109 109 srvheadhashes = srvheadhashesref.value
110 110 yesno = yesnoref.value
111 111 else:
112 112 # compatibitity with pre-batch, but post-known remotes during 1.9 devel
113 113 srvheadhashes = remote.heads()
114 114 sample = []
115 115
116 116 if cl.tip() == nullid:
117 117 if srvheadhashes != [nullid]:
118 118 return [nullid], True, srvheadhashes
119 119 return [nullid], False, []
120 120
121 121 # start actual discovery (we note this before the next "if" for
122 122 # compatibility reasons)
123 123 ui.status(_("searching for changes\n"))
124 124
125 125 srvheads = dag.internalizeall(srvheadhashes, filterunknown=True)
126 126 if len(srvheads) == len(srvheadhashes):
127 127 ui.debug("all remote heads known locally\n")
128 128 return (srvheadhashes, False, srvheadhashes,)
129 129
130 130 if sample and util.all(yesno):
131 131 ui.note("all local heads known remotely\n")
132 132 ownheadhashes = dag.externalizeall(ownheads)
133 133 return (ownheadhashes, True, srvheadhashes,)
134 134
135 135 # full blown discovery
136 136 undecided = dag.nodeset() # own nodes where I don't know if remote knows them
137 137 common = set() # own nodes I know we both know
138 138 missing = set() # own nodes I know remote lacks
139 139
140 140 # treat remote heads (and maybe own heads) as a first implicit sample response
141 141 common.update(dag.ancestorset(srvheads))
142 142 undecided.difference_update(common)
143 143
144 144 full = False
145 145 while undecided:
146 146
147 147 if sample:
148 148 commoninsample = set(n for i, n in enumerate(sample) if yesno[i])
149 149 common.update(dag.ancestorset(commoninsample, common))
150 150
151 151 missinginsample = [n for i, n in enumerate(sample) if not yesno[i]]
152 152 missing.update(dag.descendantset(missinginsample, missing))
153 153
154 154 undecided.difference_update(missing)
155 155 undecided.difference_update(common)
156 156
157 157 if not undecided:
158 158 break
159 159
160 160 if full:
161 161 ui.note("sampling from both directions\n")
162 162 sample = _takefullsample(dag, undecided, size=fullsamplesize)
163 163 elif common:
164 164 # use cheapish initial sample
165 165 ui.debug("taking initial sample\n")
166 166 sample = _takefullsample(dag, undecided, size=fullsamplesize)
167 167 else:
168 168 # use even cheaper initial sample
169 169 ui.debug("taking quick initial sample\n")
170 170 sample = _takequicksample(dag, undecided, size=initialsamplesize,
171 171 initial=True)
172 172
173 173 roundtrips += 1
174 174 ui.progress(_('searching'), roundtrips, unit=_('queries'))
175 175 ui.debug("query %i; still undecided: %i, sample size is: %i\n"
176 176 % (roundtrips, len(undecided), len(sample)))
177 177 # indices between sample and externalized version must match
178 178 sample = list(sample)
179 179 yesno = remote.known(dag.externalizeall(sample))
180 180 full = True
181 181
182 182 result = dag.headsetofconnecteds(common)
183 183 ui.progress(_('searching'), None)
184 184 ui.debug("%d total queries\n" % roundtrips)
185 185
186 186 if not result and srvheadhashes != [nullid]:
187 187 if abortwhenunrelated:
188 188 raise util.Abort(_("repository is unrelated"))
189 189 else:
190 190 ui.warn(_("warning: repository is unrelated\n"))
191 191 return (set([nullid]), True, srvheadhashes,)
192 192
193 193 anyincoming = (srvheadhashes != [nullid])
194 194 return dag.externalizeall(result), anyincoming, srvheadhashes
Show file before | Show file after | Hide comments
@@ -1,268 +1,326
1 1
2 2 Function to test discovery between two repos in both directions, using both the local shortcut
3 3 (which is currently not activated by default) and the full remotable protocol:
4 4
5 5 $ testdesc() { # revs_a, revs_b, dagdesc
6 6 > if [ -d foo ]; then rm -rf foo; fi
7 7 > hg init foo
8 8 > cd foo
9 9 > hg debugbuilddag "$3"
10 10 > hg clone . a $1 --quiet
11 11 > hg clone . b $2 --quiet
12 12 > echo
13 13 > echo "% -- a -> b tree"
14 14 > hg -R a debugdiscovery b --verbose --old
15 15 > echo
16 16 > echo "% -- a -> b set"
17 17 > hg -R a debugdiscovery b --verbose --debug
18 18 > echo
19 19 > echo "% -- b -> a tree"
20 20 > hg -R b debugdiscovery a --verbose --old
21 21 > echo
22 22 > echo "% -- b -> a set"
23 23 > hg -R b debugdiscovery a --verbose --debug
24 24 > cd ..
25 25 > }
26 26
27 27
28 28 Small superset:
29 29
30 30 $ testdesc '-ra1 -ra2' '-rb1 -rb2 -rb3' '
31 31 > +2:f +1:a1:b1
32 32 > <f +4 :a2
33 33 > +5 :b2
34 34 > <f +3 :b3'
35 35
36 36 % -- a -> b tree
37 37 comparing with b
38 38 searching for changes
39 39 unpruned common: b5714e113bc0 66f7d451a68b 01241442b3c2
40 40 common heads: b5714e113bc0 01241442b3c2
41 41 local is subset
42 42
43 43 % -- a -> b set
44 44 comparing with b
45 45 query 1; heads
46 46 searching for changes
47 47 all local heads known remotely
48 48 common heads: b5714e113bc0 01241442b3c2
49 49 local is subset
50 50
51 51 % -- b -> a tree
52 52 comparing with a
53 53 searching for changes
54 54 unpruned common: b5714e113bc0 01241442b3c2
55 55 common heads: b5714e113bc0 01241442b3c2
56 56 remote is subset
57 57
58 58 % -- b -> a set
59 59 comparing with a
60 60 query 1; heads
61 61 searching for changes
62 62 all remote heads known locally
63 63 common heads: b5714e113bc0 01241442b3c2
64 64 remote is subset
65 65
66 66
67 67 Many new:
68 68
69 69 $ testdesc '-ra1 -ra2' '-rb' '
70 70 > +2:f +3:a1 +3:b
71 71 > <f +30 :a2'
72 72
73 73 % -- a -> b tree
74 74 comparing with b
75 75 searching for changes
76 76 unpruned common: bebd167eb94d
77 77 common heads: bebd167eb94d
78 78
79 79 % -- a -> b set
80 80 comparing with b
81 81 query 1; heads
82 82 searching for changes
83 83 taking initial sample
84 84 searching: 2 queries
85 85 query 2; still undecided: 29, sample size is: 29
86 86 2 total queries
87 87 common heads: bebd167eb94d
88 88
89 89 % -- b -> a tree
90 90 comparing with a
91 91 searching for changes
92 92 unpruned common: bebd167eb94d 66f7d451a68b
93 93 common heads: bebd167eb94d
94 94
95 95 % -- b -> a set
96 96 comparing with a
97 97 query 1; heads
98 98 searching for changes
99 99 taking initial sample
100 100 searching: 2 queries
101 101 query 2; still undecided: 2, sample size is: 2
102 102 2 total queries
103 103 common heads: bebd167eb94d
104 104
105 105
106 106 Both sides many new with stub:
107 107
108 108 $ testdesc '-ra1 -ra2' '-rb' '
109 109 > +2:f +2:a1 +30 :b
110 110 > <f +30 :a2'
111 111
112 112 % -- a -> b tree
113 113 comparing with b
114 114 searching for changes
115 115 unpruned common: 2dc09a01254d
116 116 common heads: 2dc09a01254d
117 117
118 118 % -- a -> b set
119 119 comparing with b
120 120 query 1; heads
121 121 searching for changes
122 122 taking initial sample
123 123 searching: 2 queries
124 124 query 2; still undecided: 29, sample size is: 29
125 125 2 total queries
126 126 common heads: 2dc09a01254d
127 127
128 128 % -- b -> a tree
129 129 comparing with a
130 130 searching for changes
131 131 unpruned common: 66f7d451a68b 2dc09a01254d
132 132 common heads: 2dc09a01254d
133 133
134 134 % -- b -> a set
135 135 comparing with a
136 136 query 1; heads
137 137 searching for changes
138 138 taking initial sample
139 139 searching: 2 queries
140 140 query 2; still undecided: 29, sample size is: 29
141 141 2 total queries
142 142 common heads: 2dc09a01254d
143 143
144 144
145 145 Both many new:
146 146
147 147 $ testdesc '-ra' '-rb' '
148 148 > +2:f +30 :b
149 149 > <f +30 :a'
150 150
151 151 % -- a -> b tree
152 152 comparing with b
153 153 searching for changes
154 154 unpruned common: 66f7d451a68b
155 155 common heads: 66f7d451a68b
156 156
157 157 % -- a -> b set
158 158 comparing with b
159 159 query 1; heads
160 160 searching for changes
161 161 taking quick initial sample
162 162 searching: 2 queries
163 163 query 2; still undecided: 31, sample size is: 31
164 164 2 total queries
165 165 common heads: 66f7d451a68b
166 166
167 167 % -- b -> a tree
168 168 comparing with a
169 169 searching for changes
170 170 unpruned common: 66f7d451a68b
171 171 common heads: 66f7d451a68b
172 172
173 173 % -- b -> a set
174 174 comparing with a
175 175 query 1; heads
176 176 searching for changes
177 177 taking quick initial sample
178 178 searching: 2 queries
179 179 query 2; still undecided: 31, sample size is: 31
180 180 2 total queries
181 181 common heads: 66f7d451a68b
182 182
183 183
184 184 Both many new skewed:
185 185
186 186 $ testdesc '-ra' '-rb' '
187 187 > +2:f +30 :b
188 188 > <f +50 :a'
189 189
190 190 % -- a -> b tree
191 191 comparing with b
192 192 searching for changes
193 193 unpruned common: 66f7d451a68b
194 194 common heads: 66f7d451a68b
195 195
196 196 % -- a -> b set
197 197 comparing with b
198 198 query 1; heads
199 199 searching for changes
200 200 taking quick initial sample
201 201 searching: 2 queries
202 202 query 2; still undecided: 51, sample size is: 51
203 203 2 total queries
204 204 common heads: 66f7d451a68b
205 205
206 206 % -- b -> a tree
207 207 comparing with a
208 208 searching for changes
209 209 unpruned common: 66f7d451a68b
210 210 common heads: 66f7d451a68b
211 211
212 212 % -- b -> a set
213 213 comparing with a
214 214 query 1; heads
215 215 searching for changes
216 216 taking quick initial sample
217 217 searching: 2 queries
218 218 query 2; still undecided: 31, sample size is: 31
219 219 2 total queries
220 220 common heads: 66f7d451a68b
221 221
222 222
223 223 Both many new on top of long history:
224 224
225 225 $ testdesc '-ra' '-rb' '
226 226 > +1000:f +30 :b
227 227 > <f +50 :a'
228 228
229 229 % -- a -> b tree
230 230 comparing with b
231 231 searching for changes
232 232 unpruned common: 7ead0cba2838
233 233 common heads: 7ead0cba2838
234 234
235 235 % -- a -> b set
236 236 comparing with b
237 237 query 1; heads
238 238 searching for changes
239 239 taking quick initial sample
240 240 searching: 2 queries
241 241 query 2; still undecided: 1049, sample size is: 11
242 242 sampling from both directions
243 243 searching: 3 queries
244 244 query 3; still undecided: 31, sample size is: 31
245 245 3 total queries
246 246 common heads: 7ead0cba2838
247 247
248 248 % -- b -> a tree
249 249 comparing with a
250 250 searching for changes
251 251 unpruned common: 7ead0cba2838
252 252 common heads: 7ead0cba2838
253 253
254 254 % -- b -> a set
255 255 comparing with a
256 256 query 1; heads
257 257 searching for changes
258 258 taking quick initial sample
259 259 searching: 2 queries
260 260 query 2; still undecided: 1029, sample size is: 11
261 261 sampling from both directions
262 262 searching: 3 queries
263 263 query 3; still undecided: 15, sample size is: 15
264 264 3 total queries
265 265 common heads: 7ead0cba2838
266 266
267 267
268 One with >200 heads, which used to use up all of the sample:
268 269
270 $ hg init manyheads
271 $ cd manyheads
272 $ echo "+300:r @a" >dagdesc
273 $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
274 $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
275 $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
276 $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
277 $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
278 $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
279 $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
280 $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
281 $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
282 $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
283 $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
284 $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
285 $ echo "*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3 *r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3*r+3" >>dagdesc # 20 heads
286 $ echo "@b *r+3" >>dagdesc # one more head
287 $ hg debugbuilddag <dagdesc
288 reading DAG from stdin
289
290 $ hg heads -t --template . | wc -c
291 261
292
293 $ hg clone -b a . a
294 adding changesets
295 adding manifests
296 adding file changes
297 added 1340 changesets with 0 changes to 0 files (+259 heads)
298 updating to branch a
299 0 files updated, 0 files merged, 0 files removed, 0 files unresolved
300 $ hg clone -b b . b
301 adding changesets
302 adding manifests
303 adding file changes
304 added 304 changesets with 0 changes to 0 files
305 updating to branch b
306 0 files updated, 0 files merged, 0 files removed, 0 files unresolved
307
308 $ hg -R a debugdiscovery b --debug --verbose
309 comparing with b
310 query 1; heads
311 searching for changes
312 taking quick initial sample
313 searching: 2 queries
314 query 2; still undecided: 1080, sample size is: 260
315 sampling from both directions
316 searching: 3 queries
317 query 3; still undecided: 820, sample size is: 260
318 sampling from both directions
319 searching: 4 queries
320 query 4; still undecided: 560, sample size is: 260
321 sampling from both directions
322 searching: 5 queries
323 query 5; still undecided: 300, sample size is: 200
324 5 total queries
325 common heads: 3ee37d65064a
326
General Comments 0
You need to be logged in to leave comments. Login now