linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* Re: Fwd: [Lse-tech] get_pid() performance fix
@ 2002-03-05 16:43 Rajan Ravindran
  2002-03-05 17:57 ` OGAWA Hirofumi
  2002-03-14 23:18 ` [PATCH] " Hubertus Franke
  0 siblings, 2 replies; 28+ messages in thread
From: Rajan Ravindran @ 2002-03-05 16:43 UTC (permalink / raw)
  To: OGAWA Hirofumi; +Cc: linux-kernel, lse-tech



Yes, pid's are guaranteed to be unique.
Here the problem we focused is the time taken in finding the next
available free pid.
I really don't mean by your task->xxx.

-Rajan



Hubertus Franke <frankeh@watson.ibm.com> writes:

> @@ -153,13 +155,18 @@
>                               if(last_pid & 0xffff8000)
>                                     last_pid = 300;
>                               next_safe = PID_MAX;
> +                             goto repeat;
>                         }
> -                       goto repeat;
> +                       if(unlikely(last_pid == beginpid))
> +                             goto nomorepids;
> +                       continue;

It isn't guaranteed that pid is unique.

In the case:
             task->pid = 300, task->xxx = 301
             pid 301 is free

             This get_pid() returns 301.

Regards.
--
OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>

_______________________________________________
Lse-tech mailing list
Lse-tech@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/lse-tech





^ permalink raw reply	[flat|nested] 28+ messages in thread
* Re: Fwd: [Lse-tech] get_pid() performance fix
@ 2002-03-07 22:37 Manfred Spraul
  0 siblings, 0 replies; 28+ messages in thread
From: Manfred Spraul @ 2002-03-07 22:37 UTC (permalink / raw)
  To: Guest section DW, linux-kernel

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

> Maybe Alan will mutter something about sysvipc.
> Roughly speaking there are only advantages, especially since
> I think we'll have to do this sooner or later, and in such cases
> sooner is better.

The sysvipc situation isn't that bad. The new interfaces added for
32-bit uids also contain 32-bit pid values.
The semaphore code contains a stupid hack that assumes 16-bit uids,
appart from that apps linked against new glibc version should run fine.

[patch vs. 2.5.6-pre2 attached, but untested].

--
	Manfred

[-- Attachment #2: patch-sem --]
[-- Type: text/plain, Size: 1853 bytes --]

--- 2.5/ipc/sem.c	Sun Mar  3 12:04:00 2002
+++ build-2.5/ipc/sem.c	Thu Mar  7 23:33:02 2002
@@ -251,39 +251,39 @@
 	for (sop = sops; sop < sops + nsops; sop++) {
 		curr = sma->sem_base + sop->sem_num;
 		sem_op = sop->sem_op;
-
-		if (!sem_op && curr->semval)
+		result = curr->semval;
+  
+		if (!sem_op && result)
 			goto would_block;
 
-		curr->sempid = (curr->sempid << 16) | pid;
-		curr->semval += sem_op;
-		if (sop->sem_flg & SEM_UNDO)
-		{
+		result += sem_op;
+		if (result < 0)
+			goto would_block;
+		if (result > SEMVMX)
+			goto out_of_range;
+		if (sop->sem_flg & SEM_UNDO) {
 			int undo = un->semadj[sop->sem_num] - sem_op;
 			/*
 	 		 *	Exceeding the undo range is an error.
 			 */
 			if (undo < (-SEMAEM - 1) || undo > SEMAEM)
-			{
-				/* Don't undo the undo */
-				sop->sem_flg &= ~SEM_UNDO;
 				goto out_of_range;
-			}
-			un->semadj[sop->sem_num] = undo;
 		}
-		if (curr->semval < 0)
-			goto would_block;
-		if (curr->semval > SEMVMX)
-			goto out_of_range;
+		curr->semval = result;
 	}
 
-	if (do_undo)
-	{
-		sop--;
+	if (do_undo) {
 		result = 0;
 		goto undo;
 	}
-
+	sop--;
+	while (sop >= sops) {
+		sma->sem_base[sop->sem_num].sempid = pid;
+		if (sop->sem_flg & SEM_UNDO)
+			un->semadj[sop->sem_num] -= sop->sem_op;
+		sop--;
+	}
+	
 	sma->sem_otime = CURRENT_TIME;
 	return 0;
 
@@ -298,13 +298,9 @@
 		result = 1;
 
 undo:
+	sop--;
 	while (sop >= sops) {
-		curr = sma->sem_base + sop->sem_num;
-		curr->semval -= sop->sem_op;
-		curr->sempid >>= 16;
-
-		if (sop->sem_flg & SEM_UNDO)
-			un->semadj[sop->sem_num] += sop->sem_op;
+		sma->sem_base[sop->sem_num].semval -= sop->sem_op;
 		sop--;
 	}
 
@@ -624,7 +620,7 @@
 		err = curr->semval;
 		goto out_unlock;
 	case GETPID:
-		err = curr->sempid & 0xffff;
+		err = curr->sempid;
 		goto out_unlock;
 	case GETNCNT:
 		err = count_semncnt(sma,semnum);

^ permalink raw reply	[flat|nested] 28+ messages in thread
* Fwd: [Lse-tech] get_pid() performance fix
@ 2002-03-05  1:57 Hubertus Franke
  2002-03-05 16:26 ` OGAWA Hirofumi
  2002-03-07  3:56 ` Rusty Russell
  0 siblings, 2 replies; 28+ messages in thread
From: Hubertus Franke @ 2002-03-05  1:57 UTC (permalink / raw)
  To: linux-kernel, lse-tech

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


Can somebody post why this patch shouldn't be picked up ?
The attached program shows the problem in user space 
and the patch is almost trivial ..

-- Hubertus

----------  Forwarded Message  ----------

Subject: [Lse-tech] get_pid() performance fix
Date: Tue, 26 Feb 2002 18:58:51 -0500
From: "Rajan Ravindran" <rajancr@us.ibm.com>
To: lse-tech@lists.sourceforge.net
Cc: linux-kernel@vger.kernel.org, davej@suse.de

Paul Larson posted a patch which fixes the get_pid() hang,
if we run out of available pids. Nevertheless, we have
observed that it takes a long time to find the next available
pid once the last pid reaches the PID_MAX. This is due to
a constant rescan of the task list while progressing only one
pid at time, yielding an O(n**2) problem.
Here is a patch (together with Paul's fix) which eliminates the
time taken to search for an available pid, by not constantly
restarting the search through the entire task list.

Attached is also a user level test program getpid.c),
by which one can simulate creation and deletion of processes.
This application will measure the time taken for the get_pid()
routine to find the next available process.

example:
      getpid -p 32770 -n 3

which will try to create 32770 process, eventually get_pid can't
find any free pid after 32767, so it will delete 3 pids randomly
from the existing list and start calculating the time taken to
find the available pid (which we deleted).

In getpid.c the new fixes  are inside the #define NEW_METHOD.
Try compiling the getpid.c with and without -DNEW_METHOD compile
option to see the performance improvement.

here is an example output for the old and the new algorithm and
their respective execution time to find a new pid.

(See attached file: output)

This can/should be applied to 2.5 and 2.4 kernels.


(See attached file: getpid.c)

Thanks,
Rajan


diff -Naur linux-2.5.5/kernel/fork.c linux-2.5.5-new/kernel/fork.c
--- linux-2.5.5/kernel/fork.c Tue Feb 19 21:10:55 2002
+++ linux-2.5.5-new/kernel/fork.c   Tue Feb 26 15:46:36 2002
@@ -24,6 +24,7 @@
 #include <linux/file.h>
 #include <linux/binfmts.h>
 #include <linux/fs.h>
+#include <linux/compiler.h>

 #include <asm/pgtable.h>
 #include <asm/pgalloc.h>
@@ -129,12 +130,13 @@
 {
      static int next_safe = PID_MAX;
      struct task_struct *p;
-     int pid;
+     int pid, beginpid;

      if (flags & CLONE_PID)
            return current->pid;

      spin_lock(&lastpid_lock);
+     beginpid = last_pid;
      if((++last_pid) & 0xffff8000) {
            last_pid = 300;         /* Skip daemons etc. */
            goto inside;
@@ -153,13 +155,18 @@
                              if(last_pid & 0xffff8000)
                                    last_pid = 300;
                              next_safe = PID_MAX;
+                             goto repeat;
                        }
-                       goto repeat;
+                       if(unlikely(last_pid == beginpid))
+                             goto nomorepids;
+                       continue;
                  }
                  if(p->pid > last_pid && next_safe > p->pid)
                        next_safe = p->pid;
                  if(p->pgrp > last_pid && next_safe > p->pgrp)
                        next_safe = p->pgrp;
+                 if(p->tgid > last_pid && next_safe > p->tgid)
+                       next_safe = p->tgid;
                  if(p->session > last_pid && next_safe > p->session)
                        next_safe = p->session;
            }
@@ -169,6 +176,11 @@
      spin_unlock(&lastpid_lock);

      return pid;
+
+nomorepids:
+     read_unlock(&tasklist_lock);
+     spin_unlock(&lastpid_lock);
+     return 0;
 }

 static inline int dup_mmap(struct mm_struct * mm)
@@ -667,6 +679,8 @@

      copy_flags(clone_flags, p);
      p->pid = get_pid(clone_flags);
+     if (p->pid == 0 && current->pid != 0)
+           goto bad_fork_cleanup;

      INIT_LIST_HEAD(&p->run_list);

-------------------------------------------------------



-- 
-- Hubertus Franke  (frankeh@watson.ibm.com)

[-- Attachment #2: output --]
[-- Type: application/octet-stream, Size: 1014 bytes --]

./getpid -p 32771 -n 4 

Output when compiled without -DNEW_METHOD
-----------------------------------------
nprocs: 32771, ndelete:0, nitems:4
start creating 32771 processes
reached max pid <32768> reset last_pid to <300>
removed pid: <17767>
removed pid: <9158>
removed pid: <6249>
removed pid: <18547>
spent 1.172945 seconds in finding free pid <6249>
spent 2.519057 seconds in finding free pid <9158>
spent 9.857908 seconds in finding free pid <17767>
spent 10.924213 seconds in finding free pid <18547>


Output when compiled with -DNEW_METHOD
--------------------------------------
nprocs: 32771, ndelete:0, nitems:4
start creating 32771 processes
reached max pid <32768> reset last_pid to <300>
removed pid: <17767>
removed pid: <9158>
spent 0.18468 seconds in finding free pid <17767>
removed pid: <6249>
removed pid: <18547>
spent 0.30833 seconds in finding free pid <6249>
spent 0.34572 seconds in finding free pid <9158>
spent 0.41594 seconds in finding free pid <18547>


[-- Attachment #3: getpid.c --]
[-- Type: application/octet-stream, Size: 4613 bytes --]

/* 
 * Program to measure the get_pid() function performance
 *
 */

#include <stdio.h>
#include <errno.h>
#include <sched.h>
#include <sys/types.h>
#include <sys/wait.h>         
#include <sys/time.h>         
#include <getopt.h>
#include <stdlib.h>

struct task_struct {
	int pid;
	struct task_struct *next_task;
};	

#define PID_MAX	0x8000
#define GETPID_MASK	0xffff8000
#define STACK_SIZE	8192

struct task_struct *tsk_head;
int last_pid;
unsigned long nprocs;
int verbose;
int start_del;

#define alloc_task_struct() \
	((struct task_struct *)malloc(sizeof(struct task_struct)))
#define for_each_task(p) \
        for (p = tsk_head ; (p = p->next_task) != tsk_head ; ) 

int create_task();
int (*ctask) (void *arg);

int __clone (int (*fn) (void *arg), void *thread_stack, int flags, void *arg); 

int get_pid()
{
	static int next_safe = PID_MAX;
	struct task_struct *p;
	static struct timeval stime, etime;
	static int start_search=0;
	int beginpid;
	long sec,usec;

	beginpid = last_pid;
	if((++last_pid) & GETPID_MASK) {
		printf("reached max pid <%d> reset last_pid to <300>\n", last_pid);
		last_pid = 300;		/* Skip daemons etc. */
		start_del = start_search =1;
        	gettimeofday(&stime, (struct timezone *) 0);   
		goto inside;
	}

#ifdef NEW_METHOD
	if(last_pid >= next_safe) {
inside:
		next_safe = PID_MAX;
	repeat:
       		for (p = tsk_head ; (p = p->next_task) != tsk_head ; ) {
			if(p->pid == last_pid) {
				if(++last_pid >= next_safe) {
					if(last_pid & GETPID_MASK)
					last_pid = 300;
					next_safe = PID_MAX;
					goto repeat;
				}
				continue;
			}
			if(p->pid > last_pid && next_safe > p->pid)
				next_safe = p->pid;
		}
	}
#else
	if(last_pid >= next_safe) {
inside:
		next_safe = PID_MAX;
	repeat:
       		for (p = tsk_head ; (p = p->next_task) != tsk_head ; ) {
			if(p->pid == last_pid) {
				if(++last_pid >= next_safe) {
					if(last_pid & GETPID_MASK)
						last_pid = 300;
					next_safe = PID_MAX;
				}
				goto repeat;
			}
		if(p->pid > last_pid && next_safe > p->pid)
				next_safe = p->pid;
		}
	}
#endif
	if (start_search) {
        	gettimeofday(&etime, (struct timezone *) 0);  
		if ((etime.tv_usec - stime.tv_usec) < 0) {
			sec = (etime.tv_sec - stime.tv_sec) -1;
			usec = stime.tv_usec - etime.tv_usec;
		}
		else {
			sec = (etime.tv_sec - stime.tv_sec);
			usec = etime.tv_usec - stime.tv_usec;
		}
		printf("spent %d.%02d seconds in finding free pid <%d>\n",
                                        sec, usec, last_pid);
	}
	return last_pid;
}

int create_task() {
	struct task_struct *p, *prev;
	unsigned int i;

	prev = tsk_head;
	tsk_head->pid = 0; tsk_head->next_task = tsk_head;
	printf("start creating %d processes\n", nprocs);
	for (i=0; i<nprocs; i++) {
		p = alloc_task_struct();
		p->next_task = tsk_head;
		p->pid = get_pid();
		if (verbose)
			printf("created <%d>\n", p->pid);
		prev->next_task = p;
		prev = prev->next_task;
	}
}

void delete_task(int nitems) {
	struct task_struct *p, *prev;
	unsigned int i;
	long int rand;

	while (!start_del);
	for (i=0; i < nitems; i++) {
		rand = random() % PID_MAX;
        	for (prev = p = tsk_head ; (p = p->next_task) != tsk_head ; ) { 
			if (p->pid == rand) {
				prev->next_task = p->next_task;
				printf("removed pid: <%d>\n", rand);
			}
			prev = p;
		}
	}
	start_del=0;	
}

void usage() {
	printf("Usage: getpid -p <nprocs> -n <npids> -s <seed> -v [verbose]\n");
	printf("       nprocs: number of process to create\n");
	printf("       npids: number of process to delete\n");
	printf("       verbose: print debug strings\n");
}

int main(int argc, char *argv[]) {
	int pid;
	char *stk;
	int wait_status, rc;
	int c, nitems=0;

        while ((c = getopt(argc, argv, "p:s:n:v:")) != -1) {
          switch(c) {
                case 'p': nprocs = atoi(optarg); break;
                case 'n': nitems = atoi(optarg); break;
		case 's': srand(atoi(optarg)); break;
                case 'v': verbose = 1; break;
                default: usage(); return 0;
          }
        }

	if ((nprocs == 0) || (nitems > PID_MAX)) {
		printf("Invalid parameter\n");
		usage();
		return 0;
	}
	tsk_head = alloc_task_struct();
	stk = (char *)malloc(2 * STACK_SIZE);

	ctask = create_task;
	pid = __clone(ctask, &stk[STACK_SIZE],  CLONE_VM | CLONE_FS | CLONE_SIGHAND, (void *)0);
	if (pid == -1)
		printf("errno=%d <%s>\n", errno,strerror(errno));
	
	delete_task(nitems);
	waitpid(-1, &wait_status, __WCLONE);
}

^ permalink raw reply	[flat|nested] 28+ messages in thread
end of thread, other threads:[~2002-03-22 22:26 UTC | newest]

Thread overview: 28+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2002-03-05 16:43 Fwd: [Lse-tech] get_pid() performance fix Rajan Ravindran
2002-03-05 17:57 ` OGAWA Hirofumi
2002-03-05 19:53   ` Hubertus Franke
2002-03-05 20:10     ` OGAWA Hirofumi
2002-03-05 21:59       ` Hubertus Franke
2002-03-05 22:48         ` OGAWA Hirofumi
2002-03-05 23:40           ` Hubertus Franke
2002-03-14 23:18 ` [PATCH] " Hubertus Franke
2002-03-15 14:57   ` OGAWA Hirofumi
2002-03-15 15:16   ` OGAWA Hirofumi
2002-03-15 18:37     ` Hubertus Franke
2002-03-16  5:12       ` OGAWA Hirofumi
2002-03-18 21:44         ` Hubertus Franke
2002-03-22 22:14         ` Hubertus Franke
2002-03-22 22:28           ` Davide Libenzi
2002-03-22 22:26             ` Hubertus Franke
  -- strict thread matches above, loose matches on Subject: below --
2002-03-07 22:37 Fwd: [Lse-tech] " Manfred Spraul
2002-03-05  1:57 Hubertus Franke
2002-03-05 16:26 ` OGAWA Hirofumi
2002-03-05 16:43   ` Hubertus Franke
2002-03-07  3:56 ` Rusty Russell
2002-03-07 14:35   ` Hubertus Franke
2002-03-07 14:54     ` Guest section DW
2002-03-07 19:07       ` Hubertus Franke
2002-03-07 19:44         ` Richard B. Johnson
2002-03-07 19:46         ` Guest section DW
2002-03-07 23:14           ` Hubertus Franke
2002-03-07 15:21   ` Dave McCracken

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).