/* 
 * 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);
}