Points of Order

It was a cold day, but then February days were almost always cold. It didn't help that the day had got off to a worse-than-usual start: in my bleary post-waking pre-work routine I had a difficult time putting on my socks, only to discover it was because I'd already put on my boots. I sighed, took off my boots, put the socks on, put the boots back on, and was still shaking my head blearily as I walked out the door, vaguely hoping that a morning coffee or three would help.

It was to be an inauspicious harbinger of events later in the day.

I had just settled in at work and was slowly beginning to get into the flow of things when Wendy came by. "Yo, pardner," she said. "Got a minute?"

"Sure. What's up?"

"Kerry needs some help." She nodded in the direction of Kerry's cube. "It's with Bahb's code, so I suggested he come see you. Heh. Kerry's over there organizing his thoughts and mustering his courage. Just a heads-up, he'll be by soon."

"Sure," I agreed again, and thought to myself, Mustering up courage? Am I starting to intimidate him? Then I realized what she meant: my going along with the Guru's shtick was having an increasing effect on the poor intern, and I was a bit surprised when I found myself smiling at that thought.

Wendy left, and soon enough I heard footsteps approaching. Before Kerry could actually appear, I said: "Yes, young one?"

The footsteps paused, then resumed, and Kerry hove into view. "Uh, d'you mean me?"

"Yes," I said while still typing and only then turned and smiled. "What can I do for you?"

"Uh..." he said, seeming already slightly flustered. "Uh, well, I have a problem with some code that I think Bob wrote. I've got a simplified version to show you."

"Good job, glad you distilled down the example," I said approvingly. "Show away!" I made a grand gesture, and he pulled up the function on my screen:

void Process( Queue& q )
{
  int i = 0;
  Lock<Mutex> l( sendQ ); // acquire
  Send( "--- Send Begin---" );

  while( i < q.size() )
  {
    // acquire
    Lock<Mutex> l( q[i].mutex );
    Send( q[i].payload, i++ );
  } // release q[i].mutex lock

  Send( "--- Send End---" );
} // release sendQ lock

"Aaah," I aaahed pretty quickly. "I see your problem."

"Uh... you do?"

"Yes," I continued. "Consider: what's wrong with the second Send() call?" I pointed at the line:

    Send( q[i].payload, i++ );

"Right!" I interrupted. "That's exactly right, it's i! The variable i is being used in two argument expressions in the same function call. The order of evaluation of the function arguments is undefined, so either q[i].payload or i++ could be evaluated first. If the former, you're fine. If the latter, you're well and truly hosed because on the last loop iteration you'll be trying to invoke q[q.size()], which is off the end of the container. Not only shouldn't the side effect of incrementing i appear in the function parameter, but the whole thing would work better as a for loop." I edited his code to demonstrate:

void Process( Queue& q )
{
  Lock<Mutex> l( sendQ ); // acquire
  Send( "--- Send Begin---" );

  for( int i = 0; i < q.size(); ++i )
  {
    // acquire
    Lock<Mutex> l( q[i].mutex ); 
    Send( q[i].payload, i );
  } // release q[i].mutex lock

  Send( "--- Send End---" );
} // release sendQ lock

"Oh. Thanks." Kerry paused, pondering this, and then tentatively ventured: "But that's not my problem."

I blinked. "Eh?"

"My problem," Kerry explained patiently, "is that this code hangs every so often, and I don't know why."

"Right, that's what I said. You'll get an access viola--"

"No, no," Kerry broke in gently. "I see that problem now, but that's not the problem I'm having. The code doesn't blow up, at least not on the compilers we're using. What's happening is that the program hangs and won't respond. Intermittently. Once in a while. In front of our biggest customer, at an internal raw demo this morning, actually."

"Oh." I blinked again. "Right. Uh, well..."

Snap! I jumped, but got at least a little satisfaction in noticing that Kerry jumped slightly higher. I had been too absorbed in the problem to notice the Guru come up behind us until she had snapped her book shut. "My apprentice, my novice," she greeted us. "A point of order, if you please."

"Yes, we were just discussing that," I agreed, pointing at the offending lines of code I had just fixed. "We've fixed the ordering problem already, but it turns out that Kerry actually has a different problem."

"Indeed," the Guru smiled. "As you say, 'Ah, I see your problem.' But it is still a point of order, as I said. One does not put on one's shoe before one puts on one's sock." I started at this and wondered if she had a spy cam in my room. But she was already continuing: "Prithee tell, have you looked at the other uses of the Queue?"

"Other uses?" Kerry and I chorused.

"Other uses." The Guru bowed gracefully, reopened her tome, and glided away. "You might start with ExceptionReport()..." her voice floated back just as she turned the corner.

I did a quick grep and found the code the Guru was talking about. Simplified, it boiled down to this:

void ExceptionReport( Queue& q )
{
  for( int i = 0; i < q.size(); ++i )
  {
    Lock<Mutex> l( q[i].mutex );
    if( MeetsCertainCriteria( q[i].payload ) )
    {
      Lock<Mutex> l( sendQ );
      Send( q[i].payload, i );
    }
  }
}

"Yeah," I agreed. "Stinkin' locks. So, go ahead, finish the thought... tell me what we have here."

"It's a deadlock," Kerry said, gaining confidence. "We have two pieces of code, and they're acquiring two locks in reverse order, and every so often they just go hang. In Process(), we know we're going to output lots of stuff to a Send queue, so we lock the Send queue just once for the whole operation..."

"Why?"

"...to avoid needlessly releasing and reacquiring the lock, which would be inefficient. And then each item in the queue is protected by a mutex, so we lock it, output it, and release the lock on that item."

"Right. And what about ExceptionReport()?"

"There, we don't know yet if we'll even emit anything," Kerry said and sighed. "So there's no point in acquiring the Send queue lock until we know we're actually going to stuff something into it. So we get to each item in the queue, lock it, inspect it, and then if we need to send it we lock the Send queue lock too and then release both locks in reverse order."

"And sometimes...?"

"And sometimes Process() might be running in one thread while ExceptionReport() is running in another thread, and they try to acquire the same two locks in the reverse order. But... but the way the code is now, for both functions, just seems like the right thing to do in each case. Isn't it?"

"Sure it is," I agreed. "Sometimes some requirement has to give somewhere. How would you do it?"

"I don't know."

"Well," I welled, "we just have to acquire locks in the same order always or change one thread to not acquire them both. So we could change Process() to store all the items to be sent into a temporary area and only then acquire the Send lock once to send them all; that's a space overhead, but it means Process() won't ever acquire both locks at the same time because all the work on the Queue would happen first before any Send() work happens. Or we could make changes to ExceptionReport(), say to acquire the Send lock for the whole scope of the function whether it's needed or not."

"And you found that other problem too."

"Right. Never write code that depends on the order of evaluation of function arguments."

"Order," Kerry muttered to himself. "Order. Order..."

"Right, yeah. Like she said--" I looked around quickly, checking for silent footsteps sneaking up on us, but the Guru was nowhere in sight. "--both problems were a point of order. 'Scuse me now," I finished as I got up, "but I think I'll go practice changing my socks."

About the Authors

Jim Hyslop is a senior software designer with over 10 years programming experience in C and C++. Jim works at Leitch Technology International Inc., where he deals with a variety of applications, ranging from embedded applications to Windows programs. He can be reached at [email protected].