summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJozsef Kadlecsik <kadlec@blackhole.kfki.hu>2009-02-10 15:38:32 +0100
committerJozsef Kadlecsik <kadlec@blackhole.kfki.hu>2009-02-10 15:38:32 +0100
commit08b3df85d107b2ae58a7a264bcdb1480b29acf98 (patch)
tree9ba7dda8f66309203eceb6bf8910c821ba1d5315
parentaa9317d60a4cf887fe0086742412169178073806 (diff)
Fix possible duplicates in hashesh.
Bug fixed: after elements are added and deleted from a hash, an element can successfully be added in spite it's already in the hash and thus duplicates can occur. Bug spotted by Shih-Yi Chen.
-rw-r--r--kernel/ChangeLog3
-rw-r--r--kernel/ip_set_iphash.c18
-rw-r--r--kernel/ip_set_ipporthash.c18
-rw-r--r--kernel/ip_set_ipportiphash.c20
-rw-r--r--kernel/ip_set_ipportnethash.c20
-rw-r--r--kernel/ip_set_nethash.c15
6 files changed, 55 insertions, 39 deletions
diff --git a/kernel/ChangeLog b/kernel/ChangeLog
index 62ecc9a..10c2f53 100644
--- a/kernel/ChangeLog
+++ b/kernel/ChangeLog
@@ -1,4 +1,7 @@
2.4.8
+ - Bug fixed: after elements are added and deleted from a hash, an element
+ can successfully be added in spite it's already in the hash and thus
+ duplicates can occur (Shih-Yi Chen).
- Compatibility with old gcc without 'bool' added.
2.4.7
diff --git a/kernel/ip_set_iphash.c b/kernel/ip_set_iphash.c
index 976fcfc..b1bccc1 100644
--- a/kernel/ip_set_iphash.c
+++ b/kernel/ip_set_iphash.c
@@ -42,8 +42,7 @@ iphash_id(struct ip_set *set, ip_set_ip_t *hash_ip, ip_set_ip_t ip)
elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id);
if (*elem == *hash_ip)
return id;
- /* No shortcut at testing - there can be deleted
- * entries. */
+ /* No shortcut - there can be deleted entries. */
}
return UINT_MAX;
}
@@ -64,18 +63,21 @@ __iphash_add(struct ip_set_iphash *map, ip_set_ip_t *ip)
{
__u32 probe;
u_int16_t i;
- ip_set_ip_t *elem;
+ ip_set_ip_t *elem, *slot = NULL;
for (i = 0; i < map->probes; i++) {
probe = jhash_ip(map, i, *ip) % map->hashsize;
elem = HARRAY_ELEM(map->members, ip_set_ip_t *, probe);
if (*elem == *ip)
return -EEXIST;
- if (!*elem) {
- *elem = *ip;
- map->elements++;
- return 0;
- }
+ if (!(slot || *elem))
+ slot = elem;
+ /* There can be deleted entries, must check all slots */
+ }
+ if (slot) {
+ *slot = *ip;
+ map->elements++;
+ return 0;
}
/* Trigger rehashing */
return -EAGAIN;
diff --git a/kernel/ip_set_ipporthash.c b/kernel/ip_set_ipporthash.c
index 2e2bfa5..2352858 100644
--- a/kernel/ip_set_ipporthash.c
+++ b/kernel/ip_set_ipporthash.c
@@ -49,8 +49,7 @@ ipporthash_id(struct ip_set *set, ip_set_ip_t *hash_ip,
elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id);
if (*elem == *hash_ip)
return id;
- /* No shortcut at testing - there can be deleted
- * entries. */
+ /* No shortcut - there can be deleted entries. */
}
return UINT_MAX;
}
@@ -86,18 +85,21 @@ __ipporthash_add(struct ip_set_ipporthash *map, ip_set_ip_t *ip)
{
__u32 probe;
u_int16_t i;
- ip_set_ip_t *elem;
+ ip_set_ip_t *elem, *slot = NULL;
for (i = 0; i < map->probes; i++) {
probe = jhash_ip(map, i, *ip) % map->hashsize;
elem = HARRAY_ELEM(map->members, ip_set_ip_t *, probe);
if (*elem == *ip)
return -EEXIST;
- if (!*elem) {
- *elem = *ip;
- map->elements++;
- return 0;
- }
+ if (!(slot || *elem))
+ slot = elem;
+ /* There can be deleted entries, must check all slots */
+ }
+ if (slot) {
+ *slot = *ip;
+ map->elements++;
+ return 0;
}
/* Trigger rehashing */
return -EAGAIN;
diff --git a/kernel/ip_set_ipportiphash.c b/kernel/ip_set_ipportiphash.c
index 2130508..e0725d9 100644
--- a/kernel/ip_set_ipportiphash.c
+++ b/kernel/ip_set_ipportiphash.c
@@ -51,8 +51,7 @@ ipportiphash_id(struct ip_set *set, ip_set_ip_t *hash_ip,
elem = HARRAY_ELEM(map->members, struct ipportip *, id);
if (elem->ip == *hash_ip && elem->ip1 == ip1)
return id;
- /* No shortcut at testing - there can be deleted
- * entries. */
+ /* No shortcut - there can be deleted entries. */
}
return UINT_MAX;
}
@@ -90,19 +89,22 @@ __ipportip_add(struct ip_set_ipportiphash *map,
{
__u32 probe;
u_int16_t i;
- struct ipportip *elem;
+ struct ipportip *elem, *slot = NULL;
for (i = 0; i < map->probes; i++) {
probe = jhash_ip2(map, i, hash_ip, ip1) % map->hashsize;
elem = HARRAY_ELEM(map->members, struct ipportip *, probe);
if (elem->ip == hash_ip && elem->ip1 == ip1)
return -EEXIST;
- if (!(elem->ip || elem->ip1)) {
- elem->ip = hash_ip;
- elem->ip1 = ip1;
- map->elements++;
- return 0;
- }
+ if (!(slot || elem->ip || elem->ip1))
+ slot = elem;
+ /* There can be deleted entries, must check all slots */
+ }
+ if (slot) {
+ slot->ip = hash_ip;
+ slot->ip1 = ip1;
+ map->elements++;
+ return 0;
}
/* Trigger rehashing */
return -EAGAIN;
diff --git a/kernel/ip_set_ipportnethash.c b/kernel/ip_set_ipportnethash.c
index 87385a3..267370a 100644
--- a/kernel/ip_set_ipportnethash.c
+++ b/kernel/ip_set_ipportnethash.c
@@ -53,8 +53,7 @@ ipportnethash_id_cidr(struct ip_set *set, ip_set_ip_t *hash_ip,
elem = HARRAY_ELEM(map->members, struct ipportip *, id);
if (elem->ip == *hash_ip && elem->ip1 == ip1)
return id;
- /* No shortcut at testing - there can be deleted
- * entries. */
+ /* No shortcut - there can be deleted entries. */
}
return UINT_MAX;
}
@@ -137,19 +136,22 @@ __ipportnet_add(struct ip_set_ipportnethash *map,
{
__u32 probe;
u_int16_t i;
- struct ipportip *elem;
+ struct ipportip *elem, *slot = NULL;
for (i = 0; i < map->probes; i++) {
probe = jhash_ip2(map, i, hash_ip, ip1) % map->hashsize;
elem = HARRAY_ELEM(map->members, struct ipportip *, probe);
if (elem->ip == hash_ip && elem->ip1 == ip1)
return -EEXIST;
- if (!(elem->ip || elem->ip1)) {
- elem->ip = hash_ip;
- elem->ip1 = ip1;
- map->elements++;
- return 0;
- }
+ if (!(slot || elem->ip || elem->ip1))
+ slot = elem;
+ /* There can be deleted entries, must check all slots */
+ }
+ if (slot) {
+ slot->ip = hash_ip;
+ slot->ip1 = ip1;
+ map->elements++;
+ return 0;
}
/* Trigger rehashing */
return -EAGAIN;
diff --git a/kernel/ip_set_nethash.c b/kernel/ip_set_nethash.c
index d5b7a76..268fe6a 100644
--- a/kernel/ip_set_nethash.c
+++ b/kernel/ip_set_nethash.c
@@ -44,6 +44,7 @@ nethash_id_cidr(const struct ip_set_nethash *map,
elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id);
if (*elem == *hash_ip)
return id;
+ /* No shortcut - there can be deleted entries. */
}
return UINT_MAX;
}
@@ -99,17 +100,21 @@ __nethash_add(struct ip_set_nethash *map, ip_set_ip_t *ip)
{
__u32 probe;
u_int16_t i;
- ip_set_ip_t *elem;
+ ip_set_ip_t *elem, *slot = NULL;
for (i = 0; i < map->probes; i++) {
probe = jhash_ip(map, i, *ip) % map->hashsize;
elem = HARRAY_ELEM(map->members, ip_set_ip_t *, probe);
if (*elem == *ip)
return -EEXIST;
- if (!*elem) {
- *elem = *ip;
- return 0;
- }
+ if (!(slot || *elem))
+ slot = elem;
+ /* There can be deleted entries, must check all slots */
+ }
+ if (slot) {
+ *slot = *ip;
+ map->elements++;
+ return 0;
}
/* Trigger rehashing */
return -EAGAIN;