1 /* Blue Sky: File Systems in the Cloud
3 * Copyright (C) 2009 The Regents of the University of California
4 * Written by Michael Vrable <mvrable@cs.ucsd.edu>
14 /* Core filesystem: handling of directories. */
16 /* Hash a filename for a directory lookup. The string is hashed to a 64-bit
17 * value. It is guaranteed that the hash values 0, 1, and 2 are never returned
18 * (to allow the hash value to be used as an NFS cookie for a READDIR
19 * operation). TODO: We perhaps should make this a keyed hash, and may want to
20 * use something cheaper than MD5 to compute. */
21 uint64_t bluesky_directory_hash(gchar *name)
23 GChecksum *csum = g_checksum_new(G_CHECKSUM_MD5);
24 g_checksum_update(csum, (guchar *)name, -1);
27 gsize hashsize = sizeof(hashbytes);
28 g_checksum_get_digest(csum, (guint8 *)hashbytes, &hashsize);
30 uint64_t hash = GUINT64_FROM_BE(hashbytes[0]);
34 g_checksum_free(csum);
39 void bluesky_dirent_destroy(gpointer data)
41 BlueSkyDirent *dirent = (BlueSkyDirent *)data;
46 static gint bluesky_dirent_compare(gconstpointer a, gconstpointer b,
49 /* We can't simply subtract the hash values, since they are 64-bit and the
50 * result could overflow when converted to a gint. */
51 uint64_t hash1 = ((const BlueSkyDirent *)a)->hash;
52 uint64_t hash2 = ((const BlueSkyDirent *)b)->hash;
56 else if (hash1 > hash2)
62 /* Perform a lookup for a file name within a directory. Returns the inode
63 * number if found, or 0 if not (0 is never a valid inode number). Should be
64 * called with the inode lock already held. */
65 uint64_t bluesky_directory_lookup(BlueSkyInode *inode, gchar *name)
67 g_return_val_if_fail(inode->type == BLUESKY_DIRECTORY, 0);
68 g_return_val_if_fail(inode->dirents != NULL, 0);
70 /* First, construct a hash of the file name. Search the directory for a
71 * match, then check to see if it does really match. */
72 uint64_t hash = bluesky_directory_hash(name);
74 BlueSkyDirent d = {name, hash, 0};
75 GSequenceIter *i = g_sequence_search(inode->dirents, &d,
76 bluesky_dirent_compare, NULL);
78 /* g_sequence_search will return an iterator pointing just beyond the
79 * desired node if there is a match, so that when inserting the new node
80 * will go after the match. But we are trying to do a lookup, so back up
82 i = g_sequence_iter_prev(i);
84 if (g_sequence_iter_is_end(i))
86 BlueSkyDirent *dirent = g_sequence_get(i);
87 if (dirent->hash != hash)
89 if (g_strcmp0(name, dirent->name) != 0)
92 g_print("Lookup(%s) -> 0x%016llx\n", name, dirent->hash);
96 /* Insert a new entry into a directory. Should be called with the inode lock
98 gboolean bluesky_directory_insert(BlueSkyInode *dir, gchar *name, uint64_t inum)
100 /* First, construct a hash of the file name. Search the directory for a
101 * match, then check to see if it does really match. */
102 uint64_t hash = bluesky_directory_hash(name);
104 BlueSkyDirent *d = g_new(BlueSkyDirent, 1);
105 d->name = g_strdup(name);
109 GSequenceIter *i = g_sequence_search(dir->dirents, d,
110 bluesky_dirent_compare, NULL);
112 /* If a directory entry already exists, return failure. The caller must
113 * delete the old entry and try again. TODO: We'll fail on a hash
114 * collision; we should handle that case. */
115 if (!g_sequence_iter_is_end(g_sequence_iter_prev(i))) {
116 BlueSkyDirent *d2 = g_sequence_get(g_sequence_iter_prev(i));
117 if (d2->hash == hash)
121 g_sequence_insert_before(i, d);
127 /* Dump the contents of a directory to stdout. Debugging only. */
128 void bluesky_directory_dump(BlueSkyInode *dir)
130 g_print("Directory dump:\n");
132 GSequenceIter *i = g_sequence_get_begin_iter(dir->dirents);
134 while (!g_sequence_iter_is_end(i)) {
135 BlueSkyDirent *d = g_sequence_get(i);
136 g_print(" 0x%016llx [inum=%lld] %s\n", d->hash, d->inum, d->name);
137 i = g_sequence_iter_next(i);