Thursday, May 20, 2004

Mixed Memory Allocator

A hybrid approach to glibc malloc()


As we all know, modern computer systems use hundreds of megabytes of system memory to support their operation. On a shell, you can almost always stay under a hundred if you don't run any servers; but in GUI, you may reach 200, 300, 500MiB easily. Some applications use 20MiB, 40MiB, some start at 30 and grow to 80 or 100MiB, and stay there.

Most programs use a class of function calls in glibc known as the malloc() function calls. These include malloc(), calloc(), resize(), and free(). C++ programs use new[] and delete[], which are usually rooted in these functions, but not necessarily.

Because of the way the allocator works, it may be theoretically possible to increase its efficiency by anywhere from a minor, barely noticable amount to entire orders of magnitude. This would be done by attempting to balance the two methods used for allocation into a single, more effective method which neither wastes excess memory inherantly nor is forced to hold massive amounts of unused memory from the system.

Please note that the scope of this document is Linux only, and systems not supporting mmap() or equivalent calls will not be able to benefit from the new allocator scheme detailed within.

The Current Method

The malloc() class of functions has two current modes of operation, both flawed in different ways. The major method, used in most allocators on most platforms, uses the heap; while the othe method, available on Linux and other Unixes, uses the mmap() class of system calls.

Most calls to glibc malloc() functions for allocation use the heap. The simplest explaination of this method is that the heap shrinks and grows as needed. If there is not a segment of ram larger than or equal to the requested allocation, the heap is expanded via brk() to create space for the new segment. If there is free space on the end of the heap, brk() is used to shrink it, freeing the memory to the system.

The problem with the heap is that it may only exist as one large chunk. Its base (beginning) never changes, and its endpoint always must be no less than the last used piece of memory. This means that any holes in the heap are allocated, and unavailable to the system. They take up memory; and unused pages get swapped out while they're not in use, meaning that rather than just freeing and reallocating ram, a meaningless disk access must be done to give the ram back to the system and to reallocate it from the system.

One problem with the heap is that long-running applications can build up much intermittent fragmentation, and sometimes even spike for ram usage and leave junk at the top. Thus, a view of the heap may look as such for most of the application's running time:


With extremely large calls, by default those >128KiB, malloc() will become a wrapper for mmap(). mmap() maps a set of physical pages to a set of virtual pages; but it always maps whole pages. The problem with mmap() is much clearer: If you map a byte, you use 4k. 10 1 byte allocations may look like this:


The advantage of mmap() is that any one of these can be freed as soon as it is no longer in use. Unfortunately, it still bloats the ramspace.

A Hybrid Solution

On systems supporting mmap(), a hybrid solution would most likely increase the efficiency of memory allocation. Instead of using the heap or mmap(), we could use mmap()ed segments that act as heaps; that is, create a bunch of "mini-heaps" by mmap()ing contiguous memory as needed. This still leaves us vulnerable to fragmentation within pages; but entire empty pages can be immediately freed back to the system. Also, complex mappings can alleiviate situations where a new page cannot be mapped "between" two old pages.

Instead of using the heap, malloc() could use mmap() to map private, read/write, anonymous pages with the MAP_FIXED flag. This will fail if the page cannot be mapped to the exact address specified. This would allow malloc() to react by mapping somewhere else.

The basic function would be augmented by mapping the same physical pages around in other areas. Consider the case:

[**--] ____ [-***]

Where we need 7 segments to scale on here. We could satisfy this easily:


Map another page between the original two. If this mapping fails, however, we need to do one of two things: Map 2 new pages somewhere; or, my preferred method, map the other 2 pages somewhere else where we CAN map a third inbetween:

[**--] ____ [-***]

This wouldn't map extra system memory, and so we'd save a page (3 available units, plus the 1 left in the page we didn't alloc, would be 4 units, one page in our example); however, you would have to track your mapped pages and note which are which, because the multiple mapping will make allocations to one area of virtal memory space affect another. Because the above and below first and third page are the same physical memory, we must treat them as a single area of ram in our allocator.

Handling and tracking these types of allocations would be complex, but the trade-off would be good. Consider:


This is our original heap from the first example. This time, however, we can free some ram back to the system.

[****] ____ ____ ____ [---*] ____ ____ ____ [*--*]

Now, instead of using 9 pages, we use 3.

This hybrid allocator should fall back on the heap allocator if the system returns ENOMEM. ENOMEM indicates that either the system is out of memory, or that the process may not make any more memory mappings due to resource restrictions. Although running out of memory isn't recoverable, running out of your allotted memory mappings can and should be recovered from by using the heap as a fallback.

It would be very interesting to see a hybrid allocator included in glibc. It would take much coding, but the benefits could be very substantial if handled properly.

Saturday, May 15, 2004

Cascading encryption?

Let's do something nasty. . .

Thinking about IPSec, I came up with a funny thought. What if you had a database of known keys on each host, of any size, and could use them at random? That'd be a hell of a thing to crack, right? Well here's the idea in a nutshell.

First, we'll do a quick header. It'll look like the following:


First let's note how this works in theory.

PSN is the PhysicalSequenceNumber, the number of the packet.

ESN is the EncryptionSequenceNumber. The packets are encrypted based on a cascading encryption which depends on having ALL of the packets and decrypting from ESN0 forward.

SourceAddr and DestAddr are for routing. They tell where it came from, who it goes to. These are also critical.

Len tells the length in some way. For our purposes, it doesn't matter if they mean the length of the following data, the length of the whole packet, or some odd thing, as long as from this we get the last thing we need for routing.

Now, here's the fun part. KEYSIG identifies the key to be used, which has to be indexed in an identical database on each side. BUT! KEYSIG is encrypted by the key in [ESN]-1 AND THEN by the key in [ESN]-2 (not encrypted for ESN 0, encrypted with only ESN 0's key for ESN 1). So, you miss the KEYSIG for any sequence, you're screwed. Period.

The rest of the data is encrypted first by the key identified by KEYSIG, then by the key for [ESN]-1 (just KEYSIG for ESN 0). So, you have an O(N^2) probability of getting KEYSIG, or a O(N^N) probability of getting the actual data, assuming you know ALL of the keys, for any given packet. Missing the key for a KEYSIG? Your man-in-the-middle attack ends.

If your host doesn't have the KEYSIG, you can send back a packet which requests the key for KEYSIG using the signatures from the ESN immediately preceeding it. Question arises here: With a perfect man-in-the-middle, can we ensure that this is possible without letting a M-I-T-M fake it?

The idea here is that each host would have hundreds of keys acquired at different times. The cascading application of keys one atop the other from the past 2 packets and the encryption of KEYSIG itself makes it impossible to miss a packet and decrypt the rest of them, even if you posess ALL keys.

The KEYSIG for each packet should be completely random.

Sunday, May 02, 2004

I gave my aunt Gentoo

Converting the Non-Savvy

About a week ago, my aunt had some problems with her computer. Windows 2000, 4GiB hard drive (amazingly, 4.00GiB, not 4.00GB), lots of ram. It was loaded with spyware, including a popup blocker/antivirus malware program (a well designed trojan). On top of that, the hard drive was 80% full, and 79% fragmented files, some with hundreds of thousands of fragments. So I did what anyone stuck with Windows would do: ran ad-aware to dump all the spyware, and defragmented the hard drive. That. . . kind of fixed it.

Anyway, she asked me if all that was stuff I did at my house, and i took the opportunity to point out that I don't use Windows. So we got into a little conversation about Linux, and she started asking what it was. I tried to explain it out, and told her that it'd be easier to show her than to try and explain it, and easiest if she had a spare machine.

. . . ever meet someone who knows nothing about computers but just happens to have 1Ghz pentium 3's lying around in odd places? They're out there, it's scary.

So I borrowed it for a week. It had 256M of ram and a 20GB hard disk. I put 8GB on /, 2GB on swap, and 10GB on /data. / and /data are reiserfs. I set it up with gentoo-dev-sources, supermount and all; and ~x86 Gentoo. It took a week, yes. A LONG ASS TIME.

I equipped that computer with AbiWord, Gnumeric, Gnome2, KDE 3.2.2, XFCE4, Mozilla Firebird, gDesklets, X-Chat 2, abcde, vorbis tools, Anjuta, XMMS, GnomeMeeting, Gaim, Gimp 2.0.1, and xorg-x11. I gave it back to her and showed her the ropes.

First, I showed her how to use LeftCtrl+LAlt+F* to switch terminals. I then explained that GDM starts three (3) displays, and that it invariably leaves itself on the last. These three are on L[C-A]-F[7-9], and so the display automatically starts on TTY9. She grasped these concepts with relative ease; there were no questions, and she absorbed it quite easily.

While she was off doing other things, I quickly set up Gnome2 with the Crux theme, 8x2 virtual desktops, and the alien-night wallpaper from KDE; and turned off spatial browsing on Nautius. Then I put the GoodWeather and LTVariations CPU, Memory, and Disk monitor desklets on her desktop, and set up GoodWeather for her area. When she came back, I explained that the GoodWeather desklet would constantly get current weather conditions from the net every 10 minutes. She thought that was cool. :) I then showed her the virtual desktops, one of which was running Mozilla Firebird. She thought that was cool as well. She says 'cool' a lot. :/

Next, I walked her through Webmin's user adding process. She grasped the process with ease. It gave me an opportunity to explain the DAC system as well; it set the wrong perms (755) on the new user's home directory. So I used chmod -R to change those, and then explained why I set them the way I did. I then showed her her own home directory permissions in Nautilus' properties window, and explained what each meant. Then I showed her how the DAC would block access to her folder from the new user's login, and vice versa. After she had grasped that (it only took one run through the explaination), I explained the further implications of the DAC: since the entire core system is only writable by root, viruses and trojans have no way to spread; and stupid users can't screw with your system. She liked that. :)

I didn't show her how to shut it down, but she said not to worry about it because she never turns 'em off anyway. For now, she seems to grasp the DAC, the switching between display managers, and virtual desktops pretty easily. Once she's got the net up, I'll show her how to turn on DHCP for her adaptor, update her portage tree, and upgrade everything. In the mean time, she said she'd just mess with it (hey, there's menus there) and see what it can do.

This page is powered by Blogger. Isn't yours?