summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJacob Erlbeck <jerlbeck@sysmocom.de>2015-01-15 18:51:31 +0100
committerJacob Erlbeck <jerlbeck@sysmocom.de>2015-01-19 08:30:01 +0100
commita1f7a53a95483560f91fe601ed837581e25ebda1 (patch)
tree8ef08da366039ba63114944da13b195272557fb8
parent244aeadb616702b34d479be3872a5e1bf71120b0 (diff)
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
-rw-r--r--openbsc/src/gprs/gprs_sgsn.c28
1 files changed, 26 insertions, 2 deletions
diff --git a/openbsc/src/gprs/gprs_sgsn.c b/openbsc/src/gprs/gprs_sgsn.c
index f3da0387a..6f706642d 100644
--- a/openbsc/src/gprs/gprs_sgsn.c
+++ b/openbsc/src/gprs/gprs_sgsn.c
@@ -403,10 +403,34 @@ uint32_t sgsn_alloc_ptmsi(void)
{
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--)