[Click] RFC: Annotations

[Bart Braem]

Hi Andrew,

Thanks for this long and very correct representation of the SyClick discussion.

I am very much interested in this problem, so I will give my view on the situation below. Let me tell you first why I believe this is necessary. The main motivation to me flexibility.
Anyone can write an own element and consider everything else a black box. Everything works out of the box. Except, when you use annotations. Then, all of a sudden you need to take care of possible conflicts. And that does not feel right.

So, on to the solutions you mentioned. I fully agree on the advantages and disadvantages you listed for all possible solutions.
The largest issue to tackle seems the tradeoff between speed (aka the current implementation) and flexibility (aka the SyClick implementation).

This last solution comes very close to the ideal balance, in my opinion:

On 26 Nov 2009, at 00:16, Andrew Brampton wrote:

> A annotation offset table:
> We use the 48byte area, however, we ensure that no more than 48 bytes
> of annotation may be configured in a single click configuration. Some
> code would parse all the Elements within the Click configuration and
> identify which annotations are being used. Then Click determines a
> different byte offset for each annotation to exclusively use within
> the 48 byte area. For example, say a destination IP address and paint
> annotation are being used. The first annotation (dest IP) would be
> assigned zero (the beginning of the 48 byte area), and paint would be
> assigned 4. Paint is assigned 4 because the first annotation takes 4
> bytes, and paint is to appear after it.
> 
> When a annotation is written to a Packet, the offset would be looked
> up in this table and written to the correct place. This system would
> ensure that annotations do not override each other. The system should
> also be fast because it is the same as existing just with one level of
> indirection. However, we are still limited to 48 bytes, and we don't
> easily support pointers to objects.

So we are still facing a flexibility problem. This time, in the buffer size.


I have discussed this over lunch with Kurt Smolderen, who was in the coding group at SyClick. We came up with the following idea. The key is to precompute everything at compile time.

The system generates annotation macros, based on a annotation_preferences file. This file is generated based on the elements, see later. Elements can use these get and set macros, the system will of course generate compilation errors if the annotations are not defined.

The annotation_preferences file defines preference of annotations: it specifies whether an annotation should preferably be stored in the small 48 byte buffer, or in a larger map that requires indirection. This way, standard annotations like paint or dst_ip_anno can have larger preference and can be used more quickly.

The generation of the structure to fit in the 48 bytes, takes into account the platform (for the size of the pointer to the larger map), the annotation preference and alignment. Some rather intelligent algorithms could be used to make sure the bytes are used wisely.
The larger map will just be a struct, with the annotations in it. This means for this map, only 1 indirection is needed. As we know in advance where each annotation will be in the struct, things will be very fast for lookups. No list traversal is required.
The generated macros will either refer to the 48 byte struct or the larger map struct, meaning they will be quick and easy to generate.

To generate the annotation_preferences file, a new macro is introduced: 
REQUIRES_ANNO(NAME, TYPE, PREF=255)
At least one element using the annotation, preferably the one setting it, should use this macro. Duplicate definition of the annotation can easily be detected (by the macro generation program), as well as missing definition (the compiler will define the expected macros to be undefined).
Extracting the macros will happen by a scan over all or a limited set of elements, see later.
The macros resulting from this REQUIRES_ANNO macro are:
TYPE ANNO_NAME_GET();
void ANNO_NAME_SET(TYPE);
We think that with type information there, it should not be hard to generate a struct or a map. sizeof is our friend :-)

It is important to decide which elements to consider. Because, as you might notice, the standard way would be to generate annotations for all elements. In regular testing environments this is not really a problem, but it is not optimal.
So we propose to only consider the elements from packages that are being used, this will already reduce the annotation map size. However, for setups that require maximal performance this is not enough. That is why we suggest to modify click_mkmindriver to be able to output elements required in the script. This output could be used to extract used REQUIRES_ANNO macros. So we can generate a minimal annotation_preferences file, resulting in the perfect balance.

It is not always smart to allocate an entire map struct when allocating a packet. That is why a user should be able to specify something like --enable-late_annotation_allocation
Then, the map struct is not allocated upon packet construction. The ANNO_NAME_GET macro will now contain an extra check on the map pointer being valid. The ANNO_NAME_SET macro will contain map allocation logic.

A rather tricky difficulty is the type being passed to the REQUIRES_ANNO macro: what if this is a pointer or a char[].
We propose to scan for either * or [] in the macro arguments and be smart:
- if you see a pointer, add new Pointer to the packet constructor and delete Pointer to the packet destructor (yes this implies we claim pointer ownership)
- if you see char[], generate an error, it is not possible to allocate this
- if you see char[i], generate malloc and free code to handle this case 

This is the result of 1 hour of brainstorming at lunch, so this could well contain some logical errors. You comments are of course welcome.

best regards,
Bart and Kurt
-- 
Bart Braem
PATS research group - IBBT
Dept. of Mathematics and Computer Sciences
University of Antwerp
Campus Middelheim, G3.27
Middelheimlaan 1
B-2020 Antwerpen, Belgium
Phone: +32 (0)3 265.38.82
Fax: +32 (0)3 265.37.77
Web: www.pats.ua.ac.be