Gitweb: http://git.kernel.org/linus/2dcb22b346be7b7b7e630a8970d69cf3f1111ec1
Commit: 2dcb22b346be7b7b7e630a8970d69cf3f1111ec1
Parent: 79a6cdeb7eb54e3d2d4bb9fc5f0231b057882a87
Author: Imre Deak <imre.deak@nokia.com>
AuthorDate: Wed May 26 14:43:38 2010 -0700
Committer: Linus Torvalds <torvalds@linux-foundation.org>
CommitDate: Thu May 27 09:12:48 2010 -0700
idr: fix backtrack logic in idr_remove_all
Currently idr_remove_all will fail with a use after free error if
idr::layers is bigger than 2, which on 32 bit systems corresponds to items
more than 1024. This is due to stepping back too many levels during
backtracking. For simplicity let's assume that IDR_BITS=1 -> we have 2
nodes at each level below the root node and each leaf node stores two IDs.
(In reality for 32 bit systems IDR_BITS=5, with 32 nodes at each sub-root
level and 32 IDs in each leaf node). The sequence of freeing the nodes at
the moment is as follows:
layer
1 -> a(7)
2 -> b(3) c(5)
3 -> d(1) e(2) f(4) g(6)
Until step 4 things go fine, but then node c is freed, whereas node g
should be freed first. Since node c contains the pointer to node g we'll
have a use after free error at step 6.
How many levels we step back after visiting the leaf nodes is currently
determined by the msb of the id we are currently visiting:
Step
1. node d with IDs 0,1 is freed, current ID is advanced to 2.
msb of the current ID bit 1. This means we need to step back
1 level to node b and take the next sibling, node e.
2-3. node e with IDs 2,3 is freed, current ID is 4, msb is bit 2.
This means we need to step back 2 levels to node a, freeing
node b on the way.
4-5. node f with IDs 4,5 is freed, current ID is 6, msb is still
bit ...
