Coverage Report

Created: 2023-03-02 15:25

/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
31.1M
#define MAX_HASH_LEN 3
64
626M
#define MIN_DICT_SIZE 128
65
52.5k
#define MAX_DICT_HASH 8 * 2048
66
#define WITH_BIG_KEY
67
68
#ifdef WITH_BIG_KEY
69
#define xmlDictComputeKey(dict, name, len)                              \
70
623M
    (((dict)->size == MIN_DICT_SIZE) ?                                  \
71
623M
     xmlDictComputeFastKey(name, len, (dict)->seed) :                   \
72
623M
     xmlDictComputeBigKey(name, len, (dict)->seed))
73
74
#define xmlDictComputeQKey(dict, prefix, plen, name, len)               \
75
71.1k
    (((prefix) == NULL) ?                                               \
76
71.1k
      (xmlDictComputeKey(dict, name, len)) :                             \
77
71.1k
      (((dict)->size == MIN_DICT_SIZE) ?                                \
78
71.1k
       xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed) :  \
79
71.1k
       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.18k
int __xmlInitializeDict(void) {
161
3.18k
    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.18k
    return(1);
172
3.18k
}
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
30.9M
xmlDictAddString(xmlDictPtr dict, const xmlChar *name, unsigned int namelen) {
223
30.9M
    xmlDictStringsPtr pool;
224
30.9M
    const xmlChar *ret;
225
30.9M
    size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
226
30.9M
    size_t limit = 0;
227
228
#ifdef DICT_DEBUG_PATTERNS
229
    fprintf(stderr, "-");
230
#endif
231
30.9M
    pool = dict->strings;
232
31.1M
    while (pool != NULL) {
233
30.5M
  if ((size_t)(pool->end - pool->free) > namelen)
234
30.4M
      goto found_pool;
235
116k
  if (pool->size > size) size = pool->size;
236
116k
        limit += pool->size;
237
116k
  pool = pool->next;
238
116k
    }
239
    /*
240
     * Not found, need to allocate
241
     */
242
546k
    if (pool == NULL) {
243
546k
        if ((dict->limit > 0) && (limit > dict->limit)) {
244
0
            return(NULL);
245
0
        }
246
247
546k
        if (size == 0) size = 1000;
248
98.8k
  else size *= 4; /* exponential growth */
249
546k
        if (size < 4 * namelen)
250
4.57k
      size = 4 * namelen; /* just in case ! */
251
546k
  pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
252
546k
  if (pool == NULL)
253
0
      return(NULL);
254
546k
  pool->size = size;
255
546k
  pool->nbStrings = 0;
256
546k
  pool->free = &pool->array[0];
257
546k
  pool->end = &pool->array[size];
258
546k
  pool->next = dict->strings;
259
546k
  dict->strings = pool;
260
#ifdef DICT_DEBUG_PATTERNS
261
        fprintf(stderr, "+");
262
#endif
263
546k
    }
264
30.9M
found_pool:
265
30.9M
    ret = pool->free;
266
30.9M
    memcpy(pool->free, name, namelen);
267
30.9M
    pool->free += namelen;
268
30.9M
    *(pool->free++) = 0;
269
30.9M
    pool->nbStrings++;
270
30.9M
    return(ret);
271
546k
}
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
34.9k
{
289
34.9k
    xmlDictStringsPtr pool;
290
34.9k
    const xmlChar *ret;
291
34.9k
    size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
292
34.9k
    size_t limit = 0;
293
294
34.9k
    if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
295
296
#ifdef DICT_DEBUG_PATTERNS
297
    fprintf(stderr, "=");
298
#endif
299
34.9k
    pool = dict->strings;
300
35.0k
    while (pool != NULL) {
301
34.9k
  if ((size_t)(pool->end - pool->free) > namelen + plen + 1)
302
34.8k
      goto found_pool;
303
125
  if (pool->size > size) size = pool->size;
304
125
        limit += pool->size;
305
125
  pool = pool->next;
306
125
    }
307
    /*
308
     * Not found, need to allocate
309
     */
310
76
    if (pool == NULL) {
311
76
        if ((dict->limit > 0) && (limit > dict->limit)) {
312
0
            return(NULL);
313
0
        }
314
315
76
        if (size == 0) size = 1000;
316
76
  else size *= 4; /* exponential growth */
317
76
        if (size < 4 * (namelen + plen + 1))
318
0
      size = 4 * (namelen + plen + 1); /* just in case ! */
319
76
  pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
320
76
  if (pool == NULL)
321
0
      return(NULL);
322
76
  pool->size = size;
323
76
  pool->nbStrings = 0;
324
76
  pool->free = &pool->array[0];
325
76
  pool->end = &pool->array[size];
326
76
  pool->next = dict->strings;
327
76
  dict->strings = pool;
328
#ifdef DICT_DEBUG_PATTERNS
329
        fprintf(stderr, "+");
330
#endif
331
76
    }
332
34.9k
found_pool:
333
34.9k
    ret = pool->free;
334
34.9k
    memcpy(pool->free, prefix, plen);
335
34.9k
    pool->free += plen;
336
34.9k
    *(pool->free++) = ':';
337
34.9k
    memcpy(pool->free, name, namelen);
338
34.9k
    pool->free += namelen;
339
34.9k
    *(pool->free++) = 0;
340
34.9k
    pool->nbStrings++;
341
34.9k
    return(ret);
342
76
}
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
174M
xmlDictComputeBigKey(const xmlChar* data, int namelen, int seed) {
360
174M
    uint32_t hash;
361
174M
    int i;
362
363
174M
    if (namelen <= 0 || data == NULL) return(0);
364
365
174M
    hash = seed;
366
367
956M
    for (i = 0;i < namelen; i++) {
368
782M
        hash += data[i];
369
782M
  hash += (hash << 10);
370
782M
  hash ^= (hash >> 6);
371
782M
    }
372
174M
    hash += (hash << 3);
373
174M
    hash ^= (hash >> 11);
374
174M
    hash += (hash << 15);
375
376
174M
    return hash;
377
174M
}
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
23.0k
{
397
23.0k
    uint32_t hash;
398
23.0k
    int i;
399
400
23.0k
    hash = seed;
401
402
96.2k
    for (i = 0;i < plen; i++) {
403
73.2k
        hash += prefix[i];
404
73.2k
  hash += (hash << 10);
405
73.2k
  hash ^= (hash >> 6);
406
73.2k
    }
407
23.0k
    hash += ':';
408
23.0k
    hash += (hash << 10);
409
23.0k
    hash ^= (hash >> 6);
410
411
155k
    for (i = 0;i < len; i++) {
412
132k
        hash += name[i];
413
132k
  hash += (hash << 10);
414
132k
  hash ^= (hash >> 6);
415
132k
    }
416
23.0k
    hash += (hash << 3);
417
23.0k
    hash ^= (hash >> 11);
418
23.0k
    hash += (hash << 15);
419
420
23.0k
    return hash;
421
23.0k
}
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
449M
xmlDictComputeFastKey(const xmlChar *name, int namelen, int seed) {
432
449M
    unsigned long value = seed;
433
434
449M
    if (name == NULL) return(0);
435
449M
    value += *name;
436
449M
    value <<= 5;
437
449M
    if (namelen > 10) {
438
16.3M
        value += name[namelen - 1];
439
16.3M
        namelen = 10;
440
16.3M
    }
441
449M
    switch (namelen) {
442
24.0M
        case 10: value += name[9];
443
        /* Falls through. */
444
27.6M
        case 9: value += name[8];
445
        /* Falls through. */
446
39.4M
        case 8: value += name[7];
447
        /* Falls through. */
448
58.5M
        case 7: value += name[6];
449
        /* Falls through. */
450
77.8M
        case 6: value += name[5];
451
        /* Falls through. */
452
107M
        case 5: value += name[4];
453
        /* Falls through. */
454
350M
        case 4: value += name[3];
455
        /* Falls through. */
456
381M
        case 3: value += name[2];
457
        /* Falls through. */
458
409M
        case 2: value += name[1];
459
        /* Falls through. */
460
449M
        default: break;
461
449M
    }
462
449M
    return(value);
463
449M
}
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
48.1k
{
477
48.1k
    unsigned long value = seed;
478
479
48.1k
    if (plen == 0)
480
0
  value += 30 * ':';
481
48.1k
    else
482
48.1k
  value += 30 * (*prefix);
483
484
48.1k
    if (len > 10) {
485
3.59k
        int offset = len - (plen + 1 + 1);
486
3.59k
  if (offset < 0)
487
43
      offset = len - (10 + 1);
488
3.59k
  value += name[offset];
489
3.59k
        len = 10;
490
3.59k
  if (plen > 10)
491
98
      plen = 10;
492
3.59k
    }
493
48.1k
    switch (plen) {
494
177
        case 10: value += prefix[9];
495
        /* Falls through. */
496
385
        case 9: value += prefix[8];
497
        /* Falls through. */
498
562
        case 8: value += prefix[7];
499
        /* Falls through. */
500
837
        case 7: value += prefix[6];
501
        /* Falls through. */
502
1.06k
        case 6: value += prefix[5];
503
        /* Falls through. */
504
3.81k
        case 5: value += prefix[4];
505
        /* Falls through. */
506
5.05k
        case 4: value += prefix[3];
507
        /* Falls through. */
508
33.6k
        case 3: value += prefix[2];
509
        /* Falls through. */
510
36.7k
        case 2: value += prefix[1];
511
        /* Falls through. */
512
47.6k
        case 1: value += prefix[0];
513
        /* Falls through. */
514
48.1k
        default: break;
515
48.1k
    }
516
48.1k
    len -= plen;
517
48.1k
    if (len > 0) {
518
35.7k
        value += ':';
519
35.7k
  len--;
520
35.7k
    }
521
48.1k
    switch (len) {
522
0
        case 10: value += name[9];
523
        /* Falls through. */
524
0
        case 9: value += name[8];
525
        /* Falls through. */
526
1.09k
        case 8: value += name[7];
527
        /* Falls through. */
528
1.61k
        case 7: value += name[6];
529
        /* Falls through. */
530
5.71k
        case 6: value += name[5];
531
        /* Falls through. */
532
12.4k
        case 5: value += name[4];
533
        /* Falls through. */
534
14.7k
        case 4: value += name[3];
535
        /* Falls through. */
536
16.9k
        case 3: value += name[2];
537
        /* Falls through. */
538
21.5k
        case 2: value += name[1];
539
        /* Falls through. */
540
27.9k
        case 1: value += name[0];
541
        /* Falls through. */
542
48.1k
        default: break;
543
48.1k
    }
544
48.1k
    return(value);
545
48.1k
}
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
951k
xmlDictCreate(void) {
556
951k
    xmlDictPtr dict;
557
558
951k
    xmlInitParser();
559
560
#ifdef DICT_DEBUG_PATTERNS
561
    fprintf(stderr, "C");
562
#endif
563
564
951k
    dict = xmlMalloc(sizeof(xmlDict));
565
951k
    if (dict) {
566
951k
        dict->ref_counter = 1;
567
951k
        dict->limit = 0;
568
569
951k
        dict->size = MIN_DICT_SIZE;
570
951k
  dict->nbElems = 0;
571
951k
        dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
572
951k
  dict->strings = NULL;
573
951k
  dict->subdict = NULL;
574
951k
        if (dict->dict) {
575
951k
      memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
576
#ifdef DICT_RANDOMIZATION
577
            dict->seed = __xmlRandom();
578
#else
579
951k
            dict->seed = 0;
580
951k
#endif
581
951k
      return(dict);
582
951k
        }
583
0
        xmlFree(dict);
584
0
    }
585
0
    return(NULL);
586
951k
}
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
1.21M
xmlDictReference(xmlDictPtr dict) {
624
1.21M
    if (dict == NULL) return -1;
625
1.14M
    xmlMutexLock(&xmlDictMutex);
626
1.14M
    dict->ref_counter++;
627
1.14M
    xmlMutexUnlock(&xmlDictMutex);
628
1.14M
    return(0);
629
1.21M
}
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
52.5k
xmlDictGrow(xmlDictPtr dict, size_t size) {
642
52.5k
    unsigned long key, okey;
643
52.5k
    size_t oldsize, i;
644
52.5k
    xmlDictEntryPtr iter, next;
645
52.5k
    struct _xmlDictEntry *olddict;
646
#ifdef DEBUG_GROW
647
    unsigned long nbElem = 0;
648
#endif
649
52.5k
    int ret = 0;
650
52.5k
    int keep_keys = 1;
651
652
52.5k
    if (dict == NULL)
653
0
  return(-1);
654
52.5k
    if (size < 8)
655
0
        return(-1);
656
52.5k
    if (size > 8 * 2048)
657
0
  return(-1);
658
659
#ifdef DICT_DEBUG_PATTERNS
660
    fprintf(stderr, "*");
661
#endif
662
663
52.5k
    oldsize = dict->size;
664
52.5k
    olddict = dict->dict;
665
52.5k
    if (olddict == NULL)
666
0
        return(-1);
667
52.5k
    if (oldsize == MIN_DICT_SIZE)
668
50.7k
        keep_keys = 0;
669
670
52.5k
    dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
671
52.5k
    if (dict->dict == NULL) {
672
0
  dict->dict = olddict;
673
0
  return(-1);
674
0
    }
675
52.5k
    memset(dict->dict, 0, size * sizeof(xmlDictEntry));
676
52.5k
    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
7.94M
    for (i = 0; i < oldsize; i++) {
685
7.88M
  if (olddict[i].valid == 0)
686
1.98M
      continue;
687
688
5.90M
  if (keep_keys)
689
611k
      okey = olddict[i].okey;
690
5.29M
  else
691
5.29M
      okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
692
5.90M
  key = okey % dict->size;
693
694
5.90M
  if (dict->dict[key].valid == 0) {
695
5.55M
      memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
696
5.55M
      dict->dict[key].next = NULL;
697
5.55M
      dict->dict[key].okey = okey;
698
5.55M
  } else {
699
348k
      xmlDictEntryPtr entry;
700
701
348k
      entry = xmlMalloc(sizeof(xmlDictEntry));
702
348k
      if (entry != NULL) {
703
348k
    entry->name = olddict[i].name;
704
348k
    entry->len = olddict[i].len;
705
348k
    entry->okey = okey;
706
348k
    entry->next = dict->dict[key].next;
707
348k
    entry->valid = 1;
708
348k
    dict->dict[key].next = entry;
709
348k
      } 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
348k
  }
717
#ifdef DEBUG_GROW
718
  nbElem++;
719
#endif
720
5.90M
    }
721
722
7.94M
    for (i = 0; i < oldsize; i++) {
723
7.88M
  iter = olddict[i].next;
724
14.3M
  while (iter) {
725
6.43M
      next = iter->next;
726
727
      /*
728
       * put back the entry in the new dict
729
       */
730
731
6.43M
      if (keep_keys)
732
171k
    okey = iter->okey;
733
6.26M
      else
734
6.26M
    okey = xmlDictComputeKey(dict, iter->name, iter->len);
735
6.43M
      key = okey % dict->size;
736
6.43M
      if (dict->dict[key].valid == 0) {
737
5.07M
    memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
738
5.07M
    dict->dict[key].next = NULL;
739
5.07M
    dict->dict[key].valid = 1;
740
5.07M
    dict->dict[key].okey = okey;
741
5.07M
    xmlFree(iter);
742
5.07M
      } else {
743
1.36M
    iter->next = dict->dict[key].next;
744
1.36M
    iter->okey = okey;
745
1.36M
    dict->dict[key].next = iter;
746
1.36M
      }
747
748
#ifdef DEBUG_GROW
749
      nbElem++;
750
#endif
751
752
6.43M
      iter = next;
753
6.43M
  }
754
7.88M
    }
755
756
52.5k
    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
52.5k
    return(ret);
764
52.5k
}
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.09M
xmlDictFree(xmlDictPtr dict) {
775
2.09M
    size_t i;
776
2.09M
    xmlDictEntryPtr iter;
777
2.09M
    xmlDictEntryPtr next;
778
2.09M
    int inside_dict = 0;
779
2.09M
    xmlDictStringsPtr pool, nextp;
780
781
2.09M
    if (dict == NULL)
782
0
  return;
783
784
    /* decrement the counter, it may be shared by a parser and docs */
785
2.09M
    xmlMutexLock(&xmlDictMutex);
786
2.09M
    dict->ref_counter--;
787
2.09M
    if (dict->ref_counter > 0) {
788
1.14M
        xmlMutexUnlock(&xmlDictMutex);
789
1.14M
        return;
790
1.14M
    }
791
792
951k
    xmlMutexUnlock(&xmlDictMutex);
793
794
951k
    if (dict->subdict != NULL) {
795
0
        xmlDictFree(dict->subdict);
796
0
    }
797
798
951k
    if (dict->dict) {
799
88.0M
  for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
800
87.0M
      iter = &(dict->dict[i]);
801
87.0M
      if (iter->valid == 0)
802
64.5M
    continue;
803
22.4M
      inside_dict = 1;
804
53.5M
      while (iter) {
805
31.0M
    next = iter->next;
806
31.0M
    if (!inside_dict)
807
8.53M
        xmlFree(iter);
808
31.0M
    dict->nbElems--;
809
31.0M
    inside_dict = 0;
810
31.0M
    iter = next;
811
31.0M
      }
812
22.4M
  }
813
951k
  xmlFree(dict->dict);
814
951k
    }
815
951k
    pool = dict->strings;
816
1.49M
    while (pool != NULL) {
817
546k
        nextp = pool->next;
818
546k
  xmlFree(pool);
819
546k
  pool = nextp;
820
546k
    }
821
951k
    xmlFree(dict);
822
951k
}
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
630M
xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
836
630M
    unsigned long key, okey, nbi = 0;
837
630M
    xmlDictEntryPtr entry;
838
630M
    xmlDictEntryPtr insert;
839
630M
    const xmlChar *ret;
840
630M
    unsigned int l;
841
842
630M
    if ((dict == NULL) || (name == NULL))
843
18.7M
  return(NULL);
844
845
611M
    if (len < 0)
846
100M
        l = strlen((const char *) name);
847
511M
    else
848
511M
        l = len;
849
850
611M
    if (((dict->limit > 0) && (l >= dict->limit)) ||
851
611M
        (l > INT_MAX / 2))
852
0
        return(NULL);
853
854
    /*
855
     * Check for duplicate and insertion location.
856
     */
857
611M
    okey = xmlDictComputeKey(dict, name, l);
858
611M
    key = okey % dict->size;
859
611M
    if (dict->dict[key].valid == 0) {
860
17.7M
  insert = NULL;
861
594M
    } else {
862
778M
  for (insert = &(dict->dict[key]); insert->next != NULL;
863
594M
       insert = insert->next) {
864
275M
#ifdef __GNUC__
865
275M
      if ((insert->okey == okey) && (insert->len == l)) {
866
93.7M
    if (!memcmp(insert->name, name, l))
867
91.1M
        return(insert->name);
868
93.7M
      }
869
#else
870
      if ((insert->okey == okey) && (insert->len == l) &&
871
          (!xmlStrncmp(insert->name, name, l)))
872
    return(insert->name);
873
#endif
874
184M
      nbi++;
875
184M
  }
876
502M
#ifdef __GNUC__
877
502M
  if ((insert->okey == okey) && (insert->len == l)) {
878
490M
      if (!memcmp(insert->name, name, l))
879
489M
    return(insert->name);
880
490M
  }
881
#else
882
  if ((insert->okey == okey) && (insert->len == l) &&
883
      (!xmlStrncmp(insert->name, name, l)))
884
      return(insert->name);
885
#endif
886
502M
    }
887
888
30.9M
    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
30.9M
    ret = xmlDictAddString(dict, name, l);
933
30.9M
    if (ret == NULL)
934
0
        return(NULL);
935
30.9M
    if (insert == NULL) {
936
17.7M
  entry = &(dict->dict[key]);
937
17.7M
    } else {
938
13.2M
  entry = xmlMalloc(sizeof(xmlDictEntry));
939
13.2M
  if (entry == NULL)
940
0
       return(NULL);
941
13.2M
    }
942
30.9M
    entry->name = ret;
943
30.9M
    entry->len = l;
944
30.9M
    entry->next = NULL;
945
30.9M
    entry->valid = 1;
946
30.9M
    entry->okey = okey;
947
948
949
30.9M
    if (insert != NULL)
950
13.2M
  insert->next = entry;
951
952
30.9M
    dict->nbElems++;
953
954
30.9M
    if ((nbi > MAX_HASH_LEN) &&
955
30.9M
        (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
956
52.3k
  if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
957
0
      return(NULL);
958
52.3k
    }
959
    /* Note that entry may have been freed at this point by xmlDictGrow */
960
961
30.9M
    return(ret);
962
30.9M
}
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
71.1k
xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
1082
71.1k
    unsigned long okey, key, nbi = 0;
1083
71.1k
    xmlDictEntryPtr entry;
1084
71.1k
    xmlDictEntryPtr insert;
1085
71.1k
    const xmlChar *ret;
1086
71.1k
    unsigned int len, plen, l;
1087
1088
71.1k
    if ((dict == NULL) || (name == NULL))
1089
0
  return(NULL);
1090
71.1k
    if (prefix == NULL)
1091
0
        return(xmlDictLookup(dict, name, -1));
1092
1093
71.1k
    l = len = strlen((const char *) name);
1094
71.1k
    plen = strlen((const char *) prefix);
1095
71.1k
    len += 1 + plen;
1096
1097
    /*
1098
     * Check for duplicate and insertion location.
1099
     */
1100
71.1k
    okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
1101
71.1k
    key = okey % dict->size;
1102
71.1k
    if (dict->dict[key].valid == 0) {
1103
26.7k
  insert = NULL;
1104
44.3k
    } else {
1105
60.4k
  for (insert = &(dict->dict[key]); insert->next != NULL;
1106
44.3k
       insert = insert->next) {
1107
26.1k
      if ((insert->okey == okey) && (insert->len == len) &&
1108
26.1k
          (xmlStrQEqual(prefix, name, insert->name)))
1109
10.0k
    return(insert->name);
1110
16.1k
      nbi++;
1111
16.1k
  }
1112
34.3k
  if ((insert->okey == okey) && (insert->len == len) &&
1113
34.3k
      (xmlStrQEqual(prefix, name, insert->name)))
1114
26.2k
      return(insert->name);
1115
34.3k
    }
1116
1117
34.9k
    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
34.9k
    ret = xmlDictAddQString(dict, prefix, plen, name, l);
1147
34.9k
    if (ret == NULL)
1148
0
        return(NULL);
1149
34.9k
    if (insert == NULL) {
1150
26.7k
  entry = &(dict->dict[key]);
1151
26.7k
    } else {
1152
8.12k
  entry = xmlMalloc(sizeof(xmlDictEntry));
1153
8.12k
  if (entry == NULL)
1154
0
       return(NULL);
1155
8.12k
    }
1156
34.9k
    entry->name = ret;
1157
34.9k
    entry->len = len;
1158
34.9k
    entry->next = NULL;
1159
34.9k
    entry->valid = 1;
1160
34.9k
    entry->okey = okey;
1161
1162
34.9k
    if (insert != NULL)
1163
8.12k
  insert->next = entry;
1164
1165
34.9k
    dict->nbElems++;
1166
1167
34.9k
    if ((nbi > MAX_HASH_LEN) &&
1168
34.9k
        (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
1169
250
  xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
1170
    /* Note that entry may have been freed at this point by xmlDictGrow */
1171
1172
34.9k
    return(ret);
1173
34.9k
}
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
560M
xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
1187
560M
    xmlDictStringsPtr pool;
1188
1189
560M
    if ((dict == NULL) || (str == NULL))
1190
0
  return(-1);
1191
560M
    pool = dict->strings;
1192
1.13G
    while (pool != NULL) {
1193
895M
        if ((str >= &pool->array[0]) && (str <= pool->free))
1194
325M
      return(1);
1195
570M
  pool = pool->next;
1196
570M
    }
1197
234M
    if (dict->subdict)
1198
0
        return(xmlDictOwns(dict->subdict, str));
1199
234M
    return(0);
1200
234M
}
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.00M
xmlDictSetLimit(xmlDictPtr dict, size_t limit) {
1232
1.00M
    size_t ret;
1233
1234
1.00M
    if (dict == NULL)
1235
0
  return(0);
1236
1.00M
    ret = dict->limit;
1237
1.00M
    dict->limit = limit;
1238
1.00M
    return(ret);
1239
1.00M
}
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