Walking a Process Tree

Walking the process tree in the linux kernel

Indeed you kernel crash probably happens because you are using a recursive function.

You could just use a very simple loop instead of your recursive function... Do you come from a functional programming only world? A while loop is standard in C, but if you really want to use a goto you could... ;) Here is the code using a loop.

void parent_task_walk(struct task_struct* task) 
{

    struct task_struct *parent = NULL;
    char filename[MAX_FILE_LEN];


    while (task && task->mm) {

        parent = get_task_parent(task);

        printk("%s (uid:%d)",
               exe_from_mm(task->mm, filename, MAX_FILE_LEN),
               get_task_uid(task));

        if (parent && task->pid != 1)
            printk(", ");

        task = parent;
    }

}

In C#, how to kill a process tree reliably

Use ManagmentObjectSearcher and a little recursion:

private static void KillProcessAndChildren(int pid)
{
    ManagementObjectSearcher searcher = new ManagementObjectSearcher
      ("Select * From Win32_Process Where ParentProcessID=" + pid);
    ManagementObjectCollection moc = searcher.Get();
    foreach (ManagementObject mo in moc)
    {
        KillProcessAndChildren(Convert.ToInt32(mo["ProcessID"]));
    }
    try
    {
        Process proc = Process.GetProcessById(pid);
        proc.Kill();
    }
    catch (ArgumentException)
    {
        // Process already exited.
    }
 }

Walking a hierarchical tree

I think what you need essentially is the cophenetic correlation coefficient of the dendrogram.
It will tell you the heights of all splitting points. From there you can easily walk through the tree.
I made an attempt below and store all submatrices to a list "submatrices". It's a nested list. The first level is the submatrices from all splitting points. The second level is the submatrices from a splitting point.
For example, if you want all submatrices from the 1st splitting point (grey and blue clusters), it should be submatrices[[1]]. If you want the first submatrix (red cluster) from submatrices[[1]], it should be submatrices[[1]][1].

splitme <- function(data, minH){
  ##Compute dist matrix and clustering dendrogram
  d <- dist(data)
  cl <- hclust(d)
  hc <- as.dendrogram(cl)

  ##Get the cophenetic correlation coefficient matrix (cccm)
  cccm <- round(cophenetic(hc), digits = 0)

  #Get the heights of spliting points (sps)
  sps <- sort(unique(cccm), decreasing = T)

  #This list store all the submatrices
  #The submatrices extract from the nth splitting points
  #(top splitting point being the 1st whereas bottom splitting point being the last)
  submatrices <- list()

  #Iterate/Walk the dendrogram
  i <- 2 #Starting from 2 as the 1st value will give you the entire dendrogram as a whole
  while(sps[i] > minH){
    membership <- cutree(cl, h=sps[i]) #Cut the tree at splitting points
    lst <- list() #Create a list to store submatrices extract from a splitting point
    for(j in 1:max(membership)){
      member <- which(membership == j) #Get the corresponding data entry to create the submatrices
      df <- data.frame()
      for(p in member){
        df <- rbind(df, data[p, ])
        colnames(df) <- colnames(data)
        dm <- dist(df)
      }
      lst <- append(lst, list(dm)) #Append all submatrices from a splitting point to lst
    }
    submatrices <- append(submatrices, list(lst)) #Append the lst to submatrices list
    i <- i + 1
  }
  return(submatrices)
}

walking a tree with Promises

Well it isn't much of a problem to handle a function call for each node, but gathering the node values is kind of a problem. Kind of hard to walk that tree, your best bet would be to map it to a tree with no eventual values. You could use something like:

function buildTree(root_name) {
    var prom = getNodeAsync(root_name);
    return Promise.all([prom, prom.then(function(n){
        return Promise.all(childrenNamesOf(n).map(child => buildTree(child)))
    })]);
}

From there on you do:

var flatTree = buildTree(root_name).then(flatArray);
flatTree.then(nodes => nodes.forEach(visit_fn));
flatTree.then(nodes => whateverYouWantToDoWithNodes);

To flatten the array you could use:

function flatArray(nodes){
    if(Array.isArray(nodes) && nodes.length){
        return nodes.reduce(function(n, a){
                return flatArray(n).concat(flatArray(a));
        });
    } else {
        return Array.isArray(nodes) ? nodes : [nodes];
    }
}

To be honest, it's pointless to have the tree walker if you want a list of nodes you are better up flattening it up and then iterating the elements, but you can walk the array tree if you want.

Iterative tree walking

If you are doing a breadth first search the natural implementation is to push nodes into a queue, not to use recursion.

If you are doing a depth first search then recursion is the most natural way to code the traversal. However, unless your compiler optimizes tail recursion into iteration, your recursive implementation will be slower than an iterative algorithm, and will die with a stack overflow on a deep enough tree.

Some quick Python to illustrate the difference:

#A tree is a tuple of an int and a tree. 
t = (1, (2,(4, (6), (7, (9)) )), (3, (5, (8)) ))
def bfs(t):
    to_visit = [t]
    while len(to_visit) > 0:
        c = to_visit[0]
        if type(c) is int:
            print c
        else: 
            print c[0]
            to_visit.append(c[1])
            if len(c) > 2: to_visit.append(c[2])
        to_visit = to_visit[1:]

def dfs(t):
    if type(t) is int:
        print t
        return 
    print t[0]
    dfs(t[1])
    if len(t) > 2: dfs(t[2]) 

bfs(t)
dfs(t)

Performing equivalent of Kill Process Tree in C++ on windows

You might want to consider the "Jobs API". CreateJobObject and friends. You can enforce children processes to stay within the Job, by setting appropriate attribute. Then you can call TerminateJobObject whenever you want.

Clarification: this is NOT what Task Manager does.

Terminate process tree in PowerShell given a process ID

So I couldn't really find a good way to do this, so I wrote a helper function that uses recursion to walk down the process tree:

function Kill-Tree {
    Param([int]$ppid)
    Get-CimInstance Win32_Process | Where-Object { $_.ParentProcessId -eq $ppid } | ForEach-Object { Kill-Tree $_.ProcessId }
    Stop-Process -Id $ppid
}

To use it, put it somewhere in your PowerShell script, and then just call it like so:

Kill-Tree <process_id>

---

Related Topics