sgsn: Fix P-TMSI generator's distance of equal values
Currently sgsn_alloc_ptmsi uses rand() to get a new P-TMSI and then
sets to upper 2 MSB. Therefore there is no lower limit of the
distance between 2 identical P-TMSI.
This patch changes the implementation to discard any random value
above 2^30 and to generate a new random number in that case until a
fitting number is found (or a repetition limit is reached). This way,
all number below 2^30 within the PRNG's period are used.
Ticket: OW#1362
Sponsored-by: On-Waves ehf
diff --git a/openbsc/src/gprs/gprs_sgsn.c b/openbsc/src/gprs/gprs_sgsn.c
index f3da038..6f70664 100644
--- a/openbsc/src/gprs/gprs_sgsn.c
+++ b/openbsc/src/gprs/gprs_sgsn.c
@@ -403,10 +403,34 @@
{
struct sgsn_mm_ctx *mm;
uint32_t ptmsi;
- int max_retries = 23;
+ int max_retries = 100;
restart:
- ptmsi = rand() | 0xC0000000;
+ ptmsi = rand();
+ /* Enforce that the 2 MSB are set without loosing the distance between
+ * identical values. Since rand() has no duplicate values within a
+ * period (because the size of the state is the same like the size of
+ * the random value), this leads to a distance of period/4 when the
+ * distribution of the 2 MSB is uniform. This approach fails with a
+ * probability of (3/4)^max_retries, only 1% of the approaches will
+ * need more than 16 numbers (even distribution assumed).
+ *
+ * Alternatively, a freeze list could be used if another PRNG is used
+ * or when this approach proves to be not sufficient.
+ */
+ if (ptmsi >= 0xC0000000) {
+ if (!max_retries--)
+ goto failed;
+ goto restart;
+ }
+ ptmsi |= 0xC0000000;
+
+ if (ptmsi == GSM_RESERVED_TMSI) {
+ if (!max_retries--)
+ goto failed;
+ goto restart;
+ }
+
llist_for_each_entry(mm, &sgsn_mm_ctxts, list) {
if (mm->p_tmsi == ptmsi) {
if (!max_retries--)