DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=date:from:to:cc:subject:message-id:references:mime-version
         :content-type:content-disposition:in-reply-to:user-agent;
        b=G1dc8MN8W7Qch7KYheu9IVvVTxHBmwBr4zFC0awUiY9K2i5SlZp/AcPY/yjG1BOvm/
         tiQWZeVJjfSbkAXurUSExoTxFe99dypO1sWpZeoTfKrd4mx/n7D1ycGPepiNblMvgMP+
         mFdoGp48blgFZpMSOP0xO15a0AXttfJrupGyM=
Date: Mon, 14 Dec 2009 14:30:17 +0100
From: Frederic Weisbecker <fweisbec@gmail.com>
To: Hitoshi Mitake <mitake@dcl.info.waseda.ac.jp>
Cc: mingo@elte.hu, linux-kernel@vger.kernel.org,
       Peter Zijlstra <a.p.zijlstra@chello.nl>,
       Paul Mackerras <paulus@samba.org>
Subject: Re: [PATCH][RFC] perf lock: Distribute numerical IDs for each lock
	instances
Message-ID: <20091214133014.GL5168@nowhere>
References: <1260691344-4724-1-git-send-email-mitake@dcl.info.waseda.ac.jp>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <1260691344-4724-1-git-send-email-mitake@dcl.info.waseda.ac.jp>
User-Agent: Mutt/1.5.18 (2008-05-17)
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 3817
Lines: 98

On Sun, Dec 13, 2009 at 05:02:24PM +0900, Hitoshi Mitake wrote:
> This patch implements distributing numerical IDs for each lock instances.
> 
> Principle:
> At first, kernel holds lock_idtable. It is an double dimension array
> for each lock class with LOCK_IDTABLE_LENGTH of struct lock_instance_stat.
> 
> struct lock_instance_stat can have many things for lock stats or something,
> but it isn't important point.
> 
> The important point is that index of lock_idtable is used as numerical ID.
> And this patch makes lockdep_map have this ID. So searching stats data for
> lock instances are O(1), very fast.
> 
> And the second important point is that when numerical IDs are distributed
> for each lock instances.
> This patch makes lockdep_map have a new member, do_register. This is a pointer of function.
> When initialized the lock instances (for example: SPIN_DEP_MAP_INIT in spinlock_types.h),
> this member is initialized with
> register_lockdep_id() in kernel/lockdep.c .
> This function receives the adress of lockdep_map (it's owner),
> and searches lock_idtable, then if unused ID (unused index) is found,
> set the owner (spinlock_t, rwlock_t, etc. obtained with container_of) of lockdep_map
> to lock_idtable's unit determined in above.
> 
> When this do_register() called? lock_acquire() calls it.
> And once initialize completed, nop_register_lockdep_id() will be
> assigned to do_register(). It is a nop function.
> 
> I believe this patch makes implementation of perf lock more easy
> and precision, and may also help lock people.
> 
> Benefit:
>  * Low overhead
>  * int type ID is easy to deal with
> 
> Demerit:
>  * What should kernel do when lock_idtable is exhausted?
>    (But I think entire number of lock instances are not so many,
>     and predicting upper limit of it is not hard)
>  * instances before calling lock_acquire() with cannot be identified
>  * end of instances cannot be determined
> 
> This patch is a proof of concept version.
> There are some rest todos, especially the statement in lock_acquire():
> 	if (lock->do_register)
> this must be removed in future, this proves that
> there's some lockdep_map I cannot initializing correctly.
> For example, rcu_lock_map in kernel/rcupdate.c .
> 
> And I implemented debugfs entry, lockdep_idtable
> for dumping ID and name of instances like this,
> % cat  lockdep_idtable
>         --- spinlock ---
> 0: logbuf_lock
> 1: (console_sem).lock
> 2: clockevents_lock
> 3: set_atomicity_lock
> 4: pgd_lock
> 5: init_mm.page_table_lock
> 6: index_init_lock
> 7: ioapic_lock
> 8: x86_mce_decoder_chain.lock
> 9: pcpu_lock
> 10: perf_resource_lock
> ...
> 
> But it is can be merged according to checkpatch.pl,
> if you like it, could you merge it into perf/lock branch, Ingo?
> And I really want to hear comments from people! :)
> 
> Signed-off-by: Hitoshi Mitake <mitake@dcl.info.waseda.ac.jp>
> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
> Cc: Paul Mackerras <paulus@samba.org>
> Cc: Frederic Weisbecker <fweisbec@gmail.com>


So if I understand well, this maps each lockdep_map
into a unique index, right?

Then the goal is to be able to identify each lock instances from
perf lock using a simple array of indexes.

But adding the lockdep_map address from lock events would provide
you a unique id for each lock instances already. Sure it would
be addresses instead of indexes but I think a hashlist should do
the trick already. I'm not sure we need to add more complexity
inside in-kernel lock debugging while we already have the keys
to make it scale well in userspace.

Thanks.

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/