Messages in this thread | | | Date | Thu, 16 Oct 2003 19:51:28 -0700 | From | William Lee Irwin III <> | Subject | Re: /proc reliability & performance |
| |
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 - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |