diff options
author | Jozsef Kadlecsik <kadlec@blackhole.kfki.hu> | 2009-02-10 15:38:32 +0100 |
---|---|---|
committer | Jozsef Kadlecsik <kadlec@blackhole.kfki.hu> | 2009-02-10 15:38:32 +0100 |
commit | 08b3df85d107b2ae58a7a264bcdb1480b29acf98 (patch) | |
tree | 9ba7dda8f66309203eceb6bf8910c821ba1d5315 /kernel | |
parent | aa9317d60a4cf887fe0086742412169178073806 (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.
Diffstat (limited to 'kernel')
-rw-r--r-- | kernel/ChangeLog | 3 | ||||
-rw-r--r-- | kernel/ip_set_iphash.c | 18 | ||||
-rw-r--r-- | kernel/ip_set_ipporthash.c | 18 | ||||
-rw-r--r-- | kernel/ip_set_ipportiphash.c | 20 | ||||
-rw-r--r-- | kernel/ip_set_ipportnethash.c | 20 | ||||
-rw-r--r-- | kernel/ip_set_nethash.c | 15 |
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; |