/*-------------------------------------------------------------------------
 * Filename:      clockd.c
 * Copyright:     Copyright (C) 2001, Johan Pouwelse
 * Author:        Johan Pouwelse (J.A.Pouwelse@its.tudelft.nl)
 * Description:   Main file for a daemon that listens to requests of applications or 
 *                users to reserve processor cycles. Processor reservations are added
 *                together and their possible deadline is taken into account to calculate
 *                the best speed setting of the processor. The goal is to reduce power.
 * Created at:    24th Jan 2001
 * Modified by:   
 * Modified at:   
 *-----------------------------------------------------------------------*/
/*
 * clockd.c: main file for the clock speed scheduler
 *
 * Copyright (C) 2001  Johan Pouwelse (J.A.Pouwelse@its.tudelft.nl)
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 */

#include	<sys/types.h>
#include	<sys/time.h>
#include	<sys/stat.h>
#include	<sys/un.h>
/* #include	<netinet/in.h> */
/* #include	<arpa/inet.h> */
#include	<stdio.h>
#include	<stdlib.h>
#include	<string.h>
#include	<unistd.h>
#include	<errno.h>
#include	<getopt.h>
#include	<fcntl.h>
#include	<sys/socket.h>

#define         SERV_PORT  6666
#define         MAXTASKS   32
#define         MAXINTVALS 32			/* maximum number of intervals */
#define         LISTENQ    8
#define         MAXLINE    256
#define         VERBOSE    1
#define         UNIXSOCKETPATH  "/tmp/clockd.sock"	/* file for UNIX domain socket */

/* the main struct that contains processor reservations */
/* every reservation ha some fields filled in           */
typedef		struct reservation {
		long deadline;			/* deadline of task in usec from current time, -1 for infinite reservations */
		long speed;				/* required processor speed 0..12 */
		long start;				/* optional start of task, currently not used */
		long socket;				/* client socket, used to identify the reserver */
		struct reservation *next;	/* linked list of all reservations */
} reservation_t;

typedef		struct timeregion {
		long begin;			/* begin time of timeregion */
		long end;				/* ending time of timeregion */
		reservation_t *potential[MAXTASKS];		/* pointer to tasks that can be scheduled */
		int scheduled[MAXTASKS];		/* amount of task i that is scheduled */
		struct timeregion *next;	/* linked list of all timeregions */
} timeregion_t;

extern int 	errno;
char		PROMPT[] 	= "clock scheduler>";	/* the daemon prompt */
int		scaling		= 0;		/* set speed in /proc/scale */
int		verbose		= 0;		/* print debug info or be silent */
int		additive	= 0;		/* the simple additive scheduling mode */
reservation_t	*clock_schedule = NULL;		/* global variable with the complete schedule */
						/* a schedule consists of reservation_t's   */
timeregion_t	*complete_schedule = NULL;

/* function prototypes */
void		determine_deadline(struct timeval *next_event);
void		task_schedule(reservation_t *res, long *scheduled_amount, timeregion_t **schedule_space,long max_level,timeregion_t *overlap);
void		error(char *error);
void		warning(char *error);
void		set_speed(int speed);		/* set processor speed */
void		string_write(int fd, char *string);
void		print_reservations(void);

timeregion_t *create_timeregions(reservation_t *res);
void		lowest_scheduled_timeregion(timeregion_t **ret, timeregion_t *tr, long begin, long end);
long		secondlowest_timeregion(timeregion_t *threshold, timeregion_t *tr, long begin, long end);
timeregion_t	*overlapping_timeregion(timeregion_t **tr, timeregion_t *root);
long		scheduledlvl_timeregion(timeregion_t *tr);
void		delete_timeregions(timeregion_t *tr);
void	  print_timeregions(timeregion_t *res);

/***************************************************************/
/*     Scheduling routines                                     */
/***************************************************************/
/*                                                             */
/*              the heart of this daemon                       */
/*                                                             */
/* Used in NON additive mode.                                  */
/* calculate the processor speed that is needed to furfill all */
/* received reservations. Also fill the next_event variable    */
/* with the time until the next processor speed change.        */
/* method: do an algorithm that determines the near-optimal    */
/* speed setting for given reservations                        */
void energy_priority_scheduling(void) {
	reservation_t	*res;
	timeregion_t	*tr;
	timeregion_t	*lowest[MAXINTVALS];		/* pointer to tasks that can be scheduled */
	timeregion_t	*overlap;					/* 1 overlapping region, TODO extend to n */
	long second, new_task;

	res=clock_schedule;			/* global with all processor reservations */
	if(res==NULL) return;
	if (verbose)
		print_reservations();
/*	if(complete_schedule!=NULL) {
		determine_deadline(next_event);
		return;
	} */
	tr=create_timeregions(res);
	complete_schedule=tr;

	/* schedule all tasks one by one, in EDF order */
	while(res!=NULL) {
		/* loop to partially schedule the current reservation */
		/* the work to schedule, normalize from 0..16 */
		new_task=(res->deadline - res->start)*(res->speed);

		while(new_task>0) {
			lowest_scheduled_timeregion(lowest,tr, res->start, res->deadline);
			second=secondlowest_timeregion(lowest[0],tr,res->start,res->deadline);
			if (verbose)
				printf("2nd lowest: %ld.\n", second);
			overlap=overlapping_timeregion(lowest,tr);
			if (verbose) {
				if (overlap==NULL) 
					printf("schedule: task starting at %06ld, speed %ld, left %ld, no overlap\n", res->start, res->speed,new_task);
				else
					printf("schedule: task starting at %06ld, speed %ld, left %ld, overlap\n", res->start, res->speed,new_task);
			}
			/* schedule reservation: "res" and adjust overlapping tasks */
			task_schedule(res,&new_task,lowest,second,overlap);
		}
		res=res->next;
	}
	/* determine_deadline(next_event);
*/
	if (verbose) 
 	 print_timeregions(tr);
/*	delete_timeregions(tr);
*/
}

void determine_deadline(struct timeval *next_event) {
		long first_dead;
		if (complete_schedule->begin==0) {		/* calculate first deadline */
			first_dead=complete_schedule->end;
		} else {
			first_dead=complete_schedule->begin;
		}
		next_event->tv_usec=first_dead%1000000;
		first_dead-=next_event->tv_usec;
		next_event->tv_sec=first_dead/1000000;
		set_speed(scheduledlvl_timeregion(complete_schedule));
	if (verbose)
		printf("SET SPEED: %ld for %ld sec %ld usec.\n",scheduledlvl_timeregion(complete_schedule), next_event->tv_sec,next_event->tv_usec);
}

void increase_schedule(reservation_t *res, long *scheduled_amount, timeregion_t *schedule_space, int max_level) {
	int x, curr_level;

	curr_level=scheduledlvl_timeregion(schedule_space);
	if(curr_level>=max_level)
		error("schedule equal or beyond max_level");
	for(x=0;x<MAXINTVALS;x++) {
		if(schedule_space->potential[x]==NULL)
			break;
		if(schedule_space->potential[x]==res) {
			/* schedule the task from curr_lvl .. max_level

		  schedule_space->scheduled[x]+=res->speed < max_level-curr_level ? res->speed : max_level-curr_level;
			*scheduled_amount-=level*(schedule_space->end - schedule_space->begin);
			return;
*/
		}
	}
	error("could not increase schedule");
}

/* increase the reservation up to the given _total_ level in interval */
/* return the added time*speed */
long grow_reservation(reservation_t *res, timeregion_t *tr, long max_level) {
	int x;
	long addition;

	addition=max_level-scheduledlvl_timeregion(tr);
	if(addition<=0) error("could not grow to max_level");

	for(x=0;x<MAXINTVALS;x++) {
		if(tr->potential[x]==NULL)
			break;
		if(tr->potential[x]==res) {
		  if(tr->scheduled[x]<0)
				error("negative schedule found while growing");
			/* schedule the task */
		  tr->scheduled[x]+=addition;
			return (addition*(tr->end - tr->begin));
		}
	}
	error("could not increase schedule");
	return(0);
}

/* increase the reservation with addition */
long increase_reservation(reservation_t *res, timeregion_t *tr, long addition) {
	int x;

	for(x=0;x<MAXINTVALS;x++) {
		if(tr->potential[x]==NULL)
			break;
		if(tr->potential[x]==res) {
		  if(tr->scheduled[x]<0)
				error("negative schedule found while increasing");
			/* schedule the task */
		  tr->scheduled[x]+=addition;
			return(addition*(tr->end - tr->begin));
		}
	}
	error("could not increase schedule");
	return(0);
}

/* decrease from one tr */
int decrease_reservation(reservation_t *res, timeregion_t *tr, long subtract) {
	int x;

	for(x=0;x<MAXINTVALS;x++) {
		if(tr->potential[x]==NULL)
			break;
		if(tr->potential[x]==res) {
		  if(tr->scheduled[x]<=0)
				error("subtracting from zero schedule");
			/* adjust the task */
		  tr->scheduled[x]-=subtract/(tr->end - tr->begin);
		  if(tr->scheduled[x]<=0)
				error("created a zero schedule");
			return(1);
		}
	}
	return(0);
}

long average_speed(long to_schedule, timeregion_t **trs,timeregion_t *overlap) {
	int x,y;
	long total, min=99999999, max=-1;

	/* add the new task */
	total=to_schedule;

	for(x=0;x<MAXINTVALS;x++) {
		if(trs[x]==NULL)
			break;
		for(y=0;y<MAXINTVALS;y++) {
			if(trs[x]->potential[y]==NULL)
				break;
			total+=trs[x]->scheduled[y]*(trs[x]->end-trs[x]->begin);
			min=trs[x]->begin<min? trs[x]->begin : min;
			max=trs[x]->end  >max? trs[x]->end   : max;
		}
	}
		/* TODO do not assume it's the only task */
	total+=overlap->scheduled[0]*(overlap->end-overlap->begin);
	min=overlap->begin<min? overlap->begin : min;
	max=overlap->end  >max? overlap->end   : max;
	
	return(total / (max-min));
}

/* add a part of a new_task to the schedule were is costs the least amount */
/* of energy and adjust overlaping tasks */
void task_schedule(reservation_t *res, long *scheduled_amount, timeregion_t **schedule_space,long max_level,timeregion_t *overlap) {
	int x;
	long avg, transfer;

	if(overlap==NULL && max_level==-1) {
		/* for each interval schedule the task, there are no problems */
		for(x=0;x<MAXINTVALS;x++) {
			if(schedule_space[x]==NULL)
				return;
			*scheduled_amount-=increase_reservation(res,schedule_space[x],res->speed);
		}
	} else {
		if(max_level==-1 || *scheduled_amount<50000) {	/* compensate rounding errors due to int schedule type */
			printf("stopping itteration, there is no 2nd level any more.\n");
			*scheduled_amount=0;
			return;
		}
		if (verbose)
			printf("overlap tr->begin %ld\n",overlap->begin);
		/* TODO check if new_task is above avg */
		if ((avg=average_speed(*scheduled_amount,schedule_space,overlap)) < max_level) {
			max_level=avg;
		}
		if (verbose) 
			printf("average speed %ld.\n",avg);
		/* TODO do not assume it's only task in overlap */
		if (res->speed > max_level)	error("could not adjust with higher level");
		transfer=increase_reservation(overlap->potential[0],overlap, max_level-overlap->scheduled[0]);	/* shift to overlap */
		for(x=0;x<MAXINTVALS;x++) {
			if(schedule_space[x]==NULL)
				return;
			/* TODO do not asume res has only 1 tr presence */
			if(decrease_reservation(overlap->potential[0],schedule_space[x],transfer)==1) {
			} else {	/* not interval with overlap */
			}
			*scheduled_amount-=grow_reservation(res,schedule_space[x],max_level);
		}
	}
}

/* Only used in additive mode.                                 */
/* calculate the processor speed that is needed to furfill all */
/* received reservations. Also fill the next_event variable    */
/* with the time until the next processor speed change.        */
/* method: just add all processor reservations                 */
void determine_clock_schedule_additive(struct timeval *next_event) {
	reservation_t	*res;
	int speed=0;	/* required speed */
	long first_dead=-1;

	res=clock_schedule;			/* global with all processor reservations */
	while(res!=NULL) {
		speed+=res->speed;		/* add all speed requirements */
		/* TODO start of job is also a deadline */
		if (res->deadline != -1) {
			if (first_dead == -1) {		/* keep track of the first deadline */
				first_dead=res->deadline;
			} else {
				if (res->deadline < first_dead) {
					first_dead=res->deadline;
				}
			}
		}
		res=res->next;	/* else, advance in list */
	}
	if (first_dead == -1) {		/* keep track of the first deadline */
		set_speed(speed);
		if (verbose) 
			printf("SET SPEED: %d, no timeout.\n", speed);
		next_event->tv_sec=0;
		next_event->tv_usec=0;
		return;
	}
	next_event->tv_usec=first_dead%1000000;
	first_dead-=next_event->tv_usec;
	next_event->tv_sec=first_dead/1000000;
	set_speed(speed);
	if (verbose) 
		printf("SET SPEED: %d for %ld sec %ld usec.\n", speed,next_event->tv_sec,next_event->tv_usec);
}

/* use the amount of time that has passed to update all relative */
/* deadlines and remove reservations that have been furfilled    */ 
void advance_time(long usec) {
	reservation_t	**res, *del;
	timeregion_t	**tr, *rm;
	
	if (verbose) 
		printf("advanced time: %ld.\n", usec);
	if(usec<0) {
		printf("negative time: %ld.\n", usec);
		print_reservations();
		error("negative time advancement");
	}
	res=&clock_schedule;
	while(*res!=NULL) {
		if ((*res)->deadline == -1) {			/* BUG TODO: a normal passed deadline can also have -1 */
			res=&((*res)->next);
			continue;
		}
		(*res)->deadline-=usec;		/* reduce relative deadline */
		(*res)->start-=usec;		/* reduce relative deadline */
		if ((*res)->start <= 0) {	/* Should it be run-able? */
			(*res)->start=0;
		}
		if ((*res)->deadline <= 0) {	/* remove an old reservation? */
			del=*res;
			*res=del->next;
			free(del);
		} else {
			res=&((*res)->next);	/* else, advance in list */
		}
	}
	tr=&complete_schedule;
	while(*tr!=NULL) {
		(*tr)->begin-=usec;
		if ((*tr)->begin < 0)
			(*tr)->begin=0;

		(*tr)->end-=usec;
		if ((*tr)->end <= 0) {	/* delete old */
			rm=*tr;
			complete_schedule=(*tr)->next;
			free(rm);
			tr=&complete_schedule;
		} else {
			tr=&((*tr)->next);	/* else, advance in list */
		}
	}
	if (!verbose) 
		return;
	printf("DONE advanced time: %ld.\n", usec);
}

/***************************************************************/
/*     TimeRegion handling routines                            */
/***************************************************************/

/* return a scheduled overlapping task if there is overlap between base and target */
/* only return if the overlapping task is scheduled task in base */
/* TODO, ther could be more than one */
reservation_t *taskoverlaps_timeregions(timeregion_t *base, timeregion_t *target) {
	int x,y;

	if(base==target) 			/* should not be equal */
		return(NULL);

	for(x=0;x<MAXINTVALS;x++) {
		if (base->potential[x]==NULL)
			break;
		/* for all potential task that are scheduled here */
		if (base->scheduled[x]>0) {
			for(y=0;y<MAXINTVALS;y++) {
				if (target->potential[y]==NULL)
					break;
				if (base->potential[x]==target->potential[y]) {		/* same task ? */
					return(base->potential[x]);
				}
			}
		}
	}
	return(NULL);
}

/* return the overlapping time region that is scheduled with a task */
/* TODO expand to return list and more checking */
timeregion_t *overlapping_timeregion(timeregion_t **tr, timeregion_t *root) {
	reservation_t 	*overlap=NULL;
	timeregion_t	*temp;
	int x;

	for(x=0;x<MAXINTVALS;x++) {
		/* for all potential **trs */
		if (tr[x]==NULL)
			return(NULL);
		/* find a scheduled task that can be adjusted */
		temp=root;
		while(temp!=NULL) {
			if((overlap=taskoverlaps_timeregions(tr[x], temp))!=NULL) {
				return(temp);
			}
			temp=temp->next;
		}
	}
	return(NULL);
}

/* Return the lowest time within the reservations above the threshold, or -1 if none */
long getlowest_time(reservation_t *res, long threshold) {
	long lowest=-1;
	while(res!=NULL) {
		if (res->start > threshold) {
			if (lowest > -1)
				lowest=res->start>lowest ? lowest : res->start;
			else
				lowest=res->start;
		}
		if (res->deadline > threshold) {
			if (lowest > -1)
				lowest=res->deadline>lowest ? lowest : res->deadline;
			else
				lowest=res->deadline;
		}
		res=res->next;
	}
  return(lowest);
}

/* return the scheduled lvl inside the time region */
long scheduledlvl_timeregion(timeregion_t *tr) {
	long ret=0;
	int x;

	for(x=0;x<MAXINTVALS;x++) {
		if (tr->potential[x]==NULL)
			break;
		if (tr->scheduled[x]>0) {
			ret+=tr->scheduled[x];		/* add speed settings */
		}
	}
	return(ret);
}

/* select the time region with the lowest scheduled activity */
/* ret is an array of tr pointers, tr contains all timeregions, begin and end */
/* limit the valid interval */
void lowest_scheduled_timeregion(timeregion_t **ret, timeregion_t *tr, long begin, long end) {
	int x;
	long level,low=-1;
	timeregion_t *root=tr;

  for(x=0;x<MAXINTVALS;x++) {
		ret[x]=NULL;
	}
	/* find the lowest level */
	while(tr!=NULL) {
		if(begin <= tr->begin && end >= tr->end) {		/* a tr inside given begin,end */
			level=scheduledlvl_timeregion(tr);
			if(low==-1) {
				low=level;
			} else {
				low=level<low? level : low;
			}
		}
		tr=tr->next;
	}
	x=0;
	tr=root;
	/* return intervals with lowest level */
	while(tr!=NULL) {
		if(begin <= tr->begin && end >= tr->end) {		/* a tr inside given begin,end */
			level=scheduledlvl_timeregion(tr);
			if(low==level) {
				ret[x++]=tr;
			}
		}
		tr=tr->next;
	}
}
long secondlowest_timeregion(timeregion_t *threshold, timeregion_t *tr, long begin, long end) {
	long second=-1, level, lowest;

	/* what is the lowest level ? */
	lowest=scheduledlvl_timeregion(threshold);

	/* find the 2nd lowest level */
	while(tr!=NULL) {
		if(begin <= tr->begin && end >= tr->end) {		/* a tr inside given begin,end */
			level=scheduledlvl_timeregion(tr);
			if(level>lowest) {		/* the 2nd lowest must be larger then the lowest, not equal */
				if(second==-1) {
					second=level;
				} else {
					second=level<second? level : second;
				}
			}
		}
		tr=tr->next;
	}
	return(second);
}

timeregion_t *new_timeregion(long begin, long end) {
	timeregion_t *new;
	int x;

	new=(timeregion_t *)malloc(sizeof(timeregion_t));
	if (new==NULL)
		error("timeregion malloc error");
	new->begin=begin;
	new->end=end;
	new->next=NULL;
  for(x=0;x<MAXTASKS;x++) {
		new->potential[x]=NULL;
		new->scheduled[x]=0;
	}
	return(new);
}

void addto_timeregion(timeregion_t *tr, reservation_t *res) {
	int x;
  for(x=0;x<MAXTASKS;x++) {
		if (tr->potential[x]==NULL) {
			tr->potential[x]=res;
			return;
		}
	}
	error("MAXTASKS reached");
}

timeregion_t *create_timeregions(reservation_t *res) {
	long low, next;
	timeregion_t *root, *last;
	reservation_t *curr;

	if(res==NULL) 
		return(NULL);
	low=getlowest_time(res,-1);		/* select the lowest time in reservations */
	next=getlowest_time(res,low);		/* select the 2nd lowest */
	root=new_timeregion(low,next);	/* add the 1st interval */
	last=root;			/* remember the first time_region */
  low=next;
	while((next=getlowest_time(res,low)) >= 0) {
		last->next=new_timeregion(low,next);
		last=last->next;
		low=next;
	}
	last=root;
	while(last!=NULL) {
		curr=res;
		while(curr!=NULL) {
			if(curr->start <= last->begin && curr->deadline >= last->end) {
				addto_timeregion(last,curr);
			}
			curr=curr->next;
		}
		last=last->next;
	}
	return(root);
}

void delete_timeregions(timeregion_t *tr) {
  if(tr!=NULL) {
		delete_timeregions(tr->next);
		free(tr);
	}
}

/* for debugging purposes. Print all time regions */
void print_timeregions(timeregion_t *tr) {
	int x;
  if (tr!=NULL) printf("T begin\tend\t\tpotential\n");
  while(tr!=NULL) {
		printf("%ld\t%ld\t\t",tr->begin,tr->end);
  	for(x=0;x<MAXTASKS;x++) {
			if (tr->potential[x]==NULL) {
				printf("\n");
				break;
			}
			printf("%06ld,%06ld: %03d\t",tr->potential[x]->start,tr->potential[x]->deadline,tr->scheduled[x]);
		}
		tr=tr->next;
	}
}

/***************************************************************/
/*     Reservation handling routines                           */
/***************************************************************/

/* create a new struct for a processor reservation */
/* return the allocated mem with default values    */
reservation_t *new_reservation() {
	reservation_t *res;

	res = (reservation_t *) malloc (sizeof(reservation_t));
	res->deadline=-1;
	res->speed=-1;
	res->start=-1;
	res->socket=-1;
	res->next=NULL;

	return(res);
}

/* The processor reservations are stored in Earliest Deadline First order. */
/* Check if there are other reservations and insert in proper location.    */
/* Deadlines of '-1' come first; these are infinite reservations           */
void insert_reservation_EDF(reservation_t *new) {
	reservation_t	*res;

	if(clock_schedule==NULL) {		/* there are no other reservations */
		clock_schedule=new;
	} else {
		res=clock_schedule;
		if(res->deadline > new->deadline) {	/* insert before first entry */
			clock_schedule=new;
			new->next=res;
			return;
		}
		while(res->next!=NULL) {
			if(res->next->deadline > new->deadline) {	/* insert *new before the next */
				new->next=res->next;
				res->next=new;
				return;
			}
			res=res->next;
		}
		res->next=new;			/* just append */
	}
}

/* just insert the reservation at the end of the reservation list */
void insert_reservation(reservation_t *new) {
	reservation_t	*res;

	if(clock_schedule==NULL) {		/* there are no other reservations */
		clock_schedule=new;
	} else {
		res=clock_schedule;
		while(res->next!=NULL) {
			res=res->next;
		}
		res->next=new;			/* just append */
	}
}
 
/* Remove the previous speed only reservation of a client. */
/* A speed only reservation is one with no deadline or start time. */
/* This function is used to overwrite the old fixed speed reservation. */
void delete_speed_only_reservation(int socket) {
	reservation_t	**res, *del;

	res=&clock_schedule;
	while(*res!=NULL) {
		/* check if it is a speed only reservation of this client */
		if ((*res)->deadline < 0 && (*res)->start < 0 && (*res)->socket == socket) {
			del=*res;
			*res=del->next;
			free(del);
			return;		/* there can only be 1 previous fixed speed res */
		} else {
			res=&((*res)->next);	/* else, advance in list */
		}
	}
}

/* remove all reservations for a given socket, usefull when a client exits */
void delete_reservations(int socket) {
	reservation_t	**res, *del;

	res=&clock_schedule;
	while(*res!=NULL) {
		/* check if it is a reservation from this client */
		if ((*res)->socket == socket) {
			del=*res;		/* mark for removal */
			*res=del->next;		/* remove from linked list */
			free(del);		/* release mem */
		} else {
			res=&((*res)->next);	/* else, advance in list */
		}
	}
}

/* for debugging purposes. Print all made reservations */
void print_reservations(void) {
	reservation_t	*res;
	res=clock_schedule;
	if(res==NULL) {
		printf("*** no tasks.\n");
		return;
	}
	printf("socket\tdead\tspeed\tstart\n");
	while(res!=NULL) {
		printf("%ld\t%ld\t%ld\t%ld\n",res->socket,res->deadline,res->speed,res->start);
		res=res->next;
	}
}

/***************************************************************/
/*     Utility routines                                        */
/***************************************************************/

void error(char *error) {
  printf("ERROR: %s.\n",error);
  exit(-1);
}

void warning(char *error) {
  printf("WARNING: %s.\n",error);
}

int my_string_compare(const char *s1, const char *s2, int maxlen) {
	int i;

	for(i = 0; i < maxlen; i++) {
		if(s1[i] != s2[i])
			return ((int) s1[i]) - ((int) s2[i]);
		if(s1[i] == 0)		/* s1==s2 */
			return 0;	/* and equal to \0 */
	}
	return 0;
} /* my_string_compare */

int my_atol(const char *s1, long *val) {
	int i;

	*val=0;
	for(i = 0; i <= 10; i++) {	/* max is 9.999.999.999 */
		if( ((int)s1[i]) >= '0' && ((int)s1[i]) <= '9') {/* equal to a number? */
			*val*=10;
			*val+=s1[i]-'0';	/* dependant on ASCII table... */
		} else {	/* [^0-9], also when == '\0', end of string */
			return(i);
		}
	}
	return(0);
}

void set_speed(int speed) {
	int fd;
	char buf[3];
	struct timeval now;

	if (!scaling)
		return;

/* the SA1100 only knows range 0..12 instead of 0..16 */
	speed-=4;

	/* this is where we are */
	gettimeofday(&now,(struct timezone *)NULL);
	printf("%06ld.%06ld\t0\tSWITCH\t%d\n", now.tv_sec,now.tv_usec,speed);

	snprintf(buf,3,"%02d",speed);			/* prepare the command */
	if ((fd=open("/proc/scale", O_WRONLY)) < 0)	/* open the processor speed interface */
		error("could not open scale interface");
	if (write(fd,buf,2) <= 2)			/* send the set_speed command */
		error("could not write to scale interface");
	close(fd);
}

/***************************************************************/
/*     Command processing routines                             */
/***************************************************************/

/* read a given parameter from the buffer, return the value     */
/* the format is: par1=val1 par2=val2 par3=val3.                */
/* checks if par1 in the given line (s1) is equal to *parameter */
/* if true, fill *val and reduce the remaining *length to read  */
int parameter_read(char **s1, int *length, char *parameter, long *val) {
	char	line[65], *ptr=*s1;
	int	len, read_away;

	len=snprintf(line,64," %s=", parameter);	/* formated parameters as it appears in cmd line */
	if (my_string_compare(ptr,line,len) == 0) {	/* OK, found the parameter */
		if ( (read_away=my_atol(ptr+len, val)) == 0) {	/* fill the val pointer */
			return(0);			/* couldn't read the value of the parameter */
		} else {
			*s1+=len+read_away;		/* shift the current parsed pointer */
			*length-=len+read_away;
			return(len+read_away);		/* OK, return the parsed chars */
		}
	} 
	return(0);					/* did not match the parameter name */
}

/* parse the task command and update the clock scheduler info */
void process_command_time(int fd, char *ptr, int len) {
	long progress;

	if (len<=2) {
		string_write(fd,"time command requires an argument\n");
		return;
	}
	if (parameter_read(&ptr, &len, "advance", &progress) > 0) {
		if (progress<0) {	/* check argument */
			string_write(fd,"*** No valid advance parameter\n");
			return;
		}
	} else {
		string_write(fd,"*** Bad time request\n");
		return;
	}
	advance_time(progress);
	if (complete_schedule==NULL) {
		set_speed(5);		/* lowest resting speed */
		if (verbose)
			printf("SET SPEED: 5 no timeout.\n");
	} else {
		set_speed(scheduledlvl_timeregion(complete_schedule));
		if (verbose)
			printf("SET SPEED: %ld for %ld usec.\n",scheduledlvl_timeregion(complete_schedule), complete_schedule->end);
	}
}

/* parse the task command and update the clock scheduler info */
void process_command_task(int fd, char *ptr, int len) {
	reservation_t *reservation=new_reservation();

	if (len<=2) {
		string_write(fd,"task command requires an argument\n");
		return;
	}
	reservation->socket=fd;
        while (len>2) {
		if (parameter_read(&ptr, &len, "speed", &(reservation->speed)) > 0) {
		} else if (parameter_read(&ptr, &len, "deadline", &(reservation->deadline)) > 0) {
		} else if (parameter_read(&ptr, &len, "start", &(reservation->start)) > 0) {
		} else {
			string_write(fd,"*** Bad task request\n");
			free(reservation);
			return;
		}
	}
	if (reservation->speed<0) {	/* check speed argument */
		string_write(fd,"*** No valid speed parameter\n");
		return;
	}
	if (reservation->deadline<0 && reservation->start<0) {	/* only the speed param? */
		delete_speed_only_reservation(fd);	/* overwrite the old reservation */
	}
	insert_reservation(reservation);		/* insert new reservation */
}

/* check if the command matching with defined commands and call the */
/* functions that do further processing of specific command         */
int process_command(int fd, char *ptr, int len) {
	if (len>2) {
		if (my_string_compare(ptr,"exit",4) == 0) {
			delete_reservations(fd);
			return (-1);
		} else if (my_string_compare(ptr,"help",4) == 0) {
			string_write(fd,"display help\n");
		} else if (my_string_compare(ptr,"info speed=",11) == 0) {
			string_write(fd,"display mem_bw, mem_max, cpu_mhz, cpu_cost, etc.\n");
		} else if (my_string_compare(ptr,"ver",3) == 0) {
			string_write(fd,"version v0.01\n");
		} else if (my_string_compare(ptr,"task",4) == 0) {
			process_command_task(fd,ptr + 4,len-4);		/* process the processor reservation */
		} else if (my_string_compare(ptr,"time",4) == 0) {
			process_command_time(fd,ptr + 4,len-4);		/* process the time advancements */
		} else {
			string_write(fd,"*** Unknown command.\n");
		}
	}
	string_write(fd,PROMPT);
	return (0);
}

/***************************************************************/
/*     Socket I/O routines                                     */
/***************************************************************/

/* read a block of socket I/O data. Function uses buffered I/O */
static ssize_t buffered_read(int fd, char *ptr) {
	static int	read_cnt = 0;
	static char	*read_ptr;
	static char	read_buf[MAXLINE];

	if (read_cnt <= 0) {		/* I/O buffer filled ? */
again:
		if ( (read_cnt = read(fd, read_buf, sizeof(read_buf))) < 0) {
			if (errno == EINTR)
				goto again;
			printf("reading error\n");
			return(-1);		/* read returned an error */
		} else if (read_cnt == 0)
			return(0);
		read_ptr = read_buf;
	}

        /* todo flush buffer if data was from other socket ! */
	read_cnt--;
	*ptr = *read_ptr++;
	return(1);
}

/* read bytes from the given socket until \n encoutered or ^D */
ssize_t line_read(int fd, void *vptr, size_t maxlen) {
	int	n, rc;
	char	c, *ptr;

	ptr = vptr;
	for (n = 1; n < maxlen; n++) {
		if ( (rc = buffered_read(fd, &c)) == 1) {
			*ptr++ = c;
			if (c == '\n')
				break;	/* newline is stored, like fgets() */
		} else if (rc == 0) {
			if (n == 1)
				return(0);	/* EOF, no data read */
			else
				break;		/* EOF, some data was read */
		} else
			error("socket read error"); /* error, errno set by read() */	
        }

	*ptr = 0;	/* null terminate like fgets() */
	return(n);
}

/* Write "n" bytes to a descriptor. */
ssize_t	numbered_write(int fd, const void *vptr, size_t n) {
	size_t		nleft;
	ssize_t		nwritten;
	const char	*ptr;

	ptr = vptr;
	nleft = n;
	while (nleft > 0) {
		if ( (nwritten = write(fd, ptr, nleft)) <= 0) {
			if (errno == EINTR)
				nwritten = 0;		/* and call write() again */
			else
				error("socket write failed");			/* error */
		}
		nleft -= nwritten;
		ptr   += nwritten;
	}
	return(n);
}

/* I'm sorry, this is just too trivial to document */
/* Eeehhh, but this fact is now documented. */
/* TODO convert into #define */
void string_write(int fd, char *string) {
	numbered_write(fd,string,strlen(string));
}

/* create a listen socket at the specified port. 		 */
/* returns only a valid socket fd, exits with error() in case of */
/* failure. 							 */
int create_socket(int port) {
	int	sock;
	struct sockaddr_un	servaddr;

	/* STREAM should be DGRAM, but listen should then be ommited */
	if ( (sock=socket(AF_LOCAL, SOCK_STREAM, 0)) < 0) {
		error("could not create socket");
	}
	
	unlink(UNIXSOCKETPATH);
	bzero(&servaddr, sizeof(servaddr));
	servaddr.sun_family     = AF_LOCAL;
	strcpy(servaddr.sun_path, UNIXSOCKETPATH);

	if (bind(sock, &servaddr, sizeof(servaddr)) < 0) {
		error("no binding to server address");
	}

	if (listen(sock, LISTENQ) < 0) {
		error("listen failed");
	}
	return(sock);
}

int main(int argc, char **argv) {
	int				option, i, x, maxi, maxfd, listenfd, connfd, sockfd;
	int				nready, client[FD_SETSIZE];
	ssize_t				n;
	fd_set				rset, allset;
	char				line[MAXLINE];
	socklen_t			clilen;
	/* struct sockaddr_in		cliaddr; */
	struct sockaddr_un		cliaddr;
	struct timeval			timeout;
	long				passed_time, port=SERV_PORT;

	while ((option=getopt(argc,argv,"ap:vsh")) >= 0) {
		switch(option) {
			case 'a':
				additive=1;	/* additive mode */
				break;
			case 'p':
				my_atol(optarg,&port);
				break;
			case 's':
				scaling=1;	/* enable voltage scaling */
				break;
			case 'v':
				verbose=1;	/* print more debug */
				break;
			case 'h':
				printf("usage: -p <portnum> change default port of 6666\n");
				printf("       -s           scaling of frequency and voltage\n");
				printf("       -v           print debugging information\n");
				printf("       -a           simple additive mode, ignores start times, does not re-schedule\n");
				exit(0);
		}
	}
	
	listenfd=create_socket(port);	/* create a listen socket */

	maxfd = listenfd;			/* initialize */
	maxi = -1;				/* index into client[] array */
	for (i = 0; i < FD_SETSIZE; i++)
		client[i] = -1;			/* -1 indicates available entry */
	FD_ZERO(&allset);
	FD_SET(listenfd, &allset);

        /* now start the endless daemon loop ... */
	for ( ; ; ) {
		rset = allset;		/* structure assignment */

		if (additive==1)
			determine_clock_schedule_additive(&timeout);           /* DO THE SCHEDULING */
		passed_time=timeout.tv_sec*1000000+timeout.tv_usec;
		if (passed_time==0) {		/* do we have a deadline to meet? */
			timeout.tv_sec=600;	/* schedule ourselfs 10 min or less from now */
			passed_time=timeout.tv_sec*1000000;
		} 

		if ( (nready = select(maxfd+1, &rset, NULL, NULL, NULL)) < 0)
			error("select failed");
		/* passed_time-=timeout.tv_sec*1000000+timeout.tv_usec;
		advance_time(passed_time);
*/

		if (nready == 0) {		/* if only a timeout, no commands send */
			continue;
		}

		if (FD_ISSET(listenfd, &rset)) {	/* new client connection */
			clilen = sizeof(cliaddr);
			if ( (connfd = accept(listenfd, &cliaddr, &clilen)) < 0 ) {
				error("select failed");
			}
/*			if (verbose) 
				printf("new client: %s, port %d\n",
					inet_ntoa(cliaddr.sin_addr),
					ntohs(cliaddr.sin_port)); 
*/
                                        /* changed ntop to ntoa */
			for (i = 0; i < FD_SETSIZE; i++)
				if (client[i] < 0) {
					client[i] = connfd; /* save descriptor */
					break;
				}
			if (i == FD_SETSIZE)
				error("too many clients");
                        string_write(connfd,PROMPT);	/* send welcome to client */

			FD_SET(connfd, &allset);	/* add new descriptor to set */
			if (connfd > maxfd)
				maxfd = connfd;		/* for select arg1 */
			if (i > maxi)
				maxi = i;		/* max index in client[] array */

			if (--nready <= 0)
				continue;		/* no more readable descriptors */
		}

		for (i = 0; i <= maxi; i++) {		/* check all clients for data */
			if ( (sockfd = client[i]) < 0)
				continue;		/* nobody connected */
			if (FD_ISSET(sockfd, &rset)) {
				if ( (n = line_read(sockfd, line, MAXLINE)) == 0) {
					/* connection was closed by client */
					if (close(sockfd) < 0)
						warning("close problem");
					FD_CLR(sockfd, &allset);
					client[i] = -1;
					if (verbose) 
						printf("client unexpected exit.\n");
					error("no exit command given");	/* with this feature we exit and shell pipes are written */
				} else {		/* we have a valid line to process */
					if (process_command(sockfd, line, n) < 0) {
						/* client used the exit command */
						if (close(sockfd) < 0)
							warning("close problem");
						FD_CLR(sockfd, &allset);
						client[i] = -1;
						if (verbose) 
							printf("client exit.\n");
					}
					{ static int hack=0;
					if (hack==0) {
						for(x=0;x<16;x++) 						/* BIG && DIRTY DOCUMENTED HACK */
							if ( (n=line_read(sockfd, line, MAXLINE)) > 0)		/* also read multiple line cmd's */
								process_command(sockfd, line, n);
						energy_priority_scheduling();                 /* DO THE SCHEDULING */
					} else { hack=1; }
					}
				}
				if (--nready <= 0)
					break;		/* no more readable descriptors */
			}
		}
	}
}