Keith Packard
2006-Sep-04 22:35 UTC
[Fontconfig] fontconfig: Branch ''master'' - 2 commits
src/fccache.c | 264 ++++++++++++++++++++++++++++++++++++++++++--------------
src/fccfg.c | 25 +----
src/fccharset.c | 5 +
src/fcint.h | 19 +---
src/fcpat.c | 10 +-
5 files changed, 228 insertions(+), 95 deletions(-)
New commits:
diff-tree 17389539a046f7231447d531ef7f3d131c1d7515 (from
9e612141df7e693ef98071f102cecb5d777ceecb)
Author: Keith Packard <keithp@neko.keithp.com>
Date: Mon Sep 4 22:26:24 2006 -0700
Make cache reference counting more efficient.
Eliminate need to reference cache object once per cached font, instead
just count the number of fonts used from the cache and bump the reference
count once by that amount. I think this makes this refernece technique
efficient enough for use.
diff --git a/src/fccache.c b/src/fccache.c
index 69a29f2..77a303d 100644
--- a/src/fccache.c
+++ b/src/fccache.c
@@ -477,6 +477,15 @@ FcDirCacheMapFd (int fd, struct stat *fd
}
void
+FcDirCacheReference (FcCache *cache, int nref)
+{
+ FcCacheSkip *skip = FcCacheFindByAddr (cache);
+
+ if (skip)
+ skip->ref += nref;
+}
+
+void
FcDirCacheUnload (FcCache *cache)
{
FcCacheObjectDereference (cache);
diff --git a/src/fccfg.c b/src/fccfg.c
index 1139744..d9502f0 100644
--- a/src/fccfg.c
+++ b/src/fccfg.c
@@ -239,6 +239,8 @@ FcConfigAddCache (FcConfig *config, FcCa
fs = FcCacheSet (cache);
if (fs)
{
+ int nref = 0;
+
for (i = 0; i < fs->nfont; i++)
{
FcPattern *font = FcFontSetFont (fs, i);
@@ -260,9 +262,10 @@ FcConfigAddCache (FcConfig *config, FcCa
if (!FcConfigAcceptFont (config, font))
continue;
- FcPatternReference (font);
+ nref++;
FcFontSetAdd (config->fonts[FcSetSystem], font);
}
+ FcDirCacheReference (cache, nref);
}
/*
diff --git a/src/fcint.h b/src/fcint.h
index a054219..7dab169 100644
--- a/src/fcint.h
+++ b/src/fcint.h
@@ -513,6 +513,9 @@ FcCacheObjectDereference (void *object);
FcPrivate void
FcCacheFini (void);
+void
+FcDirCacheReference (FcCache *cache, int nref);
+
/* fccfg.c */
FcPrivate FcBool
diff-tree 9e612141df7e693ef98071f102cecb5d777ceecb (from
8fe2104a1e5771ac8079a438fa21e00f946be8b3)
Author: Keith Packard <keithp@neko.keithp.com>
Date: Mon Sep 4 22:20:25 2006 -0700
Reference count cache objects.
Caches contain patterns and character sets which are reference counted and
visible to applications. Reference count the underlying cache object so that
it stays around until all reference objects are no longer in use.
This is less efficient than just leaving all caches around forever, but does
avoid eternal size increases in case applications ever bother to actually
look for changes in the font configuration.
diff --git a/src/fccache.c b/src/fccache.c
index a3a758e..69a29f2 100644
--- a/src/fccache.c
+++ b/src/fccache.c
@@ -28,6 +28,7 @@
#include <dirent.h>
#include <string.h>
#include <sys/types.h>
+#include <assert.h>
#if defined(HAVE_MMAP) || defined(__CYGWIN__)
# include <unistd.h>
# include <sys/mman.h>
@@ -182,6 +183,175 @@ FcDirCacheProcess (FcConfig *config, con
return ret;
}
+#define FC_CACHE_MIN_MMAP 1024
+
+/*
+ * Skip list element, make sure the ''next'' pointer is the
last thing
+ * in the structure, it will be allocated large enough to hold all
+ * of the necessary pointers
+ */
+
+typedef struct _FcCacheSkip FcCacheSkip;
+
+struct _FcCacheSkip {
+ FcCache *cache;
+ int ref;
+ intptr_t size;
+ dev_t cache_dev;
+ ino_t cache_ino;
+ time_t cache_mtime;
+ FcCacheSkip *next[1];
+};
+
+/*
+ * The head of the skip list; pointers for every possible level
+ * in the skip list, plus the largest level in the list
+ */
+
+#define FC_CACHE_MAX_LEVEL 16
+
+static FcCacheSkip *fcCacheChains[FC_CACHE_MAX_LEVEL];
+static int fcCacheMaxLevel;
+
+/*
+ * Generate a random level number, distributed
+ * so that each level is 1/4 as likely as the one before
+ *
+ * Note that level numbers run 1 <= level <= MAX_LEVEL
+ */
+static int
+random_level (void)
+{
+ /* tricky bit -- each bit is ''1'' 75% of the time */
+ long int bits = random () | random ();
+ int level = 0;
+
+ while (++level < FC_CACHE_MAX_LEVEL)
+ {
+ if (bits & 1)
+ break;
+ bits >>= 1;
+ }
+ return level;
+}
+
+/*
+ * Insert cache into the list
+ */
+static FcBool
+FcCacheInsert (FcCache *cache, struct stat *cache_stat)
+{
+ FcCacheSkip **update[FC_CACHE_MAX_LEVEL];
+ FcCacheSkip *s, **next;
+ int i, level;
+
+ /*
+ * Find links along each chain
+ */
+ next = fcCacheChains;
+ for (i = fcCacheMaxLevel; --i >= 0; )
+ {
+ for (; (s = next[i]); next = s->next)
+ if (s->cache > cache)
+ break;
+ update[i] = &next[i];
+ }
+
+ /*
+ * Create new list element
+ */
+ level = random_level ();
+ if (level > fcCacheMaxLevel)
+ {
+ level = fcCacheMaxLevel + 1;
+ update[fcCacheMaxLevel] = &fcCacheChains[fcCacheMaxLevel];
+ fcCacheMaxLevel = level;
+ }
+
+ s = malloc (sizeof (FcCacheSkip) + (level - 1) * sizeof (FcCacheSkip *));
+ if (!s)
+ return FcFalse;
+
+ s->cache = cache;
+ s->size = cache->size;
+ s->ref = 1;
+ s->cache_dev = cache_stat->st_dev;
+ s->cache_ino = cache_stat->st_ino;
+ s->cache_mtime = cache_stat->st_mtime;
+
+ /*
+ * Insert into all fcCacheChains
+ */
+ for (i = 0; i < level; i++)
+ {
+ s->next[i] = *update[i];
+ *update[i] = s;
+ }
+ return FcTrue;
+}
+
+static FcCacheSkip *
+FcCacheFindByAddr (void *object)
+{
+ int i;
+ FcCacheSkip **next = fcCacheChains;
+ FcCacheSkip *s;
+
+ /*
+ * Walk chain pointers one level at a time
+ */
+ for (i = fcCacheMaxLevel; --i >= 0;)
+ while (next[i] && (char *) object >= ((char *) next[i]->cache +
next[i]->size))
+ next = next[i]->next;
+ /*
+ * Here we are
+ */
+ s = next[0];
+ if (s && (char *) object < ((char *) s->cache + s->size))
+ return s;
+ return NULL;
+}
+
+static void
+FcCacheRemove (FcCache *cache)
+{
+ FcCacheSkip **update[FC_CACHE_MAX_LEVEL];
+ FcCacheSkip *s, **next;
+ int i;
+
+ /*
+ * Find links along each chain
+ */
+ next = fcCacheChains;
+ for (i = fcCacheMaxLevel; --i >= 0; )
+ {
+ for (; (s = next[i]); next = s->next)
+ if (s->cache >= cache)
+ break;
+ update[i] = &next[i];
+ }
+ s = next[0];
+ assert (s->cache == cache);
+ for (i = 0; i < fcCacheMaxLevel && *update[i] == s; i++)
+ *update[i] = s->next[i];
+ while (fcCacheMaxLevel > 0 && fcCacheChains[fcCacheMaxLevel - 1]
== NULL)
+ fcCacheMaxLevel--;
+ free (s);
+}
+
+static FcCache *
+FcCacheFindByStat (struct stat *cache_stat)
+{
+ FcCacheSkip *s;
+
+ for (s = fcCacheChains[0]; s; s = s->next[0])
+ if (s->cache_dev == cache_stat->st_dev &&
+ s->cache_ino == cache_stat->st_ino &&
+ s->cache_mtime == cache_stat->st_mtime)
+ return s->cache;
+ return NULL;
+}
+
static void
FcDirCacheDispose (FcCache *cache)
{
@@ -197,82 +367,39 @@ FcDirCacheDispose (FcCache *cache)
#endif
break;
}
+ FcCacheRemove (cache);
}
-#define FC_CACHE_MIN_MMAP 1024
-
-#define FC_CACHE_HASH_SIZE 67
-
-typedef struct _FcCacheBucket FcCacheBucket;
-
-struct _FcCacheBucket {
- FcCacheBucket *next;
- FcCache *cache;
- dev_t cache_dev;
- ino_t cache_ino;
- time_t cache_mtime;
-};
-
-static FcCacheBucket *FcCacheBuckets[FC_CACHE_HASH_SIZE];
-
-static uint32_t
-FcCacheStatHash (struct stat *cache_stat)
+void
+FcCacheObjectReference (void *object)
{
- return ((uint32_t) cache_stat->st_dev ^
- (uint32_t) cache_stat->st_ino ^
- (uint32_t) cache_stat->st_mtime);
-}
+ FcCacheSkip *skip = FcCacheFindByAddr (object);
-static FcCache *
-FcCacheLookup (struct stat *cache_stat)
-{
- uint32_t hash = FcCacheStatHash(cache_stat);
- FcCacheBucket **bucket = &FcCacheBuckets[hash % FC_CACHE_HASH_SIZE];
- FcCacheBucket *b;
-
- for (b = *bucket; b; b = b->next)
- if (b->cache_dev == cache_stat->st_dev &&
- b->cache_ino == cache_stat->st_ino &&
- b->cache_mtime == cache_stat->st_mtime)
- return b->cache;
- return NULL;
+ if (skip)
+ skip->ref++;
}
-static FcBool
-FcCacheRecord (FcCache *cache, struct stat *cache_stat)
+void
+FcCacheObjectDereference (void *object)
{
- uint32_t hash = FcCacheStatHash(cache_stat);
- FcCacheBucket **bucket = &FcCacheBuckets[hash % FC_CACHE_HASH_SIZE];
- FcCacheBucket *b;
+ FcCacheSkip *skip = FcCacheFindByAddr (object);
- b = malloc (sizeof (FcCacheBucket));
- if (!b)
- return FcFalse;
- b->next = *bucket;
- b->cache = cache;
- b->cache_dev = cache_stat->st_dev;
- b->cache_ino = cache_stat->st_ino;
- b->cache_mtime = cache_stat->st_mtime;
- *bucket = b;
- return FcTrue;
+ if (skip)
+ {
+ skip->ref--;
+ if (skip->ref <= 0)
+ FcDirCacheDispose (skip->cache);
+ }
}
void
FcCacheFini (void)
{
int i;
- FcCacheBucket *b, *next;
- for (i = 0; i < FC_CACHE_HASH_SIZE; i++)
- {
- for (b = FcCacheBuckets[i]; b; b = next)
- {
- next = b->next;
- FcDirCacheDispose (b->cache);
- free (b);
- }
- FcCacheBuckets[i] = NULL;
- }
+ for (i = 0; i < FC_CACHE_MAX_LEVEL; i++)
+ assert (fcCacheChains[i] == NULL);
+ assert (fcCacheMaxLevel == 0);
}
/*
@@ -286,7 +413,7 @@ FcDirCacheMapFd (int fd, struct stat *fd
if (fd_stat->st_size < sizeof (FcCache))
return NULL;
- cache = FcCacheLookup (fd_stat);
+ cache = FcCacheFindByStat (fd_stat);
if (cache)
return cache;
/*
@@ -327,7 +454,7 @@ FcDirCacheMapFd (int fd, struct stat *fd
if (cache->magic != FC_CACHE_MAGIC_MMAP ||
cache->version < FC_CACHE_CONTENT_VERSION ||
cache->size != fd_stat->st_size ||
- !FcCacheRecord (cache, fd_stat))
+ !FcCacheInsert (cache, fd_stat))
{
if (allocated)
free (cache);
@@ -352,7 +479,7 @@ FcDirCacheMapFd (int fd, struct stat *fd
void
FcDirCacheUnload (FcCache *cache)
{
- /* Can''t free or unmap the cache as apps may point into it */
+ FcCacheObjectDereference (cache);
}
static FcBool
diff --git a/src/fccfg.c b/src/fccfg.c
index 2f0d311..1139744 100644
--- a/src/fccfg.c
+++ b/src/fccfg.c
@@ -90,8 +90,6 @@ FcConfigCreate (void)
for (set = FcSetSystem; set <= FcSetApplication; set++)
config->fonts[set] = 0;
- config->caches = NULL;
-
config->rescanTime = time(0);
config->rescanInterval = 30;
@@ -197,7 +195,6 @@ void
FcConfigDestroy (FcConfig *config)
{
FcSetName set;
- FcCacheList *cl, *cl_next;
if (config == _fcConfig)
_fcConfig = 0;
@@ -221,13 +218,6 @@ FcConfigDestroy (FcConfig *config)
if (config->fonts[set])
FcFontSetDestroy (config->fonts[set]);
- for (cl = config->caches; cl; cl = cl_next)
- {
- cl_next = cl->next;
- FcDirCacheUnload (cl->cache);
- free (cl);
- }
-
free (config);
FcMemFree (FC_MEM_CONFIG, sizeof (FcConfig));
}
@@ -239,21 +229,11 @@ FcConfigDestroy (FcConfig *config)
FcBool
FcConfigAddCache (FcConfig *config, FcCache *cache)
{
- FcCacheList *cl = malloc (sizeof (FcCacheList));
FcFontSet *fs;
intptr_t *dirs;
int i;
/*
- * Add to cache list
- */
- if (!cl)
- return FcFalse;
- cl->cache = cache;
- cl->next = config->caches;
- config->caches = cl;
-
- /*
* Add fonts
*/
fs = FcCacheSet (cache);
@@ -280,6 +260,7 @@ FcConfigAddCache (FcConfig *config, FcCa
if (!FcConfigAcceptFont (config, font))
continue;
+ FcPatternReference (font);
FcFontSetAdd (config->fonts[FcSetSystem], font);
}
}
@@ -338,6 +319,7 @@ FcConfigBuildFonts (FcConfig *config)
if (!cache)
continue;
FcConfigAddCache (config, cache);
+ FcDirCacheUnload (cache);
}
FcStrListDone (dirlist);
diff --git a/src/fccharset.c b/src/fccharset.c
index fdff91f..76c1530 100644
--- a/src/fccharset.c
+++ b/src/fccharset.c
@@ -55,7 +55,10 @@ FcCharSetDestroy (FcCharSet *fcs)
int i;
if (fcs->ref == FC_REF_CONSTANT)
+ {
+ FcCacheObjectDereference (fcs);
return;
+ }
if (--fcs->ref > 0)
return;
for (i = 0; i < fcs->num; i++)
@@ -306,6 +309,8 @@ FcCharSetCopy (FcCharSet *src)
{
if (src->ref != FC_REF_CONSTANT)
src->ref++;
+ else
+ FcCacheObjectReference (src);
return src;
}
diff --git a/src/fcint.h b/src/fcint.h
index 99ffe92..a054219 100644
--- a/src/fcint.h
+++ b/src/fcint.h
@@ -419,11 +419,6 @@ struct _FcBlanks {
FcChar32 *blanks;
};
-typedef struct _FcCacheList {
- struct _FcCacheList *next;
- FcCache *cache;
-} FcCacheList;
-
struct _FcConfig {
/*
* File names loaded from the configuration -- saved here as the
@@ -475,11 +470,6 @@ struct _FcConfig {
*/
FcFontSet *fonts[FcSetApplication + 1];
/*
- * Font cache information is mapped from cache files
- * the configuration is destroyed, the files need to be unmapped
- */
- FcCacheList *caches;
- /*
* Fontconfig can periodically rescan the system configuration
* and font directories. This rescanning occurs when font
* listing requests are made, but no more often than rescanInterval
@@ -515,6 +505,12 @@ FcPrivate FcBool
FcDirCacheWrite (FcCache *cache, FcConfig *config);
FcPrivate void
+FcCacheObjectReference (void *object);
+
+FcPrivate void
+FcCacheObjectDereference (void *object);
+
+FcPrivate void
FcCacheFini (void);
/* fccfg.c */
diff --git a/src/fcpat.c b/src/fcpat.c
index 9cd01a0..a225717 100644
--- a/src/fcpat.c
+++ b/src/fcpat.c
@@ -282,7 +282,13 @@ FcPatternDestroy (FcPattern *p)
int i;
FcPatternElt *elts;
- if (p->ref == FC_REF_CONSTANT || --p->ref > 0)
+ if (p->ref == FC_REF_CONSTANT)
+ {
+ FcCacheObjectDereference (p);
+ return;
+ }
+
+ if (--p->ref > 0)
return;
elts = FcPatternElts (p);
@@ -938,6 +944,8 @@ FcPatternReference (FcPattern *p)
{
if (p->ref != FC_REF_CONSTANT)
p->ref++;
+ else
+ FcCacheObjectReference (p);
}
FcPattern *