全部博文（48）
分类： LINUX
2013-01-06 12:07:27
Code documention **You need read this link first.**
Btrfs get/set funcIn btrfs_read_locked_inode(), we can see below codes:
inode_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_inode_item);
inode->i_mode = btrfs_inode_mode(leaf, inode_item);
Because btrfs_inode_mode is same as btrfs_item_offset, we will mainly check later one more carefully.The defination of btrfs_item_ptr:
#define btrfs_item_ptr(leaf, slot, type) \
((type *)(btrfs_leaf_data(leaf) + btrfs_item_offset_nr(leaf, slot)))
struct btrfs_leaf {
struct btrfs_header header;
struct btrfs_item items[];
}
-->btrfs_leaf_data():btrfs_leaf_data() return sizeof(struct btrfs_header).
--> offsetof(struct btrfs_leaf, items):The offset of first item in struct btrfs_leaf.
-->btrfs_item_offset_nr()
-->btrfs_item_nr():Calculate the offset of the 'nr'th item in struct brfs_leaf.
-->btrfs_item_nr_offset(nr)
-->btrfs_item_offset():The offse of the nr-th item in extent_buffer.
-->btrfs_toke_item_offset();
-->map_private_extent_buffer
Below is the defination of btrfs_item_offset:
struct btrfs_item {
struct btrfs_disk_key key;
__le32 offset;
__le32 size;
}
BTRFS_SETGET_FUNCS(item_offset, struct btrfs_item, offset, 32);
The protype of BTRFS_SETGET_FUNCS:
#define BTRFS_SETGET_FUNCS(name, type, member, bits)
In order to simplicity, I do some modification. After replacement:
u32 btrfs_item_offset(struct extent_buffer *eb, struct btrfs_item *s)
{
return btrfs_token_item_offset(eb, s, NULL);
}
u32 btrfs_token_item_offset(struct extent_buffer *eb, struct btrfs_item *s,
struct btrfs_map_token *token)
{
unsigned long part_offset = (unsigned long)s;
//Distances to tagert contains
//the offset of nr-th btrfs_item in btrfs_leaf.
unsigned long offset = part_offset + offsetof(struct btrfs_item, offset);
// location of data pointer
struct btrfs_item *p; int err; char *kaddr; u32 res;
unsigned long map_start, map_len;
unsigned long mem_len = sizeof( ( (struct btrfs_item *)0 )->offset );
if (token && token->kaddr && token->offset <= offset && token->eb == eb
&& (token->offset + PAGE_CACHE_SIZE >= offset + mem_len) )
{
kaddr = token->kaddr;
p = (struct btrfs_item *)(kaddr + part_offset - token->offset);
res = le32_to_cpu(p->member);
return res;
}
err = map_private_extent_buffer(eb, offset, mem_len, &kaddr, &map_start, &map_len);
//paramater offset is data item location pointer
if (err) {
__le32 leres;
read_eb_member(eb, s, struct btrfs_item, offset, &leres);
return le32_to_cpu(leres);
}
p = (struct btrfs_item *)(kaddr + part_offset - map_start);
res = le32_to_cpu(p->offset);
if (token) {
token->kaddr = kaddr;
token->offset = map_start;
token-eb = eb;
}
return res; // the value of btrfs_item member offset , that is the location of data pointer.
}
int map_private_extent_buffer(struct extent_buffer *eb, unsigned long start,unsigned long
min_len, char **map, unsigned long *map_start, unsigned long *map_len)
{
size_t offset = start & (PAGE_CACHE_SIZE - 1);
//start is the offset of n-th item in leaf
char *kaddr;
struct page *p;
size_t start_offset = eb->start & ((u64)PAGE_CACHE_SIZE - 1);
//eb->start is the begining address of this extent_buffer in memory
// start_offset is offset within a page.
unsigned long i = (start_offset + start) >> PAGE_CACHE_SHIFT;
// i is the numbers page .
unsigned long end_i = (start_offset + start + min_len - 1) >>PAGE_CACHE_SHIFT;
if (i != end_i) // Examine whether this item and it's member belong to the same page.
return -EINVAL;
if (i == 0) { // In the first page of extent buffer.
offset = start_offset; // offset is the begining position of extent buffer in this page
*map_start = 0; // ?
------------------------------------------------------------------------------------------------------
| ---------------- page 1-------------------- | ---------------- page 2-------------------- |
------------------------------------------------------------------------------------------------------
| extentbuffer |
|part_off | n-th item|
} else { // Not in the first page
offset = 0; // This page is belong to the extent buffer
*map_start = ((u64)i << PAGE_CACHE_SHIFT) - start_offset;
// the distence between the start address of extent buffer and the
//page that target item belong to.
// It is the overlap between part_offset and kaddr in above function.
---------------------------------------------------------------------------------------------------
| ---------------- page 1-------------------|---------------- page 2-------------------- |
---------------------------------------------------------------------------------------------------
|--------------extenbuffer ------------------------------|
| part_offset |n-th item|
| map_start |
}
if (start + min_len > eb->len) {
printk(KERN_ERR "btrfs bad mapping eb start %llu len %lu, "
"wanted %lu %lu\n", (unsigned long long)eb->start,
eb->len, start, min_len);
WARN_ON(1);
return -EINVAL;
}
p = extent_buffer_page(eb, i);
kaddr = page_address(p);
// kaddr is the address of page that target item belong to and may be overlap with part offset.
*map = kaddr + offset;
*map_len = PAGE_CACHE_SIZE - offset;
return 0;
}
In Btrfs filesystem we will need to manipulate B+Tree. Here is some utilies function preparing to do that.
Operations on Leaf
btrfs_next_leaf(), btrfs_prev_leaf(), btrfs_del_leaf()
-->btrfs_next_leaf()
-->btrfs_next_old_leaf()
-->btrfs_header_nritems(): a set/get func
-->btrfs_item_key_to_cpu(): read item's key
-->btrfs_item_key()
-->btrfs_item_nr():the nr-th item offset.
-->read_eb_member()
-->read_extent_buffer()
-->btrfs_disk_key_to_cpu():simply copy and convert endian
-->btrfs_search_slot():See in next post.
void read_extent_buffer(struct extent_buffer *eb, void *dstv,
unsigned long start, unsigned long len)
{
size_t cur;
size_t offset;
struct page *page;
char *kaddr;
char *dst = (char *)dstv;
size_t start_offset = eb->start & ((u64)PAGE_CACHE_SIZE - 1);
unsigned long i = (start_offset + start) >> PAGE_CACHE_SHIFT;
WARN_ON(start > eb->len);
WARN_ON(start + len > eb->start + eb->len);
offset = (start_offset + start) & ((unsigned long)PAGE_CACHE_SIZE - 1);
//offset is the start of target item within page.
while (len > 0) {
//read data from kaddr+offset, size len,
//maybe span multiple pages
page = extent_buffer_page(eb, i);
// the page which target item belongs to.
cur = min(len, (PAGE_CACHE_SIZE - offset));
kaddr = page_address(page);
memcpy(dst, kaddr + offset, cur);
dst += cur;
len -= cur;
offset = 0;
i++;
}
}
-->brfs_prev_leaf()
--> btrfs_item_key_to_cpu()
-->btrfs_search_slot()
-->comp_keys()
-->btrfs_del_leaf()
-->del_ptr
Operations on Item
btrfs_next_item(), btrfs_previous_item(), btrfs_insert_empty_item(), btrfs_insert_item(), btrfs_del_item()
-->btrfs_next_item()
-->btrfs_next_old_item()
-->btrfs_next_old_leaf():if current is the last item in path,return next leaf
-->btrfs_previous_item()
-->if (path->slots[0] == nritems) //for the case that prev item in the prev leaf.
path->slots[0]--;
-->btrfs_insert_empty_item()
-->btrfs_insert_empty_items()
-->btrfs_search_slot()
-->setup_items_for_insert()
void setup_items_for_insert(struct btrfs_trans_handle *trans, struct btrfs_root *root,
struct btrfs_path *path, struct btrfs_key *cpu_key,
u32 *data_size, u32 total_data, u32 total_size, int nr)
{
struct btrfs_item *item;
int i;
u32 nritems;
unsigned int data_end;
struct btrfs_disk_key disk_key;
struct extent_buffer *leaf;
int slot;
struct btrfs_map_token token;
btrfs_init_map_token(&token);
leaf = path->nodes[0];
slot = path->slots[0];
nritems = btrfs_header_nritems(leaf);
data_end = leaf_data_end(root, leaf);
if (btrfs_leaf_free_space(root, leaf) < total_size) {
btrfs_print_leaf(root, leaf);
printk(KERN_CRIT "not enough freespace need %u have %d\n",
total_size, btrfs_leaf_free_space(root, leaf));
BUG();
}
if (slot != nritems) {
unsigned int old_data = btrfs_item_end_nr(leaf, slot);
if (old_data < data_end) {
btrfs_print_leaf(root, leaf);
printk(KERN_CRIT "slot %d old_data %d data_end %d\n",
slot, old_data, data_end);
BUG_ON(1);
}
/*
* item0..itemN ... dataN.offset..dataN.size .. data0.size
*/
/* first correct the data pointers */
for (i = slot; i < nritems; i++) {
u32 ioff;
item = btrfs_item_nr(leaf, i);
ioff = btrfs_token_item_offset(leaf, item, &token);
btrfs_set_token_item_offset(leaf, item,
ioff - total_data, &token);
}
/* shift the items */
memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
btrfs_item_nr_offset(slot),
(nritems - slot) * sizeof(struct btrfs_item));
/* shift the data */
memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
data_end - total_data, btrfs_leaf_data(leaf) +
data_end, old_data - data_end);
data_end = old_data;
}
/* setup the item for the new data */
for (i = 0; i < nr; i++) {
btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
btrfs_set_item_key(leaf, &disk_key, slot + i);
item = btrfs_item_nr(leaf, slot + i);
btrfs_set_token_item_offset(leaf, item,
data_end - data_size[i], &token);
data_end -= data_size[i];
btrfs_set_token_item_size(leaf, item, data_size[i], &token);
}
btrfs_set_header_nritems(leaf, nritems + nr);
if (slot == 0) {
btrfs_cpu_key_to_disk(&disk_key, cpu_key);
fixup_low_keys(trans, root, path, &disk_key, 1);
}
btrfs_unlock_up_safe(path, 1);
btrfs_mark_buffer_dirty(leaf);
if (btrfs_leaf_free_space(root, leaf) < 0) {
btrfs_print_leaf(root, leaf);
BUG();
}
}
-->btrfs_insert_item()
-->btrfs_insert_empty_item()
-->write_extent_buffer()
-->btrfs_del_item()
-->btrfs_del_items()
-->push_leaf_left():try to merge current leaft with the left leaf
-->push_leaf_right()
Operations on Key
bin_search(), generic_bin_search(), btrfs_search_slot()
-->bin_search()
-->generic_bin_search()
-->generic_bin_search():simply just isbinary search algorithm
-->btrfs_search_slot()
-->click_here
