1111519Sdavidxu/*- 2111519Sdavidxu * Copyright (c) 2002 David Xu(davidxu@freebsd.org). 3111519Sdavidxu * All rights reserved. 4111519Sdavidxu * 5111519Sdavidxu * Redistribution and use in source and binary forms, with or without 6111519Sdavidxu * modification, are permitted provided that the following conditions 7111519Sdavidxu * are met: 8111519Sdavidxu * 1. Redistributions of source code must retain the above copyright 9111519Sdavidxu * notice, this list of conditions and the following disclaimer. 10111519Sdavidxu * 2. Redistributions in binary form must reproduce the above copyright 11111519Sdavidxu * notice, this list of conditions and the following disclaimer in the 12111519Sdavidxu * documentation and/or other materials provided with the distribution. 13111519Sdavidxu * 14111519Sdavidxu * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15111519Sdavidxu * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16111519Sdavidxu * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17111519Sdavidxu * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18111519Sdavidxu * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19111519Sdavidxu * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20111519Sdavidxu * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21111519Sdavidxu * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22111519Sdavidxu * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23111519Sdavidxu * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24111519Sdavidxu * SUCH DAMAGE. 25111519Sdavidxu * 26111519Sdavidxu * $FreeBSD$ 27111519Sdavidxu */ 28111519Sdavidxu 29111519Sdavidxu/* 30111519Sdavidxu * Test Userland Thread Scheduler (UTS) suite for KSE. 31111519Sdavidxu * Test Userland round roubin. 32111519Sdavidxu */ 33111519Sdavidxu 34111519Sdavidxu#include <sys/types.h> 35111519Sdavidxu#include <sys/signal.h> 36111519Sdavidxu#include <sys/signalvar.h> 37111519Sdavidxu#include <sys/sysctl.h> 38111519Sdavidxu#include <sys/kse.h> 39111519Sdavidxu#include <sys/ucontext.h> 40111519Sdavidxu 41111519Sdavidxu#include <stdarg.h> 42111519Sdavidxu#include <stddef.h> 43111519Sdavidxu#include <stdlib.h> 44111519Sdavidxu#include <string.h> 45111519Sdavidxu#include <sysexits.h> 46111519Sdavidxu#include <time.h> 47111519Sdavidxu#include <unistd.h> 48111519Sdavidxu#include "simplelock.h" 49111519Sdavidxu 50111519Sdavidxu#undef TRACE_UTS 51111519Sdavidxu 52111519Sdavidxu#ifdef TRACE_UTS 53111519Sdavidxu#define UPFMT(fmt...) pfmt(#fmt) 54111519Sdavidxu#define UPSTR(s) pstr(s) 55111519Sdavidxu#define UPCHAR(c) pchar(c) 56111519Sdavidxu#else 57111519Sdavidxu#define UPFMT(fmt...) /* Nothing. */ 58111519Sdavidxu#define UPSTR(s) /* Nothing. */ 59111519Sdavidxu#define UPCHAR(c) /* Nothing. */ 60111519Sdavidxu#endif 61111519Sdavidxu 62111519Sdavidxu#define MAIN_STACK_SIZE (1024 * 1024) 63111519Sdavidxu#define THREAD_STACK_SIZE (32 * 1024) 64111519Sdavidxu 65111519Sdavidxustruct uts_runq { 66111519Sdavidxu struct kse_thr_mailbox *head; 67111519Sdavidxu struct simplelock lock; 68111519Sdavidxu}; 69111519Sdavidxu 70111519Sdavidxustruct uts_data { 71111519Sdavidxu struct kse_mailbox mb; 72111519Sdavidxu struct uts_runq *runq; 73111519Sdavidxu struct kse_thr_mailbox *cur_thread; 74111519Sdavidxu}; 75111519Sdavidxu 76111519Sdavidxustatic struct uts_runq runq1; 77111519Sdavidxustatic struct uts_data data1; 78111519Sdavidxu 79111519Sdavidxustatic void init_uts(struct uts_data *data, struct uts_runq *q); 80111519Sdavidxustatic void start_uts(struct uts_data *data, int newgrp); 81111519Sdavidxustatic void enter_uts(struct uts_data *); 82111519Sdavidxustatic void pchar(char c); 83111519Sdavidxustatic void pfmt(const char *fmt, ...); 84111519Sdavidxustatic void pstr(const char *s); 85111519Sdavidxustatic void runq_init(struct uts_runq *q); 86111519Sdavidxustatic void runq_insert(struct uts_runq *q, struct kse_thr_mailbox *tm); 87111519Sdavidxustatic struct kse_thr_mailbox *runq_remove(struct uts_runq *q); 88111519Sdavidxustatic struct kse_thr_mailbox *runq_remove_nolock(struct uts_runq *q); 89111519Sdavidxustatic void thread_start(struct uts_data *data, const void *func, int arg); 90111519Sdavidxustatic void uts(struct kse_mailbox *km); 91111519Sdavidxu 92111519Sdavidxu/* Functions implemented in assembly */ 93111519Sdavidxuextern int uts_to_thread(struct kse_thr_mailbox *tdp, 94111519Sdavidxu struct kse_thr_mailbox **curthreadp); 95111519Sdavidxuextern int thread_to_uts(struct kse_thr_mailbox *tm, 96111519Sdavidxu struct kse_mailbox *km); 97111519Sdavidxu 98111519Sdavidxuvoid 99111519Sdavidxudeadloop(int c) 100111519Sdavidxu{ 101111519Sdavidxu for (;;) { 102111519Sdavidxu ; 103111519Sdavidxu } 104111519Sdavidxu} 105111519Sdavidxu 106111519Sdavidxuint 107111519Sdavidxumain(void) 108111519Sdavidxu{ 109111519Sdavidxu runq_init(&runq1); 110111519Sdavidxu init_uts(&data1, &runq1); 111111519Sdavidxu thread_start(&data1, deadloop, 0); 112111519Sdavidxu thread_start(&data1, deadloop, 0); 113111519Sdavidxu thread_start(&data1, deadloop, 0); 114111519Sdavidxu start_uts(&data1, 0); 115111519Sdavidxu pause(); 116111519Sdavidxu pstr("\n** main() exiting **\n"); 117111519Sdavidxu return (EX_OK); 118111519Sdavidxu} 119111519Sdavidxu 120111519Sdavidxu 121111519Sdavidxu/* 122111519Sdavidxu * Enter the UTS from a thread. 123111519Sdavidxu */ 124111519Sdavidxustatic void 125111519Sdavidxuenter_uts(struct uts_data *data) 126111519Sdavidxu{ 127111519Sdavidxu struct kse_thr_mailbox *td; 128111519Sdavidxu 129111519Sdavidxu /* XXX: We should atomically exchange these two. */ 130111519Sdavidxu td = data->mb.km_curthread; 131111519Sdavidxu data->mb.km_curthread = NULL; 132111519Sdavidxu 133111519Sdavidxu thread_to_uts(td, &data->mb); 134111519Sdavidxu} 135111519Sdavidxu 136111519Sdavidxu/* 137111519Sdavidxu * Initialise threading. 138111519Sdavidxu */ 139111519Sdavidxustatic void 140111519Sdavidxuinit_uts(struct uts_data *data, struct uts_runq *q) 141111519Sdavidxu{ 142111519Sdavidxu struct kse_thr_mailbox *tm; 143111519Sdavidxu int mib[2]; 144111519Sdavidxu char *p; 145111519Sdavidxu#if 0 146111519Sdavidxu size_t len; 147111519Sdavidxu#endif 148111519Sdavidxu 149111519Sdavidxu /* 150111519Sdavidxu * Create initial thread. 151111519Sdavidxu */ 152111519Sdavidxu tm = (struct kse_thr_mailbox *)calloc(1, sizeof(struct kse_thr_mailbox)); 153111519Sdavidxu 154111519Sdavidxu /* Throw us into its context. */ 155111519Sdavidxu getcontext(&tm->tm_context); 156111519Sdavidxu 157111519Sdavidxu /* Find our stack. */ 158111519Sdavidxu mib[0] = CTL_KERN; 159111519Sdavidxu mib[1] = KERN_USRSTACK; 160111519Sdavidxu#if 0 161111519Sdavidxu len = sizeof(p); 162111519Sdavidxu if (sysctl(mib, 2, &p, &len, NULL, 0) == -1) 163111519Sdavidxu pstr("sysctl(CTL_KER.KERN_USRSTACK) failed.\n"); 164111519Sdavidxu#endif 165111519Sdavidxu p = (char *)malloc(MAIN_STACK_SIZE) + MAIN_STACK_SIZE; 166111519Sdavidxu pfmt("main() : 0x%x\n", tm); 167111519Sdavidxu pfmt("eip -> 0x%x\n", tm->tm_context.uc_mcontext.mc_eip); 168111519Sdavidxu tm->tm_context.uc_stack.ss_sp = p - MAIN_STACK_SIZE; 169111519Sdavidxu tm->tm_context.uc_stack.ss_size = MAIN_STACK_SIZE; 170111519Sdavidxu 171111519Sdavidxu /* 172111519Sdavidxu * Create KSE mailbox. 173111519Sdavidxu */ 174111519Sdavidxu p = (char *)malloc(THREAD_STACK_SIZE); 175111519Sdavidxu bzero(&data->mb, sizeof(struct kse_mailbox)); 176111519Sdavidxu data->mb.km_stack.ss_sp = p; 177111519Sdavidxu data->mb.km_stack.ss_size = THREAD_STACK_SIZE; 178111519Sdavidxu data->mb.km_func = (void *)uts; 179111519Sdavidxu data->mb.km_udata = data; 180112456Sdavidxu data->mb.km_quantum = 10000; 181111519Sdavidxu data->cur_thread = tm; 182111519Sdavidxu data->runq = q; 183111519Sdavidxu pfmt("uts() at : 0x%x\n", uts); 184111519Sdavidxu pfmt("uts stack at : 0x%x - 0x%x\n", p, p + THREAD_STACK_SIZE); 185111519Sdavidxu} 186111519Sdavidxu 187111519Sdavidxustatic void 188111519Sdavidxustart_uts(struct uts_data *data, int newgrp) 189111519Sdavidxu{ 190111519Sdavidxu /* 191111519Sdavidxu * Start KSE scheduling. 192111519Sdavidxu */ 193111519Sdavidxu pfmt("kse_create() -> %d\n", kse_create(&data->mb, newgrp)); 194111519Sdavidxu data->mb.km_curthread = data->cur_thread; 195111519Sdavidxu} 196111519Sdavidxu 197111519Sdavidxu/* 198111519Sdavidxu * Write a single character to stdout, in a thread-safe manner. 199111519Sdavidxu */ 200111519Sdavidxustatic void 201111519Sdavidxupchar(char c) 202111519Sdavidxu{ 203111519Sdavidxu 204111519Sdavidxu write(STDOUT_FILENO, &c, 1); 205111519Sdavidxu} 206111519Sdavidxu 207111519Sdavidxu/* 208111519Sdavidxu * Write formatted output to stdout, in a thread-safe manner. 209111519Sdavidxu * 210111519Sdavidxu * Recognises the following conversions: 211111519Sdavidxu * %c -> char 212111519Sdavidxu * %d -> signed int (base 10) 213111519Sdavidxu * %s -> string 214111519Sdavidxu * %u -> unsigned int (base 10) 215111519Sdavidxu * %x -> unsigned int (base 16) 216111519Sdavidxu */ 217111519Sdavidxustatic void 218111519Sdavidxupfmt(const char *fmt, ...) 219111519Sdavidxu{ 220111519Sdavidxu static const char digits[16] = "0123456789abcdef"; 221111519Sdavidxu va_list ap; 222111519Sdavidxu char buf[10]; 223111519Sdavidxu char *s; 224111519Sdavidxu unsigned r, u; 225111519Sdavidxu int c, d; 226111519Sdavidxu 227111519Sdavidxu va_start(ap, fmt); 228111519Sdavidxu while ((c = *fmt++)) { 229111519Sdavidxu if (c == '%') { 230111519Sdavidxu c = *fmt++; 231111519Sdavidxu switch (c) { 232111519Sdavidxu case 'c': 233111519Sdavidxu pchar(va_arg(ap, int)); 234111519Sdavidxu continue; 235111519Sdavidxu case 's': 236111519Sdavidxu pstr(va_arg(ap, char *)); 237111519Sdavidxu continue; 238111519Sdavidxu case 'd': 239111519Sdavidxu case 'u': 240111519Sdavidxu case 'x': 241111519Sdavidxu r = ((c == 'u') || (c == 'd')) ? 10 : 16; 242111519Sdavidxu if (c == 'd') { 243111519Sdavidxu d = va_arg(ap, unsigned); 244111519Sdavidxu if (d < 0) { 245111519Sdavidxu pchar('-'); 246111519Sdavidxu u = (unsigned)(d * -1); 247111519Sdavidxu } else 248111519Sdavidxu u = (unsigned)d; 249111519Sdavidxu } else 250111519Sdavidxu u = va_arg(ap, unsigned); 251111519Sdavidxu s = buf; 252111519Sdavidxu do { 253111519Sdavidxu *s++ = digits[u % r]; 254111519Sdavidxu } while (u /= r); 255111519Sdavidxu while (--s >= buf) 256111519Sdavidxu pchar(*s); 257111519Sdavidxu continue; 258111519Sdavidxu } 259111519Sdavidxu } 260111519Sdavidxu pchar(c); 261111519Sdavidxu } 262111519Sdavidxu va_end(ap); 263111519Sdavidxu} 264111519Sdavidxu 265111519Sdavidxustatic void 266111519Sdavidxupstr(const char *s) 267111519Sdavidxu{ 268111519Sdavidxu 269111519Sdavidxu write(STDOUT_FILENO, s, strlen(s)); 270111519Sdavidxu} 271111519Sdavidxu 272111519Sdavidxustatic void 273111519Sdavidxurunq_init(struct uts_runq *q) 274111519Sdavidxu{ 275111519Sdavidxu q->head = NULL; 276111519Sdavidxu simplelock_init(&q->lock); 277111519Sdavidxu} 278111519Sdavidxu 279111519Sdavidxu/* 280111519Sdavidxu * Insert a thread into the run queue. 281111519Sdavidxu */ 282111519Sdavidxustatic void 283111519Sdavidxurunq_insert(struct uts_runq *q, struct kse_thr_mailbox *tm) 284111519Sdavidxu{ 285111519Sdavidxu simplelock_lock(&q->lock); 286111519Sdavidxu tm->tm_next = q->head; 287111519Sdavidxu q->head = tm; 288111519Sdavidxu simplelock_unlock(&q->lock); 289111519Sdavidxu} 290111519Sdavidxu 291111519Sdavidxu/* 292111519Sdavidxu * Select and remove a thread from the run queue. 293111519Sdavidxu */ 294111519Sdavidxustatic struct kse_thr_mailbox * 295111519Sdavidxurunq_remove(struct uts_runq *q) 296111519Sdavidxu{ 297111519Sdavidxu struct kse_thr_mailbox *tm; 298111519Sdavidxu 299111519Sdavidxu simplelock_lock(&q->lock); 300111519Sdavidxu tm = runq_remove_nolock(q); 301111519Sdavidxu simplelock_unlock(&q->lock); 302111519Sdavidxu return tm; 303111519Sdavidxu} 304111519Sdavidxu 305111519Sdavidxustatic struct kse_thr_mailbox * 306111519Sdavidxurunq_remove_nolock(struct uts_runq *q) 307111519Sdavidxu{ 308111519Sdavidxu struct kse_thr_mailbox *p, *p1; 309111519Sdavidxu 310111519Sdavidxu if (q->head == NULL) 311111519Sdavidxu return (NULL); 312111519Sdavidxu p1 = NULL; 313111519Sdavidxu for (p = q->head; p->tm_next != NULL; p = p->tm_next) 314111519Sdavidxu p1 = p; 315111519Sdavidxu if (p1 == NULL) 316111519Sdavidxu q->head = NULL; 317111519Sdavidxu else 318111519Sdavidxu p1->tm_next = NULL; 319111519Sdavidxu return (p); 320111519Sdavidxu} 321111519Sdavidxu 322111519Sdavidxu/* 323111519Sdavidxu * Userland thread scheduler. 324111519Sdavidxu */ 325111519Sdavidxustatic void 326111519Sdavidxuuts(struct kse_mailbox *km) 327111519Sdavidxu{ 328111519Sdavidxu struct kse_thr_mailbox *tm, *p; 329111519Sdavidxu struct uts_data *data; 330111519Sdavidxu 331111519Sdavidxu UPSTR("\n--uts() start--\n"); 332111519Sdavidxu UPFMT("mailbox -> %x\n", km); 333111519Sdavidxu 334111519Sdavidxu /* 335111519Sdavidxu * Insert any processes back from being blocked 336111519Sdavidxu * in the kernel into the run queue. 337111519Sdavidxu */ 338111519Sdavidxu data = km->km_udata; 339111519Sdavidxu p = km->km_completed; 340111519Sdavidxu km->km_completed = NULL; 341111519Sdavidxu UPFMT("km_completed -> 0x%x", p); 342111519Sdavidxu while ((tm = p) != NULL) { 343111519Sdavidxu p = tm->tm_next; 344111519Sdavidxu UPFMT(" 0x%x", p); 345111519Sdavidxu runq_insert(data->runq, tm); 346111519Sdavidxu } 347111519Sdavidxu UPCHAR('\n'); 348111519Sdavidxu 349111519Sdavidxu /* 350111519Sdavidxu * Pull a thread off the run queue. 351111519Sdavidxu */ 352111519Sdavidxu simplelock_lock(&data->runq->lock); 353111519Sdavidxu p = runq_remove_nolock(data->runq); 354111519Sdavidxu simplelock_unlock(&data->runq->lock); 355111519Sdavidxu 356111519Sdavidxu /* 357111519Sdavidxu * Either schedule a thread, or idle if none ready to run. 358111519Sdavidxu */ 359111519Sdavidxu if (p != NULL) { 360111519Sdavidxu UPFMT("\n-- uts() scheduling 0x%x--\n", p); 361111519Sdavidxu UPFMT("eip -> 0x%x progress -> %d\n", 362111519Sdavidxu p->tm_context.uc_mcontext.mc_eip, progress); 363111519Sdavidxu UPSTR("curthread set\n"); 364112456Sdavidxu pfmt("%x\n", p); 365111519Sdavidxu uts_to_thread(p, &km->km_curthread); 366111519Sdavidxu UPSTR("\n-- uts_to_thread() failed --\n"); 367111519Sdavidxu } 368111519Sdavidxu kse_release(NULL); 369111519Sdavidxu pstr("** uts() exiting **\n"); 370111519Sdavidxu exit(EX_SOFTWARE); 371111519Sdavidxu} 372111519Sdavidxu 373111519Sdavidxu/* 374111519Sdavidxu * Start a thread. 375111519Sdavidxu */ 376111519Sdavidxustatic struct kse_thr_mailbox * 377111519Sdavidxuthread_create(const void *func, int arg) 378111519Sdavidxu{ 379111519Sdavidxu struct kse_thr_mailbox *tm; 380111519Sdavidxu char *p; 381111519Sdavidxu 382111519Sdavidxu tm = (struct kse_thr_mailbox *)calloc(1, sizeof(struct kse_thr_mailbox)); 383111519Sdavidxu getcontext(&tm->tm_context); 384111519Sdavidxu p = (char *)malloc(THREAD_STACK_SIZE); 385111519Sdavidxu tm->tm_context.uc_stack.ss_sp = p; 386111519Sdavidxu tm->tm_context.uc_stack.ss_size = THREAD_STACK_SIZE; 387111519Sdavidxu makecontext(&tm->tm_context, func, 1, arg); 388111519Sdavidxu // setcontext(&tm->tm_context); 389111519Sdavidxu return tm; 390111519Sdavidxu} 391111519Sdavidxu 392111519Sdavidxustatic void 393111519Sdavidxuthread_start(struct uts_data *data, const void *func, int arg) 394111519Sdavidxu{ 395111519Sdavidxu struct kse_thr_mailbox *tm; 396111519Sdavidxu struct kse_thr_mailbox *tm2; 397111519Sdavidxu 398111519Sdavidxu tm = thread_create(func, arg); 399111519Sdavidxu tm2 = thread_create(enter_uts, (int)data); 400111519Sdavidxu tm->tm_context.uc_link = &tm2->tm_context; 401111519Sdavidxu runq_insert(data->runq, tm); 402111519Sdavidxu pfmt("thread_start() : 0x%x\n", tm); 403111519Sdavidxu} 404