(Feedback) Add /delete-if-unreferenced/

[kevans91]

[This pull request is intended to seek feedback]

/delete-if-unreferenced/ is a feature that's been pitched to GPL dtc for removing nodes that aren't referenced in the final device tree. It has not been merged yet. The expected use case is to delete pinctrl nodes and similar things that exist in an SOC .dtsi but remain ultimately unused in the final DTS because that particular board doesn't use or require them.

This does at least function and my test is correct- I'll add comments inline.

[kevans91]

I've got a new version that basically moves all of the garbage collection into resolve_cross_references (and adds to the corresponding comment that garbage collection will also be done here). It gets a little dirtier using the visit() stuff, because I ended up modifying visit() to keep track of the parent, pass that into fn, and alow fn to indicate whether or not the recursion into children should happen. I'm not sure if this is desirable, or if this is a change that would almost require a different form of visit since it's not really standard behavior.

My addition to resolve_cross_references is basically:

    // Begin garbage collection
    int nodes_removed = 0;
    do {
        // Map a node for deletion to its parent for later deletion
        std::map<node *, node *> garbage_nodes;
        root->visit([&](node &n, node *parent) {
            if (n.delete_if_unreferenced)
            {
                // Are we referenced?
                if (referenced_nodes.find(&n) == referenced_nodes.end() ||
                    referenced_nodes[&n] == 0)
                {
                    garbage_nodes[&n] = parent;
                    return false;
                }
            }
            return true;
        }, nullptr);
        nodes_removed = garbage_nodes.size();
        for (auto iter : garbage_nodes)
        {
            node *parent = iter.second;

        }
    } while (nodes_removed > 0);

What I'm not yet sure of is how I'll physically delete the nodes from garbage_nodes (see other comment made); I'm thinking the device_tree is going to have to become a friend of the node, unless I move garbage collection into node and have the local referenced_nodes from resolve_cross_references get passed into there.

[davidchisnall]

I think you need to repeat your visit thing. I thought that the existing visitor stuff let you choose whether to recurse but returning a different value, but apparently it doesn't (that would be a good addition!).

The basic algorithm that I think you need to use is:

1. Visit all nodes that are not delete-if-unused.
2. For each one, mark everything it sees as used.
3. Visit each of the newly marked nodes and repeat step 2.
4. Repeat step 3 until step 3 stops finding new reachable nodes.
5. Do a scan to mark

I'd be tempted to add a used property to each node (maybe make delete_if_unreferenced and used bitfields, so we're not using any more space) and then set this flag, so that we get a constant-time check on whether we've seen a node before.

[kevans91]

Hmm... doing this would require some more re-working, then. Step 2 in your algorithm is going to incur another tree walk just to figure out which node we're referencing, unless I'm missing something- it seems we only carry the phandles for each property, rather than a convenient node pointer.

[davidchisnall]

I think that we already collect a map from phandle to node. If we don't, then an initial walk should let you construct one. You can also set a per-FDT flag to indicate that any nodes are delete-if-unreferenced and skip the entire step if none are.

[kevans91]

This has landed in GPL DTC 1.4.7 as "/omit-if-no-ref/" -- I'll revisit this shortly, now that it's appeared in an actual release.

[davidchisnall]

This looks a lot more like it should work, but please can we have some tests for the complicated cases (i.e. ones where we need multiple iterations to determine if a node is actually referenced). It's not completely clear to me that you're correctly handling some of the nested cases. If I have something like this, does it work?

/ {
    /omit-if-no-ref/ outer@2 {
        inner@4 {
            inner2@1 {
                test-property = <&outer@2>;
            }
        }
    };
};

Does the inner reference make this live, or is it correctly deleted (does GPL'd dtc do this correctly?) What happens if you have two structures like this that reference eachother? I'd expect both to be deleted, is that what happens in the GPL'd version?

[kevans91]

Right, I plan to add a lot more tests once I get it to actually work. =)

I introduced a dependency on the resolve_cross_reference phase that I think I don't necessarily want. I'm going to rewrite parts of this in my next chunk of free time to move the garbage collection somewhere in the middle of resolve_cross_references. This has some benefits:

• We don't have to do anywhere near as much to clean up after nodes being removed from the tree
• We can yoink nodes prior to any of the... synthetic? nodes getting written (symbols, fixups, local fixups)

It's not clear how far we want to go in weeding out corner cases here, but I'll certainly do some testing to see how far GPL dtc goes. This feature is generally used in incredibly simple scenarios to remove pinctrl nodes from an SoC .dtsi for boards that aren't ever going to use them in more heavily space-constrained environments like U-Boot/SPL, and I suspect the rest of the world doesn't really care about garbage collecting things from DTS because the savings are negligible in comparison.

[kevans91]

I think I'm done dorking with it for now. FWIW- dtc does exhibit the same behavior that I have now. I think it makes the most sense, to be honest. Given that structure:

/ {
    /omit-if-no-ref/ out: outer@2 {
        inner@4 {
            inner2@1 {
                test-property = <&out>;
            };
        };
    };
};

We don't actually know, ultimately, that this is how the node was originally constructed. Due to node merging across multiple .dts/.dtsi, inner2 could've been merged in later and it's hard to say that this reference shouldn't keep that entire section of the tree alive. Granted, I can't really think of a practical situation where this would be true, I think it's better to err on the side of caution when we're trimming things out and it's not cut and dry.

[davidchisnall]

It would be quite nice to have a warning when the node that is keeping something live is a child of the node that it's finding, because that's almost certainly not intentional.

[kevans91]

Thanks; expect a follow-up PR in the next day or so.