From owner-freebsd-sparc64@FreeBSD.ORG Tue Apr 15 14:22:15 2003 Return-Path: Delivered-To: freebsd-sparc64@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 4CA2737B401; Tue, 15 Apr 2003 14:22:15 -0700 (PDT) Received: from haldjas.folklore.ee (Haldjas.folklore.ee [193.40.6.121]) by mx1.FreeBSD.org (Postfix) with ESMTP id 36CDF43FA3; Tue, 15 Apr 2003 14:22:14 -0700 (PDT) (envelope-from narvi@haldjas.folklore.ee) Received: from haldjas.folklore.ee (localhost [127.0.0.1]) by haldjas.folklore.ee (8.12.3/8.11.3) with ESMTP id h3FLM8UE047368; Wed, 16 Apr 2003 00:22:09 +0300 (EEST) (envelope-from narvi@haldjas.folklore.ee) Received: from localhost (narvi@localhost)h3FLM7uc047365; Wed, 16 Apr 2003 00:22:08 +0300 (EEST) Date: Wed, 16 Apr 2003 00:22:07 +0300 (EEST) From: Narvi To: Jake Burkholder In-Reply-To: <20030415022455.GE97094@locore.ca> Message-ID: <20030415204755.C75698-100000@haldjas.folklore.ee> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII cc: freebsd-sparc64@freebsd.org cc: freebsd-sparc@freebsd.org Subject: Re: tlb, tsb & ...stuff X-BeenThere: freebsd-sparc64@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Porting FreeBSD to the Sparc List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 15 Apr 2003 21:22:15 -0000 On Mon, 14 Apr 2003, Jake Burkholder wrote: > [ ... ] > > > > > > With 3 levels this can support a 32 gigabyte virtual address space (fully > > > resident), but doesn't penalize processes with sparse address spaces due > > > to not requiring intermediate "page table pages" in all cases. Basically > > > like traditional page tables but backwards :). > > > > > > > This would have rather bad locality of access though, no? The conflict > > side of the thing is resolvable (to an extent) using it as a sum or xor > > addressed cache. I guess I should whip up some code to show what I mean. > > Missing in L2 can delay you for say 100 cycles. Also, this scheme cause > > the pages to accumulate with basicly no eviction of 'vist once' pages. > > Yes, you're right. The current scheme has ok cache locality and the > eviction properties are nice. How does an xor addressed cache work? > I would be interested to see a simple example. The hash function needs > to be as simple as possible because it needs to fit in 1 or 2 instructions > in the tlb fault handlers. So '&' is attractive but may not have great > properties. > xor and sum addressed caches rely on additiopnal information beyond just the cache-size covering ones to compute the index, so simple examples might be: xor: &pm->tsb[((vpn >> (TTE_SHIFT + TSB_SHIFT)) ^ (vpn >> TTE_SHIFT)) & TSB_MASK)] sum: &pm->tsb[((vpn >> (TTE_SHIFT + TSB_SHIFT)) + (vpn >> TTE_SHIFT)) & TSB_MASK)] so essentially it would add a shift and a add/xor. The aim is to make most of the power of two and other pobvious conflict patterns be non-conflicting in the cache. A xor based cache has some interesting propeties (it doesn't matter whetever you use n consequtive or "conflicting" entries, the first n-1 next conflicts get mapped to different lines) - its also nice in a skew cache - the expense is bad locality. With a four-way cache, sum might be better when you consider locality. I gues thepart that worries me with only one TSB strategy is that on UltraSparc I/II the misses will be capacity misses as the TLB is fully associative, but on USPARC3 you get a 1024 entry 4-way tlb that will give you completely different pattern on many programs. > [ ... ] > > > > Another way to overcome the would be to allocate teh different "ways" of > > the TSB separately, so that the area need not be contiguous. > > This has got me thinking. The main problem is how to map the tsb into > contiguous virtual address space so it can be indexed easily by the tlb > fault handlers, ideally base + offset, where offset is a hash of the > virtual address, with no indirection. But the only requirement for > contiguity is to make the tlb fault handlers fast. When its accessed by > the kernel for pmap processing it doesn't much matter because there are > other slow things going, adding indirection there won't make much difference. > Just mapping it into the kernel address space is easy because faults on > the tsb inside of the user tlb fault handler are handled uniformly as normal > kernel tlb faults. If they were handled specially it might be possible > to use a multi level structure that's more transparent. > Something I really liked from your post about tree like structure was the idea of having a simple (lets call it L0TSB?) buffer at the front with the complex lookup hapenning later. We could even simplify it to the point where the L1 table would only contain the 8KB page number and a pointer to the entry in the TSB, so the 'fast load' handler would basicly be (in pseudcode): offset = ((v >> 10) & L0TSB_MASK); if ((l0tsb[offset+1] == 0) || (l0tsb[offset] != v)) do_real_tsb_load(v); load_from_tsb(&l0tsb[bucket+1]); return_from_exception(); which is almost as simple in sparc assembler (sorry, i'm slow writing sparc asm), short and can accomodate a two-way cache just as easily. It does mean that loading of non-8K pages will always be slower to create a fast simple case for 8KB pages. This should also provide for very fast TLB loads for cases where the LRU replacement TLB has zero locality either due to repetitive loads that cause the LRU to throw out the about to be used again entries ( not blocked for TLB matrix codes/bitmap ops) or sparse access to memory (yay for tree / linked list structures linking data present all over the heap). It also means that the "real" tsb can be more complex then now without causing speed-downs for applications, as long as most cases are handled at L0 level and there is no restriction for the tsb to be continuous. > [ ... ] > > > > I was more thinking about say using 64K pages for user stack or malloc or > > similar - it doesn't quite have the same complexity as general mapping > > scheme, in the malloc case could be requested by the user and would keep > > pressure or TLB & faults down. But sounds like this is not simple/feasible > > for now. > > I'd really like to see this, but yes it is hard to do in a generalized way. > The vm system needs to be aware of the contiguity of physical pages, and > try to make reservations of large contiguous regions, expecting all the > pages to be faulted in with the same protections so the mapping can be > "upgraded" to use a larger page size. The best work that I've seen on > this topic so far is this paper: > http://www.cs.rice.edu/~ssiyer/r/superpages/ > That Alan Cox is a FreeBSD guy, so we may see this in FreeBSD at some point. > Well, for me theproblem part starts where people start talking about page size promotion/demotion and not simply sneakily using some page size (say 64K) for specific memory regions and never promoting / demoting pages. The 64K pages are sort of magic in that way though, and in general it would suck to use the other pages sizes that way, except for possibly mapping framebuffers and similar. > Jake >