I think this algorithm should work:

1) walk /dev/block/${dev}/slaves recursively (e.g. lvm-over- luks-
over-lvm- over-md, first-level slaves won't work), collect all
whole-disk devices;
2) sort this list by device numbers (to avoid AB/BA deadlocks), remove
duplicates;
3) acquire all locks consequently.

There are some unavoidable flaws (e.g. if someone alters structure while fsck
is running), and some things could be improved, but it should work in
most cases (and if it fails, it is just no worse than current behavior).

I've tested with LVM and LUKS-over-LVM on (debian's) 3.16 kernel, it seems
works as expected.

What is not covered: /dev/loop* (and I have no plans for it).

Comments? NACKs?