Bug Summary

File:libs/apr/tables/apr_hash.c
Location:line 463, column 34
Description:Dereference of null pointer

Annotated Source Code

1/* Licensed to the Apache Software Foundation (ASF) under one or more
2 * contributor license agreements. See the NOTICE file distributed with
3 * this work for additional information regarding copyright ownership.
4 * The ASF licenses this file to You under the Apache License, Version 2.0
5 * (the "License"); you may not use this file except in compliance with
6 * the License. You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include "apr_private.h"
18
19#include "apr_general.h"
20#include "apr_pools.h"
21
22#include "apr_hash.h"
23
24#if APR_HAVE_STDLIB_H1
25#include <stdlib.h>
26#endif
27#if APR_HAVE_STRING_H1
28#include <string.h>
29#endif
30
31#if APR_POOL_DEBUG0 && APR_HAVE_STDIO_H1
32#include <stdio.h>
33#endif
34
35/*
36 * The internal form of a hash table.
37 *
38 * The table is an array indexed by the hash of the key; collisions
39 * are resolved by hanging a linked list of hash entries off each
40 * element of the array. Although this is a really simple design it
41 * isn't too bad given that pools have a low allocation overhead.
42 */
43
44typedef struct apr_hash_entry_t apr_hash_entry_t;
45
46struct apr_hash_entry_t {
47 apr_hash_entry_t *next;
48 unsigned int hash;
49 const void *key;
50 apr_ssize_t klen;
51 const void *val;
52};
53
54/*
55 * Data structure for iterating through a hash table.
56 *
57 * We keep a pointer to the next hash entry here to allow the current
58 * hash entry to be freed or otherwise mangled between calls to
59 * apr_hash_next().
60 */
61struct apr_hash_index_t {
62 apr_hash_t *ht;
63 apr_hash_entry_t *this, *next;
64 unsigned int index;
65};
66
67/*
68 * The size of the array is always a power of two. We use the maximum
69 * index rather than the size so that we can use bitwise-AND for
70 * modular arithmetic.
71 * The count of hash entries may be greater depending on the chosen
72 * collision rate.
73 */
74struct apr_hash_t {
75 apr_pool_t *pool;
76 apr_hash_entry_t **array;
77 apr_hash_index_t iterator; /* For apr_hash_first(NULL, ...) */
78 unsigned int count, max;
79 apr_hashfunc_t hash_func;
80 apr_hash_entry_t *free; /* List of recycled entries */
81};
82
83#define INITIAL_MAX15 15 /* tunable == 2^n - 1 */
84
85
86/*
87 * Hash creation functions.
88 */
89
90static apr_hash_entry_t **alloc_array(apr_hash_t *ht, unsigned int max)
91{
92 return apr_pcalloc(ht->pool, sizeof(*ht->array) * (max + 1))memset(apr_palloc(ht->pool, sizeof(*ht->array) * (max +
1)), 0, sizeof(*ht->array) * (max + 1));
93}
94
95APR_DECLARE(apr_hash_t *)apr_hash_t * apr_hash_make(apr_pool_t *pool)
96{
97 apr_hash_t *ht;
98 ht = apr_palloc(pool, sizeof(apr_hash_t));
99 ht->pool = pool;
100 ht->free = NULL((void*)0);
101 ht->count = 0;
102 ht->max = INITIAL_MAX15;
103 ht->array = alloc_array(ht, ht->max);
104 ht->hash_func = apr_hashfunc_default;
105 return ht;
106}
107
108APR_DECLARE(apr_hash_t *)apr_hash_t * apr_hash_make_custom(apr_pool_t *pool,
109 apr_hashfunc_t hash_func)
110{
111 apr_hash_t *ht = apr_hash_make(pool);
112 ht->hash_func = hash_func;
113 return ht;
114}
115
116
117/*
118 * Hash iteration functions.
119 */
120
121APR_DECLARE(apr_hash_index_t *)apr_hash_index_t * apr_hash_next(apr_hash_index_t *hi)
122{
123 hi->this = hi->next;
124 while (!hi->this) {
125 if (hi->index > hi->ht->max)
126 return NULL((void*)0);
127
128 hi->this = hi->ht->array[hi->index++];
129 }
130 hi->next = hi->this->next;
131 return hi;
132}
133
134APR_DECLARE(apr_hash_index_t *)apr_hash_index_t * apr_hash_first(apr_pool_t *p, apr_hash_t *ht)
135{
136 apr_hash_index_t *hi;
137 if (p)
138 hi = apr_palloc(p, sizeof(*hi));
139 else
140 hi = &ht->iterator;
141
142 hi->ht = ht;
143 hi->index = 0;
144 hi->this = NULL((void*)0);
145 hi->next = NULL((void*)0);
146 return apr_hash_next(hi);
147}
148
149APR_DECLARE(void)void apr_hash_this(apr_hash_index_t *hi,
150 const void **key,
151 apr_ssize_t *klen,
152 void **val)
153{
154 if (key) *key = hi->this->key;
155 if (klen) *klen = hi->this->klen;
156 if (val) *val = (void *)hi->this->val;
157}
158
159
160/*
161 * Expanding a hash table
162 */
163
164static void expand_array(apr_hash_t *ht)
165{
166 apr_hash_index_t *hi;
167 apr_hash_entry_t **new_array;
168 unsigned int new_max;
169
170 new_max = ht->max * 2 + 1;
171 new_array = alloc_array(ht, new_max);
172 for (hi = apr_hash_first(NULL((void*)0), ht); hi; hi = apr_hash_next(hi)) {
173 unsigned int i = hi->this->hash & new_max;
174 hi->this->next = new_array[i];
175 new_array[i] = hi->this;
176 }
177 ht->array = new_array;
178 ht->max = new_max;
179}
180
181APR_DECLARE_NONSTD(unsigned int)unsigned int apr_hashfunc_default(const char *char_key,
182 apr_ssize_t *klen)
183{
184 unsigned int hash = 0;
185 const unsigned char *key = (const unsigned char *)char_key;
186 const unsigned char *p;
187 apr_ssize_t i;
188
189 /*
190 * This is the popular `times 33' hash algorithm which is used by
191 * perl and also appears in Berkeley DB. This is one of the best
192 * known hash functions for strings because it is both computed
193 * very fast and distributes very well.
194 *
195 * The originator may be Dan Bernstein but the code in Berkeley DB
196 * cites Chris Torek as the source. The best citation I have found
197 * is "Chris Torek, Hash function for text in C, Usenet message
198 * <27038@mimsy.umd.edu> in comp.lang.c , October, 1990." in Rich
199 * Salz's USENIX 1992 paper about INN which can be found at
200 * <http://citeseer.nj.nec.com/salz92internetnews.html>.
201 *
202 * The magic of number 33, i.e. why it works better than many other
203 * constants, prime or not, has never been adequately explained by
204 * anyone. So I try an explanation: if one experimentally tests all
205 * multipliers between 1 and 256 (as I did while writing a low-level
206 * data structure library some time ago) one detects that even
207 * numbers are not useable at all. The remaining 128 odd numbers
208 * (except for the number 1) work more or less all equally well.
209 * They all distribute in an acceptable way and this way fill a hash
210 * table with an average percent of approx. 86%.
211 *
212 * If one compares the chi^2 values of the variants (see
213 * Bob Jenkins ``Hashing Frequently Asked Questions'' at
214 * http://burtleburtle.net/bob/hash/hashfaq.html for a description
215 * of chi^2), the number 33 not even has the best value. But the
216 * number 33 and a few other equally good numbers like 17, 31, 63,
217 * 127 and 129 have nevertheless a great advantage to the remaining
218 * numbers in the large set of possible multipliers: their multiply
219 * operation can be replaced by a faster operation based on just one
220 * shift plus either a single addition or subtraction operation. And
221 * because a hash function has to both distribute good _and_ has to
222 * be very fast to compute, those few numbers should be preferred.
223 *
224 * -- Ralf S. Engelschall <rse@engelschall.com>
225 */
226
227 if (*klen == APR_HASH_KEY_STRING(-1)) {
228 for (p = key; *p; p++) {
229 hash = hash * 33 + *p;
230 }
231 *klen = p - key;
232 }
233 else {
234 for (p = key, i = *klen; i; i--, p++) {
235 hash = hash * 33 + *p;
236 }
237 }
238
239 return hash;
240}
241
242
243/*
244 * This is where we keep the details of the hash function and control
245 * the maximum collision rate.
246 *
247 * If val is non-NULL it creates and initializes a new hash entry if
248 * there isn't already one there; it returns an updatable pointer so
249 * that hash entries can be removed.
250 */
251
252static apr_hash_entry_t **find_entry(apr_hash_t *ht,
253 const void *key,
254 apr_ssize_t klen,
255 const void *val)
256{
257 apr_hash_entry_t **hep, *he;
258 unsigned int hash;
259
260 hash = ht->hash_func(key, &klen);
261
262 /* scan linked list */
263 for (hep = &ht->array[hash & ht->max], he = *hep;
264 he; hep = &he->next, he = *hep) {
265 if (he->hash == hash
266 && he->klen == klen
267 && memcmp(he->key, key, klen) == 0)
268 break;
269 }
270 if (he || !val)
271 return hep;
272
273 /* add a new entry for non-NULL values */
274 if ((he = ht->free) != NULL((void*)0))
275 ht->free = he->next;
276 else
277 he = apr_palloc(ht->pool, sizeof(*he));
278 he->next = NULL((void*)0);
279 he->hash = hash;
280 he->key = key;
281 he->klen = klen;
282 he->val = val;
283 *hep = he;
284 ht->count++;
285 return hep;
286}
287
288APR_DECLARE(apr_hash_t *)apr_hash_t * apr_hash_copy(apr_pool_t *pool,
289 const apr_hash_t *orig)
290{
291 apr_hash_t *ht;
292 apr_hash_entry_t *new_vals;
293 unsigned int i, j;
294
295 ht = apr_palloc(pool, sizeof(apr_hash_t) +
296 sizeof(*ht->array) * (orig->max + 1) +
297 sizeof(apr_hash_entry_t) * orig->count);
298 ht->pool = pool;
299 ht->free = NULL((void*)0);
300 ht->count = orig->count;
301 ht->max = orig->max;
302 ht->hash_func = orig->hash_func;
303 ht->array = (apr_hash_entry_t **)((char *)ht + sizeof(apr_hash_t));
304
305 new_vals = (apr_hash_entry_t *)((char *)(ht) + sizeof(apr_hash_t) +
306 sizeof(*ht->array) * (orig->max + 1));
307 j = 0;
308 for (i = 0; i <= ht->max; i++) {
309 apr_hash_entry_t **new_entry = &(ht->array[i]);
310 apr_hash_entry_t *orig_entry = orig->array[i];
311 while (orig_entry) {
312 *new_entry = &new_vals[j++];
313 (*new_entry)->hash = orig_entry->hash;
314 (*new_entry)->key = orig_entry->key;
315 (*new_entry)->klen = orig_entry->klen;
316 (*new_entry)->val = orig_entry->val;
317 new_entry = &((*new_entry)->next);
318 orig_entry = orig_entry->next;
319 }
320 *new_entry = NULL((void*)0);
321 }
322 return ht;
323}
324
325APR_DECLARE(void *)void * apr_hash_get(apr_hash_t *ht,
326 const void *key,
327 apr_ssize_t klen)
328{
329 apr_hash_entry_t *he;
330 he = *find_entry(ht, key, klen, NULL((void*)0));
331 if (he)
332 return (void *)he->val;
333 else
334 return NULL((void*)0);
335}
336
337APR_DECLARE(void)void apr_hash_set(apr_hash_t *ht,
338 const void *key,
339 apr_ssize_t klen,
340 const void *val)
341{
342 apr_hash_entry_t **hep;
343 hep = find_entry(ht, key, klen, val);
344 if (*hep) {
345 if (!val) {
346 /* delete entry */
347 apr_hash_entry_t *old = *hep;
348 *hep = (*hep)->next;
349 old->next = ht->free;
350 ht->free = old;
351 --ht->count;
352 }
353 else {
354 /* replace entry */
355 (*hep)->val = val;
356 /* check that the collision rate isn't too high */
357 if (ht->count > ht->max) {
358 expand_array(ht);
359 }
360 }
361 }
362 /* else key not present and val==NULL */
363}
364
365APR_DECLARE(unsigned int)unsigned int apr_hash_count(apr_hash_t *ht)
366{
367 return ht->count;
368}
369
370APR_DECLARE(void)void apr_hash_clear(apr_hash_t *ht)
371{
372 apr_hash_index_t *hi;
373 for (hi = apr_hash_first(NULL((void*)0), ht); hi; hi = apr_hash_next(hi))
374 apr_hash_set(ht, hi->this->key, hi->this->klen, NULL((void*)0));
375}
376
377APR_DECLARE(apr_hash_t*)apr_hash_t* apr_hash_overlay(apr_pool_t *p,
378 const apr_hash_t *overlay,
379 const apr_hash_t *base)
380{
381 return apr_hash_merge(p, overlay, base, NULL((void*)0), NULL((void*)0));
382}
383
384APR_DECLARE(apr_hash_t *)apr_hash_t * apr_hash_merge(apr_pool_t *p,
385 const apr_hash_t *overlay,
386 const apr_hash_t *base,
387 void * (*merger)(apr_pool_t *p,
388 const void *key,
389 apr_ssize_t klen,
390 const void *h1_val,
391 const void *h2_val,
392 const void *data),
393 const void *data)
394{
395 apr_hash_t *res;
396 apr_hash_entry_t *new_vals = NULL((void*)0);
1
'new_vals' initialized to a null pointer value
→
397 apr_hash_entry_t *iter;
398 apr_hash_entry_t *ent;
399 unsigned int i,j,k;
400
401#if APR_POOL_DEBUG0
402 /* we don't copy keys and values, so it's necessary that
403 * overlay->a.pool and base->a.pool have a life span at least
404 * as long as p
405 */
406 if (!apr_pool_is_ancestor(overlay->pool, p)) {
407 fprintf(stderr,
408 "apr_hash_merge: overlay's pool is not an ancestor of p\n");
409 abort();
410 }
411 if (!apr_pool_is_ancestor(base->pool, p)) {
412 fprintf(stderr,
413 "apr_hash_merge: base's pool is not an ancestor of p\n");
414 abort();
415 }
416#endif
417
418 res = apr_palloc(p, sizeof(apr_hash_t));
419 res->pool = p;
420 res->free = NULL((void*)0);
421 res->hash_func = base->hash_func;
422 res->count = base->count;
423 res->max = (overlay->max > base->max) ? overlay->max : base->max;
2
←
'?' condition is false
→
424 if (base->count + overlay->count > res->max) {
3
←
Taking false branch
→
425 res->max = res->max * 2 + 1;
426 }
427 res->array = alloc_array(res, res->max);
428 if (base->count + overlay->count) {
4
←
Taking false branch
→
429 new_vals = apr_palloc(p, sizeof(apr_hash_entry_t) *
430 (base->count + overlay->count));
431 }
432 j = 0;
433 for (k = 0; k <= base->max; k++) {
5
←
Loop condition is true. Entering loop body
→
7
←
Loop condition is false. Execution continues on line 446
→
434 for (iter = base->array[k]; iter; iter = iter->next) {
6
←
Loop condition is false. Execution continues on line 433
→
435 i = iter->hash & res->max;
436 new_vals[j].klen = iter->klen;
437 new_vals[j].key = iter->key;
438 new_vals[j].val = iter->val;
439 new_vals[j].hash = iter->hash;
440 new_vals[j].next = res->array[i];
441 res->array[i] = &new_vals[j];
442 j++;
443 }
444 }
445
446 for (k = 0; k <= overlay->max; k++) {
8
←
Loop condition is true. Entering loop body
→
447 for (iter = overlay->array[k]; iter; iter = iter->next) {
9
←
Loop condition is true. Entering loop body
→
448 i = iter->hash & res->max;
449 for (ent = res->array[i]; ent; ent = ent->next) {
10
←
Loop condition is false. Execution continues on line 462
→
450 if ((ent->klen == iter->klen) &&
451 (memcmp(ent->key, iter->key, iter->klen) == 0)) {
452 if (merger) {
453 ent->val = (*merger)(p, iter->key, iter->klen,
454 iter->val, ent->val, data);
455 }
456 else {
457 ent->val = iter->val;
458 }
459 break;
460 }
461 }
462 if (!ent) {
11
←
Taking true branch
→
463 new_vals[j].klen = iter->klen;
12
←
Dereference of null pointer
464 new_vals[j].key = iter->key;
465 new_vals[j].val = iter->val;
466 new_vals[j].hash = iter->hash;
467 new_vals[j].next = res->array[i];
468 res->array[i] = &new_vals[j];
469 res->count++;
470 j++;
471 }
472 }
473 }
474 return res;
475}
476
477APR_POOL_IMPLEMENT_ACCESSOR(hash)apr_pool_t * apr_hash_pool_get (const apr_hash_t *thehash) { return
thehash->pool; }