[asterisk-dev] [Code Review]: Use a shuffling algorithm to find unused IAX2 call numbers

[Tilghman Lesher]

> On Jan. 28, 2013, 3:50 p.m., Sean Bright wrote:
> > /trunk/channels/chan_iax2.c, lines 2806-2807
> > <https://reviewboard.asterisk.org/r/2288/diff/1/?file=33122#file33122line2806>
> >
> >     This is the only part of this code I am iffy on.  We can reduce the amount of bias, but I'm not convinced it is necessary due to the fact that as numbers are retrieved and returned to the list, the order of the numbers in the array becomes less predictable.

I do have one suggestion on this, which is that you modulo by some number less than pool->available.  That is to say, eliminate the most recently used call numbers from consideration when selecting the next one.  While you might not have an actual conflict, if you were to select a call number that was just recently used, you might confuse someone doing call tracing.


- Tilghman


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


On Feb. 14, 2013, 9:51 a.m., Sean Bright wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviewboard.asterisk.org/r/2288/
> -----------------------------------------------------------
> 
> (Updated Feb. 14, 2013, 9:51 a.m.)
> 
> 
> Review request for Asterisk Developers and rmudgett.
> 
> 
> Summary
> -------
> 
> 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.
> 
> 
> Diffs
> -----
> 
>   /trunk/channels/chan_iax2.c 381401 
> 
> Diff: https://reviewboard.asterisk.org/r/2288/diff
> 
> 
> Testing
> -------
> 
> Basic testing generating trunked and non-trunked calls between Asterisk servers.  The call number assignment behavior appears to match the ao2_container approach.
> 
> 
> Thanks,
> 
> Sean
> 
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.digium.com/pipermail/asterisk-dev/attachments/20130214/1091e068/attachment.htm>