Lines Matching +full:0 +full:xa
20 * @xa is used to refer to the entire xarray.
33 static inline unsigned int xa_lock_type(const struct xarray *xa) in xa_lock_type() argument
35 return (__force unsigned int)xa->xa_flags & 3; in xa_lock_type()
58 static inline bool xa_track_free(const struct xarray *xa) in xa_track_free() argument
60 return xa->xa_flags & XA_FLAGS_TRACK_FREE; in xa_track_free()
63 static inline bool xa_zero_busy(const struct xarray *xa) in xa_zero_busy() argument
65 return xa->xa_flags & XA_FLAGS_ZERO_BUSY; in xa_zero_busy()
68 static inline void xa_mark_set(struct xarray *xa, xa_mark_t mark) in xa_mark_set() argument
70 if (!(xa->xa_flags & XA_FLAGS_MARK(mark))) in xa_mark_set()
71 xa->xa_flags |= XA_FLAGS_MARK(mark); in xa_mark_set()
74 static inline void xa_mark_clear(struct xarray *xa, xa_mark_t mark) in xa_mark_clear() argument
76 if (xa->xa_flags & XA_FLAGS_MARK(mark)) in xa_mark_clear()
77 xa->xa_flags &= ~(XA_FLAGS_MARK(mark)); in xa_mark_clear()
117 } while (0)
128 unsigned int mark = 0; in xas_squash_marks()
190 entry = xa_head(xas->xa); in xas_start()
206 void *entry = xa_entry(xas->xa, node, offset); in xas_descend()
211 entry = xa_entry(xas->xa, node, offset); in xas_descend()
245 if (node->shift == 0) in xas_load()
304 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT) in xas_nomem()
326 __must_hold(xas->xa->xa_lock) in __xas_nomem()
328 unsigned int lock_type = xa_lock_type(xas->xa); in __xas_nomem()
334 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT) in __xas_nomem()
372 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT) in xas_alloc()
391 node->count = 0; in xas_alloc()
392 node->nr_values = 0; in xas_alloc()
394 node->array = xas->xa; in xas_alloc()
410 * multi-index entry at index 0, the calculation is a little more complex
433 return 0; in max_index()
439 struct xarray *xa = xas->xa; in xas_shrink() local
448 entry = xa_entry_locked(xa, node, 0); in xas_shrink()
453 if (xa_is_zero(entry) && xa_zero_busy(xa)) in xas_shrink()
457 RCU_INIT_POINTER(xa->xa_head, entry); in xas_shrink()
458 if (xa_track_free(xa) && !node_get_mark(node, 0, XA_FREE_MARK)) in xas_shrink()
459 xa_mark_clear(xa, XA_FREE_MARK); in xas_shrink()
461 node->count = 0; in xas_shrink()
462 node->nr_values = 0; in xas_shrink()
464 RCU_INIT_POINTER(node->slots[0], XA_RETRY_ENTRY); in xas_shrink()
478 * Attempts to delete the @xas->xa_node. This will fail if xa->node has
492 parent = xa_parent_locked(xas->xa, node); in xas_delete_node()
498 xas->xa->xa_head = NULL; in xas_delete_node()
525 unsigned int offset = 0; in xas_free_nodes()
529 void *entry = xa_entry_locked(xas->xa, node, offset); in xas_free_nodes()
533 offset = 0; in xas_free_nodes()
542 parent = xa_parent_locked(xas->xa, node); in xas_free_nodes()
544 node->count = 0; in xas_free_nodes()
545 node->nr_values = 0; in xas_free_nodes()
561 struct xarray *xa = xas->xa; in xas_expand() local
563 unsigned int shift = 0; in xas_expand()
567 if (max == 0) in xas_expand()
568 return 0; in xas_expand()
579 xa_mark_t mark = 0; in xas_expand()
589 RCU_INIT_POINTER(node->slots[0], head); in xas_expand()
593 if (xa_track_free(xa) && mark == XA_FREE_MARK) { in xas_expand()
595 if (!xa_marked(xa, XA_FREE_MARK)) { in xas_expand()
596 node_clear_mark(node, 0, XA_FREE_MARK); in xas_expand()
597 xa_mark_set(xa, XA_FREE_MARK); in xas_expand()
599 } else if (xa_marked(xa, mark)) { in xas_expand()
600 node_set_mark(node, 0, mark); in xas_expand()
612 xa_to_node(head)->offset = 0; in xas_expand()
616 rcu_assign_pointer(xa->xa_head, head); in xas_expand()
641 struct xarray *xa = xas->xa; in xas_create() local
649 entry = xa_head_locked(xa); in xas_create()
651 if (!entry && xa_zero_busy(xa)) in xas_create()
654 if (shift < 0) in xas_create()
658 entry = xa_head_locked(xa); in xas_create()
659 slot = &xa->xa_head; in xas_create()
666 entry = xa_entry_locked(xa, node, offset); in xas_create()
669 shift = 0; in xas_create()
670 entry = xa_head_locked(xa); in xas_create()
671 slot = &xa->xa_head; in xas_create()
680 if (xa_track_free(xa)) in xas_create()
713 xas->xa_shift = 0; in xas_create_range()
714 xas->xa_sibs = 0; in xas_create_range()
728 xas->xa_node = xa_parent_locked(xas->xa, node); in xas_create_range()
730 if (node->offset != 0) in xas_create_range()
758 if (count < 0) in update_node()
778 void __rcu **slot = &xas->xa->xa_head; in xas_store()
780 int count = 0; in xas_store()
781 int values = 0; in xas_store()
796 xas->xa_sibs = 0; in xas_store()
835 next = xa_entry_locked(xas->xa, node, ++offset); in xas_store()
862 return xa_marked(xas->xa, mark); in xas_get_mark()
888 node = xa_parent_locked(xas->xa, node); in xas_set_mark()
891 if (!xa_marked(xas->xa, mark)) in xas_set_mark()
892 xa_mark_set(xas->xa, mark); in xas_set_mark()
920 node = xa_parent_locked(xas->xa, node); in xas_clear_mark()
923 if (xa_marked(xas->xa, mark)) in xas_clear_mark()
924 xa_mark_clear(xas->xa, mark); in xas_clear_mark()
941 xa_mark_t mark = 0; in xas_init_marks()
944 if (xa_track_free(xas->xa) && mark == XA_FREE_MARK) in xas_init_marks()
958 unsigned int marks = 0; in node_get_marks()
1023 node->array = xas->xa; in xas_split_alloc()
1024 for (i = 0; i < XA_CHUNK_SIZE; i++) { in xas_split_alloc()
1025 if ((i & mask) == 0) { in xas_split_alloc()
1034 } while (sibs-- > 0); in xas_split_alloc()
1060 int values = 0; in xas_split()
1078 XA_CHUNK_SIZE : 0; in xas_split()
1131 if (!xa_is_sibling(xa_entry(xas->xa, node, offset))) in xas_pause()
1135 if (xas->xa_index == 0) in xas_pause()
1166 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in __xas_prev()
1172 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in __xas_prev()
1205 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in __xas_next()
1211 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in __xas_next()
1263 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in xas_find()
1267 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in xas_find()
1270 xas->xa_offset = 0; in xas_find()
1322 entry = xa_head(xas->xa); in xas_find_marked()
1327 if (xa_marked(xas->xa, mark)) in xas_find_marked()
1339 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in xas_find_marked()
1347 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in xas_find_marked()
1366 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in xas_find_marked()
1367 if (!entry && !(xa_track_free(xas->xa) && mark == XA_FREE_MARK)) in xas_find_marked()
1425 xas->xa_node = xa_parent_locked(xas->xa, xas->xa_node); in xas_find_conflict()
1430 curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset); in xas_find_conflict()
1435 xas->xa_offset = 0; in xas_find_conflict()
1436 curr = xa_entry_locked(xas->xa, xas->xa_node, 0); in xas_find_conflict()
1448 * @xa: XArray.
1452 * Return: The entry at @index in @xa.
1454 void *xa_load(struct xarray *xa, unsigned long index) in xa_load() argument
1456 XA_STATE(xas, xa, index); in xa_load()
1482 * @xa: XArray.
1492 void *__xa_erase(struct xarray *xa, unsigned long index) in __xa_erase() argument
1494 XA_STATE(xas, xa, index); in __xa_erase()
1501 * @xa: XArray.
1511 void *xa_erase(struct xarray *xa, unsigned long index) in xa_erase() argument
1515 xa_lock(xa); in xa_erase()
1516 entry = __xa_erase(xa, index); in xa_erase()
1517 xa_unlock(xa); in xa_erase()
1525 * @xa: XArray.
1538 void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp) in __xa_store() argument
1540 XA_STATE(xas, xa, index); in __xa_store()
1545 if (xa_track_free(xa) && !entry) in __xa_store()
1550 if (xa_track_free(xa)) in __xa_store()
1560 * @xa: XArray.
1575 void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp) in xa_store() argument
1579 xa_lock(xa); in xa_store()
1580 curr = __xa_store(xa, index, entry, gfp); in xa_store()
1581 xa_unlock(xa); in xa_store()
1589 * @xa: XArray.
1603 void *__xa_cmpxchg(struct xarray *xa, unsigned long index, in __xa_cmpxchg() argument
1606 XA_STATE(xas, xa, index); in __xa_cmpxchg()
1616 if (xa_track_free(xa) && entry && !curr) in __xa_cmpxchg()
1627 * @xa: XArray.
1638 * Return: 0 if the store succeeded. -EBUSY if another entry was present.
1641 int __xa_insert(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp) in __xa_insert() argument
1643 XA_STATE(xas, xa, index); in __xa_insert()
1655 if (xa_track_free(xa)) in __xa_insert()
1670 unsigned int shift = 0; in xas_set_range()
1676 while ((first & XA_CHUNK_MASK) == 0) { in xas_set_range()
1700 * @xa: XArray.
1716 void *xa_store_range(struct xarray *xa, unsigned long first, in xa_store_range() argument
1719 XA_STATE(xas, xa, 0); in xa_store_range()
1754 * @xa: XArray.
1757 * Return: A number between 0 and 63 indicating the order of the entry.
1759 int xa_get_order(struct xarray *xa, unsigned long index) in xa_get_order() argument
1761 XA_STATE(xas, xa, index); in xa_get_order()
1763 int order = 0; in xa_get_order()
1795 * @xa: XArray.
1801 * Finds an empty entry in @xa between @limit.min and @limit.max,
1810 * Return: 0 on success, -ENOMEM if memory could not be allocated or
1813 int __xa_alloc(struct xarray *xa, u32 *id, void *entry, in __xa_alloc() argument
1816 XA_STATE(xas, xa, 0); in __xa_alloc()
1820 if (WARN_ON_ONCE(!xa_track_free(xa))) in __xa_alloc()
1843 * @xa: XArray.
1850 * Finds an empty entry in @xa between @limit.min and @limit.max,
1861 * Return: 0 if the allocation succeeded without wrapping. 1 if the
1865 int __xa_alloc_cyclic(struct xarray *xa, u32 *id, void *entry, in __xa_alloc_cyclic() argument
1872 ret = __xa_alloc(xa, id, entry, limit, gfp); in __xa_alloc_cyclic()
1873 if ((xa->xa_flags & XA_FLAGS_ALLOC_WRAPPED) && ret == 0) { in __xa_alloc_cyclic()
1874 xa->xa_flags &= ~XA_FLAGS_ALLOC_WRAPPED; in __xa_alloc_cyclic()
1878 if (ret < 0 && limit.min > min) { in __xa_alloc_cyclic()
1880 ret = __xa_alloc(xa, id, entry, limit, gfp); in __xa_alloc_cyclic()
1881 if (ret == 0) in __xa_alloc_cyclic()
1885 if (ret >= 0) { in __xa_alloc_cyclic()
1887 if (*next == 0) in __xa_alloc_cyclic()
1888 xa->xa_flags |= XA_FLAGS_ALLOC_WRAPPED; in __xa_alloc_cyclic()
1896 * @xa: XArray.
1904 void __xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark) in __xa_set_mark() argument
1906 XA_STATE(xas, xa, index); in __xa_set_mark()
1916 * @xa: XArray.
1922 void __xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark) in __xa_clear_mark() argument
1924 XA_STATE(xas, xa, index); in __xa_clear_mark()
1934 * @xa: XArray.
1944 bool xa_get_mark(struct xarray *xa, unsigned long index, xa_mark_t mark) in xa_get_mark() argument
1946 XA_STATE(xas, xa, index); in xa_get_mark()
1966 * @xa: XArray.
1974 void xa_set_mark(struct xarray *xa, unsigned long index, xa_mark_t mark) in xa_set_mark() argument
1976 xa_lock(xa); in xa_set_mark()
1977 __xa_set_mark(xa, index, mark); in xa_set_mark()
1978 xa_unlock(xa); in xa_set_mark()
1984 * @xa: XArray.
1992 void xa_clear_mark(struct xarray *xa, unsigned long index, xa_mark_t mark) in xa_clear_mark() argument
1994 xa_lock(xa); in xa_clear_mark()
1995 __xa_clear_mark(xa, index, mark); in xa_clear_mark()
1996 xa_unlock(xa); in xa_clear_mark()
2002 * @xa: XArray.
2007 * Finds the entry in @xa which matches the @filter, and has the lowest
2017 void *xa_find(struct xarray *xa, unsigned long *indexp, in xa_find() argument
2020 XA_STATE(xas, xa, *indexp); in xa_find()
2052 * @xa: XArray.
2057 * Finds the entry in @xa which matches the @filter and has the lowest
2067 void *xa_find_after(struct xarray *xa, unsigned long *indexp, in xa_find_after() argument
2070 XA_STATE(xas, xa, *indexp + 1); in xa_find_after()
2073 if (xas.xa_index == 0) in xa_find_after()
2102 unsigned int i = 0; in xas_extract_present()
2121 unsigned int i = 0; in xas_extract_marked()
2138 * @xa: The source XArray to copy from.
2164 unsigned int xa_extract(struct xarray *xa, void **dst, unsigned long start, in xa_extract() argument
2167 XA_STATE(xas, xa, start); in xa_extract()
2170 return 0; in xa_extract()
2188 .xa = node->array, in xa_delete_node()
2203 * @xa: XArray.
2211 void xa_destroy(struct xarray *xa) in xa_destroy() argument
2213 XA_STATE(xas, xa, 0); in xa_destroy()
2219 entry = xa_head_locked(xa); in xa_destroy()
2220 RCU_INIT_POINTER(xa->xa_head, NULL); in xa_destroy()
2222 if (xa_zero_busy(xa)) in xa_destroy()
2223 xa_mark_clear(xa, XA_FREE_MARK); in xa_destroy()
2248 for (i = 0; i < XA_MAX_MARKS; i++) in xa_dump_node()
2249 for (j = 0; j < XA_MARK_LONGS; j++) in xa_dump_node()
2259 pr_info("0-%lu: ", ~0UL); in xa_dump_index()
2272 if (shift == 0) { in xa_dump_entry()
2278 for (i = 0; i < XA_CHUNK_SIZE; i++) in xa_dump_entry()
2283 pr_cont("value %ld (0x%lx) [%px]\n", xa_to_value(entry), in xa_dump_entry()
2297 void xa_dump(const struct xarray *xa) in xa_dump() argument
2299 void *entry = xa->xa_head; in xa_dump()
2300 unsigned int shift = 0; in xa_dump()
2302 pr_info("xarray: %px head %px flags %x marks %d %d %d\n", xa, entry, in xa_dump()
2303 xa->xa_flags, xa_marked(xa, XA_MARK_0), in xa_dump()
2304 xa_marked(xa, XA_MARK_1), xa_marked(xa, XA_MARK_2)); in xa_dump()
2307 xa_dump_entry(entry, 0, shift); in xa_dump()