[Mesa-dev,v2] glsl: Add initial functions to implement an on-disk cache

Submitted by Carl Worth on Feb. 10, 2015, 1:33 a.m.

Details

Message ID 1423532011-29999-1-git-send-email-cworth@cworth.org
State New
Headers show

Not browsing as part of any series.

Commit Message

Carl Worth Feb. 10, 2015, 1:33 a.m.
This code provides for an on-disk cache of objects. Objects are stored
and retrieved via names that are arbitrary 20-byte sequences,
(intended to be SHA-1 hashes of something identifying for the
content). The directory used for the cache can be specified by means
of environment variables in the following priority order:

	$MESA_GLSL_CACHE_DIR
	$XDG_CACHE_HOME/mesa
	<user-home-directory>/.cache/mesa

By default the cache will be limited to a maximum size of 1GB. The
environment variable:

	$MESA_GLSL_CACHE_MAX_SIZE

can be set (at the time of GL context creation) to choose some other
size. This variable is a number that can optionally be followed by
'K', 'M', or 'G' to select a size in kilobytes, megabytes, or
gigabytes. By default, an unadorned value will be interpreted as
gigabytes.

The cache will be entirely disabled at runtime if the variable
MESA_GLSL_CACHE_DISABLE is set at the time of GL context creation.

This patch is intended to support a future implementation of a shader
cache. But for now, the only code using this cache is the unit tests
included here.

Many thanks to Kristian Høgsberg <krh@bitplanet.net> for the initial
implementation of code that led to this patch. In particular, the idea
of using an mmapped file, (indexed by a portion of the SHA-1), for the
efficent implementation of cache_has_key was entirely his
idea. Kristian also provided some very helpful advice in discussions
regarding various race conditions to be avoided in this code.
---

This is an update of the patch series I sent last week. Here is a
summary of the major changes:

  * All squashed into one commit, since rebasing changes through the
    series was getting too annyoing, (and there wasn't too much value
    in having things broken out).

  * The cache has now been split to have two separate notions:

	1. Storing objects named by a hash

	2. Storing a hash along with no other data

    These two notions are supported by the separate APIs of
    cache_put/cache_get and cache_put_key/cache_get_key. (The
    difference from before was that the equivalent of the new
    cache_get_key would also return true if that same key had
    previously been used for cache_put).

    Having these two notions separated means all the code that needs
    the efficiency of cache_has_key still gets it, but several
    difficult-to-fix race conditions that were discussed previously
    are no longer possible. (This was the discussion of a few
    lingering FIXME comments around index updates and unlink.)

  * The cache is now size-limited and controllable via the
    MESA_GLSL_CACHE_MAX_SIZE environment variable.

  * The patch now includes unit tests.

Here are the two major things I know that I could use in review of
this code:

  1. Portability

     For the size-limited cache, this code now calls readdir() which
     wasn't previously called in Mesa. I don't know if an MSVC
     environment provides the d_type field in the resulting struct
     dirent entries, or if the code will need some additional stat()
     calls.

     And there could, of course, be other portability problems I'm not
     aware of.

  2. Concurrency issues

     Kristian and I have discussed quite a number of potential
     race-related issues from multiple processed accessing the cache
     simultaneously. I'm not aware of cases we haven't thought
     through, but of course that's very weak as a guarantee of
     correctness.

     There are comments throughout the relevant parts of the code, but
     here is an overview to guide review:

     The two primary shared resources are the index file which is
     mmap()ped with MAP_SHARED and the filesystem itself where cached
     files are written and unlinked.

     The syncrhonization primitive used for the index file is atomic
     addition. This is used to protect the number that tracks the
     total size of the cache. The other writes to the index file are
     SHA-1 signatures. These are not protected from multiple
     writers. The thought there is that a corrupt signature from
     multiple writeres should be effectually identical to the default
     all-zeros---in either case no real SHA-1 signature for a GLSL
     source file is expected to match.

     For the filesystem, when the code as a cache miss on a file named
     <sha1> and goes off to compile and link it, it then comes back
     and opens <sha1>.tmp and attempts an flock with LOCK_EX. If this
     fails, it gives up, (trusting that the process with the active
     lock will write the identical contents that this process would
     have written). If the lock succeeds, it also next checks whether
     the file <sha1> now exists, (in case it was written by a racing
     process between the cache miss and now). Only if it does not
     exist at this point, does the process then perform the following
     operations:

	* Write contents to <sha1>.tmp
	* Rename from <sha1>.tmp to <sha1>
	* Perform the atomic addition to update the cache size

     And only then does it release its flock.

     One race that I see that remains is a process getting killed
     between the rename() and the atomic addition. That kind of thing
     could cause the calculated cache size to drift from the actual
     size of the cache by as much as a single linked program every
     time it happens. I don't know if that's important to worry about,
     (the expected drift seems small---and it's the kind of thing that
     can be fixed by just nukind ~/.cache/mesa). But it is at least
     one issue I can identify for which there's no solution in the
     current code, (nothing ever locks the entire system to sum up all
     file sizes to obtain an authoritative total cache size).

As always, any feedback will be most appreciated.

And soon I hope to follow up with some actual code to use this stuff
to cache some compiled shaders.

-Carl

 configure.ac                |   3 +
 docs/envvars.html           |  11 +
 src/glsl/Makefile.am        |  11 +
 src/glsl/Makefile.sources   |   4 +
 src/glsl/cache.c            | 708 ++++++++++++++++++++++++++++++++++++++++++++
 src/glsl/cache.h            | 172 +++++++++++
 src/glsl/tests/.gitignore   |   1 +
 src/glsl/tests/cache_test.c | 414 ++++++++++++++++++++++++++
 8 files changed, 1324 insertions(+)
 create mode 100644 src/glsl/cache.c
 create mode 100644 src/glsl/cache.h
 create mode 100644 src/glsl/tests/cache_test.c

Patch hide | download patch | download mbox

diff --git a/configure.ac b/configure.ac
index c2d775e..dcf5fca 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1072,6 +1072,9 @@  if test "x$with_sha1" = "x"; then
     fi
 fi
 AM_CONDITIONAL([ENABLE_SHADER_CACHE], [test x$enable_shader_cache = xyes])
+if test "x$enable_shader_cache" = "xyes"; then
+   AC_DEFINE([ENABLE_SHADER_CACHE], [1], [Enable shader cache])
+fi
 
 # Check for libdrm
 PKG_CHECK_MODULES([LIBDRM], [libdrm >= $LIBDRM_REQUIRED],
diff --git a/docs/envvars.html b/docs/envvars.html
index 31d14a4..a606bec 100644
--- a/docs/envvars.html
+++ b/docs/envvars.html
@@ -94,6 +94,17 @@  This is only valid for versions &gt;= 3.0.
 glGetString(GL_SHADING_LANGUAGE_VERSION). Valid values are integers, such as
 "130".  Mesa will not really implement all the features of the given language version
 if it's higher than what's normally reported. (for developers only)
+<li>MESA_GLSL_CACHE_DISABLE - if set, disables the GLSL shader cache
+<li>MESA_GLSL_CACHE_MAX_SIZE - if set, determines the maximum size of
+the on-disk cache of compiled GLSL programs. Should be set to a number
+optionally followed by 'K', 'M', or 'G' to specify a size in
+kilobytes, megabytes, or gigabytes. By default, gigabytes will be
+assumed. And if unset, a maxium size of 1GB will be used.
+<li>MESA_GLSL_CACHE_DIR - if set, determines the directory to be used
+for the on-disk cache of compiled GLSL programs. If this variable is
+not set, then the cache will be stored in $XDG_CACHE_HOME/.mesa (if
+that variable is set), or else within .cache/mesa within the user's
+home directory.
 <li>MESA_GLSL - <a href="shading.html#envvars">shading language compiler options</a>
 </ul>
 
diff --git a/src/glsl/Makefile.am b/src/glsl/Makefile.am
index e89a9ad..0c912ac 100644
--- a/src/glsl/Makefile.am
+++ b/src/glsl/Makefile.am
@@ -52,6 +52,7 @@  include Makefile.sources
 TESTS = glcpp/tests/glcpp-test				\
 	glcpp/tests/glcpp-test-cr-lf			\
 	tests/blob-test					\
+	tests/cache-test				\
 	tests/general-ir-test				\
 	tests/optimization-test				\
 	tests/sampler-types-test                        \
@@ -66,6 +67,7 @@  check_PROGRAMS =					\
 	glcpp/glcpp					\
 	glsl_test					\
 	tests/blob-test					\
+	tests/cache-test				\
 	tests/general-ir-test				\
 	tests/sampler-types-test			\
 	tests/uniform-initializer-test
@@ -77,6 +79,11 @@  tests_blob_test_SOURCES =				\
 tests_blob_test_LDADD =					\
 	$(top_builddir)/src/glsl/libglsl.la
 
+tests_cache_test_SOURCES =				\
+	tests/cache_test.c
+tests_cache_test_LDADD =				\
+	$(top_builddir)/src/glsl/libglsl.la
+
 tests_general_ir_test_SOURCES =		\
 	standalone_scaffolding.cpp			\
 	tests/builtin_variable_test.cpp			\
@@ -141,6 +148,10 @@  libglsl_la_SOURCES =					\
 	$(LIBGLSL_FILES)				\
 	$(NIR_FILES)
 
+if ENABLE_SHADER_CACHE
+libglsl_la_SOURCES += $(LIBGLSL_SHADER_CACHE_FILES)
+endif
+
 glsl_compiler_SOURCES = \
 	$(GLSL_COMPILER_CXX_FILES)
 
diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources
index a580b6e..4ccce30 100644
--- a/src/glsl/Makefile.sources
+++ b/src/glsl/Makefile.sources
@@ -181,6 +181,10 @@  LIBGLSL_FILES = \
 	s_expression.cpp \
 	s_expression.h
 
+LIBGLSL_SHADER_CACHE_FILES = \
+	cache.c \
+	cache.h
+
 # glsl_compiler
 
 GLSL_COMPILER_CXX_FILES = \
diff --git a/src/glsl/cache.c b/src/glsl/cache.c
new file mode 100644
index 0000000..15f660d
--- /dev/null
+++ b/src/glsl/cache.c
@@ -0,0 +1,708 @@ 
+/*
+ * Copyright © 2014 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ */
+
+#include <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <sys/file.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/mman.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <pwd.h>
+#include <errno.h>
+#include <dirent.h>
+
+#include "util/u_atomic.h"
+#include "util/mesa-sha1.h"
+#include "util/ralloc.h"
+#include "main/errors.h"
+
+#include "cache.h"
+
+/* Number of bits to mask off from a cache key to get an index. */
+#define CACHE_INDEX_KEY_BITS 16
+
+/* Mask for computing an index from a key. */
+#define CACHE_INDEX_KEY_MASK ((1 << CACHE_INDEX_KEY_BITS) - 1)
+
+/* The number of keys that can be stored in the index. */
+#define CACHE_INDEX_MAX_KEYS (1 << CACHE_INDEX_KEY_BITS)
+
+struct program_cache {
+   /* The path to the cache directory. */
+   char *path;
+
+   /* A pointer to the mmapped index file within the cache directory. */
+   uint8_t *index_mmap;
+   size_t index_mmap_size;
+
+   /* Pointer to total size of all objects in cache (within index_mmap) */
+   uint64_t *size;
+
+   /* Pointer to stored keys, (within index_mmap). */
+   uint8_t *stored_keys;
+
+   /* Maximum size of all cached objects (in bytes). */
+   uint64_t max_size;
+};
+
+/* Create a directory named 'path' if it does not already exist.
+ *
+ * Returns: 0 if path already exists as a directory or if created.
+ *         -1 in all other cases.
+ */
+static int
+mkdir_if_needed(char *path)
+{
+   struct stat sb;
+
+   /* If the path exists already, then our work is done if it's a
+    * directory, but it's an error if it is not.
+    */
+   if (stat(path, &sb) == 0) {
+      if (S_ISDIR(sb.st_mode)) {
+         return 0;
+      } else {
+         _mesa_warning(NULL,
+                       "Cannot use %s for shader cache (not a directory)"
+                       "---disabling.\n", path);
+         return -1;
+      }
+   }
+
+   if (mkdir(path, 0755) == 0)
+      return 0;
+
+   _mesa_warning(NULL,
+                 "Failed to create %s for shader cache (%s)---disabling.\n",
+                 path, strerror(errno));
+
+   return -1;
+}
+
+/* Concatenate an existing path and a new name to form a new path.  If the new
+ * path does not exist as a directory, create it then return the resulting
+ * name of the new path (ralloc'ed off of 'ctx').
+ *
+ * Returns NULL on any error, such as:
+ *
+ *	<path> does not exist or is not a directory
+ *	<path>/<name> exists but is not a directory
+ *	<path>/<name> cannot be created as a directory
+ */
+static char *
+concatenate_and_mkdir(void *ctx, char *path, char *name)
+{
+   char *new_path;
+   struct stat sb;
+
+   if (stat(path, &sb) != 0 || ! S_ISDIR(sb.st_mode))
+      return NULL;
+
+   new_path = ralloc_asprintf(ctx, "%s/%s", path, name);
+
+   if (mkdir_if_needed(new_path) == 0)
+      return new_path;
+   else
+      return NULL;
+}
+
+struct program_cache *
+cache_create(void)
+{
+   void *local;
+   struct program_cache *cache = NULL;
+   char *path, *max_size_str;
+   uint64_t max_size;
+   int fd = -1;
+   struct stat sb;
+   size_t size;
+
+   /* A ralloc context for transient data during this invocation. */
+   local = ralloc_context(NULL);
+   if (local == NULL)
+      goto fail;
+
+   /* At user request, disable shader cache entirely. */
+   if (getenv("MESA_GLSL_CACHE_DISABLE"))
+      goto fail;
+
+   /* Determine path for cache based on the first defined name as follows:
+    *
+    *	$MESA_GLSL_CACHE_DIR
+    *   $XDG_CACHE_HOME/mesa
+    *   <pwd.pw_dir>/.cache/mesa
+    */
+   path = getenv("MESA_GLSL_CACHE_DIR");
+   if (path && mkdir_if_needed(path) == -1) {
+      goto fail;
+   }
+
+   if (path == NULL) {
+      char *xdg_cache_home = getenv("XDG_CACHE_HOME");
+
+      if (xdg_cache_home) {
+         if (mkdir_if_needed(xdg_cache_home) == -1)
+            goto fail;
+
+         path = concatenate_and_mkdir(local, xdg_cache_home, "mesa");
+         if (path == NULL)
+            goto fail;
+      }
+   }
+
+   if (path == NULL) {
+      char *buf;
+      size_t buf_size;
+      struct passwd pwd, *result;
+
+      buf_size = sysconf(_SC_GETPW_R_SIZE_MAX);
+      if (buf_size == -1)
+         buf_size = 512;
+
+      /* Loop until buf_size is large enough to query the directory */
+      while (1) {
+         buf = ralloc_size(local, buf_size);
+
+         getpwuid_r(getuid(), &pwd, buf, buf_size, &result);
+         if (result)
+            break;
+
+         if (errno == ERANGE) {
+            ralloc_free(buf);
+            buf = NULL;
+            buf_size *= 2;
+         } else {
+            goto fail;
+         }
+      }
+
+      path = concatenate_and_mkdir(local, pwd.pw_dir, ".cache");
+      if (path == NULL)
+         goto fail;
+
+      path = concatenate_and_mkdir(local, path, "mesa");
+      if (path == NULL)
+         goto fail;
+   }
+
+   cache = ralloc(NULL, struct program_cache);
+   if (cache == NULL)
+      goto fail;
+
+   cache->path = ralloc_strdup(cache, path);
+   if (cache->path == NULL)
+      goto fail;
+
+   path = ralloc_asprintf(local, "%s/index", cache->path);
+   if (path == NULL)
+      goto fail;
+
+   fd = open(path, O_RDWR | O_CREAT | O_CLOEXEC, 0644);
+   if (fd == -1)
+      goto fail;
+
+   if (fstat(fd, &sb) == -1)
+      goto fail;
+
+   /* Force the index file to be the expected size. */
+   size = sizeof(*cache->size) + CACHE_INDEX_MAX_KEYS * CACHE_KEY_SIZE;
+   if (sb.st_size != size) {
+      if (ftruncate(fd, size) == -1)
+	 goto fail;
+   }
+
+   /* We map this shared so that other processes see updates that we
+    * make.
+    *
+    * Note: We do use atomic addition to ensure that multiple
+    * processes don't scramble the cache size recorded in the
+    * index. But we don't use any locking to prevent multiple
+    * processes from updating the same entry simultaneously. The idea
+    * is that if either result lands entirely in the index, then
+    * that's equivalent to a well-ordered write followed by an
+    * eviction and a write. On the other hand, if the simultaneous
+    * writes result in a corrupt entry, that's not really any
+    * different than both entries being evicted, (since within the
+    * guarantees of the cryptographic hash, a corrupt entry is
+    * unlikely to ever match a real cache key).
+    */
+   cache->index_mmap = mmap(NULL, size, PROT_READ | PROT_WRITE,
+			    MAP_SHARED, fd, 0);
+   if (cache->index_mmap == MAP_FAILED)
+      goto fail;
+   cache->index_mmap_size = size;
+
+   close(fd);
+
+   cache->size = (uint64_t *) cache->index_mmap;
+   cache->stored_keys = cache->index_mmap + sizeof(uint64_t);
+
+   max_size = 0;
+
+   max_size_str = getenv("MESA_GLSL_CACHE_MAX_SIZE");
+   if (max_size_str) {
+      char *end;
+      max_size = strtoul(max_size_str, &end, 10);
+      if (end == max_size_str) {
+	 max_size = 0;
+      } else {
+	 while (*end && isspace(*end))
+	    end++;
+	 switch (*end) {
+	 case 'K':
+	 case 'k':
+	    max_size *= 1024;
+	    break;
+	 case 'M':
+	 case 'm':
+	    max_size *= 1024*1024;
+	    break;
+	 case '\0':
+	 case 'G':
+	 case 'g':
+	 default:
+	    max_size *= 1024*1024*1024;
+	    break;
+	 }
+      }
+   }
+
+   /* Default to 1GB for maximum cache size. */
+   if (max_size == 0)
+      max_size = 1024*1024*1024;
+
+   cache->max_size = max_size;
+
+   ralloc_free(local);
+
+   return cache;
+
+ fail:
+   if (fd != -1)
+      close(fd);
+   if (cache)
+      ralloc_free(cache);
+   ralloc_free(local);
+
+   return NULL;
+}
+
+void
+cache_destroy(struct program_cache *cache)
+{
+   munmap(cache->index_mmap, cache->index_mmap_size);
+
+   ralloc_free(cache);
+}
+
+/* Return a filename within the cache's directory corresponding to 'key'. The
+ * returned filename is ralloced with 'cache' as the parent context.
+ *
+ * Returns NULL if out of memory.
+ */
+static char *
+get_cache_file(struct program_cache *cache, cache_key key)
+{
+   char buf[41];
+
+   _mesa_sha1_format(buf, key);
+
+   return ralloc_asprintf(cache, "%s/%c%c/%s",
+			  cache->path, buf[0], buf[1], buf + 2);
+}
+
+/* Create the directory that will be needed for the cache file for \key.
+ *
+ * Obviously, the implementation here must closely match
+ * _get_cache_file above.
+*/
+static void
+make_cache_file_directory(struct program_cache *cache, cache_key key)
+{
+   char *dir;
+   char buf[41];
+
+   _mesa_sha1_format(buf, key);
+
+   dir = ralloc_asprintf(cache, "%s/%c%c", cache->path, buf[0], buf[1]);
+
+   mkdir_if_needed(dir);
+
+   ralloc_free(dir);
+}
+
+/* Given a directory path and predicate function, count all entries in
+ * that directory for which the predicate returns true. Then choose a
+ * random entry from among those counted.
+ *
+ * Returns: A malloc'ed string for the path to the chosen file, (or
+ * NULL on any error). The caller should free the string when
+ * finished.
+ */
+static char *
+choose_random_file_matching(const char *dir_path,
+			    bool (*predicate)(struct dirent *))
+{
+   DIR *dir;
+   struct dirent *entry;
+   unsigned int count, victim;
+   char *filename;
+
+   dir = opendir(dir_path);
+   if (dir == NULL)
+      return NULL;
+
+   count = 0;
+
+   while (1) {
+      entry = readdir(dir);
+      if (entry == NULL)
+	 break;
+      if (! predicate(entry))
+	 continue;
+
+      count++;
+   }
+
+   if (count == 0) {
+      closedir(dir);
+      return NULL;
+   }
+
+   victim = rand() % count;
+
+   rewinddir(dir);
+   count = 0;
+
+   while (1) {
+      entry = readdir(dir);
+      if (entry == NULL)
+	 break;
+      if (! predicate(entry))
+	 continue;
+      if (count == victim)
+	 break;
+
+      count++;
+   }
+
+   if (entry == NULL) {
+      closedir(dir);
+      return NULL;
+   }
+
+   asprintf(&filename, "%s/%s", dir_path, entry->d_name);
+
+   closedir(dir);
+
+   return filename;
+}
+
+/* Is entry a regular file, and not having a name with a trailing
+ * ".tmp"
+ */
+static bool
+is_regular_non_tmp_file(struct dirent *entry)
+{
+   size_t len;
+
+   if (entry->d_type != DT_REG)
+      return false;
+
+   len = strlen (entry->d_name);
+   if (len >= 4 && strcmp(&entry->d_name[len-4], ".tmp") == 0)
+      return false;
+
+   return true;
+}
+
+/* Returns the size of the deleted file, (or 0 on any error). */
+static size_t
+unlink_random_file_from_directory(const char *path)
+{
+   struct stat sb;
+   char *filename;
+
+   filename = choose_random_file_matching(path, is_regular_non_tmp_file);
+   if (filename == NULL)
+      return 0;
+
+   if (stat(filename, &sb) == -1) {
+      free (filename);
+      return 0;
+   }
+
+   unlink(filename);
+
+   free (filename);
+
+   return sb.st_size;
+}
+
+/* Is entry a directory with a two-character name, (and not the
+ * special name of "..")
+ */
+static bool
+is_two_character_sub_directory(struct dirent *entry)
+{
+   if (entry->d_type != DT_DIR)
+      return false;
+
+   if (strlen(entry->d_name) != 2)
+      return false;
+
+   if (strcmp(entry->d_name, "..") == 0)
+      return false;
+
+   return true;
+}
+
+static void
+evict_random_item(struct program_cache *cache)
+{
+   const char hex[] = "0123456789abcde";
+   char *dir_path;
+   int a, b;
+   size_t size;
+
+   /* With a reasonably-sized, full cache, (and with keys generated
+    * from a cryptographic hash), we can choose two random hex digits
+    * and reasonably expect the directory to exist with a file in it.
+    */
+   a = rand() % 16;
+   b = rand() % 16;
+
+   asprintf (&dir_path, "%s/%c%c", cache->path, hex[a], hex[b]);
+   if (dir_path == NULL)
+      return;
+
+   size = unlink_random_file_from_directory(dir_path);
+
+   free(dir_path);
+
+   if (size) {
+      p_atomic_add(cache->size, - size);
+      return;
+   }
+
+   /* In the case where the random choice of directory didn't find
+    * something, we choose randomly from the existing directories.
+    *
+    * Really, the only reason this code exists is to allow the unit
+    * tests to work, (which use an artificially-small cache to be able
+    * to force a single cached item to be evicted).
+    */
+   dir_path = choose_random_file_matching(cache->path,
+					  is_two_character_sub_directory);
+   if (dir_path == NULL)
+      return;
+
+   size = unlink_random_file_from_directory(dir_path);
+
+   free(dir_path);
+
+   if (size)
+      p_atomic_add(cache->size, - size);
+}
+
+void
+cache_put(struct program_cache *cache,
+          cache_key key,
+          const void *data,
+          size_t size)
+{
+   int fd = -1, fd_final = -1, err, ret;
+   size_t len;
+   char *filename = NULL, *filename_tmp = NULL;
+   const char *p = data;
+
+   filename = get_cache_file(cache, key);
+   if (filename == NULL)
+      goto done;
+
+   /* Write to a temporary file to allow for an atomic rename to the
+    * final destination filename, (to prevent any readers from seeing
+    * a partially written file).
+    */
+   filename_tmp = ralloc_asprintf(cache, "%s.tmp", filename);
+   if (filename_tmp == NULL)
+      goto done;
+
+   fd = open(filename_tmp, O_WRONLY | O_CLOEXEC | O_CREAT, 0644);
+
+   /* Make the two-character subdirectory within the cache as needed. */
+   if (fd == -1) {
+      if (errno != ENOENT)
+	 goto done;
+
+      make_cache_file_directory(cache, key);
+
+      fd = open(filename_tmp, O_WRONLY | O_CLOEXEC | O_CREAT, 0644);
+      if (fd == -1)
+	 goto done;
+   }
+
+   /* With the temporary file open, we take an exclusive flock on
+    * it. If the flock fails, then another process still has the file
+    * open with the flock held. So just let that file be responsible
+    * for writing the file.
+    */
+   err = flock(fd, LOCK_EX);
+   if (err == -1)
+      goto done;
+
+   /* Now that we have the lock on the open temporary file, we can
+    * check to see if the destination file already exists. If so,
+    * another process won the race between when we saw that the file
+    * didn't exist and now. In this case, we don't do anything more,
+    * (to ensure the size accounting of the cache doesn't get off).
+    */
+   fd_final = open(filename, O_RDONLY | O_CLOEXEC);
+   if (fd_final != -1)
+      goto done;
+
+   /* OK, we're now on the hook to write out a file that we know is
+    * not in the cache, and is also not being written out to the cache
+    * by some other process.
+    *
+    * Before we do that, if the cache is too large, evict something
+    * else first.
+    */
+   if (*cache->size + size > cache->max_size)
+      evict_random_item(cache);
+
+   /* Now, finally, write out the contents to the temporary file, then
+    * rename them atomically to the destination filename, and also
+    * perform an atomic increment of the total cache size.
+    */
+   for (len = 0; len < size; len += ret) {
+      ret = write(fd, p + len, size - len);
+      if (ret == -1) {
+         unlink(filename_tmp);
+         goto done;
+      }
+   }
+
+   rename(filename_tmp, filename);
+
+   p_atomic_add(cache->size, size);
+
+   /* This close finally releases the flock, (now that the final dile
+    * has been renamed into place and the size has been added).
+    */
+   close(fd);
+   fd = -1;
+
+ done:
+   if (filename_tmp)
+      ralloc_free(filename_tmp);
+   if (filename)
+      ralloc_free(filename);
+   if (fd != -1)
+      close(fd);
+}
+
+void *
+cache_get(struct program_cache *cache, cache_key key, size_t *size)
+{
+   int fd = -1, ret, len;
+   struct stat sb;
+   char *filename = NULL;
+   uint8_t *data = NULL;
+
+   if (size)
+      *size = 0;
+
+   filename = get_cache_file(cache, key);
+   if (filename == NULL)
+      goto fail;
+
+   fd = open(filename, O_RDONLY | O_CLOEXEC);
+   if (fd == -1)
+      goto fail;
+
+   if (fstat(fd, &sb) == -1)
+      goto fail;
+
+   data = malloc(sb.st_size);
+   if (data == NULL)
+      goto fail;
+
+   for (len = 0; len < sb.st_size; len += ret) {
+      ret = read(fd, data + len, sb.st_size - len);
+      if (ret == -1)
+         goto fail;
+   }
+
+   ralloc_free(filename);
+   close(fd);
+
+   if (size)
+      *size = sb.st_size;
+
+   return data;
+
+ fail:
+   if (data)
+      free(data);
+   if (filename)
+      ralloc_free(filename);
+   if (fd != -1)
+      close(fd);
+
+   return NULL;
+}
+
+void
+cache_put_key(struct program_cache *cache, cache_key key)
+{
+   uint32_t *key_chunk = (uint32_t *) key;
+   int i = *key_chunk & CACHE_INDEX_KEY_MASK;
+   unsigned char *entry;
+
+   entry = &cache->stored_keys[i + CACHE_KEY_SIZE];
+
+   memcpy(entry, key, CACHE_KEY_SIZE);
+}
+
+/* This function lets us test whether a given key was previously
+ * stored in the cache with cache_put_key(). The implement is
+ * efficient by not using syscalls or hitting the disk. It's not
+ * race-free, but the races are benign. If we race with someone else
+ * calling cache_put_key, then that's just an extra cache miss and an
+ * extra recompile.
+ */
+bool
+cache_has_key(struct program_cache *cache, cache_key key)
+{
+   uint32_t *key_chunk = (uint32_t *) key;
+   int i = *key_chunk & CACHE_INDEX_KEY_MASK;
+   unsigned char *entry;
+
+   entry = &cache->stored_keys[i + CACHE_KEY_SIZE];
+
+   return memcmp(entry, key, CACHE_KEY_SIZE) == 0;
+}
diff --git a/src/glsl/cache.h b/src/glsl/cache.h
new file mode 100644
index 0000000..3617dd6
--- /dev/null
+++ b/src/glsl/cache.h
@@ -0,0 +1,172 @@ 
+/*
+ * Copyright © 2014 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ */
+
+#pragma once
+#ifndef CACHE_H
+#define CACHE_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <stdint.h>
+#include <stdbool.h>
+
+/* Size of cache keys in bytes. */
+#define CACHE_KEY_SIZE 20
+
+typedef uint8_t cache_key[CACHE_KEY_SIZE];
+
+/* Provide inlined stub functions if the shader cache is disabled. */
+
+#ifdef ENABLE_SHADER_CACHE
+
+/**
+ * Create a new cache object.
+ *
+ * This function creates the handle necessary for all subsequent cache_*
+ * functions.
+ *
+ * This cache provides two distinct operations:
+ *
+ *   o Storage and retrieval of arbitrary objects by cryptographic
+ *     name (or "key").  This is provided via cache_put() and
+ *     cache_get().
+ *
+ *   o The ability to store a key alone and check later whether the
+ *     key was previously stored. This is provided via cache_put_key()
+ *     and cache_has_key().
+ *
+ * The put_key()/has_key() operations are conceptually identical to
+ * put()/get() with no data, but are provided separately to allow for
+ * a more efficient implementation.
+ *
+ * In all cases, the keys are sequences of 20 bytes. It is anticipated
+ * that callers will compute appropriate SHA-1 signatures for keys,
+ * (though nothing in this implementation directly relies on how the
+ * names are computed). See mesa-sha1.h and _mesa_sha1_compute for
+ * assistance in computing SHA-1 signatures.
+ */
+struct program_cache *
+cache_create(void);
+
+/**
+ * Destroy a cache object, (freeing all associated resources).
+ */
+void
+cache_destroy(struct program_cache *cache);
+
+/**
+ * Store an item in the cache under the name \key.
+ *
+ * The item can be retrieved later with cache_get(), (unless the item has
+ * been evicted in the interim).
+ *
+ * Any call to cache_put() may cause an existing, random item to be
+ * evicted from the cache.
+ */
+void
+cache_put(struct program_cache *cache, cache_key key,
+          const void *data, size_t size);
+
+/**
+ * Retrieve an item previously stored in the cache with the name <key>.
+ *
+ * The item must have been previously stored with a call to cache_put().
+ *
+ * If \size is non-NULL, then, on successful return, it will be set to the
+ * size of the object.
+ *
+ * \return A pointer to the stored object if found. NULL if the object
+ * is not found, or if any error occurs, (memory allocation failure,
+ * filesystem error, etc.). The returned data is malloc'ed so the
+ * caller should call free() it when finished.
+ */
+void *
+cache_get(struct program_cache *cache, cache_key key, size_t *size);
+
+/**
+ * Store the name \key within the cache, (without any associated data).
+ *
+ * Later this key can be checked with cache_has_key(), (unless the key
+ * has been evicted in the interim).
+ *
+ * Any call to cache_record() may cause an existing, random key to be
+ * evicted from the cache.
+ */
+void
+cache_put_key(struct program_cache *cache, cache_key key);
+
+/**
+ * Test whether the name \key was previously recorded in the cache.
+ *
+ * Return value: True if cache_put_key() was previously called with
+ * \key, (and the key was not evicted in the interim).
+ *
+ * Note: cache_has_key() will only return true for keys passed to
+ * cache_put_key(). Specifically, a call to cache_put() will not cause
+ * cache_has_key() to return true for the same key.
+ */
+bool
+cache_has_key(struct program_cache *cache, cache_key key);
+
+#else
+
+static inline struct program_cache *
+cache_create(void)
+{
+   return NULL;
+}
+
+static inline void
+cache_put(struct program_cache *cache, cache_key key,
+          const void *data, size_t size)
+{
+   return 0;
+}
+
+static inline uint8_t *
+cache_get(struct program_cache *cache, cache_key key, size_t *size)
+{
+   return NULL;
+}
+
+static inline void
+cache_put_key(struct program_cache *cache, cache_key key)
+{
+   return;
+}
+
+static inline bool
+cache_has_key(struct program_cache *cache, cache_key key)
+{
+   return false;
+}
+
+#endif /* ENABLE_SHADER_CACHE */
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* CACHE_H */
diff --git a/src/glsl/tests/.gitignore b/src/glsl/tests/.gitignore
index 13dcdc4..1661ae7 100644
--- a/src/glsl/tests/.gitignore
+++ b/src/glsl/tests/.gitignore
@@ -1,4 +1,5 @@ 
 blob-test
+cache-test
 ralloc-test
 uniform-initializer-test
 sampler-types-test
diff --git a/src/glsl/tests/cache_test.c b/src/glsl/tests/cache_test.c
new file mode 100644
index 0000000..36acf84
--- /dev/null
+++ b/src/glsl/tests/cache_test.c
@@ -0,0 +1,414 @@ 
+/*
+ * Copyright © 2015 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ */
+
+/* A collection of unit tests for cache.c */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+#include <ftw.h>
+#include <errno.h>
+#include <stdarg.h>
+
+#include "util/mesa-sha1.h"
+#include "cache.h"
+
+bool error = false;
+
+void
+_mesa_warning(void *ctx, const char *fmt, ...);
+
+void
+_mesa_warning(void *ctx, const char *fmt, ...)
+{
+    va_list vargs;
+    (void) ctx;
+
+    va_start(vargs, fmt);
+
+    /* This output is not thread-safe, but that's good enough for the
+     * standalone compiler.
+     */
+    fprintf(stderr, "Mesa warning: ");
+    vfprintf(stderr, fmt, vargs);
+    fprintf(stderr, "\n");
+
+    va_end(vargs);
+}
+
+static void
+expect_equal(uint64_t actual, uint64_t expected, const char *test)
+{
+   if (actual != expected) {
+      fprintf (stderr, "Error: Test '%s' failed: Expected=%ld, Actual=%ld\n",
+               test, expected, actual);
+      error = true;
+   }
+}
+
+static void
+expect_null(void *ptr, const char *test)
+{
+   if (ptr != NULL) {
+      fprintf (stderr, "Error: Test '%s' failed: Result=%p, but expected NULL.\n",
+               test, ptr);
+      error = true;
+   }
+}
+
+static void
+expect_non_null(void *ptr, const char *test)
+{
+   if (ptr == NULL) {
+      fprintf (stderr, "Error: Test '%s' failed: Result=NULL, but expected something else.\n",
+               test);
+      error = true;
+   }
+}
+
+static void
+expect_equal_str(const char *actual, const char *expected, const char *test)
+{
+   if (strcmp(actual, expected)) {
+      fprintf (stderr, "Error: Test '%s' failed:\n\t"
+               "Expected=\"%s\", Actual=\"%s\"\n",
+               test, expected, actual);
+      error = true;
+   }
+}
+
+/* Callback for nftw used in rmrf_local below.
+ */
+static int
+remove_entry(const char *path,
+	     const struct stat *sb,
+	     int typeflag,
+	     struct FTW *ftwbuf)
+{
+   int err = remove(path);
+
+   if (err)
+      fprintf(stderr, "Error removing %s: %s\n", path, strerror(errno));
+
+   return err;
+}
+
+/* Recursively remove a directory.
+ *
+ * This is equivalent to "rm -rf <dir>" with one bit of protection
+ * that the directory name must begin with "." to ensure we don't
+ * wander around deleting more than intended.
+ *
+ * Returns 0 on success, -1 on any error.
+ */
+static int
+rmrf_local(const char *path)
+{
+   if (path == NULL || *path == '\0' || *path != '.')
+      return -1;
+
+   return nftw(path, remove_entry, 64, FTW_DEPTH | FTW_PHYS | FTW_MOUNT);
+}
+
+#define CACHE_TEST_TMP "./cache-test-tmp"
+
+static void
+test_cache_create(void)
+{
+   struct program_cache *cache;
+   int err;
+
+   /* Before doing anything else, ensure that with
+    * MESA_GLSL_CACHE_DISABLE set, that cache_create returns NULL.
+    */
+   setenv("MESA_GLSL_CACHE_DISABLE", "1", 1);
+   cache = cache_create();
+   expect_null(cache, "cache_create with MESA_GLSL_CACHE_DISABLE set");
+
+   unsetenv("MESA_GLSL_CACHE_DISABLE");
+
+   /* For the first real cache_create() clear these environment
+    * variables to test creation of cache in home directory.
+    */
+   unsetenv("MESA_GLSL_CACHE_DIR");
+   unsetenv("XDG_CACHE_HOME");
+
+   cache = cache_create();
+   expect_non_null(cache, "cache_create with no environment variables");
+
+   cache_destroy(cache);
+
+   /* Test with XDG_CACHE_HOME set */
+   err = rmrf_local(CACHE_TEST_TMP);
+   expect_equal(err, 0, "Removing " CACHE_TEST_TMP);
+
+   setenv("XDG_CACHE_HOME", CACHE_TEST_TMP "/xdg-cache-home", 1);
+   cache = cache_create();
+   expect_null(cache, "cache_create with XDG_CACHE_HOME set with"
+	       "a non-existing parent directory");
+
+   mkdir(CACHE_TEST_TMP, 0755);
+   cache = cache_create();
+   expect_non_null(cache, "cache_create with XDG_CACHE_HOME set");
+
+   cache_destroy(cache);
+
+   /* Test with MESA_GLSL_CACHE_DIR set */
+   err = rmrf_local(CACHE_TEST_TMP);
+   expect_equal(err, 0, "Removing " CACHE_TEST_TMP " again");
+
+   setenv("MESA_GLSL_CACHE_DIR", CACHE_TEST_TMP "/mesa-glsl-cache-dir", 1);
+   cache = cache_create();
+   expect_null(cache, "cache_create with MESA_GLSL_CACHE_DIR set with"
+	       "a non-existing parent directory");
+
+   mkdir(CACHE_TEST_TMP, 0755);
+   cache = cache_create();
+   expect_non_null(cache, "cache_create with MESA_GLSL_CACHE_DIR set");
+
+   cache_destroy(cache);
+}
+
+static bool
+does_cache_contain(struct program_cache *cache, cache_key key)
+{
+   void *result;
+
+   result = cache_get(cache, key, NULL);
+
+   if (result) {
+      free (result);
+      return true;
+   }
+
+   return false;
+}
+
+static void
+test_put_and_get(void)
+{
+   struct program_cache *cache;
+   /* If the text of this blob is changed, then blob_key_byte_zero
+    * also needs to be updated.
+    */
+   char blob[] = "This is a blob of thirty-seven bytes";
+   uint8_t blob_key[20];
+   uint8_t blob_key_byte_zero = 0xca;
+   char string[] = "While this string has thirty-four";
+   uint8_t string_key[20];
+   char *result;
+   size_t size;
+   uint8_t *one_KB, *one_MB;
+   uint8_t one_KB_key[20], one_MB_key[20];
+   int count;
+
+   cache = cache_create();
+
+   _mesa_sha1_compute(blob, sizeof(blob), blob_key);
+
+   /* Ensure that cache_get returns nothing before anything is added. */
+   result = cache_get(cache, blob_key, &size);
+   expect_null(result, "cache_get with non-existent item (pointer)");
+   expect_equal(size, 0, "cache_get with non-existent item (size)");
+
+   /* Simple test of put and get. */
+   cache_put(cache, blob_key, blob, sizeof(blob));
+
+   result = cache_get(cache, blob_key, &size);
+   expect_equal_str(blob, result, "cache_get of existing item (pointer)");
+   expect_equal(size, sizeof(blob), "cache_get of existing item (size)");
+
+   free(result);
+
+   /* Test put and get of a second item. */
+   _mesa_sha1_compute(string, sizeof(string), string_key);
+   cache_put(cache, string_key, string, sizeof(string));
+
+   result = cache_get(cache, string_key, &size);
+   expect_equal_str(result, string, "2nd cache_get of existing item (pointer)");
+   expect_equal(size, sizeof(string), "2nd cache_get of existing item (size)");
+
+   free(result);
+
+   /* Set the cache size to 1KB and add a 1KB item to force an eviction. */
+   cache_destroy(cache);
+
+   setenv("MESA_GLSL_CACHE_MAX_SIZE", "1K", 1);
+   cache = cache_create();
+
+   one_KB = calloc(1, 1024);
+
+   /* Obviously the SHA-1 hash of 1024 zero bytes isn't particularly
+    * interesting. But we do have want to take some special care with
+    * the hash we use here. The issue is that in this artificial case,
+    * (with only three files in the cache), the probability is good
+    * that each of the three files will end up in their own
+    * directory. Then, if the directory containing the .tmp file for
+    * the new item being added for cache_put() is the chosen victim
+    * directory for eviction, then no suitable file will be found and
+    * nothing will be evicted.
+    *
+    * That's actually expected given how the eviction code is
+    * implemented, (which expects to only evict once things are more
+    * interestingly full than that).
+    *
+    * For this test, we force this signature to land in the same
+    * directory as the original blob first written to the cache.
+    */
+   _mesa_sha1_compute(one_KB, 1024, one_KB_key);
+   one_KB_key[0] = blob_key_byte_zero;
+
+   cache_put(cache, one_KB_key, one_KB, 1024);
+
+   free (one_KB);
+
+   result = cache_get(cache, one_KB_key, &size);
+   expect_non_null(result, "3rd cache_get of existing item (pointer)");
+   expect_equal(size, 1024, "3rd cache_get of existing item (size)");
+
+   free(result);
+
+   /* Ensure eviction happened by checking that only one of the two
+    * previously-added items can still be fetched.
+    */
+   count = 0;
+   if (does_cache_contain(cache, blob_key))
+       count++;
+
+   if (does_cache_contain(cache, string_key))
+       count++;
+
+   expect_equal(count, 1, "cache_put eviction with MAX_SIZE=1K");
+
+   /* Now increase the size to 1M, add back both items, and ensure all
+    * three that have been added are available via cache_get.
+    */
+   cache_destroy(cache);
+
+   setenv("MESA_GLSL_CACHE_MAX_SIZE", "1M", 1);
+   cache = cache_create();
+
+   cache_put(cache, blob_key, blob, sizeof(blob));
+   cache_put(cache, string_key, string, sizeof(string));
+
+   count = 0;
+   if (does_cache_contain(cache, blob_key))
+       count++;
+
+   if (does_cache_contain(cache, string_key))
+       count++;
+
+   if (does_cache_contain(cache, one_KB_key))
+       count++;
+
+   expect_equal(count, 3, "no eviction before overflow with MAX_SIZE=1M");
+
+   /* Finally, check eviction again after adding an object of size 1M. */
+   one_MB = calloc(1024, 1024);
+
+   _mesa_sha1_compute(one_MB, 1024 * 1024, one_MB_key);
+   one_MB_key[0] = blob_key_byte_zero;;
+
+   cache_put(cache, one_MB_key, one_MB, 1024 * 1024);
+
+   free (one_MB);
+
+   count = 0;
+   if (does_cache_contain(cache, blob_key))
+       count++;
+
+   if (does_cache_contain(cache, string_key))
+       count++;
+
+   if (does_cache_contain(cache, one_KB_key))
+       count++;
+
+   expect_equal(count, 2, "eviction after overflow with MAX_SIZE=1M");
+
+   cache_destroy(cache);
+}
+
+static void
+test_put_key_and_get_key(void)
+{
+   struct program_cache *cache;
+   bool result;
+
+   uint8_t key_a[20] = {  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
+			 10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
+   uint8_t key_b[20] = { 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
+			 30, 33, 32, 33, 34, 35, 36, 37, 38, 39};
+   uint8_t key_a_collide[20] =
+                        { 0,  1, 42, 43, 44, 45, 46, 47, 48, 49,
+			 50, 55, 52, 53, 54, 55, 56, 57, 58, 59};
+
+   cache = cache_create();
+
+   /* First test that cache_has_key returns false before cache_put_key */
+   result = cache_has_key(cache, key_a);
+   expect_equal(result, 0, "cache_has_key before key added");
+
+   /* Then a couple of tests of cache_put_key followed by cache_has_key */
+   cache_put_key(cache, key_a);
+   result = cache_has_key(cache, key_a);
+   expect_equal(result, 1, "cache_has_key after key added");
+
+   cache_put_key(cache, key_b);
+   result = cache_has_key(cache, key_b);
+   expect_equal(result, 1, "2nd cache_has_key after key added");
+
+   /* Test that a key with the same two bytes as an existing key
+    * forces an eviction.
+    */
+   cache_put_key(cache, key_a_collide);
+   result = cache_has_key(cache, key_a_collide);
+   expect_equal(result, 1, "put_key of a colliding key lands in the cache");
+
+   result = cache_has_key(cache, key_a);
+   expect_equal(result, 0, "put_key of a colliding key evicts from the cache");
+
+   /* And finally test that we can re-add the original key to re-evict
+    * the colliding key.
+    */
+   cache_put_key(cache, key_a);
+   result = cache_has_key(cache, key_a);
+   expect_equal(result, 1, "put_key of original key lands again");
+
+   result = cache_has_key(cache, key_a_collide);
+   expect_equal(result, 0, "put_key of oiginal key evicts the colliding key");
+
+   cache_destroy(cache);
+}
+
+int
+main (void)
+{
+   test_cache_create();
+
+   test_put_and_get();
+
+   test_put_key_and_get_key();
+
+   return error ? 1 : 0;
+}