[[!meta copyright="Copyright © 2011, 2012 Free Software Foundation, Inc."]] [[!meta license="""[[!toggle id="license" text="GFDL 1.2+"]][[!toggleable id="license" text="Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled [[GNU Free Documentation License|/fdl]]."]]"""]] [[!tag open_issue_gnumach]] Mach is not always able to merge/coalesce mappings (VM entries) that are made next to each other, leading to potentially very large numbers of VM entries, which may slow down the VM functionality. This is said to particularly affect ext2fs and bash. The basic idea of Mach designers is that entry coalescing is only an optimization anyway, not a hard guarantee. We can apply it in the common simple case, and just refuse to do it in any remotely complex cases (copies, shadows, multiply referenced objects, pageout in progress, ...). Suppose you define a special test program that intentionally maps parts of a file next to each other and watches the resulting VM map entries, and just ran a full Hurd system and observed results. One can stress test ext2fs in particular to check for VM entry merging: # grep NR -r /usr &> /dev/null # vminfo 8 | wc -l That grep opens and reads lots of files to simulate a long-running machine (perhaps a build server); then one can look at the number of mappings in ext2fs afterwards. Depending on how much your /usr is populated, you will get different numbers. An older Hurd from say 2022, the above comand would result in 5,000-20,000 entries depending on the machine! In June 2023, GNUMach gained some forward merging functinality, which lowered the number of mappings down to 93 entries! (It is a separate question of why ext2fs makes that many mappings in the first place. There could possible by a leak in ext2fs that would be responsible for this, but none have been found so far. Possibly another problem is that we have an unbounded node cache in libdiskfs and Mach caching VM objects, which also keeps the node alive.) These are the simple forward merging cases that GNUMach now supports: - Forward merging: in `vm_map_enter`, merging with the next entry, in addition to merging with the previous entry that was already there; - For forward merging, a `VM_OBJECT_NULL` can be merged in front of a non-null VM object, provided the second entry has large enough offset into the object to 'mount' the the first entry in front of it; - A VM object can always be merged with itself (provded offsets/sizes match) -- this allows merging entries referencing non-anonymous VM objects too, such a file mappings; - Operations such as `vm_protect` do "clipping", which means splitting up VM map entries, in case the specified region lands in the middle of an entry -- but they were never "gluing" (merging, coalescing) entries back together if the region is later vm_protect'ed back. Now this is done (and we try to coalesce in some other cases too). This should particularly help with "program break" (brk) in glibc, which vm_protect's the pages allocated for the brk back and forth all the time. - As another optimization, throw away unmapped physical pages when there are no other references to the object (provided there is no pager). Previously the pages would remain in core until the object was either unmapped completely, or until another mapping was to be created in place of the unmapped one and coalescing kicked in. - Also shrink the size of `struct vm_page` somewhat. This was a low hanging fruit. `vm_map_coalesce_entry()` is analogous to `vm_map_simplify_entry()` in other versions of Mach, but different enough to warrant a different name. The same "coalesce" wording was used as in `vm_object_coalesce()`, which is appropriate given that the former is a wrapper for the latter. ### The following provides clarifies some inaccuracies in old IRC logs: any request, be it e.g. `mmap()`, or `mprotect()`, can easily split entries `mmap ()` cannot split entries to my knowledge, unless we're talking about `MAP_FIXED` and unampping parts of the existing mappings. my ext2fs has ~6500 entries, but I guess this is related to mapping blocks from the filesystem, right? No. Neither libdiskfs nor ext2fs ever map the store contents into memory (arguably maybe they should); they just read them with `store_read ()`, and then dispose of the the read buffers properly. The excessive number of VM map entries, as far as I can see, is just heap memory. (I'm perplexed about how the kernel can merge two memory objects if disctinct port names exist in the tasks' name space -- that's what `mem_obj` is, right?) if, say, 584 and 585 above are port names which the task expects to be able to access and do stuff with, what will happen to them when the memory objects are merged? `mem_obj` in `vminfo` output is the VM object *name* port, not the pager port (arguably `vminfo` should name it something other than `mem_obj`). The name port is basically useful for seeing if two VM regions have the exact same VM object mapped, and not much else. Previously, it was also possible, as a GNU Mach extension, to pass the name port into `vm_map ()`, but this was dropped for security reasons. When Mach is built with `MACH_VM_DEBUG`, a name port can also be used to query information about a VM object. Mach can't merge two memory objects. Mach doesn't merge *memory objects* at all, it only merges/coalesces *VM objects*. The difference is subtle, but important in certain contexts like this one: a "VM object" refers to Mach's internal representation (`struct vm_object`), and a "memory object" refers to the memory manager's implementation. There is normally a 1-to-1 correspondence between the two, but this is not always the case: internal VM objects start without a memory object (pager) port at all, and only get one created if/when they're paged out. There can be multiple VM objects referencing the same backing memory object due to copying and shadowing. So what Mach could do is merge the internal VM objects, by altering page offsets to paste pages of one of the objects after the pager of the other. But this is not implemented yet. What Mach actually does is it avoids creating those internal VM objects and entries in the first place, instead extending an already existing VM object and entry to cover the new mapping. but at least, if two `vm_objects` are created but reference the same externel memory object, the vm should be able to merge them back That never ever happens. There can only be a single `vm_object` for a memory object. (In a single instance of Mach, that is -- if multiple Machs access the same memory object over network-transparent IPC, each is going to have its own `vm_object` representing the memory object.) See `vm_object_enter()` function, which looks up an existing VM object for a memory object, and creates one if it doesn't yet exist. ok so if I get it right, the entries shown by `vmstat` are the `vm_object`, and the mem_obj listed is a send right to the memory object they're referencing ? yes No. The entries shown are VM map entries (`struct vm_map_entry`). There can be entries that reference no VM object at all (`VM_OBJECT_NULL`), or multiple entries that reference the same VM object. In fact this is visible in the example above, the two entries mapped at `0x1311000` and at `0x1314000` reference the same VM object, whose name port is 586. `mem_obj` listed is a send right to the *name* port of the VM object, not to the memory object. Letting a task get the memory object port would be disastrous for security (see the "No read-only mappings" vulnerability). i'm not sure about the type of the integer showed (port name or simply an index) It is a port name (in vminfo's IPC name space) of the VM object name port. if every `vm_allocate` request implies the creation of a memory object from the default pager Not immediately, no. Only if the memory has to be paged out. Otherwise an internal VM object is created without a memory object. and a `vm_object` is not a capability, but just an internal kernel structure used to record the composition of the address space It is a kernel structure, but it also is a capability in the same way as a task or a thread is a capability -- it is exposed as a port. Specifically, a `memory_object_control_t` port is directly converted to a `struct vm_object` by MIG. This would perhaps be clearer if `memory_object_control_t` was instead named `vm_object_t`. The VM object name port is also converted to a VM object, but this is only used in the `MACH_VM_DEBUG RPCs`. i wonder when `vm_map_enter()` gets null objects though :/ Whenever you do `vm_map ()` with `MACH_PORT_NULL` for the object, or on `vm_allocate ()` which is a shortcut for the same. the default pager backs `vm_objects` providing zero filled memory If that was the case, there would not be a need for a pager, Mach could just hand out zero-filled pages. The anonymous mappings do start out zero-filled, that is true. The default pager gets involved when the pages are dirtied (so they no longer zero-filled) and there's memory shortage so the pages have to paged out. # IRC, freenode, #hurd, 2011-07-20 could we add gnumach forward map entry merging as an open issue ? probably hurting anything using bash extensively, like build most build systems mcsim: this map entry merging problem might interest you tschwinge: see vm/vm_map.c, line ~905 "See whether we can avoid creating a new entry (and object) by extending one of our neighbors. [So far, we only attempt to extend from below.]" and also vm_object_coalesce "NOTE: Only works at the moment if the second object is NULL - if it's not, which object do we lock first?" although map entry merging should be enough this seems to be the cause for bash having between 400 and 1000+ map entries thi makes allocations and faults slow, and forks even more but again, this should be checked before attempting anything (for example, this comment still exists in freebsd, although they solved the problem, so who knows) braunr: what exactly would you want to check? braunr: this rather sounds like something you would just have to try... antrik: that map merging is actually incomplete and that entries can actually be merged hm, I see... (i.e. they are adjacent and have compatible properties ) antrik: i just want to avoid the "hey, splay trees mak fork slow, let's work on it for a month to see it wasn't the problem" so basically you need a dump of a task's map to check whether there are indeed entries that could/should be merged? hehe :-) well, vminfo should give that easily, i just didn't take the time to check it braunr, as you pointed out, "vminfo $$" seems to indicate that merging _is_ incomplete. this could actually have a noticeable impact on package builds hm the number of entries for instances of bash running scripts don't exceed 50-55 :/ the issue seems to affect only certain instances (login shells, and su -) jkoenig: i guess dash is just much lighter than bash in many ways :) braunr, the number seems to increase with usage (100 here for a newly started interactive shell, vs. 150 in an old one) yes, merging is far from complete in the vm_map code it only handles null objects (private zeroed memory), and only tries to extend a previous entry (this isn't even a true merge) this works well for the kernel however, which is why there are so few as 25 entries but any request, be it e.g. mmap(), or mprotect(), can easily split entries making their number larger my ext2fs has ~6500 entries, but I guess this is related to mapping blocks from the filesystem, right? i think so hm not sure actually i'd say it's fragmentation due to copy on writes when client have mapped memory from it there aren't that many file mappings though :( jkoenig: this might just be the same problem as in bash 0x1308000[0x3000] (prot=RW, max_prot=RWX, mem_obj=584) 0x130b000[0x6000] (prot=RW, max_prot=RWX, mem_obj=585) 0x1311000[0x3000] (prot=RX, max_prot=RWX, mem_obj=586) 0x1314000[0x1000] (prot=RW, max_prot=RWX, mem_obj=586) 0x1315000[0x2000] (prot=RX, max_prot=RWX, mem_obj=587) the first two could be merged but not the others theoritically, those may correspond to memory objects backed by different portions of the disk, right? jkoenig: this looks very much like the same issue (many private mappings not merged) jkoenig: i'm not sure jkoenig: normally there is an offset when the object is valid but vminfo may simply not display it if 0 * jkoenig goes read about memory object ok, vminfo can't actually tell if the object is anonymous or file-backed memory (I'm perplexed about how the kernel can merge two memory objects if disctinct port names exist in the tasks' name space -- that's what mem_obj is, right?) i don't see why jkoenig: can you be more specific ? braunr, if, say, 584 and 585 above are port names which the task expects to be able to access and do stuff with, what will happen to them when the memory objects are merged? good question but hm no it's not really a problem memory objects aren't directly handled by the vm system vm_object and memory_object are different things vm_objects can be split and merged and shadow objects form chains ending on a final vm_object which references a memory object hm jkoenig: ok no solution, they can't be merged :) braunr, I'm confused :-) jkoenig: but at least, if two vm_objects are created but reference the same externel memory object, the vm should be able to merge them back external* are created as a result of a split say, you map a memory object, mprotect part of it (=split), then mprotect the reste of it (=merge), it should work jkoenig: does that clarify things a bit ? ok so if I get it right, the entries shown by vmstat are the vm_object, and the mem_obj listed is a send right to the memory object they're referencing ? yes i'm not sure about the type of the integer showed (port name or simply an index) jkoenig: another possibility explaining the high number of entries is how anonymous memory is implemented if every vm_allocate request implies the creation of a memory object from the default pager the vm has no way to merge them and a vm_object is not a capability, but just an internal kernel structure used to record the composition of the address space jkoenig: not exactly the address space, but close enough jkoenig: it's a container used to know what's in physical memory and what isn't braunr, ok I think I'm starting to get it, thanks. glad i could help i wonder when vm_map_enter() gets null objects though :/ "If this port is MEMORY_OBJECT_NULL, then zero-filled memory is allocated instead" which means vm_allocate() braunr, when the task uses vm_allocate(), or maybe vm_map_enter() with MEMORY_OBJECT_NULL, there's an opportunity to extend an existing object though, is that what you referred to earlier ? jkoenig: yes, and that's what is done but how does that play out with the default pager? (I'm thinking aloud, as always feel free to ignore ;-) the default pager backs vm_objects providing zero filled memory hm, guess it wasn't your question well, swap isn't like a file, pages can be placed dynamically, which is why the offset is always 0 for this type of memory hmm I see, apparently a memory object does not have a size are you sure ? from what I can gather from http://www.gnu.org/software/hurd/gnumach-doc/External-Memory-Management.html, but I looked very quickly vm_objects have a size and each map entry recors the offset within the object where the mapping begins offset and sizes are used by the kernel when querying the memory object pager see memory_object_data_request for example right. but the default pager has another interface jkoenig: after some simple tests, i haven't seen a simple case where forward merging could be applied :( which means it's a lot harder than it first looked hm actually, there seems to be cases where this can be done all of them occurring after a first merge was done (which means a mapping request perfectly fits between two map entries) # IRC, freenode, #hurd, 2011-07-21 tschwinge: you may remove the forward map entry merging issue :/ what did you discover? tschwinge: it's actually much more complicated than i thought, and needs major changes in the vm, and about the way anonymous memory is handled from what i could see, part of the problem still exists in freebsd for the same reasons (shadow objects being one of them) [[mach_shadow_objects]]. # GCC build time using bash vs. dash # Procedure * Analyze. * Measure. * Fix. * Measure again. * Have Samuel measure on the buildd.