From 9e612141df7e693ef98071f102cecb5d777ceecb Mon Sep 17 00:00:00 2001 From: Keith Packard Date: Mon, 4 Sep 2006 22:20:25 -0700 Subject: [PATCH] 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. --- src/fccache.c | 255 ++++++++++++++++++++++++++++++++++++------------ src/fccfg.c | 22 +---- src/fccharset.c | 5 + src/fcint.h | 16 ++- src/fcpat.c | 10 +- 5 files changed, 213 insertions(+), 95 deletions(-) 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 #include #include +#include #if defined(HAVE_MMAP) || defined(__CYGWIN__) # include # include @@ -182,6 +183,175 @@ FcDirCacheProcess (FcConfig *config, const FcChar8 *dir, 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) -{ - return ((uint32_t) cache_stat->st_dev ^ - (uint32_t) cache_stat->st_ino ^ - (uint32_t) cache_stat->st_mtime); -} - -static FcCache * -FcCacheLookup (struct stat *cache_stat) +void +FcCacheObjectReference (void *object) { - uint32_t hash = FcCacheStatHash(cache_stat); - FcCacheBucket **bucket = &FcCacheBuckets[hash % FC_CACHE_HASH_SIZE]; - FcCacheBucket *b; + FcCacheSkip *skip = FcCacheFindByAddr (object); - 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_stat) 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_stat) 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_stat) 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,20 +229,10 @@ 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 */ @@ -280,6 +260,7 @@ FcConfigAddCache (FcConfig *config, FcCache *cache) 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 @@ -474,11 +469,6 @@ struct _FcConfig { * match preferrentially */ 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 @@ -514,6 +504,12 @@ FcDirCacheBuild (FcFontSet *set, const FcChar8 *dir, FcStrSet *dirs); FcPrivate FcBool FcDirCacheWrite (FcCache *cache, FcConfig *config); +FcPrivate void +FcCacheObjectReference (void *object); + +FcPrivate void +FcCacheObjectDereference (void *object); + FcPrivate void FcCacheFini (void); 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 * -- 2.39.5