From mboxrd@z Thu Jan 1 00:00:00 1970 From: akpm@linux-foundation.org Subject: + list-add-a-new-lru-list-type.patch added to -mm tree Date: Wed, 05 Jun 2013 16:10:45 -0700 Message-ID: <51afc575.OhJOWPugBQVDxAuR%akpm@linux-foundation.org> Reply-To: linux-kernel@vger.kernel.org Mime-Version: 1.0 Content-Type: application/octet-stream Content-Transfer-Encoding: 8bit Return-path: Received: from mail.linuxfoundation.org ([140.211.169.12]:40518 "EHLO mail.linuxfoundation.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1758007Ab3FEXKq (ORCPT ); Wed, 5 Jun 2013 19:10:46 -0400 Sender: mm-commits-owner@vger.kernel.org List-Id: mm-commits@vger.kernel.org To: mm-commits@vger.kernel.org, viro@zeniv.linux.org.uk, tytso@mit.edu, thellstrom@vmware.com, swhiteho@redhat.com, rientjes@google.com, riel@redhat.com, penberg@kernel.org, mtosatti@redhat.com, mhocko@suse.cz, mgorman@suse.de, koverstreet@google.com, kirill.shutemov@linux.intel.com, kamezawa.hiroyu@jp.fujitsu.com, js1304@gmail.com, john.stultz@linaro.org, jglisse@redhat.com, jack@suse.cz, hughd@google.com, hch@lst.de, hannes@cmpxchg.org, gthelen@google.com, glommer@openvz.org, gleb@redhat.com, daniel.vetter@ffwll.ch, cmaiolino@redhat.com, chuck.lever@oracle.com, bfields@redhat.com, arve@android.com, artem.bityutskiy@linux.intel.com, anton@enomsg.org, adrian.hunter@intel.com, Trond.Myklebust@netapp.com, dchinner@redhat.com Subject: + list-add-a-new-lru-list-type.patch added to -mm tree To: dchinner@redhat.com,Trond.Myklebust@netapp.com,adrian.hunter@intel.com,anton@enomsg.org,artem.bityutskiy@linux.intel.com,arve@android.com,bfields@redhat.com,chuck.lever@oracle.com,cmaiolino@redhat.com,daniel.vetter@ffwll.ch,gleb@redhat.com,glommer@openvz.org,gthelen@google.com,hannes@cmpxchg.org,hch@lst.de,hughd@google.com,jack@suse.cz,jglisse@redhat.com,john.stultz@linaro.org,js1304@gmail.com,kamezawa.hiroyu@jp.fujitsu.com,kirill.shutemov@linux.intel.com,koverstreet@google.com,mgorman@suse.de,mhocko@suse.cz,mtosatti@redhat.com,penberg@kernel.org,riel@redhat.com,rientjes@google.com,swhiteho@redhat.com,thellstrom@vmware.com,tytso@mit.edu,viro@zeniv.linux.org.uk From: akpm@linux-foundation.org Date: Wed, 05 Jun 2013 16:10:45 -0700 The patch titled Subject: list: add a new LRU list type has been added to the -mm tree. Its filename is list-add-a-new-lru-list-type.patch Before you just go and hit "reply", please: a) Consider who else should be cc'ed b) Prefer to cc a suitable mailing list as well c) Ideally: find the original patch on the mailing list and do a reply-to-all to that, adding suitable additional cc's *** Remember to use Documentation/SubmitChecklist when testing your code *** The -mm tree is included into linux-next and is updated there every 3-4 working days ------------------------------------------------------ From: Dave Chinner Subject: list: add a new LRU list type Several subsystems use the same construct for LRU lists - a list head, a spin lock and and item count. They also use exactly the same code for adding and removing items from the LRU. Create a generic type for these LRU lists. This is the beginning of generic, node aware LRUs for shrinkers to work with. [glommer@openvz.org: enum defined constants for lru. Suggested by gthelen, don't relock over retry] Signed-off-by: Dave Chinner Signed-off-by: Glauber Costa Reviewed-by: Greg Thelen Acked-by: Mel Gorman Cc: "Theodore Ts'o" Cc: Adrian Hunter Cc: Al Viro Cc: Anton Vorontsov Cc: Artem Bityutskiy Cc: Arve Hjønnevåg Cc: Carlos Maiolino Cc: Christoph Hellwig Cc: Chuck Lever Cc: Daniel Vetter Cc: David Rientjes Cc: Gleb Natapov Cc: Hugh Dickins Cc: J. Bruce Fields Cc: Jan Kara Cc: Jerome Glisse Cc: Johannes Weiner Cc: John Stultz Cc: Joonsoo Kim Cc: KAMEZAWA Hiroyuki Cc: Kent Overstreet Cc: Kirill A. Shutemov Cc: Marcelo Tosatti Cc: Michal Hocko Cc: Pekka Enberg Cc: Rik van Riel Cc: Steven Whitehouse Cc: Thomas Hellstrom Cc: Trond Myklebust Signed-off-by: Andrew Morton --- include/linux/list_lru.h | 46 +++++++++++++ lib/Makefile | 2 lib/list_lru.c | 122 +++++++++++++++++++++++++++++++++++++ 3 files changed, 169 insertions(+), 1 deletion(-) diff -puN /dev/null include/linux/list_lru.h --- /dev/null +++ a/include/linux/list_lru.h @@ -0,0 +1,46 @@ +/* + * Copyright (c) 2010-2012 Red Hat, Inc. All rights reserved. + * Author: David Chinner + * + * Generic LRU infrastructure + */ +#ifndef _LRU_LIST_H +#define _LRU_LIST_H + +#include + +enum lru_status { + LRU_REMOVED, /* item removed from list */ + LRU_ROTATE, /* item referenced, give another pass */ + LRU_SKIP, /* item cannot be locked, skip */ + LRU_RETRY, /* item not freeable. May drop the lock + internally, but has to return locked. */ +}; + +struct list_lru { + spinlock_t lock; + struct list_head list; + long nr_items; +}; + +int list_lru_init(struct list_lru *lru); +int list_lru_add(struct list_lru *lru, struct list_head *item); +int list_lru_del(struct list_lru *lru, struct list_head *item); + +static inline unsigned long list_lru_count(struct list_lru *lru) +{ + return lru->nr_items; +} + +typedef enum lru_status +(*list_lru_walk_cb)(struct list_head *item, spinlock_t *lock, void *cb_arg); + +typedef void (*list_lru_dispose_cb)(struct list_head *dispose_list); + +unsigned long list_lru_walk(struct list_lru *lru, list_lru_walk_cb isolate, + void *cb_arg, unsigned long nr_to_walk); + +unsigned long +list_lru_dispose_all(struct list_lru *lru, list_lru_dispose_cb dispose); + +#endif /* _LRU_LIST_H */ diff -puN lib/Makefile~list-add-a-new-lru-list-type lib/Makefile --- a/lib/Makefile~list-add-a-new-lru-list-type +++ a/lib/Makefile @@ -13,7 +13,7 @@ lib-y := ctype.o string.o vsprintf.o cmd sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \ proportions.o flex_proportions.o prio_heap.o ratelimit.o show_mem.o \ is_single_threaded.o plist.o decompress.o kobject_uevent.o \ - earlycpio.o percpu-refcount.o + earlycpio.o percpu-refcount.o list_lru.o obj-$(CONFIG_ARCH_HAS_DEBUG_STRICT_USER_COPY_CHECKS) += usercopy.o lib-$(CONFIG_MMU) += ioremap.o diff -puN /dev/null lib/list_lru.c --- /dev/null +++ a/lib/list_lru.c @@ -0,0 +1,122 @@ +/* + * Copyright (c) 2010-2012 Red Hat, Inc. All rights reserved. + * Author: David Chinner + * + * Generic LRU infrastructure + */ +#include +#include +#include + +int +list_lru_add( + struct list_lru *lru, + struct list_head *item) +{ + spin_lock(&lru->lock); + if (list_empty(item)) { + list_add_tail(item, &lru->list); + lru->nr_items++; + spin_unlock(&lru->lock); + return 1; + } + spin_unlock(&lru->lock); + return 0; +} +EXPORT_SYMBOL_GPL(list_lru_add); + +int +list_lru_del( + struct list_lru *lru, + struct list_head *item) +{ + spin_lock(&lru->lock); + if (!list_empty(item)) { + list_del_init(item); + lru->nr_items--; + spin_unlock(&lru->lock); + return 1; + } + spin_unlock(&lru->lock); + return 0; +} +EXPORT_SYMBOL_GPL(list_lru_del); + +unsigned long +list_lru_walk( + struct list_lru *lru, + list_lru_walk_cb isolate, + void *cb_arg, + unsigned long nr_to_walk) +{ + struct list_head *item, *n; + unsigned long removed = 0; + + spin_lock(&lru->lock); + list_for_each_safe(item, n, &lru->list) { + enum lru_status ret; + bool first_pass = true; +restart: + ret = isolate(item, &lru->lock, cb_arg); + switch (ret) { + case LRU_REMOVED: + lru->nr_items--; + removed++; + break; + case LRU_ROTATE: + list_move_tail(item, &lru->list); + break; + case LRU_SKIP: + break; + case LRU_RETRY: + if (!first_pass) + break; + first_pass = false; + goto restart; + default: + BUG(); + } + + if (nr_to_walk-- == 0) + break; + + } + spin_unlock(&lru->lock); + return removed; +} +EXPORT_SYMBOL_GPL(list_lru_walk); + +unsigned long +list_lru_dispose_all( + struct list_lru *lru, + list_lru_dispose_cb dispose) +{ + unsigned long disposed = 0; + LIST_HEAD(dispose_list); + + spin_lock(&lru->lock); + while (!list_empty(&lru->list)) { + list_splice_init(&lru->list, &dispose_list); + disposed += lru->nr_items; + lru->nr_items = 0; + spin_unlock(&lru->lock); + + dispose(&dispose_list); + + spin_lock(&lru->lock); + } + spin_unlock(&lru->lock); + return disposed; +} + +int +list_lru_init( + struct list_lru *lru) +{ + spin_lock_init(&lru->lock); + INIT_LIST_HEAD(&lru->list); + lru->nr_items = 0; + + return 0; +} +EXPORT_SYMBOL_GPL(list_lru_init); _ Patches currently in -mm which might be from dchinner@redhat.com are linux-next.patch fs-bump-inode-and-dentry-counters-to-long.patch dcache-convert-dentry_statnr_unused-to-per-cpu-counters.patch dentry-move-to-per-sb-lru-locks.patch dcache-remove-dentries-from-lru-before-putting-on-dispose-list.patch dcache-remove-dentries-from-lru-before-putting-on-dispose-list-fix.patch mm-new-shrinker-api.patch shrinker-convert-superblock-shrinkers-to-new-api.patch list-add-a-new-lru-list-type.patch inode-convert-inode-lru-list-to-generic-lru-list-code.patch dcache-convert-to-use-new-lru-list-infrastructure.patch list_lru-per-node-list-infrastructure.patch shrinker-add-node-awareness.patch vmscan-per-node-deferred-work.patch list_lru-per-node-api.patch fs-convert-inode-and-dentry-shrinking-to-be-node-aware.patch xfs-convert-buftarg-lru-to-generic-code.patch xfs-rework-buffer-dispose-list-tracking.patch xfs-convert-dquot-cache-lru-to-list_lru.patch fs-convert-fs-shrinkers-to-new-scan-count-api.patch drivers-convert-shrinkers-to-new-count-scan-api.patch i915-bail-out-earlier-when-shrinker-cannot-acquire-mutex.patch shrinker-convert-remaining-shrinkers-to-count-scan-api.patch hugepage-convert-huge-zero-page-shrinker-to-new-shrinker-api.patch shrinker-kill-old-shrink-api.patch vmscan-also-shrink-slab-in-memcg-pressure.patch memcglist_lru-duplicate-lrus-upon-kmemcg-creation.patch lru-add-an-element-to-a-memcg-list.patch list_lru-per-memcg-walks.patch memcg-per-memcg-kmem-shrinking.patch memcg-scan-cache-objects-hierarchically.patch super-targeted-memcg-reclaim.patch memcg-move-initialization-to-memcg-creation.patch memcg-reap-dead-memcgs-upon-global-memory-pressure.patch