what not to do is as important as what to do


I am a Software Engineering Student at Holberton School, San Francisco | contact me or follow me.

Share

:on how and why C language allocates memory

Special thanks to Lisa Leung for her editions.  You can follow her on github here.

In learning C language, in our studies as Software Engineering students at Holberton School, we use the GCC (i.e. GNU Compiler Collection) compiler to convert our C language code into an executable file of code in binary system (i.e. 0's and 1's) because 0's and 1's can be easily translated into on and off transistors of a circuit board.  For more on GCC compiler, check out my article: Computer Compilers: brief introduction.  So, when a transistor is off, that translates to a ‘0’ (zero), and a transistor that is on (having electric current flow) translates to a ‘1’ (one). Binary is the link between human legible code and the machine that contains transistors in the Central Processing Unit or CPU.  Once one has a basic grasp of this concept, it is a bit easier to understand memory on a computer.  If all your applications are converted, processed and stored in transistors, then you can imagine that there are only so many available transistors to store that information.

binary

Computer hardware is often grouped into 4 main components: CPU, Motherboard, hard drive, and RAM.  We're discussing memory in the blog, so I'll focus on the (1) hard disk drive (HDD) or solid state drive (SSD) otherwise known as your disk storage and (2) your system memory otherwise known as random access memory or (RAM) which is a part of the central processing unit or (CPU).  To put it simply, RAM is utilized when applications are running while disk storage is used to store files even when not being accessed.  However, a computer also uses what is known as virtual memory to run applications and current processes, which is essentially a way for the RAM to somewhat replicate the memory process on disk storage space.  There is a lot more written on these concepts in the Holberton School blog, in a post by Julien Barbier called Hack The Virtual Memory: C Strings & /proc.  Some of the larger scale concepts that I explain in this article, I learned from Julien's blog post. In this article, I will not be explaining the exact location of memory, but instead, I simply generalize memory and the storage addresses of memory.  It is important to note that a memory address on a computer is comprised of 1 byte, which consists of 8 bits.  1 bit is either a 0 or a 1, which is translated to either a closed or open circuit respectively.  Therefore, a memory address consists of 1 byte, which is 8 circuits.

Because C language has the ability for a programmer to specifically designate how much memory the application they are creating will use, when to use that memory, and when to terminate that process, C language is often understood as one of the most efficient and fastest languages during running time.  As long as a programmer knows how to use C Language's ability to allocate memory efficiently, and writes effective code to do so, their programs can run extraordinarily efficient after compilation.  Also, because the GCC compiler compiles C files and programs programs into binary which interacts with the machine, it is one of the most used languages with electronics and hardware which understands and reacts to binary code.

memory allocation

Before we proceed to discuss memory allocation, it is important to distinguish between the different ways that C language allocates memory. Essentially, there are three types of allocation — static, automatic, and dynamic. Static allocation means, that the memory for your variables is allocated when the program starts, and therefore the size of all variables statically allocated is fixed when the program is created. It applies to global variables, file scope variables, and variables qualified with static definitions inside of functions. Automatic allocation occurs for variables defined inside functions (non-static variables). You do not have to reserve extra memory to utilize such variables, but there are restrictions such as having limited control over how and when to use such variables. For example, a potential restriction of static and automatic variables, is that you cannot create a variable of an unknown size when creating the code for your program; also, or such variables will only remain accessible within the scope of the function that they are in.

:static & automatic memory allocation

One of the ways that C language efficiently allocates memory with automatic allocation is in it's "type" structure.  C organizes variables and data into different types, which indicate to the computer memory how much memory to use.  For the purpose of explaining these examples, I will be using a 32-bit computer memory system; however, it is essential to understand that the sizes of each type depends on the size of the computer.

data types and limits

In C language there are the data types can be organized into 4 main categories:

Data Type Examples
Basic int, char, float, double
Enumeration enum
Derived pointer, array, structure, union
Void void

Additionally, the basic data types can be further specified with these modifiers: short, long, signed, and unsigned.  The amount of memory that these data types utilize is basically organized like the following:

data type bytes used
per variable
32-bit
range of values
per variable
char 1 –127 to 127
int 4 –32,767 to 32,767
float 4 3.4E +/- 38 (7 digits)
double 8 1.7E +/- 308 (15 digits)
long double 10 1.7E +/- 308 (15 digits)
long int 4 –2,147,483,647 to 2,147,483,647
short int 2 –32,767 to 32,767
unsigned short int 2 0 to 65,535
signed short int 2 –32,767 to 32,767
long long int 8 –9,223,372,036,854,775,808
to 9,223,372,036,854,775,807
signed long int 4 –2,147,483,647 to 2,147,483,647
unsigned long int 4 0 to 4,294,967,295
unsigned long long int 8 0 to 18,446,744,073,709,551,615

This table shows how each data type utilizes a specified number of bytes from memory.  Since, I explained that each memory address consists of 1 byte, one could see how a char data type, which is a value of an ascii character or ascii number, is stored in 1 memory address, and int types are stored with 4 memory addresses.  So, with the example of a 32-bit system, an application can directly access up to 2^32 or 4,294,967,296 memory addresses at one time, which is 4 gigabytes of memory.  Now, functions, structs, pointers and other elements of C language are also stored in memory, but for the purpose of this post, I will not be explaining those concepts.

Now that I have established that variables in C language use different bytes of memory, when we begin to write our C programs, we will be able to realize how much memory each of our variables needs in order to process on the computer.  For example, if I define 3 variables of type int: int x, y, z;, when my program is compiled and running, it will need at least 12 bytes of memory to run.  This concept becomes especially important for pointers, arrays, strings, and structs because each of these contain large groups of memory addresses, and if they are not managed properly they will not be able to function with the memory available to your C program. Therefore, instead of using up a computer's entire memory for each array in a program, a software developer can write code, which allocates only certain memory addresses to process that array and allows for other memory addresses to be used for other processes. Hence the inspiration for the title of this post, which will come to a complete analogy when I explain how to stop memory usage with the function free().

:dynamic memory allocation

So far in all the above examples, I have been referring to static and automatic memory allocation. As a reminder, in C Language, when one defines an array or string, it is common to allocate memory immediately in the array's definition as follows: int an_array[1024];. However, C Language has different protocols for (1) defining arrays of unknown sizes, for example if an array is within a function that takes input variable as the array size, and (2) accessing arrays that were defined in other functions; in this case a pointer is used to access the memory of an array, which is defined in other functions. In these instances, dynamic allocation is helpful because you can control the exact size and scope of accessibility of such needed memory locations. With dynamic allocation it is common practice to allocate the necessary memory using the functions malloc()calloc() and realloc().

:malloc() and calloc()

An excerpt from the manual on malloc() (using Ubuntu on Linux) has an extraordinarily complete explanation in the following excerpt. I cut out the less important details and kept the main definitions of each function:

DESCRIPTION
       The malloc() function allocates size bytes and returns a pointer to the allocated memory.  The memory is not initialized...

       The free() function frees the memory space pointed to by ptr, which must have been returned by a previous call to malloc(), calloc() or realloc()...

       The  calloc()  function  allocates  memory for an array of nmemb elements of size bytes each and returns a pointer to the allocated memory.  The memory is set to zero...

       The realloc() function changes the size of the memory block pointed to by ptr to size bytes.

RETURN VALUE
       The  malloc()  and  calloc()  functions  return  a pointer to the allocated memory that is suitably aligned for any kind of variable.  On error, these functions return NULL...

       The free() function returns no value...

       The realloc() function returns a pointer to the newly allocated memory...

For all 3 of the listed functions:

If size is 0, then function returns either NULL, or a unique pointer value that can later be successfully passed to free().

Therefore, with the above explanations in mind, a programmer would need to allocate memory with malloc(), calloc() or realloc() in order to define a variable of unknown sizes or to be able to access memory in another function using pointers. Additionally, the free() function is especially useful for leaving memory unused and open for usage for other program functions.

Practical examples of memory allocation

example output of allocating memory with 0 NULL bytes

A simple program that can be used to demonstrate these concepts is a program that takes two inputs, which are the length and width of a rectangle grid, then creates a 2D array of those dimensions to be filled with the integer "0" that could then be printed to form a square in an ascii art type way.  The output for inputs of width: 6 and height: 4 is visualized in the enlarged example to the left, and the full code can be seen below.

While it may be unlikely that anyone would need to print a grid larger than the amount of memory a computer has available for a given program, the designer of such a program could still account for inputs too large for the computer's available memory in order to prevent program errors.  Let's take a look at my code below to see how it accounts for memory allocation.

below is a function which creates such a grid and prepares it to be copied by another function.  It can also be accessed from my GitHub account here.

 10 │ int **alloc_grid(int width, int height)
 11 │ {
 12 │     int **grid;
 13 │     int i, j;
 14 │ 
 15 │     if (width < 1 || height < 1)
 16 │         return (NULL);
 17 │     grid = malloc(sizeof(int *) * height);
 18 │     if (grid == NULL)
 19 │         return (NULL);
 20 │     for (i = 0; i < height; i++)
 21 │     {
 22 │         grid[i] = malloc(sizeof(int) * width);
 23 │         if (grid[i] == NULL)
 24 │         {
 25 │             for (--i; i >= 0; i--)
 26 │                 free(grid[i]);
 27 │             free(grid);
 28 │             return (NULL);
 29 │         }
 30 │     }
 31 │     for (i = 0; i < height; i++)
 32 │         for (j = 0; j < width; j++)
 33 │             grid[i][j] = 0;
 34 │     return (grid);
 35 │ }
  • Line 15 checks for inputs smaller than 1 since a length or width of less than 1 would not return any grid.
  • Line 17 allocates memory for the height of the grid, which was defined on line 12. Since this example uses 2D pointers, or in other words, a pointer to an array of pointers, each memory slot that is being allocated, represents one row of the grid. In the use of malloc() function, I used sizeof(int *) because each memory address allocated with malloc is 1 byte. Since, my end goal is to fill these memory addresses with pointers representing the beginning of each row that contain the memory address of each array of integers "0", I need to add more bytes to account for the size of pointers to integers. Therefore, there will be enough memory addresses for each pointer that is stored in the grid array. Another point to notice of this line is that my code uses a variable to define the memory locations, which is normally not allowed for arrays in C Language.
  • Line 18 checks if malloc returned a NULL pointer, which would happen if there would not be enough memory for the previous process.
  • Lines 20 - 30 repeat the same process as line 17 for each row of arrays. However, if one of the lines is unable to allocate enough memory and the malloc() function returns NULL, I need to loop through to free all the previously allocated memory before terminating my process since the previous calls to malloc were successful (there is more on why to free memory below).
  • Therefore, lines 25 - 27 free my memory.
  • My last for loop in lines 31 - 33 stores the integer of value "0" into each memory address, which was hopefully properly allocated in the previous steps, for each position in each "row" of my 2D array. The final return statement, returns a pointer to the 2D array. Since, the end of the function does not free the allocation of memory at the end of the code, and since the function returns the pointer to the allocated memory of the grid, the array remains in memory and can be accessed through utilizing the pointer that was originally defined in line 12.
  • Line 34 returns a pointer to the grid, which is a way to access the memory through returning the memory address.  The grid is not printed like the image above in the example, but it could be printed with a simple loop that printed each element of the array one at a time.

:calloc()

If you understand the function calloc(), you might realize that I could have simply used calloc()and then I would not have had to manually initialize the memory slots with the number "0." This is correct! Calloc initializes the memory addresses automatically with the character NULL character: '\0', which is integer 0 (zero).

return type

Another point to note about malloc() and calloc() is that they both return a void pointer (i.e. type void *). So, when malloc() or calloc() is called, the returned void pointer will be type casted automatically to whatever type of variable stores the return value.  In the function example that I used, this has the effect of the returned void pointer from malloc() being automatically type casted to type int *. Therefore, in the last for() loop of the example code, in lines 31 - 33, each time the index value is incremented, the system understands that it is working with an array of type integer, and therefore selects the proper memory addresses (4 bytes) to store the integer 0 for each iteration of the for loop.

:free()

You may have noticed that with dynamic allocation, it is best practice to free unused memory, but with static and automatic allocation, freeing memory is not a necessary step that needs to be coded in C language.  This is because with automatic allocation, the computer also automatically frees memory when it is not necessary to be utilized.  With dynamic allocation, if we do not specifically instruct the computer to free up the memory that we designated, then that memory will be unavailable for future processes within the running program.  In my above example of the function, alloc_grid(), which returns a grid of size width x height, the allocated memory is not be freed because in this way, another function can use the grid to store new values, simply print the grid, or do whatever else a 2D array can be used for.  As a side note, the return from the alloc_grid() function is a pointer because this is how the grid data is accessed from other functions; pointers are references to memory addresses.  If the engineer writing the program that uses the alloc_grid() function wanted to be most efficient, then when they were done using the grid, they would call the free() function on the grid, to free the grid's memory so that the memory formerly used for the grid could be used in other instances.  This would be accomplished by simply calling the function in this way: free(grid).  An example of a program that would not work properly unless memory is properly freed, is a program that continually takes input from a user or another source, which is then allocated into a width x height grid.  Such a program could theoretically continue infinitely if the program properly frees the memory used to create the grids.  However, without properly freeing memory, such a program would begin to return NULL (in the example above, this would happen in lines 17 - 20, or in lines 22 - 23) due to having insufficient memory to allocate for new grids because all the old grids would still be taking up all the available memory.

Posted in C Programming Language, code and tagged , , .