*** kern/kern_clock.c.orig	Tue May 30 12:45:40 1995
--- kern/kern_clock.c	Tue Jul 18 01:45:47 1995
***************
*** 81,86 ****
--- 81,94 ----
  /*
   * TODO:
   *	allocate more timeout table slots when table overflows.
+  *
+  *  With CALLWHEEL, this is going to be even more difficult than
+  *  before, because the sizes of callwheel and callhash are based
+  *  on ncallout.  If the maximum number of callouts is dynamically
+  *  increased, but callwheel and callhash are not replaced with larger
+  *  ones, performance could suffer.  Doing the replacement would require
+  *  allocating larger arrays, copying all the data, and freeing the old
+  *  arrays.  The clock would have to be locked out the entire time.
   */
  
  /*
***************
*** 100,106 ****
  int	stathz;
  int	profhz;
  int	profprocs;
! int	ticks;
  static int psdiv, pscnt;		/* prof => stat divider */
  int	psratio;			/* ratio: prof / stat */
  int	tickfix, tickfixinterval;	/* used if tick not really integral */
--- 108,118 ----
  int	stathz;
  int	profhz;
  int	profprocs;
! int	ticks;  /* Shouldn't this be declared in a header file? */
! #ifdef CALLWHEEL
! static int softticks;			/* Like ticks, but for softclock(). */
! static struct callout *nextsoftcheck;	/* Next callout to be checked. */
! #endif /* CALLWHEEL */
  static int psdiv, pscnt;		/* prof => stat divider */
  int	psratio;			/* ratio: prof / stat */
  int	tickfix, tickfixinterval;	/* used if tick not really integral */
***************
*** 142,151 ****
  {
  	register struct callout *p1;
  	register struct proc *p;
! 	register int delta, needsoft;
  	extern int tickdelta;
  	extern long timedelta;
  
  	/*
  	 * Update real-time timeout queue.
  	 * At front of queue are some number of events which are ``due''.
--- 154,167 ----
  {
  	register struct callout *p1;
  	register struct proc *p;
! 	register int delta;
! #ifndef CALLWHEEL
! 	register int needsoft;
! #endif /* CALLWHEEL */
  	extern int tickdelta;
  	extern long timedelta;
  
+ #ifndef CALLWHEEL
  	/*
  	 * Update real-time timeout queue.
  	 * At front of queue are some number of events which are ``due''.
***************
*** 164,169 ****
--- 180,186 ----
  		if (p1->c_time == 0)
  			break;
  	}
+ #endif  /* CALLWHEEL */
  
  	p = curproc;
  	if (p) {
***************
*** 216,222 ****
--- 233,243 ----
  	 * Process callouts at a very low cpu priority, so we don't keep the
  	 * relatively high clock interrupt priority any longer than necessary.
  	 */
+ #ifndef CALLWHEEL
  	if (needsoft) {
+ #else /* CALLWHEEL is defined */
+ 	if (callwheel[ticks & callwheelmask]) {
+ #endif /* CALLWHEEL */
  		if (CLKF_BASEPRI(frame)) {
  			/*
  			 * Save the overhead of a software interrupt;
***************
*** 227,235 ****
--- 248,352 ----
  		} else
  			setsoftclock();
  	}
+ #ifdef CALLWHEEL
+ 	else if (softticks + 1 == ticks) ++softticks;
+ #endif /* CALLWHEEL */
  }
  
+ #ifdef CALLWHEEL
  /*
+  * Hash table functions for finding callouts quickly.  The clock should
+  * be locked out when any of these are called (except callhash_hash, but
+  * that is only intended for use by the other functions anyway).
+  *
+  * int callhash_hash(void (*func)(void *), void *arg) computes an index
+  * into callhash given the function pointer and the argument pointer.
+  *
+  * void callhash_add(struct callout *c) adds the callout pointer to the
+  * table, in a place based on c->c_func and c->c_arg.
+  *
+  * void callhash_remove(struct callout *c) removes a callout pointer
+  * from the table.  Removing a callout pointer that isn't in the table
+  * is likely to corrupt the table and crash the kernel.
+  *
+  * callout *callhash_find(void (*func)(void *), void *arg) finds a
+  * callout pointer in the table given its c_func and c_arg fields.  If
+  * no matching callout is found, NULL is returned quickly.
+  */
+ 
+ #define DEFINE_HASH
+ #ifdef DEFINE_HASH
+ 
+ /* I'm not sure whether this define would be */
+ /* faster or slower than the function below. */
+ /* It requires unsigned long hash_tmp to be  */
+ /* declared in any function that uses it.    */
+ 
+ #define setup_hash() register unsigned long hash_tmp
+ 
+ #define callhash_hash(func,arg) \
+ 	(hash_tmp = (unsigned long) (arg) >> 2, \
+ 	 ((unsigned long) (func) >> 2 | hash_tmp | hash_tmp >> callhashbits \
+ 	 ) & callhashmask)
+ 
+ #else /* DEFINE_HASH is not defined */
+ 
+ #define setup_hash()
+ 
+ static unsigned long callhash_hash(func,arg)
+ 	void (*func) __P((void *));
+ 	void *arg;
+ {
+ 	register unsigned long r, a;
+ 
+ 	r = (unsigned long) func >> 2;
+ 	a = (unsigned long) arg >> 2;
+ 	r |= a;
+ 	return  (r  |  a >> callhashbits) & callhashmask;
+ }
+ 
+ #endif /* DEFINE_HASH */
+ 
+ static void callhash_add(c)
+ 	struct callout *c;
+ {
+ 	setup_hash();
+ 	register struct callout *p, **pp;
+ 
+ 	pp = callhash + callhash_hash(c->c_func, c->c_arg);
+ 	p = *pp;
+ 	if (p) p->hash_back = &c->hash_next;
+ 	c->hash_next = p;
+ 	*pp = c;
+ 	c->hash_back = pp;
+ }
+ 
+ static void callhash_remove(c)
+ 	struct callout *c;
+ {
+ 	register struct callout *t;
+ 
+ 	if ((t = c->hash_next) != NULL)
+ 		t->hash_back = c->hash_back;
+ 	*c->hash_back = t;
+ 	c->hash_back = NULL;
+ }
+ 
+ static struct callout *callhash_find(func,arg)
+ 	void (*func) __P((void *));
+ 	void *arg;
+ {
+ 	setup_hash();
+ 	register struct callout *c;
+ 
+ 	for (c = callhash[callhash_hash(func,arg)];
+ 	     c && (c->c_func != func || c->c_arg != arg);
+ 	     c = c->hash_next);
+ 	return c;
+ }
+ #endif /* CALLWHEEL */
+ 
+ /*
   * Software (low priority) clock interrupt.
   * Run periodic events from timeout queue.
   */
***************
*** 238,248 ****
--- 355,374 ----
  softclock()
  {
  	register struct callout *c;
+ #ifndef CALLWHEEL
  	register void *arg;
  	register void (*func) __P((void *));
+ #else /* CALLWHEEL is defined */
+ 	register int steps;		/* Number of steps taken since */
+ 					/* we last allowed interrupts. */
+ 	#ifndef MAX_SOFTCLOCK_STEPS
+ 	#define MAX_SOFTCLOCK_STEPS 100	/* Maximum allowed value of steps. */
+ 	#endif /* MAX_SOFTCLOCK_STEPS */
+ #endif /* CALLWHEEL */
  	register int s;
  
  	s = splhigh();
+ #ifndef CALLWHEEL
  	while ((c = calltodo.c_next) != NULL && c->c_time <= 0) {
  		func = c->c_func;
  		arg = c->c_arg;
***************
*** 253,258 ****
--- 379,436 ----
  		(*func)(arg);
  		(void) splhigh();
  	}
+ #else /* CALLWHEEL is defined */
+ 	steps = 0;
+ 	while (softticks != ticks) {
+ 		if (++steps >= MAX_SOFTCLOCK_STEPS) {
+ 			nextsoftcheck = NULL;
+ 			splx(s);
+ 			/* Give hardclock() a chance. */
+ 			(void) splhigh();
+ 			steps = 0;
+ 		}
+ 		c = callwheel[++softticks & callwheelmask];
+ 		while (c) {
+ 			if (c->c_time > 0) {
+ 				--c->c_time;
+ 				c = c->c_next;
+ 				if (++steps >= MAX_SOFTCLOCK_STEPS) {
+ 					nextsoftcheck = c;
+ 					splx(s);
+ 					/* Give hardclock() a chance. */
+ 					(void) splhigh();
+ 					c = nextsoftcheck;
+ 					steps = 0;
+ 				}
+ 			}
+ 			else {
+ 				if (nextsoftcheck = *c->c_back = c->c_next)
+ 					nextsoftcheck->c_back = c->c_back;
+ 				if (c->hash_back)
+ 					callhash_remove(c);
+ 				else {
+ 					if (++c->handle.lo == 0)
+ 						c->handle.hi += calloutsize;
+ 				}
+ 				splx(s);
+ 				c->c_func(c->c_arg);
+ 				(void) splhigh();
+ 				steps = 0;
+ 				c->c_next = callfree;
+ 				callfree = c;
+ 				c = nextsoftcheck;
+ 			}
+ 		}
+ 	}
+ 	nextsoftcheck = NULL;
+ 
+ 	/* What is this nextsoftcheck business?  It is visible to  */
+ 	/* untimeout() and unsetcallout().  It may not be the same */
+ 	/* after we lower and raise the interrupt level, because   */
+ 	/* untimeout() or unsetcallout() might have snuck in and   */
+ 	/* removed the next callout structure.                     */
+ 
+ #endif /* CALLWHEEL */
  	splx(s);
  }
  
***************
*** 268,273 ****
--- 446,490 ----
   *	value is returned from timeout, rather, the original arguments
   *	to timeout are used to identify entries for untimeout.
   */
+ 
+ #ifdef CALLWHEEL
+ /*
+  * timeout_guts --
+  *	Allocates a callout structure, fills it in, and puts it into
+  *	the callwheel.  Does not do anything with the hash table.
+  *	The clock should be locked out when timeout_guts() is called.
+  */
+ 
+ struct callout *
+ timeout_guts(ftn, arg, to_ticks)
+ 	void (*ftn) __P((void *));
+ 	void *arg;
+ 	register int to_ticks;
+ {
+ 	register struct callout *new, *p, **pp;
+ 
+ 	if (to_ticks <= 0) to_ticks = 1;
+ 
+ 	/* Fill in the next free callout structure. */
+ 	if (callfree == NULL)
+ 		panic("timeout table full");
+ 	new = callfree;
+ 	callfree = new->c_next;
+ 	new->c_arg = arg;
+ 	new->c_func = ftn;
+ 
+ 	new->c_time = to_ticks >> callwheelbits;
+ 	pp = callwheel + ((ticks + to_ticks) & callwheelmask);
+ 	p = *pp;
+ 	if (p) p->c_back = &new->c_next;
+ 	new->c_next = p;
+ 	*pp = new;
+ 	new->c_back = pp;
+ 
+ 	return new;
+ }
+ #endif /* CALLWHEEL */
+ 
  void
  timeout(ftn, arg, ticks)
  	void (*ftn) __P((void *));
***************
*** 274,284 ****
  	void *arg;
  	register int ticks;
  {
! 	register struct callout *new, *p, *t;
  	register int s;
  
! 	if (ticks <= 0)
! 		ticks = 1;
  
  	/* Lock out the clock. */
  	s = splhigh();
--- 491,502 ----
  	void *arg;
  	register int ticks;
  {
! #ifndef CALLWHEEL
! 	register struct callout *new, *p;
  	register int s;
+ 	register struct callout *t;
  
! 	if (ticks <= 0) ticks = 1;
  
  	/* Lock out the clock. */
  	s = splhigh();
***************
*** 311,323 ****
--- 529,574 ----
  	p->c_next = new;
  	new->c_next = t;
  	splx(s);
+ #else /* CALLWHEEL is defined */
+ 	register struct callout *new;
+ 	register int s;
+ 
+ 	s = splhigh();
+ 	new = timeout_guts(ftn,arg,ticks);
+ 	callhash_add(new);
+ 	splx(s);
+ #endif /* CALLWHEEL */
  }
  
+ #ifdef CALLWHEEL
+ /*
+  * untimeout_guts --
+  *	Removes a given callout structure from the callwheel, and puts
+  *	it back no the free list.  The clock should be locked out when
+  *	untimeout_guts(p) is called.
+  */
+ 
  void
+ untimeout_guts(p)
+ 	struct callout *p;
+ {
+ 	register struct callout *t;
+ 
+ 	if ((t = p->c_next) != NULL)
+ 		t->c_back = p->c_back;
+ 	*p->c_back = t;
+ 	p->c_next = callfree;
+ 	callfree = p;
+ 	if (nextsoftcheck == p) nextsoftcheck = t;
+ }
+ #endif /* CALLWHEEL */
+ 
+ void
  untimeout(ftn, arg)
  	void (*ftn) __P((void *));
  	void *arg;
  {
+ #ifndef CALLWHEEL
  	register struct callout *p, *t;
  	register int s;
  
***************
*** 335,343 ****
--- 586,663 ----
  			break;
  		}
  	splx(s);
+ #else /* CALLWHEEL is defined */
+ 	register struct callout *p;
+ 	register int s;
+ 
+ 	s = splhigh();
+ 	p = callhash_find(ftn,arg);
+ 	if (p) {
+ 		callhash_remove(p);
+ 		untimeout_guts(p);
+ 	}
+ 	splx(s);
+ #endif /* CALLWHEEL */
  }
  
+ #ifdef CALLWHEEL
  /*
+  * setcallout --
+  *	Like timeout(), but returns a handle to the callout.
+  *
+  * unsetcallout --
+  *	Like untimeout(), but takes a handle to the callout.
+  *
+  * This is an alternate interface, which may be used instead of
+  * timeout/untimeout if hard bounds on worst-case processing time are
+  * required.  Any callout created by setcallout() may be canceled by
+  * unsetcallout(), or just left to expire.  Calling unsetcallout() on
+  * a callout that has already expired, or already been canceled, is
+  * safe.  Calling unsetcallout() with a garbage handle is likely to
+  * crash the kernel.
+  */
+ 
+ struct callout_handle
+ setcallout(ftn, arg, ticks)
+ 	void (*ftn) __P((void *));
+ 	void *arg;
+ 	register int ticks;
+ {
+ 	register struct callout *new;
+ 	register int s;
+ 
+ 	s = splhigh();
+ 	new = timeout_guts(ftn,arg,ticks);
+ 	splx(s);
+ 	return new->handle;
+ }
+ 
+ void
+ unsetcallout(handle)
+ 	struct callout_handle handle;
+ {
+ 	register struct callout *p;
+ 	register int s;
+ 
+ 	s = splhigh();
+ 	p = callout + (handle.hi & calloutmask);
+ 	if (p->handle.lo == handle.lo && p->handle.hi == handle.hi) {
+ 		if (++p->handle.lo == 0)
+ 			p->handle.hi += calloutsize;
+ 		untimeout_guts(p);
+ 	}
+ 	/* /DEBUG\ */
+ 	#if 0
+ 	else printf("unsetcallout: invalid handle: lo = %lu, hi = %lu\n"
+ 		    "              mismatches:     lo = %lu, hi = %lu\n",
+ 		    handle.lo, handle.hi, p->handle.lo, p->handle.hi);
+ 	#endif
+ 	/* \DEBUG/ */
+ 	splx(s);
+ }
+ #endif /* CALLWHEEL */
+ 
+ /*
   * Compute number of hz until specified time.  Used to
   * compute third argument to timeout() from an absolute time.
   */
***************
*** 555,560 ****
--- 875,881 ----
  
  void db_show_callout(long addr, int haddr, int count, char *modif)
  {
+ #ifndef CALLWHEEL
  	register struct callout *p1;
  	register int	cum;
  	register int	s;
***************
*** 576,581 ****
                  db_printf("%9d %9d %8x  %s (%x)\n",
  			  cum, t, p1->c_arg, name, p1->c_func);
  	}
  	splx(s);
  }
! #endif
--- 897,927 ----
                  db_printf("%9d %9d %8x  %s (%x)\n",
  			  cum, t, p1->c_arg, name, p1->c_func);
  	}
+ #else /* CALLWHEEL is defined */
+ 
+ 	/* Warning:  This function hasn't actually been tested. */
+ 
+ 	register struct callout *c;
+ 	register int	s, i;
+ 	int		lowtime;
+ 	db_expr_t	offset;
+ 	char		*name;
+ 
+         db_printf("      ticks       arg  func\n");
+ 	s = splhigh();
+ 	for (i = 0;  i < callwheelsize;  ++i) {
+ 		lowtime = (i - softticks) & callwheelmask;
+ 		if (lowtime == 0) lowtime = callwheelsize;
+ 		for (c = callwheel[i];  c;  c = c->c_next) {
+ 			db_find_sym_and_offset((db_addr_t) p1->c_func,
+ 					       &name, &offset);
+ 			if (name == NULL) name = "?";
+                 	db_printf("%10d %8x  %s (%x)\n",
+ 			  	(c->c_time << callwheelbits) + lowtime,
+ 			  	c->c_arg, name, c->c_func);
+ 		}
+ 	}
+ #endif /* CALLWHEEL */
  	splx(s);
  }
! #endif /* DDB */