/** * Copyright (C) Mellanox Technologies Ltd. 2001-2015. ALL RIGHTS RESERVED. * * See file LICENSE for terms. */ #ifndef UCS_ARBITER_H_ #define UCS_ARBITER_H_ #include #include #include #include #include /* * A mechanism to arbitrate among groups of queued work elements, which attempts * to be "fair" with respect to the groups. * * - "Arbiter" - the top-level entity. * - "Element" - a single work element. * - "Group" - queue of work elements which would be dispatched in-order * * The groups and elements are arranged like this: * - every arbitrated element points to the group (head). * - first element in the group points to previous and next group (list) * - first element in the group points to the first element of next group (next_group). * - all except last element point to the next element in same group, and the * last one points to the first (next). * * Note: * Every elements holds 4 pointers. It could be done with 3 pointers, so that * the pointer to the previous group is put instead of "next" pointer in the last * element in the group, when it is put on the arbiter queue. However in makes * the code much more complicated. * * * Arbiter: * +=========+ * | current +-----------------------+ * +=========+ | * | * Elements: | * | * +---------------------------------]----------------------------------+ * | V | * | +------------+ +------------+ +------------+<--+ * +-->| list |<-------->| list |<-------->| list | * +------------+ +------------+ +------------+<--+ * +->| next +---+ +->| next +---+ + next +---+ * | +------------+ | | +------------+ | +------------+ * | | group | | | | group | | | group | * | +------------+ | | +------------+ | +--------+---+ * | | | | ^ | * | | | | | | * | +------------+ | | +------------+ | | | * | | list |<--+ | | list |<--+ | | * | +------------+ | +------------+ | | * +--+ next + +--+ next | | | * +------------+ +------------+ | | * | group | | group | | | * +---------+--+ +--------+---+ | | * ^ | ^ | | | * Groups: | | | | | | * | | | | | | * +------+ | +------+ | +------+ | * | tail |<---+ | tail |<---+ | tail |<---+ * +------+ +------+ +------+ * */ typedef struct ucs_arbiter ucs_arbiter_t; typedef struct ucs_arbiter_group ucs_arbiter_group_t; typedef struct ucs_arbiter_elem ucs_arbiter_elem_t; /** * Arbitration callback result codes. */ typedef enum { UCS_ARBITER_CB_RESULT_REMOVE_ELEM, /* Remove the current element, move to the next element. */ UCS_ARBITER_CB_RESULT_NEXT_GROUP, /* Keep current element and move to next group. Group IS NOT descheduled */ UCS_ARBITER_CB_RESULT_DESCHED_GROUP,/* Keep current element but remove the current group and move to next group. */ UCS_ARBITER_CB_RESULT_RESCHED_GROUP,/* Keep current element, do not process the group anymore during current dispatch cycle. After dispatch() is finished group automatically scheduled */ UCS_ARBITER_CB_RESULT_STOP /* Stop dispatching work altogether. Next dispatch() will start from the group that returned STOP */ } ucs_arbiter_cb_result_t; #if UCS_ENABLE_ASSERT #define UCS_ARBITER_GUARD int guard; #define UCS_ARBITER_GUARD_INIT(_arbiter) (_arbiter)->guard = 0 #define UCS_ARBITER_GUARD_ENTER(_arbiter) (_arbiter)->guard++ #define UCS_ARBITER_GUARD_EXIT(_arbiter) (_arbiter)->guard-- #define UCS_ARBITER_GUARD_CHECK(_arbiter) \ ucs_assertv((_arbiter)->guard == 0, \ "scheduling group from the arbiter callback") #else #define UCS_ARBITER_GUARD #define UCS_ARBITER_GUARD_INIT(_arbiter) #define UCS_ARBITER_GUARD_ENTER(_arbiter) #define UCS_ARBITER_GUARD_EXIT(_arbiter) #define UCS_ARBITER_GUARD_CHECK(_arbiter) #endif /** * Arbiter callback function. * * @param [in] arbiter The arbiter. * @param [in] elem Current work element. * @param [in] arg User-defined argument. * * @return According to @ref ucs_arbiter_cb_result_t. */ typedef ucs_arbiter_cb_result_t (*ucs_arbiter_callback_t)(ucs_arbiter_t *arbiter, ucs_arbiter_elem_t *elem, void *arg); /** * Top-level arbiter. */ struct ucs_arbiter { ucs_arbiter_elem_t *current; UCS_ARBITER_GUARD }; /** * Arbitration group. */ struct ucs_arbiter_group { ucs_arbiter_elem_t *tail; }; /** * Arbitrated work element. * In order to keep it small, one of the fields is a union. */ struct ucs_arbiter_elem { ucs_list_link_t list; /* List link in the scheduler queue */ ucs_arbiter_elem_t *next; /* Next element, last points to head */ ucs_arbiter_group_t *group; /* Always points to the group */ }; /** * Initialize the arbiter object. * * @param [in] arbiter Arbiter object to initialize. */ void ucs_arbiter_init(ucs_arbiter_t *arbiter); void ucs_arbiter_cleanup(ucs_arbiter_t *arbiter); /** * Initialize a group object. * * @param [in] group Group to initialize. */ void ucs_arbiter_group_init(ucs_arbiter_group_t *group); void ucs_arbiter_group_cleanup(ucs_arbiter_group_t *group); /** * Initialize an element object. * * @param [in] elem Element to initialize. */ static inline void ucs_arbiter_elem_init(ucs_arbiter_elem_t *elem) { elem->next = NULL; } /** * Add a new work element to a group - internal function */ void ucs_arbiter_group_push_elem_always(ucs_arbiter_group_t *group, ucs_arbiter_elem_t *elem); /** * Add a new work element to the head of a group - internal function */ void ucs_arbiter_group_push_head_elem_always(ucs_arbiter_t *arbiter, ucs_arbiter_group_t *group, ucs_arbiter_elem_t *elem); /** * Call the callback for each element from a group. If the callback returns * UCS_ARBITER_CB_RESULT_REMOVE_ELEM, remove it from the group. * * @param [in] arbiter Arbiter object to remove the group from. * @param [in] group Group to clean up. * @param [in] cb Callback to be called for each element. * @param [in] cb_arg Last argument for the callback. */ void ucs_arbiter_group_purge(ucs_arbiter_t *arbiter, ucs_arbiter_group_t *group, ucs_arbiter_callback_t cb, void *cb_arg); void ucs_arbiter_dump(ucs_arbiter_t *arbiter, FILE *stream); /* Internal function */ void ucs_arbiter_group_schedule_nonempty(ucs_arbiter_t *arbiter, ucs_arbiter_group_t *group); /* Internal function */ void ucs_arbiter_dispatch_nonempty(ucs_arbiter_t *arbiter, unsigned per_group, ucs_arbiter_callback_t cb, void *cb_arg); /* Internal function */ void ucs_arbiter_group_head_desched(ucs_arbiter_t *arbiter, ucs_arbiter_elem_t *head); /** * Return true if arbiter has no groups scheduled * * @param [in] arbiter Arbiter object to dispatch work on. */ static inline int ucs_arbiter_is_empty(ucs_arbiter_t *arbiter) { return arbiter->current == NULL; } /** * @return whether the group does not have any queued elements. */ static inline int ucs_arbiter_group_is_empty(ucs_arbiter_group_t *group) { return group->tail == NULL; } /** * Schedule a group for arbitration. If the group is already there, the operation * will have no effect. * * @param [in] arbiter Arbiter object to schedule the group on. * @param [in] group Group to schedule. */ static inline void ucs_arbiter_group_schedule(ucs_arbiter_t *arbiter, ucs_arbiter_group_t *group) { if (ucs_unlikely(!ucs_arbiter_group_is_empty(group))) { ucs_arbiter_group_schedule_nonempty(arbiter, group); } } /** * Deschedule already scheduled group. If the group is not scheduled, the operation * will have no effect * * @param [in] arbiter Arbiter object that group on. * @param [in] group Group to deschedule. */ static inline void ucs_arbiter_group_desched(ucs_arbiter_t *arbiter, ucs_arbiter_group_t *group) { if (ucs_unlikely(!ucs_arbiter_group_is_empty(group))) { ucs_arbiter_elem_t *head; head = group->tail->next; ucs_arbiter_group_head_desched(arbiter, head); head->list.next = NULL; } } /** * @return Whether the element is queued in an arbiter group. * (an element can't be queued more than once) * */ static inline int ucs_arbiter_elem_is_scheduled(ucs_arbiter_elem_t *elem) { return elem->next != NULL; } /** * Add a new work element to a group if it is not already there * * @param [in] group Group to add the element to. * @param [in] elem Work element to add. */ static inline void ucs_arbiter_group_push_elem(ucs_arbiter_group_t *group, ucs_arbiter_elem_t *elem) { if (ucs_arbiter_elem_is_scheduled(elem)) { return; } ucs_arbiter_group_push_elem_always(group, elem); } /** * Add a new work element to the head of a group if it is not already there * * @param [in] arbiter Arbiter object the group is on (since we modify the head * element of a potentially scheduled group). If the group * is not scheduled, arbiter may be NULL. * @param [in] group Group to add the element to. * @param [in] elem Work element to add. */ static inline void ucs_arbiter_group_push_head_elem(ucs_arbiter_t *arbiter, ucs_arbiter_group_t *group, ucs_arbiter_elem_t *elem) { if (ucs_arbiter_elem_is_scheduled(elem)) { return; } ucs_arbiter_group_push_head_elem_always(arbiter, group, elem); } /** * Dispatch work elements in the arbiter. For every group, up to per_group work * elements are dispatched, as long as the callback returns REMOVE_ELEM or * NEXT_GROUP. Then, the same is done for the next group, until either the * arbiter becomes empty or the callback returns STOP. If a group is either out * of elements, or its callback returns REMOVE_GROUP, it will be removed until * ucs_arbiter_group_schedule() is used to put it back on the arbiter. * * @param [in] arbiter Arbiter object to dispatch work on. * @param [in] per_group How many elements to dispatch from each group. * @param [in] cb User-defined callback to be called for each element. * @param [in] cb_arg Last argument for the callback. */ static inline void ucs_arbiter_dispatch(ucs_arbiter_t *arbiter, unsigned per_group, ucs_arbiter_callback_t cb, void *cb_arg) { if (ucs_unlikely(!ucs_arbiter_is_empty(arbiter))) { ucs_arbiter_dispatch_nonempty(arbiter, per_group, cb, cb_arg); } } /** * @return Group the element belongs to. */ static inline ucs_arbiter_group_t* ucs_arbiter_elem_group(ucs_arbiter_elem_t *elem) { return elem->group; } /** * @return true if element is the last one in the group */ static inline int ucs_arbiter_elem_is_last(ucs_arbiter_group_t *group, ucs_arbiter_elem_t *elem) { return group->tail == elem; } /** * @return true if element is the only one in the group */ static inline int ucs_arbiter_elem_is_only(ucs_arbiter_group_t *group, ucs_arbiter_elem_t *elem) { return ucs_arbiter_elem_is_last(group, elem) && (elem->next == elem); } #endif