lkml.org 
[lkml]   [2005]   [Jan]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFC] "biological parent" pid
On Mon, 31 Jan 2005, Michael Buesch wrote:

> Quoting Tim Schmielau <tim@physik3.uni-rostock.de>:
> > The ppid of a process is not really helpful if I want to reconstruct the
> > real history of processes on a machine, since it may become 1 when the
> > parent dies and the process is reparented to init.
> >
> > I am not aware of concepts in Linux or other unices that apply to this
> > case. So I made up the "biological parent pid" bioppid (in contrast to the
> > adoptive parents pid) that just never changes.
> > Any user of it must of course remember that it doesn't need to be a valid
> > pid anymore or might even belong to a different process that was forked in
> > the meantime. bioppid only had to be a valid pid at time btime (it's
> > a (btime, pid) pair that unambiguously identifies a process).
> >
> > Comments? (other that I just broke /proc/nnn/status parsing once again :-)
>
> Eh, I can't see how this bioppid would be useful.
> Help me. Examples?

I'm trying to reconstruct the complete history of processes from the
BSD accounting records. However, this is not very useful if a large
fraction of the processes look as if they were started by init.

The following program will print the history in a form vaguely resembling
pstree output from the accounting file:

Tim


/* treeacct.c: use ac_pid and ac_ppid fields of struct acct_v3 to
* build a tree of the process history.
*
* $Id: treeacct.c,v 0.8 2005/01/31 23:34:51 tim Exp tim $
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/mman.h>
#include <assert.h>

#include <linux/acct.h>


#define TIME_FUZZ 4

void *alloc(size_t size)
{
void *mem;
mem = malloc(size);
if (mem==NULL) {
fprintf(stderr, "out of memory.\n");
exit(5);
}
return mem;
}
/*
* For each pid the acct records are organized in a singly linked list
* named task_struct that is sorted by process start time (btime).
*
* They also form a tree according to their family relations.
*/
struct task_struct {
/* struct task_struct *prev; seems to be superfluous */
struct task_struct *next, *parent, *children, *siblings;
struct acct_v3 *acct;
};

struct pid_struct {
struct pid_struct *next;
struct task_struct *tasklist;
};
/*
* The task_structs are stored in a hash array of singly linked pid_struct
* lists sorted by pid.
*/
#define PID_HASH_MASK 0xf

struct pid_struct *pid_hash[PID_HASH_MASK + 1];

/*
* List of tasks without parents.
*/
struct task_struct *orphans=NULL;

/*
* Find the task that is uniquely determined by it's pid and the
* time when the pid was valid.
* If create!=0 and the task doesn't exist yet, create it.
*/
struct task_struct *get_task(__u32 pid, __u32 time, int create)
{
struct task_struct **task, *newtask;
struct pid_struct **pidlist, *newpid;
pidlist = &pid_hash[pid & PID_HASH_MASK];
while (*pidlist!=NULL && (*pidlist)->tasklist->acct->ac_pid > pid)
pidlist = &((*pidlist)->next);
if (*pidlist==NULL || (*pidlist)->tasklist->acct->ac_pid < pid) {
/* this pid doesn't exist */
if (create!=0) {
/* so create task */
newtask = alloc(sizeof(struct task_struct));
newtask->next = NULL;
/* as well as a pidlist for it*/
newpid = alloc(sizeof(struct pid_struct));
newpid->next = *pidlist;
newpid->tasklist = newtask;
*pidlist = newpid;
return newtask;
} else {
return NULL;
}
} else {
/* find task on pidlist */
task = &((*pidlist)->tasklist);
while (*task!=NULL
&& (*task)->acct->ac_btime < time)
task = &((*task)->next);
if (*task!=NULL
&& (*task)->acct->ac_btime <= time+TIME_FUZZ
&& (*task)->acct->ac_btime
+ (__u32)((*task)->acct->ac_etime+1)
>= time-TIME_FUZZ) {
/* process found */
if (create!=0) {
fprintf(stderr,
"warning: pid %lu, occurs twice"
" at time $lu.",
pid, time);
} else {
return *task;
}
}
if (create!=0) {
newtask = alloc(sizeof(struct task_struct));
newtask->next = *task;
*task = newtask;
return newtask;
} else {
return NULL;
}
}
}
void fill_hashtab(struct acct_v3 *acct_record)
{
struct task_struct *newtask;
newtask = get_task(acct_record->ac_pid, acct_record->ac_btime, 1);
assert(newtask!=0);

newtask->acct = acct_record;
newtask->children = NULL;
}
void tree_insert(struct task_struct *newtask)
{
struct task_struct **task;
newtask->parent = get_task(newtask->acct->ac_ppid,
newtask->acct->ac_btime, 0);
if (newtask->parent==NULL) {
task = &orphans;
} else {
task = &(newtask->parent->children);
}
/* keep the list sorted */
while ((*task) != NULL
&& ((*task)->acct->ac_pid < newtask->acct->ac_pid
|| ((*task)->acct->ac_pid == newtask->acct->ac_pid
&& (*task)->acct->ac_btime < newtask->acct->ac_btime)))
task = &((*task)->siblings);
newtask->siblings = *task;
*task = newtask;
}
void build_tree(unsigned long count)
{
struct task_struct *newtask;
struct pid_struct *pidlist;
int i;
for (i=PID_HASH_MASK; i>=0; i--)
for (pidlist = pid_hash[i];
pidlist!=NULL;
pidlist = pidlist->next)
for (newtask = pidlist->tasklist;
newtask!=NULL;
newtask = newtask->next) {
tree_insert(newtask);
count--;
}
assert(count==0);
}
void dump_task(struct task_struct *task, unsigned long depth)
{
struct task_struct *parent;
time_t t;
char start[32], end[32];
unsigned long i;
int pos;
/* convert start and end time to ascii */
t = task->acct->ac_btime;
ctime_r(&t, start);
/* start[24] = 0; */
t += (unsigned long)(task->acct->ac_etime+1);
ctime_r(&t, end);
/* end[24] = 0; */
for(i=1; i<2*depth; i++)
putchar(' ');
printf("%.*s (%lu, parent %lu) %nstart %s",
ACCT_COMM,
task->acct->ac_comm,
task->acct->ac_pid,
task->acct->ac_ppid,
&pos,
start);
for(i=1; i<pos+2*depth; i++)
putchar(' ');
printf("end %s", end);
}
void dump_tree(unsigned long count)
{
__u32 pid, maxpid=PID_HASH_MASK;
struct pid_struct *pidlist;
struct task_struct *task, *parent;
unsigned long dumped = 0;
unsigned depth = 1;
task = orphans;
while (task!=NULL) {
dump_task(task, depth);
dumped++;
if (task->children != NULL) {
depth++;
task = task->children;
} else if (task->siblings != NULL) {
task = task->siblings;
} else {
while (1) {
task = task->parent;
depth--;
if (task==NULL)
break;
if (task->siblings != NULL) {
task = task->siblings;
break;
}
}
}
}
fprintf(stderr, "dumped %lu records.\n", dumped);
assert(depth==0);
assert(dumped==count);
}
struct acct_v3
*mmap_acct_file(char *name, size_t *length, off_t *offset)
{
int acctfile;
struct acct_v3 *acct_records;
struct stat acctfile_status;
acctfile = open(name, O_RDONLY);
if (acctfile==-1) {
perror("error opening accounting file");
exit(2);
}
if (fstat(acctfile, &acctfile_status)!=0) {
perror("cannot fstat accounting file");
exit(3);
}
*length = acctfile_status.st_size - *offset;
fprintf(stderr, "length: %lu.\n", *length);
acct_records = mmap(NULL, *length, PROT_READ, MAP_PRIVATE, acctfile,
*offset);
if (acct_records==MAP_FAILED) {
perror("error mmapping accounting file");
exit(4);
}
close(acctfile);
return acct_records;
}
int main(int argc, char *argv[])
{
struct acct_v3 *acct_records;
size_t length = (unsigned long)(-1);
off_t offset = 0;
unsigned long count=0;
if (argc!=2) {
printf("usage: %s <acctfile>\n", argv[0]);
return 1;
}
acct_records = mmap_acct_file(argv[1], &length, &offset);
while (length>=sizeof(struct acct_v3)) {
fill_hashtab(acct_records);
acct_records++;
length -= sizeof(struct acct_v3);
count++;
}
if (length!=0)
fprintf(stderr,"Inclomplete last record of length %lu.\n",
length);
fprintf(stderr, "%lu records sucessfully read.\n", count);
build_tree(count);
dump_tree(count);

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 14:10    [W:0.423 / U:0.276 seconds]
©2003-2014 Jasper Spaans. hosted at Digital Ocean