linux-kernel - Re: [RESEND PATCH 01/11] kernel:lockdep:print the shortest dependency chain if finding a circle

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: <20090713070110.GA28499@elte.hu>
Date:	Mon, 13 Jul 2009 09:01:10 +0200
From:	Ingo Molnar <mingo@...e.hu>
To:	Ming Lei <tom.leiming@...il.com>
Cc:	Frederic Weisbecker <fweisbec@...il.com>, a.p.zijlstra@...llo.nl,
	linux-kernel@...r.kernel.org, akpm@...ux-foundation.org
Subject: Re: [RESEND PATCH 01/11] kernel:lockdep:print the shortest
	dependency chain if finding a circle


* Ming Lei <tom.leiming@...il.com> wrote:

> > If I understand well, lets imagine the following:
> >
> > Task 1 acquires: A B F
> > Task 2 acquires: A B C D E F
> > Task 3 acquires: F B
> >
> > Before your patch, DFS would report the BF - FB wicked 
> > dependency by reporting the Task 2 dependency snapshot, which is 
> > cluttered by the other locks C, D and E (that would be reported 
> > in the dependency chain if I'm not wrong) whereas BFS would be 
> > smarter by finding the shortest snapshot found in Task 3: just F 
> > B.
> >
> > Correct me if I misunderstand this patch.
> 
> You are correct, BFS will always find the shortest circle if there 
> is circle.
> 
> > I suggest you to provide an example along this patch, that would 
> > make it easier to demonstrate its importance.
> 
> No, as you said, the shortest circle is not very important, and it 
> is just a byproduct and we have no reason to reject it.

It's a nice byproduct, beyond the primary advantage of not being a 
stack based recursion check.

I think this patch-set is great, and there's just one more step 
needed to make it round: it would be nice to remove the limitation 
of maximum number of locks held per task. (MAX_LOCK_DEPTH)

The way we could do it is to split out this bit of struct task:

#ifdef CONFIG_LOCKDEP
# define MAX_LOCK_DEPTH 48UL
        u64 curr_chain_key;
        int lockdep_depth;
        unsigned int lockdep_recursion;
        struct held_lock held_locks[MAX_LOCK_DEPTH];
        gfp_t lockdep_reclaim_gfp;
#endif

into a separate 'struct lockdep_state' structure, and allocate it 
dynamically during fork with a initial pre-set size of say 64 locks 
depth. If we hit that limit, we'd double the allocation threshold, 
which would cause a larger structure to be allocated for all newly 
allocated tasks.

( This means that the task that hits this threshold needs to have
  lockdep disabled until it exits - but that's OK. )

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