Messages in this thread | | | From | Malcolm Beattie <> | Subject | Re: kmalloc: 56 is the answer to Linux, the Universe and Everything | Date | Tue, 26 Mar 1996 15:32:57 +0000 (GMT) |
| |
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
| |