<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">2013/11/29 Liu Yuan <span dir="ltr"><<a href="mailto:namei.unix@gmail.com" target="_blank">namei.unix@gmail.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
This implements a per-vdi allocator for http extent-based container.<br>
<br>
We use meta object tracks the free information of data vdi for the object<br>
allocation in a free list. Free list is a redundant structure for bitmap for<br>
faster allocation.<br>
<br>
future enhancements:<br>
- Add allocation group for scalability and solve the meta size limitation<br>
- use aio to speed up discard of objects<br>
- add range support for inode update<br>
<br>
Signed-off-by: Liu Yuan <<a href="mailto:namei.unix@gmail.com">namei.unix@gmail.com</a>><br>
---<br>
sheep/Makefile.am | 3 +-<br>
sheep/http/http.h | 6 +<br>
sheep/http/oalloc.c | 304 +++++++++++++++++++++++++++++++++++++++++++++++++++<br>
3 files changed, 312 insertions(+), 1 deletion(-)<br>
create mode 100644 sheep/http/oalloc.c<br>
<br>
diff --git a/sheep/Makefile.am b/sheep/Makefile.am<br>
index 552e86a..af1087f 100644<br>
--- a/sheep/Makefile.am<br>
+++ b/sheep/Makefile.am<br>
@@ -30,7 +30,8 @@ sheep_SOURCES = sheep.c group.c request.c gateway.c store.c vdi.c \<br>
plain_store.c config.c migrate.c md.c<br>
<br>
if BUILD_HTTP<br>
-sheep_SOURCES += http/http.c http/kv.c http/s3.c http/swift.c<br>
+sheep_SOURCES += http/http.c http/kv.c http/s3.c http/swift.c \<br>
+ http/oalloc.c<br>
endif<br>
if BUILD_COROSYNC<br>
sheep_SOURCES += cluster/corosync.c<br>
diff --git a/sheep/http/http.h b/sheep/http/http.h<br>
index 495a66c..046d412 100644<br>
--- a/sheep/http/http.h<br>
+++ b/sheep/http/http.h<br>
@@ -108,4 +108,10 @@ int http_request_writes(struct http_request *req, const char *str);<br>
__printf(2, 3)<br>
int http_request_writef(struct http_request *req, const char *fmt, ...);<br>
<br>
+/* object_allocator.c */<br>
+int oalloc_new_prepare(uint32_t vid, uint64_t *start, uint64_t count);<br>
+int oalloc_new_finish(uint32_t vid, uint64_t start, uint64_t count);<br>
+int oalloc_free(uint32_t vid, uint64_t start, uint64_t count);<br>
+int oalloc_init(uint32_t vid);<br>
+<br>
#endif /* __SHEEP_HTTP_H__ */<br>
diff --git a/sheep/http/oalloc.c b/sheep/http/oalloc.c<br>
new file mode 100644<br>
index 0000000..dc6be68<br>
--- /dev/null<br>
+++ b/sheep/http/oalloc.c<br>
@@ -0,0 +1,304 @@<br>
+/*<br>
+ * Copyright (C) 2013 Taobao Inc.<br>
+ *<br>
+ * Liu Yuan <<a href="mailto:namei.unix@gmail.com">namei.unix@gmail.com</a>><br>
+ *<br>
+ * This program is free software; you can redistribute it and/or<br>
+ * modify it under the terms of the GNU General Public License version<br>
+ * 2 as published by the Free Software Foundation.<br>
+ *<br>
+ * You should have received a copy of the GNU General Public License<br>
+ * along with this program. If not, see <<a href="http://www.gnu.org/licenses/" target="_blank">http://www.gnu.org/licenses/</a>>.<br>
+ */<br>
+<br>
+#include "sheep_priv.h"<br>
+#include "http.h"<br>
+<br>
+/*<br>
+ * Meta Object tracks the free information of data vdi for the object allocation<br>
+ * in a free list. Free list is a redundant structure for bitmap for faster<br>
+ * allocation.<br>
+ *<br>
+ * +-------------------------------+<br>
+ * | |<br>
+ * | sorted list v------v<br>
+ * +--------------------------------+-----------------------+ +--------+<br>
+ * | Header | fd1 | fd2 | ... | fdN | .... object data .... | <-- | bitmap |<br>
+ * +--------------------------------+-----------------------+ +---------<br>
+ * |<-- 4M -->|<br>
+ *<br>
+ * Best-fit algorithm for allocation and merge and sort the free list at<br>
+ * deallocation. One simple sorted list is effecient enough for extent based<br>
+ * invariable user object.<br>
+ *<br>
+ * XXX: Add allocation group for scalability and solve the meta size limitation<br>
+ */<br>
+<br>
+struct header {<br>
+ uint64_t used;<br>
+ uint64_t nr_free;<br>
+};<br>
+<br>
+struct free_desc {<br>
+ uint64_t start;<br>
+ uint64_t count;<br>
+};<br>
+<br>
+static inline uint32_t oalloc_meta_length(struct header *hd)<br>
+{<br>
+ return sizeof(struct header) + sizeof(struct free_desc) * hd->nr_free;<br>
+}<br>
+<br>
+#define HEADER_TO_FREE_DESC(hd) ((struct free_desc *) \<br>
+ ((char *)hd + sizeof(struct header)))<br>
+<br>
+#define MAX_FREE_DESC ((SD_DATA_OBJ_SIZE - sizeof(struct header)) / \<br>
+ sizeof(struct free_desc))<br>
+<br>
+/*<br>
+ * Initialize the data vdi<br>
+ *<br>
+ * @vid: the vdi where the allocator resides<br>
+ */<br>
+int oalloc_init(uint32_t vid)<br>
+{<br>
+ struct strbuf buf = STRBUF_INIT;<br>
+ struct sd_inode *inode = xmalloc(sizeof(struct sd_inode));<br>
+ struct header hd = {<br>
+ .nr_free = 1,<br>
+ };<br>
+ struct free_desc fd = {<br>
+ .start = 1, /* Use first object as the meta object */<br>
+ .count = MAX_DATA_OBJS - 1,<br>
+ };<br>
+ int ret;<br>
+<br>
+ strbuf_add(&buf, &hd, sizeof(hd));<br>
+ strbuf_add(&buf, &fd, sizeof(fd));<br>
+<br>
+ ret = sd_read_object(vid_to_vdi_oid(vid), (char *)inode,<br>
+ sizeof(*inode), 0);<br>
+ if (ret != SD_RES_SUCCESS) {<br>
+ sd_err("failed to read inode, %" PRIx32", %s", vid,<br>
+ sd_strerror(ret));<br>
+ goto out;<br>
+ }<br>
+ ret = sd_write_object(vid_to_data_oid(vid, 0), buf.buf,<br>
+ buf.len, 0, true);<br>
+ if (ret != SD_RES_SUCCESS) {<br>
+ sd_err("failed to create meta object for %" PRIx32", %s", vid,<br>
+ sd_strerror(ret));<br>
+ goto out;<br>
+ }<br>
+ INODE_SET_VID(inode, 0, vid);<br>
+ ret = sd_inode_write_vid(sheep_bnode_writer, inode, 0,<br>
+ vid, vid, 0, false, false);<br>
+ if (ret != SD_RES_SUCCESS) {<br>
+ sd_err("failed to update inode, %" PRIx32", %s", vid,<br>
+ sd_strerror(ret));<br>
+ goto out;<br>
+ }<br>
+out:<br>
+ strbuf_release(&buf);<br>
+ free(inode);<br>
+ return ret;<br>
+}<br>
+<br>
+/*<br>
+ * Allocate the objects and upate the free list.<br>
+ *<br>
+ * Callers are expected to call oalloc_new_finish() to update the inode bitmap<br>
+ * after filling up the data.<br>
+ *<br>
+ * @vid: the vdi where the allocator resides<br>
+ * @start: start index of the objects to allocate<br>
+ * @count: number of the objects to allocate<br>
+ */<br>
+int oalloc_new_prepare(uint32_t vid, uint64_t *start, uint64_t count)<br>
+{<br>
+ char *meta = xvalloc(SD_DATA_OBJ_SIZE);<br>
+ struct header *hd;<br>
+ struct free_desc *fd;<br>
+ uint64_t oid = vid_to_data_oid(vid, 0);<br>
+ int i, ret;<br></blockquote><div><br></div><div>uint64_t i maybe better.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
+<br>
+ ret = sd_read_object(oid, meta, SD_DATA_OBJ_SIZE, 0);<br>
+ if (ret != SD_RES_SUCCESS) {<br>
+ sd_err("failed to read meta %" PRIx64 ", %s", oid,<br>
+ sd_strerror(ret));<br>
+ goto out;<br>
+ }<br>
+<br>
+ hd = (struct header *)meta;<br>
+ fd = (struct free_desc *)(meta + oalloc_meta_length(hd)) - 1;<br>
+ sd_debug("used %"PRIu64", nr_free %"PRIu64, hd->used, hd->nr_free);<br>
+ for (i = 0; i < hd->nr_free; i++, fd--) {<br>
+ sd_debug("start %"PRIu64", count %"PRIu64, fd->start,<br>
+ fd->count);<br>
+ if (fd->count > count)<br>
+ break;<br>
+ }<br>
+ if (i == hd->nr_free) {<br>
+ ret = SD_RES_NO_SPACE;<br>
+ goto out;<br>
+ }<br>
+<br>
+ *start = fd->start;<br>
+ fd->start += count;<br>
+ fd->count -= count;<br>
+ hd->used += count;<br>
+<br>
+ /* Update the meta object */<br>
+ ret = sd_write_object(oid, meta, oalloc_meta_length(hd), 0, false);<br>
+ if (ret != SD_RES_SUCCESS)<br>
+ sd_err("failed to update meta %"PRIx64 ", %s", oid,<br>
+ sd_strerror(ret));<br>
+out:<br>
+ free(meta);<br>
+ return ret;<br>
+}<br>
+<br>
+/*<br>
+ * Update the inode map of the vid<br>
+ *<br>
+ * @vid: the vdi where the allocator resides<br>
+ * @start: start index of the objects to update<br>
+ * @count: number of the objects to update<br>
+ */<br>
+int oalloc_new_finish(uint32_t vid, uint64_t start, uint64_t count)<br>
+{<br>
+ struct sd_inode *inode = xmalloc(sizeof(struct sd_inode));<br>
+ int ret;<br>
+<br>
+ ret = sd_read_object(vid_to_vdi_oid(vid), (char *)inode,<br>
+ sizeof(*inode), 0);<br>
+ if (ret != SD_RES_SUCCESS) {<br>
+ sd_err("failed to read inode, %" PRIx64 ", %s",<br>
+ vid_to_vdi_oid(vid), sd_strerror(ret));<br>
+ goto out;<br>
+ }<br>
+ /* TODO: add range support for inode update */<br></blockquote><div><br></div><div>sd_inode_write_vid() only write header of sd_inode and btree-entres, so it is already range-updating.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
+ for (uint64_t i = 0; i < count; i++) {<br>
+ INODE_SET_VID(inode, start + i, vid);<br>
+ ret = sd_inode_write_vid(sheep_bnode_writer, inode, start + i,<br>
+ vid, vid, 0, false, false); </blockquote><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
+ if (ret != SD_RES_SUCCESS) {<br>
+ sd_err("failed to update inode, %" PRIx64", %s",<br>
+ vid_to_vdi_oid(vid), sd_strerror(ret));<br>
+ goto out;<br>
+ }<br>
+ }<br>
+out:<br>
+ free(inode);<br>
+ return ret;<br>
+}<br>
+<br>
+static int free_desc_cmp(struct free_desc *a, struct free_desc *b)<br>
+{<br>
+ return -intcmp(a->start, b->start);<br>
+}<br>
+<br>
+static inline int update_and_merge_free_desc(char *meta, uint64_t start,<br>
+ uint64_t count, uint32_t vid)<br>
+{<br>
+ struct header *hd = (struct header *)meta;<br>
+ struct free_desc *tail, *fd = HEADER_TO_FREE_DESC(hd);<br>
+ int i, j;<br></blockquote><div>uint64_t i, j;</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
+<br>
+ /* Try our best to merge it in place, or append it to tail */<br>
+ for (i = 0; i < hd->nr_free; i++) {<br>
+ if (start + count == fd->start) {<br>
+ fd->start = start;<br>
+ fd->count += count;<br>
+ break;<br>
+ } else if(fd->start + fd->count == start) {<br>
+ fd->count +=count;<br>
+ break;<br>
+ }<br>
+ fd++;<br>
+ }<br>
+<br>
+ if (i == hd->nr_free) {<br>
+ if (hd->nr_free >= MAX_FREE_DESC)<br>
+ return SD_RES_NO_SPACE;<br>
+<br>
+ tail = (struct free_desc *)(meta + oalloc_meta_length(hd));<br>
+ tail->start = start;<br>
+ tail->count = count;<br>
+ hd->nr_free++;<br>
+ }<br>
+<br>
+ hd->used -= count;<br>
+ xqsort(HEADER_TO_FREE_DESC(hd), hd->nr_free, free_desc_cmp);<br>
+<br>
+ /* Merge as hard as we can */<br>
+ j = hd->nr_free - 1;<br>
+ tail = (struct free_desc *)(meta + oalloc_meta_length(hd)) - 1;<br>
+ for (i = 0; i < j; i++, tail--) {<br>
+ struct free_desc *front = tail - 1;<br>
+<br>
+ sd_debug("start %"PRIu64", count %"PRIu64, tail->start,<br>
+ tail->count);<br>
+ if (tail->start + tail->count > front->start)<br>
+ sd_emerg("bad free descriptor found at %"PRIx32, vid);<br>
+ if (tail->start + tail->count == front->start) {<br>
+ front->start = tail->start;<br>
+ front->count += tail->count;<br>
+ memmove(tail, tail + 1, sizeof(*tail) * i);<br>
+ hd->nr_free--;<br>
+ }<br>
+ }<br>
+<br>
+ return SD_RES_SUCCESS;<br>
+}<br>
+<br>
+/*<br>
+ * Discard the allocted objects and update the free list of the allocator<br>
+ *<br>
+ * Caller should check the return value since it might fail.<br>
+ *<br>
+ * @vid: the vdi where the allocator resides<br>
+ * @start: start index of the objects to free<br>
+ * @count: number of the objects to free<br>
+ */<br>
+int oalloc_free(uint32_t vid, uint64_t start, uint64_t count)<br>
+{<br>
+ char *meta = xvalloc(SD_DATA_OBJ_SIZE);<br>
+ struct header *hd;<br>
+ uint64_t oid = vid_to_data_oid(vid, 0);<br>
+ int i, ret;<br></blockquote><div><br></div><div>uint64_t i </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
+<br>
+ ret = sd_read_object(oid, meta, SD_DATA_OBJ_SIZE, 0);<br>
+ if (ret != SD_RES_SUCCESS) {<br>
+ sd_err("failed to read meta %" PRIx64 ", %s", oid,<br>
+ sd_strerror(ret));<br>
+ goto out;<br>
+ }<br>
+<br>
+ ret = update_and_merge_free_desc(meta, start, count, vid);<br>
+ if (ret != SD_RES_SUCCESS)<br>
+ goto out;<br>
+<br>
+ /* XXX use aio to speed up discard of objects */<br>
+ for (i = 0; i < count; i++) {<br>
+ struct sd_req hdr;<br>
+<br>
+ sd_init_req(&hdr, SD_OP_DISCARD_OBJ);<br>
+ hdr.obj.oid = vid_to_data_oid(vid, start + i);<br>
+ ret = exec_local_req(&hdr, NULL);<br>
+ if (ret != SD_RES_SUCCESS)<br>
+ goto out;<br>
+ }<br>
+<br>
+ hd = (struct header *)meta;<br>
+ ret = sd_write_object(oid, meta, oalloc_meta_length(hd), 0, false);<br>
+ if (ret != SD_RES_SUCCESS) {<br>
+ sd_err("failed to update meta %"PRIx64 ", %s", oid,<br>
+ sd_strerror(ret));<br>
+ goto out;<br>
+ }<br>
+ sd_debug("used %"PRIu64", nr_free %"PRIu64, hd->used, hd->nr_free);<br>
+out:<br>
+ free(meta);<br>
+ return ret;<br>
+}<br>
<span class="HOEnZb"><font color="#888888">--<br>
1.7.9.5<br>
<br>
--<br>
sheepdog mailing list<br>
<a href="mailto:sheepdog@lists.wpkg.org">sheepdog@lists.wpkg.org</a><br>
<a href="http://lists.wpkg.org/mailman/listinfo/sheepdog" target="_blank">http://lists.wpkg.org/mailman/listinfo/sheepdog</a><br>
</font></span></blockquote></div><br><br clear="all"><div><br></div>-- <br>--<br>Best Regard<br>Robin Dong
</div></div>