From 6ea2aecbb240d0180828fa97d50ad17facb22fa1 Mon Sep 17 00:00:00 2001 From: compudj Date: Tue, 18 May 2004 22:15:06 +0000 Subject: [PATCH] hooks with priority, process traceset with strict boundaries and lttvwindow event delivery proposal git-svn-id: http://ltt.polymtl.ca/svn@528 04897980-b3bd-0310-b5e0-8ef037075253 --- ltt/branches/poly/doc/developer/hook_prio.txt | 35 +++ .../developer/lttvwindow_events_delivery.txt | 264 ++++++++++++++++++ .../process_traceset_strict_boundaries.txt | 142 ++++++++++ 3 files changed, 441 insertions(+) create mode 100644 ltt/branches/poly/doc/developer/hook_prio.txt create mode 100644 ltt/branches/poly/doc/developer/lttvwindow_events_delivery.txt create mode 100644 ltt/branches/poly/doc/developer/process_traceset_strict_boundaries.txt diff --git a/ltt/branches/poly/doc/developer/hook_prio.txt b/ltt/branches/poly/doc/developer/hook_prio.txt new file mode 100644 index 00000000..349a8ec5 --- /dev/null +++ b/ltt/branches/poly/doc/developer/hook_prio.txt @@ -0,0 +1,35 @@ +Linux Trace Toolkit + +Mathieu Desnoyers 18-05-2004 + + +Seeing that a very precise hook call ordering is needed when processing events +(especially the order for calling state update hooks and event delivery hooks), +this document defines a new type and interface that permits to merge all kind of +hooks, eventually sorted by the priority associated to them. + +As the LttvHooksById has never been used up to this point in the project, I +doubt that any real need for it exists. If we still want to implement it, it +would require to create temporary by_id hook lists, add all the specific by_id +hooks and the main hooks to it, and sort it before the traceset reading starts. + +- Type LttvHooksPrio + +This is a new type containing hooks associated with a priority. It has its own +interface which pretty much looks like the one found in hook.h, plus the fact +that a priority is associated with each hook. (lttv_hooks_prio_add, +lttv_hooks_prio_call, lttv_hooks_prio_remove are sample names of functions +offered by this interface) The container for this type would be a garray, just +like hook.c, but a lttv_hooks_prio_sort would be required in order to sort the +array before using lttv_hooks_prio_call. + +The viewers will just have to pass hooks to the main window through this type, +using the hookprio.h interface to manipulate it. Then, the main window will add +them and remove them from the context to deliver exactly the events requested by +each viewer through process traceset. + +If we want to make this data type more encapsulated, we could call +lttv_hooks_prio_sort upon each modification to the structure. Then, a simple +lttv_hooks_prio_call would be assured to call the hooks in the right order. + + diff --git a/ltt/branches/poly/doc/developer/lttvwindow_events_delivery.txt b/ltt/branches/poly/doc/developer/lttvwindow_events_delivery.txt new file mode 100644 index 00000000..2a7da4e0 --- /dev/null +++ b/ltt/branches/poly/doc/developer/lttvwindow_events_delivery.txt @@ -0,0 +1,264 @@ +Linux Trace Toolkit + +Mathieu Desnoyers 17-05-2004 + + +This document explains how the lttvwindow API could process the event requests +of the viewers, merging event requests and hook lists to benefit from the fact +that process_traceset can call multiple hooks for the same event. + +First, we will explain the detailed process of event delivery in the current +framework. We will then study its strengths and weaknesses. + +In a second time, a framework where the events requests are dealt by the main +window with fine granularity will be described. We will then discussed the +advantages and inconvenients over the first framework. + + +1. (Actual) Boundaryless event reading + +Actually, viewers request events in a time interval from the main window. They +also specify a (not so) maximum number of events to be delivered. In fact, the +number of events to read only gives a stop point, from where only events with +the same timestamp will be delivered. + +Viewers register hooks themselves in the traceset context. When merging read +requests in the main window, all hooks registered by viewers will be called for +the union of all the read requests, because the main window has no control on +hook registration. + +The main window calls process_traceset on its own for all the intervals +requested by all the viewers. It must not duplicate a read of the same time +interval : it could be very hard to filter by viewers. So, in order to achieve +this, time requests are sorted by start time, and process_traceset is called for +each time request. We keep the last event time between each read : if the start +time of the next read is lower than the time reached, we continue the reading +from the actual position. + +We deal with specific number of events requests (infinite end time) by +garantying that, starting from the time start of the request, at least that +number of events will be read. As we can't do it efficiently without interacting +very closely with process_traceset, we always read the specified number of +events requested starting from the current position when we answer to a request +based on the number of events. + +The viewers have to filter events delivered by traceset reading, because they +can be asked by another viewer for a totally (or partially) different time +interval. + + +Weaknesses + +- process_middle does not guarantee the number of events read + +First of all, a viewer that requests events to process_traceset has no garantee +that it will get exactly what it asked for. For example, a direct call to +traceset_middle for a specific number of events will delived _at least_ that +quantity of events, plus the ones that have the same timestamp that the last one +has. + +- Border effects + +Viewer's writers will have to deal with a lot of border effects caused by the +particularities of the reading by selecting the information. + +- Lack of encapsulation + +The viewer's writer will have to take into account all the border effects caused +by the interaction with other modules. This means that event if a viewer works +well alone or with another viewer, it's possible that new bugs arises when a new +viewer comes around. + + +- Duplication of the work + +Time based filters and counters of events will have to be implemented at the +viewer's side, which is a duplication of the functionnalities that would +normally be expected from the tracecontext API. + +- Lack of control over the data input + +As we expect module's writers to prefer to be as close as possible from the raw +datas, making them interact with a lower level library that gives them a data +input that they only control by further filtering of the input is not +appropriated. We should expect some reluctancy from them about using this API +because of this lack of control on the input. + +- Speed cost + +All hooks of all viewers will be called for all the time intervals. So, if we +have a detailed events list and a control flow view, asking both for different +time intervals, the detailed events list will have to filter all the events +delivered originally to the control flow view. This can be a case occuring quite +often. + + + +Strengths + +- Simple concatenation of time intervals at the main window level. + +Having the opportunity of delivering more events than necessary to the viewers +means that we can concatenate time intervals and number of events requested +fairly easily, while being hard to determine if some specific cases will be +wrong by formal methods. + +- No duplication of the tracecontext API + +Viewers deal directly with the tracecontext API for registering hooks, removing +a layer of encapsulation. + + + + + +2. (Proposed) Strict boundaries events reading + +The idea behind this method is to provide exactly the events requested by the +viewers to them, no more, no less. + +This method relies on the fact that time based and number based event requests +are, by nature, totally different and that there is no real interest in merging +both requests types. + +It uses the new API for process traceset suggested in the document +process_traceset_strict_boundaries.txt. + +It also means that the lttvwindow API will have to deal with viewer's hooks. +Those will not be allowed to add them directly in the context. They will give +them to the lttvwindow API, along with the time interval or the position and +number of events. The lttvwindow API will have to take care of adding and +removing hooks for the different time intervals requested. That means that hooks +insertion and removal will be done between each traceset processing based on +the time intervals and event positions related to each hook. We must therefore +provide a simple interface for hooks passing between the viewers and the main +window, make them easier to manage from the main window. The new type +LttvHooksPrio solves this problem. + + +Architecture + +Added to the lttvwindow API : + + +- lttvwindow_time_interval_request +arguments : +( MainWindow *main_win, + TimeWindow time_requested, guint num_events, + LttvHooksPrio process_traceset_middle, + LttvHook after_process_traceset, + gpointer after_process_traceset_data); + +- lttvwindow_position_request +arguments : +( MainWindow *main_win, + LttvTracesetPosition position, guint max_num_events, + LttvHooksPrio process_traceset_middle, + LttvHook after_process_traceset, + gpointer after_process_traceset_data); + + +Internal functions : + +- lttvwindow_process_pending_requests + + + +Implementation + + +- Type LttvHooksPrio + +see hook_prio.h + + +- lttvwindow_time_interval_request + +It adds the TimeRequest struct to the array of time requests pending and +registers a pending request for the next g_idle if none is registered. + +typedef struct _TimeRequest { + TimeWindow time_window; + guint num_events; + LttvHooksPrio middle_hooks; + LttvHook after_hook; + gpointer after_hook_data; +} TimeRequest; + + +- lttvwindow_position_request + +It adds a PositionRequest struct to the array of position requests pending and +registers a pending request for the next g_idle if none is registered. + +typedef struct _PositionRequest { + LttvTracesetPosition position; + guint max_num_events; + LttvHooksPrio middle_hooks; + LttvHook after_hook; + gpointer after_hook_data; +} PositionRequest; + + + +- lttvwindow_process_pending_requests + +This internal function gets called by g_idle, taking care of the pending +requests. It is responsible for concatenation of time intervals and position +requests. It does it while it calls process traceset. Here is the detailed +description of the way it works : + +It treats time interval requests and position requests as two different cases. +So let's start with time interval requests. + +- Time interval requests servicing + +(1) +It starts by finding the time interval request with the lowest start time and +the others with the same start time. It add its (or their) hooks to the context. +It will use this start time to seek in the traceset. + +Then, it searches for what event comes first : the end of one of the time +request actually added in the context or the start of a time request that is not +in the context. It uses this value as a end boundary for the first process +traceset middle call. + +After a process traceset middle ends, we check if we have reached the end time +of any time request. If so, we call the time requests process traceset end hook +and remove this time request from the context and the array of time requests. If +the context has no hooks left, that means that we have to jump further in the +traceset. We then simply have to use the exact routine that we used for (1). + +Else, if there are hooks left, that means that we have not finished requesting +one hook's time interval request yet, but maybe we must add a new time request +to the hook list of the context. We start back at point (1), except that instead +of finding the lowest start time, we simply keep the hooks already present in +the context and add hooks that has their start time with a value equal to the +last process traceset's end time. + + +- Position requests servicing + +As it is nearly impossible to compare two traceset positions without replaying +part of the traceset reading, which is not very efficient, we consider that the +performance cost of doing one trace read per request does not justify position +requests combinations. So, each position request will be serviced independently. + + + + +Weaknesses + +- Position requests are serviced independently, which may duplicate traceset +reads. + + + +Strengths + +- Removes the need for filtering of information supplied to the viewers. + +- Viewers have a better control on their data input. + +- Solves all the weaknesses idenfied in the actual boundaryless traceset +reading. diff --git a/ltt/branches/poly/doc/developer/process_traceset_strict_boundaries.txt b/ltt/branches/poly/doc/developer/process_traceset_strict_boundaries.txt new file mode 100644 index 00000000..40c0c7c7 --- /dev/null +++ b/ltt/branches/poly/doc/developer/process_traceset_strict_boundaries.txt @@ -0,0 +1,142 @@ +Linux Trace Toolkit + +Mathieu Desnoyers 17-05-2004 + + +1. Read Requests Cases Study + +The goal of this document is to describe the typical behavior of viewers when +they request data to a process traceset. After the implementation of three +viewers, with different needs, the idea of their need for a trace processing API +is getting clearer. + +They are splitted in two different categories : the first one is the one where +the viewers select the events they need by specifying a time interval in the +traceset and the second one is where the viewers specify a start event by it's +position in the traceset and a certain amount of events it needs. + + + +Control Flow Viewer + +This viewer, consisting in a two dimensions graph, shows the different processes +as its y axis and the time as x axis. It's clear that it needs to get the events +by specifying a start time and an end time, constituing a time interval. + + +Detailed Events List + +This list has nothing to do with time : it shows the events one by one. It cares +about the quantity of events, not their time. + +It would be simple to get the events one by one if we were reading only one +tracefile (one cpu), but the way events are read through each trace +(monothically increasing time) makes it a little bit more difficult to specify +how to increment event position. We will determine how it could be done simply. + +Let's define an event position. It's composed of a tracefile number, a bloc +number and an index in the bloc. + +A viewer could ask for a specific event position as a start event. It would +specify a number of events it needs. As a first call, it could ask for tracefile +0, bloc 0, event 0. Afterward, it can reuse information from events delivered to +keep track of the next events it needs. + +Now, let's see how process traceset could handle it. It would seek in the +traceset, searching the position number. +(need a new lttv_process_traceset_seek_position) + +Then, the viewer could simply call a process traceset function specifying a +number of events to get. + +The whole concept of numbering events would be hidden in the order in which the +process traceset gets the events in a monothically increasing time. + +We sould specify that a request from such a viewer should be of one more event +than needed : it would use the last event position to seek in the traceset for +the next read. So, for example, a request for 50 events would ask for 51, +keeping the event position of event 51. + + + +2. Architecture + +Two different sets of API functions offered to read tracesets : + +lttv_process_traceset_seek_time +lttv_process_traceset_middle_time + +lttv_process_traceset_seek_position +lttv_process_traceset_middle_position +lttv_traceset_context_position_save + + +Of course, the typical use will be to call the seek_time with the middle_time, +and similarly for position functions, but the architecture does permit viewers +to mix calls to _time and _position functions. + +The position_save saves a position that can be used later to seek back to this +exact same position, with event granularity. This implies that the +process_traceset must deliver events with the same timestamp in a deterministic +manner. + + +3. Implementation in tracecontext.c + + +- Type LttvTracesetContextPosition + +struct _LttvTracesetContextPosition { + LttEventPosition **tracefile_position; /* Position in each trace/tracefile */ + guint num_traces; /* Number of traces (for check) */ + guint num_tracefiles; /* Number of tracefiles (check) */ + GTree *pqueue; /* Copy of context pqueue */ +} + +with interfaces : + +lttv_traceset_context_position_save +(const LttvTracesetContext *context, + LttvTracesetContextPosition *pos); + + +Dependencies : + +- lttv_process_traceset_seek_position + - lttv_process_trace_seek_position + - ltt_tracefile_seek_position : already implemented + +lttv_process_traceset_seek_position will seek each trace to the right position. +Each trace will seek all of its tracesets to the right position. We keep +information about number of traces and tracefiles for extra integrity checking +when reloading the context. + +lttv_process_traceset_seek_position(LttvTracesetContext *self, + const LttvTracesetContextPosition *position); + + +- lttv_process_traceset_middle_position +We modify lttv_process_traceset_middle so that it takes as arguments : +(LttvTracesetContext *self, +const LttvTracesetContextPosition *end_position, +unsigned max_num_events) + +It's a simplification of the original function that will just read events until +the first criterion is fulfilled : the end_position is reached (we do not +deliver the event at the end_position) or the maximum number of events specified +is reached (we deliver the last event, corresponding to the maximum number of +events). The first event in the LttvTracesetContextPosition's pqueue will be +used as end_event. + +- lttv_process_traceset_seek_time : already implemented + +- lttv_process_traceset_middle_time +It's basically the same function as lttv_process_traceset_middle. We keep the +nb_events as a limit of events to read. We also keep the fact that, when the +maximum number of events is triggered, we also read the events that has the same +timestamp. This is useful for not losing events. The fact is that a viewer that +rely on time to select events it needs cannot have the granularity it needs to +select specific events from a bunch of events with the same time stamp. + + + -- 2.34.1