Use virsh to access kvm guest’s console

When we create bunch of virtual machines in kvm, you would found that using GUI tool to manage them waste time. We can use virsh to access the guest’s text console efficiently.

Step 1: check whether console device has been defined

virsh ttyconsole my_vm

If the output is shown(e.g. /dev/pts/41), it indicates the Guest has a console device already. Otherwise, define one with virsh edit. Here is an example to be added inside .

<console type='pty'>
  <target port='0'/>
</console>

Step 2: configure a serial console in the guest, in order that it will accept a connection

sudo vi /etc/init/ttyS0.conf

Add the configuration:

————————————————————————
# ttyS0 – getty
#
# This service maintains a getty on ttyS0 from the point the system is
# started until it is shut down again.

start on stopped rc RUNLEVEL=[2345]
stop on runlevel [!2345]

respawn
exec /sbin/getty -L 115200 ttyS0 xterm
————————————————————————
sudo start ttyS0

the “xterm” is your guest terminal type, you can figure out in guest by run

echo $TERM

My ubuntu 12.04 LTS’s terminal type is “Linux”, so I can replace “xterm” with “linux”

Step 3: then you can enjoy the convenience with

virsh console my_vm

Link: Ubuntu Official Document

Advertisements

Quickly create large file in linux

Usually in linux we need to quickly create large file in which we don’t care much about the content to do some test such as disk I/O test, then we can use:

fallocate -l 10GB test.bin

this system call would create a file with size 10GB named test.bin and contain random content quickly, because it only pre-allocate the space without write anything into it so that the heavy disk I/O is avoided.

Triangle Puzzle

Problem: By starting at the top of the triangle and moving to adjacent numbers on the row below, the maximum total from top to bottom is 27.

        5
      9   6
    4   6   8
  0   7   1   5

I.e. 5 + 9 + 6 + 7 = 27.
Write a program to find the maximum total from top to bottom by reading the triangle from text file. File would look like:

5
9 6
4 6 8
0 7 1 5

Solution: time complexity is O(n)
1. Read integers from file into an one-dimensional array.
2. From last level to second level and from leftmost integer to next-to-last integer in each level
3. Pick the larger one among current integer and its right neighbour, and add it up to the left adjacent integer on the row above.
4. Return array[0] (root) as maximum total

For above example:
Level 4: compare 0 and 7, add 7 to 4; compare 7 and 1, add 7 to 6; compare 1 and 5, add 5 to 8.
then level 3 would be: 11 13 13
Level 3: compare 11 and 13, add 13 to 9; compare 13 and 13, add 13 to 6.
then level 2 would be: 22 19
Level 2: compare 22 and 19, add 22 to 5.
then level 1 would be: 27
stop and return 27 as solution.

C/C++ code:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    //assuming that we know there are 100 levels in the file
    long *array = (long long*)malloc(sizeof(long)*6000);
    
    FILE *file = fopen("triangle.txt","r");
    
    if (file == 0) {
        printf("cannot open\n");
    }
    int i = 0;
    
    while (EOF != fscanf(file, "%ld", &array[i])) {
        i++;
    }
    
    //assuming that we know there are 100 levels in the file
    for(int j = 99; j > 0; j--)
    {
        for (int k = 0; k < j; k++) {
            if(array[j*(j+1)/2+k] > array[j*(j+1)/2+k+1])
            {
                array[j*(j+1)/2+k - j] += array[j*(j+1)/2+k];
            }
            else
            {
                array[j*(j+1)/2+k - j] += array[j*(j+1)/2+k+1];
            }
        }
    }
    printf("%ld\n",array[0]);
    
    return 0;
}

Link: from yodle’s website http://www.yodlecareers.com/puzzles/triangle.html

Linux boot sequence

Linux Boot Sequence:

——————————————————–

Power on the machine to initialize firmware
Pick one CPU as bootstrap processor
System is now in real mode only 1MB memory can be addressed
Use EIP and hidden offset to execute first instruction in reset vector
Jump to BIOS flash memory entry location routed by memory map on chip-set

——————————————————–

Now CPU run BIOS code
Invoke POST to test system components
Search bootable device through CMOS
Load MBR the first sector in that device to memory address 0x7c00
MBR contains primary boot loader and partition table

——————————————————–

Now CPU jump to 0x7c00 and run MBR code
First stage: search active partition and load its boot sector
This boot sector could understand Linux file system format
Use MBR’s plus boot sector’s boot loader to load another boot loader
Second stage: run the newest loaded boot loader
It read a boot configuration file e.g. grub.conf to show boot choices to user
All above boot loaders combined are called GRUB
Finally GRUB would load pick system’s image to memory
The image is split into two pieces:
small one in real-mode and compressed large one in protected-mode
GRUB could pass parameters to kernel header then jump to kernel entry point in real-mode

——————————————————–

Boot loader finished and Kernel stage start
The function flow:
start_of_setup(): basic hardware setup (arch/x86/boot/header.S)
go_to_protected_mode(): set CPU to protected mode (arch/x86/boot/main.c)
startup_32(): basic register setting (arch/x86/boot/compressed/head_32.s)
decompress_kernel(): decompress image (arch/x86/boot/compressed/misc.c)
Jump to kernel enry point in protected-mode
startup_32(): also called process 0, creat IDT and GDT, enable paging and initialize page table etc. (arch/x86/kernel/head_32.s)
start_kernel(): architecture-independent kernel start-up (init/main.c)

——————————————————–
start_kernel() do long list of initialization and then call rest_init()
rest_init(): (init/main.c)
-> kernel_thread(kernel_init): active remaining CPUs and creat first user-space process 1 to call init_post() and run /sbin/init .etc.(init/main.c)
-> kernel_thread(kthread): create kernel thread process 2 (init/main.c)
-> schedule(): context switch kick in p1 to invoke other process by checking configuration file (init/main.c)
-> cpu_idle(): when there is work to do it would be switched out (init/main.c)

resource:
http://duartes.org/gustavo/blog/post/kernel-boot-process
http://www.ibm.com/developerworks/linux/library/l-linuxboot/
http://duartes.org/gustavo/blog/post/how-computers-boot-up

Add integer between x and y by gcc inline asm code

Write a C function that adds integers between x and y, y >= x, using assembly inline

#include <stdio.h>
#include <stdlib.h>

/*return x+(x+1)+(x+2)+(x+3)+...+y*/

int asm_sum(int x, int y)
{
        int ret = 0;

        __asm__ (   "loop:addl %1, %0\n\t"
                    "inc %1\n\t"
                    "cmp %2, %1\n\t"
                    "jle loop"
                    :"+r"(ret)
                    :"r"(x), "r"(y)
                 );
        return ret;
}

int main()
{
        int x = 6;
        int y = 10;

        printf("asm_sum(%d, %d) return %d\n", 
               x, y, asm_sum(x,y));
        
        //output: asm_sum(6, 10) return 40

        return 0;
}

Verify a binary tree is a binary search tree

Algorithm: In-order traversal the binary tree and examine that the visited node’s data are in sorted order, then the binary tree is BST.

Here is source code:

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

struct node{
   int data;
   node* leftchild;
   node* rightchild;
   node(int d):data(d), leftchild(NULL),rightchild(NULL){}
};

bool isBST(node* ptr)
{
   static node* prv_node = new node(INT_MIN);
   
   if(ptr)
   {
      if(!isBST(ptr->leftchild)) return false;
      
      if(prv_node->data >= ptr->data) return false;
      
      prv_node = ptr;
      
      if(!isBST(ptr->rightchild)) return false;
   }
   
   return true;
} 

int main()
{
   /*input: a binary tree
               5
              / \
             3   6
            / \ 
           2   4
   */
   node* root = new node(1);
   root->leftchild = new node(3);
   root->rightchild = new node(6);
   root->leftchild->leftchild = new node(2);
   root->leftchild->rightchild = new node(4);

   if(isBST(root)) printf("is BST\n");
   else printf("not BST\n");
   
   /*output:
     is BST
   */
}

Difference between memmove() and memcpy()

“The memmove() function copies n bytes from memory area src to memory area dest. The memory areas may overlap: copying takes place as though the bytes in src are first copied into a temporary array that does not overlap src or dest, and the bytes are then copied from the temporary array to dest.”

“The memcpy() function copies n bytes from memory area src to memory area dest. The memory areas must not overlap. Use memmove() if the memory areas do overlap.”

So basically memmove() can handle memory overlapping but memcpy() cannot. Let’s take a look at an example to illustrate this:

#include <memory.h>
#include <string.h>
#include <stdio.h>

char str1[7] = "aabbcc";

int main( void )
{
    printf( "The string: %s\n", str1 );
    memcpy( str1 + 2, str1, 4 );
    printf( "New string: %s\n", str1 );

    strcpy( str1, "aabbcc" );   // reset string

    printf( "The string: %s\n", str1 );
    memmove( str1 + 2, str1, 4 );
    printf( "New string: %s\n", str1 );

    /* output:
        The string: aabbcc
        New string: aaaaaa
        The string: aabbcc
        New string: aaaabb
    */
}

Additionally, strcpy() cannot handle the memory overlapping problem too. Also not as described above memmove() do not need temporary space to finish coping. The implementation of memmove() could be like this:

if src > dest; then
    copy src from the beginning
else if src < dest; then
    copy src from the ending
else // src == dest
    do nothing

strcpy() can make use of the similar method to handle memory overlapping or just call memmove().

Virtuality in constructor and destructor in C++

Fact 1: there is no virtual constructor.

Reason: the compile should well know what exactly the type is to be created. Also technically speaking we can not get the dynamic dispatch information (virtual table) which is created only after the object is constructed.

Fact 2: there is virtual destructor.

Reason: it’s quite useful when you want to delete an object of a derived class through pointer to base class. So with out virtual there might be memory leak, since the destructor of derived class won’t be called. Let’s look at an example.

In this code the derived’s destructor is not called, for base’s destructor is not of type virtual.

#include <iostream>

class base
{
   public:
      base(){cout<<"Base constructor"<<endl;}
      ~base(){cout<<"Base destructor"<<endl;}
};

class derived: public base
{
   public:
      derived(){cout<<"Derived constructor"<<endl;}
      ~derived(){cout<<"Derived destructor"<<endl;}
};

int main()
{
   base* p = new derived();
   delete p;
   return 0;
   /* output:
      Base constructor
      Derived constructor
      Base destructor
   */ 
}

Now we specify the type of base’s destructor as virtual, then the derived’s destructor is called

class base
{
   public:
      base(){cout<<"Base constructor"<<endl;}
      virtual ~base(){cout<<"Base destructor"<<endl;}
};
...

int main()
{
...
   /* output:
      Base constructor
      Derived constructor
      Derived destructor
      Base destructor
   */ 

}

Fact 3: Never use virtual function member inside the constructor or destructor.

Reason: Assuming the virtual function is called in base constructor, when we declare an derived object, the base constructor would be called first. Then the virtual function in base would be called instead of going down to find a derived implementation of the virtual function, because the derived member hasn’t even been constructed at this moment. Same reason for destructor.

Let’s look at an example: Even the type of object a is derived, the foo() in base is called anyway.

#include <iostream>

class base
{
   public:
      base(){foo();}
      virtual void foo(){cout<<"base vfunc"<<endl;}
};      

class derived: public base
{
   public:
      void foo(){cout<<"derived vfunc"<<endl;}
};

int main()
{
   derived a;
   return 0;
   /* output:
      base vfunc
   */
}

Above code’s logic is wrong but would be compiled well, but if we use pure virtual function, then error would be throw out, which can explicitly prove what we discussed above

<pre>
class base
{
   public:
      base(){foo();}
      virtual void foo()=0;
};
...

int main()
{
...
    //compile error: abstract virtual `void base::foo()'
    //called from constructor
}

Root-to-leaf path sum equle to given number in tree

#include <stdlib.h>
#include <stdio.h>

struct node{
   int data;
   node* leftchild;
   node* rightchild;
   node(int d):data(d), leftchild(NULL),rightchild(NULL){}
};

void print_path(int* path, int length)
{
   int i;
   for( i = 0;i < length; i++)
   {
      printf("%d ", path[i]);
   }
   printf("\n");
}

int path_sum(int* path, int length)
{
   int i,sum = 0;
   for( i = 0;i < length; i++)
   {
      sum +=path[i];
   }
   return sum;
}

bool is_leaf(node* ptr)
{
   if(ptr->leftchild == NULL && ptr->rightchild == NULL)
   {
      return true;
   }
   else return false;
}

void match_path_sum(node* ptr,int* path,int length,int sum)
{
   if(NULL == ptr) return;
   
   path[length] = ptr->data;
   
   if(is_leaf(ptr) && path_sum(path, length + 1) == sum)
   {
      print_path(path, length + 1);
   }
   
   match_path_sum(ptr->leftchild, path, length + 1, sum);
   match_path_sum(ptr->rightchild, path, length + 1, sum);
   
}

int main()
{
   /*input: sum = 9
               3
              / \
             2   6
            / \ 
           5   4
   */
   node* root = new node(3);
   root->leftchild = new node(2);
   root->rightchild = new node(6);
   root->leftchild->leftchild = new node(5);
   root->leftchild->rightchild = new node(4);
   
   int* path = new int[100];
   
   match_path_sum(root, path, 0, 9);
   
   delete path;
   
   /*output:
     3 2 4
     3 6
   */
}

Reverse singly linked list: recursive and non-recursive

#include <stdlib.h>
#include <stdio.h>

struct node{
   int data;
   node* next;
   node(int a, node* b):data(a),next(b){}
};

class list{
   public:
      node* head;
      list():head(NULL){}
      list(int n){
         head = new node(0,NULL);
         node* prv = head;
         node* ptr = NULL;
         for(int i=1;i<n;i++)
         {
            ptr = new node(i,NULL);
            prv->next = ptr;
            prv = ptr;
         }
      }
      ~list(){
         node* ptr = head;
         while(ptr)
         {
            node* tmp = ptr;
            ptr = ptr->next;
            delete tmp;
         }
      }
      void printlist(){
         node* ptr = head;
         while(ptr)
         {
            printf("%d ", ptr->data);
            ptr = ptr->next;
         }
         printf("\n");
      } 
};

//non-recursive
void reverse(node* &head)
{
   node* prv = NULL;
   node* ptr = head;
   while(ptr)
   {
      node* tmp = ptr->next;
      ptr->next = prv;
      prv = ptr;
      ptr = tmp;
   }
   head = prv;
}

//recursive
node* r_reverse(node* ptr, node* prv)
{   
   if(ptr == NULL) return prv;
   node* tmp = ptr->next;
   ptr->next = prv;
   prv = ptr;
   return r_reverse(tmp, prv);
}

int main()
{
   list s(5);
   s.printlist();
   reverse(s.head);
   s.printlist();
   s.head = r_reverse(s.head,NULL);
   s.printlist();
   return 0;

   //output is:
   // 0 1 2 3 4
   // 4 3 2 1 0
   // 0 1 2 3 4
}