fsck.gfs2: Add new function to check dir hash tables
It's very important that fsck.gfs2 checks for a valid directory hash
table before operating further on the directory. Before this patch,
we were doing some incomplete testing, after we had already operated
on the directory, with function check_num_ptrs. This patch replaces
that scheme with a new one that preemptively checks the hash table
with a new function called check_hash_tbl.
We've got to make sure the hash table is sane. Each leaf needs to
be counted a proper power of 2. We can't just have 3 pointers to a leaf.
The number of pointers must correspond to the proper leaf depth, and they
must all fall on power-of-two boundaries. For example, suppose we have
directory that's had one of its middle leaf blocks split several times.
The split history might look something like this:
leaf
split lindex length depth pointers leaf split
----- ------ ------ ----- -------- -------------
0: 0x00 0x100 0 00 - ff <--split to 1:
1: 0x00 0x80 1 00 - 7f <--split to 2:
0x80 0x80 1 80 - ff
2: 0x00 0x40 2 00 - 3f <--split to 3:
0x40 0x40 2 40 - 7f
0x80 0x80 1 80 - ff
3: 0x00 0x20 3 00 - 1f
0x20 0x20 3 20 - 3f <--split to 4
0x40 0x40 2 40 - 7f
0x80 0x80 1 80 - ff
4: 0x00 0x20 3 00 - 1f
0x20 0x10 4 20 - 2f
0x30 0x10 4 30 - 3f <--split to 5
0x40 0x40 2 40 - 7f
0x80 0x80 1 80 - ff
5: 0x00 0x20 3 00 - 1f
0x20 0x10 4 20 - 2f
0x30 0x8 5 30 - 37 <--split to 6
0x38 0x8 5 38 - 3f
0x40 0x40 2 40 - 7f
0x80 0x80 1 80 - ff
6: 0x00 0x20 3 00 - 1f
0x20 0x10 4 20 - 2f
0x30 0x4 6 30 - 33
0x34 0x4 6 34 - 37
0x38 0x8 5 38 - 3f
0x40 0x40 2 40 - 7f
0x80 0x80 1 80 - ff
You can see from this example that it's impossible for a leaf block to have
a lf_depth of 5 and lindex 0x34. As shown in "5:" above, a leaf depth of 5
can only fall at offset 0x30 or 0x38. If it somehow falls elsewhere, say
0x34, the proper depth should be 6, and there should only be 4 pointers,
as per split "6:" above. The leaf block pointers all need to fall properly
on these boundaries, otherwise the kernel code's calculations will land it
on the wrong leaf block while it's searching, and the result will be files
you can see with ls, but can't open, delete or use them.
rhbz#902920