Unix/Linux/sheepthreads.c

/*
 *  sheepthreads.c - Minimal pthreads implementation (libpthreads doesn't
 *                   like nonstandard stacks)
 *
 *  SheepShaver (C) 1997-2005 Christian Bauer and Marc Hellwig
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

/*
 *  NOTES:
 *   - pthread_cancel() kills the thread immediately
 *   - Semaphores are VERY restricted: the only supported use is to have one
 *     thread sem_wait() on the semaphore while other threads sem_post() it
 *     (i.e. to use the semaphore as a signal)
 */

#include <sys/types.h>
#include <sys/wait.h>
#include <stdlib.h>
#include <errno.h>
#include <unistd.h>
#include <signal.h>
#include <pthread.h>
#include <semaphore.h>


/* Thread stack size */
#define STACK_SIZE 65536

/* From asm_linux.S */
extern int atomic_add(int *var, int add);
extern int atomic_and(int *var, int and);
extern int atomic_or(int *var, int or);
extern int test_and_set(int *var, int val);

/* Linux kernel calls */
extern int __clone(int (*fn)(void *), void *, int, void *);

/* struct sem_t */
#define status __status
#define spinlock __spinlock
#define sem_lock __sem_lock
#define sem_value __sem_value
#define sem_waiting __sem_waiting

/* Wait for "clone" children only (Linux 2.4+ specific) */
#ifndef __WCLONE
#define __WCLONE 0
#endif


/*
 *  Return pthread ID of self
 */

pthread_t pthread_self(void)
{
        return getpid();
}


/*
 *  Test whether two pthread IDs are equal
 */

int pthread_equal(pthread_t t1, pthread_t t2)
{
        return t1 == t2;
}


/*
 *  Send signal to thread
 */

int pthread_kill(pthread_t thread, int sig)
{
        if (kill(thread, sig) == -1)
                return errno;
        else
                return 0;
}


/*
 *  Create pthread
 */

struct new_thread {
        void *(*fn)(void *);
        void *arg;
};

static int start_thread(void *arg)
{
        struct new_thread *nt = (struct new_thread *)arg;
        nt->fn(nt->arg);
        return 0;
}

int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine)(void *), void *arg)
{
        struct new_thread *nt;
        void *stack;
        int pid;

        nt = (struct new_thread *)malloc(sizeof(struct new_thread));
        nt->fn = start_routine;
        nt->arg = arg;
        stack = malloc(STACK_SIZE);

        pid = __clone(start_thread, (char *)stack + STACK_SIZE - 16, CLONE_VM | CLONE_FS | CLONE_FILES, nt);
        if (pid == -1) {
                free(stack);
                free(nt);
                return errno;
        } else {
                *thread = pid;
                return 0;
        }
}


/*
 *  Join pthread
 */

int pthread_join(pthread_t thread, void **ret)
{
        do {
                if (waitpid(thread, NULL, __WCLONE) >= 0);
                        break;
        } while (errno == EINTR);
        if (ret)
                *ret = NULL;
        return 0;
}


/*
 *  Cancel thread
 */

int pthread_cancel(pthread_t thread)
{
        kill(thread, SIGINT);
        return 0;
}


/*
 *  Test for cancellation
 */

void pthread_testcancel(void)
{
}


/*
 *  Spinlocks
 */

/* For multiprocessor systems, we want to ensure all memory accesses
   are completed before we reset a lock.  On other systems, we still
   need to make sure that the compiler has flushed everything to memory.  */
#define MEMORY_BARRIER() __asm__ __volatile__ ("sync" : : : "memory")

static void fastlock_init(struct _pthread_fastlock *lock)
{
        lock->status = 0;
        lock->spinlock = 0;
}

static int fastlock_try_acquire(struct _pthread_fastlock *lock)
{
        int res = EBUSY;
        if (test_and_set(&lock->spinlock, 1) == 0) {
                if (lock->status == 0) {
                        lock->status = 1;
                        MEMORY_BARRIER();
                        res = 0;
                }
                lock->spinlock = 0;
        }
        return res;
}

static void fastlock_acquire(struct _pthread_fastlock *lock)
{
        MEMORY_BARRIER();
        while (test_and_set(&lock->spinlock, 1))
                usleep(0);
}

static void fastlock_release(struct _pthread_fastlock *lock)
{
        MEMORY_BARRIER();
        lock->spinlock = 0;
        __asm__ __volatile__ ("" : "=m" (lock->spinlock) : "m" (lock->spinlock));
}


/*
 *  Initialize mutex
 */

int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *mutex_attr)
{
        fastlock_init(&mutex->__m_lock);
        mutex->__m_kind = mutex_attr ? mutex_attr->__mutexkind : PTHREAD_MUTEX_TIMED_NP;
        mutex->__m_count = 0;
        mutex->__m_owner = NULL;
        return 0;
}


/*
 *  Destroy mutex
 */

int pthread_mutex_destroy(pthread_mutex_t *mutex)
{
        switch (mutex->__m_kind) {
        case PTHREAD_MUTEX_TIMED_NP:
                return (mutex->__m_lock.__status != 0) ? EBUSY : 0;
        default:
                return EINVAL;
        }
}


/*
 *  Lock mutex
 */

int pthread_mutex_lock(pthread_mutex_t *mutex)
{
        switch (mutex->__m_kind) {
        case PTHREAD_MUTEX_TIMED_NP:
                fastlock_acquire(&mutex->__m_lock);
                return 0;
        default:
                return EINVAL;
        }
}


/*
 *  Try to lock mutex
 */

int pthread_mutex_trylock(pthread_mutex_t *mutex)
{
        switch (mutex->__m_kind) {
        case PTHREAD_MUTEX_TIMED_NP:
                return fastlock_try_acquire(&mutex->__m_lock);
        default:
                return EINVAL;
        }
}


/*
 *  Unlock mutex
 */

int pthread_mutex_unlock(pthread_mutex_t *mutex)
{
        switch (mutex->__m_kind) {
        case PTHREAD_MUTEX_TIMED_NP:
                fastlock_release(&mutex->__m_lock);
                return 0;
        default:
                return EINVAL;
        }
}


/*
 *  Create mutex attribute
 */

int pthread_mutexattr_init(pthread_mutexattr_t *attr)
{
        attr->__mutexkind = PTHREAD_MUTEX_TIMED_NP;
        return 0;
}


/*
 *  Destroy mutex attribute
 */

int pthread_mutexattr_destroy(pthread_mutexattr_t *attr)
{
        return 0;
}


/*
 *  Init semaphore
 */

int sem_init(sem_t *sem, int pshared, unsigned int value)
{
        if (sem == NULL || value > SEM_VALUE_MAX) {
                errno = EINVAL;
                return -1;
        }
        if (pshared) {
                errno = ENOSYS;
                return -1;
        }
        fastlock_init(&sem->sem_lock);
        sem->sem_value = value;
        sem->sem_waiting = NULL;
        return 0;
}


/*
 *  Delete remaphore
 */

int sem_destroy(sem_t *sem)
{
        if (sem == NULL) {
                errno = EINVAL;
                return -1;
        }
        if (sem->sem_waiting) {
                errno = EBUSY;
                return -1;
        }
        sem->sem_value = 0;
        sem->sem_waiting = NULL;
        return 0;
}


/*
 *  Wait on semaphore
 */

int sem_wait(sem_t *sem)
{
        int cnt = 0;
        struct timespec tm;

        if (sem == NULL) {
                errno = EINVAL;
                return -1;
        }
        fastlock_acquire(&sem->sem_lock);
        if (sem->sem_value > 0) {
                sem->sem_value--;
                fastlock_release(&sem->sem_lock);
                return 0;
        }
        sem->sem_waiting = (struct _pthread_descr_struct *)((long)sem->sem_waiting + 1);
        while (sem->sem_value == 0) {
                fastlock_release(&sem->sem_lock);
                usleep(0);
                fastlock_acquire(&sem->sem_lock);
        }
        sem->sem_value--;
        fastlock_release(&sem->sem_lock);
        return 0;
}


/*
 *  Post semaphore
 */

int sem_post(sem_t *sem)
{
        if (sem == NULL) {
                errno = EINVAL;
                return -1;
        }
        fastlock_acquire(&sem->sem_lock);
        if (sem->sem_waiting)
                sem->sem_waiting = (struct _pthread_descr_struct *)((long)sem->sem_waiting - 1);
        else {
                if (sem->sem_value >= SEM_VALUE_MAX) {
                        errno = ERANGE;
                        fastlock_release(&sem->sem_lock);
                        return -1;
                }
        }
        sem->sem_value++;
        fastlock_release(&sem->sem_lock);
        return 0;
}


/*
 *  Simple producer/consumer test program
 */

#ifdef TEST
#include <stdio.h>

static sem_t p_sem, c_sem;
static int data = 0;

static void *producer_func(void *arg)
{
        int i, n = (int)arg;
        for (i = 0; i < n; i++) {
                sem_wait(&p_sem);
                data++;
                sem_post(&c_sem);
        }
        return NULL;
}

static void *consumer_func(void *arg)
{
        int i, n = (int)arg;
        for (i = 0; i < n; i++) {
                sem_wait(&c_sem);
                printf("data: %d\n", data);
                sem_post(&p_sem);
        }
        sleep(1); // for testing pthread_join()
        return NULL;
}

int main(void)
{
        pthread_t producer_thread, consumer_thread;
        static const int N = 5;

        if (sem_init(&c_sem, 0, 0) < 0)
                return 1;
        if (sem_init(&p_sem, 0, 1) < 0)
                return 2;
        if (pthread_create(&producer_thread, NULL, producer_func, (void *)N) != 0)
                return 3;
        if (pthread_create(&consumer_thread, NULL, consumer_func, (void *)N) != 0)
                return 4;
        pthread_join(producer_thread, NULL);
        pthread_join(consumer_thread, NULL);
        sem_destroy(&p_sem);
        sem_destroy(&c_sem);
        if (data != N)
                return 5;
        return 0;
}
#endif
Revision:	1.7
Committed:	2005-06-25T11:00:30Z (19 years, 5 months ago) by gbeauche
Content type:	text/plain
Branch:	MAIN
Changes since 1.6:	+89 -48 lines
Log Message:	Rewrite SheepThreads locks & semaphores. They now look much better and avoid busy waits for acquiring spin locks.
#	Content
1	/*
2	* sheepthreads.c - Minimal pthreads implementation (libpthreads doesn't
3	* like nonstandard stacks)
4	*
5	* SheepShaver (C) 1997-2005 Christian Bauer and Marc Hellwig
6	*
7	* This program is free software; you can redistribute it and/or modify
8	* it under the terms of the GNU General Public License as published by
9	* the Free Software Foundation; either version 2 of the License, or
10	* (at your option) any later version.
11	*
12	* This program is distributed in the hope that it will be useful,
13	* but WITHOUT ANY WARRANTY; without even the implied warranty of
14	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15	* GNU General Public License for more details.
16	*
17	* You should have received a copy of the GNU General Public License
18	* along with this program; if not, write to the Free Software
19	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20	*/
21
22	/*
23	* NOTES:
24	* - pthread_cancel() kills the thread immediately
25	* - Semaphores are VERY restricted: the only supported use is to have one
26	* thread sem_wait() on the semaphore while other threads sem_post() it
27	* (i.e. to use the semaphore as a signal)
28	*/
29
30	#include <sys/types.h>
31	#include <sys/wait.h>
32	#include <stdlib.h>
33	#include <errno.h>
34	#include <unistd.h>
35	#include <signal.h>
36	#include <pthread.h>
37	#include <semaphore.h>
38
39
40	/* Thread stack size */
41	#define STACK_SIZE 65536
42
43	/* From asm_linux.S */
44	extern int atomic_add(int *var, int add);
45	extern int atomic_and(int *var, int and);
46	extern int atomic_or(int *var, int or);
47	extern int test_and_set(int *var, int val);
48
49	/* Linux kernel calls */
50	extern int __clone(int (fn)(void ), void , int, void );
51
52	/* struct sem_t */
53	#define status __status
54	#define spinlock __spinlock
55	#define sem_lock __sem_lock
56	#define sem_value __sem_value
57	#define sem_waiting __sem_waiting
58
59	/* Wait for "clone" children only (Linux 2.4+ specific) */
60	#ifndef __WCLONE
61	#define __WCLONE 0
62	#endif
63
64
65	/*
66	* Return pthread ID of self
67	*/
68
69	pthread_t pthread_self(void)
70	{
71	return getpid();
72	}
73
74
75	/*
76	* Test whether two pthread IDs are equal
77	*/
78
79	int pthread_equal(pthread_t t1, pthread_t t2)
80	{
81	return t1 == t2;
82	}
83
84
85	/*
86	* Send signal to thread
87	*/
88
89	int pthread_kill(pthread_t thread, int sig)
90	{
91	if (kill(thread, sig) == -1)
92	return errno;
93	else
94	return 0;
95	}
96
97
98	/*
99	* Create pthread
100	*/
101
102	struct new_thread {
103	void (fn)(void *);
104	void *arg;
105	};
106
107	static int start_thread(void *arg)
108	{
109	struct new_thread nt = (struct new_thread )arg;
110	nt->fn(nt->arg);
111	return 0;
112	}
113
114	int pthread_create(pthread_t thread, const pthread_attr_t attr, void (start_routine)(void ), void arg)
115	{
116	struct new_thread *nt;
117	void *stack;
118	int pid;
119
120	nt = (struct new_thread *)malloc(sizeof(struct new_thread));
121	nt->fn = start_routine;
122	nt->arg = arg;
123	stack = malloc(STACK_SIZE);
124
125	pid = __clone(start_thread, (char *)stack + STACK_SIZE - 16, CLONE_VM \| CLONE_FS \| CLONE_FILES, nt);
126	if (pid == -1) {
127	free(stack);
128	free(nt);
129	return errno;
130	} else {
131	*thread = pid;
132	return 0;
133	}
134	}
135
136
137	/*
138	* Join pthread
139	*/
140
141	int pthread_join(pthread_t thread, void **ret)
142	{
143	do {
144	if (waitpid(thread, NULL, __WCLONE) >= 0);
145	break;
146	} while (errno == EINTR);
147	if (ret)
148	*ret = NULL;
149	return 0;
150	}
151
152
153	/*
154	* Cancel thread
155	*/
156
157	int pthread_cancel(pthread_t thread)
158	{
159	kill(thread, SIGINT);
160	return 0;
161	}
162
163
164	/*
165	* Test for cancellation
166	*/
167
168	void pthread_testcancel(void)
169	{
170	}
171
172
173	/*
174	* Spinlocks
175	*/
176
177	/* For multiprocessor systems, we want to ensure all memory accesses
178	are completed before we reset a lock. On other systems, we still
179	need to make sure that the compiler has flushed everything to memory. */
180	#define MEMORY_BARRIER() __asm__ __volatile__ ("sync" : : : "memory")
181
182	static void fastlock_init(struct _pthread_fastlock *lock)
183	{
184	lock->status = 0;
185	lock->spinlock = 0;
186	}
187
188	static int fastlock_try_acquire(struct _pthread_fastlock *lock)
189	{
190	int res = EBUSY;
191	if (test_and_set(&lock->spinlock, 1) == 0) {
192	if (lock->status == 0) {
193	lock->status = 1;
194	MEMORY_BARRIER();
195	res = 0;
196	}
197	lock->spinlock = 0;
198	}
199	return res;
200	}
201
202	static void fastlock_acquire(struct _pthread_fastlock *lock)
203	{
204	MEMORY_BARRIER();
205	while (test_and_set(&lock->spinlock, 1))
206	usleep(0);
207	}
208
209	static void fastlock_release(struct _pthread_fastlock *lock)
210	{
211	MEMORY_BARRIER();
212	lock->spinlock = 0;
213	__asm__ __volatile__ ("" : "=m" (lock->spinlock) : "m" (lock->spinlock));
214	}
215
216
217	/*
218	* Initialize mutex
219	*/
220
221	int pthread_mutex_init(pthread_mutex_t mutex, const pthread_mutexattr_t mutex_attr)
222	{
223	fastlock_init(&mutex->__m_lock);
224	mutex->__m_kind = mutex_attr ? mutex_attr->__mutexkind : PTHREAD_MUTEX_TIMED_NP;
225	mutex->__m_count = 0;
226	mutex->__m_owner = NULL;
227	return 0;
228	}
229
230
231	/*
232	* Destroy mutex
233	*/
234
235	int pthread_mutex_destroy(pthread_mutex_t *mutex)
236	{
237	switch (mutex->__m_kind) {
238	case PTHREAD_MUTEX_TIMED_NP:
239	return (mutex->__m_lock.__status != 0) ? EBUSY : 0;
240	default:
241	return EINVAL;
242	}
243	}
244
245
246	/*
247	* Lock mutex
248	*/
249
250	int pthread_mutex_lock(pthread_mutex_t *mutex)
251	{
252	switch (mutex->__m_kind) {
253	case PTHREAD_MUTEX_TIMED_NP:
254	fastlock_acquire(&mutex->__m_lock);
255	return 0;
256	default:
257	return EINVAL;
258	}
259	}
260
261
262	/*
263	* Try to lock mutex
264	*/
265
266	int pthread_mutex_trylock(pthread_mutex_t *mutex)
267	{
268	switch (mutex->__m_kind) {
269	case PTHREAD_MUTEX_TIMED_NP:
270	return fastlock_try_acquire(&mutex->__m_lock);
271	default:
272	return EINVAL;
273	}
274	}
275
276
277	/*
278	* Unlock mutex
279	*/
280
281	int pthread_mutex_unlock(pthread_mutex_t *mutex)
282	{
283	switch (mutex->__m_kind) {
284	case PTHREAD_MUTEX_TIMED_NP:
285	fastlock_release(&mutex->__m_lock);
286	return 0;
287	default:
288	return EINVAL;
289	}
290	}
291
292
293	/*
294	* Create mutex attribute
295	*/
296
297	int pthread_mutexattr_init(pthread_mutexattr_t *attr)
298	{
299	attr->__mutexkind = PTHREAD_MUTEX_TIMED_NP;
300	return 0;
301	}
302
303
304	/*
305	* Destroy mutex attribute
306	*/
307
308	int pthread_mutexattr_destroy(pthread_mutexattr_t *attr)
309	{
310	return 0;
311	}
312
313
314	/*
315	* Init semaphore
316	*/
317
318	int sem_init(sem_t *sem, int pshared, unsigned int value)
319	{
320	if (sem == NULL \|\| value > SEM_VALUE_MAX) {
321	errno = EINVAL;
322	return -1;
323	}
324	if (pshared) {
325	errno = ENOSYS;
326	return -1;
327	}
328	fastlock_init(&sem->sem_lock);
329	sem->sem_value = value;
330	sem->sem_waiting = NULL;
331	return 0;
332	}
333
334
335	/*
336	* Delete remaphore
337	*/
338
339	int sem_destroy(sem_t *sem)
340	{
341	if (sem == NULL) {
342	errno = EINVAL;
343	return -1;
344	}
345	if (sem->sem_waiting) {
346	errno = EBUSY;
347	return -1;
348	}
349	sem->sem_value = 0;
350	sem->sem_waiting = NULL;
351	return 0;
352	}
353
354
355	/*
356	* Wait on semaphore
357	*/
358
359	int sem_wait(sem_t *sem)
360	{
361	int cnt = 0;
362	struct timespec tm;
363
364	if (sem == NULL) {
365	errno = EINVAL;
366	return -1;
367	}
368	fastlock_acquire(&sem->sem_lock);
369	if (sem->sem_value > 0) {
370	sem->sem_value--;
371	fastlock_release(&sem->sem_lock);
372	return 0;
373	}
374	sem->sem_waiting = (struct _pthread_descr_struct *)((long)sem->sem_waiting + 1);
375	while (sem->sem_value == 0) {
376	fastlock_release(&sem->sem_lock);
377	usleep(0);
378	fastlock_acquire(&sem->sem_lock);
379	}
380	sem->sem_value--;
381	fastlock_release(&sem->sem_lock);
382	return 0;
383	}
384
385
386	/*
387	* Post semaphore
388	*/
389
390	int sem_post(sem_t *sem)
391	{
392	if (sem == NULL) {
393	errno = EINVAL;
394	return -1;
395	}
396	fastlock_acquire(&sem->sem_lock);
397	if (sem->sem_waiting)
398	sem->sem_waiting = (struct _pthread_descr_struct *)((long)sem->sem_waiting - 1);
399	else {
400	if (sem->sem_value >= SEM_VALUE_MAX) {
401	errno = ERANGE;
402	fastlock_release(&sem->sem_lock);
403	return -1;
404	}
405	}
406	sem->sem_value++;
407	fastlock_release(&sem->sem_lock);
408	return 0;
409	}
410
411
412	/*
413	* Simple producer/consumer test program
414	*/
415
416	#ifdef TEST
417	#include <stdio.h>
418
419	static sem_t p_sem, c_sem;
420	static int data = 0;
421
422	static void producer_func(void arg)
423	{
424	int i, n = (int)arg;
425	for (i = 0; i < n; i++) {
426	sem_wait(&p_sem);
427	data++;
428	sem_post(&c_sem);
429	}
430	return NULL;
431	}
432
433	static void consumer_func(void arg)
434	{
435	int i, n = (int)arg;
436	for (i = 0; i < n; i++) {
437	sem_wait(&c_sem);
438	printf("data: %d\n", data);
439	sem_post(&p_sem);
440	}
441	sleep(1); // for testing pthread_join()
442	return NULL;
443	}
444
445	int main(void)
446	{
447	pthread_t producer_thread, consumer_thread;
448	static const int N = 5;
449
450	if (sem_init(&c_sem, 0, 0) < 0)
451	return 1;
452	if (sem_init(&p_sem, 0, 1) < 0)
453	return 2;
454	if (pthread_create(&producer_thread, NULL, producer_func, (void *)N) != 0)
455	return 3;
456	if (pthread_create(&consumer_thread, NULL, consumer_func, (void *)N) != 0)
457	return 4;
458	pthread_join(producer_thread, NULL);
459	pthread_join(consumer_thread, NULL);
460	sem_destroy(&p_sem);
461	sem_destroy(&c_sem);
462	if (data != N)
463	return 5;
464	return 0;
465	}
466	#endif