[PATCH 3/3] gtphub: nr_map: add min,max and wrap.

historical

On Fri, Nov 27, 2015 at 10:00:08AM +0100, Jacob Erlbeck wrote:
> On 26.11.2015 17:51, Neels Hofmeyr wrote:
> > On Wed, Nov 25, 2015 at 09:05:40PM +0100, Holger Freyther wrote:
> 
> >> E.g. a unit test that exhausts the entire number space should be
> feasible.
> >
> > Really? 4.294.967.295 TEI mappings?? Thats 4*sizeof(mapping) gigabytes and
> > might need special memory model options to work, and the testing
> > machine needs that many gigs of ram and will take quite a while: O(n²)...
> 
> I am fond of exhausting tests, too.

I think it would be best to artificially limit the range to 1..16 to test
exhaustion. We wouldn't have to run through 2^32 (!) mappings then.

Let me outline the two number spaces again...
There's the TEI space (32 bits of space), random per PDP context,
and the sequence number space (16 bits of space), ++ per GTP Request.

I really doubt that anyone will manage to exaust TEIs ("64 kilobytes of
RAM ought to be enough for anyone!"), but I accept the argument, and the
randomness, too. So for the TEIs, I have added code that runs through all
the tunnels and ensures that a TEI is not mapped twice. If it is, the code
tries to pick an unused TEI outside the seen min..max range of TEIs.  But
it can't yet reliably find open gaps in the middle, which would require
having a sorted list. If no TEI guaranteed to be unused is found in that
way, gtphub will abort(). (It could just drop packets instead, but maybe
abort() is better until we have a test for it.)

TEIs are so far picked sequentially, but should (TM) be picked randomly.
Again, a sorted list would solve.

Sequence numbers are different because

- they time out after 30 seconds (I picked 30 seconds off the top of my
  head, haven't really searched for a timeout in the specs yet.)

- they are specified to be sequential.

Exhausting 65535 sequence numbers in 30 seconds sounds possible; note,
this is a general limitation of GTP. If a packet is resent again and again
with the same sequence number (common strategy when no reply is received),
a given sequence mapping can linger for more than 30 seconds; but the
retries should in turn cease within another 30 seconds or so. So on the
one hand sequence nrs are more likely to wrap (space is only 2^16), on the
other hand less likely to stick around. I'm not checking sequence nr
collisions yet.

Sequence numbers are supposed to be sequential, so for those, gtphub could
remember the range of used sequence nrs as head..tail, and advance head as
used ones are discarded. If a discarded number is != head, store that in a
list; advance head, emptying the list as appropriate, once head is
released (because of the sequential nature, that list would usually stay
pretty short). If sequence numbers' tail catches up with head, the GTP
space of pending responses is exhausted, and gtphub should probably drop
any further requests to that peer until head has advanced (and ensure
its timeout is valid or something).

Any thoughts are welcome!

BTW, the same situations can arise in osmo-sgsn and openggsn. While
obsessing about this in gtphub, we should probably visit the others as
well...? ;)

~Neels

-- 
- Neels Hofmeyr <nhofmeyr at sysmocom.de>          http://www.sysmocom.de/
=======================================================================
* sysmocom - systems for mobile communications GmbH
* Alt-Moabit 93
* 10559 Berlin, Germany
* Sitz / Registered office: Berlin, HRB 134158 B
* Geschäftsführer / Managing Directors: Holger Freyther, Harald Welte
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: Digital signature
URL: <http://lists.osmocom.org/pipermail/openbsc/attachments/20151130/b7b04c32/attachment.bin>