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