X-Git-Url: http://git.vrable.net/?a=blobdiff_plain;f=dir.c;h=204439efde629ebac028864498aa1b5d61662ff9;hb=d32328c00f54c2f6f4e6eeb8993d33d062e9477c;hp=eab71bef2c5a3837ebf6b47769231bb0f3ba4e63;hpb=8819789ef2264b26aebfae489932a447f6e0f65f;p=bluesky.git diff --git a/dir.c b/dir.c index eab71be..204439e 100644 --- a/dir.c +++ b/dir.c @@ -13,29 +13,6 @@ /* 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; @@ -43,13 +20,11 @@ void bluesky_dirent_destroy(gpointer 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; @@ -65,61 +40,90 @@ static gint bluesky_dirent_compare(gconstpointer a, gconstpointer b, 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; } @@ -133,7 +137,7 @@ void bluesky_directory_dump(BlueSkyInode *dir) 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); } }