• Al Viro's avatar
    percpu: store offsets instead of lengths in ->map[] · 723ad1d9
    Al Viro authored
    Current code keeps +-length for each area in chunk->map[].  It has
    several unpleasant consequences:
    	* even if we know that first 50 areas are all in use, allocation
    still needs to go through all those areas just to sum their sizes, just
    to get the offset of free one.
    	* freeing needs to find the array entry refering to the area
    in question; again, the need to sum the sizes until we reach the offset
    we are interested in.  Note that offsets are monotonous, so simple
    binary search would do here.
    
    	New data representation: array of <offset,in-use flag> pairs.
    Each pair is represented by one int - we use offset|1 for <offset, in use>
    and offset for <offset, free> (we make sure that all offsets are even).
    In the end we put a sentry entry - <total size, in use>.  The first
    entry is <0, flag>; it would be possible to store together the flag
    for Nth area and offset for N+1st, but that leads to much hairier code.
    
    In other words, where the old variant would have
    	4, -8, -4, 4, -12, 100
    (4 bytes free, 8 in use, 4 in use, 4 free, 12 in use, 100 free) we store
    	<0,0>, <4,1>, <12,1>, <16,0>, <20,1>, <32,0>, <132,1>
    i.e.
    	0, 5, 13, 16, 21, 32, 133
    
    This commit switches to new data representation and takes care of a couple
    of low-hanging fruits in free_pcpu_area() - one is the switch to binary
    search, another is not doing two memmove() when one would do.  Speeding
    the alloc side up (by keeping track of how many areas in the beginning are
    known to be all in use) also becomes possible - that'll be done in the next
    commit.
    Signed-off-by: default avatarAl Viro <viro@zeniv.linux.org.uk>
    Signed-off-by: default avatarTejun Heo <tj@kernel.org>
    723ad1d9
percpu.c 56.4 KB