Line data Source code
1 : // Copyright (C) 2011 The Android Open Source Project
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 :
15 : package com.google.gerrit.server.git;
16 :
17 : import com.google.common.annotations.VisibleForTesting;
18 : import com.google.common.base.MoreObjects;
19 : import com.google.common.collect.ImmutableSet;
20 : import com.google.common.collect.Maps;
21 : import com.google.common.flogger.FluentLogger;
22 : import com.google.gerrit.entities.Project;
23 : import com.google.gerrit.entities.RefNames;
24 : import com.google.gerrit.server.cache.proto.Cache.TagSetHolderProto.TagSetProto;
25 : import com.google.gerrit.server.cache.proto.Cache.TagSetHolderProto.TagSetProto.CachedRefProto;
26 : import com.google.gerrit.server.cache.proto.Cache.TagSetHolderProto.TagSetProto.TagProto;
27 : import com.google.gerrit.server.cache.serialize.ObjectIdConverter;
28 : import com.google.protobuf.ByteString;
29 : import java.io.IOException;
30 : import java.util.BitSet;
31 : import java.util.HashMap;
32 : import java.util.Map;
33 : import java.util.concurrent.atomic.AtomicReference;
34 : import org.eclipse.jgit.errors.IncorrectObjectTypeException;
35 : import org.eclipse.jgit.lib.AnyObjectId;
36 : import org.eclipse.jgit.lib.Constants;
37 : import org.eclipse.jgit.lib.ObjectId;
38 : import org.eclipse.jgit.lib.ObjectIdOwnerMap;
39 : import org.eclipse.jgit.lib.Ref;
40 : import org.eclipse.jgit.lib.RefDatabase;
41 : import org.eclipse.jgit.lib.Repository;
42 : import org.eclipse.jgit.revwalk.RevCommit;
43 : import org.eclipse.jgit.revwalk.RevSort;
44 : import org.eclipse.jgit.revwalk.RevWalk;
45 :
46 : /**
47 : * Builds a set of tags, and tracks which tags are reachable from which non-tag, non-special refs.
48 : * An instance is constructed from a snapshot of the ref database. TagSets can be incrementally
49 : * updated to newer states of the RefDatabase using the refresh method. The updateFastForward method
50 : * can do partial updates based on individual refs moving forward.
51 : *
52 : * <p>This set is used to determine which tags should be advertised when only a subset of refs is
53 : * visible to a user.
54 : *
55 : * <p>TagSets can be serialized for use in a persisted TagCache
56 : */
57 : class TagSet {
58 10 : private static final FluentLogger logger = FluentLogger.forEnclosingClass();
59 10 : private static final ImmutableSet<String> SKIPPABLE_REF_PREFIXES =
60 10 : ImmutableSet.of(
61 : RefNames.REFS_CHANGES,
62 : RefNames.REFS_CACHE_AUTOMERGE,
63 : RefNames.REFS_DRAFT_COMMENTS,
64 : RefNames.REFS_STARRED_CHANGES);
65 :
66 : private final Project.NameKey projectName;
67 :
68 : /**
69 : * refName => ref. CachedRef is a ref that has an integer identity, used for indexing into
70 : * BitSets.
71 : */
72 : private final Map<String, CachedRef> refs;
73 :
74 : /** ObjectId-pointed-to-by-tag => Tag */
75 : private final ObjectIdOwnerMap<Tag> tags;
76 :
77 : TagSet(Project.NameKey projectName) {
78 10 : this(projectName, new HashMap<>(), new ObjectIdOwnerMap<>());
79 10 : }
80 :
81 10 : TagSet(Project.NameKey projectName, HashMap<String, CachedRef> refs, ObjectIdOwnerMap<Tag> tags) {
82 10 : this.projectName = projectName;
83 10 : this.refs = refs;
84 10 : this.tags = tags;
85 10 : }
86 :
87 : Project.NameKey getProjectName() {
88 1 : return projectName;
89 : }
90 :
91 : Tag lookupTag(AnyObjectId id) {
92 9 : return tags.get(id);
93 : }
94 :
95 : // Test methods have obtuse names in addition to annotations, since they expose mutable state
96 : // which would be easy to corrupt.
97 : @VisibleForTesting
98 : Map<String, CachedRef> getRefsForTesting() {
99 1 : return refs;
100 : }
101 :
102 : @VisibleForTesting
103 : ObjectIdOwnerMap<Tag> getTagsForTesting() {
104 1 : return tags;
105 : }
106 :
107 : /** Record a fast-forward update of the given ref. This is called from multiple threads. */
108 : boolean updateFastForward(String refName, ObjectId oldValue, ObjectId newValue) {
109 : // this looks fishy: refs is not a thread-safe data structure, but it is mutated in build() and
110 : // rebuild(). TagSetHolder prohibits concurrent writes through the buildLock mutex, but it does
111 : // not prohibit concurrent read/write.
112 5 : CachedRef ref = refs.get(refName);
113 5 : if (ref != null) {
114 : // compareAndSet works on reference equality, but this operation
115 : // wants to use object equality. Switch out oldValue with cur so the
116 : // compareAndSet will function correctly for this operation.
117 5 : ObjectId cur = ref.get();
118 5 : if (cur.equals(oldValue)) {
119 5 : return ref.compareAndSet(cur, newValue);
120 : }
121 : }
122 3 : return false;
123 : }
124 :
125 : void prepare(TagMatcher m) {
126 : @SuppressWarnings("resource")
127 9 : RevWalk rw = null;
128 : try {
129 9 : for (Ref currentRef : m.include) {
130 9 : if (currentRef.isSymbolic()) {
131 0 : continue;
132 : }
133 9 : if (currentRef.getObjectId() == null) {
134 0 : continue;
135 : }
136 :
137 9 : CachedRef savedRef = refs.get(currentRef.getName());
138 9 : if (savedRef == null) {
139 : // If the reference isn't known to the set, return null
140 : // and force the caller to rebuild the set in a new copy.
141 1 : m.newRefs.add(currentRef);
142 1 : continue;
143 : }
144 :
145 : // The reference has not been moved. It can be used as-is.
146 9 : ObjectId savedObjectId = savedRef.get();
147 9 : if (currentRef.getObjectId().equals(savedObjectId)) {
148 9 : m.mask.set(savedRef.flag);
149 9 : continue;
150 : }
151 :
152 : // Check on-the-fly to see if the branch still reaches the tag.
153 : // This is very likely for a branch that fast-forwarded.
154 : try {
155 1 : if (rw == null) {
156 1 : rw = new RevWalk(m.db);
157 1 : rw.setRetainBody(false);
158 : }
159 :
160 1 : RevCommit savedCommit = rw.parseCommit(savedObjectId);
161 1 : RevCommit currentCommit = rw.parseCommit(currentRef.getObjectId());
162 1 : if (rw.isMergedInto(savedCommit, currentCommit)) {
163 : // Fast-forward. Safely update the reference in-place.
164 0 : savedRef.compareAndSet(savedObjectId, currentRef.getObjectId());
165 0 : m.mask.set(savedRef.flag);
166 0 : continue;
167 : }
168 :
169 : // The branch rewound. Walk the list of commits removed from
170 : // the reference. If any matches to a tag, this has to be removed.
171 1 : boolean err = false;
172 1 : rw.reset();
173 1 : rw.markStart(savedCommit);
174 1 : rw.markUninteresting(currentCommit);
175 1 : rw.sort(RevSort.TOPO, true);
176 : RevCommit c;
177 1 : while ((c = rw.next()) != null) {
178 1 : Tag tag = tags.get(c);
179 1 : if (tag != null && tag.refFlags.get(savedRef.flag)) {
180 1 : m.lostRefs.add(new TagMatcher.LostRef(tag, savedRef.flag));
181 1 : err = true;
182 : }
183 1 : }
184 1 : if (!err) {
185 : // All of the tags are still reachable. Update in-place.
186 1 : savedRef.compareAndSet(savedObjectId, currentRef.getObjectId());
187 1 : m.mask.set(savedRef.flag);
188 : }
189 :
190 0 : } catch (IOException err) {
191 : // Defer a cache update until later. No conclusion can be made
192 : // based on an exception reading from the repository storage.
193 0 : logger.atWarning().withCause(err).log("Error checking tags of %s", projectName);
194 1 : }
195 1 : }
196 : } finally {
197 9 : if (rw != null) {
198 1 : rw.close();
199 : }
200 : }
201 9 : }
202 :
203 : void build(Repository git, TagSet old, TagMatcher m) {
204 9 : if (old != null && m != null && refresh(old, m)) {
205 1 : return;
206 : }
207 :
208 9 : try (TagWalk rw = new TagWalk(git)) {
209 9 : rw.setRetainBody(false);
210 : for (Ref ref :
211 9 : git.getRefDatabase()
212 9 : .getRefsByPrefixWithExclusions(RefDatabase.ALL, SKIPPABLE_REF_PREFIXES)) {
213 9 : if (skip(ref)) {
214 9 : continue;
215 :
216 9 : } else if (isTag(ref)) {
217 : // For a tag, remember where it points to.
218 : try {
219 9 : addTag(rw, git.getRefDatabase().peel(ref));
220 0 : } catch (IOException e) {
221 0 : addTag(rw, ref);
222 9 : }
223 :
224 : } else {
225 : // New reference to include in the set.
226 9 : addRef(rw, ref);
227 : }
228 9 : }
229 :
230 : // Traverse the complete history. Copy any flags from a commit to
231 : // all of its ancestors. This automatically updates any Tag object
232 : // as the TagCommit and the stored Tag object share the same
233 : // underlying bit set.
234 : TagCommit c;
235 9 : while ((c = (TagCommit) rw.next()) != null) {
236 9 : BitSet mine = c.refFlags;
237 9 : int pCnt = c.getParentCount();
238 9 : for (int pIdx = 0; pIdx < pCnt; pIdx++) {
239 9 : ((TagCommit) c.getParent(pIdx)).refFlags.or(mine);
240 : }
241 9 : }
242 0 : } catch (IOException e) {
243 0 : logger.atWarning().withCause(e).log("Error building tags for repository %s", projectName);
244 9 : }
245 9 : }
246 :
247 : static TagSet fromProto(TagSetProto proto) {
248 1 : ObjectIdConverter idConverter = ObjectIdConverter.create();
249 :
250 1 : HashMap<String, CachedRef> refs = Maps.newHashMapWithExpectedSize(proto.getRefCount());
251 1 : proto
252 1 : .getRefMap()
253 1 : .forEach(
254 : (n, cr) ->
255 1 : refs.put(n, new CachedRef(cr.getFlag(), idConverter.fromByteString(cr.getId()))));
256 1 : ObjectIdOwnerMap<Tag> tags = new ObjectIdOwnerMap<>();
257 1 : proto
258 1 : .getTagList()
259 1 : .forEach(
260 : t ->
261 1 : tags.add(
262 : new Tag(
263 1 : idConverter.fromByteString(t.getId()),
264 1 : BitSet.valueOf(t.getFlags().asReadOnlyByteBuffer()))));
265 1 : return new TagSet(Project.nameKey(proto.getProjectName()), refs, tags);
266 : }
267 :
268 : TagSetProto toProto() {
269 1 : ObjectIdConverter idConverter = ObjectIdConverter.create();
270 1 : TagSetProto.Builder b = TagSetProto.newBuilder().setProjectName(projectName.get());
271 1 : refs.forEach(
272 : (n, cr) ->
273 1 : b.putRef(
274 : n,
275 1 : CachedRefProto.newBuilder()
276 1 : .setId(idConverter.toByteString(cr.get()))
277 1 : .setFlag(cr.flag)
278 1 : .build()));
279 1 : tags.forEach(
280 : t ->
281 1 : b.addTag(
282 1 : TagProto.newBuilder()
283 1 : .setId(idConverter.toByteString(t))
284 1 : .setFlags(ByteString.copyFrom(t.refFlags.toByteArray()))
285 1 : .build()));
286 1 : return b.build();
287 : }
288 :
289 : private boolean refresh(TagSet old, TagMatcher m) {
290 1 : if (m.newRefs.isEmpty()) {
291 : // No new references is a simple update. Copy from the old set.
292 1 : copy(old, m);
293 1 : return true;
294 : }
295 :
296 : // Only permit a refresh if all new references start from the tip of
297 : // an existing references. This happens some of the time within a
298 : // Gerrit Code Review server, perhaps about 50% of new references.
299 : // Since a complete rebuild is so costly, try this approach first.
300 :
301 1 : Map<ObjectId, Integer> byObj = new HashMap<>();
302 1 : for (CachedRef r : old.refs.values()) {
303 1 : ObjectId id = r.get();
304 1 : if (!byObj.containsKey(id)) {
305 1 : byObj.put(id, r.flag);
306 : }
307 1 : }
308 :
309 1 : for (Ref newRef : m.newRefs) {
310 1 : ObjectId id = newRef.getObjectId();
311 1 : if (id == null || refs.containsKey(newRef.getName())) {
312 0 : continue;
313 1 : } else if (!byObj.containsKey(id)) {
314 1 : return false;
315 : }
316 0 : }
317 :
318 0 : copy(old, m);
319 :
320 0 : for (Ref newRef : m.newRefs) {
321 0 : ObjectId id = newRef.getObjectId();
322 0 : if (id == null || refs.containsKey(newRef.getName())) {
323 0 : continue;
324 : }
325 :
326 0 : int srcFlag = byObj.get(id);
327 0 : int newFlag = refs.size();
328 0 : refs.put(newRef.getName(), new CachedRef(newRef, newFlag));
329 :
330 0 : for (Tag tag : tags) {
331 0 : if (tag.refFlags.get(srcFlag)) {
332 0 : tag.refFlags.set(newFlag);
333 : }
334 0 : }
335 0 : }
336 :
337 0 : return true;
338 : }
339 :
340 : private void copy(TagSet old, TagMatcher m) {
341 1 : refs.putAll(old.refs);
342 :
343 1 : for (Tag srcTag : old.tags) {
344 1 : BitSet mine = new BitSet();
345 1 : mine.or(srcTag.refFlags);
346 1 : tags.add(new Tag(srcTag, mine));
347 1 : }
348 :
349 1 : for (TagMatcher.LostRef lost : m.lostRefs) {
350 1 : Tag mine = tags.get(lost.tag);
351 1 : if (mine != null) {
352 1 : mine.refFlags.clear(lost.flag);
353 : }
354 1 : }
355 1 : }
356 :
357 : private void addTag(TagWalk rw, Ref ref) {
358 9 : ObjectId id = ref.getPeeledObjectId();
359 9 : if (id == null) {
360 6 : id = ref.getObjectId();
361 : }
362 :
363 9 : if (!tags.contains(id)) {
364 : BitSet flags;
365 : try {
366 9 : flags = ((TagCommit) rw.parseCommit(id)).refFlags;
367 1 : } catch (IncorrectObjectTypeException notCommit) {
368 1 : flags = new BitSet();
369 0 : } catch (IOException e) {
370 0 : logger.atWarning().withCause(e).log("Error on %s of %s", ref.getName(), projectName);
371 0 : flags = new BitSet();
372 9 : }
373 9 : tags.add(new Tag(id, flags));
374 : }
375 9 : }
376 :
377 : private void addRef(TagWalk rw, Ref ref) {
378 : try {
379 9 : TagCommit commit = (TagCommit) rw.parseCommit(ref.getObjectId());
380 9 : rw.markStart(commit);
381 :
382 9 : int flag = refs.size();
383 9 : commit.refFlags.set(flag);
384 9 : refs.put(ref.getName(), new CachedRef(ref, flag));
385 0 : } catch (IncorrectObjectTypeException notCommit) {
386 : // No need to spam the logs.
387 : // Quite many refs will point to non-commits.
388 : // For instance, refs from refs/cache-automerge
389 : // will often end up here.
390 0 : } catch (IOException e) {
391 0 : logger.atWarning().withCause(e).log("Error on %s of %s", ref.getName(), projectName);
392 9 : }
393 9 : }
394 :
395 : static boolean skip(Ref ref) {
396 9 : return ref.isSymbolic()
397 9 : || ref.getObjectId() == null
398 9 : || SKIPPABLE_REF_PREFIXES.stream().anyMatch(p -> ref.getName().startsWith(p));
399 : }
400 :
401 : private static boolean isTag(Ref ref) {
402 9 : return ref.getName().startsWith(Constants.R_TAGS);
403 : }
404 :
405 : @Override
406 : public String toString() {
407 0 : return MoreObjects.toStringHelper(this)
408 0 : .add("projectName", projectName)
409 0 : .add("refs", refs)
410 0 : .add("tags", tags)
411 0 : .toString();
412 : }
413 :
414 : static final class Tag extends ObjectIdOwnerMap.Entry {
415 :
416 : // a RefCache.flag => isVisible map. This reference is aliased to the
417 : // bitset in TagCommit.refFlags.
418 : @VisibleForTesting final BitSet refFlags;
419 :
420 : Tag(AnyObjectId id, BitSet flags) {
421 10 : super(id);
422 10 : this.refFlags = flags;
423 10 : }
424 :
425 : boolean has(BitSet mask) {
426 9 : return refFlags.intersects(mask);
427 : }
428 :
429 : @Override
430 : public String toString() {
431 0 : return MoreObjects.toStringHelper(this).addValue(name()).add("refFlags", refFlags).toString();
432 : }
433 : }
434 : /** A ref along with its index into BitSet. */
435 : @VisibleForTesting
436 : static final class CachedRef extends AtomicReference<ObjectId> {
437 : private static final long serialVersionUID = 1L;
438 :
439 : /** unique identifier for this ref within the TagSet. */
440 : final int flag;
441 :
442 : CachedRef(Ref ref, int flag) {
443 9 : this(flag, ref.getObjectId());
444 9 : }
445 :
446 10 : CachedRef(int flag, ObjectId id) {
447 10 : this.flag = flag;
448 10 : set(id);
449 10 : }
450 :
451 : @Override
452 : public String toString() {
453 0 : ObjectId id = get();
454 0 : return MoreObjects.toStringHelper(this)
455 0 : .addValue(id != null ? id.name() : "null")
456 0 : .add("flag", flag)
457 0 : .toString();
458 : }
459 : }
460 :
461 : private static final class TagWalk extends RevWalk {
462 : TagWalk(Repository git) {
463 9 : super(git);
464 9 : }
465 :
466 : @Override
467 : protected TagCommit createCommit(AnyObjectId id) {
468 9 : return new TagCommit(id);
469 : }
470 : }
471 :
472 : // TODO(hanwen): this would be better named as CommitWithReachability, as it also holds non-tags.
473 : private static final class TagCommit extends RevCommit {
474 : /** CachedRef.flag => isVisible, indicating if this commit is reachable from the ref. */
475 : final BitSet refFlags;
476 :
477 : TagCommit(AnyObjectId id) {
478 9 : super(id);
479 9 : refFlags = new BitSet();
480 9 : }
481 : }
482 : }
|
