Re: Fwd: [Lse-tech] get_pid() performance fix

OGAWA Hirofumi
2002-03-05T22:49:44Z

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

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;
> >
> > You changed it. No?
>
> Yes, we changed but only the logic that once a pid is busy we start searching
> for every task again. This is exactly the O(n**2) problem.
> Run the program and you'll see.

Run the attached file.

Result,
new pid: 301, 300: pid 300, pgrp 301

new pid == task(300)->pgrp. This get_pid() has bug.
I'm missing something?
--
OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: get_pid.c --]
[-- Type: text/x-csrc, Size: 3624 bytes --]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <sys/types.h>

#define spin_lock(x)
#define spin_unlock(x)
#define read_lock(x)
#define read_unlock(x)
#define unlikely(x) (x)
#define SET_LINKS(p) do { \
(p)->next_task = &init_task; \
(p)->prev_task = init_task.prev_task; \
init_task.prev_task->next_task = (p); \
init_task.prev_task = (p); \
} while (0)
#define REMOVE_LINKS(p) do { \
(p)->next_task->prev_task = (p)->prev_task; \
(p)->prev_task->next_task = (p)->next_task; \
} while (0)
#define CLONE_PID 0x00001000 /* set if pid shared */
#define PID_MAX 0x8000

#define for_each_task(p) \
for (p = &init_task ; (p = p->next_task) != &init_task ; )

struct task_struct {
struct task_struct *next_task, *prev_task;
pid_t pid;
pid_t pgrp;
pid_t session;
pid_t tgid;
int did_exec;
};

struct task_struct init_task = {
next_task: &init_task,
prev_task: &init_task,
pid: 0,
pgrp: 0,
session: 0,
tgid: 0,
did_exec: 0,
};
struct task_struct *current = &init_task;
static pid_t last_pid;

static int get_pid(unsigned long flags)
{
static int next_safe = PID_MAX;
struct task_struct *p;
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;
}
if(last_pid >= next_safe) {
inside:
next_safe = PID_MAX;
read_lock(&tasklist_lock);
repeat:
for_each_task(p) {
if(p->pid == last_pid ||
p->pgrp == last_pid ||
p->tgid == last_pid ||
p->session == last_pid) {
if(++last_pid >= next_safe) {
if(last_pid & 0xffff8000)
last_pid = 300;
next_safe = PID_MAX;
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;
}
read_unlock(&tasklist_lock);
}
pid = last_pid;
spin_unlock(&lastpid_lock);

return pid;

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

static void fatal(char *msg)
{
fprintf(stderr, "%s: %s", msg, strerror(errno));
exit(1);
}

static struct task_struct *find_task_by_pid(pid_t pid)
{
struct task_struct *tsk;

for_each_task(tsk)
if (tsk->pid == pid)
return tsk;
return NULL;
}

static struct task_struct *add_task(pid_t pid, pid_t pgrp, pid_t session,
pid_t tgid)
{
struct task_struct *tsk;

tsk = malloc(sizeof(struct task_struct));
if (tsk == NULL)
fatal("malloc");
tsk->pid = pid;
tsk->pgrp = pgrp;
tsk->session = session;
tsk->tgid = tgid;
SET_LINKS(tsk);

return tsk;
}

static void del_task(struct task_struct *tsk)
{
REMOVE_LINKS(tsk);
free(tsk);
}

int main()
{
int i;
pid_t pid, pgrp;
struct task_struct *tsk;

for (i = 1; i < PID_MAX; i++) {
pid = get_pid(0);
add_task(pid, pid, pid, pid);
}
/* exit() */
tsk = find_task_by_pid(301);
del_task(tsk);
/* fork() */
pgrp = pid = get_pid(0);
add_task(pid, pid, pid, pid);
/* exit() */
tsk = find_task_by_pid(300);
del_task(tsk);
/* fork() */
pid = get_pid(0);
add_task(pid, pgrp, pid, pid);
/* exit() */
tsk = find_task_by_pid(301);
del_task(tsk);

/* fork() */
pid = get_pid(0);
add_task(pid, pgrp, pid, pid);

tsk = find_task_by_pid(300);
printf("new pid: %d, 300: pid %d, pgrp %d\n",
pid, tsk->pid, tsk->pgrp);

return 0;
}