From 95878586ec7611791f4001a4ee17abf943fae3c1 Mon Sep 17 00:00:00 2001 From: "https://me.yahoo.com/a/g3Ccalpj0NhN566pHbUl6i9QF0QEkrhlfPM-#b1c14" Date: Mon, 16 Feb 2015 20:08:03 +0100 Subject: rename open_issues.mdwn to service_solahart_jakarta_selatan__082122541663.mdwn --- .../gnumach_vm_map_red-black_trees.mdwn | 346 +++++++++++++++++++++ 1 file changed, 346 insertions(+) create mode 100644 service_solahart_jakarta_selatan__082122541663/gnumach_vm_map_red-black_trees.mdwn (limited to 'service_solahart_jakarta_selatan__082122541663/gnumach_vm_map_red-black_trees.mdwn') diff --git a/service_solahart_jakarta_selatan__082122541663/gnumach_vm_map_red-black_trees.mdwn b/service_solahart_jakarta_selatan__082122541663/gnumach_vm_map_red-black_trees.mdwn new file mode 100644 index 00000000..53ff66c5 --- /dev/null +++ b/service_solahart_jakarta_selatan__082122541663/gnumach_vm_map_red-black_trees.mdwn @@ -0,0 +1,346 @@ +[[!meta copyright="Copyright © 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]] + + +# IRC, freenode, #hurd, 2012-04-23 + + btw, i'm running a gnumach version using red-black trees for vm + map entries + braunr: sounds fashionable ;-) + braunr: with some perf improvement? + looks promising for our ext2fs instances showing several thousands + of map entries + youpi: i'm not using it for lookups yet + but the tree is there, maintained, used for both regular and copy + maps, and it doesn't crash + good :) + antrik: isn't it ? :) + youpi: and the diff stat is like 50/15 + braunr: what's the goal of using the fashionable trees? + antrik: speeding up lookups in address spaces + braunr: so the idea is that if we have a heavily fragmented + address space, the performance penalty is smaller? + yes + OK + I take it you gave up on attempts to actually decrease + fragmentation?... + it's not as good as reducing fragmentation, which requires + implementing a powerful merge, but it's still better + yes + it's too messy for my brain :/ + I see + oh + it will add some overhead though + I guess log(n) ? + but if there is a significant performance gain, it'll be worth it + yes + i was more thinking about the memory overhead + right now it's a linear list? + I don't think we care nowadays :) + antrik: yes + ouch + antrik: yes ... :> + the original authors expected vm maps to have like 30 entries + so they used a list for the maps, and a hash table for the + object/offset to physical page lookups + there is a small lookup cache though, which is a nice optimization + my code now uses it first, and falls back to the RB tree if the + hint didn't help + braunr: well, don't forget to check whether it actually *is* still + an optimisation, when using fashionable trees ;-) + antrik: i checked that already :) + i did the same in x15 + I see + both bsd and linux uses a similar technique + use* + (well, bsd actually use what is done in mach :) + (or perhaps the other way around... ;-) ) + i don't think so, as the bsd vm is really the mach vm + but we don't care much + oh, right... that part actually went full circle + youpi: i have a patch ready for test on machines with significant + amounts of map entries (e.g. the buildds ..) + youpi: i won't have time for tests tonight, are you interested ? + (i've been running it for 15 minutes without any issue for now) + I'd say post to the list + ok + braunr: your patch uses the rb tree for lookups, right? + braunr: the buildd using rbtree seems swift + but maybe it's just a psychologic effect :) + the chroot ext2fs already has 1392 lines in vminfo + an rbtree can't hurt there :) + braunr: it really seems faster + the reboot might have helped too + benchmarks shall say + for now, I'll just let ironforge use it + youpi: it's always fast after a reboot ;-) + sure + but still + I mean + *obviously* the reboot has helped + but it might not be all + at least it feels so + and obviously only benchmarks can say + the major benefit AIUI is rather that the slowdown happening over + time will be less noticable + +[[performance/degradation]]. + + "over time" is actually quite fast + ext2 fills up very quickly when you build a package + it went up to 1700 lines very quickly + and stabilized around there + yeah, it can be very fast under heavy load + that's why I say reboot seems not all + it's already not so fresh + with 1700 lines in vminfo + well, I don't know how much of the slowdown I'm experiencing + (after doing stuff under memory pressure) is actually related to VM map + fragmentation... + might be all, might be none, might be something in between + then try his patch + guess I should play a bit with vminfo... + well, currently I actually experience pretty little slowdown, as + for certain reasons (only indirectly related to the Hurd) I'm not running + mutt on this machine, so I don't really have memory pressure... + + +## IRC, freenode, #hurd, 2012-04-24 + + youpi: yes, it uses bst lookups + youpi: FYI, the last time i checked, one ext2fs instance had 4k+ + map entries, and another around 7.5k + (on ironforge) + + +## IRC, freenode, #hurd, 2012-04-24 + + braunr: $ sudo vminfo 624 | wc -l + 22957 + there's no way it can not help :) + youpi: 23k, that's really huge + + +## IRC, freenode, #hurd, 2012-04-26 + + youpi: any new numbers wrt the rbtree patch ? + well, buildd times are not really accurate :) + but what I can tell is that it managed to build qtwebkit fine + ok + so the patch is probably safe :) + i'll commit it soon then + I'd say feel free to, yes + thanks + + +## IRC, freenode, #hurd, 2012-04-27 + + elmig: don't expect anything grand though, this patch is mostly + useful when address spaces get really fragmented, which mainly happens on + buildds + (and it only speeds lookups, which isn't as good as reducing + fragmentation; things like fork still have to copy thousands of map + entries) + +[[glibc/fork]]. + + +## IRC, freenode, #hurdfr, 2012-06-02 + + braunr: oh, un bug de rbtree + Assertion `diff != 0' failed in file "vm/vm_map.c", line 1002 + c'est dans rbtree_insert() + vm_map_enter (vm/vm_map.c:1002). + vm_map (vm/vm_user.c:373). + syscall_vm_map (kern/ipc_mig.c:657). + erf j'ai tué mon débuggueur, je ne peux pas inspecter plus + le peu qui me reste c'est qu'apparemment target_map == 1, size == + 0, mask == 0 + anywhere = 1 + youpi: ça signifie sûrement que des adresses overlappent + je rejetterai un coup d'oeil sur le code demain + (si ça se trouve c'est un bug rare de la vm, le genre qui fait + crasher le noyau) + (enfin jveux dire, qui faisait crasher le noyau de façon très + obscure avant le patch rbtree) + + +### IRC, freenode, #hurd, 2012-07-15 + + I get errors in vm_map.c whenever I try to "mount" a CD + Hmm, this time it rebooted the machine + braunr: The translator set this time and the machine reboots + before I can get the full message about vm_map, but here is some of the + crap I get: http://paste.debian.net/179191/ + oh + nice + that may be the bug youpi saw with my redblack tree patch + bddebian: assert(diff != 0); ? + Aye + good + it means we're trying to insert a vm_map_entry at a region in a + map which is already occupied + Oh + and unlike the previous code, the tree actually checks that + it has to + so you just simply use the iso9660fs translator and it crashes ? + Well it used to on just trying to set the translator. This time + I was able to set the translator but as soon as I cd to the mount point I + get all that crap + that's very good + more test cases to fix the vm + + +### IRC, freenode, #hurd, 2012-11-01 + + braunr: Assertion `diff != 0' failed in file "vm/vm_map.c", line + 1002 + that's in rbtree_insert + youpi: the problem isn't the tree, it's the map entries + some must overlap + if you can inspect that, it would be helpful + I have a kdb there + it's within a port_name_to_task system call + this assertion basically means there already is an item in the + tree where the new item is supposed to be inserted + this port_name_to_task presence in the stack is odd + it's in vm_map_enter + there's a vm_map just after that (and the assembly trap code + before) + I know + I'm wondering about the caller + do you have a way to inspect the inserted map entry ? + I'm actually wondering whether I have the right kernel in gdb + oh + better + with the right kernel :) + 0x80039acf (syscall_vm_map) + (target_map=d48b6640,address=d3b63f90,size=0,mask=0,anywhere=1) + size == 0 seems odd to me + (same parameters for vm_map) + right + my code does assume an entry has a non null size + (in the entry comparison function) + EINVAL (since Linux 2.6.12) length was 0. + that's a quick glance at mmap(2) + might help track bugs from userspace (e.g. in exec .. :)) + posix says the saem + same* + the gnumach manual isn't that precise + I don't seem to manage to read the entry + but I guess size==0 is the problem anyway + youpi, braunr: Is there another kernel fault? Was that in my + kernel? + no that's another problem + which became apparent following the addition of red black trees in + the vm_map code + (but which was probably present long before) + braunr: BTW, do you know if there where some specific circumstances + that led to memory exhaustion in my code? Or it just aggregated over + time? + mcsim: i don't know + s/where/were + braunr: ok + + +### IRC, freenode, #hurd, 2012-11-05 + + braunr: I have now also hit the diff != 0 assertion error; + sitting in KDB, waiting for your commands. + tschwinge: can you check the backtrace, have a look at the system + call and its parameters like youpi did ? + If I manage to figure out how to do that... :-) + * tschwinge goes read scrollback. + "trace" i suppose + if running inside qemu, you can use the integrated gdb server + braunr: No, hardware. And work intervened. And mobile phone + <-> laptop via bluetooth didn't work. But now: + Pretty similar to Samuel's: + Assert([...]) + vm_map_enter(0xc11de6c8, 0xc1785f94, 0, 0, 1) + vm_map(0xc11de6c8, 0xc1785f94, 0, 0, 1) + syscall_vm_map(1, 0x1024a88, 0, 0, 1) + mach_call_call(1, 0x1024a88, 0, 0, 1) + thanks + same as youpi observed, the requested size for the mapping is 0 + tschwinge: thanks + braunr: Anything else you'd like to see before I reboot? + tschwinge: no, that's enough for now, and the other kind of info + i'd like are much more difficult to obtain + if we still have the problem once a small patch to prevent null + size is applied, then it'll be worth looking more into it + isn't it possible to find out who called with that size? + not easy, no + it's also likely that the call that fails isn't the first one + ah sure + braunr: making mmap reject 0 size length could help? posix says + such size should be rejected straight away + 17:09 < braunr> if we still have the problem once a small patch to + prevent null size is applied, then it'll be worth looking more into it + that's the idea + making faulty processes choke on it should work fine :) + «If len is zero, mmap() shall fail and no mapping shall be + established.» + braunr: should i cook up such patch for mmap? + no, the change must be applied in gnumach + sure, but that could simply such condition in mmap (ie avoiding + to call io_map on a file) + such calls are erroneous and rare, i don't see the need + ok + i bet it comes from the exec server anyway :p + braunr: Is the mmap with size 0 already a reproducible testcase + you can use for the diff != 0 assertion? + Otherwise I'd have a reproducer now. + tschwinge: i'm not sure but probably yes + braunr: Otherwise, take GDB sources, then: gcc -fsplit-stack + gdb/testsuite/gdb.base/morestack.c && ./a.out + I have not looked what exactly this does; I think -fsplit-stack + is not really implemented for us (needs something in libgcc we might not + have), is on my GCC TODO list already. + tschwinge: interesting too :) + + +### IRC, freenode, #hurd, 2012-11-19 + + braunr: Hmm, I have now hit the diff != 0 GNU Mach assertion + failure during some GCC invocation (GCC testsuite) that does not relate + to -fsplit-stack (as the others before always have). + Reproduced: + /media/erich/home/thomas/tmp/gcc/hurd/master.build/gcc/xgcc + -B/media/erich/home/thomas/tmp/gcc/hurd/master.build/gcc/ + /home/thomas/tmp/gcc/hurd/master/gcc/testsuite/gcc.dg/torture/pr42878-1.c + -fno-diagnostics-show-caret -O2 -flto -fuse-linker-plugin + -fno-fat-lto-objects -fcompare-debug -S -o pr42878-1.s + Will check whether it's the same backtrace in GNU Mach. + Yes, same. + tschwinge: as youpi seems quite busy these days, i'll cook a patch + and commit it directly + braunr: Thanks! I have, by the way, confirmed that the + following is enough to trigger the issue: vm_map(mach_task_self(), 0, 0, + 0, 1, 0, 0, 0, 0, 0, 0); + ... and before the allocator patch, GNU Mach did accept that + and return 0 -- though I did not check what effect it actually has. (And + I don't think it has any useful one.) I'm also reading that as of lately + (Linux 2.6.12), mmap (length = 0) is to return EINVAL, which I think is + the foremost user of vm_map. + tschwinge: posix too says to return EINVAL for length = 0 + yes, we checked that earlier with youpi + +[[!message-id "87sj8522zx.fsf@kepler.schwinge.homeip.net"]]. + + tschwinge: well, actually your patch is what i had in mind + (although i'd like one in vm_map_enter to catch wrong kernel requests + too) + tschwinge: i'll work on it tonight, and do some testing to make + sure we don't regress critical stuff (exec is another major direct user + of vm_map iirc) + braunr: Oh, OK. :-) -- cgit v1.2.3