Wednesday 31 December 2014

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!!!

Monday 29 December 2014

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

Sunday 28 December 2014

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. )

Saturday 20 December 2014

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!

Friday 12 December 2014

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.

Friday 5 December 2014

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!

Monday 1 December 2014

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