The Boston Diaries

Monday, October 01, 2007

Beating on the dead horse that is health care

Gregory had a few quibbles with the “The Man, The Plan, The HMO” section of my health insurance rant of the other day (I think he didn't like the “Oh, you may pay some token amount like $20/visit, but otherwise, who cares what the price is?” bit).

Even Bunny said I got some details wrong in this section, saying that insurance companies don't just shrug and pay (Gregory said the same thing). She said that the insurance companies have a concept of a “normal price” for each service and can refuse to pay the doctor's (or clinic's or hospital's) but counter with what it thinks is the correct amount to pay. The doctor (clinic/hospital) can then either accept this counter offer, or go after the individual who had the service to pay the bill.

I don't think that Gregory's or Bunny's critiques change my main point in ths section all that much—that price is not the primary selection criterion when selecting a doctor (clinic/hospital).

I received another comment, commenting on this bit from Gregory:

Y'know, I was re-reading this entry and thinking about my good buddy PipeWrench, who is a very conservative Republican. He believes (as most Republicans do) that we Americans are responsible for ourselves and we should be going out and buying our own insurance and not begging the government for a handout.

Sadly, while PipeWrench is in the majority of people in this country who have health insurance, he is in an extremely small minority when it comes to the worldwide population of industrialized nations. People from Canada, or most of Western Europe would listen to his ideals and then look at him like he was completely nuts.

Increasingly, most Americans nowadays would look at him like he was nuts, too …

I'd like to ask PipeWrench if he'd like to shell out that kind of money on his own without any kind of health coverage, or save up that money just in case he happens to get hurt. But I've learned my lesson not to engage PipeWrench in discussions of a political nature. I like him and want to keep him as a friend.

While PipeWrench didn't respond (he doesn't really use the Internet all that often) his girlfriend did (at LiveJournal, reproduced here because once the entry rolls off the feed, so does the comment at LiveJournal):

I think you know I agree with your political views for the most part. This was very well worded. I happen to look at the link to Greg's journal, where he mentions PipeWrench and politics in the same entry, lovely. To answer his question … yes PipeWrench would pay for his own hospital stay. He almost paid more than twice that amount to have his spine fixed at a different hospital, but his doctors talked him into one in his network for various reasons. Oh, and shock! He does save up money for emergencies. PipeWrench is not a hypocrit, sorry to disappoint.

“Well, there it is,” as Emperor Joseph II is wont to say in Amadeus.

And while I'm beating a dead horse here, my entry also spawned some interesting comments at Flutterby.

Tuesday, October 02, 2007

Next time, I should stick around long enough to find out the name, the scam, and how much money it'll cost me to make money

“Hello? Hello?”

“Hey there Sean.”

“Hello.”

“You signed for information on becoming financially independant and I'm wondering if you are interested in making money.”

“I'm sorry, but I'm not interested at this time.”

“What? You don't want to make more money? Everybody wants to make more money.”

“I'm sorry, I'm not interested at this time. Especially when it's on my cell phone.”

“But Sean, this is the number you gave me.”

“Be that as it may, I'm not interested at this time.”

“So, you'd rather be a loser?”

“Yes, I'm a loser who is not interested in your meth—” Click.

Wednesday, October 03, 2007

Workaround for a Heisenbug

Okay, now I'm concerned. I'm now running the production greylist daemon on an actual server (not a virtual server) with the checkpointing feature enabled, and it's working. That can mean one of two things:

There's a bug in the virtual server environment that my program tickles
There's a bug lurking in my code that the virtual server environment tickles

Neither one is good, and it's bugging me that I don't know which is the case. But I managed to at least work around the problem in the meantime (now watch—the bug is in my code, but it's the virtual server environment that causes the bug to surface after a few hours instead of a week or so it might take on a physical server).

Thursday, October 04, 2007

Swimming with sharks

I just watched Maxed Out (link via coell via Spring), a documentary on the debt industry (credit cards companies, banking institutions, etc.) and how it's in their interest to offer incredible lines of credit to those who can't really afford it since they'll be paying off forever (one example brought up in the film, for every dollar a credit card company attempts to collect, only 33¢ is for the principle—the rest is interest and late fees).

I'm of mixed minds on this. I think it's horrible what the credit agencies have done to the people interviewed in this documentary (half were deep in debt, the other half had family members who committed suicide because they were deep in debt), seducing them with loose credit and no way of ever paying it all off. On the other hand, these are corporations we are talking about, and if by 18 you haven't learned that corporations are out for themselves (or their shareholders if they're public companies) then maybe you should learn it the hard way.

How far should we as a society go to protect ourselves from our own stupidity?

I can see those who don't speak English, or have learning disabilities as sucessfully sueing these companies for fraud; but if you can read and write English, then no, it's your responsibility to read the fine print, since by law, they do have to spell it out (even if it's 10 pages at 8pt).

Friday, October 05, 2007

It's not quite as cool as a house made out of an old jetliner, but it's probably more affordable

For Gregory—furniture made from aviation salvage (via Instapundit).

Saturday, October 06, 2007

Another look at Federalism—you know, how our government was originally designed?

And when the Fed's ban sex toys? Where do you go then? Sure, it's nice when the Feds enforce the laws you like, but what do you do when they enforce those you don't?

It's true that, left to their own devices, some states are going to choose some laws that are more restrictive than the laws Feds might enforce. For example, I think CA would have much more restrictive gun laws. Many Southern states would probably ban abortion.

However, it's much easier to reform and escape state law than it is to escape or reform Federal laws.

If we had a more federal system, marijuana would be completely legal in many states, and perhaps harder drugs as well. You might be able to buy a silencer without a FFA license in others.

Advocates of liberty would also be able to point to real life examples of American communities that are working just fine, despite the legalization of drugs/machine guns/prostitutes, instead of hypothetical examples, or distant foreign experiments that most people will never see.

In a more federal system, states would also have to compete for people more fiercely. Want high tech/bio tech businesses to locate in your state? Anti-abortion, anti-gay statutes are going to be a big turnoff to the employees (and hence, the employers) of such companies.

People would be more free to choose which legal regime most closely matched their preferences. If you wanted to live where abortion was legal, live in CA. If you wanted to shoot machine guns, choose WY or ID. Want to do both, move to NH.

Compare that to what you would have to do to escape oppressive federal laws. One route would be to move to a completely new country, which would require you to leave behind friends, family, and business contacts. You would also have to surmount language, cultural, and legal barriers to immigration.

Or, you could spend decades waging a campaign to reform the law at the federal level. This would probably require millions of dollars, and the cooperation of thousands of people to wage, with no guarantee that you would ultimately succeed.

A more federal system might not mean a more libertarian society on a given issue, in a given state. But overall, I think it would result in greater practical freedom for those who want it.

comm ent about States' Rights & Alabama sex toys at Flutterby

I quote in full, since there's a better chance that the person I want to read this will read this.

“Son, there's not much left of the carcass … you can stop beating that horse now.”

In a continuing back-and-forth exchange, the Director of the Citizens Alliance for National Health Insurance piped in, saying, “For those of you with an interest in having a viable national health insurance system in the US in our lifetime, please visit www.HR676.org.”

I checked out the Citizens Alliance for National Health Insurance website and while the site answers a bunch of questions like “Why haven't I heard of this bill before?” and “Do we really want our health care system to be controlled by government bureaucrats?” while urging people to sign up, it does not, however, present the actual text of H.R. 676, nor links to the actual text of H.R. 676. Yes, it does link to the official website for H.R. 676, but the official website for H.R. 676 (run by Congressman John Conyers, Jr. (D)) doesn't have the actual text to the bill, nor a link to the actual text.

It's a weird omission from both sites, don't you think?

And it's not like it's not online or difficult to find online.

Okay, so I went the extra step to find the actual text to H.R. 676 and after reading it, I have quite a few questions that the Citizens Alliance for National Health Insurance haven't answered. For instance:

(a) In General—All individuals residing in the United States (including any territory of the United States) are covered under the USNHI Program entitling them to a universal, best quality standard of care. Each such individual shall receive a card with a unique number in the mail. An individual's social security number shall not be used for purposes of registration under this section.

H.R. 676 [109th]: Expanded and Improved Medicare for All Act

Since the bill states “individuals residing in the United States” and not “citizens of the United States,” am I to infer that this also covers aliens? Both legal and illegal? I don't have a problem with covering legal aliens residing in the United States, but I do have a serious problem with my taxes going to pay for the health care of a large number of illegal aliens who don't even pay taxes!

Taxes? Did I say taxes?

National health insurance will simply require participating members to pay a similar monthly health insurance premium, perhaps in the form of a tax (but it's still the same thing as a premium no matter what you call it**)

**Whatever they call it—It's very important to keep in mind that this is NOT an ADDITIONAL tax but a REPLACEMENT for current private health premiums.

Citizens Alliance for National Health Insurance

Sorry, premiums, which brings up another point—is this voluntary? If it is, I'll buy the Citizens Alliance for National Health Insurance argument that it's a “premium,” not a “tax.” But if this is involuntary, you can play all the language semantic games you want, it becomes a tax! (or outright theft as some would say) The bill doesn't say one way or the other, although Conyer's financing figures show it as a payroll tax of 3.3% on both employer and employee.

Which brings up another question—as someone who is self-employed, are my taxes going up 6.6%? (In case you are unaware, those who are self- employed pay 7½% Social Security tax as an employee, and 7½% (the so called “Self-employment Tax”) as employer! Again, it's not answered in the text, nor on the official website.

(2) FEE FOR SERVICE—

(A) IN GENERAL—The Program shall negotiate a simplified fee schedule that is fair with representatives of physicians and other clinicians, after close consultation with the National Board of Universal Quality and Access and regional and State directors. Initially, the current prevailing fees or reimbursement would be the basis for the fee negotiation for all professional services covered under this Act.

(B) CONSIDERATIONS—In establishing such schedule, the Director shall take into consideration regional differences in reimbursement, but strive for a uniform national standard.

(C) STATE PHYSICIAN PRACTICE REVIEW BOARDS—The State director for each State, in consultation with representatives of the physician community of that State, shall establish and appoint a physician practice review board to assure quality, cost effectiveness, and fair reimbursements for physician delivered services.

(D) FINAL GUIDELINES—The regional directors shall be responsible for promulgating final guidelines to all providers.

(E) BILLING—Under this Act physicians shall submit bills to the regional director on a simple form, or via computer. Interest shall be paid to providers whose bills are not paid within 30 days of submission.

(F) NO BALANCE BILLING—Licensed health care clinicians who accept any payment from the USNHI Program may not bill any patient for any covered service.

(G) UNIFORM COMPUTER ELECTRONIC BILLING SYSTEM—The Director shall make a good faith effort to create a uniform computerized electronic billing system, including in those areas of the United States where electronic billing is not yet established.

(3) SALARIES WITHIN INSTITUTIONS RECEIVING GLOBAL BUDGETS—

(A) IN GENERAL—In the case of an institution, such as a hospital, health center, group practice, community and migrant health center, or a home care agency that elects to be paid a monthly global budget for the delivery of health care as well as for education and prevention programs, physicians employed by such institutions shall be reimbursed through a salary included as part of such a budget.

(B) SALARY RANGES—Salary ranges for health care providers shall be determined in the same way as fee schedules under paragraph (2).

H.R. 676 [109th]: Expanded and Improved Medicare for All Act
(emphasis added)

How is this not nationalizing the health care system? As a doctor (not that I am one, but I'm asking as if I were one) how does this benefit me? Does my malpractice insurance go down? Is it eliminated? Am I still allowed to practice privately the same treatments that this bill covers? If so, am I allowed to charge less than the Federal mandated charges? More?

(a) In General—It is unlawful for a private health insurer to sell health insurance coverage that duplicates the benefits provided under this Act.

H.R. 676 [109th]: Expanded and Improved Medicare for All Act

As an insurance company, what about our existing policies when (if) this goes into effect? Do we still provide coverage under the existing policy? If no, do those portions of the policy become null and void? And does the insured get part (or all) of their premium back?

(c) Intent—Sums appropriated pursuant to subsection (b) shall be paid for—

(1) by vastly reducing paperwork;

(2) by requiring a rational bulk procurement of medications;

(3) from existing sources of Federal government revenues for health care;

(4) by increasing personal income taxes on the top 5 percent income earners;

(5) by instituting a modest payroll tax; and

(6) by instituting a small tax on stock and bond transactions.

H.R. 676 [109th]: Expanded and Improved Medicare for All Act

How odd, even the text of the bill uses the word “tax” instead of “premium.” It looks like a tax to me. And how do I know that the “modest payroll tax” won't balloon into an “unmodest payroll tax?” Amendment XVI of the Constitution passed because the income tax was guaranteed to be a 1–7%, but that was quickly modified.

As it stands right now, there're too many questions for me to be comfortable with this bill ever being passed.

Sunday, October 07, 2007

X11 is dead?

The X11 Desktop's (what you see to the left) client/server protocol is built-in. There's no need to use vnc in most cases!!

I have no idea why it is so hard for people to grasp the power of client/server graphic networking. It's simple. Easy. Transparent. And so enormously useful that innum erable projects use it to great effect, and if only more people would just turn X11's network support on, it would be a better world.

I can only imagine it's a conspiracy.

Legions of PHBs hunched over their laptops in 1989, saying: “THIS X11 CONCEPT IS TOO POWERFUL! Imagine a world where every cell phone, handheld, laptop, desktop, server and supercomputer in the world could run all their applications on each other over a network transparent protocol!

“There'd be no need to rewrite every application for every new paradigm. We'd stop having to support all the old ones in the field, too. Every app on your cellphone could run on your desktop! And every app on your desktop could run on your cellphone! Think of all the jobs that would be lost! Think of (my) children and my golf fees!"

X11 is dead, long live X11

The X11 Windowing System is something that's hard to explain to someone who doesn't normally use computers remotely, and thus it's even hard to explain why using a computer remotely is even desireable.

I was first introduced to X11 in college, most likely by my friend Ken, who regularly came barging into my office with “Hey Sean! You gotta see this!”

X11 was cool because the Computer Science and Engineering Department would regularly install neat programs, such as a little program called Mosaic that allowed one to view information on something called the “World Wide Web,” that I could use in my office (in the Math Department one floor below the Computer Science and Engineering Department), without having to go to the trouble of installing it on my own computer (well, it wasn't my computer, but I was the administrator of it).

I even learned how to use X11 to get the login screen from my office computer on the computers in the various Computer Science and Engineering computer labs if I was stuck upstairs for some reason (and I preferred my office machine, an SGI Personal IRIS 4D/35 with video-editing capability, over the run-of-the-mill Sun SPARCstations CSE used).

I don't use X11 in that way much anymore; I find very little need for remote running of graphical programs, but when I do, it's nice that I can.

Unfortunately, there's a perception that X11 has poor performance. And yes, compared to NeWS, X11 is very clunky. And the pretty 3D eye-candy of modern windowing systems leads to even more poor performance across the network.

Besides, Microsoft Windows was never designed with network transparency in mind, and thus, to get access to Windows programs remotely, you need something like VNC. The same goes for the Macintosh. And hey, if you have ported VNC to both Windows and Mac, it's not that much work to port it to X11.

Sigh.

Another part of Mike Taht's rant skirts around true peer-to-peer networking, which the Internet was about fifteen years ago, but now, what with Microsoft's poor record at security and a perceived lack of IP addresses, is no longer the case. IPv6 will supposedly fix that, with an address space large enough to give every atom in the universe its own address, but the change in the Internet infrastructure (at least in the United States) will be expensive, not to mention time-consuming, so don't expect it to happen any time soon.

Yet another sigh.

Updated on Tuesday, October 9^th, 2007

Why VNC may be better than X11.

Tuesday, October 09, 2007

Montezuma's Revenge

Yesterday was apparently some sort of holiday but instead of celebrating the rape and enslavement of Native Americans I was in bed fighting off what can only be called Montezuma's Revenge.

I'm feeling much better today.

And speaking of Montezuma's Revenge, I think Spring might want to pick up a few of these for those times when Spodie is himself suffering from Montezuma's Revenge.

X11 is alive?

Mark send me an email replying to my post about X11:

From

Mark Grosberg <XXXXXXXXXXXXXXXXX>

To

sean@conman.org

Subject

Of X11 and remote access…

Date

Mon, 8 Oct 2007 13:36:10 -0400 (EDT)

Sean,

I read your blog post on how X11 is network enabled and thought you glossed over a very important point. See, X11 is network enabled in that it has this concept of a program is a client to a display. So yes, if I am at home I can run some program on my X11 machine at work and send the display over.

But VNC on X11 goes one step better. It's a bit like “screen” (a program I still use) but for graphical apps (something I rarely use). I can have my X11 desktop sitting in some virtual framebuffer somewhere, connect to it, interact with it, go home, re-connect and it is exactly where I left it.

The normal X11 networking model is such that I loose my program state every time I move around. At least for me, personally, I am the kind of person who maybe yearly reboots a computer such that I loose my working environment and I frequently move about to different locations.

So for me, VNC on an X11 desktop makes total sense (well, screen makes even more sense since my main UNIX box probably doesn't have enough RAM to make a virtual framebuffer).

Oh, and VNC is way faster too, especially TightVNC. You don't wait 6hrs for a window to pop up while they negotiate event masks and other nonsense that should not exist.

He does have a point, and it's one of the problems with X11—you can't redirect a window to another display on the fly. Or, at least, I don't know of a way to do that. It also depends upon how you work. Me? I don't tend to leave applications running for any great length of time (especially graphical programs) because I have this irrational fear that they'll just keep sucking memory up until the machine becomes unusable.

Help fight leukemia and lymphoma

Passing this on … Spring could use your help. Please donate to help her raise money for leukemia and lymphoma research. Every little bit helps.

Wednesday, October 10, 2007

“He stacks his dice.”

For Lorie, who does love her dice—a video of some sweet dice stacking moves (via Jason Kottke).

Thursday, October 11, 2007

A little lesson on i18n

Then your Russian translator calls on the phone, to personally tell you the bad news about how really unpleasant your life is about to become:

Russian, like German or Latin, is an inflectional language; that is, nouns and adjectives have to take endings that depend on their case (i.e., nominative, accusative, genitive, etc …)—which is roughly a matter of what role they have in syntax of the sentence—as well as on the grammatical gender (i.e., masculine, feminine, neuter) and number (i.e., singular or plural) of the noun, as well as on the declension class of the noun. But unlike with most other inflected languages, putting a number-phrase (like “ten” or “forty-three”, or their Arabic numeral equivalents) in front of noun in Russian can change the case and number that noun is, and therefore the endings you have to put on it.

He elaborates: In “I scanned %g directories”, you'd expect “directories” to be in the accusative case (since it is the direct object in the sentence) and the plural number, except where $directory_count is 1, then you'd expect the singular, of course. Just like Latin or German. But! Where $directory_count % 10 is 1 (“%” for modulo, remember), assuming $directory count is an integer, and except where $directory_count % 100 is 11, “directories” is forced to become grammatically singular, which means it gets the ending for the accusative singular … You begin to visualize the code it'd take to test for the problem so far, and still work for Chinese and Arabic and Italian, and how many gettext items that'd take, but he keeps going … But where $directory_count % 10 is 2, 3, or 4 (except where $directory_count % 100 is 12, 13, or 14), the word for “directories” is forced to be genitive singular—which means another ending … The room begins to spin around you, slowly at first … But with all other integer values, since “directory” is an inanimate noun, when preceded by a number and in the nominative or accusative cases (as it is here, just your luck!), it does stay plural, but it is forced into the genitive case—yet another ending … And you never hear him get to the part about how you're going to run into similar (but maybe subtly different) problems with other Slavic languages like Polish, because the floor comes up to meet you, and you fade into unconsciousness.

The above cautionary tale relates how an attempt at localization can lead from programmer consternation, to program obfuscation, to a need for sedation. But careful evaluation shows that your choice of tools merely needed further consideration.

Via Flutterby, A Localization Horror Story: It Could Happen To You

Yikes!

And I thought I was being clever when writing my own replacement for printf() that allowed you to refer to parameters by placement.

Okay, I'll have to explain that.

In printf(), you specify variables with a special code, such as “%s” for a string variable, “%d” for an integer:

printf("Hey!  I saw %d %s\n",count,object);

But the variable specifiers and the variables themselves have to match up. So, if I want to change the output from “I saw X blah” to “blah: X” I not only have to change the text, but the order of the parameters as well:

printf("%s: %d\n",object,count);

Also, if you wanted to print a value multiple times (and it sometimes comes up) you have to repeat that value:

/* helps to say this as Foghorn Leghorn */
printf("That boy is %s!  %s, I say!\n",adjective,adjective);

I got around that by separating the variable types and parameter positions from the format string:

my_output("i $","Hey!  I saw %a %b\n",count,object);
my_output("i $","%b: %a\n",count,object);
my_output("$","That boy is %a!  %a, I say!\n",adjective);

(okay, here, “i” denotes an integer parameter and “$” a string parameter. In the format string, “%a” refers to the first parameter, “%b” the second, and so on)

The idea was the ability to change the string without having to change any code, and to that end, I did quite well. What I didn't realize is that full i18n is hard. I mean, just beyond character set issues.

Man, I had no idea languages could be so crazy.

Friday, October 12, 2007

Spam from bogus IP space

Earlier today (okay, technically yesterday) I came across the concept of bogons, or IP address not officially allocated for use. They even provide a current list of non-routed IP blocks. Curious about the effect of using said list to block potential spam, I setup a test, consisting of 565,012 tuples (we've stepped up testing of the greylist daemon over the past week) previously processed (I'm keeping some extensive logs here), added the 6,803 IP blocks not allocated, and let it rip.

An hour and a half later, I had my answer.

Of 565,012 tuples processed, only 6,117 came from non-allocated IP space.

It's a little over 1%.

I don't think it's worth adding the non-allocated IP space to the greylist daemon. Not that it makes the daemon run slower, it's just that an IP list of that size takes up quite a bit of memory due to the trie structure used to store the table, and for such a small gain, I don't feel it's really worth it.

I guess he won't be extending anyone's mortgage by three inches anymore …

Who hated Tolstokozhev so much as to hire a hit man to assasinate him? Well, I guess you have about one billion e-mail users to suspect. Tolstokozhev was a famous spammer who sent millions of e-mail promoting viagra, cialis, penis enlargement pills and other medications. Links in these e-mails usually led to some pharmacy shop, which paid Tolstokozhev a share of its revenue. This is a well known affiliate scheme employed by spammers worldwide. Tolstokozhev is estimated to be responsible for up to 30% percent of all viagra and penis enlargement related spam.

Via Wlofie in email, Russian Viagra and Penis Enlargement Spammer Murdered

Well, speaking of anti-spam measures, that certainly works (not that I … um … condone … such actions). A bit messy, in both physical and legal aspects, but still, quite effective.

Update a few minutes later

Then again, it may be a hoax:

Some musings on parallelizing programs

Can you, in your favourite language, show me the easiest way to parallelise the following program (written in C)? I am just genuinely curious.
int gimme(int x)
{
  return x * x;
}

int main(void)
{
  int i = 2, j = 4;
  int a = gimme(i),
      b = gimme(j);
  return a * b;
}

Write Me A Small Program

In my ideal world, any compiler worth its salt would optimize (mostly through variable lifetime analysis and constant propagation) that program down to the following:

int main(void)
{
  return(64);
}

but the author's main point is—what languages today can easily parallelize that code? His point, on a massively parallel computer, the calls to gimme() are both independant of each other, and therefore can be computed at the same time (assume, for the sake of argument, that gimme() takes a bit more time to execute than a single function call and multiply).

And in an ideal world, a compiler should be able to figure out that gimme() is, for lack of a better term, a “pure” function (one that does not rely upon data outside of its input parameters and local variables). This also implies that thread creation is cheaper than it is today (or easier, which is another of the author's points), and that the compiler will take care of the messy thread creation details for me.

But even an ideal compiler won't take us very far.

I was thinking about this as I was running tests on the greylist daemon last night. The program maxed out at around 130 requests per second, and this on a dual-core 2.6GHz Intel Pentium system that hasn't even used swap space, so speed and memory isn't an issue (and remember, the greylist daemon keeps everything in memory).

But as written, the program only uses a single thread of execution. Could I not create two threads (one for each CPU in the machine) and double the speed?

Maybe, but the compiler won't help me much.

When a tuple [IP address, sender address, recipient address] comes in, the program scans a list of IP addresses which can accept or reject that tuple. If the tuple isn't outright accepted or rejected based on the IP address, then the sender address is checked, then the sender domain, then the recipient address, then the recipient domain. Now, those lists are, for the most part, read-only, so no coordination is required between multiple threads for read access.

The actual greylist itself? The program checks to see if the tuple [IP address, sender address, recipient address] already exists, and if not, adds it to the existing list of tuples. And that part, adding the tuple to the list, happens on just about every tuple that comes in. In effect, the tuple list is “write- mostly.” And to ensure a consistent list of tuples, you need to coordinate multiple threads when trying to update the list. And now you get into semaphores, and locking and dining philosophers …

Messy stuff.

I suppose each thread could get its own tuple list to update, but then you have to ensure that any given tuple X always goes to the same thread. Easy enough I suppose, but it's not something that you can leave up to the compiler.

In fact, in an ideal world, an ideal compiler would be hard-pressed to automagically parallelize this program. Certain parts, maybe. But overall, it would required thinking how best to write the program to be parallelized in the first place.

Saturday, October 13, 2007

Heisenbugs III

Wow … ten days.

Of course, the greylist daemon only took about two hours to hang on the right set of physical servers.

So I have a very subtle bug in the code.

XXXX.

The Right To Arm Bears

We had finally arrived at the South Florida Fair Grounds. I found it amusing that the South Florida fair grounds are about as far north as you can get in South Florida and still be within the geographical region known as South Florida (which technically speaking, lies between the Jupiter Inlet to the north and Homestead along the southern border, the Atlantic Ocean along the eastern edge, and US-27, beyond which is swamp land).

“You'd think they would have put the Fair Grounds somewhere more central, like central Broward County,” I said to my compatriots as we headed from the parking lots to the gates.

“It could be worse,” said Bunny, using a phrase I commonly use right back at me. “You do know that the University of South Florida isn't even in South Florida?”

“Nice sense of irony,” I said.

As we passed beneath a sign that said “Thank you. Hope you had a blast” I had an epiphanous thought—I probably picked the wrong color shirt to wear today—red. But, I thought, at least the blood won't show.

And with that, we entered the South Florida Fair Grounds towards the Gun and Knife Show.

Guns everywhere. Glocks. Smith-Wesson. Mossbergs. Colts. Everthing from .22 to 50-calibre, and then some. The Younger was eyeing an anti-aircraft rocket launcher when Spring asked who could possibly use such a device. Someone nearby said it could be useful if you live next to an airport. The Younger turned and looked expectantly at his Mom.

“No,” said Spring. “Let's continue on.”

At the point the group broke. Spring went off chasing the Younger as he flitted from table to table. Scott stayed to talk to a merchant behind the table, asking about the finer points of Colt 45s with an extended barrel. Wlofie headed off to a booth selling survival gear, and Bunny went off on a mission—to find a collection of throwing stars, muttering something about Racoon Ninjas terrorizing her neighborhood and teaching them a lesson.

I myself wandered off, amazed at the variety of guns available. And frankly, I found most of them to look fake—more like plastic toys. And to my surprise, most of them were plastic! At least the pistol grips. The cognitive dissonance was too great—the guns in TV and movies looked more “real” than these very real guns in front of me. But pick one up, and the cognitive dissonance grew—these guns where heavy.

“Looking for anything in particular?” asked a gentleman behind the table.

I looked up to see him wobbling around on a Segway. “Um,” I said, more cognitive dissonance building up, “I'm just looking.”

“Okay,” he said. “But if you need any help, just ask.” And he wheeled down the booth to pass a fellow co-worker also on a Segway. I've been to plenty of computer related shows and never saw a Segway, much less two—no, make that three Segways.

Amazing.

I wandered off to parts elsewhere.

Books on modifying the firing mechanism on an AK-47 I expected. Books on martial arts I also expected. I could even see the rationale for conspiracy books ranging from the Illuminati, the Freemasons, JKF to 9/11.

I was not expecting New Age books on Atlantis, aliens and homeopathy.

But even that wasn't as out of place as books by Noam Chomsky.

Noam Chomsky.

Available at a Gun and Knife Show.

Hey, if a Russian can sell crystals at a Gun and Knife Show, why not Noam Chomsky at a book booth?

Cognitive dissonance.

A few hours later we all meet back outside. Bunny had been unable to locate sufficiently sharp throwing stars to tackle the Racoon Ninjas terrorizing her neighborhood. The Younger had procurred a gas mask for those times when it's his turn to change the litter box. Scott informed us that while he could tell us what he got, he would have to kill us afterwards. Wlofie had a big grin on his face, but declined to tell us what that was all about.

And myself? I had successfully survived the Gun and Knife Show in a red shirt.

Sunday, October 14, 2007

Random and a rather rambling musings on computing environments and the customization thereof

I'm not even sure where to begin with this. Or even where I'm going with this.

First off, there's Aza Raskin's demonstration of Enso, an application that brings the command line back to the GUI in a very novel way (and yes, the video is worth watching, and the Enso application is something that, were it available for either the Mac or Linux, I might buy).

I got the link to the video from Thought Storms: The Return of the Command Line, which I linked to before (and that post is somewhat related to this post).

This all somehow is all related, primarily to customizing the computing environment.

One small example: I have customized vi (the standard Unix editor) to my liking. It's not a lot of customization though. My .exrc file looks like:

set ai
set showmode
set sw=2
map m ^F
map v ^B

That's it. Five lines of modification. The first just sets auto-indent mode. The second one displays the current mode (command mode or insert mode) on the screen. The third sets the tab-indent to two spaces. Those, I can live with or without (and really, half the time, I don't want auto-indent mode so that's actually a wash).

It's the last two lines I can't live without.

The first maps the M key to page forward in the command mode. Normally, the “page-down” command is Ctrl-F but that's two keys to hit, and usually, when I'm in vi, I'm not editing, I'm viewing. And the last line maps the V key to “page-up”, which is normally bound to Ctrl-B (again, two keys).

And what normally happens is I get on some random server at The Office, I'm viewing a file in vi, go to hit M to page down through the document, and get … something else.

Then I go ballistic.

Sigh.

Which is one reason why I tend to type out insanely long command lines instead of making a script—because customizing the computing environment isn't worth my time or sanity (even with a five-line file; also, people using my customizations, one of which involves renaming rm to delete tends to drive them up a wall).

This also relates partially to my dislike of IDEs. I've learned to be productive without one, since I “grew up” without using them. And I've found them to be intrusive the few times I have used them (mainly beause the built-in editor sucked compared to what I was actually used to, which again, ties back into computing environment customization). I found it weird to hear programmers (mostly students) asking where they could get an assembly language IDE—they were totally lost without such a crutch (and yes, I'm using that word deliberately here). But my crutch was a particular text editor from IBM. Was it really that great of an editor? Maybe. This quote pretty much sums up how I felt about it (the quote is about a newer version of the editor I used):

Is PE II really that good? Frankly, no. It's just that I'm really that lazy. I've used it for so long that it's like breathing to me. I don't have to think about where the keys are or what they do. I just think about what I want to do and it happens.

When I need to edit a C file that is too large for PE II, I use Brief. Sure, Brief is bigger, better, and faster than PE II. But its key bindings aren't etched into my skull like the pattern on an old monochrome monitor that's been displayed for months.

But enough about that. I know what my preferred C/C++ programming environment is in DOS. I want to find my preferred programming environment in Linux. The reason I bring up my personal preference—and the inertia that cements it—is that I believe the same sort of inertia is at work among the developers I queried.

Linux development: Command Line, Emacs or IDE?

I used that editor long enough that I never had to “think” about using it. I just did. And I'm still attempting to use the Tab key for navigation to this day (under PE, the Tab key didn't insert spaces—it just moved the cursor to the next tab stop; I could navigate to any point on the screen in just a few seconds, if that).

So, to bring this back around to Enso—yeah, it's great. Yeah, I'm tempted to get it (if only it didn't run under Windows). But do I want it? Were I to become dependent upon it, would using a non-Enso enabled system suck too much?

What exactly do I want from my computing environment?

Seven months ago I brought my workstation home from The Office with the intent of replacing my old home system linus. But the amount of customization I've done to linus is so extensive, that I've yet to actually switch. Even though I can create entries for this blog technically anywhere (and submit it as a text file, or through email, or through a web-based interface) I still prefer editing on linus, as I have several extentions to the editor I use there to help create entries (and it's still not as fast or as smooth as I would like it).

Blah.

An Open Letter to Script Kiddies

Dear script kiddie,

I know, and you know, that if you have a web server with PHP, you have an exploit waiting to happen. It's axiomatic. And really, I'm okay with that.

I'm also okay with you uploading your crap to the server using said exploit. I like porn just as much as anyone else. And you really have some interesting stuff there (thus validating Rule 34 of the Internet).

You're even smart enough to wipe the source code after you start your nefarious program. Or you're smart enough to get programs that do that for you. Bully for you. Wonderful.

But let me give you one more piece of advice, and I mean this from the cockles of my heart, maybe below the cockles, maybe in the sub-cockle area. Maybe in the liver. Maybe in the kidneys. Maybe even in the colon. But it's a piece of advice you need to hear.

If you want your little hack to go unnoticed, and frankly, that's the point, isn't it? To do your little script kiddie thangs without being noticed, then please,

Stop sucking up all the CPU time causing the system load to shoot over 600 you XXXXXXX XXXXX XX XXXX!

Ahem.

Thank you for your consideration.

Monday, October 15, 2007

“I coulda had a V8!”

Valgrind.

Why didn't I think of that sooner?

Anyway, I installed valgrind on the virtual server and started up a test run to see if I could locate the current bug.

Not two minutes in, and I got the following:

==27967== Use of uninitialised value of size 4
==27967==    at 0x80508DF: crc32 (crc32.c:83)
==27967==    by 0x804A6C1: send_packet (main.c:566)
==27967==    by 0x80496FC: mainloop (main.c:151)
==27967==    by 0x80493A5: main (main.c:68)
==27967== 
==27967== Syscall param socketcall.sendto(msg) points to uninitialised byte(s)
==27967==    at 0x40EDFD1: sendto (in /lib/tls/libc-2.3.4.so)
==27967==    by 0x80496FC: mainloop (main.c:151)
==27967==    by 0x80493A5: main (main.c:68)
==27967==  Address 0xBEEDB2EA is on thread 1's stack
==27967== 
==27967== Source and destination overlap in memcpy(0x4251028, 0x4251028, 256)
==27967==    at 0x401D236: memcpy (mac_replace_strmem.c:394)
==27967==    by 0x804F00D: tuple_expire (tuple.c:231)
==27967==    by 0x804BC3D: handle_sigalrm (signals.c:278)
==27967==    by 0x804B6BF: check_signals (signals.c:50)
==27967==    by 0x80493BD: mainloop (main.c:83)
==27967==    by 0x80493A5: main (main.c:68)

I was mystified by that first warning, as the function in question isn't all that big:

CRC32 crc32(CRC32 crc,const void *data,size_t size)
{
  const byte *p = data;

  while(size--)
  {
    crc = ((crc >> 8) & 0x00FFFFFF) ^ m_crc32_table[ (crc ^ *p++) & 0xFF ];
  }

  return(crc);
}

What could it possibly be complaining about? Only when investigating the second warning did I realize what the problem was—while I wasn't calculating the CRC over the entire structure, valgrind didn't know that. That explains the first two warnings. The third one deals with this bit of code:

for (i = j = 0 ; i < g_poolnum ; i++)
{
  /* other code */

  if (difftime(Tao,g_pool[i].atime) < c_timeout_gray)
  {
    g_pool[j++] = g_pool[i];
    continue;
  }

  /* rest of loop */
}

g_pool is an array of structures, and I'm using the C89 feature of structure assignment to avoid having to write memcpy(&g_pool[j++], &g_pool[i], sizeof(struct tuple)). But memcpy() (which is what the compiler changes the code to internally) has undefined semantics when the memory blocks overlap, and they do when i == j. This doesn't seem to cause a problem, but who knows?

I also found out that valgrind stops reporting errors after 100,000 are found:

==27967== More than 100000 total errors detected.  I'm not reporting any more.
==27967== Final error counts will be inaccurate.  Go fix your program!
==27967== Rerun with --error-limit=no to disable this cutoff.  Note
==27967== that errors may occur in your program without prior warning from
==27967== Valgrind, because errors are no longer being displayed.

Most of these deal with the child process created to save the state. I don't bother with cleaning up too much since upon calling _exit() all memory is reclaimed anyway, so I'm not terribly concerned about it. But I did lose two hours of testing to this.

Update on Tuesday, October 16¹⁶, 2007, 6 hours, 20 minutes and 9 seconds after starting the current test run of the greylist daemon

Bad news—it's still running.

You might think this is good news, but it's not. It means that the debugging conditions have changed the conditions the code runs under, so something very subtle is happening.

I did, however, make one small change to the code, clearing up two of the warnings mentioned above. I would hate to think that making that one small change fixed the program. If it's still running in the morning, then I'll run it again without valgrind and see if it works.

Sigh.

Tuesday, October 16, 2007

Heisenbugs … they're everywhere!

So I ran the greylist daemon for over eight hours under valgrind without it once hanging. I then restarted the server, this time running alone.

A few hours later, it hung.

And just for the record, when I normally attach to the running processing using gdb, it's where I would expect it to be:

(gdb) where
#0  0x008067a2 in _dl_sysinfo_int80 () from /lib/ld-linux.so.2
#1  0x003c2dd1 in recvfrom () from /lib/tls/libc.so.6
#2  0x08049411 in mainloop (sock=0) at src/main.c:88
#3  0x080493a6 in main (argc=1, argv=0xbfe5c084) at src/main.c:68

but when the process hangs:

(gdb) where
#0  0x00dff7a2 in _dl_sysinfo_int80 () from /lib/ld-linux.so.2
#1  0x00955e5e in __lll_mutex_lock_wait () from /lib/tls/libc.so.6
#2  0x008e7e4f in _L_mutex_lock_10231 () from /lib/tls/libc.so.6
#3  0x00000000 in ?? ()

I have no clue as to what's going on (and neither does gdb apparently). Running the program under valgrind obviously changes the environment, enough to mask the condition that causes the bug in the first place.

This is proving to be a very difficult bug to find.

Help! My compiler is leaking!

I fixed the problems that valgrind was complaining about in the greylist daemon (and I had hoped such problems would fix the problem, but alas, it doesn't seem to be the case, but I'm still testing), but the very nature of one of the complaints is interesting in and of itself.

A design pattern I've long used in code is the following:

/*--------------------------------------------
; the following is written to clarify 
; the issue I'm writing about.  This
; is not how I would normally write such 
; code.  It presents a simplified, yet
; realistic bit of code.
;
; And yes, this is the format I use for block
; comments in C.
;------------------------------------------*/

char   buffer[BUFSIZ];
size_t i;
size_t j;

for (i = j = 0 ; i < BUFSIZ ; i++)
{
  if (!isctrl(buffer[i]))
    buffer[j++] = buffer[i];
}

Basically, I'm going through a character array, removing certain elements (in this example, control characters) and doing so in place, to conserve memory consumption. Yes, there are instances where I'm reading and writing the same value to the same location, but in the scheme of things, it's not a bad thing. And, at least for this example, the overhead of trying to avoid unnecessary copying of data overwhelms the amount of time it takes to just do the copy.

So when I was writing the code to clean up the tuple array in the greylist daemon, I naturally wrote it as:

for (i = j = 0 ; i < g_poolnum ; i++)
{
  /* other code */

  if (difftime(Tao,g_pool[i].atime) < c_timeout_gray)
  {
    g_pool[j++] = g_pool[i];
    continue;
  }

  /* rest of loop */
}

It follows a successful pattern I've used plenty of times before. I saw nothing necessarily wrong with it, yet valgrind complained bitterly about this fragment of code. And I was a mildly surprised to see a call to memcpy() when I never explicitly called memcpy().

I just got bit with a leaky abstraction, and a rather insidious one at that.

Pre-ANSI C, I wouldn't have been able to write that code, since back then, C didn't have the concept of structure assignments, and thus, I would have had to explicitly call memcpy():

if (difftime(Tao,g_pool[i].atime) < c_timeout_gray)
{
  memcpy(&g_pool[j++],&g_pool[i],sizeof(struct tuple));
  continue;
}

But one of the advantages of working up the abstraction scale (so to speak) is that you can let the compiler take care of the grunt work for you. I mean, what if struct tuple was the size of an int? The overhead of calling memcpy() would swamp the actual act of copying the data. In fact, if struct tuple was a small multiple of an int in size, it might still not be worth the overhead of calling memcpy(). And the compiler is a better place to push such knowledge, since it can keep track of not only structure sizes, but the overhead of calling a function to copy memory and handle things accordingly.

So ANSI C allowed the compiler to handle structure assignment. And it can do a pretty fine job of it too. For instance, using a recent version of gcc with the compiler options -O3 -fomit-frame-pointer (some heavy duty optimization), it compiled the following bit of code:

struct foo
{
  int f;
};

struct foo A[256];
size_t     i;
size_t     j;
  
for (i = j = 0 ; i < 256 ; i++)
{
  if (A[i].f == 56)
    A[j++] = A[i];
}

to the following bit of x86 code (and frankly, I was surprised at the quality—and it's been translated from the alien AT&T syntax gcc uses to proper Intel syntax):

	xor	edx,edx
	xor	eax,eax
	jmps	.L6

.L4:	inc	eax
	cmp	eax,255
	ja	.L12   

.L6:	cmp	[A + eax*4],56
	jne	.L4
	inc	eax   

	mov	[A + edx*4],56	; A[j].f = 56
	inc	edx		; j++
	cmp	eax,255
	jbe	.L6 
                
.L12:

It didn't even copy the data since the compiler figured out it didn't need to. Even if we increased the size of the structure a bit:

struct foo
{
  size_t f;
  size_t f2;
  char   f3a;
  char   f3b;
  char   f3c;
  char   f3d;
  short  f4a;
  short  f4b;
};

struct foo A[256];
size_t     i;
size_t     j;
  
for (i = j = 0 ; i < 256 ; i++)
{
  if (A[i].f == 56)
    A[j++] = A[i];
}

gcc still has yet to call memcpy():

	push	ebx
	xor	edx,edx
	xor	ebx,ebx
	mov	ecx,255
	jmps	.L18   

.L16:	add	edx,16
	dec	ecx   
	js	.L23  

.L18:	cmp	[A + edx],56
	jne	.L16
     
	mov	[A + ebx],56		; A[j].f   = 56
	mov	eax,[A + 4 + edx]	; A[j].f2 = A[i].f2
	mov	[A + 4 + ebx],eax
	mov	eax,[A + 8 + edx]	; A[j].f3(a-d) = A[i].f3(a-d)
	mov	[A + 8 + ebx],eax
	mov	eax,[A + 12 + edx]	; A[j].f4(a,b) = A[i].f4(a,b)
	mov	[A + 12 + ebx],eax

	add	edx,16
	add	ebx,16
	dec	ecx   
	jns	.L18  

.L23:	pop	ebx

It just copies the 16 bytes of the structure as one assignment (because of constant propagation) and three four-byte moves. It's not until the structure gets significantly large:

struct foo
{
  size_t f;
  char   b1[124];
  size_t s2;
  char   b2[124];
};

struct foo A[256];
size_t     i;
size_t     j;

for (i = j = 0 ; i < 256 ; i++)
{
  if (A[i].f == 56)
    A[j++] = A[i];
}

that the compiler switches to calling memcpy():

	push	edi
	push	esi
	push	ebx
	xor	esi,esi
	mov	edi,offset A
	mov	ebx,255
	jmps	.L40

.L38:	add	esi,256
	dec	ebx
	js	.L45

.L40:	cmp	[A + esi],56
	jne	.L38
	push	ecx	; ???
	push	256
	lea	eax,[A + esi]
	mov	edx,edi
	push	eax
	push	edx
	call	memcpy
	add	edi,256
	add	esp,16
	add	esi,256
	dec	ebx
	jns	.L40

.L45:	pop	ebx
	pop	esi
	pop	edi

(The only anomaly in the code is the push ecx. The register isn't initialized, and memcpy() only takes three parameters, not four. My guess is that this “additional parameter” exists to keep the stack aligned along a cache line and it's this type of detail that compilers exist to keep track of. It's also interesting to note that when compiling for an 80486, gcc never bothers to call memcpy() and instead inlines the operation using REP MOVS.)

By now, you're probably asking yourself, “So? Where's the leaky abstraction?”

Well, the leaky abstraction comes in the call to memcpy(), which happened inherently.

Synopsis
#include <string.h>
void *memcpy(void *s1,void *s2,size_t n);
Description

The memcpy function copies n characters from the object pointed to by s2 into the object pointed to by s1. If copying takes place between objects that overlap, the behavior is undefined.

Returns

The memcpy function returns the value of s1.

The C Standard (emphasis added)

Well, how about that? I'm inadvertantly invoking undefined behavior in the greylist daemon! (actually, I was hoping this was the cause of the problem, but I don't think it is—sigh) Technically speaking, I don't see how there could be a problem when I'm copying a block of memory over itself, except for consuming some extra CPU time. But I would think that a compiler could see I was modifying an array of items, and either include a check to skip the operation if they overlapped completely, or switch to using memmove() (which allows the objects to overlap).

But such is the nature of working with high abstractions. When they leak, they leak!

I suppose I could have realized I was ultimately calling memcpy(), and that memcpy() has undefined semantics when the source and destination overlap, but I also expected the compiler to inline the code to copy the structure (much like gcc did when compiling on an 80486), not actually call memcpy()!

Sheesh.

Wednesday, October 17, 2007

Supreme being, or stinking rich?

“You see, to be quite frank Kevin, the fabric of the universe is far from perfect. It was a bit of a botch job you see. We only had seven days to make it. And that's where this comes in. This is the only map of all the holes. Well why repair them? Why not use 'em to get stinking rich?”

Randall—self-appointed leader of the time bandits

Hmm … stinking rich.

Evil: When I have the map, I will be free, and the world will be different, because I have understanding.

Robert: Uh, understanding of what, Master?

Evil: Digital watches. And soon I shall have understanding of video cassette recorders and car telephones. And when I have understanding of them, I shall have understanding of computers. And when I have understanding of computers, I shall be the Supreme Being!

Hmm … Supreme Being.

After consideration, once I get The Map (link via columbina) I'll go the stinking rich route. The food's better.

Maybe this time I'll get it

I think nailed that heisenbug in the greylist daemon. Given that it somehow ends up in the weeds (as a friend of mine used to say), I decided on a lark to delete all logging from the program.

Okay, it's not as insane as it sounds. The program supports logging to either syslogd or to stdout, selectable at runtime. To support this, I use a function pointer to store which logging routine to use (why I do this is a topic for another time). The functions themselves work very much like printf(), meaning they take a variable number of arguments and a format string describing the type of each argument.

The easiest way to test that particular hypothesis was to rip out that code (only on the production server).

Six hours later, it's still running, which is a very good sign.

I then audited the code, and yes, there were a few type mismatches and one instance of a mismatched number of parameters. Fixed those up, and restarted the greylist daemon.

Hopefully this will fix the problem.

Update a few hours later …

Thursday, October 18, 2007

Everything always works the first time on Star Trek

They always made it look so easy on Star Trek: The Next Generation.

The Enterprise (NCC-1701-D) is facing certain doom by the imminent implosion of a nearby nebula because the Thalaxians stole the warp core because they need it for a new face-lift technology that's a little less than enviromentally sound.

Wesley barges onto the bridge. “Hey guys! What if—”

“Get that kid off the bridge,” says Captain Jean-Luc “I'm a Shakespearian actor, not a ham” Picard, as he does his patented Picard Maneuver.

“But guys,” says Wesley, as he flips Worf onto his back and steps on his throat to prevent being forcibly removed from the bridge, “what if we were to reverse the tachyon field and reroute it through the shield generators to generate an anti-inertial damping field while simultaneously firing a photon torpedo loaded with an anti-matter implosion detonation device?”

“Why is that kid still—”

“And because we've generated an anti-inertial damping field outside the ship,” says Chief Engineer Geordi “Kunta ‘Reading Rainbow’ Kinte” La Forge, interrupting the ~~French~~ ~~British~~ ~~French~~ ~~British~~ (aw, the heck with it) stuffy shirt Captain.

“The force generated by the anti-matter implosion detonation device will push us,” says Lt. “Fully functional, if you know what I mean, and I think you do, wink wink nudge nudge say no more say no more” Data, as he's rapidly calculating something on the computer console in front of him, “into Warp two point seven eight.”

“Which is fast enough to get us out of range of the imminent implosion of a nearby nebula!” says Wesley, still holding down a struggling Worf. Captain ~~stuffy shirt~~ Picard looks momentarily confused as he quickly glances at all three expository spewing characters.

“And if we can place the photon torpedo loaded with the anti-matter implosion detonation device 22,453 kilometers at zero one five mark seven two, then we'll end up right next to the Thalaxian ship.”

“Make is so,” says Picard. “And hurry—we only have one more commercial break before the end of the show.”

And so, in twenty minutes, Wesley, Data and Geordi have managed to execute this complicated technobabblish plan flawlessly. On the first attempt. Based only on a hunch. Of a teenaged geek.

Ah, if only real life were as simple.

But I got the heisenbug nailed.

Latest statistics from the greylist daemon
Start	Wed Oct 17 23:48:32 2007
End	Thu Oct 18 17:01:55 2007
Running time	17h 13m 23s
IPs	117
Requests	3381
Requests-Cu	3
Tuples	1031
Graylisted	3240
Whitelisted	18
Graylist-Expired	2216
Whitelist-Expired	0

So, what was the fix?

It was a comment from Mark about signal handlers under Unix that lead the way.

Now, on to your bug. I would say 99% it is timing. Furthermore if I were a betting man I would say your bug rests within a signal handler. The only thing you can ever do inside a signal handler is set the value of a volatile sig_atomic_t variable really. Nothing else is safe.

That's pretty much how I wrote the signal handlers:

static volatile sig_atomic_t mf_sigint;
static volatile sig_atomic_t mf_sigquit;
static volatile sig_atomic_t mf_sigterm;
static volatile sig_atomic_t mf_sigpipe;
static volatile sig_atomic_t mf_sigalrm;
static volatile sig_atomic_t mf_sigusr1;
static volatile sig_atomic_t mf_sigusr2;
static volatile sig_atomic_t mf_sighup;

/**********************************************/

void sighandler_sigs(int sig)
{
  switch(sig)
  {
    case SIGINT   : mf_sigint   = 1; break;
    case SIGQUIT  : mf_sigquit  = 1; break;
    case SIGTERM  : mf_sigterm  = 1; break;
    case SIGPIPE  : mf_sigpipe  = 1; break;
    case SIGALRM  : mf_sigalrm  = 1; break;
    case SIGUSR1  : mf_sigusr1  = 1; break;
    case SIGUSR2  : mf_sigusr2  = 1; break;
    case SIGHUP   : mf_sighup   = 1; break;
    default: _exit(EXIT_FAILURE); /* because I'm stupid */
  }
}

/*************************************************/

void check_signals(void)
{
  if (mf_sigalrm)  handle_sigalrm();
  if (mf_sigint)   handle_sigint();
  if (mf_sigquit)  handle_sigquit();
  if (mf_sigterm)  handle_sigterm();
  if (mf_sigpipe)  handle_sigpipe();
  if (mf_sigusr1)  handle_sigusr1();
  if (mf_sigusr2)  handle_sigusr2();
  if (mf_sighup)   handle_sighup();
}

check_signals() is called during the main loop of the program; it's only sighandlers_sigs() that's called in a signal context. The only two signals that get (or rather, got) special treatment are SIGSEGV and SIGCHLD. The handler for SIGSEGV logs that it was called, unblocks any signals and re-executes itself.

The other signal is SIGCHLD. SIGCHLD is sent when a child process ends. It's then up to the parent process to call wait() (or one of its variants) to obtain the return code of the child process. If the parent doesn't do that, the child process becomes a zombie. The SIGCHLD signal handler called waitpid() (which is supposedly “safe” to call from a signal handler) as well as some logging routines. What may be happening (or was happening) is some very subtle race condition. The logging routine does allocate some memory (temporarily). The problem comes in if we're in the middle of allocating some memory when the program receives a SIGCHLD, at which point, we immediately enter the signal handler, which attempts (indirectly, through the logging routines) to allocate memory. But we were already in the memory allocation code when it got interrupted, thus leaving things in an undefined (or inconsistent) state.

I'll expound on what Mark said, and say that once you start dealing with signals, you're dealing with a multi-threaded application, and all the hurt that implies.

I rewrote the SIGCHLD handler to work like the other handlers (signal handler sets a flag, which is checked later from the main execution loop) and well, 17 hours later it's still running, on the virtual server, checkpointing itself every hour.

This only took, what? About a month to find?

But then again, I wasn't facing down the Thalaxians.

Friday, October 19, 2007

“You're programming it wrong.”

This function essentially sums all even integers from 0 to i inclusive. However, this function contains two tail calls, and what's worse as the function recurses those two tail calls are interleaved (in this case, the pattern of that interleaving is simple and easily determined in advance, but there is no reason why that would be the case in general). As far as I can see, this means that it is now impossible to record, or calculate, a full error report in the presence of tail calls in a static amount of stack space. The previous trick of recording a pointer is of little use, since every time tail recursion occurs via a different line of code than the previous call, then a new counter needs to be created pointing to the new tail call location: in the worst case, this will lead to exactly the same number of stack levels being recorded as in the unoptimized tail calling case.

Tail Call Optimization

The lack of a stack trace in tail calls is one reason to dislike them. But I dislike them for an entirely different reason.

Now, just to refresh your memory, a recursive function is a function that calls itself:

fib(i)
  if i = 0 
    return 0
  else 
    if i = 1 
      return 1
    else 
      return fib(i - 1) + fib(i - 2)
    end
  end

result = fib(10);

But recursion is expensive, as it requires aditional stack frames to handle (but it's the stack frames that make debugging easier if it's required). If the last thing a function does is call itself:

mult(a,b)
  if a = 1
    return b
  else
    return(a - 1,b+b)
  end

the compiler can turn this into a loop. And this space optimization (and that's what it is) is called `tail call optimization.” But it has to be of that form, where the last thing the routine does is call itself (and yes, the example mult() function above doesn't work for values of 0 or less, but this is an example).

fib2(i,current,next)
  if i = 0
    return current
  else
    return fib (i - 1,next,current + next)
  end

result = fib2(10,0,1);

But at that point, can you really consider it recursion? If the only way you get the benefit is to construct non-intuitive recursive functions that you can't even get a proper trace out of, isn't calling such an optimization “elegant” a polite fiction? Isn't the compiler there to take care of such details for me? Why should I be forced to write convoluted code to get decent performance? If I want that, I can code in C.

And that's my problem with tail call optimization.

Saturday, October 20, 2007

Some more musings on coroutines, plus a “proof-of-concept”

I spent today playing around with coroutines and how I might go about implementing them. My feeling is that with the upcoming push for multiprocessor systems, using some form of coroutines might make better use of such power, while at the same time being a bit easier to wrap the brain around instead of dealing with actual multithreaded programming.

My “ideal sample program,” which is a pseudo-C like language, looked like:

int main(string argv[])
{
  file input  = file.stdin;
  file output = file.stdout;
  
  switch(argv.items)
  {
    case 3: output = file.open.write(argv[2]);
    case 2: input  = file.open.read(argv[1]);
    default: break;
  }
  
  input => conversion(toupper)
        => strip_html
        => rot(13)
        => conversion(tolower)
        => rot(13)
        => output;
  exit(EXIT_SUCCESS);
}

/********************************************/

coroutine void conversion(char (*conv)(char))
        receive char c;
        send char;
{
  while(receive c)
    send conv(c);
}

/*********************************************/

coroutine void strip_html
        receive char c;
        send char;
{
  char c;
  bool in_tag = false;
  
  while(receive c)
  {
    if (c == '<')
      in_tag = true;
    else if (c == '>')
      in_tag = false;
    else
    {
      if (!in_tag)
        send c;
    }
  }
}

/******************************************/

coroutine void rot(int bias)
        receive char c;
        send char;
{
  while(receive c)
  {
    if (c.isupper)
    {
      c += bias;
      if (c > 'Z') c -= 26;
    }
    else if (c.islower)
    {
      c += bias;
      if (c > 'z') c -= 26;
    }
    
    send c;
  }
}

Why yes, the code in main() is reminiscent of the Unix command line. That's the intent. And on a uniprocessor machine, I suppose the code generated would be such that control would pass from one routine to another via some form of interprocedural goto (but hidden, much like the gotos are hidden in a while loop). And on a multiprocessor (or multicore) machine, you could create cheap threads and pipe the data between each coroutine.

And that's what my first prototype version did. This prototype is about three times longer, and uses pipes to transfer the data among the five threads that were created.

/*----------------------------------------------
; error checking removed to keep this example
; short.  It's already getting a bit silly
; in length, don't you think?
;---------------------------------------------*/

rc = pipe(p1);
rc = pipe(p2);
rc = pipe(p3);
rc = pipe(p4);

/*---------------------------------------------------
; the following is so I can avoid doing single byte
; calls to read() and write(), which will definitely
; destroy any performance gains we might get on a 
; multiprocessor system.  By wrapping these pipes in
; FILE *s, I automagically get buffering.
;
; Also, these structures contain the local data for
; each of the "coroutines" in this program,
; since I can only pass a single pointer to each.
;---------------------------------------------------*/

t1.fpin  = stdin;
t1.fpout = fdopen(p1[1],"w");
t2.fpin  = fdopen(p1[0],"r");
t2.fpout = fdopen(p2[1],"w");
t3.fpin  = fdopen(p2[0],"r");
t3.fpout = fdopen(p3[1],"w");
t4.fpin  = fdopen(p3[0],"r");
t4.fpout = fdopen(p4[1],"w");
t5.fpin  = fdopen(p4[0],"r");
t5.fpout = stdout;

rc = clone(conversion,&m_stack1[1022],FLAGS,&t1);
rc = clone(strip_html,&m_stack2[1022],FLAGS,&t2);
rc = clone(rot,       &m_stack3[1022],FLAGS,&t3);
rc = clone(conversion,&m_stack4[1022],FLAGS,&t4);
rc = clone(rot,       &m_stack5[1022],FLAGS,&t5);

while(1)
{
  child = waitpid(0,&status,0);
  if (child == -1)
  {
    if (errno == ECHILD) break;
    perror("waitpid()");
  }
}

Not only that, but there're plenty of places where things can break, although in my limited testing, things worked with very minimal error checking. I didn't bother to do any testing, this was more or less a “proof-of-concept” type thing.

I then thought of doing a second implemention, this time doing away with the pipes and seeing if I could somehow pass data directly between the “coroutines.” It required a bit of thought, and the solution I cooked up almost works (and I'll get to that in a bit).

The second version looks a bit like the first, only a bit less overhead since I don't have to create all the pipes:

/*-------------------------------------
; two extra threads are required for
; this version.  One to feed the file
; into the chain of coroutines, and one
; to accept the final data for the
; output file.
;--------------------------------------*/

t0.next = (struct parms_common *)&t1;
t1.next = (struct parms_common *)&t2;
t2.next = (struct parms_common *)&t3;
t3.next = (struct parms_common *)&t4;
t4.next = (struct parms_common *)&t5;
t5.next = (struct parms_common *)&t6;
t6.next = (struct parms_common *)&t0;

t0.pid = clone(INTERNA_input,  &m_stack0[1022],FLAGS,&t0);
t1.pid = clone(conversion,     &m_stack1[1022],FLAGS,&t1);
t2.pid = clone(strip_html,     &m_stack2[1022],FLAGS,&t2);
t3.pid = clone(rot,            &m_stack3[1022],FLAGS,&t3);
t4.pid = clone(conversion,     &m_stack4[1022],FLAGS,&t4);
t5.pid = clone(rot,            &m_stack5[1022],FLAGS,&t5);
t6.pid = clone(INTERNAL_output,&m_stack6[1022],FLAGS,&t6);

All the coroutines are linked together, and for the actual implementation, they all pause() (which stops the thread until a signal is received), and upon receiving a signal, process the data given to it (through a fixed location—you'll see in a second) and then signal the “coroutine” next in line before calling pause(). For instance, the conversion “coroutine”:

int conversion(void *arg)
{
  struct parms_conversion *parm = arg;
  int c;

  while(1)
  {
    pause();
    c = parm->c;

    /*--------------------------------------
    ; convert the data, and dump into the
    ; next coroutine's data block, then
    ; signal it that it can process the data.
    ;----------------------------------------*/

    parm->next->c = (*parm->conv)(c);
    kill(parm->next->pid,SIGCONT);

    /*-----------------------------------
    ; if we got an end-of-file marker,
    ; stop this thread.
    ;----------------------------------*/
    if (c == EOF)
      break;
  }
  _exit(EXIT_SUCCESS);
}

And it worked.

Mostly.

I was able to track the problem down to the stip_html() “coroutine”:

int strip_html(void *arg)
{
  struct parms_strip_html *parm = arg;
  int c;
  int in_tag = 0;

  while(1)
  {
    pause();
    c = parm->c;
    if (c == '<') { in_tag = 1; continue; }
    if (c == '>') { in_tag = 0; continue; }
    if (!in_tag)
    {
      parm->next->c = c;
      kill(parm->next->pid,SIGCONT);
    }
    if (c == EOF) break;
  }
  _exit(EXIT_SUCCESS);
}

It doesn't always trigger the next “coroutine” to run, which ultimately causes everything to grind to a halt. While I can hack this to work, it ultimately shows a rather critical failure on this method of implementing coroutines, in that any coroutine that doesn't send all the data it received further down the line will stop the entire chain.

And issues aside, it was about four times the code as the “ideal program.”

If anything, doing this exercise showed me two things. One, it's probably best to use pipes for “coroutines” under Unix. And two, the overhead in using “coroutines” is a bit frightening to do by hand. And it's frightening to think of all the bits that could fail. But is it worth worrying about? In Assembly it's easy to detect if some mathematical operation overflows (in fact, I haven't come across a CPU that doesn't detect overflow), but it's something I don't really concern myself with in C. Heck, in the first “proof-of-concept” I went with using fgetc() and fputc() which simply return EOF when anything bad happens. Sure, it simplifies the code, but it's hard to determine what went wrong when it goes wrong. Which is why I'm concerned: does abstraction scale?

More thoughts (now surfacing after writing all this): are coroutines really all that useful? I can see using them in mod_blog to simplify some code (mainly, formatting of entries) but in general, not much of the code I've written lends itself really to flow by coroutine. Perhaps it's that I don't have that particular tool in my toolchest and I've learned to work around it.

More pondering is required.

Sunday, October 21, 2007

Musings on four dimensional games

While surfing, I came across a mention of 3D chess, and for some reason, that triggered a memory from, oh, twenty-five years ago or so, where I was reading a gaming magazine (for physical, board-type games, not computer games) where they mentioned a board game involving Time Lords and the Fourth Dimension. I remember wanting that game, but a general lack of funds, and more importantly, a general lack of knowledge of where to get the game, left me imagining just how one could play a 2D board game dealing with time and/or the Fourth Dimension.

It was a curious memory indeed, and I decided to see if I could fish some more information out of this wonderful Intarwebs thang we have nowadays. With just that scant remembrance, I was able to locate the game in question. And not only read a review, but the actual rule sheets as well.

Sad to say, I'm glad I didn't get the game way back then. Cool concept, very poor execution. No time element at all, and a very poor concept of the Fourth Dimension as well (each piece can only move one space—optionally, you can move to a “time warp” and spend up to the next three moves to move two physical spaces on the baord—so much for a viable time warp).

But it did get me to thinking some. How could one design a game with time travel as a move? I remember playing a 4D chess variant, using a 4×4×4×4 board, which consisted of a large mat with 16 4×4 boards printed on it. Each column of boards represented a 4×4×4 volume, with four such “spaces” each representing a moment in time. As you moved your pieces (each side had four pieces, and trust me, that was hard enough) you left markers for each square visited. You could capture a piece by landing on any space with a marker, at which point, the trail of markers “past” that point were removed; of course, your piece could then be captured “earlier” in the game, at which point the captured piece captured by the captured piece was returned to the board at the point it was captured … um … does that make any sense?

Anyway, remembering that, I realized that we have these wonderful devices called “computers” that could keep track of all this stuff. Going back to a Time Lord game with actual “time travel,” the computer can keep track of every move, and allow one to move backwards through previous moves. I personally would restrict it such that you can't move a piece into the future (else what's keeping a player from hiding pieces way into future moves?) and you can't have more than one of any piece (so you can't keep moving your Time Lord piece back into the past and have an infinite army of Time Lords). I would also record the game so that afterwards, you can view in chronological time to see all the pieces wink into and out of existence.

It sounds like it would be horribly complicated, and the inner-geek in me would love to play such a game.

Monday, October 22, 2007

Oh yeah … that other place

Least you think I forgot about the other place, I just added a new entry about greylisting there, since it was a request from Smirk.

Friends don't let friends write signal handlers

Mark has a bit more to say about signal handlers:

From

Mark Grosberg <XXXXXXXXXXXXXXXXX>

To

sean@conman.org

Subject

Signal handlers.

Date

Mon, 22 Oct 2007 14:36:05 -0400 (EDT)

You know, now that I think about it even the write() system call is not totally safe in signal handlers. Why? Because lets say the write system call fails. Furthermore lets say that the signal was delivered somewhere in the return path of some other function, like, oh, I dunno, a socket I/O call.

So the socket I/O call has been performed and we are in the midst of unwinding through the various layers of libc and have set errno to some important value (like say HOST-NOT-REACHABLE) and then our signal handler attempts to write … poof our important errno value gets corrupted!

…

Amusingly from the man page for signal on my system:

Additionally, inside the signal handler it is also considered more safe to make a copy of the global variable errno and restore it before returning from the signal handler.

Too bad if you are in a threaded program “errno” is actually #defined as something like (*__pthreads_get_errno_location()). Hahah! You're so double-XXXXXX with this its not funny. Assuming that getting the errno location is atomic, is loading/storing errno? What if you have some goofy architecture where writes to errno are not atomic and require multiple instructions. That's why sig_atomic_t is so special … it's guaranteed atomic.

The fact that errno is a global variable is a consequence of the C language and it's rather poor support for multiple return values (it can—it's just that you have to pass in additional pointers). At the time, it was the easiest thing that could possibly work (I swear—at times, it feels like if it wasn't in Unix V7, then it doesn't really work that well under modern versions of Unix, like threads), not the best thing that could possibly work (like writing a systems language that supported multiple return values).

And the whole (*__pthreads_get_errno_location()) is telling—the C Standard requires that errno “expands to a modifiable lvalue”—in other words, it could be a pointer to a location which can be changed.

In fact, the C Standard on errno only covers half a page, and P. J. Plauger states in his book The Standard C Library:

If I had to identify one part of the C Standard that is uniformly disliked, I would not have to look far. Nobody likes errno or the machinery that it implies. I can't recall anybody defending this approach to error reporting, not in two dozen or more meetings of X3J11 [The ANSI working committee on standardizing C in the late 80s. —Editor], the committee that developed the C Standard. Several alternatives were proposed over the years. At least one faction favored simply discarding errno. Yet it endures.

The C Standard has even added to the existing machinery. The header <errno.h> is an invention of the committee. We wanted to have every function and data object in the library declared in some standard header. We gave errno its own standard header mostly to ghettoize it. We even added some words in the hope of clarifying a notoriously murky corner of the C language.

A continuing topic among groups working to extend and improve C is how to tame errno. Or how to get rid of it. The fact that no clear answer has emerged to date should tell you something. There are no easy answers when it comes to reporting and handling errors.

It's a rather depressing chapter to read, and P. J. Plauger is right—reporting and handling of errors is difficult reguardless of language.

But errno isn't the only problematic area with signals, so too might be pthreads, making a three-for-one clusterXXXX of your code.

Sigh.

Tuesday, October 23, 2007

Premature optimization

“We should forget about small efficiencies, say about 97% of the time. Premature optimization is the root of all evil.”

Knuth, Literate Programming, 1992, p28.

Nobody wants to argue with Knuth—it is the equivalent of arguing against the second law of thermodynamics. However, the problem here is that too often people misunderstand what Knuth was getting at.

Mature Optimization

I often feel as if the industry has gone off into collective insanity because of Knuth's quote, that concerns for programming efficiency are brushed aside because, well, optimization is eeeeeeeeeevil, people! Eeeeeeevil! (And if you really want to go down this rabbit hole, writing code is a form of premature optimization, because it's already been written. Even figuring out the problem is a form of premature optimization since someone already solved it.)

But the article points out that Knuth has been misquoted. Or rather, selectively quoted. The full quote from Knuth's book Literate Programming:

The improvement in speed from Example 2 to Example 2a is only about 12%, and many people would pronounce that insignificant. The conventional wisdom shared by many of today's software engineers calls for ignoring efficiency in the small; but I believe this is simply an overreaction to the abuses they see being practiced by penny-wise-and-pound-foolish programmers, who can't debug or maintain their “optimized” programs. In established engineering disciplines a 12% improvement, easily obtained, is never considered marginal; and I believe the same viewpoint should prevail in software engineering. Of course I wouldn't bother making such optimizations on a one-shot job, but when it's a question of preparing quality programs, I don't want to restrict myself to tools that deny me such efficiencies.

There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

Yet we should not pass up our opportunities in that critical 3%. A good programmmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code, but only after that code has been identified. It is often a mistake to make a priori judgments about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail.

Knuth, Literate Programming, 1992, p28.

Another article to read about this: The Fallacy of Premature Optimization.

Friends don't let friends code C++

As if the errno fiasco in C wasn't bad enough, not only does C++ inherit that mess, but it comes barreling down the road with a mess of more problems.

Sheesh.

Glad I'm not forced to use C++.

Wednesday, October 24, 2007

144 points of failure

I'm not even sure where to begin with this.

A customer is having a problem with duplicate emails being sent about a month after being initially sent, and it's causing the recipients to freak out (since they can't be bothered to check the date and see it's either a duplicate or a very late email message).

Our problem is obtaining the information we need to troubleshoot this problem. Our customer has no idea what “email headers” are (but then again, our customer has no idea what “a program” is or how she even checks her email) and doesn't want to bother the recipients with such details.

The real problem?

The sheer number of participants in exchanging an email between two parties. Between the two, in this case, are at least four operating systems (running on the customer's computer, our computer, the recipient's email server, and the recipient's computer), six networks (customer's local network, their ISP, our network, the network of the recipient's email server, the recipient's ISP, and the recipient's local network) across an unknown number of routers and at least six programs (customer's email client, incoming and outgoing mail daemons on our server, incoming mail daemon on recipient's server, the mailbox daemon on the recipient's email server, and the recipient's email client), any one of those could cause a minor problem that causes duplicate emails to be sent (and I'll spare you those details).

It's amazing that this crazy patchwork of servers, networks and software works at all, but boy, when it breaks, it breaks in very odd ways. I'm sure that the problem is understandable once we figure out what went wrong, but how to determine what went wrong? Especially after the fact?

Our log files don't go back that far, and what we do have is 10G worth (and due to how sendmail logs emails, an individual email at minimum generates three lines of logging information, and good luck in trying to piece all that together).

I think what I'm grousing about is my inability to fully troubleshoot the issue. The participants aren't necessarily technically inclined (which makes it difficult to get help from them, or even real solid information), and it involves more than just us. And somehow, it's our fault.

Oops. Gotta go. Yet another email issue to troubleshoot.

Now, where did I put my gun?

Thoughts on optimizing a greylist daemon

Speaking of optimization, I thought it might be fun to profile the greylist daemon. It's not difficult—just recompile the program with the appropriate compiler option and run it.

Now, when I wrote the greylist daemon, I did gave thought to how I was going to search through the vast amount of information, and wrote the code with that in mind (oooh, premature optimizations? Or was that a mature optimization?). I was also curious as to any hotspots in the code, as I tend to max out at 130 requests per second on my development server.

The results were a bit surprising:

Each sample counts as 0.01 seconds.
% time	cumulative seconds	self seconds	calls	self Ts/call	total Ts/calls	name
% time	cumulative seconds	self seconds	calls	self Ts/call	total Ts/calls	name
50.00	0.01	0.01	661477	0.00	0.00	tuple_cmp_ift
50.00	0.02	0.01	1	10.00	10.00	whitelist_dump_stream
0.00	0.02	0.00	140892	0.00	0.00	edomain_cmp
0.00	0.02	0.00	108648	0.00	0.00	crc32
0.00	0.02	0.00	95853	0.00	0.00	edomain_search
0.00	0.02	0.00	28270	0.00	0.00	StreamEOF
0.00	0.02	0.00	27439	0.00	0.00	report_stderr
0.00	0.02	0.00	27273	0.00	0.00	ipv4
0.00	0.02	0.00	27165	0.00	0.00	check_signals
0.00	0.02	0.00	27162	0.00	0.00	send_packet
0.00	0.02	0.00	27155	0.00	0.00	ip_match
0.00	0.02	0.00	27155	0.00	0.00	send_reply
0.00	0.02	0.00	27155	0.00	0.00	type_graylist
0.00	0.02	0.00	25458	0.00	0.00	tuple_search
0.00	0.02	0.00	24692	0.00	0.00	tuple_add
0.00	0.02	0.00	24692	0.00	0.00	tuple_allocate

The big surprise was that the execution time was split between two functions, tuple_cmp_ift() (which compares two tuples) and whitelist_dump_stream(), and the amusing bit is the disparity of the number of calls between the two, 661,477 calls to the former vs. the one call to the latter.

But in this case, the one call to whitelist_dump_stream() was made when the program ended (all it does is write out the tuples that have been whitelisted). Remove that from the program, and we pretty much have our hotspot—tuple_cmp_ift().

The other surprise is that there weren't any real surprises. The test data consists of 27,155 tuples with some duplicates, and you can see the various checks were called that many times. The only reason edomain_search() was called as many times as it was is that there are four lists that are checked 24,000 times each. crc32 is called twice for each packet (yes, that's intentional) so divide that by four (request and response) and it fits.

The code is pretty much even except for tuple_cmp_ift(), which is our obvious hotspot.

int tuple_cmp_ift(const void *left,const void *right)
{
  const struct tuple *l = left;
  const struct tuple *r = right;
  int                 rc;

  ddt(left   != NULL);          /* similar to assert() */
  ddt(right  != NULL);          /* but logs to syslogd */
  ddt(l->pad == 0xDECAFBAD); /* compiled out of profiled */
  ddt(r->pad == 0xDECAFBAD); /* code */

  /*-------------------------------
  ; sizeof(l->ip) is 16 bytes, enough
  ; space to hold an IPv6 address; not 
  ; that we use IPv6 currently, but planning
  ; for the future.
  ;------------------------------------------*/

  if ((rc = memcmp(l->ip,r->ip,sizeof(l->ip))) != 0) return(rc);

  if (l->fromsize < r->fromsize)
    return(-1);
  else if (l->fromsize > r->fromsize)
    return(1);

  if ((rc = memcmp(l->from,r->from,l->fromsize)) != 0) return(rc);

  if (l->tosize < r->tosize)
    return(-1);
  else if (l->tosize > r->tosize)
    return(1);

  rc = memcmp(l->to,r->to,l->tosize);
  return(rc);
}

Now, before I spend any time trying to optimize this bit of code, I thought I'd rerun the program without it. I changed tuple_search() (which calls tuple_cmp_ift()) to simply return “not found,” and I removed the call to whitelist_dump_stream(). The results were even more amusing:

Each sample counts as 0.01 seconds.
no time accumulated
% time	cumulative seconds	self seconds	calls	self Ts/call	total Ts/calls	name
% time	cumulative seconds	self seconds	calls	self Ts/call	total Ts/calls	name
0.00	0.00	0.00	140892	0.00	0.00	edomain_cmp
0.00	0.00	0.00	108668	0.00	0.00	crc32
0.00	0.00	0.00	95853	0.00	0.00	edomain_search
0.00	0.00	0.00	27438	0.00	0.00	report_stderr
0.00	0.00	0.00	27273	0.00	0.00	ipv4
0.00	0.00	0.00	27169	0.00	0.00	check_signals
0.00	0.00	0.00	27167	0.00	0.00	send_packet
0.00	0.00	0.00	27155	0.00	0.00	ip_match
0.00	0.00	0.00	27155	0.00	0.00	send_reply
0.00	0.00	0.00	27155	0.00	0.00	type_graylist
0.00	0.00	0.00	25458	0.00	0.00	tuple_add
0.00	0.00	0.00	25458	0.00	0.00	tuple_allocate
0.00	0.00	0.00	25458	0.00	0.00	tuple_search
0.00	0.00	0.00	3577	0.00	0.00	StreamEOF

Yeah, a lot of called functions, but not enough accumulated time to even survive rounding up.

I'm begining to think that the 130 requests per second limit I'm seeing isn't a function of the code, but of the network stack. Given this result, I doubt I'll bother optimizing tuple_cmp_ift() any time soon, which seems to re-enforce the whole “premature optimization is eeeeevil” thought, but in reality, I wrote the code around a few optimizations (namely, well considered data structures) in the beginning and didn't need to optimize it later.

Thursday, October 25, 2007

Ah, if only I had three cubic acres of coinage …

I'm such the Uncle Scrooge fan that I found this model of his money bin very cool! (link via spin the cat—thanks Jeff!)

Update a few minutes later …

So you're telling me that a duck who has 3 cubic acres of liquid assets and a XXXXXXX moon made of gold isn't the richest fictional character ever created?

Via Flutterby, Financial fan fiction from Forbes

Heh.

Friday, October 26, 2007

Some news on a greylist daemon implementation

I received some good news from Smirk—I can release the greylist daemon as open source. Now all that remains is to clean up the code, find a good name, and write a lot of documentation, pretty much in that order.

Monday, October 29, 2007

“His brain is gone!”

Of all the episodes of Star Trek: The Original Series, of course the only one to make it to the stage is “Spock's Brain” (link via Mike Sterling).

No, really!

Notes on stress testing a greylist daemon

I spent the weekend cleaning up the code to the greylist daemon, in preparation to releasing it. Good thing too, because I've found lots of little details, a missed call to free() here, the wrong constant used there (it didn't matter before the cleanup, afterwards, with some stuff changed, it did), and not updating some statistical information correctly.

Little details like that.

The only big change was the ability to add and remove tuples using the master control program. A nice side effect of that effort, you can now see how a tuple will be handled by the greylist daemon.

The other change is the way I handle stress testing. As a side issue about a parallel quicksort implementation, it was pointed out that the data I collected was bogus, and that I should be handling more requests than I am.

I got to thinking, and it may be that my current stress testing isn't stressful enough.

So I wrote a new stress test. This is basically two programs. The first reads through a list of tuples and generates all the packets, but saves them to a file. The second program maps this file into memory and then sends each packet, one after the other, to the greylist daemon.

My, what a difference.

The initial test was on an old 120MHz machine. The previous stress test capped out at 77 requests per second. The new stress test capped out at 381 requests per second without a dropped packet (another test, this time the stress test program didn't bother waiting for a reply, managed to send 1700 packets a second—the greylist daemon could only handle 385 per second, and obviously dropped a bunch of packets).

Not bad for a 120MHz machine.

It sounds more like a trip through hell to me …

This one is for Gregory, who likes to travel via motocycle: Angola by Motocycle (link via Flutterby).

Tuesday, October 30, 2007

More thoughts on optimizing a greylist daemon

I ran the updated stress test on a faster (2.6GHz machine) and managed to get some impressive results.

There were three different ways I ran the test. One option had the stress program send a request and wait for a reply. This was by far the slowest of the tests, but the most reliable (in terms of actually processing every request) with the greylist daemon handling between 4,000 to 6,300 tuples per second. Another option has a separate process waiting for the replies and that goes faster, between 11,000 and 17,000 tuples per second, but drops a ton of requests (on the order of 70%). The last option doesn't even bother with replies. This does both the best and the worst—30,000 tuples per second, but it drops something like 90%.

So, the program can easily handle about 5,000 requests per second on a nice server, which is probably way more than most SMTP servers can handle (and it's much nicer than the 130/second I thought it could handle).

I profiled the program again, and this time, got actual results I could use:

Each sample counts as 0.01 seconds.
% time	cumulative seconds	self seconds	calls	self Ts/call	total Ts/calls	name
% time	cumulative seconds	self seconds	calls	self Ts/call	total Ts/calls	name
21.24	0.48	0.48	2260060	0.00	0.00	crc32
14.38	0.81	0.33	443203	0.00	0.00	tuple_search
11.51	1.07	0.26	565012	0.00	0.00	ip_match
8.85	1.27	0.20	565012	0.00	0.00	type_graylist
7.97	1.45	0.18	1	0.18	2.20	mainloop
6.64	1.60	0.15	565015	0.00	0.00	send_packet
4.87	1.71	0.11	7648182	0.00	0.00	tuple_cmp_ift
4.87	1.82	0.11	565012	0.00	0.00	graylist_sanitize_req
3.98	1.91	0.09	1761756	0.00	0.00	edomain_search
3.54	1.99	0.08	2637054	0.00	0.00	edomain_cmp
3.10	2.06	0.07	421359	0.00	0.00	tuple_add
2.21	2.11	0.05	565012	0.00	0.00	send_reply
2.21	2.16	0.05	1	0.05	0.05	whitelist_dump_stream
0.89	2.18	0.02	565127	0.00	0.00	ipv4

Again, nothing terribly surprising here, except for the code gcc generated for the crc32() function (two lines of C code, one of which is while(size--)), but I used the default compiler settings; if it really bothers me, I can up the compiler settings and see what I get.

And so begins Edward George Bulwer-Lytton's Paul Clifford, as wretched a novel as existed, and it described tonight fairly well as I took The Kids trick-or-treating. The wind was so violent that it constantly inverted my umbrella and in the end, I gave up on using it.

And The Kids scored some 11 pounds of candy this year.

Unfortunately for me, they're not leaving for their Father's tomorrow …

Sigh.

Updated on Tuesday, October 9th, 2007

Update a few minutes later

Update on Tuesday, October 1616, 2007, 6 hours, 20 minutes and 9 seconds after starting the current test run of the greylist daemon

Synopsis

Description

Returns

Update a few hours later …

Update a few minutes later …

Obligatory Picture

Obligatory Contact Info

Obligatory Feeds

Obligatory Links

Obligatory Miscellaneous

Obligatory AI Disclaimer

Updated on Tuesday, October 9^th, 2007

Update on Tuesday, October 16¹⁶, 2007, 6 hours, 20 minutes and 9 seconds after starting the current test run of the greylist daemon