Skip to content

Instantly share code, notes, and snippets.

@bgrewell

bgrewell/netem_crandom_insights.md

Last active January 30, 2020 18:19
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bgrewell/27839f82b8707809ec9aecf94edc5f95 to your computer and use it in GitHub Desktop.
Save bgrewell/27839f82b8707809ec9aecf94edc5f95 to your computer and use it in GitHub Desktop.
Download ZIP
Results from some tracing into the calls to get_crandom in sch_netem.c
Raw
netem_crandom_insights.md

Insights

The function below is responsible for returning the delay value that is used by the qdisc. If no distribution is specified it is uniform, this is why I didn't see a uniform.dist file in /usr/lib/tc where the other distribution tables are.

mu == latency

sigma == jitter

You can see from the code below that if you don't specify a distribution then it uses the uniform one by default. return ((rnd % (2 * sigma)) + mu) - sigma; in this case rnd is our correlated random number from get_crandom so we take the jitter value sigma and multiply it by 2, then we modulo rnd by this value and add mu our base latency and then subtract sigma to center the jitter

/* tabledist - return a pseudo-randomly distributed value with mean mu and
 * std deviation sigma.  Uses table lookup to approximate the desired
 * distribution, and a uniformly-distributed pseudo-random source.
 */
static s64 tabledist(s64 mu, s32 sigma,
		     struct crndstate *state,
		     const struct disttable *dist)
{
	s64 x;
	long t;
	u32 rnd;

	if (sigma == 0)
		return mu;

	rnd = get_crandom(state);

	/* default uniform distribution */
	if (dist == NULL)
		return ((rnd % (2 * sigma)) + mu) - sigma;

	t = dist->table[rnd % dist->size];
	x = (sigma % NETEM_DIST_SCALE) * t;
	if (x >= 0)
		x += NETEM_DIST_SCALE/2;
	else
		x -= NETEM_DIST_SCALE/2;

	return  x / NETEM_DIST_SCALE + (sigma / NETEM_DIST_SCALE) * t + mu;
}

Testing Results

Tests were run with correlation set to 1%, 25%, 50%, 75%, 99%, 100%. Each time 4 pings were sent to trigger calls to the function.

1% Results

=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 28f5c29
last: 3bcfa65a
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 28f5c29
last: 48c2c949
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 28f5c29
last: 3745499e
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 28f5c29
last: 13e3b871
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 28f5c29
last: 76ac697
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 28f5c29
last: e83435f7
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 28f5c29
last: f78f366c
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 28f5c29
last: 5529c9b3
=================================================

25% Results

=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 40000000
last: d6d9ba4f
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 40000000
last: f0dcb307
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 40000000
last: dbc4e409
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 40000000
last: edbd0fca
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 40000000
last: 3d2c94ff
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 40000000
last: 14166356
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 40000000
last: 210522f6
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 40000000
last: 5e7d59e1
=================================================

50% Results

=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 80000000
last: c2035747
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 80000000
last: b2ea4fe4
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 80000000
last: a11e00ed
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 80000000
last: cfde1190
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 80000000
last: 9acfc11d
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 80000000
last: 95f5eb55
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 80000000
last: 4fe4aa66
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: 80000000
last: 8b290eb5
=================================================

75% Results

=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: bfffffff
last: 928fe7ef
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: bfffffff
last: 942b9d60
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: bfffffff
last: 73ea02a1
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: bfffffff
last: 8b064505
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: bfffffff
last: 9377e451
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: bfffffff
last: 975bb960
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: bfffffff
last: 78c0ef08
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: bfffffff
last: 5d262fa3
=================================================

99% Results

=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: fd70a3d6
last: 91b511ae
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: fd70a3d6
last: 90691e05
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: fd70a3d6
last: 9099f5f3
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: fd70a3d6
last: 8f736b78
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: fd70a3d6
last: 8e5da66e
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: fd70a3d6
last: 8e1e3d54
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: fd70a3d6
last: 8dfd6c8d
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: fd70a3d6
last: 8d4e075b
=================================================

100% Result

=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: init_crandom
$$vars: rho=? state=?
$$locals: 
$$parms: rho=? state=?
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: ffffffff
last: 60c38809
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: ffffffff
last: 60c38809
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: ffffffff
last: 60c38809
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: ffffffff
last: 60c38809
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: ffffffff
last: 60c38809
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: ffffffff
last: 60c38809
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: ffffffff
last: 60c38809
=================================================
=================================================
function: get_crandom
$$vars: state=0xffff8a8ef4c0ddec value=? rho=? answer=?
$$locals: value=? rho=? answer=?
$$parms: state=0xffff8a8ef4c0ddec
rho: ffffffff
last: 60c38809
=================================================
@bgrewell
Copy link
Author

bgrewell commented Jan 30, 2020 •
edited

function

static u32 get_crandom(struct crndstate *state)
{
	u64 value, rho;
	unsigned long answer;

	if (!state || state->rho == 0)	/* no correlation */
		return prandom_u32();

	value = prandom_u32();
	rho = (u64)state->rho + 1;
	answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32;
	state->last = answer;
	return answer;
}

Each point of correlation % == .00000001 increases rho by 1

Testing shows that although tc doesn't reflect values for correlation past 5 decimal places it appears that is supports much more precision.

@bgrewell
Copy link
Author

bgrewell commented Jan 30, 2020 •
edited

Reversing Formula


# Finding RHO is easy, it's just state->rho + 1
rho = ccccccd + 1

# Finding value can be done by solving for x in this equation
2356625973 = ( x * (( 1 << 32 ) - cccccce ) + 2233226875 * cccccce ) >> 32

x = 2363120662.406623058

@bgrewell
Copy link
Author

bgrewell commented Jan 30, 2020 •
edited

Additional testing was able to extract return values.

=================================================
function: prandom_u32
return: 1519699679
=================================================
=================================================
function: prandom_u32
return: 614803808
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 1353071588
return: 799370753
=================================================
=================================================
function: prandom_u32
return: 185586257
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 799370753
return: 339032381
=================================================
=================================================
function: prandom_u32
return: 4178815032
=================================================
=================================================
function: prandom_u32
return: 3584615792
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 339032381
return: 2773219938
=================================================
=================================================
function: prandom_u32
return: 1775298792
=================================================
=================================================
function: prandom_u32
return: 3538213432
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 2773219938
return: 3346965058
=================================================
=================================================
function: prandom_u32
return: 1032120861
=================================================
=================================================
function: prandom_u32
return: 855126587
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 3346965058
return: 1478086205
=================================================
=================================================
function: prandom_u32
return: 915287973
=================================================
=================================================
function: prandom_u32
return: 4001284251
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 1478086205
return: 3370484738
=================================================
=================================================
function: prandom_u32
return: 609707715
=================================================
=================================================
function: prandom_u32
return: 4191893811
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 3370484738
return: 3986541542
=================================================
=================================================
function: prandom_u32
return: 3391509117
=================================================
=================================================
function: prandom_u32
return: 2085583456
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 3986541542
return: 2560822977
=================================================
=================================================
function: prandom_u32
return: 3155005554
=================================================
=================================================
function: prandom_u32
return: 948526077
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 2560822977
return: 1351600302
=================================================
=================================================
function: prandom_u32
return: 3300652375
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 1351600302
return: 2813389356
=================================================
=================================================
function: prandom_u32
return: 3787879661
=================================================
=================================================
function: prandom_u32
return: 1434716064
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 2813389356
return: 1779384387
=================================================
=================================================
function: prandom_u32
return: 3851910044
=================================================
=================================================
function: prandom_u32
return: 2271244660
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 1779384387
return: 2148279591
=================================================
=================================================
function: prandom_u32
return: 2386965061
=================================================
=================================================
function: prandom_u32
return: 569851503
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 2148279591
return: 964458525
=================================================
=================================================
function: prandom_u32
return: 953595998
=================================================
=================================================
function: prandom_u32
return: 645229328
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 964458525
return: 725036627
=================================================
=================================================
function: prandom_u32
return: 1848264779
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 725036627
return: 1567457740
=================================================
=================================================
function: prandom_u32
return: 231998787
=================================================
=================================================
function: prandom_u32
return: 2773490191
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 1567457740
return: 2471982077
=================================================
=================================================
function: prandom_u32
return: 3619312910
=================================================
=================================================
function: prandom_u32
return: 241039705
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 2471982077
return: 798775298
=================================================
=================================================
function: prandom_u32
return: 2756137880
=================================================
=================================================
function: prandom_u32
return: 1406199565
=================================================
=================================================
function: get_crandom
state->rho: 1073741824
state->last: 798775298
return: 1254343498
=================================================

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment