From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Fri, 11 Jul 2008 15:36:10 GMT
Subject: Re: [PATCH] cherry: cache patch-ids to avoid repeating work
Message-ID: <alpine.DEB.1.00.0807111635400.8950@racer>
In-Reply-To: <7f9d599f0807110758y6c4ea7bepd726daf4fe5f074c@mail.gmail.com>

Hi,

On Fri, 11 Jul 2008, Geoffrey Irving wrote:

> On Thu, Jul 10, 2008 at 11:54 PM, Junio C Hamano <gitster@pobox.com> wrote:
> > "Geoffrey Irving" <irving@naml.us> writes:
> >
> >>>> 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.
> >>>
> >>> I have to admit that you lost me there.  AFAIR the patch-id cache is a
> >>> simple commit->patch_id store, right?  Then there should be no way to get
> >>> an infinite loop.
> >>
> >> If every entry is nonnull, find_helper loops forever.
> >
> > Isn't it sufficient to make this part check the condition as well?
> >
> > +       if (cache->count >= cache->size)
> > +       {
> > +               warning("%s is corrupt: count %"PRIu32" >= size %"PRIu32,
> > +                       filename, cache->count, cache->size);
> > +               goto empty;
> > +       }
> >
> > At runtime you keep the invariants that hashtable always has at most 3/4
> > full and whoever wrote the file you are reading must have honored that as
> > well, or there is something fishy going on.
> 
> Good point.  There's no reason not to check the 3/4 condition.  It isn't 
> sufficient to avoid the infinite loop, though, since we don't verify 
> that count is accurate.

Why so complicated?  I mean, you can count in that "infinite" loop 
yourself, no?

Ciao,
Dscho