/proc reliability & performance

/proc reliability & performance

[Albert Cahalan]

I created a process with 360 thousand threads,
went into the /proc/*/task directory, and did
a simple /bin/ls. It took over 9 minutes on a
nice fast Opteron. (it's the same at top-level
with processes, but I wasn't about to mess up
my system that much)

OK, that's a bit extreme, but it does show a
scalability problem. There is an O(n*n)
algorithm in there. Here is a proposed fix:

Tie directory readers to a task_struct (or to
some of the PID tracking structs), so that
a directory reader is on a list. When a task
exits, move the list of directory readers on
to a neighboring task.

That is O(1) on task exit, and generally O(n)
for the whole /proc or /proc/42/task read.
It's O(1) per step of the read, excepting
where multiple directory readers wind up at
the same location.

Another benefit is that it is reliable as
long as tasks don't move around on the lists.
Each task will appear at most once, and will
appear exactly once if it doesn't start or
exit during the directory scan.

Re: /proc reliability & performance

[Larry McVoy]

On Thu, Oct 16, 2003 at 10:07:18PM -0400, Albert Cahalan wrote:
> I created a process with 360 thousand threads,

And your real need for 360,000 threads is?

I tend to believe that there are hundreds, nay, thousands, nay, 360 thousand
better things to work on in the kernel.
-- 
---
Larry McVoy              lm at bitmover.com          http://www.bitmover.com/lm

Re: /proc reliability & performance

[William Lee Irwin III]

On Thu, Oct 16, 2003 at 10:07:18PM -0400, Albert Cahalan wrote:
> Tie directory readers to a task_struct (or to
> some of the PID tracking structs), so that
> a directory reader is on a list. When a task
> exits, move the list of directory readers on
> to a neighboring task.
> That is O(1) on task exit, and generally O(n)
> for the whole /proc or /proc/42/task read.
> It's O(1) per step of the read, excepting
> where multiple directory readers wind up at
> the same location.
> Another benefit is that it is reliable as
> long as tasks don't move around on the lists.
> Each task will appear at most once, and will
> appear exactly once if it doesn't start or
> exit during the directory scan.

Several other things have been tried.
(a) something mingo wrote I forgot the nature of
(b) a thing manfred wrote that recovers positions in hashtable
	collision chains by sorting them, with O(chain length)
	insertion
(c) a thing I wrote that turns the tasklist and pid_chains into
	rbtrees and uses the last-seen pid to seek in O(lg(n))
	time, and uses a routine to seek and fill buffers as a
	drop-in replacement for get_tgid_list()/get_tid_list().

I have a current implementation of (c), as well as a patch to
restore 2.4 semantics to proc_pid_statm() in O(1) time.


-- wli

Re: /proc reliability & performance

[Brian McGroarty]

[-- Attachment #1: Type: text/plain, Size: 544 bytes --]

On Thu, Oct 16, 2003 at 10:07:18PM -0400, Albert Cahalan wrote:
> I created a process with 360 thousand threads,
> went into the /proc/*/task directory, and did
> a simple /bin/ls. It took over 9 minutes on a
> nice fast Opteron. (it's the same at top-level
> with processes, but I wasn't about to mess up
> my system that much)

Are there many cases where the /proc directory contents are read in
this fashion?

I'd be more curious about how performance fares with reading a
thousand entries by name with 1k processes and with 360k processes.

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: /proc reliability & performance

[Albert Cahalan]

On Thu, 2003-10-16 at 23:24, Brian McGroarty wrote:
> On Thu, Oct 16, 2003 at 10:07:18PM -0400, Albert Cahalan wrote:
> > I created a process with 360 thousand threads,
> > went into the /proc/*/task directory, and did
> > a simple /bin/ls. It took over 9 minutes on a
> > nice fast Opteron. (it's the same at top-level
> > with processes, but I wasn't about to mess up
> > my system that much)
> 
> Are there many cases where the /proc directory
> contents are read in this fashion?

Sure. Run any of: top, ps, lsof, fuser...

> I'd be more curious about how performance fares
> with reading a thousand entries by name with 1k
> processes and with 360k processes.

Judging by the crazy example and the observation
that an O(n*n) algorithm is involved, directory
reads on that very fast machine should get annoying
once you have a few thousand processes. They'd be
perceptable one-by-one, which adds up when you have
multiple reads due to scripts, top, or multiple
users.

Anyway, it's not just about performance! That's
only half of the problem. The other half is
reliability. The way /proc works is this:

Count tasks as you read them. The number is
your directory offset. Return a few dozen entries
at a time. For each read, you'll need to find
back your place. You do this by counting tasks
until you reach your offset. Of course, tasks
will have been created and destroyed between
reads, so who knows where you'll continue from?

That's simply not reliable.

Re: /proc reliability & performance

[William Lee Irwin III]

On Fri, Oct 17, 2003 at 12:31:14AM -0400, Albert Cahalan wrote:
> Count tasks as you read them. The number is
> your directory offset. Return a few dozen entries
> at a time. For each read, you'll need to find
> back your place. You do this by counting tasks
> until you reach your offset. Of course, tasks
> will have been created and destroyed between
> reads, so who knows where you'll continue from?
> That's simply not reliable.

That's part of what the rbtree algorithm was meant to address.
It does find_tgids_after(tgids, tgid_array), filling a buffer with the
tgids starting at the first one higher than its first argument. This
way there is no possibility whatsoever of duplicates or deviation from
sorted order.


-- wli

Re: /proc reliability & performance

[Zan Lynx]

[-- Attachment #1: Type: text/plain, Size: 432 bytes --]

On Thu, 2003-10-16 at 20:07, Albert Cahalan wrote:
> I created a process with 360 thousand threads,
> went into the /proc/*/task directory, and did
> a simple /bin/ls. It took over 9 minutes on a
> nice fast Opteron.

Did you try using find instead of ls?  ls loads all entries and then
sorts them, so it can create an alphabetical display.

Try using find.  It will not take quite so long.
-- 
Zan Lynx <zlynx@acm.org>

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: /proc reliability & performance

[William Lee Irwin III]

On Thu, 2003-10-16 at 20:07, Albert Cahalan wrote:
>> I created a process with 360 thousand threads,
>> went into the /proc/*/task directory, and did
>> a simple /bin/ls. It took over 9 minutes on a
>> nice fast Opteron.

On Fri, Oct 17, 2003 at 01:40:03AM -0600, Zan Lynx wrote:
> Did you try using find instead of ls?  ls loads all entries and then
> sorts them, so it can create an alphabetical display.
> Try using find.  It will not take quite so long.

GNU ls has a -U flag that should come in handy.


-- wli

Re: /proc reliability & performance

[dada1]

From: "Larry McVoy" <lm@bitmover.com>
>
> And your real need for 360,000 threads is?
>
> I tend to believe that there are hundreds, nay, thousands, nay, 360
thousand
> better things to work on in the kernel.

Same problem here on some servers (real application), but with 280.000 tcp
sockets active.

A "cat /proc/net/tcp" takes too much time to even try it. :(

tools like "netstat" or "lsof", (even with -n flag) are just unusable.

Eric Dumazet

Re: /proc reliability & performance

[David Rees]

On Thu, October 16, 2003 at 9:31 pm, Albert Cahalan sent the following
> On Thu, 2003-10-16 at 23:24, Brian McGroarty wrote:
>> On Thu, Oct 16, 2003 at 10:07:18PM -0400, Albert Cahalan wrote:
>> > I created a process with 360 thousand threads,
>> > went into the /proc/*/task directory, and did
>> > a simple /bin/ls. It took over 9 minutes on a
>> > nice fast Opteron. (it's the same at top-level
>> > with processes, but I wasn't about to mess up
>> > my system that much)
>>
>> Are there many cases where the /proc directory
>> contents are read in this fashion?
>
> Sure. Run any of: top, ps, lsof, fuser...

I can vouch that with as few as a 3-5 hundred threads/processes started up
and not necessarily doing much, top starts using a good deal system time
on a somewhat aging dual PIII server on recent 2.4.x kernels.

-Dave

Re: /proc reliability & performance

[David S. Miller]

On Fri, 17 Oct 2003 10:01:53 +0200
"dada1" <dada1@cosmosbay.com> wrote:

> A "cat /proc/net/tcp" takes too much time to even try it. :(
> 
> tools like "netstat" or "lsof", (even with -n flag) are just unusable.

Because they don't use the netlink TCP socket dumping
facility which is made to handle such things much better
than procfs ever can.

Re: /proc reliability & performance

[Valdis.Kletnieks]

[-- Attachment #1: Type: text/plain, Size: 433 bytes --]

On Fri, 17 Oct 2003 02:10:40 PDT, "David S. Miller" said:

> > tools like "netstat" or "lsof", (even with -n flag) are just unusable.
> 
> Because they don't use the netlink TCP socket dumping
> facility which is made to handle such things much better
> than procfs ever can.

The netlink TCP socked dumping facility will also provide the
"open files" list of *non* sockets that lsof wants?

Not all the world's a TCP connection....

[-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --]

Re: /proc reliability & performance

[dada1]

From: "David S. Miller" <davem@redhat.com>
> "dada1" <dada1@cosmosbay.com> wrote:
>
> > A "cat /proc/net/tcp" takes too much time to even try it. :(
> >
> > tools like "netstat" or "lsof", (even with -n flag) are just unusable.
>
> Because they don't use the netlink TCP socket dumping
> facility which is made to handle such things much better
> than procfs ever can.

Thanks David for the hint. :) I buy it.

I found that the ss command from iproute2 package does use the 'netlink TCP
dumping' you mention (how many people on earth heard about that ?)

Instead of 15 minutes for a 'netstat -n > FILE', my server takes now 6
seconds with 'ss -n > FILE', with 200000 sockets opened.

Eric

Re: /proc reliability & performance

[Albert Cahalan]

On Fri, 2003-10-17 at 05:10, David S. Miller wrote:
> On Fri, 17 Oct 2003 10:01:53 +0200
> "dada1" <dada1@cosmosbay.com> wrote:
> 
> > A "cat /proc/net/tcp" takes too much time to even try it. :(
> > 
> > tools like "netstat" or "lsof", (even with -n flag) are just unusable.
> 
> Because they don't use the netlink TCP socket dumping
> facility which is made to handle such things much better
> than procfs ever can.

That's an accepted way to do things? Oh cool.
We just need a netlink process info dumping
facility...

Re: /proc reliability & performance

[Willy Tarreau]

On Fri, Oct 17, 2003 at 02:10:40AM -0700, David S. Miller wrote:
> On Fri, 17 Oct 2003 10:01:53 +0200
> "dada1" <dada1@cosmosbay.com> wrote:
> 
> > A "cat /proc/net/tcp" takes too much time to even try it. :(
> > 
> > tools like "netstat" or "lsof", (even with -n flag) are just unusable.
> 
> Because they don't use the netlink TCP socket dumping
> facility which is made to handle such things much better
> than procfs ever can.

Hmmm very interesting. And is there an equivalent replacement for
/proc/net/ip_conntrack ? And if not, what would be needed to implement it ?

Willy

Re: /proc reliability & performance

[David S. Miller]

On Sat, 18 Oct 2003 08:35:59 +0200
Willy Tarreau <willy@w.ods.org> wrote:

> Hmmm very interesting. And is there an equivalent replacement for
> /proc/net/ip_conntrack ? And if not, what would be needed to implement it ?

I don't know, ask the netfilter developers on the netfilter lists.
:-)