Runtime support for approximate computing in heterogeneous systems

Recently I just finished my MSc Thesis, titled “Runtime support for approximate computing in heterogeneous systems”. I developed a run-time system in C programming language that supports approximate  computations using OpenCL. You can download my thesis here.

Source code will be available in a few weeks.


Energy efficiency is the most important aspect in nowadays systems, ranging from embedded devices to high performance computers. However, the end of Dennard scaling limits expectations for energy efficiency improvements in future devices, despite manufacturing processors in lower geometries and lowering supply voltage. Many recent systems use a wide range of power managing techniques, such as DFS and DVFS, in order to balance the demanding needs for higher performance/throughput with the impact of aggressive power consumption and negative thermal effects. However these techniques have their limitations when it comes to CPU intensive workloads.

Heterogeneous systems appeared as a promising alternative to multicores and multiprocessors. They offer unprecedented performance
and energy efficiency for certain classes of workloads, however at significantly increased development effort: programmers have to spend significant effort reasoning on code mapping and optimization, synchronization, and data transfers among different devices and address
spaces. One contributing factor to the energy footprint of current software is that all parts of the program are considered equally important for the quality of the final result, thus all are executed at full accuracy. Some application domains, such as big-data, video and image processing etc., are amenable to approximations, meaning that some portions of the application can be executed with less accuracy, without having a big impact on the output result.

In this MSc thesis we designed and implemented a runtime system, which serves as the back-end for the compilation and profiling infrastructure of a task-based meta-programming model on top of OpenCL. We give the opportunity to the programmer to provide approximate functions that require less energy and also give her the freedom to express the relative  importance of different computations for the quality of the output, thus facilitating the dynamic exploration of energy / quality trade-offs in a disciplined way. Also we simplify the development of parallel algorithms on heterogeneous systems, relieving the programmer from tasks such as work scheduling and data manipulation across address spaces. We evaluate our approach using a number of real-world applications, from domains such as finance, computer vision, iterative equation solvers and computer simulation.

Our results indicate that significant energy savings can be achieved by combining the execution on heterogeneous systems with approximations, with graceful degradation of output quality. Also, hiding the underlying memory hierarchy from the programmer, performing data dependency analysis and scheduling work transparently, results in faster development without sacrificing the performance of the applications.

Performance and power prediction on heterogeneous systems using statistical methods

I just finished my Diploma Thesis and you can find it here.


Heterogeneous systems provide high computing performance, combining low cost
and low power consumption. These systems include various computational resources
with different architectures, such as CPUs, GPUs, DSPs or FPGAs. It is crucial
to have full knowledge of these architectures, but also of the programming models
used in order to increase the performance on a heterogeneous system.

One way to achieve this goal, is the prediction of the execution time on the different
computational resources, using statistical values which we collect with the use of
hardware counters. The purpose of this thesis is to increase the performance of a
heterogeneous system using the data we collected by training a statistical model
which will predict the execution time. Further goal is to use this prediction model
inside a run-time scheduler which will migrate the running application in order to
decrease the execution time and increase the overall performance.

We used various statistical models, such as linear regression, neural networks and
random forests and we predicted the execution time to Intel CPUs and NVIDIA
GPUs, with different levels of success.

Two player pong game using accelerometers.


This two person project was completed through the course of Embedded Systems at the University of Thessaly, Department of Computer Engineering. In the context of this project we implemented the classic pong game using a Spartan 6 FPGA, and two 3-axis accelerometers. The code is in Verilog and you can find it on github ( link at the bottom of the page ). The project consists two parts. First, the connection with the monitor through the VGA and game logic and the connection of the accelerometers through the SPI interface.

VGA Technology and Implementation

The first part of the project was to connect the FPGA with a monitor using the VGA output. VGA is a video standard mainly used for computer monitors introduced by IBM in 1987.

VGA video is a stream of frames. Each frame is made of horizontal and vertical series of pixels which are transmitted from top to bottom and from left to right, like a beam is traveling through the screen (CRT displays actually used a moving electron beam, but LCD displays have evolved to use the same signal timings as CRT displays). Information is only displayed when the beam is moving forward and not during the time the beam is reset back to the left or top edge of the display.

First we made a VGA controller module that generates the correct signals. The signals that we need to pass to the VGA DAC (Digital to Analog Converter) are:

spartan vga

• Pixel clock
• Vertical Sync
• Horizontal Sync
• 3-bit Red
• 3-bit Green
• 2-bit Blue

Pixel clock defines the time available to display one pixel of information. With different timing values we can achieve several resolutions, such as 800×600 etc. Vertical sync defines the refresh rate of the display and horizontal sync is used to indicate the end of a horizontal line. We use two counters, hcount and vcount that count the pixels in the horizontal and vertical lines. We can determine the location of a pixel in the screen (x,y) by combining these two counters.



Each line of the video begins with an active video region, in which RGB values are output for each pixel in the line. Then a blanking region follows in which a horizontal sync pulse is transmitted in the middle of the blanking interval. The interval before the sync pulse is known as front porch and after the sync pulse back porch.

There are many VGA timing values that can be used, in order to support several resolutions, as we can see in the table below:


For our project we had a resolution of 800×600@72Hz, so we created a 50 MHz clock, from the 100 MHz clock input of the Spartan 6 and the horizontal and the vertical count have a total value of 1039 and 665 respectively. Based on these numbers we calculate the exact time that the hsync and vsync are set active high (both signals on this resolution must be active high) and we connect them to the FPGA pins.

Pong Game

Based on the VGA module we draw on the screen basic shapes such as the paddles and a square dot that represents the ball. The paddle drawing is done at the draw_shape module that given the (x,y) position of the top left pixel, creates a 128×16 pixels rectangle. The same happens with the ball that is 32×32 pixels. Also we have a module that creates the game board; four lines for the perimeter of the screen and one vertical line at the half of the board. Each of these modules, output the pixel locations of each shape.
Ball_movement module takes as input the location of the paddles and the ball and does the necessary calculations for the ball movement. Ball moves at a constant speed of one pixel in x axis and one pixel in y axis. If ball hits the up or down board limit or one of the paddles the trajectory is changed. Also in this module we check if the ball hits the right or left limit, and if yes, a signal is generated to indicate that a player has won a point. Whenever a player wins the score is updated and displayed on the screen. If a player’s score reaches 10 points then the game is over and a message indicating which player has lost is shown. Then the game resets to its initial state. Finally this module outputs the pixel locations of the ball and the paddles and they are driven to the output_pixels module that generates the final output that the monitor will display.

A snippet of the code that checks if the ball has hit the paddle:

// Find collision between ball and the paddles
if ( ((ball_y <= paddle1 + 128) && ( (ball_y >= paddle1 - 32) || ( paddle1 <= 32 && ball_y <= 128 ) )) && ball_x == 18 )
sw_x <= 1;

if ( ((ball_y <= paddle2 + 128) && ((ball_y >= paddle2 - 32) || ( paddle2 <= 32 && ball_y <= 128 ) )) && ball_x == 750 )
sw_x <= 0;

The numbers showing the score are in seven segment display format output and are generated in the draw_score module. Also we implemented a pause game function by activating the switch T5.
Since Nexys 3 board has a reset button that only erases completely any program loaded, we use switch V8 as a reset signal for our project.

3-Axis accelerometers

An accelerometer is an electromechanical device that will measure acceleration forces. These forces may be static, like the constant force of gravity, or they could be dynamic caused by moving the accelerometer. There are different types of accelerometers depending on how they work. Some accelerometers use the piezoelectric effect; they contain microscopic crystal structures that get stressed by accelerative forces, which cause a voltage to be generated. Others implement capacitive sensing, that output a voltage dependent on the distance between two planar surfaces.

In our implementation we used a 3-axis (one axis for each direction) digital accelerometer powered by the analog device ADXL345 and took advantage of the force of gravity on y axis, making the paddles move by tilting the accelerometer right or left. We connected the accelerometers through the SPI interfaces. SPI operates in full duplex mode and uses four signals: Slave select (SS), serial clock (SCLK), serial data out (SDO), to the accelerometer and serial data in (SDI), from the accelerometer. Devices communicate in master/slave mode where master initiates the data frame. Our setup contains two shift registers, one in the master and one in the slave and they are connected as a ring. Data is shifted out with the most significant bit first, while shifting a new least significant bit into the same register.500px-SPI_single_slave.svg500px-SPI_8-bit_circular_transfer.svgWe initialize the transfer with a 5Hz clock and we transmit/receive data at 22.4 kHz rate. The accelerometer is configured for +/- 2g operation. To convert the output to g we have to find the difference between the measured output and the zero-g offset and divide it by the accelerometer’s sensitivity (expressed in counts/g or LSB/g). For our accelerometer in 2g sensitivity with 10-bit digital outputs, the sensitivity is 163 counts/g or LSB/g. The acceleration would be equal to: 𝑎=(Aout−zerog)163 g. We didn’t have to make those calculations for the paddle movement. We just take the accelerometer output and we move the paddles accordingly based on the table below:

spartan vga

Verilog Diagramsspartan vga

Diagram generated by Xilinx ISE:


In game screenshots:


acl3Screen when a player loses

You  can download the code from github here:

Attempting to make fat binaries on Linux

A fat binary is a collection of binaries put in the same executable. Each time the executable is run usually the kernel chooses the right binary, depending the architecture, and executes it. For example we may have in the same binary code for x86 and x86_64 architecture, and the OS is x86. Or even have in the same fat binary code for a CPU and a GPU program. There are some cons and some pros, but i’m not going to explain them now. There is a good article in wikipedia here.

Two or three years ago, a project by the name fatELF started by Ryan C. Gordon. He made a nice implementation, but his kernel patch was rejected so he dropped it.

So when i wanted to make an implementation of fat binaries, i had to find a work around, and not mess with the kernel.

In the following diagram is my implementation:

Let me try to explain it. First we combine all the binaries to one big file, and put as the first binary the so called “elf_header”. The combine function also adds a header to the end of the file, called “FAT_HEADER”. In there, there are information about the binaries that reside into the fat binary, such as the offset of the binary and an id.

So what does our elf_header do? First of all it is a binary made by us, whose work is to scan the end of the file, searching for the header. If the header exists, it starts to extract the info and gives us the option to run the binary we want. In my implementation it just gives the option to the user to select which binary he wants to execute. This can easily be changed to automatically scan the hardware and run the ELF binary and/or also create threads which execute 2 or more binaries at the same time.

You can find my code on github:

I just wanted to share my implementation, and not a full code. As i said the program asks the user on which binary he wants to run, and it does not put the correct id on each binary. So if you want to use it for a more serious job, you can pass the id as an argument, or use a library such as <libelf.h> to scan automatically the header of the ELF binary and extract any info you want. It’s not that hard ;)

For info about running, first you compile the elf_header, and then the main with the combine function. Then you run the generated code and give as arguments the output file, the elf_header and then the binaries you want to combine.


gcc elf_header.c -o elf_header

gcc main.c combine.c -o main

./main output elf_header &lt;arg1&gt; ... &lt;argN&gt;


GPU assisted ELF binary decryption

Usually a malware writer, or a closed source product, use some techniques in order to make the binaries difficult to read. On the one hand, the anti-virus are unable to read the signature of the malware and on the other hand a reverse engineer’s life becomes difficult.
One technique (usually not implemented alone), is to encrypt some portions of the code and decrypt them at runtime, or better decrypt each time the code we want to run and then encrypt it back.
As GPU’s have extremely high computational power, we can have really complex functions for encrypting and decrypting our code. I’ve made a really simple example of a self-decrypting application and i’ll try to explain this step by step.

First of all what is our program going to do? Well it will spawn a shell. The assembly code (we need assembly code so it can be portable) to do that is:

global _shell

xor ecx, ecx
mul ecx
push ecx
push 0x68732f2f
push 0x6e69622f
mov ebx, esp
mov al, 11
int 0x80

You can find codes like this freely available on the internet (this one is written by kernel panik), or you can make your own if you want specific things to be done (or just want to learn). We want our code to be portable, and not containing relative addresses.

So now that we have our assembly code, we compile it to an object file:

 nasm shell.asm -f elf32 -o shell.o 

Our code for the self-decrypting binary is this one, written in C for CUDA:

#include <stdio.h>
#include <sys/mman.h>
#include <cuda.h>

#define len 21

__global__ void decrypt(unsigned char *code){

int indx = threadIdx.x;
code[indx] ^= 12;


extern "C" void _shell();

int main(void){

unsigned char *p = (unsigned char*)_shell;
unsigned char *d_shell,*h_shell;

h_shell = (unsigned char *)malloc(sizeof(char)*len);

int i;
h_shell[i] = *p;
cudaMalloc((void **) &d_shell, sizeof(char)*len);
cudaMemcpy(d_shell, h_shell, sizeof(char)*len, cudaMemcpyHostToDevice);
cudaMemcpy(h_shell, d_shell, sizeof(char)*len, cudaMemcpyDeviceToHost);



Now i have to make some explainations. First of all we have to find the length of the instructions. There are some ways to do this, but there is a project by oblique here: that can do that very easily.

Now, some of you may wonder why i am mmaping and memcpying. Well there are some protections around, that prevent us from writing to some portions of memory such as .text. So we have to load our encrypted code, decrypt it and mmap it to a new portion of memory that can be executed. This is where our flags go. After that we are ready to execute our code.

UPDATE NOTE: Ok i don’t really know why i did this, but some of you may wonder, why don’t you just call mprotect? Well you are right. I updated my code on github and you can check it.

Okay i know, it’s a simple xor decryption with a fixed key, not really encrypted, but this is just a proof of concept. You can have a more complex stream cipher function like RC4 ect. Also you do not need to have a key saved in the binary somehow, but brute force until the code “makes sense”. With such a computation power it is pretty easy.

Now we compile our source code with nvcc and link it:

nvcc -c


gcc shell_spawn.o shell.o -o shell_spawn -L/usr/local/cuda/lib -lcudart

And now we have our executable! But first we have to patch our binary with our encrypted function. The reason why we used stream ciphers is because we don not want to change the size of our function, and make things more complex. One simple way to patch our elf binary is simply by opening it with a hex editor ( i used Bless), and find the code we want to patch. But how? It’s simple:

objdump -d -j .text shell_spawn

and if you search you will see the _shell function:

8048a30:    31 c9                  xor    %ecx,%ecx
8048a32:    f7 e1                  mul    %ecx
8048a34:    51                     push   %ecx
8048a35:    68 2f 2f 73 68         push   $0x68732f2f
8048a3a:    68 2f 62 69 6e         push   $0x6e69622f
8048a3f:    89 e3                  mov    %esp,%ebx
8048a41:    b0 0b                  mov    $0xb,%al
8048a43:    cd 80                  int    $0x80

Now we simply encrypt the op codes. I used xor 12 so my output is this:


We open our hex editor, load our binary and replace our old _shell function with our encrypted one:

After that we save our file and if we execute it we can see that a shell spawns!

If we objdump our file, we can see our function _shell, but this time is doing random stuff ;) :

8048a30:    3d c5 fb ed 5d  cmp  $0x5dedfbc5,%eax
8048a35:    64 23 23        and  %fs:(%ebx),%esp
8048a38:    7f 64           jg 8048a9e <__libc_csu_init+0x4e>
8048a3a:    64 23 6e 65     and %fs:0x65(%esi),%ebp
8048a3e:    62 85 ef bc 07 c1   bound  %eax,-0x3ef84311(%ebp)
8048a44:    8c 90 90 90 90 90    mov    %ss,-0x6f6f6f70(%eax)

You can find my source also on github here:

I want to develop a strong cipher and find a better way to patch my binary, so this is just the idea. If someone wants to go deeper i’d like to hear new ideas. Until then, feel free to comment, point mistakes etc :)


[1]: GPU Assisted malware

[PYTHON]A simple web crawler.

Η ιδέα μου ήρθε καθώς διάβαζα μία συνέντευξη του Dries Buytaert, founder του Drupal. Σε κάποιο σημείο είπε πως είχε φτιάξει ένα web crawler και μαζευε στατιστικά από διάφορες ιστοσελίδες.

So… why not ;)

Με την ευκαιρία είπα να δω λίγο και την python (βασικά είναι το 1ο μου script σε python) οπότε αν έχω κάνει κάποια πατάτα, διορθώστε ελεύθερα.
Η κύρια λειτουργία του είναι να βρίσκει όλα τα links σε μία σελίδα, να τα αποθηκεύει και στην συνέχεια να τα ακολουθεί.

Αρχικά παίρνει τα “feed” urls από ένα αρχείο με όνομα urls (θα βρίσκεται στον ίδιο φάκελο). Σε κάθε νέο host, καλείται η και παίρνουμε κάποιες πληροφορίες.

#!/usr/bin/env python

import urllib2, re, sys, urlparse

#******************************** Options ********************************#
def options():
   print "A simple web crawler by mpekatsoula."
   print "Options:"
   print "-h      : print help."
   print "-n i    : i is the number of \"crawls\" you want to do."
   print "          Enter -1 or leave blank for inf."
   print "-o name : the name of the file you want to store the results."
   print "          If blank the file will be named results."


# Standar values
crawls = -1
results_file = "results"

# Check user input
for arg in sys.argv[1:]:
   if arg.lower()=="-h":
   if arg.lower()=="-n":
      crawls = sys.argv[int(sys.argv[1:].index(arg))+2]
      crawls = int(crawls)
   if arg.lower()=="-o":
      results_file = sys.argv[int(sys.argv[1:].index(arg))+2]
      results_file = str(results_file)

# Open the file with the 'feed' urls
feed_urls = open('urls','r')

# Create the file to store the results
results = open(results_file,'a')

# Array that holds the urls to crawl/urls that are crawled/hosts that info has gathered
nexttocrawl = set([])
crawled_urls = set([])
gathered_info = set([])

# We need to have the expressions of a url.
# So we make an object that holds these expressions
# More info for regular expressions in python here:
expressions = re.compile('<a\s*href=[\'|"](.*?)[\'"].*?>')

# Add the feed urls from the file to the array
for line in feed_urls:

# Simple counter

while i!=crawls:

      # Get next url and print it. If the array is empty, exit.
      crawling_url = nexttocrawl.pop()
      print "[*] Crawling...: " + crawling_url
   except KeyError:

   # "Break" the url to components
   parsed_url = urlparse.urlparse(crawling_url)
   # Open the url
      url  = urllib2.urlopen(crawling_url)

   # Read the url
   url_message =
   # Find the new urls
   gen_urls = expressions.findall(url_message)

   # Store the crawled urls

   # Add the new urls to array
   for link in (gen_urls.pop() for _ in xrange(len(gen_urls))):
      if link.startswith('/'):
         link = 'http://' + parsed_url[1] + link
      elif link.startswith('#'):
         link = 'http://' + parsed_url[1] + parsed_url[2].rstrip("\n") + link
      elif not link.startswith('http'):
         link = 'http://' + parsed_url[1] + '/' + link
      if link not in crawled_urls:

   if parsed_url[1] not in gathered_info:
      # Collect the info
      collected_info = str(
      # Here we store the results ;)

#close the files & exit

Με βάση αυτό μπορούμε να κάνουμε και άλλα πράγματα, όπως πχ να βρούμε τι CMS μπορεί να τρέχει ο host, κάποια παλιά έκδοση του apache που είναι vulnerable και ότι άλλο βάλει ο νους μας ;)
Είναι κάτι πολύ απλό, αλλά αρκετά ενδιαφέρον (at least κατ’εμέ :P).

Running example:

mpekatsoula@mpekatsospito:~/Desktop$ python -o test.out -n 10
[*] Crawling...:

[*] Crawling...:
[*] Crawling...:
[*] Crawling...:
[*] Crawling...:
[*] Crawling...:
[*] Crawling...:
[*] Crawling...:
[*] Crawling...:
[*] Crawling...:


Server: nginx
Date: Sat, 06 Nov 2010 15:28:36 GMT
Content-Type: text/html; charset=UTF-8
Transfer-Encoding: chunked
Connection: close
Vary: Cookie
X-hacker: If you're reading this, you should visit and apply to join the fun, mention this header.
Link: ; rel=shortlink
Last-Modified: Sat, 06 Nov 2010 15:28:36 +0000
Cache-Control: max-age=300, must-revalidate
X-nananana: Batcache
Date: Sat, 06 Nov 2010 15:28:37 GMT
Server: Apache/2.2.9 (Ubuntu) Phusion_Passenger/3.0.0
Vary: Host,Accept-Encoding
Last-Modified: Sat, 06 Nov 2010 15:27:45 GMT
ETag: "b43a2-60d-4946408601e40"
Accept-Ranges: bytes
Content-Length: 1549
Connection: close
Content-Type: text/html
Date: Sat, 06 Nov 2010 15:28:21 GMT
Server: Apache
Last-Modified: Mon, 27 Sep 2010 14:15:24 GMT
ETag: "4a1247-1a8f7-4913e5bfab700;48ced8affcb80"
Accept-Ranges: bytes
Content-Length: 108791
Connection: close
Content-Type: text/html; charset=UTF-8
Date: Sat, 06 Nov 2010 15:28:42 GMT
Server: Apache/2.2.11 (Ubuntu) mod_apreq2-20051231/2.6.0 mod_perl/2.0.4 Perl/v5.10.0
Vary: Accept-Encoding
Connection: close
Transfer-Encoding: chunked
Content-Type: text/html; charset=utf-8
Date: Sat, 06 Nov 2010 15:28:42 GMT
Server: Apache
Last-Modified: Sat, 06 Nov 2010 14:39:02 GMT
ETag: "582c027-332f-494635a26ad80"
Accept-Ranges: bytes
Content-Length: 13103
Cache-Control: max-age=300, must-revalidate
Expires: Sat, 06 Nov 2010 15:33:42 GMT
Vary: Accept-Encoding
Connection: close
Content-Type: text/html; charset=UTF-8
Content-Length: 28900
Content-Type: text/html
Last-Modified: Mon, 15 Oct 2007 08:29:14 GMT
Accept-Ranges: bytes
ETag: "0a9d8775fc81:8098"
Server: Microsoft-IIS/6.0
IISExport: This web site was exported using IIS Export v4.2
Date: Sat, 06 Nov 2010 15:28:40 GMT
Connection: close
Cache-Control: no-cache
Pragma: no-cache
Content-Length: 155243
Content-Type: text/html; charset=utf-8
Expires: -1
Server: Microsoft-IIS/6.0
x-server-id: 115
X-UA-Compatible: IE=7
X-Powered-By: ASP.NET
X-AspNet-Version: 2.0.50727
GA: 0
NEG-Created: 11/6/2010 8:28:45 AM
Set-Cookie: NV%5FDVINFO=#5%7b%22Sites%22%3a%7b%22USA%22%3a%7b%22Values%22%3a%7b%22w19%22%3a%22Y%22%7d%2c%22Exp%22%3a%221289147325%22%7d%7d%7d;; path=/
Set-Cookie: NV%5FPRDLIST=#5%7b%22Sites%22%3a%7b%22USA%22%3a%7b%22Values%22%3a%7b%22wf%22%3a%22N82E16817371005%22%7d%2c%22Exp%22%3a%221375457325%22%7d%7d%7d;; expires=Fri, 02-Aug-2013 15:28:45 GMT; path=/
Set-Cookie: NV%5FCONFIGURATION=#5%7b%22Sites%22%3a%7b%22USA%22%3a%7b%22Values%22%3a%7b%22wd%22%3a%221%22%2c%22w39%22%3a%227657%22%7d%2c%22Exp%22%3a%221375457325%22%7d%7d%7d;; expires=Fri, 02-Aug-2013 15:28:45 GMT; path=/
Date: Sat, 06 Nov 2010 15:28:45 GMT
Set-Cookie: NSC_xxx.ofxfhh.dpn-WJQ=ffffffffaf183f1e45525d5f4f58455e445a4a423660;expires=Sat, 06-Nov-2010 16:21:52 GMT;path=/

Σημείωση: Αν δεν δώσουμε πόσα crawls θα κάνει, κατά 99% δεν πρόκειτε να σταματήσει ποτέ. Οπότε καλό θα ήταν να βάζουμε ένα πεπερασμένο πλήθος.

Linux memory management 32-bit x86

Linux memory management 32-bit x86

Η μνήμη RAM αποτελεί έναν  απο τους σημαντικότερους πόρους του συστήματος. Αν και τα σημερινά μεγέθη θα φαίνονταν τεράστια 20 χρόνια πριν, τα προγράμματα τείνουν να καταλαμβάνουν όλο και περισσότερο χώρο. Το ιδανικό σενάριο θα ήταν, για κάθε πρόγραμμα να υπάρχει η δική του ιδιωτική μνήμη, κάτι το οποίο (προς το παρών;) δεν είναι εφικτό. Οπότε κάπως πρέπει να χωρίσουμε την πίτα ώστε κανείς να μην μείνει παραπονεμένος. Εδώ έρχεται το λειτουργικό σύστημα το οποίο κάνει αυτή την δουλεία για εμάς. Θα δούμε πως γίνεται αυτό σε ένα σύστημα Linux 32-bit x86.

Κάθε διεργασία όταν φορτώνεται στην μνήμη, μέσω του λειτουργικού συστήματος, εκτελείται σε ένα πλήρως αποκομμένο περιβάλλον: δεν γνωρίζει   την ύπαρξη άλλων διεργασιών, και το μόνο που βλέπει, είναι πως όλη η μνήμη της ανήκει. Ο χώρος αυτός ονομάζεται χώρος εικονικών διευθύνσεων  (4Gb σε συστήματα 32-bit) και αποτελείται από τρία τμήματα: τμήμα κώδικα (code segment), τμήμα δεδομένων (data segmanet) και τμήμα στοίβας (stack segment).

[:code/text segment:]
Το code segment ή αλλιώς text segment, περιέχει τις εντολές μηχανής που παράχθηκαν από τον μεταγλωτιστή και τον συμβολομεταφραστή κατά την μετάφραση ενός προγράμματος, και αποτελούν τον εκτελέσιμο κώδικα του προγράμματος. Το τμήμα αυτό είναι read only, συνεπώς και το μέγεθός του σταθερό.

[:data segment:]
Το data segment παρέχει χώρο για την αποθήκευση των δεδομένων του προγράμματος. Χωρίζεται σε τρία μέρη: Initialized data (περιοχή δεδομένων με αρχικές τιμές), BSS (Block Started by Symbol) και την heap.

Initialized data: Ο χώρος αυτός περιέχει μεταβλητές και σταθερές μεταγλωττιστή οι οποίες έχουν αρχική τιμή όταν ξεκινάει το πρόγραμμα.

BSS: Οι global και static μεταβλητές που δεν έχουν αρχικοποιηθεί, εισάγωνται στο τμήμα BSS και αρχικοποιούνται σε μηδέν. Είναι ενδιαφέρον να αναφέρω πως αν ορίσουμε ένα πίνακα πχ static char buff[4048] ο μεταγλωτιστής τοποθετεί μία κεφαλίδα (ένα header) αμέσως μετά τον κώδικα και τα αρχικοποιημένα δεδομένα, η οποία λέει στο σύστημα πόσος χώρος πρέπει να εκχωριθεί. Στην περίπτωσή μας 4Kb. Με αυτό τον τρόπο αποφεύγεται η αποθήκευση 4Kb με μηδενικά στην μνήμη.

Heap: Σε αντίθεση με το text segment, το data segment μπορεί να αλλάξει μέγεθος. Αυτό γιατί τα οι τιμές των μεταβλητών τροποποιούνται συνεχώς και τα προγράμματα θέλουν να εκχωρίσουν δυναμικά μνήμη κατά την εκτέλεσή τους (πχ κλήση malloc). Η heap συνήθως αυξάνει “προς τα πάνω”, δηλαδή η μνήμη των δεδομένων που προσθετονται στην heap έχουν αριθμιτική τιμή μεγαλύτερη από τα προηγούμενα δεδομένα.

[:stack segment:]
Τέλος, στο stack segment αποθηκεύονται όλες οι τοπικές μεταβλητές. H στοίβα  μεγαλώνει “προς τα κάτω” (αντίθετα με την heap) και συνήθως ξεκινάει από την κορυφή των εικονικών διευθύνσεων -0xC0000000- . Αρχικά το stack segment δεν είναι κενό. Περιέχει όλες τις μεταβλητές κελύφους και τις εντολές που δόθηκαν στο κέλυφος και ξεκίνησε το πρόγραμμα. Πχ όταν δίνουμε mkdir test στην στοίβα υπάρχει η συμβολοσειρά “mkdir test”.

Στον εικονικό χώρο διευθύνσεων κάθε διεργασίας υπάρχει ένα σταθερά δεσμευμένο κομμάτι από τον πυρήνα -kernel space- (συγκεκριμένα ένα κομμάτι μεγέθους 1Gb).  Ο kernel space είναι μαρκαρισμένος ως privilaged code (ring0), αν δηλαδή κάποιο πρόγραμμα τον αγγιξει έχουμε page fault. Ο κώδικας του πυρήνα είναι πάντα παρών στην φυσική μνήμη του συστήματος, αντίθετα με τον κώδικα των διεργασιών ο οποίος φορτώνεται στην μνήμη όταν συμβαίνει μια εναλλαγή διεργασιών, και  δεν είναι ορατός σε επίπεδο χρήστη παρα μόνο όταν η διεργασία “παγιδευτεί” στον πυρήνα.

Ακόμα, υπάρχει η δυνατότητα χαρτογράφησης ενός αρχείου (πχ κοινόχρηστες βιβλιοθήκες) στον χώρο διευθύνσεων της διεργασίας ώστε να μπορεί να διαβαστεί και να γράφεται σαν να ήταν byte στην μνήμη. Αυτό διευκολύνει πολύ την τυχαία πρόσβαση σε αυτό, αντίθετα με τις κλήσεις συστήματος.

Όλα αυτά μπορούμε να τα δούμε πρακτικά σε ένα απλό προγραμμα. Έστω το memory.c

static int a = 1;static char buffer[4048];
int main(void)
int z = 0;
mpekatsoula@mpekatsospito:~/Desktop$ ls -l memory-rwxr-xr-x 1 mpekatsoula mpekatsoula 7149 2010-10-17 15:44 memorympekatsoula@mpekatsospito:~/Desktop$ size --format=SysV memorymemory:
section        size        addr
.interp         19   134512948
.note.ABI-tag          32   134512968     36   134513000
.hash                  36   134513036
.gnu.hash              32   134513072
.dynsym                64   134513104
.dynstr                69   134513168
.gnu.version            8   134513238
.gnu.version_r         32   134513248
.rel.dyn                8   134513280
.rel.plt               16   134513288
.init                  48   134513304
.plt                   48   134513352
.text                 364   134513408
.fini                  28   134513772
.rodata                 8   134513800
.eh_frame               4   134513808
.ctors                  8   134520588
.dtors                  8   134520596
.jcr                    4   134520604
.dynamic              208   134520608
.got                    4   134520816
.got.plt               20   134520820
.data                  12   134520840
.bss                 4080   134520864
.comment               35         0
Total                5231

Αρχικά βλέπουμε το πρόγραμμα το οποίο καταλαμβάνει χώρο 7149bytes στον δίσκο, αλλά τελικά φορτώνονται 5231. Αυτός ο extra χώρος καταλαμβάνεται από τις ονομασίες των μεταβλητών και των συναρτήσεων που έχει δώσει ο προγραμματιστής, και από πληροφορίες σχετικά με  κοινόχρηστες βιβλιοθήκες που μπορεί να χρησιμοποιεί το πρόγραμμα.
Ο πυρήνας κάνει randomize τις περιοχές της stack, της heap και του memory mapping segment(όσο αυτό είναι εφικτό στον χώρο των 32-bit διευθύνσεων), προσθέτοντας ένα random offset στην αρχική τους διεύθυνση, για κάθε διεργασία ξεχωριστά (για αυξημένη προστασία και ασφάλεια). Ο κώδικας που κάνει randomize την stack, την heap και το memory mapping segment είναι ο εξής:

Stack (/fs/binfmt_elf.c)

static unsigned long randomize_stack_top(unsigned long stack_top) {
unsigned int random_variable = 0;
if ((current->flags & PF_RANDOMIZE) && !(current->personality & ADDR_NO_RANDOMIZE)) {                 random_variable = get_random_int() & STACK_RND_MASK;
random_variable <<= PAGE_SHIFT;
return PAGE_ALIGN(stack_top) + random_variable;
return PAGE_ALIGN(stack_top) - random_variable;

Heap (/arch/x86/kernel/process_32.c)

unsigned long arch_randomize_brk(struct mm_struct *mm){
unsigned long range_end = mm->brk + 0x02000000;
return randomize_range(mm->brk, range_end, 0) ? : mm->brk;

Memory mapping segment (/arch/x86/mm/mmap.c)

static unsigned long mmap_base(void){
unsigned long gap = current->signal->rlim[RLIMIT_STACK].rlim_cur;
 if (gap < MIN_GAP)
gap = MIN_GAP;
else if (gap > MAX_GAP)
gap = MAX_GAP;
return PAGE_ALIGN(TASK_SIZE - gap - mmap_rnd());

Είναι λογικό να αναρωτηθεί κανείς τι συμβαίνει στην περίπτωση που η stack μεγαλώσει πάρα πολύ και ξεπεράσει το stack limit. Αν γίνει αυτό, έχουμε page fault και καλείτε η
expand_stack() (/mm/mmap.c)

int expand_stack(struct vm_area_struct *vma, unsigned long address){
return expand_downwards(vma, address);

η οποία με την σειρά της καλέι την
acct_stack_growth() (/mm/mmap.c)

static int acct_stack_growth(struct vm_area_struct * vma, unsigned long size, unsigned long grow)
struct mm_struct *mm = vma->vm_mm;
struct rlimit *rlim = current->signal->rlim;
unsigned long new_start;

 /* address space limit tests */
if (!may_expand_vm(mm, grow))
return -ENOMEM;

 /* Stack limit test */
if (size > rlim[RLIMIT_STACK].rlim_cur)
return -ENOMEM;

 /* mlock limit tests */
if (vma->vm_flags & VM_LOCKED) {
unsigned long locked;
unsigned long limit;
locked = mm->locked_vm + grow;
limit = rlim[RLIMIT_MEMLOCK].rlim_cur >> PAGE_SHIFT;
if (locked > limit && !capable(CAP_IPC_LOCK))
return -ENOMEM;

 /* Check to ensure the stack will not grow into a hugetlb-only region */
new_start = (vma->vm_flags & VM_GROWSUP) ? vma->vm_start :  vma->vm_end - size;
if (is_hugepage_only_range(vma->vm_mm, new_start, size))
return -EFAULT;

 /*         * Overcommit..  This must be the final test, as it will         * update security statistics.         */
if (security_vm_enough_memory(grow))
return -ENOMEM;
 /* Ok, everything looks good - let it rip */
mm->total_vm += grow;
if (vma->vm_flags & VM_LOCKED)
mm->locked_vm += grow;

vm_stat_account(mm, vma->vm_flags, vma->vm_file, grow);
return 0;

για να τσεκάρει αν μπορεί να μεγαλώσει η stack. Αν έχει φτάσει στο μέγιστο μέγεθος και προσπαθήσει να μεγαλώσει τότε έχουμε stack overflow και επομένως Segmentation Fault.
Εδώ βλέπουμε πως δύο διεργασίες μπορεί να βρίσκονται στην μνήμη (σκεφτείτε το για πολλές):

[.:Κλήσεις Συστήματος:.]
Τα περισσότερα συστήματα Linux διαθέτουν κλήσεις συστήματος για την διαχείρηση μνήμης. Οι πιο συνηθισμένες είναι οι εξής:

Καθορίζει το μέγεθος του τμήματος δεδομένων(data segment) της διεργασίας, αλλάζοντας την θέση της program break, η οποία δηλώνει σε ποιο σημείο τελειώνει το data segment. Αν αυξήσουμε την program break εκχωρούμε περισσότερη μνήμη στην διεργασία και αντίστοιχα αν την μειώσουμε, αφαιρούμε.

 #include <unistd.h>
 int brk(void *addr);


Η mmap χαρτογραφεί ένα αρχείο στην μνήμη. Η αρχική διεύθυνση του αρχείο προσδιορίζεται στην  addr, η οποία αν είναι  0 τότε το σύστημα προσδιορίζει μόνο του την διεύθυνση. Η παράμετρος len προσδιορίζει πόσα byte πρέπει να χαρτογραφηθούν, η prot  την προστασία, η flags αν το αρχείο θα έιναι ιδιωτικό η κοινόχρηστο και τέλος η offset την θέση του αρχείου όπου θα ξεκινήσει η χαρτογράφηση.

#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

Αντίθετα με την mmap η munmap αποχαρτογραφεί ένα αρχείο.

#include   <sys/mman.h>
int munmap(void *addr, size_t length);

Για παράδειγμα ας δουμε τι γίνεται όταν καλούμε την malloc. Η malloc παίρνει ως όρισμα το μέγεθος της μνήμης που θέλουμε να δεσμεύσουμε και αν δεν υπάρχει ήδη αρκετός χώρος στην heap, προσπαθεί να δεσμεύσει μνήμη μέσω της κλήσης sbrk (αυξάνει το data segment κατα increment bytes). Ας δούμε ένα προγραμματάκι, έστω το..:


#include <stdio.h>
#include <sys/types.h>
int *x;
 printf("sbrk(0) before malloc(4): 0x%x\n", sbrk(0)); //τιμή της program break πριν την κλήση τρης malloc
x = (int *) malloc(4);
printf("sbrk(0) after `x = (int *) malloc(4)': 0x%x\n", sbrk(0)); //τιμή της program break μετά την κλήση τρης malloc
printf("x = 0x%x\n", x); //διεύθυνση της x}[/code] 
mpekatsoula@mpekatsospito:~/Desktop$ ./memory2
sbrk(0) before malloc(4): 0x94e4000
sbrk(0) after `x = (int *) malloc(4)': 0x9505000x = 0x94e4008

Σημείωση: αν το όρισμα της sbrk είναι 0, μας επιστρέφει την τρέχουσα τιμή της program break.

[.:Υλοποίηση της διαχείρησης μνήμης στον πυρήνα:.]
Αφού είδαμε όλα τα παραπάνω, το πως βλέπει μία διεργασία την μνήμη, πως δεσμεύει περισσότερη μνήμη κλπ, ήρθε η ώρα να περάσουμε στο επίπεδο του πυρήνα. Πως διαχειρίζετε δηλαδή την φυσική μνήμη. Πριν ξεκινήσω, να τονίσω πως ο πυρήνας βρίσκεται πάντα στην μνήμη "καρφιτσωμένος" (pinned), και κανένα τμήμα του δεν αφαιρείται ΠΟΤΕ από την μνήμη.

Όπως είπαμε, ο πυρήνας χωρίζει τα 4Gb του εικονικού χώρου διευθύνσεων σε 1Gb για αυτόν και 3Gb για την διεργασία. Δεν σημαίνει πως ο πυρήνας χρειάζεται τόση μνήμη για αυτόν, αλλά με αυτό τον τρόπο μπορεί να διαχειρίζεται όλη την φυσική μνήμη. Ο πυρήνας μπορεί να διευθετίσει μόνο 1Gb  μνήμης, δηλαδή μέγιστο 1Gb φυσικής μνήμης (γιατί χαρτογραφεί απευθείας όλο το τμήμα εικονικών του διευθύνσεων στην φυσική μνήμη). Όμως υπάρχουν λύσεις για την χρησιμοποίηση έως και 64Gb μνήμης. Αναλυτικότερα, η φυσική μνήμη διακρίνει τρεις ζώνες:

ZONE_DMA:Χρησιμοποιείται από μερικές συσκευές (πχ [url=]ISA cards[/url]) για μεταφορά δεδομένων, και βρίσκεται στο χαμηλότερο μέρος της φυσικής μνήμης , μεταξύ 0-16Mb

ZONE_NORMAL:Τα 16 έως τα  896Mb αποτελούν την ZONE_NORMAL. Περιέχει δεδομένα τα οποία ο πυρήνας χρειάζεται συχνά να προσπελάζει.Η ZONE_NORMAL μαζί με την ZONE_DMA είναι οι μόνες που μπορούν να χαρτογραφηθούν απευθείας στον πυρήνα.

ZONE_HIGHMEM:Η ζώνη HIGHMEM βρίσκεται πάνω από τα 896Mb.
Μία περιοχή της μνήμης του πυρήνα(128Μb), χρησιμοποιείται για να αποθηκευθούν δομές του πυρήνα, πληροφορίες για τον πίνακα περιγραφέα σελίδας (mem_map) και πίνακες σελίδων. Τα 128Mb αυτά, δεν χαρτογραφούνται στην μνήμη, οπότε μας μένουν 896Mb για την ZONE_NORMAL.

Για να χρησιμοποιήσει λοιπόν ο πυρήνας μνήμη άνω του 1Gb,χαρτογραφεί σελίδες από την ΖΟΝΕ_HIGHMEM στην ZONE_NORMAL. Χαρτογραφεί δηλαδή σελίδες στον εικονικό χώρο διευθύνσεων του πυρήνα. Αυτό γίνεται με τις συναρτήσεις kmap(), kunmap(), kmap_atomic() και kunmap_atomic().

H συνάρτηση kmap σου δίνει μόνιμη χαρτογράφηση ακόμα και αν μεταφερθείς σε άλλη CPU (χρσιμοποιεί global lock). Δεν συνηθίζεται όμως, λόγο του ότι σε συστήματα SMP, μπορεί να προκαλέσει bottleneck. Έτσι συνηθως χρησιμοποιούνται οι  kmap_atomic() και kunmap_atomic().

Όπως ανέφερα και πριν, ο πυρήνας διατηρεί ένα πίνακα περιγραφέων σελίδων (page descriptors), ή αλλιώς mem_map. Κάθε page descriptor έχει ένα δείκτη προς το χώρο διευθύνσεων στον οποίο ανήκει, και στην περίπτωση που η σελίδα είναι ελεύθερη, ένα ζεύγος δεικτών επιτρέπει την δημιουργία διπλά συνδεδεμένων λιστών με άλλους page descriptors έτσι ώστε να διατηρούνται μαζί όλα τα πλαίσια των ελεύθερων σελίδων. Το μέγεθος του mem_map συνήθως καταλαμβάνει λιγότερο από 1% της φυσικής μνήμης.
Ακόμα ο πυρήνας διατηρεί και ένα περιγραφέα ζώνης (zone descriptor), ο οποίο περιέχει πληροφορίες για την σωστή αξιοποίηση την μνήμης μέσα σε κάθε ζώνη. Δηλαδή πληροφορίες όπως ο αριθμός ενεργών ή ανενεργών σελίδων κλπ. Τέλος υπάρχει και ένας περιγραφέας κόμβου οποίος περιέχει πληροφορίες σχετικά με τη χρήση της μνήμης.

Η ιδέα πίσω από την σελιδοποίηση στο Linux  είναι η εξής: Μία διεργασία δεν χρειάζεται να έιναι ολόκληρη στην μνήμη για να εκτελεστεί. Αρκεί να βρίσκονται οι πίνακες σελίδων της και η user structure. Αν αυτά μεταφερθούν στην μνήμη, η διεργασία θεωρείται ότι βρίσκεται στην μνήμη και μπορεί να χρονοπρογραμματιστεί η εκτέλεσή της. Η σελιδοποίηση υλοποιείται εν μέρη από τον πυρήνα και εν μέρη από μία διεργασία, την page daemon,η οποία όταν αφυπνίζεται ελένχει αν υπάρχει κάποια διεργασία προς εκτέλεση.

Το Linux χρησιμοποιεί μια μέθοδο σελιδοποίησης τεσσάρων επιπέδων (από τον 2.6.11). Οι πίνακες σελίδων ονομάζονται:
Καθολικός κατάλογος σελίδων - Page Global DIr
Άνω κατάλογος σελίδων - Page Upper Dir
Μεσαίος κατάλογος σελίδων - Page Middle Dir
Πίνακας σελίδων σελίδων - Page table

Ο καθολικός κατάλογος σελίδων περιέχει αρκετές διευθύνσεις του άνω καταλόγου, ο άνω του μεσαίου κοκ.(πιστεύω η εκόνα αυτή είναι αρκετά χαρακτηρηστική και δεν χρειάστηκε να κάνω κάποια δικιά μου)

Έτσι αν θέλουμε να μεταφράσουμε μία λογική διεύθυνση σε μία φυσική, πρέπει πρώτα να βρούμε την λεγόμενη linear address (γραμμική διεύθυνση(;)). Την linear address την βρίσκουμε μέσω της MMU(Memory Management Unit - Μονάδα Διαχείρισης Μνήμης). Από εκεί, η linear address μεταφράζεται στην physical address μέσω του Paging Unit. Επιπλέον αν το σύστημα δεν είναι σε κατάσταση PAE, δύο επίπεδα σελίδων είναι αρκετά. Έτσι απενεργοποιείται ο άνω κατάλογος και ο μεσαίος κατάλογος (απλά λέμε ότι περέχουν 0bits).Τέλος τα τμήματα κώδικα και τα αρχεία που χαρτογραφούνται στην μνήμη, σελιδοποοιούνται και στον δίσκο. Ότιδήποτε άλλο, σελιδοποιείται και στην περιοχή εναλλαγής, κοινώς swap area.

Γενικά το όλο θεμα είναι τεράστιο για να καληφθεί σε 5-6 σελίδες (ολόκληρα βιβλία υπάρχουν). Πιστεύω ότι κάποιος θα πάρει μία γενική ιδέα και φυσικά όποιον τον ενδιαφέρει περισσότερο μπορεί να ακολουθήσει τα λινκς από κάτω. Προσωπικά ήθελα μία όσο το δυνατόν καλύτερη άποψη για το πως διαχειρίζεται το Linux την μνήμη (κυρίως για προγραμματισμό), και παράλληλα έιπα να γράψω αυτό το αρθράκι. That's all ;)

[1]: Modern Operating Systems, 3rd Edition by Andrew S. Tanenbaum
[2]: Understanding the Linux Kernel By Daniel Pierre Bovet, Marco Cesatí
[3]: man pages
[4]: by Gustavo Duarte
[9]: by Arnold Robbins