• Jan Kara's avatar
    lib/radix-tree.c: make radix_tree_node_alloc() work correctly within interrupt · 5e4c0d97
    Jan Kara authored
    With users of radix_tree_preload() run from interrupt (block/blk-ioc.c is
    one such possible user), the following race can happen:
    
    radix_tree_preload()
    ...
    radix_tree_insert()
      radix_tree_node_alloc()
        if (rtp->nr) {
          ret = rtp->nodes[rtp->nr - 1];
    <interrupt>
    ...
    radix_tree_preload()
    ...
    radix_tree_insert()
      radix_tree_node_alloc()
        if (rtp->nr) {
          ret = rtp->nodes[rtp->nr - 1];
    
    And we give out one radix tree node twice.  That clearly results in radix
    tree corruption with different results (usually OOPS) depending on which
    two users of radix tree race.
    
    We fix the problem by making radix_tree_node_alloc() always allocate fresh
    radix tree nodes when in interrupt.  Using preloading when in interrupt
    doesn't make sense since all the allocations have to be atomic anyway and
    we cannot steal nodes from process-context users because some users rely
    on radix_tree_insert() succeeding after radix_tree_preload().
    in_interrupt() check is somewhat ugly but we cannot simply key off passed
    gfp_mask as that is acquired from root_gfp_mask() and thus the same for
    all preload users.
    
    Another part of the fix is to avoid node preallocation in
    radix_tree_preload() when passed gfp_mask doesn't allow waiting.  Again,
    preallocation in such case doesn't make sense and when preallocation would
    happen in interrupt we could possibly leak some allocated nodes.  However,
    some users of radix_tree_preload() require following radix_tree_insert()
    to succeed.  To avoid unexpected effects for these users,
    radix_tree_preload() only warns if passed gfp mask doesn't allow waiting
    and we provide a new function radix_tree_maybe_preload() for those users
    which get different gfp mask from different call sites and which are
    prepared to handle radix_tree_insert() failure.
    Signed-off-by: default avatarJan Kara <jack@suse.cz>
    Cc: Jens Axboe <jaxboe@fusionio.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    5e4c0d97
radix-tree.c 40 KB