[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/
-----------------------------------------------------------

(Updated Oct. 18, 2012, 9:36 a.m.)


Review request for Asterisk Developers, Mark Michelson, rmudgett, Matt Jordan, and kmoore.


Changes
-------

Update to reflect Richard's notes about locking containers and linear queue.

I should probably test the linear queue stuff at some point.


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 (updated)
-----

  /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/20121018/31d53a03/attachment.htm>