tools/KSE/rr/rr.c

   1 /*-
   2  * Copyright (c) 2002 David Xu(davidxu@freebsd.org).
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  *
  26  * $FreeBSD$
  27  */
  28
  29 /*
  30  * Test Userland Thread Scheduler (UTS) suite for KSE.
  31  * Test Userland round roubin.
  32  */
  33
  34 #include <sys/types.h>
  35 #include <sys/signal.h>
  36 #include <sys/signalvar.h>
  37 #include <sys/sysctl.h>
  38 #include <sys/kse.h>
  39 #include <sys/ucontext.h>
  40
  41 #include <stdarg.h>
  42 #include <stddef.h>
  43 #include <stdlib.h>
  44 #include <string.h>
  45 #include <sysexits.h>
  46 #include <time.h>
  47 #include <unistd.h>
  48 #include "simplelock.h"
  49
  50 #undef TRACE_UTS
  51
  52 #ifdef TRACE_UTS
  53 #define UPFMT(fmt...)   pfmt(#fmt)
  54 #define UPSTR(s)        pstr(s)
  55 #define UPCHAR(c)       pchar(c)
  56 #else
  57 #define UPFMT(fmt...)   /* Nothing. */
  58 #define UPSTR(s)        /* Nothing. */
  59 #define UPCHAR(c)       /* Nothing. */
  60 #endif
  61
  62 #define MAIN_STACK_SIZE                 (1024 * 1024)
  63 #define THREAD_STACK_SIZE               (32 * 1024)
  64
  65 struct uts_runq {
  66         struct kse_thr_mailbox  *head;
  67         struct simplelock       lock;
  68 };
  69
  70 struct uts_data {
  71         struct kse_mailbox      mb;
  72         struct uts_runq         *runq;
  73         struct kse_thr_mailbox  *cur_thread;
  74 };
  75
  76 static struct uts_runq runq1;
  77 static struct uts_data data1;
  78
  79 static void     init_uts(struct uts_data *data, struct uts_runq *q);
  80 static void     start_uts(struct uts_data *data, int newgrp);
  81 static void     enter_uts(struct uts_data *);
  82 static void     pchar(char c);
  83 static void     pfmt(const char *fmt, ...);
  84 static void     pstr(const char *s);
  85 static void     runq_init(struct uts_runq *q);
  86 static void     runq_insert(struct uts_runq *q, struct kse_thr_mailbox *tm);
  87 static struct   kse_thr_mailbox *runq_remove(struct uts_runq *q);
  88 static struct   kse_thr_mailbox *runq_remove_nolock(struct uts_runq *q);
  89 static void     thread_start(struct uts_data *data, const void *func, int arg);
  90 static void     uts(struct kse_mailbox *km);
  91
  92 /* Functions implemented in assembly */
  93 extern int      uts_to_thread(struct kse_thr_mailbox *tdp,
  94                         struct kse_thr_mailbox **curthreadp);
  95 extern int      thread_to_uts(struct kse_thr_mailbox *tm,
  96                         struct kse_mailbox *km);
  97
  98 void
  99 deadloop(int c)
 100 {
 101         for (;;) {
 102                 ;
 103         }
 104 }
 105
 106 int
 107 main(void)
 108 {
 109         runq_init(&runq1);
 110         init_uts(&data1, &runq1);
 111         thread_start(&data1, deadloop, 0);
 112         thread_start(&data1, deadloop, 0);
 113         thread_start(&data1, deadloop, 0);
 114         start_uts(&data1, 0);
 115         pause();
 116         pstr("\n** main() exiting **\n");
 117         return (EX_OK);
 118 }
 119
 120
 121 /*
 122  * Enter the UTS from a thread.
 123  */
 124 static void
 125 enter_uts(struct uts_data *data)
 126 {
 127         struct kse_thr_mailbox  *td;
 128
 129         /* XXX: We should atomically exchange these two. */
 130         td = data->mb.km_curthread;
 131         data->mb.km_curthread = NULL;
 132
 133         thread_to_uts(td, &data->mb);
 134 }
 135
 136 /*
 137  * Initialise threading.
 138  */
 139 static void
 140 init_uts(struct uts_data *data, struct uts_runq *q)
 141 {
 142         struct kse_thr_mailbox *tm;
 143         int mib[2];
 144         char    *p;
 145 #if 0
 146         size_t len;
 147 #endif
 148
 149         /*
 150          * Create initial thread.
 151          */
 152         tm = (struct kse_thr_mailbox *)calloc(1, sizeof(struct kse_thr_mailbox));
 153
 154         /* Throw us into its context. */
 155         getcontext(&tm->tm_context);
 156
 157         /* Find our stack. */
 158         mib[0] = CTL_KERN;
 159         mib[1] = KERN_USRSTACK;
 160 #if 0
 161         len = sizeof(p);
 162         if (sysctl(mib, 2, &p, &len, NULL, 0) == -1)
 163                 pstr("sysctl(CTL_KER.KERN_USRSTACK) failed.\n");
 164 #endif
 165         p = (char *)malloc(MAIN_STACK_SIZE) + MAIN_STACK_SIZE;
 166         pfmt("main() : 0x%x\n", tm);
 167         pfmt("eip -> 0x%x\n", tm->tm_context.uc_mcontext.mc_eip);
 168         tm->tm_context.uc_stack.ss_sp = p - MAIN_STACK_SIZE;
 169         tm->tm_context.uc_stack.ss_size = MAIN_STACK_SIZE;
 170
 171         /*
 172          * Create KSE mailbox.
 173          */
 174         p = (char *)malloc(THREAD_STACK_SIZE);
 175         bzero(&data->mb, sizeof(struct kse_mailbox));
 176         data->mb.km_stack.ss_sp = p;
 177         data->mb.km_stack.ss_size = THREAD_STACK_SIZE;
 178         data->mb.km_func = (void *)uts;
 179         data->mb.km_udata = data;
 180         data->mb.km_quantum = 10000;
 181         data->cur_thread = tm;
 182         data->runq = q;
 183         pfmt("uts() at : 0x%x\n", uts);
 184         pfmt("uts stack at : 0x%x - 0x%x\n", p, p + THREAD_STACK_SIZE);
 185 }
 186
 187 static void
 188 start_uts(struct uts_data *data, int newgrp)
 189 {
 190         /*
 191          * Start KSE scheduling.
 192          */
 193         pfmt("kse_create() -> %d\n", kse_create(&data->mb, newgrp));
 194         data->mb.km_curthread = data->cur_thread;
 195 }
 196
 197 /*
 198  * Write a single character to stdout, in a thread-safe manner.
 199  */
 200 static void
 201 pchar(char c)
 202 {
 203
 204         write(STDOUT_FILENO, &c, 1);
 205 }
 206
 207 /*
 208  * Write formatted output to stdout, in a thread-safe manner.
 209  *
 210  * Recognises the following conversions:
 211  *      %c      -> char
 212  *      %d      -> signed int (base 10)
 213  *      %s      -> string
 214  *      %u      -> unsigned int (base 10)
 215  *      %x      -> unsigned int (base 16)
 216  */
 217 static void
 218 pfmt(const char *fmt, ...)
 219 {
 220         static const char digits[16] = "0123456789abcdef";
 221         va_list  ap;
 222         char buf[10];
 223         char *s;
 224         unsigned r, u;
 225         int c, d;
 226
 227         va_start(ap, fmt);
 228         while ((c = *fmt++)) {
 229                 if (c == '%') {
 230                         c = *fmt++;
 231                         switch (c) {
 232                         case 'c':
 233                                 pchar(va_arg(ap, int));
 234                                 continue;
 235                         case 's':
 236                                 pstr(va_arg(ap, char *));
 237                                 continue;
 238                         case 'd':
 239                         case 'u':
 240                         case 'x':
 241                                 r = ((c == 'u') || (c == 'd')) ? 10 : 16;
 242                                 if (c == 'd') {
 243                                         d = va_arg(ap, unsigned);
 244                                         if (d < 0) {
 245                                                 pchar('-');
 246                                                 u = (unsigned)(d * -1);
 247                                         } else
 248                                                 u = (unsigned)d;
 249                                 } else
 250                                         u = va_arg(ap, unsigned);
 251                                 s = buf;
 252                                 do {
 253                                         *s++ = digits[u % r];
 254                                 } while (u /= r);
 255                                 while (--s >= buf)
 256                                         pchar(*s);
 257                                 continue;
 258                         }
 259                 }
 260                 pchar(c);
 261         }
 262         va_end(ap);
 263 }
 264
 265 static void
 266 pstr(const char *s)
 267 {
 268
 269         write(STDOUT_FILENO, s, strlen(s));
 270 }
 271
 272 static void
 273 runq_init(struct uts_runq *q)
 274 {
 275         q->head = NULL;
 276         simplelock_init(&q->lock);
 277 }
 278
 279 /*
 280  * Insert a thread into the run queue.
 281  */
 282 static void
 283 runq_insert(struct uts_runq *q, struct kse_thr_mailbox *tm)
 284 {
 285         simplelock_lock(&q->lock);
 286         tm->tm_next = q->head;
 287         q->head = tm;
 288         simplelock_unlock(&q->lock);
 289 }
 290
 291 /*
 292  * Select and remove a thread from the run queue.
 293  */
 294 static struct kse_thr_mailbox *
 295 runq_remove(struct uts_runq *q)
 296 {
 297         struct kse_thr_mailbox *tm;
 298
 299         simplelock_lock(&q->lock);
 300         tm = runq_remove_nolock(q);
 301         simplelock_unlock(&q->lock);
 302         return tm;
 303 }
 304
 305 static struct kse_thr_mailbox *
 306 runq_remove_nolock(struct uts_runq *q)
 307 {
 308         struct kse_thr_mailbox *p, *p1;
 309
 310         if (q->head == NULL)
 311                 return (NULL);
 312         p1 = NULL;
 313         for (p = q->head; p->tm_next != NULL; p = p->tm_next)
 314                 p1 = p;
 315         if (p1 == NULL)
 316                 q->head = NULL;
 317         else
 318                 p1->tm_next = NULL;
 319         return (p);
 320 }
 321
 322 /*
 323  * Userland thread scheduler.
 324  */
 325 static void
 326 uts(struct kse_mailbox *km)
 327 {
 328         struct kse_thr_mailbox *tm, *p;
 329         struct uts_data *data;
 330
 331         UPSTR("\n--uts() start--\n");
 332         UPFMT("mailbox -> %x\n", km);
 333
 334         /*
 335          * Insert any processes back from being blocked
 336          * in the kernel into the run queue.
 337          */
 338         data = km->km_udata;
 339         p = km->km_completed;
 340         km->km_completed = NULL;
 341         UPFMT("km_completed -> 0x%x", p);
 342         while ((tm = p) != NULL) {
 343                 p = tm->tm_next;
 344                 UPFMT(" 0x%x", p);
 345                 runq_insert(data->runq, tm);
 346         }
 347         UPCHAR('\n');
 348
 349         /*
 350          * Pull a thread off the run queue.
 351          */
 352         simplelock_lock(&data->runq->lock);
 353         p = runq_remove_nolock(data->runq);
 354         simplelock_unlock(&data->runq->lock);
 355
 356         /*
 357          * Either schedule a thread, or idle if none ready to run.
 358          */
 359         if (p != NULL) {
 360                 UPFMT("\n-- uts() scheduling 0x%x--\n", p);
 361                 UPFMT("eip -> 0x%x progress -> %d\n",
 362                     p->tm_context.uc_mcontext.mc_eip, progress);
 363                 UPSTR("curthread set\n");
 364                 pfmt("%x\n", p);
 365                 uts_to_thread(p, &km->km_curthread);
 366                 UPSTR("\n-- uts_to_thread() failed --\n");
 367         }
 368         kse_release(NULL);
 369         pstr("** uts() exiting **\n");
 370         exit(EX_SOFTWARE);
 371 }
 372
 373 /*
 374  * Start a thread.
 375  */
 376 static struct kse_thr_mailbox *
 377 thread_create(const void *func, int arg)
 378 {
 379         struct kse_thr_mailbox *tm;
 380         char *p;
 381
 382         tm = (struct kse_thr_mailbox *)calloc(1, sizeof(struct kse_thr_mailbox));
 383         getcontext(&tm->tm_context);
 384         p = (char *)malloc(THREAD_STACK_SIZE);
 385         tm->tm_context.uc_stack.ss_sp = p;
 386         tm->tm_context.uc_stack.ss_size = THREAD_STACK_SIZE;
 387         makecontext(&tm->tm_context, func, 1, arg);
 388         // setcontext(&tm->tm_context);
 389         return tm;
 390 }
 391
 392 static void
 393 thread_start(struct uts_data *data, const void *func, int arg)
 394 {
 395         struct kse_thr_mailbox *tm;
 396         struct kse_thr_mailbox *tm2;
 397
 398         tm = thread_create(func, arg);
 399         tm2 = thread_create(enter_uts, (int)data);
 400         tm->tm_context.uc_link = &tm2->tm_context;
 401         runq_insert(data->runq, tm);
 402         pfmt("thread_start() : 0x%x\n", tm);
 403 }