• Daniel Mentz's avatar
    lib/genalloc.c: start search from start of chunk · 62e931fa
    Daniel Mentz authored
    gen_pool_alloc_algo() iterates over the chunks of a pool trying to find
    a contiguous block of memory that satisfies the allocation request.
    
    The shortcut
    
    	if (size > atomic_read(&chunk->avail))
    		continue;
    
    makes the loop skip over chunks that do not have enough bytes left to
    fulfill the request.  There are two situations, though, where an
    allocation might still fail:
    
    (1) The available memory is not contiguous, i.e.  the request cannot
        be fulfilled due to external fragmentation.
    
    (2) A race condition.  Another thread runs the same code concurrently
        and is quicker to grab the available memory.
    
    In those situations, the loop calls pool->algo() to search the entire
    chunk, and pool->algo() returns some value that is >= end_bit to
    indicate that the search failed.  This return value is then assigned to
    start_bit.  The variables start_bit and end_bit describe the range that
    should be searched, and this range should be reset for every chunk that
    is searched.  Today, the code fails to reset start_bit to 0.  As a
    result, prefixes of subsequent chunks are ignored.  Memory allocations
    might fail even though there is plenty of room left in these prefixes of
    those other chunks.
    
    Fixes: 7f184275 ("lib, Make gen_pool memory allocator lockless")
    Link: http://lkml.kernel.org/r/1477420604-28918-1-git-send-email-danielmentz@google.comSigned-off-by: default avatarDaniel Mentz <danielmentz@google.com>
    Reviewed-by: default avatarMathieu Desnoyers <mathieu.desnoyers@efficios.com>
    Acked-by: default avatarWill Deacon <will.deacon@arm.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    62e931fa
genalloc.c 21.6 KB