My VIM settings

My vimrc file

set tabstop=8
set expandtab
set shiftwidth=8
set wrap
set textwidth=80
set smartindent
set autoindent
set shiftround
set hlsearch
set columns=80
set nobackup

Advertisements

Starting with git and github

Setting up git repository on github

1. create and initialize a git repository

[root@user git_client]# git init new_repo.git

2. change directory

[root@user new_repo.git]# cd new_repo.git

3. Set your username for git repository

[root@user new_repo.git]# git config --global user.name "Github_UserName"
ex:  # git config --global user.name "xyz"

4. Set your email id

[root@user new_repo.git]# git config --global user.email "your_email@youremail.com"

Check the git configuration

[root@user new_repo.git]# git config -l

5. Do the following

[root@user new_repo.git]# git remote add origin https://github_username@github.com/userName/repo_name.git
ex:
 # git remote add origin https://xyz@github.com/xyz/new_repo.git

6. Check updated url

[root@user new_repo.git]# git remote -v (to check)

7. Append following lines in .git/config

[ branch "master"]
        remote = origin
        merge = refs/heads/master

8. Create new file and make changes

[root@user new_repo.git]# touch new_file

9. Add new file in staged area

[root@user new_repo.git]# git add new_file

10. Commit the changes in newly local git repository just created

[root@user new_repo.git]# git commit -m "commit msg"

11. Now try to push directory to github. You would get following error

[root@user new_repo.git]# git push origin master
Password:
error: The requested URL returned error: 403 while accessing https://kashishbhatia@github.com/kashishbhatia/pqr.git/info/refs
fatal: HTTP request failed

12. Now login to github account and create a empty repo(with same name) in github account

13. Now try to pull the empty repo. It fails

[root@user new_repo.git]# git pull origin master 
Password: 
fatal: Couldn't find remote ref master

14. try again with “git pull”. It passes.

[root@user new_repo.git]# git pull 
Password: Your configuration specifies to merge with the ref 'master' 
from the remote, but no such ref was fetched.

15. Now finally push your changes to github repository

[root@user new_repo.git]# git push origin master 
Password: 
Counting objects: 3, done. 
Writing objects: 100% (3/3), 202 bytes, done. 
Total 3 (delta 0), reused 0 (delta 0) 
To https://github_username@github.com/userName/repo_name.git 
* [new branch] master -> master

Pull the updates done in repository

# git pull

To refresh and pull changes done by other clients on a shared repository

# git pull --rebase origin master

Clone an existing repository from github

 # git clone https://github_username@github.com/github_username/repo_name.git

Sometimes while cloning a repository from github you can get following error

[root@user rep_folder]# git clone https://github_username@github.com/username/new_repo.git
Initialized empty Git repository in /home/kashish/Desktop/git_client/reps/sleep_in_kernel/.git/
error: Could not resolve host: github.com (Domain name not found) while accessing https://github.com/kashishbhatia/sleep_in_kernel.git/info/refs

fatal: HTTP request failed

If you face this kind of problem while cloning the repository, do check if there are any http proxy enabled on your machine. Unset it and try again

[root@user rep_folder]# git config --global --unset https.proxy
[root@user rep_folder]# git clone https://github_username@github.com/username/new_repo.git
Initialized empty Git repository in /home/user/Desktop/reps_folder/new_repo/.git/
Password:
remote: Counting objects: 17, done.
remote: Compressing objects: 100% (15/15), done.
remote: Total 17 (delta 2), reused 15 (delta 0), pack-reused 0
Unpacking objects: 100% (17/17), done.

Delete a local repository

[root@user rep_folder]# git branch -D local_branch

Delete a remote repository

[root@user rep_folder]# git push origin :remote_branch

OR

[root@user rep_folder]# git push origin --delete remote_branch

FUDCon 2015, Pune

I went Pune to participate in FUDCon 2015 and it was a wonderful experience for me.
I came to know about the event through one of my friend and after going through the details, I decided to participate in the event. I submitted the talk proposal on FUDCon website and fortunately my talk got accepted in the main event.

I left for Pune on 24th June via KSRTC bus at night and reached Pune nearly at noon, the next day. Bus dropped me at Swargate bus stop.
All the speakers stay was arranged at Cocoon hotel, Magarpatta city by FUDCon organizers, so I headed towards Cocoon hotel from Swargate . Thanks to the organizers for arranging accommodation and for being so welcoming.

Next Day on 26th June, I had to present my talk on “Linux IO : Native SCSI target implementation in linux kernel”. You can find the slides here. Frankly I was little nervous but was also excited as this was the first time I was presenting a technical paper in any event.

And the day finally arrived : Day 1 of FUDCon 2015
In the morning, before leaving for the event, the organizers gave some cool fedora bottles and bags to each speakers 🙂

When I reached MIT college (the venue of the event), I was amazed, as the event started phenomenally well . Many students and open source enthusiasts arrived (even from other cities) to attend the FUDCon event.

There were three tracks focusing on storage, cloud and container technologies, respectively scheduled for three days of the event.
I attended sessions on Glusterfs and ABI compatibility before lunch. My talk was scheduled after lunch and I got a really good response. I was not hoping that I would be able to explain the significance and intricacies of SCSI targets but the interest shown by the audience proved me wrong. I found students very curious to understand the topic. Some of the students even approached me after the session to know more about the topic.

Day 2
I observed only focused audience (interested students and people from Software companies). There were some cool sessions and workshops scheduled on openstack and linux systems on second day. I attended “Zero to Hero kernel module development” by Suchakra and “contributing to openstack” by Rohan. Both the talks were very informational.
Day 2 finished up and we all headed to BlueO for FUDPub. We did bowling, played foosball and danced till we got tired 😛

Day 3
Third day was focused on container related workshops (Docker, project atomic, kubernetes, etc). I attended mostly all container workshops and they were really enlightening for newbies who want to sink their heads in container technologies 🙂

As an addendum, I can just say that it was a great event and I really enjoyed, made new friends, interacted with open source enthusiasts and contributors and got inspired. Thanking all the FUDCon organizers and volunteers for this laudable endeavor and giving me opportunity to participate in FUDCon 2015.

Splay trees and its applications

It is also a BST and self balancing tree like AVL and red-black trees but is used
in real-world applications where out of 100, 80 times the data which is queried
is 20% data in the database.

This tree implemenation not just balances the tree, to get insertion/deletion/search to complete
in O(log n) time, but also move recently accessed the data to the root. This way
frequent access to the same data will take O(1) time in next access.

Having said that, still the algorithm will result in O(log n) amortized time complexity.

Comparison between AVL, Red-Black and Splay trees

AVL and red-black trees only balances tree when tree is changed(insertion or deletion)
On contrary, Splay trees balances tree in read-only operation (like search) also.Splay tree does not have to keep extra book-keeping information in the data structure like AVL trees (height) or red-black trees (color)

Red-black trees are also balanced but less balanced than AVL trees.
Red-black trees are used in applications where insertion and deletion are frequent operations.Where as AVL trees are used for quick searching as searching takes O(Log n) because tree is balanced.

Due to insertion and deletion, tree need rebalancing. Hence if application involves
more insertion and deletion operations then AVL trees is not a best choice.
Use red-black trees instead for quick insertion and deletion.

Splay trees are also less balanced than AVl trees. Sometimes splay trees can even become less balanced than red-black trees. Why ? Because due to splaying operations they may result becoming skew trees.
Splay trees are generally used for fast searching (like AVL trees). In both AVL and splay trees, performance remains O(log n) only. But the basic difference is that AVL trees take O(log n) for every search operation whereas but splay trees can take O(1) time for frequently searched items.

Applications of Splay trees

  • Due to their reference of locality property, they can be used in implementing logic behind caches.
  • They can come handy in joining two trees – merging a tree between 2 elements of another tree (O(log M + N))
  • Also they can be used in bifurcating the data into 2 distinguish data sets – cutting a tree
  • Can be used in garbage collectors
  • Querying faster than O(log(N)) for highly biased query distributions
  • Used in network router (aprt from other data structures like Hash tables, trie, etc)

Advantages

  • Amortized O(log n) performance
  • Requires no extra book-keeping info
  • Can handle duplicate data (unlike other trees like AVL, red-black)

Disadvantages

  • Cannot be used in multithreading applications as even read-only(search) operations also alter the tree structure. Allowing multiple threads to search keys may corrupt the trees.

Implementation

Find my code here.

Reference

AVL trees and its applications

Introduction

AVL trees are self balancing binary search trees (BST).
To determine whether the tree is balanced, the height of left and right subtree is checked for each node in the tree.
The BST is considered to be balanced if |H(L) – H(R)| <= 1, where H(L) and H(R) are height of left and right subtree of a node respectively.
In other words, left and right subtrees need to be AVLs, for tree to be AVL.

Height of node in AVL = |H(L) – H(R)| <= 1

Need of AVL tree

Binary search trees have a cool property of segregating and organizing data, so that decisions to be taken at every node (while traverse) are binary. Due to this property, the search time in BSTs is
O(log n).
But BST cannot control the order in which data comes for insertion. Due to this, sometimes BST becomes skew.
Ans as we know that search in BST highly depends on height of the tree. when height is log n, the search will complete in log n time.
Having said that,  AVL trees also cannot control the order in which data comes for insertion, but they can re-arrange data in tree, so the searching times can reduce to O(log n) again. By rearrangement, AVL trees reduce the height of tree to log n

Red-Black trees vs AVL trees

Though this post focus on AVL trees, it is worth mentioning some of differences between AVL trees and Red-Black trees.
AVL trees are used frequently for quick searching as searching takes O(Log n) because tree is balanced.
Where as insertion and deletions are comparatively more tedious and slower as at every insertion and deletion, it requires re-balancing.
Hence, AVL trees are preferred for application, which are search intensive.
For application which involves more insert and delete operations, AVL trees are not a best choice.
For frequent insertion and deletion, red-black trees are used.
Red-black trees  are also balanced trees but comparatively less balanced than AVL trees.
In subsequent posts, I will try to explicate more on red-black trees.

Implementation

In AVL trees, at every decision we query height of the node. Hence AVL data structure also stores height of the node.

Ways the tree Rotates to re-balance

LL and RR rotation

 

1

LL means when new node inserted in left of left subtree – rotate right
RR means when new node inserted in right of right subtree – rotate left

LR and RL rotation

2

 

 LR means when new node inserted in right of left subtree – rotate left and then rotate right
 RL means when new node inserted in left of right subtree – rotate right and then rotate left
Tip: confused about LR and RL, read these in reverse to know the right case
but rotate the order LR is written i..e
For LR – R of L and rotate L then R
Check out my AVL tree C implementation here

Applications

As mentioned above, AVL trees are used for frequent insertion. One of the examples I know of is it is used in Memory management subsystem of linux kernel to search memory regions of processes during preemption.

Reference

Local labels in C Programming

Introduction

Everybody who has programmed in C must be knowing about “goto” and “labels“.
In GCC, there is something called local labels which restrict the scope of label and do cool stuff.
Linux kernel internal APIs extensively use local labels.

Comparison between Labels and Local Labels

Conventional labels in gcc have function scope. Where as local label can be scoped to a nested block.
Conventional Labels cannot be declared more than once in a function and that is where
local labels are used.

In complex function implementations, program often want to jump to an instruction and handle each jump
differently for different cases. In such cases local labels could be a good choice.

Example Code

Macro with local label
Macro without local label declared

Now if u call “MACRO_WITH_LOCAL_LABEL()” from any function it won’t give any compilation errors

where as calling “MACRO_WITHOUT_LOCAL_LABEL()” would give following error


[root@blr-1st-1-dhcp446 3. gcc_local_labels]# gcc -c try.c
try.c: In function ‘main’:
try.c:63: error: duplicate label ‘not_empty’
try.c:53: note: previous definition of ‘not_empty’ was here
try.c:63: error: duplicate label ‘empty’
try.c:53: note: previous definition of ‘empty’ was here
try.c:63: error: duplicate label ‘exit’
try.c:53: note: previous definition of ‘exit’ was here

Pre-processor stage successfully completes but compilation stage gives error.

Existing example

As mentioned earlier in the post, Linux code uses it these techniques in debug codes to keep track of instruction pointers etc.
For instance check usage of following macros in the code :

#define _THIS_IP_  ({ __label__ __here; __here: (unsigned long)&&__here; })

Many internal APIs of linux kernel like kmalloc() etc. call this macro to track caller function address.
Now what is this “&&__here” ? Just in brief, this is address of label, which you can store in pointers. COOL ! Isn’t ?

Using serial ports to capture logs in virtual machines

Introduction

Most of the virtualization products provide ability to attach virtual serial ports these days.
There are two ways you can use serial ports in virtual environment.
  • Using physical serial ports on host computer
  • Using file on host computer
I would throw some light on connecting virtual serial ports to files on host computer.
Usecase
Some beneficial usecases –
  1. For Administrators – In case of servers running multiple applications on guests. On application failures, or virtual machine failures, instead of using physical serial ports to redirect logs on some other system, we can use virtula serial ports for each VM, which would redirect logs on files residing on host(server).This way admins can easily track the progress/working/behavior of application by tracking logs.
  2. For Developers – For kernel developers, most of the times it is difficult to get the logs when any absurd issue strikes their way and makes their life uneasy to get to the issue. There are several methods to captures logs. But what about the case when kernel crashes during boot itself ? Would you be able to capture the logs locally to find whats fishy inside the kernel component ? Well I think Yes !!! Moreover the following techniques would also helpful to eradicate problems when logs get rolled over in the system as they are too much in number.

Using file on host computer (VMware Workstation)

Following are the steps to enable redirection of logs on host computer

  • Changing grub settings.

Go to /boot/grub/grub.conf and edit the config file by adding
“console=ttyS0 console=tty0 ignore_loglevel”  parameters.

  • Virtual machine settings

a) Add a new serial port for the VM and use Output File option.
b) Mention the location of log file(on host) in File Path textbox.

Grub Settings
VMware workstation settings

Using file on host computer (Oracle VirtualBox Manager)

  • Changing grub settings.

Go to /boot/grub/grub.conf and edit the config file by adding
“console=ttyS0 console=tty0 ignore_loglevel”  parameters.

  • Virtual machine settings

a) Add a new serial port for the VM and name it as COM1.
b) Select port mode as Raw file.
c) Mention the location of log file(on host) in File Path textbox.

Grub Settings
VM settings