How to Compile the First Version of Git on Linux

Here, we will learn how to use git, the widely-used version control system initially developed by Linus Torvalds for Linux kernel development.

First, obtain the software git by
$ sudo apt-get install git -y

Next, clone git repository from GitHub by
$ git clone https://github.com/git/git

When download is complete, it will have create a folder, so let's enter.
$ cd git

Well, we could simply build the current version of git, but for the sake of learning how to use git and getting the taste of what it is capable of doing, let's check out the very first version of git written by Linus in 2 weeks.

To do this, we first need to search for different commits:
$ git log --oneline

Now, scroll the to the very bottom by pressing 'end' key several times.When you reach the end, press 'q' key. You should see the following output:
e83c516 Initial revision of "git", the information manager from hell

This is the very first version (present in the repository). Let's check out this version by
$ git checkout e83c516

Now, you will see that the files in the folder have been de-dated back to 2005! How do I know? Well, run
$ git log

Because we will make changes and commit this soon, we will create a branch here, so simply run
$ git checkout -b ver1.0

Let's take a look at what branches we have now
$ git branch
Note that ver1.0 branch has been added, where master is the current version of git.

There are only a handful of files here at this very early stage. Feel free to read Linus' code. When done, let's compile. First, you will need to install libraries:
$ sudo apt-get install libssl-dev zlib1g-dev -y

When you run
$ make

It will probably complain about some define references. We will need to edit the Makefile file and include some libraries:
$ vim Makefile

Add -lz and -lcrypto parameters for LIBS flag, so line #11 should read
LIBS= -lssl -lz -lcrypto

Save the file and let's try to compile again
$ make

This should compile! Now, let's commit the change to the local repository:
$ git add Makefile
$ git commit -m "edit Makefile to compile in Ubuntu 14.04LTS"

To go back to the current version of git, we check out the master branch$ git checkout master

To go back to the compilable first version of git, simply run
$ git checkout ver1.0

I will go through some more advanced git tutorials later.

Changing Linux Swappiness

As the RAM price is going down very fast, most modern computers can be equipped with plenty of RAM, perhaps more than enough for most of people using RAM-efficient operating systems, such as Linux. I personally have 8GB of RAM installed, and I barely use even half of this unless I run virtual machines.

However, for whatever the reason, I still find some instances where my Linux system makes use of the swap space although I have plenty of RAM still unused. Here, I will show you how to minimize the use of the swap space. After all, accessing RAM should be incomparably faster than accessing the hard disk drive or solid state drive, so you probably want to minimize swap usage if your system has a plenty of RAM installed.

There is a variable called swappiness in Linux that determines the likelihood of swap to be used by the system. This value is saved in /proc/sys/vm/swappiness file. So, to check your system's swappiness value, simply run
$ cat /proc/sys/vm/swappiness

The default will be most likely 60. You may want to adjust this to 0 to minimize.
$ sudo echo 0 > /proc/sys/vm/swappiness

That's it!

Installing Android Studio on Ubuntu and Debian 64bit

Update: refer to official documentation from Google.


First, download the zip file from Google
http://developer.android.com/sdk/index.html

I downloaded the All Android Studio Packages for Linux at the very bottom.
Then, in the download folder, unzip the zip file
$ cd ~/Downloads
$ unzip -x android-studio-ide-*.zip

We also need Oracle JDK 1.7, so download this as well.
http://www.oracle.com/technetwork/es/java/javase/downloads/jdk7-downloads-1880260.html

Download jdk-7u79-linux-x64.tar.gz file. Unzip it as well.
$ tar xzvf jdk-7u79-linux-x64.tar.gz

This will create jdk1.7.0_79 folder. You can either leave this folder here or move it to the system folder. I personally moved it to
$ sudo mv jdk1.7.0_76 /opt/

Now, we need to set the environment JAVA_HOME to point to this folder. To do this, either
$ export JAVA_HOME=~/Downloads/jdk1.7.0_76
or
$ export JAVA_HOME=/opt/jdk1.7.0_76
depending on where you put the folder. To make this permanent, refer to my previous post.

Now, to run the Android Studio, you simply run the script in the android-studio/bin folder
$ ./android-studio/bin/studio.sh

This is not it yet. You will probably encounter some error saying
Unable to run mksdcard SDK tool.
while additional setup & installation within Android Studio because it will depend on some of 32bit libraries. Therefore, you will need to install the following 32bit libraries as well
$ sudo apt-get install lib32z1 lib32ncurses5 lib32bz2-1.0 lib32stdc++6

Update: For Debian Jessie or Ubuntu 16.04, run
$ sudo apt-get install lib32z1 lib32ncurses5 lib32stdc++6

Now, you will be able to successfully install and run Android Studio and related packages.

Connect to L2TP/IPSEC server (VPN) from Ubuntu

Step 1, install necessary package
$ sudo apt-get install openswan xl2tpd

Step 2, create a backup of /etc/ipsec.conf file
$ sudo cp /etc/ipsec.conf /etc/ipsec.conf.bk

Step 3, copy the following to the config file and modify according to the comment
$ sudo vim /etc/ipsec.conf

version    2.0

config setup
       virtual_private=%v4:10.0.0.0/8,%v4:192.168.0.0/16,%v4:172.16.0.0/12 
       nat_traversal=yes
       oe=off
       protostack=netkey
       # replace eth1 below with your network interface
       plutoopts="--interface=eth1"
   
conn L2TP-PSK
        authby=secret
        pfs=no
        auto=add
        keyingtries=3
        dpddelay=30
        dpdtimeout=120
        dpdaction=clear
        rekey=yes
        ikelifetime=8h
        keylife=1h
        type=transport
        # replace with your ip address below
        left=your_ip_address
        leftnexthop=%defaultroute
        leftprotoport=17/1701
        # replace with the server ip address below
        right=server_ip_address
        rightprotoport=17/1701

Note that in order to find out your network interface and ip address, you can simply do
$ ifconfig

Step 4, create a backup of /etc/ipsec.secrets
$ sudo cp /etc/ipsec.secrets /etc/ipsec.secrets.bk

Step 5, add the following line and modify according to the comment
$ sudo vim /etc/ipsec.secrets

# replace with your ip address, server ip address, and pre-shared key below
your_ip_address server_ip_address : PSK "pre-shared_key"


Step 6, create a backup of /etc/xl2tpd/xl2tpd.conf
$ sudo cp /etc/xl2tpd/xl2tpd.conf /etc/xl2tpd/xl2tpd.conf.bk

Step 7, copy the following to the conf file and replace with the server ip address
$ sudo vim /etc/xl2tpd/xl2tpd.conf

[lac l2tpd]
lns = server_ip_address
ppp debug = yes
pppoptfile = /etc/ppp/options.l2tpd.client
length bit = yes


Step 8, create /etc/ppp/options.l2tpd.client with the following and enter username and password
$ sudo vim /etc/ppp/options.l2tpd.client

ipcp-accept-local
ipcp-accept-remote
refuse-eap
require-mschap-v2
noccp
noauth
idle 1800
mtu 1410
mru 1410
defaultroute
replacedefaultroute
usepeerdns
debug
lock
connect-delay 5000
name user_name
password user_password


Step 9,create a route to the server by typing the following and replacing the values accordingly
$ sudo ip ro ad server_ip_address via your_default_gateway

In order to find out your default gateway, simply run
$ route


Step 10, you will need to restart the services in order to apply the changes in the settings
$ sudo invoke-rc.d ipsec restart
$ sudo invoke-rc.d xl2tpd restart


Step 11, create a shell file for connection
$ vim connect_l2tp.sh

ipsec auto --up LT2P-PSK
echo "c l2tpd" > /var/run/xl2tpd/l2tpd-control

Step 12,  create a shell file for disconnection
$ vim disconnect_l2tp.sh

echo "d l2tpd" > /var/run/xl2tpd/l2tp-control
ipsec auto --down L2TP-PSK


Step 13, set the shell files excutable
$ sudo chmod u+x connect_l2tp.sh
$ sudo chmod u+x disconnect_l2tp.sh


You are finally ready! To establish the connection, simply run the shell
$ sudo ./connect_l2tp.sh


To disconnect, run the disconnect shell
$ sudo ./disconnect_l2tp.sh


Finally, you should be able to check the status via
$ ip link
where if connection has been established, then it will be indicated by link/ppp.

How to Debug Qemu

In order to debug Qemu, one first runs the -s and -S options in qemu:
$ qemu -s -S -hda hda.img

This will pause qemu and wait for gdb connection tcp port 1234.


Open up another terminal and run the following db command
$ gdb
(gdb) target remote localhost:1234


Now, we may want to setup the break point. If you want to setup the break point as soon as the system starts, that is memory address 0x7c00, so set the break point and continue!
(gdb) b *0x7c00
(gdb) c

How to Find Assembly Code for Master Boot Record (MBR)

For IBM-compatible PCs, MBR is the first set of instructions during the boot process. In order to view the assembly code stored in MBR, one can do the following:

First, find out the file system by
$ df -h

This provides the name of the hard disk, either hda1 or sda1. The MBR is located in the very first sector of the hard disk (or solid state drive) so we will remove the number (which indicates the partition) in the following command.
$ sudo dd if=/dev/sda of=MBR.bin bs=512 count=1

This will create a raw file MBR.bin on the current directory which is the exact copy of the MBR of the computer.

Now, to examine this file, we use objdump
$ objdump -D -b binary -m i8086 MBR.bin


If you want intel syntax, add -M intel option
$ objdump -D -b binary -m i8086 -M intel MBR.bin

Note that the last two bytes should be 0x55 and 0xAA, which make up the boot signature that tells BIOS that this disk is bootable.

Setting System-Wide Environment Variables in Linux

When I download binary files that I would like to add to the PATH variable, I could simply edit ~.bashrc file. However, this will not be executed if I were to run from GUI programs, such as nautilus. In fact, this is what happened to me:

I wanted to learn Java, so I downloaded eclipse binary which should be run using Java. Well, I did not have Java installed, so I simply downloaded JDK binary files from Oracle and I edited ~/.bashrc file to add the JDK bin folder to the PATH environment. I then tried to run eclipse binary from Caja (which is MATE version of nautilus), but I got an error saying that Java could not be found in the PATH environment. This is because the environment variables are process-specific, so editing the ~/.bashrc added the Java binary folder to the PATH environment specific to the bash process, but not to the Caja process.

So, now I want to add the JDK binary folder to the system-wide PATH environment variable. To do this, I need to create a shell script in /etc/profile.d folder. Here, I added a file set-path.sh with the following line where JDK_binary_folder means refers to where JDK has been installed, such as /opt/jdk1.7.0_76.

export PATH=$PATH:JDK_binary_folder

After logging out and re-logging in, I simply double-clicked the eclipse binary from Caja, and it finally ran it without complaints!

There is another option for this. In Ubuntu, /etc/environment is a file that also sets the system-wide environment variables. Thus, one can edit the file by
$ sudo vim /etc/environment
and add the system environment as desired.

Efficient Binary Tree to Sorted Doubly Linked List Conversion Recursive Algorithm

I would like to share my own algorithm for converting a binary tree data structure to a sorted doubly linked list using recursion. I believe this is a very easy and efficient way to achieve the goal.

// Tree.java

public class Tree {

private static class Node {

int data;

Node left;

Node right;

/** Node constructor that adds the data

* 

* @param newData is the data to be inserted

*/

Node (int newData) {

data = newData;

left = null;

right = null;

}

}

private Node root;

Tree () {

root = null;

}

/** insert a new data into the tree incapsulation method 

* 

* @param newData is the data to be inserted

*/

public void insert (int newData) {

root = insert(root, newData);

}

/** insert data actual implementation method

* in this version of binary tree, the data will be appended

  * to the right tree if it is equal

* 

* @param node is the current node

* @param newData is the data to be inserted

* @return the node in which newData is inserted

*/

private Node insert (Node node, int newData) {

if (node == null)

node = new Node (newData);

else if (newData < node.data)

node.left = insert (node.left, newData);

else // if (newData >= node.data)

node.right = insert (node.right, newData);

return node;

}

/** convert a binary tree data structure into a sorted

* doubly linked list structure

* this encapsulates the actual implementation and

* takes care of the last linking process

* 

* the head of the doubly linked list will be saved in root

*/

public void convertTree() {

Node temp = root;

root = null;

temp = convertTree(temp);

// root holds the latest node

linkNodes (root, temp);

root = temp;

}

/** actual implementation method for the converting 

  * algorithm by recursion

  * will link the current node and the previous node

  * 

* @param node is the current node

* @return the head of the doubly linked list

*/

private Node convertTree(Node node) {

if (node == null)

return null;

Node ret = convertTree(node.left);

if (root == null)

// this is the first node

ret = node;

else 

// root holds the previous node

linkNodes (root, node);

root = node;

convertTree(node.right);

return ret;

}

/** a simple helper method to link two nodes into a list

* 

* @param a is the smaller list element

* @param b is the very next list element

*/

private void linkNodes (Node a, Node b) {

a.right = b;

b.left = a;

}

}

The basic idea is this: I will recursively enter into nodes in the increasing order. For each node, I will double-link its node and the previous node; the previous node is saved in the root field. After linking, the method will save its current node into the root field. This will take care of the doubly-linked list except for the first and the last nodes. For the last set of linking process, I make sure to work it out in the encapsulation function.

The reason I am saving the current (or previous) node in the root field is because Java does not have a static local variable within a method. I could, of course, create a new field for this purpose, but I did not want to do so just for this functionality. In order to use only the resources that are available to me, I decided to temporarily make use of the root field as a local static variable.

In order to determine whether I have reached the starting node (i.e., the node with the smallest data value), I check whether the root field is null, because root is set to null in the encapsulation method as an initialization. Once I reach the starting node, I set the root field to point to the current (or previous depending on the context) node.

This algorithm, I believe, is fairly fast because there is no waste of node assignment here in the linking process; that is, for every pair of nodes, there is only one set of linking assignments (i.e., 2) needed, so exactly 2N node assignments are required for a binary tree of size N.

Binary Tree Data Structure in Java for C/C++ Developers

Binary tree data structure is one of the fundamental data structures that appears in the beginning of the computer science course. In this post, I will explain a very simple binary tree class implementation in Java. As someone who has come from C/C++ language, it was a wonder for me how Java implements binary tree data structure, for Java supposedly does not have the concept of a pointer. However after studying Java for some time, it appears to me that Java actually does make use of pointers extensively. All the primitive data types, such as int, char, boolean are passed by its values while all objects are passed by reference. It turns out that Java's implementation makes it easier for programmers to write code at the expense of perhaps sacrificing the speed compared to C/C++; with C/C++ programmers have the maximum capability to manipulate every single details of the code and optimize for speed boost whereas with Java programmers are stuck with Java's built-in optimization.

In any case, here is the Java code for implementation of the tree class

// Tree.java

public class Tree {

private static class Node {

int data;

Node left;

Node right;

/** Node constructor that adds the data

* 

* @param data to be inserted

*/

Node (int data) {

data = data;

left = null;

right = null;

}

}

private Node root;

Tree () {

root = null;

}

/** insert a new data into the tree incapsulation method 

* 

* @param data to be inserted

*/

public void insert (int data) {

root = insert(root, data);

}

/** insert data actual implementation method

* in this version of binary tree, the data will be appended 

  * to the right tree if it is equal

* 

* @param node is the current node

* @param data to be inserted

* @return the node in which data is inserted

*/

private Node insert (Node node, int data) {

if (node == null)

node = new Node (data);

else if (data < node.data)

node.left = insert (node.left, data);

else // if (data >= node.data)

node.right = insert (node.right, data);

return node;

}

/** lookup data incapsulation method

* 

* @param data to be searched within the tree

* @return the total number of nodes that contain the data

*/

public int lookup (int data) {

return lookup (root, data);

}

/** lookup data actual implementation method

* 

* @param node is the current node

* @param data is the data to be searched

* @return the number of nodes containing the data in the 

  * subtree starting from node

*/

private int lookup (Node node, int data) {

if (node == null)

return 0;

else if (node.data == data)

return lookup (node.right, data) + 1;

else if (data < node.data) 

return lookup (node.left, data);

else 

return lookup (node.right, data);

}

}

Any experienced C++ programmers should immediately understand what the code is doing and what each method is doing. For actual implementation of the binary tree, below is the Main class that builds a tree from Tree.java

// Main.java

public class Main {

/** main method

* 

* @param args is the argument strings passed from the user

*/

public static void main(String[] args) {

Tree binaryTree = new Tree();

binaryTree.insert(2);

binaryTree.insert(1);

binaryTree.insert(-2);

binaryTree.insert(1);

System.out.println("lookup(1) = " + binaryTree.lookup(1));

  }

}

Short Circuit Expressions in C/C++ and Java

It was quite embarassing for me today. For more than 10 years since I started learning C language, I have not even heard of "short-circuit evaluation" until today. Today, I was studying a simple BinaryTree program in Java, and I encountered somewhat peculiar problem; I actually thought I found some sort of Java's fundamenetal error, but oh well. I was the culprit.

If you see a code below, what would you guess the output is?

public class ShortCircuit {
    private static boolean funcReturningTrue () {
        System.out.println ("this function returns true");
        return true;
    }
    private static boolean funcReturningFalse () {
        System.out.println ("this function returns false");
        return false;
    }
    
    public static void main (String[] args) {
        if (funcReturningTrue() || funcReturningFalse())
            System.out.println ("eval 1 complete");
            
        if (funcReturningFalse() && funcReturningTrue())
            ;
        else
            System.out.println ("eval 2 complete");
            
        boolean bool = (true) ? funcReturningTrue() : funcReturningFalse();
        System.out.println ("bool = " + bool);
    }
}

Well, I naively thought that both static methods inside if () evaluation would be called; I was wrong. It seems that there are some short-circuit implementation in order to save run time. For example, (true || bool) is evaluated to be true regardless of bool, so C/C++ and Java will not even evaluate bool. That is, only funcReturningTrue() will be called in the code above for the 1st if statement.

Similarly, (false && bool) is false regardless of bool, so again bool will not be evaluated. This corresponds to the 2nd if statement in the code above.

Lastly, the statement (condition) ? a : b will evaluate only a or b but not both depending on the condition. If one were to make sure that both conditions to be evaluated in the examples above, one should use | and & in place of || and &&.

Now, one can easily predict the output of the program above:
this function returns true
eval 1 complete
this function returns false
eval 2 complete
this function returns true
bool = true

Setting gdb's Assembly Code as Intel or AT&T Style

When debugging with gdb, one often looks at the assembly code of the binary file. Here, I will show how to do this and change the output as either 'intel' or 'att' format.

I have a simple helloworld program a.out that I'd like to debug. To do this, enter
$ gdb -q a.out

To read the assembly code of the function main, I would type in
(gdb) disass main

However, the default is in the 'att' format, which isn't my taste. To switch to 'intel' format, I'd type in
(gdb) set disassembly-flavor intel

If you'd like to make this change permanent, simply create a file .gdbinit in your home directory with the command that you want gdb to run every time it initialises.
$ echo "set disassembly-flavor intel" > ~/.gdbinit

That's it! Obviously, you may replace 'intel' with 'att' if you want to switch back to 'att' format.

Pointer vs Array - Possible Memory Leak

Usage of pointers is probably the most common source of error and vulnerability in C; this is why subsequent programming languages invented afterwards relinquish the concept of a pointer.

I personally like the concept of pointers because they are very useful and efficient in many ways, such as in a tree data structure. Furthermore, it helps me better understand how the code works at the low level in more details; it is my belief that a good programmer should know both the low level and high level sides of a system.

At the same time, I admit that one needs to be very careful with pointers because improper use of pointers will lead to a disaster. Here, I would like to give an example of such improper use of a pointer that will lead to memory leak.


People often interchangeably use pointers and arrays. Below is example1.c code:

#include <stdio.h>
int main () {
   char *str1 = "pppp";
   char str2[] = "aaaa";
   printf ("%s\n%s\n", str1, str2);
   return 0;
}

The code compiles with no error or warning:
$ gcc example1.c -o example1 && ./example1
pppp
aaaa


OK. As you may have expected, the string can be either a pointer or an array; there seems nothing wrong with this. So, is it true that you can interchangeably use the pointer or the array to define a string? The answer is NO.


In the above example, str1 is a pointer to "pppp", which is allocated outside the function main stack. In other words, the variable str1 is a local variable in main, but it points to "pppp" that is saved in the memory outside the main's scope. On the other hand, str2 is a local variable array which saves the string value "aaaa".


Let's examine the memory using gdb. Before that, we need to compile the source with -g option in gcc to supply symbols:
$ gcc -g example1.c -o example1


Next, run gdb and examine str1 and str2:
$ gdb -q example1

Reading symbols from example1...done.

(gdb) b 6

Breakpoint 1 at 0x80484b3: file example1.c, line 6.

(gdb) r

Starting program: /home/linuxnme/Documents/

pppp

aaaa

Let's examine the memory content of &str1

(gdb) x/wx &str1

0xbffff570: 0x08048560

In my case, 0xbffff570 is the memory address of the variable str1, which stores the content 0x08048560; this address is where the string "pppp" is saved.
(gdb) x/s str1

0x8048560: "pppp"

Let's examine &str2 now.

(gdb) x/wx &str2

0xbffff577: 0x61616161

(gdb) x/s &str2

0xbffff577: "aaaa"

Can you tell the difference now? Let's quit gdb with
(gdb) q

Quit anyway? (y or n) y

Now in order to examine memory leakage, let's consider example2.c code:

#include <stdio.h>
char* array() {
   char string[] = "aaaa";
   return string;
}
char* ptr() {
   char *string = "pppp";
   return string;
}
int main() {
   printf ("%s\n", array());
   printf ("%s\n", ptr());
   return 0;
}

Let's compile and run it. When compiling the code, your compiler should warn you that the function returns the address of the local variable.
$ gcc example2.c -o example2 && ./example2

?

pppp

As you can see, when a string is defined as an array in a local function, it is saved in the function's stack and therefore it is completely cleared out when the function returns. However, if a string is defined as a pointer, then the string is saved outside the function's scope, and therefore it will remain in the memory. This is the memory leak in the program. Here, it is only a 5-byte memory leak, but it can get worse very quickly if the function is called multiple times during its run. Although I only demonstrated this with a char string, it could be of any data types including structures or classes.

So, the main lesson here is never define anything directly from a pointer, especially in a local function because it will lead to memory leak.