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