EGLUG Systems Development Course

You can find the course details here

Here is the outline for the course.

EGLUG Systems Development Course (ESDC)
 Amr Ali
 062810

Copyright Notice

	Copyright (C) 2010 by Amr Ali
	amr-ali.co.cc

	All rights reserved.

	This work is licensed under the Creative Commons
	Attribution-Noncommercial-Share Alike 3.0 Unported License.
	To view a copy of this license visit

	or send a letter to Creative Commons, 171 Second Street,
	Suite 300, San Francisco, California, 94105, USA.

Abstract

	This course is only a premier to the system development field
	and should not be treated as a reference or base a study of
	sorts upon it. It only teaches the principles of system design
	and development for developers that invested quite an effort into
	programming and willing to go further into the realm and valleys of
	the hacker.

Quotes

	"Software Engineering might be science; but that's not what I do.
	I'm a hacker, not an engineer." - Jamie Zawinski

	"I decry the current tendency to seek patents on algorithms.
	There are better ways to earn a living than to prevent others
	from making use of one's contributions to computer science."
	- Donald E. Knuth

	"Science is what we understand well enough to explain to a computer.
	Art is everything else we do." - Donald E. Knuth

	"Always program as if the person who will be maintaining your program
	is a violent psychopath that knows where you live." - Martin Golding

	"Coding styles are like assholes, everyone has one and
	no one likes anyone else's." - Eric Warmenhoven

Jokes

	"Computers are like air conditioners: they stop working when you open
	WINDOWS."

	"unzip; strip; touch; finger; mount; fsck; more; yes; unmount; sleep"
	- My daily UNIX command list.

	"The Internet: where men are men, women are men,
	and children are FBI agents."

	"One of the main causes of the fall of the Roman Empire was that,
	lacking zero, they had no way to indicate successful termination
	of their C programs." - Robert Firth

	"UNIX is user-friendly. It's just very selective about
	who its friends are."

	"Microsoft is not the answer,
	Microsoft is the question, NO is the answer." - Erik Naggum

	"I would love to change the world, but they won't give me
	the source code" - Amr Ali? :-)

My Personal Favorite

	"There are 10 kinds of people in this world, those that understand
	trinary, those that don't, and those that confuse it with binary."
	- Whoever understands that joke will do good in this course :-)

Table Of Contents

	1. Introduction
	1.1. Summary
	1.2. Prerequisites
	1.2.1. Programming Experience
	1.2.2. Field Of Experience
	1.2.3. Programming Languages
	1.2.4. Depth Of System Knowledge
	1.2.5. CPU Designs And Architectures
	1.2.6. Mentality
	2. UNIX Based Systems Communications
	2.1. User Space To User Space
	2.2. User Space To Kernel Space
	2.3. Kernel Space To Kernel Space
	2.4. InterProcess Communication
	2.4.1. Types Of Communication
	2.4.1.1. Signals
	2.4.1.2. Pipes
	2.4.1.3. Sockets
	2.4.1.4. Message Queues
	2.4.1.5. Semaphores
	2.4.1.6. SpinLocks
	2.4.1.7. Mutexes
	2.4.1.8. Shared Memory
	2.4.2. Synchronization
	2.4.3. Common Problems
	3. System Application Design
	3.1. Strategy
	3.2. Daemons
	3.3. Logs
	3.4. Storage
	3.5. Debugging
	4. Case Studies
	4.1. Case 1
	4.2. Case 2
	4.3. Case 3
	4.4. Final Project
	5. Author
	5.1. Background
	5.2. Contact Information
	6. Thanks

1. Introduction

1.1. Summary

	ESDC is for whoever wants to develop system level applications and
	solutions that are specifically designed for UNIX based systems.
	This is an open ended course which entitles the expansion of the above
	TOC at any time without prior notice to students.

1.2. Prerequisites

1.2.1. Programming Experience

	Whoever applies to this course should had quite an experience with
	different programming languages to have the mature mentality required
	for this course. Basically it is a "MUST" that a student had at least
	written one thousand (1000) line of code in any language.

1.2.2. Field Of Experience

	It is not required that students had done any system development
	prior to this course but it is rather preferred that they have
	done at least readings on the topic or have a general idea what
	the hell we are talking about.

1.2.3. Programming Languages

	It is a "MUST" that a student is very fluent in C as a language
	but not necessarily in its libraries, however general knowledge
	of them is preferred and knowing how to use the man pages is
	a must along with knowing the meaning of "RTFM".

	ASM is not required at all, but knowing the different syntaxes
	is preferred and maybe little to how ASM as language works.

	BASH, I know I'm stating the obvious, but I don't either want to
	be fronted with questions about administering UNIX or how to build
	a Makefile, so BASH/M4 are best to be known.

1.2.4. Depth Of System Knowledge

	This course is built around UNIX based systems, mainly Linux,
	so it is a "MUST" to know your way around that system and no,
	this is not "how to make windows drivers" course.

1.2.5. CPU Designs And Architectures

	It is strongly preferred that a student knows about the different
	CPU architectures and designs and how they contribute to system
	development, that's why some ASM would be preferred in general.

	Just know this, SMP is trouble, lock your code good, or keep debugging
	day and night until you bleed out of your eye sockets.

1.2.6. Mentality

	You should have the mentality of a hunter, you never quite, and
	you never surrender to failure, you keep trying and trying.
	Always alert to the tiniest details and ready to adapt new
	tactics and techniques quickly, which requires dedication
	and effort.

2. UNIX Based Systems Communications

2.1. User Space To User Space

	First let me introduce you to what is user space,
	user space is whatever made by mere humans and runs
	in the background (ex. background process, or daemon)
	and of course cannot communicate directly with the
	physical layer of your computer.

	User space communications mainly deals within the area
	of IPC (InterProcess Communication), like shared memory
	segments, message queues, and named/unnamed pipes.

	Forget the ideas you had to have a certain file that
	some process writes to and another reads from, I had these
	ideas when I was 12, you are an adult use IPC.

	Apparently main purposes of IPC is to make two processes
	run totally independently of each other and communicate in
	an efficient way to pass certain information to each other
	back and forth.

2.2. User Space To Kernel Space

	"Kernel: is the central component of most computer operating
	systems; it is a bridge between applications and the actual
	data processing done at the hardware level." - Wikipedia

	So let me put this in more simple words, the kernel is basically
	the guy that facilitates the usage of your hardware, bluntly,
	without a kernel and you wanted to print out "hello." to your screen
	you will have to write the code that communicates to your PCI bus and
	to your video card, with all the pedantic necessary op codes and flags
	to make this 6 characters word appear to your dead cold black screen.

	But if we have our kernel how we communicate to it? can we include just
	a couple of C header files and it will contain all the above mentioned
	code? the answer is of course YES. Thats the main purpose of the
	standard C library or `stdlib', which simply is an abstraction to all
	the assembly (yes ASM, you can't talk to the kernel directly in C)
	required to communicate back and forth with your virtual/real hardware.

	However we still want to communicate directly with our kernel, isn't there
	any other possible ways except for ASM? of course there is other ways
	you silly sally, which are still another abstraction over the ASM
	interfaces the kernel provides, like IOCTL, ProcFS (Linux only),
	NetLink, and System Calls (SysCalls) all these are called IPC, but
	I don't like calling them that, so I'll call them
	ISC (InterSpace Communication).

2.3. Kernel Space To Kernel Space

	Lets imagine that you got so elite to the point that you created two
	kernel modules, and you would like to exchange information between
	them. The thing you must understand about the Linux kernel is that
	it ends up compiled to a single file, everything is shared inside the
	kernel, so you declare a certain function it becomes exported to what
	is known to be KST (Kernel Symbols Table), this table will contain
	all the functions and variables you've exported, so other parts of
	the kernel can call them.

	As a side note, as I want to impose the kernel space image upon you,
	there is no floating point arithmetics in kernel space, just because
	its not worth it. That can tell you how pedantic the process of code
	getting selected to go inside the main kernel repo is, so don't expect
	any kind of functions/libraries you are used to in user space to exist
	in kernel space.

2.4. InterProcess Communication

2.4.1. Types Of Communication

	There are mainly 8 types of communication, three of which are locking
	mechanisms, Signals, Pipes, Sockets, Message Queues, Semaphores,
	SpinLocks, Mutexes, and Shared Memory. Each will be described
	in the following sub sections, but the general idea is, they
	are all are used "not" equally, they all have their different
	purposes.

2.4.1.1. Signals

	These are one of the oldest methods to build interrupt based
	applications, which means that a signal can be sent to a process
	or two in case of an event, or the receiving of certain new data.
	Interrupt based style is heavily used inside the kernel so you
	should understand this type of communication in great depth if
	you are planning to dive into kernel space. Also must note that
	this type of communication is asynchronous, which means there is
	no two parallel ways of communication, its only one way, or live
	on one wire as our friends at the electric engineering department
	would love to call it.

2.4.1.2. Pipes

	This is a unidirectional byte stream way of communication, which
	connects the standard output from one process into the standard
	input of another process, of course that bridge is made using
	files, but not just normal usual files, they are files that are on
	a VFS inode which itself points to a physical page within memory.
	Must note that these are unnamed pipes, there are also named pipes
	which create real files with the only difference that synchronization
	must be handled by you, locking, etc. so don't expect the magic of
	unnamed pipes, but you can set permissions to FIFOs (they are called
	that because they work with the principle of First In First Out, so
	what you write first will be read first on the other end), they can
	be created simply by the command `mkfifo' (RTFM).

2.4.1.3. Sockets

	I'm sure most of you people have stumbled upon that concept before
	or read about it somewhere, or even used it. Its simply what makes
	today's networks and even the Internet, they are all operate on the
	concept of sockets. Figured it out already?, well they are simply
	all ports and IP/Host addresses/names, but not necessarily used only
	in the case of over the network communication, it can also be used
	as IPC, heard of UNIX sockets before? and yes they are different than
	TCP/IP sockets. I'm not going into much detail over this here, as this
	has literally tons of information over the Internet, which you sir/mam
	can google out on your own.

2.4.1.4. Message Queues

	You can think of this type of communication as in one-to-many
	relationship, which happens if you want to send a message to many
	processes, the only difference between it and mailboxes is that
	it has restriction on the size of each message, and shares the
	same synchronization as mailboxes which is asynchronous, meaning
	that the sender and the receiver do not need to interact with the
	message queues at the same time. It's also similar in some ways to
	Pipes, except that it all happens in memory, no files.

2.4.1.5. Semaphores

	These are more of locks than a way to communicate, and happens mostly
	over some shared resource either resides in memory or on disk. Simply
	they are a location in memory which value can be tested and set by more
	than one process, the test/set operations are atomic or uninterruptible
	which from a process point of view; once started nothing can stop it.

	You can think of them as some variable that get incremented if a
	process or thread jumps in the critical region to modify some
	critical resource (ex. memory page, file, etc.), and once finished
	with that region in question, it decrements the value in the variable
	in an atomic fashion.

	Semaphores are not the best solution out there, its quite expensive
	to lock and unlock a semaphore, it takes literally thousands of CPU
	cycles to do so, because of the system calls that had to be made. But
	they had their uses, for example if your critical region is supposed
	to be just setting an integer value to a variable, then it is a very
	bad idea to use semaphores. But if you have an operation like writing
	to some file, then its worth it to put some process to sleep and then
	wake it up after you finish, which what semaphores does.

2.4.1.6. SpinLocks

	SpinLocks on the other hand are the fastest out there, simply because
	they are hardware implemented, note that if you are working on a single
	core/processor system, SpinLocks are useless unless you have preemptive
	kernel, or preemption is compiled into your kernel. SpinLocks are the
	fastest simply because they are implemented in hardware, not like other
	locking methods which implemented in software. However take extra care
	when exactly you use SpinLocks, as their name says it, they do a busy
	spin, which means that they keep spinning in a while loop and saving
	the time of sleeping the process and waking it up again, so if the
	critical section is taking more than a thread quantum, then SpinLocks
	are a very bad idea.

2.4.1.7. Mutexes

	You can think of Mutexes as hybrids for SpinLocks and Semaphores, which
	explains why they are the most used in user space applications. They
	do require expensive system calls when locking, but when you do unlocks
	it does it without the kernel help, which saves half the time
	Semaphores take. Basically if you don't know what you are doing, your
	best bet is to use Mutexes, they are widely known and understood, so
	you won't be bothered with all the technicalities, but yet again
	if you don't want to be bothered, this course is totally not for you
	sir/mam, go have some windows lecture instead.

2.4.1.8. Shared Memory

	Shared pages of memory are what they are, I can't really think of a
	better to describe them except that they just have an id just like
	MQueues (Message Queues, duh sherlock), but just simply share memory
	pages, not necessarily having the same address for in each process
	accessing them, but they do reference the same page, the mechanics
	of this part is complex and deep, so I leave them to later on in
	course.

2.4.2. Synchronization

	We have seen two terms till now, asynchronous and synchronous
	operations, the two differ only by one character but in meaning
	they differ a lot. Asynchronous operations are operations that
	do not necessarily expect answers right away, an example would
	be your email, you send an email to a friend, but do you expect
	him to answer instantly? no. Synchronous operations on the other
	hand are operations that do expect answers instantly, basically
	they do block on answers, an example would be talking with your
	friend on the phone, when you talk, he listens and responds in
	the same conversation context.

2.4.3. Common Problems

	Most IPC methods of communication are known to share one big
	common problem, which is synchronization, which in the context
	of computers and applications should be addressed in terms of
	managing access between processes/threads, especially on a system
	that has more than one CPU (either virtual or physical).

	One of these problems does touch security, like race conditions.
	Race conditions happen when two threads or processes race for
	a certain operation, like setting or reading a value, when that
	happens, it can exploited to corrupt the system memory, or even
	gain unauthorized access to the system itself, so must take extra
	caution when setting up locks.

	Another problem is deadlocks, which happen when a certain process
	or thread locks and dies before it unlocks, which keeps either all
	other processes/threads waiting on the lock or spinning on the lock
	which ultimately results to the termination of the application.

	These kind of problems are very hard to debug, so I felt mentioning
	them in a separate section to show how important they are, or otherwise
	you will end up producing very bad code and some guy with a tie and
	a suit knows second to none about computers, yelling at you real loud
	asking for the name of the person that taught you these stuff to murder
	with a chainsaw.

3. System Application Design

3.1. Strategy

	If you grown up to be the strategy nut I am, I'm sure you will be very
	good at these stuff, simply because on the fly planning always works,
	pre-planning stuff always fail, and you need to have a vision into
	things along adapting and inventing different strategies of your own
	to be able to see bugs and errors at a glance and be able to mitigate
	them right away and know exactly what to modify and what to lave as-is,
	its really a very good skill to have, and as every other skill it comes
	with effort and training. The only method I found very effective to
	train that kind of skill is to look at others code, see and learn how
	they done things in their own way and style, try to understand it from
	the little tiny pieces, put the pieces together to form the mental
	image they had when they first developed that application and see
	if it can be improved in anyways.

	Bluntly as I always say, try to be more of a hacker that investigate
	every single detail and tries to understand the whole of everything,
	its not a shame to fail thousands of times, but it is a shame to be
	ignorant even about the little tiny things that everybody else
	discards, and always remember that knowledge is power.

3.2. Daemons

	So what are these little evil daemons, huh? They are simply what
	windows people call them, "background processes" or "services",
	if you never developed one before its time to build one. The main
	difference between a daemon and a process like "top &" is that
	the former closes all standard input descriptors (stdin, stdout,
	stderr), and forks another process which stays in a conditional
	loop till the condition that it is keeping the loop running is
	gone (ex. waiting on a SIGTERM signal). Also logging is a major
	trait of daemons, most have logs of their own and those that don't
	make use of other pre-installed logging systems.

3.3. Logs

	Any daemon should have one or more ways to communicate with the system
	administrator, if its not logs, what would it be? You can't communicate
	thorough standard output because a daemon is never attached to any
	ttys or pts's, so it gotta be logging. There are several mechanisms for
	logging, either you design your own logging, but will have to rotate
	your logs, so you won't end up with one file of gigs of bytes. Rotating
	logs isn't hard, you can make use of `logrotate'. Or you can save
	yourself all the trouble and make use of `syslog' which is a logging
	system that provides a very simple interface that you can make use of.

3.4. Storage

	Some daemons needs some way of organized storage, there are several
	solutions to fulfill your storage needs, one is to use `SQLite',
	which is used by many applications, like APT just to name one, but
	`SQLite' is only for not so sophisticated schemes of storage, and
	you should only use it in cases that does not require huge data
	sets to be stored. If your application requires some heavy duty
	DB system, I strongly recommend the usage of `MySQL', its a very
	good and a well known DBMS that comes a long with a very well
	done API.

3.5. Debugging

	Debugging daemons is specifically hard, because it involves threads
	so you want to know where exactly a certain bug is, however you need
	first to learn how to escape from the fork being done at first that
	spawns the background process. `set follow-fork-mode child' this
	command shall force GDB to follow a fork child, meaning that once
	your daemon forks a background process, GDB starts debugging the
	new child, and the parent is simply discarded and let to die.

	To know how many threads are running and which one is currently in
	context, you issue `info threads' which will display a numbered
	list. But what if you wanted to switch to one of these threads? easy
	you just issue `thread [threadno]' where [threadno] is the thread
	number you got from `info threads'. But I strongly recommend that you
	learn GDB from ground up, as it is a one essential tool in development
	under UNIX based systems.

4. Case Studies

4.1. Case 1

	Develop an application that creates exactly two threads to calculate
	parallel Fibonacci sequence starting at any given point in the seq.

	ex. of input file ...
	04 08
	89 21
	55 89
	13 21

	The first column is where the Fibonacci sequence begins and the second
	column is where it ends. The results should be outputted to standard
	output in the form of each line in the input file corresponds to a line
	in standard output.

	Also note that the order of the columns, where the Fibonacci sequence
	begins and ends is not sorted, so you might find the first column is
	the beginning of the sequence and other times the second column is the
	where it begins.

4.2. Case 2

	Create another application that calculates the Collatz conjecture
	series based on the previous application output, only that it
	communicates with the previous application over shared memory pages
	and for each outputted line of Fibonacci sequence, a Collatz series
	has to be generated for each number in that line and outputted to
	standard output in the form of a table that each column begins with
	the original number from the first application and ends by one (1)
	(read Collatz conjecture on Wikipedia).

4.3. Case 3

	Create a daemon that forks to the background and closes all standard
	descriptors, creates a few threads to pre-calculates a very large
	number of Fibonacci and Collatz series, and a client application that
	communicates with the daemon over shared memory pages to get some of
	these results and display them to standard output.

	Note that the amount of results going to be requested from the daemon
	must come from the user not hard coded, so your application must ask
	for the amount of results before getting any.

4.4. Final Project

	With a team, do develop a server that listens on a specific IP/port
	which can handle simultaneous connections using forking or threading
	if you choose forking, you will have to implement IPC between the
	forked processes and the parent process as data in each process
	has to be shared across all other processes in a central fashion
	as the parent holds all the data in a shared memory page, and all other
	forked processes access it from there. If you however decided to go
	threading you have the advantage that you won't have to implement IPC
	in your system, but would have to design the threads as a worker thread
	and a thread pool, the worker thread, waits on connections and once
	a request for a connection is presented, a thread is assigned this
	connection from the thread pool. Once the connection ends, the thread
	gets released of the connection and back to the thread pool as an
	available thread again.

	This server purpose is to broadcast messages to each and every client
	connected to it, but also store last hour of messages in a queue for
	offline clients, so when they login to the server they receive all
	last hour messages which being exchanged, that means that all messages
	that been sent back and forth between clients. This also means that you
	will have to develop a client that connects to the server and be able
	to send and receive messages from and to the server.

	If you want to get fancy, develop a configuration file parser, and make
	the listening IP/port put into a file to be read by the server when it
	starts. This is not required, but its just a way for me saying, if you
	want to get creative its absolutely encouraged.

	Good luck :-)

5. Author

5.1. Background

	I've started coding since the early age of 10 years old, and once
	I started writing my first few lines on MSX-170/MSX-350, I never
	looked back, programming and being able to have full control over
	a machine has been an addiction of mine for many years gone and many
	to come. I've started to dwell in the security field by writing my
	first symmetric encryption algorithm by the age of 14, which got me
	even more interested in programming but at a totally different level,
	all I wanted ever since is to be able to code at the most intimate
	level of the machine, and so I have done, I'm now able to code
	some of the BIOS, learned Verilog and able to design and write FPGA
	solutions.

	As for security, lets just say, it became second nature to me and
	a passion, I see vulnerabilities in humans let alone code, I can
	manipulate about everything from a group of processes to a group
	of people. Its all comes down to this, once you discover this
	security 7th sense it just becomes like your sense of vision, it just
	changes all and every aspect of your life.

5.2. Contact Information

	Please visit http://amr-ali.co.cc

6. Thanks

	I'd like to thank mother for all the support, encouragement, and love
	she always gave me in that direction. (Love ya mommy :-P)

	Also would also like to give thanks to the people that effectively
	changed my life to the better and being patient all along ...

	Gerald M O'Steen - For being the awesome mentor he is and for teaching
		me everything he could and being a very very good friend.

	Mark LaDoux - For beating me like a dead cow till I matured and learned
		the ways of pursuing knowledge and being a good friend.

	Love you all guys <31337