All posts by ralf

Self Expanding Loops in C

Imagine you want to define a C preprocessor statement like this:

#define NUM_NOPS(i) .....

and later on, in your code:

NUM_NOPS(5);

and you want your preprocessor to roll out the following code:

asm volatile("nop");
asm volatile("nop");
asm volatile("nop");
asm volatile("nop");
asm volatile("nop");

This is not as easy as it looks like. One possibility is to use Boost’s Preprocessor Repetition Utility: <boost/preprocessor/repetition/repeat.hpp>. But however, let’s assume you don’t want to use any third party libraries. There is one further possibility. You can use GCC’s unrool loops functionality:

#pragma GCC push_options
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O2")
void nops() {
 int i = 0;
 for(; i < 10 ; i++) {
   asm volatile("nop");
 }
}
#pragma GCC pop_options

int main(void) {
  nops();
}

You should compile it with:

gcc -c -o test.o -O3 test.c

Having a look at the disassembly proves, that your loop was rolled out:

objdump -d test.o

test.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <nops>:
   0:   90                      nop
   1:   90                      nop
   2:   90                      nop
   3:   90                      nop
   4:   90                      nop
   5:   90                      nop
   6:   90                      nop
   7:   90                      nop
   8:   90                      nop
   9:   90                      nop
   a:   c3                      retq   

Disassembly of section .text.startup:

0000000000000000 <main>:
   0:   31 c0                   xor    %eax,%eax
   2:   e8 00 00 00 00          callq  7 <main+0x7>
   7:   f3 c3                   repz retq 

Gentoo: Using splitdebug for specific packages

It is often favourable to keep debugging information for certain packages.

Gentoo allows to keep those symbols by adding

CFLAGS="${CFLAGS} -ggdb"
CXXFLAGS="${CXXFLAGS} -ggdb"
FEATURES="${FEATURES} splitdebug"

to your make.conf

But this enables debugging information for all packages. In order to keep debugging symbols only for certain packages, you can define a splitdebug environment in /etc/portage/env/

/etc/portage/env/splitdebug.conf:

CFLAGS="${CFLAGS} -ggdb"
CXXFLAGS="${CXXFLAGS} -ggdb"
FEATURES="${FEATURES} splitdebug"

Now you can add your packages to /etc/portage/package.env:

sys-libs/glibc splitdebug.conf

So when compiling glibc, portage will use the splitdebug environment and keep debugging symbols.

Installing Gentoo on a Raspberry PI

Install ARM Toolchain

$ emerge -av crossdev
$ crossdev -S -v -t armv6j-hardfloat-linux-gnueabi

Get Raspberry Kernel Sources

$ git clone --depth=1 https://github.com/raspberrypi/linux.git
$ wget http://xecdesign.com/downloads/linux-qemu/linux-arm.patch
$ patch -p1 -d linux/ < linux-arm.patch

Configure the Kernel for QEMU

$ cd linux
$ make ARCH=arm menuconfig
$ make ARCH=arm
$ make ARCH=arm INSTALL_MOD_PATH=../modules modules_install
$ cp arch/arm/boot/zImage ../raspi-kernel

This is my .config
and the corresponding zImage and Modules: kernel_raspi_qemu.tar

Prepare “SD Card”

Create a sparse Image (this will be the SD Card)
$ dd if=/dev/null of=gentoo-raspi.img bs=1G seek=8 # 8GiB Image Partition Image
$ cfdisk gentoo-raspi.img
#first partition: boot, vfat ~80MiB (Partition Type: 0x0C)
#second: Gentoo Root (Partition Type: 0x83)

Mount Image as NBD

$ modprobe nbd max_part=4
$ qemu-nbd --connect=/dev/nbd0 -n /path/to/gentoo-raspi.img

$ emerge -av dosfstools
$ mkfs.vfat -n boot /dev/nbd0p1
$ mkfs.ext4 -j -L Gentoo -E lazy_itable_init=0,lazy_journal_init=0 /dev/nbd0p2
$ mount /dev/nbd0p2 /mnt/raspi
$ cd /mnt/raspi
$ curl http://distfiles.gentoo.org/releases/arm/autobuilds/current-stage3-armv6j_hardfp/stage3-armv6j_hardfp-20130207.tar.bz2 | tar -xvjp

Prepare Base System


$ dd if=/dev/zero of=/mnt/raspi/var/swap bs=1M count=512
$ chmod 0600 /mnt/raspi/var/swap
$ mkswap /mnt/raspi/var/swap

$ cd /mnt/raspi/etc
$ vi fstab


Insert the following lines:
LABEL=Gentoo / ext4 noatime 0 1
LABEL=BOOT /boot vfat noatime,defaults 0 0
/var/swap swap swap defaults 0 0

Set Root Password
$ openssl passwd -1 raspi
$ vi shadow

first line: root:$1$pDGeoXQj$0zq3sa5b9o9rJ8CpcIpPR/:10770:0:::::

Set Hostname & Keymap & timezone
$ vi conf.d/hostname
$ vi conf.d/keymaps
$ ln -sf ../usr/share/zoneinfo/Europe/Berlin localtime

Configure locale.gen
$ vi /etc/locale.gen

Copy Kernel Modules
$ cp -av /path/to/modules/lib /mnt/raspi

Install Portage
$ curl http://distfiles.gentoo.org/snapshots/portage-latest.tar.bz2 | tar -xvjp -C /mnt/raspi/usr

Set correct make.profile
$ cd /mnt/raspi/etc/portage rm make.profile
$ ln -sf ../../usr/portage/profiles/default/linux/arm/13.0 make.profile

Disconnect NBD
$ umount /mnt/raspi
$ qemu-nbd --disconnect /dev/nbd0

Boot your Raspberry on QEMU

$ qemu-system-arm -kernel zImage -cpu arm1176 -m 256 -M versatilepb -no-reboot -serial stdio -append "root=/dev/sda2 panic=1 console=ttyAMA0" -hda gentoo-raspi.img
Login: root:raspi
Set Date (Raspi has no hardware Clock ๐Ÿ™ )
$ date --set="20130808 14:00"
$ rc-update del hwclock default

Configure Network
$ ifconfig eth0 10.0.2.15 #USE THIS IP!
$ route add default gw 10.0.2.2
$ echo nameserver 8.8.8.8 > /etc/resolv.conf #just use google's dns

Get dhcp Client and configure network
$ emerge dhcpcd
$ dhcpcd

Configure eth0 persistently
$ cd /etc/init.d
$ ln -s net.lo net.eth0
$ rc-update add net.eth0 boot

$ cd /etc/conf.d/
$ nano net

add the line: config_eth0="dhcp"

You WANT distcc.
emerge -av distcc #Run on both, host and guest

Edit make.conf
$ echo FEATURES="distcc" >> /etc/portage/make.conf
$ echo MAKEOPTS="-j6" >> /etc/portage/make.conf

Set DistCC Hosts
$ cd /etc/distcc
$ nano hosts

Now compile everything you want

Emerge boot stuff and kernel
$ mkdir /etc/portage/package.keywords
$ cd /etc/portage/package.keywords
$ echo sys-boot/raspberrypi-firmware ** ~arm >> raspi
$ echo sys-kernel/raspberrypi-sources ** ~arm >> raspi
$ echo media-libs/raspberrypi-userland ** ~arm >> raspi

$ mount /boot
$ emerge -av raspberrypi-firmware raspberrypi-sources raspberrypi-userland

Compile the kernel
$ cd /usr/src/linux
$ make menuconfig

$ make CC="distcc armv6j-hardfloat-linux-gnueabi-gcc" modules -j5
$ make modules_install
$ make CC="distcc armv6j-hardfloat-linux-gnueabi-gcc" -j5
$ cp arch/arm/boot/zImage /boot/kernel.img

This is my precompiled Kernel and Modules / Firmware:
.config
kernel-3.6.11-raspi.tar.gz

You also want to use SSH:
$ rc-update add sshd default

And as we do have no RTC:
$ rc-update add ntp-client default

And a syslogger:
$ emerge -av syslog-ng
$ rc-update add syslog-ng boot

Here's my image:
It needs at least 2.8GiB of space (2.3GiB without /var/swap)

As .tar.gz archive:
VFAT Boot Partition: Raspberry-Boot-20130816.tar.gz
Gentoo Installation: Raspberry-Stage4-20130816.tar.gz

As full 6GiB raw image which is bootable out of the box:
Raspberry-Gentoo-6GiB-Image-20130816.img.gz

You can use dd to flash it on a SD Card
$ gunzip Raspberry-Gentoo-6GiB-Image-20130816.img.gz
$ dd if=Raspberry-Gentoo-6GiB-Image-20130816.img of=/dev/yourraspisdcard

Have fun with Gentoo on your Raspi ๐Ÿ™‚

Update 2014-06-03:

Here's another nice tutorial without any cross-compilation

Why does SSL / TLS not use Diffie-Helman Key Exchange by default?

As it is already known SSL has to deal with a lot of severe security problems and exploits. 1 2 3 4 5

This is how an SSL connection is established:
SSL Connection Establishment

  1. client_hello:
    This is the first packet which is sent from the client to the server. The client tells the server that he wants to establish a secure connection and informs the server about all cipher suites which are supported by the client. Following picture shows the client hello more in detail:
    suites One Cipher Suite could be:
    TLS_RSA_WITH_AES_256_CBC_SHA256
    That means that this suite uses RSA for Key Exchange. As symmetric cipher this suite uses AES with a keysize of 256 Bit. As mode of operation CBC is used, and SHA256 as hash algorithm.At the beginning of the connection, the server does not know which suites are supported by the client and vice versa. As the client wants to establish the connection, it is his task to tell the server about all supported cipher suites.
  2. server_hello: After the client_hello, the server answers with server_hello. Following picture shows it in detail:
    server_suite_decisionThe server decides which suite he would like to use. In the given example he decides to use TLS_RSA_WITH_AES_256_CBC_SHA256.
  3. Server Authentication: The server sends its certificate to the client which then can test wether the certificate is valid or not.
  4. Key Exchange: When TLS_RSA is used, the client generates a random Pre Master Secret (PMS) which is sent to the server encrypted with the public key of the server.ย The server is able to decrypt the encrypted PMS with its private Key. Both, server and client then derive a common secret from the PMS.
  5. The rest of the communication gets encrypted symmetrically with AES_256_CBC.

All in all, this mechanism seems to be quite secure. Authenticity is provided through the certificate and confidentiality is provided through the symmetric encryption. However, a closer look reveals that it’s not that secure after all:

In my opinion, one of the current major risks of SSL is making use of RSA for the encryption of the symmetric key. If a weak RSA key has been used, or some third know about the private key, all the traffic can be decrypted:

Decrypted

As mentioned above at the beginning of a TLS communication, SSL uses RSA for authentication. But unfortunately, RSA is also used for Key Exchange. Actually RSA is only intended to be used for authentication and not for Key Exchange. There are much better protocols for that problem. Diffie-Hellman is a very common key exchange protocol. But Diffie-Hellman is not used by SSL by default. So the symmetric connection depends exclusivley on the secrecy of the private key.

If Diffie Hellman would be used, a third party is not able to decrypt the connection, even if he knows about the private key. The following picture shows a simple SSL connection – remember: Wireshark still knows my private key!
SSL_with_DH

Unfortunately Diffie-Hellman Key Exchange doesn’t get used very often, though all modern browser do support it.

Dear SSL developers… In future versions of SSL, please disallow Key Exchange without Diffie-Hellman or any other kind of perfect forward secrecy by default. Do not argue by backward compatibility. Argument with security. Disallow medium and weak ciphers.

Check your configuration using nice tools like SSL Test.

Maybe it’s generally time for a new secure protocol like SSL. Without all that inherited waste.

UPDATE 2012-07-02:
Nice article on this topic: SSL: Intercepted today, decrypted tomorrow

Example Implementation of a Least Recently Used Cache in C++11

This is yet another example implementation of a Least Recently Used Cache written in C++11.
It is not designed to be threadsafe, but thread safety could easily be reached by locking
the same mutex at the beginning of all public methods.

This Cache uses std::map and std::list as container types. A copy and move constructor is implemented as well.
You may also download it here.
Usage:

LRUCache<int, string> cache(10); // Max. 10 Elements

cache[4] = "Foobar";
cache.insert(2, "Barfoo");

cout << cache[2] << endl;

auto tmp = cache.getCopy(2);
if(tmp == nullptr) {
  cout << "Not found..." << endl;
} else {
 cout << *tmp << endl;
}

LRUCache.h:

#ifndef LRUCACHE_H_
#define LRUCACHE_H_

#include <memory>
#include <map>
#include <list>

template <typename Key, typename Value>
class LRUCache {

private:
	typedef std::list<Key> HistoryType;
	typedef typename HistoryType::iterator HistoryTypeIterator;
	HistoryType _history;

	typedef std::map<Key, std::pair<Value, HistoryTypeIterator> > CacheType;
	typedef typename CacheType::iterator CacheTypeIterator;
	CacheType _cache;

	size_t _maxCapacity;

	void evict(size_t numElements = 1) {
		if(numElements > _history.size()) {
			numElements = _history.size();
		}

		while(numElements--) {
			auto it = _cache.find( _history.front() );
			_cache.erase(it);
			_history.pop_front();
		}
	}

	void updateHistory(const CacheTypeIterator& it) {
		_history.splice(_history.end(), _history, it->second.second);
	}
public:
	// if maxCapacity = 0 -> unlimited capacity
	LRUCache(size_t maxCapacity) : _maxCapacity(maxCapacity) {

	}

	~LRUCache() {

	}

	LRUCache(const LRUCache& other) : _maxCapacity(other._maxCapacity) {
		std::cout << "Copy Con" << std::endl;
		_cache = other._cache;
		_history = other._history;

		// Adjust Iterators
		for(auto it = _history.begin() ; it != _history.end() ; ++it)
			_cache.find(*it)->second.second = it;
	}

	LRUCache(LRUCache&& other) : _maxCapacity(other._maxCapacity) {
		_history = std::move(other._history);
		_cache = std::move(other._cache);
	}

	void dropCache(size_t maxRemainingElements = 0) {
		size_t elementsDropped;
		if(maxRemainingElements == 0) {
			elementsDropped = _history.size();
			_cache.clear();
			_history.clear();
		} else if (_history.size() > maxRemainingElements) {
			elementsDropped = _history.size() - maxRemainingElements;
			evict(elementsDropped);
		}
	}

	size_t size() {
		return _history.size();
	}

	void setMaxCapacity(const size_t& maxCapacity) {
		// problematic case: shrink cache
		if(maxCapacity < _maxCapacity && maxCapacity != 0)
			dropCache(maxCapacity);
		_maxCapacity = maxCapacity;
	}

	std::unique_ptr<Value> getCopy(const Key& id) {
		auto it = _cache.find(id);
		std::unique_ptr<Value> retval = nullptr;
		if(it != _cache.end()) {
			updateHistory(it);
			// Copy the element
			retval = std::unique_ptr<Value>(new Value(it->second.first));
		}

		return retval;
	}

	// Inserts new element. If the element already exists, it will be overwritten.
	// Returns a reference to the inserted object
	Value& insert(const Key& id, Value c) {
		// Check if the element is already existing
		auto it = _cache.find(id);
		if(it != _cache.end()) {
			// If the element exists, overwrite it
			it->second.first = c;
			updateHistory(it);
		} else {
			if(_maxCapacity != 0 && _history.size() == _maxCapacity) {
				evict();
			}
			auto end = _history.insert(_history.end(), id);
			auto newelem = _cache.insert( std::make_pair(id, std::make_pair(std::move(c), end ) ) );
			it = newelem.first;
		}

		return it->second.first;
	}

	Value&	operator[](const Key& id) {
		auto it = _cache.find(id);
		if(it != _cache.end()) {
			updateHistory(it);
			return it->second.first;
		}

		// Create new empty element
		return insert(id, std::move(Value()));
	}
};
#endif