New upstream version 3.0.3upstream/3.0.3

1 files changed, 375 insertions, 103 deletions

diff --git a/ProcessList.c b/ProcessList.c
index aa529d5..2d27339 100644
--- a/ProcessList.c
+++ b/ProcessList.c
@@ -1,33 +1,42 @@
 /*
 htop - ProcessList.c
 (C) 2004,2005 Hisham H. Muhammad
-Released under the GNU GPL, see the COPYING file
+Released under the GNU GPLv2, see the COPYING file
 in the source distribution for its full text.
 */
 
 #include "ProcessList.h"
-#include "Platform.h"
-
-#include "CRT.h"
-#include "StringUtils.h"
 
+#include <assert.h>
 #include <stdlib.h>
 #include <string.h>
+#include <time.h>
+
+#include "CRT.h"
+#include "Hashtable.h"
+#include "Macros.h"
+#include "Vector.h"
+#include "XUtils.h"
 
 
-ProcessList* ProcessList_init(ProcessList* this, ObjectClass* klass, UsersTable* usersTable, Hashtable* pidMatchList, uid_t userId) {
+ProcessList* ProcessList_init(ProcessList* this, const ObjectClass* klass, UsersTable* usersTable, Hashtable* pidMatchList, uid_t userId) {
    this->processes = Vector_new(klass, true, DEFAULT_SIZE);
-   this->processTable = Hashtable_new(140, false);
+   this->processes2 = Vector_new(klass, true, DEFAULT_SIZE); // tree-view auxiliary buffer
+
+   this->processTable = Hashtable_new(200, false);
+   this->displayTreeSet = Hashtable_new(200, false);
+   this->draftingTreeSet = Hashtable_new(200, false);
+
    this->usersTable = usersTable;
    this->pidMatchList = pidMatchList;
-   this->userId = userId;
 
-   // tree-view auxiliary buffer
-   this->processes2 = Vector_new(klass, true, DEFAULT_SIZE);
+   this->userId = userId;
 
    // set later by platform-specific code
    this->cpuCount = 0;
 
+   this->scanTs = 0;
+
 #ifdef HAVE_LIBHWLOC
    this->topologyOk = false;
    if (hwloc_topology_init(&this->topology) == 0) {
@@ -57,9 +66,13 @@ void ProcessList_done(ProcessList* this) {
       hwloc_topology_destroy(this->topology);
    }
 #endif
+
+   Hashtable_delete(this->draftingTreeSet);
+   Hashtable_delete(this->displayTreeSet);
    Hashtable_delete(this->processTable);
-   Vector_delete(this->processes);
+
    Vector_delete(this->processes2);
+   Vector_delete(this->processes);
 }
 
 void ProcessList_setPanel(ProcessList* this, Panel* panel) {
@@ -68,20 +81,31 @@ void ProcessList_setPanel(ProcessList* this, Panel* panel) {
 
 void ProcessList_printHeader(ProcessList* this, RichString* header) {
    RichString_prune(header);
-   ProcessField* fields = this->settings->fields;
+
+   const ProcessField* fields = this->settings->fields;
+
    for (int i = 0; fields[i]; i++) {
       const char* field = Process_fields[fields[i]].title;
-      if (!field) field = "- ";
-      if (!this->settings->treeView && this->settings->sortKey == fields[i])
-         RichString_append(header, CRT_colors[PANEL_SELECTION_FOCUS], field);
-      else
-         RichString_append(header, CRT_colors[PANEL_HEADER_FOCUS], field);
+      if (!field) {
+         field = "- ";
+      }
+
+      int color = (this->settings->sortKey == fields[i]) ?
+         CRT_colors[PANEL_SELECTION_FOCUS] : CRT_colors[PANEL_HEADER_FOCUS];
+      RichString_append(header, color, field);
+      if (COMM == fields[i] && this->settings->showMergedCommand) {
+         RichString_append(header, color, "(merged)");
+      }
    }
 }
 
 void ProcessList_add(ProcessList* this, Process* p) {
    assert(Vector_indexOf(this->processes, p, Process_pidCompare) == -1);
    assert(Hashtable_get(this->processTable, p->pid) == NULL);
+   p->processList = this;
+
+   // highlighting processes found in first scan by first scan marked "far in the past"
+   p->seenTs = this->scanTs;
 
    Vector_add(this->processes, p);
    Hashtable_put(this->processTable, p->pid, p);
@@ -94,132 +118,339 @@ void ProcessList_add(ProcessList* this, Process* p) {
 void ProcessList_remove(ProcessList* this, Process* p) {
    assert(Vector_indexOf(this->processes, p, Process_pidCompare) != -1);
    assert(Hashtable_get(this->processTable, p->pid) != NULL);
+
    Process* pp = Hashtable_remove(this->processTable, p->pid);
    assert(pp == p); (void)pp;
+
    unsigned int pid = p->pid;
    int idx = Vector_indexOf(this->processes, p, Process_pidCompare);
    assert(idx != -1);
-   if (idx >= 0) Vector_remove(this->processes, idx);
+
+   if (idx >= 0) {
+      Vector_remove(this->processes, idx);
+   }
+
    assert(Hashtable_get(this->processTable, pid) == NULL); (void)pid;
    assert(Hashtable_count(this->processTable) == Vector_count(this->processes));
 }
 
 Process* ProcessList_get(ProcessList* this, int idx) {
-   return (Process*) (Vector_get(this->processes, idx));
+   return (Process*)Vector_get(this->processes, idx);
 }
 
 int ProcessList_size(ProcessList* this) {
-   return (Vector_size(this->processes));
+   return Vector_size(this->processes);
+}
+
+// ProcessList_updateTreeSetLayer sorts this->displayTreeSet,
+// relying only on itself.
+//
+// Algorithm
+//
+// The algorithm is based on `depth-first search`,
+// even though `breadth-first search` approach may be more efficient on first glance,
+// after comparision it may be not, as it's not safe to go deeper without first updating the tree structure.
+// If it would be safe that approach would likely bring an advantage in performance.
+//
+// Each call of the function looks for a 'layer'. A 'layer' is a list of processes with the same depth.
+// First it sorts a list. Then it runs the function recursively for each element of the sorted list.
+// After that it updates the settings of processes.
+//
+// It relies on `leftBound` and `rightBound` as an optimization to cut the list size at the time it builds a 'layer'.
+//
+// It uses a temporary Hashtable `draftingTreeSet` because it's not safe to traverse a tree
+// and at the same time make changes in it.
+//
+static void ProcessList_updateTreeSetLayer(ProcessList* this, unsigned int leftBound, unsigned int rightBound, unsigned int deep, unsigned int left, unsigned int right, unsigned int* index, unsigned int* treeIndex, int indent) {
+
+   // It's guaranteed that layer_size is enough space
+   // but most likely it needs less. Specifically on first iteration.
+   int layerSize = (right - left) / 2;
+
+   // check if we reach `children` of `leaves`
+   if (layerSize == 0)
+      return;
+
+   Vector* layer = Vector_new(this->processes->type, false, layerSize);
+
+   // Find all processes on the same layer (process with the same `deep` value
+   // and included in a range from `leftBound` to `rightBound`).
+   //
+   // This loop also keeps track of left_bound and right_bound of these processes
+   // in order not to lose this information once the list is sorted.
+   //
+   // The variables left_bound and right_bound are different from what the values lhs and rhs represent.
+   // While left_bound and right_bound define a range of processes to look at, the values given by lhs and rhs are indices into an array
+   //
+   // In the below example note how filtering a range of indices i is different from filtering for processes in the bounds left_bound < x < right_bound …
+   //
+   // The nested tree set is sorted by left value, which is guaranteed upon entry/exit of this function.
+   //
+   // i | l | r
+   // 1 | 1 | 9
+   // 2 | 2 | 8
+   // 3 | 4 | 5
+   // 4 | 6 | 7
+   for (unsigned int i = leftBound; i < rightBound; i++) {
+      Process* proc = (Process*)Hashtable_get(this->displayTreeSet, i);
+      assert(proc);
+      if (proc && proc->tree_depth == deep && proc->tree_left > left && proc->tree_right < right) {
+         if (Vector_size(layer) > 0) {
+            Process* previous_process = (Process*)Vector_get(layer, Vector_size(layer) - 1);
+
+            // Make a 'right_bound' of previous_process in a layer the current process's index.
+            //
+            // Use 'tree_depth' as a temporal variable.
+            // It's safe to do as later 'tree_depth' will be renovated.
+            previous_process->tree_depth = proc->tree_index;
+         }
+
+         Vector_add(layer, proc);
+      }
+   }
+
+   // The loop above changes just up to process-1.
+   // So the last process of the layer isn't updated by the above code.
+   //
+   // Thus, if present, set the `rightBound` to the last process on the layer
+   if (Vector_size(layer) > 0) {
+      Process* previous_process = (Process*)Vector_get(layer, Vector_size(layer) - 1);
+      previous_process->tree_depth = rightBound;
+   }
+
+   Vector_quickSort(layer);
+
+   int size = Vector_size(layer);
+   for (int i = 0; i < size; i++) {
+      Process* proc = (Process*)Vector_get(layer, i);
+
+      unsigned int idx = (*index)++;
+      int newLeft = (*treeIndex)++;
+
+      int level = deep == 0 ? 0 : (int)deep - 1;
+      int currentIndent = indent == -1 ? 0 : indent | (1 << level);
+      int nextIndent = indent == -1 ? 0 : ((i < size - 1) ? currentIndent : indent);
+
+      unsigned int newLeftBound = proc->tree_index;
+      unsigned int newRightBound = proc->tree_depth;
+      ProcessList_updateTreeSetLayer(this, newLeftBound, newRightBound, deep + 1, proc->tree_left, proc->tree_right, index, treeIndex, nextIndent);
+
+      int newRight = (*treeIndex)++;
+
+      proc->tree_left = newLeft;
+      proc->tree_right = newRight;
+      proc->tree_index = idx;
+      proc->tree_depth = deep;
+
+      if (indent == -1) {
+         proc->indent = 0;
+      } else if (i == size - 1) {
+         proc->indent = -currentIndent;
+      } else {
+         proc->indent = currentIndent;
+      }
+
+      Hashtable_put(this->draftingTreeSet, proc->tree_index, proc);
+
+      // It's not strictly necessary to do this, but doing so anyways
+      // allows for checking the correctness of the inner workings.
+      Hashtable_remove(this->displayTreeSet, newLeftBound);
+   }
+
+   Vector_delete(layer);
+}
+
+static void ProcessList_updateTreeSet(ProcessList* this) {
+   unsigned int index = 0;
+   unsigned int tree_index = 1;
+
+   const int vsize = Vector_size(this->processes);
+
+   assert(Hashtable_count(this->draftingTreeSet) == 0);
+   assert((int)Hashtable_count(this->displayTreeSet) == vsize);
+
+   ProcessList_updateTreeSetLayer(this, 0, vsize, 0, 0, vsize * 2 + 1, &index, &tree_index, -1);
+
+   Hashtable* tmp = this->draftingTreeSet;
+   this->draftingTreeSet = this->displayTreeSet;
+   this->displayTreeSet = tmp;
+
+   assert(Hashtable_count(this->draftingTreeSet) == 0);
+   assert((int)Hashtable_count(this->displayTreeSet) == vsize);
 }
 
-static void ProcessList_buildTree(ProcessList* this, pid_t pid, int level, int indent, int direction, bool show) {
+static void ProcessList_buildTreeBranch(ProcessList* this, pid_t pid, int level, int indent, int direction, bool show, int* node_counter, int* node_index) {
    Vector* children = Vector_new(Class(Process), false, DEFAULT_SIZE);
 
    for (int i = Vector_size(this->processes) - 1; i >= 0; i--) {
-      Process* process = (Process*) (Vector_get(this->processes, i));
+      Process* process = (Process*)Vector_get(this->processes, i);
       if (process->show && Process_isChildOf(process, pid)) {
-         process = (Process*) (Vector_take(this->processes, i));
+         process = (Process*)Vector_take(this->processes, i);
          Vector_add(children, process);
       }
    }
+
    int size = Vector_size(children);
    for (int i = 0; i < size; i++) {
-      Process* process = (Process*) (Vector_get(children, i));
-      if (!show)
+      int index = (*node_index)++;
+      Process* process = (Process*)Vector_get(children, i);
+
+      int lft = (*node_counter)++;
+
+      if (!show) {
          process->show = false;
-      int s = this->processes2->items;
-      if (direction == 1)
+      }
+
+      int s = Vector_size(this->processes2);
+      if (direction == 1) {
          Vector_add(this->processes2, process);
-      else
+      } else {
          Vector_insert(this->processes2, 0, process);
-      assert(this->processes2->items == s+1); (void)s;
+      }
+
+      assert(Vector_size(this->processes2) == s + 1); (void)s;
+
       int nextIndent = indent | (1 << level);
-      ProcessList_buildTree(this, process->pid, level+1, (i < size - 1) ? nextIndent : indent, direction, show ? process->showChildren : false);
-      if (i == size - 1)
+      ProcessList_buildTreeBranch(this, process->pid, level + 1, (i < size - 1) ? nextIndent : indent, direction, show ? process->showChildren : false, node_counter, node_index);
+      if (i == size - 1) {
          process->indent = -nextIndent;
-      else
+      } else {
          process->indent = nextIndent;
+      }
+
+      int rht = (*node_counter)++;
+
+      process->tree_left = lft;
+      process->tree_right = rht;
+      process->tree_depth = level + 1;
+      process->tree_index = index;
+      Hashtable_put(this->displayTreeSet, index, process);
    }
    Vector_delete(children);
 }
 
-void ProcessList_sort(ProcessList* this) {
-   if (!this->settings->treeView) {
-      Vector_insertionSort(this->processes);
-   } else {
-      // Save settings
-      int direction = this->settings->direction;
-      int sortKey = this->settings->sortKey;
-      // Sort by PID
-      this->settings->sortKey = PID;
-      this->settings->direction = 1;
-      Vector_quickSort(this->processes);
-      // Restore settings
-      this->settings->sortKey = sortKey;
-      this->settings->direction = direction;
-      int vsize = Vector_size(this->processes);
-      // Find all processes whose parent is not visible
-      int size;
-      while ((size = Vector_size(this->processes))) {
-         int i;
-         for (i = 0; i < size; i++) {
-            Process* process = (Process*)(Vector_get(this->processes, i));
-            // Immediately consume not shown processes
-            if (!process->show) {
-               process = (Process*)(Vector_take(this->processes, i));
-               process->indent = 0;
-               Vector_add(this->processes2, process);
-               ProcessList_buildTree(this, process->pid, 0, 0, direction, false);
-               break;
-            }
-            pid_t ppid = Process_getParentPid(process);
-            // Bisect the process vector to find parent
-            int l = 0, r = size;
-            // If PID corresponds with PPID (e.g. "kernel_task" (PID:0, PPID:0)
-            // on Mac OS X 10.11.6) cancel bisecting and regard this process as
-            // root.
-            if (process->pid == ppid)
-               r = 0;
-            while (l < r) {
-               int c = (l + r) / 2;
-               pid_t pid = ((Process*)(Vector_get(this->processes, c)))->pid;
-               if (ppid == pid) {
-                  break;
-               } else if (ppid < pid) {
-                  r = c;
-               } else {
-                  l = c + 1;
-               }
-            }
-            // If parent not found, then construct the tree with this root
-            if (l >= r) {
-               process = (Process*)(Vector_take(this->processes, i));
-               process->indent = 0;
-               Vector_add(this->processes2, process);
-               ProcessList_buildTree(this, process->pid, 0, 0, direction, process->showChildren);
+static long ProcessList_treeProcessCompare(const void* v1, const void* v2) {
+   const Process *p1 = (const Process*)v1;
+   const Process *p2 = (const Process*)v2;
+
+   return SPACESHIP_NUMBER(p1->tree_left, p2->tree_left);
+}
+
+static long ProcessList_treeProcessCompareByPID(const void* v1, const void* v2) {
+   const Process *p1 = (const Process*)v1;
+   const Process *p2 = (const Process*)v2;
+
+   return SPACESHIP_NUMBER(p1->pid, p2->pid);
+}
+
+// Builds a sorted tree from scratch, without relying on previously gathered information
+static void ProcessList_buildTree(ProcessList* this) {
+   int node_counter = 1;
+   int node_index = 0;
+   int direction = this->settings->direction;
+
+   // Sort by PID
+   Vector_quickSortCustomCompare(this->processes, ProcessList_treeProcessCompareByPID);
+   int vsize = Vector_size(this->processes);
+
+   // Find all processes whose parent is not visible
+   int size;
+   while ((size = Vector_size(this->processes))) {
+      int i;
+      for (i = 0; i < size; i++) {
+         Process* process = (Process*)Vector_get(this->processes, i);
+
+         // Immediately consume processes hidden from view
+         if (!process->show) {
+            process = (Process*)Vector_take(this->processes, i);
+            process->indent = 0;
+            process->tree_depth = 0;
+            process->tree_left = node_counter++;
+            process->tree_index = node_index++;
+            Vector_add(this->processes2, process);
+            ProcessList_buildTreeBranch(this, process->pid, 0, 0, direction, false, &node_counter, &node_index);
+            process->tree_right = node_counter++;
+            Hashtable_put(this->displayTreeSet, process->tree_index, process);
+            break;
+         }
+
+         pid_t ppid = Process_getParentPid(process);
+
+         // Bisect the process vector to find parent
+         int l = 0;
+         int r = size;
+
+         // If PID corresponds with PPID (e.g. "kernel_task" (PID:0, PPID:0)
+         // on Mac OS X 10.11.6) cancel bisecting and regard this process as
+         // root.
+         if (process->pid == ppid)
+            r = 0;
+
+         // On Linux both the init process (pid 1) and the root UMH kernel thread (pid 2)
+         // use a ppid of 0. As that PID can't exist, we can skip searching for it.
+         if (!ppid)
+            r = 0;
+
+         while (l < r) {
+            int c = (l + r) / 2;
+            pid_t pid = ((Process*)Vector_get(this->processes, c))->pid;
+            if (ppid == pid) {
                break;
+            } else if (ppid < pid) {
+               r = c;
+            } else {
+               l = c + 1;
             }
          }
-         // There should be no loop in the process tree
-         assert(i < size);
+
+         // If parent not found, then construct the tree with this node as root
+         if (l >= r) {
+            process = (Process*)Vector_take(this->processes, i);
+            process->indent = 0;
+            process->tree_depth = 0;
+            process->tree_left = node_counter++;
+            process->tree_index = node_index++;
+            Vector_add(this->processes2, process);
+            Hashtable_put(this->displayTreeSet, process->tree_index, process);
+            ProcessList_buildTreeBranch(this, process->pid, 0, 0, direction, process->showChildren, &node_counter, &node_index);
+            process->tree_right = node_counter++;
+            break;
+         }
       }
-      assert(Vector_size(this->processes2) == vsize); (void)vsize;
-      assert(Vector_size(this->processes) == 0);
-      // Swap listings around
-      Vector* t = this->processes;
-      this->processes = this->processes2;
-      this->processes2 = t;
+
+      // There should be no loop in the process tree
+      assert(i < size);
    }
+
+   // Swap listings around
+   Vector* t = this->processes;
+   this->processes = this->processes2;
+   this->processes2 = t;
+
+   // Check consistency of the built structures
+   assert(Vector_size(this->processes) == vsize); (void)vsize;
+   assert(Vector_size(this->processes2) == 0);
 }
 
+void ProcessList_sort(ProcessList* this) {
+   if (this->settings->treeView) {
+      ProcessList_updateTreeSet(this);
+      Vector_quickSortCustomCompare(this->processes, ProcessList_treeProcessCompare);
+   } else {
+      Vector_insertionSort(this->processes);
+   }
+}
 
-ProcessField ProcessList_keyAt(ProcessList* this, int at) {
+ProcessField ProcessList_keyAt(const ProcessList* this, int at) {
    int x = 0;
-   ProcessField* fields = this->settings->fields;
+   const ProcessField* fields = this->settings->fields;
    ProcessField field;
    for (int i = 0; (field = fields[i]); i++) {
       const char* title = Process_fields[field].title;
-      if (!title) title = "- ";
+      if (!title) {
+         title = "- ";
+      }
+
       int len = strlen(title);
       if (at >= x && at <= x + len) {
          return field;
@@ -253,7 +484,7 @@ void ProcessList_rebuildPanel(ProcessList* this) {
 
       if ( (!p->show)
          || (this->userId != (uid_t) -1 && (p->st_uid != this->userId))
-         || (incFilter && !(String_contains_i(p->comm, incFilter)))
+         || (incFilter && !(String_contains_i(Process_getCommand(p), incFilter)))
          || (this->pidMatchList && !Hashtable_get(this->pidMatchList, p->tgid)) )
          hidden = true;
 
@@ -282,12 +513,20 @@ Process* ProcessList_getProcess(ProcessList* this, pid_t pid, bool* preExisting,
    return proc;
 }
 
-void ProcessList_scan(ProcessList* this) {
+void ProcessList_scan(ProcessList* this, bool pauseProcessUpdate) {
+   struct timespec now;
+
+   // in pause mode only gather global data for meters (CPU/memory/...)
+   if (pauseProcessUpdate) {
+      ProcessList_goThroughEntries(this, true);
+      return;
+   }
 
    // mark all process as "dirty"
    for (int i = 0; i < Vector_size(this->processes); i++) {
       Process* p = (Process*) Vector_get(this->processes, i);
       p->updated = false;
+      p->wasShown = p->show;
       p->show = true;
    }
 
@@ -296,13 +535,46 @@ void ProcessList_scan(ProcessList* this) {
    this->kernelThreads = 0;
    this->runningTasks = 0;
 
-   ProcessList_goThroughEntries(this);
+
+   // set scanTs
+   static bool firstScanDone = false;
+   if (!firstScanDone) {
+      this->scanTs = 0;
+      firstScanDone = true;
+   } else if (clock_gettime(CLOCK_MONOTONIC, &now) == 0) {
+      this->scanTs = now.tv_sec;
+   }
+
+   ProcessList_goThroughEntries(this, false);
 
    for (int i = Vector_size(this->processes) - 1; i >= 0; i--) {
       Process* p = (Process*) Vector_get(this->processes, i);
-      if (p->updated == false)
-         ProcessList_remove(this, p);
-      else
+      if (p->tombTs > 0) {
+         // remove tombed process
+         if (this->scanTs >= p->tombTs) {
+            ProcessList_remove(this, p);
+         }
+      } else if (p->updated == false) {
+         // process no longer exists
+         if (this->settings->highlightChanges && p->wasShown) {
+            // mark tombed
+            p->tombTs = this->scanTs + this->settings->highlightDelaySecs;
+         } else {
+            // immediately remove
+            ProcessList_remove(this, p);
+         }
+      } else {
          p->updated = false;
+      }
+   }
+
+   if (this->settings->treeView) {
+      // Clear out the hashtable to avoid any left-over processes from previous build
+      //
+      // The sorting algorithm relies on the fact that
+      // len(this->displayTreeSet) == len(this->processes)
+      Hashtable_clear(this->displayTreeSet);
+
+      ProcessList_buildTree(this);
    }
 }