trt.c

Go to the documentation of this file.

/*--------------------------------------------------------------------
 *
 * (C) Copyright Koninklijke Philips Electronics NV 2006. 
 * All rights reserved. This software is licensed under the terms of
 * version 2.1 of the GNU Lesser General Public License as published 
 * by the Free Software Foundation. For licensing and warranty
 * information, see the file COPYING in the main directory.
 *
 *------------------------------------------------------------------*/

#include <setjmp.h>
#include <unistd.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <limits.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdarg.h>
#include <time.h>

#include "trt.h"

#define FIFO_READY_LIST   1

/******************************************************************************/

#ifndef MIN
#define MIN(a, b)   ((a) < (b) ? (a) : (b))
#endif

#ifndef MAX
#define MAX(a, b)   ((a) > (b) ? (a) : (b))
#endif

#define TRUE      1
#define FALSE     0

/*
 * processor table. one entry for each processor.
 */
extern processor_t trt_processor_table[TRT_MAX_NUM_PROCESSORS_PER_TILE];

/*
 * thread table. all threads in the system are in this table.
 */
extern thread_table_t trt_thread_table;

/*
 * number of processors in tile. incl. communication processors.
 */
extern int trt_num_processors;

/*
 * index of the tile we are running on.
 */
extern int trt_tile_idx;

/*
 * next ID to be assigned to thread.
 */
extern unsigned int trt_next_thread_ID;

/*
 * lock to do serial output
 */
extern int trt_serial_lock;

/*
 * pointer to the processor table entry for `this' processor.
 */
processor_t *current_processor;

#define current_thread    (get_current_processor()->running_thread)

enum purpose
{
  GENERAL, INPUT, OUTPUT, INPUT_OUTPUT, COPROC_CNTL, MAX_PURPOSE
};

/*
 * some forward decls
 */
static void debug_handler(int key);

/*
 * append member to list. lock but don't unlock!!
 */
#define append(list, member, ien)                                       \
{                                                                       \
  thread_t *__m = (member);         \
                  \
  ien = acquire_lock(list ## _lock, TRUE);      \
                  \
        __m->next = NULL;                                           \
                                                                        \
        if(list ## _head == NULL)                                       \
                list ## _head = __m;                                \
        else                                                            \
                list ## _tail->next = __m;                          \
                  \
        list ## _tail = __m;                                        \
}

/*
 * prepend member to list. lock but don't unlock!!
 */
#define prepend(list, member, ien)                                      \
{                                                                       \
        thread_t *__m = (member);                                       \
                                                                        \
        ien = acquire_lock(list ## _lock, TRUE);                        \
                                                                        \
        __m->next = list ## _head;          \
                  \
  if(__m->next == NULL)           \
    list ## _tail = __m;          \
                  \
  list ## _head = __m;            \
}

/*
 * unlink member from a (locked) list.
 */
#define unlink(list, member, prev_member)       \
{                 \
  if((prev_member))           \
    (prev_member)->next = (member)->next;     \
  else                \
    list ## _head = (member)->next;       \
                  \
  if((member)->next == NULL)          \
    list ## _tail = (prev_member);        \
}

/*
 * unlink head from a (locked) list.
 */
#define unlink_head(list, head)                                   \
{                                                                       \
  list ## _head = (head)->next;         \
}

/*
 * unlink tail from a (locked) list.
 */
#define unlink_tail(list)                                       \
{                                                                       \
  thread_t *t;              \
                  \
  if(list ## _head->next != NULL)         \
  {               \
    for(t = list ## _head; t->next->next; t = t->next)  \
      ;           \
                  \
    t->next = NULL;           \
    list ## _tail = t;          \
  }               \
  else                \
    list ## _head = NULL;         \
}

#define top_of_scheduler_stack()          \
(                 \
  &get_current_processor()->scheduler_stack[TRT_SCHEDULER_STACK_SIZE - 1]\
)

#define switch_to_scheduler_stack(fun, arg)       \
(                 \
  fun(arg)              \
)

int __bit_bucket;

/*
 * add thread to ready list
 */
static inline int add_to_ready_list(thread_t *thread, int keep_lock, int back)
{
  processor_t *p = thread->processor;
  int ien;

  if(back)
    append(p->ready_list, thread, ien)
  else
    prepend(p->ready_list, thread, ien)

  if(!keep_lock)
    release_lock(p->ready_list_lock, ien);

  /* p->domain->sleep_variable = 1; */

  return ien;
}

/*
 * divide idle_spin_count of all processors by 2.
 */
static void scale_spin_counts()
{
  processor_t *p;
  processor_t *p2 = get_current_processor();
  int i;

  for(i = 0; i < trt_num_processors; i++)
  {
    p = &trt_processor_table[i];

    if(p->domain != p2->domain)
      continue;

    atomic_srl(trt_processor_table[i].idle_spin_count, 1);
  }
}

/*
 * are all general purpose CPUs idle?
 */
int trt_is_idle()
{
  processor_t *p;
  int i;

  for(i = 0; i < trt_num_processors; i++)
  {
    p = &trt_processor_table[i];

    if(p->purpose != GENERAL)
      continue;

    if(p->running_thread != NULL || 
       p->schedule_me != NULL ||
       p->ready_list_head != NULL)
      return FALSE;
  }

  return TRUE;
}

/*
 * steal thread from another processor.
 */
static thread_t *steal_thread()
{
  thread_t *t;
  processor_t *victim = NULL, *p;
  int i, j, ien;
  domain_t *domain;

  domain = get_current_processor()->domain;
  i = get_current_processor()->index;

  for(j = 1; j < trt_num_processors; j++)
  {
    if(++i == trt_num_processors)       /* end of table? */
      i = 0;

    p = &trt_processor_table[i];

    if(p->domain != domain)
      continue;

    if(p->running_thread == NULL)   /* stop if p is also stealing */
      break;

    if(p->ready_list_head == NULL)  /* skip if p has nothing */
      continue;

    if(!victim || victim->idle_spin_count > p->idle_spin_count)
      victim = p;             /* select lowest spin count */
  }

  if(victim == NULL)                      /* nothing found? */
    return NULL;

  /* now try to get a thread from victim */

  ien = acquire_lock(victim->ready_list_lock, TRUE);

#if FIFO_READY_LIST
  if(t = victim->ready_list_head)
    unlink_head(victim->ready_list, t);
#else
  if(victim->ready_list_head)
  {
    t = victim->ready_list_tail;

    unlink_tail(victim->ready_list)
  }
  else
    t = NULL;
#endif

  release_lock(victim->ready_list_lock, ien);

  if(t != NULL)
  {
    t->processor = get_current_processor();

    if(atomic_sll(victim->idle_spin_count, 1) > 2500)
      scale_spin_counts();
  }

  return t;
}

/*
 * select a ready thread.
 */
static thread_t *select_thread()
{
  processor_t *p = get_current_processor();
  thread_t *t;
  int ien;

  /* before checking our ready list we check the schedule_me pointer
   * to see whether there is a thread that is forced to be scheduled
   * on this processor. */
  if(t = p->schedule_me)
  {
    release_lock_no_ien(p->schedule_me);

    goto exit;
  }

  /* (void) p->domain->sleep_variable; */

  /* lock our ready list */
  ien = acquire_lock(p->ready_list_lock, TRUE);

  /* let's see whether there is something in it */
  while((t = force_load(p->ready_list_head)) == NULL)
  {
    /* if not then release lock so that another processor can put
     * something in our ready list */
    release_lock(p->ready_list_lock, ien);

    /* wait for it */
    while(!force_load(p->ready_list_head))
    {
      if(t = p->schedule_me)
      {
        release_lock_no_ien(p->schedule_me);

        goto exit;
      }

      if(t = steal_thread())
      {
#if TRT_STATISTICS
        p->domain->num_thread_migrates++;
#endif  
        goto exit;
      }

      /* sws(p->domain->sleep_variable); */

      atomic_addi(p->idle_spin_count,1);

      if(p->idle_spin_count > 5000)
      {
        scale_spin_counts();
      
        if(p->idle_handler && trt_is_idle())
          p->idle_handler();
      }
    }

    /* there is something in our ready list. before we try
     * to grab it we first have to lock the list again. */
    acquire_lock(p->ready_list_lock, TRUE);
  }

  /* unlink first thread of our ready list. */
  unlink_head(p->ready_list, t);

  release_lock(p->ready_list_lock, ien);

exit:   return t;
}

#if defined(__hpux__) || defined(__sun__)
#define SAVE_CONTEXT(context)     _setjmp(context)
#define RESTORE_CONTEXT(context)  _longjmp(context, TRUE)
#else
#define SAVE_CONTEXT(context)     setjmp(context)
#define RESTORE_CONTEXT(context)  longjmp(context, TRUE)
#endif

#if defined(__linux__) && defined(__i386__)

#define SET_SP(context, sp) ((context)->__jmpbuf[4] = (int) (sp))
#define GET_SP(context)     ((context)->__jmpbuf[4])
#define ISA                 TRT_ISA_I386

#elif defined(__CYGWIN__) && defined(__i386__)

#define SET_SP(context, sp) ((context)[7] = (int) (sp))
#define GET_SP(context)     ((context)[7])
#define ISA                 TRT_ISA_I386

#elif defined(__sgi__) && defined(__mips__)

#define SET_SP(context, sp) ((context)[JB_SP] = (int) (sp))
#define GET_SP(context)     ((context)[JB_SP])
#define ISA                 TRT_ISA_MIPS

#elif defined(__sun__) && defined(__sparc__)

#define SET_SP(context, sp) ((context)[1] = (int) (sp))
#define GET_SP(context)     ((context)[1])
#define ISA                 TRT_ISA_SPARC

#elif defined(__hpux__) && defined(__hppa__)

#define SET_SP(context, sp) (((int *) (context))[1] = (int) (sp))
#define GET_SP(context)     (((int *) (context))[1])
#define ISA                 TRT_ISA_HPPA

#else
#error Sorry, your architecture is not supported
#endif

/*
 * select a ready thread and switch to it. don't save context of 
 * current thread. run block_handler prior to selection of a new thread.
 */
static void schedule_next_thread(void (*block_handler)())
{
#if TRT_STATISTICS
  get_current_processor()->domain->num_context_switches++;
#endif

  block_handler();

  current_thread = NULL;
  current_thread = select_thread();

  RESTORE_CONTEXT(current_thread->context.context);
}

/*
 * do a context switch. run block handler between the old and new thread.
 */
static void context_switch(int *unlock_me, int ien, void (*block_handler)())
{
  if(!SAVE_CONTEXT(current_thread->context.context))
  {
    if(unlock_me != NULL)
      release_lock(*unlock_me, ien);

    switch_to_scheduler_stack(schedule_next_thread, block_handler);
  }
}

static void empty_handler()
{
}

static int addr2isa(void *addr)
{
  return ISA;
}

static void thread_table_add(thread_t *thread)
{
  int ien;

  ien = acquire_lock(trt_thread_table.lock, TRUE);

  thread->next_table = NULL;
  thread->prev_table = trt_thread_table.tail;

  if(trt_thread_table.head == NULL)
    trt_thread_table.head = thread;
  else
    trt_thread_table.tail->next_table = thread;

  trt_thread_table.tail = thread;

  release_lock(trt_thread_table.lock, ien);
}

static void thread_table_remove(thread_t *thread)
{
  int ien;

  ien = acquire_lock(trt_thread_table.lock, TRUE);

  if(thread->prev_table == NULL)
    trt_thread_table.head = thread->next_table;
  else
    thread->prev_table->next_table = thread->next_table;

  if(thread->next_table == NULL)
    trt_thread_table.tail = thread->prev_table;
  else
    thread->next_table->prev_table = thread->prev_table;

  release_lock(trt_thread_table.lock, ien);
}

static void call_start_function()
{
  int arg, res, (*fun)(int);

  arg = current_thread->start_arg;
  fun = current_thread->start_fun;

  res = fun(arg);

  thr_exit(res);
}

static void set_sp(thread_t *thread, void *sp)
{
  SET_SP(thread->context.context, sp);
}

static char *isa_name(int isa)
{
  if(isa == TRT_ISA_MIPS)   return "MIPS";
  if(isa == TRT_ISA_I386)   return "i386";
  if(isa == TRT_ISA_SPARC)  return "Sparc";
  if(isa == TRT_ISA_HPPA)   return "HPPA";

  return "???";
}

static processor_t *find_processor(int isa)
{
  processor_t *p;
  int i;

  if(isa == ISA)
    return get_current_processor();

  for(i = 0; i < trt_num_processors; i++)
  {
    p = &trt_processor_table[i];

    if(p->domain->isa == isa && p->purpose == GENERAL)
      return p;
  }

  trt_panic_s("failed to find processor", isa_name(isa));

  return NULL;
}

void thr_create(thread_t *new_thread, int (*fun)(int), int arg)
{
  int isa = addr2isa(fun);

  if(trt_num_processors == 0) 
    trt_init(NULL, NULL);

  memset(new_thread, 0, sizeof(thread_t));
  new_thread->start_fun = fun;
  new_thread->start_arg = arg;
  new_thread->name = "noname";
  new_thread->processor = find_processor(isa);
  new_thread->id = atomic_add(trt_next_thread_ID, 1);

  thr_onblock(new_thread, NULL);

  thr_set_cache_ddr_domain(new_thread, 0, 0);

  sem_init(&new_thread->exit, 0, "exit");

  thread_table_add(new_thread);

  if(SAVE_CONTEXT(new_thread->context.context))
    call_start_function();
}

thread_t *thr_lookup(int id)
{
  thread_t *t;

  int ien;

  ien = acquire_lock(trt_thread_table.lock, TRUE);

  for(t = trt_thread_table.head; t && t->id != id; t = t->next_table)
    ;

  release_lock(trt_thread_table.lock, ien);

  return t;
}

typedef struct call_isa_s
{
  context_t context;              /* context to return to */
  int (*fun)(int, int, int, int); /* function to be called */
  int arg[4];                     /* arguments for it */
  int result;                     /* its result */
  void (*block_handler)();        /* saved block_handler */
  processor_t *processor;         /* processor that did thr_call_isa */
} call_isa_t;

static void call_function()
{
  call_isa_t *call_isa = (call_isa_t *) current_thread->exit_status;

  current_thread->block_handler = empty_handler;

  call_isa->result = call_isa->fun(call_isa->arg[0], call_isa->arg[1], 
                                    call_isa->arg[2], call_isa->arg[3]);

  current_thread->block_handler = call_isa->block_handler;
  current_thread->processor = call_isa->processor;
  current_thread->context = call_isa->context;

  add_to_ready_list(current_thread, FALSE, FIFO_READY_LIST);
 
  switch_to_scheduler_stack(schedule_next_thread, empty_handler);
}

int thr_isa(thread_t *thread)
{
  return ISA;
}

char *thr_isa_name(thread_t *thread)
{
  return isa_name(thr_isa(thread));
}

void thr_stack_size(thread_t *thread, int stack_size)
{
  int *stack_bot, *stack_top;

  if(stack_size == 0)
    stack_size = trt_config_stack_size;

  if(thread->stack)
    trt_free(thread->stack);

  thread->stack = trt_malloc(stack_size);
  stack_bot = thread->stack + 32;
        stack_top = thread->stack + (stack_size / sizeof(int)) - 32;

  assert(((long) stack_top & 3) == 0);
  assert(((long) stack_bot & 3) == 0);

#if defined(__hppa__)
  thread->stack_init_sp = stack_bot;
  thread->stack_magic = stack_top;
#else
  thread->stack_init_sp = stack_top;
  thread->stack_magic = stack_bot;
#endif

  thread->stack_magic[0] = TRT_STACK_OVERFLOW_MAGIC;
  thread->atexit.free_stack = TRUE;

  set_sp(thread, thread->stack_init_sp);
}

void thr_stack_addr(thread_t *thread, void *addr)
{
  static int stack_overflow_magic = TRT_STACK_OVERFLOW_MAGIC;

  thread->stack_init_sp = addr;
  thread->stack_magic = &stack_overflow_magic;

  set_sp(thread, thread->stack_init_sp);
}

static void thr_exit_cont()
{
  thread_t *curr = current_thread;
  int free_desc = curr->atexit.free_desc;
  int free_stack = curr->atexit.free_stack;

  static void *free_me = NULL;

  if(free_me != NULL)
    trt_free(free_me);

  free_me = curr->stack;

  sem_Vn(&curr->exit, 999999);

  if(free_desc)
    trt_free(curr);

  current_thread = NULL;

  schedule_next_thread(empty_handler);
}

void thr_exit(int exit_status)
{
  atexit_t *atexit = &current_thread->atexit;
  int i;

  current_thread->exit_status = exit_status;

  current_thread->block_handler();

  for(i = atexit->count - 1; i >= 0; i--)
    atexit->fun[i](atexit->arg[i]);

  if(current_thread->stack_magic[0] != TRT_STACK_OVERFLOW_MAGIC)
    trt_panic_s("Stack overflow", current_thread->name);

  thread_table_remove(current_thread);

  switch_to_scheduler_stack(thr_exit_cont, empty_handler);
}

void thr_destroy(thread_t *thread)
{
  int free_desc = thread->atexit.free_desc;
  int free_stack = thread->atexit.free_stack;

  if(thread->stack == NULL) /* already exited? */
    return;

  thread_table_remove(thread);

  if(free_stack)
    trt_free(thread->stack);

  thread->stack = NULL;

  sem_Vn(&thread->exit, 999999);

  if(free_desc)
    trt_free(thread);
}

void thr_atexit(thread_t *thread, void (*fun)(int), int arg)
{
  int i = thread->atexit.count++;

  assert(i < sizeof(thread->atexit.arg) / sizeof(int));

  thread->atexit.fun[i] = fun;
  thread->atexit.arg[i] = arg;
}

void thr_atexit_pop(thread_t *thread, int execute)
{
  int i = --thread->atexit.count;

  if(execute)
    thread->atexit.fun[i](thread->atexit.arg[i]);
}

void thr_onblock(thread_t *thread, void (*fun)(void))
{
  if(fun == NULL)
  {
    int isa = thread->processor->domain->isa;

    fun = (void (*)()) sym_query(isa, "$empty_handler", TRUE);
  }

  thread->block_handler = fun;
}

void trt_onidle(void (*handler)(void))
{
  processor_t *p;
  int i;

  for(i = 0; i < trt_num_processors; i++)
  {
    p = &trt_processor_table[i];

    if(p->domain->isa == ISA)
      p->idle_handler = handler;
  }
}

void thr_start(thread_t *thread)
{
  if(thread->stack == NULL)
    thr_stack_size(thread, trt_config_stack_size);

  add_to_ready_list(thread, FALSE, FIFO_READY_LIST);
}

static int search_ready_list(processor_t *processor, thread_t *thread)
{
  thread_t *t, *t_prev = NULL;
  int ien;

  ien = acquire_lock(processor->ready_list_lock, TRUE);

  for(t = processor->ready_list_head; t; t_prev = t, t = t->next)
  {
    if(t == thread)
      break;
  }

  if(t != NULL)
  {
    unlink(processor->ready_list, t, t_prev);
  }

  release_lock(processor->ready_list_lock, ien);

  return t != NULL;
}

static int search_blocked_list(semaphore_t *semaphore, thread_t *thread)
{
  thread_t *t = NULL, *t_prev = NULL;
  int ien;

  if(atomic_addi(semaphore->count, 1) < 0)
  {
    ien = acquire_lock(semaphore->blocked_lock, TRUE);

    for(t = semaphore->blocked_head; t; t_prev = t, t = t->next)
    {
      if(t == thread)
        break;
    }

    if(t != NULL)
      unlink(semaphore->blocked, t, t_prev); 

    release_lock(semaphore->blocked_lock, ien);
  }

  if(t == NULL)
    atomic_subi(semaphore->count, 1);

  return t != NULL;
}

void thr_suspend(thread_t *thread)
{
  processor_t *processor;
  semaphore_t *semaphore, suspend_point_sem;

  if(thread == current_thread || thread == NULL)
    context_switch(NULL, 0, current_thread->block_handler);
  else if(thread->suspension_mode == SUSPEND_DISABLE)
  {
    sem_init(&suspend_point_sem, 0, "suspend");

    thread->suspend_point_sem = &suspend_point_sem;

    sem_P(&suspend_point_sem);

    thread->suspend_point_sem = NULL;
  }
  else
  {
    while(TRUE)
    {
      if(semaphore = thread->blocked_on)
      {
        if(search_blocked_list(semaphore, thread))
        {
          thread->blocked_on = semaphore;
          return;
        }
      }

      if(processor = thread->processor)
      {
        if(search_ready_list(processor, thread))
        {
          thread->blocked_on = NULL;
          return;
        }
      }

      thr_switch();
    }
  }
}

void thr_resume(thread_t *thread)
{
  semaphore_t *semaphore = thread->blocked_on;
  int ien;

  if(semaphore != NULL && atomic_subi(semaphore->count, 1) <= 0)
  {
    append(semaphore->blocked, thread, ien);

    release_lock(semaphore->blocked_lock, ien);
  }
  else
  {
    thread->blocked_on = NULL;
  
    add_to_ready_list(thread, FALSE, FIFO_READY_LIST);
  }
}

int thr_suspend_mode(thread_t *thread, int suspension_mode)
{
  int old_suspension_mode = thread->suspension_mode;

  thread->suspension_mode = suspension_mode;

  return old_suspension_mode;
}

void thr_suspend_me()
{
  sem_V(current_thread->suspend_point_sem);

  context_switch(NULL, 0, current_thread->block_handler);
}

void thr_restart(thread_t *thread, int (*fun)(int), int arg)
{
  thread->blocked_on = NULL;

  if(fun != NULL)
  {
    thread->start_fun = fun;
    thread->start_arg = arg;
  }

  if(!SAVE_CONTEXT(thread->context.context))
  {
    set_sp(thread, thread->stack_init_sp);

    add_to_ready_list(thread, FALSE, FIFO_READY_LIST);
  }
  else
    call_start_function();
}

void thr_stop(thread_t *thread, int status)
{
  if(thread->stack != NULL)
    thr_restart(thread, (int (*)(int)) thr_exit, status);
}

void thr_switch()
{
  int *lock = &current_thread->processor->ready_list_lock;
  int ien;

  ien = add_to_ready_list(current_thread, TRUE, TRUE);
  
  context_switch(lock, ien, empty_handler);
}

void thr_join(thread_t *thread, int *exit_status)
{
  sem_P(&thread->exit);

  if(exit_status)
    *exit_status = thread->exit_status;
}

void thr_set_name(thread_t *thread, char *name)
{
  thread->name = name;
}

void trt_init_scheduling_domain(domain_t *domain, int isa)
{
  domain->isa = isa;
  domain->num_context_switches = 0;
  domain->num_thread_migrates = 0;
}

void trt_set_scheduling_domain(int processor_index, domain_t *domain)
{
  domain_t *domain_old = trt_processor_table[processor_index].domain;

  assert(domain_old->isa == domain->isa);

  trt_processor_table[processor_index].domain = domain;
}

domain_t *trt_scheduling_domain(int processor_index)
{
  return trt_processor_table[processor_index].domain;
}

void thr_migrate_domain(thread_t *thread, domain_t *domain)
{
  int i;

  assert(thread->processor->domain->isa == domain->isa);

  for(i = 0; i < trt_num_processors; i++)
  {
    if(trt_processor_table[i].domain == domain)
    {
#if TRT_STATISTICS
      trt_processor_table[i].domain->num_thread_migrates++;
#endif

      thread->processor = &trt_processor_table[i];

      if(thread == current_thread)
        thr_switch();

      return;
    }
  }
}

#if 0
/* header for old router */
#define ROUTE_HEADER(src, dst, dir0, dist0, dir1, dist1)    \
    ((dst) | ((src) << 8) | ((dist1) << 16) | ((dir1) << 21) |  \
              ((dist0) << 22) | ((dir0) << 27) | (5 << 28))
#endif

static volatile int num_tile_rows = 0;
static volatile int num_tile_cols = 0;
static volatile int num_tile_rows_cols_valid = FALSE;

int trt_num_tiles()
{
  return num_tile_rows * num_tile_cols;
}

#define K(n)  ((n) >> 10)
#define M(n)  ((n) >> 20)

void trt_init(int *stack_bot, int *stack_top)
{
  static domain_t domain = {ISA, 0, 0};
  static int stack_overflow_magic = TRT_STACK_OVERFLOW_MAGIC;
  static thread_t main_thread;
  processor_t *processor;
  int processor_index;

  processor_index = atomic_addi(trt_num_processors, 1);
  processor = &trt_processor_table[processor_index];

  assert(processor_index < TRT_MAX_NUM_PROCESSORS_PER_TILE);

  set_current_processor(processor);

  processor->index = processor_index;
  processor->purpose = GENERAL;
  processor->domain = &domain;

  current_thread = &processor->crt0_thread;
  current_thread->processor = processor;
  current_thread->name = "root";
  current_thread->stack = NULL;
  current_thread->block_handler = empty_handler;
  current_thread->id = atomic_add(trt_next_thread_ID, 1);
   
  thr_set_cache_ddr_domain(current_thread, 0, 0);

  if(stack_top != NULL)
  {
    current_thread->stack_magic = stack_bot + 1;
    current_thread->stack_magic[0] = TRT_STACK_OVERFLOW_MAGIC;
  }
  else
    current_thread->stack_magic = &stack_overflow_magic;

  thread_table_add(current_thread);

  /* at this point only one processor per isa will come by */
  
  sym_register("$call_start_function", call_start_function);
  sym_register("$call_function", call_function);
  sym_register("$empty_handler", empty_handler);

  num_tile_rows = MAX(1, num_tile_rows);
  num_tile_cols = MAX(1, num_tile_cols);
}

void trt_finalize(int status)
{
}

void sem_init(semaphore_t *semaphore, int init, char *name)
{
  semaphore->count = init;
  semaphore->blocked_head = NULL;
  semaphore->blocked_tail = NULL;
  semaphore->blocked_lock = FALSE;
  semaphore->name = name;
}

void sem_block_me(semaphore_t *semaphore)
{
  thread_t *curr = current_thread;
  int ien;

  append(semaphore->blocked, curr, ien);

  curr->blocked_on = semaphore;

  context_switch(&semaphore->blocked_lock, ien, curr->block_handler);
}

void sem_unblock_someone(semaphore_t *semaphore)
{
  thread_t *thread;
  int ien;

retry:  ien = acquire_lock(semaphore->blocked_lock, TRUE);

  thread = (thread_t *) semaphore->blocked_head;

  if(thread == NULL)
  {
    release_lock(semaphore->blocked_lock, ien);
    
    while(!force_load(semaphore->blocked_head))
      ;

    goto retry;
  }

  semaphore->blocked_head = thread->next;

  release_lock(semaphore->blocked_lock, ien);

  thread->blocked_on = NULL;

  add_to_ready_list(thread, FALSE, FIFO_READY_LIST);
}

#define atomic_sub_special(var, val, dec_leq0, dec, old_val)            \
{                                                                       \
  int new_val;                                                    \
                  \
  (old_val) = (var);                                              \
  (dec) = ((old_val) <= 0) ? (dec_leq0) : MIN((old_val), (val));  \
  new_val = (old_val) - (dec);          \
  (var) = new_val;            \
}

int sem_Pn(semaphore_t *semaphore, int n)
{
  thread_t *curr = current_thread;
  int dec, old_count, dummy, ien;

  atomic_sub_special(semaphore->count, n, 1, dec, old_count);

  if(old_count <= 0)
  {
    append(semaphore->blocked, curr, ien);

    curr->blocked_on = semaphore;

    context_switch(&semaphore->blocked_lock, ien, 
    curr->block_handler);

    atomic_sub_special(semaphore->count, n - 1, 0, dec, dummy);

    return 1 + dec;
  }
  else
    return dec;
}

void sem_Vn(semaphore_t *semaphore, int n)
{
  int old_count, ien;
  thread_t *thread;

  old_count = atomic_add(semaphore->count, n);

  if(old_count < 0)   /* were there any threads blocked? */
  {
    n = MIN(n, -old_count); /* determine how many to unblock */

    ien = acquire_lock(semaphore->blocked_lock, TRUE);

    while(n-- > 0)
    {
retry:      thread = (thread_t *) semaphore->blocked_head;

      if(thread == NULL)
      {
        release_lock(semaphore->blocked_lock, ien);
        
        while(!force_load(semaphore->blocked_head))
          ;

        acquire_lock(semaphore->blocked_lock, TRUE);

        goto retry;
      }

      semaphore->blocked_head = thread->next;

      thread->blocked_on = NULL;

      add_to_ready_list(thread, FALSE, FIFO_READY_LIST);
    }

    release_lock(semaphore->blocked_lock, ien);
  }
}

void thr_set_cache_ddr_domain(thread_t *thread, int cache_domain, 
                  int ddr_domain)
{
  thread->task_id = (thread->id & 0xffff) |
        ((cache_domain & 0x1f) << 16) |
        ((ddr_domain & 0x1f) << 21);
}

static void dump_processor_info(char *dummy)
{
  processor_t *p;
  thread_t *t;
  int i;

  serial_out("%18s ", "RUNNING");
  serial_out("%8s ", "WHERE");
  serial_out("%8s ", "ISA");
  serial_out("READY LIST\n");

  for(i = 0; i < trt_num_processors; i++)
  {
    p = &trt_processor_table[i];

    serial_out("%18s ", p->running_thread ? p->running_thread->name
                  : "-");
    serial_out("%8s ", isa_name(p->domain->isa));

    for(t = p->ready_list_head; t != NULL; t = t->next)
      serial_out("%s ", t->name);

    if(p->schedule_me)
      serial_out("%s ", p->schedule_me->name);

    serial_out("\n");
  }
}

static void dump_thread_info(char *dummy)
{
  thread_t *t;

  for(t = trt_thread_table.head; t; t = t->next_table)
    thr_dump_info(t, t == trt_thread_table.head);
}

static void dump_registry_info_R(char *dummy)
{
  sym_dump(TRUE);
}

static void dump_registry_info_r(char *dummy)
{
  sym_dump(FALSE);
}

void thr_dump_info(thread_t *thread, int header)
{
  if(header)
    serial_out("       P   BLOCKED       ISA  NAME\n");

  serial_out("%d  ", thread->processor->index);

  if(thread->stack_magic == NULL)
    serial_out("  EMBRYO  ");
  else if(thread->exit.count > 0)
    serial_out("  ZOMBIE  ");
  else if(!thread->blocked_on)
    serial_out("          ");
  else
    serial_out("%8s  ", thread->blocked_on->name);

  serial_out("%8s  %s\n", thr_isa_name(thread), thread->name);
}

static struct dbg_handler_s
{
  char *name;
  char *help;
  void (*handler)(char *);
} dbg_handler[32];

void trt_debug_handler(char *name, void (*handler)(char *), char *help)
{
  int i;

  for(i = 0; i < 32; i++)
  {
    struct dbg_handler_s *p = &dbg_handler[i];

    if(!p->name || !p->handler || !strcmp(p->name, name))
    {
      p->name = name;
      p->help = help;
      p->handler = handler;

      return;
    }
  }

  trt_panic_s("trt_debug_handler: can not register", name);
}

static void panic()
{
  char *thread_name;

  thread_name = current_thread && current_thread->name 
                                ? current_thread->name
                                : "???";

  serial_out("\tthread    = %s\n", thread_name);
  serial_out("\tcpu       = %d (%s)\n", trt_processor_index(), 
                isa_name(ISA));

  _exit(1);
}

void trt_panic(char *error_message)
{
  serial_out("PANIC: %s\n", error_message);

  panic();
}

void trt_panic_d(char *error_message, int argument)
{
  serial_out("PANIC: %s: %d\n", error_message, argument);

  panic();
}

void trt_panic_s(char *error_message, char *argument)
{
  serial_out("PANIC: %s: %s\n", error_message, argument);

  panic();
}

void *trt_malloc(unsigned int size)
{
  char *p = malloc(size);

  if(p == NULL)
    trt_panic("Out of memory");

  return p;
}

void trt_free(void *p)
{
  free(p);
}

extern volatile sym_table_t trt_sym_table;

static int sym_hash(int isa, char *name)
{
  int s = isa, i;

  for(i = 0; name[i]; i++)
    s ^= name[i] << (i & 7);

  return s;
}

void sym_register(char *name, void *addr)
{
  sym_t *new;
  int hash, index, ien;

  assert(addr != NULL);

  if(sym_query(ISA, name, FALSE))
    return;

  new = trt_malloc(sizeof(sym_t));
  hash = sym_hash(ISA, name);
  index = (unsigned) hash % 19u;

  ien = acquire_lock(trt_sym_table.lock, TRUE);

  new->isa = ISA;
  new->hash = hash;
  new->name = name;
  new->addr = addr;
  new->next = trt_sym_table.list[index];
  trt_sym_table.list[index] = new;

  release_lock(trt_sym_table.lock, ien);
}

void *sym_query(int isa, char *name, int wait)
{
  int hash, index, count = 0;
  sym_t *p;

  isa = ISA;

  hash = sym_hash(isa, name);
        index = (unsigned) hash % 19u;

  while(TRUE)
  {
    for(p = trt_sym_table.list[index]; p; p = p->next)
    {
      if(p->hash == hash && 
         p->isa == isa && !strcmp(p->name, name))
        return p->addr;
    }

    if(!wait)
      return NULL;

    if(++count % 5000 == 0)
      serial_out("sym_query: waiting for %s/%s\n", 
                 name, isa_name(isa));

    thr_switch();
  }
}

void sym_dump(int system)
{
  sym_t *p;
  int i;

  for(i = 0; i < 19; i++)
  {
    for(p = trt_sym_table.list[i]; p; p = p->next)
    {
      if(system ^ (p->name[0] == '$'))
        continue;

      serial_out("%x  %8s  %s\n", p->addr, isa_name(p->isa), 
                p->name);
    }
  }
}

int trt_load()
{
  thread_t *t;
  processor_t *p;
  int count = 0, ien, i;

  for(i = 0; i < trt_num_processors; i++)
  {
    p = &trt_processor_table[i];

    if(p->purpose != GENERAL)
                        continue;

    ien = acquire_lock(p->ready_list_lock, TRUE);

    if(p->running_thread)
      count++;

    if(p->schedule_me)
      count++;

    for(t = (thread_t *) p->ready_list_head; t; t = t->next)
      count++;

    release_lock(p->ready_list_lock, ien);
  }

  return count;
}

int trt_num_procs(int isa)
{
  int i, count = 0;
  processor_t *p;

  for(i = 0; i < trt_num_processors; i++)
  {
    p = &trt_processor_table[i];

    if(p->purpose == GENERAL && (isa < 0 || p->domain->isa == isa))
      count++;
  }

  return count;
}

static void schedule_me(processor_t *processor)
{
  if(processor == get_current_processor())
    return;

  if(SAVE_CONTEXT(current_thread->context.context))
    return;

  acquire_lock_no_ien(processor->schedule_me, current_thread);

  /* processor->domain->sleep_variable = 1; */

  switch_to_scheduler_stack(schedule_next_thread, empty_handler);
}

void trt_putc(int port, char c)
{
  putchar(c);
}

static void trt_putcn(int n, char c)
{
  while(n-- > 0)
    trt_putc(0, c);
}

static void serial_out_hex(unsigned int n)
{
  int i, d;

  for(i = 28; i >= 0; i -= 4)
        {
    d = (n >> i) & 15;

    if(d < 10)
      trt_putc(0, d + '0');
    else
      trt_putc(0, d + 'a' - 10);
  }
}

static void serial_out_str(char *s, int left, int field) 
{
  int len;

  if(s == NULL)
    s = "<NULL>";

  if(field)
  {
    len = strlen(s);

    if(!left)
      trt_putcn(field - len, ' ');

    while(*s)
      trt_putc(0, *s++);

    if(left)
      trt_putcn(field - len, ' ');
  }
  else
  {
    while(*s)
      trt_putc(0, *s++);
  }
}

static void serial_out_dec(int n, int is_signed, int left, int field)
{
  char buff[40], *s = &buff[39];
  unsigned int un, negative;

  if(is_signed && n < 0)
  {
    negative = 1;
    un = (unsigned int) -n;
  }
  else
  {
    negative = 0;
    un = (unsigned int) n;
  }

  *s = '\0';

  do
  {
    *(--s) = '0' + un % 10;
    un /= 10;
  } while(un > 0);

  if(negative)
    *(--s) = '-';

  serial_out_str(s, left, field);
}

static void formated_out(char *format, va_list arg_list)
{
  int field, left;

  if(format == NULL)
    format = "<NULL>";

  while(*format)
  {
    if(*format != '%')
    {
      trt_putc(0, *format++);
      continue;
    }
    
    format++;

    if(*format == '-')
    {
      format++;
      left = 1;   
    }
    else
      left = 0;

    field = 0;
    while(isdigit(*format))
      field = 10 * field + *format++ - '0';

    switch(*format)
    {
      case 's': serial_out_str(va_arg(arg_list, char *),
             left, field);
          break;
      case 'u': serial_out_dec(va_arg(arg_list, int), 0,
             left, field);
          break;
      case 'd': serial_out_dec(va_arg(arg_list, int), 1,
             left, field);
          break;
      case 'x':
      case 'p': serial_out_hex(va_arg(arg_list, int));
                                  break;
      case 'c': trt_putc(0, va_arg(arg_list, int));
          break;
      case '%': trt_putc(0, *format);
          break;
      default:  trt_putc(0, '%');
          trt_putc(0, *format);
          break;
    }

    format++;
  }
}

void serial_out(char *format, ...)
{
  va_list arg_list;
  int ien;

  ien = acquire_lock(trt_serial_lock, TRUE);

  va_start(arg_list, format);

  formated_out(format, arg_list);
    
  va_end(arg_list);

  release_lock(trt_serial_lock, ien);
}

---