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 --- open_issues/gnumach_vm_map_red-black_trees.mdwn | 346 ------------------------ 1 file changed, 346 deletions(-) delete mode 100644 open_issues/gnumach_vm_map_red-black_trees.mdwn (limited to 'open_issues/gnumach_vm_map_red-black_trees.mdwn') diff --git a/open_issues/gnumach_vm_map_red-black_trees.mdwn b/open_issues/gnumach_vm_map_red-black_trees.mdwn deleted file mode 100644 index 53ff66c5..00000000 --- a/open_issues/gnumach_vm_map_red-black_trees.mdwn +++ /dev/null @@ -1,346 +0,0 @@ -[[!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