lkml.org 
[lkml]   [2008]   [Sep]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH 16/39] ocfs2: Add xattr lookup code xattr btrees
    Date
    From: Tao Ma <tao.ma@oracle.com>

    Add code to lookup a given extended attribute in the xattr btree. Lookup
    follows this general scheme:

    1. Use ocfs2_xattr_get_rec to find the xattr extent record

    2. Find the xattr bucket within the extent which may contain this xattr

    3. Iterate the bucket to find the xattr. In ocfs2_xattr_block_get(), we need
    to recalcuate the block offset and name offset for the right position of
    name/value.

    Signed-off-by: Tao Ma <tao.ma@oracle.com>
    Signed-off-by: Mark Fasheh <mfasheh@suse.com>
    ---
    fs/ocfs2/xattr.c | 351 ++++++++++++++++++++++++++++++++++++++++++++++++++----
    1 files changed, 328 insertions(+), 23 deletions(-)

    diff --git a/fs/ocfs2/xattr.c b/fs/ocfs2/xattr.c
    index fb17f7f..acccdfa 100644
    --- a/fs/ocfs2/xattr.c
    +++ b/fs/ocfs2/xattr.c
    @@ -99,12 +99,25 @@ struct ocfs2_xattr_search {
    */
    struct buffer_head *xattr_bh;
    struct ocfs2_xattr_header *header;
    + struct ocfs2_xattr_bucket bucket;
    void *base;
    void *end;
    struct ocfs2_xattr_entry *here;
    int not_found;
    };

    +static int ocfs2_xattr_bucket_get_name_value(struct inode *inode,
    + struct ocfs2_xattr_header *xh,
    + int index,
    + int *block_off,
    + int *new_offset);
    +
    +static int ocfs2_xattr_index_block_find(struct inode *inode,
    + struct buffer_head *root_bh,
    + int name_index,
    + const char *name,
    + struct ocfs2_xattr_search *xs);
    +
    static int ocfs2_xattr_tree_list_index_block(struct inode *inode,
    struct ocfs2_xattr_tree_root *xt,
    char *buffer,
    @@ -604,7 +617,7 @@ static int ocfs2_xattr_find_entry(int name_index,
    }

    static int ocfs2_xattr_get_value_outside(struct inode *inode,
    - struct ocfs2_xattr_search *xs,
    + struct ocfs2_xattr_value_root *xv,
    void *buffer,
    size_t len)
    {
    @@ -613,12 +626,8 @@ static int ocfs2_xattr_get_value_outside(struct inode *inode,
    int i, ret = 0;
    size_t cplen, blocksize;
    struct buffer_head *bh = NULL;
    - struct ocfs2_xattr_value_root *xv;
    struct ocfs2_extent_list *el;

    - xv = (struct ocfs2_xattr_value_root *)
    - (xs->base + le16_to_cpu(xs->here->xe_name_offset) +
    - OCFS2_XATTR_SIZE(xs->here->xe_name_len));
    el = &xv->xr_list;
    clusters = le32_to_cpu(xv->xr_clusters);
    bpc = ocfs2_clusters_to_blocks(inode->i_sb, 1);
    @@ -668,6 +677,7 @@ static int ocfs2_xattr_ibody_get(struct inode *inode,
    {
    struct ocfs2_inode_info *oi = OCFS2_I(inode);
    struct ocfs2_dinode *di = (struct ocfs2_dinode *)xs->inode_bh->b_data;
    + struct ocfs2_xattr_value_root *xv;
    size_t size;
    int ret = 0;

    @@ -692,7 +702,11 @@ static int ocfs2_xattr_ibody_get(struct inode *inode,
    le16_to_cpu(xs->here->xe_name_offset) +
    OCFS2_XATTR_SIZE(xs->here->xe_name_len), size);
    } else {
    - ret = ocfs2_xattr_get_value_outside(inode, xs,
    + xv = (struct ocfs2_xattr_value_root *)
    + (xs->base + le16_to_cpu(
    + xs->here->xe_name_offset) +
    + OCFS2_XATTR_SIZE(xs->here->xe_name_len));
    + ret = ocfs2_xattr_get_value_outside(inode, xv,
    buffer, size);
    if (ret < 0) {
    mlog_errno(ret);
    @@ -714,12 +728,15 @@ static int ocfs2_xattr_block_get(struct inode *inode,
    struct ocfs2_dinode *di = (struct ocfs2_dinode *)xs->inode_bh->b_data;
    struct buffer_head *blk_bh = NULL;
    struct ocfs2_xattr_block *xb;
    + struct ocfs2_xattr_value_root *xv;
    size_t size;
    - int ret = -ENODATA;
    + int ret = -ENODATA, name_offset, name_len, block_off, i;

    if (!di->i_xattr_loc)
    return ret;

    + memset(&xs->bucket, 0, sizeof(xs->bucket));
    +
    ret = ocfs2_read_block(OCFS2_SB(inode->i_sb),
    le64_to_cpu(di->i_xattr_loc),
    &blk_bh, OCFS2_BH_CACHED, inode);
    @@ -736,12 +753,19 @@ static int ocfs2_xattr_block_get(struct inode *inode,

    xs->xattr_bh = blk_bh;
    xb = (struct ocfs2_xattr_block *)blk_bh->b_data;
    - xs->header = &xb->xb_attrs.xb_header;
    - xs->base = (void *)xs->header;
    - xs->end = (void *)(blk_bh->b_data) + blk_bh->b_size;
    - xs->here = xs->header->xh_entries;

    - ret = ocfs2_xattr_find_entry(name_index, name, xs);
    + if (!(le16_to_cpu(xb->xb_flags) & OCFS2_XATTR_INDEXED)) {
    + xs->header = &xb->xb_attrs.xb_header;
    + xs->base = (void *)xs->header;
    + xs->end = (void *)(blk_bh->b_data) + blk_bh->b_size;
    + xs->here = xs->header->xh_entries;
    +
    + ret = ocfs2_xattr_find_entry(name_index, name, xs);
    + } else
    + ret = ocfs2_xattr_index_block_find(inode, blk_bh,
    + name_index,
    + name, xs);
    +
    if (ret)
    goto cleanup;
    size = le64_to_cpu(xs->here->xe_value_size);
    @@ -749,12 +773,26 @@ static int ocfs2_xattr_block_get(struct inode *inode,
    ret = -ERANGE;
    if (size > buffer_size)
    goto cleanup;
    +
    + name_offset = le16_to_cpu(xs->here->xe_name_offset);
    + name_len = OCFS2_XATTR_SIZE(xs->here->xe_name_len);
    + i = xs->here - xs->header->xh_entries;
    +
    + if (le16_to_cpu(xb->xb_flags) & OCFS2_XATTR_INDEXED) {
    + ret = ocfs2_xattr_bucket_get_name_value(inode,
    + xs->bucket.xh,
    + i,
    + &block_off,
    + &name_offset);
    + xs->base = xs->bucket.bhs[block_off]->b_data;
    + }
    if (ocfs2_xattr_is_local(xs->here)) {
    memcpy(buffer, (void *)xs->base +
    - le16_to_cpu(xs->here->xe_name_offset) +
    - OCFS2_XATTR_SIZE(xs->here->xe_name_len), size);
    + name_offset + name_len, size);
    } else {
    - ret = ocfs2_xattr_get_value_outside(inode, xs,
    + xv = (struct ocfs2_xattr_value_root *)
    + (xs->base + name_offset + name_len);
    + ret = ocfs2_xattr_get_value_outside(inode, xv,
    buffer, size);
    if (ret < 0) {
    mlog_errno(ret);
    @@ -764,8 +802,11 @@ static int ocfs2_xattr_block_get(struct inode *inode,
    }
    ret = size;
    cleanup:
    - brelse(blk_bh);
    + for (i = 0; i < OCFS2_XATTR_MAX_BLOCKS_PER_BUCKET; i++)
    + brelse(xs->bucket.bhs[i]);
    + memset(&xs->bucket, 0, sizeof(xs->bucket));

    + brelse(blk_bh);
    return ret;
    }

    @@ -1679,6 +1720,7 @@ static int ocfs2_xattr_block_find(struct inode *inode,
    {
    struct ocfs2_dinode *di = (struct ocfs2_dinode *)xs->inode_bh->b_data;
    struct buffer_head *blk_bh = NULL;
    + struct ocfs2_xattr_block *xb;
    int ret = 0;

    if (!di->i_xattr_loc)
    @@ -1699,20 +1741,26 @@ static int ocfs2_xattr_block_find(struct inode *inode,
    }

    xs->xattr_bh = blk_bh;
    - xs->header = &((struct ocfs2_xattr_block *)blk_bh->b_data)->
    - xb_attrs.xb_header;
    - xs->base = (void *)xs->header;
    - xs->end = (void *)(blk_bh->b_data) + blk_bh->b_size;
    - xs->here = xs->header->xh_entries;
    + xb = (struct ocfs2_xattr_block *)blk_bh->b_data;
    +
    + if (!(le16_to_cpu(xb->xb_flags) & OCFS2_XATTR_INDEXED)) {
    + xs->header = &xb->xb_attrs.xb_header;
    + xs->base = (void *)xs->header;
    + xs->end = (void *)(blk_bh->b_data) + blk_bh->b_size;
    + xs->here = xs->header->xh_entries;
    +
    + ret = ocfs2_xattr_find_entry(name_index, name, xs);
    + } else
    + ret = ocfs2_xattr_index_block_find(inode, blk_bh,
    + name_index,
    + name, xs);

    - ret = ocfs2_xattr_find_entry(name_index, name, xs);
    if (ret && ret != -ENODATA) {
    xs->xattr_bh = NULL;
    goto cleanup;
    }
    xs->not_found = ret;
    return 0;
    -
    cleanup:
    brelse(blk_bh);

    @@ -1941,6 +1989,18 @@ cleanup:
    return ret;
    }

    +static inline u32 ocfs2_xattr_hash_by_name(struct inode *inode,
    + int name_index,
    + const char *suffix_name)
    +{
    + struct xattr_handler *handler = ocfs2_xattr_handler(name_index);
    + char *prefix = handler->prefix;
    + int prefix_len = strlen(handler->prefix);
    +
    + return ocfs2_xattr_name_hash(inode, prefix, prefix_len,
    + (char *)suffix_name, strlen(suffix_name));
    +}
    +
    /*
    * Find the xattr extent rec which may contains name_hash.
    * e_cpos will be the first name hash of the xattr rec.
    @@ -2010,6 +2070,251 @@ typedef int (xattr_bucket_func)(struct inode *inode,
    struct ocfs2_xattr_bucket *bucket,
    void *para);

    +static int ocfs2_find_xe_in_bucket(struct inode *inode,
    + struct buffer_head *header_bh,
    + int name_index,
    + const char *name,
    + u32 name_hash,
    + u16 *xe_index,
    + int *found)
    +{
    + int i, ret = 0, cmp = 1, block_off, new_offset;
    + struct ocfs2_xattr_header *xh =
    + (struct ocfs2_xattr_header *)header_bh->b_data;
    + size_t name_len = strlen(name);
    + struct ocfs2_xattr_entry *xe = NULL;
    + struct buffer_head *name_bh = NULL;
    + char *xe_name;
    +
    + /*
    + * We don't use binary search in the bucket because there
    + * may be multiple entries with the same name hash.
    + */
    + for (i = 0; i < le16_to_cpu(xh->xh_count); i++) {
    + xe = &xh->xh_entries[i];
    +
    + if (name_hash > le32_to_cpu(xe->xe_name_hash))
    + continue;
    + else if (name_hash < le32_to_cpu(xe->xe_name_hash))
    + break;
    +
    + cmp = name_index - ocfs2_xattr_get_type(xe);
    + if (!cmp)
    + cmp = name_len - xe->xe_name_len;
    + if (cmp)
    + continue;
    +
    + ret = ocfs2_xattr_bucket_get_name_value(inode,
    + xh,
    + i,
    + &block_off,
    + &new_offset);
    + if (ret) {
    + mlog_errno(ret);
    + break;
    + }
    +
    + ret = ocfs2_read_block(OCFS2_SB(inode->i_sb),
    + header_bh->b_blocknr + block_off,
    + &name_bh, OCFS2_BH_CACHED, inode);
    + if (ret) {
    + mlog_errno(ret);
    + break;
    + }
    + xe_name = name_bh->b_data + new_offset;
    +
    + cmp = memcmp(name, xe_name, name_len);
    + brelse(name_bh);
    + name_bh = NULL;
    +
    + if (cmp == 0) {
    + *xe_index = i;
    + *found = 1;
    + ret = 0;
    + break;
    + }
    + }
    +
    + return ret;
    +}
    +
    +/*
    + * Find the specified xattr entry in a series of buckets.
    + * This series start from p_blkno and last for num_clusters.
    + * The ocfs2_xattr_header.xh_num_buckets of the first bucket contains
    + * the num of the valid buckets.
    + *
    + * Return the buffer_head this xattr should reside in. And if the xattr's
    + * hash is in the gap of 2 buckets, return the lower bucket.
    + */
    +static int ocfs2_xattr_bucket_find(struct inode *inode,
    + int name_index,
    + const char *name,
    + u32 name_hash,
    + u64 p_blkno,
    + u32 first_hash,
    + u32 num_clusters,
    + struct ocfs2_xattr_search *xs)
    +{
    + int ret, found = 0;
    + struct buffer_head *bh = NULL;
    + struct buffer_head *lower_bh = NULL;
    + struct ocfs2_xattr_header *xh = NULL;
    + struct ocfs2_xattr_entry *xe = NULL;
    + u16 index = 0;
    + u16 blk_per_bucket = ocfs2_blocks_per_xattr_bucket(inode->i_sb);
    + int low_bucket = 0, bucket, high_bucket;
    + u32 last_hash;
    + u64 blkno;
    +
    + ret = ocfs2_read_block(OCFS2_SB(inode->i_sb), p_blkno,
    + &bh, OCFS2_BH_CACHED, inode);
    + if (ret) {
    + mlog_errno(ret);
    + goto out;
    + }
    +
    + xh = (struct ocfs2_xattr_header *)bh->b_data;
    + high_bucket = le16_to_cpu(xh->xh_num_buckets) - 1;
    +
    + while (low_bucket <= high_bucket) {
    + brelse(bh);
    + bh = NULL;
    + bucket = (low_bucket + high_bucket) / 2;
    +
    + blkno = p_blkno + bucket * blk_per_bucket;
    +
    + ret = ocfs2_read_block(OCFS2_SB(inode->i_sb), blkno,
    + &bh, OCFS2_BH_CACHED, inode);
    + if (ret) {
    + mlog_errno(ret);
    + goto out;
    + }
    +
    + xh = (struct ocfs2_xattr_header *)bh->b_data;
    + xe = &xh->xh_entries[0];
    + if (name_hash < le32_to_cpu(xe->xe_name_hash)) {
    + high_bucket = bucket - 1;
    + continue;
    + }
    +
    + /*
    + * Check whether the hash of the last entry in our
    + * bucket is larger than the search one.
    + */
    + xe = &xh->xh_entries[le16_to_cpu(xh->xh_count) - 1];
    + last_hash = le32_to_cpu(xe->xe_name_hash);
    +
    + /* record lower_bh which may be the insert place. */
    + brelse(lower_bh);
    + lower_bh = bh;
    + bh = NULL;
    +
    + if (name_hash > le32_to_cpu(xe->xe_name_hash)) {
    + low_bucket = bucket + 1;
    + continue;
    + }
    +
    + /* the searched xattr should reside in this bucket if exists. */
    + ret = ocfs2_find_xe_in_bucket(inode, lower_bh,
    + name_index, name, name_hash,
    + &index, &found);
    + if (ret) {
    + mlog_errno(ret);
    + goto out;
    + }
    + break;
    + }
    +
    + /*
    + * Record the bucket we have found.
    + * When the xattr's hash value is in the gap of 2 buckets, we will
    + * always set it to the previous bucket.
    + */
    + if (!lower_bh) {
    + /*
    + * We can't find any bucket whose first name_hash is less
    + * than the find name_hash.
    + */
    + BUG_ON(bh->b_blocknr != p_blkno);
    + lower_bh = bh;
    + bh = NULL;
    + }
    + xs->bucket.bhs[0] = lower_bh;
    + xs->bucket.xh = (struct ocfs2_xattr_header *)
    + xs->bucket.bhs[0]->b_data;
    + lower_bh = NULL;
    +
    + xs->header = xs->bucket.xh;
    + xs->base = xs->bucket.bhs[0]->b_data;
    + xs->end = xs->base + inode->i_sb->s_blocksize;
    +
    + if (found) {
    + /*
    + * If we have found the xattr enty, read all the blocks in
    + * this bucket.
    + */
    + ret = ocfs2_read_blocks(OCFS2_SB(inode->i_sb),
    + xs->bucket.bhs[0]->b_blocknr + 1,
    + blk_per_bucket - 1, &xs->bucket.bhs[1],
    + OCFS2_BH_CACHED, inode);
    + if (ret) {
    + mlog_errno(ret);
    + goto out;
    + }
    +
    + xs->here = &xs->header->xh_entries[index];
    + mlog(0, "find xattr %s in bucket %llu, entry = %u\n", name,
    + (unsigned long long)xs->bucket.bhs[0]->b_blocknr, index);
    + } else
    + ret = -ENODATA;
    +
    +out:
    + brelse(bh);
    + brelse(lower_bh);
    + return ret;
    +}
    +
    +static int ocfs2_xattr_index_block_find(struct inode *inode,
    + struct buffer_head *root_bh,
    + int name_index,
    + const char *name,
    + struct ocfs2_xattr_search *xs)
    +{
    + int ret;
    + struct ocfs2_xattr_block *xb =
    + (struct ocfs2_xattr_block *)root_bh->b_data;
    + struct ocfs2_xattr_tree_root *xb_root = &xb->xb_attrs.xb_root;
    + struct ocfs2_extent_list *el = &xb_root->xt_list;
    + u64 p_blkno = 0;
    + u32 first_hash, num_clusters = 0;
    + u32 name_hash = ocfs2_xattr_hash_by_name(inode, name_index, name);
    +
    + if (le16_to_cpu(el->l_next_free_rec) == 0)
    + return -ENODATA;
    +
    + mlog(0, "find xattr %s, hash = %u, index = %d in xattr tree\n",
    + name, name_hash, name_index);
    +
    + ret = ocfs2_xattr_get_rec(inode, name_hash, &p_blkno, &first_hash,
    + &num_clusters, el);
    + if (ret) {
    + mlog_errno(ret);
    + goto out;
    + }
    +
    + BUG_ON(p_blkno == 0 || num_clusters == 0 || first_hash > name_hash);
    +
    + mlog(0, "find xattr extent rec %u clusters from %llu, the first hash "
    + "in the rec is %u\n", num_clusters, p_blkno, first_hash);
    +
    + ret = ocfs2_xattr_bucket_find(inode, name_index, name, name_hash,
    + p_blkno, first_hash, num_clusters, xs);
    +
    +out:
    + return ret;
    +}
    +
    static int ocfs2_iterate_xattr_buckets(struct inode *inode,
    u64 blkno,
    u32 clusters,
    --
    1.5.4.5


    \
     
     \ /
      Last update: 2008-09-25 00:09    [W:0.057 / U:29.708 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site