DAILY NOTEBOOK ---------- 09-20-2005 ---------- --- 11:30PM - 12:30AM (1 hour) * Got simple "hello world" module building, loading, and unloading. * Began looking into reading/writing from/to /proc. * Use su - root before loading the module (the - sets the PATH so root can see /sbin/{modinfo,insmod,rmmod,etc}. * Use tail --lines=10 /var/log/messages to view the printk() output (this is fairly obvious). * BTW, a simpler version of the above command is tail -10 /var/log/messages --gp * The *.h files are in /usr/src/linux-2.6.*/include/linux/. ---------- 09-22-2005 ---------- --- 07:15PM - 10:45PM (3.5 hours) * Created the aLayer directory inside /proc. * Created a read and write file (packetCountMode) within that directory. * Use simple_strtol() and simple_strtoul() instead of (user space) atoi(), etc. * Plan * Add read-only packetCount file in /proc/aLayer. * Clean up implementation a bit. * Start working with nethooks (to actually count the packets). --- 12:00AM - 1:30 AM (1.5 hours) * Set up all /proc files. * Cleaned up implemention. ---------- 09-23-2005 ---------- --- 10:30AM - 12:00PM (1.5 hours) * Generalized packet count mode. * Did more code cleanup. * Cleaned up / reformatted this page. * The function used for proc_dir_entry.proc_read should return the number of bytes output. An infinite loop will result if this value does not eventually reach 0 (as the reader will just keep reading). If the file's value can be output in one shot (ie the output will fit in the provided buffer), then the function should return 0 when the offset is greater than 0 (indicating a second read). * The function used for proc_dir_entry.proc_write should return the number of bytes input. This function will be called until the sum of the return values of each call equals the number of bytes written to the file. Of course, if this condition is never met, an infinite loop will result. * Plan * Nethooks --- 2:00PM - 3:30PM (1.5 hours) * Completed the packetCount module. Packet counting can be turned on and off through /proc/aLayer/packetCountMode. The number of incoming (PRE_ROUTE) and outgoing (POST_ROUTE) packets can be viewed through /proc/aLayer/inPacketCount and /proc/aLayer/outPacketCount, respectively. * Testing * The packet counts increment and the incoming and outgoing packet counts are different. * In the normal case, each count increases by 1-4 packets per second. * The counts increase much more rapidly with explicitlly generated traffic (pings or X SSH tunelling, for example). * Plan * Ethereal? --- 9:00PM - 12:30AM (3.5 hours) * Built basic Ethereal plugin (framework for an alayer dissector). * Set up makefile and became familiar with build process. * Build Process * Get the Ethereal source. * Create a new directory in the plugin directory. * Write the plugin and Makefile (use Developer's Guide as reference). * As described in the Ethereal documentation, run ./autogen.sh, ./configure (satisfying build dependencies (automake, libgtk2.0, libglib2.0, libpcap, and libtool) as necessary), make, and make install (if installing the entire package from source). * Just the plugin can be built (or rebuilt) by cd'ing into the plugin directory and running make. * Copy the .so and .la files from the .libs directory in the plugin's directory to the Ethereal plugin directory (/usr/local/lib/ethereal/plugins/XX.XX/ if built and installed from source (likely in /usr/lib/ethereal/... otherwise)). * Consider spinning off .h files for the Ethereal plugin and the module. * Start using static variables more regularly (as a sort of crude access protection). * Better conform to capitalization conventions * /proc file names don't have capitals * Ethereal packet file names don't have capitals * Ethereal function names generally use underscores. * Is it really good practice to use "void" in an emtpy parameter list? * Plan * Review specific information on the alayer packet format (by re-reading the hotnets paper, reading info on the wiki, etc). * Continue implementing (fleshing out) the Ethereal plugin. ---------- 09-24-2005 ---------- --- 12:00PM - 3:00PM (3 hours) * Read more details on the alayer and Ethereal plugin implementation. * Considered implementation approaches and complexities. * Adding alayer detection to Ethereal requires that we construct a new dissector (which can be contained in a plugin). A capture filter is not adequate, as it can only filter based on known protocols, and alayer represents a new protocol. * I'm starting to think it may be (very) difficult to implement an alayer dissector in Ethereal and that it would be easier to take an alternative approach * The API documentation is poor. There are guides available for constructing basic dissectors, but little help is provided for more advanced dissectors. * We are doing something unusual, which doesn't appear to map well onto the model used by most Ethereal dissectors and the API. * Unless there is a specific requirement, or strong desire, that we use Ethereal, I would prefer to take an alternative approach. Specifically, I know that I can, starting immediately, write a module based on nethooks that will detect and report on alayer packets. In addition to using something (nethooks) with which I am already familiar, the conceptual model for this approach is much more straightforward. * Resolution: Write a solution based on libpcap. ---------- 09-27-2005 ---------- --- 2:00PM - 3:00PM (1 hour) * Implementation meeting with George and Rodrigo. * Discussed overall design. ---------- 09-29-2005 ---------- --- 3:00PM - 7:00PM (4 hours) * Worked through some details and questions about the alayer design. * Began overall design for the aEngine. * Designed the static annotator subset of the aEngine functionality. --- Design and Questions * HIGH LEVEL / INTERFACE SUMMARY * send_annotated(socket, buffer, annotation) will be best effort (the annotation will not send if the destination address is not in the discovery cache) and can only be applied to UDP messages. * Should discovery for the destination address begin automatically on a failed call to this function, or should we force the application to explicitlly request the discovery of the destination before making the call to send_annotated(...)? I prefer the latter. * Blocking and non-blocking versions of this call should be possible. We can signal to the application whether the destination address was aware, unaware, or needed to be discovered. * Perhaps it would be useful to provide a version that will not send the message at all if it cannot be annotated? * annotation_handler send_annotation(socket, annotation, ANN_ONCE|ANN_ALL) will annotate when possible and may be applied to UDP messages or TCP streams. * A packet on this socket may fail to be annotated if the destination is not in the discovery cache or if there is not sufficient room in the packet. * Should discovery begin automatically if the destination is not in the discovery cache. I would say it should. * Longest prefix matching will be similar to per-socket annoation; It will annotate when possible and may be applied to UDP and TCP. * What will the interface for setting up / cancelling prefix matching annotations look like? I currently require the prefix (as a bit mask encoded in an unsigned int), the precision of the prefix (the count of the significant bits to look at), the annotation, and the length of the annotation. Do we also want to allow prefix annotations to be ANN_ONCE or ANN_ALL? I would say we should give that option. * I think, like the per-socket annotation, discovery should begin automatically if necessary. * Again, like per-socket annotation, it should be possible to cancel a prefix annotation. * Peeking * The interface for setting up deannotation is well defined. * Should we (perhaps later) provide a way for applications to peek at annotations, without removing them from the packet? * ORDER OF ACTIONS * There was a discussion about whether the discovery cache should be checked first or it should be determined if the packet has outgoing annotations. * I would say the discovery cache should be checked first, especially if it can be made fast. If the destination doesn't support annotations, then we need to strip any existing annotations and may skip the check to see if the packet should be annotated. If the destination does support annotations, then we will go through the normal annotation procedure. If the cache does not contain the destination, then we will send the packet without annotations and begin the discovery process (only in the case that this is not a per-packet annotation). * DATA STRUCTURES * What are the best (fastest / lowest memory / easiest to implement) structures to use for the prefix and socket tables and the discovery cache? * For now I plan just to use a dynamically resizeable array and linear search for prefixes, as this is a fairly easy approach to implement. * In the future, perhaps I could order the prefixes by precision or put them all in one big binary tree. * I could do something similar for the socket table (although this might change once some of the questions below are answered). * I could do something similar for the discovery cache as well. Alternatively, I might make a 256-ary dynamic tree of booleans (indicating if the destination address is annotation aware). * COMBINING CASES * I am considering combining the prefix and per-socket annotations (the per-socket annotations would just become a special case). Here are some advantages: * Assuming the per-packet annotations are best effort, there would only be one data structure to maintain, and only one piece of code to maintain that structure and annotate packets. * Any optimizations made to the data structure would improve performance for both types of annotations. * It would be possible to specify annotations for packets going to a certain port in an address range. It would also be possible to specify annotations for packets leaving from a particular local socket, but going to an address or address range, and, optionally, to a particular port. In short, this approach would be more general. * PER-SOCKET * I'm assuming that the socket argument to annotation_handler send_annotation(socket, annotation, ANN_ONCE|ANN_ALL) will be a file descriptor. But I can't find a way to map from the struct sock (included in the struct sk_buff passed into a netfilter hook) to a file descriptor (in order to see if the packet represented by that sk_buff is associated with a socket that has annotations on it). * When the call to send_annotation(...) is first made, I can use getsockname(...) and getpeername(...) to get the source and destination address and port. I can then check each packet that passes through against these variables. If the packet matches, then we can assume it is associated with that socket, and should therefore be annotated. * Is there a better way to do this? * If the prefix and per-socket cases are combined, then it will be necessary to identify sockets by their source and desintation address and port. * VARIOUS QUESTIONS * What if there is room in a packet for some, but not all, of the annotations supposed to go out with that packet? Maybe we could give annotations priorities. Adding explicit priorities will only complicate things, so for now, maybe we could define an implicit ordering; Those annotations registered earlier have higher priority than those registered later. Further, the more specific the annotation, the higher priority it has (so per-packet annotations will be considered first, then per-socket, then prefix). This should be fairly easy to implement. * Will it be necessary to lock the core data? It looks like it will be. * Are we going to (eventually) allow numbers to be encoded, instead of requiring that they be written out as strings? This would be nice. * What role does fragmentation play? Should I be concerned about this now? * ROUTING * I am programming the module to work both at end hosts and in routers. Am I correct in my understanding that this may be used in both capacities? * Are we going to simulate routing at some point? If so, how will we do it? Perhaps we could use Click? * There are a number of other issues routing and discovery related issues that I am unclear on. I would like to discuss these. * IMPLEMENTATION REMINDERS * All of the annotation bytes, including the signalling bits, should be in network byte order. As I understand it, the annotations are just strings, so there is no ordering issue. If, however, we eventually allow multi-byte numeric fields in the annotations, they will need to be network byte ordered. * To generate the signalling bits * Take the short (16-bit) one's complement sum of the IP header, with the checksum and ttl fields set to 0 (or considered to equal 0), and the length field updated to include the annotations, associated structures, and signalling bits. * Take the one's complement of the result. This hasn't been explicitlly stated as a requirement, but I've been doing it to keep in line with the IP header checksum. * Encode the result in network byte order. * Control packets will need a reserved annotation type. It will be necessary to check all user created annotations to make sure their type does not conflict with one of the reserved types. * Can perform sanity checks at each stage of annotation deconstruction: The signalling bits, the TCP/UDP length and checksum will be incorrect, the annotation lengths need to be within the bounds of the packet, etc. * Annotation considerations - Are there annotations already, what annotations need to be removed, what annotations need to be added, is the destination annotation aware, is there sufficient room in the packet. * Need to limit the size of the discovery cache. Need to use a replacement policy that kicks out less-used addresses. * Need to remove ANN_ONCE annotations once they have been sent out. * Need to aggregate annotations for the same prefix. * Need to make an annotation pool struct. This is what should be passed into the interfaces calls to the module. It might be nice to write some user space library functions to help fill in these structs. These libraries might have other helper functions. * Need a general packet annotation / strip / peek (maybe) infrastructure. ---------- 10-01-2005 ---------- --- 12:30PM - 2:30PM (2 hours) --- 5:00PM - 7:00PM (2 hours) --- 7:30PM - 8:30PM (1 hour) --- 11:00PM - 4:00AM (5 hours) * Implemented and tested a first draft of the module and pcap annotation detector. * The module currently supports static annotations as a special case of the prefix based annotations. * Worked through a number of nasty bugs (I had forgotten some of the joys of C). * Plan * Clean up my notes and formalize questions for George and Rodrigo. * Work on design of remaining portions of module and consider their interaction with existing code. * Clean up and test existing code in module and annotation detector. * Continue implementing module and detector. ---------- 10-02-2005 ---------- --- 3:00PM - 8:00PM (5 hours) * Formalized my design notes and questions (found under "Design and Questions" from 09-29). * Plan * Clean up, review, and test existing module and detector code. * Set up debug and error infrastructure. * Write module annotation detector and stripper. * Write a user land traffic generator. * I am going to hold off on writing full annotation generator and detector (complete with annotation index, etc), until it is decided if the prefix and per-socket cases can be combined. ---------- 10-04-2005 ---------- --- 2:00PM - 4:00PM (2 hours) * Implementation meeting with George. * George recommended looking at the Click source and getting a copy of "Design And Implementation of the 4.4BSD Kernel". * George specified a goal for this week (to be completed by mid-Saturday and presented at the Monday meeting): netrads1 sends a stream of data to netrads4, which is annotated by netrads2 and deannotated by netrads3. * We covered routing through linux and set up a virtual network between a few of the blades. * George answered a bunch of questions. * Discovery, packet size limitations and fragmentation, and the user level interface are not primary concerns for now. * The module will eventually have to support a number of application defined actions during deannotation (ie in response to a packet with a certain annotation type). This will include passing the packet to the application and waiting for a decision on what to do. * These applications may reside in other kernel modules (to improve performance). * I decided against using the combined per-socket and prefix lookup table. * Benefit isn't great enough. * Implementation would be difficult and would slow incremental progress (including the goals for next week, for example). * Having each annotation type associated with it's own table is parallel and conducive to expansion. ---------- 10-05-2005 ---------- --- 12:00AM - 4:00AM (4 hours) * Spent 4 excrutiating hours working through a bug. It's finally fixed and I'm ready to move on with adding the PRE-hook. * Mozilla also crashed and I lost a lot of planning and notes. I have since recreated them below. * Lessons * Do a lot more testing (I knew this one, I just need to remind myself). * Try to make the smallest incremental changes possible between tests. * Save this notebook often ---------- 10-06-2005 ---------- --- 1:00PM - 5:00PM (4 hours) * Updated notebook with recent work, notes from implementation meeting, and future plan. * Cleaned up code, tested everything, added a debug and error infrastructure. * Generalized some data structures (in preperation for implementing the general annotation index). Reformatted and tested the code in response. * Added a PRE hook, for deannotating. * Plan 1. Get the PRE hook detecting annotated packets and stripping and printing annotations. 2. Add support for the annotation index - PRE and POST hooks will have to strip and add annotations (respectively), update index and signalling bits, etc. 3. Generalize prefix annotation to scan through entire table of annotations. 4. Set up structures for stripping annotations based on type. 5. Write helper functions for data structures. For now, just support dynamic resize (half and double), clear, and add. Can add support for remove, etc later. 6. Create the /proc interface to the prefix table and annotation strip table. ---------- 10-09-2005 ---------- --- 3:30PM - 5:30PM (2 hours) --- 9:00PM - 12:00AM (3 hours) * Implemented an annotation stripper. * Wrote a user space traffic generator. * Added print and test "infrastructure" (a bit too strong of a term) to the module. * Worked on design of general annotation and indexing code. * Use sk_buff->len, instead of sk_buff->data_len, as the IP payload length. * ipHeader->tot_len should be in network byte order, while ipHeader->check should not (I don't know why). * It's not good to make syscalls from the kernel. Find out from George how to translate a socket descriptor into its associated source and destination address and port. ---------- 10-10-2005 ---------- --- 10:30AM -12:30PM (2 hours) --- 7:00PM - 10:00PM (3 hours) --- 11:30PM - 1:30AM (2 hours) * Implemented code to add a single annotation to a running list of annotations (updating the index, etc), to write such a list to a packet (updating the IP header, etc), and to strip all annotations from a packet, optionally copying them to buffers. This is all part of an effort to add full support for the general annotation index. * Notes from source 
  1. Need to detect if the outgoing packet is already annotated
  2. We will have an annotation buffer of size MTU - link layer header length
     - IP header length - legitimate data length
     This should be split into three parts - The constants size portion at
       the end (signature, length, # of annotations), the index, and
       the annotations.
     We can keep adding annotations as long as the sum of the lengths
       of these three sections is less than the remaining room in the packet.
  3. If the packet came with annotations, these should be copied into
     the annotation buffer, and the index copied to the index buffer, and
     the length and count fields set.
  4. The variable length buffers can grow forward or backward.
  5. When all of the annotations are inserted, or the packet is full,
     the buffers need to be copied together into the tailroom of the packet.
     It may be necessary to allocate a new packet, with the correct
       amount of tailroom.
       Need to free the old skbuff
  It might be valuable to have a stripAnnotation function that just looks
     at the length field and kills all annotations, returning the text.
     This could be used for totally stripping and for clearing the annotations
       that will be written back later (after others are added).
  Similarly, it might be good to have a write annotation function that does
     the following stuff.
  6. The length and checksum need to be updated. Then the signature bits
     need to be generated.

  Write functions that will add annotations and update all of the info.

  For deanotation, will look through each annotation on packet and see if it
  should be stripped. If so, then it will be pushed somewhere. If not, then it
  will be copied to a new annotation buffer (the outgoing buffer). Should
  be able
  to use the same functions as used by annotation.

It would be nice to have a way to just remove all annotations quickly.
It is also necessary to be able to strip and copy all of the data to separate
buffers (annotations, index, and static (# annotations and total length)).
This would be used when annotating an already annotated packet.
---------- 10-11-2005 ---------- --- 11:30AM - 3:30PM (4 hours) * Cleaned up and reviewed the new code, added error handling, inserted debug printouts. * Began testing the new code. --- 4:30PM - 6:00 (1.5 hours) * Bug: Using a struct with two char arrays, each of length 1500 bytes, was crashing the kernel. For now the lengths have been lowered to 1000 bytes each (which mysteriously does not crash the kernel). It may be necessary to look for an alternative solution at some point (malloc'ing and free'ing the arrays, for example). --- 6:00PM - 8:00PM (2 hours) --- 9:00PM - 11:00PM (2 hours) * Bug: Was calling skb_push, which inserts data at the front of the data section. Changed call to skb_put. * Bug: Was forgetting to update the IP header length field before generating the signature bits. * All new code is now uncommented. Annotations are appended by the sending host and stripped by the receiving host. ---------- 10-12-2005 ---------- --- 11:00PM - 1:30AM (2 hours) --- 2:30AM - 3:30AM (1 hours) * Fixed bugs and further tested existing code. * Began adding code in support of annotation stripping by type. * Bug: Was using a 2 byte "short" annotation type (spec indicates the short annotation type should be 1 byte wide), but only writing one of those bytes to the packet. Discovered through code review. * Bug: Was not correctly marking the first bit of long types and offsets (weirdness with byte ordering). Discovered through code review. * Bug: Was adding new annotations and index fields to back of temp buffers, but copying to packet from the front of those buffers. ---------- 10-13-2005 ---------- --- 8:00PM - 10:00PM (2 hours) * Began working on support for a variable sized prefix annotation table and variable length annotation pools (within a given "add" annotation), with the goal of getting multiple annotations per packet. ---------- 10-19-2005 ---------- --- 10:30AM - 1:00PM (2.5 hours) --- 9:30PM - 11:30PM (2 hours) --- 12:30AM - 2:00AM (1.5 hours) * Finished support for variable length annotation pools. * Wrote accessor and mutator functions for all struct's and the prefix table. * Added dynamic array resize. ---------- 10-20-2005 ---------- --- 12:00PM - 2:00PM (2 hours) * Apparently the kernel doesn't support floating point operations. * All prefixes and all members of prefix pools are now considered. --- 2:00PM - 2:30PM (0.5 hours) * Implementation meeting with George. * Work toward some basic set of functionality in the module that will allow people to begin building applications using annotations (I intend to finish the prefix annotation portion of the module). * Then write a monitoring and statistics gathering application using annotations. The code for this will likely reside in another kernel module. * Also write a skeleton application module that can be used by others as a starting point for writing their own applications. * I intend to be more regular and explicit about code commits and "releases"; I will try to commit a couple of times a week and email George and Rodrigo a list of the high level changes that have been made. This list will help them take advantage of the new functionality and will allow them to summarize the progress that is being made to others. --- 5:30PM - 8:00PM (2.5 hours) --- 9:00PM - 10:30PM (1.5 hour) * Bug: Wasn't correctly updating the capacity variable of dynamically resized pointer arrays. * Bug: Something about long/reallocated packets is causing the receiver to crash. ---------- 10-21-2005 ---------- --- 10:00AM - 1:00PM (3 hours) --- 9:00PM - 12:00AM (3 hours) * Bug: Found the problem with the long packets: Copying the wrong number of bytes when looking at a long annotation offset (was looking at LONG_ANNOTATION_TYPE_LENGTH (4 bytes) instead of LONG_ANNOTATION_OFFSET_LENGTH (2 bytes)). * Added support for detecting and stripping annotations by type. * Bug: Was forgetting to actually set the type of a new typeDeannotation on creation. * Bug: Was stripping the packet of all annotations twice (the second one always led to an oops). * Bug: Was forgetting to initialize a struct (luckily caught before a crash though). See new policy below in response. * Bug: Using GFP_USER as the kmalloc flag was causing a warning and stack trace to be printed to the kernel log. Replacing all instances of GFP_USER with GFP_ATOMIC fixed the problem (although I don't know about the correctness of using GFP_ATOMIC). * Plan * Need to write the helpful infrastructure functionality I've recently come up with: Better debug printouts, a clear policy on initialization and dynamic memory management, etc. * Need to commit to CVS and make a report of new functionality. * Need to flesh out some portions of the code and figure out what functionality remains to be implemented (before prefix annotations are complete, for example). ---------- 10-22-2005 ---------- --- 12:30PM - 4:30PM (4 hours) * A bunch of misc cleanup, code review, and future code design. * Moved dynamic memory allocation policy to the new "Policies and Notes" section. * I modified all existing code so that it conforms to the policy. * More on kmalloc flags: Using GFP_ATOMIC is fine (and required, according to the warning I was seeing in the kernel log) as long as I keep the allocation amount small (a couple of pages or less). * I set up a better debug/error print infrastructure. ---------- 10-23-2005 ---------- --- 3:00PM - 6:30PM (3.5 hours) * Spent quite a bit of time expanding the print infrastructure, primarily in response to bugs. Although it eventually worked (and was pretty cool), it had become cumbersome and innefficient. I therefore removed it and went with a simple version that has the same functionality but requires a bit more programmer input. * I want to start moving toward a "release" (a cvs commit and an update with George and Rodrigo): I need to figure out what functionality remains and implement it, clean up code and notes, do more testing, etc. --- 6:30PM - 9:00PM (2.5 hours) * Cleaned up code, dealt with various small issues, and worked on design of remaining features. ---------- 10-25-2005 ---------- --- 10:30PM - 1:30AM (3 hours) * Cleaned up code and added bits of functionality (peeking at annotations, removing ANN_ONCE annotations once they have been sent out, etc). * Compiled and began testing. * Notes from source 
When we are adding annotations, it make sense to go through and do them
one annotation type
at a time (prefix, etc). When we are peeking and stripping, though, it makes
sense to only
look at each annotation in the packet once, and check all of the different
deannotation
types to see if it should be peeked or stripped. There is some issue there
of which should
be the inner loop (going through the packet or going through the deannotation
tables). For
now I'm going to look at each annotation in the packet and see if it should
be peeked
or stripped.

/* Thoughts: I'm still a little concerned about priority. Actually, I think
   there are a lot of options. The order in which the types are considered
   is pretty
   easy to change (that will happen in this function). The elements in
   each type
   table might then be ordered by priority, or could be accessed through
   a pointer
   array ordered by priority, or through a function that does the
   ordering/accessing */

/* Should we support multiple callbacks on type deannotations? If so, how do we
   support it: We could make a callback pool (in which case we need to search
   for the
   appropriate pool before adding a new typeDeannotation), or we could just add
   a new typeDeannotation (in which case we need to modify the following */

/* Need to search for an appropriate existing addAnnotation (and add to its
   pool, if it exists) before adding a new addAnnotation */
---------- 10-27-2005 ---------- --- 8:00PM - 10:00PM (2 hours) * Bug: Was not incrementing the add prefix index variable when the prefix (of the outgoing destination address) did not match the required prefix to annotate. This was causing an infinite loop (and an associated machine lock up). * Bug: I transitioned from char arrays to dynamically allocated char blocks, but forgot, in a number of places, to stop using sizeof() and start using the new capacity variables associated with the char blocks. This was causing annotations not to be added (because sizeof(pointer) is 4, not the length of the char block). * Cleaned up notes. --- 10:30PM - 12:30AM (2 hours) * More code cleanup. * Implemented small remaining pieces of functionality. * The way I currently deal with marking index fields as long or short works, but is not overly explicit, and may be prone to compiler/processor quarks. I'm going to redo this. * I would also like to write some index / annotation header manipulation functions. These should be reusable and help to shorten some functions. ---------- 10-28-2005 ---------- --- 12:00PM - 1:00PM (1 hour) * Implementation meeting with George. * George showed me how to set up the vlan (which will be helpful for testing). * He indicated I should move toward doing some performance testing (using iperf). --- 12:00AM - 2:30AM (2.5 hours) * Upcoming functionality: Callbacks and API(s) (through exportation of kernel symbols and/or through /proc). * Performed latency and throughput measurements in simple configuration. Results were encouraging, but module crashes when iperf is run for a second time. Update: The problem doesn't manifest itself when the mss is 1000 (ie the problem is presumably related to larger, nearly-full packets). --- 2:30AM - 4:00AM (1.5 hours) * Adding in error handling code for function return values. * Functions that may return error return values * kmalloc (NULL) * skb_copy_expand (NULL) * nf_register_hook (< 0) * See aengine.h for functions I wrote that may return errors. * Functons we don't need to worry about * memcpy * kfree (has void return type) * skb_put will panic if there is a problem. * skb_tailroom * kfree_skb (has void return type) * skb_trim * nf_unregister_hook (has void return type) * in_aton * Thought about sanity checking scheme * Moved to the new "Policies and Notes" section. ---------- 10-29-2005 ---------- --- 3:00PM - 4:00PM (1 hour) * Possible functionality split-offs * addSingleAnnotationToPacketSet: Prepare a type or offset (separate functions) for insertion into the index of an annotated packet. * peekAndStripDeannotations, and possibly others: Given a set of bytes, determine if the bytes represent a short or long type or offset (separate functions) and return the decoded type or offset. * I can redo the way I encode/decode types/offsets when I break off the above functions. * stripAllAnnotations, and possibly others: Grab fields from the annotation header. It would be good to have a function to deal with each header field. * Moved the task summary to the new "Policies and Notes" section. --- 4:30PM - 7:30PM (3 hours) * Added more return value handling code. * Worked through some of the complexities of propagating errors upward. * Bug: Found a case where a singleAnnotation was being created (allocated) but not destroyed (freed). ---------- 10-30-2005 ---------- --- 11:00PM - 2:00AM (3 hours) * Added two new items to the dynamic memory allocation policy (about zero'ing new structs and checking member pointers against NULL in destroy functions). * Cool memory leak detector idea: There are very specific points where new memory is allocated and freed in the module. At each point where some new memory is allocated, add the returned pointer to a void pointer array. When memory is freed, search through the pointer array and remove that pointer (maybe set it to 0). At the very end (when the module is being cleaned up) search through the memory pointer array. If there are any non NULL (non 0) pointer, then we have a memory leak. Debug statements and other higher-level mechanisms can be used to determine where the leak is taking place. * How do we deal with zero length annotations? They should be legal (in the case that we just want to send the type). * Moved sanity checking policy from here to new "Policy and Notes" section. ---------- 11-01-2005 - 11-03-2005 ---------- --- ? - ? (17.5 hours) * I just lost 3 days worth of notes due to an inexplicable twiki error (could have been my fault, could have been twiki's). Lesson: Last time this happened, I concluded that I should save more often. This time I'm concluding that I need to use an editor that has autosave (emacs, in my case), and then copy the notebook to the wiki periodically. Welcome to the future, where we have to solve problems (autosave, for example) that have already been solved for decades. * I spent 17.5 hours over this period adding remaining bits of functionality, designing and implementing sanity checking, propagating error return values, cleaning up (naming, organization, documentation), etc. I spent quite a bit of this time working on sanity checking and error propagation, including general policies which will hopefully keep things consistent. ---------- 11-06-2005 ---------- --- 1:30PM - 4:00PM (2.5 hours) * Recovered from twiki problem, reorganized notebook, planned further performance testing. --- 9:00PM - 11:30PM (2.5 hours) * Implemented sanity checks for unregister and remove functions. * Added support for 0 length annotations (and did basic testing). * addPrefixAnnotations() already scans through the entire addPrefixes table. Attempting to add support to peekAndStripTypeDeannotations() for scanning the entire peekAndStripTypes table raised some complexities: Do we strip or peek an annotation that has both an associated strip deannotation and an associated peek deannotation? If the strip deannotation comes first, do we allow the later peek deannotation to look at the annotation? Also, we need to be careful not to add an annotation back to the packet more than once. I am going to leave these issues for later (when I add support for callbacks, at the earliest). --- 12:30AM - 2:00AM (1.5 hours) * Cleaned up some index and annotationsText indexing / bounds checking code and wrote up some notes on how that works. * More planning for measurements. --- 3:00AM - 6:30AM (3.5 hours) * Performed performance measurements. --- 7:00AM - 9:30AM (2.5 hours) * Performed more measurements. * Prepared data for presentation. * Measurements: 
LATENCY

Routed: 0.154/0.016 ms
1 Annotation: 0.175/0.016
10 Annotations: 0.186/0.029
100 Annotations: 0.285/0.036
1000 Annotations: 0.298/0.019

THROUGHPUT

* MTU = 100

Routed: 87.6 Mbps
1 Annotation: 81.0 Mbps
10 Annotations: 44.3 Mbps
100 Annotations: 9.08 Mbps
1000 Annotations: 8.14 Mbps

* MTU = 250

Routed: 345 Mbps
1 Annotation: 286 Mbps
10 Annotations: 177 Mbps
100 Annotations: 37.9 Mbps
1000 Annotations: 34.2 Mbps

* MTU = 1000

Routed: 879 Mbps
1 Annotation: 867 Mbps
10 Annotations: 802 Mbps
100 Annotations: 175 Mbps
1000 Annotations: 158 Mbps
---------- 11-11-2005 ---------- --- 12:30AM - 2:00AM (1.5 hours) * Cleaned up notebook, dealt with misc documentation issues. * Read some of Linux Device Drivers (lots of good stuff). * Began working on api/concurrency. Upcoming issues: * Concurrency * Exporting symbols (with EXPORT_SYMBOL). How about syscalls (with cond_syscall)? * /proc: Need to figure out a way to output possibly a lot of data to a /proc file. Maybe we could create a file in /proc for each registered deannotation that would just output the text of the deannotations of that type. * Callbacks: What's the signature? ---------- 11-11-2005 ---------- --- 3:30PM - 5:30PM (2 hours) * Implemented callbacks. * Read more from Linux Device Drivers. * Began working on API. --- 1:30AM - 3:30AM (2 hours) * Designed API, /proc interface, implementation of (de)annotation descriptors and (de)annotation cancellation, future improvements in data structures, and their interaction. * Figured out how to deal with a single annotation that should be peeked and stripped (All callbacks should be made for that annotation, no matter their type (peek or trip). If there is one or more strip deannotations, then the annotation should be stripped (and will not continue on with the packet)) and handling of ANN_ONCE annotations (they should be removed from the pool as soon as they are put on a packet. Once ---------- 11-13-2005 ---------- --- 3:00AM - 4:00AM (1 hour) * Organized notes on recent designs, cleaned up this notebook. ---------- 11-14-2005 ---------- --- 6:30PM - 8:30PM (2 hours) --- 10:30PM - 1:00AM (2.5 hours) --- 1:30AM - 4:00AM (2.5 hours) * Made changes to handling of ANN_ONCE annotations and annotations with more than one associated deannotation. * More design of annotation descriptors. * Begin placing pointerArray's. ---------- 11-23-2005 ---------- --- 11:00AM - 12:00PM (1 hour) * Implementation meeting with Rodrigo. ---------- 10-25-2005 ---------- --- 7:00PM - 10:00PM (3 hours) * Refreshed on my status and reviewed recent code. * Began designing /proc user space interface. * Decided that using /proc will be pretty ugly. Began considering alternatives - Looked into syscalls, signals, etc. ---------- 11-26-2005 ---------- --- 10:30AM - 2:00PM (3.5 hours) * More work on designing replacement for /proc as user space interface. * Considered the operation of a possible application (traceroute with annotation awareness detection) in design of user space interface. --- 7:30PM - 9:30PM (2 hours) * Cleaned up the code and the header. * Worked on the kernel space API. ---------- 11-27-2005 ---------- --- 7:00PM - 10:30PM (3.5 hours) * Finished transitioning global (de)annotation tables to using pointerArray's. * More work on the kernel space API. * Small changes - Transitioned all instances of peekAndStrip to just strip (names were becoming too verbose), deannotation callbacks now receive a copy of the ipHeader. ---------- 12-06-2005 ---------- --- 12:00PM - 1:00PM (1 hour) * Implementation meeting with George. * Will spend the next couple of weeks working with message queues and implementing the user space interface. Possible application will be annotation traceroute. * "Bears" poster session is coming up; We may want to put on a demo. ---------- 12-08-2005 ---------- --- 12:00PM - 2:00PM (2 hours) --- 3:30PM - 5:00PM (1.5 hours) * Finished the kernel level API ([un]register{PrefixAnnotation,TypeDeannotation}). * Did some basic testing. --- 9:00PM - 10:00PM (1 hour) --- 12:30AM - 2:00AM (1.5 hours) * Organized this notebook, wrote documentation on outstanding issues (in "polices and notes" section), figured out plan going forward. ---------- 12-10-2005 ---------- --- 2:30PM - 5:00PM (2.5 hours) * Redid resizePointerArray. Decided not to add reduction into removePointerFromPointerArray for now, as there is no pressing need for the functionality, it will only add more complexity (and possibly more bugs), it may, without thresholds (which have been noted as a later task), introduce oscillation or other problems which will cause more harm than good (suppose we remove a pointer and the array is reduced, then we add one and it is increased, then we remove one, and so on). * Got rid of annotationPool's (replaced with pointerArray's). --- 8:00PM - 11:00PM (3 hours) * Cleaned up kernel API (user*) function return values (they now provide more information). * More investigation of ways to implement the user space interface. * Determined that message queues will not work as a replacement for /proc. * Netlink sockets look like a promising replacement. * Look at "IPC Options" under "User Interface". ---------- 12-11-2005 ---------- --- 4:00PM - 6:00PM (2 hours) * Finalized plan for implementing the user space interface with netlink. With luck, I'll start writing code soon. ---------- 12-13-2005 ---------- --- 3:00PM - 5:00PM (2 hours) --- 6:30PM - 8:30PM (2 hours) * Began implementing aUserInteface. * Progress: The kernel establishes a socket, the user space program is able ot send a message to that socket (just based on the protocol type), and the kernel is able to see (and print) the contents of that message, along with meta information sent in the header (the sending processes' pid, a (meaningless, for now) pid, etc). * To successfully compile when including netlink.h (#include ), you must first #include and #include . * These are in the kernel source / from the kernel perspective: * struct sock is in net/sock.h. * struct msghdr is in linux/socket.h. * struct nlmsghdr is in linux/netlink.h * From the user perspective * struct iovec is in bits/uio.h. ---------- 12-14-2005 ---------- --- 2:30PM - 4:00PM (1.5 hours) * A lot of detailed thought and planning on the specifics of the netlink user space interface (see the User Interface section). --- 11:30PM - 3:00AM (3.5 hours) * More thought on the specifics of the aUserInterface module (see the User Interface section). * Cleaned up this notebook (really just organizing and formalizing my thoughts and notes). * Dealt with a few minor issues (file renaming, adding the skbuff to the deannotation callbacks). ---------- 12-15-2005 ---------- --- 2:00PM - 4:30PM (2.5 hours) * Became familiar with all of the sample code and investigated some of the complexities of the netlink setup. * Began coding (working through the User Interface task list). --- 5:30PM - 7:30PM (2 hours) --- 8:00PM - 9:30PM (1.5 hours) * More coding. * The kernel now establishes the control queue and accepts (and can read) arbitrary messages from user apps. This is basically a "production" reimplementation of the proof of concept. I also tried out some different ways to send and read messages and became more familiar with the whole netlink infrastructure. * Committed a bunch of stuff to CVS and made sure everything in a clean CVS checkout compiles. * skb_dequeue and skb_recv_datagram can both be used in the kernel to get a message from a (netlink) socket. I will use skb_dequeue, since it's better documented. * NETLINK_CB(struct sk_buff *) accesses the CB (control block) of the argument skbuff. This is a sort of free-for-all data section that, in this context, holds a struct netlink_skb_parms (from netlink.h), which needs to be filled in before sending a message from the kernel (don't worry about creds or eff_cap). * The netlink message header and the message payload are constantly serialized. Therefore, we can create a new header/payload by simply casting (to struct nlmsghdr *) a malloc'ed chunk of memory. * This is a model we will likely use when encoding a stripped annotation and information from the associated sk_buff into a netlink message to send to the user. Accessor macros or functions (such as NETLINK_DATA) could be useful. * NLMSG_DATA(struct nlmsghdr *) accesses the data payload of the message. Because of the serialization of the header and payload, the argument struct nlmsghdr * can be obtained using (struct nlmsghdr *)(skb->data). This should be used for both reading and writing the payload. * I'm not going to deal with any of the size-related macros for now (there just isn't enough documentation to understand how they work). Hopefully this won't cause any problems. * It is good to check skb_dequeue in a loop (that continues as long as the returned sk_buff is not null. * linux/net.h has a lot of socket-related functions. * sock_release closes kernel sockets. While we keep track of a struct sock * in the module, sock_release takes a struct socket * as argument. struct sock has a member called sk_socket, with type struct socket *. * CVS is a horrible tool. I don't understand how hard it could be to add a "move" function that would move (or rename) a file in the repository and keep the changelog intact. ---------- 12-16-2005 ---------- --- 9:00PM - 12:00PM (3 hours) * The kernel can now send a message to the user space app. * Simplified the code for sending messages between kernel and user space (in both directions). ---------- 12-17-2005 ---------- --- 12:00PM - 1:30PM (1.5 hours) * Reformed the kernel and user space code to use the new / simpler messaging approach. The user app can now send a message to the kernel and the kernel will reply back. * Dealt with a few small issues. --- 3:30PM - 7:00PM (3.5 hours) * Began implementing the user space library in combination with message interpretation in the kernel. * Dealt with namespace polution issues. * Planned a move to break the code into a lot more files (to deal with namespace issues, and so that it can be shared more easily). ---------- 12-18-2005 ---------- --- 11:00PM - 2:30PM (3.5 hours) * Spent a while investigating ways to improve the print structure. This started with the idea of using __func__ to simplify things for the "user" of the print infrastructure (only me for now), and turned into a larger project than I expected. * Worked more on proper formatting, organization, and naming; I'm working on breaking code off into separate files and worried about namespace pollution (so I'm going to prefix and start using static, etc). ---------- 12-19-2005 ---------- --- 5:30PM - 8:00PM (2.5 hours) * Worked on breaking off code and cleaning up the namespace. * Began cleaning up and improving aUserInterface (module), aLayerInterface (user space library), and userInterfaceTest (user space app) and formatting them with the new namespace scheme. --- 12:30AM - 4:30AM (4 hours) * Set up the message receiving / handling / responding infrastructure code in aUserInterface and wrote the first handling function (for a request to register a prefix annotation). * Finished the register prefix annotation function in the user space library, wrote a user space app to call it, and tested. * Found a bug in aEngine: I was using returnedErrorStatus (which looks for values less than 0) to check the return of sanityCheckNewPrefixAnnotation (which returns TRUE (1) or FALSE (0)). * We now have our first user space aEngine interface (minus a return value resonse message) function and an infrastructure for adding the rest (minus the type -> API table and any of the auto unregister stuff); Progress is clearly being made (sort of). ---------- 12-21-2005 ---------- --- 4:15AM - 6:15AM (2 hours) * Totally reorganized the header files. Created the "kernel", "shared", and "user" directories inside the include directory. The goal was to eliminate duplication of those constants and structs used by both modules and user space apps (for communicating through the kernel <-> user interface). * Committed everything to CVS and made sure everything in a clean checkout compiled. * The include directory is now only for "public" headers (those containing things used by more than one module / application). * Private / per-module/application headers should go in the same directory as the associated source file(s), and, if module header files, should have "Private" appended. * No module or app should directly include files for include/shared; They should be included by the appropriate file in include/user or include/kernel. * Of course, user apps should never include files in the kernel directory, and modules should never include files from the user directory. ---------- 12-25-2005 ---------- --- 7:00PM - 9:00PM (2 hours) * Message handler dispatch in the aUserInterface module now uses a table of function pointers. * The module now responds to user space requests with a return status message and the user space app receives and interprets the message. --- 4:30AM - 7:00AM (2.5 hours) * Cleaned up code, added error checks, thought through possible error situations. * Worked through some design issues. ---------- 01-10-2005 ---------- --- 8:00AM - 10:00AM (2 hours) * Organized this notebook (about a month's worth of disorganized notes). ---------- 01-21-2006 ---------- --- 2:00PM - 3:30PM (1.5 hours) * The bladecenter is going to be wiped and emulab installed, so I may not be able to work there anymore. Therefore, I finally got kbuild working on my local machine. In the end, it only required that I get the source for my kernel and create a symlink from /lib/modules/build to the kernel source directory. * Refamiliarized with the code. * API functions in the aEngine now return a special return value when a sanity check (of a user supplied value only) fails. ---------- 01-23-2006 ---------- --- 3:00PM - 4:00PM (1 hour) --- 5:00PM - 7:30PM (2.5 hours) * All user space calls to the aLayer (through netlink) return a return status. I moved the sending of this message to a common location that is also high in the call stack (ensuring that this return status message, which the user space library will be expecting, will be sent, barring something catastrophic). * Had to perform further configuration to allow module building and installation on my local machine. * Completed error checking and propagation review. * The user space library is now able to register a prefix annotation and receive the return value from that API call. * Added the kernel and user space functions necessary to support unregistering prefix annotations. There is a bug though. --- 10:30PM - 12:00PM (1.5 hours) * Bug: I was using an unsigned int to store the value returned from a search for the index of a particular descriptor. But, the search function returns -1 (ERROR) when the descriptor is not found. Therefore, it was passing by the check (which uses returnedErrorStatus, which is a macro that evaluates to "returnStatus < 0") and causing a problem later. I fixed this problem for two index variables in both al_unregisterPrefixAnnotation and al_unregisterTypeDeannotation. * Bug: This wasn't manifesting itself, but it was near the other bug: I store a pointer to the descriptor, free the descriptor (through unregisterDescriptor), and then dereference the descriptor pointer. That is, I reference free'd memory. Fixed the problem in both unregisterPrefixAnnotation and unregisterTypeDeannotation. I did a code review on the surrounding functions (all of the API functions) for similar problems and didn't find anything. * Cleaned up some outstanding issues in the user space library (code duplication, memory allocation, return values, etc). * Added kernel and user side support for unregistering an annotation. --- 12:30PM - 2:00AM (1.5 hours) * Added kernel and user side support for registering and unregistring type deannotations, without yet dealing with actually sending the deannotations to the user process(es). 
IMPLEMENTATION -
aEngine:
  Add an entry to the deannotation struct (for the app-specific data). I
  think I'll just use an int.
  Take in an extra argument to the register call and put an extra parameter
  in the callback.
  Make sure to actually send that data on callback.
  Look at the surrounding code to see if there is anything else to do.

aUserInterface
  Need to look over the calls to the aEngine functions to see what can go wrong
  and when we should and shouldn't modify the entries in the ID -> PID table.
  Write a function to generate the ID's (simple).
  Need to create the ID -> PID table - Create the core struct, create the
  pointer array, write some core functions (search by ID, for example).
  Need to add entries and remove entries from the table when appropriate
  (in register and unregister).
  Need to write the callback; Search the table and send the message.
  Need to write the function to send the message; Need to write the struct
  for the body of that message.
User space
  Write functions to wait or poll the message queue for an incoming message.
  Need to process a message if it is there and send the right data to the
  caller.
---------- 01-24-2006 ---------- --- 8:00PM - 9:00PM (1 hour) * Designed the handling and sending of deannotations to user space. --- 10:00PM - 11:00PM (1 hour) * Implemented support in the aEngine for an app-specific int (possibly an ID), specified at the time a deannotation is registered, and fed into each call to the given callback. This is a good idea in general, and important for a simple and efficient implementation of deannotations in the aUserInterface module. ---------- 01-25-2005 ---------- --- 12:30PM - 5:30PM (5 hours) * Broke off all of the pointer array code into a common library. Spent a while figuring out how to get kbuild to compile it into each of the aLayer modules (aEngine and aUserInterface). * Added support for app specific data at the user level. * Began implementing kernel support (in the aUserInterface module) for actually sending deannotations to the user space - Set up the basic data structures and data structure manipulation functions for the deannotation -> PID mapping table, began modifying the aUserInterface handlers for deannotation registration and unregistration in support of sending deannotations. * Talked to George about possible future projects. --- 7:30PM - 8:30PM (1 hour) --- 9:00PM - 10:30PM (1.5 hours) * Finished off kernel side of deannotation support for user interface. 
The Callback
  Need to look up the pid in the table (can use the search by uniqueId that
  I already wrote).
    Need to sanity check - Make sure there exists an entry for that
    uniqueId. Can also check that the type is what we expect.
  Send the message to that pid - I should write a separate function for
  doing that.
    Need to remember to pass along the user level app specific info.

The Message Sender
  Need to define a new body type (it should be al_kernel...)
  Should do all the normal things for this type of message - Need to have
  a static_section length and a total length, etc.
  Going to need to malloc memory.
  Need to copy in the annotationText.
  Need to use put to get room into the data section of the packet.
  Need to send the message.
  Need to check for errors and free the memory whenever we return. I wasn't
  thinking; I will be alloc'ing an skb, so I don't need to free it.
Nick Neely (nneely@berkeley.edu), 04-16-2006