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