Does the FreeBSD kernel employ a page coloring algorithm? If so,
where can I find information on the heuristics used to color pages?
I have looked at Matthew Dillon's description at http://
people.freebsd.org/~nik/article.html-text
I was hoping to find something more detailed.
T
David Schultz wrote:
>
> On Wed, Jun 25, 2003, David Gilbert wrote:
> > > "Matthew" == Matthew Dillon <[EMAIL PROTECTED]> writes:
> >
> > Matthew> The primes are designed such that the page allocation
> > Matthew> code covers *ALL* the free lists in the array, so it will
> > Matthew> still
On Wed, Jun 25, 2003, David Gilbert wrote:
> > "Matthew" == Matthew Dillon <[EMAIL PROTECTED]> writes:
>
> Matthew> The primes are designed such that the page allocation
> Matthew> code covers *ALL* the free lists in the array, so it will
> Matthew> still be able to find any available free
> "Matthew" == Matthew Dillon <[EMAIL PROTECTED]> writes:
Matthew> The primes are designed such that the page allocation
Matthew> code covers *ALL* the free lists in the array, so it will
Matthew> still be able to find any available free pages if its first
Matthew> choice(s) are empty.
Ma
ith these defines
> will generally know what they're doing anyway, it would be nice to make these
> optimizations a wee bit more accessible; also, as we grow to support more
> Tier 1 architectures, having page coloring work 'out-of-the-box' across them
> might be seen as
Bruce M Simpson wrote:
> Something occurred to me whilst I was re-reading the 'Design Elements'
> article over the weekend; our page coloring algorithm, as it stands,
> might not be optimal for non-Intel CPUs.
Actually, it does very well for most architectures, and was origin
Hi,
> :U Actually, Matt, the property you've stated is much more
> :common than you seem to believe. If you generate a sequence
> :N = ( N + Stride ) % ArraySize
> :then you will visit every element of (0 ... ArraySize-1) as long as
>
> I was just answering a question. Most peo
:
:Matthew Dillon wrote:
:> For example, prime number 3 an array size 8 will scan the array in
:> the following order N = (N + PRIME) & (ARRAY_SIZE_MASK).
:> N = (N + 3) & 7:
:>
:> 0 3 6 1 4 7 2 5 ... 0
:>
:> As you can see, all the array entries are covered before the seque
Matthew Dillon wrote:
For example, prime number 3 an array size 8 will scan the array in
the following order N = (N + PRIME) & (ARRAY_SIZE_MASK).
N = (N + 3) & 7:
0 3 6 1 4 7 2 5 ... 0
As you can see, all the array entries are covered before the sequence
repeats. Onl
On Tue, Jun 24, 2003 at 02:38:13PM +0100, Bruce M Simpson wrote:
> The names of the definitions as they stand are perhaps slightly misleading
> in this respect. PQ_L2_SIZE might be better renamed PQ_SETSIZE and defined
> in terms of PQ_CACHESIZE/PQ_NSETS.
[snip]
Bikeshed, but it would still be nic
: - The page queue structures are sized according to these
:defines at boot-time.
:
: - If someone could fill me in on how the primes are arrived at that
:would be very helpful.
:
:Comments/discussion/correction welcomed, it would be good to get some
:feedback on this before I start patc
th these defines
will generally know what they're doing anyway, it would be nice to make these
optimizations a wee bit more accessible; also, as we grow to support more
Tier 1 architectures, having page coloring work 'out-of-the-box' across them
might be seen as a desirable f
On Tue, Jun 24, 2003, Bruce M Simpson wrote:
> Hi all,
>
> Something occurred to me whilst I was re-reading the 'Design Elements'
> article over the weekend; our page coloring algorithm, as it stands,
> might not be optimal for non-Intel CPUs.
>
> Spiel:
> -
Hi all,
Something occurred to me whilst I was re-reading the 'Design Elements'
article over the weekend; our page coloring algorithm, as it stands,
might not be optimal for non-Intel CPUs.
Spiel:
- Dillon's VM article talks about L1 cache reference, rather than L2.
:If I remember correctly from reading a thesis (can't remember its
:author) on the page coloring which I believe widely introduced this
:concept, page coloring adds a lot of efficiency to the directly
:mapped caches but even for the 2-way caches is nearly pointless.
:
:-SB
For the
On Sun, Aug 05, 2001 at 10:33:08PM +0100, Nik Clayton wrote:
> On Sun, Aug 05, 2001 at 12:20:36PM -0700, Matt Dillon wrote:
> > It's a good description but it might be better to simplify it a bit.
> > You don't need to go into that level of detail. There is a sh
Matt Dillon wrote:
>
> Well, first of all the page coloring is not pointless with the
> sizes hardwired. The cache characteristics do not have to
> match exactly for page coloring to work. The effectiveness is
> like a log-graph, and you don't lose a l
> Yes, I understand that. I'm just trying to find out why Mike keeps
> saying we cannot determine the processor cache characteristics at
> runtime.
Because I believed we couldn't. It appears I'm wrong. 8)
The only question left really then is whether it's worth actually trying
to tune for cac
On Sun, Aug 05, 2001 at 12:20:36PM -0700, Matt Dillon wrote:
> It's a good description but it might be better to simplify it a bit.
> You don't need to go into that level of detail. There is a short
> page coloring explanation at the end of my VM article which
In article <[EMAIL PROTECTED]>,
Matt Dillon <[EMAIL PROTECTED]> wrote:
> :Yes, I understand that. I'm just trying to find out why Mike keeps
> :saying we cannot determine the processor cache characteristics at
> :runtime.
> :
> :John
>
> You can find out from the cpuid or something like tha
:> Since most L1 caches these days are at least 16K and most L2 caches
:> these days are at least 64K (and often much higher, such as on the IA32),
:> our hardwired page coloring constants wind up being about 95% effective
:> across the entire range of chips our OS cu
escription but it might be better to simplify it a bit.
You don't need to go into that level of detail. There is a short
page coloring explanation at the end of my VM article which might
be more suitable to a man page:
http://www.daemonnews.org/21/
. As far as I can tell, it works
> :for the Pentium Pro and subsequent processors.
> :
> :John
> :--
> : John Polstra [EMAIL PROTECTED]
>
> Well, first of all the page coloring is not pointless with the
> size
[EMAIL PROTECTED]
Well, first of all the page coloring is not pointless with the
sizes hardwired. The cache characteristics do not have to
match exactly for page coloring to work. The effectiveness is
like a log-graph, and you don't lose a lot by guessing
In article <[EMAIL PROTECTED]>,
Mike Smith <[EMAIL PROTECTED]> wrote:
>
> It looks about right, but page colouring is pointless unless and until we
> can determine the processor cache characteristics at runtime.
>
> Which we can't.
Why can't we do this at least on the i386 with the CPUID inst
> If I added this to a man page would I be telling the truth :).
>
> Note, these are my notes and not the exact text that I would
> add, and I have not bother with anything to do with object
> coloring etc. I just want to make sure I've got this part
> down.
It looks about right, but page colou
If I added this to a man page would I be telling the truth :).
Note, these are my notes and not the exact text that I would
add, and I have not bother with anything to do with object
coloring etc. I just want to make sure I've got this part
down.
Chad
page col
:
:
:
: yes, I mean vm_page_t, and understand what you said. I will try to print the
:value of PQ_L2_SIZE in my kernel. Do you know what kernel options influence
:this value? I saw it is decided by PQ_CACHESIZE which is decided by different
:PQ_HUGE[LARGE/MEDIUM/...]CACHEsetting. Defaul
> :
> :However, I found that almost each map entry's page color is zero, that means
> :PQ_L2_SIZE is 1, and disable page coloring option. Maybe I can do some
> :modification to dump PQ_L2_SIZE's value, but I think my guess is right.
> :Can someone please tell me the princ
E_SHIFT)&PQ_L2_MASK;
:
:However, I found that almost each map entry's page color is zero, that means
:PQ_L2_SIZE is 1, and disable page coloring option. Maybe I can do some
:modification to dump PQ_L2_SIZE's value, but I think my guess is right.
:Can someone please tell me the principle of pag
PQ_L2_MASK;
However, I found that almost each map entry's page color is zero, that means
PQ_L2_SIZE is 1, and disable page coloring option. Maybe I can do some
modification to dump PQ_L2_SIZE's value, but I think my guess is right.
Can someone please tell me the principle of page coloring, a
> > It skips queue pq[index & PQ_L2_MASK].
> >
>
> That's correct. The inline function vm_page_list_find() in vm_page.h
> has already failed to allocate a page of the desired color, index,
> and so _vm_page_list_find() is called to allocate a page of ANY other
> color it can find.
Oh, yes. I d
On Thu, Nov 23, 2000 at 12:48:09PM -0800, Mike Smith wrote:
> > > Isn't the page coloring algoritm in _vm_page_list_find totally bogus?
> > >
> >
> > No, it's not. The comment is, however, misplaced. It describes
> > the behavior of an inline func
> Hi.
>
> Isn't the page coloring algoritm in _vm_page_list_find totally bogus?
Yes, it's totally bogus, and it should probably be ripped out.
--
... every activity meets with opposition, everyone who acts has his
rivals and unfortunately opponents also. But not becaus
Hi.
Isn't the page coloring algoritm in _vm_page_list_find totally bogus?
It skips queue pq[index & PQ_L2_MASK].
If it doesn't find page with desired color, it allocates page with nearest
color - as a result there are two pages with same color mapped at two
adjacent virtual adre
35 matches
Mail list logo
