LKML Archive on
help / color / mirror / Atom feed
From: William Lee Irwin III <>
To: David Miller <>
Subject: Re: [rfc][patch] dynamic resizing dentry hash using RCU
Date: Sat, 24 Feb 2007 18:15:34 -0800	[thread overview]
Message-ID: <> (raw)
In-Reply-To: <>

> From: William Lee Irwin III <>
> Date: Sat, 24 Feb 2007 14:56:31 -0800
>> just do it on a per-directory basis so you don't intermix children
>> of different parents in some boot-time -allocated global trainwreck
>> and you're home free.  Benchmarking is probably needed to gauge
>> which performs best.

On Sat, Feb 24, 2007 at 04:56:31PM -0800, David Miller wrote:
> The original dentry implementation in the kernel did things
> per-directory and it sucked.
> The problem you run into is that you end up with recursive algorithms
> all over the place, which chew up and overflow the kernel stack.
> So it would be a regression to go to a per-directory type
> lookup data structure for dentries.

Recursive code is clearly inadmissible in kernel environments. Any
implementations would clearly be required to be coded iteratively.
It's unclear to me where the choice of data structure would make a
demand for recursive code, but wherever it ostensibly does so, an
explicitly-allocated stack (or queue or worklist of whatever sort)
should be able to unravel it. There are furthermore rather stringent
bounds on balanced tree heights due to address space limits, so
whatever explicitly-allocated stacks may be required for e.g. tree
balancing algorithms are tightly bounded in depth.

The usual objection is to lexicographically ordered balanced trees
such as B+ trees on the grounds that string comparison is cache-
intensive. Hash tries resolve that concern, albeit at the amortized
cost of expansion and contraction of what are effectively nodes in
a radix tree with a large radix as well as undoing path compression
where required (speaking of which, lib/radix-tree.c should really do
path compression instead of the ->depth hack). The quest, as I see it,
is for self-sizing data structures with as little restructuring and
direct key (string) comparison as possible. Should the obvious
candidates not incur significant overhead on account of where they
do such, maybe they're good enough.

So I'm not sure what else to say as far as the per-directory lookup
structure commentary goes. There's no way I'd propose putting
recursive code in the kernel. I don't believe any of what I'm talking
about requires such. I'm aware of various drawbacks the algorithms
have, and have in mind that they should pass benchmark criteria in
addition to reducing kernel memory consumption in order to prove that
they don't overwhelm the putative benefits. So I think I've got all the
bases covered.

Am I off-base on any of this? Is there anything I missed?

-- wli

(P.S.: The only time I ever proposed putting something "recursive"
in the kernel, it used a flag to limit the recursion depth to two
stack frames. It was for the purpose of simplifying the reservation
of metadata in an allocator, and so not strictly necessary. A 
simplified metadata allocator could've easily been devised, albeit at
the cost of some code duplication.)

  reply	other threads:[~2007-02-25  2:15 UTC|newest]

Thread overview: 20+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2007-02-23 15:37 Nick Piggin
2007-02-23 16:31 ` Eric Dumazet
2007-02-24  1:08   ` Nick Piggin
2007-02-23 17:25 ` Zach Brown
2007-02-24  1:26   ` Nick Piggin
2007-02-24  2:07     ` Nick Piggin
2007-02-24  1:31   ` Michael K. Edwards
2007-02-24  1:52     ` Nick Piggin
2007-02-24  4:07 ` KAMEZAWA Hiroyuki
2007-02-24  5:15   ` Nick Piggin
2007-02-24  4:24 ` William Lee Irwin III
2007-02-24  5:09   ` Nick Piggin
2007-02-24 22:56     ` William Lee Irwin III
2007-02-25  0:56       ` David Miller
2007-02-25  2:15         ` William Lee Irwin III [this message]
2007-02-25  6:21 ` Paul E. McKenney
2007-03-05  4:11 ` David Miller
2007-03-05  4:27   ` Nick Piggin
2007-03-05  4:38     ` David Miller
2007-03-05  4:42     ` Nick Piggin

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:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \ \ \ \ \ \
    --subject='Re: [rfc][patch] dynamic resizing dentry hash using RCU' \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).