diff options
-rw-r--r-- | include/linux/idr.h | 2 | ||||
-rw-r--r-- | lib/idr.c | 179 |
2 files changed, 125 insertions, 56 deletions
diff --git a/include/linux/idr.h b/include/linux/idr.h index 418d87c92528..f30ceb368895 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -45,6 +45,8 @@ struct ida { * leaf nodes, ida->nodes - ida->first_leaf == number of leaf nodes */ unsigned first_leaf; + unsigned pad; + unsigned sections; unsigned long **tree; diff --git a/lib/idr.c b/lib/idr.c index 6c3531966406..eba2996b4abd 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -86,12 +86,17 @@ static void *kgalloc(size_t size, gfp_t gfp) #define IDA_SECTION_SIZE (PAGE_SIZE << IDA_ALLOC_ORDER_MAX) #define IDA_NODES_PER_SECTION (IDA_SECTION_SIZE / sizeof(unsigned long)) -static inline unsigned long *ida_index_to_node(struct ida *ida, unsigned node) +static inline unsigned long *__ida_index_to_node(struct ida *ida, unsigned node) { return ida->tree[node / IDA_NODES_PER_SECTION] + node % IDA_NODES_PER_SECTION; } +static inline unsigned long *ida_index_to_node(struct ida *ida, unsigned node) +{ + return __ida_index_to_node(ida, node + ida->pad); +} + /* * For a given number of nodes, calculate how many are going to be parent nodes * (equal to ida->first_leaf) and by extension how my will be leaves. @@ -106,6 +111,16 @@ static unsigned first_leaf_from_nodes(unsigned nodes) return ret; } +static unsigned first_leaf_from_leaves(unsigned leaves) +{ + unsigned ret = 0; + + while (ret * IDA_TREE_ARY + 1 - ret < leaves) + ret = ret * IDA_TREE_ARY + 1; + + return ret; +} + static void __ida_remove(struct ida *ida, unsigned int id) { unsigned i = ida->first_leaf + id / BITS_PER_LONG; @@ -150,53 +165,138 @@ void ida_remove(struct ida *ida, unsigned int id) EXPORT_SYMBOL(ida_remove); static void ida_increase_depth(struct ida *ida, unsigned new_nodes, - unsigned new_first_leaf) + unsigned new_first_leaf, unsigned new_pad) { unsigned old_leaves = ida->nodes - ida->first_leaf; - unsigned src = ida->nodes; - unsigned dst = new_first_leaf + old_leaves; unsigned n, i, bit; unsigned long *node; /* Shift leaves up to new position */ - while (src != ida->first_leaf) { - i = min((src - 1) % IDA_NODES_PER_SECTION + 1, - (dst - 1) % IDA_NODES_PER_SECTION + 1); - i = min(i, src - ida->first_leaf); + if (!((ida->pad + ida->first_leaf) % IDA_NODES_PER_SECTION) && + !((new_pad + new_first_leaf) % IDA_NODES_PER_SECTION)) { + unsigned sections_to_move = + (new_pad + new_first_leaf - + (ida->pad + ida->first_leaf)) / IDA_NODES_PER_SECTION; - src -= i; - dst -= i; + unsigned src = (ida->pad + ida->first_leaf) / IDA_NODES_PER_SECTION; - memmove(ida_index_to_node(ida, dst), - ida_index_to_node(ida, src), - i * sizeof(unsigned long)); + while (sections_to_move--) { + unsigned long *tmp = ida->tree[ida->sections - 1]; + + memmove(ida->tree + src + 1, + ida->tree + src, + (ida->sections - src - 1) * sizeof(unsigned long *)); + + ida->tree[src] = tmp; + } + } else if (ida->first_leaf + ida->pad != new_first_leaf + new_pad) { + unsigned src = ida->nodes + ida->pad; + unsigned dst = new_first_leaf + old_leaves + new_pad; + + while (src != ida->first_leaf + ida->pad) { + i = min((src - 1) % IDA_NODES_PER_SECTION + 1, + (dst - 1) % IDA_NODES_PER_SECTION + 1); + + i = min(i, src - (ida->first_leaf + ida->pad)); + + src -= i; + dst -= i; + + memmove(__ida_index_to_node(ida, dst), + __ida_index_to_node(ida, src), + i * sizeof(unsigned long)); + } } /* Zero out parent nodes */ - for (n = 0; n < new_first_leaf; n += i) { - i = min_t(unsigned, new_first_leaf - n, + for (n = 0; n < new_first_leaf + new_pad; n += i) { + i = min_t(unsigned, new_pad + new_first_leaf - n, IDA_NODES_PER_SECTION); - memset(ida_index_to_node(ida, n), + memset(__ida_index_to_node(ida, n), 0, i * sizeof(unsigned long)); } /* Reconstruct parent nodes */ for (n = new_first_leaf; n < new_first_leaf + old_leaves; n++) { i = n; - node = ida_index_to_node(ida, i); + node = __ida_index_to_node(ida, i + new_pad); while (!~*node && i) { bit = (i - 1) % IDA_TREE_ARY; i = (i - 1) / IDA_TREE_ARY; - node = ida_index_to_node(ida, i); + node = __ida_index_to_node(ida, i + new_pad); __set_bit(bit, node); } } } +static int do_ida_resize(struct ida *ida, unsigned long *tree, + unsigned long **sections, unsigned new_nodes, + unsigned new_first_leaf) +{ + unsigned new_pad = 0; + + if (sections) { + memcpy(sections, ida->tree, + ida->sections * sizeof(unsigned long *)); + + if (ida->tree != &ida->inline_section) + kgfree(ida->tree, ida->sections * sizeof(unsigned long *)); + + ida->tree = sections; + } + + if (ida->nodes < IDA_NODES_PER_SECTION) { + BUG_ON(new_nodes > IDA_NODES_PER_SECTION); + + memcpy(tree, ida_index_to_node(ida, 0), + ida->nodes * sizeof(unsigned long)); + + if (ida->tree[0] != &ida->inline_node) + kgfree(ida->tree[0], ida->nodes * sizeof(unsigned long)); + + ida->tree[0] = tree; + + BUG_ON(new_nodes - new_first_leaf < ida->nodes - ida->first_leaf); + } else { + unsigned leaf_sections, new_leaves; + + ida->tree[ida->sections++] = tree; + + leaf_sections = ida->sections - 1; + + while (1) { + new_leaves = leaf_sections * IDA_NODES_PER_SECTION; + + if (new_leaves < ida->nodes - ida->first_leaf) + return -1; + + new_first_leaf = first_leaf_from_leaves(new_leaves); + new_pad = round_up(new_first_leaf, IDA_NODES_PER_SECTION) - + new_first_leaf; + new_nodes = new_first_leaf + new_leaves; + + if (new_nodes <= ida->sections * IDA_NODES_PER_SECTION) + break; + + leaf_sections--; + } + } + + if (new_first_leaf != ida->first_leaf || + ida->pad != new_pad) + ida_increase_depth(ida, new_nodes, new_first_leaf, new_pad); + + ida->nodes = new_nodes; + ida->first_leaf = new_first_leaf; + ida->pad = new_pad; + + return 0; +} + /* * Attempt to double the size of the tree. We have to drop ida->lock to allocate * memory, so we might race with another allocation that also tries to resize. @@ -223,8 +323,8 @@ again: sections = NULL; cur_sections = ida->sections; - BUG_ON(ida->nodes > IDA_NODES_PER_SECTION && - ida->nodes % IDA_NODES_PER_SECTION); + BUG_ON((ida->pad + ida->nodes) > IDA_NODES_PER_SECTION && + (ida->pad + ida->nodes) % IDA_NODES_PER_SECTION); //spin_unlock_irqrestore(&ida->lock, *flags); @@ -250,44 +350,11 @@ again: return 0; } - if (sections) { - memcpy(sections, ida->tree, - ida->sections * sizeof(unsigned long *)); - - if (ida->tree != &ida->inline_section) - kgfree(ida->tree, ida->sections * sizeof(unsigned long *)); - - ida->tree = sections; - } - - if (ida->nodes < IDA_NODES_PER_SECTION) { - BUG_ON(new_nodes > IDA_NODES_PER_SECTION); - - memcpy(tree, ida_index_to_node(ida, 0), - ida->nodes * sizeof(unsigned long)); - - if (ida->tree[0] != &ida->inline_node) - kgfree(ida->tree[0], ida->nodes * sizeof(unsigned long)); - - ida->tree[0] = tree; - - BUG_ON(new_nodes - new_first_leaf < ida->nodes - ida->first_leaf); - } else { - ida->tree[ida->sections++] = tree; - - new_nodes = ida->sections * IDA_NODES_PER_SECTION; - new_first_leaf = first_leaf_from_nodes(new_nodes); - - if (new_nodes - new_first_leaf < ida->nodes - ida->first_leaf) - goto again; + if (do_ida_resize(ida, tree, sections, new_nodes, new_first_leaf)) { + /* Depth increases, but need to allocate more new nodes first */ + goto again; } - if (new_first_leaf != ida->first_leaf) - ida_increase_depth(ida, new_nodes, new_first_leaf); - - ida->nodes = new_nodes; - ida->first_leaf = new_first_leaf; - return 0; err: kgfree(sections, cur_sections * 2 * sizeof(unsigned long)); |