* Depth-First Search (DFS) through previously constructed * Control Flow Graph (CFG). * Information collected at this path would be used later * to determine is there any loops, and/or unreachable instructions. */
| 1888 | * to determine is there any loops, and/or unreachable instructions. |
| 1889 | */ |
| 1890 | static void |
| 1891 | dfs(struct bpf_verifier *bvf) |
| 1892 | { |
| 1893 | struct inst_node *next, *node; |
| 1894 | |
| 1895 | node = bvf->in; |
| 1896 | while (node != NULL) { |
| 1897 | |
| 1898 | if (node->colour == WHITE) |
| 1899 | set_node_colour(bvf, node, GREY); |
| 1900 | |
| 1901 | if (node->colour == GREY) { |
| 1902 | |
| 1903 | /* find next unprocessed child node */ |
| 1904 | do { |
| 1905 | next = get_next_node(bvf, node); |
| 1906 | if (next == NULL) |
| 1907 | break; |
| 1908 | set_edge_type(bvf, node, next); |
| 1909 | } while (next->colour != WHITE); |
| 1910 | |
| 1911 | if (next != NULL) { |
| 1912 | /* proceed with next child */ |
| 1913 | next->prev_node = get_node_idx(bvf, node); |
| 1914 | node = next; |
| 1915 | } else { |
| 1916 | /* |
| 1917 | * finished with current node and all it's kids, |
| 1918 | * proceed with parent |
| 1919 | */ |
| 1920 | set_node_colour(bvf, node, BLACK); |
| 1921 | node->cur_edge = 0; |
| 1922 | node = get_prev_node(bvf, node); |
| 1923 | } |
| 1924 | } else |
| 1925 | node = NULL; |
| 1926 | } |
| 1927 | } |
| 1928 | |
| 1929 | /* |
| 1930 | * report unreachable instructions. |
no test coverage detected