[lttng-dev] Integration of the state history system in LTTv

[alexandre.montplaisir@polymtl.ca (Alexandre Montplaisir)]

Hi Daniel,

It's nice to see there is interest ;)


On 12-01-27 10:01 AM, Thibault, Daniel wrote:
>> * libState (or something like that)
>>
>> The libState library can be used to represent the current state of a
>> system in the form of an attribute tree. An attribute is a mapping
>> between a key (a string) and a value (generally a string, an integer
>> or a null value). The attribute tree is analoguous to the structure of
>> a filesystem, since an attribute can contain children attributes in
>> addition to its own value. When the path of an attribute is specified,
>> it can be either absolute or relative to another attribute.
>>
>> The possible operations on the attribute tree are:
>> - Add a new attribute, specifying its value.
>> - Change the value of an existing attribute.
>> - Delete an attribute and all its descendants.
>> - Get the parent attribute of an attribute.
>> - Get the children attributes of an attribute, or their number.
>> - Get the total number of attributes in the tree.
>>
>> libState is independent from LTTv, is not domain-specific, and could
>> be packaged separately.
>    I suspect provision must be made for attributes that are arrays.  For instance, any of the attributes of processors in a multi-processor system.  Or is it expected to handle this by introducing a layer of index attributes?  (e.g. /processor/0/attribute, processor/1/attribute, etc.)

Every attribute in the model has a unique integer identifier, which we
call a "quark" (in reference to Glib's quarks for interned strings). So
it could be possible to build an "index" (similar to a database index)
of specific attributes by simply remembering their quarks within the
application.

For example you could ask for the quarks matching a pattern, like:
/processor/*/status

and it would return you the quarks for the /status attribute of each
processor in the trace. If you use those quarks for queries afterwards,
performance will be better (since you don't have to re-hash the same
strings over and over).


>
>> * libInterval (or something like that)
>>
>> The libInterval library can be used to represent and save an interval
>> tree in memory or on disk. Each interval is characterized by begin and
>> end timestamps, a value and a key.
>>
>> The possible operations on the interval tree are:
>> - Add an interval, specifying its key, value and begin/end timestamp.
>> - Lookup intervals that intersect a punctual time value.
>> - Lookup an interval that intersects a punctual time value and that
>> matches a given key.
>>
>> Due to the nature of the storage of the interval tree on disk,
>> deletion of intervals probably won't be possible.
>>
>> Like libState, libInterface is indenpendent from LTTv, is not
>> domain-specific, and could be packaged separately.
>    A distinction may need to be made between inclusive and exclusive bounds: e.g. the intervals [t1..t2], [t1..t2[, ]t1..t2] and ]t1..t2[ are all different from each other.

Indeed, this is not very hard to do, but it's very important to be clear
about it.

One thing that makes it easier is that timestamps are not continuous,
they are discrete. In LTTng traces, the smallest unit is a nanosecond.
We could also go down to the TSC counter, but even that wouldn't be
continuous. Between two nanoseconds, nothing happens in the trace. So
the two intervals:

[10, 20]
]11, 21[

are equivalent here. In my implementation, all the intervals are
inclusive, like [t1, t2]

If there is a state change at time t, the new state is valid right away.
So if we have changes at t1 and t2, the first state will be valid during
[t1, t2-1] and the second one will be valid from [t2, ...  onwards


Also, since all state intervals are juxtaposed to each other, it's
possible to "jump" from one state to another by taking the current
interval's end time "t_end" and doing a query at "t_end + 1" to get the
next interval.


Cheers,

-- 
Alexandre Montplaisir
DORSAL lab,
?cole Polytechnique de Montr?al