Haiku

On 2009-08-22 at 01:54:20 [+0200], Rene Gollent <anevilyak@...> wrote:
> 
> Michael and I were having a discussion about the current behavior with
> respect to preemption on release_sem_etc and/or signal delivery, and
> an uncertain question crops up: In quite a few cases, if a thread is
> woken up by either one, that wakeup is being used as a communications
> mechanism between two threads (i.e. to wake up another thread and tell
> it data is ready to be worked on). However, the scheduler currently
> only preempts if the new thread's priority is greater than that of the
> instigator. In cases like this though, it's entirely possible the two
> threads will be of equal priority, and as such that strategy might
> result in undesired latency on waking up the recipient since the
> sender will be allowed the rest of its timeslice.

Please keep in mind that lower latencies are bought with additional 
scheduling overhead and lower throughput. When both threads have the same 
priority, there's simply no rectification for doing that. Unless you base the 
decision on additional criteria like overall/current run/waittime of the 
involved threads (i.e. fairness criteria) or to-be-introduced special 
attributes/properties of locking primitives (e.g. an "interactivity buff").

> However, at the same
> time, if we did signal preemption on equal priority, there's still no
> guarantee that the target thread will in fact be the one woken up due
> to a) the 20% random factor we use for priority skipping, and b) the
> fact that we enqueue new threads at the end of the list of waiting
> threads at the same priority, and as such if another is waiting it
> will go first (if it goes at all). Is this a situation we want to deal
> with, and if so, any thoughts on how?

The "20% skip" and "enqueue at the end" are really fairness issues. So, if 
you're generally concerned about fairness, those should be addressed. I'd 
rather work on making the affine scheduler more affine first, though.

CU, Ingo

Em 22/08/2009, às 12:08, Ingo Weinhold <ingo_weinhold@...> escreveu:
> Please keep in mind that lower latencies are bought with additional
> scheduling overhead and lower throughput. When both threads have the  
> same
> priority, there's simply no rectification for doing that. Unless you  
> base the
> decision on additional criteria like overall/current run/waittime of  
> the
> involved threads (i.e. fairness criteria) or to-be-introduced special
> attributes/properties of locking primitives (e.g. an "interactivity  
> buff").

FINALLY! I've been waiting 2 years now for someone to actually  
consider this :D
*Thank you*!

> The "20% skip" and "enqueue at the end" are really fairness issues.  
> So, if
> you're generally concerned about fairness, those should be  
> addressed. I'd
> rather work on making the affine scheduler more affine first, though.

Well, since this overlaps a lot with many other scheduling /policies/,  
and I'm also addressing those, I think energy is better spent  
implementing something that is usable at the /mechanism/ level, namely  
the topology graph that was discussed a few months ago. That I could  
benefit from a lot for the load balancer, but I don't currently have  
the necessary knowledge of x86 and its MSRs to implement myself...


Cheers,
A.

On 2009-08-22 at 19:54:17 [+0200], André Braga <meianoite@...> wrote:
> Em 22/08/2009, às 12:08, Ingo Weinhold <ingo_weinhold@...> escreveu:
> > Please keep in mind that lower latencies are bought with additional
> > scheduling overhead and lower throughput. When both threads have the
> > same
> > priority, there's simply no rectification for doing that. Unless you
> > base the
> > decision on additional criteria like overall/current run/waittime of
> > the
> > involved threads (i.e. fairness criteria) or to-be-introduced special
> > attributes/properties of locking primitives (e.g. an "interactivity
> > buff").
> 
> FINALLY! I've been waiting 2 years now for someone to actually
> consider this :D
> *Thank you*!

Sorry I got you all excited and have shoot you down again. My intention was 
really only to list examples. I'm no fonder of the idea of tagging locking 
primitives than I was when you brought it up. You are still free to implement 
that concept and demonstrate its measurable benefits, though.

CU, Ingo

Em 22/08/2009, às 16:17, Ingo Weinhold <ingo_weinhold@...> escreveu:
> Sorry I got you all excited and have shoot you down again. My  
> intention was
> really only to list examples. I'm no fonder of the idea of tagging  
> locking
> primitives than I was when you brought it up. You are still free to  
> implement
> that concept and demonstrate its measurable benefits, though.

Oh, bummer. Still it's nice to have that idea remembered even if just  
for exemplification purposes.

Anyway, that's indeed the plan. I'm working full time and taking a  
computer graphics course in the night as well, so my free time was  
radically reduced, but I hope to bring better news soon.

2009/4/2 Aldrin Montana <drinmontana@...>:
> Hello Haiku Developers,

Hi Aldrin,

>
> My name is Aldrin and I am a second year student at Cal Poly, San Luis
> Obispo. Today in one of my classes my professor made the announcement that
> Haiku OS was part of Google Summer of Code and looking for volunteers. I'm
> not sure if this project is still looking for more developers but I would
> like to try and contribute what I can.
>

Nice to hear that Haiku is getting famous.
Haiku is always looking for new developers, not only for GSoC.

>
> My main interest with this project lies in kernel programming, or something
> along those lines. Last quarter I took an intro operating systems class and
> enjoyed it. I am taking the second part of that course this quarter, and
> think that this project would fit me perfectly. However, I am fairly busy
> with classes, working on satellite projects at school, work, and other
> extracurriculars. But I believe that since most of the development for this
> project will take place during the summer, I will have enough free time
> (maybe 10 - 15 hours per week minimum) to contribute a moderate amount of
> source code or debug any existing code.
>

First of all thanks for taking interest in Haiku. You have time until
tomorrow night
to submit a draft of your proposal in order to apply for gsoc,
although 15 hours per
week seems very low. We usually expect students to work up to 40 hours per week
for GSoC.

Regards,
Salvatore

Em 21/03/2009, às 12:49, Rene Gollent <anevilyak@...> escreveu:
> Hi,
> Are there any plans to implement a mechanism by which a scheduler
> could discover the topology of the detected CPUs/cores/hardware
> threads? If not, any preference on what such an API should look like?

There are such plans, indeed, as I mentioned, but I wouldn't mind if  
someone else implemented the topology API. My usage for such API would  
be to build a graph of migration penalties, such that cores connected  
by slower means would receive a higher penalty (SMT* < shared cache <  
SMT** < shared socket < shared... backplane? [and Haiku goes NUMA!])

(*,**: SMT is tricky, as discussed on a previous thread. Affinity  
flags could be used to hint the scheduler about the proper situation  
to run a thread on a logical core, in order not to trash caches and so  
on.)

Such a graph would be represented by a compact triangular matrix,  
since the penalties would be symmetrical between a pair of cores and  
its reciprocal, i.e., (Ca, Cb) and (Cb, Ca).

So, an API that returns a tree of cores as leaves and interconnections  
as nodes, or one that receives a pair of cores and returns a list of  
interconnects representing how they are reachable from one to the  
other, would be fine by me.


Cheers,
A.

2009/3/21 André Braga <meianoite@...>:
> There are such plans, indeed, as I mentioned, but I wouldn't mind if
> someone else implemented the topology API. My usage for such API would
> be to build a graph of migration penalties, such that cores connected
> by slower means would receive a higher penalty (SMT* < shared cache <
> SMT** < shared socket < shared... backplane? [and Haiku goes NUMA!])

You could probably build the graph yourself if given the appropriate
information. For example, if we extend the cpu_ent structure to
indicate the physical id, logical id, smt id for lack of better names
(i.e. two cores on the same physical die would share the same physical
ID, and  hyperthread/SMT would share the same phy + logical). This
would let you walk through gCPU and build an appropriate graph, though
this wouldn't really cover more advanced NUMA situations for the time
being. IMO that's not likely to be an issue any time soon though, so
we can tackle that bridge when we get to it. This solution wouldn't
really require a great deal of time, and no new API calls would be
necessary. Thoughts, anyone?

Regards,

Rene

On 2009-03-22 at 17:03:58 [+0100], Rene Gollent <anevilyak@...> wrote:
> 2009/3/21 André Braga <meianoite@...>:
> > There are such plans, indeed, as I mentioned, but I wouldn't mind if
> > someone else implemented the topology API. My usage for such API would
> > be to build a graph of migration penalties, such that cores connected
> > by slower means would receive a higher penalty (SMT* < shared cache <
> > SMT** < shared socket < shared... backplane? [and Haiku goes NUMA!])
> 
> You could probably build the graph yourself if given the appropriate
> information. For example, if we extend the cpu_ent structure to
> indicate the physical id, logical id, smt id for lack of better names
> (i.e. two cores on the same physical die would share the same physical
> ID, and  hyperthread/SMT would share the same phy + logical). This
> would let you walk through gCPU and build an appropriate graph, though
> this wouldn't really cover more advanced NUMA situations for the time
> being. IMO that's not likely to be an issue any time soon though, so
> we can tackle that bridge when we get to it. This solution wouldn't
> really require a great deal of time, and no new API calls would be
> necessary. Thoughts, anyone?

I'd prefer <cpu.h> to already offer a tree representation. I would introduce 
a cpu_scope structure (or class) representing a tree node. The leaf nodes 
would refer to the cpu_ents (respectively with C++ the cpu_ents (CPU) would 
derive from cpu_scope (CPUScope)). Each node would describe the properties of 
the corresponding hardware, e.g. what kind of hardware it refers to (CPU, 
core, hardware thread,...) and what resources are shared by its children 
(units, caches, busses, whatever).

CU, Ingo

On Sun, Mar 22, 2009 at 12:06 PM, Ingo Weinhold <ingo_weinhold@...> wrote:
> I'd prefer <cpu.h> to already offer a tree representation. I would introduce
> a cpu_scope structure (or class) representing a tree node. The leaf nodes
> would refer to the cpu_ents (respectively with C++ the cpu_ents (CPU) would
> derive from cpu_scope (CPUScope)). Each node would describe the properties of
> the corresponding hardware, e.g. what kind of hardware it refers to (CPU,
> core, hardware thread,...) and what resources are shared by its children
> (units, caches, busses, whatever).

That works for me, just need to wrap my head around where / how all
the CPU detection information is split up in the kernel since I see
some of it happens in the boot loader and some in the actual kernel.
Not sure yet if anything extra will be necessary to pick up the
topology data, though I was under the impression at least some of that
required ACPI.

Regards,

Rene

Rene Gollent - 2009-03-23 14:46 :
> That works for me, just need to wrap my head around where / how all
> the CPU detection information is split up in the kernel since I see
> some of it happens in the boot loader and some in the actual kernel.
> Not sure yet if anything extra will be necessary to pick up the
> topology data, though I was under the impression at least some of that
> required ACPI.

ACPI may be required for multi-socket systems, but information about 
cores/threads for a single CPU should be available via CPUID calls at 
least on Intel and AMD. Haiku currently doesn't use this, otherwise we'd 
have a CPUID wrapper which allows for passing parameters to CPUID in ECX, 
which is required for Intel. This will need to be added for proper 
multi-core detection.

The CPUID function on Intel is 0xb, "x2APIC Features/Processor Topology". 
It may be necessary to enable x2APIC before this function will return 
sensible information, but I'm not sure. For details see
"Intel® Processor Identification and the CPUID Instruction
Application Note 485" available on Intels website - googling might be 
faster than searching for it there, though. :)

The method for AMD CPUs is detailed in the "AMD CPUID Specification", 
publication # 25481 (my revision is from April 2008, maybe AMD has a newer 
version).

HTH.

Christian

On Mon, Mar 23, 2009 at 10:52 AM, Christian Packmann
<Christian.Packmann@...> wrote:
> The CPUID function on Intel is 0xb, "x2APIC Features/Processor Topology".
> It may be necessary to enable x2APIC before this function will return
> sensible information, but I'm not sure. For details see
> "Intel® Processor Identification and the CPUID Instruction
> Application Note 485" available on Intels website - googling might be
> faster than searching for it there, though. :)

We do actually use cpuid to get information about the chips in
kernel/arch/x86/cpu.cpp and/or cpuid.S. Does this need to be extended
or is it already reporting all the necessary info?

Regards,

Rene

On 2009-03-23 at 17:01:14 [+0100], Rene Gollent <anevilyak@...> wrote:
> On Mon, Mar 23, 2009 at 10:52 AM, Christian Packmann
> <Christian.Packmann@...> wrote:
> > The CPUID function on Intel is 0xb, "x2APIC Features/Processor Topology".
> > It may be necessary to enable x2APIC before this function will return
> > sensible information, but I'm not sure. For details see
> > "Intel® Processor Identification and the CPUID Instruction
> > Application Note 485" available on Intels website - googling might be
> > faster than searching for it there, though. :)
> 
> We do actually use cpuid to get information about the chips in
> kernel/arch/x86/cpu.cpp and/or cpuid.S. Does this need to be extended
> or is it already reporting all the necessary info?

No idea. I guess Axel and Michael would know, but maybe they are a little 
short on time ATM. At any rate reading the documentation and the respective 
source code will definitely help, too. :-)

CU, Ingo

On Mon, Mar 23, 2009 at 8:01 PM, Ingo Weinhold <ingo_weinhold@...> wrote:
> No idea. I guess Axel and Michael would know, but maybe they are a little
> short on time ATM. At any rate reading the documentation and the respective
> source code will definitely help, too. :-)

Will see what I can do :) On a related note, would anyone be opposed
to be me extending the kernel struct thread a bit? I'd like to be able
to track how much of its quantum a thread used for its past few runs,
since otherwise we don't have any good way (that I can see) to know
how much of a CPU hog a particular thread was, and for obvious reasons
I'd like to avoid having to do any dynamic memory allocation in the
scheduler itself, which leaves me somewhat short on options for places
to track per-thread data.

Regards,

Rene

On 2009-03-24 at 02:54:51 [+0100], Rene Gollent <anevilyak@...> wrote:
> On Mon, Mar 23, 2009 at 8:01 PM, Ingo Weinhold <ingo_weinhold@...> wrote:
> > No idea. I guess Axel and Michael would know, but maybe they are a little
> > short on time ATM. At any rate reading the documentation and the 
> > respective
> > source code will definitely help, too. :-)
> 
> Will see what I can do :) On a related note, would anyone be opposed
> to be me extending the kernel struct thread a bit? I'd like to be able
> to track how much of its quantum a thread used for its past few runs,
> since otherwise we don't have any good way (that I can see) to know
> how much of a CPU hog a particular thread was, and for obvious reasons
> I'd like to avoid having to do any dynamic memory allocation in the
> scheduler itself, which leaves me somewhat short on options for places
> to track per-thread data.

I'd say best introduce a scheduler_thread_data* field -- with the 
scheduler_thread_data structure being scheduler implementation private -- 
that is initialized/uninitialized via scheduler hooks on thread 
creation/deletion. This way each scheduler implementation can associate the 
data it needs with the thread. If you want to associate data with teams as 
well, it can be done analogously.

CU, Ingo

Rene Gollent - 2009-03-23 17:01 :
> On Mon, Mar 23, 2009 at 10:52 AM, Christian Packmann
> <Christian.Packmann@...> wrote:
>> The CPUID function on Intel is 0xb, "x2APIC Features/Processor Topology".
>> It may be necessary to enable x2APIC before this function will return
>> sensible information, but I'm not sure. For details see
>> "Intel® Processor Identification and the CPUID Instruction
>> Application Note 485" available on Intels website - googling might be
>> faster than searching for it there, though. :)
> 
> We do actually use cpuid to get information about the chips in
> kernel/arch/x86/cpu.cpp and/or cpuid.S. Does this need to be extended
> or is it already reporting all the necessary info?

The current implementation in Haiku only allows CPUID input in register 
EAX; some recent CPUID functions on Intel also require an input in ECX to 
indicate the requested level of the topology. So there needs to be a new 
CPUID wrapper which also allows for inputs to ECX. I already mentioned 
this on Haiku-Devel, and Axel had the idea to simply pass the CPUID input 
values in the cpuid_info struct. I think this is the most elegant 
solution, as it will work with other future extensions to CPUID.

Christian

André Braga - 2009-03-21 17:23 :
> There are such plans, indeed, as I mentioned, but I wouldn't mind if  
> someone else implemented the topology API. My usage for such API would  
> be to build a graph of migration penalties, such that cores connected  
> by slower means would receive a higher penalty (SMT* < shared cache <  
> SMT** < shared socket < shared... backplane? [and Haiku goes NUMA!])

Just a quick note on NUMA support: any NUMA scheduling should also keep 
track of the locality of memory allocations for any thread/team. If you 
run a thread on a CPU remote from its memory allocations, this will incur 
high bus traffic. Not a problem for a single/few thread(s) or small 
amounts of memory traffic, but if you ignore this problem you might have 
many threads generating bus traffic, which might slow down the system 
significantly.

Christian

Building a GCC cross-compiler is actually pretty straigthforward.  Just
google 'gcc cross-compiler'.  There's already a MIPS code generator for GCC
so it shouldn't be too bad.

Jim Burnes


On Mon, Jan 12, 2009 at 10:37 PM, Jonas Sundström <jonas@...> wrote:

> "François Revol" <revol@...> wrote:
>  ...
> > - add U-Boot support, which will also help an
> >  ARM port incidentally.
>
> Some current MIPS hardware would too. I've got a couple,
> both MIPS32 and MIPS64 (the latest MIPS ISAs) which I
> hope to make Haiku run on eventually.
>
> Is it correct to assume that making an appropriate cross-
> compiler (for this new Haiku/MIPSxx) is the right way to
> start?
>
> I'm intimidated by the apparent size and complexity of GCC.
> Any hints on how to approach this?
>
> /Jonas.
>
>
>
>
> ------------------------------------------------------------------------------
> This SF.net email is sponsored by:
> SourcForge Community
> SourceForge wants to tell your story.
> http://p.sf.net/sfu/sf-spreadtheword
> _______________________________________________
> Open-beos-kernel-devel mailing list
> Open-beos-kernel-devel@...
> https://lists.sourceforge.net/lists/listinfo/open-beos-kernel-devel
>

> "François Revol" <revol@...> wrote:
>  ...
> > - add U-Boot support, which will also help an
> >  ARM port incidentally.
> 
> Some current MIPS hardware would too. I've got a couple,
> both MIPS32 and MIPS64 (the latest MIPS ISAs) which I 
> hope to make Haiku run on eventually.
> 
> Is it correct to assume that making an appropriate cross-
> compiler (for this new Haiku/MIPSxx) is the right way to
> start?

Yes but you don't need to use linux like things like Crosstools, see 
below.

> 
> I'm intimidated by the apparent size and complexity of GCC.
> Any hints on how to approach this?

Both binutils and gcc must be told how to build for Haiku on the new 
arch (=cpu).
This means adding and modifying few files to add cases to handle in 
switch or default settings.

The best way is to look at what has been done on another arch for 
Haiku, then what is different for other OSes between those archs to see 
if there is something else specific to the arch.

Also, use gcc4 as there is no reason for gcc2 outside x86 (no need for 
compatibility), + it's too old.

As an exemple, I'd point to the m68k port:

svn diff -r22682:22683 binutils/
svn diff -r22684:22685 gcc/

I should probably document that sometime...

François.

> Building a GCC cross-compiler is actually pretty straigthforward.  
> Just
> google 'gcc cross-compiler'.  There's already a MIPS code generator 
> for GCC
> so it shouldn't be too bad.

Except it's not about creating a gcc for a bare mips target or for 
linux, but for Haiku, and gcc doesn't know about Haiku on MIPS yet, so 
you have to explain it how things should go.
cf. previous mail.

François.

Correct.  Forgot to mention that point.


On Wed, Jan 14, 2009 at 5:20 PM, François Revol <revol@...> wrote:

> > Building a GCC cross-compiler is actually pretty straigthforward.
> > Just
> > google 'gcc cross-compiler'.  There's already a MIPS code generator
> > for GCC
> > so it shouldn't be too bad.
>
> Except it's not about creating a gcc for a bare mips target or for
> linux, but for Haiku, and gcc doesn't know about Haiku on MIPS yet, so
> you have to explain it how things should go.
> cf. previous mail.
>
> François.
>
>
> ------------------------------------------------------------------------------
> This SF.net email is sponsored by:
> SourcForge Community
> SourceForge wants to tell your story.
> http://p.sf.net/sfu/sf-spreadtheword
> _______________________________________________
> Open-beos-kernel-devel mailing list
> Open-beos-kernel-devel@...
> https://lists.sourceforge.net/lists/listinfo/open-beos-kernel-devel
>