[Linux-hls-cvs] hls/linux-2.6 Makefile,NONE,1.1 bottom.c,NONE,1.1 bottom.h,NONE,1.1 div.c,NONE,1.1 export.c,NONE,1.1 hls_ctl.c,NONE,1.1 hls_timers.c,NONE,1.1 init.c,NONE,1.1 misc.c,NONE,1.1 procfs.c,NONE,1.1 procfs.h,NONE,1.1 sched.c,NONE,1.1

[Luca A. <lu...@us...>]

Update of /cvsroot/linux-hls/hls/linux-2.6
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv10942

Added Files:
	Makefile bottom.c bottom.h div.c export.c hls_ctl.c 
	hls_timers.c init.c misc.c procfs.c procfs.h sched.c 
Log Message:
Beginning of a 2.6 backend... Does not work yet!


--- NEW FILE: init.c ---
/*
 * Copyright (c) 2002  Luca Abeni
 *
 * Module Name: init.c
 * Abstract: Module initialization and cleanup.
 * Author: Luca Abeni 2-Feb-2002
 *
 * This is free software; see GPL.txt
 */

#include <linux/config.h>
#if defined(CONFIG_MODVERSIONS) && !defined(MODVERSIONS)
#define MODVERSIONS
#endif
#ifdef MODVERSIONS
//#include <linux/modversions.h>
#endif
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/sched.h>

#include <data.h>

#include "hls_hooks.h"
#include "bottom.h"
#include "procfs.h"

#ifndef CONFIG_GENERIC_SCHEDULER
#error Generic Scheduler is not enabled!!!
#endif

extern void (*block_hook)(struct task_struct *tsk);
extern void (*unblock_hook)(struct task_struct *tsk);
extern void (*fork_hook)(struct task_struct *tsk);
extern void (*cleanup_hook)(struct task_struct *tsk);
extern int (*setsched_hook)(pid_t pid, int policy, struct sched_param *param);
extern int (*getsched_hook)(pid_t pid, struct sched_param *param);


#ifdef __LOG_DEVICE__
#include "logger.h"
#define hls_printk log_printf
#else
#define hls_printk printk
#endif

MODULE_LICENSE("GPL");

/* FIXME: These prototypes should be removed... */
int hls_setsched(pid_t pid, int policy, struct sched_param *param);
extern void HLSInit(void);
extern void HLSDeinit (void);

extern spinlock_t hls_lock;

void hls_convert_tasks(void)
{
  struct task_struct *dummy, *t;

  /* If all the tasks must be managed by the HLS, we must
   * ``transform'' all the existing tasks in HLS tasks...
   */
    
  t = current;
  if (t->private_data == NULL) {
    t->policy = SCHED_FIFO;
    t->rt_priority = HLS_IDLE_PRIORITY;
    if ((t->state == TASK_INTERRUPTIBLE) || (t->state == TASK_UNINTERRUPTIBLE)) {
      HLSCreateThreadHook(t, t->state);
    } else if (t->state == TASK_RUNNING) {
      HLSCreateThreadHook(t, TASK_UNINTERRUPTIBLE);
      t->state = TASK_RUNNING;
      HLSUnblockThreadHook(t);
    } else {
#ifdef VERBOSE
      hls_printk("state: %ld\n", t->state);
#endif
    }
  } else {
    printk("Error: It already is an HLS task!!!\n");
    hls_printk("Error: It already is an HLS task!!!\n");
  }
    
  read_lock(&tasklist_lock);
  do_each_thread(dummy, t) {
#ifdef __FP_DEAMONS__
    if (t->tty == NULL) {
#ifdef VERBOSE
      hls_printk("Giving T%d the highest priority\n", t->pid);
#endif
      t->policy = SCHED_FIFO;
      t->rt_priority = HLS_SCHEDULING_PRIORITY + 1;
      t->private_data = NULL;
    } else {
#endif
#ifdef VERBOSE
      hls_printk("Transforming T%d in HLS task\t", t->pid);
#endif
      if (t->private_data == NULL) {
        t->policy = SCHED_FIFO;
        t->rt_priority = HLS_IDLE_PRIORITY;
        if ((t->state == TASK_INTERRUPTIBLE) || (t->state == TASK_UNINTERRUPTIBLE)) {
          HLSCreateThreadHook(t, t->state);
        } else if (t->state == TASK_RUNNING) {
          HLSCreateThreadHook(t, TASK_UNINTERRUPTIBLE);
	  t->state = TASK_RUNNING;
	  HLSUnblockThreadHook(t);
        } else {
#ifdef VERBOSE
	  hls_printk("state: %ld\t", t->state);
#endif
	}
#ifdef VERBOSE
        hls_printk("ok!\n");
#endif
      } else {
        printk("already PRIVATE_DATA != NULL???\n");
        hls_printk("already PRIVATE_DATA != NULL???\n");
      }
#ifdef __FP_DEAMONS__
    }
#endif
  } while_each_thread(dummy, t);
  read_unlock(&tasklist_lock);
}

void hls_release_tasks(void)
{
  struct task_struct *dummy, *t;

  t = current;  
  read_lock(&tasklist_lock);
  do_each_thread(dummy, t) {
    if (t->private_data != NULL) {
#ifdef VERBOSE
      printk("Removing task %d from HLS\n", t->pid);
#endif
      
      if (t->state == TASK_RUNNING) {
        hls_block_other_thread(t);
      }
      HLSExitThreadHook(t);
      t->private_data = 0;
      t->policy = SCHED_NORMAL;
    }
  } while_each_thread(dummy, t);
  read_unlock(&tasklist_lock);
}

int init_module(void)
{
  int res;
  unsigned long flags;

  res= hls_proc_init();
  if (res < 0) {
    return res;
  }
  	
  if (block_hook != NULL) {
    printk("Error installing HLS: block_hook != NULL!!!\n");
    return -1;
  }
  if (unblock_hook != NULL) {
    printk("Error installing HLS: block_hook != NULL!!!\n");
    return -1;
  }
  if (fork_hook != NULL) {
    printk("Error installing HLS: fork_hook != NULL!!!\n");
    return -1;
  }
  if (cleanup_hook != NULL) {
    printk("Error installing HLS: cleanup_hook != NULL!!!\n");
    return -1;
  }

#ifdef __DO_CLI__
  spin_lock_irqsave(&hls_lock, flags);
#endif
  block_hook = hls_bottom_vp_release;
  unblock_hook = hls_bottom_vp_request;
  fork_hook = hls_bottom_vp_register;
  cleanup_hook = hls_bottom_vp_unregister;
  setsched_hook = hls_setsched;
 
  HLSInit();
  /*
   * ??? = hls_bottom_vp_msg;
   */
#ifdef __CREATE_HIERARCHY__
  hls_convert_tasks();
#endif
  
#ifdef __DO_CLI__
  spin_unlock_irqrestore(&hls_lock, flags);
#endif
  return 0;
}

void cleanup_module(void)
{
  unsigned long flags;

#ifdef __DO_CLI__
  spin_lock_irqsave(&hls_lock, flags);
#endif
  
  hls_release_tasks();
  HLSDeinit();
    
  block_hook = NULL;
  unblock_hook = NULL;
  fork_hook = NULL;
  cleanup_hook = NULL;
  setsched_hook = NULL;

  hls_proc_cleanup();
#ifdef __DO_CLI__
  spin_unlock_irqrestore(&hls_lock, flags);
#endif
}

--- NEW FILE: sched.c ---
/*
 * Copyright (c) 2002  Luca Abeni
 *
 * Module Name: sched.c
 * Abstract: Moves tasks between schedulers.
 * Author: Luca Abeni 2-Feb-2002
 *
 * This is free software; see GPL.txt
 */

static inline struct task_struct *find_process_by_pid(pid_t pid)
{
  struct task_struct *tsk = current;

  if (pid) {
    tsk = find_task_by_pid(pid);
  }
  
  return tsk;
}


/* Return value:
 * < 0 ---> Failure
 * = 0 ---> Success
 * > 0 ---> do the regular Linux thing...
 */
int hls_setsched(pid_t pid, int policy, struct sched_param *param)
{
  struct task_struct *p;
  struct hls_param hls_p;
  struct sched_param sched_p;
  unsigned long flags;
  int res;
  
  spin_lock_irqsave(&hls_lock, flags);
  p = find_process_by_pid(pid);
  if (p == NULL) {
    spin_unlock_irqrestore(&hls_lock, flags);
    return -ESRCH;
  }
  if (policy != HLS_CBS) {
    if (p->private_data != NULL) {
      HLSExitThreadHook(t);
      p->policy = SCHED_NORMAL;
      p->private_data = NULL;
    }
    
    spin_unlock_irqrestore(&hls_lock, flags);

    return 1;
  }

  if (copy_from_user(&sched_p, param, sizeof(struct sched_param)) < 0) {
    spin_unlock_irqrestore(&hls_lock, flags);

    return -EFAULT;
  }
  if (sizeof(struct hls_param) != sched_p.size) {
    spin_unlock_irqrestore(&hls_lock, flags);

    return -EFAULT;
  }
  if (copy_from_user(&hls_p, sched_p.p, sizeof(struct hls_param)) < 0) {
    spin_unlock_irqrestore(&hls_lock, flags);

    return -EFAULT;
  }
  /* Extra consinstency check... */
  if (hls_p.signature != HLS_SIGNATURE) {
    spin_unlock_irqrestore(&hls_lock, flags);

    return -EFAULT;
  }
  
  if (p->private_data == NULL) {
    printk("HLS Error: %d has private_data = NULL???\n", p->pid);
    spin_unlock_irqrestore(&hls_lock, flags);

    return -EINVAL;
  }
  
  res = HLSCtl(p, &hls_p);

  spin_unlock_irqrestore(&hls_lock, flags);

  return res;
}


--- NEW FILE: procfs.c ---
/*
 * Copyright (c) 2002  Luca Abeni
 *
 * Module Name: procfs.c
 * Abstract: ProcFS interface for HLS: allows to create scheduler
 *           instances and to build the schedulers hierarchy.
 * Author: Luca Abeni 2-Feb-2002
 *
 * This is free software; see GPL.txt
 */

#include <linux/config.h>
#if defined(CONFIG_MODVERSIONS) && !defined(MODVERSIONS)
#define MODVERSIONS
#endif
#ifdef MODVERSIONS
//#include <linux/modversions.h>
#endif
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/proc_fs.h>
#include <linux/slab.h>

#include <data.h>
#include <interface-data.h>
#include <hls_internal.h>

#include "procfs.h"

static struct proc_dir_entry *hls_dir, *schedulers_file,
	*instances_file, *tasks_file, *default_file, *rt_file;

#if 0
extern char *hls_scheduler_name(int i);
extern char *hls_instance_name(int i);
extern char *hls_instance_scheduler(int i);
extern char *hls_instance_father(int i);
extern struct HLS_SCHED_INSTANCE *HLSFindInstByName (char *Name);
extern struct HLS_SCHED_INSTANCE *HLSNewSchedInstance(char *SchedName,
		char *InstName, struct HLS_SCHED_INSTANCE *Parent);
extern void SetDefPriForSched(char Pri, struct HLS_SCHED_INSTANCE *Inst);
extern int hls_setparam_ascii(struct HLS_SCHED_INSTANCE *inst, char *param);
#endif

static int hls_proc_read_rt(char *p, char **s, off_t o,
		int c, int *eof, void *dummy)
{
  char *name;
  int len;
  
  name = hls_rt_name();
#if (HLS_DEBUG > 0)
  printk("Read %s (%d)\n", name, strlen(name));
#endif
  len = strlen(name) + 1;
  strcpy(p, name);

  return len;
}
static int hls_proc_write_rt(struct file *f, const char *b,
		unsigned long c, void *dummy)
{
  void *sched;
  char schedname[16];

  memcpy(schedname, b, c);
  schedname[c - 1] = 0;

  sched = HLSFindInstByName(schedname);

  if (sched == NULL) {
    printk("Cannot find %s\n", schedname);

    return c;
  }

  hls_setrt(sched);

  return c;
}

static int hls_proc_read_default(char *p, char **s, off_t o,
		int c, int *eof, void *dummy)
{
  char *name;
  int len;
  
  name = hls_default_name();
#if (HLS_DEBUG > 0)
  printk("Read %s (%d)\n", name, strlen(name));
#endif
  len = strlen(name) + 1;
  strcpy(p, name);

  return len;
}
static int hls_proc_write_default(struct file *f, const char *b,
		unsigned long c, void *dummy)
{
  void *sched;
  char schedname[16];

  memcpy(schedname, b, c);
  schedname[c - 1] = 0;

  if (memcmp(schedname, "null", 4)) {
    printk("Searching for %s\n", schedname);
    sched = HLSFindInstByName(schedname);

    if (sched == NULL) {
      printk("Cannot find %s\n", schedname);

      return c;
    }
  } else {
    printk("Schedname = NULL\n");
    sched = NULL;
  }

  hls_setdefault(sched);

  return c;
}

static int hls_proc_read_schedulers(char *p, char **s, off_t o,
		int c, int *eof, void *dummy)
{
  int l, len, i;
  char *name;
  
  len = 0; i = 0;
  MOD_INC_USE_COUNT;
  while((name = hls_scheduler_name(i)) != (char *)-1) {
    if (name != NULL) {
      l = sprintf(p, "%d %s\n", i, name);
      p += l;
      len += l;
    }
    i++;
  }
  MOD_DEC_USE_COUNT;
  
  return len;
}

static int hls_proc_write_instances(struct file *f, const char *b,
		unsigned long c, void *dummy)
{
  void *father_sched, *new_instance;
  char mybuff[64];
  char instname[16], schedname[16], fathername[16];
  int len, res;
  
  memcpy(mybuff, b, c);
  mybuff[c - 1] = 0;
#if (HLS_DEBUG > 0)
  printk("ProcFSed %s\n", mybuff);
#endif
  sscanf(mybuff, "%s %s %s %n", instname, schedname, fathername, &len);

#if (HLS_DEBUG > 0)
  printk("Creating %s of type %s and father %s\n", instname, schedname, fathername);
#endif
  
  father_sched = HLSFindInstByName(fathername);
  if (father_sched == NULL) {
    printk("Cannot find the parent scheduler\n");

    return c;
  }
  
  new_instance = HLSNewSchedInstance(schedname, instname, father_sched);
  if (new_instance == NULL) {
    printk("Creation failed!\n");

    return c;
  }
  
  SetDefPriForSched(1, new_instance);

  if ((len > 0) && (len < c)) {
#if (HLS_DEBUG > 0)
    printk("Read %d: remains %s\n", len, mybuff + len);
#endif
    res = hls_setparam_ascii(new_instance, mybuff + len);
    if (res < 0) {
      printk("Failed to set the scheduling parameters\n");
      /* FIXME: Maybe we should remove this instance... */
    }
  } else {
    res = hls_setparam_ascii(new_instance, NULL);
    if (res < 0) {
      printk("Failed to set the scheduling parameters\n");
      /* FIXME: Maybe we should remove this instance... */
    }
  }
  
  return c;
}
static int hls_proc_read_instances(char *p, char **s, off_t o,
		int c, int *eof, void *type)
{
  int l, len, i;
  char *name, *schedname, *father;
  
  len = 0; i = 0;
  MOD_INC_USE_COUNT;
  while((name = hls_instance_name(i)) != (char *)-1) {
    if (name != NULL) {
      schedname = hls_instance_scheduler(i);
      father = hls_instance_father(i);
#if 1
      if (((type == (void *)2) && (!strcmp(schedname, "thread"))) ||
			      ((type == (void *)1) && (strcmp(schedname, "thread")))) {
        l = sprintf(p, "%d %s %s %s\n", i, name, schedname, father);
        p += l;
        len += l;
      }	
#else
      l = sprintf(p, "%d %s %s\n", i, name, schedname);
      p += l;
      len += l;
#endif
    }
    i++;
  }
  MOD_DEC_USE_COUNT;
  
  return len;
}

int hls_proc_init(void)
{
  hls_dir = proc_mkdir("HLS", NULL);
  if(hls_dir == NULL) {
    return -ENOMEM;
  }
  hls_dir->owner = THIS_MODULE;
  schedulers_file = create_proc_read_entry("schedulers", 0444, hls_dir,
		  hls_proc_read_schedulers, NULL);
  if(schedulers_file == NULL) {
    remove_proc_entry("HLS", NULL);
    return -ENOMEM;
  }
  schedulers_file->owner = THIS_MODULE;

  instances_file = create_proc_entry("instances", 0644, hls_dir);
  if(instances_file == NULL) {
    remove_proc_entry("schedulers", hls_dir);
    remove_proc_entry("HLS", NULL);
    
    return -ENOMEM;
  }
  instances_file->data = (void *)1;
  instances_file->read_proc = hls_proc_read_instances;
  instances_file->write_proc = hls_proc_write_instances;
  instances_file->owner = THIS_MODULE;
  
  tasks_file = create_proc_read_entry("tasks", 0444, hls_dir,
		  hls_proc_read_instances, (void *)2);
  if(tasks_file == NULL) {
    remove_proc_entry("instances", hls_dir);
    remove_proc_entry("schedulers", hls_dir);
    remove_proc_entry("HLS", NULL);
    
    return -ENOMEM;
  }
  tasks_file->owner = THIS_MODULE;

  default_file = create_proc_entry("default", 0644, hls_dir);
  if(default_file == NULL) {
    remove_proc_entry("tasks", hls_dir);
    remove_proc_entry("instances", hls_dir);
    remove_proc_entry("schedulers", hls_dir);
    remove_proc_entry("HLS", NULL);
    
    return -ENOMEM;
  }
  default_file->data = NULL;
  default_file->read_proc = hls_proc_read_default;
  default_file->write_proc = hls_proc_write_default;
  default_file->owner = THIS_MODULE;
  
  rt_file = create_proc_entry("rt", 0644, hls_dir);
  if(rt_file == NULL) {
    remove_proc_entry("default", hls_dir);
    remove_proc_entry("tasks", hls_dir);
    remove_proc_entry("instances", hls_dir);
    remove_proc_entry("schedulers", hls_dir);
    remove_proc_entry("HLS", NULL);
    
    return -ENOMEM;
  }
  rt_file->data = NULL;
  rt_file->read_proc = hls_proc_read_rt;
  rt_file->write_proc = hls_proc_write_rt;
  rt_file->owner = THIS_MODULE;
  
  return 0;
}

void hls_proc_cleanup(void)
{
  remove_proc_entry("rt", hls_dir);
  remove_proc_entry("default", hls_dir);
  remove_proc_entry("tasks", hls_dir);
  remove_proc_entry("instances", hls_dir);
  remove_proc_entry("schedulers", hls_dir);
  remove_proc_entry("HLS", NULL);
}

--- NEW FILE: misc.c ---
unsigned char KiFindLeftNibbleBitTable[] = {0, 0, 1, 1, 2, 2, 2, 2,
                                    3, 3, 3, 3, 3, 3, 3, 3};


--- NEW FILE: hls_timers.c ---
/*
 * Copyright (c) 2002  Luca Abeni & John Regehr
 *
 * Module Name: hls_timers.c
 * Abstract: Kernel-dependent part of the timers mechanism.
 * Author: Luca Abeni 2002, John Regehr 2000
 *
 * This is free software; see GPL.txt
 */

#include <hls_common.h>		/* For struct HLS_SCHED_INSTANCE */

extern spinlock_t hls_lock;
/*
 * expiring scheduler timers call this function
 */

void hls_timeout(unsigned long arg)
{
  struct HLS_SCHED_INSTANCE *Sched;

#ifdef __DO_CLI1__
  spin_lock_irqsave(&hls_lock, flags);
#endif
  Sched = (struct HLS_SCHED_INSTANCE *) arg;

  if (current->state != TASK_RUNNING) {
    /* hls_printk("Interrupting a blocking call??? [%d]\n", current->pid); */
  }

  Sched->CB->I_TimerCallback(Sched);
#ifdef __DO_CLI1__
  spin_unlock_irqrestore(&hls_lock, flags);
#endif
}

void hls_stop_timer(struct HLS_SCHED_INSTANCE *Sched)
{
    del_timer_sync(&(Sched->HLSTimer));
}

void HLSSetTimer (_int64 T1, struct HLS_SCHED_INSTANCE *Sched)
{
  _int64 T;

/* Timer debugging stuff... */
  if (timer_pending(&Sched->HLSTimer)) {
	  /* ERROR!!! Timer Posted twice! */
    extern int whereami;
    hls_hard_printk("HLS ERROR: Scheduler %s posted a timer twice!!! WAI = %d\n",
		    Sched->Name, whereami);
    return;
  }
  
  T = -T1;
  if (T < 0) {
    panic("Strange timer...");
  }
#ifdef __MULDIV__
  Sched->HLSTimer.expires = jiffies + llimd(T, HZ, 10000000);
#else
  Sched->HLSTimer.expires = jiffies + (T * HZ) / 10000000;
#endif
  if (Sched->HLSTimer.expires == jiffies) {
    Sched->HLSTimer.expires++;
  }
  Sched->HLSTimer.data = (unsigned long)Sched;
  Sched->HLSTimer.function = hls_timeout;

  add_timer(&(Sched->HLSTimer));
}

WNT_TIME HLSGetCurrentTime (void)
{
    /* FIXME: For the moment, we are using gettimeofday...
     * but we can do something smarter!
     */
#if 0
  WNT_TIME t = HLSReadTimeStamp ();

  HLS_ASSERT (NTtoTicks != 0);
  return t / NTtoTicks;
#else
  struct timeval tv;
  WNT_TIME res;
  
  do_gettimeofday(&tv);
  res = ((WNT_TIME)tv.tv_usec * 10) + (WNT_TIME)(tv.tv_sec * 10000000);
  return res;
#endif
}



--- NEW FILE: bottom.h ---
#ifndef __BOTTOM_H__
#define __BOTTOM_H__

extern void hls_bottom_vp_request(struct task_struct *t);
extern void hls_bottom_vp_release(struct task_struct *t);
extern void hls_bottom_vp_register(struct task_struct *t);
extern void hls_bottom_vp_unregister(struct task_struct *t);

#endif /* __BOTTOM_H__ */

--- NEW FILE: bottom.c ---
/*
 * Copyright (c) 2002  Luca Abeni
 *
 * Module Name: bottom.c
 * Abstract: This is the low level interface with the Linux kernel,
 *           containing the hooks called by the gensched patch and the
 *           functions used to schedule a task in Linux.
 * Author: Luca Abeni 2-Feb-2002
 *
 * This is free software; see GPL.txt
 */

#include <interface-funcs.h>
#include <linux/smp_lock.h>
#include <linux/kernel.h>
#include <linux/sched.h>

#include "data.h"
#include "interface-data.h"
#include "hls_hooks.h"
#include "bottom.h"
#include "hls_internal.h"

#ifndef CONFIG_GENERIC_SCHEDULER
#error Generic Scheduler is not enabled!!!
#endif

/* #define VERBOSE1 */

struct HLS_PROC {
  void *CurrentThread;
  int Standby;
};
static struct task_struct *my_current[MAXIMUM_PROCESSORS];

extern struct HLS_PROC HLSProc[MAXIMUM_PROCESSORS];

spinlock_t hls_lock __cacheline_aligned = SPIN_LOCK_UNLOCKED;  /* inner */

static int wup, lastt;
extern int whereami;

void show_tasks(void);
/* CHECKME: Must acquire rq lock, somewhere... */
void HLSScheduleThread(struct task_struct *t, unsigned long proc)
{
  int sched_non_running;
  
  sched_non_running = 0;
  if (my_current[proc] != NULL) {
    struct task_struct *c;

    c = my_current[proc];
#ifdef VERBOSE
    hls_printk("setting %d to %d... ", current->pid, HLS_IDLE_PRIORITY);
#endif
    if (c->rt_priority != HLS_SCHEDULING_PRIORITY) {
      printk("HLS ERROR!!! Deschedulign %d with rt_priority = %ld != %d\n",
		      c->pid, c->rt_priority, HLS_SCHEDULING_PRIORITY);
    }
/* Must be implemented in some way... */
#error TODO: Do something smart, here!!!
    c->rt_priority = HLS_IDLE_PRIORITY;
    c->prio = MAX_PRIO;
array = c->array;
array->nr_active--;
list_del(&c->run_list);
if (list_empty(array->queue + c->prio))
__clear_bit(c->prio, array->bitmap);
  } else {
#ifdef VERBOSE
    hls_printk("HLS From idle...\n");
#endif
  }

#ifdef VERBOSE
  hls_printk("current->rt_priority = %ld\n", current->rt_priority);
#endif

  my_current[proc] = t;
  /* Do we have a new task to schedule? */
  if (t != NULL) {
    sched_non_running = (t->state != TASK_RUNNING);
    if(t->policy != SCHED_FIFO) {
      printk("HLS ERROR: Scheduling an HLS task with policy != SCHED_FIFO...\n");
      hls_printk("HLS ERROR: Scheduling an HLS task with policy != SCHED_FIFO...\n");
    }
    /* Yes... Schedule it.
     * The linux dispatcher will do the dirty work for us...
     */
    t->rt_priority = HLS_SCHEDULING_PRIORITY;
    HLSProc[proc].CurrentThread = t->private_data;
    c->prio = 0;
/* FIXME! */
repeat_lock_task:
    local_irq_save(rq_flags);
    rq = task_rq(c);
    spin_lock(&rq->lock);
    if (unlikely(rq != task_rq(p))) {
      spin_unlock_irqrestore(&rq->lock, rq_flags);
      goto repeat_lock_task;
    }
    array = rq->active;
list_add_tail(&c->run_list, array->queue + c->prio);
__set_bit(c->prio, array->bitmap);
array->nr_active++;
c->array = array;


wup = t->pid;
  } else {
    HLSProc[proc].CurrentThread = NULL;
wup = -1;
  }

  set_tsk_need_resched(current);

  show_tasks();
  lastt = wup;

  if (sched_non_running) {
    printk("HLS ERROR: Trying to schedule %d with state = %ld\n",
		    t->pid, t->state);
  }
}

void hls_bottom_vp_request(struct task_struct *t)
{
  unsigned long flags;

#ifdef __DO_CLI__
  spin_lock_irqsave(&hls_lock, flags);
#endif
  
#ifdef VERBOSE
  hls_printk("\nTask %d unblocks (requests the VP)", t->pid);
#endif
  HLSUnblockThreadHook(t);

#ifdef VERBOSE
  hls_printk(" --- DONE the unblock of %d\n\n", t->pid);
#endif
#ifdef __DO_CLI__
  spin_unlock_irqrestore(&hls_lock, flags);
#endif
}

void hls_bottom_vp_release(struct task_struct *t)
{
  unsigned long flags;
  long int initial_state;

#ifdef __DO_CLI__
  spin_lock_irqsave(&hls_lock, flags);
#endif
 
  initial_state = t->state;
  if (t->state == TASK_RUNNING) {
    printk("HLS HYPER-ERROR!!! Blocking %d with state == %ld\n",
		    t->pid, t->state);
    hls_printk("HLS HYPER-ERROR!!! Blocking %d with state == %ld\n",
		    t->pid, t->state);
  }
#ifdef VERBOSE
  hls_printk("\nTask %d blocks [state %ld] (releases the VP)", t->pid,
		  t->state);
  hls_printk("State again (before calling): %ld\n", t->state);
#endif
  HLSBlockThreadHook(t);
  
#ifdef VERBOSE
  hls_printk(" --- DONE the block of %d [state %ld]\n\n", t->pid, t->state);
#endif
  if (initial_state != t->state) {
    hls_printk("HLS ERROR!!! Task state changed during the hook??? %ld != %ld!!! Correcting...\n",
		    t->state, initial_state);
    t->state = initial_state;
  }
#ifdef __DO_CLI__
  spin_unlock_irqrestore(&hls_lock, flags);
#endif
}

void hls_bottom_vp_register(struct task_struct *t)
{
  unsigned long flags;

  if (!strcmp(hls_default_name(), "")) {
    t->private_data = NULL;

    return;
  }
#ifdef __DO_CLI__
  spin_lock_irqsave(&hls_lock, flags);
#endif
  
#ifdef VERBOSE
  hls_printk("\nCreated task %d   ", t->pid);
  hls_printk("HLS parameter is: 0x%lx\n", (unsigned long int)t->hls);
#endif
  if (t->state != TASK_UNINTERRUPTIBLE) {
    printk("HLS ERROR: Creating task with unexpected state: %ld\n", t->state);
    hls_printk("HLS ERROR: Creating task with unexpected state: %ld\n", t->state);
    return;
  }
  t->policy = SCHED_FIFO;
  t->rt_priority = HLS_IDLE_PRIORITY;
  HLSCreateThreadHook(t, t->state);
  
#ifdef VERBOSE
  hls_printk(" --- DONE the creation of %d\n\n", t->pid);
#endif
#ifdef __DO_CLI__
  spin_unlock_irqrestore(&hls_lock, flags);
#endif
}

void hls_bottom_vp_unregister(struct task_struct *t)
{
  unsigned long flags;

#ifdef __DO_CLI__
  spin_lock_irqsave(&hls_lock, flags);
#endif
  
#ifdef VERBOSE
  hls_printk("\n%d exits (Unregisters the VP) \n", t->pid);
#endif
  if (t->private_data != NULL) {
    HLSExitThreadHook(t);
    t->policy = SCHED_NORMAL;
  }
  
#ifdef VERBOSE
  hls_printk(" --- DONE the end of %d\n\n", t->pid);
#endif
#ifdef __DO_CLI__
  spin_unlock_irqrestore(&hls_lock, flags);
#endif
}

void show_tasks(void)
{
  struct task_struct *dummy, *t;
  int active;

  active = 0;

  read_lock(&tasklist_lock);
  do_each_thread(dummy, t) {
#ifdef VERBOSE1
    hls_printk("T%d:\t", t->pid);
#endif

    if (t->private_data) {
#ifdef VERBOSE1
      hls_printk("HLS ");
#endif
      if (t->rt_priority == HLS_SCHEDULING_PRIORITY) {
	if (t->state != TASK_RUNNING) {
	  printk("HLS ERROR: Task %d has rt_priority = %ld and state = %ld --- WAI = %d WUP = %d Last = %d\n",
			  t->pid, t->rt_priority, t->state,
			  whereami, wup, lastt);
	  hls_printk("HLS ERROR: Task %d has rt_priority = %ld and state = %ld\n",
			  t->pid, t->rt_priority, t->state);
	}
	active++;
      }
    } else {
#ifdef VERBOSE1
      hls_printk("non hls ");
#endif
    }

#ifdef VERBOSE1
    hls_printk("priority: %ld  policy: %ld  state: %ld\n",
		    t->rt_priority, t->policy, t->state);
#endif
  } while_each_thread(dummy, t);
  read_unlock(&tasklist_lock);
#if 0
  if (active > 1) {
    printk("Too many active tasks!!! Shutting HLS down...\n");
    for_each_task(t) {
#ifdef VERBOSE
printk("T%d\t", t->pid);
#endif
    if (t->private_data != NULL) {
#ifdef VERBOSE
printk("HLS!\t");
#endif
      HLSExitThreadHook(t);
      t->private_data = 0;
      t->policy = SCHED_NORMAL;
    }
#ifdef VERBOSE
printk("\n");
#endif
  }
  HLSDeinit();
    
  block_hook = NULL;
  unblock_hook = NULL;
  fork_hook = NULL;
  cleanup_hook = NULL;
  }
#else
  if (active > 1) {
    printk("HLS ERROR: Too many active tasks!!! But doing nothing...\n");
    hls_printk("HLS ERROR: Too many active tasks!!! But doing nothing...\n");
  }
#endif
#ifdef VERBOSE
  if (active == 0) {
    hls_printk("No active tasks?\n");
  }
#endif
}

--- NEW FILE: procfs.h ---
#ifndef __PROCFS_H__
#define __PROCFS_H__

int hls_proc_init(void);
void hls_proc_cleanup(void);
#endif	/* __PROCFS_H__ */

--- NEW FILE: hls_ctl.c ---
/*
 * Copyright (c) 2002  Luca Abeni & John Regehr
 *
 * Module Name: hls_ctl.c
 * Abstract: This file implements the user interface for HLS,
 *           allowing to move tasks between scheduler instances.
 * Author: Luca Abeni 2002, John Regehr 2000
 *
 * This is free software; see GPL.txt
 */

#include <hls_common.h>
#include <hls_internal.h>

#include <thr.h>
#include <hls.h>
#include <hls_hooks.h>


#define NOLINUX_TASKS

#define HLS_NAME_SIZE 256
#define HLS_PARMS_SIZE 256

struct hls_sched_param {
  struct sched_param sp;
  int size;
  void *p;
};

extern spinlock_t hls_lock;



static int hls_setparam(struct HLS_VPROC *vp, void *sched_params, int prio)
{
  struct hls_message NewMsg;
  
#ifdef HLS_DEBUG
  NewMsg.ObjType = RRMsgValue;
#endif
  NewMsg.body = sched_params;
  if (sched_params == NULL) {
    NewMsg.type = MSG_SETPRI;
  } else {
    NewMsg.type = MSG_SETPARAMS;
  }
  NewMsg.Pri = prio;
  
  return vp->TopSched->CB->B_Msg(NULL, vp, (MsgHandle)&NewMsg);
}

static int hls_null_msg(PRKTHREAD t)
{
  int status;
  struct hls_message NewMsg; 
  struct TH_INSTANCE_DATA *th;
  HLS_STATUS res;
  
  th = HLSFindThread (t);
  HLS_ASSERT (th);
      
#ifdef HLS_DEBUG
  NewMsg.ObjType = RRMsgValue;
#endif
  NewMsg.type = MSG_NULL;
  NewMsg.body = NULL;

  res = th->vp->TopSched->CB->B_Msg (NULL, th->vp, (MsgHandle)&NewMsg);
  if (res == HLS_SUCCESS) {
    status = 0;
  } else {
    status = -EINVAL;
  }      

  HLSDbgPrint (9, ("(infr) HLSNullMsg: done\n"));

  return status;
}

static int hls_thread_move(PRKTHREAD t, struct HLS_SCHED_INSTANCE *new_sched)
{
  struct HLS_SCHED_INSTANCE *th_inst;
  struct TH_INSTANCE_DATA *th, *th1;
  HLS_STATUS status;
  VPROC_STATE st;
  
  HLSDbgPrint (9, ("(infr) entering MoveThread\n"));
    
  th = HLSFindThread(t);

  if (!th) {
    HLSDbgPrint (1, ("MoveThread: HLSFindThread returned NULL\n"));
    return -EINVAL;
  }

  HLS_ASSERT (th->vp);
  HLS_ASSERT (th->vp->BottomSched);

  th_inst = th->vp->BottomSched;
  th1 = (struct TH_INSTANCE_DATA *)th_inst->SchedData;
/* FIXME: This was put in to check if th1 is always == th...
 * it seems that it is. So, we can remove the need for th1!
  if (th == th1) {
    printk("They are the same!!!\n");
  }
 */

  HLS_ASSERT (th1->ObjType == ThInstValue);
  
  HLSDbgPrint (3, ("(infr) moving thread %s from %s to %s\n",
		   th_inst->Name, th1->vp->TopSched->Name, new_sched->Name));
  
  st = th1->vp->State;
  RemoveThread (th1, th1->Thread, HLS_TRUE);
 
  HLSDbgPrint (3, ("(infr) removed\n"));
 
  HLS_ASSERT (th1->vp->State == VP_Waiting);
  th1->vp->TopSched = new_sched;
  
  status = th1->vp->TopSched->CB->B_RegisterVP(new_sched, th_inst, th1->vp);
  HLS_ASSERT(status == HLS_SUCCESS);
  HLSDbgPrint(3, ("(infr) registered\n"));

  th_inst->Parent = new_sched;

  /* This cannot be done until the sched param are set...
  status = HLSSetPri(th1->Thread, HLS_DEFAULT_PRIORITY);
  HLS_ASSERT(status == HLS_SUCCESS);
  
  HLSDbgPrint (3, ("(infr) priority set to 1\n"));
  */

  return st;
}

void set_state(struct TH_INSTANCE_DATA *th, int st)		
{
  switch(st) {
  case VP_Ready:
  case VP_Running:
    HLSDbgPrint (3, ("(infr) ChangeDefault: requesting CPU for thread\n"));
    // th1->vp->State = VP_Ready;
    th->vp->TopSched->CB->B_VP_Request(th->vp);
    break;
  case VP_Waiting:
    HLSDbgPrint (3, ("(infr) ChangeDefault: thread is currently blocked\n"));
    th->vp->State = VP_Waiting;
    break;
  default:
    printk("HLS Error: Unexpected state!!!\n");
    HLS_ASSERT (0);
  }

  HLSDbgPrint (3, ("(infr) returning\n"));
}



/* TODO:
 * - in hls_ctl, Change hls_param *p ---> void *sp, HLS_SCHED_INSTANCE *target_sched
 * - add an hls_do_something_to_user_parms to get those vales...
 */
int hls_ctl(PRKTHREAD t, struct HLS_SCHED_INSTANCE *target_sched, void *s_p, int hls_priority)
{
  int status;
  /*
  void *s_p;
  struct HLS_SCHED_INSTANCE *target_sched;
  */
  struct TH_INSTANCE_DATA *th;
  int state;

#if 0
  if (p->command == HLS_CMD_NULL_MSG) {
    return hls_null_msg(t);
  }
#endif

#if 0
  target_sched = HLSFindInstByName(sched_name);
  if (!target_sched) {
    HLSDbgPrint (2, ("(infr) Cannot find scheduler %s\n", sched_name));
    return -EINVAL;
  }
#endif
 
  /* Find the task instance */
  th = HLSFindThread(t);
  if (!th) {
    HLSDbgPrint (2, ("(infr) oops - bad news; thread %d not found\n", t->pid));
    return -EINVAL;
  }

  /* Is it already the task's scheduler? */
  if (th->vp->TopSched == target_sched) {
    /* Yes: We simply do a setparm */
    HLSDbgPrint (9, ("(infr) hls_ctl: %s is already scheduled by %s; trying to update params\n",
		       ThreadStr(t), target_sched->Name));
    status = hls_setparam(th->vp, s_p, hls_priority);
    if (status == HLS_SUCCESS) {
      return 0;
    } else {
      return -EINVAL;
    }
  }
  
  /* We have to move to the new scheduler... */
#ifdef HLS_DEBUG
  hls_printk("hls_ctl: Moving to %s\n", target_sched->Name);
#endif
  state = hls_thread_move(t, target_sched);
  if (state < 0) {
    return -EINVAL;
  }
#ifdef HLS_DEBUG
  hls_printk("    ...and setting the parameters (Priority %d)!\n", hls_priority);
#endif
  status = hls_setparam(th->vp, s_p, hls_priority);
  if (status == HLS_SUCCESS) {
    set_state(th, state);

    return 0;
  } else {
    hls_printk("    hls_setparam failed :(\n");
    hls_thread_move(t, HLSDefaultSched);
    HLSSetPri(th->Thread, HLS_DEFAULT_PRIORITY);
    set_state(th, state);

    return -EINVAL;
  }

  return 0;
}

static int hls_parse_param(void *p, struct HLS_SCHED_INSTANCE **sched, void *parms)
{
  struct hls_sched_param sched_p;
  struct hls_param hls_p;
  static char sched_name[HLS_NAME_SIZE];
  
  if (copy_from_user(&sched_p, p, sizeof(struct hls_sched_param)) < 0) {

    return -EFAULT;
  }
  if (sizeof(struct hls_param) != sched_p.size) {

    return -EFAULT;
  }
  if (copy_from_user(&hls_p, sched_p.p, sizeof(struct hls_param)) < 0) {

    return -EFAULT;
  }
  /* Extra consinstency check... */
  if (hls_p.signature != HLS_SIGNATURE) {

    return -EFAULT;
  }
 
  if (hls_p.sched_data_size > HLS_PARMS_SIZE) {
    return -EFAULT;
  }
  if (hls_p.sched_data_size == 0) {
    memset(parms, 0, HLS_PARMS_SIZE);
  } else {
    if (copy_from_user(parms, hls_p.sched_data, hls_p.sched_data_size) < 0) {

      return -EFAULT;
    }
  }

  /* Check if there is room for the scheduler's name... */
  if (strlen(hls_p.scheduler) > HLS_NAME_SIZE) {
    return -EINVAL;
  }
  
  /* ...And get it!!! */
  memset(sched_name, 0, HLS_NAME_SIZE);
  if (copy_from_user(sched_name, hls_p.scheduler, strlen(hls_p.scheduler)) < 0) {

    return -EFAULT;
  }
  *sched = HLSFindInstByName(sched_name);
  if (!*sched) {
    printk("Cannot find scheduler %s\n", sched_name);
    
    return -EINVAL;
  }
  
  return sched_p.sp.sched_priority; 
}

static int hls_parse_priority(void *p)
{
  struct hls_sched_param sched_p;
  
  if (copy_from_user(&sched_p, p, sizeof(struct hls_sched_param)) < 0) {

    return -EFAULT;
  }
printk("Parse priority: %d\n", sched_p.sp.sched_priority);

  return sched_p.sp.sched_priority; 
}

static inline struct task_struct *find_process_by_pid(pid_t pid)
{
  struct task_struct *tsk = current;

  if (pid) {
    tsk = find_task_by_pid(pid);
  }
  
  return tsk;
}


/* Return value:
 * < 0 ---> Failure
 * = 0 ---> Success
 * > 0 ---> do the regular Linux thing...
 */
int hls_setsched(pid_t pid, int policy, struct sched_param *param)
{
  struct task_struct *p;
  unsigned long flags;
  char sp[HLS_PARMS_SIZE];
  char *sched_param = NULL;
  struct HLS_SCHED_INSTANCE *s;
  int res;
  int priority = HLS_DEFAULT_PRIORITY;
  int return_to_linux;
  
  spin_lock_irqsave(&hls_lock, flags);
  p = find_process_by_pid(pid);
  if (p == NULL) {
    spin_unlock_irqrestore(&hls_lock, flags);
    return -ESRCH;
  }

  return_to_linux = -1;
  if (policy != SCHED_HLS) {
    if (policy == SCHED_NORMAL) {
      if (p->private_data != NULL) {
#ifdef NOLINUX_TASKS
	s = HLSDefaultSched;
	priority = HLS_DEFAULT_PRIORITY;
#else
        HLSExitThreadHook(p);
        p->policy = SCHED_NORMAL;
        p->private_data = NULL;
	/* We return to use the linux scheduler...
	 * No need to set s & sched_param
	 */
        return_to_linux = 1;
#endif
      } else {
	/* Private data == NULL...
	 * - If NOLINUX_TASKS, transform in HLS
	 * - Otherwise, do nothing
	 */
#ifdef NOLINUX_TASKS
        p->policy = SCHED_FIFO;
        p->rt_priority = HLS_IDLE_PRIORITY;
        HLSCreateThreadHook(p, p->state);
#else
        printk("Policy %d != SCHED_HLS. Doing nothing... (already non-hls)\n", policy);
#endif
	/* We do not need to call hls_ctl...
	 * No need to set s & sched_param
	 */
        return_to_linux = 0;
      }
    } else {
      if (p->private_data == NULL) {
        /* Transform in HLS */
        p->policy = SCHED_FIFO;
        p->rt_priority = HLS_IDLE_PRIORITY;
        HLSCreateThreadHook(p, p->state);
      }
      /* Change scheduler to rt_sched */
      priority = hls_parse_priority(param);
      s = hls_rt_sched;
      if (priority >= HLS_MAXIMUM_PRIORITY) {
        priority = HLS_MAXIMUM_PRIORITY - 1;
      }
      if (priority < 1) {
        priority = 1;
      }
    }

    if (return_to_linux >= 0) {
      spin_unlock_irqrestore(&hls_lock, flags);

      return return_to_linux;
    }
  } else {
    priority = hls_parse_param(param, &s, sp);
    sched_param = sp;
    if (priority < 0) {
      spin_unlock_irqrestore(&hls_lock, flags);

      return priority;
    }
  }
  
  if (p->private_data == NULL) {
    printk("HLS Error: %d has private_data = NULL???\n", p->pid);
#ifdef NOLINUX_TASKS
    spin_unlock_irqrestore(&hls_lock, flags);

    return -EINVAL;
#else
    p->policy = SCHED_FIFO;
    p->rt_priority = HLS_IDLE_PRIORITY;
    HLSCreateThreadHook(p, p->state);
#endif
  }

  res = hls_ctl(p, s, sched_param, priority);
  
  spin_unlock_irqrestore(&hls_lock, flags);

  return res;
}


--- NEW FILE: Makefile ---
SCHED_MOD = ../hls/hls_sched_res.o ../hls/hls_sched_ps.o ../hls/hls_sched_rr.o

OBJS = ../hls/hls_sched_th.o ../hls/hls_hooks.o ../hls/hls_sched_root.o \
	../hls/hls_sched_join.o ../hls/hls_names.o hls_ctl.o \
	hls_timers.o ../hls/hls_debug.o ../hls/hls_init.o \
	../hls/hls_instances.o ../hls/hls_params.o \
	init.o bottom.o misc.o procfs.o

HLS = /root/src/NewGenSched/hls
HLS = $(SUBDIRS)/..
EXTRA_CFLAGS += -I $(HLS)/hls/include -I $(HLS)/linux/include

ifdef DEBUG
EXTRA_CFLAGS += -DHLS_DEBUG=$(DEBUG)
else
EXTRA_CFLAGS += -DHLS_DEBUG=0
endif

ifdef INT_SCHED
OBJS +=	$(SCHED_MOD)
EXTRA_CFLAGS += -D__INTERNAL_SCHEDULERS__
else
OBJS += export.o
endif

ifndef MULDIV
OBJS += div.o
else
EXTRA_CFLAGS += -D__MULDIV__
endif

ifdef FP
EXTRA_CFLAGS += -D__FP_DEAMONS__
endif

ifdef CLI
EXTRA_CFLAGS += -D__DO_CLI__
endif

ifdef LOG
EXTRA_CFLAGS += -I$(LOG)/include -D__LOG_DEVICE__
endif

ifdef CREATE
EXTRA_CFLAGS += -D__CREATE_HIERARCHY__
endif

obj-m = hls_module.o
hls_module-objs = $(OBJS)

include:
	$(MAKE) -C include ARCH=$(ARCH)

--- NEW FILE: export.c ---
/*
 * Copyright (c) 2002  Luca Abeni
 *
 * Module Name: export.c
 * Abstract: This file exports the HLS API to external HLS schedulers,
 *           when they are built as Linux modules.
 * Author: Luca Abeni 2-Feb-2002
 *
 * This is free software; see GPL.txt
 */

#include <interface-funcs.h>
#include <interface-data.h>

#ifdef HLS_DEBUG
#include <hls_debug.h>
#endif /* HLS_DEBUG */
#include <hls_interface.h>


EXPORT_SYMBOL(HLSRegisterScheduler);
EXPORT_SYMBOL(KiFindLeftNibbleBitTable);
EXPORT_SYMBOL(HLSNumProcs);
EXPORT_SYMBOL(HLSSetTimer);
EXPORT_SYMBOL(hls_stop_timer);
EXPORT_SYMBOL(HLSGetCurrentTime);

#ifdef HLS_DEBUG
EXPORT_SYMBOL(VPStateName);
EXPORT_SYMBOL(HLS_DBG_PRINT_LEVEL);
#endif /* HLS_DEBUG */

--- NEW FILE: div.c ---
/* This file contains parts of libgcc2.c, from gcc 2.95.3, which
 * is released under the following license
 */

/* More subroutines needed by GCC output code on some machines.  */
/* Compile this one with gcc.  */
/* Copyright (C) 1989, 92-98, 1999 Free Software Foundation, Inc.

This file is part of GNU CC.

GNU CC 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, or (at your option)
any later version.

GNU CC 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 GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

/* As a special exception, if you link this software with other files,
   some of which are compiled with GCC, to produce an executable,
   this software does not by itself cause the resulting executable
   to be covered by the GNU General Public License.
   This exception does not however invalidate any other reasons why
   the executable file might be covered by the GNU General Public License.  */

#define BITS_PER_UNIT 8	/* Check this!!! */

#define SI_TYPE_SIZE (sizeof (SItype) * BITS_PER_UNIT)

typedef int word_type __attribute__ ((mode (__word__)));

typedef unsigned int UDItype	__attribute__ ((mode (DI)));
typedef		 int DItype	__attribute__ ((mode (DI)));
typedef 	 int SItype	__attribute__ ((mode (SI)));
typedef unsigned int USItype	__attribute__ ((mode (SI)));
#if LIBGCC2_WORDS_BIG_ENDIAN
  struct DIstruct {SItype high, low;};
#else
  struct DIstruct {SItype low, high;};
#endif

typedef union
{
  struct DIstruct s;
  DItype ll;
} DIunion;

#define count_leading_zeros(count, x) \
  do {									\
    USItype __cbtmp;							\
    __asm__ ("bsrl %1,%0"						\
	     : "=r" (__cbtmp) : "rm" ((USItype) (x)));			\
    (count) = __cbtmp ^ 31;						\
  } while (0)
#define udiv_qrnnd(q, r, n1, n0, d) \
  __asm__ ("divl %4"							\
	   : "=a" ((USItype) (q)),					\
	     "=d" ((USItype) (r))					\
	   : "0" ((USItype) (n0)),					\
	     "1" ((USItype) (n1)),					\
	     "rm" ((USItype) (d)))
#define sub_ddmmss(sh, sl, ah, al, bh, bl) \
  __asm__ ("subl %5,%1
	sbbl %3,%0"							\
	   : "=r" ((USItype) (sh)),					\
	     "=&r" ((USItype) (sl))					\
	   : "0" ((USItype) (ah)),					\
	     "g" ((USItype) (bh)),					\
	     "1" ((USItype) (al)),					\
	     "g" ((USItype) (bl)))
#define umul_ppmm(w1, w0, u, v) \
  __asm__ ("mull %3"							\
	   : "=a" ((USItype) (w0)),					\
	     "=d" ((USItype) (w1))					\
	   : "%0" ((USItype) (u)),					\
	     "rm" ((USItype) (v)))
UDItype
__udivmoddi4 (UDItype n, UDItype d, UDItype *rp)
{
  DIunion ww;
  DIunion nn, dd;
  DIunion rr;
  USItype d0, d1, n0, n1, n2;
  USItype q0, q1;
  USItype b, bm;

  nn.ll = n;
  dd.ll = d;

  d0 = dd.s.low;
  d1 = dd.s.high;
  n0 = nn.s.low;
  n1 = nn.s.high;

#if !UDIV_NEEDS_NORMALIZATION
  if (d1 == 0)
    {
      if (d0 > n1)
	{
	  /* 0q = nn / 0D */

	  udiv_qrnnd (q0, n0, n1, n0, d0);
	  q1 = 0;

	  /* Remainder in n0.  */
	}
      else
	{
	  /* qq = NN / 0d */

	  if (d0 == 0)
	    d0 = 1 / d0;	/* Divide intentionally by zero.  */

	  udiv_qrnnd (q1, n1, 0, n1, d0);
	  udiv_qrnnd (q0, n0, n1, n0, d0);

	  /* Remainder in n0.  */
	}

      if (rp != 0)
	{
	  rr.s.low = n0;
	  rr.s.high = 0;
	  *rp = rr.ll;
	}
    }

#else /* UDIV_NEEDS_NORMALIZATION */

  if (d1 == 0)
    {
      if (d0 > n1)
	{
	  /* 0q = nn / 0D */

	  count_leading_zeros (bm, d0);

	  if (bm != 0)
	    {
	      /* Normalize, i.e. make the most significant bit of the
		 denominator set.  */

	      d0 = d0 << bm;
	      n1 = (n1 << bm) | (n0 >> (SI_TYPE_SIZE - bm));
	      n0 = n0 << bm;
	    }

	  udiv_qrnnd (q0, n0, n1, n0, d0);
	  q1 = 0;

	  /* Remainder in n0 >> bm.  */
	}
      else
	{
	  /* qq = NN / 0d */

	  if (d0 == 0)
	    d0 = 1 / d0;	/* Divide intentionally by zero.  */

	  count_leading_zeros (bm, d0);

	  if (bm == 0)
	    {
	      /* From (n1 >= d0) /\ (the most significant bit of d0 is set),
		 conclude (the most significant bit of n1 is set) /\ (the
		 leading quotient digit q1 = 1).

		 This special case is necessary, not an optimization.
		 (Shifts counts of SI_TYPE_SIZE are undefined.)  */

	      n1 -= d0;
	      q1 = 1;
	    }
	  else
	    {
	      /* Normalize.  */

	      b = SI_TYPE_SIZE - bm;

	      d0 = d0 << bm;
	      n2 = n1 >> b;
	      n1 = (n1 << bm) | (n0 >> b);
	      n0 = n0 << bm;

	      udiv_qrnnd (q1, n1, n2, n1, d0);
	    }

	  /* n1 != d0...  */

	  udiv_qrnnd (q0, n0, n1, n0, d0);

	  /* Remainder in n0 >> bm.  */
	}

      if (rp != 0)
	{
	  rr.s.low = n0 >> bm;
	  rr.s.high = 0;
	  *rp = rr.ll;
	}
    }
#endif /* UDIV_NEEDS_NORMALIZATION */

  else
    {
      if (d1 > n1)
	{
	  /* 00 = nn / DD */

	  q0 = 0;
	  q1 = 0;

	  /* Remainder in n1n0.  */
	  if (rp != 0)
	    {
	      rr.s.low = n0;
	      rr.s.high = n1;
	      *rp = rr.ll;
	    }
	}
      else
	{
	  /* 0q = NN / dd */

	  count_leading_zeros (bm, d1);
	  if (bm == 0)
	    {
	      /* From (n1 >= d1) /\ (the most significant bit of d1 is set),
		 conclude (the most significant bit of n1 is set) /\ (the
		 quotient digit q0 = 0 or 1).

		 This special case is necessary, not an optimization.  */

	      /* The condition on the next line takes advantage of that
		 n1 >= d1 (true due to program flow).  */
	      if (n1 > d1 || n0 >= d0)
		{
		  q0 = 1;
		  sub_ddmmss (n1, n0, n1, n0, d1, d0);
		}
	      else
		q0 = 0;

	      q1 = 0;

	      if (rp != 0)
		{
		  rr.s.low = n0;
		  rr.s.high = n1;
		  *rp = rr.ll;
		}
	    }
	  else
	    {
	      USItype m1, m0;
	      /* Normalize.  */

	      b = SI_TYPE_SIZE - bm;

	      d1 = (d1 << bm) | (d0 >> b);
	      d0 = d0 << bm;
	      n2 = n1 >> b;
	      n1 = (n1 << bm) | (n0 >> b);
	      n0 = n0 << bm;

	      udiv_qrnnd (q0, n1, n2, n1, d1);
	      umul_ppmm (m1, m0, q0, d0);

	      if (m1 > n1 || (m1 == n1 && m0 > n0))
		{
		  q0--;
		  sub_ddmmss (m1, m0, m1, m0, d1, d0);
		}

	      q1 = 0;

	      /* Remainder in (n1n0 - m1m0) >> bm.  */
	      if (rp != 0)
		{
		  sub_ddmmss (n1, n0, n1, n0, m1, m0);
		  rr.s.low = (n1 << b) | (n0 >> bm);
		  rr.s.high = n1 >> bm;
		  *rp = rr.ll;
		}
	    }
	}
    }

  ww.s.low = q0;
  ww.s.high = q1;
  return ww.ll;
}

DItype __negdi2 (DItype u)
{
  DIunion w;
  DIunion uu;

  uu.ll = u;

  w.s.low = -uu.s.low;
  w.s.high = -uu.s.high - ((USItype) w.s.low > 0);

  return w.ll;
}

DItype __divdi3 (DItype u, DItype v)
{
  word_type c = 0;
  DIunion uu, vv;
  DItype w;

  uu.ll = u;
  vv.ll = v;

  if (uu.s.high < 0)
    c = ~c,
  uu.ll = __negdi2 (uu.ll);
  if (vv.s.high < 0)
    c = ~c,
    vv.ll = __negdi2 (vv.ll);

  w = __udivmoddi4 (uu.ll, vv.ll, (UDItype *) 0);
  if (c)
    w = __negdi2 (w);

  return w;
}