PERFORCE change 97450 for review
Kip Macy
kmacy at FreeBSD.org
Fri May 19 07:57:06 UTC 2006
http://perforce.freebsd.org/chv.cgi?CH=97450
Change 97450 by kmacy at 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);
}
+
More information about the p4-projects
mailing list