Release 4.10 fs/btrfs/extent_map.c

Directory: fs/btrfs
#include <linux/err.h>
#include <linux/slab.h>
#include <linux/spinlock.h>
#include <linux/hardirq.h>
#include "ctree.h"
#include "extent_map.h"
#include "compression.h"



static struct kmem_cache *extent_map_cache;



int __init extent_map_init(void)
{
	extent_map_cache = kmem_cache_create("btrfs_extent_map",
			sizeof(struct extent_map), 0,
			SLAB_MEM_SPREAD, NULL);
	if (!extent_map_cache)
		return -ENOMEM;
	return 0;
}

Contributors
Person Tokens Prop Commits CommitProp
chris mason chris mason 22 56.41% 2 40.00%
wyatt banks wyatt banks 13 33.33% 1 20.00%
christoph hellwig christoph hellwig 3 7.69% 1 20.00%
david sterba david sterba 1 2.56% 1 20.00%
Total 39 100.00% 5 100.00%



void extent_map_exit(void)
{
	kmem_cache_destroy(extent_map_cache);
}

Contributors
Person Tokens Prop Commits CommitProp
chris mason chris mason 12 100.00% 1 100.00%
Total 12 100.00% 1 100.00%

/**
 * extent_map_tree_init - initialize extent map tree
 * @tree:               tree to initialize
 *
 * Initialize the extent tree @tree.  Should be called for each new inode
 * or other user of the extent_map interface.
 */


void extent_map_tree_init(struct extent_map_tree *tree)
{
	tree->map = RB_ROOT;
	INIT_LIST_HEAD(&tree->modified_extents);
	rwlock_init(&tree->lock);
}

Contributors
Person Tokens Prop Commits CommitProp
chris mason chris mason 23 71.88% 4 66.67%
josef bacik josef bacik 8 25.00% 1 16.67%
eric paris eric paris 1 3.12% 1 16.67%
Total 32 100.00% 6 100.00%

/**
 * alloc_extent_map - allocate new extent map structure
 *
 * Allocate a new extent_map structure.  The new structure is
 * returned with a reference count of one and needs to be
 * freed using free_extent_map()
 */


struct extent_map *alloc_extent_map(void)
{
	struct extent_map *em;
	em = kmem_cache_zalloc(extent_map_cache, GFP_NOFS);
	if (!em)
		return NULL;
	RB_CLEAR_NODE(&em->rb_node);
	em->flags = 0;
	em->compress_type = BTRFS_COMPRESS_NONE;
	em->generation = 0;
	atomic_set(&em->refs, 1);
	INIT_LIST_HEAD(&em->list);
	return em;
}

Contributors
Person Tokens Prop Commits CommitProp
chris mason chris mason 49 62.82% 3 33.33%
josef bacik josef bacik 15 19.23% 2 22.22%
li zefan li zefan 6 7.69% 1 11.11%
filipe david borba manana filipe david borba manana 5 6.41% 1 11.11%
david sterba david sterba 2 2.56% 1 11.11%
tsutomu itoh tsutomu itoh 1 1.28% 1 11.11%
Total 78 100.00% 9 100.00%

/**
 * free_extent_map - drop reference count of an extent_map
 * @em:         extent map being released
 *
 * Drops the reference out on @em by one and free the structure
 * if the reference count hits zero.
 */


void free_extent_map(struct extent_map *em)
{
	if (!em)
		return;
	WARN_ON(atomic_read(&em->refs) == 0);
	if (atomic_dec_and_test(&em->refs)) {
		WARN_ON(extent_map_in_tree(em));
		WARN_ON(!list_empty(&em->list));
		if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags))
			kfree(em->map_lookup);
		kmem_cache_free(extent_map_cache, em);
	}
}

Contributors
Person Tokens Prop Commits CommitProp
chris mason chris mason 53 60.92% 3 42.86%
wang shilong wang shilong 18 20.69% 1 14.29%
josef bacik josef bacik 12 13.79% 1 14.29%
filipe david borba manana filipe david borba manana 3 3.45% 1 14.29%
jeff mahoney jeff mahoney 1 1.15% 1 14.29%
Total 87 100.00% 7 100.00%

/* simple helper to do math around the end of an extent, handling wrap */


static u64 range_end(u64 start, u64 len)
{
	if (start + len < start)
		return (u64)-1;
	return start + len;
}

Contributors
Person Tokens Prop Commits CommitProp
filipe david borba manana filipe david borba manana 32 100.00% 1 100.00%
Total 32 100.00% 1 100.00%



static int tree_insert(struct rb_root *root, struct extent_map *em)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct extent_map *entry = NULL;
	struct rb_node *orig_parent = NULL;
	u64 end = range_end(em->start, em->len);

	while (*p) {
		parent = *p;
		entry = rb_entry(parent, struct extent_map, rb_node);

		if (em->start < entry->start)
			p = &(*p)->rb_left;
		else if (em->start >= extent_map_end(entry))
			p = &(*p)->rb_right;
		else
			return -EEXIST;
	}

	orig_parent = parent;
	while (parent && em->start >= extent_map_end(entry)) {
		parent = rb_next(parent);
		entry = rb_entry(parent, struct extent_map, rb_node);
	}
	if (parent)
		if (end > entry->start && em->start < extent_map_end(entry))
			return -EEXIST;

	parent = orig_parent;
	entry = rb_entry(parent, struct extent_map, rb_node);
	while (parent && em->start < entry->start) {
		parent = rb_prev(parent);
		entry = rb_entry(parent, struct extent_map, rb_node);
	}
	if (parent)
		if (end > entry->start && em->start < extent_map_end(entry))
			return -EEXIST;

	rb_link_node(&em->rb_node, orig_parent, p);
	rb_insert_color(&em->rb_node, root);
	return 0;
}

Contributors
Person Tokens Prop Commits CommitProp
filipe david borba manana filipe david borba manana 168 56.95% 1 33.33%
chris mason chris mason 127 43.05% 2 66.67%
Total 295 100.00% 3 100.00%

/*
 * search through the tree for an extent_map with a given offset.  If
 * it can't be found, try to find some neighboring extents
 */


static struct rb_node *__tree_search(struct rb_root *root, u64 offset,
				     struct rb_node **prev_ret,
				     struct rb_node **next_ret)
{
	struct rb_node *n = root->rb_node;
	struct rb_node *prev = NULL;
	struct rb_node *orig_prev = NULL;
	struct extent_map *entry;
	struct extent_map *prev_entry = NULL;

	while (n) {
		entry = rb_entry(n, struct extent_map, rb_node);
		prev = n;
		prev_entry = entry;

		if (offset < entry->start)
			n = n->rb_left;
		else if (offset >= extent_map_end(entry))
			n = n->rb_right;
		else
			return n;
	}

	if (prev_ret) {
		orig_prev = prev;
		while (prev && offset >= extent_map_end(prev_entry)) {
			prev = rb_next(prev);
			prev_entry = rb_entry(prev, struct extent_map, rb_node);
		}
		*prev_ret = prev;
		prev = orig_prev;
	}

	if (next_ret) {
		prev_entry = rb_entry(prev, struct extent_map, rb_node);
		while (prev && offset < prev_entry->start) {
			prev = rb_prev(prev);
			prev_entry = rb_entry(prev, struct extent_map, rb_node);
		}
		*next_ret = prev;
	}
	return NULL;
}

Contributors
Person Tokens Prop Commits CommitProp
chris mason chris mason 231 100.00% 3 100.00%
Total 231 100.00% 3 100.00%

/* check to see if two extent_map structs are adjacent and safe to merge */


static int mergable_maps(struct extent_map *prev, struct extent_map *next)
{
	if (test_bit(EXTENT_FLAG_PINNED, &prev->flags))
		return 0;

	/*
         * don't merge compressed extents, we need to know their
         * actual size
         */
	if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags))
		return 0;

	if (test_bit(EXTENT_FLAG_LOGGING, &prev->flags) ||
	    test_bit(EXTENT_FLAG_LOGGING, &next->flags))
		return 0;

	/*
         * We don't want to merge stuff that hasn't been written to the log yet
         * since it may not reflect exactly what is on disk, and that would be
         * bad.
         */
	if (!list_empty(&prev->list) || !list_empty(&next->list))
		return 0;

	if (extent_map_end(prev) == next->start &&
	    prev->flags == next->flags &&
	    prev->bdev == next->bdev &&
	    ((next->block_start == EXTENT_MAP_HOLE &&
	      prev->block_start == EXTENT_MAP_HOLE) ||
	     (next->block_start == EXTENT_MAP_INLINE &&
	      prev->block_start == EXTENT_MAP_INLINE) ||
	     (next->block_start == EXTENT_MAP_DELALLOC &&
	      prev->block_start == EXTENT_MAP_DELALLOC) ||
	     (next->block_start < EXTENT_MAP_LAST_BYTE - 1 &&
	      next->block_start == extent_map_block_end(prev)))) {
		return 1;
	}
	return 0;
}

Contributors
Person Tokens Prop Commits CommitProp
chris mason chris mason 145 74.74% 4 66.67%
josef bacik josef bacik 49 25.26% 2 33.33%
Total 194 100.00% 6 100.00%



static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em)
{
	struct extent_map *merge = NULL;
	struct rb_node *rb;

	if (em->start != 0) {
		rb = rb_prev(&em->rb_node);
		if (rb)
			merge = rb_entry(rb, struct extent_map, rb_node);
		if (rb && mergable_maps(merge, em)) {
			em->start = merge->start;
			em->orig_start = merge->orig_start;
			em->len += merge->len;
			em->block_len += merge->block_len;
			em->block_start = merge->block_start;
			em->mod_len = (em->mod_len + em->mod_start) - merge->mod_start;
			em->mod_start = merge->mod_start;
			em->generation = max(em->generation, merge->generation);

			rb_erase(&merge->rb_node, &tree->map);
			RB_CLEAR_NODE(&merge->rb_node);
			free_extent_map(merge);
		}
	}

	rb = rb_next(&em->rb_node);
	if (rb)
		merge = rb_entry(rb, struct extent_map, rb_node);
	if (rb && mergable_maps(em, merge)) {
		em->len += merge->len;
		em->block_len += merge->block_len;
		rb_erase(&merge->rb_node, &tree->map);
		RB_CLEAR_NODE(&merge->rb_node);
		em->mod_len = (merge->mod_start + merge->mod_len) - em->mod_start;
		em->generation = max(em->generation, merge->generation);
		free_extent_map(merge);
	}
}

Contributors
Person Tokens Prop Commits CommitProp
chris mason chris mason 194 65.10% 1 14.29%
josef bacik josef bacik 65 21.81% 2 28.57%
liu bo liu bo 17 5.70% 1 14.29%
filipe david borba manana filipe david borba manana 14 4.70% 2 28.57%
li zefan li zefan 8 2.68% 1 14.29%
Total 298 100.00% 7 100.00%

/**
 * unpin_extent_cache - unpin an extent from the cache
 * @tree:       tree to unpin the extent in
 * @start:      logical offset in the file
 * @len:        length of the extent
 * @gen:        generation that this extent has been modified in
 *
 * Called after an extent has been written to disk properly.  Set the generation
 * to the generation that actually added the file item to the inode so we know
 * we need to sync this extent when we call fsync().
 */


int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len,
		       u64 gen)
{
	int ret = 0;
	struct extent_map *em;
	bool prealloc = false;

	write_lock(&tree->lock);
	em = lookup_extent_mapping(tree, start, len);

	WARN_ON(!em || em->start != start);

	if (!em)
		goto out;

	em->generation = gen;
	clear_bit(EXTENT_FLAG_PINNED, &em->flags);
	em->mod_start = em->start;
	em->mod_len = em->len;

	if (test_bit(EXTENT_FLAG_FILLING, &em->flags)) {
		prealloc = true;
		clear_bit(EXTENT_FLAG_FILLING, &em->flags);
	}

	try_merge_map(tree, em);

	if (prealloc) {
		em->mod_start = em->start;
		em->mod_len = em->len;
	}

	free_extent_map(em);
out:
	write_unlock(&tree->lock);
	return ret;

}

Contributors
Person Tokens Prop Commits CommitProp
li zefan li zefan 81 45.00% 1 20.00%
liu bo liu bo 69 38.33% 1 20.00%
chris mason chris mason 19 10.56% 1 20.00%
josef bacik josef bacik 11 6.11% 2 40.00%
Total 180 100.00% 5 100.00%



void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em)
{
	clear_bit(EXTENT_FLAG_LOGGING, &em->flags);
	if (extent_map_in_tree(em))
		try_merge_map(tree, em);
}

Contributors
Person Tokens Prop Commits CommitProp
josef bacik josef bacik 36 92.31% 2 66.67%
filipe david borba manana filipe david borba manana 3 7.69% 1 33.33%
Total 39 100.00% 3 100.00%



static inline void setup_extent_mapping(struct extent_map_tree *tree,
					struct extent_map *em,
					int modified)
{
	atomic_inc(&em->refs);
	em->mod_start = em->start;
	em->mod_len = em->len;

	if (modified)
		list_move(&em->list, &tree->modified_extents);
	else
		try_merge_map(tree, em);
}

Contributors
Person Tokens Prop Commits CommitProp
chris mason chris mason 26 37.68% 2 33.33%
josef bacik josef bacik 21 30.43% 1 16.67%
liu bo liu bo 16 23.19% 1 16.67%
filipe david borba manana filipe david borba manana 5 7.25% 1 16.67%
li zefan li zefan 1 1.45% 1 16.67%
Total 69 100.00% 6 100.00%

/**
 * add_extent_mapping - add new extent map to the extent tree
 * @tree:       tree to insert new map in
 * @em:         map to insert
 *
 * Insert @em into @tree or perform a simple forward/backward merge with
 * existing mappings.  The extent_map struct passed in will be inserted
 * into the tree directly, with an additional reference taken, or a
 * reference dropped if the merge attempt was successful.
 */


int add_extent_mapping(struct extent_map_tree *tree,
		       struct extent_map *em, int modified)
{
	int ret = 0;

	ret = tree_insert(&tree->map, em);
	if (ret)
		goto out;

	setup_extent_mapping(tree, em, modified);
out:
	return ret;
}

Contributors
Person Tokens Prop Commits CommitProp
filipe david borba manana filipe david borba manana 50 89.29% 1 33.33%
chris mason chris mason 6 10.71% 2 66.67%
Total 56 100.00% 3 100.00%


static struct extent_map *

__lookup_extent_mapping(struct extent_map_tree *tree,
			u64 start, u64 len, int strict)
{
	struct extent_map *em;
	struct rb_node *rb_node;
	struct rb_node *prev = NULL;
	struct rb_node *next = NULL;
	u64 end = range_end(start, len);

	rb_node = __tree_search(&tree->map, start, &prev, &next);
	if (!rb_node) {
		if (prev)
			rb_node = prev;
		else if (next)
			rb_node = next;
		else
			return NULL;
	}

	em = rb_entry(rb_node, struct extent_map, rb_node);

	if (strict && !(end > em->start && start < extent_map_end(em)))
		return NULL;

	atomic_inc(&em->refs);
	return em;
}

Contributors
Person Tokens Prop Commits CommitProp
chris mason chris mason 127 85.81% 3 60.00%
li zefan li zefan 20 13.51% 1 20.00%
eric sandeen eric sandeen 1 0.68% 1 20.00%
Total 148 100.00% 5 100.00%

/**
 * lookup_extent_mapping - lookup extent_map
 * @tree:       tree to lookup in
 * @start:      byte offset to start the search
 * @len:        length of the lookup range
 *
 * Find and return the first extent_map struct in @tree that intersects the
 * [start, len] range.  There may be additional objects in the tree that
 * intersect, so check the object returned carefully to make sure that no
 * additional lookups are needed.
 */


struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree,
					 u64 start, u64 len)
{
	return __lookup_extent_mapping(tree, start, len, 1);
}

Contributors
Person Tokens Prop Commits CommitProp
chris mason chris mason 24 80.00% 1 50.00%
li zefan li zefan 6 20.00% 1 50.00%
Total 30 100.00% 2 100.00%

/**
 * search_extent_mapping - find a nearby extent map
 * @tree:       tree to lookup in
 * @start:      byte offset to start the search
 * @len:        length of the lookup range
 *
 * Find and return the first extent_map struct in @tree that intersects the
 * [start, len] range.
 *
 * If one can't be found, any nearby extent may be returned
 */


struct extent_map *search_extent_mapping(struct extent_map_tree *tree,
					 u64 start, u64 len)
{
	return __lookup_extent_mapping(tree, start, len, 0);
}

Contributors
Person Tokens Prop Commits CommitProp
li zefan li zefan 23 76.67% 2 66.67%
chris mason chris mason 7 23.33% 1 33.33%
Total 30 100.00% 3 100.00%

/**
 * remove_extent_mapping - removes an extent_map from the extent tree
 * @tree:       extent tree to remove from
 * @em:         extent map being removed
 *
 * Removes @em from @tree.  No reference counts are dropped, and no checks
 * are done to see if the range is in use
 */


int remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em)
{
	int ret = 0;

	WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags));
	rb_erase(&em->rb_node, &tree->map);
	if (!test_bit(EXTENT_FLAG_LOGGING, &em->flags))
		list_del_init(&em->list);
	RB_CLEAR_NODE(&em->rb_node);
	return ret;
}

Contributors
Person Tokens Prop Commits CommitProp
chris mason chris mason 52 66.67% 3 50.00%
josef bacik josef bacik 21 26.92% 2 33.33%
filipe david borba manana filipe david borba manana 5 6.41% 1 16.67%
Total 78 100.00% 6 100.00%



void replace_extent_mapping(struct extent_map_tree *tree,
			    struct extent_map *cur,
			    struct extent_map *new,
			    int modified)
{
	WARN_ON(test_bit(EXTENT_FLAG_PINNED, &cur->flags));
	ASSERT(extent_map_in_tree(cur));
	if (!test_bit(EXTENT_FLAG_LOGGING, &cur->flags))
		list_del_init(&cur->list);
	rb_replace_node(&cur->rb_node, &new->rb_node, &tree->map);
	RB_CLEAR_NODE(&cur->rb_node);

	setup_extent_mapping(tree, new, modified);
}
Contributors
Person Tokens Prop Commits CommitProp
filipe david borba manana filipe david borba manana 100 100.00% 1 100.00%
Total 100 100.00% 1 100.00%

Overall Contributors
Person Tokens Prop Commits CommitProp
chris mason chris mason 1140 55.18% 13 30.23%
filipe david borba manana filipe david borba manana 387 18.73% 4 9.30%
josef bacik josef bacik 238 11.52% 7 16.28%
li zefan li zefan 150 7.26% 4 9.30%
liu bo liu bo 103 4.99% 2 4.65%
wang shilong wang shilong 18 0.87% 1 2.33%
wyatt banks wyatt banks 13 0.63% 1 2.33%
david sterba david sterba 5 0.24% 3 6.98%
christoph hellwig christoph hellwig 3 0.15% 1 2.33%
anand jain anand jain 3 0.15% 1 2.33%
jeff mahoney jeff mahoney 1 0.05% 1 2.33%
nicholas d steeves nicholas d steeves 1 0.05% 1 2.33%
adam buchbinder adam buchbinder 1 0.05% 1 2.33%
tsutomu itoh tsutomu itoh 1 0.05% 1 2.33%
eric paris eric paris 1 0.05% 1 2.33%
eric sandeen eric sandeen 1 0.05% 1 2.33%
Total 2066 100.00% 43 100.00%
Directory: fs/btrfs

Information contained on this website is for historical information purposes only and does not indicate or represent copyright ownership.
	Person	Tokens	Prop	Commits	CommitProp
chris mason	chris mason	22	56.41%	2	40.00%
wyatt banks	wyatt banks	13	33.33%	1	20.00%
christoph hellwig	christoph hellwig	3	7.69%	1	20.00%
david sterba	david sterba	1	2.56%	1	20.00%
	Total	39	100.00%	5	100.00%
cregit-Linux how code gets into the kernel

Release 4.10 fs/btrfs/extent_map.c

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Overall Contributors
