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