lkml.org 
[lkml]   [2003]   [Mar]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
Subject[RFC] O(1) proc_pid_readdir
Below is a proposal to get rid of the quadratic behaviour of 
proc_pid_readir(): Instead of storing the task number in f_pos and walking
tasks by tasklist order, the pid is stored in f_pos and the tasks are
walked by (hash-mangled) pid order.

--
Manfred
<<
// $Header$
// Kernel Version:
// VERSION = 2
// PATCHLEVEL = 5
// SUBLEVEL = 64
// EXTRAVERSION = -ac4
--- 2.5/include/linux/sched.h 2003-02-26 19:08:43.000000000 +0100
+++ build-2.5/include/linux/sched.h 2003-03-16 13:47:59.000000000 +0100
@@ -507,6 +507,7 @@

extern struct mm_struct init_mm;

+extern int find_next_pid(int pid);
extern struct task_struct *find_task_by_pid(int pid);
extern void set_special_pids(pid_t session, pid_t pgrp);
extern void __set_special_pids(pid_t session, pid_t pgrp);
--- 2.5/kernel/pid.c 2003-01-15 20:30:27.000000000 +0100
+++ build-2.5/kernel/pid.c 2003-03-16 15:41:43.000000000 +0100
@@ -172,13 +172,22 @@
if (pid)
atomic_inc(&pid->count);
else {
+ struct list_head *elem, *bucket;
+
pid = &task->pids[type].pid;
pid->nr = nr;
atomic_set(&pid->count, 1);
INIT_LIST_HEAD(&pid->task_list);
pid->task = task;
get_task_struct(task);
- list_add(&pid->hash_chain, &pid_hash[type][pid_hashfn(nr)]);
+ bucket = &pid_hash[type][pid_hashfn(nr)];
+ __list_for_each(elem, bucket) {
+ struct pid *walk;
+ walk = list_entry(elem, struct pid, hash_chain);
+ if (walk->nr > nr)
+ break;
+ }
+ list_add_tail(&pid->hash_chain, elem);
}
list_add_tail(&task->pids[type].pid_chain, &pid->task_list);
task->pids[type].pidptr = pid;
@@ -221,6 +230,42 @@
free_pidmap(nr);
}

+/**
+ * find_next_pid - Returns the pid of next task.
+ * @pid: Starting point for the search.
+ *
+ * Returns the pid number of the task that follows behind
+ * "pid". The function works even if the input pid value
+ * is not valid anymore.
+ */
+ int find_next_pid(int pid)
+{
+ struct list_head *elem, *bucket;
+
+ if(!pid) {
+ bucket = &pid_hash[PIDTYPE_PID][0];
+ } else {
+ bucket = &pid_hash[PIDTYPE_PID][pid_hashfn(pid)];
+ }
+ read_lock(&tasklist_lock);
+next_chain:
+ __list_for_each(elem, bucket) {
+ struct pid *walk;
+ walk = list_entry(elem, struct pid, hash_chain);
+ if (walk->nr > pid) {
+ pid = walk->nr;
+ read_unlock(&tasklist_lock);
+ return pid;
+ }
+ }
+ pid = 0;
+ bucket++;
+ if (bucket < &pid_hash[PIDTYPE_PID][1<<pidhash_shift])
+ goto next_chain;
+ read_unlock(&tasklist_lock);
+ return -1;
+}
+
task_t *find_task_by_pid(int nr)
{
struct pid *pid = find_pid(PIDTYPE_PID, nr);
--- 2.5/fs/proc/base.c 2003-02-21 17:53:10.000000000 +0100
+++ build-2.5/fs/proc/base.c 2003-03-16 15:40:20.000000000 +0100
@@ -1148,62 +1148,37 @@
}

#define PROC_NUMBUF 10
-#define PROC_MAXPIDS 20
-
-/*
- * Get a few pid's to return for filldir - we need to hold the
- * tasklist lock while doing this, and we must release it before
- * we actually do the filldir itself, so we use a temp buffer..
- */
-static int get_pid_list(int index, unsigned int *pids)
-{
- struct task_struct *p;
- int nr_pids = 0;
-
- index--;
- read_lock(&tasklist_lock);
- for_each_process(p) {
- int pid = p->pid;
- if (!pid)
- continue;
- if (--index >= 0)
- continue;
- pids[nr_pids] = pid;
- nr_pids++;
- if (nr_pids >= PROC_MAXPIDS)
- break;
- }
- read_unlock(&tasklist_lock);
- return nr_pids;
-}

int proc_pid_readdir(struct file * filp, void * dirent, filldir_t filldir)
{
- unsigned int pid_array[PROC_MAXPIDS];
char buf[PROC_NUMBUF];
unsigned int nr = filp->f_pos - FIRST_PROCESS_ENTRY;
- unsigned int nr_pids, i;
+ int pid;

if (!nr) {
ino_t ino = fake_ino(0,PROC_PID_INO);
if (filldir(dirent, "self", 4, filp->f_pos, ino, DT_LNK) < 0)
return 0;
filp->f_pos++;
- nr++;
+ nr = 1;
}
+ pid = nr - 1;
+ for (;;) {
+ unsigned long i, j;
+ ino_t ino;

- nr_pids = get_pid_list(nr, pid_array);
-
- for (i = 0; i < nr_pids; i++) {
- int pid = pid_array[i];
- ino_t ino = fake_ino(pid,PROC_PID_INO);
- unsigned long j = PROC_NUMBUF;
+ pid = find_next_pid(pid);
+ if (pid < 0)
+ break;

- do buf[--j] = '0' + (pid % 10); while (pid/=10);
+ i = pid;
+ j = PROC_NUMBUF;
+ do buf[--j] = '0' + (i % 10); while (i/=10);

+ ino = fake_ino(pid,PROC_PID_INO);
if (filldir(dirent, buf+j, PROC_NUMBUF-j, filp->f_pos, ino, DT_DIR) < 0)
break;
- filp->f_pos++;
+ filp->f_pos = pid + 1 + FIRST_PROCESS_ENTRY;
}
return 0;
}
<<
-
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/

\
 
 \ /
  Last update: 2005-03-22 13:34    [W:0.093 / U:1.700 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site