* [Patch 3/4] chunkd: add objcache
@ 2009-12-27 23:59 Pete Zaitcev
2010-01-07 5:16 ` [Patch 5/4] chunkd: switch objcache to hash Pete Zaitcev
0 siblings, 1 reply; 2+ messages in thread
From: Pete Zaitcev @ 2009-12-27 23:59 UTC (permalink / raw)
To: Jeff Garzik; +Cc: Project Hail List
This a mechanism by which self-check may know what objects were updated
and thus should not be disturbed if their checksums fail.
Signed-off-by: Pete Zaitcev <zaitcev@redhat.com>
---
include/Makefile.am | 2
include/objcache.h | 72 +++++++++++++++++++++++
server/Makefile.am | 3
server/chunkd.h | 3
server/objcache.c | 128 +++++++++++++++++++++++++++++++++++++++++
server/object.c | 9 ++
server/server.c | 7 ++
test/.gitignore | 1
test/Makefile.am | 5 +
test/objcache-unit.c | 58 ++++++++++++++++++
10 files changed, 285 insertions(+), 3 deletions(-)
commit ab575b65211f00c73feffd4c8c58044142b1163f
Author: Master <zaitcev@lembas.zaitcev.lan>
Date: Sun Dec 27 16:04:43 2009 -0700
Add the objcache.
diff --git a/include/Makefile.am b/include/Makefile.am
index ddc2b8a..7abe0b5 100644
--- a/include/Makefile.am
+++ b/include/Makefile.am
@@ -1,5 +1,5 @@
include_HEADERS = chunkc.h chunk_msg.h
-EXTRA_DIST = elist.h chunk_msg.h chunksrv.h chunk-private.h
+EXTRA_DIST = elist.h chunk_msg.h chunksrv.h chunk-private.h objcache.h
diff --git a/include/objcache.h b/include/objcache.h
new file mode 100644
index 0000000..fce1485
--- /dev/null
+++ b/include/objcache.h
@@ -0,0 +1,72 @@
+
+/*
+ * Copyright 2009 Red Hat, Inc.
+ *
+ * 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.
+ *
+ * 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; see the file COPYING. If not, write to
+ * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+#ifndef _CHUNKD_OBJCACHE_H_
+#define _CHUNKD_OBJCACHE_H_
+
+#include <glib.h>
+#include <elist.h>
+#include <stdbool.h>
+
+struct objcache {
+ struct list_head head;
+ GMutex *lock;
+};
+
+struct objcache_entry {
+ struct list_head link;
+ unsigned int hash;
+ unsigned int flags;
+ int ref;
+};
+
+#define OC_F_DIRTY 0x1
+
+/*
+ * Get an entry and set flags.
+ * A method for every flag is needed because our locks are internal to
+ * the cache, and we want this to be atomic.
+ */
+#define objcache_get(c, k, l) __objcache_get(c, k, l, 0)
+#define objcache_get_dirty(c, k, l) __objcache_get(c, k, l, OC_F_DIRTY)
+extern struct objcache_entry *__objcache_get(struct objcache *cache,
+ const char *key, int klen,
+ unsigned int flag);
+
+/*
+ * Test for dirty.
+ */
+extern bool objcache_test_dirty(struct objcache *cache,
+ struct objcache_entry *entry);
+
+/*
+ * Put an entry (decrement and free, or an equivalent).
+ */
+extern void objcache_put(struct objcache *cache, struct objcache_entry *entry);
+
+/*
+ * Init a cache. Call once. May fail since it allocates a mutex.
+ */
+extern int objcache_init(struct objcache *cache);
+
+/*
+ * Terminate a cache.
+ */
+extern void objcache_fini(struct objcache *cache);
+
+#endif
diff --git a/server/Makefile.am b/server/Makefile.am
index 516b081..824c0b3 100644
--- a/server/Makefile.am
+++ b/server/Makefile.am
@@ -6,7 +6,8 @@ sbin_PROGRAMS = chunkd
chunkd_SOURCES = chunkd.h \
../lib/chunksrv.c \
- be-fs.c object.c server.c config.c cldu.c util.c
+ be-fs.c object.c server.c config.c cldu.c util.c \
+ objcache.c
chunkd_LDADD = \
@CLDC_LIBS@ @GLIB_LIBS@ @CRYPTO_LIBS@ \
@SSL_LIBS@ @EVENT_LIBS@ @TOKYOCABINET_LIBS@
diff --git a/server/chunkd.h b/server/chunkd.h
index a97088d..18dd31a 100644
--- a/server/chunkd.h
+++ b/server/chunkd.h
@@ -28,6 +28,7 @@
#include <chunk_msg.h>
#include <hail_log.h>
#include <tchdb.h>
+#include <objcache.h>
#ifndef ARRAY_SIZE
#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
@@ -118,6 +119,7 @@ struct client {
long out_len;
struct backend_obj *out_bo;
+ struct objcache_entry *out_ce;
long in_len;
struct backend_obj *in_obj;
@@ -210,6 +212,7 @@ struct server {
struct geo loc;
TCHDB *tbl_master;
+ struct objcache actives;
struct server_stats stats; /* global statistics */
};
diff --git a/server/objcache.c b/server/objcache.c
new file mode 100644
index 0000000..475ac23
--- /dev/null
+++ b/server/objcache.c
@@ -0,0 +1,128 @@
+
+/*
+ * Copyright 2009 Red Hat, Inc.
+ *
+ * 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.
+ *
+ * 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; see the file COPYING. If not, write to
+ * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+
+#include <objcache.h>
+#include <stdlib.h>
+
+/*
+ * We really should not screw around with hand-rolled garbage and use
+ * something like Paul Hsieh's SuperFastHash, but licenses are too confusing.
+ */
+static unsigned int objcache_hash(const char *key, int klen)
+{
+ unsigned int hash;
+ int i;
+ unsigned char c;
+
+ hash = 0x55555555;
+ for (i = 0; i < klen; i++) {
+ c = (unsigned char) *key++;
+ hash ^= hash << 16;
+ hash ^= c;
+ hash = (hash << 8) | (hash >> 24);
+ }
+ return hash;
+}
+
+static struct objcache_entry *objcache_lookup(struct objcache *cache,
+ unsigned int hash)
+{
+ struct objcache_entry *cep;
+
+ list_for_each_entry(cep, &cache->head, link) {
+ if (cep->hash == hash)
+ return cep;
+ }
+ return NULL;
+}
+
+static struct objcache_entry *objcache_insert(struct objcache *cache,
+ unsigned int hash)
+{
+ struct objcache_entry *cep;
+
+ cep = malloc(sizeof(struct objcache_entry));
+ if (!cep)
+ return NULL;
+ cep->hash = hash;
+ cep->flags = 0;
+ cep->ref = 1;
+ list_add(&cep->link, &cache->head);
+ return cep;
+}
+
+struct objcache_entry *__objcache_get(struct objcache *cache,
+ const char *key, int klen,
+ unsigned int flag)
+{
+ struct objcache_entry *cep;
+ unsigned int hash;
+
+ hash = objcache_hash(key, klen);
+ g_mutex_lock(cache->lock);
+ cep = objcache_lookup(cache, hash);
+ if (cep) {
+ cep->ref++;
+ } else {
+ cep = objcache_insert(cache, hash);
+ }
+ cep->flags |= flag;
+ g_mutex_unlock(cache->lock);
+ return cep;
+}
+
+bool objcache_test_dirty(struct objcache *cache, struct objcache_entry *cep)
+{
+ bool ret;
+
+ g_mutex_lock(cache->lock);
+ ret = cep->flags & OC_F_DIRTY;
+ g_mutex_unlock(cache->lock);
+ return ret;
+}
+
+void objcache_put(struct objcache *cache, struct objcache_entry *cep)
+{
+ g_mutex_lock(cache->lock);
+ if (!cep->ref) {
+ g_mutex_unlock(cache->lock);
+ /* Must not happen, or a leak for Valgrind to catch. */
+ return;
+ }
+ --cep->ref;
+ if (!cep->ref) {
+ list_del(&cep->link);
+ free(cep);
+ }
+ g_mutex_unlock(cache->lock);
+}
+
+int objcache_init(struct objcache *cache)
+{
+ cache->lock = g_mutex_new();
+ if (!cache->lock)
+ return -1;
+ INIT_LIST_HEAD(&cache->head);
+ return 0;
+}
+
+void objcache_fini(struct objcache *cache)
+{
+ g_mutex_free(cache->lock);
+}
diff --git a/server/object.c b/server/object.c
index a1205f5..5cc596a 100644
--- a/server/object.c
+++ b/server/object.c
@@ -73,6 +73,10 @@ void cli_out_end(struct client *cli)
fs_obj_free(cli->out_bo);
cli->out_bo = NULL;
}
+ if (cli->out_ce) {
+ objcache_put(&chunkd_srv.actives, cli->out_ce);
+ cli->out_ce = NULL;
+ }
free(cli->out_user);
cli->out_user = NULL;
@@ -217,6 +221,11 @@ bool object_put(struct client *cli)
if (!user)
return cli_err(cli, che_AccessDenied, true);
+ cli->out_ce = objcache_get_dirty(&chunkd_srv.actives,
+ cli->key, cli->key_len);
+ if (!cli->out_ce)
+ return cli_err(cli, che_InternalError, true);
+
cli->out_bo = fs_obj_new(cli->table_id, cli->key, cli->key_len, &err);
if (!cli->out_bo)
return cli_err(cli, err, true);
diff --git a/server/server.c b/server/server.c
index 3f38cca..e955dc8 100644
--- a/server/server.c
+++ b/server/server.c
@@ -1659,6 +1659,11 @@ int main (int argc, char *argv[])
goto err_out_session;
}
+ if (objcache_init(&chunkd_srv.actives) != 0) {
+ rc = 1;
+ goto err_out_objcache;
+ }
+
INIT_LIST_HEAD(&chunkd_srv.wr_trash);
chunkd_srv.trash_sz = 0;
@@ -1692,6 +1697,8 @@ err_out_listen:
err_out_cld:
fs_close();
err_out_fs:
+ objcache_fini(&chunkd_srv.actives);
+err_out_objcache:
if (strict_free)
g_hash_table_destroy(chunkd_srv.fd_info);
err_out_session:
diff --git a/test/.gitignore b/test/.gitignore
index ccb6bdb..a929882 100644
--- a/test/.gitignore
+++ b/test/.gitignore
@@ -4,6 +4,7 @@ it-works
large-object
lotsa-objects
nop
+objcache-unit
.libs
libtest.a
diff --git a/test/Makefile.am b/test/Makefile.am
index d9c10b5..84b4837 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -15,6 +15,7 @@ EXTRA_DIST = \
ssl-key.pem ssl-cert.pem
TESTS = \
+ objcache-unit \
prep-db \
start-daemon \
pid-exists \
@@ -29,7 +30,7 @@ TESTS = \
clean-db
check_PROGRAMS = auth basic-object it-works large-object \
- lotsa-objects nop
+ lotsa-objects nop objcache-unit
TESTLDADD = ../lib/libchunkdc.la \
libtest.a \
@@ -42,6 +43,8 @@ large_object_LDADD = $(TESTLDADD)
lotsa_objects_LDADD = $(TESTLDADD)
nop_LDADD = $(TESTLDADD)
+objcache_unit_LDADD = @GLIB_LIBS@
+
noinst_LIBRARIES = libtest.a
libtest_a_SOURCES = libtest.c
diff --git a/test/objcache-unit.c b/test/objcache-unit.c
new file mode 100644
index 0000000..f101445
--- /dev/null
+++ b/test/objcache-unit.c
@@ -0,0 +1,58 @@
+
+/*
+ * Copyright 2009 Red Hat, Inc.
+ *
+ * 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.
+ *
+ * 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; see the file COPYING. If not, write to
+ * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ */
+
+#include "../server/objcache.c"
+#include "test.h"
+
+int main(int argc, char *argv[])
+{
+ static char k1[] = { 'a' };
+ static char k2[] = { 'a', 'a' };
+ static char k3[] = { 'a', '\0', 'a' };
+ struct objcache cache;
+ struct objcache_entry *ep1, *ep2, *ep3;
+ int rc;
+
+ g_thread_init(NULL);
+ rc = objcache_init(&cache);
+ OK(rc==0);
+
+ ep1 = objcache_get(&cache, k1, sizeof(k1));
+ OK(ep1 != NULL);
+
+ ep2 = objcache_get(&cache, k2, sizeof(k2));
+ OK(ep2 != NULL);
+
+ ep3 = objcache_get(&cache, k3, sizeof(k3));
+ OK(ep3 != NULL);
+
+ OK(ep1->ref == 1); /* no collisions */
+
+ objcache_put(&cache, ep1);
+ objcache_put(&cache, ep2);
+ objcache_put(&cache, ep3);
+
+ ep2 = objcache_get(&cache, k2, sizeof(k2));
+ OK(ep2 != NULL);
+ OK(ep2->ref == 1); /* new */
+ objcache_put(&cache, ep2);
+
+ objcache_fini(&cache);
+ return 0;
+}
^ permalink raw reply related [flat|nested] 2+ messages in thread
* [Patch 5/4] chunkd: switch objcache to hash
2009-12-27 23:59 [Patch 3/4] chunkd: add objcache Pete Zaitcev
@ 2010-01-07 5:16 ` Pete Zaitcev
0 siblings, 0 replies; 2+ messages in thread
From: Pete Zaitcev @ 2010-01-07 5:16 UTC (permalink / raw)
To: Jeff Garzik; +Cc: Pete Zaitcev, Project Hail List
On second thought, let's switch objcache from list to hash. This should
help the lookup times if there's a large number of outstanding I/Os.
This also adds the objcache_count for self-testing purpoes.
And a few comments.
Signed-off-by: Pete Zaitcev <zaitcev@redhat.com>
---
include/objcache.h | 9 +++++---
server/objcache.c | 42 +++++++++++++++++++++++++----------------
test/objcache-unit.c | 8 ++++++-
3 files changed, 39 insertions(+), 20 deletions(-)
I think you mentioned that your scripts dealt with 5/4 patch numbering.
Just in case, setting references by replying to a previous patch mail.
commit 6238aa7321335b0a3aba9736ee1467777bdd6861
Author: Master <zaitcev@lembas.zaitcev.lan>
Date: Wed Jan 6 22:04:20 2010 -0700
Switch objcache from list to hash to make lookups faster.
diff --git a/include/objcache.h b/include/objcache.h
index fce1485..6e36e86 100644
--- a/include/objcache.h
+++ b/include/objcache.h
@@ -20,16 +20,14 @@
#define _CHUNKD_OBJCACHE_H_
#include <glib.h>
-#include <elist.h>
#include <stdbool.h>
struct objcache {
- struct list_head head;
GMutex *lock;
+ GHashTable *table;
};
struct objcache_entry {
- struct list_head link;
unsigned int hash;
unsigned int flags;
int ref;
@@ -60,6 +58,11 @@ extern bool objcache_test_dirty(struct objcache *cache,
extern void objcache_put(struct objcache *cache, struct objcache_entry *entry);
/*
+ * Count objects in the cache. Can be slow, and used only for debugging.
+ */
+extern int objcache_count(struct objcache *cache);
+
+/*
* Init a cache. Call once. May fail since it allocates a mutex.
*/
extern int objcache_init(struct objcache *cache);
diff --git a/server/objcache.c b/server/objcache.c
index 475ac23..e969f89 100644
--- a/server/objcache.c
+++ b/server/objcache.c
@@ -40,18 +40,6 @@ static unsigned int objcache_hash(const char *key, int klen)
return hash;
}
-static struct objcache_entry *objcache_lookup(struct objcache *cache,
- unsigned int hash)
-{
- struct objcache_entry *cep;
-
- list_for_each_entry(cep, &cache->head, link) {
- if (cep->hash == hash)
- return cep;
- }
- return NULL;
-}
-
static struct objcache_entry *objcache_insert(struct objcache *cache,
unsigned int hash)
{
@@ -63,10 +51,18 @@ static struct objcache_entry *objcache_insert(struct objcache *cache,
cep->hash = hash;
cep->flags = 0;
cep->ref = 1;
- list_add(&cep->link, &cache->head);
+ g_hash_table_insert(cache->table, &cep->hash, cep);
return cep;
}
+/*
+ * Observe the way we handle conflicts in the computed hash: we treat the
+ * keys with the same hash as same. It's acceptable in our application.
+ * At worst, an unrelated activity main in chunkd may spook self-check.
+ * This policy remains the same for list, tree, hash or any other implementing
+ * structure. If we use Glib's hash, it can have its own conflicts over
+ * a shared bucket indexed with our hash. We don't know anything about those.
+ */
struct objcache_entry *__objcache_get(struct objcache *cache,
const char *key, int klen,
unsigned int flag)
@@ -76,7 +72,7 @@ struct objcache_entry *__objcache_get(struct objcache *cache,
hash = objcache_hash(key, klen);
g_mutex_lock(cache->lock);
- cep = objcache_lookup(cache, hash);
+ cep = g_hash_table_lookup(cache->table, &hash);
if (cep) {
cep->ref++;
} else {
@@ -107,22 +103,36 @@ void objcache_put(struct objcache *cache, struct objcache_entry *cep)
}
--cep->ref;
if (!cep->ref) {
- list_del(&cep->link);
+ gboolean rcb;
+ rcb = g_hash_table_remove(cache->table, &cep->hash);
+ /*
+ * We are so super sure that this cannot happen that
+ * we use abort(), which is not welcome in daemons.
+ */
+ if (!rcb)
+ abort();
free(cep);
}
g_mutex_unlock(cache->lock);
}
+int objcache_count(struct objcache *cache)
+{
+ return g_hash_table_size(cache->table);
+}
+
int objcache_init(struct objcache *cache)
{
cache->lock = g_mutex_new();
if (!cache->lock)
return -1;
- INIT_LIST_HEAD(&cache->head);
+ /* We do not use g_str_hash becuse our keys may have nul bytes. */
+ cache->table = g_hash_table_new(g_int_hash, g_int_equal);
return 0;
}
void objcache_fini(struct objcache *cache)
{
g_mutex_free(cache->lock);
+ g_hash_table_destroy(cache->table);
}
diff --git a/test/objcache-unit.c b/test/objcache-unit.c
index f101445..874b57d 100644
--- a/test/objcache-unit.c
+++ b/test/objcache-unit.c
@@ -42,7 +42,10 @@ int main(int argc, char *argv[])
ep3 = objcache_get(&cache, k3, sizeof(k3));
OK(ep3 != NULL);
- OK(ep1->ref == 1); /* no collisions */
+ rc = objcache_count(&cache);
+ OK(rc == 3);
+
+ OK(ep1->ref == 1); /* no collisions, else improve hash */
objcache_put(&cache, ep1);
objcache_put(&cache, ep2);
@@ -53,6 +56,9 @@ int main(int argc, char *argv[])
OK(ep2->ref == 1); /* new */
objcache_put(&cache, ep2);
+ rc = objcache_count(&cache);
+ OK(rc == 0);
+
objcache_fini(&cache);
return 0;
}
^ permalink raw reply related [flat|nested] 2+ messages in thread
end of thread, other threads:[~2010-01-07 5:16 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2009-12-27 23:59 [Patch 3/4] chunkd: add objcache Pete Zaitcev
2010-01-07 5:16 ` [Patch 5/4] chunkd: switch objcache to hash Pete Zaitcev
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.