The Short Tourist's Guide to Memory Allocaters

There's ancient malloc().

And then there is glibc's malloc():

 (illustration not to scale)

General:

A very good place to start is Mr. Golick's intro: Memory Allocators 101, then there is Mr. Luu's C tutorial, or even Doug Lea's dlmalloc.  But, that's only the beginning of a very good, very long story.

Strategies (the very meat of this post):

There is an interesting survey on the different ways of writing a memory allocator, it's very informative (and well-written),  and useful to know in general (even though it's a little old).

More Specific:

For even more pleasing (and productive) confusion, there's TCMalloc, Lockless and a short paper that compares glibc to the former and the latter.

Also notable is jemalloc, and they have a nice video too.  Here's a neat synopsis of this toy.

Profiling:

TCMalloc has profiling inbuilt (via perftools), Lockless has some hooks and jemalloc has a heap profiler.  If you want to check what glibc malloc gets up to, there's malloc_count, or, you can knit your own, using malloc hooks and struct mallinfo.

The Lockless site has some neat info on how to profile without a profiler, using gcc. (their article collection is also quite a good read [with a very special recommendation for the rather nifty 'Obfuscated Rogue' proggy <3 !]).

Happy alloc()-ing!

Ps.: Stuff I idly wonder about:

None of the above seem to take performance profiles of stuff as they run and then automate the conclusions.

There is probably a very good reason for it (there always is :-) --- but, I wonder what would happen if we had a wrapper that that 'kept score' and did test runs on the inputs it knows about and then swaps in different memory allocators on the next run, depending on what profiles match that particular usage pattern the best.

In other news, here's my sure-fire way of how to beat the backgammon world champion:   you roll a double-6 to run home, and with the final checker, you put their 15th checker on the bar.  EASY! ;-)

+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+_+

Obligatory New Years' Eve video... Ms Sophie is celebrating her birthday party.  The only problem is that all her guests deceased 25 years ago, and so, the butler has to stand in... (scroll forward to 2:24 to start the actual sketch, but, in full length with the German intro, it still makes a nice ambience, even if you do not speak German ;-)  the rest is, as they say, without words!

Happy New year everyone!!!

Snakes! Why did it have to be snakes!?!

As you all know, I'm of the firm opinion that snakes of any kind are best enjoyed as soup and handbags.

Still, Python seems to stalk me.  (I trusssts it not)

(Note that this of course is the abbreviated tale.  Otherwise, this post would have been this B C-u 10000 I G.)

I was working through Dan Luu's malloc tutorial (more on that in the long promised malloc post!) and after doing the 'export LD_PRELOAD=...' trick and making the world run on my freshly typed toy malloc.so, gdb and clang bugged out thus on Ubuntu 14.04:

Could not find platform independent libraries <prefix>
Could not find platform dependent libraries <exec_prefix>
Consider setting $PYTHONHOME to <prefix>[:<exec_prefix>]
Fatal Python error: Py_Initialize: can't import _frozen_importlib 
IndexError: list assignment index out of range 
Aborted (core dumped)                                                                                   
                                                                   
Lucky for me, after a while, out of the blue, the xcfe error reporter pops up and has this useful info:  
                               
Stack trace: /usr/lib/i386-linux-gnu/libpython3.4m.so.1.0

is the lib that appears to cause the problem.  A quick ldd confirms that it's indeed involved.

But of course, python itself works.  But hang on, (after some deliberation...) python3 does not.  Aha!

strace python3 indeed does spit venom:

fstat(0, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 72), ...}) = 0
brk(0xb03f39)                           = 0xb03f39
readlink("/usr/bin/python3", "python3.4", 4096) = 9
readlink("/usr/bin/python3.4", 0x7fffff316970, 4096) = -1 EINVAL (Invalid argument)
open("/usr/bin/pyvenv.cfg", O_RDONLY)   = -1 ENOENT (No such file or directory)
open("/usr/pyvenv.cfg", O_RDONLY)       = -1 ENOENT (No such file or directory)
stat("/usr/bin/Modules/Setup", 0x7fffff3178f0) = -1 ENOENT (No such file or directory)
stat("/usr/bin/lib/python3./os.py", 0x7fffff3178f0) = -1 ENOENT (No such file or directory)
stat("/usr/bin/lib/python3./os.pyc", 0x7fffff3178f0) = -1 ENOENT (No such file or directory)
stat("/usr/lib/python3./os.py", 0x7fffff3178f0) = -1 ENOENT (No such file or directory)
stat("/usr/lib/python3./os.pyc", 0x7fffff3178f0) = -1 ENOENT (No such file or directory)
stat("/usr/lib/python3./os.py", 0x7fffff3178f0) = -1 ENOENT (No such file or directory)
stat("/usr/lib/python3./os.pyc", 0x7fffff3178f0) = -1 ENOENT (No such file or directory)
write(2, "Could not find platform independ"..., 55Could not find platform independent libraries <prefix>
) = 55

But here the snake bites it's tail, since I now first have to debug the debugging process before any debugging can take place --- Dan kindly sent me a cool wrapper trick, so the LD_PRELOAD happens in the gdb, rather than outside of it, and to gdb.  As an aside, Dan is not seeing the bug I'm seeing, but a friend of mine whom I asked to check on his setup, promptly has his prompt killed by this bug, so this is a distro specific adventure, with varying outcomes.

So, I grab the python3.4 source and the Ubuntu patch (just to be throrough) and set it all up.

The next puzzle was how to get Emacs's M-x gdb working with this.  After some advanced handwaving, the following incantation coalesces:

1. M-x gdb 
2. Run gdb (like this): gdb --annotate=3 -i=mi /home/g/python_source/python3.4-3.4.0/python
3. (gdb) set exec-wrapper /home/g/c-stuff/lpi/tlpi-dist/exercises/wrapper
4. break main

Fiddling about a bit, gets me this call stack:

0 in __GI_raise of ../nptl/sysdeps/unix/sysv/linux/raise.c:32 
1 in __GI_abort of abort.c:89
2 in Py_FatalError of Python/pythonrun.c:2628
3 in import_init of Python/pythonrun.c:280
4 in _Py_InitializeEx_Private of Python/pythonrun.c:445
5 in Py_InitializeEx of Python/pythonrun.c:489
6 in Py_Initialize of Python/pythonrun.c:490
7 in Py_Main of Modules/main.c:654    
8 in main of ./Modules/python.c:69

And chasing the snake down the rabbit hole a bit further gives me this in raise.c on line 32:

pid_t selftid = THREAD_GETMEM (pd, tid);

which in turn is defined in tls.h as

# define THREAD_GETMEM(descr, member) descr->member

At which point I've definitely arrived in Wonderland and I have to just guess that pi*thumb the problem is that the toy malloc isn't thread safe.

The toy malloc is first used here by python:

0 in malloc of malloc.c:67                                     
=>in main of ./Modules/python.c:30.

and the pertaining line of code is this:

  argv_copy = (wchar_t **)PyMem_RawMalloc(sizeof(wchar_t*) * (argc+1));

which is defined as

void * 
PyMem_RawMalloc(size_t size) 
{
    /*
     * Limit ourselves to PY_SSIZE_T_MAX bytes to prevent security holes. 
     * Most python internals blindly use a signed Py_ssize_t to track  
     * things without checking for overflows or negatives. 
     * As size_t is unsigned, checking for size < 0 is not required. 
     */
    if (size > (size_t)PY_SSIZE_T_MAX)  
        return NULL;
    return _PyMem_Raw.malloc(_PyMem_Raw.ctx, size);
}  

rooting around in the python3.4-3.4.0/Objects/obmalloc.c file I can see malloc being used in a number of places, but the shape is somewhat esoteric and I'm not quite sure about exactly what happens there(there be dragons!), but at some point, the toy malloc is employed.

Actually, there is one kind of snake I do like.  It's one of my favourite poems by D.H. Lawrence:

Snake

A snake came to my water-trough
On a hot, hot day, and I in pyjamas for the heat,
To drink there.

In the deep, strange-scented shade of the great dark carob-tree
I came down the steps with my pitcher
And must wait, must stand and wait, for there he was at the trough before
me.

He reached down from a fissure in the earth-wall in the gloom
And trailed his yellow-brown slackness soft-bellied down, over the edge of
the stone trough
And rested his throat upon the stone bottom,
And where the water had dripped from the tap, in a small clearness,
He sipped with his straight mouth,
Softly drank through his straight gums, into his slack long body,
Silently.

Someone was before me at my water-trough,
And I, like a second comer, waiting.

He lifted his head from his drinking, as cattle do,
And looked at me vaguely, as drinking cattle do,
And flickered his two-forked tongue from his lips, and mused a moment,
And stooped and drank a little more,
Being earth-brown, earth-golden from the burning bowels of the earth
On the day of Sicilian July, with Etna smoking.

The voice of my education said to me
He must be killed,
For in Sicily the black, black snakes are innocent, the gold are venomous.

And voices in me said, If you were a man
You would take a stick and break him now, and finish him off.

But must I confess how I liked him,
How glad I was he had come like a guest in quiet, to drink at my water-trough
And depart peaceful, pacified, and thankless,
Into the burning bowels of this earth?

Was it cowardice, that I dared not kill him?
Was it perversity, that I longed to talk to him?
Was it humility, to feel so honoured?
I felt so honoured.

And yet those voices:
If you were not afraid, you would kill him!

And truly I was afraid, I was most afraid,
But even so, honoured still more
That he should seek my hospitality
From out the dark door of the secret earth.

He drank enough
And lifted his head, dreamily, as one who has drunken,
And flickered his tongue like a forked night on the air, so black,
Seeming to lick his lips,
And looked around like a god, unseeing, into the air,
And slowly turned his head,
And slowly, very slowly, as if thrice adream,
Proceeded to draw his slow length curving round
And climb again the broken bank of my wall-face.

And as he put his head into that dreadful hole,
And as he slowly drew up, snake-easing his shoulders, and entered farther,
A sort of horror, a sort of protest against his withdrawing into that horrid black hole,
Deliberately going into the blackness, and slowly drawing himself after,
Overcame me now his back was turned.

I looked round, I put down my pitcher,
I picked up a clumsy log
And threw it at the water-trough with a clatter.

I think it did not hit him,
But suddenly that part of him that was left behind convulsed in undignified haste.
Writhed like lightning, and was gone
Into the black hole, the earth-lipped fissure in the wall-front,
At which, in the intense still noon, I stared with fascination.

And immediately I regretted it.
I thought how paltry, how vulgar, what a mean act!
I despised myself and the voices of my accursed human education.

And I thought of the albatross
And I wished he would come back, my snake.

For he seemed to me again like a king,
Like a king in exile, uncrowned in the underworld,
Now due to be crowned again.

And so, I missed my chance with one of the lords
Of life.
And I have something to expiate:
A pettiness.

Taormina, 1923

How to make bug hunting difficult (Professional Edition)

Step One:  Write a snazzy system error report GUI.

Step Two:  Be sure to not allow 'select all'.

Step Three: Do not enable copy and paste.

(Yes you can take screenshots.  But really. )

No-one expects the...

... unexpected!

I pasted some text into an open C comment and whilst closing the comment, I found that '/' does 'undo'.

Wot?

Aha, the ctrl key was stuck and it turns out that C-/ is short for M-x undo or C-x u.

YEEHAW!

How could I resist?

I bought a HUGE, 10 cm wide Moss Agate heart necklace, complete with a resident goat.  Or Capricorn, as Astrology fans would call it.

And, because the stage is lit in green and because it's excellent hacking music here's the theme music to 'Das Boot', played live by Klaus Doldinger himself:

OK, 5 minutes is definitely not long enough.  Here's the full length soundtrack:

Perfect for reading through traceroute.

The Sum of Things

I got stuck on a question about figuring out the closed form of 'function pesky' in exercise 2-2 in the Skiena book.  Of course it's easy to solve if you do it any other way, but, I tried to use summation algebra and failed miserably.

Where do you find this kind of information?  Why, in the Concrete Mathematics book in chapter 2. The very tome languishing in my shelf that I wimped out of after chapter 1 a long time ago.  Luckily I DID work through chapter 1(some time ago), so revisiting this should be easy-ish.  Maybe.

So since my concentration is all shot to bits at the moment anyway (this house move has me frazzled), I might as well go back to basics and learn some stuff I should have learned properly long ago.

Alternatively I could simply ignore the issue and just chalk this down to 'some you cannot solve' but, I've a lazy nature and, the summation trick is as lazy as it gets, plus it's ever so useful, so...

What happened to the malloc post I promised?  It's in the works.  I'm currently on page 36 of a long survey of different mallocs and pertaining strategies of 78 pages, and whilst I read some of the code that's around (of course, understanding very little, other than 'you-wanna-do-a-what?') it's as slow as my TCP/IP effort.  Mostly because there is a lot of read and as a consequence, a lot to think about.

Little by little as the cat eats the fish is the parole here.  (a bit like packing my house up, sooo much valuable junk).

Other cool stuff I'm currently enjoying:  A book about trees.  And:  Revolutions!

Clean, sliced Data. It's what's for dinner!

Difficulties with data? 

Just curry the lot with coconuts and prawns, and eat it.  

Problem solved.

Guten Appetit!

Ibco Clean Sliced Data 400G

Cleaned sliced data (Amaranthus Lividus)

Ibco Brand frozen vegetables are carefully hand picked, cleaned, washed and processed in the most advanced technology to preserve the natural taste and texture of the product. We take great care to ensure that all Ibco Brand products reach you in perfect condition every time.

Pack Size: 400g

Specially selected and freshly frozen
Cleaned ready to cook
Premium quality

Preparation and Usage: 

Cooking Method
Remove from packaging and defrost at room temperature for 2-3 hours.
Cook like fresh Vegetable.
The above are guidelines only.
Please ensure your food is cooked until piping hot.

Storage:
Food freezers* **** Until Expiry Date
Star Marked frozen food compartment
*** 3 months
** 1 month
* 1 week
Ice making compartment 3 days
Refrigerator 24 hours
*Should be -18°C or below

Country of Origin:
Bangladesh

I've been slacking.

The malloc stuff is tough.  So much to read!
The Skiena book exercises are pesky.  So much to solve!
I'm stuck on a couple of Euler Project problems.  I could pick another one (and I do) but... yeah.

My compiler doesn't love me any more.  :(

Apart from all that, I need to pack up an entire house for (finally) moving country.  I will never shop for anything again, I swear, I'm cured!

But still...

Just another evening on IRC

I hang out on ##c on freenode.net to learn some stuff (and for some entertainment).

Apart from talking about C, it's quite the dadaist scene:

[00:29] <pentester_> in C what's the different between char a="hello" and unsigned a="hello"?
[00:29] <pentester_> unsigned char a="hello"
[00:29] <marchelzo_> one is invalid and the other is invalid
[00:29] <pentester_> bad typo
[00:29] <pentester_> a[]
[00:30] <pentester_> char a[]="hello and unsigned char a[]="hello"
[00:30] <pentester_> ^ missing " xD
[00:30] <marchelzo_> one is an array of chars and the other is an array of unsigned chars
[00:30] <pentester_> what's the purpose of the unsigned char?
[00:30] <pentester_> i mean why someone would use it ?
[00:30] * zid` thinks pentester_ tests pens for a living
[00:31] <gyaretto> pentester_: I'm using it now.
[00:31] <gyaretto> Because I need to make use of all 8 bits.
[00:31] <marchelzo_> ungined char can store larger integers than char
[00:31] <marchelzo_> unsigned*
[00:31] <zid`> and it's unsined..
[00:31] <zid`> meaning you can perform mathematical operations on it
[00:31] <zid`> that would otherwise be UB
[00:31] <Chris> Why do you ever use any unsigned types? Because you don't care about negatives.
[00:32] <gyaretto> zid`: Didn't know that. TIL.
[00:32] <pentester_> so i can use integer which is more or equal to 0x80?
[00:32] <Chris> So you use unsigned char just to deal with bytes from 0 to 255 (or greater)
[00:32] <Chris> Yes, unsigned char ranges from at least 0 to 0xFF
[00:32] <marchelzo_> what can you do with unsigned that is UB with signed?
[00:32] <zid`> shifting
[00:32] <Chris> go past the highest value.
[00:32] <zid`> in some situations
[00:32] <zid`> overflow
[00:32] <zid`> lots of stuff
[00:32] *** ChanServ gives channel operator privileges to candide.
[00:32] *** candide sets a ban on *!zid@90.219.233.100.
[00:32] <Chris> unsigned char x = UCHAR_MAX; x++; // defined to be 0
[00:33] <pentester_> what is UB?
[00:33] <Chris> signed char y = SCHAR_MAX; x++; // undefined behavior
[00:33] <Chris> pentester_: undefined behavior.
[00:33] <Chris> er.. y++ for the second example, obviously.
[00:33] <pentester_> zid`: r u hacker?
[00:33] *** candide removes the ban on *!zid@90.219.233.100.
[00:34] <zid`> pentester_: Can you recommend me a pen?
[00:34] <pentester_> zid`: no time to sell pen
[00:34] <pentester_> i can penetrate if that what you want
[00:35] <Chris> zid`: www.penisland.net
[00:35] <m0shbear> zid`: the free ones they give out at career fairs
[00:35] <pentester_> Chris: what's the value of SCHAR_MAX
[00:35] <Chris> pentester_: implementation dependent.
[00:35] <pentester_> why its UB
[00:35] <vhlfd> Lol.
[00:35] <Chris> pentester_: why is what UB?
[00:35] <marchelzo_> ,grab pentester_ penetrate
[00:35] <m0shbear> because signed overflow is undefined
[00:35] <candide> Quote grabbed: 446: <pentester_> i can penetrate if that what you want
[00:36] <Chris> pentester_: overflowing a signed integer is undefined behavior.
[00:36] <gyaretto> Haha.
[00:36] <pentester_> will that a good thing  for hacker?
[00:36] <Chris> Don't know, don't care.
[00:36] <pentester_> i mean can an attacker benefit from UB
[00:36] <Chris> Ask ##scriptkiddies
[00:36] <marchelzo_> yes
[00:36] <zid`> Stick to testing pens
[00:37] <Chris> pentester_: buffer overflows are UB, surely you're familiar with them
[00:37] <vhlfd> I doubt he has any idea what he's doing, all things considered.
[00:37] <m0shbear> ^
[00:37] <pentester_> vhlfd: jelly?
[00:37] *** ChanServ takes channel operator privileges from candide.
[00:38] <pentester_> m0shbear: 0xF0ff
[00:38] <vhlfd> Wannabe hackers are excruciating.
[00:38] <Chris> Everyone has to learn at first.
[00:38] <zid`> He's learning upside down
[00:38] <Chris> But the side effects of UB are off-topic here.
[00:38] <zid`> He's going for things he's not intelligent enough to  understand first, rather than last
[00:38] <Chris> That's fairly typical.
[00:40] <pentester_> what's the meaning of signed overflow?
[00:40] <pentester_> i understand simple overflow
[00:40] <vhlfd> Read a book.
[00:40] <pentester_> vhlfd: wut book
[00:40] <vhlfd> ,k&r pentester_
[00:40] <Chris> It just means overflow on signed integers.
[00:40] <candide> pentester_: k&r is The C Programming Language, 2nd edition, by Kernighan and Ritchie, http://cm.bell-labs.com/cm/cs/cbook/ - be sure to see the errata as well, at http://cm.bell-labs.com/cm/cs/cbook/2ediffs.html
[00:40] <pentester_> old book
[00:40] <m0shbear> >not reading the classics
[00:40] <gunthler> http://www.twitch.tv/handmade_hero
[00:40] <candide> Title of gunthler's link: Twitch
[00:40] <vhlfd> Indeed. It could teach you a thing or two.
[00:41] <Chris> In C, when you do an arithmetic operation that takes a signed integer out of range, it's undefined behavior.
[00:41] <Chris> When you do the same on an unsigned integer, it is well defined.
[00:41] <Chris> The end.
[00:41] <pentester_> chris you mean if the maximum is -5 and i add one and it become -6 it will result in UB
[00:41] <Chris> I don't know how the hell you add 1 to -5 to get -6
[00:41] * vhlfd wanders off.
[00:41] <pentester_> add one by using add 0xff
[00:42] <pentester_> ^ -1
[00:42] * Chris facepalms.
[00:42] <m0shbear> use of twos-complement == nonportable
[00:42] <Chris> Don't try to be clever, pentester_. Adding 255 is not the same as subtracting 1
[00:42] <pentester_> i think i'm doing it right?
[00:43] <Chris> (except in certain contexts, which we're not talking about now and that's unsigned char where CHAR_BIT is 8)
[00:43] <Chris> No, you're not.
[00:43] <Chris> Adding 255 is not the same as subtracting 1. Make up your mind what you're talking about.
[00:43] <m0shbear> >assuming a certain representation of negative values
[00:43] <Chris> Given signed char x = -5; then x += 255; is undefined behavior. (assuming SCHAR_MAX == 127)
[00:43] <m0shbear> >assuming a certain number of bits
[00:43] <pentester_> Chris: now we talking
[00:44] <pentester_> i'm waiting for the example for overflowing signed integer
[00:44] <Chris> pentester_: anything which results in an out of range result.
[00:44] <pentester_> thanks
[00:44] <pentester_> unsigned will never overflow right?
[00:44] <Chris> Now, given unsigned char y = 5; then y += 255; is _guaranteed_ to set y to 4 (for CHAR_BIT == 8)
[00:44] <Chris> Correct.
[00:45] <pentester_> unsigned wrap around signed are not?
[00:45] <Chris> Yes...
[00:45] <pentester_> clear ;)
[00:46] <pentester_> ,thanks Chris
[00:46] <candide> /say, pentester_
[00:51] <batchm> pentester please note that you are being told what the C standard says from anal pedants, and not what actually happens on platforms you are likely to use now, and in your life time. I am sure there is some obscure platform where signed numerical types don't wrap around, but I am also sure you aren't using any of them
[00:52] <vhlfd> Another insane person.
[00:53] <Chris> pentester_: batchm's well meaning (toward you, not me) but ignorant comment neglects the fact that compilers are allowed to assume undefined behavior doesn't happen and can and will optimize out such things in many instances, thus causing shit to fail if you assume such a wrap. This is why gcc supports and needs the -fwrapv compiler flag, for example.
[00:54] <batchm> more anal pedantry.. please ignore it
[00:54] <Chris> (I just gave a practical example, and it's still called pedantry, hilarious)
[00:54] <batchm> unless you want to become a language lawyer, rather than actually get things done
[00:55] <lemonade`> hey guys, anything new lately?
[00:55] <m0shbear> >getting things done by assuming implementation-dependent things that are technically UB
[00:55] <m0shbear> how fun
[00:56] <vhlfd> Is moshbear the channel mule?
[00:56] <vhlfd> batchm, I don't think you know many language lawyers.
[00:57] <vhlfd> I think people in general would be happy if IDB GNU C were the topic of this channel.
[00:58] <vhlfd> Meh.
[00:58] <m0shbear> vhlfd: eh?
[01:01] <milesrout> pentester_, signed overflow isn't 'left up to the compiler' or 'left up to the target platform' or anything like that. The standard says 'signed overflow is undefined behaviour'. That means that your compiler is allowed to assume it never ever happens.
[01:02] <milesrout> e.g. if you do for (int i = 0; i < -1; i++);, you might expect that the compiler will go from 0 up to INT_MAX then wrap around and go up to -1 from INT_MIN.
[01:03] <milesrout> that *might* happen. but the compiler is allowed to say "signed overflow is undefined, so the programmer doesn't intend it to happen. 0 is greater than -1, and you only increment i in the loop, so i only increases. therefore this is an infinite loop"
[01:03] <milesrout> and emit the equivalent of for (int i = 0; true; i++)
[01:06] <naptime> milesrout: You meant i > -1 , right?
[01:06] <naptime> in the loop?
[01:06] <milesrout> naptime, uhh... yes!
[01:06] <milesrout> yes I did.
[01:06] <naptime> Okay, that makes more sense then [=
[01:07] <milesrout> of course, the compiler is also allowed to say 'when int overflows, wipe the hard drive'
[01:07] <naptime> I would hate to develop for that implementation!
[01:08] <milesrout> if you pass -fwrapv to the compiler, it'll wrap on signed overflow and everything should be dandy. if you pass -ftrapv to the compiler, it'll *trap* on signed overflow, i.e. your program will abort when it tries to increment INT_MAX.
[01:08] <naptime> And -fwipev clears the hard disk?
[01:08] <milesrout> those aren't portable, though. -ftrapv is very useful for debugging if you think you have signed overflow somewhere and the compiler is fucking with you because of it.
[01:09] <milesrout> hahah
[01:09] <eb0t> join #ubuntu
[01:09] <vhlfd> Nearly there.
[01:10] <milesrout> I'm a little disappointed if I wrote that all out and pentester_ had already left :/
[01:11] <vhlfd> milesrout, you can messenger your loop to him I'm sure.
[01:12] <naptime> milesrout: Well I got here just before you wrote it all out so I saw it even if this pentester_ user didn't >^,^<  And I thought it was very helpful!
[01:12] <milesrout> naptime, good!
[01:12] <vhlfd> >^,^<
[01:13] <PoppaVic> always assume a compiler.. and behavior. Very Good.
[01:28] <fizzie> ,cc -std=c11 -O2  void f(int i) { static int c = 0; if (c++ > 10) exit(0); printf("%d ", i); }  for (int i = INT_MAX - 2; i > -1; i++) f(i);  /* look at that optimizer go! */
[01:28] <candide> fizzie: 2147483645 2147483646 2147483647 2147483645 2147483646 2147483647 2147483645 2147483646 2147483647 2147483645 2147483646  Program received signal SIGSEGV, Segmentation fault in ?? () called by exit () called by f (i=<optimized out>) at statement: if (c++ > 10) exit(0); called by main () at statement: for (int i = INT_MAX - 2; i > -1; i++) f(i); <local variables: c = 12; i = 2147483647>

Srsly, who needs comic shows on TV when stuff like that is available? :-D

Maybe I no longer need to study ;o)

Taking a silly test, I am informed thus:

Thoughts on the Automata Course I took

Jeffrey Ullman's Automata course is very interesting, but heavy on the pea counting effort, and I have no pigeons handy that could help me out here, and this guy here isn't lending me his crew:

Still, it's a worthwhile class to take even if using n tracks on the Turing machine felt a little bit like cheating.  And the 3-SAT concept is useful to know in general too, and whilst I was struggling with some of the topics, it did give me a good workout.  Well, if it would be easy, it would not be so useful, no? ;-)  I definitely would not claim I understand the topic, but I gained an appreciation, and learned where to look in case I ever need it.  And I plan to retake the course if it runs again.

I did buy the Introduction to Automata Theory, Languages and Computation for ~£5 second hand, but it's a lot to read and going through it will take some time (a paragraph a day will eventually get it read, it's the Turing Machine method of studying -- it may or may not complete)

As a bonus, Mr. Ullman used a free version of his Foundations of Computer Science book, which is a very nice scenic tour of general CS concepts and a great way of refreshing long forgotten topics and picking up a few new ones.

My Buffer Overflowesth

There I was,  looking for a video on the glibc malloc implementation (more about that adventure in the next post) and whilst the most promising clip I found was unfortunately in Japanese (and, it has to be admitted, this is about as much as I currently understand about this topic :-)  --- I came across a gentleman on the sidebar who posted a nifty video series about buffer overruns,  and who has a good way of explaining the problem.

If you've always wondered just exactly how a buffer overrun works in real life(in a very basic way) check his video series out {some basic assembler required}:

So much for productive procrastination ;-)

Part  2, 3, 4, 5, 6, 7, 8, 9

Solving a Non-Problem

If you solve Euler Project problem 26, you will be able to see my 'solution' in the forum for that problem on page 9, as user Gabriela.

It's terrible.  Taarrrribbble.   First I didn't research the math, thinking: Oh, that is _easy_!  Then one simple hack led to another quick hack (with a bit of faerydust sprinkled) and let's just say I got the correct solution the first time I checked, because I lucked out, not because I wrote a good algorithm.

Valgrind was happy with it.  I'm not.  After posting the code, I realised that *somehow* I crammed nearly 1000 chars into a string I malloc(500)'ed.

The question is:  Why did it work?  The next question is: would it work on another computer?  And most important of all: should it have worked in the first place?  Plus, other than eye balling the code and seeing the obvious problem, is there a way to check?

True, you could say that it's not a bug as such, because it does what I intended, but... the issue that I have, is if that isn't picked up with a nice helpful (and popular!) SIGSEV, what else is as dodgy and wrong?

Adding -fstack-protector-all didn't help to find a indication of an error either.

After some surfing, I found that dmesg (and readelf -s) is my friend, and, lo and behold:

(...)
[12556151.546186] project2-exe[18950]: segfault at 7fff5a18ae00 ip 00007fd452916744 sp 00007fffaddf9338 error 4 in libc-2.19.so[7fd45288d000+1bb000]                                                                       
[12564217.667780] traps: project2-exe[19250] general protection ip:7f94a50ad7cd sp:7fff01927b90 error:0 in libc-2.19.so[7f94a5072000+1bb000]
(...)         

Luckily I knew where the problem was, or so I thought.  But, alas, this was a previous SIGSEV which I had fixed[1] and there was nothing that readelf had to tell me.  After some more coffee, I finally had the bright idea that perhaps those allocations were just not used, and I checked the man pages for strndup() and strstr() and... yep, that was the non-problem.

[1] One good reason to use the emacs shell instead of M-x compile:  search upwards is trivial and you find out some things that otherwise would have confuzzled you for yonks.

Om Nom Nom.

I'm having a tough time.

I signed up for the Coursera Automata Class, and it reminds me of the Schraraffenland Fairytale: to get to the fabled country where delicious fried birds fly into your mouth and pralines grow from bushes, you have to eat your way through a mountain of pumpernickel.

Om nom nom. 

(I will probably need to take this class twice, once for the measure, once to sink in)

File under:

'And you do Addition?' the White Queen asked. 'What's one and one and one and one and one and one and one and one and one and one?' 'I don't know,' said Alice. 'I lost count.' 'She can't do Addition,' the Red Queen interrupted.
                                                                           Through the Looking-glass

(Maybe I should make this into a t-shirt ;-)

I'm also reading through 'The Linux Programming Interface'  book and I'm now starting to cycle down into re-reading the chapters and doing the exercises [(I'm half-way through the book in the first sitting, time for some action), and whilst I'm having fun learning the basics, maybe you would enjoy refining your systems programming jutsu at the same time and heckle a beginner in style ;-)]

If you want to pile in, mail me.

Music I'm listening to:

(this is probably more 'ye olde jazz head stuff' -- but if you spool forward a bit to 10:35, you find some easier listening.  That said, Michel Petrucciani is just wonderful.  Yeah, some stuff is wild, but it always has soul(and much jump). Lots of it.)

Finally, my latest culinary foible is 'sharpening carrots':

See it in action:

Stuff the resulting peel with anything!  Om Nom Nom :-)

{{{ Life is good! }}}

Treat Yourself To A Proper Bug

The only problem is that one only needs one mouse(ok, maybe two), but there are so many nifty NOPE's to choose from: Hornet, Scorpion, Beetle, Spider and Crab.

...and the crowd goes wild!

"SIGSEGV
This very popular signal is generated when a program makes an invalid memory reference."

(From THE LINUX PROGRAMMING INTERFACE by Michael Kerrisk.)

I am now part of the 15.75%

... of members of Project Euler who have solved 25 coding problems and reached Level 1. (yay!)

But hang on, only less than 16% made it?  I think we should and can do better! So, join up and be entertained with quality puzzles.  How to solve?  Well, take a lesson from 'Transformer Owl':

Sometimes, to fake is better than to make

#! /bin/bash                                                         
# Compile a test file without those noisy -Wunused* flags, but       
# everything else that may be useful.                                
# 
# Usage: compileCTest <name of your file  without the '.c'>  
       
# give the executable an easy to spot and mass-delete friendly name
executable="$1-exe"

# remove the old executable if it exists                             
if [ -e $executable ]
then                                                                 
    rm $executable;                                                  
fi                                                                                                            
echo ""
echo "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
echo ""

# all flags from -Wall and -Wextra minus the -Wunused flags
runGCC='gcc -g -std=c99 -Waddress -Warray-bounds -Wchar-subscripts -Wenum-compare -Wimplicit-int -Wimplicit-function-declaration -Wformat -Wmain -Wmaybe-uninitialized -Wmissing-braces -Wnonnull -Wparentheses -Wpointer-sign -Wreturn-type -Wsequence-point -Wsign-compare -Wstrict-aliasing -Wstrict-overflow=1 -Wswitch -Wtrigraphs -Wuninitialized -Wunknown-pragmas -Wvolatile-register-var -Wclobbered -Wempty-body -Wignored-qualifiers -Wmissing-field-initializers -Wmissing-parameter-type -Wold-style-declaration -Woverride-init -Wsign-compare -Wtype-limits -Wuninitialized $1.c -o $1-exe -lm -lgmp'

eval $runGCC                                                         

# check that compile resulted in executable and if so, run it  
if [ -e $executable ]                 
then                                                                 
# add a couple of dividing lines to make this easier to read 
echo "=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=";
./$executable;
echo "=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=";
fi         

A gcc joke

$ gcc --help=common

...

  -pedantic                   This switch lacks documentation

  -pedantic-errors            Like -pedantic but issue them as errors

Remedial Reading for the 'C'onfused.

Programming from the Ground up is an easy going, fun read, and goes a long way towards explaining all those inconvenient miracles that occur when you first try to use pointers in C.

... and, for some reason, Holger Czukays' short video of 'Ode To Perfume' nicely matches the topic (and it's pretty good hacking music).  The longer version of that song is here

(and if this reminds you of Stockhausen's work, well, there's a reason for that)

Update: This here is also a useful read about C's peculiarities.

char* is not a synonym for char[]

... was the subject of a mail I wrote to friend, who replied:

... no, it's not a synonym. One of the ways in which they differ is in
declarators, as you see.

> int main(int argc, char *argv[])
>
> {
>         char ok[] = "abcd";

This means 'ok[] is an array, as large as necessary, in writeable
storage, containing the string "abcd\0"'.

>         char *broken = "abcd";

This means 'broken is a pointer to a character, pointing to the literal
string, in unmodified program text, "abcd". (Technically, this should be
'const char *': in C++, this is mandatory.)

Another difference: sizeof(ok) is the size of the array, in bytes;
sizeof(broken) is the size of a pointer to char on this platform.

In *parameter lists*, char *foo and char foo[] are synonyms, because
arrays decay to pointers *when passed to functions*. Otherwise, they are
not. (In this case sizeof() both will give the same answer.)

>         /* this is ok */
>
>         ok[0]= 'Z';

Yep. That's modifiable storage.

>         printf("ok = %s\n", ok);
>
>         /* this segfaults */
>
>         broken[0] = 'Z';

Can't modify program text, this is not FORTRAN where you could pass in
the number 3 to a function and then modify it to change the value of 3
throughout the universe, uh, I mean your program. :P

> TIL C is short for 'Confusion'.

The general rule is that in declarators, you're declaring exactly what
it looks like: foo *bar is a *pointer*, not a buffer of anything, so
assigning to it will assign to *some other buffer somewhere else*. foo[]
bar is a convenience notation for making an array on the stack, as long
as necessary, and then initializing it as with memcpy() with an
appropriate size. (Not strcpy() -- you can do this:

char containsnulls[] = "foo\0bar"

which will make an eight-byte array containing "foo\0bar\0". strcpy()
would only fill in the first four bytes of that.)

This general distinction is crucial to get the hang of, because very
often you want to declare things *not* on the stack -- that outlive
their containing function -- and then you genrally have to declare them
as a foo * and allocate and free them by hand. So remembering where your
things live (that char foo[] lives on the stack, while char foo * merely
puts the pointer on the stack while the data lives elsewhere) is
essential.

Shlemiel, the painter

A friend sent me this delightful joke which also doubles up as a puzzle, after I complained that the more I study, the longer my to-do list gets.

 (Go on, solve it, you know you want to.)

Personally, I think this was the best comment:

"You do realize, we're trying to sum up Stupidity as a Mathematical Equation."

But I also like the big collection of possible approaches --- those solutions have everything!

My solution is here, hidden as blue text on blue background:

Shlemiel can walk M meters per day, and his effort can be modelled as an Arithmetic series S_n  with the points S_x, S_y and S_z, therein, so we're looking for M = S_x,  2M = S_y and 3M = S_z and the values of x, y and z which give us the total distance reached on each day.

Rearranging S_n = n/2 (2p + d(n+1)) we get 2 S_n = dn^2 + dn +2pn = [(2S_n - 2pn) / d ] - n = n^2. 

(where p is the initial length and d is the distance) 

There is no closed form for finding n, but because n^2 is the biggest term, we can simply ignore the others and extract our values for x, y and z thus: 

x = floor(sqrt(M)), y = floor(sqrt(2M)) and finally, z = floor(sqrt(3M)).

On day one he paints a = x meters, the next day he manages b = (y - a) meters, and finally, c = (z - b) meters on the third. 

Update: there is of course always at least one error in every solution... and the above is no exception :) 

So...

x = floor(sqrt(2 M/d)), y = floor(sqrt(2*2M/d)) and finally, z = floor(sqrt(2*3M/d)).

Moral of the story: beware of working with convenient values.

I'm giving up on Python

Python is a pretty language in general, it has lots of very cool features and there is a lot to like.

But, is has no braces.

It's uneditable, unless you want to spend hours hitting the TAB button,  taking great care not to introduce unnecessary errors.

You cannot move code around trivially.

You cannot auto-indent it.

It's like using a chisel and a granite slab to code.  Or driving a Ferrari in England.  Or hiking in high heels.

No, Nein, Нет, Non, Naï, לא, Nej, Nee, 无,  Minime, いいえ, NOPE.

(I have no issues with editing an existing Python program. Just wouldn't code a whole one.)

It Seemed Like a Good Idea at the Time

My latest idea for the svn --diff-cmd can be seen here.

Let's hope it does better than this guys' great idea!

Your Money Or Your Life

Life and Adventures of Frank and Jesse James

Great bedtime stories --- beautifully phrased English, perfectly read.

How to arrange for tabs in your code

1. Set up a new computer downstairs.
2. Copy your messy .emacs file onto this machine.
3. Play 'catch the fish' with your cat whilst you look at the keyboard and type emacs
4. Go back upstairs to do stuff.
5. Realise that emacs's server hasn't started and don't think as to why that possibly could be.
6. Go downstairs, do M-x server-start without looking at the screen (because you're still fishing the cat)
7. Profit.

I blame the cat.

SVN --invoke-diff-cmd branch shipped

So what happened that took the time?

1. I forgot *everything* (and had to re-re-re-read the manuals)

2. My main laptop died (RIP frogburg, it croaked it's last) and so I had to build everything back from scratch on my remaining machine.  I also have a new desktop that I had so far avoided to set up, which I did at the same time.

3.  Because the trunk had changed quite a bit, my feeble attempts to merge initially produced a veritable mess that added to the general confusion.  It didn't help that this was my first merge that required actual work, nor did it help that I had a complete new install and for a few days didn't realise that kdiff3 wasn't installed, and thought that my code was broken (which it was, but not in this place) and so, I of course kept looking in the illuminated place for the door keys.

4. Somewhere in the new trunk code, a miracle happens.   That is, it picks up the actual command line input en passant 3 functions deep whilst it reads the config file, and I had to break out gdb to search the haystack.

5.  Every time I get stuck (or bored) I read a page of the TCP/IP book.  I read a lot of TCP/IP book.

Anyway, here is the new branch, this time as a patch.

Laptop and Doorstep Book Stand

I bought a laptop stand because, somehow, it seems that no matter what you do, you always end up craning your neck or twisting your arms, it's never possible to place what you want to look at 'just so'.  This contraption definitely does the trick:

You can easily type on the laptop keyboard (it does bounce a bit), but I think using a wireless keyboard and mouse is more comfortable anyway, as I like the screen to be further away than my arms reach.

Drawbacks are that you need to remove whatever is on it to adjust it, and if you undo the screws all the way by accident, you'll end up with a handful of icky greasy bits (and a spring) that you have to puzzle back together again.

The good thing about it is that it's very portable and quick to assemble and that it makes it easy to socialise laptops and those heavy doorstep books that are awkward to handle[1], and it also stops the laptop from getting too hot.

And it's great to be able to adjust the view to yourself, instead of you adjusting yourself to the view!

[1] What's not shown in the picture is that you get a couple of big rubberbands which allow you to place books so the spine doesn't fall through the middle and also make it possible to shift the laptop into the perfect position.

Rewriting my SVN branch

My invoke-diff-cmd branch cannot simply be merged, and it looks like I need to rewire things quite a bit.

So, apart from learning python for my new project (more of that in a soon to be typed blogpost!) and playing around with pylint and reading up on HTML5 after I had some great suggestions on how to improve my 'Fail to Plan, Plan to Fail' application,  I'm still trying to figure out what is actually going on in the new svn diff code, and the way I'm currently feeling about this all is probably best described as in this video below:

Then again, I'm pretty sure I'll be dining on curried chicken quite soon ;-)

Google Chrome Scrollbar Annoyance

For some reason, it was decided that web developers get to set the width of the Chrome scrollbar.

That's like allowing the petrol station to reset the width of my steering wheel.

I do not see a reason why users are expected to trawl the web for a fix and get lucky that the nth enigmatic recipe or extension works, or are advised to fiddle around with CSS code in order to restore a core functionality that should be set at OS level.

If I cannot trivially make it work, then lots of people won't either. 

*grump*

Ps.: How much user time is wasted on this 'feature'? 

A script for Exaile: bedtime-story.sh

As much as I like Exaile, it sadly lacks the option of turning a recording off after n minutes.

But, who needs a feature for the Exaile GUI when a script will suffice?

So, set your story up to play in the GUI, then use this:

bedtime-story.sh:

# turn the screen off
xset dpms force off

sleep $@ > /dev/null 2>&1

if [ $? = 1 ]
then
    # turn the screen on
    xset dpms force on
    echo "Fade out Exaile playback after a defined time, using the computer's volume control."
    echo ""
    echo "Usage: bedtime-story NUMBER[smh]..."
    echo ""
    echo "Each argument is a number followed by a unit."
    echo "The units are: s (seconds), m (minutes), h (hours)"
    echo "Example: bedtime-story 20m 10s"
    echo "The screen will be turned off, move the mouse or press a key to turn it back on."
fi

# grab current spot and volume, then gently fade and pause
c=$(exaile --current-position)
v=$(pactl list | grep Volume | cut -d ":" -f 3 | cut -d "%" -f 1 |\
 sed -n '1p' | sed -e 's/^[ \t]*//' -e 's/[ \t]*$//')
for((i=$v;i>=0;i--)) do
    sleep 1s
    pactl set-sink-volume 0 ${i}%
done
exaile --play-pause

# return volume to former setting
pactl set-sink-volume 0 ${v}%
echo "The current track was faded out beginning at $c."

Now I can go to sleep in style, whilst listening to the Internet's longest history podcasts. (in parts).