Re: /proc reliability & performance

[William Lee Irwin III <wli@holomorphy.com>]

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