• Dan Streetman's avatar
    swap: change swap_info singly-linked list to list_head · adfab836
    Dan Streetman authored
    The logic controlling the singly-linked list of swap_info_struct entries
    for all active, i.e.  swapon'ed, swap targets is rather complex, because:
    
     - it stores the entries in priority order
     - there is a pointer to the highest priority entry
     - there is a pointer to the highest priority not-full entry
     - there is a highest_priority_index variable set outside the swap_lock
     - swap entries of equal priority should be used equally
    
    this complexity leads to bugs such as: https://lkml.org/lkml/2014/2/13/181
    where different priority swap targets are incorrectly used equally.
    
    That bug probably could be solved with the existing singly-linked lists,
    but I think it would only add more complexity to the already difficult to
    understand get_swap_page() swap_list iteration logic.
    
    The first patch changes from a singly-linked list to a doubly-linked list
    using list_heads; the highest_priority_index and related code are removed
    and get_swap_page() starts each iteration at the highest priority
    swap_info entry, even if it's full.  While this does introduce unnecessary
    list iteration (i.e.  Schlemiel the painter's algorithm) in the case where
    one or more of the highest priority entries are full, the iteration and
    manipulation code is much simpler and behaves correctly re: the above bug;
    and the fourth patch removes the unnecessary iteration.
    
    The second patch adds some minor plist helper functions; nothing new
    really, just functions to match existing regular list functions.  These
    are used by the next two patches.
    
    The third patch adds plist_requeue(), which is used by get_swap_page() in
    the next patch - it performs the requeueing of same-priority entries
    (which moves the entry to the end of its priority in the plist), so that
    all equal-priority swap_info_structs get used equally.
    
    The fourth patch converts the main list into a plist, and adds a new plist
    that contains only swap_info entries that are both active and not full.
    As Mel suggested using plists allows removing all the ordering code from
    swap - plists handle ordering automatically.  The list naming is also
    clarified now that there are two lists, with the original list changed
    from swap_list_head to swap_active_head and the new list named
    swap_avail_head.  A new spinlock is also added for the new list, so
    swap_info entries can be added or removed from the new list immediately as
    they become full or not full.
    
    This patch (of 4):
    
    Replace the singly-linked list tracking active, i.e.  swapon'ed,
    swap_info_struct entries with a doubly-linked list using struct
    list_heads.  Simplify the logic iterating and manipulating the list of
    entries, especially get_swap_page(), by using standard list_head
    functions, and removing the highest priority iteration logic.
    
    The change fixes the bug:
    https://lkml.org/lkml/2014/2/13/181
    in which different priority swap entries after the highest priority entry
    are incorrectly used equally in pairs.  The swap behavior is now as
    advertised, i.e. different priority swap entries are used in order, and
    equal priority swap targets are used concurrently.
    Signed-off-by: default avatarDan Streetman <ddstreet@ieee.org>
    Acked-by: default avatarMel Gorman <mgorman@suse.de>
    Cc: Shaohua Li <shli@fusionio.com>
    Cc: Hugh Dickins <hughd@google.com>
    Cc: Dan Streetman <ddstreet@ieee.org>
    Cc: Michal Hocko <mhocko@suse.cz>
    Cc: Christian Ehrhardt <ehrhardt@linux.vnet.ibm.com>
    Cc: Weijie Yang <weijieut@gmail.com>
    Cc: Rik van Riel <riel@redhat.com>
    Cc: Johannes Weiner <hannes@cmpxchg.org>
    Cc: Bob Liu <bob.liu@oracle.com>
    Cc: Steven Rostedt <rostedt@goodmis.org>
    Cc: Peter Zijlstra <peterz@infradead.org>
    Cc: Paul Gortmaker <paul.gortmaker@windriver.com>
    Cc: Thomas Gleixner <tglx@linutronix.de>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    adfab836
swapfile.c 76.1 KB