The Boston Diaries

The ongoing saga of a programmer who doesn't live in Boston, nor does he even like Boston, but yet named his weblog/journal “The Boston Diaries.”

Go figure.

Saturday, January 14, 2006

Processing realtime data from LaBrea

Since I'm stuck at The Hospital, and The Hospital doesn't have wireless, I might as well work on the real-time LaBrea data processing program. Loaded up the laptop with program fragments and libraries I may need and brought along my copy of Advanced Programming in the Unix® Environment by W. Richard Stevens, and am coding up a storm.

And yes, I'm coding this up in C. Not like I'm going anywhere in the next couple of days.

LaBrea spits out lines like:

1136832897 Initial Connect - tarpitting: 3334 -> XXX.XXX.XXX.XXX *
1136832897 Initial Connect - tarpitting: 3339 -> XXX.XXX.XXX.XXX 139
1136832897 Persist Trapping: 3334 -> XXX.XXX.XXX.XXX 445 *
1136832898 Persist Activity: 45285 -> XXX.XXX.XXX.XXX 135
1136832898 Persist Activity: 34589 -> XXX.XXX.XXX.XXX 135 *
1136832898 Persist Activity: 3862 -> XXX.XXX.XXX.XXX 135
1136832898 Persist Activity: 4459 -> XXX.XXX.XXX.XXX 139 *

There's some other stuff that's logged, but I'm primarily looking for lines like the above. Which means the information I can store will look something like:

struct tprecord
  IP     src;
  Port   sport;
  IP     dest;
  Port   dport;
  time_t start; /* first time we see src:sport-dest:dport */
  time_t last;  /* time of last activity of src:sport-dest:dport */
  size_t packets;

Now, since we'll be handling a lot of connections, we need to store these structures in a way that is easy to search through. Could use a hash table, and we are keying off the src:sport→dest:dport tuple, and that's 10 bytes of pretty much random binary data, which is good for this type of thing. But it's an open ended hash, not knowing how many entries we'll be handling. There are several methods to handle overflows in a hash table, but that still means at some point doing a linear search, and then there's the overhead of having a hash table.

There's also storing the data in a tree. In fact, I even have code in C to manage a balanced tree (taken from Knuth). But the downside is—I only have code to add to the tree, not to delete from it. And it was hard enough to write as is.

And there's still the overhead of maintaining a tree structure.

So I'm using arrays. Less overhead and straightforward to manage. The only trick is keeping the array sorted in some order, but as long as you compare the structures in a consistent manner, that's not really an issue (and by the way, I'm sorting by source address, port, destination address and port, in that order).

To make it even easier, I have an array of structures (see above), and an array of pointers to said structures, and it's the pointer based array that is sorted (since it's faster to swap pointers than swap whole structures). And once sorted, you can use a binary search to find the record.

The default binary search in C, bsearch(), returns either a pointer to the found record, or NULL if not found. Good for most uses, but not quite what I want. In addition to either finding the record or not, I'd also like to know where in the array the record was found, and if not, where it would appear if it was in the array. And C's bsearch() does not return the index.

Why do I want that?

My thinking is that if the search (reguardless of what type of search it is) didn't find the record in a sorted array, it has the information as to where the missing record should be. And with the information as to where, it would be “trivial” to add the record at the right point in the array.

And that beats adding the new record at the end, and restorting (C's qsort() is Quick Sort, which on average is O(n lg n) running time, but the worse case is O(n2) and the worst case is then the array is mostly sorted to begin with, which is why I'd rather not resort after each addition).

And try as I might, I could not get a binary search to work that would also return the index. For now, I replaced the search with a linear search, until I can comb through some reference materials at home.

The other problem I'm having is the array manipulation code doesn't quite work. When the program starts, it has space to store X records. If it runs out of space, it increases the size of the various arrays until it hits some large number of records, then it will go through, purge records fitting some criteria.

Only it's not working properly.

Got a lot of work done on the program though, and it was nice to get into The Zone (even with a headache). At this point, I'm headed home for sleep and what looks to be yet another day at The Hospital.

Obligatory Picture

[It's the most wonderful time of the year!]

Obligatory Contact Info

Obligatory Feeds

Obligatory Links

Obligatory Miscellaneous

You have my permission to link freely to any entry here. Go ahead, I won't bite. I promise.

The dates are the permanent links to that day's entries (or entry, if there is only one entry). The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site:, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

You can also specify the entire month by leaving off the day portion. You can even select an arbitrary portion of time.

You may also note subtle shading of the links and that's intentional: the “closer” the link is (relative to the page) the “brighter” it appears. It's an experiment in using color shading to denote the distance a link is from here. If you don't notice it, don't worry; it's not all that important.

It is assumed that every brand name, slogan, corporate name, symbol, design element, et cetera mentioned in these pages is a protected and/or trademarked entity, the sole property of its owner(s), and acknowledgement of this status is implied.

Copyright © 1999-2022 by Sean Conner. All Rights Reserved.