Meditation, The Art of Exploitation

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

noreply@blogger.com (Fei Liu) — Mon, 07 Jul 2008 01:22:00 +0000

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

noreply@blogger.com (Fei Liu) — Wed, 14 May 2008 21:43:00 +0000

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

noreply@blogger.com (Fei Liu) — Tue, 13 May 2008 20:19:00 +0000

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

noreply@blogger.com (Fei Liu) — Mon, 07 Apr 2008 16:57:00 +0000

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

noreply@blogger.com (Fei Liu) — Tue, 01 Apr 2008 14:22:00 +0000

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

noreply@blogger.com (Fei Liu) — Mon, 10 Mar 2008 23:18:00 +0000

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

noreply@blogger.com (Fei Liu) — Sat, 08 Mar 2008 21:20:00 +0000

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

noreply@blogger.com (Fei Liu) — Sat, 08 Mar 2008 20:22:00 +0000

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

noreply@blogger.com (Fei Liu) — Fri, 29 Feb 2008 01:37:00 +0000

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

noreply@blogger.com (Fei Liu) — Tue, 19 Feb 2008 22:45:00 +0000

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

noreply@blogger.com (Fei Liu) — Tue, 19 Feb 2008 22:43:00 +0000

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

noreply@blogger.com (Fei Liu) — Tue, 19 Feb 2008 03:33:00 +0000

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

noreply@blogger.com (Fei Liu) — Thu, 14 Feb 2008 02:45:00 +0000

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

noreply@blogger.com (Fei Liu) — Wed, 13 Feb 2008 17:40:00 +0000

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

noreply@blogger.com (Fei Liu) — Mon, 11 Feb 2008 15:30:00 +0000

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)

noreply@blogger.com (Fei Liu) — Sat, 09 Feb 2008 01:17:00 +0000

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

noreply@blogger.com (Fei Liu) — Thu, 07 Feb 2008 19:10:00 +0000

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

noreply@blogger.com (Fei Liu) — Fri, 01 Feb 2008 16:51:00 +0000

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

noreply@blogger.com (Fei Liu) — Thu, 31 Jan 2008 17:27:00 +0000

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

noreply@blogger.com (Fei Liu) — Tue, 29 Jan 2008 14:55:00 +0000

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

noreply@blogger.com (Fei Liu) — Tue, 22 Jan 2008 15:14:00 +0000

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

noreply@blogger.com (Fei Liu) — Fri, 18 Jan 2008 15:42:00 +0000

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

noreply@blogger.com (Fei Liu) — Thu, 10 Jan 2008 18:34:00 +0000

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

noreply@blogger.com (Fei Liu) — Thu, 03 Jan 2008 18:51:00 +0000

GNU tool chain

noreply@blogger.com (Fei Liu) — Thu, 03 Jan 2008 17:16:00 +0000

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)