[PATCH libinput 1/2] util: introduce ratelimit helpers

[Peter Hutterer]

On Tue, Nov 04, 2014 at 09:35:37AM +0100, David Herrmann wrote:
> 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>
> ---
>  src/libinput-util.c | 48 ++++++++++++++++++++++++++++++++++++++++++++++++
>  src/libinput-util.h | 19 +++++++++++++++++++
>  test/misc.c         | 37 +++++++++++++++++++++++++++++++++++++
>  3 files changed, 104 insertions(+)
> 
> diff --git a/src/libinput-util.c b/src/libinput-util.c
> index eeb9786..19594e3 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;
>  }
> +
> +/*
> + * Perform rate-limit test. Returns true if the rate-limited action is still
> + * allowed, false if it should be suppressed.
> + *
> + * 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.
> + */
> +bool ratelimit_test(struct ratelimit *r)

libinput style is: return type on a separate line

> +{
> +	struct timespec ts;
> +	uint64_t utime;
> +
> +	if (r->interval <= 0 || r->burst <= 0)
> +		return true;
> +
> +	clock_gettime(CLOCK_MONOTONIC, &ts);
> +	utime = ts.tv_sec * 1000 * 1000 + ts.tv_nsec / 1000;
> +
> +	if (r->begin <= 0 || r->begin + r->interval < utime) {
> +		/* reset counter */
> +		r->begin = utime;
> +		r->num = 1;
> +		return true;
> +	} else if (r->num < r->burst) {
> +		/* continue burst */
> +		r->num++;
> +		return true;
> +	}
> +
> +	/* rate-limit with overflow check */
> +	if (r->num + 1 > r->num)
> +		++r->num;
> +
> +	return false;
> +}
> +
> +/*
> + * Return true if the ratelimit counter just crossed the cutoff value. That is,
> + * this function returns true iff the last call to ratelimit_test() was the

s/iff/if/

> + * first call to exceed the burst value in this interval.
> + */
> +bool ratelimit_cutoff(struct ratelimit *r)

bool on separate line please

> +{
> +	return r->num == r->burst + 1;
> +}


I'm wondering: why have two separate functions here? 

how about an
enum ratelimit {
        RATELIMIT_PASS,
        RATELIMIT_THRESHOLD,
        RATELIMIT_EXCEEDED,
};

then return that from ratelimit_test and then use the return value to
decide on the rest of the handling?
so the dispatch code would be:
if ((rc = ratelimit_test(...)) != RATELIMIT_EXCEEDED)) {
     log_info("SYN_DROPPED....");
     if (rc == RATELIMIT_THRESHOLD) {
        log_info("SYN_DROPPED flood");
     }
}

or the same with a switch statement.

> diff --git a/src/libinput-util.h b/src/libinput-util.h
> index 51759e8..8ff8778 100644
> --- a/src/libinput-util.h
> +++ b/src/libinput-util.h
> @@ -25,6 +25,7 @@
>  
>  #include <unistd.h>
>  #include <math.h>
> +#include <stdbool.h>
>  #include <string.h>
>  #include <time.h>
>  
> @@ -280,4 +281,22 @@ matrix_to_farray6(const struct matrix *m, float out[6])
>  	out[5] = m->val[1][2];
>  }
>  
> +struct ratelimit {
> +	uint64_t interval;
> +	uint64_t begin;
> +	unsigned burst;
> +	unsigned num;

unsigned int please

> +} RateLimit;

well, hello. what are you doing here? are you lost? :)

> +
> +#define RATELIMIT_INIT(_interval, _burst)		\
> +	((struct ratelimit){				\
> +		.interval = (_interval),		\
> +		.begin = 0,				\
> +		.burst = (_burst),			\
> +		.num = 0,				\
> +	})

any reason you didn't make this into a function of
void ratelimit_init(struct ratelimit *rl)?
I don't see a lot of benefits having this as a macro given that it's only
called once anyway (per context).

> +
> +bool ratelimit_test(struct ratelimit *r);
> +bool ratelimit_cutoff(struct ratelimit *r);
> +
>  #endif /* LIBINPUT_UTIL_H */
> diff --git a/test/misc.c b/test/misc.c
> index 1512180..70b3e57 100644
> --- a/test/misc.c
> +++ b/test/misc.c
> @@ -508,6 +508,42 @@ START_TEST(matrix_helpers)
>  }
>  END_TEST
>  
> +START_TEST(ratelimit_helpers)
> +{
> +	/* 10 attempts every 10ms */
> +	struct ratelimit rl = RATELIMIT_INIT(10000, 10);
> +	unsigned int i, j;
> +
> +	for (j = 0; j < 100; ++j) {
> +		/* a burst of 10 attempts must succeed */
> +		for (i = 0; i < 10; ++i) {
> +			ck_assert(ratelimit_test(&rl));
> +			ck_assert(!ratelimit_cutoff(&rl));
> +		}
> +
> +		/* ..then further attempts must fail.. */
> +		ck_assert(!ratelimit_test(&rl));
> +		ck_assert(ratelimit_cutoff(&rl));

you could just drop the above two lines and merge the comments into one.

> +
> +		/* ..regardless of how often we try. */
> +		for (i = 0; i < 100; ++i) {
> +			ck_assert(!ratelimit_test(&rl));
> +			ck_assert(!ratelimit_cutoff(&rl));
> +		}
> +
> +		/* ..even after waiting 5ms */
> +		usleep(5000);

msleep(5) for consistency with the rest of the code please.

> +		for (i = 0; i < 100; ++i) {
> +			ck_assert(!ratelimit_test(&rl));
> +			ck_assert(!ratelimit_cutoff(&rl));
> +		}
> +
> +		/* but after 10ms the counter is reset */
> +		usleep(6000); /* +1ms to account for time drifts */

same here

> +	}
> +}
> +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 +555,6 @@ 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);

while you're at it, please add an empty line before the return here.

Cheers,
   Peter

>  	return litest_run(argc, argv);
>  }
> -- 
> 2.1.3
>