From: Geoffrey Irving <irving@naml.us>
Date: Thu, 10 Jul 2008 14:09:14 GMT
Subject: Re: [PATCH] cherry: cache patch-ids to avoid repeating work
Message-ID: <7f9d599f0807100709u778f0ab1y28776d7efb831b61@mail.gmail.com>
In-Reply-To: <7f9d599f0807092034n438f0976pf44d4c9305871087@mail.gmail.com>

On Wed, Jul 9, 2008 at 8:34 PM, Geoffrey Irving <irving@naml.us> wrote:
> Add cached-sha-map.[ch] implementing a persistent hash map from sha1 to
> sha1.  The map is read with mmap, and completely rewritten if any entries
> change.  It would be good to add incremental update to handle the usual case
> where only a few entries change.
>
> This structure is used by patch-ids.c to cache the mapping from commit to
> patch-id into $GIT_DIR/patch-id-cache.  In the one case I've tested so far,
> this speeds up the second invocation of git-cherry by two orders of
> magnitude.  The caching can be disabled by setting cherry.cachepatchids to
> false.
>
> Original code cannibalized from Johannes Schindelin's notes-index structure.
>
> Signed-off-by: Geoffrey Irving <irving@naml.us>
> ---
>
> Note: there are at least two "holes" in this code.  First, it is impossible
> to verify the validity of the entries (this is impossible to fix).  Second,
> it is possible to write a malicious patch-id-cache file that causes git-cherry
> to go into an infinite loop.  Fixing the loop requires either traversing every
> entry on load (bad) or adding a second loop termination condition to
> find_helper.  Since looping forever is better than returning incorrect
> results, I figured fixing the weaker hole would just result in a false sense
> of security.

Oops: avoiding the infinite loop only requires reading expected O(1)
entries on load, so I can fix that if you like.  It would only be all
of them if it actually did detect the infinite loop.

Geoffrey