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