From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail6.bemta12.messagelabs.com (mail6.bemta12.messagelabs.com [216.82.250.247]) by kanga.kvack.org (Postfix) with ESMTP id CB1956B0012 for ; Fri, 17 Jun 2011 20:12:30 -0400 (EDT) Date: Fri, 17 Jun 2011 17:12:28 -0700 From: Randy Dunlap Subject: Re: [PATCH 1/12] radix_tree: exceptional entries and indices Message-Id: <20110617171228.4c85fd38.rdunlap@xenotime.net> In-Reply-To: <20110617170742.282a1bd6.rdunlap@xenotime.net> References: <20110617163854.49225203.akpm@linux-foundation.org> <20110617170742.282a1bd6.rdunlap@xenotime.net> Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: akpm Cc: Hugh Dickins , linux-kernel@vger.kernel.org, linux-mm@kvack.org On Fri, 17 Jun 2011 17:07:42 -0700 Randy Dunlap wrote: > On Fri, 17 Jun 2011 16:38:54 -0700 Andrew Morton wrote: > > > On Tue, 14 Jun 2011 03:42:27 -0700 (PDT) > > Hugh Dickins wrote: > > > > > The radix_tree is used by several subsystems for different purposes. > > > A major use is to store the struct page pointers of a file's pagecache > > > for memory management. But what if mm wanted to store something other > > > than page pointers there too? > > > > > > The low bit of a radix_tree entry is already used to denote an indirect > > > pointer, for internal use, and the unlikely radix_tree_deref_retry() case. > > > Define the next bit as denoting an exceptional entry, and supply inline > > > functions radix_tree_exception() to return non-0 in either unlikely case, > > > and radix_tree_exceptional_entry() to return non-0 in the second case. > > > > > > If a subsystem already uses radix_tree with that bit set, no problem: > > > it does not affect internal workings at all, but is defined for the > > > convenience of those storing well-aligned pointers in the radix_tree. > > > > > > The radix_tree_gang_lookups have an implicit assumption that the caller > > > can deduce the offset of each entry returned e.g. by the page->index of > > > a struct page. But that may not be feasible for some kinds of item to > > > be stored there. > > > > > > radix_tree_gang_lookup_slot() allow for an optional indices argument, > > > output array in which to return those offsets. The same could be added > > > to other radix_tree_gang_lookups, but for now keep it to the only one > > > for which we need it. > > > > Yes, the RADIX_TREE_INDIRECT_PTR hack is internal-use-only, and doesn't > > operate on (and hence doesn't corrupt) client-provided items. > > > > This patch uses bit 1 and uses it against client items, so for > > practical purpoese it can only be used when the client is storing > > addresses. And it needs new APIs to access that flag. > > > > All a bit ugly. Why not just add another tag for this? Or reuse an > > existing tag if the current tags aren't all used for these types of > > pages? > > > And regardless of the patch path that is taken, update test(s) if > applicable. I thought that someone from Red Hat had a kernel loadable > module for testing radix-tree -- or maybe that was for rbtree (?) -- > but I can't find that just now. http://people.redhat.com/jmoyer/radix-tree/ > And one Andrew Morton has a userspace radix tree test harness at > http://userweb.kernel.org/~akpm/stuff/rtth.tar.gz --- ~Randy *** Remember to use Documentation/SubmitChecklist when testing your code *** -- 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/ . Fight unfair telecom internet charges in Canada: sign http://stopthemeter.ca/ Don't email: email@kvack.org