c: alignment of structure

In this article I assume that the computer's word size is 4 bytes(IA32), because the main idea is the same for all architectures and I want to keep the article clean. You just have to adjust this article to your platform.

So, what's with the size of the structure?
You should know that members of data structure(represented by struct keyword in c) are aligned to the power of 2. Each element is stored in the closest(next) address with the appropriate alignment. The whole structure should be aligned as aligned its member with the longest alignment.
The type of each member of the structure usually has a default alignment(if you are not using #pragma pack directive). It's 1 byte for char, 2 bytes for short, 4 bytes for int. You should check this table for your arch.
So the structure

struct
{   
    char a;
    short b;
    int c;
} data;

should be 8 bytes long. How is it calculated? The structure has one char, one short and one int members. The alignment should look like

+-----------------------------------+
|char| XX |  short |       int      |
+-----------------------------------+
0         2        4                8

The short member is stored on the distance of 2 bytes from the address of char because the alignment of short is 2 bytes, the int member is stored just after the short, because the address from the beginning(in this case, or in general from the previously aligned members) is suitable for alignment of int.
But if you change the sequence of the members the whole picture could change, though the number of members and their sizes didn't change. The structure

struct
{   
    char a;
    int c;
    short b;
} data;

on the same platform should be 12 bytes long. Why? Let's calculate.

+---------------------------------------------+
|char| XX | XX | XX |       int      |  short |
+---------------------------------------------+
0         2        4                8         12

That's because the address of integer member is adjusted to its alignment.

Knowing these rules you can optimize the sizes of the structures just moving position of the members inside the structure. Let's add one char in the end to the previously declared structure:

struct
{   
    char a;
    short b;
    int c;
    char d;
} data;

The size of the structure is 12. It's easy to calculate. The size of the structure should be as aligned its member with the longest alignment. In this case the longest alignment is 4. Sequence of char, short, int is aligned to 8 bytes. Adding one char to the end you force compiler to align the structure to 12 bytes, it can't be 9 or anything else. If you look at the alignment of the original structure you could see unused byte that appeared because of the alignment. Let's move d just after(or before, doesn't matter) the a structure member:

struct
{   
    char a;
    char d;
    short b;
    int c;
} data;

The size of this structure should be 8 bytes.

+-----------------------------------+
|char|char|  short |       int      |
+-----------------------------------+
0         2        4                8

If you deal with embed devices where you have significantly small amount of memory it's good optimization. 8 bytes vs. 12 bytes, or 1K vs. 1.5K in case of 128 copies of the structure.

Another approach which is also platform and compiler dependent is to use #pragma pack directive. In general structure

struct
{   
    int c;
    short b;
} data;

should be 8 bytes long. But if you use #pragma pack with alignment to 2 bytes you may force the whole structure will be aligned to 2 bytes.

#pragma pack(push)
#pragma pack(2)

struct
{   
    int c;
    short b;
} data;

#pragma pack(pop)

This structure should be 6 bytes long.

The alignment can cause troubles especially if the data is transmitted between different platforms where alignment or size of type may differ. If it's possible strings(sequences of bytes/chars) should be used. Their alignment should always be 1 byte long.

c: executing shellcode

In previous article I've described how to overwrite function's return point to execute some code.
I *nix world most of the code is being written in c. So most likely you will have to deal with stack overflows in c.

The basics remain the same. You have to find the top of the stack of a function, calculate the address of the return point and write the beginning of your code into it.
Let's look at the code below.

#include <stdio.h>

void function()
{
    int *p;
    printf("&p: %p\n", &p);
}

int main(int argc, char **argv)
{
    function();

    return 0;
}

The address of pointer p should be the top of the stack of our function. The output should looks like

&p: 0xbffdf594

The address might change between the program execution. Running this program in gdb, stopping in the beginning of the function and looking at address of p and values of the register you can see that the difference between the &p and %esp is 4 bytes.

(gdb) l
2 
3 void function()
4 {
5     int *p;
6     printf("&p: %p\n", &p);
7 }
8 
9 int main(int argc, char **argv)
10 {
11     function();
(gdb) b 5
Breakpoint 1 at 0x804838a: file so.c, line 5.
(gdb) r
Breakpoint 1, function () at so.c:6
6     printf("&p: %p\n", &p);
(gdb) i r
esp            0xbff2d490 0xbff2d490
ebp            0xbff2d4a8 0xbff2d4a8
...
(gdb) p &p
$1 = (int **) 0xbff2d4a4

Indeed, &p is on the top of the stack. We should take into account that usually %ebp is pushed onto the stack, so the difference between &p and return point is 8 bytes.

(gdb) disass
Dump of assembler code for function function:
0x08048384 <function+0>: push   %ebp
0x08048385 <function+1>: mov    %esp,%ebp
0x08048387 <function+3>: sub    $0x18,%esp
0x0804838a <function+6>: lea    -0x4(%ebp),%eax
0x0804838d <function+9>: mov    %eax,0x4(%esp)
0x08048391 <function+13>: movl   $0x80484a0,(%esp)
0x08048398 <function+20>: call   0x8048298 <printf@plt>
0x0804839d <function+25>: leave  
0x0804839e <function+26>: ret    

We are almost ready for the hack. Let's write some shellcode that would be executed instead of returning from function to main.
I'm not strong in writing shellcode and asm, so let it be simple code that will call exit with exit code 1. The asm code is

.text

.global main
main:
movl $1, %eax
movl $1, %ebx
int $0x80

Having compiled and linked code is not enough, we can't just put ELF binary as a shellcode. I used objdump to extract disassembled code of main and its representation in machine commands.

$objdump -d shellcode
...
08048354 <main>:
 8048354: b8 01 00 00 00        mov    $0x1,%eax
 8048359: bb 01 00 00 00        mov    $0x1,%ebx
 804835e: cd 80                 int    $0x80
...

The code begins from address 8048354 and ends at 8048360. To use the instructions as a shellcode they should be put into an ascii zero-ended string where each code is prefixed with '\x'. The string with shellcode will be "\xb8\x01\x00\x00\x00\xbb\x01\x00\x00\x00\xcd\x80".
Let's integrate the shellcode into our program.

#include <stdio.h>

char shellcode[] = "\xb8\x01\x00\x00\x00\xbb\x01\x00\x00\x00\xcd\x80";

void function()
{
    int *p; 
    printf("&p: %p\n", &p);
    p = (int *)&p + 2;
    *p = (int)shellcode;
}

int main(int argc, char **argv)
{
    function();

    return 0;
}

Here I assigned the address of &p plus 8 bytes, which should be the return point, to the pointer. So p now points exactly to the return point. Later I write the address of the shellcode to *p, that is actually a return point.
If you execute this code and check the exit code you should see

$./so
&p: 0xbfd262e8
$echo $?
1

As expected the program exited with code 1. Let's walk through the execution process.

(gdb) l
6 {
7     int *p;
8     printf("&p: %p\n", &p);
9     p = (int *)&p + 2;
10     *p = (int)shellcode;
11 }
12 
13 int main(int argc, char **argv)
14 {
15     function();
(gdb) b 11
Breakpoint 1 at 0x80483b0: file so.c, line 11.
(gdb) r
&p: 0xbff2d4a4

Breakpoint 1, function () at so.c:11
11 }
(gdb) n
0x080495b8 in shellcode ()
(gdb) disass
Dump of assembler code for function shellcode:
0x080495b8 <shellcode+0>: mov    $0x1,%eax
0x080495bd <shellcode+5>: mov    $0x1,%ebx
0x080495c2 <shellcode+10>: int    $0x80
0x080495c4 <shellcode+12>: add    %al,(%eax)

Instead of returning to main the execution moved to the address 0x080495b8. Disassembled code of the shellcode is exactly the same as we have generated.

Actually this shellcode won't work in the real world because it contains null-bytes. Mostly buffer overflow attacks are used against string functions from libc and they will cut this code.

A lot of interesting shellcodes you may find at the metasploit project site.

Please note, I've suceeded with runnning this code with gcc-4.3.2 and linux-2.6.27.
With gcc-4.1.2, gcc-3.4.6 and linux-2.6.25 I didn't succeed to run the shellcode and ran into segfault with and without -fno-stack-protector gcc flag. I've also checked kernel.randomize_va_space system parameter but switching it to the different values didn't help. Unfortunately I don't know why this is not working. Actually it's failing on

mov    $0x1,%eax

I have no idea why writing value to the register causes segfault. Most likely that's not a gcc 'issue' but kernel(or kernel configuration), because my kernel 2.6.27 is not secure at all because I'm sitting behind the firewall and some performance benefit by turning off security features is critical for me.

c++: partial template specialization of class methods

In c++ it's possible to specify class method of template class.
Before I thought it's only possible to specify the whole class and then redefine functions. It could be painful if template class contains a lot of methods. Of course the expected class could be built deriving from template class specifying the new type and redefining needed functions:

template<typename T>
class B
{
    public:
        void operator ()()
        {  
            std::cout << "B<" << typeid(T).name() << ">::operator ()" << std::endl;
        }  
        void method()
        {  
            std::cout << "B<" << typeid(T).name() << ">::method()" << std::endl;
        }  
};

class C: public B<int>
{
    public:
        void operator ()()
        {  
            std::cout << "C<long#pseudo class specialization>::operator () with deriving from B<int>" << std::endl;
        }  
};
int main(int argc, char **argv)
{
    C()();
    C().method();
}

The output you expect should be

C<long#pseudo class specialization>::operator () with deriving from B<int>
B<i>::method()

We get the class C which is the same as B<int> but with custom operator ().
Unfortunately this code changes the name of the class and developer should keep in mind that class C is B<int> with custom functions. This is not explicit even if you find better name than C.

Another way, that is a c++ way, to specify methods of template class. Let's say we have class A defined below:

template<typename T0>
class A
{
    public:
        void operator ()()
        {
            std::cout << "A<" << typeid(T0).name() << ">::operator ()" << std::endl;
        }
        template<typename T1>
        void method()
        {
            std::cout << "A<" << typeid(T0).name() << ">::method<" << typeid(T1).name() << ">()" << std::endl;
        }
};

Here we can redefine both operator () and method() class methods:

template<>
void
A<float>::operator ()()
{
    std::cout << "A<float#method specialization>::operator ()" << std::endl;
}

template<>
template<>
void
A<float>::method<float>()
{
    std::cout << "A<float#method specialization>::method<float#method specialization>()" << std::endl;
}

operator () for A<float> and method<float> for A<float> have been specified. What actually happen? There was created fully specified class A for type float and both of its methods have been defined.
The output of

int main(int argc, char **argv)
{
    A<int>()();
    A<float>()();
    A<float>().method<float>();

    return 0;
}

should be

A<i>::operator ()
A<float#method specialization>::operator ()
A<float#method specialization>::method<float#method specialization>()

You can see that appropriate methods have been called.

As I mentioned before, if you do a class specialization you have to redefine all methods:

template<>
class A<double>
{
    public:
        void operator ()()
        {  
            std::cout << "A<double#class specialization>::operator ()" << std::endl;
        }  
        template<typename T1>
        void method()
        {  
            std::cout << "A<double#class specialization>::method<" << typeid(T1).name() << ">()" << std::endl;
        }  
};

Otherwise if you don't define method for A<double> and it's used somewhere in this context compiler will rise an error that no member method was defined in class A<double>. Class specialization should be used instead of class method specialization if the specialization changes the behavior of the most members of the class. Doing specialization you are defining new class with the same as template class but optimized for special case. Using the code above the next program

int main(int argc, char **argv)
{
    A<double>()();
    A<double>().method<int>();

    return 0;
}

should produce

A<double#class specialization>::operator ()
A<double#class specialization>::method<i>()

You see that methods from A<double> have been called.

And even in the case of template class specialization you still able to specify its template methods.

template<>
void
A<double>::method<double>()
{
    std::cout << "A<double#class specialization>::method<double#method specialization>()" << std::endl;
}

The program

int main(int argc, char **argv)
{
    A<double>().method<int>();
    A<double>().method<double>();

    return 0;
}

should show on stdout next messages

A<double#class specialization>::method<i>()
A<double#class specialization>::method<double#method specialization>()

At first 'undefined' method of A<double> was called and later specialized one.

Template specialization is a powerful mechanism and should be used with comprehension.

c: to exit or to _exit?

There are two functions that allow you to legally terminate your program: exit and _exit.

Both of them immediately terminate the process, close file descriptors, flush all open streams with unwritten buffered data and close all of them, send SIGCHLD signal and return exit code to the parent process if it has no set SA_NOCLDWAIT, or has not set the SIGCHLD handler to SIG_IGN.
If the process is a session leader and its controlling terminal is the controlling terminal of the session, then each process in the foreground process group of this controlling terminal is sent a SIGHUP signal, and the terminal is disassociated from this session, allowing it to be acquired by a new controlling process.

The main difference is that exit calls all functions registered with atexit and on_exit while _exit does not.
Also the threads terminated by a call to _exit() shall not invoke their cancellation cleanup handlers or per-thread data destructors.

It's worth to note that using return from main function has the same behavior as calling exit with the returned value.

How is user or developer is affected by the difference between these calls?
First of all the differences become significant when we are talking about the processes that call fork(or any other routine to create child thread or process).

I read about the side effects of calling exit from the child that caused temporary files unexpectedly removed. I haven't ever been affected by this when I used exit from the child process.
Though I'm trying to use _exit from the child processes.
This sample illustrates the absence of this possible effect at least on my system.

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/wait.h>

int main(int argc, char **argv)
{
    FILE *tmp = tmpfile();

    if (fork() == 0)
    {   
        fprintf(tmp, "Hello from child<%d>!\n", getpid());
        fflush(tmp);
        exit(0);
    }   
    else
    {   
        sleep(1);
        wait(NULL);

        char msg[256];
        fseek(tmp, 0, SEEK_SET);
        fgets(msg, 256, tmp);
        printf("message: %s\n", msg);
    }   
            
    return 0;
}

$./exit 
message: Hello from child<16489>!

The things go worse when we are talking about c++.

Destructors of global and static data are being called on at_exit stage.
After you have called the constructor of global or static object GCC automatically calls the function

int __cxa_atexit(void (* f)(void *), void *p, void *d);

Where f is a function-pointer to the destructor, p is the parameter for the destructor and d is the "home DSO" (DSO = dynamic shared object). When the process exits

void __cxa_finalize(void *d);

should be called with d = 0 in order to destroy all with __cxa_atexit registered objects.

Let's look at some samples that show side effects of calling _exit or exit from both child and parent processes.
Say we have class A that is stored in the global memory region.

#include <iostream>

using namespace std;

class A
{
    public:
        A(){cout << "A(), " << getpid() << endl;}
        ~A(){cout << "~A(), " << getpid() << endl;}
};

A a;

• The first case is when both child and parent call exit to terminate themselves.

  int main(int argc, char **argv)
  {
      if (fork() == 0)
      {   
          cout << "child, " << getpid() << endl;
          exit(0);
      }   
      else
      {   
          cout << "parent, " << getpid() << endl;
          sleep(1);
          wait(NULL);
          exit(0);
      }   
              
      return 0;
  }

  The output might be

  $./exit
  A(), 17186
  child, 17187
  ~A(), 17187
  parent, 17186
  ~A(), 17186

  You see that the object was constructed once but the destructor was called twice from the child and parent processes. This can cause really bad things.
• The second case is when the child calls exit and the parent calls _exit.

  int main(int argc, char **argv)
  {
      if (fork() == 0)
      {   
          cout << "child, " << getpid() << endl;
          exit(0);
      }   
      else
      {   
          cout << "parent, " << getpid() << endl;
          sleep(1);
          wait(NULL);
          _exit(0);
      }   
              
      return 0;
  }

  The output might be

  $./exit 
  A(), 17212
  parent, 17212
  child, 17213
  ~A(), 17213

  The constructor was called once from the parent process and destructor was called once but from the child process. You may not notice the effect unless you use object in the parent process. In spite of this it's still dangerous. But this could be used if your forked process is going to become a daemon and parent is no longer needed and will be immediately terminated.
• The third case is when both child and parent call _exit.

  int main(int argc, char **argv)
  {
      if (fork() == 0)
      {   
          cout << "child, " << getpid() << endl;
          _exit(0);
      }   
      else
      {   
          cout << "parent, " << getpid() << endl;
          sleep(1);
          wait(NULL);
          _exit(0);
      }   
              
      return 0;
  }

  The output might be

  $./exit 
  A(), 17221
  parent, 17221
  child, 17222

  Here constructor was called once but no calls of destructor. This could be fine. But if you are doing something significant in destructor such as closing connections, deleting temporary files, etc. you may run into the trouble.
• An the last one, that should be correct, is when the child calls _exit and the parent calls exit.

  int main(int argc, char **argv)
  {
      if (fork() == 0)
      {   
          cout << "child, " << getpid() << endl;
          _exit(0);
      }   
      else
      {   
          cout << "parent, " << getpid() << endl;
          sleep(1);
          wait(NULL);
          exit(0);
      }   
              
      return 0;
  }

  The output should be

  $./exit 
  A(), 17234
  child, 17235
  parent, 17234
  ~A(), 17234

  The parent process has created the object and it has destroyed it. The best behavior you can expect.

The behavior changes a bit if you are using vfork instead of fork. The behavior differ with

int main(int argc, char **argv)
{

    if (vfork() == 0)
    {   
        cout << "child, " << getpid() << endl;
        exit(0);
    }   
    else
    {   
        cout << "parent, " << getpid() << endl;
        sleep(1);
        wait(NULL);
        exit(0);
    }   
            
    return 0;
}

The output might look like

$./exit 
A(), 17321
child, 17322
~A(), 17322
parent, 17321

This is similar to the code where the child called exit and the parent called _exit. This is the expected behavior of vfork. With vfork the new process is being created without copying the page tables of the parent process, the parent and child use the same memory pages. The usage of vfork is dangerous first of all. And in the modern systems that use COW technique for forked processes you may not feel the performance reduction.

You can't be 100% sure that you are not using c++ code in your project that could define global variables somewhere. It could be third-party library in your project that uses static or global objects(the singletons, depending on the implementation, could be affected also). So the best practice is to use _exit to return from the child process and use exit(or return from main) to exit from the parent.

asm: overwriting return point of the function/stack overflow

Stack overflow is a common attack in programming world.
To understand how it could be done we should be aware about the function's stack and how the function is being executed and how it passes the execution of the code in the parent function after its call.
The stack of the function, at least in *nix, should look like

|function parameters| <--top of the stack(higher memory addresses)
|---return  point---| <--%esp
|--local variables--|
|-------------------| <--bottom of the stack(lower memory addresses)

Let's examine simple program written in asm. It has a function pc that puts giver character onto stdout and adds '\n'. In main this function is called with argument which value is '*'.

 1 .text
 2 
 3 pc:
 4     pushl %ebp
 5     movl %esp, %ebp
 6     
 7     subl $4, %esp /*4 bytes for local variables*/
 8     
 9     pushl 8(%ebp)/*get value of the function parameter*/
10     call putchar
11     pushl $0x0a /*new line*/
12     call putchar
13     addl $8, %esp/*allign stack*/
14     
15     movl %ebp, %esp
16     popl %ebp
17     ret
18     
19 
20 .global main
21 
22 main:
23     pushl $0x0000002a /*character '*'*/
24     call pc
25     addl $4, %esp/*allign stack*/
26     
27     movl $1, %eax
28     movl $0, %ebx
29     int $0x80/*exit(0)*/

I set a breakpoint on line 4 in gdb and got the information about the registers

(gdb) i r
eax            0xbfae0a34 -1079113164
ecx            0x312f6668 825189992
edx            0x1 1
ebx            0xb7fa4ff4 -1208332300
esp            0xbfae09a4 0xbfae09a4
ebp            0xbfae0a08 0xbfae0a08
esi            0xb7fe2ca0 -1208079200
edi            0x0 0
eip            0x8048384 0x8048384 <pc>

Address of %esp is 0xbfae09a4, so here is the top of the stack of our function pc.
In *nix world stack of the process grows from the higher memory addresses to the lower ones. So to get function parameter we should add 4 bytes to %esp(the size of return point is 4 bytes)[Note, on line 9 I pushed the address of %ebp + 8 because after 'pushl %ebp' value of %esp increased with 4 bytes.]

(gdb) x/c 0xbfae09a4 + 4
0xbfae09a8: 42 '*'

Yes, here we have '*' _because_ we indeed pushed it onto the stack on line 23. In %esp we can find the address of the return point

(gdb) x/x 0xbfae09a4 
0xbfae09a4: 0x080483a7

0x080483a7 is the address of the next instruction after the call of pc in main. Let's check.
Going through instruction in gdb I got out from pc

(gdb) n
pc () at fcall.s:17
17  ret
(gdb) n
main () at fcall.s:25
25  addl $4, %esp/*allign stack*/
(gdb) i r
eax            0xa 10
ecx            0xffffffff -1
edx            0xb7fa60b0 -1208328016
ebx            0xb7fa4ff4 -1208332300
esp            0xbfae09a8 0xbfae09a8
ebp            0xbfae0a08 0xbfae0a08
esi            0xb7fe2ca0 -1208079200
edi            0x0 0
eip            0x80483a7 0x80483a7 <main+7>

You can see that value of %eip is 0x80483a7, so we were right. To make a program run any other code rather than return to the parent function the address of the return point has to be overwritten.
The following code attempts to do so.
It has function evil which address will be written to the return point of the function pc. Function evil writes '%\n' on the output and calls exit syscall with exit code 1.

 1 .text
 2 
 3 evil:
 4     pushl %ebp
 5     movl %esp, %ebp
 6 
 7     pushl $0x00000025 /*character '%'*/
 8     call putchar
 9     pushl $0x0a /*new line*/
10     call putchar
11 
12     movl $1, %eax
13     movl $1, %ebx
14     int $0x80/*exit(1)*/
15     
16 pc: 
17     pushl %ebp
18     movl %esp, %ebp
19     
20     subl $4, %esp /*4 bytes for local variables*/
21 
22     pushl 8(%ebp)
23     call putchar
24     pushl $0x0a /*new line*/
25     call putchar
26     addl $8, %esp/*allign stack*/
27     
28     movl %ebp, %esp
29     popl %ebp
30 
31     movl $evil, (%esp)
32 
33     ret
34 
35 
36 .global main
37 
38 main:
39     pushl $0x0000002a /*character '*'*/
40     call pc
41     addl $4, %esp/*allign stack*/
42     
43     movl $1, %eax
44     movl $0, %ebx
45     int $0x80/*exit(0)*/

The result of the exucution of this program should be

$gcc fcall.s -o fcall -g
$./fcall 
*
%
$echo $?
1

c++: multidimensional arrays in the (dynamic) memory

I know some solutions how to store multidimensional arrays in the (dynamic) memory.
I'd like to share this knowledge because I noticed that not all of the developers understand what is going on in this field.
Let's look at different ways how to create 2-dimension array of objects of the class A which code is below

class A
{
    public:
        void * operator new(size_t size)
        {
            void *p = malloc(size);
            cout << "new, size: " << size << "\n";
            return p;
        }

        void * operator new[](size_t size)
        {
            void *p = malloc(size);
            cout << "new[], size: " << size << "\n";
            return p;
        }

        A() 
        {   
            cout << "A()\n";
            id = ++counter;
        }

        ~A()
        {   
            cout << "~A()\n";
        }   

        void call()
        {   
            cout << "id #" << id << ", " << counter << " times constructor of A was called\n";
        }

        static int counter;
        int id; 
};

int A::counter = 0;

I added some code for tracing operator new, constructor and destructor calls.
Each time the constructor is called value of class static variable counter is incremented by 1 and its new value is assigned to class member variable id.

• The first method and the simplest.
  Simply to allocate 2x2 array of A on the stack.

  cout << "size of A: " << sizeof(A) << "\n";
  A z[2][2];
  z[1][1].call();
  (z[1]+1)->call();
  (*z+3)->call();

  This piece of code produces

  size of A: 4
  A()
  A()
  A()
  A()
  id #4, 4 times constructor of A was called
  id #4, 4 times constructor of A was called
  id #4, 4 times constructor of A was called
  ~A()
  ~A()
  ~A()
  ~A()

  4 times constructor was called, 4 times destructor, no calls of operator new.
• The second, a bit more complex.
  Allocate memory for 2x2 array of A in the heap.

  cout << "size of A: " << sizeof(A) << "\n";
  A (*z)[2] = new A[2][2];
  z[1][1].call();
  (z[1]+1)->call();
  (*z+3)->call();
  delete [] z;

  The output should be

  size of A: 4
  new[], size: 20
  A()
  A()
  A()
  A()
  id #4, 4 times constructor of A was called
  id #4, 4 times constructor of A was called
  id #4, 4 times constructor of A was called
  ~A()
  ~A()
  ~A()
  ~A()
  

  4 times constructor was called, 4 times destructor, 1 call of operator new[] to allocate memory for all 4 objects.
• The next method is used to allocate memory in the heap for one-dimension array of size 2 of pointers to A. Then allocate memory for one-dimension 'sub-arrays'.

  cout << "size of A: " << sizeof(A) << "\n";
  A **z = new A*[2];
  z[0] = new A[2];
  z[1] = new A[2];
  
  z[1][1].call();
  (z[1]+1)->call();
  (*z+3)->call();
  
  delete [] z[0];
  delete [] z[1];
  delete [] z;

  size of A: 4
  new[], size: 12
  A()
  A()
  new[], size: 12
  A()
  A()
  id #4, 4 times constructor of A was called
  id #4, 4 times constructor of A was called
  id #4, 4 times constructor of A was called
  ~A()
  ~A()
  ~A()
  ~A()

  2 times constructor was called after each call to operator new[] to allocate memory for 2 objects, 4 times destructor was called
• This method is tricky a little bit. We allocate one-dimension array of size 4. Using pointer arithmetics we can simulate two-dimension array.

  cout << "size of A: " << sizeof(A) << "\n";
  A *z = new A[2*2];
  z[2+1].call();
  (z+3)->call();
  delete [] z;

  size of A: 4
  new[], size: 20
  A()
  A()
  A()
  A()
  id #4, 4 times constructor of A was called
  id #4, 4 times constructor of A was called
  ~A()
  ~A()
  ~A()
  ~A()
  

4 times constructor was called, 4 times destructor, 1 call of operator new[] to allocate memory for all 4 objects.
• This one is a combination of storing 2x2 array in the heap and in the stack. At first one-dimension array of pointers to A is put onto the stack and later memory from heap is used to allocate one-dimension 'sub-arrays'.

  cout << "size of A: " << sizeof(A) << "\n";
  A *z[2];
  z[0] = new A[2];
  z[1] = new A[2];
  
  z[1][1].call();
  (z[1]+1)->call();
  (*z+3)->call();
  
  delete [] z[0];
  delete [] z[1];

  size of A: 4
  new[], size: 12
  A()
  A()
  new[], size: 12
  A()
  A()
  id #4, 4 times constructor of A was called
  id #4, 4 times constructor of A was called
  id #4, 4 times constructor of A was called
  ~A()
  ~A()
  ~A()
  ~A()
  

  2 times constructor was called after each call to operator new[] to allocate memory for 2 objects, 4 times destructor was called

All methods have their '+'s and '-'s. One can take more time but require less memory and the other one can take more memory but could be executed faster. That depends how many calls have been done to allocate memory, where memory was taken to allocate an array, etc. Also you should remember c++ restriction for arrays on the stack that their size must be known during the compile time. The dark side of memory from the heap is that it should be explicitly released when it become unused. Some of them are more expressive for understanding some of them not.
This is upon you.

autoconf: square brackets in AS_HELP_STRING

With autoconf(2.63) if I wanted to use square brackets for AS_HELP_STRING I didn't succeed. I have been trying to add extra [] around the helpstring according to manual:

Each time there can be a macro expansion, there is a quotation expansion, i.e., one level of quotes is stripped:

int tab[10];
     =>int tab10;
     [int tab[10];]
     =>int tab[10];

The solution I've found in configure.ac of qore programming language.
The quadrigraphs are used there.
'@<:@' for '[' and '@:>@' for ']' could be used in autoconf input file.
So now I have nice output of ./configure --help in my project:

....
  --with-mysql[=DIR]      use mysql
  --with-fcgi[=DIR]       use fast CGI
  --with-pcre[=DIR]       use pcre
....

The code in configure.in looks like:

....
AS_HELP_STRING([--with-sqlite@<:@=DIR@:>@], [use sqlite])...
....

emacs: the dark side of the force

Recently I've decided to try the dark side of the force - emacs.
I'm Vim user for a long time. Several times I wanted to try emacs but didn't have a good chance.
Now I'm working on project with huge amount of sources and I decided to try emacs for it.
It works! ;)

Playing with emacs I've found out that it's not so complex as some people say.

The thing to which I couldn't get used to for some time is that I don't have to press ESC to switch to the command mode, press i(INS) to switch to editor mode and so on.

I haven't found some Vim features(as visual mode) but I believe that just don't know how to make them work.

The main difference is that there is no distinct differences between editor mode and command mode. You are allowed to run commands while you are editing the text.

All commands(or better to say most of them) begin with control- or meta- character. control is usually Ctrl on your keyboard and meta is Alt.

For guys who want to try emacs here is the migration guide on vim-to-emacs commands.
The table of equivalence of vim and emacs commands.

split horizontalsplit vertical

VIM	EMACS	Description
:qa/:wqa/:xa/:qa!	C-x C-c	exit(emacs prompts whether to save buffers or not)
h	C-b	left
l	C-f	right
b/B	M-b	word backward
w/W	M-f	word forward
j	C-n	down
k	C-p	up
0	C-a	beginning of the line
$	C-e	end of the line
gg/1G	C-<	beginning of the buffer
G	C->	end of the buffer
x	C-d	delete under cursor
D	C-k	delete from cursor to EOL
dd	C-k C-k	delete line
dw/dW	M-d	delete word
db/dB	M-{BACKSPACE}	delete word backwards
:set ignorecase {ENTER} /	C-s {needle in lower case}	icase search forward
:set ignorecase {ENTER} ?	C-r {needle in lower case}	icase search backward
/	C-s	search forward
?	C-r	search backward
:set ignorecase {ENTER} /	M-C-s {regexp in lower case}	icase regexp search forward
:set ignorecase {ENTER} ?	M-C-r {regexp in lower case}	icase regexp search backward
:%s/{needle}/{replacement}/gc	M-% {needle} {ENTER} {replacement} {ENTER}	query replace
/	M-C-s	regexp search forward
?	M-C-r	regexp search backward
u	C-_/C-x u	undo
C-R	C-_/C-x u	redo(it's tricky for emacs*)
ESC	C-g	quit the running/entered command(switch to command mode in Vim)
:e file	C-x C-f	open file
:set ro	C-x C-q	set file as read-only
:w	C-x C-s	save buffer
:w file	C-x C-w file	save buffer as ...
:wa	C-x s	save all buffers
:buffers	C-x C-b	show buffers
:b [name]	C-x b [name]	switch to another buffer
:q/:q!/:wq/:x	C-x k	close buffer
C-w n/:split	C-x 2
C-w v/:vsplit	C-x 3
C-w C-w	C-x o	switch to another window
:q	C-x 0	close window
C-w o	C-x 1	close other windows
:! {cmd}	M-!	run shell command
m{a-zA-Z}	C-@/C-space	set mark
	C-x C-x	exchange mark and position
{visual}y	M-w	copy region**
{visual}d	C-w	delete region**
p	C-y	paste
C-V {key}	C-q {key}	insert special char, e.g. ^M:
{visual}SHIFT->	C-x TAB	indent region
C-]	M-.	find tag
C-t	M-*	return to previous location
:e!	M-x revert-buffer	reload buffer from disk

*To redo changes you have undone, type `C-f' or any other command that will harmlessly break the
sequence of undoing, then type more undo commands
**region is from current position to the mark

Other useful emacs commands:

M-g	go to line
C-x i	insert file
C-x h	mark whole buffer
C-x C-t	switch two lines
M-C-a	beginning of the function
M-C-e	end of the function
M-a	beginning of the statement
M-e	end of the statement
M-C-h	mark the function
M-/	autocompletion
M-C-\	indent region
C-c C-q	indent the whole function according to indention style
C-c C-c	comment out marked area
M-x uncomment-region	uncomment marked area
M-,	jumps to the next occurence for tags-search
M-;	insert comment in code
C-x w h	highlight the text by regexp
C-x w r	disable highlighting the text by regexp

To run emacs without X add -nw command line argument.

To run multiply commands 'C-u {number} {command}' or 'M-{digit} {command}'.

emacs has bookmarks that are close to Vim marks:

C-x r m	set a bookmark at current cursor position
C-x r b	jump to bookmark
C-x r l	list bookmarks
M-x bookmark-write	write all bookmarks in given file
M-x bookmark-load	load bookmarks from given file

My ~/.emacs looks like:

(setq load-path (cons "~/.emacs.d" load-path))

(auto-compression-mode t) ; uncompress files before displaying them

(global-font-lock-mode t) ; use colors to highlight commands, etc.
(setq font-lock-maximum-decoration t)
(custom-set-faces)
(transient-mark-mode t) ; highlight the region whenever it is active
(show-paren-mode t) ; highlight parent brace
(global-hi-lock-mode t) ; highlight region by regexp

(column-number-mode t) ; column-number in the mode line

(setq make-backup-files nil)

(setq scroll-conservatively most-positive-fixnum) ; scroll only one line when I move past the bottom of the screen

(add-hook 'text-mode-hook 'turn-on-auto-fill) ; break lines at space when they are too long

(fset 'yes-or-no-p 'y-or-n-p) ; make the y or n suffice for a yes or no question

(setq comment-style 'indent)

(global-set-key (kbd "C-x C-b") 'buffer-menu) ; buffers menu in the same window

(global-set-key (kbd "C-x 3") 'split-window-horizontally-other) ; open new window horisontally and switch to it
(defun split-window-horizontally-other ()
        (interactive)
        (split-window-horizontally)
        (other-window 1)
)

(global-set-key (kbd "C-x 2") 'split-window-vertically-other) ; open new window vertically and switch to it
(defun split-window-vertically-other ()
 (interactive)
 (split-window-vertically)
 (other-window 1)
)

(global-set-key (kbd "C-c c") 'comment-region) ; comment code block
(global-set-key (kbd "C-c u") 'uncomment-region) ; uncomment code block

(global-set-key (kbd "C-x TAB") 'tab-indent-region) ; indent region
(global-set-key (kbd "C-x <backtab>") 'unindent-region) ; unindent region
(defun tab-indent-region ()
    (interactive)
 (setq fill-prefix "\t")
    (indent-region (region-beginning) (region-end) 4)
)
(defun unindent-region ()
    (interactive)
    (indent-region (region-beginning) (region-end) -1)
)

(global-set-key (kbd "TAB") 'self-insert-command)
(global-set-key (kbd "RET") 'newline-and-indent)

(setq key-translation-map (make-sparse-keymap))
(define-key key-translation-map "\177" (kbd "C-="))
(define-key key-translation-map (kbd "C-=") "\177")
(global-set-key "\177" 'delete-backward-char)
(global-set-key (kbd "C-=") 'delete-backward-char)

(setq indent-tabs-mode t)
(setq tab-always-indent t)
(setq default-tab-width 4)

(setq inhibit-startup-message t) ; do not show startup message

(iswitchb-mode t)
(desktop-save-mode t)

(display-time)

Happy emacsing!

perl: manipulations with standart output stream

Builtin functions print and write put data to stdout if the filehandle is omitted.
This is really handy.
But since you want to write to some other stream each time you have to specify filehandle for them.
It's possible to point STDOUT to some other filehandle by reassigning it

open $nfh, '>test';
$ofh = *STDOUT;
*STDOUT = *$nfh;

print "test";

*STDOUT = $ofh;
close $nfh;

or by using select function

open $nfh, '>test';
$ofh = select $nfh;

print "test";

select $ofh;
close $nfh;

and still use print and write w/o specifying the filehandle. The second method with select looks better for me.
If you use a lot of ways for output the LIFO(Last-In, First-Out) of filehandles can be used to implement an easy way to walk through them like pushd/popd in bash

#!/usr/bin/perl
@fh = ();

open my $nfh, '>test-0';
push @fh, select $nfh;

print "test\n";

open my $nfh, '>test-1';
push @fh, select $nfh;

print "test\n";

close select pop @fh;
print "test\n";
close select pop @fh;

print "test\n";

The result of executing this script

$./test.pl 
test
$cat test-*
test
test
test

Note, I used my with filehandle in open to give it an undefined scalar variable. Otherwise open will associate the stream with this variable. And the old stream will be lost. The following code does the same work w/o using my expression

#!/usr/bin/perl
@fh = ();

open $nfh, '>test-0';
push @fh, select $nfh;

print "test\n";

$nfh = undef;
open $nfh, '>test-1';
push @fh, select $nfh;

print "test\n";

close select pop @fh;
print "test\n";
close select pop @fh;

print "test\n";

The result of executing this script

$./test.pl 
test
$cat test-*
test
test
test

intel VT: how to enable

My Intel(R) Core(TM)2 Duo CPU supports intel VT but it's disabled by default in BIOS.

Currently I'm hardly testing libdodo in different environments. As I'm running IA32 kernel I was testing it in x86 environments. Lately I decided to test it in x86_64 with VMWare. I went to BIOS, turned on VT support, rebooted ... and VMWare player told me that my platform supports VT but it's disabled. What the heck? I checked that the option is enabled in BIOS several times but still couldn't run x86_64 guest OS.

Googling didn't help. Running guest OS under qemu x86_64 simulation was the last option. It's extremely slow.

When I almost gave up I reached a very interesting article.
The author is telling that after the VT option was enabled in BIOS, the processor must be plugged off from the electricity circuit.
I turned off my laptop removed power supply and battery, waited for a few seconds, plugged the stuff back, booted and started VMWare with x86_64 guest. BINGO.

Now I'm able to run x86_64 guests on x86 host.

linux: zombies

New processes are being created with fork system call. After the fork is completed there are two processes available - parent and child.

Zombie is a process that was finished before the parent and the parent hadn't made any attempts to reap it.

When the child process was stopped or terminated the kernel still holds some minimal information about it in case the parent process will attempt to get it. This information is a task_struct where pid, exit code, resource usage information, etc. could be found. All other resources(memory, file descriptors, etc.) should be released. For details you can dig into the code of the do_exit function in kernel/exit.c in the linux kernel sources.

The parent should be notified about the child's death with SIGCHLD signal.

When the parent receives SIGCHLD it can get the information about the child by calling wait/waitpid/... system call. In the interval between the child terminating and the parent calling wait, the child is said to be a zombie. Even it's can't be in running or idle states it still takes place in the process table.
As soon as parent process receives SIGCHLD signal and it's ready to get information about the dead child this information is passed to it and all the information about the child is being removed from the kernel. In wait_task_zombie function(kernel/exit.c) you should find the details.

In fact the memory that is hold by a zombie is really small but it still in the process table and processed by the scheduler and also as the process table has a fixed number of entries it is possible for the system to run out of them.

When the parent terminates without waiting for the child zombie process is adopted by 'init' process which calls wait to clean up after it.

Let's look at the common zombie and its code.

#include <unistd.h>
#include <stdio.h>

int main(int argc, char **argv)
{
    if (fork() == 0)
    {   
        printf("%d\n", getpid());
        fflush(stdout);
        _exit(0);
    }   
    else
    {   
        printf("%d\n", getpid());
        fflush(stdout);
        while (1) 
            sleep(10);
    }   
    
    return 0;
}

The output should be something like

$./zombie 
4090
4091

Grepping ps's output I got

$ps aux | grep -E "(4090|4091)"
niam      4090  0.0  0.0   1496   340 pts/2    S+   12:24   0:00 ./zombie
niam      4091  0.0  0.0      0     0 pts/2    Z+   12:24   0:00 [zombie] 

You can see that child process became a zombie.

Knowing that zombies if are not a complete evil but are very close to it, there existence should be prevented.

There are some possibilities to do that.

First of all if you want to care why the child was finished you should call wait. This is an only way I know to do that.

I know two modes of wait: blocking and non-blocking. Both methods are listed below.

• Blocking method that will suspend parent until the SIGCHLD is received.

  #include <unistd.h>
  #include <stdio.h>
  #include <signal.h>
  
  int main(int argc, char **argv)
  {
      if (fork() == 0)
      {   
          printf("%d\n", getpid());
          fflush(stdout);
          _exit(0);
      }   
      else
      {   
          int status;
          wait(&status);
          printf("%d\n", getpid());
          fflush(stdout);
          while (1) 
              sleep(10);
      }   
      
      return 0;
  }

  And the resulting output for this code was

  $./zombie 
  4949
  4950
  
  $ps aux | grep -E '(4949|4950)'
  niam      4949  0.0  0.0   1496   340 pts/2    S+   13:12   0:00 ./zombie

• Non-blocking which won't put the parent into the sleep state but requires multiply calls of waitpid.

  #include <unistd.h>
  #include <stdio.h>
  #include <signal.h>
  #include <sys/wait.h>
  
  int main(int argc, char **argv)
  {
      if (fork() == 0)
      {   
          printf("%d\n", getpid());
          fflush(stdout);
          _exit(0);
      }   
      else
      {   
          printf("%d\n", getpid());
          fflush(stdout);
          int status;
          while (1) 
          {
              waitpid(-1, &status, WNOHANG);
              sleep(10);
          }
      }   
      
      return 0;
  }

  The output was

  $./zombie 
  4932
  4931
  
  $ps aux | grep -E '(4931|4932)'
  niam      4931  0.0  0.0   1496   336 pts/2    S+   13:07   0:00 ./zombie

Another approach is to disregard child's exit status and detach it.

• Redefine SIGCHLD signal handler to specify SA_NOCLDSTOP flag for it.

  #include <unistd.h>
  #include <stdio.h>
  #include <signal.h>
  
  int main(int argc, char **argv)
  {
      struct sigaction sa;
      sigaction(SIGCHLD, NULL, &sa);
      sa.sa_flags |= SA_NOCLDWAIT;//(since POSIX.1-2001 and Linux 2.6 and later)
      sigaction(SIGCHLD, &sa, NULL);
  
      if (fork() == 0)
      {   
          printf("%d\n", getpid());
          fflush(stdout);
          _exit(0);
      }   
      else
      {   
          printf("%d\n", getpid());
          fflush(stdout);
          while (1) 
              sleep(10);
      }   
      
      return 0;
  }

  The output should be something like

  $./zombie 
  4416
  4417
  
  $ps aux | grep -E '(4416|4417)'
  niam      4416  0.0  0.0   1496   340 pts/2    S+   12:41   0:00 ./zombie

• Set SIGCHLD signal handler to SIG_IGN(ignore this signal).

  #include <unistd.h>
  #include <stdio.h>
  #include <signal.h>
  
  int main(int argc, char **argv)
  {
      struct sigaction sa;
      sigaction(SIGCHLD, NULL, &sa);
      sa.sa_handler = SIG_IGN;
      sigaction(SIGCHLD, &sa, NULL);
  
      if (fork() == 0)
      {   
          printf("%d\n", getpid());
          fflush(stdout);
          _exit(0);
      }   
      else
      {   
          printf("%d\n", getpid());
          fflush(stdout);
          while (1) 
              sleep(10);
      }   
      
      return 0;
  }

  This code should produce the following output.

  $./zombie 
  4458
  4459
  
  $ps aux | grep -E '(4459|4458)'
  niam      4458  0.0  0.0   1496   340 pts/2    S+   12:45   0:00 ./zombie

  Note that POSIX.1-1990 disallowed setting the action for SIGCHLD to SIG_IGN. POSIX.1-2001 allows this possibility, so that ignoring SIGCHLD can be used to prevent the creation of zombies

According to the linux-2.6.27 sources setting signal handler to SIG_IGN might give a small benefit in performance. Here is a piece of code from kernel/exit.c

static int ignoring_children(struct task_struct *parent)     
{                               
    int ret;                                                        
    struct sighand_struct *psig = parent->sighand;     
    unsigned long flags;        
    spin_lock_irqsave(&psig->siglock, flags);            
    ret = (psig->action[SIGCHLD-1].sa.sa_handler == SIG_IGN ||     
           (psig->action[SIGCHLD-1].sa.sa_flags & SA_NOCLDWAIT));     
    spin_unlock_irqrestore(&psig->siglock, flags);     
    return ret;                
}

The kernel checks signal handler first.

There is other problem when the software wasn't developed by you but it produces zombies during the execution. There is a trick with gdb to kill process' zombies. You can attach to the parent process and manually call wait.

$./zombie 
4980
4981

$ps aux | grep -E '(4980|4981)'
niam      4980  0.0  0.0   1496   336 pts/2    S+   13:19   0:00 ./zombie
niam      4981  0.0  0.0      0     0 pts/2    Z+   13:19   0:00 [zombie] 

$gdb -p 4980
....
(gdb) call wait()
$1 = 4981

$ps aux | grep -E '(4980|4981)'
niam      4980  0.0  0.0   1496   336 pts/2    S+   13:19   0:00 ./zombie

FreeBSD: sem_open bug

Recently I've been testing libdodo on FreeBSD 7.0
Any time sem_open was called I received 'bad system call' and abort signal from ksem_open routine.

sem_open is buggy in FreeBSD, man 3 sem_open:

BUGS
     This implementation places strict requirements on the value of name: it
     must begin with a slash (`/'), contain no other slash characters, and be
     less than 14 characters in length not including the terminating null
     character.

Anyway I was giving sem_open 14 bytes long key with leading '/' and it continued to fail.

Program received signal SIGSYS, Bad system call.
[Switching to Thread 0x28f01100 (LWP 100056)]
0x2891c84b in ksem_open () from /lib/libc.so.7
(gdb) bt
#0  0x2891c84b in ksem_open () from /lib/libc.so.7
#1  0x2891209c in sem_open () from /lib/libc.so.7
#2  0x28767386 in single (this=0x804b520, value=1, a_key=@0x804b4dc) at src/pcSyncProcessDataSingle.cc:58
#3  0x0804969c in __static_initialization_and_destruction_0 (__initialize_p=Variable "__initialize_p" is not available.
) at test.cc:24
#4  0x0804aaf5 in __do_global_ctors_aux ()
#5  0x080491ed in _init ()
#6  0x00000000 in ?? ()
#7  0x00000000 in ?? ()
#8  0xbfbfecbc in ?? ()
#9  0x080495a6 in _start ()
#10 0x00000001 in ?? ()
(gdb) up
#1  0x2891209c in sem_open () from /lib/libc.so.7
(gdb) 
#2  0x28767386 in single (this=0x804b520, value=1, a_key=@0x804b4dc) at src/pcSyncProcessDataSingle.cc:58
58  semaphore = sem_open(key.c_str(), O_CREAT, S_IWUSR, value);
(gdb) p key
$1 = {static npos = 4294967295, _M_dataplus = {<std::allocator<char>> = {<__gnu_cxx::new_allocator<char>> = {<No data fields>}, <No data fields>}, _M_p = 0x28f4a24c "/c5b80cc1e0"}}
(gdb) p value
$2 = 1

The bug is somewhere in the kernel. I should look for another implementation of semaphores in FreeBSD.

gmake: command echoing

By default gmake prints each command line before it is executed.
I knew the method to suppress this output but because I haven't bothered about it for some time I actually forgot how to do that.
Recently I wanted to make build output of libdodo pretty and tried to recall how to tell gmake not to print command lines.
gmake manual has a chapter that describes what should be done to achieve this.
'@' sign before the command tells gmake to suppress the command line echoing:

@echo "-- Compiling: $^"
@$(CXX) $(DEFINES) $(CPPFLAGS) $(CFLAGS) -fPIC -c $^

Long g++ command line won't appear on the output, instead you'll see

-- Compiling: 'the source file'.cc