rr.c revision 111519 
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: cvs2svn/branches/davidxu/tools/KSE/rr/rr.c 111519 2003-02-26 01:05:10Z davidxu $
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->cur_thread = tm;
181	data->runq = q;
182	pfmt("uts() at : 0x%x\n", uts);
183	pfmt("uts stack at : 0x%x - 0x%x\n", p, p + THREAD_STACK_SIZE);
184}
185
186static void
187start_uts(struct uts_data *data, int newgrp)
188{
189	/*
190	 * Start KSE scheduling.
191	 */
192	pfmt("kse_create() -> %d\n", kse_create(&data->mb, newgrp));
193	data->mb.km_curthread = data->cur_thread;
194}
195
196/*
197 * Write a single character to stdout, in a thread-safe manner.
198 */
199static void
200pchar(char c)
201{
202
203	write(STDOUT_FILENO, &c, 1);
204}
205
206/*
207 * Write formatted output to stdout, in a thread-safe manner.
208 *
209 * Recognises the following conversions:
210 *	%c	-> char
211 *	%d	-> signed int (base 10)
212 *	%s	-> string
213 *	%u	-> unsigned int (base 10)
214 *	%x	-> unsigned int (base 16)
215 */
216static void
217pfmt(const char *fmt, ...)
218{
219	static const char digits[16] = "0123456789abcdef";
220	va_list	 ap;
221	char buf[10];
222	char *s;
223	unsigned r, u;
224	int c, d;
225
226	va_start(ap, fmt);
227	while ((c = *fmt++)) {
228		if (c == '%') {
229			c = *fmt++;
230			switch (c) {
231			case 'c':
232				pchar(va_arg(ap, int));
233				continue;
234			case 's':
235				pstr(va_arg(ap, char *));
236				continue;
237			case 'd':
238			case 'u':
239			case 'x':
240				r = ((c == 'u') || (c == 'd')) ? 10 : 16;
241				if (c == 'd') {
242					d = va_arg(ap, unsigned);
243					if (d < 0) {
244						pchar('-');
245						u = (unsigned)(d * -1);
246					} else
247						u = (unsigned)d;
248				} else
249					u = va_arg(ap, unsigned);
250				s = buf;
251				do {
252					*s++ = digits[u % r];
253				} while (u /= r);
254				while (--s >= buf)
255					pchar(*s);
256				continue;
257			}
258		}
259		pchar(c);
260	}
261	va_end(ap);
262}
263
264static void
265pstr(const char *s)
266{
267
268	write(STDOUT_FILENO, s, strlen(s));
269}
270
271static void
272runq_init(struct uts_runq *q)
273{
274	q->head = NULL;
275	simplelock_init(&q->lock);
276}
277
278/*
279 * Insert a thread into the run queue.
280 */
281static void
282runq_insert(struct uts_runq *q, struct kse_thr_mailbox *tm)
283{
284	simplelock_lock(&q->lock);
285	tm->tm_next = q->head;
286	q->head = tm;
287	simplelock_unlock(&q->lock);
288}
289
290/*
291 * Select and remove a thread from the run queue.
292 */
293static struct kse_thr_mailbox *
294runq_remove(struct uts_runq *q)
295{
296	struct kse_thr_mailbox *tm;
297
298	simplelock_lock(&q->lock);
299	tm = runq_remove_nolock(q);
300	simplelock_unlock(&q->lock);
301	return tm;
302}
303
304static struct kse_thr_mailbox *
305runq_remove_nolock(struct uts_runq *q)
306{
307	struct kse_thr_mailbox *p, *p1;
308
309	if (q->head == NULL)
310		return (NULL);
311	p1 = NULL;
312	for (p = q->head; p->tm_next != NULL; p = p->tm_next)
313		p1 = p;
314	if (p1 == NULL)
315		q->head = NULL;
316	else
317		p1->tm_next = NULL;
318	return (p);
319}
320
321/*
322 * Userland thread scheduler.
323 */
324static void
325uts(struct kse_mailbox *km)
326{
327	struct kse_thr_mailbox *tm, *p;
328	struct uts_data *data;
329
330	UPSTR("\n--uts() start--\n");
331	UPFMT("mailbox -> %x\n", km);
332
333	/*
334	 * Insert any processes back from being blocked
335	 * in the kernel into the run queue.
336	 */
337	data = km->km_udata;
338	p = km->km_completed;
339	km->km_completed = NULL;
340	UPFMT("km_completed -> 0x%x", p);
341	while ((tm = p) != NULL) {
342		p = tm->tm_next;
343		UPFMT(" 0x%x", p);
344		if (tm->tm_slices <= 0) {
345			tm->tm_slices = 10;
346			pfmt("thread %x exhausted its time slice, reassign it 10 statclock ticks\n", tm);
347		}
348		runq_insert(data->runq, tm);
349	}
350	UPCHAR('\n');
351
352	/*
353	 * Pull a thread off the run queue.
354	 */
355	simplelock_lock(&data->runq->lock);
356	p = runq_remove_nolock(data->runq);
357	simplelock_unlock(&data->runq->lock);
358
359	/*
360	 * Either schedule a thread, or idle if none ready to run.
361	 */
362	if (p != NULL) {
363		UPFMT("\n-- uts() scheduling 0x%x--\n", p);
364		UPFMT("eip -> 0x%x progress -> %d\n",
365		    p->tm_context.uc_mcontext.mc_eip, progress);
366		UPSTR("curthread set\n");
367		uts_to_thread(p, &km->km_curthread);
368		UPSTR("\n-- uts_to_thread() failed --\n");
369	}
370	kse_release(NULL);
371	pstr("** uts() exiting **\n");
372	exit(EX_SOFTWARE);
373}
374
375/*
376 * Start a thread.
377 */
378static struct kse_thr_mailbox *
379thread_create(const void *func, int arg)
380{
381	struct kse_thr_mailbox *tm;
382	char *p;
383
384	tm = (struct kse_thr_mailbox *)calloc(1, sizeof(struct kse_thr_mailbox));
385	getcontext(&tm->tm_context);
386	p = (char *)malloc(THREAD_STACK_SIZE);
387	tm->tm_context.uc_stack.ss_sp = p;
388	tm->tm_context.uc_stack.ss_size = THREAD_STACK_SIZE;
389	makecontext(&tm->tm_context, func, 1, arg);
390	// setcontext(&tm->tm_context);
391	return tm;
392}
393
394static void
395thread_start(struct uts_data *data, const void *func, int arg)
396{
397	struct kse_thr_mailbox *tm;
398	struct kse_thr_mailbox *tm2;
399
400	tm = thread_create(func, arg);
401	tm->tm_slices = 10;
402	tm2 = thread_create(enter_uts, (int)data);
403	tm->tm_context.uc_link = &tm2->tm_context;
404	runq_insert(data->runq, tm);
405	pfmt("thread_start() : 0x%x\n", tm);
406}
407