Re: [PATCH 1/2] swap: change swap_info singly-linked list to list_head

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On Wed, Apr 23, 2014 at 6:34 AM, Mel Gorman <mgorman@xxxxxxx> wrote:
> On Sat, Apr 12, 2014 at 05:00:53PM -0400, Dan Streetman wrote:
>> 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: Dan Streetman <ddstreet@xxxxxxxx>
>> ---
>>  include/linux/swap.h     |   7 +--
>>  include/linux/swapfile.h |   2 +-
>>  mm/frontswap.c           |  13 ++--
>>  mm/swapfile.c            | 156 +++++++++++++++++------------------------------
>>  4 files changed, 63 insertions(+), 115 deletions(-)
>>
>> diff --git a/include/linux/swap.h b/include/linux/swap.h
>> index 3507115..96662d8 100644
>> --- a/include/linux/swap.h
>> +++ b/include/linux/swap.h
>> @@ -214,8 +214,8 @@ struct percpu_cluster {
>>  struct swap_info_struct {
>>       unsigned long   flags;          /* SWP_USED etc: see above */
>>       signed short    prio;           /* swap priority of this type */
>> +     struct list_head list;          /* entry in swap list */
>>       signed char     type;           /* strange name for an index */
>> -     signed char     next;           /* next type on the swap list */
>>       unsigned int    max;            /* extent of the swap_map */
>>       unsigned char *swap_map;        /* vmalloc'ed array of usage counts */
>>       struct swap_cluster_info *cluster_info; /* cluster info. Only for SSD */
>> @@ -255,11 +255,6 @@ struct swap_info_struct {
>>       struct swap_cluster_info discard_cluster_tail; /* list tail of discard clusters */
>>  };
>>
>> -struct swap_list_t {
>> -     int head;       /* head of priority-ordered swapfile list */
>> -     int next;       /* swapfile to be used next */
>> -};
>> -
>>  /* linux/mm/workingset.c */
>>  void *workingset_eviction(struct address_space *mapping, struct page *page);
>>  bool workingset_refault(void *shadow);
>> diff --git a/include/linux/swapfile.h b/include/linux/swapfile.h
>> index e282624..2eab382 100644
>> --- a/include/linux/swapfile.h
>> +++ b/include/linux/swapfile.h
>> @@ -6,7 +6,7 @@
>>   * want to expose them to the dozens of source files that include swap.h
>>   */
>>  extern spinlock_t swap_lock;
>> -extern struct swap_list_t swap_list;
>> +extern struct list_head swap_list_head;
>>  extern struct swap_info_struct *swap_info[];
>>  extern int try_to_unuse(unsigned int, bool, unsigned long);
>>
>> diff --git a/mm/frontswap.c b/mm/frontswap.c
>> index 1b24bdc..fae1160 100644
>> --- a/mm/frontswap.c
>> +++ b/mm/frontswap.c
>> @@ -327,15 +327,12 @@ EXPORT_SYMBOL(__frontswap_invalidate_area);
>>
>>  static unsigned long __frontswap_curr_pages(void)
>>  {
>> -     int type;
>>       unsigned long totalpages = 0;
>>       struct swap_info_struct *si = NULL;
>>
>>       assert_spin_locked(&swap_lock);
>> -     for (type = swap_list.head; type >= 0; type = si->next) {
>> -             si = swap_info[type];
>> +     list_for_each_entry(si, &swap_list_head, list)
>>               totalpages += atomic_read(&si->frontswap_pages);
>> -     }
>>       return totalpages;
>>  }
>>
>> @@ -347,11 +344,9 @@ static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused,
>>       int si_frontswap_pages;
>>       unsigned long total_pages_to_unuse = total;
>>       unsigned long pages = 0, pages_to_unuse = 0;
>> -     int type;
>>
>>       assert_spin_locked(&swap_lock);
>> -     for (type = swap_list.head; type >= 0; type = si->next) {
>> -             si = swap_info[type];
>> +     list_for_each_entry(si, &swap_list_head, list) {
>>               si_frontswap_pages = atomic_read(&si->frontswap_pages);
>>               if (total_pages_to_unuse < si_frontswap_pages) {
>>                       pages = pages_to_unuse = total_pages_to_unuse;
>
> The frontswap shrink code looks suspicious. If the target is smaller than
> the total number of frontswap pages then it does nothing. The callers
> appear to get this right at least. Similarly, if the first swapfile has
> fewer frontswap pages than the target then it does not unuse the target
> number of pages because it only handles one swap file. It's outside the
> scope of your patch to address this or wonder if xen balloon driver is
> really using it the way it's expected.

I didn't look into the frontswap shrinking code, but I agree the
existing logic there doesn't look right.  I'll review frontswap in
more detail to see if it needs changing here, unless anyone else gets
it to first :-)

And as you said, it's outside the scope of this particular patch.

>
> The old code scanned the files in priority order. Superficially this does
> not appear to but it actually does because you add the swap files to the
> list in priority order during swapon. If you do another revision it's
> worth adding a comment above swap_list_head that the list is ordered by
> priority and protected by the swap_lock.

Yep you're right, I will add a comment to make clear it's also
priority ordered, and why.  The only reason it needs to be priority
ordered is because swapoff has to adjust the auto-priority of any
following swap_info_structs when one is removed, that has an
automatically assigned (i.e. negative) priority.

>
>> @@ -366,7 +361,7 @@ static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused,
>>               }
>>               vm_unacct_memory(pages);
>>               *unused = pages_to_unuse;
>> -             *swapid = type;
>> +             *swapid = si->type;
>>               ret = 0;
>>               break;
>>       }
>> @@ -413,7 +408,7 @@ void frontswap_shrink(unsigned long target_pages)
>>       /*
>>        * we don't want to hold swap_lock while doing a very
>>        * lengthy try_to_unuse, but swap_list may change
>> -      * so restart scan from swap_list.head each time
>> +      * so restart scan from swap_list_head each time
>>        */
>>       spin_lock(&swap_lock);
>>       ret = __frontswap_shrink(target_pages, &pages_to_unuse, &type);
>> diff --git a/mm/swapfile.c b/mm/swapfile.c
>> index 4a7f7e6..b958645 100644
>> --- a/mm/swapfile.c
>> +++ b/mm/swapfile.c
>> @@ -51,14 +51,14 @@ atomic_long_t nr_swap_pages;
>>  /* protected with swap_lock. reading in vm_swap_full() doesn't need lock */
>>  long total_swap_pages;
>>  static int least_priority;
>> -static atomic_t highest_priority_index = ATOMIC_INIT(-1);
>>
>>  static const char Bad_file[] = "Bad swap file entry ";
>>  static const char Unused_file[] = "Unused swap file entry ";
>>  static const char Bad_offset[] = "Bad swap offset entry ";
>>  static const char Unused_offset[] = "Unused swap offset entry ";
>>
>> -struct swap_list_t swap_list = {-1, -1};
>> +/* all active swap_info */
>> +LIST_HEAD(swap_list_head);
>>
>>  struct swap_info_struct *swap_info[MAX_SWAPFILES];
>>
>> @@ -640,66 +640,50 @@ no_page:
>>
>>  swp_entry_t get_swap_page(void)
>>  {
>> -     struct swap_info_struct *si;
>> +     struct swap_info_struct *si, *next;
>>       pgoff_t offset;
>> -     int type, next;
>> -     int wrapped = 0;
>> -     int hp_index;
>> +     struct list_head *tmp;
>>
>>       spin_lock(&swap_lock);
>>       if (atomic_long_read(&nr_swap_pages) <= 0)
>>               goto noswap;
>>       atomic_long_dec(&nr_swap_pages);
>>
>> -     for (type = swap_list.next; type >= 0 && wrapped < 2; type = next) {
>> -             hp_index = atomic_xchg(&highest_priority_index, -1);
>> -             /*
>> -              * highest_priority_index records current highest priority swap
>> -              * type which just frees swap entries. If its priority is
>> -              * higher than that of swap_list.next swap type, we use it.  It
>> -              * isn't protected by swap_lock, so it can be an invalid value
>> -              * if the corresponding swap type is swapoff. We double check
>> -              * the flags here. It's even possible the swap type is swapoff
>> -              * and swapon again and its priority is changed. In such rare
>> -              * case, low prority swap type might be used, but eventually
>> -              * high priority swap will be used after several rounds of
>> -              * swap.
>> -              */
>> -             if (hp_index != -1 && hp_index != type &&
>> -                 swap_info[type]->prio < swap_info[hp_index]->prio &&
>> -                 (swap_info[hp_index]->flags & SWP_WRITEOK)) {
>> -                     type = hp_index;
>> -                     swap_list.next = type;
>> -             }
>> -
>> -             si = swap_info[type];
>> -             next = si->next;
>> -             if (next < 0 ||
>> -                 (!wrapped && si->prio != swap_info[next]->prio)) {
>> -                     next = swap_list.head;
>> -                     wrapped++;
>> -             }
>> -
>> +     list_for_each(tmp, &swap_list_head) {
>> +             si = list_entry(tmp, typeof(*si), list);
>>               spin_lock(&si->lock);
>> -             if (!si->highest_bit) {
>> -                     spin_unlock(&si->lock);
>> -                     continue;
>> -             }
>> -             if (!(si->flags & SWP_WRITEOK)) {
>> +             if (!si->highest_bit || !(si->flags & SWP_WRITEOK)) {
>>                       spin_unlock(&si->lock);
>>                       continue;
>>               }
>>
>> -             swap_list.next = next;
>> +             /*
>> +              * rotate the current swap_info that we're going to use
>> +              * to after any other swap_info that have the same prio,
>> +              * so that all equal-priority swap_info get used equally
>> +              */
>> +             next = si;
>> +             list_for_each_entry_continue(next, &swap_list_head, list) {
>> +                     if (si->prio != next->prio)
>> +                             break;
>> +                     list_rotate_left(&si->list);
>> +                     next = si;
>> +             }
>>
>
> The list manipulations will be a lot of cache writes as the list is shuffled
> around. On slow storage I do not think this will be noticable but it may
> be noticable on faster swap devices that are SSD based. I've added Shaohua
> Li to the cc as he has been concerned with the performance of swap in the
> past. Shaohua, can you run this patchset through any of your test cases
> with the addition that multiple swap files are used to see if the cache
> writes are noticable? You'll need multiple swap files, some of which are
> at equal priority so the list shuffling logic is triggered.

One performance improvement could be instead of rotating the current
entry past each following same-prio entry, just scan to the end of the
same-prio entries and move the current entry there; that would skip
the extra writes.  Especially since this code will run for each
get_swap_page(), no need for any unnecessary writes.

>
>>               spin_unlock(&swap_lock);
>>               /* This is called for allocating swap entry for cache */
>>               offset = scan_swap_map(si, SWAP_HAS_CACHE);
>>               spin_unlock(&si->lock);
>>               if (offset)
>> -                     return swp_entry(type, offset);
>> +                     return swp_entry(si->type, offset);
>>               spin_lock(&swap_lock);
>> -             next = swap_list.next;
>> +             /*
>> +              * shouldn't really have got here, but for some reason the
>> +              * scan_swap_map came back empty for this swap_info.
>> +              * Since we dropped the swap_lock, there may now be
>> +              * non-full higher prio swap_infos; let's start over.
>> +              */
>> +             tmp = &swap_list_head;
>>       }
>
> Has this ever triggered? The number of swap pages was examined under the
> swap lock so no other process should have been iterating through the
> swap files. Once a candidate was found, the si lock was acquired for the
> swap scan map so nothing else should have raced with it.

Well scan_swap_map() does drop the si->lock if it has any trouble at
all finding an offset to use, so I think it's possible that for a
nearly-full si multiple concurrent get_swap_page() calls could enter
scan_swap_map() with the same si, only some of them actually get pages
from the si and then the si becomes full, and the other threads in
scan_swap_map() see it's full and exit in failure.  I can update the
code comment there to better indicate why it was reached, instead of
just saying "we shouldn't have got here" :-)

It may also be worth trying to get a better indicator of "available"
swap_info_structs for use in get_swap_page(), either by looking at
something other than si->highest_bit and/or keeping the si out of the
prio_list until it's actually available for use, not just has a single
entry free.  However, that probably won't be simple and might be
better as a separate patch to the rest of these changes.

>
>>
>>       atomic_long_inc(&nr_swap_pages);
>> @@ -766,27 +750,6 @@ out:
>>       return NULL;
>>  }
>>
>> -/*
>> - * This swap type frees swap entry, check if it is the highest priority swap
>> - * type which just frees swap entry. get_swap_page() uses
>> - * highest_priority_index to search highest priority swap type. The
>> - * swap_info_struct.lock can't protect us if there are multiple swap types
>> - * active, so we use atomic_cmpxchg.
>> - */
>> -static void set_highest_priority_index(int type)
>> -{
>> -     int old_hp_index, new_hp_index;
>> -
>> -     do {
>> -             old_hp_index = atomic_read(&highest_priority_index);
>> -             if (old_hp_index != -1 &&
>> -                     swap_info[old_hp_index]->prio >= swap_info[type]->prio)
>> -                     break;
>> -             new_hp_index = type;
>> -     } while (atomic_cmpxchg(&highest_priority_index,
>> -             old_hp_index, new_hp_index) != old_hp_index);
>> -}
>> -
>>  static unsigned char swap_entry_free(struct swap_info_struct *p,
>>                                    swp_entry_t entry, unsigned char usage)
>>  {
>> @@ -830,7 +793,6 @@ static unsigned char swap_entry_free(struct swap_info_struct *p,
>>                       p->lowest_bit = offset;
>>               if (offset > p->highest_bit)
>>                       p->highest_bit = offset;
>> -             set_highest_priority_index(p->type);
>>               atomic_long_inc(&nr_swap_pages);
>>               p->inuse_pages--;
>>               frontswap_invalidate_page(p->type, offset);
>> @@ -1765,7 +1727,7 @@ static void _enable_swap_info(struct swap_info_struct *p, int prio,
>>                               unsigned char *swap_map,
>>                               struct swap_cluster_info *cluster_info)
>>  {
>> -     int i, prev;
>> +     struct swap_info_struct *si;
>>
>>       if (prio >= 0)
>>               p->prio = prio;
>> @@ -1777,18 +1739,21 @@ static void _enable_swap_info(struct swap_info_struct *p, int prio,
>>       atomic_long_add(p->pages, &nr_swap_pages);
>>       total_swap_pages += p->pages;
>>
>> -     /* insert swap space into swap_list: */
>> -     prev = -1;
>> -     for (i = swap_list.head; i >= 0; i = swap_info[i]->next) {
>> -             if (p->prio >= swap_info[i]->prio)
>> -                     break;
>> -             prev = i;
>> +     assert_spin_locked(&swap_lock);
>> +     BUG_ON(!list_empty(&p->list));
>> +     /* insert into swap list: */
>> +     list_for_each_entry(si, &swap_list_head, list) {
>> +             if (p->prio >= si->prio) {
>> +                     list_add_tail(&p->list, &si->list);
>> +                     return;
>> +             }
>
> An additional comment saying that it must be priority ordered for
> get_swap_page wouldn't kill.

will do.

>
>>       }
>> -     p->next = i;
>> -     if (prev < 0)
>> -             swap_list.head = swap_list.next = p->type;
>> -     else
>> -             swap_info[prev]->next = p->type;
>> +     /*
>> +      * this covers two cases:
>> +      * 1) p->prio is less than all existing prio
>> +      * 2) the swap list is empty
>> +      */
>> +     list_add_tail(&p->list, &swap_list_head);
>>  }
>>
>>  static void enable_swap_info(struct swap_info_struct *p, int prio,
>> @@ -1823,8 +1788,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
>>       struct address_space *mapping;
>>       struct inode *inode;
>>       struct filename *pathname;
>> -     int i, type, prev;
>> -     int err;
>> +     int err, found = 0;
>>       unsigned int old_block_size;
>>
>>       if (!capable(CAP_SYS_ADMIN))
>> @@ -1842,17 +1806,16 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
>>               goto out;
>>
>>       mapping = victim->f_mapping;
>> -     prev = -1;
>>       spin_lock(&swap_lock);
>> -     for (type = swap_list.head; type >= 0; type = swap_info[type]->next) {
>> -             p = swap_info[type];
>> +     list_for_each_entry(p, &swap_list_head, list) {
>>               if (p->flags & SWP_WRITEOK) {
>> -                     if (p->swap_file->f_mapping == mapping)
>> +                     if (p->swap_file->f_mapping == mapping) {
>> +                             found = 1;
>>                               break;
>> +                     }
>>               }
>> -             prev = type;
>>       }
>> -     if (type < 0) {
>> +     if (!found) {
>>               err = -EINVAL;
>>               spin_unlock(&swap_lock);
>>               goto out_dput;
>> @@ -1864,20 +1827,15 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
>>               spin_unlock(&swap_lock);
>>               goto out_dput;
>>       }
>> -     if (prev < 0)
>> -             swap_list.head = p->next;
>> -     else
>> -             swap_info[prev]->next = p->next;
>> -     if (type == swap_list.next) {
>> -             /* just pick something that's safe... */
>> -             swap_list.next = swap_list.head;
>> -     }
>>       spin_lock(&p->lock);
>>       if (p->prio < 0) {
>> -             for (i = p->next; i >= 0; i = swap_info[i]->next)
>> -                     swap_info[i]->prio = p->prio--;
>> +             struct swap_info_struct *si = p;
>> +             list_for_each_entry_continue(si, &swap_list_head, list) {
>> +                     si->prio++;
>> +             }
>>               least_priority++;
>>       }
>> +     list_del_init(&p->list);
>>       atomic_long_sub(p->pages, &nr_swap_pages);
>>       total_swap_pages -= p->pages;
>>       p->flags &= ~SWP_WRITEOK;
>> @@ -1885,7 +1843,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
>>       spin_unlock(&swap_lock);
>>
>>       set_current_oom_origin();
>> -     err = try_to_unuse(type, false, 0); /* force all pages to be unused */
>> +     err = try_to_unuse(p->type, false, 0); /* force unuse all pages */
>>       clear_current_oom_origin();
>>
>>       if (err) {
>> @@ -1926,7 +1884,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
>>       frontswap_map = frontswap_map_get(p);
>>       spin_unlock(&p->lock);
>>       spin_unlock(&swap_lock);
>> -     frontswap_invalidate_area(type);
>> +     frontswap_invalidate_area(p->type);
>>       frontswap_map_set(p, NULL);
>>       mutex_unlock(&swapon_mutex);
>>       free_percpu(p->percpu_cluster);
>> @@ -1935,7 +1893,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
>>       vfree(cluster_info);
>>       vfree(frontswap_map);
>>       /* Destroy swap account information */
>> -     swap_cgroup_swapoff(type);
>> +     swap_cgroup_swapoff(p->type);
>>
>>       inode = mapping->host;
>>       if (S_ISBLK(inode->i_mode)) {
>> @@ -2142,8 +2100,8 @@ static struct swap_info_struct *alloc_swap_info(void)
>>                */
>>       }
>>       INIT_LIST_HEAD(&p->first_swap_extent.list);
>> +     INIT_LIST_HEAD(&p->list);
>>       p->flags = SWP_USED;
>> -     p->next = -1;
>>       spin_unlock(&swap_lock);
>>       spin_lock_init(&p->lock);
>>
>> --
>> 1.8.3.1
>>
>
> --
> Mel Gorman
> SUSE Labs

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@xxxxxxxxx.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>




[Index of Archives]     [Linux ARM Kernel]     [Linux ARM]     [Linux Omap]     [Fedora ARM]     [IETF Annouce]     [Bugtraq]     [Linux]     [Linux OMAP]     [Linux MIPS]     [ECOS]     [Asterisk Internet PBX]     [Linux API]