Hash lookups during startup

[Andrew Matheson]

Greetings,

I don't really know what the format for this list is or if there is a FAQ on
common questions.  If there is, please let me know.  Also, I saw that about
6 months ago Ted Lemon made mention of some coding standards in reference to
the execute() patch.  Are there any formalized guidelines?  Or is the code
the guide? :) 

Now onto the actual topic.  When working with the DHCP server and a large
number of /21 subnets all using dynamic ranges, the server is taking close
to a minute to start.  Compare this to the same number of subnets using
/24's and the server starts in about 3 seconds.  Taking a look at the code
and running it through Quantify I've traced the issue to the
lease_hash_lookup() function (which resolves to
omapip/hash.c:hash_lookup()).  The reason for the slow down seems to be
caused by long chaining in the hash buckets.  As each IP address in the
range is checked for existence before being added, the hash_lookup function
must iterate through each element of the chain comparing the IP against the
chain contents.  My first thought was to increase the hash size (which had
already been set to 9973) and so I set it to 70001.  This had no impact
other than increasing the start up time perhaps due to the extra time
required to allocate more memory.  Thus, I stepped into the debugger and
traced the hash_lookup() function.  What I found was that the hash function
was not evenly distributing the IPs across the hash table.  Because the IPs
were all quite similar in each range, the IPs were being hashed into the
same group of 253 buckets and thus chaining.  As there are 2048 possible
addresses in a /21, this meant that there were at times 8 IPs being hashed
into each bucket from the same range.  Add in the fact that the ranges all
fall in the 10.0.0.0/8 network and there are overlapping hits on the hash
table.  An example that I've put together while stepping through the code
shows what is happening.  The first range (10.30.34.1 --> 10.30.35.253) is
placed into hash buckets 269 through 522 (253 buckets).  The second range
(10.30.56.1 --> 10.30.63.253) is placed into hash buckets 313 through 579

	269	10.30.34.1
	270	10.30.35.0   10.30.34.2
	271	10.30.35.1   10.30.34.3
	272	10.30.35.2   10.30.34.4
	.
	.
	.
	312	10.30.35.42  10.30.34.44
	313	10.30.56.1   10.30.35.43  10.30.34.45
	314	10.30.57.0   10.30.56.2   10.30.35.44  10.30.34.46
	315	10.30.57.1   10.30.56.3   10.30.35.45  10.30.34.47
	316	10.30.58.0   10.30.57.2   10.30.56.4   10.30.35.46
10.36.34.48
	.
	.
	.
	330	10.30.63.4   10.30.62.6   10.30.61.8   10.30.60.10
10.30.59.12  10.30.58.14  10.30.57.16  10.30.56.18  10.30.35.60  10.30.34.62
	.
	.
	.
	400	10.30.63.74  10.30.62.76  10.30.61.78  10.30.60.80
10.30.59.82  10.30.58.84  10.30.57.86  10.30.56.88  10.30.35.130
10.30.34.132
	.
	.
	.
	500	10.30.63.174 10.30.62.176 10.30.61.178 10.30.60.180
10.30.59.182 10.30.58.184 10.30.57.186 10.30.56.188 10.30.35.230
10.30.34.232
	.
	.
	.
	520	10.30.63.194 10.30.62.196 10.30.61.198 10.30.60.200
10.30.59.202 10.30.58.204 10.30.57.206 10.30.56.208 10.30.35.250
10.30.34.252
	521	10.30.63.195 10.30.62.197 10.30.61.199 10.30.60.201
10.30.59.203 10.30.58.205 10.30.57.207 10.30.56.209 10.30.35.251
10.30.34.253
	522	10.30.63.196 10.30.62.198 10.30.61.200 10.30.60.202
10.30.59.204 10.30.58.206 10.30.57.208 10.30.56.210 10.30.35.252
	523	10.30.63.197 10.30.62.199 10.30.61.201 10.30.60.203
10.30.59.205 10.30.58.207 10.30.57.209 10.30.56.211 10.30.35.253
	524	10.30.63.198 10.30.62.200 10.30.61.202 10.30.60.204
10.30.59.206 10.30.58.208 10.30.57.210 10.30.56.212
	.
	.
	.
	575   10.30.63.249 10.30.62.251 10.30.61.253
	576   10.30.63.250 10.30.62.252
	577   10.30.63.251 10.30.62.253
	578   10.30.63.252
	579	10.30.63.253

As you can see, in this sample case, the chain has grown to 10 items.  This
isn't bad in and of itself when accessed infrequently.  However at startup
these chains are processed for each IP address that is added resulting in an
even worse situation because the chain is processed completely as it is not
sorted.  Quantify tells me that on processing a configuration file with 8700
lines, 87 '/21' ranges and 90 '/23' ranges all ranges within the 10.0.0.0/8
network it spends 38% of it's time in hash_lookup() and 35% of it's time in
memcmp().  

What I'm looking for is some advice on how best to tackle this issue.  I can
see two possible options: find a different hashing algorithm that will
distribute the above data better, or use insertion sort on the bucket chain.
The problem with finding a different algorithm from my understanding is
finding one that will work well for many types of data (as is the
requirement for this case).  The issue with the insertion sort is the scope
of the changes required and how that might impact the rest of the code.  The
best solution from my perspective is an insertion sort on the chain.

Any comments or suggestions?  Thanks in advance!

Cheers,
Andrew C

--
Andrew Cornford-Matheson
Product Release Manager
Core Networks, Inc.