ta: remove seperate internal "ext" header

The ta_ext_header was allocated on demand for allocations which have
child-allocations or destructors. In theory, it saved 2 words for every
TA leaf allocation. It had the very API-visible problem that setting a
parent or destructor could fail. (Although in most cases, the failure
was part of an allocation call anyway. Also, mpv code generally used the
early-failure variants, so it didn't matter.)

I think this was a bit too complex. These 2 words don't really matter;
if you have memory allocations where you are worried about overhead,
then these simply shouldn't use TA. Also, we never added new features to
TA that would have needed more "optional" header fields, which would
have justified the use of such a separately allocated header struct.

This uses quite straight-forward data structures. The only strange thing
is that ta_header.parent is NULL for most child allocations. That is
because we don't want to iterate over all children when the parent is
reallocated (yes, that is allowed, yes mpv makes use of it).

The new code has a few more special cases, because the list sentinel
concept isn't used anymore. Using it would have made the code more
unnatural/complex, because ta_ext_header doesn't exist anymore.

1 files changed, 54 insertions, 79 deletions

diff --git a/ta/ta.c b/ta/ta.c
index fffc1a6602..5f7a20072b 100644
--- a/ta/ta.c
+++ b/ta/ta.c
@@ -31,9 +31,13 @@
 
 struct ta_header {
     size_t size;                // size of the user allocation
-    struct ta_header *prev;     // ring list containing siblings
+    // Invariant: parent!=NULL => prev==NULL
+    struct ta_header *prev;     // siblings list (by destructor order)
     struct ta_header *next;
-    struct ta_ext_header *ext;
+    // Invariant: parent==NULL || parent->child==this
+    struct ta_header *child;    // points to first child
+    struct ta_header *parent;   // set for _first_ child only, NULL otherwise
+    void (*destructor)(void *);
 #ifdef TA_MEMORY_DEBUGGING
     unsigned int canary;
     struct ta_header *leak_next;
@@ -59,16 +63,6 @@ union aligned_header {
 
 #define MAX_ALLOC (((size_t)-1) - sizeof(union aligned_header))
 
-// Needed for non-leaf allocations, or extended features such as destructors.
-struct ta_ext_header {
-    struct ta_header *header;  // points back to normal header
-    struct ta_header children; // list of children, with this as sentinel
-    void (*destructor)(void *);
-};
-
-// ta_ext_header.children.size is set to this
-#define CHILDREN_SENTINEL ((size_t)-1)
-
 static void ta_dbg_add(struct ta_header *h);
 static void ta_dbg_check_header(struct ta_header *h);
 static void ta_dbg_remove(struct ta_header *h);
@@ -80,29 +74,6 @@ static struct ta_header *get_header(void *ptr)
     return h;
 }
 
-static struct ta_ext_header *get_or_alloc_ext_header(void *ptr)
-{
-    struct ta_header *h = get_header(ptr);
-    if (!h)
-        return NULL;
-    if (!h->ext) {
-        h->ext = malloc(sizeof(struct ta_ext_header));
-        if (!h->ext)
-            return NULL;
-        *h->ext = (struct ta_ext_header) {
-            .header = h,
-            .children = {
-                .next = &h->ext->children,
-                .prev = &h->ext->children,
-                // Needed by ta_find_parent():
-                .size = CHILDREN_SENTINEL,
-                .ext = h->ext,
-            },
-        };
-    }
-    return h->ext;
-}
-
 /* Set the parent allocation of ptr. If parent==NULL, remove the parent.
  * Setting parent==NULL (with ptr!=NULL) always succeeds, and unsets the
  * parent of ptr. Operations ptr==NULL always succeed and do nothing.
@@ -117,22 +88,31 @@ bool ta_set_parent(void *ptr, void *ta_parent)
     struct ta_header *ch = get_header(ptr);
     if (!ch)
         return true;
-    struct ta_ext_header *parent_eh = get_or_alloc_ext_header(ta_parent);
-    if (ta_parent && !parent_eh) // do nothing on OOM
-        return false;
+    struct ta_header *new_parent = get_header(ta_parent);
     // Unlink from previous parent
-    if (ch->next) {
-        ch->next->prev = ch->prev;
+    if (ch->prev)
         ch->prev->next = ch->next;
-        ch->next = ch->prev = NULL;
+    if (ch->next)
+        ch->next->prev = ch->prev;
+    // If ch was the firs child, change child link of old parent
+    if (ch->parent) {
+        assert(ch->parent->child == ch);
+        ch->parent->child = ch->next;
+        if (ch->parent->child) {
+            assert(!ch->parent->child->parent);
+            ch->parent->child->parent = ch->parent;
+        }
     }
-    // Link to new parent - insert at end of list (possibly orders destructors)
-    if (parent_eh) {
-        struct ta_header *children = &parent_eh->children;
-        ch->next = children;
-        ch->prev = children->prev;
-        children->prev->next = ch;
-        children->prev = ch;
+    ch->next = ch->prev = ch->parent = NULL;
+    // Link to new parent - insert at start of list (LIFO destructor order)
+    if (new_parent) {
+        ch->next = new_parent->child;
+        if (ch->next) {
+            ch->next->prev = ch;
+            ch->next->parent = NULL;
+        }
+        new_parent->child = ch;
+        ch->parent = new_parent;
     }
     return true;
 }
@@ -205,6 +185,7 @@ void *ta_realloc_size(void *ta_parent, void *ptr, size_t size)
     struct ta_header *old_h = h;
     if (h->size == size)
         return ptr;
+    bool first_child = h->parent && h->parent->child == h;
     ta_dbg_remove(h);
     h = realloc(h, sizeof(union aligned_header) + size);
     ta_dbg_add(h ? h : old_h);
@@ -212,17 +193,17 @@ void *ta_realloc_size(void *ta_parent, void *ptr, size_t size)
         return NULL;
     h->size = size;
     if (h != old_h) {
-        if (h->next) {
-            // Relink siblings
+        // Relink parent
+        if (first_child)
+            h->parent->child = h;
+        // Relink siblings
+        if (h->next)
             h->next->prev = h;
+        if (h->prev)
             h->prev->next = h;
-        }
-        if (h->ext) {
-            // Relink children
-            h->ext->header = h;
-            h->ext->children.next->prev = &h->ext->children;
-            h->ext->children.prev->next = &h->ext->children;
-        }
+        // Relink children
+        if (h->child)
+            h->child->parent = h;
     }
     return PTR_FROM_HEADER(h);
 }
@@ -243,11 +224,8 @@ size_t ta_get_size(void *ptr)
 void ta_free_children(void *ptr)
 {
     struct ta_header *h = get_header(ptr);
-    struct ta_ext_header *eh = h ? h->ext : NULL;
-    if (!eh)
-        return;
-    while (eh->children.prev != &eh->children)
-        ta_free(PTR_FROM_HEADER(eh->children.prev));
+    while (h && h->child)
+        ta_free(PTR_FROM_HEADER(h->child));
 }
 
 /* Free the given allocation, and all of its direct and indirect children.
@@ -257,16 +235,11 @@ void ta_free(void *ptr)
     struct ta_header *h = get_header(ptr);
     if (!h)
         return;
-    if (h->ext && h->ext->destructor)
-        h->ext->destructor(ptr);
+    if (h->destructor)
+        h->destructor(ptr);
     ta_free_children(ptr);
-    if (h->next) {
-        // Unlink from sibling list
-        h->next->prev = h->prev;
-        h->prev->next = h->next;
-    }
+    ta_set_parent(ptr, NULL);
     ta_dbg_remove(h);
-    free(h->ext);
     free(h);
 }
 
@@ -284,10 +257,10 @@ void ta_free(void *ptr)
  */
 bool ta_set_destructor(void *ptr, void (*destructor)(void *))
 {
-    struct ta_ext_header *eh = get_or_alloc_ext_header(ptr);
-    if (!eh)
+    struct ta_header *h = get_header(ptr);
+    if (!h)
         return false;
-    eh->destructor = destructor;
+    h->destructor = destructor;
     return true;
 }
 
@@ -315,8 +288,13 @@ static void ta_dbg_add(struct ta_header *h)
 
 static void ta_dbg_check_header(struct ta_header *h)
 {
-    if (h)
+    if (h) {
         assert(h->canary == CANARY);
+        if (h->parent) {
+            assert(!h->prev);
+            assert(h->parent->child == h);
+        }
+    }
 }
 
 static void ta_dbg_remove(struct ta_header *h)
@@ -335,11 +313,8 @@ static void ta_dbg_remove(struct ta_header *h)
 static size_t get_children_size(struct ta_header *h)
 {
     size_t size = 0;
-    if (h->ext) {
-        struct ta_header *s;
-        for (s = h->ext->children.next; s != &h->ext->children; s = s->next)
-            size += s->size + get_children_size(s);
-    }
+    for (struct ta_header *s = h; s; s = s->next)
+        size += s->size + get_children_size(s);
     return size;
 }