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.
#	User	Rev	Content
1	cebix	1.1	/*
2			* sheepthreads.c - Minimal pthreads implementation (libpthreads doesn't
3			* like nonstandard stacks)
4			*
5	gbeauche	1.6	* SheepShaver (C) 1997-2005 Christian Bauer and Marc Hellwig
6	cebix	1.1	*
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	gbeauche	1.2	#define status __status
54			#define spinlock __spinlock
55	cebix	1.1	#define sem_lock __sem_lock
56			#define sem_value __sem_value
57			#define sem_waiting __sem_waiting
58
59	gbeauche	1.4	/* Wait for "clone" children only (Linux 2.4+ specific) */
60			#ifndef __WCLONE
61			#define __WCLONE 0
62			#endif
63
64	cebix	1.1
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	gbeauche	1.4	if (waitpid(thread, NULL, __WCLONE) >= 0);
145	cebix	1.1	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	gbeauche	1.7	/* 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	gbeauche	1.3	{
184	gbeauche	1.7	lock->status = 0;
185			lock->spinlock = 0;
186	gbeauche	1.3	}
187
188	gbeauche	1.7	static int fastlock_try_acquire(struct _pthread_fastlock *lock)
189	cebix	1.1	{
190	gbeauche	1.7	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	cebix	1.1	}
208
209	gbeauche	1.7	static void fastlock_release(struct _pthread_fastlock *lock)
210	cebix	1.1	{
211	gbeauche	1.7	MEMORY_BARRIER();
212			lock->spinlock = 0;
213			__asm__ __volatile__ ("" : "=m" (lock->spinlock) : "m" (lock->spinlock));
214	gbeauche	1.3	}
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	gbeauche	1.7	fastlock_init(&mutex->__m_lock);
224	gbeauche	1.3	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	gbeauche	1.7	fastlock_acquire(&mutex->__m_lock);
255	gbeauche	1.3	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	gbeauche	1.7	return fastlock_try_acquire(&mutex->__m_lock);
271	gbeauche	1.3	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	gbeauche	1.7	fastlock_release(&mutex->__m_lock);
286	gbeauche	1.3	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	cebix	1.1	}
312
313
314			/*
315			* Init semaphore
316			*/
317
318			int sem_init(sem_t *sem, int pshared, unsigned int value)
319			{
320	gbeauche	1.7	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	cebix	1.1	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	gbeauche	1.7	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	cebix	1.1	return 0;
352			}
353
354
355			/*
356			* Wait on semaphore
357			*/
358
359	gbeauche	1.7	int sem_wait(sem_t *sem)
360	cebix	1.1	{
361	gbeauche	1.7	int cnt = 0;
362			struct timespec tm;
363	cebix	1.1
364	gbeauche	1.7	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	cebix	1.1	}
380	gbeauche	1.7	sem->sem_value--;
381			fastlock_release(&sem->sem_lock);
382	cebix	1.1	return 0;
383			}
384
385
386			/*
387			* Post semaphore
388			*/
389
390			int sem_post(sem_t *sem)
391			{
392	gbeauche	1.7	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	cebix	1.1	return 0;
409			}
410	gbeauche	1.4
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