mgrier's WebLog

Transactions and in-memory data (part 1 of n)

[Maybe I'll fill in the "n" when I'm done.  I haven't had time to plan out the entire series...]

In yesterday's post, I covered basically two approaches towards how to achieve transactionality.  One is to build up a log of what to do when the commit is requested and the other is to keep track of what you have to undo if a failure or rollback occurs.

Astute readers will recognize that the first case doesn't actually solve The Big Problem of persistence and transactionality which is that you need a guaranteed way to go backwards once you've started making changes to persisted state.  There's no guarantee in the world that the "n" I/Os required to apply the changes will wholly succeed.

I haven't followed up on verifying my claim that a major database did do this but you can see that (a) it does solve the problem for voluntary rollback and (b) if you're careful and allocate space before making any dangerous changes you can see that the only damaging failure modes are basically hardware failure or excessive system stress.  For the latter, you might notice that a wide variety of databases more-or-less assume that they own the system while they're running and their installation guides probably highly recommend that you not run anything else on the hardware so the likelyhood of a failure to write due to lack of kernel mode address space or something is pretty low.

This technique also has some real advantages over the other approach.  For one, since all changes are buffered in memory, if you are going to update a value repeatedly in the context of the transaction, you are only modifying the in-memory image.  Also, subsequent reads can be guaranteed to be satisfied from memory.  Once you start worrying about concurrency, you might find that you want to capture state that you even just read from the persistent store in memory.  If you're on dedicated hardware and have the physical resources, hey maybe this is a huge perf win!  At the same time, the amount of physical memory to back the state can grow (if you're reliant on pagefile to back the state you (probably) have no perf advantage over having written the data back to the file in the first place) excessively so if you support concurrent transactions you can get into trouble if you give each transaction an arbitrary write-back quota.

So that's interesting but let's map it back into the in-memory problem that I'm focussing on.  If you have no in-memory state and you can leverage the great work done by database vendors there's a lot you can leverage.  But like I said, for a lot of business-critical code you can't do this - imagine that every keystroke in your word processor turned into a database transaction. It's just a non-starter.

It seems that there are three ways you could approach achieving this:

1. Go the "functional" route where the buffered state is a complete copy of whatever networks of objects you are trying to modify in memory
2. Build all your data structures so that they have a way to participate in an "apply log" where they do the hard work (comparisons, allocations etc.) up front but don't change anything until you commit
3. Somehow play this same game at the memory access level

1. Functional Route

This clearly doesn't scale.  If you have a large graph of objects that you're making changes to, you can't really imagine making a copy of the entire graph for every operation.

2. Defer updates into a commit-time log

This is really tricky.  Consider a binary tree implementation.  In the insert() function you'd have to allocate the memory for the new node, record where it would go and stash away enough state so that you could commit the change.  Well that part doesn't sound hard but now consider that reads against the mutated but uncommitted state must be satisfied against the log.  Tomorrow when I discuss the other approach (make changes, allowing for nofail rollback) hopefully it will be obvious that this is much much harder to get right.

3. Memory access level

Yeah right.  Research topic for someone to use to get their Ph. D. and then eventually productize it 30 years later when the hardware and compilers are at the point that it's feasible.  Basically the same pattern as GC has had. :-)

My general conclusion: while there are some compelling benefits to this pattern (rollback is easy!), for general purpose usage it's very hard to get right.

No Chinese Dictionaries

I want to go on the record and note that I will not be deveoping a Chinese/English Dictionary, in unmanaged code, managed code or any code (pages).

More than one way to skin a (transactional) cat

Let's briefly look at how databases deal with transaction rollback.  I'm going to ignore a lot of other fun stuff around locking protocols, snapshots, isolation etc. and only focus on how atomicity & durability are achieved.  I'll keep the conversation in the realm of traditional database objects: tables and rows.

Approach 1: Buffer everything until it's time

[caveat: this solution smells like "be functional and then do nofail swap()" but since we're dealing with persistent data and real hard drives, there typically isn't a "nofail swap" type of thing]

The started/created transaction object maintains a list of all of the proposed changes to the long-lived system.  You maintain some in-memory model of the whole database.  Presumably you only have to keep deltas in memory and reads which aren't satisfied by the deltas are issued against the underlying persistent store.

When you go to commit the transaction you build a nice compact queue of operations and you run them really quickly and hope that the system doesn't crash and that the hard drive doesn't develop bad sectors right then.  Hmmm... I guess that's not transactional.  I guess instead I keep a log somewhere and for each item in the queue I'm going to do, I read the current state of the database and save it in the log before making the change.  When I'm done I write a special entry at the end of the log saying that I'm done and that the previous entries don't actually have to be used to roll back the state.

In this approach, aborting the transaction is trivial - you just drop the in memory buffer.

You could try the functional game by instead writing out a new database and then using a hypothesized atomic swap filesystem operation (which is allowed to fail) for the commit.  Probably doesn't scale too well.  :-)

Approach 2: Make changes allowing for rollback

[this is how many/most databases work.  Interestingly at least one high-profile database operates(operated) in the other mode and only developed persistent journalling/crash recovery relatively late in its lifespan...  I'll double check this anecdote before I'll name the database.]

The started/created transaction gets a unique ID and changes to the database are reflected directly into the persistent store, with the exception that the before-image of each record is written to the log under the txn id.  When the txn is committed by the client, an entry it written to the log marking the txn as committed.

In this model, rollback is nontrivial since you have to go backwards through the log finding the undo state for the changes made and move things back.  Since you can't fail rollback (hmm.... sounds familliar) you have to had been sure not to do things like reorganize/compress database pages too much while making the changes.  Maybe the rollback records are just whole pages if your concurrency locking granularity is a page.

---

At some level, both are the same; it's just a matter of how you spread out your impact and I/Os.  There are also fun topics around concurrency, isolation and guaranteed forward progress when there are concurrent transactions.

I'll summarize the models:

1. Buffer up all your changes so you don't make the first real change until you're sure you're done

2. Make your changes but ensure that you can roll them back without requiring a major amount of resources

Disk I/Os can and do fail whether due to lack of kernel resources, cosmic rays, disk controller failure, disk failure etc. etc. etc.  So what's really important is being able to apply the roll back logs for uncommitted transactions in the case of catestrophic failure, ... and! .. turning any failure which might result in the database being corrupt or the log records not getting written into a catestropic failure (e.g. bugcheck()).

Can we apply some of those techniques for in-memory structures?  At what cost?

Implementation patterns to support transactional functions

Let's go back now to why I had a hard time with using the STL std::map pattern.  It was because for the primary failure-prone access pattern (insert), there is an inverse operation which could not fail.

A common pattern in TxFn (sorry I can't keep writing the long name) is that you carefully do all your may-fail work and then you finish up with a series of statements which have no opportunity for failure.  The key is that all of the may-fail work has to either (a) not be an ESE or (b) be reversible.

To not be an ESE you can act in a "functional" manner - that is, rather than mutating some state, we can create a whole new copy of the state.  Then our caller would  wait until they're past the critical last point of failure and use a pattern like "nofail" swap() to then switch the new state into place.  This is just passing the buck, we may not be an ESE since we're functional but our parent still is an ESE and has to only use "functional" methods (which of course then means that even though this one function could be a TxFn, the caller would have to solve the probelm unless you're functional "all the way through").

This sounds good but when your state is a network of interrelated objects, it doesn't work.

Interestingly I just came across: http://www.paulgrenyer.dyndns.org/cppstyle/items.php#item12 whch basically opens a discussion of these same topics but unlike fun topics that everyone wants to debate like does snprintf() suck eggs, it delivers some guidance and then wanders away looking again for another pithy topic that might garner some talk show circuits or DDJ articles.  (This series would never get a DDJ article: "hey you jokers, fancy-pants new languages don't solve all your problems for you - you still have to write good code!  And the new languages aren't making it any easier!".)

Asides aside, this leaves us in the position of requiring that every (T)ESE which can be composed into a larger scoped operation be paired with a "nofail" partner.  There appears to be a fun exception to this which is that if you have one ESE operation which doesn't have a nofail inverse, you could do it as the last "mayfail" operation.  But then you're stuck unless the function that did this careful sequencing was main().

[mgrier: edited 5/10/05 to fix some wording around the functional pattern.  I accidently switched contexts between what the support code could do (act functional) and what the caller might do (build up state using functional metaphors and then use a nofail swap() type of thing).]

Local vs. global analysis revisited

I posted that last item before having my coffee so it's really not suprising that I forgot to get around to my point.

My point is this: there are abundant tools (including the human brain) which are good at local analysis.  Global analysis is hard; this is why people with "architect" in their title tend to be stronger, broader thinkers than the rest of us people who "just" focus on shipping software.  Global analysis of the correct behavior of a piece of software is hard.  Factoring in the effect of minor local defects to the global behavior of a system is much much harder.

Almost any cost in order to convert a global correctness problem into a local correctness problem is valuable beyond your wildest dreams when you're trying to ship medium-to-large software systems.

Thus this continuing series.  People can't see their bugs any more.  Tools can't find them either.  We need to fix that.  If the belief that writing simple code should be simple is false, we need to communicate that.  If we need to make the statement true, we need to fix the tools and techniques we're applying so that you don't need the brain the size of a planet to understand all of the cascading failure modes in large long-lived software systems.

Whole program vs. local analysis

A quick note for today. Maybe more tonight.

Internally at Microsoft, as you can imagine, we have a number of tools to assist building our software.  Many are internal-only; contrary to the black-helicopter gang out there, there is a lot of cost to shipping software and it can divert your attention and resources from your primary goal of making your teams' code faster/better/whatever.

I won't divulge the details or identity of any of these tools; I'm sure you can references to all of them if you cover the MSFT blogosphere.  Let's call one of them "mega-lint".

Some people have never seen the need for a tool like lint; that's what the compiler is for, right?  The problem is that as I have alluded to several times now, compilers are all about syntax and translation semantics; their goal up to now has been to let you express your ideas more fluidly, not necessarily with better intent.

In previous example where the void reverse_array() function was calling member functions/operators on a type, on one hand it was "obvious" that they would succeed but on the other hand if you want to look at the contract long and hard, it's actually not obvious that they might succeed.  Consider, for example, a language/runtime environment where the use of operator[] was remoted (auto-remoted interfaces are problematic and will be a topic of several entries later on).  The "obviousness" that the only failure modes were covered due to our working within the documented limits of the array are now questionable.  Sorry to lapse into C++ for a bit but consider if the signature of reverse_array() had been:

template <typename T> void reverse_array(T &array) { ... }

Sure std::vector may give you some sort of guarantee, but given the requirements (existence of a size() member function and implementation of operator []), you had better code your template to deal with exceptions being thrown (a/k/a errors being returned) by all of those cases.  I had to invoke C++ here because the C equivalent of a macro would be somewhat uncompelling and I'm not familliar with Java and CLR generics enough to say whether the error contract for the members can be explicitly called out.

Back to the point.  There's no way to declare that we don't expect operator[] to fail as long as we pass in legal bounds.  (consider a sparse array implementation which may have to dynamically allocate the element on first access...)

How do we even figure out that there is a problem there?  Should all code just always write the try/catch blocks?  Probably not!  The main claim to fame for exception handling is that you should write less code, not more.  But then someone with a try/catch up higher on the stack is probably not expecting to catch the silly operator [] failure.

This kind of problem is impossible to diagnose without either massive simulation tools which can do whole program analysis and simulation or, and this is my preference, reducing the problem to be a more local one about contract description and local analysis.

Local analysis is much easier since it's what every programmer does when reading code.  Now, we've been trained badly; either there are APIs which, by convention, you ignore their failure status (fclose, fprintf, etc.) or there are new patterns building up where you have a try/catch block around a function where you catch all errors and rethrow a different exception.  Both of these inhibit easy local analysis and both patterns must be stopped if we're going to make progress in making software more reliable.

Usual caveat applies: People writing actual applications instead of reusable libraries can dial this setting pretty much wherever they want to.  Shared code authors should be very aware of this problem and the "v1" people out there (you know them, the ones who have a cool idea, get the awards and good bonuses and then move on to the next v1 project leaving their path of destruction a mile wide behind them...) need to get some discipline.

Working with inexact error contracts

Last time I lamented that the fact that std::map::erase() is not permitted to fail made it hard to come up with an example.

But the vector pattern has the basic problem I wanted to discuss.  First I'll write the obviously correct C code and then we'll see how it translates into a world where you're using helper types/functions instead of plain ol' C arrays.

void reverse_array(size_t count, int array[]) {
   size_t i, j;
   i = 0;
   j = count;
   while (i < j) {
      j--;
      int t = array[i];
      array[i] = array[j];
      array[j] = t;
      i++;
   }
}

Pretty simple, right?  Now let's use some helpers and see how much it helps.

int reverse_array(vector_t *array) {
   int err; // hey, what's going on?  Why do we need this?
   size_t count, i, j;
   vector_get_size(array, &count);
   i = 0;
   j = count;
   while (i < j) {
      int t, t1;
      j--;
      // let's do a literal transcription here of what we would do if we used operator []
      // from any of the popular class libraries.
      if ((err = vector_get_at(array, i, &t)) != 0) return err;
      if ((err = vector_get_at(array, j, &t1)) != 0) return err;
      if ((err = vector_put_at(array, i, t1)) != 0) return err;
      if ((err = vector_put_at(array, j, t)) != 0) return err;
      i++;
   }
   return 0;
}

Pretty darned non-transactional, eh?  A trivial transformation to remove some of the failure modes would be to capture the array indexing once each for i and j and then just have a few pointer dereferences...

int reverse_array(vector_t *array) {
   int err; // hey, what's going on?  Why do we need this?
   size_t count, i, j;
   vector_get_size(array, &count);
   i = 0;
   j = count;
   while (i < j) {
      int t;
      int *pi, *pj;
      j--;
      if ((err = vector_at(array, i, &pi)) != 0) return err;
      if ((err = vector_at(array, j, &pj)) != 0) return err;
      t = *pi; *pi = *pj; *pj = t;
      i++;
   }
   return 0;
}

But if we're going to go that far, we can just get the array pointer from the vector:

void reverse_array(vector_t *array) {
   size_t i, j, count;
   int *elements;
   vector_get_size(array, &count);
   vector_get_array(array, &elements);
   i = 0;
   j = count;
   while (i < j) {
      j--;
      int t = elements[i];
      elements[i] = elements[j];
      elements[j] = t;
      i++;
   }
}

Woah.  Hey, it doesn't fail any more, does it?  But who write the code this way?  Consider the C++ equivalent; something like (yes, someone better might use iterators but I'm not one with the zen of STL... at least I recognize my naivety which I doubt most people would)

void reverse_array(std::vector<int> &array) {
   size_t i, j;
   i = 0;
   j = array.size();
   while (i < j) {
      j--;
      int t = array[i];
      array[i] = array[j];
      array[j] = t;
      i++;
   }
}

How do you feel about that?  What exactly is the contract for the indexing operator in various class libraries?  The STL contract seems to indicate that the results of operator [] are defined when the index is between 0 and size-1; maybe this is correct.  Since the CLR makes no restrictions on the failure contract for functions, you have to assume they can fail.  Java seems to appropriately lock down the array access failures; they go beyond the STL contract to specifically call out that an IndexOutOfBoundsException is raised.  (You can debate which contract is better...)

Maybe the happy translation is:

void reverse_array(vector_t *array) {
   size_t count, i, j;
   vector_get_size(array, &count);
   i = 0;
   j = count;
   while (i < j) {
      int t;
      int *pi, *pj;
      j--;
      if ((err = vector_at(array, i, &pi)) != 0) bugcheck(err);
      if ((err = vector_at(array, j, &pj)) != 0) bugcheck(err);
      t = *pi; *pi = *pj; *pj = t;
      i++;
   }
   return 0;
}

Paranoia?  Good engineering?  I've been focussing on writing the code in C; writing in other languages can make the algorithm look simpler but hides a lot.

A few key points to note:

• The old fashioned code has no obvious failure modes.  (Of course the hardware can fail but hey what are you going to do about this?)
• Fancy new languages are hiding a lot of failure points
• What's the contract of the reverse_array() function?  Can it fail or not?  Should try { } catch(...) { bugcheck(); } be added?

Even good design can't succeed in isolation

I tried three times to write yesterday's entry which was intended to explore the same problems with trying to restore invariants in failure paths.  Instead I kept getting fouled up because the collections I was using were based on the STL design.  The STL designers actually did a good job in making it hard to recreate the problem I wanted to exhibit.

But instead I had to create artificially complex examples to avoid going outside the STL design patterns.  But there are problems due to the STL design which form a typical problem when trying to build reliability out of lower layers which are not conducive to it.  Much like the example of close(2) possibly failing for environmental reasons, they are just following a well established pattern of "when in doubt, return an error".

The particular case is the fact that the std::map::erase() overloads are documented not to fail, including the overload that takes a const key_type & reference (which must therefore also invoke comparisons between the key passed in and the key in the elements in the map).  This is a smart contract and we all know that strcmp() can't fail (usual caveat: except for bad parameters and in this case the failure is as catestrophic as we could hope for).

But humans aren't that interested in the kinds of comparisons that strcmp/wcscmp do; they want to do several standard things like ignore case or apply linguistic collation algorithms.  The key issue here is that for anything but these trivial byte-wise type comparisons, the comparison can have 4 results: a == b, a < b, a > b or failure.  A good example of such a string comparison API is the CompareString() API in Windows (http://msdn.microsoft.com/library/default.asp?url=/library/en-us/winui/winui/windowsuserinterface/resources/strings/stringreference/stringfunctions/comparestring.asp).

How can I be good and use a useful string comparison function and play into this pattern?  Let's write some code and see what it might look like.

int are_equal_case_insensitive(const wchar_t s1[], const wchar_t s2[]) {
   int comparisonResult;
   int err;
   if ((err = compare_string(CASE_INSENSITIVE, s1, s2, &comparisonResult)) != 0) {
      // We'll just "play it safe" and say that they're not equal
      return 0;
   }
   return (comparisonResult == 0);
}

Was that really playing it safe?  I guess we couldn't prove they were equal, but we also didn't prove that they're not equal either.  I didn't bother trying to loop like I did in the other examples when the error is ENOMEM; I'll address why that isn't really a good idea anyways later.  I guess the answer is:

int are_equal_case_insensitive(const wchar_t s1[], const wchar_t s2[]) {
   int comparisonResult;
   int err;
   if ((err = compare_string(CASE_INSENSITIVE, s1, s2, &comparisonResult)) != 0) {
      // We'll just "play it safe" and say that they're not equal
      bugcheck(err);
   }
   return (comparisonResult == 0);
}

bugcheck() is a function that would force a memory dump and then terminate the process with a failure exit code.

Is that a good solution or a bad solution?  It did seem pretty drastic but at the same time I converted a potential privilege escalation attack into a denial of service (DOS) attack.  DOS attacks are bad but not as bad as letting someone take advantage of inconsistent global state in your process.  At the same time, most managers may not feel like taking the high road here when it turns out that someone can crash the service process just by typing an unusual set of characters into some field in a data entry form.

If you don't believe this, look for all the code in Java and C# that just swallows exceptions because a "crashing" bug was reported against the app.

The point of this post is that we're going to see that it's really hard to engineer solid solutions if your framework doesn't provide you good solid guarantees.  STL actually sets a good example here, but the problem is that a good example that's in the middle of the conceptual stack can actually cause more mess than it cleans up.

My original problem I was going to talk about is because our collection classes, while modelled after the STL designs, allow erase() to fail because the key comparisons may fail.  This gets you into a real bind when you can't guarantee forward nor backwards progress.  The checked in code right now is chicken and leaves the global state torn.  I plan to fix it and we'll talk about what lengths we might have to go to in order to fix it when the normal operations don't have any guarantees of forward progress.

Why is fclose()'s contract so confusing?

Because it’s a long established pattern and contract, let’s explore fclose() today.

Here’s my ideal fclose() implementation:

int fclose(FILE *fp) {
   close(fp->fd);
   free(fp);
   return 0;
}

But of course close() can fail.  Yuck.  I found this man page on close(2) on the web; maybe it doesn’t represent the modern/common close definition but even in my idealized world, the implementation of fclose() has to be something more like:

int fclose(FILE *fp) {
   while (close(fp->fd) == -1) {
      if (errno != EINTR) {
         return EOF;
      }
   }
   free(fp);
   return 0;
}

I picked on EINTR to loop on here because the man page for close() calls it out as a condition (without mentioning whether there are or are not un-rolled-back side effects).  By my reading I assume that it means that the close() was not able to complete.  If the I/O wasn’t able to complete and I don’t get a chance to retry it, this would seem to be a very fundamental break in the I/O API design so I’ll assume that it has the contract I believe (a case of Raymond’s “What would happen if the opposite were true” analysis technique).

Notice also that something very important happened here.  There’s an implicit contract in close()-type functions which is that regardless of “success” or “failure” the resource will nonetheless be freed.

But we didn’t deallocate the FILE!  Maybe the right implementation was:

int fclose(FILE *fp) {
   int fd = fp->fd;
   free(fp);
   while (close(fd) == -1) {
      if (errno != EINTR) {
         return EOF;
      }
   }
   return 0;
}

Is this right?  Probably not; if we’re going to return an error like ENOSPC, callers need to be able to retry the operation.

The simple answer is that the close() pattern is a very special contract.  Nobody’s actually going to sit in a loop calling it.  It must deallocate/free the resources.  If the state of the address space/process is trashed, you might as well kill the process (ideally tying in with a just-in-time debugging or post-mortem-dump debugging mechanism).

But even my totally idealized fclose() implementation is unrealistically simple.  These are the buffered file I/O functions in the C run time library.  Since people are too lazy to call fflush(), the real implementation has to look something like this:

int fclose(FILE *fp) {
   if (fp->bufpos != 0) {
      const void *buf = fp->buf;
      size_t bytestowrite = fp->bufpos;
      while (bytestowrite != 0) {
         ssize_t BytesWritten = write(fp->fd, buf, bytestowrite);
         // -1 is error; otherwise it’s number of bytes written??
         if (BytesWritten == -1) {
            // what the heck am I going to do now?  Holy crud look
            // at all the error codes in the man page!  Am I really
            // going to try to figure out which of those are
            // retry-able?
            // I guess I’ll just cut and run
            return EOF;
         }
         // docs for write(2) don’t say that successful writes will
         // have written all the bytes.  Let’s hope some did!
         // but wait, what if, say -2 is returned?  What if I asked for
         // more bytes to be written than ssize_t can represent as
         // a positive number?  The docs don’t say; chances are the
         // implementation is naïve but it seems wrong to second guess
         // the apparently intentional use of ssize_t instead of
         // size_t for the return type.
         assert(BytesWritten >= 0); // do you sleep better with this?
         bytestowrite -= BytesWritten;
         buf = (const void *) (((size_t) buf) + BytesWritten);
      }
   }
   while (close(fp->fd) == -1) {
      if (errno != EINTR) {
         return EOF;
      }
   }
   free(fp); // at least free is void!! Phew!
   return EOF;
}

My point here is not to lambaste the U*ix syscall APIs in particular; they’re just one in a long line of badly designed contracts.  Deep down, CloseHandle() has a similar loop inside it because just one last IRP has to be issued to the file object and if the IRP can’t be allocated the code loops.  Arguably the IRP should have been allocated up front but people have a hard time stomaching such costs.

What I’m really trying to show is how you can design yourself into a corner.  The C buffered stream functions did this on two axis simultaneously.  The fclose() function has to try to issue writes to flush the buffer.  (Yes, it probably would have called fflush() but since fflush() doesn’t guarantee forward progress, presumably the calls to fflush() would also have to be in a loop.)  The underlying I/O implementation is fallaciously documented – that is it tried to look like it did due diligence in documenting all the things that can go wrong but even with a mature man page on a mature API, there’s no real clue left behind about what to do about these conditions.

The real point here is that rundown protocols don’t get enough attention.  I’m sure that someone thought that the design for close(2) was great.  There’s tons and tons of information about what errors you can get back!  But, in essence its contract isn’t very usable.  The C run time function fclose() has it even worse since nobody trained people to call fflush() if they really want their data written to disk.

The key that should be showing up is this:

Code that is executed in resource deallocation or invariant restoration paths is very special.  How special?  I’m still not sure; we’re taking this journey of discovery together, but you can be sure that nobody’s going to write calls to close functions in a loop hoping that it’ll someday succeed, so I’m sure that returning errors is useless.  Performing operations which may fail due to transient lack of resources is very very problematic.

Tomorrow we’ll hop back over to invariant restoration and see a bunch of the same problems.   Later we’ll journey over to the Promised Land, where all side effects are reversible… until committed.

What if close could fail?

Yesterday I made the claim that close() can’t fail in a meaningful way.  Meaning that if it’s invoked on an object in a state that does not support close(), it’s a programming/coding error.

I believe that this is correct but we’ll see that there are challenges as a result of it.

Let’s explore briefly what might happen if it could fail for environmental factors.  Are you going to write this code:

int main(int argc, const char *argv[]) {
   for (int i=1; i<argc; i++) {
      FILE *fp = fopen(argv[i], “w”);
      if (fp == NULL) {
         perror(“Unable to open file”);
         exit(EXIT_FAILURE);
      }
      // This is how it should be written but nobody does...  perror is somewhat lacking
      if (fprintf(fp, “Hello there %s\n”, argv[i]) < 0) {
         perror(“Unable to write to file”);
         fclose(fp); // should this match how fclose() is called below??  probably.
         exit(EXIT_FAILURE);
      }
      // controversial bit:
      while (fclose(fp) == EOF) {
         if (errno != ENOMEM) {
            perror(“Unable to close file”);
            exit(EXIT_FAILURE);
         }
      }
   }

   return EXIT_SUCCESS;
}

Maybe you should but I doubt it.  Maybe we should also loop on EDEADLOCK also?  ENOSPC?  All errors?  Probably not EBADF.  This error code probably means that the file handle/id in the FILE is corrupt.  Who’s going to document what?

My point here is only to try to put the nail in the coffin for resource management termination/close functions having public APIs that include failure modes other than invalid parameter.

[edited 5/3/05 2:11pm PST to fix missing return from main]
[edited 5/4/2001 4:00pm PST to fix missing close when fprintf() fails]

Resource management scope termination

Ok I've pussy-footed around the topic, I'll try to draw at least one conclusion finally from one of my first entries in this series.

When you have a pattern of real explicit resource management, the API that's used to denote the end of the resource's lifetime from the point of view of your client must not be able to fail without catestrophic consequences.

By "catestrophic consequences" I mean the appropriate level of runtime termination.  For a user mode program this is probably the process.  For a kernel mode subsystem this generally would mean bugchecking/panicing/cutesy-bomb-ing the system.

Thus the error in the original program actually was that close_resource() returned an error code in the first place.  The only "useful" error condition is if the resource pointer passed in was invalid which would have indicated a programming error, and in general the best course of action when these occur is to terminate the address space.

In conclusion, the right code for the original example actually is:

int do_work(char *psz) {
   resource *pr = NULL;
   int t;
   if ((t = open_file_as_resource(&pr, psz)) != 0) return t;
   if ((t = swap_order_of_bytes_in_resource(pr)) != 0) { close_resource(pr); return t; }
   close_resource(pr);
   return 0; // success
}

You will, of course, notice now that the semantics are very close to try/finally, destructors or IDisposable/using.

I never really got why people wanted to say that destructors can throw but that it invokes a function to terminate the program.  Maybe it was just trying to guard against "throw ()" poisoning (ala const poisoning) down the call chain in a destructor?  As long as the frames aren't unwound prior to the abnormal_termination() call I guess it's equivalent.

There is of course more to the contract than not failing but that's a topic for another day.  We will also eventually notice that all teardown operations also have to follow this basic pattern, and worry about what kind of lock-inversion/deadlock scenarios can happen when teardown occurs while a lock is held.

Function transactionality

A topic that comes up repeatedly in designing function is what a coworker of mine calls "transactionality".

Since I have a little database background, I think that this is an abuse of the term but let's go with it for a while.

Function transactionality is really a pretty simple concept.  Either a function succeeds and its ESEs are visible or it fails in which case the effective state of the system is restored to what it was when the function began.

It's worth pointing out something that is often missed in analysis.  At some constructive level, a program or subprogram is just a series of operations to be performed.  You might call a subprogram that yields a value a "true function" but I'm using C as my machine language so basically every subprogram is a function and some don't happen to return a value.

In this framework there is no notion of "success" and "failure".  (Even exceptions in such languages are defined in terms of functional behavior; it's humans who develop patterns around their use which correspond to they being associated with failure cases.)

In order to make sense of this argument you have to promote the notion of a block of code succeeding or failing to be a first class concept.  Most everyone does this regularly, but since there are no explicit language features around such markings, it's all convention which makes it hard to develop the set of rules I'm leading towards eventually in this series.

Back to function transactionality.  To discuss this further, let's subdivide the world of ESEs into two parts: Transient ESEs and Persistent ESEs.  Transient ESEs are ones which, if the program is terminated, have no effects which persist past the program's termination and restarting.  Peristent ESEs are things which you can't just make go away by stopping and restarting the program.  In general, when a piece of code is working within a single terminatable address space, TESEs are basically things in memory - global variables, data structures, etc.  PESEs generally correspond to files for the sake of discussion.  (There is a third class of one-way ESEs which you cannot undo, such as dispensing cash from the ATM or printing a character on the printer.)

I'm going to ignore PESEs for today and see what it looks like to write code that gets at least TESEs right.

First let's define a nice function that lets us to addition without all the nasty security-bug-causing overflows:

int safe_add(size_t left, size_t right, size_t *result) {
   size_t temp = left + right;
   if ((temp < left) || (temp < right))
      return EOVERFLOW;
   *result = temp;
   return 0; // success
}

It's clear that this function has only one ESE (the assignment at the end), has a clear notion of success and failure and meets the expectations of a "transactional function".  (I really do hate this term but I can't come up with something better...)

Let's use this to do some more work:

int safe_add_2(
   size_t number_to_add,
   size_t *number_to_add_to_1,
   size_t *number_to_add_to_2
   ) {
   int err;
   if ((err = safe_add(number_to_add, *number_to_add_to_1, number_to_add_to_1)) != 0) return err;
   if ((err = safe_add(number_to_add, *number_to_add_to_2, number_to_add_to_2)) != 0) return err;
   return 0;
}

Obvious implementation.  But it's not transactional!  If you were really using this library function to get something  useful done, you could get yourself into a lot of trouble unless every error reported eventually terminated the process.  Let's fix it naively.

int safe_add_2(
   size_t number_to_add,
   size_t *number_to_add_to_1,
   size_t *number_to_add_to_2
   ) {
   int err;
   if ((err = safe_add(number_to_add, *number_to_add_to_1, number_to_add_to_1)) != 0) return err;
   if ((err = safe_add(number_to_add, *number_to_add_to_2, number_to_add_to_2)) != 0) {
      safe_subtract(*number_to_add_to_1, number_to_add, number_to_add_to_1); // bug??
      return err;
   }
   return 0;
}

There we go again like in the beginning of this series.  Calling a function in the error exit path depending on it not to fail.  This code is clearly not safe against multithreaded access or anything so it's hard to argue that this is not correct.  But it sure is unsatisfying.  Let's rewrite it so that the transactionality is more obvious.

int safe_add_2(
   size_t number_to_add,
   size_t *number_to_add_to_1,
   size_t *number_to_add_to_2
   ) {
   int err;
   size_t temp1, temp2;
   if ((err = safe_add(number_to_add, *number_to_add_to_1, &temp1)) != 0) return err;
   if ((err = safe_add(number_to_add, *number_to_add_to_2, &temp2)) != 0) return err;
   *number_to_add_to_1 = temp1;
   *number_to_add_to_2 = temp2;
   return 0;
}

Good or bad?  We used two new temporaries but I personally find this more satisfying because rolling back the changes during the part of the code which could fail was pretty obvious - don't do anything!  Obviously this pattern doesn't work when the proposed state changes are bigger but like I said, it's more obvious that it's correct and in this day and age that's critical.

(The reason that PESEs are much harder is because unless you have real transaction support from the underlying persistence engine, you probably have to issue counter-operations against the changes made which themselves may fail and you can get yourself into a situation where your persistent data is corrupt and you can neither go forward nor backward.)

Side-effects: a more useful definition

A typical CS-ish definition of whether a function has a side effect is whether the function modifies any globally visible state during its execution.

e.g. this function is side-effect free:

int add(int x, int y) { return x + y; }

And this function is not:

int add(int x, int y) { interlocked_increment(&GlobalAddCounter); return x + y; }

Side effects will be interesting to us soon when we discuss what kinds of actions need to occur to undo partial state changes in failure and exit paths.

I'm going to make up a term here: Innocuous Side Effects.  I thought about this term for about 15 seconds just now so if someone has a better name, feel free to suggest it, but I'll go with the acronym ISE for now.  (Hey, I came from Digital a long time ago, just be glad I'm not calling I1E or something... ;-)

Here's an example of an ISE: [there's a bug in here; addressed later...]

int add(int x, int y) {
   if (TraceLogPointer != NULL) fprintf(TraceLogPointer, "Adding %d and %d\n", x, y);
   return x + y;
}

Notice that like 99% of the code in the world I did not check the return value from fprintf(), but unlike 90% of that code, it's actually intentional.  This was a trace log; if the trace log is on a disk that's out of space or something the implied contract for diagnosibility tracing is that exogenous factors which make the tracing unable to proceed should not break me.  I would probably have labelled the second add() implementation (which incremented a global counter) as having only ISEs also since it's extremely unlikely that the counter is used to derive any basic correctness guarantees.

I guess we need to have a term for the opposite so I'll call the others Egregious Side Effects.  Here's an ESE.  Yes, I know no real transactional system would use fprintf to write to the log; I'm just trying to be illustrative.

int tx_append_to_data_file(
   FILE *fp,
   const char *psz
   ) {
   if (fprintf(RollbackLog, "Appending: \"%s\"\n", psz) < 0) return EUNABLETOWRITETOLOGFILE; // bug??
   if (fprintf(fp, "%s\n", psz) < 0) return EUNABLETOWRITETOFILE; // bug??
   if (fprintf(RollbackLog, "Append completed\n") < 0) return EUNABLETOWRITETOLOGFILE; // bug??
   return 0;
}

Why does every line have a // bug?? comment on it?  It's rather egregious to lose the actual problem that occurred when writing the log file and would massively hurt diagnosibility.  Probably the right thing to do in all cases was to return the value in errno.  (I already chose not to return boolean success/failure indicators, leaving things like errno for passing more specific information.  Arbitrary decision but I'm going to stick with it.) Another topic for another day.

Note another possible problem here.  Even the ISE example wasn't pure; it actually calls a function that is an ESE which promotes it to be an ESE itself unless you do extra work.  Let's do the extra work:

int add(int x, int y) {
   if (TraceLogPointer != NULL) {
      int old_errno = errno;
      fprintf(TraceLogPointer, "Adding %d and %d\n", x, y);
      errno = old_errno;
   }
   return x + y;
}

(This inadvertant promotion of an ISE to an ESE due to out-of-band error information is one of the main reasons to avoid this.  I don't know how many times I had to fix code because in a cleanup path, errno or the win32 GetLastError() value was overwritten.)

The main point of this post is to establish that there are two basic kinds of side effects:

1. ESEs: Ones which are critical to correct execution of the program/system
2. ISEs: Ones which are for debugging or diagnosibility etc. where the state changes have basically two qualities:
   1. They cannot (meaningfully) fail
   2. Their actions do not cause other "type 1" side effects to change.

You could argue that 2.1 is implied by 2.2 and that 2.2 is the really critical point but I want to make it explicit that propagating an error from an ISE is a fundamental bug.

[mgrier: fixed inconsistently used global variable name for the tracing log file pointer]

Errors and a simple invariant

Before addressing the problems with close_resource(), I want to explore another avenue which is invariant restoration.

Let's amend the little function some more.  I'm trying to stay away from Windows concepts but I need to update a global counter in what is presumably a multithreaded context.  Intead of pulling in pthreads and mutexes, I'm going to call some functions called interlocked_increment() and interlocked_decrement().  They atomically update an integral type.  [I also in a fit of revisionism changed the parameter from a non-const char * to const char *.  I unfortunately was there during the const poisoning debates and some habits, even when you know they're bad, die hard...]

size_t updates_in_progress = 0;

int do_work(const char *psz) {
   resource *pr = NULL;
   int t;
   interlocked_increment(&updates_in_progress);
   if ((t = open_file_as_resource(&pr, psz)) != 0) return t;
   if ((t = swap_order_of_bytes_in_resource(pr)) != 0) { close_resource(pr); return t; } // bug??
   if ((t = close_resource(pr)) != 0) return t;
   interlocked_decrement(&updates_in_progress);
   return 0; // success
}

Ok, so that obviously created a new set of bugs.  Again, I'm avoiding syntactic sugar that could make this look a lot easier because my eventual goal is to build a case that code used to either release resources or restore invariants is very special so I want to show all the places it really ends up being used, not just the obvious ones.

Here's the fixed version in C:

size_t updates_in_progress = 0;

int do_work(const char *psz) {
   resource *pr = NULL;
   int t;
   interlocked_increment(&updates_in_progress);
   if ((t = open_file_as_resource(&pr, psz)) != 0) {
      interlocked_decrement(&updates_in_progress);
      return t;
   }
   if ((t = swap_order_of_bytes_in_resource(pr)) != 0) {
      close_resource(pr); // bug??
      interlocked_decrement(&updates_in_progress);
      return t;
   }
   if ((t = close_resource(pr)) != 0) {
      interlocked_decrement(&updates_in_progress);
      return t;
   }
   interlocked_decrement(&updates_in_progress);
   return 0; // success
}

In some future post after we discuss the reliability contracts of functions like close_resource() and interlocked_decrement() I'll compare and contrast the flavors of syntactic sugar available to make this prettier.

Always check your return codes?

Is there a bug here?

int do_work(char *psz) {
   some_type *p = NULL;
   int t;
   if ((t = foo(&p, psz)) != 0) return t;
   if ((t = bar(p)) != 0) return t;
   if ((t = baz(p)) != 0) return t;
   return 0; // success
}

Let's be clear that this is ambiguous.  We don't know what foo, bar and baz do and while it might be obvious from the calling patterns that maybe there's some pattern of resoure management going on, it's just not clear.  I don't want to spend a lot of time on good naming of functions, I want to get into resource and invariant management issues.

If I just change the names, it's pretty clear that there is a bug here:

int do_work(char *psz) {
   resource *pr = NULL;
   int t;
   if ((t = open_file_as_resource(&pr, psz)) != 0) return t;
   if ((t = swap_order_of_bytes_in_resource(pr)) != 0) return t;
   if ((t = close_resource(pr)) != 0) return t;
   return 0; // success
}

The bug of course is that if swap_order_of_bytes_in_resource() fails, we forget to close the resource.  The corrected version of this function apparently is:

int do_work(char *psz) {
   resource *pr = NULL;
   int t;
   if ((t = open_file_as_resource(&pr, psz)) != 0) return t;
   if ((t = swap_order_of_bytes_in_resource(pr)) != 0) { close_resource(pr); return t; }
   if ((t = close_resource(pr)) != 0) return t;
   return 0; // success
}

Or is it?  I just introduced an obvious bug in the source (it's not checking the return status of close_resource() in the error exit case).

I think the pattern is broken and a discussion of how the pattern is broken and what it takes to actually fix the pattern is what I'm going to write about for a while.  The fix for this particular instance of the pattern is probably well known but there are a lot of nuances and it's a gateway into larger patterns.

(note: I'm aware of how RAII helps here and I'm an advocate of it; I'm decomposing these code examples to the barest minimums so that we can see the defects present.  We'll see that in some cases the fixes for these kinds of problem exactly align with the code you would see generated for use of objects with deterministic lifetime management, be it C++ objects with destructors or CLR objects that implement IDisposable and are properly used in a using statement.)