[dovecot-cvs] dovecot/src/lib-index mail-tree-redblack.c,1.14,1.15 mail-tree.c,1.5,1.6 mail-tree.h,1.3,1.4
cras at procontrol.fi
cras at procontrol.fi
Thu Oct 24 05:48:35 EEST 2002
Update of /home/cvs/dovecot/src/lib-index
In directory danu:/tmp/cvs-serv30483/lib-index
Modified Files:
mail-tree-redblack.c mail-tree.c mail-tree.h
Log Message:
Instead of keeping "unused nodes" list in tree file, just move the last node
over the deleted one. This way we're also able to truncate the file when
needed.
Index: mail-tree-redblack.c
===================================================================
RCS file: /home/cvs/dovecot/src/lib-index/mail-tree-redblack.c,v
retrieving revision 1.14
retrieving revision 1.15
diff -u -d -r1.14 -r1.15
--- mail-tree-redblack.c 23 Oct 2002 19:49:23 -0000 1.14
+++ mail-tree-redblack.c 24 Oct 2002 01:48:33 -0000 1.15
@@ -18,7 +18,10 @@
You should have received a copy of the GNU Lesser General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- */
+*/
+
+/* NOTE: currently this code doesn't do any bounds checkings. I'm not sure
+ if I should even bother, the code would just get uglier and slower. */
#include "lib.h"
#include "mail-index.h"
@@ -60,14 +63,6 @@
MailTreeNode *node = tree->node_base;
unsigned int x;
- if (tree->header->unused_root != RBNULL) {
- /* use the nodes in the middle of the file */
- x = tree->header->unused_root;
- tree->header->unused_root = node[x].up;
- return x;
- }
-
- /* use nodes at the end of file */
if (tree->mmap_used_length == tree->mmap_full_length) {
if (!_mail_tree_grow(tree))
return RBNULL;
@@ -77,20 +72,65 @@
i_assert(tree->mmap_used_length + sizeof(MailTreeNode) <=
tree->mmap_full_length);
+ x = (tree->mmap_used_length - sizeof(MailTreeHeader)) /
+ sizeof(MailTreeNode);
+
tree->header->used_file_size += sizeof(MailTreeNode);
tree->mmap_used_length += sizeof(MailTreeNode);
- return (tree->mmap_used_length - sizeof(MailTreeHeader)) /
- sizeof(MailTreeNode) - 1;
+ memset(&node[x], 0, sizeof(MailTreeNode));
+ return x;
+}
+
+static void
+rb_move(MailTree *tree, unsigned int src, unsigned int dest)
+{
+ MailTreeNode *node = tree->node_base;
+
+ /* update parent */
+ if (node[src].up != RBNULL) {
+ if (node[node[src].up].left == src)
+ node[node[src].up].left = dest;
+ else if (node[node[src].up].right == src)
+ node[node[src].up].right = dest;
+ }
+
+ /* update children */
+ if (node[src].left != RBNULL)
+ node[node[src].left].up = dest;
+ if (node[src].right != RBNULL)
+ node[node[src].right].up = dest;
+
+ /* update root */
+ if (tree->header->root == src)
+ tree->header->root = dest;
+
+ memcpy(&node[dest], &node[src], sizeof(MailTreeNode));
+ memset(&node[src], 0, sizeof(MailTreeNode));
}
static void
rb_free(MailTree *tree, unsigned int x)
{
- MailTreeNode *node = tree->node_base;
+ unsigned int last;
- node[x].up = tree->header->unused_root;
- tree->header->unused_root = x;
+ i_assert(tree->mmap_used_length >=
+ sizeof(MailTreeHeader) + sizeof(MailTreeNode));
+
+ /* get index to last used record */
+ last = (tree->mmap_used_length - sizeof(MailTreeHeader)) /
+ sizeof(MailTreeNode) - 1;
+
+ if (last != x) {
+ /* move it over the one we want free'd */
+ rb_move(tree, last, x);
+ }
+
+ /* mark the moved node unused */
+ tree->mmap_used_length -= sizeof(MailTreeNode);
+ tree->header->used_file_size -= sizeof(MailTreeNode);
+
+ _mail_tree_truncate(tree);
}
/*
Index: mail-tree.c
===================================================================
RCS file: /home/cvs/dovecot/src/lib-index/mail-tree.c,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- mail-tree.c 23 Oct 2002 19:49:23 -0000 1.5
+++ mail-tree.c 24 Oct 2002 01:48:33 -0000 1.6
@@ -11,8 +11,9 @@
#include <unistd.h>
#include <fcntl.h>
-#define MAIL_TREE_INITIAL_SIZE \
- (sizeof(MailTreeHeader) + sizeof(MailTreeNode) * 64)
+#define MAIL_TREE_MIN_SIZE \
+ (sizeof(MailTreeHeader) + \
+ INDEX_MIN_RECORDS_COUNT * sizeof(MailTreeNode))
static int tree_set_syscall_error(MailTree *tree, const char *function)
{
@@ -46,8 +47,14 @@
int _mail_tree_mmap_update(MailTree *tree, int forced)
{
if (!forced && tree->header != NULL &&
- tree->mmap_full_length >= tree->header->used_file_size) {
+ tree->sync_id == tree->header->sync_id) {
+ /* make sure file size hasn't changed */
tree->mmap_used_length = tree->header->used_file_size;
+ if (tree->mmap_used_length > tree->mmap_full_length) {
+ i_panic("Tree file size was grown without "
+ "updating sync_id");
+ }
+
return TRUE;
}
@@ -56,7 +63,7 @@
if (tree->mmap_base != NULL) {
/* make sure we're synced before munmap() */
if (tree->modified &&
- msync(tree->mmap_base, tree->mmap_used_length, MS_SYNC) < 0)
+ msync(tree->mmap_base, tree->mmap_highwater, MS_SYNC) < 0)
return tree_set_syscall_error(tree, "msync()");
tree->modified = FALSE;
@@ -121,7 +128,9 @@
tree->header = tree->mmap_base;
tree->node_base = (MailTreeNode *) ((char *) tree->mmap_base +
sizeof(MailTreeHeader));
+ tree->sync_id = hdr->sync_id;
tree->mmap_used_length = hdr->used_file_size;
+ tree->mmap_highwater = tree->mmap_used_length;
return TRUE;
}
@@ -254,7 +263,7 @@
return tree_set_syscall_error(tree, "write_full()");
}
- if (file_set_size(tree->fd, MAIL_TREE_INITIAL_SIZE) < 0) {
+ if (file_set_size(tree->fd, MAIL_TREE_MIN_SIZE) < 0) {
if (errno == ENOSPC)
tree->index->nodiskspace = TRUE;
@@ -302,11 +311,13 @@
i_assert(tree->mmap_base != NULL);
- if (msync(tree->mmap_base, tree->mmap_used_length, MS_SYNC) < 0)
+ if (msync(tree->mmap_base, tree->mmap_highwater, MS_SYNC) < 0)
return tree_set_syscall_error(tree, "msync()");
- *fsync_fd = tree->fd;
+ tree->mmap_highwater = tree->mmap_used_length;
tree->modified = FALSE;
+
+ *fsync_fd = tree->fd;
return TRUE;
}
@@ -344,8 +355,47 @@
return tree_set_syscall_error(tree, "file_set_size()");
}
+ /* file size changed, let others know about it too by changing
+ sync_id in header. */
+ tree->header->sync_id++;
+ tree->modified = TRUE;
+
if (!_mail_tree_mmap_update(tree, TRUE) || !mmap_verify(tree))
return FALSE;
return TRUE;
+}
+
+void _mail_tree_truncate(MailTree *tree)
+{
+ /* pretty much copy&pasted from mail_index_compress() */
+ uoff_t empty_space, truncate_threshold;
+
+ i_assert(tree->index->lock_type == MAIL_LOCK_EXCLUSIVE);
+
+ if (tree->mmap_full_length <= MAIL_TREE_MIN_SIZE)
+ return;
+
+ empty_space = tree->mmap_full_length - tree->mmap_used_length;
+
+ truncate_threshold =
+ tree->mmap_full_length / 100 * INDEX_TRUNCATE_PERCENTAGE;
+
+ if (empty_space > truncate_threshold) {
+ tree->mmap_full_length = tree->mmap_used_length +
+ (empty_space * INDEX_TRUNCATE_KEEP_PERCENTAGE / 100);
+
+ /* keep the size record-aligned */
+ tree->mmap_full_length -=
+ (tree->mmap_full_length - sizeof(MailTreeHeader)) %
+ sizeof(MailTreeNode);
+
+ if (tree->mmap_full_length < MAIL_TREE_MIN_SIZE)
+ tree->mmap_full_length = MAIL_TREE_MIN_SIZE;
+
+ if (ftruncate(tree->fd, (off_t)tree->mmap_full_length) < 0)
+ tree_set_syscall_error(tree, "ftruncate()");
+
+ tree->header->sync_id++;
+ }
}
Index: mail-tree.h
===================================================================
RCS file: /home/cvs/dovecot/src/lib-index/mail-tree.h,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- mail-tree.h 23 Oct 2002 19:49:23 -0000 1.3
+++ mail-tree.h 24 Oct 2002 01:48:33 -0000 1.4
@@ -16,20 +16,22 @@
MailTreeNode *node_base;
size_t mmap_used_length;
size_t mmap_full_length;
+ size_t mmap_highwater; /* for msync()ing */
MailTreeHeader *header;
+ unsigned int sync_id;
+
unsigned int anon_mmap:1;
unsigned int modified:1;
};
struct _MailTreeHeader {
unsigned int indexid;
+ unsigned int sync_id;
- unsigned int root;
- unsigned int unused_root;
-
- unsigned int alignment;
uoff_t used_file_size;
+
+ unsigned int root;
};
struct _MailTreeNode {
@@ -74,5 +76,6 @@
int _mail_tree_set_corrupted(MailTree *tree, const char *fmt, ...);
int _mail_tree_mmap_update(MailTree *tree, int forced);
int _mail_tree_grow(MailTree *tree);
+void _mail_tree_truncate(MailTree *tree);
#endif
More information about the dovecot-cvs
mailing list