• Tejun Heo's avatar
    idr: fix a subtle bug in idr_get_next() · 6cdae741
    Tejun Heo authored
    The iteration logic of idr_get_next() is borrowed mostly verbatim from
    idr_for_each().  It walks down the tree looking for the slot matching
    the current ID.  If the matching slot is not found, the ID is
    incremented by the distance of single slot at the given level and
    repeats.
    
    The implementation assumes that during the whole iteration id is aligned
    to the layer boundaries of the level closest to the leaf, which is true
    for all iterations starting from zero or an existing element and thus is
    fine for idr_for_each().
    
    However, idr_get_next() may be given any point and if the starting id
    hits in the middle of a non-existent layer, increment to the next layer
    will end up skipping the same offset into it.  For example, an IDR with
    IDs filled between [64, 127] would look like the following.
    
              [  0  64 ... ]
           /----/   |
           |        |
          NULL    [ 64 ... 127 ]
    
    If idr_get_next() is called with 63 as the starting point, it will try
    to follow down the pointer from 0.  As it is NULL, it will then try to
    proceed to the next slot in the same level by adding the slot distance
    at that level which is 64 - making the next try 127.  It goes around the
    loop and finds and returns 127 skipping [64, 126].
    
    Note that this bug also triggers in idr_for_each_entry() loop which
    deletes during iteration as deletions can make layers go away leaving
    the iteration with unaligned ID into missing layers.
    
    Fix it by ensuring proceeding to the next slot doesn't carry over the
    unaligned offset - ie.  use round_up(id + 1, slot_distance) instead of
    id += slot_distance.
    Signed-off-by: default avatarTejun Heo <tj@kernel.org>
    Reported-by: default avatarDavid Teigland <teigland@redhat.com>
    Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
    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>
    6cdae741
idr.c 23.8 KB