[PATCH v3 libinput] util: introduce ratelimit helpers

[Hans de Goede]

Hi,

On 11/06/2014 11:39 PM, Peter Hutterer wrote:
> From: David Herrmann <dh.herrmann at gmail.com>
> 
> This adds "struct ratelimit" and "ratelimit_test()". It's a very simple
> rate-limit helper modeled after Linux' lib/ratelimit.c by Dave Young.
> 
> This comes in handy to limit log-messages in possible busy loops etc..
> 
> Signed-off-by: David Herrmann <dh.herrmann at gmail.com>
> Reviewed-by: Peter Hutterer <peter.hutterer at who-t.net>
> Signed-off-by: Peter Hutterer <peter.hutterer at who-t.net>
> ---
> The test succeeded but not in valgrind which slows everything down enough
> that we didn't trigger the rate limit (valgrind is part of make check). I
> though of adding extra flags to detect when we're running valgrind but it's
> simpler to just extend the timeouts a bit.
> So instead of 10 msg per 10ms it's 10 per 100ms, the wait is 20ms and then
> another 90ms to go definitely above the 100ms.
> And only loop three times, otherwise we trigger the generic test timeout
> detection.
> 
> Changes to v3:
> - ck_assert(a == b) -> ck_assert_int_eq(a, b)
> - timeouts tweaked to avoid test failures when running through valgrind

Looks good:

Reviewed-by: Hans de Goede <hdegoede at redhat.com>

Regards,

Hans

> 
>  src/libinput-util.c | 48 ++++++++++++++++++++++++++++++++++++++++++++++++
>  src/libinput-util.h | 16 ++++++++++++++++
>  test/misc.c         | 42 ++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 106 insertions(+)
> 
> diff --git a/src/libinput-util.c b/src/libinput-util.c
> index eeb9786..34d5549 100644
> --- a/src/libinput-util.c
> +++ b/src/libinput-util.c
> @@ -65,3 +65,51 @@ list_empty(const struct list *list)
>  {
>  	return list->next == list;
>  }
> +
> +void
> +ratelimit_init(struct ratelimit *r, uint64_t ival_ms, unsigned int burst)
> +{
> +	r->interval = ival_ms;
> +	r->begin = 0;
> +	r->burst = burst;
> +	r->num = 0;
> +}
> +
> +/*
> + * Perform rate-limit test. Returns RATELIMIT_PASS if the rate-limited action
> + * is still allowed, RATELIMIT_THRESHOLD if the limit has been reached with
> + * this call, and RATELIMIT_EXCEEDED if you're beyond the threshold.
> + * It's safe to treat the return-value as boolean, if you're not interested in
> + * the exact state. It evaluates to "true" if the threshold hasn't been
> + * exceeded, yet.
> + *
> + * The ratelimit object must be initialized via ratelimit_init().
> + *
> + * Modelled after Linux' lib/ratelimit.c by Dave Young
> + * <hidave.darkstar at gmail.com>, which is licensed GPLv2.
> + */
> +enum ratelimit_state
> +ratelimit_test(struct ratelimit *r)
> +{
> +	struct timespec ts;
> +	uint64_t mtime;
> +
> +	if (r->interval <= 0 || r->burst <= 0)
> +		return RATELIMIT_PASS;
> +
> +	clock_gettime(CLOCK_MONOTONIC, &ts);
> +	mtime = ts.tv_sec * 1000 + ts.tv_nsec / 1000 / 1000;
> +
> +	if (r->begin <= 0 || r->begin + r->interval < mtime) {
> +		/* reset counter */
> +		r->begin = mtime;
> +		r->num = 1;
> +		return RATELIMIT_PASS;
> +	} else if (r->num < r->burst) {
> +		/* continue burst */
> +		return (++r->num == r->burst) ? RATELIMIT_THRESHOLD
> +					      : RATELIMIT_PASS;
> +	}
> +
> +	return RATELIMIT_EXCEEDED;
> +}
> diff --git a/src/libinput-util.h b/src/libinput-util.h
> index 51759e8..909c9db 100644
> --- a/src/libinput-util.h
> +++ b/src/libinput-util.h
> @@ -280,4 +280,20 @@ matrix_to_farray6(const struct matrix *m, float out[6])
>  	out[5] = m->val[1][2];
>  }
>  
> +enum ratelimit_state {
> +	RATELIMIT_EXCEEDED,
> +	RATELIMIT_THRESHOLD,
> +	RATELIMIT_PASS,
> +};
> +
> +struct ratelimit {
> +	uint64_t interval;
> +	uint64_t begin;
> +	unsigned int burst;
> +	unsigned int num;
> +};
> +
> +void ratelimit_init(struct ratelimit *r, uint64_t ival_ms, unsigned int burst);
> +enum ratelimit_state ratelimit_test(struct ratelimit *r);
> +
>  #endif /* LIBINPUT_UTIL_H */
> diff --git a/test/misc.c b/test/misc.c
> index 1512180..38320f3 100644
> --- a/test/misc.c
> +++ b/test/misc.c
> @@ -508,6 +508,46 @@ START_TEST(matrix_helpers)
>  }
>  END_TEST
>  
> +START_TEST(ratelimit_helpers)
> +{
> +	struct ratelimit rl;
> +	unsigned int i, j;
> +
> +	/* 10 attempts every 100ms */
> +	ratelimit_init(&rl, 100, 10);
> +
> +	for (j = 0; j < 3; ++j) {
> +		/* a burst of 9 attempts must succeed */
> +		for (i = 0; i < 9; ++i) {
> +			ck_assert_int_eq(ratelimit_test(&rl),
> +					 RATELIMIT_PASS);
> +		}
> +
> +		/* the 10th attempt reaches the threshold */
> +		ck_assert_int_eq(ratelimit_test(&rl), RATELIMIT_THRESHOLD);
> +
> +		/* ..then further attempts must fail.. */
> +		ck_assert_int_eq(ratelimit_test(&rl), RATELIMIT_EXCEEDED);
> +
> +		/* ..regardless of how often we try. */
> +		for (i = 0; i < 100; ++i) {
> +			ck_assert_int_eq(ratelimit_test(&rl),
> +					 RATELIMIT_EXCEEDED);
> +		}
> +
> +		/* ..even after waiting 20ms */
> +		msleep(20);
> +		for (i = 0; i < 100; ++i) {
> +			ck_assert_int_eq(ratelimit_test(&rl),
> +					 RATELIMIT_EXCEEDED);
> +		}
> +
> +		/* but after 100ms the counter is reset */
> +		msleep(90); /* +10ms to account for time drifts */
> +	}
> +}
> +END_TEST
> +
>  int main (int argc, char **argv) {
>  	litest_add_no_device("events:conversion", event_conversion_device_notify);
>  	litest_add_no_device("events:conversion", event_conversion_pointer);
> @@ -519,5 +559,7 @@ int main (int argc, char **argv) {
>  	litest_add_no_device("config:status string", config_status_string);
>  
>  	litest_add_no_device("misc:matrix", matrix_helpers);
> +	litest_add_no_device("misc:ratelimit", ratelimit_helpers);
> +
>  	return litest_run(argc, argv);
>  }
>