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