Heap Memory concepts in C

Heap Memory

è Also called as dynamic memory, is an alternative to the local stack memory

Heap Memory	Local stack Memory
Manual allocation and deallocation Programmer explicitly request the size of the memory needed	Automatic allocation and deallocation Allocation à when function call Deallocation à when function exists
Programmer has much greater control of memory The blocks of memory can be requested of any size
More work
More bugs

The heap is an area of memory available to allocate areas ("blocks") of memory for the program.

Heap Manager:

Heap memory is managed by the library code called “heap manager”, used to keep track of the free blocks (available for use) and currently used blocks by the program and size of these blocks. The entire heap is free initially. Programmer requests block of memory to the Heap Manager by using library functions like malloc(), realloc() and calloc(). Heap memory can be freed by using free().

The prototypes of these functions are available in <stdlib.h>

The memory requests (memory allocation functions) like malloc() returns NULL pointer if the heap memory is full.

void* malloc(unsigned long size);
size à requested size of the block in bytes
Returns pointer to the newly allocated heap block if successful.
Returns NULL if heap is full

void free(void* heapBlockPointer);
Takes argument as pointer to the heap block and returns this block to free pool for later re-use.

How allocation functions works? It requests block of memory in the heap of a particular size. The heap manager chooses a free block, and marks this area as “in use” in its private data structure, and returns a pointer to this heap block. And, heap manager will not allocate the same block to another request. Once the block is allocated, it is the owner responsibility to clear the old content in that block. We have one memory allocation function (calloc() in c) which sets the allocated blocks to all zeros.

Each allocation request reserves a contiguous area of the requested size in the heap and returns a pointer to that new block to the program.

The heap manager has its own, private data structures to record what areas of the heap are committed to what purpose at any moment the heap manager satisfies each allocation request from the pool of free memory and updates its private data structures to record which areas of the heap are in use.

How deallocation works? It is opposite to the allocation function. The owner makes deallocation request to return the heap block to the heap free area. The deallocation function takes the pointer to the heap block, which is returned by the allocation function. This pointer should be the same pointer returned earlier by the allocation function.

When the program is finished using a block of memory, it makes an explicit deallocation request to indicate to the heap manager that the program is now finished with that block.

The heap manager updates its private data structures to show that the area of memory occupied by the block is free again and so may be re-used to satisfy future allocation requests.

Memory Leaks:

If programmer forgets to deallocate the allocated heap memory then the program said to have a memory leak, that leads to abnormal behavior based on the allocation requests.

It is a serious problem if the program runs indeterminate amount of time, that results in continuous heap requests but there are no deallocation requests and the heap memory becomes full.

Garbage Collector

It takes over the most of the responsibility for Heap Management at the cost of little extra time taken at runtime. The programming lang like Perl and Java has the feature called Garbage Collector.

BootROM and Bootloader concepts

BootROM

Permanent code written on the Read Only Memory (ROM) of the Microcontroller, allow the device to Boot(Bootloader’s job) and Initialized all the peripherals, IOs and some hardware components.

Since it is written on read only memory, this code cannot be update or change.

It contains the very first code which is executed by the processor on power-on or reset. à Bootloader’s job is to find this code

Bootloader

>> BootROM contains the very first code which is executed by the processor on power-on or reset.

Bootloader is computer program which is responsible for finding and loading the final OS or a firmware which is supposed to run on the chip.

One main difference from BootROM is that it's usually in writable flash and can be replaced or upgraded.

Bootloader main task: load the kernel into RAM from flash memory.

Specifically, the boot loader was/is responsible for setting up an ATAG list that describing

the amount of RAM,

a kernel command line,

and other parameters.

One of the most important parameters is the machine type. With device trees, an entire description of the board is passed, in turn controlling the board only.

Since there is no standard mechanism for loading the OS (or first code), we use Bootloader to locate first code. This code can be found in flash memory, hard drives etc.

Bootloader is no longer present after it loads the OS.

Bootstrap loader

Bootloader: After power on , the Bootloader is controlling the board and does not rely on the linux kernel on any way.

Bootstrap loader:  performs checksum verification of the linux kernel and also does the decompression and relocation of the kernel to the system memory.

The bootstrap loader acts as a glue between the Bootloader and the linux kernel.

[Kernel Programming #5] Passing command line arguments to module

How to pass command line arguments to module.
We know argc/argv in C programming to pass command line arguments.

In kernel programming also, we have set of macros to do this task. They are,
module_param(name, type, permissions)
module_param_array(name, type, number_pointer, permissions)
and, we have other macros also, will discuss it later.
These macros are defined in <linux/moduleparam.h>.

Example: insmod module_2.ko variable_name=value, variable_name2=value

The argument name is the name of the variable declared in the module. The variables which we can define through command line option should be declared as global variable only. The name which we use in command line argument should match with the defined variable name in the module. Instead, we have another macro to set the name of the command line argument different from the variable name in the module.

module_param_named(command_line_var_name, actual_var_name, type, permissions)

The argument type is the type of the variable. It might be int, long, short, byte, uint, ulong, ushort, charp and bool.
charp: is used in case of string variable. The kernel copy and store the string passed by user in memory and points the actual variable to this memory.
Example:
static char *student_name;
module_param(student_name, charp, perm);

Instead, if we want to copy/store the string into the memory which is pointed by the actual variable then we can use another macro.

module_param_string(command_line_var_name, actual_var_name, len, permissions)
Example:
static char student_name[len];
module_param_string(studentname, student_name, len, perm);

The argument permissions is used to set read/write permissions for the variable.
Typical value would be 0644 (owner can read, write, group can read, everyone can read).

Kernel can also accepts the array by using the macro module_param_array.
The extra argument number_pointer is a pointer to an array_datatype in which the kernel stores the number of entries stored into the array.
Example:
static int students_marks[count];
static int marks;
module_param_array(students_marks, int, &marks, perm);

Program: module_param.c

1. #include<linux/module.h>
2. #include<linux/init.h>
3. #include<linux/moduleparam.h>
4. 
   
5. static int param_int = 999;
6. static char *param_string = "KERNEL";
7. static int param_array[3] = {-1,-1,-1};
8. static int count = 0;
9. static char param_string_len[10];
10. 
    
11. module_param(param_int, int, 0);
12. module_param(param_string, charp, 0);
13. module_param_string(param_string_len, param_string_len, 10, 0);
14. module_param_array(param_array, int, &count, 0);
15. 
    
16. static int __init module_param_init(void) {
17.         int i;
18. 
    
19.         printk(KERN_INFO "param_int: %d\n", param_int);
20.         printk(KERN_INFO "param_string: %s\n", param_string);
21.         printk(KERN_INFO "param_string_len: %s\n", param_string_len);
22.         for (i = 0; i < (sizeof(param_array)/sizeof(int)); i++)
23.                 printk(KERN_INFO "param_array[%d]: %d\n", i, param_array[i]);
24. 
    
25. return 0;
26. }
27. 
    
28. static void __exit module_param_exit(void) {
29.         printk(KERN_INFO "module_param_exit:\n");
30. }
31. 
    
32. module_init(module_param_init);
33. module_exit(module_param_exit);

Build: Please refer to previous posts to build the module, need to setup makefile.

Makefile for this program:

obj-m += module_param.o

KDIR = /usr/src/linux-headers-2.6.32-28-generic

all:

        $(MAKE) -C $(KDIR) SUBDIRS=$(PWD) modules

clean:

        rm -rf *.o *.ko *.mod.* *.symvers *.order

Experiment_1: insmod module_param.ko

Output: dmesg
[17046328.638809] param_int: 999
[17046328.638812] param_string: KERNEL
[17046328.638814] param_string_len:
[17046328.638816] param_array[0]: -1
[17046328.638818] param_array[1]: -1

[17046328.638819] param_array[2]: -1

Experiment_2: insmod module_param.ko param_int=111 param_string="PRACTICE" param_string_len="PEOPLE" param_array=11,22,33

Output: dmesg

[17047110.761552] param_int: 111

[17047110.761555] param_string: PRACTICE

[17047110.761557] param_string_len: PEOPLE

[17047110.761559] param_array[0]: 11

[17047110.761561] param_array[1]: 22

[17047110.761562] param_array[2]: 33

How to build the module, how to write makefile and how to insert module using insmod, and how to check the log ? Please refer the below posts for detailed explanation:

Kernel Programming stack

Reset/Recovery Ubuntu System Password

Ubuntu System Password recovery

We can reset the password (forgotten password) of your ubuntu system in FIVE simple steps.

Step1: Restart the system. Press Esc button when you see the message like "GRUB Loading ...". Then we will see the root shell window.

Step2: Select the recovery mode option in the root shell and then "Recovery menu" will be appeared on the screen then select "Drop to root shell prompt" option.

Step3: We will see a terminal
root@(none):/#
root@(none):/# passwd <user_name>

Example: If username of your system is hacker then please type passwd hacker and press enter.
Once you enter correct username, it is request you to set new password.
Please set your password.

Step4: Now, type sync and press enter
Step5: finally type reboot -f and press enter

You are now successfully reset your ubuntu system password.

[C Programming #3] Print all combinations of given array with given size

Problem: Print all possible combinations of given array with given combination size limit.

Input:
array: 10 11 12 13 14
combination size: 3

Output:
10 11 12
10 12 13
10 13 14
11 12 13
11 13 14
12 13 14

Program:

1. #include<stdio.h>
2. 
   
3. void print_combinations(int a[], int n, int r) {
4. int i,j,k;
5. for (i = 0; i <= n-r; i++) {
6. for (j = i+1; j+r-1 <= n; j++) {
7. printf("%d\t", a[i]);
8. for (k = 0; k < r-1; k++)
9. printf("%d\t", a[j+k]);
10. printf("\n");
11. }
12. printf("\n");
13. }
14. }
15. 
    
16. int main()
17. {
18.   int a[] ={10,11,12,13,14};
19.   int n=sizeof(a)/sizeof(a[0]);
20.   print_combinations(a, n, 3);
21.  
22. return 0;
23. }

[Kernel Programming #4] container_of() macro usage in Kernel

The container_of() function in Kernel:

It is a macro, used to find the starting address of the structure by using its own member variables. We use this macro to retrieve the structure given the details of the pointer points to one of its member variables.

It accepts three arguments and returns start of address of the required structure type specified in the argument list.
Its definition is

#define container_of (ptr, type, member) ({ \
         const typeof( ((type *)0)->member) *__mptr = (ptr); \
         (type *)( (char *)__mptr - offsetof(type, member) );})

Arguments:

1. ptr: refers to the name of the pointer
2. type: structure name & type
3. member: refers to the name of the structure member

Below example would help us to understand the usage of this macro.

struct my_container {
   int some_data;
   /*
    * members list
    */
   int some_other_data;
}

Now, we have function1(), where this structure is used like below.

function1() {
/* other_code */

int *new_ptr_data = my_container_ptr->some_other_data;
function2(new_ptr);

/* other code */
}
And, we are passing new_ptr variable to another function2(new_ptr).
In the function2(), we need to access the other members of the structure of type struct my_container. But, we should not pass this structure in the argument list of function2().
So, the use of container_of macro comes into the picture now.

In function2(), we can retrieve the structure by using container_of macro like below.

function2(int *new_ptr){
     struct my_container *my_container_ptr =
                              container_of(new_ptr, struct my_container, some_other_data);
    /*
    * use my_container_ptr to access the members
    */
    /* other_code */
}

If you see the argument list of container_of macro, found the 3rd argument is some_other_data, since the new_ptr is pointed to this member only. So, we should specify this member as 3rd argument.
If the new_ptr is pointed to some_other_data2 (for example) then we should specify 3rd argument as some_other_data2 only.

[Kernel Programming #3] __init* macros usage

If you look at the previous kernel programming concepts #1 and #2, you will find a macro __init at the initialization function.
This post will tell us the importance of this macro in the Kernel.
Please go through the previous Kernel Programming post #1 and Post #2.

__init* macro role in Kernel:

If you declare initialization function with __init macro then the compiler puts this function in ".init.text" section.
Similarly, if you declare any variable with __initdata macro then the compiler puts the variable in ".init.data" section.

The macro __init* tells the compiler to put the functions and the variables if any declared using this macro, in a special section which is declared in vmlinux.ids.

The function which is used for initialization purpose and it is used only once during the kernel boot can be declare using __init macro.
Once a function is declared using __init macro then its memory is freed after this function is called and the task of this function is over. The function free_initmem() will do the task of memory cleanup.
If you look at the kernel log, we can find the below message which is an example of memory cleanup.
Freeing unused kernel memory: xxxk freed
The function free_initmem() will free the text and data sections that are associated with the function (if the function declaration uses __init macro)
This functionality is very useful in memory optimization, since it allows kernel to free the memory which is occupied by the init function and this function is not used anymore.