REN

This is the fourth one of 'Talking about C pointer' series. In this article, I'll discuss pointer of structure, shallow copy vs. deep copy and and avoiding memory leakage when using pointer of structure. In addition, I'll show an example in Linux kernel source code on how to use pointer to get the 'container of an element'.

Poiner of Structure

We've talked a lot on pointers in the last three articles. The pointer of structure, as its name, is a pointer pointing to a structure. When we use a pointer of structure pointing to one structure, then we could use '->' to visit the member of the structure.

/* test.c */
#include <stdio.h>

typedef struct S{
	int a;
	char b[2];
	int* c;
} S;

int main() {
	S s;
	s.a = 1;
	strcpy(s.b, "a");
	s.c = NULL;
	S *p = &s;
	printf("s.a = %d\n", p->a);
	printf("s.b = %s\n", p->b);
	return 0;
}

Let's compile this program in GCC:

gcc -o test test.c

The result of those codes are: (on x86_64 Linux)

s.a = 1
s.b = a

Deep Copy vs. Shallow Copy

Before illustrating 'deep copy' and 'shallow copy', let's look at a program based on the code above.

/* test.c */
#include <stdio.h>

typedef struct S{
	int a;
	char b[2];
	int* c;
} S;

int main() {
	S s;
	s.a = 1;
	strcpy(s.b, "a");
	s.c = (int*)malloc(5*sizeof(int));
	for (int i = 0; i < 5; i++)	
		s.c[i] = i;

	S t = s;	// copy s to t
	printf("t.a = %d\n", t.a);
	printf("t.b = %s\n", t.b);
	for (int i = 0; i < 5; i++)	
		printf("t.c[%d] = %d\n", i, t.c[i]);

	free(s.c);	// free dynamic memory for s.c

	t.c[0] = 5;	// modify value of c[0] in t
	printf("new value of t.c[0] = %d\n", t.c[0]);
	free(t.c);  // free dynamic memory for t.c

	return 0;
}

Let's compile this program in GCC:

gcc -o test test.c

The result of those codes are: (on x86_64 Linux)

t.a = 1
t.b = a
t.c[0] = 0
t.c[1] = 1
t.c[2] = 2
t.c[3] = 3
t.c[4] = 4
new value of t.c[0] = 5
*** Error in `./aa': double free or corruption (fasttop): 0x00000000008a7010 ***
 ...
Aborted (core dumped)

When we free the pointer t.c, there's an system error, because the copy from s to t is a shallow copy. s.c is an integer pointer pointing to a dynamic memory chunck, while t.c is also an integer pointer pointing to the same memory chunck. Thus it's nonsense to free(t.c) after free(s.c) because they are the same thing. And that is why it's called shallow copy: only copy the pointer instead of copying the dynamic memory chunck that pointer pointing to.

Now, let's make a little modification on the code above:

/* test.c */
#include <stdio.h>

typedef struct S{
	int a;
	char b[2];
	int* c;
} S;

int main() {
	S s;
	s.a = 1;
	strcpy(s.b, "a");
	s.c = (int*)malloc(5*sizeof(int));
	for (int i = 0; i < 5; i++)	
		s.c[i] = i;

	S t = s;	// copy s to t
	t.c = (int*)malloc(5*sizeof(int));
	printf("t.a = %d\n", t.a);
	printf("t.b = %s\n", t.b);
	for (int i = 0; i < 5; i++)	
		t.c[i] = s.c[i];

	free(s.c);	// free dynamic memory for s.c

	t.c[0] = 5;	// modify value of c[0] in t
	printf("new value of t.c[0] = %d\n", t.c[0]);
	free(t.c);  // free dynamic memory for t.c

	return 0;
}

Let's compile this program in GCC:

gcc -o test test.c

This time the result is correct: (on x86_64 Linux)

t.a = 1
t.b = a
new value of t.c[0] = 5

Using pointer of structure may often bring about memory leakage. In the following case, remember to free the inner dynamic memory first, then free the outer dynamic memory.

/* test.c */
#include <stdio.h>

typedef struct S{
	int a;
	char b[2];
	int* c;
} S;

int main() {
	S *s = (S*)malloc(sizeof(S));
	s->a = 1;
	strcpy(s->b, "a");
	s->c = (int*)malloc(5*sizeof(int));	

	free(s->c);	// free inner dynamic memory first
	free(s);	// free outer dynamic memory

	return 0;
}

The trick of "Get Container"

Considering the following senario: there's a linked list, and each node of this list is contained in a structure; We now know the address of an node of the list, how can we get the address of structure that contains it?

Actually, source code in linux kernel perfectly solved this issue but the code is not so easy to read. Thus, I made a slight modification to make it looks more specific:

/* test.c */
#include <stdio.h>

typedef struct node {
	int value;
	struct node* next;
} node;

typedef struct container {
	int number;
	char name[2];
	node* list_entry;
} container;

container* get_container(void* ptr) {
	return (container*)((char*)ptr - (unsigned long)(&((container*)0)->list_entry));
}

int main() {
	container c;
	c.number = 0;
	strcpy(c.name, "aa");
	c.list_entry = (node*)malloc(sizeof(node));
	c.list_entry->value = 0;
	c.list_entry->next = NULL;
	printf("The address of container c is 0x%x\n", &c);
	printf("The address of container c is 0x%x\n", get_container(&c.list_entry));
	return 0;
}

Let's compile this program in GCC:

gcc -o test test.c

The get_container() returns the address of container: (on x86_64 Linux)

The address of container c is 0xeaa1730
The address of container c is 0xeaa1730

We already know the address of list_entry, then we need to know the offset of list_entry, and make a substraction. Here's the analysis on how to calculate:

(char*)ptr - Make an type casting from void* to char* to ensure the step on operator '-' is 1.

((container*)0)->list_entry - Make an type casting from 0x0 to container*, and then get its member: list_entry

&((container*)0)->list_entry - Get the offset of list_entry

(unsigned long)(&((container*)0)->list_entry) - Make a type casting to unsigned long to ensure the length of an address

(container*)((char*)ptr - (unsigned long)(&((container*)0)->list_entry)) - Do the substraction and make a type casting to container

Conclusion

Be very careful when using pointers of structure, shallow copy may cause memory double free problem or other unexpected errors. When free the dynamic memory chuncks, make sure to free them from inner to outer. The container_of in Linux kernel is a very thicky one using pointer. In the next talk, we're gonna talk about how to implement Object-Oriented Programming model using function pointer.