Coverage Report

Created: 2023-09-24 16:02

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