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
deadloop(int c)99 deadloop(int c)
100 {
101 for (;;) {
102 ;
103 }
104 }
105
106 int
main(void)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
enter_uts(struct uts_data * data)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
init_uts(struct uts_data * data,struct uts_runq * q)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
start_uts(struct uts_data * data,int newgrp)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
pchar(char c)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
pfmt(const char * fmt,...)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
pstr(const char * s)266 pstr(const char *s)
267 {
268
269 write(STDOUT_FILENO, s, strlen(s));
270 }
271
272 static void
runq_init(struct uts_runq * q)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
runq_insert(struct uts_runq * q,struct kse_thr_mailbox * tm)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 *
runq_remove(struct uts_runq * q)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 *
runq_remove_nolock(struct uts_runq * q)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
uts(struct kse_mailbox * km)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 *
thread_create(const void * func,int arg)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
thread_start(struct uts_data * data,const void * func,int arg)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 }
404