Add cache for tag advertisements

When a client asks the server for access to a Git repository, the
server has to compute a list of tags to advertise to the client.
It is an expensive computation to determine which tags are reachable
from the branches the client has READ permission on.  For large
repositories with many tags the computation can take a considerable
amount of time, bordering on several seconds per connection. To make
the general case more efficient, introduce a cache called "git_tags".

On a trivial usage of the Linux kernel repository, the average
running time of the VisibleRefFilter when caches were hot was
7195.68 ms.  With this commit, it is a mere 5.07 milliseconds
on a hot cache.  A reduction of 99% of the running time.

The caches performs incremental updates under certain situations,
making common updates relatively painless for waiting clients:

  * Branch fast-forward / change submission:

    When a branch fast-forwards to a new commit, or a change is
    submitted to a branch, all prior tags that are reachable from
    that branch are still reachable.  The cache updates itself
    in-place to this new commit, after performing a fast-forward
    check.  Although a fast-forward check requires walking commit
    history, most fast-forwards are only a few commits ahead of the
    prior position, making the check fast enough to do on demand
    for a client.  Once the cache has been updated, other clients
    will not need to perform the check.

  * Short branch rewinds:

    If a branch rewinds to a prior version (or cuts to a different
    history), and in doing so does not eliminate any tags, the
    cache is updated in-place in real-time.  Since the change did
    not impact any tags, the cache is still valid and can continue
    to be reused.

  * Branch deletion:

    If a branch is deleted, the cache is not updated.  The deleted
    branch is simply ignored in the cache.  If a great number of
    branches are deleted and the cache is wasting memory, site
    administrators should flush the "git_tags" cache and force a
    rebuild.  However, since a branch costs just 1 bit per tag, plus
    the size of the branch name string, it would require deleting
    75,000 branches before its even worth considering flushing the
    cache manually... as 75,000 branches is about 5 MB of storage.

  * Branch creation at another branch tip:

    If a new branch is created and points to the same commit as
    an existing branch, the cache is updated by cloning itself
    and adding the new branch for all tags reachable from the
    source branch.  To keep things thread-safe in memory with
    minimal locking, this type of update requires making a full
    copy of the cache's data and is therefore more expensive than
    the prior update techniques, but is significantly cheaper than
    a full rebuild.

There are some nasty corner cases the cache does not try to
handle. For these we just suffer through a full rebuild:

  * Branch creation not at another branch tip:

    Since the newly created branch does not exactly match another
    branch, the project history must be scanned and computed to
    determine which tags are reachable from which branches. There
    is no optimization available for creating a new branch at
    an existing tag, so those cases also force a rebuild.

  * New tag:

    Since the tag position is not exactly known, which branches can
    reach it is also not known. The project history is scanned to
    rebuild the cache.

Unlike the prior version of VisibleRefFilter, a rebuild of the
cache only walks the history of the project once. This makes a
rebuild slightly faster (5s now vs. 7s before).

Cache updates occur automatically as a result of observed changes in
the Git repository references. Doing these updates live just before
sending the advertisement to a client ensure the cache's reachability
data accurately represents the advertisement the client will receive.
It also ensures any updates made directly to the repository (without
Gerrit being involved) is still properly reflected in the result.

We try to optimize updates for two common cases: change submission
and direct push fast-forwards.  Both attempt to update the cache
immediately after the reference has been updated. This saves clients
from needing to perform the fast-forward check themselves, as the
change submission or receive code already performed the check and
has the results on hand.

There is still room for future improvement:

  Adding a new tag to the cache could be computed more quickly by
  copying the old cache, and doing a walk from all branch heads up
  to the new tag, but stopping at the new tag.  This does not always
  work well when there are disconnected branches in the repository,
  as those unrelated branches will scan to the roots before
  terminating, making the update nearly the cost of full rebuild.

  Adding a new branch not at the exact same position as another
  branch could be computed more quickly by scanning all commits
  in the new branch (to see if tags were added), and all commits
  in existing branches (to see if tags should be excluded), and
  stopping at the merge base of the two sets.  Any tags that are not
  excluded from the other branches but are reachable from the other
  branches should also be reachable from the new branch. However
  this is a tricky concept, as one must consider unrelated branches,
  so this operation may need to be performed once per unique set
  of branches that a tag can reach.  Since this may require more
  than one history traversal, and if the branches are unrelated,
  a traversal all the way to the root, its nearly as expensive as
  the full rebuild option. Since its a lot more complex than a full
  rebuild, I am punting on this and may never implement it.

Change-Id: I519a39ade2742de02003d9dedd17a8edca5c4923

12 files changed, 796 insertions, 133 deletions

diff --git a/Documentation/config-gerrit.txt b/Documentation/config-gerrit.txt
index 226ffbed1b..decbc728f1 100644
--- a/Documentation/config-gerrit.txt
+++ b/Documentation/config-gerrit.txt
@@ -377,6 +377,18 @@ Keeping entries for 90 days gives sufficient time for most changes
 to be submitted or abandoned before their relevant difference items
 expire out.
 
+cache `"git_tags"`::
++
+If branch or reference level READ access controls are used, this
+cache tracks which tags are reachable from the branch tips of a
+repository.  Gerrit uses this information to determine the set
+of tags that a client may access, derived from which tags are
+part of the history of a visible branch.
++
+The cache is persisted to disk across server restarts as it can
+be expensive to compute (60 or more seconds for a large history
+like the Linux kernel repository).
+
 cache `"groups"`::
 +
 Caches the basic group information from the `account_groups` table,
diff --git a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/ProjectServlet.java b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/ProjectServlet.java
index c4db309813..a071c773ae 100644
--- a/gerrit-httpd/src/main/java/com/google/gerrit/httpd/ProjectServlet.java
+++ b/gerrit-httpd/src/main/java/com/google/gerrit/httpd/ProjectServlet.java
@@ -25,6 +25,7 @@ import com.google.gerrit.server.cache.CacheModule;
 import com.google.gerrit.server.config.CanonicalWebUrl;
 import com.google.gerrit.server.git.GitRepositoryManager;
 import com.google.gerrit.server.git.ReceiveCommits;
+import com.google.gerrit.server.git.TagCache;
 import com.google.gerrit.server.git.TransferConfig;
 import com.google.gerrit.server.git.VisibleRefFilter;
 import com.google.gerrit.server.project.NoSuchProjectException;
@@ -210,11 +211,14 @@ public class ProjectServlet extends GitServlet {
   static class Upload implements UploadPackFactory<HttpServletRequest> {
     private final Provider<ReviewDb> db;
     private final PackConfig packConfig;
+    private final TagCache tagCache;
 
     @Inject
-    Upload(final Provider<ReviewDb> db, final TransferConfig tc) {
+    Upload(final Provider<ReviewDb> db, final TransferConfig tc,
+        final TagCache tagCache) {
       this.db = db;
       this.packConfig = tc.getPackConfig();
+      this.tagCache = tagCache;
     }
 
     @Override
@@ -230,7 +234,7 @@ public class ProjectServlet extends GitServlet {
       UploadPack up = new UploadPack(repo);
       up.setPackConfig(packConfig);
       if (!pc.allRefsAreVisible()) {
-        up.setRefFilter(new VisibleRefFilter(repo, pc, db.get(), true));
+        up.setRefFilter(new VisibleRefFilter(tagCache, repo, pc, db.get(), true));
       }
       return up;
     }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/config/GerritGlobalModule.java b/gerrit-server/src/main/java/com/google/gerrit/server/config/GerritGlobalModule.java
index 5426f346a2..d6cc95d5b8 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/config/GerritGlobalModule.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/config/GerritGlobalModule.java
@@ -49,6 +49,7 @@ import com.google.gerrit.server.git.PushReplication;
 import com.google.gerrit.server.git.ReloadSubmitQueueOp;
 import com.google.gerrit.server.git.ReplicationQueue;
 import com.google.gerrit.server.git.SecureCredentialsProvider;
+import com.google.gerrit.server.git.TagCache;
 import com.google.gerrit.server.git.TransferConfig;
 import com.google.gerrit.server.git.WorkQueue;
 import com.google.gerrit.server.mail.EmailSender;
@@ -154,6 +155,7 @@ public class GerritGlobalModule extends FactoryModule {
     install(GroupIncludeCacheImpl.module());
     install(PatchListCacheImpl.module());
     install(ProjectCacheImpl.module());
+    install(TagCache.module());
     install(new AccessControlModule());
 
     factory(AccountInfoCacheFactory.Factory.class);
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/git/MergeOp.java b/gerrit-server/src/main/java/com/google/gerrit/server/git/MergeOp.java
index b66fcb5932..f29c52ee58 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/git/MergeOp.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/git/MergeOp.java
@@ -156,6 +156,7 @@ public class MergeOp {
 
   private final ChangeHookRunner hooks;
   private final AccountCache accountCache;
+  private final TagCache tagCache;
   private final CreateCodeReviewNotes.Factory codeReviewNotesFactory;
 
   @Inject
@@ -169,6 +170,7 @@ public class MergeOp {
       @GerritPersonIdent final PersonIdent myIdent,
       final MergeQueue mergeQueue, @Assisted final Branch.NameKey branch,
       final ChangeHookRunner hooks, final AccountCache accountCache,
+      final TagCache tagCache,
       final CreateCodeReviewNotes.Factory crnf) {
     repoManager = grm;
     schemaFactory = sf;
@@ -184,6 +186,7 @@ public class MergeOp {
     this.mergeQueue = mergeQueue;
     this.hooks = hooks;
     this.accountCache = accountCache;
+    this.tagCache = tagCache;
     codeReviewNotesFactory = crnf;
 
     this.myIdent = myIdent;
@@ -889,6 +892,12 @@ public class MergeOp {
         switch (branchUpdate.update(rw)) {
           case NEW:
           case FAST_FORWARD:
+            if (branchUpdate.getResult() == RefUpdate.Result.FAST_FORWARD) {
+              tagCache.updateFastForward(destBranch.getParentKey(),
+                  branchUpdate.getName(),
+                  branchUpdate.getOldObjectId(),
+                  mergeTip);
+            }
             replication.scheduleUpdate(destBranch.getParentKey(), branchUpdate
                 .getName());
 
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/git/PushOp.java b/gerrit-server/src/main/java/com/google/gerrit/server/git/PushOp.java
index a24d416d81..b28b83968a 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/git/PushOp.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/git/PushOp.java
@@ -72,6 +72,7 @@ class PushOp implements ProjectRunnable {
   private final PushReplication.ReplicationConfig pool;
   private final RemoteConfig config;
   private final CredentialsProvider credentialsProvider;
+  private final TagCache tagCache;
 
   private final Set<String> delta = new HashSet<String>();
   private final Project.NameKey projectName;
@@ -91,12 +92,14 @@ class PushOp implements ProjectRunnable {
   PushOp(final GitRepositoryManager grm, final SchemaFactory<ReviewDb> s,
       final PushReplication.ReplicationConfig p, final RemoteConfig c,
       final SecureCredentialsProvider.Factory cpFactory,
+      final TagCache tc,
       @Assisted final Project.NameKey d, @Assisted final URIish u) {
     repoManager = grm;
     schema = s;
     pool = p;
     config = c;
     credentialsProvider = cpFactory.create(c.getName());
+    tagCache = tc;
     projectName = d;
     uri = u;
   }
@@ -301,7 +304,7 @@ class PushOp implements ProjectRunnable {
         return Collections.emptyList();
       }
       try {
-        local = new VisibleRefFilter(db, pc, meta, true).filter(local);
+        local = new VisibleRefFilter(tagCache, db, pc, meta, true).filter(local);
       } finally {
         meta.close();
       }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/git/ReceiveCommits.java b/gerrit-server/src/main/java/com/google/gerrit/server/git/ReceiveCommits.java
index 4380ff015f..b0a1e76ec6 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/git/ReceiveCommits.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/git/ReceiveCommits.java
@@ -144,6 +144,7 @@ public class ReceiveCommits implements PreReceiveHook, PostReceiveHook {
   private final String canonicalWebUrl;
   private final PersonIdent gerritIdent;
   private final TrackingFooters trackingFooters;
+  private final TagCache tagCache;
 
   private final ProjectControl projectControl;
   private final Project project;
@@ -175,6 +176,7 @@ public class ReceiveCommits implements PreReceiveHook, PostReceiveHook {
       final ReplicationQueue replication,
       final PatchSetInfoFactory patchSetInfoFactory,
       final ChangeHookRunner hooks,
+      final TagCache tagCache,
       @CanonicalWebUrl @Nullable final String canonicalWebUrl,
       @GerritPersonIdent final PersonIdent gerritIdent,
       final TrackingFooters trackingFooters,
@@ -194,6 +196,7 @@ public class ReceiveCommits implements PreReceiveHook, PostReceiveHook {
     this.canonicalWebUrl = canonicalWebUrl;
     this.gerritIdent = gerritIdent;
     this.trackingFooters = trackingFooters;
+    this.tagCache = tagCache;
 
     this.projectControl = projectControl;
     this.project = projectControl.getProject();
@@ -208,7 +211,7 @@ public class ReceiveCommits implements PreReceiveHook, PostReceiveHook {
 
     if (!projectControl.allRefsAreVisible()) {
       rp.setCheckReferencedObjectsAreReachable(true);
-      rp.setRefFilter(new VisibleRefFilter(repo, projectControl, db, false));
+      rp.setRefFilter(new VisibleRefFilter(tagCache, repo, projectControl, db, false));
     }
     rp.setRefFilter(new ReceiveCommitsRefFilter(rp.getRefFilter()));
 
@@ -362,18 +365,28 @@ public class ReceiveCommits implements PreReceiveHook, PostReceiveHook {
       final Collection<ReceiveCommand> commands) {
     for (final ReceiveCommand c : commands) {
       if (c.getResult() == Result.OK) {
-        if (isHead(c)) {
-          switch (c.getType()) {
-            case CREATE:
+        switch (c.getType()) {
+          case CREATE:
+            if (isHead(c)) {
               autoCloseChanges(c);
-              break;
-            case DELETE:
-              break;
-            case UPDATE:
-            case UPDATE_NONFASTFORWARD:
+            }
+            break;
+
+          case UPDATE: // otherwise known as a fast-forward
+            tagCache.updateFastForward(project.getNameKey(),
+                c.getRefName(),
+                c.getOldId(),
+                c.getNewId());
+            if (isHead(c)) {
               autoCloseChanges(c);
-              break;
-          }
+            }
+            break;
+
+          case UPDATE_NONFASTFORWARD:
+            if (isHead(c)) {
+              autoCloseChanges(c);
+            }
+            break;
         }
 
         if (!c.getRefName().startsWith(NEW_CHANGE)) {
@@ -594,6 +607,7 @@ public class ReceiveCommits implements PreReceiveHook, PostReceiveHook {
     RefControl ctl = projectControl.controlForRef(cmd.getRefName());
     if (ctl.canCreate(rp.getRevWalk(), obj)) {
       validateNewCommits(ctl, cmd);
+
       // Let the core receive process handle it
     } else {
       reject(cmd);
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/git/TagCache.java b/gerrit-server/src/main/java/com/google/gerrit/server/git/TagCache.java
new file mode 100644
index 0000000000..053fda8b89
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/git/TagCache.java
@@ -0,0 +1,160 @@
+// 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;
+
+package com.google.gerrit.server.git;
+
+import com.google.gerrit.reviewdb.Project;
+import com.google.gerrit.server.cache.Cache;
+import com.google.gerrit.server.cache.CacheModule;
+import com.google.inject.Inject;
+import com.google.inject.Module;
+import com.google.inject.Singleton;
+import com.google.inject.TypeLiteral;
+import com.google.inject.name.Named;
+
+import org.eclipse.jgit.lib.ObjectId;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+
+@Singleton
+public class TagCache {
+  private static final String CACHE_NAME = "git_tags";
+
+  public static Module module() {
+    return new CacheModule() {
+      @Override
+      protected void configure() {
+        final TypeLiteral<Cache<EntryKey, EntryVal>> type =
+            new TypeLiteral<Cache<EntryKey, EntryVal>>() {};
+        disk(type, CACHE_NAME);
+        bind(TagCache.class);
+      }
+    };
+  }
+
+  private final Cache<EntryKey, EntryVal> cache;
+  private final Object createLock = new Object();
+
+  @Inject
+  TagCache(@Named(CACHE_NAME) Cache<EntryKey, EntryVal> cache) {
+    this.cache = cache;
+  }
+
+  /**
+   * Advise the cache that a reference fast-forwarded.
+   * <p>
+   * This operation is not necessary, the cache will automatically detect changes
+   * made to references and update itself on demand. However, this method may
+   * allow the cache to update more quickly and reuse the caller's computation of
+   * the fast-forward status of a branch.
+   *
+   * @param name project the branch is contained in.
+   * @param refName the branch name.
+   * @param oldValue the old value, before the fast-forward. The cache
+   *        will only update itself if it is still using this old value.
+   * @param newValue the current value, after the fast-forward.
+   */
+  public void updateFastForward(Project.NameKey name, String refName,
+      ObjectId oldValue, ObjectId newValue) {
+    // Be really paranoid and null check everything. This method should
+    // never fail with an exception. Some of these references can be null
+    // (e.g. not all projects are cached, or the cache is not current).
+    //
+    EntryVal val = cache.get(new EntryKey(name));
+    if (val != null) {
+      TagSetHolder holder = val.holder;
+      if (holder != null) {
+        TagSet tags = holder.getTagSet();
+        if (tags != null) {
+          tags.updateFastForward(refName, oldValue, newValue);
+        }
+      }
+    }
+  }
+
+  TagSetHolder get(Project.NameKey name) {
+    EntryKey key = new EntryKey(name);
+    EntryVal val = cache.get(key);
+    if (val == null) {
+      synchronized (createLock) {
+        val = cache.get(key);
+        if (val == null) {
+          val = new EntryVal();
+          val.holder = new TagSetHolder(name);
+          cache.put(key, val);
+        }
+      }
+    }
+    return val.holder;
+  }
+
+  static class EntryKey implements Serializable {
+    static final long serialVersionUID = 1L;
+
+    private transient String name;
+
+    EntryKey(Project.NameKey name) {
+      this.name = name.get();
+    }
+
+    @Override
+    public int hashCode() {
+      return name.hashCode();
+    }
+
+    @Override
+    public boolean equals(Object o) {
+      if (o instanceof EntryKey) {
+        return name.equals(((EntryKey) o).name);
+      }
+      return false;
+    }
+
+    private void readObject(ObjectInputStream in) throws IOException {
+      name = in.readUTF();
+    }
+
+    private void writeObject(ObjectOutputStream out) throws IOException {
+      out.writeUTF(name);
+    }
+  }
+
+  static class EntryVal implements Serializable {
+    static final long serialVersionUID = EntryKey.serialVersionUID;
+
+    transient TagSetHolder holder;
+
+    private void readObject(ObjectInputStream in) throws IOException,
+        ClassNotFoundException {
+      holder = new TagSetHolder(new Project.NameKey(in.readUTF()));
+      if (in.readBoolean()) {
+        TagSet tags = new TagSet(holder.getProjectName());
+        tags.readObject(in);
+        holder.setTagSet(tags);
+      }
+    }
+
+    private void writeObject(ObjectOutputStream out) throws IOException {
+      TagSet tags = holder.getTagSet();
+      out.writeUTF(holder.getProjectName().get());
+      out.writeBoolean(tags != null);
+      if (tags != null) {
+        tags.writeObject(out);
+      }
+    }
+  }
+}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/git/TagMatcher.java b/gerrit-server/src/main/java/com/google/gerrit/server/git/TagMatcher.java
new file mode 100644
index 0000000000..6cf873d1c2
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/git/TagMatcher.java
@@ -0,0 +1,82 @@
+// 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;
+
+package com.google.gerrit.server.git;
+
+import com.google.gerrit.server.git.TagSet.Tag;
+
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.Ref;
+import org.eclipse.jgit.lib.Repository;
+
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.Collection;
+import java.util.List;
+
+class TagMatcher {
+  final BitSet mask = new BitSet();
+  final List<Ref> newRefs = new ArrayList<Ref>();
+  final List<LostRef> lostRefs = new ArrayList<LostRef>();
+  final TagSetHolder holder;
+  final Repository db;
+  final Collection<Ref> include;
+  TagSet tags;
+  boolean updated;
+  private boolean rebuiltForNewTags;
+
+  TagMatcher(TagSetHolder holder, Repository db, Collection<Ref> include,
+      TagSet tags, boolean updated) {
+    this.holder = holder;
+    this.db = db;
+    this.include = include;
+    this.tags = tags;
+    this.updated = updated;
+  }
+
+  boolean isReachable(Ref tagRef) {
+    tagRef = db.peel(tagRef);
+
+    ObjectId tagObj = tagRef.getPeeledObjectId();
+    if (tagObj == null) {
+      tagObj = tagRef.getObjectId();
+      if (tagObj == null) {
+        return false;
+      }
+    }
+
+    Tag tag = tags.lookupTag(tagObj);
+    if (tag == null) {
+      if (rebuiltForNewTags) {
+        return false;
+      }
+
+      rebuiltForNewTags = true;
+      holder.rebuildForNewTags(this);
+      return isReachable(tagRef);
+    }
+
+    return tag.has(mask);
+  }
+
+  static class LostRef {
+    final Tag tag;
+    final int flag;
+
+    LostRef(Tag tag, int flag) {
+      this.tag = tag;
+      this.flag = flag;
+    }
+  }
+}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/git/TagSet.java b/gerrit-server/src/main/java/com/google/gerrit/server/git/TagSet.java
new file mode 100644
index 0000000000..5adfbd1c89
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/git/TagSet.java
@@ -0,0 +1,382 @@
+// 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;
+
+package com.google.gerrit.server.git;
+
+import static org.eclipse.jgit.lib.ObjectIdSerialization.readNotNull;
+import static org.eclipse.jgit.lib.ObjectIdSerialization.writeNotNull;
+
+import com.google.gerrit.reviewdb.PatchSet;
+import com.google.gerrit.reviewdb.Project;
+
+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.Repository;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.RevSort;
+import org.eclipse.jgit.revwalk.RevWalk;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.util.BitSet;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.concurrent.atomic.AtomicReference;
+
+class TagSet {
+  private static final Logger log = LoggerFactory.getLogger(TagSet.class);
+
+  private final Project.NameKey projectName;
+  private final Map<String, CachedRef> refs;
+  private final ObjectIdOwnerMap<Tag> tags;
+
+  TagSet(Project.NameKey projectName) {
+    this.projectName = projectName;
+    this.refs = new HashMap<String, CachedRef>();
+    this.tags = new ObjectIdOwnerMap<Tag>();
+  }
+
+  Tag lookupTag(AnyObjectId id) {
+    return tags.get(id);
+  }
+
+  void updateFastForward(String refName, ObjectId oldValue,
+      ObjectId newValue) {
+    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)) {
+        ref.compareAndSet(cur, newValue);
+      }
+    }
+  }
+
+  void prepare(TagMatcher m) {
+    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.
+          log.warn("Error checking tags of " + projectName, err);
+        }
+      }
+    } finally {
+      if (rw != null) {
+        rw.release();
+      }
+    }
+  }
+
+  void build(Repository git, TagSet old, TagMatcher m) {
+    if (old != null && m != null && refresh(old, m)) {
+      return;
+    }
+
+    TagWalk rw = new TagWalk(git);
+    rw.setRetainBody(false);
+    try {
+      for (Ref ref : git.getAllRefs().values()) {
+        if (skip(ref)) {
+          continue;
+
+        } else if (isTag(ref)) {
+          // For a tag, remember where it points to.
+          addTag(rw, git.peel(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) {
+      log.warn("Repository " + projectName + " has corruption", e);
+    } finally {
+      rw.release();
+    }
+  }
+
+  void readObject(ObjectInputStream in) throws IOException,
+      ClassNotFoundException {
+    int refCnt = in.readInt();
+    for (int i = 0; i < refCnt; i++) {
+      String name = in.readUTF();
+      int flag = in.readInt();
+      ObjectId id = readNotNull(in);
+      refs.put(name, new CachedRef(flag, id));
+    }
+
+    int tagCnt = in.readInt();
+    for (int i = 0; i < tagCnt; i++) {
+      ObjectId id = readNotNull(in);
+      BitSet flags = (BitSet) in.readObject();
+      tags.add(new Tag(id, flags));
+    }
+  }
+
+  void writeObject(ObjectOutputStream out) throws IOException {
+    out.writeInt(refs.size());
+    for (Map.Entry<String, CachedRef> e : refs.entrySet()) {
+      out.writeUTF(e.getKey());
+      out.writeInt(e.getValue().flag);
+      writeNotNull(out, e.getValue().get());
+    }
+
+    out.writeInt(tags.size());
+    for (Tag tag : tags) {
+      writeNotNull(out, tag);
+      out.writeObject(tag.refFlags);
+    }
+  }
+
+  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<ObjectId, Integer>();
+    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) {
+        log.warn("Error on " + ref.getName() + " of " + projectName, e);
+        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 (IOException e) {
+      log.warn("Error on " + ref.getName() + " of " + projectName, e);
+    }
+  }
+
+  private static boolean skip(Ref ref) {
+    return ref.isSymbolic() || ref.getObjectId() == null
+        || PatchSet.isRef(ref.getName());
+  }
+
+  private static boolean isTag(Ref ref) {
+    return ref.getName().startsWith(Constants.R_TAGS);
+  }
+
+  static final class Tag extends ObjectIdOwnerMap.Entry {
+    private final BitSet refFlags;
+
+    Tag(AnyObjectId id, BitSet flags) {
+      super(id);
+      this.refFlags = flags;
+    }
+
+    boolean has(BitSet mask) {
+      return refFlags.intersects(mask);
+    }
+  }
+
+  private static final class CachedRef extends AtomicReference<ObjectId> {
+    final int flag;
+
+    CachedRef(Ref ref, int flag) {
+      this(flag, ref.getObjectId());
+    }
+
+    CachedRef(int flag, ObjectId id) {
+      this.flag = flag;
+      set(id);
+    }
+  }
+
+  private static final class TagWalk extends RevWalk {
+    TagWalk(Repository git) {
+      super(git);
+    }
+
+    @Override
+    protected TagCommit createCommit(AnyObjectId id) {
+      return new TagCommit(id);
+    }
+  }
+
+  private static final class TagCommit extends RevCommit {
+    final BitSet refFlags;
+
+    TagCommit(AnyObjectId id) {
+      super(id);
+      refFlags = new BitSet();
+    }
+  }
+}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/git/TagSetHolder.java b/gerrit-server/src/main/java/com/google/gerrit/server/git/TagSetHolder.java
new file mode 100644
index 0000000000..c6667c5d40
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/git/TagSetHolder.java
@@ -0,0 +1,94 @@
+// 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;
+
+package com.google.gerrit.server.git;
+
+import com.google.gerrit.reviewdb.Project;
+
+import org.eclipse.jgit.lib.Ref;
+import org.eclipse.jgit.lib.Repository;
+
+import java.util.Collection;
+
+class TagSetHolder {
+  private final Object buildLock = new Object();
+  private final Project.NameKey projectName;
+  private volatile TagSet tags;
+
+  TagSetHolder(Project.NameKey projectName) {
+    this.projectName = projectName;
+  }
+
+  Project.NameKey getProjectName() {
+    return projectName;
+  }
+
+  TagSet getTagSet() {
+    return tags;
+  }
+
+  void setTagSet(TagSet tags) {
+    this.tags = tags;
+  }
+
+  TagMatcher matcher(Repository db, Collection<Ref> include) {
+    TagSet tags = this.tags;
+    if (tags == null) {
+      tags = build(db);
+    }
+
+    TagMatcher m = new TagMatcher(this, db, include, tags, false);
+    tags.prepare(m);
+    if (!m.newRefs.isEmpty() || !m.lostRefs.isEmpty()) {
+      tags = rebuild(db, tags, m);
+
+      m = new TagMatcher(this, db, include, tags, true);
+      tags.prepare(m);
+    }
+    return m;
+  }
+
+  void rebuildForNewTags(TagMatcher m) {
+    m.tags = rebuild(m.db, m.tags, null);
+
+    m.mask.clear();
+    m.newRefs.clear();
+    m.lostRefs.clear();
+    m.tags.prepare(m);
+  }
+
+  private TagSet build(Repository db) {
+    synchronized (buildLock) {
+      TagSet tags = this.tags;
+      if (tags == null) {
+        tags = new TagSet(projectName);
+        tags.build(db, null, null);
+        this.tags = tags;
+      }
+      return tags;
+    }
+  }
+
+  private TagSet rebuild(Repository db, TagSet old, TagMatcher m) {
+    synchronized (buildLock) {
+      TagSet cur = this.tags;
+      if (cur == old) {
+        cur = new TagSet(projectName);
+        cur.build(db, old, m);
+        this.tags = cur;
+      }
+      return cur;
+    }
+  }
+}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/git/VisibleRefFilter.java b/gerrit-server/src/main/java/com/google/gerrit/server/git/VisibleRefFilter.java
index a692fddd77..77a346f43a 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/git/VisibleRefFilter.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/git/VisibleRefFilter.java
@@ -21,22 +21,13 @@ import com.google.gerrit.reviewdb.ReviewDb;
 import com.google.gerrit.server.project.ProjectControl;
 import com.google.gwtorm.client.OrmException;
 
-import org.eclipse.jgit.errors.IncorrectObjectTypeException;
-import org.eclipse.jgit.errors.MissingObjectException;
 import org.eclipse.jgit.lib.Constants;
-import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.Ref;
 import org.eclipse.jgit.lib.Repository;
-import org.eclipse.jgit.revwalk.RevCommit;
-import org.eclipse.jgit.revwalk.RevFlag;
-import org.eclipse.jgit.revwalk.RevObject;
-import org.eclipse.jgit.revwalk.RevTag;
-import org.eclipse.jgit.revwalk.RevWalk;
 import org.eclipse.jgit.transport.RefFilter;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
-import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.HashMap;
@@ -49,15 +40,19 @@ public class VisibleRefFilter implements RefFilter {
   private static final Logger log =
       LoggerFactory.getLogger(VisibleRefFilter.class);
 
+  private final TagCache tagCache;
   private final Repository db;
+  private final Project.NameKey projectName;
   private final ProjectControl projectCtl;
   private final ReviewDb reviewDb;
   private final boolean showChanges;
 
-  public VisibleRefFilter(final Repository db,
+  public VisibleRefFilter(final TagCache tagCache, final Repository db,
       final ProjectControl projectControl, final ReviewDb reviewDb,
       final boolean showChanges) {
+    this.tagCache = tagCache;
     this.db = db;
+    this.projectName = projectControl.getProject().getNameKey();
     this.projectCtl = projectControl;
     this.reviewDb = reviewDb;
     this.showChanges = showChanges;
@@ -80,7 +75,9 @@ public class VisibleRefFilter implements RefFilter {
       } else if (isTag(ref)) {
         // If its a tag, consider it later.
         //
-        deferredTags.add(ref);
+        if (ref.getObjectId() != null) {
+          deferredTags.add(ref);
+        }
 
       } else if (projectCtl.controlForRef(ref.getLeaf().getName()).isVisible()) {
         // Use the leaf to lookup the control data. If the reference is
@@ -95,7 +92,12 @@ public class VisibleRefFilter implements RefFilter {
     // to identify what tags we can actually reach, and what we cannot.
     //
     if (!deferredTags.isEmpty() && !result.isEmpty()) {
-      addVisibleTags(result, deferredTags);
+      TagMatcher tags = tagCache.get(projectName).matcher(db, result.values());
+      for (Ref tag : deferredTags) {
+        if (tags.isReachable(tag)) {
+          result.put(tag.getName(), tag);
+        }
+      }
     }
 
     return result;
@@ -122,112 +124,6 @@ public class VisibleRefFilter implements RefFilter {
     }
   }
 
-  private void addVisibleTags(final Map<String, Ref> result,
-      final List<Ref> tags) {
-    final RevWalk rw = new RevWalk(db);
-    try {
-      final RevFlag VISIBLE = rw.newFlag("VISIBLE");
-      final List<RevCommit> starts;
-
-      rw.carry(VISIBLE);
-      starts = lookupVisibleCommits(result, rw, VISIBLE);
-
-      for (Ref tag : tags) {
-        if (isTagVisible(rw, VISIBLE, starts, tag)) {
-          result.put(tag.getName(), tag);
-        }
-      }
-    } finally {
-      rw.release();
-    }
-  }
-
-  private List<RevCommit> lookupVisibleCommits(final Map<String, Ref> result,
-      final RevWalk rw, final RevFlag VISIBLE) {
-    // Lookup and cache the roots of the graph that we know we can see.
-    //
-    final List<RevCommit> roots = new ArrayList<RevCommit>(result.size());
-    for (Ref ref : result.values()) {
-      try {
-        RevObject c = rw.parseAny(ref.getObjectId());
-        c.add(VISIBLE);
-        if (c instanceof RevCommit) {
-          roots.add((RevCommit) c);
-        } else if (c instanceof RevTag) {
-          roots.add(rw.parseCommit(c));
-        }
-      } catch (IOException e) {
-      }
-    }
-    return roots;
-  }
-
-  private boolean isTagVisible(final RevWalk rw, final RevFlag VISIBLE,
-      final List<RevCommit> starts, Ref tag) {
-    try {
-      final RevObject obj = peelTag(rw, tag);
-      if (obj.has(VISIBLE)) {
-        // If the target is immediately visible, continue on. This case
-        // is quite common as tags are often sorted alphabetically by the
-        // version number, so earlier tags usually compute the data needed
-        // to answer later tags with no additional effort.
-        //
-        return true;
-      }
-
-      if (obj instanceof RevCommit) {
-        // Cast to a commit and traverse the history to determine if
-        // the commit is reachable through one or more references.
-        //
-        final RevCommit c = (RevCommit) obj;
-        walk(rw, VISIBLE, c, starts);
-        return c.has(VISIBLE);
-      }
-
-      return false;
-    } catch (IOException e) {
-      return false;
-    }
-  }
-
-  private RevObject peelTag(final RevWalk rw, final Ref tag)
-      throws MissingObjectException, IOException {
-    // Try to use the peeled object identity, because it may be
-    // able to save us from parsing the tag object itself.
-    //
-    ObjectId target = tag.getPeeledObjectId();
-    if (target == null) {
-      target = tag.getObjectId();
-    }
-    RevObject o = rw.parseAny(target);
-    while (o instanceof RevTag) {
-      o = ((RevTag) o).getObject();
-      rw.parseHeaders(o);
-    }
-    return o;
-  }
-
-  private void walk(final RevWalk rw, final RevFlag VISIBLE,
-      final RevCommit tagged, final List<RevCommit> starts)
-      throws MissingObjectException, IncorrectObjectTypeException, IOException {
-    // Reset the traversal, but keep VISIBLE flags live as they aren't
-    // invalidated by the change in starting points.
-    //
-    rw.resetRetain(VISIBLE);
-    for (RevCommit o : starts) {
-      try {
-        rw.markStart(o);
-      } catch (IOException e) {
-      }
-    }
-
-    // Traverse the history until the tag is found.
-    //
-    rw.markUninteresting(tagged);
-    while (rw.next() != null) {
-    }
-  }
-
   private static boolean isTag(Ref ref) {
     return ref.getLeaf().getName().startsWith(Constants.R_TAGS);
   }
diff --git a/gerrit-sshd/src/main/java/com/google/gerrit/sshd/commands/Upload.java b/gerrit-sshd/src/main/java/com/google/gerrit/sshd/commands/Upload.java
index 95b33f74c1..951568a887 100644
--- a/gerrit-sshd/src/main/java/com/google/gerrit/sshd/commands/Upload.java
+++ b/gerrit-sshd/src/main/java/com/google/gerrit/sshd/commands/Upload.java
@@ -15,6 +15,7 @@
 package com.google.gerrit.sshd.commands;
 
 import com.google.gerrit.reviewdb.ReviewDb;
+import com.google.gerrit.server.git.TagCache;
 import com.google.gerrit.server.git.TransferConfig;
 import com.google.gerrit.server.git.VisibleRefFilter;
 import com.google.gerrit.sshd.AbstractGitCommand;
@@ -34,6 +35,9 @@ final class Upload extends AbstractGitCommand {
   @Inject
   private TransferConfig config;
 
+  @Inject
+  private TagCache tagCache;
+
   @Override
   protected void runImpl() throws IOException, Failure {
     if (!projectControl.canRunUploadPack()) {
@@ -42,7 +46,8 @@ final class Upload extends AbstractGitCommand {
 
     final UploadPack up = new UploadPack(repo);
     if (!projectControl.allRefsAreVisible()) {
-      up.setRefFilter(new VisibleRefFilter(repo, projectControl, db.get(), true));
+      up.setRefFilter(new VisibleRefFilter(tagCache, repo, projectControl,
+          db.get(), true));
     }
     up.setPackConfig(config.getPackConfig());
     up.setTimeout(config.getTimeout());