Date: Fri, 19 May 2006 07:56:30 GMT From: Kip Macy <kmacy@FreeBSD.org> To: Perforce Change Reviews <perforce@freebsd.org> Subject: PERFORCE change 97450 for review Message-ID: <200605190756.k4J7uUNv074951@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
http://perforce.freebsd.org/chv.cgi?CH=97450 Change 97450 by kmacy@kmacy_storage:sun4v_rwbuf on 2006/05/19 07:56:13 dramatically simplify tte hash code by not overloading last entry in a bucket Affected files ... .. //depot/projects/kmacy_sun4v/src/sys/sun4v/include/tte_hash.h#17 edit .. //depot/projects/kmacy_sun4v/src/sys/sun4v/sun4v/exception.S#55 edit .. //depot/projects/kmacy_sun4v/src/sys/sun4v/sun4v/tte_hash.c#32 edit Differences ... ==== //depot/projects/kmacy_sun4v/src/sys/sun4v/include/tte_hash.h#17 (text+ko) ==== @@ -2,7 +2,7 @@ #define _MACHINE_TTE_HASH_H_ #define HASH_ENTRY_SHIFT 2 -#define HASH_ENTRIES (1 << HASH_ENTRY_SHIFT) +#define HASH_ENTRIES ((1 << HASH_ENTRY_SHIFT) - 1) #define THE_SHIFT (TTE_SHIFT + HASH_ENTRY_SHIFT) /* size of TSB entry * #entries */ #define TH_COLLISION_SHIFT 47 /* bit 47 will never be set for a valid tag */ #define TH_COLLISION (1UL << TH_COLLISION_SHIFT) ==== //depot/projects/kmacy_sun4v/src/sys/sun4v/sun4v/exception.S#55 (text+ko) ==== @@ -1516,10 +1516,10 @@ tsb_miss_lookup_2: add %g2, 16, %g2 HASH_LOOKUP(%g2, %l6, %l2, tsb_miss_not_found, tsb_miss_found) +#if HASH_ENTRY_SHIFT > 2 tsb_miss_lookup_3: add %g2, 16, %g2 HASH_LOOKUP(%g2, %l6, %l2, tsb_miss_not_found, tsb_miss_found) -#ifdef notyet tsb_miss_lookup_4: add %g2, 16, %g2 HASH_LOOKUP(%g2, %l6, %l2, tsb_miss_not_found, tsb_miss_found) @@ -1529,23 +1529,27 @@ tsb_miss_lookup_6: add %g2, 16, %g2 HASH_LOOKUP(%g2, %l6, %l2, tsb_miss_not_found, tsb_miss_found) +#endif tsb_miss_collision: add %g2, 16, %g2 - ldda [%g2]%asi, %l6 -#endif - mov 1, %g2 + ldda [%g2]%asi, %l6 + sethi %uhi(VM_MIN_DIRECT_ADDRESS), %g3 cmp %l3, ASI_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 + srl %l6, 0, %l6 + sethi %hi(0xcafebabe), %g3 + mov %l7, %g2 + or %g3, %lo(0xcafebabe), %g3 + cmp %g3, %l6 + rdpr %tt, %g3 + beq,pt %xcc, tsb_miss_lookup_0 + nop + tsb_miss_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 ==== //depot/projects/kmacy_sun4v/src/sys/sun4v/sun4v/tte_hash.c#32 (text+ko) ==== @@ -59,36 +59,38 @@ #include <machine/tte_hash.h> #define HASH_SIZE (1 << HASH_ENTRY_SHIFT) -#define HASH_MASK(th) ((th->th_size << (PAGE_SHIFT - THE_SHIFT)) - 1) +#define HASH_MASK(th) ((th->th_size<<(PAGE_SHIFT-THE_SHIFT))-1) #define NULL_TAG 0 +#define MAGIC_VALUE 0xcafebabe - struct tte_hash_entry; +struct of_field; #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 { - uint64_t flags; - union tte_hash_field_ *next; - } of; +typedef struct tte_hash_field_ { + uint64_t tag; + uint64_t data; } tte_hash_field, *tte_hash_field_t; +struct of_field { + int16_t count; + uint8_t lock; + uint8_t pad; + uint32_t flags; + struct tte_hash_entry *next; +}; typedef struct tte_hash_entry { tte_hash_field the_fields[HASH_ENTRIES]; + struct of_field of; } *tte_hash_entry_t; - struct fragment_header { struct tte_hash_fragment *fh_next; uint16_t fh_count; uint16_t fh_free_head; - uint16_t pad[26]; + uint8_t pad[52]; }; CTASSERT(sizeof(struct fragment_header) == sizeof(struct tte_hash_entry)); @@ -104,7 +106,7 @@ struct tte_hash_fragment { struct fragment_header thf_head; - struct tte_hash_entry thf_entries[127]; + struct tte_hash_entry thf_entries[MAX_FRAGMENT_ENTRIES]; }; CTASSERT(sizeof(struct tte_hash_fragment) == PAGE_SIZE); @@ -142,7 +144,6 @@ uma_zfree(thzone, th); } - void tte_hash_init(void) { @@ -245,15 +246,15 @@ static __inline void tte_hash_set_field(tte_hash_field_t field, uint64_t tag, tte_t tte) { - field->tte.tag = tag; - field->tte.data = tte | (field->tte.data & VTD_LOCK); + field->tag = tag; + field->data = tte | (field->data & VTD_LOCK); } -static tte_hash_field_t +static tte_hash_entry_t tte_hash_allocate_fragment_entry(tte_hash_t th) { struct tte_hash_fragment *fh; - tte_hash_field_t newfield; + tte_hash_entry_t newentry; vm_page_t m; static int color; @@ -278,11 +279,11 @@ printf("new fh=%p \n", fh); } - newfield = fh->thf_entries[++fh->thf_head.fh_free_head].the_fields; - bzero(newfield, sizeof(*newfield)); + newentry = &fh->thf_entries[++fh->thf_head.fh_free_head]; + fh->thf_head.fh_count++; - return (newfield); + return (newentry); } /* @@ -296,113 +297,90 @@ static __inline tte_t -tte_hash_lookup_inline(tte_hash_field_t sfields, tte_t tte_tag, boolean_t setfield) +tte_hash_lookup_inline(tte_hash_entry_t entry, tte_t tte_tag, boolean_t insert) { int i; - tte_t entry; + tte_t tte_data; tte_hash_field_t fields; + tte_hash_entry_t curentry; + tte_data = 0; - fields = sfields; - entry = 0; -retry: - for (i = 0; i < HASH_ENTRIES && fields[i].tte.tag != 0; i++) { - if (tte_tag == fields[i].tte.tag) { - entry = (fields[i].tte.data & ~VTD_LOCK); - break; + do { + curentry = entry; /* want a valid pointer */ + fields = curentry->the_fields; + for (i = 0; i < entry->of.count; i++) { + if (fields[i].tag == tte_tag) { + tte_data = (fields[i].data & ~VTD_LOCK); + PCPU_SET(lookup_field, (u_long)&fields[i]); + break; + } } - } - if (i == HASH_ENTRIES) { + + entry = entry->of.next; + } while (curentry->of.flags == MAGIC_VALUE); + + if (insert && (tte_data == 0)) { + if (curentry->of.count == HASH_ENTRIES) { + curentry->of.flags = MAGIC_VALUE; + PCPU_SET(lookup_field, (u_long)&curentry->of); + } else { + i = curentry->of.count++; + PCPU_SET(lookup_field, (u_long)&fields[i]); #ifdef DEBUG - if (fields[(HASH_ENTRIES - 1)].of.flags & TH_INVALID) { - hash_bucket_unlock(sfields, PSTATE_KERNEL); - printf("invalid bit set in lookup flags=0x%lx next=%p (sf=f):%d\n", - fields[(HASH_ENTRIES - 1)].of.flags, - fields[(HASH_ENTRIES - 1)].of.next, - (sfields==fields)); - panic("bad flags"); + if (curentry->of.count > HASH_ENTRIES) + panic("count too large count=%d", i); +#endif } -#endif - if (fields[(HASH_ENTRIES - 1)].of.flags == TH_COLLISION) { - fields = fields[(HASH_ENTRIES - 1)].of.next; - goto retry; - } - i = (HASH_ENTRIES - 1); } - if (setfield == TRUE) - PCPU_SET(lookup_field, (u_long)&fields[i]); - - return (entry); + return (tte_data); } static __inline void -tte_hash_lookup_last_inline(tte_hash_field_t sfields) +tte_hash_lookup_last_inline(tte_hash_entry_t entry) { - int i, depth; + int count; tte_hash_field_t fields; - - depth = 0; - fields = sfields; -retry: - for (i = 0; i < (HASH_ENTRIES - 1); i++) - if (fields[i + 1].tte.tag == 0) - break; + + fields = entry->the_fields; - if (i < (HASH_ENTRIES - 1)) - PCPU_SET(last_field, (u_long)&fields[i]); - else { -#ifdef DEBUG - if (fields[(HASH_ENTRIES - 1)].of.flags & TH_INVALID) { - hash_bucket_unlock(sfields, PSTATE_KERNEL); - printf("invalid bit set in lookup_last flags=0x%lx next=%p (sf=f):%d, depth=%d", - fields[(HASH_ENTRIES - 1)].of.flags, - fields[(HASH_ENTRIES - 1)].of.next, - (sfields==fields), depth); - panic("bad flags"); - } -#endif - if (fields[(HASH_ENTRIES - 1)].of.flags == TH_COLLISION) { - if (fields[(HASH_ENTRIES - 1)].of.next[0].tte.tag != 0) { - fields = fields[(HASH_ENTRIES - 1)].of.next; - depth++; - goto retry; - } else { - /* 3rd entry is last */ - PCPU_SET(last_field, (u_long)&fields[(HASH_ENTRIES - 2)]); - /* clear collision pointer */ - tte_hash_set_field(&fields[(HASH_ENTRIES - 1)], 0, 0); + while (entry->of.flags == MAGIC_VALUE && (entry->of.next->of.count > 1)) + entry = entry->of.next; - } - } else - PCPU_SET(last_field, (u_long)&fields[(HASH_ENTRIES - 1)]); /* last in bucket */ + if ((entry->of.flags == MAGIC_VALUE) && entry->of.next->of.count == 1) { + PCPU_SET(last_field, (u_long)&entry->of.next->the_fields[0]); + entry->of.next = NULL; + entry->of.flags = 0; + } else { + count = --entry->of.count; + PCPU_SET(last_field, (u_long)&entry->the_fields[count]); } - } tte_t tte_hash_clear_bits(tte_hash_t th, vm_offset_t va, uint64_t flags) { uint64_t hash_shift, hash_index, s; - tte_hash_field_t fields; + tte_hash_entry_t entry; tte_t otte_data, tte_tag; /* 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); - + entry = (&th->th_hashtable[hash_index]); + tte_tag = (((uint64_t)th->th_context << TTARGET_CTX_SHIFT)|(va >> TTARGET_VA_SHIFT)); - s = hash_bucket_lock(fields); - if((otte_data = tte_hash_lookup_inline(fields, tte_tag, TRUE)) != 0) + s = hash_bucket_lock(entry->the_fields); + if((otte_data = tte_hash_lookup_inline(entry, tte_tag, FALSE)) != 0) tte_hash_set_field((tte_hash_field_t)PCPU_GET(lookup_field), - ((tte_hash_field_t)PCPU_GET(lookup_field))->tte.tag, - ((tte_hash_field_t)PCPU_GET(lookup_field))->tte.data & ~flags); + ((tte_hash_field_t)PCPU_GET(lookup_field))->tag, + ((tte_hash_field_t)PCPU_GET(lookup_field))->data & ~flags); - hash_bucket_unlock(fields, s); + hash_bucket_unlock(entry->the_fields, s); return (otte_data); } @@ -411,97 +389,55 @@ tte_hash_delete(tte_hash_t th, vm_offset_t va) { uint64_t hash_shift, hash_index, s; - tte_hash_field_t fields; + tte_hash_entry_t entry; tte_t tte_data, tte_tag; /* 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); + entry = (&th->th_hashtable[hash_index]); tte_tag = (((uint64_t)th->th_context << TTARGET_CTX_SHIFT)|(va >> TTARGET_VA_SHIFT)); - s = hash_bucket_lock(fields); + s = hash_bucket_lock(entry->the_fields); - if ((tte_data = tte_hash_lookup_inline(fields, tte_tag, TRUE)) == 0) + if ((tte_data = tte_hash_lookup_inline(entry, tte_tag, FALSE)) == 0) goto done; - tte_hash_lookup_last_inline(fields); + tte_hash_lookup_last_inline(entry); #ifdef DEBUG - if (((tte_hash_field_t)PCPU_GET(last_field))->tte.tag == 0) { - hash_bucket_unlock(fields, s); + if (((tte_hash_field_t)PCPU_GET(last_field))->tag == 0) { + hash_bucket_unlock(entry->the_fields, s); panic("lookup_last failed for va=0x%lx\n", va); } #endif /* move last field's values in to the field we are deleting */ if (PCPU_GET(lookup_field) != PCPU_GET(last_field)) tte_hash_set_field((tte_hash_field_t)PCPU_GET(lookup_field), - ((tte_hash_field_t)PCPU_GET(last_field))->tte.tag, - ((tte_hash_field_t)PCPU_GET(last_field))->tte.data); + ((tte_hash_field_t)PCPU_GET(last_field))->tag, + ((tte_hash_field_t)PCPU_GET(last_field))->data); tte_hash_set_field((tte_hash_field_t)PCPU_GET(last_field), 0, 0); done: - hash_bucket_unlock(fields, s); + hash_bucket_unlock(entry->the_fields, s); + if (tte_data) + th->th_entries--; - if (tte_data) - th->th_entries--; -#ifdef DEBUG - if (tte_hash_lookup(th, va) != 0) - panic("tte_hash_delete failed"); -#endif return (tte_data); } void tte_hash_insert(tte_hash_t th, vm_offset_t va, tte_t tte_data) { - - uint64_t hash_shift, hash_index, s; - tte_hash_field_t fields, newfield; - tte_t otte_data, tte_tag; - - /* 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); - - tte_tag = (((uint64_t)th->th_context << TTARGET_CTX_SHIFT)|(va >> TTARGET_VA_SHIFT)); - - s = hash_bucket_lock(fields); - otte_data = tte_hash_lookup_inline(fields, tte_tag, TRUE); #ifdef DEBUG - if (otte_data) { - hash_bucket_unlock(fields, s); - panic("mapping for va=0x%lx already exists tte_data=0x%lx\n", va, otte_data); - } + if (tte_hash_lookup(th, va) != 0) + panic("mapping for va=0x%lx already exists", va); #endif - if (((tte_hash_field_t)PCPU_GET(lookup_field))->tte.tag != 0) { - hash_bucket_unlock(fields, s); - newfield = tte_hash_allocate_fragment_entry(th); - s = hash_bucket_lock(fields); - tte_hash_set_field(newfield, - ((tte_hash_field_t)PCPU_GET(lookup_field))->tte.tag, - ((tte_hash_field_t)PCPU_GET(lookup_field))->tte.data); - - ((tte_hash_field_t)PCPU_GET(lookup_field))->of.flags = TH_COLLISION; - ((tte_hash_field_t)PCPU_GET(lookup_field))->of.next = newfield; - PCPU_SET(lookup_field, (u_long)&newfield[1]); - } - - tte_hash_set_field((tte_hash_field_t)PCPU_GET(lookup_field), tte_tag, tte_data); + tte_hash_update(th, va, tte_data); - hash_bucket_unlock(fields, s); -#ifdef DEBUG - if (tte_hash_lookup(th, va) == 0) - panic("tte_hash_insert failed"); -#endif - - th->th_entries++; } - - /* * If leave_locked is true the tte's data field will be returned to * the caller with the hash bucket left locked @@ -512,19 +448,19 @@ tte_hash_lookup(tte_hash_t th, vm_offset_t va) { uint64_t hash_shift, hash_index, s; - tte_hash_field_t fields; + tte_hash_entry_t entry; tte_t tte_data, tte_tag; /* 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); + entry = (&th->th_hashtable[hash_index]); tte_tag = (((uint64_t)th->th_context << TTARGET_CTX_SHIFT)|(va >> TTARGET_VA_SHIFT)); - s = hash_bucket_lock(fields); - tte_data = tte_hash_lookup_inline(fields, tte_tag, FALSE); - hash_bucket_unlock(fields, s); + s = hash_bucket_lock(entry->the_fields); + tte_data = tte_hash_lookup_inline(entry, tte_tag, FALSE); + hash_bucket_unlock(entry->the_fields, s); return (tte_data); } @@ -563,44 +499,41 @@ tte_t tte_hash_update(tte_hash_t th, vm_offset_t va, tte_t tte_data) { - uint64_t hash_shift, hash_index; - tte_hash_field_t fields, newfield; + + uint64_t hash_shift, hash_index, s; + tte_hash_entry_t entry, newentry; tte_t otte_data, tte_tag; - uint64_t s; /* 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); + entry = (&th->th_hashtable[hash_index]); tte_tag = (((uint64_t)th->th_context << TTARGET_CTX_SHIFT)|(va >> TTARGET_VA_SHIFT)); - s = hash_bucket_lock(fields); - otte_data = tte_hash_lookup_inline(fields, tte_tag, TRUE); + s = hash_bucket_lock(entry->the_fields); + otte_data = tte_hash_lookup_inline(entry, tte_tag, TRUE); - if (otte_data == 0 && ((tte_hash_field_t)PCPU_GET(lookup_field))->tte.tag != 0) { - hash_bucket_unlock(fields, s); - newfield = tte_hash_allocate_fragment_entry(th); - s = hash_bucket_lock(fields); - tte_hash_set_field(newfield, - ((tte_hash_field_t)PCPU_GET(lookup_field))->tte.tag, - ((tte_hash_field_t)PCPU_GET(lookup_field))->tte.data); - - ((tte_hash_field_t)PCPU_GET(lookup_field))->of.flags = TH_COLLISION; - ((tte_hash_field_t)PCPU_GET(lookup_field))->of.next = newfield; - PCPU_SET(lookup_field, (u_long)&newfield[1]); + if ((otte_data == 0) && ((struct of_field *)PCPU_GET(lookup_field))->flags == MAGIC_VALUE) { + hash_bucket_unlock(entry->the_fields, s); + newentry = tte_hash_allocate_fragment_entry(th); + s = hash_bucket_lock(entry->the_fields); + ((struct of_field *)PCPU_GET(lookup_field))->next = newentry; + newentry->of.count = 1; + PCPU_SET(lookup_field, (u_long)&newentry[0]); } tte_hash_set_field((tte_hash_field_t)PCPU_GET(lookup_field), tte_tag, tte_data); - hash_bucket_unlock(fields, s); + hash_bucket_unlock(entry->the_fields, s); +#ifdef DEBUG + if (tte_hash_lookup(th, va) == 0) + panic("va=0x%lx not found", va); +#endif - if (otte_data == 0) + if (otte_data == 0) th->th_entries++; -#ifdef DEBUG - if (tte_hash_lookup(th, va) == 0) - panic("tte_hash_update failed"); -#endif return (otte_data); } +
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200605190756.k4J7uUNv074951>