From: Jan Kara <jack@suse.cz> To: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com> Cc: Andrea Arcangeli <aarcange@redhat.com>, Andrew Morton <akpm@linux-foundation.org>, Al Viro <viro@zeniv.linux.org.uk>, Hugh Dickins <hughd@google.com>, Wu Fengguang <fengguang.wu@intel.com>, Jan Kara <jack@suse.cz>, Mel Gorman <mgorman@suse.de>, linux-mm@kvack.org, Andi Kleen <ak@linux.intel.com>, Matthew Wilcox <willy@linux.intel.com>, "Kirill A. Shutemov" <kirill@shutemov.name>, Hillf Danton <dhillf@gmail.com>, Dave Hansen <dave@sr71.net>, Ning Qu <quning@google.com>, linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org Subject: Re: [PATCH 01/23] radix-tree: implement preload for multiple contiguous elements Date: Mon, 5 Aug 2013 13:17:39 +0200 [thread overview] Message-ID: <20130805111739.GA25691@quack.suse.cz> (raw) In-Reply-To: <1375582645-29274-2-git-send-email-kirill.shutemov@linux.intel.com> On Sun 04-08-13 05:17:03, Kirill A. Shutemov wrote: > From: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com> > > The radix tree is variable-height, so an insert operation not only has > to build the branch to its corresponding item, it also has to build the > branch to existing items if the size has to be increased (by > radix_tree_extend). > > The worst case is a zero height tree with just a single item at index 0, > and then inserting an item at index ULONG_MAX. This requires 2 new branches > of RADIX_TREE_MAX_PATH size to be created, with only the root node shared. > > Radix tree is usually protected by spin lock. It means we want to > pre-allocate required memory before taking the lock. > > Currently radix_tree_preload() only guarantees enough nodes to insert > one element. It's a hard limit. For transparent huge page cache we want > to insert HPAGE_PMD_NR (512 on x86-64) entries to address_space at once. > > This patch introduces radix_tree_preload_count(). It allows to > preallocate nodes enough to insert a number of *contiguous* elements. > The feature costs about 5KiB per-CPU, details below. > > Worst case for adding N contiguous items is adding entries at indexes > (ULONG_MAX - N) to ULONG_MAX. It requires nodes to insert single worst-case > item plus extra nodes if you cross the boundary from one node to the next. > > Preload uses per-CPU array to store nodes. The total cost of preload is > "array size" * sizeof(void*) * NR_CPUS. We want to increase array size > to be able to handle 512 entries at once. > > Size of array depends on system bitness and on RADIX_TREE_MAP_SHIFT. > > We have three possible RADIX_TREE_MAP_SHIFT: > > #ifdef __KERNEL__ > #define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6) > #else > #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */ > #endif > > On 64-bit system: > For RADIX_TREE_MAP_SHIFT=3, old array size is 43, new is 107. > For RADIX_TREE_MAP_SHIFT=4, old array size is 31, new is 63. > For RADIX_TREE_MAP_SHIFT=6, old array size is 21, new is 30. > > On 32-bit system: > For RADIX_TREE_MAP_SHIFT=3, old array size is 21, new is 84. > For RADIX_TREE_MAP_SHIFT=4, old array size is 15, new is 46. > For RADIX_TREE_MAP_SHIFT=6, old array size is 11, new is 19. > > On most machines we will have RADIX_TREE_MAP_SHIFT=6. In this case, > on 64-bit system the per-CPU feature overhead is > for preload array: > (30 - 21) * sizeof(void*) = 72 bytes > plus, if the preload array is full > (30 - 21) * sizeof(struct radix_tree_node) = 9 * 560 = 5040 bytes > total: 5112 bytes > > on 32-bit system the per-CPU feature overhead is > for preload array: > (19 - 11) * sizeof(void*) = 32 bytes > plus, if the preload array is full > (19 - 11) * sizeof(struct radix_tree_node) = 8 * 296 = 2368 bytes > total: 2400 bytes > > Since only THP uses batched preload at the moment, we disable (set max > preload to 1) it if !CONFIG_TRANSPARENT_HUGEPAGE_PAGECACHE. This can be > changed in the future. > > Signed-off-by: Matthew Wilcox <willy@linux.intel.com> > Signed-off-by: Kirill A. Shutemov <kirill.shutemov@linux.intel.com> > Acked-by: Dave Hansen <dave.hansen@linux.intel.com> > --- > include/linux/radix-tree.h | 11 +++++++++++ > lib/radix-tree.c | 41 ++++++++++++++++++++++++++++++++--------- > 2 files changed, 43 insertions(+), 9 deletions(-) ... > diff --git a/lib/radix-tree.c b/lib/radix-tree.c > index 7811ed3..99ab73c 100644 > --- a/lib/radix-tree.c > +++ b/lib/radix-tree.c > @@ -82,16 +82,24 @@ static struct kmem_cache *radix_tree_node_cachep; > * The worst case is a zero height tree with just a single item at index 0, > * and then inserting an item at index ULONG_MAX. This requires 2 new branches > * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared. > + * > + * Worst case for adding N contiguous items is adding entries at indexes > + * (ULONG_MAX - N) to ULONG_MAX. It requires nodes to insert single worst-case > + * item plus extra nodes if you cross the boundary from one node to the next. > + * > * Hence: > */ > -#define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1) > +#define RADIX_TREE_PRELOAD_MIN (RADIX_TREE_MAX_PATH * 2 - 1) > +#define RADIX_TREE_PRELOAD_MAX \ > + (RADIX_TREE_PRELOAD_MIN + \ > + DIV_ROUND_UP(RADIX_TREE_PRELOAD_NR - 1, RADIX_TREE_MAP_SIZE)) Umm, is this really correct? I see two problems: 1) You may need internal tree nodes at various levels but you seem to account only for the level 1. 2) The rounding doesn't seem right because RADIX_TREE_MAP_SIZE+2 nodes may require 3 nodes at level 1 if the indexes are like: i_0 | i_1 .. i_{RADIX_TREE_MAP_SIZE} | i_{RADIX_TREE_MAP_SIZE+1} ^ ^ node boundary node boundary Otherwise the patch looks good. Honza -- Jan Kara <jack@suse.cz> SUSE Labs, CR
WARNING: multiple messages have this Message-ID (diff)
From: Jan Kara <jack@suse.cz> To: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com> Cc: Andrea Arcangeli <aarcange@redhat.com>, Andrew Morton <akpm@linux-foundation.org>, Al Viro <viro@zeniv.linux.org.uk>, Hugh Dickins <hughd@google.com>, Wu Fengguang <fengguang.wu@intel.com>, Jan Kara <jack@suse.cz>, Mel Gorman <mgorman@suse.de>, linux-mm@kvack.org, Andi Kleen <ak@linux.intel.com>, Matthew Wilcox <willy@linux.intel.com>, "Kirill A. Shutemov" <kirill@shutemov.name>, Hillf Danton <dhillf@gmail.com>, Dave Hansen <dave@sr71.net>, Ning Qu <quning@google.com>, linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org Subject: Re: [PATCH 01/23] radix-tree: implement preload for multiple contiguous elements Date: Mon, 5 Aug 2013 13:17:39 +0200 [thread overview] Message-ID: <20130805111739.GA25691@quack.suse.cz> (raw) In-Reply-To: <1375582645-29274-2-git-send-email-kirill.shutemov@linux.intel.com> On Sun 04-08-13 05:17:03, Kirill A. Shutemov wrote: > From: "Kirill A. Shutemov" <kirill.shutemov@linux.intel.com> > > The radix tree is variable-height, so an insert operation not only has > to build the branch to its corresponding item, it also has to build the > branch to existing items if the size has to be increased (by > radix_tree_extend). > > The worst case is a zero height tree with just a single item at index 0, > and then inserting an item at index ULONG_MAX. This requires 2 new branches > of RADIX_TREE_MAX_PATH size to be created, with only the root node shared. > > Radix tree is usually protected by spin lock. It means we want to > pre-allocate required memory before taking the lock. > > Currently radix_tree_preload() only guarantees enough nodes to insert > one element. It's a hard limit. For transparent huge page cache we want > to insert HPAGE_PMD_NR (512 on x86-64) entries to address_space at once. > > This patch introduces radix_tree_preload_count(). It allows to > preallocate nodes enough to insert a number of *contiguous* elements. > The feature costs about 5KiB per-CPU, details below. > > Worst case for adding N contiguous items is adding entries at indexes > (ULONG_MAX - N) to ULONG_MAX. It requires nodes to insert single worst-case > item plus extra nodes if you cross the boundary from one node to the next. > > Preload uses per-CPU array to store nodes. The total cost of preload is > "array size" * sizeof(void*) * NR_CPUS. We want to increase array size > to be able to handle 512 entries at once. > > Size of array depends on system bitness and on RADIX_TREE_MAP_SHIFT. > > We have three possible RADIX_TREE_MAP_SHIFT: > > #ifdef __KERNEL__ > #define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6) > #else > #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */ > #endif > > On 64-bit system: > For RADIX_TREE_MAP_SHIFT=3, old array size is 43, new is 107. > For RADIX_TREE_MAP_SHIFT=4, old array size is 31, new is 63. > For RADIX_TREE_MAP_SHIFT=6, old array size is 21, new is 30. > > On 32-bit system: > For RADIX_TREE_MAP_SHIFT=3, old array size is 21, new is 84. > For RADIX_TREE_MAP_SHIFT=4, old array size is 15, new is 46. > For RADIX_TREE_MAP_SHIFT=6, old array size is 11, new is 19. > > On most machines we will have RADIX_TREE_MAP_SHIFT=6. In this case, > on 64-bit system the per-CPU feature overhead is > for preload array: > (30 - 21) * sizeof(void*) = 72 bytes > plus, if the preload array is full > (30 - 21) * sizeof(struct radix_tree_node) = 9 * 560 = 5040 bytes > total: 5112 bytes > > on 32-bit system the per-CPU feature overhead is > for preload array: > (19 - 11) * sizeof(void*) = 32 bytes > plus, if the preload array is full > (19 - 11) * sizeof(struct radix_tree_node) = 8 * 296 = 2368 bytes > total: 2400 bytes > > Since only THP uses batched preload at the moment, we disable (set max > preload to 1) it if !CONFIG_TRANSPARENT_HUGEPAGE_PAGECACHE. This can be > changed in the future. > > Signed-off-by: Matthew Wilcox <willy@linux.intel.com> > Signed-off-by: Kirill A. Shutemov <kirill.shutemov@linux.intel.com> > Acked-by: Dave Hansen <dave.hansen@linux.intel.com> > --- > include/linux/radix-tree.h | 11 +++++++++++ > lib/radix-tree.c | 41 ++++++++++++++++++++++++++++++++--------- > 2 files changed, 43 insertions(+), 9 deletions(-) ... > diff --git a/lib/radix-tree.c b/lib/radix-tree.c > index 7811ed3..99ab73c 100644 > --- a/lib/radix-tree.c > +++ b/lib/radix-tree.c > @@ -82,16 +82,24 @@ static struct kmem_cache *radix_tree_node_cachep; > * The worst case is a zero height tree with just a single item at index 0, > * and then inserting an item at index ULONG_MAX. This requires 2 new branches > * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared. > + * > + * Worst case for adding N contiguous items is adding entries at indexes > + * (ULONG_MAX - N) to ULONG_MAX. It requires nodes to insert single worst-case > + * item plus extra nodes if you cross the boundary from one node to the next. > + * > * Hence: > */ > -#define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1) > +#define RADIX_TREE_PRELOAD_MIN (RADIX_TREE_MAX_PATH * 2 - 1) > +#define RADIX_TREE_PRELOAD_MAX \ > + (RADIX_TREE_PRELOAD_MIN + \ > + DIV_ROUND_UP(RADIX_TREE_PRELOAD_NR - 1, RADIX_TREE_MAP_SIZE)) Umm, is this really correct? I see two problems: 1) You may need internal tree nodes at various levels but you seem to account only for the level 1. 2) The rounding doesn't seem right because RADIX_TREE_MAP_SIZE+2 nodes may require 3 nodes at level 1 if the indexes are like: i_0 | i_1 .. i_{RADIX_TREE_MAP_SIZE} | i_{RADIX_TREE_MAP_SIZE+1} ^ ^ node boundary node boundary Otherwise the patch looks good. Honza -- Jan Kara <jack@suse.cz> SUSE Labs, CR -- 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: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
next prev parent reply other threads:[~2013-08-05 11:17 UTC|newest] Thread overview: 116+ messages / expand[flat|nested] mbox.gz Atom feed top 2013-08-04 2:17 [PATCHv5 00/23] Transparent huge page cache: phase 1, everything but mmap() Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-04 2:17 ` [PATCH 01/23] radix-tree: implement preload for multiple contiguous elements Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-05 11:17 ` Jan Kara [this message] 2013-08-05 11:17 ` Jan Kara 2013-08-06 16:34 ` Matthew Wilcox 2013-08-06 16:34 ` Matthew Wilcox 2013-08-06 20:17 ` Jan Kara 2013-08-06 20:17 ` Jan Kara 2013-08-07 16:32 ` Kirill A. Shutemov 2013-08-07 16:32 ` Kirill A. Shutemov 2013-08-07 16:32 ` Kirill A. Shutemov 2013-08-07 20:00 ` Jan Kara 2013-08-07 20:00 ` Jan Kara 2013-08-07 20:24 ` Kirill A. Shutemov 2013-08-07 20:24 ` Kirill A. Shutemov 2013-08-07 20:24 ` Kirill A. Shutemov 2013-08-07 20:36 ` Jan Kara 2013-08-07 20:36 ` Jan Kara 2013-08-07 21:37 ` Kirill A. Shutemov 2013-08-07 21:37 ` Kirill A. Shutemov 2013-08-07 21:37 ` Kirill A. Shutemov 2013-08-08 8:45 ` Kirill A. Shutemov 2013-08-08 8:45 ` Kirill A. Shutemov 2013-08-08 8:45 ` Kirill A. Shutemov 2013-08-08 10:04 ` Jan Kara 2013-08-08 10:04 ` Jan Kara 2013-08-09 11:13 ` Kirill A. Shutemov 2013-08-09 11:13 ` Kirill A. Shutemov 2013-08-09 11:13 ` Kirill A. Shutemov 2013-08-09 11:36 ` Jan Kara 2013-08-09 11:36 ` Jan Kara 2013-08-04 2:17 ` [PATCH 02/23] memcg, thp: charge huge cache pages Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-04 8:25 ` Michal Hocko 2013-08-04 8:25 ` Michal Hocko 2013-08-04 2:17 ` [PATCH 03/23] thp: compile-time and sysfs knob for thp pagecache Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-09-05 21:53 ` Ning Qu 2013-09-06 11:33 ` Kirill A. Shutemov 2013-09-06 11:33 ` Kirill A. Shutemov 2013-09-06 11:33 ` Kirill A. Shutemov 2013-09-06 17:14 ` Ning Qu 2013-08-04 2:17 ` [PATCH 04/23] thp, mm: introduce mapping_can_have_hugepages() predicate Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-04 2:17 ` [PATCH 05/23] thp: represent file thp pages in meminfo and friends Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-30 22:16 ` Ning Qu 2013-09-02 11:36 ` Kirill A. Shutemov 2013-09-02 11:36 ` Kirill A. Shutemov 2013-09-02 20:05 ` Ning Qu 2013-08-04 2:17 ` [PATCH 06/23] thp, mm: rewrite add_to_page_cache_locked() to support huge pages Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-04 2:17 ` [PATCH 07/23] mm: trace filemap: dump page order Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-04 2:17 ` [PATCH 08/23] block: implement add_bdi_stat() Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-05 11:21 ` Jan Kara 2013-08-05 11:21 ` Jan Kara 2013-08-04 2:17 ` [PATCH 09/23] thp, mm: rewrite delete_from_page_cache() to support huge pages Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-04 2:17 ` [PATCH 10/23] thp, mm: warn if we try to use replace_page_cache_page() with THP Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-04 2:17 ` [PATCH 11/23] thp, mm: handle tail pages in page_cache_get_speculative() Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-04 2:17 ` [PATCH 12/23] thp, mm: add event counters for huge page alloc on file write or read Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-04 2:17 ` [PATCH 13/23] thp, mm: allocate huge pages in grab_cache_page_write_begin() Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-04 2:17 ` [PATCH 14/23] thp, mm: naive support of thp in generic_perform_write Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-04 2:17 ` [PATCH 15/23] mm, fs: avoid page allocation beyond i_size on read Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-05 0:29 ` NeilBrown 2013-08-05 0:29 ` NeilBrown 2013-08-04 2:17 ` [PATCH 16/23] thp, mm: handle transhuge pages in do_generic_file_read() Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-04 2:17 ` [PATCH 17/23] thp, libfs: initial thp support Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-04 2:17 ` [PATCH 18/23] thp: libfs: introduce simple_thp_release() Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-04 2:17 ` [PATCH 19/23] truncate: support huge pages Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-05 13:29 ` Jan Kara 2013-08-05 13:29 ` Jan Kara 2013-08-06 20:23 ` Dave Hansen 2013-08-06 20:23 ` Dave Hansen 2013-08-06 20:57 ` Kirill A. Shutemov 2013-08-06 20:57 ` Kirill A. Shutemov 2013-08-06 21:55 ` Dave Hansen 2013-08-06 21:55 ` Dave Hansen 2013-08-09 14:39 ` Kirill A. Shutemov 2013-08-09 14:39 ` Kirill A. Shutemov 2013-08-09 14:39 ` Kirill A. Shutemov 2013-08-04 2:17 ` [PATCH 20/23] thp: handle file pages in split_huge_page() Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-06 19:09 ` Ning Qu 2013-08-06 21:09 ` Ning Qu 2013-08-06 21:47 ` Ning Qu 2013-08-09 14:46 ` Kirill A. Shutemov 2013-08-09 14:46 ` Kirill A. Shutemov 2013-08-09 14:46 ` Kirill A. Shutemov 2013-08-09 14:49 ` Ning Qu 2013-08-09 21:24 ` Ning Qu 2013-08-09 21:24 ` Ning Qu 2013-08-04 2:17 ` [PATCH 21/23] thp: wait_split_huge_page(): serialize over i_mmap_mutex too Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-04 2:17 ` [PATCH 22/23] thp, mm: split huge page on mmap file page Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov 2013-08-08 20:49 ` Khalid Aziz 2013-08-08 20:49 ` Khalid Aziz 2013-08-09 14:50 ` Kirill A. Shutemov 2013-08-09 14:50 ` Kirill A. Shutemov 2013-08-04 2:17 ` [PATCH 23/23] ramfs: enable transparent huge page cache Kirill A. Shutemov 2013-08-04 2:17 ` Kirill A. Shutemov
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20130805111739.GA25691@quack.suse.cz \ --to=jack@suse.cz \ --cc=aarcange@redhat.com \ --cc=ak@linux.intel.com \ --cc=akpm@linux-foundation.org \ --cc=dave@sr71.net \ --cc=dhillf@gmail.com \ --cc=fengguang.wu@intel.com \ --cc=hughd@google.com \ --cc=kirill.shutemov@linux.intel.com \ --cc=kirill@shutemov.name \ --cc=linux-fsdevel@vger.kernel.org \ --cc=linux-kernel@vger.kernel.org \ --cc=linux-mm@kvack.org \ --cc=mgorman@suse.de \ --cc=quning@google.com \ --cc=viro@zeniv.linux.org.uk \ --cc=willy@linux.intel.com \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.