Monday, 16 December 2013

[C Programming] Function Pointers basics in C

Function Pointers

Definition

Function pointers are pointers, which points to the address of a function. Function pointers are variables only, so it will be declared and defined like other variable.

Syntax

<data_type> (*function_pointer_name) (variable data_type list) = NULL; /* defining function pointer and initializes to NULL */

The signature of this function pointer should match with the signature of function which address is stored in this pointer.

Sample code

float doMath (float a, float b) {
 /*
    desired code
 */
return result;
}

int main() {
float (*math_pointer) (float, float) = NULL;

math_pointer = &doMath; /* pointer to function doMath() */

output = math_pointer (10.5, 11.1);
/*
   desired code
*/
return 0;
}


Usage

  1. To replace switch/if conditional statements
  2. To implement late-binding (runtime binding) (C++ scenario)
  3. To implement callbacks

Example for Usage-1

#include<stdio.h>

float addition (float a, float b) {
 return a + b;
}

float subtraction (float a, float b) {
 return a - b;
}

float multiplication (float a, float b) {
 return a * b;
}

void select (float a, float b, char opCode) {
float result;
switch(opCode)
{
 case '+': result = addition(a, b); break;
 case '-': result = subtraction(a, b); break;
 case '*': result = multiplication (a, b); break;
}
printf("Result: %f\n", result);
}

/* Replace the above switch statement with function pointer */
void select_function_pointer (float a, float b, float (*math_pointer)(float, float)) {
float result = math_pointer(a, b); /* Calling function using function pointer */
printf("Result: %f\n", result);
}

void main()
{
  float a, b;
   
  select(10, 15, '+');
  select_function_pointer (10, 15, &addition); /* Passing function as an address argument */
}


Array of Function Pointers

Since the Function pointer is a variable, we can define array of function pointer using below syntax.


Syntax-I
tyepdef <data_type> function_pointer_name (argument data_type list);
function_pointer_name array_fun_pointer [10] = {NULL};

Syntax-II
<data_type> (*array_fun_pointer[10])(argument data_type list) = {NULL};

array_fun_pointer [0] = &function1;
.
.
Calling function using function pointer
(*array_fun_pointer[0]) (arguments); or
array_fun_pointer[0](arguments);


Implementation of Callbacks using Function Pointers

It is a bit more complex syntax. Try to understand the callback mechanism in C by using below sample code:

void insert_array (int *array, size_t size, int (*getNextValue) (void))
{
     for (int i = 0; i < size; i++)
        array[i] = getNextValue();
}

int getNextRandomValue()
{
   return rand();
}

int main()
{
   int a[10];
   insert_array(a, 10, &getNextRandomValue);
}

Here, the function insert_array() takes the 3rd argument as the function address using function pointer getNextValue. And, the callback function is getNextRandomValue(), returns random value. The function insert_array() calls this callback function using function pointer getNextValue for inserting the values into the array.

The similar explanation can be found here (from Stackoverflow)

Monday, 2 December 2013

Tasklet Vs Work queues [Part-II]

For Tasklet Vs Work queues [Part-I], please click here.

Work queues

Work queues are added in linux kernel 2.6 version. And, one major difference between Work queues and Tasklets is that the handler function of work queues can sleep but not possible in the case of Tasklet's handler function.

Another difference is that the Work queues have higher latency than Tasklet.

We should look at two main data structures in the Work queue mechanism.
  1. struct workqueue_struct
  2. struct work_struct
The core work queue is represented by structure struct workqueue_struct, which is the structure onto which work is placed. This work is added to queue in the top half (Interrupt context) and execution of this work happened in the bottom half (Kernel context).

The work is represented by structure struct work_struct, which identifies the work and the deferral function.

Kernel threads named "events/X" will extract work from the core work queue and activates the work's handler function.

Work queue APIs

Create and destroy work queue structure

struct workqueue_struct *create_workqueue(name); /* Creates core workqueue */
void destroy_workqueue(struct workqueue_struct *); /* Destroy the workqueue */

Initialization of work structure

Work queue API provides 3 macros which initializes the work and also set the function handler.

INIT_WORK(work, function);
INIT_DELAYED_WORK(work, function); /* if we add any delay before adding this work into work queue structure */
INIT_DELAYED_WORK_DEFERRABLE(work, function);

EnQueue work on to work queue

Below are work queue APIs used for adding queue on to work queue.

int queue_work (struct workqueue_struct *wq, struct work_struct *work);
int queue_work_on (int cpu, struct workqueue_struct *wq, struct work_struct *work); /*  specify the CPU on which the handler should run */
int queue_delayed_work (struct workqueue_struct *wq, struct delayed_work *work), unsigned long delay); /* Queue specified work on to specified work queue after delay */
int queue_delayed_work_on (int cpu, struct workqueue_struct *wq, struct delayed_work *work), unsigned long delay);

The below functions doesn't require workqueue structure defined. These functions uses kernel-global work queue. So, no need to pass workqueue_struct in the argument list.

int schedule_work (struct work_struct *):
int schedule_work_on (int cpu, struct work_struct *):
int scheduled_delayed_work (struct delayed_work *, unsigned long delay);
int scheduled_delayed_work_on (int cpu, struct delayed_work *, unsigned long delay);

Cancel work

/* terminate work in the queue, which is not already executing in the handler */
int cancel_work_sync (struct work_struct *); 
int cancel_delayed_work_sync (struct delayed_work *);

Flush work

Below functions are used to flush the work and works in the specified workqueue.
/* Flush a particular work and block until it is completed */
int flush_work (struct work_struct *);
/* Flush all works in given workqueue and block until it is completed */
int flush_workqueue (struct workqueue_struct *);
/* Flush  kernel-global work queue */
void flush_scheduled_work (void);

Status of work

We can use below two functions to know whether the given work is pending i.e. its handler function is not yet started.
work_pending(work);
delayed_work_pending (work);

Next: Will share running examples for Tasklet and work queues.

Thursday, 28 November 2013

Tasklets Vs Work queues in the kernel

Tasklets Vs Work queues in the kernel

Tasklets and work queues used to implement deferrable functionality in the kernel. Using the Tasklets and Work queues, we can schedule a function to run at later point of time.

Deferrable functions:

It is a mechanism for supporting delayed execution of functions (not urgent functions), used in interrupt handlers.
Types of deferrable functions
1.       Tasklets
2.       Work queues
Mostly, we use these functions in Interrupt Handlers. Because some or majority of the interrupts are disabled in interrupt context. So, if the functions take more time for execution in this context then the latency to handle other hardware interrupts. Generally, we enter into interrupt context when a hardware interrupt is raised.
If we add Deferrable function in the interrupt handlers then this function will be executed in Kernel Context where the all hardware interrupts are in enable mode. So, we move function of code which can later be executed without any harm using deferrable function. And, hence we are minimizing the latency to handle hardware interrupts.
Generally the processing of work done in interrupt handler called as Top Half.
And, the processing of work done in kernel context called as Bottom Half.
Aim: Reduce work (execution time of handler code) in Top Half
We can achieve this using Tasklets method or Work queue.

Using Tasklets:

As already mentioned, the main job of the Tasklets is to schedule the work (function) to run later point of time so that we can decrease the amount of work done in interrupt handlers.

/* Declaring Tasklet */

void tasklet_function(unsigned long data);
DECLARE_TASKLET(tasklet_name, tasklet_function, tasklet_data);

/* Scheduling Tasklet */

tasklet_schedule(&tasklet_name);

Tasklets are represented by tasklet_struct structure.
struct tasklet_struct {
                struct tasklet_struct *next; /*pointing to next tasklet structure */
                unsigned long state; /* state = TASKLET_STATE_SCHED or TASKLET_STATE_RUN */
                atomic count; /* 0 = Enable; !0 = Disable */
unsigned long data;
void (*func) (unsigned long); /*func(data) */
}
Tasklets are defined using a macro DECLARE _TASKLET, which initializes the tasklet_struct using its arguments tasklet_name, tasklet_func and data.
Tasklets are enabled by default when defined using DECLARE_TASKLET macro, so that we can schedule it directly without using any other APIs.
But, if we declare tasklet using DECLARE_TASKLET_DISABLED macro then we should explicitly call tasklet_enable() API before scheduling this tasklet.

Tasklet APIs:

/* Defining Tasklet using macros */
DECLARE_TASKLET(name, func, data);
DECLARE_TASKLET_DISABLED(name, func, data);

void tasklet_init(struct tasklet_struct *, void (*func) (unsigned long), unsigned long data); /*initializes the tasklet structure with user provided info */


/* Enabling and Disabling a tasklet using enable() and disable() */
void tasklet_enable(struct tasklet_struct *); /* Enable normal priority scheduling */
void tasklet_disable(struct tasklet_struct *); /* returns after disabling the tasklet */
void tasklet_hi_enable(struct tasklet_struct *); /* Enabling High priority scheduling */
void tasklet_disable_nosync(struct tasklet_struct *); /* may returns before termination */


/* Schedule a tasklet*/
void tasklet_schedule (struct tasklet_struct *); /* Normal priority scheduling */
void tasklet_hi_schedule (struct tasklet_struct *); /* Higher priority scheduling */


CPU maintains the normal and high priority softirq vectors lists (normal priority vector list and high priority vector list) where these functions are queued.
If the function is higher priority function then it is enqueued in higher priority softirq vector list and similar case for normal priority functions.


The below two functions are used to kill a tasklet
void tasklet_kill(struct tasklet_struct *);
void tasklet_hi_kill(struct tasklet_struct *); /* Kill the tasklet and ensure they would never run */

Sample Program: tasklet.c

#include<linux/module.h>
#include<linux/kernel.h>
#include<linux/interrupt.h>
char tasklet_data[] = "tasklet function was called";
void my_tasklet_function (unsigned long data) {
        printk("%s: in %s\n", (char*)data, __func__);
}
DECLARE_TASKLET(my_first_tasklet, my_tasklet_function, (unsigned long)&tasklet_data);
int init_module()
{
        /* schedule our my_tasklet_function */
        tasklet_schedule(&my_first_tasklet);
        return 0;
}
void cleanup_module(void)
{
        tasklet_kill(&my_first_tasklet);
        return;
}

Makefile:

obj-m += tasklet.o
KDIR = /usr/src/linux-headers-2.6.32-28-generic
all:
        $(MAKE) -C $(KDIR) SUBDIRS=$(PWD) modules
clean:
        rm -rf *.o *.ko *.mod.* *.symvers *.order

Execution:

sudo insmod tasklet.ko

Output: dmesg


[3302661.097630] tasklet function was called: in my_tasklet_function

Next: Will cover work queues also...

Saturday, 23 November 2013

[C programming] Storage classes in C

Storage classes in C

C supports four different storage classes. These are auto, register, static and extern storage classes.

C compiler automatically assigns auto storage class when we declare a variable without any storage class.

<syntax of storage class in c>

<storage_class> <data_type> <variable_name>;


<storage_class> gives the information about where the variable is stored in memory, default initial value, scope of the variable and it’s life time.

AutoRegisterStaticExtern
Default storage class.
int variable;
/*Above Declaration is same as below one */
auto int variable;
/*Declaration*/
register int variable;
/*Declaration*/
static int variable;
/* Declaration */
extern int variable;
Stored in stack memoryStored in CPU registersStored in Data segmentStored in Data segment
Default initial value: Contains garbage value by default.Default initial value: Contains garbage value by default.Default initial value: Default initial value of variable is 0Default initial value: Default initial value of variable is 0
Scope: local to the functionScope: local to the functionScope: local to the functionScope: visible to the outside of the file.
Value of variable persists in function.Value of variable persists in function.Value of variable persists between function callsVariable can be shared between multiple files
Lifetime: Variable is de-allocated when the function (where the variable is declared) execution is overLifetime: Variable is de-allocated when the function execution is overLifetime: Variable is de-allocated when the program is terminated after completion of job. So, lifetime doesn’t dependent on function execution.Lifetime: Variable is de-allocated when the program is terminated after completion of job.

Extern variable vs Global variable:

The scope of the global variable is limited to the file where it is declared. But, in case of extern variable, it can be shared among functions. So, variable visibility is more compared to global variable.

Both global and extern variables are stored in data segment and have default initial value is 0.

References:


Saturday, 9 November 2013

What is Google ?

Today, I read a article "What Makes Google Services Work So Fast ?" at googlersays.com. This articles reveals something new and interesting facts about Google and its services.

We know that Google services are very fast, reliable, robust and trustworthy. We store our confidential information in Google services like Docs, gmail etc.

Google uses proprietary software which keeps its services at No.1 position.

Google File System: Google uses its own file system named as GFS (Google File System), provides reliable and efficient access to data.

Chubby: Google developed a lock services called Chubby, used for Shared resource management system. Heavily used as Domain Name Server.

BigTable: Google uses a Non-Relational Database called BigTable

Google also uses a OpenSource software for processing data

MapReduce: is s/w framework for processing large amount of unstructured data.

Linux Operating System: Majority of the Google servers/computers runs with Linux OS.

Please read the article What Makes Google Services Work So Fast ? for more details.


Thursday, 7 November 2013

[C Programming] Check if two strings are anagrams

Anagram: Two strings S1 and S2 are called anagrams when string S2 can be formed if we rearrange the letters in string S1 and vice-versa.


Example: S1 = god, S2 = dog

Solution:
------------
If we apply XOR property here then we can easily find the given strings are anagrams or not.

1 XOR 1 = 0
1 XOR 0 = 1
a XOR z = 1
s XOR s = 0

If Inputs to the XOR operator are equal then result would be ZERO.

Apply XOR for each alphabet in both strings. If the result is ZERO then the strings are anagrams else not anagrams. It may not be sufficient condition since the strings "aaa" and "bbb" are not anagrams but still the XOR of these two strings is ZERO. Hence, one more check was needed to eliminate these usecases. Compute the sum of ascii value of two strings and check if they are equal. If equal then the two given strings are anagrams.

Sample code (anagram_string.c):
--------------------------------------
  #include<stdio.h>
  #include<string.h>

  void main(int argc, char *argv[])
  {
          char *str1, *str2;
          int xor, i;
          int sum1 = 0, sum2 = 0;


          if ( argc != 3 ) /* argc should be 3 for correct execution */
          {
                  /* argv[0] is the program name */
                  printf( "usage: %s string1 string2\n", argv[0] );
                  return;
          }

          str1 = argv[1];
          str2 = argv[2];

          printf("Entered strings \"%s\" and \"%s\"\n", str1, str2);

          if (strlen(str1) != strlen(str2)) {
                  printf("Given Strings are not anagrams\n");
                  return;
          }

          for (i = 0; i < strlen(str1); i++) {
                  xor ^= str1[i];
                  xor ^= str2[i];
                  sum1 += str1[i];
                  sum2 += str2[i];
          }

          if (!xor && (sum1 == sum2))
                  printf("Given Strings are anagrams\n");
          else
                  printf("Given Strings are not anagrams\n");

  }

Output:
======
gcc anagram_string.c
./a.out ram arm

Entered strings "ram" and "arm"
Given Strings are anagrams

You might also like

Related Posts Plugin for WordPress, Blogger...