Add a in-memory cache

This is a more general API that caches data with a LRU scheme. See
include/cache.h. No comments yet, I'm still working on it. But Jeremy has given
me a hint in one of his checkins that he would like to make use of this now.

The idea is that we get rid of all our silly little caches and merge them all
into one cache that we can then very easily trim, for example even with a
smbcontrol message if someone decides memory is tight. The main user is the
stat cache, this patch also converts the getwd cache. More caches to come.
(This used to be commit 7a911b35713538d82001a3c9f34152e293fe1943)

10 files changed, 505 insertions, 204 deletions

diff --git a/source3/Makefile.in b/source3/Makefile.in
index eda3297d23..81c8330216 100644
--- a/source3/Makefile.in
+++ b/source3/Makefile.in
@@ -284,7 +284,7 @@ TALLOC_OBJ = lib/talloc/talloc.o
 LIB_WITHOUT_PROTO_OBJ = $(LIBREPLACE_OBJ) $(SOCKET_WRAPPER_OBJ) $(NSS_WRAPPER_OBJ) $(TALLOC_OBJ) \
 	lib/messages.o librpc/gen_ndr/ndr_messaging.o lib/messages_local.o \
 	lib/messages_ctdbd.o lib/packet.o lib/ctdbd_conn.o lib/talloc_stack.o \
-	lib/interfaces.o lib/rbtree.o
+	lib/interfaces.o lib/rbtree.o lib/cache.o
 
 LIB_WITH_PROTO_OBJ = $(VERSION_OBJ) lib/charcnv.o lib/debug.o lib/fault.o \
 	  lib/interface.o lib/md4.o \
diff --git a/source3/include/includes.h b/source3/include/includes.h
index 22451741a1..a45176aba3 100644
--- a/source3/include/includes.h
+++ b/source3/include/includes.h
@@ -719,6 +719,7 @@ typedef char fstring[FSTRING_LEN];
 #include "packet.h"
 #include "ctdbd_conn.h"
 #include "talloc_stack.h"
+#include "cache.h"
 
 /* used in net.c */
 struct functable {
diff --git a/source3/lib/cache.c b/source3/lib/cache.c
new file mode 100644
index 0000000000..baf2fe3984
--- /dev/null
+++ b/source3/lib/cache.c
@@ -0,0 +1,298 @@
+/*
+   Unix SMB/CIFS implementation.
+   In-memory cache
+   Copyright (C) Volker Lendecke 2007
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include "cache.h"
+#include "rbtree.h"
+
+struct memcache_element {
+	struct rb_node rb_node;
+	struct memcache_element *prev, *next;
+	size_t keylength, valuelength;
+	uint8 n;		/* This is really an enum, but save memory */
+	char data[1];		/* placeholder for offsetof */
+};
+
+struct memcache {
+	struct memcache_element *mru, *lru;
+	struct rb_root tree;
+	size_t size;
+	size_t max_size;
+};
+
+static int memcache_destructor(struct memcache *cache) {
+	struct memcache_element *e, *next;
+
+	for (e = cache->mru; e != NULL; e = next) {
+		next = e->next;
+		SAFE_FREE(e);
+	}
+	return 0;
+}
+
+struct memcache *memcache_init(TALLOC_CTX *mem_ctx, size_t max_size)
+{
+	struct memcache *result;
+
+	result = TALLOC_ZERO_P(mem_ctx, struct memcache);
+	if (result == NULL) {
+		return NULL;
+	}
+	result->max_size = max_size;
+	talloc_set_destructor(result, memcache_destructor);
+	return result;
+}
+
+static struct memcache_element *memcache_node2elem(struct rb_node *node)
+{
+	return (struct memcache_element *)
+		((char *)node - offsetof(struct memcache_element, rb_node));
+}
+
+static void memcache_element_parse(struct memcache_element *e,
+				   DATA_BLOB *key, DATA_BLOB *value)
+{
+	key->data = ((uint8 *)e) + offsetof(struct memcache_element, data);
+	key->length = e->keylength;
+	value->data = key->data + e->keylength;
+	value->length = e->valuelength;
+}
+
+static size_t memcache_element_size(size_t key_length, size_t value_length)
+{
+	return sizeof(struct memcache_element) - 1 + key_length + value_length;
+}
+
+static int memcache_compare(struct memcache_element *e, enum memcache_number n,
+			    DATA_BLOB key)
+{
+	DATA_BLOB this_key, this_value;
+
+	if ((int)e->n < (int)n) return -1;
+	if ((int)e->n > (int)n) return 1;
+
+	if (e->keylength < key.length) return -1;
+	if (e->keylength > key.length) return 1;
+
+	memcache_element_parse(e, &this_key, &this_value);
+	return memcmp(this_key.data, key.data, key.length);
+}
+
+static struct memcache_element *memcache_find(
+	struct memcache *cache, enum memcache_number n, DATA_BLOB key)
+{
+	struct rb_node *node;
+
+	node = cache->tree.rb_node;
+
+	while (node != NULL) {
+		struct memcache_element *elem = memcache_node2elem(node);
+		int cmp;
+
+		cmp = memcache_compare(elem, n, key);
+		if (cmp == 0) {
+			return elem;
+		}
+		node = (cmp < 0) ? node->rb_left : node->rb_right;
+	}
+
+	return NULL;
+}
+
+bool memcache_lookup(struct memcache *cache, enum memcache_number n,
+		     DATA_BLOB key, DATA_BLOB *value)
+{
+	struct memcache_element *e;
+
+	e = memcache_find(cache, n, key);
+	if (e == NULL) {
+		return false;
+	}
+
+	if (cache->size != 0) {
+		/*
+		 * Do LRU promotion only when we will ever shrink
+		 */
+		if (e == cache->lru) {
+			cache->lru = e->prev;
+		}
+		DLIST_PROMOTE(cache->mru, e);
+		if (cache->mru == NULL) {
+			cache->mru = e;
+		}
+	}
+
+	memcache_element_parse(e, &key, value);
+	return true;
+}
+
+static void memcache_delete_element(struct memcache *cache,
+				    struct memcache_element *e)
+{
+	rb_erase(&e->rb_node, &cache->tree);
+
+	if (e == cache->lru) {
+		cache->lru = e->prev;
+	}
+	DLIST_REMOVE(cache->mru, e);
+
+	cache->size -= memcache_element_size(e->keylength, e->valuelength);
+
+	SAFE_FREE(e);
+}
+
+static void memcache_trim(struct memcache *cache)
+{
+	if (cache->max_size == 0) {
+		return;
+	}
+
+	while ((cache->size > cache->max_size) && (cache->lru != NULL)) {
+		memcache_delete_element(cache, cache->lru);
+	}
+}
+
+void memcache_delete(struct memcache *cache, enum memcache_number n,
+		     DATA_BLOB key)
+{
+	struct memcache_element *e;
+
+	e = memcache_find(cache, n, key);
+	if (e == NULL) {
+		return;
+	}
+
+	memcache_delete_element(cache, e);
+}
+
+void memcache_add(struct memcache *cache, enum memcache_number n,
+		  DATA_BLOB key, DATA_BLOB value)
+{
+	struct memcache_element *e;
+	struct rb_node **p;
+	struct rb_node *parent;
+	DATA_BLOB cache_key, cache_value;
+	size_t element_size;
+
+	if (key.length == 0) {
+		return;
+	}
+
+	e = memcache_find(cache, n, key);
+
+	if (e != NULL) {
+		memcache_element_parse(e, &cache_key, &cache_value);
+
+		if (value.length <= cache_value.length) {
+			/*
+			 * We can reuse the existing record
+			 */
+			memcpy(cache_value.data, value.data, value.length);
+			e->valuelength = value.length;
+			return;
+		}
+
+		memcache_delete_element(cache, e);
+	}
+
+	element_size = memcache_element_size(key.length, value.length);
+
+
+	e = (struct memcache_element *)SMB_MALLOC(element_size);
+
+	if (e == NULL) {
+		DEBUG(0, ("malloc failed\n"));
+		return;
+	}
+
+	e->n = n;
+	e->keylength = key.length;
+	e->valuelength = value.length;
+
+	memcache_element_parse(e, &cache_key, &cache_value);
+	memcpy(cache_key.data, key.data, key.length);
+	memcpy(cache_value.data, value.data, value.length);
+
+	parent = NULL;
+	p = &cache->tree.rb_node;
+
+	while (*p) {
+		struct memcache_element *elem = memcache_node2elem(*p);
+		int cmp;
+
+		parent = (*p);
+
+		cmp = memcache_compare(elem, n, key);
+
+		p = (cmp < 0) ? &(*p)->rb_left : &(*p)->rb_right;
+	}
+
+	rb_link_node(&e->rb_node, parent, p);
+	rb_insert_color(&e->rb_node, &cache->tree);
+
+	DLIST_ADD(cache->mru, e);
+	if (cache->lru == NULL) {
+		cache->lru = e;
+	}
+
+	cache->size += element_size;
+	memcache_trim(cache);
+}
+
+void memcache_flush(struct memcache *cache, enum memcache_number n)
+{
+	struct rb_node *node;
+
+	/*
+	 * Find the smallest element of number n
+	 */
+
+	node = cache->tree.rb_node;
+	if (node == NULL) {
+		return;
+	}
+
+	while (true) {
+		struct memcache_element *elem = memcache_node2elem(node);
+		struct rb_node *next;
+
+		if ((int)elem->n < (int)n) {
+			next = node->rb_right;
+		}
+		else {
+			next = node->rb_left;
+		}
+		if (next == NULL) {
+			break;
+		}
+		node = next;
+	}
+
+	node = rb_next(node);
+	if (node == NULL) {
+		return;
+	}
+
+	while (node != NULL) {
+		struct memcache_element *e = memcache_node2elem(node);
+		struct rb_node *next = rb_next(node);
+
+		memcache_delete_element(cache, e);
+		node = next;
+	}
+}
diff --git a/source3/param/loadparm.c b/source3/param/loadparm.c
index 881bcece7c..eea3ecec2b 100644
--- a/source3/param/loadparm.c
+++ b/source3/param/loadparm.c
@@ -88,8 +88,6 @@ static bool include_registry_globals = False;
 #define USERSHARE_VALID 1
 #define USERSHARE_PENDING_DELETE 2
 
-bool use_getwd_cache = True;
-
 extern int extra_time_offset;
 
 static bool defaults_saved = False;
@@ -215,6 +213,7 @@ typedef struct {
 	int pwordlevel;
 	int unamelevel;
 	int deadtime;
+	bool getwd_cache;
 	int maxprotocol;
 	int minprotocol;
 	int security;
@@ -1037,7 +1036,7 @@ static struct parm_struct parm_table[] = {
 
 	{"block size", P_INTEGER, P_LOCAL, &sDefault.iBlock_size, NULL, NULL, FLAG_ADVANCED | FLAG_SHARE | FLAG_GLOBAL}, 
 	{"deadtime", P_INTEGER, P_GLOBAL, &Globals.deadtime, NULL, NULL, FLAG_ADVANCED}, 
-	{"getwd cache", P_BOOL, P_GLOBAL, &use_getwd_cache, NULL, NULL, FLAG_ADVANCED}, 
+	{"getwd cache", P_BOOL, P_GLOBAL, &Globals.getwd_cache, NULL, NULL, FLAG_ADVANCED},
 	{"keepalive", P_INTEGER, P_GLOBAL, &Globals.iKeepalive, NULL, NULL, FLAG_ADVANCED},
 	{"change notify", P_BOOL, P_LOCAL, &sDefault.bChangeNotify, NULL, NULL, FLAG_ADVANCED | FLAG_SHARE },
 	{"directory name cache size", P_INTEGER, P_LOCAL, &sDefault.iDirectoryNameCacheSize, NULL, NULL, FLAG_ADVANCED | FLAG_SHARE },
@@ -1535,6 +1534,7 @@ static void init_globals(bool first_time_only)
 	Globals.pwordlevel = 0;
 	Globals.unamelevel = 0;
 	Globals.deadtime = 0;
+	Globals.getwd_cache = true;
 	Globals.bLargeReadwrite = True;
 	Globals.max_log_size = 5000;
 	Globals.max_open_files = MAX_OPEN_FILES;
@@ -2023,6 +2023,7 @@ FN_GLOBAL_INTEGER(lp_maxmux, &Globals.max_mux)
 FN_GLOBAL_INTEGER(lp_passwordlevel, &Globals.pwordlevel)
 FN_GLOBAL_INTEGER(lp_usernamelevel, &Globals.unamelevel)
 FN_GLOBAL_INTEGER(lp_deadtime, &Globals.deadtime)
+FN_GLOBAL_BOOL(lp_getwd_cache, &Globals.getwd_cache)
 FN_GLOBAL_INTEGER(lp_maxprotocol, &Globals.maxprotocol)
 FN_GLOBAL_INTEGER(lp_minprotocol, &Globals.minprotocol)
 FN_GLOBAL_INTEGER(lp_security, &Globals.security)
diff --git a/source3/smbd/mangle_hash2.c b/source3/smbd/mangle_hash2.c
index 7066c2a4e5..9643506aea 100644
--- a/source3/smbd/mangle_hash2.c
+++ b/source3/smbd/mangle_hash2.c
@@ -93,15 +93,6 @@ static unsigned char char_flags[256];
 */
 static unsigned mangle_prefix;
 
-/* we will use a very simple direct mapped prefix cache. The big
-   advantage of this cache structure is speed and low memory usage 
-
-   The cache is indexed by the low-order bits of the hash, and confirmed by
-   hashing the resulting cache entry to match the known hash
-*/
-static char **prefix_cache;
-static unsigned int *prefix_cache_hashes;
-
 /* these are the characters we use in the 8.3 hash. Must be 36 chars long */
 static const char *basechars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 static unsigned char base_reverse[256];
@@ -147,57 +138,39 @@ static unsigned int mangle_hash(const char *key, unsigned int length)
 	return value & ~0x80000000;  
 }
 
-/* 
-   initialise (ie. allocate) the prefix cache
- */
-static bool cache_init(void)
-{
-	if (prefix_cache) {
-		return True;
-	}
-
-	prefix_cache = SMB_CALLOC_ARRAY(char *,MANGLE_CACHE_SIZE);
-	if (!prefix_cache) {
-		return False;
-	}
-
-	prefix_cache_hashes = SMB_CALLOC_ARRAY(unsigned int, MANGLE_CACHE_SIZE);
-	if (!prefix_cache_hashes) {
-		SAFE_FREE(prefix_cache);
-		return False;
-	}
-
-	return True;
-}
-
 /*
   insert an entry into the prefix cache. The string might not be null
   terminated */
 static void cache_insert(const char *prefix, int length, unsigned int hash)
 {
-	int i = hash % MANGLE_CACHE_SIZE;
+	char *str = SMB_STRNDUP(prefix, length);
 
-	if (prefix_cache[i]) {
-		free(prefix_cache[i]);
+	if (str == NULL) {
+		return;
 	}
 
-	prefix_cache[i] = SMB_STRNDUP(prefix, length);
-	prefix_cache_hashes[i] = hash;
+	memcache_add(smbd_memcache(), MANGLE_HASH2_CACHE,
+		     data_blob_const(&hash, sizeof(hash)),
+		     data_blob_const(str, length+1));
+	SAFE_FREE(str);
 }
 
 /*
   lookup an entry in the prefix cache. Return NULL if not found.
 */
-static const char *cache_lookup(unsigned int hash)
+static char *cache_lookup(TALLOC_CTX *mem_ctx, unsigned int hash)
 {
-	int i = hash % MANGLE_CACHE_SIZE;
+	DATA_BLOB value;
 
-	if (!prefix_cache[i] || hash != prefix_cache_hashes[i]) {
+	if (!memcache_lookup(smbd_memcache(), MANGLE_HASH2_CACHE,
+			     data_blob_const(&hash, sizeof(hash)), &value)) {
 		return NULL;
 	}
 
-	/* yep, it matched */
-	return prefix_cache[i];
+	SMB_ASSERT((value.length > 0)
+		   && (value.data[value.length-1] == '\0'));
+
+	return talloc_strdup(mem_ctx, (char *)value.data);
 }
 
 
@@ -377,7 +350,7 @@ static bool lookup_name_from_8_3(TALLOC_CTX *ctx,
 {
 	unsigned int hash, multiplier;
 	unsigned int i;
-	const char *prefix;
+	char *prefix;
 	char extension[4];
 
 	*pp_out = NULL;
@@ -397,7 +370,7 @@ static bool lookup_name_from_8_3(TALLOC_CTX *ctx,
 	}
 
 	/* now look in the prefix cache for that hash */
-	prefix = cache_lookup(hash);
+	prefix = cache_lookup(ctx, hash);
 	if (!prefix) {
 		M_DEBUG(10,("lookup_name_from_8_3: %s -> %08X -> not found\n",
 					name, hash));
@@ -421,6 +394,8 @@ static bool lookup_name_from_8_3(TALLOC_CTX *ctx,
 		*pp_out = talloc_strdup(ctx, prefix);
 	}
 
+	TALLOC_FREE(prefix);
+
 	if (!pp_out) {
 		M_DEBUG(0,("talloc_fail"));
 		return False;
@@ -728,10 +703,6 @@ struct mangle_fns *mangle_hash2_init(void)
 	init_tables();
 	mangle_reset();
 
-	if (!cache_init()) {
-		return NULL;
-	}
-
 	return &mangle_fns;
 }
 
diff --git a/source3/smbd/server.c b/source3/smbd/server.c
index 41d036a8b9..574197d711 100644
--- a/source3/smbd/server.c
+++ b/source3/smbd/server.c
@@ -86,6 +86,19 @@ struct messaging_context *smbd_messaging_context(void)
 	return ctx;
 }
 
+struct memcache *smbd_memcache(void)
+{
+	static struct memcache *cache;
+
+	if (!cache
+	    && !(cache = memcache_init(NULL,
+				       lp_max_stat_cache_size()*1024))) {
+
+		smb_panic("Could not init smbd memcache");
+	}
+	return cache;
+}
+
 /*******************************************************************
  What to do when smb.conf is updated.
  ********************************************************************/
diff --git a/source3/smbd/statcache.c b/source3/smbd/statcache.c
index 8f1e008985..72fed008a2 100644
--- a/source3/smbd/statcache.c
+++ b/source3/smbd/statcache.c
@@ -26,8 +26,6 @@
  Stat cache code used in unix_convert.
 *****************************************************************************/
 
-static TDB_CONTEXT *tdb_stat_cache;
-
 /**
  * Add an entry into the stat cache.
  *
@@ -45,10 +43,8 @@ void stat_cache_add( const char *full_orig_name,
 		bool case_sensitive)
 {
 	size_t translated_path_length;
-	TDB_DATA data_val;
 	char *original_path;
 	size_t original_path_length;
-	size_t sc_size = lp_max_stat_cache_size();
 	char saved_char;
 	TALLOC_CTX *ctx = talloc_tos();
 
@@ -56,12 +52,6 @@ void stat_cache_add( const char *full_orig_name,
 		return;
 	}
 
-	if (sc_size && (tdb_map_size(tdb_stat_cache) > sc_size*1024)) {
-		reset_stat_cache();
-	}
-
-	ZERO_STRUCT(data_val);
-
 	/*
 	 * Don't cache trivial valid directory entries such as . and ..
 	 */
@@ -132,24 +122,20 @@ void stat_cache_add( const char *full_orig_name,
 	saved_char = translated_path[translated_path_length];
 	translated_path[translated_path_length] = '\0';
 
-	data_val.dsize = translated_path_length + 1;
-	data_val.dptr = (uint8 *)translated_path;
-
 	/*
 	 * New entry or replace old entry.
 	 */
 
-	if (tdb_store_bystring(tdb_stat_cache, original_path, data_val,
-				TDB_REPLACE) != 0) {
-		DEBUG(0,("stat_cache_add: Error storing entry %s -> %s\n",
-					original_path, translated_path));
-	} else {
-		DEBUG(5,("stat_cache_add: Added entry (%lx:size%x) %s -> %s\n",
-			(unsigned long)data_val.dptr,
-			(unsigned int)data_val.dsize,
-			original_path,
-			translated_path));
-	}
+	memcache_add(
+		smbd_memcache(), STAT_CACHE,
+		data_blob_const(original_path, original_path_length),
+		data_blob_const(translated_path, translated_path_length + 1));
+
+	DEBUG(5,("stat_cache_add: Added entry (%lx:size %x) %s -> %s\n",
+		 (unsigned long)translated_path,
+		 (unsigned int)translated_path_length,
+		 original_path,
+		 translated_path));
 
 	translated_path[translated_path_length] = saved_char;
 	TALLOC_FREE(original_path);
@@ -186,7 +172,7 @@ bool stat_cache_lookup(connection_struct *conn,
 	unsigned int num_components = 0;
 	char *translated_path;
 	size_t translated_path_length;
-	TDB_DATA data_val;
+	DATA_BLOB data_val;
 	char *name;
 	TALLOC_CTX *ctx = talloc_tos();
 
@@ -236,9 +222,12 @@ bool stat_cache_lookup(connection_struct *conn,
 	while (1) {
 		char *sp;
 
-		data_val = tdb_fetch_bystring(tdb_stat_cache, chk_name);
+		data_val = data_blob_null;
 
-		if (data_val.dptr != NULL && data_val.dsize != 0) {
+		if (memcache_lookup(
+			    smbd_memcache(), STAT_CACHE,
+			    data_blob_const(chk_name, strlen(chk_name)),
+			    &data_val)) {
 			break;
 		}
 
@@ -275,12 +264,11 @@ bool stat_cache_lookup(connection_struct *conn,
 		}
 	}
 
-	translated_path = talloc_strdup(ctx,(char *)data_val.dptr);
+	translated_path = talloc_strdup(ctx,(char *)data_val.data);
 	if (!translated_path) {
 		smb_panic("talloc failed");
 	}
-	translated_path_length = data_val.dsize - 1;
-	SAFE_FREE(data_val.dptr);
+	translated_path_length = data_val.length - 1;
 
 	DEBUG(10,("stat_cache_lookup: lookup succeeded for name [%s] "
 		  "-> [%s]\n", chk_name, translated_path ));
@@ -288,7 +276,8 @@ bool stat_cache_lookup(connection_struct *conn,
 
 	if (SMB_VFS_STAT(conn, translated_path, pst) != 0) {
 		/* Discard this entry - it doesn't exist in the filesystem. */
-		tdb_delete_bystring(tdb_stat_cache, chk_name);
+		memcache_delete(smbd_memcache(), STAT_CACHE,
+				data_blob_const(chk_name, strlen(chk_name)));
 		TALLOC_FREE(chk_name);
 		TALLOC_FREE(translated_path);
 		return False;
@@ -366,7 +355,8 @@ void stat_cache_delete(const char *name)
 	DEBUG(10,("stat_cache_delete: deleting name [%s] -> %s\n",
 			lname, name ));
 
-	tdb_delete_bystring(tdb_stat_cache, lname);
+	memcache_delete(smbd_memcache(), STAT_CACHE,
+			data_blob_const(lname, talloc_get_size(lname)-1));
 	TALLOC_FREE(lname);
 }
 
@@ -395,15 +385,7 @@ bool reset_stat_cache( void )
 	if (!lp_stat_cache())
 		return True;
 
-	if (tdb_stat_cache) {
-		tdb_close(tdb_stat_cache);
-	}
+	memcache_flush(smbd_memcache(), STAT_CACHE);
 
-	/* Create the in-memory tdb using our custom hash function. */
-	tdb_stat_cache = tdb_open_ex("statcache", 1031, TDB_INTERNAL,
-				(O_RDWR|O_CREAT), 0644, NULL, fast_string_hash);
-
-	if (!tdb_stat_cache)
-		return False;
 	return True;
 }
diff --git a/source3/smbd/vfs.c b/source3/smbd/vfs.c
index 628d2eec4b..45d0788117 100644
--- a/source3/smbd/vfs.c
+++ b/source3/smbd/vfs.c
@@ -731,152 +731,98 @@ int vfs_ChDir(connection_struct *conn, const char *path)
 	return(res);
 }
 
-/* number of list structures for a caching GetWd function. */
-#define MAX_GETWDCACHE (50)
-
-static struct {
-	SMB_DEV_T dev; /* These *must* be compatible with the types returned in a stat() call. */
-	SMB_INO_T inode; /* These *must* be compatible with the types returned in a stat() call. */
-	char *path; /* The pathname. */
-	bool valid;
-} ino_list[MAX_GETWDCACHE];
-
-extern bool use_getwd_cache;
-
-/****************************************************************************
- Prompte a ptr (to make it recently used)
-****************************************************************************/
-
-static void array_promote(char *array,int elsize,int element)
-{
-	char *p;
-	if (element == 0)
-		return;
-
-	p = (char *)SMB_MALLOC(elsize);
-
-	if (!p) {
-		DEBUG(5,("array_promote: malloc fail\n"));
-		return;
-	}
-
-	memcpy(p,array + element * elsize, elsize);
-	memmove(array + elsize,array,elsize*element);
-	memcpy(array,p,elsize);
-	SAFE_FREE(p);
-}
-
 /*******************************************************************
  Return the absolute current directory path - given a UNIX pathname.
  Note that this path is returned in DOS format, not UNIX
  format. Note this can be called with conn == NULL.
 ********************************************************************/
 
+struct getwd_cache_key {
+	SMB_DEV_T dev;
+	SMB_INO_T ino;
+};
+
 char *vfs_GetWd(TALLOC_CTX *ctx, connection_struct *conn)
 {
         char s[PATH_MAX+1];
-	static bool getwd_cache_init = False;
 	SMB_STRUCT_STAT st, st2;
-	int i;
-	char *ret = NULL;
+	char *result;
+	DATA_BLOB cache_value;
+	struct getwd_cache_key key;
 
 	*s = 0;
 
-	if (!use_getwd_cache) {
- nocache:
-		ret = SMB_VFS_GETWD(conn,s);
-		if (!ret) {
-			DEBUG(0,("vfs_GetWd: SMB_VFS_GETWD call failed, "
-				"errno %s\n",strerror(errno)));
-			return NULL;
-		}
-		return talloc_strdup(ctx, ret);
-	}
-
-	/* init the cache */
-	if (!getwd_cache_init) {
-		getwd_cache_init = True;
-		for (i=0;i<MAX_GETWDCACHE;i++) {
-			string_set(&ino_list[i].path,"");
-			ino_list[i].valid = False;
-		}
+	if (!lp_getwd_cache()) {
+		goto nocache;
 	}
 
-	/*  Get the inode of the current directory, if this doesn't work we're
-		in trouble :-) */
+	SET_STAT_INVALID(st);
 
 	if (SMB_VFS_STAT(conn, ".",&st) == -1) {
-		/* Known to fail for root: the directory may be
-		 * NFS-mounted and exported with root_squash (so has no root access). */
+		/*
+		 * Known to fail for root: the directory may be NFS-mounted
+		 * and exported with root_squash (so has no root access).
+		 */
 		DEBUG(1,("vfs_GetWd: couldn't stat \".\" error %s "
-			"(NFS problem ?)\n",
-			strerror(errno) ));
+			 "(NFS problem ?)\n", strerror(errno) ));
 		goto nocache;
 	}
 
+	ZERO_STRUCT(key); /* unlikely, but possible padding */
+	key.dev = st.st_dev;
+	key.ino = st.st_ino;
 
-	for (i=0; i<MAX_GETWDCACHE; i++) {
-		if (ino_list[i].valid) {
-
-			/*  If we have found an entry with a matching inode and dev number
-				then find the inode number for the directory in the cached string.
-				If this agrees with that returned by the stat for the current
-				directory then all is o.k. (but make sure it is a directory all
-				the same...) */
-
-			if (st.st_ino == ino_list[i].inode && st.st_dev == ino_list[i].dev) {
-				if (SMB_VFS_STAT(conn,ino_list[i].path,&st2) == 0) {
-					if (st.st_ino == st2.st_ino && st.st_dev == st2.st_dev &&
-							(st2.st_mode & S_IFMT) == S_IFDIR) {
+	if (!memcache_lookup(smbd_memcache(), GETWD_CACHE,
+			     data_blob_const(&key, sizeof(key)),
+			     &cache_value)) {
+		goto nocache;
+	}
 
-						ret = talloc_strdup(ctx,
-							ino_list[i].path);
+	SMB_ASSERT((cache_value.length > 0)
+		   && (cache_value.data[cache_value.length-1] == '\0'));
 
-						/* promote it for future use */
-						array_promote((char *)&ino_list[0],sizeof(ino_list[0]),i);
-						if (ret == NULL) {
-							errno = ENOMEM;
-						}
-						return ret;
-					} else {
-						/*  If the inode is different then something's changed,
-							scrub the entry and start from scratch. */
-						ino_list[i].valid = False;
-					}
-				}
-			}
+	if ((SMB_VFS_STAT(conn, (char *)cache_value.data, &st2) == 0)
+	    && (st.st_dev == st2.st_dev) && (st.st_ino == st2.st_ino)
+	    && (S_ISDIR(st.st_mode))) {
+		/*
+		 * Ok, we're done
+		 */
+		result = talloc_strdup(ctx, (char *)cache_value.data);
+		if (result == NULL) {
+			errno = ENOMEM;
 		}
+		return result;
 	}
 
-	/*  We don't have the information to hand so rely on traditional
-	 *  methods. The very slow getcwd, which spawns a process on some
-	 *  systems, or the not quite so bad getwd. */
+ nocache:
+
+	/*
+	 * We don't have the information to hand so rely on traditional
+	 * methods. The very slow getcwd, which spawns a process on some
+	 * systems, or the not quite so bad getwd.
+	 */
 
 	if (!SMB_VFS_GETWD(conn,s)) {
-		DEBUG(0,("vfs_GetWd: SMB_VFS_GETWD call failed, errno %s\n",
-				strerror(errno)));
-		return (NULL);
+		DEBUG(0, ("vfs_GetWd: SMB_VFS_GETWD call failed: %s\n",
+			  strerror(errno)));
+		return NULL;
 	}
 
-	ret = talloc_strdup(ctx,s);
-
-	DEBUG(5,("vfs_GetWd %s, inode %.0f, dev %.0f\n",
-				s,(double)st.st_ino,(double)st.st_dev));
-
-	/* add it to the cache */
-	i = MAX_GETWDCACHE - 1;
-	string_set(&ino_list[i].path,s);
-	ino_list[i].dev = st.st_dev;
-	ino_list[i].inode = st.st_ino;
-	ino_list[i].valid = True;
+	if (lp_getwd_cache() && VALID_STAT(st)) {
+		ZERO_STRUCT(key); /* unlikely, but possible padding */
+		key.dev = st.st_dev;
+		key.ino = st.st_ino;
 
-	/* put it at the top of the list */
-	array_promote((char *)&ino_list[0],sizeof(ino_list[0]),i);
+		memcache_add(smbd_memcache(), GETWD_CACHE,
+			     data_blob_const(&key, sizeof(key)),
+			     data_blob_const(s, strlen(s)+1));
+	}
 
-	if (ret == NULL) {
+	result = talloc_strdup(ctx, s);
+	if (result == NULL) {
 		errno = ENOMEM;
 	}
-	return ret;
+	return result;
 }
 
 /*******************************************************************
diff --git a/source3/torture/torture.c b/source3/torture/torture.c
index ad57470c61..082949e0af 100644
--- a/source3/torture/torture.c
+++ b/source3/torture/torture.c
@@ -5042,6 +5042,81 @@ static bool run_local_rbtree(int dummy)
 	return ret;
 }
 
+static bool data_blob_equal(DATA_BLOB a, DATA_BLOB b)
+{
+	if (a.length != b.length) {
+		printf("a.length=%d != b.length=%d\n",
+		       (int)a.length, (int)b.length);
+		return false;
+	}
+	if (memcmp(a.data, b.data, a.length) != 0) {
+		printf("a.data and b.data differ\n");
+		return false;
+	}
+	return true;
+}
+
+static bool run_local_memcache(int dummy)
+{
+	struct memcache *cache;
+	DATA_BLOB k1, k2;
+	DATA_BLOB d1, d2, d3;
+	DATA_BLOB v1, v2, v3;
+
+	cache = memcache_init(NULL, 100);
+
+	if (cache == NULL) {
+		printf("memcache_init failed\n");
+		return false;
+	}
+
+	d1 = data_blob_const("d1", 2);
+	d2 = data_blob_const("d2", 2);
+	d3 = data_blob_const("d3", 2);
+
+	k1 = data_blob_const("d1", 2);
+	k2 = data_blob_const("d2", 2);
+
+	memcache_add(cache, STAT_CACHE, k1, d1);
+	memcache_add(cache, GETWD_CACHE, k2, d2);
+
+	if (!memcache_lookup(cache, STAT_CACHE, k1, &v1)) {
+		printf("could not find k1\n");
+		return false;
+	}
+	if (!data_blob_equal(d1, v1)) {
+		return false;
+	}
+
+	if (!memcache_lookup(cache, GETWD_CACHE, k2, &v2)) {
+		printf("could not find k2\n");
+		return false;
+	}
+	if (!data_blob_equal(d2, v2)) {
+		return false;
+	}
+
+	memcache_add(cache, STAT_CACHE, k1, d3);
+
+	if (!memcache_lookup(cache, STAT_CACHE, k1, &v3)) {
+		printf("could not find replaced k1\n");
+		return false;
+	}
+	if (!data_blob_equal(d3, v3)) {
+		return false;
+	}
+
+	memcache_add(cache, GETWD_CACHE, k1, d1);
+
+	if (memcache_lookup(cache, GETWD_CACHE, k2, &v2)) {
+		printf("Did find k2, should have been purged\n");
+		return false;
+	}
+
+	TALLOC_FREE(cache);
+	return true;
+}
+
 static double create_procs(bool (*fn)(int), bool *result)
 {
 	int i, status;
@@ -5196,6 +5271,7 @@ static struct {
 	{ "LOCAL-SUBSTITUTE", run_local_substitute, 0},
 	{ "LOCAL-GENCACHE", run_local_gencache, 0},
 	{ "LOCAL-RBTREE", run_local_rbtree, 0},
+	{ "LOCAL-MEMCACHE", run_local_memcache, 0},
 	{NULL, NULL, 0}};
 
 
diff --git a/source3/torture/vfstest.c b/source3/torture/vfstest.c
index 1436ecc022..7e4ee624a1 100644
--- a/source3/torture/vfstest.c
+++ b/source3/torture/vfstest.c
@@ -495,6 +495,19 @@ struct messaging_context *smbd_messaging_context(void)
 	return ctx;
 }
 
+struct memcache *smbd_memcache(void)
+{
+	static struct memcache *cache;
+
+	if (!cache
+	    && !(cache = memcache_init(NULL,
+				       lp_max_stat_cache_size()*1024))) {
+
+		smb_panic("Could not init smbd memcache");
+	}
+	return cache;
+}
+
 /* Main function */
 
 int main(int argc, char *argv[])