r23796: main COPYING file for samba4, plus some formatting varients
[samba.git] / source / lib / talloc / talloc.c
1 /* 
2    Samba Unix SMB/CIFS implementation.
3
4    Samba trivial allocation library - new interface
5
6    NOTE: Please read talloc_guide.txt for full documentation
7
8    Copyright (C) Andrew Tridgell 2004
9    Copyright (C) Stefan Metzmacher 2006
10    
11      ** NOTE! The following LGPL license applies to the talloc
12      ** library. This does NOT imply that all of Samba is released
13      ** under the LGPL
14    
15    This library is free software; you can redistribute it and/or
16    modify it under the terms of the GNU Lesser General Public
17    License as published by the Free Software Foundation; either
18    version 3 of the License, or (at your option) any later version.
19
20    This library is distributed in the hope that it will be useful,
21    but WITHOUT ANY WARRANTY; without even the implied warranty of
22    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
23    Lesser General Public License for more details.
24
25    You should have received a copy of the GNU Lesser General Public
26    License along with this library; if not, 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   memdup with a talloc. 
1091 */
1092 void *_talloc_memdup(const void *t, const void *p, size_t size, const char *name)
1093 {
1094         void *newp = _talloc_named_const(t, size, name);
1095
1096         if (likely(newp)) {
1097                 memcpy(newp, p, size);
1098         }
1099
1100         return newp;
1101 }
1102
1103 /*
1104   strdup with a talloc 
1105 */
1106 char *talloc_strdup(const void *t, const char *p)
1107 {
1108         char *ret;
1109         if (!p) {
1110                 return NULL;
1111         }
1112         ret = (char *)talloc_memdup(t, p, strlen(p) + 1);
1113         if (likely(ret)) {
1114                 _talloc_set_name_const(ret, ret);
1115         }
1116         return ret;
1117 }
1118
1119 /*
1120  append to a talloced string 
1121 */
1122 char *talloc_append_string(const void *t, char *orig, const char *append)
1123 {
1124         char *ret;
1125         size_t olen = strlen(orig);
1126         size_t alenz;
1127
1128         if (!append)
1129                 return orig;
1130
1131         alenz = strlen(append) + 1;
1132
1133         ret = talloc_realloc(t, orig, char, olen + alenz);
1134         if (!ret)
1135                 return NULL;
1136
1137         /* append the string with the trailing \0 */
1138         memcpy(&ret[olen], append, alenz);
1139
1140         _talloc_set_name_const(ret, ret);
1141
1142         return ret;
1143 }
1144
1145 /*
1146   strndup with a talloc 
1147 */
1148 char *talloc_strndup(const void *t, const char *p, size_t n)
1149 {
1150         size_t len;
1151         char *ret;
1152
1153         for (len=0; len<n && p[len]; len++) ;
1154
1155         ret = (char *)__talloc(t, len + 1);
1156         if (!ret) { return NULL; }
1157         memcpy(ret, p, len);
1158         ret[len] = 0;
1159         _talloc_set_name_const(ret, ret);
1160         return ret;
1161 }
1162
1163 #ifndef HAVE_VA_COPY
1164 #ifdef HAVE___VA_COPY
1165 #define va_copy(dest, src) __va_copy(dest, src)
1166 #else
1167 #define va_copy(dest, src) (dest) = (src)
1168 #endif
1169 #endif
1170
1171 char *talloc_vasprintf(const void *t, const char *fmt, va_list ap)
1172 {       
1173         int len;
1174         char *ret;
1175         va_list ap2;
1176         char c;
1177         
1178         /* this call looks strange, but it makes it work on older solaris boxes */
1179         va_copy(ap2, ap);
1180         len = vsnprintf(&c, 1, fmt, ap2);
1181         va_end(ap2);
1182         if (len < 0) {
1183                 return NULL;
1184         }
1185
1186         ret = (char *)__talloc(t, len+1);
1187         if (ret) {
1188                 va_copy(ap2, ap);
1189                 vsnprintf(ret, len+1, fmt, ap2);
1190                 va_end(ap2);
1191                 _talloc_set_name_const(ret, ret);
1192         }
1193
1194         return ret;
1195 }
1196
1197
1198 /*
1199   Perform string formatting, and return a pointer to newly allocated
1200   memory holding the result, inside a memory pool.
1201  */
1202 char *talloc_asprintf(const void *t, const char *fmt, ...)
1203 {
1204         va_list ap;
1205         char *ret;
1206
1207         va_start(ap, fmt);
1208         ret = talloc_vasprintf(t, fmt, ap);
1209         va_end(ap);
1210         return ret;
1211 }
1212
1213
1214 /**
1215  * Realloc @p s to append the formatted result of @p fmt and @p ap,
1216  * and return @p s, which may have moved.  Good for gradually
1217  * accumulating output into a string buffer.
1218  **/
1219 char *talloc_vasprintf_append(char *s, const char *fmt, va_list ap)
1220 {       
1221         struct talloc_chunk *tc;
1222         int len, s_len;
1223         va_list ap2;
1224         char c;
1225
1226         if (s == NULL) {
1227                 return talloc_vasprintf(NULL, fmt, ap);
1228         }
1229
1230         tc = talloc_chunk_from_ptr(s);
1231
1232         s_len = tc->size - 1;
1233
1234         va_copy(ap2, ap);
1235         len = vsnprintf(&c, 1, fmt, ap2);
1236         va_end(ap2);
1237
1238         if (len <= 0) {
1239                 /* Either the vsnprintf failed or the format resulted in
1240                  * no characters being formatted. In the former case, we
1241                  * ought to return NULL, in the latter we ought to return
1242                  * the original string. Most current callers of this 
1243                  * function expect it to never return NULL.
1244                  */
1245                 return s;
1246         }
1247
1248         s = talloc_realloc(NULL, s, char, s_len + len+1);
1249         if (!s) return NULL;
1250
1251         va_copy(ap2, ap);
1252         vsnprintf(s+s_len, len+1, fmt, ap2);
1253         va_end(ap2);
1254         _talloc_set_name_const(s, s);
1255
1256         return s;
1257 }
1258
1259 /*
1260   Realloc @p s to append the formatted result of @p fmt and return @p
1261   s, which may have moved.  Good for gradually accumulating output
1262   into a string buffer.
1263  */
1264 char *talloc_asprintf_append(char *s, const char *fmt, ...)
1265 {
1266         va_list ap;
1267
1268         va_start(ap, fmt);
1269         s = talloc_vasprintf_append(s, fmt, ap);
1270         va_end(ap);
1271         return s;
1272 }
1273
1274 /*
1275   alloc an array, checking for integer overflow in the array size
1276 */
1277 void *_talloc_array(const void *ctx, size_t el_size, unsigned count, const char *name)
1278 {
1279         if (count >= MAX_TALLOC_SIZE/el_size) {
1280                 return NULL;
1281         }
1282         return _talloc_named_const(ctx, el_size * count, name);
1283 }
1284
1285 /*
1286   alloc an zero array, checking for integer overflow in the array size
1287 */
1288 void *_talloc_zero_array(const void *ctx, size_t el_size, unsigned count, const char *name)
1289 {
1290         if (count >= MAX_TALLOC_SIZE/el_size) {
1291                 return NULL;
1292         }
1293         return _talloc_zero(ctx, el_size * count, name);
1294 }
1295
1296 /*
1297   realloc an array, checking for integer overflow in the array size
1298 */
1299 void *_talloc_realloc_array(const void *ctx, void *ptr, size_t el_size, unsigned count, const char *name)
1300 {
1301         if (count >= MAX_TALLOC_SIZE/el_size) {
1302                 return NULL;
1303         }
1304         return _talloc_realloc(ctx, ptr, el_size * count, name);
1305 }
1306
1307 /*
1308   a function version of talloc_realloc(), so it can be passed as a function pointer
1309   to libraries that want a realloc function (a realloc function encapsulates
1310   all the basic capabilities of an allocation library, which is why this is useful)
1311 */
1312 void *talloc_realloc_fn(const void *context, void *ptr, size_t size)
1313 {
1314         return _talloc_realloc(context, ptr, size, NULL);
1315 }
1316
1317
1318 static int talloc_autofree_destructor(void *ptr)
1319 {
1320         autofree_context = NULL;
1321         return 0;
1322 }
1323
1324 static void talloc_autofree(void)
1325 {
1326         _talloc_free(autofree_context);
1327 }
1328
1329 /*
1330   return a context which will be auto-freed on exit
1331   this is useful for reducing the noise in leak reports
1332 */
1333 void *talloc_autofree_context(void)
1334 {
1335         if (autofree_context == NULL) {
1336                 autofree_context = _talloc_named_const(NULL, 0, "autofree_context");
1337                 talloc_set_destructor(autofree_context, talloc_autofree_destructor);
1338                 atexit(talloc_autofree);
1339         }
1340         return autofree_context;
1341 }
1342
1343 size_t talloc_get_size(const void *context)
1344 {
1345         struct talloc_chunk *tc;
1346
1347         if (context == NULL)
1348                 return 0;
1349
1350         tc = talloc_chunk_from_ptr(context);
1351
1352         return tc->size;
1353 }
1354
1355 /*
1356   find a parent of this context that has the given name, if any
1357 */
1358 void *talloc_find_parent_byname(const void *context, const char *name)
1359 {
1360         struct talloc_chunk *tc;
1361
1362         if (context == NULL) {
1363                 return NULL;
1364         }
1365
1366         tc = talloc_chunk_from_ptr(context);
1367         while (tc) {
1368                 if (tc->name && strcmp(tc->name, name) == 0) {
1369                         return TC_PTR_FROM_CHUNK(tc);
1370                 }
1371                 while (tc && tc->prev) tc = tc->prev;
1372                 if (tc) {
1373                         tc = tc->parent;
1374                 }
1375         }
1376         return NULL;
1377 }
1378
1379 /*
1380   show the parentage of a context
1381 */
1382 void talloc_show_parents(const void *context, FILE *file)
1383 {
1384         struct talloc_chunk *tc;
1385
1386         if (context == NULL) {
1387                 fprintf(file, "talloc no parents for NULL\n");
1388                 return;
1389         }
1390
1391         tc = talloc_chunk_from_ptr(context);
1392         fprintf(file, "talloc parents of '%s'\n", talloc_get_name(context));
1393         while (tc) {
1394                 fprintf(file, "\t'%s'\n", talloc_get_name(TC_PTR_FROM_CHUNK(tc)));
1395                 while (tc && tc->prev) tc = tc->prev;
1396                 if (tc) {
1397                         tc = tc->parent;
1398                 }
1399         }
1400         fflush(file);
1401 }
1402
1403 /*
1404   return 1 if ptr is a parent of context
1405 */
1406 int talloc_is_parent(const void *context, const void *ptr)
1407 {
1408         struct talloc_chunk *tc;
1409
1410         if (context == NULL) {
1411                 return 0;
1412         }
1413
1414         tc = talloc_chunk_from_ptr(context);
1415         while (tc) {
1416                 if (TC_PTR_FROM_CHUNK(tc) == ptr) return 1;
1417                 while (tc && tc->prev) tc = tc->prev;
1418                 if (tc) {
1419                         tc = tc->parent;
1420                 }
1421         }
1422         return 0;
1423 }