Writing character device driver

#include<linux/init.h>
#include<linux/device.h>
#include<linux/module.h>
#include<linux/fs.h>
#include<asm/uaccess.h>
#include<linux/string.h>
#include<linux/cdev.h>
MODULE_LICENSE("GPL");
#define DEVICE_NAME "mychardev"
struct cdev *mydevice;
struct class *myclass;
static char Buffer[256];
static ssize_t device_read(struct file *file,char *buffer,size_t length,loff_t *offset);
static ssize_t device_write(struct file *file,const char *buffer,size_t length,loff_t *offset);
static int device_open(struct inode *inode,struct file *file);
static int device_release(struct inode *inode,struct file *file);
static struct file_operations fops=
{
    .read=device_read,
    .write=device_write,
    .open=device_open,
    .release=device_release,
};
static int hello_init(void)
{
    int error;
    mydevice=cdev_alloc();
    if((error=alloc_chrdev_region(&mydevice->dev,0,1,DEVICE_NAME)))
    {
        printk(KERN_ALERT "\nThere is problem in allocating the chrdev region.");
        return error;
    }
    mydevice->ops=&fops;
    mydevice->owner=THIS_MODULE;
    if((error=cdev_add(mydevice,mydevice->dev,1))<0)   
    {
        printk(KERN_ALERT "\nThere is a problem in adding cdev.");
        return error;
    }
    if((myclass=class_create(THIS_MODULE,DEVICE_NAME))==NULL)
    {
        printk(KERN_ALERT "\nThe class creation failed.");
        return -15;
    }
    device_create(myclass,NULL,mydevice->dev,NULL,DEVICE_NAME);
    printk(KERN_ALERT "\nThe device created successfully");
    return 0;
}
static int hello_exit(void)
{
    printk(KERN_ALERT"\nTrying to exit.");
    device_destroy(myclass,mydevice->dev);
    class_destroy(myclass);
    unregister_chrdev_region(mydevice->dev,1);
    cdev_del(mydevice);
    printk(KERN_ALERT "\nExiting the device successfully.");
    return 0;
}
static int device_open(struct inode *inode,struct file *filep)
{
    printk(KERN_ALERT "\nThe device has been opened successfully.");
    return 0;
}
static int device_release(struct inode *inode,struct file *filep)
{
    printk(KERN_ALERT "\nThe device has been closed successfully.");
    return 0;
}
static ssize_t device_read(struct file *file,char *buffer,size_t length,loff_t *offset)
{
    size_t totalbytes;
    long bytesnotcopied;
    totalbytes=strlen(Buffer);
    bytesnotcopied=copy_to_user(buffer,Buffer,totalbytes);
    return totalbytes-bytesnotcopied;
}
static ssize_t device_write(struct file *file,const char *buffer,size_t length,loff_t *offset)
{
    size_t bytesnotcopied;
    bytesnotcopied=copy_from_user(Buffer,buffer,length);
    printk(KERN_ALERT "%s ",Buffer);
    return (length-bytesnotcopied);
}
module_init(hello_init);
module_exit(hello_exit);


-------------------------------------------------------------------------------------------------------------------------------------

What are all the headers for ??

i. linux/init
       It is used for module_init() and module_exit(). Actually, these are macros and it tells the compiler that module_init() is used by the driver when it is loaded. It can be later on deleted as it will be having no other functions besides at start up. The module_exit() is used to deallocate the resources which we allocated when loading the driver through init functions.
ii.linux/device
      This header is used as the struct class and struct device are described here. These are actually needed to create a node in the filesystem like /sys. The struct class create a class entry in the class directory in the /sys with the name specified with DEVICE_NAME (in the above example). Similarly, the device is used to create a actual device node. The class is generally the accumulation of different devices.
iii.linux/module
     This header is needed as it is in this header that MODULE_LICENSE(), MODULE_AUTHOR(),etc are all described.
iv.linux/fs
     The file related operations and the struct file_operations is described in here.
v.asm/uaccess
     The inline duo functions copy_from_user and copy_to_user are described here. These two are used to take care of virtual memory as the address we are referring to might not be actually present but rather be need to swept out from the disk. Furthermore, it checks the validity of the pointer that is provided form the user space. First it checks it the read/write permission is there and it also checks if the pointer lies in the address space of the process. And it is architecture dependent thus will be present inside arch/(any architecture)/asm/uaccess.h
vi. linux/cdev
     The structure cdev is defined here.
----------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------------
alloc_chrdev_region() : This function is used to dynamically allocate the device number for the device( i.e. Major and Minor). The best thing about it is that it is safer to user as there is no chance of contradicting the Major number with the existing one. There is another variation to this
register_chrdev_reigion() : If we are sure that we are not violating the Major number that is not using the same as other drivers then we can statically allocate the device using register_chrdev_region().
cdev_alloc() : It is used to allocate the memory for the struct cdev structure.
cdev_add():  It adds the struct cdev passed and makes it lives immediately.
class_create(): It is used to create an entry in the class directory in /sys.
device_create(): It is used to create a device entry.
copy_from_user():
copy_to_user(): described above
Similarly, all the other functions are used in the exit module to release the resources allocated in the init module.
---------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------------

The mistakes I made 

i. Always include MODULE_LICENSE(" ") either "GPL" or "Dual BSD/GPL" .This is because the kernel and all the proprietary codes are released under "GPL" license so if you are using it or modifying or doing anything with it. The code must be in compliance with "GPL" license so we declared. If we forget to give MODULE_LICENSE(), we will get several errors.
ii. Run the user level program as root user or as the user who inserted the modules.
---------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------------

Inserting into the kernel

i. Building as a module

Write a make file in any directory,
obj-m := chardevices.o
all:
    make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules
clean:
    make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean
Then run $make in the terminal.
Once it is built then use
$sudo insmod ./chardevices.ko
The sudo here is mandatory without which we cannot insert it.
Similarly, *.ko should be used not *.o.

ii.Building as a part of the kernel

i. Go to the linux/device/char/chardevices (this is our directory)
Create a directory and copy a code in this directory.
Write a Makefile here,
obj-$(CONFIG_MY_CHAR)    := chardevices.o

ii. In the Makefile of linux/device/char add the following line 

obj-$(CONFIG_MY_CHAR) += chardevices/ (this is usually to specify the directory)

iii. Now, go ahead in linux/device/char and modify the Kconfig to add our configuration ie MY_CHAR

config MY_CHAR
    tristate "This is my character device"
    default y
    help

(give anything)

Since we are using tristate, there can be three state viz:

i. m which means to build the driver as module and will not be the part of the kernel

ii. y which means to build the driver as a part of the kernel

ii. n

Linux System Call for Arm Architecture

Implementation of System Calls for Arm Architecture

 I have used Linux 3.2 version for this as I was testing my system call in Mobile phone so this system call procedure may not work for the newer release of kernel.
Step 1:
Add a system call number
path : /arch/arm/include/asm/unistd.h
e.g. :
#define __NR_my_add     (__NR_SYSCALL_BASE +377 )

Step 2: 
Make an entry to calls.S with path given below
path: /arch/arm/kernel/calls.S
e.g. :
CALL(sys_my_add); (the position has to be same as the system call number ie 377)
 This file will be automatically added to entry-common.S as the file entry-common.S include it as follows.
      .table
#include "calls.S"

(Alternatively)
We can define a wrapper function in entry-common.S and then register this wrapper function in calls.S. In the entry-common.S then finally we can jump to our system call routine.
path: /arch/arm/kernel/entry-common.S
e.g. :
In calls.S
CALL(sys_my_add_wrapper);  (the position has to be same as the system call number ie 377)
In entry-common.S,
Add the following code
START(sys_my_add_wrapper)
     b      sys_my_add
ENDPROC(sys_my_add_wrapper)

Step 3:
Writing the routine for system call. Again it can be done in two ways:
i. Directly it can be included in the existing files( so that it doesn't require us to modify the Makefile)
ii. Make a separate file and change the Make file to make sure it compiles.
eg:
asmlinkage long sys_my_add(int a,int b)
{
        printk(KERN_ALERT "The addition is %d ",a+b);
        return a+b;
}
If separate file (say my_add.c) is maintained we have to add the following line in the Makefile.
e.g.:
obj-y :=my_add.o

Step 4: 
Register the function with the prototype.
path: /include/linux/syscall.h
Add the following line:
asmlinkage long sys_my_add(int,int);

Implementation in User Space 

I have written a code in Assembly to call the function.
e.g.:
mov  r7,#377
mov  r0,#25
mov r1,#35
SWI 0
mov r7,#1
SWI  0

we can also replace the last three lines of code by using SWI 377 instead.

System Calls Implementaion in Linux (for both older and newer version) in x86

Implementation of System Call in Older Linux Version

Step 1:
Reserve a system call number
path: (inside linux source tree) /arch/x86/include/asm/unistd_32.h
Go to the end and add the system call number and also modify NR_syscalls by adding 1.
e.g. : #define __NR_my_add     350
Step 2:
Declare system call prototype
path: /arch/x86/include/asm/syscalls.h
go to : #ifdef CONFIG_x86_32 (for 32 bit) or common (for both 32 or 64 or ..._64
asmlinkage long sys_my_add(int,int);
Step 3:
Append system call address to sys_call_table
path: /arch/x86/kernel/syscall_table_32.S
Go to the last position, here I'm going to the 350th position (same position as call number) and write
.long sys_my_add
Step 4:
Implement syscall Routine
It can be done in one of the two ways:
i. Add the function to the existing source file ( you don't have to change the source file)
ii. Adding a source file ( however, modify the Makefile to compile this file too)
e.g.:
asmlinkage long sys_my_add(int a,int b)
{
        printk(KERN_ALERT "The sum is %d ",a+b);
        return a+b;
}
Now, This function can be added to any existing file. If so we are done but if we have created a file say my_add.c then don't forget to add following line in a Makefile where this code exist.
obj-y := my_add.o

Implementation of System Call in Newer Linux Version

Step 1:
Now, if you would follow the previous method you would be surprise to find that
/arch/x86/include/asm/unistd_32.h file doesn't exist. It does however exist but has been removed from there and is saved in generated directory which gets generated automatically. Rather now we have to follow to the following path to modify the system call table.
path: /arch/x86/sycalls/sycall_32.tbl
Now, the table is of the form as below:
<number> <api> <name> <entry point><compat entry point>
number: specify the system call number ie increase the count of the last system call by 1
api : in the case of x86 it is by default i386
name: name of the system call
entry point: it is the entry point for our system call
compat entry point: if our call has a compat entry point
eg:
350   i386   my_add    sys_my_add
After doing this automatically the system call number gets appended in unistd_32.h and we don't have to do anything.

Step 2:
Follow the step 2 of older version.

Step 3:
Follow the step 4 of older version.

Calling the system call from user space after building the kernel

#include<stdio.h>
#include<unistd.h>
int main()
{
        int a,b,c;
        a=35;
        b=45;
        c=sycall(350,a,b);
        printf("\nThe value of the sum is %d \n",c);
        return 0;
}

Part II: Threaded Binary Search Tree Traversal

Inorder

Algorithm:
Follow the tree towards the left, print the smallest value and then move on to print the next smallest value so that finally we will be printing all the value in the ascending order. This one can be achieved simply by using recursive algorithm as follows:
For the general binary search tree,
void inorder(struct node *tree)
{
    if(tree==NULL)
        return;
    inorder(tree->left);
    printf(" %d ",tree->info);
    inorder(tree->right);
}

However, the inorder code for Threaded binary search tree isnot as simple, the code is given below

struct node *inorder_successor(struct node *tree)
{
    struct node *temp;
    temp=tree->right;
    if(tree->isright==0) //here we are checking if the tree is a leaf ( not the temp)
        return temp;
    while(temp->isleft==1)
        temp=temp->left;
    return temp;
}
/*Thus, what we are doing in the above steps are first checking if the tree is a leaf. If so we are returning temp (which is right of the tree), otherwise we are going to find the inorder successor of that tree. */
void inorder(struct node *head_tree)
{
    struct node *tree;
    printf("\n\n");
    tree=head_tree->left;
    if(tree==NULL)
    {
        printf("\nNo element in the tree.");
        return;
    }
    while(tree->left!=head_tree)
        tree=tree->left;
    do
    {
        printf(" %d ",tree->info);
        tree=inorder_successor(tree);
        if(tree==head_tree)
            break;
    }while(1);
    printf("\n\n");
}

We are using two functions here, one for the traversal and one to find the inorder succesor after traversing any node. By the way, the traversal has started from the first inorder element. (not the root of the tree)

Preorder

In preorder, for any node we first print the value of the node and then follow its left and after printing all its left value we follow the right and print all the value.
For general binary search tree, the recursive algorithm is as follows:
void preorder(struct node *tree)
{
    if(tree==NULL)
          return;
    printf(" %d ",tree->info);
    preorder(tree->left);
    preorder(tree->right);
}
However, we do it in the similar fashion as inorder for the threaded binary trees by using two functions respectively to traverse and find the preorder successor. The code for the preorder traversal is given below:

struct node *preorder_successor(struct node *tree,struct node *head_tree)
{
    struct node *temp;
    if(tree->isleft==1)
        return tree->left;
    if(tree->isright==1)
        return tree=tree->right;
    while(tree->isright==0)
    {
        tree=tree->right;
        if(tree==head_tree)
            return head_tree;
    }
    return tree->right;
}
void preorder(struct node *head_tree)
{
    struct node *tree;
    tree=head_tree->left;
    printf("\n\n");
    if(tree==NULL)
    {
        printf("\nNo element in the tree.\n");
        return;
    }
    do
    {
        printf("  %d  ",tree->info);
        tree=preorder_successor(tree,head_tree);
        if(tree==head_tree)
            return;
    }while(1);
    printf("\n\n");
}

Postorder 

In the postorder successor, for any node we follow the left link and print all the values and then follow the right one and print all the values and finally print the value of that node.
For the general binary search tree, the postorder code is below
void postorder(struct node *tree)
{
    if(tree==NULL)
          return;
    postorder(tree->left);
    postorder(tree->right);
    printf(" %d ",tree->info);
}
However, for the threaded binary search tree, it is the trickiest. Following algorithm I used to write a code from the following address http://stackoverflow.com/questions/10694037/postorder-traversal-of-tree-without-using-recursion-or-stack

The algorithm goes as follows 

• A variable can be used to check type of current action.
• If action is left traversal and current node has a left descendant, then descendant is traversed. Otherwise action changed to right traversal.
• If action is right traversal and current node has a left descendant, action changed to left traversal. Otherwise action changed to visiting a node.
• If action is visiting node: current node is visited, afterwards its postorder successor has to be found.
• If current node’s parent accessible through a thread (i.e. current node is parent’s left child) then traversal is set to continue with the right descendant of parent.
• If current node has no right descendant, this is the end of the right-extended chain of nodes.
• First: the beginning of the chain is reached through the thread of the current node.
• Second: right references of nodes in the chain is reversed.
• Finally: chain is scanned backward, each node is visited, then right references are restored to previous settings.

 The code goes as follow
enum my_enum {LEFT_TRAVERSAL=0,RIGHT_TRAVERSAL,CURRENT_VISITING};
void chain_formation(struct node *tree)
{
    struct node *start_chain,*parent,*temp;
    parent=tree;
    start_chain=tree->left;
    if(start_chain->right==tree)
        printf("  %d  ",start_chain->info);
    while(start_chain->right!=tree)
    {
        temp=start_chain->right;
        start_chain->right=parent;
        parent=start_chain;
        start_chain=temp;
    }
    while(start_chain!=tree)
    {
        printf(" %d ",start_chain->info);
        temp=parent->right;
        start_chain=parent;
        parent=temp;
    }
      
}
void postorder(struct node *head_tree)
{
    enum my_enum traversal;
    struct node *tree,*parent;  
    tree=head_tree->left;
    printf("\n\n");
    traversal=LEFT_TRAVERSAL;
    int i=20;
    do
    {
        switch(traversal)
        {
            case LEFT_TRAVERSAL:
                        parent=tree;
                        while(tree->isleft!=0)
                        {
                            parent=tree;
                            tree=tree->left;
                        }
                        traversal=RIGHT_TRAVERSAL;
                        break;
            case RIGHT_TRAVERSAL:
                        if(tree->isright==0)
                        {
                            traversal=CURRENT_VISITING;
                            break;
                        }
                        parent=tree;
                        tree=tree->right;
                        if(tree->isleft==1)
                            traversal=LEFT_TRAVERSAL;
                        else if(tree->isright==1)
                            traversal=RIGHT_TRAVERSAL;
                        else
                            traversal=CURRENT_VISITING;
                        break;
            case CURRENT_VISITING:                  
                        if(parent->info>tree->info)
                        {
                            printf("  %d  ",tree->info);
                            tree=tree->right;
                            if(parent->isright==0)
                            {
                                parent=parent->right;
                                traversal=CURRENT_VISITING;
                            }
                            else
                                traversal=RIGHT_TRAVERSAL;
                        }
                        else
                        {
                            chain_formation(tree->right);
                            tree=tree->right;
                            if(tree->isright==0)
                                parent=tree->right;
                            traversal=RIGHT_TRAVERSAL;
                        }
                        break;
            default:
                        printf("\nWrong Input\n");
                        break;
      
        }
    }while(tree!=head_tree);
    printf("\n\n");
}

Part I : Threaded Binary Search Tree ( Definition and Insertion)

Usually, in the binary tree, we notice more null links than acutal pointer.
In a binary tree with n nodes, we have
    2n = total links
    n+1 = null links
We can make use of these null links to point other nodes in the tree as a result of which we can traverse a tree without thre requirement of having stack. It can facilitate the traversal of all three viz Inorder, Preorder and Postorder traversal without the need of extra memory required.
In the memory representation, we must be able to distinguish between threads and normal pointer. This is done by adding two extra bit fields isright and isleft.

isleft=1 if parent->left is a normal pointer.
isleft=0 if parent ->left is a thread.

isright=1 if parent->right is a normal pointer.
isright=0 if parent->right is a thread.

If the node->right_child==NULL, now we will replace it by a pointer to the node which would be printed after P when traversing the tree in inorder.
If the node->left_child==NULL, we will replace it by a pointer to the node which immediately precedes node P in inorder.

However, we will still be having two pointers viz the one in the extreme left(directly down the left line from root) and the one in the extreme right(directly along the right line from root). To prevent it we will assume a head node for threaded binary trees.
The actual tree is the left subtree of the head node. And these two NULL pointers in the extreme points to this head node as well.

The following code is to declare a node structure for the threaded binary search tree and the insertion of the node in that tree.



struct node
{
    int info;
    struct node *left,*right;
    unsigned int isleft:1;
    unsigned int isright:1;
};
/* Be pretty clear here use UNSIGNED otherwise if you will use 1 bit signed number then it will be 0 and -1 so in the subsequent comparison you have to use -1 instead of 1. If you will use 1 bit unsigned number then it will behave like a binary 0 and 1 bit.*/

void insert(struct node *head_tree,int num)
{
    struct node *tree,*temp;
    tree=head_tree->left;
    if(head_tree->isleft==0)
    {
        head_tree->left=(struct node*)malloc(sizeof(struct node));
        head_tree->left->left=head_tree;
        head_tree->left->right=head_tree;
        head_tree->left->info=num;
        head_tree->isleft=1;
        head_tree->left->isleft=0;
        head_tree->left->isright=0;
        return;
    }
    while(1)
    {
        if((tree->isleft==0 && tree->info>=num) || (tree->isright==0 && tree->info<=num))
            break;
        else if(tree->info>num)
            tree=tree->left;
        else
            tree=tree->right;
    }
    temp=(struct node*)malloc(sizeof(struct node));
    temp->info=num;
    temp->left=NULL;
    temp->right=NULL;
    temp->isleft=0;
    temp->isright=0;
    if(tree->info>num)
    {
        temp->left=tree->left;
        temp->right=tree;
        tree->left=temp;
        tree->isleft=1;
    }
    else
    {
        temp->right=tree->right;
        temp->left=tree;
        tree->right=temp;
        tree->isright=1;
    }
}