lkml.org 
[lkml]   [1996]   [Mar]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRe: kmalloc: 56 is the answer to Linux, the Universe and Everything
Date
Daniel Barlow writes:
>
> > no. requests size requested
> > 24205 56 struct vm_area_struct
> > 303 988 struct task_struct
> > 303 84 struct mm_struct
> > 303 516 struct signal_struct
> > 303 16 struct fs_struct
> > 303 1060 struct files_struct
> >
> >I only went through the 'easy' requests - those with 303 requests.
> >They come from creating new tasks, but all of the structures are
> >allocated seperately. I decreased NR_OPEN on my system to 246 and am now
> >enjoying an extra 8-10 pages of free memory (yeah). NR_OPEN is defined
> >in linux/fs.h and limits.h. signal_struct can't be helped, but maybe
> >there is a way to attach it to some of the other allocations... Or
> >perhaps a kmalloc that better deals with these allocations should be
> >written. Any ideas?
>
> I guessed it was the task creation, chiefly from looking at the graph;
> it's kind of saw-toothed. Diddling the struct sizes seems a bit of a
> dead end, to me; signal_struct will in any case change when POSIX 4
> signals come in (I assume). I'd prefer a kmalloc which can do
> arbitrary sizes.
>
> I did some more `analysis'; in particular, by logging the address that
> kmalloc was called from it gets a lot easier to track things down. I
> also tried to collect some data on a networked machine.
>
> When networking comes into the picture, the big wastage seems to come
> from nfs (surprise ...). Most networking allocations are for less
> than 508 bytes, but a 2048 byte kmalloc actually gets given 4080 bytes
> --- a full page, in other words. On the other hand, at least when I
> tested, it only seemed to use one page at a a time.
> <http://ftp.linux.org.uk/~barlow/kmalloc/>; go and take a look in the
> subdirectories.
>
> A simple enhancement might be for kmalloc of between 2040 bytes and a
> page to get handed straight off to __get_free_pages, and for kfree(p)
> to test if p is page aligned before messing with its lists. The
> problem is that you then lose the ability to check that the pointer
> passed to kfree is genuine.
>
> Another possibility (given that the size classes _aren't_ powers of
> two anyway) is to introduce a couple more of them. 670 bytes, say.

In the *excellent* book "Unix Internals: The New Frontiers" by Uresh
Vahalia (plug, plug for those who haven't already read it), he
discusses kernel memory allocation implementations for most modern
Unices, including SVR4, SVR4.2, Mach. It's incredibly useful for those
of us without access to proprietary kernel source to see an
independent comparison of methods used. I've only had a chance to skim
through it once and unfortunately I can't remember details off-hand of
which Unix uses which allocator. However, there are at least two
possibilities for the two problem structures above. In both cases they
are just under a power of 2 and allocation of vm_area_struct at least
needs to be as fast as possible from the above stats.

A generic solution would be a zone allocator as used in Mach which
lets you (dynamically) allocate a zone for vm_area_struct structures
of fixed known size. Allocation is fast (they're on a linked list with
no header to bump up their size) and zone_gc handles garbage collection
and handing back zone pages to the free pool and runs from the swapper
when memory is low. The only problem with that is that it requires
someone to write a general purpose zone allocator. The other solution
that strikes me would be a buddy or lazy-buddy allocator which handled
allocations for power-of-two-blocks-with-no-header via its own bitmap of
used blocks. I think it's SVR4 and SVR4.2 which use variations of that.

As much as I'd like to chip in myself and start writing, I don't really
have the time at the moment. However, if others think it's a good idea
and you (Daniel) have time *and* think I can be of any help to you, I'll
point you in the right direction. We really ought to set up a Linux
kernel hacker's workshop around here sometime.

--Malcolm

--
Malcolm Beattie <mbeattie@sable.ox.ac.uk>
Unix Systems Programmer
Oxford University Computing Services


\
 
 \ /
  Last update: 2005-03-22 13:36    [from the cache]
©2003-2011 Jasper Spaans