Merge branch 'v4-0-test' of ssh://git.samba.org/data/git/samba into v4-0-trivial
[samba.git] / source4 / lib / talloc / talloc.c
1 /* 
2    Samba Unix SMB/CIFS implementation.
3
4    Samba trivial allocation library - new interface
5
6    NOTE: Please read talloc_guide.txt for full documentation
7
8    Copyright (C) Andrew Tridgell 2004
9    Copyright (C) Stefan Metzmacher 2006
10    
11      ** NOTE! The following LGPL license applies to the talloc
12      ** library. This does NOT imply that all of Samba is released
13      ** under the LGPL
14    
15    This library is free software; you can redistribute it and/or
16    modify it under the terms of the GNU Lesser General Public
17    License as published by the Free Software Foundation; either
18    version 3 of the License, or (at your option) any later version.
19
20    This library is distributed in the hope that it will be useful,
21    but WITHOUT ANY WARRANTY; without even the implied warranty of
22    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
23    Lesser General Public License for more details.
24
25    You should have received a copy of the GNU Lesser General Public
26    License along with this library; if not, see <http://www.gnu.org/licenses/>.
27 */
28
29 /*
30   inspired by http://swapped.cc/halloc/
31 */
32
33 #ifdef _SAMBA_BUILD_
34 #include "version.h"
35 #if (SAMBA_VERSION_MAJOR<4)
36 #include "includes.h"
37 /* This is to circumvent SAMBA3's paranoid malloc checker. Here in this file
38  * we trust ourselves... */
39 #ifdef malloc
40 #undef malloc
41 #endif
42 #ifdef realloc
43 #undef realloc
44 #endif
45 #define _TALLOC_SAMBA3
46 #endif /* (SAMBA_VERSION_MAJOR<4) */
47 #endif /* _SAMBA_BUILD_ */
48
49 #ifndef _TALLOC_SAMBA3
50 #include "replace.h"
51 #include "talloc.h"
52 #endif /* not _TALLOC_SAMBA3 */
53
54 /* use this to force every realloc to change the pointer, to stress test
55    code that might not cope */
56 #define ALWAYS_REALLOC 0
57
58
59 #define MAX_TALLOC_SIZE 0x10000000
60 #define TALLOC_MAGIC 0xe814ec70
61 #define TALLOC_FLAG_FREE 0x01
62 #define TALLOC_FLAG_LOOP 0x02
63 #define TALLOC_MAGIC_REFERENCE ((const char *)1)
64
65 /* by default we abort when given a bad pointer (such as when talloc_free() is called 
66    on a pointer that came from malloc() */
67 #ifndef TALLOC_ABORT
68 #define TALLOC_ABORT(reason) abort()
69 #endif
70
71 #ifndef discard_const_p
72 #if defined(__intptr_t_defined) || defined(HAVE_INTPTR_T)
73 # define discard_const_p(type, ptr) ((type *)((intptr_t)(ptr)))
74 #else
75 # define discard_const_p(type, ptr) ((type *)(ptr))
76 #endif
77 #endif
78
79 /* these macros gain us a few percent of speed on gcc */
80 #if (__GNUC__ >= 3)
81 /* the strange !! is to ensure that __builtin_expect() takes either 0 or 1
82    as its first argument */
83 #define likely(x)   __builtin_expect(!!(x), 1)
84 #define unlikely(x) __builtin_expect(!!(x), 0)
85 #else
86 #define likely(x) x
87 #define unlikely(x) x
88 #endif
89
90 /* this null_context is only used if talloc_enable_leak_report() or
91    talloc_enable_leak_report_full() is called, otherwise it remains
92    NULL
93 */
94 static void *null_context;
95 static void *autofree_context;
96
97 struct talloc_reference_handle {
98         struct talloc_reference_handle *next, *prev;
99         void *ptr;
100 };
101
102 typedef int (*talloc_destructor_t)(void *);
103
104 struct talloc_chunk {
105         struct talloc_chunk *next, *prev;
106         struct talloc_chunk *parent, *child;
107         struct talloc_reference_handle *refs;
108         talloc_destructor_t destructor;
109         const char *name;
110         size_t size;
111         unsigned flags;
112 };
113
114 /* 16 byte alignment seems to keep everyone happy */
115 #define TC_HDR_SIZE ((sizeof(struct talloc_chunk)+15)&~15)
116 #define TC_PTR_FROM_CHUNK(tc) ((void *)(TC_HDR_SIZE + (char*)tc))
117
118 static void talloc_abort_double_free(void)
119 {
120         TALLOC_ABORT("Bad talloc magic value - double free"); 
121 }
122
123 static void talloc_abort_unknown_value(void)
124 {
125         TALLOC_ABORT("Bad talloc magic value - unknown value"); 
126 }
127
128 /* panic if we get a bad magic value */
129 static inline struct talloc_chunk *talloc_chunk_from_ptr(const void *ptr)
130 {
131         const char *pp = (const char *)ptr;
132         struct talloc_chunk *tc = discard_const_p(struct talloc_chunk, pp - TC_HDR_SIZE);
133         if (unlikely((tc->flags & (TALLOC_FLAG_FREE | ~0xF)) != TALLOC_MAGIC)) { 
134                 if (tc->flags & TALLOC_FLAG_FREE) {
135                         talloc_abort_double_free();
136                 } else {
137                         talloc_abort_unknown_value();
138                 }
139         }
140         return tc;
141 }
142
143 /* hook into the front of the list */
144 #define _TLIST_ADD(list, p) \
145 do { \
146         if (!(list)) { \
147                 (list) = (p); \
148                 (p)->next = (p)->prev = NULL; \
149         } else { \
150                 (list)->prev = (p); \
151                 (p)->next = (list); \
152                 (p)->prev = NULL; \
153                 (list) = (p); \
154         }\
155 } while (0)
156
157 /* remove an element from a list - element doesn't have to be in list. */
158 #define _TLIST_REMOVE(list, p) \
159 do { \
160         if ((p) == (list)) { \
161                 (list) = (p)->next; \
162                 if (list) (list)->prev = NULL; \
163         } else { \
164                 if ((p)->prev) (p)->prev->next = (p)->next; \
165                 if ((p)->next) (p)->next->prev = (p)->prev; \
166         } \
167         if ((p) && ((p) != (list))) (p)->next = (p)->prev = NULL; \
168 } while (0)
169
170
171 /*
172   return the parent chunk of a pointer
173 */
174 static inline struct talloc_chunk *talloc_parent_chunk(const void *ptr)
175 {
176         struct talloc_chunk *tc;
177
178         if (unlikely(ptr == NULL)) {
179                 return NULL;
180         }
181
182         tc = talloc_chunk_from_ptr(ptr);
183         while (tc->prev) tc=tc->prev;
184
185         return tc->parent;
186 }
187
188 void *talloc_parent(const void *ptr)
189 {
190         struct talloc_chunk *tc = talloc_parent_chunk(ptr);
191         return tc? TC_PTR_FROM_CHUNK(tc) : NULL;
192 }
193
194 /*
195   find parents name
196 */
197 const char *talloc_parent_name(const void *ptr)
198 {
199         struct talloc_chunk *tc = talloc_parent_chunk(ptr);
200         return tc? tc->name : NULL;
201 }
202
203 /* 
204    Allocate a bit of memory as a child of an existing pointer
205 */
206 static inline void *__talloc(const void *context, size_t size)
207 {
208         struct talloc_chunk *tc;
209
210         if (unlikely(context == NULL)) {
211                 context = null_context;
212         }
213
214         if (unlikely(size >= MAX_TALLOC_SIZE)) {
215                 return NULL;
216         }
217
218         tc = (struct talloc_chunk *)malloc(TC_HDR_SIZE+size);
219         if (unlikely(tc == NULL)) return NULL;
220
221         tc->size = size;
222         tc->flags = TALLOC_MAGIC;
223         tc->destructor = NULL;
224         tc->child = NULL;
225         tc->name = NULL;
226         tc->refs = NULL;
227
228         if (likely(context)) {
229                 struct talloc_chunk *parent = talloc_chunk_from_ptr(context);
230
231                 if (parent->child) {
232                         parent->child->parent = NULL;
233                         tc->next = parent->child;
234                         tc->next->prev = tc;
235                 } else {
236                         tc->next = NULL;
237                 }
238                 tc->parent = parent;
239                 tc->prev = NULL;
240                 parent->child = tc;
241         } else {
242                 tc->next = tc->prev = tc->parent = NULL;
243         }
244
245         return TC_PTR_FROM_CHUNK(tc);
246 }
247
248 /*
249   setup a destructor to be called on free of a pointer
250   the destructor should return 0 on success, or -1 on failure.
251   if the destructor fails then the free is failed, and the memory can
252   be continued to be used
253 */
254 void _talloc_set_destructor(const void *ptr, int (*destructor)(void *))
255 {
256         struct talloc_chunk *tc = talloc_chunk_from_ptr(ptr);
257         tc->destructor = destructor;
258 }
259
260 /*
261   increase the reference count on a piece of memory. 
262 */
263 int talloc_increase_ref_count(const void *ptr)
264 {
265         if (unlikely(!talloc_reference(null_context, ptr))) {
266                 return -1;
267         }
268         return 0;
269 }
270
271 /*
272   helper for talloc_reference()
273
274   this is referenced by a function pointer and should not be inline
275 */
276 static int talloc_reference_destructor(struct talloc_reference_handle *handle)
277 {
278         struct talloc_chunk *ptr_tc = talloc_chunk_from_ptr(handle->ptr);
279         _TLIST_REMOVE(ptr_tc->refs, handle);
280         return 0;
281 }
282
283 /*
284    more efficient way to add a name to a pointer - the name must point to a 
285    true string constant
286 */
287 static inline void _talloc_set_name_const(const void *ptr, const char *name)
288 {
289         struct talloc_chunk *tc = talloc_chunk_from_ptr(ptr);
290         tc->name = name;
291 }
292
293 /*
294   internal talloc_named_const()
295 */
296 static inline void *_talloc_named_const(const void *context, size_t size, const char *name)
297 {
298         void *ptr;
299
300         ptr = __talloc(context, size);
301         if (unlikely(ptr == NULL)) {
302                 return NULL;
303         }
304
305         _talloc_set_name_const(ptr, name);
306
307         return ptr;
308 }
309
310 /*
311   make a secondary reference to a pointer, hanging off the given context.
312   the pointer remains valid until both the original caller and this given
313   context are freed.
314   
315   the major use for this is when two different structures need to reference the 
316   same underlying data, and you want to be able to free the two instances separately,
317   and in either order
318 */
319 void *_talloc_reference(const void *context, const void *ptr)
320 {
321         struct talloc_chunk *tc;
322         struct talloc_reference_handle *handle;
323         if (unlikely(ptr == NULL)) return NULL;
324
325         tc = talloc_chunk_from_ptr(ptr);
326         handle = (struct talloc_reference_handle *)_talloc_named_const(context,
327                                                    sizeof(struct talloc_reference_handle),
328                                                    TALLOC_MAGIC_REFERENCE);
329         if (unlikely(handle == NULL)) return NULL;
330
331         /* note that we hang the destructor off the handle, not the
332            main context as that allows the caller to still setup their
333            own destructor on the context if they want to */
334         talloc_set_destructor(handle, talloc_reference_destructor);
335         handle->ptr = discard_const_p(void, ptr);
336         _TLIST_ADD(tc->refs, handle);
337         return handle->ptr;
338 }
339
340
341 /* 
342    internal talloc_free call
343 */
344 static inline int _talloc_free(void *ptr)
345 {
346         struct talloc_chunk *tc;
347
348         if (unlikely(ptr == NULL)) {
349                 return -1;
350         }
351
352         tc = talloc_chunk_from_ptr(ptr);
353
354         if (unlikely(tc->refs)) {
355                 int is_child;
356                 /* check this is a reference from a child or grantchild
357                  * back to it's parent or grantparent
358                  *
359                  * in that case we need to remove the reference and
360                  * call another instance of talloc_free() on the current
361                  * pointer.
362                  */
363                 is_child = talloc_is_parent(tc->refs, ptr);
364                 _talloc_free(tc->refs);
365                 if (is_child) {
366                         return _talloc_free(ptr);
367                 }
368                 return -1;
369         }
370
371         if (unlikely(tc->flags & TALLOC_FLAG_LOOP)) {
372                 /* we have a free loop - stop looping */
373                 return 0;
374         }
375
376         if (unlikely(tc->destructor)) {
377                 talloc_destructor_t d = tc->destructor;
378                 if (d == (talloc_destructor_t)-1) {
379                         return -1;
380                 }
381                 tc->destructor = (talloc_destructor_t)-1;
382                 if (d(ptr) == -1) {
383                         tc->destructor = d;
384                         return -1;
385                 }
386                 tc->destructor = NULL;
387         }
388
389         if (tc->parent) {
390                 _TLIST_REMOVE(tc->parent->child, tc);
391                 if (tc->parent->child) {
392                         tc->parent->child->parent = tc->parent;
393                 }
394         } else {
395                 if (tc->prev) tc->prev->next = tc->next;
396                 if (tc->next) tc->next->prev = tc->prev;
397         }
398
399         tc->flags |= TALLOC_FLAG_LOOP;
400
401         while (tc->child) {
402                 /* we need to work out who will own an abandoned child
403                    if it cannot be freed. In priority order, the first
404                    choice is owner of any remaining reference to this
405                    pointer, the second choice is our parent, and the
406                    final choice is the null context. */
407                 void *child = TC_PTR_FROM_CHUNK(tc->child);
408                 const void *new_parent = null_context;
409                 if (unlikely(tc->child->refs)) {
410                         struct talloc_chunk *p = talloc_parent_chunk(tc->child->refs);
411                         if (p) new_parent = TC_PTR_FROM_CHUNK(p);
412                 }
413                 if (unlikely(_talloc_free(child) == -1)) {
414                         if (new_parent == null_context) {
415                                 struct talloc_chunk *p = talloc_parent_chunk(ptr);
416                                 if (p) new_parent = TC_PTR_FROM_CHUNK(p);
417                         }
418                         talloc_steal(new_parent, child);
419                 }
420         }
421
422         tc->flags |= TALLOC_FLAG_FREE;
423         free(tc);
424         return 0;
425 }
426
427 /* 
428    move a lump of memory from one talloc context to another return the
429    ptr on success, or NULL if it could not be transferred.
430    passing NULL as ptr will always return NULL with no side effects.
431 */
432 void *_talloc_steal(const void *new_ctx, const void *ptr)
433 {
434         struct talloc_chunk *tc, *new_tc;
435
436         if (unlikely(!ptr)) {
437                 return NULL;
438         }
439
440         if (unlikely(new_ctx == NULL)) {
441                 new_ctx = null_context;
442         }
443
444         tc = talloc_chunk_from_ptr(ptr);
445
446         if (unlikely(new_ctx == NULL)) {
447                 if (tc->parent) {
448                         _TLIST_REMOVE(tc->parent->child, tc);
449                         if (tc->parent->child) {
450                                 tc->parent->child->parent = tc->parent;
451                         }
452                 } else {
453                         if (tc->prev) tc->prev->next = tc->next;
454                         if (tc->next) tc->next->prev = tc->prev;
455                 }
456                 
457                 tc->parent = tc->next = tc->prev = NULL;
458                 return discard_const_p(void, ptr);
459         }
460
461         new_tc = talloc_chunk_from_ptr(new_ctx);
462
463         if (unlikely(tc == new_tc || tc->parent == new_tc)) {
464                 return discard_const_p(void, ptr);
465         }
466
467         if (tc->parent) {
468                 _TLIST_REMOVE(tc->parent->child, tc);
469                 if (tc->parent->child) {
470                         tc->parent->child->parent = tc->parent;
471                 }
472         } else {
473                 if (tc->prev) tc->prev->next = tc->next;
474                 if (tc->next) tc->next->prev = tc->prev;
475         }
476
477         tc->parent = new_tc;
478         if (new_tc->child) new_tc->child->parent = NULL;
479         _TLIST_ADD(new_tc->child, tc);
480
481         return discard_const_p(void, ptr);
482 }
483
484
485
486 /*
487   remove a secondary reference to a pointer. This undo's what
488   talloc_reference() has done. The context and pointer arguments
489   must match those given to a talloc_reference()
490 */
491 static inline int talloc_unreference(const void *context, const void *ptr)
492 {
493         struct talloc_chunk *tc = talloc_chunk_from_ptr(ptr);
494         struct talloc_reference_handle *h;
495
496         if (unlikely(context == NULL)) {
497                 context = null_context;
498         }
499
500         for (h=tc->refs;h;h=h->next) {
501                 struct talloc_chunk *p = talloc_parent_chunk(h);
502                 if (p == NULL) {
503                         if (context == NULL) break;
504                 } else if (TC_PTR_FROM_CHUNK(p) == context) {
505                         break;
506                 }
507         }
508         if (h == NULL) {
509                 return -1;
510         }
511
512         return _talloc_free(h);
513 }
514
515 /*
516   remove a specific parent context from a pointer. This is a more
517   controlled varient of talloc_free()
518 */
519 int talloc_unlink(const void *context, void *ptr)
520 {
521         struct talloc_chunk *tc_p, *new_p;
522         void *new_parent;
523
524         if (ptr == NULL) {
525                 return -1;
526         }
527
528         if (context == NULL) {
529                 context = null_context;
530         }
531
532         if (talloc_unreference(context, ptr) == 0) {
533                 return 0;
534         }
535
536         if (context == NULL) {
537                 if (talloc_parent_chunk(ptr) != NULL) {
538                         return -1;
539                 }
540         } else {
541                 if (talloc_chunk_from_ptr(context) != talloc_parent_chunk(ptr)) {
542                         return -1;
543                 }
544         }
545         
546         tc_p = talloc_chunk_from_ptr(ptr);
547
548         if (tc_p->refs == NULL) {
549                 return _talloc_free(ptr);
550         }
551
552         new_p = talloc_parent_chunk(tc_p->refs);
553         if (new_p) {
554                 new_parent = TC_PTR_FROM_CHUNK(new_p);
555         } else {
556                 new_parent = NULL;
557         }
558
559         if (talloc_unreference(new_parent, ptr) != 0) {
560                 return -1;
561         }
562
563         talloc_steal(new_parent, ptr);
564
565         return 0;
566 }
567
568 /*
569   add a name to an existing pointer - va_list version
570 */
571 static inline const char *talloc_set_name_v(const void *ptr, const char *fmt, va_list ap) PRINTF_ATTRIBUTE(2,0);
572
573 static inline const char *talloc_set_name_v(const void *ptr, const char *fmt, va_list ap)
574 {
575         struct talloc_chunk *tc = talloc_chunk_from_ptr(ptr);
576         tc->name = talloc_vasprintf(ptr, fmt, ap);
577         if (likely(tc->name)) {
578                 _talloc_set_name_const(tc->name, ".name");
579         }
580         return tc->name;
581 }
582
583 /*
584   add a name to an existing pointer
585 */
586 const char *talloc_set_name(const void *ptr, const char *fmt, ...)
587 {
588         const char *name;
589         va_list ap;
590         va_start(ap, fmt);
591         name = talloc_set_name_v(ptr, fmt, ap);
592         va_end(ap);
593         return name;
594 }
595
596
597 /*
598   create a named talloc pointer. Any talloc pointer can be named, and
599   talloc_named() operates just like talloc() except that it allows you
600   to name the pointer.
601 */
602 void *talloc_named(const void *context, size_t size, const char *fmt, ...)
603 {
604         va_list ap;
605         void *ptr;
606         const char *name;
607
608         ptr = __talloc(context, size);
609         if (unlikely(ptr == NULL)) return NULL;
610
611         va_start(ap, fmt);
612         name = talloc_set_name_v(ptr, fmt, ap);
613         va_end(ap);
614
615         if (unlikely(name == NULL)) {
616                 _talloc_free(ptr);
617                 return NULL;
618         }
619
620         return ptr;
621 }
622
623 /*
624   return the name of a talloc ptr, or "UNNAMED"
625 */
626 const char *talloc_get_name(const void *ptr)
627 {
628         struct talloc_chunk *tc = talloc_chunk_from_ptr(ptr);
629         if (unlikely(tc->name == TALLOC_MAGIC_REFERENCE)) {
630                 return ".reference";
631         }
632         if (likely(tc->name)) {
633                 return tc->name;
634         }
635         return "UNNAMED";
636 }
637
638
639 /*
640   check if a pointer has the given name. If it does, return the pointer,
641   otherwise return NULL
642 */
643 void *talloc_check_name(const void *ptr, const char *name)
644 {
645         const char *pname;
646         if (unlikely(ptr == NULL)) return NULL;
647         pname = talloc_get_name(ptr);
648         if (likely(pname == name || strcmp(pname, name) == 0)) {
649                 return discard_const_p(void, ptr);
650         }
651         return NULL;
652 }
653
654
655 /*
656   this is for compatibility with older versions of talloc
657 */
658 void *talloc_init(const char *fmt, ...)
659 {
660         va_list ap;
661         void *ptr;
662         const char *name;
663
664         /*
665          * samba3 expects talloc_report_depth_cb(NULL, ...)
666          * reports all talloc'ed memory, so we need to enable
667          * null_tracking
668          */
669         talloc_enable_null_tracking();
670
671         ptr = __talloc(NULL, 0);
672         if (unlikely(ptr == NULL)) return NULL;
673
674         va_start(ap, fmt);
675         name = talloc_set_name_v(ptr, fmt, ap);
676         va_end(ap);
677
678         if (unlikely(name == NULL)) {
679                 _talloc_free(ptr);
680                 return NULL;
681         }
682
683         return ptr;
684 }
685
686 /*
687   this is a replacement for the Samba3 talloc_destroy_pool functionality. It
688   should probably not be used in new code. It's in here to keep the talloc
689   code consistent across Samba 3 and 4.
690 */
691 void talloc_free_children(void *ptr)
692 {
693         struct talloc_chunk *tc;
694
695         if (unlikely(ptr == NULL)) {
696                 return;
697         }
698
699         tc = talloc_chunk_from_ptr(ptr);
700
701         while (tc->child) {
702                 /* we need to work out who will own an abandoned child
703                    if it cannot be freed. In priority order, the first
704                    choice is owner of any remaining reference to this
705                    pointer, the second choice is our parent, and the
706                    final choice is the null context. */
707                 void *child = TC_PTR_FROM_CHUNK(tc->child);
708                 const void *new_parent = null_context;
709                 if (unlikely(tc->child->refs)) {
710                         struct talloc_chunk *p = talloc_parent_chunk(tc->child->refs);
711                         if (p) new_parent = TC_PTR_FROM_CHUNK(p);
712                 }
713                 if (unlikely(_talloc_free(child) == -1)) {
714                         if (new_parent == null_context) {
715                                 struct talloc_chunk *p = talloc_parent_chunk(ptr);
716                                 if (p) new_parent = TC_PTR_FROM_CHUNK(p);
717                         }
718                         talloc_steal(new_parent, child);
719                 }
720         }
721 }
722
723 /* 
724    Allocate a bit of memory as a child of an existing pointer
725 */
726 void *_talloc(const void *context, size_t size)
727 {
728         return __talloc(context, size);
729 }
730
731 /*
732   externally callable talloc_set_name_const()
733 */
734 void talloc_set_name_const(const void *ptr, const char *name)
735 {
736         _talloc_set_name_const(ptr, name);
737 }
738
739 /*
740   create a named talloc pointer. Any talloc pointer can be named, and
741   talloc_named() operates just like talloc() except that it allows you
742   to name the pointer.
743 */
744 void *talloc_named_const(const void *context, size_t size, const char *name)
745 {
746         return _talloc_named_const(context, size, name);
747 }
748
749 /* 
750    free a talloc pointer. This also frees all child pointers of this 
751    pointer recursively
752
753    return 0 if the memory is actually freed, otherwise -1. The memory
754    will not be freed if the ref_count is > 1 or the destructor (if
755    any) returns non-zero
756 */
757 int talloc_free(void *ptr)
758 {
759         return _talloc_free(ptr);
760 }
761
762
763
764 /*
765   A talloc version of realloc. The context argument is only used if
766   ptr is NULL
767 */
768 void *_talloc_realloc(const void *context, void *ptr, size_t size, const char *name)
769 {
770         struct talloc_chunk *tc;
771         void *new_ptr;
772
773         /* size zero is equivalent to free() */
774         if (unlikely(size == 0)) {
775                 _talloc_free(ptr);
776                 return NULL;
777         }
778
779         if (unlikely(size >= MAX_TALLOC_SIZE)) {
780                 return NULL;
781         }
782
783         /* realloc(NULL) is equivalent to malloc() */
784         if (ptr == NULL) {
785                 return _talloc_named_const(context, size, name);
786         }
787
788         tc = talloc_chunk_from_ptr(ptr);
789
790         /* don't allow realloc on referenced pointers */
791         if (unlikely(tc->refs)) {
792                 return NULL;
793         }
794
795         /* by resetting magic we catch users of the old memory */
796         tc->flags |= TALLOC_FLAG_FREE;
797
798 #if ALWAYS_REALLOC
799         new_ptr = malloc(size + TC_HDR_SIZE);
800         if (new_ptr) {
801                 memcpy(new_ptr, tc, tc->size + TC_HDR_SIZE);
802                 free(tc);
803         }
804 #else
805         new_ptr = realloc(tc, size + TC_HDR_SIZE);
806 #endif
807         if (unlikely(!new_ptr)) {       
808                 tc->flags &= ~TALLOC_FLAG_FREE; 
809                 return NULL; 
810         }
811
812         tc = (struct talloc_chunk *)new_ptr;
813         tc->flags &= ~TALLOC_FLAG_FREE; 
814         if (tc->parent) {
815                 tc->parent->child = tc;
816         }
817         if (tc->child) {
818                 tc->child->parent = tc;
819         }
820
821         if (tc->prev) {
822                 tc->prev->next = tc;
823         }
824         if (tc->next) {
825                 tc->next->prev = tc;
826         }
827
828         tc->size = size;
829         _talloc_set_name_const(TC_PTR_FROM_CHUNK(tc), name);
830
831         return TC_PTR_FROM_CHUNK(tc);
832 }
833
834 /*
835   a wrapper around talloc_steal() for situations where you are moving a pointer
836   between two structures, and want the old pointer to be set to NULL
837 */
838 void *_talloc_move(const void *new_ctx, const void *_pptr)
839 {
840         const void **pptr = discard_const_p(const void *,_pptr);
841         void *ret = _talloc_steal(new_ctx, *pptr);
842         (*pptr) = NULL;
843         return ret;
844 }
845
846 /*
847   return the total size of a talloc pool (subtree)
848 */
849 size_t talloc_total_size(const void *ptr)
850 {
851         size_t total = 0;
852         struct talloc_chunk *c, *tc;
853
854         if (ptr == NULL) {
855                 ptr = null_context;
856         }
857         if (ptr == NULL) {
858                 return 0;
859         }
860
861         tc = talloc_chunk_from_ptr(ptr);
862
863         if (tc->flags & TALLOC_FLAG_LOOP) {
864                 return 0;
865         }
866
867         tc->flags |= TALLOC_FLAG_LOOP;
868
869         total = tc->size;
870         for (c=tc->child;c;c=c->next) {
871                 total += talloc_total_size(TC_PTR_FROM_CHUNK(c));
872         }
873
874         tc->flags &= ~TALLOC_FLAG_LOOP;
875
876         return total;
877 }
878
879 /*
880   return the total number of blocks in a talloc pool (subtree)
881 */
882 size_t talloc_total_blocks(const void *ptr)
883 {
884         size_t total = 0;
885         struct talloc_chunk *c, *tc = talloc_chunk_from_ptr(ptr);
886
887         if (tc->flags & TALLOC_FLAG_LOOP) {
888                 return 0;
889         }
890
891         tc->flags |= TALLOC_FLAG_LOOP;
892
893         total++;
894         for (c=tc->child;c;c=c->next) {
895                 total += talloc_total_blocks(TC_PTR_FROM_CHUNK(c));
896         }
897
898         tc->flags &= ~TALLOC_FLAG_LOOP;
899
900         return total;
901 }
902
903 /*
904   return the number of external references to a pointer
905 */
906 size_t talloc_reference_count(const void *ptr)
907 {
908         struct talloc_chunk *tc = talloc_chunk_from_ptr(ptr);
909         struct talloc_reference_handle *h;
910         size_t ret = 0;
911
912         for (h=tc->refs;h;h=h->next) {
913                 ret++;
914         }
915         return ret;
916 }
917
918 /*
919   report on memory usage by all children of a pointer, giving a full tree view
920 */
921 void talloc_report_depth_cb(const void *ptr, int depth, int max_depth,
922                             void (*callback)(const void *ptr,
923                                              int depth, int max_depth,
924                                              int is_ref,
925                                              void *private_data),
926                             void *private_data)
927 {
928         struct talloc_chunk *c, *tc;
929
930         if (ptr == NULL) {
931                 ptr = null_context;
932         }
933         if (ptr == NULL) return;
934
935         tc = talloc_chunk_from_ptr(ptr);
936
937         if (tc->flags & TALLOC_FLAG_LOOP) {
938                 return;
939         }
940
941         callback(ptr, depth, max_depth, 0, private_data);
942
943         if (max_depth >= 0 && depth >= max_depth) {
944                 return;
945         }
946
947         tc->flags |= TALLOC_FLAG_LOOP;
948         for (c=tc->child;c;c=c->next) {
949                 if (c->name == TALLOC_MAGIC_REFERENCE) {
950                         struct talloc_reference_handle *h = (struct talloc_reference_handle *)TC_PTR_FROM_CHUNK(c);
951                         callback(h->ptr, depth + 1, max_depth, 1, private_data);
952                 } else {
953                         talloc_report_depth_cb(TC_PTR_FROM_CHUNK(c), depth + 1, max_depth, callback, private_data);
954                 }
955         }
956         tc->flags &= ~TALLOC_FLAG_LOOP;
957 }
958
959 static void talloc_report_depth_FILE_helper(const void *ptr, int depth, int max_depth, int is_ref, void *_f)
960 {
961         const char *name = talloc_get_name(ptr);
962         FILE *f = (FILE *)_f;
963
964         if (is_ref) {
965                 fprintf(f, "%*sreference to: %s\n", depth*4, "", name);
966                 return;
967         }
968
969         if (depth == 0) {
970                 fprintf(f,"%stalloc report on '%s' (total %6lu bytes in %3lu blocks)\n", 
971                         (max_depth < 0 ? "full " :""), name,
972                         (unsigned long)talloc_total_size(ptr),
973                         (unsigned long)talloc_total_blocks(ptr));
974                 return;
975         }
976
977         fprintf(f, "%*s%-30s contains %6lu bytes in %3lu blocks (ref %d) %p\n", 
978                 depth*4, "",
979                 name,
980                 (unsigned long)talloc_total_size(ptr),
981                 (unsigned long)talloc_total_blocks(ptr),
982                 (int)talloc_reference_count(ptr), ptr);
983
984 #if 0
985         fprintf(f, "content: ");
986         if (talloc_total_size(ptr)) {
987                 int tot = talloc_total_size(ptr);
988                 int i;
989
990                 for (i = 0; i < tot; i++) {
991                         if ((((char *)ptr)[i] > 31) && (((char *)ptr)[i] < 126)) {
992                                 fprintf(f, "%c", ((char *)ptr)[i]);
993                         } else {
994                                 fprintf(f, "~%02x", ((char *)ptr)[i]);
995                         }
996                 }
997         }
998         fprintf(f, "\n");
999 #endif
1000 }
1001
1002 /*
1003   report on memory usage by all children of a pointer, giving a full tree view
1004 */
1005 void talloc_report_depth_file(const void *ptr, int depth, int max_depth, FILE *f)
1006 {
1007         talloc_report_depth_cb(ptr, depth, max_depth, talloc_report_depth_FILE_helper, f);
1008         fflush(f);
1009 }
1010
1011 /*
1012   report on memory usage by all children of a pointer, giving a full tree view
1013 */
1014 void talloc_report_full(const void *ptr, FILE *f)
1015 {
1016         talloc_report_depth_file(ptr, 0, -1, f);
1017 }
1018
1019 /*
1020   report on memory usage by all children of a pointer
1021 */
1022 void talloc_report(const void *ptr, FILE *f)
1023 {
1024         talloc_report_depth_file(ptr, 0, 1, f);
1025 }
1026
1027 /*
1028   report on any memory hanging off the null context
1029 */
1030 static void talloc_report_null(void)
1031 {
1032         if (talloc_total_size(null_context) != 0) {
1033                 talloc_report(null_context, stderr);
1034         }
1035 }
1036
1037 /*
1038   report on any memory hanging off the null context
1039 */
1040 static void talloc_report_null_full(void)
1041 {
1042         if (talloc_total_size(null_context) != 0) {
1043                 talloc_report_full(null_context, stderr);
1044         }
1045 }
1046
1047 /*
1048   enable tracking of the NULL context
1049 */
1050 void talloc_enable_null_tracking(void)
1051 {
1052         if (null_context == NULL) {
1053                 null_context = _talloc_named_const(NULL, 0, "null_context");
1054         }
1055 }
1056
1057 /*
1058   disable tracking of the NULL context
1059 */
1060 void talloc_disable_null_tracking(void)
1061 {
1062         _talloc_free(null_context);
1063         null_context = NULL;
1064 }
1065
1066 /*
1067   enable leak reporting on exit
1068 */
1069 void talloc_enable_leak_report(void)
1070 {
1071         talloc_enable_null_tracking();
1072         atexit(talloc_report_null);
1073 }
1074
1075 /*
1076   enable full leak reporting on exit
1077 */
1078 void talloc_enable_leak_report_full(void)
1079 {
1080         talloc_enable_null_tracking();
1081         atexit(talloc_report_null_full);
1082 }
1083
1084 /* 
1085    talloc and zero memory. 
1086 */
1087 void *_talloc_zero(const void *ctx, size_t size, const char *name)
1088 {
1089         void *p = _talloc_named_const(ctx, size, name);
1090
1091         if (p) {
1092                 memset(p, '\0', size);
1093         }
1094
1095         return p;
1096 }
1097
1098 /*
1099   memdup with a talloc. 
1100 */
1101 void *_talloc_memdup(const void *t, const void *p, size_t size, const char *name)
1102 {
1103         void *newp = _talloc_named_const(t, size, name);
1104
1105         if (likely(newp)) {
1106                 memcpy(newp, p, size);
1107         }
1108
1109         return newp;
1110 }
1111
1112 static inline char *__talloc_strlendup(const void *t, const char *p, size_t len)
1113 {
1114         char *ret;
1115
1116         ret = (char *)__talloc(t, len + 1);
1117         if (unlikely(!ret)) return NULL;
1118
1119         memcpy(ret, p, len);
1120         ret[len] = 0;
1121
1122         _talloc_set_name_const(ret, ret);
1123         return ret;
1124 }
1125
1126 /*
1127   strdup with a talloc
1128 */
1129 char *talloc_strdup(const void *t, const char *p)
1130 {
1131         if (unlikely(!p)) return NULL;
1132         return __talloc_strlendup(t, p, strlen(p));
1133 }
1134
1135 /*
1136   strndup with a talloc
1137 */
1138 char *talloc_strndup(const void *t, const char *p, size_t n)
1139 {
1140         if (unlikely(!p)) return NULL;
1141         return __talloc_strlendup(t, p, strnlen(p, n));
1142 }
1143
1144 static inline char *__talloc_strlendup_append(char *s, size_t slen,
1145                                               const char *a, size_t alen)
1146 {
1147         char *ret;
1148
1149         ret = talloc_realloc(NULL, s, char, slen + alen + 1);
1150         if (unlikely(!ret)) return NULL;
1151
1152         /* append the string and the trailing \0 */
1153         memcpy(&ret[slen], a, alen);
1154         ret[slen+alen] = 0;
1155
1156         _talloc_set_name_const(ret, ret);
1157         return ret;
1158 }
1159
1160 /*
1161  * Appends at the end of the string.
1162  */
1163 char *talloc_strdup_append(char *s, const char *a)
1164 {
1165         if (unlikely(!s)) {
1166                 return talloc_strdup(NULL, a);
1167         }
1168
1169         if (unlikely(!a)) {
1170                 return s;
1171         }
1172
1173         return __talloc_strlendup_append(s, strlen(s), a, strlen(a));
1174 }
1175
1176 /*
1177  * Appends at the end of the talloc'ed buffer,
1178  * not the end of the string.
1179  */
1180 char *talloc_strdup_append_buffer(char *s, const char *a)
1181 {
1182         size_t slen;
1183
1184         if (unlikely(!s)) {
1185                 return talloc_strdup(NULL, a);
1186         }
1187
1188         if (unlikely(!a)) {
1189                 return s;
1190         }
1191
1192         slen = talloc_get_size(s);
1193         if (likely(slen > 0)) {
1194                 slen--;
1195         }
1196
1197         return __talloc_strlendup_append(s, slen, a, strlen(a));
1198 }
1199
1200 /*
1201  * Appends at the end of the string.
1202  */
1203 char *talloc_strndup_append(char *s, const char *a, size_t n)
1204 {
1205         if (unlikely(!s)) {
1206                 return talloc_strdup(NULL, a);
1207         }
1208
1209         if (unlikely(!a)) {
1210                 return s;
1211         }
1212
1213         return __talloc_strlendup_append(s, strlen(s), a, strnlen(a, n));
1214 }
1215
1216 /*
1217  * Appends at the end of the talloc'ed buffer,
1218  * not the end of the string.
1219  */
1220 char *talloc_strndup_append_buffer(char *s, const char *a, size_t n)
1221 {
1222         size_t slen;
1223
1224         if (unlikely(!s)) {
1225                 return talloc_strdup(NULL, a);
1226         }
1227
1228         if (unlikely(!a)) {
1229                 return s;
1230         }
1231
1232         slen = talloc_get_size(s);
1233         if (likely(slen > 0)) {
1234                 slen--;
1235         }
1236
1237         return __talloc_strlendup_append(s, slen, a, strnlen(a, n));
1238 }
1239
1240 #ifndef HAVE_VA_COPY
1241 #ifdef HAVE___VA_COPY
1242 #define va_copy(dest, src) __va_copy(dest, src)
1243 #else
1244 #define va_copy(dest, src) (dest) = (src)
1245 #endif
1246 #endif
1247
1248 char *talloc_vasprintf(const void *t, const char *fmt, va_list ap)
1249 {
1250         int len;
1251         char *ret;
1252         va_list ap2;
1253         char c;
1254
1255         /* this call looks strange, but it makes it work on older solaris boxes */
1256         va_copy(ap2, ap);
1257         len = vsnprintf(&c, 1, fmt, ap2);
1258         va_end(ap2);
1259         if (unlikely(len < 0)) {
1260                 return NULL;
1261         }
1262
1263         ret = (char *)__talloc(t, len+1);
1264         if (unlikely(!ret)) return NULL;
1265
1266         va_copy(ap2, ap);
1267         vsnprintf(ret, len+1, fmt, ap2);
1268         va_end(ap2);
1269
1270         _talloc_set_name_const(ret, ret);
1271         return ret;
1272 }
1273
1274
1275 /*
1276   Perform string formatting, and return a pointer to newly allocated
1277   memory holding the result, inside a memory pool.
1278  */
1279 char *talloc_asprintf(const void *t, const char *fmt, ...)
1280 {
1281         va_list ap;
1282         char *ret;
1283
1284         va_start(ap, fmt);
1285         ret = talloc_vasprintf(t, fmt, ap);
1286         va_end(ap);
1287         return ret;
1288 }
1289
1290 static inline char *__talloc_vaslenprintf_append(char *s, size_t slen,
1291                                                  const char *fmt, va_list ap)
1292                                                  PRINTF_ATTRIBUTE(3,0);
1293
1294 static inline char *__talloc_vaslenprintf_append(char *s, size_t slen,
1295                                                  const char *fmt, va_list ap)
1296 {
1297         ssize_t alen;
1298         va_list ap2;
1299         char c;
1300
1301         va_copy(ap2, ap);
1302         alen = vsnprintf(&c, 1, fmt, ap2);
1303         va_end(ap2);
1304
1305         if (alen <= 0) {
1306                 /* Either the vsnprintf failed or the format resulted in
1307                  * no characters being formatted. In the former case, we
1308                  * ought to return NULL, in the latter we ought to return
1309                  * the original string. Most current callers of this
1310                  * function expect it to never return NULL.
1311                  */
1312                 return s;
1313         }
1314
1315         s = talloc_realloc(NULL, s, char, slen + alen + 1);
1316         if (!s) return NULL;
1317
1318         va_copy(ap2, ap);
1319         vsnprintf(s + slen, alen + 1, fmt, ap2);
1320         va_end(ap2);
1321
1322         _talloc_set_name_const(s, s);
1323         return s;
1324 }
1325
1326 /**
1327  * Realloc @p s to append the formatted result of @p fmt and @p ap,
1328  * and return @p s, which may have moved.  Good for gradually
1329  * accumulating output into a string buffer. Appends at the end
1330  * of the string.
1331  **/
1332 char *talloc_vasprintf_append(char *s, const char *fmt, va_list ap)
1333 {
1334         if (unlikely(!s)) {
1335                 return talloc_vasprintf(NULL, fmt, ap);
1336         }
1337
1338         return __talloc_vaslenprintf_append(s, strlen(s), fmt, ap);
1339 }
1340
1341 /**
1342  * Realloc @p s to append the formatted result of @p fmt and @p ap,
1343  * and return @p s, which may have moved. Always appends at the
1344  * end of the talloc'ed buffer, not the end of the string.
1345  **/
1346 char *talloc_vasprintf_append_buffer(char *s, const char *fmt, va_list ap)
1347 {
1348         size_t slen;
1349
1350         if (unlikely(!s)) {
1351                 return talloc_vasprintf(NULL, fmt, ap);
1352         }
1353
1354         slen = talloc_get_size(s);
1355         if (likely(slen > 0)) {
1356                 slen--;
1357         }
1358
1359         return __talloc_vaslenprintf_append(s, slen, fmt, ap);
1360 }
1361
1362 /*
1363   Realloc @p s to append the formatted result of @p fmt and return @p
1364   s, which may have moved.  Good for gradually accumulating output
1365   into a string buffer.
1366  */
1367 char *talloc_asprintf_append(char *s, const char *fmt, ...)
1368 {
1369         va_list ap;
1370
1371         va_start(ap, fmt);
1372         s = talloc_vasprintf_append(s, fmt, ap);
1373         va_end(ap);
1374         return s;
1375 }
1376
1377 /*
1378   Realloc @p s to append the formatted result of @p fmt and return @p
1379   s, which may have moved.  Good for gradually accumulating output
1380   into a buffer.
1381  */
1382 char *talloc_asprintf_append_buffer(char *s, const char *fmt, ...)
1383 {
1384         va_list ap;
1385
1386         va_start(ap, fmt);
1387         s = talloc_vasprintf_append_buffer(s, fmt, ap);
1388         va_end(ap);
1389         return s;
1390 }
1391
1392 /*
1393   alloc an array, checking for integer overflow in the array size
1394 */
1395 void *_talloc_array(const void *ctx, size_t el_size, unsigned count, const char *name)
1396 {
1397         if (count >= MAX_TALLOC_SIZE/el_size) {
1398                 return NULL;
1399         }
1400         return _talloc_named_const(ctx, el_size * count, name);
1401 }
1402
1403 /*
1404   alloc an zero array, checking for integer overflow in the array size
1405 */
1406 void *_talloc_zero_array(const void *ctx, size_t el_size, unsigned count, const char *name)
1407 {
1408         if (count >= MAX_TALLOC_SIZE/el_size) {
1409                 return NULL;
1410         }
1411         return _talloc_zero(ctx, el_size * count, name);
1412 }
1413
1414 /*
1415   realloc an array, checking for integer overflow in the array size
1416 */
1417 void *_talloc_realloc_array(const void *ctx, void *ptr, size_t el_size, unsigned count, const char *name)
1418 {
1419         if (count >= MAX_TALLOC_SIZE/el_size) {
1420                 return NULL;
1421         }
1422         return _talloc_realloc(ctx, ptr, el_size * count, name);
1423 }
1424
1425 /*
1426   a function version of talloc_realloc(), so it can be passed as a function pointer
1427   to libraries that want a realloc function (a realloc function encapsulates
1428   all the basic capabilities of an allocation library, which is why this is useful)
1429 */
1430 void *talloc_realloc_fn(const void *context, void *ptr, size_t size)
1431 {
1432         return _talloc_realloc(context, ptr, size, NULL);
1433 }
1434
1435
1436 static int talloc_autofree_destructor(void *ptr)
1437 {
1438         autofree_context = NULL;
1439         return 0;
1440 }
1441
1442 static void talloc_autofree(void)
1443 {
1444         _talloc_free(autofree_context);
1445 }
1446
1447 /*
1448   return a context which will be auto-freed on exit
1449   this is useful for reducing the noise in leak reports
1450 */
1451 void *talloc_autofree_context(void)
1452 {
1453         if (autofree_context == NULL) {
1454                 autofree_context = _talloc_named_const(NULL, 0, "autofree_context");
1455                 talloc_set_destructor(autofree_context, talloc_autofree_destructor);
1456                 atexit(talloc_autofree);
1457         }
1458         return autofree_context;
1459 }
1460
1461 size_t talloc_get_size(const void *context)
1462 {
1463         struct talloc_chunk *tc;
1464
1465         if (context == NULL)
1466                 return 0;
1467
1468         tc = talloc_chunk_from_ptr(context);
1469
1470         return tc->size;
1471 }
1472
1473 /*
1474   find a parent of this context that has the given name, if any
1475 */
1476 void *talloc_find_parent_byname(const void *context, const char *name)
1477 {
1478         struct talloc_chunk *tc;
1479
1480         if (context == NULL) {
1481                 return NULL;
1482         }
1483
1484         tc = talloc_chunk_from_ptr(context);
1485         while (tc) {
1486                 if (tc->name && strcmp(tc->name, name) == 0) {
1487                         return TC_PTR_FROM_CHUNK(tc);
1488                 }
1489                 while (tc && tc->prev) tc = tc->prev;
1490                 if (tc) {
1491                         tc = tc->parent;
1492                 }
1493         }
1494         return NULL;
1495 }
1496
1497 /*
1498   show the parentage of a context
1499 */
1500 void talloc_show_parents(const void *context, FILE *file)
1501 {
1502         struct talloc_chunk *tc;
1503
1504         if (context == NULL) {
1505                 fprintf(file, "talloc no parents for NULL\n");
1506                 return;
1507         }
1508
1509         tc = talloc_chunk_from_ptr(context);
1510         fprintf(file, "talloc parents of '%s'\n", talloc_get_name(context));
1511         while (tc) {
1512                 fprintf(file, "\t'%s'\n", talloc_get_name(TC_PTR_FROM_CHUNK(tc)));
1513                 while (tc && tc->prev) tc = tc->prev;
1514                 if (tc) {
1515                         tc = tc->parent;
1516                 }
1517         }
1518         fflush(file);
1519 }
1520
1521 /*
1522   return 1 if ptr is a parent of context
1523 */
1524 int talloc_is_parent(const void *context, const void *ptr)
1525 {
1526         struct talloc_chunk *tc;
1527
1528         if (context == NULL) {
1529                 return 0;
1530         }
1531
1532         tc = talloc_chunk_from_ptr(context);
1533         while (tc) {
1534                 if (TC_PTR_FROM_CHUNK(tc) == ptr) return 1;
1535                 while (tc && tc->prev) tc = tc->prev;
1536                 if (tc) {
1537                         tc = tc->parent;
1538                 }
1539         }
1540         return 0;
1541 }