1 files changed, 257 insertions, 105 deletions

diff --git a/iptables/nft-cache.c b/iptables/nft-cache.c
index 638b18bc..91d29670 100644
--- a/iptables/nft-cache.c
+++ b/iptables/nft-cache.c
@@ -24,6 +24,15 @@
 
 #include "nft.h"
 #include "nft-cache.h"
+#include "nft-chain.h"
+
+/* users may define NDEBUG */
+static void assert_nft_restart(struct nft_handle *h)
+{
+	int rc = nft_restart(h);
+
+	assert(rc >= 0);
+}
 
 static void cache_chain_list_insert(struct list_head *list, const char *name)
 {
@@ -39,7 +48,7 @@ static void cache_chain_list_insert(struct list_head *list, const char *name)
 	}
 
 	new = xtables_malloc(sizeof(*new));
-	new->name = strdup(name);
+	new->name = xtables_strdup(name);
 	list_add_tail(&new->head, pos ? &pos->head : list);
 }
 
@@ -55,7 +64,7 @@ void nft_cache_level_set(struct nft_handle *h, int level,
 		return;
 
 	if (!req->table)
-		req->table = strdup(cmd->table);
+		req->table = xtables_strdup(cmd->table);
 	else
 		assert(!strcmp(req->table, cmd->table));
 
@@ -104,52 +113,49 @@ static void mnl_genid_get(struct nft_handle *h, uint32_t *genid)
 		return;
 
 	xtables_error(RESOURCE_PROBLEM,
-		      "Could not fetch rule set generation id: %s\n", nft_strerror(errno));
+		      "Could not fetch rule set generation id: %s",
+		      nft_strerror(errno));
 }
 
 static int nftnl_table_list_cb(const struct nlmsghdr *nlh, void *data)
 {
-	struct nftnl_table *t;
-	struct nftnl_table_list *list = data;
+	struct nftnl_table *nftnl = nftnl_table_alloc();
+	const struct builtin_table *t;
+	struct nft_handle *h = data;
+	const char *name;
 
-	t = nftnl_table_alloc();
-	if (t == NULL)
-		goto err;
+	if (!nftnl)
+		return MNL_CB_OK;
+
+	if (nftnl_table_nlmsg_parse(nlh, nftnl) < 0)
+		goto out;
 
-	if (nftnl_table_nlmsg_parse(nlh, t) < 0)
+	name = nftnl_table_get_str(nftnl, NFTNL_TABLE_NAME);
+	if (!name)
 		goto out;
 
-	nftnl_table_list_add_tail(t, list);
+	t = nft_table_builtin_find(h, name);
+	if (!t)
+		goto out;
 
-	return MNL_CB_OK;
+	h->cache->table[t->type].exists = true;
 out:
-	nftnl_table_free(t);
-err:
+	nftnl_table_free(nftnl);
 	return MNL_CB_OK;
 }
 
 static int fetch_table_cache(struct nft_handle *h)
 {
-	char buf[16536];
 	struct nlmsghdr *nlh;
-	struct nftnl_table_list *list;
+	char buf[16536];
 	int i, ret;
 
-	if (h->cache->tables)
-		return 0;
-
-	list = nftnl_table_list_alloc();
-	if (list == NULL)
-		return 0;
-
-	nlh = nftnl_rule_nlmsg_build_hdr(buf, NFT_MSG_GETTABLE, h->family,
-					NLM_F_DUMP, h->seq);
+	nlh = nftnl_nlmsg_build_hdr(buf, NFT_MSG_GETTABLE, h->family,
+				    NLM_F_DUMP, h->seq);
 
-	ret = mnl_talk(h, nlh, nftnl_table_list_cb, list);
+	ret = mnl_talk(h, nlh, nftnl_table_list_cb, h);
 	if (ret < 0 && errno == EINTR)
-		assert(nft_restart(h) >= 0);
-
-	h->cache->tables = list;
+		assert_nft_restart(h);
 
 	for (i = 0; i < NFT_TABLE_MAX; i++) {
 		enum nft_table_type type = h->tables[i].type;
@@ -157,9 +163,7 @@ static int fetch_table_cache(struct nft_handle *h)
 		if (!h->tables[i].name)
 			continue;
 
-		h->cache->table[type].chains = nftnl_chain_list_alloc();
-		if (!h->cache->table[type].chains)
-			return 0;
+		h->cache->table[type].chains = nft_chain_list_alloc();
 
 		h->cache->table[type].sets = nftnl_set_list_alloc();
 		if (!h->cache->table[type].sets)
@@ -169,6 +173,152 @@ static int fetch_table_cache(struct nft_handle *h)
 	return 1;
 }
 
+static uint32_t djb_hash(const char *key)
+{
+	uint32_t i, hash = 5381;
+
+	for (i = 0; i < strlen(key); i++)
+		hash = ((hash << 5) + hash) + key[i];
+
+	return hash;
+}
+
+static struct hlist_head *chain_name_hlist(struct nft_handle *h,
+					   const struct builtin_table *t,
+					   const char *chain)
+{
+	int key = djb_hash(chain) % CHAIN_NAME_HSIZE;
+
+	return &h->cache->table[t->type].chains->names[key];
+}
+
+struct nft_chain *
+nft_chain_find(struct nft_handle *h, const char *table, const char *chain)
+{
+	const struct builtin_table *t;
+	struct hlist_node *node;
+	struct nft_chain *c;
+
+	t = nft_table_builtin_find(h, table);
+	if (!t)
+		return NULL;
+
+	hlist_for_each_entry(c, node, chain_name_hlist(h, t, chain), hnode) {
+		if (!strcmp(nftnl_chain_get_str(c->nftnl, NFTNL_CHAIN_NAME),
+			    chain))
+			return c;
+	}
+	return NULL;
+}
+
+static int
+nft_cache_add_base_chain(struct nft_handle *h, const struct builtin_table *t,
+			 struct nft_chain *nc)
+{
+	uint32_t hooknum = nftnl_chain_get_u32(nc->nftnl, NFTNL_CHAIN_HOOKNUM);
+	const char *name = nftnl_chain_get_str(nc->nftnl, NFTNL_CHAIN_NAME);
+	const char *type = nftnl_chain_get_str(nc->nftnl, NFTNL_CHAIN_TYPE);
+	uint32_t prio = nftnl_chain_get_u32(nc->nftnl, NFTNL_CHAIN_PRIO);
+	const struct builtin_chain *bc = NULL;
+	int i;
+
+	for (i = 0; i < NF_IP_NUMHOOKS && t->chains[i].name != NULL; i++) {
+		if (hooknum == t->chains[i].hook) {
+			bc = &t->chains[i];
+			break;
+		}
+	}
+
+	if (!bc ||
+	    prio != bc->prio ||
+	    strcmp(name, bc->name) ||
+	    strcmp(type, bc->type))
+		return -EINVAL;
+
+	nc->base_slot = &h->cache->table[t->type].base_chains[hooknum];
+	if (*nc->base_slot)
+		return -EEXIST;
+
+	*nc->base_slot = nc;
+	return 0;
+}
+
+int nft_cache_add_chain(struct nft_handle *h, const struct builtin_table *t,
+			struct nftnl_chain *c)
+{
+	const char *cname = nftnl_chain_get_str(c, NFTNL_CHAIN_NAME);
+	struct nft_chain *nc = nft_chain_alloc(c);
+	int ret;
+
+	if (nftnl_chain_is_set(c, NFTNL_CHAIN_HOOKNUM)) {
+		ret = nft_cache_add_base_chain(h, t, nc);
+		if (ret) {
+			h->cache->table[t->type].tainted = true;
+			nft_chain_free(nc);
+			return ret;
+		}
+	} else {
+		list_add_tail(&nc->head,
+			      &h->cache->table[t->type].chains->list);
+	}
+	hlist_add_head(&nc->hnode, chain_name_hlist(h, t, cname));
+	return 0;
+}
+
+static void __nft_chain_list_sort(struct list_head *list,
+				  int (*cmp)(struct nft_chain *a,
+					     struct nft_chain *b))
+{
+	struct nft_chain *pivot, *cur, *sav;
+	LIST_HEAD(sublist);
+
+	if (list_empty(list))
+		return;
+
+	/* grab first item as pivot (dividing) value */
+	pivot = list_entry(list->next, struct nft_chain, head);
+	list_del(&pivot->head);
+
+	/* move any smaller value into sublist */
+	list_for_each_entry_safe(cur, sav, list, head) {
+		if (cmp(pivot, cur) > 0) {
+			list_del(&cur->head);
+			list_add_tail(&cur->head, &sublist);
+		}
+	}
+	/* conquer divided */
+	__nft_chain_list_sort(&sublist, cmp);
+	__nft_chain_list_sort(list, cmp);
+
+	/* merge divided and pivot again */
+	list_add_tail(&pivot->head, &sublist);
+	list_splice(&sublist, list);
+}
+
+static int nft_chain_cmp_byname(struct nft_chain *a, struct nft_chain *b)
+{
+	const char *aname = nftnl_chain_get_str(a->nftnl, NFTNL_CHAIN_NAME);
+	const char *bname = nftnl_chain_get_str(b->nftnl, NFTNL_CHAIN_NAME);
+
+	return strcmp(aname, bname);
+}
+
+int nft_cache_sort_chains(struct nft_handle *h, const char *table)
+{
+	const struct builtin_table *t = nft_table_builtin_find(h, table);
+
+	if (!t)
+		return -1;
+
+	if (h->cache->table[t->type].sorted)
+		return 0;
+
+	__nft_chain_list_sort(&h->cache->table[t->type].chains->list,
+			      nft_chain_cmp_byname);
+	h->cache->table[t->type].sorted = true;
+	return 0;
+}
+
 struct nftnl_chain_list_cb_data {
 	struct nft_handle *h;
 	const struct builtin_table *t;
@@ -178,10 +328,9 @@ static int nftnl_chain_list_cb(const struct nlmsghdr *nlh, void *data)
 {
 	struct nftnl_chain_list_cb_data *d = data;
 	const struct builtin_table *t = d->t;
-	struct nftnl_chain_list *list;
 	struct nft_handle *h = d->h;
-	const char *tname, *cname;
 	struct nftnl_chain *c;
+	const char *tname;
 
 	c = nftnl_chain_alloc();
 	if (c == NULL)
@@ -200,14 +349,7 @@ static int nftnl_chain_list_cb(const struct nlmsghdr *nlh, void *data)
 		goto out;
 	}
 
-	list = h->cache->table[t->type].chains;
-	cname = nftnl_chain_get_str(c, NFTNL_CHAIN_NAME);
-
-	if (nftnl_chain_list_lookup_byname(list, cname))
-		goto out;
-
-	nftnl_chain_list_add_tail(c, list);
-
+	nft_cache_add_chain(h, t, c);
 	return MNL_CB_OK;
 out:
 	nftnl_chain_free(c);
@@ -283,6 +425,7 @@ static int set_fetch_elem_cb(struct nftnl_set *s, void *data)
 	char buf[MNL_SOCKET_BUFFER_SIZE];
 	struct nft_handle *h = data;
 	struct nlmsghdr *nlh;
+	int ret;
 
 	if (set_has_elements(s))
 		return 0;
@@ -291,7 +434,14 @@ static int set_fetch_elem_cb(struct nftnl_set *s, void *data)
 				    NLM_F_DUMP, h->seq);
 	nftnl_set_elems_nlmsg_build_payload(nlh, s);
 
-	return mnl_talk(h, nlh, set_elem_cb, s);
+	ret = mnl_talk(h, nlh, set_elem_cb, s);
+
+	if (!ret && h->verbose > 1) {
+		fprintf(stdout, "set ");
+		nftnl_set_fprintf(stdout, s, 0, 0);
+		fprintf(stdout, "\n");
+	}
+	return ret;
 }
 
 static int fetch_set_cache(struct nft_handle *h,
@@ -320,8 +470,8 @@ static int fetch_set_cache(struct nft_handle *h,
 		}
 	}
 
-	nlh = nftnl_set_nlmsg_build_hdr(buf, NFT_MSG_GETSET,
-					h->family, flags, h->seq);
+	nlh = nftnl_nlmsg_build_hdr(buf, NFT_MSG_GETSET,
+				    h->family, flags, h->seq);
 
 	if (s) {
 		nftnl_set_nlmsg_build_payload(nlh, s);
@@ -330,7 +480,7 @@ static int fetch_set_cache(struct nft_handle *h,
 
 	ret = mnl_talk(h, nlh, nftnl_set_list_cb, &d);
 	if (ret < 0 && errno == EINTR) {
-		assert(nft_restart(h) >= 0);
+		assert_nft_restart(h);
 		return ret;
 	}
 
@@ -363,14 +513,14 @@ static int __fetch_chain_cache(struct nft_handle *h,
 	struct nlmsghdr *nlh;
 	int ret;
 
-	nlh = nftnl_chain_nlmsg_build_hdr(buf, NFT_MSG_GETCHAIN, h->family,
-					  c ? NLM_F_ACK : NLM_F_DUMP, h->seq);
+	nlh = nftnl_nlmsg_build_hdr(buf, NFT_MSG_GETCHAIN, h->family,
+				    c ? NLM_F_ACK : NLM_F_DUMP, h->seq);
 	if (c)
 		nftnl_chain_nlmsg_build_payload(nlh, c);
 
 	ret = mnl_talk(h, nlh, nftnl_chain_list_cb, &d);
 	if (ret < 0 && errno == EINTR)
-		assert(nft_restart(h) >= 0);
+		assert_nft_restart(h);
 
 	return ret;
 }
@@ -405,9 +555,15 @@ static int fetch_chain_cache(struct nft_handle *h,
 	return ret;
 }
 
+struct rule_list_cb_data {
+	struct nftnl_chain *chain;
+	int verbose;
+};
+
 static int nftnl_rule_list_cb(const struct nlmsghdr *nlh, void *data)
 {
-	struct nftnl_chain *c = data;
+	struct rule_list_cb_data *rld = data;
+	struct nftnl_chain *c = rld->chain;
 	struct nftnl_rule *r;
 
 	r = nftnl_rule_alloc();
@@ -419,13 +575,22 @@ static int nftnl_rule_list_cb(const struct nlmsghdr *nlh, void *data)
 		return MNL_CB_OK;
 	}
 
+	if (rld->verbose > 1) {
+		nftnl_rule_fprintf(stdout, r, 0, 0);
+		fprintf(stdout, "\n");
+	}
 	nftnl_chain_rule_add_tail(r, c);
 	return MNL_CB_OK;
 }
 
-static int nft_rule_list_update(struct nftnl_chain *c, void *data)
+static int nft_rule_list_update(struct nft_chain *nc, void *data)
 {
+	struct nftnl_chain *c = nc->nftnl;
 	struct nft_handle *h = data;
+	struct rule_list_cb_data rld = {
+		.chain = c,
+		.verbose = h->verbose,
+	};
 	char buf[16536];
 	struct nlmsghdr *nlh;
 	struct nftnl_rule *rule;
@@ -443,13 +608,13 @@ static int nft_rule_list_update(struct nftnl_chain *c, void *data)
 	nftnl_rule_set_str(rule, NFTNL_RULE_CHAIN,
 			   nftnl_chain_get_str(c, NFTNL_CHAIN_NAME));
 
-	nlh = nftnl_rule_nlmsg_build_hdr(buf, NFT_MSG_GETRULE, h->family,
-					NLM_F_DUMP, h->seq);
+	nlh = nftnl_nlmsg_build_hdr(buf, NFT_MSG_GETRULE, h->family,
+				    NLM_F_DUMP, h->seq);
 	nftnl_rule_nlmsg_build_payload(nlh, rule);
 
-	ret = mnl_talk(h, nlh, nftnl_rule_list_cb, c);
+	ret = mnl_talk(h, nlh, nftnl_rule_list_cb, &rld);
 	if (ret < 0 && errno == EINTR)
-		assert(nft_restart(h) >= 0);
+		assert_nft_restart(h);
 
 	nftnl_rule_free(rule);
 
@@ -464,21 +629,16 @@ static int fetch_rule_cache(struct nft_handle *h,
 {
 	int i;
 
-	if (t) {
-		struct nftnl_chain_list *list =
-			h->cache->table[t->type].chains;
-
-		return nftnl_chain_list_foreach(list, nft_rule_list_update, h);
-	}
+	if (t)
+		return nft_chain_foreach(h, t->name, nft_rule_list_update, h);
 
 	for (i = 0; i < NFT_TABLE_MAX; i++) {
-		enum nft_table_type type = h->tables[i].type;
 
 		if (!h->tables[i].name)
 			continue;
 
-		if (nftnl_chain_list_foreach(h->cache->table[type].chains,
-					     nft_rule_list_update, h))
+		if (nft_chain_foreach(h, h->tables[i].name,
+				      nft_rule_list_update, h))
 			return -1;
 	}
 	return 0;
@@ -511,14 +671,14 @@ retry:
 	if (req->level >= NFT_CL_TABLES)
 		fetch_table_cache(h);
 	if (req->level == NFT_CL_FAKE)
-		return;
+		goto genid_check;
 	if (req->level >= NFT_CL_CHAINS)
 		fetch_chain_cache(h, t, chains);
 	if (req->level >= NFT_CL_SETS)
 		fetch_set_cache(h, t, NULL);
 	if (req->level >= NFT_CL_RULES)
 		fetch_rule_cache(h, t);
-
+genid_check:
 	mnl_genid_get(h, &genid_check);
 	if (h->nft_genid != genid_check) {
 		flush_cache(h, h->cache, NULL);
@@ -544,31 +704,25 @@ static int ____flush_rule_cache(struct nftnl_rule *r, void *data)
 	return 0;
 }
 
-static int __flush_rule_cache(struct nftnl_chain *c, void *data)
+static int __flush_rule_cache(struct nft_chain *c, void *data)
 {
-	return nftnl_rule_foreach(c, ____flush_rule_cache, NULL);
+	return nftnl_rule_foreach(c->nftnl, ____flush_rule_cache, NULL);
 }
 
 int flush_rule_cache(struct nft_handle *h, const char *table,
-		     struct nftnl_chain *c)
+		     struct nft_chain *c)
 {
-	const struct builtin_table *t;
-
 	if (c)
 		return __flush_rule_cache(c, NULL);
 
-	t = nft_table_builtin_find(h, table);
-	if (!t || !h->cache->table[t->type].chains)
-		return 0;
-
-	return nftnl_chain_list_foreach(h->cache->table[t->type].chains,
-					__flush_rule_cache, NULL);
+	nft_chain_foreach(h, table, __flush_rule_cache, NULL);
+	return 0;
 }
 
-static int __flush_chain_cache(struct nftnl_chain *c, void *data)
+static int __flush_chain_cache(struct nft_chain *c, void *data)
 {
-	nftnl_chain_list_del(c);
-	nftnl_chain_free(c);
+	nft_chain_list_del(c);
+	nft_chain_free(c);
 
 	return 0;
 }
@@ -581,6 +735,19 @@ static int __flush_set_cache(struct nftnl_set *s, void *data)
 	return 0;
 }
 
+static void flush_base_chain_cache(struct nft_chain **base_chains)
+{
+	int i;
+
+	for (i = 0; i < NF_INET_NUMHOOKS; i++) {
+		if (!base_chains[i])
+			continue;
+		hlist_del(&base_chains[i]->hnode);
+		nft_chain_free(base_chains[i]);
+		base_chains[i] = NULL;
+	}
+}
+
 static int flush_cache(struct nft_handle *h, struct nft_cache *c,
 		       const char *tablename)
 {
@@ -591,9 +758,11 @@ static int flush_cache(struct nft_handle *h, struct nft_cache *c,
 		table = nft_table_builtin_find(h, tablename);
 		if (!table)
 			return 0;
-		if (c->table[table->type].chains)
-			nftnl_chain_list_foreach(c->table[table->type].chains,
-						 __flush_chain_cache, NULL);
+
+		flush_base_chain_cache(c->table[table->type].base_chains);
+		nft_chain_foreach(h, tablename, __flush_chain_cache, NULL);
+		c->table[table->type].sorted = false;
+
 		if (c->table[table->type].sets)
 			nftnl_set_list_foreach(c->table[table->type].sets,
 					       __flush_set_cache, NULL);
@@ -604,18 +773,19 @@ static int flush_cache(struct nft_handle *h, struct nft_cache *c,
 		if (h->tables[i].name == NULL)
 			continue;
 
+		flush_base_chain_cache(c->table[i].base_chains);
 		if (c->table[i].chains) {
-			nftnl_chain_list_free(c->table[i].chains);
+			nft_chain_list_free(c->table[i].chains);
 			c->table[i].chains = NULL;
+			c->table[i].sorted = false;
 		}
+
 		if (c->table[i].sets) {
 			nftnl_set_list_free(c->table[i].sets);
 			c->table[i].sets = NULL;
 		}
-	}
-	if (c->tables) {
-		nftnl_table_list_free(c->tables);
-		c->tables = NULL;
+
+		c->table[i].exists = false;
 	}
 
 	return 1;
@@ -689,11 +859,6 @@ void nft_release_cache(struct nft_handle *h)
 	}
 }
 
-struct nftnl_table_list *nftnl_table_list_get(struct nft_handle *h)
-{
-	return h->cache->tables;
-}
-
 struct nftnl_set_list *
 nft_set_list_get(struct nft_handle *h, const char *table, const char *set)
 {
@@ -705,16 +870,3 @@ nft_set_list_get(struct nft_handle *h, const char *table, const char *set)
 
 	return h->cache->table[t->type].sets;
 }
-
-struct nftnl_chain_list *
-nft_chain_list_get(struct nft_handle *h, const char *table, const char *chain)
-{
-	const struct builtin_table *t;
-
-	t = nft_table_builtin_find(h, table);
-	if (!t)
-		return NULL;
-
-	return h->cache->table[t->type].chains;
-}
-