valeriu.palos.ro

Case study: fixed number of iterations with LPeg

valeriup — Wed, 01 Sep 2010 15:49:02 +0000

Words fail me to describe just how awesome LPeg is. Designed as a Lua implementation of the PEG concept, it is a true programming gem! Please, if you dont’t know what it is, take some time to familiarize yourself with it! It’s not the easiest thing to grasp, but you will *not* regret it! It is certainly one of the most worthwhile learning efforts you can make in generic programming.

One great feature of LPeg is that it’s binary-safe, meaning that (unlike regular expressions) it can be safely used to parse binary data! This makes it an excellent tool for parsing binary protocols, especially network communication protocols, such as the Action Message Format (used by Adobe Flash for making remote calls and even in FLV movie files). I’ll leave it to you to explore the possibilities…

Beware that from here on, I assume that you know your way around Lua, LPeg and how they work.

The problem

That being said, this article is actually about an unusual roadblock I hit while using LPeg to build a Lua-based AMF parser, and the various solutions I found and/or came up with to overcome it (you didn’t think that I mentioned AMF before by accident, did you?).

The issue is LPeg’s implementation of repetitive patterns: in particular, its inability to match (or capture) a fixed number of occurrences of a certain pattern, although it can match a minimum or a maximum number of such occurrences, which is perfect for stream-oriented parsing (such as parsing programming languages) but insufficient for binary data.

Just to clarify, here’s a small list of LPeg patterns which correspond to the typical PCRE repetitive constructs (in each case we’re trying to match the string ‘cloth’):

Nr.	Matching occurrences of ‘cloth’	PCRE pattern	LPeg pattern
1	0 or more (at least 0)	`/(cloth)*/`	`lpeg.P'cloth'^0`
2	1 or more (at least 1)	`/(cloth)+/`	`lpeg.P'cloth'^1`
3	X or more (at least X)	`/(cloth){X,}/`	`lpeg.P'cloth'^X`
4	1 or less (at most 1)	`/(cloth)?/`	`lpeg.P'cloth'^-1`
5	X or less (at most X)	`/(cloth){,X}/`	`lpeg.P'cloth'^-X`
6	precisely X (no more, no less)	`/(cloth){X,X}/`	`-- not implemented --`
7	anywhere between X and Y	`/(cloth){X,Y}/`	`-- not implemented --`

For cases 6 and 7, LPeg does not offer any simple constructs so we have to find a complex one. But let’s put case 7 aside for a while, and try to tackle case 6, then we’ll see…

Attempt 1 (brute force)

The first solution was rather straight-forward: we explicitly compose (i.e. append) a pattern for every occurrence we need to match. I call this the brute force method (for obvious reasons). For example, to match the word ‘cloth’ exactly three times we would use the pattern lpeg.P'cloth' * lpeg.P'cloth' * lpeg.P'cloth'.

Naturally, this is quite inflexible: what if we need to match 183 occurrences? To achieve that, we use a pattern generation function. Here’s a complete working example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

local lpeg = require'lpeg'

-- Version 1.
-- Generates a big pattern where every interation has
-- a corresponding instance of the initial pattern. The
-- resulting pattern captures all occurrences in a table.
function multiply_1(item, count)
local set = lpeg.P(true)
while count > 0 do
set = set * item
count = count - 1
end
return lpeg.Ct(set)
end

-- Generate subject ('cloth,cloth,...').
local subject = string.rep('cloth,', 10)

-- A capture of the word 'cloth' optionally followed by a comma.
local item = lpeg.C(lpeg.P'cloth') * lpeg.P','^-1

-- Match exactly 10 items.
local result = lpeg.match(multiply_1(item, 10), subject)

-- Display capture table.
print(unpack(result))

This function adds a composition operation to the big pattern for each occurrence. One method of improving this is to reduce the amount of compositions to the a bare minimum. We do this by duplicating (i.e. growing in powers of 2) the pattern until the required size is reached (also used by LPeg’s regexp emulator):

1
2
3
4
5
6
7
8
9
10
11
12
13
14

-- Version 1(b).
-- Generates a (potentially large) pattern using only
-- the minimum possible amount of compositions.
function multiply_1b(item, count)
local set = lpeg.P(true)
while count >= 1 do
if count % 2 >= 1 then
set = set * item
end
item = item * item
count = count / 2
end
return lpeg.Ct(set)
end

Looks good, however, this method presents a serious problem: the resulting pattern can get very large, forcing the limits of the Lua stack. It works well enough for small jobs, but it is unwise to generate more than a few hundred repetitions using this method (and even that may be pushing it). This means that the brute force method is unusable for heavy binary parsing, where we would often need to match even thousands of pattern repetitions.

We need to do better…

Attempt 2 (capture folding)

The next approach is a bit more complex and makes use of the more advanced features of LPeg: the lpeg.Cf() and lpeg.Cmt() captures.

In essence, we match at most the desired number of occurrences (using the ^-N operation described in the table at the top) and on every match (i.e. iteration) we execute a folding function (via lpeg.Cf()) that adds the item to the result table and also decreases a counter. At the end, we execute a checking function (via lpeg.Cmt()) which will test if the counter reached 0 (thus ensuring exact matching) and will fail if not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

-- Version 2.
-- Somewhat better approach, which starts with an empty table and gradually
-- folds every occurring capture of the initial pattern into this table, at
-- the same time decrementing the counter. Eventually, it also checks if the
-- counter reached 0 and fails otherwise.
function multiply_2(item, count)
return lpeg.Cmt(

-- Fold capture.
lpeg.Cf(
lpeg.Ct'' * item^-count,

-- Append capture.
function(set, item)
count = count - 1
table.insert(set, item)
return set
end),

-- Final check.
function(s, i, set)
if count > 0 then
return false
end
return i, set
end)
end

Note that the capture starts with an empty table created from the empty string (i.e. lpeg.Ct''). This table is the first parameter given to the folding function (i.e. set); after all the iterations, it will contain all captured items and will then be given to the check-up function for evaluation. Eventually, if all goes well, it will be returned back as the final result of multiply().

Overall this method will behave much better than the first; the generated pattern is much more elegant. However, the generated pattern can still grow quite large in memory, even though it’s not that obvious (i.e. I was surprised to find that it also crashed when generating more than a few thousand iterations).

The issue is the item^-count bit. Checking the C code of the LPeg implementation, quickly reveals that whenever count is not 0 (i.e. which is a special case), the engine is forced to allocate count objects in memory, and while these objects are lighter than a complete item pattern (as in the first solution) they are still scaling-up the problem badly!

Eventually, this method only allows generating repetitive patterns of a few thousand iterations (that is as far as I was able to push it). But, what if we need to handle a rogue pattern of 35 000 occurrences? What then? No!… we still need better!

Attempt 3 (classic loop)

The only thing left to try is a (slightly) more rudimentary technique. Basically, it is the same as the second approach but with a significant modification: instead of using lpeg.Cf() to “accumulate” (i.e. fold) every occurrence of item to the result table, we just use a straight-forward loop that will advance through the input stream at every iteration.

That makes the pattern completely dynamic, i.e. totally non-proportional to the number of matched occurrences. As a result, this method allows for an unlimited number of iterations with no memory wastes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

-- Version 3.
-- Best method so far, capable of an unlimited number of iterations. It uses
-- an explicit loop to walk over all all iterations at match-time, so there
-- is no potentially huge pattern ever created. This method simply populates
-- the result table at each iteration, or fails the entire set if the count
-- is not reached precisely.
function multiply_3(item, count)
return lpeg.Cmt(lpeg.P(true),
function(s, i)
local set, offset = {}, i
for j = 1, count do
set[j], offset = lpeg.match(item * lpeg.Cp(), s, offset)
if not offset then
return false
end
end
return offset, set
end)
end

When applied to a string, this will start matching at the current position (i.e. due to the lpeg.P(true) construct). The lpeg.Cmt() capture will trigger the iteration function immediately and there, in turn, will loop for ‘count’ number of times, matching the item at every iteration and appending it to the results table. At the same time, at each iteration, the offset is advanced by capturing the position immediately following the matched item (i.e. the lpeg.Cp() construct). If anything goes wrong, then the entire match fails (i.e. via return false).

This method works flawlessly (as far as I could tell). The generated pattern is minimal (memory-wise), the source code is very small, and the function is overall very fast (only slightly slower than the first two approaches, when matching small-sized patterns). But most importantly, with this version, matching huge numbers of item repetitions is trivial (e.g. tens of thousands, millions…).

Intervals

From here, implementing case 7 (i.e. multiply(X, Y)) is quite easy…

One approach would be to use multiply_3(item, X) to ensure the minimum number of occurrences (i.e. X) and then append the pattern item^-(Y-X) which will optionally match the remaining occurrences up to the maximum amount allowed. This method will work, and can also be used with the first two solutions, but will still (potentially) waste memory when (Y-X) is large.

A better (and still easy) approach would be to modify the loop inside multiply_3() to also accept an optional number of iterations (above the minimum). Here’s how…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

-- Version 3(b).
-- The final variant with support for interval matching
-- based on the third capturing approach (classic loop).
function multiply_3b(item, min, max)
return lpeg.Cmt(lpeg.P(true),
function(s, i)
local set, offset, attempt = {}, i, 0
for j = 1, max or min do
set[j], attempt = lpeg.match(item * lpeg.Cp(), s, offset)
if not attempt then
if j > min then
break
else
return false
end
end
offset = attempt
end
return offset, set
end)
end

In conclusion…

So, that was… quite a trip! Anyway, in hope that someone will find all this useful, I close with the usual…

Enjoy!

P.S. I would be very surprised if anyone actually reads this ridiculous banter; if you are still here, I take my hat off to you, sir (or madam)!

Lua2C, an updated version

valeriup — Thu, 22 Jul 2010 05:26:58 +0000

I know I have been “missing in action” lately but I am working furiously, and I seem to have too little time for my blog (very sad face). But, just for a breath of fresh air, I thought I’d share something with the world.

Entering lua2c.lua

Lately I became quite interested in Lua (a lot actually). It has phenomenal speed, exceptional interfacing with C and some features and libraries that just make my day (i.e. coroutines, lpeg, lua-ev and others), and since I needed to embed some Lua scripts (entirely) in a C project I’m currently working on, I ended up adapting Mike Edgar’s “bin2c.lua” script (which takes a Lua script and turns it into a C header file) to suit my needs.

Basic functionality

Specifically, this adaptation generates a function that takes a Lua state as the only argument and then runs the embedded Lua code in the given state after which it returns the status (as opposed to putting the code straight in the top-level scope of the generated file). This makes it easier to embed code in C and then invoke it, and also to apply the same code onto multiple Lua states (e.g. multiple threads).

Check the end of the post for a usage sample.

Options

-c compiles to Lua bytecode for (slightly) faster loading (does not work with LuaJIT)
-s minifies the source code before embedding to minimize wastes
-e applies a mild (XOR-based) obfuscation to prevent embedding of plain text
[UPDATE: -u produces a (void) function that never fails and panics on errors ]

Download

So here it is, enjoy: lua2c.lua (MIT license, same as Lua)
[UPDATE: It seems that Codecolorer (or GeSHI) totally trashes my script (breaks comments, escapes etc.) so I had to remove the embedded source and instead just post a download link. ]

Just to be clear

For example, given a lua script file called ‘test.lua’ (shown below) this is how we would go about embedding it into a simple C program called ‘test.c’.

1
2
3
4
5
6
7
8
9

-- test.lua: a small sign that we're up and running...

print("I am an embedded Lua script running inside a C binary! Hmm... cozy!")

function some_activity()
-- ...
end

-- ...

And here is the C file (rather overly commented)…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/*
* Include our embedded script.
*/
#include "test.h"

/*
* Invoke the script.
*/
int main(int argc, char* argv[]) {

// create a Lua state
lua_State* L = lua_open();

// load basic libraries into state
luaL_openlibs(L);

// invoke embedded script into state
// by calling the generated function
load_test_lua(L);

// finish
lua_close(L);
return 0;
}

And here’s how we can compile all this into an executable. Note that I tested this on Ubuntu Lucid and the following packages had to be installed: lua5.1, liblua5.1-0-dev, liblua5.1-lpeg2, liblua5.1-bitop0. Your configuration may differ, and if you don’t have the pre-built Lua packages, you will have to install them manyally (along with the dependencies)!

1
2
3
4
5
6
7
8
9

# generate (unprotected, minified and encrypted) C code
lua lua2c.lua -seu test.lua > test.h

# compile C program against Lua library
gcc test.c -o test `pkg-config lua5.1 --libs --cflags`

# run program
./test
I am an embedded script running from inside a C binary! Hmm... cozy!

Let me know if it works fr you, or if you think of some cool improvement!
Cheers!

Loomiere/Stream: Revived!

valeriup — Sat, 01 May 2010 20:57:59 +0000

OK folks, things have settled down and we are good to go. After some considerations the legal concerns for Loomiere/Stream are now cleared and gone. The source is now released and will be available indefinitely. Again, this streamer (minimally customized) has already been serving all the video content at http://peteava.ro for 3 full months (for those seeking a demo).

Source code: loomiere-0.2.1-tar.gz

Warning:
Any software downloaded from this website is *never* to be associated in any form with pornographic or erotic content! I.E. “Loomiere/Stream” must *never* be used to stream pornographic or erotic videos! There are plenty alternatives if you can’t help it.

Just a teaser:
Fighting the video-streaming problem has taught me very many things which, in turn, led me to realize that I might be able to use a substantially different streaming approach to achieve a massive amount of optimization in this field. So quite soon, I think I’ll have ready a brand new (and far more powerful) streamer that aims at making it possible for a single server to serve many thousands (I am still testing this) of streams simultaneously using commodity hardware. I am not yet settled on whether this project will be commercial, open-sourced or both but I hope to clear this aspect soon as well. Real-world streaming (i.e. before and after) statistics will be made available on release.

Stay tuned!

Seven essential WordPress plugins

valeriup — Wed, 10 Feb 2010 08:53:50 +0000

Here are the plugins I recommend for use on a WordPress blog.

Most (not all) of these plugins are generic, meaning that they are not bound to a specific type of blog and may (or should) be used regardless of what you write.

All of these plugins are top quality (IMHO) and provide an invaluable service for any blogger. I wholeheartedly recommend that you use and support them. I think that all of these should be apart of a standard WordPress installation.

1. Akismet

Website: http://akismet.com/download/
Everyone knows this one but it deserves mention. It prevents content spam. I’ve used it for about two years and so far it did [edit] not miss! I believe it now comes bundled with WordPress out-of-the-box.

2. Bad-behaviour

Website: http://www.bad-behavior.ioerror.us/download/
Prevents link and robot spam. Again, very good service repelling e-mail address harvesters, spam bots and all kinds of evil insects.

3. WPIDS

Website: http://php-ids.org/2007/09/12/wpids-phpids-your-wordpress-the-comfy-way/
An excellent alliance between WordPress and the PHPIDS project. It monitors your website for a very wide range of security attacks and does it very well.

4. WP Total Cache

Website: http://www.w3-edge.com/wordpress-plugins/w3-total-cache/
This plugin enhances the performance of your blog and it seems to me, after trying out wp-cache and wp-super -cache that this is the best of the lot. It can even use a memcached server (if you have one).

5. FlagrantDisregard FeedBurner

Website: http://flagrantdisregard.com/feedburner/
This plugin provides the fundamental functionality of redirecting you blog feeds to FeedBurner, so you can track your subscribers properly.

6. WordPress Stats

Website: http://wordpress.org/extend/plugins/stats/
Again, a fundamental feature: basic statistical tracking of your website right in the dashboard.

7. CodeColorer

Website: http://kpumuk.info/projects/wordpress-plugins/codecolorer/
I have yet to see a better syntax highlighting plugin than this one. Full-featured, configurable, knows any language in the book and very easy to use. Mix in a good mono-spaced font and your set!

Ok so maybe there are more, but these, I find myself installing constantly on all blogs that fall into my hands (except number 7 – CodeColorer – since it is only meant for posting source code).

Enjoy… and contribute if you like!

@font-face for a programmer’s blog?

valeriup — Tue, 09 Feb 2010 08:28:51 +0000

See Consolas in action

I’m sure that many of you are well aware of the exceptional @font-face CSS3 rule, which made life much easier for many designers, I would think. A few days ago I started wondering if it would be appropriate to use such an instrument on my blog… the site you’re on! Yoopie!

And, why not!? I love the idea of making my source codes more readable by using some custom font (Consolas anyone?). Anyway, I started looking around for some fonts and was not pleased with any of them (well to be fair I did like DejaVu Sans Mono but not as much as Consolas, unfortunately).

Long story short, here is a very generous list of web-embeddable fonts which can be used freely in commercial scenarios, gathered by the awesome FontSquirrel.com website (an instant friend!). They even provide a @font-face generator interface that transforms a given font file (TTF or OTF) into the needed formats (mainly EOT for IE) and also generates the embedding CSS3 rules. You should really give it a go!

And if you are wondering how I could speak of embedding Consolas on my blog, knowing full-well the licensing policy of Microsoft in these matters, here is your answer: one can buy a license to embed Consolas on the web (I paid $17.50) from here.

You can see it in action on any of my posts that contains some source code. Like this one!

I know, I know! I also would have never believed that I would actually promote a Microsoft product on my blog, but the Consolas font deserves all the credit! It is simply unsurpassed as far as programming goes.

So, does anyone know any other web-embeddable fonts worth mentioning?

URI parsing using Bash built-in features

valeriup — Wed, 03 Feb 2010 08:24:04 +0000

A bit of background

A while ago I posted an article describing how one could parse complete URIs in Bash using the sed program. Since then, I have realized that there is a better way to do it, a much better way: via Bash built-in pattern matching!
Here are some benefits of this improvement:

It no longer executes external programs (i.e. sed) for pattern matching. This translates to higher speed and lower memory and CPU usages, which means that you could use this parser for much more intense URI crunching.
The new regular expressions are drastically simplified thanks to the ${BASH_REMATCH[*]} array that is able to hold more than 9 matched sub-expressions, unlike sed that can only work with single-digit escapes: \1-\9 (yuck!).
The parsing algorithm is contained in a single Bash function, so no external file is needed to hold the regular expressions. This also means, obviously, that the pattern file is no longer loaded from disk on every execution (so HDD is saved as well).
The generated variables are named identically to the first version, so you should be able to upgrade your scripts to this version with absolutely minimal effort.
[Edit]
No eval instruction is needed (unlike in the first version), further improving performance.

Functionality

The function takes the URI as its parameter(s) and parses it. If the parsing was successful it returns 0 (zero), if not (bad URI) it will return 1 (or any other non-zero integer).
The URI components are placed on global variables identical to those from the first article. There is an example script further down either way so you will get the picture.

Expected URI syntax

1	[schema://][user[:password]@]host[:port][/path][?[param=value]...][#fragment]

The actual parser code

This is the actual function. You can embed this straight into your Bash script and it will be available for execution. This method greatly simplifies the usage and even debugging of this parser.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#
# URI parsing function
#
# The function creates global variables with the parsed results.
# It returns 0 if parsing was successful or non-zero otherwise.
#
# [schema://][user[:password]@]host[:port][/path][?[param=value]...][#fragment]
#
function uri_parser() {
# uri capture
uri="$@"

# safe escaping
uri="${uri//\`/%60}"
uri="${uri//\"/%22}"

# top level parsing
pattern='^(([a-z]{3,5})://)?((([^:\/]+)(:([^@\/]*))?@)?([^:\/?]+)(:([0-9]+))?)(\/[^?]*)?(\?[^#]*)?(#.*)?$'
[[ "$uri" =~ $pattern ]] || return 1;

# component extraction
uri=${BASH_REMATCH[0]}
uri_schema=${BASH_REMATCH[2]}
uri_address=${BASH_REMATCH[3]}
uri_user=${BASH_REMATCH[5]}
uri_password=${BASH_REMATCH[7]}
uri_host=${BASH_REMATCH[8]}
uri_port=${BASH_REMATCH[10]}
uri_path=${BASH_REMATCH[11]}
uri_query=${BASH_REMATCH[12]}
uri_fragment=${BASH_REMATCH[13]}

# path parsing
count=0
path="$uri_path"
pattern='^/+([^/]+)'
while [[ $path =~ $pattern ]]; do
eval "uri_parts[$count]=\"${BASH_REMATCH[1]}\""
path="${path:${#BASH_REMATCH[0]}}"
let count++
done

# query parsing
count=0
query="$uri_query"
pattern='^[?&]+([^= ]+)(=([^&]*))?'
while [[ $query =~ $pattern ]]; do
eval "uri_args[$count]=\"${BASH_REMATCH[1]}\""
eval "uri_arg_${BASH_REMATCH[1]}=\"${BASH_REMATCH[3]}\""
query="${query:${#BASH_REMATCH[0]}}"
let count++
done

# return success
return 0
}

A demonstration

Ok, I wouldn’t let you hanging there without an example, would I? This example basically uses the sample URI from the first version, and parses it accordingly. The difference is that this is an actual bash script so you can paste the parser function at the top (after #!/bin/bash) and just run it to see the parser in action.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#!/bin/bash

# parser function goes here...

# sample URI (including an injection attack)
uri='http://user:pass@www.example.com:19741/dir1/dir2/file.php?param=some_value&array[0]="123"¶m2=\`cat /etc/passwd\`#bottom-left'

# perform parsing and handle failure
uri_parser "$uri" || { echo "Malformed URI!"; exit 1; }

# main uri
echo "uri = $uri"

# mai uri components
echo "uri_schema = $uri_schema"
echo "uri_address = $uri_address"
echo "uri_user = $uri_user"
echo "uri_password = $uri_password"
echo "uri_host = $uri_host"
echo "uri_port = $uri_port"
echo "uri_path = $uri_path"
echo "uri_query = $uri_query"
echo "uri_fragment = $uri_fragment"

# path segments
echo "uri_parts[0] = ${uri_parts[0]}"
echo "uri_parts[1] = ${uri_parts[1]}"
echo "uri_parts[2] = ${uri_parts[2]}"

# query arguments
echo "uri_args[0] = ${uri_args[0]}"
echo "uri_args[1] = ${uri_args[1]}"
echo "uri_args[2] = ${uri_args[2]}"

# query arguments values
echo "uri_arg_param = $uri_arg_param"
echo "uri_arg_array[0] = ${uri_arg_array[0]}"
echo "uri_arg_param2 = $uri_arg_param2"

Expected output

The demonstration above should output the following lines of text.
Check to see if it matches and give me some feedback with the results!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

uri = http://user:pass@www.example.com:19741/dir1/dir2/file.php?param=some_value&array[0]=%22123%22¶m2=\%60cat /etc/passwd\%60#bottom-left
uri_schema = http
uri_address = user:pass@www.example.com:19741
uri_user = user
uri_password = pass
uri_host = www.example.com
uri_port = 19741
uri_path = /dir1/dir2/file.php
uri_query = ?param=some_value&array[0]=%22123%22¶m2=\%60cat /etc/passwd\%60
uri_fragment = #bottom-left
uri_parts[0] = dir1
uri_parts[1] = dir2
uri_parts[2] = file.php
uri_args[0] = param
uri_args[1] = array[0]
uri_args[2] = param2
uri_arg_param = some_value
uri_arg_array[0] = %22123%22
uri_arg_param2 = \%60cat /etc/passwd\%60

Conclusion

So, that’s it! A far better URI parser implemented straight in Bash. However, I think it could be taken even further with your help so please give it a try and write some feedback!

Enjoy!

Quality Coding Practices

valeriup — Tue, 02 Feb 2010 19:53:59 +0000

This is a set of guidelines that I put together starting a while back, which I try to respect when I write code. It is mostly (at least for now) oriented towards programming in C, but any systems programming language could benefit. Be aware that these do not apply to everyone or every scenario, adaptation and clever compromises are essential!

Now, this is obviously only a humble start, so I would like to ask the community (yes, you!) to pitch in and help grow (and correct) this list of useful principles, so that, in time, it may actually become something used by folks around the web to better their coding practices. C’mon, this will be fun, fun, fun!

I. System operations on data, memory or file descriptors

Use variable-length-arrays or alloca() as much as possible instead of malloc() and friends. This kind of allocation is much faster and is allocated on the current function’s stack instead of the heap, so the allocated memory is automatically released when the containing function returns .
[see http://en.wikipedia.org/wiki/Variable-length_array]
[see http://www.gnu.org/s/libc/manual/html_node/Advantages-of-Alloca.html]
Limit kernel syscalls to an absolute minimum. All operations on file handles (including stdin, stdout and stderr) are translated (at some point) into kernel syscalls! The same goes for malloc()/free() and many others. To this end you may consider reading the following points…
Use mmap()/munmap() and friends whenever possible to dramatically reduce the costs of highly fragmented file i/o operations and/or memory allocations ;
[see http://en.wikipedia.org/wiki/Memory-mapped_file]
Use readv()/writev() and friends whenever possible instead of multiple read()/write() calls to make use of scatter/gather file operations, enabling you to combine multiple read or write operations in a single kernel syscall;
[see http://en.wikipedia.org/wiki/Vectored_I/O]
Use splice()/sendfile() to replace malloc()/read()/write() when copying data between file descriptors. The splice()/sendfile() calls are able to copy a segment of a given input file to an output file or internet socket just like a read()/write() instruction pair would (using a memory buffer pre-allocated with malloc()). However, splice()/sendfile() operate entirely inside the kernel, thus many syscalls are saved and no pre-allocated buffer is needed the whole copy yielding much higher performance.

II. Source generation, preprocessing, compilation

Avoid passing expressions or function calls as parameters to macros. The macros will simply get expanded and the expression or function call that was given as a parameter will be executed at runtime in all places where they were expanded by the macro definition; this creates a lot of useless work and opens the possibility for undefined behaviour since an expression or function will be executed multiple times rather than only once as intended.

1
2
3
4
5

// Example
#define MAX(a, b) ((a) > (b) ? (a) : (b)) // the macro
int level = MAX(get_level(), 10); // bad usage
int current_level = get_level(); // good usage
int level = MAX(current_level, 10); // ...

Surround macro parameters with parantheses. This prevents syntax errors when expanding expression parameters.
Analyze the preprocessed code. Many times your macros can expand to unexpectedly large pieces of code making the final executable much larger; analyzing the preprocessed code cand enable you to translate such macros into function calls that get executed at run-time instead of expanded at compile-time.  
1
2
# GCC: preprocess only
 $ gcc -E source.c > source.txt

  This optimization can make the final executable much smaller and faster to load (and sometimes even execute) into the system memory (ergo inlining code is *not* always a better choice)!

III. Miscellaneous

Use environment variables or program parameters instead of configuration files whenever possible. Having configuration files, while attractive, is costly in many cases. Your program must have additional code to load and parse the configurations in memory and it also has to access the disk to read the file(s) on every run. Using parameters or environment variables avoids all these problems elegantly while still allowing you to pass various settings to the program. If you are writing a performance-critical program, that has to be small and quick to load in memory, this may save you a lot of unneeded bloat.

That’s it for now!
And, don’t be a scrooge! Tell me what you think.

Enjoy!

First impressions on Loomiere/Stream performance

valeriup — Tue, 02 Feb 2010 11:47:09 +0000

As promised, here are some of the first monitoring statistics of Loomiere/Stream in a production environment after moving away from psstream. Only one server is considered, a Quad-core Xeon with 8GB RAM (not that they are used anymore).

This shows the memory usage over one week (the switch was made on the 29th as is obvious).

…and the swap for that week:

Next we have the disk-drives load as given by iostat over one week:

Here is the TCP traffic over the interface (bare in mind that when the switch occurred, there were far more clients served simultaneously):

And finally, here is a chart showing the number of active simultaneous connections handled by the streamer over the course of one day:

Before, with psstream setup with NGINX/php-fastcgi, this server was processing 150 or (maximum 200) connections simultaneously.

So these are some first impressions, and it is plain to see that this streamer works! However, I am still not satisfied, I will continue to tinker with it and squeeze as much performance out of one server as I can.

Til’later.

Loomiere/Stream – A high performance streaming server

valeriup — Sat, 30 Jan 2010 16:35:35 +0000

UPDATE: The code is now freely available under GPLv3. Please see this post for an update.

ATTENTION: Due to the fact that myself and my company are not yet satisfied with some issues regarding the legal terms of Loomiere/Stream, I think it is wise to take it (temporarily) offline until we resolve our concerns! Also some of the technical characteristics have been retracted.

Are you killing psstream?

Well, yes! I am sure that many of you already know about psstream (the PHP streaming extension I made a while back). Well, many things happened since then and I came to realize I could do better; a whole lot better actually. As of now the ‘psstream’ project is officially no longer developed (see below). It will remain on the website for some time to come for archiving purposes but that is it.

But wait, why did you do it?

For some time now I have be looking into improving the streaming mechanism for a large video-sharing project run by my company. PSStream was a first effort, and it did the job but soon ran into problems. None of our servers was able to properly stream more than 150 clients simultaneously and the resources were grossly wasted, hence, Loomiere/Stream.

Care to share some caracteristics?

Sure. Unlike psstream (in which the moov parsing code from code-shop.com was used) Loomiere/Stream is written from scratch in C (and a bit of Bash) and uses a very minimalistic and lightweight approach. A lot of time was invested into optimizing this streamer; here are some delicious features I consider worth mentioning:

Secure and configurable
- Loomiere/Streamer is, in fact, a set of micro-streamers (mp4, flv etc.) that come together into a fast and secure HTTP server using the ipsvd and runit server tools which are very well optimized and stable. This means that I (and you) don’t have to go through the huge pain of making this server secure over time. It also means that the server’s security rules will be very flexible and easy to manage.
Optimized to the extreme
- Each micro-streamer is an extremely small program written in C/dietlibc (the mp4 streamer has at most 21k depending on system) and completely statically linked (no external libraries are linked when executed); this means that these processes can be started very quickly and the CPU is not strained by linking.
- The micro-streamers have an extremely low memory footprint (mp4 has uses about 120k, never more);
- Loomiere/Stream uses a “One process per request” approach, which is not usually very recommended on a web-server (due to the fact that it a process is usually heavier than a thread), but in the case of video streaming processes are better (IMO) than thread-pools. This is because each connection transfers a large amount of data and takes a very long time to complete, and would therefore fill-up the thread-pool rather quickly and keep it occupied for the duration of the streaming regardless of server load; here the process start-up time becomes irrelevant, and anyway the Loomiere/Strem micro-streamers startup extremely fast.
- As a side-note, I think it would be beneficial to test a thread-based approach in the case of smooth-streaming, since in that case the requests would be short enough to make it feasible. Or maybe I could use unlimited threads to stream (i.e. use threads but not a thread pool), that would be worth trying out, I think since it is possible that less context switching will occur. I’ll have to do some tests.
Saves bandwidth (throttling)
- The streamer tries to send only enough data to the player so that it will always be up-to-date. This is, of course, configurable via a set of parameters.
Versatile
- Loomiere/Stream is able to serve MP4 and FLV files (flv, f4v, mp4, m4v, mov…) as well as image files (jpg, png, gif, bmp). Images are supported because you may have images to be served along with your movies on the same machine so you won’t have to install a second webserver to access them (however, see the recommendations further down).
- The starting seek point can be given in bytes or seconds (only MP4 supports seconds yet, but FLV players always seek by byte position anyway).
- The whole streaming system is very configurable via ‘/etc/loomiere/stream.conf’, and in real-time (you don’t have to restart the server for new settings to become active).
Open source
- Loomiere/Stream is released under the GPLv3 license with an important amendment: one can never use this software for streaming pornographic or sexual content of any kind! Aside from that, you’re clear .

Did you test this anywhere?

The Loomiere/Stream server entered full production on Friday 29th of January, 2010 at 14:31 on all the content streaming servers of the peteava.ro website. Until now it has been running flawlessly.

A random check (while I’m writing this post) on one of the most strained servers yielded 653 simutaneous clients and a workload of: 8.81, 9.03, 22.47. The old streamer served at most 150 clients with extreme difficulty (the machine was almost frozen). The bandwidth usage dropped from the initial 1300MB/s to about 900 MB/s (approximate values), even though there were many more clients served in parallel.

Everything sounds good but do you think it could be better?

I know it can! Right now the server is in beta state! I can not guarantee anything at this moment (even unofficially) since I am still testing it myself under very heavy load. I will get back with more detailed statistics (and graphs), I promise!

Fantastic, where do I get it from?

ATTENTION: Due to the fact that me and my company are not yet satisfied with some issues regarding the legal terms of Loomiere/Stream, I think it is wise to take it (temporarily) offline until we resolve our concerns!

Giving any support?

I plan to provide commercial support for all Loomiere components (just the streamer for now), so yes! Soon I promise! How soon depends on how many people will use this server and request this specifically.

Until then, the support is basically open and free to anyone who wants to get involved. Practically, if you will have a problem with it and need my help, I’ll be here, I promise!

How do we use it?

The server: I don’t have a proper documentation written yet (that will be coming) but there is a “DETAILS” file in the source archive (above) that explains (in short) what you need to do to get it working. However you should have some knowledge about how ipsvd and runit work before tackling the streamer.

The clients: That’s easy, from any flash video player, you simply use the following url syntax:

http://yourserver.com/path/to/file.mp4 [ ?start=x.xxx [ &end=y.yyy ]]

Is there anything else?

I did not do any benchmarks against the Nginx and Lighttpd modules provided by the people at code-shop.com (they have renewed their modules as well). However, I hope my streamer will perform better considering that it was written with performance in mind, as a standalone server, thus not being required to work with existing web-servers. Maybe someone could do some tests (maybe I’ll get around to it some day).

Well, for now, give me any feedback, bug reports or feature requests as a comment here.

Remember, streaming high-volume video is a very tricky business, there are many things involved! So if you have a single server that does other things beside the video streaming, I advise you to use your main web server as a front, redirecting streaming requests to the Loomiere/Stream server or simply stream your videos directly on a different port (like 81, or 8080) so that both servers can live on the same machine.

Although Loomiere/Stream is able to stream images, I only recommend you use it in case of large images and not for very small images that are heavily accessed (which is usually the case on the web). So if you can, use another web server for small images (with caching maybe?). I recommend: thttpd, nginx or fnord but any other (even Apache) would do just fine (depending on your requirements).

That’s it for now, I gotta sleep. Enjoy!

Recursive chmod distinguishing files from folders

valeriup — Wed, 16 Dec 2009 11:22:16 +0000

Version 3

An even better method is:

1 2	find "$target" -type f -exec chmod -c "$mode_files" {} \; \ -or -type d -exec chmod -c "$mode_dir" {} \;

A true one-liner!

Version 2

A better method is this:

1 2	find "$target" -type f -exec chmod -c "$mode_files" {} \; find "$target" -type d -exec chmod -c "$mode_dir" {} \;

This one can also be used from the command line.

Version 1

Many times I needed to apply certain permissions recursively on a given path but with different permissions on files than on directories (i.e. I want 0644 for files and 0744 for directories). This behaviour is not provided by the chmod tool so here is a simple and effective bash function to do just that:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# Recursively apply chmod to path.
# If mode_files is missing then apply mode_dir to files too.
# Params: target mode_dir [mode_files]
function deep_chmod() {
function _walk() {
local F
for F in `find "$1"`; do
local M="$3"; [[ `file -b "$F"` == "directory" ]] && M="$2"
chmod -c "$M" "$F" > /dev/null
done
}
if [[ $# > 2 ]]; then
_walk "$1" "$2" "$3"
else
chmod -Rc "$2" "$1"
fi
}

I’m looking for a way to improve on this since it is quite costly for large directories: for each file or directory at least two programs are executed (file and chmod) which is not very efficient! For now, it gets the job done.
Enjoy!