Index: include/thread_private.h =================================================================== RCS file: /cvs/src/lib/libc/include/thread_private.h,v diff -u -p -r1.36 thread_private.h --- include/thread_private.h 6 Jan 2021 19:54:17 -0000 1.36 +++ include/thread_private.h 4 Jul 2024 05:02:10 -0000 @@ -287,6 +287,18 @@ struct __sem { int shared; }; +struct __cmtx_node { + volatile uint32_t wait; + SIMPLEQ_ENTRY(__cmtx_node) link; +}; +SIMPLEQ_HEAD(__cmtx_node_list, __cmtx_node); + +struct __cmtx { + _atomic_lock_t spin; + uint32_t lock; + struct __cmtx_node_list list; +}; + TAILQ_HEAD(pthread_queue, pthread); #ifdef FUTEX @@ -402,6 +414,13 @@ struct pthread { (self)->delayed_cancel = 0; \ ENTER_CANCEL_POINT_INNER(tib, 1, 1) +#define SPIN_COUNT 128 +#if defined(__i386__) || defined(__amd64__) +#define SPIN_WAIT() asm volatile("pause": : : "memory") +#else +#define SPIN_WAIT() do { } while (0) +#endif + /* * Internal functions exported from libc's thread bits for use by libpthread */ @@ -413,6 +432,19 @@ void _rthread_debug(int, const char *, . __attribute__((__format__ (printf, 2, 3))); pid_t _thread_dofork(pid_t (*_sys_fork)(void)); void _thread_finalize(void); + +/* + * simple^Wmutex for libc to use internally + */ +void __cmtx_init(struct __cmtx *); +void __cmtx_enter(struct __cmtx *); +void __cmtx_leave(struct __cmtx *); + +#define __CMTX_INITIALIZER(_cm) { \ + .spin = _SPINLOCK_UNLOCKED, \ + .lock = 0, \ + .list = SIMPLEQ_HEAD_INITIALIZER(_cm.list), \ +} /* * Threading syscalls not declared in system headers Index: thread/rthread.c =================================================================== RCS file: /cvs/src/lib/libc/thread/rthread.c,v diff -u -p -r1.9 rthread.c --- thread/rthread.c 12 Oct 2020 22:06:51 -0000 1.9 +++ thread/rthread.c 4 Jul 2024 05:02:10 -0000 @@ -21,6 +21,8 @@ #include #include +#include +#include #include #include @@ -46,8 +48,11 @@ struct pthread _initial_thread = { void _spinlock(volatile _atomic_lock_t *lock) { - while (_atomic_lock(lock)) - sched_yield(); + while (_atomic_lock(lock)) { + do { + SPIN_WAIT(); + } while (*lock != _ATOMIC_LOCK_UNLOCKED); + } membar_enter_after_atomic(); } DEF_STRONG(_spinlock); @@ -69,6 +74,82 @@ _spinunlock(volatile _atomic_lock_t *loc *lock = _ATOMIC_LOCK_UNLOCKED; } DEF_STRONG(_spinunlock); + +/* + * libc internal mutex + * + * the lock is implemented as a list of waiters protected by a spinlock. + * threads waiting for the lock add themselves to the list, and then + * spin on their own wait variable. + * + * this avoids (some) contention on the lock data structure by + * having threads spin on their stack. the thread that "owns" the + * lock is responsible for checking if there are waiting threads and + * updating their wait variable to wake them up. + * + * it also provides ordered access to the critical section by having + * threads only woken up in the order the were queued on the lock. + * + * this in turn (ha) prevents the "thundering herd" in classic locks + * where all threads are woken up so they can try and take ownership. + */ + +void +__cmtx_init(struct __cmtx *cm) +{ + cm->spin = _SPINLOCK_UNLOCKED; + cm->lock = 0; + SIMPLEQ_INIT(&cm->list); +} + +void +__cmtx_enter(struct __cmtx *cm) +{ + struct __cmtx_node self = { .wait = 1 }; + uint32_t locked; + unsigned int spin; + + _spinlock(&cm->spin); + locked = cm->lock; + if (!locked) + cm->lock = 1; + else + SIMPLEQ_INSERT_TAIL(&cm->list, &self, link); + _spinunlock(&cm->spin); + + if (!locked) + return; + + for (spin = 0; spin < SPIN_COUNT; spin++) { + SPIN_WAIT(); + if (!self.wait) + return; + } + + do { + futex(&self.wait, FUTEX_WAIT_PRIVATE, 1, NULL, NULL); + } while (self.wait); +} + +void +__cmtx_leave(struct __cmtx *cm) +{ + struct __cmtx_node *next; + + _spinlock(&cm->spin); + next = SIMPLEQ_FIRST(&cm->list); + if (next != NULL) + SIMPLEQ_REMOVE_HEAD(&cm->list, link); + else + cm->lock = 0; + _spinunlock(&cm->spin); + + if (next == NULL) + return; + + next->wait = 0; + futex(&next->wait, FUTEX_WAKE_PRIVATE, 1, NULL, NULL); +} static void _rthread_init(void) Index: thread/rthread_file.c =================================================================== RCS file: /cvs/src/lib/libc/thread/rthread_file.c,v diff -u -p -r1.3 rthread_file.c --- thread/rthread_file.c 27 Dec 2022 17:10:06 -0000 1.3 +++ thread/rthread_file.c 4 Jul 2024 05:02:10 -0000 @@ -38,6 +38,8 @@ * */ +#include +#include #include #include #include @@ -47,17 +49,26 @@ #include "rthread.h" #include "rthread_cb.h" +struct file_lock_waiter { + volatile unsigned int wait; + pthread_t owner; + SIMPLEQ_ENTRY(file_lock_waiter) link; +}; + +SIMPLEQ_HEAD(file_lock_waiters, file_lock_waiter); + /* * The FILE lock structure. The FILE *fp is locked if the owner is * not NULL. If not locked, the file lock structure can be * reassigned to a different file by setting fp. */ struct file_lock { - LIST_ENTRY(file_lock) entry; /* Entry if file list. */ - FILE *fp; /* The target file. */ - struct pthread_queue lockers; - pthread_t owner; - int count; + LIST_ENTRY(file_lock) entry; /* Entry if file list. */ + FILE *fp; + + pthread_t owner; + unsigned int count; + struct file_lock_waiters waiters; }; /* @@ -83,115 +94,144 @@ struct file_lock { * allocated statically in the hope that there won't be too many * collisions that require a malloc and an element added to the list. */ -static struct static_file_lock { - LIST_HEAD(file_list_head, file_lock) head; +static struct file_lock_bucket { + volatile unsigned int initted; + struct __cmtx lock; + LIST_HEAD(file_lock_list, file_lock) head; struct file_lock fl; } flh[NUM_HEADS]; -/* Lock for accesses to the hash table: */ +/* Lock for initialisation of the hash table: */ static _atomic_lock_t hash_lock = _SPINLOCK_UNLOCKED; +static struct file_lock_bucket * +file_bucket(FILE *fp) +{ + int idx = file_idx(fp); + struct file_lock_bucket *flb = &flh[idx]; + + if (!flb->initted) { + _spinlock(&hash_lock); + if (!flb->initted) { + __cmtx_init(&flb->lock); + LIST_INIT(&flb->head); + + SIMPLEQ_INIT(&flb->fl.waiters); + + /* XXX barrier? */ + flb->initted = 1; + } + _spinunlock(&hash_lock); + } + + return (flb); +} + /* * Find a lock structure for a FILE, return NULL if the file is * not locked: */ -static -struct file_lock * -find_lock(int idx, FILE *fp) +static struct file_lock * +find_lock(struct file_lock_bucket *flb, FILE *fp) { struct file_lock *p; /* Check if the file is locked using the static structure: */ - if (flh[idx].fl.fp == fp && flh[idx].fl.owner != NULL) + if (flb->fl.fp == fp) { /* Return a pointer to the static lock: */ - p = &flh[idx].fl; - else { - /* Point to the first dynamic lock: */ - p = LIST_FIRST(&flh[idx].head); - + p = &flb->fl; + } else { /* * Loop through the dynamic locks looking for the * target file: */ - while (p != NULL && (p->fp != fp || p->owner == NULL)) - /* Not this file, try the next: */ - p = LIST_NEXT(p, entry); + LIST_FOREACH(p, &flb->head, entry) { + if (p->fp == fp) + break; + } } - return(p); + + return (p); } /* * Lock a file, assuming that there is no lock structure currently * assigned to it. */ -static -struct file_lock * -do_lock(int idx, FILE *fp) +static struct file_lock * +do_lock(struct file_lock_bucket *flb, FILE *fp) { struct file_lock *p; /* Check if the static structure is not being used: */ - if (flh[idx].fl.owner == NULL) { + if (flb->fl.owner == NULL) { /* Return a pointer to the static lock: */ - p = &flh[idx].fl; - } - else { - /* Point to the first dynamic lock: */ - p = LIST_FIRST(&flh[idx].head); - + p = &flb->fl; + } else { /* * Loop through the dynamic locks looking for a * lock structure that is not being used: */ - while (p != NULL && p->owner != NULL) - /* This one is used, try the next: */ - p = LIST_NEXT(p, entry); + LIST_FOREACH(p, &flb->head, entry) { + if (p->fp == NULL) + break; + } } /* * If an existing lock structure has not been found, * allocate memory for a new one: */ - if (p == NULL && (p = (struct file_lock *) - malloc(sizeof(struct file_lock))) != NULL) { + if (p == NULL) { + p = malloc(sizeof(*p)); + if (p == NULL) + return (NULL); + + p->owner = NULL; + p->count = 0; + SIMPLEQ_INIT(&p->waiters); + /* Add the new element to the list: */ - LIST_INSERT_HEAD(&flh[idx].head, p, entry); + LIST_INSERT_HEAD(&flb->head, p, entry); } - /* Check if there is a lock structure to acquire: */ - if (p != NULL) { - /* Acquire the lock for the running thread: */ - p->fp = fp; - p->owner = pthread_self(); - p->count = 1; - TAILQ_INIT(&p->lockers); - } - return(p); + p->fp = fp; + + return (p); } void _thread_flockfile(FILE * fp) { - int idx = file_idx(fp); - struct file_lock *p; - pthread_t self = pthread_self(); + struct file_lock_bucket *flb = file_bucket(fp); + struct file_lock *p; + pthread_t self = pthread_self(); + pthread_t owner; + struct file_lock_waiter wchan = { .wait = 1, .owner = self }; - /* Lock the hash table: */ - _spinlock(&hash_lock); + __cmtx_enter(&flb->lock); /* Get a pointer to any existing lock for the file: */ - if ((p = find_lock(idx, fp)) == NULL) { + p = find_lock(flb, fp); + if (p == NULL) { /* * The file is not locked, so this thread can * grab the lock: */ - do_lock(idx, fp); + p = do_lock(flb, fp); + if (p == NULL) { + /* XXX unable to allocate dynamic lock! */ + __cmtx_leave(&flb->lock); + /* abort(); */ + return; + } - /* - * The file is already locked, so check if the - * running thread is the owner: - */ - } else if (p->owner == self) { + p->owner = self; /* Take ownership of the file_lock */ + } + + owner = p->owner; + /* Check if the running thread is the owner: */ + if (owner == self) { /* * The running thread is already the * owner, so increment the count of @@ -205,101 +245,84 @@ _thread_flockfile(FILE * fp) * Append this thread to the queue of * threads waiting on the lock. */ - TAILQ_INSERT_TAIL(&p->lockers,self,waiting); - while (p->owner != self) { - __thrsleep(self, 0, NULL, &hash_lock, NULL); - _spinlock(&hash_lock); - } + SIMPLEQ_INSERT_TAIL(&p->waiters, &wchan, link); } + __cmtx_leave(&flb->lock); - /* Unlock the hash table: */ - _spinunlock(&hash_lock); + if (owner == self) + return; + + /* spin? */ + + while (wchan.wait) + futex(&wchan.wait, FUTEX_WAIT_PRIVATE, 1, NULL, NULL); } int _thread_ftrylockfile(FILE * fp) { - int ret = -1; - int idx = file_idx(fp); - struct file_lock *p; - - /* Lock the hash table: */ - _spinlock(&hash_lock); + struct file_lock_bucket *flb = file_bucket(fp); + struct file_lock *p; + pthread_t self = pthread_self(); + int ret = -1; + __cmtx_enter(&flb->lock); /* Get a pointer to any existing lock for the file: */ - if ((p = find_lock(idx, fp)) == NULL) { + p = find_lock(flb, fp); + if (p == NULL) { /* * The file is not locked, so this thread can * grab the lock: */ - p = do_lock(idx, fp); - - /* - * The file is already locked, so check if the - * running thread is the owner: - */ - } else if (p->owner == pthread_self()) { - /* - * The running thread is already the - * owner, so increment the count of - * the number of times it has locked - * the file: - */ - p->count++; - } else { - /* - * The file is locked for another thread, - * so this try fails. - */ - p = NULL; + p = do_lock(flb, fp); + if (p == NULL) { + /* XXX unable to allocate dynamic lock! */ + __cmtx_leave(&flb->lock); + /* abort(); */ + return (-1); + } + + p->owner = self; } - /* Unlock the hash table: */ - _spinunlock(&hash_lock); - - /* Check if the lock was obtained: */ - if (p != NULL) - /* Return success: */ + if (p->owner == self) { + p->count++; ret = 0; + } + __cmtx_leave(&flb->lock); return (ret); } -void +void _thread_funlockfile(FILE * fp) { - int idx = file_idx(fp); - struct file_lock *p; - - /* Lock the hash table: */ - _spinlock(&hash_lock); - - /* - * Get a pointer to the lock for the file and check that - * the running thread is the one with the lock: - */ - if ((p = find_lock(idx, fp)) != NULL && p->owner == pthread_self()) { - /* - * Check if this thread has locked the FILE - * more than once: - */ - if (--p->count == 0) { - /* Get the new owner of the lock: */ - if ((p->owner = TAILQ_FIRST(&p->lockers)) != NULL) { - /* Pop the thread off the queue: */ - TAILQ_REMOVE(&p->lockers,p->owner,waiting); - - /* - * This is the first lock for the new - * owner: - */ - p->count = 1; + struct file_lock_bucket *flb = file_bucket(fp); + struct file_lock *p; + struct file_lock_waiter *wchan = NULL; - __thrwakeup(p->owner, 1); - } + __cmtx_enter(&flb->lock); + /* Get a pointer to the lock for the file: */ + p = find_lock(flb, fp); + /* assert p != NULL */ + /* assert p->owner == self */ + if (--p->count == 0) { + wchan = SIMPLEQ_FIRST(&p->waiters); + if (wchan != NULL) { + SIMPLEQ_REMOVE_HEAD(&p->waiters, link); + p->owner = wchan->owner; + p->count = 1; + } else { + /* This gives the entry back to the bucket: */ + p->fp = NULL; + p->owner = NULL; } } + __cmtx_leave(&flb->lock); + + if (wchan == NULL) + return; - /* Unlock the hash table: */ - _spinunlock(&hash_lock); + wchan->wait = 0; + futex(&wchan->wait, FUTEX_WAKE_PRIVATE, 1, NULL, NULL); } Index: thread/rthread_libc.c =================================================================== RCS file: /cvs/src/lib/libc/thread/rthread_libc.c,v diff -u -p -r1.4 rthread_libc.c --- thread/rthread_libc.c 6 Jan 2021 19:54:17 -0000 1.4 +++ thread/rthread_libc.c 4 Jul 2024 05:02:10 -0000 @@ -152,24 +152,9 @@ _thread_mutex_destroy(void **mutex) /* * the malloc lock */ -#ifndef FUTEX -#define MALLOC_LOCK_INITIALIZER(n) { \ - _SPINLOCK_UNLOCKED, \ - TAILQ_HEAD_INITIALIZER(malloc_lock[n].lockers), \ - PTHREAD_MUTEX_DEFAULT, \ - NULL, \ - 0, \ - -1 } -#else -#define MALLOC_LOCK_INITIALIZER(n) { \ - _SPINLOCK_UNLOCKED, \ - PTHREAD_MUTEX_DEFAULT, \ - NULL, \ - 0, \ - -1 } -#endif +#define MALLOC_LOCK_INITIALIZER(n) __CMTX_INITIALIZER(malloc_lock[n]) -static struct pthread_mutex malloc_lock[_MALLOC_MUTEXES] = { +static struct __cmtx malloc_lock[_MALLOC_MUTEXES] = { MALLOC_LOCK_INITIALIZER(0), MALLOC_LOCK_INITIALIZER(1), MALLOC_LOCK_INITIALIZER(2), @@ -204,51 +189,16 @@ static struct pthread_mutex malloc_lock[ MALLOC_LOCK_INITIALIZER(31) }; -static pthread_mutex_t malloc_mutex[_MALLOC_MUTEXES] = { - &malloc_lock[0], - &malloc_lock[1], - &malloc_lock[2], - &malloc_lock[3], - &malloc_lock[4], - &malloc_lock[5], - &malloc_lock[6], - &malloc_lock[7], - &malloc_lock[8], - &malloc_lock[9], - &malloc_lock[10], - &malloc_lock[11], - &malloc_lock[12], - &malloc_lock[13], - &malloc_lock[14], - &malloc_lock[15], - &malloc_lock[16], - &malloc_lock[17], - &malloc_lock[18], - &malloc_lock[19], - &malloc_lock[20], - &malloc_lock[21], - &malloc_lock[22], - &malloc_lock[23], - &malloc_lock[24], - &malloc_lock[25], - &malloc_lock[26], - &malloc_lock[27], - &malloc_lock[28], - &malloc_lock[29], - &malloc_lock[30], - &malloc_lock[31] -}; - void _thread_malloc_lock(int i) { - pthread_mutex_lock(&malloc_mutex[i]); + __cmtx_enter(&malloc_lock[i]); } void _thread_malloc_unlock(int i) { - pthread_mutex_unlock(&malloc_mutex[i]); + __cmtx_leave(&malloc_lock[i]); } static void @@ -256,14 +206,8 @@ _thread_malloc_reinit(void) { int i; - for (i = 0; i < _MALLOC_MUTEXES; i++) { - malloc_lock[i].lock = _SPINLOCK_UNLOCKED; -#ifndef FUTEX - TAILQ_INIT(&malloc_lock[i].lockers); -#endif - malloc_lock[i].owner = NULL; - malloc_lock[i].count = 0; - } + for (i = 0; i < _MALLOC_MUTEXES; i++) + __cmtx_init(&malloc_lock[i]); } /* @@ -303,18 +247,18 @@ _thread_atfork_unlock(void) /* * arc4random lock */ -static _atomic_lock_t arc4_lock = _SPINLOCK_UNLOCKED; +static struct __cmtx arc4_lock = __CMTX_INITIALIZER(arc4_lock); void _thread_arc4_lock(void) { - _spinlock(&arc4_lock); + __cmtx_enter(&arc4_lock); } void _thread_arc4_unlock(void) { - _spinunlock(&arc4_lock); + __cmtx_leave(&arc4_lock); } pid_t Index: thread/rthread_mutex.c =================================================================== RCS file: /cvs/src/lib/libc/thread/rthread_mutex.c,v diff -u -p -r1.5 rthread_mutex.c --- thread/rthread_mutex.c 13 Feb 2019 13:09:32 -0000 1.5 +++ thread/rthread_mutex.c 4 Jul 2024 05:02:10 -0000 @@ -36,14 +36,7 @@ enum { CONTENDED = 2, /* threads waiting for this mutex */ }; -#define SPIN_COUNT 128 -#if defined(__i386__) || defined(__amd64__) -#define SPIN_WAIT() asm volatile("pause": : : "memory") -#else -#define SPIN_WAIT() do { } while (0) -#endif - -static _atomic_lock_t static_init_lock = _SPINLOCK_UNLOCKED; +static struct __cmtx static_init_lock = __CMTX_INITIALIZER(static_init_lock); int pthread_mutex_init(pthread_mutex_t *mutexp, const pthread_mutexattr_t *attr) @@ -151,10 +144,10 @@ _rthread_mutex_timedlock(pthread_mutex_t * is NULL. */ if (*mutexp == NULL) { - _spinlock(&static_init_lock); + __cmtx_enter(&static_init_lock); if (*mutexp == NULL) error = pthread_mutex_init(mutexp, NULL); - _spinunlock(&static_init_lock); + __cmtx_leave(&static_init_lock); if (error != 0) return (EINVAL); } Index: thread/rthread_sync.c =================================================================== RCS file: /cvs/src/lib/libc/thread/rthread_sync.c,v diff -u -p -r1.6 rthread_sync.c --- thread/rthread_sync.c 10 Jan 2024 04:28:43 -0000 1.6 +++ thread/rthread_sync.c 4 Jul 2024 05:02:10 -0000 @@ -30,7 +30,7 @@ #include "rthread.h" #include "cancel.h" /* in libc/include */ -static _atomic_lock_t static_init_lock = _SPINLOCK_UNLOCKED; +static struct __cmtx static_init_lock = __CMTX_INITIALIZER(); /* * mutexen @@ -96,10 +96,10 @@ _rthread_mutex_lock(pthread_mutex_t *mut * is NULL. */ if (*mutexp == NULL) { - _spinlock(&static_init_lock); + __cmtx_enter(&static_init_lock); if (*mutexp == NULL) ret = pthread_mutex_init(mutexp, NULL); - _spinunlock(&static_init_lock); + __cmtx_leave(&static_init_lock); if (ret != 0) return (EINVAL); }