Merge lp:~stefan.goetz-deactivatedaccount/hipl/hash_table_comparisons into lp:hipl
- hash_table_comparisons
- Merge into trunk
Status: | Merged |
---|---|
Merged at revision: | 4948 |
Proposed branch: | lp:~stefan.goetz-deactivatedaccount/hipl/hash_table_comparisons |
Merge into: | lp:hipl |
Diff against target: |
358 lines (+91/-50) 9 files modified
firewall/cache.c (+14/-7) firewall/cache_port.c (+5/-2) firewall/user_ipsec_sadb.c (+18/-24) hipd/hadb.c (+18/-5) hipd/hidb.c (+6/-1) hipd/hiprelay.c (+10/-6) hipd/netdev.c (+8/-1) hipd/oppdb.c (+6/-1) hipd/oppipdb.c (+6/-3) |
To merge this branch: | bzr merge lp:~stefan.goetz-deactivatedaccount/hipl/hash_table_comparisons |
Related bugs: |
Reviewer | Review Type | Date Requested | Status |
---|---|---|---|
Miika Komu | Approve | ||
Stefan Götz (community) | Abstain | ||
Review via email: mp+36660@code.launchpad.net |
This proposal supersedes a proposal from 2010-09-21.
Commit message
Description of the change
Fixed hash table bug(s)
HIP's hash tables base on OpenSSL's lhash which requires two call-back functions: one for hashing table entries and one for comparing them in the case of hash collisions.
The current code consistently implemented the comparison functions by comparing hashes of the entries. This is incorrect as it does not meet the semantics required of the comparison function. The effect is that when two different table entries have the same hash, the hash table implementation is not able to distinguish them. In this case it can, for example, return the wrong entry during a lookup. Since some hash tables store HIs, this problem might be security sensitive.
With this change, all comparison functions are made to compare the hash input, i.e., the table entries themselves, instead of their hashes.
Miika Komu (miika-iki) wrote : Posted in a previous version of this proposal | # |
Stefan Götz (stefan.goetz-deactivatedaccount) wrote : Posted in a previous version of this proposal | # |
> P.S. I can do some testing later this week if needed.
Yes, since I don't have a test setup, I'd appreciate it if you or someone else
could test this.
Stefan
René Hummen (rene-hummen) wrote : Posted in a previous version of this proposal | # |
The patch looks ok. However, I suggest naming the parameters of the compare more expressively as to clarify that one parameter represents the (temporary and) partially filled entry containing only look-up information, whereas the other parameter is an entry of the hash table. Furthermore, mention that the hash of both entries already match when the compare function is used. I will do these changes to doxygen right after the merge.
I agree that the code needs to be tested before merging. Please, go ahead, Miika.
Stefan Götz (stefan.goetz-deactivatedaccount) wrote : Posted in a previous version of this proposal | # |
Maybe another attempt at clarifying why these changes were necessary:
Let's assume, we have a hash table to hold elements of the type
struct entry {
struct in6_addr hit;
int foo;
char bar;
};
and the hash is calculated only over the HIT (i.e., the HIT is the hash input). We initialize the hash table with a call-back function that takes a struct entry instance and hashes the HIT and a call-back function that compares two struct entry instances for equality.
Let's assume that we put two struct entry instances into the hash table. The entries have different HITs but they hash to the same hash value. Thus, both are stored in the hash table in the same hash bucket in a linked list.
Later, when when we want to look up an entry we create a 'struct entry' instance called 'needle'. We then copy the HIT we want to look up into it and pass it to the look-up function of the hash table. The hash table implementation then uses the hash call-back to hash the HIT and to find the correct hash bucket. It then iterates over the linked list of the hash bucket and compares every hash bucket entry with 'needle' to figure out, which one is equal to 'needle'.
The existing implementation would compare the hashes of the HITs in 'needle' and the hash bucket entries. Since 'needle' has, by algorithm, the same hash as all the hash bucket entries, the first entry from the hash bucket matches right away and the lookup always returns the first entry from the hash bucket, even if there are other entries in the hash bucket. This might, of course, mean that the returned hash table entry has the same hash as 'needle' but not the same HIT.
With the changes proposed here, the compare call-backs are changed to compare the actual hash input (e.g., the HITs) instead of their hashes so that hash collisions are handled correctly.
Stefan Götz (stefan.goetz-deactivatedaccount) wrote : Posted in a previous version of this proposal | # |
> I will
> do these changes to doxygen right after the merge.
Wouldn't it make more sense to add these changes to the branch before merging it? Isn't the idea to keep working on the branch until everybody is happy with it and to merge it only then?
Stefan Götz (stefan.goetz-deactivatedaccount) wrote : Posted in a previous version of this proposal | # |
> The reason this has been working in the
> past is that the comparisons with pointers are based on rather long-lived
> structures such hadb entry.
Actually, for the hash tables, the comparison call-back functions are not based on pointers but on hashes (the comparisons *are* pointer-based for the linked-list derivation of the hash table). Therefore, I believe there are two other reasons why this has been working in the past:
1) SHA1 is an excellent hash function and the hash table uses enough hash buckets compared to the entries stored in them by HIP, so that hash collisions were, indeed, quite unlikely, if they ever occurred. Without having really checked this, I assume that hipd never actually puts enough entries into any of these hash tables to create a lot of hash collisions.
2) This is a really hard bug to catch because it's so transient that you couldn't blame anyone for simply overlooking it :-)
Miika Komu (miika-iki) wrote : Posted in a previous version of this proposal | # |
> > The reason this has been working in the
> > past is that the comparisons with pointers are based on rather long-lived
> > structures such hadb entry.
>
> Actually, for the hash tables, the comparison call-back functions are not
> based on pointers but on hashes (the comparisons *are* pointer-based for the
> linked-list derivation of the hash table). Therefore, I believe there are two
> other reasons why this has been working in the past:
You're correct, though this function seems to actually compare pointers:
firewall/
Stefan Götz (stefan.goetz-deactivatedaccount) wrote : Posted in a previous version of this proposal | # |
> You're correct, though this function seems to actually compare pointers:
>
> firewall/
What is the point of finding a pointer in a list if I already have that very
pointer at hand?
If that code does what I think it is doing, that list implementation is so
broken it just cannot do any useful work. So I hope that code does not do what I
think it is doing. Wait - I'm not sure that that would be a good thing either.
In any case, this is off-topic. I'll put it into a bug report.
Stefan Götz (stefan.goetz-deactivatedaccount) wrote : Posted in a previous version of this proposal | # |
> You're correct, though this function seems to actually compare pointers:
>
> firewall/
Oops, I was a little too bug-happy there - that code is fine as long as it is
used the way it is.<eom>
Miika Komu (miika-iki) wrote : Posted in a previous version of this proposal | # |
Tested - changes affecting hipd are kosher. Next firewall..
Miika Komu (miika-iki) wrote : Posted in a previous version of this proposal | # |
Tested also firewall (hipfw -kld). It can still accept and drop connections properly. So the changes seem to work nicely.
Stefan Götz (stefan.goetz-deactivatedaccount) wrote : Posted in a previous version of this proposal | # |
Are there any remaining obstacles to merging this branch?
René Hummen (rene-hummen) wrote : Posted in a previous version of this proposal | # |
> > I will
> > do these changes to doxygen right after the merge.
>
> Wouldn't it make more sense to add these changes to the branch before merging
> it? Isn't the idea to keep working on the branch until everybody is happy with
> it and to merge it only then?
Are you willing to fix the doxygen? Otherwise, I need write permissions on your branch.
Stefan Götz (stefan.goetz-deactivatedaccount) wrote : Posted in a previous version of this proposal | # |
> I suggest naming the parameters of the compare
> more expressively as to clarify that one parameter represents the (temporary
> and) partially filled entry containing only look-up information, whereas the
> other parameter is an entry of the hash table.
The information, which paramater is which, would unnecessarily expose an implementation detail of the hash table. I would also be worried that someone in the future might rely on this information and write strange comparison code that treats the two arguments differently.
> Furthermore, mention that the
> hash of both entries already match when the compare function is used.
Yes, I agree that that would me useful. I will make these changes, update the branch, and re-submit this MP.
Given the rich cultural copy&paste tradition in HIP, do you think that now that all comparison functions are fixed and the Doxygen comments are quite explicit about how to use them, we could do without renaming the function arguments? I don't like the idea very much for the reasons mentioned above.
René Hummen (rene-hummen) wrote : Posted in a previous version of this proposal | # |
> > I suggest naming the parameters of the compare
> > more expressively as to clarify that one parameter represents the (temporary
> > and) partially filled entry containing only look-up information, whereas the
> > other parameter is an entry of the hash table.
>
> The information, which paramater is which, would unnecessarily expose an
> implementation detail of the hash table. I would also be worried that someone
> in the future might rely on this information and write strange comparison code
> that treats the two arguments differently.
Agreed.
> > Furthermore, mention that the
> > hash of both entries already match when the compare function is used.
>
> Yes, I agree that that would me useful. I will make these changes, update the
> branch, and re-submit this MP.
Thanks.
> Given the rich cultural copy&paste tradition in HIP, do you think that now
> that all comparison functions are fixed and the Doxygen comments are quite
> explicit about how to use them, we could do without renaming the function
> arguments? I don't like the idea very much for the reasons mentioned above.
Yes.
René Hummen (rene-hummen) wrote : Posted in a previous version of this proposal | # |
> Given the rich cultural copy&paste tradition in HIP, do you think that now
> that all comparison functions are fixed [...]
I'm actually not sure about that. A grep for HIP_HASHTABLE revealed other locations where it is used:
./firewall/
./firewall/
./firewall/
-> compare function in line 254 (not modified)
./lib/core/
./lib/core/
./lib/core/
--
./modules/
./modules/
./modules/
-> both actually use the (unorthodox) linked list implementation leading to the cmp function in lib/core/
Stefan Götz (stefan.goetz-deactivatedaccount) wrote : Posted in a previous version of this proposal | # |
>> now that all comparison functions are fixed [...]
>
> I'm actually not sure about that. A grep for HIP_HASHTABLE revealed other locations where it is used:
You're right, I missed a few comparison functions :-( I'll take care of those
along with the requested documentation changes. I'll also have a look at that
list implementation and how it is used.
Stefan
Stefan Götz (stefan.goetz-deactivatedaccount) wrote : | # |
The requested changes have been made to this branch.
I also looked at how the hash table is used as a linked list, as suggested by Rene. In the instances he indicated I could not find any problems. It's certainly not the most elegant nor the most efficient list implementation (the complexity of iterating the list is > O(n)), but it works.
Miika Komu (miika-iki) : | # |
Preview Diff
1 | === modified file 'firewall/cache.c' |
2 | --- firewall/cache.c 2010-09-25 18:30:26 +0000 |
3 | +++ firewall/cache.c 2010-09-26 15:58:41 +0000 |
4 | @@ -272,16 +272,23 @@ |
5 | } |
6 | |
7 | /** |
8 | - * Compare two HITs |
9 | - * |
10 | - * @param ptr1: pointer to a HIT |
11 | - * @param ptr2: pointer to a HIT |
12 | - * |
13 | - * @return zero if hashes are identical, or one otherwise |
14 | + * Compare two cache table entries to resolve hash collisions. |
15 | + * |
16 | + * Note that when this function is called, the hashes of the two hash table entries provided as arguments are known to be equal. |
17 | + * The point of this function is to allow the hash table to determine whether the entries (or rather the part used to calculate the hash) themselves are equal or whether they are different and this is just a hash collision. |
18 | + * |
19 | + * @param ptr1: pointer to a fw_cache_hl_t |
20 | + * @param ptr2: pointer to a fw_cache_hl_t |
21 | + * |
22 | + * @return zero if the peer HITs in both table entries are identical, a non-zero value otherwise. |
23 | */ |
24 | static int hip_firewall_match_hit_peer(const void *ptr1, const void *ptr2) |
25 | { |
26 | - return hip_firewall_hash_hit_peer(ptr1) != hip_firewall_hash_hit_peer(ptr2); |
27 | + // stg: can one assume that there will always be at most one fw_cache_hl_t object per hit_peer? |
28 | + // If so, one could compare the pointers instead because if the hit_peers are the same, the pointers would be the same, and comparing the pointers is faster. |
29 | + const struct in6_addr *peer1 = &((const fw_cache_hl_t *) ptr1)->hit_peer; |
30 | + const struct in6_addr *peer2 = &((const fw_cache_hl_t *) ptr2)->hit_peer; |
31 | + return memcmp(peer1, peer2, sizeof(*peer1)); |
32 | } |
33 | |
34 | /** |
35 | |
36 | === modified file 'firewall/cache_port.c' |
37 | --- firewall/cache_port.c 2010-09-25 18:30:26 +0000 |
38 | +++ firewall/cache_port.c 2010-09-26 15:58:41 +0000 |
39 | @@ -246,14 +246,17 @@ |
40 | /** |
41 | * Compare two keys for the hashtable |
42 | * |
43 | + * Note that when this function is called, the hashes of the two hash table entries provided as arguments are known to be equal. |
44 | + * The point of this function is to allow the hash table to determine whether the entries (or rather the part used to calculate the hash) themselves are equal or whether they are different and this is just a hash collision. |
45 | + * |
46 | * @param ptr1 pointer to the first key |
47 | * @param ptr2 pointer to the second key |
48 | * |
49 | - * @return 0 if hashes identical, otherwise 1 |
50 | + * @return 0 if keys identical, otherwise != 0 |
51 | */ |
52 | static int hip_firewall_match_port_cache_key(const void *ptr1, const void *ptr2) |
53 | { |
54 | - return hip_firewall_port_hash_key(ptr1) != hip_firewall_port_hash_key(ptr2); |
55 | + return strncmp((const char *)ptr1, (const char *)ptr2, FIREWALL_PORT_CACHE_KEY_LENGTH); |
56 | } |
57 | |
58 | /** |
59 | |
60 | === modified file 'firewall/user_ipsec_sadb.c' |
61 | --- firewall/user_ipsec_sadb.c 2010-09-25 18:30:26 +0000 |
62 | +++ firewall/user_ipsec_sadb.c 2010-09-26 15:58:41 +0000 |
63 | @@ -127,6 +127,9 @@ |
64 | /** |
65 | * compares the hashes of 2 SA entries to check if they are the same |
66 | * |
67 | + * Note that when this function is called, the hashes of the two hash table entries provided as arguments are known to be equal. |
68 | + * The point of this function is to allow the hash table to determine whether the entries (or rather the part used to calculate the hash) themselves are equal or whether they are different and this is just a hash collision. |
69 | + * |
70 | * @param sa_entry1 first SA entry to be compared with |
71 | * @param sa_entry2 second SA entry to be compared with |
72 | * @return 1 if different entries, else 0 |
73 | @@ -134,22 +137,16 @@ |
74 | static int hip_sa_entries_cmp(const hip_sa_entry_t *sa_entry1, |
75 | const hip_sa_entry_t *sa_entry2) |
76 | { |
77 | - int err = 0; |
78 | - unsigned long hash1 = 0; |
79 | - unsigned long hash2 = 0; |
80 | + int result = 0; |
81 | |
82 | // values have to be present |
83 | HIP_ASSERT(sa_entry1 && sa_entry2); |
84 | |
85 | - HIP_IFEL(!(hash1 = hip_sa_entry_hash(sa_entry1)), -1, |
86 | - "failed to hash sa entry\n"); |
87 | - HIP_IFEL(!(hash2 = hip_sa_entry_hash(sa_entry2)), -1, |
88 | - "failed to hash sa entry\n"); |
89 | - |
90 | - err = (hash1 != hash2); |
91 | - |
92 | -out_err: |
93 | - return err; |
94 | + result = memcmp(&sa_entry1->inner_src_addr, &sa_entry2->inner_src_addr, sizeof(sa_entry1->inner_src_addr)); |
95 | + if (result != 0) { |
96 | + return result; |
97 | + } |
98 | + return memcmp(&sa_entry1->inner_dst_addr, &sa_entry2->inner_dst_addr, sizeof(sa_entry1->inner_dst_addr)); |
99 | } |
100 | |
101 | /** |
102 | @@ -191,6 +188,9 @@ |
103 | /** |
104 | * compares the hashes of 2 link entries to check if they are the same |
105 | * |
106 | + * Note that when this function is called, the hashes of the two hash table entries provided as arguments are known to be equal. |
107 | + * The point of this function is to allow the hash table to determine whether the entries (or rather the part used to calculate the hash) themselves are equal or whether they are different and this is just a hash collision. |
108 | + * |
109 | * @param link_entry1 first link entry to be compared with |
110 | * @param link_entry2 second link entry to be compared with |
111 | * @return 1 if different entries, else 0 |
112 | @@ -198,23 +198,17 @@ |
113 | static int hip_link_entries_cmp(const hip_link_entry_t *link_entry1, |
114 | const hip_link_entry_t *link_entry2) |
115 | { |
116 | - int err = 0; |
117 | - unsigned long hash1 = 0; |
118 | - unsigned long hash2 = 0; |
119 | + int result = 0; |
120 | |
121 | // values have to be present |
122 | HIP_ASSERT(link_entry1 != NULL && link_entry1->spi != 0); |
123 | HIP_ASSERT(link_entry2 != NULL && link_entry2->spi != 0); |
124 | |
125 | - HIP_IFEL(!(hash1 = hip_link_entry_hash(link_entry1)), -1, |
126 | - "failed to hash link entry\n"); |
127 | - HIP_IFEL(!(hash2 = hip_link_entry_hash(link_entry2)), -1, |
128 | - "failed to hash link entry\n"); |
129 | - |
130 | - err = (hash1 != hash2); |
131 | - |
132 | -out_err: |
133 | - return err; |
134 | + result = link_entry1->spi - link_entry2->spi; |
135 | + if (result != 0) { |
136 | + return result; |
137 | + } |
138 | + return memcmp(&link_entry1->dst_addr, &link_entry2->dst_addr, sizeof(link_entry1->dst_addr)); |
139 | } |
140 | |
141 | /** |
142 | |
143 | === modified file 'hipd/hadb.c' |
144 | --- hipd/hadb.c 2010-09-25 18:30:26 +0000 |
145 | +++ hipd/hadb.c 2010-09-26 15:58:41 +0000 |
146 | @@ -147,18 +147,26 @@ |
147 | * a comparison function for the hash table algorithm to distinguish |
148 | * two HAs from each other |
149 | * |
150 | + * Note that when this function is called, the hashes of the two hash table entries provided as arguments are known to be equal. |
151 | + * The point of this function is to allow the hash table to determine whether the entries (or rather the part used to calculate the hash) themselves are equal or whether they are different and this is just a hash collision. |
152 | + * |
153 | * @param ha1 a HA to compare for equality |
154 | * @param ha2 a HA to compare for equality |
155 | * @return zero if the HAs match or non-zero otherwise |
156 | */ |
157 | static int hip_ha_cmp(const hip_ha_t *ha1, const hip_ha_t *ha2) |
158 | { |
159 | - if (ha1 == NULL || &(ha1->hit_our) == NULL || &(ha1->hit_peer) == NULL || |
160 | - ha2 == NULL || &(ha2->hit_our) == NULL || &(ha2->hit_peer) == NULL) { |
161 | + int result_hit_our = 0; |
162 | + |
163 | + if (ha1 == NULL || ha2 == NULL) { |
164 | return 1; |
165 | } |
166 | |
167 | - return hip_ha_LHASH_HASH(ha1) != hip_ha_LHASH_HASH(ha2); |
168 | + result_hit_our = memcmp(&ha1->hit_our, &ha2->hit_our, sizeof(ha1->hit_our)); |
169 | + if (result_hit_our != 0) { |
170 | + return result_hit_our; |
171 | + } |
172 | + return memcmp(&ha1->hit_peer, &ha2->hit_peer, sizeof(ha1->hit_peer)); |
173 | } |
174 | |
175 | /** A callback wrapper of the prototype required by @c lh_new(). */ |
176 | @@ -182,7 +190,10 @@ |
177 | } |
178 | |
179 | /** |
180 | - * test if two peer addresses match |
181 | + * test if two peer addresses match to detect and avoid hash collisions in the peer address list. |
182 | + * |
183 | + * Note that when this function is called, the hashes of the two hash table entries provided as arguments are known to be equal. |
184 | + * The point of this function is to allow the hash table to determine whether the entries (or rather the part used to calculate the hash) themselves are equal or whether they are different and this is just a hash collision. |
185 | * |
186 | * @param ptr1 a pointer to a hip_peer_addr_list_item |
187 | * @param ptr2 a pointer to a hip_peer_addr_list_item |
188 | @@ -190,7 +201,9 @@ |
189 | */ |
190 | static int hip_match_peer_addr(const void *ptr1, const void *ptr2) |
191 | { |
192 | - return hip_hash_peer_addr(ptr1) != hip_hash_peer_addr(ptr2); |
193 | + const struct in6_addr *addr1 = &((const struct hip_peer_addr_list_item *) ptr1)->address; |
194 | + const struct in6_addr *addr2 = &((const struct hip_peer_addr_list_item *) ptr2)->address; |
195 | + return memcmp(addr1, addr2, sizeof(*addr1)); |
196 | } |
197 | |
198 | /* PRIMITIVES */ |
199 | |
200 | === modified file 'hipd/hidb.c' |
201 | --- hipd/hidb.c 2010-09-25 18:30:26 +0000 |
202 | +++ hipd/hidb.c 2010-09-26 15:58:41 +0000 |
203 | @@ -187,13 +187,18 @@ |
204 | /** |
205 | * matching function required by hashtable/linked list implementation |
206 | * |
207 | + * Note that when this function is called, the hashes of the two hash table entries provided as arguments are known to be equal. |
208 | + * The point of this function is to allow the hash table to determine whether the entries (or rather the part used to calculate the hash) themselves are equal or whether they are different and this is just a hash collision. |
209 | + * |
210 | * @param ptr1 a pointer to hip_host_id_entry |
211 | * @param ptr2 a pointer to hip_host_id_entry |
212 | * @return zero on match or non-zero on unmatch |
213 | */ |
214 | int hip_hidb_match(const void *ptr1, const void *ptr2) |
215 | { |
216 | - return hip_hidb_hash(ptr1) != hip_hidb_hash(ptr2); |
217 | + const hip_hit_t *hit1 = &((const struct hip_host_id_entry *) ptr1)->lhi.hit; |
218 | + const hip_hit_t *hit2 = &((const struct hip_host_id_entry *) ptr2)->lhi.hit; |
219 | + return memcmp(hit1, hit2, sizeof(*hit1)); |
220 | } |
221 | |
222 | /** |
223 | |
224 | === modified file 'hipd/hiprelay.c' |
225 | --- hipd/hiprelay.c 2010-09-25 18:30:26 +0000 |
226 | +++ hipd/hiprelay.c 2010-09-26 15:58:41 +0000 |
227 | @@ -314,18 +314,20 @@ |
228 | /** |
229 | * relay hash table comparison function |
230 | * |
231 | + * Note that when this function is called, the hashes of the two hash table entries provided as arguments are known to be equal. |
232 | + * The point of this function is to allow the hash table to determine whether the entries (or rather the part used to calculate the hash) themselves are equal or whether they are different and this is just a hash collision. |
233 | + * |
234 | * @param rec1 a hip_relrec_t structure |
235 | * @param rec2 a hip_relrec_t structure |
236 | * @return zero if the structures are equal or one otherwise |
237 | */ |
238 | static int hip_relht_cmp(const hip_relrec_t *rec1, const hip_relrec_t *rec2) |
239 | { |
240 | - if (rec1 == NULL || &(rec1->hit_r) == NULL || |
241 | - rec2 == NULL || &(rec2->hit_r) == NULL) { |
242 | + if (rec1 == NULL || rec2 == NULL) { |
243 | return 1; |
244 | } |
245 | |
246 | - return hip_relht_hash(rec1) != hip_relht_hash(rec2); |
247 | + return memcmp(&rec1->hit_r, &rec2->hit_r, sizeof(rec1->hit_r)); |
248 | } |
249 | |
250 | /** A callback wrapper of the prototype required by @c lh_new(). */ |
251 | @@ -585,8 +587,10 @@ |
252 | static IMPLEMENT_LHASH_HASH_FN(hip_relwl, const hip_hit_t) |
253 | |
254 | /** |
255 | - * The compare function of the @c hiprelay_wl hashtable. Compares the hash |
256 | - * values calculated from parameter @c hit1 and @c hit2. |
257 | + * The compare function of the @c hiprelay_wl hashtable. |
258 | + * |
259 | + * Note that when this function is called, the hashes of the two hash table entries provided as arguments are known to be equal. |
260 | + * The point of this function is to allow the hash table to determine whether the entries (or rather the part used to calculate the hash) themselves are equal or whether they are different and this is just a hash collision. |
261 | * |
262 | * @param hit1 a pointer to a HIT. |
263 | * @param hit2 a pointer to a HIT. |
264 | @@ -598,7 +602,7 @@ |
265 | return 1; |
266 | } |
267 | |
268 | - return hip_relwl_hash(hit1) != hip_relwl_hash(hit2); |
269 | + return memcmp(hit1, hit2, sizeof(*hit1)); |
270 | } |
271 | |
272 | /** A callback wrapper of the prototype required by @c lh_new(). */ |
273 | |
274 | === modified file 'hipd/netdev.c' |
275 | --- hipd/netdev.c 2010-09-25 18:30:26 +0000 |
276 | +++ hipd/netdev.c 2010-09-26 15:58:41 +0000 |
277 | @@ -178,22 +178,29 @@ |
278 | const struct netdev_address *na = (const struct netdev_address *) ptr; |
279 | uint8_t hash[HIP_AH_SHA_LEN]; |
280 | |
281 | + /* stg: TODO A cryptographically secure hash is unnecessarily expensive for a hash table. Something cheaper, like an XOR, would do just fine. */ |
282 | hip_build_digest(HIP_DIGEST_SHA1, &na->addr, |
283 | sizeof(struct sockaddr_storage), hash); |
284 | |
285 | + /* stg: TODO Returning only a long is all the more reason to move to a cheaper hash function. */ |
286 | return *((unsigned long *) hash); |
287 | } |
288 | |
289 | /** |
290 | * equality function for the addresses hash table |
291 | * |
292 | + * Note that when this function is called, the hashes of the two hash table entries provided as arguments are known to be equal. |
293 | + * The point of this function is to allow the hash table to determine whether the entries (or rather the part used to calculate the hash) themselves are equal or whether they are different and this is just a hash collision. |
294 | + * |
295 | * @param ptr1 a pointer to a netdev_address structure |
296 | * @param ptr2 a pointer to a netdev_address structure |
297 | * @return 0 if the given pointers match or 1 otherwise |
298 | */ |
299 | static int hip_netdev_match(const void *ptr1, const void *ptr2) |
300 | { |
301 | - return hip_netdev_hash(ptr1) != hip_netdev_hash(ptr2); |
302 | + const struct netdev_address *na1 = (const struct netdev_address *) ptr1; |
303 | + const struct netdev_address *na2 = (const struct netdev_address *) ptr2; |
304 | + return memcmp(&na1->addr, &na2->addr, sizeof(na1->addr)); |
305 | } |
306 | |
307 | /** |
308 | |
309 | === modified file 'hipd/oppdb.c' |
310 | --- hipd/oppdb.c 2010-09-25 18:30:26 +0000 |
311 | +++ hipd/oppdb.c 2010-09-26 15:58:41 +0000 |
312 | @@ -121,13 +121,18 @@ |
313 | /** |
314 | * matching function for the hashtable implementation |
315 | * |
316 | + * Note that when this function is called, the hashes of the two hash table entries provided as arguments are known to be equal. |
317 | + * The point of this function is to allow the hash table to determine whether the entries (or rather the part used to calculate the hash) themselves are equal or whether they are different and this is just a hash collision. |
318 | + * |
319 | * @param ptr1 a pointer to a hip_opp_block_t structure |
320 | * @param ptr2 a pointer to a hip_opp_block_t structure |
321 | * @return zero on match or non-zero otherwise |
322 | */ |
323 | static int hip_oppdb_match_hit(const void *ptr1, const void *ptr2) |
324 | { |
325 | - return hip_hash_hit(ptr1) != hip_hash_hit(ptr2); |
326 | + const hip_opp_block_t *b1 = (const hip_opp_block_t *) ptr1; |
327 | + const hip_opp_block_t *b2 = (const hip_opp_block_t *) ptr2; |
328 | + return memcmp(&b1->peer_phit, &b2->peer_phit, sizeof(hip_hit_t) + sizeof(struct sockaddr_in6)); |
329 | } |
330 | |
331 | /** |
332 | |
333 | === modified file 'hipd/oppipdb.c' |
334 | --- hipd/oppipdb.c 2010-09-25 18:30:26 +0000 |
335 | +++ hipd/oppipdb.c 2010-09-26 15:58:41 +0000 |
336 | @@ -67,16 +67,19 @@ |
337 | } |
338 | |
339 | /** |
340 | - * Compares two ip addresses using their hashes |
341 | + * Compares two ip addresses. |
342 | + * |
343 | + * Note that when this function is called, the hashes of the two hash table entries provided as arguments are known to be equal. |
344 | + * The point of this function is to allow the hash table to determine whether the entries (or rather the part used to calculate the hash) themselves are equal or whether they are different and this is just a hash collision. |
345 | * |
346 | * @param ptr1: pointer to the first ip address to compare |
347 | * @param ptr2: pointer to the second ip address to compare |
348 | * |
349 | - * @return 0 if the ip hashes are identical, 1 if they are different |
350 | + * @return 0 if the ips are identical, 1 if they are different |
351 | */ |
352 | static int hip_oppipdb_match_ip(const void *ptr1, const void *ptr2) |
353 | { |
354 | - return hip_oppipdb_hash_ip(ptr1) != hip_oppipdb_hash_ip(ptr2); |
355 | + return memcmp(ptr1, ptr2, sizeof(hip_oppip_t)); |
356 | } |
357 | |
358 | /** |
I'm glad that somebody did this last. The reason this has been working in the past is that the comparisons with pointers are based on rather long-lived structures such hadb entry.
While this looks ok, it needs some testing. Here's a simple way to test a subset of the functionality changed using two machines (opportunistic mode and registration):
Server:
1. hipd -k
2. hipconf add service rvs relay
3. hipconf get hi default
Client:
4. hipd -k
5. hipconf add server rvs <server-hit(see step 3)> <server-ip> 1234 # normal registration
6. hipconf rst all
7. hipconf add server rvs <server-ip> 1234 # opportunistic registration
P.S. I can do some testing later this week if needed.