System calls

Before starting System call, we will start with OS. Operating System(OS) is a software that manage system resource and provide reliability to users. The Key service provided by OS are,
1. Controlling execution of process
2. Scheduling process in a fairly manner
3. Allocating Main Memory for process
4. Allocating Secondary memory for efficient storage and retrieve data and
5. Allowing process control over peripherals devices.

Application process can't access hardware without the help of Kernel. The below figure shows the privilege levels and communication path.

System call is a primary mechanism for application to interact and request kernel to provide service. So if user want to access system hardware it request system call. When System call get called, it initiate software interrupt/trap. Which makes CPU to switch over from user mode to kernel mode. Interrupt number of software interrupt is 0x80. Below is an example how system call is implemented in assembly language.

/*size_t write(int fd, const void *buf, size_t count)*/

mov edx,count ; message length

mov ecx,buf  ; message to write

mov ebx,fd  ; file descriptor

mov eax,4  ; system call number (sys_write)

int 0x80  ; call kernel

C wrapper function is used, in order to avoid repeated implementation of above code for different system calls. There are lot of pros and cons for using wrapper functions. To add a new system calls you need to build Linux kernel source and then follow the below steps,

1. add entry in "arch/x86/syscalls/syscall_64.tbl". If you are using x86_64 bit system.

# <number> <abi> <name> <entry point>

323    common    test_syscall    sys_test_syscall

2. add "sys_test_syscall()" declaration in "include/linux/syscalls.h". asmlinkage means the function should expect its arguments on the stack rather than in registers.

asmlinkage long sys_test_syscall(void);

3. add definition of "sys_test_syscall()" in a new or existing file.
In our case we added this function in test_syscall.c in directory test_syscall in <kernel_source>

#include <linux/kernel.h>

#include <linux/linkage.h>



asmlinkage long sys_test_syscall(void) {

    pr_err("Successfully created syscall!!\n");

}

4. Make sure the file is build by default. by Adding suitable changes in Makefile

<KERNEL_SOURCE>/test_syscall/Makefile



obj-y    := test_syscall.o



<KERNEL_SOURCE>/Makefile

....

core-y    := usr/ test_syscall/

5. Compile and load the kernel, after compiled kernel get loaded.
Create a c file to call the syscall.

#include <stdio.h>



int main() {

    syscall(323);

    return 0;

}

6. test_syscall kernel print get printed which can be seen in kernel log.

[  2185.076091] Successfully created syscall!!

Here we successfully created the system call. If you need further clarification please comment my blog.

Booth’s algorithm: Multiplication of two unsigned numbers and signed numbers

Here, I am going to share how multiplication is done inside processor. Due to evolution of human mind, There may be better and different way to do.

Each and every method have some pros and cons, If we choose first it is quite complicated to implement the same in processor as everything in processor is Logic High and Logic Low. For the second one, it take O(multiplier) times and you need to take care in choosing lower value as multiplier. Third method shows multiplication done using Logic High(1’s) and Logic Low(0’s). If you look into third one, every times 1’s and 0’s are multiplied with the multiplicand and shifted left (2 power n) times. Where n is the position of bit used by multiplier.

Below figure, explains how Multiplication is done for two unsigned numbers.

Lets understand the concept first, for example, take 6(0b0110) as multiplicand and 2(0b0010)as multiplier and Initial value of Accumulator and Carry bit are zero.

Step 1:

Check the Last bit of multiplier(i.e. 2) if it is 0 proceed else jump to step 2. Right shift Accumulator, Multiplier and carry in such a way that last bit(LSB) of Accumulator jump to first position(MSB) of Multiplier, Carry bit jump to first position(MSB) of Accumulator and Last bit of Multiplier is left alone. We can also do the same thing using left shift which use additional memory compare to this method.

Count = Count + 1

Accumulator = 0b0000

Multiplier = 0b0001

Step 2:

Now check again the last bit of multiplier if it 1. Add multiplicand with Accumulator and store the result in Accumulator.

Accumulator = 0b0110

After that do the Right shift Accumulator, Multiplier and carry in such a way that last bit(LSB) of Accumulator jump to first position(MSB) of Multiplier, Carry bit jump to first position(MSB) of Accumulator and Last bit of Multiplier is left alone.

Count = Count + 1

Accumulator = 0b0011

Multiplier = 0b0000

Step 3:

Do the Above steps until count reach the size of multiplier.

Count == 4

Accumulator = 0b0000

Multiplier = 0b1100

And the Result will be,

Result = Accumulator(4bit MSB) | Multiplier (4bit LSB).

Result = (0b0000 << 4) | 0b1100 = 0b00001100 = 12.

The above method will not be applicable to solve multiplication of negative number. What we can do is convert both multiplier and multiplicand to positive numbers, perform the multiplication then take 2’s complement of the result.

The above figure is the advance method used for multiplication of two signed or unsigned numbers.

Here, is how the above method multiply two signed/unsigned numbers.

Here is the C source code, for the above algorithm

#define BYTE                 8

#define SET_MSB_BIT(x)       ((x) << (BYTE -1)) 

#define TWOS_COMPLEMENT(x)   ((~x) + 1) 

short multiply(unsigned char multiplicand, unsigned char multiplier) { 

    unsigned short result = 0;

    /*Accumulator, intial value is assigned as zero*/

    unsigned char ACC = 0; 

    unsigned char M = multiplicand; 

    unsigned char Q = multiplier; 

    /*Number of bits in a byte*/

    unsigned char count = BYTE; 

    /*Q-1, intial value assigned as zero*/

    bool Q_prev = 0; 

    /*Q 0*/

    bool Q_0 = 0;

    /*Accumulator MSB bit*/

    bool ACC_msb = 0; 



    do { 

            Q_0 = Q & 1; 

            if (Q_0 ^ Q_prev) {

                    /*Check xor truth table*/ 

                    ACC = ACC + (Q_0 ? TWOS_COMPLEMENT(M): M); 

            }

            /*Right shift Q by one*/ 

            Q = Q >> 1;

            /*store Q_0 value as Q_prev*/

            Q_prev = Q_0;

            /*Store MSB bit of ACC*/

            ACC_msb = ACC & SET_MSB_BIT(1);

            /*Set MSB bit of Q, if ACC LSB bit is set*/

            Q |= SET_MSB_BIT(ACC & 1);

            /*right shift Accumulator*/

            ACC = ACC >> 1;

            ACC |= SET_MSB_BIT(ACC_msb);

            count--;

    } while(count > 0);

    result = Q | (ACC << BYTE);

    return result;

}

/*example code for division for unsigned number*/

#define SIZE_HWORD (16) /*bits*/ 

 

struct division { 

    unsigned short quotient; 

    unsigned short reminder; 

}; 

 

struct division divide(unsigned short divisor, unsigned short dividend) { 

    struct division result; 

    unsigned short ACC = 0; 

    unsigned short M = divisor; 

    unsigned short Q = dividend; 

    short count = SIZE_HWORD; 

    bool Q_0 = 0; 

    bool Q_msb = 0; 

 

    do { 

        /*Assign Q_0 ,i.e. LSB bit as 1*/ 

        Q_0 = 1; 

        /*store MSB bit of Q as Q_msb*/ 

        Q_msb = (Q & (1 << (SIZE_HWORD -1))); 

 

        /*left shift Acc by 1*/ 

        ACC = ACC << 1; 

        /*ADD Q_msb to the LSB of ACC*/ 

        ACC |= Q_msb; 

        /*left shift Q by 1*/ 

        Q = Q << 1; 

 

        /*subtract ACC with M*/ 

        ACC -= M; 

 

        /*check ACC is negative, 

        if so revert the value back. ADD zero to Q_0*/ 

        if ((short)ACC < 0) { 

            ACC += M; 

            Q_0 = 0; 

        } 

        Q |= Q_0; 

        /*decrement count*/ 

        count--; 

    } while (count > 0); 

    result.reminder = ACC; 

    result.quotient = Q; 

    return result; 

}

Thanks for viewing my blog, please post your comment.

Function call – stack implementation

Hi,

I like to share in depth of how stack grows and how it look like.

Lets take the below example,

#include<stdio.h>

int foo(int a, int b, int c) {

        int sum = 0;

        sum = a + b + c;

        return sum;

}

int main() {

        foo(10,20,30);

        return 0;

}

When you compile and run this code, crt0 will load your file into memory and check for the entry to get start. By default entry is main so the function get start from main() function. Inside main() function we have called function foo(), so the caller is main() and callee is foo(). After executing the statements in foo(), it need to return back to main(), i.e the one who calls(caller). The scope of the variable defined inside the function is limited to lifetime of the function. In order to avoid violation, the two dedicated CPU registers ebp(Base Pointer), esp(Stack Pointer) control its. So how does the two register control scope of variable and function calls. Here is pictorial representation of Caller calling callee and how the stack get updated.

From the above figure, I have mentioned Higher address and Lower address too show that the stack grows but in downward. So when Caller calls Callee it PUSH the argument from right to left into stack and it left a WORD size for return. If Callee return value greater than size of WORD then return hold the address of location where it getting stored. Base pointer is otherwise knows as frame pointer for the function, and stack pointer hold the maximum limit of the function. Whenever you call PUSH the stack pointer get updated first and value is loaded next. When you return back from callee the base pointer and stack pointer get updated to the caller. But the callee’s content are still in memory which may be override when caller call another function or swapping happens. During unwinding phase it doesn’t update the stack with zero.

Here is some questions to think.

1. When you defined an array inside a function how it get assigned into memory, whether index zero pushed first or the index last?

2. When you implement a recursive function did you face a stack over flow? If so how will you find the stack size(RLIMIT)? – getrlimit()

3. Create a function foo() which return datatype int, define a variable foo_i of datatype int inside foo with value 100 to it and return foo_i. Similarly define another function bar() same as foo() and variable bar_i similar to foo_i but undefined. Increment the bar_i and return bar_i. Consolidate the both foo() and bar() returns to a variable and print it.

Oops!! I haven’t explained the code written on the top. will leave that as an assignment to you.

Steps to Apply Patches to Kernel

Here I am going to share the steps to apply patches to kernel. interesting is it.

Step 1: Clonning
Clone the latest Linux kernel from kernel.org, I prefer source from Linus
# git clone git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git

Step 2: Branching
After cloning the linux kernel, It is better to create a new branch
# git branch
Switch to new branch
# git checkout

Step 3: Apply Changes
Make some changes and Check the difference
# git diff

Step 4: Commit
Commit the Changes
# git commit -a

A good commit message look like below things
———————————————————————
Header line: explain commit in one line

Body of commit message in few lines of text, explaining things
in more detail, like background about the issue being fixed, etc.
The Body of the message should not exceed 70 lines.

Reported-by:
Signed-off-by: Your Name <youremail@yourhost.com>

example:
Subject:[PATCH] Makefile: Change text to contain text

As a part of example, text field in Makefile is changed to text.
This is just an example, I think you can explain better than me.

Signed-off-by: Nobel Sharanyan J <nobelsharanyan86@gmail.com>
———————————————————————

Step 5: Generate Patch
Create the Patch
# git format-patch master..
or you can use something like
# git format-patch –stdout origin/master

Step 6: Cross check the patch before sending
Check whether patch is error free and ok to submit
# ./scripts/checkpatch.pl .patch

Step 7: whom to mail
# ./scripts/get_maintainer.pl .patch
the above command will list down the maintainers email id.

Step 8: How to mail,
To send mail you can use either mutt or git
if your are using git sendmail follow this,
# git config –global sendemail.smtpuser
# git config –global sendemail.smtpserver smtp.googlemail.com
# git config –global sendemail.smtpencryption tls
# git config –global sendemail.smtpserverport 587
# git config –global sendemail.smtppass

to cross check whether config is written correctly check “~/.gitconfig”

Step 9: Test mail.
Try a test mail not to maintainer, no need to distrub them
# git send-email –to <name>@gmail.com –cc <name>@gmail.com .patch

check the mail. hurray!! ready to send patch to linux.

view git log using below command,
git log
git log –oneline
There are lot of better comments, better google it or refer some books.

Now you follow the same process to apply patches to kernel, instead of to add maintainer in to list

Counting number of bit sets in an integer (Hamming Weight)

There is always a multiple ways to get a solutions for given problem and I am not going to argue this is the best.

int count_number_of_bit_set(unsigned value) {

    unsigned int shift[] = {1, 2, 4, 8, 16};

    unsigned int magic_number[] = {

                                   0x55555555,

                                   0x33333333,

                                   0x0F0F0F0F,

                                   0x00FF00FF,

                                   0x0000FFFF};

    unsigned char i = 0;

    for (; i <= 4; i++) {

         value = (value & magic_number[i]) +

                 ((value >> shift[i]) & magic_number[i]);

    }

    return value;

}

Let understand the logic inside the code,

The above picture is drawn to explain the concept for a byte. which can be extended for multiple bytes by applying the above concept.

If you like my blog, Please comment your views and feedback.