Check in some more benchmark results for BlueSky/S3-west
[bluesky.git] / bluesky / dir.c
1 /* Blue Sky: File Systems in the Cloud
2  *
3  * Copyright (C) 2009  The Regents of the University of California
4  * Written by Michael Vrable <mvrable@cs.ucsd.edu>
5  *
6  * TODO: Licensing
7  */
8
9 #include <stdint.h>
10 #include <inttypes.h>
11 #include <glib.h>
12
13 #include "bluesky-private.h"
14
15 /* Core filesystem: handling of directories. */
16
17 void bluesky_dirent_destroy(gpointer data)
18 {
19     BlueSkyDirent *dirent = (BlueSkyDirent *)data;
20     g_free(dirent->name);
21     g_free(dirent->name_folded);
22     g_free(dirent);
23 }
24
25 gint bluesky_dirent_compare(gconstpointer a, gconstpointer b,
26                             gpointer unused)
27 {
28     uint32_t hash1 = ((const BlueSkyDirent *)a)->cookie;
29     uint32_t hash2 = ((const BlueSkyDirent *)b)->cookie;
30
31     if (hash1 < hash2)
32         return -1;
33     else if (hash1 > hash2)
34         return 1;
35     else
36         return 0;
37 }
38
39 /* Perform a lookup for a file name within a directory.  Returns the inode
40  * number if found, or 0 if not (0 is never a valid inode number).  Should be
41  * called with the inode lock already held. */
42 uint64_t bluesky_directory_lookup(BlueSkyInode *inode, gchar *name)
43 {
44     g_return_val_if_fail(inode->type == BLUESKY_DIRECTORY, 0);
45     g_return_val_if_fail(inode->dirhash != NULL, 0);
46
47     BlueSkyDirent *d = g_hash_table_lookup(inode->dirhash, name);
48     if (d == NULL)
49         return 0;
50     else
51         return d->inum;
52 }
53
54 /* Case-insensitive lookup. */
55 uint64_t bluesky_directory_ilookup(BlueSkyInode *inode, gchar *name)
56 {
57     g_return_val_if_fail(inode->type == BLUESKY_DIRECTORY, 0);
58     g_return_val_if_fail(inode->dirhash_folded != NULL, 0);
59
60     name = bluesky_lowercase(name);
61     BlueSkyDirent *d = g_hash_table_lookup(inode->dirhash_folded, name);
62     g_free(name);
63
64     if (d == NULL)
65         return 0;
66     else
67         return d->inum;
68 }
69
70 /* Iterate through a directory listing.  This returns one directory entry at a
71  * time, finding the first entry with a directory cookie value larger than the
72  * supplied one.  Use a cookie of 0 to start reading from the start of a
73  * directory. */
74 BlueSkyDirent *bluesky_directory_read(BlueSkyInode *dir, uint32_t cookie)
75 {
76     BlueSkyDirent start = {NULL, NULL, cookie, 0};
77     GSequenceIter *i = g_sequence_search(dir->dirents, &start,
78                                          bluesky_dirent_compare, NULL);
79
80     if (g_sequence_iter_is_end(i))
81         return NULL;
82     else
83         return g_sequence_get(i);
84 }
85
86 /* Insert a new entry into a directory.  Should be called with the inode lock
87  * already held. */
88 gboolean bluesky_directory_insert(BlueSkyInode *dir,
89                                   const gchar *name, uint64_t inum)
90 {
91     g_return_val_if_fail(dir->type == BLUESKY_DIRECTORY, FALSE);
92
93     /* Check that no entry with the given name already exists. */
94     if (g_hash_table_lookup(dir->dirhash, name) != NULL)
95         return FALSE;
96
97     BlueSkyDirent *d = g_new(BlueSkyDirent, 1);
98     d->name = g_strdup(name);
99     d->name_folded = bluesky_lowercase(name);
100     d->inum = inum;
101
102     GSequence *dirents = dir->dirents;
103
104     /* Pick an unused cookie value for the directory at random.  Restrict
105      * ourselves to positive 32-bit values (even if treated as signed), and
106      * keep the first four slots free. */
107     while (1) {
108         do {
109             d->cookie = g_random_int() & 0x7fffffff;
110         } while (d->cookie < 4);
111
112         /* If the directory is empty, we can't possibly have a collision, so
113          * just go with the first key chosen. */
114         if (g_sequence_get_length(dirents) == 0)
115             break;
116
117         /* Otherwise, try looking up the generated cookie.  If we do not find a
118          * match, we can use this cookie value, otherwise we need to generate a
119          * new one and try again.  Because of the check above for an empty
120          * directory, we know that the lookup will return something so no need
121          * to worry about NULL. */
122         GSequenceIter *i = g_sequence_search(dir->dirents, d,
123                                              bluesky_dirent_compare, NULL);
124         i = g_sequence_iter_prev(i);
125         if (((BlueSkyDirent *)g_sequence_get(i))->cookie != d->cookie)
126             break;
127     }
128
129     /* Add the directory entry to both indices. */
130     g_sequence_insert_sorted(dirents, d, bluesky_dirent_compare, NULL);
131     g_hash_table_insert(dir->dirhash, d->name, d);
132     g_hash_table_insert(dir->dirhash_folded, d->name_folded, d);
133
134     bluesky_inode_update_ctime(dir, 1);
135     //bluesky_inode_do_sync(dir);     // TODO: Needed?
136
137     return TRUE;
138 }
139
140 /* Remove an entry from a directory.  Should be called with the inode lock
141  * already held. */
142 gboolean bluesky_directory_remove(BlueSkyInode *dir, gchar *name)
143 {
144     g_return_val_if_fail(dir->type == BLUESKY_DIRECTORY, FALSE);
145
146     BlueSkyDirent *d = g_hash_table_lookup(dir->dirhash, name);
147     if (d == NULL) {
148         return FALSE;
149     }
150
151     g_hash_table_remove(dir->dirhash, d->name);
152     g_hash_table_remove(dir->dirhash_folded, d->name_folded);
153
154     GSequenceIter *i = g_sequence_search(dir->dirents, d,
155                                          bluesky_dirent_compare, NULL);
156     i = g_sequence_iter_prev(i);
157
158     /* Assertion check, this ought to succeed */
159     g_return_val_if_fail(g_sequence_get(i) == d, FALSE);
160
161     g_sequence_remove(i);
162
163     bluesky_inode_update_ctime(dir, 1);
164
165     return TRUE;
166 }
167
168 /* Rename a file.  If desired (if overwrite is true) and if the target already
169  * exists, it will be unlinked first. */
170 gboolean bluesky_rename(BlueSkyInode *dir1, gchar *name1,
171                         BlueSkyInode *dir2, gchar *name2,
172                         gboolean case_sensitive,
173                         gboolean overwrite)
174 {
175     g_return_val_if_fail(dir1->type == BLUESKY_DIRECTORY, FALSE);
176     g_return_val_if_fail(dir2->type == BLUESKY_DIRECTORY, FALSE);
177
178     BlueSkyDirent *d1, *d2;
179
180     d1 = g_hash_table_lookup(case_sensitive ? dir1->dirhash
181                                             : dir1->dirhash_folded, name1);
182     d2 = g_hash_table_lookup(case_sensitive ? dir2->dirhash
183                                             : dir2->dirhash_folded, name2);
184
185     if (d1 == NULL)
186         return FALSE;
187
188     uint64_t inum = d1->inum;
189
190     /* Check that this rename does not cause a directory to be moved into one
191      * of its descendants, as that would create a loop of directories
192      * disconnected from the root. */
193     /* TODO */
194
195     if (d2 != NULL) {
196         if (!overwrite)
197             return FALSE;
198
199         bluesky_directory_remove(dir2, name2);
200
201         // TODO: Drop inode reference
202     }
203
204     bluesky_directory_remove(dir1, name1);
205     bluesky_directory_insert(dir2, name2, inum);
206
207     return TRUE;
208 }
209
210 /* Dump the contents of a directory to stdout.  Debugging only. */
211 void bluesky_directory_dump(BlueSkyInode *dir)
212 {
213     g_print("Directory dump:\n");
214
215     GSequenceIter *i = g_sequence_get_begin_iter(dir->dirents);
216
217     while (!g_sequence_iter_is_end(i)) {
218         BlueSkyDirent *d = g_sequence_get(i);
219         g_print("    0x%08x [inum=%"PRIu64"] %s\n",
220                 d->cookie, d->inum, d->name);
221         i = g_sequence_iter_next(i);
222     }
223 }