Minix 3 System event framework (SEF)

In this post i will give an introduction into the minix 3 OS System Event Framework (SEF), and its usage and the benefits behind it. If you are not familiar with the minix 3 OS you may need to have a look at this post.

Agenda

• Introduction
• Event types
• Call-backs
• References

Introduction

SEF is a component of the system library that deals with system events in a centralized and convenient way. In MINIX 3 every driver and system server has to deal with the System Event Framework (SEF) which handles live up-dates and failure recovery.

Every system service (server or device driver) must call sef_startup() at startup time to handle initialization and sef_receive() when receiving a message. The developer can register callbacks to provide handlers for each particular type of event. When no callback is registered for one particular event, the default behavior is assumed. The developer can also reuse some predefined callback implementations provided by SEF for each particular event type.

Event types

Initialization

Triggered by initialization messages sent by the Reincarnation Server when a service is started. The API and the predefined callback implementations are declared in <minix/sef.h> and defined in lib/syslib/sef_init.c.

Ping

Triggered by keep-a-live messages sent by the Reincarnation Server periodically to check the status of a system service. The API and the predefined callback implementations are declared in <minix/sef.h> and defined in lib/libsys/sef_ping.c.

Live update

Triggered by live update messages sent by the Reincarnation Server when an update is available for a particular system service. The API and the predefined callback implementations are declared in <minix/sef.h> and defined in lib/libsys/sef_liveupdate.c.

Signal (Not included in the minix wiki, i got it from the code)

Triggered to intercept process signals (e.g., SIGTERM). The API and the predefined callback implementations are declared in <minix/sef.h> and defined in lib/libsys/sef_signal.c.

Callbacks (This section is totally extracted (by me) from the component code)

Initialization callbacks

void sef_setcb_init_fresh(sef_cb_init_t cb)


Set the start up init callback, if cb is null then the default init callback is assumed.

void sef_setcb_init_lu(sef_cb_init_t cb)

Set the live update init callback, if cb is null then the default live update init callback is assumed.

void sef_setcb_init_restart(sef_cb_init_t cb)

Set the restart init callback, if cb is null then the default restart init callback is assumed.

sef_setcb_init_response(sef_cb_init_response_t cb)

Set the init response callback for example (notify the Reincarnation Server that we completed init)

Ping callbacks

void sef_setcb_ping_reply(sef_cb_ping_reply_t cb)

Set the ping reply callback, two default implementations introduced either do nothing (sef_cb_ping_reply_null), or ack (sef_cb_ping_reply_pong).

Live update callbacks

void sef_setcb_lu_prepare(sef_cb_lu_prepare_t cb)

Set the live update prepare callback, if cb is null default callback is assumed.

void sef_setcb_lu_state_isvalid(sef_cb_lu_state_isvalid_t cb)

Set the live update is valid state callback, when a live update encountered the RS must assure that the driver/server is in a valid state for live update.

void sef_setcb_lu_state_changed(sef_cb_lu_state_changed_t cb)

Set the live update changed state callback.

void sef_setcb_lu_state_dump(sef_cb_lu_state_dump_t cb)

Set the live update state dump callback -> I think its for debugging information or something like that.

void sef_setcb_lu_state_save(sef_cb_lu_state_save_t cb)

Set the live update stat save callback.

void sef_setcb_lu_response(sef_cb_lu_response_t cb)

Set the live update response callback, for example telling the RS that we are up and running.

Signal callbacks

void sef_setcb_signal_handler(sef_cb_signal_handler_t cb) 

Set the signal handler callback. Default implementation is either to ignore all signals, or handling the term signal (Terminate in this case), Also it provide a case to handle posix signals.

void sef_setcb_signal_manager(sef_cb_signal_manager_t cb)

Still can't know its purpose till now.

References

• Minix wiki page
• Minix git repository

Feed backs are more than welcomed.

Problem solving techniques (Example problems) (Cont.)

In this post i will show how to use the divide and conquer technique to solve problems, you may need to check previous post.

Problem 3 (Binary search)

Given a list of sorted integer numbers and an integer, find the occurrence of this number into the list or -1 if it doesn't exist.

Discussion 

We can linear search for this list O(N), but with the fact that the list is sorted we can at each time get the middle element of the array and minimize the search space into either the left half part (if the searched element is less than the mid element), or the right half (if the searched element is greater than the mid element). O(lg N) where N is number of elements.

Code

int binary_search(vector<int> vec, int src, int dest, int elem) {
    if(dest < src) return -1;
    int mid = (src+dest+1)/2;
  
    if(elem == vec[mid]) return mid;
    else if(elem < vec[mid]) return binary_search(vec, src, mid-1, elem);
    else return binary_search(vec, mid+1, dest, elem);
}

Problem 4 (LargestSubsequence)
Topcoder SRM 518 (DIV 1 level 1, DIV 2 level 2)

For Strings x and y, we say y is a subsequence of x if y can be obtained from x by erasing some (possibly all or none) of the letters in x. For example, "tpcdr" is a subsequence of "topcoder", while "rt" is not.

Given a String s, return the lexicographically largest subsequence of s.

Discussion

For example if the passed string is "test" then all subsequences listed in lexicographical order are "" (empty string), "e", "es", "est", "et", "s", "st", "t", "te", "tes", "test", "tet", "ts", "tst" and "tt". So return "tt".

Code

string getLargest(string s) {
    if(s.size() == 1)
        return s;
    string tmp = getLargest(s.substr(1));
    if(tmp[0] <= s[0])
        return s[0]+tmp;
    return tmp;
}

Problem 5 (Merge sort)

Merge sort is based on the divide-and-conquer paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with subproblems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through subproblems.

To sort A[p .. r]:

1. Divide Step

If a given array A has zero or one element, simply return; it is already sorted. Otherwise, split A[p .. r] into two subarrays A[p .. q] and A[q + 1 .. r], each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r].

2. Conquer Step

Conquer by recursively sorting the two subarrays A[p .. q] and A[q + 1 .. r].

3. Combine Step

Combine the elements back in A[p .. r] by merging the two sorted subarrays A[p .. q] and A[q + 1 .. r] into a sorted sequence. To accomplish this step, we will define a procedure MERGE (A, p, q, r).

 Code

vector<int> merge(vector<int> a, vector<int> b) {
    vector<int> res;
    int sz = (a.size()+b.size()), i = 0, j = 0;
  
    a.push_back(INT_MAX);
    b.push_back(INT_MAX);
 
    while(res.size() < sz) {
        if(a[i] <= b[j]) {
            res.push_back(a[i]);
            ++i;
        }
        else {
            res.push_back(b[j]);
            ++j;
        }
    }
 
    return res;
}


vector<int> merge_sort(vector<int> A) {
    if(A.size() <= 1) return A; // Already sorted
    vector<int> left, right, res;
 
    int i, mid = A.size()/2;
  
    for(i = 0; i < mid; i++) left.push_back(A[i]);
    for(i = mid; i < A.size(); i++) right.push_back(A[i]);
 
    left = merge_sort(left);
    right = merge_sort(right);
    res = merge(left, right);
  
    return res;
}


In the next post i will show sample problems solved using the Dynamic programming technique.

Problem solving techniques (Cont.) Example problems

In this post and the up coming future posts i will show how to use the techniques discussed in my earlier posts problem solving techniques (part 1 and part 2) to solve problems.

Complete search (brute force) examples

Problem 1 (Building a House)
Code jam (Qualification Round Africa and Arabia 2011)

You have just bought land and want to plant the largest rectangular field possible. In surveying your land, you find a number of obstacles and decide to draw a map. You indicate in each square of the map whether it contains grass (G), rock (R), water (W), shrubs (S), or trees (T). While the grass can be mowed and the shrubs dug from the ground, the water, rocks, and trees cannot be removed. Given these obstacles, determine the area of the largest rectangular field.

Input

The first line of input gives the number of cases, N.
N test cases follow. For each test case there will be:

• One line containing two space-separated integers indicating the length (L) and width (W) of your land.
• Followed by, W lines, each containing L characters where each indicates the conditions for that square of land (one of G, R, W, S, or T).

Output

For each test case, output one line containing "Case #x: " followed by the maximum area of the largest rectangle that can be cleared.

Limits:
1 ≤ L ≤ 50
1 ≤ W ≤ 50

N ≤ 30
Fewer than 20 obstacles in each test case. 

Discussion

From the constraints above we can check that a brute-force solution could survive. With the mathematical fact that we can represent a rectangle with only two points, we can iterate all possible combination's of two points and check if the rectangle represented with those two points include an obstacle or not. O(L^2*W^2*C) where c is the number of obstacles in the grid.

Code

vector<point> obstacles;
int res = -1;

for (i = 0; i < l; i++)
for (j = 0; j < w; j++)
if(grid[i][j] != 'G' || grid[i][j] != 'S') obstacles.push_back(point(i, j));

for(i = 0; i < l; i++)
for(j = 0; j < w; j++)
for(a = i; a < l; a++)
for(b = j; b < w; b++)
{

for(c = 0; c < obstacles.size(); c++)

if(obstacles[c].x >= i && obstacles[c].x <= a && obstacles[c].y >= j && obstacles[c].y <= b) break;

if(c >= obstacles.size()) res = max(res, (a-i+1)*(b-j+1));

}

cout << res << endl;

Problem 2 (SRMCodingPhase)
Topcoder (SRM 520 Div 2 level 2, Div 1 level 1)

Mr. Dengklek introduced you to an online programming contest called SRM (Special Round Match)!

You are now in the coding phase of the contest. There are 3 problems in the contest. You have practiced a lot before in practice rooms, so you are sure that you can solve the first problem in skills[0] minutes, the second problem in skills[1] minutes and the third problem is skills[2] minutes.

You have exactly 75 minutes to solve the problems. Before submitting a solution to a problem, you must first open the problem. If you submit a solution to a problem t minutes after you open the problem, you will receive:

• (points[0] - 2t) points for the first problem, or
• (points[1] - 4t) points for the second problem, or
• (points[2] - 8t) points for the third problem.

In your strategy, you only submit a solution to a problem after you solve the problem. If you don't submit a solution to a problem, you will receive zero points for the problem.

It is well-known that luck plays an important role in a contest. A fortune-teller told you that you have luck points of luck. You may use these points to decrease the amount of time you need to solve the problems, in minutes. Of course, you don't have to use all the points. Each point is worth one minute per problem. So, if you initially can solve a problem in t minutes, by using x points of luck (where x is a positive integer and 0 < x < t), you can solve the problem in (t - x) minutes (it is impossible to use t or more points of luck on the problem).

Arrange your strategy in this coding phase. Return the maximum total score you can achieve in this coding phase.

Constraints
-	points will contain exactly 3 elements.
-	points[0] will be between 250 and 300, inclusive.
-	points[1] will be between 450 and 600, inclusive.
-	points[2] will be between 900 and 1100, inclusive.
-	skills will contain exactly 3 elements.
-	Each element of skills will be between 1 and 100, inclusive.
-	luck will be between 0 and 100, inclusive.

Discussion

From the problem constraints we can loop through all possible combination's of solved problems and compute the maximum points gained each time,  caution about the tricky luck part, we can use greedy to pass it.

Code

int countScore(vector <int> points, vector <int> skills, int luck) {
   
        int res = 0;
      
        for(int i = 0; i < 2; i++) // 1 solve, 0 not solve
        for(int j = 0; j < 2; j++) // 1 solve, 0 not solve
        for(int s = 0; s < 2; s++) // 1 solve, 0 not solve
        {
            vector<int> lucky(3, 0);
            int minutes = 0, tmp = 0;
          
            if(s == 1) { // Solving problem 3
                lucky[2] = min(skills[2]-1, luck); // Compute the lucky for prob 3
                minutes += skills[2]; // Add the time for solving prob 3
                tmp += points[2]-8*(skills[2]-lucky[2]); // Add the points gained from solving prob 3
            }
            if(j == 1) { // solving problem 2
                lucky[1] = min(skills[1]-1, luck-lucky[2]); // Compute the lucky of solving prob 2
                minutes += skills[1]; // Add the time for solving prob 2
                tmp += points[1]-4*(skills[1]-lucky[1]); // Add the points gained from solving prob 2
            }
            if(i == 1) {
                lucky[0] = min(skills[0]-1, luck-lucky[2]-lucky[1]); // Compute the lucky for prob 1
                minutes += skills[0]; // Add the time for solving prob 1
                tmp += points[0]-2*(skills[0]-lucky[0]); // Add the points gained from solving prob 1
            }  
          
            if(minutes-luck <= 75) { // Check that we can solve the probs within time
                res = max(res, tmp); // Check the max num of points
            }
        }
      
        return res;
    }


The next post show how to solve specific types of problems using Divide and Conquer technique.

Problem solving techniques (Cont.)

In this post i will complete the post Problem solving techniques

Backtracking

Backtracking is a refinement of the brute force approach, which systematically searches for a solution to a problem among all available options. It does so by assuming that the solutions are represented by vectors (v₁, ..., v_m) of values and by traversing, in a depth first manner, the domains of the vectors until the solutions are found. 

When invoked, the algorithm starts with an empty vector. At each stage it extends the partial vector with a new value. Upon reaching a partial vector (v₁, ..., v_i) which can’t represent a partial solution, the algorithm backtracks by removing the trailing value from the vector, and then proceeds by trying to extend the vector with alternative values. 

Graph Algorithms

Representing a graph

Array representation

The basic concept is to have a 2 dimensional array of integers, where the element in row i, at column j represents the edge cost from node i to j. If the connection from i to j is not possible, we use some sort of sentinel value (usually a very large or small value, like -1 or the maximum integer). Another nice thing about this type of structure is that we can represent directed or undirected edges very easily.

So for example, the following connection matrix:

    A  B  C
A   0  1  5
B  -1  0  1
C  -1 -1  0

Would mean that node A has a 0 weight connection to itself, a 1 weight connection to node B and 5 weight connection to node C. Node B on the other hand has no connection to node A, a 0 weight connection to itself, and a 1 weight connection to C. Node C is connected to nobody. This graph would look like this if you were to draw it:

This representation is very convenient for graphs that do not have multiple edges between each node, and allows us to simplify working with the graph.


Adjacency list

In this representation the graph can be represented as a big list of nodes, each node can be represented as a structure that holds data section and a list of indicies (Indicies of the childs).

structure node
   vector<int> childs;
   [data]
end

vector<node> graph;

Searching a graph

Depth first search

The depth first search is well geared towards problems where we want to find any solution to the problem (not necessarily the shortest path), or to visit all of the nodes in the graph.

The basic concept is to visit a node, then push all of the nodes to be visited onto the stack. To find the next node to visit we simply pop a node of the stack, and then push all the nodes connected to that one onto the stack as well and we continue doing this until all nodes are visited. It is a key property of the Depth First search that we not visit the same node more than once, otherwise it is quite possible that we will recurse infinitely. We do this by marking the node as we visit it, then unmarking it after we have finished our recursions. This action allows us to visit all the paths that exist in a graph; however for large graphs this is mostly infeasible so we sometimes omit the marking the node as not visited step to just find one valid path through the graph (which is good enough most of the time).

So the basic structure will look something like this:

dfs(node start) {
 stack s;
 s.push(start);
 while (s.empty() == false) {
  top = s.top();
  s.pop();
  mark top as visited;

  check for termination condition

  add all of top's unvisited neighbors to the stack.
  mark top as not visited;
 }
}

Alternatively we can define the function recursively as follows:

dfs(node current) {
 mark current as visited;
 visit all of current's unvisited neighbors by calling dfs(neighbor)
 mark current as not visited;
}

Breadth First Search

The Breadth First search is an extremely useful searching technique. It differs from the depth-first search in that it uses a queue to perform the search, so the order in which the nodes are visited is quite different. It has the extremely useful property that if all of the edges in a graph are unweighted (or the same weight) then the first time a node is visited is the shortest path to that node from the source node. You can verify this by thinking about what using a queue means to the search order. When we visit a node and add all the neighbors into the queue, then pop the next thing off of the queue, we will get the neighbors of the first node as the first elements in the queue. This comes about naturally from the FIFO property of the queue and ends up being an extremely useful property. One thing that we have to be careful about in a Breadth First search is that we do not want to visit the same node twice, or we will lose the property that when a node is visited it is the quickest path to that node from the source.

The basic structure of a breadth first search will look this:

void bfs(node start) {
 queue s;
 s.push(start);
 while (s.empty() == false) {
  top = s.front();
  s.pop();
  mark top as visited;

 }

}

Shortest path

Dijkstra algorithm

It essentially allows you to write a Breadth First search, and instead of using a Queue you use a Priority Queue and define a sorting function on the nodes such that the node with the lowest cost is at the top of the Priority Queue. This allows us to find the best path through a graph in O(m * log(n)) time where n is the number of vertices and m is the number of edges in the graph. 

Graph algorithms

Maximum flow, minimum  cut problem

In this problem we are given a directed graph, in which every edge has a certain capacity c associated with it, a starting vertex (the source, X in the example above), and an ending vertex (the sink). We are asked to associate another value f satisfying f ≤ c for each edge such that for every vertex other than the source and the sink, the sum of the values associated to the edges that enter it must equal the sum of the values associated to the edges that leave it. We will call f the flow along that edge. Furthermore, we are asked to maximize the sum of the values associated to the arcs leaving the source, which is the total flow in the network. 

Now how do we actually solve the problem? First, let us define two basic concepts for understanding flow networks: residual networks and augmenting paths. Consider an arbitrary flow in a network. The residual network has the same vertices as the original network, and one or two edges for each edge in the original. More specifically, if the flow along the edge x-y is less than the capacity there is a forward edge x-y with a capacity equal to the difference between the capacity and the flow (this is called the residual capacity), and if the flow is positive there is a backward edge y-x with a capacity equal to the flow on x-y. An augmenting path is simply a path from the source to the sink in the residual network, whose purpose is to increase the flow in the original one. It is important to understand that the edges in this path can point the "wrong way" according to the original network. The path capacity of a path is the minimum capacity of an edge along that path.

The algorithm starts with no flow everywhere and increase the total flow in the network while there is an augmenting path from the source to the sink with no full forward edges or empty backward edges - a path in the residual network. The algorithm (known as the Ford-Fulkerson method) is guaranteed to terminate: due to the capacities and flows of the edges being integers and the path-capacity being positive, at each step we get a new flow that is closer to the maximum. As a side note, the algorithm isn't guaranteed to even terminate if the capacities are irrationals.

Now we are done with the theoretical part of studying algorithms. Example problems

MINIX 3 Operating system

Two years ago i was watching a video on youtube introducing the architecture of the MINIX 3 operating system, honestly it was really awesome and worth to be shared with you now.

In this post i will introduce to you the MINIX operating system architecture and design. I will give a small introduction about the design goals of minix then will push you into the details of all the modules and the hierarchy of the MINIX kernel modules.

Agenda

• Introduction
• Minix 3 Features
• Design Goals
• Minix 3 Architecture
• Minix 3 Drivers and Servers
• Reliability and security
• Conclusion
• References

Introduction

MINIX 3 is a new open-source operating system designed to be highly reliable, flexible, and secure. It is loosely based somewhat on previous versions of MINIX, but is fundamentally different in many key ways. MINIX 1 and 2 were intended as teaching tools; MINIX 3 adds the new goal of being usable as a serious system on resource-limited and embedded computers and for applications requiring high reliability

This new OS is extremely small, with the part that runs in kernel mode under 6000 lines of executable code. The parts that run in user mode are divided into small modules, well insulated from one another. For example, each device driver runs as a separate user-mode process so a bug in a driver (by far the biggest source of bugs in any operating system), cannot bring down the entire OS. In fact, most of the time when a driver crashes it is automatically replaced without requiring any user intervention, without requiring rebooting, and without affecting running programs. These features, the tiny amount of kernel code, and other aspects greatly enhance system reliability.

MINIX 3 Features

• POSIX compliant
• Networking with TCP/IP
• X Window System
• Languages: cc, gcc, g++, perl, python, etc.
• Over 650 UNIX programs
• Many improvements since V2
• Full multiuser and multiprogramming
• Device drivers run as user processes
• High degree of fault tolerance
• Full C source code supplied

Design Goals

The approach that MINIX 3 uses to achieve high reliability is fault isolation. In particular, unlike traditional OSes, where all the code is linked into a single huge binary running in kernel mode, in MINIX 3, only a tiny bit of code runs in kernel mode--about 4000 lines in all (Minix 2). This code handles interrupts, process scheduling, and interprocess communication. The rest of the operating system runs as a collection of user-mode processes, each one encapsulated by the MMU hardware and none of them running as superuser. One of these processes, dubbed the reincarnation server, keeps tabs on all the others and when one of them begins acting sick or crashes, it automatically replaces it by a fresh version. Since many bugs are transient, triggered by unusual timing, in most cases, restarting the faulty component solves the problem and allows the system to repair itself without a reboot and without the user even noticing it. This property is called self healing, and traditional systems do not have it.

Minix 3 Architecture

The structure of MINIX 3 is shown in Fig. 1. It is constructed as a series of layers. At the bottom, running in kernel mode, is a microkernel, consisting of about 3000 lines of C and 800 lines of assembler (Minix 2). Above that comes a layer of device drivers, with each driver in a separate user-mode process to ease in replacing it should it fail. Then come the servers, which form the core of the operating system. These include the reincarnation server mentioned above, the file server, the process manager, and others, including the X server, the data store, and various others. Finally, on top of that come the user processes. Although internally, MINIX 3 is completely different from other UNIX systems, it supports the standard POSIX interface to applications, so normal UNIX software can be ported fairly easily.

Fig. 1

The components communicate by passing fixed-length messages. For example, a user process requests file I/O send sending a message to the file server, which then checks its cache and if the needed block is not present, sends a message to the disk driver process to go get the block. While sending a message adds a little bit of overhead (about 500 nsec on a 3-GHz Pentium 4), the system is still quite responsive. For example, a complete system build, which requires over 120 compilations, takes well under 10 sec.

  

Minix 3 Drivers and Servers

• Drivers and servers run as user mode processes
• Powers granted to them are carefully cotrolled
• Non can execute privileged instructions
• Time slicing so drivers/servers in infinite loop can't hang sys
• None can access kernel memory
• None can directly access other address spaces
• Bit map for determining allowed kernel calls
• Bit map for who each one can send to
• No direct I/O and list of allowed I/O ports via kernel
• User mode servers
• File server:
• File system interface to user space programs
• Process manager
• Process management (Creation-Termination)
• Handles signals
• Virtual memory server
• Mechanisms is in the kernel, policy is in the VM server
• Keeps track of free and used pages
• Catches and handles page faults
• Data store
• Small local name server
• Used to map server name to end point
• Could be used for recoverable drivers
• Information server
• Used for debug dumps
• Network server
• Contains full TCP/IP stack in user space (Interesting huh? :-D)
• X server
• Reincarnation server
• Parent of all drivers and servers
• Whenever a server/driver dies the RS collects it
• RS checks a table for action to take e.g., Restart it
• RS also ping drivers and servers frequently

Reliability and security   

Kernel reliability and security

• Fewer line of codes means fewer kernel bugs
• No foreign code (e.g., drivers) in the kernel
• Static data structures (no malloc in kernel)
• Removing bugs to user space reduces their power

IPC reliability and security

• Fixed length messages (no buffer overruns)
• Initial rendezvous system was simple
• No lost messages
• No buffer management
• Interrupts and messages are unified
• Problem:
• Clients send messages to server
• Server tries to respond, but client has died
• Server can't send message and thus hangs
• Solution:
• Asynchronous messages

Drivers reliability and security

• Untrusted code: heavily isolated
• Bugs, viruses cannot spread to other modules
• Cannot touch kernel data structures
• Bad pointers crash only one driver; recoverable
• Infinite loops detected and driver restarted
• Restricted power to do damage (not superuser)

Conclusion 

• Current OSes are bloated and unreliable
• Minix 3 is an attempt at a reliable, secure OS
• Kernel is very small (6000 LoC)
• OS runs as a collection of user space processes
• Each driver is a separate process
• Each OS component has restricted privileges
• Faulty drivers can be replaced automatically

References

• Minix 3 home page
• OS news introduction to minix 3
• Andrew Tanenbaum talk
• Minix installation video

Introduction to IPtables firewall

In this post i will explain the basic usage of IPtables firewall.

Note: Samples taken from other articles -> Check the references section 

Agenda

• Introduction
• Understanding firewall and packet filtering
• IPtables internals
• Getting started
• Conclusion
• References

Introduction

IPtables is the IP packet filtering system that is integrated with the latest 2.4.x versions of the Linux kernel. This system facilitates greater control over IP packet filtering and firewall configuration on Linux systems, be they systems connected to the Internet or a LAN, servers, or proxy servers interfacing between a LAN and the Internet.

There is a wealth of information available about iptables, but much of it is fairly complex, and if you want to do a few basic things, this How To is for you.  

Understanding firewall and packet filtering

For a Linux system connected to a network, a firewall is the essential defense mechanism that allows only legitimate network traffic in and out of the system and disallows everything else. To determine whether the network traffic is legitimate or not, a firewall relies on a set of rules it contains that are predefined by a network or system administrator. These rules tell the firewall whether to consider as legitimate and what to do with the network traffic coming from a certain source, going to a certain destination, or having a certain protocol type. The term "configuring the firewall" refers to adding, modifying, and removing these rules.

Network traffic is made up of IP packets or simply packets -- small chunks of data traveling in streams from a source system to a destination system. These packets have headers, i.e. bits of data prefixed to every packet that contain information about the packet's source, destination, and protocol types. Based on a set of rules, a firewall checks these headers to determine which packet to accept and which packet to reject. This process is known as packet filtering. 

IPtables internals

The IPtables IP packet filtering system is a powerful tool that is used to add, edit and remove the rules that a firewall follows and consists of while making packet filtering decisions. These rules are stored in special-purpose packet filtering tables integrated in the Linux kernel. Inside the packet filtering tables the rules are grouped together in what are known as chains.

The netfilter/iptables IP packet filtering system, although referred to as a single entity, is actually made up of two components: netfilter and iptables. 

The netfilter component, also known as kernelspace, is the part of the kernel that consists of packet filtering tables containing sets of rules that are used by the kernel to control the process of packet filtering. 

The iptables component is a tool, also known as userspace, which facilitates inserting, modifying and removing rules in the packet filtering tables.

By using userspace, you can build your own customized rules that are saved in packet filtering tables in kernelspace. These rules have targets that tell the kernel what to do with packets coming from certain sources, heading for certain destinations or have certain protocol types. If a packet matches a rule, the packet can be allowed to pass through using target ACCEPT. A packet can also be blocked and killed using target DROP or REJECT. There are many more targets available for other actions that can be performed on packets. 

The rules are grouped in chains, according to the types of packets they deal with. Rules dealing with incoming packets are added to the INPUT chain. Rules dealing with outgoing packets are added to the OUTPUT chain. And rules dealing with packets being forwarded are added to the FORWARD chain. These three chains are the main chains built-in by default inside basic packet-filtering tables. There are many other chain types available like PREROUTING and POSTROUTING and there is also provision for user-defined chains. Each chain can have a policy that defines "a default target", i.e. a default action to perform, if a packet doesn't match any rule in that chain. 

After the rules are built and chains are in place, the real work of packet filtering starts. Here is where the kernelspace takes over from userspace. When a packet reaches the firewall, the kernel first examines the header information of the packet, particularly the destination of the packet. This process is known as routing.

If the packet originated from outside and is destined for the system and the firewall is on, the kernel passes it on to the INPUT chain of the kernelspace packet filtering table. If the packet originated from inside the system or another source on an internal network the system is connected to and is destined for another outside system, the packet is passed on to the OUTPUT chain. Similarly, packets originating from outside systems and destined for outside systems are passed on to the FORWARD chain. 

Next the packet's header information is compared with each rule in the chain it is passed on to, unless it perfectly matches a rule. If a packet matches a rule, the kernel performs the action specified by the target of that rule on the packet. But if the packet doesn't match a rule, then it is compared to the next rule in the chain. Finally, if the packet doesn't match to any rule in the chain, then the kernel consults the policy of that chain to decide what to do with the packet. Ideally the policy should tell the kernel to DROP that packet. Figure 1 graphically illustrates this packet filtering process.

             Figure 1

Getting started

Almost all Linux distributions come with iptables installed and ready to use. Make sure you have the iptables command available in your preferred shell. 

Because we are going to make modifications at the kernel level, make sure you have root privileges.

Checking Currently applied rules

root@desktop:~# iptables -L
Chain INPUT (policy ACCEPT)
target     prot opt source               destination         

Chain FORWARD (policy ACCEPT)
target     prot opt source               destination         

Chain OUTPUT (policy ACCEPT)
target     prot opt source               destination      

The output also mentions Chain. Think of iptable chains as sections in the firewall allowing a certain type of traffic. For example, to block all traffic from the private network to the internet, that rule would be set in the OUTPUT section. Similarly, any rule affecting incoming traffic would be listed in the INPUT chain.
The three chains are each applied to one type of activity in the firewall. At this point, there is nothing set yet. This means there are no restrictions and all network traffic is allowed to come and go.

• Chain INPUT
• Chain FORWARD, and
• Chain OUTPUT

Saving rules to a file

root@desktop:~# iptables-save > /etc/iptables.rules

root@desktop:~# cat /etc/iptables.rules 
# Generated by iptables-save v1.4.4 on Thu Dec 22 15:10:42 2011

*filter
:INPUT ACCEPT [732:83443]
:FORWARD ACCEPT [0:0]
:OUTPUT ACCEPT [656:51642]
COMMIT
# Completed on Thu Dec 22 15:10:42 2011

 

Use the iptables-save command and redirected the output to a text file in the "/etc" directory. 

One of the first requirements is to allow established connections to receive traffic. You need this when you want anything behind the firewall (in a private network) to be able to send and receive network data without restrictions.

Establish sessions rule
 

root@desktop:~# iptables -A INPUT -m conntrack --ctstate \

ESTABLISHED,RELATED -j ACCEPT
root@desktop:~# iptables -L
Chain INPUT (policy ACCEPT)
target     prot opt source               destination         
ACCEPT     all  --  anywhere             anywhere    ctstate RELATED,ESTABLISHED 

Chain FORWARD (policy ACCEPT)
target     prot opt source               destination         

Chain OUTPUT (policy ACCEPT)
target     prot opt source               destination

To have a better idea of what was issued, let's break the command apart and explain each one:

-A INPUT: Append this rule to the INPUT chain.

-m conntrack: Match the following connection tracking for the current packet/connection. 

-ctstate ESTABLISHED, RELATED: Connection states that the rule should apply to. In this case, an ESTABLISHED connection means a connection that has seen packets in both directions and a RELATED type means that the packet is starting a new connection but it is associated with an existing connection.

-j ACCEPT: tells the firewall to accept the connections described before. Another valid setting for the -j flag would be DROP




Accepting inbound SSH connections




root@desktop:~# iptables -A INPUT -p tcp --dport ssh -j ACCEPT
root@desktop:~# iptables -L
Chain INPUT (policy ACCEPT)
target     prot opt source               destination         
ACCEPT     all  --  anywhere             anywhere     ctstate RELATED,ESTABLISHED 
ACCEPT     tcp  --  anywhere             anywhere     tcp dpt:ssh 

Chain FORWARD (policy ACCEPT)
target     prot opt source               destination         

Chain OUTPUT (policy ACCEPT)

target     prot opt source               destination         

Blocking all incoming traffic

root@desktop:~#  iptables -A INPUT -j DROP
root@desktop:~# iptables -L
Chain INPUT (policy ACCEPT)
target     prot opt source               destination         
ACCEPT     all  --  anywhere             anywhere     ctstate RELATED,ESTABLISHED 
ACCEPT     tcp  --  anywhere             anywhere     tcp dpt:ssh 
DROP       all  --  anywhere             anywhere            

Chain FORWARD (policy ACCEPT)
target     prot opt source               destination         

Chain OUTPUT (policy ACCEPT)
target     prot opt source               destination       
 

Verifying firewall configuration

root@desktop:~# iptables-save > /etc/iptables.rules 
root@desktop:~# cat /etc/iptables.rules 
# Generated by iptables-save v1.4.4 on Thu Dec 22 15:10:42 2011
*filter
:INPUT ACCEPT [1234:120406]
:FORWARD ACCEPT [0:0]
:OUTPUT ACCEPT [1522:124750]
-A INPUT -m conntrack --ctstate RELATED,ESTABLISHED -j ACCEPT 
-A INPUT -p tcp -m tcp --dport 22 -j ACCEPT 
-A INPUT -j DROP 
COMMIT
# Completed on Thu Dec 22 15:10:42 2011

Network scan with locked down server

~ $ nmap 10.0.0.120    

Starting Nmap 5.35DC1 ( http://nmap.org ) at 2010-11-21 20:56 EST
Note: Host seems down. If it is really up, but blocking our ping probes, try -Pn
Nmap done: 1 IP address (0 hosts up) scanned in 3.04 seconds

~ $ nmap -Pn 10.0.0.120

Starting Nmap 5.35DC1 ( http://nmap.org ) at 2010-11-21 20:56 EST
Nmap scan report for 10.0.0.120
Host is up (0.017s latency).
Not shown: 999 filtered ports
PORT   STATE SERVICE
22/tcp open  ssh

Nmap done: 1 IP address (1 host up) scanned in 12.19 seconds

Note that a scan was attempted against the IP where the server is located, but nmap failed to list the open ports. This happens because the firewall is set in such a way that it is blocking everything except for the SSH port we have open. Since nmap uses a specific network  protocol to verify if the host is up, it returned empty handed. The second try was successful and is telling us that only SSH is open and nothing else. With just three rules, we managed to get an effective lock down of  our server.
Saving rules

Now you've learned how to build basic rules and chains and how to add or remove them from the packet filtering tables. But you should remember that rules built the way described above are saved into the kernel and are lost when the system is rebooted. So if you have an error-free and efficient set of rules added to the packet filtering tables, to use the rules again after a reboot, you have to save the rule set in a file.

$ iptables-save > iptables-script
 
Whenever you boot your system again, you can restore the rule set into the packet filtering tables from this script file using the iptables-restore command as shown below:

$ iptables-restore iptables-script
 
And if you prefer to restore the rule set automatically every time you boot your system, then you can put the command specified above into any of your initialization shell-scripts.
 

 Conclusion

We have gone through some simple steps to get iptables to run properly and to safely lock down a Linux server. The rules applied should provide a good sense of what is going on in a server using iptables as a firewall. I encourage you to give iptables a try, especially if you depend on an appliance and want more control and easily replicated human-readable configurations.

While the rules used we've used here are simple, the full flexibility and complexity of iptables is beyond the scope of this article. There are many complex rules that you can combine to create a safe and controllable firewall environment.

 References

• Introduction to netfilter/iptables
• Firewall uptime and security with iptables
• IPtables HowTo

Introduction to GNU C Compiler (GCC)

In this post i will show some of the useful built-in functions and command line options, Not all of them but the most important to me and may be to the reader.

Agenda

• Command line options
• C dialect options
• Warning options
• Debugging options
• Optimize options
• Pre-processor options
• Link options
• Environment variables
•  Built-in functions
• References

Command line options

C dialect options


-ansi

In C mode, this is equivalent to `-std=c90'. In C++ mode, it is equivalent to `-std=c++98'.

This turns off certain features of GCC that are incompatible with ISO C90 (when compiling C code), or of standard C++ (when compiling C++ code), such as the asm and typeof keywords, and predefined macros such as unix and vax that identify the type of system you are using. It also enables the undesirable and rarely used ISO trigraph feature. For the C compiler, it disables recognition of C++ style `//' comments as well as the inline keyword.

The alternate keywords __asm__, __extension__, __inline__ and __typeof__ continue to work despite -ansi. You would not want to use them in an ISO C program, of course, but it is useful to put them in header files that might be included in compilations done with -ansi. Alternate predefined macros such as __unix__ and __vax__ are also available, with or without -ansi.

-fno-asm 

Do not recognize asm, inline or typeof as a keyword, so that code can use these words as identifiers. You can use the keywords __asm__, __inline__ and __typeof__ instead. -ansi implies -fno-asm.

In C++, this switch only affects the typeof keyword, since asm and inline are standard keywords. You may want to use the -fno-gnu-keywords flag instead, which has the same effect.

-fopenmp

Enable handling of OpenMP directives #pragma omp in C/C++ and !$omp in Fortran. When -fopenmp is specified, the compiler generates parallel code according to the OpenMP Application Program Interface v3.0 http://www.openmp.org/.

Warning options

-fsyntax-only

Check the code for syntax errors, but don't do anything beyond that.

-fmax-errors=n

Limits the maximum number of error messages to n, at which point GCC bails out rather than attempting to continue processing the source code. If n is 0 (the default), there is no limit on the number of error messages produced. If -Wfatal-errors is also specified, then -Wfatal-errors takes precedence over this option.

-w

Inhibit all warning messages.

-Werror

Make all warnings into errors. 

-Wfatal-errors 

 This option causes the compiler to abort compilation on the first error occurred rather than trying to keep going and printing further error messages. 

-Wall 

This enables all the warnings about constructions that some users consider questionable, and that are easy to avoid (or modify to prevent the warning), even in conjunction with macros.

-Wunused-function 

Warn whenever a static function is declared but not defined or a non-inline static function is unused. This warning is enabled by -Wall.

-Wunused-parameter 

Warn whenever a function parameter is unused aside from its declaration.

-Wunused-label 

Warn whenever a label is declared but not used. This warning is enabled by -Wall.

-Wunused-parameter 

Warn whenever a function parameter is unused aside from its declaration

-Wunused-variable

Warn whenever a local variable or non-constant static variable is unused aside from its declaration. This warning is enabled by -Wall.

-Wunused-value 

Warn whenever a statement computes a result that is explicitly not used. To suppress this warning cast the unused expression to `void'. This includes an expression-statement or the left-hand side of a comma expression that contains no side effects. For example, an expression such as `x[i,j]' will cause a warning, while `x[(void)i,j]' will not. This warning is enabled by -Wall.

-Wunused 

All the above -Wunused options combined.

-Wno-div-by-zero 

Do not warn about compile-time integer division by zero. Floating point division by zero is not warned about, as it can be a legitimate way of obtaining infinities and NaNs.

-Wfloat-equal 

 Warn if floating point values are used in equality comparisons.

-Wtype-limits 

Warn if a comparison is always true or always false due to the limited range of the data type, but do not warn for constant expressions. For example, warn if an unsigned variable is compared against zero with `<' or `>='. This warning is also enabled by -Wextra 

-Wsign-compare 

 Warn when a comparison between signed and unsigned values could produce an incorrect result when the signed value is converted to unsigned. This warning is also enabled by -Wextra; to get the other warnings of -Wextra without this warning, use `-Wextra -Wno-sign-compare'.

-Winline 

Warn if a function can not be inlined and it was declared as inline. Even with this option, the compiler will not warn about failures to inline functions declared in system headers. 

The compiler uses a variety of heuristics to determine whether or not to inline a function. For example, the compiler takes into account the size of the function being inlined and the amount of inlining that has already been done in the current function. Therefore, seemingly insignificant changes in the source program can cause the warnings produced by -Winline to appear or disappear. 

-Wstack-protector 

This option is only active when -fstack-protector is active. It warns about functions that will not be protected against stack smashing.

-Woverlength-strings 

Warn about string constants which are longer than the “minimum maximum” length specified in the C standard. Modern compilers generally allow string constants which are much longer than the standard's minimum limit, but very portable programs should avoid using longer strings.

Debugging options

-g 

Produce debugging information in the operating system's native format (stabs, COFF, XCOFF, or DWARF 2). GDB can work with this debugging information.

-ggdb

Produce debugging information for use by GDB.

-Q 

Makes the compiler print out each function name as it is compiled, and print some statistics about each pass when it finishes.

-ftime-report 

Makes the compiler print some statistics about the time consumed by each pass when it finishes.

Optimize options

-O

-O1 

Optimize. Optimizing compilation takes somewhat more time, and a lot more memory for a large function. 

With -O, the compiler tries to reduce code size and execution time, without performing any optimizations that take a great deal of compilation time.

-O2 

Optimize even more. GCC performs nearly all supported optimizations that do not involve a space-speed tradeoff. As compared to -O, this option increases both compilation time and the performance of the generated code.

-O3

Optimize yet more. -O3 turns on all optimizations specified by -O2 and also turns on the -finline-functions, -funswitch-loops, -fpredictive-commoning, -fgcse-after-reload, -ftree-vectorize and -fipa-cp-clone options.

-O0 

Reduce compilation time and make debugging produce the expected results. This is the default.

-Os

Optimize for size. -Os enables all -O2 optimizations that do not typically increase code size. It also performs further optimizations designed to reduce code size.

-fstack-protector 

Emit extra code to check for buffer overflows, such as stack smashing attacks. This is done by adding a guard variable to functions with vulnerable objects. This includes functions that call alloca, and functions with buffers larger than 8 bytes. The guards are initialized when a function is entered and then checked when the function exits. If a guard check fails, an error message is printed and the program exits.

-fstack-protector-all 

Like -fstack-protector except that all functions are protected.

Pre-processor options

-D name 

Predefine name as a macro, with definition 1.

-D name=definition 

The contents of definition are tokenized and processed as if they appeared during translation phase three in a `#define' directive. In particular, the definition will be truncated by embedded newline characters.

-U name 

Cancel any previous definition of name, either built in or provided with a -D option.

-undef 

Do not predefine any system-specific or GCC-specific macros. The standard predefined macros remain defined.

-I dir 

Add the directory dir to the list of directories to be searched for header files. Directories named by -I are searched before the standard system include directories. If the directory dir is a standard system include directory, the option is ignored to ensure that the default search order for system directories and the special treatment of system headers are not defeated . If dir begins with =, then the = will be replaced by the sysroot prefix; see --sysroot and -isysroot.

-o file 

Write output to file. This is the same as specifying file as the second non-option argument to cpp. gcc has a different interpretation of a second non-option argument, so you must use -o to specify the output file.

-v 

Verbose mode. Print out GNU CPP's version number at the beginning of execution, and report the final form of the include path.

-version

--version 

Print out GNU CPP's version number. With one dash, proceed to preprocess as normal. With two dashes, exit immediately.

Link options

-llibrary

-l library 

Search the library named library when linking. (The second alternative with the library as a separate argument is only for POSIX compliance and is not recommended.)

-static 

On systems that support dynamic linking, this prevents linking with the shared libraries. On other systems, this option has no effect.

-shared 

Produce a shared object which can then be linked with other objects to form an executable. Not all systems support this option.

Directory options

COMPILER_PATH 

The value of COMPILER_PATH is a colon-separated list of directories, much like PATH. GCC tries the directories thus specified when searching for subprograms, if it can't find the subprograms using GCC_EXEC_PREFIX.

LIBRARY_PATH 

The value of LIBRARY_PATH is a colon-separated list of directories, much like PATH. When configured as a native compiler, GCC tries the directories thus specified when searching for special linker files, if it can't find them using GCC_EXEC_PREFIX. Linking using GCC also uses these directories when searching for ordinary libraries for the -l option (but directories specified with -Lcome first).

Built-in functions

__builtin_types_compatible_p (type1, type2)

You can use the built-in function __builtin_types_compatible_p to determine whether two types are the same.
This built-in function returns 1 if the unqualified versions of the types type1 and type2 (which are types, not expressions) are compatible, 0 otherwise. The result of this built-in function can be used in integer constant expressions.

double __builtin_huge_val (void)

Returns a positive infinity, if supported by the floating-point format, else DBL_MAX. This function is suitable for implementing the ISO C macro HUGE_VAL.

float __builtin_huge_valf (void)

Similar to __builtin_huge_val, except the return type is float.

long double __builtin_huge_vall (void)

Similar to __builtin_huge_val, except the return type is long double.

 double __builtin_inf (void)

Similar to __builtin_huge_val, except a warning is generated if the target floating-point format does not support infinities.

int __builtin_ctz (unsigned int x)

Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.

int __builtin_popcount (unsigned int x)

Returns the number of 1-bits in x.

References

• GCC online docs

Problem solving techniques

In this post i will present some of the basic knowledge a computer programmer should have in order to solve specific types of problems. This will increase developers' skills by not only increasing their ability for solving hard problems, but also help them writing the most efficient code for a specific solution.

Agenda

• Introduction

• Runtime analysis
• Program execution time
• Best case vs Average case vs Worst case analysis

•  Problem solving techniques
• Complete search
• Divide and conquer
• Dynamic programming
• Greedy
• Backtracking

• Graph algorithms
• Representing a graph
• Array representation
• Adjacency list

• Searching a graph
• Depth first search  
• Breadth first search
• Shortest path
• Dijkstra algorithm
• Graph algorithms
• Maximum flow, minimum cut algorithm

• Example problems
• Conclusion
• References

Introduction

The first step towards an understanding of why the study and knowledge of algorithms are so important is to define exactly what we mean by an algorithm. According to the popular algorithms textbook Introduction to Algorithms (Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein), "an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values as output." In other words, algorithms are like road maps for accomplishing a given, well-defined task. So, a chunk of code that calculates the terms of the Fibonacci sequence is an implementation of a particular algorithm. Even a simple function for adding two numbers is an algorithm in a sense, albeit a simple one.

Some algorithms, like those that compute the Fibonacci sequences, are intuitive and may be innately embedded into our logical thinking and problem solving skills. However, for most of us, complex algorithms are best studied so we can use them as building blocks for more efficient logical problem solving in the future. In fact, you may be surprised to learn just how many complex algorithms people use every day when they check their e-mail or listen to music on their computers. This article will introduce some basic ideas related to the analysis of algorithms, and then put these into practice with a few examples illustrating why it is important to know about algorithms (Future posts).

Runtime analysis 

One of the most important aspects of an algorithm is how fast it is. It is often easy to come up with an algorithm to solve a problem, but if the algorithm is too slow, it's back to the drawing board.

Program execution time

Since the exact speed of an algorithm depends on where the algorithm is run, as well as the exact details of its implementation, computer scientists typically talk about the run-time relative to the size of the input. For example, if the input consists of N integers, an algorithm might have a run-time proportional to N^2, represented as O(N^2). This means that if you were to run an implementation of the algorithm on your computer with an input of size N, it would take C*N^2 seconds, where C is some constant that doesn't change with the size of the input.

Best case vs Average case vs Worst case analysis

In order to show the difference between these types of algorithms analysis, i will present a simple problem which is linear search. In this problem we take as input an array and a specific element to search for, the output is the index of this element. The actual processing for this algorithm is looping for all the array elements till we find it and return the index, or -1 if reach the end of the array.

•   Best case:

If the element exists at the start of the array this will take only one step of searching.

• Average case:

If the element exists at the middle of the array this will take N/2 steps to get a result.

• Worst case:

If the element doesn't exist this will take N steps to get a result.

Obviously searching for a solution that will survive the worst case is always the only way for a developer to survive :).

Problem solving techniques

Not all problems could be solved using a specific technique, but one can say that a specific category could be solved using a specific technique, however each problem has its own idea that problem solver should customize the technique used to solve the problem. 

Complete search (Brute force)

Complete search exploits the brute force, straight-forward, try-them-all method of finding the answer. This method should almost always be the first algorithm/solution you consider. If this works within time and space constraints, then do it: it's easy to code and usually easy to debug. This means you'll have more time to work on all the hard problems, where brute force doesn't work quickly enough. In the case of a problem with only fewer than a couple million possibilities, iterate through each one of them, and see if the answer works.

Divide and conquer

A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same (or related) type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

This technique is the basis of efficient algorithms for all kinds of problems.

Dynamic programming

A DP is an algorithmic technique which is usually based on a recurrent formula and one (or some) starting states. A sub-solution of the problem is constructed from previously found ones. DP solutions have a polynomial complexity which assures a much faster running time than other techniques like backtracking, brute-force etc.

Greedy technique

A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. On some problems, a greedy strategy need not produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution (Be-Careful).

For example, a greedy strategy for the traveling salesman problem (which is of a high computational complexity) is the following heuristic: "At each stage visit an unvisited city nearest to the current city". This heuristic need not find a best solution but terminates in a reasonable number of steps; finding an optimal solution typically requires unreasonably many steps.

Continue to the next section