/* Core filesystem: handling of directories. */
-/* Hash a filename for a directory lookup. The string is hashed to a 64-bit
- * value. It is guaranteed that the hash values 0, 1, and 2 are never returned
- * (to allow the hash value to be used as an NFS cookie for a READDIR
- * operation). TODO: We perhaps should make this a keyed hash, and may want to
- * use something cheaper than MD5 to compute. */
-uint64_t bluesky_directory_hash(gchar *name)
-{
- GChecksum *csum = g_checksum_new(G_CHECKSUM_MD5);
- g_checksum_update(csum, (guchar *)name, -1);
-
- guint64 hashbytes[2];
- gsize hashsize = sizeof(hashbytes);
- g_checksum_get_digest(csum, (guint8 *)hashbytes, &hashsize);
-
- uint64_t hash = GUINT64_FROM_BE(hashbytes[0]);
- if (hash < 3)
- hash = 3;
-
- g_checksum_free(csum);
-
- return hash;
-}
-
void bluesky_dirent_destroy(gpointer data)
{
BlueSkyDirent *dirent = (BlueSkyDirent *)data;
g_free(dirent);
}
-static gint bluesky_dirent_compare(gconstpointer a, gconstpointer b,
- gpointer unused)
+gint bluesky_dirent_compare(gconstpointer a, gconstpointer b,
+ gpointer unused)
{
- /* We can't simply subtract the hash values, since they are 64-bit and the
- * result could overflow when converted to a gint. */
- uint64_t hash1 = ((const BlueSkyDirent *)a)->hash;
- uint64_t hash2 = ((const BlueSkyDirent *)b)->hash;
+ uint32_t hash1 = ((const BlueSkyDirent *)a)->cookie;
+ uint32_t hash2 = ((const BlueSkyDirent *)b)->cookie;
if (hash1 < hash2)
return -1;
uint64_t bluesky_directory_lookup(BlueSkyInode *inode, gchar *name)
{
g_return_val_if_fail(inode->type == BLUESKY_DIRECTORY, 0);
- g_return_val_if_fail(inode->dirents != NULL, 0);
+ g_return_val_if_fail(inode->dirhash != NULL, 0);
- /* First, construct a hash of the file name. Search the directory for a
- * match, then check to see if it does really match. */
- uint64_t hash = bluesky_directory_hash(name);
-
- BlueSkyDirent d = {name, hash, 0};
- GSequenceIter *i = g_sequence_search(inode->dirents, &d,
- bluesky_dirent_compare, NULL);
-
- /* g_sequence_search will return an iterator pointing just beyond the
- * desired node if there is a match, so that when inserting the new node
- * will go after the match. But we are trying to do a lookup, so back up
- * by one position. */
- i = g_sequence_iter_prev(i);
-
- if (g_sequence_iter_is_end(i))
- return 0;
- BlueSkyDirent *dirent = g_sequence_get(i);
- if (dirent->hash != hash)
+ BlueSkyDirent *d = g_hash_table_lookup(inode->dirhash, name);
+ if (d == NULL)
return 0;
- if (g_strcmp0(name, dirent->name) != 0)
- return 0;
-
- g_print("Lookup(%s) -> 0x%016llx\n", name, dirent->hash);
- return dirent->inum;
+ else
+ return d->inum;
}
/* Insert a new entry into a directory. Should be called with the inode lock
* already held. */
gboolean bluesky_directory_insert(BlueSkyInode *dir, gchar *name, uint64_t inum)
{
- /* First, construct a hash of the file name. Search the directory for a
- * match, then check to see if it does really match. */
- uint64_t hash = bluesky_directory_hash(name);
+ g_return_val_if_fail(dir->type == BLUESKY_DIRECTORY, FALSE);
+
+ /* Check that no entry with the given name already exists. */
+ if (g_hash_table_lookup(dir->dirhash, name) != NULL)
+ return FALSE;
BlueSkyDirent *d = g_new(BlueSkyDirent, 1);
d->name = g_strdup(name);
- d->hash = hash;
d->inum = inum;
+ GSequence *dirents = dir->dirents;
+
+ /* Pick an unused cookie value for the directory at random. Restrict
+ * ourselves to positive 32-bit values (even if treated as signed), and
+ * keep the first four slots free. */
+ while (1) {
+ do {
+ d->cookie = g_random_int() & 0x7fffffff;
+ } while (d->cookie < 4);
+
+ /* If the directory is empty, we can't possibly have a collision, so
+ * just go with the first key chosen. */
+ if (g_sequence_get_length(dirents) == 0)
+ break;
+
+ /* Otherwise, try looking up the generated cookie. If we do not find a
+ * match, we can use this cookie value, otherwise we need to generate a
+ * new one and try again. Because of the check above for an empty
+ * directory, we know that the lookup will return something so no need
+ * to worry about NULL. */
+ GSequenceIter *i = g_sequence_search(dir->dirents, d,
+ bluesky_dirent_compare, NULL);
+ i = g_sequence_iter_prev(i);
+ if (((BlueSkyDirent *)g_sequence_get(i))->cookie != d->cookie)
+ break;
+ }
+
+ /* Add the directory entry to both indices. */
+ g_sequence_insert_sorted(dirents, d, bluesky_dirent_compare, NULL);
+ g_hash_table_insert(dir->dirhash, d->name, d);
+
+ bluesky_inode_update_ctime(dir, 1);
+
+ return TRUE;
+}
+
+/* Remove an from a directory. Should be called with the inode lock already
+ * held. */
+gboolean bluesky_directory_remove(BlueSkyInode *dir, gchar *name)
+{
+ g_return_val_if_fail(dir->type == BLUESKY_DIRECTORY, FALSE);
+
+ BlueSkyDirent *d = g_hash_table_lookup(dir->dirhash, name);
+ if (d == NULL) {
+ return FALSE;
+ }
+
+ g_hash_table_remove(dir->dirhash, name);
+
GSequenceIter *i = g_sequence_search(dir->dirents, d,
bluesky_dirent_compare, NULL);
+ i = g_sequence_iter_prev(i);
- /* If a directory entry already exists, return failure. The caller must
- * delete the old entry and try again. TODO: We'll fail on a hash
- * collision; we should handle that case. */
- if (!g_sequence_iter_is_end(g_sequence_iter_prev(i))) {
- BlueSkyDirent *d2 = g_sequence_get(g_sequence_iter_prev(i));
- if (d2->hash == hash)
- return FALSE;
- }
+ /* Assertion check, this ought to succeed */
+ g_return_val_if_fail(g_sequence_get(i) == d, FALSE);
+
+ g_sequence_remove(i);
+
+ bluesky_dirent_destroy(d);
- g_sequence_insert_before(i, d);
- dir->change_count++;
+ bluesky_inode_update_ctime(dir, 1);
return TRUE;
}
while (!g_sequence_iter_is_end(i)) {
BlueSkyDirent *d = g_sequence_get(i);
- g_print(" 0x%016llx [inum=%lld] %s\n", d->hash, d->inum, d->name);
+ g_print(" 0x%08x [inum=%lld] %s\n", d->cookie, d->inum, d->name);
i = g_sequence_iter_next(i);
}
}
projects / bluesky.git / blobdiff