Attachment #107408 for bug #60579

Lines 57-62 Link Here

(-)a/fs/btrfs/super.c (-1 / +9 lines)
57	#include "dev-replace.h"	57	#include "dev-replace.h"
58	#include "free-space-cache.h"	58	#include "free-space-cache.h"
59	#include "backref.h"	59	#include "backref.h"
		60	#include "ulist.h"
60	#include "tests/btrfs-tests.h"	61	#include "tests/btrfs-tests.h"
61		62
62	#define CREATE_TRACE_POINTS	63	#define CREATE_TRACE_POINTS
Lines 1787-1796 static int __init init_btrfs_fs(void) Link Here
1787	if (err)	1788	if (err)
1788	goto free_compress;	1789	goto free_compress;
1789		1790
1790	err = extent_io_init();	1791	err = ulist_init_cachep();
1791	if (err)	1792	if (err)
1792	goto free_cachep;	1793	goto free_cachep;
1793		1794
		1795	err = extent_io_init();
		1796	if (err)
		1797	goto free_ulist;
		1798
1794	err = extent_map_init();	1799	err = extent_map_init();
1795	if (err)	1800	if (err)
1796	goto free_extent_io;	1801	goto free_extent_io;
Lines 1849-1854 free_extent_map: Link Here
1849	extent_map_exit();	1854	extent_map_exit();
1850	free_extent_io:	1855	free_extent_io:
1851	extent_io_exit();	1856	extent_io_exit();
		1857	free_ulist:
		1858	ulist_destroy_cachep();
1852	free_cachep:	1859	free_cachep:
1853	btrfs_destroy_cachep();	1860	btrfs_destroy_cachep();
1854	free_compress:	1861	free_compress:
Lines 1864-1869 static void __exit exit_btrfs_fs(void) Link Here
1864	btrfs_auto_defrag_exit();	1871	btrfs_auto_defrag_exit();
1865	btrfs_delayed_inode_exit();	1872	btrfs_delayed_inode_exit();
1866	btrfs_prelim_ref_exit();	1873	btrfs_prelim_ref_exit();
		1874	ulist_destroy_cachep();
1867	ordered_data_exit();	1875	ordered_data_exit();
1868	extent_map_exit();	1876	extent_map_exit();
1869	extent_io_exit();	1877	extent_io_exit();

Lines 8-13 Link Here

(-)a/fs/btrfs/ulist.c (-50 / +71 lines)
8	#include <linux/export.h>	8	#include <linux/export.h>
9	#include "ulist.h"	9	#include "ulist.h"
10		10
		11	static struct kmem_cache *ulist_node_cachep;
		12
11	/*	13	/*
12	* ulist is a generic data structure to hold a collection of unique u64	14	* ulist is a generic data structure to hold a collection of unique u64
13	* values. The only operations it supports is adding to the list and	15	* values. The only operations it supports is adding to the list and
Lines 51-62 Link Here
51	void ulist_init(struct ulist *ulist)	53	void ulist_init(struct ulist *ulist)
52	{	54	{
53	ulist->nnodes = 0;	55	ulist->nnodes = 0;
54	ulist->nodes = ulist->int_nodes;	56	ulist->last_node = NULL;
55	ulist->nodes_alloced = ULIST_SIZE;
56	ulist->root = RB_ROOT;	57	ulist->root = RB_ROOT;
57	}	58	}
58	EXPORT_SYMBOL(ulist_init);	59	EXPORT_SYMBOL(ulist_init);
59		60
		61	static void free_nodes(struct ulist *ulist)
		62	{
		63	struct rb_node *n;
		64	struct ulist_node *un;
		65
		66	n = rb_first(&ulist->root);
		67	while (n) {
		68	un = rb_entry(n, struct ulist_node, rb_node);
		69	n = rb_next(n);
		70	rb_erase(&un->rb_node, &ulist->root);
		71	un->next = NULL;
		72	if (!un->alloced)
		73	continue;
		74	kmem_cache_free(ulist_node_cachep, un);
		75	}
		76	}
		77
60	/**	78	/**
61	* ulist_fini - free up additionally allocated memory for the ulist	79	* ulist_fini - free up additionally allocated memory for the ulist
62	* @ulist: the ulist from which to free the additional memory	80	* @ulist: the ulist from which to free the additional memory
Lines 70-78 void ulist_fini(struct ulist *ulist) Link Here
70	* The first ULIST_SIZE elements are stored inline in struct ulist.	88	* The first ULIST_SIZE elements are stored inline in struct ulist.
71	* Only if more elements are alocated they need to be freed.	89	* Only if more elements are alocated they need to be freed.
72	*/	90	*/
73	if (ulist->nodes_alloced > ULIST_SIZE)	91	if (ulist->nnodes > ULIST_SIZE)
74	kfree(ulist->nodes);	92	free_nodes(ulist);
75	ulist->nodes_alloced = 0; /* in case ulist_fini is called twice */	93	ulist->nnodes = 0; /* in case ulist_fini is called twice */
		94	ulist->last_node = NULL;
76	ulist->root = RB_ROOT;	95	ulist->root = RB_ROOT;
77	}	96	}
78	EXPORT_SYMBOL(ulist_fini);	97	EXPORT_SYMBOL(ulist_fini);
Lines 201-249 int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, Link Here
201	return 0;	220	return 0;
202	}	221	}
203		222
204	if (ulist->nnodes >= ulist->nodes_alloced) {	223	if (ulist->nnodes >= ULIST_SIZE) {
205	u64 new_alloced = ulist->nodes_alloced + 128;	224	node = kmem_cache_alloc(ulist_node_cachep, gfp_mask);
206	struct ulist_node *new_nodes;	225	if (!node)
207	void *old = NULL;
208	int i;
209
210	for (i = 0; i < ulist->nnodes; i++)
211	rb_erase(&ulist->nodes[i].rb_node, &ulist->root);
212
213	/*
214	* if nodes_alloced == ULIST_SIZE no memory has been allocated
215	* yet, so pass NULL to krealloc
216	*/
217	if (ulist->nodes_alloced > ULIST_SIZE)
218	old = ulist->nodes;
219
220	new_nodes = krealloc(old, sizeof(new_nodes) new_alloced,
221	gfp_mask);
222	if (!new_nodes)
223	return -ENOMEM;	226	return -ENOMEM;
224		227	node->val = val;
225	if (!old)	228	node->aux = aux;
226	memcpy(new_nodes, ulist->int_nodes,	229	node->alloced = 1;
227	sizeof(ulist->int_nodes));	230	node->next = NULL;
228		231	ret = ulist_rbtree_insert(ulist, node);
229	ulist->nodes = new_nodes;	232	if (ret) {
230	ulist->nodes_alloced = new_alloced;	233	kmem_cache_free(ulist_node_cachep, node);
231		234	return ret;
232	/*
233	* krealloc actually uses memcpy, which does not copy rb_node
234	* pointers, so we have to do it ourselves. Otherwise we may
235	* be bitten by crashes.
236	*/
237	for (i = 0; i < ulist->nnodes; i++) {
238	ret = ulist_rbtree_insert(ulist, &ulist->nodes[i]);
239	if (ret < 0)
240	return ret;
241	}	235	}
		236	ulist->last_node->next = node;
		237	ulist->last_node = node;
		238	} else {
		239	ulist->int_nodes[ulist->nnodes].val = val;
		240	ulist->int_nodes[ulist->nnodes].aux = aux;
		241	ulist->int_nodes[ulist->nnodes].alloced = 0;
		242	ulist->int_nodes[ulist->nnodes].next = NULL;
		243	ret = ulist_rbtree_insert(ulist,
		244	&ulist->int_nodes[ulist->nnodes]);
		245	if (ret)
		246	return ret;
		247	node = &ulist->int_nodes[ulist->nnodes];
242	}	248	}
243	ulist->nodes[ulist->nnodes].val = val;	249	if (ulist->last_node)
244	ulist->nodes[ulist->nnodes].aux = aux;	250	ulist->last_node->next = node;
245	ret = ulist_rbtree_insert(ulist, &ulist->nodes[ulist->nnodes]);	251	ulist->last_node = node;
246	BUG_ON(ret);
247	++ulist->nnodes;	252	++ulist->nnodes;
248		253
249	return 1;	254	return 1;
Lines 268-278 EXPORT_SYMBOL(ulist_add); Link Here
268	*/	273	*/
269	struct ulist_node ulist_next(struct ulist ulist, struct ulist_iterator *uiter)	274	struct ulist_node ulist_next(struct ulist ulist, struct ulist_iterator *uiter)
270	{	275	{
271	if (ulist->nnodes == 0)	276	if (ulist->last_node == NULL)
272	return NULL;
273	if (uiter->i < 0 \|\| uiter->i >= ulist->nnodes)
274	return NULL;	277	return NULL;
275		278	if (!uiter->cur)
276	return &ulist->nodes[uiter->i++];	279	uiter->cur = &ulist->int_nodes[0];
		280	else
		281	uiter->cur = uiter->cur->next;
		282	return uiter->cur;
277	}	283	}
278	EXPORT_SYMBOL(ulist_next);	284	EXPORT_SYMBOL(ulist_next);
		285
		286	void ulist_destroy_cachep(void)
		287	{
		288	if (ulist_node_cachep)
		289	kmem_cache_destroy(ulist_node_cachep);
		290	}
		291
		292	int ulist_init_cachep(void)
		293	{
		294	ulist_node_cachep = kmem_cache_create("ulist_node",
		295	sizeof(struct ulist_node), 0,
		296	SLAB_RECLAIM_ACCOUNT \|
		297	SLAB_MEM_SPREAD, NULL);
		298	return (ulist_node_cachep) ? 0 : -ENOMEM;
		299	}




 */
#define ULIST_SIZE 16

struct ulist_iterator {
	int i;
};

/*
 * element of the list
 */
struct ulist_node {
	u64 val;		/* value to store */
	u64 aux;		/* auxiliary value saved along with the val */
	struct ulist_node *next;	/* single linked list */
	short alloced:1;	/* needs to be freed */
	struct rb_node rb_node;	/* used to speed up search */
};

struct ulist_iterator {
	struct ulist_node *cur;
};


struct ulist {
	/*
	 * number of elements stored in list
	 */
	unsigned long nnodes;

	/* Last element in the list */
	struct ulist_node *last_node;
	 */
	unsigned long nodes_alloced;

	/*
	 * pointer to the array storing the elements. The first ULIST_SIZE
	 * elements are stored inline. In this case the it points to int_nodes.
	 * After exceeding ULIST_SIZE, dynamic memory is allocated.
	 */
	struct ulist_node *nodes;

	struct rb_root root;


		    u64 *old_aux, gfp_t gfp_mask);
struct ulist_node *ulist_next(struct ulist *ulist,
			      struct ulist_iterator *uiter);
void ulist_destroy_cachep(void);
int ulist_init_cachep(void);

#define ULIST_ITER_INIT(uiter) ((uiter)->cur = NULL)

#endif

Return to bug 60579

Lines 27-62 Link Here

(-)a/fs/btrfs/ulist.h (-16 / +12 lines)
27	*/	27	*/
28	#define ULIST_SIZE 16	28	#define ULIST_SIZE 16
29		29
30	struct ulist_iterator {
31	int i;
32	};
33
34	/*	30	/*
35	* element of the list	31	* element of the list
36	*/	32	*/
37	struct ulist_node {	33	struct ulist_node {
38	u64 val; /* value to store */	34	u64 val; /* value to store */
39	u64 aux; /* auxiliary value saved along with the val */	35	u64 aux; /* auxiliary value saved along with the val */
		36	struct ulist_node next; / single linked list */
		37	short alloced:1; /* needs to be freed */
40	struct rb_node rb_node; /* used to speed up search */	38	struct rb_node rb_node; /* used to speed up search */
41	};	39	};
42		40
		41	struct ulist_iterator {
		42	struct ulist_node *cur;
		43	};
		44
		45
43	struct ulist {	46	struct ulist {
44	/*	47	/*
45	* number of elements stored in list	48	* number of elements stored in list
46	*/	49	*/
47	unsigned long nnodes;	50	unsigned long nnodes;
48		51
49	/*	52	/* Last element in the list */
50	* number of nodes we already have room for	53	struct ulist_node *last_node;
51	*/
52	unsigned long nodes_alloced;
53
54	/*
55	* pointer to the array storing the elements. The first ULIST_SIZE
56	* elements are stored inline. In this case the it points to int_nodes.
57	* After exceeding ULIST_SIZE, dynamic memory is allocated.
58	*/
59	struct ulist_node *nodes;
60		54
61	struct rb_root root;	55	struct rb_root root;
62		56
Lines 76-82 int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, Link Here
76	u64 *old_aux, gfp_t gfp_mask);	70	u64 *old_aux, gfp_t gfp_mask);
77	struct ulist_node ulist_next(struct ulist ulist,	71	struct ulist_node ulist_next(struct ulist ulist,
78	struct ulist_iterator *uiter);	72	struct ulist_iterator *uiter);
		73	void ulist_destroy_cachep(void);
		74	int ulist_init_cachep(void);
79		75
80	#define ULIST_ITER_INIT(uiter) ((uiter)->i = 0)	76	#define ULIST_ITER_INIT(uiter) ((uiter)->cur = NULL)
81		77
82	#endif	78	#endif