1293838Sdim/*- 2293838Sdim * Copyright (c) 2002 David Xu(davidxu@freebsd.org). 3353358Sdim * All rights reserved. 4353358Sdim * 5353358Sdim * Redistribution and use in source and binary forms, with or without 6293838Sdim * modification, are permitted provided that the following conditions 7293838Sdim * are met: 8293838Sdim * 1. Redistributions of source code must retain the above copyright 9293838Sdim * notice, this list of conditions and the following disclaimer. 10293838Sdim * 2. Redistributions in binary form must reproduce the above copyright 11293838Sdim * notice, this list of conditions and the following disclaimer in the 12293838Sdim * documentation and/or other materials provided with the distribution. 13309124Sdim * 14293838Sdim * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15321369Sdim * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16293838Sdim * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17321369Sdim * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18321369Sdim * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19293838Sdim * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20293838Sdim * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21293838Sdim * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22293838Sdim * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23293838Sdim * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24293838Sdim * SUCH DAMAGE. 25293838Sdim * 26293838Sdim * $FreeBSD$ 27293838Sdim */ 28293838Sdim 29293838Sdim/* 30293838Sdim * Test Userland Thread Scheduler (UTS) suite for KSE. 31293838Sdim * Test Userland round roubin. 32293838Sdim */ 33293838Sdim 34321369Sdim#include <sys/types.h> 35293838Sdim#include <sys/signal.h> 36309124Sdim#include <sys/signalvar.h> 37309124Sdim#include <sys/sysctl.h> 38293838Sdim#include <sys/kse.h> 39293838Sdim#include <sys/ucontext.h> 40293838Sdim 41293838Sdim#include <stdarg.h> 42293838Sdim#include <stddef.h> 43293838Sdim#include <stdlib.h> 44293838Sdim#include <string.h> 45293838Sdim#include <sysexits.h> 46293838Sdim#include <time.h> 47293838Sdim#include <unistd.h> 48293838Sdim#include "simplelock.h" 49293838Sdim 50309124Sdim#undef TRACE_UTS 51309124Sdim 52309124Sdim#ifdef TRACE_UTS 53309124Sdim#define UPFMT(fmt...) pfmt(#fmt) 54327952Sdim#define UPSTR(s) pstr(s) 55293838Sdim#define UPCHAR(c) pchar(c) 56309124Sdim#else 57293838Sdim#define UPFMT(fmt...) /* Nothing. */ 58293838Sdim#define UPSTR(s) /* Nothing. */ 59321369Sdim#define UPCHAR(c) /* Nothing. */ 60293838Sdim#endif 61321369Sdim 62293838Sdim#define MAIN_STACK_SIZE (1024 * 1024) 63293838Sdim#define THREAD_STACK_SIZE (32 * 1024) 64321369Sdim 65309124Sdimstruct uts_runq { 66293838Sdim struct kse_thr_mailbox *head; 67309124Sdim struct simplelock lock; 68293838Sdim}; 69293838Sdim 70309124Sdimstruct uts_data { 71293838Sdim struct kse_mailbox mb; 72309124Sdim struct uts_runq *runq; 73309124Sdim struct kse_thr_mailbox *cur_thread; 74309124Sdim}; 75309124Sdim 76309124Sdimstatic struct uts_runq runq1; 77293838Sdimstatic struct uts_data data1; 78293838Sdim 79293838Sdimstatic void init_uts(struct uts_data *data, struct uts_runq *q); 80293838Sdimstatic void start_uts(struct uts_data *data, int newgrp); 81293838Sdimstatic void enter_uts(struct uts_data *); 82327952Sdimstatic void pchar(char c); 83321369Sdimstatic void pfmt(const char *fmt, ...); 84293838Sdimstatic void pstr(const char *s); 85293838Sdimstatic void runq_init(struct uts_runq *q); 86293838Sdimstatic void runq_insert(struct uts_runq *q, struct kse_thr_mailbox *tm); 87293838Sdimstatic struct kse_thr_mailbox *runq_remove(struct uts_runq *q); 88321369Sdimstatic struct kse_thr_mailbox *runq_remove_nolock(struct uts_runq *q); 89293838Sdimstatic void thread_start(struct uts_data *data, const void *func, int arg); 90309124Sdimstatic void uts(struct kse_mailbox *km); 91293838Sdim 92321369Sdim/* Functions implemented in assembly */ 93293838Sdimextern int uts_to_thread(struct kse_thr_mailbox *tdp, 94309124Sdim struct kse_thr_mailbox **curthreadp); 95293838Sdimextern int thread_to_uts(struct kse_thr_mailbox *tm, 96293838Sdim struct kse_mailbox *km); 97293838Sdim 98293838Sdimvoid 99293838Sdimdeadloop(int c) 100293838Sdim{ 101293838Sdim for (;;) { 102293838Sdim ; 103293838Sdim } 104321369Sdim} 105321369Sdim 106293838Sdimint 107293838Sdimmain(void) 108293838Sdim{ 109321369Sdim runq_init(&runq1); 110293838Sdim init_uts(&data1, &runq1); 111293838Sdim thread_start(&data1, deadloop, 0); 112293838Sdim thread_start(&data1, deadloop, 0); 113321369Sdim thread_start(&data1, deadloop, 0); 114293838Sdim start_uts(&data1, 0); 115293838Sdim pause(); 116293838Sdim pstr("\n** main() exiting **\n"); 117321369Sdim return (EX_OK); 118321369Sdim} 119321369Sdim 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