* [PATCH 1/2] ipt_hashlimit.c: use hashlist (hlist_head) instead of list_head
@ 2005-02-17 5:17 Samuel Jean
2005-02-22 11:36 ` Harald Welte
0 siblings, 1 reply; 2+ messages in thread
From: Samuel Jean @ 2005-02-17 5:17 UTC (permalink / raw)
To: Harald Welte; +Cc: netfilter-devel
[-- 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;
}
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [PATCH 1/2] ipt_hashlimit.c: use hashlist (hlist_head) instead of list_head
2005-02-17 5:17 [PATCH 1/2] ipt_hashlimit.c: use hashlist (hlist_head) instead of list_head Samuel Jean
@ 2005-02-22 11:36 ` Harald Welte
0 siblings, 0 replies; 2+ messages in thread
From: Harald Welte @ 2005-02-22 11:36 UTC (permalink / raw)
To: sjean; +Cc: netfilter-devel
[-- Attachment #1: Type: text/plain, Size: 645 bytes --]
On Thu, Feb 17, 2005 at 12:17:04AM -0500, Samuel Jean wrote:
> This patch just replaces list_head with hlist_head/node.
thanks, applied to svn and pending for kernel submission (probably only
after 2.6.11 is out, since it is not a bug fix but merely an
optimization)
--
- Harald Welte <laforge@netfilter.org> http://netfilter.org/
============================================================================
"Fragmentation is like classful addressing -- an interesting early
architectural error that shows how much experimentation was going
on while IP was being designed." -- Paul Vixie
[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2005-02-22 11:36 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2005-02-17 5:17 [PATCH 1/2] ipt_hashlimit.c: use hashlist (hlist_head) instead of list_head Samuel Jean
2005-02-22 11:36 ` Harald Welte
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.