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