[asterisk-dev] [Code Review] app_queue: maintain some form of order for all round robin queues as members are added/removed from a queue

[jrose]

-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviewboard.asterisk.org/r/2164/#review7285
-----------------------------------------------------------



/branches/1.8/apps/app_queue.c
<https://reviewboard.asterisk.org/r/2164/#comment14060>

    Small addendum here in response to something I uncovered while testing:
    
    	/* If the position being removed is less than the current place in the queue, reduce the queue position by one so that we don't skip the member
    	 * who would have been next otherwise. */
    	if (pos < queue->rrpos) {
    		queue->rrpos--;
    	}
    
    goes between the pos declaration and the ao2_callback.


- jrose


On Oct. 16, 2012, 3:26 p.m., jrose wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviewboard.asterisk.org/r/2164/
> -----------------------------------------------------------
> 
> (Updated Oct. 16, 2012, 3:26 p.m.)
> 
> 
> Review request for Asterisk Developers, Mark Michelson, rmudgett, Matt Jordan, and kmoore.
> 
> 
> Summary
> -------
> 
> This patch is a complicated way to solve what appears on the surface to be a simple problem.
> 
> When using the round robin memory strategy for a queue, Asterisk dumps all members into an ao2_container (read: hash table) without any reliable ordering. In order to get a member out of that hash, for the purpose of calling a member in the queue, it tracks a round robin position variable and simply iterates along the queue members until it reaches that member position.
> 
> Round Robin Ordered causes the order to be forced to the order the members are added by making the hash table have a single bucket, effectively making the container into a linked list. Ordering becomes much more predictable this way.
> 
> The problem reported in this case was that when adding and removing members to/from a queue in various ways, the order isn't preserved. In the case of rrmemory, this is because the items themselves are capable of moving from position to position, so the new member can be placed in front of the old one cause it to 'slide back' in the order. In this manner, it's possible for a single member to be called twice in a row if a member is added between calls into the queue.
> 
> Another problem which can occur when removing a member is that a member will be skipped when a member is removed. This occurs for similar reasons. This also affects round robin ordered unlike with the addition of a member since members can be removed regardless members being in front of or behind them (with rrordered, additions always occur at the end of the linked list)
> 
> Addressing this required the addition of a field to members (rr_queuepos) which tracks where in the queue a member is supposed to be. Each time a member is added, their queuepos is set to be the next available position in the list. If a member is removed from the queue, then that member's order is checked and all members of the queue with a larger order value will see their order decremented by one. If this occurs with many members at once (such as in the case of a reload) then this process may be repeated multiple times so that no value will be skipped.
> 
> This effectively makes the behavior of both round robin queues the same as far as picking which member is next is concerned. I'm not sure if that could be considered a breaking change since the order of rrmemory before isn't guaranteed to follow any particular metric.
> 
> 
> This addresses bug AST-989.
>     https://issues.asterisk.org/jira/browse/AST-989
> 
> 
> Diffs
> -----
> 
>   /branches/1.8/apps/app_queue.c 375024 
> 
> Diff: https://reviewboard.asterisk.org/r/2164/diff
> 
> 
> Testing
> -------
> 
> Checked that order is followed by calling into queues, tested removal and addition from rrordered and rrmemory queues, tested reloads.
> 
> 
> Thanks,
> 
> jrose
> 
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.digium.com/pipermail/asterisk-dev/attachments/20121016/005a958c/attachment.htm>