/proc reliability & performance

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.

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

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

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.

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

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.

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

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 <[email protected]>

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

-- wli

From: "Larry McVoy" <[email protected]>

thousand

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

On Thu, October 16, 2003 at 9:31 pm, Albert Cahalan sent the following

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

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....

From: "David S. Miller" <[email protected]>

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

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

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

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