Coverage Report

Created: 2023-09-28 22:19

/src/libxml2/dict.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * dict.c: dictionary of reusable strings, just used to avoid allocation
3
 *         and freeing operations.
4
 *
5
 * Copyright (C) 2003-2012 Daniel Veillard.
6
 *
7
 * Permission to use, copy, modify, and distribute this software for any
8
 * purpose with or without fee is hereby granted, provided that the above
9
 * copyright notice and this permission notice appear in all copies.
10
 *
11
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
12
 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
13
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
14
 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
15
 *
16
 * Author: daniel@veillard.com
17
 */
18
19
#define IN_LIBXML
20
#include "libxml.h"
21
22
#include <limits.h>
23
#include <stdlib.h>
24
#include <time.h>
25
26
#include "private/dict.h"
27
#include "private/threads.h"
28
29
/*
30
 * Following http://www.ocert.org/advisories/ocert-2011-003.html
31
 * it seems that having hash randomization might be a good idea
32
 * when using XML with untrusted data
33
 * Note1: that it works correctly only if compiled with WITH_BIG_KEY
34
 *  which is the default.
35
 * Note2: the fast function used for a small dict won't protect very
36
 *  well but since the attack is based on growing a very big hash
37
 *  list we will use the BigKey algo as soon as the hash size grows
38
 *  over MIN_DICT_SIZE so this actually works
39
 */
40
#if !defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION)
41
#define DICT_RANDOMIZATION
42
#endif
43
44
#include <string.h>
45
#ifdef HAVE_STDINT_H
46
#include <stdint.h>
47
#else
48
#ifdef HAVE_INTTYPES_H
49
#include <inttypes.h>
50
#elif defined(_WIN32)
51
typedef unsigned __int32 uint32_t;
52
#endif
53
#endif
54
#include <libxml/tree.h>
55
#include <libxml/dict.h>
56
#include <libxml/xmlmemory.h>
57
#include <libxml/xmlerror.h>
58
#include <libxml/globals.h>
59
60
/* #define DEBUG_GROW */
61
/* #define DICT_DEBUG_PATTERNS */
62
63
9.22M
#define MAX_HASH_LEN 3
64
122M
#define MIN_DICT_SIZE 128
65
8.97k
#define MAX_DICT_HASH 8 * 2048
66
#define WITH_BIG_KEY
67
68
#ifdef WITH_BIG_KEY
69
#define xmlDictComputeKey(dict, name, len)                              \
70
117M
    (((dict)->size == MIN_DICT_SIZE) ?                                  \
71
117M
     xmlDictComputeFastKey(name, len, (dict)->seed) :                   \
72
117M
     xmlDictComputeBigKey(name, len, (dict)->seed))
73
74
#define xmlDictComputeQKey(dict, prefix, plen, name, len)               \
75
290k
    (((prefix) == NULL) ?                                               \
76
290k
      (xmlDictComputeKey(dict, name, len)) :                             \
77
290k
      (((dict)->size == MIN_DICT_SIZE) ?                                \
78
290k
       xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed) :  \
79
290k
       xmlDictComputeBigQKey(prefix, plen, name, len, (dict)->seed)))
80
81
#else /* !WITH_BIG_KEY */
82
#define xmlDictComputeKey(dict, name, len)                              \
83
        xmlDictComputeFastKey(name, len, (dict)->seed)
84
#define xmlDictComputeQKey(dict, prefix, plen, name, len)               \
85
        xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed)
86
#endif /* WITH_BIG_KEY */
87
88
/*
89
 * An entry in the dictionary
90
 */
91
typedef struct _xmlDictEntry xmlDictEntry;
92
typedef xmlDictEntry *xmlDictEntryPtr;
93
struct _xmlDictEntry {
94
    struct _xmlDictEntry *next;
95
    const xmlChar *name;
96
    unsigned int len;
97
    int valid;
98
    unsigned long okey;
99
};
100
101
typedef struct _xmlDictStrings xmlDictStrings;
102
typedef xmlDictStrings *xmlDictStringsPtr;
103
struct _xmlDictStrings {
104
    xmlDictStringsPtr next;
105
    xmlChar *free;
106
    xmlChar *end;
107
    size_t size;
108
    size_t nbStrings;
109
    xmlChar array[1];
110
};
111
/*
112
 * The entire dictionary
113
 */
114
struct _xmlDict {
115
    int ref_counter;
116
117
    struct _xmlDictEntry *dict;
118
    size_t size;
119
    unsigned int nbElems;
120
    xmlDictStringsPtr strings;
121
122
    struct _xmlDict *subdict;
123
    /* used for randomization */
124
    int seed;
125
    /* used to impose a limit on size */
126
    size_t limit;
127
};
128
129
/*
130
 * A mutex for modifying the reference counter for shared
131
 * dictionaries.
132
 */
133
static xmlMutex xmlDictMutex;
134
135
#ifdef DICT_RANDOMIZATION
136
#ifdef HAVE_RAND_R
137
/*
138
 * Internal data for random function, protected by xmlDictMutex
139
 */
140
static unsigned int rand_seed = 0;
141
#endif
142
#endif
143
144
/**
145
 * xmlInitializeDict:
146
 *
147
 * DEPRECATED: Alias for xmlInitParser.
148
 */
149
0
int xmlInitializeDict(void) {
150
0
    xmlInitParser();
151
0
    return(0);
152
0
}
153
154
/**
155
 * __xmlInitializeDict:
156
 *
157
 * This function is not public
158
 * Do the dictionary mutex initialization.
159
 */
160
3.70k
int __xmlInitializeDict(void) {
161
3.70k
    xmlInitMutex(&xmlDictMutex);
162
163
#ifdef DICT_RANDOMIZATION
164
#ifdef HAVE_RAND_R
165
    rand_seed = time(NULL);
166
    rand_r(& rand_seed);
167
#else
168
    srand(time(NULL));
169
#endif
170
#endif
171
3.70k
    return(1);
172
3.70k
}
173
174
#ifdef DICT_RANDOMIZATION
175
int __xmlRandom(void) {
176
    int ret;
177
178
    xmlMutexLock(&xmlDictMutex);
179
#ifdef HAVE_RAND_R
180
    ret = rand_r(& rand_seed);
181
#else
182
    ret = rand();
183
#endif
184
    xmlMutexUnlock(&xmlDictMutex);
185
    return(ret);
186
}
187
#endif
188
189
/**
190
 * xmlDictCleanup:
191
 *
192
 * DEPRECATED: This function is a no-op. Call xmlCleanupParser
193
 * to free global state but see the warnings there. xmlCleanupParser
194
 * should be only called once at program exit. In most cases, you don't
195
 * have call cleanup functions at all.
196
 */
197
void
198
0
xmlDictCleanup(void) {
199
0
}
200
201
/**
202
 * xmlCleanupDictInternal:
203
 *
204
 * Free the dictionary mutex.
205
 */
206
void
207
0
xmlCleanupDictInternal(void) {
208
0
    xmlCleanupMutex(&xmlDictMutex);
209
0
}
210
211
/*
212
 * xmlDictAddString:
213
 * @dict: the dictionary
214
 * @name: the name of the userdata
215
 * @len: the length of the name
216
 *
217
 * Add the string to the array[s]
218
 *
219
 * Returns the pointer of the local string, or NULL in case of error.
220
 */
221
static const xmlChar *
222
9.10M
xmlDictAddString(xmlDictPtr dict, const xmlChar *name, unsigned int namelen) {
223
9.10M
    xmlDictStringsPtr pool;
224
9.10M
    const xmlChar *ret;
225
9.10M
    size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
226
9.10M
    size_t limit = 0;
227
228
#ifdef DICT_DEBUG_PATTERNS
229
    fprintf(stderr, "-");
230
#endif
231
9.10M
    pool = dict->strings;
232
9.11M
    while (pool != NULL) {
233
8.46M
  if ((size_t)(pool->end - pool->free) > namelen)
234
8.44M
      goto found_pool;
235
17.9k
  if (pool->size > size) size = pool->size;
236
17.9k
        limit += pool->size;
237
17.9k
  pool = pool->next;
238
17.9k
    }
239
    /*
240
     * Not found, need to allocate
241
     */
242
655k
    if (pool == NULL) {
243
655k
        if ((dict->limit > 0) && (limit > dict->limit)) {
244
0
            return(NULL);
245
0
        }
246
247
655k
        if (size == 0) size = 1000;
248
15.1k
  else size *= 4; /* exponential growth */
249
655k
        if (size < 4 * namelen)
250
4.28k
      size = 4 * namelen; /* just in case ! */
251
655k
  pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
252
655k
  if (pool == NULL)
253
0
      return(NULL);
254
655k
  pool->size = size;
255
655k
  pool->nbStrings = 0;
256
655k
  pool->free = &pool->array[0];
257
655k
  pool->end = &pool->array[size];
258
655k
  pool->next = dict->strings;
259
655k
  dict->strings = pool;
260
#ifdef DICT_DEBUG_PATTERNS
261
        fprintf(stderr, "+");
262
#endif
263
655k
    }
264
9.10M
found_pool:
265
9.10M
    ret = pool->free;
266
9.10M
    memcpy(pool->free, name, namelen);
267
9.10M
    pool->free += namelen;
268
9.10M
    *(pool->free++) = 0;
269
9.10M
    pool->nbStrings++;
270
9.10M
    return(ret);
271
655k
}
272
273
/*
274
 * xmlDictAddQString:
275
 * @dict: the dictionary
276
 * @prefix: the prefix of the userdata
277
 * @plen: the prefix length
278
 * @name: the name of the userdata
279
 * @len: the length of the name
280
 *
281
 * Add the QName to the array[s]
282
 *
283
 * Returns the pointer of the local string, or NULL in case of error.
284
 */
285
static const xmlChar *
286
xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen,
287
                 const xmlChar *name, unsigned int namelen)
288
107k
{
289
107k
    xmlDictStringsPtr pool;
290
107k
    const xmlChar *ret;
291
107k
    size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
292
107k
    size_t limit = 0;
293
294
107k
    if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
295
296
#ifdef DICT_DEBUG_PATTERNS
297
    fprintf(stderr, "=");
298
#endif
299
107k
    pool = dict->strings;
300
108k
    while (pool != NULL) {
301
107k
  if ((size_t)(pool->end - pool->free) > namelen + plen + 1)
302
106k
      goto found_pool;
303
932
  if (pool->size > size) size = pool->size;
304
932
        limit += pool->size;
305
932
  pool = pool->next;
306
932
    }
307
    /*
308
     * Not found, need to allocate
309
     */
310
364
    if (pool == NULL) {
311
364
        if ((dict->limit > 0) && (limit > dict->limit)) {
312
0
            return(NULL);
313
0
        }
314
315
364
        if (size == 0) size = 1000;
316
364
  else size *= 4; /* exponential growth */
317
364
        if (size < 4 * (namelen + plen + 1))
318
0
      size = 4 * (namelen + plen + 1); /* just in case ! */
319
364
  pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
320
364
  if (pool == NULL)
321
0
      return(NULL);
322
364
  pool->size = size;
323
364
  pool->nbStrings = 0;
324
364
  pool->free = &pool->array[0];
325
364
  pool->end = &pool->array[size];
326
364
  pool->next = dict->strings;
327
364
  dict->strings = pool;
328
#ifdef DICT_DEBUG_PATTERNS
329
        fprintf(stderr, "+");
330
#endif
331
364
    }
332
107k
found_pool:
333
107k
    ret = pool->free;
334
107k
    memcpy(pool->free, prefix, plen);
335
107k
    pool->free += plen;
336
107k
    *(pool->free++) = ':';
337
107k
    memcpy(pool->free, name, namelen);
338
107k
    pool->free += namelen;
339
107k
    *(pool->free++) = 0;
340
107k
    pool->nbStrings++;
341
107k
    return(ret);
342
364
}
343
344
#ifdef WITH_BIG_KEY
345
/*
346
 * xmlDictComputeBigKey:
347
 *
348
 * Calculate a hash key using a good hash function that works well for
349
 * larger hash table sizes.
350
 *
351
 * Hash function by "One-at-a-Time Hash" see
352
 * http://burtleburtle.net/bob/hash/doobs.html
353
 */
354
355
#ifdef __clang__
356
ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow")
357
#endif
358
static uint32_t
359
11.3M
xmlDictComputeBigKey(const xmlChar* data, int namelen, int seed) {
360
11.3M
    uint32_t hash;
361
11.3M
    int i;
362
363
11.3M
    if (namelen <= 0 || data == NULL) return(0);
364
365
11.3M
    hash = seed;
366
367
77.1M
    for (i = 0;i < namelen; i++) {
368
65.8M
        hash += data[i];
369
65.8M
  hash += (hash << 10);
370
65.8M
  hash ^= (hash >> 6);
371
65.8M
    }
372
11.3M
    hash += (hash << 3);
373
11.3M
    hash ^= (hash >> 11);
374
11.3M
    hash += (hash << 15);
375
376
11.3M
    return hash;
377
11.3M
}
378
379
/*
380
 * xmlDictComputeBigQKey:
381
 *
382
 * Calculate a hash key for two strings using a good hash function
383
 * that works well for larger hash table sizes.
384
 *
385
 * Hash function by "One-at-a-Time Hash" see
386
 * http://burtleburtle.net/bob/hash/doobs.html
387
 *
388
 * Neither of the two strings must be NULL.
389
 */
390
#ifdef __clang__
391
ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow")
392
#endif
393
static unsigned long
394
xmlDictComputeBigQKey(const xmlChar *prefix, int plen,
395
                      const xmlChar *name, int len, int seed)
396
58.5k
{
397
58.5k
    uint32_t hash;
398
58.5k
    int i;
399
400
58.5k
    hash = seed;
401
402
319k
    for (i = 0;i < plen; i++) {
403
260k
        hash += prefix[i];
404
260k
  hash += (hash << 10);
405
260k
  hash ^= (hash >> 6);
406
260k
    }
407
58.5k
    hash += ':';
408
58.5k
    hash += (hash << 10);
409
58.5k
    hash ^= (hash >> 6);
410
411
475k
    for (i = 0;i < len; i++) {
412
417k
        hash += name[i];
413
417k
  hash += (hash << 10);
414
417k
  hash ^= (hash >> 6);
415
417k
    }
416
58.5k
    hash += (hash << 3);
417
58.5k
    hash ^= (hash >> 11);
418
58.5k
    hash += (hash << 15);
419
420
58.5k
    return hash;
421
58.5k
}
422
#endif /* WITH_BIG_KEY */
423
424
/*
425
 * xmlDictComputeFastKey:
426
 *
427
 * Calculate a hash key using a fast hash function that works well
428
 * for low hash table fill.
429
 */
430
static unsigned long
431
106M
xmlDictComputeFastKey(const xmlChar *name, int namelen, int seed) {
432
106M
    unsigned long value = seed;
433
434
106M
    if (name == NULL) return(0);
435
106M
    value += *name;
436
106M
    value <<= 5;
437
106M
    if (namelen > 10) {
438
4.38M
        value += name[namelen - 1];
439
4.38M
        namelen = 10;
440
4.38M
    }
441
106M
    switch (namelen) {
442
5.28M
        case 10: value += name[9];
443
        /* Falls through. */
444
6.15M
        case 9: value += name[8];
445
        /* Falls through. */
446
7.53M
        case 8: value += name[7];
447
        /* Falls through. */
448
9.78M
        case 7: value += name[6];
449
        /* Falls through. */
450
12.4M
        case 6: value += name[5];
451
        /* Falls through. */
452
17.3M
        case 5: value += name[4];
453
        /* Falls through. */
454
67.7M
        case 4: value += name[3];
455
        /* Falls through. */
456
80.3M
        case 3: value += name[2];
457
        /* Falls through. */
458
85.9M
        case 2: value += name[1];
459
        /* Falls through. */
460
106M
        default: break;
461
106M
    }
462
106M
    return(value);
463
106M
}
464
465
/*
466
 * xmlDictComputeFastQKey:
467
 *
468
 * Calculate a hash key for two strings using a fast hash function
469
 * that works well for low hash table fill.
470
 *
471
 * Neither of the two strings must be NULL.
472
 */
473
static unsigned long
474
xmlDictComputeFastQKey(const xmlChar *prefix, int plen,
475
                       const xmlChar *name, int len, int seed)
476
231k
{
477
231k
    unsigned long value = seed;
478
479
231k
    if (plen == 0)
480
0
  value += 30 * ':';
481
231k
    else
482
231k
  value += 30 * (*prefix);
483
484
231k
    if (len > 10) {
485
16.6k
        int offset = len - (plen + 1 + 1);
486
16.6k
  if (offset < 0)
487
1.11k
      offset = len - (10 + 1);
488
16.6k
  value += name[offset];
489
16.6k
        len = 10;
490
16.6k
  if (plen > 10)
491
1.38k
      plen = 10;
492
16.6k
    }
493
231k
    switch (plen) {
494
2.94k
        case 10: value += prefix[9];
495
        /* Falls through. */
496
5.09k
        case 9: value += prefix[8];
497
        /* Falls through. */
498
6.99k
        case 8: value += prefix[7];
499
        /* Falls through. */
500
9.52k
        case 7: value += prefix[6];
501
        /* Falls through. */
502
11.9k
        case 6: value += prefix[5];
503
        /* Falls through. */
504
27.0k
        case 5: value += prefix[4];
505
        /* Falls through. */
506
34.1k
        case 4: value += prefix[3];
507
        /* Falls through. */
508
205k
        case 3: value += prefix[2];
509
        /* Falls through. */
510
210k
        case 2: value += prefix[1];
511
        /* Falls through. */
512
227k
        case 1: value += prefix[0];
513
        /* Falls through. */
514
231k
        default: break;
515
231k
    }
516
231k
    len -= plen;
517
231k
    if (len > 0) {
518
163k
        value += ':';
519
163k
  len--;
520
163k
    }
521
231k
    switch (len) {
522
0
        case 10: value += name[9];
523
        /* Falls through. */
524
0
        case 9: value += name[8];
525
        /* Falls through. */
526
2.83k
        case 8: value += name[7];
527
        /* Falls through. */
528
5.03k
        case 7: value += name[6];
529
        /* Falls through. */
530
21.5k
        case 6: value += name[5];
531
        /* Falls through. */
532
57.0k
        case 5: value += name[4];
533
        /* Falls through. */
534
68.4k
        case 4: value += name[3];
535
        /* Falls through. */
536
81.6k
        case 3: value += name[2];
537
        /* Falls through. */
538
97.8k
        case 2: value += name[1];
539
        /* Falls through. */
540
115k
        case 1: value += name[0];
541
        /* Falls through. */
542
231k
        default: break;
543
231k
    }
544
231k
    return(value);
545
231k
}
546
547
/**
548
 * xmlDictCreate:
549
 *
550
 * Create a new dictionary
551
 *
552
 * Returns the newly created dictionary, or NULL if an error occurred.
553
 */
554
xmlDictPtr
555
1.47M
xmlDictCreate(void) {
556
1.47M
    xmlDictPtr dict;
557
558
1.47M
    xmlInitParser();
559
560
#ifdef DICT_DEBUG_PATTERNS
561
    fprintf(stderr, "C");
562
#endif
563
564
1.47M
    dict = xmlMalloc(sizeof(xmlDict));
565
1.47M
    if (dict) {
566
1.47M
        dict->ref_counter = 1;
567
1.47M
        dict->limit = 0;
568
569
1.47M
        dict->size = MIN_DICT_SIZE;
570
1.47M
  dict->nbElems = 0;
571
1.47M
        dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
572
1.47M
  dict->strings = NULL;
573
1.47M
  dict->subdict = NULL;
574
1.47M
        if (dict->dict) {
575
1.47M
      memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
576
#ifdef DICT_RANDOMIZATION
577
            dict->seed = __xmlRandom();
578
#else
579
1.47M
            dict->seed = 0;
580
1.47M
#endif
581
1.47M
      return(dict);
582
1.47M
        }
583
0
        xmlFree(dict);
584
0
    }
585
0
    return(NULL);
586
1.47M
}
587
588
/**
589
 * xmlDictCreateSub:
590
 * @sub: an existing dictionary
591
 *
592
 * Create a new dictionary, inheriting strings from the read-only
593
 * dictionary @sub. On lookup, strings are first searched in the
594
 * new dictionary, then in @sub, and if not found are created in the
595
 * new dictionary.
596
 *
597
 * Returns the newly created dictionary, or NULL if an error occurred.
598
 */
599
xmlDictPtr
600
0
xmlDictCreateSub(xmlDictPtr sub) {
601
0
    xmlDictPtr dict = xmlDictCreate();
602
603
0
    if ((dict != NULL) && (sub != NULL)) {
604
#ifdef DICT_DEBUG_PATTERNS
605
        fprintf(stderr, "R");
606
#endif
607
0
        dict->seed = sub->seed;
608
0
        dict->subdict = sub;
609
0
  xmlDictReference(dict->subdict);
610
0
    }
611
0
    return(dict);
612
0
}
613
614
/**
615
 * xmlDictReference:
616
 * @dict: the dictionary
617
 *
618
 * Increment the reference counter of a dictionary
619
 *
620
 * Returns 0 in case of success and -1 in case of error
621
 */
622
int
623
982k
xmlDictReference(xmlDictPtr dict) {
624
982k
    if (dict == NULL) return -1;
625
793k
    xmlMutexLock(&xmlDictMutex);
626
793k
    dict->ref_counter++;
627
793k
    xmlMutexUnlock(&xmlDictMutex);
628
793k
    return(0);
629
982k
}
630
631
/**
632
 * xmlDictGrow:
633
 * @dict: the dictionary
634
 * @size: the new size of the dictionary
635
 *
636
 * resize the dictionary
637
 *
638
 * Returns 0 in case of success, -1 in case of failure
639
 */
640
static int
641
8.97k
xmlDictGrow(xmlDictPtr dict, size_t size) {
642
8.97k
    unsigned long key, okey;
643
8.97k
    size_t oldsize, i;
644
8.97k
    xmlDictEntryPtr iter, next;
645
8.97k
    struct _xmlDictEntry *olddict;
646
#ifdef DEBUG_GROW
647
    unsigned long nbElem = 0;
648
#endif
649
8.97k
    int ret = 0;
650
8.97k
    int keep_keys = 1;
651
652
8.97k
    if (dict == NULL)
653
0
  return(-1);
654
8.97k
    if (size < 8)
655
0
        return(-1);
656
8.97k
    if (size > 8 * 2048)
657
0
  return(-1);
658
659
#ifdef DICT_DEBUG_PATTERNS
660
    fprintf(stderr, "*");
661
#endif
662
663
8.97k
    oldsize = dict->size;
664
8.97k
    olddict = dict->dict;
665
8.97k
    if (olddict == NULL)
666
0
        return(-1);
667
8.97k
    if (oldsize == MIN_DICT_SIZE)
668
8.96k
        keep_keys = 0;
669
670
8.97k
    dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
671
8.97k
    if (dict->dict == NULL) {
672
0
  dict->dict = olddict;
673
0
  return(-1);
674
0
    }
675
8.97k
    memset(dict->dict, 0, size * sizeof(xmlDictEntry));
676
8.97k
    dict->size = size;
677
678
    /*  If the two loops are merged, there would be situations where
679
  a new entry needs to allocated and data copied into it from
680
  the main dict. It is nicer to run through the array twice, first
681
  copying all the elements in the main array (less probability of
682
  allocate) and then the rest, so we only free in the second loop.
683
    */
684
1.16M
    for (i = 0; i < oldsize; i++) {
685
1.15M
  if (olddict[i].valid == 0)
686
542k
      continue;
687
688
609k
  if (keep_keys)
689
2.07k
      okey = olddict[i].okey;
690
607k
  else
691
607k
      okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
692
609k
  key = okey % dict->size;
693
694
609k
  if (dict->dict[key].valid == 0) {
695
564k
      memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
696
564k
      dict->dict[key].next = NULL;
697
564k
      dict->dict[key].okey = okey;
698
564k
  } else {
699
45.0k
      xmlDictEntryPtr entry;
700
701
45.0k
      entry = xmlMalloc(sizeof(xmlDictEntry));
702
45.0k
      if (entry != NULL) {
703
45.0k
    entry->name = olddict[i].name;
704
45.0k
    entry->len = olddict[i].len;
705
45.0k
    entry->okey = okey;
706
45.0k
    entry->next = dict->dict[key].next;
707
45.0k
    entry->valid = 1;
708
45.0k
    dict->dict[key].next = entry;
709
45.0k
      } else {
710
          /*
711
     * we don't have much ways to alert from here
712
     * result is losing an entry and unicity guarantee
713
     */
714
0
          ret = -1;
715
0
      }
716
45.0k
  }
717
#ifdef DEBUG_GROW
718
  nbElem++;
719
#endif
720
609k
    }
721
722
1.16M
    for (i = 0; i < oldsize; i++) {
723
1.15M
  iter = olddict[i].next;
724
1.68M
  while (iter) {
725
534k
      next = iter->next;
726
727
      /*
728
       * put back the entry in the new dict
729
       */
730
731
534k
      if (keep_keys)
732
579
    okey = iter->okey;
733
534k
      else
734
534k
    okey = xmlDictComputeKey(dict, iter->name, iter->len);
735
534k
      key = okey % dict->size;
736
534k
      if (dict->dict[key].valid == 0) {
737
427k
    memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
738
427k
    dict->dict[key].next = NULL;
739
427k
    dict->dict[key].valid = 1;
740
427k
    dict->dict[key].okey = okey;
741
427k
    xmlFree(iter);
742
427k
      } else {
743
107k
    iter->next = dict->dict[key].next;
744
107k
    iter->okey = okey;
745
107k
    dict->dict[key].next = iter;
746
107k
      }
747
748
#ifdef DEBUG_GROW
749
      nbElem++;
750
#endif
751
752
534k
      iter = next;
753
534k
  }
754
1.15M
    }
755
756
8.97k
    xmlFree(olddict);
757
758
#ifdef DEBUG_GROW
759
    xmlGenericError(xmlGenericErrorContext,
760
      "xmlDictGrow : from %lu to %lu, %u elems\n", oldsize, size, nbElem);
761
#endif
762
763
8.97k
    return(ret);
764
8.97k
}
765
766
/**
767
 * xmlDictFree:
768
 * @dict: the dictionary
769
 *
770
 * Free the hash @dict and its contents. The userdata is
771
 * deallocated with @f if provided.
772
 */
773
void
774
2.26M
xmlDictFree(xmlDictPtr dict) {
775
2.26M
    size_t i;
776
2.26M
    xmlDictEntryPtr iter;
777
2.26M
    xmlDictEntryPtr next;
778
2.26M
    int inside_dict = 0;
779
2.26M
    xmlDictStringsPtr pool, nextp;
780
781
2.26M
    if (dict == NULL)
782
0
  return;
783
784
    /* decrement the counter, it may be shared by a parser and docs */
785
2.26M
    xmlMutexLock(&xmlDictMutex);
786
2.26M
    dict->ref_counter--;
787
2.26M
    if (dict->ref_counter > 0) {
788
793k
        xmlMutexUnlock(&xmlDictMutex);
789
793k
        return;
790
793k
    }
791
792
1.47M
    xmlMutexUnlock(&xmlDictMutex);
793
794
1.47M
    if (dict->subdict != NULL) {
795
0
        xmlDictFree(dict->subdict);
796
0
    }
797
798
1.47M
    if (dict->dict) {
799
73.0M
  for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
800
71.6M
      iter = &(dict->dict[i]);
801
71.6M
      if (iter->valid == 0)
802
64.2M
    continue;
803
7.36M
      inside_dict = 1;
804
16.5M
      while (iter) {
805
9.20M
    next = iter->next;
806
9.20M
    if (!inside_dict)
807
1.84M
        xmlFree(iter);
808
9.20M
    dict->nbElems--;
809
9.20M
    inside_dict = 0;
810
9.20M
    iter = next;
811
9.20M
      }
812
7.36M
  }
813
1.47M
  xmlFree(dict->dict);
814
1.47M
    }
815
1.47M
    pool = dict->strings;
816
2.12M
    while (pool != NULL) {
817
655k
        nextp = pool->next;
818
655k
  xmlFree(pool);
819
655k
  pool = nextp;
820
655k
    }
821
1.47M
    xmlFree(dict);
822
1.47M
}
823
824
/**
825
 * xmlDictLookup:
826
 * @dict: the dictionary
827
 * @name: the name of the userdata
828
 * @len: the length of the name, if -1 it is recomputed
829
 *
830
 * Add the @name to the dictionary @dict if not present.
831
 *
832
 * Returns the internal copy of the name or NULL in case of internal error
833
 */
834
const xmlChar *
835
117M
xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
836
117M
    unsigned long key, okey, nbi = 0;
837
117M
    xmlDictEntryPtr entry;
838
117M
    xmlDictEntryPtr insert;
839
117M
    const xmlChar *ret;
840
117M
    unsigned int l;
841
842
117M
    if ((dict == NULL) || (name == NULL))
843
1.68M
  return(NULL);
844
845
116M
    if (len < 0)
846
11.8M
        l = strlen((const char *) name);
847
104M
    else
848
104M
        l = len;
849
850
116M
    if (((dict->limit > 0) && (l >= dict->limit)) ||
851
116M
        (l > INT_MAX / 2))
852
0
        return(NULL);
853
854
    /*
855
     * Check for duplicate and insertion location.
856
     */
857
116M
    okey = xmlDictComputeKey(dict, name, l);
858
116M
    key = okey % dict->size;
859
116M
    if (dict->dict[key].valid == 0) {
860
6.90M
  insert = NULL;
861
109M
    } else {
862
124M
  for (insert = &(dict->dict[key]); insert->next != NULL;
863
109M
       insert = insert->next) {
864
24.0M
#ifdef __GNUC__
865
24.0M
      if ((insert->okey == okey) && (insert->len == l)) {
866
9.71M
    if (!memcmp(insert->name, name, l))
867
9.02M
        return(insert->name);
868
9.71M
      }
869
#else
870
      if ((insert->okey == okey) && (insert->len == l) &&
871
          (!xmlStrncmp(insert->name, name, l)))
872
    return(insert->name);
873
#endif
874
14.9M
      nbi++;
875
14.9M
  }
876
100M
#ifdef __GNUC__
877
100M
  if ((insert->okey == okey) && (insert->len == l)) {
878
98.1M
      if (!memcmp(insert->name, name, l))
879
98.1M
    return(insert->name);
880
98.1M
  }
881
#else
882
  if ((insert->okey == okey) && (insert->len == l) &&
883
      (!xmlStrncmp(insert->name, name, l)))
884
      return(insert->name);
885
#endif
886
100M
    }
887
888
9.10M
    if (dict->subdict) {
889
0
        unsigned long skey;
890
891
        /* we cannot always reuse the same okey for the subdict */
892
0
        if (((dict->size == MIN_DICT_SIZE) &&
893
0
       (dict->subdict->size != MIN_DICT_SIZE)) ||
894
0
            ((dict->size != MIN_DICT_SIZE) &&
895
0
       (dict->subdict->size == MIN_DICT_SIZE)))
896
0
      skey = xmlDictComputeKey(dict->subdict, name, l);
897
0
  else
898
0
      skey = okey;
899
900
0
  key = skey % dict->subdict->size;
901
0
  if (dict->subdict->dict[key].valid != 0) {
902
0
      xmlDictEntryPtr tmp;
903
904
0
      for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
905
0
     tmp = tmp->next) {
906
0
#ifdef __GNUC__
907
0
    if ((tmp->okey == skey) && (tmp->len == l)) {
908
0
        if (!memcmp(tmp->name, name, l))
909
0
      return(tmp->name);
910
0
    }
911
#else
912
    if ((tmp->okey == skey) && (tmp->len == l) &&
913
        (!xmlStrncmp(tmp->name, name, l)))
914
        return(tmp->name);
915
#endif
916
0
    nbi++;
917
0
      }
918
0
#ifdef __GNUC__
919
0
      if ((tmp->okey == skey) && (tmp->len == l)) {
920
0
    if (!memcmp(tmp->name, name, l))
921
0
        return(tmp->name);
922
0
      }
923
#else
924
      if ((tmp->okey == skey) && (tmp->len == l) &&
925
    (!xmlStrncmp(tmp->name, name, l)))
926
    return(tmp->name);
927
#endif
928
0
  }
929
0
  key = okey % dict->size;
930
0
    }
931
932
9.10M
    ret = xmlDictAddString(dict, name, l);
933
9.10M
    if (ret == NULL)
934
0
        return(NULL);
935
9.10M
    if (insert == NULL) {
936
6.90M
  entry = &(dict->dict[key]);
937
6.90M
    } else {
938
2.19M
  entry = xmlMalloc(sizeof(xmlDictEntry));
939
2.19M
  if (entry == NULL)
940
0
       return(NULL);
941
2.19M
    }
942
9.10M
    entry->name = ret;
943
9.10M
    entry->len = l;
944
9.10M
    entry->next = NULL;
945
9.10M
    entry->valid = 1;
946
9.10M
    entry->okey = okey;
947
948
949
9.10M
    if (insert != NULL)
950
2.19M
  insert->next = entry;
951
952
9.10M
    dict->nbElems++;
953
954
9.10M
    if ((nbi > MAX_HASH_LEN) &&
955
9.10M
        (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
956
8.08k
  if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
957
0
      return(NULL);
958
8.08k
    }
959
    /* Note that entry may have been freed at this point by xmlDictGrow */
960
961
9.10M
    return(ret);
962
9.10M
}
963
964
/**
965
 * xmlDictExists:
966
 * @dict: the dictionary
967
 * @name: the name of the userdata
968
 * @len: the length of the name, if -1 it is recomputed
969
 *
970
 * Check if the @name exists in the dictionary @dict.
971
 *
972
 * Returns the internal copy of the name or NULL if not found.
973
 */
974
const xmlChar *
975
0
xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
976
0
    unsigned long key, okey;
977
0
    xmlDictEntryPtr insert;
978
0
    unsigned int l;
979
980
0
    if ((dict == NULL) || (name == NULL))
981
0
  return(NULL);
982
983
0
    if (len < 0)
984
0
        l = strlen((const char *) name);
985
0
    else
986
0
        l = len;
987
0
    if (((dict->limit > 0) && (l >= dict->limit)) ||
988
0
        (l > INT_MAX / 2))
989
0
        return(NULL);
990
991
    /*
992
     * Check for duplicate and insertion location.
993
     */
994
0
    okey = xmlDictComputeKey(dict, name, l);
995
0
    key = okey % dict->size;
996
0
    if (dict->dict[key].valid == 0) {
997
0
  insert = NULL;
998
0
    } else {
999
0
  for (insert = &(dict->dict[key]); insert->next != NULL;
1000
0
       insert = insert->next) {
1001
0
#ifdef __GNUC__
1002
0
      if ((insert->okey == okey) && (insert->len == l)) {
1003
0
    if (!memcmp(insert->name, name, l))
1004
0
        return(insert->name);
1005
0
      }
1006
#else
1007
      if ((insert->okey == okey) && (insert->len == l) &&
1008
          (!xmlStrncmp(insert->name, name, l)))
1009
    return(insert->name);
1010
#endif
1011
0
  }
1012
0
#ifdef __GNUC__
1013
0
  if ((insert->okey == okey) && (insert->len == l)) {
1014
0
      if (!memcmp(insert->name, name, l))
1015
0
    return(insert->name);
1016
0
  }
1017
#else
1018
  if ((insert->okey == okey) && (insert->len == l) &&
1019
      (!xmlStrncmp(insert->name, name, l)))
1020
      return(insert->name);
1021
#endif
1022
0
    }
1023
1024
0
    if (dict->subdict) {
1025
0
        unsigned long skey;
1026
1027
        /* we cannot always reuse the same okey for the subdict */
1028
0
        if (((dict->size == MIN_DICT_SIZE) &&
1029
0
       (dict->subdict->size != MIN_DICT_SIZE)) ||
1030
0
            ((dict->size != MIN_DICT_SIZE) &&
1031
0
       (dict->subdict->size == MIN_DICT_SIZE)))
1032
0
      skey = xmlDictComputeKey(dict->subdict, name, l);
1033
0
  else
1034
0
      skey = okey;
1035
1036
0
  key = skey % dict->subdict->size;
1037
0
  if (dict->subdict->dict[key].valid != 0) {
1038
0
      xmlDictEntryPtr tmp;
1039
1040
0
      for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1041
0
     tmp = tmp->next) {
1042
0
#ifdef __GNUC__
1043
0
    if ((tmp->okey == skey) && (tmp->len == l)) {
1044
0
        if (!memcmp(tmp->name, name, l))
1045
0
      return(tmp->name);
1046
0
    }
1047
#else
1048
    if ((tmp->okey == skey) && (tmp->len == l) &&
1049
        (!xmlStrncmp(tmp->name, name, l)))
1050
        return(tmp->name);
1051
#endif
1052
0
      }
1053
0
#ifdef __GNUC__
1054
0
      if ((tmp->okey == skey) && (tmp->len == l)) {
1055
0
    if (!memcmp(tmp->name, name, l))
1056
0
        return(tmp->name);
1057
0
      }
1058
#else
1059
      if ((tmp->okey == skey) && (tmp->len == l) &&
1060
    (!xmlStrncmp(tmp->name, name, l)))
1061
    return(tmp->name);
1062
#endif
1063
0
  }
1064
0
    }
1065
1066
    /* not found */
1067
0
    return(NULL);
1068
0
}
1069
1070
/**
1071
 * xmlDictQLookup:
1072
 * @dict: the dictionary
1073
 * @prefix: the prefix
1074
 * @name: the name
1075
 *
1076
 * Add the QName @prefix:@name to the hash @dict if not present.
1077
 *
1078
 * Returns the internal copy of the QName or NULL in case of internal error
1079
 */
1080
const xmlChar *
1081
290k
xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
1082
290k
    unsigned long okey, key, nbi = 0;
1083
290k
    xmlDictEntryPtr entry;
1084
290k
    xmlDictEntryPtr insert;
1085
290k
    const xmlChar *ret;
1086
290k
    unsigned int len, plen, l;
1087
1088
290k
    if ((dict == NULL) || (name == NULL))
1089
0
  return(NULL);
1090
290k
    if (prefix == NULL)
1091
0
        return(xmlDictLookup(dict, name, -1));
1092
1093
290k
    l = len = strlen((const char *) name);
1094
290k
    plen = strlen((const char *) prefix);
1095
290k
    len += 1 + plen;
1096
1097
    /*
1098
     * Check for duplicate and insertion location.
1099
     */
1100
290k
    okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
1101
290k
    key = okey % dict->size;
1102
290k
    if (dict->dict[key].valid == 0) {
1103
77.8k
  insert = NULL;
1104
212k
    } else {
1105
287k
  for (insert = &(dict->dict[key]); insert->next != NULL;
1106
212k
       insert = insert->next) {
1107
120k
      if ((insert->okey == okey) && (insert->len == len) &&
1108
120k
          (xmlStrQEqual(prefix, name, insert->name)))
1109
45.5k
    return(insert->name);
1110
74.8k
      nbi++;
1111
74.8k
  }
1112
166k
  if ((insert->okey == okey) && (insert->len == len) &&
1113
166k
      (xmlStrQEqual(prefix, name, insert->name)))
1114
137k
      return(insert->name);
1115
166k
    }
1116
1117
107k
    if (dict->subdict) {
1118
0
        unsigned long skey;
1119
1120
        /* we cannot always reuse the same okey for the subdict */
1121
0
        if (((dict->size == MIN_DICT_SIZE) &&
1122
0
       (dict->subdict->size != MIN_DICT_SIZE)) ||
1123
0
            ((dict->size != MIN_DICT_SIZE) &&
1124
0
       (dict->subdict->size == MIN_DICT_SIZE)))
1125
0
      skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
1126
0
  else
1127
0
      skey = okey;
1128
1129
0
  key = skey % dict->subdict->size;
1130
0
  if (dict->subdict->dict[key].valid != 0) {
1131
0
      xmlDictEntryPtr tmp;
1132
0
      for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1133
0
     tmp = tmp->next) {
1134
0
    if ((tmp->okey == skey) && (tmp->len == len) &&
1135
0
        (xmlStrQEqual(prefix, name, tmp->name)))
1136
0
        return(tmp->name);
1137
0
    nbi++;
1138
0
      }
1139
0
      if ((tmp->okey == skey) && (tmp->len == len) &&
1140
0
    (xmlStrQEqual(prefix, name, tmp->name)))
1141
0
    return(tmp->name);
1142
0
  }
1143
0
  key = okey % dict->size;
1144
0
    }
1145
1146
107k
    ret = xmlDictAddQString(dict, prefix, plen, name, l);
1147
107k
    if (ret == NULL)
1148
0
        return(NULL);
1149
107k
    if (insert == NULL) {
1150
77.8k
  entry = &(dict->dict[key]);
1151
77.8k
    } else {
1152
29.3k
  entry = xmlMalloc(sizeof(xmlDictEntry));
1153
29.3k
  if (entry == NULL)
1154
0
       return(NULL);
1155
29.3k
    }
1156
107k
    entry->name = ret;
1157
107k
    entry->len = len;
1158
107k
    entry->next = NULL;
1159
107k
    entry->valid = 1;
1160
107k
    entry->okey = okey;
1161
1162
107k
    if (insert != NULL)
1163
29.3k
  insert->next = entry;
1164
1165
107k
    dict->nbElems++;
1166
1167
107k
    if ((nbi > MAX_HASH_LEN) &&
1168
107k
        (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
1169
882
  xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
1170
    /* Note that entry may have been freed at this point by xmlDictGrow */
1171
1172
107k
    return(ret);
1173
107k
}
1174
1175
/**
1176
 * xmlDictOwns:
1177
 * @dict: the dictionary
1178
 * @str: the string
1179
 *
1180
 * check if a string is owned by the dictionary
1181
 *
1182
 * Returns 1 if true, 0 if false and -1 in case of error
1183
 * -1 in case of error
1184
 */
1185
int
1186
94.7M
xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
1187
94.7M
    xmlDictStringsPtr pool;
1188
1189
94.7M
    if ((dict == NULL) || (str == NULL))
1190
0
  return(-1);
1191
94.7M
    pool = dict->strings;
1192
167M
    while (pool != NULL) {
1193
108M
        if ((str >= &pool->array[0]) && (str <= pool->free))
1194
35.7M
      return(1);
1195
72.7M
  pool = pool->next;
1196
72.7M
    }
1197
58.9M
    if (dict->subdict)
1198
0
        return(xmlDictOwns(dict->subdict, str));
1199
58.9M
    return(0);
1200
58.9M
}
1201
1202
/**
1203
 * xmlDictSize:
1204
 * @dict: the dictionary
1205
 *
1206
 * Query the number of elements installed in the hash @dict.
1207
 *
1208
 * Returns the number of elements in the dictionary or
1209
 * -1 in case of error
1210
 */
1211
int
1212
0
xmlDictSize(xmlDictPtr dict) {
1213
0
    if (dict == NULL)
1214
0
  return(-1);
1215
0
    if (dict->subdict)
1216
0
        return(dict->nbElems + dict->subdict->nbElems);
1217
0
    return(dict->nbElems);
1218
0
}
1219
1220
/**
1221
 * xmlDictSetLimit:
1222
 * @dict: the dictionary
1223
 * @limit: the limit in bytes
1224
 *
1225
 * Set a size limit for the dictionary
1226
 * Added in 2.9.0
1227
 *
1228
 * Returns the previous limit of the dictionary or 0
1229
 */
1230
size_t
1231
1.68M
xmlDictSetLimit(xmlDictPtr dict, size_t limit) {
1232
1.68M
    size_t ret;
1233
1234
1.68M
    if (dict == NULL)
1235
0
  return(0);
1236
1.68M
    ret = dict->limit;
1237
1.68M
    dict->limit = limit;
1238
1.68M
    return(ret);
1239
1.68M
}
1240
1241
/**
1242
 * xmlDictGetUsage:
1243
 * @dict: the dictionary
1244
 *
1245
 * Get how much memory is used by a dictionary for strings
1246
 * Added in 2.9.0
1247
 *
1248
 * Returns the amount of strings allocated
1249
 */
1250
size_t
1251
0
xmlDictGetUsage(xmlDictPtr dict) {
1252
0
    xmlDictStringsPtr pool;
1253
0
    size_t limit = 0;
1254
1255
0
    if (dict == NULL)
1256
0
  return(0);
1257
0
    pool = dict->strings;
1258
0
    while (pool != NULL) {
1259
0
        limit += pool->size;
1260
0
  pool = pool->next;
1261
0
    }
1262
0
    return(limit);
1263
0
}
1264