Skip to content
  • Al Viro's avatar
    Make allocation of anon devices cheaper · c63e09ec
    Al Viro authored
    
    
    Standard trick - add a new variable (start) such that
    for each n < start n is known to be busy.  Allocation can
    skip checking everything in [0..start) and if it returns
    n, we can set start to n + 1.  Freeing below start sets
    start to what we'd just freed.
    
    Of course, it still sucks if we do something like
    	free 0
    	allocate
    	allocate
    in a loop - still O(n^2) time.  However, on saner loads it
    improves the things a lot and the entire thing is not worth
    the trouble of switching to something with better worst-case
    behaviour.
    
    Signed-off-by: default avatarAl Viro <viro@zeniv.linux.org.uk>
    c63e09ec