lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  linux-cve-announce  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date:	Wed, 20 Oct 2010 14:50:09 -0400
From:	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To:	"Frank Ch. Eigler" <fche@...hat.com>
Cc:	linux-kernel@...r.kernel.org, systemtap@...rces.redhat.com,
	ltt-dev@...ts.casi.polymtl.ca,
	Steven Rostedt <rostedt@...dmis.org>, mingo@...e.hu,
	Peter Zijlstra <peterz@...radead.org>,
	Frederic Weisbecker <fweisbec@...il.com>,
	Elena Zannoni <elena.zannoni@...cle.com>,
	Arnaldo Carvalho de Melo <acme@...radead.org>,
	Thomas Gleixner <tglx@...utronix.de>,
	Aaron Spear <aaron_spear@...tor.com>,
	Tasneem Brutch - SISA <t.brutch@...a.samsung.com>,
	Tim Bird <tim.bird@...sony.com>, dominique.toupin@...csson.com,
	Andi Kleen <andi@...stfloor.org>,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>,
	Philippe Maisonneuve <Philippe.Maisonneuve@...driver.com>,
	Felix Burton <Felix.Burton@...driver.com>,
	Andrew McDermott <Andrew.McDermott@...driver.com>,
	Stefan Hajnoczi <stefanha@...il.com>
Subject: Re: [RFC] Common Trace Format Proposal for Linux (v1)

* Frank Ch. Eigler (fche@...hat.com) wrote:
> 
> Hi -
> 
> mathieu wrote:
> 
> > [...]
> > Metadata attribute representation:
> >   align = value;                                /* value in bits */
> > [...]
> >   byte_order = native OR network OR be OR le;	/* network and be are aliases */
> > [...]
> 
> Is there some reason to invent a new textual syntax for describing
> how to pack structs?  There is DWARF, ASN.1, C, ....

Hi Frank,

I discussed with the TIWG this morning, and in a nutshell, these standard seems
to be to some degree incompatible with our requirements. In more detail:

DWARF:

- Represents a language such as C. We want to represent trace events, not C
  structures.
- To examplify, the way bitfields are encoded by gcc is sub-optimal for our
  trace format (see the proposal document for explanation).
- Another example is the difficulty to represent dynamically sized strings and
  sequences contained *within* a structure in DWARF.
- We want to keep meta-data along with the trace, which means that we want to
  keep the size of this information relatively low.
- We fear that DWARF is too complex for our needs.
- We want to generate the meta-data from TRACE_EVENT() macros. We'd like to keep
  a 1-1 mapping between the types as described by programmers and the meta-data,
  which argues against the DWARF binary format.
- We would like to keep the meta-data in text format for human readability
  reasons, which is not possible with DWARF.

ASN.1:

I must admit I am still reading through the various encoding rules (BER, CER,
DER, PER, XER, ....). So far, some ideas are interesting, but I don't think it
applies directly to what we're trying to achieve.

For the following discussion, I'm referring to:

Standards describing the ASN.1 notation:

ISO/IEC 8824-4
http://www.itu.int/ITU-T/studygroups/com17/languages/X.683-0207.pdf

Standards describing the ASN.1 encoding rules:

ISO/IEC 8825-1 (BER, CER and DER)
http://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf
ISO/IEC 8825-2 (PER)
http://www.itu.int/ITU-T/studygroups/com17/languages/X.691-0207.pdf
ISO/IEC 8825-4 (XER)
http://www.itu.int/ITU-T/studygroups/com17/languages/X.693-0112.pdf
ISO/IEC 8825-5 (XSD mapping)
http://www.itu.int/ITU-T/studygroups/com17/languages/X694.pdf
(GSER)
http://tools.ietf.org/html/rfc3641

For instance, the BER encoding (Basic encoding rules), CER (Canonical encoding
rules) and DER (Distinguished encoding rules), XER (XML encoding rules) and GSER
are rejected because they encode the identifier with the data. They also encode
the length as prefix to each content, which is wasteful. We need to split the
metadata from the actual data to stay compact.


PER (Packed encoding rules) has some interesting concepts, which might (or not)
be interesting for us:
- "choices", basically unions with a preceding selector. Seems overkill.
- optional fields, which require one bit in the trace to specify if field is
  present or not. Seems overkill, consumes space, especially with non-packed
alignment.

For performance reasons, we want to allow the tracer to write into the trace
with either packed or naturally aligned writes (the choice depends on the
architecture's ability to do unaligned writes efficiently). Therefore, some
choices done in PER that are specifically tuned for the packed representation
don't make sense on architectures where we have to use naturally aligned writes.
Their "ALIGNED" vs "UNALIGNED" distiction does not align on the natural type
size, but rather on the byte size.

Another issue is the bitfield description for PER. A "range" (e.g. 65 to 128)
must be specified to map to a bitfield size. The natural way for a programmer to
express a bitfield size is to specify the number of bits directly, not a range.

That being said, PER is probably the closest to our binary representation so
far, except for the fact that it does not take "natural alignment" into account.

XSD mapping is rejected because I don't think we'll generate XML from the
TRACE_EVENT() macro.


In general:

We also have to represent our event categorization (not just structures) in this
metadata, for which neither ASN.1 nor DWARF looks like a good fit. Also, we are
trying to come up with a simple representation of what we need, which ends up
being a small subset of DWARF and ASN.1. So far, our understanding is that
aiming for compatibility with these standards would bring much more restriction
and fail to meet our requirements, for very little gain.

It's very good to have a look at these through, because encodings like PER have
very interesting ways to tackle the problem.

Thanks for your input, please feel free to tell me if I missed important
elements.

Mathieu

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists