Memory part 3: Virtual Memory [LWN.net]

Memory part 3: Virtual Memory

Posted Oct 11, 2007 11:12 UTC (Thu) by addw (guest, #1771)
Parent article: Memory part 3: Virtual Memory

This means, on average, that each mapping wastes half the page size in physical memory for each mapping.

Is that really correct ? If there is an allocation several pages long then the last page will be, on average, 1/2 wasted.

Look at the example a bit later, the first memory size is 0x0132ac (78508 decimal) which is 19 (4k sized) pages and 684 bytes, so 3412 out of 78508 bytes wasted = 4%.

(Log in to post comments)

What's your problem then ?

Posted Oct 11, 2007 19:59 UTC (Thu) by khim (subscriber, #9252) [Link]

If there is an allocation several pages long then the last page will be, on average, 1/2 wasted, or, in other words, each mapping wastes half the page size in physical memory for each mapping. You've said the same thing Drepper said but in different words as far as I can see...

What's your problem then ?

Posted Oct 11, 2007 23:25 UTC (Thu) by jzbiciak (✭ supporter ✭, #5246) [Link]

There's a pretty big difference between the "last page" of "an allocation several pages long", and "each mapping". Each page has a mapping, and so the allocation mentioned has multiple mappings associated with it because it involves multiple pages. Suppose I allocate 62K, and I need to carve it into 4K pages. I end up allocating 64K total (16 pages). 15 of the 16 pages are fully utilized, and the last page is half-wasted.

Consider an allocation of N bytes that does not share pages with any other allocation--for example, an allocation via mmap.

It requires ceil(N / PAGE_SIZE) pages (and therefore mappings).
It will waste (PAGE_SIZE - (N % PAGE_SIZE)) bytes total.
There will be floor(N / PAGE_SIZE) fully utilized pages.

The amount of wasted bytes depends on the distribution of N. As N grows larger (and the number of mappings per allocation goes up), the number of wasted bytes per mapping goes down.

(And yes, that's pseudo-code. The actual C code to compute those quantities isn't much different, but it's a little noisier.)

What's your problem then ?

Posted Oct 15, 2007 13:13 UTC (Mon) by mgedmin (subscriber, #34497) [Link]

I do not think the work "mapping" means what you think it means, at least in the context of this article.

Here's what the manual page of mmap says: "mmap() creates a new mapping in the virtual address space of the calling process. The starting address for the new mapping is specified in start. The length argument specifies the length of the mapping."

That's how I understand "mapping": a contiguous range of virtual memory addresses in the address space of a particular process.

Memory part 3: Virtual Memory

Posted Oct 11, 2007 23:32 UTC (Thu) by jzbiciak (✭ supporter ✭, #5246) [Link]

If it were, then it seems virtual memory is a recipe for wasting half your memory. I think what was meant was "each contiguous range that is mapped."

There seems to be a shorthand amongst some folk to call what corresponds to a row in /proc/<PID>/maps "a mapping," when indeed it is typically composed of multiple pages, and is really multiple mappings that are contiguous in virtual address space. For example, a quick peek with "cat /proc/self/maps" here at work shows:

$ cat /proc/self/maps 
00101000-00227000 r-xp 00000000 03:02 1196106    /lib/tls/libc-2.3.4.so
00227000-00229000 r-xp 00125000 03:02 1196106    /lib/tls/libc-2.3.4.so
00229000-0022b000 rwxp 00127000 03:02 1196106    /lib/tls/libc-2.3.4.so
0022b000-0022d000 rwxp 0022b000 00:00 0 
0055c000-00572000 r-xp 00000000 03:02 1196104    /lib/ld-2.3.4.so
00572000-00573000 r-xp 00015000 03:02 1196104    /lib/ld-2.3.4.so
00573000-00574000 rwxp 00016000 03:02 1196104    /lib/ld-2.3.4.so
08048000-0804c000 r-xp 00000000 03:02 967851     /bin/cat
0804c000-0804d000 rwxp 00003000 03:02 967851     /bin/cat
0804d000-0806e000 rwxp 0804d000 00:00 0 
b7fde000-b7fe0000 rwxp b7fde000 00:00 0 
bfffd000-c0000000 rwxp bfffd000 00:00 0 
ffffe000-fffff000 ---p 00000000 00:00 0

Under the shorthand nomenclature, that's 13 mappings. Clearly, far more than 13 pages are involved.

definition of mapping

Posted Oct 12, 2007 17:07 UTC (Fri) by giraffedata (subscriber, #1954) [Link]

It's not even shorthand; it's just the nonspecific meaning of the word "mapping." Relating 10 virtual pages to 10 real pages is a mapping; relating one of those real pages to one of those real pages is also a mapping. One could legitimately call an entire page table a mapping.

The text elides a great deal about the process of loading an executable; if it gave proper context, it would probably be more clear that it isn't referring to individual page mappings.

definition of mapping

Posted Oct 12, 2007 17:17 UTC (Fri) by jzbiciak (✭ supporter ✭, #5246) [Link]

Fair enough. I try to be precise myself when I can. I personally think of the three notions of "mapping" you have as "page mapping," "mapped range" and "memory map", though I can easily see imperfections in those names. :-)