add experimental depanalysis module
authorPierre-Marc Fournier <pierre-marc.fournier@polymtl.ca>
Fri, 24 Jul 2009 19:45:28 +0000 (15:45 -0400)
committerPierre-Marc Fournier <pierre-marc.fournier@polymtl.ca>
Fri, 24 Jul 2009 19:45:28 +0000 (15:45 -0400)
lttv/lttv/state.c
lttv/lttv/state.h
lttv/modules/text/Makefile.am
lttv/modules/text/depanalysis.c [new file with mode: 0644]
lttv/modules/text/sstack.c [new file with mode: 0644]
lttv/modules/text/sstack.h [new file with mode: 0644]

index 70ca8cbe06286f447bd4f7193be8ccca48c51b9e..ef688770f0d41ee80ad697f0992549936c767d34 100644 (file)
@@ -83,6 +83,7 @@ GQuark
     LTT_EVENT_SOFT_IRQ_ENTRY,
     LTT_EVENT_SOFT_IRQ_EXIT,
     LTT_EVENT_SCHED_SCHEDULE,
+    LTT_EVENT_SCHED_TRY_WAKEUP,
     LTT_EVENT_PROCESS_FORK,
     LTT_EVENT_KTHREAD_CREATE,
     LTT_EVENT_PROCESS_EXIT,
@@ -99,7 +100,10 @@ GQuark
     LTT_EVENT_SYS_CALL_TABLE,
     LTT_EVENT_SOFTIRQ_VEC,
     LTT_EVENT_KPROBE_TABLE,
-    LTT_EVENT_KPROBE;
+    LTT_EVENT_KPROBE,
+    LTT_EVENT_OPEN,
+    LTT_EVENT_READ,
+    LTT_EVENT_POLL_EVENT;
 
 /* Fields Quarks */
 
@@ -131,7 +135,8 @@ GQuark
     LTT_FIELD_ID,
     LTT_FIELD_ADDRESS,
     LTT_FIELD_SYMBOL,
-    LTT_FIELD_IP;
+    LTT_FIELD_IP,
+    LTT_FIELD_FD;
 
 LttvExecutionMode
   LTTV_STATE_MODE_UNKNOWN,
@@ -1311,6 +1316,24 @@ static void copy_process_state(gpointer key, gpointer value,gpointer user_data)
         g_array_index(process->user_stack, guint64, i);
   }
   new_process->current_function = process->current_function;
+
+  /* fd hash table stuff */
+  {
+    GHashTableIter it;
+    int key;
+    GQuark value;
+
+    /* copy every item in the hash table */
+    new_process->fds = g_hash_table_new(g_direct_hash, g_direct_equal);
+
+    g_hash_table_iter_init(&it, process->fds);
+    while (g_hash_table_iter_next (&it, (void *)&key, (void *)&value)) {
+      g_hash_table_insert(new_process->fds, &key, &value);
+    }
+  }
+
+  /* When done creating the new process state, insert it in the
+   * hash table */
   g_hash_table_insert(new_processes, new_process, new_process);
 }
 
@@ -2327,6 +2350,7 @@ static LttvTracefileState *ltt_state_usertrace_find(LttvTraceState *tcs,
   return tfs;
 }
 
+/* Return a new and initialized LttvProcessState structure */
 
 LttvProcessState *
 lttv_state_create_process(LttvTraceState *tcs, LttvProcessState *parent, 
@@ -2400,6 +2424,8 @@ lttv_state_create_process(LttvTraceState *tcs, LttvProcessState *parent,
   /* Allocate an empty function call stack. If it's empty, use 0x0. */
   process->user_stack = g_array_sized_new(FALSE, FALSE,
       sizeof(guint64), 0);
+
+  process->fds = g_hash_table_new(g_direct_hash, g_direct_equal);
   
   return process;
 }
@@ -2441,7 +2467,7 @@ lttv_state_find_process_or_create(LttvTraceState *ts, guint cpu, guint pid,
 
 /* FIXME : this function should be called when we receive an event telling that
  * release_task has been called in the kernel. In happens generally when
- * the parent waits for its child terminaison, but may also happen in special
+ * the parent waits for its child termination, but may also happens in special
  * cases in the child's exit : when the parent ignores its children SIGCCHLD or
  * has the flag SA_NOCLDWAIT. It can also happen when the child is part
  * of a killed thread group, but isn't the leader.
@@ -2461,6 +2487,10 @@ static int exit_process(LttvTracefileState *tfs, LttvProcessState *process)
   g_hash_table_remove(ts->processes, &key);
   g_array_free(process->execution_stack, TRUE);
   g_array_free(process->user_stack, TRUE);
+
+  /* the following also clears the content */
+  g_hash_table_destroy(process->fds);
+
   g_free(process);
   return 1;
 }
@@ -2470,6 +2500,10 @@ static void free_process_state(gpointer key, gpointer value,gpointer user_data)
 {
   g_array_free(((LttvProcessState *)value)->execution_stack, TRUE);
   g_array_free(((LttvProcessState *)value)->user_stack, TRUE);
+
+  /* the following also clears the content */
+  g_hash_table_destroy(((LttvProcessState *)value)->fds);
+
   g_free(value);
 }
 
@@ -3224,6 +3258,29 @@ static gboolean thread_brand(void *hook_data, void *call_data)
   return FALSE;
 }
 
+static gboolean fs_open(void *hook_data, void *call_data)
+{
+  LttvTracefileState *s = (LttvTracefileState *)call_data;
+  LttvTraceState *ts = (LttvTraceState *)s->parent.t_context;
+  LttEvent *e = ltt_tracefile_get_event(s->parent.tf);
+  LttvTraceHook *th = (LttvTraceHook *)hook_data;
+  struct marker_field *f;
+  guint cpu = s->cpu;
+  int fd;
+  char *filename;
+  LttvProcessState *process = ts->running_process[cpu];
+
+  f = lttv_trace_get_hook_field(th, 0);
+  fd = ltt_event_get_int(e, f);
+
+  f = lttv_trace_get_hook_field(th, 1);
+  filename = ltt_event_get_string(e, f);
+
+  g_hash_table_insert(process->fds, fd, g_quark_from_string(filename));
+
+  return FALSE;
+}
+
 static void fix_process(gpointer key, gpointer value,
    gpointer user_data)
 {
@@ -3677,6 +3734,12 @@ void lttv_state_add_event_hooks(LttvTracesetState *self)
         FIELD_ARRAY(LTT_FIELD_ID, LTT_FIELD_ADDRESS, LTT_FIELD_SYMBOL),
         dump_softirq, NULL, &hooks);
 
+    lttv_trace_find_hook(ts->parent.t,
+        LTT_CHANNEL_FS,
+        LTT_EVENT_OPEN,
+        FIELD_ARRAY(LTT_FIELD_FD, LTT_FIELD_FILENAME),
+        fs_open, NULL, &hooks);
+
     /* Add these hooks to each event_by_id hooks list */
 
     nb_tracefile = ts->parent.tracefiles->len;
@@ -4366,6 +4429,7 @@ static void module_init()
   LTT_EVENT_SOFT_IRQ_ENTRY     = g_quark_from_string("softirq_entry");
   LTT_EVENT_SOFT_IRQ_EXIT      = g_quark_from_string("softirq_exit");
   LTT_EVENT_SCHED_SCHEDULE   = g_quark_from_string("sched_schedule");
+  LTT_EVENT_SCHED_TRY_WAKEUP = g_quark_from_string("sched_try_wakeup");
   LTT_EVENT_PROCESS_FORK          = g_quark_from_string("process_fork");
   LTT_EVENT_KTHREAD_CREATE = g_quark_from_string("kthread_create");
   LTT_EVENT_PROCESS_EXIT          = g_quark_from_string("process_exit");
@@ -4383,6 +4447,9 @@ static void module_init()
   LTT_EVENT_SOFTIRQ_VEC = g_quark_from_string("softirq_vec");
   LTT_EVENT_KPROBE_TABLE = g_quark_from_string("kprobe_table");
   LTT_EVENT_KPROBE = g_quark_from_string("kprobe");
+  LTT_EVENT_OPEN = g_quark_from_string("open");
+  LTT_EVENT_READ = g_quark_from_string("read");
+  LTT_EVENT_POLL_EVENT = g_quark_from_string("poll_event");
 
   LTT_FIELD_SYSCALL_ID    = g_quark_from_string("syscall_id");
   LTT_FIELD_TRAP_ID       = g_quark_from_string("trap_id");
@@ -4412,6 +4479,7 @@ static void module_init()
   LTT_FIELD_ADDRESS       = g_quark_from_string("address");
   LTT_FIELD_SYMBOL        = g_quark_from_string("symbol");
   LTT_FIELD_IP            = g_quark_from_string("ip");
+  LTT_FIELD_FD            = g_quark_from_string("fd");
   
   LTTV_CPU_UNKNOWN = g_quark_from_string("unknown");
   LTTV_CPU_IDLE = g_quark_from_string("idle");
index ad7f9e064693f59590e9629ff52261a2001dfad2..8ed648f289d1b89b34fa0ca4a7b185ffb993654d 100644 (file)
@@ -90,6 +90,7 @@ extern GQuark
     LTT_EVENT_SOFT_IRQ_ENTRY,
     LTT_EVENT_SOFT_IRQ_EXIT,
     LTT_EVENT_SCHED_SCHEDULE,
+    LTT_EVENT_SCHED_TRY_WAKEUP,
     LTT_EVENT_PROCESS_FORK,
     LTT_EVENT_KTHREAD_CREATE,
     LTT_EVENT_PROCESS_EXIT,
@@ -106,7 +107,10 @@ extern GQuark
     LTT_EVENT_SYS_CALL_TABLE,
     LTT_EVENT_SOFTIRQ_VEC,
     LTT_EVENT_KPROBE_TABLE,
-    LTT_EVENT_KPROBE;
+    LTT_EVENT_KPROBE,
+    LTT_EVENT_OPEN,
+    LTT_EVENT_READ,
+    LTT_EVENT_POLL_EVENT;
 
 /* Fields Quarks */
 
@@ -137,7 +141,8 @@ extern GQuark
     LTT_FIELD_ID,
     LTT_FIELD_ADDRESS,
     LTT_FIELD_SYMBOL,
-    LTT_FIELD_IP;
+    LTT_FIELD_IP,
+    LTT_FIELD_FD;
 
 typedef struct _LttvTracesetState LttvTracesetState;
 typedef struct _LttvTracesetStateClass LttvTracesetStateClass;
@@ -284,6 +289,7 @@ typedef struct _LttvProcessState {
   LttvProcessType type;        /* kernel thread or user space ? */
   guint target_pid; /* target PID of the current event. */
   guint free_events; /* 0 : none, 1 : free or exit dead, 2 : should delete */
+  GHashTable *fds; /* hash table of int (file descriptor) -> GQuark (file name) */
 } LttvProcessState;
 
 #define ANY_CPU 0 /* For clarity sake : a call to lttv_state_find_process for
index 03425fb395f5c9e42abe761db7c30a45f8a8006f..0e91ebef4c071e8b95f8f7787fc9613c9ca1432d 100644 (file)
@@ -4,7 +4,7 @@ LIBS += $(GLIB_LIBS) -lgobject-2.0 -L${top_builddir}/ltt -llttvtraceread
 
 libdir = ${lttvplugindir}
 
-lib_LTLIBRARIES = libtextDump.la libbatchAnalysis.la libtextFilter.la libprecomputeState.la
+lib_LTLIBRARIES = libtextDump.la libbatchAnalysis.la libtextFilter.la libprecomputeState.la libdepanalysis.la
 libtextDump_la_LDFLAGS = -module -avoid-version
 libtextDump_la_SOURCES = textDump.c
 libbatchAnalysis_la_LDFLAGS = -module -avoid-version
@@ -13,6 +13,8 @@ libtextFilter_la_LDFLAGS = -module -avoid-version
 libtextFilter_la_SOURCES = textFilter.c
 libprecomputeState_la_LDFLAGS = -module -avoid-version
 libprecomputeState_la_SOURCES = precomputeState.c
+libdepanalysis_la_LDFLAGS = -module -avoid-version
+libdepanalysis_la_SOURCES = depanalysis.c sstack.c
 
 noinst_HEADERS = \
        batchanalysis.h
diff --git a/lttv/modules/text/depanalysis.c b/lttv/modules/text/depanalysis.c
new file mode 100644 (file)
index 0000000..ca92617
--- /dev/null
@@ -0,0 +1,2048 @@
+/* This file is part of the Linux Trace Toolkit viewer
+ * Copyright (C) 2008 Pierre-Marc Fournier
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License Version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * MA 02111-1307, USA.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <lttv/lttv.h>
+#include <lttv/option.h>
+#include <lttv/module.h>
+#include <lttv/hook.h>
+#include <lttv/attribute.h>
+#include <lttv/iattribute.h>
+#include <lttv/stats.h>
+#include <lttv/filter.h>
+#include <lttv/print.h>
+#include <ltt/ltt.h>
+#include <ltt/event.h>
+#include <ltt/trace.h>
+#define _GNU_SOURCE
+#include <stdio.h>
+#include <glib.h>
+#include <stdlib.h>
+
+#include "sstack.h"
+
+static LttvHooks
+  *before_traceset,
+  *after_traceset,
+//  *before_trace,
+  *event_hook;
+
+static int depanalysis_range_pid = -1;
+static int depanalysis_range_pid_searching = -1;
+static int depanalysis_use_time=0;
+static int depanalysis_event_limit = -1;
+static LttTime depanalysis_time1, depanalysis_time2;
+static char *arg_t1_str,*arg_t2_str;
+static int statedump_finished = 0;
+
+
+struct llev_state_info_irq {
+       int irq;
+};
+
+struct llev_state_info_softirq {
+       int softirq;
+};
+
+struct llev_state_info_syscall {
+       int syscall_id;
+
+       int substate;
+
+       void *private;
+};
+
+struct llev_state_info_syscall__open {
+       GQuark filename;
+};
+
+struct llev_state_info_syscall__read {
+       GQuark filename;
+};
+
+struct llev_state_info_syscall__poll {
+       GQuark filename;
+};
+
+struct llev_state_info_preempted {
+       int prev_state;
+};
+
+struct hlev_state_info_blocked {
+       int syscall_id;
+       unsigned char trap; /* flag */
+       int substate;
+
+       /* Garray of pointers to struct process_state that reflect the
+         * low-level state stack when respectively entering and exiting the blocked
+         * state.
+         */
+       GArray *llev_state_entry;
+       GArray *llev_state_exit;
+
+       int pid_exit; /* FIXME: it's not pretty to have this here; find this info elsewhere */
+       LttTime time_woken;
+
+       void *private;
+};
+
+struct hlev_state_info_blocked__open {
+       GQuark filename;
+};
+
+struct hlev_state_info_blocked__read {
+       GQuark filename;
+};
+
+struct hlev_state_info_blocked__poll {
+       GQuark filename;
+};
+
+struct hlev_state_info_interrupted_irq {
+       int irq;
+};
+
+struct hlev_state_info_interrupted_softirq {
+       int softirq;
+};
+
+struct summary_tree_node {
+       char *name;
+       GHashTable *children;
+       LttTime duration;
+       GArray *episodes;
+       int id_for_episodes;
+};
+
+struct state_info {
+       char name[40];
+       int size_priv;
+       char *tree_path[6];
+};
+
+struct state_info llev_state_infos[] = {
+       { "UNKNOWN", 0, { NULL } },
+       { "RUNNING", 0, { NULL } },
+       { "SYSCALL", sizeof(struct llev_state_info_syscall), { NULL } },
+       { "IRQ", sizeof(struct llev_state_info_irq), { NULL } },
+       { "SOFTIRQ", sizeof(struct llev_state_info_softirq), { NULL } },
+       { "TRAP", 0, { NULL } },
+       { "PREEMPTED", sizeof(struct llev_state_info_preempted), { NULL } },
+};
+
+struct state_info hlev_state_infos[] = {
+       { "UNKNOWN", 0, { "Total", "Unknown", NULL } },
+       { "RUNNING", 0, { "Total", "Working", NULL } },
+       { "BLOCKED", sizeof(struct hlev_state_info_blocked), { "Total", "Blocked", NULL } },
+       { "INTERRUPTED_IRQ", sizeof(struct hlev_state_info_interrupted_irq), { "Total", "Interrupted", "IRQ", NULL } },
+       { "INTERRUPTED_SOFTIRQ", sizeof(struct hlev_state_info_interrupted_softirq), { "Total", "Interrupted", "SoftIRQ", NULL } },
+       { "INTERRUPTED_CPU", 0, { "Total", "Interrupted", "Preempted", NULL } },
+       { "INTERRUPTED_POST_BLOCK", 0, { "Total", "Interrupted", "Waiting schedule after blocking", NULL } },
+};
+
+enum llev_state {
+       LLEV_UNKNOWN=0,
+       LLEV_RUNNING,
+       LLEV_SYSCALL,
+       LLEV_IRQ,
+       LLEV_SOFTIRQ,
+       LLEV_TRAP,
+       LLEV_PREEMPTED,
+};
+
+enum llev_syscall_substate {
+       LLEV_SYSCALL__UNDEFINED,
+       LLEV_SYSCALL__OPEN,
+       LLEV_SYSCALL__READ,
+       LLEV_SYSCALL__POLL,
+};
+
+enum hlev_event {
+       HLEV_EVENT_TRY_WAKEUP=0,
+};
+
+enum hlev_state {
+       HLEV_UNKNOWN=0,
+       HLEV_RUNNING,
+       HLEV_BLOCKED,
+       HLEV_INTERRUPTED_IRQ,
+       HLEV_INTERRUPTED_SOFTIRQ,
+       HLEV_INTERRUPTED_CPU,
+       HLEV_INTERRUPTED_POST_BLOCK,
+};
+
+enum hlev_state_blocked {
+       HLEV_BLOCKED__UNDEFINED,
+       HLEV_BLOCKED__OPEN,
+       HLEV_BLOCKED__READ,
+       HLEV_BLOCKED__POLL,
+};
+
+struct sstack_event {
+       int event_type;
+       void *private;
+};
+
+struct try_wakeup_event {
+       int pid; /* this sould be more precise avec pid may be reused */
+       LttTime time;
+       struct process *waker;
+};
+
+struct process_state {
+       int bstate;
+       int cause_type;
+       void *private;
+
+       LttTime time_begin;
+       LttTime time_end;
+};
+
+struct process_with_state {
+       struct process *process;
+       struct process_state state;
+};
+
+#define PROCESS_STATE_STACK_SIZE 10
+struct process {
+       int pid;
+       GQuark name;
+       int parent;
+
+       struct sstack *stack;
+       struct process_state *llev_state_stack[PROCESS_STATE_STACK_SIZE];
+       int stack_current;
+       struct process_state *hlev_state;
+       GArray *hlev_history;
+};
+
+static inline void *old_process_state_private_data(struct process *p)
+{
+       return p->llev_state_stack[p->stack_current]->private;
+}
+
+static inline struct process_state *process_find_state(struct process *p, enum llev_state st)
+{
+       int i;
+
+       for(i=p->stack->array->len-1; i>=0; i--) {
+               struct sstack_item *item = g_array_index(p->stack->array, struct sstack_item *, i);
+
+               struct process_with_state *pwstate = item->data_val;
+               if(pwstate->state.bstate == st) {
+                       return &pwstate->state;
+               }
+       }
+
+       return NULL;
+}
+
+static int find_pos_in_stack(enum llev_state lls, struct process *p)
+{
+       int i;
+       for(i=p->stack_current; i>=0; i--) {
+               if(p->llev_state_stack[i]->bstate == lls)
+                       return i;
+       }
+
+       return -1;
+}
+
+static struct process_state *find_in_stack(enum llev_state lls, struct process *p)
+{
+       int result;
+
+       result = find_pos_in_stack(lls, p);
+
+       if(result >= 0)
+               return p->llev_state_stack[result];
+       else
+               return NULL;
+
+}
+
+/* called back from sstack on deletion of a data_val which is
+ * a struct process_with_state
+ */
+
+static void delete_data_val(struct process_with_state *pwstate)
+{
+       // FIXME: Free this also
+       //g_free(pwstate->state.private);
+
+       // FIXME: this is really ugly. Don't free the pwstate if the state is LLEV_RUNNING.
+       // LLEV_RUNNING is a special case that's being processed and deleted immediately after
+       // being inserted on the sstack, to prevent state begin accumulated because it couldn't
+       // be processed before the end of the trace. If we free the state, we get invalid memory
+       // reads when looking at it on the state_stack.
+       //if(pwstate->state.bstate != LLEV_RUNNING)
+       //      g_free(pwstate);
+}
+
+static struct sstack_item *prepare_push_item(struct process *p, enum llev_state st, LttTime t)
+{
+       struct process_with_state *pwstate = g_malloc(sizeof(struct process_with_state));
+       struct sstack_item *item;
+
+       int wait_for_pop = 0;
+
+       if(st == LLEV_SYSCALL) {
+               /* We need to push LLEV_SYSCALL as wait_for_pop because it depends on some of
+                * its children. If we don't do this, it's going to get processed immediately
+                * by the sstack and we might miss some details about it that will come later.
+                */
+               wait_for_pop = 1;
+       }
+
+       item = sstack_item_new_push(wait_for_pop);
+
+       //printf("pushing in context of %d\n", p->pid);
+
+       pwstate->process = p;
+       pwstate->state.bstate = st;
+       pwstate->state.time_begin = t;
+       pwstate->state.private = g_malloc(llev_state_infos[st].size_priv);
+
+       item->data_val = pwstate;
+       item->delete_data_val = delete_data_val;
+}
+
+static void *item_private(struct sstack_item *item)
+{
+       struct process_with_state *pwstate = item->data_val;
+       return pwstate->state.private;
+}
+
+static void commit_item(struct process *p, struct sstack_item *item)
+{
+       sstack_add_item(p->stack, item);
+}
+
+static void old_process_push_llev_state(struct process *p, struct process_state *pstate)
+{
+       if(++p->stack_current >= PROCESS_STATE_STACK_SIZE) {
+               fprintf(stderr, "depanalysis: internal process stack overflow\n");
+               abort();
+       }
+
+       p->llev_state_stack[p->stack_current] = pstate;
+}
+
+static void live_complete_process_push_llev_state(struct process *p, enum llev_state st, LttTime t)
+{
+       struct process_state *pstate = g_malloc(sizeof(struct process_state));
+
+       pstate->bstate = st;
+       pstate->time_begin = t;
+       pstate->private = g_malloc(llev_state_infos[st].size_priv);
+
+       old_process_push_llev_state(p, pstate);
+}
+
+static void prepare_pop_item_commit_nocheck(struct process *p, enum llev_state st, LttTime t)
+{
+       struct process_with_state *pwstate;
+       struct sstack_item *item = sstack_item_new_pop();
+
+       int push_idx;
+
+       if(p->stack->pushes->len > 0)
+               push_idx = g_array_index(p->stack->pushes, int, p->stack->pushes->len-1);
+       else
+               push_idx = -1;
+
+       if(push_idx >= 0) {
+               pwstate = g_array_index(p->stack->array, struct sstack_item *, push_idx)->data_val;
+               pwstate->process = p;
+               pwstate->state.time_end = t;
+               item->data_val = pwstate;
+               /* don't set delete_data_val because we use the same pwstate as push, and we don't want to free it twice */
+       }
+       else {
+
+               pwstate = g_malloc(sizeof(struct process_with_state));
+               pwstate->process = p;
+               item->data_val = pwstate;
+               pwstate->state.time_end = t;
+               pwstate->state.bstate = st;
+       }
+
+       sstack_add_item(p->stack, item);
+
+}
+
+static void prepare_pop_item_commit(struct process *p, enum llev_state st, LttTime t)
+{
+       struct process_with_state *pwstate;
+       struct sstack_item *item = sstack_item_new_pop();
+
+       int push_idx;
+              
+       if(p->stack->pushes->len > 0)
+               push_idx = g_array_index(p->stack->pushes, int, p->stack->pushes->len-1);
+       else
+               push_idx = -1;
+
+       if(push_idx >= 0) {
+               /* FIXME: ugly workaround for kernel bug that generates two kernel_arch_syscall_exit on fork.
+                * The bug only occurs upon creation of new processes. But these processes always have
+                * a LLEV_RUNNING at index 0. */
+               if(push_idx >= p->stack->array->len)
+                       return;
+
+               pwstate = g_array_index(p->stack->array, struct sstack_item *, push_idx)->data_val;
+
+               if(pwstate->state.bstate != st) {
+                       /* FIXME: ugly workaround for kernel bug that generates two kernel_arch_syscall_exit on fork */
+                       if(st != LLEV_SYSCALL) {
+                               printf("bad pop! at ");
+                               print_time(t);
+                               printf("\n");
+                               print_stack(p->stack);
+                               abort();
+                       }
+                       else {
+                               /* case where we have a double syscall_exit */
+                               return;
+                       }
+               }
+       }
+
+       prepare_pop_item_commit_nocheck(p, st, t);
+}
+
+
+static int try_pop_blocked_llev_preempted(struct process *p, LttTime t)
+{
+       int push_idx;
+       struct process_with_state *pwstate;
+
+       if(p->stack->pushes->len > 0)
+               push_idx = g_array_index(p->stack->pushes, int, p->stack->pushes->len-1);
+       else
+               push_idx = -1;
+
+       if(push_idx >= 0) {
+               pwstate = g_array_index(p->stack->array, struct sstack_item *, push_idx)->data_val;
+
+               if(!(pwstate->state.bstate == LLEV_PREEMPTED && ((struct llev_state_info_preempted *)pwstate->state.private)->prev_state > 0)) {
+                       printf("double try wake up\n");
+                       return 0;
+               }
+       }
+
+       prepare_pop_item_commit_nocheck(p, LLEV_PREEMPTED, t);
+       return 1;
+}
+
+static void old_process_pop_llev_state(struct process *p, struct process_state *pstate)
+{
+       /* Ensure we are really popping the current state */
+       /* FIXME: pstate->bstate is uninitialized? */
+       // Commenting because it does not work. The way things work now, this check cannot work.
+       //if(p->llev_state_stack[p->stack_current]->bstate != LLEV_UNKNOWN && p->llev_state_stack[p->stack_current]->bstate != pstate->bstate) {
+       //      printf("ERROR! bad pop!\n");
+       //      abort();
+       //}
+
+       /* Actually change the that position */
+       if(p->stack_current >= 0)
+               p->stack_current--;
+
+       /* If stack empty, we must put something in it */
+       if(p->stack_current == -1) {
+               if(pstate->bstate == LLEV_SYSCALL) {
+                       //process_push_llev_state(p, LLEV_RUNNING, pstate->time_end);
+                       live_complete_process_push_llev_state(p, LLEV_RUNNING, pstate->time_end);
+               }
+               else {
+                       live_complete_process_push_llev_state(p, LLEV_UNKNOWN, pstate->time_end);
+               }
+       }
+}
+
+static GHashTable *process_hash_table;
+static GHashTable *syscall_table;
+static GHashTable *irq_table;
+static GHashTable *softirq_table;
+
+/* Insert the hooks before and after each trace and tracefile, and for each
+   event. Print a global header. */
+
+static FILE *a_file;
+
+static GString *a_string;
+
+static gboolean write_traceset_header(void *hook_data, void *call_data)
+{
+  LttvTracesetContext *tc = (LttvTracesetContext *)call_data;
+
+  g_info("Traceset header");
+
+  /* Print the trace set header */
+  fprintf(a_file,"Trace set contains %d traces\n\n",
+      lttv_traceset_number(tc->ts));
+
+  return FALSE;
+}
+
+inline void print_time(LttTime t)
+{
+       //printf("%lu.%lu", t.tv_sec, t.tv_nsec);
+       double f;
+       f = (double)t.tv_sec + ((double)t.tv_nsec)/1000000000.0;
+       printf("%.9f", f);
+}
+
+GArray *oldstyle_stack_to_garray(struct process_state_stack **oldstyle_stack, int current)
+{
+       GArray *retval;
+       int i;
+
+       retval = g_array_new(FALSE, FALSE, sizeof(struct process_state_stack *));
+
+       for(i=0; i<current; i++) {
+               g_array_append_val(retval, oldstyle_stack[i]);
+       }
+
+       return retval;
+}
+
+static void update_hlev_state(struct process *p, LttTime t)
+{
+       int i;
+
+       enum hlev_state new_hlev;
+
+       for(i=p->stack_current; i>=0; i--) {
+               enum llev_state st;
+               st = p->llev_state_stack[i]->bstate;
+
+               if(st == LLEV_RUNNING || st == LLEV_TRAP || st == LLEV_SYSCALL) {
+                       new_hlev = HLEV_RUNNING;
+                       break;
+               }
+               else if(st == LLEV_IRQ) {
+                       new_hlev = HLEV_INTERRUPTED_IRQ;
+                       break;
+               }
+               else if(st == LLEV_SOFTIRQ) {
+                       new_hlev = HLEV_INTERRUPTED_SOFTIRQ;
+                       break;
+               }
+               else if(st == LLEV_PREEMPTED) {
+                       int prev_state = ((struct llev_state_info_preempted *) old_process_state_private_data(p))->prev_state;
+
+                       if(prev_state == 0) {
+                               new_hlev = HLEV_INTERRUPTED_CPU;
+                       }
+                       else if(prev_state == -1) {
+                               new_hlev = HLEV_INTERRUPTED_POST_BLOCK;
+                       }
+                       else {
+                               new_hlev = HLEV_BLOCKED;
+                       }
+                       break;
+               }
+               else if(st == LLEV_UNKNOWN) {
+                       new_hlev = HLEV_UNKNOWN;
+                       break;
+               }
+               else {
+                       abort();
+               }
+       }
+
+       /* If no state change, do nothing */
+       if(p->hlev_state != NULL && new_hlev == p->hlev_state->bstate) {
+               return;
+       }
+
+       p->hlev_state->time_end = t;
+       /* This check is here because we initially put HLEV_UNKNOWN as hlev state, but in the case
+        * of processes newly created, it is immediately replaced by HLEV_BLOCKED. In order to avoid
+        * having a UNKNOWN state of duration 0 in the summary, we don't add it. This isn't as elegant
+        * as it ought to be.
+        */
+       if(ltt_time_compare(p->hlev_state->time_begin, p->hlev_state->time_end) != 0)
+               g_array_append_val(p->hlev_history, p->hlev_state);
+       p->hlev_state = g_malloc(sizeof(struct process_state));
+       p->hlev_state->bstate = new_hlev;
+       p->hlev_state->time_begin = t;
+       p->hlev_state->private = g_malloc(hlev_state_infos[new_hlev].size_priv);
+
+       //printf("depanalysis: now at hlev state %s\n", hlev_state_infos[new_hlev].name);
+
+       /* Set private data */
+       switch(p->hlev_state->bstate) {
+               case HLEV_UNKNOWN:
+                       break;
+               case HLEV_RUNNING:
+                       break;
+               case HLEV_BLOCKED: {
+                       struct hlev_state_info_blocked *hlev_blocked_private = p->hlev_state->private;
+                       //struct process_state *ps = find_in_stack(LLEV_SYSCALL, p);
+                       int syscall_pos = find_pos_in_stack(LLEV_SYSCALL, p);
+                       int trap_pos = find_pos_in_stack(LLEV_TRAP, p);
+
+                       /* init vals */
+                       hlev_blocked_private->syscall_id = 1;
+                       hlev_blocked_private->trap = 0;
+                       hlev_blocked_private->substate = HLEV_BLOCKED__UNDEFINED;
+                       hlev_blocked_private->private = NULL;
+                       hlev_blocked_private->llev_state_entry = oldstyle_stack_to_garray(p->llev_state_stack, p->stack_current);
+                       hlev_blocked_private->llev_state_exit = NULL;
+
+                       //g_assert(syscall_pos >= 0 || trap_pos >= 0);
+
+                       if(trap_pos > syscall_pos) {
+                               hlev_blocked_private->trap = 1;
+                       }
+
+                       /* initial value, may be changed below */
+                       hlev_blocked_private->substate = HLEV_BLOCKED__UNDEFINED;
+
+                       if(syscall_pos >= 0) {
+                               struct process_state *ps = p->llev_state_stack[syscall_pos];
+                               struct llev_state_info_syscall *llev_syscall_private = (struct llev_state_info_syscall *) ps->private;
+                               hlev_blocked_private->syscall_id = llev_syscall_private->syscall_id;
+
+                               if(llev_syscall_private->substate == LLEV_SYSCALL__OPEN) {
+                                       struct llev_state_info_syscall__open *llev_syscall_open_private;
+                                       struct hlev_state_info_blocked__open *hlev_blocked_open_private;
+                                       llev_syscall_open_private = llev_syscall_private->private;
+                                       hlev_blocked_private->substate = HLEV_BLOCKED__OPEN;
+                                       hlev_blocked_open_private = g_malloc(sizeof(struct hlev_state_info_blocked__open));
+                                       hlev_blocked_private->private = hlev_blocked_open_private;
+                                       hlev_blocked_open_private->filename = llev_syscall_open_private->filename;
+
+                                       //printf("depanalysis: blocked in an open!\n");
+                               }
+                               else if(llev_syscall_private->substate == LLEV_SYSCALL__READ) {
+                                       struct llev_state_info_syscall__read *llev_syscall_read_private;
+                                       struct hlev_state_info_blocked__read *hlev_blocked_read_private;
+                                       llev_syscall_read_private = llev_syscall_private->private;
+                                       hlev_blocked_private->substate = HLEV_BLOCKED__READ;
+                                       hlev_blocked_read_private = g_malloc(sizeof(struct hlev_state_info_blocked__read));
+                                       hlev_blocked_private->private = hlev_blocked_read_private;
+                                       hlev_blocked_read_private->filename = llev_syscall_read_private->filename;
+
+                                       //printf("depanalysis: blocked in a read!\n");
+                               }
+                               else if(llev_syscall_private->substate == LLEV_SYSCALL__POLL) {
+                                       struct llev_state_info_syscall__poll *llev_syscall_poll_private;
+                                       struct hlev_state_info_blocked__poll *hlev_blocked_poll_private;
+                                       llev_syscall_poll_private = llev_syscall_private->private;
+                                       hlev_blocked_private->substate = HLEV_BLOCKED__POLL;
+                                       hlev_blocked_poll_private = g_malloc(sizeof(struct hlev_state_info_blocked__poll));
+                                       hlev_blocked_private->private = hlev_blocked_poll_private;
+                                       hlev_blocked_poll_private->filename = llev_syscall_poll_private->filename;
+
+                                       //printf("depanalysis: blocked in a read!\n");
+                               }
+                       }
+                       else {
+                               hlev_blocked_private->syscall_id = -1;
+                       }
+
+                       break;
+               }
+               case HLEV_INTERRUPTED_IRQ: {
+                       struct hlev_state_info_interrupted_irq *sinfo = p->hlev_state->private;
+                       struct process_state *ps = find_in_stack(LLEV_IRQ, p);
+                       if(ps == NULL)
+                               abort();
+                       else
+                               sinfo->irq = ((struct llev_state_info_irq *) ps->private)->irq;
+                       break;
+               }
+               case HLEV_INTERRUPTED_SOFTIRQ: {
+                       struct hlev_state_info_interrupted_softirq *sinfo = p->hlev_state->private;
+                       struct process_state *ps = find_in_stack(LLEV_SOFTIRQ, p);
+                       if(ps == NULL)
+                               abort();
+                       else
+                               sinfo->softirq = ((struct llev_state_info_softirq *) ps->private)->softirq;
+                       break;
+               }
+               default:
+                       break;
+       };
+}
+
+static gint compare_summary_tree_node_times(gconstpointer a, gconstpointer b)
+{
+       struct summary_tree_node *n1 = (struct summary_tree_node *) a;
+       struct summary_tree_node *n2 = (struct summary_tree_node *) b;
+
+       return ltt_time_compare(n2->duration, n1->duration);
+}
+
+/* Print an item of the simple summary tree, and recurse, printing its children.
+ *
+ * If depth == -1, this is the root: we don't print a label, we only recurse into
+ * the children.
+ */
+
+static void print_summary_item(struct summary_tree_node *node, int depth)
+{
+       GList *vals;
+
+       if(depth >= 0) {
+               printf("\t%*s (", strlen(node->name)+2*depth, node->name);
+               print_time(node->duration);
+               printf(") <%d>\n", node->id_for_episodes);
+       }
+
+       if(!node->children)
+               return;
+
+       vals = g_hash_table_get_values(node->children);
+
+       /* sort the values */
+       vals = g_list_sort(vals, compare_summary_tree_node_times);
+
+       while(vals) {
+               print_summary_item((struct summary_tree_node *)vals->data, depth+1);
+               vals = vals->next;
+       }
+
+       /* we must free the list returned by g_hash_table_get_values() */
+       g_list_free(vals);
+}
+
+static inline void print_irq(int irq)
+{
+       printf("IRQ %d [%s]", irq, g_quark_to_string(g_hash_table_lookup(irq_table, &irq)));
+}
+
+static inline void print_softirq(int softirq)
+{
+       printf("SoftIRQ %d [%s]", softirq, g_quark_to_string(g_hash_table_lookup(softirq_table, &softirq)));
+}
+
+static inline void print_pid(int pid)
+{
+       struct process *event_process_info = g_hash_table_lookup(process_hash_table, &pid);
+
+       char *pname;
+
+       if(event_process_info == NULL)
+               pname = "?";
+       else
+               pname = g_quark_to_string(event_process_info->name);
+       printf("%d [%s]", pid, pname);
+}
+
+static void modify_path_with_private(GArray *path, struct process_state *pstate)
+{
+       //GString tmps = g_string_new("");
+       char *tmps;
+
+       // FIXME: fix this leak
+       switch(pstate->bstate) {
+               case HLEV_INTERRUPTED_IRQ:
+                       asprintf(&tmps, "IRQ %d [%s]", ((struct hlev_state_info_interrupted_irq *)pstate->private)->irq, g_quark_to_string(g_hash_table_lookup(irq_table, &((struct hlev_state_info_interrupted_irq *)pstate->private)->irq)));
+                       g_array_append_val(path, tmps);
+                       break;
+               case HLEV_INTERRUPTED_SOFTIRQ:
+                       asprintf(&tmps, "SoftIRQ %d [%s]", ((struct hlev_state_info_interrupted_softirq *)pstate->private)->softirq, g_quark_to_string(g_hash_table_lookup(softirq_table, &((struct hlev_state_info_interrupted_softirq *)pstate->private)->softirq)));
+                       g_array_append_val(path, tmps);
+                       break;
+               case HLEV_BLOCKED: {
+                       struct hlev_state_info_blocked *hlev_blocked_private = (struct hlev_state_info_blocked *)pstate->private;
+
+                       if(hlev_blocked_private->trap) {
+                               char *ptr = "Trap";
+                               g_array_append_val(path, ptr);
+                       }
+                       
+                       if(hlev_blocked_private->syscall_id == -1) {
+                               char *ptr = "Userspace";
+                               g_array_append_val(path, ptr);
+                       }
+                       else {
+                               asprintf(&tmps, "Syscall %d [%s]", hlev_blocked_private->syscall_id, g_quark_to_string(g_hash_table_lookup(syscall_table, &hlev_blocked_private->syscall_id)));
+                               g_array_append_val(path, tmps);
+                       }
+
+                       if(((struct hlev_state_info_blocked *)pstate->private)->substate == HLEV_BLOCKED__OPEN) {
+                               char *str = g_quark_to_string(((struct hlev_state_info_blocked__open *)((struct hlev_state_info_blocked *)pstate->private)->private)->filename);
+                               g_array_append_val(path, str);
+                       }
+                       else if(((struct hlev_state_info_blocked *)pstate->private)->substate == HLEV_BLOCKED__READ) {
+                               char *str;
+                               asprintf(&str, "%s", g_quark_to_string(((struct hlev_state_info_blocked__read *)((struct hlev_state_info_blocked *)pstate->private)->private)->filename));
+                               g_array_append_val(path, str);
+                               /* FIXME: this must be freed at some point */
+                               //free(str);
+                       }
+                       else if(((struct hlev_state_info_blocked *)pstate->private)->substate == HLEV_BLOCKED__POLL) {
+                               char *str;
+                               asprintf(&str, "%s", g_quark_to_string(((struct hlev_state_info_blocked__poll *)((struct hlev_state_info_blocked *)pstate->private)->private)->filename));
+                               g_array_append_val(path, str);
+                               /* FIXME: this must be freed at some point */
+                               //free(str);
+                       }
+                       break;
+               }
+       };
+}
+
+void print_stack_garray_horizontal(GArray *stack)
+{
+       /* FIXME: this function doesn't work if we delete the states as we process them because we
+        * try to read those states here to print the low level stack.
+        */
+       int i;
+
+       for(i=0; i<stack->len; i++) {
+               struct process_state *pstate = g_array_index(stack, struct process_state *, i);
+               printf("%s", llev_state_infos[pstate->bstate].name);
+
+               if(pstate->bstate == LLEV_SYSCALL) {
+                       struct llev_state_info_syscall *llev_syscall_private = pstate->private;
+                       printf(" %d [%s]", llev_syscall_private->syscall_id, g_quark_to_string(g_hash_table_lookup(syscall_table, &llev_syscall_private->syscall_id)));
+               }
+
+               printf(", ");
+               
+       }
+}
+
+static int dicho_search_state_ending_after(struct process *p, LttTime t)
+{
+       int under = 0;
+       int over = p->hlev_history->len-1;
+       struct process_state *pstate;
+       int result;
+
+       if(over < 1)
+               return -1;
+
+       /* If the last element is smaller or equal than the time we are searching for,
+        * no match
+        */
+       pstate = g_array_index(p->hlev_history, struct process_state *, over);
+       if(ltt_time_compare(pstate->time_end, t) <= 0) {
+               return -1;
+       }
+       /* no need to check for the equal case */
+
+       pstate = g_array_index(p->hlev_history, struct process_state *, under);
+       result = ltt_time_compare(pstate->time_end, t);
+       if(result >= 1) {
+               /* trivial match at the first element if it is greater or equal
+                * than the time we want
+                */
+               return under;
+       }
+
+       while(1) {
+               int dicho;
+
+               dicho = (under+over)/2;
+               pstate = g_array_index(p->hlev_history, struct process_state *, dicho);
+               result = ltt_time_compare(pstate->time_end, t);
+
+               if(result == -1) {
+                       under = dicho;
+               }
+               else if(result == 1) {
+                       over = dicho;
+               }
+               else {
+                       /* exact match */
+                       return dicho+1;
+               }
+
+               if(over-under == 1) {
+                       /* we have converged */
+                       return over;
+               }
+       }
+
+}
+
+/* FIXME: this shouldn't be based on pids in case of reuse
+ * FIXME: should add a list of processes used to avoid loops
+ */
+
+static struct process_state *find_state_ending_after(int pid, LttTime t)
+{
+       struct process *p;
+       int result;
+
+
+       p = g_hash_table_lookup(process_hash_table, &pid);
+       if(!p)
+               return NULL;
+
+       result = dicho_search_state_ending_after(p, t);
+
+       if(result == -1)
+               return NULL;
+       else
+               return g_array_index(p->hlev_history, struct process_state *, result);
+}
+
+static void print_delay_pid(int pid, LttTime t1, LttTime t2, int offset)
+{
+       struct process *p;
+       int i;
+
+       p = g_hash_table_lookup(process_hash_table, &pid);
+       if(!p)
+               return;
+
+       i = dicho_search_state_ending_after(p, t1);
+       for(; i<p->hlev_history->len; i++) {
+               struct process_state *pstate = g_array_index(p->hlev_history, struct process_state *, i);
+               if(ltt_time_compare(pstate->time_end, t2) > 0)
+                       break;
+                       
+               if(pstate->bstate == HLEV_BLOCKED) {
+                       struct hlev_state_info_blocked *state_private_blocked;
+                       state_private_blocked = pstate->private;
+                       struct process_state *state_unblocked;
+
+                       printf("%*s", 8*offset, "");
+                       printf("Blocked in ");
+                       print_stack_garray_horizontal(state_private_blocked->llev_state_entry);
+
+                       printf("(times: ");
+                       print_time(pstate->time_begin);
+                       printf("-");
+                       print_time(pstate->time_end);
+
+                       printf(", dur: %f)\n", 1e-9*ltt_time_to_double(ltt_time_sub(pstate->time_end, pstate->time_begin)));
+
+                       state_unblocked = find_state_ending_after(state_private_blocked->pid_exit, state_private_blocked->time_woken);
+                       if(state_unblocked) {
+                               if(state_unblocked->bstate == HLEV_INTERRUPTED_IRQ) {
+                                       struct hlev_state_info_interrupted_irq *priv = state_unblocked->private;
+                                       /* if in irq or softirq, we don't care what the waking process was doing because they are asynchroneous events */
+                                       printf("%*s", 8*offset, "");
+                                       printf("Woken up by an IRQ: ");
+                                       print_irq(priv->irq);
+                                       printf("\n");
+                               }
+                               else if(state_unblocked->bstate == HLEV_INTERRUPTED_SOFTIRQ) {
+                                       struct hlev_state_info_interrupted_softirq *priv = state_unblocked->private;
+                                       printf("%*s", 8*offset, "");
+                                       printf("Woken up by a SoftIRQ: ");
+                                       print_softirq(priv->softirq);
+                                       printf("\n");
+                               }
+                               else {
+                                       LttTime t1prime=t1;
+                                       LttTime t2prime=t2;
+
+                                       if(ltt_time_compare(t1prime, pstate->time_begin) < 0)
+                                               t1prime = pstate->time_begin;
+                                       if(ltt_time_compare(t2prime, pstate->time_end) > 0)
+                                               t2prime = pstate->time_end;
+
+                                       print_delay_pid(state_private_blocked->pid_exit, t1prime, t2prime, offset+1);
+                                       printf("%*s", 8*offset, "");
+                                       printf("Woken up in context of ");
+                                       print_pid(state_private_blocked->pid_exit);
+                                       if(state_private_blocked->llev_state_exit) {
+                                               print_stack_garray_horizontal(state_private_blocked->llev_state_exit);
+                                       }
+                                       else {
+                                       }
+                                       printf(" in high-level state %s", hlev_state_infos[state_unblocked->bstate].name);
+                                       printf("\n");
+                               }
+                       }
+                       else {
+                               printf("%*s", 8*offset, "");
+                               printf("Weird... cannot find in what state the waker (%d) was\n", state_private_blocked->pid_exit);
+                       }
+
+
+                       //print_delay_pid(state_private_blocked->pid_exit, pstate->time_start, pstate->time_end);
+                       //printf("\t\t Woken up in context of %d: ", state_private_blocked->pid_exit);
+                       //if(state_private_blocked->llev_state_exit) {
+                       //      print_stack_garray_horizontal(state_private_blocked->llev_state_exit);
+                       //      printf("here3 (%d)\n", state_private_blocked->llev_state_exit->len);
+                       //}
+                       //else
+                       //      printf("the private_blocked %p had a null exit stack\n", state_private_blocked);
+                       //printf("\n");
+               }
+       }
+}
+
+static void print_range_critical_path(int process, LttTime t1, LttTime t2)
+{
+       printf("Critical path for requested range:\n");
+       printf("Final process is %d\n", process);
+       print_delay_pid(process, t1, t2, 2);
+}
+
+static void print_process_critical_path_summary()
+{
+       struct process *pinfo;
+       GList *pinfos;
+       int i,j;
+
+       pinfos = g_hash_table_get_values(process_hash_table);
+       if(pinfos == NULL) {
+               fprintf(stderr, "error: no process found\n");
+               return;
+       }
+
+       printf("Process Critical Path Summary:\n");
+
+       for(;;) {
+               struct summary_tree_node base_node = { children: NULL };
+
+               struct process_state *hlev_state_cur;
+
+               pinfo = (struct process *)pinfos->data;
+               printf("\tProcess %d [%s]\n", pinfo->pid, g_quark_to_string(pinfo->name));
+
+               if(pinfo->hlev_history->len < 1)
+                       goto next_iter;
+
+               print_delay_pid(pinfo->pid, g_array_index(pinfo->hlev_history, struct process_state *, 0)->time_begin, g_array_index(pinfo->hlev_history, struct process_state *, pinfo->hlev_history->len - 1)->time_end, 2);
+
+               next_iter:
+
+               if(pinfos->next)
+                       pinfos = pinfos->next;
+               else
+                       break;
+       }
+}
+
+gint compare_states_length(gconstpointer a, gconstpointer b)
+{
+       struct process_state **s1 = (struct process_state **)a;
+       struct process_state **s2 = (struct process_state **)b;
+       gint val;
+
+       val = ltt_time_compare(ltt_time_sub((*s2)->time_end, (*s2)->time_begin), ltt_time_sub((*s1)->time_end, (*s1)->time_begin));
+       return val;
+}
+
+static void print_simple_summary()
+{
+       struct process *pinfo;
+       GList *pinfos;
+       GList *pinfos_first;
+       int i,j;
+       int id_for_episodes = 0;
+
+       /* we save all the nodes here to print the episodes table quickly */
+       GArray *all_nodes = g_array_new(FALSE, FALSE, sizeof(struct summary_tree_node *));
+
+       pinfos_first = g_hash_table_get_values(process_hash_table);
+       if(pinfos_first == NULL) {
+               fprintf(stderr, "error: no processes found\n");
+               return;
+       }
+       pinfos = pinfos_first;
+
+       printf("Simple summary:\n");
+
+       /* For each process */
+       for(;;) {
+               struct summary_tree_node base_node = { children: NULL, name: "Root" };
+
+               struct process_state *hlev_state_cur;
+
+               pinfo = (struct process *)pinfos->data;
+               printf("\tProcess %d [%s]\n", pinfo->pid, g_quark_to_string(pinfo->name));
+
+               /* For each state in the process history */
+               for(i=0; i<pinfo->hlev_history->len; i++) {
+                       struct process_state *pstate = g_array_index(pinfo->hlev_history, struct process_state *, i);
+                       struct summary_tree_node *node_cur = &base_node;
+                       GArray *tree_path_garray;
+
+                       /* Modify the path based on private data */
+                       tree_path_garray = g_array_new(FALSE, FALSE, sizeof(char *));
+                       {
+                               int count=0;
+                               char **tree_path_cur2 = hlev_state_infos[pstate->bstate].tree_path;
+                               while(*tree_path_cur2) {
+                                       count++;
+                                       tree_path_cur2++;
+                               }
+                               g_array_append_vals(tree_path_garray, hlev_state_infos[pstate->bstate].tree_path, count);
+                       }
+                       modify_path_with_private(tree_path_garray, pstate);
+                       
+                       /* Walk the path, adding the nodes to the summary */
+                       for(j=0; j<tree_path_garray->len; j++) {
+                               struct summary_tree_node *newnode;
+                               GQuark componentquark;
+
+                               /* Have a path component we must follow */
+                               if(!node_cur->children) {
+                                       /* must create the hash table for the children */
+                                       node_cur->children = g_hash_table_new(g_int_hash, g_int_equal);
+                               }
+                               
+                               /* try to get the node for the next component */
+                               componentquark = g_quark_from_string(g_array_index(tree_path_garray, char *, j));
+                               newnode = g_hash_table_lookup(node_cur->children, &componentquark);
+                               if(newnode == NULL) {
+                                       newnode = g_malloc(sizeof(struct summary_tree_node));
+                                       newnode->children = NULL;
+                                       newnode->name = g_array_index(tree_path_garray, char *, j);
+                                       newnode->duration = ltt_time_zero;
+                                       newnode->id_for_episodes = id_for_episodes++;
+                                       newnode->episodes = g_array_new(FALSE, FALSE, sizeof(struct process_state *));
+                                       g_hash_table_insert(node_cur->children, &componentquark, newnode);
+
+                                       g_array_append_val(all_nodes, newnode);
+                               }
+                               node_cur = newnode;
+
+                               node_cur->duration = ltt_time_add(node_cur->duration, ltt_time_sub(pstate->time_end, pstate->time_begin));
+                               g_array_append_val(node_cur->episodes, pstate);
+                       }
+               }
+
+               /* print the summary */
+               print_summary_item(&base_node, -1);
+
+               printf("\n");
+
+               if(pinfos->next)
+                       pinfos = pinfos->next;
+               else
+                       break;
+       }
+
+       printf("\n");
+
+       printf("Episode list\n");
+       pinfos = pinfos_first;
+
+       /* For all the nodes of the Simple summary tree */
+       for(i=0; i<all_nodes->len; i++) {
+               struct summary_tree_node *node = (struct summary_tree_node *)g_array_index(all_nodes, struct summary_tree_node *, i);
+
+               /* Sort the episodes from longest to shortest */
+               g_array_sort(node->episodes, compare_states_length);
+
+               printf("\tNode id: <%d>\n", node->id_for_episodes);
+               /* For each episode of the node */
+               for(j=0; j<node->episodes->len; j++) {
+                       struct process_state *st = g_array_index(node->episodes, struct process_state *, j);
+
+                       printf("\t\t");
+                       print_time(st->time_begin);
+                       printf("-");
+                       print_time(st->time_end);
+                       printf(" (%f)\n", 1e-9*ltt_time_to_double(ltt_time_sub(st->time_end,st->time_begin)));
+               }
+       }
+}
+
+static void print_simple_summary_pid_range(int pid, LttTime t1, LttTime t2)
+{
+       struct process *pinfo;
+       int i,j;
+       int id_for_episodes = 0;
+
+       /* we save all the nodes here to print the episodes table quickly */
+       GArray *all_nodes = g_array_new(FALSE, FALSE, sizeof(struct summary_tree_node *));
+
+       pinfo = g_hash_table_lookup(process_hash_table, &pid);
+
+       {
+               struct summary_tree_node base_node = { children: NULL, name: "Root" };
+
+               struct process_state *hlev_state_cur;
+
+               printf("\tProcess %d [%s]\n", pinfo->pid, g_quark_to_string(pinfo->name));
+
+               /* For each state in the process history */
+               for(i=0; i<pinfo->hlev_history->len; i++) {
+                       struct process_state *pstate = g_array_index(pinfo->hlev_history, struct process_state *, i);
+                       struct summary_tree_node *node_cur = &base_node;
+                       GArray *tree_path_garray;
+
+                       if(ltt_time_compare(pstate->time_end, t1) < 0)
+                               continue;
+
+                       if(ltt_time_compare(pstate->time_end, t2) > 0)
+                               break;
+
+                       /* Modify the path based on private data */
+                       tree_path_garray = g_array_new(FALSE, FALSE, sizeof(char *));
+                       {
+                               int count=0;
+                               char **tree_path_cur2 = hlev_state_infos[pstate->bstate].tree_path;
+                               while(*tree_path_cur2) {
+                                       count++;
+                                       tree_path_cur2++;
+                               }
+                               g_array_append_vals(tree_path_garray, hlev_state_infos[pstate->bstate].tree_path, count);
+                       }
+                       modify_path_with_private(tree_path_garray, pstate);
+                       
+                       /* Walk the path, adding the nodes to the summary */
+                       for(j=0; j<tree_path_garray->len; j++) {
+                               struct summary_tree_node *newnode;
+                               GQuark componentquark;
+
+                               /* Have a path component we must follow */
+                               if(!node_cur->children) {
+                                       /* must create the hash table for the children */
+                                       node_cur->children = g_hash_table_new(g_int_hash, g_int_equal);
+                               }
+                               
+                               /* try to get the node for the next component */
+                               componentquark = g_quark_from_string(g_array_index(tree_path_garray, char *, j));
+                               newnode = g_hash_table_lookup(node_cur->children, &componentquark);
+                               if(newnode == NULL) {
+                                       newnode = g_malloc(sizeof(struct summary_tree_node));
+                                       newnode->children = NULL;
+                                       newnode->name = g_array_index(tree_path_garray, char *, j);
+                                       newnode->duration = ltt_time_zero;
+                                       newnode->id_for_episodes = id_for_episodes++;
+                                       newnode->episodes = g_array_new(FALSE, FALSE, sizeof(struct process_state *));
+                                       g_hash_table_insert(node_cur->children, &componentquark, newnode);
+
+                                       g_array_append_val(all_nodes, newnode);
+                               }
+                               node_cur = newnode;
+
+                               node_cur->duration = ltt_time_add(node_cur->duration, ltt_time_sub(pstate->time_end, pstate->time_begin));
+                               g_array_append_val(node_cur->episodes, pstate);
+                       }
+               }
+
+               /* print the summary */
+               print_summary_item(&base_node, -1);
+
+               printf("\n");
+       }
+
+       printf("\n");
+
+       printf("Episode list\n");
+
+       /* For all the nodes of the Simple summary tree */
+       for(i=0; i<all_nodes->len; i++) {
+               struct summary_tree_node *node = (struct summary_tree_node *)g_array_index(all_nodes, struct summary_tree_node *, i);
+
+               /* Sort the episodes from longest to shortest */
+               g_array_sort(node->episodes, compare_states_length);
+
+               printf("\tNode id: <%d>\n", node->id_for_episodes);
+               /* For each episode of the node */
+               for(j=0; j<node->episodes->len; j++) {
+                       struct process_state *st = g_array_index(node->episodes, struct process_state *, j);
+
+                       printf("\t\t");
+                       print_time(st->time_begin);
+                       printf("-");
+                       print_time(st->time_end);
+                       printf(" (%f)\n", 1e-9*ltt_time_to_double(ltt_time_sub(st->time_end,st->time_begin)));
+               }
+       }
+}
+
+static void flush_process_sstacks(void)
+{
+       GList *pinfos;
+       
+       pinfos = g_hash_table_get_values(process_hash_table);
+       while(pinfos) {
+               struct process *pinfo = (struct process *)pinfos->data;
+
+               sstack_force_flush(pinfo->stack);
+
+               pinfos = pinfos->next;
+       }
+
+       g_list_free(pinfos);
+}
+
+struct family_item {
+       int pid;
+       LttTime creation;
+};
+
+void print_range_reports(int pid, LttTime t1, LttTime t2)
+{
+       GArray *family = g_array_new(FALSE, FALSE, sizeof(struct family_item));
+       int i;
+
+       /* reconstruct the parental sequence */
+       for(;;) {
+               struct process *pinfo;
+               struct family_item fi;
+               LttTime cur_beg;
+
+               pinfo = g_hash_table_lookup(process_hash_table, &pid);
+               if(pinfo == NULL)
+                       abort();
+
+               fi.pid = pid;
+               cur_beg = g_array_index(pinfo->hlev_history, struct process_state *, 0)->time_begin;
+               fi.creation = cur_beg;
+               g_array_append_val(family, fi);
+
+               if(ltt_time_compare(cur_beg, t1) == -1) {
+                       /* current pid starts before the interesting time */
+                       break;
+               }
+               if(pinfo->parent == -1) {
+                       printf("unable to go back, we don't know the parent of %d\n", fi.pid);
+                       abort();
+               }
+               /* else, we go on */
+               pid = pinfo->parent;
+
+       }
+
+       printf("Simple summary for range:\n");
+       for(i=family->len-1; i>=0; i--) {
+               LttTime iter_t1, iter_t2;
+               int iter_pid = g_array_index(family, struct family_item, i).pid;
+
+               if(i == family->len-1)
+                       iter_t1 = t1;
+               else
+                       iter_t1 = g_array_index(family, struct family_item, i).creation;
+
+               if(i == 0)
+                       iter_t2 = t2;
+               else
+                       iter_t2 = g_array_index(family, struct family_item, i-1).creation;
+
+               printf("This section of summary concerns pid %d between ");
+               print_time(iter_t1);
+               printf(" and ");
+               print_time(iter_t2);
+               printf(".\n");
+               print_simple_summary_pid_range(iter_pid, iter_t1, iter_t2);
+       }
+       print_range_critical_path(depanalysis_range_pid, t1, t2);
+}
+
+static gboolean write_traceset_footer(void *hook_data, void *call_data)
+{
+       LttvTracesetContext *tc = (LttvTracesetContext *)call_data;
+
+       g_info("TextDump traceset footer");
+
+       fprintf(a_file,"End trace set\n\n");
+
+//     if(LTTV_IS_TRACESET_STATS(tc)) {
+//             lttv_stats_sum_traceset((LttvTracesetStats *)tc, ltt_time_infinite);
+//             print_stats(a_file, (LttvTracesetStats *)tc);
+//     }
+
+       /* After processing all the events, we need to flush the sstacks
+         * because some unfinished states may remain in them. We want them
+         * event though there are incomplete.
+         */
+       flush_process_sstacks();
+
+       /* print the reports */
+       print_simple_summary();
+       print_process_critical_path_summary();
+       printf("depanalysis_use_time = %d\n", depanalysis_use_time);
+       if(depanalysis_use_time == 3) {
+               if(depanalysis_range_pid == -1 && depanalysis_range_pid_searching >= 0)
+                       depanalysis_range_pid = depanalysis_range_pid_searching;
+
+               if(depanalysis_range_pid >= 0) {
+                       print_range_reports(depanalysis_range_pid, depanalysis_time1, depanalysis_time2);
+               }
+               else
+                       printf("range critical path: could not find the end of the range\n");
+       }
+
+  return FALSE;
+}
+
+#if 0
+static gboolean write_trace_header(void *hook_data, void *call_data)
+{
+  LttvTraceContext *tc = (LttvTraceContext *)call_data;
+#if 0 //FIXME
+  LttSystemDescription *system = ltt_trace_system_description(tc->t);
+
+  fprintf(a_file,"  Trace from %s in %s\n%s\n\n",
+         ltt_trace_system_description_node_name(system),
+         ltt_trace_system_description_domain_name(system),
+         ltt_trace_system_description_description(system));
+#endif //0
+  return FALSE;
+}
+#endif
+
+
+static int write_event_content(void *hook_data, void *call_data)
+{
+  gboolean result;
+
+//  LttvIAttribute *attributes = LTTV_IATTRIBUTE(lttv_global_attributes());
+
+  LttvTracefileContext *tfc = (LttvTracefileContext *)call_data;
+
+  LttvTracefileState *tfs = (LttvTracefileState *)call_data;
+
+  LttEvent *e;
+
+  guint cpu = tfs->cpu;
+  LttvTraceState *ts = (LttvTraceState*)tfc->t_context;
+  LttvProcessState *process = ts->running_process[cpu];
+
+  e = ltt_tracefile_get_event(tfc->tf);
+
+  lttv_event_to_string(e, a_string, TRUE, 1, tfs);
+
+//  if(a_state) {
+    g_string_append_printf(a_string, " %s ",
+        g_quark_to_string(process->state->s));
+//  }
+
+  g_string_append_printf(a_string,"\n");
+
+  fputs(a_string->str, a_file);
+  return FALSE;
+}
+
+static int field_get_value_int(struct LttEvent *e, struct marker_info *info, GQuark f)
+{
+       struct marker_field *marker_field;
+       int found=0;
+
+       for_each_marker_field(marker_field, info) {
+               if (marker_field->name == f) {
+                       found = 1;
+                       break;
+               }
+       }
+       g_assert(found);
+       return ltt_event_get_long_unsigned(e, marker_field);
+}
+
+static char *field_get_value_string(struct LttEvent *e, struct marker_info *info, GQuark f)
+{
+       struct marker_field *marker_field;
+       int found=0;
+
+       for_each_marker_field(marker_field, info) {
+               if (marker_field->name == f) {
+                       found = 1;
+                       break;
+               }
+       }
+       g_assert(found);
+       return ltt_event_get_string(e, marker_field);
+}
+
+void process_delayed_stack_action(struct process *pinfo, struct sstack_item *item)
+{
+       //printf("processing delayed stack action on pid %d at ", pinfo->pid);
+       //if(((struct process_with_state *) item->data_val)->state.time_begin.tv_nsec == 987799696)
+       //      printf("HERE!!!\n");
+       //print_time(((struct process_with_state *) item->data_val)->state.time_begin);
+       //printf("\n");
+       //printf("stack before:\n");
+       //print_stack(pinfo->stack);
+
+       if(item->data_type == SSTACK_TYPE_PUSH) {
+               struct process_with_state *pwstate = item->data_val;
+               //printf("pushing\n");
+               old_process_push_llev_state(pinfo, &pwstate->state);
+               update_hlev_state(pinfo, pwstate->state.time_begin);
+       }
+       else if(item->data_type == SSTACK_TYPE_POP) {
+               struct process_with_state *pwstate = item->data_val;
+               //printf("popping\n");
+               old_process_pop_llev_state(pinfo, &pwstate->state);
+               update_hlev_state(pinfo, pwstate->state.time_end);
+       }
+       else if(item->data_type == SSTACK_TYPE_EVENT) {
+               struct sstack_event *se = item->data_val;
+               if(se->event_type == HLEV_EVENT_TRY_WAKEUP) {
+                       /* FIXME: should change hlev event from BLOCKED to INTERRUPTED CPU  when receiving TRY_WAKEUP */
+                       struct try_wakeup_event *twe = se->private;
+
+                       /* FIXME: maybe do some more rigorous checking here */
+                       if(pinfo->hlev_state->bstate == HLEV_BLOCKED) {
+                               struct hlev_state_info_blocked *hlev_blocked_private = pinfo->hlev_state->private;
+
+                               hlev_blocked_private->pid_exit = twe->pid;
+                               hlev_blocked_private->time_woken = twe->time;
+                               hlev_blocked_private->llev_state_exit = oldstyle_stack_to_garray(twe->waker->llev_state_stack, twe->waker->stack_current);
+                               //printf("set a non null exit stack on %p, and stack size is %d\n", hlev_blocked_private, hlev_blocked_private->llev_state_exit->len);
+
+                               /*
+                               if(p->stack_current >= 0 && p->llev_state_stack[p->stack_current]->bstate == LLEV_PREEMPTED) {
+                                       old_process_pop_llev_state(pinfo, p->llev_state_stack[p->stack_current]);
+                                       update_hlev_state(pinfo
+                                       old_process_push_llev_state
+                               }*/
+
+                       }
+               }
+       }
+
+       //printf("stack after:\n");
+       //print_stack(pinfo->stack);
+}
+
+static struct process *get_or_init_process_info(struct LttEvent *e, GQuark name, int pid, int *new)
+{
+       gconstpointer val;
+
+       val = g_hash_table_lookup(process_hash_table, &pid);
+       if(val == NULL) {
+               struct process *pinfo;
+               int i;
+
+               /* Initialize new pinfo for newly discovered process */
+               pinfo = g_malloc(sizeof(struct process));
+               pinfo->pid = pid;
+               pinfo->parent = -1; /* unknown parent */
+               pinfo->hlev_history = g_array_new(FALSE, FALSE, sizeof(struct process_state *));
+               pinfo->stack = sstack_new();
+               pinfo->stack_current=-1;
+               pinfo->stack->process_func = process_delayed_stack_action;
+               pinfo->stack->process_func_arg = pinfo;
+               for(i=0; i<PROCESS_STATE_STACK_SIZE; i++) {
+                       pinfo->llev_state_stack[i] = g_malloc(sizeof(struct process_state));
+               }
+
+               pinfo->hlev_state = g_malloc(sizeof(struct process_state));
+               pinfo->hlev_state->bstate = HLEV_UNKNOWN;
+               pinfo->hlev_state->time_begin = e->event_time;
+               pinfo->hlev_state->private = NULL;
+
+               /* set the name */
+               pinfo->name = name;
+
+               g_hash_table_insert(process_hash_table, &pinfo->pid, pinfo);
+               if(new)
+                       *new = 1;
+               return pinfo;
+       }
+       else {
+               if(new)
+                       *new = 0;
+               return val;
+        
+       }
+}
+
+static int differentiate_swappers(int pid, LttEvent *e)
+{
+       if(pid == 0)
+               return pid+e->tracefile->cpu_num+2000000;
+       else
+               return pid;
+}
+
+static int process_event(void *hook_data, void *call_data)
+{
+       LttvTracefileContext *tfc = (LttvTracefileContext *)call_data;
+       LttvTracefileState *tfs = (LttvTracefileState *)call_data;
+       LttEvent *e;
+       struct marker_info *info;
+
+       /* Extract data from event structures and state */
+       guint cpu = tfs->cpu;
+       LttvTraceState *ts = (LttvTraceState*)tfc->t_context;
+       LttvProcessState *process = ts->running_process[cpu];
+       LttTrace *trace = ts->parent.t;
+       struct process *pinfo;
+
+       e = ltt_tracefile_get_event(tfs->parent.tf);
+
+       info = marker_get_info_from_id(tfc->tf->mdata, e->event_id);
+
+       //if(depanalysis_use_time && (ltt_time_compare(e->timestamp, arg_t1) == -1 || ltt_time_compare(e->timestamp, arg_t2) == 1)) {
+       //      return;
+       //}
+       /* Set the pid for the dependency analysis at each event, until we are passed the range. */
+       if(depanalysis_use_time == 3) {
+               if(ltt_time_compare(e->event_time, depanalysis_time2) <= 0) {
+                       depanalysis_range_pid = process->pid;
+               }
+               else {
+                       /* Should stop processing and print results */
+               }
+       }
+
+       /* Code to limit the event count */
+       if(depanalysis_event_limit > 0) {
+               depanalysis_event_limit--;
+       }
+       else if(depanalysis_event_limit == 0) {
+               write_traceset_footer(hook_data, call_data);
+               printf("exit due to event limit reached\n");
+               exit(0);
+       }
+
+       /* write event like textDump for now, for debugging purposes */
+       //write_event_content(hook_data, call_data);
+
+       if(tfc->tf->name == LTT_CHANNEL_SYSCALL_STATE && info->name == LTT_EVENT_SYS_CALL_TABLE) {
+               GQuark q;
+               int *pint = g_malloc(sizeof(int));
+
+               *pint = field_get_value_int(e, info, LTT_FIELD_ID);
+               q = g_quark_from_string(field_get_value_string(e, info, LTT_FIELD_SYMBOL));
+               g_hash_table_insert(syscall_table, pint, q);
+       }
+       else if(tfc->tf->name == LTT_CHANNEL_IRQ_STATE && info->name == LTT_EVENT_LIST_INTERRUPT) {
+               GQuark q;
+               int *pint = g_malloc(sizeof(int));
+
+               *pint = field_get_value_int(e, info, LTT_FIELD_IRQ_ID);
+               q = g_quark_from_string(field_get_value_string(e, info, LTT_FIELD_ACTION));
+               g_hash_table_insert(irq_table, pint, q);
+       }
+       else if(tfc->tf->name == LTT_CHANNEL_SOFTIRQ_STATE && info->name == LTT_EVENT_SOFTIRQ_VEC) {
+               GQuark q;
+               int *pint = g_malloc(sizeof(int));
+
+               *pint = field_get_value_int(e, info, LTT_FIELD_ID);
+               q = g_quark_from_string(field_get_value_string(e, info, LTT_FIELD_SYMBOL));
+               g_hash_table_insert(softirq_table, pint, q);
+       }
+
+
+       /* Only look at events after the statedump is finished.
+        * Before that, the pids in the LttvProcessState are not reliable
+        */
+       if(statedump_finished == 0) {
+               if(tfc->tf->name == LTT_CHANNEL_GLOBAL_STATE && info->name == LTT_EVENT_STATEDUMP_END)
+                       statedump_finished = 1;
+               else
+                       return FALSE;
+
+       }
+
+       pinfo = get_or_init_process_info(e, process->name, differentiate_swappers(process->pid, e), NULL);
+
+       /* the state machine
+        * Process the event in the context of each process
+        */
+
+       if(tfc->tf->name == LTT_CHANNEL_KERNEL && info->name == LTT_EVENT_IRQ_ENTRY) {
+               struct process *event_process_info = pinfo;
+               struct sstack_item *item;
+
+               item = prepare_push_item(event_process_info, LLEV_IRQ, e->event_time);
+               ((struct llev_state_info_irq *) item_private(item))->irq = field_get_value_int(e, info, LTT_FIELD_IRQ_ID);
+               commit_item(event_process_info, item);
+       }
+       else if(tfc->tf->name == LTT_CHANNEL_KERNEL && info->name == LTT_EVENT_IRQ_EXIT) {
+               struct process *event_process_info = pinfo;
+
+               prepare_pop_item_commit(event_process_info, LLEV_IRQ, e->event_time);
+       }
+       else if(tfc->tf->name == LTT_CHANNEL_KERNEL && info->name == LTT_EVENT_SCHED_SCHEDULE) {
+               int next_pid = field_get_value_int(e, info, LTT_FIELD_NEXT_PID);
+               int prev_pid = field_get_value_int(e, info, LTT_FIELD_PREV_PID);
+               if(next_pid != 0) {
+                       struct process *event_process_info = get_or_init_process_info(e, process->name, differentiate_swappers(next_pid, e), NULL);
+                       prepare_pop_item_commit(event_process_info, LLEV_PREEMPTED, e->event_time);
+               }
+               if(prev_pid != 0) {
+                       struct sstack_item *item;
+                       struct process *event_process_info = get_or_init_process_info(e, process->name, differentiate_swappers(prev_pid, e), NULL);
+
+                       item = prepare_push_item(event_process_info, LLEV_PREEMPTED, e->event_time);
+                       ((struct llev_state_info_preempted *) item_private(item))->prev_state = field_get_value_int(e, info, LTT_FIELD_PREV_STATE);
+                       commit_item(event_process_info, item);
+               }
+       }
+       else if(tfc->tf->name == LTT_CHANNEL_KERNEL && info->name == LTT_EVENT_TRAP_ENTRY) {
+               struct process *event_process_info = pinfo;
+               struct sstack_item *item;
+
+               item = prepare_push_item(event_process_info, LLEV_TRAP, e->event_time);
+               commit_item(event_process_info, item);
+       }
+       else if(tfc->tf->name == LTT_CHANNEL_KERNEL && info->name == LTT_EVENT_TRAP_EXIT) {
+               struct process *event_process_info = pinfo;
+
+               prepare_pop_item_commit(event_process_info, LLEV_TRAP, e->event_time);
+       }
+       else if(tfc->tf->name == LTT_CHANNEL_KERNEL && info->name == LTT_EVENT_SYSCALL_ENTRY) {
+               struct process *event_process_info = pinfo;
+               struct sstack_item *item;
+
+               item = prepare_push_item(event_process_info, LLEV_SYSCALL, e->event_time);
+               ((struct llev_state_info_syscall *) item_private(item))->syscall_id = field_get_value_int(e, info, LTT_FIELD_SYSCALL_ID);
+               ((struct llev_state_info_syscall *) item_private(item))->substate = LLEV_SYSCALL__UNDEFINED;
+               commit_item(event_process_info, item);
+       }
+       else if(tfc->tf->name == LTT_CHANNEL_KERNEL && info->name == LTT_EVENT_SYSCALL_EXIT) {
+               struct process *event_process_info = pinfo;
+
+               prepare_pop_item_commit(event_process_info, LLEV_SYSCALL, e->event_time);
+       }
+       else if(tfc->tf->name == LTT_CHANNEL_KERNEL && info->name == LTT_EVENT_SOFT_IRQ_ENTRY) {
+               struct process *event_process_info = pinfo;
+               struct sstack_item *item;
+
+               item = prepare_push_item(event_process_info, LLEV_SOFTIRQ, e->event_time);
+               ((struct llev_state_info_softirq *) item_private(item))->softirq = field_get_value_int(e, info, LTT_FIELD_SOFT_IRQ_ID);
+               commit_item(event_process_info, item);
+       }
+       else if(tfc->tf->name == LTT_CHANNEL_KERNEL && info->name == LTT_EVENT_SOFT_IRQ_EXIT) {
+               struct process *event_process_info = pinfo;
+
+               prepare_pop_item_commit(event_process_info, LLEV_SOFTIRQ, e->event_time);
+       }
+       else if(tfc->tf->name == LTT_CHANNEL_KERNEL && info->name == LTT_EVENT_PROCESS_FORK) {
+               int pid = differentiate_swappers(field_get_value_int(e, info, LTT_FIELD_CHILD_PID), e);
+               struct process *event_process_info = get_or_init_process_info(e, process->name, differentiate_swappers(field_get_value_int(e, info, LTT_FIELD_CHILD_PID), e), NULL);
+               struct sstack_item *item;
+
+               event_process_info->parent = process->pid;
+               //printf("At ");
+               //print_time(e->event_time);
+               //printf(", fork in process %d (%s), creating child %d\n", differentiate_swappers(process->pid, e), g_quark_to_string(process->name), pid);
+
+               item = prepare_push_item(event_process_info, LLEV_RUNNING, e->event_time);
+               commit_item(event_process_info, item);
+               item = prepare_push_item(event_process_info, LLEV_SYSCALL, e->event_time);
+               /* FIXME: this sets fork() as syscall, it's pretty inelegant */
+               ((struct llev_state_info_syscall *) item_private(item))->syscall_id = 57;
+               ((struct llev_state_info_syscall *) item_private(item))->substate = LLEV_SYSCALL__UNDEFINED;
+               commit_item(event_process_info, item);
+
+               item = prepare_push_item(event_process_info, LLEV_PREEMPTED, e->event_time);
+               /* Consider fork as BLOCKED */
+               ((struct llev_state_info_preempted *) item_private(item))->prev_state = 1;
+               commit_item(event_process_info, item);
+
+               //printf("process %d now has a stack of height %d\n", differentiate_swappers(process->pid, e), get_or_init_process_info(e, process->name, differentiate_swappers(process->pid, cpu), NULL)->stack_current-1);
+
+       }
+       else if(tfc->tf->name == LTT_CHANNEL_FS && info->name == LTT_EVENT_EXEC) {
+               struct process *event_process_info = pinfo;
+
+               guint cpu = tfs->cpu;
+               LttvProcessState *process_state = ts->running_process[cpu];
+               event_process_info->name = process_state->name;
+       }
+       else if(tfc->tf->name == LTT_CHANNEL_FS && info->name == LTT_EVENT_OPEN) {
+               struct process_state *pstate = process_find_state(pinfo, LLEV_SYSCALL);
+               struct llev_state_info_syscall *llev_syscall_private;
+               struct llev_state_info_syscall__open *llev_syscall_open_private;
+
+               /* TODO: this is too easy */
+               if(pstate == NULL)
+                       goto next_iter;
+
+               llev_syscall_private = (struct llev_state_info_syscall *)pstate->private;
+
+               //printf("depanalysis: found an open with state %d in pid %d\n", pstate->bstate, process->pid);
+               if(pstate->bstate == LLEV_UNKNOWN)
+                       goto next_iter;
+
+               g_assert(pstate->bstate == LLEV_SYSCALL);
+               g_assert(llev_syscall_private->substate == LLEV_SYSCALL__UNDEFINED);
+
+               llev_syscall_private->substate = LLEV_SYSCALL__OPEN;
+               //printf("setting substate LLEV_SYSCALL__OPEN on syscall_private %p\n", llev_syscall_private);
+               llev_syscall_private->private = g_malloc(sizeof(struct llev_state_info_syscall__open));
+               llev_syscall_open_private = llev_syscall_private->private;
+
+               llev_syscall_open_private->filename = g_quark_from_string(field_get_value_string(e, info, LTT_FIELD_FILENAME));
+               
+       }
+       else if(tfc->tf->name == LTT_CHANNEL_FS && info->name == LTT_EVENT_READ) {
+               struct process_state *pstate = process_find_state(pinfo, LLEV_SYSCALL);
+               struct llev_state_info_syscall *llev_syscall_private;
+               struct llev_state_info_syscall__read *llev_syscall_read_private;
+               GQuark pfileq;
+               int fd;
+
+               /* TODO: this is too easy */
+               if(pstate == NULL)
+                       goto next_iter;
+
+               llev_syscall_private = (struct llev_state_info_syscall *)pstate->private;
+
+               //printf("depanalysis: found an read with state %d in pid %d\n", pstate->bstate, process->pid);
+               if(pstate->bstate == LLEV_UNKNOWN)
+                       goto next_iter;
+
+               g_assert(pstate->bstate == LLEV_SYSCALL);
+               g_assert(llev_syscall_private->substate == LLEV_SYSCALL__UNDEFINED);
+
+               llev_syscall_private->substate = LLEV_SYSCALL__READ;
+               //printf("setting substate LLEV_SYSCALL__READ on syscall_private %p\n", llev_syscall_private);
+               llev_syscall_private->private = g_malloc(sizeof(struct llev_state_info_syscall__read));
+               llev_syscall_read_private = llev_syscall_private->private;
+
+               fd = field_get_value_int(e, info, LTT_FIELD_FD);
+               pfileq = g_hash_table_lookup(process->fds, fd);
+               if(pfileq) {
+                       llev_syscall_read_private->filename = pfileq;
+               }
+               else {
+                       char *tmp;
+                       asprintf(&tmp, "Unknown filename, fd %d", fd);
+                       llev_syscall_read_private->filename = g_quark_from_string(tmp);
+                       free(tmp);
+               }
+       }
+       else if(tfc->tf->name == LTT_CHANNEL_FS && info->name == LTT_EVENT_POLL_EVENT) {
+               struct process_state *pstate = process_find_state(pinfo, LLEV_SYSCALL);
+               struct llev_state_info_syscall *llev_syscall_private;
+               struct llev_state_info_syscall__poll *llev_syscall_poll_private;
+               GQuark pfileq;
+               int fd;
+
+               /* TODO: this is too easy */
+               if(pstate == NULL)
+                       goto next_iter;
+
+               llev_syscall_private = (struct llev_state_info_syscall *)pstate->private;
+
+               //printf("depanalysis: found an poll with state %d in pid %d\n", pstate->bstate, process->pid);
+               if(pstate->bstate == LLEV_UNKNOWN)
+                       goto next_iter;
+
+               /* poll doesn't have a single event that gives the syscall args. instead, there can be an arbitrary
+                * number of fs_pollfd or fd_poll_event events
+                * We use the fd_poll_event event, which occurs for each fd that had activity causing a return of the poll()
+                * For now we only use the first.
+                * We should do something about this. FIXME
+                */
+               if(llev_syscall_private->substate == LLEV_SYSCALL__POLL)
+                       goto next_iter;
+
+               g_assert(pstate->bstate == LLEV_SYSCALL);
+               g_assert(llev_syscall_private->substate == LLEV_SYSCALL__UNDEFINED);
+
+               llev_syscall_private->substate = LLEV_SYSCALL__POLL;
+               //printf("setting substate LLEV_SYSCALL__POLL on syscall_private %p\n", llev_syscall_private);
+               llev_syscall_private->private = g_malloc(sizeof(struct llev_state_info_syscall__poll));
+               llev_syscall_poll_private = llev_syscall_private->private;
+
+               fd = field_get_value_int(e, info, LTT_FIELD_FD);
+               pfileq = g_hash_table_lookup(process->fds, fd);
+               if(pfileq) {
+                       llev_syscall_poll_private->filename = pfileq;
+               }
+               else {
+                       char *tmp;
+                       asprintf(&tmp, "Unknown filename, fd %d", fd);
+                       llev_syscall_poll_private->filename = g_quark_from_string(tmp);
+                       free(tmp);
+               }
+       }
+       else if(tfc->tf->name == LTT_CHANNEL_KERNEL && info->name == LTT_EVENT_SCHED_TRY_WAKEUP) {
+               struct sstack_event *se = g_malloc(sizeof(struct sstack_event));
+               struct try_wakeup_event *twe = g_malloc(sizeof(struct try_wakeup_event));
+               struct sstack_item *item = sstack_item_new_event();
+               int target = field_get_value_int(e, info, LTT_FIELD_PID);
+               struct process *target_pinfo;
+               int result;
+
+               se->event_type = HLEV_EVENT_TRY_WAKEUP;
+               se->private = twe;
+               //printf("pushing try wake up event in context of %d\n", pinfo->pid);
+
+               twe->pid = differentiate_swappers(process->pid, e);
+               twe->time = e->event_time;
+               twe->waker = pinfo;
+
+               /* FIXME: the target could not yet have an entry in the hash table, we would then lose data */
+               target_pinfo = g_hash_table_lookup(process_hash_table, &target);
+               if(!target_pinfo)
+                       goto next_iter;
+
+               item->data_val = se;
+               item->delete_data_val = delete_data_val;
+
+               sstack_add_item(target_pinfo->stack, item);
+
+               /* Now pop the blocked schedule out of the target */
+               result = try_pop_blocked_llev_preempted(target_pinfo, e->event_time);
+
+               if(result) {
+                       struct sstack_item *item;
+                       struct process *event_process_info = target_pinfo;
+
+                       item = prepare_push_item(event_process_info, LLEV_PREEMPTED, e->event_time);
+                       ((struct llev_state_info_preempted *) item_private(item))->prev_state = -1; /* special value meaning post-block sched out */
+                       commit_item(event_process_info, item);
+               }
+
+       }
+
+       next_iter:
+       skip_state_machine:
+       return FALSE;
+}
+
+void print_sstack_private(struct sstack_item *item)
+{
+       struct process_with_state *pwstate = item->data_val;
+
+       if(pwstate && item->data_type == SSTACK_TYPE_PUSH)
+               printf("\tstate: %s", llev_state_infos[pwstate->state.bstate].name);
+
+       printf(" (");
+       print_time(pwstate->state.time_begin);
+       printf("-");
+       print_time(pwstate->state.time_end);
+       printf("\n");
+               
+}
+
+static LttTime ltt_time_from_string(const char *str)
+{
+       LttTime retval;
+
+       char *decdot = strchr(str, '.');
+
+       if(decdot) {
+               *decdot = '\0';
+               retval.tv_nsec = atol(decdot+1);
+       }
+       else {
+               retval.tv_nsec = 0;
+       }
+
+       retval.tv_sec = atol(str);
+
+       return retval;
+}
+
+static void arg_t1(void *hook_data)
+{
+       printf("arg_t1\n");
+       depanalysis_use_time |= 1;
+       depanalysis_time1 = ltt_time_from_string(arg_t1_str);
+}
+
+static void arg_t2(void *hook_data)
+{
+       depanalysis_use_time |= 2;
+       depanalysis_time2 = ltt_time_from_string(arg_t2_str);
+}
+
+static void arg_pid(void *hook_data)
+{
+}
+
+static void arg_limit(void *hook_data)
+{
+}
+
+static void init()
+{
+  gboolean result;
+
+  print_sstack_item_data = print_sstack_private;
+
+  LttvAttributeValue value;
+
+  LttvIAttribute *attributes = LTTV_IATTRIBUTE(lttv_global_attributes());
+
+  a_file = stdout;
+
+  lttv_option_add("dep-time-start", 0, "dependency analysis time of analysis start", "time",
+      LTTV_OPT_STRING, &arg_t1_str, arg_t1, NULL);
+  lttv_option_add("dep-time-end", 0, "dependency analysis time of analysis end", "time",
+      LTTV_OPT_STRING, &arg_t2_str, arg_t2, NULL);
+  lttv_option_add("dep-pid", 0, "dependency analysis pid", "pid",
+      LTTV_OPT_INT, &depanalysis_range_pid_searching, arg_pid, NULL);
+  lttv_option_add("limit-events", 0, "dependency limit event count", "count",
+      LTTV_OPT_INT, &depanalysis_event_limit, arg_limit, NULL);
+
+  process_hash_table = g_hash_table_new(g_int_hash, g_int_equal);
+  syscall_table = g_hash_table_new(g_int_hash, g_int_equal);
+  irq_table = g_hash_table_new(g_int_hash, g_int_equal);
+  softirq_table = g_hash_table_new(g_int_hash, g_int_equal);
+
+  a_string = g_string_new("");
+
+  result = lttv_iattribute_find_by_path(attributes, "hooks/event",
+      LTTV_POINTER, &value);
+  g_assert(result);
+  event_hook = *(value.v_pointer);
+  g_assert(event_hook);
+  lttv_hooks_add(event_hook, process_event, NULL, LTTV_PRIO_DEFAULT);
+
+//  result = lttv_iattribute_find_by_path(attributes, "hooks/trace/before",
+//      LTTV_POINTER, &value);
+//  g_assert(result);
+//  before_trace = *(value.v_pointer);
+//  g_assert(before_trace);
+//  lttv_hooks_add(before_trace, write_trace_header, NULL, LTTV_PRIO_DEFAULT);
+//
+  result = lttv_iattribute_find_by_path(attributes, "hooks/traceset/before",
+      LTTV_POINTER, &value);
+  g_assert(result);
+  before_traceset = *(value.v_pointer);
+  g_assert(before_traceset);
+  lttv_hooks_add(before_traceset, write_traceset_header, NULL,
+      LTTV_PRIO_DEFAULT);
+
+  result = lttv_iattribute_find_by_path(attributes, "hooks/traceset/after",
+      LTTV_POINTER, &value);
+  g_assert(result);
+  after_traceset = *(value.v_pointer);
+  g_assert(after_traceset);
+  lttv_hooks_add(after_traceset, write_traceset_footer, NULL,
+      LTTV_PRIO_DEFAULT);
+}
+
+static void destroy()
+{
+  lttv_option_remove("dep-time-start");
+  lttv_option_remove("dep-time-end");
+  lttv_option_remove("dep-pid");
+  lttv_option_remove("limit-events");
+
+  g_hash_table_destroy(process_hash_table);
+  g_hash_table_destroy(syscall_table);
+  g_hash_table_destroy(irq_table);
+  g_hash_table_destroy(softirq_table);
+
+  g_string_free(a_string, TRUE);
+
+  lttv_hooks_remove_data(event_hook, write_event_content, NULL);
+//  lttv_hooks_remove_data(before_trace, write_trace_header, NULL);
+  lttv_hooks_remove_data(before_traceset, write_traceset_header, NULL);
+  lttv_hooks_remove_data(after_traceset, write_traceset_footer, NULL);
+}
+
+LTTV_MODULE("depanalysis", "Dependency analysis test", \
+           "Produce a dependency analysis of a trace", \
+           init, destroy, "stats", "batchAnalysis", "option", "print")
+
diff --git a/lttv/modules/text/sstack.c b/lttv/modules/text/sstack.c
new file mode 100644 (file)
index 0000000..532bab3
--- /dev/null
@@ -0,0 +1,405 @@
+#include <glib.h>
+
+#include "sstack.h"
+
+/* This is the implementation of sstack, a data structure that holds
+ * operations done on a stack in order to play them on a stack a short
+ * while later. They are played when dependencies are fulfilled. The
+ * operations are held in a queue.
+ *
+ * Operations include PUSH of data, POP, as well as other special markers.
+ *
+ * Stack operations are defined by a struct sstack_item. Each struct
+ * sstack_item has 3 flags:
+ *   - finished
+ *   - processable
+ *   - deletable
+ *
+ * Finished is raised when all the dependencies of the operation are
+ * fulfilled. POPs are always created finished because they have no
+ * dependencies. PUSHes are marked finished when their corresponding
+ * POP is added to the queueit is the PUSHes
+ * that contain the and EVENTs are always created finished.
+ *
+ * Once an operation is finished
+ */
+
+void (*print_sstack_item_data)(struct sstack_item *);
+
+/* Debugging function: print a queue item */
+
+static void print_item(struct sstack_item *item)
+{
+       char *label;
+
+       if(item->data_type == SSTACK_TYPE_PUSH) {
+               label = "PUSH";
+       }
+       else if(item->data_type == SSTACK_TYPE_POP) {
+               label = "POP";
+       }
+       else {
+               label = "UNKNOWN";
+       }
+
+       printf("%-10s    %-2u%-2u%-2u", label, item->finished, item->processable, item->deletable);
+       /* hack: call this external, application-dependant function to show the private data in the item */
+       print_sstack_item_data(item);
+}
+
+/* Debugging function: print the queue as it is now */
+
+void print_stack(struct sstack *stack)
+{
+       int i;
+
+       printf("************************\n");
+       printf("**     %-10s    F P D\n", "label");
+       for(i=0; i<stack->array->len; i++) {
+               struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, i);
+
+               printf("** %-3d- ", i);
+               print_item(item);
+       }
+       printf("\n");
+}
+
+static void try_start_deleting(struct sstack *stack)
+{
+       int index = stack->array->len-1;
+
+       while(index >= 0 && g_array_index(stack->array, struct sstack_item *, index)->deletable) {
+               struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, index);
+
+               if(item->delete_data_val)
+                       item->delete_data_val(item->data_val);
+
+               //g_array_free(item->depends, FALSE);
+               //g_array_free(item->rev_depends, FALSE);
+               g_free(item);
+
+               g_array_remove_index(stack->array, index);
+               index--;
+       }
+
+       if(stack->proc_index > stack->array->len)
+               stack->proc_index = stack->array->len;
+}
+
+/* An item is deletable as soon as it is processed. However, all the items after it
+ * in the list must be deleted before it can be deleted.
+ *
+ * After this function, try_start_deleting must be called.
+ */
+
+static void mark_deletable(struct sstack *stack, int index)
+{
+       struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, index);
+
+       item->deletable = 1;
+
+//     if(index == stack->array->len - 1) {
+//             start_deleting(stack);
+//     }
+}
+
+#if 0
+/* Called to process an index of the queue */
+
+static void process(struct sstack *stack, int index)
+{
+       g_assert(stack->proc_index == index);
+
+       //printf("sstack: starting to process\n");
+       while(stack->proc_index < stack->array->len) {
+               struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, stack->proc_index);
+
+               if(!item->processable)
+                       break;
+
+               //printf("sstack: processing ");
+               //print_item(item);
+
+               if(stack->process_func) {
+                       stack->process_func(stack->process_func_arg, item);
+               }
+               else {
+                       printf("warning: no process func\n");
+               }
+
+               stack->proc_index++;
+
+               mark_deletable(stack, stack->proc_index-1);
+               if(item->pushpop >= 0 && item->pushpop < stack->proc_index-1) {
+                       mark_deletable(stack, item->pushpop);
+               }
+               try_start_deleting(stack);
+       }
+       //printf("sstack: stopping processing\n");
+}
+
+/* Called to mark an index of the queue as processable */
+
+static void mark_processable(struct sstack *stack, int index)
+{
+       struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, index);
+
+       item->processable = 1;
+
+       if(stack->proc_index <= stack->array->len && stack->proc_index == index) {
+               process(stack, index);
+       }
+}
+
+/* Called to check whether an index of the queue could be marked processable. If so,
+ * mark it processable.
+ *
+ * To be processable, an item must:
+ * - be finished
+ * - have its push/pop dependency fulfilled
+ * - have its other dependencies fulfilled
+ */
+
+static void try_mark_processable(struct sstack *stack, int index)
+{
+       int i;
+       int all_finished = 1;
+
+       struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, index);
+
+       //for(i=0; i<stack->array->len; i++) {
+       //      if(!g_array_index(stack->array, struct sstack_item *, index)->finished) {
+       //              all_finished = 0;
+       //              break;
+       //      }
+       //}
+
+       /* Theoritically, we should confirm that the push/pop dependency is
+        * finished, but in practice, it's not necessary. If we are a push, the
+        * corresponding pop is always finished. If we are a pop and we exist,
+        * the corresponding push is necessarily finished.
+        */
+
+       //if(all_finished) {
+       if(item->finished) {
+               mark_processable(stack, index);
+       }
+       //}
+}
+
+/* Called to mark an index of the queue as finished */
+
+static void mark_finished(struct sstack *stack, int index)
+{
+       struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, index);
+
+       item->finished = 1;
+
+       try_mark_processable(stack, index);
+}
+
+#endif
+/* --------------------- */
+
+static void try_advance_processing(struct sstack *stack)
+{
+       //g_assert(stack->proc_index == index);
+
+       //printf("sstack: starting to process\n");
+       while(stack->proc_index < stack->array->len) {
+               struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, stack->proc_index);
+
+               //if(!item->finished) {
+               //      break;
+               //}
+
+               //printf("sstack: processing ");
+               //print_item(item);
+
+               if(stack->process_func) {
+                       stack->process_func(stack->process_func_arg, item);
+               }
+               else {
+                       printf("warning: no process func\n");
+               }
+
+               stack->proc_index++;
+
+               if(item->data_type == SSTACK_TYPE_POP)
+                       mark_deletable(stack, stack->proc_index-1);
+               if(item->pushpop >= 0 && item->pushpop < stack->proc_index-1) {
+                       mark_deletable(stack, item->pushpop);
+               }
+       }
+       try_start_deleting(stack);
+       //printf("sstack: stopping processing\n");
+}
+
+
+/* Add an item to the queue */
+
+void sstack_add_item(struct sstack *stack, struct sstack_item *item)
+{
+       int index;
+
+       g_array_append_val(stack->array, item);
+
+       //printf("stack after adding\n");
+       //print_stack(stack);
+
+       index = stack->array->len-1;
+
+       if(item->data_type == SSTACK_TYPE_PUSH) {
+               int top_of_wait_pop_stack;
+
+               if(stack->wait_pop_stack->len && g_array_index(stack->wait_pop_stack, int, stack->wait_pop_stack->len-1)) {
+                       /* if the preceding is a wait_for_pop (and there is a preceding), push a wait_for_pop */
+                       const int one=1;
+                       g_array_append_val(stack->wait_pop_stack, one);
+               }
+               else {
+                       /* otherwise, push what the item wants */
+                       g_array_append_val(stack->wait_pop_stack, item->wait_pop);
+               }
+
+               top_of_wait_pop_stack = g_array_index(stack->wait_pop_stack, int, stack->wait_pop_stack->len-1);
+
+               g_array_append_val(stack->pushes, index);
+
+               //printf("after pushing:\n");
+               //print_stack(stack);
+               if(top_of_wait_pop_stack == 0) {
+                       try_advance_processing(stack);
+                       /* ASSERT that we processed the whole sstack */
+               }
+               //printf("after processing:\n");
+               //print_stack(stack);
+       }
+       else if(item->data_type == SSTACK_TYPE_POP) {
+               item->finished = 1;
+
+               if(stack->pushes->len > 0) {
+                       /* FIXME: confirm we are popping what we expected to pop */
+                       item->pushpop = g_array_index(stack->pushes, int, stack->pushes->len-1);
+                       g_array_index(stack->array, struct sstack_item *, item->pushpop)->pushpop = index;
+                       g_array_index(stack->array, struct sstack_item *, item->pushpop)->finished = 1;
+
+                       g_array_remove_index(stack->pushes, stack->pushes->len-1);
+               }
+
+               if(stack->wait_pop_stack->len > 0) {
+                       int top_of_wait_pop_stack;
+
+                       g_array_remove_index(stack->wait_pop_stack, stack->wait_pop_stack->len-1);
+
+                       if(stack->wait_pop_stack->len > 0) {
+                               top_of_wait_pop_stack = g_array_index(stack->wait_pop_stack, int, stack->wait_pop_stack->len-1);
+
+                               if(top_of_wait_pop_stack == 0)
+                                       try_advance_processing(stack);
+                       }
+                       else {
+                               try_advance_processing(stack);
+                       }
+               }
+               else {
+                       try_advance_processing(stack);
+               }
+       }
+
+       //printf("stack after processing\n");
+       //print_stack(stack);
+}
+
+/* Force processing of all items */
+
+void sstack_force_flush(struct sstack *stack)
+{
+       int i;
+
+       for(i=0; i<stack->array->len; i++) {
+               struct sstack_item *item = g_array_index(stack->array, struct sstack_item *, i);
+
+               if(!item->finished) {
+                       item->finished = 1;
+               }
+       }
+
+       try_advance_processing(stack);
+}
+
+/* Create a new sstack */
+
+struct sstack *sstack_new(void)
+{
+       struct sstack *retval;
+
+       retval = (struct sstack *) g_malloc(sizeof(struct sstack));
+
+       retval->array = g_array_new(FALSE, FALSE, sizeof(struct sstack_item *));
+       retval->pushes = g_array_new(FALSE, FALSE, sizeof(int));
+       retval->wait_pop_stack = g_array_new(FALSE, FALSE, sizeof(int));
+       retval->proc_index = 0;
+       retval->process_func = NULL;
+
+       return retval;
+}
+
+/* Create a new sstack_item. Normally not invoked directly. See other functions below. */
+
+struct sstack_item *sstack_item_new(void)
+{
+       struct sstack_item *retval;
+
+       retval = (struct sstack_item *) g_malloc(sizeof(struct sstack_item));
+       retval->finished = 0;
+       retval->processable = 0;
+       retval->deletable = 0;
+       retval->data_type = 0;
+       retval->data_val = NULL;
+       retval->delete_data_val = NULL;
+       retval->pushpop = -1;
+       retval->wait_pop = 0;
+       //retval->depends = g_array_new(FALSE, FALSE, sizeof(int));
+       //retval->rev_depends = g_array_new(FALSE, FALSE, sizeof(int));
+
+       return retval;
+}
+
+/* Create a new sstack_item that will represent a PUSH operation */
+
+struct sstack_item *sstack_item_new_push(unsigned char wait_pop)
+{
+       struct sstack_item *retval = sstack_item_new();
+
+       retval->data_type = SSTACK_TYPE_PUSH;
+       retval->wait_pop = wait_pop;
+
+       return retval;
+}
+
+/* Create a new sstack_item that will represent a POP operation */
+
+struct sstack_item *sstack_item_new_pop(void)
+{
+       struct sstack_item *retval = sstack_item_new();
+
+       retval->data_type = SSTACK_TYPE_POP;
+       retval->finished = 1;
+
+       return retval;
+}
+
+/* Create a new sstack_item that will represent an EVENT operation */
+
+struct sstack_item *sstack_item_new_event(void)
+{
+       struct sstack_item *retval = sstack_item_new();
+
+       retval->data_type = SSTACK_TYPE_EVENT;
+       retval->finished = 1;
+       retval->processable = 1;
+       retval->deletable = 1;
+
+       return retval;
+}
diff --git a/lttv/modules/text/sstack.h b/lttv/modules/text/sstack.h
new file mode 100644 (file)
index 0000000..4ff713b
--- /dev/null
@@ -0,0 +1,72 @@
+#ifndef SSTACK_H
+#define SSTACK_H
+
+#define SSTACK_TYPE_PUSH  1
+#define SSTACK_TYPE_POP   2
+#define SSTACK_TYPE_EVENT 3
+
+//#define SSTACK_PUSH_VAL(i) (()i->data_val)
+
+/* An item of a struct sstack, that describes a stack operation */
+
+struct sstack_item {
+       /* state flags */
+       unsigned char finished;
+       unsigned char processable;
+       unsigned char deletable;
+
+       /* Type of operation: SSTACK_TYPE_PUSH, SSTACK_TYPE_POP or SSTACK_TYPE_EVENT */
+       int data_type;
+       /* private, application-dependant data */
+       void *data_val;
+
+       /* Function to call to delete data_val */
+       void (*delete_data_val)(void *data_val);
+
+       /* The index of the corresponding push (for a pop) or pop (for a push) */
+       int pushpop;
+
+       /* Does this item require that we wait for its pop to process it */
+       int wait_pop;
+
+       GArray *depends;
+       GArray *rev_depends;
+};
+
+/* external debugging function to print the private data of an item */
+extern void (*print_sstack_item_data)(struct sstack_item *);
+
+/* An actual sstack */
+
+struct sstack {
+       GArray *array;
+
+       /* Stack of the indexes of the pushes that have been done. An index is popped when the
+        * corresponding pop is added to the sstack. This enables us to find the index of the
+        * last push.
+        */
+       GArray *pushes;
+
+       /* Stack of 0's and 1's. 0: don't wait for pop to process the children
+        * 1: wait for pop to process its children
+        */
+       GArray *wait_pop_stack;
+
+       /* Next item we must try to process */
+       int proc_index;
+
+       void (*process_func)(void *arg, struct sstack_item *item);
+       void *process_func_arg; /* the pointer passed as the "arg" argument of process_func */
+};
+
+struct sstack_item *sstack_new_item();
+
+void sstack_add_item(struct sstack *stack, struct sstack_item *item);
+
+struct sstack *sstack_new(void);
+struct sstack_item *sstack_item_new(void);
+struct sstack_item *sstack_item_new_push(unsigned char finished);
+struct sstack_item *sstack_item_new_pop(void);
+struct sstack_item *sstack_item_new_evt(void);
+
+#endif /* SSTACK_H */
This page took 0.052301 seconds and 4 git commands to generate.