From b63a7cc2e041ecffd46183cd61923f532c13d113 Mon Sep 17 00:00:00 2001 From: Jakub Jermar Date: Mon, 6 Nov 2006 20:19:56 +0000 Subject: [PATCH] Rewrite ofw_tree_node_process() to iterate through the peer list instead of recursing. --- boot/genarch/ofw_tree.c | 189 ++++++++++++++++++++++++++---------------------- 1 file changed, 104 insertions(+), 85 deletions(-) diff --git a/boot/genarch/ofw_tree.c b/boot/genarch/ofw_tree.c index 2ca6a84ab..5ab96227e 100644 --- a/boot/genarch/ofw_tree.c +++ b/boot/genarch/ofw_tree.c @@ -69,7 +69,8 @@ static void * ofw_tree_space_alloc(size_t size) * * Transfer entire information from the OpenFirmware device tree 'current' node to * its memory representation in 'current_node'. This function recursively processes - * all node's peers and children. + * all node's children. Node's peers are processed iteratively in order to prevent + * stack from overflowing. * * @param current_node Pointer to uninitialized ofw_tree_node structure that will * become the memory represenation of 'current'. @@ -83,114 +84,132 @@ static void ofw_tree_node_process(ofw_tree_node_t *current_node, static char name[OFW_TREE_PROPERTY_MAX_NAMELEN]; phandle peer; phandle child; - unsigned properties = 0; size_t len; int i; - /* - * Initialize node. - */ - current_node->parent = parent_node; - current_node->peer = NULL; - current_node->child = NULL; - current_node->node_handle = current; - current_node->properties = 0; - current_node->property = NULL; - current_node->device = NULL; + while (current_node) { + /* + * Initialize node. + */ + current_node->parent = parent_node; + current_node->peer = NULL; + current_node->child = NULL; + current_node->node_handle = current; + current_node->properties = 0; + current_node->property = NULL; + current_node->device = NULL; - /* - * Get the disambigued name. - */ - len = ofw_package_to_path(current, path, MAX_PATH_LEN); - if (len == -1) - return; + /* + * Get the disambigued name. + */ + len = ofw_package_to_path(current, path, MAX_PATH_LEN); + if (len == -1) + return; - path[len] = '\0'; - for (i = len - 1; i >= 0 && path[i] != '/'; i--) - ; - i++; /* do not include '/' */ + path[len] = '\0'; + for (i = len - 1; i >= 0 && path[i] != '/'; i--) + ; + i++; /* do not include '/' */ - len -= i; - current_node->da_name = ofw_tree_space_alloc(len + 1); /* add space for trailing '\0' */ - if (!current_node->da_name) - return; + len -= i; + + /* add space for trailing '\0' */ + current_node->da_name = ofw_tree_space_alloc(len + 1); + if (!current_node->da_name) + return; - memcpy(current_node->da_name, &path[i], len); - current_node->da_name[len] = '\0'; + memcpy(current_node->da_name, &path[i], len); + current_node->da_name[len] = '\0'; - /* - * Recursively process the potential peer node. - */ - peer = ofw_get_peer_node(current); - if (peer != 0 && peer != -1) { - ofw_tree_node_t *peer_node; - - peer_node = ofw_tree_node_alloc(); - if (peer_node) { - ofw_tree_node_process(peer_node, parent_node, peer); - current_node->peer = peer_node; - } - } - /* - * Recursively process the potential child node. - */ - child = ofw_get_child_node(current); - if (child != 0 && child != -1) { - ofw_tree_node_t *child_node; + /* + * Recursively process the potential child node. + */ + child = ofw_get_child_node(current); + if (child != 0 && child != -1) { + ofw_tree_node_t *child_node; - child_node = ofw_tree_node_alloc(); - if (child_node) { - ofw_tree_node_process(child_node, current_node, child); - current_node->child = child_node; + child_node = ofw_tree_node_alloc(); + if (child_node) { + ofw_tree_node_process(child_node, current_node, child); + current_node->child = child_node; + } } - } - /* - * Count properties. - */ - name[0] = '\0'; - while (ofw_next_property(current, name, name) == 1) - current_node->properties++; + /* + * Count properties. + */ + name[0] = '\0'; + while (ofw_next_property(current, name, name) == 1) + current_node->properties++; - if (!current_node->properties) - return; + if (!current_node->properties) + return; - /* - * Copy properties. - */ - current_node->property = ofw_tree_properties_alloc(current_node->properties); - if (!current_node->property) - return; + /* + * Copy properties. + */ + current_node->property = ofw_tree_properties_alloc(current_node->properties); + if (!current_node->property) + return; - name[0] = '\0'; - for (i = 0; ofw_next_property(current, name, name) == 1; i++) { - size_t size; + name[0] = '\0'; + for (i = 0; ofw_next_property(current, name, name) == 1; i++) { + size_t size; - if (i == current_node->properties) - break; + if (i == current_node->properties) + break; - memcpy(current_node->property[i].name, name, OFW_TREE_PROPERTY_MAX_NAMELEN); - current_node->property[i].name[OFW_TREE_PROPERTY_MAX_NAMELEN] = '\0'; + memcpy(current_node->property[i].name, name, + OFW_TREE_PROPERTY_MAX_NAMELEN); + current_node->property[i].name[OFW_TREE_PROPERTY_MAX_NAMELEN] = '\0'; - size = ofw_get_proplen(current, name); - current_node->property[i].size = size; - if (size) { - void *buf; + size = ofw_get_proplen(current, name); + current_node->property[i].size = size; + if (size) { + void *buf; - buf = ofw_tree_space_alloc(size); - if (current_node->property[i].value = buf) { + buf = ofw_tree_space_alloc(size); + if (current_node->property[i].value = buf) { + /* + * Copy property value to memory node. + */ + (void) ofw_get_property(current, name, buf, size); + } + } else { + current_node->property[i].value = NULL; + } + } + + current_node->properties = i; /* Just in case we ran out of memory. */ + + /* + * Iteratively process the next peer node. + * Note that recursion is a bad idea here. + * Due to the topology of the OpenFirmware device tree, + * the nesting of peer nodes could be to wide and the + * risk of overflowing the stack is too real. + */ + peer = ofw_get_peer_node(current); + if (peer != 0 && peer != -1) { + ofw_tree_node_t *peer_node; + + peer_node = ofw_tree_node_alloc(); + if (peer_node) { + current_node->peer = peer_node; + current_node = peer_node; + current = peer; /* - * Copy property value to memory node. + * Process the peer in next iteration. */ - (void) ofw_get_property(current, name, buf, size); + continue; } - } else { - current_node->property[i].value = NULL; } + /* + * No more peers on this level. + */ + break; } - - current_node->properties = i; /* Just in case we ran out of memory. */ } /** Construct memory representation of OpenFirmware device tree. -- 2.11.4.GIT