From 9667351422dec0ca40a784a08dec7ce128482aba Mon Sep 17 00:00:00 2001
From: Thomas Schwinge <tschwinge@gnu.org>
Date: Wed, 10 Jul 2013 23:39:29 +0200
Subject: IRC.
---
microkernel/mach/deficiencies.mdwn | 1427 ++++++++++++++++++++++-
microkernel/mach/gnumach/memory_management.mdwn | 15 +
2 files changed, 1440 insertions(+), 2 deletions(-)
(limited to 'microkernel')
diff --git a/microkernel/mach/deficiencies.mdwn b/microkernel/mach/deficiencies.mdwn
index 1294b8b3..d1cdeb54 100644
--- a/microkernel/mach/deficiencies.mdwn
+++ b/microkernel/mach/deficiencies.mdwn
@@ -260,9 +260,9 @@ License|/fdl]]."]]"""]]
solve a number of problems... I just wonder how many others it would open
-# IRC, freenode, #hurd, 2012-09-04
+# X15
-X15
+## IRC, freenode, #hurd, 2012-09-04
<braunr> it was intended as a mach clone, but now that i have better
knowledge of both mach and the hurd, i don't want to retain mach
@@ -767,3 +767,1426 @@ In context of [[open_issues/multithreading]] and later [[open_issues/select]].
<braunr> imo, a rewrite is more appropriate
<braunr> sometimes, things done in x15 can be ported to the hurd
<braunr> but it still requires a good deal of effort
+
+
+## IRC, freenode, #hurd, 2013-04-26
+
+ <bddebian> braunr: Did I see that you are back tinkering with X15?
+ <braunr> well yes i am
+ <braunr> and i'm very satisfied with it currently, i hope i can maintain
+ the same level of quality in the future
+ <braunr> it can already handle hundreds of processors with hundreds of GB
+ of RAM in a very scalable way
+ <braunr> most algorithms are O(1)
+ <braunr> even waking up multiple threads is O(1) :)
+ <braunr> i'd like to implement rcu this summer
+ <bddebian> Nice. When are you gonna replace gnumach? ;-P
+ <braunr> never
+ <braunr> it's x15, not x15mach now
+ <braunr> it's not meant to be compatible
+ <bddebian> Who says it has to be compatible? :)
+ <braunr> i don't know, my head
+ <braunr> the point is, the project is about rewriting the hurd now, not
+ just the kernel
+ <braunr> new kernel, new ipc, new interfaces, new libraries, new everything
+ <bddebian> Yikes, now that is some work. :)
+ <braunr> well yes and no
+ <braunr> ipc shouldn't be that difficult/long, considering how simple i
+ want the interface to be
+ <bddebian> Cool.
+ <braunr> networking and drivers will simply be reused from another code
+ base like dde or netbsd
+ <braunr> so besides the kernel, it's a few libraries (e.g. a libports like
+ library), sysdeps parts in the c library, and a file system
+ <bddebian> For inclusion in glibc or are you not intending on using glibc?
+ <braunr> i intend to use glibc, but not for upstream integration, if that's
+ what you meant
+ <braunr> so a private, local branch i assume
+ <braunr> i expect that part to be the hardest
+
+
+## IRC, freenode, #hurd, 2013-05-02
+
+ <zacts> braunr: also, will propel/x15 use netbsd drivers or netdde linux
+ drivers?
+ <zacts> or both?
+ <braunr> probably netbsd drivers
+ <zacts> and if netbsd, will it utilize rump?
+ <braunr> i don't know yet
+ <zacts> ok
+ <braunr> device drivers and networking will arrive late
+ <braunr> the system first has to run in ram, with a truely configurable
+ boot process
+ <braunr> (i.e. a boot process that doesn't use anything static, and can
+ boot from either disk or network)
+ <braunr> rump looks good but it still requires some work since it doesn't
+ take care of messaging as well as we'd want
+ <braunr> e.g. signal relaying isn't that great
+ <zacts> I personally feel like using linux drivers would be cool, just
+ because linux supports more hardware than netbsd iirc..
+ <mcsim> zacts: But it could be problematic as you should take quite a lot
+ code from linux kernel to add support even for a single driver.
+ <braunr> zacts: netbsd drivers are far more portable
+ <zacts> oh wow, interesting. yeah I did have the idea that netbsd would be
+ more portable.
+ <braunr> mcsim: that doesn't seem to be as big a problem as you might
+ suggest
+ <braunr> the problem is providing the drivers with their requirements
+ <braunr> there are a lot of different execution contexts in linux (hardirq,
+ softirq, bh, threads to name a few)
+ <braunr> being portable (as implied in netbsd) also means being less
+ demanding on the execution context
+ <braunr> which allows reusing code in userspace more easily, as
+ demonstrated by rump
+ <braunr> i don't really care about extensive hardware support, since this
+ is required only for very popular projects such as linux
+ <braunr> and hardware support actually comes with popularity (the driver
+ code base is related with the user base)
+ <zacts> so you think that more users will contribute if the projects takes
+ off?
+ <braunr> i care about clean and maintainable code
+ <braunr> well yes
+ <zacts> I think that's a good attitude
+ <braunr> what i mean is, there is no need for extensive hardware support
+ <mcsim> braunr: TBH, I did not really got idea of rump. Do they try to run
+ the whole kernel or some chosen subsystems as user tasks?
+ <braunr> mcsim: some subsystems
+ <braunr> well
+ <braunr> all the subsystems required by the code they actually want to run
+ <braunr> (be it a file system or a network stack)
+ <mcsim> braunr: What's the difference with dde?
+ <braunr> it's not kernel oriented
+ <mcsim> what do you mean?
+ <braunr> it's not only meant to run on top of a microkernel
+ <braunr> as the author named it, it's "anykernel"
+ <braunr> if you remember at fosdem, he run code inside a browser
+ <braunr> ran*
+ <braunr> and also, netbsd drivers wouldn't restrict the license
+ <braunr> although not a priority, having a (would be) gnu system under
+ gplv3+ would be nice
+ <zacts> that would be cool
+ <zacts> x15 is already gplv3+
+ <zacts> iirc
+ <braunr> yes
+ <zacts> cool
+ <zacts> yeah, I would agree netbsd drivers do look more attractive in that
+ case
+ <braunr> again, that's clearly not the main reason for choosing them
+ <zacts> ok
+ <braunr> it could also cause other problems, such as accepting a bsd
+ license when contributing back
+ <braunr> but the main feature of the hurd isn't drivers, and what we want
+ to protect with the gpl is the main features
+ <zacts> I see
+ <braunr> drivers, as well as networking, would be third party code, the
+ same way you run e.g. firefox on linux
+ <braunr> with just a bit of glue
+ <zacts> braunr: what do you think of the idea of being able to do updates
+ for propel without rebooting the machine? would that be possible down the
+ road?
+ <braunr> simple answer: no
+ <braunr> that would probably require persistence, and i really don't want
+ that
+ <zacts> does persistence add a lot of complexity to the system?
+ <braunr> not with the code, but at execution, yes
+ <zacts> interesting
+ <braunr> we could add per-program serialization that would allow it but
+ that's clearly not a priority for me
+ <braunr> updating with a reboot is already complex enough :)
+
+
+## IRC, freenode, #hurd, 2013-05-09
+
+ <braunr> the thing is, i consider the basic building blocks of the hurd too
+ crappy to build anything really worth such effort over them
+ <braunr> mach is crappy, mig is crappy, signal handling is crappy, hurd
+ libraries are ok but incur a lot of contention, which is crappy today
+ <bddebian> Understood but it is all we have currently.
+ <braunr> i know
+ <braunr> and it's good as a prototype
+ <bddebian> We have already had L4, viengoos, etc and nothing has ever come
+ to fruition. :(
+ <braunr> my approach is compeltely different
+ <braunr> it's not a new design
+ <braunr> a few things like ipc and signals are redesigned, but that's minor
+ compared to what was intended for hurdng
+ <braunr> propel is simply meant to be a fast, scalable implementation of
+ the hurd high level architecture
+ <braunr> bddebian: imagine a mig you don't fear using
+ <braunr> imagine interfaces not constrained to 100 calls ...
+ <braunr> imagine per-thread signalling from the start
+ <bddebian> braunr: I am with you 100% but it's vaporware so far.. ;-)
+ <braunr> bddebian: i'm just explaining why i don't want to work on large
+ scale projects on the hurd
+ <braunr> fixing local bugs is fine
+ <braunr> fixing paging is mandatory
+ <braunr> usb could be implemented with dde, perhaps by sharing the pci
+ handling code
+ <braunr> (i.e. have one big dde server with drivers inside, a bit ugly but
+ straightforward compared to a full fledged pci server)
+ <bddebian> braunr: But this is the problem I see. Those of you that have
+ the skills don't have the time or energy to put into fixing that kind of
+ stuff.
+ <bddebian> braunr: That was my thought.
+ <braunr> bddebian: well i have time, and i'm currently working :p
+ <braunr> but not on that
+ <braunr> bddebian: also, it won't be vaporware for long, i may have ipc
+ working well by the end of the year, and optimized and developer-friendly
+ by next year)
+
+
+## IRC, freenode, #hurd, 2013-06-05
+
+ <braunr> i'll soon add my radix tree with support for lockless lookups :>
+ <braunr> a tree organized based on the values of the keys thmselves, and
+ not how they relatively compare to each other
+ <braunr> also, a tree of arrays, which takes advantage of cache locality
+ without the burden of expensive resizes
+ <arnuld> you seem to be applying good algorithmic teghniques
+ <arnuld> that is nice
+ <braunr> that's one goal of the project
+ <braunr> you can't achieve performance and scalability without the
+ appropriate techniques
+ <braunr> see http://git.sceen.net/rbraun/librbraun.git/blob/HEAD:/rdxtree.c
+ for the existing userspace implementation
+ <arnuld> in kern/work.c I see one TODO "allocate numeric IDs to better
+ identify worker threads"
+ <braunr> yes
+ <braunr> and i'm adding my radix tree now exactly for that
+ <braunr> (well not only, since radix tree will also back VM objects and IPC
+ spaces, two major data structures of the kernel)
+
+
+## IRC, freenode, #hurd, 2013-06-11
+
+ <braunr> and also starting paging anonymous memory in x15 :>
+ <braunr> well, i've merged my radix tree code, made it safe for lockless
+ access (or so i hope), added generic concurrent work queues
+ <braunr> and once the basic support for anonymous memory is done, x15 will
+ be able to load modules passed from grub into userspace :>
+ <braunr> but i've also been thinking about how to solve a major scalability
+ issue with capability based microkernels that noone else seem to have
+ seen or bothered thinking about
+ <braunr> for those interested, the problem is contention at the port level
+ <braunr> unlike on a monolithic kernel, or a microkernel with thread-based
+ ipc such as l4, mach and similar kernels use capabilities (port rights in
+ mach terminology) to communicate
+ <braunr> the kernel then has to "translate" that reference into a thread to
+ process the request
+ <braunr> this is done by using a port set, putting many ports inside, and
+ making worker threads receive messages on the port set
+ <braunr> and in practice, this gets very similar to a traditional thread
+ pool model
+ <braunr> one thread actually waits for a message, while others sit on a
+ list
+ <braunr> when a message arrives, the receiving thread wakes another from
+ that list so it receives the next message
+ <braunr> this is all done with a lock
+ <bddebian> Maybe they thought about it but couldn't or were to lazy to find
+ a better way? :)
+ <mcsim> braunr: what do you mean under "unlike .... a microkernel with
+ thread-based ipc such as l4, mach and similar kernels use capabilities"?
+ L4 also has capabilities.
+ <braunr> mcsim: not directly
+ <braunr> capabilities are implemented by a server on top of l4
+ <braunr> unless it's OKL4 or another variant with capabilities back in the
+ kernel
+ <braunr> i don't know how fiasco does it
+ <braunr> so the problem with this lock is potentially very heavy contention
+ <braunr> and contention in what is the equivalent of a system call ..
+ <braunr> it's also hard to make it real-time capable
+ <braunr> for example, in qnx, they temporarily apply priority inheritance
+ to *every* server thread since they don't know which one is going to be
+ receiving next
+ <mcsim> braunr: in fiasco you have capability pool for each thread and this
+ pool is stored in tread control block. When one allocates capability
+ kernel just marks slot in a pool as busy
+ <braunr> mcsim: ok but, there *is* a thread for each capability
+ <braunr> i mean, when doing ipc, there can only be one thread receiving the
+ message
+ <braunr> (iirc, this was one of the big issue for l4-hurd)
+ <mcsim> ok. i see the difference.
+ <braunr> well i'm asking
+ <braunr> i'm not so sure about fiasco
+ <braunr> but that's what i remember from the generic l4 spec
+ <mcsim> sorry, but where is the question?
+ <braunr> 16:04 < braunr> i mean, when doing ipc, there can only be one
+ thread receiving the message
+ <mcsim> yes, you specify capability to thread you want to send message to
+ <braunr> i'll rephrase:
+ <braunr> when you send a message, do you invoke a capability (as in mach),
+ or do you specify the receiving thread ?
+ <mcsim> you specify a thread
+ <braunr> that's my point
+ <mcsim> but you use local name (that is basically capability)
+ <braunr> i see
+ <braunr> from wikipedia: "Furthermore, Fiasco contains mechanisms for
+ controlling communication rights as well as kernel-level resource
+ consumption"
+ <braunr> not certain that's what it refers to, but that's what i understand
+ from it
+ <braunr> more capability features in the kernel
+ <braunr> but you still send to one thread
+ <mcsim> yes
+ <braunr> that's what makes it "easily" real time capable
+ <braunr> a microkernel that would provide mach-like semantics
+ (object-oriented messaging) but without contention at the messsage
+ passing level (and with resource preallocation for real time) would be
+ really great
+ <braunr> bddebian: i'm not sure anyone did
+ <bddebian> braunr: Well you can be the hero!! ;)
+ <braunr> the various papers i could find that were close to this subject
+ didn't take contention into account
+ <braunr> exception for network-distributed ipc on slow network links
+ <braunr> bddebian: eh
+ <braunr> well i think it's doable acctually
+ <mcsim> braunr: can you elaborate on where contention is, because I do not
+ see this clearly?
+ <braunr> mcsim: let's take a practical example
+ <braunr> a file system such as ext2fs, that you know well enough
+ <braunr> imagine a large machine with e.g. 64 processors
+ <braunr> and an ignorant developer like ourselves issuing make -j64
+ <braunr> every file access performed by the gcc tools will look up files,
+ and read/write/close them, concurrently
+ <braunr> at the server side, thread creation isn't a problem
+ <braunr> we could have as many threads as clients
+ <braunr> the problem is the port set
+ <braunr> for each port class/bucket (let's assume they map 1:1), a port set
+ is created, and all receive rights for the objects managed by the server
+ (the files) are inserted in this port set
+ <braunr> then, the server uses ports_manage_port_operations_multithread()
+ to service requests on that port set
+ <braunr> with as many threads required to process incoming messages, much
+ the same way a work queue does it
+ <braunr> but you can't have *all* threads receiving at the same time
+ <braunr> there can only be one
+ <braunr> the others are queued
+ <braunr> i did a change about the queue order a few months ago in mach btw
+ <braunr> mcsim: see ipc/ipc_thread.c in gnumach
+ <braunr> this queue is shared and must be modified, which basically means a
+ lock, and contention
+ <braunr> so the 64 concurrent gcc processes will suffer from contenion at
+ the server while they're doing something similar to a system call
+ <braunr> by that, i mean, even before the request is received
+ <braunr> mcsim: if you still don't understand, feel free to ask
+ <mcsim> braunr: I'm thinking on it :) give me some time
+ <braunr> "Fiasco.OC is a third generation microkernel, which evolved from
+ its predecessor L4/Fiasco. Fiasco.OC is capability based"
+ <braunr> ok
+ <braunr> so basically, there are no more interesting l4 variants strictly
+ following the l4v2 spec any more
+ <braunr> "The completely redesigned user-land environment running on top of
+ Fiasco.OC is called L4 Runtime Environment (L4Re). It provides the
+ framework to build multi-component systems, including a client/server
+ communication framework"
+ <braunr> so yes, client/server communication is built on top of the kernel
+ <braunr> something i really want to avoid actually
+ <mcsim> So when 1 core wants to pull something out of queue it has to lock
+ it, and the problem arrives when other 63 cpus are waiting in the same
+ lock. Right?
+ <braunr> mcsim: yes
+ <mcsim> could this be solved by implementing per cpu queues? Like in slab
+ allocator
+ <braunr> solved, no
+ <braunr> reduced, yes
+ <braunr> by using multiple port sets, each with their own thread pool
+ <braunr> but this would still leave core problems unsolved
+ <braunr> (those making real-time hard)
+ <mcsim> to make it real-time is not really essential to solve this problem
+ <braunr> that's the other way around
+ <mcsim> we just need to guarantee that locking protocol is fair
+ <braunr> solving this problem is required for quality real-time
+ <braunr> what you refer to is similar to what i described in qnx earlier
+ <braunr> it's ugly
+ <braunr> keep in mind that message passing is the equivalent of system
+ calls on monolithic kernels
+ <braunr> os ideally, we'd want something as close as possible to an
+ actually system call
+ <braunr> so*
+ <braunr> mcsim: do you see why it's ugly ?
+ <mcsim> no i meant exactly opposite, I meant to use some deterministic
+ locking protocol
+ <braunr> please elaborate
+ <braunr> because what qnx does is deterministic
+ <mcsim> We know in what sequences threads will acquire the lock, so we will
+ not have to apply inheritance to all threads
+ <braunr> hwo do you know ?
+ <mcsim> there are different approaches, like you use ticket system or MCS
+ lock (http://portal.acm.org/citation.cfm?id=103729)
+ <braunr> that's still locking
+ <braunr> a system call has 0 contention
+ <braunr> 0 potential contention
+ <mcsim> in linux?
+ <braunr> everywhere i assume
+ <mcsim> than why do they need locks?
+ <braunr> they need locks after the system call
+ <braunr> the system call itself is a stupid trap that makes the thread
+ "jump" in the kernel
+ <braunr> and the reason why it's so simple is the same as in fiasco:
+ threads (clients) communicate directly with the "server thread"
+ (themselves in kernel mode)
+ <braunr> so 1/ they don't go through a capability or any other abstraction
+ <braunr> and 2/ they're even faster than on fiasco because they don't need
+ to find the destination, it's implied by the trap mechanism)
+ <braunr> 2/ is only an optimization that we can live without
+ <braunr> but 1/ is a serious bottleneck for microkernels
+ <mcsim> Do you mean that there system call that process without locks or do
+ you mean that there are no system calls that use locks?
+ <braunr> this is what makes papers such as
+ https://www.kernel.org/doc/ols/2007/ols2007v1-pages-251-262.pdf valid
+ <braunr> i mean the system call (the mechanism used to query system
+ services) doesn't have to grab any lock
+ <braunr> the idea i have is to make the kernel transparently (well, as much
+ as it can be) associate a server thread to a client thread at the port
+ level
+ <braunr> at the server side, it would work practically the same
+ <braunr> the first time a server thread services a request, it's
+ automatically associated to a client, and subsequent request will
+ directly address this thread
+ <braunr> when the client is destroyed, the server gets notified and
+ destroys the associated server trhead
+ <braunr> for real-time tasks, i'm thinking of using a signal that gets sent
+ to all servers, notifying them of the thread creation so that they can
+ preallocate the server thread
+ <braunr> or rather, a signal to all servers wishing to be notified
+ <braunr> or perhaps the client has to reserve the resources itself
+ <braunr> i don't know, but that's the idea
+ <mcsim> and who will send this signal?
+ <braunr> the kernel
+ <braunr> x15 will provide unix like signals
+ <braunr> but i think the client doing explicit reservation is better
+ <braunr> more complicated, but better
+ <braunr> real time developers ought to know what they're doing anyway
+ <braunr> mcsim: the trick is using lockless synchronization (like rcu) at
+ the port so that looking up the matching server thread doesn't grab any
+ lock
+ <braunr> there would still be contention for the very first access, but
+ that looks much better than having it every time
+ <braunr> (potential contention)
+ <braunr> it also simplifies writing servers a lot, because it encourages
+ the use of a single port set for best performance
+ <braunr> instead of burdening the server writer with avoiding contention
+ with e.g. a hierarchical scheme
+ <mcsim> "looking up the matching server" -- looking up where?
+ <braunr> in the port
+ <mcsim> but why can't you just take first?
+ <braunr> that's what triggers contention
+ <braunr> you have to look at the first
+ <mcsim> > (16:34:13) braunr: mcsim: do you see why it's ugly ?
+ <mcsim> BTW, not really
+ <braunr> imagine serveral clients send concurrently
+ <braunr> mcsim: well, qnx doesn't do it every time
+ <braunr> qnx boosts server threads only when there are no thread currently
+ receiving, and a sender with a higher priority arrives
+ <braunr> since qnx can't know which server thread is going to be receiving
+ next, it boosts every thread
+ <braunr> boosting priority is expensive, and boosting everythread is linear
+ with the number of threads
+ <braunr> so on a big system, it would be damn slow for a system call :)
+ <mcsim> ok
+ <braunr> and grabbing "the first" can't be properly done without
+ serialization
+ <braunr> if several clients send concurrently, only one of them gets
+ serviced by the "first server thread"
+ <braunr> the second client will be serviced by the "second" (or the first
+ if it came back)
+ <braunr> making the second become the first (i call it the manager) must be
+ atomic
+ <braunr> that's the core of the problem
+ <braunr> i think it's very important because that's currently one of the
+ fundamental differences wih monolithic kernels
+ <mcsim> so looking up for server is done without contention. And just
+ assigning task to server requires lock, right?
+ <braunr> mcsim: basically yes
+ <braunr> i'm not sure it's that easy in practice but that's what i'll aim
+ at
+ <braunr> almost every argument i've read about microkernel vs monolithic is
+ full of crap
+ <mcsim> Do you mean lock on the whole queue or finer grained one?
+ <braunr> the whole port
+ <braunr> (including the queue)
+ <mcsim> why the whole port?
+ <braunr> how can you make it finer ?
+ <mcsim> is queue a linked list?
+ <braunr> yes
+ <mcsim> than can we just lock current element in the queue and elements
+ that point to current
+ <braunr> that's two lock
+ <braunr> and every sender will want "current"
+ <braunr> which then becomes coarse grained
+ <mcsim> but they want different current
+ <braunr> let's call them the manager and the spare threads
+ <braunr> yes, that's why there is a lock
+ <braunr> so they don't all get the same
+ <braunr> the manager is the one currently waiting for a message, while
+ spare threads are available but not doing anything
+ <braunr> when the manager finally receives a message, it takes the first
+ spare, which becomes the new manager
+ <braunr> exactly like in a common thread pool
+ <braunr> so what are you calling current ?
+ <mcsim> we have in a port queue of threads that wait for message: t1 -> t2
+ -> t3 -> t4; kernel decided to assign message to t3, than t3 and t2 are
+ locked.
+ <braunr> why not t1 and t2 ?
+ <mcsim> i was calling t3 in this example as current
+ <mcsim> some heuristics
+ <braunr> yeah well no
+ <braunr> it wouldn't be deterministic then
+ <mcsim> for instance client runs on core 3 and wants server that also runs
+ on core 3
+ <braunr> i really want the operation as close as a true system call as
+ possible, so O(1)
+ <braunr> what if there are none ?
+ <mcsim> it looks up forward up to the end of queue: t1->t2->t4; takes t4
+ <mcsim> than it starts from the beginning
+ <braunr> that becomes linear in the worst case
+ <mcsim> no
+ <braunr> so 4095 attempts on a 4096 cpus machine
+ <braunr> ?
+ <mcsim> you're right
+ <braunr> unfortunately :/
+ <braunr> a per-cpu scheme could be good
+ <braunr> and applicable
+ <braunr> with much more thought
+ <braunr> and the problem is that, unlike the kernel, which is naturally a
+ one thread per cpu server, userspace servers may have less or more
+ threads than cpu
+ <braunr> possibly unbalanced too
+ <braunr> so it would result in complicated code
+ <braunr> one good thing with microkernels is that they're small
+ <braunr> they don't pollute the instruction cache much
+ <braunr> keeping the code small is important for performance too
+ <braunr> so forgetting this kind of optimization makes for not too
+ complicated code, and we rely on the scheduler to properly balance
+ threads
+ <braunr> mcsim: also note that, with your idea, the worst cast is twice
+ more expensive than a single lock
+ <braunr> and on a machine with few processors, this worst case would be
+ likely
+ <mcsim> so, you propose every time try to take first server from the queue?
+ <mcsim> braunr: ^
+ <braunr> no
+ <braunr> that's what is done already
+ <braunr> i propose doing that the first time a client sends a message
+ <braunr> but then, the server thread that replied becomes strongly
+ associated to that client (it cannot service requests from other clients)
+ <braunr> and it can be recycled only when the client dies
+ <braunr> (which generates a signal indicating the server it can now recycle
+ the server thread)
+ <braunr> (a signal similar to the no-sender or dead-name notifications in
+ mach)
+ <braunr> that signal would be sent from the kernel, in the traditional unix
+ way (i.e. no dedicated signal thread since it would be another source of
+ contention)
+ <braunr> and the server thread would directly receive it, not interfering
+ with the other threads in the server in any way
+ <braunr> => contention on first message only
+ <braunr> now, for something like make -j64, which starts a different
+ process for each compilation (itself starting subprocesses for
+ preprocessing/compiling/assembling)
+ <braunr> it wouldn't be such a big win
+ <braunr> so even this first access should be optimized
+ <braunr> if you ever get an idea, feel free to share :)
+ <mcsim> May mach block thread when it performs asynchronous call?
+ <mcsim> braunr: ^
+ <braunr> sure
+ <braunr> but that's unrelated
+ <braunr> in mach, a sender is blocked only when the message queue is full
+ <mcsim> So we can introduce per cpu queues at the sender side
+ <braunr> (and mach_msg wasn't called in non blocking mode obviously)
+ <braunr> no
+ <braunr> they need to be delivered in order
+ <mcsim> In what order?
+ <braunr> messages can't be reorder once queued
+ <braunr> reordered
+ <braunr> so fifo order
+ <braunr> if you break the queue in per cpu queues, you may break that, or
+ need work to rebuild the order
+ <braunr> which negates the gain from using per cpu queues
+ <mcsim> Messages from the same thread will be kept in order
+ <braunr> are you sure ?
+ <braunr> and i'm not sure it's enough
+ <mcsim> thes cpu queues will be put to common queue once context switch
+ occurs
+ <braunr> *all* messages must be received in order
+ <mcsim> these*
+ <braunr> uh ?
+ <braunr> you want each context switch to grab a global lock ?
+ <mcsim> if you have parallel threads that send messages that do not have
+ dependencies than they are unordered
+ <mcsim> always
+ <braunr> the problem is they might
+ <braunr> consider auth for example
+ <braunr> you have one client attempting to authenticate itself to a server
+ through the auth server
+ <braunr> if message order is messed up, it just won't work
+ <braunr> but i don't have this problem in x15, since all ipc (except
+ signals) is synchronous
+ <mcsim> but it won't be messed up. You just "send" messages in O(1), but
+ than you put these messages that are not actually sent in queue all at
+ once
+ <braunr> i think i need more details please
+ <mcsim> you have lock on the port as it works now, not the kernel lock
+ <mcsim> the idea is to batch these calls
+ <braunr> i see
+ <braunr> batching can be effective, but it would really require queueing
+ <braunr> x15 only queues clients when there is no receiver
+ <braunr> i don't think batching can be applied there
+ <mcsim> you batch messages only from one client
+ <braunr> that's what i'm saying
+ <mcsim> so client can send several messages during his time slice and than
+ you put them into queue all together
+ <braunr> x15 ipc is synchronous, no more than 1 message per client at any
+ time
+ <braunr> there also are other problems with this strategy
+ <braunr> problems we have on the hurd, such as priority handling
+ <braunr> if you delay the reception of messages, you also delay priority
+ inheritance to the server thread
+ <braunr> well not the reception, the queueing actually
+ <braunr> but since batching is about delaying that, it's the same
+ <mcsim> if you use synchronous ipc than there is no sence in batching, at
+ least as I see it.
+ <braunr> yes
+ <braunr> 18:08 < braunr> i don't think batching can be applied there
+ <braunr> and i think sync ipc is the only way to go for a system intended
+ to provide messaging performance as close as possible to the system call
+ <mcsim> do you have as many server thread as many cores you have?
+ <braunr> no
+ <braunr> as many server threads as clients
+ <braunr> which matches the monolithic model
+ <mcsim> in current implementation?
+ <braunr> no
+ <braunr> currently i don't have userspace :>
+ <mcsim> and what is in hurd atm?
+ <mcsim> in gnumach
+ <braunr> asyn ipc
+ <braunr> async
+ <braunr> with message queues
+ <braunr> no priority inheritance, simple "handoff" on message delivery,
+ that's all
+ <anatoly> I managed to read the conversation :-)
+ <braunr> eh
+ <braunr> anatoly: any opinion on this ?
+ <anatoly> braunr: I have no opinion. I understand it partially :-) But
+ association of threads sounds for me as good idea
+ <anatoly> But who am I to say what is good or what is not in that area :-)
+ <braunr> there still is this "first time" issue which needs at least one
+ atomic instruction
+ <anatoly> I see. Does mach do this "first time" thing every time?
+ <braunr> yes
+ <braunr> but gnumach is uniprocessor so it doesn't matter
+ <mcsim> if we have 1:1 relation for client and server threads we need only
+ per-cpu queues
+ <braunr> mcsim: explain that please
+ <braunr> and the problem here is establishing this relation
+ <braunr> with a lockless lookup, i don't even need per cpu queues
+ <mcsim> you said: (18:11:16) braunr: as many server threads as clients
+ <mcsim> how do you create server threads?
+ <braunr> pthread_create
+ <braunr> :)
+ <mcsim> ok :)
+ <mcsim> why and when do you create a server thread?
+ <braunr> there must be at least one unbound thread waiting for a message
+ <braunr> when a message is received, that thread knows it's now bound with
+ a client, and if needed wakes up/spawns another thread to wait for
+ incoming messages
+ <braunr> when it gets a signal indicating the death of the client, it knows
+ it's now unbound, and goes back to waiting for new messages
+ <braunr> becoming either the manager or a spare thread if there already is
+ a manager
+ <braunr> a timer could be used as it's done on the hurd to make unbound
+ threads die after a timeout
+ <braunr> the distinction between the manager and spare threads would only
+ be done at the kernel level
+ <braunr> the server would simply make unbound threads wait on the port set
+ <anatoly> How client sends signal to thread about its death (as I
+ understand signal is not message) (sorry for noob question)
+ <mcsim> in what you described there are no queues at all
+ <braunr> anatoly: the kernel does it
+ <braunr> mcsim: there is, in the kernel
+ <braunr> the queue of spare threads
+ <braunr> anatoly: don't apologize for noob questions eh
+ <anatoly> braunr: is that client is a thread of some user space task?
+ <braunr> i don't think it's a newbie topic at all
+ <braunr> anatoly: a thread
+ <mcsim> make these queue per cpu
+ <braunr> why ?
+ <braunr> there can be a lot less spare threads than processors
+ <braunr> i don't think it's a good idea to spawn one thread per cpu per
+ port set
+ <braunr> on a large machine you'd have tons of useless threads
+ <mcsim> if you have many useless threads, than assign 1 thread to several
+ core, thus you will have twice less threads
+ <mcsim> i mean dynamically
+ <braunr> that becomes a hierarchical model
+ <braunr> it does reduce contention, but it's complicated, and for now i'm
+ not sure it's worth it
+ <braunr> it could be a tunable though
+ <mcsim> if you want something fast you should use something complicated.
+ <braunr> really ?
+ <braunr> a system call is very simple and very fast
+ <braunr> :p
+ <mcsim> why is it fast?
+ <mcsim> you still have a lot of threads in kernel
+ <braunr> but they don't interact during the system call
+ <braunr> the system call itself is usually a simple instruction with most
+ of it handled in hardware
+ <mcsim> if you invoke "write" system call, what do you do in kernel?
+ <braunr> you look up the function address in a table
+ <mcsim> you still have queues
+ <braunr> no
+ <braunr> sorry wait
+ <braunr> by system call, i mean "the transition from userspace to kernel
+ space"
+ <braunr> and the return
+ <braunr> not the service itself
+ <braunr> the equivalent on a microkernel system is sending a message from a
+ client, and receiving it in a server, not processing the request
+ <braunr> ideally, that's what l4 does: switching from one thread to
+ another, as simply and quickly as the hardware can
+ <braunr> so just a context and address space switch
+ <mcsim> at some point you put something in queue even in monolithic kernel
+ and make request to some other kernel thread
+ <braunr> the problem here is the indirection that is the capability
+ <braunr> yes but that's the service
+ <braunr> i don't care about the service here
+ <braunr> i care about how the request reaches the server
+ <mcsim> this division exist for microkernels
+ <mcsim> for monolithic it's all mixed
+ <anatoly> What does thread do when it receive a message?
+ <braunr> anatoly: what it wants :p
+ <braunr> the service
+ <braunr> mcsim: ?
+ <braunr> mixed ?
+ <anatoly> braunr: hm, is it a thread of some server?
+ <mcsim> if you have several working threads in monolithic kernel you have
+ to put request in queue
+ <braunr> anatoly: yes
+ <braunr> mcsim: why would you have working threads ?
+ <mcsim> and there is no difference either you consider it as service or
+ just "transition from userspace to kernel space"
+ <braunr> i mean, it's a good thing to have, they usually do, but they're
+ not implied
+ <braunr> they're completely irrelevant to the discussion here
+ <braunr> of course there is
+ <braunr> you might very well perform system calls that don't involve
+ anything shared
+ <mcsim> you can also have only one working thread in microkernel
+ <braunr> yes
+ <mcsim> and all clients will wait for it
+ <braunr> you're mixing up work queues in the discussion here
+ <braunr> server threads are very similar to a work queue, yes
+ <mcsim> but you gave me an example with 64 cores and each core runs some
+ server thread
+ <braunr> they're a thread pool handling requests
+ <mcsim> you can have only one thread in a pool
+ <braunr> they have to exist in a microkernel system to provide concurrency
+ <braunr> monolithic kernels can process concurrently without them though
+ <mcsim> why?
+ <braunr> because on a monolithic system, _every client thread is its own
+ server_
+ <braunr> a thread making a system call is exactly like a client requesting
+ a service
+ <braunr> on a monolithic kernel, the server is the kernel
+ <braunr> and it *already* has as many threads as clients
+ <braunr> and that's pretty much the only thing beautiful about monolithic
+ kernels
+ <mcsim> right
+ <mcsim> have to think about it :)
+ <braunr> that's why they scale so easily compared to microkernel based
+ systems
+ <braunr> and why l4 people chose to have thread-based ipc
+ <braunr> but this just moves the problems to an upper level
+ <braunr> and is probably why they've realized one of the real values of
+ microkernel systems is capabilities
+ <braunr> and if you want to make them fast enough, they should be handled
+ directly by the kernel
+
+
+## IRC, freenode, #hurd, 2013-06-13
+
+ <bddebian> Heya Richard. Solve the worlds problems yet? :)
+ <kilobug> bddebian: I fear the worlds problems are NP-complete ;)
+ <bddebian> heh
+ <braunr> bddebian: i wish i could solve mine at least :p
+ <bddebian> braunr: I meant the contention thing you were discussing the
+ other day :)
+ <braunr> bddebian: oh
+ <braunr> i have a solution that improves the behaviour yes, but there is
+ still contention the first time a thread performs an ipc
+ <bddebian> Any thread or the first time there is contention?
+ <braunr> there may be contention the first time a thread sends a message to
+ a server
+ <braunr> (assuming a server uses a single port set to receive requests)
+ <bddebian> Oh aye
+ <braunr> i think it's as much as can be done considering there is a
+ translation from capability to thread
+ <braunr> other schemes are just too heavy, and thus don't scale well
+ <braunr> this translation is one of the two important nice properties of
+ microkernel based systems, and translations (or indrections) usually have
+ a cost
+ <braunr> so we want to keep them
+ <braunr> and we have to accept that cost
+ <braunr> the amount of code in the critical section should be so small it
+ should only matter for machines with several hundreds or thousands
+ processors
+ <braunr> so it's not such a bit problem
+ <bddebian> OK
+ <braunr> but it would have been nice to have an additional valid
+ theoretical argument to explain how ipc isn't that slow compared to
+ system calls
+ <braunr> s/bit/big/
+ <braunr> people keep saying l4 made ipc as fast as system calls without
+ taking that stuff into account
+ <braunr> which makes the community look lame in the eyes of those familiar
+ with it
+ <bddebian> heh
+ <braunr> with my solution, persistent applications like databases should
+ perform as fast as on an l4 like kernel
+ <braunr> but things like parallel builds, which start many different
+ processes for each file, will suffer a bit more from contention
+ <braunr> seems like a fair compromise to me
+ <bddebian> Aye
+ <braunr> as mcsim said, there is a lot of contention about everywhere in
+ almost every application
+ <braunr> and lockless stuff is hard to correctly implement
+ <braunr> os it should be all right :)
+ <braunr> ... :)
+ <mcsim> braunr: What if we have at least 1 thread for each core that stay
+ in per-core queue. When we decide to kill a thread and this thread is
+ last in a queue we replace it with load balancer. This is still worse
+ than with monolithic kernel, but it is simplier to implement from kernel
+ perspective.
+ <braunr> mcsim: it doesn't scale well
+ <braunr> you end up with one thread per cpu per port set
+ <mcsim> load balancer is only one thread
+ <mcsim> why would it end up like you said?
+ <braunr> remember the goal is to avoid contention
+ <braunr> your proposition is to set per cpu queues
+ <braunr> the way i understand what you said, it means clients will look up
+ a server thread in these queues
+ <braunr> one of them actually, the one for the cpu they're currently
+ running one
+ <braunr> so 1/ it disables migration
+ <braunr> or 2/ you have one server thread per client per cpu
+ <braunr> i don't see what a "load balancer" would do here
+ <mcsim> client either finds server thread without contention or it sends
+ message to load balancer, that redirects message to thread from global
+ queue. Where global queue is concatenation of local ones.
+ <braunr> you can't concatenate local queues in a global one
+ <braunr> if you do that, you end up with a global queue, and a global lock
+ again
+ <mcsim> not global
+ <mcsim> load balancer is just one
+ <braunr> then you serialize all remote messaging through a single thread
+ <mcsim> so contention will be only among local thread and load balancer
+ <braunr> i don't see how it doesn't make the load balancer global
+ <mcsim> it makes
+ <mcsim> but it just makes bootstraping harder
+ <braunr> i'm not following
+ <braunr> and i don't see how it improves on my solution
+ <mcsim> in your example with make -j64 very soon there will be local
+ threads at any core
+ <braunr> yes, hence the lack of scalability
+ <mcsim> but that's your goal: create as many server thread as many clients
+ you have, isn't it?
+ <braunr> your solution may create a lot more
+ <braunr> again, one per port set (or server) per cpu
+ <braunr> imagine this worst case: you have a single client with one thread
+ <braunr> which gets migrated to every cpu on the machine
+ <braunr> it will spawn one thread per cpu at the server side
+ <mcsim> why would it migrate all the time?
+ <braunr> it's a worst case
+ <braunr> if it can migrate, consider it will
+ <braunr> murphy's law, you know
+ <braunr> also keep in mind contention doesn't always occur with a global
+ lock
+ <braunr> i'm talking about potential contention
+ <braunr> and same things apply: if it can happen, consider it will
+ <mcsim> than we can make load balancer that also migrates server threads
+ <braunr> ok so in addition to worker threads, we'll add an additional per
+ server load balancer which may have to lock several queues at once
+ <braunr> doesn't it feel completely overkill to you ?
+ <mcsim> load balancer is global, not per-cpu
+ <mcsim> there could be contention for it
+ <braunr> again, keep in mind this problem becomes important for several
+ hundreds processors, not below
+ <braunr> yes but it has to balance
+ <braunr> which means it has to lock cpu queues
+ <braunr> and at least two of them to "migrate" server threads
+ <braunr> and i don't know why it would do that
+ <braunr> i don't see the point of the load balancer
+ <mcsim> so, you start make -j64. First 64 invocations of gcc will suffer
+ from contention for load balancer, but later on it will create enough
+ server threads and contention will disappear
+ <braunr> no
+ <braunr> that's the best case : there is always one server thread per cpu
+ queue
+ <braunr> how do you guarantee your 64 server threads don't end up in the
+ same cpu queue ?
+ <braunr> (without disabling migration)
+ <mcsim> load balancer will try to put some server thread to the core where
+ load balancer was invoked
+ <braunr> so there is no guarantee
+ <mcsim> LB can pin server thread
+ <braunr> unless we invoke it regularly, in a way similar to what is already
+ done in the SMP scheduler :/
+ <braunr> and this also means one balancer per cpu then
+ <mcsim> why one balance per cpu?
+ <braunr> 15:56 < mcsim> load balancer will try to put some server thread to
+ the core where load balancer was invoked
+ <braunr> why only where it was invoked ?
+ <mcsim> because it assumes that if some one asked for server at core x, it
+ most likely will ask for the same service from the same core
+ <braunr> i'm not following
+ <mcsim> LB just tries to prefetch were next call will be
+ <braunr> what you're describing really looks like per-cpu work queues ...
+ <braunr> i don't see how you make sure there aren't too many threads
+ <braunr> i don't see how a load balancer helps
+ <braunr> this is just an heuristic
+ <mcsim> when server thread is created?
+ <mcsim> who creates it?
+ <braunr> and it may be useless, depending on how threads are migrated and
+ when they call the server
+ <braunr> same answer as yesterday
+ <braunr> there must be at least one thread receiving messages on a port set
+ <braunr> when a message arrives, if there aren't any spare threads, it
+ spawns one to receive messages while it processes the request
+ <mcsim> at the moment server threads are killed by timeout, right?
+ <braunr> yes
+ <braunr> well no
+ <braunr> there is a debian patch that disables that
+ <braunr> because there is something wrong with thread destruction
+ <braunr> but that's an implementation bug, not a design issue
+ <mcsim> so it is the mechanism how we insure that there aren't too many
+ threads
+ <mcsim> it helps because yesterday I proposed to hierarchical scheme, were
+ one server thread could wait in cpu queues of several cores
+ <mcsim> but this has to be implemented in kernel
+ <braunr> a hierarchical scheme would help yes
+ <braunr> a bit
+ <mcsim> i propose scheme that could be implemented in userspace
+ <braunr> ?
+ <mcsim> kernel should not distinguish among load balancer and server thread
+ <braunr> sorry this is too confusing
+ <braunr> please start describing what you have in mind from the start
+ <mcsim> ok
+ <mcsim> so my starting point was to use hierarchical management
+ <mcsim> but the drawback was that to implement it you have to do this in
+ kernel
+ <mcsim> right?
+ <braunr> no
+ <mcsim> so I thought how can this be implemented in user space
+ <braunr> being in kernel isn't the problem
+ <braunr> contention is
+ <braunr> on the contrary, i want ipc in kernel exactly because that's where
+ you have the most control over how it happens
+ <braunr> and can provide the best performance
+ <braunr> ipc is the main kernel responsibility
+ <mcsim> but if you have few clients you have low contention
+ <braunr> the goal was "0 potential contention"
+ <mcsim> and if you have many clients, you have many servers
+ <braunr> let's say server threads
+ <braunr> for me, a server is a server task or process
+ <mcsim> right
+ <braunr> so i think 0 potential contention is just impossible
+ <braunr> or it requires too many resources that make the solution not
+ scalable
+ <mcsim> 0 contention is impossible, since you have disbalance in numbers of
+ client threads and server threads
+ <braunr> well no
+ <braunr> it *canù be achieved
+ <braunr> imagine servers register themselves to the kernel
+ <braunr> and the kernel signals them when a client thread is spawned
+ <braunr> you'd effectively have one server thread per client
+ <braunr> (there would be other problems like e.g. when a server thread
+ becomes the client of another, etc..)
+ <braunr> so it's actually possible
+ <braunr> but we clearly don't want that, unless perhaps for real time
+ threads
+ <braunr> but please continue
+ <mcsim> what does "and the kernel signals them when a client thread is
+ spawned" mean?
+ <braunr> it means each time a thread not part of a server thread is
+ created, servers receive a signal meaning "hey, there's a new thread out
+ there, you might want to preallocate a server thread for it"
+ <mcsim> and what is the difference with creating thread on demand?
+ <braunr> on demand can occur when receiving a message
+ <braunr> i.e. during syscall
+ <mcsim> I will continue, I just want to be sure that I'm not basing on
+ wrong assumtions.
+ <mcsim> and what is bad in that?
+ <braunr> (just to clarify, i use the word "syscall" with the same meaning
+ as "RPC" on a microkernel system, whereas it's a true syscall on a
+ monolithic one)
+ <braunr> contention
+ <braunr> whether you have contention on a list of threads or on map entries
+ when allocating a stack doesn't matter
+ <braunr> the problem is contention
+ <mcsim> and if we create server thread always?
+ <mcsim> and do not keep them in queue?
+ <braunr> always ?
+ <mcsim> yes
+ <braunr> again
+ <braunr> you'd have to allocate a stack for it
+ <braunr> every time
+ <braunr> so two potentially heavy syscalls to allocate/free the stac
+ <braunr> k
+ <braunr> not to mention the thread itself, its associations with its task,
+ ipc space, maintaining reference counts
+ <braunr> (moar contention)
+ <braunr> creating threads was considered cheap at the time the process was
+ the main unit of concurrency
+ <mcsim> ok, than we will have the same contention if we will create a
+ thread when "the kernel signals them when a client thread is spawned"
+ <braunr> now we have work queues / thread pools just to avoid that
+ <braunr> no
+ <braunr> because that contention happens at thread creation
+ <braunr> not during a syscall
+ <braunr> i'll redefine the problem: the problem is contention during a
+ system call / IPC
+ <mcsim> ok
+ <braunr> note that my current solution is very close to signalling every
+ server
+ <braunr> it's the lazy version
+ <braunr> match at first IPC time
+ <mcsim> so I was basing my plan on the case when we create new thread when
+ client makes syscall and there is not enough server threads
+ <braunr> the problem exists even when there is enough server threads
+ <braunr> we shouldn't consider the case where there aren't enough server
+ threads
+ <braunr> real time tasks are the only ones which want that, and can
+ preallocate resources explicitely
+ <mcsim> I think that real time tasks should be really separated
+ <mcsim> For them resource availability as much more important that good
+ resource utilisation.
+ <mcsim> So if we talk about real time tasks we should apply one police and
+ for non-real time another
+ <mcsim> So it shouldn't be critical if thread is created during syscall
+ <braunr> agreed
+ <braunr> that's what i was saying :
+ <braunr> :)
+ <braunr> 16:23 < braunr> we shouldn't consider the case where there aren't
+ enough server threads
+ <braunr> in this case, we spawn a thread, and that's ok
+ <braunr> it will live on long enough that we really don't care about the
+ cost of lazily creating it
+ <braunr> so let's concentrate only on the case where there already are
+ enough server threads
+ <mcsim> So if client makes a request to ST (is it ok to use abbreviations?)
+ there are several cases:
+ <mcsim> 1/ There is ST waiting on local queue (trivial case)
+ <mcsim> 2/ There is no ST, only load balancer (LB). LB decides to create a
+ new thread
+ <mcsim> 3/ Like in previous case, but LB decides to perform migration
+ <braunr> migration of what ?
+ <mcsim> migration of ST from other core
+ <braunr> the only case effectively solving the problem is 1
+ <braunr> others introduce contention, and worse, complex code
+ <braunr> i mean a complex solution
+ <braunr> not only code
+ <braunr> even the addition of a load balancer per port set
+ <braunr> thr data structures involved for proper migration
+ <mcsim> But 2 and 3 in long run will lead to having enough threads on all
+ cores
+ <braunr> then you end up having 1 per client per cpu
+ <mcsim> migration is needed in any case
+ <braunr> no
+ <braunr> why would it be ?
+ <mcsim> to balance load
+ <mcsim> not only for this case
+ <braunr> there already is load balancing in the scheduler
+ <braunr> we don't want to duplicate its function
+ <mcsim> what kind of load balancing?
+ <mcsim> *has scheduler
+ <braunr> thread weight / cpu
+ <mcsim> and does it perform migration?
+ <braunr> sure
+ <mcsim> so scheduler can be simplified if policy "when to migrate" will be
+ moved to user space
+ <braunr> this is becoming a completely different problem
+ <braunr> and i don't want to do that
+ <braunr> it's very complicated for no real world benefit
+ <mcsim> but all this will be done in userspace
+ <braunr> ?
+ <braunr> all what ?
+ <mcsim> migration decisions
+ <braunr> in your scheme you mean ?
+ <mcsim> yes
+ <braunr> explain how
+ <mcsim> LB will decide when thread will migrate
+ <mcsim> and LB is user space task
+ <braunr> what does it bring ?
+ <braunr> imagine that, in the mean time, the scheduler then decides the
+ client should migrate to another processor for fairness
+ <braunr> you'd have migrated a server thread once for no actual benefit
+ <braunr> or again, you need to disable migration for long durations, which
+ sucks
+ <braunr> also
+ <braunr> 17:06 < mcsim> But 2 and 3 in long run will lead to having enough
+ threads on all cores
+ <braunr> contradicts the need for a load balancer
+ <braunr> if you have enough threads every where, why do you need to balance
+ ?
+ <mcsim> and how are you going to deal with the case when client will
+ migrate all the time?
+ <braunr> i intend to implement something close to thread migration
+ <mcsim> because some of them can die because of timeout
+ <braunr> something l4 already does iirc
+ <braunr> the thread scheduler manages scheduling contexts
+ <braunr> which can be shared by different threads
+ <braunr> which means the server thread bound to its client will share the
+ scheduling context
+ <braunr> the only thing that gets migrated is the scheduling context
+ <braunr> the same way a thread can be migrated indifferently on a
+ monolithic system, whether it's in user of kernel space (with kernel
+ preemption enabled ofc)
+ <braunr> or*
+ <mcsim> but how server thread can process requests from different clients?
+ <braunr> mcsim: load becomes a problem when there are too many threads, not
+ when they're dying
+ <braunr> they can't
+ <braunr> at first message, they're *bound*
+ <braunr> => one server thread per client
+ <braunr> when the client dies, the server thread is ubound and can be
+ recycled
+ <braunr> unbound*
+ <mcsim> and you intend to put recycled threads to global queue, right?
+ <braunr> yes
+ <mcsim> and I propose to put them in local queues in hope that next client
+ will be on the same core
+ <braunr> the thing is, i don't see the benefit
+ <braunr> next client could be on another
+ <braunr> in which case it gets a lot heavier than the extremely small
+ critical section i have in mind
+ <mcsim> but most likely it could be on the same
+ <braunr> uh, no
+ <mcsim> becouse on this load on this core is decreased
+ <mcsim> *because
+ <braunr> well, ok, it would likely remain on the same cpu
+ <braunr> but what happens when it migrates ?
+ <braunr> and what about memory usage ?
+ <braunr> one queue per cpu per port set can get very large
+ <braunr> (i understand the proposition better though, i think)
+ <mcsim> we can ask also "What if random access in memory will be more usual
+ than sequential?", but we still optimise sequential one, making random
+ sometimes even worse. The real question is "How can we maximise benefit
+ of knowledge where free server thread resides?"
+ <mcsim> previous was reply to: "(17:17:08) braunr: but what happens when it
+ migrates ?"
+ <braunr> i understand
+ <braunr> you optimize for the common case
+ <braunr> where a lot more ipc occurs than migrations
+ <braunr> agreed
+ <braunr> now, what happens when the server thread isn't in the local queue
+ ?
+ <mcsim> than client request will be handled to LB
+ <braunr> why not search directly itself ?
+ <braunr> (and btw, the right word is "then")
+ <mcsim> LB can decide whom to migrate
+ <mcsim> right, sorry
+ <braunr> i thought you were improving on my scheme
+ <braunr> which implies there is a 1:1 mapping for client and server threads
+ <mcsim> If job of LB is too small than it can be removed and everything
+ will be done in kernel
+ <braunr> it can't be done in userspace anyway
+ <braunr> these queues are in the port / port set structures
+ <braunr> it could be done though
+ <braunr> i mean
+ <braunr> using per cpu queues
+ <braunr> server threads could be both in per cpu queues and in a global
+ queue as long as they exist
+ <mcsim> there should be no global queue, because there again will be
+ contention for it
+ <braunr> mcsim: accessing a load balancer implies contention
+ <braunr> there is contention anyway
+ <braunr> what you're trying to do is reduce it in the first message case if
+ i'm right
+ <mcsim> braunr: yes
+ <braunr> well then we have to revise a few assumptions
+ <braunr> 17:26 < braunr> you optimize for the common case
+ <braunr> 17:26 < braunr> where a lot more ipc occurs than migrations
+ <braunr> that actually becomes wrong
+ <braunr> the first message case occurs for newly created threads
+ <mcsim> for make -j64 this is actually common case
+ <braunr> and those are usually not spawn on the processor their parent runs
+ on
+ <braunr> yes
+ <braunr> if you need all processors, yes
+ <braunr> i don't think taking into account this property changes many
+ things
+ <braunr> per cpu queues still remain the best way to avoid contention
+ <braunr> my problem with this solution is that you may end up with one
+ unbound thread per processor per server
+ <braunr> also, i say "per server", but it's actually per port set
+ <braunr> and even per port depending on how a server is written
+ <braunr> (the system will use one port set for one server in the common
+ case but still)
+ <braunr> so i'll start with a global queue for unbound threads
+ <braunr> and the day we decide it should be optimized with local (or
+ hierarchical) queues, we can still do it without changing the interface
+ <braunr> or by simply adding an option at port / port set creation
+ <braunr> whicih is a non intrusive change
+ <mcsim> ok. your solution should be simplier. And TBH, what I propose is
+ not clearly much mory gainful.
+ <braunr> well it is actually for big systems
+ <braunr> it is because instead of grabbing a lock, you disable preemption
+ <braunr> which means writing to a local, uncontended variable
+ <braunr> with 0 risk of cache line bouncing
+ <braunr> this actually looks very good to me now
+ <braunr> using an option to control this behaviour
+ <braunr> and yes, in the end, it gets very similar to the slab allocator,
+ where you can disable the cpu pool layer with a flag :)
+ <braunr> (except the serialized case would be the default one here)
+ <braunr> mcsim: thanks for insisting
+ <braunr> or being persistent
+ <mcsim> braunr: thanks for conversation :)
+ <mcsim> and probably I had to start from statement that I wanted to improve
+ common case
+
+
+## IRC, freenode, #hurd, 2013-06-20
+
+ <congzhang> braunr: how about your x15, it is impovement for mach or
+ redesign? I really want to know that:)
+ <braunr> it's both largely based on mach and now quite far from it
+ <braunr> based on mach from a functional point of view
+ <braunr> i.e. the kernel assumes practically the same functions, with a
+ close interface
+ <congzhang> Good point:)
+ <braunr> except for ipc which is entirely rewritten
+ <braunr> why ? :)
+ <congzhang> for from a functional point of view:) I think each design has
+ it intrinsic advantage and disadvantage
+ <braunr> but why is it good ?
+ <congzhang> if redesign , I may need wait more time to a new function hurd
+ <braunr> you'll have to wait a long time anyway :p
+ <congzhang> Improvement was better sometimes, although redesign was more
+ attraction sometimes :)
+ <congzhang> I will wait :)
+ <braunr> i wouldn't put that as a reason for it being good
+ <braunr> this is a departure from what current microkernel projects are
+ doing
+ <braunr> i.e. x15 is a hybrid
+ <congzhang> Sure, it is good from design too:)
+ <braunr> yes but i don't see why you say that
+ <congzhang> Sorry, i did not show my view clear, it is good from design
+ too:)
+ <braunr> you're just saying it's good, you're not saying why you think it's
+ good
+ <congzhang> I would like to talk hybrid, I want to talk that, but I am a
+ litter afraid that you are all enthusiasm microkernel fans
+ <braunr> well no i'm not
+ <braunr> on the contrary, i'm personally opposed to the so called
+ "microkernel dogma"
+ <braunr> but i can give you reasons why, i'd like you to explain why *you*
+ think a hybrid design is better
+ <congzhang> so, when I talk apple or nextstep, I got one soap :)
+ <braunr> that's different
+ <braunr> these are still monolithic kernels
+ <braunr> well, monolithic systems running on a microkernel
+ <congzhang> yes, I view this as one type of hybrid
+ <braunr> no it's not
+ <congzhang> microkernel wan't to divide process ( task ) from design view,
+ It is great
+ <congzhang> as implement view or execute view, we have one cpu and some
+ physic memory, as the simplest condition, we can't change that
+ <congzhang> that what resource the system has
+ <braunr> what's your point ?
+ <congzhang> I view this as follow
+ <congzhang> I am cpu and computer
+ <congzhang> application are the things I need to do
+ <congzhang> for running the program and finish the job, which way is the
+ best way for me
+ <congzhang> I need keep all the thing as simple as possible, divide just
+ from application design view, for me no different
+ <congzhang> desgin was microkernel , run just for one cpu and these
+ resource.
+ <braunr> (well there can be many processors actually)
+ <congzhang> I know, I mean hybrid at some level, we can't escape that
+ <congzhang> braunr: I show my point?
+ <braunr> well l4 systems showed we somehow can
+ <braunr> no you didn't
+ <congzhang> x15's api was rpc, right?
+ <braunr> yes
+ <braunr> well a few system calls, and mostly rpcs on top of the ipc one
+ <braunr> jsu tas with mach
+ <congzhang> and you hope the target logic run locally just like in process
+ function call, right?
+ <braunr> no
+ <braunr> it can't run locally
+ <congzhang> you need thread context switch
+ <braunr> and address space context switch
+ <congzhang> but you cut down the cost
+ <braunr> how so ?
+ <congzhang> I mean you do it, right?
+ <congzhang> x15
+ <braunr> yes but no in this way
+ <braunr> in every other way :p
+ <congzhang> I know, you remeber performance anywhere :p
+ <braunr> i still don't see your point
+ <braunr> i'd like you to tell, in one sentence, why you think hybrids are
+ better
+ <congzhang> balance the design and implement problem :p
+ <braunr> which is ?
+ <congzhang> hybird for kernel arc
+ <braunr> you're stating the solution inside the problem
+ <congzhang> you are good at mathmatics
+ <congzhang> sorry, I am not native english speaker
+ <congzhang> braunr: I will find some more suitable sentence to show my
+ point some day, but I can't find one if you think I did not show my
+ point:)
+ <congzhang> for today
+ <braunr> too bad
+ <congzhang> If i am computer I hope the arch was monolithic, If i am
+ programer I hope the arch was microkernel, that's my idea
+ <braunr> ok let's get a bit faster
+ <braunr> monolithic for performance ?
+ <congzhang> braunr: sorry for that, and thank you for the talk:)
+ <braunr> (a computer doesn't "hope")
+ <congzhang> braunr: you need very clear answer, I can't give you that,
+ sorry again
+ <braunr> why do you say "If i am computer I hope the arch was monolithic" ?
+ <congzhang> I know you can slove any single problem
+ <braunr> no i don't, and it's not about me
+ <braunr> i'm just curious
+ <congzhang> I do the work for myself, as my own view, all the resource
+ belong to me, I does not think too much arch related divide was need, if
+ I am the computer :P
+ <braunr> separating address spaces helps avoiding serious errors like
+ corrupting memory of unrelated subsystems
+ <braunr> how does one not want that ?
+ <braunr> (except for performance)
+ <congzhang> braunr: I am computer when I say that words!
+ <braunr> a computer doesn't want anything
+ <braunr> users (including developers) on the other way are the point of
+ view you should have
+ <congzhang> I am engineer other time
+ <congzhang> we create computer, but they are lifeable just my feeling, hope
+ not talk this topic
+ <braunr> what ?
+ <congzhang> I mark computer as life things
+ <braunr> please don't
+ <braunr> and even, i'll make a simple example in favor of isolating
+ resources
+ <braunr> if we, humans, were able to control all of our "resources", we
+ could for example shut down our heart by mistake
+ <congzhang> back to the topic, I think monolithic was easy to understand,
+ and cut the combinatorial problem count for the perfect software
+ <braunr> the reason the body have so many involuntary functions is probably
+ because those who survived did so because these functions were
+ involuntary and controlled by separated physiological functions
+ <braunr> now that i've made this absurd point, let's just not consider
+ computers as life forms
+ <braunr> microkernels don't make a system that more complicated
+ <congzhang> they does
+ <braunr> no
+ <congzhang> do
+ <braunr> they create isolation
+ <braunr> and another layer of indirection with capabilities
+ <braunr> that's it
+ <braunr> it's not that more complicated
+ <congzhang> view the kernel function from more nature view, execute some
+ code
+ <braunr> what ?
+ <congzhang> I know the benefit of the microkernel and the os
+ <congzhang> it's complicated
+ <braunr> not that much
+ <congzhang> I agree with you
+ <congzhang> microkernel was the idea of organization
+ <braunr> yes
+ <braunr> but always keep in mind your goal when thinking about means to
+ achieve them
+ <congzhang> we do the work at diferent view
+ <kilobug> what's quite complicated is making a microkernel design without
+ too much performances loss, but aside from that performances issue, it's
+ not really much more complicated
+ <congzhang> hurd do the work at os level
+ <kilobug> even a monolithic kernel is made of several subsystems that
+ communicated with each others using an API
+ <core-ix> i'm reading this conversation for some time now
+ <core-ix> and I have to agree with braunr
+ <core-ix> microkernels simplify the design
+ <braunr> yes and no
+ <braunr> i think it depends a lot on the availability of capabilities
+ <core-ix> i have experience mostly with QNX and i can say it is far more
+ easier to write a driver for QNX, compared to Linux/BSD for example ...
+ <braunr> which are the major feature microkernels usually add
+ <braunr> qnx >= 5 do provide capabilities
+ <braunr> (in the form of channels)
+ <core-ix> yeah ... it's the basic communication mechanism
+ <braunr> but my initial and still unanswered question was: why do people
+ think a hybrid kernel is batter than a true microkernel, or not
+ <braunr> better*
+ <congzhang> I does not say what is good or not, I just say hybird was
+ accept
+ <braunr> core-ix: and if i'm right, they're directly implemented by the
+ kernel, and not a userspace system server
+ <core-ix> braunr: evolution is more easily accepted than revolution :)
+ <core-ix> braunr: yes, message passing is in the QNX kernel
+ <braunr> not message passing, capabilities
+ <braunr> l4 does message passing in kernel too, but you need to go through
+ a capability server
+ <braunr> (for the l4 variants i have in mind at least)
+ <congzhang> the operating system evolve for it's application.
+ <braunr> congzhang: about evolution, that's one explanation, but other than
+ that ?
+ <braunr> core-ix: ^
+ <core-ix> braunr: by capability you mean (for the lack of a better word
+ i'll use) access control mechanisms?
+ <braunr> i mean reference-rights
+ <core-ix> the "trusted" functionality available in other OS?
+ <braunr> http://en.wikipedia.org/wiki/Capability-based_security
+ <braunr> i don't know what other systems refer to with "trusted"
+ functionnality
+ <core-ix> yeah, the same thing
+ <congzhang> for now, I am searching one way to make hurd arm edition
+ suitable for Raspberry Pi
+ <congzhang> I hope design or the arch itself cant scale
+ <congzhang> can be scale
+ <core-ix> braunr: i think (!!!) that those are implemented in the Secure
+ Kernel (http://www.qnx.com/products/neutrino-rtos/secure-kernel.html)
+ <core-ix> never used it though ...
+ <congzhang> rpc make intercept easy :)
+ <braunr> core-ix: regular channels are capabilities
+ <core-ix> yes, and by extensions - they are in the kenrel
+ <braunr> that's my understanding too
+ <braunr> and that one thing that, for me, makes qnx an hybrid as well
+ <congzhang> just need intercept in kernel,
+ <core-ix> braunr: i would dive the academic aspects of this ... in my mind
+ a microkernel is system that provides minimal hardware abstraction,
+ communication primitives (usually message passing), virtual memory
+ protection
+ <core-ix> *wouldn't ...
+ <braunr> i think it's very important on the contrary
+ <braunr> what you describe is the "microkernel dogma"
+ <braunr> precisely
+ <braunr> that doesn't include capabilities
+ <braunr> that's why l4 messaging is thread-based
+ <braunr> and that's why l4 based systems are so slow
+ <braunr> (except okl4 which put back capabilities in the kernel)
+ <core-ix> so the compromise here is to include capabilities implementation
+ in the kernel, thus making the final product hybrid?
+ <braunr> not only
+ <braunr> because now that you have them in kernel
+ <braunr> the kernel probably has to manage memory for itself
+ <braunr> so you need more features in the virtual memory system
+ <core-ix> true ...
+ <braunr> that's what makes it a hybrid
+ <braunr> other ways being making each client provide memory, but that's
+ when your system becomes very complicated
+ <core-ix> but I believe this is true for pretty much any "general OS" case
+ <braunr> and some resources just can't be provided by a client
+ <braunr> e.g. a client can't provide virtual memory to another process
+ <braunr> okl4 is actually the only pragmatic real-world implementation of
+ l4
+ <braunr> and they also added unix-like signals
+ <braunr> so that's an interesting model
+ <braunr> as well as qnx
+ <braunr> the good thing about the hurd is that, although it's not kernel
+ agnostic, it doesn't require a lot from the underlying kernel
+ <core-ix> about hurd?
+ <braunr> yes
+ <core-ix> i really need to dig into this code at some point :)
+ <braunr> well you may but you may not see that property from the code
+ itself
diff --git a/microkernel/mach/gnumach/memory_management.mdwn b/microkernel/mach/gnumach/memory_management.mdwn
index 4e237269..477f0a18 100644
--- a/microkernel/mach/gnumach/memory_management.mdwn
+++ b/microkernel/mach/gnumach/memory_management.mdwn
@@ -188,3 +188,18 @@ License|/fdl]]."]]"""]]
patch
<braunr> (more kernel memory, thus more physical memory - up to 1.8 GiB -
but then, less user memory)
+
+
+# IRC, freenode, #hurd, 2013-06-06
+
+ <nlightnfotis> braunr: quick question, what memory allocation algorithms
+ does the Mach use? I know it uses slab allocation, so I can guess buddy
+ allocators too?
+ <braunr> no
+ <braunr> slab allocator for kernel memory (allocation of buffers used by
+ the kernel itself)
+ <braunr> a simple freelist for physical pages
+ <braunr> and a custom allocator based on a red-black tree, a linked list
+ and a hint for virtual memory
+ <braunr> (which is practically the same in all BSD variants)
+ <braunr> and linux does something very close too
--
cgit v1.2.3