From: Stefan Sperling <stsp@stsp.name>
Subject: fix pack index cache element rotation
To: gameoftrees@openbsd.org
Date: Sun, 10 Oct 2021 21:41:02 +0200

Keep most often used pack index files near the front of the
pack index array (in the second diff chunk of the patch below).
The previous code was swapping the former best entry with the
newly selected best entry. This means the former best entry
can end up in any position of the array. The cache ends up
being a shuffle instead of an LRU cache.

Instead, elements should be rotated such that the former best
entry becomes the second-best entry, by moving it to the second
position.

Also, (in the first diff chunk of my patch) do not bother inserting
at the front when we have just opened a new pack index file. At this
point we do not even know whether the pack index file we have opened
has the object we are looking for.

ok?

diff a3774042d47a891f7f7994479c470b945aa686c6 e05ab166ec9565f0db792112d06bcb3cd1dac85f
blob - 17697cc62656dd554d17df6ee00a548fde19f6e9
blob + f216e0867a7738383ffc5b34e5923ad33c16f541
--- lib/repository.c
+++ lib/repository.c
@@ -928,19 +928,13 @@ cache_packidx(struct got_repository *repo, struct got_
 		}
 	}
 	if (i == repo->pack_cache_size) {
-		err = got_packidx_close(repo->packidx_cache[i - 1]);
+		i = repo->pack_cache_size - 1;
+		err = got_packidx_close(repo->packidx_cache[i]);
 		if (err)
 			return err;
 	}
 
-	/*
-	 * Insert the new pack index at the front so it will
-	 * be searched first in the future.
-	 */
-	memmove(&repo->packidx_cache[1], &repo->packidx_cache[0],
-	    sizeof(repo->packidx_cache) -
-	    sizeof(repo->packidx_cache[0]));
-	repo->packidx_cache[0] = packidx;
+	repo->packidx_cache[i] = packidx;
 
 	return NULL;
 }
@@ -984,10 +978,10 @@ got_repo_search_packidx(struct got_packidx **packidx, 
 			 * searching a wrong pack index can be expensive.
 			 */
 			if (i > 0) {
-				struct got_packidx *p;
-				p = repo->packidx_cache[0];
+				memmove(&repo->packidx_cache[1],
+				    &repo->packidx_cache[0],
+				    i * sizeof(repo->packidx_cache[0]));
 				repo->packidx_cache[0] = *packidx;
-				repo->packidx_cache[i] = p;
 			}
 			return NULL;
 		}