<html>
<body>
<div style="font-family: Verdana, Arial, Helvetica, Sans-Serif;">
<table bgcolor="#f9f3c9" width="100%" cellpadding="8" style="border: 1px #c9c399 solid;">
<tr>
<td>
This is an automatically generated e-mail. To reply, visit:
<a href="https://reviewboard.asterisk.org/r/2164/">https://reviewboard.asterisk.org/r/2164/</a>
</td>
</tr>
</table>
<br />
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: 10px;">
<p style="margin-top: 0;">On October 17th, 2012, 4:05 p.m., <b>rmudgett</b> wrote:</p>
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: 10px;">
<table width="100%" border="0" bgcolor="white" style="border: 1px solid #C0C0C0; border-collapse: collapse; margin: 2px padding: 2px;">
<thead>
<tr>
<th colspan="4" bgcolor="#F0F0F0" style="border-bottom: 1px solid #C0C0C0; font-size: 9pt; padding: 4px 8px; text-align: left;">
<a href="https://reviewboard.asterisk.org/r/2164/diff/1/?file=31870#file31870line4245" style="color: black; font-weight: bold; text-decoration: underline;">/branches/1.8/apps/app_queue.c</a>
<span style="font-weight: normal;">
(Diff revision 1)
</span>
</th>
</tr>
</thead>
<tbody style="background-color: #e4d9cb; padding: 4px 8px; text-align: center;">
<tr>
<td colspan="4"><pre style="font-size: 8pt; line-height: 140%; margin: 0; ">static int calc_metric(struct call_queue *q, struct member *mem, int pos, struct queue_ent *qe, struct callattempt *tmp)</pre></td>
</tr>
</tbody>
<tbody>
<tr>
<th bgcolor="#f0f0f0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2">4173</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="k">case</span> <span class="n">QUEUE_STRATEGY_LINEAR</span>:</pre></td>
<th bgcolor="#f0f0f0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">4245</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="k">case</span> <span class="n">QUEUE_STRATEGY_LINEAR</span>:</pre></td>
</tr>
<tr>
<th bgcolor="#f0f0f0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2">4174</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="k">if</span> <span class="p">(</span><span class="n">pos</span> <span class="o"><</span> <span class="n">qe</span><span class="o">-></span><span class="n">linpos</span><span class="p">)</span> <span class="p">{</span></pre></td>
<th bgcolor="#f0f0f0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">4246</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="k">if</span> <span class="p">(</span><span class="n">pos</span> <span class="o"><</span> <span class="n">qe</span><span class="o">-></span><span class="n">linpos</span><span class="p">)</span> <span class="p">{</span></pre></td>
</tr>
<tr>
<th bgcolor="#f0f0f0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2">4175</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="n">tmp</span><span class="o">-></span><span class="n">metric</span> <span class="o">=</span> <span class="mi">1000</span> <span class="o">+</span> <span class="n">pos</span><span class="p">;</span></pre></td>
<th bgcolor="#f0f0f0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">4247</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="n">tmp</span><span class="o">-></span><span class="n">metric</span> <span class="o">=</span> <span class="mi">1000</span> <span class="o">+</span> <span class="n">pos</span><span class="p">;</span></pre></td>
</tr>
<tr>
<th bgcolor="#f0f0f0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2">4176</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="p">}</span> <span class="k">else</span> <span class="p">{</span></pre></td>
<th bgcolor="#f0f0f0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">4248</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="p">}</span> <span class="k">else</span> <span class="p">{</span></pre></td>
</tr>
<tr>
<th bgcolor="#f0f0f0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2">4177</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="k">if</span> <span class="p">(</span><span class="n">pos</span> <span class="o">></span> <span class="n">qe</span><span class="o">-></span><span class="n">linpos</span><span class="p">)</span></pre></td>
<th bgcolor="#f0f0f0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">4249</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="k">if</span> <span class="p">(</span><span class="n">pos</span> <span class="o">></span> <span class="n">qe</span><span class="o">-></span><span class="n">linpos</span><span class="p">)</span></pre></td>
</tr>
<tr>
<th bgcolor="#f0f0f0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2">4178</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="cm">/* Indicate there is another priority */</span></pre></td>
<th bgcolor="#f0f0f0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">4250</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="cm">/* Indicate there is another priority */</span></pre></td>
</tr>
<tr>
<th bgcolor="#f0f0f0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2">4179</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="n">qe</span><span class="o">-></span><span class="n">linwrapped</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span></pre></td>
<th bgcolor="#f0f0f0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">4251</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="n">qe</span><span class="o">-></span><span class="n">linwrapped</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span></pre></td>
</tr>
<tr>
<th bgcolor="#f0f0f0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2">4180</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="n">tmp</span><span class="o">-></span><span class="n">metric</span> <span class="o">=</span> <span class="n">pos</span><span class="p">;</span></pre></td>
<th bgcolor="#f0f0f0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">4252</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="n">tmp</span><span class="o">-></span><span class="n">metric</span> <span class="o">=</span> <span class="n">pos</span><span class="p">;</span></pre></td>
</tr>
</tbody>
<tbody>
<tr>
<th bgcolor="#f0f0f0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2">4181</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="p">}</span></pre></td>
<th bgcolor="#f0f0f0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">4253</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="p">}</span></pre></td>
</tr>
<tr>
<th bgcolor="#f0f0f0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2">4182</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="n">tmp</span><span class="o">-></span><span class="n">metric</span> <span class="o">+=</span> <span class="n">mem</span><span class="o">-></span><span class="n">penalty</span> <span class="o">*</span> <span class="mi">1000000</span> <span class="o">*</span> <span class="n">usepenalty</span><span class="p">;</span></pre></td>
<th bgcolor="#f0f0f0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">4254</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="n">tmp</span><span class="o">-></span><span class="n">metric</span> <span class="o">+=</span> <span class="n">mem</span><span class="o">-></span><span class="n">penalty</span> <span class="o">*</span> <span class="mi">1000000</span> <span class="o">*</span> <span class="n">usepenalty</span><span class="p">;</span></pre></td>
</tr>
<tr>
<th bgcolor="#f0f0f0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2">4183</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="k">break</span><span class="p">;</span></pre></td>
<th bgcolor="#f0f0f0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">4255</font></th>
<td bgcolor="#ffffff" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="k">break</span><span class="p">;</span></pre></td>
</tr>
</tbody>
</table>
<pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">Linear may suffer from a similar problem.</pre>
</blockquote>
</blockquote>
<pre style="margin-left: 1em; white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">I suppose I ought to use the same variable from member (rr_queuepos) here and change the name of the variable to just 'queuepos'
At least, I don't think there is any reason not to just use the same position variable.</pre>
<br />
<p>- jrose</p>
<br />
<p>On October 16th, 2012, 3:26 p.m., jrose wrote:</p>
<table bgcolor="#fefadf" width="100%" cellspacing="0" cellpadding="8" style="background-image: url('https://reviewboard.asterisk.org/media/rb/images/review_request_box_top_bg.png'); background-position: left top; background-repeat: repeat-x; border: 1px black solid;">
<tr>
<td>
<div>Review request for Asterisk Developers, Mark Michelson, rmudgett, Matt Jordan, and kmoore.</div>
<div>By jrose.</div>
<p style="color: grey;"><i>Updated Oct. 16, 2012, 3:26 p.m.</i></p>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Description </h1>
<table width="100%" bgcolor="#ffffff" cellspacing="0" cellpadding="10" style="border: 1px solid #b8b5a0">
<tr>
<td>
<pre style="margin: 0; padding: 0; white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">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.</pre>
</td>
</tr>
</table>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Testing </h1>
<table width="100%" bgcolor="#ffffff" cellspacing="0" cellpadding="10" style="border: 1px solid #b8b5a0">
<tr>
<td>
<pre style="margin: 0; padding: 0; white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">Checked that order is followed by calling into queues, tested removal and addition from rrordered and rrmemory queues, tested reloads.</pre>
</td>
</tr>
</table>
<div style="margin-top: 1.5em;">
<b style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Bugs: </b>
<a href="https://issues.asterisk.org/jira/browse/AST-989">AST-989</a>
</div>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Diffs</b> </h1>
<ul style="margin-left: 3em; padding-left: 0;">
<li>/branches/1.8/apps/app_queue.c <span style="color: grey">(375024)</span></li>
</ul>
<p><a href="https://reviewboard.asterisk.org/r/2164/diff/" style="margin-left: 3em;">View Diff</a></p>
</td>
</tr>
</table>
</div>
</body>
</html>