linux-kernel - Re: [PATCH v3 03/15] lockdep: Refactor lookup_chain

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20160920020012.GJ2279@X58A-UD3R>
Date:   Tue, 20 Sep 2016 11:00:12 +0900
From:   Byungchul Park <byungchul.park@....com>
To:     Nilay Vaish <nilayvaish@...il.com>
Cc:     peterz@...radead.org, mingo@...nel.org, tglx@...utronix.de,
        walken@...gle.com, boqun.feng@...il.com, kirill@...temov.name,
        Linux Kernel list <linux-kernel@...r.kernel.org>,
        linux-mm@...ck.org, iamjoonsoo.kim@....com,
        akpm@...ux-foundation.org, npiggin@...il.com
Subject: Re: [PATCH v3 03/15] lockdep: Refactor lookup_chain_cache()

On Mon, Sep 19, 2016 at 11:36:25AM -0500, Nilay Vaish wrote:
> On 18 September 2016 at 22:05, Byungchul Park <byungchul.park@....com> wrote:
> > On Thu, Sep 15, 2016 at 10:33:46AM -0500, Nilay Vaish wrote:
> >> On 13 September 2016 at 04:45, Byungchul Park <byungchul.park@....com> wrote:
> >> > @@ -2215,6 +2178,75 @@ cache_hit:
> >> >         return 1;
> >> >  }
> >> >
> >> > +/*
> >> > + * Look up a dependency chain.
> >> > + */
> >> > +static inline struct lock_chain *lookup_chain_cache(u64 chain_key)
> >> > +{
> >> > +       struct hlist_head *hash_head = chainhashentry(chain_key);
> >> > +       struct lock_chain *chain;
> >> > +
> >> > +       /*
> >> > +        * We can walk it lock-free, because entries only get added
> >> > +        * to the hash:
> >> > +        */
> >> > +       hlist_for_each_entry_rcu(chain, hash_head, entry) {
> >> > +               if (chain->chain_key == chain_key) {
> >> > +                       debug_atomic_inc(chain_lookup_hits);
> >> > +                       return chain;
> >> > +               }
> >> > +       }
> >> > +       return NULL;
> >> > +}
> >>
> >> Byungchul,  do you think we should increment chain_lookup_misses
> >> before returning NULL from the above function?
> >
> > Hello,
> >
> > No, I don't think so.
> > It will be done in add_chain_cache().
> >
> 
> I think you are assuming that a call to lookup will always be followed
> by add.  I thought the point of breaking the original function into
> two was that each of the functions can be used individually, without
> the other being called.  This means we would not increment the number

Right.

But, we have to remind that counting for cache miss can happen twice if
it's handled in lookup_chain_cache(), because chain_lookup_misses() is
called twice every lookup. One is 'lockless access' for fast path, the
other is 'lock-protected access' for guarranting real miss.

So only when the miss is indentified under lock-protected,
chain_lookup_misses has to be counted. Current chain_lookup_misses means
that "cache miss happened and was _added_ into cache", semantically.
Thus I think it's not bad to handle it in add().

> of misses when only lookup() gets called, but not add().  Or we would

lookup() might be called locklessly for fast path. It would be useful, but
it guarrantees nothing but cache bit. So we cannot count miss in lookup().
Furthermore, we have to assume add() is called when cache miss.

> increment the number of misses when only add() is called and not
> lookup().

Actually add() will not be called without calling lookup(). Anyway, I can
see what you're concerning.. Is there any alterative which is better?

> 
> It really seems odd to me that hits get incremented in lookup and misses don't.
> 
> --
> Nilay