Date: Sat, 6 May 2006 00:34:24 GMT From: Kip Macy <kmacy@FreeBSD.org> To: Perforce Change Reviews <perforce@freebsd.org> Subject: PERFORCE change 96722 for review Message-ID: <200605060034.k460YOvw023311@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://perforce.freebsd.org/chv.cgi?CH=96722 Change 96722 by kmacy@kmacy_storage:sun4v_rwbuf on 2006/05/06 00:33:31 remove initial hand memory allocation for hash tables initial cut of arbitrary collision depth handling Affected files ... .. //depot/projects/kmacy_sun4v/src/sys/sparc64/sparc64/genassym.c#19 edit .. //depot/projects/kmacy_sun4v/src/sys/sun4v/include/tte_hash.h#12 edit .. //depot/projects/kmacy_sun4v/src/sys/sun4v/sun4v/exception.S#47 edit .. //depot/projects/kmacy_sun4v/src/sys/sun4v/sun4v/pmap.c#45 edit .. //depot/projects/kmacy_sun4v/src/sys/sun4v/sun4v/tte_hash.c#20 edit Differences ... ==== //depot/projects/kmacy_sun4v/src/sys/sparc64/sparc64/genassym.c#19 (text+ko) ==== @@ -183,8 +183,10 @@ ASSYM(VTD_REF, VTD_REF); ASSYM(VTD_W, VTD_W); ASSYM(VTD_SW_W, VTD_SW_W); +ASSYM(VTD_LOCK, VTD_LOCK); ASSYM(THE_SHIFT, THE_SHIFT); +ASSYM(TH_COLLISION_SHIFT, TH_COLLISION_SHIFT); ASSYM(HVTSB_PA, offsetof(struct hv_tsb_info, hvtsb_pa)); ASSYM(PM_HASHSCRATCH, offsetof(struct pmap, pm_hashscratch)); ASSYM(PM_TSBSCRATCH, offsetof(struct pmap, pm_tsbscratch)); @@ -351,3 +353,4 @@ ASSYM(VM_MIN_DIRECT_ADDRESS, VM_MIN_DIRECT_ADDRESS); ASSYM(VM_MIN_PROM_ADDRESS, VM_MIN_PROM_ADDRESS); ASSYM(VM_MAX_PROM_ADDRESS, VM_MAX_PROM_ADDRESS); + ==== //depot/projects/kmacy_sun4v/src/sys/sun4v/include/tte_hash.h#12 (text+ko) ==== @@ -1,12 +1,14 @@ #ifndef _MACHINE_TTE_HASH_H_ #define _MACHINE_TTE_HASH_H_ -#define THE_SHIFT 6 /* size of hash entry is 64-bytes */ +#define THE_SHIFT 6 /* size of hash entry is 64-bytes */ +#define TH_COLLISION_SHIFT 47 /* bit 47 will never be set for a valid tag */ +#define TH_COLLISION (1UL << TH_COLLISION_SHIFT) struct tte_hash; typedef struct tte_hash *tte_hash_t; -void tte_hash_init(vm_paddr_t); +void tte_hash_init(void); void tte_hash_clear(tte_hash_t hash); ==== //depot/projects/kmacy_sun4v/src/sys/sun4v/sun4v/exception.S#47 (text+ko) ==== @@ -491,7 +491,7 @@ .macro spill_mixed_ktt1_sk btst 1, %sp bz,a,pt %xcc, fault_32bit_sk - srl %sp, 0, %sp + srl %sp, 0, %sp ba,a,pt %xcc, fault_64bit_sk nop .align 128 @@ -1359,13 +1359,13 @@ andn tmp, lock_bit, tmp ; \ stxa tmp, [addr + 8]%asi ; -#define HASH_LOOKUP(addr, tag, searchtag, endlabel, matchlabel) \ +#define HASH_LOOKUP(addr, tag, searchtag, faillabel, matchlabel) \ ldda [addr]%asi, tag ; \ cmp tag, searchtag ; \ be,pn %xcc, matchlabel ; \ nop ; \ cmp tag, %g0 ; \ - be,pn %xcc, endlabel ; \ + be,pn %xcc, faillabel ; \ nop #define RESTORE_TRAPWIN(pcpu, cansave, label1, label2) \ @@ -1518,18 +1518,30 @@ rdpr %tt, %g3 ! reload trap type tsb_miss_lookup_0: - HASH_LOOKUP(%g2, %l6, %l2, 7f, 8f) + HASH_LOOKUP(%g2, %l6, %l2, tsb_miss_not_found, 8f) tsb_miss_lookup_1: add %g2, 16, %g2 - HASH_LOOKUP(%g2, %l6, %l2, 7f, 8f) + HASH_LOOKUP(%g2, %l6, %l2, tsb_miss_not_found, 8f) tsb_miss_lookup_2: add %g2, 16, %g2 - HASH_LOOKUP(%g2, %l6, %l2, 7f, 8f) + HASH_LOOKUP(%g2, %l6, %l2, tsb_miss_not_found, 8f) tsb_miss_lookup_3: add %g2, 16, %g2 - HASH_LOOKUP(%g2, %l6, %l2, 7f, 8f) + HASH_LOOKUP(%g2, %l6, %l2, tsb_miss_not_found, 8f) + mov 1, %g2 + sethi %uhi(VM_MIN_DIRECT_ADDRESS), %g3 + cmp %l3, ASI_LDTD_N + sllx %g2, TH_COLLISION_SHIFT, %g2 + sllx %g3, 32, %g3 + beq,pt %xcc, 7f + nop + andn %l7, %g3, %l7 ! generate real address +7: + andcc %l6, %g2, %g0 + rdpr %tt, %g3 + bnz,a,pt %xcc, tsb_miss_lookup_0 + mov %l7, %g2 tsb_miss_not_found: -7: ! not found ! we need to jump to tl0_trap to drop us back down to tl0 ! and take us to trap(...) to service the fault wr %g0, %l3, %asi @@ -1588,9 +1600,13 @@ MAGIC_TRAP_ON;MAGIC_TRAP_ON;MAGIC_EXIT ! die if all we're doing ! is storing same data #else + mov %o0, %g1 + mov %o5, %g7 PUTCHAR(0x5a) PUTCHAR(0x5a) PUTCHAR(0x5a) + mov %g1, %o0 + mov %g7, %o5 MAGIC_TRAP_ON; MAGIC_TRAP_OFF #endif 12: ==== //depot/projects/kmacy_sun4v/src/sys/sun4v/sun4v/pmap.c#45 (text+ko) ==== @@ -106,7 +106,6 @@ int sparc64_nmemreg; extern vm_paddr_t mmu_fault_status_area; -vm_paddr_t proc0_mem; /* @@ -631,7 +630,6 @@ */ mmu_fault_status_area = pmap_bootstrap_alloc(MMFSA_SIZE*MAXCPU); - proc0_mem = pmap_bootstrap_alloc(PAGE_SIZE*4*400); /* * Allocate and map the message buffer. */ @@ -924,19 +922,18 @@ } goto validate; - } - /* - * Mapping has changed, invalidate old range and fall through to - * handle validating new mapping. - */ - if (opa) { + } else if (opa) { + /* + * Mapping has changed, invalidate old range and fall through to + * handle validating new mapping. + */ if (otte_data & VTD_WIRED) pmap->pm_stats.wired_count--; if (otte_data & VTD_MANAGED) { om = PHYS_TO_VM_PAGE(opa); pmap_remove_entry(pmap, om, va); } - } else + } else pmap->pm_stats.resident_count++; /* @@ -1118,7 +1115,7 @@ pv_entry_high_water = 9 * (pv_entry_max / 10); uma_zone_set_obj(pvzone, &pvzone_obj, pv_entry_max); - tte_hash_init(proc0_mem); + tte_hash_init(); } ==== //depot/projects/kmacy_sun4v/src/sys/sun4v/sun4v/tte_hash.c#20 (text+ko) ==== @@ -59,20 +59,21 @@ #define HASH_MASK(th) ((th->th_size << (PAGE_SHIFT - THE_SHIFT)) - 1) #define HASH_VALID 0x1 + #define DEBUG struct tte_hash_entry; -typedef union { +#define MAX_FRAGMENT_ENTRIES ((PAGE_SIZE / sizeof(struct tte_hash_entry)) - 1) + +typedef union tte_hash_field_ { struct { uint64_t tag; uint64_t data; } tte; struct { - uint16_t flags; - uint16_t count; - uint32_t vapad; /* zero if this is a collision entry */ - struct tte_hash_entry *next; + uint64_t flags; + union tte_hash_field_ *next; } of; } tte_hash_field, *tte_hash_field_t; @@ -82,16 +83,33 @@ } *tte_hash_entry_t; +struct fragment_header { + struct fragment_header *fh_next; + uint16_t fh_count; + uint16_t fh_free_head; + uint16_t pad[26]; +}; + +CTASSERT(sizeof(struct fragment_header) == sizeof(struct tte_hash_entry)); + struct tte_hash { uint16_t th_size; /* size in pages */ uint16_t th_context; /* TLB context */ uint32_t th_entries; /* # pages held */ tte_hash_entry_t th_hashtable; /* hash of TTEs */ + struct tte_hash_fragment *th_fhhead; + struct tte_hash_fragment *th_fhtail; +}; + +struct tte_hash_fragment { + struct fragment_header thf_head; + struct tte_hash_entry thf_entries[127]; }; +CTASSERT(sizeof(struct tte_hash_fragment) == PAGE_SIZE); + + static struct tte_hash kernel_tte_hash; -static vm_paddr_t proc0_mem; - /* * Data for the tte_hash allocation mechanism */ @@ -146,13 +164,12 @@ } void -tte_hash_init(vm_paddr_t bootmem) +tte_hash_init(void) { thzone = uma_zcreate("TTE_HASH", sizeof(struct tte_hash), NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, UMA_ZONE_VM | UMA_ZONE_NOFREE); tte_hash_max = maxproc; uma_zone_set_obj(thzone, &thzone_obj, tte_hash_max); - proc0_mem = bootmem; } @@ -178,7 +195,7 @@ tte_hash_t th; vm_page_t m, tm; int i; - static int proc0_mem_allocated; + static int color; th = get_tte_hash(); @@ -187,15 +204,6 @@ th->th_context = (uint16_t)context; m = NULL; - - if (proc0_mem_allocated < 400) { - - proc0_mem_allocated++; - th->th_hashtable = (void *)TLB_PHYS_TO_DIRECT(proc0_mem); - proc0_mem += PAGE_SIZE*HASH_SIZE; - goto done; - } - while (m == NULL) { m = vm_page_alloc_contig(HASH_SIZE, 2*PAGE_SIZE_4M, (1UL<<34), PAGE_SIZE, (1UL<<34)); @@ -208,9 +216,21 @@ if (tm->flags & PG_ZERO) pmap_zero_page(tm); } + th->th_hashtable = (void *)TLB_PHYS_TO_DIRECT(VM_PAGE_TO_PHYS(m)); + m = NULL; + while (m == NULL) { + m = vm_page_alloc(NULL, color++, + VM_ALLOC_NORMAL | VM_ALLOC_NOOBJ | VM_ALLOC_WIRED | + VM_ALLOC_ZERO); - th->th_hashtable = (void *)TLB_PHYS_TO_DIRECT(VM_PAGE_TO_PHYS(m)); -done: + if (m == NULL) + VM_WAIT; + } + if (m->flags & PG_ZERO) + pmap_zero_page(m); + + th->th_fhtail = th->th_fhhead = (void *)TLB_PHYS_TO_DIRECT(VM_PAGE_TO_PHYS(m)); + *scratchval = (uint64_t)((vm_offset_t)th->th_hashtable) | ((vm_offset_t)th->th_size); return (th); @@ -231,6 +251,26 @@ field->tte.data = tte | (field->tte.data & VTD_LOCK); } +static tte_hash_field_t +tte_hash_allocate_fragment_entry(tte_hash_t th, tte_hash_field_t field) +{ + struct tte_hash_fragment *fh; + tte_hash_field_t newfield; + + fh = th->th_fhtail; + if (fh->thf_head.fh_count == MAX_FRAGMENT_ENTRIES) { + /* XXX allocate a new page */ + panic("new fragment page allocation unimplemented"); + } + newfield = fh->thf_entries[++fh->thf_head.fh_free_head].the_fields; + fh->thf_head.fh_count++; + tte_hash_set_field(&newfield[0], field->tte.tag, field->tte.data); + field->of.flags = TH_COLLISION; + field->of.next = newfield; + + return newfield; +} + static __inline tte_t tte_hash_lookup_inline(tte_hash_t th, vm_offset_t va, tte_hash_field_t *field) { @@ -245,13 +285,28 @@ fields = (th->th_hashtable[hash_index].the_fields); entry = 0; +retry: for (i = 0; i < 4 && fields[i].tte.tag != 0; i++) { if (((fields[i].tte.tag << TTARGET_VA_SHIFT) == (va & ~PAGE_MASK_4M))) { entry = (fields[i].tte.data & ~VTD_LOCK); break; } } - if (field && i < 4) + if (i == 4) { + if (fields[3].of.flags & TH_COLLISION) { + printf("following next pointer looking up 0x%lx\n", va); + fields = fields[3].of.next; + goto retry; + } + printf("allocating fragment entry and shifting entry for tag=0x%lx data=0x%lx\n", + fields[3].tte.tag, fields[3].tte.data); + fields = tte_hash_allocate_fragment_entry(th, &fields[3]); + printf("new fragment address is %p\n", fields); + /* entry following shifted entry is the first unallocated */ + i = 1; + } + + if (field) *field = &fields[i]; /* * XXX handle the case of collisions > 3 @@ -260,12 +315,41 @@ } +static __inline void +tte_hash_lookup_last_inline(tte_hash_t th, vm_offset_t va, tte_hash_field_t *field) +{ + uint64_t hash_shift, hash_index; + tte_hash_field_t fields; + int i; + /* XXX - only handle 8K pages for now */ + + hash_shift = PAGE_SHIFT; + hash_index = (va >> hash_shift) & HASH_MASK(th); + fields = (th->th_hashtable[hash_index].the_fields); + +retry: + for (i = 0; i < 4 && fields[i + 1].tte.tag != 0; i++) + ; + + if (i == 4) { + if (fields[3].of.flags & TH_COLLISION) { + fields = fields[3].of.next; + goto retry; + } + /* if there is no collision pointer, 3 is the last entry */ + i = 3; + } + + if (field) + *field = &fields[i]; +} + + tte_t tte_hash_delete(tte_hash_t th, vm_offset_t va) { uint64_t hash_shift, hash_index; tte_hash_field_t fields, lookup_field, last_field; - int i; tte_t tte_data; /* XXX - only handle 8K pages for now */ @@ -276,17 +360,14 @@ hash_bucket_lock(fields); - tte_data = tte_hash_lookup_inline(th, va, &lookup_field); - - if (tte_data == 0) + if ((tte_data = tte_hash_lookup_inline(th, va, &lookup_field)) == 0) goto done; th->th_entries--; - for (i = 0; (i < 4) && (fields[i + 1].tte.tag != 0); i++) - ; - last_field = &fields[i]; + tte_hash_lookup_last_inline(th, va, &last_field); + /* move last field's values in to the field we are deleting */ if (lookup_field != last_field) tte_hash_set_field(lookup_field, last_field->tte.tag, last_field->tte.data); @@ -378,7 +459,7 @@ uint64_t tte_hash_set_scratchpad_user(tte_hash_t th, uint64_t context) { - + uint64_t hash_scratch; /* This will break if a hash table ever grows above 64MB * 2^(13+13)
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200605060034.k460YOvw023311>