3
* alloc.c - multi-reference hierarchial allocator
5
* Copyright © 2009 Scott James Remnant <scott@netsplit.com>.
6
* Copyright © 2009 Canonical Ltd.
8
* This program is free software; you can redistribute it and/or modify
9
* it under the terms of the GNU General Public License version 2, as
10
* published by the Free Software Foundation.
12
* This program is distributed in the hope that it will be useful,
13
* but WITHOUT ANY WARRANTY; without even the implied warranty of
14
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15
* GNU General Public License for more details.
17
* You should have received a copy of the GNU General Public License along
18
* with this program; if not, write to the Free Software Foundation, Inc.,
19
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24
#endif /* HAVE_CONFIG_H */
30
#include <nih/macros.h>
31
#include <nih/logging.h>
39
* @parents: parents of this context,
40
* @children: children of this context,
41
* @destructor: function to be called when freed.
43
* This structure is placed before all allocations in memory and is used
44
* to build up an n-ary tree of them. Allocations may have multiple
45
* parent references and multiple children. Allocations are automatically
46
* freed if the last parent reference is freed. When an allocation is
47
* freed, all children are unreferenced and any destructors called.
49
* Members of @parents and @children are both NihAllocRef objects.
51
typedef struct nih_alloc_ctx {
54
NihDestructor destructor;
59
* @children_entry: list head in parent's children list,
60
* @parents_entry: list head in child's parents list,
61
* @parent: pointer to parent context,
62
* @child: pointer to child context.
64
* This structure is shared by both @parent and @child denoting a reference
65
* between the two of them. It is placed in @parent's children list through
66
* @children_entry and @child's parents list through @parents_entry.
68
typedef struct nih_alloc_ref {
69
NihList children_entry;
70
NihList parents_entry;
78
* @ptr: pointer to block of memory.
80
* Obtain the location of the NihAllocCtx structure given a pointer to the
81
* block of memory beyond it.
83
* Returns: pointer to NihAllocCtx structure.
85
#define NIH_ALLOC_CTX(ptr) ((NihAllocCtx *)(ptr) - 1)
89
* @ctx: pointer to NihAllocCtx structure.
91
* Obtain the location of the block of memory given a pointer to the
92
* NihAllocCtx structure in front of it.
94
* Returns: pointer to block of memory.
96
#define NIH_ALLOC_PTR(ctx) ((void *)((NihAllocCtx *)(ctx) + 1))
99
* NIH_ALLOC_FINALISED:
101
* Flag placed in the destructor field of a context to indicate the
102
* destructor has been called and the object is pending being freed.
104
#define NIH_ALLOC_FINALISED ((void *)-1)
107
/* Prototypes for static functions */
108
static inline int nih_alloc_context_free (NihAllocCtx *ctx);
110
static inline NihAllocRef *nih_alloc_ref_new (NihAllocCtx *parent,
112
__attribute__ ((malloc));
113
static inline void nih_alloc_ref_free (NihAllocRef *ref);
114
static inline NihAllocRef *nih_alloc_ref_lookup (NihAllocCtx *parent,
118
/* Point to the functions we actually call for allocation. */
119
void *(*__nih_malloc) (size_t size) = malloc;
120
void *(*__nih_realloc) (void *ptr, size_t size) = realloc;
121
void (*__nih_free) (void *ptr) = free;
126
* @parent: parent object for new object,
127
* @size: size of requested object.
129
* Allocates an object in memory of at least @size bytes and returns a
132
* If @parent is not NULL, it should be a pointer to another object which
133
* will be used as a parent for the returned object. When all parents
134
* of the returned object are freed, the returned object will also be
137
* If you have clean-up that you would like to run, you can assign a
138
* destructor using the nih_alloc_set_destructor() function.
140
* Returns: newly allocated object or NULL if insufficient memory.
143
nih_alloc (const void *parent,
148
ctx = __nih_malloc (sizeof (NihAllocCtx) + size);
152
nih_list_init (&ctx->parents);
153
nih_list_init (&ctx->children);
155
ctx->destructor = NULL;
158
nih_alloc_ref_new (NIH_ALLOC_CTX (parent), ctx);
160
return NIH_ALLOC_PTR (ctx);
166
* @ptr: object to reallocate,
167
* @parent: parent object of new object,
168
* @size: size of new object.
170
* Adjusts the size of the object @ptr to be at least @size bytes, which
171
* may be larger or smaller than the existing object, and returns the
174
* If @ptr is NULL, this simply calls nih_alloc() and passes both @parent
175
* and @size to it, returning the returned object.
177
* If @ptr is not NULL, @parent is ignored; though it is usual to pass a
178
* parent of @ptr for style reasons.
180
* Returns: reallocated object or NULL if insufficient memory.
183
nih_realloc (void * ptr,
188
NihList * first_parent = NULL;
189
NihList * first_child = NULL;
192
return nih_alloc (parent, size);
194
ctx = NIH_ALLOC_CTX (ptr);
195
nih_assert (ctx->destructor != NIH_ALLOC_FINALISED);
197
/* This is somewhat more difficult than alloc or free because we
198
* have two lists of pointers to worry about. Fortunately the
199
* properties of NihList help us a lot here.
201
* The problem is that references between us and our parents,
202
* and references between us and our children, all contain list
203
* pointers that are potentially invalid once relloc has been
206
* We could strip it all down before calling realloc then rebuild
207
* it afterwards, but that's expensive and could be error-prone in
208
* the case where the allocator fails.
210
* The solution is to rely on a property of nih_list_add(). The
211
* entry passed (to be added) is cut out of its containing list
212
* without dereferencing the return pointers, this means we can
213
* cut the bad pointers out simply by calling nih_list_add()
214
* to put the new entry back in the same position.
216
* Of course, this only works in the non-empty list case as trying
217
* to cut an entry out of an empty list would dereference those
218
* invalid pointers. Happily all we need to do for the empty
219
* list case is call nih_list_init() again.
221
* So we just remember the first parent and first child reference,
222
* or NULL if the list is empty.
225
if (! NIH_LIST_EMPTY (&ctx->parents))
226
first_parent = ctx->parents.next;
227
if (! NIH_LIST_EMPTY (&ctx->children))
228
first_child = ctx->children.next;
230
/* Now do the actual realloc(), if this fails then we can just
231
* return NULL since we've not actually changed anything.
233
ctx = __nih_realloc (ctx, sizeof (NihAllocCtx) + size);
237
/* Now update our parents and children lists, or reinitialise,
238
* as noted above this ensures that all the pointers are correct
241
nih_list_add_after (first_parent, &ctx->parents);
243
nih_list_init (&ctx->parents);
247
nih_list_add_after (first_child, &ctx->children);
249
nih_list_init (&ctx->children);
252
/* We still have to fix up the parent and child pointers, but
255
NIH_LIST_FOREACH (&ctx->parents, iter) {
256
NihAllocRef *ref = NIH_LIST_ITER (iter, NihAllocRef,
262
NIH_LIST_FOREACH (&ctx->children, iter) {
263
NihAllocRef *ref = NIH_LIST_ITER (iter, NihAllocRef,
269
return NIH_ALLOC_PTR (ctx);
275
* @ptr: object to free.
277
* Returns the object @ptr to the allocator so the memory consumed may be
278
* re-used by something else.
280
* All parent references are discarded and the destructor for @ptr is called.
281
* Then all children are recursively unreferenced. Those that have no
282
* remaining parent references will also have their destructors called and
283
* their children unreferenced, etc. Once all destructors have been called,
284
* the objects themselves are freed.
286
* If you call nih_free() on an object with parent references, you should
287
* make sure that any pointers to the object are reset. If you are unsure
288
* whether or not there are references you should call nih_discard(), if
289
* you only want to discard a particular parent reference you should call
292
* Returns: return value from @ptr's destructor, or 0.
299
nih_assert (ptr != NULL);
301
ctx = NIH_ALLOC_CTX (ptr);
302
nih_assert (ctx->destructor != NIH_ALLOC_FINALISED);
304
/* Cast off our parents first, without recursing. This ensures
305
* we always have zero references before we call the destructor,
306
* and has the somewhat neat property of breaking any reference
309
NIH_LIST_FOREACH_SAFE (&ctx->parents, iter) {
310
NihAllocRef *ref = NIH_LIST_ITER (iter, NihAllocRef,
313
nih_alloc_ref_free (ref);
316
return nih_alloc_context_free (ctx);
321
* @ptr: object to discard.
323
* If the object @ptr has no parent references, then returns it to the
324
* allocator so the memory consumed may be re-used by something else.
326
* If @ptr has parent references, this function does nothing and returns.
328
* You would use nih_discard() when you allocated @ptr without any parent
329
* but have passed it to functions that may have taken a reference to it
330
* in the meantime. Compare with nih_free() which acts even if there are
331
* parent references, and nih_unref() which only removes a single parent
334
* Returns: return value from @ptr's destructor, or 0.
337
nih_discard (void *ptr)
341
nih_assert (ptr != NULL);
343
ctx = NIH_ALLOC_CTX (ptr);
344
nih_assert (ctx->destructor != NIH_ALLOC_FINALISED);
346
if (NIH_LIST_EMPTY (&ctx->parents))
347
return nih_alloc_context_free (ctx);
353
* _nih_discard_local:
354
* @ptr: address of local object to be discarded.
356
* This function should never be called directly, it is used as part of the
357
* implementation of nih_local and simply calls nih_discard() with the local
361
_nih_discard_local (void *ptraddr)
363
/* Can't just take void ** as a parameter, since that will upset
364
* gcc typechecking, and we want to be able to be used on any
367
void **ptr = (void **)ptraddr;
375
* nih_alloc_context_free:
376
* @ctx: context to free.
378
* This is the internal function called by nih_free(), nih_discard() and
379
* nih_unref() to actually free an allocated context and its attached
382
* All parent references must have been discarded prior to calling this
385
* The destructor for @ctx is called, and then all children are recursively
386
* unreferenced. Those that have no remaining parent references will also
387
* have their destructors called and their children unreferenced, etc.
388
* Once all destructors have been called, the objects themselves are freed.
390
* Returns: return value from @ptr's destructor, or 0.
393
nih_alloc_context_free (NihAllocCtx *ctx)
397
nih_assert (ctx != NULL);
398
nih_assert (ctx->destructor != NIH_ALLOC_FINALISED);
399
nih_assert (NIH_LIST_EMPTY (&ctx->parents));
401
/* We have no parents, call our destructor before doing anything
402
* to our children. Save the return value, since this is what
406
ret = ctx->destructor (NIH_ALLOC_PTR (ctx));
407
ctx->destructor = NIH_ALLOC_FINALISED;
409
/* Recursively finalise all of our children. */
410
NIH_LIST_FOREACH_SAFE (&ctx->children, iter) {
411
NihAllocRef *ref = NIH_LIST_ITER (iter, NihAllocRef,
414
/* Disassociate the child from its parent.
415
* If that was not the last parent, the child should not
416
* be freed, so destroy the rest of the reference and move
419
nih_list_destroy (&ref->parents_entry);
420
if (! NIH_LIST_EMPTY (&ref->child->parents)) {
421
nih_list_destroy (&ref->children_entry);
426
/* Child is to be destroyed and has no links back to its
427
* parents. We call the destructor now.
429
if (ref->child->destructor)
430
ref->child->destructor (NIH_ALLOC_PTR (ref->child));
431
ref->child->destructor = NIH_ALLOC_FINALISED;
433
/* Reparent all of its own children to us so that they too
434
* will be finalised if the last reference is removed.
436
* In order to do this depth-first while preserving order,
437
* we insert the items before our cursor; and then put the
438
* cursor back at the head of them.
440
NIH_LIST_FOREACH_SAFE (&ref->child->children, citer) {
441
NihAllocRef *cref = NIH_LIST_ITER (citer, NihAllocRef,
444
nih_list_add (&_iter, &cref->children_entry);
447
nih_list_add_after (iter, &_iter);
450
/* We now have a single list of children all of which have no
451
* references back to us as their parent, and all of had their
452
* destructors called.
456
NIH_LIST_FOREACH_SAFE (&ctx->children, iter) {
457
NihAllocRef *ref = NIH_LIST_ITER (iter, NihAllocRef,
460
__nih_free (ref->child);
462
nih_list_destroy (&ref->children_entry);
466
/* And now we can free ourselves. */
474
* nih_alloc_real_set_destructor:
475
* @ptr: pointer to object,
476
* @destructor: destructor function to set.
478
* Sets the destructor of the allocated object @ptr to @destructor, which
479
* may be NULL to unset an existing destructor. Normally you would use
480
* the nih_alloc_set_destructor() macro which expands to this function
481
* but casts @destructor to the correct type, since almost all destructors
482
* will be defined with their argument to be the type of the object
483
* rather than void *.
485
* The destructor will be called before the object is freed, either
486
* explicitly by nih_free() or nih_discard(), or because the last parent
487
* has unreferenced the object.
489
* When the destructor is called, the parent references to the object will
490
* have already been discarded but all children references will be intact
491
* and none of the children will have been freed. There is no need to use
492
* a destructor to unreference or free children, that is automatic.
494
* The pointer @ptr passed to the destructor is that of the object being
495
* freed, and the destructor may return a value which will be the return
496
* value of nih_free() or nih_discard() if used directly on the object.
498
* Since objects may also be freed by unreferencing, and the value is not
499
* returned in this case, it should only be used for informational or
500
* debugging purposes.
503
nih_alloc_real_set_destructor (const void * ptr,
504
NihDestructor destructor)
508
nih_assert (ptr != NULL);
510
ctx = NIH_ALLOC_CTX (ptr);
511
nih_assert (ctx->destructor != NIH_ALLOC_FINALISED);
513
ctx->destructor = destructor;
519
* @ptr: object to reference,
520
* @parent: new parent object.
522
* Adds a reference to the object @ptr from @parent, adding to any other
523
* objects referencing @ptr. The reference can be broken using nih_unref().
525
* @ptr will only be automatically freed when the last parent unreferences
526
* it. It may still be manually freed with nih_free(), though this doesn't
527
* sort out any pointers.
529
* This function is generally used when accepting an object that you wish
530
* to hold a reference to, which is cheaper than making a copy. The caller
531
* must be careful to only use nih_discard() or nih_unref() to drop its own
535
nih_ref (const void *ptr,
538
nih_assert (ptr != NULL);
539
nih_assert (parent != NULL);
541
nih_alloc_ref_new (NIH_ALLOC_CTX (parent), NIH_ALLOC_CTX (ptr));
546
* @parent: parent context,
547
* @child: child context.
549
* This is the internal function used by nih_ref() and nih_alloc() to
550
* create a new reference between the @parent and @child contexts.
552
* Returns: new reference, already linked to both objects.
554
static inline NihAllocRef *
555
nih_alloc_ref_new (NihAllocCtx *parent,
560
nih_assert (parent != NULL);
561
nih_assert (parent->destructor != NIH_ALLOC_FINALISED);
562
nih_assert (child != NULL);
563
nih_assert (child->destructor != NIH_ALLOC_FINALISED);
565
ref = NIH_MUST (malloc (sizeof (NihAllocRef)));
567
nih_list_init (&ref->children_entry);
568
nih_list_init (&ref->parents_entry);
570
ref->parent = parent;
573
nih_list_add_after (&parent->children, &ref->children_entry);
574
nih_list_add_after (&child->parents, &ref->parents_entry);
582
* @ptr: object to unreference,
583
* @parent: parent object to remove.
585
* Removes the reference to the object @ptr from @parent, if this is the
586
* last reference to @ptr then @ptr will be automatically freed.
588
* You never need to call this in your own destructors since children
589
* are unreferenced automatically, however this function is useful if you
590
* only hold a reference to an object for a short period and wish to
594
nih_unref (void * ptr,
600
nih_assert (ptr != NULL);
601
nih_assert (parent != NULL);
603
ctx = NIH_ALLOC_CTX (ptr);
604
nih_assert (ctx->destructor != NIH_ALLOC_FINALISED);
606
ref = nih_alloc_ref_lookup (NIH_ALLOC_CTX (parent), ctx);
608
nih_assert (ref != NULL);
609
nih_alloc_ref_free (ref);
611
if (NIH_LIST_EMPTY (&ctx->parents))
612
nih_alloc_context_free (ctx);
617
* @ptr: object to unreference,
618
* @parent: parent object to remove.
620
* Removes the reference to the object @ptr from @parent, but will not
621
* automatically free @ptr even if this is the last reference.
624
nih_unref_only (const void *ptr,
629
nih_assert (ptr != NULL);
630
nih_assert (parent != NULL);
632
ref = nih_alloc_ref_lookup (NIH_ALLOC_CTX (parent),
633
NIH_ALLOC_CTX (ptr));
635
nih_assert (ref != NULL);
636
nih_alloc_ref_free (ref);
640
* nih_alloc_ref_free:
641
* @ref: reference to free.
643
* This is the internal function used by nih_free(), nih_unref() and
644
* nih_unref_only() to remove the reference @ref from its parent and child
645
* contexts. It does not free the child context, even if this is the last
648
* This function is notably not called by nih_alloc_context_unref() since
649
* that manipulates the references to perform finalisation.
652
nih_alloc_ref_free (NihAllocRef *ref)
654
nih_assert (ref != NULL);
656
nih_list_destroy (&ref->children_entry);
657
nih_list_destroy (&ref->parents_entry);
665
* @ptr: object to query,
666
* @parent: parent object to look for.
668
* If @parent is NULL any parent will match.
670
* Returns: TRUE if @parent has a reference to @ptr, FALSE otherwise.
673
nih_alloc_parent (const void *ptr,
678
nih_assert (ptr != NULL);
680
ctx = NIH_ALLOC_CTX (ptr);
681
nih_assert (ctx->destructor != NIH_ALLOC_FINALISED);
686
ref = nih_alloc_ref_lookup (NIH_ALLOC_CTX (parent), ctx);
688
return ref ? TRUE : FALSE;
690
return NIH_LIST_EMPTY (&ctx->parents) ? FALSE : TRUE;
695
* nih_alloc_ref_lookup:
696
* @parent: parent context,
697
* @child: child context.
699
* This is the internal function used by nih_unref() and nih_alloc_parent()
700
* to lookup a reference between the @parent and @child contexts.
702
* Returns: NihAllocRef structure or NULL if no reference exists.
704
static inline NihAllocRef *
705
nih_alloc_ref_lookup (NihAllocCtx *parent,
708
nih_assert (parent != NULL);
709
nih_assert (parent->destructor != NIH_ALLOC_FINALISED);
710
nih_assert (child != NULL);
711
nih_assert (child->destructor != NIH_ALLOC_FINALISED);
713
NIH_LIST_FOREACH (&child->parents, iter) {
714
NihAllocRef *ref = NIH_LIST_ITER (iter, NihAllocRef,
717
if (ref->parent == parent)
727
* @ptr: pointer to object.
729
* Returns: the size of the allocated object, which may be larger than
730
* originally requested.
733
nih_alloc_size (const void *ptr)
737
nih_assert (ptr != NULL);
739
ctx = NIH_ALLOC_CTX (ptr);
740
nih_assert (ctx->destructor != NIH_ALLOC_FINALISED);
742
return malloc_usable_size (ctx) - sizeof (NihAllocCtx);
added
removed
nih/alloc.c
