From e4865d133cc8106cd3d9ec1a381ce579fa522c76 Mon Sep 17 00:00:00 2001 From: Matthias Kruk Date: Sat, 24 Apr 2021 09:21:44 +0900 Subject: [PATCH] include/sem: Re-implement semaphores without busy-waiting workaround The current sem module has a design issue that requires the use of sleep or inotifywait to avoid busy-waiting when the semaphore counter is zero. This commit adds a new sem implementation that avoids the problem altogether through the use of a separate mutex (called waitlock), which sem_wait() will attempt to acquire, causing it to be blocked until the waitlock is released by a call to sem_post(). Further, the new implementation keeps all filesystem objects belonging to a semaphore in a directory, giving it a cleaner appearance. This commit also adds several test cases for the new sem module. --- include/sem.sh | 283 ++++++++++++----------- test/sem.sh | 616 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 764 insertions(+), 135 deletions(-) create mode 100755 test/sem.sh diff --git a/include/sem.sh b/include/sem.sh index 224e771..2a1e397 100644 --- a/include/sem.sh +++ b/include/sem.sh @@ -6,63 +6,63 @@ # __init() { - if ! include "mutex"; then + if ! include "is" "mutex" "wmutex" "log"; then return 1 fi declare -xgr __sem_path="$TOOLBOX_HOME/sem" + if ! mkdir -p "$__sem_path"; then + return 1 + fi + return 0 } - -_sem_mutexpath() { - local sem - - sem="$1" +_sem_get_path() { + local sem="$1" if [[ "$sem" == *"/"* ]]; then - echo "$sem.mutex" + echo "$sem" else - echo "$__sem_path/$sem.mutex" + echo "$__sem_path/$sem" fi } -_sem_ownerpath() { - local sem +_sem_get_waitlock() { + local sem="$1" - sem="$1" + echo "$(_sem_get_path "$sem")/waitlock" +} - if [[ "$sem" == *"/"* ]]; then - echo "$sem.owner" - else - echo "$__sem_path/$sem.owner" - fi +_sem_get_countlock() { + local sem="$1" + + echo "$(_sem_get_path "$sem")/countlock" } -_sem_sempath() { - local sem +_sem_get_owner() { + local sem="$1" - sem="$1" + echo "$(_sem_get_path "$sem")/owner" +} - if [[ "$sem" == *"/"* ]]; then - echo "$sem" - else - echo "$__sem_path/$sem" - fi +_sem_get_counter() { + local sem="$1" + + echo "$(_sem_get_path "$sem")/counter" } -_sem_inc() { - local sem - local value +_sem_counter_inc() { + local sem="$1" - sem="$1" + local value - if ! value=$(cat "$sem"); then + if ! value=$(< "$sem"); then return 1 fi - ((value++)) + ((++value)) if ! echo "$value" > "$sem"; then return 1 @@ -71,22 +71,19 @@ _sem_inc() { return 0 } -_sem_dec() { - local sem - local value +_sem_counter_dec() { + local sem="$1" - sem="$1" + local value - if ! value=$(cat "$sem"); then + if ! value=$(< "$sem"); then return 1 fi - if (( value == 0 )); then + if (( --value < 0 )); then return 1 fi - ((value--)) - if ! echo "$value" > "$sem"; then return 1 fi @@ -95,67 +92,79 @@ _sem_dec() { } sem_init() { - local name - local value + local name="$1" + local value="$2" - local mutex local sem + local waitlock + local countlock + local counter local owner local err - name="$1" - value="$2" - err=0 + err=1 - mutex=$(_sem_mutexpath "$name") - sem=$(_sem_sempath "$name") - owner=$(_sem_ownerpath "$name") + sem=$(_sem_get_path "$name") + waitlock=$(_sem_get_waitlock "$name") + countlock=$(_sem_get_countlock "$name") + counter=$(_sem_get_counter "$name") + owner=$(_sem_get_owner "$name") - if ! [[ "$value" =~ ^[0-9]+$ ]]; then + if ! is_digits "$value"; then + log_debug "Initial value must be numeric" return 1 fi - if ! mkdir -p "${sem%/*}"; then + if ! mkdir "$sem"; then + log_error "Semaphore $sem exists" return 1 fi - # If the semaphore is new, locking must succeed, - # otherwise it was not a new semaphore - if ! mutex_trylock "$mutex"; then - log_error "Could not acquire $mutex" - return 1 + if ! mutex_trylock "$countlock"; then + log_error "Could not acquire $countlock" + else + # If value is greater than zero, the next call to sem_wait() does + # not have to wait for a sem_post() to happen. Hence the waitlock + # does not need to be locked. + + if ! mutex_trylock "$owner"; then + log_error "Could not acquire mutex $owner" + elif (( value == 0 )) && ! wmutex_trylock "$waitlock"; then + log_error "Could not acquire wmutex $waitlock" + elif ! echo "$value" > "$counter"; then + log_error "Could not write counter $counter" + else + err=0 + fi + + mutex_unlock "$countlock" fi - if ! mutex_trylock "$owner"; then - log_error "Could not acquire $mutex" - err=1 - elif ! echo "$value" > "$sem"; then - err=1 + if (( err != 0 )); then + if ! rm -rf "$sem"; then + log_error "Could not remove $sem" + fi fi - mutex_unlock "$mutex" return "$err" } sem_destroy() { - local name + local name="$1" - local mutex local sem local owner - name="$1" + sem=$(_sem_get_path "$name") + owner=$(_sem_get_owner "$name") - mutex=$(_sem_mutexpath "$name") - sem=$(_sem_sempath "$name") - owner=$(_sem_ownerpath "$name") - - # Make sure only the owner can destroy the semaphore if ! mutex_unlock "$owner"; then + log_debug "Could not unlock $owner" return 1 fi - if ! rm -f "$mutex" "$sem"; then + if ! rm -rf "$sem"; then + log_error "Could not remove $sem" return 1 fi @@ -163,114 +172,118 @@ sem_destroy() { } sem_wait() { - local name + local name="$1" - local mutex - local sem - local passed + local waitlock + local countlock + local counter + local err - name="$1" + waitlock=$(_sem_get_waitlock "$name") + countlock=$(_sem_get_countlock "$name") + counter=$(_sem_get_counter "$name") + err=1 - mutex=$(_sem_mutexpath "$name") - sem=$(_sem_sempath "$name") - passed=false + if ! wmutex_lock "$waitlock"; then + return 1 + fi - while ! "$passed"; do - mutex_lock "$mutex" + if mutex_lock "$countlock"; then + local count - if _sem_dec "$sem"; then - passed=true - fi + _sem_counter_dec "$counter" - mutex_unlock "$mutex" + # if count was greater than 1, we need to unlock the waitlock + # because there won't be anyone calling sem_post() - # Workaround to prevent busy-waiting. The semaphore - # might get increased before we get to the inotifywait, - # in which case we'd wait for a whole second, during - # which another process might pass the semaphore. This - # is not ideal, but to prevent this we'd need something - # like pthread_cond_wait(). - if ! "$passed"; then - inotifywait -qq -t 1 "$sem" + count=$(<"$counter") + if (( count > 0 )); then + wmutex_unlock "$waitlock" fi - done - return 0 + mutex_unlock "$countlock" + err=0 + fi + + return "$err" } sem_trywait() { - local name - - local mutex - local sem - local res - - name="$1" + local name="$1" - mutex=$(_sem_mutexpath "$name") - sem=$(_sem_sempath "$name") - res=1 + local waitlock + local countlock + local counter + local err - mutex_lock "$mutex" + waitlock=$(_sem_get_waitlock "$name") + countlock=$(_sem_get_countlock "$name") + counter=$(_sem_get_counter "$name") + err=1 - if _sem_dec "$sem"; then - res=0 + if ! wmutex_trylock "$waitlock"; then + return 1 fi - mutex_unlock "$mutex" + if mutex_lock "$countlock"; then + _sem_counter_dec "$counter" + mutex_unlock "$countlock" + err=0 + fi - return "$res" + return "$err" } sem_post() { - local name + local name="$1" - local mutex - local sem + local waitlock + local countlock + local counter local err - local value - name="$1" + waitlock=$(_sem_get_waitlock "$name") + countlock=$(_sem_get_countlock "$name") + counter=$(_sem_get_counter "$name") + err=1 - mutex=$(_sem_mutexpath "$name") - sem=$(_sem_sempath "$name") - err=0 + if mutex_lock "$countlock"; then + _sem_counter_inc "$counter" + mutex_unlock "$countlock" - mutex_lock "$mutex" + if [ -L "$waitlock" ]; then + wmutex_unlock "$waitlock" + fi - if ! _sem_inc "$sem"; then - err=1 + err=0 fi - mutex_unlock "$mutex" - return "$err" } sem_peek() { local name="$1" - local mutex - local sem + local countlock + local counter local value local err - mutex=$(_sem_mutexpath "$name") - sem=$(_sem_sempath "$name") - err=false + countlock=$(_sem_get_countlock "$name") + counter=$(_sem_get_counter "$name") + err=1 - mutex_lock "$mutex" + if mutex_lock "$countlock"; then + if value=$(<"$counter"); then + err=0 + fi - if ! value=$(<"$sem"); then - err=true + mutex_unlock "$countlock" fi - mutex_unlock "$mutex" - - if "$err"; then - return 1 + if (( err == 0 )); then + echo "$value" fi - echo "$value" - return 0 + return "$err" } diff --git a/test/sem.sh b/test/sem.sh new file mode 100755 index 0000000..e0f4f43 --- /dev/null +++ b/test/sem.sh @@ -0,0 +1,616 @@ +#!/usr/bin/env bats + +. toolbox.sh +include "sem" + +setup() { + delete=() + return 0 +} + +teardown() { + if (( ${#delete[@]} > 0 )); then + rm -rf "${delete[@]}" + fi + + return 0 +} + +@test "sem00: _sem_get_path() returns the path of a private semaphore if name does not contain slashes" { + local name + local expectation + local reality + + name="hoge" + expectation="$__sem_path/$name" + reality=$(_sem_get_path "$name") + + [[ "$expectation" == "$reality" ]] +} + +@test "sem01: _sem_get_path() returns the path of a public semaphore if name contains a slash" { + local name + local expectation + local reality + + name="hoge/hoge" + expectation="$name" + reality=$(_sem_get_path "$name") + + [[ "$expectation" == "$reality" ]] +} + +@test "sem02: _sem_get_waitlock() returns the path of a private semaphore's waitlock" { + local name + local expectation + local reality + + name="hoge" + expectation="$__sem_path/$name/waitlock" + reality=$(_sem_get_waitlock "$name") + + [[ "$expectation" == "$reality" ]] +} + +@test "sem03: _sem_get_waitlock() returns the path of a public semaphore's waitlock" { + local name + local expectation + local reality + + name="hoge/hoge" + expectation="$name/waitlock" + reality=$(_sem_get_waitlock "$name") + + [[ "$expectation" == "$reality" ]] +} + +@test "sem04: _sem_get_countlock() returns the path of a private semaphore's countlock" { + local name + local expectation + local reality + + name="hoge" + expectation="$__sem_path/$name/countlock" + reality=$(_sem_get_countlock "$name") + + [[ "$expectation" == "$reality" ]] +} + +@test "sem05: _sem_get_countlock() returns the path of a public semaphore's countlock" { + local name + local expectation + local reality + + name="hoge/hoge" + expectation="$name/countlock" + reality=$(_sem_get_countlock "$name") + + [[ "$expectation" == "$reality" ]] +} + +@test "sem06: _sem_get_owner() returns the path of a private semaphore's owner mutex" { + local name + local expectation + local reality + + name="hoge" + expectation="$__sem_path/$name/owner" + reality=$(_sem_get_owner "$name") + + [[ "$expectation" == "$reality" ]] +} + +@test "sem07: _sem_get_owner() returns the path of a public semaphore's owner mutex" { + local name + local expectation + local reality + + name="hoge/hoge" + expectation="$name/owner" + reality=$(_sem_get_owner "$name") + + [[ "$expectation" == "$reality" ]] +} + +@test "sem08: _sem_get_counter() returns path of a private semaphore's counter" { + local name + local expectation + local reality + + name="hoge" + expectation="$__sem_path/$name/counter" + reality=$(_sem_get_counter "$name") + + [[ "$expectation" == "$reality" ]] +} + +@test "sem09: _sem_get_counter() returns path of a public semaphore's counter" { + local name + local expectation + local reality + + name="hoge/hoge" + expectation="$name/counter" + reality=$(_sem_get_counter "$name") + + [[ "$expectation" == "$reality" ]] +} + +@test "sem10: _sem_counter_inc() increases the counter" { + local counter + local value + local i + + counter=$(mktemp) + delete+=("$counter") + + value=0 + echo "$value" > "$counter" + + for (( i = 1; i <= 64; i++ )); do + _sem_counter_inc "$counter" + value=$(<"$counter") + (( value == i )) + done +} + +@test "sem11: _sem_counter_dec() decreases the counter" { + local counter + local value + local i + + counter=$(mktemp) + delete+=("$counter") + + value=64 + echo "$value" > "$counter" + + for (( i = 63; i >= 0; i-- )); do + _sem_counter_dec "$counter" + value=$(<"$counter") + (( value == i )) + done +} + +@test "sem12: sem_init() creates a private semaphore" { + local path + local name + + name="test_sem12_$RANDOM" + path=$(_sem_get_path "$name") + + ! [ -d "$path" ] + sem_init "$name" 0 + [ -d "$path" ] + + delete+=("$path") +} + +@test "sem13: sem_init() creates a public semaphore" { + local path + local name + + path=$(mktemp -d) + delete+=("$path") + name="$path/test_sem13" + + ! [ -d "$name" ] + sem_init "$name" 0 + [ -d "$name" ] +} + +@test "sem14: sem_init() creates a private semaphore" { + local path + local name + + name="test_sem14_$RANDOM" + path=$(_sem_get_path "$name") + + ! [ -d "$name" ] + sem_init "$name" 0 + [ -d "$path" ] + + delete+=("$path") +} + +@test "sem15: sem_init() locks the waitlock if value is 0" { + local path + local name + local waitlock + + path=$(mktemp -d) + delete+=("$path") + name="$path/test_sem15" + + sem_init "$name" 0 + + waitlock=$(_sem_get_waitlock "$name") + + [ -L "$waitlock" ] +} + +@test "sem16: sem_init() does not lock the waitlock if value > 0" { + local path + local i + + path=$(mktemp -d) + delete+=("$path") + + for (( i = 1; i <= 8; i++ )); do + local name + local waitlock + + name="$path/test_sem16_$i" + waitlock=$(_sem_get_waitlock "$name") + + sem_init "$name" "$i" + + ! [ -L "$waitlock" ] + done +} + +@test "sem17: sem_init() does not lock the countlock" { + local path + local i + + path=$(mktemp -d) + delete+=("$path") + + for (( i = 0; i < 8; i++ )); do + local name + local countlock + + name="$path/test_sem17_$i" + countlock=$(_sem_get_countlock "$name") + + sem_init "$name" "$i" + + ! [ -L "$countlock" ] + done +} + +@test "sem18: sem_init() sets the semaphore's counter" { + local path + local i + + path=$(mktemp -d) + delete+=("$path") + + for (( i = 0; i < 8; i++ )); do + local name + local counter + local value + + name="$path/test_sem18_$i" + counter=$(_sem_get_counter "$name") + + sem_init "$name" "$i" + + value=$(<"$counter") + (( value == i )) + done +} + +@test "sem19: sem_init() sets the ownerlock" { + local path + local name + local ownerlock + + path=$(mktemp -d) + delete+=("$path") + + name="$path/test_sem19" + ownerlock=$(_sem_get_owner "$name") + + sem_init "$name" 0 + + [ -L "$ownerlock" ] +} + +@test "sem20: sem_init() makes the current process owner of the semaphore" { + local path + local name + local ownerlock + + path=$(mktemp -d) + delete+=("$path") + + name="$path/test_sem20" + ownerlock=$(_sem_get_owner "$name") + + sem_init "$name" 0 + + owner=$(readlink "$ownerlock") + (( BASHPID == owner )) +} + +@test "sem21: sem_init() makes the subshell owner of the semaphore" { + local path + local name + + path=$(mktemp -d) + delete+=("$path") + + name="$path/test_sem21" + + ( + local ownerlock + local owner + + sem_init "$name" 0 + ownerlock=$(_sem_get_owner "$name") + owner=$(readlink "$ownerlock") + + (( owner == BASHPID )) + (( owner != $$ )) + ) +} + +@test "sem22: sem_init() fails if value is missing" { + local path + local name + + path=$(mktemp -d) + delete+=("$path") + + name="$path/test_sem22" + + ! sem_init "$name" +} + +@test "sem23: sem_init() fails if value is not numeric" { + local path + local name + + path=$(mktemp -d) + delete+=("$path") + + name="$path/test_sem23" + + ! sem_init "$name" "test" +} + +@test "sem24: sem_init() fails if value is negative" { + local path + local name + + path=$(mktemp -d) + delete+=("$path") + + name="$path/test_sem24" + + ! sem_init "$name" -1 +} + +@test "sem25: sem_init() does not create a semaphore if the value is missing" { + local path + local name + + path=$(mktemp -d) + delete+=("$path") + + name="$path/test_sem25" + + ! sem_init "$name" + ! [ -e "$name" ] +} + +@test "sem26: sem_init() does not create a semaphore if the value is not numeric" { + local path + local name + + path=$(mktemp -d) + delete+=("$path") + + name="$path/test_sem26" + + ! sem_init "$name" "test" + ! [ -e "$name" ] +} + +@test "sem27: sem_init() does not create a semaphore if the value is negative" { + local path + local name + + path=$(mktemp -d) + delete+=("$path") + + name="$path/test_sem27" + + ! sem_init "$name" -1 + ! [ -e "$name" ] +} + +@test "sem28: sem_destroy() destroys semaphore if called by owner" { + local path + local name + + path=$(mktemp -d) + delete+=("$path") + + name="$path/test_sem28" + + sem_init "$name" 0 + + [ -e "$name" ] + sem_destroy "$name" + ! [ -e "$name" ] +} + +@test "sem29: sem_destroy() does not destroy another process's semaphore" { + local path + local name + + path=$(mktemp -d) + delete+=("$path") + + name="$path/test_sem29" + + sem_init "$name" 0 + [ -e "$name" ] + ! ( sem_destroy "$name" ) + [ -e "$name" ] +} + +@test "sem30: sem_post() increases the counter by one" { + local name + local path + local counter + local i + + path=$(mktemp -d) + delete+=("$path") + + name="$path/test_sem30" + counter=$(_sem_get_counter "$name") + + sem_init "$name" 0 + + for (( i = 1; i <= 16; i++ )); do + local value + + sem_post "$name" + value=$(<"$counter") + + (( value == i )) + done +} + +@test "sem31: sem_wait() decreases the counter by one" { + local name + local path + local counter + local i + + path=$(mktemp -d) + delete+=("$path") + + name="$path/test_sem31" + counter=$(_sem_get_counter "$name") + + sem_init "$name" 16 + + for (( i = 15; i >= 0; i-- )); do + local value + + sem_wait "$name" + value=$(<"$counter") + + (( value == i )) + done +} + +@test "sem32: sem_wait() locks the waitlock if the counter is 1" { + local name + local path + local waitlock + + path=$(mktemp -d) + delete+=("$path") + + name="$path/test_sem32" + waitlock=$(_sem_get_waitlock "$name") + + sem_init "$name" 1 + sem_wait "$name" + [ -L "$waitlock" ] +} + +@test "sem33: sem_wait() releases the waitlock if the counter is greater than 1" { + local name + local path + local waitlock + + path=$(mktemp -d) + delete+=("$path") + + name="$path/test_sem33" + waitlock=$(_sem_get_waitlock "$name") + + sem_init "$name" 2 + sem_wait "$name" + ! [ -L "$waitlock" ] +} + +@test "sem34: sem_peek() returns the counter of a semaphore" { + local name + local path + local i + + path=$(mktemp -d) + delete+=("$path") + + name="$path/test_sem34" + + sem_init "$name" 0 + + for (( i = 1; i <= 16; i++ )); do + local counter + + sem_post "$name" + counter=$(sem_peek "$name") + (( counter == i )) + done +} + +@test "sem35: sem_post() wakes up sem_wait()" { + local sem + local path + local ppid + local cpid + local timeout + + + path=$(mktemp -d) + delete+=("$path") + + sem="$path/test_sem35" + + sem_init "$sem" 0 + + ( sem_wait "$sem" ) & + cpid="$!" + ( sem_post "$sem" ) & + + for (( timeout = 10; timeout > 0; timeout-- )); do + if ! ps -p "$cpid" &> /dev/null; then + return 0 + fi + + sleep 1 + done + + kill -9 "$cpid" + return 1 +} + +@test "sem36: sem_wait() is woken up by sem_post()" { + local sem + local path + local ppid + local cpid + local timeout + + path=$(mktemp -d) + delete+=("$path") + + timeout=10 + sem="$path/test_sem36" + + sem_init "$sem" 0 + + ( sem_post "$sem" ) & + ( sem_wait "$sem" ) & + cpid="$!" + + for (( timeout = 10; timeout > 0; timeout-- )); do + if ! ps -p "$cpid" &> /dev/null; then + return 0 + fi + + sleep 1 + done + + kill -9 "$cpid" + return 1 +} -- 2.47.3