Re: [RESEND PATCH 01/11] kernel:lockdep:print the shortestdependency chain if finding a circle

[Ingo Molnar]

* Ming Lei <tom.leiming@xxxxxxxxx> 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@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/