| // Copyright (C) 2011 The Android Open Source Project |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| package com.google.gerrit.server.git; |
| |
| import com.google.common.annotations.VisibleForTesting; |
| import com.google.common.base.MoreObjects; |
| import com.google.common.collect.ImmutableSet; |
| import com.google.common.collect.Maps; |
| import com.google.common.flogger.FluentLogger; |
| import com.google.gerrit.entities.Project; |
| import com.google.gerrit.entities.RefNames; |
| import com.google.gerrit.server.cache.proto.Cache.TagSetHolderProto.TagSetProto; |
| import com.google.gerrit.server.cache.proto.Cache.TagSetHolderProto.TagSetProto.CachedRefProto; |
| import com.google.gerrit.server.cache.proto.Cache.TagSetHolderProto.TagSetProto.TagProto; |
| import com.google.gerrit.server.cache.serialize.ObjectIdConverter; |
| import com.google.protobuf.ByteString; |
| import java.io.IOException; |
| import java.util.BitSet; |
| import java.util.HashMap; |
| import java.util.Map; |
| import java.util.concurrent.atomic.AtomicReference; |
| import org.eclipse.jgit.errors.IncorrectObjectTypeException; |
| import org.eclipse.jgit.lib.AnyObjectId; |
| import org.eclipse.jgit.lib.Constants; |
| import org.eclipse.jgit.lib.ObjectId; |
| import org.eclipse.jgit.lib.ObjectIdOwnerMap; |
| import org.eclipse.jgit.lib.Ref; |
| import org.eclipse.jgit.lib.RefDatabase; |
| import org.eclipse.jgit.lib.Repository; |
| import org.eclipse.jgit.revwalk.RevCommit; |
| import org.eclipse.jgit.revwalk.RevSort; |
| import org.eclipse.jgit.revwalk.RevWalk; |
| |
| /** |
| * Builds a set of tags, and tracks which tags are reachable from which non-tag, non-special refs. |
| * An instance is constructed from a snapshot of the ref database. TagSets can be incrementally |
| * updated to newer states of the RefDatabase using the refresh method. The updateFastForward method |
| * can do partial updates based on individual refs moving forward. |
| * |
| * <p>This set is used to determine which tags should be advertised when only a subset of refs is |
| * visible to a user. |
| * |
| * <p>TagSets can be serialized for use in a persisted TagCache |
| */ |
| class TagSet { |
| private static final FluentLogger logger = FluentLogger.forEnclosingClass(); |
| private static final ImmutableSet<String> SKIPPABLE_REF_PREFIXES = |
| ImmutableSet.of( |
| RefNames.REFS_CHANGES, |
| RefNames.REFS_CACHE_AUTOMERGE, |
| RefNames.REFS_DRAFT_COMMENTS, |
| RefNames.REFS_STARRED_CHANGES); |
| |
| private final Project.NameKey projectName; |
| |
| /** |
| * refName => ref. CachedRef is a ref that has an integer identity, used for indexing into |
| * BitSets. |
| */ |
| private final Map<String, CachedRef> refs; |
| |
| /** ObjectId-pointed-to-by-tag => Tag */ |
| private final ObjectIdOwnerMap<Tag> tags; |
| |
| TagSet(Project.NameKey projectName) { |
| this(projectName, new HashMap<>(), new ObjectIdOwnerMap<>()); |
| } |
| |
| TagSet(Project.NameKey projectName, HashMap<String, CachedRef> refs, ObjectIdOwnerMap<Tag> tags) { |
| this.projectName = projectName; |
| this.refs = refs; |
| this.tags = tags; |
| } |
| |
| Project.NameKey getProjectName() { |
| return projectName; |
| } |
| |
| Tag lookupTag(AnyObjectId id) { |
| return tags.get(id); |
| } |
| |
| // Test methods have obtuse names in addition to annotations, since they expose mutable state |
| // which would be easy to corrupt. |
| @VisibleForTesting |
| Map<String, CachedRef> getRefsForTesting() { |
| return refs; |
| } |
| |
| @VisibleForTesting |
| ObjectIdOwnerMap<Tag> getTagsForTesting() { |
| return tags; |
| } |
| |
| /** Record a fast-forward update of the given ref. This is called from multiple threads. */ |
| boolean updateFastForward(String refName, ObjectId oldValue, ObjectId newValue) { |
| // this looks fishy: refs is not a thread-safe data structure, but it is mutated in build() and |
| // rebuild(). TagSetHolder prohibits concurrent writes through the buildLock mutex, but it does |
| // not prohibit concurrent read/write. |
| CachedRef ref = refs.get(refName); |
| if (ref != null) { |
| // compareAndSet works on reference equality, but this operation |
| // wants to use object equality. Switch out oldValue with cur so the |
| // compareAndSet will function correctly for this operation. |
| ObjectId cur = ref.get(); |
| if (cur.equals(oldValue)) { |
| return ref.compareAndSet(cur, newValue); |
| } |
| } |
| return false; |
| } |
| |
| void prepare(TagMatcher m) { |
| @SuppressWarnings("resource") |
| RevWalk rw = null; |
| try { |
| for (Ref currentRef : m.include) { |
| if (currentRef.isSymbolic()) { |
| continue; |
| } |
| if (currentRef.getObjectId() == null) { |
| continue; |
| } |
| |
| CachedRef savedRef = refs.get(currentRef.getName()); |
| if (savedRef == null) { |
| // If the reference isn't known to the set, return null |
| // and force the caller to rebuild the set in a new copy. |
| m.newRefs.add(currentRef); |
| continue; |
| } |
| |
| // The reference has not been moved. It can be used as-is. |
| ObjectId savedObjectId = savedRef.get(); |
| if (currentRef.getObjectId().equals(savedObjectId)) { |
| m.mask.set(savedRef.flag); |
| continue; |
| } |
| |
| // Check on-the-fly to see if the branch still reaches the tag. |
| // This is very likely for a branch that fast-forwarded. |
| try { |
| if (rw == null) { |
| rw = new RevWalk(m.db); |
| rw.setRetainBody(false); |
| } |
| |
| RevCommit savedCommit = rw.parseCommit(savedObjectId); |
| RevCommit currentCommit = rw.parseCommit(currentRef.getObjectId()); |
| if (rw.isMergedInto(savedCommit, currentCommit)) { |
| // Fast-forward. Safely update the reference in-place. |
| savedRef.compareAndSet(savedObjectId, currentRef.getObjectId()); |
| m.mask.set(savedRef.flag); |
| continue; |
| } |
| |
| // The branch rewound. Walk the list of commits removed from |
| // the reference. If any matches to a tag, this has to be removed. |
| boolean err = false; |
| rw.reset(); |
| rw.markStart(savedCommit); |
| rw.markUninteresting(currentCommit); |
| rw.sort(RevSort.TOPO, true); |
| RevCommit c; |
| while ((c = rw.next()) != null) { |
| Tag tag = tags.get(c); |
| if (tag != null && tag.refFlags.get(savedRef.flag)) { |
| m.lostRefs.add(new TagMatcher.LostRef(tag, savedRef.flag)); |
| err = true; |
| } |
| } |
| if (!err) { |
| // All of the tags are still reachable. Update in-place. |
| savedRef.compareAndSet(savedObjectId, currentRef.getObjectId()); |
| m.mask.set(savedRef.flag); |
| } |
| |
| } catch (IOException err) { |
| // Defer a cache update until later. No conclusion can be made |
| // based on an exception reading from the repository storage. |
| logger.atWarning().withCause(err).log("Error checking tags of %s", projectName); |
| } |
| } |
| } finally { |
| if (rw != null) { |
| rw.close(); |
| } |
| } |
| } |
| |
| void build(Repository git, TagSet old, TagMatcher m) { |
| if (old != null && m != null && refresh(old, m)) { |
| return; |
| } |
| |
| try (TagWalk rw = new TagWalk(git)) { |
| rw.setRetainBody(false); |
| for (Ref ref : |
| git.getRefDatabase() |
| .getRefsByPrefixWithExclusions(RefDatabase.ALL, SKIPPABLE_REF_PREFIXES)) { |
| if (skip(ref)) { |
| continue; |
| |
| } else if (isTag(ref)) { |
| // For a tag, remember where it points to. |
| try { |
| addTag(rw, git.getRefDatabase().peel(ref)); |
| } catch (IOException e) { |
| addTag(rw, ref); |
| } |
| |
| } else { |
| // New reference to include in the set. |
| addRef(rw, ref); |
| } |
| } |
| |
| // Traverse the complete history. Copy any flags from a commit to |
| // all of its ancestors. This automatically updates any Tag object |
| // as the TagCommit and the stored Tag object share the same |
| // underlying bit set. |
| TagCommit c; |
| while ((c = (TagCommit) rw.next()) != null) { |
| BitSet mine = c.refFlags; |
| int pCnt = c.getParentCount(); |
| for (int pIdx = 0; pIdx < pCnt; pIdx++) { |
| ((TagCommit) c.getParent(pIdx)).refFlags.or(mine); |
| } |
| } |
| } catch (IOException e) { |
| logger.atWarning().withCause(e).log("Error building tags for repository %s", projectName); |
| } |
| } |
| |
| static TagSet fromProto(TagSetProto proto) { |
| ObjectIdConverter idConverter = ObjectIdConverter.create(); |
| |
| HashMap<String, CachedRef> refs = Maps.newHashMapWithExpectedSize(proto.getRefCount()); |
| proto |
| .getRefMap() |
| .forEach( |
| (n, cr) -> |
| refs.put(n, new CachedRef(cr.getFlag(), idConverter.fromByteString(cr.getId())))); |
| ObjectIdOwnerMap<Tag> tags = new ObjectIdOwnerMap<>(); |
| proto |
| .getTagList() |
| .forEach( |
| t -> |
| tags.add( |
| new Tag( |
| idConverter.fromByteString(t.getId()), |
| BitSet.valueOf(t.getFlags().asReadOnlyByteBuffer())))); |
| return new TagSet(Project.nameKey(proto.getProjectName()), refs, tags); |
| } |
| |
| TagSetProto toProto() { |
| ObjectIdConverter idConverter = ObjectIdConverter.create(); |
| TagSetProto.Builder b = TagSetProto.newBuilder().setProjectName(projectName.get()); |
| refs.forEach( |
| (n, cr) -> |
| b.putRef( |
| n, |
| CachedRefProto.newBuilder() |
| .setId(idConverter.toByteString(cr.get())) |
| .setFlag(cr.flag) |
| .build())); |
| tags.forEach( |
| t -> |
| b.addTag( |
| TagProto.newBuilder() |
| .setId(idConverter.toByteString(t)) |
| .setFlags(ByteString.copyFrom(t.refFlags.toByteArray())) |
| .build())); |
| return b.build(); |
| } |
| |
| private boolean refresh(TagSet old, TagMatcher m) { |
| if (m.newRefs.isEmpty()) { |
| // No new references is a simple update. Copy from the old set. |
| copy(old, m); |
| return true; |
| } |
| |
| // Only permit a refresh if all new references start from the tip of |
| // an existing references. This happens some of the time within a |
| // Gerrit Code Review server, perhaps about 50% of new references. |
| // Since a complete rebuild is so costly, try this approach first. |
| |
| Map<ObjectId, Integer> byObj = new HashMap<>(); |
| for (CachedRef r : old.refs.values()) { |
| ObjectId id = r.get(); |
| if (!byObj.containsKey(id)) { |
| byObj.put(id, r.flag); |
| } |
| } |
| |
| for (Ref newRef : m.newRefs) { |
| ObjectId id = newRef.getObjectId(); |
| if (id == null || refs.containsKey(newRef.getName())) { |
| continue; |
| } else if (!byObj.containsKey(id)) { |
| return false; |
| } |
| } |
| |
| copy(old, m); |
| |
| for (Ref newRef : m.newRefs) { |
| ObjectId id = newRef.getObjectId(); |
| if (id == null || refs.containsKey(newRef.getName())) { |
| continue; |
| } |
| |
| int srcFlag = byObj.get(id); |
| int newFlag = refs.size(); |
| refs.put(newRef.getName(), new CachedRef(newRef, newFlag)); |
| |
| for (Tag tag : tags) { |
| if (tag.refFlags.get(srcFlag)) { |
| tag.refFlags.set(newFlag); |
| } |
| } |
| } |
| |
| return true; |
| } |
| |
| private void copy(TagSet old, TagMatcher m) { |
| refs.putAll(old.refs); |
| |
| for (Tag srcTag : old.tags) { |
| BitSet mine = new BitSet(); |
| mine.or(srcTag.refFlags); |
| tags.add(new Tag(srcTag, mine)); |
| } |
| |
| for (TagMatcher.LostRef lost : m.lostRefs) { |
| Tag mine = tags.get(lost.tag); |
| if (mine != null) { |
| mine.refFlags.clear(lost.flag); |
| } |
| } |
| } |
| |
| private void addTag(TagWalk rw, Ref ref) { |
| ObjectId id = ref.getPeeledObjectId(); |
| if (id == null) { |
| id = ref.getObjectId(); |
| } |
| |
| if (!tags.contains(id)) { |
| BitSet flags; |
| try { |
| flags = ((TagCommit) rw.parseCommit(id)).refFlags; |
| } catch (IncorrectObjectTypeException notCommit) { |
| flags = new BitSet(); |
| } catch (IOException e) { |
| logger.atWarning().withCause(e).log("Error on %s of %s", ref.getName(), projectName); |
| flags = new BitSet(); |
| } |
| tags.add(new Tag(id, flags)); |
| } |
| } |
| |
| private void addRef(TagWalk rw, Ref ref) { |
| try { |
| TagCommit commit = (TagCommit) rw.parseCommit(ref.getObjectId()); |
| rw.markStart(commit); |
| |
| int flag = refs.size(); |
| commit.refFlags.set(flag); |
| refs.put(ref.getName(), new CachedRef(ref, flag)); |
| } catch (IncorrectObjectTypeException notCommit) { |
| // No need to spam the logs. |
| // Quite many refs will point to non-commits. |
| // For instance, refs from refs/cache-automerge |
| // will often end up here. |
| } catch (IOException e) { |
| logger.atWarning().withCause(e).log("Error on %s of %s", ref.getName(), projectName); |
| } |
| } |
| |
| static boolean skip(Ref ref) { |
| return ref.isSymbolic() |
| || ref.getObjectId() == null |
| || SKIPPABLE_REF_PREFIXES.stream().anyMatch(p -> ref.getName().startsWith(p)); |
| } |
| |
| private static boolean isTag(Ref ref) { |
| return ref.getName().startsWith(Constants.R_TAGS); |
| } |
| |
| @Override |
| public String toString() { |
| return MoreObjects.toStringHelper(this) |
| .add("projectName", projectName) |
| .add("refs", refs) |
| .add("tags", tags) |
| .toString(); |
| } |
| |
| static final class Tag extends ObjectIdOwnerMap.Entry { |
| |
| // a RefCache.flag => isVisible map. This reference is aliased to the |
| // bitset in TagCommit.refFlags. |
| @VisibleForTesting final BitSet refFlags; |
| |
| Tag(AnyObjectId id, BitSet flags) { |
| super(id); |
| this.refFlags = flags; |
| } |
| |
| boolean has(BitSet mask) { |
| return refFlags.intersects(mask); |
| } |
| |
| @Override |
| public String toString() { |
| return MoreObjects.toStringHelper(this).addValue(name()).add("refFlags", refFlags).toString(); |
| } |
| } |
| /** A ref along with its index into BitSet. */ |
| @VisibleForTesting |
| static final class CachedRef extends AtomicReference<ObjectId> { |
| private static final long serialVersionUID = 1L; |
| |
| /** unique identifier for this ref within the TagSet. */ |
| final int flag; |
| |
| CachedRef(Ref ref, int flag) { |
| this(flag, ref.getObjectId()); |
| } |
| |
| CachedRef(int flag, ObjectId id) { |
| this.flag = flag; |
| set(id); |
| } |
| |
| @Override |
| public String toString() { |
| ObjectId id = get(); |
| return MoreObjects.toStringHelper(this) |
| .addValue(id != null ? id.name() : "null") |
| .add("flag", flag) |
| .toString(); |
| } |
| } |
| |
| private static final class TagWalk extends RevWalk { |
| TagWalk(Repository git) { |
| super(git); |
| } |
| |
| @Override |
| protected TagCommit createCommit(AnyObjectId id) { |
| return new TagCommit(id); |
| } |
| } |
| |
| // TODO(hanwen): this would be better named as CommitWithReachability, as it also holds non-tags. |
| private static final class TagCommit extends RevCommit { |
| /** CachedRef.flag => isVisible, indicating if this commit is reachable from the ref. */ |
| final BitSet refFlags; |
| |
| TagCommit(AnyObjectId id) { |
| super(id); |
| refFlags = new BitSet(); |
| } |
| } |
| } |