From: Samuel Jean <sj-netfilter@cookinglinux.org>
To: Harald Welte <laforge@netfilter.org>
Cc: netfilter-devel@lists.netfilter.org
Subject: [PATCH 1/2] ipt_hashlimit.c: use hashlist (hlist_head) instead of list_head
Date: Thu, 17 Feb 2005 00:17:04 -0500 [thread overview]
Message-ID: <421428D0.8020907@cookinglinux.org> (raw)
[-- Attachment #1: Type: text/plain, Size: 6843 bytes --]
Name: use hashlist (hlist_head) instead of list_head
Status: Tested on Linux 2.6.10.
Patch against 2.6.11-rc4-bk2
Incremental to Harald's semaphore locking patch
Signed-off-by: Samuel Jean <sjean@cookinglinux.org>
A bucket is 8 bytes when using list_head's list. This is not really necessary
as we never use function requiering to access the tail in O(1).
By using hlist_head, we made a bucket down to 4 bytes. Quite a signifiant size
when one uses 2^20 buckets. (yes, there is...)
The root list doesn't need list_head too.
This patch just replaces list_head with hlist_head/node.
NOTE: I dropped listhelp.h as rusty mentioned he was going to
get rid of, someday.
Patch is inlined and attached as I'm dumb and dunno how to inline the attachement.
--- a/net/ipv4/netfilter/ipt_hashlimit.c 2005-02-14 21:21:49.000000000 -0500
+++ b/net/ipv4/netfilter/ipt_hashlimit.c 2005-02-16 23:19:19.000000000 -0500
@@ -33,11 +33,7 @@
#include <linux/sctp.h>
#include <linux/proc_fs.h>
#include <linux/seq_file.h>
-
-#define ASSERT_READ_LOCK(x)
-#define ASSERT_WRITE_LOCK(x)
-#include <linux/netfilter_ipv4/lockhelp.h>
-#include <linux/netfilter_ipv4/listhelp.h>
+#include <linux/list.h>
#include <linux/netfilter_ipv4/ip_tables.h>
#include <linux/netfilter_ipv4/ipt_hashlimit.h>
@@ -67,7 +63,7 @@ struct dsthash_dst {
struct dsthash_ent {
/* static / read-only parts in the beginning */
- struct list_head list;
+ struct hlist_node node;
struct dsthash_dst dst;
/* modified structure members in the end */
@@ -80,7 +76,7 @@ struct dsthash_ent {
};
struct ipt_hashlimit_htable {
- struct list_head list; /* global list of all htables */
+ struct hlist_node node; /* global list of all htables */
atomic_t use;
struct hashlimit_cfg cfg; /* config */
@@ -94,12 +90,12 @@ struct ipt_hashlimit_htable {
/* seq_file stuff */
struct proc_dir_entry *pde;
- struct list_head hash[0]; /* hashtable itself */
+ struct hlist_head hash[0]; /* hashtable itself */
};
static DECLARE_LOCK(hashlimit_lock); /* protects htables list */
static DECLARE_MUTEX(hlimit_mutex); /* additional checkentry protection */
-static LIST_HEAD(hashlimit_htables);
+static HLIST_HEAD(hashlimit_htables);
static kmem_cache_t *hashlimit_cachep;
static inline int dst_cmp(const struct dsthash_ent *ent, struct dsthash_dst *b)
@@ -120,9 +116,17 @@ hash_dst(const struct ipt_hashlimit_htab
static inline struct dsthash_ent *
__dsthash_find(const struct ipt_hashlimit_htable *ht, struct dsthash_dst *dst)
{
- struct dsthash_ent *ent;
+ struct dsthash_ent *ent = NULL;
+ struct hlist_node *pos;
u_int32_t hash = hash_dst(ht, dst);
- ent = LIST_FIND(&ht->hash[hash], dst_cmp, struct dsthash_ent *, dst);
+
+ if (!hlist_empty(&ht->hash[hash]))
+ hlist_for_each_entry(ent, pos, &ht->hash[hash], node) {
+ if (dst_cmp(ent, dst)) {
+ break;
+ }
+ }
+
return ent;
}
@@ -162,7 +166,7 @@ __dsthash_alloc_init(struct ipt_hashlimi
ent->dst.src_ip = dst->src_ip;
ent->dst.src_port = dst->src_port;
- list_add(&ent->list, &ht->hash[hash_dst(ht, dst)]);
+ hlist_add_head(&ent->node, &ht->hash[hash_dst(ht, dst)]);
return ent;
}
@@ -170,7 +174,7 @@ __dsthash_alloc_init(struct ipt_hashlimi
static inline void
__dsthash_free(struct ipt_hashlimit_htable *ht, struct dsthash_ent *ent)
{
- list_del(&ent->list);
+ hlist_del(&ent->node);
kmem_cache_free(hashlimit_cachep, ent);
atomic_dec(&ht->count);
}
@@ -210,7 +214,7 @@ static int htable_create(struct ipt_hash
hinfo->cfg.max = hinfo->cfg.size;
for (i = 0; i < hinfo->cfg.size; i++)
- INIT_LIST_HEAD(&hinfo->hash[i]);
+ INIT_HLIST_HEAD(&hinfo->hash[i]);
atomic_set(&hinfo->count, 0);
atomic_set(&hinfo->use, 1);
@@ -231,7 +235,7 @@ static int htable_create(struct ipt_hash
add_timer(&hinfo->timer);
LOCK_BH(&hashlimit_lock);
- list_add(&hinfo->list, &hashlimit_htables);
+ hlist_add_head(&hinfo->node, &hashlimit_htables);
UNLOCK_BH(&hashlimit_lock);
return 0;
@@ -258,8 +262,9 @@ static void htable_selective_cleanup(str
/* lock hash table and iterate over it */
spin_lock_bh(&ht->lock);
for (i = 0; i < ht->cfg.size; i++) {
- struct dsthash_ent *dh, *n;
- list_for_each_entry_safe(dh, n, &ht->hash[i], list) {
+ struct dsthash_ent *dh;
+ struct hlist_node *pos, *n;
+ hlist_for_each_entry_safe(dh, pos, n, &ht->hash[i], node) {
if ((*select)(ht, dh))
__dsthash_free(ht, dh);
}
@@ -295,9 +300,10 @@ static void htable_destroy(struct ipt_ha
static struct ipt_hashlimit_htable *htable_find_get(char *name)
{
struct ipt_hashlimit_htable *hinfo;
+ struct hlist_node *pos;
LOCK_BH(&hashlimit_lock);
- list_for_each_entry(hinfo, &hashlimit_htables, list) {
+ hlist_for_each_entry(hinfo, pos, &hashlimit_htables, node) {
if (!strcmp(name, hinfo->pde->name)) {
atomic_inc(&hinfo->use);
UNLOCK_BH(&hashlimit_lock);
@@ -313,7 +319,7 @@ static void htable_put(struct ipt_hashli
{
if (atomic_dec_and_test(&hinfo->use)) {
LOCK_BH(&hashlimit_lock);
- list_del(&hinfo->list);
+ hlist_del(&hinfo->node);
UNLOCK_BH(&hashlimit_lock);
htable_destroy(hinfo);
}
@@ -631,12 +637,17 @@ static int dl_seq_show(struct seq_file *
struct proc_dir_entry *pde = s->private;
struct ipt_hashlimit_htable *htable = pde->data;
unsigned int *bucket = (unsigned int *)v;
+ struct dsthash_ent *ent;
+ struct hlist_node *pos;
- if (LIST_FIND_W(&htable->hash[*bucket], dl_seq_real_show,
- struct dsthash_ent *, s)) {
- /* buffer was filled and unable to print that tuple */
- return 1;
- }
+ if (!hlist_empty(&htable->hash[*bucket]))
+ hlist_for_each_entry(ent, pos, &htable->hash[*bucket], node) {
+ if (dl_seq_real_show(ent, s)) {
+ /* buffer was filled and unable to print that tuple */
+ return 1;
+ }
+ }
+
return 0;
}
[-- Attachment #2: linux-2.6.11-rc4-bk2-hashlimit_hlist-based.patch --]
[-- Type: text/x-patch, Size: 5028 bytes --]
--- a/net/ipv4/netfilter/ipt_hashlimit.c 2005-02-14 21:21:49.000000000 -0500
+++ b/net/ipv4/netfilter/ipt_hashlimit.c 2005-02-16 23:19:19.000000000 -0500
@@ -33,11 +33,7 @@
#include <linux/sctp.h>
#include <linux/proc_fs.h>
#include <linux/seq_file.h>
-
-#define ASSERT_READ_LOCK(x)
-#define ASSERT_WRITE_LOCK(x)
-#include <linux/netfilter_ipv4/lockhelp.h>
-#include <linux/netfilter_ipv4/listhelp.h>
+#include <linux/list.h>
#include <linux/netfilter_ipv4/ip_tables.h>
#include <linux/netfilter_ipv4/ipt_hashlimit.h>
@@ -67,7 +63,7 @@ struct dsthash_dst {
struct dsthash_ent {
/* static / read-only parts in the beginning */
- struct list_head list;
+ struct hlist_node node;
struct dsthash_dst dst;
/* modified structure members in the end */
@@ -80,7 +76,7 @@ struct dsthash_ent {
};
struct ipt_hashlimit_htable {
- struct list_head list; /* global list of all htables */
+ struct hlist_node node; /* global list of all htables */
atomic_t use;
struct hashlimit_cfg cfg; /* config */
@@ -94,12 +90,12 @@ struct ipt_hashlimit_htable {
/* seq_file stuff */
struct proc_dir_entry *pde;
- struct list_head hash[0]; /* hashtable itself */
+ struct hlist_head hash[0]; /* hashtable itself */
};
static DECLARE_LOCK(hashlimit_lock); /* protects htables list */
static DECLARE_MUTEX(hlimit_mutex); /* additional checkentry protection */
-static LIST_HEAD(hashlimit_htables);
+static HLIST_HEAD(hashlimit_htables);
static kmem_cache_t *hashlimit_cachep;
static inline int dst_cmp(const struct dsthash_ent *ent, struct dsthash_dst *b)
@@ -120,9 +116,17 @@ hash_dst(const struct ipt_hashlimit_htab
static inline struct dsthash_ent *
__dsthash_find(const struct ipt_hashlimit_htable *ht, struct dsthash_dst *dst)
{
- struct dsthash_ent *ent;
+ struct dsthash_ent *ent = NULL;
+ struct hlist_node *pos;
u_int32_t hash = hash_dst(ht, dst);
- ent = LIST_FIND(&ht->hash[hash], dst_cmp, struct dsthash_ent *, dst);
+
+ if (!hlist_empty(&ht->hash[hash]))
+ hlist_for_each_entry(ent, pos, &ht->hash[hash], node) {
+ if (dst_cmp(ent, dst)) {
+ break;
+ }
+ }
+
return ent;
}
@@ -162,7 +166,7 @@ __dsthash_alloc_init(struct ipt_hashlimi
ent->dst.src_ip = dst->src_ip;
ent->dst.src_port = dst->src_port;
- list_add(&ent->list, &ht->hash[hash_dst(ht, dst)]);
+ hlist_add_head(&ent->node, &ht->hash[hash_dst(ht, dst)]);
return ent;
}
@@ -170,7 +174,7 @@ __dsthash_alloc_init(struct ipt_hashlimi
static inline void
__dsthash_free(struct ipt_hashlimit_htable *ht, struct dsthash_ent *ent)
{
- list_del(&ent->list);
+ hlist_del(&ent->node);
kmem_cache_free(hashlimit_cachep, ent);
atomic_dec(&ht->count);
}
@@ -210,7 +214,7 @@ static int htable_create(struct ipt_hash
hinfo->cfg.max = hinfo->cfg.size;
for (i = 0; i < hinfo->cfg.size; i++)
- INIT_LIST_HEAD(&hinfo->hash[i]);
+ INIT_HLIST_HEAD(&hinfo->hash[i]);
atomic_set(&hinfo->count, 0);
atomic_set(&hinfo->use, 1);
@@ -231,7 +235,7 @@ static int htable_create(struct ipt_hash
add_timer(&hinfo->timer);
LOCK_BH(&hashlimit_lock);
- list_add(&hinfo->list, &hashlimit_htables);
+ hlist_add_head(&hinfo->node, &hashlimit_htables);
UNLOCK_BH(&hashlimit_lock);
return 0;
@@ -258,8 +262,9 @@ static void htable_selective_cleanup(str
/* lock hash table and iterate over it */
spin_lock_bh(&ht->lock);
for (i = 0; i < ht->cfg.size; i++) {
- struct dsthash_ent *dh, *n;
- list_for_each_entry_safe(dh, n, &ht->hash[i], list) {
+ struct dsthash_ent *dh;
+ struct hlist_node *pos, *n;
+ hlist_for_each_entry_safe(dh, pos, n, &ht->hash[i], node) {
if ((*select)(ht, dh))
__dsthash_free(ht, dh);
}
@@ -295,9 +300,10 @@ static void htable_destroy(struct ipt_ha
static struct ipt_hashlimit_htable *htable_find_get(char *name)
{
struct ipt_hashlimit_htable *hinfo;
+ struct hlist_node *pos;
LOCK_BH(&hashlimit_lock);
- list_for_each_entry(hinfo, &hashlimit_htables, list) {
+ hlist_for_each_entry(hinfo, pos, &hashlimit_htables, node) {
if (!strcmp(name, hinfo->pde->name)) {
atomic_inc(&hinfo->use);
UNLOCK_BH(&hashlimit_lock);
@@ -313,7 +319,7 @@ static void htable_put(struct ipt_hashli
{
if (atomic_dec_and_test(&hinfo->use)) {
LOCK_BH(&hashlimit_lock);
- list_del(&hinfo->list);
+ hlist_del(&hinfo->node);
UNLOCK_BH(&hashlimit_lock);
htable_destroy(hinfo);
}
@@ -631,12 +637,17 @@ static int dl_seq_show(struct seq_file *
struct proc_dir_entry *pde = s->private;
struct ipt_hashlimit_htable *htable = pde->data;
unsigned int *bucket = (unsigned int *)v;
+ struct dsthash_ent *ent;
+ struct hlist_node *pos;
- if (LIST_FIND_W(&htable->hash[*bucket], dl_seq_real_show,
- struct dsthash_ent *, s)) {
- /* buffer was filled and unable to print that tuple */
- return 1;
- }
+ if (!hlist_empty(&htable->hash[*bucket]))
+ hlist_for_each_entry(ent, pos, &htable->hash[*bucket], node) {
+ if (dl_seq_real_show(ent, s)) {
+ /* buffer was filled and unable to print that tuple */
+ return 1;
+ }
+ }
+
return 0;
}
next reply other threads:[~2005-02-17 5:17 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-02-17 5:17 Samuel Jean [this message]
2005-02-22 11:36 ` [PATCH 1/2] ipt_hashlimit.c: use hashlist (hlist_head) instead of list_head Harald Welte
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=421428D0.8020907@cookinglinux.org \
--to=sj-netfilter@cookinglinux.org \
--cc=laforge@netfilter.org \
--cc=netfilter-devel@lists.netfilter.org \
--cc=sjean@cookinglinux.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.