Find fibonacci number at position n: recursion

#include <stdio.h>

int fib(int n)
{
    if(n<=1)
        return n;
    return fib(n-1)+fib(n-2);
}


int main()
{
    int a,r;
    printf("Enter any number : ");
    scanf("%d",&a);
    r=fib(a-1);
    printf("The no. at position %d is %d\n",a,r);
    return 0;
}

Print fibonacci series upto n: Without recursion

#include <stdio.h>

int main()
{
    int first=0,second=1,next,i,n;
    printf("Enter the limit: ");
    scanf("%d",&n);
    for(i=0; i<=n-1; i++)
    {
        if(i<=1)
            next = i;
        else
        {
            next = first + second;
            first = second;
            second = next;
        }
        printf("%d ",next);
    }
}

Print fibonacci series upto n: recursion

/* Print fibonacci series upto n: recursion */

#include <stdio.h>

int fib(int n)
{
    if(n <= 1)
        return n;
    else
    {
        return fib(n-1) + fib(n-2);
    }
}

int main()
{
    int n,i;
    printf("Enter the limit: ");
    scanf("%d",&n);
    for(i=0; i
    {
        printf("%d ",fib(i));
    }
    return 0;
}

VIM - ETAGS/CSCOPE

VIM - ETAGS/CSCOPE
CTRL + \ + s [To go to a symbol]
CTRL + t  [To jump back]

CTRL + Spacebar + s [split horizontally]
CTRL + w + w [Browse windows]
CTRL + w + c [Close a window]
CTRL + w + o [Make the current window only one]
CTRL + w + s [Horizontal split]
CTRL + w + v [Vertical split]
CTRL + Spacebar CTRL + Spacebar + s [Split vertically]


Cscope database for linux kernel
LNX=/home/vinod/files/beagle/linux-3.0.4
    find  $LNX                                                                \
    -path "$LNX/arch/*" ! -path "$LNX/arch/arm*" -prune -o               \
    -path "$LNX/tmp*" -prune -o                                           \
    -path "$LNX/Documentation*" -prune -o                                 \
    -path "$LNX/scripts*" -prune -o                                       \
        -name "*.[chxsS]" -print >/home/vinod/files/beagle/linux-3.0.4/cscope.files

cscope -b -q -k -v

Create Mask

/* Create a mask with m set bits followed by n unset bits */

#include <stdio.h>


unsigned int createmask(unsigned int m, unsigned int n)
{
    return (~(~0 << m) << n);
}

char *basecalc(unsigned int num, unsigned int base)
{
    static char buff[32];
    char *s = &buff[31];
    *s = '\0';
    int cnt = 0,i;
    while(num)
    {
        *(--s) = "0123456789ABCDEF"[num%base];
        num /= base;
        cnt++;
        if(cnt > 7) break;
    }
    for(i=cnt; i<=7;i++)
        *(--s) = '0';
    return s;
}

int main()
{
    unsigned int m,n,r;
    printf("Enter the required set bits: ");
    scanf("%d",&m);
    printf("Enter the required unset bits: ");
    scanf("%d",&n);
    r = createmask(m,n);
    printf("The created mask: %s\n",basecalc(r,2));
    return 0;
}

Test 1:

Enter the required set bits  : 5
Enter the required unset bits: 3
The created mask             : 11111000

Test 2:

Enter the required set bits  : 2
Enter the required unset bits: 5
The created mask             : 01100000

Register, Mask and Value

#include <stdio.h>


char *basecalc(unsigned int num, unsigned int base)
{
    static char buff[32];
    char *s = &buff[31];
    int cnt = 0,i;
    *s = '\0';
    while(num)
    {
        *(--s) = "0123456789ABCDEF"[num%base];
        num /= base;
        cnt++;
        if(cnt>7) break;
    }
    for(i=cnt;i<=7;i++)
        *(--s) = '0';
    return s;
   
}

int fbs(int mask)
{
    unsigned int pos = 0;
    if(!mask) return 0;
    while(!(mask &1))
    {
        mask >>= 1;
        pos++;
    }
    return (pos);
}

int setmask (int num, int mask, int value)
{
    /*This multiplies value by the lowest set bit in MASK.
      The multiplier is known to be a constant power of 2 at compile time,
      so this will be compiled as a simple left shift by any remotely sane compiler.
     */
    //value *= ( mask & ~(mask << 1));
    //return (num &= (value | ~mask) );
    return ( num &= ((value*(mask & ~(mask<<1)))|~mask )  );
}

int main()
{
    int num, mask, value,res;

    printf("Enter the num: ");
    scanf("%d",&num);      
    printf("Enter the mask: ");
    scanf("%d",&mask);
    printf("Enter the value: ");
    scanf("%d",&value);

    /* ------------------------ */
    printf("Num  : %s\n",basecalc(num,2));
    printf("Mask : %s\n",basecalc(mask,2));
    printf("Value: %s\n",basecalc(value,2));
    /* ------------------------ */

    res = setmask(num,mask,value);
    printf("The set value: %s\n",basecalc(res,2));
    return 0;
}

TEST 1
Enter the num  : 25
Enter the mask : 24
Enter the value: 1
Num            : 00011001
Mask           : 00011000
Value          : 00000001
The set value  : 00001001

TEST 2
Enter the num  : 153
Enter the mask : 24
Enter the value: 2
Num            : 10011001
Mask           : 00011000
Value          : 00000010
The set value  : 10010001

Video RAM driver

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/init.h>

#include <linux/kdev_t.h>
#include <linux/types.h>
#include <linux/fs.h>

#include <asm/uaccess.h>
#include <asm/io.h>
#include <linux/device.h>
#include <linux/cdev.h>


#define VRAM_BASE 0x000A0000
#define VRAM_SIZE 0x00020000

static void __iomem *vram;
static dev_t first;
static struct cdev c_dev;
static struct class *cl;


static int my_open(struct inode *i, struct file *f)
{return 0;}

static int my_close(struct inode *i, struct file *f)
{return 0;}

static ssize_t my_read(struct file *f, char __user *buf,size_t len,loff_t *off)
{
    int i;
    unsigned char byte;

    if(*off >= VRAM_SIZE)
    {
         return 0;          
    }
   
    if(*off + len > VRAM_SIZE)
    {
        len = VRAM_SIZE - *off;
    }
   
    for(i=0; i
    {
        byte = ioread8((unsigned char *)vram + *off + i);
        if(copy_to_user(buf+i,&byte,1))
            return -EFAULT;
    }
    *off +=len;
    return len;
}

static ssize_t my_write(struct file *f,const char __user *buf, size_t len, loff_t *off)
{
    int i;
    unsigned char byte;

    if(*off >= VRAM_SIZE)
        return 0;

    if(*off + len > VRAM_SIZE)
        len = VRAM_SIZE - *off;

    for(i=0; i
    {
        if(copy_from_user(&byte,buf+i,1))
            return -EFAULT;
        iowrite8(byte,(unsigned char *)vram + *off +i);
    }
    *off += len;   
    return len;
}

static struct file_operations vram_fops =
{
    .owner = THIS_MODULE,
    .open = my_open,
    .release = my_close,
    .read = my_read,
    .write = my_write
};

static int __init vram_init(void)
{
    printk(KERN_INFO "VRAM init started...");
    if( (vram = ioremap(VRAM_BASE,VRAM_SIZE)) == NULL)
    {
        printk(KERN_ERR "Mapping video ram failed\n");
        return -1;
    }
    printk(KERN_INFO "Video RAM mapping OK");

    if(alloc_chrdev_region(&first,0,1,"vram") < 0)
        return -1;

    if( (cl = class_create(THIS_MODULE,"chrdrv")) == NULL)
    {
        unregister_chrdev_region(first,1);
        return -1;
    }       

    if(device_create(cl,NULL,first,NULL,"vram") == NULL)
    {
        class_destroy(cl);
        unregister_chrdev_region(first,1);
        return -1;
    }
   
    cdev_init(&c_dev,&vram_fops);
    if(cdev_add(&c_dev,first,1) == -1)
    {
        device_destroy(cl,first);
        class_destroy(cl);
        unregister_chrdev_region(first,1);
        return -1;
    }

    printk(KERN_INFO "Successful vram driver init...");
    return 0;
}

static void __exit vram_exit(void)
{
    cdev_del(&c_dev);
    device_destroy(cl,first);
    class_destroy(cl);
    unregister_chrdev_region(first,1);
    iounmap(vram);
    printk(KERN_INFO "Alvida: vram driver unregistered");
}

module_init(vram_init);
module_exit(vram_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("VINOD");
MODULE_DESCRIPTION("VRAM driver");

COMMANDS:

WRITE: echo -n "0123456789" > /dev/vram
READ: od -t x1 -v /dev/vram 

cat /proc/iomem
cat /proc/meminfo

Simple Character Driver

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/init.h>

#include <linux/kdev_t.h>
#include <linux/types.h>
#include <linux/fs.h>

#include <linux/device.h>
#include <linux/cdev.h>
#include <asm/uaccess.h>

static dev_t first;
static struct cdev c_dev;
static struct class *cl;
static char c;

static int my_open(struct inode *i, struct file *f)
{
    printk(KERN_INFO "DRIVER: open()");
    return 0;
}

static int my_close(struct inode *i, struct file *f)
{
    printk(KERN_INFO "DRIVER: close()");
    return 0;
}

static ssize_t my_read(struct file *f,char __user *buf, size_t len, loff_t *off)
{
    printk(KERN_INFO "DRIVER: read()");
    if(copy_to_user(buf,&c,1) != 0)
        return -EFAULT;
    else
        return 1;
}

static ssize_t my_write(struct file *f, const char __user *buf, size_t len, loff_t *off)
{
    printk(KERN_INFO "DRIVER: write()");
    if(copy_from_user(&c, buf+len-1,1) != 0)
        return -EFAULT;
    else
        return len;
}

static struct file_operations my_fops =
{
    .owner    = THIS_MODULE,
    .open     = my_open,
    .release  = my_close,
    .read     = my_read,
    .write    = my_write
};

static int __init dd_init(void)
{
    printk(KERN_INFO "Namaskar: dd initialization");
   
    if(alloc_chrdev_region(&first, 0, 1, "VINZU") < 0)
    {
        return -1;
    } 

    if( (cl = class_create(THIS_MODULE,"chrdrv")) == NULL)
    {
        unregister_chrdev_region(first,1);
        return -1;
    }  

    if(device_create(cl,NULL,first,NULL,"mynull") == NULL)
    {
        class_destroy(cl);
        unregister_chrdev_region(first,1);
        return -1;
    }

    cdev_init(&c_dev,&my_fops);
    if(cdev_add(&c_dev,first,1) == -1)
    {
        device_destroy(cl,first);
        class_destroy(cl);
        unregister_chrdev_region(first,1);
        return -1;
    }

    printk(KERN_INFO "dd registerd successfully...");
    return 0;
}

static void __exit dd_exit(void)
{
    cdev_del(&c_dev);
    device_destroy(cl,first);
    class_destroy(cl);
    unregister_chrdev_region(first,1);
    printk(KERN_INFO "Alvida: dd unregisterd");
}

module_init(dd_init);
module_exit(dd_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("VINOD");
MODULE_DESCRIPTION("Simple character driver");


|COMMANDS FOR TESTING:


cat /proc/devices - VINZU
ls /sys/class - chardrv
ls -l /dev - mynull

echo -n "hello" > /dev/mynull
dmesg | tail -10
cat /dev/mynull
ctrl + c
dmesg | tail -10

how to write to a physical address in Linux?

 Usually you do this in several steps in a device driver:

1. Call request_mem_region() to request virtual memory region;
2. Call ioremap() to map physical address to virtual address;
3. Read/write mapped virtual address by using iowriteXX() /
ioreadXX(), etc. Here XX can be 8, 16, or 32 for example, represents
bit width.
4. Call iounmap() and release_mem_region() to release memory mapping;

[ NOTE: phys_to_virt() only works with directly mapped physical address. Using phys_to_virt() is the best idea, anyway.]


To make access generic
The addresses referring to RAM are termed as physical addresses,and those referring to device maps are bus addresses.In Linux, none of these are directly accessible, but are to mapped to virtual addresses and then accesses through them. This is to make RAM and device access generic.


void *ioremap (unsigned long device_bus_address, unsigned long device_region_size);
void iounmap (void *virt_addr);

Once mapped to virtual addresses, it depends on the device datasheet as to which set of device registers and/or device memory to read from or wirte into, by adding their offsets to the virtual address returned by ioremap().
unsigned int ioread8(void *virt_addr);
unsigned int ioread16(void *virt_addr);
unsigned int ioread32(void *virt_addr);

unsigned int iowrite8(u8 value, void *virt_addr);
unsigned int iowrite16(u16 value, void *virt_addr);
unsigned int iowrite32(u32 value, void *virt_addr);

 

Custom device driver in an RTOS (With Buffered I/O)

Driver functionalities

1. Driver initialization    
    Initialize the actual hardware device
    Initialize the internal data structres

2. Driver control
    Run-time control of hardware device
    e.g.: Change the baud rate of a serial device

3. Driver access
    In applications where multiple threads need simultaneous driver acces - use semaphore

4. Driver input/output
    How input/output is buffered and how threads wait on them

5. Driver interrupts
    Interrupts notify the driver of device input,output, control & error events.

6. Driver status
    Run time status & statistics associated with the drive operation.

7. Driver termination
    If the driver and/or the physical hardware device need to be shut down.

---

 

Example: Simple serial hardware device with a configuration register, and input register and an output register
Initialization
Two counting semaphores are used to manage the driver's input and output operation.
Input semaphore: Set by input ISR when a character is received by the serial hardware device
         Semaphore is created with an initial value of 0.
Output semaphore: Indicates availability of the serial hardware transmit register
          Semaphore is created with an initial value of 1 to indicate availability.

void sdriver_initialize(void)
{
    /* Initialize the two counting semaphores user to control the simple I/O */
    tx_semaphore_create(&sdriver_input_semaphore,"Sdriver Input Semaphore",0);
    tx_semaphore_create(&sdriver_output_semaphore,"Sdriver Output Semaphore",1);

    /* Setup interrupt vectors for input and output ISRs.
       The initial vector handling should call the ISRs
       defined in this file.*/

    /* Configure serial device hardware for RX/TX interrupt
       generation, baud reate, stop bits, etc. */
}

Simple driver input:
When a serial device interrupt is received, the input semaphore is set.
If one or more threads are waiting for a character from the driver, the
thread waiting the longest is resumed.
Limitations: Dropping input characters
Handled by: Add input character buffer

unsigned char sdriver_input(void)
{
    /*determine if there is a character waiting. If not, suspend */
    tx_semaphore_get(&sdriver_input_semaphore, TX_WAIT_FOREVER);
  
    /* Return character from serial RX hardware register */
    return(*serial_hardware_input_ptr);
}

void sdriver_input_isr(void)
{
    /* See if an input character notification is pending */
    if(!sdriver_input_semaphore.tx_semaphore_count)
    {
        /* If not, notify thread of an input character */
        tx_semaphore_put(&sdriver_input_semaphore);
    }
}

Simple driver output:
Output semaphore is used to signal when the serial device's transmit register is free.

void sdriver_output(unsigned char alpha)
{
    /* Determine if the hardware is ready to transmit a character.
       If not, suspend until the previous output completes. */
    tx_semaphore_get(&sdriver_output_semaphore, TX_WAIT_FOREVER);

    /* Send the character through the hardware */
    *serial_hardware_output_ptr = alpha;
}

void sdriver_output_isr(void)
{
    /* Notify thread last character transmit is complete */
    tx_semaphore_put(&sdriver_output_semaphore);
}

Shortcomings: Illustrates the basic idea of a simple driver.
          Doesn't address data buff

ering or any overhead issues.

---

 

Advanced driver issues:

1. Logic for Circular input buffer

unsigned char input_buffer[MAX_SIZE];
unsigned char *input_write_ptr;
unsigned char *input_read_ptr;

/* Initialization */
input_write_ptr =  &input_buffer[0];
input_read_ptr  =  &input_buffer[0];

/* Input byte ISR... alpha has character from device */
save_ptr = input_write_ptr;
*input_write_ptr++ = alpha;
if(input_write_ptr > &input_buffer[MAX_SIZE-1])
    input_write_ptr = &input_buffer[0]; /* Wrap */
if(input_write_ptr == input_read_ptr)
    input_write_ptr = save_ptr; /* Buffer full */

/* Retrieve input byte from the buffer */
if(input_read_ptr != input_write_ptr)
{
    alpha = *input_read_ptr++;
    if(input_read_ptr > &input_buffer[MAX_SIZE -1 ])
        input_read_ptr = &input_buffer[0];
}

2. Logic for Circular output buffer

unsigned char output_buffer[MAX_SIZE];
unsigned char *output_write_ptr;
unsinged char *output_read_ptr;

/* Initialization */
output_write_ptr = &output_buffer[0];
output_read_ptr  = &output_buffer[0];

/* Transmit complete ISR... Device ready to send */
if(output_read_ptr != output_write_ptr)
{
    *device_reg = *output_read_ptr++;
    if(output_read_ptr > &output_buffer[MAX_SIZE-1])
        output_read_ptr = &output_buffer[0];
}


/* Output drive buffer service. If device busy, buffer! */
save_ptr = output_write_ptr;
*output_write_ptr++ =  alpha;
if(output_write_ptr > &output_buffer[MAX_SIZE -1 ] )
    output_write_ptr = &output_buffer[0]; /* Wrap */
if(outpu_write_ptr == output_read_ptr)
    output_write_ptr = save_ptr; /* Buffer full */

---

Scheduling - Algorithms

Scheduler Does:
(1) CPU Utilization
    Keeping the CPU as busy as possible
(2) Throughput
    No. of tasks that completed their execution per time unit
(3) Turnaround
    The total time between the submission of a task & its completion.
(4) Waiting Time
    The amount of time a task waits in the ready queue.
(5) Response Time
    The amount of time it takes from when a request was submitted until the first response is produced.
(6) Fairness
    Allocating equal CPU time to each task
Note: In RTOS, the tasks should meet their deadlines

---

Scheduling Algorithms:
(1) Cyclic Executive/Run to completion
    Iterates through a given set of tasks
    Interrupts are not allowed, only polling
(2) Cooperative multitasking
    Applications run until they yield
(3)Round -Robin scheduling
    Tasks run until they've consumed their timeslice, or until they're blocked
(4) Preemptive priority based multitasking
    Running threads are preempted by threads with higher priorities
    It is not designed to be fair; but to be deterministic
(5) Time partition scheduling
    Guarantees that threads or groups of threads get a predetermined percentage of the CPU.
(6) Deadline scheduling
    Only available in specialized Oss.
    The schedule is dynamically computed such that the applications meet previously specified deadlines.

---

Interrupts & scheduling

    Interrupts can cause the threads to be rescheduled.
Interrupt Service Routine(ISR): Activities that must be handled at interrupt time(Such as emptying buffers that will quickly overwritten)
Interrupt Service Thread(IST): Activities that can be delayed and handled during normal, priority-driven, thread scheduling(Such as processing data for use by other tasks)

---

OS can change the priority of a task:
    1. Prevent priority inversion
    2. Deadline scheduler
    3. priority decay scheduling

Priority inversion: Typically occurs when a shared resource is held by a lower-priority thread, thus preventing the higher-priority thread from executing as it should.
Low priority thread requesting a high priority thread to do work on its behalf.
NOTE: Priority inversion could be prevented using mechanims such as priority inheritance or priority ceiling emulation.

---

Rate Monotonic Analysis
    RMA is the most common method used to analyze and assign priorities for systems with periodic deadlines.But, interrupt processing is not taken care of here.

       
   

#C_CODE: Binary tree - Morris traversal

#include <stdio.h>

#include <malloc.h>

typedef struct bintree tree;
struct bintree
{
    int data;
    tree *left;
    tree *right;
};

tree *newnode(int num)
{
    tree *r;
    r = (tree *)malloc(sizeof(tree));
    r->data = num;
    r->left = NULL;
    r->right= NULL;
    return (r);
}


void insert(tree **q, int num)
{
    tree *temp = *q;
    if(NULL == temp)
        *q = newnode(num);
    else
    {
        if(num <= temp->data) insert(&(temp->left),num);
        else insert(&(temp->right),num);
    }
}

/* Compute the no. of nodes in the tree */
int size(tree *temp)
{
    if (NULL == temp) return 0;
    else return (size(temp->left) + 1 + size(temp->right));
}

void display(tree *temp)
{
    tree *cur, *pre;
    if(NULL == temp) return;
    cur = temp;

    while(NULL != cur)
    {
        if(NULL == cur->left)
        {
            printf("%d ",cur->data);
            cur = cur->right; 
        }
        else
        {
            pre = cur->left;
            while(pre->right != NULL && pre->right != cur)
                pre = pre->right;
            if(pre->right == NULL)
            {
                pre->right = cur;
                cur = cur->left;
            }
            else
            {
                pre->right = NULL;
                printf("%d ",cur->data);
                cur = cur->right;
            }
        }
    }
}

void inorder(tree *temp)
{
   if(temp != NULL)
   {
       inorder(temp->left);
       printf("%d ",temp->data);
       inorder(temp->right);
   }
}

void preorder(tree *temp)
{
    if(temp != NULL)
    {
        printf("%d ",temp->data);
        preorder(temp->left);
        preorder(temp->right);
    }
}

void postorder(tree *temp)
{
    if(temp != NULL)
    {
        postorder(temp->left);
        postorder(temp->right);
        printf("%d ",temp->data);
    }
}
int numarr[10] = {7,4,1,3,0,5,2,8,6,9};
int main()
{
    tree *root = NULL;
    int i;

    for(i=0; i<10; i++)
        insert(&root,numarr[i]);

    printf("\nThe no. of nodes in the tree: %d\n",size(root));    

    printf("\ninorder: ");
    inorder(root);
    
    printf("\npreorder: ");
    preorder(root);

    printf("\npostorder: ");
    postorder(root);

    printf("\nMorris traversal: ");
    display(root); 
    return 0;
}

#C_CODE: Single Linked List

#include <stdio.h>

#include <malloc.h>


typedef struct singlelink node;
struct singlelink
{
    int data;
    node *next;
};

void append(node **q, int num)
{
    node *temp = *q, *r = NULL;
  
    r = (node *)malloc(sizeof(node));
    r->data = num;
    r->next = NULL;
    if(NULL == temp)
    {
        *q = r;
    }    
    else
    {
        while(NULL != temp->next)
            temp = temp->next;
        temp->next = r;
    }
}

void display(node *temp)
{
    printf("\nThe list: ");
    while(temp)
    {
        printf("%d ",temp->data);
        temp = temp->next;
    }

}

void reverse(node **q)
{
    node *temp1 = *q, *temp2 = NULL, *temp3 = NULL;
  
    while(temp1)
    {
       temp2 = temp1->next; // Save the next pointer
       temp1->next = temp3; // Update the next
       temp3 = temp1; // Update the previous
       temp1 = temp2;
    }

    if(temp3)
        *q = temp3;
}


void delete(node **q, int val)
{
    node *temp = *q, *old = NULL;

    while(temp)
    {
        if(temp->data == val)
        {
           if(temp == *q)
              *q = temp->next;       
           else
                old->next = temp->next;
            free(temp);
        }
        else
        {
            old = temp;
            temp = temp->next;
        }
    }
}

int main()
{
    node *head = NULL;
    unsigned int i;

    for(i=0; i<10; i++)
        append(&head,i);
    display(head);
 
    reverse(&head);
    display(head);

    delete(&head,5);
    display(head);

    return 0;
}

#C_CODE: Base calculator

#include <stdio.h>

char * basecalc(int num,int base)
{
    static char buff[32];
    char *s = &buff[31];
    *s  = '\0';
    while(num)
    {
        *(--s) = "0123456789ABCDEF"[num%base];
        num /= base;
    }
    return s;
}

int main()
{
    int num,base;
    fputs("Enter the num: ",stdout);
    scanf("%d",&num);
    fputs("Enter the base: ",stdout);
    scanf("%d",&base);
    printf("The num %d in base %d is: %s\n",num,base,basecalc(num,base));
    return 0;
}

#C_CODE: Palindrome

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


int pali(char *s)
{
    char *s2 = s + strlen(s) - 1;

    if(!*s) return 0;

    while(*(s2--) == *(s++) && *s);
    return (!*s && *(++s2) == *(--s));
}

int main()
{  
    char buff[32];
    fputs("Enter the string: ",stdout);
    fgets(buff,sizeof(buff),stdin);  
    *(buff + strlen(buff) - 1)  = '\0';
    printf("Is the string \"%s\" palindrome?%s\n",  
    buff,pali(buff)?"YES":"NO");
    return 0;
}

Linux commands

who am i
who
w - extended who command
who -b
fuser /dev/ttyS0
ps proc_id
fuser -k /dev/ttyS0
vmstat - virtual memory status
find
file
wc - count lines,words,characters in a file
df - filesystem statistics
netstat
iostat
diff
sdiff
lshalb  - dynamic database of connected hardware devices

RENAME exe to exe1
find . -name "*.exe" | while read i;
  do
	mv "$i" "${i%.exe}.exe1";
  done

Find the process that is currently using the serial port

Run as root


$ fuser /dev/ttyUSB0 [or /dev/ttyS0]
> /dev/ttyUSB0:         1761


$ ps 1761
>  PID TTY      STAT   TIME COMMAND
   1761 pts/0    S+     0:00 minicom


This process can also be killed directly with fuser as root
$ fuser -k /dev/ttyUSB0


To quickly connect to board using GNU screen:
$ screen /dev/ttyUSB0 115200

CACHE Memory

CACHE (pronounced "CASH")

Cache is used by the processor to reduce the average time to access main memory.
Cache is a smaller, faster memory which stores copies of the data from the most frequently used main memory locations.
When the processor needs to read from or write to a location in main memory, it first checks whether a copy of that data is in the cache.If so, the processor immediately reads from or writes to the cache, which is much faster than reading from or writing to the main memory.

Most CPU's have at least 3 independent caches:
     1. Instruction cache - Speed up executable instructin fetch
     2. Data cache - Speed up data fetch and store
     3. Translation lookaside buffer(TLB) - Speed up virtual-to-physical address translation for both executable instructions and data.

     NOTE: Data cache is organized as a hierarchy of more cache levels - L1,L2 etc.
     NOTE: Cache built into CPU itself is referred to as Level 1(L1) cache.Cache that resides on a separate chip next to the CPU is called Level 2(L2) cache. Some CPUs                 have both L1 & L2 cache built-in and designate the separate cache chip as Level 3(L3) cache.
     NOTE: Cache coherence
                The data in main memory being cached may be changed by other entities (e.g: peripherals usind DMA or multi-core processor), in which case the copy in                     the cache may become out-of-date or stale. 
                Cache coherence protocols should be used for this.

cache hit and cache miss:
      These are just simple terms for the accuracy of what goes into the CPU's cache. If the CPU accesses its cache looking for data it will either find it or it won't. If the CPU finds what's its after that's called a cache hit. If it has to go to main memory to find it then it is called a cache miss. The percentage of hits from the overall cache requests is called the hit rate.

TLB & MMU
    Most CPUs implement some form of virtual memory.
    Each program running on the machine sees its own simplified address space, which contains code and data for that program only. Each program uses this virtual address space without regard for where it exists in physical memory.
    Virtual memory requires the processor to translate virtual addresses generated by the program into physical addresses in main memory. The portin of the processor that does this translation is known as the memory management unit(MMU). The fast path through the MMU can perform those translations stored in the translation lookaside buffer(TLB), which is a cache of mappings from the operating system's page table.

Freescale - i.Mx
Marvel - XScale
Nvidia - Tegra
ST-Ericsson - Nova & NovaThor
Qualcomm - Snapdragon
TI - OMAP
Samsung - Hummingbird
Apple - A4,A5

#ifdef MY_DBG_EN
    #define MY_DBG printf
#else
    #define MY_DBG(fmt, ...) do {} while(0)

Linux Device Driver

Reference
[Anil Kumar Pugalia]

A device driver is a piece of software that drives a device.

Device - Device Controller - Bus - CPU
Devices are connected to device controller.
Device controllers are typically connected to the CPU through their respectively named buses (IDE, PCI, USB, SPI, I2C...).

Two types of drivers:
        1. Device driver
        2. Bus driver

1. Device Driver

Fig: Linux device driver partition

A device driver has two parts:
    1. Device specific  [Understand & decode device datasheet]
    2. Operating System(OS) specific [Tightly coupled with the OS mechanisms of user interface]

A device driver provides a 'systemcall', interface to the user; this is called the boundary line between the so called kernel space and user space of Linux.

In Linux a driver is broadly classified into three verticals:

Fig: Device Driver Classification

Network Vertical
     1. Network protocol stack
     2. Network interface card device drivers

Storage Vertical
  1. File System drivers   [ To decode various formats on different partitions]
  2. Block device drivers.[ For various h/w storage protocols like IDE,SCSI,MTD]

2. Bus Driver

In Linux, Bus drivers (or the horizontals) are often split into two parts:
          1. A device controller specific
          2. An abstraction layer over that for the verticals to interface, commonly
              called cores.
              [e.g.:   1. USB controller drivers - ohci, ehci etc,
                         2. USB abstraction - usbcore 
              ]

---

Dynamic Loading in Linux
In Linux, we can load or unload a driver on the fly, and it is active for use instantly after loading. Also it is instantly, disabled when unloaded. This is called dynamic loading and unloading of drivers in Linux.

* Linux kernel is an object oriented implementation in C.

Commands: insmod, lsmod, rmmod, modprobe, modinfo

Simple kernel module/driver
/* simple driver code
 * Author: Vinod Sasidharan
 */

#include
#include
#include

static int __init hello_init(void)
{
    printk(KERN_INFO "Hai: Hello connected");
    return 0;
}

static void __exit hello_exit(void)
{
    printk(KERN_INFO "Bye: Hello disconnected");
}

module_init(hello_init);
module_exit(hello_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Vinod Sasidharan");
MODULE_DESCRIPTION("Simple kernel module");

Makefile [Use this for all kernel modules; do change the name(hello.o)]

obj-m+=hello.o
all:
    make -C /lib/modules/$(shell uname -r)/build M=$(shell pwd) modules
clean:
    make -C /lib/modules/$(shell uname -r)/build M=$(shell pwd) clean
install:
    make -C /lib/modules/$(shell uname -r)/build M=$(shell pwd) modules_install
Commands
$ sudo su
$ make
$ insmod hello.ko
$ lsmod | grep hello
$ dmesg | tail -10
$ rmmod hello
$ dmesg | tail -10
$ objdump -d hello.ko
$ nm hello.ko

Tested on: Ubuntu 11.04 - the Natty Narwhal

---

 printk n kernel c

• Floating point is not supported in Linux kernel.
• When programming for the kernel, we don't bother about the float formats %f, %lf.
• All printk calls put their output into the (log) ring buffer of the kernel. Then the syslog daemon running in the user-space picks them up for final processing and re-direction to various devices as configure in the configuration file /etc/syslog.conf [Ubuntu: /etc/sysctl.conf]
• Typical destination: /var/log/messages
• A user space utility 'dmesg' is provided to directly parse the kernel ring buffer, and dump it to standard output.
• Kernel C is just standard C with some additional extensions from the C compiler.
• All functions with __init are supposed to be executed only once during boot up. So after their execution, kernel frees up RAM by removing them.
• Functions in the exit section are supposed to be called during system shut down.

---

Character Drivers

Fig: Character driver

If we write drivers for byte-oriented operations (or character oriented operations) then we refer to them as character drivers.

4 entities

1.     Application
2.     Character device file
3.     Character device driver
4.     Character device

• Character driver usage is done by the user space application through the character device file linked to it through the virtual file system (VFS).
• An application does the usual file operations on the character device file.
• Those operations are translated to the corresponding functions in the linked character device driver by the VFS.
• Those functions then do the final low-level access to the actual device to achieve the desired results.

---

---

---

OS Functions

1. Process Management
2. Memory Management
3. Device Management
4. Storage Management
5. Network Management

Root File System (RFS) in Linux

File system: Place to store data in form of files


The root file system refers to the file system mounted at the base of the file system hierarchy 
designated simply as /.

A minimal RFS should contain the following:

        Binaries (/bin,/sbin)
        Libraries (/lib)
        Devices (/dev)
        Configurations (/etc)
        Virtual File Systems (/proc, /sys)
        Applicaiton temporary file (/tmp)
        variable data from daemons & utilities (/var)
        user data (/root, /home) - Optional
        Mount points (/mnt, /media) - optional
        Additional software (/usr,/opt) - optional
        Bootloader files (/boot) - optional


bin - Binary executables, used by all users on the system
dev - Device nodes
etc - local system configuration files
home - user account files
lib - system libraries such as the  C library and many others.
sbin - binary executables usually reserved for superuser accounts on the system.
tmp -temporary files
usr - a secondary file system hierarchy for application programs, usually read-only.
var - contains variable files, such as system logs and temporary configuration files.
proc - a special file system containing system information
mnt - a placeholder for user-mounted devices and file systems.

Links:
1. http://libraryopt.sourceforge.net/
2. http://www.openembedded.org/wiki/Main_Page
3. http://buildroot.uclibc.org/

Custom Linux in BeagleBoard-xM

The golden reference:

    [labbookpages website]
    [Angstrom Linux - BeagleBoardXm]

Step1: Build the toolchain

    Use crosstool-ng
    [crosstool website]
    My version - crosstool-ng-1.9.3 [180 directories, 1227 files]
    Takes nearly 1 hour to build completely.
    At the end a set of executables viz. "arm-unknown-linux-gnueabi-gcc"
    etc. could be seen in the "x-tools/bin" directory.

Step2: Build the U-Boot

    Bootloader boots the system by copying the kernel &
    root file system to memory.
    [U-Boot website]
    [U-Boot Source Code]
    $ cd u-boot-2011.06/
    $ export CROSS_COMPILE=arm-unknown-linux-gnueabi-
    $ export PATH="/files/beagle/x-tools/bin:$PATH"
    $ make distclean [May have to be root]
    $ make omap3_beagle_config
    $ make
    "u-boot.bin" would be obtained in the same folder 'u-boot-2011.06'

Step3: Build the Xloader (MLO)

      [Xloader reference1] [Xloader reference2]

     Why xloader?
          The SRAM size in DM3730 is 64K.
          u-boot binary size is more than this.(~300K)
          x-loader binary size is lesser (~24K)
          Hence Xloader is required as the main loader
          in SRAM, which would download the u-boot image
          to main MDDR SDRAM.(512MB).
    $ git clone git://gitorious.org/x-load-omap3/mainline.git
    $ cd mainline
    $ make distclean
    $ make omap3530beagle_config
          (NOTE: config file updated in mainline
          tree for DM3730 in BeagleBoardXm)
    $ make
      The output would be "x-loader.bin"; which is in
      raw executable format.
      The size and address should be added at the
      image's first 16-bytes for non-XIP devices.
    Use signGP script [signGP Source Code]
    $ ./signGP x-load.bin
    "x-load.bin.ift" file would be created.
    $ mv x-load.bin.ift MLO

Step4: Build the Linux Kernel

    

Step5: Build the root file system

Step6: Create the boot script

Step7: Prepare the microSdCard

    5 files need to be stored in the uSd Card.
          1. MLO (Xloader)
          [ NOTE: This should be copied first to ensure that it is at the
          start of the card. After copying unmount & then re-mount  
          the card. ]
          2. u-boot.bin
          3. boot.scr (Boot script)
          4. uImage (Linux Kernel image)
          5. rootfs.ext2 (Root file system)

    Two partitions are created.
    The first is used to store the boot loader, kernel and root filing system. 
    The second partition can be used for general file storage.

    7.1 Delete existing partitions

     Remove the existing partition tables:

             root@neolappy:/files/beagle/vinchk#
             dd if=/dev/zero of=/dev/mmcblk0 bs=1024 count=1024

    7.2 Create primary partition

       
       root@neolappy:/files/beagle/vinchk# fdisk /dev/mmcblk0

    Device contains neither a valid DOS partition table, nor Sun, 

    SGI or OSF disklabel

    Building a new DOS disklabel with disk identifier 0x58bad9f5.

    Changes will remain in memory only, until you decide to write them.

    After that, of course, the previous content won't be recoverable.

    Warning: invalid flag 0x0000 of partition table 4 will be corrected 

    by w(rite)

    WARNING: DOS-compatible mode is deprecated. It's strongly recommended to

             switch off the mode (command 'c') and change display units to

             sectors (command 'u').

    Command (m for help): n
    Command action
       e   extended
       p   primary partition (1-4)
    p
    Partition number (1-4): 1
    First cylinder (1-122784, default 1): (Press Enter)
    Using default value 1
    Last cylinder, +cylinders or +size{K,M,G} (1-122784, default 122784): +64M

    Command (m for help): t
    Selected partition 1
    Hex code (type L to list codes): c
    Changed system type of partition 1 to c (W95 FAT32 (LBA))

    Command (m for help): a
    Partition number (1-4): 1

    

7.2 Create the 2nd partition

    Command (m for help): n
    Command action
       e   extended
       p   primary partition (1-4)
    p
    Partition number (1-4): 2
    First cylinder (2050-122784, default 2050): (Press Enter)
    Using default value 2050
    Last cylinder, +cylinders or +size{K,M,G} (2050-122784,
    default 122784): (Press Enter)
    Using default value 122784

    Command (m for help): t
    Partition number (1-4): 2
    Hex code (type L to list codes): 83

    Command (m for help):

7.3 Check created partitions & write

    Command (m for help): p

    Disk /dev/mmcblk0: 4023 MB, 4023386112 bytes

    4 heads, 16 sectors/track, 122784 cylinders

    Units = cylinders of 64 * 512 = 32768 bytes

    Sector size (logical/physical): 512 bytes / 512 bytes

    I/O size (minimum/optimal): 512 bytes / 512 bytes

    Disk identifier: 0x58bad9f5

   Device          Boot   Start    End       Blocks   Id     System

   /dev/mmcblk0p1   *     1        2049      65560    c      W95 FAT32 (LBA)

   /dev/mmcblk0p2         2050     122784    3863520  83     Linux

    Command (m for help): w
    The partition table has been altered!

   Calling ioctl() to re-read partition table.

   WARNING: Re-reading the partition table failed with error 16:

   Device or    resource busy.

   The kernel still uses the old table. The new table will be used at

   the next reboot or after you run partprobe(8) or kpartx(8)

   WARNING: If you have created or modified any DOS 6.x

   partitions, please see the fdisk manual page for additional

   information.

   Syncing disks.

Partitions: mmcblk0
                            1. mmcblk0p1
                            2. mmcblk0p2

7.4 Create the file systems in the partitions

    Partition1: mkfs.vfat -F 32 -n "boot" /dev/mmcblk0p1

    Partition2: mke2fs -L "files" /dev/mmcblk0p2 

    root@neolappy:/files/beagle/vinchk# mkfs.vfat -F 32 -n "boot" /dev/mmcblk0p1
    mkfs.vfat 3.0.9 (31 Jan 2010)

    root@neolappy:/files/beagle/vinchk# mke2fs -L "files" /dev/mmcblk0p2 
    mke2fs 1.41.14 (22-Dec-2010)
    Filesystem label=files
    OS type: Linux
    Block size=4096 (log=2)
    Fragment size=4096 (log=2)
    Stride=0 blocks, Stripe width=0 blocks
    241920 inodes, 965880 blocks
    48294 blocks (5.00%) reserved for the super user
    First data block=0
    Maximum filesystem blocks=989855744
    30 block groups
    32768 blocks per group, 32768 fragments per group
    8064 inodes per group
    Superblock backups stored on blocks: 
        	32768, 98304, 163840, 229376, 294912, 819200, 884736

    Writing inode tables: done                            
    Writing superblocks and filesystem accounting information: done

    This filesystem will be automatically checked every 32 mounts or
    180 days, whichever comes first.  Use tune2fs -c or -i to override.

what is systems software?

Operating system and utility programs manage computer resources at a low level.
Software is generally divided into:
1. Systems software
2. Applications software

Applications software comprises programs designed for an end user, such as word processors, database systems, and spreadsheet programs.
Systems software includes compilers, loaders, linkers and debuggers.

Tech links: Embedded linux

1. Cross Compiler

http://www.linuxjournal.com/content/cross-compiling-options

2. Boot time reduction

http://www.linuxjournal.com/magazine/reducing-boot-time-embedded-linux-systems?page=0,2

3. Steps for building embedded linux systems

http://www.linuxjournal.com/article/9686

Baudrate issue in Beagleboard Xm

While working with Beagleboard Xm I faced a strange issue related to baud rate.
My setup:
   1. Beagle Board Xm
   2. Acer 4930 Laptop
   3. 5v,3Amps supply for Beagleboard
   4. USB to serial converter. [Detected as /dev/ttyUSB0 - minicom is used on host side]
The issue:
  1. Getting jumbled characters in u-boot menu at times
  2. This continues even if the kernel is up.
Solution:
For u-boot:
Change the current baudrate "setenv baudrate 19200"
Change the baudrate in minicom "CTRL A,Z; O; Serial Port Setup; E; B(Require times for 19200)"
For seeing the kernel messages:
Before booting the kernel set the proper bootargs to be passed.
"setenv bootargs console=ttyS2,19200n8"
NOTE: The kernel boot-up messages could be seen; but the login prompt is not seen due to the issue. Here change back minicom(host side) baud rate to 115200.
Now the login prompt could be seen; but the jumbled character issue would be there.
Still login using the required credentials.
After logging in:
Use the shell command to change baudrate of required serial port
"stty -F /dev/ttyS2 speed 19200"

BeagleboardXm Experiments

Install "u-boot-tools" also to use mkimage.
#sudo apt-get install u-boot-tools

Start Here with Beagle Board Xm

==================================
Build Root: Download source errors
1. genext2fs -> http://sourceforge.net/projects/genext2fs/files/
2. fakeroot --> http://sources.buildroot.net/
STEPS:
1. make menuconfig
2. Select - Build Options
3. Select - Mirrors and Download locations
4. Set "Primary Download site" as "http://sources.buildroot.net/"
===================================

How to configure vi for source code browsing?

Install
1. Install ctags
The ctags program which is written by the VIM team is called " Exuberant Ctags" and supports the most features in VIM.Use it.
2. Install cscope
3. Download and place "cscope_maps.vim" plugin in your directory "$HOME/.vim/plugin".
[If the directories are not there, create them using mkdir command]


Create Database for ctags & cscope
In your source code directory:
    1. ctags -RV
    2. cscope -Rvb


How to navigate?
Place cursor on any symbol(function name,variable...) & press the key combinations.
1. ctags:
    CTRL + ], SHIFT + 8, CTRL + T, CTRL + I, CTRL + O
2. cscope
    CTRL + \ + s

Advanced Vi Tutorial

The questions

C Programming
1. Pointers
2. Bit-arithmetic
3. Basic data structures(list,queue,stack,hash table, array).Data structure selection for different situations: time complexity/memory useage tradeoffs
4. Notions of virtual address and physical address and how pointers can be used to access them
5. Differences between libray calls versus system calls
6. How various commonly used routines like - malloc(), free() , printf() are implemented
7. If you have networking background - get an idea of how typical networking routines like connect(), bin(), recv(), sento(),recvfrom() are implemented.

Operating Systems(linux,unix(bsd),vxWorks)
1. Get an idea of common OS services are implemented
- what is involved in process/task/thread creation
- what is involved in locking or unlocking a semaphore
- what is involved in implementing a sleep() routine
2. If you have networking background, get an idea of how packets traverse the stack from wire to socket buffers through different execution contexts like interrupts and/or tasks and/or tasklets and/or bottom-halfs and/or work-queues and/or processes and/or softirqs and/or ISRs. An idea of what are the typical API used in transition between network stack layers and different contexts of execution.
3. Get and idea of the type of locking to use for a given mutual exclusion requirement- for example when to use semaphore versus spinlock or when to use spinlock versus irq_disable/enable. An idea of locks are eligible for use in which execution contexts.


Architecture(x86/MIPS/PowerPC/ARM/any other 32-bit or 64-bit processor)
1. Differences between virtual memory and physical memory
2. What is segmentation fault or page fault and physical memory
3. what is involved in DMA transfer
4. How is a spinlock implemented - what assembly instructions
5. Differences between 32-bit and 64-bit CPUs and impact of that on software and how software can be designed to be portable.
6. Commonly used compiler flags and optimizations. Impact of this options(+ve or -ve) on program execution.