Skip to content

Commit 3159f94

Browse files
author
Matthew Wilcox
committed
xarray: Replace exceptional entries
Introduce xarray value entries and tagged pointers to replace radix tree exceptional entries. This is a slight change in encoding to allow the use of an extra bit (we can now store BITS_PER_LONG - 1 bits in a value entry). It is also a change in emphasis; exceptional entries are intimidating and different. As the comment explains, you can choose to store values or pointers in the xarray and they are both first-class citizens. Signed-off-by: Matthew Wilcox <willy@infradead.org> Reviewed-by: Josef Bacik <jbacik@fb.com>
1 parent 66ee620 commit 3159f94

File tree

26 files changed

+278
-232
lines changed

26 files changed

+278
-232
lines changed

‎arch/powerpc/include/asm/book3s/64/pgtable.h

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -723,9 +723,7 @@ static inline bool pte_user(pte_t pte)
723723
BUILD_BUG_ON(_PAGE_HPTEFLAGS & (0x1f << _PAGE_BIT_SWAP_TYPE)); \
724724
BUILD_BUG_ON(_PAGE_HPTEFLAGS & _PAGE_SWP_SOFT_DIRTY); \
725725
} while (0)
726-
/*
727-
* on pte we don't need handle RADIX_TREE_EXCEPTIONAL_SHIFT;
728-
*/
726+
729727
#define SWP_TYPE_BITS 5
730728
#define __swp_type(x) (((x).val >> _PAGE_BIT_SWAP_TYPE) \
731729
& ((1UL << SWP_TYPE_BITS) - 1))

‎arch/powerpc/include/asm/nohash/64/pgtable.h

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -313,9 +313,7 @@ static inline void __ptep_set_access_flags(struct vm_area_struct *vma,
313313
#define MAX_SWAPFILES_CHECK() do { \
314314
BUILD_BUG_ON(MAX_SWAPFILES_SHIFT > SWP_TYPE_BITS); \
315315
} while (0)
316-
/*
317-
* on pte we don't need handle RADIX_TREE_EXCEPTIONAL_SHIFT;
318-
*/
316+
319317
#define SWP_TYPE_BITS 5
320318
#define __swp_type(x) (((x).val >> _PAGE_BIT_SWAP_TYPE) \
321319
& ((1UL << SWP_TYPE_BITS) - 1))

‎drivers/gpu/drm/i915/i915_gem.c

Lines changed: 7 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -5996,7 +5996,8 @@ i915_gem_object_get_sg(struct drm_i915_gem_object *obj,
59965996
count = __sg_page_count(sg);
59975997

59985998
while (idx + count <= n) {
5999-
unsigned long exception, i;
5999+
void *entry;
6000+
unsigned long i;
60006001
int ret;
60016002

60026003
/* If we cannot allocate and insert this entry, or the
@@ -6011,12 +6012,9 @@ i915_gem_object_get_sg(struct drm_i915_gem_object *obj,
60116012
if (ret && ret != -EEXIST)
60126013
goto scan;
60136014

6014-
exception =
6015-
RADIX_TREE_EXCEPTIONAL_ENTRY |
6016-
idx << RADIX_TREE_EXCEPTIONAL_SHIFT;
6015+
entry = xa_mk_value(idx);
60176016
for (i = 1; i < count; i++) {
6018-
ret = radix_tree_insert(&iter->radix, idx + i,
6019-
(void *)exception);
6017+
ret = radix_tree_insert(&iter->radix, idx + i, entry);
60206018
if (ret && ret != -EEXIST)
60216019
goto scan;
60226020
}
@@ -6054,15 +6052,14 @@ i915_gem_object_get_sg(struct drm_i915_gem_object *obj,
60546052
GEM_BUG_ON(!sg);
60556053

60566054
/* If this index is in the middle of multi-page sg entry,
6057-
* the radixtree will contain an exceptional entry that points
6055+
* the radix tree will contain a value entry that points
60586056
* to the start of that range. We will return the pointer to
60596057
* the base page and the offset of this page within the
60606058
* sg entry's range.
60616059
*/
60626060
*offset = 0;
6063-
if (unlikely(radix_tree_exception(sg))) {
6064-
unsigned long base =
6065-
(unsigned long)sg >> RADIX_TREE_EXCEPTIONAL_SHIFT;
6061+
if (unlikely(xa_is_value(sg))) {
6062+
unsigned long base = xa_to_value(sg);
60666063

60676064
sg = radix_tree_lookup(&iter->radix, base);
60686065
GEM_BUG_ON(!sg);

‎drivers/staging/erofs/utils.c

Lines changed: 6 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,6 @@ static atomic_long_t erofs_global_shrink_cnt;
3535

3636
#ifdef CONFIG_EROFS_FS_ZIP
3737

38-
/* radix_tree and the future XArray both don't use tagptr_t yet */
3938
struct erofs_workgroup *erofs_find_workgroup(
4039
struct super_block *sb, pgoff_t index, bool *tag)
4140
{
@@ -47,9 +46,8 @@ struct erofs_workgroup *erofs_find_workgroup(
4746
rcu_read_lock();
4847
grp = radix_tree_lookup(&sbi->workstn_tree, index);
4948
if (grp != NULL) {
50-
*tag = radix_tree_exceptional_entry(grp);
51-
grp = (void *)((unsigned long)grp &
52-
~RADIX_TREE_EXCEPTIONAL_ENTRY);
49+
*tag = xa_pointer_tag(grp);
50+
grp = xa_untag_pointer(grp);
5351

5452
if (erofs_workgroup_get(grp, &oldcount)) {
5553
/* prefer to relax rcu read side */
@@ -83,9 +81,7 @@ int erofs_register_workgroup(struct super_block *sb,
8381
sbi = EROFS_SB(sb);
8482
erofs_workstn_lock(sbi);
8583

86-
if (tag)
87-
grp = (void *)((unsigned long)grp |
88-
1UL << RADIX_TREE_EXCEPTIONAL_SHIFT);
84+
grp = xa_tag_pointer(grp, tag);
8985

9086
err = radix_tree_insert(&sbi->workstn_tree,
9187
grp->index, grp);
@@ -131,9 +127,7 @@ unsigned long erofs_shrink_workstation(struct erofs_sb_info *sbi,
131127

132128
for (i = 0; i < found; ++i) {
133129
int cnt;
134-
struct erofs_workgroup *grp = (void *)
135-
((unsigned long)batch[i] &
136-
~RADIX_TREE_EXCEPTIONAL_ENTRY);
130+
struct erofs_workgroup *grp = xa_untag_pointer(batch[i]);
137131

138132
first_index = grp->index + 1;
139133

@@ -150,8 +144,8 @@ unsigned long erofs_shrink_workstation(struct erofs_sb_info *sbi,
150144
#endif
151145
continue;
152146

153-
if (radix_tree_delete(&sbi->workstn_tree,
154-
grp->index) != grp) {
147+
if (xa_untag_pointer(radix_tree_delete(&sbi->workstn_tree,
148+
grp->index)) != grp) {
155149
#ifdef EROFS_FS_HAS_MANAGED_CACHE
156150
skip:
157151
erofs_workgroup_unfreeze(grp, 1);

‎fs/btrfs/compression.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -440,7 +440,7 @@ static noinline int add_ra_bio_pages(struct inode *inode,
440440
rcu_read_lock();
441441
page = radix_tree_lookup(&mapping->i_pages, pg_index);
442442
rcu_read_unlock();
443-
if (page && !radix_tree_exceptional_entry(page)) {
443+
if (page && !xa_is_value(page)) {
444444
misses++;
445445
if (misses > 4)
446446
break;

0 commit comments

Comments
 (0)