<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/2288/">https://reviewboard.asterisk.org/r/2288/</a>
</td>
</tr>
</table>
<br />
<p>Ship it!</p>
<pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">I can't find fault in the implementation, and I'd be willing to bet large sums of money this performs better than an ao2_container.</pre>
<br />
<div>
<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/2288/diff/2/?file=33123#file33123line2798" style="color: black; font-weight: bold; text-decoration: underline;">/trunk/channels/chan_iax2.c</a>
<span style="font-weight: normal;">
(Diff revision 2)
</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 char *handle_cli_iax2_show_callno_limits(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)</pre></td>
</tr>
</tbody>
<tbody>
<tr>
<th bgcolor="#b1ebb0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2"></font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "></pre></td>
<th bgcolor="#b1ebb0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">2788</font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "><span class="cm"> * the number at x, but in our case we swap and then set the value at x to 0.</span></pre></td>
</tr>
</tbody>
</table>
<pre style="margin-left: 2em; white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">I'm curious why you set the value at x to 0. It shouldn't cause a problem but if anything after the number of available callnos is essentially invisible, why bother setting to 0?</pre>
</div>
<br />
<div>
<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/2288/diff/2/?file=33123#file33123line2803" style="color: black; font-weight: bold; text-decoration: underline;">/trunk/channels/chan_iax2.c</a>
<span style="font-weight: normal;">
(Diff revision 2)
</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 char *handle_cli_iax2_show_callno_limits(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)</pre></td>
</tr>
</tbody>
<tbody>
<tr>
<th bgcolor="#b1ebb0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2"></font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "></pre></td>
<th bgcolor="#b1ebb0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">2793</font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "><span class="cm"> * When numbers are returned to the pool, we put them just passed x and</span></pre></td>
</tr>
</tbody>
</table>
<pre style="margin-left: 2em; white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">s/passed/past/</pre>
</div>
<br />
<div>
<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/2288/diff/2/?file=33123#file33123line2806" style="color: black; font-weight: bold; text-decoration: underline;">/trunk/channels/chan_iax2.c</a>
<span style="font-weight: normal;">
(Diff revision 2)
</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 char *handle_cli_iax2_show_callno_limits(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)</pre></td>
</tr>
</tbody>
<tbody>
<tr>
<th bgcolor="#b1ebb0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2"></font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "></pre></td>
<th bgcolor="#b1ebb0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">2796</font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="cm">/* </span><span class="cs">XXX</span><span class="cm"> There is some fairly obvious modulo bias here. Do we care? */</span></pre></td>
</tr>
<tr>
<th bgcolor="#b1ebb0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2"></font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "></pre></td>
<th bgcolor="#b1ebb0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">2797</font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span class="n">choice</span> <span class="o">=</span> <span class="n">ast_random</span><span class="p">()</span> <span class="o">%</span> <span class="n">pool</span><span class="o">-></span><span class="n">available</span><span class="p">;</span></pre></td>
</tr>
</tbody>
</table>
<pre style="margin-left: 2em; white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">This shouldn't be an issue.
Modulo bias typically is an issue for older implementations of rand() as well as some non-Linux implementations of rand().
Modern day rand() uses the same random number generation as random(), so the lower bits of the random number are as random as the higher bits.
On top of that, ast_random() reads from /dev/urandom for its random numbers if possible. If it cannot, it calls random().</pre>
</div>
<br />
<p>- Mark</p>
<br />
<p>On January 29th, 2013, 8:10 a.m., Sean Bright 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 and rmudgett.</div>
<div>By Sean Bright.</div>
<p style="color: grey;"><i>Updated Jan. 29, 2013, 8:10 a.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;">While adding red-black tree containers to astobj2 in r376575, Richard pointed out the way chan_iax2 finds unused call numbers will prevent ao2_container integrity checks at runtime.
This patch removes the ao2_container and instead uses fixed sized arrays and a modified Fisher-Yates-Durstenfeld shuffle to maintain the call number list. This involves treating the lower indexes of the call number array as the available numbers and the higher indexes as the used ones. As new call numbers are requested, we choose a random call number from the lower indices of the array, and swap it with the call number that is currently at the end of the available list. The swapped value becomes the new start to the used list. Here's an example to illustrate, pretending that there are only 10 call numbers instead of 2^15:
Starting state:
Numbers: [0][1][2][3][4][5][6][7][8][9]
Available: 10
Choose a random index, pull out the call number at that index, and swap it with the value at the end of our range, and decrement our available numbers:
Chosen: 6
Numbers: [0][1][2][3][4][5][9][7][8] | [6]
Available: 9
Choose a random index, pull out the call number at that index, and swap it with the value at the end of our range, and decrement our available numbers:
Chosen: 3
Numbers: [0][1][2][8][4][5][9][7] | [3][6]
Available: 8
And so on. In the example above, we put the call number that we are extracting at the end of the list, but in reality we don't really care. The numbers after the end of the usable range are effectively "checked out" and we don't track them - we simply append the returned number to the list of available numbers and increment:
Return: 6
Numbers: [0][1][2][8][4][5][9][7][6] | [6]
Available: 9
While 3 is outstanding. In short, the numbers after the "pivot" are irrelevant and we never look at them again, we simply overwrite them with returned numbers.
I haven't done performance testing but I assume this is a bit faster than the current implementation, although the locking behavior is similar.</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;">Basic testing generating trunked and non-trunked calls between Asterisk servers. The call number assignment behavior appears to match the ao2_container approach.</pre>
</td>
</tr>
</table>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Diffs</b> </h1>
<ul style="margin-left: 3em; padding-left: 0;">
<li>/trunk/channels/chan_iax2.c <span style="color: grey">(380330)</span></li>
</ul>
<p><a href="https://reviewboard.asterisk.org/r/2288/diff/" style="margin-left: 3em;">View Diff</a></p>
</td>
</tr>
</table>
</div>
</body>
</html>