• Tejun Heo's avatar
    idr: fix top layer handling · 326cf0f0
    Tejun Heo authored
    Most functions in idr fail to deal with the high bits when the idr
    tree grows to the maximum height.
    
    * idr_get_empty_slot() stops growing idr tree once the depth reaches
      MAX_IDR_LEVEL - 1, which is one depth shallower than necessary to
      cover the whole range.  The function doesn't even notice that it
      didn't grow the tree enough and ends up allocating the wrong ID
      given sufficiently high @starting_id.
    
      For example, on 64 bit, if the starting id is 0x7fffff01,
      idr_get_empty_slot() will grow the tree 5 layer deep, which only
      covers the 30 bits and then proceed to allocate as if the bit 30
      wasn't specified.  It ends up allocating 0x3fffff01 without the bit
      30 but still returns 0x7fffff01.
    
    * __idr_remove_all() will not remove anything if the tree is fully
      grown.
    
    * idr_find() can't find anything if the tree is fully grown.
    
    * idr_for_each() and idr_get_next() can't iterate anything if the tree
      is fully grown.
    
    Fix it by introducing idr_max() which returns the maximum possible ID
    given the depth of tree and replacing the id limit checks in all
    affected places.
    
    As the idr_layer pointer array pa[] needs to be 1 larger than the
    maximum depth, enlarge pa[] arrays by one.
    
    While this plugs the discovered issues, the whole code base is
    horrible and in desparate need of rewrite.  It's fragile like hell,
    Signed-off-by: default avatarTejun Heo <tj@kernel.org>
    Cc: Rusty Russell <rusty@rustcorp.com.au>
    Cc: <stable@vger.kernel.org>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    326cf0f0
idr.c 28.1 KB