From patchwork Wed Dec 13 23:38:18 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Oleh Derevenko X-Patchwork-Id: 24922 Received: (qmail 98682 invoked by alias); 13 Dec 2017 23:38:28 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 98669 invoked by uid 89); 13 Dec 2017 23:38:27 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, FREEMAIL_FROM, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: mail-qk0-f174.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to:cc :content-transfer-encoding; bh=8jal5DXPfBMYLjTTjTLRlGHLrw4+u/cVl/RlgU/+NMU=; b=YOqKCKk500s091/Ir+su+zzmvuiqmnoWYdOADxgYW3TxefubCdRL4e07uaw2PxBHs/ YP5CkbT46gO+JW1QtVTvotTmI87KxJsRAFksk3QCHUShWwEHb3OsTxvc4O53vYHGQdbQ uJ6TDJ94Bi+yujm6PH7WTmVwTPVORWPvKr0DZirTrvg1ESmbkrfbzYJjSaoCtWrf2EE/ WY5KDTNv87dn2XrTOtQkQE9m0V6tlGm24mJ1pIBWXRuauVTEcc0PapG+6dFFWg2i9nJy 9bIc30pTak8r2NoSjAbFEQf0sbNo8c+B5a7VDr6dKPFuCkbr+QgfUuKHHap03wnKC3Td 3WBg== X-Gm-Message-State: AKGB3mKXhEBEFaWVfF5fCdwLmED3V5SLj4ZeULHcJ/t3rAMIklVq2E5N meCqzHCiJ2MZ31EkPQjSCPSCA9tAa6iYp5HkVNE= X-Google-Smtp-Source: ACJfBouNusDjj63zAnOISyq4SWiacGfMoQpoc+3t1lBbBsgCYtmmHDobRUcS8SPfKwPvXKFfZcmMZp9lXcXPpuPcp+k= X-Received: by 10.55.19.93 with SMTP id d90mr12759540qkh.271.1513208299125; Wed, 13 Dec 2017 15:38:19 -0800 (PST) MIME-Version: 1.0 From: Oleh Derevenko Date: Thu, 14 Dec 2017 01:38:18 +0200 Message-ID: Subject: [RFC 1/1] Contributing a compound object to the libpthread -- diff To: "Carlos O'Donell" Cc: libc-alpha@sourceware.org misc/mutexgear.c | 798 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ misc/mutexgear.h | 667 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 1465 insertions(+) + * // Assign own completion wheel pointer to the item to indicate the item is being processed. + * // If the pointer value was already not null, it is an indication that + * // the work item is being canceled and no processing is necessary for it. + * if (AtomicSwapPointer(&item->m_worker_wheel_ptr, &context->m_item_completion_wheel) == NULL) + * { + * // Handle the work item extracted. The item pointer is to remain valid. + * HandleWorkItem(item, &exit_requested); // This is to mark the work item completed, if necessary + * + * // Break the item item-object relation. Failure to do it is again an indication + * // that the item is being canceled and is going to be deleted by the canceling thread. + * int unlinked = UnlinkItemFromRelatedObjectList(item); + * + * // Roll the wheel to let the other party know that the item processing is completed. + * pthread_wheel_slaveroll(&context->m_item_completion_wheel); + * + * // If this thread was to break the item-object relation... + * if (unlinked) + * { + * // ... it is responsible for deleting the item. + * DeleteWorkItem(item); + * } + * } + * } + * + * // Finally detach the wheel on exit + * pthread_wheel_detachslave(&context->m_item_completion_wheel); + * } + * + * + * static + * void ClientThread_CancelWorkItemsByRelation(pool_context_t *pool, related_object_t *relation) + * { + * work_item_t *item; + * // Iterate removing the relation items one by one... + * while (UnlinkRelatedObjectNextWorkItem(relation, &item)) + * { + * // If removing the item from the pool work queue succeeds it means + * // that the work on the item has not been started yet and it can be safely deleted. + * if (!RemoveItemFromPoolWorkQueue(pool, item)) + * { + * // Otherwise, swap a not-NULL value (e.g. the item pointer itself) with the wheel pointer content. + * // This is to indicate to any workers that the item is being canceled and does not need to be handled + * // and, at the same time, this is to extract the item completion wheel pointer + * // that might have been already assigned by a worker there. + * pthread_wheel_t *assigned_completion_wheel = (pthread_wheel_t *)AtomicSwapPointer(&item->m_worker_wheel_ptr, item); + * + * // If the current thread was the first to assign the value, it is safe to proceed with deletion immediately + * if (assigned_completion_wheel != NULL + * // Otherwise it may be necessary to wait until the item's handling is over. + * && !IsWorkItemMarkedCompleted(item)) + * { + * // Grip on the assigned wheel + * pthread_wheel_gripon(assigned_completion_wheel); + * + * // Retry item completion tests... + * while (!IsWorkItemMarkedCompleted(item)) + * { + * // ... and turn the wheel until the handling is over + * pthread_wheel_turn(assigned_completion_wheel); + * } + * + * // Finally release the wheel + * pthread_wheel_release(assigned_completion_wheel); + * } + * } + * + * // Release resources allocated to the item + * DeleteWorkItem(item); + * } + * } + * + * \endcode + */ + + +#endif // #ifndef __MUTEXWHEEL_H_INCLUDED + +/************************************************************************/ +/* The synchronization technique used in this file along with */ +/* the object implementations is a subject of U.S. Patent application */ +/* (Application No. 15/155031; Publication No. 2017-0329652) */ +/************************************************************************/ diff --git a/misc/mutexgear.c b/misc/mutexgear.c new file mode 100644 index 0000000..cd2b5d9 --- /dev/null +++ b/misc/mutexgear.c @@ -0,0 +1,798 @@ +/************************************************************************/ +/* The synchronization technique used in this file along with */ +/* the object implementations is a subject of U.S. Patent application */ +/* (Application No. 15/155031; Publication No. 2017-0329652) */ +/************************************************************************/ + +/************************************************************************/ +/* Mutex Gear API, Copyright (c) 2016-2017 Oleh Derevenko */ +/* All rights reserved. E-mail: oleh.derevenko@gmail.com */ +/* Skype: oleh_derevenko */ +/************************************************************************/ + + +/** + * \file + * \brief Mutex Gear API Implementation + * + */ + + +#include "mutexgear.h" +#include + + +#ifndef EOK +#define EOK 0 +#endif + + +////////////////////////////////////////////////////////////////////////// + +/*extern */ +int pthread_toggleattr_init(pthread_toggleattr_t *__attr) +{ + int ret = pthread_mutexattr_init(&__attr->mutexattr); + return ret; +} + +/*extern */ +int pthread_toggleattr_destroy(pthread_toggleattr_t *__attr) +{ + int ret = pthread_mutexattr_destroy(&__attr->mutexattr); + return ret; +} + + +/*extern */ +int pthread_toggleattr_getpshared(const pthread_toggleattr_t *__attr, int *__pshared) +{ + int ret = pthread_mutexattr_getpshared(&__attr->mutexattr, __pshared); + return ret; +} + +/*extern */ +int pthread_toggleattr_setpshared(pthread_toggleattr_t *__attr, int __pshared) +{ + int ret = pthread_mutexattr_setpshared(&__attr->mutexattr, __pshared); + return ret; +} + + +/*extern */ +int pthread_toggleattr_getprioceiling(const pthread_toggleattr_t *__attr, int *__prioceiling) +{ + int ret = pthread_mutexattr_getprioceiling(&__attr->mutexattr, __prioceiling); + return ret; +} + +/*extern */ +int pthread_toggleattr_getprotocol(const pthread_toggleattr_t *__attr, int *__protocol) +{ + int ret = pthread_mutexattr_getprotocol(&__attr->mutexattr, __protocol); + return ret; +} + +/*extern */ +int pthread_toggleattr_setprioceiling(pthread_toggleattr_t *__attr, int __prioceiling) +{ + int ret = pthread_mutexattr_setprioceiling(&__attr->mutexattr, __prioceiling); + return ret; +} + +/*extern */ +int pthread_toggleattr_setprotocol(pthread_toggleattr_t *__attr, int __protocol) +{ + int ret = pthread_mutexattr_setprotocol(&__attr->mutexattr, __protocol); + return ret; +} + + +////////////////////////////////////////////////////////////////////////// + +// Use negative offsets from PTHREAD_TOGGLEELEMENT_INVALID to store pushon indices +#define ENCODE_TOGGLE_PUSHON_INDEX(idx) (PTHREAD_TOGGLEELEMENT_INVALID - (idx)) +#define DECODE_TOGGLE_PUSHON_INDEX(val) (PTHREAD_TOGGLEELEMENT_INVALID - (val)) + +/*extern */ +int pthread_toggle_init(pthread_toggle_t *__toggle, const pthread_toggleattr_t *__attr) +{ + int ret; + + const pthread_mutexattr_t *__mutexattr = __attr ? &__attr->mutexattr : NULL; + + int fault = 0; + unsigned int mutexindex; + for (mutexindex = 0; mutexindex != PTHREAD_TOGGLE_NUMELEMENTS; ++mutexindex) + { + if ((ret = pthread_mutex_init(__toggle->muteces + mutexindex, __mutexattr)) != EOK) + { + for (; mutexindex != 0;) + { + --mutexindex; + pthread_mutex_destroy(__toggle->muteces + mutexindex); + } + + fault = 1; + break; + } + } + + if (!fault) + { + __toggle->thumb_position = PTHREAD_TOGGLEELEMENT_INVALID; + // Store pushon position the attach operation start index + // to aid pushon operations acting on the same indices as the switching is going to do. + __toggle->push_position = ENCODE_TOGGLE_PUSHON_INDEX(PTHREAD_TOGGLEELEMENT_ATTACH_FIRST); + } + + return !fault ? EOK : ret; +} + +/*extern */ +int pthread_toggle_destroy(pthread_toggle_t *__toggle) +{ + int ret; + + int fault = 0; + unsigned int mutexindex; + + if (__toggle->thumb_position == PTHREAD_TOGGLEELEMENT_DESTROYED) + { + // The toggle has already been destroyed + ret = EINVAL; + fault = 1; + } + + for (mutexindex = !fault ? PTHREAD_TOGGLE_NUMELEMENTS : 0; mutexindex != 0;) + { + --mutexindex; + + if ((ret = pthread_mutex_destroy(__toggle->muteces + mutexindex)) != EOK) + { + fault = 1; + break; + } + } + + if (!fault) + { + __toggle->thumb_position = PTHREAD_TOGGLEELEMENT_DESTROYED; + } + + return !fault ? EOK : ret; +} + + +/*extern */ +int pthread_toggle_attach(pthread_toggle_t *__toggle) +{ + int ret; + + int fault = 0; + + if (__toggle->thumb_position == PTHREAD_TOGGLEELEMENT_INVALID) + { + // The toggle has been initialized or detached before - OK to proceed + + int first_index = PTHREAD_TOGGLEELEMENT_ATTACH_FIRST; + + // NOTE! pthread_mutex_trylock() is used instead of pthread_mutex_lock() here! + // External logic must guarantee the toggle is free for attaching at the start position + if ((ret = pthread_mutex_trylock(__toggle->muteces + first_index)) == EOK) + { + __toggle->thumb_position = first_index; + } + else + { + fault = 1; + } + } + else if ((unsigned int)__toggle->thumb_position >= (unsigned int)PTHREAD_TOGGLE_NUMELEMENTS) + { + // The object is in an invalid state + ret = EINVAL; + fault = 1; + } + else + { + // The toggle has already been attached + ret = EBUSY; + fault = 1; + } + + return !fault ? EOK : ret; +} + +/*extern */ +int pthread_toggle_switch(pthread_toggle_t *__toggle) +{ + int ret; + + int fault = 0; + + if (__toggle->thumb_position == PTHREAD_TOGGLEELEMENT_INVALID) + { + // The toggle has not been attached + ret = EPERM; + fault = 1; + } + else if ((unsigned int)__toggle->thumb_position >= (unsigned int)PTHREAD_TOGGLE_NUMELEMENTS) + { + // The object is in an invalid state + ret = EINVAL; + fault = 1; + } + else + { + // OK to proceed + int thumb_position = __toggle->thumb_position; + int next_position = thumb_position != PTHREAD_TOGGLE_NUMELEMENTS - 1 ? thumb_position + 1 : 0; + + if ((ret = pthread_mutex_lock(__toggle->muteces + next_position)) == EOK) + { + if ((ret = pthread_mutex_unlock(__toggle->muteces + thumb_position)) == EOK) + { + __toggle->thumb_position = next_position; + } + else + { + // Revert the next mutex to the initial state and fault + pthread_mutex_unlock(__toggle->muteces + next_position); // Should normally succeed + + fault = 1; + } + } + else + { + fault = 1; + } + } + + return !fault ? EOK : ret; +} + +/*extern */ +int pthread_toggle_detach(pthread_toggle_t *__toggle) +{ + int ret; + + int fault = 0; + + if (__toggle->thumb_position == PTHREAD_TOGGLEELEMENT_INVALID) + { + // The toggle has not been attached + ret = EPERM; + fault = 1; + } + else if ((unsigned int)__toggle->thumb_position >= (unsigned int)PTHREAD_TOGGLE_NUMELEMENTS) + { + // The object is in an invalid state + ret = EINVAL; + fault = 1; + } + else + { + // OK to proceed + if ((ret = pthread_mutex_unlock(__toggle->muteces + __toggle->thumb_position)) == EOK) + { + __toggle->thumb_position = PTHREAD_TOGGLEELEMENT_INVALID; + } + else + { + fault = 1; + } + } + + return !fault ? EOK : ret; +} + + +/*extern */ +int pthread_toggle_pushon(pthread_toggle_t *__toggle) +{ + int ret; + + int fault = 0; + + if ((unsigned int)DECODE_TOGGLE_PUSHON_INDEX(__toggle->push_position) < (unsigned int)PTHREAD_TOGGLE_NUMELEMENTS) + { + // OK to proceed + int pushon_index = DECODE_TOGGLE_PUSHON_INDEX(__toggle->push_position); + + if ((ret = pthread_mutex_lock(__toggle->muteces + pushon_index)) == EOK) + { + pthread_mutex_unlock(__toggle->muteces + pushon_index); // Should normally succeed + + __toggle->push_position = pushon_index != PTHREAD_TOGGLE_NUMELEMENTS - 1 + ? ENCODE_TOGGLE_PUSHON_INDEX(pushon_index + 1) : ENCODE_TOGGLE_PUSHON_INDEX(0); + } + else + { + fault = 1; + } + } + else + { + // The object is in an invalid state + ret = EINVAL; + fault = 1; + } + + return !fault ? EOK : ret; +} + + +////////////////////////////////////////////////////////////////////////// + +/*extern */ +int pthread_wheelattr_init(pthread_wheelattr_t *__attr) +{ + int ret = pthread_mutexattr_init(&__attr->mutexattr); + return ret; +} + +/*extern */ +int pthread_wheelattr_destroy(pthread_wheelattr_t *__attr) +{ + int ret = pthread_mutexattr_destroy(&__attr->mutexattr); + return ret; +} + + +/*extern */ +int pthread_wheelattr_getpshared(const pthread_wheelattr_t *__attr, int *__pshared) +{ + int ret = pthread_mutexattr_getpshared(&__attr->mutexattr, __pshared); + return ret; +} + +/*extern */ +int pthread_wheelattr_setpshared(pthread_wheelattr_t *__attr, int __pshared) +{ + int ret = pthread_mutexattr_setpshared(&__attr->mutexattr, __pshared); + return ret; +} + + +/*extern */ +int pthread_wheelattr_getprioceiling(const pthread_wheelattr_t *__attr, int *__prioceiling) +{ + int ret = pthread_mutexattr_getprioceiling(&__attr->mutexattr, __prioceiling); + return ret; +} + +/*extern */ +int pthread_wheelattr_getprotocol(const pthread_wheelattr_t *__attr, int *__protocol) +{ + int ret = pthread_mutexattr_getprotocol(&__attr->mutexattr, __protocol); + return ret; +} + +/*extern */ +int pthread_wheelattr_setprioceiling(pthread_wheelattr_t *__attr, int __prioceiling) +{ + int ret = pthread_mutexattr_setprioceiling(&__attr->mutexattr, __prioceiling); + return ret; +} + +/*extern */ +int pthread_wheelattr_setprotocol(pthread_wheelattr_t *__attr, int __protocol) +{ + int ret = pthread_mutexattr_setprotocol(&__attr->mutexattr, __protocol); + return ret; +} + + +////////////////////////////////////////////////////////////////////////// + +// Use negative offsets from PTHREAD_WHEELELEMENT_INVALID to store pushon indices +#define ENCODE_WHEEL_PUSHON_INDEX(idx) (PTHREAD_WHEELELEMENT_INVALID - (idx)) +#define DECODE_WHEEL_PUSHON_INDEX(val) (PTHREAD_WHEELELEMENT_INVALID - (val)) + +/*extern */ +int pthread_wheel_init(pthread_wheel_t *__wheel, const pthread_wheelattr_t *__attr) +{ + int ret; + + const pthread_mutexattr_t *__mutexattr = __attr ? &__attr->mutexattr : NULL; + + int fault = 0; + unsigned int mutexindex; + for (mutexindex = 0; mutexindex != PTHREAD_WHEEL_NUMELEMENTS; ++mutexindex) + { + if ((ret = pthread_mutex_init(__wheel->muteces + mutexindex, __mutexattr)) != EOK) + { + for (; mutexindex != 0;) + { + --mutexindex; + pthread_mutex_destroy(__wheel->muteces + mutexindex); + } + + fault = 1; + break; + } + } + + if (!fault) + { + __wheel->slave_index = PTHREAD_WHEELELEMENT_INVALID; + // Store master the attachslave operation start index + // to aid pushon operations acting on the same indices as the slave is going to do. + __wheel->master_index = ENCODE_WHEEL_PUSHON_INDEX(PTHREAD_WHEELELEMENT_ATTACH_FIRST); + } + + return !fault ? EOK : ret; +} + +/*extern */ +int pthread_wheel_destroy(pthread_wheel_t *__wheel) +{ + int ret; + + int fault = 0; + unsigned int mutexindex; + + if (__wheel->slave_index == PTHREAD_WHEELELEMENT_DESTROYED) + { + // The object has already been destroyed + ret = EINVAL; + fault = 1; + } + + for (mutexindex = !fault ? PTHREAD_WHEEL_NUMELEMENTS : 0; mutexindex != 0;) + { + --mutexindex; + + if ((ret = pthread_mutex_destroy(__wheel->muteces + mutexindex)) != EOK) + { + fault = 1; + break; + } + } + + if (!fault) + { + __wheel->slave_index = PTHREAD_WHEELELEMENT_DESTROYED; + } + + return !fault ? EOK : ret; +} + + +/*extern */ +int pthread_wheel_attachslave(pthread_wheel_t *__wheel) +{ + int ret; + + int fault = 0; + + if (__wheel->slave_index == PTHREAD_WHEELELEMENT_INVALID) + { + // The wheel has been initialized or a slave has been detached - OK to proceed + + int first_index = PTHREAD_WHEELELEMENT_ATTACH_FIRST; + // NOTE! pthread_mutex_trylock() is used instead of pthread_mutex_lock() here! + // External logic must guarantee the wheel is free for driven-attaching at the start position + if ((ret = pthread_mutex_trylock(__wheel->muteces + first_index)) == EOK) + { + __wheel->slave_index = first_index; + } + else + { + fault = 1; + } + } + else if ((unsigned int)__wheel->slave_index >= (unsigned int)PTHREAD_WHEEL_NUMELEMENTS) + { + // The object is in an invalid state + ret = EINVAL; + fault = 1; + } + else + { + // A slave had already been attached + ret = EBUSY; + fault = 1; + } + + return !fault ? EOK : ret; +} + +/*extern */ +int pthread_wheel_slaveroll(pthread_wheel_t *__wheel) +{ + // NOTE: This matches the pthread_wheel_turn() but operates with slave_index rather than the master_index + int ret; + + int fault = 0; + + if (__wheel->slave_index == PTHREAD_WHEELELEMENT_INVALID) + { + // Slave has not been attached + ret = EPERM; + fault = 1; + } + else if ((unsigned int)__wheel->slave_index >= (unsigned int)PTHREAD_WHEEL_NUMELEMENTS) + { + // The object is in an invalid state + ret = EINVAL; + fault = 1; + } + else + { + // OK to proceed + int slave_index = __wheel->slave_index; + int next_index = slave_index != PTHREAD_WHEEL_NUMELEMENTS - 1 ? slave_index + 1 : 0; + + if ((ret = pthread_mutex_trylock(__wheel->muteces + next_index)) == EOK) + { + if ((ret = pthread_mutex_unlock(__wheel->muteces + slave_index)) == EOK) + { + __wheel->slave_index = next_index; + } + else + { + // Revert the next mutex to the initial state and fault + pthread_mutex_unlock(__wheel->muteces + next_index); // Should normally succeed + + fault = 1; + } + } + else if (ret == EBUSY) + { + // If the next mutex is busy, it is an indication that the other side still has a turn available/unfinished + // and will be able to still freely check its predicate. Rolling ahead can therefore be skipped. + } + else + { + fault = 1; + } + } +// NOTE: The implementation above corresponds to the Option_2 of the "Event Signaling" step 2. +// The Option_1 would have looked like this: +// ... +// else +// { +// int slave_index = __wheel->slave_index; +// int next_index = slave_index != PTHREAD_WHEEL_NUMELEMENTS - 1 ? slave_index + 1 : 0; +// +// if ((ret = pthread_mutex_lock(__wheel->muteces + next_index)) == EOK +// && (ret = pthread_mutex_unlock(__wheel->muteces + slave_index)) == EOK) +// { +// __wheel->slave_index = next_index; +// } +// else +// { +// fault = 1; +// } +// } +// + return !fault ? EOK : ret; +} + +/*extern */ +int pthread_wheel_detachslave(pthread_wheel_t *__wheel) +{ + // NOTE: This matches the pthread_wheel_release() but operates with slave_index rather than the master_index + int ret; + + int fault = 0; + + if (__wheel->slave_index == PTHREAD_WHEELELEMENT_INVALID) + { + // Slave has not been attached + ret = EPERM; + fault = 1; + } + else if ((unsigned int)__wheel->slave_index >= (unsigned int)PTHREAD_WHEEL_NUMELEMENTS) + { + // The object is in an invalid state + ret = EINVAL; + fault = 1; + } + else + { + // OK to proceed + if ((ret = pthread_mutex_unlock(__wheel->muteces + __wheel->slave_index)) == EOK) + { + __wheel->slave_index = PTHREAD_WHEELELEMENT_INVALID; + } + else + { + fault = 1; + } + } + + return !fault ? EOK : ret; +} + + +/*extern */ +int pthread_wheel_pushon(pthread_wheel_t *__wheel) +{ + // NOTE: Pushons start with the same index as the pthread_wheel_attachslave() does, to come in agreement with it + int ret; + + int fault = 0; + + if ((unsigned int)DECODE_WHEEL_PUSHON_INDEX(__wheel->master_index) < (unsigned int)PTHREAD_WHEEL_NUMELEMENTS) + { + // OK to proceed + int pushon_index = DECODE_WHEEL_PUSHON_INDEX(__wheel->master_index); + + if ((ret = pthread_mutex_lock(__wheel->muteces + pushon_index)) == EOK) + { + pthread_mutex_unlock(__wheel->muteces + pushon_index); // Should normally succeed + + __wheel->master_index = pushon_index != PTHREAD_WHEEL_NUMELEMENTS - 1 + ? ENCODE_WHEEL_PUSHON_INDEX(pushon_index + 1) : ENCODE_WHEEL_PUSHON_INDEX(0); + } + else + { + fault = 1; + } + } + else if ((unsigned int)__wheel->master_index >= (unsigned int)PTHREAD_WHEEL_NUMELEMENTS) + { + // The object is in an invalid state + ret = EINVAL; + fault = 1; + } + else + { + // The object had been gripped on and is not available for pushing unless is released + ret = EBUSY; + fault = 1; + } + + return !fault ? EOK : ret; +} + + +/*extern */ +int pthread_wheel_gripon(pthread_wheel_t *__wheel) +{ + int ret; + + int fault = 0; + + if ((unsigned int)DECODE_WHEEL_PUSHON_INDEX(__wheel->master_index) < (unsigned int)PTHREAD_WHEEL_NUMELEMENTS) + { + // Up to PTHREAD_WHEEL_NUMELEMENTS down starting with PTHREAD_WHEELELEMENT_INVALID indicate + // that there might be pthread_wheel_pushon calls before or there might be none of them. + // Both cases are OK. + + int trial_index; + // Get the last pushon index (if any) to start seeking with + for (trial_index = DECODE_WHEEL_PUSHON_INDEX(__wheel->master_index); ; ) + { + // Do trials in reverse direction to avoid risk of following the other side's locks. + // Start immediately with a decrement since the last pushon index is likely to be still occupied by the slave. + trial_index = trial_index != 0 ? trial_index - 1 : PTHREAD_WHEEL_NUMELEMENTS - 1; + + if ((ret = pthread_mutex_trylock(__wheel->muteces + trial_index)) == EOK) + { + __wheel->master_index = trial_index; + break; + } + else if (ret != EBUSY) + { + fault = 1; + break; + } + } + } + else if ((unsigned int)__wheel->master_index >= (unsigned int)PTHREAD_WHEEL_NUMELEMENTS) + { + // The object is in an invalid state + ret = EINVAL; + fault = 1; + } + else + { + // The object had already been gripped on + ret = EBUSY; + fault = 1; + } + + return !fault ? EOK : ret; +} + +/*extern */ +int pthread_wheel_turn(pthread_wheel_t *__wheel) +{ + // NOTE: This matches the pthread_wheel_slaveroll() but operates with master_index rather than the slave_index + int ret; + + int fault = 0; + + if ((unsigned int)DECODE_WHEEL_PUSHON_INDEX(__wheel->master_index) < (unsigned int)PTHREAD_WHEEL_NUMELEMENTS) + { + // Up to PTHREAD_WHEEL_NUMELEMENTS down starting with PTHREAD_WHEELELEMENT_INVALID indicate + // that there migth or might not be pthread_wheel_pushon calls but the wheel has not been gripped on + ret = EPERM; + fault = 1; + } + else if ((unsigned int)__wheel->master_index >= (unsigned int)PTHREAD_WHEEL_NUMELEMENTS) + { + // The object is in an invalid state + ret = EINVAL; + fault = 1; + } + else + { + // OK to proceed + int master_index = __wheel->master_index; + int next_index = master_index != PTHREAD_WHEEL_NUMELEMENTS - 1 ? master_index + 1 : 0; + + if ((ret = pthread_mutex_lock(__wheel->muteces + next_index)) == EOK) + { + if ((ret = pthread_mutex_unlock(__wheel->muteces + master_index)) == EOK) + { + __wheel->master_index = next_index; + } + else + { + // Revert the next mutex to the initial state and fault + pthread_mutex_unlock(__wheel->muteces + next_index); // Should normally succeed + + fault = 1; + } + } + else + { + fault = 1; + } + } + + return !fault ? EOK : ret; +} + +/*extern */ +int pthread_wheel_release(pthread_wheel_t *__wheel) +{ + // NOTE: This matches the pthread_wheel_detachslave() but operates with master_index rather than the slave_index + int ret; + + int fault = 0; + + if ((unsigned int)DECODE_WHEEL_PUSHON_INDEX(__wheel->master_index) < (unsigned int)PTHREAD_WHEEL_NUMELEMENTS) + { + // Up to PTHREAD_WHEEL_NUMELEMENTS down starting with PTHREAD_WHEELELEMENT_INVALID indicate + // that there migth or might not be pthread_wheel_pushon calls but the wheel has not been gripped on + ret = EPERM; + fault = 1; + } + else if ((unsigned int)__wheel->master_index >= (unsigned int)PTHREAD_WHEEL_NUMELEMENTS) + { + // The object is in an invalid state + ret = EINVAL; + fault = 1; + } + else + { + // OK to proceed + int master_index = __wheel->master_index; + + if ((ret = pthread_mutex_unlock(__wheel->muteces + master_index)) == EOK) + { + // Store the next index as a pushon index to allow continuing + // with the object in pushon mode + __wheel->master_index = master_index != PTHREAD_WHEEL_NUMELEMENTS - 1 + ? ENCODE_WHEEL_PUSHON_INDEX(master_index + 1) : ENCODE_WHEEL_PUSHON_INDEX(0); + } + else + { + fault = 1; + } + } + + return !fault ? EOK : ret; +} + +/************************************************************************/ +/* The synchronization technique used in this file along with */ +/* the object implementations is a subject of U.S. Patent application */ +/* (Application No. 15/155031; Publication No. 2017-0329652) */ +/************************************************************************/ diff --git a/misc/mutexgear.h b/misc/mutexgear.h new file mode 100644 index 0000000..8af7d57 --- /dev/null +++ b/misc/mutexgear.h @@ -0,0 +1,667 @@ +/************************************************************************/ +/* The synchronization technique used in this file along with */ +/* the object implementations is a subject of U.S. Patent application */ +/* (Application No. 15/155031; Publication No. 2017-0329652) */ +/************************************************************************/ + +#ifndef __MUTEXWHEEL_H_INCLUDED +#define __MUTEXWHEEL_H_INCLUDED + + +/************************************************************************/ +/* Mutex Gear API, Copyright (c) 2016-2017 Oleh Derevenko */ +/* All rights reserved. E-mail: oleh.derevenko@gmail.com */ +/* Skype: oleh_derevenko */ +/************************************************************************/ + +/** + * \file + * \brief Mutex Gear API Definitions + * + * The module defines two objects: a "toggle" and a "wheel". + * The toggle implements the coordinated operation mode + * while the wheel provides the independent operation as described + * in the Application document. + */ + + +#include +#include + + +////////////////////////////////////////////////////////////////////////// + +/* + * \typedef pthread_toggleattr_t + * \brief An attributes structure used to define the attributes of a \c toggle object on creation + */ +typedef struct _pthread_toggleattr_t +{ + pthread_mutexattr_t mutexattr; + +} pthread_toggleattr_t; + +/* + * \fn int pthread_toggleattr_init(pthread_toggleattr_t *__attr) + * \brief A function to initialize a \c pthread_toggleattr_t instance. + */ +int pthread_toggleattr_init(pthread_toggleattr_t *__attr); +/* + * \fn int pthread_toggleattr_destroy(pthread_toggleattr_t *__attr) + * \brief A function to destroy a previously initialized \c pthread_toggleattr_t + * instance and free any resources possibly allocated for it. + */ +int pthread_toggleattr_destroy(pthread_toggleattr_t *__attr); + +/* + * \fn int pthread_toggleattr_getpshared(const pthread_toggleattr_t *__attr, int *__pshared) + * \brief A function to get process shared attribute value stored in a \c toggleattr + * structure (similar to the \c pthread_mutexattr_getpshared). + */ +int pthread_toggleattr_getpshared(const pthread_toggleattr_t *__attr, int *__pshared); +/* + * \fn int pthread_toggleattr_setpshared(pthread_toggleattr_t *__attr, int __pshared) + * \brief A function to assign process shared attribute value to a \c toggleattr + * structure (similar to the \c pthread_mutexattr_setpshared). + */ +int pthread_toggleattr_setpshared(pthread_toggleattr_t *__attr, int __pshared); + +/* + * \fn int pthread_toggleattr_getprioceiling(const pthread_toggleattr_t *__attr, int *__prioceiling) + * \brief A function to query priority ceiling attribute value stored in a \c toggleattr + * structure (similar to the \c pthread_mutexattr_getprioceiling). + */ +int pthread_toggleattr_getprioceiling(const pthread_toggleattr_t *__attr, int *__prioceiling); +/* + * \fn int pthread_toggleattr_getprotocol(const pthread_toggleattr_t *__attr, int *__protocol) + * \brief A function to retrieve lock protocol attribute value stored in a \c toggleattr + * structure (similar to the \c pthread_mutexattr_getprotocol). + */ +int pthread_toggleattr_getprotocol(const pthread_toggleattr_t *__attr, int *__protocol); +/* + * \fn int pthread_toggleattr_setprioceiling(pthread_toggleattr_t *__attr, int __prioceiling) + * \brief A function to assign a priority ceiling value to a \c toggleattr + * structure (similar to the \c pthread_mutexattr_setprioceiling). + */ +int pthread_toggleattr_setprioceiling(pthread_toggleattr_t *__attr, int __prioceiling); +/* + * \fn int pthread_toggleattr_setprotocol(pthread_toggleattr_t *__attr, int __protocol) + * \brief A function to set a lock protocol value to a \c toggleattr + * structure (similar to the \c pthread_mutexattr_setprotocol). + */ +int pthread_toggleattr_setprotocol(pthread_toggleattr_t *__attr, int __protocol); + + +enum +{ + PTHREAD_TOGGLEELEMENT_DESTROYED = INT_MIN, + // The commented elements below are occupied (implicitly used in code) + // _PTHREAD_TOGGLEELEMENT_PUSHON_SECOND = -2, == PTHREAD_TOGGLEELEMENT_INVALID - _PTHREAD_TOGGLEELEMENT_SECOND + // _PTHREAD_TOGGLEELEMENT_PUSHON_FIRST = -1, == PTHREAD_TOGGLEELEMENT_INVALID - _PTHREAD_TOGGLEELEMENT_FIRST + PTHREAD_TOGGLEELEMENT_INVALID = -1, + _PTHREAD_TOGGLEELEMENT_FIRST = 0, + // _PTHREAD_TOGGLEELEMENT_SECOND = 1, + + PTHREAD_TOGGLE_NUMELEMENTS = 2, + PTHREAD_TOGGLEELEMENT_ATTACH_FIRST = _PTHREAD_TOGGLEELEMENT_FIRST, +}; + +/* + * \typedef pthread_toggle_t + * \brief A \c toggle object structure. + */ +typedef struct _pthread_toggle_t +{ + pthread_mutex_t muteces[PTHREAD_TOGGLE_NUMELEMENTS]; + int thumb_position; + int push_position; + +} pthread_toggle_t; + +/* + * \def PTHREAD_TOGGLE_INITIALIZER + * \brief A \c toggle object in-place static initializer (similar to \c PTHREAD_MUTEX_INITIALIZER). + */ +#define PTHREAD_TOGGLE_INITIALIZER { { PTHREAD_MUTEX_INITIALIZER, PTHREAD_MUTEX_INITIALIZER }, PTHREAD_TOGGLEELEMENT_INVALID } + + +/* + * \fn int pthread_toggle_init(pthread_toggle_t *__toggle, const pthread_toggleattr_t *__attr) + * \brief A function to create a \c toggle object with attributes defined in the \c toggleattr instance. + */ +int pthread_toggle_init(pthread_toggle_t *__toggle, const pthread_toggleattr_t *__attr); +/* + * \fn int pthread_toggle_destroy(pthread_toggle_t *__toggle) + * \brief A function to destroy a \c toggle instance and release any resources that might be allocated for it. + */ +int pthread_toggle_destroy(pthread_toggle_t *__toggle); + + +/* + * \fn int pthread_toggle_attach(pthread_toggle_t *__toggle) + * \brief A function to attach to the \c toggle to be called + * by the signaler (the S) thread to accomplish the Precondition 1. + */ +int pthread_toggle_attach(pthread_toggle_t *__toggle); +/* + * \fn int pthread_toggle_switch(pthread_toggle_t *__toggle) + * \brief A function to be called by the signaler (the S) thread + * to notify a potential waiter of an event. This corresponds + * to the steps 1-3 of the "Event Signaling" section. + */ +int pthread_toggle_switch(pthread_toggle_t *__toggle); +/* + * \fn int pthread_toggle_detach(pthread_toggle_t *__toggle) + * \brief A function to be called by the signaler (the S) thread + * to release the \c toggle object whenever it is not going to be used any more. + */ +int pthread_toggle_detach(pthread_toggle_t *__toggle); + +/* + * \fn int pthread_toggle_pushon(pthread_toggle_t *__toggle) + * \brief A function to be called by the waiter (the W) thread + * to block waiting for an event notification. This corresponds + * to the steps 1-3 of the "Event Waiting" section. + */ +int pthread_toggle_pushon(pthread_toggle_t *__toggle); + + +////////////////////////////////////////////////////////////////////////// + +/* + * \typedef pthread_wheelattr_t + * \brief An attributes structure used to define the attributes of a \c wheel object on creation. + */ +typedef struct _pthread_wheelattr_t +{ + pthread_mutexattr_t mutexattr; + +} pthread_wheelattr_t; + + +/* + * \fn int pthread_wheelattr_init(pthread_wheelattr_t *__attr) + * \brief A function to initialize a \c pthread_wheelattr_t instance. + */ +int pthread_wheelattr_init(pthread_wheelattr_t *__attr); +/* + * \fn int pthread_wheelattr_destroy(pthread_wheelattr_t *__attr) + * \brief A function to destroy a previously initialized \c pthread_wheelattr_t + * instance and free any resources possibly allocated for it. + */ +int pthread_wheelattr_destroy(pthread_wheelattr_t *__attr); + +/* + * \fn int pthread_wheelattr_getpshared(const pthread_wheelattr_t *__attr, int *__pshared) + * \brief A function to get process shared attribute value stored in + * a \c wheelattr structure (similar to the \c pthread_mutexattr_getpshared). + */ +int pthread_wheelattr_getpshared(const pthread_wheelattr_t *__attr, int *__pshared); +/* + * \fn int pthread_wheelattr_setpshared(pthread_wheelattr_t *__attr, int __pshared) + * \brief A function to assign process shared attribute value to + * a \c wheelattr structure (similar to \c the pthread_mutexattr_setpshared). + */ +int pthread_wheelattr_setpshared(pthread_wheelattr_t *__attr, int __pshared); + +/* + * \fn int pthread_wheelattr_getprioceiling(const pthread_wheelattr_t *__attr, int *__prioceiling) + * \brief A function to query priority ceiling attribute value + * stored in a \c wheelattr structure (similar to the \c pthread_mutexattr_getprioceiling). + */ +int pthread_wheelattr_getprioceiling(const pthread_wheelattr_t *__attr, int *__prioceiling); +/* + * \fn int pthread_wheelattr_getprotocol(const pthread_wheelattr_t *__attr, int *__protocol) + * \brief A function to retrieve lock protocol attribute value + * stored in a \c wheelattr structure (similar to the \c pthread_mutexattr_getprotocol). + */ +int pthread_wheelattr_getprotocol(const pthread_wheelattr_t *__attr, int *__protocol); +/* + * \fn int pthread_wheelattr_setprioceiling(pthread_wheelattr_t *__attr, int __prioceiling) + * \brief A function to assign a priority ceiling value to + * a \c wheelattr structure (similar to the \c pthread_mutexattr_setprioceiling). + */ +int pthread_wheelattr_setprioceiling(pthread_wheelattr_t *__attr, int __prioceiling); +/* + * \fn int pthread_wheelattr_setprotocol(pthread_wheelattr_t *__attr, int __protocol) + * \brief A function to set a lock protocol value to + * a \c wheelattr structure (similar to the \c pthread_mutexattr_setprotocol). + */ +int pthread_wheelattr_setprotocol(pthread_wheelattr_t *__attr, int __protocol); + + +enum +{ + PTHREAD_WHEELELEMENT_DESTROYED = INT_MIN, + // The commented elements below are occupied (implicitly used in code) + // _PTHREAD_WHEELELEMENT_PUSHON_THIRD = -3, == PTHREAD_WHEELELEMENT_INVALID - _PTHREAD_WHEELELEMENT_THIRD + // _PTHREAD_WHEELELEMENT_PUSHON_SECOND = -2, == PTHREAD_WHEELELEMENT_INVALID - _PTHREAD_WHEELELEMENT_SECOND + // _PTHREAD_WHEELELEMENT_PUSHON_FIRST = -1, == PTHREAD_WHEELELEMENT_INVALID - _PTHREAD_WHEELELEMENT_FIRST + PTHREAD_WHEELELEMENT_INVALID = -1, + _PTHREAD_WHEELELEMENT_FIRST = 0, + // _PTHREAD_WHEELELEMENT_SECOND = 1, + // _PTHREAD_WHEELELEMENT_THIRD = 2, + + PTHREAD_WHEEL_NUMELEMENTS = 3, + PTHREAD_WHEELELEMENT_ATTACH_FIRST = _PTHREAD_WHEELELEMENT_FIRST, +}; + +/* + * \typedef pthread_wheel_t + * \brief A wheel object structure. + */ +typedef struct _pthread_wheel_t +{ + pthread_mutex_t muteces[PTHREAD_WHEEL_NUMELEMENTS]; + int slave_index; + int master_index; + +} pthread_wheel_t; + +/* + * \def PTHREAD_WHEEL_INITIALIZER + * \brief A \c wheel object in-place static initializer (similar to \c PTHREAD_MUTEX_INITIALIZER). + */ +#define PTHREAD_WHEEL_INITIALIZER { { PTHREAD_MUTEX_INITIALIZER, PTHREAD_MUTEX_INITIALIZER, PTHREAD_MUTEX_INITIALIZER }, PTHREAD_WHEELELEMENT_INVALID, PTHREAD_WHEELELEMENT_INVALID } + + +/* + * \fn int pthread_wheel_init(pthread_wheel_t *__wheel, const pthread_wheelattr_t *__attr) + * \brief A function to create a \c wheel object with attributes defined in the \c wheelattr instance. + */ +int pthread_wheel_init(pthread_wheel_t *__wheel, const pthread_wheelattr_t *__attr); +/* + * \fn int pthread_wheel_destroy(pthread_wheel_t *__wheel) + * \brief A function to destroy a \c wheel instance and release any resources + * that might be allocated for it. + */ +int pthread_wheel_destroy(pthread_wheel_t *__wheel); + + +/* + * \fn int pthread_wheel_attachslave(pthread_wheel_t *__wheel) + * \brief A function to attach to the toggle to be called by the signaler (the S) thread + * to accomplish the independent operation Precondition 1. + */ +int pthread_wheel_attachslave(pthread_wheel_t *__wheel); +/* + * \fn int pthread_wheel_slaveroll(pthread_wheel_t *__wheel) + * \brief A function to be called by the signaler (the S) thread + * to notify a potential waiter of an event. This corresponds to + * the step 2.-Option_2 of the "Event Signaling" section + * (to be called after changing the V predicate to an "event happened" meaning). + */ +int pthread_wheel_slaveroll(pthread_wheel_t *__wheel); +/* + * \fn int pthread_wheel_detachslave(pthread_wheel_t *__wheel) + * \brief A function to be called by the signaler (the S) thread + * to release the \c wheel object whenever it is not going to be used any more. + */ +int pthread_wheel_detachslave(pthread_wheel_t *__wheel); + +/* + * \fn int pthread_wheel_pushon(pthread_wheel_t *__wheel) + * \brief A compatibility function to use a \c wheel object in coordinated mode + * replicating a \c toggle object’s functionality. The synchronization effects + * this function achieves with the \c wheel object are the same as + * the \c pthread_toggle_pushon function with a \c toggle object would do. + */ +int pthread_wheel_pushon(pthread_wheel_t *__wheel); + +/* + * \fn int pthread_wheel_gripon(pthread_wheel_t *__wheel) + * \brief A function to be called by a waiter (the W) thread + * to initiate a waiting operation. This corresponds to the step 1 of the "Event Waiting" section. + */ +int pthread_wheel_gripon(pthread_wheel_t *__wheel); +/* + * \fn int pthread_wheel_turn(pthread_wheel_t *__wheel) + * \brief A function to be called by the waiter (the W) thread + * to re-lock serializing synchronization to the next object as described + * in the step 2 of the "Event Waiting" section. + * + * This is to be done in a loop each time after evaluating the V predicate + * unless and until its value indicates the event occurrence. + */ +int pthread_wheel_turn(pthread_wheel_t *__wheel); +/* + * \fn int pthread_wheel_release(pthread_wheel_t *__wheel) + * \brief A function to be called by the waiter (the W) thread + * to end the event waiting operation releasing the currently locked + * serializing synchronization object as described in the step 3 + * of the "Event Waiting" section. + */ +int pthread_wheel_release(pthread_wheel_t *__wheel); + + + +/* + * Some usage examples: + * + * 1. Scheduling a task in a worker thread an waiting for it to complete + * (a coordinated execution mode example) + * + * \code + * + * typedef struct worker_context + * { + * pthread_toggle_t m_completion_toggle; + * // ... + * + * } worker_context_t; + * + * typedef struct work_item + * { + * //... + * + * } work_item_t; + * + * + * // Notify the upper logical level that the worker has finished initializing and is ready. + * extern void NotifyHostWorkerThreadIsReady(worker_context_t *context); + * // Test if the worker has already notified the upper logical level about being ready. + * extern int IsHostNotifiedOfWorkerThreadBeingReady(worker_context_t *worker); + * // Assign the item for execution and wake the worker up. + * extern void AssignAWorkItem(worker_context_t *context, work_item_t *item); + * // Extract next work item to be processed or block the caller if there are none. + * extern work_item_t *ExtractPendingWorkItem(worker_context_t *context); + * // Perform work item intended operations and mark it as completed. + * // Return exit request status as implied by the work item. + * extern void HandleWorkItem(work_item_t *item, int *out_exit_requested); + * // Test if the item has already been marked as completed by a worker. + * extern int IsWorkItemMarkedCompleted(work_item_t *item); + * + * + * static + * void ClientThread_ScheduleWorkItem(worker_context_t *worker, work_item_t *item) + * { + * // The function can only be called after the worker initialization phase ends + * assert(IsHostNotifiedOfWorkerThreadBeingReady(worker)); + * + * // Assign a work item and wake the worker up. + * AssignAWorkItem(worker, item); + * } + * + * static + * void WorkerThread_ThreadRoutine(worker_context_t *context) + * { + * // Initially attach the toggle + * pthread_toggle_attach(&context->m_completion_toggle); + * + * // Let the upper level know the worked has been started + * // and is ready to serve requests (the toggle has been attached) + * NotifyHostWorkerThreadIsReady(context); + * + * int exit_requested; + * for (exit_requested = 0; !exit_requested; ) + * { + * // Extract a next item to handle. Block if there are no items queued. + * work_item_t *item = ExtractPendingWorkItem(context); + * // Handle the work item extracted + * HandleWorkItem(item, &exit_requested); // This is to mark the work item completed + * + * // Switch the toggle each time after an item has been handled + * pthread_toggle_switch(&context->m_completion_toggle); + * } + * + * // Finally detach the toggle on exit + * pthread_toggle_detach(&context->m_completion_toggle); + * } + * + * static + * void ClientThread_WaitWorkItemCompletion(worker_context_t *worker, work_item_t *item) + * { + * // Just push the toggle on... + * pthread_toggle_pushon(&worker->m_completion_toggle); + * + * // ...and assert that the work item has indeed completed + * assert(IsWorkItemMarkedCompleted(item)); + * } + * + * \endcode + * + * + * 2. Waiting for room in a limited size work queue to push work item into + * + * \code + * + * typedef struct worker_context + * { + * pthread_wheel_t m_item_extraction_wheel; + * // ... + * + * } worker_context_t; + * + * typedef struct work_item + * { + * // ... + * + * } work_item_t; + * + * // Notify the upper logical level that the worker has finished initializing and is ready + * extern void NotifyHostWorkerThreadIsReady(worker_context_t *context); + * // Test if the worker has already notified the upper logical level about being ready + * extern int IsHostNotifiedOfWorkerThreadBeingReady(worker_context_t *worker); + * // Insert the item into the work queue and wake the worker up if the queue was empty. + * extern int QueueAWorkItem(worker_context_t *context, work_item_t *item); + * // Extract next work item to be processed or block the caller if there are none. + * extern work_item_t *ExtractPendingWorkItem(worker_context_t *context); + * // Perform work item intended operations and release resources allocated to the item. + * // Return exit request status as implied by the work item. + * extern void HandleAndDeleteWorkItem(work_item_t *item, int *out_exit_requested); + * + * static + * void WorkerThread_ThreadRoutine(worker_context_t *context) + * { + * // Initially attach the wheel as the slave + * pthread_wheel_attachslave(&context->m_item_extraction_wheel); + * + * // Let the upper level know the worked has been started + * // and is ready to serve requests (the toggle has been attached) + * NotifyHostWorkerThreadIsReady(context); + * + * int exit_requested; + * for (exit_requested = 0; !exit_requested; ) + * { + * // Extract a next item to handle. Block if there are no items queued. + * work_item_t *item = ExtractPendingWorkItem(context); + * // Roll the wheel to let the other side know there is some room in queue + * pthread_wheel_slaveroll(&context->m_item_extraction_wheel); + * + * // Handle the work item extracted + * HandleAndDeleteWorkItem(item, &exit_requested); + * } + * + * // Finally detach the wheel on exit + * pthread_wheel_detachslave(&context->m_item_extraction_wheel); + * } + * + * static + * void ClientThread_ScheduleWorkItem(worker_context_t *worker, work_item_t *item) + * { + * // The function can only be called after the worker initialization phase ends + * assert(IsHostNotifiedOfWorkerThreadBeingReady(worker)); + * + * // Push the item into the work queue. Wake the worker up if the queue was empty. + * // False return indicates there is no room for the item. + * if (!QueueAWorkItem(worker, item)) + * { + * // Grip on the wheel + * pthread_wheel_gripon(&worker->m_item_extraction_wheel); + * + * // Retry queuing attempts... + * while (!QueueAWorkItem(worker, item)) + * { + * // ... and turn the wheel until the queuing succeeds + * pthread_wheel_turn(&worker->m_item_extraction_wheel); + * } + * + * // Finally, release the wheel + * pthread_wheel_release(&worker->m_item_extraction_wheel); + * } + * } + * + * \endcode + * + * + * 3. Canceling all work items scheduled into a thread pool by relation to a particular object. + * + * \code + * + * typedef struct pool_context + * { + * // ... + * + * } pool_context_t; + * + * typedef struct worker_context + * { + * pool_context_t *m_pool; + * pthread_wheel_t m_item_completion_wheel; + * // ... + * + * } worker_context_t; + * + * typedef struct work_item + * { + * void *volatile m_worker_wheel_ptr; // To be initialized with NULL + * // ... + * + * } work_item_t; + * + * typedef struct related_object + * { + * // ... + * + * } related_object_t; + * + * // Atomically swap the value with the destination content and return the latter. + * extern void *AtomicSwapPointer(void *volatile *destination_ptr, void *value); + * // Establish a relation connection between the object and the item (e.g. link the item in an object-local list). + * extern void LinkItemIntoRelatedObjectList(related_object_t *relation, work_item_t *item); + * // Break the relation connection of the item (e.g. by unlinking the item from its current object-local list). + * // The return status is "false" if the relation has already been broken by other party. + * extern int UnlinkItemFromRelatedObjectList(work_item_t *item); + * // Remove and return next item from the object-local relation list. The boolean result indicates item availability. + * extern int UnlinkRelatedObjectNextWorkItem(related_object_t *relation, work_item_t **out_item); + * // Insert the item into the pool-local work queue and wake up a worker if necessary. + * extern void QueueAWorkItem(pool_context_t *pool, work_item_t *item); + * // Extract next work item to be processed or block the caller if there are none. + * extern work_item_t *ExtractPendingWorkItem(pool_context_t *pool); + * // Remove the given item from pool execution queue. The return status is "false" + * // if the item has already been removed by a worker. + * extern int RemoveItemFromPoolWorkQueue(pool_context_t *pool, work_item_t *item); + * // Perform work item intended operations and mark it as completed. + * // Return exit request status as implied by the work item. + * extern void HandleWorkItem(work_item_t *item, int *out_exit_requested); + * // Test if the item has already been marked as completed by a worker. + * extern int IsWorkItemMarkedCompleted(work_item_t *item); + * // Release any resources allocated to the item + * extern void DeleteWorkItem(work_item_t *item); + * + * static + * void ClientThread_ScheduleWorkItem(pool_context_t *pool, related_object_t *relation, work_item_t *item) + * { + * // Establish item to object relation. + * LinkItemIntoRelatedObjectList(relation, item); + * // Push the item into the pool queue. Wake a new worker up if necessary. + * QueueAWorkItem(pool, item); + * } + * + * + * static + * void WorkerThread_ThreadRoutine(worker_context_t *context) + * { + * // Initially attach the wheel as the slave + * pthread_wheel_attachslave(&context->m_item_completion_wheel); + * + * pool_context_t *pool = context->m_pool; + * + * int exit_requested; + * for (exit_requested = 0; !exit_requested; ) + * { + * // Extract a next item to handle. Block if there are no items queued. + * work_item_t *item = ExtractPendingWorkItem(pool); + *