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