call_rcu(&node->rcu, mt_free_rcu);
}
-static unsigned int mt_height(const struct maple_tree *mt)
-{
- return (mt->ma_flags & MT_FLAGS_HEIGHT_MASK) >> MT_FLAGS_HEIGHT_OFFSET;
-}
static void mas_set_height(struct ma_state *mas)
{
unsigned char piv)
{
struct maple_node *node = mte_to_node(mn);
+ enum maple_type type = mte_node_type(mn);
- if (piv >= mt_pivots[piv]) {
+ if (piv >= mt_pivots[type]) {
WARN_ON(1);
return 0;
}
- switch (mte_node_type(mn)) {
+ switch (type) {
case maple_arange_64:
return node->ma64.pivot[piv];
case maple_range_64:
static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp)
{
struct maple_alloc *node;
- struct maple_alloc **nodep = &mas->alloc;
unsigned long allocated = mas_allocated(mas);
unsigned long success = allocated;
unsigned int requested = mas_alloc_req(mas);
node->node_count--;
success += count;
- nodep = &node->slot[0];
- node = *nodep;
+ node = node->slot[0];
requested -= count;
}
mas->alloc->total = success;
root = mas_root(mas);
/* Tree with nodes */
if (likely(xa_is_node(root))) {
+ mas->depth = 1;
mas->node = mte_safe_root(root);
return NULL;
}
unsigned long max, min;
unsigned long prev_max, prev_min;
- last = next = mas->node;
- prev_min = min = mas->min;
+ next = mas->node;
+ min = mas->min;
max = mas->max;
do {
offset = 0;
mast->free = &free;
mast->destroy = &destroy;
l_mas.node = r_mas.node = m_mas.node = MAS_NONE;
- if (!(mast->orig_l->min && mast->orig_r->max == ULONG_MAX) &&
+
+ /* Check if this is not root and has sufficient data. */
+ if (((mast->orig_l->min != 0) || (mast->orig_r->max != ULONG_MAX)) &&
unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type]))
mast_spanning_rebalance(mast);
node = mas_pop_node(wr_mas->mas);
node->parent = mas_mn(wr_mas->mas)->parent;
wr_mas->mas->node = mt_mk_node(node, b_type);
- mab_mas_cp(b_node, 0, b_end, wr_mas->mas, true);
-
+ mab_mas_cp(b_node, 0, b_end, wr_mas->mas, false);
mas_replace(wr_mas->mas, false);
reuse_node:
mas_update_gap(wr_mas->mas);
static inline void mas_wr_walk_descend(struct ma_wr_state *wr_mas)
{
- wr_mas->mas->depth++;
wr_mas->type = mte_node_type(wr_mas->mas->node);
mas_wr_node_walk(wr_mas);
wr_mas->slots = ma_slots(wr_mas->node, wr_mas->type);
wr_mas->mas->min = wr_mas->r_min;
wr_mas->mas->node = wr_mas->content;
wr_mas->mas->offset = 0;
+ wr_mas->mas->depth++;
}
/*
* mas_wr_walk() - Walk the tree for a write.
unsigned long *pivots, *gaps;
void __rcu **slots;
unsigned long gap = 0;
- unsigned long max, min, index;
+ unsigned long max, min;
unsigned char offset;
if (unlikely(mas_is_err(mas)))
min = mas_safe_min(mas, pivots, --offset);
max = mas_safe_pivot(mas, pivots, offset, type);
- index = mas->index;
- while (index <= max) {
+ while (mas->index <= max) {
gap = 0;
if (gaps)
gap = gaps[offset];
min = mas_safe_min(mas, pivots, offset);
}
- if (unlikely(index > max)) {
- mas_set_err(mas, -EBUSY);
- return false;
- }
+ if (unlikely((mas->index > max) || (size - 1 > max - mas->index)))
+ goto no_space;
if (unlikely(ma_is_leaf(type))) {
mas->offset = offset;
return false;
ascend:
- if (mte_is_root(mas->node))
- mas_set_err(mas, -EBUSY);
+ if (!mte_is_root(mas->node))
+ return false;
+no_space:
+ mas_set_err(mas, -EBUSY);
return false;
}
{
enum maple_type type = mte_node_type(mas->node);
unsigned long pivot, min, gap = 0;
- unsigned char count, offset;
- unsigned long *gaps = NULL, *pivots = ma_pivots(mas_mn(mas), type);
+ unsigned char offset;
+ unsigned long *gaps;
+ unsigned long *pivots = ma_pivots(mas_mn(mas), type);
void __rcu **slots = ma_slots(mas_mn(mas), type);
bool found = false;
gaps = ma_gaps(mte_to_node(mas->node), type);
offset = mas->offset;
- count = mt_slots[type];
min = mas_safe_min(mas, pivots, offset);
- for (; offset < count; offset++) {
+ for (; offset < mt_slots[type]; offset++) {
pivot = mas_safe_pivot(mas, pivots, offset, type);
if (offset && !pivot)
break;
mas->min = min;
mas->max = pivot;
offset = 0;
- type = mte_node_type(mas->node);
- count = mt_slots[type];
break;
}
}
return entry;
}
+EXPORT_SYMBOL_GPL(mas_walk);
static inline bool mas_rewind_node(struct ma_state *mas)
{
mas->last = mas->index + size - 1;
return 0;
}
+EXPORT_SYMBOL_GPL(mas_empty_area);
/*
* mas_empty_area_rev() - Get the highest address within the range that is
mas->index = mas->last - size + 1;
return 0;
}
+EXPORT_SYMBOL_GPL(mas_empty_area_rev);
static inline int mas_alloc(struct ma_state *mas, void *entry,
unsigned long size, unsigned long *index)
mas_wr_store_entry(&wr_mas);
return wr_mas.content;
}
+EXPORT_SYMBOL_GPL(mas_store);
/**
* mas_store_gfp() - Store a value into the tree.
return 0;
}
+EXPORT_SYMBOL_GPL(mas_store_gfp);
/**
* mas_store_prealloc() - Store a value into the tree using memory
BUG_ON(mas_is_err(mas));
mas_destroy(mas);
}
+EXPORT_SYMBOL_GPL(mas_store_prealloc);
/**
* mas_preallocate() - Preallocate enough nodes for a store operation
}
mas->alloc = NULL;
}
+EXPORT_SYMBOL_GPL(mas_destroy);
/*
* mas_expected_entries() - Set the expected number of entries that will be inserted.
return ret;
}
+EXPORT_SYMBOL_GPL(mas_expected_entries);
/**
* mas_next() - Get the next entry.
/* Retries on dead nodes handled by mas_next_entry */
return mas_next_entry(mas, max);
}
+EXPORT_SYMBOL_GPL(mas_find);
/**
* mas_find_rev: On the first call, find the first non-null entry at or below
/* Retries on dead nodes handled by mas_next_entry */
return mas_prev_entry(mas, min);
}
-EXPORT_SYMBOL_GPL(mas_find);
+EXPORT_SYMBOL_GPL(mas_find_rev);
/**
* mas_erase() - Find the range in which index resides and erase the entire
mas_rewalk(mas, index);
return 1;
}
-#endif /* not defined __KERNEL__ */
+void mt_cache_shrink(void)
+{
+}
+#else
+/*
+ * mt_cache_shrink() - For testing, don't use this.
+ *
+ * Certain testcases can trigger an OOM when combined with other memory
+ * debugging configuration options. This function is used to reduce the
+ * possibility of an out of memory even due to kmem_cache objects remaining
+ * around for longer than usual.
+ */
+void mt_cache_shrink(void)
+{
+ kmem_cache_shrink(maple_node_cache);
+
+}
+EXPORT_SYMBOL_GPL(mt_cache_shrink);
+
+#endif /* not defined __KERNEL__ */
/*
* mas_get_slot() - Get the entry in the maple state node stored at @offset.
* @mas: The maple state
else if (entry)
mt_dump_node(mt, entry, 0, mt_max[mte_node_type(entry)], 0);
}
+EXPORT_SYMBOL_GPL(mt_dump);
/*
* Calculate the maximum gap in a node and check if that's what is reported in
rcu_read_unlock();
}
+EXPORT_SYMBOL_GPL(mt_validate);
#endif /* CONFIG_DEBUG_MAPLE_TREE */
projects / platform / kernel / linux-starfive.git / blobdiff