2002-11-13 15:22:48

by Beau Kuiper

[permalink] [raw]
Subject: PATCH: Pusedo-random pid generation (not really serious)

Hi all,

Earlier today, I had just got home, and I decided that "I just had to check my
email".

So, away I go, booting up my linux system. I start X, and KDE gleefully comes
to life. Then I hit my email button (Kmail), only to discover that Kmail
thinks its still running, for the third time this week. (Kmail has a lock
file where it stores its running PID, and it gets left behind on an abnormal
shutdown, like Ctrl-Alt-Backspace, or the reboot command while it is running)

So, instead of doing the obvious thing, adding a command the remove the lock
file when I log in, I decide to do it the hard way by adding pusedo-random
pid generation into the kernel.

This patch isn't designed to add security and/or unpredictability into pid
creation. It simply is trying to avoid using the same pids all the time,
which confused programs that used lock files.

The linear random number generator here has a period of 2^31, and statisticly,
its pretty ok.

Decription:

1) Patch replaces get_pid with my version.
2) get_pid() returns 1 on first illiteration
3) get_pid() on second and further illiteration, seeds itself using the system
time, and then generates pids using a simple linear random number generator.

Bugs:

1) Does not detect out of pid situation. This is not a problem on default
kernel configurations, since only 2048 threads can exist at any one time on
the default configuration.
2) Probably other subtle things I haven't noticed yet :-)

Since I know that this will NEVER make it into a standard kernel, I simply
post it for people who might find it useful. People like me, who use Kmail
and are not very particular about shutting down carefully 8-)

Just apply the patch to kernel/fork.c and watch the pretty pids.

Have Fun
Beau Kuiper
[email protected]

--- linux-orig/kernel/fork.c Wed Nov 13 22:10:18 2002
+++ linux/kernel/fork.c Wed Nov 13 23:17:31 2002
@@ -83,6 +83,29 @@
/* Protects next_safe and last_pid. */
spinlock_t lastpid_lock = SPIN_LOCK_UNLOCKED;

+// beaus magic random pid generator
+
+static unsigned int pid_make_next(unsigned int last)
+{
+ unsigned short num;
+
+ // second pass through, seed from system time
+ if (last == 1)
+ {
+ struct timeval now;
+
+ do_gettimeofday(&now);
+ last = now.tv_sec & 0x7FFFFFFE;
+ }
+
+ last = (last * 16807) % 0x7FFFFFFE;
+
+ // first pass through, return 1 for init.
+ if (last == 0)
+ last = 1;
+ return last;
+}
+
static int get_pid(unsigned long flags)
{
static int next_safe = PID_MAX;
@@ -93,50 +116,39 @@
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;
- }
- if(unlikely(last_pid == beginpid))
+
+ // stir for next pid
+
+ last_pid = pid_make_next(last_pid);
+
+ read_lock(&tasklist_lock);
+
+ pid = last_pid & 0x7FFF;
+ if (pid == 0)
+ pid++;
+
+repeat:
+ for_each_task(p) {
+ if(p->pid == pid ||
+ p->pgrp == pid ||
+ p->tgid == pid ||
+ p->session == pid) {
+ last_pid = pid_make_next(last_pid);
+ pid = last_pid & 0x7FFF;
+ // TODO: add code to find when we run out of pids.
+/* if(unlikely(last_pid == beginpid))
goto nomorepids;
- goto repeat;
- }
- 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;
+*/
+ if (pid == 0)
+ pid++;
+ goto repeat;
}
- read_unlock(&tasklist_lock);
}
- pid = last_pid;
+
+ spin_unlock(&tasklist_lock);
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)



2002-11-13 15:37:41

by Lars Marowsky-Bree

[permalink] [raw]
Subject: Re: PATCH: Pusedo-random pid generation (not really serious)

On 2002-11-13T23:30:36,
Beau Kuiper <[email protected]> said:

> This patch isn't designed to add security and/or unpredictability into pid
> creation. It simply is trying to avoid using the same pids all the time,
> which confused programs that used lock files.

Those programs are royally broken, they at least need to verify that the PID
stored actually refers to itself.

Be happy that you find out about such broken behaviour immediately and fix the
programs.

> The linear random number generator here has a period of 2^31, and statisticly,
> its pretty ok.

> Since I know that this will NEVER make it into a standard kernel, I simply
> post it for people who might find it useful. People like me, who use Kmail
> and are not very particular about shutting down carefully 8-)

Fix kmail.


Sincerely,
Lars Marowsky-Br?e <[email protected]>

--
Principal Squirrel
SuSE Labs - Research & Development, SuSE Linux AG

"If anything can go wrong, it will." "Chance favors the prepared (mind)."
-- Capt. Edward A. Murphy -- Louis Pasteur