vfs: Convert file allocation code to use the IDR

index bf70b3e..7eb4432 100644
@@ -22,8 +22,8 @@ struct idr {
 };
 
 /*
- * The IDR API does not expose the tagging functionality of the radix tree
- * to users.  Use tag 0 to track whether a node has free space below it.
+ * Reserve one of the radix tree tags to track whether a node has free
+ * space below it.
  */
 #define IDR_FREE	0
 

@@ -93,6 +93,59 @@ static inline void *idr_remove(struct idr *idr, int id)
 	return radix_tree_delete_item(&idr->idr_rt, id, NULL);
 }
 
+/**
+ * idr_tag_set - Set a tag on an entry
+ * @idr: IDR pointer
+ * @id: ID of entry to tag
+ * @tag: Tag index to set
+ *
+ * If there is an entry at @id in this IDR, set a tag on it and return
+ * the address of the entry.  If @id is outside the range of the IDR,
+ * return NULL.  This API does not allow you to set IDR_FREE on an entry;
+ * use idr_remove() for that.  The implementation does not currently check
+ * that IDR_FREE is clear, so it is possible to set a tag on a free entry.
+ * This is not recommended and may change in the future.
+ */
+static inline void *idr_tag_set(struct idr *idr, int id, unsigned int tag)
+{
+	BUG_ON(tag == IDR_FREE);
+	return radix_tree_tag_set(&idr->idr_rt, id, tag);
+}
+
+/**
+ * idr_tag_clear - Clear a tag on an entry
+ * @idr: IDR pointer
+ * @id: ID of entry to tag
+ * @tag: Tag index to clear
+ *
+ * If there is an entry at @id in this IDR, clear its tag and return
+ * the address of the entry.  If @id is outside the range of the IDR,
+ * return NULL.  This API does not allow you to clear IDR_FREE on an entry;
+ * use idr_alloc() for that.  The implementation does not currently check
+ * that IDR_FREE is clear, so it is possible to clear a tag on a free entry.
+ * This is not recommended and may change in the future.
+ */
+static inline void *idr_tag_clear(struct idr *idr, int id, unsigned int tag)
+{
+	BUG_ON(tag == IDR_FREE);
+	return radix_tree_tag_clear(&idr->idr_rt, id, tag);
+}
+
+/**
+ * idr_tag_get - Return whether a particular entry has a tag set
+ * @idr: IDR pointer
+ * @id: ID of entry to check
+ * @tag: Tag index to check
+ *
+ * Returns true/false depending whether @tag is set on this ID.  Unlike
+ * idr_tag_set() or idr_tag_clear(), you can use the IDR_FREE tag value,
+ * as it can be useful to know whether a particular ID has been allocated.
+ */
+static inline bool idr_tag_get(const struct idr *idr, int id, unsigned int tag)
+{
+	return radix_tree_tag_get(&idr->idr_rt, id, tag);
+}
+
 static inline void idr_init(struct idr *idr)
 {
 	INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);

index 691a9ad..6723384 100644
@@ -638,18 +638,17 @@ static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp,
 		if (!node)
 			return -ENOMEM;
 
+		/* Propagate the aggregated tag info to the new child */
+		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
+			if (root_tag_get(root, tag))
+				tag_set(node, tag, 0);
+		}
 		if (is_idr(root)) {
 			all_tag_set(node, IDR_FREE);
 			if (!root_tag_get(root, IDR_FREE)) {
 				tag_clear(node, IDR_FREE, 0);
 				root_tag_set(root, IDR_FREE);
 			}
-		} else {
-			/* Propagate the aggregated tag info to the new child */
-			for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
-				if (root_tag_get(root, tag))
-					tag_set(node, tag, 0);
-			}
 		}
 
 		BUG_ON(shift > BITS_PER_LONG);

@@ -1434,8 +1433,6 @@ void *radix_tree_tag_set(struct radix_tree_root *root,
 
 		parent = entry_to_node(node);
 		offset = radix_tree_descend(parent, &node, index);
-		BUG_ON(!node);
-
 		if (!tag_get(parent, tag, offset))
 			tag_set(parent, tag, offset);
 	}

@@ -1489,7 +1486,7 @@ static void node_tag_clear(struct radix_tree_root *root,
  *	Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
  *	corresponding to @index in the radix tree.  If this causes
  *	the leaf node to have no tags set then clear the tag in the
- *	next-to-leaf node, etc.
+ *	parent node, etc.
  *
  *	Returns the address of the tagged item on success, else NULL.  ie:
  *	has the same return value and semantics as radix_tree_lookup().

@@ -1512,8 +1509,7 @@ void *radix_tree_tag_clear(struct radix_tree_root *root,
 		offset = radix_tree_descend(parent, &node, index);
 	}
 
-	if (node)
-		node_tag_clear(root, parent, tag, offset);
+	node_tag_clear(root, parent, tag, offset);
 
 	return node;
 }

@@ -1552,11 +1548,11 @@ int radix_tree_tag_get(const struct radix_tree_root *root,
 	struct radix_tree_node *node, *parent;
 	unsigned long maxindex;
 
-	if (!root_tag_get(root, tag))
-		return 0;
-
 	radix_tree_load_root(root, &node, &maxindex);
 	if (index > maxindex)
+		return is_idr(root) && (tag == IDR_FREE);
+
+	if (!root_tag_get(root, tag))
 		return 0;
 
 	while (radix_tree_is_internal_node(node)) {

@@ -1783,7 +1779,7 @@ void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root,
 			child = rcu_dereference_raw(node->slots[offset]);
 		}
 
-		if (!child)
+		if (!child && !is_idr(root))
 			goto restart;
 		if (child == RADIX_TREE_RETRY)
 			break;

@@ -1994,11 +1990,10 @@ static bool __radix_tree_delete(struct radix_tree_root *root,
 	unsigned offset = get_slot_offset(node, slot);
 	int tag;
 
+	for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
+		node_tag_clear(root, node, tag, offset);
 	if (is_idr(root))
 		node_tag_set(root, node, IDR_FREE, offset);
-	else
-		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
-			node_tag_clear(root, node, tag, offset);
 
 	replace_slot(slot, NULL, node, -1, exceptional);
 	return node && delete_node(root, node, NULL, NULL);

index 30cd0b2..fd94bee 100644
@@ -135,6 +135,32 @@ void idr_null_test(void)
 	assert(idr_is_empty(&idr));
 }
 
+#define IDR_TEST	1
+
+void idr_tag_test(void)
+{
+	unsigned int i;
+	DEFINE_IDR(idr);
+
+	for (i = 0; i < 100; i++) {
+		assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == i);
+		if (i % 7 == 0)
+			idr_tag_set(&idr, i, IDR_TEST);
+	}
+
+	for (i = 0; i < 100; i += 14) {
+		assert(idr_tag_get(&idr, i, IDR_TEST));
+		idr_tag_clear(&idr, i, IDR_TEST);
+	}
+
+	for (i = 0; i < 100; i++) {
+		assert(idr_tag_get(&idr, i, IDR_TEST) == (i % 14 == 7));
+	}
+
+	idr_for_each(&idr, item_idr_free, &idr);
+	idr_destroy(&idr);
+}
+
 void idr_nowait_test(void)
 {
 	unsigned int i;

@@ -225,6 +251,7 @@ void idr_checks(void)
 	idr_replace_test();
 	idr_alloc_test();
 	idr_null_test();
+	idr_tag_test();
 	idr_nowait_test();
 	idr_get_next_test();
 }

index 7eb4432..9f71e63 100644
@@ -84,7 +84,8 @@ static inline void idr_set_cursor(struct idr *idr, unsigned int val)
 int idr_alloc_cyclic(struct idr *, void *entry, int start, int end, gfp_t);
 int idr_for_each(const struct idr *,
 		 int (*fn)(int id, void *p, void *data), void *data);
-void *idr_get_next(struct idr *, int *nextid);
+void *idr_get_next(const struct idr *, int *nextid);
+void *idr_get_next_tag(const struct idr *, int *nextid, unsigned int tag);
 void *idr_replace(struct idr *, void *, int id);
 void idr_destroy(struct idr *);
 

@@ -213,6 +214,18 @@ static inline void *idr_find(const struct idr *idr, int id)
 	     entry;							\
 	     ++id, (entry) = idr_get_next((idr), &(id)))
 
+/**
+ * idr_for_each_entry_tagged - iterate over IDs with a set tag
+ * @idr: IDR handle
+ * @entry: The pointer stored in @idr
+ * @id: The index of @entry in @idr
+ * @tag: tag to search for
+ */
+#define idr_for_each_entry_tagged(idr, entry, id, tag)			\
+	for (id = 0;							\
+	     ((entry) = idr_get_next_tag(idr, &(id), (tag))) != NULL;	\
+	     ++id)
+
 /*
  * IDA - IDR based id allocator, use when translation from id to
  * pointer isn't necessary.

index b13682b..68e39c3 100644
@@ -120,7 +120,7 @@ int idr_for_each(const struct idr *idr,
  * to the ID of the found value.  To use in a loop, the value pointed to by
  * nextid must be incremented by the user.
  */
-void *idr_get_next(struct idr *idr, int *nextid)
+void *idr_get_next(const struct idr *idr, int *nextid)
 {
 	struct radix_tree_iter iter;
 	void __rcu **slot;

@@ -135,6 +135,34 @@ void *idr_get_next(struct idr *idr, int *nextid)
 EXPORT_SYMBOL(idr_get_next);
 
 /**
+ * idr_get_next_tag - Find next tagged entry
+ * @idr: idr handle
+ * @nextid: Pointer to lowest possible ID to return
+ * @tag: tag to search for
+ *
+ * Returns the next tagged entry in the tree with an ID greater than
+ * or equal to the value pointed to by @nextid.  On exit, @nextid is updated
+ * to the ID of the found value.  To use in a loop, the value pointed to by
+ * nextid must be incremented by the user.  If a NULL entry is tagged, it
+ * will be returned.
+ */
+void *idr_get_next_tag(const struct idr *idr, int *nextid, unsigned int tag)
+{
+	struct radix_tree_iter iter;
+	void __rcu **slot;
+
+	radix_tree_iter_init(&iter, *nextid);
+	slot = radix_tree_next_chunk(&idr->idr_rt, &iter,
+					RADIX_TREE_ITER_TAGGED | tag);
+	if (!slot)
+		return NULL;
+
+	*nextid = iter.index;
+	return rcu_dereference_raw(*slot);
+}
+EXPORT_UNUSED_SYMBOL(idr_get_next_tag);
+
+/**
  * idr_replace - replace pointer for given id
  * @idr: idr handle
  * @ptr: New pointer to associate with the ID

index fd94bee..334ce1c 100644
@@ -23,19 +23,15 @@
 
 int item_idr_free(int id, void *p, void *data)
 {
-	struct item *item = p;
-	assert(item->index == id);
-	free(p);
-
+	item_free(p, id);
 	return 0;
 }
 
 void item_idr_remove(struct idr *idr, int id)
 {
 	struct item *item = idr_find(idr, id);
-	assert(item->index == id);
 	idr_remove(idr, id);
-	free(item);
+	item_free(item, id);
 }
 
 void idr_alloc_test(void)

@@ -139,11 +135,13 @@ void idr_null_test(void)
 
 void idr_tag_test(void)
 {
-	unsigned int i;
+	int i;
 	DEFINE_IDR(idr);
+	struct item *item;
 
 	for (i = 0; i < 100; i++) {
-		assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == i);
+		item = item_create(i, 0);
+		assert(idr_alloc(&idr, item, 0, 0, GFP_KERNEL) == i);
 		if (i % 7 == 0)
 			idr_tag_set(&idr, i, IDR_TEST);
 	}

@@ -157,6 +155,10 @@ void idr_tag_test(void)
 		assert(idr_tag_get(&idr, i, IDR_TEST) == (i % 14 == 7));
 	}
 
+	idr_for_each_entry_tagged(&idr, item, i, IDR_TEST) {
+		assert(item->index % 14 == 7);
+	}
+
 	idr_for_each(&idr, item_idr_free, &idr);
 	idr_destroy(&idr);
 }

index 1a257d7..74f8e5c 100644
@@ -62,13 +62,18 @@ void item_sanity(struct item *item, unsigned long index)
 	assert((item->index | mask) == (index | mask));
 }
 
+void item_free(struct item *item, unsigned long index)
+{
+	item_sanity(item, index);
+	free(item);
+}
+
 int item_delete(struct radix_tree_root *root, unsigned long index)
 {
 	struct item *item = radix_tree_delete(root, index);
 
 	if (item) {
-		item_sanity(item, index);
-		free(item);
+		item_free(item, index);
 		return 1;
 	}
 	return 0;

index 0f8220c..cbabea1 100644
@@ -13,6 +13,7 @@ struct item {
 int item_insert(struct radix_tree_root *root, unsigned long index);
 int item_insert_order(struct radix_tree_root *root, unsigned long index,
 			unsigned order);
+void item_free(struct item *item, unsigned long index);
 int item_delete(struct radix_tree_root *root, unsigned long index);
 struct item *item_lookup(struct radix_tree_root *root, unsigned long index);
 

index 9f71e63..d43cf01 100644
@@ -147,6 +147,12 @@ static inline bool idr_tag_get(const struct idr *idr, int id, unsigned int tag)
 	return radix_tree_tag_get(&idr->idr_rt, id, tag);
 }
 
+static inline unsigned long idr_get_tag_batch(const struct idr *idr, int id,
+							unsigned int tag)
+{
+	return radix_tree_get_tag_batch(&idr->idr_rt, id, tag);
+}
+
 static inline void idr_init(struct idr *idr)
 {
 	INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);

index 3e57350..f701e0b 100644
@@ -339,6 +339,8 @@ void radix_tree_iter_tag_set(struct radix_tree_root *,
 		const struct radix_tree_iter *iter, unsigned int tag);
 void radix_tree_iter_tag_clear(struct radix_tree_root *,
 		const struct radix_tree_iter *iter, unsigned int tag);
+unsigned long radix_tree_get_tag_batch(const struct radix_tree_root *,
+				unsigned long index, unsigned int tag);
 unsigned int radix_tree_gang_lookup_tag(const struct radix_tree_root *,
 		void **results, unsigned long first_index,
 		unsigned int max_items, unsigned int tag);

67 lines not on this page · raw message

index 334ce1c..3f9f429 100644
@@ -139,6 +139,8 @@ void idr_tag_test(void)
 	DEFINE_IDR(idr);
 	struct item *item;
 
+	assert(idr_get_tag_batch(&idr, 0, IDR_FREE) == ~0UL);
+
 	for (i = 0; i < 100; i++) {
 		item = item_create(i, 0);
 		assert(idr_alloc(&idr, item, 0, 0, GFP_KERNEL) == i);

@@ -146,6 +148,20 @@ void idr_tag_test(void)
 			idr_tag_set(&idr, i, IDR_TEST);
 	}
 
+	assert(idr_get_tag_batch(&idr, 0, IDR_FREE) == 0);
+#if BITS_PER_LONG == 64
+	assert(idr_get_tag_batch(&idr, 0, IDR_TEST) == 0x8102040810204081UL);
+	assert(idr_get_tag_batch(&idr, 64, IDR_TEST) == 0x408102040UL);
+#else
+	assert(idr_get_tag_batch(&idr, 0, IDR_TEST) == 0x10204081UL);
+	assert(idr_get_tag_batch(&idr, 32, IDR_TEST) == 0x81020408UL);
+	assert(idr_get_tag_batch(&idr, 64, IDR_TEST) == 0x08102040UL);
+	assert(idr_get_tag_batch(&idr, 96, IDR_TEST) == 0x4UL);
+#endif
+	assert((int)idr_get_tag_batch(&idr, 64, IDR_FREE) == 0);
+	assert(idr_get_tag_batch(&idr, 128, IDR_FREE) == ~0UL);
+	assert(idr_get_tag_batch(&idr, 128, IDR_TEST) == 0);
+
 	for (i = 0; i < 100; i += 14) {
 		assert(idr_tag_get(&idr, i, IDR_TEST));
 		idr_tag_clear(&idr, i, IDR_TEST);

@@ -159,6 +175,10 @@ void idr_tag_test(void)
 		assert(item->index % 14 == 7);
 	}
 
+	item_free(idr_remove(&idr, 7), 7);
+	assert((int)idr_get_tag_batch(&idr, 0, IDR_TEST) == 0x00200000UL);
+	assert((int)idr_get_tag_batch(&idr, 0, IDR_FREE) == 0x00000080);
+
 	idr_for_each(&idr, item_idr_free, &idr);
 	idr_destroy(&idr);
 }

index cbabea1..09616ff 100644
@@ -52,7 +52,7 @@ struct item *
 /* Normally private parts of lib/radix-tree.c */
 struct radix_tree_node *entry_to_node(void *ptr);
 void radix_tree_dump(struct radix_tree_root *root);
-int root_tag_get(struct radix_tree_root *root, unsigned int tag);
+bool root_tag_get(struct radix_tree_root *root, unsigned int tag);
 unsigned long node_maxindex(struct radix_tree_node *);
 unsigned long shift_maxindex(unsigned int shift);
 int radix_tree_cpu_dead(unsigned int cpu);

index d43cf01..eed1c1a 100644
@@ -166,6 +166,38 @@ static inline bool idr_is_empty(const struct idr *idr)
 }
 
 /**
+ * idr_copy_preload - preload for idr_copy()
+ * @src: IDR to be copied from
+ * @gfp: Allocation mask to use for preloading
+ *
+ * Preallocates enough memory for a call to idr_copy().  This function
+ * returns with preemption disabled.  Call idr_preload_end() once the
+ * copy has completed.
+ *
+ * Return: -ENOMEM if the memory could not be allocated.
+ */
+static inline int idr_copy_preload(const struct idr *src, gfp_t gfp)
+{
+	return radix_tree_copy_preload(&src->idr_rt, gfp);
+}
+
+/**
+ * idr_check_preload - Check the preload is still sufficient
+ * @src: IDR to be copied from
+ *
+ * Between the successful allocation of memory and acquiring the lock that
+ * protects @src, the IDR may have expanded.  If this function returns
+ * false, more memory needs to be preallocated.
+ *
+ * Return: true if enough memory remains allocated, false to retry the
+ * preallocation.
+ */
+static inline bool idr_check_preload(const struct idr *src)
+{
+	return radix_tree_check_preload(&src->idr_rt);
+}
+
+/**
  * idr_preload_end - end preload section started with idr_preload()
  *
  * Each idr_preload() should be matched with an invocation of this

index f701e0b..f53d004 100644
@@ -354,6 +354,9 @@ static inline void radix_tree_preload_end(void)
 	preempt_enable();
 }
 
+int radix_tree_copy_preload(const struct radix_tree_root *, gfp_t);
+bool radix_tree_check_preload(const struct radix_tree_root *);
+
 int radix_tree_split_preload(unsigned old_order, unsigned new_order, gfp_t);
 int radix_tree_split(struct radix_tree_root *, unsigned long index,
 			unsigned new_order);

95 lines not on this page · raw message

index 3f9f429..e8d5386 100644
@@ -225,6 +225,29 @@ void idr_get_next_test(void)
 	idr_destroy(&idr);
 }
 
+void idr_copy_test(void)
+{
+	DEFINE_IDR(src);
+	DEFINE_IDR(dst);
+	int i;
+	void *p;
+
+	for (i = 0; i < 10000; i++) {
+		struct item *item = item_create(i, 0);
+		assert(idr_alloc(&src, item, 0, 20000, GFP_KERNEL) == i);
+	}
+
+	idr_copy_preload(&src, GFP_KERNEL);
+	idr_for_each_entry(&src, p, i) {
+		assert(idr_alloc(&dst, p, i, i + 1, GFP_NOWAIT) == i);
+	}
+	idr_preload_end();
+
+	idr_for_each(&src, item_idr_free, NULL);
+	idr_destroy(&src);
+	idr_destroy(&dst);
+}
+
 void idr_checks(void)
 {
 	unsigned long i;

@@ -276,6 +299,7 @@ void idr_checks(void)
 	idr_tag_test();
 	idr_nowait_test();
 	idr_get_next_test();
+	idr_copy_test();
 }
 
 /*

index bf1bb23..0c5885e 100644
@@ -4,6 +4,8 @@
 #include "generated/map-shift.h"
 #include "../../../../include/linux/radix-tree.h"
 
+unsigned long radix_tree_count_nodes(const struct radix_tree_root *root);
+
 extern int kmalloc_verbose;
 extern int test_verbose;
 

index bc9a784..a7504e2 100644
@@ -11,6 +11,42 @@
 #include "test.h"
 #include "regression.h"
 
+static void count_node_check(void)
+{
+	unsigned long i, j, k;
+	RADIX_TREE(tree, GFP_KERNEL);
+
+	assert(radix_tree_empty(&tree));
+	assert(radix_tree_count_nodes(&tree) == 0);
+	assert(item_insert(&tree, 0) == 0);
+	assert(radix_tree_count_nodes(&tree) == 0);
+
+	for (i = 1; i < RADIX_TREE_MAP_SIZE; i++) {
+		assert(item_insert(&tree, i) == 0);
+		assert(radix_tree_count_nodes(&tree) == 1);
+	}
+
+	j = 3;
+	k = 3;
+	for (i = RADIX_TREE_MAP_SIZE; i < i * RADIX_TREE_MAP_SIZE;
+			i *= RADIX_TREE_MAP_SIZE) {
+		assert(item_insert(&tree, i) == 0);
+		assert(radix_tree_count_nodes(&tree) == j);
+		j += k;
+		k++;
+	}
+
+	assert(item_insert(&tree, i) == 0);
+	assert(radix_tree_count_nodes(&tree) == j);
+
+	item_kill_tree(&tree);
+}
+
+void basic_checks(void)
+{
+	count_node_check();
+}
+
 void __gang_check(unsigned long middle, long down, long up, int chunk, int hop)
 {
 	long idx;

@@ -362,6 +398,8 @@ int main(int argc, char **argv)
 	rcu_register_thread();
 	radix_tree_init();
 
+	basic_checks();
+
 	regression1_test();
 	regression2_test();
 	regression3_test();

index ad6f094..1c000d8 100644
@@ -47,7 +47,6 @@ static void *alloc_fdmem(size_t size)
 
 static void __free_fdtable(struct fdtable *fdt)
 {
-	kvfree(fdt->fd);
 	kvfree(fdt->open_fds);
 	kfree(fdt);
 }

@@ -89,15 +88,7 @@ static void copy_fd_bitmaps(struct fdtable *nfdt, struct fdtable *ofdt,
  */
 static void copy_fdtable(struct fdtable *nfdt, struct fdtable *ofdt)
 {
-	unsigned int cpy, set;
-
 	BUG_ON(nfdt->max_fds < ofdt->max_fds);
-
-	cpy = ofdt->max_fds * sizeof(struct file *);
-	set = (nfdt->max_fds - ofdt->max_fds) * sizeof(struct file *);
-	memcpy(nfdt->fd, ofdt->fd, cpy);
-	memset((char *)nfdt->fd + cpy, 0, set);
-
 	copy_fd_bitmaps(nfdt, ofdt, ofdt->max_fds);
 }
 

@@ -131,15 +122,11 @@ static struct fdtable * alloc_fdtable(unsigned int nr)
 	if (!fdt)
 		goto out;
 	fdt->max_fds = nr;
-	data = alloc_fdmem(nr * sizeof(struct file *));
-	if (!data)
-		goto out_fdt;
-	fdt->fd = data;
 
 	data = alloc_fdmem(max_t(size_t,
 				 2 * nr / BITS_PER_BYTE + BITBIT_SIZE(nr), L1_CACHE_BYTES));
 	if (!data)
-		goto out_arr;
+		goto out_fdt;
 	fdt->open_fds = data;
 	data += nr / BITS_PER_BYTE;
 	fdt->close_on_exec = data;

@@ -148,8 +135,6 @@ static struct fdtable * alloc_fdtable(unsigned int nr)
 
 	return fdt;
 
-out_arr:
-	kvfree(fdt->fd);
 out_fdt:
 	kfree(fdt);
 out:

@@ -170,6 +155,7 @@ static int expand_fdtable(struct files_struct *files, unsigned int nr)
 	struct fdtable *new_fdt, *cur_fdt;
 
 	spin_unlock(&files->file_lock);
+	idr_preload_end();
 	new_fdt = alloc_fdtable(nr);
 
 	/* make sure all __fd_install() have seen resize_in_progress

@@ -178,6 +164,7 @@ static int expand_fdtable(struct files_struct *files, unsigned int nr)
 	if (atomic_read(&files->count) > 1)
 		synchronize_sched();
 
+	idr_preload(GFP_KERNEL);
 	spin_lock(&files->file_lock);
 	if (!new_fdt)
 		return -ENOMEM;

@@ -228,8 +215,10 @@ static int expand_files(struct files_struct *files, unsigned int nr)
 
 	if (unlikely(files->resize_in_progress)) {
 		spin_unlock(&files->file_lock);
+		idr_preload_end();
 		expanded = 1;
 		wait_event(files->resize_wait, !files->resize_in_progress);
+		idr_preload(GFP_KERNEL);
 		spin_lock(&files->file_lock);
 		goto repeat;
 	}

@@ -290,8 +279,8 @@ static unsigned int count_open_files(struct fdtable *fdt)
 struct files_struct *dup_fd(struct files_struct *oldf, int *errorp)
 {
 	struct files_struct *newf;
-	struct file **old_fds, **new_fds;
 	unsigned int open_files, i;
+	struct file *f;
 	struct fdtable *old_fdt, *new_fdt;
 
 	*errorp = -ENOMEM;

@@ -302,6 +291,7 @@ struct files_struct *dup_fd(struct files_struct *oldf, int *errorp)
 	atomic_set(&newf->count, 1);
 
 	spin_lock_init(&newf->file_lock);
+	idr_init(&newf->fd_idr);
 	newf->resize_in_progress = false;
 	init_waitqueue_head(&newf->resize_wait);
 	newf->next_fd = 0;

@@ -310,8 +300,9 @@ struct files_struct *dup_fd(struct files_struct *oldf, int *errorp)
 	new_fdt->close_on_exec = newf->close_on_exec_init;
 	new_fdt->open_fds = newf->open_fds_init;
 	new_fdt->full_fds_bits = newf->full_fds_bits_init;
-	new_fdt->fd = &newf->fd_array[0];
 
+restart:
+	idr_copy_preload(&oldf->fd_idr, GFP_KERNEL);
 	spin_lock(&oldf->file_lock);
 	old_fdt = files_fdtable(oldf);
 	open_files = count_open_files(old_fdt);

@@ -321,6 +312,7 @@ struct files_struct *dup_fd(struct files_struct *oldf, int *errorp)
 	 */
 	while (unlikely(open_files > new_fdt->max_fds)) {
 		spin_unlock(&oldf->file_lock);
+		idr_preload_end();
 
 		if (new_fdt != &newf->fdtab)
 			__free_fdtable(new_fdt);

@@ -343,41 +335,50 @@ struct files_struct *dup_fd(struct files_struct *oldf, int *errorp)
 		 * who knows it may have a new bigger fd table. We need
 		 * the latest pointer.
 		 */
+		idr_copy_preload(&oldf->fd_idr, GFP_KERNEL);
 		spin_lock(&oldf->file_lock);
 		old_fdt = files_fdtable(oldf);
 		open_files = count_open_files(old_fdt);
 	}
 
+	if (!idr_check_preload(&oldf->fd_idr)) {
+		spin_unlock(&oldf->file_lock);
+		idr_preload_end();
+		goto restart;
+	}
+
 	copy_fd_bitmaps(new_fdt, old_fdt, open_files);
 
-	old_fds = old_fdt->fd;
-	new_fds = new_fdt->fd;
-
-	for (i = open_files; i != 0; i--) {
-		struct file *f = *old_fds++;
-		if (f) {
-			get_file(f);
-		} else {
-			/*
-			 * The fd may be claimed in the fd bitmap but not yet
-			 * instantiated in the files array if a sibling thread
-			 * is partway through open().  So make sure that this
-			 * fd is available to the new process.
-			 */
-			__clear_open_fd(open_files - i, new_fdt);
+	idr_for_each_entry(&oldf->fd_idr, f, i) {
+		int err;
+
+		get_file(f);
+		err = idr_alloc(&newf->fd_idr, f, i, i + 1, GFP_NOWAIT);
+		if (WARN(err != i, "Could not allocate %d: %d", i, err)) {
+			spin_unlock(&oldf->file_lock);
+			goto out;
 		}
-		rcu_assign_pointer(*new_fds++, f);
 	}
+
 	spin_unlock(&oldf->file_lock);
+	idr_preload_end();
 
-	/* clear the remainder */
-	memset(new_fds, 0, (new_fdt->max_fds - open_files) * sizeof(struct file *));
+	/*
+	 * The fd may be claimed in the fd bitmap but not yet
+	 * instantiated in the files array if a sibling thread
+	 * is partway through open().
+	 */
+	for_each_set_bit(i, new_fdt->open_fds, new_fdt->max_fds) {
+		if (!idr_find(&newf->fd_idr, i))
+			__clear_bit(i, new_fdt->open_fds);
+	}
 
 	rcu_assign_pointer(newf->fdt, new_fdt);
 
 	return newf;
 
 out_release:
+	idr_destroy(&newf->fd_idr);
 	kmem_cache_free(files_cachep, newf);
 out:
 	return NULL;

@@ -401,7 +402,8 @@ static struct fdtable *close_files(struct files_struct * files)
 		set = fdt->open_fds[j++];
 		while (set) {
 			if (set & 1) {
-				struct file * file = xchg(&fdt->fd[i], NULL);
+				struct file *file;
+				file = idr_remove(&files->fd_idr, i);
 				if (file) {
 					filp_close(file, files);
 					cond_resched_rcu_qs();

@@ -469,28 +471,14 @@ struct files_struct init_files = {
 	.fdt		= &init_files.fdtab,
 	.fdtab		= {
 		.max_fds	= NR_OPEN_DEFAULT,
-		.fd		= &init_files.fd_array[0],
 		.close_on_exec	= init_files.close_on_exec_init,
 		.open_fds	= init_files.open_fds_init,
 		.full_fds_bits	= init_files.full_fds_bits_init,
 	},
 	.file_lock	= __SPIN_LOCK_UNLOCKED(init_files.file_lock),
+	.fd_idr		= IDR_INIT,
 };
 
-static unsigned int find_next_fd(struct fdtable *fdt, unsigned int start)
-{
-	unsigned int maxfd = fdt->max_fds;
-	unsigned int maxbit = maxfd / BITS_PER_LONG;
-	unsigned int bitbit = start / BITS_PER_LONG;
-
-	bitbit = find_next_zero_bit(fdt->full_fds_bits, maxbit, bitbit) * BITS_PER_LONG;
-	if (bitbit > maxfd)
-		return maxfd;
-	if (bitbit > start)
-		start = bitbit;
-	return find_next_zero_bit(fdt->open_fds, maxfd, start);
-}
-
 /*
  * allocate a file descriptor, mark it busy.
  */

@@ -501,54 +489,37 @@ int __alloc_fd(struct files_struct *files,
 	int error;
 	struct fdtable *fdt;
 
+	idr_preload(GFP_KERNEL);
 	spin_lock(&files->file_lock);
-repeat:
-	fdt = files_fdtable(files);
-	fd = start;
-	if (fd < files->next_fd)
-		fd = files->next_fd;
 
-	if (fd < fdt->max_fds)
-		fd = find_next_fd(fdt, fd);
-
-	/*
-	 * N.B. For clone tasks sharing a files structure, this test
-	 * will limit the total number of files that can be opened.
-	 */
-	error = -EMFILE;
-	if (fd >= end)
+	error = idr_alloc(&files->fd_idr, NULL, start, end, GFP_NOWAIT);
+	if (error == -ENOSPC) {
+		error = -EMFILE;
 		goto out;
+	}
+	BUG_ON(error < 0);
+	fd = error;
 
 	error = expand_files(files, fd);
-	if (error < 0)
+	if (error < 0) {
+		idr_remove(&files->fd_idr, fd);
 		goto out;
-
-	/*
-	 * If we needed to expand the fs array we
-	 * might have blocked - try again.
-	 */
-	if (error)
-		goto repeat;
+	}
 
 	if (start <= files->next_fd)
 		files->next_fd = fd + 1;
 
+	fdt = files_fdtable(files);
 	__set_open_fd(fd, fdt);
 	if (flags & O_CLOEXEC)
 		__set_close_on_exec(fd, fdt);
 	else
 		__clear_close_on_exec(fd, fdt);
 	error = fd;
-#if 1
-	/* Sanity check */
-	if (rcu_access_pointer(fdt->fd[fd]) != NULL) {
-		printk(KERN_WARNING "alloc_fd: slot %d not NULL!\n", fd);
-		rcu_assign_pointer(fdt->fd[fd], NULL);
-	}
-#endif
 
 out:
 	spin_unlock(&files->file_lock);
+	idr_preload_end();
 	return error;
 }
 

@@ -575,6 +546,7 @@ void put_unused_fd(unsigned int fd)
 {
 	struct files_struct *files = current->files;
 	spin_lock(&files->file_lock);
+	BUG_ON(idr_remove(&files->fd_idr, fd));
 	__put_unused_fd(files, fd);
 	spin_unlock(&files->file_lock);
 }

@@ -604,22 +576,9 @@ void put_unused_fd(unsigned int fd)
 void __fd_install(struct files_struct *files, unsigned int fd,
 		struct file *file)
 {
-	struct fdtable *fdt;
-
-	might_sleep();
-	rcu_read_lock_sched();
-
-	while (unlikely(files->resize_in_progress)) {
-		rcu_read_unlock_sched();
-		wait_event(files->resize_wait, !files->resize_in_progress);
-		rcu_read_lock_sched();
-	}
-	/* coupled with smp_wmb() in expand_fdtable() */
-	smp_rmb();
-	fdt = rcu_dereference_sched(files->fdt);
-	BUG_ON(fdt->fd[fd] != NULL);
-	rcu_assign_pointer(fdt->fd[fd], file);
-	rcu_read_unlock_sched();
+	rcu_read_lock();
+	BUG_ON(idr_replace(&files->fd_idr, file, fd));
+	rcu_read_unlock();
 }
 
 void fd_install(unsigned int fd, struct file *file)

@@ -641,10 +600,9 @@ int __close_fd(struct files_struct *files, unsigned fd)
 	fdt = files_fdtable(files);
 	if (fd >= fdt->max_fds)
 		goto out_unlock;
-	file = fdt->fd[fd];
+	file = idr_remove(&files->fd_idr, fd);
 	if (!file)
 		goto out_unlock;
-	rcu_assign_pointer(fdt->fd[fd], NULL);
 	__clear_close_on_exec(fd, fdt);
 	__put_unused_fd(files, fd);
 	spin_unlock(&files->file_lock);

@@ -676,10 +634,9 @@ void do_close_on_exec(struct files_struct *files)
 			struct file *file;
 			if (!(set & 1))
 				continue;
-			file = fdt->fd[fd];
+			file = idr_remove(&files->fd_idr, fd);
 			if (!file)
 				continue;
-			rcu_assign_pointer(fdt->fd[fd], NULL);
 			__put_unused_fd(files, fd);
 			spin_unlock(&files->file_lock);
 			filp_close(file, files);

@@ -842,17 +799,27 @@ static int do_dup2(struct files_struct *files,
 	 * tables and this condition does not arise without those.
 	 */
 	fdt = files_fdtable(files);
-	tofree = fdt->fd[fd];
+	tofree = idr_find(&files->fd_idr, fd);
 	if (!tofree && fd_is_open(fd, fdt))
 		goto Ebusy;
 	get_file(file);
-	rcu_assign_pointer(fdt->fd[fd], file);
+	if (tofree) {
+		idr_replace(&files->fd_idr, file, fd);
+	} else {
+		int err = idr_alloc(&files->fd_idr, file, fd, fd + 1,
+								GFP_NOWAIT);
+		if (err != fd) {
+			WARN(1, "do_dup2 got %d for fd %d\n", err, fd);
+			goto Ebusy;
+		}
+	}
 	__set_open_fd(fd, fdt);
 	if (flags & O_CLOEXEC)
 		__set_close_on_exec(fd, fdt);
 	else
 		__clear_close_on_exec(fd, fdt);
 	spin_unlock(&files->file_lock);
+	idr_preload_end();
 
 	if (tofree)
 		filp_close(tofree, files);

@@ -861,6 +828,7 @@ static int do_dup2(struct files_struct *files,
 
 Ebusy:
 	spin_unlock(&files->file_lock);
+	idr_preload_end();
 	return -EBUSY;
 }
 

@@ -875,6 +843,7 @@ int replace_fd(unsigned fd, struct file *file, unsigned flags)
 	if (fd >= rlimit(RLIMIT_NOFILE))
 		return -EBADF;
 
+	idr_preload(GFP_KERNEL);
 	spin_lock(&files->file_lock);
 	err = expand_files(files, fd);
 	if (unlikely(err < 0))

@@ -883,6 +852,7 @@ int replace_fd(unsigned fd, struct file *file, unsigned flags)
 
 out_unlock:
 	spin_unlock(&files->file_lock);
+	idr_preload_end();
 	return err;
 }
 

@@ -901,6 +871,7 @@ int replace_fd(unsigned fd, struct file *file, unsigned flags)
 	if (newfd >= rlimit(RLIMIT_NOFILE))
 		return -EBADF;
 
+	idr_preload(GFP_KERNEL);
 	spin_lock(&files->file_lock);
 	err = expand_files(files, newfd);
 	file = fcheck(oldfd);

@@ -917,6 +888,7 @@ int replace_fd(unsigned fd, struct file *file, unsigned flags)
 	err = -EBADF;
 out_unlock:
 	spin_unlock(&files->file_lock);
+	idr_preload_end();
 	return err;
 }
 

@@ -974,7 +946,7 @@ int iterate_fd(struct files_struct *files, unsigned n,
 	spin_lock(&files->file_lock);
 	for (fdt = files_fdtable(files); n < fdt->max_fds; n++) {
 		struct file *file;
-		file = rcu_dereference_check_fdtable(files, fdt->fd[n]);
+		file = __fcheck_files(files, n);
 		if (!file)
 			continue;
 		res = f(p, file, n);

index 6e84b2cae..4072f24 100644
@@ -12,6 +12,7 @@
 #include <linux/types.h>
 #include <linux/init.h>
 #include <linux/fs.h>
+#include <linux/idr.h>
 
 #include <linux/atomic.h>
 

@@ -23,7 +24,6 @@
 
 struct fdtable {
 	unsigned int max_fds;
-	struct file __rcu **fd;      /* current fd array */
 	unsigned long *close_on_exec;
 	unsigned long *open_fds;
 	unsigned long *full_fds_bits;

@@ -51,6 +51,7 @@ struct files_struct {
 	bool resize_in_progress;
 	wait_queue_head_t resize_wait;
 
+	struct idr fd_idr;
 	struct fdtable __rcu *fdt;
 	struct fdtable fdtab;
   /*

@@ -61,7 +62,6 @@ struct files_struct {
 	unsigned long close_on_exec_init[1];
 	unsigned long open_fds_init[1];
 	unsigned long full_fds_bits_init[1];
-	struct file __rcu * fd_array[NR_OPEN_DEFAULT];
 };
 
 struct file_operations;

@@ -79,11 +79,7 @@ struct files_struct {
  */
 static inline struct file *__fcheck_files(struct files_struct *files, unsigned int fd)
 {
-	struct fdtable *fdt = rcu_dereference_raw(files->fdt);
-
-	if (fd < fdt->max_fds)
-		return rcu_dereference_raw(fdt->fd[fd]);
-	return NULL;
+	return idr_find(&files->fd_idr, fd);
 }
 
 static inline struct file *fcheck_files(struct files_struct *files, unsigned int fd)

index 1c000d8..da3a35b 100644
@@ -294,7 +294,6 @@ struct files_struct *dup_fd(struct files_struct *oldf, int *errorp)
 	idr_init(&newf->fd_idr);
 	newf->resize_in_progress = false;
 	init_waitqueue_head(&newf->resize_wait);
-	newf->next_fd = 0;
 	new_fdt = &newf->fdtab;
 	new_fdt->max_fds = NR_OPEN_DEFAULT;
 	new_fdt->close_on_exec = newf->close_on_exec_init;

@@ -506,9 +505,6 @@ int __alloc_fd(struct files_struct *files,
 		goto out;
 	}
 
-	if (start <= files->next_fd)
-		files->next_fd = fd + 1;
-
 	fdt = files_fdtable(files);
 	__set_open_fd(fd, fdt);
 	if (flags & O_CLOEXEC)

@@ -538,8 +534,6 @@ static void __put_unused_fd(struct files_struct *files, unsigned int fd)
 {
 	struct fdtable *fdt = files_fdtable(files);
 	__clear_open_fd(fd, fdt);
-	if (fd < files->next_fd)
-		files->next_fd = fd;
 }
 
 void put_unused_fd(unsigned int fd)

index 4072f24..c2a53b6 100644
@@ -58,7 +58,6 @@ struct files_struct {
    * written part on a separate cache line in SMP
    */
 	spinlock_t file_lock ____cacheline_aligned_in_smp;
-	unsigned int next_fd;
 	unsigned long close_on_exec_init[1];
 	unsigned long open_fds_init[1];
 	unsigned long full_fds_bits_init[1];

index da3a35b..e8c6ada 100644
@@ -56,9 +56,6 @@ static void free_fdtable_rcu(struct rcu_head *rcu)
 	__free_fdtable(container_of(rcu, struct fdtable, rcu));
 }
 
-#define BITBIT_NR(nr)	BITS_TO_LONGS(BITS_TO_LONGS(nr))
-#define BITBIT_SIZE(nr)	(BITBIT_NR(nr) * sizeof(long))
-
 /*
  * Copy 'count' fd bits from the old table to the new table and clear the extra
  * space if any.  This does not copy the file pointers.  Called with the files

@@ -75,11 +72,6 @@ static void copy_fd_bitmaps(struct fdtable *nfdt, struct fdtable *ofdt,
 	memset((char *)nfdt->open_fds + cpy, 0, set);
 	memcpy(nfdt->close_on_exec, ofdt->close_on_exec, cpy);
 	memset((char *)nfdt->close_on_exec + cpy, 0, set);
-
-	cpy = BITBIT_SIZE(count);
-	set = BITBIT_SIZE(nfdt->max_fds) - cpy;
-	memcpy(nfdt->full_fds_bits, ofdt->full_fds_bits, cpy);
-	memset((char *)nfdt->full_fds_bits + cpy, 0, set);
 }
 
 /*

@@ -124,14 +116,12 @@ static struct fdtable * alloc_fdtable(unsigned int nr)
 	fdt->max_fds = nr;
 
 	data = alloc_fdmem(max_t(size_t,
-				 2 * nr / BITS_PER_BYTE + BITBIT_SIZE(nr), L1_CACHE_BYTES));
+				 2 * nr / BITS_PER_BYTE, L1_CACHE_BYTES));
 	if (!data)
 		goto out_fdt;
 	fdt->open_fds = data;
 	data += nr / BITS_PER_BYTE;
 	fdt->close_on_exec = data;
-	data += nr / BITS_PER_BYTE;
-	fdt->full_fds_bits = data;
 
 	return fdt;
 

@@ -246,15 +236,11 @@ static inline void __clear_close_on_exec(unsigned int fd, struct fdtable *fdt)
 static inline void __set_open_fd(unsigned int fd, struct fdtable *fdt)
 {
 	__set_bit(fd, fdt->open_fds);
-	fd /= BITS_PER_LONG;
-	if (!~fdt->open_fds[fd])
-		__set_bit(fd, fdt->full_fds_bits);
 }
 
 static inline void __clear_open_fd(unsigned int fd, struct fdtable *fdt)
 {
 	__clear_bit(fd, fdt->open_fds);
-	__clear_bit(fd / BITS_PER_LONG, fdt->full_fds_bits);
 }
 
 static unsigned int count_open_files(struct fdtable *fdt)

@@ -298,7 +284,6 @@ struct files_struct *dup_fd(struct files_struct *oldf, int *errorp)
 	new_fdt->max_fds = NR_OPEN_DEFAULT;
 	new_fdt->close_on_exec = newf->close_on_exec_init;
 	new_fdt->open_fds = newf->open_fds_init;
-	new_fdt->full_fds_bits = newf->full_fds_bits_init;
 
 restart:
 	idr_copy_preload(&oldf->fd_idr, GFP_KERNEL);

@@ -472,7 +457,6 @@ struct files_struct init_files = {
 		.max_fds	= NR_OPEN_DEFAULT,
 		.close_on_exec	= init_files.close_on_exec_init,
 		.open_fds	= init_files.open_fds_init,
-		.full_fds_bits	= init_files.full_fds_bits_init,
 	},
 	.file_lock	= __SPIN_LOCK_UNLOCKED(init_files.file_lock),
 	.fd_idr		= IDR_INIT,

index c2a53b6..6bece35 100644
@@ -26,7 +26,6 @@ struct fdtable {
 	unsigned int max_fds;
 	unsigned long *close_on_exec;
 	unsigned long *open_fds;
-	unsigned long *full_fds_bits;
 	struct rcu_head rcu;
 };
 

@@ -60,7 +59,6 @@ struct files_struct {
 	spinlock_t file_lock ____cacheline_aligned_in_smp;
 	unsigned long close_on_exec_init[1];
 	unsigned long open_fds_init[1];
-	unsigned long full_fds_bits_init[1];
 };
 
 struct file_operations;

index e8c6ada..8d67968 100644
@@ -222,6 +222,11 @@ static int expand_files(struct files_struct *files, unsigned int nr)
 	return expanded;
 }
 
+static inline bool fd_is_open(unsigned int fd, struct files_struct *files)
+{
+	return !idr_tag_get(&files->fd_idr, fd, IDR_FREE);
+}
+
 static inline void __set_close_on_exec(unsigned int fd, struct fdtable *fdt)
 {
 	__set_bit(fd, fdt->close_on_exec);

@@ -778,7 +783,7 @@ static int do_dup2(struct files_struct *files,
 	 */
 	fdt = files_fdtable(files);
 	tofree = idr_find(&files->fd_idr, fd);
-	if (!tofree && fd_is_open(fd, fdt))
+	if (!tofree && fd_is_open(fd, files))
 		goto Ebusy;
 	get_file(file);
 	if (tofree) {

index 6bece35..67259f4 100644
@@ -34,11 +34,6 @@ static inline bool close_on_exec(unsigned int fd, const struct fdtable *fdt)
 	return test_bit(fd, fdt->close_on_exec);
 }
 
-static inline bool fd_is_open(unsigned int fd, const struct fdtable *fdt)
-{
-	return test_bit(fd, fdt->open_fds);
-}
-
 /*
  * Open file table structure
  */

index 8d67968..8cd77c5 100644
@@ -373,37 +373,21 @@ struct files_struct *dup_fd(struct files_struct *oldf, int *errorp)
 	return NULL;
 }
 
-static struct fdtable *close_files(struct files_struct * files)
+static void close_files(struct files_struct * files)
 {
 	/*
-	 * It is safe to dereference the fd table without RCU or
-	 * ->file_lock because this is the last reference to the
-	 * files structure.
+	 * No need for RCU or ->file_lock protection because
+	 * this is the last reference to the files structure.
 	 */
-	struct fdtable *fdt = rcu_dereference_raw(files->fdt);
-	unsigned int i, j = 0;
+	struct file *file;
+	int fd;
 
-	for (;;) {
-		unsigned long set;
-		i = j * BITS_PER_LONG;
-		if (i >= fdt->max_fds)
-			break;
-		set = fdt->open_fds[j++];
-		while (set) {
-			if (set & 1) {
-				struct file *file;
-				file = idr_remove(&files->fd_idr, i);
-				if (file) {
-					filp_close(file, files);
-					cond_resched_rcu_qs();
-				}
-			}
-			i++;
-			set >>= 1;
-		}
+	idr_for_each_entry(&files->fd_idr, file, fd) {
+		filp_close(file, files);
+		cond_resched_rcu_qs();
 	}
 
-	return fdt;
+	idr_destroy(&files->fd_idr);
 }
 
 struct files_struct *get_files_struct(struct task_struct *task)

@@ -422,7 +406,8 @@ struct files_struct *get_files_struct(struct task_struct *task)
 void put_files_struct(struct files_struct *files)
 {
 	if (atomic_dec_and_test(&files->count)) {
-		struct fdtable *fdt = close_files(files);
+		struct fdtable *fdt = rcu_dereference_raw(files->fdt);
+		close_files(files);
 
 		/* free the arrays if they are not embedded */
 		if (fdt != &files->fdtab)

index 65145a3..2070bc6 100644
@@ -1728,7 +1728,7 @@ static int do_execveat_common(int fd, struct filename *filename,
 		 * inaccessible after exec. Relies on having exclusive access to
 		 * current->files (due to unshare_files above).
 		 */
-		if (close_on_exec(fd, rcu_dereference_raw(current->files->fdt)))
+		if (close_on_exec(fd, current->files))
 			bprm->interp_flags |= BINPRM_FLAGS_PATH_INACCESSIBLE;
 		bprm->filename = pathbuf;
 	}

index be8fbe2..9c2061b 100644
@@ -255,7 +255,7 @@ static long do_fcntl(int fd, unsigned int cmd, unsigned long arg,
 		err = f_dupfd(arg, filp, O_CLOEXEC);
 		break;
 	case F_GETFD:
-		err = get_close_on_exec(fd) ? FD_CLOEXEC : 0;
+		err = close_on_exec(fd, current->files) ? FD_CLOEXEC : 0;
 		break;
 	case F_SETFD:
 		err = 0;

170 lines not on this page · raw message

index c330495..2735ccc 100644
@@ -36,10 +36,8 @@ static int seq_show(struct seq_file *m, void *v)
 		spin_lock(&files->file_lock);
 		file = fcheck_files(files, fd);
 		if (file) {
-			struct fdtable *fdt = files_fdtable(files);
-
 			f_flags = file->f_flags;
-			if (close_on_exec(fd, fdt))
+			if (close_on_exec(fd, files))
 				f_flags |= O_CLOEXEC;
 
 			get_file(file);

index 67259f4..7f1ab82 100644
@@ -22,18 +22,14 @@
  */
 #define NR_OPEN_DEFAULT BITS_PER_LONG
 
+#define	FD_TAG_CLOEXEC	1
+
 struct fdtable {
 	unsigned int max_fds;
-	unsigned long *close_on_exec;
 	unsigned long *open_fds;
 	struct rcu_head rcu;
 };
 
-static inline bool close_on_exec(unsigned int fd, const struct fdtable *fdt)
-{
-	return test_bit(fd, fdt->close_on_exec);
-}
-
 /*
  * Open file table structure
  */

@@ -52,7 +48,6 @@ struct files_struct {
    * written part on a separate cache line in SMP
    */
 	spinlock_t file_lock ____cacheline_aligned_in_smp;
-	unsigned long close_on_exec_init[1];
 	unsigned long open_fds_init[1];
 };
 

@@ -82,6 +77,16 @@ static inline struct file *fcheck_files(struct files_struct *files, unsigned int
 	return __fcheck_files(files, fd);
 }
 
+static inline bool close_on_exec(unsigned int fd, struct files_struct *files)
+{
+	bool res;
+
+	rcu_read_lock();
+	res = idr_tag_get(&files->fd_idr, fd, FD_TAG_CLOEXEC);
+	rcu_read_unlock();
+	return res;
+}
+
 /*
  * Check whether the specified fd has an open file.
  */

index 61eb82c..1856bbf 100644
@@ -76,7 +76,6 @@ static inline void fdput_pos(struct fd f)
 extern int f_dupfd(unsigned int from, struct file *file, unsigned flags);
 extern int replace_fd(unsigned fd, struct file *file, unsigned flags);
 extern void set_close_on_exec(unsigned int fd, int flag);
-extern bool get_close_on_exec(unsigned int fd);
 extern void put_filp(struct file *);
 extern int get_unused_fd_flags(unsigned flags);
 extern void put_unused_fd(unsigned int fd);

index 56c5731..23f198b 100644
@@ -19,6 +19,7 @@
 #include <linux/fdtable.h>
 #include <linux/bitops.h>
 #include <linux/interrupt.h>
+#include <linux/init_task.h>
 #include <linux/spinlock.h>
 #include <linux/rcupdate.h>
 #include <linux/workqueue.h>

index e211227..5d20a14 100644
@@ -346,32 +346,33 @@ static int poll_select_copy_remaining(struct timespec64 *end_time,
 
 static int max_select_fd(unsigned long n, fd_set_bits *fds)
 {
-	unsigned long *open_fds;
+	unsigned long bad_fds;
 	unsigned long set;
 	int max;
-	struct fdtable *fdt;
+	struct idr *fd_idr = &current->files->fd_idr;
 
 	/* handle last in-complete long-word first */
 	set = ~(~0UL << (n & (BITS_PER_LONG-1)));
 	n /= BITS_PER_LONG;
-	fdt = files_fdtable(current->files);
-	open_fds = fdt->open_fds + n;
 	max = 0;
 	if (set) {
 		set &= BITS(fds, n);
 		if (set) {
-			if (!(set & ~*open_fds))
+			bad_fds = idr_get_tag_batch(fd_idr, (n * BITS_PER_LONG),
+							IDR_FREE);
+			if (!(set & bad_fds))
 				goto get_max;
 			return -EBADF;
 		}
 	}
 	while (n) {
-		open_fds--;
 		n--;
 		set = BITS(fds, n);
 		if (!set)
 			continue;
-		if (set & ~*open_fds)
+		bad_fds = idr_get_tag_batch(fd_idr, (n * BITS_PER_LONG),
+						IDR_FREE);
+		if (set & bad_fds)
 			return -EBADF;
 		if (max)
 			continue;

index c61b506..7483c9c 100644
@@ -1153,17 +1153,13 @@ int compat_core_sys_select(int n, compat_ulong_t __user *inp,
 	fd_set_bits fds;
 	void *bits;
 	int size, max_fds, ret = -EINVAL;
-	struct fdtable *fdt;
 	long stack_fds[SELECT_STACK_ALLOC/sizeof(long)];
 
 	if (n < 0)
 		goto out_nofds;
 
 	/* max_fds can increase, so grab it once to avoid race */
-	rcu_read_lock();
-	fdt = files_fdtable(current->files);
-	max_fds = fdt->max_fds;
-	rcu_read_unlock();
+	max_fds = READ_ONCE(current->files->max_fds);
 	if (n > max_fds)
 		n = max_fds;
 

531 lines not on this page · raw message

index 88c3555..ec6fdaf 100644
@@ -186,7 +186,7 @@ static inline void task_state(struct seq_file *m, struct pid_namespace *ns,
 
 	task_lock(p);
 	if (p->files)
-		max_fds = files_fdtable(p->files)->max_fds;
+		max_fds = READ_ONCE(p->files->max_fds);
 	task_unlock(p);
 	rcu_read_unlock();
 

index 2735ccc..7e5aeca 100644
@@ -231,7 +231,7 @@ static int proc_readfd_common(struct file *file, struct dir_context *ctx,
 
 	rcu_read_lock();
 	for (fd = ctx->pos - 2;
-	     fd < files_fdtable(files)->max_fds;
+	     fd < files->max_fds;
 	     fd++, ctx->pos++) {
 		char name[PROC_NUMBUF];
 		int len;

index 5d20a14..14da393 100644
@@ -557,7 +557,6 @@ int core_sys_select(int n, fd_set __user *inp, fd_set __user *outp,
 	void *bits;
 	int ret, max_fds;
 	size_t size, alloc_size;
-	struct fdtable *fdt;
 	/* Allocate small arguments on the stack to save memory and be faster */
 	long stack_fds[SELECT_STACK_ALLOC/sizeof(long)];
 

@@ -566,10 +565,7 @@ int core_sys_select(int n, fd_set __user *inp, fd_set __user *outp,
 		goto out_nofds;
 
 	/* max_fds can increase, so grab it once to avoid race */
-	rcu_read_lock();
-	fdt = files_fdtable(current->files);
-	max_fds = fdt->max_fds;
-	rcu_read_unlock();
+	max_fds = READ_ONCE(current->files->max_fds);
 	if (n > max_fds)
 		n = max_fds;
 

index 7f1ab82..ff94541 100644
@@ -24,43 +24,16 @@
 
 #define	FD_TAG_CLOEXEC	1
 
-struct fdtable {
-	unsigned int max_fds;
-	unsigned long *open_fds;
-	struct rcu_head rcu;
-};
-
 /*
  * Open file table structure
  */
 struct files_struct {
-  /*
-   * read mostly part
-   */
+	spinlock_t file_lock;
 	atomic_t count;
-	bool resize_in_progress;
-	wait_queue_head_t resize_wait;
-
 	struct idr fd_idr;
-	struct fdtable __rcu *fdt;
-	struct fdtable fdtab;
-  /*
-   * written part on a separate cache line in SMP
-   */
-	spinlock_t file_lock ____cacheline_aligned_in_smp;
-	unsigned long open_fds_init[1];
+	unsigned int max_fds;
 };
 
-struct file_operations;
-struct vfsmount;
-struct dentry;
-
-#define rcu_dereference_check_fdtable(files, fdtfd) \
-	rcu_dereference_check((fdtfd), lockdep_is_held(&(files)->file_lock))
-
-#define files_fdtable(files) \
-	rcu_dereference_check_fdtable((files), (files)->fdt)
-
 /*
  * The caller must ensure that fd table isn't shared or hold rcu or file lock
  */