<div dir="ltr"><div>I don't know the exact hardware algorithm used for the complex indexing. The page coloring has less and less of an effect as cpu caches get better at distributing the data. The overall effectiveness of the combination can only get better, even if it is only a slight improvement.<br><br></div>-Matt<br></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jun 1, 2015 at 9:32 AM, Alex Merritt <span dir="ltr"><<a href="mailto:merritt.alex@gmail.com" target="_blank">merritt.alex@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Correction ---<span class=""><div><br></div><div><span style="font-size:12.8000001907349px">A direct-mapping function to index a cache, to me, means the use of specific well-known index bits within the physical address to determine the set into which it will be placed when cached.</span><br></div><div><span style="font-size:12.8000001907349px"><br></span></div></span><div><span style="font-size:12.8000001907349px">becomes</span></div><div><span style="font-size:12.8000001907349px"><br></span></div><div><span style="font-size:12.8000001907349px">A direct-mapping function to index a cache, to me, means the use of specific well-known index bits within the address (virtual or physical) to determine the set into which it will be placed when cached.</span><span style="font-size:12.8000001907349px"><br></span></div><div><span style="font-size:12.8000001907349px"><br></span></div><div><span style="font-size:12.8000001907349px">Apologies.</span></div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jun 1, 2015 at 9:30 AM, Alex Merritt <span dir="ltr"><<a href="mailto:merritt.alex@gmail.com" target="_blank">merritt.alex@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Matt,<div><br></div><div>Thank you for the insight into the L1 operation. As L1 uses a direct-mapped indexing function, we can apply known techniques such as use of offsets to ensure specific placement within the cache, as you mention.</div><div><br></div><div>My question is not in regard to whether virtual addresses or physical addresses are used for indexing, but rather the function itself that the hardware uses to perform indexing. Below is sample code which parses CPUID to extract this information. On an Intel Haswell, it shows the L3 to have "complex indexing" whereas L1/L2 to have direct. On an Intel Westmere, all caches use direct mapping. I noticed processors since Sandy Bridge have complex indexing in the LLC.</div><div><br></div><div>A direct-mapping function to index a cache, to me, means the use of specific well-known index bits within the physical address to determine the set into which it will be placed when cached. Complex indexing suggests this is no longer true. If true, how can we be sure the coloring strategy used by the kernel to sort pages, based on specific index bits, will continue to have the same effect on modern processors?</div><div><br></div><div>-Alex<br><div><br></div><div><div>/* Intel Programmer Manual instruction set reference</div><div> * CPUID, table 3-17.</div><div> */</div><div>#include <stdio.h></div><div>static const char *CACHE_STR[4] = {</div><div> "NULL",</div><div> "Data cache",</div><div> "Instruction cache",</div><div> "Unified cache",</div><div>};</div><div>int main(void)</div><div>{</div><div> unsigned int eax = 0, ebx = 0, ecx = 0, edx = 0;</div><div> unsigned int func = 4, val;</div><div> while (1) {</div><div> func = 4;</div><div> unsigned int _ecx = ecx++;</div><div> __asm__("cpuid \n\t"</div><div> : "=a"(eax), "=b"(ebx), "=c"(_ecx), "=d"(edx)</div><div> : "a"(func), "b"(ebx), "c"(_ecx), "d"(edx)</div><div> :);</div><div> /* check if a cache type is specified */</div><div> if (!(val = (eax & 0x1f)))</div><div> break;</div><div> printf("\ntype: %s\n", CACHE_STR[val]);</div><div><br></div><div> val = ((eax >> 5) & 0x7);</div><div> printf("level: %d\n", val);</div><div><br></div><div> val = ((ebx >> 22) & 0x3ff);</div><div> printf("ways: %d\n", val+1);</div><div><br></div><div> val = (_ecx & 0xffffffff);</div><div> printf("number of sets: %d\n", val+1);</div><div><br></div><div> val = ((edx >> 2) & 0x1);</div><div> printf("complex index: %d (%s)\n",</div><div> val, (val ? "complex indexing" : "direct-mapped"));</div><div><br></div><div> printf("\n");</div><div> }</div><div>}</div></div></div><div><br></div></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, May 30, 2015 at 7:21 PM, Matthew Dillon <span dir="ltr"><<a href="mailto:dillon@backplane.com" target="_blank">dillon@backplane.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>I think what you are describing is Intel's virtually indexed physical cache. It is designed to allow the L1 cache access to occur concurrent with the PTE (page table entry) lookup, which is much more efficient than having to wait for the page table lookup first and then start the memory access on the L1 cache.<br><br></div><div>The downside of this is that being virtually indexed, many programs tend to load at the same virtual memory address and memory map operations also tend to map at the same virtual memory address. When these represent private data rather than shared data, the cpu caches can wind up not being fully utilized. They are still N-way set associative so all is not lost, but they aren't optimally used.<br><br></div><div>The general solution is to implement an offset in the userland memory allocator (not so much in the kernel) which is what we do for larger memory allocations.<br></div><div><br></div>-Matt<br><div><br></div></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, May 29, 2015 at 8:52 AM, Alex Merritt <span dir="ltr"><<a href="mailto:merritt.alex@gmail.com" target="_blank">merritt.alex@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">I learned this recently, having gained access to newer Intel processors: these CPUs (Sandybridge, Haswell) use a form of indexing into the LLC which is no longer direct (i.e. taking specific bits from a physical address to determine which set the cache line in the LLC it goes into), but rather what they call "complex indexing"[1]. Presumably this is some proprietary hashing.<br></div><div class="gmail_quote"><br></div><div class="gmail_quote">I wanted to ask -- does page coloring, using direct indexing logic by the kernel, have an advantage if such hashing is used, also if we are unaware of the specific algorithm used to index the LLC? If we are unable to determine which pages will conflict in the cache without careful study, and assuming this algorithm may change between microarchitectures, it seems there may be less benefit to applying the technique.</div><div class="gmail_quote"><br></div><div class="gmail_quote">[1] <span style="font-family:Calibri,sans-serif;font-size:11pt"> </span><span style="font-family:Calibri,sans-serif;font-size:11pt">Intel
Manual Vol.2A Table 3-17, cpuid command 04H</span></div><div class="gmail_quote"><span style="font-family:Calibri,sans-serif;font-size:11pt"><br></span></div><div class="gmail_quote"><font face="Calibri, sans-serif"><span style="font-size:14.6666669845581px">-Alex</span></font></div><div class="gmail_quote"><br></div><div class="gmail_quote">On Tue, Apr 14, 2015 at 10:47 AM, Matthew Dillon <span dir="ltr"><<a href="mailto:dillon@backplane.com" target="_blank">dillon@backplane.com</a>></span> wrote:<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div>--<br><br></div><div>If I recall, FreeBSD mostly removed page coloring from their VM page allocation subsystem. DragonFly kept it and integrated it into the fine-grained-locked VM page allocator. There's no advantage to manipulating the parameters for two reasons.<br><br></div><div>First, all page coloring really does is try to avoid degenerate situations in the cpu caches. The cpu caches are already 4-way or 8-way set-associative. The page coloring improves this but frankly even the set associativeness in the base cpu caches gets us most of the way there. So adjusting the page coloring algorithms will not yield any improvements.<br><br></div><div>Secondly, the L1 cache is a physical memory cache but it is also virtually indexed. This is a cpu hardware optimization that allows the cache lookup to be initiated concurrent with the TLB lookup. Because of this, physical set associatively does not actually solve all the problems which can occur with a virtually indexed cache.<br><br></div><div>So the userland memory allocator implements an offsetting feature for allocations which attempts to address the virtually indexed cache issues. This feature is just as important as the physical page coloring feature for performance purposes.<br></div><div><br></div>-Matt<br><div><br></div></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Apr 14, 2015 at 10:10 AM, Alex Merritt <span dir="ltr"><<a href="mailto:merritt.alex@gmail.com" target="_blank">merritt.alex@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">Hello!<div><br></div><div>I am interested in learning whether Dragonfly supports large pages (2M and 1G), and secondly, what mechanisms exist for applications to have influence over the colors used to assign the physical pages backing their memory, specifically for private anonymous mmap'd regions. Regarding coloring, I'd like to be able to evaluate applications with a small number of colors (restricting their access to the last-level cache) and compare their performance to more/all colors available. I am initially looking to work in hacks to achieve this to perform some preliminary experiments, perhaps by way of a kernel module or something.</div><div><br></div><div>A cursory search of the code showed no hints at support for large pages, but I did find there are more internal functions governing the allocation of pages based on colors, compared to FreeBSD (10.1). In FreeBSD it seems colors are only considered for regions which are added that are backed by a file, but I am not 100% certain.</div><div><br></div><div>I appreciate any help!</div><div><br></div><div>Thanks,</div><div>Alex</div></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>