Meditation, The Art of Exploitation

Thinking? At last I have discovered it--thought; this alone is inseparable from me. I am, I exist--that is certain. But for how long? For as long as I am thinking. For it could be, that were I totally to cease from thinking, I should totally cease to exist....I am, then, in the strict sense only a thing that thinks.

Tuesday, August 28, 2007

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

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


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

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

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

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

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

Friday, August 24, 2007

Spin lock, OS scheduler, and SMP

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

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

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

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

Wednesday, August 22, 2007

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

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


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

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


#ifndef MY_SOCKET_HPP
#define MY_SOCKET_HPP

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

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

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

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

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

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

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

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

#endif



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

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

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

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

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

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

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

Wednesday, August 15, 2007

Linux Threads, Process, Signals, C++ Exceptions

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

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

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

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

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

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

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

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

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

using namespace std;
using namespace boost;

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

typedef void (*sighandler_t)(int);

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

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

class bthread{

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

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