CDU: Support Dropping Clients when CDU DB is Full
This patch adds support for dropping the least recently seen clients in
the CDU DB. Prior to this patch, we would implicitly drop new clients when
the CDU DB was full (by refusing to add them to the CDU DB). With this
patch, we will instead drop the 10% least-recently seen clients.
To find the least-recently seen clients, we will sort O(nlog(n)) all the
clients and drop the last 10%. We do this as we're adding a new client
to the database, and so hopefully is safe enough.
PS2: Use CDU_INFO instead of pr_info_ratelimited. Also don't declare
variables for timing the sort unless we're in debug mode.
Change-Id: I99e339f089475a5945ebd8390b171bb563aa319c
diff --git a/client_data_usage/cdu_db.c b/client_data_usage/cdu_db.c
index 9427183..3f06928 100644
--- a/client_data_usage/cdu_db.c
+++ b/client_data_usage/cdu_db.c
@@ -22,6 +22,7 @@
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/jhash.h>
+#include <linux/list_sort.h>
#include <linux/etherdevice.h>
#include <net/netfilter/nf_conntrack.h>
#include <net/netfilter/nf_conntrack_core.h>
@@ -32,6 +33,7 @@
struct hlist_head cdu_db_usage_hash[USAGE_HASH_BITS] __read_mostly;
static int cdu_db_usage_count __read_mostly;
+struct list_head cdu_db_usage_list; /* Sorted list */
DEFINE_SPINLOCK(cdu_db_hash_lock);
static unsigned int jhash_rnd __read_mostly;
@@ -122,6 +124,61 @@
return NULL;
}
+static int cdu_last_activity_time_cmp(void * priv, struct list_head *a, struct list_head *b)
+{
+ struct usage_entry * obj_a = container_of(a, struct usage_entry, lnode);
+ struct usage_entry * obj_b = container_of(b, struct usage_entry, lnode);
+
+ if (obj_a->last_time < obj_b->last_time)
+ return -1;
+
+ if(obj_a->last_time > obj_b->last_time)
+ return 1;
+
+ return 0;
+
+}
+
+static struct list_head const* sort_cdu_db(void)
+{
+#ifdef DEBUG_ENABLE
+ struct timespec start;
+ struct timespec end;
+ get_monotonic_boottime(&start);
+#endif
+
+ if (list_empty(&cdu_db_usage_list))
+ return NULL;
+
+ list_sort(NULL, &cdu_db_usage_list, cdu_last_activity_time_cmp);
+#ifdef DEBUG_ENABLE
+ get_monotonic_boottime(&end);
+ CDU_DEBUG("%s took %lu ns\n", __func__, end.tv_nsec - start.tv_nsec);
+#endif
+ return &cdu_db_usage_list;
+}
+
+static void cdu_drop_clients(void)
+{
+ struct list_head const * sorted_list;
+ struct list_head * pos, *n;
+ struct usage_entry *obj;
+ unsigned int client_drop_count = CDU_USAGE_DROP_CHUNK;
+ sorted_list = sort_cdu_db();
+
+ if (!sorted_list)
+ return;
+ list_for_each_safe(pos, n, sorted_list) {
+ if (--client_drop_count == 0)
+ return;
+ obj = container_of(pos, struct usage_entry, lnode);
+ CDU_INFO("DROPPPING MAC = %pm, IP = %pI4, IP6 = %pI6, Last_Time = %lu, First_Time = %lu, Connect_Time = %lu\n",
+ obj->mac, &obj->addr.ip, &obj->addr.ip6,
+ obj->last_time, obj->first_time, obj->last_time - obj->first_time);
+ cdu_db_remove(obj);
+ }
+}
+
/* Add new entry to the hash table, based on information in ct */
static struct usage_entry *cdu_db_add_entry(const struct nf_conn *ct)
{
@@ -137,8 +194,8 @@
return NULL;
if (unlikely(cdu_db_usage_count >= CDU_USAGE_MAXENTRY)) {
- CDU_ERROR("usage limit exceeded.\n");
- return NULL;
+ CDU_ERROR("Usage limit exceeded, dropping oldest clients\n");
+ cdu_drop_clients();
}
obj = kzalloc(sizeof(struct usage_entry), GFP_ATOMIC);
@@ -157,7 +214,7 @@
obj->key = calc_hash_key_from_ct(ct);
hlist_add_head(&obj->node, &cdu_db_usage_hash[obj->key]);
-
+ list_add(&obj->lnode, &cdu_db_usage_list);
cdu_db_usage_count++;
if (obj->family == NFPROTO_IPV4)
@@ -362,6 +419,7 @@
{
cdu_db_usage_count--;
hlist_del(&obj->node);
+ list_del(&obj->lnode);
kfree(obj);
}
@@ -395,6 +453,8 @@
for (i = 0; i < USAGE_HASH_BITS; i++)
INIT_HLIST_HEAD(&cdu_db_usage_hash[i]);
+ INIT_LIST_HEAD(&cdu_db_usage_list);
+
get_random_bytes(&jhash_rnd, sizeof(jhash_rnd));
CDU_DEBUG("db initialized\n");
diff --git a/client_data_usage/cdu_db.h b/client_data_usage/cdu_db.h
index c5a50b4..45d91cb 100644
--- a/client_data_usage/cdu_db.h
+++ b/client_data_usage/cdu_db.h
@@ -27,6 +27,7 @@
#define CDU_DB_CONNTR_NOCLEAR 0
extern struct hlist_head cdu_db_usage_hash[USAGE_HASH_BITS] __read_mostly;
+extern struct list_head cdu_db_usage_list;
extern spinlock_t cdu_db_hash_lock;
int cdu_db_init(void);
diff --git a/client_data_usage/cdu_types.h b/client_data_usage/cdu_types.h
index c319fa7..d72615c 100644
--- a/client_data_usage/cdu_types.h
+++ b/client_data_usage/cdu_types.h
@@ -19,6 +19,7 @@
#pragma once
+#include <linux/list.h>
/* backwards compatible - remote code does not expect cumulative entries, but
* instead expects only new data since last cleared
* also see kernel nf_conn_counter counter: include/net/netfilter/nf_conntrack_acct.h
@@ -42,6 +43,7 @@
#define CDU_USAGE_MAXENTRY 2048
#endif
+#define CDU_USAGE_DROP_CHUNK ((int) (CDU_USAGE_MAXENTRY / 10)) /* Drop 10 percent of the least recently seen clients */
#define IP_ALEN 4
#define IP6_ALEN 16
@@ -55,6 +57,7 @@
struct usage_entry {
struct hlist_node node;
+ struct list_head lnode;
unsigned int key; /* hash table key */
union nf_inet_addr addr; /* client IP addr */