CMock Under The Hood: Part 2 - Chaining

Welcome to part 2 of CMock Under The Hood. You can find part 1 here. As I mentioned previously, you aren't likely to need any of this information to USE CMock... I'm making an assumption that there are others out there who just want to know how something works and why decisions were made the way they were. This article is for people like that.

Today we are talking about the second feature that is handled primarily in the C module of CMock: Chaining. To understand CMock's Chaining procedures, we should first look at how CMock thinks about function calls. What we need now is a sample header to mock. Let's go with a simple header Lab.h that has only three functions:

void SecretLab_Init(void);
int  SecretLab_IsSecret(void);
char* SecretLab_Move(char* OldLocation, int SecretId);

When CMock creates a mock for this header, it starts by creating three structure typedefs, one for each of the functions. These structs represent everything we would need to know about a single instance of calling that particular function. The details vary based on which options you have enabled, but likely they will end up looking something like this:

typedef struct _CMOCK_Lab_SecretLab_Init_CALL_INSTANCE
{
  UNITY_LINE_TYPE LineNumber;
} CMOCK_Lab_SecretLab_Init_CALL_INSTANCE;

typedef struct _CMOCK_Lab_SecretLab_IsSecret_CALL_INSTANCE
{
  UNITY_LINE_TYPE LineNumber;
  int ReturnVal;
} CMOCK_Lab_SecretLab_IsSecret_CALL_INSTANCE;

typedef struct _CMOCK_Lab_SecretLab_Move_CALL_INSTANCE
{
  UNITY_LINE_TYPE LineNumber;
  char* ReturnVal;
  char* Expected_OldLocation;
  int   Expected_SecretId;
} CMOCK_Lab_SecretLab_Move_CALL_INSTANCE;

Next, there is a module private (static) struct defined. At a minimum, this struct has a single field for each function in the module. This field is an index value, like so:

static struct MockLab
{
  int Lab_SecretLab_Init_CallInstance;
  int Lab_SecretLab_IsSecret_CallInstance;
  int Lab_SecretLab_Move_CallInstance;
} Mock;

Before each test, these values are all going to get set to 0. Within our test, when we call one of these Expect functions, we ask CMock to give us a block from the memory pool that is the size of that functions CALL_INSTANCE struct. Our Expect call then fills out the struct using the arguments passed.

Sticking with our example, let's say a test made the following call:

SecretLab_IsSecret_ExpectAndReturn(1);

The inside of SecretLab_IsSecret_ExpectAndReturn(int) is going to ask the Memory Manager for sizeof CMOCK_Lab_SecretLab_IsSecret_CALL_INSTANCE bytes. Then it's going to fill out the line number that made the call (a topic for another day) and the return value of 1.

But then what?

It needs to store that away somewhere so that it knows that we made this call. What if we called this same ExpectAndReturn a second time in this test and returned a 0? Clearly it's important that we preserve the order of these calls. 

This is where the static Mock structure comes in... and this is where Chaining comes in. Our Mock struct is always pointing at the first call instance for each function. If a particular function is never called, its entry in the Mock struct will remain 0, indicating that it is empty.

The fun happens when the Expect then makes a call to CMock_Guts_MemChain. This function takes two arguments. The first is the root index for this function. The second is the index of the memory we just allocated and filled. The root index is looked up in the Mock struct. The output of this function is also the root index, so that it can be assigned back to the Mock struct element. This might at first seem a little strange, but it allows the MemChain function to accept an index for a function that is being called for the first time, and handle it transparently.

So what happens inside the MemChain function? It's a simple matter of following the indexes like a single-linked list. The Mock struct gave us the index to the first element. If it was zero, then we assign our first element to be this instance and return the index. If not, we follow the chain. But where are the pointers to the next elements?

For that, we need to back up real quickly to when we were talking about Memory Management. At that point, I glossed over a detail, because it made more sense to talk about it today. Whenever you ask CMock's Memory Manager to allocate a block of memory, it allocates the requested size PLUS a few more bytes to hold the next index. It actually puts this index first. Because the index is always the same size, CMock_Guts_MemNew actually skips this index returns the memory location for the start of the desired data. But CMock's internals know that it's there... and when we call chain, it knows that it only needs to back up a few bytes from the given address, and it will be looking at the index of the NEXT call instance for this particular function. The last call instance in each chain will have a NEXT index of 0, indicating that there are no more calls left.

So what does this end up looking like? Let's look at a simplified snapshot of what CMock's memory pool will look like after this series of calls:

void test_MoveBaseWhenFound(void)
{
  SecretLab_Init_Expect();
  SecretLab_IsSecret_ExpectAndReturn(0);
  SecretLab_Move_ExpectAndReturn("Polar Ice Caps", 42, "Underground Base");
  SecretLab_IsSecret_ExpectAndReturn(1);

  //We're going to see what it looks like here!

  CheckOnBase();
}

So what does the memory look like in the spot we indicated? Something like this:

ValueWhat it's there for
0Index NULL because Init called only once
3Line number we called Init_Expect
40Index of next call to IsSecret's data
4Line number we called first IsSecret_Expect
0Int Value we are returning
0Index NULL because Move called only once
5Line number we called Move_Expect
0x12345678Pointer to string "Polar Ice Caps"
42SecretID and padding
0x12345712Pointer to string "Underground Base"
0Index NULL because this was last call to IsSecret
1Int value to be returned

Our Mock struct looks something like this:

Lab_SecretLab_Init_CallInstance:     4
Lab_SecretLab_IsSecret_CallInstance: 12
Lab_SecretLab_Move_CallInstance:     28

Make sense?

It might seem like it is incredibly inefficient to have a linear search every time we need to insert a new Expect call. Each time, we start with the base and we trace until we reach the last call of that function, and we add ours. As the number of Expectations grows, this operation gets slower and slower linearly (It is, after all, an O(n) operation). 

However, it should be noted that most tests... and by most I mean the overwhelming majority... don't have many calls to the same function. Tests that deal with loops are still often just working with dozens, not tens of thousands, of calls. For cases where the number of calls are low, it is actually MORE efficient for us to do this linear search than a more complex algorithm. The memory overhead also scales with the number of calls, making it a good fit for memory constrained situations like this one.

One final thing that is worth pointing out: CMock has ONE memory pool, but each Mocked module you have linked in has its own private (static module-scoped) Mock struct. Because the Mock objects store the base index, the core Memory Management functions don't need to care about the number of functions or modules or arguments or anything else... they can focus on just allocating the next block and adding it to whatever chain it is told to add it to.

If I were a better artist, I would insert a picture of worms twisting through a piece of swiss cheese at this point, because that is how I like to imagine CMock's memory map when it's heavily used.

I hope you found this jaunt through CMock's internals interesting! Next time, we'll talk about it's heavy dependency on macros and what it does that. Thanks for reading!