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 65struct uts_runq { 66 struct kse_thr_mailbox *head; 67 struct simplelock lock; 68}; 69 70struct uts_data { 71 struct kse_mailbox mb; 72 struct uts_runq *runq; 73 struct kse_thr_mailbox *cur_thread; 74}; 75 76static struct uts_runq runq1; 77static struct uts_data data1; 78 79static void init_uts(struct uts_data *data, struct uts_runq *q); 80static void start_uts(struct uts_data *data, int newgrp); 81static void enter_uts(struct uts_data *); 82static void pchar(char c); 83static void pfmt(const char *fmt, ...); 84static void pstr(const char *s); 85static void runq_init(struct uts_runq *q); 86static void runq_insert(struct uts_runq *q, struct kse_thr_mailbox *tm); 87static struct kse_thr_mailbox *runq_remove(struct uts_runq *q); 88static struct kse_thr_mailbox *runq_remove_nolock(struct uts_runq *q); 89static void thread_start(struct uts_data *data, const void *func, int arg); 90static void uts(struct kse_mailbox *km); 91 92/* Functions implemented in assembly */ 93extern int uts_to_thread(struct kse_thr_mailbox *tdp, 94 struct kse_thr_mailbox **curthreadp); 95extern int thread_to_uts(struct kse_thr_mailbox *tm, 96 struct kse_mailbox *km); 97 98void 99deadloop(int c) 100{ 101 for (;;) { 102 ; 103 } 104} 105 106int 107main(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 */ 124static void 125enter_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 */ 139static void 140init_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 187static void 188start_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 */ 200static void 201pchar(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 */ 217static void 218pfmt(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 265static void 266pstr(const char *s) 267{ 268 269 write(STDOUT_FILENO, s, strlen(s)); 270} 271 272static void 273runq_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 */ 282static void 283runq_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 */ 294static struct kse_thr_mailbox * 295runq_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 305static struct kse_thr_mailbox * 306runq_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 */ 325static void 326uts(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 */ 376static struct kse_thr_mailbox * 377thread_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 392static void 393thread_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} 404