[PATCH xserver 4/4] EXA: Replace hash table with glyph privates for glyph cache lookup.
Michel Dänzer
michel at daenzer.net
Wed May 18 08:15:36 PDT 2011
From: Michel Dänzer <daenzer at vmware.com>
Inspired by the corresponding intel driver change by Chris Wilson.
Also drop the special case for filling the cache initially, doesn't seem to
buy anything at this point.
v2: Always update eviction position after adding new glyph to cache.
Signed-off-by: Michel Dänzer <daenzer at vmware.com>
---
exa/exa.c | 3 +
exa/exa_glyphs.c | 219 +++++++++++++++++------------------------------------
exa/exa_priv.h | 20 ++---
3 files changed, 80 insertions(+), 162 deletions(-)
diff --git a/exa/exa.c b/exa/exa.c
index a4e294a..b6df33c 100644
--- a/exa/exa.c
+++ b/exa/exa.c
@@ -799,6 +799,8 @@ exaCloseScreen(int i, ScreenPtr pScreen)
unwrap(pExaScr, ps, Composite);
if (pExaScr->SavedGlyphs)
unwrap(pExaScr, ps, Glyphs);
+ if (pExaScr->SavedUnrealizeGlyph)
+ unwrap(pExaScr, ps, UnrealizeGlyph);
unwrap(pExaScr, ps, Trapezoids);
unwrap(pExaScr, ps, Triangles);
unwrap(pExaScr, ps, AddTraps);
@@ -960,6 +962,7 @@ exaDriverInit (ScreenPtr pScreen,
wrap(pExaScr, ps, Composite, exaComposite);
if (pScreenInfo->PrepareComposite) {
wrap(pExaScr, ps, Glyphs, exaGlyphs);
+ wrap(pExaScr, ps, UnrealizeGlyph, exaUnrealizeGlyph);
} else {
wrap(pExaScr, ps, Glyphs, ExaCheckGlyphs);
}
diff --git a/exa/exa_glyphs.c b/exa/exa_glyphs.c
index a6b8165..40dd82e 100644
--- a/exa/exa_glyphs.c
+++ b/exa/exa_glyphs.c
@@ -56,6 +56,13 @@
#define DBG_GLYPH_CACHE(a)
#endif
+struct exaGlyph {
+ ExaGlyphCachePtr cache;
+ int pos;
+};
+
+static DevPrivateKeyRec exaGlyphKey;
+
/* Width of the pixmaps we use for the caches; this should be less than
* max texture size of the driver; this may need to actually come from
* the driver.
@@ -63,7 +70,6 @@
#define CACHE_COLUMNS (1024 / 32)
#define CACHE_SIZE 256
-#define HASH_SIZE 557
/* Maximum number of glyphs we buffer on the stack before flushing
* rendering to the mask or destination surface.
@@ -88,6 +94,9 @@ exaGlyphsInit(ScreenPtr pScreen)
ExaScreenPriv(pScreen);
int i = 0;
+ if (!dixRegisterPrivateKey(&exaGlyphKey, PRIVATE_GLYPH, 0))
+ FatalError("Failed to register EXA glyph private key");
+
memset(pExaScr->glyphCaches, 0, sizeof(pExaScr->glyphCaches));
pExaScr->glyphCaches[i].format = PICT_a8;
@@ -124,12 +133,8 @@ exaUnrealizeGlyphCaches(ScreenPtr pScreen,
cache->picture = NULL;
}
- free(cache->hashEntries);
- cache->hashEntries = NULL;
-
- free(cache->glyphs);
- cache->glyphs = NULL;
- cache->glyphCount = 0;
+ free(cache->ppGlyph);
+ cache->ppGlyph = NULL;
}
}
@@ -199,23 +204,17 @@ exaRealizeGlyphCaches(ScreenPtr pScreen,
/* And store the picture in all the caches for the format */
for (i = 0; i < EXA_NUM_GLYPH_CACHES; i++) {
ExaGlyphCachePtr cache = &pExaScr->glyphCaches[i];
- int j;
if (cache->format != format)
continue;
cache->picture = pPicture;
cache->picture->refcnt++;
- cache->hashEntries = malloc(sizeof(int) * HASH_SIZE);
- cache->glyphs = malloc(sizeof(ExaCachedGlyphRec) * CACHE_SIZE);
- cache->glyphCount = 0;
+ cache->ppGlyph = calloc(CACHE_SIZE, sizeof(struct exaGlyph*));
- if (!cache->hashEntries || !cache->glyphs)
+ if (!cache->ppGlyph)
goto bail;
- for (j = 0; j < HASH_SIZE; j++)
- cache->hashEntries[j] = -1;
-
cache->evictionPosition = rand() & (CACHE_SIZE - 1);
}
@@ -229,6 +228,23 @@ bail:
}
void
+exaUnrealizeGlyph(ScreenPtr screen, GlyphPtr pGlyph)
+{
+ struct exaGlyph *priv;
+
+ /* Use Lookup in case we have not attached to this glyph. */
+ priv = dixLookupPrivate(&pGlyph->devPrivates, &exaGlyphKey);
+ if (priv == NULL)
+ return;
+
+ if (priv->cache)
+ priv->cache->ppGlyph[priv->pos] = NULL;
+
+ dixSetPrivate(&pGlyph->devPrivates, &exaGlyphKey, NULL);
+ free(priv);
+}
+
+void
exaGlyphsFini (ScreenPtr pScreen)
{
ExaScreenPriv(pScreen);
@@ -242,104 +258,6 @@ exaGlyphsFini (ScreenPtr pScreen)
}
}
-static int
-exaGlyphCacheHashLookup(ExaGlyphCachePtr cache,
- GlyphPtr pGlyph)
-{
- int slot;
-
- slot = (*(CARD32 *) pGlyph->sha1) % HASH_SIZE;
-
- while (TRUE) { /* hash table can never be full */
- int entryPos = cache->hashEntries[slot];
- if (entryPos == -1)
- return -1;
-
- if (memcmp(pGlyph->sha1, cache->glyphs[entryPos].sha1, sizeof(pGlyph->sha1)) == 0){
- return entryPos;
- }
-
- slot--;
- if (slot < 0)
- slot = HASH_SIZE - 1;
- }
-}
-
-static void
-exaGlyphCacheHashInsert(ExaGlyphCachePtr cache,
- GlyphPtr pGlyph,
- int pos)
-{
- int slot;
-
- memcpy(cache->glyphs[pos].sha1, pGlyph->sha1, sizeof(pGlyph->sha1));
-
- slot = (*(CARD32 *) pGlyph->sha1) % HASH_SIZE;
-
- while (TRUE) { /* hash table can never be full */
- if (cache->hashEntries[slot] == -1) {
- cache->hashEntries[slot] = pos;
- return;
- }
-
- slot--;
- if (slot < 0)
- slot = HASH_SIZE - 1;
- }
-}
-
-static void
-exaGlyphCacheHashRemove(ExaGlyphCachePtr cache,
- int pos)
-{
- int slot;
- int emptiedSlot = -1;
-
- slot = (*(CARD32 *) cache->glyphs[pos].sha1) % HASH_SIZE;
-
- while (TRUE) { /* hash table can never be full */
- int entryPos = cache->hashEntries[slot];
-
- if (entryPos == -1)
- return;
-
- if (entryPos == pos) {
- cache->hashEntries[slot] = -1;
- emptiedSlot = slot;
- } else if (emptiedSlot != -1) {
- /* See if we can move this entry into the emptied slot, we can't
- * do that if if entry would have hashed between the current position
- * and the emptied slot. (taking wrapping into account). Bad positions
- * are:
- *
- * | XXXXXXXXXX |
- * i j
- *
- * |XXX XXXX|
- * j i
- *
- * i - slot, j - emptiedSlot
- *
- * (Knuth 6.4R)
- */
-
- int entrySlot = (*(CARD32 *) cache->glyphs[entryPos].sha1) % HASH_SIZE;
-
- if (!((entrySlot >= slot && entrySlot < emptiedSlot) ||
- (emptiedSlot < slot && (entrySlot < emptiedSlot || entrySlot >= slot))))
- {
- cache->hashEntries[emptiedSlot] = entryPos;
- cache->hashEntries[slot] = -1;
- emptiedSlot = slot;
- }
- }
-
- slot--;
- if (slot < 0)
- slot = HASH_SIZE - 1;
- }
-}
-
#define CACHE_X(pos) (((pos) & (CACHE_COLUMNS - 1)) * cache->glyphWidth)
#define CACHE_Y(pos) (cache->yOffset + ((pos) / CACHE_COLUMNS) * cache->glyphHeight)
@@ -432,68 +350,71 @@ exaGlyphCacheBufferGlyph(ScreenPtr pScreen,
PicturePtr pSrc,
ExaCompositeRectPtr pRect)
{
+ struct exaGlyph *priv;
int pos;
int x, y;
if (buffer->mask && buffer->mask != cache->picture)
return ExaGlyphNeedFlush;
- if (!cache->picture) {
- if (!exaRealizeGlyphCaches(pScreen, cache->format))
- return ExaGlyphFail;
- }
+ if (!cache->picture && !exaRealizeGlyphCaches(pScreen, cache->format))
+ return ExaGlyphFail;
DBG_GLYPH_CACHE(("(%d,%d,%s): buffering glyph %lx\n",
cache->glyphWidth, cache->glyphHeight, cache->format == PICT_a8 ? "A" : "ARGB",
(long)*(CARD32 *) pGlyph->sha1));
-
- pos = exaGlyphCacheHashLookup(cache, pGlyph);
- if (pos != -1) {
+
+ priv = dixGetPrivate(&pGlyph->devPrivates, &exaGlyphKey);
+ if (!priv) {
+ priv = malloc(sizeof(*priv));
+ if (!priv)
+ return ExaGlyphFail;
+
+ priv->cache = NULL;
+ priv->pos = -1;
+ dixSetPrivate(&pGlyph->devPrivates, &exaGlyphKey, priv);
+ }
+
+ if (priv->cache == cache) {
+ pos = priv->pos;
DBG_GLYPH_CACHE((" found existing glyph at %d\n", pos));
x = CACHE_X(pos);
y = CACHE_Y(pos);
} else {
- if (cache->glyphCount < CACHE_SIZE) {
- /* Space remaining; we fill from the start */
- pos = cache->glyphCount;
- x = CACHE_X(pos);
- y = CACHE_Y(pos);
- cache->glyphCount++;
- DBG_GLYPH_CACHE((" storing glyph in free space at %d\n", pos));
+ pos = cache->evictionPosition;
+ x = CACHE_X(pos);
+ y = CACHE_Y(pos);
- exaGlyphCacheHashInsert(cache, pGlyph, pos);
+ if (cache->ppGlyph[pos]) {
+ int i;
- } else {
/* Need to evict an entry. We have to see if any glyphs
* already in the output buffer were at this position in
* the cache
*/
- pos = cache->evictionPosition;
- x = CACHE_X(pos);
- y = CACHE_Y(pos);
- DBG_GLYPH_CACHE((" evicting glyph at %d\n", pos));
- if (buffer->count) {
- int i;
-
- for (i = 0; i < buffer->count; i++) {
- if (pSrc ?
- (buffer->rects[i].xMask == x && buffer->rects[i].yMask == y) :
- (buffer->rects[i].xSrc == x && buffer->rects[i].ySrc == y)) {
- DBG_GLYPH_CACHE((" must flush buffer\n"));
- return ExaGlyphNeedFlush;
- }
+ for (i = 0; i < buffer->count; i++) {
+ if (pSrc ?
+ (buffer->rects[i].xMask == x && buffer->rects[i].yMask == y) :
+ (buffer->rects[i].xSrc == x && buffer->rects[i].ySrc == y)) {
+ DBG_GLYPH_CACHE((" must flush buffer\n"));
+ return ExaGlyphNeedFlush;
}
}
- /* OK, we're all set, swap in the new glyph */
- exaGlyphCacheHashRemove(cache, pos);
- exaGlyphCacheHashInsert(cache, pGlyph, pos);
-
- /* And pick a new eviction position */
- cache->evictionPosition = rand() & (CACHE_SIZE - 1);
+ DBG_GLYPH_CACHE((" evicting glyph at %d\n", pos));
+ cache->ppGlyph[pos]->cache = NULL;
+ cache->ppGlyph[pos]->pos = -1;
}
+ /* Add new glyph */
+ priv->cache = cache;
+ priv->pos = pos;
+ cache->ppGlyph[pos] = priv;
+
exaGlyphCacheUploadGlyph(pScreen, cache, x, y, pGlyph);
+
+ /* And pick a new eviction position */
+ cache->evictionPosition = rand() & (CACHE_SIZE - 1);
}
buffer->mask = cache->picture;
diff --git a/exa/exa_priv.h b/exa/exa_priv.h
index 98d3807..b75b241 100644
--- a/exa/exa_priv.h
+++ b/exa/exa_priv.h
@@ -105,9 +105,7 @@ enum ExaMigrationHeuristic {
ExaMigrationSmart
};
-typedef struct {
- unsigned char sha1[20];
-} ExaCachedGlyphRec, *ExaCachedGlyphPtr;
+struct exaGlyph;
typedef struct {
/* The identity of the cache, statically configured at initialization */
@@ -115,16 +113,7 @@ typedef struct {
int glyphWidth;
int glyphHeight;
- /* Hash table mapping from glyph sha1 to position in the glyph; we use
- * open addressing with a hash table size determined based on size and large
- * enough so that we always have a good amount of free space, so we can
- * use linear probing. (Linear probing is preferrable to double hashing
- * here because it allows us to easily remove entries.)
- */
- int *hashEntries;
-
- ExaCachedGlyphPtr glyphs;
- int glyphCount; /* Current number of glyphs */
+ struct exaGlyph **ppGlyph;
PicturePtr picture; /* Where the glyphs of the cache are stored */
int yOffset; /* y location within the picture where the cache starts */
@@ -164,6 +153,7 @@ typedef struct {
CompositeProcPtr SavedComposite;
TrianglesProcPtr SavedTriangles;
GlyphsProcPtr SavedGlyphs;
+ UnrealizeGlyphProcPtr SavedUnrealizeGlyph;
TrapezoidsProcPtr SavedTrapezoids;
AddTrapsProcPtr SavedAddTraps;
void (*do_migration) (ExaMigrationPtr pixmaps, int npixmaps, Bool can_accel);
@@ -695,6 +685,10 @@ exaGlyphs (CARD8 op,
GlyphListPtr list,
GlyphPtr *glyphs);
+void
+exaUnrealizeGlyph(ScreenPtr pScreen,
+ GlyphPtr pGlyph);
+
/* exa_migration_classic.c */
void
exaCopyDirtyToSys (ExaMigrationPtr migrate);
--
1.7.5.1
More information about the xorg-devel
mailing list