Bugs in the new IPTraffic v2 code (Shibby and others based on same code)

Discussion in 'Tomato Firmware' started by RMerlin, Dec 9, 2012.

  1. RMerlin

    RMerlin Network Guru Member


    While implementing cstats/IPTraffic v2 into Asuswrt-Merlin reusing the code from Shibby's Tomato I ran into a bug or two. Took a while to track down, but I finally got it working reliably.

    Multiple calls to asp_iptraffic() in the httpd will end up in the httpd process crashing after 2-3 calls. The issue is caused by the last line where it clears the tree:

    TREE_FORWARD_APPLY(&tree, _Node, linkage, Node_housekeeping, NULL);
    Turns out the tree was corrupted/had invalid pointers in it after that call. There are a few problems here causing this:

    1) TREE_FORWARD_APPLY() cannot be used to recursively free and remove all nodes. Once you remove a node, then the tree gets shifted, meaning you might no longer have a pointer to your (former) neighbour. This means that in a tree with 10-12 nodes, that call will only be able to free up 3-4 nodes on average, leaving the rest there. That means a memory leak over time, or nodes getting reused in subsequent calls (when they shouldn't).

    2) The Housekeeping helper function used there does a free(node) before trying to access that node's pointers as it tries to TREE_REMOVE it. This can lead to a crash if that node's content were to be modified by another process between the free() call and the TREE_REMOVE.

    3) Once you start removing nodes from a tree, the tree seems to be left in an invalid state. That's where a subsequent call to asp_iptraffic() often results in a segfault in httpd.

    What I did to fix these issues here:

    1) I modified the Housekeeping helper in httpd/iptraffic.h to free() the node without removing it. It now looks like this:

    void Node_housekeeping(Node *self, void *info) {
    That way, the recursive TREE_FORWARD_APPLY will go through every node, freeing the memory allocated for all nodes. I was able to confirm it by inserting a printf() call in the housekeeping() function - I always had as many calls there as I had nodes in my tree.

    2) I modified the tree.h main file so TREE_FORWARD_APPLY_ALL will keep a copy of the pointer to the next node before calling the helper function (which in this case free()s the memory) and trying to access the next node.. That means even if your helper function frees the memory, you can still safely continue walking down (or right in this case) the tree. This is the modified function inside tree.h:

     void TREE_FORWARD_APPLY_ALL_##node##_##field                                                          \
        (struct node *self, void (*function)(struct node *node, void *data), void *data)                    \
      {                                                                                                    \
        if (self)                                                                                          \
          {                                                                                                \
            TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_left, function, data);                  \
            struct node *right = self->field.avl_right; /* Preserve before removing */                      \
            function(self, data);                                                                          \
            TREE_FORWARD_APPLY_ALL_##node##_##field(right, function, data);                                \
          }                                                                                                \
    3) After freeing all nodes in my tree in asp_iptraffic(), I re-initialize the tree's head. So the end of asp_iptraffic() now looks like this:

            websWrite(wp, "];\n");
            TREE_FORWARD_APPLY(&tree, _Node, linkage, Node_housekeeping, NULL);
            TREE_INIT(&tree, Node_compare);
    Apologies for not providing proper diff files, but my codebase is laid down somewhat differently from Tomato :)
  2. koitsu

    koitsu Network Guru Member

    Very, very nice find. (See folks, I kept telling you that IPTraffic feature had some kind of leak in it, sigh... :) )

    Your fix makes sense to me, at least mostly. However, you should declare struct node *right at the top of the TREE_FORWARD_APPLY_ALL() function/macro, and not where you do (hell, I'm surprised the compiler lets you get away with that!). I.e. the function/macro should look like this (I'm not going to bother typing in all the damn line continuation characters BTW):

    void TREE_FORWARD_APPLY_ALL_...whatever... ( ... ) {
      if (self) {
        struct node *right;
        right = self->field.avl_right;
        function(self, data);
    It's funny that all of this is userland-based; in FreeBSD we have entire system-wide macros and functions that provide trees and linked-lists for us. I'm surprised Linux doesn't have something similar; then again it may, but maybe not in uClibc. :(
  3. RMerlin

    RMerlin Network Guru Member

    I remember linked lists from back in my AmigaOS development days (in the early 90s). The OS relied heavily on these, especially Exec, the Amiga kernel/executive. They were quite nice to play with, tho more basic than modern tree systems, and probably not designed to easily handle the large amount of data handled these days.

    All of this AVL tree macro stuff seems to have been written to be as compact as possible, with a lot of on-the-fly stuff. I simply kept the same coding style as the rest of that file, where declarations are commonly combined with assignments in other macros.
  4. kthaddock

    kthaddock Network Guru Member

    Nice finding !
    If I remember rigt is Teaman author of that code. I haven't seen him here for a while.
  5. RMerlin

    RMerlin Network Guru Member

    That's correct. I tried to find his Email address, but all I could find on his Google repo was a truncated address( to fend off spammers). After 10 mins of digging I gave up and simply posted this here.
  6. kthaddock

    kthaddock Network Guru Member


    You get PM.
  7. RMerlin

    RMerlin Network Guru Member

    Thanks. I'll send him an Email pointing to that thread.
  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice