uxa: Use a glyph private rather than a hash table.

Store the cache position directly on the glyph using a devPrivate rather
than an through auxiliary hash table.

x11perf on PineView:
650/638 kglyphs/s -> 701/686 kglyphs/s [aa/rgb]

Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk>
(cherry picked from commit 11581dda99cb2e4ae78fc73be4b02185b3be58ed)

Signed-off-by: Owain G. Ainsworth <oga@openbsd.org>

3 files changed, 141 insertions, 196 deletions

diff --git a/uxa/uxa-glyphs.c b/uxa/uxa-glyphs.c
index 93a738ed..b0fdd5f7 100644
--- a/uxa/uxa-glyphs.c
+++ b/uxa/uxa-glyphs.c
@@ -80,11 +80,30 @@ typedef enum {
 	UXA_GLYPH_NEED_FLUSH,	/* would evict a glyph already in the buffer */
 } uxa_glyph_cache_result_t;
 
+struct uxa_glyph {
+	uxa_glyph_cache_t *cache;
+	int pos;
+};
+
+static int uxa_glyph_index;
+
+static inline struct uxa_glyph *uxa_glyph_get_private(GlyphPtr glyph)
+{
+	return dixLookupPrivate(&glyph->devPrivates, &uxa_glyph_index);
+}
+
+static inline void uxa_glyph_set_private(GlyphPtr glyph, struct uxa_glyph *priv)
+{
+	dixSetPrivate(&glyph->devPrivates, &uxa_glyph_index, priv);
+}
+
 void uxa_glyphs_init(ScreenPtr pScreen)
 {
 	uxa_screen_t *uxa_screen = uxa_get_screen(pScreen);
 	int i = 0;
 
+	dixRequestPrivate(&uxa_glyph_index, 0); /* XXX ignores status */
+
 	memset(uxa_screen->glyphCaches, 0, sizeof(uxa_screen->glyphCaches));
 
 	uxa_screen->glyphCaches[i].format = PICT_a8;
@@ -110,7 +129,6 @@ void uxa_glyphs_init(ScreenPtr pScreen)
 		uxa_screen->glyphCaches[i].columns =
 		    CACHE_PICTURE_WIDTH / uxa_screen->glyphCaches[i].glyphWidth;
 		uxa_screen->glyphCaches[i].size = 256;
-		uxa_screen->glyphCaches[i].hashSize = 557;
 	}
 }
 
@@ -130,11 +148,6 @@ static void uxa_unrealize_glyph_caches(ScreenPtr pScreen, unsigned int format)
 			cache->picture = NULL;
 		}
 
-		if (cache->hashEntries) {
-			xfree(cache->hashEntries);
-			cache->hashEntries = NULL;
-		}
-
 		if (cache->glyphs) {
 			xfree(cache->glyphs);
 			cache->glyphs = NULL;
@@ -211,24 +224,19 @@ static Bool uxa_realize_glyph_caches(ScreenPtr pScreen, unsigned int format)
 
 	for (i = 0; i < UXA_NUM_GLYPH_CACHES; i++) {
 		uxa_glyph_cache_t *cache = &uxa_screen->glyphCaches[i];
-		int j;
 
 		if (cache->format != format)
 			continue;
 
 		cache->picture = pPicture;
 		cache->picture->refcnt++;
-		cache->hashEntries = xalloc(sizeof(int) * cache->hashSize);
 		cache->glyphs =
-		    xalloc(sizeof(uxa_cached_glyph_t) * cache->size);
+		    xcalloc(sizeof(GlyphPtr), cache->size);
 		cache->glyphCount = 0;
 
-		if (!cache->hashEntries || !cache->glyphs)
+		if (!cache->glyphs)
 			goto bail;
 
-		for (j = 0; j < cache->hashSize; j++)
-			cache->hashEntries[j] = -1;
-
 		cache->evictionPosition = rand() % cache->size;
 	}
 
@@ -254,105 +262,6 @@ void uxa_glyphs_fini(ScreenPtr pScreen)
 	}
 }
 
-static int
-uxa_glyph_cache_hash_lookup(uxa_glyph_cache_t * cache, GlyphPtr pGlyph)
-{
-	int slot;
-
-	slot = (*(CARD32 *) pGlyph->sha1) % cache->hashSize;
-
-	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 = cache->hashSize - 1;
-	}
-}
-
-static void
-uxa_glyph_cache_hash_insert(uxa_glyph_cache_t * cache, GlyphPtr pGlyph, int pos)
-{
-	int slot;
-
-	memcpy(cache->glyphs[pos].sha1, pGlyph->sha1, sizeof(pGlyph->sha1));
-
-	slot = (*(CARD32 *) pGlyph->sha1) % cache->hashSize;
-
-	while (TRUE) {		/* hash table can never be full */
-		if (cache->hashEntries[slot] == -1) {
-			cache->hashEntries[slot] = pos;
-			return;
-		}
-
-		slot--;
-		if (slot < 0)
-			slot = cache->hashSize - 1;
-	}
-}
-
-static void uxa_glyph_cache_hash_remove(uxa_glyph_cache_t * cache, int pos)
-{
-	int slot;
-	int emptiedSlot = -1;
-
-	slot = (*(CARD32 *) cache->glyphs[pos].sha1) % cache->hashSize;
-
-	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) %
-			    cache->hashSize;
-
-			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 = cache->hashSize - 1;
-	}
-}
-
 #define CACHE_X(pos) (((pos) % cache->columns) * cache->glyphWidth)
 #define CACHE_Y(pos) (cache->yOffset + ((pos) / cache->columns) * cache->glyphHeight)
 
@@ -409,6 +318,22 @@ uxa_glyph_cache_upload_glyph(ScreenPtr pScreen,
 	return TRUE;
 }
 
+void
+uxa_glyph_unrealize(ScreenPtr pScreen,
+		    GlyphPtr pGlyph)
+{
+	struct uxa_glyph *priv;
+
+	priv = uxa_glyph_get_private(pGlyph);
+	if (priv == NULL)
+		return;
+
+	priv->cache->glyphs[priv->pos] = NULL;
+
+	uxa_glyph_set_private(pGlyph, NULL);
+	xfree(priv);
+}
+
 static uxa_glyph_cache_result_t
 uxa_glyph_cache_buffer_glyph(ScreenPtr pScreen,
 			     uxa_glyph_cache_t * cache,
@@ -416,6 +341,7 @@ uxa_glyph_cache_buffer_glyph(ScreenPtr pScreen,
 			     GlyphPtr pGlyph, int xGlyph, int yGlyph)
 {
 	uxa_composite_rect_t *rect;
+	struct uxa_glyph *priv = NULL;
 	int pos;
 
 	if (buffer->source && buffer->source != cache->picture)
@@ -431,87 +357,88 @@ uxa_glyph_cache_buffer_glyph(ScreenPtr pScreen,
 			 cache->format == PICT_a8 ? "A" : "ARGB",
 			 (long)*(CARD32 *) pGlyph->sha1));
 
-	pos = uxa_glyph_cache_hash_lookup(cache, pGlyph);
-	if (pos != -1) {
-		DBG_GLYPH_CACHE(("  found existing glyph at %d\n", pos));
+	if (cache->glyphCount < cache->size) {
+		/* Space remaining; we fill from the start */
+		pos = cache->glyphCount++;
+		DBG_GLYPH_CACHE(("  storing glyph in free space at %d\n", pos));
 	} else {
-		if (cache->glyphCount < cache->size) {
-			/* Space remaining; we fill from the start */
-			pos = cache->glyphCount;
-			cache->glyphCount++;
-			DBG_GLYPH_CACHE(("  storing glyph in free space at %d\n", pos));
+		GlyphPtr evicted;
+
+		/* Need to evict an entry. We have to see if any glyphs
+		 * already in the output buffer were at this position in
+		 * the cache
+		 */
 
-			uxa_glyph_cache_hash_insert(cache, pGlyph, pos);
+		pos = cache->evictionPosition;
+		DBG_GLYPH_CACHE(("  evicting glyph at %d\n", pos));
+		if (buffer->count) {
+			int x, y;
+			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;
-			DBG_GLYPH_CACHE(("  evicting glyph at %d\n", pos));
-			if (buffer->count) {
-				int x, y;
-				int i;
-
-				x = CACHE_X(pos);
-				y = CACHE_Y(pos);
-
-				for (i = 0; i < buffer->count; i++) {
-					if (buffer->rects[i].xSrc == x
-					    && buffer->rects[i].ySrc == y) {
-						DBG_GLYPH_CACHE(("  must flush buffer\n"));
-						return UXA_GLYPH_NEED_FLUSH;
-					}
+			x = CACHE_X(pos);
+			y = CACHE_Y(pos);
+
+			for (i = 0; i < buffer->count; i++) {
+				if (buffer->rects[i].xSrc == x
+				    && buffer->rects[i].ySrc == y) {
+					DBG_GLYPH_CACHE(("  must flush buffer\n"));
+					return UXA_GLYPH_NEED_FLUSH;
 				}
 			}
-
-			/* OK, we're all set, swap in the new glyph */
-			uxa_glyph_cache_hash_remove(cache, pos);
-			uxa_glyph_cache_hash_insert(cache, pGlyph, pos);
-
-			/* And pick a new eviction position */
-			cache->evictionPosition = rand() % cache->size;
 		}
 
-		/* Now actually upload the glyph into the cache picture; if
-		 * we can't do it with UploadToScreen (because the glyph is
-		 * offscreen, etc), we fall back to CompositePicture.
-		 */
-		if (!uxa_glyph_cache_upload_glyph(pScreen, cache, pos, pGlyph)) {
-			CompositePicture(PictOpSrc,
-					 GlyphPicture(pGlyph)[pScreen->myNum],
-					 None,
-					 cache->picture,
-					 0, 0,
-					 0, 0,
-					 CACHE_X(pos),
-					 CACHE_Y(pos),
-					 pGlyph->info.width,
-					 pGlyph->info.height);
+		evicted = cache->glyphs[pos];
+		if (evicted != NULL) {
+			priv = uxa_glyph_get_private(evicted);
+			uxa_glyph_set_private(evicted, NULL);
 		}
 
+		/* And pick a new eviction position */
+		cache->evictionPosition = rand() % cache->size;
 	}
 
+	/* Now actually upload the glyph into the cache picture; if
+	 * we can't do it with UploadToScreen (because the glyph is
+	 * offscreen, etc), we fall back to CompositePicture.
+	 */
+	if (!uxa_glyph_cache_upload_glyph(pScreen, cache, pos, pGlyph)) {
+		CompositePicture(PictOpSrc,
+				 GlyphPicture(pGlyph)[pScreen->myNum],
+				 None,
+				 cache->picture,
+				 0, 0,
+				 0, 0,
+				 CACHE_X(pos),
+				 CACHE_Y(pos),
+				 pGlyph->info.width,
+				 pGlyph->info.height);
+	}
+
+	if (priv == NULL) {
+		priv = xalloc(sizeof(struct uxa_glyph));
+		if (priv == NULL) {
+			cache->glyphs[pos] = NULL;
+			return UXA_GLYPH_FAIL;
+		}
+	}
+
+	priv->cache = cache;
+	priv->pos = pos;
+	uxa_glyph_set_private(pGlyph, priv);
+	cache->glyphs[pos] = pGlyph;
+
 	buffer->source = cache->picture;
 
-	rect = &buffer->rects[buffer->count];
+	rect = &buffer->rects[buffer->count++];
 	rect->xSrc = CACHE_X(pos);
 	rect->ySrc = CACHE_Y(pos);
 	rect->xDst = xGlyph - pGlyph->info.x;
 	rect->yDst = yGlyph - pGlyph->info.y;
 	rect->width = pGlyph->info.width;
 	rect->height = pGlyph->info.height;
-
-	buffer->count++;
-
 	return UXA_GLYPH_SUCCESS;
 }
 
-#undef CACHE_X
-#undef CACHE_Y
-
 static uxa_glyph_cache_result_t
 uxa_buffer_glyph(ScreenPtr pScreen,
 		 uxa_glyph_buffer_t * buffer,
@@ -522,12 +449,33 @@ uxa_buffer_glyph(ScreenPtr pScreen,
 	int width = pGlyph->info.width;
 	int height = pGlyph->info.height;
 	uxa_composite_rect_t *rect;
+	struct uxa_glyph *priv;
 	PicturePtr source;
 	int i;
 
 	if (buffer->count == GLYPH_BUFFER_SIZE)
 		return UXA_GLYPH_NEED_FLUSH;
 
+	priv = uxa_glyph_get_private(pGlyph);
+	if (priv != NULL) {
+		uxa_glyph_cache_t *cache = priv->cache;
+		int pos = priv->pos;
+
+		if (buffer->source && buffer->source != cache->picture)
+			return UXA_GLYPH_NEED_FLUSH;
+
+		buffer->source = cache->picture;
+
+		rect = &buffer->rects[buffer->count++];
+		rect->xSrc = CACHE_X(pos);
+		rect->ySrc = CACHE_Y(pos);
+		rect->xDst = xGlyph - pGlyph->info.x;
+		rect->yDst = yGlyph - pGlyph->info.y;
+		rect->width = pGlyph->info.width;
+		rect->height = pGlyph->info.height;
+		return UXA_GLYPH_SUCCESS;
+	}
+
 	if (PICT_FORMAT_BPP(format) == 1)
 		format = PICT_a8;
 
@@ -535,15 +483,15 @@ uxa_buffer_glyph(ScreenPtr pScreen,
 		uxa_glyph_cache_t *cache = &uxa_screen->glyphCaches[i];
 
 		if (format == cache->format &&
-		    width <= cache->glyphWidth &&
+		    width  <= cache->glyphWidth &&
 		    height <= cache->glyphHeight) {
 			uxa_glyph_cache_result_t result =
-			    uxa_glyph_cache_buffer_glyph(pScreen,
-							 &uxa_screen->
-							 glyphCaches[i],
-							 buffer,
-							 pGlyph, xGlyph,
-							 yGlyph);
+				uxa_glyph_cache_buffer_glyph(pScreen,
+							     &uxa_screen->
+							     glyphCaches[i],
+							     buffer,
+							     pGlyph, xGlyph,
+							     yGlyph);
 			switch (result) {
 			case UXA_GLYPH_FAIL:
 				break;
@@ -562,19 +510,19 @@ uxa_buffer_glyph(ScreenPtr pScreen,
 
 	buffer->source = source;
 
-	rect = &buffer->rects[buffer->count];
+	rect = &buffer->rects[buffer->count++];
 	rect->xSrc = 0;
 	rect->ySrc = 0;
 	rect->xDst = xGlyph - pGlyph->info.x;
 	rect->yDst = yGlyph - pGlyph->info.y;
 	rect->width = pGlyph->info.width;
 	rect->height = pGlyph->info.height;
-
-	buffer->count++;
-
 	return UXA_GLYPH_SUCCESS;
 }
 
+#undef CACHE_X
+#undef CACHE_Y
+
 static PicturePtr
 uxa_glyphs_acquire_source(ScreenPtr screen,
 			  PicturePtr src,
diff --git a/uxa/uxa-priv.h b/uxa/uxa-priv.h
index bace6798..a183db9b 100644
--- a/uxa/uxa-priv.h
+++ b/uxa/uxa-priv.h
@@ -103,10 +103,6 @@ char uxa_drawable_location(DrawablePtr pDrawable);
 #endif
 
 typedef struct {
-	unsigned char sha1[20];
-} uxa_cached_glyph_t;
-
-typedef struct {
 	/* The identity of the cache, statically configured at initialization */
 	unsigned int format;
 	int glyphWidth;
@@ -115,16 +111,7 @@ typedef struct {
 	/* Size of cache; eventually this should be dynamically determined */
 	int size;
 
-	/* 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;
-	int hashSize;
-
-	uxa_cached_glyph_t *glyphs;
+	GlyphPtr *glyphs;
 	int glyphCount;		/* Current number of glyphs */
 
 	PicturePtr picture;	/* Where the glyphs of the cache are stored */
@@ -161,6 +148,7 @@ typedef struct {
 	GlyphsProcPtr SavedGlyphs;
 	TrapezoidsProcPtr SavedTrapezoids;
 	AddTrapsProcPtr SavedAddTraps;
+	UnrealizeGlyphProcPtr SavedUnrealizeGlyph;
 #endif
 	EnableDisableFBAccessProcPtr SavedEnableDisableFBAccess;
 
@@ -472,4 +460,8 @@ uxa_glyphs(CARD8 op,
 	   INT16 xSrc,
 	   INT16 ySrc, int nlist, GlyphListPtr list, GlyphPtr * glyphs);
 
+void
+uxa_glyph_unrealize(ScreenPtr pScreen,
+		    GlyphPtr pGlyph);
+
 #endif /* UXAPRIV_H */
diff --git a/uxa/uxa.c b/uxa/uxa.c
index 9ea14662..ce03fa07 100644
--- a/uxa/uxa.c
+++ b/uxa/uxa.c
@@ -393,6 +393,8 @@ static Bool uxa_close_screen(int i, ScreenPtr pScreen)
 		ps->Trapezoids = uxa_screen->SavedTrapezoids;
 		ps->AddTraps = uxa_screen->SavedAddTraps;
 		ps->Triangles = uxa_screen->SavedTriangles;
+
+		ps->UnrealizeGlyph = uxa_screen->SavedUnrealizeGlyph;
 	}
 #endif
 
@@ -524,6 +526,9 @@ Bool uxa_driver_init(ScreenPtr screen, uxa_driver_t * uxa_driver)
 		uxa_screen->SavedGlyphs = ps->Glyphs;
 		ps->Glyphs = uxa_glyphs;
 
+		uxa_screen->SavedUnrealizeGlyph = ps->UnrealizeGlyph;
+		ps->UnrealizeGlyph = uxa_glyph_unrealize;
+
 		uxa_screen->SavedTriangles = ps->Triangles;
 		ps->Triangles = uxa_triangles;