sourcecode

Friday, July 13, 2012

How to compile a kernel on Ubuntu 10.04


  • sudo apt-get install fakeroot kernel-wedge build-essential makedumpfile kernel-package libncurses5 libncurses5-dev
Then an error occurs:
The following packages have unmet dependencies: build-essential: Depends: g++ (>= 4:4.3.1) but it is not going to be installed
Solution: Update ubuntu with all packages using update manager.

  • Under ~/src/linux-2.6.32, using command
$make menuconfig
    I don't know how to change... so I didn't change anything.
    • I forgot to use this command line below the first time:
    sudo update-initramfs -c -k 2.6.32.11+drm33.2-alpha
     Then I got an unbootable kernel :(

    Kernel Panic - not syncing: VFS: Unable to mount root fs on unknown-block(0,0)
    • And  I had to make a live CD and boot from CD-ROM
    https://help.ubuntu.com/community/BurningIsoHowto
    http://askubuntu.com/questions/41930/kernel-panic-not-syncing-vfs-unable-to-mount-root-fs-on-unknown-block0-0

    Create two folders under /mnt : /mnt/dev and /mnt/proc
    Start with a livecd, open a a terminal
    sudo fdisk -l
    sudo mount /dev/sdax /mnt
    sudo mount --bind /dev /mnt/dev
    sudo mount --bind /proc /mnt/proc
    sudo chroot /mnt 
    

    with the new root folder, cd under /boot and find all the kernel versions.
    $update-initramfs -u -k 2.6.32.59+drm33.24-alpha
    $update-grub

    • After boot up, use $uname to verify the booted version.

    /**************END******************/



    Wednesday, July 11, 2012

    star wars

    telnet towel.blinkenlights.nl

    EXECVE(2)

    $man 2 execve

    NAME
           execve - execute program

    SYNOPSIS
           #include

           int execve(const char *filename, char *const argv[],
                      char *const envp[]);



    Also the man page points out:
    *  Any   outstanding   asynchronous   I/O   operations   are   canceled.



    • If the execution is unsuccessful, execve returns with -1 and its calling process continues.
    • If the execution is successful, execve overwrites its calling process (the rest of the code in the calling process is not reached) and the exit status is the same as defined in the process calling execve. (Either case the exit status code is the same).

    The envp does not seem to work well in execve(). It is suggested to use execvp() instead.

    /**********************END**********************/

    WAIT(2) and status

    $man 2 wait

    NAME
           wait, waitpid, waitid - wait for process to change state

    SYNOPSIS
           #include
           #include

           pid_t wait(int *status);

           pid_t waitpid(pid_t pid, int *status, int options);

           int waitid(idtype_t idtype, id_t id, siginfo_t *infop, int options);

       Feature Test Macro Requirements for glibc (see feature_test_macros(7)):

           waitid():
               _SVID_SOURCE || _XOPEN_SOURCE >= 500 ||
               _XOPEN_SOURCE && _XOPEN_SOURCE_EXTENDED
               || /* Since glibc 2.12: */ _POSIX_C_SOURCE >= 200809L




    If no wait() function is used, the parent vs child process is in a race condition, i.e. the order of execution of the two processes is not determined.

    When there are different exit paths in the child, it is possible to have them identified by the status variable, calling WEXITSTATUS(status) in the parent process after wait(2), according to _exit(status) numbers.







    /*********************END*********************/

    READ(2)

    $man 2 read

    NAME
           read - read from a file descriptor

    SYNOPSIS
           #include

           ssize_t read(int fd, void *buf, size_t count);
     



    • size_t and ssize_t are both int

    • fd: STDIN_FILENO for standard in (keyboard, effectively 0)

    • There are three numbers: the buff size (bSize), the acceptance count size (cSize) and the actually input size (iSize).  
      1. When (iSize < cSize): if the input is terminated by Enter, then add one to the number of letters; if the input is terminated by ctrl+d, then no extra letter is appended. 
        • For example, user input: $ABC
          with an Enter, then iSize == 4, and the buffer stores ASCII (* means garbage integers):
          65 66 67 10 *  *  *
        • user input: $ABC
          with a ctrl+d, then iSzie == 3, and the buffer stores ASCII:
          65 66 67 *  *  *
      2. When (iSize > cSize), the exceeding input is ignored and resultant iSize == cSize
      3.  When (bSize < cSize), danger! The system does not perform boundary check! So one can input long enough to write out of the buffer's boundary and no warnings given. This probably won't corrupt immediately, but it still can cause fatal error potentially at any time!
      4. When a read() function is encountered, the system waits for the input. And every call of read(), the buf is overwritten.
    For write(2) function, similar scenarios show. the fd can be STDOUT_FILENO for standard output (monitor, effectively 1).

    /*********************END*******************/

    EggShell

    CIS415 Spring 2012, Project1

    Written in C

    #define _POSIX_SOURCE
    #define _BSD_SOURCE
    #include <unistd.h>
    #include <sys/types.h>
    #include <sys/wait.h>
    #include <signal.h>
    #include <stdlib.h>//malloc
    #include <stdio.h>
    #include <errno.h>
    #define SIZE 1024
    char USAGE[]="Usage: $EggShell seconds";
    
    int string_to_int(char* input);//convert a string to int. when encounter a non-number, the rest of the string is ignored
    void print_prompt();//print the shell prompt
    void print_int(int num);//print an integer to the monitor
    void print_string(char* input);//print a string, ended with NULL, to the monitor
    void print_cr();//print to monitor carrage return/new line
    char** command_parser(char* input, int* output_length);//the input string is parsed by space, ' ', to substrings stored in output.
    //the length of the string array returned: output_length is recorded. The caller is responsible to free the memory using command_parser_free()
    void command_parser_free(char** string_array, int length);
    int read_terminal(char* buf);//if the string is ended with a carrige return, common for termial input, it is parsed to end with 0.
    //return the actually string length
    int run_command(char** command,int time_out);
    void alarm_handler(int signum);
    
    /****************************************/
    int main(int argc, char** argv){
      int time_out = 1;//second
      if (argc != 2){
        print_string(USAGE);
        print_cr();
        if (argc > 2) return 0;
      }
      else time_out = string_to_int(argv[1]);
      char read_buff[SIZE+1];
      read_buff[SIZE] = 0;
      while(1){
        print_prompt();
        int read_length = read(STDIN_FILENO, read_buff, SIZE);// read_terminal(read_buff);
        if (read_length && '\n'==read_buff[0]) continue;//only Enter is pressed
        if (read_length && '\n'==read_buff[read_length-1]) --read_length;
        read_buff[read_length] = 0;//terminate string
        int fork_id = fork();
        if (fork_id < 0){
          print_string("Fork failed!\n");
        }else if(fork_id > 0){//parent
          int status;
          wait(&status);//man wait for the use of status
          if(WIFSIGNALED(status)){
     print_string("All eggs are hatched! You need another shell!\n");
          }
          else if (WIFEXITED(status)){
            if (EXIT_EGGSHELL == WEXITSTATUS(status)){
       print_string("Exit\n");
       return 0;
     } else if (COMMAND_ERROR != WEXITSTATUS(status))
       print_string("You escaped, for now!\n");
          }
        }else{//child
          int vector_length = 0;
          char** string_vector = command_parser(read_buff, &vector_length);
          if (!string_vector || !string_vector[0]){
     _exit(EXIT_EGGSHELL);//input is ctrl+d only
          }
          run_command(string_vector, time_out);
          command_parser_free(string_vector, vector_length);
          //int errsv = errno;
          perror("Command Error");
          _exit(COMMAND_ERROR);
          //exit with a command error
        }//eles child
      }//for ii
    }//main()
    /***************************************/
    int string_to_int(char* input){
      int result = 0;
      for(int ii = 0; input[ii] >= '0' && input[ii] <='9'; ++ii){
        result *= 10;
        result += input[ii]-'0';
      }//for ii
      return result;
    }//string_to_int()
    
    void print_prompt(){
      char prompt[]="$EggShell>";
      print_string(prompt);
    }
    
    void print_int(int num){
        if (!num) return;
        char digit = num % 10 + '0';
        print_int(num/10);
        write(STDOUT_FILENO,&digit,1);
    }//print_int()
    
    void print_string(char* input){
      if(!input) return;
      for(int ii = 0; input[ii] != 0; ++ii){
        write(STDOUT_FILENO,&input[ii],1);
      }//for ii
    }//print_string()
    
    void print_cr(){
      write(STDOUT_FILENO,"\n",1);
    }//print_cr
    char** command_parser(char* input, int* output_length){
      *output_length = 0;
      char** v_string = (char**)malloc(128*sizeof(char*));//max number of arguments
      for(int ii = 0; input[ii]; ){//whole string
        while (input[ii] == ' ') ++ii;
        if (!input[ii]) break;
        char* a_string = (char*)malloc(128*sizeof(char));//max length of an argument
        int jj = 0;//index for a word
        while ( input[ii] && input[ii] != ' '){
          a_string[jj++] = input[ii++];
        }
        a_string[jj++] = 0;//string end
        a_string = realloc(a_string, jj*sizeof(char*));//reszie (shrink) word string
        v_string[(*output_length)++] = a_string;//careful, ++ is higher than *
      }//for ii
      v_string[(*output_length)++] = NULL;
      v_string = realloc(v_string, *output_length*(sizeof(char*)));
      return v_string;
    }//command_parser()
    void command_parser_free(char** string_array, int length){
      for(int ii = 0; ii < length; ++ii) free(string_array[ii]);
      free(string_array);
    }
    
    int read_terminal(char* buf){
      int read_in = read(0, buf, SIZE);
      if (read_in &&  buf[read_in-1] == 10){//10 is new line feed
          --read_in;
      }
      buf[read_in] = 0;
      return read_in;
    }
    
    int run_command(char** command, int time_out){
      alarm(time_out);
      signal(SIGALRM, alarm_handler);
      return execve(command[0],command,NULL);
    }
    
    void alarm_handler(int signum){//p268
      kill(getpid(),SIGKILL);
    }
    
    /****************END********************/

    Tuesday, July 10, 2012

    Edit Distance

    Problem: http://www.leetcode.com/onlinejudge

    Edit Distance
    Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
    You have the following 3 operations permitted on a word:
    a) Insert a character
    b) Delete a character
    c) Replace a character

    Algorithm: http://en.wikipedia.org/wiki/Levenshtein_distance

    Related to Longest Common Sequence:
    http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-15-dynamic-programming-longest-common-subsequence/

    Code:
    class Solution {
    public:
        inline int minInt(int a, int b){
            return (a< b?a:b);
        }
        inline int minInt(int a, int b, int c){
            return minInt(minInt(a, b), c);        
        }
        int minDistance(string word1, string word2) {
            // Start typing your C/C++ solution below
            // DO NOT write int main() function
            int l1 = word1.length();
            int l2 = word2.length();
            string& w1 = (l1< l2?word1:word2);//shorter - horizontal
            string& w2 = (l1< l2?word2:word1);//longer - vertical
            int const length1 = w1.length();
            int const length2 = w2.length();
            if (!length1) return length2;
            vector< int> dist(length1,0);
            for(int ii = 0; ii < length1; ++ii){//row 0, dist[0] is not used
                dist[ii] = ii + 1;
            }//for ii
            for(int ii = 0; ii < length2; ++ii){//vertical, start from row 1 (when length2==1)
                int distDiag = ii;
                int distLeft = ii + 1;
                for(int jj = 0; jj < length1; ++jj){//horizontal
                    int const distUp = dist[jj];
                    if (w1[jj] == w2[ii]) dist[jj] = distDiag;
                    else dist[jj] = minInt(distLeft, distUp, distDiag) + 1;
                    distDiag = distUp;
                    distLeft = dist[jj];
                }
            }
            return dist[length1-1];
        }
    }; 
    /**If there is some memory constrain, the minimum memory depends on the length
    of the shorter string, as the code above
    
    The general bottom-up method utilizing updating table, similar to the
    longest-common sequence (start at 55:50)
    http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-15-dynamic-programming-longest-common-subsequence/
    
    Algo: http://en.wikipedia.org/wiki/Levenshtein_distance
    A working implementation can be found here:
    http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C.2B.2B
    */
    
    #include <string>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    template <typename T>
    class Solution{
    public:
      int edit_distance(T const& s1, T const& s2){
        vector<vector<int>> matrix(s1.size()+1, vector<int>(s2.size()+1));
        //s2 horizontal, s1 vertical
        for(int ii = 0; ii <= s1.size(); ++ii) matrix[ii][0] = ii;
        for(int ii = 0; ii <= s2.size(); ++ii) matrix[0][ii] = ii;
        for(int ii = 1; ii <= s1.size(); ++ii){
          for(int jj = 1; jj <= s2.size(); ++jj){//scan from left to right
            //line by line
            matrix[ii][jj] = min(min(matrix[ii-1][jj], matrix[ii][jj-1])+1,
              matrix[ii-1][jj-1]+static_cast<int>(s1[ii-1] != s2[jj-1]));
          }//for jj
        }//for ii
        return matrix[s1.size()][s2.size()];
      }
    };
    
    int main(){
      cout<<"hello"<<endl;
      
      Solution<string> s;
      string s1("cat");
      string s2("hat");
      cout<<s.edit_distance(s1,s2)<<endl;
      return 0;
    }