Skip to content
  • Attilio Rao's avatar
    Sync back vmcontention branch into HEAD: · 774d251d
    Attilio Rao authored
    Replace the per-object resident and cached pages splay tree with a
    path-compressed multi-digit radix trie.
    Along with this, switch also the x86-specific handling of idle page
    tables to using the radix trie.
    
    This change is supposed to do the following:
    - Allowing the acquisition of read locking for lookup operations of the
      resident/cached pages collections as the per-vm_page_t splay iterators
      are now removed.
    - Increase the scalability of the operations on the page collections.
    
    The radix trie does rely on the consumers locking to ensure atomicity of
    its operations.  In order to avoid deadlocks the bisection nodes are
    pre-allocated in the UMA zone.  This can be done safely because the
    algorithm needs at maximum one new node per insert which means the
    maximum number of the desired nodes is the number of available physical
    frames themselves.  However, not all the times a new bisection node is
    really needed.
    
    The radix trie implements path-compression because UFS indirect blocks
    can lead to several objects with a very sparse trie, increasing the number
    of levels to usually scan.  It also helps in the nodes pre-fetching by
    introducing the single node per-insert property.
    
    This code is not generalized (yet) because of the possible loss of
    performance by having much of the sizes in play configurable.
    However, efforts to make this code more general and then reusable in
    further different consumers might be really done.
    
    The only KPI change is the removal of the function vm_page_splay() which
    is now reaped.
    The only KBI change, instead, is the removal of the left/right iterators
    from struct vm_page, which are now reaped.
    
    Further technical notes broken into mealpieces can be retrieved from the
    svn branch:
    http://svn.freebsd.org/base/user/attilio/vmcontention/
    
    Sponsored by:	EMC / Isilon storage division
    In collaboration with:	alc, jeff
    Tested by:	flo, pho, jhb, davide
    Tested by:	ian (arm)
    Tested by:	andreast (powerpc)
    774d251d