/*
* Copyright (C) Sistina Software, Inc. 1997-2003 All rights reserved.
- * Copyright (C) 2004-2005 Red Hat, Inc. All rights reserved.
+ * Copyright (C) 2004-2006 Red Hat, Inc. All rights reserved.
*
* This copyrighted material is made available to anyone wishing to use,
* modify, copy, or redistribute it subject to the terms and conditions
*/
/*
-* Implements Extendible Hashing as described in:
-* "Extendible Hashing" by Fagin, et al in
-* __ACM Trans. on Database Systems__, Sept 1979.
-*
-*
-* Here's the layout of dirents which is essentially the same as that of ext2
-* within a single block. The field de_name_len is the number of bytes
-* actually required for the name (no null terminator). The field de_rec_len
-* is the number of bytes allocated to the dirent. The offset of the next
-* dirent in the block is (dirent + dirent->de_rec_len). When a dirent is
-* deleted, the preceding dirent inherits its allocated space, ie
-* prev->de_rec_len += deleted->de_rec_len. Since the next dirent is obtained
-* by adding de_rec_len to the current dirent, this essentially causes the
-* deleted dirent to get jumped over when iterating through all the dirents.
-*
-* When deleting the first dirent in a block, there is no previous dirent so
-* the field de_ino is set to zero to designate it as deleted. When allocating
-* a dirent, gfs2_dirent_alloc iterates through the dirents in a block. If the
-* first dirent has (de_ino == 0) and de_rec_len is large enough, this first
-* dirent is allocated. Otherwise it must go through all the 'used' dirents
-* searching for one in which the amount of total space minus the amount of
-* used space will provide enough space for the new dirent.
-*
-* There are two types of blocks in which dirents reside. In a stuffed dinode,
-* the dirents begin at offset sizeof(struct gfs2_dinode) from the beginning of
-* the block. In leaves, they begin at offset sizeof(struct gfs2_leaf) from the
-* beginning of the leaf block. The dirents reside in leaves when
-*
-* dip->i_di.di_flags & GFS2_DIF_EXHASH is true
-*
-* Otherwise, the dirents are "linear", within a single stuffed dinode block.
-*
-* When the dirents are in leaves, the actual contents of the directory file are
-* used as an array of 64-bit block pointers pointing to the leaf blocks. The
-* dirents are NOT in the directory file itself. There can be more than one block
-* pointer in the array that points to the same leaf. In fact, when a directory
-* is first converted from linear to exhash, all of the pointers point to the
-* same leaf.
-*
-* When a leaf is completely full, the size of the hash table can be
-* doubled unless it is already at the maximum size which is hard coded into
-* GFS2_DIR_MAX_DEPTH. After that, leaves are chained together in a linked list,
-* but never before the maximum hash table size has been reached.
-*/
+ * Implements Extendible Hashing as described in:
+ * "Extendible Hashing" by Fagin, et al in
+ * __ACM Trans. on Database Systems__, Sept 1979.
+ *
+ *
+ * Here's the layout of dirents which is essentially the same as that of ext2
+ * within a single block. The field de_name_len is the number of bytes
+ * actually required for the name (no null terminator). The field de_rec_len
+ * is the number of bytes allocated to the dirent. The offset of the next
+ * dirent in the block is (dirent + dirent->de_rec_len). When a dirent is
+ * deleted, the preceding dirent inherits its allocated space, ie
+ * prev->de_rec_len += deleted->de_rec_len. Since the next dirent is obtained
+ * by adding de_rec_len to the current dirent, this essentially causes the
+ * deleted dirent to get jumped over when iterating through all the dirents.
+ *
+ * When deleting the first dirent in a block, there is no previous dirent so
+ * the field de_ino is set to zero to designate it as deleted. When allocating
+ * a dirent, gfs2_dirent_alloc iterates through the dirents in a block. If the
+ * first dirent has (de_ino == 0) and de_rec_len is large enough, this first
+ * dirent is allocated. Otherwise it must go through all the 'used' dirents
+ * searching for one in which the amount of total space minus the amount of
+ * used space will provide enough space for the new dirent.
+ *
+ * There are two types of blocks in which dirents reside. In a stuffed dinode,
+ * the dirents begin at offset sizeof(struct gfs2_dinode) from the beginning of
+ * the block. In leaves, they begin at offset sizeof(struct gfs2_leaf) from the
+ * beginning of the leaf block. The dirents reside in leaves when
+ *
+ * dip->i_di.di_flags & GFS2_DIF_EXHASH is true
+ *
+ * Otherwise, the dirents are "linear", within a single stuffed dinode block.
+ *
+ * When the dirents are in leaves, the actual contents of the directory file are
+ * used as an array of 64-bit block pointers pointing to the leaf blocks. The
+ * dirents are NOT in the directory file itself. There can be more than one
+ * block pointer in the array that points to the same leaf. In fact, when a
+ * directory is first converted from linear to exhash, all of the pointers
+ * point to the same leaf.
+ *
+ * When a leaf is completely full, the size of the hash table can be
+ * doubled unless it is already at the maximum size which is hard coded into
+ * GFS2_DIR_MAX_DEPTH. After that, leaves are chained together in a linked list,
+ * but never before the maximum hash table size has been reached.
+ */
#include <linux/sched.h>
#include <linux/slab.h>
#include <linux/spinlock.h>
-#include <linux/completion.h>
#include <linux/buffer_head.h>
#include <linux/sort.h>
#include <linux/gfs2_ondisk.h>
#include <linux/crc32.h>
-#include <asm/semaphore.h>
+#include <linux/vmalloc.h>
#include "gfs2.h"
#include "lm_interface.h"
uint32_t index, uint32_t len, uint64_t leaf_no,
void *data);
-int gfs2_dir_get_buffer(struct gfs2_inode *ip, uint64_t block, int new,
- struct buffer_head **bhp)
+
+int gfs2_dir_get_new_buffer(struct gfs2_inode *ip, uint64_t block,
+ struct buffer_head **bhp)
{
struct buffer_head *bh;
- int error = 0;
-
- if (new) {
- bh = gfs2_meta_new(ip->i_gl, block);
- gfs2_trans_add_bh(ip->i_gl, bh, 1);
- gfs2_metatype_set(bh, GFS2_METATYPE_JD, GFS2_FORMAT_JD);
- gfs2_buffer_clear_tail(bh, sizeof(struct gfs2_meta_header));
- } else {
- error = gfs2_meta_read(ip->i_gl, block, DIO_START | DIO_WAIT,
- &bh);
- if (error)
- return error;
- if (gfs2_metatype_check(ip->i_sbd, bh, GFS2_METATYPE_JD)) {
- brelse(bh);
- return -EIO;
- }
- }
+ bh = gfs2_meta_new(ip->i_gl, block);
+ gfs2_trans_add_bh(ip->i_gl, bh, 1);
+ gfs2_metatype_set(bh, GFS2_METATYPE_JD, GFS2_FORMAT_JD);
+ gfs2_buffer_clear_tail(bh, sizeof(struct gfs2_meta_header));
*bhp = bh;
return 0;
}
+static int gfs2_dir_get_existing_buffer(struct gfs2_inode *ip, uint64_t block,
+ struct buffer_head **bhp)
+{
+ struct buffer_head *bh;
+ int error;
+ error = gfs2_meta_read(ip->i_gl, block, DIO_START | DIO_WAIT, &bh);
+ if (error)
+ return error;
+ if (gfs2_metatype_check(ip->i_sbd, bh, GFS2_METATYPE_JD)) {
+ brelse(bh);
+ return -EIO;
+ }
+ *bhp = bh;
+ return 0;
+}
static int gfs2_dir_write_stuffed(struct gfs2_inode *ip, const char *buf,
unsigned int offset, unsigned int size)
if (!extlen) {
new = 1;
- error = gfs2_block_map(ip, lblock, &new, &dblock,
- &extlen);
+ error = gfs2_extent_map(ip->i_vnode, lblock, &new,
+ &dblock, &extlen);
if (error)
goto fail;
error = -EIO;
goto fail;
}
- error = gfs2_dir_get_buffer(ip, dblock,
- (amount == sdp->sd_jbsize) ?
- 1 : new, &bh);
+ if (amount == sdp->sd_jbsize || new)
+ error = gfs2_dir_get_new_buffer(ip, dblock, &bh);
+ else
+ error = gfs2_dir_get_existing_buffer(ip, dblock, &bh);
+
if (error)
goto fail;
if (!extlen) {
new = 0;
- error = gfs2_block_map(ip, lblock, &new, &dblock,
- &extlen);
+ error = gfs2_extent_map(ip->i_vnode, lblock, &new,
+ &dblock, &extlen);
if (error)
goto fail;
}
gfs2_meta_ra(ip->i_gl, dblock, extlen);
if (dblock) {
- error = gfs2_dir_get_buffer(ip, dblock, new, &bh);
+ if (new)
+ error = gfs2_dir_get_new_buffer(ip, dblock, &bh);
+ else
+ error = gfs2_dir_get_existing_buffer(ip, dblock, &bh);
if (error)
goto fail;
dblock++;
BUG_ON(buf == NULL);
- switch(be16_to_cpu(h->mh_type)) {
+ switch(be32_to_cpu(h->mh_type)) {
case GFS2_METATYPE_LF:
offset = sizeof(struct gfs2_leaf);
break;
return offset;
wrong_type:
printk(KERN_WARNING "gfs2_scan_dirent: wrong block type %u\n",
- be16_to_cpu(h->mh_type));
+ be32_to_cpu(h->mh_type));
return -1;
}
{
struct gfs2_meta_header *h = (struct gfs2_meta_header *)bh->b_data;
- if (be16_to_cpu(h->mh_type) == GFS2_METATYPE_LF) {
+ if (be32_to_cpu(h->mh_type) == GFS2_METATYPE_LF) {
if (gfs2_meta_check(dip->i_sbd, bh))
return -EIO;
*dent = (struct gfs2_dirent *)(bh->b_data +
* Takes a dent from which to grab space as an argument. Returns the
* newly created dent.
*/
-struct gfs2_dirent *gfs2_init_dirent(struct inode *inode,
- struct gfs2_dirent *dent,
- const struct qstr *name,
- struct buffer_head *bh)
+static struct gfs2_dirent *gfs2_init_dirent(struct inode *inode,
+ struct gfs2_dirent *dent,
+ const struct qstr *name,
+ struct buffer_head *bh)
{
struct gfs2_inode *ip = inode->u.generic_ip;
struct gfs2_dirent *ndent;
return ERR_PTR(error);
dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size, scan, name, NULL);
got_dent:
+ if (unlikely(dent == NULL || IS_ERR(dent))) {
+ brelse(bh);
+ bh = NULL;
+ }
*pbh = bh;
return dent;
}
/* Get the old leaf block */
error = get_leaf(dip, leaf_no, &obh);
if (error)
- goto fail;
+ return error;
- gfs2_trans_add_bh(dip->i_gl, obh, 1);
oleaf = (struct gfs2_leaf *)obh->b_data;
+ if (dip->i_di.di_depth == be16_to_cpu(oleaf->lf_depth)) {
+ brelse(obh);
+ return 1; /* can't split */
+ }
+
+ gfs2_trans_add_bh(dip->i_gl, obh, 1);
nleaf = new_leaf(inode, &nbh, be16_to_cpu(oleaf->lf_depth) + 1);
if (!nleaf) {
len = 1 << (dip->i_di.di_depth - be16_to_cpu(oleaf->lf_depth));
half_len = len >> 1;
if (!half_len) {
+ printk(KERN_WARNING "di_depth %u lf_depth %u index %u\n", dip->i_di.di_depth, be16_to_cpu(oleaf->lf_depth), index);
gfs2_consist_inode(dip);
error = -EIO;
goto fail_brelse;
return error;
- fail_lpfree:
+fail_lpfree:
kfree(lp);
- fail_brelse:
+fail_brelse:
brelse(obh);
-
- fail:
brelse(nbh);
return error;
}
return 0;
error = -ENOMEM;
- larr = kmalloc((leaves + entries) * sizeof(void*), GFP_KERNEL);
+ larr = vmalloc((leaves + entries) * sizeof(void*));
if (!larr)
goto out;
darr = (const struct gfs2_dirent **)(larr + leaves);
out_kfree:
for(i = 0; i < leaf; i++)
brelse(larr[i]);
- kfree(larr);
+ vfree(larr);
out:
return error;
}
brelse(obh);
return -ENOSPC;
}
- oleaf->lf_next = cpu_to_be64(bn);
+ oleaf->lf_next = cpu_to_be64(bh->b_blocknr);
brelse(bh);
brelse(obh);
error = dir_split_leaf(inode, name);
if (error == 0)
continue;
- if (error != -ENOSPC)
+ if (error < 0)
break;
if (ip->i_di.di_depth < GFS2_DIR_MAX_DEPTH) {
error = dir_double_exhash(ip);
if (error)
break;
error = dir_split_leaf(inode, name);
- if (error)
+ if (error < 0)
break;
- continue;
+ if (error == 0)
+ continue;
}
error = dir_new_leaf(inode, name);
if (!error)
if (!entries)
gfs2_consist_inode(dip);
leaf->lf_entries = cpu_to_be16(--entries);
- brelse(bh);
}
+ brelse(bh);
error = gfs2_meta_inode_buffer(dip, &bh);
if (error)
* Returns: 1 if alloc required, 0 if not, -ve on error
*/
-int gfs2_diradd_alloc_required(struct inode *inode,
- const struct qstr *name)
+int gfs2_diradd_alloc_required(struct inode *inode, const struct qstr *name)
{
struct gfs2_dirent *dent;
struct buffer_head *bh;
dent = gfs2_dirent_search(inode, name, gfs2_dirent_find_space, &bh);
- if (!dent)
+ if (!dent) {
return 1;
+ }
if (IS_ERR(dent))
return PTR_ERR(dent);
brelse(bh);