Release 4.10 fs/nilfs2/btree.c

Directory: fs/nilfs2
/*
 * btree.c - NILFS B-tree.
 *
 * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * Written by Koji Sato.
 */

#include <linux/slab.h>
#include <linux/string.h>
#include <linux/errno.h>
#include <linux/pagevec.h>
#include "nilfs.h"
#include "page.h"
#include "btnode.h"
#include "btree.h"
#include "alloc.h"
#include "dat.h"

static void __nilfs_btree_init(struct nilfs_bmap *bmap);



static struct nilfs_btree_path *nilfs_btree_alloc_path(void)
{
	struct nilfs_btree_path *path;
	int level = NILFS_BTREE_LEVEL_DATA;

	path = kmem_cache_alloc(nilfs_btree_path_cache, GFP_NOFS);
	if (path == NULL)
		goto out;

	for (; level < NILFS_BTREE_LEVEL_MAX; level++) {
		path[level].bp_bh = NULL;
		path[level].bp_sib_bh = NULL;
		path[level].bp_index = 0;
		path[level].bp_oldreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
		path[level].bp_newreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
		path[level].bp_op = NULL;
	}

out:
	return path;
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 88 77.88% 1 33.33%
li hong li hong 24 21.24% 1 33.33%
ryusuke konishi ryusuke konishi 1 0.88% 1 33.33%
Total 113 100.00% 3 100.00%



static void nilfs_btree_free_path(struct nilfs_btree_path *path)
{
	int level = NILFS_BTREE_LEVEL_DATA;

	for (; level < NILFS_BTREE_LEVEL_MAX; level++)
		brelse(path[level].bp_bh);

	kmem_cache_free(nilfs_btree_path_cache, path);
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 23 53.49% 1 25.00%
li hong li hong 19 44.19% 2 50.00%
ryusuke konishi ryusuke konishi 1 2.33% 1 25.00%
Total 43 100.00% 4 100.00%

/*
 * B-tree node operations
 */


static int nilfs_btree_get_new_block(const struct nilfs_bmap *btree,
				     __u64 ptr, struct buffer_head **bhp)
{
	struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache;
	struct buffer_head *bh;

	bh = nilfs_btnode_create_block(btnc, ptr);
	if (!bh)
		return -ENOMEM;

	set_buffer_nilfs_volatile(bh);
	*bhp = bh;
	return 0;
}

Contributors
Person Tokens Prop Commits CommitProp
ryusuke konishi ryusuke konishi 70 100.00% 3 100.00%
Total 70 100.00% 3 100.00%



static int nilfs_btree_node_get_flags(const struct nilfs_btree_node *node)
{
	return node->bn_flags;
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 17 100.00% 1 100.00%
Total 17 100.00% 1 100.00%


static void

nilfs_btree_node_set_flags(struct nilfs_btree_node *node, int flags)
{
	node->bn_flags = flags;
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 20 100.00% 1 100.00%
Total 20 100.00% 1 100.00%



static int nilfs_btree_node_root(const struct nilfs_btree_node *node)
{
	return nilfs_btree_node_get_flags(node) & NILFS_BTREE_NODE_ROOT;
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 20 100.00% 1 100.00%
Total 20 100.00% 1 100.00%



static int nilfs_btree_node_get_level(const struct nilfs_btree_node *node)
{
	return node->bn_level;
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 17 100.00% 1 100.00%
Total 17 100.00% 1 100.00%


static void

nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level)
{
	node->bn_level = level;
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 20 100.00% 1 100.00%
Total 20 100.00% 1 100.00%



static int nilfs_btree_node_get_nchildren(const struct nilfs_btree_node *node)
{
	return le16_to_cpu(node->bn_nchildren);
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 20 100.00% 1 100.00%
Total 20 100.00% 1 100.00%


static void

nilfs_btree_node_set_nchildren(struct nilfs_btree_node *node, int nchildren)
{
	node->bn_nchildren = cpu_to_le16(nchildren);
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 23 100.00% 1 100.00%
Total 23 100.00% 1 100.00%



static int nilfs_btree_node_size(const struct nilfs_bmap *btree)
{
	return 1 << btree->b_inode->i_blkbits;
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 20 95.24% 1 50.00%
ryusuke konishi ryusuke konishi 1 4.76% 1 50.00%
Total 21 100.00% 2 100.00%



static int nilfs_btree_nchildren_per_block(const struct nilfs_bmap *btree)
{
	return btree->b_nchildren_per_block;
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 12 70.59% 1 20.00%
ryusuke konishi ryusuke konishi 5 29.41% 4 80.00%
Total 17 100.00% 5 100.00%


static __le64 *

nilfs_btree_node_dkeys(const struct nilfs_btree_node *node)
{
	return (__le64 *)((char *)(node + 1) +
			  (nilfs_btree_node_root(node) ?
			   0 : NILFS_BTREE_NODE_EXTRA_PAD_SIZE));
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 41 100.00% 1 100.00%
Total 41 100.00% 1 100.00%


static __le64 *

nilfs_btree_node_dptrs(const struct nilfs_btree_node *node, int ncmax)
{
	return (__le64 *)(nilfs_btree_node_dkeys(node) + ncmax);
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 25 83.33% 1 33.33%
ryusuke konishi ryusuke konishi 5 16.67% 2 66.67%
Total 30 100.00% 3 100.00%


static __u64

nilfs_btree_node_get_key(const struct nilfs_btree_node *node, int index)
{
	return le64_to_cpu(*(nilfs_btree_node_dkeys(node) + index));
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 28 96.55% 1 50.00%
ryusuke konishi ryusuke konishi 1 3.45% 1 50.00%
Total 29 100.00% 2 100.00%


static void

nilfs_btree_node_set_key(struct nilfs_btree_node *node, int index, __u64 key)
{
	*(nilfs_btree_node_dkeys(node) + index) = cpu_to_le64(key);
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 31 96.88% 1 50.00%
ryusuke konishi ryusuke konishi 1 3.12% 1 50.00%
Total 32 100.00% 2 100.00%


static __u64

nilfs_btree_node_get_ptr(const struct nilfs_btree_node *node, int index,
			 int ncmax)
{
	return le64_to_cpu(*(nilfs_btree_node_dptrs(node, ncmax) + index));
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 28 82.35% 1 25.00%
ryusuke konishi ryusuke konishi 6 17.65% 3 75.00%
Total 34 100.00% 4 100.00%


static void

nilfs_btree_node_set_ptr(struct nilfs_btree_node *node, int index, __u64 ptr,
			 int ncmax)
{
	*(nilfs_btree_node_dptrs(node, ncmax) + index) = cpu_to_le64(ptr);
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 31 83.78% 1 25.00%
ryusuke konishi ryusuke konishi 6 16.22% 3 75.00%
Total 37 100.00% 4 100.00%



static void nilfs_btree_node_init(struct nilfs_btree_node *node, int flags,
				  int level, int nchildren, int ncmax,
				  const __u64 *keys, const __u64 *ptrs)
{
	__le64 *dkeys;
	__le64 *dptrs;
	int i;

	nilfs_btree_node_set_flags(node, flags);
	nilfs_btree_node_set_level(node, level);
	nilfs_btree_node_set_nchildren(node, nchildren);

	dkeys = nilfs_btree_node_dkeys(node);
	dptrs = nilfs_btree_node_dptrs(node, ncmax);
	for (i = 0; i < nchildren; i++) {
		dkeys[i] = cpu_to_le64(keys[i]);
		dptrs[i] = cpu_to_le64(ptrs[i]);
	}
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 115 94.26% 1 25.00%
ryusuke konishi ryusuke konishi 7 5.74% 3 75.00%
Total 122 100.00% 4 100.00%

/* Assume the buffer heads corresponding to left and right are locked. */


static void nilfs_btree_node_move_left(struct nilfs_btree_node *left,
				       struct nilfs_btree_node *right,
				       int n, int lncmax, int rncmax)
{
	__le64 *ldkeys, *rdkeys;
	__le64 *ldptrs, *rdptrs;
	int lnchildren, rnchildren;

	ldkeys = nilfs_btree_node_dkeys(left);
	ldptrs = nilfs_btree_node_dptrs(left, lncmax);
	lnchildren = nilfs_btree_node_get_nchildren(left);

	rdkeys = nilfs_btree_node_dkeys(right);
	rdptrs = nilfs_btree_node_dptrs(right, rncmax);
	rnchildren = nilfs_btree_node_get_nchildren(right);

	memcpy(ldkeys + lnchildren, rdkeys, n * sizeof(*rdkeys));
	memcpy(ldptrs + lnchildren, rdptrs, n * sizeof(*rdptrs));
	memmove(rdkeys, rdkeys + n, (rnchildren - n) * sizeof(*rdkeys));
	memmove(rdptrs, rdptrs + n, (rnchildren - n) * sizeof(*rdptrs));

	lnchildren += n;
	rnchildren -= n;
	nilfs_btree_node_set_nchildren(left, lnchildren);
	nilfs_btree_node_set_nchildren(right, rnchildren);
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 178 94.68% 1 33.33%
ryusuke konishi ryusuke konishi 10 5.32% 2 66.67%
Total 188 100.00% 3 100.00%

/* Assume that the buffer heads corresponding to left and right are locked. */


static void nilfs_btree_node_move_right(struct nilfs_btree_node *left,
					struct nilfs_btree_node *right,
					int n, int lncmax, int rncmax)
{
	__le64 *ldkeys, *rdkeys;
	__le64 *ldptrs, *rdptrs;
	int lnchildren, rnchildren;

	ldkeys = nilfs_btree_node_dkeys(left);
	ldptrs = nilfs_btree_node_dptrs(left, lncmax);
	lnchildren = nilfs_btree_node_get_nchildren(left);

	rdkeys = nilfs_btree_node_dkeys(right);
	rdptrs = nilfs_btree_node_dptrs(right, rncmax);
	rnchildren = nilfs_btree_node_get_nchildren(right);

	memmove(rdkeys + n, rdkeys, rnchildren * sizeof(*rdkeys));
	memmove(rdptrs + n, rdptrs, rnchildren * sizeof(*rdptrs));
	memcpy(rdkeys, ldkeys + lnchildren - n, n * sizeof(*rdkeys));
	memcpy(rdptrs, ldptrs + lnchildren - n, n * sizeof(*rdptrs));

	lnchildren -= n;
	rnchildren += n;
	nilfs_btree_node_set_nchildren(left, lnchildren);
	nilfs_btree_node_set_nchildren(right, rnchildren);
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 174 94.57% 1 33.33%
ryusuke konishi ryusuke konishi 10 5.43% 2 66.67%
Total 184 100.00% 3 100.00%

/* Assume that the buffer head corresponding to node is locked. */


static void nilfs_btree_node_insert(struct nilfs_btree_node *node, int index,
				    __u64 key, __u64 ptr, int ncmax)
{
	__le64 *dkeys;
	__le64 *dptrs;
	int nchildren;

	dkeys = nilfs_btree_node_dkeys(node);
	dptrs = nilfs_btree_node_dptrs(node, ncmax);
	nchildren = nilfs_btree_node_get_nchildren(node);
	if (index < nchildren) {
		memmove(dkeys + index + 1, dkeys + index,
			(nchildren - index) * sizeof(*dkeys));
		memmove(dptrs + index + 1, dptrs + index,
			(nchildren - index) * sizeof(*dptrs));
	}
	dkeys[index] = cpu_to_le64(key);
	dptrs[index] = cpu_to_le64(ptr);
	nchildren++;
	nilfs_btree_node_set_nchildren(node, nchildren);
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 137 94.48% 1 25.00%
ryusuke konishi ryusuke konishi 8 5.52% 3 75.00%
Total 145 100.00% 4 100.00%

/* Assume that the buffer head corresponding to node is locked. */


static void nilfs_btree_node_delete(struct nilfs_btree_node *node, int index,
				    __u64 *keyp, __u64 *ptrp, int ncmax)
{
	__u64 key;
	__u64 ptr;
	__le64 *dkeys;
	__le64 *dptrs;
	int nchildren;

	dkeys = nilfs_btree_node_dkeys(node);
	dptrs = nilfs_btree_node_dptrs(node, ncmax);
	key = le64_to_cpu(dkeys[index]);
	ptr = le64_to_cpu(dptrs[index]);
	nchildren = nilfs_btree_node_get_nchildren(node);
	if (keyp != NULL)
		*keyp = key;
	if (ptrp != NULL)
		*ptrp = ptr;

	if (index < nchildren - 1) {
		memmove(dkeys + index, dkeys + index + 1,
			(nchildren - index - 1) * sizeof(*dkeys));
		memmove(dptrs + index, dptrs + index + 1,
			(nchildren - index - 1) * sizeof(*dptrs));
	}
	nchildren--;
	nilfs_btree_node_set_nchildren(node, nchildren);
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 173 95.58% 1 25.00%
ryusuke konishi ryusuke konishi 8 4.42% 3 75.00%
Total 181 100.00% 4 100.00%



static int nilfs_btree_node_lookup(const struct nilfs_btree_node *node,
				   __u64 key, int *indexp)
{
	__u64 nkey;
	int index, low, high, s;

	/* binary search */
	low = 0;
	high = nilfs_btree_node_get_nchildren(node) - 1;
	index = 0;
	s = 0;
	while (low <= high) {
		index = (low + high) / 2;
		nkey = nilfs_btree_node_get_key(node, index);
		if (nkey == key) {
			s = 0;
			goto out;
		} else if (nkey < key) {
			low = index + 1;
			s = -1;
		} else {
			high = index - 1;
			s = 1;
		}
	}

	/* adjust index */
	if (nilfs_btree_node_get_level(node) > NILFS_BTREE_LEVEL_NODE_MIN) {
		if (s > 0 && index > 0)
			index--;
	} else if (s < 0)
		index++;

 out:
	*indexp = index;

	return s == 0;
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 175 100.00% 1 100.00%
Total 175 100.00% 1 100.00%

/**
 * nilfs_btree_node_broken - verify consistency of btree node
 * @node: btree node block to be examined
 * @size: node size (in bytes)
 * @inode: host inode of btree
 * @blocknr: block number
 *
 * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
 */


static int nilfs_btree_node_broken(const struct nilfs_btree_node *node,
				   size_t size, struct inode *inode,
				   sector_t blocknr)
{
	int level, flags, nchildren;
	int ret = 0;

	level = nilfs_btree_node_get_level(node);
	flags = nilfs_btree_node_get_flags(node);
	nchildren = nilfs_btree_node_get_nchildren(node);

	if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||
		     level >= NILFS_BTREE_LEVEL_MAX ||
		     (flags & NILFS_BTREE_NODE_ROOT) ||
		     nchildren < 0 ||
		     nchildren > NILFS_BTREE_NODE_NCHILDREN_MAX(size))) {
		nilfs_msg(inode->i_sb, KERN_CRIT,
			  "bad btree node (ino=%lu, blocknr=%llu): level = %d, flags = 0x%x, nchildren = %d",
			  inode->i_ino, (unsigned long long)blocknr, level,
			  flags, nchildren);
		ret = 1;
	}
	return ret;
}

Contributors
Person Tokens Prop Commits CommitProp
ryusuke konishi ryusuke konishi 123 100.00% 2 100.00%
Total 123 100.00% 2 100.00%

/**
 * nilfs_btree_root_broken - verify consistency of btree root node
 * @node: btree root node to be examined
 * @inode: host inode of btree
 *
 * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
 */


static int nilfs_btree_root_broken(const struct nilfs_btree_node *node,
				   struct inode *inode)
{
	int level, flags, nchildren;
	int ret = 0;

	level = nilfs_btree_node_get_level(node);
	flags = nilfs_btree_node_get_flags(node);
	nchildren = nilfs_btree_node_get_nchildren(node);

	if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||
		     level >= NILFS_BTREE_LEVEL_MAX ||
		     nchildren < 0 ||
		     nchildren > NILFS_BTREE_ROOT_NCHILDREN_MAX)) {
		nilfs_msg(inode->i_sb, KERN_CRIT,
			  "bad btree root (ino=%lu): level = %d, flags = 0x%x, nchildren = %d",
			  inode->i_ino, level, flags, nchildren);
		ret = 1;
	}
	return ret;
}

Contributors
Person Tokens Prop Commits CommitProp
ryusuke konishi ryusuke konishi 101 100.00% 3 100.00%
Total 101 100.00% 3 100.00%



int nilfs_btree_broken_node_block(struct buffer_head *bh)
{
	struct inode *inode;
	int ret;

	if (buffer_nilfs_checked(bh))
		return 0;

	inode = bh->b_page->mapping->host;
	ret = nilfs_btree_node_broken((struct nilfs_btree_node *)bh->b_data,
				      bh->b_size, inode, bh->b_blocknr);
	if (likely(!ret))
		set_buffer_nilfs_checked(bh);
	return ret;
}

Contributors
Person Tokens Prop Commits CommitProp
ryusuke konishi ryusuke konishi 78 100.00% 3 100.00%
Total 78 100.00% 3 100.00%


static struct nilfs_btree_node *

nilfs_btree_get_root(const struct nilfs_bmap *btree)
{
	return (struct nilfs_btree_node *)btree->b_u.u_data;
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 25 96.15% 1 50.00%
ryusuke konishi ryusuke konishi 1 3.85% 1 50.00%
Total 26 100.00% 2 100.00%


static struct nilfs_btree_node *

nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level)
{
	return (struct nilfs_btree_node *)path[level].bp_bh->b_data;
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 32 100.00% 1 100.00%
Total 32 100.00% 1 100.00%


static struct nilfs_btree_node *

nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level)
{
	return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data;
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 32 100.00% 1 100.00%
Total 32 100.00% 1 100.00%



static int nilfs_btree_height(const struct nilfs_bmap *btree)
{
	return nilfs_btree_node_get_level(nilfs_btree_get_root(btree)) + 1;
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 22 95.65% 1 50.00%
ryusuke konishi ryusuke konishi 1 4.35% 1 50.00%
Total 23 100.00% 2 100.00%


static struct nilfs_btree_node *

nilfs_btree_get_node(const struct nilfs_bmap *btree,
		     const struct nilfs_btree_path *path,
		     int level, int *ncmaxp)
{
	struct nilfs_btree_node *node;

	if (level == nilfs_btree_height(btree) - 1) {
		node = nilfs_btree_get_root(btree);
		*ncmaxp = NILFS_BTREE_ROOT_NCHILDREN_MAX;
	} else {
		node = nilfs_btree_get_nonroot_node(path, level);
		*ncmaxp = nilfs_btree_nchildren_per_block(btree);
	}
	return node;
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 41 51.25% 1 33.33%
ryusuke konishi ryusuke konishi 39 48.75% 2 66.67%
Total 80 100.00% 3 100.00%



static int nilfs_btree_bad_node(const struct nilfs_bmap *btree,
				struct nilfs_btree_node *node, int level)
{
	if (unlikely(nilfs_btree_node_get_level(node) != level)) {
		dump_stack();
		nilfs_msg(btree->b_inode->i_sb, KERN_CRIT,
			  "btree level mismatch (ino=%lu): %d != %d",
			  btree->b_inode->i_ino,
			  nilfs_btree_node_get_level(node), level);
		return 1;
	}
	return 0;
}

Contributors
Person Tokens Prop Commits CommitProp
ryusuke konishi ryusuke konishi 69 100.00% 2 100.00%
Total 69 100.00% 2 100.00%


struct nilfs_btree_readahead_info {
	
struct nilfs_btree_node *node;	/* parent node */
	
int max_ra_blocks;		/* max nof blocks to read ahead */
	
int index;			/* current index on the parent node */
	
int ncmax;			/* nof children in the parent node */
};



static int __nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
				   struct buffer_head **bhp,
				   const struct nilfs_btree_readahead_info *ra)
{
	struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache;
	struct buffer_head *bh, *ra_bh;
	sector_t submit_ptr = 0;
	int ret;

	ret = nilfs_btnode_submit_block(btnc, ptr, 0, REQ_OP_READ, 0, &bh,
					&submit_ptr);
	if (ret) {
		if (ret != -EEXIST)
			return ret;
		goto out_check;
	}

	if (ra) {
		int i, n;
		__u64 ptr2;

		/* read ahead sibling nodes */
		for (n = ra->max_ra_blocks, i = ra->index + 1;
		     n > 0 && i < ra->ncmax; n--, i++) {
			ptr2 = nilfs_btree_node_get_ptr(ra->node, i, ra->ncmax);

			ret = nilfs_btnode_submit_block(btnc, ptr2, 0,
							REQ_OP_READ, REQ_RAHEAD,
							&ra_bh, &submit_ptr);
			if (likely(!ret || ret == -EEXIST))
				brelse(ra_bh);
			else if (ret != -EBUSY)
				break;
			if (!buffer_locked(bh))
				goto out_no_wait;
		}
	}

	wait_on_buffer(bh);

 out_no_wait:
	if (!buffer_uptodate(bh)) {
		nilfs_msg(btree->b_inode->i_sb, KERN_ERR,
			  "I/O error reading b-tree node block (ino=%lu, blocknr=%llu)",
			  btree->b_inode->i_ino, (unsigned long long)ptr);
		brelse(bh);
		return -EIO;
	}

 out_check:
	if (nilfs_btree_broken_node_block(bh)) {
		clear_buffer_uptodate(bh);
		brelse(bh);
		return -EINVAL;
	}

	*bhp = bh;
	return 0;
}

Contributors
Person Tokens Prop Commits CommitProp
ryusuke konishi ryusuke konishi 298 98.03% 2 66.67%
michael christie michael christie 6 1.97% 1 33.33%
Total 304 100.00% 3 100.00%



static int nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
				   struct buffer_head **bhp)
{
	return __nilfs_btree_get_block(btree, ptr, bhp, NULL);
}

Contributors
Person Tokens Prop Commits CommitProp
ryusuke konishi ryusuke konishi 33 100.00% 1 100.00%
Total 33 100.00% 1 100.00%



static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree,
				 struct nilfs_btree_path *path,
				 __u64 key, __u64 *ptrp, int minlevel,
				 int readahead)
{
	struct nilfs_btree_node *node;
	struct nilfs_btree_readahead_info p, *ra;
	__u64 ptr;
	int level, index, found, ncmax, ret;

	node = nilfs_btree_get_root(btree);
	level = nilfs_btree_node_get_level(node);
	if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0)
		return -ENOENT;

	found = nilfs_btree_node_lookup(node, key, &index);
	ptr = nilfs_btree_node_get_ptr(node, index,
				       NILFS_BTREE_ROOT_NCHILDREN_MAX);
	path[level].bp_bh = NULL;
	path[level].bp_index = index;

	ncmax = nilfs_btree_nchildren_per_block(btree);

	while (--level >= minlevel) {
		ra = NULL;
		if (level == NILFS_BTREE_LEVEL_NODE_MIN && readahead) {
			p.node = nilfs_btree_get_node(btree, path, level + 1,
						      &p.ncmax);
			p.index = index;
			p.max_ra_blocks = 7;
			ra = &p;
		}
		ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh,
					      ra);
		if (ret < 0)
			return ret;

		node = nilfs_btree_get_nonroot_node(path, level);
		if (nilfs_btree_bad_node(btree, node, level))
			return -EINVAL;
		if (!found)
			found = nilfs_btree_node_lookup(node, key, &index);
		else
			index = 0;
		if (index < ncmax) {
			ptr = nilfs_btree_node_get_ptr(node, index, ncmax);
		} else {
			WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN);
			/* insert */
			ptr = NILFS_BMAP_INVALID_PTR;
		}
		path[level].bp_index = index;
	}
	if (!found)
		return -ENOENT;

	if (ptrp != NULL)
		*ptrp = ptr;

	return 0;
}

Contributors
Person Tokens Prop Commits CommitProp
koji sato koji sato 241 71.51% 1 12.50%
ryusuke konishi ryusuke konishi 96 28.49% 7 87.50%
Total 337 100.00% 8 100.00%



static int nilfs_btree_do_lookup_last(const struct nilfs_bmap *btree,
				      struct nilfs_btree_path *path,
				      __u64 *keyp, __u64 *ptrp)
{
	struct nilfs_btree_node *node;
	__u64 ptr;
	int index, level, ncmax, ret;

	node = nilfs_btree_get_root(btree)
	Person	Tokens	Prop	Commits	CommitProp
koji sato	koji sato	88	77.88%	1	33.33%
li hong	li hong	24	21.24%	1	33.33%
ryusuke konishi	ryusuke konishi	1	0.88%	1	33.33%
	Total	113	100.00%	3	100.00%
cregit-Linux how code gets into the kernel

Release 4.10 fs/nilfs2/btree.c

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors
