From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx112.postini.com [74.125.245.112]) by kanga.kvack.org (Postfix) with SMTP id BEBBB6B0002 for ; Tue, 16 Apr 2013 10:43:54 -0400 (EDT) Message-ID: <516D639D.6@parallels.com> Date: Tue, 16 Apr 2013 07:43:41 -0700 From: Glauber Costa MIME-Version: 1.0 Subject: Re: [PATCH v3 08/32] list: add a new LRU list type References: <1365429659-22108-1-git-send-email-glommer@parallels.com> <1365429659-22108-9-git-send-email-glommer@parallels.com> In-Reply-To: Content-Type: text/plain; charset="ISO-8859-1"; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Greg Thelen Cc: linux-mm@kvack.org, cgroups@vger.kernel.org, Dave Shrinnker , Serge Hallyn , kamezawa.hiroyu@jp.fujitsu.com, Michal Hocko , Johannes Weiner , Andrew Morton , hughd@google.com, linux-fsdevel@vger.kernel.org, containers@lists.linux-foundation.org, Dave Chinner On 04/15/2013 10:56 AM, Greg Thelen wrote: > On Sun, Apr 14 2013, Greg Thelen wrote: > >> On Mon, Apr 08 2013, Glauber Costa wrote: >> >>> From: Dave Chinner >>> >>> 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: enum defined constants for lru. Suggested by gthelen ] >>> Signed-off-by: Dave Chinner >>> Signed-off-by: Glauber Costa >> >> Optional nit pick below: >> >> Reviewed-by: Greg Thelen >> >> >>> --- >>> include/linux/list_lru.h | 44 ++++++++++++++++++ >>> lib/Makefile | 2 +- >>> lib/list_lru.c | 117 +++++++++++++++++++++++++++++++++++++++++++++++ >>> 3 files changed, 162 insertions(+), 1 deletion(-) >>> create mode 100644 include/linux/list_lru.h >>> create mode 100644 lib/list_lru.c >>> >>> diff --git a/include/linux/list_lru.h b/include/linux/list_lru.h >>> new file mode 100644 >>> index 0000000..394c28c >>> --- /dev/null >>> +++ b/include/linux/list_lru.h >>> @@ -0,0 +1,44 @@ >>> +/* >>> + * 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, lock dropped */ >>> +}; >>> + >>> +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 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); >>> + >>> +long list_lru_walk(struct list_lru *lru, list_lru_walk_cb isolate, >>> + void *cb_arg, long nr_to_walk); >>> + >>> +long list_lru_dispose_all(struct list_lru *lru, list_lru_dispose_cb dispose); >>> + >>> +#endif /* _LRU_LIST_H */ >>> diff --git a/lib/Makefile b/lib/Makefile >>> index d7946ff..f14abd9 100644 >>> --- a/lib/Makefile >>> +++ b/lib/Makefile >>> @@ -13,7 +13,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \ >>> 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 >>> + earlycpio.o list_lru.o >>> >>> lib-$(CONFIG_MMU) += ioremap.o >>> lib-$(CONFIG_SMP) += cpumask.o >>> diff --git a/lib/list_lru.c b/lib/list_lru.c >>> new file mode 100644 >>> index 0000000..03bd984 >>> --- /dev/null >>> +++ b/lib/list_lru.c >>> @@ -0,0 +1,117 @@ >>> +/* >>> + * 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); >>> + >>> +long >>> +list_lru_walk( >>> + struct list_lru *lru, >>> + list_lru_walk_cb isolate, >>> + void *cb_arg, >>> + long nr_to_walk) >>> +{ >>> + struct list_head *item, *n; >>> + long removed = 0; >>> +restart: >>> + spin_lock(&lru->lock); > > Sometimes isolate() drops the lru locks (when it returns LRU_RETRY) and > sparse complains thus complains here: > > lib/list_lru.c:55:18: warning: context imbalance in 'list_lru_walk' - different lock contexts for basic block > > It looks like other dcache code suffers similar sparse warnings. Is > there any way to annotate this warning away? Or is this just something > we live with? The code is correct. If we return 3 (now LRU_RETRY), we drop the lock in the callback. This is documented in the comment about LRU_RETRY. When we loop again, we don't reacquire the lock However, I think this can be changed to avoid the warning. If we change the semantics to always return with the lock taken, we can drop it in LRU_RETRY (we really have to), then re lock it, and return in the callback with it locked. They we just move the restart: label below the spin_lock acquisition instead of after. It should work, and with clearer semantics. -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org